DAgger Explicat: De ce Behavior Cloning Se Abate și Ce Dovedește Agregarea Setului de Date

Există o defecțiune specifică pe care o întâlnește oricine care antrenează o politică de manipulare mai devreme sau mai târziu. Politica se întinde către cub, se apropie la doi centimetri, ezită, alunecă lateral, apoi face ceva neînrudit cu sarcina. Pierderea de validare a fost bună. Redarea în buclă deschisă față de episoadele ținute separate a fost bună. Și totuși brațul se termină într-o poziție care nu apare nicăieri în datele de antrenare, și de acolo nu are nimic sensibil de spus.

Această defecțiune are un nume și o teorie stabilită în spatele ei. Acesta este primul din patru articole despre DAgger, și acoperă argumentul în sine: de ce potrivirea unei politici pe propriile traiectorii ale demonstratorului produce o eroare care poate crește cu pătratul lungimii episodului, ce schimbă agregarea setului de date, și ce nu promite dovada de non-regret. Bucla pe hardware real este acoperită în rularea unei bucle DAgger pe un SO-100, varianta cu gate uman în HG-DAgger și intervenții cu gate uman, și întrebarea măsurării în măsurarea unei bucle DAgger.

Presupunerea pe care o face în tăcere behavior cloning

Un set de date de demonstrare este o grămadă de perechi observație-acțiune. Behavior cloning se potrivește o funcție la acea grămadă cu învățare supravegheată obișnuită și se oprește acolo. Este cea mai veche idee din domeniu. ALVINN al lui Pomerleau, în 1988, era o rețea de propagare inversă cu trei straturi care lua imagini dintr-o cameră și un telemetru cu rază laser și producea direcția în care ar trebui să se deplaseze vehiculul; a fost antrenată pe imagini de drumuri simulate și a urmat drumuri reale în unele condiții de teren. Rețeta nu s-a schimbat mult; rețelele au.

Ceea ce se omite este o verificare a locului de unde provin acele perechi. Fiecare dintre ele se află pe o traiectorie pe care a produs-o demonstratorul. Politica pe care o implementezi produce a sa proprie. În momentul în care se abate, este întrebată despre stări care nu au fost în distribuția de antrenare, și răspunsul ei o mută mai departe. Ross, Gordon și Bagnell deschid lucrarea DAgger cu exact aceasta: predicția secvențială încalcă presupunerea i.i.d. din spatele învățării statistice, deoarece propriile predicții ale celui care învață determină intrările pe care le vede apoi.

Cea mai clară ilustrare din acea lucrare nu este un robot deloc. Clonarea unui planificator aproape optim pentru Super Mario Bros. a produs o politică care s-a blocat în mod repetat împotriva unui obstacol în loc să-l sară. Motivul este întregul argument într-o singură propoziție: expertul a sărit întotdeauna de la o distanță confortabilă, deci setul de date nu conținea starea în care Mario era apăsat asupra unui obstacol, și deci nici o etichetă pentru ceea ce trebuie să facă o dată ce era.

Schimbă Mario pentru un SO-100 arm și structura este identică. Demonstrațiile tale arată o apropiere curată și o apriendere curată, nu griperul închizând doi centimetri scurt - deci politica nu are idee ce să facă de acolo, și orice ghicește o ia mai departe. Covariate shift este o proprietate a procedura de colectare a datelor, nu a arhitecturii rețelei.

De unde provine termenul pătratic

Lucrarea AISTATS din 2010 de Ross și Bagnell, Efficient Reductions for Imitation Learning, face compunerea precisă. Fie T orizontul sarcinii, fie costul sarcinii este mărginit în intervalul unitar, și fie epsilon pierderea suplimentară măsurată sub expert's distribuția stării - numărul pe care setul dvs. de validare îl raportează. Apoi costul suplimentar al executării acelei politici pentru T pași, relativă la expert, este mărginit de T pătrat ori epsilon. Ross, Gordon și Bagnell reafirmă aceasta ca Teorema 2.1 în lucrarea DAgger și adaugă propoziția care contează: limita este strânsă. Problemele există în care o politică cu epsilon pierdere pe distribuția expertului într-adevăr suportă cost suplimentar crescând pătratic în T.

Strâns nu înseamnă tipic. Termenul pătratic este un caz în cel mai rău caz pe o clasă de probleme, nu o predicție despre sarcina ta de cules și plasare. Ceea ce stabilește este că mai multă demonstrație expert nu poate elimina problema: doar reafirmă estimarea epsilon pe o distribuție pe care politica nu va fi testată.

