Transdukcja (uczenie maszynowe)
W logice , wnioskowaniu statystycznym i nadzorowanym uczeniu się , transdukcja lub wnioskowanie transdukcyjne to rozumowanie z obserwowanych, konkretnych (treningowych) przypadków do konkretnych (testowych) przypadków. W przeciwieństwie do indukcji jest wnioskowanie od zaobserwowanych przypadków uczących do ogólnych reguł, które są następnie stosowane do przypadków testowych. Rozróżnienie jest najbardziej interesujące w przypadkach, w których przewidywania modelu transdukcyjnego nie są osiągalne przez żaden model indukcyjny. Należy zauważyć, że jest to spowodowane przez wnioskowanie transdukcyjne na różnych zestawach testowych, które dają wzajemnie niespójne prognozy.
Transdukcję wprowadził Vladimir Vapnik w latach 90. XX wieku, motywowany jego poglądem, że transdukcja jest lepsza od indukcji, ponieważ według niego indukcja wymaga rozwiązania bardziej ogólnego problemu (wywnioskowania funkcji) przed rozwiązaniem bardziej szczegółowego problemu (obliczenia wyników dla nowych przypadków ): „Rozwiązując interesujący Cię problem, nie rozwiązuj bardziej ogólnego problemu jako kroku pośredniego. Postaraj się uzyskać odpowiedź, której naprawdę potrzebujesz, ale nie bardziej ogólną”. Podobną obserwację poczynił wcześniej Bertrand Russell : „dojdziemy do wniosku, że Sokrates jest śmiertelnikiem, z większym podejściem do pewności, jeśli uczynimy nasz argument czysto indukcyjnym, niż jeśli pójdziemy drogą„ wszyscy ludzie są śmiertelni ”, a następnie zastosujemy dedukcję” (Russell 1912, rozdz. VII).
Przykładem uczenia się, które nie jest indukcyjne, jest klasyfikacja binarna, w której dane wejściowe mają tendencję do grupowania się w dwie grupy. Duży zestaw testowych danych wejściowych może pomóc w znalezieniu klastrów, dostarczając w ten sposób przydatnych informacji o etykietach klasyfikacyjnych. Te same przewidywania nie byłyby możliwe do uzyskania z modelu, który indukuje funkcję opartą wyłącznie na przypadkach uczących. Niektórzy mogą nazwać to przykładem blisko spokrewnionego częściowo nadzorowanego uczenia się , ponieważ motywacja Vapnika jest zupełnie inna. Przykładem algorytmu z tej kategorii jest Transductive Support Vector Machine (TSVM).
Trzecia możliwa motywacja, która prowadzi do transdukcji, wynika z potrzeby zbliżenia. Jeśli dokładne wnioskowanie jest obliczeniowo niemożliwe, można przynajmniej spróbować upewnić się, że przybliżenia są dobre na testowych danych wejściowych. W takim przypadku dane wejściowe testowe mogłyby pochodzić z dowolnego rozkładu (niekoniecznie związanego z rozkładem danych wejściowych szkoleniowych), co nie byłoby dozwolone w uczeniu częściowo nadzorowanym. Przykładem algorytmu należącego do tej kategorii jest Bayesian Committee Machine (BCM).
Przykładowy problem
Poniższy przykładowy problem porównuje niektóre unikalne właściwości transdukcji z indukcją.
Podany jest zbiór punktów, tak że niektóre punkty są oznaczone (A, B lub C), ale większość punktów jest nieoznakowana (?). Celem jest przewidzenie odpowiednich etykiet dla wszystkich nieoznakowanych punktów.
Indukcyjne podejście do rozwiązania tego problemu polega na wykorzystaniu oznaczonych punktów do wytrenowania algorytmu uczenia nadzorowanego , a następnie zleceniu mu przewidywania etykiet dla wszystkich nieoznakowanych punktów. Jednak w przypadku tego problemu algorytm uczenia nadzorowanego będzie miał tylko pięć oznaczonych punktów do wykorzystania jako podstawa do zbudowania modelu predykcyjnego. Z pewnością trudno będzie zbudować model, który uchwyci strukturę tych danych. Na przykład, jeśli używany jest algorytm najbliższego sąsiada, wówczas punkty w pobliżu środka będą oznaczone jako „A” lub „C”, mimo że oczywiste jest, że należą do tego samego klastra, co punkt oznaczony „B”.
Zaletą transdukcji jest możliwość uwzględnienia wszystkich punktów, a nie tylko oznaczonych punktów, podczas wykonywania zadania etykietowania. W tym przypadku algorytmy transdukcyjne oznaczyłyby nieoznaczone punkty zgodnie z klastrami, do których naturalnie należą. Punkty pośrodku byłyby zatem najprawdopodobniej oznaczone jako „B”, ponieważ są upakowane bardzo blisko tej gromady.
Zaletą transdukcji jest to, że może być w stanie dokonać lepszych prognoz przy mniejszej liczbie oznaczonych punktów, ponieważ wykorzystuje naturalne przerwy znalezione w nieoznakowanych punktach. Wadą transdukcji jest to, że nie tworzy modelu predykcyjnego. Jeśli do zbioru zostanie dodany wcześniej nieznany punkt, cały algorytm transdukcyjny musiałby zostać powtórzony ze wszystkimi punktami, aby przewidzieć etykietę. Może to być kosztowne obliczeniowo, jeśli dane są udostępniane przyrostowo w strumieniu. Co więcej, może to spowodować zmianę przewidywań niektórych starych punktów (co może być dobre lub złe, w zależności od aplikacji). Z drugiej strony algorytm uczenia nadzorowanego może natychmiast oznaczać nowe punkty, przy bardzo niewielkich kosztach obliczeniowych.
Algorytmy transdukcji
Algorytmy transdukcji można zasadniczo podzielić na dwie kategorie: te, które starają się przypisać dyskretne etykiety punktom nieoznakowanym, oraz te, które mają na celu regresję ciągłych etykiet dla nieoznakowanych punktów. Algorytmy, które mają na celu przewidywanie dyskretnych etykiet, zwykle uzyskuje się przez dodanie częściowego nadzoru do grupowania . Można zastosować dwie klasy algorytmów: klastrowanie płaskie i klastrowanie hierarchiczne. Te ostatnie można dalej podzielić na dwie kategorie: te, które skupiają się przez podział, i te, które skupiają się przez aglomerację. Algorytmy, które mają na celu przewidywanie ciągłych etykiet, zwykle są wyprowadzane przez dodanie częściowego nadzoru do a wieloraki algorytm uczenia się.
Transdukcja partycjonowania
Transdukcję dzielącą można traktować jako transdukcję z góry na dół. Jest to częściowo nadzorowane rozszerzenie klastrowania opartego na partycjach. Zwykle wykonuje się to w następujący sposób:
Rozważ zbiór wszystkich punktów jako jedną dużą partycję. Podczas gdy każda partycja P zawiera dwa punkty ze sprzecznymi etykietami: Partycja P na mniejsze partycje. Dla każdej partycji P: Przypisz tę samą etykietę wszystkim punktom w P.
Oczywiście z tym algorytmem można zastosować dowolną rozsądną technikę partycjonowania. Do tego celu bardzo popularne są schematy partycjonowania typu max flow min cut .
Transdukcja aglomeratywna
Transdukcję aglomeracyjną można traktować jako transdukcję oddolną. Jest to częściowo nadzorowane rozszerzenie klastrowania aglomeracyjnego. Zwykle wykonuje się to w następujący sposób:
Oblicz odległości parami, D, między wszystkimi punktami. Sortuj D w porządku rosnącym. Rozważmy każdy punkt jako klaster o rozmiarze 1. Dla każdej pary punktów {a,b} w D: Jeśli (a nie jest oznaczony) lub (b jest nieoznaczony) lub (a i b mają tę samą etykietę) Połącz dwa skupienia które zawierają a i b. Oznacz wszystkie punkty w połączonym skupieniu tą samą etykietą.
Transdukcja wieloraka
Transdukcja oparta na wielorakim uczeniu się jest wciąż bardzo młodą dziedziną badań.
Zobacz też
- VN Vapnik. Statystyczna teoria uczenia się . Nowy Jork: Wiley, 1998. (Patrz strony 339-371)
- V. Tresp. Maszyna komitetu Bayesa , Neural Computation, 12, 2000, pdf .
- B. Russella. Zagadnienia filozofii , Biblioteka Uczelni Krajowej, 1912. [1] .
Linki zewnętrzne
- Gammerman, V. Vovk, V. Vapnik (1998). „ Uczenie się przez transdukcję ”. Wczesne wyjaśnienie transdukcyjnego uczenia się.
- „ Omówienie częściowo nadzorowanego uczenia się i transdukcji ”, rozdział 25 częściowo nadzorowanego uczenia się, Olivier Chapelle, Bernhard Schölkopf i Alexander Zien, wyd. (2006). MIT Press. Omówienie różnicy między SSL a transdukcją.
- Waffles to otwarta biblioteka C++ zawierająca algorytmy uczenia maszynowego, w tym algorytmy transdukcji, także Waffles .
- SVMlight to pakiet SVM ogólnego przeznaczenia, który zawiera transdukcyjną opcję SVM.