DAgger selitetty: miksi Behavior Cloning ajautuu ja mitä Dataset Aggregation todella todistaa

On olemassa tietty vika, johon jokainen, joka kouluttaa manipulaatiopolicy:a, ennemmin tai myöhemmin törmää. Policy ulottaa käden kohti kuutiota, pääsee kahden sentin etäisyydelle, epäröi, ajautuu sivusuunnassa, sitten tekee jotain, jolla ei ole tekemistä tehtävän kanssa. Validointihäviö oli ok. Avoimen silmukan toisto täytäntöön otettujen episodien vastaan oli ok. Silti käsivarsi päätyy asentoon, joka ei näy lainkaan harjoitustiedoissa, ja sieltä sillä ei ole mitään järkevää sanottavaa.

Tämä vika on nimetty, ja sen takana on vakiintunut teoria. Tämä on ensimmäinen neljästä artikkelista DAgger-algoritmin aiheesta, ja se käsittelee itse argumentin: miksi policy, joka sovitetaan demonstraattorin omille liikeradoille, tuottaa virheen, joka voi kasvaa episodin pituuden neliön mukaan, mitä dataset aggregation muuttaa, ja mitä no-regret-todistus ei lupaa. Todellisen laitteiston silmukka on käsitelty artikkelissa DAgger-silmukan ajaminen SO-100:lla, ihmisten valvoma variantti artikkelissa HG-DAgger ja ihmisten valvomat interventiot, ja mittauskysymys artikkelissa DAgger-silmukan mittaaminen.

Oletus, jonka behavior cloning tekee hiljaa

Demonstraatiotietojoukko on pino havainto-toimintapareja. Behavior cloning sovittaa funktion tuohon pinoon tavallisella supervised learningilla ja lopettaa siinä. Se on vanhin idea alalla. Pomerleau:n ALVINN vuonna 1988 oli kolmikerroksinen backpropagation-verkko, joka otti kuvia kamerasta ja lasersäteilytutkasta ja tuotti suunnan, johon ajoneuvo kuuluisi matkustaa; se koulutettiin simuloiduilla tiekulvan kuvilla ja seurasi todellisia teitä joissakin maastoolosuhteissa. Resepti ei ole muuttunut paljon; verkot ovat.

Mitä jätetään huomiotta, on tarkistus siitä, mistä nämä parit tulevat. Jokainen niistä on liikeradalla, jonka demonstraattori tuotti. Policy, jonka otat käyttöön, tuottaa omansa. Heti kun se poikkeaa, sitä pyydetään tilasta, joka ei ole harjoitusjakauman sisällä, ja sen vastaus vie sen kauemmas. Ross, Gordon ja Bagnell avaavat DAgger-paperin juuri tällä: sekvenssiennustus rikkoo i.i.d.-oletuksen tilastollisen oppimisen takana, koska oppijan omat ennusteet määrittävät syötteet, joita se näkee seuraavaksi.

Selkein havainto tuossa paperissa ei ole robottiikka lainkaan. Lähes optimaalisen Super Mario Bros. -suunnittelejan kloonaaminen tuotti policy:n, joka toistuvasti jäi jumiintuneeksi esteeseen sen sijaan, että hyppäisi sen yli. Syy on koko argumentti yhdessä lauseessa: asiantuntija aina hyppäsi miellyttävältä etäisyydeltä, joten tietojoukko ei sisältänyt tilaa, jossa Mario olisi ylempiä estettä vasten, eikä siksi merkintää sille, mitä tehdä sitten kun hän oli.

Korvaa Mario SO-100 kädellä ja rakenne on sama. Esitykset näyttävät puhtaan lähestymisen ja puhtaan hahmotuksen, eivät kaksissa senteissä sulkeutuvaa pihtiä - joten policy:lla ei ole mitään ideaa sieltä, ja mikä tahansa sen arvaus vie sen kauemmas. Covariate shift on ominaisuus data collection prosessista, ei verkkoarkkitehtuurista.

Mistä neliöllinen termi tulee

