dsvm演算法

❶ 支持向量機原理

支持向量機原冊悶理SVM簡介
支持向量機（support vector machines, SVM）是一種二分類模型，它的基本模型是定義在特徵空間上的間隔最大的線性分類器，間隔最大使它有別於感知機；SVM還包括核技巧，這使它成為實質上的非線性分類器。SVM的的學習策略就是間隔最大化，可形式化為一個求解凸二次規劃的問題，也等價於正則化的合頁損失函數的最小化問題。SVM的的學習演算法就是求解凸二次規劃的最優化演算法。

SVM演算法原理
SVM學習的基本想法是求解能夠正確劃分訓練數據集並且幾何間隔最大的分離超平面。如下圖所示， \boldsymbol{w}\cdot x+b=0 即為分離超平面，對於線性可分的數據集來說，這樣的超平面有無窮知姿碼多個（即感知機），但是幾何間隔最大的分離超平面卻是唯一的。

在推導之前，先給出一些定義。假設給定一個特徵空間上的訓練數據集

T=\left\{ \left( \boldsymbol{x}_1,y_1 \right) ,\left( \boldsymbol{x}_2,y_2 \right) ,...,\left( \boldsymbol{x}_N,y_N \right) \right\}

其中， \boldsymbol{x}_i\in \mathbb{R}^n ， y_i\in \left\{ +1,-1 \right\} ,i=1,2,...N ， x_i 為第 i 個特徵向量， y_i 為類標記，當它等於+1時為正例；為-1時搭哪為負例。再假設訓練數據集是線性可分的。

幾何間隔：對於給定的數據集 T 和超平面 w\cdot x+b=0 ，定義超平面關於樣本點 \left( x_i,y_i \right) 的幾何間隔為

\gamma _i=y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert} \right)

超平面關於所有樣本點的幾何間隔的最小值為

\gamma =\underset{i=1,2...,N}{\min}\gamma _i

實際上這個距離就是我們所謂的支持向量到超平面的距離。

根據以上定義，SVM模型的求解最大分割超平面問題可以表示為以下約束最優化問題

\underset{\boldsymbol{w,}b}{\max}\ \gamma

s.t.\ \ \ y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert} \right) \ge \gamma \ ,i=1,2,...,N

將約束條件兩邊同時除以 \gamma ，得到

y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert \gamma}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert \gamma} \right) \ge 1

因為 \lVert \boldsymbol{w} \rVert \text{，}\gamma 都是標量，所以為了表達式簡潔起見，令

\boldsymbol{w}=\frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert \gamma}

b=\frac{b}{\lVert \boldsymbol{w} \rVert \gamma}

得到

y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1,\ i=1,2,...,N

又因為最大化 \gamma ，等價於最大化 \frac{1}{\lVert \boldsymbol{w} \rVert} ，也就等價於最小化 \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2 （ \frac{1}{2} 是為了後面求導以後形式簡潔，不影響結果），因此SVM模型的求解最大分割超平面問題又可以表示為以下約束最優化問題

\underset{\boldsymbol{w,}b}{\min}\ \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2

s.t.\ \ y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1,\ i=1,2,...,N

這是一個含有不等式約束的凸二次規劃問題，可以對其使用拉格朗日乘子法得到其對偶問題（al problem）。

首先，我們將有約束的原始目標函數轉換為無約束的新構造的拉格朗日目標函數

L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\lVert \boldsymbol{w} \rVert ^2-\sum_{i=1}^N{\alpha _i\left( y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1 \right)}

其中 \alpha _i 為拉格朗日乘子，且 \alpha _i\ge 0 。現在我們令

\theta \left( \boldsymbol{w} \right) =\underset{\alpha _{_i}\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right)

當樣本點不滿足約束條件時，即在可行解區域外：

y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) <1

此時，將 \alpha _i 設置為無窮大，則 \theta \left( \boldsymbol{w} \right) 也為無窮大。

當滿本點滿足約束條件時，即在可行解區域內：

y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1

此時， \theta \left( \boldsymbol{w} \right) 為原函數本身。於是，將兩種情況合並起來就可以得到我們新的目標函數

\theta \left( \boldsymbol{w} \right) =\begin{cases} \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2\ ,\boldsymbol{x}\in \text{可行區域}\\ +\infty \ \ \ \ \ ,\boldsymbol{x}\in \text{不可行區域}\\ \end{cases}

於是原約束問題就等價於

\underset{\boldsymbol{w,}b}{\min}\ \theta \left( \boldsymbol{w} \right) =\underset{\boldsymbol{w,}b}{\min}\underset{\alpha _i\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =p^*

看一下我們的新目標函數，先求最大值，再求最小值。這樣的話，我們首先就要面對帶有需要求解的參數 \boldsymbol{w} 和 b 的方程，而 \alpha _i 又是不等式約束，這個求解過程不好做。所以，我們需要使用拉格朗日函數對偶性，將最小和最大的位置交換一下，這樣就變成了：

\underset{\alpha _i\ge 0}{\max}\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =d^*

要有 p^*=d^* ，需要滿足兩個條件：

① 優化問題是凸優化問題

② 滿足KKT條件

首先，本優化問題顯然是一個凸優化問題，所以條件一滿足，而要滿足條件二，即要求

\begin{cases} \alpha _i\ge 0\\ y_i\left( \boldsymbol{w}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1\ge 0\\ \alpha _i\left( y_i\left( \boldsymbol{w}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1 \right) =0\\ \end{cases}

為了得到求解對偶問題的具體形式，令 L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) 對 \boldsymbol{w} 和 b 的偏導為0，可得

\boldsymbol{w}=\sum_{i=1}^N{\alpha _iy_i\boldsymbol{x}_{\boldsymbol{i}}}

\sum_{i=1}^N{\alpha _iy_i}=0

將以上兩個等式帶入拉格朗日目標函數，消去 \boldsymbol{w} 和 b ， 得

L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _iy_i\left( \left( \sum_{j=1}^N{\alpha _jy_j\boldsymbol{x}_{\boldsymbol{j}}} \right) \cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) +}\sum_{i=1}^N{\alpha _i}

\ \ \ \ \ \ \ \ \ \ \ =-\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}+\sum_{i=1}^N{\alpha _i}

即
\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =-\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\al

❷ 支持向量機（SVM）

參考Jerrylead 和 july-支持向量機通俗導論

再回憶一下邏輯回歸：Logistic回歸目的是從特徵學習出一個0/1分類模型，而 這個模型是將特徵的線性組合作為自變數 ，由於自變數的取值范圍是負無窮到正無窮。因此，使用logistic函數（或稱作sigmoid函數） 將自變數映射到(0,1)上，映射後的值被認為是屬於y=1的概率 。

中間那條線是θ T x=0，logistic回歸強調 所有點 盡可能地遠離中間那條線。學習出的結果也就中間那條線。
但是：
考慮上面3個點A、B和C。從圖中我們可以確定A是×類別的， 然而C我們是不太確定的 ，B還算能夠確定。這樣我們可以得出結論， 我們更應該關心靠近中間分割線的點，讓他們盡可能地遠離中間線，而不是在所有點上達到最優（引出了下面的函數間隔與幾何間隔） 。

我想這就是支持向量機的思路和logistic回歸的不同點：
支持向量機考慮局部（不關心已經確定遠離的點），
邏輯回歸一個考慮全局（已經遠離的點可能通過調整中間線使其能夠更加遠離，但是也可能使一部分點靠近中間線來換取另外一部分點更加遠離中間線。）

上面已經知道，θ T x=0是分類的線，在svm中，只考慮局部，只考慮θ T x的正負問題，而不用關心g（z）。因此，在這里，用w T x+b代替θ T x，並 對g(z)做一個簡化 ，將其簡單映射到類別標簽y=1和y=-1上。

這里的y取值為1和-1（在svm中，只考慮局部，只考慮θ T x的正負問題），是為了方便定義：在分類正確的情況下，函數間隔（確信度 ）的大小

比如，在分類正確的情況下，y等於1，wx+b應該為正數越大，則情況越好，是正例的確定度就越大。就如上圖的A點。y等於-1，wx+b應該為負數越大，則情況越好是負例的確信度就越大。

所以， 函數間隔越大，說明分類正確的置信度越大。函數間隔越小 ，比如上圖c點，說明越不能確定c點屬於哪一類。

可以為 別的值，只是為了方便。這一點在參考的第二個博客上也已經說明了。

由上面解釋，已知可以用y(wT x + b) 的正負性來判定（或表示）分類的正確性。

定義函數間隔如下：

