模式分類的途徑主要分為以下三種：

  1. 估計類條件概率密度 p(x|w_i) ：通過p(w_i)和p(x|w_i) ，利用貝葉斯規則計算後驗概率 ，然後通過最大後驗概率做出決策。可以採用兩種方法對概率密度進行估計。

1a：概率密度參數估計：基於對p(x|w_i)的含參數的描述，主要有最大似然估計和貝葉斯估計。

1b：概率密度非參數估計：基於對p(x|w_i)的非參數的描述，主要有Parzen窗方法。

2. 直接估計後驗概率 p(x|w_i) ，不需要先估計 p(x|w_i) 的。主要有K近鄰方法等。

3. 直接計算判別函數，不需要估計 p(x|w_i) 或者 p(w_i|x) 。常見的方法有感知器等。

關於判別函數得概念在貝葉斯估計一文中已經有所涉及。這裡依舊列出判別函數的判別規則：

如果g_j(x)geq g_i(x), forall i e j,則為模式w_j。

假設每一類別的判別函數形式已知，那麼可以利用訓練樣本集可估計判別函數中的參數。

線性判別函數中，每個判別函數是特徵向量x的分量的線性組合，即 g(x)=w^tx+w_0=w_1x_1+w_2x_2+...+w_dx_d+w_0

對於c類問題，每個類i對應一個線性判別函數。

g_i(x)=w_i^tx+w_0=w_{i1}x_1+w_{i2}x_2+...+w_{id}x_d+w_{i0}

二元分類問題中，可用一個判別函數實現：

g(x)=g_1(x)-g_2(x)=(w_{11}-w_{21})x_1+(w_{12}-w_{22})x_1+...+(w_{10}-w_{20})

=w_1x_1+w_2x_2+...+w_dx_d+w_0

判決規則為：

推廣到多類情況，由c個線性判別函數構成的c類分類器稱為線性機器（線性機）。?

線性機器的決策規則為：如果g_j(x)geq g_i(x), forall i e j,則為模式w_j。

設 Re_i 和 Re_j 是兩個相鄰的判決域，則它們之間的邊界為超平面 H_{ij} 的一部分， H_{ij}由Re_i 和 Re_j分別對應的判別函數決定：

g_i(x)=g_j(x) 或者 (w_i-w_j)x+(w_{i0}-w_{j0})=0

H_{ij}的方向由 w_i-w_j 決定。

將線性判別函數推廣到廣義判別函數：

首先是二次判別函數：

g(x)=w_0+sum_{i=1}^dw_ix_i+sum_{i=1}^dsum_{j=1}^dw_{ij}x_ix_j

接著是多項式判別函數：

g(x)=w_0+sum_{i=1}^dw_ix_i+sum_{i=1}^dsum_{j=1}^dw_{ij}x_ix_j+sum_{i=1}^dsum_{j=1}^dsum_{k=1}^dw_{ijk}x_ix_jx_k

最後，

g(x)=sum_{i=1}^{d}a_iy_i(x)=a^ty

這裡，a是d維的權向量，分量函數 y_i(x) 可以是x的任意函數，可視為特徵提取子系統的結果.雖然 g(x) 不是x的線性函數，但卻是y的線性函數，稱為廣義線性判別函數。

假設二次型函數為 g(x)=a_1+a_2x+a_3x^2 ,且 y=[1 x x^2]^T ，則

g(x)=a_1y_1+a_2y_2+a_3y_3=a^ty

引入增廣的概念，對於函數 g(x)=w_0+sum_{i=1}^dw_ix_i=sum_{i=0}^dw_ix_i

增廣特徵向量 y=[1 x ... x^d]^T=[1 x]

增廣權向量 a=[w_0,w_1,...,w_d]=[w_0, w]

假設有一個包含n個樣本的集合 {y_1,y_2,...y_n} ，用這些樣本來確定判別函數 g(x)=a^ty 中的權向量a。如果存在一個權向量（即y空間中存在一個超平面），能將所有這些樣本正確分類，則這些樣本稱為「線性可分」（linear separable）。

兩類問題的規範化：

對於樣本 y_i ，如果 a^ty_i>0 ，則標記為 w_1 ，如果 a^ty_i<0 ，則標記為 w_2 。

將所有標記為 w_2 的樣本取負（ y_ileftarrow -y_i ），則問題可以簡化為：尋找一個對所有樣本都有 a^ty_i>0 的權向量a。這裡a稱為分離向量（separating vector）或解向量（solution vector）。

