Tekst źródłowy strony Sztuczna inteligencja/SI Moduł 9 - Wnioskowanie indukcyjne

<!-- Wygenerowane przez tex2wikiu8.pl czas: wto lip 18 18:54:53 CEST 2006 -->

== Wnioskowanie indukcyjne ==
W rozdziale tym wyjaśnimy co rozumiemy pod pojęciem wnioskowania indukcyjnego i sformalizujemy je matematycznie.
Następnie przedstawimy zasadę uczenia z nauczycielem i podamy kilka przykładów.

== Obiekty i atrybuty ==

Załóżmy, że zajmujemy się zbiorem obiektów <math>O \,</math> i interesuje nas zauważenie pewnych prawidłowości w tym zbiorze, opisywanych za pomocą funkcji <math>\phi:O \rightarrow V \,</math>.

Zbiór <math>O \,</math> jest zbiorem elementów związanych ze światem rzeczywistym, np. samochodów, roślin, firm, klientów banku itp. Elementy te są często charakteryzowane za pomocą pewnej liczby mierzalnych cech, zwanych ''atrybutami''. Na przykład w przypadku klientów banku atrybutami mogą być np. numer PESEL, adres zamieszkania, stan cywilny, wysokość miesięcznych dochodów itp. Z kolei w przypadku samochodu może być to marka, typ silnika, rodzaj  nadwozia, rodzaj skrzyni biegów, typowe zużycie paliwa itp.

Atrybuty charakteryzują elementy ze zbioru <math>O \,</math> i możemy je traktować jako funkcje postaci <math>a: O \rightarrow A \,</math>, gdzie <math>A \,</math> jest dziedziną wartości atrybutu. Ponieważ każdy element zbioru <math>O \,</math> może być charakteryzowany przez więcej niż jeden atrybut, przyjmiemy, że atrybuty są numerowane kolejnymi liczbami począwszy od jedności. Tak więc każdy obiekt <math>o \in O \,</math> jest opisany za pomocą wektora wartości atrybutów <math>[a_1(o),...., a_n(o)] \,</math>. .

W niektórych przypadkach identyfikacja obiektu przez zbiór wartości atrybutów jest jednoznaczna (w praktyce numer PESEL wystarcza do identyfikacji obywatela Polski). Wtedy możliwe jest z technicznego punktu widzenia utożsamienie zbioru <math>O \,</math> ze zbiorem <math>D=A_1 \times ... \times A_n \,</math>, gdzie <math> A_1, ... , A_n \,</math> oznaczają zbiory wartości kolejnych atrybutów.

Są jednak przypadki, gdy nie można mówić o jednoznaczności opisu obiektu za pomocą wartości atrybutów. Prostym przykładem może być baza danych osobowych, w której notuje się imiona, nazwiska i daty urodzenia, bez numeru PESEL, NIP, ani żadnego dokumentu tożsamości  unikalnym numerze. Wówczas należy się liczyć z sytuacją, gdy wiele różnych osób będzie scharakteryzowanych za pomocą takiego samego zestawu danych.

== Zadanie wnioskowania indukcyjnego ==

Przyjmijmy, że istnieje pewna nieznana funkcja <math>\phi:O \rightarrow V \,</math> oraz zbiór funkcji <math>a_i \,</math>, zwanych atrybutami, których zbiory wartości są oznaczane przez <math>A_1,..., A_n \,</math>.  Oznaczmy <math>D=A_1 \times ... \times A_n \,</math>. Załóżmy także, że dysponujemy pewną liczbą obserwacji w postaci par <math>\{{\mathbf x}, v \} \,</math> gdzie <math>{\mathbf x}=[a_1(o),...., a_n(o)] \,</math> oraz <math>v=\phi(o) \,</math>.

W dalszym ciągu tekstu będziemy zakładać dla większej przejrzystości że zbiór atrybutów wystarcza do jednoznacznej identyfikacji obiektów, a odstępstwa od tego założenia będziemy traktować jako swoisty wyjątek. Przyjmując wspomniane założenie, można uprościć rozważania i przyjąć, że interesuje nas funkcja <math>f:D \rightarrow V \,</math>, która jest zdefiniowana następująco <math>f([a_1(o),...., a_n(o)])=\phi(o) \,</math>.