Ruta de evadare este în aceeași lucrare, reafirmată ca Teorema 2.2. Dacă o politică obține pierdere epsilon sub its own distribuția stării, și o singură acțiune greșită costă cel mult u în cost-la-merge sub expert, costul suplimentar este mărginit de u ori T ori epsilon - liniar în orizont. Constanta u este cantitatea interesantă: cel mult 1 pentru dezacord 0-1 cu expertul, și O(1) ori de câte ori expertul se poate recupera în câțiva pași. În cel mai rău caz este O(T), și limita liniară nu este mai bună decât cea pătratică.

Cele două încercări care au venit înainte de DAgger

Antrenamentul înainte este răspunsul sincer dar nepractical. Antrenează o politică separată pentru fiecare pas în timp, în ordine, fiecare pe distribuția stării indusă de politicile deja fixate pentru pași anteriori, deci fiecare politică vede exact distribuția pe care o va întâlni. Capcanul este în descriere: T politici, antrenate secvențial, fără oprire timpurie. Pentru o manipulare episode la 30 cadre pe secundă, T este în sute.

SMILe, din aceeași lucrare, și SEARN, din lucrarea lui Daume, Langford și Marcu despre predicție structurată, iau cealaltă rută: o politică staționară, dar stochastică. Fiecare iterație antrenează o componentă și o adaugă unui amestec, mutând masa de probabilitate departe de expert. Rezultatul este un amestec în care unele componente sunt mai rele decât altele - pe un braț fizic, un controler care poate preleva o componentă rea în mișcare. Aceasta este motivația declarată pentru dorința unei politici staționare deterministic în schimb.

DAgger: o idee, o cutie

Agregarea Setului de Date menține politica deterministă și mută reparația în colectarea datelor. Fiecare rundă: derulează politica actuală, înregistrează stările pe care le vizitează, întreabă expertul ce acțiune corectă ar fi fost în fiecare, adaugă acele perechi la setul de date pe care îl deja ai, reentrează pe uniune. Numele este algoritmul - agregezi, nu renunți niciodată.

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

Trei detalii transportă mai multă greutate decât arată. Etichetele sunt pentru stări vizitate de politica mixtă, dar acțiunile provin de la expert - politica furnizează întrebările, expertul răspunsurile. Reentrenarea este pe agregatul întreg, care face fiecare rundă o etapă Follow-The-Leader: la runda n alegi cea mai bună politică cu privire din urmă pe fiecare traiectorie până acum. Acea cadru este ceea pe care se agață dovada. Și algoritmul se termină prin întoarcerea celei mai bune politici în secvență așa cum este aleasă pe un set de validare, deoarece teoremele garantează că unele politică în secvență este bună, nu că cea din urmă este.

Planificarea beta, și de ce nu este un buton de reglare

Politica mixtă este beta_i ori expert plus unu minus beta_i ori cursant. Punctul este practic: primele câteva politici învățate sunt antrenate pe foarte puțin date, fac multe greșeli, și ar petrece altfel derularea în stări care devin irelevante o dată ce politica se îmbunătățește.

Teoria impune exact o condiție: media în curs a betelor trebuie să meargă la zero. Analiza funcționează cu beta_i mărginit de (1 - alpha) la puterea i-1, pentru o constantă alpha independentă de T.

Diferența dintre 2980 și 3030 pe o scală care rulează până la aproximativ 4300 este mică, dar explicația lucrării despre ea este nota practică cea mai utilă din secțiune. Cu orar fără parametri, Mario s-a blocat în același loc devreme și a generat o masă de date aproape-duplicate din acea singură locație; lăsând expertul să conducă o fracție din timp atât l-a deblocat cât și a lărgit varietatea stărilor. Orar este mai puțin despre raportul de amestecare decât despre dacă colectarea ta de date continuă să producă stări noi sau aceeași defecțiune.

Garanția: o reducere la învățarea online de non-regret

Iată mișcarea care face lucrarea ceea ce este. Tratează fiecare rundă DAgger ca un exemplu într-o problemă de învățare online, în care pierderea la runda i este pierderea suplimentară sub distribuția stării politicii folosite la runda i. Cel care învață se angajează la o politică înainte de a vedea acea pierdere, și secvența nu este staționară deoarece depinde de politicile produse până acum.

