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