Wnioskowanie indukcyjne polega na wyznaczeniu funkcji <math>g:D \rightarrow V \,</math> w taki sposób, aby jak najlepiej przybliżała ona funkcję <math>f \,</math>. Innymi słowy, wnioskowanie indukcyjne to ''aproksymacja'' funkcji <math>f \,</math> funkcją <math>g \,</math>.

W zależności od dziedziny <math>D \,</math> i przeciwdziedziny <math>V \,</math> aproksymowanej funkcji <math>f \,</math>, mówi się o różnych odmianach zadania wnioskowania indukcyjnego. Wymienimy tu dwie podstawowe odmiany.

Jeśli <math>V \,</math> jest zbiorem skończonym (nierzadko zakłada się po prostu, że <math>V=\{0,1\} \,</math>), to elementy tego zbioru są często interpretowane jako etykiety klas i taką odmianę wnioskowania indukcyjnego nazywa się często ''uczeniem się klasyfikacji''. Funkcja <math>f \,</math> bywa nazywana ''pojęciem docelowym'', zaś funkcja <math>g \,</math> - ''hipotezą''.

Z kolei jeśli <math>D=R^n \,</math> oraz <math>V=R \,</math> mówi się często o zadaniu regresji. Niekiedy zadanie regresji utożsamia się po prostu z zadaniem aproksymacji.

Wyróżnienie zadań regresji i klasyfikacji ma jeszcze jeden powód, związany z rodzajami modeli wykorzystywanych w tych podejściach. W przypadku realizacji zadań klasyfikacji funkcja <math>g \,</math> jest typowo złożonym wyrażeniem logicznym, dla wygody przetwarzania przedstawianym  jako drzewo decyzyjne lub zbiór reguł decyzyjnych. Z kolei w zadaniach regresji funkcja <math>g \,</math> jest zazwyczaj wyrażeniem arytmetycznym, nierzadko o złożonej postaci.

== Wnioskowanie indukcyjne jako zadanie przeszukiwania ==

Oznaczmy przez <math>\Omega \,</math> zbiór wszystkich funkcji postaci <math>D \rightarrow V \,</math>, tj. zbiór funkcji przyjmujących argumenty ze zbioru <math>D \,</math> i zwracających wartości ze zbioru <math>V \,</math>.  Aproksymowana funkcja <math>f \,</math> jest oczywiście elementem zbioru <math>\Omega \,</math>.

Załóżmy, że w zbiorze <math>\Omega \,</math> da się „pomierzyć odległość” między dwiema dowolnymi funkcjami, a zatem istnieje funkcja <math>|\cdot| : \Omega \times \Omega \rightarrow R_+ \,</math> , która jest metryką w zbiorze <math>\Omega \,</math>. Z punktu widzenia zadania aproksymacji możemy powiedzieć, że dla dowolnych funkcji <math>f_1, f_2 \in \Omega \,</math> odległość <math>|f_1, f_2| \,</math> jest ''błędem aproksymacji'' funkcji <math>f_1 \,</math> za pomocą funkcji <math>f_2 \,</math>.

=== Przykład 1 ===
Niech <math>\Omega \,</math> będzie zbiorem funkcji postaci <math>[0,1] \rightarrow [-1,1] \,</math> (a zatem <math>D=[0,1] \,</math>, <math>V=[-1,1] \,</math>). Załóżmy też, że metryka w zbiorze <math>\Omega \,</math> będzie miała postać

<!-- equation 0 -->
:{| width="100%"
| width="95%" align="left" | <math>|f_1, f_2| = \int_0^1 [f_1(x)-f_2(x)]^2 d x
 \,</math>
|}
(metrykę tę będziemy nazywać błędem kwadratowym).

Załóżmy, że aproksymowaną funkcją jest <math>f(x)=(x-0.5)^2 \,</math>, natomiast funkcje aproksymujące należą do zbioru funkcji opisanych wzorem <math>g(x) = a\cos(bx+c)+d \,</math>, gdzie <math>a,b,c,d \,</math> są parametrami. Zadanie aproksymacji polega na znalezieniu takich wartości parametrów, dla których błąd kwadratowy jest minimalny. Można się przekonać wykonując proste obliczenia numeryczne, że z pewnym przybliżeniem ma to miejsce dla wartości parametrów równych <math>a=-0.25, \,</math> <math>b=3.06, \,</math> <math>c= -0.5, \,</math> <math>d=0.25, \,</math> a zatem funkcja aproksymująca jest dana wzorem <math>g(x)=-0.25 \cos(3.06x-1.53)+0.25 \,</math>. Wykresy funkcji aproksymowanej (czerwony) i aproksymującej (niebieski) są umieszczone poniżej.

