Metody odkrywania wiedzy: wykład 9
Konstruktywna indukcja

Paweł Cichosz


Date: 2001/2002

Wykład dotyczy modyfikacji przestrzeni atrybutów innych niż dyskretyzacja atrybutów ciągłych (i zbliżona do niej agregacja atrybutów porządkowych), których dokonanie może poprzedzać zastosowanie metod odkrywania wiedzy i ułatwiać jej efektywne znajdowanie.

Przestrzeń atrybutów a przestrzeń hipotez

Przestrzeń atrybutów jest w przypadku odkrywania wiedzy zazwyczaj dana z góry i, wydawać by się mogło, raz na zawsze. Pozornie z jej ewentualnych modyfikacji nie może wyniknąć żaden pożytek, gdyż i tak wszelkie dostępne dane są opisane za pomocą pierwotnej przestrzeni atrybutów, a zmiana atrybutów co najwyżej zmieni sposób zapisu tych danych.

Informacyjna zawartość atrybutów

Powyższe rozumowanie jest jednak poprawne tylko o tyle, że trafnie wskazuje na niemożność stworzenia żadnej informacji, której nie ma w wartościach atrybutów, za pomocą których są opisywane przykłady. Eliminując niektóre atrybuty, zastępując je innymi, dodając nowe, można doprowadzić do sytuacji, w której część informacji dostępnej w danych zniknie, lecz nigdy nie pojawi się żadna informacja nowa. Jednak sensowność przekształcania atrybutów, opiera się ona na zupełnie innych przesłankach niż ich ,,informacyjna zawartość''. Modyfikacje przestrzeni atrybutów warto czasem brać pod uwagę nie dlatego, że pozwalają o dziedzinie wiedzieć więcej, lecz dlatego, że pozwalają tę wiedzę lepiej reprezentować. Wiąże się to z wpływem przestrzeni atrybutów na przestrzeń rozpatrywanych przez hipotez, dzięki któremu zastosowanie odpowiednich przekształceń może niekiedy umożliwić uzyskanie przez ten sam algorytm hipotez lepszych -- bardziej dokładnych, mniej złożonych, bardziej czytelnych dla człowieka -- niż dla oryginalnego zestawu atrybutów.

Atrybuty a reprezentacja

Przestrzeń hipotez może zależeć w ogólnym przypadku od algorytmu uczenia się, a dokładniej od przyjmowanej przez ten algorytm metody reprezentacji hipotez. Skoro jednak przykłady są widziane jako wektory wartości atrybutów, to maksymalna możliwa przestrzeń hipotez zależy od zestawu atrybutów. Niektóre metody reprezentacji hipotez, takie jak drzewa decyzyjne lub zbiory reguł, umożliwiają reprezentowanie wszystkich dopuszczalnych hipotez dla danego zestawu atrybutów. Z kolei w postaci pojedynczych kompleksów mogą być wyrażone tylko niektóre hipotezy pojęć pojedynczych.

Zmiana obciążenia absolutnego

Jeśli stosowana przez algorytm uczenia się (czy ogólniej: odkrywania wiedzy) metoda reprezentacji hipotez umożliwia reprezentowanie wszystkich dopuszczalnych hipotez dla danego zestawu atrybutów, to modyfikacja tego zestawu może spowodować, że przestrzeń hipotez się skurczy, lecz na pewno się nie poszerzy. Usuwając dowolne atrybuty lub wprowadzając nowe atrybuty funkcyjnie od nich zależne przestrzeń hipotez możemy jedynie zawęzić, albo więc nie zmieni się ona w wyniku naszych poczynań w ogóle, albo stanie się mniejsza. Wprawdzie dodanie nowych atrybutów lub zastąpienie dotychczasowych atrybutów nowymi atrybutami o większej liczbie wartości zwiększa liczbę możliwych do wyrażenia za ich pomocą hipotez dopuszczalnych, lecz jest to tylko pozorne poszerzenie, gdyż wobec funkcyjnej zależności nowych atrybutów od atrybutów oryginalnych liczba faktycznie różnych (a nie tylko reprezentowanych w różny sposób) hipotez pozostanie w najlepszym razie taka sama, a być może się zmniejszy. Ograniczenie przestrzeni hipotez możemy traktować jako wprowadzenie dodatkowego obciążenia absolutnego.

Takie przekształcenia atrybutów, jeśli są odpowiednio dobrane, mogą usunąć z przestrzeni hipotez hipotezy najbardziej złożone, dla których istnieje duże ryzyko nadmiernego dopasowania i które byłyby nieczytelne dla człowieka, ułatwiając w ten sposób znalezienie hipotez prostszych i bardziej czytelnych -- choć może mniej dokładnie opisujących pojęcie docelowe. Stanie się tak w szczególności w przypadku eliminacji niektórych atrybutów, które są mało istotne ze względu na kategorie pojęcia docelowego, a których uwzględnienie w opisie przykładów sprzyja komplikowaniu hipotez. Poza tym ewentualne zawężenie przestrzeni hipotez upraszcza problem jej przeszukiwania. W związku z tym zmiana taka będzie korzystna pod warunkiem, że hipoteza uznana przez wybrany algorytm uczenia się za najlepszą z nowej przestrzeni nie będzie gorsza (czyli nie będzie miała większego błędu rzeczywistego) od tej, jaką ten sam algorytm wybrałby z przestrzeni oryginalnej.

Zmiana obciążenia preferencji

