Metody odkrywania wiedzy: wykład 10
Od uczenia się do odkrywania wiedzy

Paweł Cichosz

Date: 2001/2002

Wykład ma na celu skomentowanie -- bezpośrednio po prezentacji podstawowych metod odkrywania wiedzy wywodzących się z indukcyjnego uczenia się -- głównych problemów występujących przy ich stosowaniu do rzeczywistych zbiorów danych.

Duże zbiory danych

Zakrawa na paradoks, że duża liczba przykładów trenujących, niezbędna do uzyskania w drodze indukcyjnego uczenia się dostatecznie dokładnej hipotezy, może się jednocześnie stać jedną z najpoważniejszych przeszkód w ich praktycznym stosowaniu. Jest jednak jasne, że koszt obliczeniowy znalezienia hipotezy przez wszystkie algorytmy zależy od rozmiaru przetwarzanego zbioru trenującego co najmniej liniowo. Jeśli rozmiar ten sięga milionów przykładów, co w przypadku współczesnych baz danych nie jest rzadkością, to koszt może przekroczyć granice akceptowalności, czasem nawet wielokrotnie. Naszkicujemy tu kilka ogólnych podejść do tego problemu, zmierzających do ograniczenia liczby przykładów uwzględnianych przy uczeniu się, a później dyskutując zagadnienia implementacyjne na końcu rozdziału wrócimy do niego, wspominając o specjalnych strukturach danych umożliwiających przetwarzanie w efektywny sposób dużych zbiorów trenujących w całości.

Okienkowanie

Najprostszym systematycznym i uniwersalnym podejściem do uczenia się na podstawie dużych zbiorów danych jest technika okienkowania, czyli uczenia się na podstawie początkowo małych i w miarę potrzeby rosnących podzbiorów zbioru trenującego, nazywanych zbiorami roboczymi. Schemat tego sposobu postępowania przedstawia poniższy algorytm.

Pomysł polega na wybieraniu stosunkowo niewielkiego losowego podzbioru całego zbioru trenującego i uczeniu się hipotezy na podstawie tak otrzymanego zbioru roboczego. Uzyskana hipoteza jest następnie testowana na pozostałych przykładach trenujących, a zbiór roboczy jest uzupełniany o niektóre (również losowo wybrane) spośród tych, które są przez nią klasyfikowane niepoprawnie. Dla nowego zbioru roboczego wykorzystywany algorytm uczenia się ponownie generuje hipotezę i cały proces powtarza się tak długo, jak długo kolejna hipoteza jest lepsza od poprzedniej ze względu na błąd próbki na zbiorze trenującym (lub dopóki błąd próbki nie spadnie poniżej wymaganego poziomu). Błąd próbki jest w tym miejscu jedynym kryterium oceny, gdyż po zakończeniu generowania serii hipotez ostatnia z nich jest przycinana w celu uniknięcia nadmiernego dopasowania. Ponieważ jednak ostateczny rezultat całego takiego procesu może zależeć od wyboru początkowego zbioru roboczego (i następnie dodawanych do niego przykładów), sugeruje się powtarzanie go pewną liczbę razy i ostateczny wybór najlepszej z uzyskanych hipotez, przy czym tym razem stosowane kryterium jakości może oprócz błędu próbki uwzględniać inne cechy, takie jak złożoność. Doświadczenia wskazują, że użycie zbioru roboczego, który początkowo zawiera około jednej dziesiątej całego zbioru trenującego, prowadzi w typowych przypadkach do uzyskania zadowalającej hipotezy po kilku iteracjach. Dla średnich i dużych zbiorów trenujących (od tysięcy do setek tysięcy przykładów) oznacza to na ogół znaczne oszczędności w stosunku do próby uczenia się na podstawie całego zbioru trenującego.

Redukcja liczby przykładów

Jeżeli okienkowanie z różnych względów okazuje się niewystarczające, gdyż uzyskanie dostatecznie dużej dokładności wymaga wielu iteracji poszerzania okna, można wziąć pod uwagę dokonanie samobójczej z pozoru operacji redukcji dostępnego zbioru trenującego. Aby nie była to istotnie operacja samobójcza, należy ją przeprowadzić w sposób, który z dużym prawdopodobieństwem pozostawi w zredukowanych danych interesujące i użyteczne zależności, występujące w oryginalnym zbiorze danych. Można na to także patrzeć jak na swoistą technikę zapobiegania nadmiernemu dopasowaniu, zgodnie z którą przycina się nie zbyt złożoną hipotezę, z czym wielokrotnie się dotychczas spotkaliśmy, lecz zbyt duży zbiór trenujący.

Redukcja taka może mieć dwojaką postać. Po pierwsze, może być osiągnięta przez przeprowadzenia grupowania pojęciowego jako fazy przetwarzania wstępnego i następnie użycia opisów grup jako źródła nowych, znacznie mniej licznych przykładów. Aby podejście to miało sens, grupowanie to powinno następować oddzielnie dla przykładów trenujących wszystkich kategorii, zaś jego ziarnistość (określająca liczbę uzyskiwanych grup) powinna być dobrana tak, aby osiągnięta została pożądana skala redukcji rozmiaru tenującego. Najlepiej wykorzystać w tym celu grupowanie hierarchiczne, wybierając najbardziej odpowiedni poziom hierarchii. Dla każdej grupy można wówczas wybrać po prostu pewną niewielką liczbę zaliczonych do niej przykładów, w najprostszym przypadku równomiernie losując. Można również na podstawie opisu grupy wygenerować pewną liczbę ,,sztucznych'' przykładów należących do tej grupy. Sposób tworzenia nowych przykładów dla poszczególnych grup zależy od ich reprezentacji stosowanej w używanym algorytmie grupowania. Dla grupy reprezentowanej za pomocą kompleksu określa on dopuszczalne wartości każdego atrybutu i w ramach takiego zbioru wartości dopuszczlnych można stosować równomierne losowanie. Przy reprezentacji probabilistycznej dysponujemy rozkładami prawdopodobieństwa wartości poszczególnych atrybutów dla przykładów należących do grupy i można wygenerować opisy przykładów według tych rozkładów. Poważną słabością tego rozwiązania jest jednak przyjmowane w nim domyślnie, a często nieprawdziwe założenie, że grupowanie zbioru trenującego jest znacznie mniej kosztowne niż bezpośrednie uczenie się hipotezy dla tego zbioru. Może być to prawdą tylko pod warunkiem użycia bardzo uproszczonych algorytmów grupowania.

Inne podejście polega na bezpośrednim wyborze ze zbioru trenującego tylko jego pewnego niewielkiego podzbioru, złożonego z przykładów uznanych za najbardziej reprezentatywne. Można zaproponować różne proste heurystyki umożliwiające dokonanie tego wyboru w sposób na tyle efektywny obliczeniowo, aby ogólny nakład obliczeń na uczenie się znacznie się dzięki temu zmniejszył. Przedstawimy jedną z nich, pochodzącą z programu ESEL pierwotnie przeznaczonego do wybierania przykładów dla systemu AQ.