Ross ja Bagnell vuoden 2010 AISTATS-paperi, Efficient Reductions for Imitation Learning, tekee kumulatiivisen virheen tarkaksi. Olkoon T tehtävän horisontti, tehtävän kustannus rajoitettu yksikköväliksi, ja epsilon korvaava häviö mitattu asiantuntijan tilajakauman alla - numero, jonka validointisettisi raportoi. Sitten ylimääräinen kustannus kyseisen policy:n ajamisesta T vaiheelle, suhteessa asiantuntijaan, on rajoitettu T neliö kertaa epsilon. Ross, Gordon ja Bagnell esittävät uudelleen tämän Lauseena 2.1 DAgger-paperissa ja lisäävät lauseen, jolla on merkitystä: raja on tiukka. Ongelmat olemassa, joissa policy epsilon-häviöllä asiantuntijan jakauman päällä todella aiheutuu ylimääräisen kustannuksen kasvavan neliöllisesti T:ssä.

Tiukka ei tarkoita tyypillistä. Neliöllinen termi on pahin tapaus ongelmaluokan yli, ei ennustus pick-and-place-tehtävästä. Mitä se vakiinnuttaa, on että enemmän asiantuntijan esittelystä ei voi poistaa ongelmaa: se vain terävöittää epsilon:n estimaattia jakauman alla, jota policy:a ei testata.

Pakoväylä on samassa paperissa, uusintana Lauseena 2.2. Jos policy saavuttaa häviön epsilon sen omalla omalla tilajakauman alla, ja yksittäinen väärä toiminta maksaa enintään u cost-to-go:ssa asiantuntijan alle, ylimääräinen kustannus on rajoitettu u kertaa T kertaa epsilon - lineaarinen horisontissa. Vakio u on mielenkiintoinen määrä: enintään 1 0-1 epäsuhdan kanssa asiantuntijan kanssa, ja O(1) aina kun asiantuntija voi toipua muutamassa askeleessa. Pahimmassa tapauksessa se on O(T), ja lineaarinen raja ei ole parempi kuin neliöllinen.

Kaksi yritystä, jotka edeltävät DAgger:ia

Eteenpäin koulutus on rehellinen mutta epäkäytännöllinen vastaus. Kouluta erillinen policy jokaiselle aika-askelelle, järjestyksessä, jokainen aiemmin kiinnitetyistä policy:ista indusoituneesta tilajakauman alla, joten jokainen policy näkee tarkalleen jakauman, jonka se tulee kohtaamaan. Anso kuvauksessa: T policy:a, koulutettu peräkkäin, ei varhaista pysäyttämistä. Manipulaatioepisodin tapauksessa 30 kuvaa sekunnissa, T on satojen luokkaa.

SMILe, samasta paperista, ja SEARN, Daume:n, Langford:in ja Marcu:n työstä strukturoidusta ennustamisesta, ottavat toisen reitin: yksi stationaarinen policy, mutta stokastinen. Jokainen iteraatio kouluttaa komponentin ja lisää sen seokseen, siirtäen todennäköisyys massan pois asiantuntijalta. Tulos on seos, jossa jotkut komponentit ovat huonompia kuin toiset - fyysisellä käsivarrella ohjaaja, joka voi näytteistää huonon komponentin liikkeen kesken. Se on mainittu motivaatio vaatimukselle stationaarinen deterministinen policy sen sijaan.

DAgger: yksi idea, yksi ruutu

Dataset Aggregation pitää determinististisen policy:n ja siirtää korjauksen data collectioniin. Jokainen kierros: aja nykyinen policy, kirjaa tilat, joita se käy, kysy asiantuntijalta, mikä oikea toiminta olisi ollut kussakin, lisää nämä parit jo olemassa olevaan datasettiin, kouluta uudelleen liittoon. Nimi on algoritmi - aggregoit, et koskaan hylkää.

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

Kolme yksityiskohtaa kantavat enemmän painoa kuin näyttävät. Merkit ovat sekottuvan policy:n käytyjen tilojen, mutta toiminnot tulevat asiantuntijalta - policy tarjoaa kysymykset, asiantuntija vastaukset. Uudelleenkoulutus on koko aggregaatin yhteydessä, mikä tekee jokaisen kierroksen Follow-The-Leader askeleeksi: kierroksella n valitset parhaan policy:n jälkikäteen kaikista tähän mennessä ajetuista liikeradoista. Se kehys on mitä todistus roikkuu. Ja algoritmi päättyy valitsemalla paras policy sekvenssissä validointisarjassa, koska teoreemat takaavat, että jokin policy sekvenssissä on hyvä, ei että viimeinen on.

