Web検索エンジンのヒット件数のロバストな推定

1
¨
¥
§論文 ¦
Technical Papers ¯¯
Web 検索エンジンのヒット件数のロバストな推定
Robust Estimation of Search Engine Counts
友部博教
Hironori Tomobe
産業技術総合研究所
National Institute of Advanced Industrial Science and Technology (AIST)
[email protected], http://www.aist.go.jp/
松尾豊
（同
上）
西村拓一
（同
上）
Yutaka Matsuo
Takuichi Nishimura
[email protected], http://ymatsuo.com/
[email protected], http://staff.aist.go.jp/takuichi.nishimura/
keywords: 検索エンジン，ヒット件数，Google，セマンティック Web，自然言語処理
Summary
Various studies within NLP and Semantic Web use the search engine count on a query returned
by a search engine (such as Google, Yahoo! and MSN). However, sometimes the search engine count is
unreliable, especially when the count is large. As the search engine counts gain increasing importance in
many systems, it is of prominent importance that some means be made available to make the results more
robust and independent from a particular specification of a search engine. In this paper, we propose a novel
algorithm that estimates the search engine count robustly. It (i) uses the co-occurrence of terms as evidence
to estimate the occurrence of a given word, and (ii) integrates multiple evidence for robust estimation. We
evaluated our algorithm for more than 2000 queries on three datasets using Google, Yahoo! and MSN search
engine; results showed that it can estimate search count counts with correlation of greater than 0.95. It also
provides estimate counts for any module that judges a web page as positive or negative. Consequently, we
can estimate the number of documents with included references of a particular person (among namesakes)
on the entire web.
1. はじめに
Web 上には，あらゆる人があらゆるトピックについて
何でも書くことができるため，膨大な Web ページが存
在する．そこから自分に必要な Web ページを探し出す
ことを手助けしてくれるのが検索エンジンであり，我々
は Web を利用する上で検索エンジンに頼る部分が大き
い．さらに，検索エンジンを本来の「Web ページを探し
出す」という直接的な目的だけではなく，検索エンジン
の検索結果を利用する仕組みも増えてきた．特にセマン
ティック Web や自然言語処理の研究において，検索エン
ジンをオントロジー構築や知識獲得，FAQ 生成などに利
用する研究が出現し，Web の持つ潜在能力が注目されて
いる [松尾 07]．
セマンティック Web の文脈において，Web 上に存在す
る膨大な Web ページから，高度なサービスの提供や Web
構造の解析を行うことが課題になる．そこで大きな役割
を担うのが検索エンジンである．例えば，Cimiano らの
開発した，Web ページの固有表現のパターンを Google
を使って解析することで，自動あるいは半自動アノテー
ションを行う PANKOW というシステム [Cimiano 04]
や，松尾らの開発した，Google に二人の氏名を入力し
ヒット件数から関係性の指標を得ることで，コミュニティ
内のメンバー同士のソーシャルネットワークを抽出する
POLYPHONET というシステム [Matsuo 06] もある．
さらに検索エンジンにフレーズを入力し検索結果から抽
出した，オントロジーとソーシャルネットワークの関係
性を調査した研究 [Mika 05a, Mika 05b] もある．
一方自然言語処理の研究では，大量の Web ページを
含む Web が巨大なコーパスとして注目され，Web 上の
ページから情報を抽出する検索エンジンの役割が重要視
されている [Kilgarriff 03]．ニュースやブログなど日々変
わりゆくトピックはすぐに Web に反映されるため，Web
をコーパスに使うことで新しいトピックのシソーラスを
自動に構築する [Curran 02] ことができる．また Web
をコーパスとして，総称的で抽象的なものを指す上位概
念と，個別の具体的なものを指す下位概念の抽出や，部
分・全体関係の抽出 [Miura 04, Cimiano 04, Hage 06]，
ヒット件数と PMI を算出することによる同義語の識別
[Turney 01] などが可能であり，語の意味類似性を検索
エンジンとテキスト処理によって計算する [Turney 05]
こともできる．
このように多くの研究で検索エンジンが利用されてい
る大きな理由には，次のようなものが考えられる．
• Web 上から任意の語を含む Web ページを取得する
ため
• 統計情報として検索ヒット件数を取得するため
前者は，Hearst Pattern[Hearst 92] のような上位・下
2
位概念を認識するためのクエリパターンの探索などが目
的であり，後者は 2 つの単語の関係性を統計情報となる
検索ヒット件数から推定することを目的とする．例えば，
「友部博教松尾豊」というクエリを検索エンジンに入力
し得られた検索ヒット件数は，二人の関係性の強さの指
標となる．
しかし，検索エンジンが出力するヒット件数には以下
のような問題点がある．
• 検索ヒット件数が大きい場合には，正確な値ではな
く近似的な値を示すことがある．
• 検索エンジンのインデックスの更新タイミングによ
り，得られる検索ヒット件数が検索するたびに異な
る [Manning 07]．
通常の Web ページ検索という目的において，検索ヒット
件数の誤差は大きな問題とはならないが，検索ヒット件
数を統計情報として扱うオントロジー構築やソーシャル
ネットワーク抽出では検索ヒット件数の精度は抽出結果
に大きく影響する．
本論文では入力されたクエリのヒット件数を，検索エ
ンジンから出力される検索ヒット件数を用いて推定する
手法を提案する．また，検索エンジンから出力される検
索ヒット件数に誤差が生じた場合にも，複数の検索結果
を用いることでロバストに推定することができる．提案
手法では，複数の検索結果を得るために，入力されたク
エリと任意の語集合との共起ヒット件数を利用する．共
起ヒット件数とは，複数の語を検索エンジンに入力する
ことによって得られるヒット件数であり，クエリに含ま
れる語が共起する Web ページの出現頻度を意味する．例
えば，“A”というクエリの検索ヒット件数を推定するた
めに “A AND X”というクエリを用意し，A と X の共
起ヒット件数から逆に，A のヒット件数を求める．ここ
で複数の X を用意し共起ヒット件数を複数取得すること
でロバスト推定を可能にした．このクエリ A に加える語
X をプローブ語と呼ぶ．
そこで，クエリ A との共起ヒット件数が推定に適する
プローブ語 X を探し，検索エンジンから取得した複数の
検索ヒット件数を統合することで，クエリ A を含むヒッ
ト件数を推定する．また，2000 以上のクエリを含むデー
タセットに関して提案手法を適用し評価した結果，正解
となる検索ヒット件数に対し推定値が 0.95 以上の相関
を示した．さらに本論文ではソーシャルネットワーク抽
出における提案手法の応用方法を述べ，セマンティック
Web や自然言語処理に関する研究における本論文の位置
付けを明確にする．
以下，2 章では検索エンジンを用いた Web ページのサ
ンプリング手法と，検索ヒット件数の利用に関する関連
研究を述べる．3 章では，検索件数を推定する手法の詳
細を述べ，共起ヒット件数から検索ヒット件数を推定で
きることを示す．4 章ではロバストに推定を行うために，
複数の指標を用いたプローブ語選択の手法や，プローブ
語から得た共起ヒット件数を統合するアルゴリズムを述
べる．そして 5 章では本論文で提案する手法の評価を行
い，共起ヒット件数からロバストに推定できることを示
す．そして 6 章で本手法の拡張について議論し，7 章で
まとめる．
人工知能学会論文誌
巻 x 号 a（2007 年）
2. 関連研究
現在，Web 上には膨大な数の Web ページが存在する．
しかし Web 上全てのページを調べ上げ，検索クエリを含
むページ全てを抽出することは不可能であるため，Web
全体を推定するには全体の特徴を表現するような標本を
抽出する必要がある．そこで関連研究に，検索エンジン
を用いたサンプリング手法に関する研究をあげる．
まず，Bar-Yossef ら [Bar-Yossef 06] は，検索エンジ
ンのインデックスを用いて，語やフレーズを共有する文
書から生成した仮想グラフ上でランダムウォークを実行
することでサンプリングする手法を提案している．こう
してサンプリングした文書に関して語 A の出現を同定
することで Web 全体での出現頻度を推定できるが，仮
想グラフ生成に膨大な数の Web ページをコーパスに利
用する必要がある．Bharat ら [Bharat 98] は，語彙辞
書における出現頻度の推定値を定式化することにより，
検索エンジンのインデックスをランダムにサンプリング
する手法を提案している．これは複数の検索エンジンの
インデックス数や重複するページ数を推定することが目
的だが，検索ヒット件数の推定に用いることも可能であ
る．本論文の提案手法との詳細な比較は 6 章で述べる．
Anagnostopoulos ら [Anagnostopoulos 05] は，検索エ
ンジン内部のインデックス一覧や document-at-a-time
による評価に基づきサンプリングする手法を提案してい
る．これはヒット件数推定に効果的であるが，各検索エ
ンジンが内部にこの方式を採用しなければ利用すること
ができないという問題点がある．
検索ヒット件数を用いたセマンティック Web や自然言
語処理に関する研究は前章でもいくつか例をあげた．さ
らに加えるなら，Keller ら [Keller 02] のヒット件数の有
効性を分類した研究がある．この研究では，形容詞-名詞，
名詞-名詞，動詞-目的語などの組み合わせをカウントし，
Web 上での出現頻度と British National Corpus(BNC)
のような詳細に作られたコーパスでの出現頻度の相互関
連性を示した．文節のカウントとは別に，Web に基づく
モデルを用いたために，スペル誤り生成，形容詞順序，複
合名詞区切り，可算性の検出などの自然言語処理におけ
る多くのタスクが達成された [Lapata 04]．また，自然
言語処理の応用技術を見据えた検索エンジン構築の試み
もある [Cafarella 05] が，本論文では既存の検索エンジ
ンのインタフェースを用いた手法を提案する．
最近では検索エンジンのヒット件数を人気や話題の指
標に利用することが注目されている．テレビ番組では検
索ヒット件数を話題の指標に利用することがあり，CD
売り上げや映画の興行収入，ニュースや芸能人のスキャ
ンダルなど，検索ヒット件数を注目度の指標として情報
を用いる例もある．また，科学者の氏名の検索ヒット件
数と業績の関係を調査している研究 [Bagrow 04] もある．
この研究では，科学者は業績のアピールの場に Web を
良く使うため，結果的に Web ページ数が増える傾向に
あると指摘している．このように検索エンジンのヒット
件数は社会的に大きな力を持ち始めており，正確な検索
ヒット件数を求める必要性が高まっている．
Web 検索エンジンのヒット件数のロバストな推定
3. 検索ヒット件数の推定
本章では，検索エンジンを用いた検索ヒット件数の推
定手法の基本的な考え方を述べる．推定は語の共起ヒッ
ト件数を用いて行うが，それに伴い生じる問題点の詳細
を考察し，その問題点に対処した推定手法を提案する．
3・1 共起ヒット件数に基づく推定
本論文では，検索エンジンに関する以下の前提から議
論を始める．
(前提) k 件よりヒット件数が少ない場合は値が正確で
ある．
多くの検索エンジンでは，検索結果にトップ k 件を提
示する仕組みになっている (Google や Yahoo!，MSN で
は，1000 件まで検索結果を表示するので k = 1000 とな
る)．特に，検索クエリに該当する Web ページ数が k 件
以下なら，検索エンジン側はそのクエリを含む全ての検
索結果を提示することが可能であり，またその提示され
た全てのページに関して，クエリを正しく含む結果であ
るかどうかを技術的に判断することが可能である．以上
から，この前提は現状の検索エンジンにおいて適切であ
ると言える．
では，ヒット件数が k 件を超える検索クエリ A に対し
て正確なヒット件数 nA を推定する方法を考えよう．ま
ず，検索ヒット件数を k 以下に抑えるような適切な語 X
をクエリに加え，“X AND A”というクエリで絞り込み
検索を行うことでヒット件数 n(X, A) を得る．
（この件
数が k よりも小さければ正確である．
）次に，語 A と語
X の Web 上での出現が独立同分布 (independent and
identically distributed: i.i.d) だとしよう．絞込みに使
う語 X が Web ドキュメントに含まれる確率を p(X) とす
ると，語 A の検索エンジンによる検索ヒット件数 nA は，
n(X, A)/p(X) で推定することができる．語 X の Web
上での出現確率 p(X) は事前に求めておけばよい．
しかし，この手法には以下にあげる二つの問題点がある．
• 推定に関する問題
確率 p(X) を計算するのが困難である．語 X を含む
正確な Web ページ数が必要だが，件数 k を超える
場合には正確ではない．
• 独立同分布に関する問題
語は語の共起には偏りがある [Manning 02, Manning 07] ∗1 ．語 X の Web ページの出現確率 p(X)
が語 A と独立であるという保証はない．
そこで本論文では，拡大率，プローブ語という概念を
導入し，これを解決する．
§ 1 拡大率
まず，語 X の出現特性を学習するための語をトレー
ニング語と呼び，トレーニング語集合 Atrain を用意す
る．次に全ての語 A0 ∈ Atrain と X の共起ヒット件数
n(X, A0 ) を求める．そして語 A0 のヒット件数 n0A と共
起ヒット件数の比率 n0A /n(X, A0 ) の平均値を X の拡大
∗1 例えば「看護士」という語は，
「医者」や「病院」という語と
共に頻出するし，
「保育園」という語は「子ども」や「幼児」と
いう語と共起して出現する．
3
率mX と定義する．これより，語 A のヒット件数の推定
値 n̂A は以下の式で求めることができる．
n̂A = mX × n(X, A)
確率上では，mX は Atrain における 1/p(X) の平均値
の意味を持つことになる．例えば，
「井手剛」氏のヒット件
数を推定することを考えよう．
「井手剛」氏の検索エンジン
Google でのヒット件数は 982 件である．次に，絞込み検
索で「井手剛」と「研究」の語をクエリに入力すると，共
起ヒット件数は 555 件となる．ここで，事前に Atrain を
用いて「研究」という語の拡大率 m研究が 1.741 であると
すると，検索ヒット件数を用いて，555 × 1.741 = 966.2
という計算のもと，ヒット件数の推定することができる．
この場合は実際のヒット件数 982 件と比べれば，適切な
推定ができているといえよう．本手法では，もし「井手
剛」氏の検索ヒット件数が正確にわからない（つまり，検
索結果が k 件を超えてしまう）場合には，
「井手剛」氏と
いう語と他の単語の間の共起件数を使用するだけで推定
できる．
検索クエリで用いる語を増やせば，当然結果は絞り込
まれるので拡大率は理論上 1 より大きくなるはずである．
しかし，検索エンジンや検索語によっては拡大率が１よ
り小さくなることがあった∗2 ．しかしこのような特定の
語で起こる問題や，独立同分布でなく共起の偏りのある
語でも，複数のトレーニング語との共起ヒット件数を用
いることで，その影響を排除することができる．
拡大率が大きい，すなわち語同士の共起関係が弱い場
合にはヒット件数が k 件以下となる可能性が高く，必然
的に信頼できる値となる．しかし，拡大率が大きい場合
には，検索ヒット件数が数件以下，あるいは 0 件というこ
とが起こりうるので，共起ヒット件数から得られるの情
報量は乏しい．そこで，本研究では単純化のために拡大
率の閾値を設け，閾値以下の拡大率を持つ語を排除した．
§ 2 プローブ語
さて，我々が拡大率を求めるために用いる語 X を本
論文ではプローブ語と呼ぶ．本手法では，まず最初にプ
ローブ語の候補となる語の集合 Xcand を用意する．次に
語 A0 ∈ Atrian に対して，共起ヒット件数に偏りのない
プローブ語 Xprobe を候補集合 Xcand から探す．プロー
ブ語の優劣は語集合 Atrain に依存する．例えば，
「研究」
という語は研究者氏名の検索ヒット件数の推定を行うの
に優れている．これは，多くの研究者の氏名を含むペー
ジで，幅広く利用されているため特定の研究者に偏る語
ではないためである．一方で，
「マイニング」や「自然言
語」のような語は，データマイニングや自然言語処理の
研究者の氏名と共起することが多く，プローブ語として
不適切である．また， “the”や “in”のような一般語は研
究者氏名に対して偏りなく共起して出現するが，ストッ
プワードとして扱われることが多いため利用することが
難しい．さらに多くの Web ページで含まれる語でもあ
∗2 “visualization”で検索した場合と， “web AND visualization”で検索した場合，後者は絞込み検索であるにも関わらず
検索ヒット件数が多いということが起こり，拡大率が 1 未満に
あることもある．
4
人工知能学会論文誌
るため，拡大率が小さく推定が困難になる．プローブ語
の選択方法は 4.1 節で詳細に述べる．
本手法では，語の共起の偏りの取り扱いに特色がある．
多くの研究では，語の共起の偏りを重要な要素とし語の
認識を行う [Matsuo 04] など，共起の偏りを積極的に利
用するが，本研究では共起の偏りが少ない語を探すこと
が重要である．特定の文書やコーパスで頻出したり，特定
の語と共起頻度の高い語は特徴的な語と言えるが，本論
文では拡大率の観点から偏りなく出現する語に注目する．
3・2 推定値の統合
次に特定のプローブ語による影響や，検索エンジンに
よる影響を受けづらいロバスト推定の手法を述べる．そ
こで，検索ヒット件数の推定にただ 1 つのプローブ語を
用いるのではなく，複数のプローブ語を利用し得られた
ヒット件数から推定値を統合することで，特定の語によ
る影響を排除する．本論文では複数の指標を統合する方
法として，単一係数による統合と回帰係数による統合の
二つのアプローチを提案する．
§ 1 単一係数による統合
複数のプローブ語を用いるには，各プローブ語から導
き出される推定値をもとに，検索ヒット件数の推定を行
えばよい．もっとも単純な方法は，それぞれのプローブ
語が導き出す推定値を確率変数に基づき重み付けして統
合するものである．検索ヒット件数はベルヌーイ分布と
考えることができる．入力されたクエリーが Web ペー
ジに含まれるか否かを確率変数とすると，含まれる確率
を p とすれば，含まれない確率は q = 1 − p となる．N
ページの Web ページがベルヌーイ分布で存在すると仮
定すると，平均は N p，分散は N pq となる．
正規分布をベルヌーイ分布に近似することができるの
で，m 個のプローブ語に対する
m 個の正規分布があると
P
き，平均値は µ =
µj ×1/σj
P
j
j
1/σj2
で表される．ここで，µj
¶
³
学習フェーズ
(1) トレーニング語集合 Atrain とプローブ語候
補の集合 Xcand を用意する．
(2) トレーニング語 A0 ∈ Atrain に対し，ヒット
件数 nA0 とプローブ語候補 X ∈ Xcand との共
起ヒット件数 n(X, A0 ) を得る．
2
(3) プローブ語候補 X の拡大率 mX ，分散 σX
，
およびプローブ語選択の指標値 sX を求める．
(4) 拡大率の閾値 mthre 以上の拡大率 mX を
持つプローブ語候補 X を指標値 sX の小さいも
のから選び，プローブ語 Xprobe とする．
(5) （回帰係数による統合の場合） X ∈ Xprobe
と A0 の共起ヒット件数 n(X, A0 ) を基に nA0 の
線形回帰を行い，プローブ語 X の係数 kX を計
算する．
µ
´
図 1 学習フェーズ
¶
³
(1) クエリ A を決める．
(2) プローブ語 X ∈ Xprobe と語 A の共起ヒット
件数 n(X, A) を検索エンジンから得る．
(3) (単一係数による統合の場合) 以下の式を計算
する．
P
n̂A =
X∈Xprobe
P
2
mX × n(X, A) × 1/σX
X∈Xprobe
2
1/σX
(1)
これは，推定値が各プローブ語の拡大率の分散の逆数
により重み付けられていることを意味する．よって，拡
大率の分散の大きい語ほど重みが小さくなり，推定値に
与える影響は少なくなる．この統合手法を単一係数によ
る統合と呼ぶ．単一係数による統合では，いくつかのプ
ローブ語から推定値を得ることができなかったとしても，
推定値を計算できるという利点がある．逆に，プローブ語
集合に依存して推定値が大きく異なるという欠点もある．
§ 2 回帰係数による統合
回帰係数による統合では，各プローブ語の共起自体を
属性とみなした上で推定を行う．線形回帰では，プロー
ブ語 X ∈ Xprobe に対し，トレーニング語 A0 の共起頻度
に対する重み kX を学習させる．すると，この重みを用
いて語 A のヒット件数の推定値は以下の式で計算するこ
とができる．
X∈Xprobe
P
n̂A =
2
(mX × n(X, A)/σX
)
X∈Xprobe
2
(1/σX
)
(4) (回帰係数による統合の場合) 以下の式を計算
する．
X
n̂A =
kX × n(X, A)
X∈Xprobe
µ
´
と σj2 は分布 j の平均と分散である．したがって，語 A
のヒット件数の推定値は以下のようになる．
P
巻 x 号 a（2007 年）
図 2 推定フェーズ
n̂A =
X
kX × n(X, A)
X∈Xprobe
この統合手法の利点は，プローブ語同士の共起に偏り
がある場合でも，その影響を排除できることである．そ
の一方で，重み kX を学習するために多くのトレーニン
グデータが必要であり，トレーニングデータが不十分で
あると過学習を起こすという問題もある．
4. アルゴリズム
本章では，ヒット件数推定のためのアルゴリズムを述
べる．アルゴリズムは学習フェーズと推定フェーズの二
つに分かれる．学習フェーズのアルゴリズムを図 1 に，
推定フェーズのアルゴリズムを図 2 に示す．
学習フェーズでは，まず語集合 Atrain とプローブ語
の候補となる語集合 Xcand を用意する．本論文では例と
Web 検索エンジンのヒット件数のロバストな推定
5
して，Atrain に研究者氏名を，Xcand に「マイニング」
や「自然言語」など研究に関するキーワードのリストを，
学術論文のタイトルから抽出する．そして，プローブ語
候補 X ∈ Xcand をクエリに検索エンジンへ入力し検索
ヒット件数を取得し，語 A ∈ Atrain との共起ヒット件数
n(X, A) も取得する．その例を表 1 に示す．
表 1 において共起ヒット件数には大きな特徴がある．
まず，
「学習」と「本村陽一」氏の共起ヒット件数は 9320
件である．これは他の人物と「学習」のヒット件数に比
べ大きい．同じように「知識」と「武田英明」氏の共起
ヒット件数も大きい．これは，
「本村陽一」氏はベイジア
ンネットワークの研究者であり，
「学習」という語と共起
するケースが多いためである．また「武田英明」氏もナ
レッジマネジメントやセマンティック Web に関する研究
者であり，
「知識」という語と共起しやすかった．
では，推定に適するプローブ語の選択手法について考
察する．本手法では，拡大率の分散，χ2 値，KullbackLeibler 係数，コサイン距離の 4 つの指標値を用いてプ
ローブ語の選択を行った．まず，拡大率の分散が低いとい
うことは，特定の語と強い共起をするわけではなく，ど
の語とも満遍なく共起しやすいということになるので，
プローブ語に妥当である．次に，χ2 値はプローブ語と
ターゲット語の独立性を計測できるため，χ2 値の少ない
ものを選ぶことで，独立性の高いプローブ語を選択でき
る．Kullback-Leibler 係数とコサイン距離は，モデルと
なるヒット件数の分布との類似度に応じてプローブ語を
評価し選択することができる．
この 4 つのプローブ語 X の指標値 sX の計算式を以下
にあげる．
Var 拡大率の分散値．
2
sX = σX
1
2
3
4
5
...
148
149
150
151
152
プローブ語
検索
手法
データ
評価
可能
...
モデリング
実験
タグ
教材
障害
拡大率
分散
3.255
3.417
3.425
3.709
4.159
...
16.44
18.10
18.08
20.96
21.86
13.91
13.92
15.61
19.96
21.334
...
350.8
403.6
408.9
511.1
636.7
された．本手法では，使用するプローブ語数を決め，指
標 sX が小さいものをプローブ語に選択する．これらの
4 つの指標に加え，ランダムでプローブ語を選んだもの
(Rnd) を含め，5 章で比較評価を行う．
本手法では多くのクエリーを検索エンジンに入力する
ことになる．例えば，m 個のプローブ語と l 個のトレー
ニングデータを用いるとすると，学習のために m × l 回
検索を行わなければならない．推定フェーズでは，プロー
ブ語の個数 m 回検索を行う必要がある．プローブ語の数
と適合率の関係はトレードオフであり，プローブ語の数
が多ければ精度もあがるが検索件数が増え検索エンジン
に負荷をかけることになる．逆にプローブ語の数が少な
ければ検索エンジンへの負荷は減るが精度が下がる．本
論文では評価から 10 個から 20 個程度のプローブ語が妥
当であると判断した．
5. 本手法の評価
2
0
Chi χ 値による n(X, A ) の観測値に基づく指標値．確
率 p(A0 ) は p(A0 ) = nA0 /(σA0 ∈Atrain nA0 ) で示される．
sX =
X
A0 ∈Atrain
(n(X, A0 ) − nX∗ · p(A0 ))2
nX∗ · p(A0 )
X
where nX∗ =
n(X, A0 )
A0 ∈Atrain
Cos 語集合 Atrain の語 A0 と共起ヒット件数 n(X, A0 )
のコサイン距離．
s−1
X
表 2 閾値以上の拡大率を持つ分散の少ないプローブ語のリスト
=
P
qP
A0 ∈Atrain
A0 ∈Atrain
(nA0 )
nA0 n(X, A0 )
qP
2
A0 ∈Atrain
n(X, A0 )2
KL p と q の確率分布の差分を指標とする KullbuckLeibler 係数．
X
p(A0 )
s−1
p(A0 ) log
X =
q(A0 )
0
A ∈Atrain
どの指標を用いた場合でも，sX が小さい語ほどプロー
ブ語に適する．表 2 は拡大率の閾値以上のプローブ語を
分散値の昇順に並べたものである．
「情報」や「研究」と
いう語は分散は小さいものの，拡大率が小さいため排除
本章では，前章で提案した手法の評価を行い，検索ヒッ
ト件数の推定の有効性を考察する．
5・1 実験に用いるデータと評価手法
提案する手法の評価のため，ソーシャルネットワーク
におけるデータセット (SN )，および日本語一般語のデー
タセット (GW J) と英語一般語のデータセット (GW E)
の 3 つを用意した．
• SN ソーシャルネットワークの自動抽出に用いたデー
タをデータセットとした．[Matsuo 06] と同様の人工
知能学会学会員を対象にしたソーシャルネットワー
クの作成に用いたデータセットである．このデータ
セットには 540 名の会員氏名とキーワード 188 語が
含まれている．キーワードは論文のタイトルやアブ
ストラクトで頻出する語を選んでいる．会員氏名を
Atrain ，キーワードを Xcand とした．
• GNJ 日本語の一般語に関するデータセットであり，
Yahoo! Japan のディレクトリのカテゴリーから構
築した．トップカテゴリーの 413 語を集め，Atrain
とした．また，カテゴリー内の Web ページに頻出
する語トップ 200 語を選び，プローブ語候補 Xcand
とした．オントロジー学習の面で検索エンジンのカ
テゴリは有効であり，本手法の評価に利用した．
6
人工知能学会論文誌
氏名
神嶌敏弘
中丸茂
鳥居大祐
中西英之
小出誠二
庄司裕子
本村陽一
武田英明
喜連川優
...
拡大率 mX
mX の分散
単独件数
298
160
103
499
403
1510
16300
23000
91100
...
システム
201
34
71
399
184
582
11400
15100
86900
...
1.994
3.792
支援
114
15
51
294
101
658
605
11500
78600
...
4.225
26.978
表 1 プローブ語の共起ヒット件数
情報
ため
学習
ロボット
257
204
187
65
122
118
52
10
78
74
48
14
460
369
204
145
204
154
48
36
1120
822
447
235
13900 10300
9320
664
18800
13100
830
665
90000
84000
856
479
...
...
...
...
1.433
2.302
4.835
8.617
0.684
5.804
32.90
104.7
手法
191
14
43
205
70
287
595
899
9600
...
4.505
29.88
巻 x 号 a（2007 年）
エージェント
58
7
48
315
64
107
303
861
73500
...
9.551
126.2
遺伝
98
10
27
205
57
92
349
702
659
...
5.952
48.44
知識
125
54
37
197
111
447
614
11700
674
...
4.811
30.25
• GNE 英語の一般語に関するデータセットであり，
Yahoo! Directory のカテゴリーから構築した．カ
テゴリーのラベル 500 語を Atrain とし，そのラベル
のうち，Web ページに頻出する上位 200 語を Xcand
とした．
評価の方法は以下の通りである．まず，語 A ∈ Atrain
と，プローブ語 X ∈ Xprobe の共起ヒット件数 n(X, A)
を検索エンジンから取得し，推定ヒット件数 n̂A を求め
る．次に，比較対象に検索エンジンからヒット件数 nA
を求めておく．真のヒット件数は分からないので，nA
は平均的に正しいという仮定を置いている．そして推定
値 n̂A とヒット件数 nA の相関係数を求めることによっ
て評価を行う．相関係数が高ければ，本論文で提案する
手法により共起ヒット件数から検索ヒット件数の推定を
行うことができる，ということになる．プローブ語選択
の指標に分散 (Var)，コサイン距離 (Cos)，χ2 値 (Chi)，
Kullback-Leibler 係数 (KL)，ランダム (Rnd) を用いて
比較した．また，各々の指標を単一係数による統合と回
帰係数による統合で比較した計 10 通りの組み合わせの
評価を，5-fold の交差検定を行った．
図 3 プローブ語と相関係数
5・2 検索エンジンによる評価
表 3 に検索エンジン Google の相関係数を示す．同様に
Yahoo!(表 4) や MSN(表 5) といった検索エンジンによる
評価も行った．どの指標もランダムで選んだプローブ語
(Rnd) に比べ相関が高いが，特に Kullback-Leibler(KL)
と χ2 値の効果が高いことがわかる．単一係数による統
合と回帰係数による統合の比較では，双方とも大きな差
異はない．ランダムで選んだプローブ語に関しては回帰
結合による統合がよい相関を示している．また，検索エ
ンジンごとの比較では，Kullback-Leibler 係数や χ2 値
では大きな違いが見られなかったが，ランダムで選んだ
プローブ語 (Rnd) では Google がよい相関を示した．
データセット SN とデータセット GNJ では，相関係
数が 0.8 から 0.9 だった．データセット GNE では相関
は 0.9 を超え，高いものでは 0.97 であった．したがって，
共起からヒット件数を推定することは有効であると考え
ることができる．
プローブ語と相関係数の関係を図 3 に示す．プローブ
語が多くなるにつれては相関係数は上がっていくが（特
に 12 個まで），それ以上となると相関係数は 0.65 程度
に落ち込む．よって，この場合，プローブ語は 12 個程度
が妥当である．これ以上の語数を超えると，候補とした
語全ての影響を受けてしまい，相関係数に影響を及ぼす
図 4 Google による検索ヒット件数と推定値
と考えられる．
データセット SN に関して，図 4 に Google による検索
で得た値と推定した値の分布を示す．推定値と検索ヒッ
ト件数との間に相関が見られる一方で，2000 件から 9000
件の間の検索ヒット件数が見られず，検索ヒット件数の少
ない集合と多い集合とに分布するということがわかる．こ
の現象は，Google がヒット件数に応じて異なるモジュー
ルが存在することを示している．検索件数が少ない場合
には正確な値を出力し，ヒット件数が大きい場合には，推
定値を出力していると考えられる．よって，本手法の前
提である「ヒット件数が k 件より少ない場合にはヒット
件数は正確である」という仮定の正しさを支持する現象
である．
Web 検索エンジンのヒット件数のロバストな推定
7
SN
GWJ
GWE
Sgl+Rnd
0.645
0.653
0.846
Sgl+Var
0.786
0.827
0.978
表 3 検索エンジン Google を用いた場合の正解例との相関係数
Sgl+Cos
Sgl+Chi Sgl+KL Reg+Rnd Reg+Var Reg+Cos
0.797
0.850
0.748
0.703
0.794
0.725
0.734
0.862
0.822
0.679
0.754
0.798
0.797
0.944
0.827
0.853
0.912
0.842
Reg+Chi
0.849
0.869
0.942
Reg+KL
0.810
0.865
0.937
SN
GWJ
GWE
Sgl+Rnd
0.635
0.620
0.696
Sgl+Var
0.650
0.740
0.969
表 4 検索エンジン Yahoo!を用いた場合の正解例との相関係数
Sgl+Cos
Sgl+Chi Sgl+KL Reg+Rnd Reg+Var Reg+Cos
0.802
0.853
0.770
0.559
0.572
0.834
0.852
0.868
0.788
0.632
0.827
0.804
0.871
0.917
0.483
0.683
0.915
0.915
Reg+Chi
0.876
0.857
0.820
Reg+KL
0.782
0.898
0.956
5・3 Accoona を用いた評価
次に，我々は Accoona∗3 と呼ばれる検索エンジンを用
いて本手法を評価した．Accoona は企業情報専門の検索
エンジンであり，FAST 検索エンジンを使って 2004 年
より運用がなされている．Acoona による検索では正確
なヒット件数を求めることができるので，提案手法の推
定値の評価に有効である．例えば，
「network」という語
を入力すると，76,480,933 件という正確なヒット件数を
返す．
そこで本手法の評価を行うために，一般的な検索エンジ
ンをシミュレートした．既存の検索エンジンのヒット件数
にはガウス雑音が加わっているものと仮定し，Accoona
の出力する結果に対し，ヒット件数の 20%のガウス雑音
を加えた．これによって，ノイズを含むヒット件数と，正
確なヒット件数を両方とも取得することができる．
次に英語一般語データセット (GWE) に対し，KullbackLeibler 係数 (KL) を指標にプローブ語を選択し推定を行っ
た．正確なヒット件数とノイズを含むヒット件数の相関
係数は 0.821 であったが，推定を行った結果，正確なヒッ
ト件数と推定値の相関係数は 0.872 となった．これから
わかるように，本手法では複数の共起ヒット件数をもと
に推定を行うことにより，単にクエリとなる語を検索エ
ンジンに入力する場合に比べ精度が高くなる．
6. 応用と議論
n̂pos
A =
ここでは，コンピュータサイエンスの研究者である鳥
居大祐氏，安藤公一氏，奥村学氏のヒット件数を推定する
例を挙げる．まず，表 6 に示すように各氏とプローブ語の
共起ヒット件数を得る．そして，KL を指標にプローブ語
を選択し，回帰係数による統合により推定値を計算する．
表 7 に同姓同名判定モジュールの有無による推定値の違い
を示す．ここで用いる同姓同名の正誤判定モジュールは，
特定の人物の同姓同名を判別し，検索対象の人物である
かどうかを判定するモジュールである．このモジュールは
対象の人物固有のキーワードを用意し，キーワードを使っ
た文脈情報で収集した Web ページを判別する [Bollegara
06]．この例では，鳥居大祐氏の場合，正誤判定モジュー
ルの有無に関わらず推定値はほぼ同じである．その一方
で，安藤公一氏は正誤判定モジュールにより 12%件数が
減り，奥村学氏にいたっては 1/4 ほどのページが削られ
ていることがわかる．これは，安藤公一氏や奥村学氏と
いう名前は，鳥居大祐氏の名前に比べ同姓同名の人物が
多いことを示している．
表 6 評価モジュール用のプローブ語との共起ヒット件数
氏名
鳥居大祐
6・1 ソーシャルネットワーク抽出への応用
ソーシャルネットワークの自動抽出 [Matsuo 06] では，
氏名の検索ヒット件数を用いて関係性の強さの指標を計
算する．よって，正確な検索ヒット件数を推定する必要
がある．検索エンジンによってクエリを含む Web ページ
を検索することができるが，取得した Web ページが検索
要求に適うものではないかもしれない．例えば，クエリ
に氏名を入力した場合，対象となる人物に同姓同名の人
物がいることもある．そこで，ソーシャルネットワーク
の自動抽出では，同姓同名の正誤を判別するモジュール
（同姓同名判定モジュールと呼ぶ）が，検索対象の人物名
を含む Web ページを正確に取得することに有効である．
これを本論文の推定手法と組み合わせることで，正確な
推定値を求めることができる．
ここで，k ページの文書を保持し，kpos 件が目的に正
しい文書であったとしよう．すると，正しいページの推
定値は次の式のようになる．
∗3 http://www.acoona.com
kpos
n̂A
k
安藤公一
奥村学
プローブ語
支援
構造
振る舞い
理解
支援
構造
振る舞い
理解
支援
構造
振る舞い
理解
件数
正例率
正例数
51
29
36
29
166
145
81
116
902
945
667
695
0.73
0.89
0.75
0.90
0.82
0.76
0.86
0.81
0.91
0.76
0.85
0.79
37.2
24.7
27.0
26.1
136.1
110.2
69.7
94.0
820.8
718.2
567.0
549.1
表 7 人物に関するヒット件数の推定
氏名
鳥居大祐
安藤公一
奥村学
正誤判定なし
正誤判定あり
163.8
305.1
17975.4
158.3
268.9
13967.2
図 5 に Google ヒット件数のみで生成した人工知能学
会に所属する研究者のソーシャルネットワークと，本手
8
人工知能学会論文誌
SN
GWJ
GWE
Sgl+Rnd
0.536
0.416
0.554
Sgl+Var
0.783
0.794
0.961
表 5 検索エンジン MSN を用いた場合の正解例との相関係数
Sgl+Cos
Sgl+Chi
Sgl+KL Reg+Rnd Reg+Var Reg+Cos
0.762
0.850
0.775
0.578
0.715
0.890
0.820
0.816
0.869
0.462
0.671
0.896
0.488
0.929
0.972
0.616
0.947
0.873
巻 x 号 a（2007 年）
Reg+Chi
0.854
0.812
0.935
Reg+KL
0.866
0.813
0.978
れを発展させたものと位置付けることができる
検索ヒット件数はベルヌーイ分布であるため，推定の
確率モデルを語の共起分布によって確率することができ
た．しかし，検索エンジンではスパム対策のヒューリス
ティックな処理など，内部的な処理がなされていること
があり，より洗練されたモデルを作るにはまだ問題があ
る．現状の検索エンジンに適したモデルへ発展させると
共に，推定精度を上げることが今後の課題である．
7. おわりに
図 5 Web より自動抽出したソーシャルネットワークの比較
法の推定値により生成したネットワークを示す．同姓同
名が多い研究者の場合，時にヒット件数が大きくなって
しまうことがあり，他の研究者との関係性の指標となる
Jaccard 係数や Simpson 係数が小さくなってしまう．そ
の結果，全体のリンクが想定よりも少なくなる現象が見
られた．しかし，本論文の推定手法によりネットワーク
抽出を行った場合，より多くのリンクが生成された．例
えば，ヒット件数のみで生成したネットワーク上でリン
クの少ない人物が，推定値により生成したネットワーク
ではリンク数が多くなっている．このように本論文で提
案した手法は，Web 上の全文書を対象とし特定の条件に
適合するページ数を推定するために有効である．
6・2 議
論
本論文は特殊な検索エンジンを用いるわけではなく，
日常的に使用する検索エンジンのインタフェースを用い
て検索ヒット件数をロバストに推定するところに新規性
がある．では，従来研究の手法を用いて Web ページの
検索ヒット件数を推定する方法を考察しよう．たとえば，
Bharat らのアプローチ [Bharat 98] を用いた場合には，
語 A の推定値は次のような手順で推定できる．
• まず，語や節からなる語彙辞書 L を作成する．そし
てこの語彙辞書に含まれる語 X の事前確率 p(X) を
求める．
• 次に，語 X を検索エンジンに入力し，検索された文
書に語 A が含まれているかどうか調べる．
この手法では，文書をランダムに標本抽出し，その文
書の中に語 A が含まれているかどうかを調べる．そして
事前確率 p(X) を用いて語 A のヒット件数を推定する．
しかし，この方法で安定した値を得るためには，多くの
標本が必要となる．実際この手法から “X AND A” とい
うクエリーを入力するという方法にたどり着いた．それ
ゆえ，本手法は Bharat らのアプローチをもとにし，そ
本論文では，検索エンジンのヒット件数をロバストに
推定する新しいアルゴリズムを提案した．提案手法は語
の共起に基づき，ヒット件数を推定する．そして，複数
のデータセットにおいて有効であることを示した．特に
英語一般語のデータセットに対して，正確なヒット件数
に対する相関係数は，Google では 0.978，Yahoo では
0.969，MSN では 0.978 を示した．さらに，Accoona を
用いた評価では，ノイズを含む検索結果でも検索ヒット
件数を推定できることを示した．
本論文の意義は，オントロジー構築やソーシャルネッ
トワーク抽出などセマンティック Web の研究，さらに多
くの自然言語処理のタスクにおいて，検索エンジンの仕
様や固有に持つ問題にとらわれず，検索ヒット件数を利
用することができるという点にある．自然言語の強大な
コーパスとしても，社会的な影響力としても，Web は高
い潜在能力を持っている．Web にある世界中の情報を扱
う研究において，本論文は検索エンジンの有益な利用法
の一つの方向性を示している．
♦ 参考文献 ♦
[Anagnostopoulos 05] Anagnostopoulos, A., Broder, A. Z.,
and Carmel, D.: Sampling search-engine results, in In Proc.
WWW 2005, pp. 245–256 (2005)
[Bagrow 04] Bagrow, J., Rozenfeld, H., Bollt, E., and Avraham, ben D.: How famous is a scientist? - famous to those
who know us, Europhysics Letters, p. 67:511 (2004)
[Bar-Yossef 06] Bar-Yossef, Z. and Gurevich, M.: Random
sampling from a search engine ’s index, in In Proc. WWW
2006 (2006)
[Bharat 98] Bharat, K. and Broder, A.: A technique for measuring the relative size and overlap of public Web search
engines, in In Proc. 7th WWW Conf. (1998)
[Bollegara 06] Bollegara, D., Matsuo, Y., and Ishizuka, M.:
Disambiguating personal names on the web using automatically extracted key phrases, in In Proc. ECAI 2006 (2006)
[Bunge 93] Bunge, J. and Fitzpatrick, M.: Estimating the
number of species: A review, Journal of the American Statistical Association (1993)
[Cafarella 05] Cafarella, M. and Etzioni, O.: A search engine
for natural language applications, in In Proc. WWW2005
(2005)
[Cimiano 04] Cimiano, P., Handschuh, S., and Staab, S.: Towards the self-annotating web, in In Proc. WWW2004, pp.
462–471 (2004)
Web 検索エンジンのヒット件数のロバストな推定
[Curran 02] Curran, J.: Ensemble methods for automatic
thesaurus extraction, in In Proc. EMNLP 2002 (2002)
[Haas 98] Haas, P. and Stokes, L.: Estimating the number
of classes in a finite population, Journal of the American
Statistical Association (1998)
[Hage 06] Hage, W., Kolb, H., and Schreiber, G.: A method
for learning part-whole relations, in In Proc. ISWC2006
(2006)
[Hearst 92] Hearst, M.: Automatic acquisition of hyponyms
from large text corpora, In Proc. COLING ’92, pp. 539–545
(1992)
[Keller 02] Keller, F., Lapata, M., and Ourioupina, O.: Using the web to overcome data sparseness, in In Proc.
EMNLP 2002, pp. 230–237 (2002)
[Kilgarriff 03] Kilgarriff, A.: Introduction to the special issue
on the web as corpus, Computer Linguistics, p. 29(3) (2003)
[Lapata 04] Lapata, M. and Keller, F.: The web as a baseline: Evaluating the performance of unsupervised web-based
models for a range of nlp tasks, in In Proc. HLT-NAACL
2004, pp. 121–128 (2004)
[Manning 02] Manning, C. and Schutze, H.: Foundations of
statistical natural language processing, The MIT Press, London (2002)
[Manning 07] Manning, C., Raghavan, P., and Schutze, H.:
Introduction to Information Retrieval, Cambridge University Press (2007), online version
[Matsuo 04] Matsuo, Y. and Ishizuka, M.: Keyword extraction from a single document using word co–ocurrence statistical information, International Journal on Artificial Intelligence Tools, Vol. 13, No. 1, pp. 157–169 (2004)
[Matsuo 06] Matsuo, Y., Mori, J., Hamasaki, M., Takeda, H.,
Nishimura, T., Hasida, K., and Ishizuka, M.: POLYPHONET: An advanced social network extraction system,
in In Proc. WWW 2006 (2006)
[Mika 05a] Mika, P.: Flink: Semantic web technology for the
extraction and analysis of social networks, Journal of Web
Semantics, Vol. 3, No. 2 (2005)
[Mika 05b] Mika, P.: Ontologies are us: A unified model
of social networks and semantics, in In Proc. ISWC2005
(2005)
[Miura 04] Miura, K., Tsuruoka, Y., and Tsujii, J.: Automatic acquisition of concept relations from web documents
with sense clustering, in In Proc. IJCNLP04 (2004)
[Turney 01] Turney, P.: Mining the web for synonyms: PMIIR versus LSA on TOEFL, in In Proc. ECML-2001, pp.
491–02 (2001)
[Turney 05] Turney, P. D.: Measuring semantic similarity by
latent relational analysis, in In Proc. IJCAI-05 (2005)
[松尾 07] 松尾豊：世界へのインタフェースとしての検索エンジ
ン, 電子情報通信学会論文誌, 解説記事 (2007)
〔担当委員：××○○〕
19YY 年 MM 月 DD 日受理
著
者
紹介
友部
博教
（正会員）
著者 1 の略歴
9
松尾
豊（正会員）
著者 2 の略歴
西村
拓一（正会員）
著者 3 の略歴

Download Report