所有可能的權向量構成「權空間」（weight space），解向量為權空間中的一點。對每個 y_i ， a^ty_i=0 確定一個權空間中穿過原點的超平面， y_i 為其法向量。解向量必然在每個訓練樣本確定的超平面的正側，即解向量必然在n個樣本確定的n個正半空間的交疊區中，該交疊區稱為「解區域」（solution region），其中任意向量都是解向量。

求解向量可通過最小化某個準則函數J(a)來實現，梯度下降法用於解決函數極小化問題，其基本思想為：

  • 隨意選擇一個權向量a(1)作為初始值
  • 計算J(a)在a(1)的梯度向量 ，其負方向代表從a(1)處J(a)下降最快的方向
  • 下一個值a(2)為從a(1)沿梯度的負方向移動一段距離而得到
  • 迭代公式為： a(k+1)=a(k)-eta(k) abla J(a(k)) 。

關於梯度下降法的有效性，可以見如下推導：

η是一個與d成正相關的變數，需要滿足足夠小的條件，上式才成立。

在梯度下降法中有一個問題，就是學習率的選擇，如果 eta_k 太小，演算法收斂非常緩慢,如果 eta_k 太大，演算法可能會過沖（overshoot），甚至無法收斂。

這裡，推導最優的學習率：

準則函數在a(k)附近的二階展開式為： J(a)simeq J(a(k))+ abla J^t(a-a(k))+frac{1}{2}(a-a(k))^tH(a-a(k))

其中， abla J 為J(a)在a(k)的梯度向量，H為赫森矩陣，即J(a)在a(k)的二階偏導，其中 h_{ij}=frac{partial^2J}{partial a_ipartial a_j} 。代入 a(k+1)=a(k)-eta(k) abla J(a(k)) 得：

J(a(k+1))simeq J(a(k))-eta(k)|| abla J||^2+frac{1}{2}eta^2(k) abla J^tH abla J

當 eta(k)=frac{|| abla J||^2}{ abla J^tH abla J} 時， J(a(k+1)) 最小。

在李宏毅的課程裡面，給出了另一個比較有效的 eta 值。

使用平方和模擬二階導數

在牛頓下降法中，直接求使得 J(a)simeq J(a(k))+ abla J^t(a-a(k))+frac{1}{2}(a-a(k))^tH(a-a(k)) 最小化得a最為a(k+1)。

所以迭代公式為： a(k+1)=a(k)-H^{-1} abla J 。

牛頓下降法的優點是在每一步給出了比梯度下降法更優的步長，但是如果赫森矩陣H奇異時，無法應用牛頓下降法並且即使H非奇異，計算H的逆矩陣的計算複雜度 O(d^3) 。

前面介紹了如何求解準則函數J(a)的最小值，接著下一個問題是如何構建準則函數。

首先介紹感知器準則函數： J_p(a)=sum_{yin Y}(-a^ty) ，其中 Y(a) 表示被a分錯的樣本集。感知器準則函數正比於錯分樣本到判決面距離之和。

感知器準則函數的梯度為： abla J_P=sum_{yin Y}(-y)

梯度下降迭代公式： a(k+1)=a(k)+eta(k)sum_{yin Y_k}y ，其中 Y_k 表示被a(k)錯分的樣本集。

感知器演算法主要有以下幾種，首先介紹批處理感知器演算法。

批處理時，每次修正權向量a時，需要「成批」考慮所有訓練樣本，這也是最常見的方案。

下面給出批處理感知器演算法：

接著介紹單樣本校正，在批處理感知器演算法中，每次校正需要考察所有樣本，在單樣本校正每次僅考察一個錯分樣本。

可以順序考慮輸入樣本，一旦發現某個樣本錯分，立即對當前權向量進行修正。為了保證每個樣本都可以在序列中無限次出現，可以使訓練樣本按順序不斷循環出現在序列中，直至演算法收斂。除此之外，還可以隨機抽取樣本。

下面給出固定增量單樣本感知器演算法：

接著給出帶邊沿裕量的變增量感知器演算法：

感知器演算法本質上是「誤差校正方法」，如果問題本身線性不可分，則校正過程可能永遠無法結束。

所以，開始介紹第二種準則函數，最小平方誤差函數。

這裡，不再僅僅是錯分樣本，而是包含所有樣本的準則函數，不再追求 a^ty_i>0 ，轉而令 a^ty_i=b_i ，其中 b_i 為任意取定的正常數。將線性不等式組求解轉換成線性方程組求解：

在上式中，n為樣本個數，d為特徵數，也是樣本的維度。該線性方程組可寫為 Ya=b 。如果Y是非奇異的，則解為： a=Y^{-1}b 。通常情況下， n>d ，即Y的行數大於列數，線性方程組超定，a通常無精確解。