Un algoritm este non-regret dacă pierderea medie peste N runde se apropie de cea a celei mai bune politici single cu privire din urmă. Follow-The-Leader pe pierderi puternic convexe este un atât de algoritm, cu regret mediu scăzând pe ordinul 1/N - și reentrenarea pe agregatul întreg este exact Follow-The-Leader. Orice alt aprenrant de non-regret ar servi la fel: analiza este o reducere, nu o proprietate a unui singur optimizator.

O lemă leagă diferența dintre politica mixtă care a colectat datele și politica învățată care va fi implementată: Lema 4.1 limitează distanța L1 dintre distribuțiile lor de stare de 2 T beta_i. Aceasta este motivul pentru care betele trebuie să se descompună - în timp ce expertul încă ține autoritate de control apreciabilă, stările pe care le colectezi nu sunt stările pe care le va produce politica ta. Combină lema cu limita de regret și rezultatul principal urmează: după aproximativ T iterații, unele politici în secvență are pierdere suplimentară sub propria distribuție în O(1/T) de epsilon_N. Alimentează-ți în limita liniară și aterizezi la Teorema 3.2.

Partea empirică este modestă după standardele actuale. În Super Tux Kart, linia de bază supravegheată nu și-a îmbunătățit căderi medii pe tur pe măsură ce mai mulți date au sosit, DAgger a ajuns la o politică care niciodată nu a căzut de pe pistă după cincisprezece iterații, și SMILe după douăzeci încă a căzut aproximativ de două ori pe tur. Pe reper de scris cu mână, acuratețea caracterului a rulat 82 la sută fără structură, 83.6 la sută supravegheată, 85.5 la sută cu DAgger. Nici una dintre acestea nu este un rezultat de manipulare.

Ce nu promite dovada

Declarațiile teoremei sunt condiționale, și condițiile sunt purtătoare de sarcină.

Un rezultat suplimentar este adesea citat ca o refutație și nu este una. Rajaraman, Yang, Jiao și Ramachandran studiază limitele minimax ale învățării prin imitare în MDP-uri episodice cu un spațiu de stare finit S și orizont H, și dovedesc o limită de suboptimalitate pe ordinul |S| H pătrat peste N care ține chiar atunci când învățatorul poate activ interoga expertul la stări vizitate. Aceasta este o rată de caz în cel mai rău peste o clasă de MDP-uri la un buget de episod fix, și ceea ce exclude este ideea că interacțiunea îmbunătățește rata minimax; teorema DAgger este o afirmație diferită, limitând politica implementată relativă la ceea ce propria sa clasă de politică poate obține.

Swamy, Choudhury, Bagnell și Wu mai târziu au clasificat acești algoritmi după care momente din comportamentul expertului se potrivesc, și au introdus o noțiune de recuperabilitate moment care delimitează cât de bine fiecare familie mitiga eroarea compusă. Sondajele de Osa și de Celemin acoperă peisajul algoritmic și interfețele de retroacțiune uman.

Factura: etichetarea stărilor pe care expertul nu le-a produs niciodată

Tot ceea ce de mai sus presupune un expert care poate fi interogat oriunde. În simulare cu un planificator care este aproape liber - experimentele Mario au folosit un planificator aproape-optim cu acces complet la starea jocului. Cu un om pe un robot este costul dominant, și unul ciudat: omul trebuie să producă o acțiune corectă într-o configurație căreia propria sa competență nu ar fi creat-o niciodată.

Kelly, Sidrane, Driggs-Campbell și Kochenderfer enunță obiecția direct în lucrarea HG-DAgger. DAgger vanilă necesită expertului să furnizeze etichetele de acțiune în timp ce nu este pe deplin în control al sistemului. Aceasta reduce siguranța, și cu experți umani este probabil să degradeze calitatea etichetelor colectate, pe care o atribuie perceput lag-ului actuatorului. Eticheta pe care o recuperezi nu este eticheta pe care a presupus-o algoritmul.

Laskey și colegii ataca problema din cealaltă parte cu DART, și cadrul lor este direct: tehnicile on-policy sunt plictisitoare pentru supraveghetorii umani, adaugă sarcină de calcul, și pot vizita stări periculoase în timpul antrenării. Alternativa lor injectează zgomot calibrat în propriile demonstrații ale supraveghetorului, deci recuperarea se demonstrează fără ca robotul să ruleze niciodată o politică neîncredere. Pe MuJoCo Humanoid raportează DART scăzând recompensa cumulativă a supraveghetorului cu 5 la sută în timpul antrenării, în timp ce DAgger execută politici cu 80 la sută mai puțin recompensă cumulativă decât supraveghetorul; pe apriendere în aglomerație cu un Toyota HSR, o creștere medie de 62 la sută față de behavior cloning.

