講演者：堀井 俊佑（早稲田大学）
題 目：メッセージ伝搬アルゴリズムとその応用
日 時：2015年5月29日(金) 18:00-
場 所：早稲田大学西早稲田キャンパス63号館 数学応用数理会議室（102号室）
Ａ：皆さん、お集まりいただきありがとうございます。数理人セミナーのたぶん7回目になると思います。今日は早稲田大学の、僕とドクターを取ったのが一緒ですね。
堀井：ドクター取ったの一緒です。
Ａ：部屋も近かったので、よく廊下で会ってワーッとやってました。堀井さんです。専門は情報理論になるんですか？
堀井：符号理論とかです。
Ａ：符号理論とかですね。その周辺の方ですので、いろいろ楽しいお話を聴けたらいいなと思います。では75分ぐらい、よろしくお願いします。
堀井：よろしくお願いします。ご紹介ありがとうございます。今日はおそらく皆さん初めましてだと思うんですけれども。普段は情報理論関係の学会に参加していて、応用数理学会に機会があれば参加したいと思ってるんですけど、今のところ参加したことがないので。
今日はこういうタイトルで発表をします。『メッセージ伝搬アルゴリズムとその応用』というタイトルです。
具体的にはこんな感じで。最初にメッセージ伝搬アルゴリズムというものをお話しして、その後にその応用として2つ、誤り訂正符号の復号という問題と、あと、圧縮センシングという問題への応用についてお話ししようと思っているんですが。スライドの枚数が全部で54枚となっているので、時間的に全部はお話しできないかもしれないので、お話しできる所までという形にしたいと思います。おそらく皆さんとちょっと専門が違うところの話になるので、もし途中で何か分からないところがあったら聞いていただければありがたいです。
まずは最初に確率推論問題という問題とメッセージ伝搬アルゴリズムというものについてお話をします。
確率推論問題というのを一般的なかたちで書いているんですけれども、確率推論問題ってこういう問題です。今、何か複数の確率変数があって、それの同時確率関数もこういうふうに与えられていて、確率推論問題ってどういう問題かというと、複数ある確率変数の中で一部の変数の値が観測されたという下でこういうものを計算するような問題です。
これは何かというと、周辺確率分布です。n+1からN、これは順番についてはどうでもいいんですけど、一部が与えられているというところがポイントで、一部が与えられていて残りの変数に関して周辺化計算をするような問題です。例えばx1ということでしたら、こういうものを計算することになります。今、これは同時確率がどういう関数かということは分かっているので、与えられた部分に関しては代入をして、それ以外の部分に関してはとり得る値の全ての方法に関して和をとるという計算になっています。
αというのがありますけれども、これは確率にしなくてはいけないので、足したら1になるように正規化するような正規化定数です。これはどういうところに出てくるかというと、例えば簡単な例ですけどこんな問題が考えられる。
今、変数の数が5個あって、x1というのは風邪かどうかを表す確率です。これは0か1と仮定して、x2というのがインフルエンザかどうかを表す確率変数。これも0か1。0だったらインフルエンザじゃなくて、1だったらインフルエンザにかかってるというような確率変数だと考えて。x3が体温、x4という変数が喉の痛みがあるか無いかというのを表す変数で、x5が筋肉痛があるか無いかみたいなのを表す変数だというふうにして。
今、仮定としてこれの同時確率というのは分かっていると仮定をした下で、観測できる現象として体温が37度あります、喉の痛みもあります、筋肉痛もありますといったときに、それが風邪なのかインフルエンザなのかというのを知りたいと思ったらば、こういったものを計算すればよくて。これを計算すれば、37度で喉の痛みがあって筋肉痛があるときに風邪である確率というのを計算すればいい。同じようにインフルエンザである確率みたいなものを計算することができるので、こういったものを計算するというのが確率推論という問題として……。人によって確率推論という問題の定義は違うんですけれど、今日の話の中では、確率推論の問題というのはこういうふうな周辺確率分布を計算する問題と定義したいと思います。
Ｂ：すみません、ちょっと素人質問で申し訳ないんですけど、確率変数のxって包含関係みたいなのがあってもいいんですか？
堀井：包含関係……独立か独立じゃないかということですね。独立じゃなくても大丈夫です。今回の場合ですとx3とx4だとおそらく独立じゃないと思いますので、そういったところには構造があってもいいということです。今はとりあえずそういったところは全部無視して、とりあえず同時密度が与えられているという条件だけを与えています。
これをちょっと書き換えて整理すると、やりたいことって実はもっとシンプルに言うことができます。今、同時確率というのはx1からXNまでの関数なんですけれども、観測された部分に関しては代入してしまいます。ということで、これっていうのは実は観測できない変数に関する関数になっているわけです。x1からxnが観測できないやつです。それの関数が与えられたときに、何か注目する変数以外の全ての変数に関して和を計算する問題です。
これはちょっと書き換えてますけれども、同時確率関数が与えられているんですけれども、観測できてる部分に関しては代入してしまいます。ということで、観測できない変数に関する何か関数だというふうに考えることができて、その関数を、何かある興味が例えばx1であればx1以外の変数に関して全ての候補で和をとるという計算を考えましょうという問題です。
容易に分かることなんですけれども、これをまともに計算しようとするとnの指数オーダーの計算量がかかります。もしxが例えば離散の変数で全部が0、1しかとらないと考えたとしても、例えばn個の変数があって、x1以外の変数に関してとり得る値全てに関して和をとるとなると、x2からxnが全て0、1でn-1個あるので、それの全てのパターンというと2の(n-1)乗あるので、この計算をしようとすると、例えばxが離散のときだったらばnに関して指数オーダーの和計算をしなくてはいけない。一方でxが連続だったときには(n-1)乗の積分計算をしなければいけなくて、それが解的に計算できるケースはまれです。数値計算する時にも(n-1)乗の積分計算って非常に計算量がものすごいことになってしまうということです。
後でこの誤り訂正符号の復号問題というのが実際にこういうふうな問題として表せますよという話をするんですが、誤り訂正符号の復号問題で言ったらば、このときのnがどれぐらいかというとだいたい数千から数万ぐらいのものなので、これをまともに計算しようとしたら無理なんです。
なんですけど、問題としてこの関数に関して何も構造を仮定していないんですけれども、これが何らかの構造を持てば効率的に計算できる場合というのがあります。これはすごい簡単な話で、使っているのは単に分配法則を使ってるだけなんですけれども。
例えばx1からx5の5個の変数の関数fというのが与えられているんですけれども、もし仮にこの関数がこういうふうに因数分解できたとします。5個の関数です。1つ目の関数はx1だけに依存して、2つ目の関数がx2だけに依存して、3つ目の関数はx1、x2、x3に依存してという、こういうかたちの関数の積に因数分解できたとすると。例えばこのときにx1に関して周辺化をするという計算を考えると、この関数のx1以外の変数に関して全ての候補で和をとるという計算を行うんですけれども、もしこれがこういうふうに関数の積のかたちで因数分解できていればx2からx5まで全て和をとるんですけれども、例えばx3、x4という関数はx3とx4にしか依存しないので、それ以外の変数に関して和をとる必要はないわけです。
ちょっと説明すると、これをまずx4に関して和をとってあげれば、それはx3だけの関数になります。最後のfeに関してもx5だけで和をとってあげれば、これはx3の関数になります。だからこれもx3の関数になって、これもx3の関数になるんです。ここの部分の積というのはx1からx3までの関数になってるわけですけれども、先にx4に関してここの部分を先に周辺化してしまえばこれはx3の関数になっているので、ここの部分の関数というのは結局x1とx2とx3だけの関数になっているので、ここの部分に関してはx2とx3だけの周辺化計算をすればいいということになります。
左辺と右辺の計算の仕方で計算量がどれぐらい変わるかと考えると、左のほうというのはx2からx5までを全て同時に周辺化計算しようとすると、Xの要素数の4乗ぐらいのオーダーになるわけですけど、ここの部分で一番かかるのはここの部分の和計算なので、2乗ぐらいのオーダーに計算量を下げることができる。今、ここでx1だけの計算について書きましたけれども、他の変数に関しても同様に計算量を下げて周辺化計算をすることができます。ここまでよろしいですか？
今日のタイトルにもなっているメッセージ伝搬アルゴリズムって何をやっているかというと、今言ったこの計算を全ての変数に関して並列計算をしようという、ただそれだけの話です。今、これはx1だけに関しての和計算をしましたけど、他の変数x2からx5に関しても同じように周辺化計算をするんですけど、そのときに出てくる計算って同じ計算をする部分があるので、そこの部分をまとめて並列にやってしまおうというのが今日のメッセージ伝搬についての基本的なアイデアなんですが。
メッセージ伝搬アルゴリズムの説明の前に、ちょっと準備としてファクターグラフというグラフを紹介します。ファクターグラフは、今の関数の因数分解の構造を表した2部グラフでして、2部グラフなのでノードの種類が2種類あるグラフになっていて、変数ノードと関数ノードという2種類のノードがあって、変数ノードは変数に対応していて関数ノードは関数に対応していて、関数ノードと変数ノード間にエッジがあるようなグラフになっているんですけれども。ある変数がある関数の引数になっているときに、その変数と関数の間にエッジを引いたようなグラフです。
これは先ほどの例ですけれども、例えばfAという関数は引数としてx1だけを引数に持っているので、faという関数ノードとx1という変数ノード間にエッジがつながっている。例えばfcという関数はx1とx2とx3という引数を持つので、fcという関数ノードとx1からx3までの変数ノードがエッジでつながっているようなグラフ。これがファクターグラフです。
このファクターグラフっていうものの上でメッセージ伝搬アルゴリズムっていうのが定義されるんですけれども、ちょっと複雑なんですけれども、いきなりアルゴリズムの説明をしてしまいます。
メッセージ伝搬アルゴリズムといっているんですけれども、ここでは名前をSum-productアルゴリズムという名前を付けています。メッセージ伝搬アルゴリズムといったりSum-productアルゴリズムといったりBelief Propagationといったりして、いろいろな名前が付いてるんですけれども。基本的には全部同じアルゴリズムなんですが、論文で使っている用語に統一して、この論文の中でこのアルゴリズムをSum-productアルゴリズムという名前が付けられているので、Sum-productアルゴリズムと付けてますけれども。
各ノードで、変数ノードと関数ノードで次のような計算をします。メッセージというものを計算するんですけれども、メッセージって何かというと関数です。関数を計算するアルゴリズム。変数ノードと関数ノードで処理が違いまして、変数ノードから関数ノードにメッセージを送る場合、例えばこの変数ノードからこの関数ノードにメッセージを計算するときには、これがメッセージとなってるんですけれど、結局は実は正体はxiの関数です。
xiの関数をどういうふうに計算するかというと、それ以外の関数ノードから同じように計算されたメッセージというのが送られてきます。メッセージは結局xiの関数なんですけれどもxiの関数が送られてくるので、変数ノードから関数ノードへの処理は結構単純で、送られてきた関数の積を計算するというものです。ただし、送り先の関数以外の関数ノードから送られてきた関数・メッセージの積を計算して、送り先に送るという処理を行います。葉ノードのときには「恒等的に1」をするような関数を――これは初期化ですけれども――送ります。
一方で、関数ノードから変数ノードへのメッセージの計算というのはちょっと複雑になります。同じようにメッセージっていってるんですが、関数を送ります。faという関数ノードからxiという変数ノードにメッセージを送ります。メッセージというのは結局xiの関数なんですけれども、関数faからxiへ送るメッセージ。xiの関数というのはちょっと複雑ですが、こういうふうな関数を計算します。
どういう構造になっているかというと、これは自分自身の関数です。自分自身の関数と送られてきたメッセージ・関数の積を計算して、送り先以外の変数に関して周辺化計算をする。ここのカッコの中身というのはfaという関数の引数と同じ引数を持つような関数になっているんですけれども、それを送り先の変数以外の変数に関する周辺化計算をするというのがこの関数ノード処理になります。関数ノードが葉ノードのときには、自分自身の関数そのものを初期メッセージとして送るというアルゴリズムです。
ちょっとややっこしいんですけれども、この処理をやると、先ほどやった周辺化計算をすることができます。ちょっと例を使って説明します。
これは先ほどと同じ例です。こういうふうに因数分解されていて、今、例えばx1に関して周辺化計算をしたいと思ったらば、x1に送られてくるメッセージというのはfaから送られてくるメッセージとfcから送られてくるメッセージの積になります。これです。aから1へ送られてくるメッセージとcから1へ送られてくるメッセージが送られてきます。
まずaから1へ送られてくるメッセージはどういうふうなメッセージが送られてくるかというと、これはfaというノードが葉ノードになっているので、葉ノードのときには関数そのものが出てきます。ですからここに出てくるのはfaという関数がそのまま出てきて。
cから1へ送るメッセージというのはどうなっていたかというと、こういうかたちになっているんですけど。自分自身とcから1へ送るメッセージの計算をしたいんですが、送り先以外の変数ノードから送られてくる、この場合でしたらx2から送られてくるメッセージとx3から送られてくるメッセージの積を計算して、今、送り先がx1なので、x1以外の変数に関して和をとるという処理を行う。
これを帰納的に書いていくと、今度は2からcへ送られてくるメッセージと3からcへ送られてくるメッセージがどんなのかというと、どんどんどんどん先ほどのメッセージの計算ルールに従って計算をしていくと、先ほどのx1の周辺化計算を行ったのと同じ式が出てきます。
ちょっとだけ見ますと、例えば2からcへのメッセージというのが、2からcへ送るメッセージというのはこのdから2へ送られてくるメッセージそのものになって、3からcへ送るメッセージというのはdから3へ送られてくるメッセージとeから3へ送られてくるメッセージの積になります。
今度はdから2へ送るメッセージというのは何かというと、これは葉ノードなので関数そのものが出てきて、dから3へ送るメッセージというのはdそのものと4からdへ送られるものの積を計算して、送り先であるx3以外、つまりx4に関して和計算を行う。
eから3というのはfeと5からeへ送られてくるメッセージの積を計算して、x5に関して周辺化をするというふうなかたちで、最終的にこれをもう一段階計算してあげると、先ほどのここで出てきた式と一致するということが確認できます。
今、x1の周辺化だけを見せましたが、x2からx5に関しても同じように周辺化計算ができるということが分かります。ここまで何かありますか？
Sum-productアルゴリズムを省略してSPアルゴリズムと呼びますが、SPアルゴリズムというのを紹介したんですけれども、SPアルゴリズムで周辺化計算というのが必ず行えるかというとそんなことはなくて、周辺化計算が正確に計算できる条件というのがあります。どういうときに計算できるかというと、ファクターグラフに閉路が存在しない場合のみ正しい周辺化計算ができます。先ほどの例ではこのファクターグラフの中に閉路が無かったので、正しい周辺化計算がSum-productアルゴリズムで計算できたわけです。
では、グラフに閉路が存在する場合はどうか。一般的な問題としてはグラフに閉路が存在しないケースというのがむしろまれで、だいたい問題に依存してファクターグラフっていうのが書かれるんですが、だいたいそのファクターグラフには閉路が存在すると。そういう場合にSPアルゴリズムで周辺化計算ができるかというと、周辺化計算はできない。正しい周辺化計算が行われる保証は無いんですけれども、ただこのアルゴリズムを適用することだけはできるんです。
要は、変数ノードの処理としては送られてきたメッセージを単純に掛け算して送ってあげる、関数ノードから変数ノードでは自分自身と送られてきたメッセージの積を計算して送り先以外の変数に関して周辺化計算をするという、このルールだけを適用することはできる。ただ、周辺化計算はできるという保証は何も無いんですけれども、アルゴリズムを適用することはできます。そういうふうにサイクルがある場合でも先ほどのメッセージ計算を行うアルゴリズムはなぜか別の名前がついているんですけども、Loopy Belief Propagationっていったりします。
閉路が存在するときに先ほどのルールでLoopy Belief Propagationを適用したときに、その性能はどうなっているのか。正しい周辺化計算はできないんですけれども、その場合の性能はどうなっているのかというと、実験的にはうまくいく。そこそこいい値、いい近似計算になってることが多い。ただ、どれぐらいの近似になっているかという保証は全く無いんですけれども、実験的には割と「いいね」ということが多い。
あと、誤り訂正符号の復号とか圧縮センシングの問題というのは、その性能の理論解析をどうやってやったらいいかみたいな研究が盛んに行われています。誤り訂正符号のほうではDensity Evolution――日本語だと「密度発展法」と呼ばれているんですけれども――という解析方法だったりとか、単純に日本語にすると「状態発展」になりますが、圧縮センシングのほうの性能解析ではState Evolutionという性能を解析する手法に関する研究が結構割と最近やられています。Density Evolutionのほうはもう10年ぐらい前からやられているんですけれども、圧縮センシングのほうのState Evolutionに関する研究は割と最近です。ここまでで、とりあえずザッと確率推論の問題とそのアルゴリズムの紹介をしました。
Ｃ：ちょっといいですか？ 実験的にうまくいくというのは周辺化計算が行えるという意味でいいですか？
堀井：そうです。周辺確率というのを求めているわけなんですけれども、正しい周辺確率を求めるているわけではないです。何だかよく分からないけれども、何か計算している。ただその計算結果が、例えば小さいsmall exampleで実験をしてみると、割と正しい周辺化計算したものと近いものになっていると。
Ｃ：実験するというのは、何かサンプルを見て、観測を見たときに同じような分布が出るという……どういう意味で？
堀井：言ってみればそういうことです。例えば……
Ｃ：確率分布を近似するようなことはできますよね、データ分布で。
堀井：できます。
Ｃ：その形が似ている？
堀井：似ている。
Ｃ：なるほど。ちょっと後で話を聞けば分かるというぐらいの気もするけど、「ある」というのは、適用することは閉路があってもできるんですよね？
堀井：できます、できます。
Ｃ：できるという意味は、前のスライドで言うと......とその1個次か、最終的に周辺分布の最後の式がでできますね。そのかたちに式が出てくるという意味なの？ それとも……
堀井：単純に数値として。これが出てくるという意味ではなくて、単純に……。最終的に求めたいのって、例えばx1に関する周辺化をしたいんであれば、出てくる関数ってx1に関する何かの関数ですよね。だから、最終的に何だか正体がよく分からないx1の関数が出てくるっていう意味。
Ｃ：やっぱりあれですね。関数系が具体的に書けるわけじゃなくて……
堀井：書けるわけではないですね。
Ｃ：形を絵で描くことはできるという、そういう話なんですね。
堀井：例えばx1が離散だったらば、0、1であれば0のときはこういう値で1のときはこういう値みたいな、何か関数が出てくるという。
Ｃ：それが「できる」というのは、今のスライドの中だと全然分からなかったんです。
堀井：出てくるというのは……最終的な処理を説明していないんですけど、最終的な処理というのは、サイクルが無いケースでいうと、送られてきた関数の単純な掛け算になってるわけなんですけど。例えばバイナリのケースで言ったら、最終的に何か関数ノードから変数ノードに向かって何か。関数って言ってますけれども、離散だったら要はその値。
例えばこれが0、1をとるような変数だったとしたらば、ここからここに送られてくるのというのは、適当に書きますけれど、今、関数から変数ノードへのメッセージをνという記号を使ってるんですけど、νのaからfというのの、これが送られてくるというだけなんです、数値として。閉じたかたちで関数は送られてくるわけではなくて、その関数の値が送られてくるだけなので、それらを単純に全部。計算しているものは、結局、途中経過も閉じたかたちでは書けないんですけど、これらを全部掛けたものが出てくるという。これを、正しい周辺化をfiと書くとすると、これの近似値とみなしましょうという考え方です。
Ｃ：閉路が無ければ、そこのνに対してまた再帰的にそこでやっているような計算をしていけば最終的にfのかたちで全部書けるけど……
堀井：閉路がある場合に関しては初期化を適当に行います。変数ノードから関数ノードに送るメッセージを初期化して、例えば恒等的に1を出力するような関数に初期化しておいて、関数ノードが葉ノードのときには自分自身の関数そのもので初期化をしておいて、あとはこのルールに従って計算をするっていう。
Ｃ：そのやり方だとすると、なんかループがあったらcontractionというか縮約していって、そういう気がするんですけど、それをやってることになるの？ それとも全然違うの？
堀井：これ、そもそも収束しないケースがあります、このアルゴリズムを適用すると。
Ｃ：それはそうですね。だから、contractionをすると点の中で動き続けるというのが収束しないという対応というか、そんな感じにでもないの？
堀井：あるループの中で、メッセージが例えば反転するような現象がずっと繰り返されてしまったりとか。うまくいってくれればそういったメッセージがだんだん収束していってくれるんですけど、必ずしもそういったことが起こるという保証も無いという、このアルゴリズムは。結構簡単に、すごい小さな例でも収束しない例というのは簡単に作ることはできるんですけれども。
Ｃ：なんかループを3頂点ぐらい、3つあげていけたら。
堀井：単純に一番小さい例で3つですね。こういうグラフを描けばよいので、こんな問題でもこのアルゴリズムが収束しない例というのは作ることができます。ここの関数の収束で、一応、そのアルゴリズムが収束するための条件を出すとかっていう研究もあったりはします。
Ｃ：ありがとうございます。まあ、だいたい。
堀井：ありがとうございます。よろしいですか？
では、ちょっと打って変わって話を誤り訂正符号の話に。誤り訂正符号って皆さんご存じかご存じじゃないかっていうのが分からなかったんで、すごい基本的なところからお話しさせていただくんですけれども。
データの通信とか記録を行う際に、物理現象に伴う雑音によってデータに誤りが生じる場合がある。例えば携帯電話で通信をする時に、他の電波の干渉を受けて送りたい情報が違う信号に変わってしまったりだとか、例えばCDというメディアに情報を記録した時に、CDに傷が付いてその部分が読み取りができなくなってしまったりとかっていうようなことが起こります。通信もしくは記録媒体に情報を書き込む前にあらかじめそのデータというものを符号化しておくことで誤りを訂正するような技術が、誤り訂正符号の技術になります。
簡単な応用例として例えばこんなのもありますということで、QRコードっておそらく皆さんご存じだと思うんですけれども。テキスト情報をバイナリで記録する2次元コードです。ちなみにこのQRコードはこのセミナーのホームページのQR例を載っけておいたので、皆さんの距離からできるかどうか分からないんですけれども、読めばホームページが開けると。
Ａ：あとで買うから。（笑）
堀井：ここで見ていただきたいのは、中央に隠してる部分があるんです。QRコードの部分をあえて隠してるんですけど、ここの部分が隠れていても実際にこれをやってみるとホームページに飛ぶことができます。これは実験で確かめているんですけれども。だいたいこの中の面積のうちの30％ぐらいが見れなかったとしても、たぶん場所にもよると思うんですけれども、正しく読み取ることができるようになっています。それは、この中に誤り訂正の技術が使われているからです。もし学部時代に誤り訂正符号とかを授業で習っている方は、ここで使われているのはReed-Solomon符号という符号です。
誤り訂正符号の中身はどうなっているかというと、こんな感じになっています。送信したい情報をバイナリじゃなくてもいいんですけどとりあえずバイナリで表現しておいて、長さkの0、1の系列で表します。これを情報系列と呼んでいて、長さを伸ばさないと誤りを訂正できないので長さを伸ばします。今、長さnの系列にして、kよりnが大きいという状況です。ただ、このときにも全部の系列を使うわけじゃないのでその部分集合になるわけですけれども、それがc。これが符号。送る候補になるような長さnの系列全部の集合が符号で、その要素を符号語と呼びます。
通信路は、これも流儀があるんですけれども確率モデルとして定義することが多いです。入力に対して出力が確率的に決定されるようなモデルを考える。全体としてはこんなモデルになっていて、長さkの系列がある確率分布p(b)に従って、これは等確率であることを仮定することが多いんですけれども、長さkの系列のどれが出てくるかは事前には分からないので、これが等確率に出てくるという仮定を置きます。長さkの系列が何かある確率に従って等確率に出てきて、符号器では長さnの系列に変換をして、それが通信路を通って符号語とは違うものに変換される。この受け取った系列を基にして元の符号を推定するというのが、一連のこの誤り訂正の流れになります。
ここの通信路のモデルに関してはいろいろとモデルがあるんですけれども、ここでは2つほど紹介します。例えば2元対称通信路、Binary Symmetric ChannelなのでBSCと略されることが多いですけれども、例えば入出力どっちとも0、1で、確率pで0と1が反転するような通信路がこの2元対称通信路、BSCと呼ばれる通信路です。
あとは2元消失通信路、Binary Erasure ChannelでBECと略しますが、要は部分的に信号が読み取れなくなるような状態、0か1を送ったのにどっちか判定できなくなってしまったという。その判定できないことを表すのがこの「？」の文字。「？」じゃなくてもいいんですけど、消失シンボル、何か違うシンボル、0と1以外のシンボルに確率pで変換してしまう、確率pで0と1が消失してしまうというのが、この2元消失通信路という通信路です。
他にもあるんですけれども、とりあえずこの講演の中ではこの2つを主に出していきます。
すごい簡単な例なんですけど結構いろんなところに使われていて、テレビのリモコンとかにも使われているみたいな話を聞いたことがあります。
簡単な符号化・復号の例として反復符号という例で、すごい誰でも思いつく話で、符号化としてはあらかじめ情報記号を何回か繰り返せばいいじゃないかという発想です。奇数回繰り返す、例えば3回繰り返す。010を送りたいとなったときに、あらかじめその010を000111000というふうに全てのシンボルを3回繰り返したものに変換しておく。これが符号語になるわけです。今、kが1でnが3のケースを考えています。これは一つ一つが情報系列で、0に対応する符号語が000で、1に対応する符号語が111で、というような状況です。
通信路を通って確率pで、BSCだとすると0が1に変換されたり1が0に反転したりします。この場合の復号法としては、簡単な復号法として例えば各符号語に対して多数決するというものです。001だったら0が多いから、ここは0だろうと。こっちの部分に関しては1が多いから1だろうというふうにするというのが、割とリーズナブルな――この場合はこれが最適なんですけれども――こういうような復号法というのが考えられます。
これはもちろん復号が誤る可能性もあります。というのは、このケースだったらば、今はたまたま誤っている個数がそれぞれの符号語に関してたかだか1個なのでちゃんと復号できてますけれども、このケースだったら2個以上誤ったら違う符号語に復号してしまいます。一般的に言ったら、q回繰り返すんだったらば、誤りの数が2分のqよりも小さければ正しく復号可能ですけれども、2分のqを超えると復号は誤る、復号失敗ということになります。
そうすると評価基準が出てくるわけですけれども、誤り訂正符号の評価基準は何かというと、まず符号化比率です。今の例で言ったらば、qをどんどん増やしていけば訂正できる誤りの数がどんどん増えていきます。が、例えばCDだったらそのCDの中に書き込める0と1の数はあらかじめ決まっているので、qを増やすということは書き込める情報が少なくなるということになるので、それを表す評価基準がこれです。情報系列kに対して符号長nの比率でレートと言ったりしますけれども、この比率が一つの評価基準です。通信速度だったり記憶容量の効率に関する評価基準になります。q回反復符号の符号化比率は、容易に分かるようにq分の1です。1つのシンボルを送るのに長さがqになっているので、q分の1。
もう一つが、この復号誤り率です。復号がつまりは失敗する確率です。これも2種類の評価基準があるんですけれども、系列単位で見るときにはブロック誤り――各ブロックで見たときに復号結果が元の送信符号と異なる――か、ビット単位で見る、シンボル単位で見る、記号単位で見るような評価基準、これらが評価基準として使われます。これは信頼性の評価に対応します。例えばBSCにおけるq回反復符号のブロック誤り率は解析的に計算することができて、こんな感じになります。要は2分のq以上、通信路で誤りが発生してしまうと復号誤りになってしまうので、これぐらいの誤り確率になるということです。
最後に3つ目が、符号化・復号に掛かる計算量というのが評価基準になります。例えば復号に計算量が掛かるということは元の情報を取り出すのに時間が掛かってしまうということなので、これらも評価基準になります。
これは教科書から図を借りてきてうまく描いている人のを引用したものなんですけれども、先ほどの反復符号の復号性能をグラフ化したものになります。横軸が符号化比率、レートで、縦軸がブロック誤り率になります。例えば通信路で0と1が反転する確率が0.1のときの反復符号の符号化比率とブロック誤り率を描いてます。r1というのは符号化しないということなので、復号を誤る確率は通信路の反転する確率と一緒で0.1です。
反復回数をどんどん増やしていけば誤り率はどんどん減少していくわけですけど、当然、符号化比率も減少していくというわけです。3回繰り返し符号だったらば符号化比率は3分の1、5回だったら5分の1、61だったら61分の1というかたちになります。反復回数を増やせば誤り率は0に近づいていって、その代わり符号化比率も0に近づいていく。
この例だけ見ると、誤り率を0に近づけようとしたら符号化比率を0にしなければいけないと思う人もいると思うんですけれども、実際にはそうではないというのを示した通信路符号化定理というのがあって。
通信路に対して定義される通信路容量というものがあって、符号化比率がその通信路容量Cよりも小さければブロック誤り率を任意に小さくすることができます。
要は、条件としては符号化比率が通信路容量より小さいという条件であれば、ブロック誤り率は任意に小さくすることができます。符号長を無限大にしなければいけないですけれども。符号長無限大でブロック誤り率を任意に小さくできるような符号が存在します。逆に、符号化比率が通信路容量C以上であれば、ブロック誤り率を任意に小さくできるような符号というのは存在しないということも証明しています。
これは一つの限界を示す定理であって、具体的にこういう符号化・復号法をすればいいですよということを示しているわけではないので、それ以来、具体的にこの限界を達成するような方法というのを探しましょうというのが誤り訂正符号の研究の発端になっています。
先ほどの例でいくと、例えばpが――これは計算方法は今回載せていないんですけれども――誤り率が0.1、反転確率が0.1の2元対称通信路の通信路容量Cというのは、これぐらいだということが計算で求めることができます。0.531044。要は、符号化比率がこれよりも小さければブロック誤り率はいくらでも小さくすることができるような符号が存在しますよ、ということを下のが証明しています。
つまりこのグラフでいくと、ここはCとなっているんですけれども、こっち側から右というのはどうやっても無理だと。どうやってもここを達成するような符号化・復号法の組み合わせは存在しないけれども、逆にこちら側は達成できるような符号化・復号法が存在するということを証明したのが今の定理です。反復符号だったらこれぐらいで、このプラスの記号、今日はお話ししないんですけれど、BCH符号という符号だったらばこれぐらいというふうになっているわけですけれども、全然限界にはほど遠い性能であるということが分かる。
ちょっと前まで、10年ぐらい前までは、多項式時間で符号化・復号が可能で通信路容量を達成するような実用的な符号というのは存在しなかったんですけれども、10年ぐらい前からポロポロとそういう方式が出てきています。私が学部の時に誤り訂正の授業を受けた時には「存在しません」と教えられてたんですけれども、最近は別に「通信路容量を達成できます」と言ったところで誰も驚かないというような状態です。
例えば今日は出てこないですけどexpander 符号という符号と線形計画復号法、これは復号法に線形計画を使うという復号法なんですけど。書いてから気づいたんですけど、私はどっちかというと今日お話しするこのSum-product復号に関する研究よりも、こっちの最適化に基づく復号法のほうの研究が実際には自分ではたくさんやっているんですけれども。たぶんこっちはどちらかというとちょっとマニアックで、この業界はたぶんこっちの研究している人がすごいたくさんいるので、今日はちょっとこっちの話をします。
あとはpolar符号、プラス、Successive decordingというのだったり、空間結合というのにちょっと修飾子が付くんですけれども、空間結合LDPC符号、プラス、Sum-product復号。この復号に使われているものが、先ほど紹介したなんだかよく分かんないアルゴリズムです。なんだかよく分からないんですけれども、通信路容量を達成するということは証明できているということになります。
空間結合というのが付いてますけれどもLDPC符号は、実際にはWiMAXやデジタルテレビの衛星通信とかで実用的にも使われている符号です。
空間結合というのは抜けているんですけれども、一般的なLDPC符号の性能はこれぐらいだというふうになっています。これが限界なので、過去の符号に比べたらかなり限界に近づいているということが分かります。ここまで何かありますか？ よろしいですか？
では、LDPC符号の概要なんですけれども、概要を述べるだけだと結構簡単で、準備としてパリティ検査行列というものを導入します。これは符号の満たすべき条件を行列表記したものです。例えば先ほどの3回反復符号の場合、符号語は000か111のどちらかだったわけですけれども、これっていうのは例えばこの2本の方程式で――演算は全部F2上で定義してますけれども――表現することができます。これを行列表現するとこういうふうなかたちで書くことができるんですけど、このときにここに出てくる行列のことを符号のパリティ検査行列と呼びます。
一意には決まらないんですけれども、パリティ検査行列を決定するということが、ニアリーイコール、符号も決定ということになるので、符号を構成するといったときにはだいたいパリティ検査行列をつくる問題と考えて差し支えありません。「ありません」というと語弊があるんですけど。符号を構成するといったときには、この行列をどうやってつくるかという話をみんな考えているということです。
LDPC符号、特に正則LDPC符号というのは、要はこれが単純に疎な行列だというだけです。LDPCって略語、言ってなかったですけどLow-Density Parity-Check codeの略なので、要はこのパリティ検査行列が疎だといってるのがLDPC符号です。パリティ検査行列の各行の1の数を行重みといったり、各列の1の数を列重みといったりしますけれども、そういったものが符号長に比べて全然小さいという定義です。正則といったときには、各行と各列の1の数が等しいLDPC符号のことを正則LDPC符号といいます。
これが先ほどの確率推論の問題とどう関わってくるのかということなんですけど、もう一度、通信路モデルを描いたのがこちらの図になりますけど、こういう問題を考えています。情報系列が等確率に従って出てきて、それを符号化器で符号化して、通信路で確率的な変換を受けたものから符号語を推定するような問題と考えているんですけど。
今、ここの部分が等確率的に出てくるとしているので、小文字にはなっていますけれどもこれは実際には確率変数になっているわけです。情報系列は確率変数です。ということは、それを符号化という関数をかまして出てくる符号語というのも確率変数で、それに対して確率的な変換を受ける受信系列というのも確率変数なので、結局ここに出てくる変数は全部、確率変数。
復号問題というのは、受信系列というのを見ることができるので、ここの部分は見ることができます。これを観測した下でこの符号語の系列を推定する問題だと見ることができるので、これを観測した下でこの確率変数を推定する問題として確率推論の問題として定式化することができるわけです。
では、先ほどのSPアルゴリズムを適用する際に何が分からなければいけないかというと、ここの同時確率の構造が決まればSPアルゴリズムを適用することができます。それを適用した復号法のことをSum-product復号法といいます。
この確率分布はどうなっているかという話なんですけれども、これは一般的な話として同時確率をpxかける(xの下でのy)というふうな条件付き確率の積に分解しまして。pxというのは符号語であれば等確率で出てくる、符号語じゃないやつは出てこないので0という確率として書くことができます。
この式をちょっと書き換えて、こういうかたちの指示関数の積で表します。ここの部分は何かというと、先ほどパリティ検査行列というのを導入しましたが、パリティ検査行列のj行目の制約条件を満たしていたらば1、そうでなければ0をとるような関数。符号語というのはパリティ検査行列の制約式を全て満たしていたときのみ符号語になり得るので、全ての制約条件を満たしているときにここはC分の1になるというようなかたちになっています。
p(y|x)の部分は、ここは通信路のモデルです。今回のケースではここの部分を独立な、各時点で前のシンボルと次の時点のシンボルというのは影響を受けないというような確率モデルを考えると、こういうふうに書くことができます。各時点の条件付き確率の積で表すということです。例えば誤り率pのBSCだったらば、こんなかたちで書くことができるわけです。xiとyiが一緒だったら1-pで、違ったらばpという関数です。
これを全部書き下すと、こんなかたちになります。同時確率はここの部分はpxになっていて、ここの部分はp(y|x)というところです。例えば3回反復符号の場合だったらば、パリティ検査行列はこんなかたちになっていましたので、変数はx1からx3なので、変数ノードはx1からx3まであります。ここの部分がp(y1|x1)、ここは、p(y2|x2)というふうなかたちで、ここの部分は受信信号から計算される関数になっています。
ここの部分は関数ノードなんですけれどもチェックノードといったりします。ここの部分がパリティ検査技術の制約式に対応する部分になります。例えば左側の部分は――ここだけmodを書いてますけれども――F2上でx1+x2=0という制約を表していて、ここの部分の関数がx2+x3=0という制約を表しているという構造になっています。パリティ検査行列とこの変数のチェックノード間の接続関係が1対1に対応するようなかたちです。ここの部分は符号のタナーグラフといったりしますけど、ここの部分がパリティ検査行列から1対1に対応します。なので、慣れてくるとこっち側で見ると、これとこれが同じように見えてくるという感じなんですけど。ここの部分が1行目のx1+x2=0というふうに対応していて、ここの部分がx2+x3=0という関数に対応していると。
いったんファクターグラフが描ければ、先ほどのアルゴリズムを適用することができます。先ほどのアルゴリズムはグラフさえあれば一応アルゴリズムは適用することはできるので、グラフが描けてしまえばアルゴリズムは適用できるわけなので、先ほどのアルゴリズムを適用するとそれがSum-product復号法となります。
ここの部分はかなり省略しちゃってるんですけれども、適当に式展開するとアルゴリズムを簡略化することができます。分かりやすいのでこのあと話を全部、消失通信路に限定して話をさせていただきますけれども、例えば消失通信路のようなケースですと、要は送る関数の値が3種類に限定されるので、その3種類の値だけを送ればいいというかたちになるんです。
変数ノード処理はこういうかたちになります。受け取ったメッセージが全て消失メッセージのときに消失メッセージを送る。ここに「？」というメッセージが送られてきたら、送るメッセージは「？」。もし「？」以外のメッセージが1つでもあったらば、送られてきた「？」以外のメッセージを送るというようなかたちに簡略化することができます。これは、先ほどの変数ノード処理をかなり簡略化するとこうなりますという話なんですけれども。
関数ノード処理のほうは、受け取ったメッセージに消失メッセージが含まれていたらば、消失メッセージを送る。受け取ったメッセージが全て消失以外だったらば、受け取ったメッセージの排他的論理和を送る。
これはどういうことかというとすごい簡単な話で、ここのチェックノードはここの変数を足したら0になりますよという情報を持っているので、例えばここから「自分は1だ」というふうな情報が送られてきて、こっちからは「自分は0だ」という情報が送られてきたらば、「じゃあ」ということでその情報を基にして「あなたは1ですよ」というのを送っていると考える。ただ、1つでも送られてきたメッセージの中に「自分がまだ0か1か分かりません」となっていたらば、他の部分から送られてきても、それを足したら0だという情報から「あなたは何ですよ」と送ることはできないので、それは「すみません、分かりません」というメッセージを送るわけです。
変数ノードのほうは、誰か1人でも「あなたは0です」という情報を送ってきている人がいたんだったらば、その情報を基にして「自分は0なんだ」となって、その情報を送る。0か1が送られてくるんですけれども、1つでも誰かから「あなたは0か1です」というふうな情報が送られてきたら「自分は0か1なんだ」となって、送られてきたメッセージが全部「？」だったら自分自身が分からない、自分が0か1なのかが分からないという状態を表している。
Ｄ：それは0、1、「？」という場合はないんですか？
堀井：それが起こらないというのが証明できます。送られてくるメッセージがconflictするっていうことは起こらない。
これが消失通信路に対するSum-product復号アルゴリズムになります。よくよく考えてみればすごい簡単で、ある種の連立方程式を消去法で解いているようなかたちになります。部分的な変数に関する情報、局所的な情報を基にしていって、解けるところからどんどん0か1を代入していっているというイメージなので、ある意味で連立方程式を単に解いてるだけです、消失通信路の場合は。
結局、実は今回、話はしてないんですけれども、ファクターグラフにサイクルが無い場合は今のアルゴリズムはガウスの消去法を使っているのと同じことになります。
LDPC符号とSum-product復号の誤り率を理論的に求めたいというニーズがあります。でなければ通信路容量を達成できるかどうかということの証明ができないので、誤り率を理論的に求めたいという要求があるんですけれども、少なくとも反復符号、プラス、多数決で復号するみたいなアルゴリズムに比べると断然複雑なので、誤り率を理論的に計算するというのは結構難しい問題です。
これはこの業界独特、情報理論とか符号理論と、あと、たぶん統計力学にちょっと独特な文化だと思うんですけど、ある1つの符号に対する誤り率を計算することはあきらめます。あきらめてどうするかというと、符号の集合を考える。符号のクラスを考えて1つの符号の誤り率を計算するんじゃなくて、符号の集合を考えて、符号のクラスを考えて平均的なふるまいを解析しましょうと。アンサンブル解析といったりします。
ファクターグラフが部分的に木であると仮定して、あるエッジを流れるメッセージの確率分布を求めるというような解析の仕方をします。エッジを流れるメッセージの確率密度がアルゴリズムとともにどう発展していくかというのを見るので、Density Evolution、密度発展法という名前になっています。
どういうような分布を考えるかというと、1つの符号を固定するんじゃなくて符号アンサンブル、符号のクラスというのを考えるんですけれども、例えばこんなかたちの符号アンサンブルというのを考えます。基本的にはファクターグラフを作ることが符号を構成することなので、そのグラフをどう構成するかという話になっているわけなんですけれども。
ここから出てくるやつに関して、これをソケットといってるんですけれども、例えばここには3本のエッジがつながれていてほしいということであれば、行列の列の1の数、列重みが3であるときには、ここから出てくるエッジの数は3と決まっていて、行重みが4であるようなときというのは、こっちから出てくるエッジの数というのは4本というのは決まっているので、とりあえずここから3つ伸ばしておいて、こっちから4つ伸ばしておいて、こことここの間をランダムにつなぐ。
要は、ランダムな置換を考えることと一緒です。これをここにつなぐのか、ここにつなぐのか、ここにつなぐのかというのをランダムに考えて、全ての順列パターンを考えた符号に対する確率分布みたいなものを考えようと。グラフが1個決まると誤り率というのが決まるので、この作り方で決まる誤り率全部の平均を計算しましょうという考え方です。
ここからはかなり省略して書いているので、本当に概要なんですけれども。どうやって計算するかというと、実はあるエッジを流れるメッセージがどうなっているかというのを求めるのが、このグラフが木だったらば、例えばそこを頂点として展開していったグラフがもし木であれば、このメッセージがどういう確率で消失メッセージになるかというのを計算することは簡単にできます。
例えば受信した時に、一番最初の初期化メッセージが消失である確率というのは通信路で消失が発生する確率なので、ある所で流れるメッセージが一番最初に消失である確率というのは確率pになります。
次に、あるチェックノードから変数ノードに送るメッセージが消失になる確率というのはどうなるかというと、こうなります。チェックノードから変数ノードに送るメッセージというのが消失じゃないときというのはどういうときかというと、送られてくるメッセージが全部消失じゃないときだけ送るメッセージは消失じゃなくなります。つまり、ここの1本1本が消失でない確率は1-pなので、例えばこれは3つありますけど、この3つのメッセージが全て消失じゃない確率は(1-p)の3乗なので、このメッセージが消失になる確率はそれを1から引いてあげて、こういう確率になると。
変数からチェックノードへ送るメッセージが消失になる確率というのはどうなるかというと、ちょっと複雑なんですけれども、変数ノードからチェックノードへ送るメッセージというのは、1つでもこの中に消失メッセージがあったらここからここに送るメッセージは消失になるので、ここに今2本ありますけれども、これの2乗。これが消失である確率はこれなので、これを2乗した確率。あと、自分自身が受け取るメッセージが消失である確率もあるので、これにpを掛けたものというかたちで。こういうふうに帰納的に、もしこのグラフが木だったらば、こういうかたちで誤り確率を計算することができます。
そういうふうにして帰納的に計算したのが、この場合の密度発展方程式となります。初期化としてこういうふうに1というふうに計算しておいて。要は繰り返し回数ごとに、グラフの中に流れているメッセージが消失メッセージになっている確率というのを計算していることになります。
ただよくよく考えると、先ほどから「グラフがもし木だったらば、こういうふうに計算できます」と仮定をしているんですけれども、実際には木にならないわけです。なんですけど、ここがちょっとアンサンブル解析のうまいところで、先ほどの符号のアンサンブル、符号のクラスでというのを考えると、部分的にグラフを描いたときにそこの部分が木にならない確率というのが符号長を伸ばしていくと0に収束しますよということが証明されています。木だと仮定した下で解析をしてかまわないというのを証明したのがこのRichardsonなんですけれども。
ここはだいぶ端折った説明になってますけど、いわば、1つの符号に対する性能解析はあきらめてアンサンブルに対する解析としたことによって、木だと仮定した下での解析ができるというのがこの解析方法のうまいところかなと思います。
この方程式に関してどういうふうにメッセージ誤り率が変化していくかというのを見ると、いろいろパラメータがありますけれども、例えばパリティ検査行列の行重みが6、列重みが3で、通信路で消失が起こる確率が0.4の場合に、最初は0.4なんですけど、繰り返し回数を増やしていくとメッセージが消失になる確率はどんどん減っていきます。
消失確率が0.42の場合はこうなるんですけれども
0.43になってくるとこれは0に収束しません。つまり、何回繰り返しても消失メッセージが残ったまんまになってしまうということになります。つまり何があるかというと、ここの間に何かしきい値があるということです。0.42の所と0.43の所の間のどこかに、誤り率が0にいくようなpと、誤り率が0にいかないようなpというのが存在するということが分かります。
先ほどの密度発展方程式の不動点解析をすると、通信路の消失確率pがいくつ以下だったら復号誤り率を0に近づけるかというのが分かります。そうやって求めたのをBPしきい値と呼んでいます。先ほどの例だったら0.429いくつ、いくつ、いくつ……0.42だったらうまくいって、0.43だったらうまくいかないんですけど、もうちょっと詳しくやっていくと0.429うんたらかんたらという値が出てきます。
消失確率pの消失通信路の通信路容量は1-pであるということを証明することができます。ですから、例えば0.43だったら消失通信路の通信路容量は0.57ですけれども、この場合だったらば0.429よりも誤り率が多くなってしまうと誤り率を0にできないので、この正則なLDPC符号での通信路容量を達成するということは残念ながら言えないんですけれども、最近の符号構成とかを考えると、例えば2011年ぐらいに証明されているのだと、こういった符号のクラスというのを考えると、今の解析方法で通信路容量を達成することが数値的に証明できますということが言われています。この辺になってくるとちょっと解析方法が複雑になってきますけれども、ポテンシャル関数を使った解析が有効だったりします。
だいぶザッと流しちゃいましたけれども、符号理論への応用のまとめとしてはこんな感じです。符号の復号問題は確率理論の問題と見ることができて、LDPC符号に対してSum-productアルゴリズムを用いて復号を適用するといい性能が得られますよということです。あとは、それを解析する方法として、Density Evolutionという解析方法があります。また、こういった方法で限界を達成するということが証明可能な符号というのが存在しますということが言えたとします。
BECの場合のDensity Evolutionは結構簡単に導けるんですけれども、これがBSCとか他の通信路になってくると、こういう発展方程式を導くのは少し難しくなります。が、一応、いろんな通信路に対してこういった密度発展方程式というのが導かれています。
ここまでで何か、後半だいぶ飛ばしてしまったんですけど、何か質問とかあったら。
Ｄ：さっきの繰り返し回数というのは、1回分の全部伝搬するプロセスというのがあって、それを何度もやるということですね。
堀井：そうですね、はい。フラグ全体で1回、全てのノードで計算をしたときにそれが1回というふうにカウントしています。
堀井：いいですか。あと、あまり時間が無いので、圧縮センシングのほうは途中までお話をしようかと。これ、何時まで？
Ａ：一応7時半ぐらいですね。7時半ぐらいまでの感じでだいたいお願いします。
堀井：これはたぶん途中まで、問題設定の紹介ぐらい。圧縮センシングってちなみにご存じの方っていらっしゃ……いらっしゃいますね。ご存じの方にとってはつまんない話になりますが。
問題は、こっちのほうが問題はシンプルに書くことができます。長さがnの系列xというのがあって、それにm×n行列を掛けるんですけれども、mがnより小さいという状況を考えて。それを掛けた系列がyとして観測されるということです。この行列で変換されたyを観測した下でこの元信号xを推定しましょうという、ただ単純にこれだけの問題です。この観測行列が既知、分かっているということです。
今、nが行数が列数よりも少ないという状況を仮定しているので、何の仮定も無ければこのxを一意に復元することはできません。が、仮定としてxが疎であるということが分かっていれば、その疎性を利用して解を導くことができますということです。応用としては、MRIとか通信とか機械学習とかいろんなところに応用されています。ただ単純にこれだけの話です。
どういうときに復元ができるか。当然ですけれども、観測行列、ここでいったらΦがどういう性質を持っているかというのが復元可能かどうかの鍵を握っているわけですけれども。それに対して例えば行列に対してRIP定数（制約等長性定数）というのがあって、これが大きければ大きいほど復元できますよという話なんですけれども。
これはどういう定義になっているかというと、ちょっと説明が難しいんですけれども、行列のある列を指定してあげるとその部分行列というのができるわけですけれども、その部分行列というのがどれぐらい……要はベクトルに掛けたときに長さを変えるわけですけれども、それをやるときにその長さができるだけ変わらないようにしたい。そのときに長さがどれぐらい変わるかというのを表しているのが、このδというやつです。行列の部分行列というのが正規直交系にどれぐらい近いかというのを示すような指標が、このRIP定数という指標になっています。
ちょっと式はややっこしいんですけれども。これはSが1からnに対して定義されるんですけれども、S以下、それ以下のインデックスの集合Tに対して、長さtの任意のベクトルに対して、これを満たすようなδの中で最小の実数というのがその行列のRIP定数と呼ばれるものです。これが定義です。
例えば、こういったことが証明されています。これはあえて名前を出してますけど、Cand`es and Taoとなってますが、Taoというのは2006年のフィールズ賞受賞者のTao。疎性を表すのがこのtで、0でない部分の位置というのをtとしたときに、そこの部分というのがS以下で、そのSに対してδ2Sに対するRIP定数が1より小さければ、こういう計算をすることによってxを一意に復元することができますよという定理です。
今、xを推定したいんですけど、xに関してはこういうような制約条件が分かっている。Φに関してのyになるということが分かっているので、そういうものの中で最も疎であるような解を出力しなさいと。これはL0なのでノルムじゃないんですけれども、0じゃない位置の個数。Φx=yを満たすようなxの中で非0要素が最も少ない解を出力しなさいという最適化問題を解いてあげると、もしこういう条件を満たしているんだったらば、元信号xが一意に復元できますという定理です。ただこれが残念なのは、この問題自体、NP困難なので普通は解くことはできないと。
対して、L1ノルムで変えたもののやつというのをやってあげると、ちょっと性能が悪くなりますけれども、こういう条件を満たしていれば、要はL0じゃなくて、Φを掛けたときにyになるという条件の下でL1ノルムを最小化するという問題を解いてあげると、その解というのは元信号xに一致しますということが、同じ論文ですけれども証明されています。先ほどの問題と違ってこっちの問題は線形計画問題として定式化できるので、Nに対して――Nというのは元信号の長さですけれども――多項式オーダーで解くことができる。
RIP定数の小さい行列をどうやって作るかという問題があるんですけれども、そもそも実はRIP定数の評価自体が計算量的に困難で、やっぱりここでも先ほどの符号理論と同じようなかたちでランダム行列のアンサンブルというのが出てきます。これもやっぱり同じ論文で、行列の各要素を正規分布に従って派生させると、高い確率でRIP定数は先ほどの条件を満たします。√2-1よりも小さくなりますというようなことが証明されています。僕も1回読んだんですけど、よく分かんなかったです。『ランダム行列の固有値の漸近分布』と書いてあるんですが、結構難しかったです。結構前に読んだんで、ちょっと覚えてないんですけど。
ということなので、要は観測行列というのを正規分布に従ってランダムに派生させればこういう性質を満たすので、それを使ってL1最適化をすれば元信号が復元できますよというところまで証明がされているということです。
ここまでの話は先ほどのメッセージ伝搬アルゴリズムに全く関係ないんですけど、何が出てくるかというと、L1復元は線形計画問題なので――nが小文字になったり大文字になったりしますけれども――、要は信号の長さの多項式オーダーで実行可能なんですけれども、実際の問題ではnが数千とか数万とかあるので、これに対して単体法とか内点法をやるのはちょっと重たいということで、このL1復元を行うためのアルゴリズムに関する研究が盛んに行われています。
いろいろあるんですけど、そのうちの一つとして先ほどのメッセージ伝搬アルゴリズムを使ったものというのがありますということです。ただ、今のところ問題の中では全く確率的要素は出てきてない。メッセージ伝搬アルゴリズムは確率推論に対するアルゴリズムなのに、問題の中には確率的要素は一切出てきていないんですけれども、
信号xに対して仮想的にこういう確率分布を考えます。
これは何をやっているかというと、これは制約条件を表しているやつですけれども、yはy=Φxという関係があるので、行列の各行に対する制約条件を積の形でばらしているかたちなんですけど、要はy=Φxという条件を満たしていたら1、そうでなかったら0という制約条件をこれで表していて、ここの部分というのはL1ノルムのふうに対応しているわけなんですけれども。
こういうような確率分布を考えてあげると、これってどういうところに確率を持つかというと、ここの部分で制約条件を満たしていたらば1、そうでなかったら0というような関数が入っているので、結局、この最適化問題の実行可能解の所だけに確率測度が集中している、確率測度を持っているというような確率分布になっていて。なおかつ、これはβって0より大きい正のパラメータなんですけれども、βというのはどんどん大きくしていくとpxというのがある一点に確率密度が集中していって、結局、この最適化問題の最適解周辺に確率密度が集中していくような仮想的な確率分布になっているというわけです。
なので、これでちょっと確率的な要素を作り出してあげて、この確率分布に対して先ほどのSum-productアルゴリズムを適用してあげようというようなかたちでやってあげると、メッセージ伝搬型のアルゴリズムが適用できるということです。
ファクターグラフはこんな感じのグラフになります。下のほうが制約条件の部分を表している関数で、こっちの部分が観測信号に対する関数を表しているやつです。
Ｄ：その解ってβに依存するんですか？
堀井：最終的にはβを無限大の極限に飛ばすので、βに依存しないかたちになります。もちろん、この状態だったらβに依存します。周辺確率もβに依存するんですけど、後でアルゴリズムに導くときにβは無限大に飛ばすということをやります。
先ほどのSum-productアルゴリズムを適用してあげるとこういう更新式が出てくるんですけれども、今回の場合とLDPC符号の復号の場合の問題で最大の違いは、そもそもこの計算ができないだろうということです。先ほどの例と違ってここの部分がすごい密な形になっているので、そもそもこの計算ができないという問題があります。メッセージの計算が解析的にできない。そもそもSum-productアルゴリズム自体が近似のアルゴリズムなんですけれども、そもそもその近似計算すらできない。
何をやっているかというと、極限を考えて、中心極限定理とかを使ってSum-productアルゴリズムをさらに近似するというようなことをやっています。Message Passingの近似なのでApproximate Message PassingでAMPというアルゴリズムになっていて、情報理論分野だと割と今、流行っていると言っていいかどうか分かんないんですけど、一時期ちょっと流行った。
アルゴリズムを書くとこんな感じで書くことができて。
その解析方法としてのファクターグラフは密なグラフなのでLDPC符号みたいな解析はできなくて、統計力学分野の話が流入されてきてState Evolutionというのが解析方法として出てきました。
Density Evolutionと同じような感じで、こっちのMessage Passingに関しても解析手法が出てきたという感じです。
圧縮センシングの問題のL1復元問題自体は線形計画問題なんですけれども、仮想的に確率推論の問題と見なしてしまって、Sum-productアルゴリズムの近似みたいなのをやってあげる。いろいろと近似の近似になってしまって、そんなんでうまくいくのかと思うんですけれども、たぶん最初の頃は「やってみたらばうまくいった」という話だったと思うんです。「やってみたらうまくいった？ じゃあ、なんでうまくいくんだろう？」というところで、いろんな人が頑張って性能解析手法を導いたという感じです。
もともと統計力学の人がやっていて、レプリカ法とかという数学的には厳密に証明されてないような手法を使って証明していたんですけれど、最近はそれが数学的に厳密に性能解析されたという経緯があります。たぶんそれはこっちの統計力学系のほうで研究が進んだんだと思うんですけど。
ザッとですが、まとめに入ります。
メッセージ伝搬アルゴリズムは誤り訂正符号とか圧縮センシングにおいて有効です。特にこれらの分野では割と理論解析も手法も研究されているということです。特にアルゴリズムを適用するというだけだと結構いろんな場面に応用されていて、たぶん一番このアルゴリズムが有名なのがこの辺かなと私は思っているんですけれども。画像復元をやったりとか、あとは医療システム。最初に出した例のような感じなんですけれども、症状からその患者がどういう病気であるかを推定するみたいなところで結構使われてたりします。
圧縮センシング以外にも、一見、確率推論の問題じゃないような問題に対しても単に最適化アルゴリズムとして有効な場合もあるので、もしかしたらこういったところがまた新しい応用みたいなのが出てくるかもしれないなと考えています。以上です。
Ａ：ありがとうございました。何か質問、ご意見等ありましたらお願いします。
Ｅ：最後のほうに出てきたAMPだと100万とかのオーダーの問題でも実用的には動く？
堀井：AMPアルゴリズムの計算量がだいたい……これがAMPアルゴリズムなんですけど基本的に行列の計算だけでできるので、だいたいオーダーとしては行列のm×nぐらいのオーダーで計算ができるので、適用できるという話です。
Ｅ：1反復毎にm×nのオーダー？
堀井：そうですね。1反復がm×nのオーダーで。
Ｄ：これを繰り返していくんですよね？
堀井：これを繰り返すというかたちになります。
Ｄ：ですので、全列の収束回数として考えられてる？
堀井：考えられると。
Ｄ：それは解に向かう途中は制約はハードに満たしている状態なんですか？ それとも満たしていない状態で最終的に満たすようなかたち？
堀井：このアルゴリズムは途中でもハードに満たすことは要請していないので、たぶん制約条件は崩れていると思います。最終的に一致するっていう感じかな。ちょっと分かんないです。たぶん……どうなんだろう？
Ｄ：スレッショルディングしてそれを……
堀井：ここの部分の項がなければ毎回の更新でその条件を満たすようなかたちでの更新になってるんですけれども、この項の影響がわけ分かんないんですぐに答えられないんですけど。
Ｄ：その項はADMMとかモーメントみたいなそういうなニュアンスがあるんですか？
堀井：そうなんです。この問題に対して先ほどのL1復元に対してADMMを適用すると、すごい似たかたちのアルゴリズムが出てくるんです。すごい似てるんですけど、微妙に違うんです。
Ｄ：計算上的にはそれと似たような？
堀井：似たような計算になります。ADMM……
Ｃ：そっちに出てきた射影勾配法というのは、これとは違うんですか？
堀井：似てるんです。ある意味、射影勾配みたいなのになっているので、ここの部分が射影になっているので。要はここの部分に勾配みたいな意味があるわけではなくて……
Ｄ：逆じゃないですか？ そっちが勾配の役割になってて、射影はその制約へのプロジェクションになってないですか？
堀井：そうですね。ここの部分で処理に掛けているので、ここの部分が射影。
Ｄ：勾配のほうじゃない？ だから射影勾配ですよ。勾配が伝えないからたぶん近接作用素として見て、Forward-Backward splittingのかたちにするとそういう感じになったりする。違ってるのは、なんで？
堀井：あれ？ どっちがどっちか分かんなくなっちゃいましたけど、要はアルゴリズム的には射影勾配法とほとんど同じようなアルゴリズムになるんですけど、AMPでは特にアルゴリズムの導出の中には勾配のようなものは出てこないということです。あくまで先ほどのメッセージパッシングの近似としてこのアルゴリズムは出てきているので。
Ｄ：スレッショルディングしてるということは、L1ノルムのMoreau envelopeをとったものと勾配と一致しているんですけど、それが勾配という意味？
堀井：そうですね。こっちが勾配ですね。すみません、そうです。
Ｃ：いいですか？ 解はガウシアンを仮定してましたっけ？
堀井：φはガウシアンとしてます。
Ｃ：そこは結構言い切れるもんなんですか？ ランダム行列の固有値がキーになってくるとかだと、あんまりガウシアンじゃなくてもそれなりに分散は合ってたような気がするんですけれど。
堀井：この証明が現段階ではガウシアンじゃないと証明できないというかたちになっています。もともとCand`esとTaoの証明のところだと、別にガウシアンじゃなくても例えばフーリエ変換の行列の一部分をとってくるみたいなやつでも満たしますみたいな証明になってたんですけど、こっちの部分はまだそこまで証明ができていなくて、そこの条件を緩められるかどうかというのは今やられてるんじゃないかと思います、僕はやってないんですけど。
Ｃ：なんかアルゴリズム的に変えなきゃいけないんですかね、途中で。キーのかたちとかは関係あるのかな？
堀井：アルゴリズムはたぶん変わらないと思うんですが。
Ｃ：変わらないんですかね。
堀井：じゃないかなと思っているんですけど。たぶん単純に解析方法の問題。
Ｃ：解析方法のね。
堀井：そんな気がする。ちょっと分かんないです。個人的には先ほどのADMMとかの関係性とかのほうが結構興味があるんですけど。やっぱりよく分からないです、出てくるアルゴリズムが。ただ、出てくる結果が非常に近いというのがちょっと面白いなと思って。
今日はちょっと話さなかったんですけど、先ほどのLDPC符号の復号のほうでもADMMを使って復号するとかという研究はあって、僕はどっちかというとそっちのほうの研究をやっているんですけど。でもやっぱり似たようなアルゴリズムなので、その辺の関係性は面白いかと思ってます。
Ａ：他に何かありますか？
そしたら、いったんこれで終わらせて、またこの後もし時間があれば少しお話をするようにしましょう。どうもありがとうございました。（拍手）
堀井：ありがとうございました。