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

06-03

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

來自專欄人人都是演算法工程師

筆記也許會遲到，但一定不能缺席！！！補一篇第七個月的！

這個月的筆記雖然遲到了，但這是我取得突破性進展的一個月，我基本能夠獨立自主的學習，並且梳理知識點了。機器學習方面我完成了邏輯斯蒂回歸這一章的學習，數據結構和演算法，編程語言方面都有了一些進展，下面進行詳述。

機器學習方面

本月主要完成了《機器學習基石》第十章 Logistic Regression 的學習，一共四節，視頻時長66分鐘，配以《統計學習方法》第6.1節邏輯斯蒂回歸模型，我一共大概花了3.5h用來學習。我首先要說明一點的是，大家不要被 Logistic Regression這個名字嚇到了，其實框架內容是比較簡單易學的，就是線性回歸套上了一個Logistic 函數。

一. 我學了那些資料

1.《機器學習基石》第十章 Logistic Regression，我們用下面這四個問題去引領這一章的學習。

邏輯斯蒂回歸解決什麼樣的問題？

解決soft classification的問題，即軟性二分類問題。以預測一個病人是否會得心臟病為例，我們不再是絕對的預測他是否得病，我們要預測他得心臟病的概率，模型輸出的空間是連續的，在0至1之間，越接近於1說明病人患病的概率越大。

目標函數為: $f(X)=P(1|X)in [0,1]$ （10-1）

理想的數據應該為：

但是實際的數據可以看成含有雜訊的理想數據：

邏輯斯蒂回歸是什麼樣的？

在解決軟性二元分類的假設函數的設計問題上，我們類比之前的二元分類和線性回歸，也要計算個人特徵數據 $X=(x_{0},x_{1},...,x_{d})$ 的加權分數 $S=sum_{i=0}^{d}{w_{i}x_{i}}=W^{T}X$ ,分數越大說明得心臟病的概率越大，那如何將此實數範圍內的分數轉換為[0,1]內的概率呢，大牛們給出的答案是套上一個logistic函數（關於為什麼是logistic函數不是其他函數，請有興趣的同學自行探索）。

logistic函數的解析式為： $heta(S)=frac{e^{s}}{1+e^s}=frac{1}{1+e^{-s}}$ （10-2）

logistic函數是一個處處可微，單調（monotonic）的S形（sigmoid）函數，因此又被稱為sigmoid函數。

因此軟性二元分類的假設函數可以重寫為： $h(X)=frac{1}{1+e^{-W_TX}}$ （10-3）

邏輯斯蒂回歸的錯誤函數

由正例和負例的概率相加要為1，可以推出目標函數以下性質： $f(X)=P(1|X)in [0,1]Leftrightarrow P(y|X)=left{egin{matrix} f(X)(y=+1)\ 1-f(X)(y=-1) end{matrix} ight.$ （10-4）

若有訓練數據集 $D=egin{Bmatrix} (X_{1},circ ),(X_{2}, imes ),...,(X_{N}, imes ) end{Bmatrix}$

設那麼通過目標函數f產生此種訓練集D的概率為輸入樣本產生概率P(X)及產生對應標記的概率的乘積： $P(D)=P(X_{1})P(circ |X_{1})*P(X_{2})P( imes |X_{2})*...*P(X_{N})P( imes |X_{1})$ （10-5）

帶入目標函數性質化簡為：

$P(D)=P(X_{1})f(X_{1})*P(X_{2})(1-f(X_{2}))*...*P(X_{N})(1-f(X_{N}))$ （10-6）

$f(X)$ 是未知的，我們用 $h(X)$ 去逼近 $f(X)$ ,那麼通過假設函數h產生D的概率，即似然函數為：

$P(D)=P(X_{1})h(X_{1})*P(X_{2})(1-h(X_{2}))*...*P(X_{N})(1-h(X_{N}))$ （10-7）

因為我們的假設函數h和f非常接近，那麼h產生此訓練數據集D的可能性或(likehood)和f產生同樣數據集D的可能性(probility)也很接近，目標函數f既然產生了這樣的訓練數據集D，那麼可以認為函數f產生該數據集D的可能性很大。那麼可以推斷出最好的假設函數g，應該是似然最大的假設函數h。強烈建議大家重新學習下最大似然估計法，這裡用的就是這個原理。

$g=argmax( likehood(h))$ （10-8）

當我們的假設函數h使用如(10-3)logistic函數的時候，有性質如下：

$h(-X)=1-h(X)$ (10-9)

帶入似然函數(10-7)，消除P(X)的影響，因為對於任何一個假設函數來說,P(X)都是一樣的，得到關於似然函數的表達式：

$likehood(logistic h) propto prod_{n=1}^{N}h(y_{n}X_{n})$ （10-10）

上式巧妙的將 $y_{n}$ 放入公式中來表達 $X_{n }$ 的符號，使表達式變得簡潔。將 $h(X)= heta(W^T X)$ 帶入(10-10)，再帶入(10-8)，得到我們最終的極大似然函數表達式：

$underset{W}{max}(likehood(W) propto prod_{n=1}^{N} heta (y_{n}W^TX))$ （10-11）

接下來為了計算方便，做了兩點處理，加入負號，將求最大值問題轉換為求最小值問題，利用求對數，將連乘問題轉化為連加問題,為了與之前研究的問題類似，加入了 $frac{1}{N}$ 求平均，得到：

$underset{W}{min} frac{1}{N} sum_{n=1}^{N}-ln heta (y_{n}W^TX))$ （10-12）

