Metody odkrywania wiedzy: wykład 2
Indukcyjne uczenie się

Paweł Cichosz


Date: 2001/2002

Wykład przedstawia podstawowe wstępne informacje o indukcyjnym uczeniu się -- tym rodzaju uczenia się, który jest używany do odkrywania wiedzy w danych.

Znaczenie uczenia się

Przez uczenie się będziemy rozumieć zachodzącą w pewnym systemie autonomiczną zmianę prowadzącą do poprawy jakości jego działania, dokonującą się na podstawie obserwacji lub doświadczeń historycznych. Przyjmiemy, że zmiana, o jakiej jest tu mowa, polega na zdobyciu lub udoskonaleniu przez ucznia wiedzy lub umiejętności, zachowaniu tej wiedzy lub umiejętności i wykorzystywaniu jej przy wykonywaniu zadań stojących przed uczniem.

Rodzaj uczenia się, z jakim mamy do czynienia, jest charakteryzowany przez postać i sposób dostarczania uczniowi jego obserwacji lub doświadczeń (informacji trenującej), mechanizm generowania na ich podstawie nowej wiedzy i sposób jej wykorzystywania. Jeśli na przykład zadaniem ucznia jest klasyfikowanie obiektów do kategorii, informacja trenująca może mieć postać zbioru przykładowych poprawnie zaklasyfikowanych obiektów, na podstawie analizy których uczeń generuje pewne reguły klasyfikacji, które następnie może wykorzystać do klasyfikacji dowolnych nowych obiektów.

Znaczenie indukcji

Z pojęciem indukcji spotykamy się, kiedy jest mowa o wnioskowaniu indukcyjnym. Potocznie jest ono rozumiane jako przechodzenie od prostych jednostkowych faktów do ogólnych praw. W odniesieniu do uczenia się przez wnioskowanie indukcyjne rozumiemy generowania na podstawie analizy dostarczonych danych (trenujących) hipotezy indukcyjnej, stanowiącej ogólny opis występujących w tych danych zależności. który może z kolei być stosowany do wnioskowania dedukcyjnego na temat nowych danych. Rozróżnienie tych dwóch rodzajów wnioskowania jest w tym przypadku następujące:

wnioskowanie indukcyjne:
analiza dostępnych danych w celu wygenerowania hipotezy opisującej występujące w nich zależności,
wnioskowanie dedukcyjne:
stosowanie uzyskanej hipotezy do nowych danych w celu ich weryfikacji, uzupełnienia lub predykcji.

W praktyce mamy do czynienia z danymi zorganizowanymi jako zbiór rekordów opisanych za pomocą ustalonego zestawu atrybutów. Wnioskowanie indukcyjne polega wówczas na generowaniu hipotez opisującej zależności między atrybutami, a wnioskowanie dedukcyjne na stosowaniu tej hipotezy do sprawdzania poprawności, uzupełniania lub przewidywania wartości pewnych atrybutów.

Poniżej będą nieco bardziej formalnie wprowadzone podstawowe terminy związane z indukcyjnym uczeniem się i zdefiniowane jego podstawowe rodzaje (uczenie się pojęć, uczenie się aproksymacji, grupowanie).

Dziedzina i atrybuty

Dziedziną będziemy nazywać oznaczany przez $ X$ zbiór obiektów, których dotyczyć ma wiedza nabywana przez ucznia. Mogą to być przedmioty, osoby, wydarzenia, sytuacje, stany rzeczy itd.

Każdy obiekt, element dziedziny $ x\in X$, będziemy nazywać przykładem.

Będziemy zakładać, że przykłady są opisywane za pomocą atrybutów. Atrybutem będziemy nazywać dowolną funkcję określoną na dziedzinie. Przyjmiemy, że opis każdego przykładu $ x\in X$ składa się z wartości $ n\geq 1$ atrybutów, $ a_1:X\mapsto A_1,a_2:X\mapsto A_2,\dots,a_n:X\mapsto A_n$. W zależności od przeciwdziedziny (zbioru wartości) atrybuty dzieli się na kilka typów. Najbardziej podstawowy jest podział na atrybuty:

nominalne:
o skończonym zbiorze nieuporządkowanych wartości dyskretnych,
porządkowe:
o przeliczalnym zbiorze uporządkowanych wartości dyskretnych,
ciągłe:
o wartościach ze zbioru liczb rzeczywistych.
Dla dowolnego zbioru przykładów $ P\subseteq X$, atrybutu $ a:X\mapsto A$ i jego wartości $ v\in A$ oznaczymy przez $ P_{av}$ zbiór tych przykładów z $ P$, dla których atrybut $ a$ ma wartość $ v$, czyli $ P_{av}=\{x\in P \;\vert\; a(x)=v\}$.

