Machine Learning

Zautomatyzowane techniki gromadzenia danych wraz z niedrogim urządzeniem pamięci masowej umożliwiły gromadzenie i przechowywanie olbrzymich ilości danych. Zakupy w punktach sprzedaży, odczyty temperatury i ciśnienia (wraz z innymi danymi pogodowymi), wiadomości, transakcje finansowe wszelkiego rodzaju, strony internetowe i zapisy interakcji w sieci to tylko kilka z wielu przykładów. Ale ogromna ilość surowych danych wymaga skutecznych technik "eksploracji danych" w celu klasyfikacji, kwantyfikacji i wyodrębniania przydatnych informacji. Metody uczenia maszynowego odgrywają coraz większą rolę w analizie danych, ponieważ mogą radzić sobie z ogromnymi ilościami danych. W rzeczywistości im więcej danych, tym lepiej. Większość metod uczenia maszynowego konstruuje hipotezy na podstawie danych. Tak więc (na przykład klasyczny przykład), jeśli duży zestaw danych zawiera kilka wystąpień łabędzi będących białymi i żadnych wystąpień łabędzi innych kolorów, wówczas algorytm uczenia maszynowego może wywnioskować, że "wszystkie łabędzie są białe". Wnioskowanie jest "indukcyjne", a nie "dedukcyjne". Wnioski dedukcyjne wynikają koniecznie i logicznie z ich przesłanek, podczas gdy indukcyjne są hipotezami, które zawsze podlegają sfałszowaniu przez dodatkowe dane. (Być może nadal istnieje nieodkryta wyspa czarnych łabędzi .) Mimo to wnioskowania indukcyjne, oparte na dużej ilości danych, są niezwykle przydatne. Rzeczywiście sama nauka opiera się na wnioskach indukcyjnych. Podczas gdy przed około 1980 r. Uczenie maszynowe (reprezentowane głównie przez metody sieci neuronowej) było przez niektórych uważane za margines sztucznej inteligencji, uczenie maszynowe stało się ostatnio znacznie ważniejsze we współczesnej sztucznej inteligencji. Opisałem już jeden przykład, a mianowicie wykorzystanie sieci bayesowskich, które są automatycznie konstruowane z danych. Rozwój r, począwszy od lat 80. XX wieku, uczynił uczenie maszynowe jedną z najważniejszych gałęzi sztucznej inteligencji.

Uczenie się oparte na pamięci

