どこまで直せるか

友だちに1枚の絵を送ります。左が送った絵、右が届いた絵です。同じものを送り続けているのに、右は送るたびに違う汚れ方をします。

絵は白と黒だけでできていて、白を0、黒を1として、32×32＝1024ビットを順番に送っています。

では、絵はどこで汚れたのでしょうか。汚れたのは、絵が通っていった道すじの途中です。この道すじのことを通信路といいます。

通信路は0と1しか運べません。そして運んでいる途中で、ときどき0が1に、1が0に化けます。0が1に化ける確率と、1が0に化ける確率が同じだとみなしたものを二元対称通信路（BSC）といいます。誤り訂正符号の話は、だいたいこの1枚の図から始まります。

いま使っているスマホの中でも、机の上のパソコンの中でも、同じことが起きています。ビットが裏返るのは、宇宙探査機のような遠い場所だけで起きる事故ではありません。身のまわりの3か所を見てみます。

誤りを直したいとき、まず思いつくのは「同じものを何回も送る」でしょう。1ビットを3回ずつ送って、届いた3つの多数決を取ります。1回くらい裏返っても、残り2つが正しければ勝ちます。

同じ1024ビットの絵を、3倍にしないで、それでも直せるようにできないでしょうか。

ここからは、4ビットの情報を送ります。そのまま送ると4ビット、3回くり返すと12ビット。その中間の7ビットで送ってみます。増やすのは3ビットだけです。

4ビットの情報 d1 d2 d3 d4 はそのまま送り、うしろに検査ビット p1 p2 p3 を3つ足して7ビットにします。検査ビットは、選んだデータビットの排他的論理和（XOR。1の個数が奇数なら1、偶数なら0）です。この「どのデータビットを見るか」を決める表のことを、講義ではパリティ検査行列と呼びます。

4ビットの情報は16通りあるので、送られる7ビットの並び（符号語）も16通りできます。7ビットの並びは全部で128通りありますから、そのうち16通りだけを「使ってよい並び」として選んだことになります。

それぞれの検査ビットが、どのデータビットを見るかを決めてください。チェックした分のXORが、その検査ビットになります。

設計を考えるのをやめて、128通りの中から16通りをくじ引きで選んだらどうなるでしょうか。

同じ7ビットの枠で、きちんと構成された符号です。検査ビットの作り方は次の3行で決まっています。

7ビットを受け取った側は、使ってよい16個の符号語すべてと見比べて、いちばん近いものに直します。ここでいう近さは、何ビット違うかです。これをハミング距離といい、いちばん近い符号語に決める復号のしかたを限界距離復号といいます。

符号語どうしが遠く離れていれば、1ビットくらい汚れても、いちばん近いのは元の符号語のままです。近くに別の符号語があると、あっさり取り違えます。符号語の間のいちばん狭いすき間を最小距離 d と呼び、必ず直せる誤りの個数は t = ⌊(d−1)/2⌋ になります（講義の定理2）。

「必ず」と書いてあることに注意してください。t個を超える誤りでも、運がよければ直ります。下の表の成功率がtだけで決まらないのはそのためです。

この割合は、16通りの情報と128通りの誤りかたをすべて数え上げて計算した正確な値です。試行回数による揺れはありません。

上の数字は計算で出したものです。いま設定した確率のまま、実際に何度も送って数えてみます。回数を増やすほど、上の表の値に近づいていきます。

① 同じ7ビットなのに、ハミング符号だけ成績が抜けています。ランダム符号も、うまくいかない自作符号も、送っているビット数はハミング符号とまったく同じ7ビットです。差がついたのは量ではありません。16個の符号語をどこに置いたかだけです。

② 繰り返し3回は強いけれど、12ビット必要です。ハミング符号は7ビットで、そのすぐうしろまで迫ります。 強さだけを見て比べても意味がありません。かかるコストと一緒に見ないと、比較になりません。

③ 数字を体感に直すと、こうなります。

STEP2で見た差は、この図1枚で説明がつきます。使ってよい符号語のまわりに、半径tの縄張りを描きます。届いた7ビットがどこかの縄張りの中に落ちれば、その中心に直せます。

