線性模型（線性回歸、感知機和邏輯斯諦回歸）

線性模型.png

線性模型

根據(jù)周志華老師的定義來說澄成，線性模型是指其通過屬性的線性組合來進行預(yù)測的函數(shù)胧洒，即
$f ( \boldsymbol { x } ) = w _ { 1 } x _ { 1 } + w _ { 2 } x _ { 2 } + \ldots + w _ { d } x _ { d } + b$
用一般向量形式，則寫成
$f ( x ) = w ^ { \mathrm { T } } x + b$
其中墨状， $\omega = \left( \omega _ { 1 } ; \omega _ { 2 } ; \cdots ; \omega _ { d } \right)$ 卫漫，并且 $w$ 和 $b$ 學(xué)到以后，模型也就確定了肾砂。因此列赎，因此我們應(yīng)該對線性模型有了一個初步的理解，那就是一定會用訓(xùn)練集去學(xué)習(xí)出一條線從而作為模型函數(shù)通今，而究竟這條線是用來擬合數(shù)據(jù)還是分類數(shù)據(jù)粥谬，那就要看模型是屬性回歸模型還是分類模型了

對于線性模型來說，它有很多種辫塌，比如回歸模型中有線性回歸誊酌，分類模型中有感知機、邏輯斯諦回歸等霸株，接下來我們主要展開講解這三個模型

線性回歸

線性回歸是對給定的訓(xùn)練數(shù)據(jù)集進行線性擬合着绷，從而找到一條能使得大多數(shù)樣本點都盡可能被準(zhǔn)確預(yù)測的擬合線，比如公式如下：
$\mathrm { f } \left( x _ { i } \right) = \omega ^ { T } x _ { i } + b储矩，使得f \left( x _ { i } \right) \approx y _ { i }$

低維下的線性回歸

當(dāng)然感耙，在高維的情況下肯定就不再是一條線了，比如在三維情況下這條線就將會是一個曲面持隧，這里之所以稱為線性回歸即硼，相信應(yīng)該是諸多前輩們?yōu)榱宋覀冞@些人能夠直觀地理解吧

高維下的線性回歸

線性回歸的學(xué)習(xí)策略

對于線性回歸問題，我們最終的目的就是學(xué)習(xí)得到 $w$ 和 $b$ 屡拨，建立起這個模型公式只酥，而目前最首要的問題就是：如何確定 $w$ 和 $b$ 是最優(yōu)呢褥实？

一般，對于線性回歸問題裂允，我們采用的是均方誤差作為模型的性能度量损离，也就是我們會盡可能讓均方誤差最小化，而均方誤差最小的時候绝编，其參數(shù)w和b就是我們想要的最優(yōu)參數(shù)了僻澎，即
$\begin{aligned} \left( w ^ { * } , b ^ { * } \right) & = \underset { ( w , b ) } { \operatorname { argmin } } \sum _ { i = 1 } ^ { m } \left( f \left( x _ { i } \right) - y _ { i } \right) ^ { 2 } \\ & = \underset { ( w , b ) } { \operatorname { argmin } } \sum _ { i = 1 } ^ { m } \left( y _ { i } - w x _ { i } - b \right) ^ { 2 } \end{aligned}$
說明：

均方誤差的幾何意義是對應(yīng)的歐幾里得距離；
基于均方誤差最小化來進行模型求解的方法稱為“最小二乘法”十饥；
基于12窟勃，最小二乘法的幾何意義也就是找到一條直線，使得所有樣本到這條直線的歐氏距離之和最小
當(dāng)然绷跑，也是可以用梯度下降法去做參數(shù)求解的拳恋，只是感知機部分會用到，這里就重復(fù)展開

我們現(xiàn)在知道砸捏，我們想要找到最好的擬合線需要用到最小二乘法求解代價函數(shù)最小時的 $w$ 和 $b$ 谬运，然而最小二乘法是如何找到最佳參數(shù)的呢？這里我們不需要深究垦藏，只需要了解最小二乘法的代數(shù)法的求解過程是通過代價函數(shù) $\sum _ { i = 1 } ^ { m } \left( f \left( x _ { i } \right) - y _ { i } \right)$ 對參數(shù) $w$ 和 $b$ 進行求偏導(dǎo)梆暖，并令每個偏導(dǎo)值為0，進而求解整個方程組掂骏；其他的求解方法自然還有轰驳，比如矩陣法求解，具體內(nèi)容可以參考文章后面的博客（最小二乘法小結(jié)）

為更多地理解最小二乘法的求解方式弟灼，我們這里引入周志華老師的單變量線性回歸求解（代數(shù)法）和多變量線性回歸（矩陣法）求解

單變量線性回歸

首先级解，我們令 $E _ { ( w , b ) } = \sum _ { i = 1 } ^ { m } \left( y _ { i } - w x _ { i } - b \right) ^ { 2 }$
然后，分別對 $w$ 和 $b$ 進行求偏導(dǎo)田绑，得
$\begin{aligned} \frac { \partial E _ { ( w , b ) } } { \partial w } & = 2 \left( w \sum _ { i = 1 } ^ { m } x _ { i } ^ { 2 } - \sum _ { i = 1 } ^ { m } \left( y _ { i } - b \right) x _ { i } \right) \\ \frac { \partial E _ { ( w , b ) } } { \partial b } & = 2 \left( m b - \sum _ { i = 1 } ^ { m } \left( y _ { i } - w x _ { i } \right) \right) \end{aligned}$
接著勤哗，令偏導(dǎo)式為0，解得
$\begin{array} { c } { w = \frac { \sum _ { i = 1 } ^ { m } y _ { i } \left( x _ { i } - \overline { x } \right) } { \sum _ { i = 1 } ^ { m } x _ { i } ^ { 2 } - \frac { 1 } { m } \left( \sum _ { i = 1 } ^ { m } x _ { i } \right) ^ { 2 } } } \\ { b = \frac { 1 } { m } \sum _ { i = 1 } ^ { m } \left( y _ { i } - w x _ { i } \right) } \end{array}$
注：單變量線性回歸和多變量線性回歸的區(qū)別僅在于樣本點的特征數(shù)是一個還是多個掩驱，所以在單變量的時候芒划， $w$ 的參數(shù)只有一個，公式是 $f \left( x _ { i } \right) = \omega x _ { i } + b$ ,在多變量的時候 $w$ 的參數(shù)就有多個欧穴，公式是 $f \left( x _ { i } \right) = \omega ^ { T } x _ { i } + b$

