Perceptron - Perceptron

W uczenia maszynowego The perceptron jest algorytm uczenia nadzorowanego z klasyfikatorów binarnych . Klasyfikator binarny to funkcja, która może decydować, czy dane wejściowe, reprezentowane przez wektor liczb, należy do określonej klasy. Jest to rodzaj klasyfikatora liniowego , czyli algorytmu klasyfikacji, który dokonuje swoich predykcji na podstawie funkcji predyktora liniowego łączącego zbiór wag z wektorem cech .

Historia

Maszyna Mark I Perceptron, pierwsza implementacja algorytmu perceptron. Połączono go z kamerą z fotokomórkami z siarczku kadmu 20×20, aby uzyskać 400-pikselowy obraz. Główną widoczną cechą jest panel krosowy, który ustawia różne kombinacje funkcji wejściowych. Po prawej stronie tablice potencjometrów, które zaimplementowały wagi adaptacyjne.

Algorytm perceptronu został wynaleziony w 1958 roku w Cornell Aeronautical Laboratory przez Franka Rosenblatta , finansowanym przez United States Office of Naval Research .

Perceptron miał być maszyną, a nie programem, i chociaż jego pierwsza implementacja była w oprogramowaniu dla IBM 704 , została następnie zaimplementowana w niestandardowym sprzęcie jako „perceptron Mark 1”. Ta maszyna została zaprojektowana do rozpoznawania obrazów : miała tablicę 400 fotokomórek , losowo połączonych z „neuronami”. Wagi kodowane były w potencjometrach , a aktualizacje wag w trakcie uczenia wykonywały silniki elektryczne.

Na konferencji prasowej zorganizowanej przez marynarkę wojenną Stanów Zjednoczonych w 1958 r. Rosenblatt wypowiedział się na temat perceptronu, który wywołał gorące kontrowersje wśród raczkującej społeczności AI ; opierając się na oświadczeniach Rosenblatta, The New York Times donosi, że perceptron jest „embrionem elektronicznego komputera, który, według marynarki wojennej, będzie w stanie chodzić, mówić, widzieć, pisać, reprodukować się i być świadomym swojego istnienia”.

Chociaż początkowo perceptron wydawał się obiecujący, szybko udowodniono, że perceptronów nie można wytrenować w rozpoznawaniu wielu klas wzorców. Spowodowało to stagnację w dziedzinie badań nad sieciami neuronowymi na wiele lat, zanim uznano, że sprzężone do przodu sieci neuronowe z dwiema lub więcej warstwami (zwane również wielowarstwowymi perceptronami ) mają większą moc przetwarzania niż perceptrony z jedną warstwą (zwane również jednowarstwowymi). perceptron warstwowy ).

Perceptrony jednowarstwowe są zdolne do uczenia się tylko liniowo rozdzielonych wzorów. W przypadku zadania klasyfikacji z pewną funkcją aktywacji kroku, pojedynczy węzeł będzie miał pojedynczą linię dzielącą punkty danych tworzące wzorce. Więcej węzłów może tworzyć więcej linii podziału, ale te linie muszą w jakiś sposób zostać połączone, aby utworzyć bardziej złożone klasyfikacje. Druga warstwa perceptronów, a nawet węzłów liniowych, wystarcza do rozwiązania wielu problemów, których nie da się rozdzielić.

W 1969 roku słynna książka zatytułowana Perceptrons autorstwa Marvina Minsky'ego i Seymour Paperta wykazała, że nie jest możliwe, aby te klasy sieci nauczyły się funkcji XOR . Często uważa się (niesłusznie), że przypuszczono również, że podobny wynik miałby zastosowanie dla wielowarstwowej sieci perceptronowej. Nie jest to jednak prawdą, ponieważ zarówno Minsky, jak i Papert wiedzieli już, że wielowarstwowe perceptrony są w stanie wytworzyć funkcję XOR. (Patrz strona o Perceptronach (książka), aby uzyskać więcej informacji.) Niemniej jednak często mylony tekst Minsky/Papert spowodował znaczny spadek zainteresowania i finansowania badań sieci neuronowych. Minęło dziesięć lat, zanim badania sieci neuronowych doświadczyły odrodzenia w latach 80. XX wieku. Ten tekst został przedrukowany w 1987 roku jako „Perceptrons - Extended Edition”, gdzie pokazano i poprawiono niektóre błędy w oryginalnym tekście.

