DAgger vysvětleno: Proč se behavior cloning plánuje a co agregace datových sad skutečně dokazuje

Existuje specifická selhání, kterou potkává každý, kdo trénuje manipulační politiku dříve nebo později. Politika dosáhne krychle, dostane se do dvou centimetrů, váhá, posunutí stranou, pak dělá něco nesouvisejícího s úkolem. Validační loss byla v pořádku. Open-loop přehrávka proti vybraným episódám byla v pořádku. A přesto paži skončí v póze, která se nikdy neobjevuje v trénovacích datech a odtud nemá nic rozumného na řeknutí.

Toto selhání má jméno a ustálený teoretický základ. Toto je první ze čtyř článků o DAgger, a pokrývá samotný argument: proč přizpůsobení politiky na vlastní trajektorie demonstranta produkuje chybu, která může růst s druhou mocninou délky epizody, co agregace datových sad mění, a co zaručuje důkaz bez regretů. Smyčka na skutečném hardwaru je pokryta v spuštění DAgger smyčky na SO-100, varianta s bránou člověka v HG-DAgger a intervence s bránou člověka, a měřicí otázka v měření DAgger smyčky.

Předpoklad, který behavior cloning tiše dělá

Demonstrační datová sada je hromada párů pozorování-akce. Behavior cloning přizpůsobí funkci této hromadě s běžným učením pod dohledem a zastaví se. Je to nejstarší myšlenka v oboru. Pomerleau's ALVINN, v roce 1988, byla třívrstvá back-propagation síť, která vzala obrázky z kamery a laserového skenovacího zařízení a vytvořila směr, kterým by se vozidlo mělo ubírat; byla trénována na simulovaných silničních obrázcích a sledovala skutečné silnice za některých polních podmínek. Recept se příliš nezměnil; sítě ano.

Co se přeskakuje, je kontrola toho, odkud tyto páry pochází. Každý z nich leží na trajektorii, kterou demonstrant vytvořil. Politika, kterou nasadíte, vytváří svou vlastní. Ve chvíli, kdy se odchýlí, je dotazována na stavy, které nebyly v distribuci tréninku, a její odpověď ji posunuje dále. Ross, Gordon a Bagnell otvírají dokument DAgger právě tímto: sekvenční predikce porušuje i.i.d. předpoklad pod statistickým učením, protože learnerovy vlastní předpovědi určují vstupy, které vidí dále.

Nejjasnější ilustrace v tomto dokumentu není vůbec robot. Klonování téměř optimálního plánovače pro Super Mario Bros. vytvořilo politiku, která se opakovaně zasekla proti překážce místo přeskočení. Důvod je celý argument v jedné větě: expert vždy skočil z pohodlné vzdálenosti, takže datová sada neobsahovala žádný stav, ve kterém by byl Mario tlačen proti překážce, a proto žádný štítek co dělat, jakmile tam byl.

Nahraďte Mario za SO-100 paži a struktura je totožná. Vaše demonstrace ukazují čistý přístup a čistý úchop, ne gripper zavírající se dva centimetry krátkým - takže politika neví, co dělat odtud, a ať si myslí cokoliv, vezme to dále. Posun kovariantů je vlastnost procedury sběru dat, ne architekturou sítě.

Odkud pochází kvadratický člen

Dokument AISTATS z roku 2010 od Rosse a Bagnella, Efficient Reductions for Imitation Learning, činí kumulativní chybu přesnou. Nechť T je horizont úkolu, nechť náklady na úkol jsou vázány v jednotkovém intervalu a nechť epsilon je náhradní ztráta měřená pod distribucí stavů experta - číslo, které vaše validační sada hlásí. Pak jsou extra náklady na spuštění této politiky pro T kroků relativní k expertovi vázány na T na druhou násobeno epsilon. Ross, Gordon a Bagnell znovu uvádějí toto jako Větu 2.1 v dokumentu DAgger a přidávají větu, která záleží: vázání je těsné. Problémy existují, kde politika s epsilon ztrátou na distribuci experta skutečně zvyšuje extra náklady kvadraticky v T.

Těsně neznamená typicky. Kvadratický člen je nejhorší případ v třídě problémů, ne předpověď o vašem úkolu vychytávání a umisťování. Co to stanovuje, je, že více expert demonstrací nemůže odstranit problém: pouze zlepšuje odhad epsilon na distribuci, na které politika nebude testována.

