Perceptron の実装です、と言ってからずいぶん経ってしまいましたが、ようやくその続き……と思わせておいて、実はブログの移転のお知らせです。
サイボウズグループ全体の技術ブログとして Cybozu Inside Out が立ち上がり、こちらの "nakatani @ cybozu labs" で書いていたような記事も今後そちらで書かせていただくことになりました。
第１回目の記事として、Perceptron の実装編として、O.Henry と Edgar Allan Poe の文章を Perceptron で学習して正しく見分けられるか！？ という記事を書かせていただきましたので、よろしければごらんください。
コンピュータはオー・ヘンリーとエドガー・アラン・ポーの文章を見分けられるか？ - Cybozu Inside Out
サイトは変わりますが、これからも引き続きよろしくお願いいたします。
なお、こちらのブログにある過去記事については、このまま保持される予定です。
Perceptron の実装とか見ると、ものすごく簡単なので、本当にこれで学習できちゃうの？ と不安になってしまいました(苦笑)。
こういうときは、実際にパーセプトロンが計算しているとおりに、紙と鉛筆で計算してみて、期待する結果が出てくることを確認してみたくなります。
参照する教科書は「パターン認識と機械学習・上」(PRML) の「 4.1.7 パーセプトロンアルゴリズム」。
短い節です。必要最低限のことを一通り書いてある感じかな。
計算に用いるサンプルですが、手で計算できる規模でないといけないので、論理演算の AND を試してみることにします。
ちゃんとした説明は PRML などを見て欲しいですが、とても簡単にまとめます。
２値の線形識別モデルは、N 次元空間内を (N-1) 次元の超平面(決定面)で分割することで、入力ベクトル x から得られる特徴ベクトル φ(x) が２つのクラスのどちらに属するかを分類します(２次元で言えば、座標平面を直線で分割している感じ)。
その超平面は重みベクトル w を使って、 w^T φ(x) = 0 と表します。
空間を w^T φ(x) ≧ 0 と w^T φ(x) < 0 に分割するわけですね。
重みベクトル w を決定する一般的なアプローチは、誤差関数を決め、それを w の関数と見なし、最小化する w を求める、となります。
パーセプトロンは、誤差関数としてパーセプトロン基準を用い、また最小化に確率的最急降下アルゴリズムを用いるのが特徴、と。
パーセプトロン基準は、目的変数として t ∈ {-1, +1} を用いつつ(通常は {0, 1})、誤差関数を次のように定義しています。
E_P(w) = - Σ w^T Φ(x_n) t_n
ここで Σは誤分類されたパターン全体を走るとします。
すると、w^T Φ(x_n) ≧ 0 のとき t_n は「間違って」 -1 になっているし、w^T Φ(x_n) < 0 のときは t_n は「間違って」 +1 になっているため、E_P(w) は常に０以上であることがわかります。
これを最小化するために、「誤分類された x_n １つずつに対して」次の式を使って逐次的に最小値に近づけていきます。
イメージとしては、ニュートン法(多次元版)って感じです。
このあたり、PRML には 3.1.3 節を見ろ、と書いてますが、5.2.4 節もあわせて見るといいかもしれません。
w^(γ+1) = w^(γ) - η▽E_P(w) = w^(γ) + φ(x_n) t_n
ややこしそうに書いてますが、アバウトにぶっちゃけると「ハズレのときは、そのハズレが出てしまった特徴ベクトルを重みベクトルに足すか引くかする」ということです。
こんな方法では最小値に本当に近づくのかどうか必ずしもわからないんですが、「解が存在する場合は」この計算を有限回繰り返すことで解が得られます、というのが「パーセプトロンの収束定理」で、Perceptron のキモです。
ね、ほんとにそんなんでうまく学習できるんですか？ という気になるでしょう。
論理演算 AND とは……は、さすがに略。
AND の入力ベクトルと目的変数は次のようになります(ベクトルは転置した状態で記述します)。
x_0 = (0, 0), t_0 = -1 x_1 = (1, 0), t_1 = -1 x_2 = (0, 1), t_2 = -1 x_3 = (1, 1), t_3 = +1
これを学習できるのか、手で計算してみましょう。
特徴関数 φ は x_n そのままでもいいんですが、「φ_0 はバイアスでしょ、jk」と PRML にもあるので、次のように定義します。
φ( x_0 ) = (1, 0, 0) φ( x_1 ) = (1, 1, 0) φ( x_2 ) = (1, 0, 1) φ( x_3 ) = (1, 1, 1)
これより重みベクトル w も３次元、初期値は w^(0) = (0, 0, 0) となります。
さて、ここから計算していきますが、誤分類ベクトルは本来ランダムに選ぶべきところ、ここでは少々恣意的に選んでいくことにします(理由は後述)。
■Step 1
x_0 は w^T Φ(x_0) = 0 ≧ 0 となり t_0 = -1 と合致しません。
よって、「次の w 」は次の式で求まります。
w^(1) = w^(0) + φ(x_0) t_0 = (0, 0, 0) - (1, 0, 0) = (-1, 0, 0)
ますます不安……この調子で大丈夫？
■Step 2
x_3 は w^T Φ(x_3) = -1 + 0 + 0 < 0 となり t_3 = +1 と合致しません。よってw^(2) = w^(1) + φ(x_3) t_3 = (-1, 0, 0) + (1, 1, 1) = (0, 1, 1)
■Step 3
x_1 は w^T Φ(x_1) = 0 + 1 + 0 ≧ 0 となり t_1 = -1 と合致しません。よってw^(3) = w^(2) + φ(x_1) t_1 = (0, 1, 1) - (1, 1, 0) = (-1, 0, 1)
■Step 4
x_2 は w^T Φ(x_2) = -1 + 0 + 1 ≧ 0 となり t_2 = -1 と合致しません。よってw^(4) = w^(3) + φ(x_2) t_2 = (-1, 0, 1) - (1, 0, 1) = (-2, 0, 0)
■Step 5
x_3 は w^T Φ(x_3) = -2 + 0 + 0 < 0 となり t_3 = +1 と合致しません。よってw^(5) = w^(4) + φ(x_3) t_3 = (-2, 0, 0) + (1, 1, 1) = (-1, 1, 1)
■Step 6
x_1 は w^T Φ(x_1) = -1 + 1 + 0 ≧ 0 となり t_1 = -1 と合致しません。よってw^(6) = w^(5) + φ(x_1) t_1 = (-1, 1, 1) - (1, 1, 0) = (-2, 0, 1)
■Step 7
x_3 は w^T Φ(x_3) = -2 + 0 + 1 < 0 となり t_3 = +1 と合致しません。よってw^(7) = w^(6) + φ(x_3) t_3 = (-2, 0, 1) + (1, 1, 1) = (-1, 1, 2)
■Step 8
x_2 は w^T Φ(x_2) = -1 + 0 + 2 ≧ 0 となり t_2 = -1 と合致しません。よってw^(8) = w^(7) + φ(x_2) t_2 = (-1, 1, 2) - (1, 0, 1) = (-2, 1, 1)
これで全ての w^T Φ(x_n) が目的変数と合致するようになり、w = (-2, 1, 1) が得られます。
いやあ本当に学習できるんですね。
めでたしめでたし。
もしよければ、各ステップごとに決定面がどのように遷移するか描いてみると面白いかもしれませんね。
w = (a, b, c)、φ = (1, x, y) とすると、w^T φ = a + bx + cy = 0 なので、座標平面の ( - a/b , - a/c ) を通る直線として表せるので。
こんな簡単な例でも、いろいろ問題点が見えてきます。
(1) 収束に時間がかかる。
明確に解があることがわかっている、これだけ低次元の例でも収束に８回かかっています。
オンライン学習ライブラリで「学習を１０回繰り返す」必要があるのも大納得。
(2) 学習データの偏りに強い影響を受ける。
上の計算で(恣意的に)選ばれた誤分類ベクトルを見ると、x_3 が多いことがわかります。これは、正例が x_3 しかないためです。
これを本当にランダムに選んでいたら(そして実際の計算ではおおむねそうせざるを得ない)、収束にはもっと回数を要したでしょう。
あるいは学習データに偏りがなくても、ランダムに選んだ順番がたまたま「ずっと正例でトレーニングした後、今度はずっと負例」なんてことになったら、間違った結果が確実に出てしまうでしょう。
このあたりの問題点を少しでも解消しようとするのが Averaged Perceptron その他の方式、ということでしょうか。
なんにせよ、オンライン学習で「ランダム！」「繰り返し！」と叫ばれる理由がよくわかって、一安心です。
次回は実装。
今度は CLUTO を試してみた話を書こうと思っていたのですけど、あまりふくらみそうにないので、保留。
オンライン学習(逐次学習)に興味があるので、まずは Perceptron 周辺を勉強し始めてます。
が、その前に動くものをさわっておこうということで、岡野原さんのオンライン機械学習ライブラリをちょっぴり試してみました。
Linux なら ./configure & make でＯＫ。
Windows の場合 oll.hpp の先頭のどこかに
#include <algorithm>
を追加すれば VC++ でもコンパイルできました。
サンプルデータには、プロジェクトページにも実験としてあがっている news20.binary をまずは使ってみることにしましょう。
「シャッフルし、15000例の訓練データと4996例のテストデータに分けた」とあるので、その通りにします。
$ sort -R news20.binary > news20.random $ head -15000 news20.random > news20.train $ tail -4996 news20.random > news20.test
実際に中谷が興味があるのは自然言語処理なので、NLP らしいデータはまた別途用意して試してみたいと思います。
まずはパーセプトロン。
ビルドが通ってデータの用意もできました。
実行。
$ ./oll_train P news20.train news20.model.p -C=2.0 -b=1.0 -I=10
15000 例の学習データを用いて、Perceptron(P) で１０回繰り返して学習(-I=10)、結果を news20.model.p に保存します。
学習手法は先頭の "P" を "AP" などに変更することで変えられます。そのあたり、コマンドラインの仕様はプロジェクトページで見てください。
「同じデータを１０回繰り返して学習する」というあたりが、収束(の可能性)がある線形識別器ならでは、でしょうか。
Naive Bayes とかだと同じデータで１０回学習なんて考えられないですから。
$ ./oll_test news20.test news20.model.p Accuracy 94.235% (4708/4996) (Answer, Predict): (p,p):2425 (p,n):35 (n,p):253 (n,n):2283
学習結果を用いて、テストデータを分類させてみて、その正解率を出しています。
(p|n,p|n) は positive|negative を positive|negative に分類した件数で、正解率は 94%。
プロジェクトページの例と大きく違っていないので、一応動いていることが確認できました。
これで自分で勉強＆実装したものとのベンチマークがとれますね。
次は、Perceptron を理解するために、「手で Perceptron を計算」してみます。
英単語タイピングゲーム iVoca にて、本日以下の機能をリリースしました。
ブック画面の右上に「問題一覧」リンクが追加されています。
問題一覧では、問題と解答の他に「出題数」「習得度」「苦手度」が各単語ごとに表示されます。
例えば「難読駅名(JR東日本 東京近郊編)」の問題一覧は以下のようになります(ユーザ登録して遊んでいない場合は出題数・習得度・苦手度は空になります)。
「習得度」には現在の習得レベルが 100点満点で表示されます。ブックのスコアは、この習得度の合計とほぼ一致するようになっています。
「苦手度」は、「その単語にどれだけ手こずったか」が星０個～５個で表示されます(多いほど苦手)。
問題一覧ではヘッダをクリックするとソートしますので、「苦手度」順に表示させて苦労した単語が確認するなど、今までに学んだことのあるブックについて、いろいろな楽しみ方や役立て方をしてもらえるようになりました。
ずいぶん前からご要望いただいていた「問題と解答の長さを長くして欲しい」にも、ようやく対応しました。
長～い問題や解答については、ご覧のようなイメージで２行で表示されます。
スローペースではありますが、iVoca では引き続きより楽しんで単語を覚えられる機能を追加していきたいと思いますので、よろしくお願いします。
本日、英単語タイピングゲーム iVoca をアップデートしました。
更新内容は次の通りです。
iVoca の認証はこれまで「外部認証のみ」だったわけですが、API をどうするか、などなどなどの頭の痛い問題がありました。
今回、iVoca が利用していた外部認証の一つ「サイボウズ(R) ネットID」がサービスを停止することになったので、これを機に独自認証の機能を提供することにいたしました。
これで API を提供できる道筋がついたので、まずは第一弾として、個人の学習履歴データを取得できるようにしました。
iVoca アカウントを設定し、公開設定を「公開」に指定した後、
http://ivoca.nsdev1/api/progresses/[iVoca アカウント名]
この URL にアクセスすることで、熱心に学習している５件のブックについて、日々の学習履歴が json 形式で得られます(フォーマットについては後日解説します……すいません)。
なお、従来「サイボウズ(R) ネットID」をご利用いただいていた方のログインID(メールアドレス)とパスワードは、上の注意書きの通りそのまま iVoca アカウントのほうに移行させていただいていますので、「ログイン」をクリックした後、iVoca アカウントのログインフォームにてメールアドレスとパスワードを入れてログインしてください。
mixi OpenID でご利用いただいていた方はそのまま引き続きご利用いただけますし、setting メニューにて iVoca アカウントも設定して、併用することも出来るようになっています。
そして、今回の目玉機能は iKnow! 対応です。
iKnow の API を利用して、iKnow の「学習アイテムリスト」を iVoca で学ぶ(遊ぶ)ことができるようになりました。
これにより iKnow の素晴らしい問題リストを iVoca で覚えられるようになっただけでなく、iKnow にて音声データのある単語はちゃんとゲーム中に発音してくれるようになっています。
ここに挙げたリスト以外にも、iVoca のユーザであればどなたでも、iKnow のどのリストでも iVoca で学べる(遊べる)ように登録することができます。
iVoca の iKnow メニュー から、iKnow のリスト画面の URL ( http://www.iknow.co.jp/lists/.... という形式のもの) を指定するか、同じ画面の iKnow リスト検索を使って利用したいリストを探してください。
なお、初めて iVoca にて利用するリストの場合には、学習データ初期化のための処理が10秒～１分程度かかります。
これほど素晴らしいデータを API で提供してくれているセレゴさんには、本当に感謝します。ありがとうございます。
これを第１弾として、逆に iVoca のブック(単語帳)を iKnow に登録する機能や、iVoca と iKnow の学習データを一元化して見せる機能とか、まずは iVoca でざっと覚えて、特に苦手な単語だけを選んで iKnow のリストを自動的に作るとかとか、いろいろ夢はふくらむんですが、順番にちょっとずつ、ですね。
まずは「問題の長さをもうちょっと長くできると嬉しい」という要望をいただいているのに、まだほうったらかしなので、こちらをやっつけるところからでしょうかね。
なお発音機能は Flash Player にて、バックエンドで iKnow アイテム情報を順次取得して実現しています。そのため、音声を発音するようになるまで少し遅れたり、ごく一部の単語のみしか発音してくれない、という状態になる場合があります。iKnow が混雑する時間帯は特に起きやすいようです。
改善を図りたいと考えてはいますが、あらかじめご了承ください。
英単語タイピングゲーム iVoca につきまして、以下の日程でメンテナンスを実施させていただきます。
・2009年2月16日(月) 18:00 ～ 20:00
メンテナンス中は iVoca をご利用していただくことが出来ませんので、ご了承ください。
メンテナンスが終了次第、サービスを再開いたします。
今回のメンテナンスにおきまして、以下の更新を予定しております。
IR の階層的クラスタリングを試すの続きです。
"efficient" な HAC(hiererachical agglomerative clustering) を実装してみます。
今回は、コード全体をぺたぺた貼り付けるのも見にくいし面倒だしということで、github に置いてみました。
git://github.com/shuyo/iir.git
前回作った corpus パックも commit してありますので、 clone すればいきなり動く、はず。
git clone git://github.com/shuyo/iir.git cd iir/hac ruby hac.rb 4million.corpus
おのおの手元でちょこちょこ改変して試してみるには CodeRepos より git の方が向いてるんじゃあないかなあと思ったんですが、git まだ使いこなせてないのでなんか色々間違ってるかも。
実装の説明に行く前に、まず前回の naive HAC (=single-link clustering) はなぜ inefficient だったか、という話を簡単に。
クラスタを近い(=類似度が高い)順に結合していくのが HAC の基本ですが、そうなると当然「クラスタ同士の類似度」を計算しなくてはならなくなります。
一番素直で簡単のだと、「クラスタ間で最も近い(類似度が高い)ベクトル同士の類似度を、クラスタ間の類似度とする」という方法があるのですが(これが single-link clustering)、これが「大きいクラスタほど有利」な計算方法であることは明らかでしょう。
このため、「大きいクラスタが、対象を一つずつ拾っていってしまう」という現象(chaining)が発生してしまい、クラスタリングとして役に立たなくなってしまうことがあるわけです。
それを解消するための方法として、IIR の 17.2～17.4 では single-link clustering 以外に complete-link clustering, centroid, group-average など、チェインニングが起きにくい「クラスタ同士の類似度」を紹介しています。これらの詳細については、ここでは省きますね。
前回も紹介した「クラスタリングとは (クラスター分析とは)」にもこれらの方法が載っています。ただし、こちらは類似度として(ユークリッド)距離を使用しているので、IIR の cosine similarity とは大小が逆だったり、距離の場合に有効な「ウォード法」が紹介されていたりします。
また、IIR 17.2.1 では、前回の naive HAC の計算量は Θ(N^3) だったのですが、priority queue を導入すると Θ(N^2 log N) にできるよ、という話をしています。
それらを合わせたアルゴリズムの pseudo code が掲載されているので、今回はそれに沿って実装してみるわけです。
Pathtraq で Web ページの自動分類を手がけてみて。
Web ページは日々どんどん変わっていくのでフィルタは常に更新されなければいけないんですが、そのためには適切なタイミングに、適切な学習データを用意しなければならない。大変。
メンテナンスフリーが理想ですが、もちろん難しい。
現実的なところとしては「追加学習が必要なことを検知して、適切な学習データの候補を提案してくれる」というものが作りたいなあ……などなど考えているわけです。
そこらへんも含めて、自然言語処理とか機械学習とかそこら辺のお勉強をしてるんですが、実際に手を動かさないとわかんないですよねー。
というわけで、 "Introduction to Information Retrieval" の Chapter 17 "Hierarchical clustering" に沿って、ドキュメントの分類器を作ってみました。
ポイントは、教師無し分類でどれくらいのことができるのか。
なので Chapter 16 の K-means でも良かったんですが、dendrogram で結果が得られるのが楽しそうだったので、手始めに 階層的クラスタリング にしました。
K-means も別途試してみるつもり。
"Hierarchical clustering"(階層的クラスタリング) については、日本語での説明だとこちらのページがわかりやすいです。
「似ているもの」同士を結んで、全体を１つの２分木のようなもの（デンドログラム）に分類する手法です。おのおのの枝分かれについて閾値が明確なので、この結果から任意の個数のクラスタを得ることが出来るのが特徴です。
というわけで「デンドログラム」を描くのがひとまず目指すゴール。
単語をタイピングで覚える iVoca(アイボキャ)。
問題が上から落ちてくるので、どんどん答えていくだけで単語を覚えてしまえるサービスです。
タイピングということはやっぱり英語だけなのか……
これが日本語でもできたら、英語から日本語もできるし、それこそ英語以外のいろいろなことを覚えるのに使えるのになあ。
と思っていたあなたに朗報！
iVoca が日本語入力に対応しました。
「iVoca 難読漢字」です。
ちょっぴり難しめの漢字や熟語が降ってきますので、読みを「ローマ字入力で」答えてください。
もちろん今までの iVoca と同じで、ユーザ登録すれば漢字ごとの成績を覚えてくれて、苦手な問題を重点的に暗記できます。
仮名漢字混じりの問題ももちろんＯＫ！
「基本英単語100！(意味編)」は、iVocaで楽しんでもらっていた「基本英単語100！」の意味を答えるバージョンです。
例えば問題で "see" が落ちて来たら "見る" と答えるわけですね。
漢字の入力はどうするのかって？ 変換とか面倒でしょう？
いえいえご心配なく！
なんと "mi" と入力した時点で "見" が表示されます。
変換とか全くいらないので、とっても楽ちん。覚えることだけに集中できます。
他にも「ハリー・ポッター１巻を読むのに必要な英単語(意味編)」や、「都道府県の県庁所在地」など、日本語入力に対応したブックはどんどん増えていきます。
もちろん iVoca なので、ユーザが自由に問題を作ることができます。
これからは暗記ものならだいたいなんでも iVoca を使ってもらえますね。
英語だけじゃなくて、様々な Vocabulary (語彙)を増やすのに iVoca を活用してもらえると嬉しいです。
そうそう。
とりあえず覚えなきゃいけないことがない人でも、「全く変換とかしないのにどんどん漢字が表示されていく」という新感覚はぜひ一度楽しんでもらいたいです(笑)。
なかなか気持ちいいですよ！
続きには「日本語対応ブックの作り方」。