Mówiąc o zawężeniu przestrzeni hipotez, jakie może wynikać z modyfikacji przestrzeni atrybutów, trzeba odróżnić możliwość reprezentowania różnych hipotez ,,w zasadzie'' i możliwość ich reprezentowania w praktyce w rozsądny sposób. Dla skuteczności algorytmu odkrywania wiedzy ma bowiem znaczenie nie tylko to, czy jest on w stanie reprezentować określone hipotezy -- i w związku z tym można korzystając z tego algorytmu ich się nauczyć -- lecz także to, czy można je reprezentować w prosty sposób -- i wtedy można się ich nauczyć efektywnie. Algorytmy uczenia się nie przeszukują na ogół wyczerpująco całej przestrzeni hipotez, lecz poruszają się po niej, stosując pewne heurystyczne strategie przeszukiwania w celu wyboru najbardziej obiecujących kierunków poszukiwań. Można się wówczas spodziewać, że zmiana przestrzeni atrybutów, nawet nie zmieniając przestrzeni hipotez, wpłynie na to, którą hipotezę z tej przestrzeni dany algorytm uczenia się wybierze oraz jakim kosztem tego dokona. Jeśli zmiana ta spowoduje poprawę jakości hipotezy lub kosztu jej uzyskania, to będziemy mieli do czynienia z pozytywnym skutkiem przekształcania atrybutów. Zmiana zestawu atrybutów może zatem zmienić w korzystny sposób obciążenie preferencji, przyczyniając się do uzyskania lepszych hipotez.

Rodzaje przekształceń

Weźmiemy pod uwagę następujące podstawowe rodzaje przekształcania zestawu atrybutów:

Usuwanie atrybutów może zawęzić przestrzeń hipotez. Jeśli jednak usuwane atrybuty są nieistotne w tym sensie, że hipotezy dobrze przybliżające pojęcie docelowe nie zależą od ich wartości dla wszystkich lub większości przykładów dziedziny, to takie ograniczenie w niczym nie zmniejsza możliwości algorytmu uczenia się, a ułatwia stojący przed nim problem przeszukiwania, skoro przeszukiwana przestrzeń staje się dzięki eliminacji atrybutów mniejsza.

Dodawanie nowych atrybutów nie ogranicza przestrzeni hipotez, lecz nie może także, zgodnie z wcześniejszą dyskusją, jej poszerzać. Może natomiast prowadzić do tego, że pewne hipotezy mają za pomocą nowych atrybutów prostszą reprezentację. Takie nowe atrybuty są zawsze ściśle zależne funkcyjnie od atrybutów oryginalnych -- dla każdego przykładu wartość nowego atrybutu może być wyznaczona na podstawie wartości dla tego przykładu wszystkich lub niektórych atrybutów oryginalnych. Wiąże się to z tym, że informacyjna zawartość przestrzeni atrybutów nie ulega przez dodanie do niej nowych atrybutów żadnej zmianie.

Zastępowanie pierwotnie istniejących atrybutów nowymi to nic innego jak usuwanie pierwszych i dodawanie drugich, czyli złożenie dwóch poprzednich rodzajów przekształceń, przy czym dodawane atrybuty są funkcyjnie zależne od usuwanych. Takie przekształcenie jest w praktyce najczęstsze, a jego szczególnym przypadkiem jest omawiana oddzielnie dyskretyzacja atrybutów ciągłych. Zależnie od sytuacji, może ono prowadzić do zawężenia lub pozostawienia bez zmian przestrzeni hipotez, lecz w każdym przypadku ma na celu ułatwienie jej skutecznego przeszukiwania. W ten sposób atrybuty, który są istotne i nie mogą zostać w zwykły sposób usunięte, są zastępowane atrybutami niosącymi w całości lub w części tę samą informację, ale korzystnie wpływającymi na złożoność hipotez dobrze przybliżających pojęcie docelowe. Przy zastępowaniu liczba dodawanych atrybutów może być zarówno mniejsza, jak i większa lub równa liczbie atrybutów usuwanych. Każdy z nich może być zależny funkcyjnie od jednego lub większej liczby usuwanych atrybutów, a także od innych atrybutów, które są pozostawiane.

Po zastosowaniu przez ucznia dowolnych przekształceń wszystkie przykłady są przed ich przekazaniem do stosowanego następnie algorytmu odkrywania wiedzy poddawane konwersji, czyli ,,tłumaczone'' do postaci wektorów wartości zmodyfikowanego zestawu atrybutów. Takie przekształcanie opisów przykładów będziemy nazywać rzutowaniem. Rzutowanie jest również konieczne dla nowych przykładów w przypadku stosowania do nich hipotezy uzyskanej przy zmienionym zestawie atrybutów.

Rodzaje konstruktywnej indukcji

Decyzje o uznaniu niektórych atrybutów za nieistotne lub mało użyteczne mogą być oparte na różnych przesłankach. Również tworząc nowe atrybuty, które określa się jako funkcje wartości atrybutów wcześniej dostępnych, można z różnych źródeł czerpać wskazówki co do właściwych postaci tych funkcji, zapewniających dużą użyteczność nowych atrybutów. Ze względu na źródło informacji decydujących o sposobach przekształcania przestrzeni atrybutów wyróżnia się w związku z tym trzy podstawowe odmiany konstruktywnej indukcji:

Konstruktywna indukcja na podstawie danych polega przede wszystkim na statystycznej analizie zbioru trenującego. Badając rozkłady wartości atrybutów i kategorii można dzięki niej wykryć atrybuty, które nie są istotne ze względu na pojęcie docelowe (w przypadku uczenia się z nadzorem) lub ze względu na możliwe grupowanie przykładów (w przypadku uczenia się bez nadzoru). Umożliwia to obliczanie różnego rodzaju miar korelacji i statystycznej istotności. Możliwe jest także stwierdzenie występowania zależności między niektórymi atrybutami, umożliwiających w pewnych sytuacjach zastąpienie ich jednym nowym atrybutem.

