李航《統計學習方法》第二章習題和筆記

• 感覺機模型
• 點到平面公式的推導兩種思路
• 習題

感覺機模型

模型： f ( x ) = s i g n ( w ⃗ ⋅ x ⃗ + b ) f(x) = {\rm sign}(\vec w \cdot \vec x +b) f(x)=sign(w

⋅x

+b) 注意w和b是n維向量，b是常數偏置

政策：損失函數： L ( w ⃗ , b ) = − ∑ x i ∈ M y i ( w ⃗ ⋅ x ⃗ i + b ) L(\vec w, b) = -\sum \limits_{x_i\in M}y_i(\vec w \cdot \vec x_i +b) L(w

,b)=−xi​∈M∑​yi​(w

⋅x

i​+b) M是誤分類點的集合，L是誤分類點到超平面的總距離。政策即為通過算法，學習出使得損失函數最小的參數w和b

算法：随機梯度下降（SGD）

書中給出的梯度公式過分簡潔，工科生表示一下子轉不過來。精确到參數向量/梯度向量的每一個次元的話，可以寫成這樣：（參考吳老大cs229 lecture notes）

∇ w L ( w ⃗ , b ) = ∂ ∂ w L ( w ⃗ , b ) = ( ∂ ∂ w ( 1 ) L ( w ⃗ , b ) , ⋯   , ∂ ∂ w ( n ) L ( w ⃗ , b ) ) T \nabla_wL(\vec w, b)=\frac{\partial}{\partial w}L(\vec w, b) =\left( \frac{\partial}{\partial w^{(1)}}L(\vec w, b) ,\cdots, \frac{\partial}{\partial w^{(n)}}L(\vec w, b)\right)^T ∇w​L(w

,b)=∂w∂​L(w

,b)=(∂w(1)∂​L(w

,b),⋯,∂w(n)∂​L(w

,b))T

其中梯度向量的第k項為：

∂ ∂ w ( k ) L ( w ⃗ , b ) = ∂ ∂ w ( k ) ( − ∑ x i ∈ M y i ( w ⃗ ⋅ x ⃗ i + b ) ) \dfrac{\partial}{\partial w^{(k)}}L(\vec w, b)=\dfrac{\partial}{\partial w^{(k)}}\left(-\sum \limits_{x_i\in M}y_i(\vec w \cdot \vec x_i +b)\right) ∂w(k)∂​L(w

,b)=∂w(k)∂​(−xi​∈M∑​yi​(w

⋅x

i​+b))

= ∂ ∂ w ( k ) ( − ∑ x i ∈ M y i ( w ( 1 ) x i ( 1 ) + ⋯ w ( k ) x i ( k ) ⋯ + w ( n ) x i ( n ) + b ) ) =\dfrac{\partial}{\partial w^{(k)}}\left(-\sum \limits_{x_i\in M}y_i\left(w^{(1)} x_i^{(1)}+\cdots w^{(k)} x_i^{(k)} \cdots+w^{(n)} x_i^{(n)}+b\right)\right) =∂w(k)∂​(−xi​∈M∑​yi​(w(1)xi(1)​+⋯w(k)xi(k)​⋯+w(n)xi(n)​+b))

= − ∑ x i ∈ M y i x i ( k ) =-\sum\limits_{x_i\in M}y_ix_i^{(k)} =−xi​∈M∑​yi​xi(k)​

對于每一個次元（k = 1~n）都是一樣的，由此可得到書中的梯度公式，對b過程一樣。

注意，随機梯度下降一次隻用了誤分類點集M中随機的一個（不像梯度下降算法，每次更新參數要用到每一個誤分類點處的梯度）

點到平面公式的推導兩種思路

從向量投影的角度考慮可以參考這篇博文

轉化為拉格朗日乘子法，對點到平面上任一點的距離做最小化，可以參考這篇pdf講義

習題

1： 感覺機不能表示異或

可以從直覺上看發現線性不可分，或者拿第3題的定理證。。

2：Python感覺機模型建立

3：定理證明

第一步：直覺了解凸殼定義。從公式可以看出來，凸殼内的一點是S内所有點的權重平均，或者說是總權重為1的線性組合。是以在任意一個次元上的值都介于S内點的最小值和最大值之間。是以這個集合代表了S内的點能圍出的最大的凸多邊形内的所有點。按公式畫個圖：

參考資料：

點面距離，投影 https://blog.csdn.net/yutao03081/article/details/76652943

點面距離，拉格朗日乘子法 http://www.staff.city.ac.uk/o.castro-alvaredo/teaching/lagrange.pdf

斯坦福cs229 講義: https://see.stanford.edu/Course/CS229