# 雑音のある通信路モデルを用いた句構造解析

原田慎太朗 1 渡辺太郎 $^{1}$ 大内啓樹 1,2
1 奈良先端科学技術大学院大学 2 理化学研究所
\{harada.shintaro.hk4, taro, hiroki.ouchi\}@is.naist.jp

## 概要

構文解析モデルである分類/識別モデルおよび結合モデルは多くの学習データを必要する. しかし、学習データとして利用される Treebank の構築には膨大な人日を必要とするため、低資源下で機能する構文解析モデルが求めらる。これに対して、雑音のあ る通信路モデルを用いた句構造解析モデルを提案 する. 雑音のある通信路モデルは問題を分割してお り、学習に必要なデータ数を抑えることができる.

本研究では、構造が比較的単純な sequence-tosequence モデルで句構造解析を定式化する. 実験結果として、英語および中国語データセットにおい て、本モデルが有効であることを確認した。また、低資源設定においても有効であることを確認した。

## 1 はじめに

構文解析は、単語関係または階層的構造を計算す る問題である. その結果、入力文の解釈性が高まる ため、言語学や自然言語処理における基本的なタス クである．それゆえに研究は盛んであり、多数の高精度かつドメイン特有の句構造解析モデルが提案さ れている。構文解析モデルである分類識別モデル あるいは結合モデルには非常に多くの学習データが 必要である. しかし、構文解析の学習データとして 使用される Treebank の訓練データは、他のデータと 比較すると非常に少ない. さらに、Treebank の構築 および拡張には莫大な時間と言語学的な専門性が必要である.

この課題に対処するために、雑音のある通信路モ デルを用いた句構造解析モデルを提案する. 雑音の ある通信路モデルは、通信路モデルと言語モデルに 分割できる。通信路モデルは入力をうまく説明する 出力を選択ように学習する. これにより、直接モデ ルで起こりうる、入力の一部から出力が予測される という問題を回避でき [1]、その結果、データシフ トに頑健なモデルになる. 言語モデルは、対ではな
いデータから学習可能であり、出力言語における良 さをモデル化できる. 雑音のある通信路モデルは誤 り訂正や音声認識の分野で使用されてきたモデルで あり、近年では深層学習に拡張され [2]、機械翻訳 $[3,4]$ や対話生成 $[5]$ などで優れた性能を発揮してい る. 特に、低資源設定では通常のモデルより大きな 効果を発揮できる.

本研究では、雑音のある通信路モデル用いるにあ たり構文解析を Seq2Seq (sequence-to-sequence) 問題 として定式化する. 英語（PTB: Penn Treebank）お よび 中国語（CTB: Chinese Treebank）における実験、 および、低資源設定における結果より、本モデルが 有効であることを確認した。

## 2 関連研究

構文解析アルゴリズム 句構造解析において、 Chart 型、Transition 型、Seq2Seq 型が代表的なアル ゴリズムとして挙げられる. Chart 型は、各スパン のスコアを計算し、動的計画法を用いて生成可能な 木構造を求める. そのため、高性能であるが文長 $n$ に対して $\Theta\left(n^{3}\right)$ の計算量を持つ. Transition 型は、履歴を考慮した語彙的特徴を持つ Shift-Reduce 操作を 繰り返し選択することにより、木構造を求める. 最先端の性能は持たないが文長 $n$ に対して $O(n)$ の計算量で解析可能である. Seq2Seq 型は Chart 型およ び Transition 型と比較して、モデル設計が比較的簡単である. また、ビームサーチデコーディングを採用することで、出力長 $m$ に対してビームサイズ $k$ で 性能と計算量 $O(\mathrm{~km})$ を調整できる。