多變量線性回歸

為方便起見民逼，我們將 $w$ 和 $b$ 吸收入向量形式 $\widehat { \omega } = ( \omega ; b )$ ；這里的樣本有 $d$ 個屬性涮帘，把數(shù)據(jù)集 $D$ 表示為一個 $m*(d+1)$ 大小的矩陣 $X$ 拼苍，其中每行對應(yīng)一個樣本，該行的前 $d$ 個元素對應(yīng)著樣本的前 $d$ 個屬性值调缨，如下
$\mathbf { X } = \left( \begin{array} { c c c c c } { x _ { 11 } } & { x _ { 12 } } & { \dots } & { x _ { 1 d } } & { 1 } \\ { x _ { 21 } } & { x _ { 22 } } & { \dots } & { x _ { 2 d } } & { 1 } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } & { \vdots } \\ { x _ { m 1 } } & { x _ { m 2 } } & { \dots } & { x _ { m d } } & { 1 } \end{array} \right) = \left( \begin{array} { c c } { x _ { 1 } ^ { \mathrm { T } } } & { 1 } \\ { x _ { 2 } ^ { \mathrm { T } } } & { 1 } \\ { \vdots } & { \vdots } \\ { x _ { m } ^ { \mathrm { T } } } & { 1 } \end{array} \right)$
另外映屋，把輸出的標(biāo)記也寫成向量形式 $y = \left( y _ { 1 } ; y _ { 2 } ; \cdots ; y _ { m } \right)$ 苟鸯，于是，我們得到目標(biāo)式如下：
$\hat { \boldsymbol { w } } ^ { * } = \underset { \boldsymbol { \hat { w } } } { \arg \min } ( \boldsymbol { y } - \mathbf { X } \hat { \boldsymbol { w } } ) ^ { \mathbf { T } } ( \boldsymbol { y } - \mathbf { X } \hat { \boldsymbol { w } } )$

現(xiàn)在棚点，我們先令 $E _ { \hat { \boldsymbol { w } } } = ( \boldsymbol { y } - \mathbf { X } \hat { \boldsymbol { w } } ) ^ { \mathrm { T } } ( \boldsymbol { y } - \mathbf { X } \hat { \boldsymbol { w } } )$

接著用 $E _ { \hat { \boldsymbol { w } } }$ 對 $\hat { \boldsymbol { w } }$ 求導(dǎo)，得到
$\frac { \partial E _ { \hat { \boldsymbol { w } } } } { \partial \hat { \boldsymbol { w } } } = 2 \mathbf { X } ^ { \mathrm { T } } ( \mathbf { X } \hat { \boldsymbol { w } } - \boldsymbol { y } )$

注：矩陣求導(dǎo)這部分大家應(yīng)該都是一樣在學(xué)校沒有學(xué)過的湾蔓，畢竟學(xué)矩陣的時候我們不學(xué)矩陣求導(dǎo)瘫析，學(xué)求導(dǎo)的時候我們還是不學(xué)矩陣求導(dǎo)，所以造成了似乎能看懂又看不太懂的情況默责，所以我把過程貼在下面贬循，有需要更深入了解的同學(xué)可以到文章后面參考博客《機器學(xué)習(xí)中的矩陣求導(dǎo)的一點總結(jié)（三種方法求線性回歸最佳參數(shù)）》
$\nabla _ { w } J ( w )$
$= \nabla _ { w } ( X w - Y ) ^ { T } ( X w - Y )$
$= \nabla _ { w } \left( w ^ { T } X ^ { T } X w - Y ^ { T } X w - w ^ { T } X ^ { T } Y + Y ^ { T } Y \right)$
$= \nabla _ { w } \left( w ^ { T } X ^ { T } X w \right) - \nabla _ { w } \left( Y ^ { T } X w \right) - \nabla _ { w } \left( w ^ { T } X ^ { T } Y \right)$
$= 2 * X ^ { T } X w - X ^ { T } Y - X ^ { T } Y$
$= 2 * X ^ { T } X w - 2 * X ^ { T } Y$

得到偏導(dǎo)式后，一般來說我們令其為0即可得到 $\hat { \boldsymbol { w } }$ 的解桃序；但是杖虾，由于計算過程涉及到了矩陣的求逆運算，所以我們必須分為兩種情況進行討論：

當(dāng) $X ^ { T } X$ 是滿秩矩陣時媒熊，可以直接令偏導(dǎo)式為0奇适，得到
$\hat { \boldsymbol { w } } ^ { * } = \left( \mathbf { X } ^ { \mathrm { T } } \mathbf { X } \right) ^ { - 1 } \mathbf { X } ^ { \mathrm { T } } \boldsymbol { y }$
當(dāng) $X ^ { T } X$ 不是滿秩矩陣時，我們可能會得到多組解芦鳍；例如矩陣X的列數(shù)多于行數(shù)嚷往，顯然不是滿秩矩陣，此時便會解除多個的值（用借用我們中學(xué)解線性方程組時柠衅，如果因變量的數(shù)目大于方程的數(shù)目皮仁，則必然會出現(xiàn)很多組解）；所以菲宴，面對多組解的情況贷祈，我們的做法是引入正則化項（似乎就是吳恩達視頻里的正規(guī)化方程，可以幫助解決矩陣的行數(shù)小于列數(shù)的情況）

感知機學(xué)習(xí)算法（Percetron Learning Algorithm）

