投稿日: その他 論文紹介

A New Semantic Similarity Measuring Method Based on Web Search Engines

Lu, Gang
Huang, Peng
He, Lijun
Cu, Changyong
Li, Xiaobo
In W. Trans. on Comp. vol. 9
http://dl.acm.org/citation.cfm?id=1852382

概要

検索エンジンを用いて得られる情報を基に,単語間の意味的類似度を測ることを目的としている.

手法

検索エンジンのヒットカウントを用いて測る主な手法として以下の4つをあげている.以下の式中で,hits(q)qをクエリとしたときの検索ヒット数,hits(q_{1}\land q_{2})q_{1}q_{2}を共に含むページの検索ヒット数を表す.また,Nは全Webページ数で,論文中では10^{10}としている.

  1. WebJaccard(q_{1},q_{2})=\log_{2} \left( \frac{hits(q_{1}\land q_{2})}{hits(q_{1})\times hits(q_{2})-hits(q_{1}\land q_{2})} \right)

  2. WebDice(q_{1},q_{2})=\log_{2} \left( \frac{2 \times hits(q_{1}\land q_{2})}{hits(q_{1})\times hits(q_{2})} \right)

  3. WebPMI(q_{1},q_{2})=\log_{2} \left( \frac{hits(q_{1}\land q_{2})/N}{\left( hits(q_{1})/N \right) \times  \left( hits(q_{2})/N \right)} \right)

  4. NDG(q_{1},q_{2})=\frac{max \left( \log \left( hits(q_{1}) \right), \log \left( hits(q_{2})\right) \right)}{\log{N- min \left( \log \left( hits(q_{1}) \right), \log \left( hits(q_{2}) \right) \right)}}

1,2,3では,hits(q_{1} \land q_{2})の値が閾値以下なら0とする.論文中では閾値を5としている.

これらに対して,本論文ではCo-occurrence Double-check Mode(CODC)と呼ばれる以下の式で表される手法を提案している.
 CODC(X,Y)=e^{\lambda}: \lambda = \log{ \left( \frac{|D(Y@X)|}{|D(X)|} \times \frac{|D(X@Y)|}{|D(Y)|} \right)^{\alpha}}
式中でXYはそれぞれ単語,D(X)Xの検索結果のスニペット集合,D(Y@X)D(X)の中でYを含むスニペット集合.論文中では検索結果の上位1000件を取得して使用している.また,\alphaの値は0.15としている.
この手法において問題となるのは,「apple」のような語で検索したとき,検索結果に様々な意味のappleの検索結果が混在することである.そこで,各検索結果をDMOZ Open Directory Projectで定義された最上位の13個のクラスに分類し,各クラスの文書集合に対してCODCを計算し,その最大値をXYの類似度とする.分類するにあたって,DMOZの各クラスに対応する文書集合があるので,それを基にSVMを作る.この手法をRCODCと呼ぶ.

実験

実験に用いるデータはR&G datasetとM&C datasetと呼ばれるもので,いずれも単語のペアとその類似度から成るデータである.
評価の際は,各手法の出力結果と正解データとの相関係数を求める.
評価の結果,手法1から4の中で最も良かったWebPMIでも,R&G datasetで0.32,M&C datasetで0.49という値であった.CODCはR&G datasetで0.77,M&C datasetで0.79と大幅に改善された.また,RCODCはR&G datasetで0.82,M&C datasetで0.81とさらに改善できていた.


-その他, 論文紹介
-

関連記事

Mobile App Retrieval for Social Media Users via Inference of Implicit Intent in Social Media Text

Park, Dae Hoon and Fang, Yi and Liu, Mengwen and Zhai, ChengXiang In Proc. of CIKM 2016 概要 ツイートに含まれる …

Characterizing the influence of domain expertise on web search behavior

White, Ryen W. Dumais, Susan T. Teevan, Jaime In Proc. of WSDM 2009 http://dl.acm.org/citation.cfm?i …

Identifying topical authorities in microblogs

Pal, Aditya Counts, Scott In Proc. of WSDM2011 http://dl.acm.org/citation.cfm?id=1935843 概要 あるキーワードに …

VODUM: A Topic Model Unifying Viewpoint, Topic and Opinion Discovery

Thibaut, Thonet and Guillaume, Cabanac and Mohand, Boughanem and Karen, Pinel-Sauvagnat In Proc. of …

Semantic Similarity Between Search Engine Queries Using Temporal Correlation

S. Chien, and N. Immorlica In Proc. of WWW 2005 http://dl.acm.org/citation.cfm?id=1060752 目的 クエリログを用 …