<!-- begin{wiki} -->
[[Grafika:SI M9 wykres 1.png]]

<!-- end{wiki} -->
Zauważmy także, że przyjęta w przykładzie klasa funkcji <math>G \,</math> nie zawiera funkcji <math>f \,</math>, a zatem funkcja <math>f \,</math> nie da się aproksymować z zerowym błędem - jest nienauczalna.

=== Przykład 2 ===
Niech <math>\Omega \,</math> będzie zbiorem funkcji postaci <math>\{0,1\}^4 \rightarrow \{0,1\} \,</math> (a zatem <math>D=\{0,1\}^4 \,</math>, <math>V=\{0,1\} \,</math>). Załóżmy też, że metryka w zbiorze <math>\Omega \,</math> będzie miała postać

<!-- equation 0 -->
:{| width="100%"
| width="95%" align="left" | <math>|f_1, f_2| = \sum_{{\mathbf x} \in D} |f_1({\mathbf x})-f_2({\mathbf x})|.
 \,</math>
|}
Zauważmy, że argumentem funkcji jest wektor czterobitowy.

Załóżmy, że aproksymowaną funkcją jest <math>f({\mathbf x})=(x_1 \or x_2) \and x_3 \or x_4  \,</math>, natomiast funkcje aproksymujące należą do zbioru funkcji opisanych wzorem <math>g({\mathbf x}) = (x_i \and x_j) \or (x_k \and x_l)\or (x_m \and x_n) \,</math>, gdzie <math>i,j,k,l,m,n \,</math> są numerami bitów wektora <math>{\mathbf x} \,</math>. Zadanie aproksymacji polega na znalezieniu takich wartości <math>i,j,k,l,m,n \,</math>, dla których błąd jest minimalny. Można się przekonać, że
ma to miejsce dla <math>i=1, j=3, k=2, l=3, m=4, n=4 \,</math>, a zatem funkcja aproksymująca jest dana wzorem
<math>g({\mathbf x}) = (x_1 \and x_3) \or (x_2 \and x_3)\or (x_4 \and x_4) \,</math>.
Zauważmy także, że przyjęta w przykładzie klasa funkcji <math>G \,</math> zawiera funkcję <math>f \,</math>, a zatem funkcja <math>f \,</math> da się aproksymować z zerowym błędem - jest nauczalna.

W indukcyjnym uczeniu zakłada się, że dysponujemy możliwością wygenerowania pewnej liczby funkcji aproksymujących. Oznaczmy zbiór wszystkich funkcji aproksymujących przez <math>G \,</math>. Naturalnie, każda funkcja należąca do <math>G \,</math> jest funkcją ze zbioru <math>\Omega \,</math>, a zatem <math>G \subseteq \Omega \,</math>. Zadanie aproksymacji polega więc na wyznaczeniu takiej funkcji <math>g \in G \,</math>, że wartość błędu aproksymacji <math>|f,g| \,</math> jest jak najmniejsza. Zadanie to jest realizowane przez przeszukiwanie zbioru <math>G \,</math>, a szczegóły techniczne sposobu realizacji tego zadania są omówione w wykładach poświęconych [[../SI Moduł 10 - Zadanie i metody klasyfikacji|uczeniu się klasyfikacji]], [[../SI Moduł 11 - Zadanie i metody regresji|regresji nieliniowej]] i [[../SI Moduł 12|perceptronowi wielowarstwowemu]].

Rzecz jasna, że jeśli <math>f \in G \,</math>, to istnieje dokładne rozwiązanie zadania aproksymacji (tzn. takie, dla którego <math>f=g \,</math>). Mówimy wówczas, że funkcja <math>f \,</math> jest ''nauczalna'' w klasie funkcji <math>G \,</math>. W przeciwnym przypadku, tzn. jeśli <math>f \notin G \,</math>,  należy liczyć się z niezerowym błędem  aproksymacji, zaś <math>f \,</math> jest ''nienauczalna''.

