2013/12/31

ノンパラメトリック平均場近似と確率伝播法の提案

2013年も残り少なくなってきました.そこで,今回は研究の締めくくりとして,今年のCVPRで発表した論文について紹介したいと思います.

僕の研究は,大雑把に言うとグラフィカルモデルの最適化手法に関するものです.本研究の貢献を簡単にまとめると,次のようになります.

  • グラフィカルモデル内の確率変数が連続的である場合,計算上の理由から,変分ベイズ法ならびに確率伝播法で扱える分布のモデルには制限があります.提案手法を使うことで,非指数型の分布族に関しても変分ベイズ法を効率的に適用できるようになりました.
  • さらに,同様の議論を確率伝播法にも適用することで,確率伝播法をノンパラメトリックに扱うこともできるようになりました.

実際の論文では対象のグラフィカルモデルを一階のマルコフ確率場に限定していますが,変分ベイズ法などの別の領域にも容易に適用できます.また,議論を簡単にするため実際の論文では確率変数の離散化を焦点に当てた形で書いていますが,その流れに沿って書いてもあまり面白く無いので,ここではどのような過程でこのような研究に取り組んだのか簡単に書いていきたいと思います.

グラフィカルモデルは機械学習の多くの分野で使われてきた確率モデルです.この確率モデルを用いて対象の問題を高精度に解くためには,確率変数の周辺化が重要となってきます.周辺化の計算を直接行うことは困難であるため,大きく分けて2つの方法論で周辺分布を近似的に求めることが一般的です.一つはギブスサンプリングに代表される,大量のサンプルをばらまいてモンテカルロ的に推定解を求める方法,もう1つは平均場近似(変分ベイズ法)や確率伝播法に代表される,変分原理に基づいた近似的推論法を使う方法です.後者は得られる推定解の精度が比較的悪いものの,特定の反復方程式に従って周辺分布を更新するだけで良いため,高速に周辺分布の推定解が求められる利点を持ちます.本研究は後者の推定手法に関するものです.

変分原理に基づいた周辺分布の反復計算は,グラフィカルモデル内の確率変数が連続的であるか離散的であるかで異なります.変数が連続的である場合,周辺分布の密度関数は少数のパラメータからなるパラメトリックな連続分布として表現されます.そして,平均場近似,確率伝播法の両方とも,実際の最適化には変分原理に従って導出された特定の反復方程式に従って,対象のパラメータを更新していきます.しかしながら,このような更新は更新後の分布が更新前の分布と同じパラメータで表現される必要があるため,扱える分布モデルの範囲は非常に限られていました.以上の背景から,僕は平均場近似ならびに確率伝播法をノンパラメトリックに扱えるような方法論を新しく提案すれば,良いインパクトになるのではないかと考えました.

このような元々の平均場近似や確率伝播法では扱えない分布をどうにかして扱えるよう拡張できないだろうかという要望は多く,これまでにいくつかの試みが提案されています.これらの試みはすべて次の混合分布の仮定を下にしています.すなわち,平均場近似や確率伝播法で扱う近似分布やメッセージを,次の混合ガウス分布で仮定することです.

もし上の仮定の下で混合ガウス分布のパラメータに関する反復方程式を導出できたのであれば,対象のグラフィカルモデルがどのような分布であったとしても平均場近似や確率伝播法を適用できる.つまり,平均場近似や確率伝播法の可能性を一気に広げることができます.

しかし,このアイデアを直接適用してもあまり上手くいかないことが知られていました.なぜなら,変分原理は計算の段階で混合ガウス分布のエントロピーを計算する必要があるためです.混合ガウス分布のエントロピーは計算困難であるため,このままでは反復方程式を解析的に導出できません.

このような問題に対応するための方法として,これまで大きく分けて2つのアプローチが提案されてきました.1つは解析解を出すために,混合分布のエントロピーにJensenの不等式を用いてさらなる近似を行い,解析解を求める方法です[3].しかしながら,この方法論は平均場近似や確率伝播法で導入した近似分布の他に,さらなる近似をおくことになります.もう1つはモンテカルロ法を用いて,混合ガウス分布のパラメータの反復解を力技で求める方法です[1][2].しかしながら,この方法論ではサンプル数に依存せず高速に推定解を求められる,確率伝播法の利点を失うことになります.

これ以外にエントロピーの計算をどうにかして解決できないだろうかと思い,思考を巡らせました.前述の通り,そもそもの問題は混合ガウス分布のエントロピーが計算困難であることでした.ガウス分布の裾が別のガウス分布に干渉してしまうため,それぞれ独立した分布として扱うことができないのです.そうであれば,最初の出発点に混合ガウス分布を選ぶのではなく,互いに干渉しない別の分布を選べば良いのではないでしょうか?例えばヒストグラムのような,互いに干渉せず,エントロピーが容易に計算できる混合矩形分布を採用するのは?

