Inferring semantic query relations from collective user behavior
概要
またもやeBay Research Labs．
クエリにおけるSemanticな関係性を分析する．
3種の類似度指標を考え，それぞれをグラフで表現する．その後，それらを線形結合し，クエリqに対して関連したクエリを出力する．
普通のクエリ推薦技術だけではなく，検索時に商品ページがゼロ件であるような状況（null results）へも対応可能であるとしている．
TEXTUAL SIMILARITY
文字列の類似度．
クエリをという，ユニークな単語
の集合で表現するとする．
そのクエリに対し，次に挙げるような2種類のクエリに対しエッジを張る．
を満たすような
．これは元のクエリに単語を追加したクエリ．
を満たすような
．これは元のクエリから単語を取り除いたクエリ．
エッジの重みは，違う単語の個数
について
とする．
こうして得たグラフをTerm Connection Graphと呼ぶ．
SIMILARITY BASED ON USER SESSIONS
ユーザ情報を用いた類似度．
ユーザが購入行動を行ったセッション内における二回のクエリ入力を取り出す．
二つのクエリの間に重みとなるエッジを張る．この
は二つのクエリが登場した回数によって重みをヒューリスティックに決定している．例えば，10000回登場していれば0.9，200回から1000回の間であれば0.6など．
SIMILARITY BASED ON A FUNCTION MAPPING QUERIES TO A HIGHER DIMENSIONAL SPACE
今度はクエリと商品ページを結びつける．具体的には"britney spears"で検索し，"britney spears poster 8x10 new"という商品を購入した場合，"britney spears"というクエリに対し{:poster => 1, :8x10 => 1, :new => 1}という特徴ベクトルを付与する．続いて，他のユーザが"britney spears"で検索し，"britney spears fantasy perfume new"という商品を購入した場合，"britney spears"の特徴ベクトルを{:poster => 1, :8x10 => 1, :new => 2, :fantasy => 1, :perfume => 1}と更新する．この特徴ベクトルは数え上げた後，クエリの登場回数で正規化する．こうすることにより，比較的短い検索クエリを高次元空間へマッピングできる．
この特徴ベクトルを用いてクエリ間の類似度を計算していく．まずクエリごとに最大25個（これは予備実験で求めた精度を失わずに高速に計算できる個数）の特徴を用い，とする．
SEMANTIC QUERY NETWORK
あとは3つの指標をとやって線形結合．
応用
色々書かれているけど印象的なのは"7.3 Recovery from Null Results"．売り手とユーザとで用いる語彙が違っていたり，クエリが独特過ぎたりする場合，検索結果が0件になってしまう．関連する適切な，かつ，ユーザの意図にそったクエリをこの手法で推薦してやるとビジネスチャンスが潰える事が無い．
感想
SIMILARITY BASED ON A FUNCTION MAPPING QUERIES TO A HIGHER DIMENSIONAL SPACEのアプローチは興味深く感じた．
実際のシステムでこの手法がどのように用いられ，どの程度収益に貢献しているのか，A/Bテストなどでユーザの行動がどのように変化したか，などの部分が抜け落ちているのが惜しいと感じた．
あとをkernelと表現するのは間違ってはいないけど違和感を覚えた．Conclusionsに
Description of a kernel function that can map short queries to a high dimensional feature space based on the characteristics of inventory sold and effectively depict query-query semantic similarity.
Inferring semantic query relations from collective user behavior
などと記述してあるのでどこにそんな式があったかと何度も見返してしまった．