Seq2Seq 型は線形化した構文木（S 式）を構成す る開/閉括弧およびラベルを単語と見なすことで定式化される [6]. ここにおける線形化とは、構文木 の終端ノードを記号に置き換える操作である. 線形化手法には様々な方法 $[6,7,8]$ が提案されている が、本研究では代表的な $\mathrm{S}$ 式の線形化 $[6,7]$ を用 いる. その例を表 1 に示す.ここで、表 1 におけ る LBD (Linearized by Dummy)、LBP (Linearized by

Pre-Terminal)、LBT（Linearized by Treminal）はそれ ぞれ線形化手法の名称であり、それぞれ終端ノード をダミ一記号 “XX“、前終端記号、終端記号で置き 換える。さらに、開/閉括弧にもラベルを付ける。

構文解析モデル 構文解析モデルは大きく分け て分類/識別モデルおよび結合モデルに分けられる.分類/識別のモデルは、Transition-based モデル [9]、 Chart-based モデル [10]、Seq2Seq モデル [6,7,11] が 挙げられる. Transition-based モデルと Chart-based モ デルはそれぞれ木構造を構成する操作とラベル付き スパンを識別する。それに対して、Seq2Seq モデル は木構造を構成する線形化された記号を識別する.結合モデルは、木構造を構成するルールの生成確率

成する単語および操作の生成確率をモデル化する 手法 [14] などが挙げられる. 最尤推定、あるいは、 ニューラルネットワークによる学習のために ha 、多くのデータを必要とする。

## 3 雑音のある通信路句構造解析器

本研究では、構文解析を Seq2Seq モデルを用いて 以下のようにモデル化する.

$
P(\boldsymbol{y} \mid \boldsymbol{x})=\sum_{i=1}^{|\boldsymbol{y}|} P\left(y_{i} \mid \boldsymbol{y}_{<i}, \boldsymbol{x}\right)
$

ここで， $\boldsymbol{x}$ は単語列、 $\boldsymbol{y}$ を線形化された記号列、 $|\boldsymbol{y}|$ は出力する記号列の長さであり， $\boldsymbol{y}_{<i}$ は記号 $y_{i}$ より 前の記号列 $x_{1}, \ldots, y_{i-1}$ を表す.ここで、ベイズの 定理 $P(\boldsymbol{y} \mid \boldsymbol{x}) \propto P(\boldsymbol{x} \mid \boldsymbol{y}) P(\boldsymbol{y})$ より、雑音のある通信路モ デルは、線形化された記号列 $\boldsymbol{y}$ から単語列 $\boldsymbol{x}$ を生成 する通信路モデル $P(\boldsymbol{x} \mid \boldsymbol{y})$ と線形化された記号 $\boldsymbol{y}$ の 言語モデル $P(\boldsymbol{y})$ から以下のようにモデル化される.

$
P(\boldsymbol{x} \mid \boldsymbol{y})=\sum_{i=1}^{|\boldsymbol{x}|} P\left(x_{i} \mid \boldsymbol{x}_{<i}, \boldsymbol{y}\right)
$

ここで， $|\boldsymbol{x}|$ は入力文の長さであり， $\boldsymbol{x}_{<i}$ は単語 $x_{i}$ よ り前の単語列 $x_{1}, \ldots, x_{i-1}$ を表す.

雑音のある通信路モデルは、出力から入力を予測 するため低資源設定でも効果を発揮できることが報告されている [2]. そのため、比較的学習データ数の 少ない Treebankでも有効であることが期待できる. さらには、言語モデルで木構造の良さをモデル化す ることが可能である. そのため、既存のモデルとは 異なり、木構造を意識しながらデコーディングする ことで学習時と推論時のズレを抑えることが期待で きる. 事実、先行研究 [15] は直接モデルに木構造の保証するための制約付きデコーディングを導入して いるが、制約無しと比べて精度が低下している。

