支持向量機(jī)涉及到數(shù)學(xué)公式和定力非常多，只有掌握了這些數(shù)學(xué)公式才能更好地理解支持向量機(jī)算法庵芭。

最優(yōu)化問(wèn)題

最優(yōu)化問(wèn)題一般是指對(duì)于某一個(gè)函數(shù)而言,求解在其指定作用域上的全局最小值問(wèn)題,一般分為以下三種情況(備注:以下幾種方式求出來(lái)的解都有可能是局部極小值,只有當(dāng)函數(shù)是凸函數(shù)的時(shí)候,才可以得到全局最小值)

（1）無(wú)約束問(wèn)題:求解方式一般求解方式梯度下降法、牛頓法狂男、坐標(biāo)軸下降法等;其中梯度下降法是用遞歸來(lái)逼近最小偏差的模型溉旋。我們?cè)谇懊娼榻B過(guò)俩由；

（2）等式約束條件:求解方式一般為拉格朗日乘子法

（3）不等式約束條件:求解方式一般為KKT條件

拉格朗日乘子式

有拉格朗日乘子法的地方财异，必然是一個(gè)組合優(yōu)化問(wèn)題倘零。參數(shù)α被稱(chēng)為拉格朗日乘子，且α不等于零戳寸。

假設(shè)有一個(gè)二維的優(yōu)化問(wèn)題呈驶，如下：

對(duì)于上述優(yōu)化問(wèn)題可以轉(zhuǎn)化為求下列函數(shù)的最值：

拉格朗日乘數(shù)法（Lagrange multiplier）有很直觀的幾何意義。

我們可以畫(huà)出f的等高線圖疫鹊，如下圖袖瞻。此時(shí)，約束g=c由于只有一個(gè)自由度拆吆，因此也是圖中的一條曲線（紅色曲線所示）聋迎。顯然地，當(dāng)約束曲線g=c與某一條等高線f=d1相切時(shí)枣耀，函數(shù)f取得極值霉晕。

兩曲線相切等價(jià)于兩曲線在切點(diǎn)處擁有共線的法向量。因此可得函數(shù)f(x,y)與g(x,y)在切點(diǎn)處的梯度（gradient）成正比捞奕。 于是我們便可以列出方程組求解切點(diǎn)的坐標(biāo)(x,y)牺堰，進(jìn)而得到函數(shù)f的極值。

在梯度為零的情況下取得最小值颅围，既滿(mǎn)足兩個(gè)函數(shù)的導(dǎo)數(shù)相加等于零伟葫；滿(mǎn)足的梯度公式如下：

用圖表現(xiàn)出來(lái)則如上圖所示。

用偏導(dǎo)數(shù)方法列出方程：

求出x,y,λ的值院促，代入即可得到目標(biāo)函數(shù)的極值

例子：求函數(shù)：

在約束條件：

下的最小值筏养。

代碼如下：

import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
import math
from mpl_toolkits.mplot3d import Axes3D
# 解決中文顯示問(wèn)題
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
# 拉格朗日乘子法理解
def f(x, y):
    return x**2 / 2.0 + y**2 / 3.0 - 1

# 構(gòu)建數(shù)據(jù)
X1 = np.arange(-8, 8, 0.2)
X2 = np.arange(-8, 8, 0.2)
X1, X2 = np.meshgrid(X1, X2)
Y = np.array(list(map(lambda t: f(t[0], t[1]), zip(X1.flatten(), X2.flatten()))))
Y.shape = X1.shape

# 限制條件
X3 = np.arange(-4, 4, 0.2)
X3.shape = 1,-1
X4 = np.array(list(map(lambda t: t ** 2+1, X3)))

# 畫(huà)圖
fig = plt.figure(facecolor='w')
ax = Axes3D(fig)
ax.plot_surface(X1, X2, Y, rstride=1, cstride=1, cmap=plt.cm.jet)
ax.plot(X3, X4 , 'ro--', linewidth=2)


ax.set_title(u'拉格朗日乘子的理解')
ax.set_xlabel('x')
ax.set_zlabel('z')
ax.set_ylabel('y')
plt.show()

輸出的結(jié)果如圖所示：

理解好拉格朗日乘子有助于理解后面的KKT條件。

KKT條件

繼續(xù)討論關(guān)于帶等式以及不等式的約束條件的凸函數(shù)優(yōu)化常拓。任何原始問(wèn)題約束條件無(wú)非最多3種渐溶，等式約束，大于號(hào)約束墩邀，小于號(hào)約束掌猛，而這三種最終通過(guò)將約束方程化簡(jiǎn)化為兩類(lèi)：約束方程等于0和約束方程小于0盏浙。

上述的二維優(yōu)化問(wèn)題眉睹，則多了一個(gè)不等式：

對(duì)于上述優(yōu)化問(wèn)題可以轉(zhuǎn)化為求下列函數(shù)的最值：

可以轉(zhuǎn)化為一下兩種情況：

（1）當(dāng)可行解在約束內(nèi)部區(qū)域的時(shí)候,令β=0即可消去約束。

（2）對(duì)于參數(shù)β的取值而言,在等值約束中,約束函數(shù)和目標(biāo)函數(shù)的梯度只要滿(mǎn)足平

