Perceptron jądra

W uczeniu maszynowym perceptron jądra jest wariantem popularnego algorytmu uczenia się perceptronu , który może uczyć się maszyn jądra , tj. nieliniowych klasyfikatorów wykorzystujących funkcję jądra do obliczania podobieństwa próbek niewidocznych do próbek uczących. Algorytm został wynaleziony w 1964 roku, co czyni go pierwszym uczącym się klasyfikacji jądra.

Czynności wstępne

Algorytm perceptronu

Główny artykuł: Perceptron

Algorytm perceptronu to algorytm uczenia się online , który działa na zasadzie „uczenia się opartego na błędach”. Iteracyjnie ulepsza model, uruchamiając go na próbkach treningowych, a następnie aktualizując model, gdy stwierdzi, że dokonał nieprawidłowej klasyfikacji w odniesieniu do nadzorowanego sygnału. Model wyuczony przez standardowy algorytm perceptronu to liniowy klasyfikator binarny: wektor wag w (i opcjonalnie składnik przecięcia b , pominięty tutaj dla uproszczenia), który jest używany do klasyfikowania przykładowego wektora x jako klasa „jeden” lub klasa „minus jeden” wg

${\ Displaystyle {\ kapelusz {y}} = \ operatorname {sgn} (\ mathbf {w} ^ {\ top} \ mathbf {x})}$

gdzie zero jest arbitralnie odwzorowane na jeden lub minus jeden. („ Kapelusz ” na ŷ oznacza szacunkową wartość).

W pseudokodzie algorytm perceptronu jest określony przez:

Zainicjuj w do wektora zerowego o długości p , liczby predyktorów (cech).

Dla pewnej ustalonej liczby iteracji lub do momentu spełnienia kryterium zatrzymania:

Dla każdego przykładu uczącego x _i z etykietą prawdy podstawowej y _i ∈ {-1, 1 }:

Niech ŷ = sgn( w ^T x _i ) .

Jeśli ŷ ≠ y _i , zaktualizuj w ← w + y _i x _ja .

Metody jądra

Główny artykuł: metody jądra

W przeciwieństwie do modeli liniowych wyuczonych przez perceptron, metoda jądra jest klasyfikatorem, który przechowuje podzbiór swoich przykładów uczących x _i , przypisuje każdemu wagę α _i i podejmuje decyzje dotyczące nowych próbek x' poprzez ocenę

${\ Displaystyle \ nazwa operatora {sgn} \ suma _ {i} \ alfa _ {i} y_ {i} K (\ mathbf {x} _ {i },\mathbf {x'} )}$ .

Tutaj K jest pewną funkcją jądra. Formalnie funkcja jądra jest nieujemnym półokreślonym jądrem (patrz warunek Mercera ), reprezentującym iloczyn wewnętrzny między próbkami w przestrzeni wielowymiarowej, tak jakby próbki zostały rozszerzone o dodatkowe cechy za pomocą funkcji Φ : K ( x , x' ) = Φ( x ) · Φ ( x' ) . Intuicyjnie można to traktować jako funkcję podobieństwa między próbkami, więc maszyna jądra ustala klasę nowej próbki przez ważone porównanie ze zbiorem uczącym. Każda funkcja x' ↦ K ( x _i , x' ) służy jako funkcja bazowa w klasyfikacji.

Algorytm

Aby uzyskać ziarnistą wersję algorytmu perceptronu, musimy najpierw sformułować go w postaci dualnej , zaczynając od obserwacji, że wektor wag w można wyrazić jako liniową kombinację n próbek treningowych. Równanie wektora ciężaru to

${\ Displaystyle \ mathbf {w} = \ suma _ {i} ^ {n} \ alfa _ {i} y_ {i} \ mathbf {x} _ {i}}$

gdzie α _i jest liczbą błędnych klasyfikacji x _i , wymuszających aktualizację w ← w + y _i x _i . Korzystając z tego wyniku, możemy sformułować algorytm podwójnego perceptronu, który przechodzi przez próbki tak jak poprzednio, dokonując prognoz, ale zamiast przechowywać i aktualizować wektor wagi w , aktualizuje wektor „licznika błędów” α . Musimy również przepisać formułę przewidywania, aby pozbyć się w :

${\ Displaystyle {\ rozpocząć {wyrównane} {\ kapelusz {y}} & = \ nazwa operatora {sgn} (\ mathbf {w} ^ {\ mathsf {T}} \ mathbf {x}) \\& = \ nazwa operatora { sgn} \left(\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}\right)^{\mathsf {T}}\mathbf {x} \\&=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}(\mathbf {x} _{i}\cdot \mathbf {x} )\end{ wyrównany}}}$

Podłączenie tych dwóch równań do pętli treningowej przekształci ją w algorytm podwójnego perceptronu .

Wreszcie, możemy zastąpić iloczyn skalarny w podwójnym perceptronie dowolną funkcją jądra, aby uzyskać efekt mapy cech Φ bez jawnego obliczania Φ( x ) dla jakichkolwiek próbek. W ten sposób uzyskuje się algorytm perceptronu jądra:

Zainicjuj α wektorem zerowym o długości n , czyli liczbie próbek uczących.

Dla pewnej ustalonej liczby iteracji lub do momentu spełnienia kryterium zatrzymania:

Dla każdego przykładu uczącego x _j , y _j :

Niech ${\ Displaystyle {\ kapelusz {y}} = \ nazwa operatora {sgn} \ suma _ {i} ^ {n} \ alfa _ {i} y_ {i} K (\ mathbf {x} _ {i}, \ mathbf {x} _{j})}$

Jeśli ŷ ≠ y _j , wykonaj aktualizację zwiększając licznik błędów:

α _j ← α _j + 1

Warianty i rozszerzenia

Jednym z przedstawionych powyżej problemów z perceptronem jądra jest to, że nie uczy się on rzadkich maszyn jądra. Początkowo wszystkie α _i są zerowe, więc ocena funkcji decyzyjnej w celu uzyskania ŷ nie wymaga żadnych ocen jądra, ale każda aktualizacja zwiększa pojedynczy α _i , przez co ocena jest coraz bardziej kosztowna. Co więcej, gdy perceptron jądra jest używany w online , liczba niezerowych α _i, a tym samym koszt oceny, rośnie liniowo wraz z liczbą przykładów przedstawionych algorytmowi.

Aby rozwiązać ten problem, zaproponowano wariant perceptronu jądra typu Forgetron. Utrzymuje aktywny zestaw przykładów z niezerowym α _i , usuwając („zapominając”) przykłady z aktywnego zestawu, gdy przekracza on z góry określony budżet i „kurcząc” (obniżając wagę) starych przykładów w miarę promowania nowych do niezerowego α _i .

Innym problemem związanym z perceptronem jądra jest brak regularyzacji , co czyni go podatnym na przeuczenie . Algorytm uczenia jądra online NORMA można uznać za uogólnienie algorytmu perceptronu jądra z regularyzacją. Algorytm sekwencyjnej optymalizacji minimalnej (SMO) używany do uczenia maszyn wektorów nośnych można również uznać za uogólnienie perceptronu jądra.

Głosowany algorytm perceptronu Freunda i Schapire'a rozciąga się również na przypadek z jądrem, dając granice uogólnienia porównywalne z SVM jądra.