Hatena::ブログ(Diary)

Topics Related to Computers and NLP

2013-05-19

パーセプトロンを実装してみた

実装力を磨くためと学習器への理解を深めるために、パーセプトロンを実装してみた。3時間ぐらいかかった。今のレベルはSVM赤本に行く前ぐらいのレベル。

コードは以下にある。以下で参考にしたチュートリアル擬似コードをそのまま実装した。
https://github.com/akkikiki/nlp_tutorial/blob/master/train_perceptron.py

以下のチュートリアルを参考にした。詳しい事はこちらに書いてあるが、概要を述べてみる。
パーセプトロンアルゴリズムと文書分類

ちなみに、自分は昨年の春ぐらいにPRML4章(パーセプトロン含む)を輪読会で発表したのだが、完全に忘れていたうえ、読んだ時も機械学習の全体像(識別関数、生成モデル、識別モデルから成る)が掴めていなかったので、いきなりPRMLを読むのはオススメしない。
今PRML4.1.7節を見たら「すごい、わかりやすい!」と思うけど、直前のフィッシャーの識別関数あたりで全体力を消費して、命からがら、パーセプトロンを読んだ覚えがあるので、全然わからなかった。

以下パーセプトロンの概要である。

オンライン学習器である

すなわち、一つの学習事例に対して、重みを更新していく
更新式は


w = w + y *¥eta*¥phi(x)

φ(x)は入力データxの素性で、yは識別結果である。また、η>0は学習率と呼ばれる。
ηの値は「更新時にどのくらいの大きさで、重みを更新するか」である。ちなみにパーセプトロンは収束定理があり、対象データが線形分離可能ならば、どんな学習率でも収束が保証されているため*1、学習率は大抵1である。自分のコード(チュートリアル)でもそうした。

識別結果yは-1か1である

この制限により、学習データと比較した時に識別結果が間違っていた場合、重みが識別結果の符号に引っ張られる。イメージとしてはPRML、図4.7a(http://research.microsoft.com/en-us/um/people/cmbishop/PRML/prmlfigs-jpg/Figure4.7a.jpg)である。黒い矢印がwで赤い矢印で、緑色の丸に囲まれた点が、誤って識別されたため、点(赤いベクトル)の方へ境界を引っ張る。

識別関数である

echizen_tmさんのブログを読んでいて、気付いた。確率ないのは面倒でなくイイネ!

以下雑記

http://gihyo.jp/dev/serial/01/machine-learning/0017はnumpyを使ってパーセプトロンを実装しているので、今度やってみる。

ちなみにSVMパーセプトロンを発展させたもので、

パーセプトロンに導入した学習器である。Sequential Minimal Optimization(SMO)等により高次元のデータに対しても学習が早い、とかの特徴がある。

自分の実装で気を付けるべき、と思った点も述べてみる。

  • 疑似コードから書くこと
  • 全体像(大枠)を書き、詳しい処理は適当な関数の名前を付けて、後で詳細を書く。

当たり前のことだけど、複雑なアルゴリズムほど脳内だけでは処理仕切れなくなる。そして、つまずき、実装を諦める、と言った場合が自分の経験上多い。
疑似コードを書いておくと「ここ何を処理したいんだっけ?」と詰まった場合でも、確認して前に進める。

2013-05-14

日本語入力を支える技術がすごい分かり易い

p196, 5.5節あたりの話である。

何で条件付き確率を定義する時に指数関数を使っているのか?

PRMLの4章を読んでいた際に謎として残っていたのが、「何故、確率を定義する時に指数関数(softmax function)を使っているのか?」である。うろ覚えの人工知能論の授業では「微分可能にするため」として納得していたが、この本を読んでみてしっくりきた。

指数関数を使う理由:

  1. 確率を扱いたいため、出力値を0以上にする必要がある
  2. 確率を扱いたいため、全ての背反事象に対する確率の総和を1にする必要がある(参考:http://d.hatena.ne.jp/nowokay/20120214)
  3. (これは自分の推測かつ、あまり必要ない)微分可能にする必要がある

結局重みの更新式を算出する際に偏微分する必要があるから、「微分可能にするため」も理由の一つであると推測する。しかし、劣微分あたりの話で「微分不可能な項に対する対処」をする必要があるので、あまり必要ないかな。

以下雑記

  1. 連想配列の実装に対してトライ木を使う、という発想はなかった。言われてみれば、確かにそうなんだけど、言われなければ気が付かなかった。
  2. NLPベイズの定理が用いられる例として、機械翻訳の例がよくあるけど、かな漢字変換の例も取り入られた方がわかり易いと思う。例えば日本語から英語に翻訳する際に、英語から日本語に翻訳される確率を用いていると「あれ、それって同じ問題をあらかじめ解かれているってこと?」と疑問が湧いた(あれは、バイリンガルコーパスを使用しているからだけど)。かな漢字変換をする際に、「変換候補である漢字の読み方yが入力されたかな列xである確率 P(x|y)」と「変換された文字列が日本語らしい確率 P(y)」を考慮に入れることの方が理解しやすい(読み推定とかな漢字変換は違う、という私見に基づく)。
  3. p171あたりの劣微分、劣勾配に関する話は「L1正則化の際に、正則化項は微分不可能。どうやって偏微分するの?」という疑問を当然思うべきであったのに頭になかったので、目から鱗だった。

まだ読み終わってないので、多分続く。

日本語入力を支える技術 ?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

日本語入力を支える技術 ?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)