DAgger objaśniony: Dlaczego Behavior Cloning dryfuje i co agregacja zbiorów danych faktycznie udowadnia

Istnieje określony typ awarii, z którym spotyka się każdy, kto trenuje politykę manipulacji, wcześniej czy później. Polityka sięga po sześcian, zbliża się na dwa centymetry, zawaha się, dryfuje na boki, a następnie robi coś niezwiązanego z zadaniem. Strata walidacji była w porządku. Replay w open-loop względem wstrzymanych epizodów było w porządku. A jednak ramię robota kończy się w pozycji, która nigdzie nie pojawia się w danych treningowych, i stąd nie ma nic sensownego do powiedzenia.

Ta awaria ma nazwę i ugruntowaną teorię za sobą. To jest pierwszy z czterech artykułów na temat DAgger, i obejmuje sam argument: dlaczego dopasowanie polityki do własnych trajektorii demonštratora daje błąd, który może rosnąć z kwadratem długości epizodu, co zmienia agregacja zbiorów danych, i co dowód bez żału nie obiecuje. Pętla na rzeczywistym sprzęcie jest omówiona w uruchomianiu pętli DAgger na SO-100, wariant kontrolowany przez człowieka w HG-DAgger i interwencje kontrolowane przez człowieka, i pytanie pomiarowe w pomiarze pętli DAgger.

Założenie, które behavior cloning dyskretnie przyjmuje

Zbiór danych demonstracyjnych to stos par obserwacja-akcja. Behavior cloning dopasowuje funkcję do tego stosu zwykłym uczeniem nadzorowanym i kończy. To jest najstarsza idea w tej dziedzinie. ALVINN Pomerleau z 1988 roku był trzywarstwową siecią propagacji wstecz, która pobierała obrazy z kamery i czujnika zasięgu laserowego i produkował kierunek, w którym pojazd powinien się poruszać; był trenowany na symulowanych obrazach dróg i podążał rzeczywistymi drogami w niektórych warunkach polowych. Przepis się nie zmienił wiele; sieci owszem.

Co się pomija, to sprawdzenie, skąd pochodzą te pary. Każda z nich leży na trajektorii, którą stworzył demonstrujący. Polityka, którą wdrażasz, tworzy swoją własną. W momencie, gdy się odchyla, jest kwestionowana o stany, które nie były w rozkładzie treningowym, a jej odpowiedź przesuwa ją dalej. Ross, Gordon i Bagnell otwierają artykuł DAgger dokładnie tym: predykcja sekwencyjną narusza założenie i.i.d. leżące u podstaw uczenia statystycznego, ponieważ własne przewidywania ucznia określają wejścia, które widzi dalej.

Najjaśniejszą ilustracją w tym artykule nie jest robot wcale. Klonowanie quasi-optymalnego planisty dla Super Mario Bros. dało politykę, która wielokrotnie utykała o przeszkodę zamiast ją przeskoczyć. Powód to cały argument w jednym zdaniu: ekspert zawsze przeskakiwał z wygodnej odległości, więc zbiór danych nie zawierał stanu, w którym Mario były przygniecione do przeszkody, a zatem nie zawierał etykiety, co robić, gdy tam był.

Zamień Mario na ramię SO-100 i struktura jest identyczna. Twoje demonstracje pokazują czysty zbliż i czysty chwyt, nie chwytacz zamykający się dwa centymetry za krótko - tak że polityka nie ma pojęcia, co robić stąd, i cokolwiek zgaduje, przesuwa ją dalej. Covariate shift jest właściwością procedury zbierania danych, nie architektury sieci.

Skąd pochodzi termin kwadratowy

Artykuł AISTATS z 2010 roku autorstwa Rossa i Bagnella, Efficient Reductions for Imitation Learning, precyzuje nawarstwianie się. Niech T będzie horyzontem zadania, niech koszt zadania będzie ograniczony w przedziale jednostkowym, i niech epsilon będzie stratą zastępczą zmierzoną pod rozkładem stanów eksperta - liczbą, którą raportuje Twój zbiór walidacyjny. Wtedy dodatkowy koszt uruchomienia tej polityki na T kroków względem eksperta jest ograniczony przez T do kwadratu razy epsilon. Ross, Gordon i Bagnell powtarzają to jako Theorem 2.1 w artykule DAgger i dodają zdanie, które ma znaczenie: granica jest ścisła. Istnieją problemy, w których polityka z stratą epsilon na rozkładzie eksperta rzeczywiście ponosi dodatkowy koszt rosnący kwadratowo w T.

Ścisłe nie oznacza typowe. Termin kwadratowy to najgorszy przypadek na klasie problemów, nie przewidywanie o twoim zadaniu pick-and-place. To ustala, że więcej demonstracji eksperta nie może usunąć problem: tylko ostrzega szacunek epsilon na rozkładzie, na którym polityka nie będzie testowana.

