検索モデル

情報検索システムの核となるのは 検索モデル。文書検索システムの場合、

検索質問: ユーザが入力する検索語群
検索対象: 語の集合で表現された文書群

これらを何らかの方法で比較し、検索質問に適合する文書を見つけ出す仕組みのことを検索モデルと呼ぶ。

索引比較によって検索を行う検索モデル

ブーリアンモデル
ベクトル空間モデル
確率モデル
ファジィ集合モデル
拡張ブーリアンモデル
ネットワークモデル
クラスタモデル

ここでは重要な2つだけを取り上げる。

ブーリアンモデル

検索質問を AND, OR, NOT などの論理演算子を使って論理式で表現し、検索する方法。
検索質問の論理式に対して各文書が真か偽かを判定するモデル
- 真と偽の中間はなく、ランク付けはできない。

ブーリアンモデルでは、検索質問を構成する語がそれぞれ、その語を含む文書集合と対応している。よって、論理演算子による演算は、文書集合どうしの集合演算と考えることができる。例えば、語 t₁ と語 t₂ の両方が出現する文書集合を得たい場合、検索質問は次のようになる。

t₁ AND t₂

これは t₁ を含む文書集合と、 t₂ を含む文書集合との交わりを表している。それぞれの集合を {d₁, d₃, d₄, d₅}、 {d₁, d₂, d₃} であるとすれば、交わりは {d₁, d₃} となる。

検索モデル

検索システムとしては、以下の仕組みが必要。

語 t が出現する文書群を知る仕組み
集合演算を高速に実現する仕組み

前者を実現する構造は、転置ファイル (inverted file) と呼ばれる。「転置」という名の由来は、ある文書においてどんな語が出現しているか、の逆であるため。

転置インデックス (wikipedia)

語	文書ID	出現頻度
t₁	d₁	1
	d₃	5
	d₄	2
	d₅	3
t₂	d₁	3
	d₂	3
	d₃	2

単純なブーリアンモデルでは出現頻度の情報は不要だが、モデルに何らかの拡張をして頻度情報を利用することが多い。

ベクトル空間モデル

文書内での語の出現位置、語と語の前後関係などを無視する場合、文書を単語の集合 (bag of words) として扱うことができる。検索質問も同様。
索引語-文書行列を思い出すと、ある文書 d_j における語の出現状況は、行列の1列 (j列) で表される。これは、文書が語の異なり数(種類数)を次元とするベクトルで表現されていることを意味する。

		d₁	d₂	d₃	d₄	d₅
t₁	\|	1	0	5	2	3	\|
t₂	\|	0	3	3	2	0	\|
t₃	\|	3	2	0	4	0	\|
t₄	\|	6	6	8	7	5	\|
t₅	\|	4	1	4	0	0	\|
t₆	\|	0	5	0	3	2	\|

d₁ の文書ベクトル = [ 1 0 3 6 4 0 ]

ベクトル空間モデル

		d₁	d₂	d₃	d₄	d₅
t₁	\|	1	0	5	2	3	\|
t₂	\|	0	3	3	2	0	\|
t₃	\|	3	2	0	4	0	\|
t₄	\|	6	6	8	7	5	\|
t₅	\|	4	1	4	0	0	\|
t₆	\|	0	5	0	3	2	\|

d₁ の文書ベクトル = [ 1 0 3 6 4 0 ]

文書ベクトルの次元数: 文書集合において現れる語の数
文書集合内の各文書の文書ベクトルは同じ次元(要素数)
- 1文書に出現する語の異なり数は限られているため、値 0 の要素が多くなる
検索質問についても、同じ次元のベクトルで表現する
- ほとんどの要素は値が 0 となる

検索質問と各文書が同じ次元のベクトルで表現されれば、どちらも同じ次元のベクトル空間に存在していることになる。そして、検索質問に最も適合する文書を探すことは、検索質問ベクトルに最も類似する文書ベクトルを探すことと同じとなる。この計算モデルをベクトル空間モデル (vector space model) という。

ベクトル空間モデル

ベクトルの類似度

内積を使う方法や、コサイン (余弦) を使う方法など、さまざまなものが提案されている。最もよく用いられているのはコサイン (コサイン類似度と呼ぶことも)。コサインはベクトルのなす角に対応するものなので、ベクトルの大きさ (ノルム) は無視することになる。これは語の重みの絶対値によらず、語と語の重みのバランスが似通っている文書を類似度が高いとする方法であるといえる。