Algorytm ESEL zakłada, że dla przykładów jest określona pewna miara odległości, zależna od wartości opisujących je atrybutów. Funkcję odległości przykładów oznaczać będziemy przez $\delta$ i założymy, że może być ona stosowana zarówno do przykładów, jak i wektorów wartości atrybutów. Podstawowa heurystyka leżąca u podstaw omawianej techniki może być sformułowana jako dążenie do wybierania przykładów maksymalnie od siebie odległych. Przy zadanym stopniu redukcji zbioru trenującego wybiera się z niego takie przykłady, aby ich wzajemne odległości były jak największe. Dokładniej, można sformułować przybliżone kryterium reprezentatywności zbioru przykładów jako maksymalizację średniej odległości między dowolnymi dwoma przykładami z tego zbioru przy jednoczesnym możliwie niewielkim zróżnicowaniu tych odległości.

Punktem wyjścia jest ustalenie w zbiorze trenującym $T$ pewnego wektora wartości atrybutów, który można nazwać wektorem minimalnym. Jest to dowolny taki wektor, w którym dla wszystkich atrybutów porządkowych i ciągłych znajdują się ich najmniejsze wartości występujące w zbiorze $T$. Wartości atrybutów nominalnych mogą być w wektorze minimalnym dowolne, w szczególności można przyjąć dla tych wartości porządek leksykograficzny i wybrać pierwsze wartości według tego porządku. Wektor minimalny, oznaczany przez $\mu$, służy następnie do znalezienia w zbiorze $T$ dwóch ,,skrajnych'' przykładów $x_{\min}$ i $x_{\max}$, odpowiednio najbliższego wektorowi minimalnemu i najdalszego od niego według metryki $\delta$. Odległość między tymi przykładami, $\delta(x_{\min},x_{\max})$, jest następnie dzielona na pewną liczbę $m\geq 1$ podprzedziałów, wyznaczających jednocześnie podział zbioru trenującego $T$ na rozłączne podzbiory $P_1,P_2,\dots,P_m$ w taki sposób, że do zbioru $P_i$ należą te i tylko te przykłady $x\in T$, dla których odległość $\delta(x,\mu)$ należy do przedziału o numerze $i$. Dobór końców przedziałów powinien zapewniać jednakową w przybliżeniu liczbę elementów w każdym z tych zbiorów, przez co $\vert P_i\vert\approx\frac{\vert T\vert}{m}$ dla każdego $i=1,2,\dots,m$. Z każdego z podzbiorów $P_1,P_2,\dots,P_m$ wybiera się taką samą liczbę przykładów $r\frac{\vert T\vert}{m}$, które wejdą w skład zbioru $r\vert T\vert$ najbardziej reprezentatywnych przykładów, stanowiącego wynik algorytmu, gdzie $r$ oznacza żądany współczynnik redukcji zbioru trenującego. Dla każdego $i=1,2,\dots,m$ ze zbioru $P_i$ jest więc wybierany pewien podzbiór $S_i\subset P_i$, dla którego $\vert S_i\vert=r\frac{\vert T\vert}{m}$. Pierwsze dwa przykłady $x_1$ i $x_2$, które trafiają do zbioru $S_i$, są wybierane jako najbardziej odległe od siebie przykłady w zbiorze $P_i$. Ponieważ ich znalezienie w ten sposób może być kosztowne w przypadku dużych zbiorów przykładów, można zadowolić się przybliżoną, lecz znacznie tańszą wersją algorytmu, w której odpowiedni krok realizuje się jako:

$$x_1 :={} \mathrm{arg}\min_{x\in P_i}\delta(x,\mu)$$ (1)

$$x_2 :={} \mathrm{arg}\max_{x\in P_i}\delta(x,x_1)$$ (2)

Następnie każdy kolejny przykład jest wybierany tak, aby iloczyn jego odległości od wszystkich przykładów wcześniej dodanych do $S_i$ był jak największy. Zapewnia to z jednej strony maksymalizację średniej odległości od wszystkich przykładów, a z drugiej strony zachowanie możliwie zbliżonych odległości między poszczególnymi przykładami.

Próbkowanie wewnętrzne

Zarówno okienkowanie, jak i metody redukcji rozmiaru zbioru trenującego zmierzają do ograniczenia kosztu uczenia się dla dużych zbiorów trenujących przez jednoczesne uwzględnianie tylko części przykładów. Algorytm uczenia się nie ulega wówczas żadnej zmianie, a tylko jest stosowany do pewnego podzbioru zbioru trenującego. Możliwe jest jednak także inne podejście, przenoszące wybór próbki przykładów w obręb algorytmu uczenia się, stosowanego wówczas do całego zbioru trenującego. Koncepcja polega na tym, aby tylko obliczenia najbardziej kosztowne i zależne od liczby przykładów algorytm wykonywał na podstawie ich losowej, każdorazowo niezależnie wybranej próbki. Takie podejście nazwiemy próbkowaniem wewnętrznym. Może ono niekiedy dawać lepsze efekty niż okienkowanie lub redukcja liczby przykładów, gdyż istnieje możliwość uwzględniania w różnych operacjach wykonywanych przez algorytm, zależnie od ich złożoności, większej lub mniejszej części zbioru trenującego, a żaden przykład nie jest z góry skazany na pominięcie.

Praktyczna realizacja próbkowania wewnętrznego zależy od algorytmu uczenia się, dla którego jest wprowadzane. W przypadku konstruowania drzew decyzyjnych najbardziej kosztowną operacją jest wybór testu, więc, jeśli związany z aktualnym węzłem zbiór przykładów jest liczny, to wyboru tego można dokonać na podstawie jego losowo wybranego podzbioru. Na niższych poziomach drzewa, kiedy liczba przykładów się zmniejszy, mogą być już uwzględniane wszystkie przykłady. Jest także możliwe inne pokrewne podejście, polegające na wzięciu pod uwagę tylko pewnej liczby losowo wybranych testów i znalezienie najlepszego z nich. Może to dać istotne oszczędności, jeśli liczba możliwych testów jest duża, co na ogół ma miejsce w przypadku testów dla atrybutów ciągłych. W przypadku indukcji reguł od liczby przykładów zależy przede wszystkim ocena jakości kompleksów, do której niezbędne jest wyznaczenie liczby przykładów z pewnego zbioru pokrywanych przez oceniany kompleks. W tym przypadku także, jeśli zbiór ten jest liczny, można obliczenia wykonać dla jego losowego podzbioru.

Dekompozycja zbioru trenującego

Koszt obliczeniowy przetwarzania dużych zbiorów trenujących to nie jedyny związany z nimi problem. Nie mniej istotny może okazać się inny problem, polegający na tym, że zależności występujące w takich dużych zbiorach danych mogą być bardzo złożone, zbyt złożone, aby opisujące je hipotezy były czytelne i możliwe do interpretacji, co może być jednym z celów odkrywania tych zależności. Jeśli więc złożoność taka, chociaż być może uzasadniona naturą faktycznie występujących w danych zależności, jest nie akceptowana z punktu widzenia celu, jakiemu ma służyć odkrywanie zależności i sposobu ich wykorzystywania, jako alternatywa pozostaje dekompozycja zbioru trenującego na podzbiory i poszukiwanie, odpowiednio wówczas prostszych, hipotez dla każdego z nich. Oczywiście dekompozycja taka nie może być arbitralna, lecz dokonana w systematyczny sposób ze względu na wartości wybranych atrybutów. Uzyskujemy wówczas hipotezy o ograniczonym zakresie stosowalności: wartości wybranych do dekompozycji atrybutów wyznaczają właściwą dla danego przykładu hipotezę. Każda hipoteza dostarczana jest wraz z warunkami określającymi zakres jej stosowania.

