感覺機學習小結

什麼是感覺機

• 是一種人工神經網絡

     感覺機可以通過數學統計學方法完成對函數的估計或近似，能在外界資訊的基礎上改變内部結構，是一種自适應系統，通俗的講就是具備學習功能。

• 是一種最簡單形式的前饋神經網絡

     感覺機模型的參數從輸入層向輸出層單向傳播，整個網絡中無回報。感覺機是最簡單形式是因為隻包含一層傳播。

• 是一種二進制線性分類器

     感覺機的輸出結果隻有+1 和–1二值，是以說感覺機是一個二進制分類器；

     在二維空間中，感覺機的模型就是一條直線，将平面中的正負樣本點分離成兩份，在三維中，感覺機的模型就是一個平面，将空間中的正負樣本點分離成兩份，放到更高維的空間中，感覺機的模型就是一個超平面；

     這也就是說，如果在二維空間中，不存在直線剛好将正負樣本點分離成兩份，在三維空間中，不存在平面将空間中的正負樣本點分離成兩份，那麼你的資料就無法使用感覺機模型；

     感覺機的使用前提是資料本身線性可分。

感覺機模型

   假設我們有n個樣本，每個樣本包含m維輸入特征和一個二進制類别輸出,如下所示：

​ ( x 1 ( 1 ) , x 1 ( 2 ) , x 1 ( 3 ) , … , x 1 ( m ) , y 1 ) , ( x 2 ( 1 ) , x 2 ( 2 ) , x 2 ( 3 ) , … , x 2 ( m ) , y 2 ) , … . ( x n ( 1 ) , x n ( 2 ) , x n ( 3 ) , … , x n ( m ) , y n ) (x^{(1)}_{1}, x^{(2)}_{1}, x^{(3)}_{1}, …, x^{(m)}_{1}, y_{1}), (x^{(1)}_{2}, x^{(2)}_{2}, x^{(3)}_{2}, …, x^{(m)}_{2}, y_{2}),….(x^{(1)}_{n}, x^{(2)}_{n}, x^{(3)}_{n}, …, x^{(m)}_{n}, y_{n}) (x1(1)​,x1(2)​,x1(3)​,…,x1(m)​,y1​),(x2(1)​,x2(2)​,x2(3)​,…,x2(m)​,y2​),….(xn(1)​,xn(2)​,xn(3)​,…,xn(m)​,yn​)

   其中， ( x 1 ( 1 ) , x 1 ( 2 ) , x 1 ( 3 ) , … , x 1 ( m ) , y 1 ) (x^{(1)}_{1}, x^{(2)}_{1}, x^{(3)}_{1}, …, x^{(m)}_{1}, y_{1}) (x1(1)​,x1(2)​,x1(3)​,…,x1(m)​,y1​) 代表一個樣本， x 1 ( 1 ) x^{(1)}_{1} x1(1)​表示樣本的一個輸入特征，其下标表示這是第幾個樣本，上标表示這是這個樣本的第幾個輸入特征； y 1 y_1 y1​ 表示樣本的輸出，其下标表示這是第幾個樣本；

   我們的目的是找到這樣一個超平面，即：

​ θ 0 + θ 1 x ( 1 ) + θ 2 x ( 2 ) + … + θ m x ( m ) = 0 \theta_{0}+\theta_{1}x^{(1)}+\theta_{2}x^{(2)}+…+\theta_{m}x^{(m)}=0 θ0​+θ1​x(1)+θ2​x(2)+…+θm​x(m)=0

   其滿足對于是以有的正樣本： θ 0 + θ 1 x ( 1 ) + θ 2 x ( 2 ) + … + θ m x ( m ) &gt; 0 \theta_{0}+\theta_{1}x^{(1)}+\theta_{2}x^{(2)}+…+\theta_{m}x^{(m)}&gt;0 θ0​+θ1​x(1)+θ2​x(2)+…+θm​x(m)>0 ，對于所有的負樣本：$ \theta_{0}+\theta_{1}x{(1)}+\theta_{2}x{(2)}+…+\theta_{m}x^{(m)}<0$ ；進而得到線性可分。如果資料線性可分，這樣的超平面一般都不是唯一的，也就是說感覺機模型可以有多個解。

   簡化超平面：将 θ 1 x ( 1 ) + θ 2 x ( 2 ) + … + θ m x ( m ) \theta_{1}x^{(1)}+\theta_{2}x^{(2)}+…+\theta_{m}x^{(m)} θ1​x(1)+θ2​x(2)+…+θm​x(m) 記為向量 ( θ 1 , θ 2 , θ 3 , … , θ m ) (\theta_{1}, \theta_{2}, \theta_{3}, …, \theta_{m}) (θ1​,θ2​,θ3​,…,θm​) 與輸入特征向量 ( x ( 1 ) , x ( 2 ) , x ( 3 ) , … , x ( m ) ) (x^{(1)}, x^{(2)}, x^{(3)}, …, x^{(m)}) (x(1),x(2),x(3),…,x(m)) 的内積，可得超平面為：