定義誤差向量： e=Ya-b ，在a無解的情況下，求使得誤差向量長度的平方最小的a，作為線性方程組的近似解。最小平方誤差（最小誤差平方和）準則函數為：

J_s(a)=||Ya-b||^2=sum_{i=1}^n(a^ty_i-b_i)^2

Widrow-Hoff演算法：

採用梯度下降法求 J_s(a)=||Ya-b||^2 的極小值： abla J_s=2Y^t(Ya-b) 。

遞歸公式為： a(k+1)=a(k)-eta(k)Y^t(Ya_k-b) 。

單樣本情況下： a(k+1)=a(k)+eta(k)(b_k-a(k)^ty^k)y^k

Widrow-Hoff演算法將訓練點到超平面的距離平方和最小化，即使在線性可分情況下，Widrow-Hoff演算法的解也可能不能將所有訓練樣本完全正確分類，但是， Widrow-Hoff演算法在線性可分和不可分情況下，都能得到不錯的近似解。

接下來，簡單介紹以下支持向量機，關於支持向量機的細節會在其他支持向量機專題文章裡面詳述。

支持向量機（Support Vector Machine, SVM）依賴於對數據的一種特殊預處理，從而實現對線性不可分數據的較好分類。該預處理通過一個非線性映射 varphi(x) 將原數據映射到一個更高維的空間 y_k=varphi(x_k) ，使得在此高維空間中的映射點 y_k 線性可分。非線性映射反映了設計者的先驗知識，在缺乏先驗知識的前提下，常用的非線性映射函數有：多項式函數、高斯函數等。儘管SVM自上世紀90年代開始成為一個非常熱門的領域，其基本思想卻早在1963年就由V.N. Vapnik提出來了。

介紹支持向量機中第一個重要概念，間隔（margin）。模式到判決面的最小距離稱為分類間隔。一般認為，分類間隔越大的判決面越好，離判決面最近的樣本點稱為支持向量（support

vector）。

高維空間中權向量a和映射點y都是增廣的，則判別函數為 g(y)=a^ty 。對於二元分類，記 z_k=+1 表示 x_k 屬於 w_1 , z_k=-1 表示 x_k 屬於 w_2 。設邊沿裕量為1，則有 z_kg(y_k)geq 1 。

樣本點到判決面的距離為： frac{|acdot y|}{||a||}=frac{|g(y_k)|}{||a||}=frac{z_kg(y_k)}{||a||}geq frac{1}{||a||}

優化目標為：最大化 frac{1}{||a||} ，即最小化 ||a|| ，約束條件為 z_kg(y_k)geq 1 。

根據KTT條件，可將上述優化目標轉換為：

L(alpha)=sum_{k=1}^{n}alpha_i-frac{1}{2}alpha_kalpha_jz_kz_jy_j^ty_k ，約束條件為 sum_{k=1}^nz_kalpha_k=0 , alphageq 0,k=1,...,n 。

分析可知線性分類器僅僅依賴於內積計算 x_i^tx_j ，如果所有樣本點都映射到高維（甚至可能為無限維）空間中 varphi:y_k=varphi(x_k) ，在此高維空間中的內積計算 varphi(x_i)^tvarphi(x_j) 往往很難計算或根本無法計算。核函數指原數據空間中對應於變換後空間中內積計算的某種函數 K(x_i,x_j)=varphi(x_i)^tvarphi(x_j) 。這表明：較複雜的高維空間中的內積計算可以通過低維空間中的核函數間接進行。如果一個問題僅包含內積計算，則可以不指定具體的映射函數，而僅需知道該映射函數對應的核函數。

由Mercer定理，任何半正定對稱函數都可以作為核函數。這裡給出半正定定義：由 a_{ij}=k(x_i,x_j) 組成的矩陣A為半正定矩陣，即對任意非零實數向量z，有 z^tAzgeq0 。

對稱則表明： k(x_i,x_j)=k(x_j,x_i) 。

常見的核函數包括：

多項式核： k(x,y)=(x^ty+1)^d

高斯核： k(x,y)=exp(-frac{||x-y||^2}{2sigma^2})

推廣到多類問題：

  • 如果 {y_1,y_2,...,y_n} 線性可分，則存在一個權向量集 {a_1,a_2,...,a_c} ，當 y_kin Y_i 時，對所有 j e i ，有 a_iy_k>a_jy_k 。
  • {a_1,...,a_c} 確定後，對測試樣本y，如果對所有 j e i ，有, a_iy>a_jy ,則判斷y屬於第i類。

