# [筆記] 機器學習 大規模的機器學習

> It's not who has the best algorithm that wins. It's who has the most data.

* 大規模的機器學習是用來處理大數據的算法
* 可以先使用較少的資料，並畫出學習曲線，判斷是否需要用到大數據
* 當資料量較大時，會使梯度下降算法 ( 批量梯度下降 batch gradient descent ) 的計算量非常大，因此必須使用不同的梯度下降算法

### 隨機梯度下降 ( stochastic gradient descent )

1. 資料預處理，將資料打亂
2. 循環運算資料 1 到 m，每筆資料做一次迭代

* Repeat ( 整個循環可能循環計算 1 ~ 10 次，取決於資料量大小 )

* for i = 1 to m

* $\theta_j$ = $\theta_j - \alpha(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$ ( for j = 0, 1, ..., n )

* 隨機梯度下降可以運用於各種算法
* 與基本的梯度下降差別

* 基本的梯度下降 : 算完所有資料後做一次迭代
* 隨機梯度下降 : 算完每筆資料做一次迭代
* 隨機梯度下降的下降路徑較迂迴

#### 如何檢查收斂及選擇學習速率 α

* 檢查收斂

* $cost(\theta, (x^{(i)}, y^{(i)}))$ = $\dfrac{1}{2}(h_{\theta}(x^{(i)} - y^{(i)}))^2$
* 在更新 θ 前，先計算 $cost(\theta, (x^{(i)}, y^{(i)}))$

* 因為如果使用更新後的 θ，使其在訓練資料上做預測，會比實際效果更好

* 每 1000 次迭代 ( 也能是其他數字 ) 計算 $cost(\theta, (x^{(i)}, y^{(i)}))$ 的平均值並畫出來
* 觀察畫出來的圖，檢查隨機梯度下降是否在收斂

* 可能出現的圖 :


* 藍線 : 代表學習算法已經收斂了
* 紅線 : 試試更小的學習速率 α，或許可以收斂到更好的點


* 紅線 : 將每 1000 次迭代計算平均改為 5000，可能得到更平滑的曲線


* 藍線 : 為 1000 次迭代計算平均，過於陡峭看不出是否收斂
* 紅線 : 改成 5000 後，可以看出其實是有在收斂的
* 紫線 : 若是改成 5000 後，發現並沒有收斂，也許需要改變學習速率 α、特徵、算法...


* 表示算法正在發散，試著降低學習速率 α

* 選擇學習速率 α

* 隨機梯度下降並不會真正的收斂，而是一直在最小值附近徘徊
* 若想使隨機梯度下降確實收斂到全局最小值，可以隨時間變化減少學習速率 α

* α = $\dfrac{常數 1}{迭代次數 + 常數 2}$

* 雖然可以確實收斂到全局最小值，但並不是很常用，因為多了要選擇 `常數 1` 與 `常數 2` 的工作量，而且收斂到最小值附近其實已經很不錯了

### 小批量梯度下降 ( mini-batch gradient descent )

* 有時會比隨機梯度下降快上一些
* 算完每 b 筆資料做一次迭代 ( b 通常會是 2 ~ 100 )
* 算法 : ( 假設 b 為 10，m 為 1000 )

* Repeat

* for i = 1, 11, 21, 31, ..., 991

* $\theta_j$ = $\theta_j - \alpha\dfrac{1}{10}\sum^{i + 9}_{k = i}(h_{\theta}(x^{(k)}) - y^{(k)})x_j^{(k)}$ ( for j = 0, 1, ..., n )

### 在線學習機制 ( online learning )

* 在擁有連續的新數據進來時，需要在線學習機制來從中學習
* 可以對正在變化的新數據進行調適
* 算法 :

* 根據使用者 Get (x, y)
* 使用此 (x, y) 去更新 θ
* 然後此 (x, y) 就可以拋棄了

* 使用在線學習機制的例子 : 給不同用戶展示他們可能有興趣的項目
* 事實上使用在線學習機制的問題，都可以被歸類到擁有固定資料集的標準學習算法，但許多大公司偏向以在線學習機制獲取新數據來學習

### 映射化簡 ( map reduce )

* 一種可以在多台機器上 ( 或多核 ) 學習的算法，加速學習的速率
* 只要機器學習算法可以表示為求和的形式就可以運用映射化簡
* 算法 : ( 假設資料量 m 為 400 )

* 機器 1 使用 (x⁽¹⁾, y⁽¹⁾)，...，(x⁽¹⁰⁰⁾, y⁽¹⁰⁰⁾)

* $temp_j^{(1)}$ = $\sum^{100}_{i = 1}(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$

* 機器 2 使用 (x⁽¹⁰¹⁾, y⁽¹⁰¹⁾)，...，(x⁽²⁰⁰⁾, y⁽²⁰⁰⁾)

* $temp_j^{(2)}$ = $\sum^{200}_{i = 101}(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$

* 機器 3 使用 (x⁽²⁰¹⁾, y⁽²⁰¹⁾)，...，(x⁽³⁰⁰⁾, y⁽³⁰⁰⁾)

* $temp_j^{(3)}$ = $\sum^{300}_{i = 201}(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$

* 機器 4 使用 (x⁽³⁰¹⁾, y⁽³⁰¹⁾)，...，(x⁽⁴⁰⁰⁾, y⁽⁴⁰⁰⁾)

* $temp_j^{(4)}$ = $\sum^{400}_{i = 301}(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$

* 結合 : $\theta_j$ = $\theta_j - \alpha\dfrac{1}{400}(temp_j^{(1)} + temp_j^{(2)} + temp_j^{(3)} + temp_j^{(4)})$ ( for j = 0, 1, ..., n )


* 將數據分給多台電腦運算


* 將數據分給多核運算 ( 不須擔心網路延遲 )
* 有些線性代數函式庫會自動利用多核完成運算，這時就不須自己實現映射化簡技術

###### tags: `筆記` `機器學習` `隨機梯度下降` `小批量梯度下降` `在線學習機制` `映射化簡`