Holographic Embeddings による CCG 構文解析
山木良輔 1 谷口忠大 1 持橋大地 2
1 立命館大学 情報理工学部 2 統計数理研究所{yamaki.ryosuke,taniguchi}@em.ci.ritsumei.ac.jp daichi@ism.ac.jp

概要

NPS

𝐯0:2

𝐯0:5

本研究では知識グラフをベクトル空間に埋め込む

𝐯3:5

𝐯1:2
“sister”

ための手法である Holographic Embeddings を CCG 構
文解析に適用することで，単語分散表現から句や文の分散表現を再帰的に構成し，文の構成要素間の依NP/N
𝐯0:1
“My”

存関係を明示的にモデリングする手法を提案する．

S\NP
𝐯2:5

N

𝐯4:5
“eat”
(S\NP)/(S\NP)𝐯2:3 𝐯3:4“loves” “to”

そして，提案手法が CCG における Supertagging 精度
図1の向上に有効であることを示し，さらに句の分散表
現を用いることで句に対するカテゴリ割当を直接的埋め込み空間上でのベクトルの再帰的な合成.に予測しながら句構造を探索する Span-based Parsing

CCG で は 句 構 造 の 探 索 に 先 立 っ て，各 単 語 に尤もらしい CCG カテゴリ (Supertag) を割り当てるアルゴリズムを導入する．実験結果から，提案手法

Supertagging という処理が行われることが一般的

は Supertagging 精度において既存モデルを上回る性であり，これによって句構造の探索空間が大幅に能を示し，構文解析の精度においても，同じ C&C削減され，探索効率が向上する [2]．ここで，既存パーザを用いる中で世界最高性能を達成した．の Supertagging 手法には LSTM，Transformer などの

1

はじめにニューラルネットワークベースのエンコーダを用いることで各単語に割り当てられるカテゴリを分類問

自然言語処理において，文の背後に潜む統語構造題として予測するモデル [3, 4] や，単語ごとに尤もを解析する技術として構文解析が存在する．構文解
析は統語的な曖昧性の解消に役立つため，質問応答らしいカテゴリを生成するモデル [5, 6, 7] が存在すや機械翻訳など，様々な自然言語処理アプリケー存関係や階層関係のモデリングの観点からみると，る．文の構成要素である単語や句の間に存在する依ションの基盤技術として活用されている．構文解析

既存手法ではこれらの関係をニューラルネットワーのうち，特に単語間に存在する階層関係・句構造をクを用いて非明示的にモデリングしているものが明らかにすることに焦点をおいたものとして句構造解析，そして解析に用いられる文法理論の１つ多い．
これに対し，本研究では Holographic Embeddingsとして組み合わせ範疇文法 (Combinatory Categorial(HolE) [8] を用いて，図 1 に示すような埋め込み空Grammar, CCG) [1] がある．CCG は語彙化文法の一間上でのベクトルの再帰的な合成を行うことで，種であり，文中の各単語に対してその単語の文法的Supertagging モデルに単語や句同士の依存関係を明機能を示すカテゴリを与え，それらを組み合わせ規示的に組み込む手法を提案する．また，ベクトルの則に従って組み合わせることで統語構造を計算す

再帰的合成によって得られる句の分散表現を活用しる．ここで，各カテゴリは S: 文，N: 名詞，NP：名た新たな構文解析アルゴリズムを導入し，依存関係詞句などの基本カテゴリと"/"，"\" を再帰的に組みの明示的なモデリングの CCG 構文解析における有合わせることによって構成され，単語の文法的機能に関する情報を多く含む．CCG を用いることで単用性について検証する．

語間の長距離依存関係や並列構造など，自然言語に存在する複雑な統語構造を簡潔に表現可能であることが知られている．

2

Holographic Embeddings
Nickel らは知識グラフをベクトル空間に埋め込むための手法として Holographic Embeddings [8] を提案した．知識グラフは複数の実体と，それらの関係性するためには，各実体に付与された分散表現同士の相互作用を的確に捉えられるベクトルの合成演算子を設計することが重要となる．HolE ではこの合成演算子として巡回相関を採用しており，巡回相関は⋆𝐯2:5S\NP⋆𝐯0:2𝐯3:5NP

𝐯1:2NP/N

巡回相関の演算は ★ で表され，式 (1) で定義されS\NP⋆⋆𝐯0:1

ベクトル間の相互関係を捉えることに適している．

SN

𝐯2:3

𝐯3:4

(S\NP)/(S\NP)(S\NP)/(S\NP)

𝐯4:5
S\NP

Deep Contextualized Encoder