Cesta úhybu je ve stejném dokumentu, znovu uvedena jako Věta 2.2. Pokud politika dosahuje ztráty epsilon pod vlastní distribuci stavů a jediná chybná akce stojí nejvýše u v ceně k cíli pod expertem, extra náklady jsou vázány na u krát T krát epsilon - lineárně v horizontu. Konstanta u je zajímavá veličina: nejvýše 1 pro 0-1 nesouhlas s expertem a O(1) kdykoli expert může obnovit během pár kroků. V nejhorším případě je O(T) a lineární vázání není pak lepší než kvadratické.

Dva pokusy, které přišly před DAgger

Forward training je čestná, ale nepraktická odpověď. Trénujte samostatnou politiku pro každý časový krok, v pořádku, každou na distribuci stavů vyvolané politikami již fixovanými pro předchozí kroky, takže každá politika vidí přesně distribuci, které bude čelit. Háček je v popisu: T politik, trénovaných postupně, bez brzkého zastavení. Pro manipulační epizodu při 30 snímcích za sekundu, T je v stovkách.

SMILe, ze stejného článku, a SEARN, z práce Daumé, Langforda a Marcua o strukturovaném předpovídání, berou druhou cestu: jeden stacionární politika, ale stochastická. Každá iterace trénuje komponentu a přidá ji do směsi, posouvá hmotu pravděpodobnosti pryč od experta. Výsledkem je směs, ve které jsou některé komponenty horší než jiné - na fyzickém paži, kontrolér, který může vzorkovat špatnou komponentu uprostřed pohybu. To je uvedený důvod pro přání stacionární deterministické politiky místo.

DAgger: jedna myšlenka, jedna krabice

Agregace datových sad udržuje deterministickou politiku a přesune opravu do sběru dat. Každé kolo: vyrolujte aktuální politiku, zaznamenávejte stavy, které navštěvuje, požádejte experta, jaká by byla správná akce v každé, přidejte tyto páry do datové sady, kterou již máte, přetrénujte na unii. Jméno je algoritmus - agregujete, nikdy neodstraňujete.

D            <- {}                      # the aggregate dataset
pi_hat_1     <- any policy in Pi

for i = 1 .. N:
    pi_i  = beta_i * expert  +  (1 - beta_i) * pi_hat_i
    roll out pi_i for T steps, record every visited state s
    D_i   = { (s, expert(s))  for every visited state s }
    D     = D  union  D_i               # aggregate, do not replace
    pi_hat_{i+1} = train on all of D

return the best pi_hat_i on a validation set

Tři detaily mají větší váhu, než vypadají. Štítky jsou pro stavy navštívené smíšenou politikou, ale akce pochází od experta - politika poskytuje otázky, expert odpovědi. Přetrénování probíhá na celkové agregaci, což dělá každé kolo krokem Follow-The-Leader: v kole n si vyberete nejlepší politiku zpětně nad každou trajektorií dosud. Toto je rámce, na které důkaz visí. A algoritmus končí vrácením nejlepší politiky v pořadí jako zvolené v sadě validace, protože věty zaručují, že nějaká politika v pořadí je dobrá, ne že poslední je.

Harmonogram beta a proč to není stavěcí knop

Smíšená politika je beta_i krát expert plus jeden minus beta_i krát learner. Bod je praktický: první pár naučených politik je trénováno na velmi málo dat, dělá spoustu chyb a by jinak strávila zavedení ve stavech, které se stanou irelevantními, jakmile se politika zlepší.

Teorie ukládá přesně jednu podmínku: průměr běhu beta musí jít na nulu. Analýza funguje s beta_i omezenou (1 - alfa) na mocninu i-1, pro konstantu alfa nezávislou na T.

Propast mezi 2980 a 3030 na měřítku běžícím zhruba do 4300 je malá, ale vysvětlení dokumentu je nejužitečnější praktická poznámka v sekci. S verzí bez parametrů se Mario zasekl na stejném místě brzy a vytvořil hromadu téměř duplikátních dat z jedné lokality; nechat experta jet zlomek času jak ho uvolnili tak rozšířili rozmanitost stavů. Harmonogram je méně o poměru míchání než o tom, zda váš sběr dat stále vytváří nové stavy nebo stejné selhání.

Záruka: redukce na online learning bez regretů

