msc-michal-maciaszek/Podstawy_teoretyczne.tex

\chapter{Podstawy teoretyczne}
\section{Uczenie maszynowe i jego rodzaje}
\subsection{O uczeniu maszynowym}
Jedną z definicji, dobrze oddającą charakter uczenia maszynowego, możemy znaleźć w pracy ,,An overview of Machine Learning and its Applications'': Uczenie maszynowe [...] to dział informatyki, który wyewoluował z~rozpoznawania wzorców i~teorii uczenia obliczeniowego w sztucznej inteligencji. To uczenie i~budowanie algorytmów, które uczą się i~tworzą predykcje na podstawie zbiorów danych.''\cite{Overview}

Uczenie maszynowe (ang. \emph{machine learning}) to jeden z~najważniejszych współcześnie działów informatyki. Wykorzystuje ono dostarczane dane empiryczne do tworzenia modeli predykcyjnych. Modele uczenia maszynowego stają się integralną częścią otaczającego nas świata, są wykorzystywane w~coraz szerszej gamie aplikacji. Wraz ze wzrostem użytku uczenia maszynowego, wzrasta potrzeba tworzenia coraz lepiej działających i~szybciej uczących się modeli.

\subsubsection{Podział na uczenie nadzorowane, nienadzorowane i ze wzmacnianiem}
Algorytmy uczenia maszynowego możemy wyróżnić według różnych kryteriów. Jednym ze sposobów jest podział biorący pod uwagę rodzaj wykorzystywanych danych i~informacji, jakie są w nich zawarte. Biorąc pod uwagę to kryterium możemy wyszczególnić trzy typy:

\subsubsection{Uczenie nadzorowane}
W uczeniu nadzorowanym dane treningowe składają się z~par: wejściowego obiektu uczącego (wektora $X$) i~pożądanej odpowiedzi (etykiety) $Y$. Celem nauki jest znalezienie takiej reguły, która odpowiednio mapuje wejścia do wyjść.


\[Y = f(X)\]


Na podstawie takiej funkcji mapującej, kiedy otrzymamy nowe dane jesteśmy w~stanie przewidzieć ich etykietę.

Typowymi problemami dla uczenia nadzorowanego są:
\begin{itemize}
\item regresja - przewidywana odpowiedź (etykieta) przedstawiana jest za pomocą liczby rzeczywistej. Przykładowym zadaniem regresji może być np. przewidywanie ceny akcji na giełdzie (za wektor cech przyjmując ceny pozostałych akcji),
\item klasyfikacja - przewidywana jest klasa danego obiektu w~postaci wartości dyskretnej. Typowym zadaniem klasyfikacji jest wykrywanie spamu.
\end{itemize}
Przykładami algorytmów reprezentujących uczenie nadzorowane są:
\begin{itemize}
\item regresja logistyczna,
\item drzewa decyzyjne,
\item regresja liniowa,
\item maszyna wektorów nośnych.
\end{itemize}



\subsubsection{Uczenie nienadzorowane}
W uczeniu nienadzorowanym dostarczone dane są nieetykietowane, a~zadaniem algorytmów jest wyszukiwanie wzorców i~struktur wśród danych. Model próbuje się wyuczyć bez żadnej metody nadzorującej. Przykładowymi zadaniami takiego modelu mogą być analiza skupień czy analiza składowych głównych.

\subsubsection{Uczenie ze wzmacnianiem}
W uczeniu ze wzmacnianiem (w odróżnieniu od uczenia nadzorowanego i~nienadzorowanego) modelowi nie przygotowuje się danych. Zamiast tego, przygotowywane jest (potencjalnie złożone) środowisko, z~którego model automatycznie pobiera dane. Takie podejście oparte jest na metodzie prób i~błędów. Zadaniem programisty tworzącego model, jest utworzenie systemu nagród i~kar, na podstawie których model będzie podejmował decyzje (jego celem jest zmaksymalizowanie nagród). Poza tym człowiek nie daje żadnych wskazówek ani sugestii jak wykonać zadanie. To zadaniem modelu jest wymyślenie, jak wykonywać zadanie, aby otrzymywać jak największe nagrody; zaczynając od całkowicie losowych prób po bardzo złożone rozwiązania.

