tabateeの日記： winnow

何かに勝利するって話じゃなくて、Computer Science系の話です。

以前のエントリで紹介した論文「Scaling to Very Very Large Corpora for Natural Language Desambiguation」のFigure 1の右の方で最高の性能を出しているWinnowって手法を知らなかったんですが(他の3つは知ってたんですが)、Winnowのわかり易い解説を見つけました。
理論的な方まで追うと他のものよりも大変そうですが、コードを書くレベルでは驚くほど簡単な手法に見えます。
anthyの最近のはMemory basedのclassifierを使ってて、Social IMEとかで使ってるものにはvotingを追加してみたりしてますが、将来に検討するようなことがあればこの辺のアルゴリズムもアリな気もします。

パーセプトロン？

[nokuno (34086)]

パーセプトロンの学習法や最急降下法に似ていますが、
誤差に学習係数をかけて重みに足すのではなく、重み自体をα倍してるんですね。

理論的な解析はたしかに大変そうです。

Re:

[Anonymous Coward]

リンク先の「朱鷺の杜Wiki」の記事を書いたものです． おっしゃるように，パーセプトロンのように勾配を加算するタイプではなく，乗算により重みを更新する点が違います． こうした乗算型の更新や，重み付多数決型のPAC学習での枠組みでの誤差解析を行ったのがLittlestoneの大きな功績で，ブースティングなどの手法にも影響を与えました． 基本文献のLittlestoneの論文には，誤差を保証するためのαなどのパラメータの範囲や学習できる問題について論じられています． コードは，データマイニングツール Weka にも含まれています． 以上，ご参考となればさいわいです．

Re:パーセプトロン？

[tabatee (1637)]

解説ありがとうございます＆Wikiの他の項も楽しく読ませていただいております！
今のところのanthyのサンプル数(数万文節)だと現行のMemory Based+Votingに素性はマニュアルで選択というのはそんなに悪くないと思ってます。
もし、Winnowを使うとすると、変換エンジンがユーザに出した結果が文節の伸縮などを受けたかどうかをもとに、係数を更新していくことでユーザ好みの変換を学習していくなんてのが面白いんじゃないか妄想中です :-)

Naive Bayes

[nokuno (34086)]

そういえば、元の論文ではNaive Bayesもかなりの性能を出していますし、実装も容易ですよね。 コーパスが増えてきたらNaive Bayesも検討してみましょうか。 Anthyの素性の設計がどうなってるか分からないので、独立性を仮定していいのか疑問ですが…

Re:Naive Bayes

[tabatee (1637)]

別のコメントへの返事でもあるんですが、classifierを実用してみた論文とかを見てると、線形分離できないものも混じった入力にlinearなものやlog linearなclassiferを使ったり、素性が独立で無さそうな状況でNaive Bayesを使ってもそれなりにうまくいってるような例を見かけます。(実際、Scalingなんとかの論文 [microsoft.com]のConfusion Set Disambiguationもそうじゃないでしょうか)
結局、入力のどの程度に問題なものが含まれているかに依存してそうで、試してみれば意外といけるかもしれませんね。その前にサンプルを増やしたり、素性(品詞体系)の選択を工夫したりすべきなんでしょうけど…

学習にWinnowを使えば良いかもしれないと書いたのは、係数が最近の正変換や誤変換にフィットして古い情報を忘れていくように調整することで、ユーザの傾向に合った学習機構になるんじゃないかと思ったからですが、実際のところ学習はセコい手でなんとかなってるように感じます。

Re:

[Anonymous Coward]

> 素性が独立で無さそうな状況でNaive Bayesを使ってもそれなりにうまくいってるような例を見かけます。
おっしゃるように，独立でなくてもナイーブベイズでうまく行く場合は多いです．著名な論文として次のものがあります．
フルペーパー： P.Domingos and M.Pazzani, "On The Optimality of The Simple Bayesian Classifier under Zero-One Loss", Machine Learning, vol.29, pp.103-130 (1997)
国際会議：P.Domingos and M.Pazzani, "Beyond Independence: Conditions for The Optimality o The Simple Bayesian Classifier", ICML1996

過去のk個の語か

Re:Naive Bayes

[tabatee (1637)]

色々とありがとうございます。
自分自身は何かタナボタが降ってきでもしない限りanthyの開発をする気のない状況で、余暇にはアセンブラよりlow levelなscript言語処理系なんてのを作って遊んでいる今日この頃ですが、今後、変換エンジンを作ろうとする人には役に立つ議論だと思います。

一応、今のanthyでは、過去のk個の語から次の語を予測ではなくて、k個の単語もしくは文節の列が正変換・誤変換となる確率を考えるようにしています(やる事は一緒ですが)。「確率的言語モデル」に書かれている方法で最大エントロピー法を使っての開発もやってみたのですが、以下の理由で失敗しました。

• 識別モデルではなく確率的言語モデルを使ったため、誤変換に対して不適当な確率が出てしまった
• 当時は例文が数百文しかなかった
• パラメータの収束にかかる時間が長く、仕事から帰って寝るまでの時間で効率的な開発ができなかった(誤変換の傾向を調査する手段がなかった)
• 複数の開発者のコミュニケーションがあんまり機能しなかった

ちょっと頑張ればいくつかの問題は解決しそうな気がするのですが、とりあえず、こんな状況から逃げるためにMemory basedの識別モデルという安易な手に逃げてしまいました。anthyが自分で出した誤変換を負例とし、未知の素性の組み合わせには確率0を出すようにしています。

確かに学習の重いアルゴリズムを変換ごとに使うのは無理なので、そういうのはリリースする人が例文から計算してインストールパッケージに含めるようにし、実行時にはオンラインアルゴリズムの結果と投票で混ぜるのもアリですね。

Re:

[Anonymous Coward]

「朱鷺の杜Wiki」をごらんいただきありがとうございます． Winnow は，基本は線形分離できる問題が対象です．ですので，変換エンジンとかだと苦しいかもしれません． 内部の詳細は存じ上げないのではずしているかもしれませんが，基底関数を導入して非線形化を図るとか，ブースティングなどの弱学習器の投票による方法とかの方が適切なような気がします．