Droga ucieczki znajduje się w tym samym artykule, powtórzona jako Theorem 2.2. Jeśli polityka osiąga stratę epsilon pod jego własnym rozkładem stanów, i pojedyncza zła akcja kosztuje co najwyżej u w koszcie do celu pod ekspertem, dodatkowy koszt jest ograniczony przez u razy T razy epsilon - liniowy w horyzoncie. Stała u to interesująca ilość: co najwyżej 1 dla niezgodności 0-1 z ekspertem, i O(1) kiedykolwiek ekspert może się odzyskać w kilka kroków. W najgorszym przypadku to O(T), a granica liniowa nie jest wtedy lepsza od kwadratowej.

Dwie próby poprzedzające DAgger

Forward training to uczciwa ale niepraktyczna odpowiedź. Trenuj oddzielną politykę dla każdego kroku czasowego, po kolei, każda na rozkładzie stanów indukowanym przez polityki już ustalone dla wcześniejszych kroków, so każda polityka widzi dokładnie rozkład, z którym się spotka. Haczyk jest w opisie: T polityk, trenowanych sekwencyjnie, bez wczesnego zatrzymywania. W przypadku manipulacji episodu przy 30 klatkach na sekundę, T wynosi setki.

SMILe z tego samego artykułu i SEARN z pracy Daumé, Langforda i Marcusa nad strukturalną predykcją idą inną drogą: jedna stacjonarna polityka, ale stochastyczna. Każda iteracja trenuje komponent i dodaje go do mieszanki, przesuwając masę probabilistyczną od eksperta. Wynikiem jest mieszanka, w której niektóre komponenty są gorsze od innych - na fizycznym ramieniu, kontroler, który może próbować złego komponentu w trakcie ruchu. To jest podane uzasadnienie dla chęci stacjonarnej deterministycznej polityki zamiast tego.

DAgger: jeden pomysł, jedno pudełko

Agregacja zbiorów danych zachowuje deterministyczną politykę i przenosi naprawę do zbierania danych. Każda runda: uruchom bieżącą politykę, zapisz stany, które odwiedza, poproś eksperta, co byłoby prawidłową akcją w każdym, dodaj te pary do zbioru danych, który masz już, ponownie trenuj na sumie. Nazwa to algorytm - agregujesz, nigdy nie odrzucasz.

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

Trzy szczegóły ważą więcej niż wyglądają. Etykiety są dla stanów odwiedzanych przez mieszaną politykę, ale akcje pochodzą od eksperta - polityka dostarcza pytania, ekspert odpowiedzi. Ponowne trenowanie jest na całym agregacie, co czyni każdą rundę krokiem Follow-The-Leader: w rundzie n wybierasz najlepszą politykę z perspektywy na każdą trajektorię do tej pory. To jest framing, na którym dowód się zawiesza. I algorytm kończy się zwracając najlepszą politykę w sekwencji wybraną na zbiorze walidacyjnym, ponieważ twierdzenia gwarantują, że jakaś polityka w sekwencji jest dobra, nie że ostatnia jest.

Harmonogram beta i dlaczego nie jest on pokrętłem do regulacji

Mieszana polityka to beta_i razy ekspert plus jeden minus beta_i razy uczeń. Punkt jest praktyczny: pierwsze kilka nauczonych polityk jest trenowanych na bardzo mało danych, popełnia wiele błędów, i inaczej spędzałby rollout w stanach, które stają się nieistotne, gdy polityka się poprawi.

Teoria nakłada dokładnie jeden warunek: średnia bieżąca bet musi zmienić się na zero. Analiza działa z beta_i ograniczoną przez (1 - alfa) do mocy i-1, dla stałej alfa niezależnej od T.

Luka między 2980 a 3030 na skali sięgającej około 4300 jest mała, ale wyjaśnienie artykułu jest najużyteczniejszą praktyczną notatką w tej sekcji. Z harmonogramem bez parametrów Mario utknął w tym samym miejscu na wczesnym etapie i wygenerował masę prawie zduplikowanych danych z tej jednej lokalizacji; pozwalając ekspertowi kierować frakcję czasu zarówno go uwolnił, jak i poszerzył różnorodność stanów. Harmonogram dotyczy mniej stosunku mieszankę niż tego, czy zbieranie danych stale produkuje nowe stany czy to samo niepowodzenie.

Gwarancja: redukcja do uczenia online bez żału

Oto posunięcie, które sprawia, że artykuł jest tym, czym jest. Potraktuj każdą rundę DAgger jako jeden przykład w problemie uczenia online, gdzie strata w rundzie i to strata zastępcza pod rozkładem stanów polityki użytej w rundzie i. Uczeń zobowiązuje się do polityki przed zobaczeniem tej straty, i sekwencja jest niestacjonarna, ponieważ zależy od wyprodukowanych polityk do tej pory.