Specjalizowane struktury danych

Zostały zaprojektowane specjalne struktury danych ułatwiające algorytmom uczenia się bezpośrednie przetwarzanie dużych zbiorów danych. Nie możemy tu zbyt szczegółowo omawiać konretnych koncepcji, ale jako przykład warto wymienić $AD$-drzewa, struktury zapewniające efektywne zliczanie przykładów, co jest jedną z kluczowych operacji większości algorytmów odkrywania wiedzy.

Funkcja $AD$-drzewa polega na przechowywaniu informacji o liczbie przykładów spełniających dowolne warunki mające postać koniunkcji warunków dla pojedycznych atrybutów, które z kolei określają po prostu jedną wymaganą wartość atrybutu. Pojęcie docelowe może być przy tym uwzględniane w tych warunkach jako dodatkowy atrybut, co pozwala nie zajmować się nim odrębnie. Warunki takiej postaci możemy oczywiście reprezentować jako kompleksy złożone z selektorów pojedynczych i uniwersalnych. Skonstruowane dla zbioru trenującego $T$ i przechowywane w pamięci $AD$-drzewo umożliwia wyznaczenie liczby przykładów $\vert T_k\vert$ pokrywanych przez dowolny kompleks $k$ w stałym czasie, niezależnie od liczby przykładów w zbiorze $T$, co jest oczywiście znakomitym osiągnięciem. Przy konstrukcji drzewa decyzyjnego każdy podzbiór $P_{tr}$, na jaki aktualny zbiór przykładów $P$ jest dzielony przez test $t:X\mapsto R_t$ dla różnych $r\in R_t$, jest podzbiorem zbioru trenującego $T$ pokrywanym przez kompleks $k_P\land k_{tr}$, przy czym $k_P$ jest kompleksem reprezentującym koniunkcję warunków na ścieżce od korzenia drzewa do aktualnego węzła, a $k_{tr}$ jest kompleksem (atomowym) reprezentującym wynik $r$ testu $t$. Przy indukcji reguł trzeba uwzględnić dodatkowo selektory dysjunkcyjne, lecz wystarczy w tym celu zauważyć, że jeśli kompleks $k$ zawiera selektor $v_1\lor v_2\lor\dots\lor v_k$ na pozycji $i$, to

$$\vert T_k\vert = \sum_{j=1}^k\vert T_{k_j}\vert$$ (3)

przy czym dla $j=1,2,\dots,k$ każdy kompleks $k_j$ jest identyczny z kompleksem $k$, z wyjątkiem selektora na pozycji $i$, który jest selektorem pojedynczym $v_j$.

