Metody odkrywania wiedzy: wykład 14
Odkrywanie równań

Paweł Cichosz


Date: 2001/2002

Wykład jest poświęcony metodom odkrywania zależności między atrybutami ciągłymi przy założeniu, że czytelność ich symbolicznego zapisu w postaci wyrażeń arytmetycznych jest ważniejsza niż dokładność. Omawiany jest zestaw heurystycznych metod odkrywania równań dla dwóch oraz większej liczby atrybutów.

Problem odkrywania równań

Dla atrybutów o wartościach ciągłych można podjąć próbę opisania funkcyjnej zależności między nimi, jeśli taka występuje, za pomocą równania. Tego typu zależność, o ile uda się ją znaleźć, jest na ogół bardzo interesująca i przydatna. Wiąże się to z faktem, że równania o odpowiednio dużym zakresie obowiązywania (czyli zachodzące dla wielu przykładów) i stosunkowo dużej dokładności mają dość dobrą wartość predykcyjną i są łatwe do interpretacji. O ile pierwsza z tych dwóch właściwości, czyli możliwość przewidywania wartości pewnego atrybutu ciągłego na podstawie wartości innych atrybutów, może być osiągnięta łatwiej i w większym stopniu przez stosowanie metod aproksymacji funkcji, o tyle nie mogą one na ogół zapewnić drugiej z nich. Jeśli właśnie łatwość interpretacji ma priorytet, warto sięgnąć po metody odkrywania równań. Oczywiście nie jest jednak tak, że odkrywanie równań może zastąpić aproksymację funkcji. Wiele zależności ma charakter zbyt złożony, aby dały się zapisać symbolicznie w postaci czytelnych dla człowieka równań bez poświęcania przy tym dokładności w zbyt dużym stopniu. Próbę taką warto jednak podjąć, gdyż niektóre wielkości, zwłaszcza pochodzące z pomiarów i obserwacji empirycznych, jeśli rzeczywiście wiąże je bezpośrednia zależność, podlegają prawidłowościom, dla których równanie jest najlepszym opisem. Czasem zadowalamy się przy tym równaniami zachodzącymi tylko dla fragmentów dziedziny, szukając różnych równań dla różnych jej obszarów. Ze względu na, dość powierzchowną, zbieżność odkrywania równań z niektórymi aspektami działalności badawczej w obszarze nauk przyrodniczych, czasem ten rodzaj odkryć nazywa się odkryciami naukowymi.

Terminologia i notacja dla równań

Dla wygody i zgodnie z powszechnie przyjętym zwyczajem na czas omawiania metod odkrywania równań odejdziemy od naszej zwykłej terminologii i notacji. Atrybuty ciągłe, dla których będzie poszukiwana zależność, nazwiemy zmiennymi, oznaczając je literami $ x$, $ y$, $ z$ itp. Założymy, że analizowany zbiór przykładów zawiera pewną liczbę wartości wszystkich rozważanych zmiennych, które będziemy oznaczać dodając do odpowiedniej zmiennej dolny indeks oznaczający kolejny numer wartości, czyli numer przykładu trenującego. Zatem dla dwóch zmiennych $ x$ i $ y$ zawiera on pary $ \langle x_i,y_i\rangle$ dla $ i=1,2,\dots$, przy czym zazwyczaj nie będziemy wprowadzać specjalnego oznaczenia dla ich liczby, choć oczywiście musi ona być skończona. Odpowiednio dla trzech zmiennych $ x$, $ y$, $ z$ przykładami trenującymi będą trójki $ \langle x_i,y_i,z_i\rangle$ dla $ i=1,2,\dots$. Dla zbioru zmiennych $ V$ zbiór trenujący zawierający $ \vert V\vert$-elementowe krotki wartości zmiennych z tego zbioru będziemy oznaczać przez $ T^V$, zakładając pewien ustalony porządek dla tych zmiennych, tak aby przyporządkowanie poszczególnych wartości odpowiednim zmiennym było jednoznaczne.

