Metody odkrywania wiedzy: wykład 13
Aproksymacja funkcji

Paweł Cichosz

Date: 2001/2002

Wykład prezentuje wybrane metody uczenia się aproksymacji funkcji, a więc znajdowania zależności wybranego atrybutu ciągłego traktowanego jako funkcja docelowa od innych atrybutów (najczęściej również ciągłych), przy czym głównym celem jest możliwie dokładne, a niekoniecznie czytelne dla człowieka, reprezentowanie tej zależności.

Specyfika aproksymacji

Aproksymacja, nazywana czasem klasyfikacją z ciągłymi klasami, polega na poszukiwaniu zależności wybranego atrybutu ciągłego, nazywanego funkcją docelową, od innych atrybutów, najczęściej również ciągłych. Zależność ta służyć ma nie tyle prezentacji i interpretacji przez człowieka, co raczej przewidywaniu nieznanych wartości funkcji docelowej dla nowych danych, więc główny nacisk kładzie się na dokładne, a niekoniecznie czytelne, reprezentowanie zależności. W przypadku zależności dotyczących atrybutów ciągłych dokładność jest szczególnie trudna do pogodzenia z czytelnością. Wtedy, gdy czytelność ma priorytet nad dokładnością, sięga się po metody odkrywania równań.

Cechy

Mówiąc o aproksymacji funkcji jak zwykle będziemy rozważać pewną dziedzinę $X$, na której jest określona funkcja docelowa $f:X\mapsto\Re$ oraz pewna liczba atrybutów. Na ogół będziemy zakładać, że wszystkie z nich są ciągłe, i dla podkreślenia tego założenia stosować inną niż dotąd terminologię i notację: zamiast o atrybutach będzie mowa o cechach, oznaczanych $\phi_0,\phi_1,\dots,\phi_{n-1}$. Niekiedy okaże się przydatne założenie, że dodatkowo jest zawsze określona cecha $\phi_n$ taka, że $\phi_n(x)=1$ dla każdego $x\in X$. Przez $\phi(x)$ oznaczać będziemy cały wektor $n$ (lub $n+1$) cech przykładu $x$.

Notacja wektorowa

Ponieważ wektory cech są wektorami liczb rzeczywistych, a wartości aproksymowanej funkcji są również liczbami rzeczywistymi, operacje wykonywane przez algorytmy aproksymacji funkcji często mogą być bezpośrednio wyrażone matematycznie, przy czym zazwyczaj odpowiednie równania najprościej jest zapisać wektorowo. Elementy wszystkich wektorów będą numerowane od 0 i oznaczane za pomocą indeksów dolnych. Przy wektorowym zapisie operacji algebraicznych wektory muszą być niekiedy traktowane jako macierze złożone z jednej kolumny lub jednego wiersza. Tu przyjmiemy, że wektory są kolumnowe, czyli traktuje się je jako macierze złożone z jednej kolumny.

Cykle uczenia się

Wiele algorytmów aproksymacji do wyznaczenia hipotezy dobrze przybliżającej funkcję docelową może wymagać wielokrotnego przetwarzania całego zbioru trenującego, oczywiście jeśli jest on skończony i znany w całości. Możemy więc powiedzieć, że proces uczenia się dla takich algorytmów w naturalny sposób jest podzielony na pewną liczbę cykli, z których każdy obejmuje jednokrotne przetwarzanie każdego przykładu trenującego. Jest to właściwość, z którą nie mieliśmy wcześniej do czynienia.

Informacja trenująca

Możliwe są różne postaci informacji trenującej, służącej do uczenia się aproksymacji funkcji. Oczywiście najbardziej naturalną postacią przykładu trenującego jest para $\langle x,f(x)\rangle$ dla pewnego $x\in X$, analogiczna do przykładu etykietowanego do uczenia się pojęć. W większej części praktycznych zastosowań uczenia się aproksymacji do odkrywania wiedzy tak właśnie będzie. Niekiedy jednak, ze względu na specyficzne wymogi zastosowania uczącego się aproksymatora, wygodniej jest jako drugi element pary trenującej, zamiast wartości funcji, przekazywać błąd wartości aktualnej hipotezy ucznia. Przykładem trenującym jest wówczas para $\langle x,f(x)-h(x)\rangle$ dla pewnego $x\in X$, przy czym $h$ oznacza aktualną hipotezę ucznia, podlegającą zmianom w trakcie uczenia się. W każdym przypadku będziemy dla wygody mówić o zbiorze trenującym $T$ jako o pewnym podzbiorze dziedziny $X$, zakładając, że należącym do niego przykładom towarzyszą etykiety odpowiedniej postaci.

Metody parametryczne

Do najczęściej stosowanych uczących się aproksymatorów funkcji należą metody oparte na reprezentacji parametrycznej. Wymagają one, aby przykłady (argumenty aproksymowanej funkcji) były opisywane za pomocą wektorów rzeczywistoliczbowych cech oraz zakładają, że hipoteza jest reprezentowana w postaci wektora również rzeczywistych parametrów, często nazywanych wagami. Uczenie się polega na modyfikowaniu wag na podstawie przykładów trenujących w sposób prowadzący do zmniejszenia błędu reprezentowanej przez nie hipotezy w stosunku do nieznanej funkcji docelowej. Prezentując metody parametryczne będziemy tym zakładać, że dla każdego $x\in X$ określona jest dodatkowa cecha $\phi_n(x)=1$.

Obliczanie wartości funkcji

Dla przykładu $x\in X$ i pewnej hipotezy $h$ reprezentowanej przez wektor wag $w$ wartość $h(x)$ jest obliczana na podstawie $\phi(x)$ i $w$. Możemy napisać:

$$h(x) = F(\phi(x),w)$$ (1)

przy czym $F$ jest pewną funkcją, opisującą zależność wyjść aproksymatora od wektora cech przykładu i wektora wag. Zależność ta, którą nazwiemy funkcją odwzorowania, jest indywidualną właściwością poszczególnych aproksymatorów opartych na reprezentacji parametrycznej. Decyduje ona o możliwości aproksymowania różnych funkcji docelowych, a także o konkretnym algorytmie uczenia się. Hipotezę aproksymatora parametrycznego definiują łącznie wektor wag $w$ oraz funkcja odwzorowania $F$. Jeśli jednak przyjmiemy, że dla rozważanego konkretnego aproksymatora funkcja odwzorowania ma ustaloną postać, co w większości przypadków jest prawdą, to do jednoznacznego wyznaczenia hipotezy wystarcza wektor wag. Hipotezę reprezentowaną przez wektor wag $w$ będziemy w dalszej dyskusji oznaczać przez $h_w$.

Aktualizacja wartości funkcji

Dla każdego uczącego się aproksymatora największe znaczenie ma wykorzystywany przez niego mechanizm uczenia się. W przypadku metod parametrycznych chodzi o sposób modyfikowania wektora wag $w$ na podstawie przykładu trenującego $\langle x, f(x)-h_w(x)\rangle$ dla pewnego $x\in X$, przy czym $f(x)$ jest wartością funkcji docelowej dla przykładu $x$, a $h_w(x)$ jej przybliżeniem obliczanym na podstawie wektora $w$ w przedstawiony wyżej sposób.

Załóżmy, że dany jest ustalony zbiór $T$ etykietowanych błędami przykładów trenujących. Najprostsze sformułowanie celu uczenia się polega na zażądaniu znalezienia takiego wektora wag, dla którego względny bądź średniokwadratowy błąd próbki na zbiorze trenującym będzie możliwie najmniejszy. Błędy te będą minimalizowane wtedy, kiedy kiedy minimalizowana będzie nieco inna, dogodniejsza ze względów analitycznych wielkość:

$$\varepsilon^f_T(h_w)=\sum_{x\in T}\frac{1}{2}\big(f(x)-h_w(x)\big)^2$$ (2)

którą nazwiemy funkcją błędu. Do najbardziej powszechnie wykorzystywanych, choć nie pozbawionych wad, mechanizmów uczenia się prowadzących do tak sformułowanego celu jest reguła spadku gradientu. Zgodnie z nią (jednokrotne) przetworzenie zbioru trenującego $T$ powinno polegać na modyfikacji wektora wag przez dodanie do niego wektora przyrostów wag, wyznaczonego w następujący sposób:

$$\Delta_w = -\beta\nabla_w\varepsilon^f_T(h_w)$$ (3)

czyli wykonaniu modyfikacji $w:=w+\Delta_w$, przy czym $\nabla_w\varepsilon^f_T(h_w)$ oznacza wektor pochodnych cząstkowych $\varepsilon^f_T(h_w)$ względem poszczególnych wag. Dla pojedynczej wagi $w_i$ możemy tę samą regułę zapisać następująco:

$$\Delta_{w_i} = -\beta\frac{\partial\varepsilon^f_T(h_w)} {\partial w_i}$$ (4)

Parametr $\beta$ jest liczbą rzeczywistą na ogół z przedziału $(0,1]$, nazywaną rozmiarem kroku, która określa skalę przeprowadzanej modyfikacji wag. Reguła spadku gradientu interpretowana w najbardziej bezpośredni sposób mówi, że należy zmienić wagi w tym kierunku, który doprowadzi do zmniejszenia wartości błędu. Wykonywane w ten sposób modyfikacje doprowadzą więc, przy odpowiednio małych wartościach $\beta$, do znalezienia wektora wag, dla którego błąd aproksymacji osiąga przynajmniej lokalne minimum.