ここで,hは変数iにおける,s番目の矩形分布を表します.本研究で新しく提案したアイデアは基本的にはこれだけです.この矩形分布の位置とサイズは,重なっていなければ変数空間のどの箇所に配置しても構いません.すなわち,この表現を用いて変数空間の重要な箇所を密に離散化し,重要でない箇所を疎に離散化することもできます.さらに,変数毎に配置する矩形分布の個数は異なっていても構いません.すなわち,変数の重要性に従って,変数の離散化の度合いを変えることもできます. 

次に,上の表現を用いて本来の連続的な最適化問題をパラメータαの最適化問題へ変換し,パラメータに関する反復方程式を導出しました.詳しくは言及しませんが,最終的に導出した反復方程式の形は対象の変数が離散的な場合の平均場近似,確率伝播法の形と非常に似通っています.唯一の違いはエネルギー関数に加わる補正項の存在です.この補正項は変数空間の離散化の「非一様性」を補正する役割をもちます.すなわち,提案手法によって,グラフィカルモデルの連続的な変数空間を非一様に離散化し,ノンパラメトリックに扱えるようになったのです.

以上,急ぎですが本研究の解説記事を書かせていただきました.興味を持っていただけた方は,次のURLからダウンロードしていただければ幸いです.

http://www.vision.is.tohoku.ac.jp/index.php/download_file/view/35/177/167/

参考文献
[1] A. Ihler et. al., Particle Belief Propagation, AISTATS, 2009
[2] E. B. Sudderth et. al., Nonparametric Belief Propagation, CVPR, 2003
[3] S. J. Gershman et. al., Nonparametric Variational Inference, ICML, 2012

2013/11/30

ビットコインの知られざる技術的魅力とその可能性


概要

ご存知の通り,ビットコイン(Bitcoin)と呼ばれる謎の仮想通貨が今世界中で大きな話題を呼んでいる.日本においてもその流れは例外でないものの,その話題の殆どがネガティブなイメージ(リンデンドルやチューリップの球根など)とともに報道されることが多い.しかしながら,これらの報道によってビットコインをただの投機先の一つと断定することは早計である.ビットコインがもつ本当の魅力は値段ではない.本当の魅力はビットコインの背後に隠れた優れたアイデアと,その可能性にある.本記事では,一般に語られるビットコインの値動きではなく,これまであまり知られていない,ビットコインが持つ別の可能性について簡単に紹介する.

なお,本記事は読者が,ビットコインやネットワークに関する初歩的な知識を持つものとして話を進める.ビットコインについての概要はビットコインとは?,もしくはbitcoins.comが詳しい.また余談ではあるが,はじめてビットコインの概要を知った方がもつ典型的な疑問や疑惑のほとんどは,Bitcoin wikiMythsの項で詳しく言及されている.興味がある方はそちらを参照されたい.

イントロダクション

技術的な詳細を省くと,一般のユーザにとって,ビットコインは円やドルなどの従来の法定通貨には無い4つの利点があることが知られている.

  • 世界中の何処からでも送金できる.国境による制約を受けない.
  • 通貨の偽造が非常に困難であることが数学的に保証されている. 
  • 銀行口座は決して凍結されない.
  • 誰に対しても非常に安い手数料で送金できる.

しかしながら,これらの利点は日本にいる一般的な消費者にとってあまり魅力的でない.偽札が氾濫し投資行動も制限されている現在の中国では,決して偽造できず,世界中に送金できるビットコインは大きな利点がある.その一方,日本の大多数の消費者は海外送金には興味がなく,日本円の価値も揺るぎないものと信じられている.中国と比較して,日本でビットコインが相対的にあまり話題にならない理由の一つはそれらの違いにあると考えられる.

だが,現在一般に知られる上の利点は,ビットコインがもつ多くの性質のごく一部にすぎない.事実,ビットコインのプロトコルは送金処理だけでなく,借用証やエスクロー,株式取引にも応用できることが分かっている.特に,ビットコインのプロトコルを利用して,株取引や物品の売買などをすべてビットコインのネットワーク上で実現しようと試みる,BitcoinX (Colored Coins)と呼ばれる取り組みがある.以降はこれらの機能に焦点を当てて説明する.

ビットコインネットワーク

