目次
かなり遅くなりましたが、第1回 データ構造と情報検索と言語処理勉強会 #DSIRNLPに参加しました。
帰ってから２日半ほど寝込んでしまい、更新が遅れました。。。
初の土曜日開催の勉強会でしたが、家族を説得してなんとか参加しました。
おかげで色々と面白そうなキーワードが拾えてよかったです。（拾っただけで理解するのはかなり時間がかかりそうですが。。。）
ということで、前回同様、個人的にメモを取ったので。誤記などあるかもしれませんが、その時はコメントいただければと。
0.DSIRNLPについて
※ボランティアで受付してたので聞けず。
1.TRIEにトライ！～今日からはじめるTRIE入門～
@echizen_tm さん
資料：http://www.scribd.com/doc/58688141/Try-for-Trie
1.TRIEの説明
実装についてはあとでスライドをみればいいか。（※ボランティアで受付してたので前半聞けず）
・パトリシア木
・Double Array
・LOUDS
・XBW
2.作ってみた
その1 ベーシック
Q.ノードのラベルどーする？
・固定長（ラベル＝1文字）
定数時間でアクセス可能
・可変長（ラベル＝任意文字列）
Patricia木に拡張可能
A.拡張性を考えて可変長に！
3.LOUDSとは？
概要
Jacobsonが提案
Level-Order Unary Degree Sequenceの略（いつからLOUDSになったのか不明）
構築済みTRIEからLOUDSを構築
作業領域がO(NlogN)からO(N)に
・ノードに幅優先で順番（Level-Order）をつける
・子ノードの数を付ける。Unary符号で実装
作ってみた
・UnaryよりVerticalCodeのほうがよさそう
http://d.hatena.ne.jp/echizen_tm/20100531/1275323074
・dag_vectorを使ってもいいかもよ？
4.QA
Q.可変長を配列にすればいいんじゃね？
A.単純にやると効率悪そう？
※LOUDSをlucene-gosenに適用するとなんか嬉しいことあるかな？
現状はDouble-Arrayだけど。
2. ランキング学習ことはじめ（Solr系に利用できそうな予感。。。ごごご。。。むずかしい。。。）
@sleepy_yoshi さん NTTのSuharaさん「話がうまい」
数原 良彦
自己紹介
情報検索、ランキング学習をやってる。
三浦半島在住
ねらい
ランキング学習の認知度を高める、ざっくり伝える。
ごめんなさい
「実装」についてをわすれてた。
・ランキング学習とは？
Learning to rank
preference learningとは違う
教師あり機械学習で検索ランキングに適用
・歴史
従来は単一ランキング
クエリ・文書関連度（TF-IDF、BM25）
文書の重要度（PageRank、HITS、SALSAなど）
近代的なランキングの実装方法
上記データを利用して関数を適用する。
・何を正解とするのか？
適合性評価の作成方法
評価点数を多段階で点数化
ランキング評価方法
ランキングを正解データと比較
NDCG（Normalized Discounted Cumulative Gain）
※分類問題におけるモデルの生成
Training Data＋学習アルゴリズム＝＞モデル
ランキング学習の訓練データ
素性や評価はクエリごとに変わってくるTraining data（ここが違う）
ここまでのまとめ
正解データは適合度至上主義！
ランキング学習手法
３つのアプローチ
教師あり機械学習（識別学習）≒
どのような目的関数/損失関数を
どのように最適化するのか
アプローチ
1.Pointwise手法
単一のデータに対して損失関数を設定
2.Pairwise手法
同一クエリのペアに対して損失関数を設定
3.Listwise手法
同一クエリのリストに対して損失関数を設定
Pointwise：あまりつかえない。
例：二値分類（適合＋１不適合－１）で学習
補足：Perceptron
例：PRank
しきい値と重み両方修正する。
Pairwise：Pointwiseよりいいらしい
文書ペアで損失を設定
MQ2007、MQ2008データセットの結果
Pairwise手法とListwise手法を比較しても
そんなに悪くないらしい
IR-SVMってので偏りなどを排除できて、精度向上になるよ
NLP2011でPARankっての発表したよ（手前味噌）
QA
Q.じゃんけんみたいに循環しない？（nokuno）
A.半順序のデータだと起きるが、検索の場合は全順序なので大丈夫だよ
Listwise：Pairwiseよりいいらしい
ListNetってのあり。
AdaRank
検索評価指標を直接最適化するブースティング手法
性能はいまいち？実装は簡単
その他の話題
Click-through logs
Query-dependent ranking
Feature selection
Transfer learning/Domain adaptation
Diversity/Novelty
公開Dataset
LETOR3.0/4.0 Dataset
MSLR-WEB Datasetなど
実装
RankingSVM
Stoch….
Learning to Rank教科書
英語の資料が今年複数出たみたい
まとめ
近代的な検索エンジンは多数のランキング素性を利用
評価データを用いてランキング素性の最適な重み付けを求める方法
。。。
機械学習手法は論文≒実装
なので、ソースコード見るほうが重要（論文にないノウハウがあるよ）
3.snappy調べてみた
@machy 町永圭吾（赤いポータルサイト）
TopCoderなどで活躍中？
・snappyは圧縮/伸張ライブラリ
zlibよりサイズが大きいけど一桁はやいですぞ。
・インストールなど
google－gflagsってのがないと動作しないよ。
・比較してみた（zlib）
一桁は言い過ぎだけど、はやかった。
・比較してみた（lzo）
Hadoopで利用されているlzo
はやかった。
・仕組みは？
zlib 辞書式符号化＋ハフマン符号化＝出力
snappy 辞書式符号化＋リテラル＝出力
・辞書式符号化は？
前に出てきたデータで同じ文字列の部分について端折る
・ハフマン符号化
よく出てくる記号を短い符号で置き換えることで圧縮する。
・snappyの符号化
基本バイト単位での処理にすることで、高速化してるみたい。
・snappyの辞書参照元の探し方
ハッシュテーブル利用してマッチする位置を検索
4byte窓でハッシュ値を計算してハッシュテーブルを更新
・圧縮しにくいデータ（同じ単語が出てこないパターン）について
圧縮をあきらめ始める（32回同じのが見つからないと窓の移動幅が1つずつ大きくなる）
16KB（フラグメント内）での比較回数が1008回に抑えられる。
・特徴
ハッシュがしょうと移したらあるはずのマッチが見つからないこともある。
メモリ消費量を抑えるためのハッシュのサイズ？
最悪ケースのサイズを予め確保してから処理するため、メモリの再確保が起きないのではやいぞ。
4.類似文字列検索してますか？
@overlast さん Yな会社
1.曖昧な情報を処理する能力
曖昧な情報を解決しようとする能力が高い。
例：お笑い芸人の芸がサンプルｗ
画像検索は曖昧クエリに答える例。。。
スターバックス、スタバ、SUTABA
スータバでも画像が出てきた。->女子高生とかが「スータバ」で画像をアップしてたりするから。
文字列を使った検索は現代のインフラになってるよね。
例：iタウンページ
タイトルとかに「スターバックスコーヒー」って書いてないとだめ。？
「スタバ」800件くらい -> 正規化で「ー」消してるんじゃないの？
「スータバックスコーヒー」0件 ちがうな。シノニム辞書登録してるな。
曖昧なクエリ（キーワード）から検索できないかなぁ？
曖昧情報の処理は文字列処理にこそ必要
なんでヒットしたかがわかるのが正解
なんでヒットしたかわからないけど、ちゃんと出てきたから正解！
2.ゼロ件ヒット問題（ゼロマッチ）
ピクシブ百科事典
「ピングドラム」だと17件
「ピンクドラム」だと0件 しかも真っ白！！
使いにくいよね。けど、一般的な検索システムの問題だよね。
Googleだと出てくる「ピンクドラム」の結果の最初にはピングドラムが出てくる。
->リンクがはられているから出てきた？みんなの間違いで助けられてる
食べログ
「俺のハンバーグ」
「俺はハンバーグ」で検索したら。。。「俺はハンバーグで連れは。。。」がヒット->しらねーよｗ
まとめ
ゼロ件ヒットは機会損失！！
3.曖昧な文字列で正しい文字列を探す方法
正しい文字列って？
1.表記誤りがない
2.心の底で求めている
※異表記同義、同表記異義、異言語表記（日本語の情報を英語で検索）などもある
正しさはユーザによって変わる。
正しい文字列をさがす手法
クエリ表記の正誤という軸
誤の場合表記をヒントに似た文字列を検索してみる。
探したい対象が正確か曖昧か
表記意外がヒントで同じ対象に到達できる？
どんな情報を手がかりにする？
編集距離（レーベンシュタイン）
検索ログ
4.Apporoの紹介
チョコ？いや、ロケット？いや、Approximate …
http://code.google.com/p/apporo/
中小規模だと使えそう
SimString
今後
よみかな、ローマ字表記に基づく類似文字列検索＋高速化の予定
技術概要
Suffix Array
N-gram Searchベースの近似文字列照合
Bit Parallel Matchingによる編集距離計算
5.検索と言語と文化（仮）
@mizuno_takaaki さん
放送禁止のためメモなし。
7.自然言語処理におけるargmax操作
@hitoshi_ni さん
※順番変更
・近似解法
その１ 全探索
いや、無理でしょ、計算が。
その２ 貪欲法
最適解が出るかは不明。
その３ ビームサーチ
上位kこの仮説を保持しながら幅優先探索
・動的計画法
すでに最大値がわかっていて、ゴールから眺めてみる。
逆からたどるとルートがわかるんじゃないか。
マルコフ性につけ込むことで、わかるんじゃないか。
計算量：品詞数の2乗
（品詞数の2乗）＊形態素数
DPの実装
Viterbiかなぁ？
・整数計画法（線形->整数）
自然言語処理としては整数計画法でだいたいOK。
アルゴリズム
・手元の解空間中から許容解を得る
・分枝してそこから最大値を求める
最大値＞許容解ならそちらを探索。
プログラム実装する？
すごく大変じゃないけど簡単でもないね。
問題の弱点がわかってるなら実装してもいいよね。
整数計画法の場合lp_solveなどのフリーのソフトで解くのがいいよ。エクセルでも解けるよ
ILP（整数計画法？）
問題の切り分けに使える。
まとめ
ILPで解けたら、いろいろ自分で考えると面白いよ。
その他のバズワード
参考資料
組み合わせ最適化＝1万円超
アリ本
6.ソーシャルグラフ分析(導入編)
@kimuras さん mixiの木村さん
・グラフ探索部分はまた今度。
・テキストマイニングや検索エンジンまわりやってる。
・ノードが数1千万、エッジが数億のオーダー
・分散技術の発展によるアルゴリズムの多様化
これまで
RDBからDumpしたデータをKVSに入れて頑張ってた。
Dump部分でデータ構造を毎回構築
問題点
変更による再実装、メンテナンスコスト、
これから
graphDBに取組中。マイニングに最適な感じ
graphDBの実装
OrientDB、Neo4jとか
Neo4jって
ACIDトランザクション可能
EmbeddedGraphDatabaseだとAGPLｖ３だから気をつけてね。
luceneで全文検索インデックスつくってるみたい。
Gremlinってのがquery言語を汎化してるらし。
とあるSNSのデータを使ってみたよ。
メモリ64G、CPUは1コアしか使えなかったよ。
ノード：15million、枝：600million
まとめ
ということで、色々と面白い話が聞けました。特にTRIEの話はかなり興味を持ちました。
検索周りで嫌というほど出てくるので。まだまだきちんと理解できてないので復習しないと。。。
lucene-gosenにも関係あるので、しっかり資料をみて復習する予定です。
基本的に検索系の話に関連があることが多くて面白く聞くことができました。
「類似文字列検索してますか？」や「ランキング学習ことはじめ」などは身近な話（だけど、なかなかきちんと学習できてない話）でした。
また、「自然言語処理におけるargmax操作」では大学でやっていた線形計画法などのわかりやすい説明で10年経ってようやく理解ができた次第です。。。（もっとちゃんと勉強しとけば。。。）
懇親会にも参加し、研究に近い分野の方が多い中でいろいろな話が聞けたのはよかったと思います。
次回もいろいろなキーワードを拾いたいのでぜひ参加したいです。
comments powered by Disqus
See Also by Hugo
- search-UIとSearchkitと検索画面
- Bonfire Data & Science #1に参加しました
- Search Engineering Tech Talk(検索技術勉強会)の運営として参加して始めてみました。
- 第25回Elasticsearch勉強会を開催しました。
- 第1章の05から06までやってみた（言語処理100本ノック）