Przyjmiemy, że zawsze jedna ustalona zmienna jest zmienną zależną, a pozostałe zmienne są zmiennymi niezależnymi. Poszukiwane jest wówczas równanie opisujące zależność zmiennej zależnej, którą zgodnie ze zwyczajem będziemy oznaczać przez $ y$, od zmiennych niezależnych. Wybór zmiennej zależnej ma przy tym znaczenie podobne jak wybór atrybutu reprezentującego kategorie przy stosowaniu algorytmów uczenia się pojęć do odkrywania zależności. Jest on na ogół względny i wynika z zainteresowań eksperymentatora. Można wielokrotnie poszukiwać równań dla tego samego zbioru zmiennych, przyjmując za każdym razem inną z nich za zależną. Jeśli zmienna zależna $ y$ jest jawnie wyodrębniona, to zbiór trenujący będziemy oznaczać przez $ T^{y,V_x}$, przy czym $ V_x$ jest zbiorem zmiennych niezależnych, a w przypadku szczególnym, gdy $ V_x=\{x\}$, po prostu przez $ T^{y,x}$. Założymy przy tym, że w krotkach wchodzących w skład zbiorów trenujących wartości zmiennej zależnej znajdują się na ostatniej pozycji, czyli

$\displaystyle T^{y,x} = \{\langle x_i,y_i\rangle \;\vert\; i=1,2,\dots\}$. (1)

Równania z dwiema zmiennymi

Najprostszy rodzaj równań to funkcyjna zależność dwóch zmiennych. Mając zbiór pochodzących z obserwacji (pomiarów) przykładów trenujących w postaci par wartości $ \langle x_i,y_i\rangle$ dla $ i=1,2,\dots$, chcemy znaleźć funkcję $ f$, o możliwie prostym symbolicznym zapisie, taką że równanie $ y=f(x)$ opisuje te dane maksymalnie dokładnie. Zauważmy, że niektóre z omawianych metod aproksymacji funkcji mogłyby być tu wykorzystane pod warunkiem założenia szczególnych postaci tej funkcji. Ograniczając się do funkcji liniowych, można do znalezienia określających je parametrów (wag) wykorzystać parametryczne metody aproksymacji, a dokładniej aproksymator liniowy (liniową regresję). Nas interesuje jednak możliwość odkrywania zależności o w miarę dowolnym charakterze, a więc bez założeń silnie ograniczających ich postać, a przy tym możliwych do symbolicznego zapisania w czytelnej postaci.

Wykrywanie trendów i stałych

Jedną z najprostszych heurystyk jest wykrywanie trendów i stałych. Jest to właściwie zestaw czterech heurystycznych reguł, które w bardzo nieformalny sposób można zapisać następująco:

  1. jeśli zmienna $ y$ ma wartość $ v$ dla odpowiednio dużej liczby przykładów, to przyjmij, że $ y$ ma stałą wartość $ v$,
  2. jeśli zmienne $ x$ i $ y$ są liniowo zależne z pochyleniem $ a$ i przesunięciem $ b$, czyli $ y=ax+b$ dla odpowiednio dużej liczby przykładów, to przyjmij, że ten związek zachodzi zawsze,
  3. jeśli $ y$ zmniejsza się przy zwiększaniu się $ x$ oraz $ x$ i $ y$ nie są zależne liniowo, to utwórz nową zmienną $ t=xy$,
  4. jeśli $ y$ zwiększa się przy zwiększaniu $ x$ oraz $ x$ i $ y$ nie są zależne liniowo, to utwórz nową zmienną $ t=x/y$.
Pierwsze dwie z powyższych reguł służą do wykrywania stałych wartości zmiennych oraz zależności liniowych. Obie z nich bezpośrednio prowadzą do sformułowania równania wiążącego zmienne $ y$ i $ x$. Jak długo jednak żadnej z nich nie można zastosować, tak długo są tworzone za pomocą pozostałych dwóch reguł nowe zmienne, do których ponawia się rekurencyjnie próbę zastosowania którejś z reguł. Należy więc rozumieć, że w regułach tych rolę zmiennych $ x$ i $ y$ mogą odgrywać w kolejnych cyklach ich stosowania dowolne z wprowadzonych dotychczas zmiennych. Dwie ostatnie reguły w podanej postaci stosują się tylko do zmiennych o jednakowych znakach, modyfikacja dla przypadku zmiennych o przeciwnych znakach jest jednak oczywista.

