糞糞糞ネット弁慶

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

Fast query execution for retrieval models based on path constrained random walks(KDD 2010) 読んだ

Fast query execution for retrieval models based on path-constrained random walks

概要

普通のグラフベースのランダムウォークでは,ランダムウォーカーが異なる経路(path)の重要性を理解していない単純なモデルである.
よって,ノードにタイプ,エッジに関係が割り振られたグラフにおいて,移動経路に制約を突っ込んだランダムウォークをPath Constrained Random Walkをこれまでに提案してきた.
その際,ランダムウォークの計算が煩雑になるので近似手法を提案する.
その結果,2〜100倍の高速化を実現し,なおかつ精度もほぼ落ちなかった.

notation

notationが非常に分かりにくい.
まずスキーマが与えられる.はエンティティ(ノード)のタイプの集合であり,は"関係"の集合である.また,各"関係"は2つのタイプを持つ.ここの記法が分かりにくいが,つまりはからに向けて,2つのタイプの間に"関係"がある,という意味である.わざわざ1,2とつけてあり混乱する.
ランダムウォークするグラフはエンティティ関係グラフである.はエンティティの集合である.各エンティティはタイプを持つ().同時に,とする..とする.つまりはエンティティ間に"関係"があれば1とする,みたいな感じ.ここの記述は論文ではとなっていて完全に意味が分からない.ついでにと書く.つまりはの隣接要素集合.
問題定義としては,クエリとしてエンティティ集合とそのタイプが与えられ,その関係を予測する.
具体例として,Twitterの情報をエンティティ関係グラフで表現する事を考える.
http://img.skitch.com/20110515-j2y7fid3tftg596jf85r4haeaj.jpg
この図はTwitterにおけるスキーマの一例である.
まず,タイプにはなどが考えられる.それらを結ぶ"関係"にはなどが考えられる.例えばについては,postからpostにin_reply_toがつくのでであると言える.また,はUserがtweetをpostするのでとなる.
http://img.skitch.com/20110515-m2nqfxda3i4etkbxi3e6wxua25.jpg
このスキーマにエンティティを代入したエンティティ関係グラフがこの図である.スキーマに実体(エンティティ)を突っ込むとこうなる.

Path-Constrained Random Walk

"関係"パスを考える.この時,なる制約を加える.これは,"関係"に順序関係があるという意味である.
について


とする.つまりはRをエッジにして普通にランダムウォークさせる(論文では is short hand for となっている).
あとは得られたrelation pathの集合に対して

でスコアリングする.パラメータは学習.

ランダムウォークの近似

で,このランダムウォーク計算は非常に密になるので近似計算で高速化する.
大体目的としては,本来のランダムウォークにおいてが高くなるものは高く,低いものは低くなってくれると好ましい(そもそも,ページランクなどはべき乗則に従うというのが経験的に知られているので,大雑把に計算したものがべき乗則に従ってくれると嬉しい).

Fingerprint Strategy

値の伝播そのものを諦め,

とする.これは

Speeding up influence calculation : influenceを求めるランダムウォークは繰り返し数を定数cとしてもO(c|D||W|)=O(|D||W|)かかる。これは全記事に対する計算を全単語を一つずつ取り除きながらやるのでこの値になる。これを削減する。やり方はまず単語を取り除かないランダムウォークを行う。その時、どの単語からどの記事に何度遷移したかを数え上げておく。そしてinfluence(d_i, d_j|w)を計算するときの\prod_{w}^{i}(d_j)をランダムウォークを使わず、「wを経由せずにd_jに到達した回数」とする。当然これでは真の値ではないが、どうせ期待値が欲しかったのでこれでも構わないらしい。

Connecting the Dots Between News Articles(KDD 2010) 読んだメモ - 糞ネット弁慶

でも似た方法が使われていた.

Weighted Particle Filtering

particleに関するアナロジーが何を指しているのか分からないが,方法としては閾値を決めて,伝播する値がそれ以上であれば全隣接エンティティに値を伝播し,それ以下であれば隣接するエンティティ1つのみに値を伝播する.

# distribution_h_i: i ステップ目におけるランダムウォークによる確率分布
# relation_R: "関係"
# relation_R(e, *)でeの隣接要素全てを取得するものとする
# min_particle_size_e: 打ち切り判定で用いるパラメータ epsilon
def weighted_particle_filtering(distribution_h_i, relation_R, min_particle_size_e)
  # i+1 ステップ目におけるランダムウォークによる確率分布を初期化
  distribution_h_i_1 = Hash.new{0}

  distribution_h_i.each_pair do |e, value|
    next if value == 0
    # e からのランダムウォークで一度に伝播させる値
    size_new = value / relation_R(e, *).size

    # 伝播させる値がパラメータ epsilon より大きいか判定
    if size_new > min_particle_size_e
      # 大きければ全ての隣接エンティティに伝播
      relation_R(e, *).each do |e_dash|
        distribution_h_i_1[e_dash] += size_new
      end
    else
      # 大きくなければランダムにどこか1つのエンティティのみに値を伝播
      e_dash = relation_R(e, *).sample
      distribution_h_i_1[e_dash] += distribution_h_i[e]
    end
  end

  # i+1 ステップ目の値を返して終了
  return distribution_h_i_1
end
Truncation Strategies

これも値を打ち切る.通常のランダムウォークによってを求めた後に,とする.つまりはパラメータで減衰をかけるし,より小さければ0にし,それ以上伝播を行わせないようにする.
もう一つ,beam truncationというものも考える.これはで伝播を行う.はW番目に大きいの値であり,Wをビーム幅と呼ぶ事にする.

実験

色々やった.少しのロスだけで2〜100倍の高速化を実現した.
スパース化のアプローチによって,高速化だけでなく,出力のクオリティも向上した.

感想

主眼であったと思われるスパース化による高速化よりも,経路に制限を加えるランダムウォークや,タイプや関係性を考えるランダムウォークに興味があった.リッチなデータは整形するのがめんどくさそうだし,ここで人力アノテータの出番かと思うと胸が熱くなる.