W $AD$-drzewie występują dwa rodzaje węzłów. Węzły warunków reprezentują pewne warunki (zestawy wartości atrybutów), nie przechowywane jednak w nich jawnie, a wynikające z ich położenia w drzewie, a dokładniej określone przez ścieżkę prowadzącą do nich od korzenia drzewa, który zawiera węzeł odpowiadający pustym warunkom, czyli kompleksowi uniwersalnemu. Każdy węzeł warunków jako węzły potomne posiada węzły atrybutów. Każdy węzeł atrybutu odpowiada jednemu określonemu na dziedzinie atrybutowi i wychodzą z niego gałęzie prowadzące do węzłów warunków, z których każda odpowiada jednej wartości tego atrybutu. Węzłami potomnymi węzła atrybutu $a_i$ są węzły warunków uwzględniające dodatkowy warunek dla poszczególnych wartości tego atrybutu. Aby ten mglisty opis słowny skonkretyzować, oznaczmy przez $n_k$ węzeł warunków odpowiadający warunkom reprezentowanym przez kompleks $k$, który zawiera liczbę $\vert T_k\vert$. Jeśli $k=\langle ?\rangle$, to węzeł ten znajduje się w korzeniu drzewa. W przeciwnym przypadku jego węzłem macierzystym jest pewien węzeł atrybutu, sam z kolei będący węzłem potomnym innego węzła warunków. Przez $n_{k,a_i}$ oznaczmy węzeł atrybutu odpowiadający atrybutowi $a_i$, będący węzłem potomnym węzła warunków $n_k$. Dla każdej wartości $v\in A_i$ atrybutu $a_i$ węzeł $n_{k,a_i}$ ma węzeł potomny $n_{k\land k_{a_iv}}$, gdzie $k_{a_iv}$ oznacza kompleks atomowy zawierający na pozycji $i$ selektor pojedynczy $v$. Aby uniknąć przy tym wielokrotnego występowania węzłów odpowiadających takim samym warunkom przyjmuje się, że jeśli węzeł warunków $n_k$ jest węzłem potomnym węzła atrybutu $n_{k',a_i}$, to z kolei jego węzłami potomnymi są wyłącznie węzły atrybutów o numerach większych od $i$, czyli $n_{k,a_{i+1}},n_{k,a_{i+2}},\dots, n_{k,a_n}$. Na najniższym poziomie znajdują się liście, które są węzłami warunków odpowiadającymi kompleksom zawierającym wyłącznie selektory pojedyncze, a więc nakładającym warunki na wartości każdego atrybutu.

Korzystanie z $AD$-drzew jest uzasadnione, jeśli do tego samego zbioru trenującego ma być wielokrotnie stosowany ten sam algorytm w różnych wersjach lub różne algorytmy uczenia się. Wówczas jednokrotny nakład obliczeń wymagany do zbudowania takiego drzewa jest ,,amortyzowany'' przez jego wielokrotne wykorzystanie.

Liczne atrybuty

Koszt obliczeniowy algorytmów indukcyjnego uczenia się zależy na ogół nie tylko od ,,długości'' zbioru trenującego, czyli liczby przykładów, lecz także od jego ,,szerokości'', czyli liczby atrybutów. Redukcja tej ostatniej może być również uzasadniona, zwłaszcza że może powodować uzyskanie prostszej, choć zapewne mniej dokładnej hipotezy. Chodzi tu oczywiście o usuwanie atrybutów nieistotnych lub mało istotnych, czyli o jeden z rodzajów konstruktywnej indukcji. Warto przy okazji przypomnieć, że także redukcja liczby wartości atrybutów przez ich dyskretyzację lub agregowanie może mieć korzystny wpływ na koszt uczenia się i złożoność uzyskiwanej hipotezy.

Liczne kategorie

Niekiedy możemy mieć do czynienia nie tylko z problemem wynikającym z dużej liczby atrybutów lub ich wartości, lecz także z dużą liczbą kategorii. Oczywiście ona także wpływa na koszt obliczeniowy algorytmów uczenia się, na przykład na obliczenie funkcji oceny testów przy indukcji drzew decyzyjnych. O ile typowe wartości liczby kategorii, wynoszące kilka lub kilkanaście, nie są na ogół źródłem szczególnych kłopotów, o tyle mając do czynienia z kilkudziesięcioma lub kilkuset kategoriami powinniśmy się liczyć z wyraźnym wzrostem nakładów obliczeniowych. Można wówczas wykonać swego rodzaju krok wstecz, czyli zastąpić pojęcie wielokrotne pewną liczbą pojęć pojedynczych.

Bezpośrednia realizacja powyższej koncepcji polegałaby na związaniu z każdą kategorią pojęcia wielokrotnego $c:X\mapsto C$ odpowiedniego pojęcia pojedynczego, odróżniającego przykłady tej kategorii od przykładów wszystkich innych kategorii, traktowanych jako negatywne. Z takim bezpośrednim podejściem wiążą się jednak pewne łatwe do zauważenia mankamenty. Po pierwsze, jeśli zgodnie z założeniem liczba kategorii $\vert C\vert$ jest duża, to wynosząca tyle samo liczba pojęć pojedynczych, dla których należałoby uczyć się odpowiednich hipotez, także może być poważnym problemem efektywnościowym. Jeśli koszt stosowanego algorytmu uczenia się zależy od kategorii co najwyżej liniowo, to w efekcie zamiast oszczędności uzyskamy co najmniej dwukrotne zwiększenie wymaganego łącznego czasu obliczeń, skoro w wyniku przekształcenia dla każdej kategorii pierwotnego pojęcia wielokrotnego wprowadzamy dwie kategorie odpowiadającego jej pojęcia pojedynczego. Po drugie, dla wszystkich lub większości z tych pojęć pojedynczych zbiór trenujący będzie się prawdopodobnie charakteryzował dużą nierównomiernością rozkładu kategorii, polegającą na znacznej przewadze liczebnej przykładów negatywnych. Na ogół nie wpływa ona dobrze na jakość uzyskiwanych hipotez, o czym będzie jeszcze mowa.

Lepsze podejście zarówno ze względu na łączne koszty obliczeniowe, jak i jakość uzyskiwanej hipotezy polega na zastosowaniu specjalnego binarnego kodowania kategorii pierwotnego pojęcia wielokrotnego. Poszczególne bity binarnego słowa kodowego reprezentującego każdą kategorię są następnie traktowane jako etykiety kategorii pojęć pojedynczych. Każde z nich reprezentuje podział zbioru kategorii $C$ pojęcia pierwotnego na dwa podzbiory $C^i_1$ i $C^i_0$, przy czym kategoriom jednego z nich odpowiada nowa kategoria $1$, a kategoriom drugiego nowa kategoria 0, zaś $i$ oznacza numer bitu. Jeśli podział ten jest dokonywany równomiernie, to wymagana liczba pojęć pojedynczych wynosi $\log_2\vert C\vert$ po zaokrągleniu w górę do najbliższej liczby całkowitej, a więc dla dużej liczby kategorii znacznie mniej niż $\vert C\vert$. Następnie dla każdego z tych pojęć następuje uczenie się odpowiedniej hipotezy. Uzyskujemy w ten sposób pewną liczbę $m$ hipotez, które należy na koniec odpowiednio połączyć przez głosowanie według następującego schematu:

$$h_*(x) = \mathrm{arg}\max_{d\in C}\sum_{i=1}^m\xi_i(h_i(x),d)$$ (4)

przy czym dla $d_1\in\{0,1\}$, $d_2\in C$ oraz $i=1,2,\dots,m$

$$\xi_i(d_1,d_2) = \begin{cases}1 & \text{jeśli $d_2\in C^i_{d_1}$,}\\ 0 & \text{jeśli $d_2\not\in C^i_{d_1}$.} \end{cases}$$ (5)

W ten sposób na podstawie $m$ hipotez $h_i:X\mapsto\{0,1\}$ otrzymujemy hipotezę $h_*:X\mapsto C$.

Nierównomierny rozkład kategorii

Cechą występującą w niektórych rzeczywistych zbiorach danych jest nierównomierny rozkład kategorii, gdy liczby przykładów trenujących poszczególnych kategorii znacznie się od siebie różnią. Szczególnie często występuje on dla pojęć pojedynczych, kiedy liczba przykładów pozytywnych może być bardzo niewielka w porównaniu z liczbą przykładów negatywnych albo przykłady pozytywne mogą wyraźnie przeważać liczebnie nad negatywnymi. Dla większości algorytmów taka nierównowaga nie wpływa dobrze na jakość uzyskiwanych hipotez, w każdym razie z punktu widzenia oczekiwań eksperymentatora. Jeśli w zbiorze trenującym $T$ przykłady pewnej kategorii $d\in C$ stanowią $100\cdot p$%, czyli $\frac{\vert T^d\vert}{\vert T\vert}=p$, to trywialna hipoteza zaliczająca każdy przykład do tej właśnie kategorii osiągnie na zbiorze $T$ błąd próbki równy $1-p$. Jeśli przewaga kategorii $d$ jest duża, to będzie to błąd niewielki i hipoteza taka formalnie mogłaby wydawać się dobra, skoro zapewniając mały błąd ma przy tym najmniejszą możliwą złożoność, lecz jest ona zupełnie niezadowalająca, jeśli oczekujemy odkrycia zależności występujących w danych, a więc tego, co odróżnia przykłady różnych kategorii.

Aby z opisanym negatywnym zjawiskiem sobie poradzić, stosuje się techniki niwelujące nierównomierność rozkładu kategorii w zbiorze trenującym. Można je podzielić na dwa zasadnicze rodzaje:

• techniki próbkowania stosowane do przykładów kategorii większościowych, zmniejszające ich liczbę,
• techniki replikacji stosowane do przykładów kategorii mniejszościowych, zwiększające ich liczbę.

Pierwsze podejście polega na wyborze, na ogół równomiernie losowym, pewnej liczby przykładów z każdej kategorii, która jest reprezentowana zbyt licznie w stosunku do pozostałych, dla których są wybierane wszystkie przykłady. Uzyskuje się w ten sposób podzbiór zbioru trenującego o bardziej równomiernym rozkładzie kategorii. Oczywiście różny losowy wybór przykładów, dając różne podzbiory, może także prowadzić do różnych hipotez. Można wówczas wygenerować ich pewną liczbę i wybrać najlepszą (być może ze względu na błąd próbki na całym zbiorze trenującym, jeśli nie jest dostępny oddzielny zbiór przykładów do testowania hipotez) lub wszystkie uzyskane hipotezy połączyć, zgodnie z zasadami metauczenia się, o którym będzie mowa niżej. Przy drugim podejściu dokonuje się sztucznego rozmnożenia przykładów kategorii zbyt słabo reprezentowanych w zbiorze trenującym. Jeśli faktyczna liczba przykładów pewnej kategorii wynosi $k$, a pożądana $k'>k$, to oczekiwana liczba kopii każdego przykładu tej kategorii, jakie wejdą w skład generowanego zbioru trenującego, jest równa $\frac{k'}{k}$. Wyboru przykładów do replikacji można dokonać losowo. Wówczas wielokrotne powtarzanie tego zabiegu może dać w efekcie inną hipotezę, więc stosuje się tu ta sama uwaga, jaka dotyczyła próbkowania.