Przedstawione reguły są niezwykle proste. Chociaż umożliwiają odkrycie w efektywny sposób pewnych nietrywialnych równań, w szczególności niektórych klasycznych praw nauk empirycznych i w wielu przypadkach ich stosowanie zakończy się niepowodzeniem. Nie będzie on w stanie, w szczególności, odkryć związków wielomianowych stopnia $ 2$ lub wyższych, w tym tak prostego związku jak $ y=ax^2+b$, w których występują nie iloczyny dwóch zmiennych, lecz potęgi jednej zmiennej. Zawiedzie on też zawsze, jeśli zależność $ x$ i $ y$ nie jest monotoniczna, czyli przy wzroście wartości $ x$ wartości $ y$ zarówno rosną dla części zbioru $ P$, jak i maleją dla jego innych fragmentów. W podstawowej postaci metoda wykrywania trendów i stałych nie przewiduje również mechanizmów działania przy częściowo niepoprawnych danych, kiedy wartości zmiennych w niektórych lub wszystkich przykładach są obarczone pewnym błędem. Aby taką możliwość uwzględnić, należy przy wykrywaniu wartości stałych i zależności liniowych dopuścić odpowiednio wartości w przybliżeniu stałe (o dostatecznie małym odchyleniu standardowym) i zależności w przybliżeniu liniowe (o współczynniku korelacji dostatecznie bliskim $ 1$ lub $ -1$).

Wykrywanie stałych pochodnych

Bardziej zaawansowaną heurystyką odkrywania prostych równań jest wykrywanie stałych pochodnych. Technika ta umożliwia znajdowanie dowolnych wielomianowych zależności między parą zmiennych, przeszukując w pewien systematyczny sposób przestrzeń funkcji wielomianowych. Przeszukiwanie to rozpoczyna się od rozważenia możliwych składników wielomianu o najwyższym stopniu, przez kolejne sprawdzanie składników o stopniach niższych aż do kwadratowych, liniowych i stałych. Pomysł na znalezienie tych składników, czyli określenie potęgi zmiennej $ x$ i odpowiadającego jej współczynnika wielomianu, polega na badaniu pochodnych zależności $ y$ od $ x$. Metodą różnicową obliczane są wartości kolejnych pochodnych dla poszczególnych przykładów (zerowego, pierwszego, drugiego rzędu itd.), aż do uzyskania pochodnej o stałej wartości dla wszystkich przykładów. Rząd tej stałej pochodnej i jej wartość dają informację odpowiednio o stopniu i współczynniku najwyższego stopniem wyrazu wielomianu. Następnie to samo podejście jest stosowane do znalezienia składników o kolejnych niższych stopniach. Dokładny sposób postępowania najlepiej wyjaśnia poniższy rekurencyjny algorytm.


\begin{algorithmic}[1] \FUNCTION $\textit{stałe-pochodne}(y,x,P)$\INPUTARGS\mbox... ...v)$; \RET $wx^n+\textit{stałe-pochodne}(v,x,P^{v,x})$. \ENDIF \end{algorithmic}

Funkcja stałe-pochodne otrzymuje jako parametry zmienną zależną $ y$, zmienną niezależną $ x$ i zbiór przykładów $ P$. Zbiór ten przy pierwszym wywołaniu jest zbiorem trenującym $ T^{y,x}$, zawierającym pary wartości $ \langle x_i,y_i\rangle$ dla $ i=1,2,\dots$. Funkcja zwraca wyrażenie opisujące zależność zmiennej $ y$ od zmiennej $ x$ występującą w zbiorze $ P$. Jeśli więc jako wynik otrzymamy pewne wyrażenie $ f(x)$, to odpowiednie równanie ma postać $ y=f(x)$. Równania nie są zwracane bezpośrednio ze względu na wygodę zapisu wywołań rekurencyjnych.

Podstawowe znaczenie dla działania algorytmu ma obliczanie na podstawie przykładów zawartych w $ P$ wartości pochodnych zmiennej zależnej rzędu $ n$, $ y^{(n)}_i$ dla $ i=1,2,\dots$ oraz kolejnych wartości $ n$, rozpoczynając od 0. Ściślej mówiąc, w przedstawionej postaci algorytm zamiast wartości pochodnej rzędu $ n$ oblicza jej wartość podzieloną przez $ n!$, o czym dość łatwo się przekonać. Obliczenia są przeprowadzane dla rosnących wartości $ n$ dopóty, dopóki wartości $ y^{(n)}$ nie staną się stałe dla danych ze zbioru $ P$. W przypadku idealnym oznacza to jednakowe wartości $ y^{(n)}_i$ dla wszystkich $ i$, dla których para $ \langle x_i,y_i\rangle$ znajduje się w $ P$, chociaż w praktyce możemy dopuścić wartości w przybliżeniu stałe. Przyjmujemy, że wówczas wywołanie funkcji $ \textit{stała}(y^{(n)},P)$ daje w wyniku taką stałą lub ,,prawie stałą'' wartość $ y^{(n)}$ w zbiorze $ P$, co w tym drugim przypadku może oznaczać faktycznie wartość średnią, która jest zachowywana jako $ w$. Wówczas, jeśli $ n>0$ (w przeciwnym przypadku $ y$ jest określona funkcją stałą $ y=w$), to jest tworzona nowa zmienna zależna określona jako $ v=y-wx^n$ i ten sam algorytm jest stosowany rekurencyjnie do odkrycia równania opisującego zależność zmiennej $ v$ od zmiennej $ x$. Jest to poprzedzone uzupełnieniem przykładów ze zbioru $ P$ o wartości zmiennej $ v$, czyli do każdego przykładu o numerze $ i$ jest dodawana obliczona w podany sposób wartość $ v_i$. Utworzenie zmiennej o podanej definicji oraz rozszerzenie zbioru przykładów realizują odpowiednio funkcje $ \textit{zmienna}$ i $ \textit{rozszerzenie}$. Zbiór przykładów przekazywany do wywołania rekurencyjnego powstaje przez wybranie z rozszerzonego w ten sposób zbioru $ P$ wartości zmiennych $ v$ i $ x$, co zapisujemy jako $ P^{v,x}$. Jeśli następnie wywołanie rekurencyjne doprowadzi do znalezienia pewnej zależności $ v=F(x)$, to oczywiście wyrażenie opisujące zależność $ y$ od $ x$ uzyskamy ponownie dodając składnik $ wx^n$, czyli $ y=wx^n+F(x)$.

