線性判別函數(shù)

1、關(guān)于線性判別函數(shù)第一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.1 引言問(wèn)題的提出 線性決策面是較簡(jiǎn)單的，易于實(shí)現(xiàn)，因此本章主要討論線性分類器。第二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.1 引言判別函數(shù)形式第三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.1 引言兩類情況決定分類界面的方向， 決定分類界面的位置第四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.1 引言線性分類器的設(shè)計(jì)步驟 （1）有一已知類別的樣本集H （2）確定一準(zhǔn)則函數(shù) （3）利用最優(yōu)化技術(shù)求出準(zhǔn)則函數(shù)極值解 第五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.1 引言與最優(yōu)分類器的關(guān)系 貝葉斯分類器是在錯(cuò)誤率或風(fēng)險(xiǎn)

2、下為最優(yōu)的分類器。線性分類器針對(duì)錯(cuò)誤率或風(fēng)險(xiǎn)是“次優(yōu)”的。但對(duì)于所采用的準(zhǔn)則函數(shù) 則是最優(yōu)的。線性可分性 已知一樣本集，如果有一個(gè)線性分類器能把每個(gè)樣本正確分類，則稱這組樣本集為線性可分的，否則稱為線性不可分的。反之，如果樣本集是線性可分的，則必然存在一個(gè)線性分類器能把每個(gè)樣本正確分類。第六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別R. A. Fisher爵士,1890.2.17-1962.7.29,英國(guó)現(xiàn)代統(tǒng)計(jì)學(xué)與現(xiàn)代演化論的奠基者之一劍橋大學(xué)岡維爾與凱斯學(xué)院宴會(huì)廳里的染色玻璃窗，上方的彩繪方格用以紀(jì)念拉丁方陣，下方的白色文字則是紀(jì)念羅納德費(fèi)雪。 由1936年的經(jīng)

3、典論文開(kāi)始最早研究線性判別函數(shù)，發(fā)明了最大似然估計(jì)方法。其著作有研究者用的統(tǒng)計(jì)方法 統(tǒng)計(jì)方法和科學(xué)推理 近交的理論 試驗(yàn)設(shè)計(jì) 自然選擇的遺傳理論 根據(jù)孟德?tīng)栠z傳方式的親屬 間的相關(guān) 第七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類） 問(wèn)題的提出 在低維空間中行得通的方法在高維空間里往往失效，因此需要降低空間維數(shù)。 基本原理將高維空間數(shù)據(jù)向某一直線上投影，如何確定該直線在特征空間中的最佳方向？Fisher法即尋找最佳的投影方向 ，使投影后樣本最佳可分第八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）投影的表示0投影示意圖第九張，PP

4、T共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）基本參量定義（d維x空間） （1）各類樣本均值向量 （2）樣本類內(nèi)離散度矩陣 和總類內(nèi)離散度矩陣 （3）樣本類間離散度矩陣對(duì)稱半正定陣，當(dāng)Nd時(shí)通常非奇異對(duì)稱半正定陣第十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）補(bǔ)充定義正定二次型設(shè)有實(shí)二次型 ，若對(duì)任意向量X都有f0，則稱矩陣A為正定矩陣；若f0，則稱A為負(fù)定矩陣；若f0 ，則稱A為半正定矩陣。補(bǔ)充定義非奇異陣當(dāng)|A|=0時(shí)，方陣A為奇異陣；|A| 0時(shí)，方陣A為非奇異陣。方陣A可逆的充要條件是|A| 0?？赡骊囈喾Q非退化陣或非奇異陣或滿

5、秩陣不可逆的方陣也稱退化陣或奇異陣或降秩陣第十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）基本參量定義（一維y空間） （1）各類樣本均值向量 （2）樣本類內(nèi)離散度矩陣 和總類內(nèi)離散度矩陣 第十二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）定義Fisher準(zhǔn)則函數(shù)原則：各類樣本盡可能分開(kāi)，類內(nèi)樣本盡量密集，需求令準(zhǔn)則函數(shù)極大的 。第十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）準(zhǔn)則函數(shù)的顯式化求令準(zhǔn)則函數(shù)極大的第十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類