感知機是基于數(shù)據(jù)集線性可分的前提下的一種二分類線性模型喝峦，即把數(shù)據(jù)集中的所有實例用一個超平面進行分離势誊，其超平面的一側(cè)為正例（即+1），另一側(cè)為負(fù)例（-1）愈犹。因此键科，這個模型就是相當(dāng)于把整個特征空間進行二分化，然后對每一個測試樣例進行分類進而得到測試樣例的標(biāo)簽漩怎。比如勋颖，公式如下：
$f ( x ) = \operatorname { sign } ( w \cdot x + b )$
說明：

數(shù)據(jù)集線性可分是指：對于給定的一個數(shù)據(jù)集 $T = \left\{ \left( x _ { 1 } , y _ { 1 } \right) , \left( x _ { 2 } , y _ { 2 } \right) , \cdots , \left( x _ { N } , y _ { N } \right) \right\}$ ，其中 $x _ { i } \in \mathcal { X } = R ^ { n }$ 勋锤， $y _ { i } \in y = \{ + 1 , - 1 \}$ 饭玲， $\mathrm { i } = 1,2 , \cdots , \mathrm { N }$ ，如果存在一個超平面S可以使得正實例點和負(fù)實例點完全正確地劃分到超平面的兩側(cè)叁执，則稱數(shù)據(jù)集T為線性可分?jǐn)?shù)據(jù)集
sign是符號函數(shù)茄厘，即
$\operatorname { sign } ( x ) = \left\{ \begin{array} { l l } { + 1 , } & { x \geqslant 0 } \\ { - 1 , } & { x < 0 } \end{array} \right.$
感知機模型屬于判別模型矮冬；
感知機的幾何解釋：
- 線性方程 $wx+b$ 對應(yīng)于特征空間 $R^n$ 中的一個超平面 $S$ ， $S$ 被稱為分離超平面
- $w$ 是超平面的法向量
- $b$ 是超平面的截距
- 圖示如下：
  
  感知機

感知機的學(xué)習(xí)策略

因為感知機算法的本身就是要通過訓(xùn)練集去找到一個分離超平面次哈，而想要找到這樣的超平面就需要確定參數(shù) $w$ 和 $b$ 胎署，和線性回歸的問題一樣，我們怎樣才能確定參數(shù) $w$ 和 $b$ 呢窑滞？因此琼牧，大佬們制定了策略，即定義一個損失函數(shù)哀卫，我們的目標(biāo)就是讓損失函數(shù)極小化巨坊，從而在極小化的基礎(chǔ)上找到參數(shù) $w$ 和 $b$ ，所以此改，我們現(xiàn)在分兩步走趾撵，第一步是找到我們需要的損失函數(shù)，第二步就是我們?nèi)绾巫屵@個損失函數(shù)最小化

第一步：如何找到損失函數(shù)共啃？

根據(jù)《統(tǒng)計學(xué)習(xí)方法》的說法占调，感知機的損失函數(shù)是選擇誤分類點到超平面 $S$ 的總距離，而不是誤分類點的總數(shù)勋磕。為此妈候，我們根據(jù)公式（可聯(lián)系點到平面的公式）得到任意一點到 $x_{i}$ 超平面 $S$ 的距離為：
$\frac { 1 } { \| w \| } \left| w \cdot x _ { 0 } + b \right|$
注意，這里的是的范式挂滓；因此苦银，我們也能得到所有誤分類點到超平面S的距離：
- 說明：
  1. $M$ 是誤分類點的集合
  2. 為什么去掉了絕對值后多了個 $-y_{i}$ ？這是因為我們?yōu)榱巳サ艚^對值赶站，考慮了兩種情況
    - 當(dāng) $\omega x _ { i } + b > 0$ 時幔虏， $y _ { i } = - 1$ ，此時 $- y _ { i } \left( \omega x _ { i } + b \right) > 0$
    - 當(dāng) $\omega x _ { i } + b < 0$ 時贝椿， $y _ { i } = + 1$ 想括，此時 $- y _ { i } \left( \omega x _ { i } + b \right) > 0$
    所以，基于上面兩種情況烙博，我們才把絕對值去掉后的公式形式寫成了 $- y _ { i } \left( \omega x _ { i } + b \right)$
更進一步瑟蜈，我們將分母忽略，于是就得到了我們感知機的損失函數(shù)渣窜，如下：
- 說明：
  - 這里我們引用某個博主的解答铺根，如下:
    1. $\frac { 1 } { \| w\| }$ 不影響 $- y _ { i } \left( \omega x _ { i } + b \right)$ 正負(fù)的判斷，即不影響學(xué)習(xí)算法的中間過程乔宿。因為感知機學(xué)習(xí)算法是誤分類驅(qū)動的位迂，這里需要注意的是所謂的“誤分類驅(qū)動”指的是我們只需要判斷 $- y _ { i } \left( \omega x _ { i } + b \right)$ 的正負(fù)來判斷分類的正確與否，而 $\frac { 1 } { \| w\| }$ 并不影響正負(fù)值的判斷。所以 $\frac { 1 } { \| w\| }$ 對感知機學(xué)習(xí)算法的中間過程可有可無掂林；
    2. $\frac { 1 } { \| w\| }$ 不影響感知機學(xué)習(xí)算法的最終結(jié)果臣缀。因為感知機學(xué)習(xí)算法最終的終止條件是所有的輸入都被正確分類，即不存在誤分類的點泻帮。則此時損失函數(shù)為0精置，對應(yīng)于 $- y _ { i } \left( \omega x _ { i } + b \right) / \| w\|$ ，即分母為0锣杂。則可以看出氯窍， $\frac { 1 } { \| w\| }$ 對最終結(jié)果也沒有影響。
    3. 綜上所述蹲堂，我們可以從上面看出，忽略 $\frac { 1 } { \| w\| }$ 對感知機學(xué)習(xí)算法的執(zhí)行過程不會產(chǎn)生任何影響贝淤，反而還可以簡化運算柒竞，提高算法執(zhí)行效

第二步：如何讓損失函數(shù)最小化？