== Stopnie swobody modelu ==
Funkcje należące do klasy <math>G \,</math> są zazwyczaj reprezentowane w sposób wygodny do ich dalszego przetwarzania. Często przyjmuje się taki model funkcji aproksymującej, że jest ona dana wyrażeniem przyjmującym pewną liczbę parametrów (por. przykład 1), a zadanie aproksymacji sprowadza się do dobrania takich wartości tych parametrów, które prowadzą do minimalnego błędu aproksymacji. O parametrach tych mówi się, że są ''stopniami swobody'' modelu. W przypadku modeli nie opisywanych zbiorem parametrów, liczba stopni swobody jest pojęciem znacznie trudniejszym do wyłożenia (można ją np. wiązać z ilością danych potrzebnych do jednoznacznego określenia modelu), zdajmy się więc na intuicję i przyjmijmy, że liczba stopni swobody to miernik „komplikacji” modelu.

Zazwyczaj jest tak, że im większa liczba stopni swobody modelu, tym więcej funkcji można wyrazić za jego pomocą, a zatem tym liczniejsza jest rodzina funkcji <math>G \,</math>. Jest to z jednej strony zjawisko pozytywne, bo pozwala liczyć na to, że aproksymowana funkcja będzie zawarta w rodzinie <math>G \,</math>, albo przynajmniej w rodzinie <math>G \,</math> istnieje funkcja dająca mały błąd aproksymacji. Z drugiej jednak strony, im większa rodzina <math>G \,</math>, tym trudniejsze w realizacji jest zadanie przeszukiwania. Jak się przekonamy niżej, jest jeszcze jeden mankament wynikający z dużej liczby swobody, mianowicie zjawisko przeuczenia (lub inaczej nadmiernego dopasowania).

== Możliwości pomiaru błędu aproksymacji ==
Pomiar błędu aproksymacji (tj. obliczenie wartości metryki dla dwóch funkcji z <math>\Omega \,</math>) wymaga pełnej znajomości obu rozważanych funkcji, tzn. możliwości obliczenia wartości każdej funkcji dla każdego argumentu. Jak założono wcześniej, nie jest to możliwe w przypadku funkcji aproksymowanej <math>f \,</math> - dla niej dysponujemy tylko zbiorem obserwacji. Tak więc w czasie realizacji wnioskowania indukcyjnego jako zadania przeszukiwania musimy się posługiwać przybliżoną wartością błędu aproksymacji, tzw. ''próbkowym'' błędem aproksymacji, lub po prostu błędem próbkowym.

== Przykłady błędu próbkowego ==
W zbiorze <math>\Omega \,</math> funkcji postaci <math>[0,1] \rightarrow [-1,1] \,</math>  zakładaliśmy, że metryka była określona jako

<!-- equation 0 -->
:{| width="100%"
| width="95%" align="left" | <math>|f_1, f_2| = \int_0^1 [f_1(x)-f_2(x)]^2 d x
 \,</math>
|}
Jeśli dysponujemy tylko zbiorem wartości funkcji <math>f_1, f_2 \,</math> w punktach należących do zbioru <math>S \,</math>, wówczas błąd próbkowy zdefiniujemy jako

<!-- equation 0 -->
:{| width="100%"
| width="95%" align="left" | <math>e(f_1, f_2) = \frac{1}{N} \sum_{x \in S} [f_1(x)-f_2(x)]^2
 \,</math>
|}
gdzie <math>N \,</math> jest liczebnością zbioru <math>S \,</math>. Błąd próbkowy opisany powyżej nosi nazwę błędu średniokwadratowego.

W zbiorze <math>\Omega \,</math> funkcji postaci <math>\{0,1\}^4 \rightarrow \{0,1\} \,</math>  zakładaliśmy, że metryka była określona jako

<!-- equation 0 -->
:{| width="100%"
| width="95%" align="left" | <math>|f_1, f_2| = \sum_{{\mathbf x} \in D} |f_1({\mathbf x})-f_2({\mathbf x})|.
 \,</math>
|}
Jeśli dysponujemy tylko zbiorem wartości funkcji <math>f_1, f_2 \,</math> w punktach należących do zbioru <math>S \,</math>, wówczas błąd próbkowy zdefiniujemy jako