Jądra perceptronowa algorytm został już wprowadzony w 1964 roku przez Aizerman et al. Gwarancje granic marginesu zostały podane dla algorytmu Perceptron w ogólnym nierozłącznym przypadku najpierw przez Freunda i Schapire (1998), a ostatnio przez Mohri i Rostamizadeh (2013), którzy rozszerzają poprzednie wyniki i podają nowe granice L1.

Perceptron to uproszczony model neuronu biologicznego . Podczas gdy złożoność biologicznych modeli neuronów jest często wymagana do pełnego zrozumienia zachowania neuronów, badania sugerują, że liniowy model podobny do perceptronu może wytworzyć pewne zachowanie obserwowane w prawdziwych neuronach.

Definicja

W nowoczesnym sensie perceptron jest algorytmem uczenia klasyfikatora binarnego zwanego funkcją progową : funkcją, która mapuje swoje wejście ( wektor o wartości rzeczywistej ) na wartość wyjściową (pojedynczą wartość binarną ): $\mathbf {x}$ $f(\mathbf {x} )$

{\ Displaystyle f (\ mathbf {x} ) = {\ zacząć {przypadki} 1 i {\ tekst {jeśli}} \ \ mathbf {w} \ cdot \ mathbf {x} + b> 0, \ \ 0 i {\ tekst {w przeciwnym razie}}\end{przypadki}}}

gdzie jest wektorem wag o wartościach rzeczywistych, jest iloczynem skalarnym , gdzie $m$ jest liczbą wejść do perceptronu, a $b$ jest odchyleniem . Obciążenie przesuwa granicę decyzji z dala od źródła i nie zależy od żadnej wartości wejściowej. $\mathbf {w}$ ${\ Displaystyle \ mathbf {w} \ cdot \ mathbf {x}}$ ${\ Displaystyle \ suma _ {i = 1} ^ {m} w_ {i} x_ {i}}$

Wartość (0 lub 1) jest używana do klasyfikacji jako dodatnia lub ujemna instancja w przypadku problemu z klasyfikacją binarną. Jeśli $b$ jest ujemne, to ważona kombinacja danych wejściowych musi dawać dodatnią wartość większą niż w celu wypchnięcia neuronu klasyfikatora powyżej progu 0. Przestrzennie nastawienie zmienia położenie (choć nie orientację) granicy decyzyjnej . Algorytm uczenia perceptronu nie kończy się, jeśli zbiór uczący nie jest liniowo separowany . Jeśli wektory nie są liniowo separowalne, uczenie nigdy nie osiągnie punktu, w którym wszystkie wektory zostaną prawidłowo sklasyfikowane. Najbardziej znanym przykładem niezdolności perceptronu do rozwiązywania problemów z wektorami nierozdzielnymi liniowo jest problem wyłączności logicznej lub . W odnośniku badane są przestrzenie rozwiązań granic decyzyjnych dla wszystkich funkcji binarnych i zachowań uczenia się. $f(\mathbf {x} )$ $\mathbf {x}$ $|b|$

W kontekście sieci neuronowych perceptron jest sztucznym neuronem wykorzystującym funkcję kroku Heaviside'a jako funkcję aktywacji. Algorytm perceptronu jest również nazywany perceptronem jednowarstwowym , aby odróżnić go od perceptronu wielowarstwowego , który jest mylący dla bardziej skomplikowanej sieci neuronowej. Jako klasyfikator liniowy, perceptron jednowarstwowy jest najprostszą siecią neuronową ze sprzężeniem do przodu .

Algorytm uczenia

