Shopping for products you don't know you need(WSDM 11) 読んだ

Shopping for products you don't know you need

概要

検索エンジンの検索ログからユーザの商業的な興味を推測する．
この際必要となるのが，全てのクエリが相互に関連しているQuery community．これはクエリをノードとしたグラフにおけるクリークとして表現される．
この論文では2つの方法を使ってrecommendationを行う．

その前に

commercial queryの正確な意味合いが論文中で定義されていなかったのでここで考察する．論文を読む限りでは恐らく，「＊＊＊ならAmazon」などのように，ユーザが購入すると思われる商品名などをcommercial queryと呼んでいると考えられる．
commercial queryを推測するというのはつまり，「ユーザが何を買おうとするだろうか」「ユーザはこれらの行動からどんな商品を欲しているか」を推測するのと同義だと考えられる．

問題設定

こんな感じの検索クエリを考える．

クエリ	日	時間
ルクルーゼ　調理器具	12月12日	10:00 AM
キャストアイロン　レビュー	12月12日	10:01 AM
キャストアイロン　調理法	12月12日	10:02 AM
冬休み	12月13日	07:00 PM
ヨーロッパ　冬休み	12月13日	07:01 PM
ヨーロッパ　天気　冬	12月13日	07:02 PM
リビエラマヤ　旅行	12月13日	07:30 PM
最安　リビエラマヤ　ツアー旅行	12月13日	07:33 PM
リビエラマヤ　最も良いリゾート	12月13日	07:45 PM
メキシカーナ航空　フライト	12月14日	07:00 PM
日焼け止め　防水　購入	12月20日	08:05 PM
水中用カメラ　買うには	12月21日	08:15 PM

このクエリログから推測できる事は，冬休みにどこに行こうか迷った挙句リビエラマヤに行く事を決めたユーザが日焼け止めと水中用カメラを買おうとしているという事である．
理想としてはそれ（日焼け止めと水中用カメラ）を推薦できればいいのだが，

リビエラマヤに行こうとするユーザはキャストアイロンの調理器具を必要としている
ヨーロッパに行こうとしているユーザは水中用カメラを必要としている

といった誤った推薦を行う可能性が考えられる．この原因は検索クエリはノイジーであり，興味は急速に移り変わり，また，興味が全て検索クエリで表現されるわけではないからである．
この論文で扱う問題は，検索クエリからそれに関連する商業用クエリを提示することである．これに関する問題は2つある．一つは，ユーザは様々な方法で意図を表現するという事（リビエラマヤと検索するだけでなく，ユカタン半島，カリビアンなども同様の意味を持つ）．もう一つは共起数が大きいからと言ってその2つのクエリが必ずしも関連があるというわけでない事．
一つ目の問題に取り組むため，query communityを定義する．これは，community内のクエリ全てが関連しているものである．従来のquery suggestionとの違いは，query suggestionでは与えられたクエリ1つとその他のクエリが関連しているものである．
二つ目の問題に対しては2つの推薦手法を提案した．そのうち片方は共起を用いるが工夫してる．もう一方ではユーザのクエリをcommercial queryに対する納得できそうな説明として用いる方法である．

Query Community

query communityの定義