根據(jù)《統(tǒng)計學(xué)習(xí)方法》中介紹播聪，感知機學(xué)習(xí)算法是誤分類驅(qū)動的朽基，具體采用的方法是：隨機梯度下降（Stochastic Gradient Descent）；也就是先任意選取一個超平面和 ,然后利用梯度下降方法不斷地極小化目標(biāo)函數(shù)离陶；其中稼虎，極小化過程不是一次使中的所有誤分類點的梯度下降，而是一次隨機選取一個誤分類點使其梯度下降這是隨機梯度下降和標(biāo)準(zhǔn)的梯度下降之間的區(qū)別
- 說明：
  1. 隨機梯度下降和標(biāo)準(zhǔn)的梯度下降及批量梯度下降之間的區(qū)別招刨？
    - 標(biāo)準(zhǔn)梯度下降：
      1. 標(biāo)準(zhǔn)梯度是使用全部樣本計算梯度的霎俩，其計算代價比較高，但是在理論上沉眶，其下降速度是三種里面最快的打却，因為標(biāo)準(zhǔn)梯度是基于所有樣本，所以對于步長 $η$ 的取值谎倔，標(biāo)準(zhǔn)梯度下降的步長 $η$ 往往比隨機梯度和批量梯度下降的大柳击。
      2. 因為標(biāo)準(zhǔn)梯度是最小化所有訓(xùn)練樣本的損失函數(shù)，所以它的每一步都是全局最優(yōu)的下降方向片习，最終求解的是全局的最優(yōu)解捌肴，即求解的參數(shù)是使得風(fēng)險函數(shù)最小。
    - 隨機梯度下降：
      1. 隨機梯度使用單個樣本計算藕咏，計算代價比較低状知，由于下降方向彎彎繞繞，所以有一定可能性避開局部最優(yōu)侈离，但是下降速度也比較慢试幽，會迭代更多次。除此之外，如果誤差曲面有多個局部最小值（即 $w$ 有多個極小值）铺坞，隨機梯度下降可能避免陷入這些局部最小值起宽，原因還是在于隨機梯度下降采用單個樣本的誤差梯度來引導(dǎo)搜索，也就是說济榨，它有一定可能避開局部最優(yōu)坯沪，也有一定可能陷入局部最優(yōu)，究竟如何擒滑，還得等用代碼實現(xiàn)了才能知道腐晾；
      2. 另外，因為標(biāo)準(zhǔn)梯度下降的是使用準(zhǔn)確的梯度丐一，它可以理直氣壯地走藻糖，隨機梯度下降使用的是近似的梯度，就得小心翼翼地走库车，怕一不小心誤入歧途南轅北轍了巨柒；
      3. 雖然隨機梯度下降不是每次迭代得到的損失函數(shù)都向著全局最優(yōu)方向，但是大的整體的方向是向全局最優(yōu)解的柠衍，最終的結(jié)果往往是在全局最優(yōu)解附近洋满。
    - 批量梯度下降：
      1. 批量梯度介于兩者之間，每次使用部分樣本計算梯度珍坊。也就是說牺勾，批量的梯度下降就是一種折中的方法，他用了部分小樣本來近似全部的樣本阵漏。即：每次更新 $w$ 使用一批樣本驻民。
      2. 步長 $η$ 太小，收斂速度太慢袱饭；步長 $η$ 太大川无，會在最佳收斂點附近徘徊
      3. 不同問題的batch是不一樣的，nlp的paper訓(xùn)練部分batch一般就設(shè)置為10000虑乖，那么為什么是10000呢懦趋，我覺得這就和每一個問題中神經(jīng)網(wǎng)絡(luò)需要設(shè)置多少層，沒有一個人能夠準(zhǔn)確答出疹味，只能通過實驗結(jié)果來進行超參數(shù)的調(diào)整仅叫。（這一段摘自文章后面的博客）
  2. 最小二乘法與梯度下降法的異同：
    - 實現(xiàn)實現(xiàn)不同：最小二乘法是直接對參數(shù)求導(dǎo)找出全局最小，是非迭代法糙捺。而梯度下降法是一種迭代法诫咱，先給定一個 $β$ ，然后向參數(shù)下降最快的方向調(diào)整 $β$ 洪灯，在若干次迭代之后找到局部最小坎缭。
    - 梯度下降法的缺點：到最小點的時候收斂速度變慢，并且對初始點的選擇極為敏感，其改進大多是在這兩方面下功夫掏呼。
目前我們已經(jīng)知道了方法坏快，現(xiàn)在，我們先假設(shè)誤分類點集合M是固定的憎夷，那么整天的損失函數(shù) $L(w,b)$ 的梯度是：
$\begin{aligned} \nabla _ { w } L ( w , b ) & = - \sum _ { x _ { i } \in M } y _ { i } x _ { i } \\ \nabla _ { b } L ( w , b ) & = - \sum _ { x _ { i } \in M } y _ { i } \end{aligned}$
我們隨機選取一個誤分類點莽鸿，對 $w$ , $b$ 進行更新：
$\begin{aligned} w &\leftarrow w + \eta y _ { i } x _ { i } \\ b &\leftarrow b + \eta y _ { i } \end{aligned}$
因為整個感知機學(xué)習(xí)算法是收斂的，最終我們會得到一個最優(yōu)的參數(shù) $w$ 和 $b$ 拾给，而收斂的證明過程在《統(tǒng)計學(xué)習(xí)方法》中也有具體的證明過程祥得，這里不做收斂證明的展開，至此蒋得，第二步完結(jié)级及。

感知機學(xué)習(xí)算法的兩種形式

接下來我們講解的感知機學(xué)習(xí)算法一共有兩種，即原始形式和對偶形式

原始形式的算法：

