隠れマルコフモデルで手書き文字学習

PRML13.2にでてくる手書き文字学習の例を実装してみた。すぐ試したい方は解説の下の「試してみよう!」を御覧ください。

手書き文字の学習では、手書き文字のサンプルを入力することでその文字を表現する確率モデルを学習する。
手書き文字の学習の例として文字”2”を学習する場合をみてみよう。図1の上段のように”2”の手書き文字データをたくさん用意し、学習をおこなうと”2”を表す確率モデルが学習される。この確率モデルを用いると、図1の下段のように手書きの”2”を生成することができたり、たくさんの文字の中から”2”を識別することもできる。


図1(PRMLサポートサイトよりDL)

ちょっとだけ解説

では”2”という文字をどのような確率モデルで表現しているか?ここでは隠れマルコフモデルを利用してみる。

隠れマルコフモデルは、(観測者には見えない)状態が前の状態に依存して変化していて、その状態に依存してデータが生成される場合によく用いられるモデルである。隠れマルコフモデルのグラフィカルモデルを図2に表す。

[:W360]
図2(PRMLサポートサイトよりDL)

図2において確率変数Zは観測者が見えない隠れ状態(離散)であり、確率変数Xは状態に依存して生成されるデータを表現している。状態は前の状態にのみ依存し、データは状態に依存して生成されることがみてとれる。

次に、手書き文字を表現する(生成する)確率モデルを隠れマルコフモデルを使って構成する。

まず、観測データについて。図1上段のようなデータをどう表現するかであるが、(PRMLにあるとおり)きまった長さの線分の列で手書き文字を近似し、線分の角度の列でもってデータ”2”を表現する。例えば”2”は↗↗→→↘↘↙↙↙→→こんな感じ。ここでは角度は360度を32分割して離散値としておく。

次に、状態遷移確率 P(z_n|z_{n-1}, A)について。 AはKxKの行列で A_{jk} = p(z_{nk} =1| z_{n-1, j} =1)つまり状態jから状態kへの遷移確率である。(Kは状態数)手書き文字学習では状態変化に対して状態jからは状態jまたは状態j+1へしか変化できないといった制限を加える。

次に、データ生成部分 P(x_n|z_n, \mu)について。データは離散値(32個の角度)であるので、多項分布を用いて表現できる。つまり、 P(x_{n}| z_{n,k} = 1) = \mbox{Multi}(x_n| \mu_k)である。 \Sigma_{j=1}^{32} \mu_{k,j} = 1に注意。

以上でモデルの準備が完了した。あとはデータを集めて、データにフィットするようなモデルパラメータ(ここでは A, \mu)をEMアルゴリズムなどをつかって学習してあげればよい。(ここはPRML参照ってことで省略)

試してみよう!

図1上段のように手書き文字のサンプルを入力すると、図1下段のように学習したモデルから手書き文字を生成してくれるデモアプリです。下の説明を読んでご使用ください。

手書き文字学習デモ

注意:そういえばこのモデルだと一筆書きしか対応できない。


画面の説明

  • 画面左:学習用の手書き文字データ入力フォーム(こっちに学習したい文字を書くと)
  • 画面右:学習したモデルから手書き文字を生成するフォーム(こっちにその文字を生成する)

使い方

  1. 画面左に手書き文字を書く(ミスった場合はclearボタン。画面左だけがクリアされる)
  2. addボタンを押す
  3. 1-2を繰り返し10個くらいは学習用に手書きデータを入力してみる
  4. learnボタンを押し、しばし待つと学習が完了する
  5. generateボタンをなんどか押してみる。画面右に学習された確率モデルから文字が生成される

その他

  • clear allボタンは初期状態にもどす。登録した手書き文字データや学習した確率モデルを消去します。

PNUTS (Yahoo!'s Geo-Replication Service)

PNUTSについてのメモを少々

  • PNUTSはオンラインアクセス用のレコードベースのストレージである。(HDFSのようなバッチ処理をターゲットとしたものと相補関係にある)
  • PNUTSは地理的に離れたところにレプリカをもつ。これによりフロントのインタラクティブなアプリに対し低レイテンシでデータを提供できる。
  • PNUTSは十数カ所程度の地理的に離れたデータセンタ(1カ所につき1000ストレージマシンでペタバイト)の規模までスケールするように作られている。
  • データの書き込み時の同期は、マスターに同期で書きこんだ後クライアントにリターン。その後、非同期にレプリカをもつサーバに通知する。(timeline consistency)
  • ルーズなスキーマのレコードを格納していくかたちで、ところどころカラムの値がなくてもok
  • データはプライマリーキーでHashしてロードバランスすることもできるし、ソートしてレンジクエリがかけられるようにもできる

元ネタ

http://idleprocess.wordpress.com/2009/08/09/yahoos-geo-replication-service-pnuts/