Prosta modyfikacja opisanej metody umożliwia znaczne rozszerzenie klasy funkcji branych pod uwagę przez system dokonujący odkryć. Oprócz analizowania możliwych wielomianowych związków między $ x$ i $ y$, można więc poszukiwać takich związków między $ x$ i $ y^2$, $ x$ i $ y^3$ itd., a także np. $ x$ i $ \log y$ lub $ x$ i $ \sin y$. Można więc nie ograniczać się do poszukiwania zależności wielomianowych $ y$ od $ x$, lecz wziąć pod uwagę bardziej ogólną sytuację poszukiwania zależności wielomianowych pewnej nowej zmiennej, zależnej bezpośrednio tylko od $ y$, i pewnej nowej zmiennej, zależnej bezpośrednio tylko od $ x$. Jest to podejście analogiczne do rozszerzania reprezentacji przy aproksymacji funkcji. Przedstawiona technika może zostać też w sugerowany już wyżej sposób zmodyfikowana w celu dopuszczenia danych obarczonych błędami przez rozluźnienie wymagania, aby pochodne były stałe, czyli zastąpienie go wymaganiem, aby były one ,,prawie stałe'' -- z dokładnością określoną przez pewne parametry algorytmu.

Konkretyzacja wzorców

W przedstawionych dotychczas podejściach system dokonujący odkryć stara się określić wyrażenia opisujące związki między obserwowanymi zmiennymi wyłącznie na podstawie dostępnych danych, do których jest dobierana postać równania. Mankamentem takiego podejścia jest dość mała odporność na niepoprawność tych danych, która może bądź uniemożliwić w ogóle odkrycie równania, bądź doprowadzić do jego nadmiernie skomplikowanej postaci. Alternatywne podejście może polegać na dostarczeniu automatycznemu odkrywcy wzorców równań, które należy wziąć pod uwagę. Wzorzec to nic innego niż równanie parametryzowane, które przekształca się w równanie konkretne po określeniu wartości wszystkich parametrów. Przy danym zestawie wzorców odkrywanie równań polega więc na dopasowywaniu ich do danych przez poszukiwanie odpowiednich wartości parametrów i ostatecznym wybraniu jednego równania o najlepszym dopasowaniu.

Jedną z najprostszych strategii dobierania parametrów wzorców jest zachłanne przeszukiwanie ich przestrzeni, którego pewną wersję przedstawimy tu dokładniej. Zgodnie z nią proces przeszukiwania rozpoczyna się od zbioru równań początkowych, uzyskanych w wyniku skonkretyzowania wszystkich wzorców przez przypisanie ich parametrom różnych kombinacji wartości $ -1$, 0 i $ 1$. Następnie powtarza się iteracyjnie podstawowy cykl generowania nowych równań przez modyfikację parametrów i pominięcie najgorszych z nich. Jest to przykład zastosowania przeszukiwania wiązkowego, w którym w każdej fazie bierze się pod uwagę pewną ograniczoną liczbę najlepszych kandydatów. Szczegóły tego podejścia przedstawia poniższy algorytm.


\begin{algorithmic}[1] \FUNCTION $\textit{konkretyzuj-wzorce}(y,x,T^{y,x},S)$\IN... ...\mathrm{arg}\max_{e\in E} \vartheta^y_e(T^{y,x}),y,T^{y,x})$. \end{algorithmic}