る．また式 (2) のように高速フーリエ変換 F およびその逆変換 F−1 を用いても計算可能であることが知られている．ここで，c1 , c2 は合成元の 𝑑 次元ベク
トル，p は合成後の 𝑑 次元ベクトル，⊙ はアダマー

Inputであり，知識グラフをベクトル空間上でモデリング

Recursive Vector Compositionを表したエッジから構成されるグラフ構造のデータ

𝐯0:5“My sister loves to eat”

図2

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

ル積， F(·) は複素共役をそれぞれ表す．
[p] 𝑘 = [c1 ★ c2 ] 𝑘 =𝑑−1∑

3.1
𝑐 1𝑖 𝑐 2(𝑘+𝑖)

mod 𝑑(1)p = c1 ★ c2 = F ( F(c1 ) ⊙ F(c2 ))

(2)

𝑖=0−1

単語と単語，単語と句，句と句など，自然言語の文を構成する要素間の階層関係・依存関係をモデリン
グするにあたり，巡回相関には以下のような数学的に好ましい性質が存在する．
• 非 可 換 な 演 算 で あ る：巡 回 相 関 で は 一 般 に
a ★ b ≠ b ★ a が成り立つ．この性質は非対称な依存関係をモデリングするのに向いている．例
えば，"right human"と"human right"という２つの名詞句に対して異なる分散表現を合成し，これらを区別することが可能である．
• 結合法則を満たさない：巡回相関では一般に(a ★ b) ★ c ≠ a ★ (b ★ c) が成り立つ．この性質は単語分散表現の再帰的合成

ここでは，CCG の Supertagging モデルにおいて，文の構成要素間に存在する依存関係を明示的にモデリングするための手法として，巡回相関による単語分散表現の再帰的合成を提案する．本手法では文中における特定の句を構成している複数の単語の分散表現を巡回相関によって再帰的に合成することで，句全体としての分散表現を計算する．単語分散表現の再帰的合成の概略図を図 2 に示し，図中の具体例を用いて本手法の概要を説明する．まず，入力文 ("My sister loves to eat") を事前学習済みのエンコーダに入力することで各単語のベクトル(v0:1 , v1:2 , · · · , v4:5 ) を得る．ベクトルの添字 𝑖 : 𝑗 は，入力文中の 𝑖 + 1 番目の単語から 𝑗 番目の単語が含まれる区間 [𝑖, 𝑗] を意味する．なお，全ての実験においてエンコーダには RoBERTa-large [9] を採用して句構造解析が明らかにしようとする自然言語の階層関係をモデリングするのに重要である．例

おり，各単語は 1024 次元のベクトルに変換される．