行即可,而在不等式約束中,若β≠0,則說(shuō)明可行解在約束區(qū)域的邊界上,這個(gè)時(shí)候可行解應(yīng)該盡可能的靠近無(wú)約束情況下的解,所以在約束邊界上,目標(biāo)函數(shù)的負(fù)梯度方向應(yīng)該遠(yuǎn)離約束區(qū)域朝無(wú)約束區(qū)域時(shí)的解,此時(shí)約束函數(shù)的梯度方向與目標(biāo)函數(shù)的負(fù)梯度方向應(yīng)相同;從而可以得出β>0废膘。

此時(shí)約束條件可以寫(xiě)作：

在圖上表示如圖：

由于：

可以轉(zhuǎn)化為：

這是一個(gè)對(duì)偶問(wèn)題竹海，下面簡(jiǎn)單介紹一下對(duì)偶問(wèn)題的求解方法：

在優(yōu)化問(wèn)題中,目標(biāo)函數(shù)f(X)存在多種形式,如果目標(biāo)函數(shù)和約束條件都為變量的線性函數(shù),則稱(chēng)問(wèn)題為線性規(guī)劃;如果目標(biāo)函數(shù)為二次函數(shù),則稱(chēng)最優(yōu)化問(wèn)題為二次規(guī)劃;如果目標(biāo)函數(shù)或者約束條件為非線性函數(shù),則稱(chēng)最優(yōu)化問(wèn)題為非線性?xún)?yōu)化。每個(gè)線性規(guī)劃問(wèn)題都有一個(gè)對(duì)應(yīng)的對(duì)偶問(wèn)題丐黄。對(duì)偶問(wèn)題具有以下幾個(gè)特性

（1）.對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題;

（2）.無(wú)論原始問(wèn)題是否是凸的,對(duì)偶問(wèn)題都是凸優(yōu)化問(wèn)題

（3）對(duì)偶問(wèn)題可以給出原始問(wèn)題的-—個(gè)下界

（4）.當(dāng)滿(mǎn)足一定條件的時(shí)候,原始問(wèn)題和對(duì)偶問(wèn)題的解是完美等價(jià)的.

以上問(wèn)題可以轉(zhuǎn)化為：

這為后面要用到的SVM求解斋配，提供和很大的方便。

參考： 如果公式推導(dǎo)還是不懂，也可以參考《統(tǒng)計(jì)學(xué)習(xí)方法》李航-P103<學(xué)習(xí)的對(duì)偶算法>

點(diǎn)到超平面距離公式：

加入為二維空間可以轉(zhuǎn)化為點(diǎn)到直線的距離艰争，用以前學(xué)過(guò)的點(diǎn)到直線距離可以表示如下面所示：

假如是多維空間的超平面坏瞄，則點(diǎn)到平面的距離可以表示為：

超平面公式：

距離公式：

感知器模型

感知器算法是最古老的分類(lèi)算法之一,原理比較簡(jiǎn)單,不過(guò)模型的分類(lèi)泛化能力比較弱,不過(guò)感知器模型是SⅥM、神經(jīng)網(wǎng)絡(luò)甩卓、深度學(xué)習(xí)等算法的基礎(chǔ)鸠匀。它的目的就是找到一條直線或者超平面把不同的樣本進(jìn)行分類(lèi)。

感知器的思想很簡(jiǎn)單:比如你們班上的很多學(xué)生逾柿，可以分為男生和女生缀棍。,感知器模型就是試圖找到一條直線,能夠把所有的男同學(xué)和女同學(xué)分隔開(kāi),如果是高維空間中,感知器模型尋找的就是一個(gè)超平面,能夠把所有的二元類(lèi)別分割開(kāi)。感知器模型的前提是:數(shù)據(jù)是線性可分的机错。如下圖所示：

對(duì)于m個(gè)樣本爬范，每個(gè)樣本n維特征，且屬于二元類(lèi)別輸出弱匪，如下所示：

我們的目的是找到一個(gè)超平面：

使得一個(gè)類(lèi)別樣本滿(mǎn)足：

另外一些樣本滿(mǎn)足：

則感知器模型最終可以寫(xiě)作：

假如分類(lèi)正確：

相反分類(lèi)錯(cuò)的的話(huà)：

可以寫(xiě)出損失函數(shù)：所以我們可以定義我們的損害函數(shù)為期望使分類(lèi)錯(cuò)誤的所有樣本(m條樣本)到超平面的距離之和最小青瀑。損失函數(shù)為：

因?yàn)榇藭r(shí)分子和分母中都包含了θ值,當(dāng)分子擴(kuò)大N倍的時(shí)候,分母也會(huì)隨之?dāng)U大,也就是說(shuō)分子和分母之間存在倍數(shù)關(guān)系,所以可以固定分子或者分母為1然后求另一個(gè)即分子或者分母的倒數(shù)的最小化作為損失函數(shù),簡(jiǎn)化后的損失函數(shù)為(分母為1):

直接使用梯度下降法就可以對(duì)損失函數(shù)求解,不過(guò)由于這里的m是分類(lèi)錯(cuò)誤的樣本點(diǎn)集合,不是固定的,所以我們不能使用批量梯度下降法(BGD)求解,只能使用隨機(jī)梯度下降(SGD)或者小批量梯度下降(MBGD);一般在感知器模型中使用SGD來(lái)求解。