\subsubsection{Podział na uczenie wsadowe i strumieniowe}
Innym sposobem klasyfikacji algorytmów uczenia maszynowego jest podział na uczenie wsadowe i~strumieniowe.

Podczas trenowania wsadowego model uczony jest na wszystkich dostępnych w~danej chwili danych (ang.  \emph{batch learning}). Zwykle trenowanie modelu w~taki sposób zajmuje dużo czasu i~pochłania olbrzymie ilości zasobów -- z~tego powodu takie modele są zwykle trenowane w trybie offline. W przypadku gdybyśmy chcieli przystosować model do nowych danych (np. przystosować do rozpoznawania nowego typu spamu), musielibyśmy wyuczyć nowy model, a~następnie umieścić go w systemie w miejsce starego.

Upraszczając możemy więc powiedzieć, że przy uczeniu wsadowym, żeby douczyć model, należy go trenować w całości od nowa.

Przeciwnym podejściem do uczenia wsadowego jest uczenie strumieniowe (zwane także inkrementalnym). Algorytmy strumieniowe pozwalają na douczanie już wytrenowanego modelu, stąd znacznie częściej wykorzystywane są one podczas uczenia w trybie online.

W algorytmach strumieniowych model uczony jest na każdej próbce po kolei, a~wagi poszczególnych cech uaktualniane są na każdym kroku. Pośrednim rozwiązaniem pomiędzy oboma trybami jest uczenie na mniejszych grupkach danych (ang. \emph{mini batches}), jednak z~powodu możliwości douczania takich modeli, rozwiązanie to może być zaliczane do trybu strumieniowego.

Uczenie strumieniowe doskonale nadaje się do systemów, w~których dane dostarczane są w~sposób ciągły, a~ten musi adaptować się do zmieniającej się sytuacji. Dodatkową zaletą jest brak potrzeby przetrzymywania danych, z~których model już się nauczył. Algorytmy takie uczą się zwykle szybciej -- aktualizacja modelu następuje po każdej próbce.

Warto jednak zwrócić uwagę, że niektóre algorytmy uczenia maszynowego można zakwalifikować do jednego z dwóch trybów zależnie od użytej funkcji optymalizacji. Przykładowo regresja logistyczna działa w trybie strumieniowym, gdy użyty jest stochastyczny spadek gradientu, natomiast w trybie wsadowym używamy spadku gradientu (optymalizacji dla wszystkich próbek). Podobna sytuacja występuje w przypadku drzew Hoeffdinga, będących inkrementalną odmianą drzew decyzyjnych.



\subsection{Wsadowe algorytmy uczenia maszynowego}
\subsubsection{Regresja logistyczna}
Regresja logistyczna jest jedną z metod statystycznych, skupiającą się na analizie niezależnych zmiennych. Za pomocą funkcji sigmoidalnej (logistycznej), model oblicza prawdopodobieństwo, że próbka należy do jednej z~klas. Trening modelu polega na wyznaczeniu sigmoidy, która najlepiej odzwierciedlałaby dane. Regresja logistyczna zwykle jest używana do analizy zmiennych, które determinują wynik znajdujący się na skali dychotomicznej, ale może być także używana do rozwiązywania problemów wieloklasowych.

\begin{figure}
  \caption{Przykład funkcji sigmoidalnej}
  \label{wykres_regresji}
    \includegraphics[scale=0.65]{Images/log-reg-sigmoid.png}
\end{figure}

