[筆記] 大規模的機器學習
It’s not who has the best algorithm that wins. It’s who has the most data.
- 大規模的機器學習是用來處理大數據的算法
- 可以先使用較少的資料，並畫出學習曲線，判斷是否需要用到大數據
- 當資料量較大時，會使梯度下降算法 ( 批量梯度下降 batch gradient descent ) 的計算量非常大，因此必須使用不同的梯度下降算法
隨機梯度下降 ( stochastic gradient descent )
- 資料預處理，將資料打亂
循環運算資料 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(1), y(1))，…，(x(100), y(100))
- $temp_j^{(1)}$ = $\sum^{100}_{i = 1}(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$
機器 2 使用 (x(101), y(101))，…，(x(200), y(200))
- $temp_j^{(2)}$ = $\sum^{200}_{i = 101}(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$
機器 3 使用 (x(201), y(201))，…，(x(300), y(300))
- $temp_j^{(3)}$ = $\sum^{300}_{i = 201}(h_{\theta}(x^{(i)}) - y^{(i)})x_j^{(i)}$
機器 4 使用 (x(301), y(301))，…，(x(400), y(400))
- $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 )
- 將數據分給多台電腦運算
- 將數據分給多核運算 ( 不須擔心網路延遲 )
- 有些線性代數函式庫會自動利用多核完成運算，這時就不須自己實現映射化簡技術
