CRPを用いた格フレーム構築（英語） [@Kawahara:2014:EACL]

概要

以下の3ステップで構築する

各項構造ごとに”predominant argument”を選ぶ
- dobj, ccomp, nsubj, prep ∗, iobjの順序の中うち，最も高い順位をもつ項
- I sold it.ならdobjのit,It sellsならnsubjのIt
動詞とpredominant argumentの双方が共通している項構造ごとにグループを作る（初期フレーム）
フレームを構成する項構造の頻度の和が10以下のフレームは捨てる

初期格フレームのイメージは以下の通り

この初期フレームの動詞はobserve，predominant argumentはdobj:effect
- 総頻度 140
- nsubj {they 30, we 20, …}
- dobj {effect 140}
- prep_at {time 20, …, …}

Chinese Restaurant Process (Aldous, 1985)でクラスタリング
初期フレーム $v_i$ がフレーム $f_j$ に属する事後確率(posterior) $P(f_j \mid v_i)$
- $P(f_j \mid v_i) \propto \frac{n(f_j)}{N + \alpha} \cdot P(v_i \mid f_j)$
- 第1項が事前確率(prior)，第2項が $v_i$ の尤度(likelihood)
尤度 $P(v_i \mid f_j)$ はディリクレ多項分布で定義される
- $P(v_i \mid f_j) = \displaystyle \prod_{w \in V} P(w \mid f_j)^{count(v_i, w)}$
$P(w \mid f_j)$
- $P(w \mid f_j) = \frac{count(f_j, w) + \beta}{\sum_{t \in V} count(f_j, t) + \mid V \mid \cdot \beta}$
- $f_j$ が新規のときは $\frac{1}{\mid V \mid}$
Notations
- $N$ : 初期フレームの数
- $n(f_j)$ : 現在 $f_j$ に割り当てられている初期フレームの数．ただし $f_j$ が新規のとき $n(f_j)=\alpha$
- $\alpha$ : 新しいフレームがどのくらい作られやすいかを表すハイパーパラメータ
- $count(v_i, w)$ : $v_i$ の中の $w$ の頻度
- $count(f_j, w)$ : $f_j$ の中の $w$ の頻度
- $\mid V \mid$ : 全フレーム中の語彙の異なり総数 (注:subj:youとdobj:you等，格が異なれば違うものとして扱う)
- $\beta$ : ディリクレ分布のハイパーパラメータ

ギブスサンプリングの方法

全初期フレームにランダムにフレーム番号を与える
以下の「サンプリング」を各初期フレームに対して順に行う
- 着目している初期フレーム $x$ が属するフレームから， $x$ を抜いて，頻度分布を計算する
- その頻度分布をもとに， $x$ が所属するフレームを求める確率分布を計算する
- その確率分布を元に $x$ の新しい所属フレームを求め， $x$ に割り当てる
- （以後 $x$ の割り当てが変更されるまで，この割り当てを用いて計算する）
2を $B$ 回（数十回）繰り返す
2を $I$ 回（数百回）繰り返す
4のループ内で最も割り当てられた回数が多いフレームを，それぞれの初期フレームが真に所属するフレームとする

各フレームごとに， $v_i$ のposteriorを計算し，その確率分布に従い，確率的に次の所属先を決定する
$posterior \propto prior \cdot likelihood$ だが，計算を簡単にするために， $\log(prior \cdot likelihood)$ を求める
$\log(prior \cdot likelihood) = \log(prior) + \log(likelihood)$
$\log(prior) = \log( n(f_j) ) - \log (N + \alpha)$
$\log(likelihood) = \displaystyle \sum_{w \in V} ( count(v_i, w) \cdot ( \log A_w - \log B_w) )$
- $\log A_w = \log (count(f_j, w) + \beta)$
- $\log B_w = \log ( \sum_{t \in V} count(f_j, t) + \mid V \mid \cdot \beta )$
計算例
- $\mid V \mid = 879$ , $N = 5$ ,
- $f_j$ $f_{j}$ の例: 用例数30, 項の総和50, 現在の所属初期フレーム数 $n(f_j)=3$ $n (f_{j}) = 3$
  - dobj 20: bread 10, sushi 10
  - subj 30: I 25, you 5
- $v_j$ $v_{j}$ の例: 用例数20, 項の総和25
  - dobj 5:sushi 5
  - subj 20: I 12, you 8
- $\log(prior) = \log 3 - \log (5 + \alpha)$
- $\log(likelihood) = 12 \dot (\log (25 + \beta) - \log(50+879 \beta)) + 8 \dot (\log (5 + \beta) - \log(50+879 \beta)) + 5 \dot (\log (10 + \beta) - \log(50+879 \beta))$