W konstruktywnej indukcji na podstawie wiedzy akcentowana jest rola wiedzy wrodzonej i dostarczającego ją eksperta. Wiedza ta, opisując pewne aspekty dziedziny, może umożliwić określenie właściwych przekształceń przestrzeni atrybutów. Jednak w wielu przypadkach ekspert, który taką wiedzę posiada, najłatwiej może ją wyrazić po prostu z góry dobierając odpowiednio przestrzeń atrybutów, co w ogóle eliminuje potrzebę konstruktywnej indukcji. Nie lekceważąc znaczenia konstruktywnej indukcji na podstawie wiedzy, nie będziemy się nią zajmować, głównie ze względu na to, że jest to podejście szczególnie słabo usystematyzowane i sposób jego stosowania silnie zależy od konkretnych właściwości dziedziny oraz charakteru posiadanej o niej wiedzy.

Z naszego punktu widzenia najbardziej interesująca jest konstruktywna indukcja na podstawie hipotez. Polega ona na analizowaniu hipotez uzyskanych za pomocą stosowanego algorytmu uczenia się dla poprzedniej przestrzeni atrybutów i przekształcaniu jej, tak aby było możliwe poprawienie jakości tych hipotez. Ten rodzaj konstruktywnej indukcji dopasowuje wykorzystywane przekształcenia atrybutów nie tylko do charakteru danych trenujących, lecz także do algorytmu uczenia się i związanej z nim metody reprezentacji hipotez. Nie wymaga przy tym dostępności wiedzy eksperckiej. Zalety te powodują, że jest on szczególnie dogodny do stosowania w praktyce, także w połączeniu z pozostałymi rodzajami konstruktywnej indukcji.

Konstruktywna indukcja na podstawie danych

Zgodnie z zapowiedzią konstruktywna indukcja na podstawie danych polega na analizowaniu rozkładów wartości atrybutów i kategorii w zbiorze trenującym w poszukiwaniu takich przekształceń przestrzeni atrybutów, dzięki którym będzie wystarczająca do dostatecznie dokładnego opisu pojęcia docelowego, a przy tym będzie sprzyjać opisywaniu go w prosty sposób, przede wszystkim dzięki możliwie niewielkiej liczbie atrybutów i możliwie niewielkiej liczbie ich wartości. Omawiane wcześniej metody dyskretyzacji atrybutów ciągłych (i agregacji atrybutów porządkowych) można uznać za szczególne rodzaje konstruktywnej indukcji na podstawie danych, gdyż dobierają one sposób podziału przeciwdziedziny dyskretyzowanego lub agregowanego atrybutu właśnie na podstawie analizy zbioru trenującego. Obecnie zajmiemy się konstruktywną indukcją na podstawie danych, stosowaną do atrybutów dyskretnych, nie zajmując się już więcej innymi przekształceniami dla atrybutów ciągłych, chociaż podobne zagadnienie powróci przy okazji omawiania metod odkrywania równań.

Wykrywanie atrybutów nieistotnych

Mówiąc o atrybutach nieistotnych zakładamy, że przestrzeń atrybutów ma służyć do uczenia się pewnego pojęcia docelowego $ c:X\mapsto C$ i dany jest odpowiedni zbiór trenujący $ T$. Nieistotność atrybutu $ a:X\mapsto A$ oznacza, że do reprezentowania hipotezy dobrze przybliżającej pojęcie docelowe nie jest on potrzebny, a w każdym razie taki wniosek wynika z analizy opisów i etykiet przykładów trenujących. Do wykrywania atrybutów nieistotnych ze względu na pojęcie docelowe można wykorzystać testy statystycznej istotności, takie jak test $ \chi^2$. W tym przypadku interesuje nas weryfikacja hipotezy zerowej, zgodnie z którą wartości atrybutu $ a$ i kategorie pojęcia docelowego $ c$ są od siebie niezależne, co oznaczałoby, że atrybut $ a$ może być usunięty z przestrzeni atrybutów. Odpowiednią postać statystyki $ \chi^2$ sformułujemy następująco:

$\displaystyle \chi^2_a(T) = \sum_{d\in C}\sum_{v\in A} \frac{\big(\vert T^d_{av}\vert-e^d_{av}(T)\big)^2}{e^d_{av}(T)}$, (1)

przy czym dla dowolnej kategorii $ d\in C$ i wartości atrybutu $ v\in A$ wartość $ e^d_{av}(T)$ oznacza oczekiwaną liczbę przykładów trenujących kategorii $ d$, dla których atrybut $ a$ ma wartość $ v$ przy założeniu hipotezy zerowej, czyli niezależności rozkładu kategorii od wartości atrybutu. Jest to więc liczba przykładów kategorii $ d$ z wartością $ v$ atrybutu $ a$, jakiej spodziewamy się przy założeniu, że dla przykładów o takiej wartości tego atrybutu rozkład kategorii jest taki sam jak w całym zbiorze $ T$. Liczbę tę wyznacza się w zwykły sposób jako:

$\displaystyle e^d_{av} = \vert T_{av}\vert\frac{\vert T^d\vert}{\vert T\vert}$. (2)

Wykrywanie zależności funkcyjnych

Skoro statystyka $ \chi^2$ może być wykorzystana do sprawdzania niezależności atrybutów i kategorii, to można się nią posłużyć także do poszukiwania zależności między atrybutami. Dla pary atrybutów $ a_i:X\mapsto A_i$ i $ a_j:X\mapsto A_j$ zapiszemy formułę do obliczenia statystyki $ \chi^2$ następująco:

