線性可分的數據集下，感知機模型是否是凸優化問題？

01-03

線性可分的數據集下，感知機演算法是可以收斂的，但是李航的統計學習方法上說感知機演算法存在很多解且依賴於初始值的選擇和選擇順序。但是如果感知機模型是凸優化問題那麼其一定存在一個最優解，我根據感知機模型的優化問題進行分析推導發現其優化函數是線性函數，那麼這說明感知機模型是凸優化問題，那麼其應該存在最優解，和李航的書中出現矛盾，請大家幫忙解答！

我覺得題主疑惑的原因在於沒有意識到logistic regression和perceptron演算法的不同點。

logistic regression演算法做的事情是最小化這個目標函數（negative log-likelihood）：

$L(w) = sum_{i} left[ y_i log (1 + ext{e}^{-w^Tx_i}) + (1-y_i) log (1 + ext{e}^{w^Tx_i}) ight]$

其中 $x_i in mathbb{R}^n$ 表示第i個數據向量， $y_i in {0,1}$ 是 $x_i$ 的類別， $w in mathbb{R}^n$ 是待求的權重向量（偏移向量b可通過在每個 $x_i$ 末尾增加一個1而包括在w中，故省略）。可以證明，這個函數對w是凸的。logistic regression並沒有規定要用什麼演算法來求w，可以用最基本的梯度下降法，也可以用更高級的優化演算法。

與此不同的是，perceptron演算法規定了w的更新步驟，它的最顯著的後果是導致w不能取到 $mathbb{R}^n$ 中的任意值，而只能取各個數據向量的整係數線性組合。這個限制使得perceptron往往會錯過最優解。另外，perceptron演算法的終止條件是所有數據均正確分類，並不是最小化L(w)，所以它只會找到一個可行解，而不是使得L(w)最小的最優解。

====下面是題外話====

其實更有意思的是，「線性可分」這個條件對logistic regression演算法和perceptron演算法的影響是截然相反的。對於perceptron演算法來說，「線性可分」是演算法能夠結束的充要條件，是件好事。但對於logistic regression來說，「線性可分」卻是件壞事，它意味著目標函數沒有極小值——沒錯，目標函數是凸的，但存在一個方向，沿著這個方向走下去，目標函數是單調減小的（但有界）。感性認識就是，既然線性可分，那我們就希望那個S型曲面儘可能陡峭，而陡峭是沒有限度的（如下圖）。所以，在線性可分的數據集上做logistic regression，就必須加regularization以保證演算法收斂。

評論中有人讓我用圖來說明「線性可分」對logistic regression來說是件壞事。如圖，五根紅線和五根藍線表示了一個二維的線性可分的數據集。注意數據是二維的，即只有x1、x2坐標，我把它畫成立體的只是為了觀察方便。紅色數據點的x1坐標均為正，藍色數據點的x1坐標均為負。

第一個子圖中，w = (1, 0)，彩色的曲面表示的是每個坐標被劃分為紅色類別的概率，即 $h(x) = frac{1}{1 + ext{e}^{-w^Tx}}$ 。我們希望h(x)對於紅色數據點儘可能接近1，對於藍色數據點儘可能接近於0，這樣目標函數就更小。如果我們把w中元素的值增大，例如像第二個子圖那樣，調整為w = (3,0)，彩色的S形曲面就會變得更陡峭，h(x)也就更接近1或0。如果極端一些，讓 $w=(+infty, 0)$ ，如第三個子圖，此時h(x)在x&>0時等於1，在x&<0時等於0，目標函數是最小的。但是，我們並不希望w中的元素可以這樣無限增大，所以在線性可分時，需要加regularization。

我覺得感知機模型的優化求解並不是一個凸優化問題。

其問題在於它的目標函數----- 不是固定 -----的！

它的目標函數是說對錯誤分類點的損失最小化，而錯誤分類點在優化過程中是不斷變化的，那麼它的目標函數其實也是在發生一些不可預測的變化的，這能算凸優化嗎？不能嗎？能嗎？（若要使用來計算的點不變，需要加入indicate fucntion或者sign function這樣的非凸函數，所以答案很明顯了）

而題主之所以推導出來，可能是因為把錯誤分類點固定下來不變，來推導了吧？

謝邀。題主對凸函數的理解可能和我有點偏差。

一元線性函數y關於x的函數 $y=wcdot x+b$ ，即是凸函數也是凹函數。凸函數的性質是：凸函數的任何極小值也是最小值，而只有嚴格凸函數才是最多只有一個最小值。

而多元二次可微的連續函數 $L(w,b)=aw+b$ ,其中a是常數，w,b均為變數，其Hessen矩陣為2*2的零矩陣，半正定，所以也是凸函數，但非嚴格凸函數，不能由此推斷具有唯一解。

從原理上解釋，是因為：

感知機學習演算法其實是最基礎的二類分類的線性分類器，其實是後來支持向量機（SVM）提出的基礎，其分類平面為： $f(x)=sign(wcdot x+b)$

其中， $sign(x)$ 函數為符號函數，當x大於等於0的時候為1，小於0的時候為-1。

在線性可分的前提下，如果得到了判別函數，那麼對於一個新來的樣本，判別的標準很簡單，就是如果 $wcdot x+b>0$ ，那麼判定為正實例，如果 $wcdot x+b<0$ ，那麼判定為負實例。

基於上述準則，感知機的損失函數很自然就是為誤分類點的總數，也就是對分類錯誤的點進行懲罰。

對於某個誤分類的樣本點 $(x_{i} ,y_{i})$ ,其類標籤 $y_{i}$ 必然與判別平面的符號相反，

也就是，如果 $wcdot x+b<0$ ，那麼 $y_{i}=+1$ ；如果，那麼 $y_{i}=-1$ .

所以，損失函數為該誤分類點到分類平面的距離：

$-frac{1}{||w||}y_i(wcdot x_i+b)$

因為我們只考慮其符號問題，所以不考慮分母 $frac{1}{||w||}$ ，得到感知機的損失函數為：

$L(w,b)=-sum_{x_iin M}^{} y_i(wcdot x_i+b)$ ，其中M為誤分類的樣本點的集合。

可以對比下SVM的誤差損失函數：

$L(w,b)=-frac{1}{||w||}y_i(wcdot x_i+b)$

可以看出來，感知機的誤差損失函數L(w,b)其實是參數w,b的連續可導函數。

而SVM由於考慮了幾何間隔，考慮了分母 $frac{1}{||w||}$ ，從最大化間隔的角度考慮問題，可以化為凸規劃問題（凸規劃中，或者目標函數是凸函數，變數的約束函數是凸函數（不等式約束），或者是放射函數（等式約束）），SVM嚴格遵守凸規劃定義，而凸規劃中，局部最優解既是全局最優解，所以SVM求得的分類線性平面是唯一的；

在感知機中，你選擇不同的初始值進行迭代，在迭代中選擇誤分類點的順序不同，都可能導致其解的不同。如果你需要得到唯一的超平面，則需要對分離的超平面增加約束條件（如SVM里對間隔進行約束）從而使問題變為凸優化問題，具有唯一解。

在線性可分的情況下，最naive的感知機演算法就是凸的，題主可以想想max(0,f(x))在f(x)為凸的情況下是否為凸，這邊我就直接給出結論了。希望對您有幫助，謝謝。

補充：

關於存在多個最優解的情況，凸優化問題沒有說只存在唯一解，只有嚴格凸的問題才是存在唯一解的，這個可以參考boyd老師的《convex optimization》一書。

您好，請教一個問題可好？請問誤分類點到分類平面的距離：這個公式是如何得到的呢？如何理解呢？