# Holographic Embeddings による CCG 構文解析

山木良輔 1 谷口忠大 ${ }^{1}$ 持橋大地 ${ }^{2}$
1 立命館大学 情報理工学部 2 統計数理研究所
\{yamaki.ryosuke,taniguchi\}@em.ci.ritsumei.ac.jp daichi@ism.ac.jp

## 概要

本研究では知識グラフをべクトル空間に埋め込む ための手法である Holographic Embeddings を CCG 構文解析に適用することで，単語分散表現から句や文 の分散表現を再帰的に構成し，文の構成要素間の依存関係を明示的にモデリングする手法を提案する。 そして，提案手法が CCG における Supertagging 精度 の向上に有効であることを示し，さらに句の分散表現を用いることで句に対するカテゴリ割当を直接的 に予測しながら句構造を探索する Span-based Parsing アルゴリズムを導入する．実験結果から，提案手法 は Supertagging 精度において既存モデルを上回る性能を示し，構文解析の精度においても，同じ C\&C パーザを用いる中で世界最高性能を達成した.

## 1 はじめに

自然言語処理において，文の背後に潜む統語構造 を解析する技術として構文解析が存在する. 構文解析は統語的な曖昧性の解消に役立つため，質問応答 や機械翻訳など，様々な自然言語処理アプリケー ションの基盤技術として活用されている. 構文解析 のうち，特に単語間に存在する階層関係・句構造を 明らかにすることに焦点をおいたものとして句構造解析，そして解析に用いられる文法理論の 1 つ として組み合わせ範疇文法 (Combinatory Categorial Grammar, CCG) [1] がある. CCG は語彙化文法の一種であり，文中の各単語に対してその単語の文法的機能を示すカテゴリを与え，それらを組み合わせ規則に従って組み合わせることで統語構造を計算す る.ここで，各カテゴリは $\mathrm{S}$ : 文， $\mathrm{N}$ : 名詞， $\mathrm{NP}$ : 名詞句などの基本カテゴリと"/"，"|" を再帰的に組み 合わせることによって構成され，単語の文法的機能 に関する情報を多く含む. CCG を用いることで単語間の長距離依存関係や並列構造など，自然言語に 存在する複雑な統語構造を簡潔に表現可能であるこ とが知られている。

図 1 埋め込み空間上でのベクトルの再帰的な合成.

CCG では句構造の探索に先立って，各単語に 尤もらしい CCG カテゴリ (Supertag)を割り当てる Supertagging という処理が行われることが一般的 であり，これによって句構造の探索空間が大幅に 削減され，探索効率が向上する [2]. ここで，既存 の Supertagging 手法には LSTM，Transformer などの ニューラルネットワークベースのエンコーダを用い ることで各単語に割り当てられるカテゴリを分類問題として予測するモデル $[3,4]$ や，単語ごとに尤も らしいカテゴリを生成するモデル $[5,6,7]$ が存在す る. 文の構成要素である単語や句の間に存在する依存関係や階層関係のモデリングの観点からみると，既存手法ではこれらの関係をニューラルネットワー クを用いて非明示的にモデリングしているものが 多い.

これに対し，本研究では Holographic Embeddings (HolE) [8] を用いて，図 1 に示すような埋め込み空間上でのベクトルの再帰的な合成を行うことで， Supertagging モデルに単語や句同士の依存関係を明示的に組み込む手法を提案する。また，ベクトルの 再帰的合成によって得られる句の分散表現を活用し た新たな構文解析アルゴリズムを導入し，依存関係 の明示的なモデリングの CCG 構文解析における有用性について検証する。

## 2 Holographic Embeddings

Nickel らは知識グラフをべクトル空間に埋め込む ための手法として Holographic Embeddings [8] を提案

した. 知識グラフは複数の実体と, それらの関係性 を表したエッジから構成されるグラフ構造のデータ であり，知識グラフをべクトル空間上でモデリング するためには, 各実体に付与された分散表現同士の 相互作用を的確に捉えられるべクトルの合成演算子 を設計することが重要となる．HolEではこの合成演算子として巡回相関を採用しており，巡回相関は ベクトル間の相互関係を捉えることに適している.

巡回相関の演算は $\star$ で表され，式 (1)で定義され る. また式 (2)のように高速フーリエ変換 Fおよび その逆変換 $\mathscr{F}^{-1}$ を用いても計算可能であることが知 られている.ここで， $\mathbf{c}_{1}, \mathbf{c}_{2}$ は合成元の $d$ 次元べク トル, $\mathbf{p}$ は合成後の $d$ 次元ベクトル，๑はアダマー ル積， $\overline{F(\cdot)}$ は複素共役をそれぞれ表す。

