論文
DBSJ Letters Vol.4, No.2――――――――――――――――――――――――――――――――――――

検索語の曖昧性を解消するキーワ
ードの提示手法
Query
Ambiguity
Indication
Infrequent Term Cooccurrences♥

若木 裕美
高須 淳宏♦

正田 備也
安達 淳♦

Using

♦

Hiromi WAKAKI Tomonari MASADA
Atsuhiro TAKASU Jun ADACHI

既存の検索エンジンではキーワード検索が主流で，数語からなる適切な検索質問を見つけるのが難しい．本稿では，単語の低頻度共起を利用し，検索質問の曖昧性を解消する手法を提案する．この手法は“多種類の単語と共起する単語は，独立したトピックを持ちえない”という仮説に基づき，単語に重みを与え，トピックに分けやすいかどうかの尺度とする．
さらに Web データを用いた実験で有効性を確認する．
Conventional search engines are designed mainly for
keyword search. Therefore, we have to try many
combinations of query terms. This paper presents aquery disambiguation method by using infrequent termcooccurrences. Our method weights terms based on the
hypothesis that terms appearing with a wide variety ofterms cannot establish an independent topic. The
weighting is a measure whether the term can articulate
a specific topic. Besides we verify the effectiveness of our
method by using Web data.

1. はじめに従来型の検索エンジンでは，ランキングされた結果を見ても所望の情報を得にくい．それは検索エンジンが悪かったのであろうか．そもそもユーザによって入力される検索語は信頼性の高いものと言えるだろうか．現状では，質問者が欲しい情報を得るために，体系立って作られてはいないWeb 上の情報の特性に合わせて「的確に欲しい情報を持ってこられる語」を入力する必要がある．また多くの場合，質問語は1，2語であり，情報量が少ないことも質問処理を困難にしている．
その結果、ユーザが必要とはしない内容が検索結果に含まれて提示されていることとなる．異なる内容が含まれていたとしても，検索質問から特定できない場合には，それを排除す
る術を検索エンジンは持ち合わせていない．多義語に限らず，検索における曖昧性は常に存在すると思われる．
本稿では，検索語をヒントにユーザの必要とする語を提示する手法を提案する．これは検索結果を得る手続きとは別個の手法であり，検索結果に対して情報の整理、情報の提示を♥学生会員 東京大学大学院情報理工学系研究科博士課程
hiromi@nii.ac.jp♦
正会員 国立情報学研究所 {masada, takasu,
adachi}@nii.ac.jp

1

行うことを最終的な目的とするものである．将来的には，集めた語を幾つかのトピックに分けて提示することで，ユーザは自分の検索要求の中にある曖昧性に気が付き，そのトピッ
クの中からより自分の要求に合致するものを選択することが可能となる手法であると考える．

2. 分節性（articulateness）
2.1

分節性の仮説

検索質問の曖昧性に対処するため，検索結果に含まれるト
ピックを分けて提示することを想定する．だが，既存の特徴
語抽出でスコアの高い語は，検索結果の文書の多くに現れ，
個別的なトピックの手がかりになりにくい．そこで，検索結果に含まれる多様なトピックを識別できる語を抽出する指標として、新たに「分節性(articulateness)」を提案する．
分節性の高い語とは，特定のトピックに関する文書に現れやすいが、他のトピックに関する文書には現れにくい語のことだと考える．そして，共起概念を導入してこの考え方を具体化し，次の仮説を立てる：特定の少数の語とよく共起するが，他の多数の語とはあまり共起しない語は，分節性が高い．なお，本稿では，同じ文書に現れることを共起と定義する．次に，分節性を定量的に表す二つの定式化 AR1， AR2 を提案する．

2.2 定式化 1：異なり語数に基づく（AR1）
分節性の理想に合うモデルとして，「その文書集合の中において，多くの種類の語と一緒に出てくる可能性の高い語は，
その文書集合の中で独立したトピックをもてないものである」と仮定する．
まず，単語tiの分節性を，ti を含む文書に現れる単語の種
類の平均数AvgType(ti)を使って定式化することを考える．Sを検索結果として得た文書の集合，NS(ti)をSの中で単語ti を含む文書の数，NS(ti∧tj)をSの中で単語ti とtj を含む文書の数とすると，AvgType(ti) はΣtj≠ti NS(ti∧tj) / NS(ti) と表すことができる．このAvgType(ti) が小さいほど単語t iの分節性が高いとみなす．しかし，NS(ti)が小さい単語は，分節性に関係なくAvgType(ti)も小さくなりやすい．そこで，単語tiがSの中のある程度多くの文書に現れるという条件を加えて，
AR1(ti ) =N S (ti ) 2
1
N (t ) 2⋅= S i
NU (ti ) AvgType (ti ) NU (ti )∑t j ≠ tiN S (ti ∧ t j )N S (ti )という特徴量AR1で単語ti の分節性を表すことにする．ここで，NS(ti)2 / NU(ti)という項は，NS(ti) / NU(ti)とNS(ti)を掛け合わせてつくった項である．NS(ti) / NU(ti)は，検索対象となる文書全部の集合Uの中で単語ti が現れる文書の数NU(ti)に対する，Sの中で単語ti が現れる文書数NS(ti)の比であり，単語ti がSにどれだけ関係しているかを相対的に表している．
NS(ti)は集合Sの中で単語tiが現れる文書数そのもので，単語ti のSへの関係の度合いを直接表している．