Wykres \ref{wykres_regresji} reprezentuje przykładową funkcję sigmoidalną. Wzór takiej funkcji ma postać:
\begin{displaymath}
y(x) = 1 / (1 + e ^{-x})
\end{displaymath}
gdzie $x$ jest wartością liczbową powstałą z~iloczynu wag i~wartości cech (plus obciążenie - ang. \emph{bias}). Wartości wag są dopasowywane w~trakcie treningu modelu za pomocą algorytmu optymalizacyjnego, który stara się zminimalizować funkcję straty.

Z założenia funkcja logistyczna może być trenowana zarówno w trybie wsadowym i~strumieniowym. Wybór odpowiedniego algorytmu optymalizacji przystosowuje funkcję do nauki w~jednym z tych trybów. Użycie algorytmu Spadku Gradientu (ang. \emph{Gradient Descent}) zwykle używane jest przy wsadowym trybie nauki. Bierzemy wtedy pod uwagę błędy dla wszystkich próbek danych przy każdej iteracji podczas aktualizowania wag --- stąd też szersza nazwa Batch Stochastic Gradient. Przy dużych zbiorach danych może się jednak zdarzyć, że czas aktualizacji w tym trybie będzie zbyt długi.

\subsubsection{Drzewa decyzyjne}

Drzewa decyzyjne są kolejnym modelem, który w zależności od implementacji może występować w trybie wsadowym i strumieniowym. W tym modelu węzły reprezentują testy na cechach (np. ,,czy na niebie są chmury''), gałęzie wyniki tych testów (,,są chmury'' lub ,,nie ma chmur''), a~liść etykietę klasy (,będzie padać''/,,nie będzie'').

\begin{figure}
\centering
  \caption{Przykład prostego drzewa decyzyjnego}
\includegraphics{Images/Small_tree.png}
\end{figure}

Aby opisać działanie tych algorytmów musimy zdefiniować jedną z istotnych ich właściwości:

Miara czystości - jest to wybrana metryka, która pozwala na odnalezienie ,,najlepszego'' (najbardziej optymalnego) podziału danych w drzewie. Co w danym przypadku oznacza ,,najlepszy'' podział, będzie zależało od użytego algorytmu. 

Przykładem może być takiej miary jest miara zanieczyszczeń Giniego. 

Miarę zanieczyszczeń Giniego możemy przedstawić wzorem:
\begin{displaymath}
Gini = \sum_{i=1}^J P(i) * (1 - P(i))
\end{displaymath}
gdzie P(i) jest prawdopodobieństwem pewnej klasyfikacji i.


Większość algorytmów, przy pomocy których tworzone są drzewa decyzyjne, wykorzystuje strategię TDIDT \cite{drzewadecyzyjne}, czyli strategię ,,z~góry na dół'' (ang. \emph{top down induction of decision trees}), opartą na zasadzie ,,dziel i~rządź''. Taką strategię w~skrócie można opisać w dany sposób:
\begin{enumerate}
\item Na wejście przyjmij cały zbiór danych
\item Znajdź taki podział danych na podstawie atrybuty, która zmaksymalizuje przybraną miarę czystości
\item Dokonaj podziału na danych wejściowych (tworząc nowe zbiory)
\item Powtarzaj kroki 1 i~2 na nowych zbiorach.
\item Przytnij drzewo, aby uniknąć przeuczania.
\end{enumerate}

Różne implementacje drzew decyzyjnych będą wykorzystywały inne metody znalezienia najlepszego podziału, metryki i~stosowały (bądź nie) przycinanie drzewa. Najpopularniejszymi implementacjami są:

\begin{itemize} 
\item ID3 (\emph{Iterative Dichotomiser 3}),
\item C4.5 (następca ID3),
\item CART (\emph{Classification And Regression Tree}).
\end{itemize} 


\subsubsection{Maszyny wektorów nośnych}
Algorytm SVM (ang. \emph{support vector machines}) jest wydajnym i~szybkim algorytmem używanym głównie do zadań klasyfikacji (ale także regresji). Oparty jest na odnajdywaniu hiperprzestrzeni, która najlepiej dzieliłaby dane na dwie (lub więcej) klasy. 

