糾錯輸出編碼相關論文綜述和要點
糾錯輸出編碼相關論文綜述和要點
糾錯輸出編碼相關論文綜述和要點
糾錯輸出編碼（ECOC）綜述和基本原理 目錄
<機器學習導論> ....................................................................................................................... 1
《Solving Multiclass Learning Problems via Error-Correcting Output Codes》 ....................... 2
A Subspace to ECOC .................................................................................................................. 3
中文參考文獻 ........................................................................................................................... 5
<機器學習導論>
在糾錯輸出編碼中，主要的分類任務透過由基學習器實現的一組子任務來定義。其思想是：將一個類從其他類區分開來的原始任務可能是一個困難的問題。作為替代，我們定義一組簡單的分類問題，每個專注於原始任務的一個方面，並透過組合這些簡單的分類器來得到最終的分類器。
這時，基分類器是輸出為-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類的樣本區分開。同時M(, 3)也決定了如何構造基分類器h3的訓練樣本集T3：所有標記為C2類及C3類的樣本形成正樣本 3 ，而標記為C1類的例項構成負樣本 3 ，對h3的訓練應使得 xi T3，當xi 3 時，h3(xi) 1；當xi 3 時，h3(xi) 1。
這樣，編碼矩陣使得我們可以用二分類問題定義多分類問題，並且這是一種適用於任意可以實現二分基學習器的學習演算法的方法，例如，線性或多層感知器，決策樹或初始定義的兩類問題的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的行業儘可能的不相同，使得在一個活多個基學習器失效時，可以獲得最大的糾錯。 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維二值矩陣為糾錯輸出編碼矩陣。矩陣的列數即為編碼的長度，矩陣的行數即為多分類問題的分類類數。矩陣中的每行M(r,·)表示一個類別的碼文。
對於K類問題，一個好的糾錯輸出編碼矩陣應該滿足兩個要求：
糾錯輸出編碼相關論文綜述和要點
一是行儘量分開。即每個類別的碼文與其它類別的碼文間的漢明距離要儘可能大。
二是列儘量分開。每個基學習器決策函式hi應該與其餘的基學習器決策函式hj，j不等於i，是相互獨立的。這可以透過強調列i和其餘列之間的漢明距離要大以及列i與其它列的補之間的距離要大來獲得。
編碼的糾錯輸能力與行間漢明距離直接相關。而列間漢民距離需要大的目的還不明確。如果兩列列i和列j十分相似或完全一樣，那麼基學習器的判決函式hi和hj的決策結果會含有相同的錯誤。僅當錯誤出現在不同的編碼位置時，糾錯輸出編碼才是有效的，所以不同位置同時出現的錯誤的機會必須少。當同時出現錯誤較多時，糾錯碼將不能糾正。
互補列之間的錯誤也是相互關聯的。….當兩列互補時，他們之間的漢明距離也最大。因此列儘量分開的條件就是試圖使列既不相同又不互補。
除非分類類別數大於等於5，否則同時滿足上述兩個條件是很困難的。例如，當分類類別為3時，僅有8
這8列中，4列與另外4列中還有一列是全0或是全1列，這對於分類時毫無作用的。結果是僅剩下三列可以作為糾錯輸出編碼矩陣的列，這與一對多的編碼數是一樣的。
通常地，如果是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]選擇哪種設計方法由分類類數K。