$
\begin{array}{r}
{[\mathbf{p}]_{k}=\left[\mathbf{c}_{1} \star \mathbf{c}_{2}\right]_{k}=\sum_{i=0}^{d-1} c_{1 i} c_{2(k+i)} \bmod d} \\
\mathbf{p}=\mathbf{c}_{1} \star \mathbf{c}_{2}=\mathscr{F}^{-1}\left(\overline{\mathscr{F}\left(\mathbf{c}_{1}\right)} \odot \mathscr{F}\left(\mathbf{c}_{2}\right)\right)
\end{array}
$

単語と単語, 単語と句, 句と句など，自然言語の文 を構成する要素間の階層関係・依存関係をモデリン グするにあたり，巡回相関には以下のような数学的 に好ましい性質が存在する。
- 非可換な演算である：巡回相関では一般に $\mathbf{a} \star \mathbf{b} \neq \mathbf{b} \star \mathbf{a}$ が成り立つ. この性質は非対称な 依存関係をモデリングするのに向いている。例 えば，"right human"と"human right"という $2 \supset の$名詞句に対して異なる分散表現を合成し，これ らを区別することが可能である。

・結合法則を満たさない：巡回相関では一般に $(\mathbf{a} \star \mathbf{b}) \star \mathbf{c} \neq \mathbf{a} \star(\mathbf{b} \star \mathbf{c})$ が成り立つ. この性質は 句構造解析が明らかにしょうとする自然言語の 階層関係をモデリングするのに重要である。例 えば，"saw a girl with a telescope"という句には 少なくとも 2 つ階層関係・内部構造が考えら れる："((saw (a girl)) (with (a telescope)))", "(saw ((a girl)(with (a telescope $)))) "$ "このような単語列 に対して，分散表現の合成演算が結合法則を満 たさない場合，複数存在しうる階層関係のそれ ぞれを，異なる分散表現として区別することが 可能となる.

以上より，我々は HolE ならびに巡回相関を CCG 構文解析において文中の単語や句の間に存在する依存関係をモデリングするための手法として採用する。

## 3 Holographic CCG

図 2 単語分散表現の再帰的合成.

## 3.1 単語分散表現の再帰的合成

ここでは，CCGの Supertagging モデルにおいて，文の構成要素間に存在する依存関係を明示的にモ デリングするための手法として，巡回相関による単語分散表現の再帰的合成を提案する. 本手法では文中における特定の句を構成している複数の単語の 分散表現を巡回相関によって再帰的に合成するこ とで, 句全体としての分散表現を計算する. 単語分散表現の再帰的合成の概略図を図 2 に示し, 図中の具体例を用いて本手法の概要を説明する。ま ず，入力文 ("My sister loves to eat") を事前学習済み のエンコーダに入力することで各単語のベクトル $\left(\mathbf{v}_{0: 1}, \mathbf{v}_{1: 2}, \cdots, \mathbf{v}_{4: 5}\right)$ を得る. ベクトルの添字 $i: j$ は,入力文中の $i+1$ 番目の単語から $j$ 番目の単語が含 まれる区間 $[i, j]$ を意味する。なお，全ての実験に おいてエンコーダには RoBERTa-large [9]を採用して おり, 各単語は 1024 次元のベクトルに変換される.次に各単語のべクトルを CCG の組み合わせ規則に 従って再帰的に合成することで，文を構成する各句の分散表現を計算する. 例えば，図中の"loves to eat"という動詞句に対応するべクトル $\mathbf{v}_{2: 5}$ は，以下 の通りにベクトルを再帰的に合成することで計算さ れる。

$
\mathbf{v}_{2: 5}=\mathbf{v}_{2: 3} \star \mathbf{v}_{3: 5}=\mathbf{v}_{2: 3} \star\left(\mathbf{v}_{3: 4} \star \mathbf{v}_{4: 5}\right)
$

同様の計算を, 文全体としてのベクトル $\mathbf{v}_{0: 5}$ が得ら れるまで繰り返し行う。

