糾錯(cuò)輸出編碼相關(guān)論文綜述和要點(diǎn)
糾錯(cuò)輸出編碼相關(guān)論文綜述和要點(diǎn)
糾錯(cuò)輸出編碼（ECOC）綜述和基本原理 目錄
<機(jī)器學(xué)習(xí)導(dǎo)論> ....................................................................................................................... 1
《Solving Multiclass Learning Problems via Error-Correcting Output Codes》 ....................... 2
A Subspace to ECOC .................................................................................................................. 3
中文參考文獻(xiàn) ........................................................................................................................... 5
<機(jī)器學(xué)習(xí)導(dǎo)論>
在糾錯(cuò)輸出編碼中，主要的分類(lèi)任務(wù)通過(guò)由基學(xué)習(xí)器實(shí)現(xiàn)的一組子任務(wù)來(lái)定義。其思想是：將一個(gè)類(lèi)從其他類(lèi)區(qū)分開(kāi)來(lái)的原始任務(wù)可能是一個(gè)困難的問(wèn)題。作為替代，我們定義一組簡(jiǎn)單的分類(lèi)問(wèn)題，每個(gè)專(zhuān)注于原始任務(wù)的一個(gè)方面，并通過(guò)組合這些簡(jiǎn)單的分類(lèi)器來(lái)得到最終的分類(lèi)器。
這時(shí)，基分類(lèi)器是輸出為-1/+1的二元分類(lèi)器，并且有一個(gè)K*L的編碼矩陣W，其K行是關(guān)于L個(gè)基學(xué)習(xí)器dj類(lèi)的二元編碼。例如，M(2, ) [ 1 1 1 1]表示若一個(gè)樣本屬于第2類(lèi)(C2)，則該樣本應(yīng)在h1和h4上取負(fù)值，在h2和h3上取正值；M(, 3) [ 1 1 1]T可理解為第三個(gè)基分類(lèi)器h3的任務(wù)是將屬于C1類(lèi)的樣本與屬于C2和C3類(lèi)的樣本區(qū)分開(kāi)。同時(shí)M(, 3)也決定了如何構(gòu)造基分類(lèi)器h3的訓(xùn)練樣本集T3：所有標(biāo)記為C2類(lèi)及C3類(lèi)的樣本形成正樣本 3 ，而標(biāo)記為C1類(lèi)的實(shí)例構(gòu)成負(fù)樣本 3 ，對(duì)h3的訓(xùn)練應(yīng)使得 xi T3，當(dāng)xi 3 時(shí)，h3(xi) 1；當(dāng)xi 3 時(shí)，h3(xi) 1。
這樣，編碼矩陣使得我們可以用二分類(lèi)問(wèn)題定義多分類(lèi)問(wèn)題，并且這是一種適用于任意可以實(shí)現(xiàn)二分基學(xué)習(xí)器的學(xué)習(xí)算法的方法，例如，線(xiàn)性或多層感知器，決策樹(shù)或初始定義的兩類(lèi)問(wèn)題的SVM。
典型的每類(lèi)一個(gè)判別式的情況對(duì)應(yīng)于對(duì)角矩陣，其中L=K，例如，對(duì)于K=4，我們有
W=【】
這里的問(wèn)題是：如果某一個(gè)基學(xué)習(xí)器存在錯(cuò)誤，就會(huì)有誤分類(lèi)，因?yàn)轭?lèi)的碼
糾錯(cuò)輸出編碼相關(guān)論文綜述和要點(diǎn)
字之間非常相似，因而糾錯(cuò)碼采用的方法是使L>K來(lái)增加碼字之間的漢明距離。一種可能的方法是類(lèi)逐對(duì)分開(kāi)，其中對(duì)i<j有一個(gè)不同的基學(xué)習(xí)器將ci和cj分開(kāi)。在這種情況下，當(dāng)K=4時(shí)，L=K(K-1)/2，編碼矩陣為W=[]。
其中的0表示無(wú)關(guān)，這就是說(shuō)，訓(xùn)練d1來(lái)將C1與C2分開(kāi)并且在訓(xùn)練中不使用屬于其他類(lèi)的實(shí)例。類(lèi)似地，一個(gè)實(shí)例屬于C2如果有d1=-1,并且d4=d5=+1,并且我們不考慮d2,d3,d6的值。這種方法的問(wèn)題是對(duì)于比較大的K，逐對(duì)分開(kāi)是不可行的。
方法是預(yù)先設(shè)定L值，然后尋找w使得以漢明距離衡量的行間距以及列間距離都盡可能的大。對(duì)K類(lèi)問(wèn)題而言，存在2k-1-1中可能列，即兩類(lèi)問(wèn)題。這是因?yàn)镵位可以寫(xiě)成2K種不同的形式和補(bǔ)（比如，“0101”和“1010”，從我們的角度來(lái)看，二者定義相同的判別式），將所有可能組合除以2減1，因?yàn)槿珵?（或1）的列是無(wú)用的`。例如K=4時(shí)，我們有
1 1M 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
當(dāng)K很大時(shí)，對(duì)于一個(gè)給定的L值，我們從2k-1-1列中選取L列，我們希望W的這些列盡可能的不相同，以便每個(gè)基學(xué)習(xí)器所學(xué)習(xí)的子任務(wù)盡可能互不相同。同時(shí)，我們希望W的行業(yè)盡可能的不相同，使得在一個(gè)活多個(gè)基學(xué)習(xí)器失效時(shí)，可以獲得最大的糾錯(cuò)。 ECOC可以用投票方式來(lái)表述，其中W的元素wij可以看作投票權(quán)值：
yi wijdj
j 1L
然后我們選取具有最高yi的類(lèi)。通過(guò)求加權(quán)和并選擇最大值（判別類(lèi)別）取代尋求一個(gè)精確的匹配使得dj也不必是二元的，二是可取-1到+1之間的任意值，以軟確定性取代硬判決。注意位于0到1之間的pj值（例如后驗(yàn)概率）可以很簡(jiǎn)單地被轉(zhuǎn)換為-1到+1之間的dj值： Dj=2pj-1
。
ECOC的一個(gè)問(wèn)題是：由于編碼矩陣W被設(shè)置為先驗(yàn)，因此不能保證由W的列所定義的子任務(wù)一定是簡(jiǎn)單。Dietterich的研究表明二分樹(shù)可能要比多分樹(shù)大，而且當(dāng)使用多層感知器時(shí)，后向傳播可能收斂較慢。
《Solving Multiclass Learning Problems via Error-Correcting Output Codes》
最早的ECOC文獻(xiàn)：
糾錯(cuò)編碼設(shè)計(jì)。
定義一個(gè)K*L維二值矩陣為糾錯(cuò)輸出編碼矩陣。矩陣的列數(shù)即為編碼的長(zhǎng)度，矩陣的行數(shù)即為多分類(lèi)問(wèn)題的分類(lèi)類(lèi)數(shù)。矩陣中的每行M(r,·)表示一個(gè)類(lèi)別的碼文。
對(duì)于K類(lèi)問(wèn)題，一個(gè)好的糾錯(cuò)輸出編碼矩陣應(yīng)該滿(mǎn)足兩個(gè)要求：
糾錯(cuò)輸出編碼相關(guān)論文綜述和要點(diǎn)
一是行盡量分開(kāi)。即每個(gè)類(lèi)別的碼文與其它類(lèi)別的碼文間的漢明距離要盡可能大。
二是列盡量分開(kāi)。每個(gè)基學(xué)習(xí)器決策函數(shù)hi應(yīng)該與其余的基學(xué)習(xí)器決策函數(shù)hj，j不等于i，是相互獨(dú)立的。這可以通過(guò)強(qiáng)調(diào)列i和其余列之間的漢明距離要大以及列i與其它列的補(bǔ)之間的距離要大來(lái)獲得。
編碼的糾錯(cuò)輸能力與行間漢明距離直接相關(guān)。而列間漢民距離需要大的目的還不明確。如果兩列列i和列j十分相似或完全一樣，那么基學(xué)習(xí)器的判決函數(shù)hi和hj的決策結(jié)果會(huì)含有相同的錯(cuò)誤。僅當(dāng)錯(cuò)誤出現(xiàn)在不同的編碼位置時(shí)，糾錯(cuò)輸出編碼才是有效的，所以不同位置同時(shí)出現(xiàn)的錯(cuò)誤的機(jī)會(huì)必須少。當(dāng)同時(shí)出現(xiàn)錯(cuò)誤較多時(shí)，糾錯(cuò)碼將不能糾正。
互補(bǔ)列之間的錯(cuò)誤也是相互關(guān)聯(lián)的。….當(dāng)兩列互補(bǔ)時(shí)，他們之間的漢明距離也最大。因此列盡量分開(kāi)的條件就是試圖使列既不相同又不互補(bǔ)。
除非分類(lèi)類(lèi)別數(shù)大于等于5，否則同時(shí)滿(mǎn)足上述兩個(gè)條件是很困難的。例如，當(dāng)分類(lèi)類(lèi)別為3時(shí)，僅有8
這8列中，4列與另外4列中還有一列是全0或是全1列，這對(duì)于分類(lèi)時(shí)毫無(wú)作用的。結(jié)果是僅剩下三列可以作為糾錯(cuò)輸出編碼矩陣的列，這與一對(duì)多的編碼數(shù)是一樣的。
通常地，如果是K類(lèi)問(wèn)題，除去互補(bǔ)和全0或全1的列，最多還有2k-1-1列可用，對(duì)于4類(lèi)問(wèn)題，我們能獲得一個(gè)7列輸出編碼矩陣，使得行間的最小漢明距離為4. 對(duì)于5類(lèi)問(wèn)題，我們能獲得一個(gè)15列輸出編碼矩陣，使得行間的最小漢明距離為
文中介紹了四種設(shè)計(jì)糾錯(cuò)輸出編碼的方法：Exhaustive Codes(EC); Column Selection from Exhaustive Code(CSEC); Randomized Hill Climbing; BCH編碼[1,2]選擇哪種設(shè)計(jì)方法由分類(lèi)類(lèi)數(shù)K。
【糾錯(cuò)輸出編碼相關(guān)論文綜述和要點(diǎn)】相關(guān)文章：
2017年論文文獻(xiàn)綜述寫(xiě)作要點(diǎn)及格式05-07
和晨間鍛煉相關(guān)的論文06-18
小學(xué)數(shù)學(xué)特點(diǎn)和趨勢(shì)綜述論文06-23
細(xì)胞的物質(zhì)輸出和輸入11-26
醫(yī)學(xué)論文綜述內(nèi)容要求及綜述范文05-25
部隊(duì)心理教育和疏導(dǎo)工作研究綜述論文06-17
基于GSM紅外報(bào)警系統(tǒng)設(shè)計(jì)和PDU編碼的技術(shù)分析論文04-20
綜述論文范文07-14