\chapter{Selekcja cech i modeli}\label{cha:FSiMS}
Głównym celem ekstrakcji wiedzy z danych jest taka jej reprezentacja, by była łatwa i zrozumiała dla człowieka. Dlatego też najczęściej wiedzę przedstawia się w postaci zbioru reguł, gdyż taki zapis wydaje się być najbardziej intuicyjny i powinien w spełnić własność łatwości interpretacji (prostota systemu). Można więc ponownie przytoczyć tutaj kryteria, które powinien spełniać dobrze zdefiniowany system regułowy - z jednej strony powinien przedstawiać informacje w postaci jak najmniejszego zbioru reguł, przy czym  liczba przesłanek w poszczególnych regułach powinna być również minimalna zwiększając prostotę systemu, z drugiej zaś strony powinien charakteryzować się jak największą generalizacją i dokładnością. W przypadku reguł prototypowych (reguł-P) problem selekcji prototypów, a tym samym problem redukcji liczby reguł, został opisany w rozdziale \ref{chap:ProtoSel}. Jednakże spełnienie opisanego kryterium prostoty wymaga również rozważenia problemu selekcji cech, redukując tym samym liczbę przesłanek.\\
Niezależnym i bardzo istotnym problemem systemów inteligencji obliczeniowej jest poszukiwanie optymalnego modelu dla danego zagadnienia. Powszechnie znane twierdzenie {\it nie ma obiadu za darmo} (ang. No free lunch theorem) wskazuje na to, iż nie istnieje jeden najlepszy algorytm lub ich kombinacja, pozwalająca na znalezienie zawsze optymalnego rozwiązania. Dlatego też konieczne staje się znalezienie odpowiednich metod oceny oraz przeszukiwania - zwanych meta uczeniem (ang. meta learning), pozwalających na rozwiązanie takiego problemu. Innym istotnym zagadnieniem, również związanym z problemem meta uczenia, jest poszukiwanie przestrzeni modelu w celu optymalizacji jego parametrów. 
%=======================================================================================
\section{Selekcja cech}
Problem selekcji cech jest niezwykle szerokim polem nauki, cieszącym się w ostatnich latach coraz większym zainteresowaniem. Dowodem tego może być gwałtownie wzrastająca liczba publikacji związanych z tym tematem. Pociąga to jednocześnie coraz większą liczbę możliwych sposobów rozwiązania problemu doboru optymalnego podzbioru cech.\\
Algorytmy metod selekcji cech można podzielić na różne sposoby, jednak najbardziej istotnym kryterium podziału wydaje się być podział na metody filtrów (ang. filter methods), metody opakowujące (ang. wrappers methods)\cite{F-Kohavi-WrappersFS,F-Kohavi-WrappersApproach}, oraz metody wbudowane (ang. embedded methods). \\
Pierwsza z grup metod przeprowadza niezależną od procesu klasyfikacji selekcję cech. Z reguły, jako kryterium działania filtrów używa się różnych statystyk, które oceniają cechy pod względem ich korelacji z etykietami oraz (lub) usuwają ze zbioru cechy redundantne (częstym kryterium filtracji cech jest optymalność w sensie Bayesowskim). Druga zaś grupa metod - opakowujące - do oceny jakości cech używają klasyfikatora i wybierają z całego zbioru atrybutów jedynie te, które pozwalają na najlepszą jego jakość klasyfikacji. Podejście to ma bardzo silne podstawy teoretyczne, co zostało pokazane w pracach Kohaviego, gdyż zbiór optymalnych cech w sensie Bayesowskim nie oznacza optymalnego zbioru cech dla danego klasyfikatora. Ostatnią grupą metod są algorytmy, które posiadają wbudowaną właściwość selekcji cech, ich typowym przykładem są algorytmy drzew decyzji. Osobną możliwą grupą są metody łączące w sobie różne przedstawione powyżej podejścia. Charakteryzują się one tym, iż wstępnej oceny dokonuje inny klasyfikator niż ostateczny lub gdy cząstkowe wyniki filtrów są następnie oceniane przez klasyfikator końcowy. Czasami do oceny istotności cechy używana jest dokładność klasyfikacji w zamian za kryteria statystyczne bądź, w przypadku bardzo dużych zbiorów danych, metody opakowujące poprzedzane są wstępną filtracją cech. \\
Powszechnie używane są dwa niezależne podejścia we wspomnianych grupach metod - algorytmy rankingowe oraz algorytmy przeszukiwania. Pierwsze dokonują niezależnej oceny każdej z cech indywidualnie, a następnie w oparciu o posortowane wartości istotności dokonywany jest wybór odpowiedniego podzbioru cech. Natomiast metody przeszukiwania korzystają z różnych algorytmów przeszukiwania grafów (drzew) w celu optymalizacji zbioru atrybutów. Drugie z wymienionych podejść charakteryzuje się dużo większą dokładnością, a uzyskiwane rezultaty z reguły przewyższają wyniki metod rankingowych, choć wymagają one dużego nakładu obliczeniowego. Natomiast metody rankingowe są znacznie szybsze, co jest ich istotną zaletą, jednak nie gwarantują one tak dobrych rezultatów jak metody przeszukiwania.  \\
Ponieważ w systemach reguł-P istotną cechą jest prostota uzyskanego rozwiązania przy jednoczesnej maksymalnej zdolności uogólniania, dlatego w rozprawie skoncentrowano się na analizie metod opakowujących oraz metod hybrydowych łączących metody rankingowe oraz metody opakowujące.
%----------------------------------------------------------------------------------------
\subsection{Metody rankingowe}
Metody rankingowe są najszybszymi metodami selekcji cech. Bazują one na wyznaczeniu współczynnika $J(\cdot)$ określającego zdolność dyskryminacji lub zależność pomiędzy cechą $f$ a klasą $C$. Współczynnik ten wyznaczany jest indywidualnie dla każdego z atrybutów, a następnie w zależności od wielkości współczynnika $J(\cdot)$ następuje sortowanie od najbardziej do najmniej istotnej cechy. W ostatnim kroku według określonego kryterium np. zdolności dyskryminacji (funkcja oceń$(\cdot)$), pierwszych $n'$ najlepszych cech  wybieranych jest jako podzbiór finalny. Algorytm rankingowy przedstawiony jest na schemacie \reff{fi:FSRank}.
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE ${\bf f}$ \COMMENT{wejściowy zbiór cech} 
	\REQUIRE $J(\cdot)$	\COMMENT{funkcja rankingowa}
	\FOR{$i=1\ldots n$}
		\STATE $a_i \leftarrow J(f_i)$ \COMMENT{oceń i-tą cechę}
	\ENDFOR
	\STATE ${\bf f} \leftarrow {\rm sort}({\bf f},\bf{a})$ \COMMENT{sortuj cechy wg. istotności}
	\STATE $acc \leftarrow 0$ 
	\STATE ${\bf f}^a \leftarrow \emptyset$
	\FOR{$j = 1 \ldots n$} %\COMMENT{dla każdej z cech}
		\STATE ${\bf f}^a={\bf f}^a \cup f_i$  \COMMENT{dodaj do podzbioru ${\bf f}^a$ nową cechę}
		\STATE $tacc \leftarrow $oceń$({\bf f}^a)$ \COMMENT{oceń podzbiór cech ${\bf f}^a$ }
		\IF{$tacc>acc$} 
			\STATE $acc \leftarrow tacc$ \COMMENT{jeżeli nowy podzbiór jest lepszy od poprzedniego }
			\STATE ${\bf f'} \leftarrow {\bf f}^a$ \COMMENT{zapamiętaj wynik aktualny podzbiór}
		\ENDIF
	\ENDFOR
	\RETURN ${\bf f'}$
\end{algorithmic}
	\label{fi:FSRank} 
	\caption{Selekcja cech w oparciu o ranking cech}%
\end{algorithm}

Metody rankingowe używają różnych metod oceny jakości pojedynczej cechy, a jedną z nich jest wykorzystanie algorytmów klasyfikacji do oceny każdej z cech według zależności  $J_i=\acc(Model(\BT_i,\alpha))$, gdzie $\alpha$ to zbiór parametrów modelu, a $\acc$ to jego dokładność. Innymi powszechnie używanymi kryteriami są miary statystyczne oraz bazujące na teorii informacji. Przykładem takich miar jest metryka, zwana znormalizowanym zyskiem informacji (ang. normalized information gain), znana również jako asymetryczny współczynnik zależności (ang. asymmetric dependency coefficient, ADC) opisana równaniem \reff{eq:ADC} \cite{F-Shridhar_1998}:

\be \label{eq:ADC} ADC(C ,f) =  \frac{MI \left( C , f\right)}{ H \left( C \right) } \ee

gdzie $H(c)$ oraz $H(f)$ to odpowiednio entropia klas i cechy, zaś $MI(C,f)$ to informacja wzajemna (ang. mutual information) pomiędzy klasami $C$ i cechą $f$ określona przez Shanonna \cite{F-Shanonn_1946} jako \reff{eq:ShannonMI} 
\be \label{eq:ShannonMI}
\begin{array}{c}
H(C) = -\sum_{i=1}^c  p(C_i) \lg_2 p(C_i) \\
H(f) = - \sum_x p(f=x) \lg_{2}  p(f=x)  \\
MI(C,f) = - I(C,f)  +H(C) + H(f) 
\end{array}
\ee
W zależności tej suma po $x$ jest realizowana jedynie dla cech $f$ przyjmujących dyskretne wartości, natomiast cechy ciągłe wymagają zamiany sumy na całkę lub wstępnej dyskretyzacji by możliwa była estymacja prawdopodobieństwa $p(f=x)$.\\
Innym przykładem metryki zaproponowanym przez Setiono \cite{F-Setiono_1996} jest miara znormalizowanego względnego zysku informacyjnego (ang. normalized gain
ratio) opisanego zależnością \reff{eq:Setiono}.
 

\be \label{eq:Setiono} U_{S}(C,f)\; = \; \frac{MI(C,f)}{H(f)} \ee

Inną możliwą normalizacją służącą do wyznaczenia zysku informacyjnego może być miara wyznaczająca entropię klasa-cecha poprzez \reff{eq:UH}. 

\be \label{eq:UH} U_{H}(C,f) =  \frac{MI(C,f)}{H(f,C)} \ee
%
gdzie $H(f,C)$ jest połączoną entropią zmiennych cecha $f$ klasa $C$.\\

Mantaras \cite{F-Mantaras_1991} zaproponował interesujące kryterium $D_{ML}$ spełniające wszystkie aksjomaty odległości, określoną jako \reff{eq:Mantaras}.

\be \label{eq:Mantaras} D_{ML}(f_i,C)\;=\;H(f_i|C)\;+\; H(C|f_i) \ee

gdzie $H(f_i|C)$ i $H(C|f_i)$ są entropią warunkową zdefiniowaną przez Shanonna
\cite{F-Shanonn_1946} jako $H(X|Y)=H(X,Y)-H(Y)$.

Index ważonej połączonej  entropii został zaproponowany przez Chi \cite{F-Chi_1993} jako \reff{eq:chi}

\be \label{eq:chi} Ch(f) = - \sum_{k=1}^{N} p(f=x_k) \sum_{i=1}^{K} p(f=x_k ,C_i) \lg_{2}
p(f=x_k ,C_i) \ee

Pewną alternatywą do przedstawionych tu miar teorioinformacyjnych jest statystyka $\chi^2$, która mierzy zależność pomiędzy dwoma zmiennymi losowymi - tu zdefiniowanymi jako relacja pomiędzy cechą a klasą. Statystyka $\chi^2$ zdefiniowana jest wyrażeniem \reff{eq:chi2}.

\be \label{eq:chi2} \chi^{2}(f,C) = \sum_{ij} \frac{\left(p(f=x_j,C_i)-p(f=x_j)*p(C_i)
\right)^{2}} { p(f=x_j)p(C_i) } \ee
%
gdzie $p(\cdot)$ są odpowiednimi prawdopodobieństwami. Duże wartości $\chi^2$ odpowiadają silnej korelacji pomiędzy cechą a klasą, dzięki czemu możliwe jest wykorzystanie tej statystyki do przeprowadzenia procesu rankingu. \\
Przedstawione powyżej współczynniki stanowią jedynie wybrane miary mierzące relacje podobieństwa rozkładów klasa - cecha. Możliwe jest więc przedstawienie szeregu innych współczynników, do których należą różne współczynniki statystyczne, jak Pearsonowski współczynnik korelacji \cite{F-Hall}. Porównanie wyżej opisanych metod rankingowych opisano w rozdziale \ref{sec:FS-comp}.\\
Jak już wspomniano wcześniej, metody rankingowe są najszybszymi metodami selekcji cechy, gdyż ocenie poddawane są globalnie pojedyncze atrybuty. Takie rozwiązanie pociąga jednak za sobą poważne negatywne konsekwencje, mianowicie w finalnym zbiorze cech pozostają wszystkie atrybuty redundantne $\mathop{\exists}\limits_{i\neq j} f_i=f_j$. Związane jest to z faktem, iż warunkiem koniecznym, lecz nie wystarczającym redundancji jest równość współczynników rankingowych. Powoduje to, że cechy redundantne po dokonaniu rankingu występują obok siebie i dodanie nowej kolejnej cechy wynikającej z rankingu nie wpływa na jakość wyników klasyfikacji, a jedynie niepotrzebnie zwiększa liczbę cech opisujących dany problem. Rozwiązaniem tego problemu są metody filtrów poprzedzające optymalizację wyboru liczby cech użytych do klasyfikacji, a usuwające z rankingu cechy redundantne. Przykładem takiego rozwiązania jest algorytm zaproponowany przez Biesiadę i Ducha \cite{F-Biesiada-KomSmirnof}, bazujący na statystyce Kolmogorova-Smirnova porównujący skumulowane rozkłady prawdopodobieństwa dla par cech oceniając czy cechy są redundantne. 

%------------------------------------------------------------------------------------
\subsection{Metody przeszukiwania w selekcji cech} 
Przewagą metod przeszukiwania nad metodami rankingowymi jest większa dokładność uzyskanych wyników. Metody te bazują na algorytmach przeszukiwania, zarówno stochastycznych jak i heurystycznych. Pociąga to jednak za sobą zwiększony koszt obliczeniowy, co w przypadku dużych zbiorów danych (jak przykładowo dostarczonych podczas zawodów rozgrywanych w ramach konferencji NIPS'2003, gdzie zbiory liczyły odpowiednio 100 tysięcy i 60 tysięcy cech)  może być poważnym ograniczeniem.  Typowymi rozwiązaniami rodziny algorytmów przeszukiwania są metody selekcji w przód i tył (ang. forward/backward selection) oraz algorytmy genetyczne.

\paragraph{Selekcja w przód.}
Algorytm selekcja w przód \reff{fi:ForwardSel} rozpoczyna od pustego zbioru cech i stopniowo w każdej iteracji dodaje nową cechę, spośród pozostałych cech, która maksymalizuje określone kryterium (z reguły dokładność liczoną w procesie walidacji krzyżowej).
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE ${\bf f}$
	\STATE ${\bf f}^a \leftarrow \emptyset$
	\FOR{$j=1\ldots n$}
		\STATE ${\bf f'} \leftarrow {\bf f}^a$
		\FOR{$i=1\ldots n$}
			\STATE ${\bf f}^b \leftarrow {\bf f'} \cup f_i$
			\STATE $tacc \leftarrow $oceń$({\bf f}^b)$
			\IF{$tacc > acc$}
				\STATE $acc \leftarrow tacc$ 
				\STATE ${\bf f}^a \leftarrow {\bf f}^b$
			\ENDIF
		\ENDFOR
	\ENDFOR
	\RETURN ${\bf f'}$
\end{algorithmic}
	\label{fi:ForwardSel}
	\caption{Selekcja w przód}
\end{algorithm}

\paragraph{Selekcja w tył.}
Algorytm selekcji w tył \reff{fi:BackwardSel} w odróżnieniu od selekcji w przód, rozpoczyna od pełnego zbioru cech i iteracyjnie usuwa te cechy, które psują jakość klasyfikacji. W każdej iteracji usuwana jest jedna cecha mająca najbardziej negatywny wpływ na dokładność klasyfikacji, aż do momentu gdy określone kryterium przestanie rosnąć.
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE ${\bf f}$
	\STATE ${\bf f}^a \leftarrow {\bf f}$
	\FOR{$j=1\ldots n$}
		\STATE ${\bf f'} \leftarrow {\bf f}^a$
		\FOR{$i=1\ldots n$}
			\STATE ${\bf f}^b \leftarrow {\bf f'} \setminus f_i$
			\STATE $tacc \leftarrow $oceń$({\bf f}^b)$
			\IF{$tacc > acc$}
				\STATE $acc \leftarrow tacc$ 
				\STATE ${\bf f}^a \leftarrow {\bf f}^b$
			\ENDIF
		\ENDFOR
	\ENDFOR
	\RETURN ${\bf f'}$
\end{algorithmic}
	\label{fi:BackwardSel}
	\caption{Selekcja w tył} 
\end{algorithm}

\paragraph{Inne}
Spośród innych rozwiązań na uwagę zasługują metody uczenia typu {\it dodaj $i$ odejmij $j$} \cite{F-Pudil-FloatingSearchFS}, gdzie w każdej iteracji dodawanych jest $i$ nowych cech w procesie selekcji w przód, a odejmowanych jest $j$ cech gdzie $i>j$. Metoda ta dokonuje dużo dokładniejszego przeszukania niż proste metody selekcji w przód lub tył, jednak wielokrotnie wzrasta złożoność obliczeniowa takiego rozwiązania. Kolejnym powszechnie stosowanym rozwiązaniem są systemy stochastycznego przeszukiwania jak algorytmy genetyczne \cite{F-Siedlecki-GeneticFS,F-Kuncheva-GeneticFS,F-Oh-GeneticFS} lub inne bazujące na systemach immunologicznych \cite{F-Bereta-SwornFS}. Bardzo dokładne studium procesu selekcji cech z opisem różnych metod i strategii można znaleźć w \cite{B-NIPS} oraz w repozytorium prowadzonym przez J. Biesiadę w ramach projektu Fsel++ \cite{F-Biesiada-InfoselWWW}, gdzie zgromadzonych zostało ponad 724 różnych publikacji wyłącznie o tematyce selekcji cech. 

\subsection{Analiza skuteczności algorytmów selekcji cech} \label{sec:FS-comp}
Duża liczba różnych algorytmów selekcji cech wymaga przeprowadzenia analizy w celu wyznaczenia tych metod, które najlepiej realizują przedstawione im zadania. W tym celu dokonano empirycznego porównania metod selekcji zarówno w oparciu o ranking, jak i metody przeszukiwania. Weryfikacji poszczególnych metod dokonano porównując wyniki klasyfikacji na zbiorach opisanych w rozdziale \ref{chap:Dodatek}. Procedura testowa polegała na wybraniu przez algorytm selekcji cech podzbioru atrybutów i na tym podzbiorze przeprowadzenie testu walidacji krzyżowej klasyfikatora. Dodatkowo metody rankingowe przetestowano na sztucznych zbiorach danych o znanym rozkładzie klas i istotności poszczególnych cech (zbiory {\it Gauss1} oraz {\it Gauss2}). Jako klasyfikatory zostały wykorzystane zaproponowane w pracy algorytmy ekstrakcji reguł prototypowych typu \kNN - algorytm CFCM w połączeniu z LVQ oraz optymalizacją liczby prototypów poprzez algorytm wyścigu, jak również algorytm OPTDL. Do wyznaczenia wskaźników \reff{eq:ADC} -\reff{eq:chi2} wykorzystano pakiet selekcji cech Fsel++ \cite{F-Biesiada-InfoselWWW}\\

\subsubsection{Wyniki} \label{sec:AttrSelRes}
\paragraph{Metody rankingowe.}
Wstępnie każdy z przedstawionych w pracy współczynników rankingowych poddano ocenie na znanych zbiorach nazwanych {\it Gauss1} oraz {\it Gauss2}. Zbiory te są sztucznymi zbiorami danych o odpowiednio 4 i 8 cechach ciągłych. Obydwa zbiory składają się z 4 klas i 4000 wektorów, po 1000 wektorów przypadających na każdą z klas. Zbiór {\it Gauss1} stanowi zbiór czterech Gaussowskich skupisk w kolejnych wymiarach coraz bardziej nachodzących na siebie. Centrum pierwszego klastra położone jest we współrzędnych $\Bp_1=[0,0,0,0]^T$, a kolejnych $\Bp_2=a\cdot[1,1/2,1/3,1/4]^T$, $\Bp_3=2a\cdot[1,1/2,1/3,1/4]^T$ oraz  $\Bp_4=3a\cdot[1,1/2,1/3,1/4]^T$. Taki układ klastrów powoduje, że współczynniki istotności cech powinny przedstawiać się następująco $[f_1 > f_2 > f_3 > f_4]$.\\
Zbiór {\it Gauss2} jest rozszerzeniem zbioru {\it Gauss1} o dodatkowe 4 liniowo zależne cechy, według zależności $f_i+4 = 2f_i + \epsilon$ gdzie $\epsilon$ stanowi dodany szum o rozkładzie jednostajnym.\\
Wyniki obliczeń przeprowadzone na danych wygenerowanych sztucznie wykazały równoważność wszystkich metryk, które jednogłośnie i bezbłędnie wskazały na istotność poszczególnych cech. Jednak wyniki uzyskane dla realnych zbiorów danych wykazują zmiany porządku hierarchii istotności cech. Różnice te były możliwe do zaobserwowania również ze względu na jakość dyskretyzacji, gdyż  do estymacji $p(f=X_j,C_i)$ posłużono się histogramami o 5, 10 oraz 15 przedziałach. Dlatego też do porównania współczynników wykorzystano wartości rankingowe, które dla danej dyskretyzacji najlepiej wypadły w ocenie dokładności klasyfikacji. Proces oceny jakości współczynników rankingowych został podzielony na dwa etapy, gdzie w pierwszym dokonano rankingu cech, a następnie w oparciu o uzyskane wyniki przeprowadzono testy dziesięciokrotnej walidacji krzyżowej klasyfikatora. \\
Wyniki obliczeń przedstawiono na wykresach rys.\reff{fi:FS-RankCFCM} dla algorytmu CFCM+LVQ oraz na wykresach rys.\reff{fi:FS-RankOPTDL} dla algorytmu OPTDL. Poszczególne wykresy  przedstawiają zależność dokładności klasyfikacji w funkcji liczby $n$-pierwszych cech o najwyższej wartości współczynnika dla 4 różnych losowo wybranych zbiorów danych.    
%\bfig
%	\epsfig{figure=pic/AttrS_Io,width=9cm,height=6cm}
%	\caption{Wyniki rankingu dla zbioru {\it jonosfera}}
%	\label{fi:FS-IO}
%\efig
%
%\bfig
%	\epsfig{figure=pic/AttrS_Cl,width=9cm,height=6cm}
%	\caption{Wyniki rankingu dla zbioru {\it choroby serca}}
%	\label{fi:FS-Cl}
%\efig
%
%\bfig
%	\epsfig{figure=pic/AttrS_Pi,width=9cm,height=6cm}
%	\caption{Wyniki rankingu dla zbioru {\it cukrzyca}}
%	\label{fi:FS-Pi}
%\efig
%
%\bfig
%	\epsfig{figure=pic/AttrS_Wb,width=9cm,height=6cm}
%	\caption{Wyniki rankingu dla zbioru {\it rak piersi}}
%	\label{fi:FS-WB}
%\efig
\bfig
\subfigure[Zbiór {\it jonosfera}]{\label{fi:FS-RankCFCM-Io}\includegraphics[width=0.45\textwidth]{pic/AttrS_Io}}
\subfigure[Zbiór {\it choroby serca}]{\label{fi:FS-RankCFCM-Cl}\includegraphics[width=0.45\textwidth]{pic/AttrS_Cl}}
\subfigure[Zbiór {\it cukrzyc}]{\label{fi:FS-RankCFCM-Pi}\includegraphics[width=0.45\textwidth]{pic/AttrS_Pi}}
\subfigure[Zbiór {\it rak piersi}]{\label{fi:FS-RankCFCM-Wb}\includegraphics[width=0.45\textwidth]{pic/AttrS_Wb}}
	\caption{Wyniki rankingu dla algorytmu CFCM+LVQ}
	\label{fi:FS-RankCFCM}
\efig

\bfig
\subfigure[Zbiór {\it jonosfera}]{\label{fi:FS-RankOPTDL-Io}\includegraphics[width=0.45\textwidth]{pic/OAttrS_Io}}
\subfigure[Zbiór {\it choroby serca}]{\label{fi:FS-RankOPTDL-Cl}\includegraphics[width=0.45\textwidth]{pic/OAttrS_Cl}}
\subfigure[Zbiór {\it cukrzyc}]{\label{fi:FS-RankOPTDL-Pi}\includegraphics[width=0.45\textwidth]{pic/OAttrS_Pi}}
\subfigure[Zbiór {\it rak piersi}]{\label{fi:FS-RankOPTDL-Wb}\includegraphics[width=0.45\textwidth]{pic/OAttrS_Wb}}
	\caption{Wyniki rankingu dla algorytmu OPTDL}
	\label{fi:FS-RankOPTDL}
\efig






%\bfig
%	\epsfig{figure=pic/OAttrS_Io,width=9cm,height=6cm}
%	\caption{Wyniki rankingu dla zbioru {\it jonosfera}}
%	\label{fi:FS-IO-OP}
%\efig
%
%\bfig
%	\epsfig{figure=pic/OAttrS_Cl,width=9cm,height=6cm}
%	\caption{Wyniki rankingu dla zbioru {\it choroby serca}}
%	\label{fi:FS-Cl-OP}
%\efig
%
%\bfig
%	\epsfig{figure=pic/OAttrS_Pi,width=9cm,height=6cm}
%	\caption{Wyniki rankingu dla zbioru {\it cukrzyca}}
%	\label{fi:FS-Pi-OP}
%\efig
%
%\bfig
%	\epsfig{figure=pic/OAttrS_Wb,width=9cm,height=6cm}
%	\caption{Wyniki rankingu dla zbioru {\it rak piersi}}
%	\label{fi:FS-WB-OP}
%\efig


%Dla realnych zbiorów danych wyniki szeregowania cech wg. różnych wskaźników przedstawiają tabele \reff{tab:HyperRank} odpowiednio dla każdego zbioru danych.
%
%Oceny współczynników rankingowych dokonano porównując jakość klasyfikacji po dodaniu kolejnych cechach wynikających z wartości współczynnika rankingowego. Porównania dokonano na zbiorach {\it Gauss1}, {\it Gauss2}, {\it Hypothyroid} oraz {\it Abalone}, dokonując niezależnie rankingu cech na całym zbiorze, a następnie poddając uzyskany z rankingu wynik analizie w oparciu o typowe klasyfikatory jak 1NN oraz C4.5. Ponieważ metody wyznaczenie wartości współczynników rankingowych wymagają estymacji prawdopodobieństw łącznych $p(f=X_j,C_i)$ dlatego też posłużono się w tym celu histogramami dyskretyzując każdą z cech metodą stałej szerokości dzieląc je na 16 oraz 32 przedziały. Przy czym zamieszczone wyniki dotyczą najlepszy uzyskanych rezultatów. Weryfikacji poddano współczynniki opisane równaniami  \reff{eq:ADC} -\reff{eq:chi2} wykorzystując w tym celu pakiet selekcji cech Infosel \cite{F-Biesiada-InfoselWWW} \\ 
%Wyniki obliczeń przeprowadzone na danych wygenerowanych sztucznie wykazały równoważność wszystkich metryk, które jednogłośnie i bezbłędnie wskazały na istotność poszczególnych cech. Dla realnych zbiorów danych wyniki szeregowania cech wg. różnych wskaźników przedstawiają tabele \reff{tab:HyperRank} odpowiednio dla zbiorów danych {\it hyperthyroid} i {\it abalone}.
%
%Analiza uzyskanych wyników z tabeli \reff{tab:HyperRank} wskazuje na porównywalną kolejność rankingu cech. Wszystkie stosowane indeksy wskazały na za najistotniejsze cechy  21, 17, 19, 18, przy czym są to cechy ciągłe, a na uzyskane wyniki nie miała wpływu liczba podziałów dyskretyzacji. Dla mniej istotnych cechy pojawiają się drobne różnice, jednakże nie miały one istotnego znaczenia i wpływu na jakość dyskryminacji. Analiza wykresów \reff{fi:Hyp1NN} oraz \reff{fi:HypC45} wskazuje, że maksymalną zdolność klasyfikacji osiągano po prezentacji pierwszych 6 cech, a pozostałe cechy nie wpływały istotnie na jakość klasyfikacji. Dla wyników uzyskanych dla klasyfikatora 1NN widoczna jest dominująca właściwość indeksu $U_S$. Dla algorytmu C4.5 na wykresach zauważalna jest stabilizacja wyników wynikająca z właściwości algorytmów drzewa decyzji polegającej na automatycznym oczyszczaniu drzewa i pozostawieniu jedynie istotnych z punktu widzenia drzewa cech. 
%\bfig
%\vspace*{-1cm}
%\epsfig{figure=pic/comp1NN,width=9cm,height=6cm}
%\caption{Dokładność w funkcji liczby, zbiór {\it hypothyroid}, klasyfikator 1NN}
%\label{fi:Hyp1NN}
%\efig
%\vspace*{-1.2cm}
%\bfig
%\vspace*{-1cm}
%\epsfig{figure=pic/compC45,width=9cm,height=6cm}
%\caption{Dokładność w funkcji liczby, zbiór {\it hypothyroid}, klasyfikator C4.5}
%\label{fi:HypC45}
%\efig
%\vspace*{-1.2cm}
%\bfig
%\vspace*{-1cm}
%\epsfig{figure=pic/compBayes,width=9cm,height=6cm}
%\caption{Dokładność w funkcji liczby, zbiór {\it hypothyroid}, klasyfikator Naiwny Bayesowski}
%\label{fi:HypNB}
%\efig
%Kolejność uszeregowania cech dla zbioru {\it hypothyroid} przedstawiono w tabeli \reff{tab:HyperRank}, a wyniki klasyfikacji w zależności od liczby wybranych cech przedstawiają rysunki


\paragraph{Zbiorcze porównanie.}
Podobnie jak w przypadku oceny metod rankingowych posłużono się tutaj dwuetapowym procesem testowania. W części pierwszej dokonano selekcji cech w oparciu o algorytmy {\it selekcji w przód}, {\it selekcji w tył} stosując metodę opakowywania klasyfikatorem oraz metodę selekcji w oparciu o drzewa decyzji, a następnie w drugim kroku dokonano klasyfikacji w procesie dziesięciokrotnej walidacji krzyżowej. Zebrane wyniki dla algorytmu klasyfikacji CFCM+LVQ przedstawiono w tabeli \reff{tab:FeatureComp}, gdzie dodatkowo umieszczono informację o liczbie wybranych prototypów ($l$) oraz liczbie cech ($f$), przy czym dla każdej z metod optymalizowana była jedynie dokładność klasyfikacji.
\begin{table}
\begin{center}
\begin{footnotesize}
%\setlength{\tabcolsep}{3pt}
%\begin{tabular}{|l|r@{ $\pm$ }l|c|c|r@{ $\pm$ }l|c|c|r@{ $\pm$ }l|c|c|}
\begin{tabular}{|l|r@{ $\pm$ }l|c|c|r@{ $\pm$ }l|c|c|r@{ $\pm$ }l|c|c|}
\hline
&\multicolumn{4}{|c|}{Selekcja w tył}&\multicolumn{4}{|c|}{Selekcja w przód}&\multicolumn{4}{|c|}{Selekcja  drzewem}\\ \hline
Zbiór&\multicolumn{2}{|c|}{Dokładność}& $f$&l&\multicolumn{2}{|c|}{Dokładność}& $f$&l&\multicolumn{2}{|c|}{Dokładność}& $f$&l\\ \hline
Wyrostek rob.			&85.70    &13.98   &6    &2&		84.86&		14.38		&4		&2 & 84.86   &15.85   &2    &2 \\
Winorośl					&97.25    &2.90   &11    &3&		95.06&		4.79		&5		&7 &92.57    &6.05    &6    &3	\\
Cukrzyca					&77.22    &4.36    &7    &3&		76.96&		3.01		&4		&3 &75.65    &2.43    &2    &4	\\
Jonosfera				&87.81    &6.90   &32    &6&		92.10&		4.25		&5 	&6 &87.57    &7.11    &2    &4	\\
Choroby serca			&85.49    &5.59    &7    &3&		84.80&		5.23		&3		&2 &84.80    &5.23    &3    &2	\\
Irysy						&95.33    &6.32    &3    &5&		97.33&		3.44		&2		&4 &97.33    &3.44    &2    &4	\\
Sonar						&66.81    &20.66   &56   &4&		75.62&		12.97		&4		&3 &74.62    &12.40   &1    &2	\\
Choroby wątroby		&67.24    &8.79    &5    &2&		68.45&		6.40		&4		&2 &66.71    &9.05    &2    &2	\\
Rak piersi				&97.82    &1.96    &7    &3&		97.81&		2.19		&5		&3 &97.23    &2.51    &5    &4	\\
Lancet					&95.66    &2.36    &7    &4&		94.65&		2.64&		5&		4& 93.33    &3.20    &4   &3\\
\hline
\end{tabular}
\end{footnotesize}
\caption{Porównanie algorytmów selekcji cech dla algorytmu CFCM+LVQ}
\end{center}
\label{tab:FeatureComp}
\end{table}
Podobnego porównania dokonano również dla algorytmu OPTDL. W typ przypadku ze względu na złożoność obliczeniową algorytmów selekcji oraz klasyfikatora dokonano porównania metod selekcji bazujących na metodzie rankingowej, gdzie do oceny jakości cech posłużono się współczynnikiem korelacji oraz metody selekcji bazującej na drzewach decyzji. W porównaniu zastosowano dwie metody rankingowe typu {\it selekcja w przód} oraz {\it selekcja w tył} gdzie kolejne cechy dodawane są wg. wartości współczynnika rankingowego, aż do osiągnięcia pierwszego maksimum. Taka procedura dodatkowo ogranicza złożoność obliczeniową, jednakże powoduje, że osiągane są maksima lokalne. W tabeli tab.\reff{tab:FeatureComp-OPTDL} użyto identycznych oznaczeń jak w tab.\reff{tab:FeatureComp}.
\begin{table}
\begin{center}
\begin{footnotesize}
%\setlength{\tabcolsep}{3pt}
%\begin{tabular}{|l|r@{ $\pm$ }l|c|c|r@{ $\pm$ }l|c|c|r@{ $\pm$ }l|c|c|}
\begin{tabular}{|l|r@{ $\pm$ }l|c|c|r@{ $\pm$ }l|c|c|r@{ $\pm$ }l|c|c|}
\hline
&\multicolumn{4}{|c|}{Ranking w tył}&\multicolumn{4}{|c|}{Ranking w przód}&\multicolumn{4}{|c|}{Selekcja  drzewem}\\ \hline
Zbiór&\multicolumn{2}{|c|}{Dokładność}& $f$&l&\multicolumn{2}{|c|}{Dokładność}& $f$&l&\multicolumn{2}{|c|}{Dokładność}& $f$&l\\ \hline
Wyrostek rob.			&87.77    &9.68   & 6    &1&		87.77    &9.68    &6    &1 &81.88    &17.58   &2    &1 \\
Winorośl					&96.70    &4.67   &13    &5&		75.34    &11.45   &1    &3 &89.91    &8.47    &4    &5 \\
Cukrzyca					&76.43    &4.66   & 3    &4&		76.43    &4.66    &3    &4 &72.79    &5.43    &4    &1 \\
Jonosfera				&93.79    &4.30   &27    &5&		93.79    &4.30   &27    &5 &88.68    &4.83    &2    &1 \\
Choroby serca			&84.15    &5.58   & 3    &3&		84.15    &5.58    &3    &3 &84.15    &5.58    &3    &3 \\
Irysy						&98.00    &3.22   & 2    &2&		98.00    &3.22    &2    &2 &98.00    &3.22    &2    &2 \\
Sonar						&78.55    &15.71  & 13   &3&		78.55    &15.71  &13    &3 &73.17    &11.33   &1    &1 \\
Choroby wątroby		&59.36    &9.40   & 6    &5&		56.52    &9.06    &1    &1 &64.06    &4.96    &2    &4 \\
Rak piersi				&97.23    &2.10   & 9    &1&		91.96    &4.72    &1    &1 &96.35    &2.48    &5    &1 \\
Lancet					&94.35    &2.94   & 7    &3&		94.35    &2.94    &7    &3 &94.35    &1.63    &4    &3 \\
\hline
\end{tabular}
\end{footnotesize}
\caption{Porównanie algorytmów selekcji cech dla algorytmu OPTDL}
\end{center}
\label{tab:FeatureComp-OPTDL}
\end{table}

\paragraph{Podsumowanie wyników}
Przedstawione wyniki wskazują, iż dobór odpowiedniej metody selekcji cech jest niezmiernie istotny. Wyniki badań opublikowane w \cite{B-NIPS} oraz rezultaty konkursów selekcji cech \cite{Ch-Guyon-NIPS03} sugerują, że nie istnieje istotny związek pomiędzy typem klasyfikatora a odpowiednią metodą rankingową selekcji cech. Dlatego też podczas wyboru wskaźnika rankingowego można się kierować prostotą jego wyznaczenia (wskaźniki teorioinformacyjne wymagają wstępnej dyskretyzacji) lub powinien być realizowany w procesie meta uczenia.\\
 W przypadku reguł prototypowych dają się jednak zaobserwować pewne tendencje wynikające z konieczności znalezienia kompromisu pomiędzy dokładnością a złożonością modelu. Analiza załączonych wyników wskazuje, iż  metody {\it selekcji w przód} oraz {\it selekcji w tył} charakteryzują się największą dokładnością i przewyższa pozostałe metody. Należy jednak zwrócić uwagę na złożoność obliczeniową tych metod, jest ona rzędu !!!!!$XXXXXXX$!!!!! - powoduje to, że wykorzystanie ich w realnych problemach analizy danych jest ograniczone ze względu na koszt obliczeń. Ważnym podkreślenia jest również problem osiągania przez opisane metody ekstremów lokalnych (pierwszego napotkanego maksimum). Widać to porównując wyniki uzyskane dla zbioru {\it choroby wątroby} i algorytmu selekcji bazującego na drzewach decyzji, gdzie ta metoda selekcji dała lepsze rezultaty oraz mniejszą liczbę ostatecznie wybranych cech. Możliwością obejścia problemu ekstremów lokalnych są algorytmy przeszukiwania typu {\it dodaj $i$ odejmij $j$}, które jednak dodatkowo zwiększają złożoność obliczeniową.\\
Wady tej pozbawione są metody rankingowe, których zaletą jest niska złożoność obliczeniowa odpowiadająca liniowej zależności w funkcji liczby cech ($O(|\bf{f}|)$). Jednak metody te mogą być niestabilne w funkcji uzyskiwanej dokładności - obrazują to wykresy rys.\reff{fi:FS-RankCFCM-Io} i rys.\reff{fi:FS-RankCFCM-Cl} dla algorytmu CFCM+LVQ oraz rys.\reff{fi:FS-RankOPTDL-Io} i rys.\reff{fi:FS-RankCFCM-Cl} dla algorytmu OPTDL. Uzyskane wyniki dla metod rankingowych nie pozwalają na jednoznaczne wyłonienie najlepszego wskaźnika, dlatego też propozycją rozwiązania są komitety metod rankingowych, w których o wadze danej cechy decyduje częstość jej występowania na określonej pozycji. Na uwagę zasługuje również duża skuteczność wskaźnika rankingowego, jakim jest współczynnik korelacji. Wśród jego zalet należy zaznaczyć niski koszt jego wyznaczenia oraz niezależność od problemu estymacji prawdopodobieństwa.\\
Rozwiązaniem kompromisowym wydaje się być selekcja cech wykorzystująca metodę drzew decyzji. Cechuje się ona umiarkowaną złożonością obliczeniową !!!!!!$XXXXXO(|\bf{f}|\log|\bf{f}|)$!!!!!, a jednocześnie w miarę dobrymi rezultatami selekcji.\\
Metodą łączącą zalety algorytmów drzew decyzji oraz algorytmów przeszukiwania jest łączenie różnych metody selekcji. Przykładowym rozwiązaniem jest tutaj dwuetapowy proces selekcji, gdzie w pierwszym kroku wybierany jest początkowy podzbiór cech, realizowany poprzez metodę selekcji w oparciu o drzewa decyzji, a następnie, w drugim kroku selekcja w przód dodająca do wybranego podzbioru cechy maksymalizujące dokładność lub też wybór cech na podstawie drzewa nie przyciętego (pełnego) a następnie usuwanie nieistotnych cech zgodnie z algorytmem selekcji w tył. Algorytmy te wymagają jednak przeprowadzenia dalszych badań. 


%=============================================================================================

\section{Meta uczenie} \label{sec:MetaLearning}
Meta uczenie można podzielić na dwa niezależne problemy - selekcję optymalnych parametrów modelu oraz selekcję optymalnego algorytmu uczenia. W pierwszy przypadku dążymy do dobrania optymalnych hiperparametrów modelu, które maksymalizują daną funkcję kryterialną - takimi parametrami mogą być współczynnik uczenia czy też rodzaj funkcji odległości.  Problem selekcji modelu to problem doboru najlepszego algorytmu uczenia (np. problem doboru najlepszej metody selekcji prototypów lub typu reguł-P) oraz odpowiednich transformacji danych.\\
W szczególności meta uczenie obejmuje również zagadnienie oceny jakości modelu, strategię poszukiwania optymalnego algorytmu oraz problem redukcji złożoności obliczeniowej.
%--------------------------------------------------------------------------------------------
\subsection{Metody oceny modelu}
\subsubsection{Szacowanie jakości modelu}
Jednym z istotnych problemów jest ocena jakości zbudowanego modelu. Ogólnie istnieje wiele podejść do tego zagadnienia m.in. przedstawione w  \cite{B-Duda-Hart}. Najbardziej trywialnym jest testowanie modelu bazujące na dwóch różnych zbiorach - treningowym, używanym do uczenia modelu i testowym, oceniającym jakości modelu. Takie rozwiązanie ma wiele wad. Jego poważnym ograniczeniem jest zależność uzyskanych wyników od podziału na część treningową i testową, co w znaczny sposób zafałszowuje prawdziwe możliwości modelu. Jedyną możliwością w miarę rzetelnej oceny przy wykorzystaniu podziału trening/test jest analiza danych o znanym rozkładzie prawdopodobieństwa (np. w celach porównawczych różnych metod) - gdzie możliwe jest stworzenie zbioru testowego o rozmiarze znacznie przekraczającym rozmiar zbioru treningowego ($m_{test}\gg m_{train}$). \\
Metodą najpowszechniej stosowaną w problematyce oceny jakości modelu jest $k$-krotna walidacja krzyżowa (ang. k-fold cross validation), występująca w dwóch odmianach. Proces walidacji polega tu na podziale zbioru treningowego $\BT$ na $k$ równych części, gdzie system uczony jest $k$-krotnie na $k-1$ częściach, a testowany na pozostałej jednej części zbioru $\BT$. W każdej iteracji następuje zmiana części testującej, tak że w rezultacie system testowany jest na wszystkich wektorach zbioru treningowego. Poszczególne odmiany $k$-krotnej walidacji krzyżowej różnią się tym, iż w przypadku walidacji stratyfikowanej dąży się do tego, by zapewnić stały rozkład prawdopodobieństwa występowania klas w każdej z $k$ części. Pomiar dokładności klasyfikacji w przypadku walidacji krzyżowej liczony jest jako średnia dokładność dla każdego z $k$ procesów. \\
Problem który występuje w przypadku walidacji krzyżowej to dobór odpowiedniej wartości $k$. Mała wartość $k$ pozwala na bardziej rzetelną ocenę pojedynczej walidacji, gdyż stosunek części walidującej do uczącej jest stosunkowo duży. Rozwiązanie takie zmniejsza jednak ilość powtórzeń procesu uczenia, co negatywnie wpływa na jakość oceny wartości średniej. Należy również zauważyć kolejny problem, jakim jest reprezentatywność danych uczących. Małe wartości $k$ mogą doprowadzić do sytuacji, gdzie pewne drobne, acz istotne obszary będą mało licznie reprezentowane w części uczącej, co może doprowadzić do ich pominięcia. Problem ten nie występuje dla dużych wartości $k$, gdzie dodatkowo poprawia się jakość oceny wartości średniej. Nie należy jednak zapominać o wadzie metody, jaką jest wzrost złożoności obliczeniowej, co może w znacznym stopniu ograniczać praktyczne aplikacje (najczęściej przyjmuje się $k=10$). Skrajnym przypadkiem walidacji krzyżowej jest test {\it jeden pozostaw} (ang. leave one out), gdzie system testowany jest $m$-krotnie zawsze na pojedynczym wektorze. W literaturze dowodzi się, że test ten jest ,,niemal'' nieobciążony \cite{B-Scholkopf-Kernels}, jednakże na uwagę zasługuje fakt, iż nie pozwala on na wyznaczenie wariancji modelu, którą łatwo daje się wyliczyć w przypadku $k \ll n$ jako odchylenie standardowe wyników uzyskanych w poszczególnych walidacjach. Informacja taka może być bardzo istotna, dając dodatkowe wskazówki o zbudowanym modelu. \\
Rozwinięciem testu walidacji krzyżowej jest test, w którym proces walidacji krzyżowej powtarzany jest wielokrotnie (tak zwany X-test). Dzięki takiemu rozwiązaniu zwiększa się liczba prób pojedynczych ocen, jednocześnie uniezależniając się od losowości podziału na $k$ podzbiorów, co ma szczególne znaczenie dla małych zbiorów danych.\\
W literaturze spotykane są również inne metody selekcji modelu, jak bazujące na teorii Bayesowskiej \cite{S-Seeger-BayesModelSel,S-Scholkopf-IntroKernel}. W metodzie tej zakłada się, że parametry modelu takie, jak współczynniki uczenia, stopień metryki $L$ są traktowane - podobnie jak cechy zbioru uczącego - jako zmienne losowe poddając je analizie Bayesowskiej. Jednak przeprowadzone testy empiryczne wskazują, że dla małych zbiorów danych ze względu na problem estymacji prawdopodobieństwa możliwe jest występowanie błędów tej metody.\\
Bardzo dobrą metodą testowania modelu jest tak zwany {\it Bootsrtaping} lub test {\it Monte Carlo} \cite{B-Duda-Hart}, który polega na wielokrotnym losowaniu zarówno części uczącej, jak i testującej ze zwracaniem. Takie rozwiązanie powoduje bardziej naturalny (zbliżony do rzeczywistego) rozkład danych w obydwu zbiorach, jednakże wymagane jest, by proces podziału na część treningową i testową realizowany był wielokrotnie. Niestety determinuje to bardzo dużą złożoność obliczeniową tej metody. Jest ona szczególnie często stosowana w przypadkach małolicznych zbiorów danych, dla których metody walidacji krzyżowej nie dają zadowalających efektów.  
%-----------------------------------------------------------------------------------------
\subsubsection{Wybór najlepszego modelu}
Omówione powyżej metody weryfikacji jakości modelu pozwalają na estymację jego dokładności, liczoną najczęściej jako średnią z uzyskanych wyników walidacji (dla metod walidacji krzyżowej oraz bootstrap). Jednak ocena i wybór modelu na podstawie jedynie wartości średniej dokładności $\overline{\acc}$ obarczona może być błędem, gdyż tym sposobem nie jest uwzględniania wariancja modelu. Wariancja modelu może być natomiast interpretowana jako wariancja uzyskanych wyników dokładności. Przeprowadzone testy wskazują, iż wpływ wariancji jest bardzo istotny, gdyż średnia dokładność nie uwzględnia rozrzutu wartości dokładności poszczególnych walidacji. Ma to również istotny wpływ na stabilizację wyników szacowania. \\
Do wyboru najlepszego modelu niezbędne jest więc porównanie zarówno wartości średniej z różnych walidacji, jak i jej odchylenia standardowego. Można w tym celu posłużyć się różnymi testami statystycznymi, jednak najprostszą formą jest analiza dokładności zdefiniowana jako \reff{eq:acc-std}. 
\be \label{eq:acc-std} \overline{\acc}-std \ee
Metoda ta pozwala na wybór modelu na podstawie pesymistycznego oszacowania dokładności. Stanowi ona w pewnym sensie uproszczenie testu T-Studenta dla średnich z próby.

%------------------------------------------------------------------------------------------

\subsection{Metody przeszukiwania}
Podobnie jak w przypadku selekcji prototypów oraz selekcji cech, również w przypadku selekcji modelu największą popularnością cieszą się metody przeszukiwania. Jednakże z uwagi na konieczność optymalizacji wielu parametrów modeli selekcji cech, proces ten staje się bardzo zachłanny obliczeniowo.  
%\bfig \label{fi:MetaLearnBasic}
%\begin{flushleft}
%function $BM$=MetaLearning($\BT,\bf{sM},\bf{sFT}$)
%input:\\
%\tab    $\BT$ - zbiór uczący\\
%\tab    $\bf{sM}$ - zbiór metod klasyfikacji (np. różne wartości współczynników uczenia dla algoytmu LVQ)\\
%\tab    $\bf{sFT}$ - zbiór metod transformacji danych (np. różne algorytmy selekcji cech)
%output:\\
%\tab    $BM$ - najlepszy model\\
%var
%\tab    $M$ - obecnie testowany model\\
%\tab    $FS$ - obecnie używany model transformacji danych\\
%begin \\
%\tab for i=1 \ldots size(${\bf sM}$) //dla każdego klasyfikatora\\%
%\tab \tab for j=1 \ldots size(${\bf sFT}$) //dla każdego transformera danych\\%
%\tab \tab \tab $M$=buildmodel($\BT,{ \bf sM}(i),{\bf sFT}(j)$); //utwórz aktualny model z klasyfikatora i transformera\\
%\tab \tab \tab $cacc$=validate($M$); //przetestuj model\\
%\tab \tab \tab if $acc>cacc$ then $BM$=${\bf sFT}_j + {\bf sM}_i; acc=cacc$\\ 
%\tab \tab end;\\
%\tab end;\\
%\tab return $BM$ //zwróć najlepszy model\\
%\end{flushleft}
%\caption{Przykładowy podstawowy algorytm meta-uczenia}%
%\efig %
%
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, 
	\REQUIRE ${\bf M}$ \COMMENT{Zbiór klasyfikatorów}
	\REQUIRE ${\bf S}$ \COMMENT{Zbiór metod selekcji cech}
	\STATE $k \leftarrow {\rm sizeof}({\bf M})$
	\STATE $t \leftarrow {\rm sizeof}({\bf S})$
	\STATE $acc \leftarrow 0$
	\FOR{j=1\ldots k}
		\FOR{$i=1\ldots t$}
			\STATE $tacc \leftarrow {\rm Validate}([S_i,M_j],\BT)$
			\IF{$tacc>acc$}
				\STATE $acc \leftarrow tacc$
				\STATE $S' \leftarrow S_i$
				\STATE $M' \leftarrow M_j$
			\ENDIF
		\ENDFOR
	\ENDFOR 
	\RETURN $M'$, $S'$
\end{algorithmic}
	\label{fi:MetaLearnBasic}
	\caption{Przykładowy algorytm meta-uczenia}
\end{algorithm}
%
Główną wadą przestawionego na schemacie \reff{fi:MetaLearnBasic} algorytmu jest zagnieżdżenie jednego procesu przeszukiwania w drugim. Przykładem takiego zjawiska może być selekcja cech połączona z selekcją prototypów, gdzie obydwa zadania realizowane są przez proces szukania. Dlatego też konieczne staje się rozważenie algorytmów przyspieszających i upraszczających, redukując również złożoność obliczeniową procesu przeszukiwania. \\
\paragraph{Strategia 1}
Jedną z możliwości poprawy jest wykorzystanie metody filtrów w selekcji cech (np. poprzez użycie drzew decyzji), dzięki czemu procesy selekcji cech i optymalizacji parametrów modelu stają się niezależne, znacznie redukując złożoność obliczeniową w porównaniu np. do metod opakowujących.\\
\paragraph{Strategia 2}
Inną możliwością jest rozpoczęcie procesu uczenia od optymalizacji parametrów modelu realizowanego na całym zbiorze danych lub po uprzedniej selekcji cech zrealizowanej w oparciu o metody filtrów (strategia 1). W kolejnym kroku  następuje proces selekcji cech metodami opakowującymi, algorytmem selekcji w tył, usuwając jedynie te cechy, które psują dokładność danego modelu.
\paragraph{Strategia 3}
Ostatnie proponowane rozwiązanie wykorzystuje możliwości algorytmów uczenia, bazujących na metodach optymalizacji gradientowej posiadających zdolność douczania. W przypadku reguł prototypowych dotyczy to algorytmu LVQ, który pozwala na rozszerzenie strategii 2. W metodzie tej, po każdym usunięciu cechy następuje douczenie systemu poprzez kilka iteracji algorytmu LVQ1 bądź LVQ2.x. Dzięki takiemu rozwiązaniu znacznie skraca się czas uczenia modelu, co sprzyja dalszej optymalizacji. Ponadto douczanie modelu bazuje na wykorzystaniu uprzednio zdobytej wiedzy, co wpływa  na jakość uzyskanych rezultatów pomijając problem inicjalizacji.
%---------------------------------------------------------------------------------------------
\subsection{Redukcja złożoności obliczeniowej w metodach walidacji krzyżowej oraz Bootstrap}
Bardzo ciekawą metodę redukcji złożoności obliczeniowej zaproponowali w swojej pracy Maron and Moore
\cite{Maron-RacingModelSel}. W swych badaniach analizowali oni możliwość skrócenia procesu obliczeniowego poprzez zaprzestanie walidacji modelu, który jest znacząco gorszy od aktualnie najlepszego. Ich algorytm wykorzystywał statystykę T-Studenta do oceny wyników w kolejnych krokach $k$-krotnej walidacji krzyżowej. Jeżeli aktualnie analizowany model po $s$ krokach, gdzie $s<k$, wykazywał istotnie gorsze wyniki niż najlepszy z dotychczasowych modeli, proces walidacji zostawał wstrzymany, a aktualny model wycofany jako  bezużyteczny.