Beta schedule, ja miksi se ei ole virityspainike

Sekoitettu policy on beta_i kertaa asiantuntija plus yksi miinus beta_i kertaa learner. Pointti on käytännöllinen: ensimmäiset opitut policy:t koulutetaan hyvin pienellä datalla, tekevät paljon virheitä, ja muutoin kuluttaisivat kierroksen tiloissa, joista tulee merkityksettömiä kun policy paranee.

Teoria asettaa tarkalleen yhden ehdon: bettojen juokseva keskiarvo on ajettava nollaan. Analyysi toimii beta_i:n kanssa sidottu (1 - alpha) potenssiin i-1, vakio alpha riippumaton T:stä.

Ero 2980:n ja 3030:n välillä, joka asteikolla kulkee noin 4300:aan, on pieni, mutta paperin selitys siitä on hyödyllisin käytännöllinen huomio osiossa. Parametrittomalla aikataululla Mario juuttui samaan kohtaan alussa ja tuotti massan lähes identtisiä tietoja kyseisestä paikasta; antamalla asiantuntijalle ajaa osuuden aikaa avasi hänet ja laajensi tilojen valikoimaa. Aikataulu on vähemmän sekoitussuhteesta ja enemmän siitä, jatkaako data collection tuottamaan uusia tiloja vai samaa vika.

Takuu: reduksio no-regret online learningiin

Tässä on siirtymä, joka tekee paperista mitä se on. Kohtele jokaista DAgger kierrosta yhtenä esimerkkinä online-oppimisongelmassa, missä häviö kierroksella i on korvaava häviö käytetyn policy:n tilajakauman alla. Oppilas sitoutuu policy:hin ennen häviön näkemistä, ja sekvenssi on ei-stationaarinen koska se riippuu tuotettuista policy:sta.

Algoritmi on no-regret jos sen keskimääräinen häviö N kierroksella lähestyy parhaan yksittäisen policy:n jälkikäteen. Follow-The-Leader vahvasti konveksilla häviöillä on tällainen algoritmi, keskimääräinen katuma kutistuu 1/N:n luokkaa - ja uudelleenkoulutus koko aggregaatin yhteydessä on tarkalleen Follow-The-Leader. Mikä tahansa muu no-regret learner palvelisi: analyysi on reduksio, ei yhden optimoijan ominaisuus.

Yksi lemma silloittaa aukon sekoitetun policy:n välillä, joka keräsi tiedot, ja opitun policy:n välillä, joka otetaan käyttöön: Lemma 4.1 rajoittaa L1-etäisyyden niiden tilajakaumien välillä 2 T beta_i:llä. Tämä on miksi betat täytyy hajota - kun asiantuntija pitää silti huomattavaa ohjauksen valtaa, tilat, joita keräät, eivät ole tiloja, joita policy:si tuottaa. Yhdistä lemma katuma-rajaan ja pääulos seuraa: noin T iteraation jälkeen jokin policy sekvenssissä on korvaava häviö sen omalla jakauman alla O(1/T):n sisällä epsilon_N:stä. Syötä lineaarinen raja ja laskeudu Lauseeseen 3.2.

Empiirinen puoli on vaatimaton nykyisten standardien mukaan. Super Tux Kart:issa supervised baseline ei parantanut keskimääräisiä putoamisia per kierros kun lisää tietoa saapui, DAgger saavutti policy:n, joka ei koskaan pudonnut radalta viidentoista iteraation jälkeen, ja SMILe kahdenkymmenen jälkeen putosi edelleen noin kahdesti per kierros. Käsialavertailussa merkkien tarkkuus oli 82 prosenttia ilman rakennetta, 83,6 prosenttia supervised, 85,5 prosenttia DAgger:n kanssa. Mikään näistä ei ole manipulaatiotulos.

Mitä todistus ei lupaa

Lauselausunnot ovat ehdollisia, ja ehdot ovat kantavia.

