# Techniki optymalizacji

- przygotowanie danych
  - balansowanie zestawu
  - wzbogacanie danych
  - mieszanie (randomizacja)
  - zestaw uczący, walidacyjny i testowy
- problem znikających i eksplodujących gradientów
  - Batch Normalization
  - sieci rezydualne

</div><div markdown="1">

- problem przeuczenia sieci
  - Dropout
- uczenie sieci
  - funkcja straty
  - algorytmy optymalizacji
  - zmienny współczynnik uczenia
- metryki
  - tablica pomyłek
  - czułość, swoistość, precyzja, dokładność
  - krzywa ROC

</div></div>

---
## Dane, dane, dane!
> Model może być co najwyżej tak dobry, jak zestaw danych użytych do trenowania.

![](algorytm_ml.svg)

----

### Równoważenie (balansowanie) zestawu uczącego

- model nauczy się najlepiej tych cech, których w zestawie danych jest najwięcej
- uczenie modelu powinno odbywać się z użyciem różnorodnej i zrównoważonej bazy

#### Wyznaczanie wag dla klas

- wartość funkcji straty jest średnią strat cząstkowych dla poszczególnych elementów zestawu uczącego
- możemy wyznaczyć wagi dla poszczególnych klas na podstawie ich liczności
- $w_k \sim \frac{1}{licznosc \\ klasy \\ k}$

</div><div markdown="1">

#### Wzbogacanie danych

- Przykładowe metody wzbogadzania zbioru obrazów:
losowy obrót, zbliżenie, jasność i kontrast, odwrócenie, przesunięcie

![](augmented_cats.png)

</div></div>

----

## Skalowanie danych

- dokonujemy transformacji danych w celu ustalenia uniwersalnej skali
- pozwala nam to wyorzystywać dane wyrażane w różnych jednoskach i skalach
- skalowanie ogranicza problem znikania i eksplodowania gradientów

**Normalizacja**
- przeskalowanie i przesunięcie danych do ustalonego zakresu np. $[0, 1]$

$\hat x_i = \frac{x_i - min(x)}{max(x)-min(x)}$

</div><div markdown="1">

**Standaryzacja**
- transformacja, po której średnia wynosi $0$, a odchylenie standardowe wynosi $1$

$\hat x_i = \frac{x_i - \mu}{\sigma}$

</div></div>

> Uwaga: powyższe pojęcia są często stosowane zamiennie.

----

## Mieszanie danych (randomizacja)

- uczenie sieci przebiega na podstawie danych przekazywanych **w porcjach** (*mini batch*)
- batche są wybierane **losowo** ze zbioru uczącego na początku każdej epoki
- podział na batche ułatwia znalezienie **globalnego minimum** funkcji straty (czynnik stochastyczny)
- przetworzenie pojedyńczej porcji wymaga **mniejszych zasobów obliczeniowych**
- by uczenie było stabilne, rozkład danych w porcji powinien być zbliżony do rozkładu w całym zestawie uczącym
- przemieszanie danych powinno nastąpić **przed podziałem** zbioru danych na zestaw uczący i testowy

</div><div markdown="1">

![](random_minibatches.webp)

</div></div>

---

## Zestaw uczący i testowy

> Pierwsza zasada uczenia maszynowego: nigdy nie używaj tych samych danych do uczenia i do walidacji modelu.

- zestaw danych dzielimy na **trzy części**: zestaw uczący (treningowy), walidacyjny i testowy
- **wsteczna propagacja** i aktualizacja parametrów modelu są przeprowadzane wyłącznie na podstawie danych z **zestawu uczącego**
- dostrajanie modelu (tuning), czyli dobór hiperparametrów, następuje na podstawie **zestawu walidacyjnego**
- ostateczna ocena jakości modelu następuje na podstawie **zestawu testowego**
- podział na części jest konieczny, by móc ocenić stopień przeuczenia modelu
- podziału dokonujemy po uprzednim przemieszaniu danych
- przykładowe proporcje stosowane w praktyce:
  - zestaw uczący: 60-80%
  - zestaw walidacyjny: 10-20%
  - zestaw testowy: 10-20%

