DAgger forklart: Hvorfor atferdskloning driver og hva datasettaggregering faktisk beviser

Det er en spesifikk feil som alle som trener en manipulasjonstrategi møter før eller siden. Strategien når mot kuben, kommer innen to centimeter, nøler, driver sidelengs, gjør deretter noe irrelevant for oppgaven. Valideringsfeil var fin. Åpen omgang gjentakelse mot holdt-ut episoder var fin. Og likevel ender armen opp i en stilling som ikke vises noe sted i treningsdataene, og derfra har den ingen fornuftig å si.

Denne feilen har et navn og en etablert teori bak seg. Dette er den første av fire artikler om DAgger, og den dekker argumentet selv: hvorfor det å tilpasse en strategi på demonstrantens egne baner produserer en feil som kan vokse med kvadratet av episodelengden, hva datasettaggregering endrer, og hva beviset uten anger ikke lover. Løkken på ekte maskinvare dekkes i kjøring av en DAgger-løkke på en SO-100, varianten med menneske-gate i HG-DAgger og menneske-gatede intervensjoner, og målespørsmålet i måling av en DAgger-løkke.

Antagelsen atferdskloning gjør stille

Et demonstrasjonsdatasett er en haug med observasjons-handlings par. Atferdskloning tilpasser en funksjon til den haugen med vanlig overvåket læring og stopper der. Det er den eldste ideen i feltet. Pomerleau's ALVINN, i 1988, var et tre-lags tilbakepropagasjonsnettverk som tok bilder fra et kamera og en laserskannerepocenter og produserte retningen kjøretøyet skulle reise; det ble trent på simulerte veibilder og fulgte virkelige veier under noen feltforhold. Oppskriften har ikke endret seg mye; nettverkene har.

Det som blir hoppet over er en sjekk på hvor disse parene kom fra. Hver eneste av dem ligger på en bane demonstranten produserte. Strategien du distribuerer produserer sin egen. Øyeblikket den avviker, blir den spurt om tilstander som ikke var i treningsfordelingen, og svaret beveger den videre ut. Ross, Gordon og Bagnell åpner DAgger-avisen med akkurat dette: sekvensiell prediksjon bryter i.i.d.-antagelsen under statistisk læring, fordi lærerens egne spådommer bestemmer inngangene den ser videre.

Den klareste illustrasjonen i det papiret er ikke en robot i det hele tatt. Kloning av en nær-optimal planlegger for Super Mario Bros. produserte en strategi som gjentatte ganger satt seg fast mot en hindring i stedet for å hoppe over den. Grunnen er hele argumentet i en setning: eksperten hoppet alltid fra en behagelig avstand, så datasettet inneholdt ingen tilstand der Mario var trykket opp mot en hindring, og derfor ingen etikett for hva du gjør når han var.

Bytt Mario for en SO-100 arm og strukturen er identisk. Dine demonstrasjoner viser en ren tilnærming og et rent grep, ikke gripen lukkes to centimeter kort - så strategien har ingen idé hva du gjør derfra, og uansett hva den gjetter tar den videre ut. Kovariatforskyvning er en egenskap ved datainsamlingsprosedyren, ikke på nettverksarkitekturen.

Hvor det kvadratiske leddet kommer fra

2010 AISTATS-papiret av Ross og Bagnell, Effektive reduksjoner for imitasjonslæring, gjør sammensettingen presis. La T være oppgavehorisonten, la oppgavekostnad være begrenset i enhetsintervallet, og la epsilon være surrogatstap målt under ekspertens tilstandsfordeling - tallet valideringsettet ditt rapporterer. Deretter er den ekstra kostnaden ved kjøring av den strategien for T trinn, relativt til eksperten, begrenset av T i kvadrat ganger epsilon. Ross, Gordon og Bagnell omstater dette som teorem 2.1 i DAgger-papiret og legger til setningen som betyr: grensen er stram. Problemer eksisterer der en strategi med epsilon tap på ekspertens fordeling virkelig pådrår ekstra kostnad som vokser kvadratisk i T.

Stram betyr ikke typisk. Det kvadratiske leddet er et verste tilfelle over en klasse av problemer, ikke en forutsigelse om oppgaven din velg-og-plassering. Det som etableres er at mer ekspertdemonstrasjon ikke kan fjerne problemet: det bare skjerper estimatet av epsilon på en fordeling strategien ikke vil bli testet på.