輸入：訓(xùn)練數(shù)據(jù)集 $\mathrm { T } = \left\{ \left( x _ { 1 } , y _ { 1 } \right) , \left( x _ { 2 } , y _ { 2 } \right) , \dots , \left( x _ { N } , y _ { N } \right) \right\}$ 额衙，其中 $x _ { i } \in \mathcal { X } = R ^ { n }$ 创千， $y _ { i } \in y = \{ + 1 , - 1 \}$ ， $\mathrm { i } = 1,2 , \cdots , \mathrm { N }$ 入偷；學(xué)習(xí)率 $\eta$ （ $0<\eta<1$ ）；
輸出： $w$ 械哟， $b$ 疏之；感知機模型 $f ( x ) = \operatorname { sign } ( \omega x + b )$
學(xué)習(xí)過程：
1. 選取初值 $w_{0}$ ， $b_{0}$
2. 在訓(xùn)練集中選取數(shù)據(jù) $(x_{i},y_{i})$
3. 如果 $y _ { i } \left( \omega x _ { i } + b \right) \leq 0$ 暇咆，則
  $\begin{aligned} w &\leftarrow w + \eta y _ { i } x _ { i } \\ b &\leftarrow b + \eta y _ { i } \end{aligned}$
4. 轉(zhuǎn)至（2）锋爪，直至訓(xùn)練集中沒有誤分類點

對偶形式的引入

原始形式寫完，我們再來從幾個問題中著手展開講解感知機的對偶形式爸业！

什么是對偶形式呢其骄？
- 根據(jù)前面所講，我們知道單個誤分類點的是通過下面的兩個公式
  $\begin{aligned} w &\leftarrow w + \eta y _ { i } x _ { i } \\ b &\leftarrow b + \eta y _ { i } \end{aligned}$ 來更新參數(shù)w和b的扯旷；同時我們還知道拯爽，我們更新的方法是隨機梯度下降，也就是每次更新都是從誤分類點中隨機抽取一個來對參數(shù)進行更新钧忽；因此我們可以想象毯炮，在算法收斂找到最優(yōu)的參數(shù)w和b的這個參數(shù)更新的過程中，每個誤分類點都可能經(jīng)歷了很多次被抽取用來更新參數(shù) $w$ 和 $b$ 的過程耸黑，此時我們添加一個新的概念 $\eta_{i}$ 桃煎，其是用來指代誤分類樣本點 $x _ { i } y _ { i }$ 在參數(shù)更新過程中被抽取的次數(shù)
- 現(xiàn)在，我們了解了新的概念后大刊，我們再來看一下經(jīng)歷了全部的更新后所找到的最優(yōu)參數(shù)公式：
  
  此時为迈，我們再引入一個新的概念；
  - 說明：
    1. 這里的 $\alpha _ { i }$ 是《統(tǒng)計學(xué)習(xí)方法》中的寫法，我想李航老師的意思應(yīng)該是想簡化參數(shù)
    2. 整個算法的步長 $\eta$ 是固定的葫辐，而我之前在博客中有看過別的博主觀點是說步長是計算機根據(jù)需要選取的，并不是固定值纽乱，所以我自己對這里也不是很明白鸦列，希望以后能在代碼實現(xiàn)的過程中理解
- 此時薯嗤，我們根據(jù)新概念 $\alpha _ { i }$ 對我們之前的最終參數(shù)公式進行調(diào)整纤泵，如下：
  $\begin{aligned}w &= \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } x _ { i }\\b &= \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i }\end{aligned}$
為什么感知機要有對偶形式呢骆姐？
- 先給出一個結(jié)論：對偶形式是從不同的角度解答原問題的相似問題，也就是說對偶其實就是在原問題的基礎(chǔ)上進行的變形捏题；
- 感知機使用對偶形式可以加快計算速度：因為在對偶形式里玻褪，樣本點的特征向量是以內(nèi)積的形式存在于訓(xùn)練算法中的，因此公荧，如果我們事先算好訓(xùn)練集中實例間的內(nèi)積并儲存在矩陣?yán)锎洌簿褪荊ram矩陣，就可以在訓(xùn)練時大大快快算法的學(xué)習(xí)速度
- Gram矩陣：
  - $\mathrm { G } = \left[ x _ { i } \cdot x _ { j } \right] _ { N \times N }$
  - eg：我們有三個實例點 $x_{1},x_{2},x_{3}$ 循狰，則Gram矩陣為：
    $\left[ \begin{array} { l l l } { x _ { 1 } \cdot x _ { 1 } } & { x _ { 1 } \cdot x _ { 2 } } & { x _ { 1 } \cdot x _ { 3 } } \\ { x _ { 2 } \cdot x _ { 1 } } & { x _ { 2 } \cdot x _ { 2 } } & { x _ { 2 } \cdot x _ { 3 } } \\ { x _ { 3 } \cdot x _ { 1 } } & { x _ { 3 } \cdot x _ { 2 } } & { x _ { 3 } \cdot x _ { 3 } } \end{array} \right]$

對偶形式的算法：

輸入：訓(xùn)練數(shù)據(jù)集 $\mathrm { T } = \left\{ \left( x _ { 1 } , y _ { 1 } \right) , \left( x _ { 2 } , y _ { 2 } \right) , \dots , \left( x _ { N } , y _ { N } \right) \right\}$ 窟社，其中 $x _ { i } \in \mathcal { X } = R ^ { n }$ ， $y _ { i } \in y = \{ + 1 , - 1 \}$ 绪钥， $\mathrm { i } = 1,2 , \cdots , \mathrm { N }$ 灿里；學(xué)習(xí)率 $\eta$ （ $0<\eta<1$ ）；
輸出： $\alpha$ 程腹， $b$ 匣吊；感知機模型 $f ( x ) = \operatorname { sign } \left( \sum _ { j = 1 } ^ { N } a _ { j } y _ { j } x _ { j } \cdot x + b \right)$ 缀去，其中 $\alpha = \left( \alpha _ { 1 } , \alpha _ { 2 } , \cdots , \alpha _ { N } \right) ^ { T }$
學(xué)習(xí)過程：
1. 選取初值 $\alpha \leftarrow 0 , b \leftarrow 0$
2. 在訓(xùn)練集中選取數(shù)據(jù) $(x_{i},y_{i})$
3. 如果 $y _ { i } \left( \sum _ { j = 1 } ^ { N } a _ { j } y _ { j } x _ { j } \cdot x _ { i } + b \right) \leq 0$ 池户，則
  $\begin{aligned}\begin{array} { c } { \alpha _ { i } \leftarrow \alpha _ { i } + \eta } \\ { b \leftarrow b + \eta y _ { i } } \end{array} \end{aligned}$