​ θ 0 + ( θ 1 , θ 2 , θ 3 , … , θ m ) ⋅ ( x ( 1 ) , x ( 2 ) , x ( 3 ) , … , x ( m ) ) = 0 \theta_{0}+(\theta_{1}, \theta_{2}, \theta_{3}, …, \theta_{m}) \cdot (x^{(1)}, x^{(2)}, x^{(3)}, …, x^{(m)})=0 θ0​+(θ1​,θ2​,θ3​,…,θm​)⋅(x(1),x(2),x(3),…,x(m))=0

   将 θ 0 \theta_{0} θ0​ 記為 b （偏置 bias），将 ( θ 1 , θ 2 , θ 3 , … , θ m ) (\theta_{1}, \theta_{2}, \theta_{3}, …, \theta_{m}) (θ1​,θ2​,θ3​,…,θm​) 記做 w （權值 weight），可得超平面為：

​ w ⋅ x + b = 0 w \cdot x + b = 0 w⋅x+b=0

   是以，我們将感覺機模型定義為：

​ f ( x ) = s i g n ( w ⋅ x + b ) f(x) = sign(w \cdot x+b) f(x)=sign(w⋅x+b)

   其中：

​ s i g n ( x ) = { + 1 x ≥ 0 − 1 x &lt; 0 sign(x)=\begin{cases} +1 &amp; x \geq 0 \\-1 &amp; x&lt;0\end{cases} sign(x)={+1−1​x≥0x<0​

感覺機損失函數

   我們知道了感覺機模型，我們還需要評價感覺機模型的方法，也就是損失函數。我們将所有誤分類點到超平面的總距離作為感覺機模型的損失函數。

   首先我們知道空間 R R R 中任一點 x x x 到平面 S S S 的距離是：

​ 1 ∣ ∣ w ∣ ∣ ∣ w ⋅ x + b ∣ \frac{1}{||w||} |w \cdot x + b| ∣∣w∣∣1​∣w⋅x+b∣

   其中： ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣ 是 w w w 的 L 2 L_2 L2​ 範數 ( L 2 L_2 L2​ 範數是指向量各元素的平方和然後求平方根)。

   接下來，我們假設所有誤分類點的集合為 M M M ，因為當 w ⋅ x + b &gt; 0 w\cdot x+b&gt;0 w⋅x+b>0時， ＝ y ＝ − 1 ＝y＝-1 ＝y＝−1，而當 w ⋅ x + b &lt; 0 w \cdot x+b&lt;0 w⋅x+b<0時， ＝ y ＝ + 1 ＝y＝+1 ＝y＝+1 。是以對于誤分類點來說其到平面 S S S 的距離可寫作：

​ − 1 ∣ ∣ w ∣ ∣ y ( w ⋅ x + b ) -\frac{1}{||w||} y(w \cdot x + b) −∣∣w∣∣1​y(w⋅x+b)

   那麼所有誤分類點 M M M 到超平面 S S S 的總距離為:

​ − 1 ∣ ∣ w ∣ ∣ ∑ x ∈ M y ( w ⋅ x + b ) -\frac{1}{||w||} \sum_{x \in M}{y(w \cdot x + b)} −∣∣w∣∣1​x∈M∑​y(w⋅x+b)

   不考慮 − 1 ∣ ∣ w ∣ ∣ -\frac{1}{||w||} −∣∣w∣∣1​ ，我們就得到了感覺機學習的損失函數。

​ L ( w , b ) = − ∑ x ∈ M y ( w ⋅ x + b ) L(w,b)=-\sum_{x \in M}{y(w \cdot x + b)} L(w,b)=−x∈M∑​y(w⋅x+b)

感覺機學習算法

   我們知道了評價感覺機模型的方法，也就是損失函數。那麼我們對于模型的優化也就是求解損失函數的極小化。

   求解 w , b w, b w,b ， 使其為以下損失函數極小化問題的解：

​ m i n w , b L ( w , b ) = − ∑ x ∈ M y ( w ⋅ x + b ) min_{w,b}L(w,b)=-\sum_{x \in M}{y(w \cdot x + b)} minw,b​L(w,b)=−x∈M∑​y(w⋅x+b)

   我們采用随機梯度下降法求解損失函數極小化問題。極小化過程中不是一次使M中所有誤分類點的梯度下降，而是一次随機選取一個誤分類點使其梯度下降。

   我們知道對于誤分類集合M固定時，那麼損失函數L(w,b)的梯度為：

​ ∇ w L ( w , b ) = − ∑ x ∈ M y x \nabla_{w}L(w,b)=-\sum_{x\in M}yx ∇w​L(w,b)=−x∈M∑​yx

​ ∇ b L ( w , b ) = − ∑ x ∈ M y \nabla_{b}L(w,b)=-\sum_{x\in M}y ∇b​L(w,b)=−x∈M∑​y

   我們每次随機選取一個誤分類點 ( x i , y i ) (x_{i}, y_{i}) (xi​,yi​) 對 w , b w, b w,b 進行更新，那麼對 w , b w, b w,b 的更新為：

​ w ← w + η y i x i w\leftarrow w+\eta y_{i}x_{i} w←w+ηyi​xi​

​ b ← b + η y i b \leftarrow b+\eta y_{i} b←b+ηyi​

   其中 η ( 0 &lt; η ≤ 1 ) \eta (0 &lt; \eta \leq 1) η(0<η≤1) 是步長，在機器學習中又稱為學習率(learning rate)。

​

   具體的訓練步驟如下：

   (1) 任意選取平面 S 0 S_{0} S0​ ,使用 ( w 0 , b 0 ) (w_{0}, b_{0}) (w0​,b0​) 表示平面 S 0 S_{0} S0​ ;

   (2) 在誤分類點集 M M M 中選取一個誤分類點 ( x i , y i ) (x_{i}, y_{i}) (xi​,yi​) ；

   (3) 對 ( w , b ) (w, b ) (w,b) 進行一次梯度下降，即：

    w ← w + η y i x i w\leftarrow w +\eta y_{i}x_{i} w←w+ηyi​xi​

    b ← b + η y i b \leftarrow b +\eta y_{i} b←b+ηyi​

   (4) 使用新平面 S S S 判斷是否任有誤分類點，如有跳轉至第二步，如無即完成模型訓練；

   這種學習算法易于了解，可直覺解釋為：當存在樣本點被誤分類時，就調整分離超平面的位置也就是 ( w , b ) (w,b) (w,b)，使分離超平面超誤分類點的一側移動，以減少該誤分類點與分離超平面間的距離，直至分離超平面越過該誤分類點使其被正确分類。

   此學習算法為感覺機學習的基本算法，對應于後面将提到的對偶形式，稱為感覺機學習算法的原始形式。

感覺機學習算法的對偶形式

   感覺機學習算法的對偶形式相較與原始形式來說，要難了解一些。但是如果你已經完全了解原始形式，那麼對偶形式也很好了解；如果你對于原始形式還不是很了解，我建議完全消化了原始形式再來看對偶形式。

   從某種角度來說，可以認為對偶形式是原始形式數學層面的優化，其存在的意義在于優化感覺機學習算法的學習效率。

   其實也不盡然，對偶形式不僅僅是數學層面的優化，其基本思路是能夠解釋得通的，而且這個思路在其它機器學習算法中是可以沿用的。本節将盡可能解釋其基本思路。

   首先，在原始算法中我們使用 ( w , b ) (w, b) (w,b) 來表示最終的分離超平面 S S S ，通過分析原始形式的疊代過程，也就是：

​ w ← w + η y i x i w\leftarrow w+\eta y_{i}x_{i} w←w+ηyi​xi​

​ b ← b + η y i b \leftarrow b+\eta y_{i} b←b+ηyi​

   我們知道，每次對于 w w w 的更新是在原 w w w 的基礎上加上了某一個誤分類點的輸入特征、輸出特征與學習率 η \eta η 的乘積，每次對于 b b b 的更新是在原 b b b 的基礎上加上了某一個誤分類點的輸出特征與學習率 η \eta η 的乘積， ( w , b ) (w, b) (w,b) 每次疊代的增量分别是 η y i x i \eta y_{i}x_{i} ηyi​xi​、 η y i \eta y_{i} ηyi​ 。

   那麼我們可以認為， ( w , b ) (w, b) (w,b) 最終由初始 ( w 0 , b 0 ) (w_{0}, b_{0}) (w0​,b0​) 加上增量總群組成， ( w , b ) (w, b) (w,b) 的增量總和可以使用 $ \sum_{i=1}{N}a_{i}y_{i}x_{i}$、$\sum_{i=1}{N}a_{i}y_{i}$ 來分别表示，這裡的 a = ( a 1 , a 2 , a 3 , … , a n ) T = ( n 1 η , n 2 η , n 3 η , … , n n η ) T a = {(a_{1}, a_{2}, a_{3},… ,a_{n})}^T = {(n_{1}\eta, n_{2}\eta, n_{3}\eta,… ,n_{n}\eta)}^T a=(a1​,a2​,a3​,…,an​)T=(n1​η,n2​η,n3​η,…,nn​η)T , n i n_{i} ni​ 為疊代過程中樣本集中第 i i i 個樣本共被選中幾次進行梯度下降.

   綜上所訴，可以用以下公式來表示 ( w , b ) (w, b) (w,b) :

​ w = w 0 + ∑ i = 1 N a i y i x i w = w_{0} + \sum_{i=1}^{N}a_{i}y_{i}x_{i} w=w0​+i=1∑N​ai​yi​xi​

​ b = b 0 + ∑ i = 1 N a i y i b = b_{0} + \sum_{i=1}^{N}a_{i}y_{i} b=b0​+i=1∑N​ai​yi​

   因為， ( w 0 , b 0 ) (w_{0}, b_{0}) (w0​,b0​) 為随機標明的初始分離超平面，可令初始值 w 0 , b 0 w_{0},b_{0} w0​,b0​ 均為0，那麼 ( w , b ) (w, b) (w,b) 為：

​ w = ∑ i = 1 N a i y i x i w = \sum_{i=1}^{N}a_{i}y_{i}x_{i} w=i=1∑N​ai​yi​xi​

​ b = ∑ i = 1 N a i y i b = \sum_{i=1}^{N}a_{i}y_{i} b=i=1∑N​ai​yi​

   那麼，感覺機模型 f ( x ) = s i g n ( w ⋅ x + b ) f(x) = sign(w \cdot x+b) f(x)=sign(w⋅x+b) 被重新定義為：

​ f ( x ) = s i g n ( ∑ i = 1 N a i y i x i ⋅ x + b ) f(x) = sign( \sum_{i=1}^{N}a_{i}y_{i}x_{i} \cdot x+b) f(x)=sign(i=1∑N​ai​yi​xi​⋅x+b)

   我們求解的值由 ( w , b ) (w, b) (w,b) 變更為 ( a , b ) (a, b) (a,b) 。

   具體的訓練步驟如下：

   (1) 令 ( a , b ) (a, b) (a,b) 均為0；

   (2) 在誤分類點集 M M M 中選取一個誤分類點 ( x i , y i ) (x_{i}, y_{i}) (xi​,yi​) ；

   (3) 對 ( a , b ) (a, b ) (a,b) 進行一次更新，即：

    a i ← a i + η a_{i}\leftarrow a_{i}+\eta ai​←ai​+η

    b ← b + η y i b \leftarrow b+\eta y_{i} b←b+ηyi​

   (4) 使用新平面 S 1 S_{1} S1​ 判斷是否任有誤分類點，如有跳轉至第二步，如無即完成模型訓練；

   那麼，為什麼說對偶形式相對于原始形式計算速度更快呢？？

   這是因為，在原始形式中，每次疊代 ( w , b ) (w, b) (w,b) ，我們要計算 n n n(樣本數量)次 w ⋅ x w \cdot x w⋅x ，這裡的計算量非常大；而在對偶形式中，觀察模型函數可以看到，我們涉及到的内積計算是 x i ⋅ x x_{i} \cdot x xi​⋅x ，我們可以事先計算出訓練集中樣本之間的内積并以矩陣的形式存儲，這個矩陣就是所謂的 Gram 矩陣：

    G = [ x i ⋅ x j ] N × N G = [x_{i} \cdot x_{j}]_{N \times N} G=[xi​⋅xj​]N×N​

那麼每次疊代過程中都不再涉及内積計算了，直接從 Gram 矩陣擷取。這就是為什麼說對偶形式相對于原始形式計算速度更快的原因。

總結

   感覺機算法是一個簡單易懂的機器學習算法，但是麻雀雖小五髒俱全，其所涉及到的學習方法、損失函數求解以及優化方法是機器學習的核心思想。也是支援向量機、神經網絡等算法的基石。雖說現在的實用價值不高了，但是對感覺機算法的融會貫通會讓你更容易了解在此基礎上發展的更為複雜的其它算法。