インタフェース設計論 授業ページ
3. 検索システム
資料
講義ページ (on Scrapbox)
参考情報いろいろ
Twitter
ハッシュタグ: #sfcid2017
個人プロジェクトをScrapbox上に作成
sfc-id2017-CNSログインアカウント
ソフトウェアは進化しない説
本日の話題
情報検索システム
情報検索インタフェース
結論
検索システム研究の歴史は長い
テキスト検索研究は終了気味
画像検索などに期待
検索インタフェースはまだまだ
インクリメンタル検索や検索単語の補完すら最近の話
人生は検索である!?
仕事や生活のかなりの部分は情報検索
本質的に情報を生成/加工することは稀
例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 (再現率)
正しい検索結果 ÷ 正しい全情報
適合率と再現率
理想は両方100%
実際はトレードオフがある
F値 =
ブーリアン検索
文書中に単語が含まれているかを検索
単語文書行列を利用
ブーリアン検索
利点
AND/OR/NOT検索が可能
e.g.
Brutus AND Caesar but NOT Calpurnia
欠点
表が巨大になる
文書ランキングができない
転置インデクス
単語文書行列を小さく表現
単語の扱い
単語切り出し
文書から単語を区切って切り出す
正規化
活用形の処理
ステミング
ストップワードを除去 (前置詞など)
to be or not to be
ベクトル空間モデル
文書と検索文字列を単語ベクトルで表現
ベクトルの内積で類似度を評価
単語文書行列
ベクトル空間モデル
出現頻度にもとづく単語の重みづけ
tf-idf と呼ばれる重みが一般的
tf: Term Frequency
idf: Inverse Document Frequency
文書j中の単語iの出現頻度
全文書中の単語iの出現頻度
「連想検索」
情報学研究所の高野氏が提案
ベクトル空間モデルの検索システムにオシャレなFlashインタフェースをつけたもの
GETAを利用
GETA
単語/文書行列WAM(Word-Article Matrix)ライブラリ
連想検索ライブラリ
クラスタリングライブラリ
使いやすくするライブラリ by
適合フィードバック(Relevance Feedback)
検索結果を検索文字列にフィードバック
自動的でも手動でもよい
マッチ上位項目のカテゴリをキーワードに追加するのが有効
検索結果向上に着実な効果
適合フィードバックの問題
ユーザーはフィードバックしたがらない
検索行動を長引かせたくない
クエリが長くなる
ユーザは再現率に興味が無い
クエリ拡張
シソーラス利用
ログ利用
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]
を比較 最悪の場合約 回の文字比較が必要
Knuth-Morris-Pratt法
P[7]
(= b
)で不一致が検出されたとき 前のテキストは
aaaaaa
であることが既知 P[6]
(= a
)の比較をやり直せばよい 不一致が検出されたときに比較をやりなおすべきPの文字の位置をあらかじめ「失敗関数」として計算
無駄な比較を繰り返さないようにする
Knuth-Morris-Pratt法の例
P =
abcaba
の場合 5 → 1 の遷移
5の状態でテキストの最後が
abca
であることが既知 →2の状態まで戻れる
5から6に遷移できない場合
次の文字は
b
でない →1の状態まで戻れる
Boyer-Moore法
最速といわれるテキスト検索アルゴリズム
文字比較回数が文字列長より少なくてすむ
KMP法ではテキストの文字をすべて比較しなければならない
パタンの右端からマッチを調べる
1回目の文字比較で
T[m] = c
であることがわかる c
はPに含まれていないので2回目の比較は T[m+1]
の先から調べればよいBoyer-Moore法 (Cont'd)
右からk文字だけ一致したときにその次にどこから比較を再開すればよいかをあらかじめパタンから計算
2個の表を用意
d1 -- 右端で不一致が検出されたときの、
移動数[不一致文字]
の表 d2 -- 右からk文字目で不一致が検出されたときの、
移動数[不一致位置]
の表 先の例の場合、
d1['a']
= 1, d2['c']
= d1['d']
= ... = 8である。シフタアルゴリズム
長さの文字列検索のマッチ状態をビットで表現
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)
[]
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
正規表現のパタンマッチ
Aho-Corasick法
grep方式
egrep方式
Aho-Corasick法
(文字列1|文字列2|...)
の形のパタンの認識 KMP法の拡張
失敗関数を使用(KMP法よりも複雑)
fgrepコマンドで使用
例:
ac|baa|bacd|ba|bb
の認識grep方式
UNIXのgrepコマンドで使用
*
、 ?
などのパタンを受け持つ関数を再帰的に呼ぶことによりパタンマッチを行なう abc|def
のようなパタンを認識できない 「ソフトウェア作法」に解説有り
表現は美しいが速度は遅い
egrep方式
UNIXのegrepコマンドで使用
任意の正規表現パタンを使用可能
アルゴリズム
正規表現からNFA(非決定性状態遷移機械)を作成
NFAからDFA(決定性状態遷移機械)を作成
DFAを表現する遷移テーブルを作成
パタン作成の手間はかかるがパタンマッチ実行は高速
非決定性状態遷移機械の例
パタン
(SUB)*
変換計算
変換された決定性状態遷移機械
変換された決定性状態遷移機械
(もとの非決定性状態遷移機械)
正規表現でできないこと
数を数えられない
状態を保持できない
曖昧マッチができない
中規模なテキスト検索
インデクス作成をサボる
絞ったテキストに対してパタンマッチを適用
シグナチャ法
単語をビット列で表現
「単語」→
0000000100000000
「表現」→
0000000000001000
単語のビット列のORで文書を表現
「単語の表現」→
0000000100001000
検索文字列のビット表現とANDをとることにより検索
別単語が同じビット列になることがあるので誤検索がおこる
検索と直接操作
直接操作
連続的
可逆的
直感的
直接操作的な検索
検索条件を変えるとすぐ結果が変化
検索条件を戻すともとに戻る
当然の話だがいまだにポピュラーではない
インクリメンタル検索
検索文字を入力するたびに結果が変化
Emacsの検索
乗換案内
Google Suggest
「乗換案内」
Migemo
Emacsの日本語インクリメンタル検索
Demo: Migemo
テキスト検索の限界
Googleに満足してますか?
良いキーワードを考える必要がある
漠然とした検索が不可能
現在のところ主流だが将来は不明
キーワード以外の検索手法
ページランク
近傍検索
ズーミング検索
位置利用検索
曖昧検索
ファセット検索
ページランク
Google創設者(Larry Page)の発明
ページの内容でなくリンクで重要度を判定
高い評価のページからリンクされるとランクが上がる
人力の勝利
Larry Page
X=Z XはZの発する唯一のリンクを受けている
Y=X/2 YはXの発する2つのリンクのうち、ひとつを受けている
Z=X/2+Y ZはXの発する2つのリンクのうちひとつを受け、かつYの発する唯一のリンクを受けている
⇒ X : Y : Z = 0.4 : 0.2 : 0.4
芋蔓検索
これは何でしょう?
みつかった経緯
絵に描く
⇒ 人に見せて聞く
⇒ 花散里という図柄だ
⇒ 「源氏香図」のひとつ
日付、内容、置き場所の近いデータを近くに表示
近傍関係の例
リンク関係にもとづく検索
Scrapboxでの例
情報視覚化テクニックを併用
位置情報からの検索
強力だがまだ大変
他のサービスとの連係で変わってくるかも
ズーミング写真検索
もしかして検索
Googleの曖昧検索
「完済 標語」で検索すると「関西 兵庫」ばかり出た (2009)
現在は直っている
ユーザーに価値がある絞り込み条件をあらかじめ用意
楽な操作で絞り込み
各種ECサイトで利用可能
「洗濯機」を選択すると洗濯機製造メーカーだけ表示される
検索結果がゼロになることがない
その他の検索
画像検索
動画検索
音声検索
展望
新しい検索手法とインタフェース手法の組み合わせが望まれる