えば，"saw a girl with a telescope"という句には従って再帰的に合成することで，文を構成する各少なくとも２つの階層関係・内部構造が考えら句の分散表現を計算する．例えば，図中の"loves toれる："((saw (a girl)) (with (a telescope)))"，"(saweat"という動詞句に対応するベクトル v2:5 は，以下((a girl) (with (a telescope))))". このような単語列に対して，分散表現の合成演算が結合法則を満次に各単語のベクトルを CCG の組み合わせ規則にの通りにベクトルを再帰的に合成することで計算される．

たさない場合，複数存在しうる階層関係のそれぞれを，異なる分散表現として区別することが可能となる．
以上より，我々は HolE ならびに巡回相関を CCG 構
文解析において文中の単語や句の間に存在する依存関係をモデリングするための手法として採用する．

3

Holographic CCG

v2:5 = v2:3 ★ v3:5 = v2:3 ★ (v3:4 ★ v4:5 )同様の計算を，文全体としてのベクトル v0:5 が得られるまで繰り返し行う．
v0:5 = v0:2 ★ v2:5
= (v0:1 ★ v1:2 ) ★ (v2:3 ★ v3:5 )= (v0:1 ★ v1:2 ) ★ (v2:3 ★ (v3:4 ★ v4:5 ))なお，巡回相関を再帰的に適用すると合成後のベク計誤差の計算およびモデルパラメータの更新は式

トルのノルムが急激に増大し，数値計算上好ましく(4)，(5) でそれぞれ表される．

ないため，巡回相関によって合成したベクトルに対L = L𝑤 + L𝑝 + L𝑠
𝜕L𝜃←𝜃−𝜇𝜕𝜃

して，式 (3) で表されるノルム制約を加えている．
p′ = 𝑘p/(∥p∥ + 𝜖)

if ∥p∥ ≥ 𝑘p

otherwise(3)

た だ し，p, p′ は そ れ ぞ れ ノ ル ム 制 約 の 適 用 前 と

(4)
(5)

ここで，L は逆伝播される合計誤差，𝜃 はモデルパ
ラメータ，𝜇 は学習率をそれぞれ表す．
モデルの学習終了後，開発用データ及びテスト

適 用 後 の ベ ク ト ル を 表 し て お り，𝑘 は ノ ル ム の用データに対して Supertagging を行う際には，ま最大値である．本研究では，全ての実験においてず入力文中の各単語をエンコーダを通して分散表

𝑘 = 103 , 𝜖 = 10−12 に設定した．

3.2

Supertagging

入力文を構成する全ての単語と句に関して，それ現に変換する．そして，これらのベクトルを順伝播型ニューラルネットワークに入力することで𝑃𝑤 (𝑖, 𝑖 + 1) を計算し，各単語に対するカテゴリ割当の予測を行う．ここで，各単語に対する割当確率がらのベクトル v𝑖:𝑖+1 , v𝑖: 𝑗 を計算した後，これらを順0.1 以上となるカテゴリ全てを各単語の Supertag と伝播型ニューラルネットワークに入力することで，して付与する．

単語と句それぞれに関するカテゴリ割当の確率分布
𝑃𝑤 (𝑖, 𝑖 + 1), 𝑃 𝑝 (𝑖, 𝑗) と，区間 [𝑖, 𝑗] において句が成立

3.3

する確率 𝑃𝑠 (𝑖, 𝑗) をそれぞれ計算する．
𝑃𝑤 (𝑖, 𝑖 + 1) = SM(Q𝑤 𝜎(LN (U𝑤 v𝑖:𝑖+1 + b𝑤 )) + c𝑤 )𝑃 𝑝 (𝑖, 𝑗) = SM(Q 𝑝 𝜎(LN (U 𝑝 v𝑖: 𝑗 + b 𝑝 )) + c 𝑝 )𝑃𝑠 (𝑖, 𝑗) = Sigmoid(qT𝑠 𝜎(LN (U𝑠 v𝑖: 𝑗 + b𝑠 )) + c𝑠 )Span-based Parsing

提案手法によって計算される句の分散表現は，句に対するカテゴリ割当を直接予測しながら句構造の探索を行う Span-based の構文解析アルゴリズム (以下 Span-based Parsing) に適用可能である．Span-based
Parsing は Stern らが PCFG による句構造解析に導こ こ で，Q𝑤 , Q 𝑝 , qT𝑠 , U𝑤 , U 𝑝 , U𝑠 , b𝑤 , b 𝑝 , b𝑠 , c𝑤 , c 𝑝 , c𝑠

入し [10]，Clark が同様の手法を CCG に適用するはモデルの学習対象となる重み行列およびベことで大幅な性能向上を達成した [11]．Span-based

クトルであり, 𝜎(·) は ReLU による非線形変換, LN (·)

Parsing では，単語の分散表現から文中の特定の区は Layer Normalization，SM(·) はソフトマックス関数，Sigmoid(·) はシグモイド関数をそれぞれ表す．

間・句に対応する分散表現を計算し，その分散表現を用いて区間が句を形成する確率および，句に対また，全ての順伝播型ニューラルネットワークにおして割り当てられるカテゴリの予測を行う．我々

いて，ReLU による非線形変換の直後に Dropout 層は，CKY アルゴリズムに対して，提案手法におけるを挿入している．これらの単語・句に対するカテゴ

句のカテゴリ割当の確率分布 𝑃 𝑝 (𝑖, 𝑗) と句の成立確

リ割当の確率分布および句の成立確率が正解に合致

率 𝑃𝑠 (𝑖, 𝑗) の情報を組み込むことによって，新たなするようにモデルを学習させることで，単語や句のSpan-based Parsing アルゴリズムを導入した．本アル

分散表現が相互に影響を及ぼし合い，結果として構ゴリズムの詳細については付録 A に示す．

成要素間の依存関係を明示的に与えた状況下でのSupertagging モデルの学習が実現される．
モデルの学習には誤差逆伝播法を用いる．まず，単語のカテゴリ割当 𝑃𝑤 (𝑖, 𝑖 + 1) の予測誤差 L𝑤 と句4

実験

4.1

データセットのカテゴリ割当 𝑃 𝑝 (𝑖, 𝑗) の予測誤差 L𝑝 をそれぞれモデルの学習・評価のためのデータセットには，交差エントロピー誤差を基準として計算する．また，これらに加えて句の成立確率 𝑃𝑠 (𝑖, 𝑗) の予測誤

CCG で一般的に用いられる英語 CCGbank [12] を使

差 L𝑠 を，二値交差エントロピー誤差を基準として用した．CCGbank は Penn Treebank と同じ Wall Street
Journal の記事に対して CCG のカテゴリがアノテー計算する．そして，これらの誤差の一部または全部を逆伝播することでモデルパラメータの最適化を行ションされたデータセットであり，24 個 (00-23) のう．例えば，3 つの誤差全てを逆伝播する場合，合のデータセット分割方法に従い，セクション 02-21セクションで構成されている．本実験では既存研究

表1

CCGbank の統計情報.

Objective
L𝑤 (baseline)
L𝑤 + L𝑝
L𝑤 + L𝑠

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

L𝑤 + L𝑝 + L𝑠

HyperparametersEpochs
Batch size
Learning rates
AdamW 𝛽 ′ 𝑠
AdamW 𝜖Weight decay
Dropout probability

Values1016
1e-4(base), 1e-5(ﬁne-tune)
0.9, 0.999
1e-6
0.01
0.2

表4

クション 23 をテスト用データとして用いた．デー
タセットに関する統計情報を表 1 に示す．

実験条件

モデルの学習に関する各種ハイパーパラメータを
表 2 に示す．Optimizer には AdamW [13] を使用し，Parser
C&C
C&C
C&C
C&C
Span

Acc
LF
96.46±0.02 91.86±0.03
96.56±0.01 91.95±0.02
96.51±0.03 91.89±0.03
96.58±0.02 92.00±0.03–92.47±0.07

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

Model
Vaswani et al. [3]Tian et al. [4]Bhargava and Penn [5]Prange et al. [6]Liu et al. [7]Clark [11] (Transformer を使用)
提案モデル (L𝑤 + L𝑝 + L𝑠 )を学習用データ，セクション 00 を開発用データ，セ4.2

開発用データにおける提案法の性能.

Train
Dev
Test
02-21
00
23
39,604 1,913
2,407
929,552 45,422 55,371

Section number
Number of sentences
Number of words
表2

表35

Parser
C&C
C&C
C&C
C&C
C&C
Span
C&C
Span

Acc
94.24
96.25
96.00
96.22
96.05
–
96.50
–

LF
88.32
90.58
90.9
90.91
89.80
92.9
92.11
92.60

結果
ベースライン手法と提案モデルそれぞれの開発用

データにおける性能を表 3 に示す．有意水準 1%で片側 𝑡 検定を行った結果，L𝑤 + L𝑝 + L𝑠 を学習に用い学習率は RoBERTa-large のファインチューニング部

た提案モデルはベースラインモデルを Supertagging
精度と C&C Parser における Labeled F-score の両者に分 (ﬁne-tune) とその他の部分 (base) で異なる値を設おいて有意に上回っていることが確認された．さら定した．に，Span-based Parsing は C&C Parser をさらに上回る

学習終了後，提案モデルによって Supertagging が性能を発揮している．

なされた文を事前学習済みの CCG 構文解析モデル

次に，テスト用データにおける既存手法との比である C&C Parser [14] の入力とすることで構文解析較を表 4 に示す．提案モデルの Supertagging 精度を行った．また，同様に我々が導入した Span-basedと C&C Parser における Labeled F-score は全ての既Parsing による構文解析も行った．

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

4.3

評価指標

る Labeled F-score も，現状の最高性能モデルであるClark [11] に迫る性能を発揮している．

6

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

既存研究に従い，モデルの評価指標には Supertag-

本研究の今後の展開としては，現状の教師あり学

ging の精度 (Acc) と構文解析結果から得られる単語習手法から教師なし学習手法への拡張や，ロボット間依存関係の情報として Labeled F-score (LF) を用のセンサー系から得られるマルチモーダル情報と言いた．

語情報の統合への応用などを予定している．

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

参考文献[1] Mark Steedman. The Syntactic Process, Vol. 24. MITpress 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 ofthe 2016 Conference of the North American Chapter ofthe Association for Computational Linguistics: HumanLanguage 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 Decodingof 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 Conferenceon Artiﬁcial Intelligence, Vol. 35, No. 15, pp. 13443–13451, May 2021.
[8] Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio. Holographic Embeddings of Knowledge Graphs. InProceedings of the AAAI Conference on Artiﬁcial 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: acorpus 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: Version0.95. Technical report, University of Cambridge Computer Laboratory, August, 2015.

Span-based Parsing アルゴリズム

AAlgorithm 1 Span-based CKY Parsing
1: v0:1 , v1:2 , · · · , v𝑛−1:𝑛 = 𝐸𝑛𝑐𝑜𝑑𝑒(𝑤 1 , 𝑤 2 , · · · , 𝑤 𝑛 )⊲ エンコーダで文中の各単語をベクトルに変換

2: for 𝑖 = 0, · · · , 𝑛 − 1 do
3:

𝑃𝑤 (𝑖, 𝑖 + 1) = 𝑆𝑀 (Q𝑤 𝜎(𝐿𝑁 (U𝑤 v𝑖:𝑖+1 + b𝑤 )) + c𝑤 )4:for 𝐶 ∈ {𝑋 |𝑃𝑤 (𝑖, 𝑖 + 1) [𝑋] > 𝑡 𝑤 = 0.1} do

5:𝑝𝑟𝑜𝑏[𝑖, 𝑖 + 1, 𝐶] = log 𝑃𝑤 (𝑖, 𝑖 + 1) [𝐶]6:𝑣𝑒𝑐𝑡𝑜𝑟 [𝑖, 𝑖 + 1, 𝐶] = v𝑖:𝑖+1⊲ 単語に対するカテゴリ割当確率を計算⊲ 𝑃∗ (𝑖, 𝑗) [𝑋] は区間 [𝑖, 𝑗] に対するカテゴリ 𝑋 の割当確率

7: for 𝑙 = 2, · · · , 𝑛 do
8:
9:
10:
11:

for 𝑖 = 0, · · · , 𝑛 − 𝑙 do
𝑗 =𝑖+𝑙for 𝑘 = 𝑖 + 1, · · · , 𝑗 − 1 do
for 𝐶1 ∈ {𝑋 | 𝑝𝑟𝑜𝑏[𝑖, 𝑘, 𝑋] > 0} do

12:v𝑖:𝑘 = 𝑣𝑒𝑐𝑡𝑜𝑟 [𝑖, 𝑘, 𝐶1 ]13:

for 𝐶2 ∈ {𝑋 | 𝑝𝑟𝑜𝑏[𝑘, 𝑗, 𝑋] > 0} do

14:v 𝑘: 𝑗 = 𝑣𝑒𝑐𝑡𝑜𝑟 [𝑘, 𝑗, 𝐶2 ]15:

v𝑖: 𝑗 = v𝑖:𝑘 ★ v 𝑘: 𝑗

16:

𝑃𝑠 (𝑖, 𝑗) = 𝑆𝑖𝑔𝑚𝑜𝑖𝑑 (q𝑠 𝜎(𝐿𝑁 (U𝑠 v𝑖: 𝑗 + b𝑠 )) + c𝑠 )17:

if 𝑃𝑠 (𝑖, 𝑗) > 𝑡 𝑠 = 0.01 then

⊲ 巡回相関でベクトルを合成

18:

𝑃 𝑝 (𝑖, 𝑗) = 𝑆𝑀 (Q 𝑝 𝜎(𝐿𝑁 (U 𝑝 v𝑖: 𝑗 + b 𝑝 )) + c 𝑝 )19:

for 𝐶 ∈ {𝑋 |𝐶1 𝐶2 → 𝑋 ∈ 𝑅} do

20:
21:
22:
23:

⊲ 句が成立する確率を計算

T⊲ 句に対するカテゴリ割当確率を計算⊲ 𝑅 は組み合わせ規則

if 𝑃 𝑝 (𝑖, 𝑗) [𝐶] > 𝑡 𝑝 = 0.01 then𝑝 = log 𝑃𝑠 (𝑖, 𝑗) + log 𝑃 𝑝 (𝑖, 𝑗) [𝐶] + 𝑝𝑟𝑜𝑏[𝑖, 𝑘, 𝐶1 ] + 𝑝𝑟𝑜𝑏[𝑘, 𝑗, 𝐶2 ]if 𝑝 > 𝑝𝑟𝑜𝑏[𝑖, 𝑗, 𝐶] then𝑝𝑟𝑜𝑏[𝑖, 𝑗, 𝐶] = 𝑝

24:𝑏𝑎𝑐𝑘 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 [𝑖, 𝑗, 𝐶] = (𝑘, 𝐶1 , 𝐶2 )25:

𝑣𝑒𝑐𝑡𝑜𝑟 [𝑖, 𝑗, 𝐶] = v𝑖: 𝑗

本研究において我々が導入した Span-based Parsing のアルゴリズムを Algorithm 1 に示す．簡略化のため，上記アルゴリズムでは，CCG の組み合わせ規則のうち，Binary の規則のみを前提とした場合の処理手順を示している．実際，CCG には Type-raising などの Unary の規則が存在するため，上記アルゴリズムに加えて，Unary の規則によって生成されるカテゴリをチャートに追加する必要がある．