2.3 定式化 2:確率論的観点に基づく（AR2）
もう１つの定式化として、単語tiの分節性をti以外の単語の，集合S での出現頻度と，単語ti を含む文書集合の中での出現頻度とのずれを計算することで，単語ti の分節性を評価する式を考える．分節性の考え方に合うものとして『その単語が出現することで，他の単語の出現確率が低くなる方向にずれるものほど良い』というモデルを定式化することを考える．
ここで「単語tiが文書に現れる」確率をPS(ti)，ひとつの文書中で単語ti とtj が共起する確率を，PS(ti ∧ tj) と書くことにする．本稿では，

日本データベース学会 Letters Vol.4, No.2

論文
DBSJ Letters Vol.4, No.2――――――――――――――――――――――――――――――――――――PS (ti ) = N S (ti ) N S

PS (ti ∧ t j ) = N S (ti ∧ t j ) N Sと定義する．以下，出現確率，共起確率は，集合S 上で考えるので，添え字S は省略し，PS(ti)，PS(ti, tj)などと書く．
K j ( x) =y∈t j , ¬t jとかくとき，Kj(X) は，KL情報量(Kullback Leibler情報量)と呼ばれる値である．分節性を考える上で関心のある値は，
単語ti が現れる場合のみのずれであり，Kj (ti) が大きくなることで表される．Kj (ti) が大きくなる場合には，次の２つの場合があり得る．
(a)P(tj|ti) log P(tj|ti)P(tj)< 0の場合(低くなる方向にずれる)(b)P(tj|ti) log P(tj|ti)P(tj)> 0の場合(増える方向にずれる)
本稿で扱う単語の分節性では，『他の単語の出現確率が低くなる方向にずれる（これをSKLとする）』ものを求めており，
前者の項(a) だけが必要となる．そこで分節性は，(a)の条
件に合うような単語tj が多いほど『単語ti の分節性は高い』と定義でき，KL 情報量の式を変形して定式化することができる．これをAR2 と表すことにする．
P (t j | t i )P (t j )+ P(¬t j | t i ) log

P (¬t j | t i )P (¬t j )N (t ) 2
AR 2(t i ) = S i × ∑ SKL(t j ; t i )N U (t i ) t j ≠ tiと書ける1．

3. 実験
3.1

実験における比較対照の式の整理

単語ti と他の各単語tj との共起情報に基づく特徴量をcw(ti, tj) とする．そして，
CW (t i ) = ∑ cw(t i , t j )t j ≠ tiと定義されるCW(ti) を，ti と他の単語の共起情報すべてを集約した値とする．さらに，このCW(ti) とNS(ti)2 / NU(ti) をかけることで，文書集合S に強く関係する単語ほど，共起に基づく特徴量がより強調されるように，単語のスコアを定める．
W (t i ) = N S ×

N S (t i ) + 0.5
N S − N S (t i ) + 0.5
NU (t i ) − N S (t i ) + 0.5
NU − NU (t i ) − N S + N S (t i ) + 0.5

ただし，α, k4は，パラメータとする．
RSVは，Query Expansionのための特徴語選択に使われる．

P ( y | x)

∑ P( y | x) log P( y)SKL (t j ; t i ) = − P(t j | t i ) log