Wektorami nośnymi nazywane są współrzędne pojedynczych obserwacji znajdujące się najbliżej hiperpłaszczyzny, których usunięcie spowodowałoby przesunięcie pozycji dzielącej dane hiperpłaszczyzny.

W dwuwymiarowym modelu (czyli na przykład takim, w którym dane opisane są za pomocą tylko dwóch cech) możemy opisać hiperpłaszczyznę jako linię, która dzieli dane na dwie części. Im dalej od linii znajdowałyby się dane, tym pewniejsi możemy być, że dane zostały poprawnie sklasyfikowane. Celem algorytmów SVM jest znalezienie takiej hiperpłaszczyzny, która maksymalizuje odległość do najbliższej obserwacji danych z~każdej klasy.

\subsection{Strumieniowe algorytmy uczenia maszynowego}

\subsubsection{Stochastyczny spadek gradientu}
O ile stochastyczny spadek gradient nie jest bezpośrednio algorytmem uczenia maszynowego; jest on metodą optymalizacji, która pozwala wielu algorytmom na działanie w trybie strumieniowym

Wykorzystując wsadową implementację spadku gradientu, podczas obliczania kolejnych gradientów, wykorzystujemy wszystkie dostępne próbki. Obliczanie pochodnych od funkcji straty (TODO - może wyjaśnić to przy regresji logistycznej) dla wielu próbek może być bardzo czasochłonne. Z tego powodu wykorzystujemy stochastyczną (strumieniową) implementację. Wybierana jest losowa próbka (lub po prostu kolejna, gdy model jest douczany), następnie obliczana jest wartość kroku, o jaką musimy dopasować wagi parametrów funkcji.

Warto zwrócić uwagę na to, że pomimo zmniejszenia liczby obliczeń potrzebnych do wykonania kroku, samych kroków (dopasowań modelu) zwykle będzie znacznie więcej. Z tego powodu model często dostosowuje się do nauki przy pomocy pewnych mniejszych zbiorów próbek (ang. \emph{mini-batch}), co pozwala zachować optymalną ilość potrzebnych obliczeń.

\subsubsection{Perceptron}
Perceptron jest przykładem najprostszej sieci neuronowej, składającej się z~jednego lub więcej neuronów. Zwykle używając pojęcia perceptronu, bierze się pod uwagę perceptron z jedną warstwą ukrytą (wielowarstwowy perceptron określany jest już terminem bardziej złożonej jednokierunkowej sieci neuronowej). 

Sztuczny neuron jest matematyczną funkcją opartą na modelu biologicznego neuronu. Każdy taki neuron przyjmuje pewne dane na wejście, nadaje im wagi, sumuje, a następnie przekazuje tę sumę do funkcji aktywacji aby utworzyć pewne wyjście. Rolę funkcji aktywacji mogą przyjmować na przykład: funkcja logistyczna, liniowa czy progowa.

Dla perceptronu (zwłaszcza wielowarstwowego) proces nauczania oparty najczęściej jest na metodzie wstecznej propagacji błędu.

\subsubsection{Drzewa Hoeffdinga}
Drzewa Hoeffdinga są inkrementalną implementacją algorytmu drzew decyzyjnych; zamiast używać do nauki wiele razy tych samych danych, algorytm korzysta z pojawiających się nowych przykładów. Są zdolne do nauki na olbrzymich ilości danych, zakładając, że ich dystrybucja nie zmienia się znacząco w czasie. 

Podobnie jak w rozwiązaniu wsadowym --- raz utworzony węzeł nie może już zostać zmieniony, nie wykazują więc odporności na tzw. \emph{concept drift}. Drzewa Hoeffdinga --- tak jak w klasycznych rozwiązaniach --- opierają algorytm swojej budowy na podziale atrybutów. W~odróżnieniu od algorytmu wsadowego zakładają, że nawet mała próbka wystarcza, aby wybrać odpowiednie atrybuty do podziału. \cite{Srimani2015PerformanceAO}