Różniczkując $\varepsilon^f_T(h)$ względem wagi $w_i$ otrzymujemy, jak łatwo się przekonać,

$$\frac{\partial\varepsilon^f_T(h_w)}{\partial w_i} = \sum_{x\in T} (f(x)-h_w(x)) \cdot\Big(-\frac{\partial h_w(x)}{\partial w_i}\Big)$$ (5)

co umożliwia przepisanie naszej reguły w zmodyfikowanej postaci:

$$\Delta_{w_i} = \sum_{x\in T} \beta(f(x)-h_w(x)) \frac{\partial h_w(x)}{\partial w_i}$$ (6)

czy też w zapisie wektorowym

$$\Delta_w = \sum_{x\in T}\beta(f(x)-h_w(x))\nabla_w h_w(x)$$ (7)

Uzyskana w ten sposób reguła modyfikacji wag nazywana bywa uogólnioną regułą delta. Reprezentuje ona ogólny algorytm uczenia się w parametrycznych aproksymatorach funkcji. Jego konkretyzacja zależy oczywiście od charakteru zależności $h_w(x)$ od $w$ dla każdego $x\in X$, za co odpowiada funkcja odwzorowania $F$.

Zauważmy, że powyższą regułę, zgodnie z którą modyfikacja wag następuje na podstawie sumy pewnych wartości obliczonych dla poszczególnych przykładów trenujących, możemy również przedstawić w następującej postaci:

$$\Delta_w = \sum_{x\in T} \Delta_w(x)$$ (8)

przy czym $\Delta_w(x)$ określa modyfikację wag, wynikającą z przetworzenia pojedynczego przykładu trenującego $x\in T$, obliczaną zgodnie ze wzorem:

$$\Delta_w(x) = \beta(f(x)-h_w(x))\nabla_w h_w(x)$$ (9)

Dzięki takiemu sformułowaniu uogólniona reguła delta może być stosowana w inkrementacyjnym trybie uczenia się, kiedy zmiany wektora wag dokonuje się bezpośrednio po uwzględnienieniu każdego przykładu $x\in T$ przez operację podstawienia $w:=w+\Delta_w(x)$.

Aproksymator liniowy

Najprostszą konkretyzację przedstawionej ogólnej reguły uczenia się aproksymatorów opartych na reprezentacji parametrycznej uzyskujemy dla aproksymatorów liniowych, czyli takich, w których opisywana przez $F$ zależność wartości $h_w(x)$ od $\phi(x)$ ma charakter liniowy, a wektor wag $w$ tę zależność parametryzuje. Można wówczas przyjąć, że wektor $w$ liczy tyle elementów, ile cech jest używanych do opisu przykładów, czyli $n+1$ (z uwzględnieniem dodatkowej cechy o numerze $n$ stale równej $1$), a wartości funkcji są obliczane zgodnie ze wzorem:

$$h_w(x) = \sum_{i=0}^n\phi_i(x)w_i$$ (10)

czyli w zapisie wektorowym

$$h_w(x) = w^{\mathrm{T}}\phi(x)$$ (11)

Zauważmy, że dla dowolnego przykładu $x$, dla którego wartości cech spełniają warunek $\phi_0(x)=\phi_1(x)=\dots=\phi_{n-1}(x)=0$, uzyskiwalibyśmy z tego wyrażenia zawsze $h_w(x)=0$ bez względu na wektor wag $w$, gdyby nie wprowadzenie dodatkowej cechy $\phi_n(x)=1$, dzięki której mamy wtedy $h_w(x)=w_n$. Dodatkowa cecha powoduje zatem dodanie składnika $w_n$ do obliczonej bez jej użycia wartości $h_w(x)$ dla każdego przykładu $x$. Taki sam efekt można uzyskać w inny sposób, przez zmianę formuły, według której aproksymator liniowy oblicza wartość $h_w(x)$, lecz dzięki użyciu cechy $\phi_n$ jest możliwy jej prostszy i wygodniejszy do analizy zapis.

Nietrudno się przekonać, że dla aproksymatorów liniowych

$$\frac{\partial h_w(x)}{\partial w_i} = \phi_i(x)$$ (12)

czyli

$$\nabla_w h_w(x) = \phi(x)$$ (13)

Umożliwia to zapisanie uogólnionej reguły delta w następującej uproszczonej postaci, w której nazywana jest ona po prostu regułą delta (także regułą LMS lub regułą Widrowa-Hoffa):

$$\Delta_w = \sum_{x\in T}\beta(f(x)-h_w(x))\phi(x)$$ (14)

W wersji inkrementacyjnej dla dowolnego przykładu trenującego $x$ mamy odpowiednio:

$$\Delta_w(x) = \beta(f(x)-h_w(x))\phi(x)$$ (15)

Dla pojedynczej wagi $w_i$, $i=0,1,\dots,n$, otrzymujemy:

$$\Delta_{w_i} ={} \sum_{x\in T}\beta(f(x)-h_w(x))\phi_i(x)$$ (16)

$$\Delta_{w_i}(x) ={} \beta(f(x)-h_w(x))\phi_i(x)$$ (17)

Regułę Widrowa-Hoffa formułuje się niekiedy także w wersji znormalizowanej, w której obliczana wielkość modyfikacji dla każdej wagi jest dzielona przez sumę wartości cech przykładu, na podstawie którego dokonuje się tej modyfikacji:

$$\Delta_w ={} \sum_{x\in T}\frac{\beta(f(x)-h_w(x))\phi(x)}{\sum_{i=0}^n w_i}$$ (18)

$$\Delta_w(x) ={} \frac{\beta(f(x)-h_w(x))\phi(x)}{\sum_{i=0}^n w_i}$$ (19)

Taką normalizację można interpretować jako równomierne ,,rozdzielanie'' błędu $f(x)-h_w(x)$ między wszystkie wagi w stopniu proporcjonalnym do udziału każdej z nich w obliczaniu $h_w(x)$. Według innego punktu widzenia mamy tu do czynienia ze swego rodzaju adaptacyjnym doborem rozmiaru kroku.

Stosujące regułę LMS liniowe aproksymatory parametryczne są także nazywane prostymi perceptronami i mogą być traktowane jako szczególny, najprostszy rodzaj sieci neuronowych.

Aproksymatory nieliniowe

Aproksymatory liniowe mają szereg bardzo atrakcyjnych z praktycznego punktu widzenia właściwości. Uczą się stosunkowo szybko, mechanizm uczenia się jest prosty analitycznie i implementacyjnie oraz tani obliczeniowo, w dodatku posługiwanie się regułą spadku gradientu w przypadku liniowej zależności $h_w(x)$ od $\phi(x)$ nie grozi znalezieniem lokalnych minimów funkcji $\varepsilon^f_T(h_w)$, różnych od poszukiwanego minimum globalnego. Te niewątpliwe zalety są okupione jedną poważną wadą. Wiele funkcji docelowych, zwłaszcza tych interesujących ze względu na realne zastosowania, nie może być z dostatecznie dużą dokładnością reprezentowanych jako jedynie liniowa kombinacja cech przykładów. Wówczas zasadne jest sięgnięcie po aproksymatory nieliniowe.

Najlepiej znanym parametrycznym aproksymatorem nieliniowym jest perceptron wielowarstwowy, czyli najbardziej popularny i najczęściej stosowany rodzaj sieci neuronowych. Do uczenia się aproksymacji za pomocą perceptrona wielowarstwowego najczęściej stosuje się algorytm propagacji wstecznej błędu. Metody te mają bogatą literaturę i nie będziemy o nich mówić.

W konkretnych zastosowaniach mogą być wykorzystywane specyficzne aproksymatory nieliniowe, z funkcją odwzorowania zaprojektowaną z uwzględnieniem dostępnej wiedzy o dziedzinie. W każdym przypadku można wyprowadzić odpowiednią konkretyzację uogólnionej reguły delta. W szczególności dla najprostszego rodzaju aproksymatorów nieliniowych, w których wartość hipotezy oblicza się według wzoru:

$$h_w(x) = \sum_{i=0}^n\zeta(\phi_i(x))w_i$$ (20)

gdzie $\zeta$ jest funkcją nieliniowo przekształcającą pojedyncze cechy, mamy:

$$\Delta_w = \sum_{x\in T}\beta(f(x)-h_w(x))\zeta(\phi(x))$$ (21)

W ten sposób można łatwo uwzględnić dostępną niekiedy wiedzę, że wartości funkcji docelowej zależą np. od kwadratów czy sinusów cech. Postępowanie takie to w istocie zastępowanie cech pierwotnie dostępnych nowymi, o czym będzie jeszcze mowa.

Metody wykładniczo-gradientowe

Przedstawione reguły aktualizacji wag dla liniowych i nieliniowych aproksymatorów parametrycznych są konkretyzacjami reguły spadku gradientu, zgodnie z którą kierunek i wielkość zmiany wag zależą od gradientu błędu, w tym przypadku średniokwadratowego. Przedstawiona wersja tych metod wykorzystuje regułę spadku gradientu do addytywnej modyfikacji wektora wag: po wyznaczeniu wartości błędu $\Delta_w$ jest on dodawany do wektora wag zgodnie z operacją podstawienia $w:=w+\Delta_w$ lub, dla pojedynczej wagi, $w_i:=w_i+\Delta_{w_i}$. Niedawno zaproponowano alternatywne i niekiedy bardziej skuteczne podejście, polegające na multiplikatywnej modyfikacji wag. Punktem wyjścia do tej koncepcji jest zapisanie addytywnej reguły modyfikacji dla logarytmów wag:

$$\ln w_i := \ln w_i + \Delta_{w_i}$$ (22)

co może być zapisane w równoważnej postaci:

$$w_i:=w_i\cdot\exp(\Delta_{w_i})$$ (23)

Pod pewnymi warunkami powyższa multiplikatywna reguła może być stosowana z wartościami błędów $\Delta_{w_i}$, wyznaczanymi tak samo jak w przypadku klasycznej modyfikacji addytywnej. W szczególności niezbędne jest wówczas, aby wszystkie wagi były liczbami dodatnimi. Tymczasem jest oczywiste, że w celu reprezentowania pewnych funkcji może zachodzić potrzeba wykorzystywania również ujemnych wag. Prostym rozwiązaniem tego problemu w przypadku aproksymatorów liniowych może być ograniczenie się do dodatnich wag, lecz powielenie wektora cech ze znakiem minus. Oznacza to reprezentowanie każdego przykładu $x$ za pomocą wektora cech

$$\langle \phi_0(x),\dots,\phi_{n-1}(x),\phi_n(x), -\phi_0(x),\dots,-\phi_{n-1}(x),-\phi_n(x)\rangle$$ (24)

przy czym jak zwykle przyjmujemy $\phi_n(x)=1$.

Regresja

Metody parametrycznej aproksymacji funkcji w nieco innym ujęciu są także nazywane metodami regresji. Regresja oznacza dopasowywanie zbioru parametrów pewnej formuły matematycznej, nazywanej modelem regresyjnym, do dostępnych danych, tak aby uzyskany w ten sposób model jak najdokładniej opisywał te dane. Parametryczny aproksymator funkcji może być więc traktowany jako model regresyjny, a wektor wag stanowi jego parametry, które powinny być dobrane tak, aby funkcja docelowa była jak najlepiej przybliżana na zbiorze trenującym. To, co odróżnia klasyczną regresję od interesujących nas tutaj aproksymatorów funkcji, to właśnie sposób wyznaczania wag. Zamiast rozważanych przez nas reguł aktualizacji, których wielokrotne stosowanie z odpowiednio małym rozmiarem kroku przybliża wagi do wartości minimalizujących błąd, mówiąc o regresji ma się na ogół na myśli analityczne wyznaczanie właściwego wektora wag. Nie jest to jednak różnica rozwiązywanego problemu, a tylko najczęściej stosowanych technik jego rozwiązania. Nie ma więc żadnych przeszkód, aby uczące się parametryczne aproksymatory funkcji nazywać algorytmami regresji, wyróżniając regresję liniową, w której funkcja odwzorowania jest liniowo zależna od cech, oraz różne formy regresji nieliniowej.

Tradycyjne rozwiązanie problemu regresji liniowej sprowadza się do znalezienia minimalnokwadratowego rozwiązania układu równań, powstałego przez zapisanie równania:

$$\sum_{i=0}^n\phi_i(x)w_i = f(x)$$ (25)

dla każdego przykładu trenującego $x\in T$. W zapisie macierzowym taki układ równań możemy zapisać następująco:

$$\phi(T)w = f(T)$$ (26)

gdzie $\phi(T)$ oznacza macierz wartości cech przykładów ze zbioru $T$ (wiersze odpowiadają przykładom, kolumny odpowiadają cechom), a $f(T)$ oznacza kolumnowy wektor wartości funkcji docelowej dla przykładów ze zbioru $T$. Znalezienie rozwiązania polega na lewostronnym przemnożeniu obu stron równania przez transponowaną macierz cech:

$$\phi(T)^{\mathrm{T}}\phi(T)w = \phi(T)^{\mathrm{T}}f(T)$$ (27)

i następnie odwróceniu (jeśli to możliwe) kwadratowej macierzy $\phi(T)^{\mathrm{T}}\phi(T)$. Po przemnożeniu lewostronnym przec macierz odwrotną do niej dostajemy:

$$w = (\phi(T)^{\mathrm{T}}\phi(T))^{-1}\phi(T)^{\mathrm{T}}f(T)$$ (28)

co jest poszukiwanym rozwiązaniem.

Niestety, złożoność obliczeniowa odwracania macierzy ogranicza możliwość stosowania takiej metody do stosunkowo niewielkich zbiorów trenujących -- dla większej liczby przykładów bardziej opłacalna jest iteracyjna modyfikacja wag za pomocą reguły delta.

Rozszerzona reprezentacja

Aproksymator liniowy, który charakteryzuje się dużą szybkością uczenia się oraz niskim kosztem obliczeniowym, nie może być bezpośrednio stosowany zbyt szeroko, gdyż w wielu dziedzinach występują zależności o zdecydowanie nieliniowym charakterze. Z kolei uniwersalne parametryczne aproksymatory nieliniowe, jakimi są perceptrony wielowarstwowe, uczą się wolniej i są narażone na lokalne minima funkcji błędu. Jeden z pomysłów na zwiększenie zakresu stosowania aproksymatora liniowego polega na zastosowaniu go do odpowiednio zmodyfikowanych przestrzeni cech.

Rozszerzanie opisu przykładów

Podstawowa koncepcja rozszerzonej reprezentacji jest niezwykle prosta. Podczas gdy aproksymatory nieliniowe starają się uzyskać zwiększenie mocy reprezentacji przez wykorzystanie nieliniowej zależności wartości hipotezy od wektora wag i cech przykładu, metody rozszerzonej reprezentacji dążą do osiągnięcia tego samego celu, pozostawiając liniową zależność, lecz rozszerzając w zamian, na ogół znacznie, zestaw cech opisujących przykłady. Jeśli postępowanie takie przypomina konstruktywną indukcję, to rzecz jasna podobieństwo nie jest przypadkowe. W jednym i drugim przypadku chodzi o ,,poprawienie'' opisu przykładów, tak aby nie zmieniony algorytm uczenia się mógł uzyskiwać lepsze wyniki.

Aby nieco sformalizować naszkicowany pomysł, założymy, że dla każdego przykładu $x\in X$ jego $n$-elementowy wektor cech $\phi(x)$ zostaje w pewien sposób przekształcony w $n'$-elementowy rozszerzony wektor cech $\phi'(x)$, przy czym na ogół $n'\gg n$. W obu przypadkach może być oczywiście dodana specjalna cecha $\phi_n(x)=\phi_{n'}(x)=1$ dla każdego $x$, lecz często nie jest to konieczne -- rozszerzenie reprezentacji może eliminować powody, dla których w przypadku zwykłych aproksymatorów parametrycznych taka cecha była potrzebna. Nie będziemy więc brać jej pod uwagę w poniższej dyskusji.

Wektor $\phi'(x)$ stanowi rozszerzoną reprezentację przykładu $x$. Możemy na nią patrzeć jak na przyporządkowanie przykładowi pewnego punktu w $n'$-wymiarowej przestrzeni, podczas gdy oryginalna reprezentacja $\phi(x)$ lokowała ten przykład w przestrzeni o znacznie mniejszej wymiarowości. Wartość hipotezy reprezentowanej przez wektor wag $w$ jest wówczas obliczany dla przykładu $x$ tak jak przez aproksymator liniowy działający w rozszerzonej przestrzeni, czyli