也就是，這個樣本點x與超平面之間的間隔（但是現在有些不準確，所以有下面的幾何間隔）。

此時，若根據SVM的思想，最大化這個間隔，就能提高分類正確的確信度了嗎？

答案是否定的，因為，如果成比例的改變w 和b（如將它們改成2w 和2b），則函數間隔的值f(x) 卻變成了原來的2 倍（ 雖然函數值增大了，達到了目標，但是此時超平面沒有改變 ），所以只有函數間隔還遠遠不夠。

我們真正關心的，其實是「幾何上」的點到平面的距離，於是可以用幾何知識推理出來的幾何間隔。 而不是一開始人們想當然定義的函數間隔。

事實上，我們可以對法向量w 加些約束條件（ 這就是調優問題的思考了 )，從而引出真正定義點到超平面的距離——幾何間隔（geometrical margin）的概念。

又因為x 0 是超平面w T x + b=0上的點，利用向量之間的運算

再令上式乘上對應的類別y，即可得出幾何間隔

從上述函數間隔和幾何間隔的定義可以看出：幾何間隔就是函數間隔除以∥w∥，而 函數間隔實際上就是，只是人為定義的一個間隔度量，而幾何間隔才是直觀上的點到超平面的距離。

接下來就是我們的目標：尋找一個超平面， 使得離超平面比較近的點能有更大的間距。 也就是我們不考慮所有的點都必須遠離超平面，我們關心求得的超平面能夠讓所有點中離它最近的點具有最大間距。也就是找到最大的幾何間隔。

由上一小節可以知道，我們這里要找的最大間隔分類超平面中的「間隔」指的是幾何間隔。

上面兩個式子的意思是（ 注意，函數間距上面是折線，幾何間距上面是波浪線 ）：
最大化幾何間隔
約束條件是，每個樣例的函數間隔都要大於全局的那一個函數間隔（也就是所有訓練集里的最小的那個）

用函數間隔表示幾何間隔

於是得到了這個式子：

然而這個時候目標函數不是凸函數，約束條件也不是線性的，沒法直接代入優化軟體里計算。我們還要改寫。前面說到 同時擴大w和b對結果沒有影響 ，因此，我們將全局的函數間隔值定義為1。於是，上述的函數轉變成了

由於求1/||w||的最大值，相當於求||w||²的最小值，因此結果為：

因為現在的 目標函數是二次的，約束條件是線性的，所以它是一個凸二次規劃問題 。這個問題可以用現成的QP (Quadratic Programming) 5優化包進行求解。一言以蔽之：在一定的約束條件下，目標最優，損失最小。

根據前面幾個文章的話，SVM作為判別模型，它的的模型，就是 w T x i + b 。參數就是w和b。學習完參數以後，新來的樣例作為x i ，得到結果大於1，說明在超平面上面，所以是正例。反之亦然。

根據SVM的思想，SVM的初步目標函數，就是所有樣例的幾何間隔盡可能的大

至此，得到了SVM的目標函數，算是初步解決了SVM的這個問題，用優化包求解得到wb，即可得到具有最大幾何間距的超平面，提高分類每個點的確信度，分類目標完成。

接下來介紹的是手工求解w和b的方法了，一種更優的求解方法。

從上可以看出 ，就同時擴大w和b就相當於等式兩邊同時除以函數間隔 γ，而新的w和b仍然是舊的wb的函數，所以最大化仍然可以進行。

效果等價於，令函數間隔γ=1，綜上所述，零γ=1是合理的，而且也方便了原優化問題的計算 。

由拉格朗日對偶（線性可分條件下SVM的對偶演算法）引入核函數（非線性可分條件下SVM的演算法）

上一篇說到，得到了 如下的線性可分的SVM的目標函數 ，可以利用優化包進行求解。