Funkcja $ \textit{konkretyzuj-wzorce}$ otrzymuje oprócz zwykłych argumentów, z jakimi mieliśmy dotychczas do czynienia, dodatkowy argument $ S$, będący zbiorem wzorców, czyli parametryzowanych wyrażeń zależnych od zmiennej niezależnej $ x$. Wyrażenie zwracane przez tę funkcję po zakończeniu jej działania jest zawsze konkretyzacją pewnego wzorca z tego zbioru. Na ich podstawie generuje się i modyfikuje w kolejnych iteracjach zbiór konkretnych wyrażeń $ E$, których jakość oceniana jest na podstawie zbioru danych $ T^{y,x}$. W ogólnym przypadku wartość funkcji oceny dla wyrażenia $ e$ na podstawie zbioru przykładów $ P$, oznaczana przez $ \vartheta^y_e(P)$, ma na celu określenie jego przydatności do opisu występującej w zbiorze $ P$ zależności zmiennej $ y$ od zmiennej $ x$. Można ją zdefiniować jako wartość bezwzględną współczynnika korelacji wartości zmiennej $ y$ faktycznie występujących w zbiorze $ P$ oraz obliczonych dla odpowiednich wartości zmiennej $ x$ wartości wyrażenia $ e$.

Początkowy zbiór wyrażeń $ E$ powstaje na podstawie zbioru wzorców $ S$ przez ich konkretyzację, polegającą na podstawieniu za występujące w nich parametry wszystkich kombinacji wartości $ -1,0,1$. Dla wzorca $ k$-elementowego może w ten sposób powstać $ 3^k$ konkretyzujących go wyrażeń. Niektóre z nich mogą następnie z pewnych względów zostać odrzucone jako trywialne (np. o stałych wartościach niezależnych od wartości zmiennej $ x$) lub źle określone matematycznie (np. zawierające dzielenie przez 0 czy stosujące pewną funkcję elementarną do argumentu spoza jej dziedziny). Mogą być także pominięte wyrażenia zależne liniowo od innego wyrażenia. Za przeprowadzenie konkretyzacji wzorców w opisany odpowiada wywołanie funkcji $ \textit{generuj0}$.

W kolejnych iteracjach w zbiorze $ E$ pozostawia się co najwyżej $ m\geq 1$ najlepszych wyrażeń według przyjętej funkcji oceny, przy czym $ m$ oznacza ustaloną szerokość wiązki. Na ich podstawie są następnie generowane i dodawane do zbioru $ E$ wyrażenia zmodyfikowane. Modyfikacja każdego wyrażenia polega na zwiększeniu lub zmniejszeniu wartości jednego lub większej liczby parametrów odpowiadającego mu wzorca o pewną wielkość $ \beta$, inicjowaną jako $ \frac{1}{2}$, lecz na końcu każdej iteracji redukowaną. Nazwiemy ją, ze względu na pewną analogię do modyfikacji wag w parametrycznych aproksymatorach funkcji, rozmiarem kroku. Zmniejszanie rozmiaru kroku jest realizowane przez wywołanie funkcji $ \textit{redukcja-kroku}$, która otrzymuje jako argument dotychczasową wartość $ \beta$ i zwraca nową, zmniejszoną. W najprostszym przypadku redukcja polega na mnożeniu $ \beta$ przez pewien ustalony współczynnik mniejszy od $ 1$, na przykład przez  $ \frac{1}{2}$.

W przypadku wyrażenia, będącego konkretyzacją wzorca zawierającego $ k$ parametrów, wyrażenia zmodyfikowane otrzymuje się dodając do lub odejmując od wartości dowolnych $ 1\leq l\leq k$ z tych parametrów rozmiar kroku $ \beta$. Liczba zmodyfikowanych wyrażeń wyniesie więc

$\displaystyle \sum_{l=1}^k\binom{k}{l}2^l$, (2)

choć również teraz niektóre z nich mogą zostać z góry odrzucone jako niedopuszczalne lub liniowo zależne od innych. Generowaniem zmodyfikowanych wyrażeń w przedstawiony sposób zajmuje się funkcja $ \textit{generuj}$, która jako argumenty otrzymuje zbiór $ E$ i rozmiar kroku $ \beta$. W kolejnej iteracji ponownie w powiększonym w ten sposób zbiorze $ E$ pozostawi się co najwyżej $ m$ najlepszych wyrażeń i przeprowadzi modyfikacje ze zmniejszoną wartością rozmiaru kroku. Iteracje te są kontynuowane do czasu osiągnięcia przez $ \beta$ pewnej ustalonej małej wartości $ \epsilon$, która określa dokładność, z jaką może zostać wyznaczony najlepszy zestaw parametrów wzorców.