4. 轉(zhuǎn)至（2）统倒，直至訓(xùn)練集中沒有誤分類點
說明：
- 判定誤分類的條件 $y _ { i } \left( \sum _ { j = 1 } ^ { N } a _ { j } y _ { j } x _ { j } \cdot x _ { i } + b \right) \leq 0$ 报亩，對照原始形式 $y _ { i } \left( \omega x _ { i } + b \right) \leq 0$ ，可能會很困惑為什么差別這么大掸哑，如果參考上面引入 $\alpha_{i}$ 的部分可以更進一步發(fā)現(xiàn)牵辣，其中 $\sum _ { j = 1 } ^ { N } a _ { j } y _ { j } x _ { j }$ 不應(yīng)該是最終更新得到的參數(shù) $w$ 嗎拐云？沒錯，的確是危彩，因為整個學(xué)習(xí)算法選用的是隨機梯度下降的方法，所以在進行選取誤分類點 $(x _ { j },y _ { j })$ 的過程中我們必須用當(dāng)前最終的參數(shù) $w$ 來進行判斷拼坎，所以才會有這樣的一個判定條件
- 看到 $\alpha _ { i } \leftarrow \alpha _ { i } + \eta , b \leftarrow b + \eta y _ { i }$ 的更新方式肯定也很奇怪壳鹤，為什么是這樣的更新形式？這是因為欧芽，我們的新參數(shù) $\eta_{i}$ 被李航老師用 $\alpha _ { i } = n _ { i } \eta$ 的方式蘊含到了 $\alpha _ { i }$ 里库正，從而我們沒能看到能代表更新式子的本質(zhì)是 $\eta_{i}$ ，其實我們只要想一下 $\eta_{i}$ 表示的是誤分類樣本點 $(x _ { j },y _ { j })$ 在參數(shù)更新過程中被抽取的次數(shù)趟大，我們就可以明白，每次我們選取一個誤分類點 $(x _ { j },y _ { j })$ 的時候，因為誤分類點的判定條件的符合岛蚤，這個 $(x _ { j },y _ { j })$ 又需要再用來對參數(shù)進行一次更新，所以更新式應(yīng)該是 $n _ { i } = n _ { i } + 1$ 铁坎，也因此，更新式被蘊含在 $\alpha _ { i } \leftarrow \alpha _ { i } + \eta = \left( n _ { i } + 1 \right) \eta$ 式子里

感知機的問題

根據(jù)我們先前的定義可以知道，感知機是基于數(shù)據(jù)集線性可分的前提下的可以尋找到一個超平面對數(shù)據(jù)進行分類的模型买羞，如下圖所示：

線性可分的情況

但是群叶，我們可以想一下舶衬，如果數(shù)據(jù)不可分怎么辦呢梁剔？

根據(jù)這個問題码撰，我們首先來看如果發(fā)生線性不可分究竟是什么樣的一種情況：

答：這個超平面會一直震蕩來震蕩去砾省，從而在達到迭代上限的時候停下

線性不可分的情況

現(xiàn)在狠鸳，我們知道這個問題引發(fā)的結(jié)果是什么了卸察，我們就需要考慮另一個問題，怎么解決？

答：Pocket算法
1. 這是根據(jù)在網(wǎng)上的博客了解到的跃巡，臺大的林軒田老師在講感知機算法時講解了一個Pocket改進算法，這是類似一種貪心選擇的算法抹镊，下面我們借用網(wǎng)上的一個博客內(nèi)容對這個改進算法做一個簡單的直觀理解
  - Pocket PLA（他們似乎把感知機學(xué)習(xí)算法稱為Naive PLA）遂黍，怎么理解呢？就好像我們在搜尋最佳分類直線的時候，隨機選擇錯誤點修正邪铲，修正后的直線放在口袋里英染，暫時作為最佳分類線狭握。然后如果還有錯誤點，繼續(xù)隨機選擇某個錯誤點修正，修正后的直線與口袋里的分類線比較澡谭，把分類錯誤點較少的分類線放入口袋杆兵。一直到迭代次數(shù)結(jié)束，這時候放在口袋里的一定是最佳分類線，雖然可能還有錯誤點存在受神，但已經(jīng)是最少的了格侯。
2. Pocket PLA缺點：
  - 如果數(shù)據(jù)一開始就是完全線性可分的鼻听，那么用這個算法所找出的解未必是最好的，并且時間花費也可能比較大联四。
  - 由于data是隨機選取的撑碴，迭代的次數(shù)也是人定的，很可能迭代完后所找到的解并不是最好的驮履。

邏輯斯諦回歸（Logistics Regression）

邏輯斯諦回歸是一個二分類的模型，簡稱LR，它是在線性回歸的基礎(chǔ)上使用了sigmoid函數(shù)评矩，將線性模型 $\omega ^ { T } x + b$ 的結(jié)果壓縮到了[0,1]之間，從而實現(xiàn)了將回歸問題轉(zhuǎn)化為了分類問題。

線性回歸和邏輯斯諦回歸

下面我們先借用吳恩達視頻中的一個例子來講解一下線性回歸解決不了的分類問題

例：下圖是一個乳腺癌分類的問題两疚，其中橫軸是腫瘤的大小，縱軸是我們的預(yù)測值√胨ǎ現(xiàn)在我們用線性回歸去擬合數(shù)據(jù)沟使，其中預(yù)測函數(shù)的閾值設(shè)置為0.5材诽，即大于等于0.5的預(yù)測為1滩援，表示是惡性腫瘤畔塔，小于0.5的預(yù)測為0，表示良性腫瘤瓤的。我們很幸運的可以發(fā)現(xiàn)今膊，這條直線擬合的很好频敛，剛好所有的樣本點都能夠分類正確

線性回歸1

