« 2005年09月 | メイン | 2005年11月 »
2005年10月24日
tree.hh を使って木の操作
Cマガジンを読んでたら、tree.hh の記事が紹介されてました。
http://www.aei.mpg.de/~peekas/tree/
tree.hh は、STL と互換性のある tree 操作ライブラリです。STL のインタフェイスを踏襲しているので、STL アルゴリズムとの相性も抜群です。C++ で構文解析木を扱う機会が多いのですが、以前はほとんど自前で処理をしていました。もっと早く知っておけばよかったです。
tree<std::string> tr;
tree<std::string>::iterator top = tr.begin();
tree<std::string>::iterator one = tr.insert(top, "one");
tr.append_child(one, "two");
tree<std::string>::iterator three = tr.append_child(one, "three");
tr.append_child(three, "four");
tr.append_child(three, "five");
tr.append_child(one, "six");
tr.insert(three, "seven");
こんな感じで木を作ります。insert と appehd_child を組み合わせるだけです。
さらに、木のノードが iterator になっているのが良いですね。iterator も数種類あって、
- pre_order_iterator: 現在の node から pre_oreder で node を辿る
- post_order_iterator: 現在の node から post_oreder で node を辿る
(ただし、in_order はないの？)
- sibling_order_iterator: 現在の node の子供を辿る
- fixed_depth_iterator: ある深さの node を辿る
などを組み合わせて木を辿れます。これらは random access iterator なので、
tree<std::string>::iterator l = std::find(tr.begin(), tr.end(), "seven");
tr.insert(l, "eight");
みたいに、std::find を使って、node を挿入ってなこともできます。
さらに、
- 二つの木を merge する
- sibling をソート (再帰的にも可能)
- node を一部フラットにする
- 指定した sibling の範囲を部分木として取り出す
- subtree どうしを swap する
といった気の利いたアルゴリズムもあります。
投稿者 taku : 01:17 | コメント (8) | トラックバック
2005年10月17日
リアルめかぶ
めかぶが好物の私ですが、スーパーで売っているいろんなタイプのめかぶをトライしています。しかし納得できるものが少ない。NAIST近くのサカエに売っていた「カネキ吉田商店」の「若めかぶとろろ」がやっぱり一番です。引っ越してきてからは、なかかなこのめかぶに出会うことがなかったのですが、つい最近嫁さんが見つけたそうです。どうやら150円で売ってるみたい。奈良では100円だったのに。。
ひさびさに出会えたこともあり、改めてその味に感動しました。なんたって歯ごたえが違います。たいていのスーパーのめかぶは、単にヌルヌルしてるだけなのですが、カネキさんのは適度なコリコリ感があります。焼酎がすすみます。量も比較的多めです。
このめかぶを安定して入手したいのですが。ダイエー系のスーパーならあるのかな？
さて、形態素解析器 MeCab ですが、0.90の公開準備がようやく整いつつあります。解析精度のよきせぬバグが最近入ったので、それを早急に fix して、文書を書けば晴れて公開できそうです。大幅に遅れて申し訳ありません。
投稿者 taku : 00:56 | コメント (1) | トラックバック
2005年10月11日
page popularity と page quality と randomness (PageRank 編)
昨日の話の続きです。よくよく考えてみると、PageRank も無作為性を取り入れたアルゴリズムでした。
PageRank は、Web Page の quality を求める方法の一つです。基本的な考え方は、ネットサーファーが ε の確率で無作為に選んだページにジャンプし、1-ε の確率で現在のページ内のリンクを辿ります。サーファがこの手続きを延々と続けていき、定常状態でのページの滞在時間が PageRank です。
このときの ε で無作為のページにジャンプする行為が、無作為性そのものです。
PageRank に似たアルゴリズムとして、Kleinberg の HITS があります。これは、たくさんのリンクを放出する HUB度 と、たくさんのリンクをもらう Authority度 という二つの quality を page に与え、HUB度 の高いページからリンクされると Authority 度が高くなり、Authority度 の高いページにリンクすると HUB 度が高くなるという再帰的な定義の定常状態から各 quality を計算します。
ポイントとしては、HITS には、無作為性がありません。
無作為性が無い HITS にはどういう問題点があるのでしょうか？ この問題点をまとめた論文として、Stable Algorithms for Link Analysis があります。結論から言えば、HITS はリンク構造の perturbation(ゆらぎ)に弱いという欠点を持っています。Web のリンクの構造にちょっとした変化(リンクが消滅したり、指す場所が変化する)が発生しただけで、Authority度とHUB度が大きく変わってしまいます。このような「ゆらぎ」は、実世界に頻出するためHITS は適切なスコアリングが行えません。
PageRank は、無作為性を入れているため、ある程度の「ゆらぎ」を加えても、PageRank のスコア自身は大きく変化しません。無作為性がシステムそのものを頑健にしています。当然ですが、ε=1 とすれば、どのページも一様の PageRank を持ってしまい無意味です。 quality としてのスコアと頑健性はトレードオフにあります。リンク構造にどれぐらいのゆらぎがあるのかが分かれば、εをどう設定すればよいか検討がつくでしょう。また、無作為にあるページにジャンプする方法は、実際の人間の行動から考えても理にかなっています。
HITS 自身の問題点は、HITS に無作為性を入れることで解決できるようです。件の論文は、HITS の問題点を起点に、無作為性を取り入れた Randomized HITS の提案となっています。
昨日の話と強引に結びつけるなら、無作為性のない単純な popularity ベースのランキングは、初期状態や外乱といった「ゆらぎ」に敏感にランキングが変化してしまう不安定な方法と言えます。
投稿者 taku : 01:40 | コメント (9) | トラックバック
2005年10月10日
MT 3.2
やろうやろうと思っていてなかなかできなかった MT のアップグレードを行いました。
コメントスパムの問題がある程度解決されるとおもいます。
あと、エントリ数が多くなってきたので、sqlite を導入してみました。 sqlite は手軽でなかなかよいですね。Ajax 手書き文字認識のデータが10万事例ほどたまったのですが、人手修正用のバックエンドに sqlite を使ってみようと思います。
投稿者 taku : 19:35 | コメント (19) | トラックバック
page popularity と page quality
注目のエントリーの仕様が、はてブの偏りを助長してるのでは を読んでふと思うことがありました。 一般に popularity による quality 評価の性能は、popularity の初期状態に強く依存します。初期状態がよければそのまま正のフィードバックに乗りますが、それに失敗すると shut out されてしまいます。単に早くページが作られたという理由だけで quality が 過大評価されてしまう現象はよくあります。
ページ popularity と quality に関する興味深い論文があります。
Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results
検索結果のランキングを popularity ベースでやったときの問題点がまず述べられています。popularity はたいていうまく動きます。しかし、ユーザの興味は検索結果の上位にしかないので、単に新しいページや一元的な理由で上位にランクされたページにユーザの興味が集中し、真に quality の高いページが shut out されてしまいます。著者はそこで検索結果に randomに選んだページを数パーセントほど混ぜると、全体の検索エンジンの quality が向上した報告しています。さらに、ページの新しさに応じて、どのくらい混ぜるのかといった考察もあるようです。（詳しく読んでいないので間違っているかも）
popularity と randomness はトレードオフの関係にあります。前者は今まで知っているページの quality を重視し、後者は今まで知られていないページの潜在的な quality を評価するのに役立ちます。情報検索の precison と recall とほぼ同じ概念です。
はてなブックマークも、適切な無作為性を入れると面白みが増すと思います。たとえば、1000人が1000人、同じ注目エントリを読んで、ひとつの方向にバイアスがかかったリストになるよりは、個々が重なりを持ちつつも、少量の別々のページを読むほうが、quality の高いページをまんべんなく収集できそうです。
このように、一定の無作為性をシステムにわざと投入することは、珍しいことではありません。ニューラルネットワークの学習の際に、モデルの重みに適当な乱数を加算することで、性能が上がるという現象があるようです。乱数によって、ネットワークにある程度の「柔軟さ」が生まれるからです。機械学習における正則化もこれと似た考えに基づいています。
投稿者 taku : 00:31 | コメント (56) | トラックバック
2005年10月06日
Ajax で隠れた技術を表舞台に出す
Ajax を知ったのは、今年の2~3月ぐらいだったと思います。この技術に触れたとき、「これで一般には表に出しにくい技術をデモれるかも。。。」と感じたのを覚えています。ほどなくして Ajax KIWI, Ajax IME, Ajax Migemo を作ってそれなりの反響が得られました。
私自身、Webアプリケーション開発の経験はほとんどありません。最近の Web 開発インフラの進歩の速さにはいつも驚かされています。一方、私は急激な進歩とは程遠く、表舞台には出てこない機械学習とか言語処理のツールをふだん hack しています。私がいる分野は、パフォーマンス(実行速度)が結構重要です。 いまさらながら C++ を使って実装していますし、パフォーマンス向上のためのトリビアをそれなりに蓄積しています。ほかにも高速な辞書マッチや文字列検索処理などのコードも書き溜めていました。
今思えばこれがかえって良かったのかもしれません。自分が Web プログラマだったら、フロントエンドの開発は出来たとしてもバックエンドの開発は多分できなかったです。出来たとしてもパフォーマンスに問題があったと思います。Ajax は、自分が持っている専門的で日陰の技術をいとも簡単に表舞台に引っ張り出すのにとても役立ちました。
Ajaxは、Web のアクセスビリティを向上させるインフラだといわれていますが、私は個人的に別の点に注目しています。 Ajax は、Web とは無縁だけど別の分野で尖った技術を持っている会社や個人が、その技術や技術力を宣伝したり、新たな可能性や応用を一般ユーザに示すのに役立つのではないでしょうか。そのような技術がWeb の世界に出てくることで、ユーザと技術の距離が縮んでいくような気がします。
大規模文字列検索が得意であれば、KWIC のようなツール、画像処理が得意であればインテリジェントな画像検索、機械学習が得意であれば、Weka のようなフロントエンド、自然言語処理が得意であれば文書校正支援... などざっと考えただけでもいろいろありそうです。
投稿者 taku : 01:16 | コメント (16) | トラックバック
2005年10月02日
タグとマルチラベル問題と機械学習
ネット上のサービスを見ていると、メールなりWebページをある一意のカテゴリに分類するという整理法から、タグ（ラベル）をつけるという整理法に変わってきているようです。
代表的な例は Gmail。フォルダという概念はなくメールにラベルを付与していきます。私が良く使う方法は、「リマインダー」のラベル（メールの重要さという観点）と「内容」のラベルです。二つはそれぞれ独立した分類方法ですが、フォルダだと同居できません。他の例だと「はてなブックマーク」があります。ユーザが任意のタグを付与することができます。
機械学習の言葉を使えば、従来のフォルダは「シングルラベル」の分類問題、後者のタグは「マルチラベル」分類問題となります。文字どおり、前者はインスタンスに対し1つのラベルのみを付与する問題、後者は複数のラベルを付与する問題です。
さて、機械学習の分野でマルチラベル問題はどう進展してるのでしょうか？実際のところ、ほとんどすべての機械学習アルゴリズムはシングルラベルのために設計されています。その理由としてシングルラベルのアルゴリズムを使ってマルチラベルの問題を解くことは可能であるという背景があります。二値分類のアルゴリズム（たとえばSVM)を使い、あるインスタンスにラベルAを付与すべきかどうかを推定できます。この方法だと、ラベルの種類が100種類あると100個の分類器を作る必要があります。
これはこれでうまくいくのですが、付け焼刃技術であるのは否めません。一方、はじめからマルチラベル問題をターゲットとしているアルゴリズムも少なからず存在するようです。私の知る限りでは、以下の二つです。
- PMM
Naive Bayse の拡張。SPAM分類でよく使われるベイジアンフィルタの拡張。
生成モデル。実装は比較的楽。良くも悪くも Naive Bayse なので、その性質を受け継ぐ。
解説記事
NIPS のオリジナルペーパー
- SVM
二値分類 SVM の拡張。もしくは、構造学習 SVM の special case。PMM の影響を受けている。識別モデル
NIPS のオリジナルペーパー
PMM はこの問題に着目した初めての手法だと思います。解説記事によると、私が思うところの整理方法としてのタグ付与というよりは、既存の新聞やYahooカテゴリが一部マルチラベルになっているという観察が出発点になっているようです。近年マルチラベルのデータがたくさん入手できるようになっています。いろんなデータを使って実験、評価しやすくなりました。今のネットの整理方法とマルチラベル機械アルゴリズムという二つの観点から新しい仕事なり応用を考えてみるのも面白いでしょう。もちろん、新しい手法の出現も期待できます。
個人的には、もっと Lite weight な 識別モデルを作ってみたいです。