5. Webと検索 2016/11/7
Webと検索
増井俊之
慶應義塾大学 環境情報学部
masui@pitecan.com
2016/11/7
人生は検索である
仕事や生活のかなりの部分は情報検索
本質的に情報を生成/加工することは少ない
例1: メールの送信
メールソフトを捜す
メール作成ボタンを捜す
送り先アドレスを捜す
送るべきメッセージを捜す (入力する)
添付ファイルを捜す
送信ボタンを捜す
...
例2: 趣味
良いレストランを捜す
面白い番組を捜す
面白い映画を捜す
面白いニュースを捜す
聞きたい音楽を捜す
面白い展覧会を捜す
掘り出し物を捜す
例3: 計算機操作における検索
メニュー
プログラムや機能を捜す
アイコン
プログラムやデータを捜す
フォルダ
階層的分類にもとづいて情報を捜す
スクロールバー
画面に入りきらない情報から必要な部分を捜す
Webと検索
Web上の作業もほとんどは検索
ユビキタス時代も傾向は同様
ハイパーテキストはもともと検索システム
情報検索の歴史
テキスト検索研究時代
インターネット黎明期
人力検索時代
統合的検索時代
テキスト検索研究時代 (〜1995)
「Information Retrieval」
ACM SIGIRとか
テキスト全文検索
一般人が検索システムを使うことは稀
研究は枯れてきていた印象
マルチメディア検索は盛り上がらず
インターネット黎明期 (〜2000)
従来の研究者がサーチエンジンを実装
Lycos
AltaVista
...
テキスト検索システムの認知が広まる
人力検索時代 (〜2010?)
Google登場
ページランク = 人力リンクを利用
テキストの中身よりも人力情報を重視
ソーシャルフィルタリング
ソーシャルブックマーク
統合的検索時代 (2010〜?)
あらゆる付帯情報を検索に利用
位置情報、時間情報、etc.
漠然とした情報から正しい情報を検索
芋蔓検索
新しいテキスト検索技術
SVM, LSI, ...
テキスト検索対象の規模と検索手法
大規模
インデクス作成
小規模
なめらかな直接検索
テキスト走査も可能
中規模
両者のうまい組み合わせ
長い研究の歴史がある
Information Retrieval (IR)
ACM SIGIR
インデクスを作成しておくのが普通
構造があるもの = データベース<br>それ以外の検索 = IR
適合率と再現率
Precision (適合率)
正しい検索結果 ÷ 全検索結果
Recall (再現率)
正しい検索結果 ÷ 正しい全情報
適合率と再現率
理想は両方100%
実際はトレードオフがある
F値 = 2 / ( 1 / Recall + 1 / Precision )
ブーリアン検索
文書中に単語が含まれているかを検索
単語文書行列を利用
https://i.gyazo.com/7e30f277ce8b72bdb57a37f9fde7c63b.png
ブーリアン検索
利点
AND/OR/NOT検索が可能
e.g. Brutus AND Caesar but NOT Calpurnia
欠点
表が巨大になる
文書ランキングができない
転置インデクス
単語文書行列を小さく表現
https://i.gyazo.com/8c1dfea7b39d97dfcf9f5f69416e0658.png
単語の扱い
単語切り出し
文書から単語を区切って切り出す
正規化
活用形の処理
ステミング
ストップワードを除去 (前置詞など)
ベクトル空間モデル
文書と検索文字列を単語ベクトルで表現
ベクトルの内積で類似度を評価
https://gyazo.com/5d8bf7d946262da0b78887494b276900.png
ベクトル空間モデル
出現頻度にもとづく単語の重みづけ
Wij = TFij * IDFi
Tij = (term freq) 文書j中の単語iの出現頻度
IDFi = (inverse term freq) log(N/DFi)
DFi = 全文書中の単語iの出現頻度
「連想検索」
ベクトル空間モデルの検索システムにオシャレなFlashインタフェースをつけたもの
GETA
単語/文書行列WAM(Word-Article Matrix)ライブラリ
連想検索ライブラリ
クラスタリングライブラリ
https://i.gyazo.com/d2ee52573898e150ccc0fb5ac20edce1.png
https://i.gyazo.com/ce482951a5a90407d1abfc1f02eda035.png
適合フィードバック(Relevance Feedback)
検索結果を検索文字列にフィードバック
自動的でも手動でもよい
マッチ上位項目のカテゴリをキーワードに追加するのが有効
検索結果向上に着実な効果
適合フィードバックの問題
ユーザーはフィードバックしたがらない
検索行動を長引かせたくない
クエリが長くなる
ユーザは再現率に興味が無い
クエリ拡張
https://i.gyazo.com/e696d55b51d26c7016a48c7e11ac976a.png
シソーラス利用
ログ利用
Web向き
自然言語の単語の並びを確率的にモデル化
文書が検索語に適合する確率を計算
索引語、適合文書、非適合文書などの出現確率を表現
理論的基礎あり
tf, idfなどの計算はヒューリスティック
LSI(Latent Semantic Indexing)
単語文書行列の特異値分解 (Singular value decompositions, SVD) を利用
固有値分解のようなもの
SVD計算
単語文書行列を低階数行列に変換
計算量減少 / 適合率向上
小規模なキーワード検索
検索対象テキストを走査
パタンマッチアルゴリズムを利用
パタンマッチアルゴリズム
完全マッチ
正規表現
曖昧検索
テキスト検索アルゴリズム
文字列T[1..n]中のパタンP[1..m]の出現位置を計算
単純に比較していくと遅い
各種の高速アルゴリズム
Knuth-Morris-Pratt(KMP)法
Boyer-Moore法
Shifterアルゴリズム
超単純アルゴリズム
T[1..m] と P[1..m]を比較
T: aaaaaaaaaaaaaaaaab
P: aaaaaab
T[2..m] と P[1..m] を比較
T: aaaaaaaaaaaaaaaab
P: aaaaaab
...
T[n-m+1..n] と P[1..m] を比較
T: aaaaaaaab
P: aaaaaab
最悪の場合約 n * m 回の文字比較が必要
Knuth-Morris-Pratt法
P[7] (= b)で不一致が検出されたとき
前のテキストはaaaaaaであることが既知
P[6] (= a)の比較をやり直せばよい
不一致が検出されたときに比較をやりなおすべきPの文字の位置をあらかじめ「失敗関数」として計算
無駄な比較を繰り返さないようにする
https://gyazo.com/1d7b988f5207f5d70182f576cd28e525.png
Knuth-Morris-Pratt法の例
P = abcaba の場合
https://gyazo.com/981d1b79dceedfa85cf5995ea44be3b4.png
5 → 1 の遷移
5の状態でテキストの最後がabcaであることが既知
→2の状態まで戻れる
5から6に遷移できない場合
次の文字はbでない
→1の状態まで戻れる
Boyer-Moore法
最速といわれるテキスト検索アルゴリズム
文字比較回数が文字列長より少なくてすむ
KMP法ではテキストの文字をすべて比較しなければならない
パタンの右端からマッチを調べる
1回目の文字比較でT[m] = cであることがわかる
cはPに含まれていないので2回目の比較はT[m+1]の先から調べればよい
https://gyazo.com/c0ef58ec05df6c96c8591907363c7b2c.png
Boyer-Moore法 (Cont'd)
右からk文字だけ一致したときにその次にどこから比較を再開すればよいかをあらかじめパタンから計算
2個の表を用意
d1 -- 右端で不一致が検出されたときの、移動数不一致文字の表
d2 -- 右からk文字目で不一致が検出されたときの、移動数不一致位置の表
先の例の場合、d1['a'] = 1, d2['c'] = d1['d'] = ... = 8である。
シフタアルゴリズム
長さmの文字列検索のマッチ状態をmビットで表現
k文字マッチをk番目のビットで表現
e.g. 11101 = 2文字マッチ
次の文字がcであるとき、この状態変数を1ビット左にシフトし、T[c]とのORを計算することにより新しい状態を計算
Tcはあらかじめ計算しておく値で、パタン文字==cの位置だけ0になっている。 e.g. パタンabac → T['a']=0101
ミスマッチを許すときはORのかわりに加算を使用
シフタアルゴリズム (Cont'd)
条件によってはBMより高速
曖昧検索ユティリティ`agrep'で使用
正規表現
文字列のパタンを指定して検索
曖昧な検索ができる
e.g. 「〇山×郎さん」を探す
Unixでポピュラーになった
正規表現パタン
選言
「aまたはb」
文字集合
「英数字」
繰り返し
「aが3個以上並んだもの」
正規表現の例
abc
(abc|def)
[abc]
ab*c
正規表現の例
(時計|時間|時刻)を([0-9]*)時に(セットする|設定する|あわせる)
ファイルを((きっちり(きっちり)?)?)消す
言語の生成文法
言語の文を生成する規則
終端記号(e.g. 「山」)と非終端記号(e.g. 名詞)
名詞 ← 「山」
名詞句 ← 形容詞 名詞
正規文法
正規表現を表現する文法
A ← aB という形式のみ (A/B: 非終端記号, a: 終端記号)
正規表現の実現
同等の状態遷移機械に変換可能
e.g. a(b|cd) に対応する文法と状態遷移機械
A ← aS
B ← bA
C ← cA
B ← dC
https://gyazo.com/ef47894d05a71d085fb31cdd9527910e.png
正規表現のパタンマッチ
Aho-Corasick法
grep方式
egrep方式
Aho-Corasick法
(文字列1|文字列2|...)の形のパタンの認識
KMP法の拡張
失敗関数を使用(KMP法よりも複雑)
fgrepコマンドで使用
例: ac|baa|bacd|ba|bbの認識
https://gyazo.com/7926b6c03cc66c5f883d4aa2a4a14da7.png
grep方式
UNIXのgrepコマンドで使用
*、?などのパタンを受け持つ関数を再帰的に呼ぶことによりパタンマッチを行なう
abc|defのようなパタンを認識できない
表現は美しいが速度は遅い
egrep方式
UNIXのegrepコマンドで使用
任意の正規表現パタンを使用可能
アルゴリズム
正規表現からNFA(非決定性状態遷移機械)を作成
NFAからDFA(決定性状態遷移機械)を作成
DFAを表現する遷移テーブルを作成
パタン作成の手間はかかるがパタンマッチ実行は高速
非決定性状態遷移機械の例
パタン (SUB)*SECTION
https://i.gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png
変換計算
https://gyazo.com/d9e5779fe46637b3fedf7783e0e2d1d3.png
変換された決定性状態遷移機械
https://i.gyazo.com/c74f45af19228955d3a50cb796d6781b.png
もとの非決定性状態遷移機械
https://i.gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png
正規表現でできないこと
数を数えられない
状態を保持できない
曖昧マッチができない
曖昧パタンマッチ
1文字誤り/2文字誤り...を許す検索
文字欠落/余分な文字/文字違い
正規表現では表現しづらい
e.g. abacの1文字欠落 → bac|aac|abc|aba
曖昧検索アルゴリズム
agrep
シフタアルゴリズムを拡張
ピテカン検索
曖昧検索を行なう状態遷移表作成/使用
曖昧検索状態遷移機械の例
https://gyazo.com/33d3ba9323939d1f9426a25d24184078.png
パタンマッチ実行例
https://gyazo.com/33a87ab418c6e283073219e7d021d387.png
正規表現を使った変わった検索
正規表現展開+曖昧検索
Migemo検索
正規表現にマッチする文字列生成
(sub)*section にマッチする文字列
⇒ "section", "subsection", "subsubsection", ...
状態遷移機械を順番にたどって自動生成可能
正規表現の例
`(時計|時間|時刻)を(0|1|2|3|4|5|6|7|8|9|10|11|12)時に(セットする|設定する|あわせる)'
時計を0時にセットする
時計を0時に設定する
時計を0時にあわせる
時計を1時にセットする
時計を1時に設定する
時計を1時にあわせる
時計を2時にセットする
時計を2時に設定する
...
正規表現展開+曖昧検索
展開した文字列を曖昧検索する
「時刻を4時設定する」
「時を4時にセットする」
re_expand.rb
code:ruby
require 'rubygems'
require 're_expand'
'(月|火|水|木|金)曜(1|2|3|4|5|6)限)'.expand { |s,a|
puts s
}
実行結果
code:text
月曜1限
月曜2限
月曜3限
月曜4限
月曜5限
月曜6限
火曜1限
火曜2限
火曜3限
火曜4限
...
Migemo検索
漢字をローマ字から検索する
検索と入力の共通化
予測入力辞書を検索に利用
入力できるものは必ず検索できる!
Migemoの手法
「増井」の入力
「ま」を入力し、「また」「真面目」「増井」などから「増井」を選択
「増井」の検索
「ま」を入力し、(また|真面目|増井)というパタンでテキストを検索
中規模なテキスト検索
インデクス作成をサボる
絞ったテキストに対してパタンマッチを適用
シグナチャ法
単語をビット列で表現
「単語」→ 0000000100000000
「表現」→ 0000000000001000
単語のビット列のORで文書を表現
「単語の表現」→ 0000000100001000
検索文字列のビット表現とANDをとることにより検索
別単語が同じビット列になることがあるので誤検索がおこる
キーワード検索の限界
良いキーワードを考える必要がある
漠然とした検索が不可能
現在のところ主流だが将来は不明
その他の検索システム
ページランク
Google創設者の発明
ページの内容でなくリンクで重要度を判定
高い評価のページからリンクされるとランクが上がる
人力の勝利
https://i.gyazo.com/bf2b2e2007b7d9ef0eb6c3d39e41ecbd.png
Ｘ＝Ｚ ＸはＺの発する唯一のリンクを受けている
Ｙ＝X/2 YはＸの発する2つのリンクのうち、ひとつを受けている
Ｚ＝X/2＋Ｙ ＺはＸの発する2つのリンクのうちひとつを受け、かつＹの発する唯一のリンクを受けている
⇒ X : Y : Z = 0.4 : 0.2 : 0.4
芋蔓検索
これは何でしょう?
https://gyazo.com/03435fbba38fe55a3572342c2bde1118.png
みつかった経緯
https://gyazo.com/03435fbba38fe55a3572342c2bde1118.png
絵に描く⇒ 人に見せて聞く ⇒ 花散里という図柄だ ⇒「源氏香図」のひとつ
https://gyazo.com/02f55f00aca0f66a51ac1314e2ad0544.png
日付、内容、置き場所の近いデータを近くに表示
https://gyazo.com/49ff2980552894951bb1a1e0e12368a7.png
近傍関係の例
https://gyazo.com/9ff211e2c2f30b87fe047ecff7bd0f49.png
これは誰?
https://gyazo.com/dca92d28dd9908386d3d714e5f89324c.png
リンク関係にもとづく検索
Gyazzでの例
http://gyazz.com/UIPedia/Scott%20R.%20Klemmer https://gyazo.com/a738125c5136a92bdcb96cab19768e28.png
デモ: Gyazzによる近傍検索
https://gyazo.com/a061817dd0d4aed5601ec8777a99e19a.png
芋蔓書籍検索
電子書籍の購入情報利用
書籍を選択すると関連書籍がリストされる
https://gyazo.com/99c6fa89f9e6506076af59f9a2685494.png
KWIC (Keyword in Context) 検索
検索単語の周囲の文章も表示する
https://gyazo.com/87392290feca02abd1905e594e965377.png
KWICで芋蔓検索
https://gyazo.com/f0024adc81aa0e17212ba6b11474a437.png
https://gyazo.com/3c725d96d915aabc254d6eebb76ea9fd.png
位置情報からの検索
大変強力だが個人の努力が必要
他のサービスとの連係で変わってくるかも
https://gyazo.com/a9046001433d00c785d7b9770d18ad45.png
インクリメンタル検索 / 曖昧検索
Web上ではまだまだ少ない
試行錯誤中?
「Googleインスタント検索」
https://i.gyazo.com/cb5f732f4696e0b85310eb9b467967d4.png
デモ: ズーミング検索と近傍検索の組みあわせ
https://gyazo.com/20c6deb3153f8743975602366ddfee9c.png
もしかして検索
最近のGoogleの機能
「もしかして」アルゴリズム実験中?
2010は直ってた
その後よく再発している
情報視覚化システム
情報視覚化 = 検索システム
対話的な情報視覚化システムが多数存在
情報視覚化システムは後の講義で解説
参考文献