6、）求令準(zhǔn)則函數(shù)極大的要求的是方向，常量系數(shù)可去除第十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）概念補(bǔ)充二次型對(duì)向量求導(dǎo)第十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）投影過(guò)程一維閾值的選取 （1）當(dāng)維數(shù)與樣本數(shù)都很大時(shí)，可用貝葉斯分類器 （2）依據(jù)先驗(yàn)知識(shí)選擇第十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.2 Fisher線性判別（兩類）Fisher線性判別步驟 （1）求兩類樣本均值向量 （2）求兩類樣本類內(nèi)離散度矩陣 （3）求總類內(nèi)離散度矩陣 （4）求向量 （5）求出兩類樣本在 上的投影點(diǎn) （6）求各類在投影空間的

7、均值 （7）選取閾值 （8）對(duì)于未知樣本，計(jì)算其在 上的投影點(diǎn)y （9）根據(jù)決策規(guī)則分類第十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）問(wèn)題的提出 20世紀(jì)50年代由Rosenblatt提出，用于腦模型感知器，故稱為感知準(zhǔn)則函數(shù)。該模型未獲成功，主要由于無(wú)法解決非線性問(wèn)題，但其思想可沿用。 第十九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）基本思想 分類器形式已定，只要估計(jì)出權(quán)值向量即完成分類器設(shè)計(jì)。感知器采用迭代的方法，是一種典型的賞罰過(guò)程，對(duì)正確分類的模式則“賞”，這里即“不罰”，權(quán)向量不變。對(duì)錯(cuò)誤分類的模式則“罰”，即修正權(quán)向量。第二十張

8、，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）樣本及權(quán)向量的增廣 第二十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）樣本的規(guī)范化 如果樣本集是線性可分的，必然存在某個(gè)權(quán)向量可使第二十二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）感知準(zhǔn)則函數(shù)的構(gòu)造感知器（perceptron)對(duì)被錯(cuò)分樣本的處理準(zhǔn)則函數(shù)為0時(shí)無(wú)錯(cuò)分優(yōu)化目標(biāo)：令準(zhǔn)則函數(shù)極小，采用梯度下降法第二十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）感知準(zhǔn)則函數(shù)的梯度下降求解 尋求最優(yōu)的a令J極小迭代方式尋找極小值思想：由某一初值開(kāi)始，沿某一方向，

9、按某一步長(zhǎng)搜尋極小值，由于梯度是函數(shù)值增長(zhǎng)最快的方向，沿負(fù)梯度即為函數(shù)下降最快的方向，沿此方向可最快到達(dá)極小點(diǎn)，故稱梯度下降法。第二十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）純量對(duì)向量求導(dǎo)補(bǔ)充定義：純量對(duì)向量求導(dǎo)負(fù)負(fù)為正第二十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）感知準(zhǔn)則函數(shù)梯度下降法步驟收斂，結(jié)束第二十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）步驟描述 （1）給定初始權(quán)向量a(1)和步長(zhǎng) （2）找出被權(quán)向量a(k)錯(cuò)分的所有樣本，轉(zhuǎn)（3）；如 無(wú)錯(cuò)分樣本，算法結(jié)束。 （3）按迭代公式求新的權(quán)向量a(k+

10、1)，轉(zhuǎn)（2）第二十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）例：已知兩類樣本，以感知器算法求解分類器（求判別函數(shù)）第二十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）解：寫(xiě)出規(guī)范化增廣樣本向量第二十九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）第三十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）批處理把所有錯(cuò)分類樣本一次性找出來(lái)修正與人的學(xué)習(xí)方式不同，人采用“單樣本修正”方式單樣本修正找出一個(gè)錯(cuò)分樣本即進(jìn)行修正第三十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）按單樣本修

11、正法重作例題固定增量法第三十二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）迭代方法要從理論上證明收斂，此處僅以圖形方式說(shuō)明修正前錯(cuò)分類修正后正確分類第三十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）結(jié)論：可以證明，采用梯度下降法對(duì)于線性可分的樣本集，經(jīng)過(guò)有限步修正，一定能找到一個(gè)使準(zhǔn)則函數(shù)達(dá)到極小值的權(quán)向量a，即算法在有限步內(nèi)收斂，其收斂速度取決于初始權(quán)向量和步長(zhǎng)。分類界面接近最終位置時(shí)，步長(zhǎng)需選得較小，否則修正過(guò)頭。但如各步步長(zhǎng)都選得很小，收斂速度變慢。為此，采用變步長(zhǎng)方案。對(duì)于線性不可分情況，算法不收斂。第三十四張，PPT共六十四頁(yè)，創(chuàng)作于

