模式識(shí)別課程(四)-線性分類器/線性判別函數(shù)

本筆記是筆者課程學(xué)習(xí)中所做筆記(絕對(duì)原創(chuàng))，轉(zhuǎn)載請(qǐng)聯(lián)系作者
有問(wèn)題歡迎在交流區(qū)探討學(xué)習(xí)，QQ：761322725
碼字不易哩簿，好心人隨手點(diǎn)個(gè)贊??
前文包括貝葉斯決策，參數(shù)估計(jì)

概念回顧

模式分類的目的： 設(shè)法在特征空間中找到兩類/多類之間的分界面兽叮。

生成模型

隨機(jī)模式
從一定的概率模型出發(fā)累盗，把**模式識(shí)別問(wèn)題轉(zhuǎn)化成概率模型估
計(jì)問(wèn)題 **，如蟆淀，條件概率密度估計(jì)
分類器設(shè)計(jì)實(shí)是對(duì)概率模型的估計(jì)拯啦。
又稱為基于(概率)模型的模式識(shí)別方法。

判別模型

確定性簡(jiǎn)單模式
從要解決的問(wèn)題和訓(xùn)練樣本出發(fā)熔任，直接求出判別函數(shù)褒链。
有些方法可事先確定判別函數(shù)的形式，通過(guò)訓(xùn)練樣本確定其中的參數(shù)疑苔。如：SVM 甫匹，神經(jīng)網(wǎng)絡(luò)
也稱為基于數(shù)據(jù)的模式識(shí)別方法(或統(tǒng)計(jì)模式識(shí)別的幾何方法)

線性判別函數(shù)

基于樣本直接設(shè)計(jì)分類器的三個(gè)基本要素

確定分類器即判別函數(shù)的類型
確定分類器設(shè)計(jì)的目標(biāo)或準(zhǔn)則
設(shè)計(jì)算法利用樣本數(shù)據(jù)尋找最優(yōu)的函數(shù)參數(shù)
形式化定義：
在判別函數(shù)集 $\{g(\theta),\theta \in \Theta \}$ 中，確定待定參數(shù) $\theta ^{*}$ 惦费，使得目標(biāo)函數(shù) $L(\theta)$ 最小/大：
$L(\theta ^{*})=\underset{\theta}{min}L(\theta)$

判別函數(shù)的定義

直接用來(lái)對(duì)樣本進(jìn)行分類判決的函數(shù)
若兩類樣本可以用一個(gè)方程 $g(x)=0$ 來(lái)劃分兵迅，則 $g(x)$ 為判別函數(shù)/決策函數(shù)/判決函數(shù)， $g(x)=0$ 為決策面

如上圖：

一般形式

線性判別函數(shù)由輸入向量x的各分量的線性組合構(gòu)成
矩陣形式表示為： $g(X)=W^TX+W_0$ , $W_0$ 稱為偏置
$X=\begin{bmatrix} x_1\\ x_2\\ ...\\ x_d \end{bmatrix},W=\begin{bmatrix} W_1\\ W_2\\ ...\\ W_d \end{bmatrix}$
如果將偏置項(xiàng)也整合到矩陣中的話薪贫，可以表示為： $g(X)=W^T$ 恍箭，稱為增廣表示形式
$X=\begin{bmatrix} 1\\ x_1\\ x_2\\ ...\\ x_d \end{bmatrix},W=\begin{bmatrix} W_0\\ W_1\\ W_2\\ ...\\ W_d \end{bmatrix}$
關(guān)于判別函數(shù)存在以下兩種情況

針對(duì)二分類問(wèn)題，即類別有2個(gè)

如上圖瞧省，對(duì)于d維數(shù)據(jù)扯夭， $d-1$ 維的超平面把 $d$ 維輸入空間中歸為 $w_1$ 的點(diǎn)與歸為 $w_2$ 的點(diǎn)分開(kāi)。
權(quán)向量的性質(zhì)： $W$ 和決策面正交臀突，確定了決策面的方向勉抓。

對(duì)任一點(diǎn)X及其在決策面上的投影 $X_{\perp}$ ，有:
$X=X_{\perp}+r\frac{W}{||W||}$ , $g(X)=W^TX+W_0$ ,
且 $g(X_{\perp})=W^TX_{\perp}+W_0$
將X代入函數(shù)式中：
$g(X)=W^T(X_{\perp}+r\frac{W}{||W||})+W_0$
$=W^TX_{\perp}+r\frac{W^TW}{||W||}+W_0$
$=r||W||$
$r=\frac{g(x)}{||W||}$
其中 $r$ 是 $X$ 到?jīng)Q策面的垂直距離候学， $\frac{W}{||W||}$ 是 $W$ 方向上的單位向量藕筋。
任一點(diǎn)到?jīng)Q策面的垂直距離維 $r=\frac{g(x)}{||W||}$
$\color{red}{g(x)給出了點(diǎn)到判別面的距離的度量}$
原點(diǎn)到?jīng)Q策面的垂直距離為 $-\frac{W_0}{||W||}$
$\color{red}{w_0決定了判別面的位置}$
多類問(wèn)題
給定c(c>2)個(gè)類別的樣本集合，三種劃分方式：