Algorytm jest bez żału, jeśli jego średnia strata na N rund zbliża się do najlepszej pojedynczej polityki z perspektywy. Follow-The-Leader na silnie wypukłych stratach jest takim algorytmem, ze średnim żałem kurczącym się na poziomie 1/N - i ponowne trenowanie na pełnym agregacie to dokładnie Follow-The-Leader. Każdy inny uczeń bez żału byłby równie dobry: analiza to redukcja, nie właściwość jednego optymalizera.

Jeden lemat przerzuca przepaść między mieszaną polityką, która zebrała dane, a nauczaną polityką, która będzie wdrażana: Lemma 4.1 ogranicza odległość L1 między ich rozkładami stanów przez 2 T beta_i. Dlatego bety muszą się zmniejszać - podczas gdy ekspert nadal sprawuje przychody kontroli, stany, które zbierasz, to nie stany, które twoja polityka będzie produkować. Połącz lemat z granicą żału a główny wynik następuje: po około T iteracjach, jakaś polityka w sekwencji ma stratę zastępczą pod jej własnym rozkładem w O(1/T) epsilon_N. Włóż to do granicy liniowej i ląduj na Theorem 3.2.

Strona empiryczna jest skromna według dzisiejszych standardów. W Super Tux Kart nadzorowana linia bazowa nie poprawiła swoich średnich upadków na okrążenie, gdy przyszło więcej danych, DAgger osiągnął politykę, która nigdy nie spadła z toru po piętnastu iteracjach, a SMILe po dwudziestu wciąż spadła mniej więcej dwa razy na okrążenie. W benchmarku pisma ręcznego, dokładność znaku wynosiła 82 procent bez struktury, 83,6 procent nadzorowany, 85,5 procent z DAgger. Żaden z nich nie jest wynikiem manipulacji.

Co dowód nie obiecuje

Stwierdzenia twierdzeń są warunkowe, a warunki są znaczące.

Jeden dalszy wynik jest często cytowany jako refutacja i nie jest nim. Rajaraman, Yang, Jiao i Ramachandran badają minimax limity imitation learning w episodowych MDP ze skończoną przestrzenią stanów S i horyzontem H, i udowadniają dolną granicę suboptimalności na rzęd |S| H do kwadratu nad N, która utrzymuje się nawet gdy uczeń może aktywnie kwestionować eksperta w odwiedzonych stanach. To jest najgorszy przypadek na klasie MDP przy ustalonym budżecie epizodu, i co wyklucza, to idea, że interakcja poprawia minimax tempo; twierdzenie DAgger to inny stwierdzenie, ograniczające wdrażaną politykę do tego, co jej własna klasa polityk może osiągnąć.

Swamy, Choudhury, Bagnell i Wu później zaklasyfikowali te algorytmy według których momentów zachowania eksperta pasują, i wprowadzili pojęcie odzyskania momentu, które określa jak dobrze każda rodzina łagodzi błąd nawarstwiający się. Przeglądy Osa i Celemina obejmują krajobraz algorytmiczny i interfejsy sprzężenia zwrotnego człowieka.

Rachunek: etykietowanie stanów, które ekspert nigdy nie wyprodukował

Wszystko powyżej zakłada eksperta, który może być kwestionowany wszędzie. W symulacji z planistą, który jest prawie bezpłatny - eksperymenty Mario używały quasi-optymalnego planisty z pełnym dostępem do stanu gry. Z człowiekiem na robocie to jest dominujący koszt, i dziwny: człowiek musi wygenerować prawidłową akcję w konfiguracji, którą ich własna kompetencja nigdy by nie stworzyła.

Kelly, Sidrane, Driggs-Campbell i Kochenderfer stawiają sprzeciw wprost w artykule HG-DAgger. Vanilla DAgger wymaga od eksperta dostarczenia etykiet akcji, jednocześnie nie będąc w pełni pod kontrolą systemu. To zmniejsza bezpieczeństwo, i z ludzkimi ekspertami jest prawdopodobne, że pogorszy jakość zebranych etykiet, którą przypisują postrzegane opóźnieniu aktuatora. Etykieta, którą otrzymujesz zwrotnie, to nie etykieta, którą algorytm założył.

Laskey i kolegowie atakują problem z innej strony za pomocą DART, i ich framing jest bezpośredni: techniki on-policy są żmudne dla ludzkich nadzorców, dodają obciążenie obliczeniowe i mogą odwiedzać niebezpieczne stany podczas treningu. Ich alternatywa wstrzykuje skalibrowany szum do własnych demonstracji nadzorcy, aby odzyskanie się demonstrowało bez robota kiedykolwiek uruchamiającego niezaufaną politykę. Na MuJoCo Humanoid raportują DART zmniejszenie łącznego wynagrodzenia nadzorcy o 5 procent podczas treningu, podczas gdy DAgger wykonuje polityki z 80 procentami mniej łącznego wynagrodź niż nadzorca; na chwytaniu w zagmatwanym z Toyota HSR, średni wzrost 62 procent względem behavior cloning.

