Large Scale Machine Learning - Week_10

Gradient Descent with Large Datasets

Learning With Large Datasets

我們得知要獲得一個高效能的機器學習演算法，可以透過大量資料來訓練演算法/模型，達到我們覺得合理的預期結果。但訓練數據大量，也有它自己的問題，特別是計算量的部分。

就拿計算梯度下降的部分來講，如果我們每做一次梯度下降就要跌代計算所有的模型和真實結果的誤差，要是數據量到達千萬的級別，可能就要花掉許多時間或者得運用更強大的運算資源去縮短時間，這樣的計算代價是非常昂貴的，所以後續會再提到其他的計算梯度下降的演算法，幫助我們可以更有效率且花費較少計算資源去訓練模型。

當然在使用上千萬的數據去計算前，當然也要先嘗試看看數千筆的數據是否也能達到我們的目標，要如何確認機器學習演算法是否該運用多少資料並檢查機器學習的演算法是否正確運行時，那就可以畫出學習曲線，也就是關於代價函數和數據及數量的xy圖，下面左方的圖代表高方差的數據，下面右方的圖代表高偏差的數據，關於兩種模型的偏差，都有相
對應的方式可以去解決問題。

在大規模的機器學習中，我們喜歡找到合理計算量的方法，或者高效率的計算方法來處理大數據，接下來的章節我們會介紹隨機梯度下降和映射化簡等方法來處理大量數據。


--------------------------------------------------------------------------------------------------------------------------
Stochastic Gradient Descent

當我們遇到規模很大數據時，可以透過隨機梯度下降，隨機梯度下降的代價函數表示如下：

這和普通批次的代價函數(Batch Gradient Descent)的差異在於沒有m樣本數量這個常數。主要普通的批次代價函數，是對所有樣本的代價函數求平均值，而隨機梯度下降(Stochastic Gradient Descent)的代價函數是對單一樣本求代價函數。

進行隨機梯度下降此演算法時要先隨機重新排序訓練樣本，然後再對每個訓練樣本進行隨機梯度下降的工作，作法如下：

下面為進行隨機梯度下降時的迭代公式：

和普通的批次梯度下降迭代公式做比較：

隨機梯度下降在每一次計算之後，便會更新參數θ，而不需要首先將所有訓練樣本求和，在批次梯度下降演算法還沒有完成一迭代時，隨機梯度下降演算法已經迭代很多次，這就是隨機梯度下降演算法的優勢。但是這樣的算法存在的問題是，不是每一步都是朝著正確的方向邁出，因此隨機梯度下降演算法雖然逐漸走向全局最小值的位置，但是可能無法到達最小值的那點，而在最小值附近徘迴。


--------------------------------------------------------------------------------------------------------------------------
Mini-Batch Gradient Descent

小量批次梯度下降演算法世界魚梯輛梯度下降演算法和隨機梯度下降演算法之間的演算法，每次計算常數b個訓練數據，變更新迭代一次θ，下圖為小量批次梯度下降的演算法：

通常我們會令b值在2-100之間，這樣做的好處在於，我們可以用向量化的方式來循環b個訓練實例，如果我們用的線性代數函數庫比較好，能夠支持平行處理，那麼演算法的總體表現將不受影響(與隨機梯度下降相同)。


--------------------------------------------------------------------------------------------------------------------------
Stochastic Gradient Descent Convergence

此章節我們介紹隨機梯度下降演算法的調校和學習率α的選取，在批次梯度下降中，我們可以令代價函數J為迭代次數的函數，也就是繪出代價函數和迭代次數的XY圖，根據圖表來判斷梯度下降是否收斂。但是在大規模的訓練數據集的情況下，這是不切實際的，因為其計算代價太高了。

在隨機梯度下降中，我們在每一次更新θ之前都計算一次代價函數，然後每X次迭代出來後，求出這X次用訓練數據迭代所造成的影響，也就是計算這X次迭代的代價函數的平均值，然後繪製這些平均值與X次迭代次數之間的函數圖表。

我們看到(A)這幅圖，藍色代表隨機梯度下降函數有著較大學習速率的α，紅色曲線則是代表調整學習速率α較小後的結果，發現紅色曲線可以收斂在更小的價值函數。