$$h_w(x) = \sum_{i=0}^{n'-1}\phi'_i(x)w_i = w^{\mathrm{T}}\phi'(x)$$ (29)

przy czym liczba wag musi być równa liczbie cech w rozszerzonej reprezentacji.

Podstawowe znaczenie dla oceny przydatności metod aproksymacji wykorzystujących rozszerzoną reprezentację mają przesłanki, na których opiera się oczekiwanie, że zwiększanie wymiarowości przestrzeni cech przyniesie pożytek. Kryje się za nim nadzieja, że odwzorowanie nieliniowe w oryginalnej przestrzeni cech może się stać liniowe lub możliwe do dobrego przybliżenia za pomocą odwzorowania liniowego w rozszerzonej przestrzeni. Nie jest trudno przekonać się, biorąc pod uwagę proste przykłady funkcji docelowych, że istotnie może się tak zdarzyć, jeśli cechy $\phi'$ zostaną w odpowiedni sposób dobrane. W szczególności dla każdej funkcji docelowej można wskazać takie rozszerzone cechy $\phi'$, dla których funkcja ta może być reprezentowana liniowo. O najprostszym wariancie tego podejścia, w którym $n'=n$ i $\phi'(x)=\zeta(\phi(x))$ dla pewnej nieliniowej funkcji $\zeta$ była już mowa wyżej. W niektórych zastosowaniach klasa funkcji docelowej jest w istocie znana i tego typu proste podejście może dać zaskakująco dobre efekty w porównaniu z aproksymatorami ,,prawdziwie'' nieliniowymi. Nas jednak najbardziej interesować będzie maksymalnie ogólny przypadek, kiedy wystarczająca wiedza na temat funkcji docelowej nie jest dostępna i rozszerzoną reprezentację należy dobrać w ten sposób, aby była możliwie uniwersalna i mogła być użyta do skutecznego uczenia się różnych funkcji docelowych.

Reprezentacja randomizowana

Najprostszym uniwersalnym i przy tym zadziwiająco skutecznym sposobem rozszerzania reprezentacji jest stosowanie reprezentacji randomizowanej. Dla ustalonego $n'\gg n$ wartości cech rozszerzonej przestrzeni wyznacza się na podstawie cech oryginalnych, stosując pewne przekształcenie zależne od losowych parametrów. Przekształcenia takie mogą być określane nie tylko dla przykładów opisywanych przez cechy ciągłe, jakimi zajmowaliśmy się dotychczas, lecz także przez dowolne atrybuty dyskretne. Można sobie wyobrazić bardzo wiele różnych szczegółowych przekształceń randomizowanych. Poniższy przykład to jedna z najprostszych możliwości.

Wygodnie będzie w poniższej dyskusji założyć, że przeciwdziedziną każdej cechy $\phi_i$ dla $i=0,1,\dots,n-1$ jest przedział $[0,1]$. Jeśli pierwotne cechy określone na rozważanej dziedzinie nie spełniają tego warunku, to można je poddać odpowiedniej normalizacji, o ile ich przeciwdziedziny są przedziałami obustronnie ograniczonymi.

Przyjmiemy teraz, że pierwotne cechy $\phi_0,\phi_1,\dots,\phi_{n-1}$ zostały już w razie potrzeby znormalizowane i każda z nich może przyjmować wartości z przedziału $[0,1]$. Wówczas rozszerzone cechy mogą być wyznaczane na podstawie cech pierwotnych dla każdego przykładu $x\in X$ według następującej formuły stosowanej dla wszystkich $i=0,1,\dots,n'-1$:

$$\phi'_i(x) = \xi\left(\frac{\sum_{j=0}^{n-1}\phi_j(x)r_{ij}} {\sum_{j=0}^{n-1}r_{ij}}\right)$$ (30)

przy czym dla dowolnego $y\in\Re$

$$\xi(y) = \begin{cases}0 & \text{jeśli $y\leq 0$,}\\ 1 & \text{jeśli $y>0$.} \end{cases}$$ (31)

Współczynniki $r_{ij}$, dla $i=0,1,\dots,n'-1$, $j=0,1,\dots,n-1$, są ustalonymi liczbami wybranymi losowo ze zbioru $\{-1,1\}$ podczas inicjowania aproksymatora i nie są zmieniane w trakcie jego działania. Wektor $\phi'(x)$ powstaje więc dla każdego przykładu $x\in X$ na podstawie wektora $\phi(x)$ w drodze pewnego nieliniowego przekształcenia, zależnego od ustalonych, lecz wybranych losowo parametrów. Nieliniowe przekształcenie jest w naszym przypadku reprezentowane przez funkcję skoku jednostkowego $\xi$, która przyjmuje wartość $1$ dla argumentów przekraczających 0 i wartość 0 dla argumentów poniżej 0. Argumentem tej funkcji jest średnia ważona wartości cech pierwotnych dla przykładu $x$, przy obliczaniu której rolę wag odgrywają losowo ustalone parametry aproksymatora. Podejście to jest motywowane nadzieją, że nieliniowość wprowadzona w ten sposób do zależności $h_w(x)$ od $\phi(x)$ będzie wystarczająca do dostatecznie dokładnego aproksymowania funkcji docelowej.

Rozproszone przybliżone kodowanie

Dużą skuteczność z efektywnością obliczeniową znakomicie łączy konstruowanie rozszerzonej reprezentacji za pomocą rozproszonego przybliżonego kodowania. W podejściu tym rozszerzona przestrzeń cech jest na ogół bardzo duża, lecz dla każdego przykładu $x\in X$ jedynie stosunkowo niewielka liczba rozszerzonych cech $\phi'_i(x)$ ma wartości różne od 0. Dzięki temu obliczenie $h_w(x)$ nie wiąże się z dużymi kosztami, gdyż wszystkie cechy o zerowych wartościach mogą zostać pominięte. Również proces znajdowania tych $i$, dla których $\phi'_i(x)\neq 0$, może być zazwyczaj przeprowadzony bardzo efektywnie. Ma to decydujące znaczenie dla praktycznej atrakcyjności rozproszonego przybliżonego kodowania.

W metodach, o których mowa, na ogół przyjmuje się, że cechy rozszerzonej przestrzeni są binarne. Dla każdego przykładu $x\in X$ oraz $i=0,1,\dots,n'-1$ mamy więc $\phi'_i(x)\in\{0,1\}$, przy czym liczba jedynek w wektorze $\phi'(x)$ jest znacznie mniejsza od liczby zer. Obliczenie $h_w(x)=w^{\mathrm{T}}\phi'(x)$ sprowadza się wówczas do zsumowania tych (niewielu) wag, dla których odpowiadające im cechy mają wartość $1$. Również aktualizacja funkcji dla danego przykładu trenującego sprowadza się do modyfikacji tylko tych wag, które odpowiadają cechom przyjmującym dla tego przykładu niezerową wartość. Oszczędzamy więc na obliczeniach zarówno podczas odtwarzania wartości aproksymowanej funkcji, jak i przy ich aktualizacji.

Jedną z konktryzacji tej koncepcji jest aproksymator CMAC (Cerebellar Model Articulation Controller). Wykorzystuje on pokrycia $n$-wymiarowej przestrzeni wartości pierwotnych cech $n$-wymiarowymi hiperprostopadłościanami, które nazwiemy kratkami (dla dwóch wymiarów będą to prostokąty, dla trzech -- prostopadłościany, itd.). Takie kratkowanie powstaje przez podzielenie zakresu wartości każdej cechy na pewne przedziały -- niekoniecznie równomiernie i niekoniecznie jednakowo dla każdej cechy. W aproskymatorze CMAC wykorzystuje się pewną liczbę $L$ takich kratkowań, przesuniętych względem siebie wzdłuż wszystkich (w najprostszym wariancie) lub niektórych (w bardziej wyrafinowanych wariantach) wymiarów. Każdy przykład $x$ reprezentowany przez wektor wartości cech $\phi(x)$ ,,trafia'' wówczas w jedną kratkę każdego z przesuniętych względem siebie kratkowań. Jeśli wyobrazimy sobie, że wszystkie kratki mają swoje numery od $1$ do $n'$, to dla każdego przykładu $x$ dostajemy $L$ numerów ,,trafionych'' przez niego kratek. Niech $I(x)$ oznacza zbiór tych numerów. Wówczas można przyjąć:

$$\phi'_i(x) = \begin{cases}1 & \text{jeśli $i\in I(x)$,}\\ 0 & \text{jeśli $i\not\in I(x)$.} \end{cases}$$ (32)

Metody pamięciowe

Metody pamięciowe reprezentują paradygmat ,,leniwego uczenia się'': uczenie się polega zasadniczo tylko na zapamiętaniu danych trenujących. Ich przetwarzanie odkładane jest do czasu, gdy zachodzi potrzeba odpowiedzi na zapytanie -- zastosowania hipotezy do nowego przykładu, i koncentruje się na przykładach trenujących podobnych do niego. W ten sposób można się uczyć zarówno aproksymacji, jak i klasyfikacji, jednak właśnie do aproksymacji podejście to jest stosowane częściej.

U podstaw koncepcji pamięciowych metod aproksymacji funkcji leży przeświadczenie, że przy współczesnym stanie techniki można i warto poświęcić dla dokładności aproksymacji i szybkości procesu uczenia się pamięciową i czasową efektywność obliczeniową. Może to wyglądać na kierowanie się technologiczną brutalną siłą, lecz o ocenie omawianych metod nie decyduje ich finezja, lecz skuteczność, a ta okazała się dość znaczna. Zobaczymy zresztą także, że nawet takie brutalne podejście pozostawia sporo miejsca na pomysłowe rozwiązania, wpływające na jakość aproksymacji i nakład obliczeń.

Pamięć i jej stosowanie

Aproksymatory pamięciowe wymagają przykładów trenujących etykietowane wartościami funkcji docelowej, gdyż tylko pod tym warunkiem będzie możliwe wykorzystanie ich do wyznaczenia odpowiedzi na zapytanie. Przyjmiemy, że wszystkie takie przykłady, jakie otrzymał aproksymator, składają się na zapamiętany przez niego zbiór trenujący $T$. Zawartością tak rozumianej pamięci są więc pary $\langle x,f(x)\rangle$ dla $x\in T$. Będziemy zakładać, że przykłady są opisywane przez $n$ cech, gdyż dodatkowa cecha $\phi_n$ o stałej wartości nie będzie w tym przypadku potrzebna.

Istotnym założeniem, na którym opierają się metody pamięciowe, jest dostępność metryki określonej na dziedzinie $X$, mierzącej odległość między dowolnymi dwoma przykładami. Jest to pewna funkcja $\delta:X\times X\mapsto\Re^+\cup\{0\}$, która nie musi w zasadzie spełniać żadnych szczególnych warunków (nawet standardowych aksjomatów odległości), a jedynie dobrze odzwierciedlać nasze rozumienie podobieństwa przykładów z dziedziny, w której jest przeprowadzana aproksymacja funkcji. Najczęściej jest stosowana standardowa metryka euklidesowa z opcjonalnym skalowaniem, zgodnie z którą odległość między przykładami $x_1,x_2\in X$ jest obliczana następująco:

$$\delta(x_1,x_2) = \sqrt{\sum_{i=0}^{n-1} \alpha_i^2\big(\phi_i(x_1)-\phi_i(x_2)\big)^2}$$ (33)

przy czym $\alpha_i$ dla $i=0,1,\dots,n-1$ są współczynnikami skalującymi, dzięki którym można regulować wpływ poszczególnych cech na odległość. Przy omawianiu grupowania były dyskutowane możliwości uogólnienia takiej odległości na atrybuty porządkowe i ciągłe, umożliwiłoby stosowanie aproksymatorów pamięciowych również dla dziedzin z takimi atrybutami.

Potrafiąc mierzyć stopień podobieństwa przykładów, mamy możliwość odpowiadania na zapytania na podstawie zawartości pamięci aproksymatora. Najczęściej bowiem dla zadanego w zapytaniu przykładu $x_*\in X$ wyznacza się wartość $h(x_*)$, mającą być przybliżeniem wartości funkcji docelowej $f(x_*)$, biorąc pod uwagę zapamiętane przykłady trenujące $\langle x,f(x)\rangle$ dla $x\in T$ i uzależniając ich wpływ na obliczenie $h(x_*)$ od odległości $\delta(x,x_*)$, zdefiniowanej w odpowiedni dla dziedziny sposób. Różne rodzaje aproksymatorów pamięciowych są wyróżniane przede wszystkim ze względu na stosowane do tego strategie, z których przejrzymy teraz najbardziej podstawowe.

Najbliższy sąsiad

Najprostszym i najbardziej znanym podejściem do aproksymacji funkcji na podstawie zapamiętywania jest metoda najbliższego sąsiada, często nazywana krótko NN (nearest neighbor). Jak nazwa sugeruje, w celu wyznaczenia odpowiedzi na zapytanie dotyczące przykładu $x_*$ bierze się pod uwagę najbliższy mu, według przyjętej metryki, przykład trenujący. Jeśli przykładem tym jest $\langle x,f(x)\rangle$ dla pewnego $x\in T$, to przyjmuje się $h(x_*)=f(x)$. Formalnie można to zapisać następująco:

$$h(x_*) = f\big(\mathrm{arg}\min_{x\in T}\delta(x,x_*)\big)$$ (34)

Zauważmy, że tak sformułowany algorytm aproksymacji nie wymaga przyjęcia żadnych założeń dotyczących dziedziny i reprezentacji przykładów poza tym, że jest dla nich określona pewna miara odległości. Zauważmy także, że algorytm najbliższego sąsiada, w przedstawionej podstawowej wersji, nie wymaga zakładania również niczego o przeciwdziedzinie aproksymowanego za jego pomocą odwzorowania docelowego $f$. Jeśli przeciwdziedziną tą jest zbiór liczb rzeczywistych $\Re$, to algorytm istotnie rozwiązuje zadanie uczenia się aproksymacji. Nic jednak nie stoi na przeszkodzie, aby funkcja $f$ była w rzeczywistości pojęciem, o przeciwdziedzinie będącej pewnym zbiorem kategorii $C$. Wówczas algorytm najbliższego sąsiada rozwiązuje zadanie uczenia się pojęć, gdyż służy do klasyfikowania przykładów na podstawie zapamiętanych danych trenujących.

Zaletą algorytmu NN jest jego prostota i uniwersalność. Uniwersalność umożliwia stosowanie go do zupełnie dowolnych dziedzin i określonych na nich odwzorowań. Można również powiedzieć, że charakteryzuje się on bardzo dużą (w istocie maksymalną) szybkością uczenia się, jeśli zgodzimy się rozumieć przez to, że do uzyskania $h(x)=f(x)$ dla pewnego przykładu $x\in X$ wystarczy jednokrotna prezentacja przykładu trenującego $\langle x,f(x)\rangle$. Dokładność uzyskiwanej aproksymacji zależy oczywiście od ilości dostępnych danych trenujących i jakości metryki, jaka jest wykorzystywana do znajdowania najbliższych sąsiadów.

Oczywistym mankamentem najprostszej wersji algorytmu NN jest łatwo zrozumiała tendencja do nadmiernego dopasowywania się do zaszumionych danych trenujących. Jeśli dla przykładu, którego dotyczy zapytanie, najbliższym sąsiadem będzie przykład o niepoprawnej wartości funkcji docelowej, to błąd odpowiedzi na to zapytanie może być arbitralnie duży. Inny problem to ,,schodkowość'' realizowanego przez aproksymator odwzorowania $h$, którego wartości zmieniają się nieciągle na dziedzinie wokół poszczególnych przykładów trenujących. Często stosowanym uogólnieniem algorytmu NN, który w pewnym stopniu neutralizuje te wady, jest algorytm $k$NN, używający $k$ najbliższych sąsiadów. Polega on na znalezieniu w zbiorze zapamiętanych przykładów $T$ ustalonej liczby $k\geq 1$ przykładów najbliższych przykładowi $x_*$, którego dotyczy zapytanie, i wyznaczeniu $h(x_*)$ na podstawie wartości funkcji docelowej dla tych $k$ przykładów. Standardowym podejściem jest obliczenie średniej arytmetycznej tych wartości. Jeśli więc przez $\mathrm{Arg}\min^k_{x\in T}\delta(x,x_*)$ oznaczymy zbiór $k$ przykładów ze zbioru $T$ najbliższych przykładowi $x$ według pewnej metryki $\delta$, to formalnie algorytm $k$NN możemy opisać następująco:

$$h(x_*) = \frac{1}{k} \sum_{x\in\mathrm{Arg}min^k_{x\in T}\delta(x,x_*)}f(x)$$ (35)

Podejście to można w tej postaci stosować tylko do aproksymowania funkcji o wartościach rzeczywistoliczbowych. Chcąc używać takiego uogólnienia algorytmu $k$NN do klasyfikowania przykładów, można zastąpić obliczanie średniej wyborem najliczniej reprezentowanej kategorii.

Lokalne średnie ważone

Inne podejście do pamięciowej aproksymacji funkcji prezentuje metoda lokalnych średnich ważonych, nazywana też regresją rdzeniową lub interpolacją Shepparda. Przezwycięża ona niektóre słabości algorytmu $k$NN kosztem większego nakładu obliczeń podczas wyznaczania odpowiedzi na zapytania i mniejszej szybkości uczenia się. Istotą omawianego podejścia jest obliczanie wartości aproksymowanej funkcji dla przykładu $x_*$ jako ważonej średniej wartości funkcji dla zapamiętanych przykładów trenujących. W ogólnym przypadku możemy zapisać:

$$h(x_*) = \frac{\sum_{x\in T}w_{xx*}f(x)}{\sum_{x\in T} w_{xx_*}}$$ (36)

przy czym $w_{xx_*}\in\Re$ oznacza wagę stosowaną dla wartości funkcji docelowej dla przykładu $x$ podczas wyznaczania odpowiedzi aproksymatora dla przykładu $x_*$. Oczywiście wagi z reguły zależą od odległości między przykładami, których dotyczą. Dla bliskich sobie według przyjętej metryki przykładów $x$ i $x_*$ waga $w_{xx_*}$ powinna być duża, tak aby wartość $f(x)$ miała duży wpływ na obliczenie $h(x_*)$. Dla każdego zapytania należy więc najpierw wyznaczyć odpowiedni wektor wag, o rozmiarze równym rozmiarowi pamięci aproksymatora, co niestety wpływa w istotny sposób na koszt obliczeniowy. Proces ten można jednak częściowo usprawnić, pomijając przykłady $x$, dla których $w_{xx_*}<w_{\mathrm{min}}$, przy czym ta ostatnia wartość oznacza pewien ustalony próg, jaki muszą przekroczyć wagi zapamiętanych przykładów, aby były one użyte do odpowiedzi na zapytanie. Wówczas do obliczenia $h(x_*)$ używane są tylko przechowywane w pamięci przykłady w obrębie pewnej stałej odległości od $x_*$. Odległość ta zależy od charakteru zależności $w_{xx_*}$ od $\delta(x,x_*)$.

Do wyznaczenia wagi $w_{xx_*}$ dla wartości $f(x)$ używanej do obliczenia $h(x_*)$ stosowane są pewne malejące funkcje zależne od $\delta(x,x_*)$, nazywane funkcjami wygładzającymi lub ważącymi, gdyż decydują one o wpływie wartości $f(x)$ dla różnych $x$ na wartość $h(x_*)$. Do najbardziej typowych wykorzystywanych w tym celu funkcji należy funkcja gaussowska, zgodnie z którą

$$w_{xx_*} = \exp\Big(-\frac{\delta(x,x_*)^2}{k^2}\Big)$$ (37)

lub tańsza do obliczenia i wolniej ,,opadająca'' hiperbola kwadratowa

$$w_{xx_*} = \frac{1}{1 + m(\delta(x,x_*)/k)^2}$$ (38)

przy czym typową wartością $m$ jest $20$. Przyjmuje się parametryzować funkcję wygładzania parametrem $k$, nazywanym szerokością rdzenia wygładzania, który określa odległość przykładu $x$ od przykładu $x_*$ (w sensie metryki $\delta$), przy której funkcja wygładzająca ma jeszcze znaczącą wartość. Niekiedy jawnie uwzględnia się w definicji funkcji wygładzającej minimalną odległość $\delta_{\mathrm{min}}$, przy której przyjmuje ona niezerowe wartości. Może być w szczególności stosowana następująca formuła obliczania wag:

$$w_{xx_*} = \begin{cases}1-\delta(x,x_*)^p & \text{jeśli $\delta(x... ...min}}$,}\\ 0 & \text{jeśli $\delta(x,x_*)>\delta_{\mathrm{min}}$,} \end{cases}$$ (39)

