§1-1 of “Information Theory, Inference and Learning Algorithms”/David Mackay
通信路符号化問題
この本の最初のトピックは、通信路符号化問題の繰り返しコードである。
通信路問題のタスクは、デジタル信号を送信すると通信路上でランダムなノイズ(ビットフリップ)が起きてしまうので、ノイズが乗った信号から元の信号を復元することである。
「なぜ通信路符号化問題を学ばなくてはいけないのか？はやく機械学習がやりたい!!」
本書では画像の例が用いられている。画像を通信路で送ると、ノイズが乗った画像になる。しかし、人間には何の画像だかわかる。これは、脳による復号処理だと言える。
だから、復号問題は、Machine Inferenceの一種である。
繰り返しコードRnとは、通信t→sにおいて、次のルールでencodingを行うものである。
0→000, 1→111
この信号にノイズが乗るので、受け取り側の信号では2の3乗=8通りすべての可能性がありうる。decodingは次のように行うのが一見正しいように思える。
000/001/010/100→0
111/110/101/011→1
しかし、これは正しいとは限らない。例えば、入力が全て1だとわかっている場合は、次のように復号すべきだ。たとえ000を受け取ったとしても、それは全てのビットがたまたまフリップされたからに過ぎないと考えなければいけない。
000/001/010/100/111/110/101/011→1
これを厳密に表現すると、事前確率P(0)とP(1)、P(0)+P(1)=1の設定によりdecoding方法が変わるということである。具体的に求めたい確率は事後確率P(0|000)～P(0|111)、P(1|000)～P(1|111)である。これはベイズの定理により、
例1)
例えばエラーレートが低く(10%)、元信号も1と0が半々(P(1)=P(0)=0.5)であったら、上の確率は
であるから、000を0に複合するのは自然である。このように、「常識的な結論を定量的に出す」性質から、ベイズ推定はAugumented Common Senceであると言われる。
だから、復号問題は、Bayes Inferenceの一種だとも言える。
復号問題はMachine InferenceでありBayes Inferenceなので、最初のトピックとして適当なのだと言える。
ハードディスクの限界
繰り返し符号化は、ハードディスクで言えば、101…ではなく、111000111…という形式でデータを保存することだから、より多い台数のハードディスクを連結することで、よりエラーレートを下げられる。
通常求められるエラーレートは、10の15乗に1回である。これを実現するには、61台ものハードディスクを連結する必要がある。これではとても実用できない。この問題はどのように解決できるのだろうか？