3. 検索システム

資料

講義ページ (on Scrapbox)

参考情報いろいろ

Twitter

@masui_sfc

@masui

ハッシュタグ: #sfcid2017

個人プロジェクトをScrapbox上に作成

sfc-id2017-CNSログインアカウント

e.g.

ソフトウェアは進化しない説

https://gyazo.com/995e11acb4a37d8dbb697ae05cbfa4ee http://herpolhode.com/rob/utah2000.pdf

本日の話題

情報検索システム

情報検索インタフェース

結論

検索システム研究の歴史は長い

テキスト検索研究は終了気味

画像検索などに期待

検索インタフェースはまだまだ

インクリメンタル検索や検索単語の補完すら最近の話

人生は検索である!?

仕事や生活のかなりの部分は情報検索

本質的に情報を生成/加工することは稀

例1: メールの送信

メールソフトを捜す

メール作成ボタンを捜す

送り先アドレスを捜す

送るべきメッセージを捜す (入力する)

添付ファイルを捜す

送信ボタンを捜す

...

例2: 趣味

良いレストランを捜す

面白い番組を捜す

面白い映画を捜す

面白いニュースを捜す

聞きたい音楽を捜す

面白い展覧会を捜す

掘り出し物を捜す

例3: 計算機のGUI

メニュー

プログラムや機能を捜す

アイコン

プログラムやデータを捜す

フォルダ

階層的分類にもとづいて情報を捜す

スクロールバー

画面に入りきらない情報から必要な部分を捜す

情報検索の歴史

テキスト検索研究時代

インターネット黎明期

人力検索時代

統合的検索時代

テキスト検索研究時代 (〜1995)

「Information Retrieval」

ACM SIGIRが研究の中心

テキスト全文検索

一般人が検索システムを使うことは稀

研究は枯れてきていた印象

マルチメディア検索は盛り上がらず

インターネット黎明期 (〜2000)

従来の研究者がサーチエンジンを実装

Lycos, AltaVista, Inktomi, ...

テキスト検索システムの認知が広まる

人力検索時代 (〜2010)

Google登場!

ページランク = 人力リンクを利用

テキストの中身よりも人力情報を重視

ソーシャルフィルタリング

ソーシャルブックマーク

統合的検索時代 (～2020)

あらゆる付帯情報を検索に利用

位置情報、時間情報、etc.

漠然とした情報から正しい情報を検索

新しいテキスト検索技術

SVM, LSI, ...

新しいAI技術検索 (～2030?)

テキスト検索

検索対象の規模と検索手法

大規模

インデクス作成

小規模

パタンマッチ

中規模

両者の組み合わせ

大規模なテキスト検索

長い研究の歴史がある

Information Retrieval (IR)

