第2回自然言語処理勉強会＠東京に参加してきた
「あずにゃんに関連する検索キーワード」→「あずにゃん ペロペロ」を実現するクエリ推薦技術について [twitter:@y_benjo]さん
発表資料：http://d.hatena.ne.jp/repose/20100925/1285399983
ユーザが入力したクエリに「近い」クエリを推奨する技術に関する二つの論文の紹介。
ここでいう「近い」とは、「意味的に近い」ということ。
今回の紹介論文で用いるデータは以下のとおり
- ユーザが入力したクエリ
- 検索結果からどのページに遷移したかという情報
論文1: Query suggestion using hitting time
論文PDFリンク：http://research.microsoft.com/en-us/um/people/denzho/papers/sugg.pdf
手法
- ユーザが入力したクエリと、アクセスしたページから二部グラフを作成する
- そのグラフ上をランダムウォークし、クエリを推奨する
利点
- 意味的に似ているクエリが推奨される
- 共起していないクエリも推奨される
- ロングテールに対応しやすい
- パーソナライズしやすい
クエリ推奨の課題
この論文によると
- いかにパーソナライズするか・・・MSRという略語をとっても、工学の人なら多分「Microsoft Research」、金融の人なら「Montage Service Rights」でしょう
- ロングテールに相当するクエリにどう対応するか・・・広告分野において大きな期待が生まれる
実際は、本当にマイナー過ぎるなキーワードは推奨されずらそうだけど、単純な共起モデルよりは良い結果が出そうとのこと
論文2: Generalized syntactic and semantic models of query reformulation.
論文PDFリンク：http://www.google.com/research/pubs/archive/36337.pdf
- 文字列の類似度と意味の類似度をあわせて一般化したクエリ推奨手法を提案
- 生成モデルを使ってクエリを推奨してみた
- 教師あり学習も適用
クリックログは用いない手法
- PMI(Pointwise Mutual Information)というのがよくわからず、ついていけない感じ。。。。
- 同じユーザが連続して入力したクエリを用いる
- 評価指標にはスピアマンの順位相関というものを使うらしい。
FSNLP６章読みながら「nグラム入門」的なこと [twitter:@naoya_t]さん
発表資料：http://blog.livedoor.jp/naoya_t/archives/51478756.html
連続したn単語（ないしn文字）をひとつの塊としたもの。
n-gramには大きくわけて２種類ある
- 単語nグラム
- 文字nグラム
1) 文章の素性値としてのnグラム
Latent Dirichlet Allocation入門 [twitter:@tsubosaka]さん
発表資料：http://d.hatena.ne.jp/tsubosaka/20100925/1285424360
機械学習ライブラリmalletを使う。
単語は独立に出現しているのではなく、潜在的なトピックを持ち、同じトピックを持つ単語は同じ文章に出現しやすい
何の役に立つのか？
- 文章分類
- 次元削減
- 言語モデル - 情報検索
文章生成モデル
- 各トピックごとに単語出現確率をディリクレ分布から生成
- 文章ごとにトピック確率をディリクレ分布から生成
推論アルゴリズム
- Gibbs samplerを使ったパラメータ推定ほうがよく用いられる
Mozcソースコード徹底解説 [twitter:@nokuno]さん
発表資料：http://d.hatena.ne.jp/nokuno/20100925/1285429764
変換エンジンの設計
- 疎結合な階層構造を採用
- ipc > session > converter > storage
コンバータ層の設計
かな漢字変換としてはオーソドックスな設計
言語モデル：クラスbigram
- クラスの接続コストと単語の生起コストを合計
ソースコード：辞書ファイル
- 左ID、右ID - 複合語の場合異なる
ラティス構造
- 全ての変換候補をコンパクトに表現
経路探索：Viterbiアルゴリズム - 線形時間で経路を探索
ストレージ層
IMEは常駐するのでメモリ使用量を最小限に抑えるよう工夫
- LOUDSによるコンパクトなTrieインデックス
- ハフマンコーディングによるバリューの圧縮
- 接続コスト格納のための疎行列の圧縮
- NG語彙フィルタのためのBloom Filter
- LRU(Least Resently Used)キャッシュ
データ構造：Trie
- 文字をノードとする木構造インデックス
- 豊富な検索操作
- 完全一致検索
- 前方一致検索
- common prefix search - (teaを検索するときに、tとかteとかの途中の単語も高速にヒットする)
データ構造：LOUDS
- ビット配列でえ木構造をコンパクトに表現
- ノード数*2+1 で表現できる。
- 実際には高速化のため補助インデックスも必要
- rxというライブラリのコード。かなりキモいｗ
- 岡野原さんのtx読んだほうがいいかも。
Rewriter候補の書き換え - 様々のヒューリスティックを実装
- 学習機能（文節区切り、文節内の順序）
- 共起コーパスの反映
- 数字、単漢字、記号変換昨日
- 日付変換昨日、顔文字変換昨日、電卓機能
- 福笑い機能、おみくじ機能
Bloom Filter - 予測変換に出さない候補をフィルタリング
- 仮名漢字変換と予測変換は辞書を共有している
- 予測にだけ出したくない候補を動的にフィルタリング
- 間違えてフィルターすることはあるけど、間違えてフィルターをすり抜けることはない
ナイーブベイズで言語判定 [twitter:@shuyo]
発表資料：http://d.hatena.ne.jp/n_shuyo/20100925/language_detection
言語判定
- 言語の絞り込み付きで検索したい
- 言語別のフィルタを適用したい（SPAMフィルタとか）
世間にあるもの＞少ない
- コーパス／モデルの構築が高コスト - 対象言語の知識がどうしてもかなり必要
- アジア系のサポートなし
既存のライブラリ
- Lingua::LanguageGuesser
- NGramJ
両方ともテキスト分類器の実装(TextCat)をベース - コサイン類似度
文字n-gramで言語判定ができる理由
- 各言語には固有の文字や綴り字の規則がある
- Zで始まる単語はドイツ語には多いが、英語にはほとんど無い
- etc...
- これら特徴に「確率」を設定し、文書全体に累積
- tri-gramだとsparse過ぎる
- uni-gramからtri-gramまで全部使う
言語判定の流れ
- 学習：学習コーパスからp(Xi|Ck)を求める
- 判定：対象テキストからp(Ck|X)を求める
「文字」について予習
- 世界で使われる文字は大きく４つに分類される
言語系統と「文字」
- 文字が同じで言語体系も似ていると判別しづらいというのがわかる
- 文字が独特の奴は楽（日本語のかな）
漢字系 - 中国語と日本語のように書けば通じるというのは特殊。世界的には口頭は通じるが書くとわからないほうが多い。
Rubyで検証
- http://github.com/shuyo/iir/tree/master/langdetect
- 割といい結果が出た。
- 確率を正規化していないけど割といい結果が出た*1
プロトタイプの問題点
- コーパスに依存した作り
言語判定ライブラリ for Java
- オープンソースとして公開( Apache License 2.0 )
- http://code.google.com/p/language-detection/
- Wikipediaのabstractデータベースファイルを採用
文字の正規化 - これが本題
- 基本 - stop characterの除外
- 文字種全体を代表となる１文字にまとめる
- etc
感想
- 各発表の時間が比較的長めだったので、濃い内容でよかった
- 英文も論文も読み慣れていないので、こういった論文紹介は個人的にとても有り難かった
- Query suggestion using hitting timeの方は自社の検索ログでも実装できそうと思ったけど、改めて見直すと理解できてないな。。。。orz...
- でも面白そうなのでプロトタイプぐらいは作ってみたい
- n-gramは自社検索で使っていて*2おなじみだったけど、全文検索エンジン以外での話で単語のつながりとかを確率的に扱う話は個人的に始めてだったので新鮮だった*3
- LDAの話はLDAって何って状態*4だったのでイマイチ消化しきれず。Malletというライブラリは覚えておこう
- Mozcの話はまとめにあった「IMEは総合格闘技」の言葉通り、幅広いなぁという印象を受けた。データ構造系のところはTrieとかBloom Filterとは単語はよく聞くけどよくわかっていないので特に復習したいと思った
- id:nokunoさんの資料は「ぷるむる」復習レーンでもいつもよくまとまっていて個人的に非常に分かりやすい
- 言語判定のはなしは事前のタイトルからは想像できない、実践的で非常に泥臭い内容。各国語の特徴とか調べるの凄い大変そうだと思ったけど、そういったノウハウを惜しげもなく公開されているという意味で貴重な発表だった。日本語は難しいなんて話はよくきけど、やっぱりかなり特殊な言語なんだな
