---
tags: AI Summer school
---
# 大規模機器學習的隨機優化
- 王奕翔教授 台大電機系

## ML:from data to intelligence

Problems:
-

* Amount of data
* feature selection
* Model selection

### Abstraction of ML

* input > **BLACK BOX** > output (Supervised)
* 如何知道Black box如何運作?

* Training data > Model > Predict
* Estimated Black box ($\hat{y}$) <-> Black box ($y$)

* 前者是一個learning model (透過loss...等等)

### Quantifying the Effectiveness

* loss function ($y$和$\hat{y}$實際上的距離)

* 用一個函數來測量兩者之間有多遠

Example:
* 0-1 loss (Classification)
* hinge loss (SVM的loss function)
* Cross entropy loss (One-hot encoding)

### Learning Model

1. 通常先將Raw data map到一個high dimension的feature 再抽取features

* 如何抽取?...

2. 把features 丟進 learning model後產出output $\hat{y}$

3. Parameter $w$ 通常很高維

* 如何找到好的$w$?
* 從learning data中學習
* 什麼是好? (未必loss很低就是好 -> **Overfitting**)

### Expected loss

* 用testing input來測試$y$和$\hat{y}$之間相差多遠 (Prediction vs Ground Truth) 算出loss
* 取loss的期望值 並透過調整$w$來嘗試minimize這個期望值

* 所謂的Random(Stochastic)就是隨機抽一個點來比較

### Risk Minimization is Challenging

* statisical vs empirical
* 前者的分布unknown 後者的知道
* 因為gradient很難算　所以其實很難

### 最佳化gradient, Hessian很難 如何估計?

### First-Order Approimation

* 每一次iteration只需算一個gradient
* 無法算Hessian
* 大規模的ml不考慮First-Order (Costly)

## Stochastic Gradient Method by Robbins and Monro,1951

1. 從 $w$開始
2. 在每一個iteration中都產生一個亂數 並利用目前的gradient來算出一個stochatic vector
$g$
3. 選擇 step size
4. 利用 $g$ update $w$

在n個iteration後output出最後的$w$ (Unbiased estimated)

### SGD for Risk minimization

* 若有足夠的homogeneous data 可直接從data算出 $P$

* 但若沒有 也可以用 Empirical Risk中算出

### Stochastic vs Full-Batch

* 與其把所有gradient算出來 平均出大gradient (costly)
不如用SGD更有效率
* Example... LBFGS vs SGD
* SGD一開始掉比較快
* 其實在ML裡面, Train比較久沒有比較好, 可能會overfitting

### Intuitive Explanation: 為何SGD一開始很快 最後變很慢?

* $w^*$是最佳點 因此一開始都是往右邊跑 直到跑到右邊後會開始左右不斷移動 (自己confuse自己)

* 這個左右震盪的現象就是最後收斂很慢的原因 (最後還是會找到 只是要很久)

* 可降低Stepsize來繼續Train

Emerging Questions

1. Convergence guarantess of SGD?
2. SGD如何取決於問題的結構
3. ....

* Begin with Convex problems (Non-Convex比較有趣 但不夠成熟)

### Why Convexity

* 因為若沒有結構化的條件很難得到全局最佳點 但Convex problem有一些好用、成熟的function、演算法可以使用
* Convexity 能肯定global convergence 在optimum上
(也就是在convex problem中 local covergence = global convergence

### Strong Convexity

* **something stronger than convexity**

* EX: First-Order 、 second-order condition

### smoothness

可微分 -> smooth (Strongly-Convex gradient變化速度很快)
不可微分 -> Non-smooth

* 在convex problem下 可能有些點無法微分 只要將gradient用subsgradient替代即可 (但要有smothness)

* 有smoothness會快很多

### SGD 的 Variance Reduction

* SGD已經無法再更快了 只能透過修改參數來加速
* 辣張圖
* Key: SGD的Variance
* 可用mini-batch 降低Variance (一次Sample愈多 variance愈小)
* 一開始的時候不需要很小的Variance 但接近最佳點的時候就需要小一點的Variance (**Dynamic smapling**)

### Reduce Variance 的其中一個方法 - SVRG algorithm

[SVRG Paper](https://papers.nips.cc/paper/4937-accelerating-stochastic-gradient-descent-using-predictive-variance-reduction.pdf)

## [Main Reference](https://arxiv.org/abs/1606.04838)