Nie jest bynajmniej jasne, jaki dokładnie rozkład kategorii w zbiorze trenującym daje najlepsze wyniki, gdyż zależy to nie tylko od właściwości dziedziny, pojęcia docelowego i algorytmu uczenia się, lecz także od oczekiwać eksperymentara. Formalnie rzecz biorąc nie ma powodu do ingerowania w rozkład kategorii w zbiorze trenującym, jeśli zbiór ten pochodzi z tego samego rozkładu prawdopodobieństwa, który będzie następnie generował nowe przykłady, do klasyfikowania których uzyskana hipoteza miałaby być stosowana. Jeśli więc przykładów pewnej kategorii jest w zbiorze trenującym mało, to rzadko występują one w dziedzinie przy wyborze zgodnie z tym rozkładem prawdopodobieństwa, a tym samym popełniane dla nich pomyłki mają niewielki wpływ na błąd rzeczywisty hipotezy. Wszystko zatem byłoby w porządku, gdyby minimalizacja błędu rzeczywistego rzeczywiście zawsze była celem, jaki sobie stawiamy. Czasem jednak, a przy stosowaniu uczenia się do eksploracji baz danych szczególnie często, ważniejsze może być opisanie występującej zależności niż sama dokładność. Może być też tak, że w praktyce koszty pomyłek dla poszczególnych kategorii nie są jednakowe, a kryterium oceny hipotez jest nie tyle błąd, co raczej oczekiwany koszt popełnianych przez nią pomyłek.

Uwzględnianie kosztu pomyłek

Obliczając błąd hipotez każdą pomyłkę traktujemy tak samo, ale w niektórych zastosowaniach może nie być obojętnę, przykład jakiej kategorii błędnie zaklasyfikowano i do jakiej niepoprawnej kategorii został zaliczony. Niech dla każdych dwóch kategorii $d_1,d_2\in C$ będzie określony koszt $\rho(d_1,d_2)$ związany z pomyłkowym podaniem kategorii $d_1$ dla przykładu, którego poprawną kategorią jest $d_2$. Koszty mogą być dowolnymi liczbami nieujemnymi, chociaż wygodnie jest ograniczyć się do wartości z przedziału $[0,1]$.

Najbardziej naturalne jest uwaględnianie kosztu pomyłek w funkcjach oceny, jakie są przez większość algorytmów wykorzystywane w trakcie konstruowania hipotezy, a więc np. w kryterium stopu i wyboru testu dla drzew decyzyjnych, ocenie kompleksów przy indukcji reguł itd. W szczególności dla dowolnego zbioru przykładów $P$ możemy określić koszt pomyłek związanych z zaliczeniem ich wszystkich do kategorii większościowej w tym zbiorze:

$$\rho(P) = \sum_{x\in P}\rho(d_P, c(x))$$ (6)

gdzie $d_P$ jest większościową kategorią w $P$. Taka wielkość obliczona dla zbioru przykładów pokrywanych przez kompleks może służyć do oceny jakości kompleksu przy indukcji reguł. Z kolei przy wyborze testu można odpowiednią wielkość obliczać dla każdego z podzbiorów, na jakie test dzieli aktualny zbiór przykładów, i ważoną średnią wyników uznać za funkcję oceny testu.

Charakteryzowanie rozkładu pomyłek

Niezależnie od tego, czy zostały zastosowane techniki uwrażliwiające algorytm stosowany do generowania hipotezy na koszty pomyłek, w praktyce często występuję potrzeba scharakteryzowania rozkładu pomyłek, jakie popełnia uzyskana hipoteza. Wykorzystuje się w tym celu macierz pomyłek, w której wiersze i kolumny odpowiadają kategoriom, a element $e(d_1,d_2)$ w wierszu $d_1$ i kolumnie $d_2$ oznacza liczbę pomyłek polegających na podaniu kategorii $d_1$ w miejsce poprawnej kategorii $d$ popełnionych przez hipotezę na pewnym zbiorze przykładów.

W przypadku pojęć pojedynczych o zbiorze kategorii $C=\{0,1\}$, jakie występują często w zagadnieniach diagnostycznych (diagnostyka medyczna, diagnostyka mechaniczna lub elektroniczna, wykrywanie nadużyć itp.) możliwa jest lepsza charakterystyka rozkładu pomyłek z punktu widzenia celu, do jakiego hipoteza ma służyć. Poszczególne elementy macierzy pomyłek mogą być wówczas opisane następująco:

• $e(0,0)$ -- liczba prawdziwych negatywnych (true negatives),
• $e(0,1)$ -- liczba fałszywych negatywnych (false negatives),
• $e(1,0)$ -- liczba fałszywych pozytywnych (false positives),
• $e(1,1)$ -- liczba prawdziwych pozytywnych (true positives),

według konwencji, w której ,,prawdziwy'' oznacza przykład poprawnie zaklasyfikowany i ,,fałszywy'' oznacza przykład niepoprawnie zaklasyfikowany. Na podstawie tych wartości oblicza się współczynniki charakteryzujące skuteczność hipotezy w wykrywaniu ,,interesujących'' przypadków, które umownie oznacza kategoria $1$, np.::

dokładność:

procent przykładów poprawnie zaklasyfikowanych,

$$\frac{e(0,0)+e(1,1)}{e(0,0)+e(0,1)+e(1,0)+e(1,1)},$$ (7)

błąd:

procent przykładów błędnie klasyfikowanych,

$$\frac{e(0,1)+e(1,0)}{e(0,0)+e(0,1)+e(1,0)+e(1,1)},$$ (8)

skuteczność (recall):

procent przykładów pozytywnych, które zostały wykryte,

$$\frac{e(1,1)}{e(0,1)+e(1,1)},$$ (9)

precyzja (precision):

procent przykładów wykrytych, które są pozytywne,

$$\frac{e(1,1)}{e(1,0)+e(1,1)}.$$ (10)

Niekompletne dane

W wielu dziedzinach na porządku dziennym jest występowanie w bazach danych rekordów, dla których wartości niektórych pól nie są wypełnione. Niekompletność informacji może wynikać z różnych przyczyn, zależnie od specyfiki bazy danych.W zależności od dziedziny należy liczyć się z tym, że dla kilku lub nawet kilkudziesięciu procent przykładów trenujących będą występowały nieznane wartości pewnych atrybutów, przy czym dla niektórych przykładów może wystąpić taka sytuacja, że wartości nieznanych jest nawet więcej niż znanych.

Można wskazać następujące podstawowe podejścia do problemu brakujących wartości atrybutów:

1. Ignorowanie przykładów z brakującymi wartościami.
2. Traktowanie braku wartości jako specjalnej dodatkowej wartości.
3. Wypełnianie brakujących wartości.
4. Zastępowanie przykładów z brakującymi wartościami przykładami ułamkowymi.

Pierwsza możliwość nie zasługuje na szerszy komentarz. Może to być dobre podejście tylko jeśli brakujące wartości zdarzają się bardzo rzadko i wyłącznie na etapie uczenia się hipotezy -- podczas stosowania hipotezy ignorowanie przykładu z brakującymi wartościami atrybutów byłoby niedopuszczalną odmową klasyfikacji.

Druga możliwość polega w istocie na poszerzeniu przeciwdziedziny $A$ każdego atrybutu $a:X\mapsto A$ o dodatkową wartość interpretowaną jako ,,nieznana''. Jest to technika bardzo prosta w realizacji, która może w niektórych przypadkach być skuteczna, jeśli założymy, że braki wartości poszczególnych atrybutów są raczej częste (tak aby wartość ,,nieznana'' mogła być odpowiednio uwzględniona w odkrywanej zależności) i równie częste w danych trenujących, co w nowych danych do klasyfikacji (jest to warunek reprezentatywności zbioru trenującego). Założenia te nie zawsze są spełnione, a w szczególności można sobie wyobrazić sytuację, że dane trenujące są znacznie bardziej kompletne, niż dane do których ma być następnie stosowana hipoteza, co wyklucza stosowanie tej techniki.