$\displaystyle \chi^2_{a_i,a_j}(T) = \sum_{v_i\in A_i}\sum_{v_j\in A_j} \frac{\b... ...vert T_{a_iv_i,a_jv_j}\vert-e_{a_iv_i,a_jv_j}(T)\big)^2} {e_{a_iv_i,a_jv_j}(T)}$, (3)

przy czym $ T_{a_iv_i,a_jv_j}=T_{a_iv_i}\cap T_{a_jv_j}$. Oczekiwana liczba przykładów, dla których atrybut $ a_i$ ma wartość $ v_i$ oraz atrybut $ a_j$ ma wartość $ v_j$ przy założeniu hipotezy zerowej o ich niezależności, jest wyznaczana jako:

$\displaystyle e_{a_iv_i,a_jv_j} = \frac{\vert T_{a_iv_i}\vert\cdot\vert T_{a_jv_j}\vert}{\vert T\vert}$. (4)

Dla takiej statystyki można rozważyć współczynnik $ V$ Cramera:

$\displaystyle V_{a_i,a_j}(T) = \sqrt{\frac{\chi^2_{a_i,a_j}(T)}{\vert T\vert(m-1)}}$, (5)

przy czym $ m=\min\{\vert A_i\vert,\vert A_j\vert\}$. Wartość 0 oznacza brak jakiejkolwiek zależności między atrybutami $ a_i$ i $ a_j$, a wartość $ 1$ -- maksymalną, funkcyjną zależność.

Zależność funkcyjna dla pary atrybutów umożliwia usunięcie jednego z nich, gdyż nie wnosi on do opisu przykładów żadnej dodatkowej informacji ponad tę, której dostarcza drugi. Należy wówczas pozostawić ten z dwóch atrybutów, który ma mniej możliwych wartości, gdyż będzie to sprzyjać uzyskaniu prostszych hipotez podczas uczenia się. W praktyce nie należy spodziewać się często pełnej zależności funkcyjnej, ale można uznawać za zależne funkcyjnie atrybuty, dla których współczynnik $ V$ Cramera jest dostatecznie bliski $ 1$. Wówczas jednak właściwsze od usuwania jednego z dwóch ,,prawie funkcyjnie'' zależnych atrybutów może być zastąpienie ich nowym, odpowiednio skonstruowanym atrybutem. Najprostszym i najbardziej uniwersalnym podejściem jest wtedy utworzenie dla pary atrybutów $ a_i$ i $ a_j$ nowego atrybutu $ a_{ij}:X\mapsto A_{ij}$, który każdej parze wartości $ \langle v_i,v_j\rangle\in A_i\times A_j$ przyporządkowuje jednojednoznacznie jedną wartość nowego atrybutu $ v_{ij}\in A_{ij}$, a następnie przeprowadzenie agregacji wartości tak skonstruowanego ,,iloczynu kartezjańskiego'' oryginalnych atrybutów, zmniejszającej rozmiar przeciwdziedziny bez znaczącego osłabienia możliwości rozróżniania przykładów różnych kategorii. Uniwersalność tego podejścia przejawia się między innymi w tym, że może być w taki sam sposób stosowane do dowolnej liczby atrybutów, a więc niekoniecznie dwóch.

Agregacja wartości atrybutów

Przy okazji omawiania dyskretyzacji atrybutów ciągłych zauważyliśmy, że analogicznie może być przeprowadzona agergacja atrybutów porządkowych. Nic jednak nie stoi na przeszkodzie, aby podejście to, nieznacznie tylko zmienione, zastosować także do atrybutów nominalnych. Nie jest dla nich określona relacja porządku i tym samym nie można mówić o żadnych przedziałach jako podzbiorach przeciwdziedziny, zawierających pewną liczbę kolejnych wartości, lecz można w zamian rozważać dowolne podzbiory przeciwdziedziny, która w tym przypadku jest zawsze skończona.

Zastępując przedziały dowolnymi podzbiorami, możemy do agregacji atrybutów nominalnych zastosować algorytm oparty na podstawowym schemacie dyskretyzacji wstępującej. Rozpoczynając od podzbiorów jednoelementowych, odpowiadających wszystkim elementom przeciwdziedziny agregowanego atrybutu, w każdej iteracji byłaby brana pod uwagę możliwość połączenia dowolnych dwóch podzbiorów. Tym razem nie ma oczywiście żadnego odpowiednika przyległości, której wymaga się od łączonych przedziałów, więc kandydatów do połączenia może być odpowiednio więcej. Odpowiednio zmodyfikowaną postać schematu dyskretyzacji wstępującej przedstawia poniższy algorytm.


\begin{algorithmic}[1] \FUNCTION $\textit{agreguj-wstępująco}(P,a)$\INPUTARGS\mb... ...IL{$\textit{kryterium-stopu}(\mathbb{V})$}; \RET $\mathbb{V}$. \end{algorithmic}

Decyzję o połączeniu podzbiorów można oprzeć na wartości statystyki $ \chi^2$, dążąc do łączenia podzbiorów mało różniących się ze względu na rozkład częstości kategorii. Jeśli agregowany jest atrybut $ a:X\mapsto A$ i $ V_1,V_2\subset A$ oznaczają dwa podzbiory jego przeciwdziedziny, których połączenie się rozważa, to odpowiednią definicję statystyki $ \chi^2$ zapiszemy następująco:

\begin{displaymath}\begin{split}\chi^2_{a,V1,V_2}(P) ={}& \sum_{d\in C} \frac{\b... ...})\big)^2} {e^d_{a,V_2}(P_{a,V_1\cup V_2})}\text{,} \end{split}\end{displaymath} (6)