此外，由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數(al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法。

引入對偶的優點：

因為 引入拉格朗日運算元可以求出極值。 （參考最優化方法的解釋）

這種極值問題怎麼求

首先，同樣定義拉格朗日公式，希望可以利用拉格朗日運算元法求得最優解，得到：

但是，出現問題了，此時加入的約束條件g已經不再等於0了，所以，此時可以調整運算元alpha變成很大很大的 值，使結果負無窮， 這顯然是不合理的。

所以，我們需要 排除在滿足條件下，也會無解的情況。

因此，我們定義下面的函數

要看這個函數有什麼優點，就要看看這個函數相比於L(ω,α,b)有什麼變化： 加了max，加了α I 大於等於零。

所以，當g和h不滿足約束時，總可以調整α i 和β i 來使thetap具最大值為正無窮。

只有當g和h滿足約束時，此時g<0，我們可以調整α i 和β i （使α i 等於0，β i 任意），得到最大值，即θ p =f(w)。

於是函數等價於這樣

於是原來的極值問題min f(w) 就等價於求min θ p 了，
即：

也就是說，最小化 θ p ，就是為了得到最小的 f(w)，而能有f(w)就說明了滿足約束條件。所以這個等價於原來的極值問題。

至此， 相比於拉格朗日公式L(ω,α,b)，現在即加入了拉格朗日運算元，又排除了純粹的拉格朗日公式中出現無窮的情況。

但是，又出現了新的問題，也就是，如果直接求解，首先面對的就是兩個參數（最裡面的是max，這個max問題有兩個參數），而且alpha也是不等式約束，再在w上求最小值，這個過程並不容易做。那麼應該怎麼辦呢？

在最優化課程里，當遇到不好解的優化問題時，可以轉化為原問題的對偶問題試試。
此處，d代表對偶。D--al

我們定義函數

θ D 將問題轉化為先求L(ω,α,b)關於 ω 的最小值（此時α和β是固定值），之後再求θ D 的最大值。 上來面對的是一個參數，相對簡單些。

相對於原問題，更換了min和max的順序，得到了它的對偶問題。

--------------------------------------------------------------------------------------------------------------
一般的更換順序的結果是MaxMin(X) <= MinMax(X)。也就是，此時有

對偶問題已經表示出來了，這個對偶問題也相對原問題好求，那麼，這兩個問題等價嗎？或者說，對偶問題的解是不是原問題的解呢？

需要用KKT條件來判斷了。

對於拉格朗日運算元的深入理解可以看看《最優化方法》，講義的最後一頁。

含有不等式約束的問題，常常 用KKT條件求得候選最優解

對於一般化的拉格朗日公式：

最優值 w 必須滿足以下三個條件：

----------1、L對 w 求導為零
----------2、h(w)=0
----------3、α i g i =0 ，i = 1，...，k

注意此時

第三個條件表明了KKT的思想：極值會在可行域邊界取得。 ----解釋：
-----對於一個特定的自變數w1，當自變數w1在 第 i 個 可行域邊界（g i (w1)=0）時，說明此時這個約束是起到了作用的。 這個約束是w1被g i 約束了。此時只能到g i 的平面上（即邊界），再多就出界了。。。 而對於最優解來說，就是f(w)達到最優，所以L中，除了f(w)部分，其餘應該都等於0，所以此時α>0(或許等於零也可以？疑問）

----而此時，w1在其他的約束條件g 非i 下，有g 非i (w1)<0），說明W1可以隨意些，說明此時這個約束並沒有起到作用，但是作為最優解，為了 除了f(w)部分，其餘應該都等於0 ，所以其系數α應該等於零。

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

注意：這個是傳統最優化問題的一般式，這個問題有k個不等式約束方程，所有的點都要滿足這k個不等式約束。 。假設有一百個樣本點，只有有三個極值N1，N2，N3，那麼說明其餘97個點帶入這k個方程中去都會小於零。 另外對於這三個極值點，可能會有g i (N1) = 0,除了第i個g以外，g(N1)都小於0 。然後對於極值N2，g j (N2)=0，除了第j個約束以外，其餘的g(N2)都小於0。

而本節一開始討論的問題，只有一個約束方程（因為參數只有w和b）即：y（w T x+b）>=1，所有的點（一共m個）都要滿足這個約束方程。 而關於為什麼非支持向量的系數alpha會等於零呢？也就是相當於前面的，k=1（有k個約束條件）的情況下，m個樣本點中，非支持向量的約束g<0，為了最優解，除了f(w)應該都等於零，所以alpha應該等於零。

另外可以參考這段話：

即，若d* = p* <==> x * 滿足KKT條件

由上面那句話可以知道，

折騰這么長時間，也就是為了說明，已經知道原問題

是凸優化問題，所以，只要對偶問題的自變數w滿足了KKT條件，那麼它就是對偶問題的最優解w * ，同時也是原問題的最優解了。

所以，由上可知，只要解出了2.1.3中的問題的參數w和b，也就是原問題的解了。

重新回到SVM的優化問題（其中每個約束式實際就是一個訓練樣本）：

我們將約束條件改寫為拉格朗日的形式：

由KKT條件可知，只有當函數間隔是1（g=0）的時候，α i >0。此時，這個樣例 w i 在約束平面上受到約束 。對於其它的不在線上的樣例點（g<0），極值不會在其范圍內去的，所以這些樣例點前面的系數α i =0.

實線是最大間隔超平面，假設×號的是正例，圓圈的是負例。在虛線上的點就是函數間隔是1的點，他們前面的系數α i >0， 這三個點被稱作 支持向量。

由上面問題，構造拉格朗日函數如下（沒有等式約束，所以沒有β）：

————————————————————————————————

下面我們按照對偶問題的求解步驟來一步步進行，由2.1.3可知，對偶問題的形式為：

首先求解L的最小值（最裡面的先求），此時αi是固定的，L的最小值只與w和b有關。對w和b分別求偏導數。

得到

將上式帶回到拉格朗日函數中得到，此時得到的是該函數的最小值（目標函數是凸函數）， 即裡面的min L已經求出，接下來就是求max了
代入後，化簡過程如下：

最後得到

由於最後一項是0，因此簡化為

這里，上式中左右邊的向量內積，用方括弧表示。

到這一步，拉格朗日函數只包含了一個變數α i 。接著進行下一步 ，最大化的過程，求得α i 。

假設求得了α i 就能根據求導得到的結果

求得w，然後就能得到b。

b 就是 距離超平面最近的正的函數間隔要等於離超平面最近的負的函數間隔。 （其實，由前面的那個x和圈的圖，可以認為b就是截距，這個截距b等於上下兩條虛線的截距的平均值。）

注意，這里的w，b，alpha都是 向量，都是m維的向量

至於這里的α怎麼求得，即上面的最大化問題怎麼求解，將留給下一篇中的SMO演算法來闡明。

也就是說，手動解的話，還是需要利用SMO演算法，求得α才行。

————————————————————————————————

這里考慮另外一個問題，由於前面求解中得到

用α i 代替w帶入判別模型w T x+b，得到：

也就是說， 利用判別模型對新來樣本進行判別時 ，以前新來的要分類的樣本首先根據w和b做一次線性運算，然後看求的結果是大於1還是小於1來判斷正例還是負例。大於1，說明在超平面的上面，說明是正例。同理，小於1說明在超平面的下面，說明是負例。

約束條件是wx+b-1小於等於零，所以判斷就是wx+b與1進行大小比較

現在有了alpha，不需要求出w （那b呢，b怎麼求呢，前面已經解釋，b是由離超平面最近的間隔和負的函數間隔相等。。。得到的。所以，將新來的樣本與訓練數據中 支持向量 做內積以後，再確定最大的正數函數間隔以及最小的負數函數間隔，即可。）

就沖上面這段話，支持向量的系數alpha，也不能等於0。

另外，那有人會說，與前面所有的樣本都做運算是不是太耗時了？其實不然，我們從KKT條件中得到，只有支持向量的α i >0 （不等於零）其他情況α i 是等於零的。 比如，像前面那個x和圈的圖，新來的樣本只需要和三個支持向量做運算即可 。

由此可以看到，求出α i 以後，只需要利用支持向量，就可以來判斷新來的樣例是正例還是負例了。也許這也是是為什麼叫支持向量機吧。

上面這個公式，為下面要提到的核函數（kernel）做了很好的鋪墊。

下面，先把沒求得的alpha放一放，趁著剛剛得到的這個公式的熱乎勁，再去看看核函數。

❸ 機器視覺Q&A

 A. 數據增廣

 B. 提前停止訓練

C. 添加Dropout

答案：ABC

A. SGD（stochatic gradient descent）

B. BGD（batch gradient descent）

C. Adadetla

D. Momentum

答案：C

【解析】

1）SGD受到學習率α影響

2）BGD受到batch規模m影響

3）Adagrad的一大優勢時可以避免手動調節學習率，比如設置初始的預設學習嫌拆率為0.01，然後就不管它，另其在學習的過程中自己變化。

為了避免削弱單調猛烈下降的減少學習率，Adadelta產生了1。Adadelta限制把歷史梯度累積窗口限制到固定的尺寸w，而不是累加所有的梯度平方和

4）Momentum：也受到學習率α的影響

A.懲罰了模型的復雜度，避免模型過度學習訓練集，提高泛化能力

B.剃刀原理：如果兩個理論都能解釋一件事情，那麼較為簡單的理論往往是正確的

C.正則項降低了每一次系數w更新的步伐，使參數更小，模型更簡單

D.貝葉斯學派的觀點，認為加入了先驗分布（l1拉普拉斯分布，l2高斯分布），減少參數的選擇空間

答案：ABCD

【解析】A/C選項沒有問題，只不過C中的"步伐"理解起來並不清晰。B/D選項是有點追本溯源的意思，剃刀原理其實是奧卡姆剃刀原理：更小的權值w，從某種意義上說，表示網路的復雜度更低，對數據的擬合剛剛好；從貝葉斯角度理解，為參數ω引入拉普拉斯先驗分布的最大似然，相當於給均方誤差函數加上L1正則項；為參數ω引入高斯先驗分布的最大似然，相當於給均方誤差函數加上L2正則項。

a.計算預測值和真實值之間的誤差

b.重復迭代，直至得到網路權重的最佳值

c.把輸入傳入網路，得到輸出值

d.用隨機值初始化權重和偏差

e.對每一個產生誤差的神經元，調整相應的（權重）值以減小誤差

答案：dcaeb

A.懲罰了模型的復雜度，避免模型過度學習訓練集，提高泛化能力

B.剃刀原理：如果兩個理論都能解釋一件事情，那麼較為簡單的理論往往是正確的

C.正則項降低了每一次系數w更新的步伐，使參數更小，模型更簡單

D.貝葉斯學派的觀點，認為神者野加入了先驗分布（l1拉普拉斯分布，l2高斯分布），減少參數的選擇空間

答案：ABCD

【解析】A/C選項沒有問題，只不過C中的"步伐"理解起來並不清晰。B/D選項是有點追本溯源的意思，剃刀原理其實是奧卡姆剃刀原理：更小的權值w，從某種意義上說，表示網路的復雜度更低，對數據的擬合剛剛好；從貝葉斯角度理解，為參數ω引入拉普拉斯先驗分布的最大似然，相當於給均方誤差函數加上L1正則項；為參數ω引入高斯先驗游喊分布的最大似然，相當於給均方誤差函數加上L2正則項。

參考：

[正則化為什麼能防止過擬合（重點地方標紅了）](https://www.cnblogs.com/alexanderkun/p/6922428.html)

[【機器學習】從貝葉斯角度理解正則化緩解過擬合](https://blog.csdn.net/u014433413/article/details/78408983)

A. 220x220x5

B. 218x218x5

C. 217x217x8

D. 217x217x3

答案：B

【解析】卷積計算公式：Hout=（Himg+2Padding−Kfilterh）/S + 1；Wout=（Wimg+2Padding−Kfilterw）/S + 1。其中Padding是邊界填空值，Kfilterw表示卷積核的寬度，S表示步長。

A.少於2秒

B.大於2秒

C.仍是2秒

D.說不準

答案：C

【解析】在架構中添加Dropout這一改動僅會影響訓練過程，而並不影響測試過程。

A.准確率適合於衡量不平衡類別問題

B.精確率和召回率適合於衡量不平衡類別問題

C.精確率和召回率不適合於衡量不平衡類別問題

D.上述選項都不對

答案：B

A. Boosting

B. Bagging

C. Stacking

D. Mapping

答案：B

【解析】dropout的思想繼承自bagging方法。

bagging是一種集成方法（ensemble methods）,可以通過集成來減小泛化誤差（generalization error）。

bagging的最基本的思想是通過分別訓練幾個不同分類器，最後對測試的樣本，每個分類器對其進行投票。在機器學習上這種策略叫model averaging。 我們可以把dropout類比成將許多大的神經網路進行集成的一種bagging方法。

1. 隨機初始化感知機權重

2. 去到數據集的下一批（batch）

3. 如果預測值和輸出不一致，則調整權重

4. 對一個輸入樣本，計算輸出值

A. 1,2,3,4

B. 4,3,2,1

C. 3,1,2,4

D. 1,4,3,2

答案：D

11.【單選題】下列哪項關於模型能力（model capacity）的描述是正確的？（指神經網路模型能擬合復雜函數的能力）

A.隱藏層層數增加，模型能力增加

B. Dropout的比例增加，模型能力增加

C.學習率增加，模型能力增加

D.都不正確

答案：A

A. Logistic回歸可用於預測事件發生概率的大小

B. Logistic回歸的目標函數是最小化後驗概率

C. SVM的目標的結構風險最小化

D. SVM可以加入正則化項，有效避免模型過擬合

答案：B

【解析】Logistic回歸本質上是一種根據樣本對權值進行極大似然估計的方法，而後驗概率正比於先驗概率和似然函數的乘積。Logistic僅僅是最大化似然函數，並沒有最大化後驗概率，更談不上最小化後驗概率。A正確 Logit回歸的輸出就是樣本屬於正類別的幾率，可以計算出概率；C正確. SVM的目標是找到使得訓練數據盡可能分開且分類間隔最大的超平面，應該屬於結構風險最小化. D正確. SVM可以通過正則化系數控制模型的復雜度，避免過擬合。

A增加訓練集量

B減少神經網路隱藏層節點數

C刪除稀疏的特徵

D SVM演算法中使用高斯核/RBF核代替線性核

答案：D

【解析】一般情況下，越復雜的系統，過擬合的可能性就越高，一般模型相對簡單的話泛化能力會更好一點。

B.一般認為，增加隱層數可以降低網路誤差（也有文獻認為不一定能有效降低），提高精度，但也使網路復雜化，從而增加了網路的訓練時間和出現「過擬合」的傾向， svm高斯核函數比線性核函數模型更復雜，容易過擬合

D.徑向基(RBF)核函數/高斯核函數的說明,這個核函數可以將原始空間映射到無窮維空間。對於參數 ，如果選的很大，高次特徵上的權重實際上衰減得非常快，實際上（數值上近似一下）相當於一個低維的子空間；反過來，如果選得很小，則可以將任意的數據映射為線性可分——當然，這並不一定是好事，因為隨之而來的可能是非常嚴重的過擬合問題。不過，總的來說，通過調整參數 ，高斯核實際上具有相當高的靈活性，也是 使用最廣泛的核函數 之一。

A.感知准則函數

B.貝葉斯分類

C.支持向量機

D.Fisher准則

答案：ACD

【解析】

線性分類器有三大類：感知器准則函數、SVM、Fisher准則，而貝葉斯分類器不是線性分類器。

感知准則函數 ：准則函數以使錯分類樣本到分界面距離之和最小為原則。其優點是通過錯分類樣本提供的信息對分類器函數進行修正，這種准則是人工神經元網路多層感知器的基礎。

支持向量機 ：基本思想是在兩類線性可分條件下，所設計的分類器界面使兩類之間的間隔為最大，它的基本出發點是使期望泛化風險盡可能小。（使用核函數可解決非線性問題）

Fisher准則 ：更廣泛的稱呼是線性判別分析（LDA），將所有樣本投影到一條遠點出發的直線，使得同類樣本距離盡可能小，不同類樣本距離盡可能大，具體為最大化「廣義瑞利商」。

根據兩類樣本一般類內密集，類間分離的特點，尋找線性分類器最佳的法線向量方向，使兩類樣本在該方向上的投影滿足類內盡可能密集，類間盡可能分開。這種度量通過類內離散矩陣 Sw和類間離散矩陣 Sb實現。

A.卷積神經網路

B.循環神經網路

C.全連接神經網路

D.選項A和B

答案：D

A.L2正則項，作用是最大化分類間隔，使得分類器擁有更強的泛化能力

B.Hinge損失函數，作用是最小化經驗分類錯誤

C.分類間隔為1/||w||，||w||代表向量的模

D.當參數C越小時，分類間隔越大，分類錯誤越多

答案：C

A正確。考慮加入正則化項的原因：想像一個完美的數據集，y>1是正類，y<-1是負類，決策面y=0，加入一個y=-30的正類雜訊樣本，那麼決策面將會變「歪」很多，分類間隔變小，泛化能力減小。加入正則項之後，對雜訊樣本的容錯能力增強，前面提到的例子裡面，決策面就會沒那麼「歪」了，使得分類間隔變大，提高了泛化能力。

B正確。

C錯誤。間隔應該是2/||w||才對，後半句應該沒錯，向量的模通常指的就是其二范數。

D正確。考慮軟間隔的時候，C對優化問題的影響就在於把a的范圍從[0，+inf]限制到了[0,C]。C越小，那麼a就會越小，目標函數拉格朗日函數導數為0可以求出w=求和ai∗yi∗xi，a變小使得w變小，因此間隔2/||w||變大。

A.Dropout

B.分批歸一化(Batch Normalization)

C.正則化(regularization)

D.上述選項都可以

答案：D

A.95

B.96

C.97

D.98

答案：C

A.(AB)C

B.AC(B)

C.A(BC)

D.上述所有選項效率相同

答案：A

【解析】首先，根據簡單的矩陣知識，因為 A*B， A的列數必須和 B的行數相等。因此，可以排除 B選項，

然後，再看 A、 C選項。在 A選項中，m∗n的矩陣 A和n∗p的矩陣 B的乘積，得到 m∗p的矩陣 A\*B，而 A∗B的每個元素需要 n次乘法和 n-1次加法，忽略加法，共需要 m∗n∗p次乘法運算。同樣情況分析 A*B之後再乘以 C時的情況，共需要 m∗p∗q次乘法運算。因此， A選項 (AB)C需要的乘法次數是 m∗n∗p+m∗p∗q。同理分析， C選項 A (BC)需要的乘法次數是 n∗p∗q+m∗n∗q。

A.把除了最後一層外所有的層都凍結，重新訓練最後一層

B.對新數據重新訓練整個模型

C.只對最後幾層進行調參(fine tune)

D.對每一層模型進行評估，選擇其中的少數來用

答案：C

【解析】如果有個預先訓練好的神經網路,就相當於網路各參數有個很靠譜的先驗代替隨機初始化.若新的少量數據來自於先前訓練數據(或者先前訓練數據量很好地描述了數據分布,而新數據采樣自完全相同的分布),則凍結前面所有層而重新訓練最後一層即可;但一般情況下,新數據分布跟先前訓練集分布有所偏差,所以先驗網路不足以完全擬合新數據時,可以凍結大部分前層網路,只對最後幾層進行訓練調參(這也稱之為fine tune)。

增加神經網路層數,可能會增加測試數據集的分類錯誤率

減少神經網路層數,總是能減小測試數據集的分類錯誤率

增加神經網路層數,總是能減小訓練數據集的分類錯誤率

A. 1

B. 1和 3

C. 1和 2

D. 2

答案：A

【解析】深度神經網路的成功,已經證明增加神經網路層數,可以增加模型範化能力,也就是，訓練數據集和測試數據集都表現得更好。但這篇文獻中（https://arxiv.org/pdf/1512.03385v1.pdf）,作者提到更多的層,也不一定能保證有更好的表現.所以不能絕對地說層數多的好壞,只能選A

A.分類過程中類別不平衡

B.實例分割過程中，相同類別圖像距離過小

C.提取語義信息時，高層語義過少的時候

D.物體定位時，目標面積過小

答案：A

【解析】Focal Loss最初是在[RetinaNet](https://arxiv.org/abs/1708.02002)論文中提出，旨在解決one-stage目標檢測中正負樣本不均衡的問題，也可擴展到樣本的類別不均衡問題上。該損失函數降低了大量簡單負樣本在訓練中所佔的權重。

參考自：https://github.com/amusi/daily-question/blob/master/README.md

❹ 自然語言處理（NLP）的基礎難點：分詞演算法

自然語言處理（NLP，Natural Language Processing）是人工智慧領域中的一個重要方向，主要研究人與計算機之間用自然語言進行有效通信的各種理論和方法。自然語言處理的底層任務由易到難大致可以分為詞法分析、句法分析和語義分析。分詞是詞法分析（還包括詞性標注和命名實體識別）中最基本的任務，也是眾多NLP演算法中必不可少的第一步，其切分准確與否往往與整體結果息息相關。

金融領域分詞的難點

分詞既簡單又復雜。簡單是因為分詞的演算法研究已經很成熟了，大部分的演算法（如HMM分詞、CRF分詞）准確率都可以達到95%以上；復雜則是因為剩下的5%很難有突破，主要可以歸結於三點：

▲粒度，即切分時的最小單位，不同應用對粒度的要求不一樣，比如「融資融券」可以是一個詞也可以是兩個詞

▲歧義，比如「恆生」一詞，既可指恆生公司，又可指恆生指數

▲未登錄詞，即未出現在演算法使用的詞典中的詞，比如不常見的專業金融術語，以及各種上市公司的名稱

在金融領域中，分詞也具有上述三個難點，並且在未登錄詞方面的難點更為突出，這是因為金融類詞彙本來就多，再加上一些專有名詞不僅有全稱還有簡稱，這就進一步增大了難度。

在實際應用中，以上難點時常會造成分詞效果欠佳，進而影響之後的任務。尤其是在一些金融業務中，有許多需要與用戶交互的場景，某些用戶會用口語化的詞彙描述業務，如果分詞錯誤會影響用戶意圖的解析，這對分詞的准確性提出了更高的要求。因此在進行NLP上層應用開發時，需要對分詞演算法有一定的了解，從而在效果優化時有能力對分詞器進行調整。接下來，我們介紹幾種常用的分詞演算法及其應用在金融中的優劣。

幾種常見的分詞演算法

分詞演算法根據其核心思想主要分為兩種：

第一種是基於字典的分詞，先把句子按照字典切分成詞，再尋找詞的最佳組合方式，包括最大匹配分詞演算法、最短路徑分詞演算法、基於N-Gram model的分詞演算法等；

第二種是基於字的分詞，即由字構詞，先把句子分成一個個字，再將字組合成詞，尋找最優的切分策略，同時也可以轉化成序列標注問題，包括生成式模型分詞演算法、判別式模型分詞演算法、神經網路分詞演算法等。

最大匹配分詞尋找最優組合的方式是將匹配到的最長片語合在一起，主要的思路是先將詞典構造成一棵Trie樹（也稱為字典樹），Trie樹由詞的公共前綴構成節點，降低了存儲空間的同時可以提升查找效率。

最大匹配分詞將句子與Trie樹進行匹配，在匹配到根結點時由下一個字重新開始進行查找。比如正向（從左至右）匹配「他說的確實在理」，得出的結果為「他／說／的確／實在／理」。如果進行反向最大匹配，則為「他／說／的／確實／在理」。

這種方式雖然可以在O(n)時間對句子進行分詞，但是只單向匹配太過絕對，尤其是金融這種詞彙較豐富的場景，會出現例如「交易費/用」、「報價單/位」等情況，所以除非某些詞的優先順序很高，否則要盡量避免使用此演算法。

最短路徑分詞演算法首先將一句話中的所有詞匹配出來，構成詞圖（有向無環圖DAG），之後尋找從起始點到終點的最短路徑作為最佳組合方式，例：

我們認為圖中每個詞的權重都是相等的，因此每條邊的權重都為1。

在求解DAG圖的最短路徑問題時，總是要利用到一種性質：即兩點之間的最短路徑也包含了路徑上其他頂點間的最短路徑。比如S->A->B->E為S到E到最短路徑，那S->A->B一定是S到B到最短路徑，否則會存在一點C使得d(S->C->B)<d(S->A->B)，那S到E的最短路徑也會變為S->C->B->E，這就與假設矛盾了。利用上述的最優子結構性質，可以利用貪心演算法或動態規劃兩種求解演算法：

（1）基於Dijkstra演算法求解最短路徑，該演算法適用於所有帶權有向圖，求解源節點到其他所有節點的最短路徑，並可以求得全局最優解；

（2）N-最短路徑分詞演算法，該方法是對Dijkstra演算法的擴展，在每一步保存最短的N條路徑，並記錄這些路徑上當前節點的前驅，在最後求得最優解時回溯得到最短路徑。這種方法的准確率優於Dijkstra演算法，但在時間和空間復雜度上都更大。

相較於最大匹配分詞演算法，最短路徑分詞演算法更加靈活，可以更好地把詞典中的片語合起來，能更好地解決有歧義的場景。比如上述「他說的確實在理」這句話，用最短路徑演算法的計算結果為「他／說／的／確實／在理」，避免了正向最大匹配的錯誤。但是對於詞典中未存在的詞基本沒有識別能力，無法解決金融領域分詞中的「未登錄詞」難點。

N-Gram（又稱N元語法模型）是基於一個假設：第n個詞出現與前n-1個詞相關，而與其他任何詞不相關。在此種假設下，可以簡化詞的條件概率，進而求解整個句子出現的概率。

現實中，常用詞的出現頻率或者概率肯定比罕見詞要大。因此，可以將求解詞圖最短路徑的問題轉化為求解最大概率路徑的問題，即分詞結果為「最有可能的詞的組合「。

計算詞出現的概率，僅有詞典是不夠的，還需要充足的語料，所以分詞任務已經從單純的「演算法」上升到了「建模」，即利用統計學方法結合大數據挖掘，對「語言」（句子出現的概率）進行建模。

我們將基於N-gram模型所統計出的概率分布應用到詞圖中，可以得到詞的概率圖。對該詞圖用最短路徑分詞演算法求解最大概率的路徑，即可得到分詞結果。

相較於前兩種分詞演算法，基於N-Gram model的分詞演算法對詞頻進行了統計建模，在切分有歧義的時候力求得到全局最優值，比如在切分方案「證券/自營/業務」和「證券/自/營業/務」中，統計出「證券/自營/業務」出現的概率更大，因此結果有更高的准確率。但也依然無法解決金融場景中未登錄詞的問題。

生成式模型主要有隱馬爾可夫模型（HMM，Hidden Markov Model）、樸素貝葉斯分類等。HMM是常用的分詞模型，基於Python的jieba分詞器和基於Java的HanLP分詞器都使用了HMM。

HMM模型認為在解決序列標注問題時存在兩種序列，一種是觀測序列，即人們顯性觀察到的句子，另一種是隱狀態序列，即觀測序列的標簽。假設觀測序列為X，隱狀態序列是Y，則因果關系為Y->X。因此要得到標注結果Y，必須對X的概率、Y的概率、P(X|Y)進行計算，即建立P(X,Y)的概率分布模型。

HMM演算法可以在一定程度上解決未登錄詞的問題，但生成式模型的准確率往往沒有接下來要談到的判別式模型高。

判別式模型主要有感知機、支持向量機（SVM，Support Vector Machine）、條件隨機場（CRF，Conditional Random Field）、最大熵模型等，其中感知機模型和CRF模型是常用的分詞模型。

（1）平均感知機分詞演算法

感知機是一種簡單的二分類線性模型，通過構造超平面，將特徵空間（輸入空間）中的樣本分為正負兩類。通過組合，感知機也可以處理多分類問題。但由於每次迭代都會更新模型的所有權重，被誤分類的樣本會造成很大影響，因此採用平均的方法，在處理完一部分樣本後對更新的權重進行平均。

（2）CRF分詞演算法

CRF可以看作一個無向圖模型，假設給定的標注序列為Y，觀測序列為X，CRF對條件概率P(Y|X)進行定義，而不是對聯合概率建模。

平均感知機演算法雖然速度快，但仍不夠准確。適合一些對速度要求高、對准確性要求相對不那麼高的場景。CRF分詞演算法可以說是目前最常用的分詞、詞性標注和實體識別演算法，它對未登陸詞也有很好的識別能力，是目前在速度、准確率以及未登錄詞識別上綜合表現最突出的演算法，也是我們目前所採用的解決方案，但速度會比感知機慢一些。

在NLP中，最常用的神經網路為循環神經網路（RNN，Recurrent Neural Network），它在處理變長輸入和序列輸入問題中有著巨大的優勢。LSTM（Long Short-Term Memory，長短期記憶網路）為RNN變種的一種，在一定程度上解決了RNN在訓練過程中梯度消失和梯度爆炸的問題。

目前對於序列標注任務，業內公認效果最好的模型是BiLSTM+CRF。相比於上述其它模型，雙向循環神經網路BiLSTM，可以更好地編碼當前字等上下文信息，並在最終增加CRF層，核心是用Viterbi演算法進行解碼，以得到全局最優解，避免B,S,E這種不可能的標記結果的出現，提高准確率。

神經網路分詞雖然能在准確率、未登錄詞識別上有更好的表現，但RNN無法並行計算，在速度上沒有優勢，所以該演算法通常在演算法研究、句子精確解析等對速度要求不高的場景下使用。

分詞作為NLP底層任務之一，既簡單又重要，很多時候上層演算法的錯誤都是由分詞結果導致的。因此，對於底層實現的演算法工程師，不僅需要深入理解分詞演算法，更需要懂得如何高效地實現和調試。

而對於上層應用的演算法工程師，在實際分詞時，需要根據業務場景有選擇地應用上述演算法，比如在搜索引擎對大規模網頁進行內容解析時，對分詞對速度要求大於精度，而在智能問答中由於句子較短，對分詞的精度要求大於速度。

❺ SVM演算法原理

一、決策面方程

以二維空間為例，二維空間中任意一條直線方程可以寫為

我們將其向量化，可以得到

設用向量w代表矩陣a1和a2，用向量x代表矩陣x1和x2，標量γ代表b，則方程可化表示為

從方程可知，一個n維空間的超平面在二維空間上的表現，可以是一條直線，或者一個曲線（二維空間中只能看到這個n維超平面穿過而無法看到其模樣）， 超平面方程即是我們的決策面方程

二、函數間隔和幾何間隔

在SVM監督學習中，我們規定標簽數據為+1和-1兩個值，這么做的目的， 可以計算出任意一個樣本點在超平面方程上的表現結果的符號，與標簽符號是否一致來判斷分類的正確性 ，為此我們可以引入函數間隔的概念

但是當我們成比例的縮放w和γ，函數間隔的值也將成比例的變化，可是超平面的位置並沒有發生任何變化，所以函數間隔並不是我們想要的分類間隔，為此，我們需要引入幾何間隔的概念

還是以二維空間出發，任意一點到直線的距離可以寫成

我們將其拓展到n維空間，直線方程即是我們的超平面方程，則n維空間中任何一點到超平面的距離可以寫成

為此，我們引入幾何間隔概念，其中||w||表示向量w的二范數

從幾何間隔可以看出，就算等比例縮放w和γ，由於除上了||w||使得幾何間隔的值不會改變，它只隨著超平面位置的變化而變化，因此， 我們要尋找的分類間隔是幾何間隔

三、不等式約束條件

SVM演算法的目的是找到一個將分類效果達到最合理化的超平面，這個超平面即是分類器 。而評估分類器的好壞的標准就是分類間隔的大小

我們定義分類間隔的距離為d，好的分類器應該讓所有樣本點到決策面的幾何間隔都大於等於d

化簡上式，不等式兩邊同時除以d可得

由於||w||和d都是標量，可定義

則上式可化簡為

在不等式兩邊同時乘以yi，即將兩個式子化簡為一個式子（這里體現了正是因為標簽數據為+1和-1，才方便將約束條件變成一個約束方程）

這個約束方程的意義 即是任何樣本點到超平面（分類器）的幾何間隔都大於等於分類間隔

四、SVM最優化模型的數學描述

評估分類器的優劣是分類間隔的大小，且對於任意樣本點都滿足約束方程

由約束方程可知，當樣本點落在支持向量邊界上有如下關系

則分類間隔d可以表示為支持向量點到超平面的幾何間隔

要讓任何樣本點都在d之外，即求分類間隔d的最大值，則目標函數可以寫成

為了方便在後續最優化處理中對目標函數的求導，我們將目標函數做等效變化

由目標函數是二次的，而約束條件是線性的，則 SVM的數學模型即是：不等式約束條件下的二次型函數優化 ，而求解這一類優化問題，接下來我們需要構造 拉格朗乘子函數

五、引入拉格朗函數

目標函數是求解在約束條件g(x)下的二次型函數f(x)的最小值，直觀上我們希望構造一個函數L(x)，使得L(x)在f(x)的可行解區域內的求出的值和f(x)求出的值完全一樣，而在f(x)的可行解區域外，L(x)的值又接近無窮大，這么做的目的，使得我們可以用一個函數L(x)來等效表示原問題的g(x)和f(x)

拉格朗函數的目的，就是將約束條件融合到目標函數中，構造一個新函數來表示目標函數，將有約束的優化問題轉化為無約束的優化問題

下面，我們構造拉格朗函數來表示目標函數

其中αi是拉格朗日乘子，每一個約束條件對應一個拉格朗日乘子，其中αi大於等於0

則原優化問題可以轉化為

討論如下條件(1)(2)：

(1) 當樣本點不滿足約束條件時，即說明在 可行解區域外

此時將αi置為正無窮大，那麼θ(w)顯然也是正無窮大

(2) 當樣本點滿足約束條件時，即說明在 可行解區域內

此時θ(w)的最小值就是原目標函數，於是綜上所述，引入拉格朗乘子函數後，可以得到新的目標函數

我們用p*表示優化目標函數後的最優解，且與最初的目標函數等價

觀察新的目標函數，如果直接求偏導數求解，那麼一上來將面對w和b兩個未知參數，而αi又是不等式約束，求解過程將非常復雜。換一個角度思考，如果將max和min的位置對調，變成如下新的目標函數

上式變化使用了 拉格朗日函數的對偶性，交換後的新問題即是原目標函數的對偶問題 ，我們用d*來表示對偶目標函數的最優解，可見d*的求導過程比p*相對容易，且d*<=p*，而當滿足下列條件時，d*= p*

因為目標函數本身已經是一個凸函數，而優化問題又是求解最小值，所以目標函數的最優化問題就是凸優化問題，則接下來就要重點討論KKT條件

六、KKT條件的描述

一個最優化模型能夠表示成下列標准形式

其中f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，m和n分別是等式約束和不等式約束的數量

KKT條件即是規定f(x)的 最優值 必須滿足以下(1)(2)(3)條件， 只有滿足KKT條件，目標函數的最優化問題依然可以用拉格朗日乘子法解決

很明顯，我們需要優化的目標函數屬於帶有不等式約束函數g(x)，所以條件二顯然滿足，下面我們來分析條件一和條件三的理論

七、目標函數的等高線與約束條件的最優值分析（條件一）

對於KKT條件一的分析，我們假設目標函數是f(x1,x2)的二元函數，它的圖像在三維空間里是一個曲面，准確的來說是一個凸曲面

其中g(x1,x2)是約束方程，要求目標函數f(x1,x2)的最小值，即轉化為 求g(x1,x2)=c這條曲線上的一點，使得f(x1,x2)取得最小值，換個比喻，就是在山上（目標函數曲面）尋找一條山路（約束條件曲線）的最低點

我們畫出目標函數的等高線，來分析目標函數最優值和約束條件的關系

對於研究目標函數z=f(x1,x2)，當z取不同的值，即將曲線z投影在(x1,x2)組成的空間中（這里指的是二維空間），也就是曲面的等高線，上圖中d1和d2即是兩條目標函數的等高線，可以看出，當約束函數g(x1,x2)與目標函數的等高線有共同的交點， 即證明這組值同時滿足在目標函數的可行域中，也符合約束條件的約束關系

如果等高線與g(x1,x2) 相交 ，則是一組目標函數的解，但是這個解一定不是最優解， 因為相交意味著肯定存在其它等高線在該條等高線的內部或者外部 ，可能會使得新的等高線與g(x1,x2)的交點更大或者更小，這就意味著只有當等高線與g(x1,x2) 相切 ，才可能得到最優解（切線可能多條）

所以最優解必須滿足： 目標函數的負梯度方向與約束函數的梯度方向一致

而上式恆成立的條件就是： 拉格朗日乘子α >= 0 ，且這個式子就是目標函數對各個參數求偏導數的結果，即KKT的第一個條件：目標函數對各個參數的導數為0

八、分類討論約束條件和拉格朗日乘子的組合（條件三）

對於KKT條件三，可以看出，因為所有的約束函數gi(x)<=0，所有的拉格朗日乘子αi>=0，要使得求和後結果為0，要麼某個約束函數gi(x)=0，要麼其對應的αi=0

從一個案例出發來分析KKT條件三的邏輯，假設目標函數和約束函數是

將不等式約束構造出拉格朗日函數，並分別對x1和x2求偏導數

而KKT的條件三要求最優解滿足 ∑α*g(x) = 0，在這個案例里α和g(x)只有一個，結合條件一，可以得到

根據之前的分析，最優值滿足條件三的話，要麼α=0，要麼g(x)=0

（i）：如果α=0，則x1=1，x2=-2，代入g(x1,x2) =10-1-10*(-2)=29>0，發現這組解違背了約束函數g(x)<0，則舍棄這組解

（ii）: 如果g(x1,x2)=0，則代入x1和x2的表達式到g(x)中，解出α=58/101>0，發現這組解不違背約束函數，則代入α解出x1=130/101，x2=88/101，則這組解有可能是最優解

綜上(i)(ii)討論，目標函數的最優值符合KKT條件三，也說明了 滿足強對偶條件的優化問題的最優值必須滿足KKT條件

九、求解對偶問題

上面分析了目標函數滿足凸優化和KKT條件，則問題轉化為求解原問題的對偶問題（即p*=d*）

根據對偶問題描述，先要求內側w和b關於L(w,b,α)的最小化值，即求L對w和b的偏導數

將w和b的偏導數帶入拉格朗函數化簡得

整理一下最終化簡結果為

從上述結果可以看出，樣本的x和y是已知的，此時的 L(w,b,α)函數只有一個變數，即αi

我們歸納一下現在的目標函數為

現在目標函數變成了如上形式，其中αi>=0，這里隱含著一個假設，即數據100%線性可分，但是現實生活中，數據往往是不會那麼規則的線性化，為此我們需要引入鬆弛變數

十、引入鬆弛變數

由於現實世界中的數據都是帶有噪音的，也就是數據可能出偏離其正常的位置很遠，而出現這種極端現象後往往會影響超平面的選擇，也許將無法構造出將數據徹底分開的超平面出來

所以對於處理這種情況， SVM需要允許（妥協）出某些噪音很大的數據點能夠偏離超平面，即允許其出現在超平面的錯誤的一側 ，為此我們引入鬆弛變數C，這樣我們的目標函數又變為

接下來為了研究討論αi的取值范圍，我們加上一個負號將目標函數等價轉化為

十一、討論拉格朗乘子的取值意義和其值域

回顧一下最初的約束條件為

設ui為該約束條件，可以歸納出αi關於約束函數的取值意義

αi只有滿足上述3種情況，才能求出最優解，所以 當αi與約束條件ui沖突的時候，需要更新這些αi ，這也就是滿足目標函數的第一個約束限制，即0<=αi<=C

而同時目標函數還受到第二個約束條件的限制，即

所以不能只更新一個αi因子，需要同時再次更新第二個αj因子，也就是 α因子總是成對的更新（αi對總是和αj配對），一增一減，此消彼長，才能保證加權和為0的約束 ，同時這也就是下面提及SMO演算法的思想和多元函數化簡為二元函數，在從二元函數化簡為一元函數的難點

根據這個約束和α因子需要成對更新，假設我們選取的兩個拉格朗乘子為α1和α2，則更新之前是old，更新之後是new，且更新前後需要滿足和為0的約束

兩個因子同時更新顯然非常困難，所以需要先求出第一個αj的解，再用αj的解去表示更新第二個αi的解 ，後文的SMO演算法會闡述這一點。因此需要先確定αj的取值范圍，假設L和H分別為它的下界和上界，結合目標函數的約束限制來綜合討論L和H的取值關系

（i）：當y1和y2異號時，可以得到

移項可得a2 = a1 - A，此時α的取值范圍如下圖所示

所以此時α的上下界H和L為

（ii）：當y1和y2同號時，可以得到

移項可得a2 = -a1 + A，此時α的取值范圍如下圖所示

所以此時α的上下界H和L為

綜上(i)(ii)的討論，通過y1和y2的異號或者同號，可以推導出α更新後的上下界分別為

這個公式顯得非常的重要，它將α因子限制在有效的矩形范圍內，在SMO演算法中，當我們更新完α後，由於α可能會被更新得很大或很小，因此需要經過裁剪來保證α的在約束條件內

12、SMO演算法的思想

回顧之前第九，第十，第十一步的分析，目標函數為

目標函數只包含n個變數α的 多元函數 ，且帶有兩個約束條件，我們的 目的是求出目標函數的最小值，即找到一組α的組合，使得目標函數取得最小值

由第十一步的分析，我們需要不斷更新這n個α因子，通過迭代來逼近函數達到最小值，但是如果一次性更新n個參數，將會有n!種組合，那麼時間復雜度將會非常高，為此我們首先想到 坐標上升（下降）法

來通過一個例子來說明坐標上升法的思路

可知案例中要求一個三元函數的最大值， 演算法的思想是每次迭代時只更新一個維度，通過多次迭代直到收斂來優化函數的最值 ，求出三個變數的偏導數推出其關系

通過迭代即就可以求出其最值

SMO演算法借鑒了坐標上升（下降）法的思想來優化α因子組合，但是由於目標函數的第二個約束條件有加權和為0的限制，導致每次迭代時候不能只更新一個因子αi，必須同時更新與之配對的另一個因子αj，此消彼長才能保證加權和為0（第十一步中已提及）

所以SMO演算法思想是將原始問題中，求解n個參數的二次規劃問題，分解成了多個子二次規劃問題來分別求解，每一個子問題只需要求解2個參數，即將多元函數推導為二元函數，再將二元函數推導為一元函數

13、多元函數推導為二元函數

目標函數是關於α的N元函數，通過SMO的演算法思想，假設每次迭代更新，選取一對α1和α2的組合，其餘的乘子不變， 首先需要將α1和α2從目標函數中分離出來 ，也就是將多元函數推導為二元函數

從N元函數中分離出α1和α2因子

由於上式推導結果過於復雜，我們定義2個表達式來表示上式常量部分，用來簡化上式

又由於單獨存下的常數項對以後的求導沒有貢獻，所以我們提出單獨的常數項定義為Constant

帶入vi和Constant表達式，則結果化簡為

至此，我們將 多元函數推導為含有α1和α2變數的二元函數 ，接下來將這個二元函數推導為一元函數

14、二元函數推導為一元函數

我們需要推導出α1和α2的關系，然後用α2來表示α1帶入二元函數，就可以推導出關於α2的一元函數了

由目標函數的第二個約束條件

同理根據SMO演算法思想，從約束條件中分離出α1和α2

將等式兩邊同時乘以y1，可推導出α1和α2的關系

同理，我們定義兩個表達式r和s來表示上式的常量部分，用來簡化上式關系

帶入r和s後，α1和α2的關系推導為

下面將α1帶入我們的二元函數中，可得

至此， 我們將二元函數推導為只含有一個變數α2的一元函數 ，接下來終於可以對目標函數求導了

15、求解一元函數的偏導數，推導出第一個拉格朗乘子的遞推關系

我們對一元函數求α2的偏導數為0

帶入s=y1*y2和y2*y2=1，整理上式可求出α2

❻ 你知道支持向量機（SVM）是什麼意思嗎

超級通俗的解釋：支持向量機是用來解決分類問題的。先考慮最簡單的情況，豌豆和米粒，用曬子很快可以分開，小顆粒漏下去，大顆粒保留。用一個函數來表示就是當直徑d大於某個值D，就判定為豌豆，小於某個值就是米粒。d>D, 豌豆d<D,米粒在數軸上就是在d左前銷邊就是米粒，右邊就是慧宴遊綠豆，這是一維的情況。但是實際問題沒這么簡單，祥鏈考慮的問題不單單是尺寸，一個花的兩個品種，怎麼分類，假設決定他們分類的有兩個屬性，花瓣尺寸和顏色。單獨用一個屬性來分類，像剛才分米粒那樣，就不行了。這個時候我們設置兩個值尺寸x和顏色y.我們把所有的數據都丟到x-y平面上作為點，按道理如果只有這兩個屬性決定了兩個品種，數據肯定會按兩類聚集在這個二維平面上。

❼ 數據挖掘十大演算法-

整理里一晚上的數據挖掘演算法，其中主要引自wiki和一些論壇。發布到上作為知識共享，但是發現Latex的公式轉碼到網頁的時候出現了丟失，暫時沒找到解決方法，有空再回來填坑了。

——編者按

一、 C4.5

C4.5演算法是由Ross Quinlan開發的用於產生決策樹的演算法[1]，該演算法是對Ross Quinlan之前開發的ID3演算法的一個擴展。C4.5演算法主要應用於統計分類中，主要是通過分析數據的信息熵建立和修剪決策樹。

1.1 決策樹的建立規則

在樹的每個節點處，C4.5選擇最有效地方式對樣本集進行分裂，分裂規則是分析所有屬性的歸一化的信息增益率，選擇其中增益率最高的屬性作為分裂依據，然後在各個分裂出的子集上進行遞歸操作。

依據屬性A對數據集D進行分類的信息熵可以定義如下：

劃分前後的信息增益可以表示為：

那麼，歸一化的信息增益率可以表示為：

1.2 決策樹的修剪方法

C4.5採用的剪枝方法是悲觀剪枝法(Pessimistic Error Pruning，PEP)，根據樣本集計運算元樹與葉子的經驗錯誤率，在滿足替換標准時，使用葉子節點替換子樹。

不妨用K表示訓練數據集D中分類到某一個葉子節點的樣本數，其中其中錯誤分類的個數為J，由於用估計該節點的樣本錯誤率存在一定的樣本誤差，因此用表示修正後的樣本錯誤率。那麼，對於決策樹的一個子樹S而言，設其葉子數目為L(S)，則子樹S的錯誤分類數為：

設數據集的樣本總數為Num，則標准錯誤可以表示為：

那麼，用表示新葉子的錯誤分類數，則選擇使用新葉子節點替換子樹S的判據可以表示為：

二、KNN

最近鄰域演算法(k-nearest neighbor classification, KNN)[2]是一種用於分類和回歸的非參數統計方法。KNN演算法採用向量空間模型來分類，主要思路是相同類別的案例彼此之間的相似度高，從而可以藉由計算未知樣本與已知類別案例之間的相似度，來實現分類目標。KNN是一種基於局部近似和的實例的學習方法，是目前最簡單的機器學習演算法之一。

在分類問題中，KNN的輸出是一個分類族群，它的對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k = 1，則該對象的類別直接由最近的一個節點賦予。在回歸問題中，KNN的輸出是其周圍k個鄰居的平均值。無論是分類還是回歸，衡量鄰居的權重都非常重要，目標是要使較近鄰居的權重比較遠鄰居的權重大，例如，一種常見的加權方案是給每個鄰居權重賦值為1/d，其中d是到鄰居的距離。這也就自然地導致了KNN演算法對於數據的局部結構過於敏感。

三、Naive Bayes

在機器學習的眾多分類模型中，應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型(Naive Bayesian Model，NBC)[3]。樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎，以及穩定的分類效率。同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。

在假設各個屬性相互獨立的條件下，NBC模型的分類公式可以簡單地表示為：

但是實際上問題模型的屬性之間往往是非獨立的，這給NBC模型的分類准確度帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型；而在屬性相關性較小時，NBC模型的性能最為良好。

四、CART

CART演算法(Classification And Regression Tree)[4]是一種二分遞歸的決策樹，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子結點都有兩個分支，因此CART演算法生成的決策樹是結構簡潔的二叉樹。由於CART演算法構成的是一個二叉樹，它在每一步的決策時只能是「是」或者「否」，即使一個feature有多個取值，也是把數據分為兩部分。在CART演算法中主要分為兩個步驟：將樣本遞歸劃分進行建樹過程；用驗證數據進行剪枝。

五、K-means

k-平均演算法(k-means clustering)[5]是源於信號處理中的一種向量量化方法，現在則更多地作為一種聚類分析方法流行於數據挖掘領域。k-means的聚類目標是：把n個點（可以是樣本的一次觀察或一個實例）劃分到k個聚類中，使得每個點都屬於離他最近的均值（此即聚類中心）對應的聚類。

5.1 k-means的初始化方法

通常使用的初始化方法有Forgy和隨機劃分(Random Partition)方法。Forgy方法隨機地從數據集中選擇k個觀測作為初始的均值點；而隨機劃分方法則隨機地為每一觀測指定聚類，然後執行「更新」步驟,即計算隨機分配的各聚類的圖心，作為初始的均值點。Forgy方法易於使得初始均值點散開，隨機劃分方法則把均值點都放到靠近數據集中心的地方；隨機劃分方法一般更適用於k-調和均值和模糊k-均值演算法。對於期望-最大化(EM)演算法和標准k-means演算法，Forgy方法作為初始化方法的表現會更好一些。

5.2 k-means的標准演算法

k-means的標准演算法主要包括分配(Assignment)和更新(Update)，在初始化得出k個均值點後，演算法將會在這兩個步驟中交替執行。

分配(Assignment)：將每個觀測分配到聚類中，使得組內平方和達到最小。

更新(Update)：對於上一步得到的每一個聚類，以聚類中觀測值的圖心，作為新的均值點。

六、Apriori

Apriori演算法[6]是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法，其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。Apriori採用自底向上的處理方法，每次只擴展一個對象加入候選集，並且使用數據集對候選集進行檢驗，當不再產生匹配條件的擴展對象時，演算法終止。

Apriori的缺點在於生成候選集的過程中，演算法總是嘗試掃描整個數據集並盡可能多地添加擴展對象，導致計算效率較低；其本質上採用的是寬度優先的遍歷方式，理論上需要遍歷次才可以確定任意的最大子集S。

七、SVM

支持向量機(Support Vector Machine, SVM)[7]是在分類與回歸分析中分析數據的監督式學習模型與相關的學習演算法。給定一組訓練實例，每個訓練實例被標記為屬於兩個類別中的一個或另一個，SVM訓練演算法創建一個將新的實例分配給兩個類別之一的模型，使其成為非概率二元線性分類器。SVM模型是將實例表示為空間中的點，這樣映射就使得單獨類別的實例被盡可能寬的明顯的間隔分開。然後，將新的實例映射到同一空間，並基於它們落在間隔的哪一側來預測所屬類別。

除了進行線性分類之外，SVM還可以使用所謂的核技巧有效地進行非線性分類，將其輸入隱式映射到高維特徵空間中，即支持向量機在高維或無限維空間中構造超平面或超平面集合，用於分類、回歸或其他任務。直觀來說，分類邊界距離最近的訓練數據點越遠越好，因為這樣可以縮小分類器的泛化誤差。

八、EM

最大期望演算法(Expectation–Maximization Algorithm, EM)[7]是從概率模型中尋找參數最大似然估計的一種演算法。其中概率模型依賴於無法觀測的隱性變數。最大期望演算法經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望(E)，利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化(M)，最大化在E步上求得的最大似然值來計算參數的值。M步上找到的參數估計值被用於下一個E步計算中，這個過程不斷交替進行。

九、PageRank

PageRank演算法設計初衷是根據網站的外部鏈接和內部鏈接的數量和質量對網站的價值進行衡量。PageRank將每個到網頁的鏈接作為對該頁面的一次投票，被鏈接的越多，就意味著被其他網站投票越多。

演算法假設上網者將會不斷點網頁上的鏈接，當遇到了一個沒有任何鏈接出頁面的網頁，這時候上網者會隨機轉到另外的網頁開始瀏覽。設置在任意時刻，用戶到達某頁面後並繼續向後瀏覽的概率，該數值是根據上網者使用瀏覽器書簽的平均頻率估算而得。PageRank值可以表示為：

其中，是被研究的頁面集合，N表示頁面總數，是鏈接入頁面的集合，是從頁面鏈接處的集合。

PageRank演算法的主要缺點是的主要缺點是舊的頁面等級會比新頁面高。因為即使是非常好的新頁面也不會有很多外鏈，除非它是某個站點的子站點。

十、AdaBoost

AdaBoost方法[10]是一種迭代演算法，在每一輪中加入一個新的弱分類器，直到達到某個預定的足夠小的錯誤率。每一個訓練樣本都被賦予一個權重，表明它被某個分類器選入訓練集的概率。如果某個樣本點已經被准確地分類，那麼在構造下一個訓練集中，它被選中的概率就被降低；相反，如果某個樣本點沒有被准確地分類，那麼它的權重就得到提高。通過這樣的方式，AdaBoost方法能「聚焦於」那些較難分的樣本上。在具體實現上，最初令每個樣本的權重都相等，對於第k次迭代操作，我們就根據這些權重來選取樣本點，進而訓練分類器Ck。然後就根據這個分類器，來提高被它分錯的的樣本的權重，並降低被正確分類的樣本權重。然後，權重更新過的樣本集被用於訓練下一個分類器Ck[，並且如此迭代地進行下去。

AdaBoost方法的自適應在於：前一個分類器分錯的樣本會被用來訓練下一個分類器。AdaBoost方法對於雜訊數據和異常數據很敏感。但在一些問題中，AdaBoost方法相對於大多數其它學習演算法而言，不會很容易出現過擬合現象。AdaBoost方法中使用的分類器可能很弱（比如出現很大錯誤率），但只要它的分類效果比隨機好一點（比如兩類問題分類錯誤率略小於0.5），就能夠改善最終得到的模型。而錯誤率高於隨機分類器的弱分類器也是有用的，因為在最終得到的多個分類器的線性組合中，可以給它們賦予負系數，同樣也能提升分類效果。

引用

[1] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.

[2] Altman, N. S. An introction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879

[3] Webb, G. I.; Boughton, J.; Wang, Z. Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning (Springer). 2005, 58 (1): 5–24. doi:10.1007/s10994-005-4258-6

[4] decisiontrees.net Interactive Tutorial

[5] Hamerly, G. and Elkan, C. Alternatives to the k-means algorithm that find better clusterings (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 2002

[6] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.

[7] Cortes, C.; Vapnik, V. Support-vector networks. Machine Learning. 1995, 20 (3): 273–297. doi:10.1007/BF00994018

[8] Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39 (1):1–38, 1977

[9] Susan Moskwa. PageRank Distribution Removed From WMT. [October 16, 2009]

[10] Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855