接下來，我們再進一步，假設(shè)現(xiàn)在訓(xùn)練集中突然來了一個尺寸非常大的惡性腫瘤，這個樣本點將使得我們原先擬合的直線發(fā)生變化缤骨，如下

線性回歸2

現(xiàn)在爱咬，我們發(fā)現(xiàn)閾值0.5對應(yīng)的結(jié)點發(fā)生了變化，從原先的酒紅色的結(jié)點向右移動到了藍(lán)色結(jié)點绊起，此時我們可以發(fā)現(xiàn)精拟，這條直線的預(yù)測并不像原先那么好了，它讓兩個原先預(yù)測為1的樣本點突然被預(yù)測為了0虱歪，就是上面4個紅叉的左邊兩個

邏輯斯諦回歸模型

鑒于上面的例子蜂绎，我們可以發(fā)現(xiàn)，線性回歸對于分類問題是具有很差的預(yù)測效果的笋鄙，因此师枣，我們在原先的線性回歸的問題上引入sigmoid函數(shù)，也就是將原先的預(yù)測值 $\omega ^ { T } x + b$ 作為自變量填充到了sigmoid函數(shù)在萧落，如下圖黑色曲線：

單位階躍函數(shù)與對數(shù)幾率函數(shù)

說明：

圖源自周志華老師的《機器學(xué)習(xí)》践美，其中紅色線部分是單位階躍函數(shù)，公式是圖上紅色字體部分找岖，黑色曲線是sigmoid函數(shù)陨倡，借用這個圖的原因是想說明我們不選用單位階躍函數(shù)的原因是因為其不連續(xù)，相對的sigmoid函數(shù)是極好的许布，連續(xù)可導(dǎo)的
我們剛才說LR模型是在線性回歸的基礎(chǔ)上加了sigmoid函數(shù)兴革，也就是將原先的預(yù)測值 $\omega ^ { T } x + b$ 作為自變量 $z$ 填充到了sigmoid函數(shù)里，所以我們得到了如下公式
$y = \frac { 1 } { 1 + e ^ { - \left( \boldsymbol { w } ^ { \mathrm { T } } \boldsymbol { x } + b \right) } }$

此時蜜唾，我們需要引入一些新的概念：我們把一個事件的幾率（odds）指代為該事件發(fā)生的概率與該事件不發(fā)生的概率比值杂曲；如果事件發(fā)生的概率是 $p$ ，那么該事件的幾率是 $\frac { p } { 1 - p }$ 袁余，該事件的對數(shù)幾率（log odds）是
$\operatorname { logit } ( p ) = \log \frac { p } { 1 - p }$

注：對數(shù)幾率也可以成為是logit函數(shù)解阅，對此，其實我們可以不用被它怪異的名稱嚇到泌霍，它就是某事件發(fā)生概率與不發(fā)生概率比值的對數(shù)形式而已

為了建立起上面兩個式子的聯(lián)系货抄，我們將 $y$ 視為樣本 $x$ 作為正例的可能性，也就是 $p$ 朱转， $1-y$ 視為樣本 $x$ 作為反例的可能性蟹地，也就是 $1-p$ ，所以我們可以通過 $y = \frac { 1 } { 1 + e ^ { - \left( \omega ^ { T } x + b \right) } }$ 變化為如下形式：
$\ln \frac { y } { 1 - y } = w ^ { \mathrm { T } } x + b$
此時藤为，為了方便怪与，我們再把權(quán)值向量 $w$ 和輸入向量 $x$ 進行擴充，即 $\widehat { \omega } = \left( \omega _ { 1 } ; \omega _ { 2 } ; \cdots ; \omega _ { n } ; b \right) ^ { T }$ 缅疟， $X=\left( x _ { 1 } ; x _ { 2 } ; \cdots ; x _ { d } ; 1 \right) ^ { T }$ 分别，這時遍愿，上式又可以變化為如下形式
$\log \frac { y } { 1 - y } = \widehat { w } \cdot X$

接下來，我們 $y$ 視為后驗概率估計 $p ( y = 1 | x )$ 耘斩，則得到
$\log \frac { P ( y = 1 | x ) } { 1 - P ( y = 1 | x ) } = \widehat { w } \cdot X$

由上式沼填，再加上 $\mathrm { p } ( y = 1 | x ) + \mathrm { p } ( y = 0 | x ) = 1$ ，我們終于可以得到邏輯斯諦回歸模型的公式了括授，即：
$\begin{aligned} P ( y = 1 | x ) & = \frac { e ^ { ( \hat { w } \cdot X ) } } { 1 + e ^ { ( \hat { w } \cdot X ) } } \\ P ( y = 0 | x ) & = \frac { 1 } { 1 + e ^ { ( \hat { w } \cdot X ) } } \end{aligned}$

參數(shù)估計

對于邏輯斯諦回歸模型坞笙，我們一般采用極大似然估計去對參數(shù)進行估計，接下來荚虚，我們開始進行極大似然估計對我們的參數(shù)進行估計

根據(jù)極大似然估計的常規(guī)步驟薛夜，我們需要寫出似然函數(shù)，因此版述，我們先設(shè)
$P ( Y = 1 | x ) = \pi ( x ) , \quad P ( Y = 0 | x ) = 1 - \pi ( x )$

則梯澜，似然函數(shù)為
$\prod _ { i = 1 } ^ { N } \left[ \pi \left( x _ { i } \right) \right] ^ { y _ { i } } \left[ 1 - \pi \left( x _ { i } \right) \right]^{1-y_{ i }}$