przy czym $ P$ oznacza zbiór przykładów etykietowanych, na podstawie których przeprowadza się agregację -- zazwyczaj jest to zbiór trenujący, który następnie będzie wykorzystywany do uczenia się pojęcia docelowego. Oczywiście dla dowolnego zbioru wartości $ V\subset A$ przyjmujemy oznaczenia:

$\displaystyle P_{a,V} ={}$ $\displaystyle \{x\in P \;\vert\; a(x)\in V\}$, (7)
$\displaystyle P^d_{a,V} ={}$ $\displaystyle P^d\cap P_{a,V}$, (8)

a $ e^d_{a,V_i}(P_{a,V_1\cup V_2})$ dla $ i\in\{1,2\}$ oznacza oczekiwaną liczbę przykładów kategorii $ d$ w zbiorze przykładów o rozmiarze $ \vert P_{a,V_i}\vert$, gdyby rozkład kategorii był w nim taki sam jak w zbiorze $ P_{a,V_1\cup V_2}$, czyli gdyby nie zależał od tego, do którego z dwóch podzbiorów należy wartość atrybutu $ a$. Rzecz jasna

$\displaystyle e^d_{a,V_i}(P_{a,V_1\cup V_2}) = \vert P_{a,V_i}\vert\frac{\vert P^d_{a,V_1\cup V_2}\vert} {\vert P_{a,V_1\cup V_2}\vert}$. (9)

Kryterium stopu może być także określone przez podanie maksymalnej wartości statystyki $ \chi^2$.

Zależności wyższych rzędów

Wszystkie przedstawione techniki konstruktywnej indukcji na podstawie danych opierają się na testowaniu zależności dla pary atrybutów lub dla jednego atrybutu i pojęcia docelowego. Przyjmowaliśmy, że jest w tym celu stosowana statystyka $ \chi^2$. Bez względu jednak na to, czy będzie zastosowana ta czy inna metoda testowania zależności, techniki te mają pewną trudną do przezwyciężenia słabość. Uwzględniają one tylko zależności pierwszego rzędu, dotyczące dwóch atrybutów niezależnie od wartości pozostałych atrybutów, pomijając możliwość występowania zależności wyższych rzędów, występujących dla większej liczby atrybutów. Tymczasem może się zdarzyć tak, że przy braku zależności dla par atrybutów występują jakieś zależności dla trójek lub większych liczb atrybutów. Może się też zdarzyć, że dwa atrybuty takie, że każdy z osobna wydaje się nieistotny (pojęcie docelowe nie zależy od wartości każdego z nich zgodnie z testem zależności), uwzględnione jednocześnie okazują się istotne (pojęcie docelowe zależy od obu atrybutów razem wziętych).

Zatem atrybut, od którego pojęcie docelowe nie zależy w świetle testu zależności, nie musi być naprawdę niestotny -- pojęcie docelowe może zależeć od tego atrybutu wraz z jednym lub większą liczbą innych atrybutów. Aby wykryć atrybuty prawdziwie nieistotne dla pojęcia docelowego, należałoby więc uwzględnić jego zależność od wszystkich podzbiorów $ n$-elementowego zbioru atrybutów. Atrybut mógłby być uznany za nieistotny tylko pod warunkiem, że usunięcie go z dowolnego podzbioru atrybutów nie zwiększa ich łącznej istotności. Niestety, taka wyczerpująca weryfikacja istotności wiąże się ze zbyt dużymi nakładami obliczeń i raczej nie można jej polecić, jeśli liczba atrybutów przekracza kilka. Tego typu zależności wyższych rzędów są bardziej skutecznie wykrywane przez konstruktywną indukcję na podstawie hipotez, która będzie omawiana niżej. Pozostając na gruncie konstruktywnej indukcji na podstawie danych jesteśmy skazani na pewne heurystyczne strategie przeszukiwania przestrzeni możliwych podzbiorów pierwotnego zestawu atrybutów, w poszukiwaniu najlepszego. Kryterium jakości może być tu różne, w szczególności za najlepszy możemy uznać minimalny zestaw atrybutów, od którego pojęcie docelowe jest w wystarczającym stopniu zależne funkcyjnie. Tego typu strategie przeszukiwania mogą zaczynać od jednoelementowych podzbiorów zestawu atrybutów i następnie iteracyjnie rozszerzać jeden lub kilka najlepszych dotąd podzbiorów o kolejny atrybut (podejście wstępujące) lu przeciwnie, zaczynając od całego pierwotnego zestawu atrybutów kolejno eliminować po jednym atrybucie (podejście zstępujące).

Konstruktywna indukcja na podstawie hipotez

Konstruktywna indukcja na podstawie hipotez jest bezpośrednio sprzęgnięta z procesem indukcyjnego uczenia się za pomocą pewnego ustalonego algorytmu i odpowiedniej dla niego reprezentacji hipotez. Analiza uzyskiwanych hipotez jest podstawą do modyfikacji zestawu atrybutów. Istnieją co najmniej dwa warianty tego ogólnego podejścia. Pierwsze polega na cyklicznym, naprzemiennym generowaniu hipotez i wprowadzaniu przekształceń na podstawie ich analizy: każda kolejna hipoteza powstaje z wykorzystaniem zestawu atrybutów zmienionego pod wpływem poprzedniej hipotezy. Drugie, stosowane do wyboru najlepszego podzbioru z pierwotnego zestawu atrybutów (bez wprowadzania nowych atrybutów), polega na systematycznym przeglądaniu możliwych podzbiorów i ocenie ich przydatności na podstawie jakości hipotez, do jakich uzyskania prowadzą.

Iteracyjne przekształcanie zestawu atrybutów