----

## Problem przeuczenia
### *Overfitting*

- nadmierne dopasowanie, przetrenowanie
- oznacza, że model nauczył się danych, a nie rozkładu, z jakiego pochodzą dane
- model nauczył się danych "na pamięć"
- niemożliwość generalizacji wiedzy, czyli zastosowania modelu do nieznanych danych

</div><div markdown="1">

![](overfitting.svg)

</div></div>

----

## Problem przeuczenia

- przeuczenie można zaobserwować dzięki podziałowi na **zestaw uczący i walidacyjny**
- dla modelu przeuczonego spada wartość funkcji straty dla zestawu uczącego, a rośnie dla zestawu walidacyjnego
  
**Unikanie problemu**
- wczesne zatrzymanie uczenia
- regularyzacja (dropout)

</div><div markdown="1">

![](overfitting_error.svg)

</div></div>

----
## Dropout

- metoda regularyzacji
- podczas uczenia losowa część $p$ wejść jest ustawiana na $0$
- pozostałe wejścia zostają przeskalowane o czynnik $\frac{1}{1-p}$ (w celu zachowania wariancji)
- podczas wnioskowania warstwa *dropout* jest ignorowana (odwzorowanie tożsamościowe)
- intuicja: końcowy model jest superpozycją wielu modeli, opartych na podsieciach

</div><div markdown="1">

![](dropout.svg)

- przeważnie warstwę *dropout* umieszcza się za warstwami liniowymi / gęstymi (np. $p=0.5$)
- czasem stosuje się również po warstwach konwolucyjnych (np. $p=0.2$)

</div></div>

