Uczenie się przestrzeni wersji - Version space learning

Przestrzeń wersji dla języka hipotez „prostokąta” w dwóch wymiarach. Zielone plusy to pozytywne przykłady, a czerwone kółka to negatywne przykłady. GB jest granicą maksymalnie ogólnej pozytywnej hipotezy, a SB jest maksymalnie szczegółową granicą pozytywnej hipotezy. Pośrednie (cienkie) prostokąty przedstawiają hipotezy w przestrzeni wersji.

Uczenie się w przestrzeni wersji to logiczne podejście do uczenia maszynowego , w szczególności klasyfikacji binarnej . Algorytmy uczące się w przestrzeni wersji przeszukują predefiniowaną przestrzeń hipotez , postrzeganą jako zbiór zdań logicznych . Formalnie przestrzeń hipotezy jest dysjunkcją

(tj. albo hipoteza 1 jest prawdziwa, albo hipoteza 2, albo dowolny podzbiór hipotez od 1 do n ). Algorytm uczenia się w przestrzeni wersji został przedstawiony z przykładami, których użyje do ograniczenia przestrzeni swojej hipotezy; dla każdego przykładu x hipotezy niezgodne z x są usuwane z przestrzeni. To iteracyjne udoskonalanie przestrzeni hipotez nazywa się algorytmem eliminacji kandydatów , przestrzeń hipotezy utrzymywana jest wewnątrz algorytmu jako przestrzeń wersji .

Algorytm przestrzeni wersji

W warunkach, w których istnieje ogólność porządkująca hipotezy, możliwe jest przedstawienie przestrzeni wersji za pomocą dwóch zestawów hipotez: (1) najbardziej szczegółowe spójne hipotezy oraz (2) najbardziej ogólne spójne hipotezy, gdzie „spójna” oznacza zgodność z obserwowanymi danymi.

Najbardziej szczegółowe hipotezy (tj. Specyficzna granica SB ) obejmują zaobserwowane pozytywne przykłady treningu i jak najmniejszą pozostałą przestrzeń cech . Hipotezy te, jeśli zmniejszono dalej, wyklucza się pozytywny przykład treningowy, a więc stają się niespójne. Te minimalne hipotezy zasadniczo stanowią (pesymistyczne) twierdzenie, że prawdziwe pojęcie jest definiowane tylko przez już zaobserwowane pozytywne dane: Tak więc, jeśli zaobserwuje się nowy (nigdy wcześniej nie widziany) punkt danych, należy przyjąć, że jest on negatywny. (To znaczy, jeśli dane nie zostały wcześniej wykluczone, to jest wykluczone).

Najbardziej ogólne hipotezy (tj. Ogólna granica GB ) obejmują zaobserwowane pozytywne przykłady treningu, ale obejmują również tyle samo pozostałej przestrzeni cech, nie uwzględniając żadnych negatywnych przykładów treningu. Te, Jeżeli powiększony dalej, to jest negatywny przykład szkolenia, a tym samym będą niespójne. Te maksymalne hipotezy zasadniczo stanowią (optymistyczne) twierdzenie, że prawdziwe pojęcie jest definiowane tylko przez już zaobserwowane negatywne dane: Tak więc, jeśli zaobserwuje się nowy (nigdy wcześniej nie widziany) punkt danych, należy przyjąć, że jest on pozytywny. (To znaczy, jeśli dane nie zostały wcześniej wykluczone, zostaną wykluczone).

Zatem podczas uczenia się przestrzeń wersji (która sama jest zbiorem - być może nieskończonym - zawierającym wszystkie spójne hipotezy) może być reprezentowana tylko przez jej dolną i górną granicę (maksymalnie ogólne i maksymalnie szczegółowe zestawy hipotez), a operacje uczenia się mogą być wykonywane po prostu na tych reprezentatywnych zestawach.

Po nauczeniu się klasyfikację można przeprowadzić na niewidocznych przykładach, testując hipotezę poznaną przez algorytm. Jeśli przykład jest zgodny z wieloma hipotezami, można zastosować zasadę większości głosów.

Tło historyczne

Pojęcie przestrzeni wersji zostało wprowadzone przez Mitchella na początku lat 80. XX wieku jako ramy do zrozumienia podstawowego problemu nadzorowanego uczenia się w kontekście poszukiwania rozwiązań . Chociaż podstawowa metoda wyszukiwania „ eliminacji kandydatów ”, która towarzyszy strukturze przestrzeni wersji, nie jest popularnym algorytmem uczenia się, istnieją pewne praktyczne implementacje, które zostały opracowane (np. Sverdlik & Reynolds 1992, Hong & Tsang 1997, Dubois & Quafafou 2002).

Główną wadą uczenia się przestrzeni wersji jest jego niezdolność do radzenia sobie z szumem: każda para niespójnych przykładów może spowodować załamanie się przestrzeni wersji , tj. Opróżnienie, tak że klasyfikacja stanie się niemożliwa. Jedno z rozwiązań tego problemu zostało zaproponowane przez Dubois i Quafafou, którzy zaproponowali Szorstką Przestrzeń Wersji, w której przybliżenia oparte na zbiorach przybliżonych są używane do poznania pewnych i możliwych hipotez w obecności niespójnych danych.

Zobacz też

  • Analiza koncepcji formalnej
  • Programowanie w logice indukcyjnej
  • Szorstki zestaw . [Wstępny schemat zbioru koncentruje się na przypadku, w którym niejednoznaczność jest wprowadzana przez zubożony zestaw funkcji . Oznacza to, że docelowej koncepcji nie można w sposób rozstrzygający opisać, ponieważ dostępny zestaw funkcji nie pozwala ujednoznacznić obiektów należących do różnych kategorii. Struktura przestrzeni wersji koncentruje się na (klasycznej indukcji) przypadku, w którym niejednoznaczność jest wprowadzana przez zubożony zestaw danych . Oznacza to, że docelowej koncepcji nie można w sposób zdecydowany opisać, ponieważ dostępne dane nie pozwalają jednoznacznie określić hipotezy. Oczywiście oba rodzaje niejednoznaczności mogą wystąpić w tym samym problemie edukacyjnym.]
  • Rozumowanie indukcyjne . [O ogólnym problemie indukcji].

Bibliografia

  1. ^ a b c d Russell, Stuart ; Norvig, Peter (2003) [1995]. Artificial Intelligence: A Modern Approach (2nd ed.). Prentice Hall. pp. 683–686. ISBN   978-0137903955 .
  2. ^ a b Mitchell, Tom M. (1982). „Uogólnienie jako wyszukiwanie”. Sztuczna inteligencja . 18 (2): 203–226. doi : 10.1016 / 0004-3702 (82) 90040-6 .
  3. ^ Dubois Vincent; Quafafou, Mohamed (2002). "Uczenie się koncepcji z przybliżeniem: przybliżone przestrzenie wersji". Rough Sets and Current Trends in Computing: Proceedings of the Third International Conference, RSCTC 2002 . Malvern, Pensylwania. s. 239–246. doi : 10.1007 / 3-540-45813-1_31 .