Fluktveien er i det samme papiret, omstatet som teorem 2.2. Hvis en strategi oppnår tap epsilon under sin egen tilstandsfordeling, og en enkelt gal handling koster på det meste u i kostnad-to-go under eksperten, er den ekstra kostnaden begrenset av u ganger T ganger epsilon - lineær i horisonten. Konstanten u er den interessante størrelsen: på det meste 1 for 0-1 uenighet med eksperten, og O(1) når eksperten kan gjenopprette innen noen få trinn. I verste tilfelle er den O(T), og den lineære grensen er da ikke bedre enn den kvadratiske.

De to forsøkene som kom før DAgger

Forover trening er det ærlige men upraktiske svaret. Tren en separat strategi for hver tidstrinn, i rekkefølge, hver på tilstandsfordelingen indusert av strategiene allerede fikset for tidligere trinn, så hver strategi ser nøyaktig fordelingen den vil møte. Fangsten er i beskrivelsen: T strategier, trent sekvensielt, ingen tidlig stans. For en manipulasjons episode på 30 bilder per sekund, T er i hundretallene.

SMILe, fra det samme papiret, og SEARN, fra Daume, Langford og Marcu's arbeid om strukturert prediksjon, tar den andre ruten: en stasjonær strategi, men stokastisk. Hver iterasjon trener en komponent og legger den til en blanding, flytter sannsynlighetsmasse bort fra eksperten. Resultatet er en blanding der noen komponenter er verre enn andre - på en fysisk arm, en kontroller som kan prøve en dårlig komponent mid-motion. Det er den oppgitte motivasjonen for å ønske en stasjonær deterministisk strategi i stedet.

DAgger: en idé, en boks

Datasettaggregering holder den deterministiske strategien og flytter fiksen inn i datainsamling. Hver runde: kjør ut den nåværende strategien, registrer tilstandene den besøker, spør eksperten hva den riktige handlingen ville ha vært i hver, legg disse parene til datasettet du allerede har, omtren på foreningen. Navnet er algoritmen - du aggregerer, du kaster aldri bort.

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

Tre detaljer bærer mer vekt enn de ser ut til å gjøre. Etikettene er for tilstander besøkt av den blandede strategien, men handlingene kommer fra eksperten - strategien gir spørsmålene, eksperten svarene. Omtreninger er på hele aggregatet, som gjør hver runde til et Følg-Lederen-trinn: ved runde n velger du den beste strategien i ettertid over hver bane så langt. Det er den rammen som beviset henger på. Og algoritmen ender ved å returnere den beste strategien i sekvensen som valgt på et valideringssett, fordi teoremene garanterer at noen strategi i sekvensen er god, ikke at den siste er.

Beta-planen, og hvorfor den ikke er en innstillings knapp

Den blandede strategien er beta_i ganger eksperten pluss en minus beta_i ganger læreren. Poengten er praktisk: de første lærte strategiene blir trent på veldig lite data, gjør mange feil, og ville ellers brukt omgangen i tilstander som blir irrelevante når strategien forbedres.

Teorien pålegger nøyaktig en betingelse: gjennomsnittets gjennomsnitt av betaene må gå til null. Analysen fungerer med beta_i begrenset av (1 - alfa) til kraften i-1, for en konstant alfa uavhengig av T.

Gapet mellom 2980 og 3030 på en skala som løper til omtrent 4300 er liten, men papperets forklaring på det er det mest nyttige praktiske notatet i delen. Med den parameter-fri planen, Mario satt seg fast på samme sted tidlig og genererte en masse nær-duplikat data fra det ene stedet; la eksperten kjøre en brøkdel av tiden både løste ham og utvidet mangfoldet av tilstander. Planen handler mindre om blandingsforholdet enn om hvorvidt datainsamlingen din fortsetter å produsere nye tilstander eller samme feil.

Garantien: en reduksjon til kravfri online-læring

Her er trekket som gjør papiret det er. Behandle hver DAgger-runde som ett eksempel i et online-læringsproblem, der tapet ved runde i er surrogatstap under tilstandsfordelingen av strategien som brukes ved runde i. Læreren forplikter seg til en strategi før han ser det tapet, og sekvensen er ikke-stasjonær fordi den avhenger av strategiene produsert så langt.