12、2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）單樣本修正與批處理的比較：（1）學(xué)習(xí)開(kāi)始時(shí)不能得到所有的訓(xùn)練樣本，必須使用在線方法。（2）訓(xùn)練樣本數(shù)很大時(shí)，單樣本方便，比批處理有效，因?yàn)榕幚硇枰郊佑洃泚?lái)積累局部更新。（3）單樣本引入一些隨機(jī)噪聲，有助于逃離局部極小值。批處理引入一些平均濾波。（4）單樣本適合大規(guī)模分類問(wèn)題，因?yàn)楹芏嘤?xùn)練樣本含有冗余信息，對(duì)梯度貢獻(xiàn)類似，更新權(quán)值前計(jì)算所有樣本浪費(fèi)。第三十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.3感知準(zhǔn)則函數(shù)（兩類）單樣本修正與批處理的比較：（5）批處理對(duì)梯度矢量估計(jì)較好，避免了權(quán)值變化相互影響，因此需要高精度映射時(shí)，選用批處理方法，但其難于通

13、過(guò)提高計(jì)算速度來(lái)補(bǔ)償增加的計(jì)算開(kāi)銷。（6）批處理在復(fù)雜優(yōu)化中有直接應(yīng)用，單樣本與批處理的相對(duì)有效性與求解的問(wèn)題直接相關(guān)。 結(jié)論：許多情況下，單樣本修正優(yōu)于批處理，特別是對(duì)大的和冗余的訓(xùn)練集。第三十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)感知器對(duì)線性不可分情況不收斂 樣本集是否線性可分無(wú)法確定 希望找到一種既適合線性可分又適合線性不可分情況的算法。該算法具有如下特性： 對(duì)于線性可分情況，一定能找到將樣本全部正確分類的權(quán)向量。 對(duì)于線性不可分情況，得到一個(gè)使誤差平方和極小的權(quán)向量。該準(zhǔn)則函數(shù)稱為平方誤差準(zhǔn)則函數(shù)。第三十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4

14、最小平方誤差準(zhǔn)則函數(shù)定義平方誤差準(zhǔn)則函數(shù)第三十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)最小二乘近似解即方程個(gè)數(shù)大于未知數(shù)個(gè)數(shù)，屬超定方程組，一般無(wú)解，但可求線性最小二乘解。第三十九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)一、偽逆法（解析方法） 第四十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)一、偽逆法（解析方法） 第四十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)一、偽逆法（解析方法） b的選?。康葍r(jià)于Fisher線性判別漸進(jìn)逼近貝葉斯判別函數(shù)第四十二張，PPT共六十四頁(yè)，創(chuàng)作于202

15、2年6月4.4最小平方誤差準(zhǔn)則函數(shù)第四十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)上例中如何求逆？初等變換第四十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)二、梯度下降法 第四十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)MSE的梯度下降法第四十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.4最小平方誤差準(zhǔn)則函數(shù)MSE梯度下降法的單樣本改進(jìn)第四十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣1、按兩類問(wèn)題處理 one-against-all123C類C個(gè)判別函數(shù)，若若兩個(gè)判別函數(shù)同時(shí)大于0

16、，則樣本落入不確定區(qū)域缺點(diǎn)：存在不確定區(qū)域，樣本落入其中無(wú)法確定類別，錯(cuò)誤率大。第四十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月-123+-+-4.5線性分類器的多類推廣例：設(shè)有一個(gè)三類問(wèn)題，其判別函數(shù)為第四十九張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣兩個(gè)判別函數(shù)同時(shí)大于0則落入不確定區(qū)-123+-+-第五十張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣2、多類化兩類 one-against-one132用線性分類器將類別兩兩分開(kāi)，C類問(wèn)題需要C(C-1)/2個(gè)判別函數(shù)仍然存在不確定區(qū)域第五十一張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5

17、線性分類器的多類推廣例：設(shè)有一個(gè)三類問(wèn)題，其判別函數(shù)為-123+-+-第五十二張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣-123+-+-仍然存在無(wú)效區(qū)域第五十三張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣3、直接按多類問(wèn)題處理132C類C個(gè)判別函數(shù)不存在不確定區(qū)域，多類問(wèn)題多采用此方案。第五十四張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣例：設(shè)有一個(gè)三類問(wèn)題，其判別函數(shù)為123第五十五張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣123無(wú)不確定區(qū)域，經(jīng)常采用第五十六張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣多類感知器例題 給出三類訓(xùn)練樣本如下：第五十七張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類推廣第五十八張，PPT共六十四頁(yè)，創(chuàng)作于2022年6月4.5線性分類器的多類