[論文紹介@SNLP2023] Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars (ACL2023)

論文紹介 Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars Songlin Yang, Roger Levy, Yoon Kim ACL 2023 上田 亮 (東京大学 宮尾研究室 D1) 2023/08/28 (月) 第 15 回最先端 NLP 勉強会 (SNLP 2023)

目次 1. 論文の概要 2. 背景 (動的計画法側から) 3. 背景 (統語理論側から) 4. 教師なし LCFRS 5. 実験結果など 6. まとめ 1

論文の概要

論文の概要 1/2 Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars :::::::::::::::::::::: ::::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::::::::::::::::::: 不連続 な (; 非交差制約を満たさない) 句構造をもつ 弱文脈依存文法 の 教師なし学習 ::::::::::: :::::::::::::::::::::::: :::::::::::::::::::: 今回活躍する文法は CCG でも TAG でもなく LCFRS (Linear Context-Free Rewriting System) ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: (知名度の低い formalism 故に mildly context-sensitive grammar と言ってウケの良さを狙ったのかなと邪推) 2

論文の概要 2/2 動的計画法側の進展 因子グラフ文法 (FGG) 文法 as 因子グラフ HMM, PCFG の一般化 低ランク FGG パラメタ数削減で 計算の効率化 統語理論側の進展 LCFRS CFG/TAG 等の共通部分 を上手く抽出 教師あり LCFRS 不連続な句構造の Parsing に向いている 教師なしLCFRSの実現へ ::::::::::::::::::::::::::::::::::::::::::: 3

背景 (動的計画法側から)

Factor Graph Grammar (FGG) [Chiang and Riley, 2020] Factor Graph Grammar (FGG) [Chiang and Riley, 2020] 統語構造 as 因子グラフ (Factor Graph) HMM/PCFG の一般化 信念伝搬 (ﾒｯｾｰｼﾞ･ﾊﾟｯｼﾝｸﾞ) は 前向き/内側ｱﾙｺﾞﾘｽﾞﾑの一般化 (賢い より広範な文法の Parsing 実装しやすく ) 画像は [Yang et al., 2022] より拝借 4

PCFGs can do better [Yang et al., 2021] Unsupervised PCFG with Many Symbols PCFG を低ランクなテンソルで効率化した分 非終端記号の数を多くしてみた話 P T = ri=1 ui ⊗ vi ⊗ wi (ui , vi , wi ∈ RN ) DIORA [Drozdov et al., 2019] や PRPN [Shen et al., 2018] を凌ぐ ※両者とも (当時)SoTA の教師なし構文解析 大量の非終端記号さえあれば PCFG でよい？ 隠れ層の大きな CNN 的なもの？ 事後分布が複雑になるのかな？ 5

低ランク FGG [Yang et al., 2022] FGG 文法 as 因子グラフ (前々頁) Many Nonterminals 低ランク化して効率化 (前頁) 低ランク FGG [Yang et al., 2022] 因子 (Factor) as 低ランクなテンソル 前頁よりもさらに効率的なアルゴリズム が得られる さらに効率的な信念伝搬が可能になる 性能も良好 6

背景 (統語理論側から)

Linear Context-Free Rewriting System 筋の良さげな統語理論あるある [Vijay-Shanker et al., 1987] 木 (Tree) から木 (Tree) への 書換 (Rewriting) として定式化されがち :::::::::::::: 線形 (Linear) :::::::::: • 一回の書換で木のサイズがおおよそ線形に増加 • ※小さくならない & 倍々ゲームみたいに増えるわけでもない 文脈自由 (Context-Free) (※導出過程が) :::::::::::::::::::: • 導出過程が過去の書換履歴に依存しない • ※導出過程が文脈自由なのであって 言語が文脈自由とは限らない Linear Context-Free Rewriting System (LCFRS) として抽象化・定式化 (賢い ) ::::::::: 7

Simple Range Concatenation Grammar Simple Range Concatenation Grammar (SRCG) LCFRS と等価 & LCFRS の記述に便利 [Boullier, 1998] LCFRS G = (N, T, V, P, S), where N : a set of nonterminals T : a set of terminals V : a set of variables S ∈ N : a start symbol P 3 A(α1 , . . . , αdim(A) ) → (1) (1) (m) (m) A1 (X1 , .., Xdim(A1 ) ) · · · Am (X1 , .., Xdim(A1 ) ) ::::::: ::::::::::::::::: 8

LCFRS では不連続な句構造を表現できる 自然言語にしばしば見られる不連続な句構造 Wh-movement (英語), V2 語順 (ドイツ語), Cross-serial dependency (オランダ語), etc. LCFRS では不連続な句構造を表現できる 画像は [Yang et al., 2023] より拝借 9

教師あり LCFRS 教師あり LCFRS たまに revisit され 不連続な句構造を表現する手法 としての有用性が確認されてきた模様 [e.g., Maier et al., 2012, Coavoux and Cohen, 2019, Stanojević and Steedman, 2020b] (話が逸れますが) Stanojević & Steedman のバイタリティがすごい Incremental CCG と並行してこんなこともしてたんですね [Incremental CCG: Stanojević and Steedman, 2019, 2020a] 10

教師なし LCFRS