SafeDAgger al lui Zhang și Cho tratează cererile la politica de referință ca resursa rară: o politică de siguranță separată prezice, fără a interoga, dacă politica primară este pe cale să se abate de la referință dincolo de un prag, și doar acele stări sunt predate. Toate trei reacționează la același fapt - analiza DAgger nu percepe taxă pentru etichetele experți, și realitatea percepe o mare.

Ce înseamnă aceasta pentru un SO-100 pe masa ta

Traduce orizontul în propriile tale unități. O episod de douăzeci de secunde la 30 cadre pe secundă este 600 pași de decizie, și T în fiecare limită de mai sus este acel număr. La T = 600, diferența dintre un termen scalare cu T și unu scalare cu T pătrat este diferența dintre o politică care se recuperează dintr-o apropiere rea și una care nu face.

Aceasta este în parte motivul pentru care îngrămădirea acțiunilor ajută: atunci când o politică emite o scurtă secvență de acțiuni pe pas de inferență, numărul de puncte de decizie scade, și tot și numărul de șanse pentru compunere. Zhao, Kumar, Levine și Finn denumesc eroarea compusă ca motivație pentru Action Chunking with Transformers, și raportează succes 80 la sută pe șase sarcini grele din lumea reală, pe hardware bimanual low-cost, din zece minute valorează demonstrații. Îngrămădirea nu elimină covariate shift - stările sunt încă a propriului politicii - dar scurtează orizontul efectiv. Vezi action chunking și ghidul SO-100 imitation learning.

Cea de-a doua traducere este metrica de progres. Nu puteți măsura epsilon sub propria distribuție a politicii direct - asta necesită acțiuni expert de adevăr fundamental pentru fiecare stare vizitată, lucrul pe care încerci să-l eviti producând. Ce ți dă o buclă cu gate uman în schimb este rata de intervenție: fracția de cadre într-o rulare în care omul a preluat. Este un proxy, și se mișcă din motive neînrudite cu politica - un operator răbdător intervine mai puțin. Folosit consistent, este singurul număr care spune dacă o rundă a meritat după-amiaza.

O a treia traducere este o avertizare de calitate a datelor pe care analiza nu o acoperă. Mandlekar și colegii au studiat șase algoritmi de învățare offline pe cinci sarcini de manipulare multi-etapă simulate și trei din lumea reală, și raportează o sensibilitate la alegerile de design algoritmice, o dependență de calitatea demonstrațiilor, și variabilitate cauzată de criteriul de oprire. Belkhale, Cui și Sadigh susțin că calitatea setului de date trebuie formalizată prin divergența de acțiune și diversitate de tranziție, și notează că diversitatea de stare nu este întotdeauna benefică. O rundă DAgger adaugă stări pe care nu a ales nimeni deliberat: unele sunt datele de recuperare pe care le ai nevoie, unele sunt robotul agitând în timp ce vânezi controlul de preluare.

Mecanic o rundă este șase pași: rulează inferența cu înregistrarea pe, preia atunci când politica se comportă greșit, revizuiește rularea și depunere fiecare episod, sincronizare corecțiile, compune un set de date amestecat din originale plus corecții cu selecție de episod făcută explicit per sursă, și continuă antrenare din precedentul checkpoint mai degrabă decât modelul de bază. Pe ay-robots acei pași există ca butoane, care elimină conducerile dar nu și judecata. Două atenționări: continuarea dintr-un checkpoint inițializează greutatea și nu este o reluare de optimizer, și mișcarea de aliniere a brațului conducător este încă ușor testată pe hardware. Vezi training și datasets.

Arborele familiei, într-un tabel

Întrebări frecvente

Unde să mergi de aici

Dacă nu ai antrenat încă o politică, această teorie este timpurie: înregistrează mai întâi un set de date, începând de la antrenarea primei politici și clientul de birou. Dacă cântărești o sută demonstrații curate în plus față de corecții de pornire: demonstrațiile curate nu fixează o problemă de distribuție. Pentru mecanică, continuă cu varianta cu gate uman și apoi parcurgerea SO-100.