<!-- equation 0 -->
:{| width="100%"
| width="95%" align="left" | <math>e(f_1, f_2) = \sum_{{\mathbf x} \in A} |f_1({\mathbf x})-f_2({\mathbf x})|
 \,</math>
|}
Zauważmy, że w tym przypadku błąd próbkowy nie będzie nigdy mniejszy niż rzeczywisty błąd aproksymacji.

Fakt posługiwania się wartością przybliżoną jest źródłem poważnych kłopotów, gdyż minimalizacja błędu próbkowego niekoniecznie musi iść w parze z minimalizacją „prawdziwego” błędu aproksymacji. W szczególnie „złośliwych” przypadkach może się zdarzyć, że błąd aproksymacji ''wzrasta'' wraz ze zmniejszającym się błędem próbkowym.  Typowym przykładem takiego przypadku jest zbyt duża liczba stopni swobody modelu, a co za tym idzie zbyt szeroka klasa funkcji <math>G \,</math> w porównaniu z zawartością całego zbioru <math>\Omega \,</math>. Mówi się wtedy, że zaszło ''nadmierne dopasowanie'' funkcji aproksymującej do danych albo ''przeuczenie'' modelu.

=== Przykład 3 ===
Załóżmy ponownie, że <math>\Omega \,</math> jest zbiorem funkcji postaci <math>[0,1] \rightarrow [-1,1] \,</math> i że posługujemy się błędem kwadratowym i średniokwadratowym. Będziemy ponownie aproksymować funkcję <math>f(x)=(x-0.5)^2 \,</math>, tym razem jednak, w celu uzyskania większej dokładności, aproksymująca funkcja będzie postaci

<!-- equation 0 -->
:{| width="100%"
| width="95%" align="left" | <math>g(x) = a_1\cos(b_1x+c_1)+a_2\cos(b_2x+c_2)+a_3\cos(b_3x+c_3)+d,
 \,</math>
|}
jest więc opisana za pomocą jedenastu  parametrów. Można się przekonać wykonując proste obliczenia numeryczne, że można uzyskać aproksymator o nieco mniejszym niż w przykładzie 1 błędzie kwadratowym przyjmując wartości parametrów:
<math>a_1=-0.110, \,</math> <math>b_1=3.142, \,</math> <math>c_1=-1.571, \,</math> <math>a_2=-0.660, \,</math> <math>b_2=2.100, \,</math> <math>c_2=-1.050, \,</math> <math>a_3=-0.076, \,</math> <math>b_3-3.600, \,</math> <math>c_3=-1.800, d=0.25 \,</math>
(jednak nie jest to raczej aproksymator o optymalnych wartościach parametrów). Wykres funkcji aproksymowanej (linia czerwona) i aproksymującej (linia niebieska) jest podany na poniższym rysunku

<!-- begin{wiki} -->
[[Grafika:SI M9 wykres 2.png]]

<!-- end{wiki} -->
Jednak jeśli wyznaczamy parametry aproksymatora poprzez minimalizację próbkowego błędu średniokwadratowego, to może to doprowadzić do postaci funkcji <math>g \,</math> mającej niewiele wspólnego funkcją <math>f \,</math>. Jeśli aproksymator rozważany w tym przykładzie będzie wynikiem minimalizacji błędu średniokwadratowego, a zbiór trenujący ma postać


<!-- \begin{tabular} -->
:{| border="1" style="text-align:center"
|<math>x \,</math>    ||    <math>f(x) \,</math> 
|-
|0  ||  0.25 
|-
|0.06  ||  0.19 
|-
|0.12  ||  0.14 
|-
|0.21  ||  0.08 
|-
|0.25  ||  0.06 
|-
|0.32  ||  0.03 
|-
|0.37  ||  0.02 
|-
|0.5  ||  0 
|-
|0.62  ||  0.01 
|-
|0.75  ||  0.06 
|-
|0.79  ||  0.08 
|-
|0.88  ||  0.14 
|-
|0.94  ||  0.19 
|-
|1  ||  0.25 
|-
|}
<!-- end{tabular} -->