雑音のある通信路モデルを用いて $\boldsymbol{x}$ から $\boldsymbol{y}$ を生成 するためには、 $\operatorname{argmax}_{\boldsymbol{y}} \log P(\boldsymbol{x} \mid \boldsymbol{y})+\log P(\boldsymbol{y})$ を計算 する必要がある。しかし、通信路モデル $P(\boldsymbol{x} \mid \boldsymbol{y})$ は各候補 $\boldsymbol{y}_{<i}$ に対して条件付きであり、各語彙に対して 別々の順伝搬が必要なため計算量が大きくなる.こ の問題を軽減するに、先行研究 $[2,3,4]$ ではビーム サイズ $k 1$ と $k 2$ を用いた 2 段階のビームサーチを採用しており、直接モデル、通信路モデル、言語モデ ルの線形結合でデコーディングする.

$
\frac{\lambda_{\text {dir }}}{n} \log P(y \mid x)+\frac{\lambda_{c h}}{m} \log P(x \mid y)+\frac{\lambda_{l m}}{m} \log P(y)
$

ここで、 $m$ は入力文の長さであり、 $n$ はこれまで出力した記号の長さである. また、 $\lambda_{d i r} 、 \lambda_{c h} 、 \lambda_{l m}$ は それぞれ、直接モデル、通信路モデル、言語モデル に対する重みを示すハイパーパラメータである.

時間的複雑さは、各部分候補に対して入力全体の スコアリングを繰り返し行うため $O\left(k_{1} k_{2} m n\right)$ になる が、GPUでは並列処理できるため、ほぼ無視できる [3]. ただし、通信路モデルの出力確率の計算的複雑 さは $k_{1} \times k_{2} \times S \times V$ であり、メモリを多く確保する ためにデコーディング時のバッチサイズを大幅に小 さくする必要がある.ここで、 $S$ は入力の最大文長、 $V$ は出力の語彙数である．そのため、GPUで並列化 できる計算量が少なくなり推論速度が低下する。そ こで、先行研究 [4] では語彙数 $V$ を語彙の中で最も 頻度の高い部分集合の数を示すハイパーパラメータ $V^{\prime}$ に置き換えることで計算的複雑さを抑えている.

## 4 実験

実験データは PTB と CTB を用いる. データの分割および前処理は先行研究 [10] に従う．ただし、頻度が 5 未満の単語を未知語として処理した. データ の内訳は表 2 に示す. 先行研究 $[7,11]$ では LSTM モ デルを用いているが、本研究では Seq2Seq モデルと 言語モデルに数多くのタスクで高い性能を発揮する Transformer モデル [16] を用いる. 学習および推論時の設定については付録 $\mathrm{A}$ に記載する。

木構造の評価は $\mathrm{EVALB}^{1}$ )を用いる。今回の構文解析モデルは木構造を構成するためのルールに従わな いため、有効な木構造を保証しない。また、EVALB は無効な木構造を評価対象の母数に含めないため、

1) https://nlp.cs.nyu.edu/evalb/
文 he had an idea 。

$\mathrm{S}$ 式 (S (NP (PRP he)) (VP (VBD had) (NP (DT an) (NN idea))) (. .))

LBD (S (NP XX NP) (VP XX (NP XX XX NP) VP) XX S)

LBP (S (NP PRP NP) (VP VBD (NP DT NN NP) VP) . S)

LBT (S (NP he NP) (VP had (NP an idea NP) VP) . S)

$\mathrm{F}$ 值による比較が難しい。ここで、無効な木構造は 次の通りである：(1) 開括弧と閉括弧の個数が一致 しない.（2）終端記号の個数が入力文に含まれる単語数または字面が一致しない，そこで、無効な木構造を評価対象の母数に含め計算した比較可能な $\mathrm{F}$ 值 （CF: Comparable F-measure）も報告する.