Zwykłym podejściem sztucznej inteligencji do radzenia sobie z dużymi ilościami danych jest w pewien sposób zmniejszenie ich ilości. Na przykład sieć neuronowa jest w stanie reprezentować to, co jest ważne w dużej ilości danych treningowych, według struktury sieci i wartości masy. Podobnie, uczenie się sieci bayesowskiej na podstawie danych powoduje kondensację tych danych w strukturze węzła sieci i jej tabelach prawdopodobieństwa warunkowego. Jednak nasze rosnące możliwości przechowywania dużych ilości danych w pamięci komputera o szybkim dostępie i obliczania tych danych umożliwiły techniki, które przechowują i wykorzystują wszystkie dane w razie potrzeby - bez wcześniejszej kondensacji. Oznacza to, że te techniki nie próbują zmniejszyć ilości danych, zanim zostaną one faktycznie wykorzystane do jakiegoś zadania. Wszystkie niezbędne redukcje, na przykład decyzji, są wykonywane w momencie podjęcia decyzji. W dalszej części opiszę niektóre z tych metod uczenia się opartych na pamięci. Wspomniałem już o metodach "najbliższego sąsiada" do klasyfikacji punktu w przestrzeni wielowymiarowej. Na przykład "reguła k-najbliższego sąsiada" przypisuje punkt danych do tej samej kategorii, co większość k przechowywane punkty danych, które są najbliżej. Podobną technikę można zastosować do powiązania wartości liczbowej (lub zestawu wartości) z punktem danych. Na przykład można przypisać średnią z przechowywanych wartości powiązanych z najbliższymi sąsiadami nowy punkt. Ta wersja reguły może być używana w aplikacjach kontrolnych lub szacunkowych. Reguła k-najbliższego sąsiada jest prototypowym przykładem uczenia się opartego na pamięci i wywołuje kilka pytań na temat możliwych rozszerzeń. Po pierwsze, zastosować najbliższe- reguła sąsiada (jak to już przedstawiłem), każdy punkt odniesienia musi być listą liczb {punkt lub wektor w przestrzeni wielowymiarowej. o, jedno pytanie brzmi: "Jak przedstawić dane tak, aby coś w rodzaju metody najbliższego sąsiada można zastosować? "Po drugie, co to jest "odległość" do zmierzenia między punktami danych? Gdy dane są reprezentowane przez punkty w przestrzeni wielowymiarowej, naturalnym wyborem jest zwykła odległość euklidesowa. Jednak nawet w takim przypadku zwykle "przeskalowuje się" wymiary, aby nie przypisywać nadmiernej wagi tym wymiarom, dla których dane są bardziej "rozłożone". Jeśli dane nie są reprezentowane jako punkty w przestrzeni, należy zastosować inny sposób pomiaru "bliskości" danych. W zależności od formy danych zaproponowano kilka metod. Po trzecie, czy wśród najbliższych punktów danych bliższe wyniki powinny być lepsze niż odległe? Podstawową metodę k-najbliższego sąsiada można rozszerzyć, ważąc ważność punktów danych w sposób zależny od ich bliskości. Zwykle używa się czegoś zwanego "jądrem", które stopniowo zmniejsza wagę punktów danych, które są coraz dalej. Po czwarte, jaka powinna być wartość k? Ilu pobliskich sąsiadów wykorzystamy, podejmując decyzję w sprawie nowej części danych? Cóż, przy odpowiednim rodzaju jądra można wziąć pod uwagę wszystkie punkty danych. Te, które są najdalej, po prostu miałyby zerowy lub nieistotny wpływ na decyzję. Pytanie o to, jaką wartość k do użycia zastępuje się teraz pytaniem o to, jak daleko powinien rozciągać się wpływ jądra. Wreszcie, po uwzględnieniu wszystkich ważonych sąsiadów, w jaki sposób podejmujemy decyzję lub przypisujemy wartość liczbową lub wartości? Powinno to być w taki sam jak ten związany z większością głosów sąsiadów, a może z jakąś "średnią" ważonych sąsiadów? W zależności od tego wyboru można zaimplementować różne wersje tak zwanych metod regresji statystycznej. Andrew W. Moore i Christopher G. Atkeson (są jednymi z pionierów w opracowywaniu rozszerzeń zasad k-najbliższych sąsiadów i zastosowaniu tych rozszerzeń do kilku ważnych problemów w eksploracji danych i kontroli robota. Eksperymenty w stosowaniu tych pomysłów do kontrolowania problemów opisano w kilku artykułach. Jeden artykuł2 wspomina o sterowaniu robotycznym urządzeniem do gry w żonglerkę zwaną "trzymaniem diabła". Opracowano system oparty na pamięci, aby nauczyć się, jak trzymać kij w grze. Rysunek poniżej pokazuje schemat żonglowania człowiekia



Przedstawiono również konfigurację robotów z niektórymi parametrami sensorycznymi i kontrolnymi.

Rozumowanie na podstawie przypadków

Dziedzinę sztucznej inteligencji, zwaną "rozumowaniem opartym na analizie przypadków" (CBR), można postrzegać jako uogólniony rodzaj uczenia się opartego na pamięci. W CBR przechowywana biblioteka "spraw" służy do analizy, interpretacji i rozwiązywania nowych spraw. Na przykład w medycynie zapisy diagnostyczne i terapeutyczne dla pacjentów stanowią bibliotekę przypadków; po przedstawieniu nowego przypadku podobne przypadki można pobrać z biblioteki, aby pomóc w diagnozowaniu i leczeniu. W prawie wcześniejsze precedensy prawne są stosowane w interpretacjach i decyzjach dotyczących nowych spraw (zgodnie z praktyką prawną stare decisis, która nakazuje rozstrzyganie spraw w oparciu o precedensy określone w poprzednich sprawach). Przypadki podobne do nowego przypadku można traktować jako "sąsiadów" w uogólnionej "przestrzeni" przypadków. Aby odzyskać bliskich sąsiadów, idea bliskości w tej przestrzeni musi opierać się na pewnej mierze podobieństwa. Jedna z pionierów wnioskowania na podstawie przypadków, Janet Kolodner, profesor informatyki i kognitywistyki w Georgia Institute of Technology opisuje proces w następujący sposób: Dobrymi przypadkami [do pobrania] są te, które mogą potencjalnie poczynić odpowiednie prognozy dotyczące nowego przypadku. Pobieranie odbywa się za pomocą funkcji nowej sprawy jako indeksów w bibliotece spraw. Przypadki oznaczone przez podzbiory tych funkcji lub przez funkcje, które można uzyskać z tych funkcji, są przywoływane. [Następnie wybieramy spośród tych] najbardziej obiecującą sprawę lub sprawy do uzasadnienia…Czasami właściwe jest wybranie jednego najlepszego przypadku; czasami potrzebny jest mały zestaw. Gdy odzyskana sprawa (lub sprawy) jest przystosowana do zastosowania do nowej sprawy, może następnie (jeśli się powiedzie) zostać zmieniona, tak aby części, które mogą być przydatne do rozwiązywania problemów w przyszłości, mogły zostać zachowane w stale rosnącej bibliotece spraw. Rozumowanie na podstawie przypadków ma swoje korzenie w modelu pamięci dynamicznej Rogera Schanka. Wczesna praca została wykonana przez dwóch doktorantów Schanka, Janet Kolodner i Michaela Lebowitza. Innym ważnym źródłem pomysłów na CBR są pomysły Minsky′ego na temat ram. Edwina Rissland, profesor na University of Massachusetts w Amherst i inny pionier CBR, pisze, że jej praca CBR jest bezpośrednim rozwinięciem jej "pracy nad" ograniczonym generowaniem przykładów " … która modelowała budowę nowych (kontr) przykładów poprzez modyfikację istniejących wcześniejszych "bliskich" przykładów (przedstawionych jako ramek) pobranych z sieci przykładów. "Rissland i jej uczniowie wnieśli istotny wkład w stosowanie CBR w prawie. Napisała, że proces CBR jest czasami podsumowywany przez cztery" R ", Retrieve, Reuse, Revise, i Retain. Według strony internetowej prowadzonej przez Artficial Intelligence Applications Institute na University of Edinburgh, "Case-based Reasoning jest jedną z najbardziej udanych stosowanych technologii sztucznej inteligencji w ostatnich latach. Aplikacje komercyjne i przemysłowe można szybko opracowywać, a istniejące bazy danych korporacyjnych mogą być wykorzystywane jako źródła wiedzy. Najpopularniejsze aplikacje to centra informacyjne i systemy diagnostyczne. "

Drzewa decyzyjne

Następny na liście nowych osiągnięć w uczeniu maszynowym jest automatyczna konstrukcja struktur zwanych "drzewami decyzyjnymi" z dużych baz danych. Drzewa decyzyjne składają się z sekwencji testów służących do określenia kategorii lub wartości liczbowej do przypisania do rekordu danych. Drzewa decyzyjne są szczególnie odpowiednie do użycia z danymi nienumerycznymi i numerycznymi. Na przykład baza danych personelu może zawierać informacje na temat działu pracownika, na przykład marketingu, produkcji lub księgowości. W języku bazy danych takie elementy danych nazywane są "kategorialnymi" (w celu odróżnienia ich od danych liczbowych). W tej sekcji opiszę te struktury, ucząc się metody ich automatycznego konstruowania oraz niektóre z ich aplikacji.

Wyszukiwanie danych i drzewa decyzyjne

Eksploracja danych to proces uzyskiwania przydatnych informacji z dużych baz danych. Rozważmy na przykład bazę danych na temat zachowania kart kredytowych przez ludzi. Może to obejmować zapisy płatności, średnie kwoty zakupu, opłaty za opóźnienie, średnie salda i tak dalej. Odpowiednie metody eksploracji danych mogą ujawnić, między innymi, że ludzie z wysokimi opłatami za późne opłaty, wysokimi średnimi zakupami i innymi zidentyfikowanymi cechami zwykle wykazywali wysokie średnie salda. Jedna ważna metoda eksploracji danych wykorzystuje dane do konstruowania drzew decyzyjnych. Rozważmy bardzo prostą bazę danych, aby zilustrować działanie drzew decyzyjnych. Załóżmy, że firma, powiedzmy Wal-Mart, utrzymuje bazę danych, w której przechowuje informacje o gospodarstwach domowych, do których wcześniej wysłał kupony rabatowe na niektóre swoje produkty. Załóżmy, że baza danych zawiera informacje o lokalizacji gospodarstwa domowego (miejskiego, podmiejskiego lub wiejskiego), rodzaju domu (ranczo lub wielopiętrowy), niezależnie od tego, czy gospodarstwo domowe jest poprzednim klientem Wal-Mart, oraz czy gospodarstwo domowe jest, czy nie odpowiedział na którykolwiek z poprzednich mailingów z kuponami. (Oczywiście jest to tylko zmyślony przykład; właściwie nie wiem nic o prawdziwych bazach Wal-Mart.) Tabelaryczna reprezentacja takiej bazy danych wyglądałaby tak:



Każdy wiersz w tabeli nazywany jest "rekordem". Przedmioty na górze każdej kolumny nazywa się "atrybuty ", a elementy w kolumnie nazywane są" wartościami "odpowiedniego atrybutu. Analiza tej bazy danych, metodami, które wyjaśnię później, może ujawnić, że drzewo decyzyjne pokazane poniżej przechwytuje informacje o tym, które gospodarstwa domowe odpowiedziały na wysyłkę kuponu, a które nie.



Testy wartości atrybutów przeprowadzane są w wewnętrznych węzłach drzewa (w polach), a wyniki (niezależnie od tego, czy pojawiła się odpowiedź) znajdują się na końcach (lub liściach) drzewa (w owalach). Takie drzewo może być przydatne do prognozowania oczekiwanych odpowiedzi przed wysłaniem kolejnej wiadomości. Opracowano metody automatycznego konstruowania (czyli uczenia się) drzew decyzyjnych takich jak ten (i znacznie większe) automatycznie z dużych baz danych.

Konstruowanie drzew decyzyjnych

A. EPAM

Prawdopodobnie najwcześniejszy system do konstruowania drzew decyzyjnych został opracowany pod koniec lat 50. XX wieku przez Edwarda Feigenbauma w ramach jego pracy doktorskiej. Rozprawa pod kierunkiem Herberta Simona z Carnegie Mellon University (wówczas Carnegie Institute of Technology). Jego system nazywał się EPAM, skrót od Elementary Perceiver and Memorizer. Celem badań było "wyjaśnienie i przewidzenie zjawiska [ludzkiego] uczenia się werbalnego". Standardowy eksperyment psychologiczny do testowania tej umiejętności polegał na pokazaniu ludziom par nonsensownych sylab, takich jak DAX-JIR i PIB-JUX. Pierwszy członek pary był nazywany "bodźcem", a drugi "odpowiedzią". Po kilkakrotnym zobaczeniu wielu takich par, pacjentowi następnie pokazuje się losowy bodziec i testuje jego zdolność do generowania prawidłowej odpowiedzi. Pary takie pokazano EPAM podczas "fazy uczenia się". Uczenie się polegało na rozwijaniu czegoś, co Feigenbaum nazwał "siecią dyskryminacyjną" do przechowywania związków między bodźcami i reakcjami. Sieć była tym, co teraz nazwalibyśmy drzewem decyzyjnym z testami cech liter w wewnętrznych węzłach i odpowiedziami przechowywanymi na końcach lub liściach drzewa. W "fazie testowania" programu EPAM sylaba bodźca bezsensownego została przefiltrowana przez testy w dół drzewa, aż do liścia, w którym (ma się nadzieję) zachowano prawidłową odpowiedź. Przykładową sieć dyskryminacyjną EPAM pokazano poniżej



Okrągłe węzły to testy, a węzły w ramkach to odpowiedzi. EPAM nie tylko skutecznie modelował w tym zakresie wydajność ludzi w zadaniu uczenia się "w parze z partnerem", modelowało również zapominanie. Feigenbaum stwierdził, że "o ile wiemy, [EPAM] jest pierwszą konkretną demonstracją tego rodzaju zapominania w maszynie uczącej się". EPAM został napisany w języku przetwarzania list Carnegie, IPL-V. W rzeczywistości funkcje przetwarzania list języków, takich jak IPL-V, były wymagane do pisania programów, które mogłyby rozwijać drzewa decyzyjne. Nic więc dziwnego, że EPAM był pierwszym takim programem. Program Feigenbauma jest nadal uważany za istotny wkład zarówno w teorie ludzkiej inteligencji, jak i badania AI. Simon, Feigenbaum i inni kontynuowali prace nad programami EPAM, których zwieńczeniem był EPAM-VI, kodowany w IPL-V i działający na PC.

B. CLS

Kolejną znaczącą pracę nad drzewami decyzyjnymi wykonano na Uniwersytecie Yale około 1960 roku. Tam psycholog Carl I. Hovland i jego doktorat. uczeń Earl B. (Buz) Hunt opracował komputerowy model uczenia się koncepcji człowieka. Po tym, jak Hovland zapadł na raka w 1961 roku, Hunt kontynuował pracę nad koncepcją uczenia się i współpracował z Janet Marin i Philipem Stone′em przy opracowywaniu serii programów edukacyjnych opartych na drzewie decyzyjnym o nazwie CLS, akronim od Concept Learning System. Hunt i jego koledzy potwierdzili powiązaną wcześniejszą pracę nad EPAM. Przynajmniej dla celów AI systemy CLS wkrótce zostały przyćmione przez inne systemy uczenia się na drzewach decyzyjnych, a mianowicie ID3, CART i powiązane programy.

C. ID3

J. Ross Quinlan opracował ID3, akronim dla iteracyjnego dychotomizera, pod koniec lat siedemdziesiątych, kiedy był na urlopie naukowym (z University of Sydney) w Stanford. (Nazwa pochodzi od faktu, że program konstruował drzewa decyzyjne przez iteracyjne dzielenie zestawów rekordów danych, aż można je było sklasyfikować w jednej z dwóch odrębnych kategorii. Późniejsze wersje pozwoliły na klasyfikację w więcej niż dwóch kategoriach, ale "D" utrzymywało się w nazwie.) Quinlan był wcześniej doktorem (pierwszym właściwie) na Wydziale Informatyki Uniwersytetu Waszyngtońskiego, pracujący w Earl Hunt. Quinlan wyjaśnił genezę ID3 w e-mailu:

"Usiadłem na kursie podanym przez Donalda Michie [odwiedzającego wówczas Stanforda] i zaintrygowało mnie zaproponowane przez niego zadanie, a mianowicie poznanie zasady decydowania o wyniku prostej gry w szachy. ID3 zaczęło się od przekodowania CLS Buz [czyli Earla B. Hunta], ale zmieniłem niektóre wewnętrzne elementy (takie jak kryterium podziału zestawu przypadków) i włączyłem iteracyjne podejście, które pozwoliło ID3 na obsługę wtedy - ogromny zestaw 29 000 skrzynek treningowych."

Oto, w skrócie, jak ID3 przystąpiłoby do budowy drzewa decyzyjnego do przewidywania wartości atrybutu odpowiedzi przy użyciu mojej rozbudowanej bazy danych Wal-Mart. Po pierwsze, ID3 szukałby tego pojedynczego atrybutu, który mógłby być użyty jako "najlepszy" test przy rozróżnianiu tych rekordów danych o wartości "tak" dla atrybutu odpowiedzi od tych o wartości "nie". (Będę miał więcej do powiedzenia na temat tego, jak na chwilę określa się "najlepsze"). Żaden pojedynczy test nie dzieli danych idealnie, ale załóżmy, że lokalizacja działa lepiej niż inne. W końcu w tym przykładzie wszystkie rekordy danych o wartości wiejskiej dla atrybutu lokalizacji ma wartość "tak" dla atrybutu odpowiedzi, a żaden z nich nie ma wartości "nie". Załóżmy, że przewaga (ale nie wszystkie) rekordów danych o wartości podmiejskiej ma wartość tak dla atrybutu odpowiedzi i że przewaga (ale znowu nie wszystkie) rekordów danych o wartości miejski ma wartość nie dla atrybut odpowiedzi. Tak więc atrybut położenia ma całkiem dobre (ale niedoskonałe) zadanie polegające na rozdzielaniu rekordów danych w odniesieniu do atrybutu odpowiedzi. Test wartości atrybutu lokalizacji zostałby zatem użyty jako pierwszy test w drzewie decyzyjnym . Do tej pory podzielilibyśmy bazę danych na trzy podzbiory, z których dwa mają rekordy danych o mieszanych wartościach atrybutu odpowiedzi. Następnie ID3 zastosowałby tę samą technikę podziału do każdego z tych dwóch podzbiorów o mieszanej wartości, szukając dla każdego z nich najlepszej następnej funkcji do użycia jako testu. W tym prostym i raczej nierealistycznym przykładzie dwa testy, które zostałyby zastosowane, a mianowicie typ i klient, zapewniłyby "czyste" podziały (to znaczy te, które nie mają mieszanych wartości), a skończylibyśmy już drzewem decyzyjnym pokazanym powyżej. Gdyby podziały nie były czyste lub w inny sposób nie do zaakceptowania, ID3 kontynuowałby wybieranie testów na wynikowych podzbiorach baz danych, dopóki podziały nie dadzą czystych lub akceptowalnych wyników. Wybór atrybutu do przetestowania jest kluczowy w tworzeniu użytecznych drzew decyzyjnych. W swoim oryginalnym programie ID3 Quinlan zastosował miarę związaną z "dokładnością" wynikającego z tego podziału przy określaniu, którego atrybutu użyć do testowania. W późniejszych pracach użył miary zwanej "zdobywaniem informacji", której dokładnej definicji nie będę tu wchodził, poza stwierdzeniem, że jest to ten atrybut, którego wartości przekazują najwięcej 'informacji"o poszukiwanej kategoryzacji. Quinlan użył definicji Claude′a Shannona do mierzenia ilości informacji. Jeszcze później użył znormalizowanej miary zdobywania informacji, aby nie odchylać się na korzyść testów z wieloma wynikami. Zainteresowanie maszyną symboliczną Quinlana i innych była ukierunkowana głównie na uczenie się tego rodzaju reguł na podstawie danych. Z drzewa decyzyjnego łatwo jest konstruować reguły, śledząc testy w celu wygenerowania części "IF" i wykorzystując wskazówki zawarte w części "THEN". Na przykład w przykładzie bazy danych Wal-Mart możemy wywnioskować następujące reguły z drzewa decyzyjnego:

IF (location = suburban) and (type = ranch), THEN (response = no)
IF (location = suburban) and (type = multi-story), THEN (response = yes)
IF (location = rural), THEN (response = yes)
IF (location = urban) and (customer = yes), THEN (response = no)

IF (location = urban) and (customer = no), THEN (response = yes)

W pracy Quinlana w Stanford, ID3 był w stanie wygenerować dość duże drzewa decyzyjne, a tym samym zestawy reguł, do przewidywania, czy pewne pozycje w szachach końcowych zakończą się stratą dla czarnych. W przypadku problemu tego typu zasugerowanego przez Donalda Michie, ID3 użył dwudziestu atrybutów (obejmujących cechy pozycji kawałków na planszy) i bazy danych 29 236 różnych ułożenia kawałków, aby zbudować drzewo z 393 węzłami, których przewidywania były prawidłowe 99,74% . Jednym z problemów, którego należy unikać przy konstruowaniu drzew decyzyjnych, jest "przesadzanie", to znaczy wybieranie testów na podstawie tak małej ilości danych, że wyniki testów nie wychwytują znaczących relacji w danych jako całości. Bez względu na to, jak duża jest oryginalna baza danych, jeśli seria testów ostatecznie wytworzy podzbiór, który nadal nie jest czysty, ale został zredukowany do zbyt małej liczby rekordów danych, każda próba podzielenia tego podzbioru przekroczyłaby te dane, a zatem nie byłaby przydatna. Z tego powodu techniki uczenia się drzewa decyzyjnego zazwyczaj zatrzymują budowę drzewa tuż przed podzbiorami danych, które miałyby zbyt mało rekordów, ale nadal dawałyby akceptowalne wyniki.

D. C4.5, CART i następcy

Quinlan kontynuował pracę nad systemami do konstruowania drzew decyzyjnych, poprawiając ich moc i możliwości zastosowania. Powiedział, że "ID3 jest dość prosty - około 600 linii PASCAL".Jego system C4.5 (który miał około 9 000 linii C) mógł pracować z bazami danych, których atrybuty miały ciągłe wartości liczbowe oprócz tych kategorycznych. Mógł nawet radzą sobie z bazami danych, w których niektórych rekordach brakowało wartości niektórych atrybutów. Na koniec dysponowano metodami poprawy ogólnej wydajności poprzez przycinanie niektórych części drzewa i dla uproszczenia reguły IF-THEN wywodzące się z drzew. Firma komercyjna Quinlana, założona w 1983 roku, sprzedaje ulepszoną wersję C4.5 o nazwie C5.0 (wraz z wersją Windows o nazwie See5) . Donald Michie założył również firmę, która niezależnie opracowała komercyjną wersję ID3 o nazwie ACLS. Jednym ze znaczących postępów w uczeniu maszynowym w tym okresie była owocna współpraca między ludźmi sztucznej inteligencji a statystykami, którzy prowadzili fundamentalne, a także badania stosowane w zakresie klasyfikacji, szacowania i prognozowania. Każda grupa uczyła się od drugiej, a uczenie maszynowe jest dla niej znacznie bogatsze. Chociaż w tę współpracę zaangażowanych było kilka osób, mógłbym wspomnieć w szczególności statystyka Stanforda, Jerome′a Friedmana, który rozpoczął współpracę z niektórymi doktoratami AI ze Stanford. Po swojej wcześniejszej pracy nad konstrukcją drzewa decyzyjnego Friedman, we współpracy z Leo Breimanem, Richardem Olshenem i Charlesem Stoneem, pomógł opracować system o nazwie CART, akronim dla drzew klasyfikacyjnych i drzew regresji. CART ma wiele funkcji z C4. 5 (i w rzeczywistości C4.5 zastosował techniki CART do radzenia sobie z atrybutami liczbowymi). Systemy uczenia drzew decyzyjnych zostały zastosowane do szerokiej gamy problemów eksploracji danych

E. Programowanie logiki indukcyjnej

Wyrażone w języku logiki zdań, JEŻELI {NASTĘPNIE reguły utworzone z drzew decyzyjnych mają postać P1 ∧ P2∧… PN → P. P i Q to zdania bez wewnętrznej struktury. Wcześniej mówiłem o rachunku predykatów, w którym zdania, zwane predykatami, miały wewnętrzne argumenty. W tym języku można mieć znacznie bardziej wyraziste reguły, takie jak ∀ (x , y, z) [Ojciec (x; y) ∧ Rodzeństwo (z , y) → Ojciec (x; z)], na przykład. Opracowano kilka technik uczenia się tego rodzaju reguł "relacyjnych" z baz danych i innych "wiedzy podstawowej". (Wspomniałem wcześniej pokrewny temat, mianowicie uczenie się "probabilistycznych modeli relacyjnych", które są wersjami sieci bayesowskich, które dopuszczały predykaty ze zmiennymi.) Jeden ze wczesnych systemów uczenia się reguł relacyjnych został opracowany przez Quinlan i nazywał się FOIL. Ponieważ wyuczone reguły mają tę samą formę, co instrukcje w języku komputerowym PROLOG (język oparty na logice), dziedzina poświęcona nauce tych reguł nazywa się " Indukcyjnym programowaniem logicznym"(ILP). Chociaż metody ILP wykorzystują aparat logiczny zbyt skomplikowany, bym mógł tu wyjaśnić, niektóre z nich mają ścisły związek z konstrukcją drzewa decyzyjnego. Istnieje kilka zastosowań ILP, w tym nauka zasad relacyjnych dla aktywność leku, w przypadku struktury drugorzędowej białka i projektowania siatki elementarnej. Są to wszystkie przykłady tego, co można nazwać "eksploracją danych relacyjnych"

Sieci neuronowe

W latach 60. XX wieku badacze sieci neuronowych stosowali różne metody zmiany regulowanych wag sieci, dzięki czemu cała sieć reagowała odpowiednio na zestaw danych wejściowych "szkoleniowych". Na przykład Frank Rosenblatt w Cornell skorygował wartości masy w warstwie końcowej tego, co nazwał trójwarstwowym perceptronem alfa. Bill Ridgway (jeden ze studentów Bernarda Widrowa ze Stanford) dostosował wagi w pierwszej warstwie, którą nazwał MADALINE. Mieliśmy podobny schemat dostosowywania ciężarów w pierwszej warstwie maszyn sieci neuronowych MINOS II i MINOS III w SRI. Inni stosowali różne techniki statystyczne do ustalania wartości masy. Ale wszystkim nam przeszkodziło to, jak zmienić wagi w więcej niż jednej warstwie sieci wielowarstwowych.

Algorytm Backprop

Problem ten został rozwiązany w połowie lat 80. XX wieku dzięki wynalezieniu techniki zwanej "propagacją wsteczną" (w skrócie backprop) wprowadzonej przez Davida Rumelharta, Geoffreya E. Hintona i Ronalda J. Williamsa. Podstawowa idea backprop jest prosta, ale matematyka (którą pominę) jest raczej skomplikowana. W odpowiedzi na błąd na wyjściu sieci, backprop dokonuje niewielkich korekt we wszystkich wagach, aby zmniejszyć ten błąd. Można ją traktować jako metodę wspinaczki (a raczej zejścia w dół)-szukanie niskich wartości błędu w krajobrazie ciężarów. Ale zamiast wypróbować wszystkie możliwe niewielkie zmiany masy i zdecydować, który zestaw odpowiada stromemu zjazdowi, backprop używa rachunku różniczkowego do obliczenia najlepszego zestawu zmian masy. Czytelnicy, którzy pamiętają trochę rachunku różniczkowego (lub być może liceum), nie będą mieli problemów z przypomnieniem sobie, że można go użyć do obliczenia nachylenia krzywej lub powierzchni. Błąd na wyjściu sieci neuronowej można traktować jako funkcję ciężaru sieci, to znaczy powierzchni w "przestrzeni wagowej". Tę funkcję można zapisać i "zróżnicować" (operację w rachunku różniczkowym) w odniesieniu do ciężarów, aby uzyskać zestaw zmian ciężaru, które poprowadzą nas w dół w najbardziej stromym kierunku. Problem z implementacją tego pomysłu w prosty sposób dla sieci neuronowych polega na tym, że sieci te mają "progi", których efektem jest wypełnienie powierzchni błędu nagłymi "klifami". (Wyjścia sieci z progami mogą zmieniać się z 1 na 0 lub z 0 na 1 z nieskończenie małymi zmianami niektórych wartości masy.) Operacje rachunku różniczkowego wymagają płynnie zmieniających się powierzchni i są frustrowane przez klify. Rumelhart i współpracownicy poradzili sobie z tym problemem, zastępując progi komponentami, których dane wyjściowe mogą zmieniać się tylko płynnie, mimo że zmieniają się dość gwałtownie, aby sieć mogła wykonać mniej więcej to samo co sieć z progami. Dzięki tym zamianom można zastosować rachunek różniczkowy i całkowy do propagacji funkcji błędu (od wyjścia do wejścia) w sieci, aby obliczyć najlepszy zestaw zmian wartości wagi we wszystkich warstwach sieci. Chociaż ten proces zerowania dopuszczalnych wartości masy jest powolny, został zastosowany z imponującymi wynikami w przypadku wielu problemów związanych z uczeniem się sieci neuronowej. Dlaczego o tym nie pomyśleliśmy? W rzeczywistości niektórzy ludzie najwyraźniej wymyślili podobny pomysł, zanim Rumelhart i jego koledzy to zrobili. Prawdopodobnie najwcześniej Arthur E. Bryson Jr. i Y. C. Ho zastosowali iteracyjne metody gradientu do rozwiązania równań Eulera -Lagrange′a. Paul Werbos, zaproponował również błędy propagacji wstecznej w celu trenowania wielowarstwowych sieci neuronowych. Podobnie jak w przypadku wszystkich lokalnych technik wyszukiwania, backprop może utknąć na jednym z lokalnych minimów powierzchni błędu. Oczywiście proces uczenia się można powtarzać, zaczynając od różnych wartości początkowych wag, aby spróbować znaleźć niższą (lub być może najniższą) wartość błędu. W każdym razie metoda backprop jest nadal, jak napisał Laveen Kanal w 1993 roku, prawdopodobnie najbardziej rozpowszechniona ogólna procedura szkolenia sieci neuronowych w zakresie klasyfikacji wzorców. "Metody uczenia sieci neuronowej zostały zastosowane w różnych obszarach, w tym w kontroli samolotów, wykrywaniu oszustw związanych z kartami kredytowymi, rozpoznawaniu waluty w automatach i eksploracji danych.

NETtalk

Jednym z bardzo interesujących zastosowań metody uczenia się z wykorzystaniem metody backprop było opracowane przez Terrence'a J. Sejnowskiego i Charlesa Rosenberga . Nauczyli sieci neuronowej mówić! W jednym ze swoich eksperymentów ich system, zwany NETtalk, nauczył się czytać tekst, który został przepisany z nieformalnej, ciągłej mowy sześcioletniego dziecka i wytwarzał dźwięk (brzmiał wyjątkowo jak u dziecka). Sieć miała 203 jednostek wejściowych zaprojektowanych do kodowania ciągu siedmiu list. Tekst był przesyłany strumieniowo przez te siedem jednostek litera po literze. Było 80 "ukrytych jednostek", które były podłączone do wejść za pomocą regulowanych obciążników. Spodziewano się, że ukryte jednostki będą tworzyć wewnętrzne reprezentacje odpowiednie do rozwiązania problemu odwzorowania liter na fonemy. "Były jednostki wyjściowe, które miały wytwarzać zakodowane wersje fonemów, podstawowe jednostki dźwięków mowy. Jednostki wyjściowe zostały połączone z ukrytymi jednostkami za pomocą dodatkowych regulowanych ciężarów. (Łącznie było 18 629 regulowanych ciężarów). W końcu kody fonemiczne zostały przekazane do komercyjnego syntezatora mowy w celu uzyskania słyszalnego sygnału wyjściowego. Sieć była szkolona przez porównywanie, za każdym razem, fonemiczny kod w jednostkach wyjściowych w stosunku do tego, jaki powinien być kod dla wprowadzania tekstu w tym kroku czasu. Backprop został użyty do zmodyfikowania wag w taki sposób, aby zmniejszyć ten błąd. Autorzy twierdzą, że "w ciągu kilku dni można było wytrenować sieć z siedmioliterowym oknem." (Pamiętaj, że komputery były znacznie wolniejsze w 1987 r.) Doszli do wniosku, że "ogólnie zrozumiałość mowy była całkiem dobra" i że "im więcej słów uczy się sieć, tym lepiej jest uogólniać i poprawnie wymawiać nowe słowa." Po treningu na korpusie 1024 słów sieć została przetestowana [bez dalszego szkolenia] na kontynuacji 439 słów od tego samego mówcy . Wydajność wyniosła 78%, co wskazuje, że duża część nauki została przeniesiona na nowe słowa nawet po małej próbce angielskich słów. "Oprócz określonej sieci przeprowadzono również eksperymenty w sieciach z bardziej ukrytymi z dwiema warstwami jednostek ukrytych. Ogólnie rzecz biorąc, większe sieci działały lepiej.

ALVINN

Kolejna aplikacja sieci neuronowej, ta do sterowania furgonetką, została opracowana przez doktora Deana Pomerleau, student Carnegie Mellon University. System, który obejmował furgonetkę, kamerę telewizyjną do patrzenia na drogę przed sobą oraz aparat interfejsu, nazywał się ALVINN, skrót od Autonomous Land Vehicle in a Neural Network. ALVINN wykorzystał pojazd CMU Navlab, który został zbudowany na podwoziu samochodu dostawczego z napędem hydraulicznym i elektrycznym układem kierowniczym. Według artykułu CMU: "Komputery mogą sterować i prowadzić furgonetkę za pomocą serwomechanizmów elektrycznych i hydraulicznych lub kierowca może przejąć kontrolę nad jazdą do miejsca testowego lub pominąć komputer". Dane wejściowe do sieci neuronowej ALVINN stanowiła tablica wartości natężenia obrazu w skali szarości 30x32 o niskiej rozdzielczości 30x32 wytwarzana przez kamerę wideo zamontowaną na dachu furgonetki. Każde z tych 960 wejść było podłączone do każdego z czterech ukrytych jednostek dzięki regulowanym ciężarkom. Z kolei jednostki ukryte zostały połączone z linią 30 jednostek wyjściowych od lewej do prawej za pomocą regulowanych wag. Jednostki wyjściowe sterowały mechanizmem sterującym furgonetki w następujący sposób: Środkowa jednostka wyjściowa reprezentuje warunek "jazdy na wprost", podczas gdy jednostki na lewo i prawo od środka reprezentują kolejno ostrzejsze skręty w lewo i prawo. Jednostki po skrajnej lewej i prawej stronie wektora wyjściowego reprezentują zwoje o promieniu 20 m odpowiednio w lewo i w prawo, a jednostki pomiędzy reprezentują zwoje, które zmniejszają się liniowo w swojej krzywiźnie do jednostki środkowej "na wprost".…Kierunek sterowania podyktowany przez sieć jest uważany za środek masy "wzgórza" aktywacji otaczającej jednostkę wyjściową o najwyższym poziomie aktywacji. Używając środka masy aktywacji zamiast najbardziej aktywnej jednostki wyjściowej podczas określania w ten sposób kierunku kierowania pozwala na korekty kierownicy dla poprawy dokładności jazdy ALVINN. Istnieją różne wersje ALVINN. W jednym szkolenie sieci było "w locie", co oznacza, że sieć była szkolona w czasie rzeczywistym, gdy van kierowany był przez ludzkiego kierowcę różnymi drogami i ścieżkami. Pożądany kąt skrętu został wybrany przez kierowcę, a ciężary sieci zostały skorygowane za pomocą korekcji tylnej, aby spróbować naśladować wydajność kierowcy. Jednym z problemów związanych z tą metodą było to, że sieć nigdy nie była narażona na możliwe obrazy "zejścia z drogi". Do zestawu treningowego dodano symulacje tego, jak wyglądałyby takie obrazy (oznaczone w tych przypadkach kątem skrętu). Podsumowując typowy test wydajności ALVINN, Pomerleau napisał:" Ponad trzy przebiegi, sieć jedzie z prędkością 5 mil na godzinę wzdłuż 100-metrowego odcinka testowego średnia pozycja pojazdu wynosiła 1,6 cm na prawo od środka, przy standardowym odchyleniu 7,2 cm. Pod kontrolą człowieka średnia pozycja pojazdu wynosiła 4,0 cm na prawo od środka, ze standardowym odchyleniem 5,47 cm."

Carnegie Mellon's Robotics Institute kontynuował (i nadal kontynuuje) prace nad pojazdami autonomicznymi, chociaż podejście sieci neuronowej do sterowania za pomocą obrazu zostało zastąpione przez bardziej niezawodne algorytmy widzenia komputerowego. Ich system postrzegania wizualnego RALPH z 1995 r. (Akronim oznaczający funkcję szybkiego dostosowywania pozycji bocznej) wykorzystywał specjalne procedury przetwarzania obrazu w celu określenia krzywizny granicy drogi. Według Pomerleau: "RALPH był w stanie zlokalizować drogę i samodzielnie kierować na różnych rodzajach dróg w wielu różnych warunkach. RALPH przejechał naszym pojazdem testowym Navlab 5 ponad 3000 mil po drogach od ścieżek rowerowych jednopasmowych, po wiejskie autostrady, do autostrad międzystanowych ". Latem 1995 r. Jeden z ich specjalnie wyprofilowanych pojazdów, Pontiac Trans Sport z 1990 r. (Navlab 5) przekazany przez Delco Electronics, kierował autonomicznie (za pomocą RALPH) na 2779 z 2849 mil z Pittsburgha do San Diego w Kalifornii. (Tylko kierowanie było autonomiczne {doktorant z Pomerleau i doktor Todd Jochem obsługiwał przepustnicę i hamulec.) Średnia prędkość wynosiła ponad 60 mil na godzinę

Uczenie się bez nadzoru

Drzewo decyzyjne i metody uczenia sieci neuronowej opisane do tej pory są przykładami "uczenia nadzorowanego", "rodzaju uczenia się, w którym próbuje się nauczyć klasyfikować dane z dużej próbki danych szkoleniowych, których klasyfikacje są znane." nadzór ", który kieruje uczeniem się w tych systemach, polega na informowaniu systemu o klasyfikacji każdej bazy danych w zestawie szkoleniowym. Jednak czasami możliwe jest zbudowanie użytecznych klasyfikacji danych na podstawie samych danych. Techniki do tego celu podlegają nagłówek "nauka bez nadzoru". Załóżmy , że mamy zestaw nieznakowanych punktów próbnych, takich jak te pokazane na rysunku



Czy można się czegoś nauczyć z takich danych? Po oględzinach widzimy, że punkty wydają się być rozmieszczone w trzech grupach. Być może każdy klaster zawiera punkty, które można uznać za należące do tej samej kategorii. Tak więc, gdybyśmy mogli automatycznie przetwarzać próbki danych w celu identyfikacji klastrów i granic między nimi, mielibyśmy metodę uczenia się bez nadzoru. Badacze AI zastosowali kilka metod identyfikacji klastrów próbek treningowych. Popularnym i łatwym do wyjaśnienia jest tak zwana metoda k-średnich. Działa poprzez powtarzanie następujących kroków:

1. Zainstaluj, być może w przypadkowych lokalizacjach, pewną liczbę, powiedzmy k, "poszukiwaczy klastrów" w przestrzeni próbek.
2. Dla każdego z tych osób poszukujących klastra zgrupuj próbki szkoleniowe, które są do niego bliższe niż dla innych osób poszukujących klastra.
3. Oblicz centroid ("środek ciężkości") każdej z tych grup próbek.
4. Przenieś każdego z poszukiwaczy gromad do środka ciężkości odpowiedniej grupy.
5. Powtarzaj te kroki, aż żadna osoba poszukująca klastra nie będzie musiała zostać ponownie przeniesiona.

Pod koniec tego procesu osoby poszukujące klastra będą znajdować się w środkach grup prób szkoleniowych, które można uznać za klastry lub oddzielne kategorie danych. Teraz, aby sklasyfikować jakiś nowy punkt danych, którego nie ma w zestawie szkoleniowym, po prostu obliczamy, do którego poszukiwacza klastra jest najbliżej. Proces zależy oczywiście od możliwości odgadnięcia liczby klastrów, k. Metody tego polegają na ogół na dostosowaniu ich liczby, tak aby punkty w klastrach były bliżej siebie niż odległości między klastrami. Statystycy i inni opracowali kilka metod grupowania danych, w tym wariacje związane z metodą k-średnich. Jedna wybitna technika AutoClass została opracowana przez Petera Cheesemana i współpracowników z NASA. Według strony internetowej o AutoClass, AutoClass pobiera bazę danych przypadków opisaną przez kombinację rzeczywistych i dyskretnych atrybutów i automatycznie wyszukuje naturalne klasy w tych danych. Nie trzeba mówić, ile klas jest obecnych ani jak wyglądają - wyciąga te informacje z samych danych. Klasy są opisane probabilistycznie, dzięki czemu obiekt może mieć częściowe członkostwo w różnych klasach, a definicje klas mogą się nakładać. AutoClass słynie z odkrycia nowej klasy gwiazd w podczerwieni. Odkrył także nowe klasy białek, intronów i innych wzorów w danych sekwencji DNA / białek. Istnieją nawet techniki, które można zastosować do danych nienumerycznych. Statystycy grupują wszystkie te metody (numeryczne i nienumeryczne) pod ogólnym nagłówkiem "analiza skupień". Podręcznik Dudy, Harta i Bociana zawiera obszerną dyskusję na temat uczenia się bez nadzoru (a także innych tematów w klasyfikacji danych).

Nauka wzmocnienia

Nauka optymalnych zasad

Istnieje inny styl uczenia się, który leży nieco pomiędzy odmianą nadzorowaną i nienadzorowaną. Przykładem może być nauka, które z kilku możliwych działań, na przykład, robot powinien wykonać na każdym etapie w ciągłej sekwencji doświadczeń, biorąc pod uwagę tylko ostateczny wynik wszystkich jego działań. Ekstremalnym przypadkiem byłaby nauka doskonałej gry w szachy, biorąc pod uwagę tylko informacje o wygranej lub przegranej pod koniec gry. Nie zbudowano jeszcze systemu, który mógłby nauczyć się grać w szachy w ten sposób, ale program może nauczyć się grać w backgammon w ten sposób i nauczyć się wykonywania innych interesujących zadań, takich jak kontrolowanie walki śmigłowców. Pożyczając terminy z psychologicznej teorii uczenia się, możemy nazwać informacje o wygranych lub przegranych (lub ogólnie informacje o dobrych lub złych wynikach) "nagrodą" lub "wzmocnieniem", a ten styl uczenia się nazywa się "uczeniem wzmacniającym" lub (czasami) "uczenie się metodą prób i błędów". Nauka wzmacniana ma długą i zróżnicowaną historię. Psycholog Edward L. Thorndike badał ten styl uczenia się na zwierzętach. W swojej książce "Reinforcement Learning: An Introduction", Richard S. Sutton i Andrew G. Barto , dwaj pionierzy tego pola, wspominają o kilku historycznych kamieniach milowych, w tym metodzie Arthura Samuela do uczenia się funkcji oceny w warcabach, wykorzystanie dynamicznych technik programowania Richarda Bellmana w optymalnej kontroli, system uczenia się metodą prób i błędów Johna Andreaea STeLLA, systemy uczenia Donalda Michie do gry w kółko i krzyżyk (MENACE) i równoważenia biegunów ( BOXE) oraz praca A. Harry'ego Klopfa nad neuronami hedonistycznymi. "Uczenie się przez wzmocnienie jest kolejną z tych subdyscyplin sztucznej inteligencji, która stała się wysoce techniczna i wielorozgałęziona. Spróbuję delikatnego i niematematycznego opisu tego, jak to działa. W najprostszym ustawienie, uczenie się ze wzmocnieniem polega na nauczeniu się przechodzenia przez zbiór stanów, przechodzenia od jednego stanu do drugiego itd., aby osiągnąć stan, w którym otrzymuje się nagrodę. Problem jest podobny do tego, z którym mierzy się szczur w nauce prowadzenia labiryntu (lub robota, z którym robot ma się zmierzyć podczas nauki jak wykonać zadanie). W rzeczywistości wykorzystajmy przykład labiryntu do opisania niektórych aspektów uczenia się przez wzmocnienie. Typowy labirynt pokazano tu



Problemem szczura jest przejście z pozycji początkowej do sera w pozycji bramkowej. Szare kropki mają na celu zobrazowanie sytuacji, w których szczur mógłby się znaleźć i rozpoznać. W terminologii uczenia wzmacniającego sytuacje te nazywane są "stanami". W każdym stanie szczur może wybierać spośród, powiedzmy, czterech działań, mianowicie skręć w lewo, skręć w prawo, idź do przodu lub do tyłu. W zależności od stanu możliwe są tylko niektóre działania - na przykład nie można iść naprzód, gdy stoi się w ślepym zaułku. Każde możliwe działanie przenosi szczura z jednego stanu do sąsiedniego w labiryncie. Zbiór stanów i łączące je działania można traktować jako wykres, podobny do tych, które omówiłem, gdy mówiłem o metodach wyszukiwania. Aby nie oddalić się zbytnio od tego, co wiadomo o prawdziwych szczurach biegnących w labiryncie, przejdźmy teraz do opisu, w jaki sposób funkcjonalny "robot-szczur" może nauczyć się prowadzić ten labirynt. Głównym problemem dla robota jest to, że zaczyna się od braku mapy labiryntu i nie ma pojęcia o skutkach swoich działań. Oznacza to, że dla każdego stanu, w którym się on znajduje, nie wie, które następne stany przyniosłyby dla różnych działań, które mógłby podjąć w tym stanie. Gdyby bowiem miał taką mapę, powiedzmy reprezentowaną przez wykres, mógłby przeszukać wykres (przy użyciu metody takiej jak A*) w celu znalezienia ścieżki do węzła celu. Jednym ze sposobów jest próba nauczenia się wykresu stanów i ich połączeń metodami prób i błędów, a następnie zastosowania metod wyszukiwania grafów, aby dowiedzieć się, jak poruszać się po labiryncie. Alternatywą i tą stosowaną w większości metod uczenia się przez zbrojenie jest nazywanie wszystkich stanów napotykanych przez robota, który błąka się losowo w poszukiwaniu celu. (Zakładamy, że ostatecznie osiągnie cel.) W terminologii uczenia się wzmacniającego "polityka" prowadzenia labiryntu łączy pewne pojedyncze działanie z każdym nazwanym stanem. Najlepsza lub "optymalna polityka" kojarzyłaby z każdym stanem to działanie, które prowadziłoby do najkrótszej (lub w inny sposób najmniej kosztownej) ścieżki przez labirynt. Uczenie się przez wzmocnienie polega na uczeniu się najlepszej polityki, a przynajmniej dobrej polityki. Jedną z metod uczenia się zasad jest powiązanie"wyceny " z każdą możliwą akcją w każdym stanie, a następnie dostosowując te liczby (w oparciu o doświadczenie), aż wskażą drogę do celu. Ta metoda nazywa się "Q-learning" i została pierwotnie zasugerowana przez Christophera Watkinsa w jego doktoracie na Uniwersytecie Cambridge. Teza,że Robot rozpoczyna proces uczenia się, przypisując nazwę do stanu, w którym się rozpoczyna, i przypisując losowo wybrane numery wyceny do każdej akcji, jaką może podjąć w tym stanie. Proces uczenia się rozszerzy tę tabelę, przypisując nazwy i numery wyceny wszystkich działań, które może podjąć w każdym napotkanym nowym stanie. (Zakładamy, że robot pamięta w swojej tabeli nazwy wszystkich stanów, które już odwiedził w procesie uczenia się, i odróżnia je od nowych stanów.) Stan początkowy robota, z losowo wybranym numerem wyceny przypisanym do jego jedynego działania możliwe, pokazano na szkicu po lewej stronie rysunku



Na każdym etapie procesu uczenia się robot podejmuje tę akcję, mając najwyższy numer wyceny. Ponieważ w początkowym stanie robota jest tylko jedna akcja, wykonuje ona tę czynność, wprowadza się w nowy stan i przypisuje losowe liczby wycen do możliwych akcji nowy stan. Ten krok pokazano na środkowym szkicu z rysunku powyżej. Teraz jest kluczowy krok w nauce. Ponieważ robot "teraz" wie, że może osiągnąć nowy stan, mając działania, których najwyższy numer wyceny to 6, aktualizuje numer wyceny, a mianowicie 3, akcji prowadzącej do tego stanu, dostosowując go do liczby bardziej spójnej z byciem jest w stanie podjąć działanie, które według niego jest warte 6. Aby uwzględnić "koszt" właśnie zakończonej akcji, dostosowanie 3 nie idzie aż do 6, ale tylko do 5, powiedzmy. Wynik pokazano na prawym szkicu z rysunku powyżej, na którym skorygowana wycena jest nieco większa niż inne liczby i zacieniowana i ten proces trwa. W każdym stanie podejmij działanie, którego numer wyceny jest największy, a następnie dostosuj ten numer wyceny, przybliżając jego wartość do wartości działania o najwyższym numerze wyceny we właśnie wprowadzonym stanie. I chociaż proces rozpoczyna się od losowo wybranych liczb wyceny, ostatecznie proces prób i błędów potknie się do stanu docelowego, w którym zostanie uzyskana wysoka "nagroda". Na tym etapie właśnie podjęta akcja, która doprowadziła do tego nagrody, ma wartość wyceny podniesioną do tej samej wartości (lub może nieco mniejszej) niż wartość nagrody.



Szkic po lewej stronie przyrządu pokazuje niektóre stany i wartości akcji w momencie, gdy robot podejmuje akcję, która osiąga cel. Na szkicu po prawej stronie przyrządu pokazuję skorygowaną wycenę (zacieniowaną) dla tego działania zmierzającego do osiągnięcia celu. Teraz po raz pierwszy , wycena akcji opiera się na zdobyciu nagrody, a nie jest ustalana losowo. Jeśli robot kiedykolwiek znajdzie się w stanie sąsiadującym ze stanem celu, z pewnością podejmie tę samą akcję. Co ważniejsze, kiedy osiągnie ten przedostatni stan w kolejnym doświadczeniu, propaguje tę wartość opartą na nagrodach wstecz.



Załóżmy, że na szkicu po lewej robot znajduje się w stanie zaznaczonym strzałką. Z tego stanu podejmuje tę akcję z największą wyceną, która prowadzi ją do stanu sąsiadującego z celem. Akcja o największej wycenie prowadzącej z tego stanu ma wycenę 99, więc wycena właśnie wykonanej akcji zmienia się z 11 na 98, jak pokazano na szkicu po prawej stronie. Zwiększenie wycen działań w stanach zbliżonych do celu poprzez propagację wsteczną powoduje, że stany te z natury "nagradzają" tak, jakby były stanami docelowymi. Bystry czytelnik może narzekać, że sprytnie ustawiłem "losowe" wartości wyceny na wartości, które doprowadziłyby do celu, gdy robot osiągnie stan zbliżony do celu. Co by było, gdyby wartości te były takie, jakie najprawdopodobniej byłyby, że po zbliżeniu się robot oddalił się od prawie osiągniętego celu? Jeśli liczby wyceny zostaną skorygowane zgodnie z zaleceniami, zawsze biorąc pod uwagę koszt ruchu, mała myśl przekona jednego, że ostatecznie liczby będą takie, aby zmusić robota do osiągnięcia celu, a wszystkie inne drogi ostatecznie zostaną zamknięte . Dzięki ciągłemu doświadczeniu wyceny działań związanych z osiąganiem celu stopniowo propagują się wstecz od celu. Ostatecznie, po wielu doświadczeniach związanych z próbami i błędami (i przy pewnych "uzasadnionych" założeniach), wartości będą zbieżne z tymi, które wdrażają optymalną politykę, to znaczy taką, która zawsze doprowadza robota do celu w najbardziej efektywny sposób. Większość wersji uczenia wzmacniającego ma następujące opracowania:

•  Nagrody mogą być przyznawane w więcej niż jednym stanie. Oznacza to, że niekoniecznie istnieje jeden cel, ale wiele stanów, które mogą przyczynić się do nagrody. Nagrody są reprezentowane przez wartości liczbowe, które mogą być dodatnie (prawdziwe "nagrody"), zero lub ujemne ("kary").
•  Zamiast próbować znaleźć zasadę, która odpowiada optymalnej śieżce do stanu jednego celu próbuje się nauczyć zasad, które maksymalizują oczekiwaną z czasem nagrodę. Zazwyczaj przy poznawaniu zasad nagrody oczekiwane w odległej przyszłości są "dyskontowane", co oznacza, że nie liczą się tak, jak nagrody oczekiwane od razu.
•  Każde działanie podjęte w danym stanie nie zawsze może prowadzić do tego samego stanu. Można próbować dowiedzieć się, jakie są prawdopodobieństwa, że niektóre działania podjęte w danym stanie prowadzą do tego, co robią inne stany i niektóre metody uczenia wzmacniającego, takie jak "zamiatanie priorytetowe". Proces uczenia się Q unika potrzeby wyraźnego poznania tych prawdopodobieństw, ponieważ niezależnie od tego, jakie one są, odpowiednio (wraz z nagrodami) odpowiednio wpływają na wartości, które proces uczenia przypisuje parom stan-działanie.
•  Kolejną komplikacją może być to, że robot ma niedoskonałą wiedzę o tym, w jakim jest stanie, ponieważ jego aparat sensoryczny nie jest wystarczająco dokładny ani informacyjny. W takim przypadku mówi się, że rzeczywisty stan, w którym znajduje się robot, jest "ukryty", co dodatkowo komplikuje problem uczenia się optymalnej polityki.

Dzięki tym opracowaniom problem staje się jednym z tzw. "Procesów decyzyjnych Markowa" (MDP). Ze względu na niedoskonałą wiedzę o stanie nazywa się to "częściowo obserwowalnym procesem decyzyjnym Markowa" (POMDP). MDP i POMDP zostały dobrze zbadane przez ludzi w teorii kontroli, a także w AI. Mogę użyć przykładu labiryntu robota, aby wspomnieć o kilku rzeczach, które są ważne w zastosowaniu uczenia wzmacniającego w praktycznych zastosowaniach. Po pierwsze, założyłem, że losowa eksploracja robota ostatecznie wyląduje w stanie celu. W złożonych problemach szansa na losowe osiągnięcie celu (lub innych nagród) może być niewielka do zera. Podział problemu na hierarchię podproblemów, w których nagrody są łatwiejsze do zdobycia, jest czasem wykorzystywany do przyspieszenia nauki. Dodatkowo można zastosować strategie "kształtowania", w których robot jest umieszczony w sytuacji wystarczająco blisko celu, aby losowa eksploracja znalazła cel. Następnie, po przypisaniu niektórym działaniom zbliżonym do celu ocen związanych z celem, sytuacje początkowe można stopniowo przesuwać coraz dalej od celu. Alternatywnie, można podać wskazówki, być może w postaci nagród pośrednich, aby dać robotowi znać, że radzi sobie dobrze. Takie strategie są wykorzystywane w nauczaniu umiejętności ludzi i zwierząt. Kolejny problem dotyczy kompromisu między "wykorzystywaniem" już wyuczonej polityki a "badaniem" w celu znalezienia lepszych polityk. Często zdarza się, że zestaw wycen czynności uzyskanych na wczesnym etapie procesu uczenia się może nie być najlepszym możliwym zestawem. Aby nauczyć się lepszego zestawu, należy w jakiś sposób zachęcić robota do losowego odstąpienia od znanej polityki, aby przejść do lepszego. Wreszcie, wiele problemów może mieć tak zwane "przestrzenie stanów" tak duże, że cały zestaw wszystkich stanów oraz ich działania i wyceny nie mogą być wyraźnie wymienione w tabeli takiej jak ta, którą założyłem dla problemu labiryntu robota. W takim przypadku wyceny działań, które można podjąć w danym stanie, muszą być obliczone, a nie zapisane.

TD-GAMMON

Jednym z najbardziej imponujących przykładów siły metod uczenia maszynowego jest system TD-GAMMON opracowany przez Geralda Tesauro w IBM. Wersje TD-GAMMON nauczyły się grać w świetnego tryktraka po graniu przeciwko sobie podczas milionów gier. TD-GAMMON zastosował kombinację uczenia sieci neuronowej i pewnego rodzaju uczenia wzmacniającego zwanego "uczeniem różnic czasowych" (co wyjaśnia pre TD ). Sieć neuronowa TD-GAMMON składała się z trzech warstw. W jednej wersji było 198 jednostek wejściowych, 40 jednostek ukrytych i 4 jednostki wyjściowe. Każda z jednostek wyjściowych może mieć wartość wyjściową od 0 do 1. Każde z wyjść miało za zadanie oszacowanie prawdopodobieństwa określonego wyniku gry. Cztery możliwe rozważane wyniki to białe wygrane, białe gammony, czarne wygrane lub czarne gammony. Jednostki wejściowe zostały zakodowane, aby reprezentować konfigurację elementów na płycie. Wartości czterech wyjść połączono, aby uzyskać liczbę dającą oszacowaną "wartość" pozycji płytki z punktu widzenia bieli. Po pierwsze, oto jak sieć została wykorzystana do wyboru ruch (zakładam tutaj, że czytelnik ma pewną znajomość trik-traka, ale mój opis powinien mieć sens nawet dla tych, którzy tego nie robią). Na każdym etapie gry rzuca się kostkami, a program bierze pod uwagę wszystkie możliwych ruchów, które mógłby wykonać, biorąc pod uwagę rzut kostką. Sieć oblicza wartość każdej możliwej wynikowej planszy, a program wybiera ruch produkujący planszę o najlepszej wartości (która jest najwyższą wartością, gdy jest to ruch białych i najniższa wartość, gdy jest ruch czarnego). Oto, jak sieć się uczy: Dla każdej pozycji planszy napotkanej podczas rzeczywistej gry wagi sieci są korygowane za pomocą backprop, dzięki czemu wartość obliczona dla tej pozycji planszy jest bliższa obliczonej wartości dla tymczasowej następnej pozycji na planszy (i dlatego widzimy, dlaczego pojawia się termin "różnica czasowa"). Sieć rozpoczyna się od losowo wybranych wartości masy, więc ruchy na początku procesu uczenia się, a także korekty wagi, są losowe. Ale ostatecznie nawet losowo wybrane ruchy powodują zwycięstwo jednego z graczy. Po wygranej znane są cztery wartości prawdopodobieństwa - jedna z nich to "1", a reszta to "0". Następnie można dopasować wagi sieci, aby wartość przedostatniej planszy była zbliżona do wartości tej ostatecznej, zwycięskiej pozycji na planszy. Podobnie jak we wszystkich procedurach uczenia się przy wzmocnieniu, wartości są stopniowo propagowane do tyłu od końca gry do pozycji wyjściowej. Po milionach gier wagi sieciowe przyjmują wartości, które prowadzą do eksperckiej gry. Komentując wersję TD-GAMMON, która oprócz uczenia się wykorzystuje również wyszukiwanie, Sutton i Barto napisali TD-GAMMON 3.0, który wydaje się być na poziomie lub bardzo blisko siły gry najlepszych ludzkich graczy na świecie. Może już być mistrzem świata. Programy te zmieniły już także sposób, w jaki grają najlepsi gracze. Na przykład TD-GAMMON nauczył się grać na niektórych pozycjach otwarcia inaczej niż było to w konwencji najlepszych graczy ludzkich. W oparciu o sukces TD-GAMMON i dalszą analizę, najlepsi ludzcy gracze zajmują teraz te pozycje, podobnie jak TD-GAMMON.

Inne zastosowania

Prawdopodobnie istnieją setki ważnych metod uczenia się przez wzmacnianie. Typowym, a zarazem dramatycznym przykładem jest praca Andrew Ng i jego grupy w Stanford nad nauką wykonywania akrobacyjnych manewrów śmigłowca. Inne zastosowania dotyczyły wysyłki wind, planowania warsztatów, zarządzania zużyciem energii i czworonożnych robotów kroczących. Jako ostatni komentarz na temat uczenia się wzmacniającego, warto zauważyć, że część technologii uczenia maszynowego, część, której nazwa została zapożyczona z psychologii, spłaca teraz swój dług, zapewniając teoretyczne ramy uczenia się mózgu zwierząt na poziomie neurofizjologicznym . W artykule w Journal of Neuroscience Christopher H. Donahue i Hyojung Seo napisali: Aby podejmować skuteczne decyzje podczas poruszania się w niepewnym otoczeniu, zwierzęta muszą rozwinąć zdolność do dokładnego przewidywania konsekwencji swoich działań. Uczenie się przez wzmocnienie stało się kluczowym teoretycznym paradygmatem pozwalającym zrozumieć, w jaki sposób zwierzęta dokonują tego wyczynu… Oprócz skutecznego przewidywania zachowania zwierząt przy wyborze, z powodzeniem wykorzystano model uczenia się wzmocnienia w celu wyjaśnienia funkcji zwojów podstawy w zachowaniu ukierunkowanym na cel. Wykazano, że neurony dopaminergiczne w brzusznym obszarze nakrywkowym i istocie czarnej kodują błąd przewidywania nagrody, który jest wykorzystywany do poprawy wyników przyszłych wyborów zwierzęcia. Inne badanie na małpach wykonujących zadanie wolnego wyboru wykazało, że aktywność neuronów prążkowia jest skorelowana z wartościami czynności, które zostały oszacowane poprzez zintegrowanie wcześniejszej historii wyników związanej z każdym działaniem

Ulepszenia

Wiele metod uczenia maszynowego, o których wspomniano, można ulepszyć na różne sposoby. Niektóre z nich opierają się na pracy statystów, a inne przez ludzi pracujących nad tzw. "Obliczeniową teorią uczenia się" .Jedna technika, zwana "bagging" (akronim od agregacji bootstrapu) jest zasługą profesora Leo Breimana z University of California, Berkeley. W przypadku problemów z klasyfikacją workowanie polega na łączeniu wyników pewnej liczby, powiedzmy m, oddzielnych klasyfikatorów. Każdy uczestnik jest szkolony przy użyciu innego podzbioru oryginalnego zestawu treningowego. Podzbiory te są uzyskiwane z oryginału przez losowe wybranie (z zastąpieniem) niektórych jego przykładów. (Statystycy nazywają te próbki "próbkami ładowania początkowego"). Po przeszkoleniu każdego z klasyfikatorów dokonuje się ostatecznej klasyfikacji większością głosów. Technikę tę można zastosować niezależnie od rodzaju zastosowanego indywidualnego klasyfikatora - sieci neuronowej, drzewa decyzyjnego, najbliższego sąsiada lub tego, co masz. Pakowanie można również zastosować do problemu powiązania liczby (zamiast kategorii) z przykładem. W takim przypadku wyniki są uśredniane, a nie uczestniczą w głosowaniu. Operacje głosowania i uśredniania pomagają uniknąć przesłonięcia danych, a tym samym dają lepszą wydajność, niż można by uzyskać przy jednym szkoleniu wszystkich klas na wszystkich danych. [Można się zastanawiać, jak można by poprawić wydajność sieci neuronowej MADALINE z lat 60, gdyby każda z jej jednostek progowych była szkolona na próbkach bootstrapu.] Podobny pomysł, zwany "boosting, został zaproponowany przez Roberta E. Schapire. Chociaż istnieje wiele wersji, tutaj w skrócie opisano, jak to działa. Korzystając z jednej z nadzorowanych metod uczenia maszynowego, uczący jest szkolony na oryginalnym zestawie szkoleniowym, w którym każda próbka jest jednakowo ważona. " (Masę i-tej próbki, powiedzmy w_i, można ustawić, na przykład, włączając tę próbkę w_i razy do zestawu treningowego.) Następnie budowany jest nowy zestaw treningowy, w którym próbki, które zostały błędnie sklasyfikowane, a ich "waga" została zwiększona, a dla próbek, które zostały prawidłowo sklasyfikowane, ich waga spadła. Korzystając z tego nowego zestawu szkoleniowego, trenowany jest inny uczestnik. (Ten przypuszczalnie będzie pracował ciężej na wcześniejszych błędnie sklasyfikowanych próbach.) Proces ten powtarza się, dopóki nie znajdziemy pewnej liczby, powiedzmy m, klasyfikatorów. Teraz każdy z klas głosuje nad kategoryzacją nowych próbek. Ich głosy ważone są w jaki sposób dobrze spisali się na oryginalnym zestawie treningowym. Głosy bardziej wiarygodnych klasyfikatorów liczą się bardziej niż głosy mniej wiarygodnych klasyfikatorów. Nawet gdy pierwotni klasyfikatorzy są "słabi" (to znaczy wcale niezbyt wiarygodni), ogólna dokładność połączonego zestawu m klasyfikatorów może być całkiem dobra, tym samym "poprawiając" wyniki. Zaproponowano kilka sposobów poprawy. Jeden z popularnych, z powodu Yoava Freunda i Roberta Schapire′a, nazywa się "Adaboost". Możliwe jest także łączenie workowania i boostingu. Na koniec wspomnę o "maszynach wektorowych wsparcia" (SVM). Pełny ich opis wymagałby więcej matematyki, niż chcielibyśmy tutaj zagłębić, ale mogę dać przybliżone i gotowe wyobrażenie o tym, jak działają na podstawie przykładu geometrycznego. Po lewej stronie ryc. 29.17 pokazuję te same punkty które ilustrowały granicę oddzielającą w przestrzeni cech.



Punkty oznaczone małymi kwadratami odpowiadają próbkom z jednej kategorii, a punkty oznaczone małymi kółkami odpowiadają próbkom z innej kategorii. Przypominamy, że punkty na diagramach mają współrzędne równe cechom, f₁ i f₂, obliczonym z elementów (takich jak dźwięki mowy, obrazy lub inne dane), które chcemy sklasyfikować. Zdarza się w tym przypadku, że istnieje wiele linii prostych (to znaczy liniowych), które oddzielą punkty w dwóch kategoriach. Dlatego próba wyszkolenia elementu neuronowego w celu klasyfikacji punktów (uważana za "próbki treningowe") zakończy się powodzeniem. Gdybyśmy użyli standardowej procedury korekcji błędów do treningu, z pewnością uzyskalibyśmy pewną granicę liniową, ale w przypadku maszyn SVM wymagamy więcej granicy niż tylko oddzielenie próbek treningowych. Chcemy, aby odległości (zwane "marginesem") od najbliższych punktów przeciwnych kategorii były jak największe. Taka liniowa granica jest pokazana po prawej stronie powyższego rysunku. Równoległe linie przerywane po obu stronach przechodzą przez te najbliższe punkty, które są nazywane "wektorami wspierającymi". Pożądane są granice z możliwie największymi marginesami, ponieważ lepiej klasyfikują nowe punkty, których nie ma w zestawie treningowym. Oznacza to, że mają lepsze właściwości "uogólniające". Wczesna praca nad rozpoznawaniem wzorców (nadzorowanej odmiany uczenia się) w SRI obejmowała pewne eksperymenty, w których próbowaliśmy znaleźć granice izolowane od próbek szkoleniowych. Jedna z metod tego polegała na szkoleniu próbek pochodzących z oryginalnych poprzez dodanie do nich niewielkiej ilości "hałasu". Chodziło o to, aby procedura szkolenia z korekcją błędów zastosowana do tego rozszerzonego zestawu została wyparta z oryginalnych próbek. Bardziej elegancka metoda została zaproponowana przez H. Glucksmana, w której trening korekcji błędów trwał do momentu osiągnięcia minimalnej dozwolonej odległości między próbkami treningowymi a granicami oddzielenia. Jednak aby zapewnić możliwie duże marginesy, konieczne są złożone procedury optymalizacji. Teraz możesz zapytać , jak uzyskać przestrzenie cech, które można liniowo oddzielić? Jednym ze sposobów jest użycie czegoś w rodzaju alfa-perceptronu Rosenblatta. Przypomnijmy, że elementy w pierwszej warstwie elementów progowych alfa-perceptronu, powiedzmy N z nich, każdy otrzymały swój własny wkład z losowej kolekcji pomiarów danych (takich jak piksele lub wartości fali mowy). Wyjścia binarne tych "jednostek asocjacyjnych" (jak nazywano te elementy pierwszej warstwy) były wówczas cechami podobnymi do tych, których użyłem w dwuwymiarowym przykładzie. Określili punkty w N-wymiarowej przestrzeni cech, którą (miał nadzieję Rosenblatt) można było rozdzielić liniowo. Często były to prace Rosenblatta. Osoby pracujące z SVM używają różnych metod definiowania funkcji. Ich metoda zapewnia, że wynikowa przestrzeń cech jest liniowo rozdzielalna (a przynajmniej prawie tak). Ich funkcje obejmują użycie tego, co nazywają "jądrem", a maszyny korzystające z takich funkcji nazywane są "urządzeniami jądra". Ponownie matematyka jest zbyt złożona, aby ją tu opisać, ale zainteresowany czytelnik może spojrzeć na książkę Nello Cristianiniego i John Shawe-Taylor: Jak wskazuje ta książka, historia matematyki prowadzącej do maszyn jądra i maszyn SVM sięga początków XX wieku i angażowała ludzi w teorię optymalizacji, statystyki i teorię uczenia obliczeniowego. a maszyny jądra są doskonałymi przykładami tego, w jaki sposób praca w kilku dyscyplinach, przy użyciu wysoce technicznego aparatu matematycznego, przyczyniła się do powstania nowych, zaawansowanych technik w sztucznej inteligencji. Ważnymi miejscami opisywania nowej pracy w uczeniu maszynowym są sponsorowane przez Neural Information Processing Systems (NIPS) konferencje corocznie przez Fundację Neural Information Processing Systems Foundation, po wysłuchaniu wszystkich opisanych w nim metod uczenia maszynowego rozdział, możesz rozsądnie zapytać, która metoda jest najlepsza? Należy zastosować metodę najbliższego sąsiada, drzewo decyzyjne, sieć neuronową lub coś takiego jeszcze?