Po zakończeniu wiązkowego przeszukiwania przestrzeni parametrów z uzyskanego w ostatniej iteracji zbioru wyrażeń $ E$ jest wybierane jedno najlepsze wyrażenie. Algorytm zapewnia, że obliczane za jego pomocą wartości są silnie skorelowane z wartościami zmiennej $ y$ w zbiorze $ T^{y,x}$, nie zapewnia jednak, że są im równe lub chociaż zbliżone. Ostatecznie zwracane wyrażenie musi więc powstać przez jego dopasowanie do zbioru danych $ T^{y,x}$, co w jest reprezentowane przez operację $ \textit{dopasowanie}$. Dopasowanie to może mieć postać liniowego przekształcenia wyrażenia $ e$, czyli ostatecznie zwracane wyrażenie ma postać $ ae+b$, przy czym parametry $ a$ i $ b$ są dobrane w taki sposób, aby wartości $ ae+b$ były jak najbliższe wartościom $ y$ w zbiorze $ T^{y,x}$. Problem doboru tych wartości to oczywiście nic innego niż (prosty, gdyż dotyczący dwóch zmiennych) problem regresji liniowej.

Równania z wieloma zmiennymi

Odkrywanie równań dotyczących więcej niż dwóch zmiennych jest zdecydowanie bardziej złożone i wymaga bardziej złożonych niż przedstawione dotąd technik. Bezpośrednie ich uogólnienie nie jest możliwe, z wyjątkiej, jak zobaczymy, najprostszej metody wykrywania trendów i stałych. Można natomiast próbować sprowadzić problem odkrycia równania dla wielu zmiennych do problemu wielokrotnego odkrywania równań dla dwóch zmiennych.

Dekompozycja funkcji wielu zmiennych

Gdy system ma eksperymentalną kontrolę nad zmiennymi, między którymi poszukuje związków, lub gdy z góry jest dostępna dostatecznie duża ilość danych, można zastosować technikę dekompozycji funkcji wielu zmiennych, zgodnie z którą traktuje się je jako pewnego rodzaju kombinacje funkcji jednej zmiennej. Założymy obecnie, że jeśli mamy $ n$ zmiennych niezależnych, to dla dowolnej występującej w zbiorze trenującym kombinacji wartości dowolnych $ n-1$ z nich w zbiorze tym jest także dostatecznie wiele różnych wartości pominiętej zmiennej niezależnej i odpowiadających jej wartości zmiennej zależnej, dopuszczając, że w razie potrzeby są przeprowadzane eksperymenty niezbędne do uzyskania tych wartości. Można wówczas wybrać jedną zmienną i podzielić zbiór trenujący na podzbiory, odpowiadające poszczególnym występującym w nim jej wartościom, czyli dokonać selekcji. Następnie dla każdego z tych podzbiorów można poszukiwać, stosując rekurencyjnie ten sam algorytm, zależności zmiennej zależnej od pozostałych zmiennych niezależnych. Po uzyskaniu tych równań można je potraktować jako konkretyzacje wspólnego wzorca i zastosować dowolną metodę odkrywania równań z dwiema zmiennymi do wyznaczenia zależności parametrów tego wzorca od wartości zmiennej wybranej na początku. Ponieważ liczba branych pod uwagę zmiennych niezależnych zmniejsza się przy wywołaniu rekurencyjnym o $ 1$, na pewno głębokość rekurencji nie przekroczy liczby zmiennych niezależnych. Przedstawiony niżej algorytm precyzuje tę koncepcję.


\begin{algorithmic}[1] \FUNCTION $\textit{dekompozycja}(y,V_x)$\INPUTARGS\mbox{}... ...,x})$; \STATE $\textit{podstaw}(s,\psi,e)$; \ENDFOR \RET $s$. \end{algorithmic}