W tym podejściu algorytm uczenia się jest stosowany do zbioru trenującego z pierwotnym zestawem atrybutów w celu wygenerowania pewnej hipotezy. Hipoteza taka jest następnie traktowana jako źródło informacji, umożliwiających uznanie niektórych nie występujących w niej atrybutów za zbędne i usunięcie ich lub wprowadzenie nowych atrybutów, odpowiadających pewnym funkcjom dotychczasowych atrybutów często występującym w hipotezie. Po zmodyfikowaniu przestrzeni atrybutów ten sam algorytm jest używany do znalezienia kolejnej hipotezy, która jest ponownie analizowana w ten sam sposób. Postępowanie takie powtarzane jest tak długo, jak długo zmiany wprowadzane do przestrzeni atrybutów powodują poprawę właściwości uzyskiwanych hipotez. Tak opisany schemat konstruktywnej indukcji na podstawie hipotez precyzuje poniższy algorytm.


\begin{algorithmic}[1] \FUNCTION $\textit{KIH}(L,T,\mathbb{A})$\INPUTARGS\mbox{}... ...t{zastosuj-algorytm}(L,\mathbb{A},T)$; \RET $\mathbb{A}$, $h$. \end{algorithmic}

Zgodnie z przedstawionym schematem, algorytm uczenia się jest wielokrotnie używany do wygenerowania hipotezy na podstawie części przykładów trenujących ze zbioru $ P\subset T$, nazywanego zbiorem pierwotnym. Pozostałe przykłady trenujące tworzą zbiór wtórny $ S=T-P$, który jest wykorzystywany do oceny poprawy, jaką dają wprowadzane w kolejnych iteracjach przekształcenia przestrzeni atrybutów, i do podejmowania na tej podstawie decyzji o zakończeniu konstruktywnej indukcji. Analiza hipotezy, z uwzględnieniem zbioru pierwotnego, na podstawie którego została uzyskana, ma na celu określenie najbardziej obiecujących przekształceń przestrzeni atrybutów. Podjęciem decyzji w tej kwestii i jej realizacją zajmuje się funkcja $ \textit{przekształcenia}$, która stanowi rdzeń przedstawionego podejścia do konstruktywnej indukcji, decydujący o specyfice jego różnych konkretnych wcieleń. Przekształcenia takie mogą oczywiście powodować odpowiednią niejawną modyfikację przestrzeni możliwych do reprezentowania hipotez. Po dokonaniu tych modyfikacji ten sam cykl może zostać powtórzony, o ile nie jest spełnione kryterium stopu. Na koniec za pomocą ostatecznie uzyskanej przestrzeni atrybutów znajdowana jest hipoteza przez zastosowanie algorytmu uczenia się do całego zbioru trenującego $ T$. Podany algorytm opisuje więc nie tylko schemat konstruktywnej indukcji na podstawie hipotez, lecz także sposób jej połączenia z właściwym procesem uczenia się. Oczywiście każdorazowe wykonanie operacji $ \textit{zastosuj-algorytm}$ musi na wstępie obejmować odpowiednie rzutowanie zbioru przykładów na aktualną przestrzeń atrybutów.

W ten sposób konstruktywną indukcję można zastosować do ,,wzmocnienia'' właściwie dowolnego algorytmu indukcyjnego uczenia się z nadzorem lub bez nadzoru. Konkretyzacja przedstawionego schematu wymaga jednak określenia operacji, które chociaż nie zależą bezpośrednio od algorytmu uczenia się, zależą od wykorzystywanej przez niego reprezentacji hipotez. Te operacje to ocena jakości hipotez na podstawie pewnego zbioru przykładów oraz, co najważniejsze, analizowanie hipotez w celu określenia obiecujących przekształceń przestrzeni atrybutów. Z pierwszym z nich zetknęliśmy się już wielokrotnie i tu potraktujemy go tylko pobieżnie, a drugim zajmiemy się nieco dokładniej.

Kryterium stopu

Najprostsze, lecz i najbardziej naturalne kryterium stopu dla konstruktywnej indukcji (nie tylko na podstawie hipotez) stanowi warunek braku korzystnych efektów w wyniku ostatnio zastosowanych przekształceń przestrzeni atrybutów. W przypadku podanego wyżej algorytmu stwierdzenie poprawy lub jej braku jest możliwe na podstawie oceny jakości ostatniej hipotezy $ h$ na zbiorze wtórnym $ S$ i porównanie jej z oceną uzyskaną dla hipotezy w poprzednim kroku. Zaprzestawanie dalszych przekształceń tylko po jednokrotnym braku poprawy mogłoby być jednak decyzją zbyt radykalną, uniemożliwiającą wypróbowanie dostatecznie wielu obiecujących przekształceń. Właściwsze wydaje się raczej przyjęcie łagodniejszego kryterium stopu, które zezwala na brak poprawy, a nawet pogorszenie, w pewnej niewielkiej liczbie iteracji. Dopiero przekroczenie tej liczby zatrzymuje algorytm.

Ocena hipotez

Konstruktywna indukcja na podstawie hipotez wymaga ich oceny w celu weryfikacji, czy wykonywane przekształcenia przestrzeni atrybutów są rzeczywiście korzystne, oraz podjęcia decyzji o zaprzestaniu ich dalszego stosowania, jeśli przestaną przynosić korzyści. W zasadzie wszystko, co o ocenie hipotez było w różnych miejscach książki powiedziane dotychczas, może mieć tu zastosowanie, zależnie oczywiście od ich reprezentacji. Trudno w tej sytuacji wskazać podejście, które byłoby powszechnie przyjęte i uniwersalnie użyteczne. Można, jak zwykle, stosować różne heurystyki uwzględniające dokładność i złożoność. Wiele różnych kryteriów oceny można uwzględnić za pomocą funkcji typu LEF. Niezależnie jednak od szczegółowych postaci używanych heurystyk trzeba wziąć pod uwagę dwie podstawowe kwestie: zbiór przykładów, na podstawie którego przeprowadza się ocenę dokładności hipotezy, oraz uwzględnienie przy ocenie złożoności także złożoności definicji nowych atrybutów dodanych w wyniku konstruktywnej indukcji.