ACM SIGIR (Special Interest Group on Information Retrieval

インデクスを作成しておくのが普通

構造があるもの = データベース

それ以外の検索 = IR

適合率と再現率

Precision (適合率)

正しい検索結果 ÷ 全検索結果

Recall (再現率)

正しい検索結果 ÷ 正しい全情報

適合率と再現率

http://masui.sfc.keio.ac.jp/dbee8fd0f7e8f192bc024f4d49e9d4e9.graffle http://gyazo.com/aa28558496ec2d2ad76d23619ce71a43.png

理想は両方100%

実際はトレードオフがある

F値 = $ 2 \over {{ 1 \over {Recall}} + {1 \over {Precision}}}

ブーリアン検索

文書中に単語が含まれているかを検索

単語文書行列を利用

http://gyazo.com/7e30f277ce8b72bdb57a37f9fde7c63b.png

ブーリアン検索

利点

AND/OR/NOT検索が可能

e.g. Brutus AND Caesar but NOT Calpurnia

欠点

表が巨大になる

文書ランキングができない

転置インデクス

単語文書行列を小さく表現

http://gyazo.com/8c1dfea7b39d97dfcf9f5f69416e0658.png

単語の扱い

単語切り出し

文書から単語を区切って切り出す

正規化

活用形の処理

ステミング

ストップワードを除去 (前置詞など)

to be or not to be

ベクトル空間モデル

文書と検索文字列を単語ベクトルで表現

ベクトルの内積で類似度を評価

単語文書行列

http://gyazo.com/5d8bf7d946262da0b78887494b276900.png

ベクトル空間モデル

出現頻度にもとづく単語の重みづけ

tf-idf と呼ばれる重みが一般的

tf: Term Frequency

idf: Inverse Document Frequency

$ W_{ij} = TF_{ij} \times IDF_i

$ TF_{ij} = 文書j中の単語iの出現頻度

$ IDF_i = \log(N / DF_i)

$ DF_i = 全文書中の単語iの出現頻度

「連想検索」

情報学研究所の高野氏が提案

ベクトル空間モデルの検索システムにオシャレなFlashインタフェースをつけたもの

GETAを利用

GETA

単語/文書行列WAM(Word-Article Matrix)ライブラリ

連想検索ライブラリ

クラスタリングライブラリ

使いやすくするライブラリ by 増井俊之.icon

新書マップ

http://gyazo.com/d2ee52573898e150ccc0fb5ac20edce1.png

想-IMAGINE Book Search

http://gyazo.com/ce482951a5a90407d1abfc1f02eda035.png

適合フィードバック(Relevance Feedback)

検索結果を検索文字列にフィードバック

自動的でも手動でもよい

マッチ上位項目のカテゴリをキーワードに追加するのが有効

検索結果向上に着実な効果

適合フィードバックの問題

ユーザーはフィードバックしたがらない

検索行動を長引かせたくない

クエリが長くなる

ユーザは再現率に興味が無い

クエリ拡張

http://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: aaaaaaaaaaaaaaaaab

P: aaaaaab

...

T[n-m+1..n]とP[1..m]を比較

最悪の場合約 $ n \times m 回の文字比較が必要

Knuth-Morris-Pratt法

P[7] (= b)で不一致が検出されたとき

前のテキストはaaaaaaであることが既知

P[6] (= a)の比較をやり直せばよい

不一致が検出されたときに比較をやりなおすべきPの文字の位置をあらかじめ「失敗関数」として計算

無駄な比較を繰り返さないようにする

http://gyazo.com/1d7b988f5207f5d70182f576cd28e525.png

Knuth-Morris-Pratt法の例

P = abcaba の場合

http://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]の先から調べればよい

http://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を計算することにより新しい状態を計算

T[c]はあらかじめ計算しておく値で、パタン文字==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

http://gyazo.com/ef47894d05a71d085fb31cdd9527910e.png

正規表現のパタンマッチ

Aho-Corasick法

grep方式

egrep方式

Aho-Corasick法

(文字列1|文字列2|...) の形のパタンの認識

KMP法の拡張

失敗関数を使用(KMP法よりも複雑)

fgrepコマンドで使用

例: ac|baa|bacd|ba|bbの認識

http://gyazo.com/7926b6c03cc66c5f883d4aa2a4a14da7.png

grep方式

UNIXのgrepコマンドで使用

*、?などのパタンを受け持つ関数を再帰的に呼ぶことによりパタンマッチを行なう

abc|defのようなパタンを認識できない

「ソフトウェア作法」に解説有り

表現は美しいが速度は遅い

egrep方式

UNIXのegrepコマンドで使用

任意の正規表現パタンを使用可能

アルゴリズム

正規表現からNFA(非決定性状態遷移機械)を作成

NFAからDFA(決定性状態遷移機械)を作成

DFAを表現する遷移テーブルを作成

パタン作成の手間はかかるがパタンマッチ実行は高速

非決定性状態遷移機械の例

パタン (SUB)*SECTION

http://gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png

変換計算

http://gyazo.com/d9e5779fe46637b3fedf7783e0e2d1d3.png

変換された決定性状態遷移機械

http://gyazo.com/c74f45af19228955d3a50cb796d6781b.png

変換された決定性状態遷移機械

http://gyazo.com/c74f45af19228955d3a50cb796d6781b.png

(もとの非決定性状態遷移機械)

http://gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png

正規表現でできないこと

数を数えられない

状態を保持できない

曖昧マッチができない

中規模なテキスト検索

インデクス作成をサボる

絞ったテキストに対してパタンマッチを適用

シグナチャ法

単語をビット列で表現

「単語」→ 0000000100000000

「表現」→ 0000000000001000

単語のビット列のORで文書を表現

「単語の表現」→ 0000000100001000

検索文字列のビット表現とANDをとることにより検索

別単語が同じビット列になることがあるので誤検索がおこる

検索と直接操作

直接操作

連続的

可逆的

直感的

直接操作的な検索

検索条件を変えるとすぐ結果が変化

検索条件を戻すともとに戻る

当然の話だがいまだにポピュラーではない

インクリメンタル検索

検索文字を入力するたびに結果が変化

Emacsの検索

乗換案内

Google Suggest

「乗換案内」

http://gyazo.com/f0e800ae8648adac94c020bd61951a79.png

Migemo

Emacsの日本語インクリメンタル検索

http://gyazo.com/de4be34b79fe5fab36f765428f69c806.png

Demo: Migemo

テキスト検索の限界

Googleに満足してますか?

良いキーワードを考える必要がある

漠然とした検索が不可能

現在のところ主流だが将来は不明

キーワード以外の検索手法

ページランク

近傍検索

ズーミング検索

位置利用検索

曖昧検索

ファセット検索

ページランク

Google創設者(Larry Page)の発明

ページの内容でなくリンクで重要度を判定

高い評価のページからリンクされるとランクが上がる

人力の勝利

Larry Page

https://gyazo.com/5a7ea84315f9ec3569afb46f070aa3d3

ページランク

http://gyazo.com/bf2b2e2007b7d9ef0eb6c3d39e41ecbd.png

Ｘ＝ＺＸはＺの発する唯一のリンクを受けている

Ｙ＝X/2 YはＸの発する2つのリンクのうち、ひとつを受けている

Ｚ＝X/2＋ＹＺはＸの発する2つのリンクのうちひとつを受け、かつＹの発する唯一のリンクを受けている

⇒ X : Y : Z = 0.4 : 0.2 : 0.4

芋蔓検索

これは何でしょう?

http://gyazo.com/03435fbba38fe55a3572342c2bde1118.png

みつかった経緯

http://gyazo.com/03435fbba38fe55a3572342c2bde1118.png

絵に描く

⇒ 人に見せて聞く

⇒ 花散里という図柄だ

⇒ 「源氏香図」のひとつ

近傍検索システム

日付、内容、置き場所の近いデータを近くに表示

http://gyazo.com/49ff2980552894951bb1a1e0e12368a7.png

近傍関係の例

http://gyazo.com/9ff211e2c2f30b87fe047ecff7bd0f49.png

リンク関係にもとづく検索

Scrapboxでの例

https://gyazo.com/2c70348a630a341146bc9fcba90b3111 https://scrapbox.io/UIPedia/Scott%20R.%20Klemmer

ズーミング検索

情報視覚化テクニックを併用

http://gyazo.com/cb5f732f4696e0b85310eb9b467967d4.png

位置情報からの検索

強力だがまだ大変

他のサービスとの連係で変わってくるかも

ズーミング写真検索

https://gyazo.com/b545e286d2692b42ade2ec90b11af33f http://www.pitecan.com/tmp/RainbowZoomer/photobrowser2.html#%E3%83%AF%E3%82%A4%E3%83%B3

もしかして検索

Googleの曖昧検索

「完済標語」で検索すると「関西兵庫」ばかり出た (2009)

現在は直っている

ファセット検索

ユーザーに価値がある絞り込み条件をあらかじめ用意

楽な操作で絞り込み

各種ECサイトで利用可能

Marti Hearstの資料

http://gyazo.com/13d047dd83955b6d5ea69bdae0390aea.png http://scope.knowledge-works.co.jp/2012/06/%E3%83%87%E3%82%A3%E3%83%AC%E3%82%AF%E3%83%88%E3%83%AA%E6%A4%9C%E7%B4%A2-vs-%E3%83%95%E3%82%A1%E3%82%BB%E3%83%83%E3%83%88%E6%A4%9C%E7%B4%A2/

「洗濯機」を選択すると洗濯機製造メーカーだけ表示される

検索結果がゼロになることがない

その他の検索

画像検索

動画検索

音声検索

展望

新しい検索手法とインタフェース手法の組み合わせが望まれる