進而，其對數(shù)似然函數(shù)為
$\begin{aligned} L ( \widehat { w } ) & = \sum _ { i = 1 } ^ { N } \left[ y _ { i } \log \pi \left( x _ { i } \right) + \left( 1 - y _ { i } \right) \log \left( 1 - \pi \left( x _ { i } \right) \right) \right] \\ & = \sum _ { i = 1 } ^ { N } \left[ y _ { i } \log \frac { \pi \left( x _ { i } \right) } { 1 - \pi \left( x _ { i } \right) } + \log \left( 1 - \pi \left( x _ { i } \right) \right) \right] \\ & = \sum _ { i = 1 } ^ { N } \left[ y _ { i } \left( \widehat { w } \cdot x _ { i } \right) - \log \left( 1 + e ^ { \left( \widehat { w } \cdot x _ { i } \right) } \right] \right. \end{aligned}$
最后渴析，我們令 $L ( \widehat { w } )$ 為0晚伙，求極大值，進而就可以得到 $\widehat { w }$ 的估計值

說明：

可能我們對似然函數(shù)感覺很奇怪檬某，但學(xué)過《概率論與數(shù)理統(tǒng)計》的同學(xué)應(yīng)該都是了解的撬腾，而需要指出的是螟蝙，這個似然函數(shù)就是我們的損失函數(shù)
當(dāng)然恢恼，對于LR模型的參數(shù)估計并非只有極大似然估計一種方法，在吳恩達的視頻中就是用梯度下降的方法去對似然函數(shù)進行參數(shù)估計的胰默，但鑒于感知機部分里梯度下降已經(jīng)講了許多场斑，我們這里不再過多展開。

我們假設(shè)極大似然估計得到的估計值是 $\widehat { \omega } ^ { * }$ 牵署，則學(xué)習(xí)到的邏輯斯諦回歸模型為
$\begin{aligned}P ( y = 1 | x ) = \frac { \exp \left( \hat { w } ^ { * } \cdot x \right) } { 1 + \exp \left( \hat { w } ^ { * } \cdot x \right) }\\P ( y = 0 | x ) = \frac { 1 } { 1 + \exp \left( \hat { w } ^ { * } \cdot x \right) }\end{aligned}$

邏輯斯諦回歸這部分總體來說總結(jié)得還是太過簡單漏隐，主要目前是在不想花太多精力在這個模型上面，畢竟時間和精力都是有限的奴迅，所以希望自己以后在第二個階段模型實現(xiàn)的過程中能夠為這些坑慢慢填上吧青责！

參考資料：
[1]：最小二乘法小結(jié)
[2]：機器學(xué)習(xí)中的矩陣求導(dǎo)的一點總結(jié)（三種方法求線性回歸最佳參數(shù)）
[3]：感知機中損失函數(shù)1/||w||為什么可以不考慮（或直接忽略）？
[4]：梯度下降的三種形式BGD取具、SGD以及MBGD
[5]：隨機梯度下降（Stochastic gradient descent）和批量梯度下降（Batch gradient descent ）的公式對比脖隶、實現(xiàn)對比
[6]：PLA算法（感知機）
[7]：《機器學(xué)習(xí)》周志華
[8]：《統(tǒng)計學(xué)習(xí)方法》李航
[9]：《機器學(xué)習(xí)》（視頻）吳恩達

最后編輯于：2019.01.20 16:04:10

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市暇检，隨后出現(xiàn)的幾起案子产阱，更是在濱河造成了極大的恐慌，老刑警劉巖块仆，帶你破解...
沈念sama閱讀 206,723評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件构蹬，死亡現(xiàn)場離奇詭異王暗，居然都是意外死亡，警方通過查閱死者的電腦和手機庄敛，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,485評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門俗壹，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人铐姚，你說我怎么就攤上這事策肝。” “怎么了隐绵？”我有些...
開封第一講書人閱讀 152,998評論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵之众，是天一觀的道長。經(jīng)常有香客問我依许，道長棺禾，這世上最難降的妖魔是什么峭跳？我笑而不...
開封第一講書人閱讀 55,323評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮悬襟，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘脊岳。我一直安慰自己垛玻，他們只是感情好割捅，可當(dāng)我...
茶點故事閱讀 64,355評論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布帚桩。她就那樣靜靜地躺著账嚎，像睡著了一般郭蕉。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上檩小，一...
開封第一講書人閱讀 49,079評論 1贊 285
城市分裂傳說
那天筐付，我揣著相機與錄音瓦戚，去河邊找鬼较解。笑死印衔，一個胖子當(dāng)著我的面吹牛奸焙，可吹牛的內(nèi)容都是我干的与帆。我是一名探鬼主播墨榄，決...
沈念sama閱讀 38,389評論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼阵翎，長吁一口氣：“原來是場噩夢啊……” “哼贮喧！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起雇庙，我...
開封第一講書人閱讀 37,019評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤疆前，失蹤者是張志新（化名）和其女友劉穎竹椒，沒想到半個月后胸完，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體赊窥，經(jīng)...
沈念sama閱讀 43,519評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡扯再，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 35,971評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年熄阻，在試婚紗的時候發(fā)現(xiàn)自己被綠了饺律。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片复濒。...
茶點故事閱讀 38,100評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖砸泛，靈堂內(nèi)的尸體忽然破棺而出唇礁，到底是詐尸還是另有隱情盏筐，我是刑警寧澤琢融，帶...
沈念sama閱讀 33,738評論 4贊 324
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站纳令，受9級特大地震影響平绩，放射性物質(zhì)發(fā)生泄漏馒过。R本人自食惡果不足惜腹忽，卻給世界環(huán)境...
茶點故事閱讀 39,293評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一窘奏、第九天我趴在偏房一處隱蔽的房頂上張望着裹。院中可真熱鬧骇扇，春花似錦少孝、人聲如沸稍走。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,289評論 0贊 19
一樁弒父案焙压，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽冗恨。三九已至，卻和暖如春心俗，著一層夾襖步出監(jiān)牢的瞬間城榛，已是汗流浹背狠持。一陣腳步聲響...
開封第一講書人閱讀 31,517評論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工甜刻，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留得院，地道東北人祥绞。一個月前我還...
沈念sama閱讀 45,547評論 2贊 354
代替公主和親
正文我出身青樓蜕径，卻偏偏與公主長得像，于是被迫代替她去往敵國和親虹统。傳聞我的和親對象是個殘疾皇子车荔，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 42,834評論 2贊 345

線性模型（線性回歸乖杠、感知機和邏輯斯諦回歸）