第十周筆記：大量數據演算法

01-25

（第九周筆記還有推薦系統沒補充完，不過要補充好推薦系統還得查很多資料，所以暫時沒有補充的慾望。）

首先一個問題，是否需要用大數據？

記得之前筆記（第六周筆記）中，我們分析過一種情況，就是當樣本數量m達到一定的程度時，增加樣本數量，對於交叉驗證集和訓練集之間得出的誤差的差距，並沒有太多減少的空間時，就不再需要增加樣本量。

一句話，當分別計算J_cv和J_train在當前樣本數量下的誤差時，差距極大時，應當使用更多數據，差距極小時，就不應當使用大量數據了。

那麼，大量數據時，用什麼演算法呢？

數據太多，如果還按照批量梯度下降來玩，估計一個因子都得算個三五天，整個公式出出來，改一改，一個月就過去了……

那就不用所有因子來玩嘛。一步一步局部下降（貪婪演算法）也不錯嘛！但是貪婪演算法也有問題，那就是，如果你的數據凹凸不平的，有很多個局部最優，那就會發生如下情況：

那咋辦呢？是的，你可以多重複隨機選初始點迭代幾次，然後在交叉集上比較，但是萬一這種坑坑窪窪的地方很多，那你得重複很多次，運氣不好興許一輩子就過去了~

那我們就不用局部最優，還是得用全部數據，那不就慢了么，怎麼辦呢？那就每次就一個數據就拿去改變參數，湊合湊合得了。由於很隨便，所以就叫它隨便，啊不對隨機梯度下降……

隨機梯度下降：

我們先看看以前的批量梯度下降的公式：

$heta_{j}= heta_{j}-alpha *frac{d}{d heta_{j} } J_{ heta}$ = $heta_{j}= heta_{j}-alpha /m*sum_{i}^{m}{} (h(x_i) -y_{i} )*x_{i,j}$

那麼，現在我們改成了每次隨便挑一個數據，於是公式就成了：

$heta_{j}= heta_{j}-alpha /m*{} (h(x_i) -y_{i} )*x_{j}$

也就是說，other than 把所有的數據拿來加一遍再改變參數值，我們現在變成了急不可耐地看到一個數據就改變一次參數值……

啥，你說這不就是貪婪演算法，並不隨機么……？

那好，那就……執行之前，把數據打亂，python的話就randshaffle一下，於是就隨機了唄~~~

那麼最後還有一個問題，我們以前的批量梯度下降，是一遍又一遍地迭代，直到收斂到某一個範圍內。現在，你每個數據就下降一次，需要重複多少次呢？

不重複啊。說了這是給大量數據準備的，我們就假吧意思大量數據來說下降一次就夠了。於是我們就總共只下降一次……只是對於其中，每個數據迭代的時候，就直接改變參數值 $heta$ 了。所以你也看到了……由於只下降一次，數據不夠多時就別用了。誤差會很大的。

迷你批量梯度下降（略拗口）：

我們也可以換個思路，還是用批量梯度下降，只是這時候不用所有數據，而是和剛才哪個隨機梯度下降的思路結合一下。批量一度下降是所有數據一起算一次，改變一次參數值對吧？隨機梯度下降時每個觀測數據都拿來改變一次參數值對吧？咱中國人講究中庸嘛。就既不拿所有的，也不光拿一個，而是一小批一小批地拿來下降，比如每次10個數據下降一次啦，每次20個數據下降一次啦。之類的。

那麼我們怎麼選呢？

把數據隨機分成x份，每份裡面有10~100個數據。以每份b個數據舉例，我們要迭代的參數公式就成了這樣：

i=1,b=10(假設b為10)

while i < m

$heta_{j}= heta_{j}-alpha /m*sum_{i}^{i+b-1}{} (h(x_i) -y_{i} )*x_{i,j}$

i += b

差不多就是這樣……意思就是從每個拿來改變一次參數 $heta$ ，變成了每b個拿來改一次參數 $heta$ 。

檢查收斂：

那麼現在又有一個問題來了。我們數據多了就變懶了，算一次湊合湊合過了，萬一不收斂怎麼辦？所以還得檢查收斂……

怎麼檢查收斂呢？

拿出我們的代價函數： $cost=1/2*(h(x_{i} )-y_{i} )^2$

每迭代k次，就計算一下。最後把圖畫出來，看看收斂不收斂。

藍色是1000次看一下，紅色是5000次看一下。橫坐標是看的次數，縱坐標是當前看的時候cost的值。

可以看到，第一幅圖是在收斂的表現，到達最低點後開始震蕩。第二幅圖意思是你看的範圍越大，看到的振幅越小（批量梯度下降看起來就很光滑了。相反，k=1的時候，看起來就心電圖了……）第三附圖表示的意思是，如果你看著震蕩不確定到最小沒有，增加k，就可以知道到底是應該優化演算法還是只是雜音造成的震蕩。第四附圖當然就是發散了，這時候可以試試小一點的 $alpha$ 值。

接下來又有一個問題來了。大量數據一般都不是一次就給完的，很多時候，是連續給你賽數據，演算法也要與時俱進嘛。當然，這時候你就可以直接用上面說的兩種演算法，新數據直接分成幾份，算了就馬上拿去改變參數值。這裡可以讓客戶端完成一部分簡單的數據處理再交給伺服器，比如伺服器每天計算一次參數，客戶端通過這些參數，把缺失數據補充完整，再返回給客戶端。又例如如果網路恨不好，而數據量足夠客戶端依據數據計算出一個代價函數，返回這個代價函數而不是數據，也許能提高一定的效率。嘛……再多的就要學分散式處理了。這裡就不多扯淡了、

第11周的筆記內容很少，大致就是講一下如何涉及一個機器學習的解決計劃，以及感謝收看云云。在這裡一併寫了吧。基本思路就是，把一個複雜的機器學習問題分解成n個小問題（當然你也可以讓神經網路自己分解去……）例如你要讓機器自己看書，你就可以這樣分解問題，讓機器識別出書，讓機器通過書識別出段落，語句，讓機器通過段落語句識別其中的文字關聯，進而識別出其抽象化的意思。讓機器通過抽象化的意思重新組合合成你需要的信息。這種，把一個複雜的問題拆分成n個細小的問題一個一個解決。

常見的，例如我們要自動分析一個地區菜價，拿上來的數據不可能100%完整，那麼就可以分為兩套來做，第一個系統用來補充不完整信息（天氣，道路交通，政府政策等），第二個系統用第一個系統已經加工好的信息來分析出想要的數據，第三個系統根據這些數據來預測未來的菜價。

實際過程中，由於每次系統都有偏差，最後總準確率會不斷下降。例如上面說的哪個分析菜價的，也許總準確率為80%，然後如果是給完善的信息，不考慮第1個系統的誤差，準確率是90%，如果給完善的數據，直接用來預測，準確率是98%。那麼就可以簡單的理解為，系統1可改善上限為10%，系統2可改善上限為8%，系統3可改善上限為2%。假如時間有限，也許就應該把寶貴的時間主要用以改善系統1和系統2。