SafeDAgger Zhang i Cho traktuje zapytania do polityki odniesienia jako rzadki zasób: oddzielna polityka bezpieczeństwa przewiduje, bez zapytania, czy główna polityka zbliża się do odejścia od odniesienia poza próg, i tylko te stany są przekazywane. Wszystkie trzy reagują na ten sam fakt - analiza DAgger nie pobiera nic za etykiety eksperta, a rzeczywistość pobiera wiele.

Co to oznacza dla SO-100 na twoim biurku

Przetłumacz horyzont na twoje własne jednostki. Epizod trzydzieści sekund przy 30 klatkach na sekundę to 600 kroków decyzji, i T we wszystkich powyższych granicach to ta liczba. Przy T = 600 różnica między terminem skalującym się z T a jednym skalującym się z T do kwadratu to różnica między polityką, która odzyskuje się ze złej akcji, a tą, która nie.

To jest część, dlaczego chunking akcji pomaga: gdy polityka emituje krótką sekwencję akcji na krok wnioskowania, liczba punktów decyzji spada, a także liczba szans do nawarstwiania się. Zhao, Kumar, Levine i Finn noszą błąd nawarstwiający się jako motywację do Action Chunking with Transformers i raportują 80 do 90 procent sukcesu na sześciu trudnych rzeczywistych zadaniach, na tankim sprzęcie dwurękim, z dziesięciu minut demonstracji. Chunking nie usuwa covariate shift - stany są wciąż własnymi polityką - ale skraca efektywny horyzont. Zobacz chunking akcji i poradnik imitation learning SO-100.

Drugie tłumaczenie to metryka postępu. Nie możesz zmierzyć epsilon pod własnym rozkładem polityki bezpośrednio - to wymaga akcji eksperta z podstawową prawdą dla każdego odwiedzonego stanu, rzeczy, którą próbujesz unikać produkowania. Co pętla kontrolowana przez człowieka daje ci zamiast tego, to intervention rate: ułamek ramek w biegu, podczas którego człowiek przejął. To jest proxy, i porusza się z powodów niezwiązanych z polityką - cierpliwy operator mniej się interweniuje. Używane konsekwentnie, to jedyna liczba, która mówi, czy runda warta była popołudnia.

Trzecie tłumaczenie to ostrzeżenie o jakości danych, które analiza nie obejmuje. Mandlekar i współpracownicy badali sześć offline algorytmów uczenia na pięciu symulowanych i trzech rzeczywistych zadaniach manipulacji wieloetapowej, i raportują czułość na wybory algorytmiczne, zależność od jakości demonstracji i zmienność spowodowaną kryterium zatrzymania. Belkhale, Cui i Sadigh argumentują, że jakość zbioru danych powinna być sformalizowana poprzez dywergencję akcji i różnorodność przejścia, i zauważają, że różnorodność stanu nie zawsze jest korzystna. Runda DAgger dodaje stany, których nikt celowo nie wybrał: niektóre to dane odzyskiwania, których potrzebujesz, niektóre to robot majaczący, podczas gdy szukasz kontroli przejęcia.

Mechanicznie runda to sześć kroków: uruchom wnioskowanie z nagrywaniem, przejdź, gdy polityka się myli, przejrzyj bieg i złóż każdy epizod, zsynchronizuj korekty, skomponuj mieszany zbiór danych z oryginałów i korekcji z wyborem episodów wyraźnie na źródło, i kontynuuj trening z poprzedniego punktu kontrolnego zamiast modelu bazowego. Na ay-robots te kroki istnieją jako przyciski, co usuwa instalację hydrauliczną ale nie osąd. Dwa zastrzeżenia: kontynuacja z punktu kontrolnego inicjuje wagi i nie jest wznowieniem optymalizera, i ruch wyrównania ramienia lidera jest wciąż lekko testowany na sprzęcie. Zobacz trenowanie i zbiory danych.

Drzewo genealogiczne w jednej tabeli

Często zadawane pytania

Gdzie iść stąd

Jeśli nie trenowałeś jeszcze polityki, ta teoria jest przedwczesna: nagraj zbiór danych najpierw, zaczynając od trenerowania swojej pierwszej polityki i klienta desktopowego. Jeśli rozważasz sto kolejnych czystych demonstracji contra uruchamianie korekcji: czyste demonstracje nie rozwiązują problemu dystrybucji. Dla mechaniki, kontynuuj z wariantem kontrolowanym przez człowieka i wtedy przewodnikiem SO-100.