Word Alignment via Submodular Maximization over Matroids - todo314 @ ウィキ

Word Alignment via Submodular Maximization over Matroids

• Hui Lin, Jeff Bilmes
• ACL-HLT 2011

概要だけ

• 単語アラインメント：単語対応をとる
• よくある制約はマトロイド制約で表せる
• 英語: $$ e_1, \ldots, e_I $$
• 仏語: $$ f_1, \ldots, f_J $$
• $$ E=\{1,\ldots,I\}, F=\{1,\ldots,J\} $$
• 欲しい割り当て: $$ A \subseteq = V = E \times F $$
  • E--Fの二部グラフのようなもの

制約

• $$f_j$$には高々$$k_j$$単語しか割り当てない
• $$ |A \cap (E \times \{j\})| \leq k_j $$
• この制約は分割を生成するので，
• $$ \mathcal{I}_E = \{ A \subseteq V \mid \forall j \in F, |A \cap (E \times \{j\})| \leq k_j \} $$
• $$ \mathcal{I}_F = \{ A \subseteq V \mid \forall i \in F, |A \cap (\{i\} \times F)| \leq k_i \}
• 両方共分割マトロイドになる
• マトロイド交差にもなるけど，考えない

目的関数

• モジュラ $$ f(A) = \sum_{i \in E}\sum_{j \in \delta_i(A)} s_{i,j} $$
• 劣モジュラ $$ f(A) = \sum_{i \in E} \left( \sum_{j \in \delta_i(A)} s_{i,j} \right)^\alpha $$
  • iから沢山対応させたとして，少し歪ませる
  • ある程度ばらばらになってほしい（のかな？

• 実験

  モジュラ	$$ \mathrm{Fert}_F(A) \leq 1, \mathrm{Fert}_E(A) \leq 1 $$
  モジュラ	$$\mathrm{Fert}_F(A) \leq 1$$
  モジュラ	$$\mathrm{Fert}_F(A) \leq k_j$$
  劣モジュラ	$$\mathrm{Fert}_F(A) \leq 1$$

  劣モジュラ

  $$\mathrm{Fert}_F(A) \leq k_j$$

  一番良い

• 単に貪欲しているので他の複雑な方法よりかなり速い→やった！

まとめ

• マッチングは確かに色々いけそう

劣モジュラ 自然言語処理

2015/11/24