$
\begin{aligned}
\mathbf{v}_{0: 5} & =\mathbf{v}_{0: 2} \star \mathbf{v}_{2: 5} \\
& =\left(\mathbf{v}_{0: 1} \star \mathbf{v}_{1: 2}\right) \star\left(\mathbf{v}_{2: 3} \star \mathbf{v}_{3: 5}\right) \\
& =\left(\mathbf{v}_{0: 1} \star \mathbf{v}_{1: 2}\right) \star\left(\mathbf{v}_{2: 3} \star\left(\mathbf{v}_{3: 4} \star \mathbf{v}_{4: 5}\right)\right)
\end{aligned}
$

なお，巡回相関を再帰的に適用すると合成後のべク トルのノルムが急激に増大し, 数値計算上好ましく ないため, 巡回相関によって合成したべクトルに対 して，式 (3)で表されるノルム制約を加えている.

$
\mathbf{p}^{\prime}= \begin{cases}k \mathbf{p} /(\|\mathbf{p}\|+\epsilon) & \text { if }\|\mathbf{p}\| \geq k \\ \mathbf{p} & \text { otherwise }\end{cases}
$

ただし， p, $\mathbf{p}^{\prime}$ はそれぞれノルム制約の適用前と 適用後のベクトルを表しており,$k$ はノルムの 最大值である. 本研究では, 全ての実験において $k=10^{3}, \epsilon=10^{-12}$ に設定した.

## 3.2 Supertagging

入力文を構成する全ての単語と句に関して，それ らのベクトル $\mathbf{v}_{i: i+1}, \mathbf{v}_{i: j}$ を計算した後, これらを順伝播型ニューラルネットワークに入力することで,単語と句それぞれに関するカテゴリ割当の確率分布 $P_{w}(i, i+1), P_{p}(i, j)$ と, 区間 $[i, j]$ において句が成立 する確率 $P_{s}(i, j)$ をそれぞれ計算する.

$
\begin{aligned}
P_{w}(i, i+1) & =\operatorname{SM}\left(\mathbf{Q}_{w} \sigma\left(L N\left(\mathbf{U}_{w} \mathbf{v}_{i: i+1}+\mathbf{b}_{w}\right)\right)+\mathbf{c}_{w}\right) \\
P_{p}(i, j) & =\operatorname{SM}\left(\mathbf{Q}_{p} \sigma\left(L N\left(\mathbf{U}_{p} \mathbf{v}_{i: j}+\mathbf{b}_{p}\right)\right)+\mathbf{c}_{p}\right) \\
P_{s}(i, j) & =\operatorname{Sigmoid}\left(\mathbf{q}_{s}^{\top} \sigma\left(L N\left(\mathbf{U}_{s} \mathbf{v}_{i: j}+\mathbf{b}_{s}\right)\right)+\mathbf{c}_{s}\right)
\end{aligned}
$

ここで, $\mathbf{Q}_{w}, \mathbf{Q}_{p}, \mathbf{q}_{s}^{\top}, \mathbf{U}_{w}, \mathbf{U}_{p}, \mathbf{U}_{s}, \mathbf{b}_{w}, \mathbf{b}_{p}, \mathbf{b}_{s}, \mathbf{c}_{w}, \mathbf{c}_{p}, \mathbf{c}_{s}$ はモデルの学習対象となる重み行列およびべ クトルであり, $\sigma(\cdot)$ は ReLUによる非線形変換, $L N(\cdot)$ は Layer Normalization， $S M(\cdot)$ はソフトマックス関数, Sigmoid (.) はシグモイド関数をそれぞれ表す. また, 全ての順伝播型ニューラルネットワークにお いて, ReLUによる非線形変換の直後に Dropout 層 を指てている.これらの単語・句に対するカテゴ リ割当の確率分布および句の成立確率が正解に合致 するようにモデルを学習させることで，単語や句の 分散表現が相互に影響を及ぼし合い，結果として構成要素間の依存関係を明示的に与えた状況下での Supertagging モデルの学習が実現される.

モデルの学習には誤差逆伝播法を用いる. まず，単語のカテゴリ割当 $P_{w}(i, i+1)$ の予測誤差 $\mathscr{L}_{w}$ と句 のカテゴリ割当 $P_{p}(i, j)$ の予測誤差 $\mathscr{L}_{p}$ をそれぞれ 交差エントロピー誤差を基準として計算する。ま た, これらに加えて句の成立確率 $P_{s}(i, j)$ の予測誤差 $\mathscr{L}_{S}$ を, 二値交差エントロピー誤差を基準として 計算する. そして, これらの誤差の一部または全部 を逆伝播することでモデルパラメータの最適化を行 う. 例えば，3つの誤差全てを逆伝播する場合，合計誤差の計算およびモデルパラメータの更新は式 (4)，(5)でそれぞれ表される.

