誤り訂正出力符号

誤り訂正出力符号 (error correcting output code; ECOC)†

誤り訂正出力符号は，多クラスの分類問題を，2値分類器で解くための手法．

一対他分類器では，\(k-1\)個の，一対一分類器では，\(k(k-1)/2\)個の分類器を学習する．多数の分類器を使うと頑健性は向上するが，多くの計算量が必要になる． \(k-1\)と\(k(k-1)/2\)個の間の個数の分類器で，頑健性と計算量のバランスをとるための手法が誤り訂正出力符号を使った多クラス分類．

クラス＼分類器	1	2	3	4	5	6
A	1	1	1	1	1	1
B	0	0	0	1	1	1
C	0	1	1	1	0	0
D	1	0	1	0	1	0

A〜Dの4クラスの場合に，6個の分類器を使う例．この表は，分類器 1 は，クラスAとDでは1を，クラスBとCでは0を出力することを示す．ここで，各クラスの行を，そのクラスの符号とする．

頑健性を向上させるため，行ベクトルの符号は，Hamming距離で測って互いに離れるようにする．符号長を \(L\) とすると，Hamming距離は \(k\) から \(L-k\) の間にできる．この例ではHamming距離は3か4になっている．同時に，同じ列があってはならず，列の0/1を反転させたものも他の列にあってはならない．という訳で \(k\) が大きいと設計は大変．

分類は，1〜6の分類器の出力の符号と，各クラスの符号を比べHamming距離で一番近いクラスに分類する．例えば，分類器1〜6が 100111 という出力をした場合，クラス A〜D の符号へのHamming距離はそれぞれ，2，1，5，3となり，一番近いクラスBに分類にする．