符号語どうしの距離が3以上あれば、半径1の縄張りが重なりません。だから1ビットの誤りは必ず直せます。距離が2しかないと、1ビットずれた点が両方の縄張りに入ってしまい、どちらか決められません。距離が1なら、もう隣が別の符号語です。

だから t = ⌊(d−1)/2⌋ なのです。距離dのすき間に、半径tの縄張りを両側から2つ入れて、まだ重ならない最大のtがこれです。STEP2で自分が動かした数字は、この縄張りの重なり具合を見ていたことになります。

でたらめに選んだ符号は、STEP2でさんざんな結果でした。16個をくじ引きで選ぶと、ほぼ必ずどこか2つが隣どうし（距離1）になってしまうからです。7ビットの世界は128通りしかなく、そこに16個も置けば、ぶつかるのが当たり前です。

ただし、これは「長さ7では通用しない」という話であって、「でたらめは駄目だ」という話ではありません。符号語を長くしていくと、でたらめに選んだ符号のほうが、むしろ良い性能を持つようになります。1948年にシャノンが示した通信路符号化定理は、おおよそ次のことを言っています。

つまり、長くすればでたらめでも強くなります。ただし長い符号には別の困りごとがあります。届いた列といちばん近い符号語を探す手間が、とてつもなく増えるのです。このページのように16個と見比べるだけなら一瞬ですが、実用の符号では符号語の数が桁違いに大きくなります。構成のうまさは、性能のためというより、現実的な時間で復号するためにあるという見方もできます。いまスマホで使われているLDPC符号は、その両方をうまく満たした符号です。

ここからが本題です。10種類の動物を当てるAIを作るとします。作り方のひとつは、はい／いいえで答える判定器をたくさん並べることです。「体が大きい？」「泳ぐ？」「毛がある？」——こういう質問にそれぞれ答える小さなAIを15個用意して、その答えの並びから動物を当てます。

判定器はときどき間違えます。写真が暗ければ「毛がある？」を読み違えます。1個でも間違えたら答えが変わってしまう作りだと、まるで使えません。

でも、その「はい／いいえ」15個の並びは、0と1が15個並んだもの——つまり符号語です。

だから、10種類の動物に割り当てる15ビットを、たがいに遠く離して置けばいいのです。下の表がその割り当てで、どの2つの動物をとっても15個中8個が違うように作ってあります。最小距離8、つまり t = ⌊7/2⌋ = 3。判定器が3個まで間違えても、正しい動物に戻ります。

◯が「はい」、・が「いいえ」。列が15個の判定器、行が10種類の動物です。

そして、ここからが研究になります。通信路の符号は「1ビットが裏返る確率はどれも同じ」という前提で設計されています。ところがAIの判定器は事情が違います。「泳ぐ？」は当てやすく、「かしこい？」は当てにくい。判定器ごとに間違えやすさが違い、しかも似た質問どうしは一緒に間違えます。通信路の教科書どおりの符号が、そのまま最適とはかぎりません。

どんな符号語を割り当てれば、間違いやすさの偏った判定器の集まりから、いちばん正確に答えを引き出せるか。判定器の自信の度合い（どれくらい「はい」寄りか）まで使って復号するとどうなるか。これが、この研究室で進めているECOCの研究です。STEP2で4096通りの中から当たりを探したのと、やっていることは地続きです。探す相手が、通信路からAIに変わっただけです。

前に触るとよいのは どこまで縮むか。同じ情報理論の話で、こちらは「短くする」側です。短くするのと、壊れないようにするのは、表と裏の関係にあります。

次に進む → なら 戻せないかけ算 へ。ここでは壊れた0と1を元に戻しましたが、あちらは逆に、鍵を持たない人には戻せないように作ります。同じ0と1の置きかえでも、戻せることを目指すか、戻せないことを目指すかが反対向きです。

ほかの系列からは 質問で分ける木。はい／いいえの質問を並べて答えにたどりつく、という考え方そのものを動かせます。あちらは質問を1本の木につなぎ、ECOCは質問の答えを符号語として束ねて読みます。