przy czym $p\geq 0$.

Niezależnie od konkretnej definicji funkcji wygładzającej metoda regresji rdzeniowej wymusza gładkość odwzorowania $h$. Oznacza to siłą rzeczy, że można za jej pomocą aproksymować węższą klasę funkcji niż za pomocą metody najbliższego sąsiada, chociaż umożliwia lepszą interpolację między rzadko rozrzuconymi przykładami trenującymi oraz niwelowanie szumu. W ten sposób zwiększa możliwość generalizacji i zmniejsza ryzyko nadmiernego dopasowania.

Lokalna regresja

Ostatnią grupą pamięciowych metod uczenia się aproksymacji funkcji, o jakiej tu wspomnimy, są metody lokalnej regresji. Nazwa sugeruje, że można je dobrze określić przeciwstawiając globalnej regresji. Globalna regresja to regresja o której była mowa dotychczas, polegająca na znajdowaniu wektora wag (jednego, wspólnego dla całego zbioru trenującego) zapewniającego możliwie maksymalną dokładność parametrycznej reprezentacji funkcji docelowej. Różnica między regresją globalną a regresją lokalną polega na tym, że ta ostatnia zamiast jednego, wspólnego dla całej dziedziny wektora wag (modelu globalnego), stara się dopasować do danych trenujących wiele różnych wektorów wag dla różnych fragmentów dziedziny (modeli lokalnych). Każdy z nich jest wyznaczany w trakcie przetwarzania zapytania na podstawie przykładów trenujących najbliższych przykładowi, którego to zapytanie dotyczy, uwzględnianych w stopniu określonym przez ich odległość od niego.