Ocena dokładności.

Algorytm konstruktywnej indukcji na podstawie hipotez zakłada podział zbioru trenującego na podzbiory, z których jeden jest używany do znajdowania roboczych hipotez i drugi do ich oceniania, co jest podejściem dość wygodnym i często przyjmowanym. Wówczas w najprostszym przypadku błąd próbki na zbiorze wtórnym $ S$ może służyć za kryterium porównań. Ponieważ oceniana hipoteza nie zależy od zbioru $ S$, błąd próbki na tym zbiorze jest najbardziej prawdopodobną wartością błędu rzeczywistego. Czasem jednak dostępny zbiór przykładów jest zbyt mały, aby po jego podziale zbiory pierwotny i wtórny były dostatecznie duże odpowiednio do uzyskania dobrej jakości hipotez, których analiza prowadziłaby do korzystnych przekształceń atrybutów, oraz do wiarygodnej oceny tych hipotez. Można wówczas odstąpić od używania dwóch odrębnych zbiorów przykładów i do obu celów wykorzystać ten sam, cały zbiór $ T$, postępując tak, jak było to wcześniej sugerowane dla metody przycinania pesymistycznego. Polega to w skrócie na pesymistycznym szacowaniu rzeczywistego błędu hipotezy na podstawie jej błędu próbki na zbiorze trenującym i wykorzystywaniu takiego oszacowania do oceny hipotez.

Ocena złożoności.

Niezależnie od przyjętej do oceny hipotez miary złożoności, którą może być w najprostszych przypadkach liczba węzłów lub liści dla drzew decyzyjnych, liczba reguł, selektorów nieuniwersalnych lub występujących w nich wartości artrybutów dla zbiorów reguł, trzeba pamiętać o tym, aby w odpowiedni sposób uwzględnić także złożoność nowych atrybutów dodawanych w trakcie konstruktywnej indukcji. Gdyby zostało to zaniedbane, a złożoność hipotez byłaby brana mimo to pod uwagę, szybko moglibyśmy uzyskać najprostsze z możliwych hipotezy, reprezentowane za pomocą pojedynczych atrybutów (np. drzewo decyzyjne z jednym tylko węzłem lub jedna reguła dla każdej kategorii, zawierająca w kompleksie co najwyżej jeden nieuniwersalny, pojedynczy selektor), gdyż cała złożoność związana z reprezentowaniem pojęcia docelowego zostałaby przeniesiona do atrybutów. Oczywiście takie przeniesienie złożoności nie jest celem konstruktywnej indukcji.

Wykorzystanie zasady minimalnej długości kodu.

W świetle powyższej dyskusji trudno nie dostrzec korzyści, jakie może dać wykorzystanie do oceny skutków konstruktywnej indukcji zasady minimalnej długości kodu. Odpowiednio zastosowana, umożliwia ona jednoczesną ocenę dokładności i złożoności na podstawie jednego zbioru przykładów, czyli całego zbioru trenującego. Jak zwykle podstawą oceny jest długość kodu dla dwuczęściowego komunikatu, składającego się z opisu hipotezy i danych trenujących przy założeniu jej znajomości. Przy kodowaniu hipotezy trzeba jednak tym razem uwzględnić także definicje nowych atrybutów, które zostały utworzone w wyniku konstruktywnej indukcji. Długość kodu dla hipotezy musi być zwiększona o długość kodu niezbędną do zapisania tych definicji.

Wybór przekształceń

Analiza hipotez może być podstawą wyboru przekształceń przestrzeni atrybutów każdego z trzech głównych rodzajów, jakie wyróżniliśmy. Nie będziemy tu zajmować się wykorzystywanymi w tym celu szczegółowymi technikami, specyficznymi dla poszczególnych systemów konstruktywnej indukcji opisanych w literaturze, poprzestając na zasugerowaniu ogólnych koncepcji usuwania oraz dodawania nowych atrybutów na podstawie analizy hipotez.

Usuwanie atrybutów.

W najprostszym przypadku kandydatami do eliminacji są atrybuty nie wykorzystywane w analizowanej hipotezie lub takie, które nie mają zasadniczego znaczenia dla jej dokładności. Jeśli stosowany algorytm uczenia się jest wspomagany przez mechanizmy zapobiegające nadmiernemu dopasowaniu, takie jak przycinanie, to można oczekiwać, że hipoteza nakłada pewne warunki tylko na wartości tych atrybutów, które są faktycznie istotne ze względu na kategorie pojęcia docelowego. Wówczas pozostałe atrybuty mogą być pominięte.

Nowe atrybuty.

Wykorzystywane przez analizowaną hipotezę kombinacje warunków nakładanych na wartości atrybutów mogą posłużyć do zdefiniowania nowych atrybutów, jeśli są spełniane przez odpowiednio dużo przykładów trenujących. Takie kombinacje warunków, nazywane czasem wzorcami, mogą być w szczególności reprezentowane jako poddrzewa w przypadku indukcji drzew decyzyjnych lub kompleksy w przypadku indukcji reguł. Na ich podstawie mogą być zdefiniowane atrybuty binarne, przyjmujące wartość $ 1$ dla przykładów pokrywanych przez wzorce (czyli spełniających odpowiednie warunki) i wartość 0 dla pozostałych przykładów. Analiza drzew decyzyjnych z testami przynależnościowymi lub zbiorów reguł z selektorami dysjunkcyjnymi może również być podstawą agregacji wartości atrybutów, polegającej na zastąpieniu kilku wartości występujących łącznie w takim teście lub selektorze jedną nową wartością.