Algorytm zakłada wykorzystanie granicy Hoeffdinga do zagwarantowania jak najbardziej optymalnego wyboru atrybutu podziału. Wzór na obliczenie granicy Hoeffdinga przedstawia się następująco:

\begin{displaymath}
\epsilon = \sqrt{ \frac{R^{2} ln(1/\delta)}{2n} }
\end{displaymath}
gdzie:

$R$ - zakres wartości estymowanej funkcji,

\textdelta  - dopuszczalny błąd estymacji (wprowadzany ręcznie),

$n$ - rozmiar próbki.

Wzór ten pozwala wyznaczyć liczbę przykładów niezbędnych do uzyskania najlepszego podziału na każdym węźle. \cite{Jagirdar2018OnlineML}


\subsubsection{Passive Aggresive Clasifier}
Klasyfikator pasywno agresywny (ang. \emph{Passive Aggresive Clasifier}) jest jednym z~algorytmów często używanych podczas nauki na dużych zbiorach danych. Podobnie jak w przypadku perceptronu, nie wykorzystywany jest tutaj współczynnik uczenia. Używany natomiast jest parametr regularyzacji, mówiący jak dużą karę będzie otrzymywał model za niepoprawną predykcję.

Nazwa algorytmu, pochodzi od jego sposobu nauki:
\begin{itemize}
\item \emph{passive} - jeżeli predykcja jest poprawna, nie zmieniaj nic w modelu,
\item \emph{aggresive} - jeżeli predykcja jest niepoprawna, dokonaj zmian w modelu.
\end{itemize}

Warto zwrócić uwagę, że przez taką strategię nauki, wagi mogą być bardzo dynamicznie zmieniane, reagując na niepoprawne predykcje. Może to prowadzić zmiany wektora wag w niepoprawnych kierunku, ignorując prawidłowe predykcje.

\subsection{Metody ewaluacji algorytmów uczenia maszynowego}

Istotną częścią tworzenia modeli i~analizy ich predykcji jest odpowiednia ewaluacja. Dobór odpowiednich metryk ewaluacji jest kluczowy w~ocenie predykcji modelu -- skupiając się na konkretnej metryce, możemy trenować model w~kierunku konkretnych zastosowań. Poniżej zostaną przedstawione metody i~metryki stosowane podczas ewaluacji modelu.

\subsubsection{Przetrzymanie}
Przetrzymanie  (ang. \emph{hold-out}) - polega na jednokrotnym podziale zbioru na zbiory treningowy i~testowy. Zwykle podziału dokonuje się w proporcji $2/3$ i~$1/3$ (ewentualnie 80\% i 20\%). W~zależności jednak od rozmiaru danych, potrzeby dokładniejszej ewaluacji bądź dłuższego treningu; proporcje te mogą być zmieniane.

\subsubsection{Ocena krzyżowa}

Ocena krzyżowa (ang. \emph{cross validation}) polega na podziale zbiorów na $k$ części (stąd często używana nazwa ,,ocena krzyżowa na k-częściach''). Jedna z~części używana jest jako zbiór testowy, pozostałe odgrywają rolę zbioru treningowego. Trening i ewaluacja powtarzane są $k$ razy, za każdym razem zmieniając zbiór testowy, aż każdy z~nich zostanie wykorzystany w tej roli. Końcowy wynik często jest po prostu średnią z~każdej ewaluacji, natomiast takie badanie pozwala na sprawdzanie odchyłu od średniej, dlatego zapisuje się wyniki z~każdej ewaluacji. Przykładowa ocena krzyżowa została przedstawiona na rysunku \ref{fig:crossval}.


