「Word Alignment via Submodular Maximization over Matroids」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 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$$|
- モジュラ
--
* 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$$|一番良い|
- 単に貪欲しているので他の複雑な方法よりかなり速い→やった！
* まとめ
- マッチングは確かに色々いけそう
&tags()
2015/11/24