教師あり LCFRS から教師なし LCFRS へ 動的計画法側の進展 因子グラフ文法 (FGG) 文法 as 因子グラフ HMM, PCFG の一般化 低ランク FGG パラメタ数削減で 計算の効率化 統語理論側の進展 LCFRS CFG/TAG 等の共通部分 を上手く抽出 教師あり LCFRS 不連続な句構造の Parsing に向いている 教師なしLCFRSの実現へ ::::::::::::::::::::::::::::::::::::::::::: ※厳密には LCFRS を少し制限した LCFRS-2 11

実験結果など

定性評価 (を 1 つ紹介) 画像は [Yang et al., 2023] より拝借 12

定量評価 (を 1 つ紹介) • NEGRA, TIGER ドイツ語ツリーバンク • LASSY オランダ語ツリーバンク 画像は [Yang et al., 2023] より拝借 13

まとめ

主著者 (Songlin Yang さん) がすごい 主著のリスト (御本人の HP をもとに作成): • • • • • • • • ACL 2023 × 2 EMNLP 2022 (findings) NAACL 2022 (*equal contribution) ACL 2022 × 2 ACL 2022 (findings) ACL 2021 NAACL 2021 COLING 2020 (タイトルを見る限り) 全て Parsing 関連の論文 めちゃくちゃカッコいい 14

まとめ 動的計画法側の進展 Factor Graph Grammar 低ランク FGG 統語理論側の進展 Linear Context-Free Rewriting System 教師なしLCFRSの実現へ ::::::::::::::::::::::::::::::::::::::::::: Parsing は複雑性と効率性のせめぎ合い • Continous vs. Discontinuous • Many Parameters vs. Many Nonterminals 両者のギリギリの境界線が分かりつつある？ GPU の登場によって盤面が変化？ 15

参考文献 i Pierre Boullier. Proposal for a Natural Language Processing Syntactic Backbone. Research Report RR-3342, INRIA, 1998. URL https://inria.hal.science/inria-00073347. David Chiang and Darcey Riley. Factor graph grammars. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6648–6658. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/file/ 49ca03822497d26a3943d5084ed59130-Paper.pdf. Maximin Coavoux and Shay B. Cohen. Discontinuous constituency parsing with a stack-free transition system and a dynamic oracle. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 204–217, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19-1018. URL https://aclanthology.org/N19-1018. Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit Iyyer, and Andrew McCallum. Unsupervised latent tree induction with deep inside-outside recursive auto-encoders. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 1129–1141, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19-1116. URL https://aclanthology.org/N19-1116. 16

• https://inria.hal.science/inria-00073347
• https://proceedings.neurips.cc/paper_files/paper/2020/file/49ca03822497d26a3943d5084ed59130-Paper.pdf
• https://aclanthology.org/N19-1018
• https://aclanthology.org/N19-1116

参考文献 ii Wolfgang Maier, Miriam Kaeshammer, and Laura Kallmeyer. PLCFRS parsing revisited: Restricting the fan-out to two. In Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+11), pages 126–134, Paris, France, September 2012. URL https://aclanthology.org/W12-4615. Yikang Shen, Zhouhan Lin, Chin wei Huang, and Aaron Courville. Neural language modeling by jointly learning syntax and lexicon. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=rkgOLb-0W. Miloš Stanojević and Mark Steedman. CCG parsing algorithm with incremental tree rotation. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 228–239, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19-1020. URL https://aclanthology.org/N19-1020. Miloš Stanojević and Mark Steedman. Max-margin incremental CCG parsing. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4111–4122, Online, July 2020a. Association for Computational Linguistics. doi: 10.18653/v1/2020.acl-main.378. URL https://aclanthology.org/2020.acl-main.378. Miloš Stanojević and Mark Steedman. Span-based LCFRS-2 parsing. In Proceedings of the 16th International Conference on Parsing Technologies and the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies, pages 111–121, Online, July 2020b. Association for Computational Linguistics. doi: 10.18653/v1/2020.iwpt-1.12. URL https://aclanthology.org/2020.iwpt-1.12. 17

• https://aclanthology.org/W12-4615
• https://openreview.net/forum?id=rkgOLb-0W
• https://aclanthology.org/N19-1020
• https://aclanthology.org/2020.acl-main.378
• https://aclanthology.org/2020.iwpt-1.12

参考文献 iii K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi. Characterizing structural descriptions produced by various grammatical formalisms. In Proceedings of the 25th Annual Meeting on Association for Computational Linguistics, ACL ’87, page 104 – 111, USA, 1987. Association for Computational Linguistics. doi: 10.3115/981175.981190. URL https://doi.org/10.3115/981175.981190. Songlin Yang, Yanpeng Zhao, and Kewei Tu. PCFGs can do better: Inducing probabilistic context-free grammars with many symbols. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1487–1498, Online, June 2021. Association for Computational Linguistics. doi: 10.18653/v1/2021.naacl-main.117. URL https://aclanthology.org/2021.naacl-main.117. Songlin Yang, Wei Liu, and Kewei Tu. Dynamic programming in rank space: Scaling structured inference with low-rank HMMs and PCFGs. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4797–4809, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10.18653/v1/2022.naacl-main.353. URL https://aclanthology.org/2022.naacl-main.353. Songlin Yang, Roger Levy, and Yoon Kim. Unsupervised discontinuous constituency parsing with mildly context-sensitive grammars. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5747–5766, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.acl-long.316. URL https://aclanthology.org/2023.acl-long.316. 18

• https://doi.org/10.3115/981175.981190
• https://aclanthology.org/2021.naacl-main.117
• https://aclanthology.org/2022.naacl-main.353
• https://aclanthology.org/2023.acl-long.316