【正文】 為零向量 感知器算法是通過解不等式組 ，求出 W。 0?XW2. LMSE算法 1) 原理 的求解。式中： ∴ 兩式等價(jià)。 ? ? T21 ,, Ni bbbb ???B 為各分量均為正值的矢量。 LMSE算法把對(duì)滿足 XW 0 的求解，改為滿足 BXW ?① 在方程組中當(dāng)行數(shù) 列數(shù)時(shí)，通常無解，稱為矛盾方程組，一般求近似解。在模式識(shí)別中，通常訓(xùn)練樣本數(shù) N總是大于模 式的維數(shù) n，因此方程的個(gè)數(shù) (行數(shù) )模式向量的維數(shù) (列數(shù) )， 是矛盾方程組，只能求近似解 W*，即 說明： 極小? BXW *② LMSE算法的出發(fā)點(diǎn)：選擇一個(gè)準(zhǔn)則函數(shù)，使得當(dāng) J達(dá)到最小值時(shí)， XW=B 可得到 近似解（最小二乘近似解） 。 ③ LMSE算法的思路： BWBXWXW、通過求準(zhǔn)則函數(shù)極小找求解對(duì)求解對(duì)?? 0轉(zhuǎn)化為 轉(zhuǎn)化為 準(zhǔn)則函數(shù)定義為： ? ? 221, BXWBXW ?J“最小二乘”： —— 最小：使方程組兩邊誤差最小， 也即使 J最小。 —— 二乘：次數(shù)為 2，乘了兩次 最小平方（誤差算法） ? ?? ? 1111121111221111111111???????????????????????????????????????????????????????????NNinnnnNNnNininnbbbwwwwxxxxxxxx?????????????BXW????????????????????????????????????????????NNiiNNnnNnNinnininnnbbbbwwxwxbwwxwxbwwxwxXWXWXWTT11T1111111111111???????? ? 向量各分量的平方和向量各分量的平方和 ?? 22BXW? ? ? ? ? ??????? NiiiNN bbb12T2T211T2 XWXWXWBXW ?考察向量 (XW－ B) 有： 可以看出： ① 當(dāng)函數(shù) J達(dá)到最小值，等式 XW=B有最優(yōu)解。即又將問題轉(zhuǎn)化為求準(zhǔn)則函數(shù)極小值的問題。 ② 因?yàn)?J有兩個(gè)變量 W和 B，有更多的自由度供選擇求解，故可望改善算法的收斂速率。 ? ? ? ?21T22121, ????Niii bJ XWBXWBXWXW=B 的近似解也稱“最優(yōu)近似解”： —— 使方程組兩邊所有誤差之和最?。醋顑?yōu)）的解。 準(zhǔn)則函數(shù)： ? ? ? ? BXBXXXWBXXWXBXWX T1TTTT 0 ?????? 使 J 對(duì) W求最小，令 ，得： 2) 推導(dǎo) LMSE算法遞推公式 與問題相關(guān)的兩個(gè)梯度： ? ?BXWXW ??? TJ? ?? ?BXWBXWB ???? 21J (346) (347) 由 (347)式可知：只要求出 B， 就可求出 W。 求遞推公式： (1) 求 W 的遞推關(guān)系 X為 N (n+1)長(zhǎng)方陣， X為 (n+1) N 長(zhǎng)方陣 。 ? ? T1T XXXX ? 稱為 X的偽逆， 式中： (345) 0???WJ(2) 求 B(k+1)的迭代式 ? ? ? ?? ?kJckkBBBBB???????????? 1? ? ? ? ? ? ? ?? ? ? ? ? ?? ?kkkkckk BXWBXWBB ????? 21(346)代入，得 cc ?? 2 ? ? ? ? ? ?kkk eBXW ? 令 ，定義 (349) ? ? ? ? ? ? ? ?? ?kkckk eeBB ???? 1 (350) (346) ? ?? ?BXWBXWB ????21J利用梯度算法公式 有： ? ? ? ? ? ?? ?kJckkWWWXWWW??????????? ,1? ? ? ? ? ?? ?kk BBXXXXX ? T1T? ? ? ? ? ?kckck eXeXBX ???(3) 求 W(k+1)的迭代式 將 (350)代入 (347)式 W=XB 有： ? ? ? ? ? ? ? ? ? ?? ?? ?kkckkk eeBXBXW ?????? 11? ? ? ? ? ? ? ?? ?kkk BXWXXXeX ? T1T=0 ? ? ? ?kck eXW ??0?? ? ? ? ? ?kkk eBXW ? (349) ? ? ? ? ? ? ? ?? ?kkckk eeBB ???? 1 (350) ? ? ? ?11 BXW ?? ? ? ? ? ?kkk BXWe ?? ? ? ? ? ?kckk eXWW 1 ???? ? ? ? ? ? ? ?? ?kkckk eeBB ???? 1? ? ? ?11 ??? kk BXW總結(jié)：設(shè)初值 B(1)，各分量均為正值，括號(hào)中數(shù)字代表迭代次數(shù) 。 …… W(k+1)、 B(k+1)互相獨(dú)立，先后次序無關(guān)。 …… 求出 B， W后，再迭代出下一個(gè) e，從而計(jì)算出新的 B， W。 ? ? ? ?11 BXW ?? ? ? ? ? ?kkk BXWe ?? ? ? ? ? ? ? ?? ?kkckk eeBB ???? 1或另一算法：先算 B(k+1)，再算 W(k+1)。 3）模式類別可分性判別 ② 如果 e(k)0 ，表明 XW(k)B(k) 0， 隱含有解。繼續(xù)迭代， 可使 e(k) → 0 。 ③ 如果 e(k)0（所有分量為負(fù)數(shù)或零，但不全為零），停止迭 代，無解。此時(shí)若繼續(xù)迭代，數(shù)據(jù)不再發(fā)生變化。 可以證明：當(dāng)模式類線性可分，且校正系數(shù) c滿足 時(shí)，該算法收斂，可求得解 W。 10 ?? c 理論上不能證明該算法到底需要迭代多少步才能達(dá)到收 斂，通常在每次迭代計(jì)算后檢查一下 XW(k) 和誤差向量 e(k) ， 從而可以判斷是否收斂。 ① 如果 e(k)=0 ，表明 XW(k)=B(k) 0，有解。 分以下幾種情況： ? ? ? ? ? ?111 ???? kkk BXWe? ? ? ?kk WW ?? 1? ? ? ?kk ee ?? 1? ? ? ?kk BB ?? 1? ? ? ?11 ??? kk BXW情況③分析： ? ? ? ? ? ? ? ?? ?kkckk eeBB ???? 1e(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的偽逆矩陣 。 ? ? T1T XXXX ?…… (3) 設(shè)置初值 c和 B(1)， c為正的校正增量， B(1)的各分量大于零， 迭代次數(shù) k=1 。開始迭代： 計(jì)算 ? ? ? ?11 BXW ?(4) 計(jì)算 ，進(jìn)行可分性判別。 ? ? ? ? ? ?kkk BXWe ?如果 e(k)0，線性可分，若進(jìn)入 (5)可使 e(k) → 0 ，得最優(yōu)解。 如果 e(k)0，線性不可分，停止迭代，無解，算法結(jié)束。 如果 e(k)=0，線性可分，解為 W(k)，算法結(jié)束。 否則，說明 e(k)的各分量值有正有負(fù)，進(jìn)入 (5)。 ? ? ? ? ? ?kckk eXWW 1 ???? ? ? ? ? ? ? ?? ?kkckk eeBB ???? 1? ? ? ? ? ? ? ?? ?kkckk eeBB ???? 1? ? ? ?11 ??? kk BXW(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ì)算。 ? ? 1T XX例 已知兩類模式訓(xùn)練樣本： ? ? ? ?TT1 1,0,0,0:?? ? ? ?TT2 1,1,0,1:? 1x 2x 0 1? 2? 1 1 試用 LMSE算法求解權(quán)向量。 ?????????????111101110100X解： (1) 寫出規(guī)范化增廣樣本矩陣： Aij是 aij的代數(shù)余子式，注意兩者的行和列的標(biāo)號(hào)互換。 ? ? T1T XXXX ? (2) 求偽逆矩陣 ??????????????????????????????????422221212111101110100111110101100T XX*1 1 AAA ?求逆矩陣： ???????????333231232221131211aaaaaaaaaA???????????332313232212312111*AAAAAAAAAA若 ，則 |A|——A的行列式 A*——A的伴隨矩陣 ???????????422221212T XX 劃去 aij所在的行和列的元素，余下元素構(gòu)成的行列式做aij的余子式，記作 Mij ，將 叫做元素 aij的代數(shù)余子式。例： 代數(shù)余子式定義： ? ? ijij AM ?? ji1? ?32311211323112113223 1 aaaaaaaaA ?? ?? ???????????????????????322240204413222402041T1TXXXX44884416422221212T ?????XX行列式 : ???????????333231232221131211aaaaaaaaaA*1 1 AAA ?????????????????????????????????1113222222224111111010110032224020441X? ? ? ??????????? ??????????? ??????????????