NU
w2 t i = α × log(k ' 4 ×+ 1) + (1 − α ) × log
N U (t i )

3.2

実験の手法

NTCIR3 web task [1] は，およそ1000 万件のWeb ページ
を対象とし，検索課題は47 個用意されている．各課題において与えられる検索語は2〜3 個である（図1 step.1）．
各検索課題から検索2を行い，上位1000 件を取り出す（図1step.2）．この上位1000 件中において，5 件以上の文書で現れた語だけを残す．その結果，どの検索課題についても1万語前後を得た．また，本実験においては，stop word は除去していない．ここで残った全ての語のペアに関して，共起した文書の数を調べる．そして，共起した文書の数を使って，各式による値を計算する（図1 step.3）．各手法による結果の上位5 語(a, b, c, d,e) を，元々の検索課題(A+B+C) に1つずつ加えて，5 通りの検索(A+B+C+a, A+B+C+b,…,
A+B+C+e) を行い（図1 step.4），最も高かった平均適合率3を当該平均適合率とする（図1 step.5）．最後に，全ての課題についての平均を取り，各式による結果について比較を行う．

3.3

実験の意義

本手法の目的は，元の検索語が曖昧なために検索結果に含まれてしまう多様なトピックを，良く分離できる語を見つけることである．ここで，異なるトピックに属し，かつ，互いにそのトピックを他から際立たせるような語を，同時に元の検索語に付け加えて検索すると，検索結果として複数のトピックのものが混在するだけでなく，検索自体がうまくいかな
いことも想像される．一方，評価用の正解集合は，１つのトピックだけを含むように作られており，求められるのは1つのトピックに関わるものだけである．そこで，本実験においては，Query Expansion のように抽出された語すべてを一緒に付け足すのではなく，上位にランク付けされた語をそれぞれ別個に元の検索語に追加した．そして，複数得られた検索

N S (t i )× CW (t i )N U (t i )特徴語抽出の手法には様々あるが，今回の実験では，AR1, AR2,
UnitWeight, CF, 相互情報量, KL情報量，χ2 検定，RSVの8通りのスコア付け手法を比較した(詳しくは，表4を参照)[7] ．
ただし，UnitWeightは，CW(ti) = 1とし，NS(ti)2 / NU(ti) の部分だけを単語のスコアとする．これによって，すべてのス
コア付け手法に共通する項の影響を見ることができる．また
CFでは，AR1と逆の考え方，すなわち『他の語と共起する種類の多い方が良い語である』という指標を定式化し比較対象とした．
また，単語の共起情報を用いないRSV (Robertsonʼs
Selection Value) [5]は以下の式で定義される．
RSVti = w2 ti × (N S (t i ) N U (t i )
−
)
NS
NU

図1
Fig.1

実験の手法

Experiments procedures.

2 OKAPI の式[2] を使用した．
1 ここで新しく定義したSKL に近い式を，Lau らが[3] の論文において，異なる用途で使っている．

2

3 平均適合率の計算は，TREC のtrec eval を用いた．また，relevancelevel はrigid である．

日本データベース学会 Letters Vol.4, No.2

論文
DBSJ Letters Vol.4, No.2――――――――――――――――――――――――――――――――――――
表 1 得られた平均適合率と平均適合率の上昇率．
Table 1 Overall precisions and their upward rates of
the tested term extraction methods.
計算式
平均適合率
上昇率(%)
UnitWeight
0.17659.9
AR10.184715.0
AR20.189918.2
CF0.180112.1
相互情報量(MI)0.182913.9
KL 情報量(KL)0.17337.9
χ2 検定
0.17519.0
RSV
0.1867
16.3
結果からそれぞれ評価して平均適合率を求め，最も良かった
値を当該検索課題の平均適合率とした．なぜなら，最も良い平均適合率を与える語は，評価用の正解集合が含むトピックに一番近いトピックを表わしているはずだからである. もし平均適合率が上昇すれば，検索結果に含まれる多様なトピックのうち，少なくとも正解集合と同じトピックについては，対応するキーワードを取り出すことができていることを示すといえる．つまり，分離性能については検証できないが，分離性を持つような語であっても検索の性能向上に寄与するかどうかを検証できる実験方法である．

3.4

結果と考察

ベースラインは，元々与えられた3 語で検索したときの平均適合率であった0.1606 である．しかしRSV 以外は，共通項であるUnitWeight の後ろに各式による重みの和を掛けているため，比較対象としてUnitWeight の0.1765 を超えなければ，各式で効果があったとは言えない．平均適合率が大きく上昇しているのは，AR1，AR2，RSVの三つであった(表1)．
RSV はもともと，検索要求に適した語群を見つけるために提案されており，それと同程度の検索性能上昇に寄与する語がAR1，AR2を用いて得ることができたといえる．
さらに，この三つの手法（AR1，AR2，RSV）は平均適合率の値では差が無いが，順位付けされた語の一覧を見ると，単語の質が異なっている(表2，表3)．RSV では比較的一般的な意味でも用いられる語が挙がっているが，AR1 やAR2 では検索質問に関連のある特定の分野でのみ使われるような専門的な言葉が多く含まれる．これは，トピックに分けるための指標となり得ることを示唆している．例えば，「哺乳類，絶滅，危機」という3 語から(表2) は，“レッドデータブック
4” や“ルリカケス5”，“シナノミズラモグラ6” という固有名詞が，「世界樹+北欧神話+名前」という3 語から(表3) は，“イグドラシル” という正に北欧神話に出てくる世界樹を指す呼び名が，上位5 件の中に入っている．

4. 関連研究キーワード抽出（ 重要語抽出）の手法は，既存の研究でも数多く提案されている．その中でも，語の分布を測り代表性(representativeness) という指標にあう語を重要とみる手法[6]や，語の共起にχ2 検定を利用して重要な語を選ぶ

表 2 検索質問: 絶滅＋哺乳類＋危機 (baselin は 0.1291)
Table 2 Query: “Mammalia”, “extermination”, and“crisis”. (The baseline is 0.1291.)
手法
上位五語
平均適合率

RSV

AR1

AR2

種
生息
生物
野生
動物
レッドデータブック
瀕危惧
危急
シナノミズラモグラ
レッドデータブック
危急
危惧
両生類
ルリカケス

0.12120.11050.0762
0.09230.07240.06250.07390.16800.1027
0.2361
0.06250.10270.16800.07470.1712

表 3 検索質問: 世界樹+北欧神話+名前(baseline は 0.0675)
Table 3 Query: “the World Tree”, “Norse mythology”,
and “name”. (The baseline is 0.0675.)
手法
上位五語
平均適合率

RSV

AR1

AR2

神
たち
それ
歴史
物語
Pandaemonium
イグドラシル
ソグネフィヨルドエッダ
シルマリル
イグドラシル
古事記
ギリシア
ノルウェー
フィヨルド

0.02530.02800.03770.02660.01980.0586
0.37670.05230.05250.05330.37670.02270.01600.02030.0287

手法[8] が，語の分布のずれを見るという観点では近い．しかし，全文書における単語の重要度（あるいは各文書中での単語の重要度）で一次元的に並べること考えており，その点では今回の(トピックに分ける)目的と異なる．
トピックに分けるというとクラスタリングを想起するかもしれない．例えば，検索要求に合致するクラスタを選ぶことが検索閲覧の効率化につながるとして作られたシステ
ム:Scatter/Gather [4] がある．しかし，これもまた文書同士の関連性を見るもので，検索要求として入力するのに適した語を探すことは難しい．

5. おわりに4 環境省が，日本の絶滅のおそれのある野生生物の種についてそれらの生息状況等を取りまとめたもの
5
環境省のレッドデータブックでは絶滅危惧II 類（VU）．

6 レッドデータブック・哺乳類では，準絶滅危惧（NT）．

3

本稿では，語の低頻度共起を用いて検索質問の曖昧性を除けるような語を抽出するための手法である分節性（AR1 とAR2)について提案した．特に，AR2 については，情報量的な裏付けを持った定式化であり，また，他手法に比べ格段に良日本データベース学会 Letters Vol.4, No.2

