Nauka Occam - Occam learning

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Structure Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LEKARSTWO Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Structure Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v t mi

W obliczeniowej teorii uczenia się , Occam learning stanowi model uczenia algorytmicznego, gdzie celem uczącego ma wyjścia zwięzłe przedstawienie otrzymanych danych treningowych. Jest to ściśle związane z prawdopodobnie w przybliżeniu poprawnym (PAC) uczeniem się , w którym uczący się jest oceniany na podstawie jego zdolności predykcyjnej zestawu testowego.

Uczenie się Occama implikuje uczenie się PAC, a dla szerokiej gamy zajęć koncepcyjnych jest również odwrotnie: uczenie się PAC oznacza uczenie się Occama.

Wprowadzenie

Uczenie Ockhama pochodzi od brzytwy Ockhama , która jest zasadą mówiącą, że biorąc pod uwagę, że wszystkie inne rzeczy są równe, krótsze wyjaśnienie zaobserwowanych danych powinno być preferowane nad wyjaśnieniem dłuższym. Teoria uczenia się Ockhama jest formalnym i matematycznym uzasadnieniem tej zasady. Po raz pierwszy została pokazana przez Blumera i in. że uczenie się Occama implikuje uczenie się PAC, które jest standardowym modelem uczenia się w teorii uczenia się komputerowego. Innymi słowy, skąpstwo (hipotezy wyjściowej) implikuje moc predykcyjną .

Definicja uczenia się Occam

Zwięzłość koncepcji w klasie koncepcji może być wyrażona przez długość najkrótszego ciągu bitów, który może reprezentować w . Uczenie Occam łączy zwięzłość danych wyjściowych algorytmu uczącego z jego mocą predykcyjną na niewidocznych danych. ${\displaystyle c}$ ${\displaystyle {\mathcal {C}}}$${\ Displaystyle rozmiar (c)}$${\displaystyle c}$${\displaystyle {\mathcal {C}}}$

Niech i będą klasami pojęć zawierającymi odpowiednio pojęcia i hipotezy docelowe. Następnie dla stałych i , algorytm uczenia się jest -Occam algorytm do korzystania IFF, biorąc pod uwagę zestaw z próbkami oznakowane zgodnie z koncepcją , wyprowadza hipotezę taką, że ${\displaystyle {\mathcal {C}}}$${\ Displaystyle {\ Mathcal {H}}}$${\ Displaystyle \ alfa \ geq 0}$${\ Displaystyle 0 \ leq \ beta <1}$${\ Displaystyle L}$${\displaystyle (\alfa ,\beta )}$${\displaystyle {\mathcal {C}}}$${\ Displaystyle {\ Mathcal {H}}}$${\ Displaystyle S = \ {x_ {1}, \ kropki, x_ {m} \}}$${\ Displaystyle m}$${\displaystyle c\in {\mathcal {C}}}$${\ Displaystyle L}$${\ Displaystyle h \ w {\ matematyczny {H}}}$

• ${\ Displaystyle h}$jest zgodny z on (czyli ), i${\displaystyle c}$${\displaystyle S}$${\ Displaystyle h (x) = c (x), \ forall x \ w S}$
• ${\ Displaystyle rozmiar (h) \ leq (n \ cdot rozmiar (c)) ^ {\ alfa} m ^ {\ beta}}$

gdzie jest maksymalna długość dowolnej próbki . Algorytm Occama jest nazywany wydajnym, jeśli działa w czasie wielomianu w , i Mówimy, że klasa pojęciowa jest uczona Occamem w odniesieniu do klasy hipotezy, jeśli istnieje wydajny algorytm Occama do używania${\ Displaystyle n}$${\ Displaystyle x \ w S}$${\ Displaystyle n}$${\ Displaystyle m}$${\ Displaystyle rozmiar (c).}$${\displaystyle {\mathcal {C}}}$${\ Displaystyle {\ Mathcal {H}}}$${\displaystyle {\mathcal {C}}}$${\ Displaystyle {\ Mathcal {H}}.}$

Związek między uczeniem się Occam i PAC