Uczenie się pojęć

Pojęcia

Pojęcie $ c$ jest funkcją $ c:X\mapsto C$, przy czym $ C$ oznacza skończony zbiór kategorii. W przypadku pojęć pojedynczych będziemy przyjmować $ C=\{0,1\}$. W przypadku pojęć wielokrotnych $ C$ może być dowolnym skończonym zbiorem kategorii o liczności $ \vert C\vert>2$. Dla pojęć pojedynczych mówi się o przykładach pozytywnych ($ x\in X$, dla których $ c(x)=1$) i negatywnych ($ x\in X$, dla których $ c(x)=0$).

Hipotezy

Każda hipoteza $ h$, podobnie jak każde pojęcie, jest funkcją przypisującą przykładom ich kategorie $ h:X\mapsto C$.

Dane trenujące

Przykładem etykietowanym pojęcia $ c$ określonego na dziedzinie $ X$ będziemy nazywać parę złożoną z (nieetykietowanego) przykładu $ x\in X$ i jego kategorii, którą zapisujemy $ \langle x,c(x)\rangle$, przy czym przykład $ x$ jest opisany za pomocą określonych na dziedzinie atrybutów. Dane trenujące do uczenia się pojęć mają postać zbioru takich par, nazywanego zbiorem trenującym. Dla wygody będziemy mówić, że zbiorem trenującym jest po prostu pewien podzbiór dziedziny $ T\subset X$, zakładając, że dla $ x\in T$ kategorie $ c(x)$ są znane.

Niepoprawne dane trenujące