to parametry, dla których można doprowadzić do zerowego błędu aproksymacji są następujące:
<math>a_1=-0.11, \,</math> <math>b_1=3.14, \,</math> <math>c_1=-1.5708, \,</math> <math>a_2=-0.07, \,</math> <math>b_2=2.1, \,</math> <math>c_2=-1.0500, \,</math> <math>d=0.25, \,</math> <math>a_3=-0.08, \,</math> <math>b_3=46.5, \,</math> <math>c_3=-23.2500, d=0.25, \,</math>
a wykresy funkcji aproksymowanej (linia czerwona) i aproksymującej (linia niebieska) wyglądają jak poniżej.

<!-- begin{wiki} -->
[[Grafika:SI M9 wykres 3.png]]

<!-- end{wiki} -->
Jak do tego doszło? Odpowiedź jest prosta - parametry aproksymatora zostały wyznaczone tak, aby  wykres funkcji <math>g \,</math> przechodził jak najbliżej punktów zawartych w zbiorze trenującym. Określanie parametrów poprzez minimalizację błędu średniokwadratowego na zbiorze trenującym jest więc „ślepe” na punkt zawarte poza tym zbiorem, a wynik jest tym bardziej odmienny od możliwego do uzyskania przez minimalizację błędu kwadratowego, im więcej jest stopni swobody (w naszym przypadku parametrów) określających funkcję aproksymującą.

== Zasada brzytwy Ockhama ==
Modelowanie jest procesem towarzyszącym nie tylko sztucznej inteligencji, matematyce, fizyce, chemii itp., ale również m.in. filozofii, teologii. Na gruncie tych ostatnich nauk została sformułowana słynna zasada, która mówi że „nie należy mnożyć bytów ponad potrzebę”, tzn. należy starać się tłumaczyć zjawiska w najprostszy możliwy sposób. Zasadę tę sformułował Ockham, od którego nazwiska pochodzi nazwa „brzytwy Ockhama”, którą „wycina się” zbędne byty
(por. np. http://pl.wikipedia.org/wiki/Brzytwa_Ockhama).

Na gruncie sztucznej inteligencji, a w szczególności metod aproksymacji, dąży się zgodnie z zasadą  brzytwy Ockhama do modeli o możliwie najmniejszej liczbie stopni swobody. Dzięki temu zmniejsza się niebezpieczeństwo przeuczenia modelu.

== Zbiory trenujące i testowe ==
Zapobieganie nadmiernemu dopasowaniu jest przypuszczalnie najbardziej wyzywającym zadaniem uczenia z nauczycielem. Częściowe rozwiązanie tego problemu przynosi metoda polegająca na podzieleniu obserwacji, którymi się dysponuje w czasie uczenia, na dwa rozłączne podzbiory.

Pierwszy z nich, zwany ''zbiorem uczącym'', jest wykorzystywany do szacowania próbkowego błędu aproksymacji w procesie poszukiwania funkcji aproksymującej minimalizującej ten błąd. Gdy już zostanie ona wyznaczona, przystępuje się do obliczenia próbkowego błędu aproksymacji na drugim zbiorze, zwanym ''zbiorem testowym''.

Porównanie wartości obu błędów dostarcza pewnej informacji o tym, na ile realną groźbę stanowi nadmierne dopasowanie. Jeśli wartości obu błędów są porównywalne (zazwyczaj, choć nie zawsze, błąd na zbiorze uczącym będzie mniejszy), to niebezpieczeństwo nadmiernego dopasowania jest niewielkie. Natomiast duża różnica między oboma wartościami błędu próbkowego stanowi sygnał ostrzegawczy przed ryzykiem nadmiernego dopasowania.

Gdy zostanie powzięte podejrzenie o przeuczeniu modelu, trzeba próbować temu zaradzić. Jednym ze sposobów nich jest wykonanie ponownego podziału zbioru obserwacji na zbiór trenujący i testowy, i ponowne wykonanie modelu. Innym sposobem jest umiejętne zmniejszenie liczby stopni swobody wykorzystywanego modelu (a tym samym, zastąpienie zbioru funkcji aproksymujących <math>G \,</math> zbiorem <math>G' \subset G \,</math>) i powtórzenie procesu modelowania.