Dwa pozostałe podejścia są bardziej zaawansowane i uniwersalne, więc warto o nich powiedzieć więcej.

Wypełnianie brakujących wartości

Podejście to jest uniwersalne i nie wymaga żadnych szczególnych właściwości algorytmu uczenia się ani hipotez, gdyż sprowadza się do odpowiedniego wstępnego przetwarzania danych. Na podstawie analizy zbioru trenującego gromadzone są informacje pozwalające na wypełnianie brakujących wartości -- zarówno w danych trenujących, jak i w przykładach, do których później będzie stosowana hipoteza. Możliwe są następujące warianty wypełniania wartości atrybutu $a$ dla przykładu $x$:

• najczęściej występującą wartością atrybutu $a$ w zbiorze trenującym,
• najczęściej występującą wartością atrybutu $a$ w zbiorze w zbiorze przykładów trenujących o kategorii $c(x)$,
• wartością ustaloną na podstawie znanych wartości innych atrybutów dla przykładu $x$ i jego kategorii $c(x)$ za pomocą hipotezy uzyskanej przez uczenie się pojęcia docelowego identycznego z atrybutem $a$, jeśli jest to atrybut dyskretny, lub aproksymacji funkcji identycznej z $a$, jeśli jest to atrybut ciągły, z wykorzystaniem pewnego algorytmu uczenia się.

Ta ostatnia najbardziej zaawansowana wersja wypełniania polega na zastosowaniu pewnego algorytmu uczenia się, dla którego pojęciem docelowym (lub funkcją docelową) będzie atrybut z brakującymi wartościami, po to aby następne uzyskaną hipotezę zastosować do wypełniania tych wartości. Jednak postępowanie takie znacznie koszt obliczeniowy uczenia się i powinno być stosowane tylko z prostymi algorytmami uczenia się, które same dobrze sobie radzą z brakującymi wartościami (gdyż oczywiście przykłady mogą mieć brakujące wartości więcej niż jednego atrybutu). Dobrym kandydatem jest naiwny klasyfikator bayesowski.

Przykłady ułamkowe

Technika ta wymaga ona związania z każdym przykładem liczby jego egzemplarzy. Zwykle każdy przykład ma dokładnie jeden egzemplarz, lecz przykłady ułamkowe mają liczbę egzemplarzy między 0 a $1$. Przykład z nieznaną wartością atrybutu zostaje zastąpiony zbiorem przykładów ułamkowych ze wszystkimi wartościami tego atrybutu występującymi w zbiorze $P$; dla każdej z nich liczba egzemplarzy jest ustalona jako stosunek liczby przykładów w zbiorze trenującymi z taką wartością atrybutu $a$ do liczby wszystkich przykładów trenujących ze znaną wartością tego atrybutu. Jeśli brakujących wartości atrybutów dla przykładu jest więcej, należy ponawiać to postępowanie dla każdego atrybutu, ,,dzieląc'' dalej przykłady ułamkowe.

Nie każdy algorytm uczenia się jest w stanie odpowiednio przetwarzać przykłady ułamkowe. Przykładem jest algorytm AQ, który wymaga używania pojedynczych wybranych przykładów jako ziaren. Jednak większość algorytmów, które nie przetwarzają pojedynczych przykładów, lecz posługują się liczbami przykładów spełniających określone warunki, może być z powodzeniem zastosowana do generowania hipotez na podstawie zbiorów trenujących z przykładami ułamkowymi. Liczbę elementów w pewnym zbiorze przykładów wystarczy traktować jako sumę liczb egzemplarzy poszczególnych przykładów. Jest to możliwe np. w przypadku indukcji drzew decyzyjnych, algorytmu indukcji reguł CN2 czy naiwnego klasyfikatora bayesowskiego, a także algorytmu grupowania COBWEB.

Wykorzystanie przykładów ułamkowych przy klasyfikacji przykładu z brakującymi wartościami atrybutów oznacza w istocie oddzielne klasyfikowanie każdego przykładu ułamkowego, a następnie przeprowadzenie głosowania, w którym każda z uzyskanych kategorii ma wagę równą liczbie egzmeplarzy przykładu ułamkowego, dla którego ją wyznaczono.

Niepoprawne dane

W wielu bazach danych wartości niektórych atrybutów, zwłaszcza pochodzących z pomiarów, są w naturalny sposób obarczone błędami, czy, jak mówimy, zaszumione. Stwarza to ryzyko odkrycia zależności nadmiernie dopasowanych do przypadkowych danych. Zależności takie, nawet jeśli zachodzą z dużą dokładnością dla dotychczas dostępnych rekordów, nie są na ogół wystarczająco dokładne dla nowych rekordów, co pozbawia je wartości predykcyjnej.

O zapobieganie nadmiernemu dopasowaniu można zadbać zarówno podczas znajdowania zależności (akceptując tylko zależności statystycznie istotne), jak i poddając modyfikacji znalezione już zależności przez ich upraszczanie. Ten ostatni proces przybiera postać przycinania drzew decyzyjnych (kiedy wybrany fragment drzewa jest usuwany i zastępowany liściem), reguł (kiedy są usuwane niektóre ich warunki) czy w inny sposób reprezentowanych hipotez. Chociaż pogarsza to obserwowaną dokładność tych zależności dla rekordów znajdujących się w bazie danych, zwiększa ich oczekiwaną dokładność dla nowych rekordów. Jak pamiętamy, powszechnie przyjmuje się, zgodnie z zasadą brzytwy Ockhama, że prawdopodobieństwo przypadkowego dopasowania do danych prostych zależności jest znacznie mniejsze niż złożonych zależności.

W przypadku atrybutów, w których wartościach normalnie nie powinny występować błędy, odkrywanie zależności może doprowadzić do stwierdzenia anomalii, które mogą świadczyć o wystąpieniu nieprzewidzianych błędów (np. spowodowanych przez operatora). Najprostszym rodzajem anomalii, występującym dla atrybutów ciągłych, są wartości izolowane. Są to wartości atrybutu ciągłego występujące tylko dla nielicznych przykładów i znacznie odbiegające od wartości, jakie ten atrybut przyjmuje dla pozostałych przykładów. Anomalie mogą być także obserwowane jako wyjątki od dokładnej reguły lub jako reguły pokrywające bardzo małą liczbę przykładów.

Metauczenie się

Jedną z bardzo przydatnych praktycznie technik poprawiania dokładności klasyfikacji dla rzeczywistych zbiorów danych jest metauczenie się. Wobec trudności, jakie mogą w praktyce występować przy próbie znalezienia jednej hipotezy o zadowalającej dokładności i złożoności, koncepcja ta polega na znajdowaniu pewnej liczby hipotez, które nazwiemy hipotezami bazowymi, i odpowiednim ich łączeniu. Poszczególne hipotezy bazowe muszą być dostatecznie proste, lecz niekoniecznie dokładne dla całej dziedziny. Często wystarczają hipotezy niezwykle proste o dokładności tylko niewiele lepszej od losowej. Odpowiedni sposób połączenia sprawia, że uzyskana w jego wyniku metahipoteza będzie co najmniej tak samo dokładna jak najlepsza z tych hipotez, a często umożliwi zdecydowaną poprawę dokładności.