関連性 $R$ について，2つのクエリ $q, q'$ について関連性があるなら $R(q, q')=1$ とし，関連性が無ければ $R(q,q')=0$ とする．この時， $q, q' \in C$ なる全てのクエリについて $R(q, q')=1$ であるような最大の $C$ をquery community と呼ぶ（また，実際 $R$ についてアクセスできないものとする）．
$R$ は頂点がクエリ，エッジを関連性とする無向グラフ $G=(V, E)$ で表現する．
その後は $G$ 上のクリークがquery community になるわけだが，我々は $G$ を直接得る事ができず，それより更にスパースな $\hat{G}$ しかない．この $\hat{G}$ はユーザが2つのクエリを短い時間間隔で検索していたらエッジを張ることにする．また，この $\hat{G}$ におけるエッジは全て ${G}$ に含まれているものとする．
$\hat{G}$ には $G$ においてはクリークではない，偽のクリークが多く含まれていると思われるので，次にグラフから密なサブグラフを得る事によってquery communities のsubsetを得ることにする（ここが何を言っているのか意味が分からない）．というわけで $(\alpha , \beta )-cluster$ というのを考える．

(\alpha, \beta)-clusterの定義

グラフ $G=(V, E)$ について全エッジがセルフループなエッジを持っているとする． $E(c, C)$ を $\{(c,v):\forall v \in C\}$ なるエッジ集合とすると，

Internally Dense: $\forall v \in C$ , $|E(v, C)| \geq \beta |C|$
Externally Sparse: $\forall u \in V \setminus C$ , $|E(u, C)| \leq \alpha |C|$

である時， $C \subset V$ は $(\alpha , \beta )-cluster$ である．
何言ってるかというとクラスタ外部と内部のエッジの比を考えてクラスタですよーと言っている．

Random Delection Model

次に $G$ と $\hat{G}$ の関係について考える．ここでは大雑把に確率pを考えて， $\hat{G}$ は $G$ の各エッジを確率pで残し，確率1-pで削除して得られたと考える．
あとはこの性質を使って query community を抽出する．

The Recovery Algorithm

このアルゴリズムはdensificationとclusteringの二つに分かれる．densificationでは単純にグラフにエッジを足していく．その後， $(\alpha, \beta)-cluster$ を抽出する．
Rubyによる擬似コード．

# 入力: グラフg_hat, サイズk，internal densityであるbeta, external sparsityであるalpha
# 出力: サイズkのcommunityの集合S

def finding_query_communities_in_sparce_graphs(g_hat, k, beta, alpha)
  g_hat.nodes.permutation(2).each do |node_pair|
    # g_hatに存在しないエッジの全てについて処理を試みる
    u, v = node_pair
    next if g_hat.edges.include?(u, v)

    # adjacencies(u) で u の隣接要素のリストが得られるとして
    d[u => v] = ( adjacencies(u) & adjacencies(v) ).size / ( adjacencies(u) | adjacencies(v) ).size
    # 確率d[u => v]でエッジ(u, v)をg_hatに加える #=> densification
    g_hat.add_edge(u, v) if rand() < d[u => v]
  end

  # 返り値
  query_communities = [ ]
  
  g_hat.nodes.each do |c|
    query_community = [ ]
    ( adjacencies(c) | adjacencies( adjacencies(c) ) ).each do |v|
      query_community.push v if ( adjacencies(v) | adjacencies(c) ).size >= (2 * beta - 1) * k
    end

    # (a, b)-clusterかどうかの判定
    query_communities.push query_community if query_community.a_b_cluter?
  end

  return query_communities
end

擬似コード書いてて思ったけど判定式でしか $\alpha$ 使わないのか．
これで無事 query community が得られました．

Recommendation

推薦は共起を使うものとクエリの関係性を「説明」として用いるものの二種類がある．

Co-Occurrence Recommendation Method

検索クエリとcommercial queryについて共起を用いるかなり，非常にナイーブな手法．検索クエリqとcommercial query rについて，qとrの順序を考慮して共起をカウントし，しきい値を超えたら推薦する．順序を考慮する理由は例えば，"HDMIケーブル"と検索する人はすでに"HD TV"を持っていると考えるのが自然であるので，そういった推薦を行わないようにするため．
以下擬似コード．

# 入力: 検索ログ search_log, しきい値theta_1, theta_2
# 出力: keyにq，valueにrを持ち，qについてrを推薦する，といった形式のハッシュ recommendation
def co_occurrence_recommendation(search_log, theta_1, theta_2)
  recommendation = Hash.new
  R = search_log.commercial_queries
  Q = search_log.queries
  
  Q.each do |q|
    R.each do |r|
      # 共起をカウント
      n[q => r] = search_log.count("rを検索する前にqを検索した人")
      n[r => q] = search_log.count("qを検索する前にrを検索した人")
      # しきい値を超えたら推薦
      recommendation[q] = r if n[q => r] > theta_1 && n[q => r] > theta_2 * n[r => q]
    end
  end
  return recommendation
end

Explanations Recommendation Method

今度は共起ではなく，クエリの関係性に「説明」というものを考える．commercial query rが与えられたとき，rが何故検索されたのかという理由を探す．
アルゴリズムが何をやってるのかはわかるがどうしてこれが「説明」になるのかが理解できない．
以下擬似コード．

# 入力: 検索ログ search_log, しきい値theta, commercial query r
# 元論文では r は引数ではないがこちらのほうが分かりやすいのでそう書く
# 出力: rが推薦されるための検索クエリ q のリスト recommendation
def hitting_set_recommendation(search_log, theta, r)
  recommendation = [ ]
  Q = search_log.queries
  U_r = search_log.select("rを検索したユーザが検索していたクエリ")

  while !U_r.empty?
    q = U_r.most_frequentry_query
    # U_rで最も登場したクエリqをそのまま推薦し，U_rから削除する
    recommendation.push q if U_r.most_frequentry_query.count > theta
    U_r.delete_if{|e| e.include?(q) }
  end
  
  return recommendation
end

感想

内容はさておきタイトルが釣りっぽかった．
query community の概念そもそもより，ここでは完全にスルーしてしまった $\hat{G}$ の性質に関しての方が論文のポイントだったのだろう．recommendationの部分が想像以上にあっさりしていた．

糞糞糞ネット弁慶

読んだ論文についてメモを書きます．趣味の話は http://repose.hatenablog.com