Yksi muista tulosta usein lainataan kieltäytymisenä eikä ole. Rajaraman, Yang, Jiao ja Ramachandran tutkivat imitation learningin minimax-rajoja episodisissa MDP:issä äärellisellä tilajoukolla S ja horisontilla H, ja todistavat suboptimaalisuuden alarajan |S| H neliöllä yli N:llä, joka pätee jopa kun oppilas voi aktiivisesti kyselyä asiantuntijaa käydetyissä tiloissa. Se on pahin tapaus MDP-luokan yli kiinteässä episodibudjetissa, ja mitä se sulkee pois on idea, että vuorovaikutus parantaa minimax-nopeutta; DAgger:n lause on eri väite, rajoittaen otetun käyttöön policy:n suhteessa siihen, mitä sen oma policy-luokka voi saavuttaa.

Swamy, Choudhury, Bagnell ja Wu myöhemmin luokittelivat nämä algoritmit asiantuntijan käyttäytymisen momentin perusteella, jota ne vastaavat, ja johdattelivat hetken toipumiskelpoisuuden käsitteen, joka erottaa kuinka hyvin jokainen perhe lieventää kumulatiivista virhettä. Osa ja Celemin tekemät tutkimukset kattavat algoritmisen maiseman ja ihmisten palaute-käyttöliittymät.

Lasku: tilojen merkintä, joita asiantuntija ei koskaan tuottanut

Kaikki edellä oleva olettaa asiantuntijan, jota voi kyselyä missä tahansa. Simulaatiossa lähes ilmaisella suunnittelijalla - Mario-kokeet käyttivät lähes optimaalista suunnittelijaa, jolla on täysi pääsy pelitiloihin. Ihmisen kanssa robotissa se on hallitseva kustannus, ja omituinen: ihminen on tuottaa oikea toiminta konfiguraatiossa, jonka heidän oma pätevyys ei koskaan olisi luonut.

Kelly, Sidrane, Driggs-Campbell ja Kochenderfer esittävät väitteen suoraan HG-DAgger paperissa. Vanilla DAgger vaatii asiantuntijaa toimittamaan toimintomerkkejä, vaikka he eivät ole täysin hallinnassa järjestelmää. Tämä vähentää turvallisuutta, ja ihmisen asiantuntijoiden kanssa se todennäköisesti heikentää kerättyjen merkkien laatua, jonka he johtavat koettuun toimilaitteiden viiveeseen. Merkki, jonka saat takaisin, ei ole merkki, jonka algoritmi oletti.

Laskey ja kollegat hyökkäävät ongelmaan toiselta puolelta DART:in kanssa, ja heidän kehystyään on suoraviivainen: on-policy tekniikat ovat rasittavia ihmisen valvojille, lisäävät laskennallista kuormaa, ja voivat käydä vaarallisissa tiloissa harjoituksen aikana. Heidän vaihtoehtonsa ruiskuttaa kalibroitua kohinaa valvojan omiin esittelyihin, joten palautuminen saadaan esitellä ilman, että robotti koskaan ajaisi luottamattomaksi policy:ksi. MuJoCo Humanoidissa he raportoivat DART:in vähentävän valvojan kumulatiivisen palkinnon 5 prosenttia harjoituksen aikana, kun taas DAgger ajaa policy:a 80 prosenttia vähemmän kumulatiivisella palkkiolla kuin valvoja; kiinni tarttuminen sekaisuudessa Toyota HSR:llä, keskimäärin 62 prosentin nousu behavior cloningiin verrattuna.

Zhang ja Cho:n SafeDAgger käsittelee kyselyjä referenssipolicy:lle niukkana resurssina: erillinen turvallisuuspolicy ennustaa, ilman kyselyä, ovatko pääpolicy lähellä poikkeamaa referenssistä kynnyksen yli, ja vain nämä tilat luovutetaan. Kaikki kolme reagoivat samaan tosiasiaan - DAgger analyysi ei veloita mitään asiantuntijan merkeistä, ja todellisuus veloittaa paljon.

Mitä tämä tarkoittaa SO-100:lle työpöydällä