Pełne określenie konkretnej formy metauczenia się polega na podaniu metod generowania oraz łączenia hipotez bazowych. W poniższej dyskusji tych metod założymy, że na podstawie zbioru trenującego $T$ ma powstać zbiór liczący $m>1$ hipotez bazowych $H=\{h_1,h_2,\dots,h_m\}$, które następnie należy połączyć w jedną metahipotezę $h_*$.

Generowanie hipotez bazowych

Aby związane z metauczeniem się nadzieje na uzyskanie metahipotezy o błędzie rzeczywistym mniejszym od błędów każdej wykorzystywanej przez nią hipotezy bazowej mogły się ziścić, hipotezy te muszą być różne, czyli w różny sposób klasyfikować niektóre przykłady z dziedziny. Jeśli dla pewnego przykładu hipotezy bazowe różnią się przypisywanymi mu kategoriami, to część z nich popełnia dla tego przykładu pomyłkę, a część, być może, klasyfikuje go poprawnie. Jeśli dla różnych przykładów poprawnej klasyfikacji będą dokonywać różne hipotezy, to istnieje przynajmniej teoretyczna możliwość otrzymania z ich połączenia metahipotezy popełniającej mniej pomyłek niż najlepsza z nich. Zależy nam zatem na uzyskaniu pewnej liczby hipotez bazowych niezależnych od siebie, a ściślej takich, dla których popełniane pomyłki są niezależne lub co najwyżej słabo zależne. Przedstawimy kilka najczęściej wykorzystywanych metod generowania takich hipotez.

Stosowanie różnych algorytmów.

Najbardziej bezpośrednim podejściem do generowania różnych niezależnych hipotez bazowych jest użycie do uzyskania każdej z nich innego algorytmu uczenia się. W szczególnym przypadku może to oznaczać także użycie tego samego algorytmu z różnymi parametrami, jeśli w istotny sposób wpływają na jego działanie. Poszczególne hipotezy bazowe możemy zatem generować stosując algorytmy indukcji drzew decyzyjnych (być może w kilku wersjach, różniących się rodzajem używanych testów lub kryterium wyboru testu), algorytmy indukcji reguł (także być może w kilku odmianach, różniących się strategią przeszukiwania przestrzeni kompleksów lub heurystycznymi funkcjami oceny ich jakości), naiwny klasyfikator bayesowski czy dowolny inny algorytm uczenia się pojęć. Przy tym podejściu liczba hipotez bazowych rzadko przekracza kilka i każda z nich jest znajdowana przez inny algorytm na podstawie zazwyczaj tego samego, całego zbioru trenującego.

Próbkowanie zbioru trenującego.

Najprostsze podejście stosowane wówczas, gdy jest dostępny jeden algorytm uczenia się, polega na jego wielokrotnym stosowaniu do wybranych losowo niezależnie od siebie podzbiorów zbioru trenującego, które możemy nazwać bazowymi zbiorami trenującymi. Daje to dobre efekty w przypadku algorytmów, dla których nawet niewielkie zmiany przykładów trenujących mogą znacząco zmienić uzyskiwaną przez nie hipotezę. Do takich algorytmów, nazywanych niestabilnymi, należą między innymi algorytmy indukcji drzew decyzyjnych i reguł. Najprostszy wariant techniki próbkowania polega na wybraniu każdego z $m$ bazowych zbiorów trenujących, mających służyć do uzyskania odpowiednio $m$ hipotez bazowych, przez niezależne losowanie ze zwracaniem $r\vert T\vert$ przykładów z całego zbioru trenującego $T$, przy czym $r\in(0,1]$ jest współczynnikiem określającym stosunek rozmiaru każdego podzbioru do rozmiaru całego zbioru trenującego. Wartość $r$ nie musi wynosić $\frac{1}{m}$, często jest ona raczej wyraźnie większa i sięga $\frac{2}{3}$, jeśli pozwala na to koszt obliczeń. Nawet jeśli $r=1$, co jest także częstym wyborem (tak działa popularna wersja metauczenia się znana pod nazwą bagging), ze względu na mechanizm losowania ze zwracanie dostajemy bazowe zbiory trenujące, które mają taki sam rozmiar jak pierwotny zbiór $T$, lecz w każdym z nich niektóre przykłady z $T$ się nie znajdują, a niektóre występują wielokrotnie. Inne możliwe podejście polega na dokonaniu w sposób losowy podziału zbioru $T$ na $m$ równolicznych (w przybliżeniu) rozłącznych podzbiorów $T_1,T_2,\dots,T_m$. W celu uzyskania hipotezy bazowej $h_i$ używany jest bazowy zbiór trenujący powstały przez połączenie $m-1$ podzbiorów $T_j$ dla $j\neq i$. Trzecia i bardziej zaawansowana technika polega na konstruowaniu kolejno $m$ rozkładów prawdopodobieństwa określonych na zbiorze $T$ i wybieraniu przykładów do każdego z bazowych zbiorów trenujących przez losowanie ze zwracaniem według odpowiadającego mu rozkładu. Pierwszy rozkład jest równomierny, czyli daje każdemu przykładowi jednakowe prawdopodobieństwo wyboru. Każdy następny powstaje na podstawie poprzedniego przez zwiększenie prawdopodobieństwa przykładów błędnie klasyfikowanych przez uzyskaną na jego podstawie hipotezę bazową. Takie postępowanie jest charakterystyczne dla popularnej odmiany metauczenia się znanej jako boosting.

Modyfikacje przestrzeni atrybutów.

Różne hipotezy bazowe można uzyskać także stosując jeden algorytm uczenia się do jednego zbioru trenującego, zmieniając jednak zestaw atrybutów używanych do opisu przykładów. Różne zestawy atrybutów prowadzą do uzyskania różnych hipotez bazowych. W najprostszej wersji tego podejścia zestaw wszystkich atrybutów określonych na dziedzinie jest dzielony na podzbiory w sposób ustalony bądź na podstawie dostępnej wiedzy o dziedzinie (zazwyczaj przez wydzielanie atrybutów jakoś ze sobą powiązanych, opisujących podobne właściwości przykładów), bądź arbitralnie, w szczególności losowo. Zbiór trenujący rzutowany na poszczególne podzbiory zbioru wszystkich atrybutów służy następnie do generowania hipotez przez zastosowanie tego samego w każdym przypadku algorytmu. Poszczególne zestawy atrybutów nie muszą być i na ogół nie są rozłączne, powinny się jednak różnić na tyle, aby mógł być spełniony postulat niezależności pomyłek popełnianych przez poszczególne hipotezy. Takie podejście może znaleźć zastosowanie tylko w przypadku, gdy liczba atrybutów określonych na dziedzinie jest dostatecznie duża.

Randomizacja algorytmów.