之後將 $heta$ 的具體表達式帶入，化簡得到：

$underset{W}{min} frac{1}{N} sum_{n=1}^{N}ln(1+exp(-y_{n}W^TX))$ （10-13）

我們對照之前研究的模型，定義：

$E_{in}(W)=frac{1}{N} sum_{n=1}^{N}ln(1+exp(-y_{n}W^TX))$ (10-14)

即（10-14）最小值時，所得W就為我們需要的假設函數的參數。

我們又稱 $error(W,X,y)ln(1+exp(-y_{n}W^TX))$ 為交叉熵錯誤(cross-entropy error)。

如何求解參數

梯度的求解林老師講了一小節課，但是我們絕大多數人應該不聽這節課也會求梯度，就是普通的複合函數求導，高端的一點的叫法稱為「連鎖律」，其梯度為：

$igtriangledown E_{in}(W)=frac{1}{N} sum_{n=1}^{N} heta (-y_{n}W^TX_{n})(-y_{n}X_{n})$

最小化 $E_{in}(W)$ ，我們想到的方法就是求梯度，令梯度為零求其解析解,其中一種情況比較好求解，林老師解釋了，就是至少要線性可分。

其他情況解析解難求，就利用梯度下降法，關於梯度下降法林老師著重解釋了為甚麼負梯度方向為函數下降最快的方向（表示聽的不是很透徹，結論先記住拿來用吧），使用方法我們上一篇已經討論過類似的了，詳見機務？演算法工程師！轉職筆記（七）。

2.《統計學習方法》第六章邏輯斯蒂回歸部分

此部分和林老師的講解基本一致，只是推導細節在表現形式上略有不同，但是更簡練，建議掌握作為面試手撕使用。

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

請戳邏輯回歸的常見面試點總結 - ModifyBlog - 博客園

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

邏輯斯蒂回歸這部分的內容還是比較長的，建議找幾篇好的博客，自己梳理下思路，便於記憶。我參考了機器學習基石筆記10--機器可以怎樣學習（2） - 杜少 - 博客園
實際訓練數據和理想數據的差異在哪裡？

理想數據要的標籤是一個人得病的概率，而實際數據的標籤只有得病與未得病兩種極端情況。

極大似然估計法的理解

參考最大似然估計和最小二乘法怎麼理解？

編程語言

由於時間有限，畢向東Java基礎視頻（35天版本）依然是在零碎的時間觀看，上下班路上，休息的間隙都拿出手機看一小節，所以梳理的知識點可能不像機器學習那麼緊密並且有邏輯，但是大家自己學習的時候最好做個腦圖，把邏輯梳理清楚。

一.我學了哪些資料

1.畢向東Java基礎視頻（35天版本）的繼承基礎和抽象類與介面部分。

直接上腦圖了，繼承基礎部分。

抽象類與介面

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