Jednym z istotnych problemów praktycznych związanych z uczeniem się pojęć (ale także z innymi rodzajami indukcyjnego uczenia się) jest niepoprawność danych trenujących. Może ona polegać na przekłamaniach w opisach przykładów, zawierających niepoprawne wartości niektórych atrybutów, lub w etykietach kategorii. Przedstawiona definicja zbioru trenującego dla uczenia się pojęć nie uwzględnia możliwości występowania w nim niepoprawnych przykładów. W definicji tej mówi się o tym, że zbiór trenujący składa się z opisów przykładów stanowiących wektory wartości atrybutów opatrzone etykietami kategorii pojęcia docelowego, niejawnie zakładając, że jedne i drugie są zawsze poprawne. Pozostając dla prostoty przy przedstawionej definicji możemy o przekłamaniach wartości atrybutów mówić zakładając, że do opisywania przykładów są używane zamiast oryginalnych atrybutów określonych na dziedzinie atrybuty z zestawu $ \{a_1',a_2',\dots,a_n'\}$, przy czym dla każdego $ i=1,2,\dots,n$ wartość atrybutu $ a_i'$ może się różnić od wartości atrybutu $ a_i$ dla niektórych przykładów. Podobnie można założyć, że przykłady są opatrzone etykietami pewnego pojęcia $ c'$, które może niektórym przykładom przypisywać inne etykiety niż pojęcie docelowe $ c$. O zbiorach trenujących zawierających przekłamania będziemy mówić, że są zaszumione.

W praktyce odkrywania wiedzy rozróżnienie na ,,prawdziwe'' i ,,przekłamane'' wartości atrybutów lub kategorie jest o tyle mało istotne, że prawie zawsze dysponujemy wyłącznie danymi -- takimi jakie są -- i nie wiemy nic o ,,prawdziwych'' atrybutach czy ,,prawdziwym'' pojęciu.

Ocena dokładności hipotez

Porównując hipotezę $ h$ z pojęciem docelowym $ c$ na pewnym zbiorze przykładów $ P\subseteq X$ możemy oszacować jej błąd próbki jako stosunek liczby niepoprawnie klasyfikowanych przykładów z tego zbioru do liczby wszystkich jego elementów:

$\displaystyle e^c_P(h) = \frac{\big\vert\{x\in P \;\vert\; h(x)\neq c(x)\}\big\vert}{\vert P\vert}$. (1)

Bardziej interesująca jest wartość błędu rzeczywistego hipotezy, który można interpretować jako oczekiwany błąd próbki na losowo wybranym zbiorze przykładów. Zakładając, że przykłady są wybierane z dziedziny zgodnie z określonym na niej pewnym rozkładem prawdopodobieństwa $ \Omega$, definicję błędu rzeczywistego można zapisać następująco:

$\displaystyle e^c_{\Omega}(h) = \mathrm{Pr}_{x\in\Omega}(h(x)\neq c(x))$, (2)

przy czym $ \mathrm{Pr}_{x\in\Omega}$ oznacza prawdopodobieństwo przy założeniu wylosowania $ x$ ze zbioru $ X$ zgodnie z rozkładem $ \Omega$. Błędu rzeczywistego nie można oczywiście obliczyć, ale można go oszacować na podstawie błędu próbki na zbiorze przykładów wybranych zgodnie z rozkładem $ \Omega$.

O hipotezach, które mają błąd próbki 0 na pewnym zbiorze przykładów $ P$ mówi się, że są spójne z pojęciem docelowym na tym zbiorze lub krócej spójne z tym zbiorem. W przypadku niepoprawnych danych trenujących z przekłamanymi etykietami spójność ze zbiorem trenującym oznacza, że hipoteza podaje dla każdego przykładu kategorię taką, jaka jest dostarczona z tym zbiorem, a więc być może przekłamaną. W tej sytuacji hipoteza spójna ze zbiorem trenującym może nie być spójna z (prawdziwym) pojęciem docelowym na tym zbiorze. W praktyce takie rozróżnienie nie ma jednak znaczenia, gdyż ,,prawdziwe'' pojęcie docelowe jest wyłącznie bytem teoretycznym, a a dostępne są wyłącznie jego być może przekłamane kategorie dla przykładów trenujących.

Nadmierne dopasowanie

Nie zawsze hipotezy minimalizujące błąd próbki na zbiorze trenującym są najlepsze. W pewnych przypadkach możemy mieć do czynienia z niepożądanym zjawiskiem zwanym nadmiernym dopasowaniem, które będziemy rozumieć w następujący sposób:

Dla danej dziedziny $ X$, określonego na niej pojęcia docelowego $ c$ i rozkładu prawdopodobieństwa $ \Omega$ na $ X$ hipoteza $ h$ jest nadmiernie dopasowana do zbioru trenującego $ T$ wylosowanego zgodnie z rozkładem $ \Omega$, jeśli istnieje hipoteza $ h'$ taka, że $ e^c_T(h)<e^c_T(h')$, ale $ e^c_{\Omega}(h)>e^c_{\Omega}(h')$.

Hipoteza jest zatem nadmiernie dopasowana do zbioru trenującego, jeśli inna hipoteza o większym błędzie próbki na tym zbiorze ma mimo to mniejszy błąd rzeczywisty.

Zagrożenie nadmiernym dopasowaniem jest szczególnie duże w przypadku występujących często w praktyce niepoprawnych danych trenujących, z przekłamaniami w etykietach przykładów. Wówczas nadmiernie dopasowana hipoteza odzwierciedla przypadkowe przekłamania w zbiorze trenującym, a nie (albo nie tylko) istotne właściwości pojęcia docelowego. Nadmierne dopasowanie może wystąpić również dla poprawnych danych trenujących, jeśli uczeń nie dokona ich dostatecznej generalizacji. Hipoteza o małym błędzie próbki na zbiorze trenującym może odzwierciedlać szczególne właściwości wchodzących w jego skład przykładów, niekoniecznie istotne z punktu widzenia pojęcia docelowego.

Najczęściej stosowanym podejściem, mającym na celu unikanie nadmiernego dopasowania, jest uwzględnianie w algorytmach uczenia się, oprócz błędu próbki na zbiorze trenującym, złożoności hipotez jako jednego z czynników decydujących o wyborze hipotezy. Nieformalnie można to uzasadnić obserwacją, że jest znacznie mniej prawdopodobne, aby zgodność prostych hipotez z danymi trenującymi była przypadkowa niż w przypadku hipotez skomplikowanych, gdyż tych pierwszych jest znacznie mniej niż tych drugich. Jeśli hipoteza skomplikowana dobrze pasuje do danych, to być może jest to konsekwencją uwzględnienia przez nią ich przypadkowych błędów i w istocie pasuje ona do nich nadmiernie. Jeśli mały błąd próbki na zbiorze trenującym ma hipoteza prosta, to można się spodziewać, że wynika to z trafnego przybliżenia przez nią pojęcia docelowego. Rozumowanie to leży u podstaw zasady zapożyczonej przez teorię i praktykę indukcyjnego uczenia się z filozofii, znanej pod nazwą brzytwy Ockhama.

Cel uczenia się

Celem uczenia się pojęć jest na podstawie zbioru trenującego dla pewnego pojęcia docelowego $ c$ znalezienie hipotezy $ h$ będącej możliwie najlepszym przybliżeniem tego pojęcia. Postulatem idealnym jest znalezienie hipotezy o minimalnym błędzie rzeczywistym, ponieważ jednak jest to kryterium nieweryfikowalne, zastępuje się je innymi. W najprostszym przypadku można przyjąć kryterium minimalizacji błędu próbki na zbiorze trenującym, jednak samo to kryterium zazwyczaj nie prowadzi do hipotez wysokiej jakości ze względu na zjawisko nadmiernego dopasowania, w związku z czym zazwyczaj dodatkowo uwzględnia się przynajmniej postulat minimalizacji złożoności hipotezy. (W praktyce złożoność hipotez utożsamia się z ich rozmiarem w przyjętej reprezentacji).

Uczenie się aproksymacji

Funkcja docelowa

Rozważamy uczenie się pewnej nieznanej funkcji docelowej $ f:X\mapsto\Re$ przypisującej elementom dziedziny liczby rzeczywiste. Nie ma potrzeby rozważania funkcji o wartościach w $ \Re^m$ dla $ m>1$, gdyż uczenie się aproksymacji takich funkcji sprowadza się do $ m$-krotnego uczenia się aproksymacji funkcji o wartościach w $ \Re$.

Hipotezy

W przypadku aproksymacji funkcji możliwe hipotezy są również funkcjami $ h:X\mapsto\Re$.

Dane trenujące

Przykładem etykietowanym funckji $ f$ określonej na dziedzinie $ X$ będziemy nazywać parę złożoną z (nieetykietowanego) przykładu $ x\in X$ i wartości, jaką przyjmuje dla niego funkcja $ f$, którą zapisujemy $ \langle x,f(x)\rangle$, przy czym przykład $ x$ jest opisany za pomocą określonych na dziedzinie atrybutów. Dane trenujące do uczenia się aproksymacji mają postać zbioru takich par, nazywanego zbiorem trenującym. Tak jak w przypadku uczenia się pojęć, dla wygody będziemy mówić, że zbiorem trenującym jest po prostu pewien podzbiór dziedziny $ T\subset X$, zakładając, że dla $ x\in T$ wartości $ f(x)$ są znane.

Ocena dokładności hipotez

Istnieje szereg miar dokładności hipotezy do aproksymacji funkcji na danym zbiorze przykladów $ P$, odpowiadających błędowi próbki dla klasyfikacji. Najczęściej używany jest błąd średniokwadratowy, określony następująco:

$\displaystyle s^f_P(h) = \frac{1}{\vert P\vert}\sum_{x\in P}\big(f(x)-h(x))^2$. (3)

Odpowiednik błędu rzeczywistego można wówczas dla ustalonego rozkładu $ \Omega$ na $ X$ zdefiniować następująco:

$\displaystyle s^f_{\Omega}(h) = \mathbf{E}_{\Omega}\Big[\big(f(x)-h(x)\big)^2\Big]$, (4)

gdzie $ \mathbf{E}_{\Omega}$ oznacza wartość oczekiwaną przy założeniu, że przykłady są wybierane z dziedziny zgodnie z rozkładem $ \Omega$.

Tworzenie pojęć

Przez tworzenie pojęć będziemy rozumieć wyznaczanie podziału przykladów trenujących na grupy ze względu na podobieństwo, przypisywanie indywidualnej kategorii każdej z tych grup, i generowanie hipotezy pozwalającej klasyfikować do tak utworzonych kategorii dowolne elementy dziedziny. Taki rodzaj uczenia się nazywany jest częściej grupowaniem pojęciowym.

Grupowanie a podobieństwo

Nie określając żadnego konkretnego algorytmu grupowania można powiedzieć tylko tyle, że podział na grupy następuja na podstawie pewnej miary podobieństwa przykładów określonej na dziedzinie. Podział ten powinien spełniać dwa postulany:

  1. maksymalizacja podobieństwa przykładów w ramach każdej grupy,
  2. minimalizacja podobieństwa między przykładami z różnych grup.

Hipotezy

W tworzeniu pojęć każda hipoteza $ h$ ma specyficzny dla niej zbiór kategorii $ C_h$, odpowiadający podziałowi na grupy. Poza tym zachowuje się jak hipoteza do uczenia się pojęć, czyli klasyfikuje dowolny elemen dziedziny do kategorii ze zbioru $ C_h$, a więc jest funkcją $ h:X\mapsto C_h$.

Uwagi praktyczne

Przedstawiona terminologia i notacja jest wygodna przy dyskutowaniu w ścisły sposób algorytmów uczenia się. Nie odpowiada ona dokładnie terminologii, jaką wygodnie jest się posługiwać mówiąc o praktycznych metodach odkrywania wiedzy, ale łatwo się na nią tłumaczy. Przykłady odpowiadają rekordom bazodanowym, opisujące je atrybuty odpowiadają atrybutom-polom rekordów, pojęcie docelowe czy funkcja docelowa to pewien wybrany atrybut, dla którego poszukuje się zależności od innych atrybutów.

Literatura

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

About this document ...

Metody odkrywania wiedzy: wykład 2
Indukcyjne uczenie się

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

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

Pawel Cichosz 2004-02-12