Poniżej znajduje się przykład algorytmu uczenia dla perceptronu jednowarstwowego. W przypadku perceptronów wielowarstwowych , w których istnieje warstwa ukryta, należy zastosować bardziej wyrafinowane algorytmy, takie jak propagacja wsteczna . Jeżeli funkcja aktywacji lub leżący u jej podstaw proces modelowany przez perceptron jest nieliniowy , alternatywne algorytmy uczenia , takie jak reguła delta , mogą być stosowane , o ile funkcja aktywacji jest różniczkowalna . Niemniej jednak algorytm uczenia opisany w poniższych krokach często będzie działał, nawet dla wielowarstwowych perceptronów z nieliniowymi funkcjami aktywacji.

Kiedy wiele perceptronów jest połączonych w sztucznej sieci neuronowej, każdy neuron wyjściowy działa niezależnie od wszystkich pozostałych; w ten sposób uczenie się każdego wyniku można rozpatrywać oddzielnie.

Definicje

Najpierw definiujemy kilka zmiennych:

r jest szybkością uczenia się perceptronu. Szybkość uczenia się wynosi od 0 do 1, większe wartości powodują, że zmiany wagi są bardziej zmienne.
${\ Displaystyle y = f (\ mathbf {z} )}$ oznacza wyjście z perceptronu dla wektora wejściowego . $\mathbf {z}$
${\ Displaystyle D = \ {(\ mathbf {x} _ {1}, d_ {1}), \ kropki, (\ mathbf {x} _ {s}, d_ {s}) \}}$ ${\ Displaystyle D = \ {(\ mathbf {x} _ {1}, d_ {1}), \ kropki, (\ mathbf {x} _ {s}, d_ {s}) \}}$ Jest to zestaw treningowy z próbek, gdzie: $s$ $s$
- ${\ Displaystyle \ mathbf {x} _ {j}}$ jest -wymiarowym wektorem wejściowym. ${\ Displaystyle n}$
- $d_{j}$ jest pożądaną wartością wyjściową perceptronu dla tego wejścia.

Wartości cech przedstawiamy w następujący sposób:

$x_{j,i}$ jest wartością th cechy trenującego wektora wejściowego . $i$ ${\ Displaystyle j}$
$x_{j,0}=1$ .

Aby przedstawić wagi:

$w_{i}$ jest th wartością w wektorze wag , która ma być pomnożona przez wartość th cechy wejściowej. $i$ $i$
Ponieważ , jest to faktycznie odchylenie , którego używamy zamiast stałej odchyłki . $x_{j,0}=1$ $w_{0}$ $b$

Aby pokazać zależność czasową , używamy: $\mathbf {w}$

${\ Displaystyle w_ {i} (t)}$ to waga w czasie . $i$ $t$

Kroki

Zainicjuj wagi. Wagi mogą być inicjowane na 0 lub na małą wartość losową. W poniższym przykładzie używamy 0.
Dla każdego przykładu j w naszym zbiorze uczącym D wykonaj następujące kroki na wejściu i żądanym wyjściu : ${\ Displaystyle \ mathbf {x} _ {j}}$ ${\mathbf {x}}_{j}$ $d_{j}$ $d_{j}$
1. Oblicz rzeczywistą wydajność:
  ${\ Displaystyle {\ zacząć {wyrównany} y_ {j} (t) i = f [\ mathbf {w} (t) \ cdot \ mathbf {x} _ {j}] \ \ & = f [w_ {0} (t)x_{j,0}+w_{1}(t)x_{j,1}+w_{2}(t)x_{j,2}+\dotsb +w_{n}(t)x_{ j,n}]\end{wyrównany}}}$
2. Zaktualizuj wagi:
  ${\ Displaystyle w_ {i} (t + 1) = w_ {i} (t) \; {\ pogrubiony symbol {+}} \; r \ cdot (d_ {j}-y_ {j} (t)) x_ { j,i}}$ , dla wszystkich funkcji , to współczynnik uczenia się . $0\leq i\leq n$ ${\ Displaystyle r}$
W przypadku uczenia w trybie offline , drugi etap może być powtarzany, aż błąd iteracji jest mniejszy niż próg błędu określony przez użytkownika lub została zakończona z góry określona liczba iteracji, gdzie s jest ponownie wielkością zestawu próbek. ${\ Displaystyle {\ Frac {1} {s}} \ suma _ {j = 1} ^ {s} | d_ {j}-y_ {j} (t) |}$ ${\ Displaystyle \ gamma}$