ビットコインは中央管理が存在しない,P2Pのデジタル通貨である.ビットコインを使うことで,ユーザは自分が持つウォレットのビットコインを,他のユーザのウォレットへ送金できる.「アドレス」「送金」などの用語から,ビットコインが行っている処理はまるでAliceがBobにメールを送信しているかのようにビットコインのデータを直接送っているように見えるが,その実体は大きく異なる.

ビットコインの実体は巨大なP2Pの分散型データベースである.例えば,AliceがCarolから貰った1 BTCを,Bobに送金する場合を考える.この場合ビットコインが行っている処理は,AliceがBobに対して1 BTCのデータを何かの形で送信しているのではない.実際は,Aliceがビットコインネットワークの全体に対して,「AliceがCarolから貰った1 BTCのうち,1 BTCをBobに送金する」という内容のトランザクションを宣言している.次に,ビットコインの参加者はこの宣言を検証して矛盾がないことを確認し,分散型データベースに対象のトランザクションを記入する.二重払いなどの矛盾がある場合は,単にそのトランザクションは無視される.分散型データベースに記入されているのはAliceやBobの口座残高ではなく,「XがYから貰ったM BTCのうち,N BTCをZに送金する」といったトランザクションの集合である.

興味深いことに,このトランザクションの内容は表現力を持ったスクリプト言語で記述されている.これは,トランザクションに書き込める内容は送金処理といった単純な取引だけでなく,より複雑な取引にも対応できることを意味する.Contractsではその具体例としてデポジット,エスクロー取引,保証契約にも応用できると提案している.トランザクションの内容は誰もが見られる形で保存されるため,契約書の内容は決して偽造されない.そしてこのスクリプト言語を別の形で利用することで,ビットコインを実際の資産売買や権利譲渡にも応用しようとする取り組みがBitcoinX,またはColored Coin(色をつけたコイン)と呼ばれるプロジェクトである.

BitcoinX (Colored Coins)

BitcoinX (またはColored Coins)はトランザクションのスクリプトを利用して,特定のビットコインにビットコイン以外の価値―例えば債権やコモディティなど―を結びつけるプロジェクトである.この別の価値を結びつける行為のことを,発案者は「色をつける(Colored)」と表現している.BitcoinXを使うことで,ユーザはビットコインの送金と同じ感覚で,安全かつ確実に資産の受け渡しや売買を行える.

クリスマスコンサートのチケットを例に説明する.Aliceは有名なクラシックコンサートの主催者で,チケットをビットコインでも発売したいと考えている.この場合,AliceはまずBitcoinXを使って特定のビットコインに「色をつける」.例えば,あるコインには「2013年12月24日 六本木クリスマスコンサート A-20席」,もう一方のコインには「2013年12月24日 六本木クリスマスコンサート S-3席」といった色である.色をつけるビットコインの額自体は少額で構わない.これは原価の安いただの紙切れが,コンサートの入場権という価値を持つことで高い値段が付けられる現象と似ている.ビットコインに色をつける行為自体は誰でもできるものの,誰が色を付けたのかという署名も一緒に記入される.この署名の偽造が困難であることは数学的に保証されているので,攻撃者によるチケットの偽造も同様に困難である.

次に,Aliceはこの色のついたビットコインを販売して,多数の顧客に送信する.顧客が入場の際に行う操作は,単にこの色がついたコインを携帯のウォレットに入れ,入場口の端末にかざすだけでよい.なぜなら,分散型データベースにはこの色のついたコインが最終的にどのウォレットに入っているのか,誰もが見られる形で記録されているためである.

ここで,顧客の一人であるBobは急な仕事でコンサートへ行けなくなったため,手持ちのチケット(色のついたコイン)を売却したい場合を考える.このとき,Bobはチケットを購入したい第三者を見つけ,スクリプトを利用したエスクロー取引で安全にビットコインとチケットを交換する.このとき実際に行われるのはビットコインネットワークを使用したビットコインの交換だけであるので,手数料は非常に安く抑えられる(詳細はContractsを参照されたい).

このアイデアは単純だが幅広い応用が考えられる.例えば債権の売買や,オークション,株式の発行などである.これまで,ユーザはこのような取引を安全に行うために,国や企業などの仲介者に対して多額の手数料を払う必要があった.BitcoinXを使用した場合,ユーザはこのような手数料を払う必要はない.かつ,これらの取引は誰もが見られる形で公開されるため,偽造などの不正は困難である.

