機務？演算法工程師！轉職筆記（七）

02-16

第七個月了！不知不覺已經過半，繼續加油！

這個月，我們繼續完善了線性回歸的系統學習——著重學習了用梯度下降法實現線性回歸模型，然後在編程語言方面熟悉了Python語言，數據結構方面簡單學習了哈希表。這個月還是比較開心的，我們開了一個小差，通過做一個「答題遊戲」助手的小軟體，在github上收穫了800多個贊，上了幾天熱榜；而且本專欄得到了廣州日報記者李華的主動報道，還是挺開心的，也感謝他的報道~下面是知識分享~

機器學習方面

本月的學習主要進一步完善了線性回歸模型的另一種實現方法——梯度下降法。

一. 我學了那些資料

上一篇學習筆記裡面介紹了通過最小二乘法求解線性回歸，但是這種方法是存在一些缺陷的，比如在矩陣不可逆的情況下要用偽逆矩陣求解近似(一般平台會提供相關的解決辦法)，還有在特徵維度特別高，數據量大的的情況下求解比較困難，這時利用最小二乘法實現線性回歸的方法就不適用了，就需要用到梯度下降法來實現線性回歸。以下學習內容我參考了大量相關的博客，最主要的是以下兩篇和其中引用的鏈接，其中還有github上一個工程，可以自己嘗試重現下，一併致謝哈。

機器學習演算法入門之(一) 梯度下降法實現線性回歸

機器學習－梯度下降演算法 - Longfei Han

線性回歸是什麼？線性回歸模型的的一般形式？

請回溯機務？演算法工程師！轉職筆記（六）

線性回歸模型的學習過程（梯度下降法：批量梯度下降法，隨機梯度下降法）