Algorytm aktualizuje wagi po krokach 2a i 2b. Te wagi są natychmiast stosowane do pary w zestawie uczącym, a następnie aktualizowane, zamiast czekać, aż wszystkie pary w zestawie uczącym przejdą te etapy.

Diagram przedstawiający perceptron aktualizujący swoją granicę liniową w miarę dodawania kolejnych przykładów treningowych

Do danych wejściowych przypisywane są odpowiednie wagi, a wynikowa suma ważona jest przekazywana do funkcji, która generuje wynik o.

Konwergencja

Perceptron jest klasyfikatorem liniowym , dlatego nigdy nie osiągnie stanu z wszystkimi wektorami wejściowymi poprawnie sklasyfikowanymi, jeśli zbiór $uczący D$ nie jest liniowo separowalny , tj. jeśli przykłady pozytywne nie mogą być oddzielone od przykładów negatywnych przez hiperpłaszczyznę. W takim przypadku, w ramach standardowego algorytmu uczenia się, żadne „przybliżone” rozwiązanie nie będzie stopniowo stosowane, ale zamiast tego uczenie się całkowicie zawiedzie. Stąd, jeśli liniowa rozdzielność zbioru uczącego nie jest znana a priori, należy zastosować jeden z poniższych wariantów uczących.

Jeśli zbiór treningowy jest liniowo separowany, wtedy perceptron ma gwarancję zbieżności. Ponadto istnieje górna granica tego, ile razy perceptron dostosuje swoje ciężary podczas treningu.

Załóżmy , że wektory wejściowe z tych dwóch klas mogą być oddzielone hiperpłaszczyzną z marginesem , tzn. istnieje wektor wagowy i termin odchylenia $b$ taki , że dla wszystkich z i dla wszystkich z , gdzie jest pożądana wartość wyjściowa perceptronu do wprowadzania danych . Niech $R$ oznacza również maksymalną normę wektora wejściowego. Novikoff (1962) udowodnił, że w tym przypadku algorytm perceptronu jest zbieżny po dokonaniu aktualizacji. Ideą dowodu jest to , że wektor wag jest zawsze dostosowywany o określoną wielkość w kierunku , w którym ma ujemny iloczyn skalarny , a zatem może być ograniczony powyżej przez $O$ $($ $\sqrt$ $t$ $)$ , gdzie $t$ jest liczbą zmian wektor wagi. Jednak może być również ograniczony poniżej przez $O$ $($ $t$ $),$ ponieważ jeśli istnieje (nieznany) zadowalający wektor wag, to każda zmiana powoduje postęp w tym (nieznanym) kierunku o wartość dodatnią, która zależy tylko od wektora wejściowego. ${\ Displaystyle \ gamma}$ ${\ Displaystyle \ mathbf {w} , | | \ mathbf {w} | | = 1}$ ${\ Displaystyle \ mathbf {w} \ cdot \ mathbf {x} _ {j}> \ gamma}$ ${\ Displaystyle j}$ $d_{j}=1$ ${\ Displaystyle \ mathbf {w} \ cdot \ mathbf {x} _ {j} <- \ gamma}$ ${\ Displaystyle j}$ ${\ Displaystyle d_ {j} = 0}$ $d_{j}$ ${\ Displaystyle j}$ ${\ Displaystyle O (R ^ {2} / \ gamma ^ {2})}$

Dwie klasy punktów i dwie z nieskończenie wielu granic liniowych, które je rozdzielają. Mimo że granice są względem siebie niemal pod kątem prostym, algorytm perceptronu nie ma możliwości wyboru między nimi.

Podczas gdy algorytm perceptronu gwarantuje zbieżność do jakiegoś rozwiązania w przypadku liniowo separowalnego zbioru treningowego, może on nadal wybierać dowolne rozwiązanie, a problemy mogą dopuszczać wiele rozwiązań o różnej jakości. Perceptronowa optymalnej stabilności , obecnie znany jako liniowej maszyny oporowo-wektor , zaprojektowana w celu rozwiązania tego problemu (Krauth i Mezard, 1987).