W najprostszym wariancie lokalna regresja polega na wybraniu ustalonej liczby $k$ najbliższych sąsiadów przykładu $x_*$, którego dotyczy zapytanie, i wyznaczenie wag (przy założonej konkretnej funkcji odwzorowania reprezentacji parametrycznej) tylko na podstawie tych przykładów. Ponieważ będzie ich niewiele (na ogół kilkanaście lub kilkadziesiąt), może być zastosowana podana wcześniej analityczna metoda wyznaczania wag w regresji liniowej. Następnie uzyskany wektor wag służy do wyznaczenia wartości hipotezy aproksymatora $h(x_*)$.

Metody symboliczne

Na podobnej w pewnym sensie do lokalnej regresji koncepcji opierają się metody aproksymacji symbolicznej. Jest to określenie nieco na wyrost, gdyż faktycznie popularność zdobyły jak dotąd tylko aproksymatory drzewiaste, łączące lokalną regresję z drzewami decyzyjnymi, ale można sobie bez trudu wyobrazić działające na podobnej zasadzie aproksymatory regułowe. Podstawowy pomysł jest taki, aby opisać w pewien sposób, charakterystyczny dla symbolicznej reprezentacji hipotez stosowanej do klasyfikacji, zestaw warunków dotyczących wartości cech (albo ogólnie atrybutów, gdyż można dopuścić tu ich różne typy), a następnie dla przykładów spełniających te warunki wyznaczać wektor wag metodą regresji (najczęściej, chociaż niekoniecznie) liniowej.

Hipotezy modelowania

Aby naszkicowaną koncepcję nieco bardziej skonkretyzować, weźmy pod uwagę pewien zbiór modeli $M=\{h_1,h_2,\dots,h_m\}$. Każdy model jest pewną hipotezą umożliwiającą obliczenie dla dowolnego przykładu $x\in X$ wartości mającej być przybliżeniem wartości funkcji docelowej dla tego przykładu. Nie oczekujemy od każdej z nich dokładnego przybliżania funkcji docelowej na całej dziedzinie, a jedynie na jej pewnym podzbiorze. Za wyznaczenie podziału dziedziny na podzbiory, którym są przypisane poszczególne modele, odpowiada hipoteza modelowania $h_M:X\mapsto M$. Każdemu przykładowi $x\in X$ przyporządkowuje ona pewien model $h\in M$, który może być użyty do wyznaczenia przybliżonej wartości funkcji docelowej dla tego przykładu. Wówczas wartość hipotezy reprezentowanej przez rozważany aproksymator może być dla dowolnego przykładu $x\in X$ zapisana jako $[h_M(x)](x)$, czyli wynik zastosowania do przykładu $x$ hipotezy, jaką przyporządkowuje mu hipoteza modelowania.

Zauważmy że w trywialnym przypadku każdy model ze zbioru $M$ może być reprezentowany przez pewną ustaloną liczbę. Wówczas hipoteza modelowania bezpośrednio przypisywałaby przykładom wartości funkcji docelowej, co oznaczałoby najbardziej naiwne zastosowanie algorytmów uczenia się pojęć do aproksymacji funkcji. W ogólnym przypadku modele, czyli hipotezy ze zbioru $M$, mogą być w zasadzie dowolnymi hipotezami do aproksymacji funkcji, lecz przyjmiemy, że są to hipotezy odpowiadające aproksymatorom parametrycznym, najczęściej liniowym, dla których wektor wag może być zazwyczaj wyznaczony -- ze względu na niewielką liczbę przykładów -- bezpośrednio analitycznie. Hipoteza modelowania może być z kolei dowolnie reprezentowaną hipotezą do uczenia się pojęć, która do tej samej ,,kategorii'' zalicza przykłady, co do których istnieje duża szansa, że można do nich dopasować jeden wspólny model, w tym przypadku liniowy, uzyskując dużą dokładność. Najprostsza konkretyzacja tego ogólnego sformułowania polegałaby na tym, aby do tego samego modelu były przypisywane przykłady o dostatecznie mało zróżnicowanych wartościach funkcji docelowej. Jako miarę zróżnicowania można wykorzystać standardowe odchylenie wartości funkcji docelowej.

Hipoteza modelowania nie musi być w zasadzie reprezentowana symbolicznie, lecz ten przypadek jest najciekawszy i tylko przy takiej reprezentacji sugerowane podejście do aproksymacji funkcji jest rzeczywiście atrakcyjne. Decyduje o tym duża szybkość uczenia się dla hipotez symbolicznych oraz ich czytelna postać, co w zastosowaniach do odkrywania wiedzy ma duże znaczenie. Aproksymatorami symbolicznymi będziemy więc nazywać aproksymatory wykorzystujące symbolicznie reprezentowane hipotezy modelowania. Uczenie się w aproksymatorze symbolicznym obejmuje dwa związane ze sobą procesy: uczenie się hipotezy modelowania, wyznaczającej podział dziedziny na obszary o zbliżonych wartościach funkcji docelowej, oraz uczenie się hipotez, przybliżających tę funkcję w każdym z tych obszarów.

Drzewa modelowania

Konkretną realizacją przedstawionej koncepcji są drzewa modelowania, w których do reprezentacji hipotezy modelowania służy drzewo decyzyjne. Algorytm ich konstruowania, bezpośrednio oparty na standardowym algorytmie zstępującego konstrukowania drzew decyzyjnych, jest znany pod nazwą M5'. Drzewem modelowania jest drzewo decyzyjne, którego węzły w zwykły sposób testują wartości atrybutów określonych na dziedzinie, za pomocą testów odpowiednich dla różnych typów, jakie mogą wystąpić, a liście określają model dla związanych z nimi przykładów. Aby miało to sens, drzewo nie powinno być pogłębiane aż do osiągnięcia jednoelementowych zbiorów przykładów -- przyjmiemy , że z każdym liściem jest związany pewien podzbiór zbioru trenującego, o którego rozmiarze oraz zróżnicowaniu wartości funkcji docelowej decyduje kryterium stopu przyjęte podczas konstruowania drzewa. Z kolei kryterium wyboru testu przy tworzeniu każdego nowego węzła drzewa powinno wskazać test, który najlepiej podzieli zbiór przykładów związanych z tym węzłem na podzbiory, charakteryzujące się możliwie niewielkim zróżnicowaniem wartości funkcji docelowej. Do budowy drzewa decyzyjnego może być użyty bez żadnych zmian standardowy schemat zstępującej konstrukcji drzewa, używający odpowiednio sformułowanych kryteriów stopu i wyboru testu.

Kryterium stopu

Kryterium stopu służy do podjęcia decyzji, kiedy zamiast kolejnego węzła drzewa należy utworzyć liść, zaprzestając w ten sposób dalszego podziału aktualnego zbioru przykładów na podzbiory. Skoro zależy nam na tym, aby przykłady w liściach miały możliwie mało zróżnicowane wartości funkcji docelowej, naturalne jest zatrzymywanie rekurencyjnego pogłębiania drzewa, kiedy warunek ten zostanie spełniony. Jeśli więc $P$ oznacza aktualny zbiór przykładów, to odpowiednie kryterium stopu można zapisać następująco:

$$\sigma_f(P) \leq \theta_{\sigma}$$ (40)

przy czym $\sigma_f(P)$ oznacza odchylenie standardowe wartości funkcji $f$ dla przykładów ze zbioru $P$, a parametr $\theta_{\sigma}$ określa maksymalny dopuszczalny poziom zróżnicowania wartości funkcji docelowej w liściach. Jako dodatkowy warunek w kryterium stopu można uwzględnić warunek dotyczący liczby przykładów w zbiorze $P$, przyjmując, że liść należy utworzyć zawsze, kiedy jest ich odpowiednio mało, nawet jeśli wartości funkcji docelowej są dla nich bardzo zróżnicowane.

Wybór testu

Wybór testu dla tworzonego węzła drzewa decyzyjnego ma na celu podział aktualnego zbioru przykładów na podzbiory charakteryzujące się możliwie małym zróżnicowaniem wartości funkcji docelowej. Potrzebujemy więc funkcji oceny testów formalizującej w pewien sposób takie kryterium preferencji. Weźmy pod uwagę pewien test $t:X\mapsto R_t$. Jego zastosowanie dzieli aktualny zbiór przykładów $P$ na podzbiory $P_{tr}$ odpowiadające różnym wynikom testu $r\in R_t$. W każdym z takich podzbiorów miarą zróżnicowania wartości funkcji docelowej $f$ jest wartość $\sigma_f(P_{tr})$. Za wartość funkcji oceny testu $t$ względem zbioru przykładów $P$ możemy przyjąć uśrednioną miarę zróżnicowania dla wszystkich wyznaczanych przez ten test podzbiorów, czyli

$$\sum_{r\in R_t}\frac{\vert P_{tr}\vert}{\vert P\vert}\sigma_f(P_{tr})$$ (41)

wybierając zawsze testy minimalizujące wartość tak określonej funkcji. Postępowanie takie jest równoważne z maksymalizacją funkcji oceny zdefiniowanej następująco:

$$\sigma_f(P) - \sum_{r\in R_t}\frac{\vert P_{tr}\vert}{\vert P\vert} \sigma_f(P_{tr})$$ (42)

która mierzy redukcję standardowego odchylenia wartości funkcji docelowej, wynikającą z zastosowania testu $t$. Taka funkcja ma dodatkową zaletę, polegającą na tym, że przyjmuje wartości dodatnie tylko dla testów dających poprawę (zmniejszających zróżnicowanie) oraz wartość 0 dla testów, których zastosowanie nie przynosi pożytku. Jeśli więc na pewnym etapie konstruowania drzewa okaże się, że wszystkie możliwe do zastosowania testy mają ocenę 0, to nie ma sensu jego dalsze pogłębianie. Dostarcza to dodatkowego warunku w kryterium stopu.

Przycinanie

Nawet przy bardzo starannie dobranym kryterium stopu trudno konstruując drzewa modelowania w opisany sposób uniknąć nadmiernego dopasowania i do uzyskania dobrych efektów jest na ogół niezbędne przycinanie. Przebiega ono tak jak dla zwykłych drzew decyzyjnych i polega na zastępowaniu niektórych węzłów drzewa liśćmi, jeśli nie doprowadzi to do pogorszenia szacowanego błędu rzeczywistego. Przycinanie musi poprzedzać wyznaczenie modeli dla poszczególnych liści, ale także dla węzłów, dla których będzie brane pod uwagę przycięcie. Tylko wtedy można ocenić błąd poddrzewa o korzeniu w takim węźle na podstawie modeli dla wszystkich jego liści oraz błąd liścia, jaki powstałby po jego przycięciu, na podstawie modelu dla tego węzła. Najłatwiej jest dokonać takiej oceny, kiedy dysponujemy zbiorem przycinania niezależnym od zbioru trenującego. Wystarczy wówczas porównać błąd próbki uzyskiwany dla całego poddrzewa oraz dla liścia, jaki miałby je zastąpić, gdyż błąd próbki jest najbardziej prawdopodobną wartością błędu rzeczywistego.

Zagadnienia praktyczne

Dobór rozmiaru kroku

Wartość rozmiaru kroku w aproksymatorach parametrycznych wpływa na ich szybkość uczenia się oraz na możliwą do uzyskania dokładność ich hipotez, a przy trybie inkrementacyjnym także na ich stabilność. Małe wartości parametru $\beta$ umożliwiają uzyskanie dużej dokładności, czyli najlepszego możliwego dopasowania wag do przykładów trenujących, a przy inkrementacyjnym uczeniu się dużej stabilności, czyli niewielkich wahań wartości hipotezy po każdorazowej modyfikacji wag. Zmienianie wag w małych krokach powoduje jednak, że wymagana może być duża liczba takich kroków, co oznacza małą szybkość uczenia się. W związku z tym odpowiedni dobór tego parametru jest zawsze pewnym kompromisem między szybkością a dokładnością oraz stabilnością i na ogół musi być dokonany eksperymentalnie, przez wypróbowanie wartości z pewnego zakresu, na ogół od $0.01$ do $0.5$. Różne wartości mogą okazać się najlepsze dla różnych aproksymatorów, dziedzin i funkcji docelowych, trudno więc podać jakiekolwiek uniwersalne wskazówki.

Często lepsze efekty można osiągnąć, stosując zmienne wartości rozmiaru kroku, zależne na przykład od etapu, na którym znajduje się proces uczenia się. Najprostsza zdroworozsądkowa strategia polegałaby na rozpoczęciu od stosunkowo dużej wartości $\beta$ i redukowaniu jej po każdym cyklu. Proponowane były również bardziej wyrafinowane strategie adaptacji rozmiaru krokui, umożliwiające jego zmniejszanie i zwiększanie na podstawie obserwacji gradientu i wartości funkcji błędu.

Dyskretne i mieszane przestrzenie atrybutów

Większość przedstawionych w tym rozdziale aproksymatorów jest przeznaczona do stosowania w dziedzinach opisywanych za pomocą atrybutów ciągłych, co jest zgodne z potrzebami występującymi najczęściej w praktycznych zastosowaniach. Modyfikacje umożliwiające stosowanie także dla dyskretnych lub mieszanych przestrzeni atrybutów są najprostsze dla metod pamięciowych. W ich przypadku wystarczy odpowiednio dobrać metrykę, za pomocą której mierzy się odległość między przykładami. W najprostszym przypadku można posłużyć się w tym celu uogólnioną metryką euklidesową:

$$\delta(x_1,x_2) = \sqrt{\sum_{i=0}^{n-1}\alpha_i^2\delta_i(x_1,x_2)^2}$$ (43)

przy czym dla atrybutów ciągłych oczywiście $\delta_i(x_1,x_2)=\vert a_i(x_1)-a_i(x_2)\vert$. Dla atrybutów porządkowych należy w oczywisty sposób uogólnić rozumienie różnicy wartości, traktując ją jako zwiększoną o $1$ liczbę wartości pośrednich między $a_i(x_1)$ i $a_i(x_2)$ należących do zbioru $A_i$, a dla atrybutów nominalnych można przyjąć

$$\delta_i(x_1,x_2) = \begin{cases}1 & \text{jeśli $a_i(x_1)=a_i(x_2)$,}\\ 0 & \text{jeśli $a_i(x_1)\neq a_i(x_2)$.} \end{cases}$$ (44)

W metodach opartych na rozszerzonej reprezentacji muszą być określone transformacje rozszerzające przestrzeń atrybutów z uwzględnieniem ich typów, co może być kłopotliwe. Stosowane rozwiązania są najczęściej projektowane ad hoc do konkretnych zastosowań i nie ma dobrego rozwiązania uniwersalnego, np. dyskretnego odpowiednika aproksymatora CMAC. Użycie podstawowych metod parametrycznych z atrybutami dyskretnymi jest możliwe przez zastąpienie ich liczbowymi cechami. W przypadku atrybutów porządkowych można po prostu zastąpić ich wartości kolejnymi liczbami całkowitymi, w kolejności zgodnej z ustaloną dla nich relacją porządku. W przypadku atrybutów nominalnych wprowadzanie w ten sposób sztucznej, nie mającej żadnej rozsądnej interpretacji relacji porządku mogłoby być niewłaściwe, najczęściej więc każdy atrybyt nominalny $a:X\mapsto A$ zastępuje się cechami $\phi_{av}$ dla wszystkich wartości $v\in A$, określonymi dla dowolnego przykładu $x\in X$ następująco:

$$\phi_{av}(x) = \begin{cases}1 & \text{jeśli $a(x)=v$,}\\ 0 & \text{jeśli $a(x)\neq v$.} \end{cases}$$ (45)

Podejście to może także być zastosowane dla atrybutów porządkowych, wtedy jednak prowadzi do pomijania określonych dla ich wartości relacji porządku.

Ograniczona pamięć w metodach pamięciowych