Tady je tah, který dělá papír tím, co je. Ošetřete každé kolo DAgger jako jeden příklad v online learning problému, kde ztráta na kole i je náhradní ztráta pod distribuci stavů politiky používané na kole i. Learner se zaváží politikou dříve, než vidí tuto ztrátu, a sekvence je nestacionární, protože závisí na politikách dosud vytvořených.

Algoritmus bez regretů, pokud jeho průměrná ztráta v N kolech přistupuje té nejlepší jednotlivé politiky zpětně. Follow-The-Leader na silně konvexních ztrátách je takový algoritmus, s průměrným regret zmenšujícím se v pořadí 1/N - a přetrénování na plné agregaci je přesně Follow-The-Leader. Jakýkoli jiný learner bez regretů by sloužil stejně dobře: analýza je redukce, ne vlastnost jednoho optimizéru.

Jedno lema překlenuje propast mezi smíšenou politikou, která shromáždila data, a naučenou politikou, která bude nasazena: Lema 4.1 hraničí L1 vzdálenost mezi jejich distribucemi stavů 2 T beta_i. To je důvod, proč se beta musí rozpad - zatímco expert stále drží značnou autoritu řízení, stavy, které shromažďujete, nejsou stavy, které vaše politika bude produkovat. Kombinujte lema s vazbou regret a hlavní výsledek následuje: po zhruba T iteracích, nějaká politika v pořadí má náhradní ztrátu pod vlastní distribucí v rámci O(1/T) epsilon_N. Krmte to do lineární vazby a přistanete na Větě 3.2.

Empirická strana je skromná podle dnešních standardů. V Super Tux Kart supervizovaný baseline nezlepšil svůj průměr pádů za kolo, když přišlo více dat, DAgger dosáhl politiky, která nikdy nespadla ze stopy po patnácti iteracích a SMILe po dvaceti stále padl zhruba dvakrát za kolo. Na benchmarku psaní, přesnost znaků běžela 82 procent bez struktury, 83,6 procent supervizované, 85,5 procent s DAgger. Žádný z nich není manipulační výsledek.

Co důkaz neslibuje

Věty jsou podmíněné a podmínky jsou zátěž.

Jeden další výsledek je často citován jako vyvrácení a není jeden. Rajaraman, Yang, Jiao a Ramachandran studují minimax limity imitation learning v episodických MDP s konečným stavovým prostorem S a horizontem H a prokazují horní mez suboptimalnosti v pořadí |S| H na druhou přes N, která platí i když se learner může aktivně dotazovat experta na navštívené stavy. To je nejhorší případ over třídy MDP na pevném rozpočtu epizod a co to vylučuje, je myšlenka, že interakce zlepšuje minimax sazbu; věta DAgger je jiné tvrzení, hraničící nasazenou politiku relativně k tomu, co může dosáhnout její třída politiky.

Swamy, Choudhury, Bagnell a Wu později klasifikovali tyto algoritmy podle toho, které momenty chování experta se shodují, a zavedli pojem obnova momentu, která vymezuje, jak dobře každá rodina zmírňuje kumulativní chybu. Průzkumy od Osy a od Celemína pokrývají algoritmickou krajinu a lidská zpětná vazba rozhraní.

Účet: označování stavů, které expert nikdy nevytvořil

Vše výše předpokládá experta, který se může dotázat kdekoli. V simulaci s plánovačem, který je téměř zdarma - Mario experimenty používaly téměř optimální plánovač s plným přístupem ke stavu hry. S člověkem na robotovi je to dominantní náklady a podivný: člověk musí vytvořit správnou akci v konfiguraci, kterou jejich vlastní kompetence by nikdy nevytvořila.

Kelly, Sidrane, Driggs-Campbell a Kochenderfer státi námitku přímo v papíru HG-DAgger. Vanilka DAgger vyžaduje, aby expert poskytl štítky akcí, aby nebyl plně v kontrole systému. Toto snižuje bezpečnost a s lidskými experty se pravděpodobně zhorší kvalita shromážděných štítků, které připisují vnímaným zpožděním aktuátoru. Štítek, který dostanete zpět, není štítek, který algoritmus předpokládal.