Warianty

Algorytm kieszonkowy z mechanizmem zapadkowym (Gallant, 1990) rozwiązuje problem stabilności uczenia się perceptronu, utrzymując najlepsze dotychczas widziane rozwiązanie „w kieszeni”. Następnie algorytm kieszeni zwraca rozwiązanie w kieszeni, a nie ostatnie rozwiązanie. Może być również stosowany do nierozłącznych zbiorów danych, gdzie celem jest znalezienie perceptronu z niewielką liczbą błędnych klasyfikacji. Jednak rozwiązania te pojawiają się czysto stochastycznie i dlatego algorytm kieszonkowy ani nie zbliża się do nich stopniowo w trakcie uczenia, ani nie ma gwarancji, że pojawią się w określonej liczbie kroków uczenia.

Algorytm Maxovera (Wendemuth, 1995) jest „solidny” w tym sensie, że będzie zbieżny niezależnie od (wcześniejszej) wiedzy o liniowej separowalności zbioru danych. W przypadku liniowo rozdzielnym rozwiąże problem treningowy – w razie potrzeby nawet przy optymalnej stabilności ( maksymalny margines między zajęciami). W przypadku nierozłącznych zestawów danych zwróci rozwiązanie z niewielką liczbą błędnych klasyfikacji. We wszystkich przypadkach algorytm stopniowo zbliża się do rozwiązania w trakcie uczenia, bez zapamiętywania stanów poprzednich i bez skoków stochastycznych. Konwergencja to globalna optymalność dla separowalnych zbiorów danych i lokalna optymalność dla nierozłącznych zbiorów danych.

Głosowany perceptron (Freund i Schapire, 1999) jest wariantem wykorzystującym wiele perceptronów ważonych. Algorytm uruchamia nowy perceptron za każdym razem, gdy przykład jest błędnie sklasyfikowany, inicjując wektor wag końcowymi wagami ostatniego perceptronu. Każdemu perceptronowi zostanie również przypisana inna waga odpowiadająca liczbie przykładów prawidłowo zaklasyfikowanych przed błędną klasyfikacją jednego, a na końcu wynikiem będzie ważony głos na wszystkie perceptrony.

W problemach rozdzielnych trening perceptronowy może również mieć na celu znalezienie największego marginesu oddzielającego między zajęciami. Tak zwany perceptron optymalnej stabilności można określić za pomocą iteracyjnych schematów treningu i optymalizacji, takich jak algorytm Min-Over (Krauth i Mezard, 1987) lub AdaTron (Anlauf i Biehl, 1989)). AdaTron wykorzystuje fakt, że odpowiedni problem optymalizacji kwadratowej jest wypukły. Perceptron optymalnej stabilności wraz ze sztuczką jądra stanowią koncepcyjne podstawy maszyny wektorów nośnych .

-Perceptron ponadto stosować do wstępnego przetwarzania warstwy stałych losowych wag, z progowaniu zespołów wyjściowych. Umożliwiło to perceptronowi klasyfikację wzorców analogowych poprzez rzutowanie ich na przestrzeń binarną . W rzeczywistości, dla przestrzeni projekcyjnej o wystarczająco dużym wymiarze, wzory mogą stać się liniowo rozdzielone. ${\ Displaystyle \ alfa}$

Innym sposobem rozwiązywania problemów nieliniowych bez użycia wielu warstw jest użycie sieci wyższego rzędu (jednostka sigma-pi). W tego typu sieci każdy element w wektorze wejściowym jest rozszerzany o każdą kombinację par zwielokrotnionych wejść (drugiego rzędu). Można to rozszerzyć na sieć n- order.

Należy jednak pamiętać, że najlepszym klasyfikatorem niekoniecznie jest ten, który doskonale klasyfikuje wszystkie dane treningowe. Rzeczywiście, gdybyśmy mieli wcześniejsze ograniczenie, że dane pochodzą z równowariantowych rozkładów Gaussa, liniowa separacja w przestrzeni wejściowej jest optymalna, a rozwiązanie nieliniowe jest przesadnie dopasowane .