Wybór najlepszego podzbioru atrybutów

Inny wariant konstruktywnej indukcji może być środkiem zaradczym na dyskutowany wyżej problem trudnych do wykrywania zależności wyższego rzędu, które powoduje, że bezpośrednie usuwanie (być może pozornie) nieistotnych atrybutów jest ryzykowne. Zamiast oceniać istotność usuwanych atrybutów można oceniać jakość pozostałego podzbioru, używając go przy generowaniu hipotez (często np. drzew decyzyjnych). Jedna z możliwych realizacji tego podejścia mogłaby mieć charakter zstępujący: zaczynając od pełnego pierwotnego $ n$-elementowego zestawu atrybutów w pierwszym etapie usuwa się z niego każdy pojedynczy atrybut. Po wybraniu najlepszego z takich $ (n-1)$-elementowych podzbiorów można z kolei rozważać usunięcie z niego kolejnego atrybutu (każdego możliwego). Najlepszy $ (n-2)$-elementowy podzbiór mogłby być dalej pomniejszany o jeden atrybut, itd. Istotą tej koncepcji jest to, że każdy rozważany podzbiór jest oceniany ze względu na jakość hipotezy, jaką z jego wykorzystaniem generuje algorytm uczenia się używany do konstruktywnej indukcji. Może to być ocena wyznaczona przez błąd na oddzielnym zbiorze przykładów albo przez błąd na zbiorze trenującym i złożoność (które łącznie uwzględnia zasada minimalnej długości kodu).

Zagadnienia praktyczne

Aby uzyskać praktycznie skuteczny system konstruktywnej indukcji, trzeba rozstrzygnąć szereg problemów, które nie zostały tu poruszone w dostatecznym stopniu. Najważniejsza jest sygnalizowana w niej tylko kwestia oceny hipotez uzyskiwanych dla różnych reprezentacji i rozstrzygnięcie, czy konstruktywna indukcja daje poprawę. Przy tej ocenie należy wziąć pod uwagę dokładność hipotezy, jej złożoność, a także liczbę i złożoność atrybutów używanych do jej reprezentowania. Innym problemem jest efektywne przeszukiwanie niezwykle dużej przestrzeni możliwych do wykonania przekształceń, zarówno w przypadku konstruktywnej indukcji na podstawie danych, jak i konstruktywnej indukcji na podstawie hipotez.

Na każdy szczególny rodzaj przekształcenia przestrzeni atrybutów, taki jak usunięcie wybranego atrybutu lub dodanie nowego atrybutu zdefiniowanego na podstawie wybranych atrybutów, można patrzeć jak na pewien operator. Takie operatory umożliwiają przemieszczanie się w przestrzeni (metaprzestrzeni) możliwych zestawów atrybutów. Ponieważ wszystkie możliwe do skonstruowania zestawy nie mogą być wypróbowane i ocenione, dużego znaczenia nabiera strategia stosowania operatorów, reprezentująca właściwy kompromis między jakością ostatecznie uzyskiwanego rozwiązania a ilością obliczeń niezbędnych do jego znalezienia. Zazwyczaj względy efektywności obliczeniowej muszą wziąć górę i stosuje się różne warianty strategii zachłannej, które nie muszą prowadzić do optymalnych końcowych zestawów artrybutów. Zgodnie z taką strategią ze zbioru możliwych do zastosowania operatorów wybiera się zazwyczaj jeden najlepszy według pewnej funkcji heurystycznej i powtarza to tak długo, jak długo zastosowanie wybranego operatora faktycznie daje poprawę. Trzeba tu odróżnić wstępną ocenę ,,atrakcyjności'' operatora, która musi być łatwa do obliczenia i stąd z konieczności prosta, gdyż obliczana dla dużej liczby możliwych operatorów, od późniejszej weryfikacji faktycznej skuteczności wybranego i zastosowanego operatora. W pierwszym przypadku sposób oceny wynika z charakteru uwzględnianych operatorów oraz nałożonych na nie kryteriów preferencji. W szczególności ze wszystkich atrybutów możliwych do usunięcia jest wybierany atrybut o najniższym wskaźniku istotności, agregację rozważa się w pierwszej kolejności dla atrybutów o dużej liczbie wartości itp. W drugim przypadku najlepszego kryterium oceny dostarcza efekt zastosowania zmodyfikowanej przez zastosowanie operatora przestrzeni atrybutów do uczenia się, czyli wygenerowania kolejnej hipotezy. Poprawa jakości tej hipotezy świadczy o tym, że wybrany operator okazał się użyteczny. Taki sposób postępowania jest właściwy konstruktywnej indukcji na podstawie hipotez, która jednak może być połączona z konstruktywną indukcją na podstawie danych. Mimo że przedstawiony schemat konstruktywnej indukcji na podstawie hipotez tego nie uwzględnia, warto zezwolić na wycofanie tych wprowadzonych w poprzednim kroku przekształceń, których przydatności nie potwierdza ocena kolejnej uzyskanej hipotezy.

Literatura

  1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdział 7.3).
  2. Witten, I. A., Frank, E. Data Mining. Morgan Kaufmann, 2000. (Podrozdział 7.1).

About this document ...

Metody odkrywania wiedzy: wykład 9
Konstruktywna indukcja

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-w9.tex

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

Pawel Cichosz 2004-02-12