$\color{red}{1對(duì)其他 (one-versus-the-rest)}$ ,轉(zhuǎn)化為c個(gè)兩分類問(wèn)題

存在不能確定區(qū)域
$\color{red}{1對(duì)1 (one-versus-one)}$ 梳码，c(c-1)/2個(gè)二元判別函數(shù)
c類判別函數(shù)

廣義線性判別函數(shù)

線性判別函數(shù) $g(X)=W_0+\sum_{i=1}^dw_ix_i$ ：加入更高次的項(xiàng)隐圾，得到多項(xiàng)式判別函數(shù)： $g(x)=\sum_{i=1}^{\hatqbquqiv}w_iy_i(X),g(X)=W^Ty$
$y=\sum w_{ij}x_ix_j$
$y_i(X)$ 將d維空間上的點(diǎn)映射到 $\hat8ememnd$ 維的y空間上的點(diǎn)，
導(dǎo)致維度災(zāi)難： $\hatcdjp1mb>d$ 掰茶，即向高維空間映射暇藏，
相應(yīng)補(bǔ)救措施：強(qiáng)制加入大的 margin( 或訓(xùn)練樣本之間的“間隔等措施，如支持向量機(jī)濒蒋。這樣處理基于假設(shè) ：映射到高維空間并不給數(shù)據(jù)附加任何錯(cuò)誤的結(jié)構(gòu)及相關(guān)性）

Fisher線性判別分析

1936年R.A.Fisher提出線性判別分析(Linear Discriminant Analysis,LDA),從降低維度的角度考察線性分類模型盐碱。

目標(biāo)：尋找有利于分類的投影方向.通過(guò)調(diào)整權(quán)向量w 把兔，我們可以選擇讓類別之間分開(kāi)最大的一個(gè)投影。
對(duì)于二分類問(wèn)題瓮顽，其思想是選擇投影方向县好，使投影后兩類相隔盡可能遠(yuǎn)，而同時(shí)每一類內(nèi)部的樣本又盡可能聚集暖混。
在原樣本空間中(二分類)缕贡，兩類的類均值向量：

$m_2=\frac{1}{n_2}\sum_{X_i \in D_2}X_i$
當(dāng)使用權(quán)重向量 $W$ 投影時(shí)， $類間分離程度$ 的最簡(jiǎn)單度量方式是 $類均值投影之后的距離$
$\widetilde{m_1}-\widetilde{m_2}=W^T(m_1-m_2)$ ,最大化該距離即可
$\widetilde{m_k}=\sum_{X_i \in D_i}W^TX_i$ 表示投影后的類均值向量拣播，
均值投影的問(wèn)題在于沒(méi)有考慮類內(nèi)的數(shù)據(jù)離散度
Fisher提出：通過(guò)最大化一個(gè)函數(shù)晾咪，使投影后的類間分離性最大，同時(shí)又能使每類的類內(nèi)分離性較小贮配。
投影后的類內(nèi)離散度(使用方差表示)如下：
$\widetilde{s_k^2}=\sum_{X_i \in D_k}(W^TX_i-\widetilde{m_k})$
類內(nèi)的總離散度是 $\widetilde{s_1^2}+\widetilde{s_2^2}$
$\color{red}{Fisher 準(zhǔn)則函數(shù) 定義為類間離散度與類內(nèi)離散度之比谍倦。}$
$J_F(W)=\frac{(\widetilde{m_1}-\widetilde{m_2})^2}{\widetilde{s_1^2}+\widetilde{s_2^2}}$
將公式轉(zhuǎn)換成為原空間的表示
$J_F(W)=\frac{W^TS_BW}{W^TS_WW}$
$S_B=(m_2-m_1)(m_2-m_1)^T$ 表示原空間類間離散度矩陣
$S_W=\sum_{i=1}^2\sum_{X\in D_i}(X-m_i)(X-m_i)^T$ 表示原空間類內(nèi)離散度矩陣
$W^*=\underset{W}{argmax}J_F(W)=S_W^{-1}(m_2-m_1)$
對(duì)于準(zhǔn)則函數(shù) $J_F(W)$ 求其最大值，對(duì)W求導(dǎo)并令其等于0：

相應(yīng)判別函數(shù)為：
若

練習(xí)

利用Fisher判別解決二分類

感知機(jī)算法

Rosenblatt于1962年提出牧嫉，是一個(gè)二分類的線性模型剂跟，輸入特征向量X，輸出類別[t],分別為+1和-1
$y(X)=f(W^T\phi(X))$
非線性激活函數(shù)f()： $f(a)=\left\{\begin{matrix} +1,a\geqslant 0\\ -1,a<0 \end{matrix}\right.$

某錯(cuò)分樣本對(duì)誤差函數(shù)的貢獻(xiàn)是
w 的線性函數(shù)酣藻，而對(duì)于正確分類的樣本曹洽，誤差函數(shù)等于零。總的誤差函數(shù)是分段線性的辽剧。
對(duì)于該誤差函數(shù)使用隨機(jī)梯度下降法進(jìn)行迭代更新：權(quán)向量的迭代公式為：

感知機(jī)算法的可收斂性：

感知機(jī)準(zhǔn)則總結(jié)

優(yōu)點(diǎn)：簡(jiǎn)單送淆、便于實(shí)現(xiàn)
缺點(diǎn)：結(jié)果不唯一，在線性不可分的情況下不收斂
然而感知機(jī)算法是神經(jīng)網(wǎng)絡(luò)怕轿，深度學(xué)習(xí)發(fā)展的基礎(chǔ)偷崩。

總結(jié)

本篇筆記記錄了線性分類器的基本知識(shí)，主要介紹了Fisher和感知機(jī)法則撞羽，兩個(gè)算法思路簡(jiǎn)單清晰阐斜，實(shí)現(xiàn)起來(lái)也比較容易，是后續(xù)復(fù)雜算法的基礎(chǔ)诀紊。對(duì)于線性判別函數(shù)谒出，需要掌握其基本的形式和構(gòu)建思想即可。

最后編輯于：2019.11.09 20:51:50

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

人面猴
序言：七十年代末邻奠，一起剝皮案震驚了整個(gè)濱河市笤喳，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌碌宴，老刑警劉巖杀狡，帶你破解...
沈念sama閱讀 217,277評(píng)論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異贰镣，居然都是意外死亡呜象，警方通過(guò)查閱死者的電腦和手機(jī)膳凝，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,689評(píng)論 3贊 393
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)恭陡，“玉大人鸠项，你說(shuō)我怎么就攤上這事∽咏” “怎么了？”我有些...
開(kāi)封第一講書人閱讀 163,624評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵楼入，是天一觀的道長(zhǎng)哥捕。經(jīng)常有香客問(wèn)我，道長(zhǎng)嘉熊，這世上最難降的妖魔是什么遥赚？我笑而不...
開(kāi)封第一講書人閱讀 58,356評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮阐肤，結(jié)果婚禮上凫佛，老公的妹妹穿的比我還像新娘。我一直安慰自己孕惜，他們只是感情好愧薛，可當(dāng)我...
茶點(diǎn)故事閱讀 67,402評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著衫画，像睡著了一般毫炉。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上削罩，一...
開(kāi)封第一講書人閱讀 51,292評(píng)論 1贊 301
城市分裂傳說(shuō)
那天瞄勾，我揣著相機(jī)與錄音，去河邊找鬼弥激。笑死进陡，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的微服。我是一名探鬼主播趾疚，決...
沈念sama閱讀 40,135評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼职辨！你這毒婦竟也來(lái)了盗蟆？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書人閱讀 38,992評(píng)論 0贊 275
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤舒裤，失蹤者是張志新（化名）和其女友劉穎喳资，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體腾供，經(jīng)...
沈念sama閱讀 45,429評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡仆邓，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,636評(píng)論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年鲜滩，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片节值。...
茶點(diǎn)故事閱讀 39,785評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡徙硅，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出搞疗，到底是詐尸還是另有隱情嗓蘑，我是刑警寧澤，帶...
沈念sama閱讀 35,492評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布匿乃，位于F島的核電站桩皿，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏幢炸。R本人自食惡果不足惜泄隔，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,092評(píng)論 3贊 328
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望宛徊。院中可真熱鬧佛嬉，春花似錦、人聲如沸闸天。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 31,723評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)苞氮。三九已至缰揪，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間葱淳，已是汗流浹背钝腺。一陣腳步聲響...
開(kāi)封第一講書人閱讀 32,858評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留赞厕，地道東北人艳狐。一個(gè)月前我還...
沈念sama閱讀 47,891評(píng)論 2贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像皿桑，于是被迫代替她去往敵國(guó)和親毫目。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,713評(píng)論 2贊 354

模式識(shí)別課程(四)-線性分類器/線性判別函數(shù)

模式識(shí)別課程(四)-線性分類器/線性判別函數(shù)

目錄

前言

概念回顧

生成模型

判別模型

線性判別函數(shù)

判別函數(shù)的定義

一般形式

廣義線性判別函數(shù)

Fisher線性判別分析

練習(xí)

感知機(jī)算法

感知機(jī)準(zhǔn)則總結(jié)

總結(jié)

推薦閱讀更多精彩內(nèi)容