Inne algorytmy klasyfikacji liniowej obejmują Winnow , maszynę wektora nośnego i regresję logistyczną .

Perceptron wieloklasowy

Podobnie jak większość innych technik uczenia klasyfikatorów liniowych, perceptron w naturalny sposób uogólnia klasyfikację wieloklasową . Tutaj dane wejściowe i wyjściowe są rysowane z dowolnych zestawów. Funkcja reprezentacji cech odwzorowuje każdą możliwą parę wejścia/wyjścia na skończenie wymiarowy wektor cech o wartościach rzeczywistych. Tak jak poprzednio wektor cech jest mnożony przez wektor wagi , ale teraz wynikowy wynik jest używany do wyboru spośród wielu możliwych wyników: $x$ $y$ $f(x,y)$ $w$

{\ Displaystyle {\ kapelusz {y}} = \ operatorname {argmax} _ {y} f (x, y) \ cdot w.}

Ponowne uczenie się powtarza przykłady, przewidując wynik dla każdego z nich, pozostawiając wagi niezmienione, gdy przewidywany wynik pasuje do celu, i zmieniając je, gdy tak nie jest. Aktualizacja staje się:

{\ Displaystyle w_ {t + 1} = w_ {t} + f (x, y)-f (x {\ kapelusz {y}}).}

Ta wieloklasowa formuła sprzężenia zwrotnego redukuje się do oryginalnego perceptronu, gdy jest wektorem o wartościach rzeczywistych, jest wybrany spośród , i . $x$ $y$ ${\ Displaystyle \ {0,1 \}}$ $f(x,y)=yx$

W przypadku niektórych problemów reprezentacje wejścia/wyjścia i funkcje mogą być wybrane tak, aby można je było skutecznie znaleźć, nawet jeśli są wybierane z bardzo dużego lub nawet nieskończonego zestawu. ${\ Displaystyle \ operatorname {argmax} _ {y} f (x, y) \ cdot w}$ $y$

Od 2002 roku trening perceptronowy stał się popularny w dziedzinie przetwarzania języka naturalnego dla takich zadań, jak znakowanie części mowy i parsowanie składniowe (Collins, 2002). Został również zastosowany do problemów z uczeniem maszynowym na dużą skalę w środowisku przetwarzania rozproszonego .

Bibliografia

Dalsza lektura

Aizerman, MA i Braverman, EM i Lew I. Rozonoer. Podstawy teoretyczne metody funkcji potencjału w uczeniu rozpoznawania wzorców. Automatyka i zdalne sterowanie, 25:821-837, 1964.
Rosenblatt, Frank (1958), Perceptron: probabilistyczny model przechowywania i organizacji informacji w mózgu , Cornell Aeronautical Laboratory, Psychological Review, v65, nr 6, s. 386-408. doi : 10.1037/h0042519 .
Rosenblatt, Frank (1962), Zasady neurodynamiki. Waszyngton, DC: Spartan Books.
Minsky ML i Papert SA 1969. Perceptrony . Cambridge, MA: MIT Press.
Gallant, SI (1990). Algorytmy uczenia oparte na perceptronie. Transakcje IEEE w sieciach neuronowych, tom. 1, nie. 2, s. 179–191.
Mohri, Mehryar i Rostamizadeh, Afshin (2013). Ograniczenia błędów perceptronu arXiv:1305.0208, 2013.
Novikoff, AB (1962). O dowodach zbieżności na perceptronach. Sympozjum na temat matematycznej teorii automatów, 12, 615-622. Instytut Politechniczny Brooklynu.
Widrow, B. , Lehr, MA, „ 30 lat Adaptive Neural Networks: Perceptron, Madaline and Backpropagation ”, Proc. IEEE , t. 78, nr 9, s. 1415–1442, (1990).
Collins, M. 2002. Metody treningu dyskryminacyjnego dla ukrytych modeli Markowa: Teoria i eksperymenty z algorytmem perceptronu w Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP '02).
Yin, Hongfeng (1996), algorytmy i analizy oparte na perceptronie, biblioteka widma, Concordia University, Kanada

Languages

In other projects