Umiejętność Occama implikuje uczenie się PAC, zgodnie z następującym twierdzeniem Blumera i in. przedstawia:

Twierdzenie ( uczenie się Occama implikuje uczenie się PAC )

Niech będzie wydajnym algorytmem -Occam do używania . Wtedy istnieje stała taka, że ​​dla dowolnego , dla dowolnego rozkładu , danych próbek pobranych z i oznaczonych zgodnie z koncepcją długości bitów każda, algorytm wygeneruje hipotezę taką, że z prawdopodobieństwem co najmniej .${\ Displaystyle L}$${\displaystyle (\alfa ,\beta )}$${\displaystyle {\mathcal {C}}}$${\ Displaystyle {\ Mathcal {H}}}$${\displaystyle a>0}$${\displaystyle 0<\epsilon,\delta <1}$${\displaystyle {\mathcal {D}}}$${\ Displaystyle m \ geq a \ lewo ({\ Frac {1} {\ epsilon}} \ log {\ Frac {1} {\ delta}} + \ lewo ({\ Frac {(n \ cdot rozmiar (c)) )^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)}$${\displaystyle {\mathcal {D}}}$${\displaystyle c\in {\mathcal {C}}}$${\ Displaystyle n}$${\ Displaystyle L}$${\ Displaystyle h \ w {\ matematyczny {H}}}$${\ Displaystyle błąd (h) \ leq \ epsilon }$${\displaystyle 1-\delta}$

Tutaj chodzi o koncepcję i dystrybucję . Oznacza to, że algorytm jest również uczniem PAC dla klasy koncepcji przy użyciu klasy hipotez . Nieco bardziej ogólne sformułowanie jest następujące: ${\błąd displaystyle (h)}$${\displaystyle c}$${\displaystyle {\mathcal {D}}}$${\ Displaystyle L}$${\displaystyle {\mathcal {C}}}$${\ Displaystyle {\ Mathcal {H}}}$

Twierdzenie ( uczenie Occam oznacza uczenie PAC, wersja kardynalności )

Niech . Niech będzie algorytmem takim, że dane próbki pobrane ze stałego, ale nieznanego rozkładu i oznaczone zgodnie z koncepcją długości bitów każda, wyprowadza hipotezę, która jest zgodna z oznaczonymi próbkami. Wtedy istnieje stała taka, że ​​if , then gwarantuje wyprowadzenie hipotezy takiej, że z prawdopodobieństwem co najmniej .${\displaystyle 0<\epsilon,\delta <1}$${\ Displaystyle L}$${\ Displaystyle m}$${\displaystyle {\mathcal {D}}}$${\displaystyle c\in {\mathcal {C}}}$${\ Displaystyle n}$${\ Displaystyle h \ w {\ mathcal {H}} _ {n, m}}$${\displaystyle b}$${\ Displaystyle \ log | {\ mathcal {H}} _ {n, m} | \ leq b \ epsilon m- \ log {\ Frac {1} {\ delta}}}$${\ Displaystyle L}$${\ Displaystyle h \ w {\ mathcal {H}} _ {n, m}}$${\ Displaystyle błąd (h) \ leq \ epsilon }$${\displaystyle 1-\delta}$

Chociaż powyższe twierdzenia pokazują, że uczenie Occam jest wystarczające do uczenia PAC, nie mówi nic o konieczności. Board i Pitt pokazują, że w przypadku szerokiej gamy zajęć koncepcyjnych uczenie się metodą Occam jest w rzeczywistości niezbędne do uczenia się PAC. Udowodnili, że dla każdej klasy pojęć, która jest wielomianowo zamknięta na listach wyjątków, uczenie się PAC implikuje istnienie algorytmu Occama dla tej klasy pojęć. Klasy pojęć, które są wielomianowo zamknięte na listach wyjątków, obejmują formuły logiczne, obwody, deterministyczne automaty skończone , listy decyzyjne, drzewa decyzyjne i inne geometrycznie zdefiniowane klasy pojęciowe.

Klasa koncepcja jest wielomianowo zamknięte pod listami wyjątek, jeśli istnieje algorytm wielomianowy czasu tak, że gdy dana reprezentacja koncepcji i skończonej listy z wyjątkami , wyjścia przedstawienie koncepcji takich, że koncepcje i zgadza z wyjątkiem na planie . ${\displaystyle {\mathcal {C}}}$${\ Displaystyle A}$${\displaystyle c\in {\mathcal {C}}}$${\ Displaystyle E}$${\displaystyle c'\in {\mathcal {C}}}$${\displaystyle c}$${\displaystyle c'}$${\ Displaystyle E}$

Dowód, że uczenie się Occam oznacza uczenie się PAC

Najpierw udowadniamy wersję kardynalności. Nazwijmy hipotezę złą if , gdzie znowu jest w odniesieniu do prawdziwego pojęcia i podstawowego rozkładu . Prawdopodobieństwo, że zbiór próbek jest zgodny, wynosi co najwyżej , przez niezależność próbek. Przez związek prawdopodobieństwo, że istnieje zła hipoteza w wynosi co najwyżej , czyli jest mniejsze niż w przypadku . To kończy dowód drugiego twierdzenia powyżej. ${\ Displaystyle h \ w {\ matematyczny {H}}}$ ${\ Displaystyle błąd (h) \ geq \ epsilon }$${\błąd displaystyle (h)}$${\displaystyle c}$${\displaystyle {\mathcal {D}}}$${\displaystyle S}$${\ Displaystyle h}$${\ Displaystyle (1-\ epsilon) ^ {m}}$${\ Displaystyle {\ Mathcal {H}} _ {n, m}}$${\ Displaystyle | {\ mathcal {H}} _ {n, m} | (1-\ epsilon) ^ {m}}$${\ Displaystyle \ delta}$${\ Displaystyle \ log | {\ mathcal {H}} _ {n, m} | \ leq O (\ epsilon m) - \ log {\ Frac {1} {\ delta}}}$

Korzystając z drugiego twierdzenia, możemy udowodnić pierwsze twierdzenie. Ponieważ mamy algorytm -Occam, oznacza to, że każda wyjściowa hipoteza może być reprezentowana przez co najwyżej bity, a zatem . To mniej niż gdybyśmy ustawili jakąś stałą . Tak więc, dzięki twierdzeniu o kardynalizacji, wyprowadzi spójną hipotezę z prawdopodobieństwem co najmniej . Na tym kończy się dowód pierwszego twierdzenia powyżej. ${\displaystyle (\alfa ,\beta )}$${\ Displaystyle L}$${\ Displaystyle (n \ cdot rozmiar (c)) ^ {\ alfa} m ^ {\ beta}}$${\ Displaystyle \ log | {\ mathcal {H}} _ {n, m} | \ leq (n \ cdot rozmiar (c)) ^ {\ alfa} m ^ {\ beta}}$${\ Displaystyle O (\ epsilon m) - \ log {\ Frac {1} {\ delta}}}$${\ Displaystyle m \ geq a \ lewo ({\ Frac {1} {\ epsilon}} \ log {\ Frac {1} {\ delta}} + \ lewo ({\ Frac {(n \ cdot rozmiar (c)) )^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)}$${\displaystyle a>0}$${\ Displaystyle L}$${\ Displaystyle h}$${\displaystyle 1-\delta}$

Poprawa złożoności próbki w przypadku typowych problemów

Chociaż uczenie się Occam i PAC są równoważne, struktura Occam może być używana do tworzenia ściślejszych ograniczeń złożoności próbki klasycznych problemów, w tym spójników, spójników z kilkoma odpowiednimi zmiennymi i list decyzyjnych.

Rozszerzenia

Wykazano również, że algorytmy Occama są skuteczne w uczeniu PAC w obecności błędów, pojęć probabilistycznych, uczenia się funkcji i nieniezależnych przykładów Markowa.

Zobacz też

• Minimalizacja ryzyka strukturalnego
• Teoria uczenia się komputerowego

Bibliografia