$
\begin{array}{r}
\mathscr{L}=\mathscr{L}_{w}+\mathscr{L}_{p}+\mathscr{L}_{s} \\
\theta \leftarrow \theta-\mu \frac{\partial \mathscr{L}}{\partial \theta}
\end{array}
$

ここで， $\mathscr{L}$ は逆伝播される合計誤差， $\theta$ はモデルパ ラメータ， $\mu$ は学習率をそれぞれ表す。

モデルの学習終了後, 開発用データ及びテスト 用データに対して Supertagging を行う際には，ま ず入力文中の各単語をエンコーダを通して分散表現に変換する. そして，これらのべクトルを順伝播型ニューラルネットワークに入力することで $P_{w}(i, i+1)$ を計算し, 各単語に対するカテゴリ割当 の予測を行う。ここで，各単語に対する割当確率が 0.1 以上となるカテゴリ全てを各単語の Supertag と して付与する。

## 3.3 Span-based Parsing

提案手法によって計算される句の分散表現は，句 に対するカテゴリ割当を直接予測しながら句構造の 探索を行う Span-based の構文解析アルゴリズム (以下 Span-based Parsing) に適用可能である. Span-based Parsing は Stern らが PCFG による句構造解析に導入乙 [10], Clark が同様の手法を CCG に適用する ことで大幅な性能向上を達成した [11]. Span-based Parsing では，単語の分散表現から文中の特定の区間・句に対応する分散表現を計算し, その分散表現 を用いて区間が句を形成する確率および，句に対 して割り当てられるカテゴリの予測を行う. 我々 は，CKYアルゴリズムに対して，提案手法における 句のカテゴリ割当の確率分布 $P_{p}(i, j)$ と句の成立確率 $P_{s}(i, j)$ の情報を組み込むことによって，新たな Span-based Parsing アルゴリズムを導入した. 本アル ゴリズムの詳細については付録 A に示す.

## 4 実験

## 4.1 データセット

モデルの学習・評価のためのデータセットには, CCG で一般的に用いられる英語 CCGbank [12] を使用した. CCGbank は Penn Treebank と同じ Wall Street Journal の記事に対して CCG のカテゴリがアノテー ションされたデータセットであり， 24 個 (00-23) の セクションで構成されている. 本実験では既存研究 のデータセット分割方法に従い，セクション 02-21
表 1 CCGbank の統計情報.

表 2 モデルの学習に関するハイパーパラメータ.

を学習用データ，セクション 00 を開発用データ，セ クション 23 をテスト用データとして用いた. デー タセットに関する統計情報を表 1 に示す.

## 4.2 実験条件

モデルの学習に関する各種ハイパーパラメータを 表 2 に示す. Optimizer には AdamW [13] を使用し，学習率は RoBERTa-large のファインチューニング部分 (fine-tune) とその他の部分 (base) で異なる值を設定した。

学習終了後, 提案モデルによって Supertagging が なされた文を事前学習済みの CCG 構文解析モデル である C\&C Parser [14] の入力とすることで構文解析 を行った. また，同様に我々が導入した Span-based Parsing による構文解析も行った.

提案手法の有効性を定量的に評価するにあたり，異なる誤差の組み合わせを用いてモデルの学習を 行った. まず単語レベルでのカテゴリ割当の誤差 $\mathscr{L}_{w}$ のみを学習に用いるモデルをベースラインモデ ルとし，これに対して句の分散表現から計算される 誤差 $\mathscr{L}_{p}, \mathscr{L}_{S}$ の一方，もしくは両方を合計した誤差 を用いるものを提案モデルとする．各モデルを異な る乱数シード値から 8 回ずつ学習させ，ベースライ ンモデルと提案モデルの各種評価指標の値を比較 した.

## 4.3 評価指標

既存研究に従い，モデルの評価指標には Supertagging の精度 (Acc) と構文解析結果から得られる単語間依存関係の情報として Labeled F-score (LF) を用 いた.表 3 開発用データにおける提案法の性能.

表 4 テストデータにおける既存手法との性能比較.

## 5 結果