En algoritme er kravfri hvis dens gjennomsnittlige tap over N runder nærmer seg det for den beste enkeltstrategien i ettertid. Følg-Lederen på sterkt konvekse tap er en slik algoritme, med gjennomsnittlig anger som krymper på størrelse av 1/N - og omtrening på hele aggregatet er nøyaktig Følg-Lederen. Enhver annen kravfri lærer ville fungert like godt: analysen er en reduksjon, ikke en egenskap for en optimiser.

Et lemma brokker gapet mellom den blandede strategien som samlet dataene og den lærte strategien som distribueres: lemma 4.1 begrenser L1-avstanden mellom deres tilstandsfordelinger ved 2 T beta_i. Dette er hvorfor betaene må forfalle - mens eksperten fortsatt har betydelig kontrollmyndighet, er tilstandene du samler ikke tilstandene strategien din produserer. Kombinere lemmaet med angerarmen og hovedresultatet følger: etter omtrent T iterasjoner, noen strategi i sekvensen har surrogatstap under sin egen fordeling innen O(1/T) av epsilon_N. Mat det inn i den lineære grensen og du lander på teorem 3.2.

Den empiriske siden er beskjeden etter dagens standarder. I Super Tux Kart gjorde den tilsyn basert på grunnlaget ikke forbedring av gjennomsnittlige fall per omgang som mer data ankom, DAgger nådde en strategi som aldri falt av sporet etter femten iterasjoner, og SMILe etter tjue fortsatt falt omtrent to ganger per omgang. På håndskrifttesten, karakter nøyaktighet løp 82 prosent uten struktur, 83,6 prosent tilsyn, 85,5 prosent med DAgger. Ingen av disse er et manipulasjonsresultat.

Hva beviset ikke lover

Teoremsetningene er betinget, og betingelsene er belastningsbærende.

Et resultatet til blir ofte sitert som en tilbakevisning og er ikke en. Rajaraman, Yang, Jiao og Ramachandran studerer minimax-grensene for imitasjonslæring i episodiske MDPer med et begrenset tilstandsrom S og horisont H, og beviser en suboptimalitet nedre grense på størrelse av |S| H i kvadrat over N som gjelder selv når læreren kan aktivt spørre eksperten ved besøkte tilstander. Det er en verste tilfelle pris over en klasse av MDPer på en fast episodebudsjett, og hva det utelukker er ideen om at interaksjon forbedrer minimax-kursen; DAggers teorem er et annet utsagn, som begrenser den distribuerte strategien relativt til hva dens egen strategiklasse kan oppnå.

Swamy, Choudhury, Bagnell og Wu klassifiserte senere disse algoritmene etter hvilke øyeblikk av ekspertens oppførsel de samsvarer, og introduserte en oppfatning av øyeblikk gjenopprettbarhet som avgrenser hvor godt hver familie demper sammensatt feil. Oversiktene av Osa og av Celemin dekker det algoritmiske landskapet og menneske-tilbakemeldingsgrensesnittene.

Regningen: koding av tilstander eksperten aldri produserte

Alt ovenfor antar en ekspert som kan spørres hvor som helst. I simulering med en planlegger som er nesten gratis - Mario-eksperimentene brukte en nær-optimal planlegger med full tilgang til spilletilstand. Med en menneskelig på en robot er det den dominerende kostnaden, og en merkelig: mennesket må produsere en riktig handling i en konfigurasjon deres egen kompetanse aldri ville ha opprettet.

Kelly, Sidrane, Driggs-Campbell og Kochenderfer oppgir innvendingen direkte i HG-DAgger-avisen. Vanilje DAgger krever at eksperten leverer handlingsetiketter mens de ikke er fullt i kontroll av systemet. Dette reduserer sikkerheten, og med menneskeeksperter er det sannsynlig at det vil forverres kvaliteten på de innsamlede etikettene, som de legger ned til opplevd aktuatorlag. Etiketten du får tilbake er ikke etiketten algoritmen antok.

Laskey og kolleger angriper problemet fra den andre siden med DART, og rammen deres er stump: on-policy teknikker er kjedelige for menneskelige veiledere, legger til beregningsmessig byrde, og kan besøke farlige tilstander under trening. Deres alternativ injiserer kalibrert støy inn i veilederens egne demonstrasjoner, slik at gjenoppretting får demonstrert uten at roboten kjører en upålitelig strategi. På MuJoCo Humanoid rapporterer de DART reduserer vegledernes kumulative belønning med 5 prosent under trening, mens DAgger utfører strategier med 80 prosent mindre kumulativ belønning enn veilederen; på grasping i rot med en Toyota HSR, en gjennomsnittlig 62 prosent økning over atferdskloning.