我們看到(B)這幅圖，假設藍色曲線代表隨機梯度下降以1000個訓練數據為平均所畫出的價值函數，紅色曲線則是代表5000個訓練數據為平均所畫出的價值函數，可以發現紅色較為平滑反映出長期的趨勢。

我們看到(C)這幅圖，我們繪製藍色曲線這樣的圖表時，可能會得到上下震盪但是不會明顯減少的函數圖形，可以運用增加平均的訓練數據來使曲線更加平緩，也許便能看出下降的趨勢(紅色曲線)，也有可能表現仍是上下震盪且不下降(粉紅色曲線)，那麼就代表我們的模型本身可能存在一些錯誤。

我們看到(D)這幅圖，若得到這樣的函數圖形，藍色曲線不度上升，那麼代表我們會需要一個較小的學習速率α。

當然我們也可另學習速率隨著迭帶次數增加而減小，例如令：

隨著我們不斷地靠近全局最小值，通過減小學習率，我們迫使算法收斂而非在最小值附近徘徊，但是我們通常不需要這樣做便能有非常好的效果，對α進行調整所耗費的計算通常不值得。


--------------------------------------------------------------------------------------------------------------------------

Advanced Topics

Online Learning

這個章節討論一種新的大規模的機器學習機制，叫做在線學習，在線學習演算法指的是對數據流而非離線的靜態數據集的學習，許多在線網站都有持續不斷得用戶流，對於每一個用戶，網站希望能在不將數據存儲到數據庫中便順利地進行演算法學習。許多大型網站或者大型網路使用，使用不同版本的在線學習機制的演算法，從大批湧入又離開網站的用戶身上學習。特別要提及的是，如果你有一個由連續的用戶流引發的連續的數據流，進入你的網站，你能做的是使用一個在線學習機制，從數據流中學習用戶的偏好，然後使用這些資訊來優化一些關於網站的決策。


假設我們正在經一家物流公司，每當伊格用戶詢問從地點A置地點B的快遞費用時，我們給用戶一個報價，該用戶可能選擇接受(y=1)或不接受(y=0)。現在我們希望建構一個模型，來預測用戶接受報價使用我們物流服務的可能性。因此報價是我們的一個特徵，其他特徵為距離、起始地點目標地點以及特定的用戶數據。模型的輸出是P(y=1)。

在線學習的算法與隨機梯度下降算法有些類似，我們對單一的實例進行學習，而非對一個提前定義的訓練數據集進行循環，下面為在線學習的演算法：

一但度一個數據的學習完成後，我們便可以丟棄該數據，不需要再儲存它了。這種方式的好處在於，我們的算法可以很好的適應用戶的傾向性，演算法可以針對用戶的當前行為不斷地更新模型以適應該用戶。每次交互事件並不只產生一個數據集，例如我們一次給用戶提供3個物流選項，用戶選擇地2項，實際上我們可以獲得3個新的訓練實例，因而我們的算法可以一次從3個實例中學習並更新模型。

--------------------------------------------------------------------------------------------------------------------------
Map Reduce and Data Parallelism

映射畫檢和數據並行對於大規模機器學習問題而言是非常重要的概念。之前提到，如果我們用批次梯度下降演算法來求解大規模數據資料及的最佳解，我們需要對整個訓練及進行循環，計算偏微分和代價函數，再來求和，計算代價非常大。如果我們能夠將我們的數據及分配給多台電腦，讓每台電腦處理數據資料集的一個子集，然後我們將每台電腦計算子集的結果匯集後再求和，這種方法叫做映射化簡。

具體而言，如果任何學習演算法能夠表達為對訓練數據集的函數求和，那麼便能將這個任務分配給多台電腦(或者同意台電腦的不同CPU核心)，以達到加速處理的目的。

假設我們有400訓練樣本，我們可以將批物梯度下降求和的任務分配給4台電腦進行處理，就如下表所示：

很多高級的線性代數函數庫已經能夠利用多核CPU的多個核心來平行地處理矩陣運算，這也是算法的向量化實現如此重要的緣故(比使用迴圈計算快)。


--------------------------------------------------------------------------------------------------------------------------