Crowdsourcing Algorithms for Entity Resolution - todo314 @ ウィキ

Crowdsourcing Algorithms for Entity Resolution

• Norases Vesdapunt, Kedar Bellare, Nilesh Dalvi
• VLDB 2014

概要

• Entity Resolution = 同じエンティティを差すレコード集合を特定する
• 入力=uncertain graph（辺確率はある種の信念）
• 人間に各点対の辺の有無を質問できる
• 出来るだけ少ない質問数で、完遂したい
  • 推移閉包の性質を利用する
• 手法を提案
  • 既存の手法は実は良くない
• 実験したよ

問題定式化

• Uncertain graph $$ G=(X,E) $$
• 各辺eは確率p(e)で生きる
• ランダムグラフがクラスタリングになっていればOK
  • クリークの互いに素な和になってる
• Q=あり得るクラスタリング全体の確率分布
  • クリーク和になると条件付けする必要がある
• 信託：辺の有無（YES/NO）を答える
• 目標：クリーク和を完璧に特定する
• $$ \mathsf{cost}(\pi) $$ :=分布Q上で戦略πの期待信託呼出回数
• CROWD-CC: cost最小のπを見つける

計算量解析

• 補題3: 信託を呼ばなくても分かる場合
  1. $$(x_1,x_2) \in E$$ : x1からx2までYESな辺だけの経路がある
  2. $$(x_1,x_2) \not\in E$$ : x1からx1'までYES経路、x2からx2'までYES経路、x1'-x2'間にNO辺
• 最悪時
  • cost(π,C) := Cに固定した上での呼出回数
• 補題6: $$ \mathsf{cost}(\pi,C)≦2(n+1)\mathsf{cost}(\pi^*,C)$$
  • 最適手法が必要な呼出回数と、任意手法の呼出回数の上限
• 定理7: Cの分布で期待値をとっても成立

既存手法[Wang-Li-Kraska-Franklin-Feng. SIGMOD'13] $$\pi_{\mathrm{dec}}$$

• 辺確率の降順に見る、実はあまり良くない
• クラスタ間の辺確率を高く、クラスタ内の辺確率を低くすると、先に無意味なクエリをしまくる
• 本当にそんなのがありますか？！を以下で議論
• Correlation clustering $$H(V,E^+,E^-)$$ からCROWD-CC $$G(X,E),p$$ への変換
  • $$ p(e) = \begin{cases} 1-\epsilon & e\in E^+ \\ \epsilon & e\in E^- \end{cases} $$
• 最適CCクラスタリング$$C_0$$が唯一であるとする
• 補題10: $$ \mathsf{cost}(\pi) = \mathsf{cost}(\pi,C_0)+O(1) $$
  • 但し、$$ \epsilon_0 := \frac{\epsilon}{1-\epsilon} = n^{-n-2} $$
  • C0から一つでも非賛同が増えると、発生確率にε0倍のギャップので、C0がcostに支配的
• 補題11: 最適クラスタリングが2クラスタで間にΩ(n^2)本の辺がある入力がある

アルゴリズム

• 補題3で特定できる不要呼出は自動的に排除
• 乱択アルゴリズム $$\pi_{\mathrm{rand}}$$
  1. ランダムに頂点対を選ぶ
  2. クエリを打つ
  3. 真だったら頂点対を縮約
  • クラスタ数=kなら、O(k)ステップ以内で真辺が見つかる→頂点数が1減る
  • O(nk)呼出で十分
  • O(k)-近似
    • 解析がちょっと怪しい
• 頂点優先順位 $$\pi_{\mathrm{node}}$$
  1. $$ \mathbf{for} \ i = 1 \ \mathbf{to} \ n $$
  2. $$ \;\; \mathbf{for} \ j = 1 \ \mathbf{to}\ i-1 $$
  3. $$ \;\;\;\; (x_i, x_j) $$にクエリを打つ
  • O(k)-近似（iループの頂点順位に関わらず）
  • ヒューリスティクス
    • 内部ループは高確率順、外部ループは(Σ_近傍 辺確率)順

実験

• データセット
  • Cora, Places, Product
• 手法
  • dec, rand, nodeを比較
• Progressive recall: 質問数 vs. 特定した同一組数／真の同一組数
  • nodeが良い感じ（ホントか❔）
• Complete resolution: 完璧にGUESSするまでのクエリ数の鋭敏性
  • 適当の割合の辺確率を反転させる
    • 引っ繰り返すとdecがやばいことにする、nodeも悪化する
    • randは辺確率に影響されないので、安定
  • 辺確率をビンに分けて粗くする
    • 何故かopt以下になっている手法が有るが何故？

まとめ

• 所々怪しい…が問題としては分かりやすいので良い感じ
• 確率分布の定式化が微妙な気がする

VLDB entity resolution uncertain graphs クラウドソーシング

2017/06/26