Argumenty przedstawionej funkcji to zmienna zależna $ y$, zbiór zmiennych niezależnych $ V_x$ oraz zbiór przykładów $ P$, o którym zakładamy, że zawiera dostatecznie dużą ilość danych. Przy pierwszym wywołaniu jest to zbiór trenujący $ T^{y,V_x}$. Działanie algorytmu rozpoczyna się od sprawdzenia kryterium stopu algorytmu. Jeśli jest ono spełnione, to nie następują żadne wywołania rekurencyjne i zmienną $ y$ traktuje się jako stałą na zbiorze $ P$, nawet jeśli naprawdę ma ona różne wartości. Takie zatrzymanie rekurencji musi nastąpić w szczegóności, jeśli zbiór $ V_x$ nie zawiera żadnej zmiennej. Wówczas wprawdzie zmienna $ y$ może nie być stała na skutek niepoprawności danych lub występowania ukrytej zależności $ y$ od innych nieznanych zmiennych, lecz nie mając na te czynniki wpływu musimy ją traktować jako stałą. Może się okazać, że nawet jeśli $ V_x\neq\emptyset$, to wartości zmiennej $ y$ są stałe na zbiorze $ P$ i wtedy także nie ma potrzeby wykonywania dalszych wywołań rekurencyjnych. Przyjmiemy zatem, że kryterium stopu obejmuje oba te przypadki i że w każdym z nich jest zwracana stała wartość uzyskana za pomocą wywołania funkcji $ \textit{stała}(y,P)$. Może to być w rzeczywistości średnia wartość zmiennej $ y$ obserwowana w zbiorze $ P$.

Jeśli nie jest spełnione kryterium stopu, czyli zbiór zmiennych niezależnych $ V_x$ nie jest pusty i wartości zmiennej $ y$ nie są stałe, to ze zbioru $ V_x$ jest wybierana pewna zmienna niezależna $ x$. Algorytm wywołuje w tym celu pomocniczą funkcję $ \textit{zmienna-niezależna}$. Sposób wyboru tej zmiennej z punktu widzenia poprawności algorytmu może być zupełnie dowolny, możemy jednak liczyć na najlepsze efekty wybierając zmienną, od której wartości najsilniej zależą wartości zmiennej $ y$, czyli dla której odpowiedni współczynnik korelacji ma największą wartość (bezwzględną). Taka strategia daje pewność, że jeśli niektóre zmienne niezależne są nieistotne, nie będziemy im niepotrzebnie poświęcać uwagi. Dla wybranej zmiennej $ x$ przez $ P_{xb}$ oznaczamy zbiór tych przykładów ze zbioru $ P$, dla których ma ona pewną ustaloną wartość $ b$. Brane są pod uwagę wszystkie występujące w zbiorze $ P$ wartości $ b$ zmiennej $ x$ i dla każdej z nich odpowiedni zbiór przykładów $ P_{xb}$ (wynik selekcji) jest traktowany jako zbiór trenujący do uczenia się zależności $ y$ od pozostałych zmiennych niezależnych. W tym celu są wykonywane rekurencyjne wywołania algorytmu. Otrzymywane w ich wyniku wyrażenia są gromadzone w zbiorze $ E$.

Po rozpatrzeniu wszystkich wartości zmiennej $ x$ wyrażenia ze zbioru $ E$ są traktowane jako różne konkretyzacje pewnego wspólnego wzorca. Interesuje nas wzorzec o minimalnej liczbie parametrów, którego konkretyzacjami są wszystkie te wyrażenia. Taki wzorzec będziemy nazywać minimalnym wzorcem. Jego wyznaczenie dla dowolnego zbioru wyrażeń jest operacją dość prostą, w naszym przypadku na jej uproszczenie dodatkowo wpływa fakt, że wszystkie te wyrażenia są generowane przez ten sam algorytm, nie będziemy się więc zatrzymywać nad sposobem realizacji funkcji $ \textit{minimalny-wzorzec}$, która ma to zadanie wykonać. Przyjmujemy, że zwraca ona trzy wartości: wzorzec $ s$, zbiór występujących w nim parametrów $ \Psi$ oraz oznaczany przez $ P^{\Psi}$ zbiór zestawów wartości tych parametrów, odpowiadających poszczególnym wyrażeniom ze zbioru $ E$. Przyjmujemy dokładniej, że

$\displaystyle P^{\Psi} = \{P^{\psi,x} \;\vert\; \psi\in\Psi\}$, (3)

czyli że $ P^{\Psi}$ jest rodziną zbiorów przykładów dla każdego parametru. Dla parametru $ \psi\in\Psi$ zbiór $ P^{\psi,x}$ zawiera przykłady jego zależności od wartości zmiennej $ x$, czyli pary postaci $ \langle b,\psi_b\rangle$ dla każdej wartości $ b$ zmiennej $ x$, dla której znalezione zostało pewne wyrażenie znajdujące się w zbiorze $ E$.