ベクトル空間モデルでは、類似度により文書のランキングが可能。一方、AND や OR のような論理演算はできない。

簡単な実装

まず転置ファイルを用いて、検索質問の語を1つでも含む文書の集合を求める。
その文書集合内の各文書に対して、検索質問との類似度をベクトル計算により求める。
その類似度によりランキングする。

速度を度外視すれば、比較的簡単なプログラムで実現することができる。

実装例: WAMと連想検索 (1)

索引語-文書行列を WAM(Word-Article Matrix) と呼ぶ。
行列の要素を文書内の単語頻度(tf)とする。

実装例: WAMと連想検索 (2)

WAM は文書数が多いと巨大な行列になる。ただし、0 の要素が非常に多い。
0 の部分を圧縮してメモリに載せると、高速な検索が可能。

実装例: WAMと連想検索 (3)

WAM を用いた連想検索エンジン GETA

文書で検索/再検索ができる。

実装例: WAMと連想検索 (4)

連想検索を利用したサービス

Web magazine 風 (新書の検索)
新書マップ (ノンフィクション・教養系の新書・選書)

新書マップの開発スタッフには本学科の卒業生が参加 (完成後 Yahoo! Japan に転職)

Webページ検索: リンク構造解析

Webの検索エンジンでは、Webページ間のリンク構造を利用したランキングが行われている。リンクを張っているのはWebコンテンツの作成者であるので、これは集合知の一種と考えることができる。

代表的アルゴリズム

PageRank (Google)
HITSアルゴリズム (YST = Yahoo! US)

PageRank: リンク構造解析

Google 検索が採用しているアルゴリズムは非公開であるが、その基礎となるアルゴリズムは PageRank(ページランク)と呼ばれ、広く知られている。

PageRank は「多くの良質なページからリンクされているページは、やはり良質なページである」 という考え方に基づいて、全てのページの重要度(=PageRank)を求める。これは再帰的な関係であるため、行列計算が必要となる。

PageRank の概念図 (Page et al. (1998) Figure 2 'Simplified Page Calculation' より引用(の引用))

Google の秘密 - PageRank 徹底解説 (馬場肇氏)
- 「2. PageRank の基本概念」を参照

HITSアルゴリズム: リンク構造解析

リンク構造解析を用いる手法の代表例として、PageRank より若干複雑な HITSアルゴリズムがある。 HITSアルゴリズムでは、重要なノードとしてオーソリティとハブの2種類を考え、リンク集的なサイト(ハブ)を別に扱っているところに特徴がある。

オーソリティ: 良質なサイト
ハブ: 良質なサイトにリンクを張る、良質なリンク集

参考サイト

HITSアルゴリズムとは (SEO検索エンジン最適化)
HITS, 主成分分析, SVD (naoyaのはてなダイアリー)

リンク構造解析の応用

PageRank の「多くの良質なページからリンクされているページは、やはり良質なページである」 という考え方は、ハイパーリンクと似た関係にあるものに応用できる。

いい論文から参照されている論文ほどいい論文
いいユーザからフォローされている人はいいユーザ

参考: ネットワーク分析

ソーシャルネットワークの分析では、リンク構造解析よりもネットワーク分析の手法が役立つ。

群衆の英知もしくは狂気

Webページ検索のランキング

リンク構造解析はページの良し悪しを教えてくれるが、検索語に対する良し悪しではない。

検索語の出現場所
- 段落内、見出し内、ページのタイトル内...
サイトの性質
- 公式サイトか、CGM(掲示板、ブログ、ソーシャルメディア)か、まとめサイトか...

さまざまな指標を反映させてランキングをしている。

SEO

SEO (Search Engine Optimization; 検索エンジン最適化)

Webページの検索結果の順位を上げる工夫
商売になっている

意味のある対策

キーワードを画像にしない。
見出しをきちんと書く。
まともなサイトからリンクを張ってもらう。

不正な対策

見えないようにキーワード群を並べる。
関連サイトでリンクを張りあう。

不正に順位を操作したと見なされると検索結果から除外され「Google八分」となる。

ズバリ、検索で1位になる方法をこっそり教えてください！／グーグルの金谷武明さんに聞いてきた [参考]

情報アクセスと知的処理 (4)