Structured annotations of web queries(SIGMOD 2010) 読んだ

まとめ

検索クエリを構造化して扱うための手法を提示．

なんでそう扱いたいか

前の論文とも関連する，というかそちらの問題意識に近いけれど，商品検索のクエリは構造化されている．
通常の情報検索の文脈で"50 inch LG lcd tv"というクエリは一見何も問題無さそうだが，実はLGは50inchのlcd tvを生産していないのでこれでは商品がヒットしない．しかしクエリを構造化すればLGのlcd tvを検索できるので他のinchをユーザに提示できる．
この論文の目的は2つ．

クエリを構造化されたデータとして扱えるようにする．例えば"50 inch LG lcd tv"というクエリを { テーブル(クエリが意図している領域) => TV，サイズ => 50inch，ブランド => LG，テレビの種類 => lcd tvs} と解釈できるようにしたい．
1つのクエリが複数のテーブルで解釈可能になる場合がある．例えばwhite tigerというクエリはアシックスのスニーカーの白いものを指しているのか，white tigerというタイトルの本を探しているのか，white tigerという動物を探しているのか，という事である．こういった場合，どのアノテーションが最も確からしいのかも計算したい．

問題定義

テーブルと呼ばれるデータ構造を考える．これはジャンル（商品）ごとに定義され，属性(attribute)とその値で構成される．
テレビとモニター，2つのテーブルの例を次に示す．

Type	Brand	Diagona
	TVs
TV	Samsung	46inch
TV	Sony	60inch
TV	LG	26inch

Type	Brand	Diagona
	Monitors
Monitor	Samsung	24inch
Monitor	Dell	12inch
Monitor	HP	32inch

こんな感じで商品ごとに属性(Brand, Diagonal...)とその値(Sony, 46inch...)で構成される．
あとはクエリについて

クエリの単語それぞれに対応する属性を推定する
その後，最も確からしいテーブルをクエリに推定する

という作業をやっていく．

クエリの単語それぞれに対応する属性を推定する(Annotation)

ここの作業は比較的単純．事前にテーブルごとに属性とその値をかき集めてストアしておく．あとはクエリの中からマッチするかどうかで判定("数字 [単位]"みたいな部分の処理は後述)．その後クエリをS = {Table, Annotated Token, Free Token}というタプルで管理する．具体的には"50 inch LG lcd"というクエリは

S_1:
 Table: TVs
 
 Annotated_Token: 
  50inch: TVs.Diagonal
  LG: TVs.Brand
  lcd: TVs.Screen
  
 Free_Token:

 
S_2:
 Table: Monitors
 
 Annotated_Token: 
  50inch: Monitors.Diagonal
  LG: Monitors.Brand
  lcd: Monitors.Screen
  
 Free_Token: 

 
S_3:
 Table: Refrigerators
 
 Annotated_Token: 
  50inch: Refrigerators.Width
  LG: Refrigerators.Brand
  
 Free_Token:
    - lcd

こんな感じでテレビとモニタと冷蔵庫という3つのテーブルについてそれぞれアノテーションされる．冷蔵庫にはlcdなんて属性は存在しないのでFree Token扱い．

最も確からしいテーブルをクエリに推定する

アノテーションができたので，次にどのテーブルがクエリにふさわしいかを推定する．ここで生成モデルを考える．まずユーザは $P(T.A_i)$ の確率でテーブルTとそこにある属性の集合 $T.A_i$ を選ぶ．クエリにフリートークンが入ってる事を考慮してこれを $T.\tilde{A}_i$ と考える．次にユーザは特定のトークンを確率 $P((AT_i,FT_i)|T.\tilde{A}_i)$ で選ぶ．つまりはあるクエリがテーブルiに属するスコアは $P(S_i)=P((AT_i,FT_i)|T.\tilde{A}_i)P(T.\tilde{A}_i)$ となる．
例えば"LD 30 inch screen"はテーブルTVsについてとアノテーションされる．このクエリにおいて選択された属性は{TVs.Brand, TVs.Diagonal, TVs.free}なので
$P(S_i) = P((LG,\, 30inch),\,(screen)\, |\, (Brand,\, Diagonal,\, free))P(TVs.Brand,\, TVs.Diagonal,\, TVs.free)$
となる．ここで

$AT_i, FT_i$ が互いに独立であり
$FT_i$ はTに依存し
[AT_i]は $T.A_i$ に依存する

という仮定を置くと $P(S_i)=P((AT_i)|T.A_i)P(FT_i|T)P(T.\tilde{A}_i)$ となる．あとは各項計算する．
しかしこれだけだと「え，これ普通の検索クエリのつもりで入れただけでそんな構造化したつもりとかないんだけど」みたいな誤判定をする可能性がある．例えば"green apple"なるクエリを「青りんご」とそのままに解釈するのではなく「緑色という属性を持つアップルブランドの商品」と誤解するみたいな感じ．これを防ぐために普通の検索クエリから構成される言語モデル(Open Language Model)を考えて， $P(S_{OLM}) = P(FT_q|OLM)P(OLM)$ を計算する．それであとはしきい値 $\theta$ を考えて $\frac{P(S_i)}{P(OLM)} > \theta$ なら構造化して扱うようにする．

具体的に計算する

じゃあ具体的に何をどう計算するのかという話．求めなきゃならんのは $P(S_i)$ において $P((AT_i)|T.A_i),\, P(FT_i|T),\, P(T.\tilde{A}_i)$ の3項， $P(S_{OLM})$ においては $P(FT_q|OLM),\, P(OLM)$ の2項．
まず $P(AT_i|T.A_i) = \frac{|T(AT_i.V)|}{|T|}$ ． $T(AT_i.V)$ は何かというとテーブルにおいて属性がその値を取る個数．"50 inch LG lcd"なるクエリだと「ブランドがLGで50 inch」なる属性を持つ要素の個数．それをテーブルのサイズで割る．実際は属性の値ごとに（全属性が独立であるという仮定に基づき）数え上げかけ合わせていく（数値属性はカテゴリ化した上で）．あと細かい話だと全属性が独立というわけでもなく，例えばテレビブランドと商品ラインナップは独立じゃないので考慮してやる（ソニーというブランドとブラビアというラインナップは独立じゃない）．
$P(FT_q|OLM)$ については普通の検索クエリのユニグラムを使って $\prod_{w \in FT_q} P(w|OLM)$ としてやる． $P(FT_i|T)$ についてはテーブル固有のユニグラム $P(w|UM_T)$ と普通の検索クエリのユニグラム $P(w|OLM)$ を使って $P(FT_i|T) = \prod_{w \in FT_i} \lambda P(w|UM_T) + \mu P(w|OLM)$ としてやる．
残りの $P(T.\tilde{A}_i),\, P(OLM)$ はEMで求める．