Innym sposobem uzyskania wielu różnych hipotez za pomocą tego samego algorytmu na podstawie tego samego zbioru przykładów jest randomizacja algorytmów uczenia się, czyli wprowadzenie do nich modyfikacji, powodujących pewien niedeterminizm ich działania. Dzięki temu wielokrotne zastosowanie tego samego algorytmu do tych samych danych będzie dawać do pewnego stopnia różne wyniki. Najprostszy sposób wprowadzenia losowości do wielu różnych algorytmów uczenia się pojęć polega na wykorzystaniu w tym celu funkcji heurystycznych używanych w nich do kierowania przeszukiwaniem przestrzeni hipotez. Dodając do ich wartości niewielki składnik losowy, spowodujemy, że przy kolejnych uruchomieniach algorytmu niektóre z wybranych kierunków przeszukiwania będą inne. W szczególności może tu chodzić o funkcję oceny testów przy indukcji drzew decyzyjnych oraz oceny kompleksów przy indukcji reguł. Losowy składnik funkcji oceny może być liczbą wygenerowaną według rozkładu normalnego o wartości oczekiwanej równej 0 i odpowiednio dobranym odchyleniu standardowym. W praktyce wygodniejsze może być jednak pozostawienie zwykłych deterministycznych funkcji oceny, lecz odstąpienie od ich deterministycznej maksymalizacji na rzecz maksymalizacji randomizowanej, w której jest wybierana niekoniecznie możliwość o największej wartości funkcji oceny, lecz raczej w sposób losowy dowolna z pewnej ustalonej liczby najwyżej ocenionych możliwości. Dla nowego węzła przy zstępującym konstruowaniu drzewa decyzyjnego możemy zatem wybrać test losowo spośród $25$% najlepszych testów, a ograniczając rozmiar gwiazdy przy generowaniu kompleksów pozostawić w niej $m$ losowo wybranych elementów spośród jej $2m$ najlepszych elementów, aby dla przykładu użyć konkretnych liczb. Oczywiście nietrudno jest zaproponować znacznie więcej konkretnych technik randomizacji algorytmów uczenia się.

Modyfikacje kategorii.

Opisana wyżej technika binarnego kodowania kategorii, przedstawiona jako środek zaradczy na dużą liczbę kategorii, jest w istocie także pewną techniką metauczenia się.

Łączenie hipotez bazowych

Od dowolnej metody łączenia hipotez bazowych oczekujemy przynajmniej, że utworzona przez nią metahipoteza $h_*$ nie będzie hipotezą gorszą ze względu na błąd rzeczywisty od najdokładniejszej z nich. Metauczenie się można jednak uznać za udane tylko pod warunkiem, że metahipoteza będzie lepsza od wykorzystywanych przez nią hipotez bazowych. Można zaproponować różne metody konstruowania metahipotez, co do których można się spodziewać, że spełnią takie oczekiwania. Są wśród nich wprawdzie także metody bardzo specyficzne, zależne od reprezentacji hipotez bazowych, lecz tutaj zajmiemy się tylko metodami uniwersalnymi, które mogą być stosowane dla dowolnych reprezentacji. Większość z nich nie zależy także od pochodzenia hipotez bazowych.

Głosowanie.

Najprostszy i jednocześnie najczęściej stosowany, a przy tym nie najmniej skuteczny sposób łączenia hipotez bazowych, to głosowanie. W najprostszym przypadku, gdy głos każdej hipotezy bazowej liczy się tak samo, metahipoteza jest definiowana dla każdego przykładu $x\in X$ następująco:

$$h_*(x) = \mathrm{arg}\max_{d\in C}\big\vert\{h\in H \;\vert\; h(x)=d\}\big\vert$$ (11)

przy czym $H$ oznacza zbiór hipotez bazowych. Mimo prostoty metoda ta daje zazwyczaj bardzo dobre efekty. W wersji bardziej zaawansowanej jest stosowane ważone głosowanie, przy którym każdej hipotezie $h\in H$ odpowiada waga $w_h$ określająca ,,siłę'' jej głosu przy głosowaniu. Wówczas mamy:

$$h_*(x) = \mathrm{arg}\max_{d\in C} \sum_{h\in\{h'\in H \;\vert\; h'(x)=d\}}w_h$$ (12)

W celu uzyskania metahipotezy o możliwie minimalnym błędzie rzeczywistym przy ustalaniu wag hipotez można uwzględnić ich błędy próbki, przyznając mniej dokładnym hipotezom mniejszy wpływ na wynik głosowania. Jedna z (wielu) możliwości określenia wagi hipotezy $h$ na podstawie jej błędu jest następująca:

$$w_h = \log\frac{1-e^c_T(h)}{e^c_T(h)}$$ (13)

Maksymalizacja prawdopodobieństwa.

Za szczególną wersję ważonego głosowania można uznać wyznaczanie metahipotezy w sposób probabilistyczny, oparty na zasadach klasyfikacji bayesowskiej. Może tu znaleźć zastosowanie w szczególności optymalny klasyfikator bayesowski, niepraktyczny w innych zastosowaniach ze względu na dużą liczbę hipotez, jakie musiałby w nich łączyć. Aby w tym przypadku było możliwe jego użycie, każdej hipotezie bazowej $h\in H$ musi zostać przypisane odpowiednie prawdopodobieństwo a priori $\mathrm{Pr}(h)$ oraz należy określić zasady wyznaczania prawdopodobieństw danych trenujących $\mathrm{Pr}(T\,\vert\,h)$. Wówczas wyznaczone zgodnie ze wzorem Bayesa prawdopodobieństwa a posteriori poszczególnych hipotez bazowych $\mathrm{Pr}(h\,\vert\,T)$ służą jako ich wagi przy ważonym głosowaniu. Inne i w gruncie rzeczy prostsze podejście polega na użyciu naiwnego klasyfikatora bayesowskiego, wybierającego kategorie przykładów według zasady:

$$h_*(x_*) = \mathrm{arg}\max_{d\in C} \mathrm{Pr}_{x\in\Omega}\Big(c(x)=d\,\vert\, \bigwedge_{i=1}^mh_i(x)=h_i(x_*)\Big)$$ (14)

co w zwykły sposób, stosując wzór Bayesa i założenie o niezależności, można zastąpić przez

$$\begin{split}h_*(x_*) ={}& \mathrm{arg}\max_{d\in C}\Big[\mat... ...ig(h_i(x)=h_i(x_*)\,\vert\,c(x)=d\big)\Big]\text{.} \end{split}$$ (15)

Zauważmy, że hipotezy bazowe są w tym podejściu traktowane jak atrybuty; na podstawie ich wartości ustala się wartość metahipotezy.

Uczenie się na wyższym poziomie.

Ostatnia propozycja stanowi w istocie przykład zastosowania bardziej ogólnego podejścia do łączenia hipotez bazowych, w którym rolę naiwnego klasyfikatora bayesowskiego może przejąć dowolny algorytm uczenia się. Rolę atrybutów odgrywałyby dla niego hipotezy bazowe. Hipoteza byłaby wówczas wyznaczana w wyniku zastosowania tego algorytmu do zbioru trenującego $T$, rzutowanego na zbiór hipotez bazowych $H$, co oznacza opis przykładów za pomocą etykiet przypisywanych im przez wszystkie hipotezy z tego zbioru. W ten sposób metahipoteza może być reprezentowana przez drzewo decyzyjne lub zbiór reguł, które wyznaczają kategorię każdego przykładu na podstawie kategorii, do których ten przykład został zaliczony przez poszczególne hipotezy bazowe. Takie uczenie się na wyższym poziomie jest niewątpliwie pociągającą koncepcją, w pełni uzasadniającą termin ,,metauczenie się'', lecz zazwyczaj dostatecznie dobre efekty znacznie mniejszym kosztem można uzyskać stosując podane wyżej prostsze podejścia.

Literatura

1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdział 10.2.)

About this document ...

Metody odkrywania wiedzy: wykład 10
Od uczenia się do odkrywania wiedzy

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation mow-w10.tex

The translation was initiated by Pawel Cichosz on 2004-02-12