木構造の表現による性能の違いを確認するため に、左側に分解した二分木 (LLBD、LLBP、LLBT) と右側に分解した二分木 (RLBD、RLBP、RLBT）も 用いた. さらに二分木変換後に単鎖を結合すること で、系列長を $3 n$ で統一する. ここで、 $n$ は木構造に 含まれる単語数である。

## 5 結果

簡易化のために、直接モデル、通信路モデル、言語モデルをそれぞれ DIR、CH、LM で表す. 本研究 では、DIR、DIR+LM、DIR+CH+LM という三つのモ デルで実験を行う．また、 $\mathrm{CH}$ の必要性を示すため に、DIR+LM の実験も示す.

## 5.1 定量評価

表 3 と表 4 にそれぞれ PTB と CTB における構文解析の結果を示す. ここで、表 3 と表 4 における CP と CR は比較可能な適合率と再現率を示す. PTB と CTB において、DIR+CH+LM が他のモデルより数多 くの有効かつ質の良い木構造を出力することが確認 できる. 線形化手法について、PTB ではダミ一記号 による線形化手法（LBD）が、CTB では前終端記号 による線形化手法（LBP）が最も良い. 二分木につ いては、PTB と CTB において二分木の有効性には ばらつきがあり、言語または Treebank の特徴に依存 すると考えられる。表 3 PTB における実験結果

## 5.2 定性評価

図 1 にLBP形式のPTBテストセットにおける出力例を示す. DIR および DIR+LM のモデルでは、“all“ の品詞または階層的位置の予測に失敗している。ま た、DIR+LM モデルは、“care of in the music man“を 名詞句として予測してしまい、木構造を正しく出力 することに失敗している。しかし、DIR+CH+LM は 木構造を正しく出力できている。これより、 $\mathrm{CH}$ が DIR およびLM の失敗を修正していることが分かる.

## 5.3 低資源設定における定量評価

雑音のある通信路モデルが低資源設定の句構造解析において有効であるかを調べるためにLBP 形式 のPTB および CTB の訓練データを $10 \%$ 刻みで分割
表 4 CTB における実験結果

してモデル学習した. 結果を図 2 に示す. 低資源設定の PTB と CTB において、DIR+CH+LM の性能が 全体的に高いことが確認できる. また、他のモデル では性能が低下する箇所でも、DIR+CH+LM は頑健 に動作しており、低資源設定においても有効である ことが確認できる.

## 6 おわりに

本研究では、低資源かつ高性能な句構造解析器 の構築を目的に雑音のある通信路を用いた句構造解析器を提案した. 結果、雑音のある通信路を用 いた句構造解析器が PTB および CTB、さらには低資源設定においても有効であることを確認した。 また、Treebankによって有効な線形化手法が異な ることを確認した. 今後の課題として、常に正し い木構造を保証するために制約付きデコーディン グ [11,15]の導入を試みる。また、NPCMJ（NINJAL Parsed Corpus of Modern Japanese) ${ }^{2)}$ や Arabic Treebank など実験データの種類を増やし提案手法の有効性を 検証する。

2) https://npcmj.ninjal.ac.jp/interfaces/

図 1 木構造の比較 (一番目: GOLD、二番目 : DIR、二番目:DIR+LM、四番目 : DIR+CH+LM)

図 2 低資源設定の PTB と CTBにおける実験結果

## 謝辞

本研究は JSPS 科研費 JP19K20351 および JP20K23325 の助成を受けたものである.

## 参考文献

[1] Dan Klein and Christopher D. Manning. Conditional structure versus conditional estimation in nlp models. In Proceedings of the ACL-02 Conference on Empirical Methods in Natural Language Processing - Volume 10, EMNLP '02, p. 9-16, USA, 2002. Association for Computational Linguistics.

[2] Lei Yu, Phil Blunsom, Chris Dyer, Edward Grefenstette, and Tomás Kociský. The neural noisy channel. CoRR, Vol. abs/1611.02554, , 2016.

[3] Kyra Yee, Yann Dauphin, and Michael Auli. Simple and effective noisy channel modeling for neural machine translation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 56965701, Hong Kong, China, November 2019. Association for Computational Linguistics.

[4] Shruti Bhosale, Kyra Yee, Sergey Edunov, and Michael Auli. Language models not just for pre-training: Fast online neural noisy channel modeling. In Proceedings of the Fifth Conference on Machine Translation, pp. 584-593, Online, November 2020. Association for Computational Linguistics.