Zhang og Cho's SafeDAgger behandler spørsmål til referansestrategien som den knappe ressursen: en separat sikkerhetsstrategi forutsier, uten å spørre, om den primære strategien er i ferd med å avvike fra referansen utover en terskel, og bare disse tilstandene blir overlevert. Alle tre reagerer på det samme faktum - DAgger-analysen lader ingenting for ekspertetiketter, og virkeligheten lader mye.

Hva dette betyr for en SO-100 på ditt skrivebord

Oversett horisonten til dine egne enheter. En tjue-sekunders episode på 30 bilder per sekund er 600 beslutningstrinn, og T i hver grense ovenfor er det tallet. Ved T = 600, er forskjellen mellom et ledd som skaleres med T og en som skaleres med T i kvadrat forskjellen mellom en strategi som gjenoppretter fra en dårlig tilnærming og en som ikke gjør det.

Dette er del av hvorfor handlingsklumping hjelper: når en strategi sender ut en kort sekvens av handlinger per slutningstrinn, tallet av beslutningspunkter faller, og så gjør tallet over sjansen til sammensetning. Zhao, Kumar, Levine og Finn navngir sammensatt feil som motivasjon for handling Chunking med Transformers, og rapporterer 80 til 90 prosent suksess på seks vanskelige virkelige verden oppgaver, på lavkost bimanual maskinvare, fra ti minutter verdt av demonstrasjoner. Klumping fjerner ikke kovariatforskyvning - tilstandene er fortsatt strategiens egen - men det forkorter den effektive horisonten. Se handlingsklumping og SO-100 imitasjonslearning guide.

Den andre oversettelsen er progresjonsmetrikken. Du kan ikke måle epsilon under strategiens egen fordeling direkte - det trenger sannhetsvitne eksperthandlinger for hver besøkt tilstand, tingen du prøver å unngå produksjon. Hva en menneske-gatet løkke gir deg i stedet er intervensjonsfrekvens: brøkdelen av bilder i en løp der mennesket hadde tatt over. Det er en proxy, og den beveger seg av grunner ikke relatert til strategien - en tålmodig operatør intervenerer mindre. Brukt konsekvent, er det det eneste tallet som sier om en runde var verdt ettermiddagen.

En tredje oversettelse er en datakvalitets advarsel analysen ikke dekker. Mandlekar og kolleger studerte seks offline læring algoritmer på fem simulert og tre virkelige verden multi-stadium manipulasjonsoppgaver, og rapporterer en følsomhet for algoritmisk designvalg, en avhengighet på kvaliteten av demonstrasjonene, og variabilitet forårsaket av stoppkritiumet. Belkhale, Cui og Sadigh argumenterer at datasett kvalitet bør formaliseres gjennom handlingsforskjell og overgangsmangfold, og merker at tilstandsmangfold ikke alltid er gunstig. En DAgger-runde legger til tilstander ingen valgte bevisst: noen er gjenopprettingsdataene du trenger, noen er roboten som flagrer mens du bumber for takeover-kontrollen.

Mekanisk en runde er seks trinn: kjør slutning med opptak på, ta over når strategien misbehaver, gjennomgå løpet og arkiver hver episode, synk korreksjoner, komponere et blandet datasett fra originaler pluss korreksjoner med episode valg gjort eksplisitt per kilde, og fortsett trening fra den tidligere kontrollpunkt i stedet for basemodellen. På ay-robots disse trinnene eksisterer som knapper, som fjerner installasjonen men ikke dommen. To forbeholdene: fortsetter fra et kontrollpunkt initialiserer vekter og er ikke en optimiser-resume, og lederer-arm justeringsbevegelsen er fortsatt lett testet på maskinvare. Se trening og datasetter.

Familiefamilien, i en tabell

Ofte stilte spørsmål

Hvor skal jeg gå herfra

Hvis du ikke har trent en strategi ennå, er denne teorien for tidlig: opptak et datasett først, starter fra trening av din første strategi og skrivebord klient. Hvis du veier en annen hundre rein demonstrasjoner mot starter korreksjoner: rein demonstrasjoner fikser ikke et distribusjon problem. For mekanikken, fortsett med den menneske-gatede varianten og deretter SO-100 gjennomgang.