https://repose.hatenadiary.jp/entry/20110915/1316020119

Consideration set generation in commerce search

概要

ECサイトの検索結果(consideration set)を改善する．

問題意識

ECサイトの検索エンジン及び検索結果は通常の文書検索におけるそれとは次の点で異なる．

ECサイトではユーザは検索結果を上位下位構わず開きまくる
- 文書検索だと上位がクリックされやすい
検索クエリ及び検索対象のデータが構造化されている
- 商品側では属性(attribute)ごとにインデックスが貼られる．カメラを例に取るとブランド，モデル，色など
- クエリ側も当然構造化されている
  - 例えば"10mp Nikon Digital Camera"なる検索クエリは特定のメーカ(Nikon)のある望ましい属性(1000万解像度)を持つカメラを求めているという事がわかる

ついでに言えば，ユーザの検索クエリと本人の需要が完全に結びついている事も少ない．ユーザは異なるキーワード/属性を入力しながら何を買うかを決めていくのが常である．これは2つの理由か生じる．

ユーザはしばしばその商品領域の知識を十分に備えていない(ex. 例えばあるメーカの商品で特定スペックのものがあるかどうか，など)
ユーザは全ての属性を入力して検索するわけではない

ここで重要になるのは2である．つまりは商品の属性は1) ユーザが検索クエリに入力している特定属性(specified attribute)と，2) ユーザが検索クエリに入力していない不特定属性(unspecified attribute)からなるという事になる．例えば"Nikon Coolpix 10mp digital camera"なる検索クエリではメーカ，商品シリーズ名，解像度は特定属性であり，色，ズーム機能，型番は不特定属性であると言える．
これらを踏まえて，この研究では特定属性の類似度は高く，不特定属性についてはばらつきを大きくすることを考えた検索結果(consideration set)を考える．

問題定義

重み付き無向完全グラフ $G=(V,E)$ を考える．ノードは商品，エッジの重み $d(x, y)$ は不特定属性による2商品 $x,y$ 間の距離．ついでに各ノードについてコスト $c$ を考える．これは(クエリと?)ノードの特定属性による距離．目的はノード集合 $S$ についてコスト $c(S) = \sum_{v \in S}c(v)$ を最小化しつつばらつき(dispersion) $Disp(S)$ を最大化する．ばらつきは $\sum_{x, y \in S} d(x, y)$ なるMax-sum dispersionを考える．
これらを踏まえるとこれは次のようなLP緩和で書ける．
Maximize $\sum_{u, v \in V} d(u, v)x_{uv} - \lambda\sum_{v \in V} c(v)y_v$
$x_{uv} \leq \min (y_u, y_v)\,\forall u,v \in V$
$0 \leq x_{uv},y_u,y_v \leq 1\, \forall u,v \in V$
$y_u,y_v$ はvがSに入るなら1になる変数で $x_{uv}$ は $y_u=y_v=1$ なら1になる変数．
また，単調増加(monotone)な属性(価格など)について，価格のばらつきあふれる検索結果を出されるよりもなるべく安い商品のみがユーザによろしいと思われる．現状の不特性属性の距離 $d(x, y)$ では単調性を解釈できないので， $d'(x, y) = d(x, y) + w(x) + w(y)$ としてxとyの値における重要性の項を付け加えてやる．
あとはGreedyにモリモリ解く．アルゴリズムは論文参照．なんでこれで解けるのか理解できなかったので触れない．

実験

bingのデータを使ってconsideration setの質と不特定属性の多様性について評価実験．

感想

なんかアイデアとかイントロ面白くて読み進めた挙句肝心の擬似コードが何をやってるのかはわかるけどどうしてこれで解けるのかが理解できないと不完全燃焼感つらい．
次はrefされてたクエリを構造化されたデータとして扱えるようアノテーションする論文(Structured annotations of web queries)読む．