---
title: [論文紹介@SNLP2023] Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars (ACL2023)
tags: 
author: [Ryo Ueda](https://www.docswell.com/user/ryo-ueda)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/4EZVPQD6J3.jpg?width=480
description: 第15回最先端NLP勉強会で発表予定のスライド（準備中です）
published: August 21, 23
canonical: https://www.docswell.com/s/ryo-ueda/5M1Q1N-snlp-2023-08-28
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/4EZVPQD6J3.jpg)

論文紹介
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)


# Page. 2

![Page Image](https://bcdn.docswell.com/page/Y765M61LEV.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/G75YZ64M74.jpg)

論文の概要


# Page. 4

![Page Image](https://bcdn.docswell.com/page/9J2GRMVRJR.jpg)

論文の概要 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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/DEYVDX35EM.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/VJNM61V478.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/YE9NL564E3.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/GE8KXYZV7D.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/LELZ84DRJR.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/4JMV6KPPJW.jpg)

背景 (統語理論側から)


# Page. 11

![Page Image](https://bcdn.docswell.com/page/PJR2PX1YE9.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/PEXD36Y47X.jpg)

Simple Range Concatenation Grammar
Simple Range Concatenation Grammar (SRCG)
LCFRS と等価 &amp; 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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/3EKXY13P7D.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/L7359QG4E5.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/87DDG9157G.jpg)

教師なし LCFRS


# Page. 16

![Page Image](https://bcdn.docswell.com/page/VJPX3ZQD78.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/2EVL4W5GJQ.jpg)

実験結果など


# Page. 18

![Page Image](https://bcdn.docswell.com/page/57GX1DPDEL.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/4EQ8D12XJP.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/KJ42ZRL2E1.jpg)

まとめ


# Page. 21

![Page Image](https://bcdn.docswell.com/page/LE1MRQLK7G.jpg)

主著者 (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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/GEW31MVPE2.jpg)

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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/47ZVPQ46E3.jpg)

参考文献 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


# Page. 24

![Page Image](https://bcdn.docswell.com/page/YJ65M63L7V.jpg)

参考文献 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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/GJ5YZ6LMJ4.jpg)

参考文献 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