怎麼說呢？學霸說Java的基礎，尤其是面向對象部分都是重點。。。

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

Java的學習我一直是以用零碎時間看視頻為主的，學習進度比較慢，複習再翻視頻也比較麻煩，特別是一些基礎代碼部分，後來我發現之前傳的資料當中有一個名為：「Java_SE基礎畢向東老師全程筆記.pdf」的東西，這應該是當初某個大佬的學習筆記，寫得非常仔細全面，非常適合複習的時候快速review，建議找來看看。

數據結構和演算法

新學習了二分查找。複習了冒泡排序，選擇排序，反轉鏈表，複習的內容不再贅述。

一.我學了哪些資料

二分查找

/*需求：二分查找，傳入數組和查詢目標值，如果找到目標值，返回下標，如果未查詢到，返回應該插入的位置。實現思路：定義三個下標，left，mid，right。每次mid取left和right的中間值，比較target和 arr[mid]的值。如果相等，直接返回。若a[mid]<target,,則left=mid+1；若a[mid]>target,則right=mid-1；重複上述動作，直到找到arr[mid]=target，或者下標l>r跳出循環，會出現三種情況導致跳出： 1.target比a[0]小，跳出循環前，l=r=mid=0，之後，a[mid]>target,則right=mid -1=- 1，越界跳出循環，此時返回left就是target該插入的位置。 2.target>a[length],跳出循環前，l=r=a[length-1],之後，a[mid]<target,l=m id+1 =length，同上。 3.target在a[k]和a[k+1]之間，跳出循環前，要麼是l=r=mid=k.要麼是l=r=k+1,然後類似如上分別跳出循環，得到left為target插入位置。由此可見，最後都是返回了left */ public static int searchInsert(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int left = 0; int right = nums.length - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) return mid; if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return left; } public static void main(String[] args) { int[] a={1,3,5,6}; int ret=searchInsert(a,10); System.out.println(ret); }

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

學霸說他當時面試的時候有兩次剛開始就是在紙上寫這個題，面試問這個問題相關內容的概率超級高。

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

在while循環中為啥總是返回left？

這就是二分查找中我遇到的問題，搜索了些關鍵詞，一開始沒有找到特別好的解釋，所以最後我就寫了幾個簡單的數組，按程序實際的運行過程，一步一步手寫運行邏輯，發現最後跳出循環不外乎以上提到實現思路中提到的三種情況，特別是數據結構和演算法題目中建議大家多寫寫畫畫，可以增加對題目的理解。

但是發文前，學霸給了個鏈接，讓我拓展一下關於二分查找的知識，於是我發現了新世界，原來還有這麼多玩法，詳情請戳：二分查找有幾種寫法？它們的區別是什麼？

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

最近在讀劉未鵬的《暗時間》，關於學習與思考的非常棒的書！！！強烈推薦。

我發現我和學霸之前討論過的一些關於學習的話題，書里都提到了，並且給了比較詳細的解釋，推薦給大家，站在巨人的肩膀上學習，希望我們都能有所進步。

這裡暫提一點，書中在談到時間和效率的時候提到了如何閱讀資料的方法我覺得自己深有體會：根據主題、問題來查閱資料，讀幾本書的某些相關章節，看幾個主題博客。這樣不僅能夠比較快的了解一個主題，避免在無關內容上浪費時間，也能通過不同作者的不同角度，多個方面全面的認識一個問題，有時如果你幸運的話，會發現有些博客，乾脆利落的把一個主題講的簡潔易懂，比別人很多書上的章節講得都好，真是帥爆了。希望大家在學習的過程中多多應用這一方法，提高效率。

在完成此文的時候北京的春天已經大張旗鼓的來了，但我還是忍不住要吐槽一下剛剛過去的冬天，真是漫長難捱，加之一些其他事情，倍感疲憊，不過終究都還是過去了,事情都在好轉。前一段時間我和學霸聊起過去的這一年，覺得雖然偶有不如意之事，但總體上我們都還是挺享受正在做的事情，方向也沒有太大偏差，感覺也挺有力量，希望在新的一年裡，我們能夠輸出更多東西，繼續嘗試一些想做的事情，祝各位安好！過幾天見！