ベースライン手法と提案モデルそれぞれの開発用 データにおける性能を表 3 に示す. 有意水準 $1 \%$ で 片側 $t$ 検定を行った結果, $\mathscr{L}_{w}+\mathscr{L}_{p}+\mathscr{L}_{s}$ を学習に用い た提案モデルはベースラインモデルを Supertagging 精度と C\&C Parser における Labeled F-score の両者に おいて有意に上回っていることが確認された. さら に, Span-based Parsing は C\&C Parser をさらに上回る 性能を発揮している。

次に，テスト用データにおける既存手法との比較を表 4 に示す. 提案モデルの Supertagging 精度 と C\&C Parser における Labeled F-score は全ての既存手法を上回っており，Span-based Parsing におけ る Labeled F-score も，現状の最高性能モデルである Clark [11]に迫る性能を発揮している.

## 6 おわりに

本研究では，CCG の Supertagging モデルにおいて 文の構成要素間の依存関係を明示的にモデリングす る手法を提案し，また，提案手法から計算される句 の分散表現を活用した Span-based Parsing アルゴリ ズムを導入した。提案手法はベースライン手法を上回る最高性能を発揮し，依存関係の明示的なモデリ ングが CCG 構文解析にとって有効であることを示 した.

本研究の今後の展開としては，現状の教師あり学習手法から教師なし学習手法への拡張や，ロボット のセンサー系から得られるマルチモーダル情報と言語情報の統合への応用などを予定している.

## 謝辞

本研究は, JST, ムーンショット型研究開発事業, JPMJMS2033 の支援を受けたものです.

## 参考文献

[1] Mark Steedman. The Syntactic Process, Vol. 24. MIT press Cambridge, MA, 2000.

[2] Stephen Clark and James R Curran. The Importance of Supertagging for Wide-Coverage CCG Parsing. In COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics, pp. 282-288, 2004.

[3] Ashish Vaswani, Yonatan Bisk, Kenji Sagae, and Ryan Musa. Supertagging with LSTMs. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 232-237, 2016.

[4] Yuanhe Tian, Yan Song, and Fei Xia. Supertagging Combinatory Categorial Grammar with Attentive Graph Convolutional Networks. arXiv preprint arXiv:2010.06115, 2020.

[5] Aditya Bhargava and Gerald Penn. Supertagging with CCG primitives. In Proceedings of the 5th Workshop on Representation Learning for NLP, pp. 194-204, 2020.

[6] Jakob Prange, Nathan Schneider, and Vivek Srikumar. Supertagging the Long Tail with Tree-Structured Decoding of Complex Categories. Transactions of the Association for Computational Linguistics, Vol. 9, pp. 243-260, 2021.

[7] Yufang Liu, Tao Ji, Yuanbin Wu, and Man Lan. Generating CCG Categories. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, No. 15, pp. 1344313451, May 2021.

[8] Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio. Holographic Embeddings of Knowledge Graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 30, 2016.

[9] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A Robustly Optimized BERT Pretraining Approach. arXiv preprint arXiv:1907.11692, 2019.

[10] Mitchell Stern, Jacob Andreas, and Dan Klein. A Minimal Span-Based Neural Constituency Parser. arXiv preprint arXiv:1705.03919, 2017.

[11] Stephen Clark. Something Old, Something New: Grammar-based CCG Parsing with Transformer Models. arXiv preprint arXiv:2109.10044, 2021.

[12] Julia Hockenmaier and Mark Steedman. CCGbank: a corpus of CCG derivations and dependency structures extracted from the Penn Treebank. Computational Linguistics, Vol. 33, No. 3, pp. 355-396, 2007.

[13] Ilya Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. In International Conference on Learning Representations, 2019.

[14] Stephen Clark, Darren Foong, Luana Bulat, and Wenduan Xu. The Java Version of the C\&C Parser: Version
0.95. Technical report, University of Cambridge Computer Laboratory, August, 2015.

## A Span-based Parsing アルゴリズム

本研究において我々が導入した Span-based Parsing のアルゴリズムを Algorithm 1 に示す. 簡略化のため,上記アルゴリズムでは，CCG の組み合わせ規則のうち，Binary の規則のみを前提とした場合の処理手順を示 している. 実際，CCG には Type-raising などの Unary の規則が存在するため，上記アルゴリズムに加えて， Unary の規則によって生成されるカテゴリをチャートに追加する必要がある.
 山木良輔 1 谷口忠大 ${ }^{1}$ 持橋大地 ${ }^{2}$ 1 立命館大学 情報理工学部 2 統計数理研究所 \{yamaki.ryosuke,taniguchi\}@em.ci.ritsumei.ac.jp daichi@ism.ac.jp  