\begin{figure}[H]
\centering
\caption[what]{Przykładowa ocena krzyżowa na $k$ częściach \footnotemark}
\includegraphics[scale=0.2]{Images/cross.jpeg}
\label{fig:crossval}
\end{figure}
\footnotetext{\url{https://medium.com/@eijaz/holdout-vs-cross-validation-in-machine-learning-7637112d3f8f.}}

\subsubsection{Macierz pomyłek}

Macierz pomyłek (ang. \emph{confusion matrix}) jest macierzą o~rozmiarze dwa na dwa używaną podczas klasyfikacji. Na jednej osi (zwykle poziomej) przedstawiona jest właściwa wartość próbek, a~na drugiej (pionowej) wartość przewidziana przez klasyfikator. Przykładowa macierz przedstawiona jest na rysunku \ref{fig:confus}.

\begin{figure}[H]
\caption[frog]{Macierz pomyłek \footnotemark}
\includegraphics[scale=0.6]{Images/confus.png}
\label{fig:confus}
\end{figure}
\footnotetext{\url{https://towardsdatascience.com/performance-metrics-confusion-matrix-precision-recall-and-f1-score-a8fe076a2262}}


W takiej macierzy możemy wyróżnić wartości:
\begin{itemize}
    \item prawdziwie negatywne (TF - \emph{True False}) - model prawidłowo przewidział negatywną klasę,
    \item prawdziwie pozytywne (TP - \emph{True Positive}) - model prawidłowo przewidział pozytywną klasę (obie wartości są pozytywne),
    \item fałszywie negatywne (FN - \emph{False Negative}) - model nieprawidłowo przewidział wartość negatywnej klasy,
    \item fałszywe pozytywne (FP - \emph{False Positive}) - model nieprawidłowo przewidział wartość negatywnej klasy.
\end{itemize}

\subsubsection{Dokładność}
Dokładność (ang. \emph{accuracy}) - przedstawia liczbę prawidłowo przewidzianych predykcji podzieloną przez liczbę wszystkich predykcji. Dobrze spisuje się przy ocenianiu zbalansowanych klas, ale przy znacznej przewadze jednej z klas może prowadzić do nieprawidłowej interpretacji skuteczności modelu. Za pomocą macierzy pomyłek możemy określić ją wzorem:
\begin{displaymath}
Accuracy = \frac {TP + TN}{TP + FP + TN + FN}
\end{displaymath}

\subsubsection{Precyzja}
Precyzja (ang. \emph{precision}) - za jej pomocą możemy sprawdzić ile spośród poprawnie przewidzianych pozytywnie klas w rzeczywistości jest pozytywne. Przedstawiamy ją wzorem:
\begin{displaymath}
Precision = \frac {TP} {TP + FP}
\end{displaymath}

\subsubsection{Zwrot}
Zwrot (ang. \emph{recall}) - nazywany jest też czułością. Pozwala zmierzyć ile sklasyfikowano pozytywnie przykładów względem wszystkich przykładów prawdziwie pozytywnych. Metryka ta jest szczególnie istotna, kiedy klas pozytywnych jest mało i~zależy nam na poprawnym jej wykryciu.
\begin{displaymath}
Recall = \frac {TP} {TP + FN}
\end{displaymath}

\subsubsection{\emph{Miara F1}}
Miara ta przedstawia średnią harmoniczną precyzji i zwrotu. Istotne jest używanie tej metryki podczas badania niezbalansowanych zbiorów danych.

\begin{displaymath}
F1 score = \frac {2 * Precision * Recall} {Precision + Recall}
\end{displaymath}

\subsubsection{\emph{Log loss}}
\emph{Log loss} jest jedną z najważniejszych miar klasyfikacji, oparta jest jednak na prawdopodobieństwach przy przewidywaniu klas (nie sprawdzi się więc w~niektórych algorytmach). Znacznie ciężej jest ją bezpośrednio interpretować, jednak znacznie lepiej od poprzednio przedstawionych metryk sprawuje się przy porównywaniu modelów.

\emph{Log loss jest} wskaźnikiem, który pokazuje, jak blisko przewidziane prawdopodobieństwa klas są dla prawdziwych wartości klas. Im bardziej przewidziane prawdopodobieństwa odbiegają od wartości tym większa jest wartość \emph{log loss}.