模式識(shí)別_第三章_判別函數(shù)PPT課件

第三章判別函數(shù)及幾何分類法 第三章判別函數(shù) 3 1判別函數(shù)3 2線性判別函數(shù)3 3廣義線性判別函數(shù)3 4線性判別函數(shù)的幾何性質(zhì)3 5感知器算法3 6梯度法3 7最小平方誤差算法3 8非線性判別函數(shù) 3 1判別函數(shù) 聚類分析法 第二章 判決函數(shù)法 幾何分類法 確定性事件分類 第三章 概率分類法 隨機(jī)事件分類 第四章 線性判決函數(shù)法 統(tǒng)計(jì)決策方法 非線性判決函數(shù)法 復(fù)習(xí)與引申 3 1判別函數(shù) 1 判別函數(shù)定義 用判別函數(shù)分類的概念模式識(shí)別系統(tǒng)的主要作用判別各個(gè)模式所屬的類別對(duì)一個(gè)兩類問題的判別 就是將模式x劃分成 1和 2兩類 3 1判別函數(shù) 1 定義 用判別函數(shù)分類的概念描述 兩類問題的判別函數(shù) 若分屬于 1 2的兩類模式可用一方程d X 0來(lái)劃分 那么稱d X 為判別函數(shù) 或稱判決函數(shù) 決策函數(shù) 3 1判別函數(shù) discriminantfunction 直接用來(lái)對(duì)模式進(jìn)行分類的準(zhǔn)則函數(shù) 例 一個(gè)二維的兩類判別問題 模式分布如圖示 這些分屬于 1 2兩類的模式可用一直線方程d X 0來(lái)劃分 為坐標(biāo)變量 為方程參數(shù) 式中 圖3 2兩類二維模式的分布 1 判別函數(shù)的定義 具體描述 若 則 若 則類 若 則類 或拒絕 將某一未知模式X代入 維數(shù) 3時(shí) 判別邊界為一平面 維數(shù) 3時(shí) 判別邊界為一超平面 d X 表示的是一種分類的標(biāo)準(zhǔn) 它可以是1 2 3維的 也可以是更高維的 判別界面的正負(fù)側(cè) 是在訓(xùn)練判別函數(shù)的權(quán)值時(shí)確定的 2 判別函數(shù)正負(fù)值的確定 圖3 3判別函數(shù)正負(fù)的確定 1 判決函數(shù)d X 的幾何性質(zhì) 它可以是線性的或非線性的函數(shù) 維數(shù)在特征提取時(shí)已經(jīng)確定 如 已知三維線性分類 判決函數(shù)的性質(zhì)就確定了判決函數(shù)的形式 3 確定判別函數(shù)的兩個(gè)因素 例 非線性判決函數(shù) 2 判決函數(shù)d X 的系數(shù) 用所給的模式樣本確定 3 2線性判別函數(shù) 3 2 1線性判別函數(shù)的一般形式 將二維模式推廣到n維 線性判別函數(shù)的一般形式為 3 2 式中 權(quán)向量 即參數(shù)向量 增廣向量的形式 式中 為增廣權(quán)向量 為增廣模式向量 3 2 2線性判別函數(shù)的性質(zhì) 1 兩類情況 對(duì)M個(gè)線性可分模式類 1 2 M 有三種劃分方式 2 多類情況 兩分法 兩分法 兩分法特例 3 2線性判別函數(shù) 3 2 2線性判別函數(shù)的性質(zhì)分類問題多類情況1判別函數(shù)圖例 例子 用線性判別函數(shù)將屬于 i類的模式與其余不屬于 i類的模式分開 識(shí)別分類時(shí) 對(duì)某一模式區(qū) di X 0的條件超過一個(gè) 或全部的di X 0 分類失效 相當(dāng)于不確定區(qū) indefiniteregion IR 此法將M個(gè)多類問題分成M個(gè)兩類問題 識(shí)別每一類均需M個(gè)判別函數(shù) 識(shí)別出所有的M類仍是這M個(gè)函數(shù) 例3 1設(shè)有一個(gè)三類問題 其判別式為 現(xiàn)有一模式 X 7 5 T 試判定應(yīng)屬于哪類 并畫出三類模式的分布區(qū)域 解 將X 7 5 T代入上三式 有 三個(gè)判別界面分別為 圖示如下 步驟 a 畫出界面直線 b 判別界面正負(fù)側(cè) 找特殊點(diǎn)帶入 c 找交集 例3 2已知di X 的位置和正負(fù)側(cè) 分析三類模式的分布區(qū)域 一個(gè)判別界面只能分開兩個(gè)類別 不能把其余所有的類別都分開 判決函數(shù)為 這里 則類 而在判別類模式時(shí)不起作用 如 對(duì)一個(gè)三類問題 如果 識(shí)別分類時(shí) 判別函數(shù)性質(zhì) 與值無(wú)關(guān) 例3 3一個(gè)三類問題 三個(gè)判決函數(shù)為 解 計(jì)算得 可寫成 x2 x1 d23 X 0 d12 X 0 d13 X 0 5 5 3 0 分類時(shí) 每分離出一類 需要與I有關(guān)的M 1個(gè)判決函數(shù) 要分開M類模式 共需M M 1 2個(gè)判決函數(shù) 對(duì)三類問題需要3 3 1 2 3個(gè)判決函數(shù) 即 每次從M類中取出兩類的組合 例3 4已知dij X 的位置和正負(fù)側(cè) 分析三類模式的分布區(qū)域 當(dāng) i j兩分法中的判別函數(shù)dij X 可以分解為 時(shí) 那么di X dj X 就相當(dāng)于多類情況2中的dij X 0 因此對(duì)具有判別函數(shù) 的M類情況 判別函數(shù)性質(zhì)為 或 識(shí)別分類時(shí) 判別界面需要做差值 對(duì) i類 應(yīng)滿足 di 其他所有d 除邊界區(qū)外 沒有不確定區(qū)域 特點(diǎn) 是第二種情況的特例 由于dij X di X dj X 若在第三種情況下可分 則在第二種情況下也可分 但反過來(lái)不一定 把M類情況分成了 M 1 個(gè)兩類問題 并且類的判別界面全部與類的判別界面相鄰 向無(wú)窮遠(yuǎn)處延伸的區(qū)域除外 例3 5一個(gè)三類模式 M 3 分類器 其判決函數(shù)為 試判斷X0 1 1 T屬于哪一類 且分別給出三類的判決界面 解 判決界面如圖所示 類的判決函數(shù) 類的判決函數(shù) 例3 6已知判決界面的位置和正負(fù)側(cè) 分析三類模式的分布區(qū)域 3 2線性判別函數(shù) 3 2 2線性判別函數(shù)的性質(zhì)及分類方法3 小結(jié)明確概念 線性可分模式分類若可用任一個(gè)線性函數(shù)來(lái)劃分 則這些模式就稱為線性可分的 否則就是非線性可分的 一旦線性函數(shù)的系數(shù)wk被確定 這些函數(shù)就可用作模式分類的基礎(chǔ) 3 2線性判別函數(shù) 3 2 2線性判別函數(shù)的性質(zhì)及分類方法多類情況1和多類情況2 的比較對(duì)于M類模式的分類 多類情況1需要M個(gè)判別函數(shù) 而多類情況2需要M M 1 2個(gè)判別函數(shù) 當(dāng)M 3時(shí) 后者需要更多個(gè)判別式 缺點(diǎn) 采用多類情況1時(shí) 每一個(gè)判別函數(shù)都要把一種類別的模式與其余M 1種類別的模式分開 而不是將一種類別的模式僅于另一種類別的模式分開 由于一種模式的分布要比M 1種模式的分布更為聚集 因此多類情況2受到的限制條件少 對(duì)模式的線性可分的可能性比多類情況1更大一些 這是多類情況2的一個(gè)優(yōu)點(diǎn) 3 3廣義線性判別函數(shù) 出發(fā)點(diǎn)線性判別函數(shù)簡(jiǎn)單 容易實(shí)現(xiàn) 非線性判別函數(shù)復(fù)雜 不容易實(shí)現(xiàn) 若能將非線性判別函數(shù)轉(zhuǎn)換為線性判別函數(shù) 則有利于模式分類的實(shí)現(xiàn) 3 3廣義線性判別函數(shù) 基本思想設(shè)有一個(gè)訓(xùn)練用的模式集 x 在模式空間x中線性不可分 但在模式空間x 中線性可分 其中x 的各個(gè)分量是x的單值實(shí)函數(shù) x 的維數(shù)k高于x的維數(shù)n 即若取x f1 x f2 x fk x k n則分類界面在x 中是線性的 在x中是非線性的 此時(shí)只要將模式x進(jìn)行非線性變換 使之變換后得到維數(shù)更高的模式x 就可以用線性判別函數(shù)來(lái)進(jìn)行分類 描述 1 非線性多項(xiàng)式函數(shù)非線性判別函數(shù)的形式之一是非線性多項(xiàng)式函數(shù) 3 3廣義線性判別函數(shù) 目的 對(duì)非線性邊界 通過某映射 把模式空間X變成X 以便將X空間中非線性可分的模式集 變成在X 空間中線性可分的模式集 設(shè)一訓(xùn)練用模式集 X 在模式空間X中線性不可分 非線性判別函數(shù)形式如下 3 9 式中是模式X的單值實(shí)函數(shù) fi X 取什么形式及d X 取多少項(xiàng) 取決于非線性邊界的復(fù)雜程度 廣義形式的模式向量定義為 3 10 這里X 空間的維數(shù)k高于X空間的維數(shù)n 3 9 式可寫為 上式是線性的 討論線性判別函數(shù)并不會(huì)失去一般性的意義 3 11 隨著小樣本學(xué)習(xí)理論和支持向量機(jī)的迅速發(fā)展 廣義線性判別函數(shù)的 維數(shù)災(zāi)難 問題在一定程度上找到了解決的辦法 非線性變換可能非常復(fù)雜 問題 維數(shù)大大增加 維數(shù)災(zāi)難 例3 7假設(shè)X為二維模式向量 fi X 選用二次多項(xiàng)式函數(shù) 原判別函數(shù)為 定義 d X 線性化為 即 廣義線性判別函數(shù) 3 4線性判別函數(shù)的幾何性質(zhì) 3 4 1模式空間與超平面 模式空間 以n維模式向量X的n個(gè)分量為坐標(biāo)變量的歐氏空間 模式向量的表示 點(diǎn) 有向線段 線性分類 用d X 進(jìn)行分類 相當(dāng)于用超平面d X 0把模式空間分成不同的決策區(qū)域 2 討論 1 概念 式中 設(shè)判別函數(shù) 超平面 1 模式向量X1和X2在超平面上 W0是超平面的法向量 方向由超平面的負(fù)側(cè)指向正側(cè) 設(shè)超平面的單位法線向量為U 2 X不在超平面上 將X向超平面投影得向量Xp 構(gòu)造向量R r X到超平面的垂直距離 有 r 判別函數(shù)d X 正比于點(diǎn)X到超平面的代數(shù)距離 X到超平面的距離 點(diǎn)X到超平面的代數(shù)距離 帶正負(fù)號(hào) 正比于d X 函數(shù)值 3 X在原點(diǎn) 得 超平面的位置由閾值權(quán)wn 1決定 wn 1 0時(shí) 原點(diǎn)在超平面的正側(cè) wn 1 0時(shí) 原點(diǎn)在超平面負(fù)側(cè) wn 1 0時(shí) 超平面通過原點(diǎn) 3 4 2權(quán)空間與權(quán)向量解 1 概念 權(quán)空間 以的權(quán)系數(shù)為坐標(biāo)變量的 n 1 維歐氏空間 增廣權(quán)向量的表示 點(diǎn) 有向線段 2 線性分類 判別函數(shù)形式已定 只需確定權(quán)向量 類 X11 X12 X1p 類 X21 X22 X2q 設(shè)增廣樣本向量 使d X 將 1和 2分開 需滿足 給 2的q個(gè)增廣模式乘以 1 統(tǒng)一為 其中 樣本的規(guī)范化過程 對(duì)每個(gè)已知的X d X 0在權(quán)空間確定一個(gè)超平面 共 p q 個(gè) 在權(quán)空間中尋找向量W使判別函數(shù)d X 能把 1類和 2類分開 就是尋找一個(gè)權(quán)向量 其在 p q 個(gè)超平面的正側(cè)的交迭區(qū)域里 W的解區(qū) X 規(guī)范化增廣樣本向量 例 二維權(quán)空間 超平面的方程為 超平面 過原點(diǎn)的直線 陰影部分 解區(qū) 3 4 3二分法 二分法 Dichotomies 用判別函數(shù)d X 將給定的N個(gè)模式分成兩類的方法 是一種基本的分類方法 判別函數(shù)的不同分類能力可以通過二分法總數(shù)衡量 若不限制判別函數(shù)的形式 N個(gè)n維模式用判別函數(shù)分成兩類的二分法總數(shù)為2N 若限定用線性判別函數(shù) 并且樣本在模式空間是良好分布的 即在n維模式空間中沒有 n 1 個(gè)模式位于 n 1 維子空間中 可以證明 N個(gè)n維模式用線性判別函數(shù)分成兩類的方法總數(shù) 即線性二分法總數(shù)為 或線性二分法概率 只要模式的個(gè)數(shù)N小于或等于增廣模式的維數(shù) n 1 模式類總是線性可分的 例 4個(gè)良好分布的2維模式 若用線性判別函數(shù)分類 線性二分法總數(shù) 線性二分法概率 圖3 14線性二分法的概率 將 2時(shí)的N值定義為閾值N0 稱為二分法能力 即 通過N0 可以對(duì)任意N個(gè)樣本的線性可分性進(jìn)行粗略估計(jì) 3 5感知器算法 出發(fā)點(diǎn)一旦判別函數(shù)的形式確定下來(lái) 不管它是線性的還是非線性的 剩下的問題就是如何確定它的系數(shù) 在模式識(shí)別中 系數(shù)確定的一個(gè)主要方法就是通過對(duì)已知樣本的訓(xùn)練和學(xué)習(xí)來(lái)得到 感知器算法就是通過訓(xùn)練樣本模式的迭代和學(xué)習(xí) 產(chǎn)生線性 或廣義線性 可分的模式判別函數(shù) 3 5感知器算法 基本思想采用感知器算法 PerceptionApproach 能通過對(duì)訓(xùn)練模式樣本集的 學(xué)習(xí) 得到判別函數(shù)的系數(shù) 說明這里采用的算法不需要對(duì)各類別中模式的統(tǒng)計(jì)性質(zhì)做任何假設(shè) 因此稱為確定性的方法 3 5感知器算法 背景 感知器 一詞出自于20世紀(jì)50年代中期到60年代中期人們對(duì)一種分類學(xué)習(xí)機(jī)模型的稱呼 它是屬于有關(guān)動(dòng)物和機(jī)器學(xué)習(xí)的仿生學(xué)領(lǐng)域中的問題 當(dāng)時(shí)的一些研究者認(rèn)為感知器是一種學(xué)習(xí)機(jī)的強(qiáng)有力模型 后來(lái)發(fā)現(xiàn)估計(jì)過高了 但發(fā)展感知器的一些相關(guān)概念仍然沿用下來(lái) 3 5感知器算法 1 概念理解 訓(xùn)練 用已知類別的模式樣本指導(dǎo)機(jī)器對(duì)分類規(guī)則進(jìn)行反復(fù)修改 最終使分類結(jié)果與已知類別信息完全相同的過程 1 訓(xùn)練與學(xué)習(xí) 只要求出權(quán)向量 分類器的設(shè)計(jì)即告完成 本節(jié)開始介紹如何通過各種算法 利用已知類別的模式樣本訓(xùn)練出權(quán)向量W 對(duì)線性判別函數(shù) 當(dāng)模式維數(shù)已知時(shí) 判別函數(shù)的形式實(shí)際上已經(jīng)確定 如 三維時(shí) 3 感知器對(duì)一種分類學(xué)習(xí)機(jī)模型的稱呼 屬于有關(guān)機(jī)器學(xué)習(xí)的仿生學(xué)領(lǐng)域中的問題 由于無(wú)法實(shí)現(xiàn)非線性分類而下馬 但 賞罰概念 reward punishmentconcept 得到廣泛應(yīng)用 2 確定性分類器 處理確定可分情況的分類器 通過幾何方法將特征空間分解為對(duì)應(yīng)不同類的子空間 又稱為幾何分類器 2 感知器算法 perceptionapproach 兩類線性可分的模式類 設(shè) 其中 應(yīng)具有性質(zhì) 對(duì)樣本進(jìn)行規(guī)范化處理 即 2類樣本全部乘以 1 則有 感知器算法通過對(duì)已知類別的訓(xùn)練樣本集的學(xué)習(xí) 尋找一個(gè)滿足上式的權(quán)向量 感知器算法步驟 1 選擇N個(gè)分屬于 1和 2類的模式樣本構(gòu)成訓(xùn)練樣本集 X1 XN 構(gòu)成增廣向量形式 并進(jìn)行規(guī)范化處理 任取權(quán)向量初始值W 1 開始迭代 迭代次數(shù)k 1 2 用全部訓(xùn)練樣本進(jìn)行一輪迭代 計(jì)算WT k Xi的值 并修正權(quán)向量 分兩種情況 更新權(quán)向量的值 c 正的校正增量 分類器對(duì)第i個(gè)模式做了錯(cuò)誤分類 權(quán)向量校正為 統(tǒng)一寫為 3 分析分類結(jié)果 只要有一個(gè)錯(cuò)誤分類 回到 2 直至對(duì)所有樣本正確分類 分類正確時(shí) 對(duì)權(quán)向量 賞 這里用 不罰 即權(quán)向量不變 分類錯(cuò)誤時(shí) 對(duì)權(quán)向量 罰 對(duì)其修改 向正確的方向轉(zhuǎn)換 感知器算法是一種賞罰過程 3 收斂性 收斂性 經(jīng)過算法的有限次迭代運(yùn)算后 求出了一個(gè)使所有樣本都能正確分類的W 則稱算法是收斂的 可以證明感知器算法是收斂的 收斂條件 模式類別線性可分 例3 8已知兩類訓(xùn)練樣本 解 所有樣本寫成增廣向量形式 進(jìn)行規(guī)范化處理 屬于 2的樣本乘以 1 用感知器算法求出將模式分為兩類的權(quán)向量解和判別函數(shù) 任取W 1 0 取c 1 迭代過程為 第一輪 有兩個(gè)WT k Xi 0的情況 錯(cuò)判 進(jìn)行第二輪迭代 第二輪 第三輪 第四輪 該輪迭代的分類結(jié)果全部正確 故解向量 相應(yīng)的判別函數(shù)為 當(dāng)c W 1 取其他值時(shí) 結(jié)果可能不一樣 所以感知器算法的解不是單值的 判別界面d X 0如圖示 采用多類情況3的方法時(shí) 應(yīng)有 4 感知器算法用于多類情況 對(duì)于M類模式應(yīng)存在M個(gè)判決函數(shù) 算法主要內(nèi)容 設(shè)有M種模式類別 設(shè)其權(quán)向量初值為 第k次迭代時(shí) 一個(gè)屬于 i類的模式樣本X被送入分類器 計(jì)算所有判別函數(shù) 訓(xùn)練樣本為增廣向量形式 但不需要規(guī)范化處理 分二種情況修改權(quán)向量 若第l個(gè)權(quán)向量使 則相應(yīng)的權(quán)向量作調(diào)整 即 可以證明 只要模式類在情況3判別函數(shù)時(shí)是可分的 則經(jīng)過有限次迭代后算法收斂 c為正的校正增量 例3 9設(shè)有三個(gè)線性可分的模式類 三類的訓(xùn)練樣本分別為 若則權(quán)向量不變 現(xiàn)采用多類情況3的方式分類 試用感知器算法求出判別函數(shù) 解 增廣向量形式 注意 這里任一類的樣本都不能乘以 1 任取初始權(quán)向量 c 1 第一次迭代 三個(gè)權(quán)向量都需要修改 第二次迭代 第三次迭代 修改為權(quán)向量 以上進(jìn)行的一輪迭代運(yùn)算中 三個(gè)樣本都未正確分類 進(jìn)行下一輪迭代 第四次迭代 在第五 六 七迭代中 對(duì)所有三個(gè)樣本都已正確分類 權(quán)向量的解 判別函數(shù) 4 采用感知器算法的多類模式的分類 討論這里的分類算法都是通過模式樣本來(lái)確定判別函數(shù)的系數(shù) 但一個(gè)分類器的判斷性能最終要受并未用于訓(xùn)練的那些未知樣本來(lái)檢驗(yàn) 要使一個(gè)分類器設(shè)計(jì)完善 必須采用有代表性的訓(xùn)練數(shù)據(jù) 它能夠合理反映模式數(shù)據(jù)的整體 4 采用感知器算法的多類模式的分類 討論要獲得一個(gè)判別性能好的線性分類器 究竟需要多少訓(xùn)練樣本 直觀上是越多越好 但實(shí)際上能收集到的樣本數(shù)目會(huì)受到客觀條件的限制 過多的訓(xùn)練樣本在訓(xùn)練階段會(huì)使計(jì)算機(jī)需要較長(zhǎng)的運(yùn)算時(shí)間 一般來(lái)說 合適的樣本數(shù)目可如下估計(jì) 若k是模式的維數(shù) 令C 2 k 1 則通常選用的訓(xùn)練樣本數(shù)目約為C的10 20倍 3 6梯度法 定義梯度是一個(gè)向量 它的最重要性質(zhì)就是指出了函數(shù)f在其自變量y增加時(shí)最大增長(zhǎng)率的方向 負(fù)梯度指出f的最陡下降方向利用這個(gè)性質(zhì) 可以設(shè)計(jì)一個(gè)迭代方案來(lái)尋找函數(shù)的最小值 設(shè)函數(shù)f Y 是向量的函數(shù) 則f Y 的梯度定義為 3 6梯度法 梯度的方向是函數(shù)f Y 在Y點(diǎn)增長(zhǎng)最快的方向 梯度的模是f Y 在增長(zhǎng)最快的方向上的增長(zhǎng)率 增長(zhǎng)率最大值 1 梯度概念 梯度向量的最重要性質(zhì)之一 指出函數(shù)f在其自變量增加時(shí) 增長(zhǎng)最快的方向 3 6 1梯度法基本原理 顯然 負(fù)梯度指出了最陡下降方向 梯度算法的依據(jù) 即 2 梯度算法 設(shè)兩個(gè)線性可分的模式類 1和 2的樣本共N個(gè) 2類樣本乘 1 將兩類樣本分開的判決函數(shù)d X 應(yīng)滿足 梯度算法的目的仍然是求一個(gè)滿足上述條件的權(quán)向量 主導(dǎo)思想是將聯(lián)立不等式求解W的問題 轉(zhuǎn)換成求準(zhǔn)則函數(shù)極小值的問題 N個(gè)不等式 準(zhǔn)則函數(shù)的選取原則 具有唯一的最小值 并且這個(gè)最小值發(fā)生在WTXi 0時(shí) 用負(fù)梯度向量的值對(duì)權(quán)向量W進(jìn)行修正 實(shí)現(xiàn)使準(zhǔn)則函數(shù)達(dá)到極小值的目的 定義一個(gè)對(duì)錯(cuò)誤分類敏感的準(zhǔn)則函數(shù)J W X 在J的梯度方向上對(duì)權(quán)向量進(jìn)行修改 一般關(guān)系表示成從W k 導(dǎo)出W k 1 其中c是正的比例因子 1 將樣本寫成規(guī)范化增廣向量形式 選擇準(zhǔn)則函數(shù) 設(shè)置初始權(quán)向量W 1 括號(hào)內(nèi)為迭代次數(shù)k 1 權(quán)向量修正為 迭代次數(shù)k加1 輸入下一個(gè)訓(xùn)練樣本 計(jì)算新的權(quán)向量 直至對(duì)全部訓(xùn)練樣本完成一輪迭代 3 在一輪迭代中 如果有一個(gè)樣本使 回到 2 進(jìn)行下一輪迭代 否則 W不再變化 算法收斂 2 依次輸入訓(xùn)練樣本X 設(shè)第k次迭代時(shí)輸入樣本為Xi 此時(shí)已有權(quán)向量W k 求 3 6梯度法 采用梯度法求解的基本思想對(duì)感知器算法式中的w k xk隨迭代次數(shù)k而變 是變量 定義一個(gè)對(duì)錯(cuò)誤分類敏感的準(zhǔn)則函數(shù)J w x 先任選一個(gè)初始權(quán)向量w 1 計(jì)算準(zhǔn)則函數(shù)J的梯度 然后從w 1 出發(fā) 在最陡方向 梯度方向 上移動(dòng)某一距離得到下一個(gè)權(quán)向量w 2 從w k 導(dǎo)出w k 1 的一般關(guān)系式 3 6梯度法 討論若正確地選擇了準(zhǔn)則函數(shù)J w x 則當(dāng)權(quán)向量w是一個(gè)解時(shí) J達(dá)到極小值 J的梯度為零 由于權(quán)向量是按J的梯度值減小 因此這種方法稱為梯度法 最速下降法 為了使權(quán)向量能較快地收斂于一個(gè)使函數(shù)J極小的解 C值的選擇是很重要的 若C值太小 則收斂太慢 若C值太大 則搜索可能過頭 引起發(fā)散 例3 10選擇準(zhǔn)則函數(shù) 簡(jiǎn)單地考慮X為一維增廣模式的情況X 1 此時(shí)W w 兩者均為標(biāo)量 錯(cuò)誤分類時(shí) 對(duì)權(quán)向量校正 正確分類時(shí) 對(duì)權(quán)向量不做修正 隨著權(quán)向量W向理想值接近 準(zhǔn)則函數(shù)關(guān)于W的導(dǎo)數(shù) 越來(lái)越趨近于零 這意味著準(zhǔn)則函數(shù)J越來(lái)越接近最小值 當(dāng)最終時(shí) J達(dá)到最小值 此時(shí)W不再改變 算法收斂 將感知器算法中聯(lián)立不等式求解W的問題 轉(zhuǎn)換為求函數(shù)J極小值的問題 c 梯度算法是求解權(quán)向量的一般解法 算法的具體計(jì)算形式取決于準(zhǔn)則函數(shù)J W X 的選擇 J W X 的形式不同 得到的具體算法不同 a b c值的選擇很重要 如c值太小 收斂太慢 但若太大 搜索又可能過頭 甚至引起發(fā)散 3 6 2固定增量法 準(zhǔn)則函數(shù) 求W k 的遞推公式 1 求J的梯度 方法 函數(shù)對(duì)向量求導(dǎo) 函數(shù)對(duì)向量的分量求導(dǎo) 即 該準(zhǔn)則函數(shù)有唯一最小值 0 且發(fā)生在的時(shí)候 設(shè) 部分 首先求 另 矩陣論中有 其中 由 的結(jié)論有 將代入 得 由此可以看出 感知器算法是梯度法的特例 即 梯度法是將感知器算法中聯(lián)立不等式求解W的問題 轉(zhuǎn)換為求函數(shù)J極小值的問題 將原來(lái)有多個(gè)解的情況 變成求最優(yōu)解的情況 上式即為固定增量算法 與感知器算法形式完全相同 即 只要模式類是線性可分的 算法就會(huì)給出解 3 6 2固定增量法 過程說明 設(shè)已由前一步迭代得到w k 的值 讀入模式樣本xk 判別wT k xk是否大于0 xk界定的判別界面為wT k xk 0 當(dāng)w k 在判別界面的負(fù)區(qū)域時(shí) wT k xk 0 校正 w k 1 w k xk 這里取C 1 校正后 w k 1 向量比w k 向量更接近于模式xk所決定的正區(qū)域 3 6 2固定增量法 討論若模式是線性可分的 選擇合適的準(zhǔn)則函數(shù)J w x 算法就能給出解 若模式不是線性可分的 算法的結(jié)果就會(huì)來(lái)回?cái)[動(dòng) 得不到收斂 3 7最小平方誤差算法 leastmeansquareerror LMSE 亦稱Ho Kashyap算法 出發(fā)點(diǎn)感知器算法只是當(dāng)被分模式可用一個(gè)特定的判別界面分開時(shí)才收斂 在不可分情況下 只要計(jì)算程序不終止 它就始終不收斂 即使在模式可分的情況下 也很難事先算出達(dá)到收斂時(shí)所需要的迭代次數(shù) 這樣 在模式分類過程中 有時(shí)候會(huì)出現(xiàn)一次又一次迭代卻不見收斂的情況 白白浪費(fèi)時(shí)間 為此需要知道 發(fā)生遲遲不見收斂的情況時(shí) 到底是由于收斂速度過慢造成的呢 還是由于所給的訓(xùn)練樣本集不是線性可分造成的呢 最小平方誤差 LMSE 算法 除了對(duì)可分模式是收斂的以外 對(duì)于類別不可分的情況也能指出來(lái) 1 分類器的不等式方程 上式分開寫為 寫成矩陣形式為 令N n 1 的長(zhǎng)方矩陣為X 則變?yōu)?式中 0為零向量 感知器算法是通過解不等式組 求出W 2 LMSE算法 1 原理 的求解 式中 兩式等價(jià) 為各分量均為正值的矢量 LMSE算法把對(duì)滿足XW 0的求解 改為滿足 準(zhǔn)則函數(shù)定義為 最小二乘 最小 使方程組兩邊誤差最小 也即使J最小 二乘 次數(shù)為2 乘了兩次 考察向量 XW B 有 可以看出 當(dāng)函數(shù)J達(dá)到最小值 等式XW B有最優(yōu)解 即又將問題轉(zhuǎn)化為求準(zhǔn)則函數(shù)極小值的問題 因?yàn)镴有兩個(gè)變量W和B 有更多的自由度供選擇求解 故可望改善算法的收斂速率 XW B的近似解也稱 最優(yōu)近似解 使方程組兩邊所有誤差之和最小 即最優(yōu) 的解 準(zhǔn)則函數(shù) 使J對(duì)W求最小 令 得 2 推導(dǎo)LMSE算法遞推公式 與問題相關(guān)的兩個(gè)梯度 3 46 3 47 由 3 47 式可知 只要求出B 就可求出W 求遞推公式 1 求W的遞推關(guān)系 X為N n 1 長(zhǎng)方陣 X 為 n 1 N長(zhǎng)方陣 稱為X的偽逆 式中 3 45 2 求B k 1 的迭代式 3 46 代入 得 令 定義 3 49 3 50 3 求W k 1 的迭代式 將 3 50 代入 3 47 式W X B有 總結(jié) 設(shè)初值B 1 各分量均為正值 括號(hào)中數(shù)字代表迭代次數(shù) W k 1 B k 1 互相獨(dú)立 先后次序無(wú)關(guān) 求出B W后 再迭代出下一個(gè)e 從而計(jì)算出新的B W 或另一算法 先算B k 1 再算W k 1 3 模式類別可分性判別 如果e k 0 表明XW k B k 0 隱含有解 繼續(xù)迭代 可使e k 0 如果e k 0 所有分量為負(fù)數(shù)或零 但不全為零 停止迭代 無(wú)解 此時(shí)若繼續(xù)迭代 數(shù)據(jù)不再發(fā)生變化 可以證明 當(dāng)模式類線性可分 且校正系數(shù)c滿足時(shí) 該算法收斂 可求得解W 理論上不能證明該算法到底需要迭代多少步才能達(dá)到收斂 通常在每次迭代計(jì)算后檢查一下XW k 和誤差向量e k 從而可以判斷是否收斂 如果e k 0 表明XW k B k 0 有解 分以下幾種情況 情況 分析 e k 0 綜上所述 只有當(dāng)e k 中有大于零的分量時(shí) 才需要繼續(xù)迭代 一旦e k 的全部分量只有0和負(fù)數(shù) 則立即停止 事實(shí)上 往往早在e k 全部分量都達(dá)到非正值以前 就能看出其中有些分量向正值變化得極慢 可及早采取對(duì)策 通過反證法可以證明 在線性可分情況下 算法進(jìn)行過程中不會(huì)出現(xiàn)e k 的分量全為負(fù)的情況 若出現(xiàn)e k 的分量全為負(fù) 則說明模式類線性不可分 4 LMSE算法描述 1 根據(jù)N個(gè)分屬于兩類的樣本 寫出規(guī)范化增廣樣本矩陣X 2 求X的偽逆矩陣 3 設(shè)置初值c和B 1 c為正的校正增量 B 1 的各分量大于零 迭代次數(shù)k 1 開始迭代 計(jì)算 4 計(jì)算 進(jìn)行可分性判別 如果e k 0 線性可分 若進(jìn)入 5 可使e k 0 得最優(yōu)解 如果e k 0 線性不可分 停止迭代 無(wú)解 算法結(jié)束 如果e k 0 線性可分 解為W k 算法結(jié)束 否則 說明e k 的各分量值有正有負(fù) 進(jìn)入 5 5 計(jì)算W k 1 和B k 1 方法1 分別計(jì)算 方法2 先計(jì)算 再計(jì)算 迭代次數(shù)k加1 返回 4 3 算法特點(diǎn) 1 算法盡管略為復(fù)雜一些 但提供了線性可分的測(cè)試特征 2 同時(shí)利用N個(gè)訓(xùn)練樣本 同時(shí)修改W和B 故收斂速度快 3 計(jì)算矩陣復(fù)雜 但可用迭代算法計(jì)算 例3 11已知兩類模式訓(xùn)練樣本 試用LMSE算法求解權(quán)向量 解 1 寫出規(guī)范化增廣樣本矩陣 Aij是aij的代數(shù)余子式 注意兩者的行和列的標(biāo)號(hào)互換 2 求偽逆矩陣 求逆矩陣 劃去aij所在的行和列的元素 余下元素構(gòu)成的行列式做aij的余子式 記作Mij 將叫做元素aij的代數(shù)余子式 例 代數(shù)余子式定義 行列式 3 取和c 1開始迭代 解為W 1 判斷函數(shù)為 圖示如下 例3 12已知模式訓(xùn)練樣本 2 求 解 1 規(guī)范化增廣樣本矩陣 3 取和c 1 迭代 用LMSE算法求解權(quán)向量 e 1 全部分量為負(fù) 無(wú)解 停止迭代 為線性不可分模式 小結(jié) 1 感知器法 梯度法 最小平方誤差算法討論的分類算法都是通過模式樣本來(lái)確定判別函數(shù)的系數(shù) 所以要使一個(gè)分類器設(shè)計(jì)完善 必須采用有代表性的數(shù)據(jù) 訓(xùn)練判別函數(shù)的權(quán)系數(shù) 它們能合理反映模式數(shù)據(jù)的總體 2 要獲得一個(gè)有較好判別性能的線性分類器 所需要的訓(xùn)練樣本的數(shù)目的確定 用指標(biāo)二分法能力N0來(lái)確定訓(xùn)練樣本的數(shù)目 通常訓(xùn)練樣本的數(shù)目不能低于N0 選為N0的5 10倍左右 二維 不能低于6個(gè)樣本 最好選在30 60個(gè)樣本之間 三維 不能低于8個(gè)樣本 最好選在40 80個(gè)樣本之間 n為模式維數(shù) 如 3 8非線性判別函數(shù)3 8 1分段線性判別函數(shù) 出發(fā)點(diǎn)線性判別函數(shù)在進(jìn)行分類決策時(shí)是最簡(jiǎn)單有效的 但在實(shí)際應(yīng)用中 常常會(huì)出現(xiàn)不能用線性判別函數(shù)直接進(jìn)行分類的情況 采用廣義線性判別函數(shù)的概念 可以通過增加維數(shù)來(lái)得到線性判別 但維數(shù)的大量增加會(huì)使在低維空間里在解析和計(jì)算上行得通的方法在高維空間遇到困難 增加計(jì)算的復(fù)雜性 引入分段線性判別函數(shù)的判別過程 它比一般的線性判別函數(shù)的錯(cuò)誤率小 但又比非線性判別函數(shù)簡(jiǎn)單 3 8 1分段線性判別函數(shù) 特點(diǎn) 基本組成為超平面 相對(duì)簡(jiǎn)單 能逼近各種形狀的超曲面 圖例 用判別函數(shù)分類可用一個(gè)二次判別函數(shù)來(lái)分類也可用一個(gè)分段線性判別函數(shù)來(lái)逼近這個(gè)二次曲線 1 一般分段線性判別函數(shù) 設(shè)有M類模式 將 i類 i 1 2 M 劃分為li個(gè)子類 其中第n個(gè)子類的判別函數(shù) i類的判別函數(shù)定義為 M類的判決規(guī)則 用各類判別函數(shù)進(jìn)行分類判決實(shí)際是用各類選出的子類判別函數(shù)進(jìn)行判決 判別面由各子類的判別函數(shù)決定 若 i類的第n個(gè)子類和 j類的第m個(gè)子類相鄰 判別界面方程為 子類之間的判別界面組成各類之間的判別界面 類間判別界面分段線性 2 基于距離的分段線性判別函數(shù) 設(shè) 1類均值向量 2類均值向量 N1 N2 兩類樣本數(shù) 任一模式X到M1和M2的歐氏距離平方 判決規(guī)則 判別界面方程 1 最小距離分類器 化簡(jiǎn)得 X的線性方程 確定一個(gè)超平面 最小距離分類器 2 分段線性距離分類器 設(shè) M類模式 其中 i類劃分為li個(gè)子類 第n個(gè)子類的均值向量為 每個(gè)子類的判別函數(shù) 每類的判別函數(shù) 判決規(guī)則 若 則 3 8 2分段線性判別函數(shù)的學(xué)習(xí)方法 1 已知子類劃分時(shí)的學(xué)習(xí)方法 每個(gè)子類看成獨(dú)立的類 在一類范圍內(nèi)根據(jù)多類情況3 學(xué)習(xí)各子類判別函數(shù) 繼而得到各類判別函數(shù) 2 已知子類數(shù)目時(shí)的學(xué)習(xí)方法 用類似于固定增量算法的錯(cuò)誤修正算法學(xué)習(xí)分段線性判別函數(shù) 3 未知子類數(shù)目時(shí)的學(xué)習(xí)方法 樹狀分段線性分類器 樹狀分段線性分類器判別函數(shù)的學(xué)習(xí)及分類過程 3 8 3勢(shì)函數(shù)法 一種確定性的非線性分類方法 目的用勢(shì)函數(shù)的概念來(lái)確定判別函數(shù)和劃分類別界面 基本思想假設(shè)要?jiǎng)澐謱儆趦煞N類別 1和 2的模式樣本 這些樣本可看成是分布在n維模式空間中的點(diǎn)xk 把屬于 1的點(diǎn)比擬為某種能源點(diǎn) 在點(diǎn)上 電位達(dá)到峰值 隨著與該點(diǎn)距離的增大 電位分布迅速減小 即把樣本xk附近空間x點(diǎn)上的電位分布 看成是一個(gè)勢(shì)函數(shù)K x xk 對(duì)于屬于 1的樣本集群 其附近空間會(huì)形成一個(gè) 高地 這些樣本點(diǎn)所處的位置就是 山頭 同理 用電位的幾何分布來(lái)看待屬于 2的模式樣本 在其附近空間就形成 凹地 只要在兩類電位分布之間選擇合適的等高線 就可以認(rèn)為是模式分類的判別函數(shù) 一維情況示例 3 8 3勢(shì)函數(shù)法 一種確定性的非線性分類方法 2 勢(shì)函數(shù)法判別函數(shù)的產(chǎn)生模式分類的判別函數(shù)可由分布在模式空間中的許多樣本向量 xk k 1 2 和 的勢(shì)函數(shù)產(chǎn)生 任意一個(gè)樣本所產(chǎn)生的勢(shì)函數(shù)以K x xk 表征 則判別函數(shù)d x 可由勢(shì)函數(shù)序列K x x1 K x x2 來(lái)構(gòu)成 序列中的這些勢(shì)函數(shù)相應(yīng)于在訓(xùn)練過程中輸入機(jī)器的訓(xùn)練模式樣本x1 x2 在訓(xùn)練狀態(tài) 模式樣本逐個(gè)輸入分類器 分類器就連續(xù)計(jì)算相應(yīng)的勢(shì)函數(shù) 在第k步迭代時(shí)的積累位勢(shì)決定于在該步前所有的單獨(dú)勢(shì)函數(shù)的累加 以K x 表示積累位勢(shì)函數(shù) 若加入的訓(xùn)練樣本xk 1是錯(cuò)誤分類 則積累函數(shù)需要修改 若是正確分類 則不變 依次輸入樣本 利用勢(shì)函數(shù)逐步積累勢(shì)能的過程 判別函數(shù)由模式空間中樣本向量的勢(shì)函數(shù)K X Xk 累加產(chǎn)生 分類器計(jì)算積累勢(shì)K X 最后取d X K X 設(shè)初始積累勢(shì)函數(shù) 下標(biāo)為迭代次數(shù) 勢(shì)函數(shù)法 第一步 加入訓(xùn)練樣本X1 K1 X 描述了加入第一個(gè)樣本后的邊界劃分 第二步 加第二個(gè)訓(xùn)練樣本X2 分三種情況 分類正確 勢(shì)函數(shù)不變 錯(cuò)誤分類 修改勢(shì)函數(shù) 第k步 設(shè)Kk X 為加入訓(xùn)練樣本X1 X2 Xk后的積累勢(shì)函數(shù) 則加入第k 1個(gè)樣本 有 以上決定積累位勢(shì)的迭代算法可寫為 其中rk 1為校正項(xiàng)系數(shù) 定義為 3 57 3 58 從所給的訓(xùn)練樣本集中略去不使積累勢(shì)發(fā)生變化的那些樣本 可得一簡(jiǎn)化樣本序列 校正錯(cuò)誤的樣本 算法可歸納為 即 由 k 1 個(gè)訓(xùn)練樣本產(chǎn)生的積累勢(shì) 等于兩類中校正錯(cuò)誤的樣本的總勢(shì)能之差 式中 3 59 3 60 從勢(shì)函數(shù)算法可看出 積累勢(shì)函數(shù)起著判別函數(shù)的作用 因此可直接用作判別函數(shù) 故取d X K X 由 3 57 式得 式中rk 1按 3 58 式取值 也可簡(jiǎn)寫成 式中取值同 3 60 3 61 從勢(shì)函數(shù)可以看出 積累位勢(shì)起著判別函數(shù)的作用當(dāng)xk 1屬于 1時(shí) Kk xk 1 0 當(dāng)xk 1屬于 2時(shí) Kk xk 1 0 則積累位勢(shì)不做任何修改就可用作判別函數(shù) 由于一個(gè)模式樣本的錯(cuò)誤分類可造成積累位勢(shì)在訓(xùn)練時(shí)的變化 因此勢(shì)函數(shù)算法提供了確定 1和 2兩類判別函數(shù)的迭代過程 判別函數(shù)表達(dá)式取d x K x 則有 dk 1 x dk x rk 1K x xk 1 兩個(gè)n維向量X和Xk的函數(shù)K X Xk 如同時(shí)滿足下列三個(gè)條件 都可做為勢(shì)函數(shù) 3 勢(shì)函數(shù)的選擇 當(dāng)向量X與Xk的距離趨于無(wú)窮時(shí) K X Xk 趨于零 K X Xk 是光滑函數(shù) 且是X與Xk之間距離的單調(diào)下降函數(shù) 1 勢(shì)函數(shù)應(yīng)具備的條件 2 構(gòu)成勢(shì)函數(shù)的兩種方法 式中 在模式定義域內(nèi)應(yīng)為正交函數(shù)集 型勢(shì)函數(shù) 用對(duì)稱的有限項(xiàng)多項(xiàng)式展開 即 a 內(nèi)積 定義為 是一個(gè)實(shí)數(shù) 正交函數(shù) 概念 已知函數(shù)y x 和z x b 正交 滿足 y z 0 例 將這類勢(shì)函數(shù)代入 3 61 式 有判別函數(shù) 型勢(shì)函數(shù) 直接選擇雙變量X和Xk的對(duì)稱函數(shù)作為勢(shì)函數(shù) 即 如 3 67 3 68 曲線c含有正弦函數(shù) 具有振蕩特點(diǎn) 只有第一個(gè)振蕩周期可用 式中為正常數(shù) 3 66 圖3 25一維 型勢(shì)函數(shù)舉例 例3 14設(shè)兩類訓(xùn)練樣本集 樣本分布如圖所示 用 型勢(shì)函數(shù)進(jìn)行分類 求判別函數(shù) 解 兩類模式不是線性可分的 這里選擇指數(shù)型的勢(shì)函 二維情況下勢(shì)函數(shù)為 開始迭代 式中 第一步 第二步 分類正確 不修正 第三步 分類錯(cuò)誤 修正 第四步 分類錯(cuò)誤 修正 第五步 不修正 第六步 修正 第七步 不修正 第八步 不修正 第九步 不修正 第十步 不修正 從X7至X10的四次迭代中 所有訓(xùn)練樣本皆被正確分類 故算法已收斂于判別函數(shù) 分類器設(shè)計(jì)完畢 判別函數(shù) 判別界面 d X 0 第七步 第八步 3 勢(shì)函數(shù)的選擇討論用第二類勢(shì)函數(shù) 當(dāng)訓(xùn)練樣本維數(shù)和數(shù)目都較高時(shí) 需要計(jì)算和存儲(chǔ)的指數(shù)項(xiàng)較多 正因?yàn)閯?shì)函數(shù)由許多新項(xiàng)組成 因此有很強(qiáng)的分類能力 結(jié)束 同學(xué)們 來(lái)學(xué)校和回家的路上要注意安全 同學(xué)們 來(lái)學(xué)校和回家的路上要注意安全