線性判別函數(shù)

線性判別函數(shù)第1頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1引言問(wèn)題的提出

線性決策面是較簡(jiǎn)單的，易于實(shí)現(xiàn)，因此本章主要討論線性分類器。第2頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1引言判別函數(shù)形式第3頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1引言兩類情況決定分類界面的方向，決定分類界面的位置第4頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1引言線性分類器的設(shè)計(jì)步驟

（1）有一已知類別的樣本集H

（2）確定一準(zhǔn)則函數(shù)

（3）利用最優(yōu)化技術(shù)求出準(zhǔn)則函數(shù)極值解

第5頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.1引言與最優(yōu)分類器的關(guān)系

貝葉斯分類器是在錯(cuò)誤率或風(fēng)險(xiǎn)下為最優(yōu)的分類器。線性分類器針對(duì)錯(cuò)誤率或風(fēng)險(xiǎn)是“次優(yōu)”的。但對(duì)于所采用的準(zhǔn)則函數(shù)則是最優(yōu)的。線性可分性已知一樣本集，如果有一個(gè)線性分類器能把每個(gè)樣本正確分類，則稱這組樣本集為線性可分的，否則稱為線性不可分的。反之，如果樣本集是線性可分的，則必然存在一個(gè)線性分類器能把每個(gè)樣本正確分類。第6頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別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)典論文開始最早研究線性判別函數(shù)，發(fā)明了最大似然估計(jì)方法。其著作有《研究者用的統(tǒng)計(jì)方法》《統(tǒng)計(jì)方法和科學(xué)推理》《近交的理論》《試驗(yàn)設(shè)計(jì)》《自然選擇的遺傳理論》《根據(jù)孟德爾遺傳方式的親屬間的相關(guān)》第7頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）

問(wèn)題的提出

在低維空間中行得通的方法在高維空間里往往失效，因此需要降低空間維數(shù)。

基本原理將高維空間數(shù)據(jù)向某一直線上投影，如何確定該直線在特征空間中的最佳方向？Fisher法即尋找最佳的投影方向，使投影后樣本最佳可分第8頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）投影的表示0投影示意圖第9頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）基本參量定義（d維x空間）

（1）各類樣本均值向量（2）樣本類內(nèi)離散度矩陣和總類內(nèi)離散度矩陣（3）樣本類間離散度矩陣對(duì)稱半正定陣，當(dāng)N>d時(shí)通常非奇異對(duì)稱半正定陣第10頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）補(bǔ)充定義—正定二次型設(shè)有實(shí)二次型，若對(duì)任意向量X都有f>0，則稱矩陣A為正定矩陣；若f<0，則稱A為負(fù)定矩陣；若f≧0，則稱A為半正定矩陣。補(bǔ)充定義—非奇異陣當(dāng)|A|=0時(shí)，方陣A為奇異陣；|A|≠0時(shí)，方陣A為非奇異陣。方陣A可逆的充要條件是|A|≠0?？赡骊囈喾Q非退化陣或非奇異陣或滿秩陣不可逆的方陣也稱退化陣或奇異陣或降秩陣第11頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）基本參量定義（一維y空間）

（1）各類樣本均值向量（2）樣本類內(nèi)離散度矩陣和總類內(nèi)離散度矩陣

第12頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）定義Fisher準(zhǔn)則函數(shù)原則：各類樣本盡可能分開，類內(nèi)樣本盡量密集，需求令準(zhǔn)則函數(shù)極大的。第13頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）準(zhǔn)則函數(shù)的顯式化求令準(zhǔn)則函數(shù)極大的第14頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）求令準(zhǔn)則函數(shù)極大的要求的是方向，常量系數(shù)可去除第15頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）概念補(bǔ)充—二次型對(duì)向量求導(dǎo)第16頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）投影過(guò)程一維閾值的選取

（1）當(dāng)維數(shù)與樣本數(shù)都很大時(shí)，可用貝葉斯分類器（2）依據(jù)先驗(yàn)知識(shí)選擇第17頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.2Fisher線性判別（兩類）Fisher線性判別步驟（1）求兩類樣本均值向量（2）求兩類樣本類內(nèi)離散度矩陣（3）求總類內(nèi)離散度矩陣（4）求向量（5）求出兩類樣本在上的投影點(diǎn)（6）求各類在投影空間的均值（7）選取閾值（8）對(duì)于未知樣本，計(jì)算其在上的投影點(diǎn)y

（9）根據(jù)決策規(guī)則分類第18頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）問(wèn)題的提出

20世紀(jì)50年代由Rosenblatt提出，用于腦模型感知器，故稱為感知準(zhǔn)則函數(shù)。該模型未獲成功，主要由于無(wú)法解決非線性問(wèn)題，但其思想可沿用。

第19頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）基本思想

分類器形式已定，只要估計(jì)出權(quán)值向量即完成分類器設(shè)計(jì)。感知器采用迭代的方法，是一種典型的賞罰過(guò)程，對(duì)正確分類的模式則“賞”，這里即“不罰”，權(quán)向量不變。對(duì)錯(cuò)誤分類的模式則“罰”，即修正權(quán)向量。第20頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）樣本及權(quán)向量的增廣

第21頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）樣本的規(guī)范化