[5] Qi Liu, Lei Yu, Laura Rimell, and Phil Blunsom. Pretraining the noisy channel model for task-oriented dialogue. Trans. Assoc. Comput. Linguistics, Vol. 9, pp. 657-674, 2021.

[6] Oriol Vinyals, Ł ukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. Grammar as a foreign language. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, Vol. 28. Curran Associates, Inc., 2015.

[7] Mitchell Stern, Daniel Fried, and Dan Klein. Effective inference for generative neural parsing. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 1695-1700, Copenhagen, Denmark, September 2017. Association for Computational Linguistics.

[8] Daniel Fernández-González and Carlos GómezRodríguez. Enriched in-order linearization for faster sequence-to-sequence constituent parsing. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 4092-4099, Online, July 2020. Association for Computational Linguistics.

[9] Taro Watanabe and Eiichiro Sumita. Transition-based neural constituent parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1169-1179, Beijing, China, July 2015. Associ- ation for Computational Linguistics.

[10] Nikita Kitaev and Dan Klein. Constituency parsing with a self-attentive encoder. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2676-2686, Melbourne, Australia, July 2018. Association for Computational Linguistics.

[11] Jun Suzuki, Sho Takase, Hidetaka Kamigaito, Makoto Morishita, and Masaaki Nagata. An empirical study of building a strong baseline for constituency parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 612-618, Melbourne, Australia, July 2018. Association for Computational Linguistics.

[12] Michael Collins. Three generative, lexicalised models for statistical parsing. In 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pp. 16-23, Madrid, Spain, July 1997. Association for Computational Linguistics.

[13] Slav Petrov and Dan Klein. Improved inference for unlexicalized parsing. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pp. 404-411, Rochester, New York, April 2007. Association for Computational Linguistics.

[14] Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. Recurrent neural network grammars. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 199-209, San Diego, California, June 2016. Association for Computational Linguistics.

[15] Daniel Deutsch, Shyam Upadhyay, and Dan Roth. A general-purpose algorithm for constrained sequential inference. In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), pp. 482-492, Hong Kong, China, November 2019. Association for Computational Linguistics.

[16] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arXiv:1706.03762, 2017.

[17] Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of NAACL-HLT 2019: Demonstrations, 2019.

[18] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.

[19] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. CoRR, Vol. abs/1512.00567, , 2015.
表 5 雑音のある通信路モデルのハイパーパラメータ

## A 学習設定

## A. 1 モデルのハイパーパラメータ

Seq2Seq モデルと言語モデルには、それぞれ Fairseq[17]で提供されている transformer_iwslt_de_en と transformer_lmを用いた.

## A. 2 学習のハイパーパラメータ

モデルの学習における最適化アルゴリズムには Adam[18]を用いた. 目的関数はラベル平滑化交差 エントロピー [19]を用い，平滑化パラメータは 0.1 とした. 全ての実験において、バッチサイズは 4096 単語とし、4GPU でモデルを学習させた. モデルの パラメータ更新回数は 100,000 回とした. また、学習率は 4000 回更新時で $5 \mathrm{e}-4$ となるように線形的に 増加させ、以降は更新回数の平方根の逆数に比例し て減衰させた [16].

## A. 3 推論のハイパーパラメータ

デコーディングに用いたハイパーパラメータを 表 5 に示す. ハイパーパラメータは開発用セットに おいて最も性能が良いものを選択した. なお、ビー ムサイズは 1 から 5 までを 1 刻みで、モデルに対す る重みは 0.1 から 1.0 まで 0.1 刻みで検証した。
 原田慎太朗 1 渡辺太郎 $^{1}$ 大内啓樹 1,2 1 奈良先端科学技術大学院大学 2 理化学研究所 \{harada.shintaro.hk4, taro, hiroki.ouchi\}@is.naist.jp  