論文
DBSJ Letters Vol.4, No.2――――――――――――――――――――――――――――――――――――
い平均適合率が得られている．今後は，この２つの手法による語の選択が，他の手法に対して単語の質が異なるということを実証できるような実験を行う予定である．
また本手法は，検索質問に含まれる曖昧性（多義性）を，それぞれのトピックに分けてユーザに提示できるシステム
を最終的な目標としている．トピックに分ける上で有効な手法であることは実験しているが，紙面のため割愛した．今後は，この点に関しても更に研究を進めていく予定である．

[謝辞］
この研究は，文部科学省科学研究費補助金特定領域研究
13224087 (2001-2005) の補助を受けています．

[文献］[1] Oyama K. Ishida E. Kando N. Eguchi, K. and K.
Kuriyama. “Overview of the web retrieval task at thethird ntcir workshop”, 2003.
[2] F. Hui, T. Tao, and Z. ChengXiang. “A formal study of
information retrieval heuristics”, In Proc. of SIGIR
2004.
[3] Lau, R. Y.K., P.D.Bruza, and D. Song. “Belief revision
for adaptive information retrieval”, In Proc. of SIGIR’04,
pp. 130–137, 2004.
[4] H. Marti and P. Jan. “Reexamining the cluster
hypothesis: Scatter/gather on retrieval results”, In Proc.
of SIGIR’96, pp. 76–84, 1996.
[5] Toyoda M., Kitsuregawa M., Mano H., Itoh H., andOgawa Y.. “University of tokyo/ricoh at ntcir-3 web
retrieval task”, In Proc. of the 3rd NTCIR Workshop
Meeting, pp. 31–38, 2002.
[6] Hisamitsu T., Niwa Y., Nishioka S., Sakurai H.,
Imaichi O., Iwayama M., and Takano A.. “Extracting
terms by a combination of term frequency and a

Table 4

AR2

χ2 検定

正田 備也

Tomonari MASADA

2004 年東京大学大学院情報理工学系研究科電子情報学専攻
博士課程修了．情報理工学博士．同年，国立情報学研究所プ
ロジェクト研究員．情報検索，データマイニングの研究に従事．情報処理学会，日本データベース学会，各会員．

高須 淳宏

Atsuhiro TAKASU

1989 年東京大学大学院工学系研究科博士課程修了．工学博
士．2003 年より同研究所教授．データ工学，電子図書館，
機械学習の研究に従事．電子情報通信学会，情報処理学会，
人工知能学会，日本データベース学会，ACM，IEEE 各会員．

安達 淳

Jun ADACHI

1981 年東京大学大学院工学系研究科博士課程修了．工学博
士．国立情報学研究所教授．東京大学大学院情報理工学系研究科教授を併任．データベースシステム，データマイニング，
情報検索，電子図書館システム等の開発研究に従事．電子情報通信学会，情報処理学会、IEEE，ACM 各会員．

N S (t i ∧ t j ) −1)
N S (t i )tj

SKL(t j ; t i ) = − P(t j | t i ) log

P(t j | t i )P(t j )+ P(¬t j | t i ) log

P ( ¬t j | t i )P ( ¬t j )1

MI (ti , t j ) = P (ti ){P (t j | ti ) log

KL(t j ; t i ) = P (t j | t i ) log

χ 2 (t j ; t i ) =P (t j | t i )P (t j | ¬ t i )P (t j )P(t j )++ P (¬t j | t i ) log

P (¬t j | ti )P (¬t j )P (¬ t j )P (¬t j | t i )P (¬t j )P ( ¬t j )+}P ( ¬t j | ¬t i ){P(¬t j | t i ) − P(¬t j )}2{P(t j | ¬t i ) − P(t j )}2
P(t j )N S (t i )+ P (¬t j | ¬ti ) log

P (t j )P (t j | t i )N S (t i ∧ t j )+ P (¬t j | ti ) log

P (t j ){P(t j | t i ) − P(t j )}2

N S (t i ) 2
× CW (ti )NU (t i )AR1(t i ) =N S (t i ) 2
1×N U (t i ) AvgType (t i )AR 2(t i ) =N S (t i ) 2
× ∑ SKL (t j ; t i )N U (t i ) t j ≠ t i

W (ti ) =CW (ti ) = AvgType (ti ) = ∑+4

Hiromi WAKAKI東京大学大学院情報理工学系研究科博士課程在学中．2004
東京大学大学院新領域創成科学研究科修士課程修了．日本データベース学会学生会員．

CW (t i ) = AvgType(t i ) −1 = (∑+ P (¬ti ){P (t j | ¬ti ) log

KL 情報量若木 裕美

W (t i ) =t j ≠ ti

相互情報量[7] Y. Yiming and O. P. Jan. “A comparative study on
feature selection in text categorization”, In Proc. of
ICML- 97, pp. 412–420, 1997.
[8] 松尾豊, 石塚満. “語の共起の統計情報に基づく文書からのキーワード抽出アルゴリズム”人工知能学会論文誌,
Vol. 17, pp. 213‒227, 2002.

CW(ti)

UnitWeightCFjournal of theoretical and applied aissues in specialized
communication, Vol. 6, No. 2, pp. 211–232, 2000.

表 4 実験に用いた式の一覧
List of formulations for experiments.

手法
AR1

measure of term representativeness”, International

N S (ti ) 2
×1
NU (ti )CF (t i ) =N S (t i ) 2
× AvgType(t i )N U (t i )W (t i ) =N S (t i ) 2
× ∑ MI (t i ; t j )N U (t i ) t j ≠ t i

W (t i ) =N S (t i ) 2
× ∑ KL(t i ; t j )N U (t i ) t j ≠ t j

W (ti ) =N S (ti ) 2
× ∑ χ 2 (t i ; t j )N U (t i ) t j ≠ t j}{P(¬t j | ¬t i ) − P(¬t j )}2
P ( ¬t j )日本データベース学会 Letters Vol.4, No.2