如果樣本集是線性可分的，必然存在某個(gè)權(quán)向量可使第22頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月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ù)極小，采用梯度下降法第23頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）感知準(zhǔn)則函數(shù)的梯度下降求解

尋求最優(yōu)的a令J極小迭代方式尋找極小值思想：由某一初值開始，沿某一方向，按某一步長(zhǎng)搜尋極小值，由于梯度是函數(shù)值增長(zhǎng)最快的方向，沿負(fù)梯度即為函數(shù)下降最快的方向，沿此方向可最快到達(dá)極小點(diǎn)，故稱梯度下降法。第24頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）純量對(duì)向量求導(dǎo)補(bǔ)充定義：純量對(duì)向量求導(dǎo)負(fù)負(fù)為正第25頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）感知準(zhǔn)則函數(shù)梯度下降法步驟收斂，結(jié)束第26頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月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+1)，轉(zhuǎn)（2）第27頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）例：已知兩類樣本，以感知器算法求解分類器（求判別函數(shù)）第28頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）解：寫出規(guī)范化增廣樣本向量第29頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）第30頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）批處理—把所有錯(cuò)分類樣本一次性找出來(lái)修正與人的學(xué)習(xí)方式不同，人采用“單樣本修正”方式單樣本修正—找出一個(gè)錯(cuò)分樣本即進(jìn)行修正第31頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）按單樣本修正法重作例題固定增量法第32頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）迭代方法要從理論上證明收斂，此處僅以圖形方式說(shuō)明修正前錯(cuò)分類修正后正確分類第33頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月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ì)于線性不可分情況，算法不收斂。第34頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）單樣本修正與批處理的比較：（1）學(xué)習(xí)開始時(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)。第35頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.3感知準(zhǔn)則函數(shù)（兩類）單樣本修正與批處理的比較：（5）批處理對(duì)梯度矢量估計(jì)較好，避免了權(quán)值變化相互影響，因此需要高精度映射時(shí)，選用批處理方法，但其難于通過(guò)提高計(jì)算速度來(lái)補(bǔ)償增加的計(jì)算開銷。（6）批處理在復(fù)雜優(yōu)化中有直接應(yīng)用，單樣本與批處理的相對(duì)有效性與求解的問(wèn)題直接相關(guān)。

結(jié)論：許多情況下，單樣本修正優(yōu)于批處理，特別是對(duì)大的和冗余的訓(xùn)練集。第36頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)感知器對(duì)線性不可分情況不收斂∵樣本集是否線性可分無(wú)法確定∴希望找到一種既適合線性可分又適合線性不可分情況的算法。該算法具有如下特性：對(duì)于線性可分情況，一定能找到將樣本全部正確分類的權(quán)向量。對(duì)于線性不可分情況，得到一個(gè)使誤差平方和極小的權(quán)向量。該準(zhǔn)則函數(shù)稱為平方誤差準(zhǔn)則函數(shù)。第37頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)定義平方誤差準(zhǔn)則函數(shù)第38頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)最小二乘近似解即方程個(gè)數(shù)大于未知數(shù)個(gè)數(shù)，屬超定方程組，一般無(wú)解，但可求線性最小二乘解。第39頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)一、偽逆法（解析方法）

第40頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)一、偽逆法（解析方法）

第41頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)一、偽逆法（解析方法）

b的選??？等價(jià)于Fisher線性判別漸進(jìn)逼近貝葉斯判別函數(shù)第42頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)第43頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)上例中如何求逆？初等變換第44頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)二、梯度下降法

第45頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)MSE的梯度下降法第46頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.4最小平方誤差準(zhǔn)則函數(shù)MSE梯度下降法的單樣本改進(jìn)第47頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.5線性分類器的多類推廣1、按兩類問(wèn)題處理one-against-all123C類C個(gè)判別函數(shù)，若若兩個(gè)判別函數(shù)同時(shí)大于0，則樣本落入不確定區(qū)域缺點(diǎn)：存在不確定區(qū)域，樣本落入其中無(wú)法確定類別，錯(cuò)誤率大。第48頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月-123+-++-4.5線性分類器的多類推廣例：設(shè)有一個(gè)三類問(wèn)題，其判別函數(shù)為第49頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.5線性分類器的多類推廣兩個(gè)判別函數(shù)同時(shí)大于0則落入不確定區(qū)-123+-++-第50頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.5線性分類器的多類推廣2、多類化兩類one-against-one132用線性分類器將類別兩兩分開，C類問(wèn)題需要C(C-1)/2個(gè)判別函數(shù)仍然存在不確定區(qū)域第51頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.5線性分類器的多類推廣例：設(shè)有一個(gè)三類問(wèn)題，其判別函數(shù)為-123+-++-第52頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.5線性分類器的多類推廣-123+-++-仍然存在無(wú)效區(qū)域第53頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.5線性分類器的多類推廣3、直接按多類問(wèn)題處理132C類C個(gè)判別函數(shù)不存在不確定區(qū)域，多類問(wèn)題多采用此方案。第54頁(yè)，課件共61頁(yè)，創(chuàng)作于2023年2月4.5線性分類器的多類推廣例：設(shè)有一個(gè)三類問(wèn)題，其判別函數(shù)為