假設 yin Y_1 ，則 a_1y-a_jy>0,j=2,...c 。記 alpha=[a_1,a_2,...,a_c]^T ，

記：

這裡每個 eta_{1j} 對應於將屬於 w_1 和 w_j 的樣本規範化，即屬於 w_j 的樣本取負，這樣可以保證 alphaeta_{1j}>0 ，多類問題成功轉化為兩類問題。

這裡給出多元分類的Kesler構造法：

?當 yin Y_i 時，可類似構造c-1個訓練樣本 eta_{ij} ，其中第i個子向量為y，第j個子向量為-y，其餘都為0。如果對於所有 j e i ，都有 alphaeta_{ij}>0 ，則α中的分量構成能將多類樣本集正確分類的線性機的c個權向量。

最後，簡單介紹多層神經網路。

一個神經網路的基本組成包括神經元（neuron）和權值（weight）。神經元之間通過權值相連。神經網路學習得到的知識通過權值和神經元中的偏置編碼，即神經網路訓練過程為通過訓練數據確定所有的權值和偏置。

繼續前面的感知器話題，簡單感知器（simple perceptron）指僅包含輸入層和輸出層的兩層前饋神經網路。其函數形式為： y=sgn(sum_{i=1}^dw_ix_i+w_0)=sgn(w^tx+w_0) 。

感知器的學習過程如下（單樣本過程）：

感知器的不足：僅能處理線性可分情況並且即使在線性可分情況下，也可能無法給出最優解。

所以可以使用多層神經網路作為判定函數。包含一個隱藏層的前饋神經網路的模型如下圖所示：

其判別函數的形式為： g_k(x)=z_k=f(sum_{j=1}^{n_H}w_{kj}f(sum_{i=1}^{d}w_{ji}x_i+w_{j0})+w_{k0)} 。

另外，一般逼近理論提到，One layer of hidden units with sigmoid activation function is sufficient for approximating any function with finitely many discontinuities to arbitrary precision. 給出了神經網路提供了理論支持。但是，這隻具有理論上的意義，即多層網路能實現任意決策。該理論告訴我們「Can」，但沒告訴我們「How」，網路的結構設計和訓練方法需要具體問題具體分析。

最後一個子問題是神經網路中的反向傳播演算法。

以前面提到的最小平均方差作為準則函數為例，分析反向傳播演算法過程。

J(w)=frac{1}{2}sum_{k=1}^c(t_k-z_k)^2=frac{1}{2}(t-z)^2

Delta w=-etafrac{partial J}{partial w} ， Delta w_{mn}=-etafrac{partial J}{partial w_{mn}}

w(m+1)=w(m)+Delta w(m)

分析 g_k(x)=z_k=f(sum_{j=1}^{n_H}w_{kj}f(sum_{i=1}^{d}w_{ji}x_i+w_{j0})+w_{k0)} ：

隱含層到輸出層的權值更新情況：

frac{partial J}{partial w_{kj}}=frac{partial J}{partial net_k}frac{partial net_k}{partial w_{kj}}=-delta_kfrac{partial net_k}{partial w_{kj}} ,

這裡， delta_kequiv -frac{partial J}{partial net_k}=-frac{partial J}{partial z_k}frac{partial z_k}{partial net_w}=(t_k-z_k)f(net_k) ；net為激活函數。

又 frac{partial net_k}{partial w_{kj}}=y_j

故 Delta w_{kj}=etadelta_ky_j=eta(t_k-z_k)f(net_k)y_i 。

輸入層到隱含層的權值更新情況：

frac{partial J}{partial w_{ji}}=frac{partial J}{partial y_j}frac{partial y_i}{partial net_j}frac{partial net_j}{partial w_{ji}}

其中， f(net_j)=frac{partial y_i}{partial net_j}， frac{partial net_j}{partial w_{ji}}=x_i

delta_jequiv f(net_j)sum_{k=1}^cw_{kj}delta_k ，輸出單元的敏感度反向傳播到了隱單元。

Delta w_{ji}=eta x_idelta_j=eta x_i f(net_j)sum_{k=1}^cw_{kj}delta_k

可以使用訓練協議調整權值，這裡給出三種常見的方式。

  • 隨機訓練：模式隨機從訓練集中選取，每輸入一個模式，權值就更新一次
  • 成批訓練：所有模式一次全部送入網路，然後才進行一次權值更新
  • 在線訓練：每種模式只提供一次，每提供一種模式，權值更新一次

推薦閱讀：
相关文章