Laskey a kolegové útočí na problém z druhé strany s DART a jejich rámec je přímý: on-policy techniky jsou únavné pro lidské supervizory, přidávají výpočetní zátěž a mohou navštívit nebezpečné stavy během tréninku. Jejich alternativou je injekce kalibrovaného šumu do vlastních demonstrací supervizora, takže obnovení se demonstruje bez robota, který by někdy spustil nedůvěryhodnou politiku. Na MuJoCo Humanoid hlásí DART snížení kumulativní odměny supervizora o 5 procent během tréninku, zatímco DAgger spouští politiky s 80 procenty nižší kumulativní odměnou než supervizor; na uchopování v zmatku s Toyota HSR průměrný nárůst o 62 procent nad behavior cloning.

Zhang a Cho's SafeDAgger léčí dotazy na referenční politiku jako vzácný zdroj: samostatná bezpečnostní politika předpovídá, bez dotazování, zda se primární politika chystá odchýlit od reference za práh a pouze tyto stavy se předávají. Všechny tři reagují na stejný fakt - analýza DAgger neúčtuje nic za štítky experta a realita účtuje velmi hodně.

Co to znamená pro SO-100 na vašem stole

Přeložit horizont do vašich vlastních jednotek. Dvaceticekunda epizoda při 30 snímcích za sekundu je 600 rozhodovacích kroků a T v každé vazbě výše je to číslo. Při T = 600, rozdíl mezi termínem škálováním T a jedním škálováním s T na druhou je rozdíl mezi politikou, která se obnoví ze špatného přístupu a jednou, která ne.

To je částečně proč akce chunking pomáhá: když politika emituje krátkou sekvenci akcí na krok odvozování, počet rozhodovacích bodů padá a také počet šancí ke sčítání. Zhao, Kumar, Levine a Finn pojmenují kumulativní chybu jako motivaci pro Action Chunking with Transformers a hlásí 80 až 90 procent úspěchu na šesti obtížných úlohách v reálném světě, na levném bimanálním hardwaru, z deseti minut demonstrací. Chunking neodstraňuje posun kovariantů - stavy jsou stále vlastní politiky - ale zkracuje efektivní horizont. Vidět chunking akcí a SO-100 průvodce imitation learning.

Druhý překlad je metriku pokroku. Nemůžete měřit epsilon pod vlastní distribucí politiky přímo - to potřebuje správné akce experta pro každý navštívený stav, věc, kterou se snažíte vyhnout vytváření. Co vám místo toho dá smyčka s bránou člověka je míra intervence: zlomek snímků v běhu, během kterého člověk převzal. Je to proxy a pohybuje se z důvodů souvisejících s politikou - trpělivý operátor zasahuje méně. Používáno důsledně, je to jediné číslo, které říká, zda bylo kolo stojí za odpoledne.

Třetí překlad je varování kvality dat, která analýza nepokrývá. Mandlekar a kolegové studovali šest offline learning algoritmů na pěti simulovaných a třech reálných manipulačních úkolech vícestupňového a hlásí citlivost na algoritmické volby designu, závislost na kvalitě demonstrací a variabilitu způsobenou kritériem zastavení. Belkhale, Cui a Sadigh tvrdí, že kvalita datové sady by měla být formalizována prostřednictvím divergence akcí a rozmanitosti přechodu a poznamenávají, že rozmanitost stavů není vždy prospěšná. Kolo DAgger přidává stavy, které nikdo záměrně nevybral: některé jsou data obnovy, která potřebujete, některá jsou robot bitkující se, když se potácíte po ovládání přejetí.

Mechanicky kolo je šest kroků: spusťte odvozování se záznamem, převezměte, když politika chybuje, zkontrolujte běh a archivujte každou epizodu, synchronizujte opravy, skomponujte smíšenou datovou sadu z originálů plus opravy s výběrem epizod provedeno explicitně pro zdroj a pokračujte v tréninku z předchozího bodu kontroly spíše než základní model. Na ay-robots tyto kroky existují jako tlačítka, která odstraňují potrubí, ale ne úsudek. Dva varování: pokračování z bodu kontroly inicializuje váhy a není obnovením optimizéru, a posun zarovnání vedoucího paže je stále lehce testován na hardwaru. Vidět trénování a datové sady.

Rodokmen, v jedné tabulce

Často kladené otázky

Kam jít odtud

Pokud jste ještě netrénovali politiku, tato teorie je předčasná: nejdříve zaznamenejte datovou sadu, počínaje trénování vaší první politiky a desktopový klient. Pokud vážíte dalších sto čistých demonstrací proti zahájení oprav: čisté demonstrace neopraví problém distribuce. Pro mechaniku pokračujte s variantou s bránou člověka a pak průvodce SO-100.