定義的損失函數基本和最小二乘法解法很相似，這裡成為 $J_{w}=frac{1}{2N}((w^{T}x_{a}-y_{a})^{2}+((w^{T}x_{b}-y_{b})^{2}+...+((w^{T}x_{n}-y_{n})^{2})=frac{1}{2N}sum_{k=1}^{N}(h_{w}x_{k}-y_{k})^{2}$

為什麼分母有個「2」，我查了很多資料，普遍的解釋是這裡填寫一個常量對最後的結果並沒有影響,可以實驗，把 $J_{w}$ 最前面的1/N修改或者刪除並不會改變最終的結果，填「2」只是為了抵消後面平方求導後多出來的「2」，使公式顯得簡潔。。。大佬們真是什麼都想得出來。

梯度下降法的原理

由微積分知識可得，多元函數沿其負梯度方向下降最快。梯度下降法所做的是從損失函數中的任意一點開始，使參數每一步向梯度的反方向更新，逐步找到損失函數值的最低點，或者迭代到一定次數後，到達一個可以接受的損失函數值的點。

我們把損失函數 $J_{w}$ 看做由特徵權重 $h_{w}（w_{0},w_{1},w_{2}...w_{d}）$ 這個向量的各個維度的分量 $w_{0},w_{1},w_{2}...w_{d}$ 組成的多元函數,求損失函數的梯度，就是對各個維度的 $w_{0},w_{1},w_{2}...w_{d}$ 求偏導，然後組成的向量就是梯度。對於向量 $h_{w}$ 的每一維分量 $w_{j}$ ，我們都可以求出梯度的分量:

$frac{partial J_{w}}{partial w_{j}}=frac{partial}{partial w_{j}}frac{1}{2N}sum_{k=1}^{N}(h_{w}x_{k}-y_{k})^{2}$

$=frac{1}{N}sum_{k=1}^{N}(h_{w}x_{k}-y_{k})x_{kj}$

批量梯度下降法：

從上面的公式中，我們進一步得到特徵權重分量 $w_{j}$ 的更新公式,因為這個更新公式需要把N個樣本全部帶入計算，所以我們稱之為批量梯度下降。

$w_{j}^{new}=w_{j}-alpha *frac{partial J_{w}}{partial w_{j}}$

$=w_{j}-alpha *frac{1}{N}sum_{k=1}^{N}(h_{w}x_{k}-y_{k})x_{kj}$

把特徵權重的每一個分量都同時執行如上的更新，就得到了新的特種權重 $h_{w}^{new}$ ,之後再進入新一輪更新，直到到達停止條件。

隨機梯度下降法：

隨機梯度下降法和批量梯度下降法的區別在於每次更新時使用的樣本點數不同，有些文章寫批量梯度用了全部的樣本點（我覺得用一部分應該也可以），隨機梯度就是隨機選點，具體操作就是是更新時減去偏導的部分是否是各個樣本點先求和再求平均，還是直接隨機用一個點。

$w_{j}^{new}=w_{j}-alpha *(h_{w}x_{k}-y_{k})x_{kj}$

關於 $alpha$ 和停止條件：

上式中 $alpha$ 叫學習速率，也叫步長，一般取0到1之間，停止條件，一般是迭代到達一定次數，或者損失函數到達一個可以接受的範圍內。關於具體 $alpha$ 的選值和停止條件的確定屬於模型參數優化的問題，我們有機會再探究。

二.學霸指點：難點/重點分析和面試高頻問題

學霸說現在看起來推進進度還在線性回歸這裡，可能看起來有點慢了。但是最基礎的模型確實是最重要且最常用的，線性回歸的訓練方法還是需要了解和掌握的。從其中演化出來的演算法還是很多的。

三.我遇到的問題及解決辦法

為什麼損失函數採用這種方差的形式？？？這種函數的和優化有什麼固定的套路么？
為什麼多元函數沿其負梯度方向下降最快？

以上兩個問題請參考給出博客的「對誤差函數的進一步思考」及「梯度相關部分」，不在此贅述。

編程語言

本著提高編程實戰能力的目的（主要是針對我哈），我們趁著答題遊戲的熱度利用Python做了一個答題助手，效果還不錯，學霸負責開發，我負責輔助維護，順便熟悉了Python語言的基礎操作，感覺收穫還是挺多的,關於Python，我只想說老司機們誠不欺我：Life is short, use Python!

一.我學了哪些資料

1.關於Python

我主要看了簡明 Python 教程（更新的版本針對Python3：簡明 Python 教程 · GitBook）和Python3 教程 | 菜鳥教程。比較老的版本簡明Python教程是針對Python2的，與Python3在print語句和輸入輸出上有一點不同，其他都差不多，但是這個教程的知識結構清晰，例子寫得簡明扼要，是一個非常好的入門教程（也可以直接看針對Python3的版本），而菜鳥教程則提供了更豐富的實例和例如正則表達式，GUI編程等等稍微更高級一點的知識應用，兩者相互補充，非常實用。

如果你是一個一直關注我們的轉職筆記，並且跟進探索的同學，我覺得學習Python這門語言並沒有什麼難度，基礎的編程語言基礎和C之類的差不多，類和面向對象的概念在Java中我們已經接觸過，所以從整體上來看，學習並沒有什麼難度，下面我就自己的學習經驗總結下知識結構和要點。

2.關於答題助手

這個軟體的主要流程是先截取android模擬器的屏幕，然後進行上傳伺服器進行ocr識別，最終自動搜索答案。其實挺簡單的，學霸說做的過程中也沒遇到什麼太大的問題，這個項目中我也解決了一些問題，發現python確實好用，代碼基本上簡介明了，確實比java開發東西要快很多。有興趣的同學可以去rrdssfgcs/wenda-helper看一下~

二.學霸指點：難點/重點分析和面試高頻問題

三.我遇到的問題及解決辦法

我一開始搜了很多資料還有網課視頻，打算開始跟著視頻學習Python，但是進度很慢，後來一個有經驗的同學跟我說了一點：在有了一定語言基礎的時候，閱讀靠譜的文字版教程比看視頻的學習效率要高得多，有實在不懂的知識點再找視頻看看。這個經驗我覺得非常有用。

數據結構和演算法

我們繼續跳戲了，沒有繼續《大話數據結構》的內容，初步了解了一下哈希表，有關哈希表的的內容的確很多，這裡我只是希望用簡單的例子讓大家對哈希表有一個概念性的認識。

一.我學了哪些資料

首先我要說明一點，隨著Java的更新，其中的hashMap的實現方式也在隨著更新，但是基本的實現理論都是一樣的。我參考了一篇博客哈希表、Java中HashMap - CSDN博客，做了一個總結。

哈希表是什麼？哈希函數是什麼？

有一個問題：我們是如何在數據結構中做查找的呢？

在線性表、樹這些結構中，記錄在結構中的相對位置是隨機的，和記錄的關鍵字之間不存在確定關係，因此，在結構中查找時需要進行一系列和關鍵字的比較，查找的效率依賴於查找過程中所進行的比較次數。

哈希表是一種數據結構，理想的情況是希望不經過任何比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的關係f，使每個關鍵字和結構中一個唯一的存儲位置相對應。因而在查找時，只要根據這個對應關係f找到給定值K的像f(K)。若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上，反之在這個位置上沒有記錄。由此，不需要比較便可直接取得所查記錄。在此，我們稱這個對應關係f為哈希(Hash)函數 ，按這個思想建立的表為哈希表 。

根據設定的Hash函數 - H(key)和處理衝突的方法，將一組關鍵字映象到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的象作為記錄在表中的存儲位置，這樣的表便稱為Hash表 。

但是哈希表不是完美的，不同的數據關鍵字經過哈希函數計算後，有可能得到了同樣的地址，我們稱這種情況為衝突，我們不僅要找一個好的哈希函數，也要找一個好的解決衝突的辦法。

有什麼應用

多用於存儲數據並進行快速查找。

如何實現（這個問題的確很複雜，這一篇我只能先簡要介紹下了）

哈希函數

有直接定址法，數字分析法，平方取中法，摺疊法，隨機數法，除留取余法，等等。主要解釋下最簡單，最常用的除留取余法。
除留取余法：f(k)=k mod p ， p<=m，取關鍵字被某個不大於Hash表 長m 的數p 除後所得的餘數為Hash地址 。值得注意的是，在使用除留取余法 時，對p 的選擇很重要，如果p 選的不好會容易產生同義詞 。由經驗得知：p 最好選擇不大於表長m 的一個質數、或者不包含小於20的質因數的合數。

解決衝突

有開放定址法，再哈希法，公共溢出區，鏈地址法，這裡介紹下比較簡單的鏈地址法。
鏈地址法：將所有關鍵字經過哈希函數計算後得到相同地址的數據元素存儲在同一線性表中，即在Hash 出來的哈希地址中不直接存數據元素，而是存儲一個數據元素的鏈表，當發生衝突時，將同地址的數據元素加入鏈表。

一個簡單實現的例子：下圖即是用除留取余法結合鏈地址法處理衝突實現的一個哈希表。

二.學霸指點：難點分析和面試高頻問題

學霸說簡單的對一種數據結構的工具包調用還是比較簡單的，如果能做到理解數據結構的具體實現方法，無論是對語言的掌握還是學習能力的提升都是很有幫助的。

三.我遇到的問題及解決辦法

學霸一開始給我的問題是了解Java哈希表的實現過程，然後我就去網上搜索，當找到這篇博客的時候，我以為我找到了理解Java哈希表的全部內容，但是和學霸討論的時候，學霸說，你這個理論應該是沒問題的，但是現在Java的實現方法應該不是這個樣子了，然後他打開了Java哈希表的源碼，我發現具體的實現中還有很多細節，這裡面沒有講到，還是too young，too naive，以後要找原汁原味的東西還是要直接到源碼中去。

Share學習經驗---他山之石，可以攻玉

不要想太多，先學著做個HelloWorld,這是進入一個新領域的最快最有效的方法。

我發現學霸有一個習慣，無論是學習新的語言，還是新的模型，他總是直擊自己的需求，快速的把這個領域有關自己需求的最基本的HelloWorld搞定，然後再根據自己的需求去更具體的優化，修改。我每次學習一個新東西的時候總是想著有很多東西，要先把基礎看了，一步一步來，經常自己花了很多時間，看了很多東西，但是自己最開始的需求還沒有解決，這種不好的學習習慣一定要杜絕。

年底的北京真冷，晚上零下十幾度，還是要在外場修飛機~~~唉，不知道要說什麼，給大家拜個早年吧！！！