Niezależnie od sposobu organizacji pamięci w aproksymatorach pamięciowych, o którym będzie jeszcze mowa dalej, jej rozmiar musi być ograniczony. Przy stosowaniu aproksymatora w trybie inkrementacyjnym, kiedy liczba przykładów trenujących może okazać się dowolnie duża, należy liczyć się z całkowitym zapełnieniem pamięci. Pomijanie wówczas dalszych przykładów najczęściej jest niedopuszczalne, choćby dlatego, że inkrementacyjny tryb uczenia się jest często stosowany dla niestacjonarnych, zmiennych w czasie funkcji docelowych, wskutek czego nowe przykłady zawsze muszą być uwzględniane. Nie pozostaje wówczas nic innego, jak usunąć z pamięci niektóre ze starych przykładów i w ten sposób zrobić miejsce dla nowych. Pozostaje określić strategię wybierania przykładów do usunięcia.

Można wskazać trzy zasadnicze strategie usuwania, których wykorzystanie wydaje się rozsądne. Pierwsza i najprostsza to strategia losowa, zgodnie z którą w razie potrzeby z pamięci usuwa się równomiernie losowo wybrany przykład. Chociaż może to wyglądać na podejście bardzo prymitywne, nie powinno być lekceważone. Po pierwsze, nie wymaga ono żadnych dodatkowych obliczeń ani przechowywania dodatkowych danych. Po drugie, przez losowy wybór unika ono, być może, szkodliwego obciążenia, jakie mogłoby się wiązać z usuwaniem przykładów według ustalonej strategii deterministycznej. Taka strategia deterministyczna może w najprostszym przypadku polegać na usuwaniu z pamięci ,,najstarszego'' przykładu, czyli najdawniej w niej umieszczonego. Podejście to jest szczególnie uzasadnione przy uczeniu się niestacjonarnych funkcji docelowych, kiedy stopniowo stare przykłady są wypierane przez nowe, zawierające bardziej aktualne wartości funkcji. Aby jednak stosowanie go nie wprowadzało wspomnianego szkodliwego obciążenia, kolejne przykłady dostarczane uczniowi powinny być niezależnie losowane z dziedziny. Jeśli między kolejnymi przykładami występują pewne zależności, co często się zdarza w zastosowaniach, kiedy stanowią one kolejne obserwacje dotyczące pewnego procesu, usuwanie najstarszych przykładów może być niebezpieczne. Lepszą strategią powinno być wtedy usuwanie przykładów najrzadziej używanych do wyznaczenia wartości hipotezy aproksymatora dla przykładów, których dotyczą kierowane do niego zapytania. Dla każdego przechowywanego przykładu należałoby zatem utrzymywać także statystykę, określającą względną częstość jego wykorzystywania do odpowiadania na zapytania, czyli stosunek liczby zapytań, przy jakich był użyty, do ogólnej liczby zapytań zadanych aproksymatorowi od czasu, kiedy został on wprowadzony do pamięci.

Wygładzanie w drzewach modelowania

W praktyce czasem oczekujemy od aprksymatorów funkcji, aby ich hipoteza była stosunkowo ,,gładka'' -- zmieniała wartości w niewielkim stopniu przy małych zmianach wartości cech. W drzewie modelowania, jeśli zmiana wartości cechy spowoduje dotarcie do innego liścia, może nastąpić duża skokowa zmiana wartości hipotezy. Będzie tak zwłaszcza dla drzew budowanych na podstawie niewielu przykładów. Aby tego uniknąć, stosuje się proces wygładzania. Realizuje się go przez tworzenie modeli regresyjnych nie tylko dla liści drzewa, lecz także dla każdego węzła wewnętrznego. Następnie po wyznaczeniu dla przykładu liścia i wartości związanego z nim modelu, następuje cofanie się po ścieżce od liścia do korzenia i wyznaczanie wartości modeli z odwiedzanych po drodze węzłów, które służą do modyfikacji wartości otrzymanej w liściu. W każdym węźle zmodyfikowaną wartość wyznacza się jako średnią ważoną wartości otrzymanej ,,z dołu'' (od potomka) i wartości otrzymanej z modelu w tym węźle, przy czym ważenie jest proporcjonalne do liczby przykładów trenujących związanych z każdym z węzłów. Tak obliczona wartość jest propagowana ,,w górę'' do kolejnego węzła, aż do osiągnięcia korzenia, w którym uzyskuje się ostateczną wartość hipotezy aproksymatora.

Wagi w rozproszonych przybliżonych tablicach

Do istoty rozproszonego przybliżonego kodowania należy duży rozmiar rozszerzonej przestrzeni cech, której tylko niewielka część jest aktywna dla każdego przykładu. Mimo więc, że do obliczania i aktualizacji hipotezy każdorazowo używa się niewielkiej liczby wag, często zaledwie kilku lub kilkunastu, łączna liczba wag jest zazwyczaj bardzo duża -- czasem zbyt duża w stosunku do możliwości pamięciowych.

Prosta i uniwersalna technika, jaka może złagodzić problem dużego rozmiaru wektora wag, to kodowanie mieszające, polegające w tym przypadku na odwzorowaniu obliczanych w zwykły sposób logicznych numerów wag z zakresu od 0 do $n'-1$ na ich fizyczne numery, będące liczbami z zakresu od 0 do $n''-1$ dla $n''\ll n'$. Przy takim podejściu jeden numer fizyczny odpowiada pewnej liczbie numerów logicznych, przeciętnie $\frac{n'}{n''}$. Jest to na ogół możliwe bez istotnego pogorszenia dokładności aproksymacji dzięki temu, że zazwyczaj istnieje wiele rozszerzonych cech, które są stosunkowo rzadko aktywne dla dostarczanych aproksymatorowi przykładów i w związku z tym odpowiadające im wagi nie są w zasadzie używane. Dzięki temu jedna fizycznie przechowywana waga może odpowiadać pewnej liczbie różnych cech rozszerzonych. W praktyce zupełnie dobre efekty dają wartości $n''$ równe od $0.1n'$ nawet do $0.01n'$, co oznacza redukcję rozmiaru wektora wag od $10$ do $100$ razy. Odwzorowania numeru logicznego wagi $i\in\{0,1,\dots,n'-1\}$ na numer fizyczny $j\in \{0,1,\dots,n''-1\}$ powinno charakteryzować się możliwie dużą równomiernością, czyli przypisywać każdemu numerowi fizycznemu taką samą liczbę numerów logicznych. Na ogół przyjmuje się po prostu

$$j = i\bmod n''$$ (46)

przy czym $\bmod$ oznacza operator dzielenia modulo, zapewniając przy tym, że $n'$ jest całkowitą wielokrotnością $n''$.

Zapamiętywanie przykładów

We wszystkich przedstawionych metodach pamięciowych występuje wspólny problem znalezienia wśród przechowywanych w pamięci przykładów trenujących takich par $\langle x,f(x)\rangle$, dla których przykład $x$ jest dostatecznie bliski według przyjętej metryki przykładowi $x_*$, będącemu przedmiotem zapytania. Naiwna implementacja poszukiwania najbliższych sąsiadów wymaga obliczenia odległości $\delta(x,x_*)$ dla każdego zapamiętanego przykładu $x\in T$. Jeśli przykłady są reprezentowane za pomocą $n$ cech, to koszt tych obliczeń wynosi $O(n\vert T\vert)$. Tymczasem rozmiar zbioru zapamiętywanych przykładów $T$ jest w metodach pamięciowych na ogół liczony co najmniej w tysiącach, a często liczba przykładów przechowywanych w pamięci nieustannie się zwiększa, co może uczynić koszt takiego bezpośredniego podejścia do znajdowania najbliższych sąsiadów nieakceptowalnym.

Znacznie efektywniejszą implementację można uzyskać, wykorzystując specjalne struktury danych nazywane $k$-d drzewami, czyli drzewami $k$-wymiarowymi. Struktura nazywana $k$-d drzewem jest szczególnego rodzaju drzewem binarnym, zbudowanym z węzłów, z których każdy ma dwa węzły potomne i reprezentuje podział pewnego regionu $k$-wymiarowej hiperprzestrzeni na dwa mniejsze regiony. Ściślej rzecz biorąc, regiony te są hiperprostopadłościanami o ścianach równoległych do hiperpłaszczyzn układu współrzędnych. Każdy węzeł odpowiada pewnemu hiperprostopadłościanowi, a jego dwa węzły potomne odpowiadają dwóm mniejszym hiperprostopadłościanom, na które macierzysty hiperprostopadłościan jest dzielony. Podział ten jest wyznaczany wzdłuż jednego z $k$ wymiarów przez określoną wartość progową współrzędnej (w naszym przypadku cechy) odpowiadającej temu wymiarowi. W każdym węźle jest przechowywany numer wymiaru, wzdłuż którego dokonuje on podziału, oraz odpowiednia wartość progowa. Liście $k$-d drzewa odpowiadają dostatecznie małym regionom i w każdym z nich przechowuje się zbiór punktów $k$-wymiarowej przestrzeni, należących do odpowiedniego regionu. Umożliwia to efektywny dostęp do punktów należących do określonego regionu.

Literatura

1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdziały 8.1, 8.3, 8.4, 8.5, 8.6, 8.7, 8.8).
2. Witten, I. A., Frank, E. Data Mining. Morgan Kaufmann, 2000. (Podrozdziały 3.7, 4.6, 4.7, 6.5).

About this document ...

Metody odkrywania wiedzy: wykład 13
Aproksymacja funkcji

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

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