> [Improving neural networks by preventing co-adaptation of feature detectors](https://arxiv.org/abs/1207.0580) (2012)
---
## Problem znikających i eksplodujących gradientów

- wyznaczanie gradientu za pomocą reguły łańcuchowej ma swoje negatywne konsekwencje
- niska (zerowa) wartość jednego z gradientów lokalnych powoduje zniknięcie gradientu
- zanik gradientu powoduje zatrzymanie procesu uczenia sieci

### Przyczyny

- nieunormowane dane
- zbyt duże wartości wag skutkują dużą wartością pól lokalnych działających na neurony
- duże pole lokalne powoduje wejście neuronu w stan nasycenia

</div><div markdown="1">

### Metody unikania problemu

- odpowiednia inicjalizacja wag (wariancja zależna on liczby neuronów w warstwie)
- stosowanie odpowiednich funkcji aktywacji (unikanie funkcji sigmoidalnych w warstwach ukrytych)
- uczenie adaptacyjne
- warstwy normalizacyjne (np. *batch/layer normalization*)
- *residual neural networks*

</div></div>

----
### Batch Normalization

- przeskalowanie (standaryzacja)
- parametry $\gamma$ i $\beta$ (po jednym na neuron) podlegają uczeniu
- wartości początkowe: $\gamma=1$, $\beta=0$
- **podczas uczenia** średnia i odchylenie wyznaczane są na podstawie pojedyńczego mini-batcha
- **podczas wnioskowania** skalowanie następuje na podstawie średnich kroczących wyliczonych podczas uczenia ($\alpha$ - bezwładność)

<div markdown="1">\[\begin{aligned}
\mu & \leftarrow \alpha \mu + (1-\alpha)\mu_B \\
\sigma & \leftarrow \alpha \sigma + (1-\alpha)\sigma_B
\end{aligned}\]</div>

- BN zwykle umieszcza się bezpośrednio przed nieliniowością (funkcją aktywacji)

</div><div markdown="1">

![](batchnorm_alg.png)
> [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://arxiv.org/abs/1502.03167) (2015)

</div></div>

---

## Sieci rezydualne
### *Residual Neural Networks (ResNets)*

- *ResNet* - Residual Neural Network
- model zaproponowany w 2015 roku przez grupę badaczy z firmy Microsoft (*MSRA*)
- grupa zwyciężyła w 194 kategoriach (na 200) w konkursie [ImageNet](https://www.image-net.org/challenges/LSVRC/2015/results.php) w 2015 roku

</div><div markdown="1">

![](he.png)

[Źródło](https://scholar.google.com/citations?user=DhtAFkwAAAAJ&hl=en)

</div></div>

----
## Założenia modelu ResNet

- połączenia resztkowe (skróty), omijające warstwę lub grupę warstw
- na ogół skrót omija warstwę splotową, normalizującą (np. *BatchNorm*) i aktywacyjną
- skróty pozwalają na propagację gradientu ograniczając problem znikania gradientów w bardzo głębokich sieciach
- obecność skrótów upraszcza sieć, stabilizując algorytm optymalizacji poprzez wymuszenie stopniowej eksploracji przestrzeni parametrów
- dodanie skrótu nie zwiększa złożoności obliczeniowej, skróty nie posiadają wag (ew. małą liczbę wyłącznie do projekcji w skrócie)

</div><div markdown="1">

![](resnet_block.png)

</div></div>

----

## Zasada działania ResNet

- **założenie:** odwzorowanie $H(\vec x)$ może być aproksymowane przez szereg przekształceń (warstw) nieliniowych
- **teza:** możliwa jest aproksymacja reszty (residuum) $F(\vec x)= H(\vec x)-\vec x$
- **obserwacja:** algorytmom łatwiej jest znaleźć residuum $F(\vec x)$, niż funkcję $H(\vec x)$
- skrót przekazuje niezmieniony sygnał, oznacza więc **odwzorowanie tożsamościowe**
- oryginalny sygnał jest dodawany do wyniku działania funkcji $F(\vec x)$
- jeśli $F(\vec x)$ i $\vec x$ mają inny wymiar, dokonywana jest liniowa projekcja $W_s \vec x$ (np. za pomocą splotu $1 \times 1$)

</div><div markdown="1">

![](resnet_block.png)

</div></div>

----

## Sieć splotowa typu ResNet

### *Bottleneck architecture*

- blok składa się z 3 warstw splotowych
  - warstwa z filtrami $1 \times 1$: redukcja wymiaru (liczby kanałów)
  - warstwa z filtrami $3 \times 3$ (mniejszy rozmiar wejściowy i wyjściowy)
  - warstwa z filtrami $1 \times 1$: przywrócenie wymiaru
- ostatnia warstwa $1 \times 1$ może zmniejszać rozdzielczość poprzez skok o wartości $2$.

</div><div markdown="1">

![](resnet_deep.png)

</div></div>

----

### Sieć splotowa typu ResNet

Przykłady architektur *ResNet* dla bazy *ImageNet*:

![](resnet_impl.png)

Zmniejszenie rozdzielczości następuje w warstwach *conv3_1*, *conv4_1* i *conv5_1* ze skokiem $2$.

Dla porównania: liczba FLOPs dla VGG19: $19.6 \times 10^9$.

</div><div markdown="1">

![](vgg_vs_resnet.png)

</div></div>

---

## Algorytmy optymalizacji

- gradient w sieciach neuronowych wyznaczamy metodą wstecznej propagacji
- aktualizacji parametrów sieci możemy dokonać z wykorzystaniem różnych algorytmów
- algorytmy różnią się stabilnością i szybkością znajdowania minimum funkcji straty

![](opt1.gif)

</div><div markdown="1">

![](opt2.gif)

</div></div>

> https://ruder.io/optimizing-gradient-descent/
----

## Metoda gradientu prostego 
### *gradient descent (GD)*

- układ opisują parametry $\theta$ (wagi połączeń sieci neuronowej)
- szukamy minimum pewnej funkcji straty $L$
- wyznaczamy gradient $\nabla_\theta L$ metodą wstecznej propagacji
- aktualizujemy wartości wag proporcjonalnie do wartości gradientu lecz w przeciwnym kierunku

$\theta_t \leftarrow \theta_{t-1} - \eta \nabla_\theta L$

- w metodzie GD gradient wyznaczony jest na podstawie **całego** zbioru uczącego

----

## Wersja stochastyczna metody gradientu prostego
### *stochastic gradient descent (SGD)*

- gradient wyznaczamy na podstawie wartości funkcji straty dla pojedynczego wzorca $\mu$
- aktualizujemy wagi sieci

$\theta_t \leftarrow \theta_{t-1} - \eta \nabla_\theta L^{(\mu)}$

- procedurę powtarzamy dla każdego wzorca w zbiorze uczącym
- kolejność wzorców jest losowa i inna dla każdej epoki
- dla metody SGD charakterystyczne są duże fluktuacje

## Mini-batch SGD
- gradient wyznaczamy dla pewnej porcji (*batch*) danych z zestawu uczącego
- porcje są losowane

----

## SGD z bezwładnością
### (*SGD with momentum*)

- szybkość uczenia w danym kroku zależy od poprzedniego kroku
- $\gamma$ - parametr bezwładności

$v_t=\gamma v_{t-1} + \eta \nabla_\theta L$

$\theta_t \leftarrow  \theta_{t-1} - v_t$

- dzięki bezwładności układ szybciej znajduje minimum
- bezwładność redukuje fluktuacje

----

## Problemy tradycyjnych algorytmów

- trudny wybór szybkości uczenia (mała $\eta$ - wolne zbieganie, duża $\eta$ - niestabilność)
- ta sama szybkość uczenia przez wszystkie epoki (ewentualnie trudność określenia zmienności uczenia z czasem)
- ta sama szybkość uczenia dla wszystkich parametrów, bez względu na częstotliwość występowania odpowiadającej im cechy
- trudność ominięcia lokalnych minimów

----

## AdaGrad
### adaptive gradient algorithm

- różne współczynniki uczenia dla każdego parametru i kroku
- wolniejsze uczenie wag odpowiadających za często występujące cechy
- szybsze uczenie wag związanych z rzadkimi cechami

$g_t = \nabla_\theta L$ - gradient funkcji straty

Aktualizacja szybkości uczenia:

$\theta_t \leftarrow \theta_{t+1} - \frac{\eta}{\sqrt{G_t } + \epsilon} \cdot g_t$

$G_t$ - macierz diagonalna: $G_t=\sum\limits_{\tau=1}^{t}g_\tau^{2}$

</div><div markdown="1">

## AdaDelta

- modyfikacja metody AdaGrad
- rozwiązuje problem kumulowania się gradientów z poprzednich kroków, a więc malenia współczynnika uczenia
- wprowadzone jest okno czasowe o ustalonej długości, z którego wyliczany jest współczynnik uczenia

</div></div>

----

## RMSprop
### root mean square propagation

- niezależna szybkość uczenia dla każdego parametru
- szybkość uczenia zależy od ruchomej średniej ostatnich gradientów dla danej wagi.
- wagi są aktualizowane wg równania:

$\theta_t \leftarrow \theta_{t-1} - \frac{\eta}{\sqrt{v_t } + \epsilon} \cdot \nabla_\theta L$

$v_t \leftarrow \gamma v_{t-1}+(1-\gamma )(\nabla_\theta L)^{2}$

gdzie $\gamma$ jest parametrem zapominania.

----

## Adam
### adaptive moment estimation

- szybkość uczenia zależy od wykładniczo zanikającej średniej z ostatnich gradientów
- zależy również od wykładniczo zanikającej średniej drugich momentów gradientów
- rozwiązanie takie symuluje bezwładność i opór

Zanikające średnie:

$m_t=\beta_1 m_{t−1}+(1−\beta_1)\nabla_\theta L$

$v_t=\beta_2 v_{t−1}+(1−\beta_2)(\nabla_\theta L)^2$

</div><div markdown="1">

Ponieważ $m$ i $v$ na początku są zerowe, wyznaczamy ich poprawione wartości:

$\hat m_t = \frac{m_t}{1-\beta_1^t}$

$\hat v_t = \frac{v_t}{1-\beta_2^t}$

</div></div>

Aktualizacja wag: $\theta_t \leftarrow \theta_{t-1} - \frac{\eta}{\sqrt{\hat v_t}+\epsilon} \hat m_t$

Domyślne wartości: $\beta_1=0.9$, $\beta_2=0.999$

----

## Zmienny współczynnik uczenia

- w celu poprawy skuteczności optymalizacji często stosuje się zmienny współczynnik uczenia
- na ogół zaczyna się od większej wartości, a następnie zmniejsza z upływem kolejnych epok
- popularne strategie to:
  - obniżanie współczynnika po osiągnięciu plateau
  - spadek odcinkami stały
  - spadek wykładniczy
  - spadek z "gorącymi restartami"

---

## Ocena jakości modelu

- tablica pomyłek
- współczynniki jakości
- krzywa ROC

----

## Tablica pomyłek

- inaczej: macierz błędów (*ang. confusion matrix*)
- ocena jakości klasyfikacji binarnej (dwie klasy)
- oznaczenia:
  - TP - *true positive*
  - TN - *true negative*
  - FP - *false positive*, błąd I rodzaju
  - FN - *false negative*, błąd II rodzaju

![](conf_matrix.png)

</div><div markdown="1">

![](conf_matrix_short.png)

![](pregnant.jpg)

</div></div>

----

### Przykłady dla większej liczby klas

![](cm_kachuee.png)
(Kachuee 2018)

</div><div markdown="1">

![](cm_hannun.png)
(Hannun 2019)

</div></div>

----

## Współczynniki jakości

- **trafność** (*accuracy*): odsetek poprawnych klasyfikacji dokonywanych przez model.
- **precyzja** (*precission*): stopień w jakim klasyfikacje pozytywne na podstawie modelu są poprawne.
- **czułość** (*sensitivity*, *recall*, *true positive rate*): zdolność modelu do wychwytywania przypadków pozytywnych.
- **specyficzność**, swoistość (*specificity*, *true negative rate*): zdolność modelu do wychwytywania przypadków negatywnych.
- współczynnik *F1*: średnia harmoniczna czułości i precyzji

</div><div markdown="1">

- $accuracy = \frac{TP+TN}{TP+TN+FP+FN}$

- $precission = \frac{TP}{TP+FP}$

- $sensitivity = \frac{TP}{TP+FN} = \frac{TP}{P} = TPR$

- $specificity = \frac{TN}{TN+FP}= \frac{TN}{N} = TNR$

</div></div>

----

## Optymalizacja wartości progowej klasyfikatora
### Krzywa ROC (receiver operator characteristic)

- wykres wartości *TPR* (czułość) i *FPR* (1-swoistość) w zależności od prawdopodobieństwa wystąpienia zdarzenia szacowanego przez model
- wraz ze wzrostem prawdopodobieństwa granicznego klasyfikacji pozytywnej, obie miary maleją
- o jakości klasyfikatora mówi miara *AUC*, czyli pole pod krzywą *ROC* (*ang. area under curve*)
- krzywa *ROC* pozwala porównywać ze sobą różne klasyfikatory
- stosuje się również do klasyfilatorów wieloklasowych w układzie *jeden kontra reszta*

</div><div markdown="1">

![](roc_curve.svg)

</div></div>

----

## Przykłady krzywej ROC

![](roc_kwon.png)

(Kwon 2020)

</div><div markdown="1">

![](roc_hannun.png)

(Hannun 2019)

</div></div>