Käännä horisontti omiksi yksiköiksi. Kaksikymmentä sekuntia episodia 30 kehyksellä sekunnissa on 600 päätösaskelta, ja T jokaisessa rajassa yllä on kyseinen numero. T = 600, ero termin skaalautumisen välillä T:llä ja T:n neliöllä on ero policy:n välillä, joka toipuu huonosta lähestymistavasta ja sellaisen välillä, joka ei.

Tämä on osasyy miksi toimintojen niputtaminen auttaa: kun policy lähettää lyhyen toimintojen sekvenssin päättelyaskelta kohti, päätöspisteen määrä laskee, ja niin tekee mahdollisuuksien määrä yhdistää. Zhao, Kumar, Levine ja Finn nimeävät kumulatiivisen virheen Action Chunking with Transformers motivaatioksi, ja raportoivat 80-90 prosentin menestymisen kuudessa vaikeassa todellisen maailman tehtävässä, pienellä kaksikäsisellä laitteistolla, kymmenestä minuutista esittelystä. Niputtaminen ei poista covariate shiftiä - tilat ovat silti policy:n omia - mutta se lyhentää tehollista horisontia. Katso toimintojen niputtaminen ja SO-100 imitation learning opas.

Toinen käännös on edistysmetriikka. Et voi mitata epsilonia policy:n omalla jakauman alla suoraan - se tarvitsee perus-totuuden asiantuntijan toiminnot jokaiselle käydetylle tilalle, asia, jonka yritit välttää tuottamasta. Mitä ihmisten valvoma silmukka antaa sen sijaan on intervention nopeus: osuus kehyksistä ajossa, joiden aikana ihminen oli ottanut haltuunsa. Se on välitysmuuttuja, ja se muuttuu syistä, jotka eivät liity policy:hin - kärsivällinen operaattori puuttuu vähemmän. Käytetty johdonmukaisesti, se on yksi numero, joka kertoo onko kierros ollut arvoinen iltapäivää.

Kolmas käännös on data-laatu varoitus, jota analyysi ei kata. Mandlekar ja kollegat tutkivat kuutta offline-oppimisalgoritmia viidessä simuloidussa ja kolmessa todellisen maailman multi-stage manipulaatiotehtävässä, ja raportoivat herkkyyttä algoritmisille suunnitteluvalinnoille, riippuvuutta demonstraatioiden laadusta, ja vaihtelua pysäytyskriteerillä aiheutuvaksi. Belkhale, Cui ja Sadigh väittävät, että tietojoukkon laatu tulee muodostaa toimintojen eroavaisuuden ja siirtymän monimuotoisuuden kautta, ja huomaavat, että tilojen monimuotoisuus ei aina ole hyödyllistä. DAgger kierros lisää tiloja, joita kukaan ei valittu tarkoituksella: jotkut ovat palautumistiedot, joita tarvitset, jotkut ovat robotti heilumassa, kun sinä turvautua haltuunotto-ohjainta.

Mekaanisesti kierros on kuusi vaihetta: aja päättelyä kirjauksen kanssa, ota haltuunsa kun policy käyttäytyy väärin, arvioi kierros ja arkistoi jokaisen episodin, synkronoi korjaukset, koosta sekoitettu tietojoukko alkuperäisistä sekä korjauksista lähdesivun mukaan valitulla episodilla, ja jatka koulutusta edellisestä tarkistuspisteestä eikä perusmallia. Ay-robots:ssa nämä vaiheet ovat olemassa painikkeina, jotka poistavat putkiston mutta eivät harkintaa. Kaksi varoitusta: tarkistuspisteestä jatkaminen alustaa painot eikä ole optimoija-resume, ja johtajan käden linjaus-liike on silti kevyesti testattu laitteistolla. Katso koulutus ja tietojoukot.

Perheträvi, yhdessä taulukossa

Usein kysytyt kysymykset

Minne sieltä

Jos et ole vielä kouluttanut policy:a, tämä teoria on ennenaikainen: kirjaa tietojoukko ensin, aloittaen kouluttaminen ensimmäistä policy:a ja työpöydän asiakkaasta. Jos punnit toista sataa puhtasta esittelyä vastaan aloitettavia korjauksia: puhtaat esittelyt eivät korjaa jakauman ongelmaa. Mekaanisuuden osalta, jatka ihmisten valvoma varianti ja sitten SO-100 kävely.