Dla każdego parametru $ \psi\in\Psi$ uzyskanego wzorca pozostaje znaleźć jego zależność od wybranej na początku zmiennej $ x$. Jest to prosta zależność dla dwóch zmiennych, do której znalezienia może być użyta dowolna metoda, podstawiona w przedstawionym algorytmie w miejsce wywołania procedury $ \textit{znajdź-równanie1}$. Poszukuje ona zależności $ \psi$ od $ x$ na podstawie zbioru trenującego $ P^{\psi,x}$. Znalezione wyrażenie zastępuje we wzorcu $ s$ parametr $ \psi$. Po zastąpieniu wszystkich parametrów uzyskane wyrażenie jest zwracane jako wynik działania algorytmu.

Wykrywanie korelacji

Powyższe podejście nie może być zastosowane, jeśli zbiór dostępnych danych nie jest dostatecznie duży, a system nie ma eksperymentalnej kontroli nad wartościami zmiennych i nie może pozyskać potrzebnych mu przykładów. Musi on wtedy pozostać biernym obserwatorem dostarczanych mu danych, które mogą nie zawierać przykładów potrzebnych do użycia podejścia opartego na dekompozycji. Okazuje się, że pomocna może być w tym przypadku nieco zmodyfikowana najprostsza z omawianych heurystyk dla znajdowania prostych równań z dwiema zmiennymi: technika wykrywania stałych i trendów. Modyfikacja polega na tym, że obecnie zamiast wykrywać monotoniczne trendy, przy których wzrost wartości jednej zmiennej pociąga za sobą wzrost lub spadek warości drugiej zmiennej, staramy się wykrywać korelacje zachodzące między wartościami zmiennych. Jeśli okaże się, że wartości $ x$ i $ y$ są pozytywnie skorelowane, to jest tworzona nowa zmienna $ t=x/y$, jeśli zaś $ x$ i $ y$ są skorelowane negatywnie, to jest tworzona nowa zmienna $ t=xy$.

Korelacje o różnym stopniu mogą występować między wieloma parami zmiennych, co powoduje potrzebę wyboru najbardziej obiecujących. Typowym podejściem jest wtedy zastosowanie przeszukiwania wiązkowego zbioru możliwych zmiennych, zgodnie z którym bierze się pod uwagę ustaloną liczbę $ m\geq 1$ najsilniej skorelowanych par zmiennych, na podstawie których tworzy się nowe zmienne. W kolejnej iteracji ponownie oblicza się współczynniki korelacji dla wszystkich par zmiennych, postępując w ten sposób aż do wykrycia zmiennej o stałej wartości lub zmiennych zależnych liniowo czy też ,,prawie liniowo''. Można liczyć na to, że w miarę tworzenia zmiennych o coraz bardziej złożonych definicjach, uwzględniających coraz więcej pierwotnie dostępnych zmiennych, największe współczynniki korelacji będą się zbliżać do $ 1$ lub $ -1$. Gdy dla pewnej pary zmiennych współczynnik korelacji stanie się dostatecznie bliski $ 1$ co do wartości bezwzględnej, można przyjąć, że zmienne te łączy zależność liniowa i zwrócić opisujące tę zależność równanie.

Zagadnienia praktyczne

W praktyce często trudno liczyć na znalezienie równań dla wszystkich atrybutów ciągłych na podstawie całego dostępnego zbioru danych. Konieczne może się okazać dokonywanie dwóch rodzajów ograniczeń:

Oznacza to, że prawdziwie użyteczny system odkrywania równań powinien być wyposażony w pewne strategie (zapewne heurystyczne) dekompzycji zbioru danych i wyboru zestawu atrybutów. Jeśli dekompozycja jest określana przez warunki nałożone na wartości jednego lub większej liczby atrybutów, to może być reprezentowana np. za pomocą drzewa decyjnego. Jego węzły zawierałyby warunki, a liście wyznaczałyby podzbiory całego zbioru danych, dla których bezpośrednio poszukiwane byłyby równania. Kryterium podziału (wyboru warunków do węzłów) mogłoby uwzględniać średnią wartość bezwzględną współczynnika korelacji dla par atrybutów na podzbiorach powstałych w wyniku podziału. Wybór atrybutów, dla których poszukiwać należy równań, można również oprzeć na współczynniku korelacji, zaczynając od dwóch atrybutów o maksymalnej wartości bezwzględnej współczynnika korelacji i następnie dołączając do nich kolejne atrybuty maksymalnie skorelowane z nimi.

Literatura

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

About this document ...

Metody odkrywania wiedzy: wykład 14
Odkrywanie równań

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

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

Pawel Cichosz 2004-02-12