さらにこのアイデアを発展させて,特定のビットコインと実際の通貨を結びつけることができる.ここで,ある企業が特定のコインに「100円」という色をつけたとする.このコインを実際にその企業の店頭に持ち込めば,100円と交換してもらうことができる.すなわち,このコインは100円の価値を持つ(この色をつけるBTCの額は,市場で取引される日本円の価格と対応していないことに注意されたい.すなわち,色をつけるBTCの額は,コンサートチケットと同様に少額で構わない).結果として,日本円はビットコインと同じような形で流通させることができるようになり,かつその流通にかかる手数料は非常に安く抑えられる.もちろん,ドル,ユーロ,ウォンなどの他の通貨も,同様の手続きでビットコインネットワークに流通できる.もはやビットコインは仮想通貨をやりとりするためだけの存在ではなくなった,ビットコインは仲介者が存在せずとも,安全かつ確実にあらゆる取引を遂行するためのプラットフォームにも成り得るのだ.

まとめ

ビットコインはよくバブルと共に語られることが多いが,ビットコインの本当の魅力は値段でなく,その背後にある技術と可能性である.その可能性の一部として,本記事ではビットコインを介したエクスロー取引や,資産取引の具体例について説明した.ビットコインを使うことで,ユーザはあらゆる取引を,仲介手数料を殆ど取られることなく安全かつ確実に遂行できる.

現在,BitcoinXは実際のBitcoinクライアントには統合されていない,開発途中のプロジェクトである.この開発を積極的に進め,将来的にはモバイルなどの端末機器でも使えるようにすることが求められる.また,課税問題やマネーロンダリングなどといった,解決すべき法的課題も多い.しかしながら,将来的にはこれらの懸念は段階的に解決されるであろうと考えられる.ビットコインはあらゆるトランザクションが公開されるプラットフォームであるため,将来的にはむしろ,従来よりも透明性の高い資産取引とその課税ができるようになるだろう.

ビットコインの未来は誰にも分からない.しかし,匿名のエンジニア―Satoshi Nakamoto―が発表したこのアイデアが画期的であることは疑いようがない.たとえビットコインの価格が崩壊しその価値を失ったとしても,この先進的な技術を他の分野へ応用することは重要であると考えている.

2013/04/26

条件付き確率場の推論と学習

条件付き確率場の推論と学習 from Masaki Saito

 前回の研究室ゼミで話した,条件付き確率場についての簡単な紹介スライドを公開します.内容は基本的なPairwise CRFについての話と,それが実際にどのような問題に対して応用がなされているか,またもっとも使われる最適化手法の一つである,平均場近似と確率伝搬法についての簡単な解説と,CRFの初歩的な学習法といった流れです.

補足:
 CRFの学習は自然言語処理など他の分野でもよく使われている学習法なのでおそらく知っている方は多いと思うのですが,普通はダイレクトに対数尤度を最大化することでパラメータを求めています.しかし,今回はKL距離という確率分布間の近さを図る指標を用いて対数尤度を拡張し,パラメータを求めています.なぜわざわざそうするのかというと,だいたいの最適化手法がKL距離の最小化という議論に帰着できて,すっきりするからです.KL距離を使えば平均場近似,確率伝搬法,最尤推定,あと時間の都合上話せなかったTRWやGeneralized Belief Propagationなどの最適化手法がすべて統一的に理解できます.これによって覚えることが少なくなって楽できるだけでなく,このKL距離を使った新しい最適化手法を提案することもできます.

2013/04/25

近況報告

お久しぶりです.細々とした近況はTwitterに書いているのですが,あくまでTwitterはつぶやきであって,記事でない.定期的に自分の中でまとめた内容をブログに吐き出す必要がありますね.
  1. 修士論文を提出し,晴れて今年度から博士後期課程の1年生です.不安が全くないと言えば嘘になりますが,それでも毎日好きなことを学び,研究できる環境は非常に楽しい.みなさんもぜひ博士課程に進学しましょう.唯一不満に思うところは頻繁に書類を書く業務が入るあたりですが,仕方のないことです.
  2. 後できちんとした内容を書きますが,2013年のCVPR(コンピュータビジョンのトップカンファレンス)に採択されました.去年を含めると今回で2回目の採択ですが,前回と異なるのが,今回はポスターではなくオーラルセッションでの採択というところです.オーラルセッションは非常に狭き門(採択率 60/1870 = 3.2%)でありますので,そのような研究成果を得られたことは非常に嬉しいですし,来年もぜひ通しておきたいところです.
  3. 博士後期課程になりましたので,これからは本名メインで活動していきます.プロフィール画像も更新しました.前に使ってた画像は高校時代からのものでしたから,大体7年位使っていたんでしょうか.というかこのブログ,今年で7年目になるのですね.
  4. 自身の宣伝もかねて,論文やコードなどはこれから作る自己紹介のページにて積極的に公開していきます.論文についてはできるだけ読んでもらえるよう,簡単な解説も記事にしていきたいと思っております.