組合せ範疇文法の漸進的構文解析

随分と昔に、CCG(combinatory categorial grammar/組み合わせ範疇文法)のパーサを作った。
https://m-a-o.hatenablog.com/entry/20160614/p3

この時の実装は、CYK法に近いもので、ボトムアップ構文解析である。

ところで、人間が自然言語を処理する時は、単語を先頭から順に処理していってると思われる。普通のCCGに於いて、例えば、I saw a cat.という文は標準的には、以下のような導出木によってparseされる。

I    saw          a          cat
--  ---------   ------      -----
NP  (S\NP)/NP    NP/N         N
                ----------------- (/-application)
                       NP
    ----------------------------- (/-application)
               S\NP
--------------------------------- (\-application)
               S

この場合、文章が最後まで提示されないと構文解析を開始できないが、英語を知ってる人は、I saw a ...まで提示された時、次に目的語が来ることを期待していて、最後まで文が提示されなくても、ある程度の構文解析を行い、かつ、文章が完成していないことも理解している。

CCGには、単純な左適用、右適用以外にも、色々な導出規則があって、特にtype raisingという規則では、最終的に得たい統語範疇がSで、途中までの統語範疇がXの場合、残りの部分の統語範疇はS\Xだろうから、統語範疇Xを、S\Xに右適用して統語範疇Sが得られるS/(S\X)に置き換えることが許される。元々は、type raisingがあると、単語の統語範疇を追加することなく、導出木を作れるケースがあるという理由で、導入された規則だと思うけど、続きの文章に対する予測を行うのに類似した作用を定式化していると考えることもできる。

type raisingを使うと、上の文章の場合、以下のように、前から順に導出木を作っていくこともできる。

   I        saw          a       cat
-------   ---------   ------    -----
  NP      (S\NP)/NP    NP/N       N
-------- (type raising)
S/(S\NP)  
-------------------- (composition)
        S/NP
----------------------------- (composition)
            S/N
--------------------------------------- (/-application)
                   S

CCGに於いて、この2つの導出木は、等価な構文解析結果を与える。

つまり、統語範疇X/YとX\Yを持つ単語は、型Y->Xを持つ関数と解釈され、上の2つの導出木は型Sを持つ値を作っている。コンビネータBをB f g = λx.f (g x)で定義すると、これは関数の合成操作で、単語wの"意味"が[ [w] ]で与えられるとすると、後者の導出木の値は以下のように計算できる。

(B (B (λf.f [[I]]) (λx.[[saw]] x)) [[a]]) [[cat]] 
=>  (B (λf.f [[I]]) (λx.[[saw]] x)) ([[a]] [[cat]])
=> (λf.f [[I]]) ([[saw]] ([[a]] [[cat]]))
=> [[saw]] ([[a]] [[cat]]) [[I]]

これは最初の導出木から得られる値と等しい。この柔軟性のために、CCGには同値な導出が無数に存在することになり、枝刈りしないと大変なことになる。追加していいCCGの導出規則は、上のような単純型付ラムダ計算の体系を破綻させないことが必要条件になるが、十分条件は良くわからない(多分、言語ごとに使っていいコンビネータのセットが多少違う?)ので、不足がないという保証はない。

細かく言えば、統語範疇も、もう少し細分化しないと、現在の標準的なCCGでは、"him are I."みたいな文章も通ってしまうので、非文を弾くということには、比較的甘い傾向がある。

前から順に処理していけるかは、実用的観点からも気になる話。機械学習を使ったNLPでも、文章は、単語列を先頭から順に処理していくことで結果を得るのが普通だし、
Unsupervised POS Induction with Word Embeddings
https://arxiv.org/abs/1503.06760
という論文では、窓幅1でword2vecで学習したベクトルからHMMを使って、品詞の教師なし学習をやって、従来法より良い結果が得られると書いている。

窓幅1なので、semanticな情報はほぼ皆無で、統語的な情報のみを含んでるだろうと感覚的には思うが、一方で、そもそも、原理的に窓幅1のword embeddingでは捉えきれない統語情報がないのか疑問に思う。もし、完全にincrementalなparserが作れるのならば、(word2vecで出来るかどうかはともかく)原理的には窓幅1で統語情報を全て得られる可能性はある。

そういうわけで、incremental parserが可能なのかというのは、興味ある問題である。

Incremental combinatory categorial grammar and its derivations
https://dl.acm.org/doi/10.5555/1964799.1964809
では、incremental combinatory categorial grammar(ICCG)と呼んでる。が、結果は完璧でない。

Incremental Derivations in CCG
https://www.aclweb.org/anthology/W12-4623.pdf

は、もう少し詳しく議論している。

3つの連続する統語範疇から一つの統語範疇Xが導出される場合、
(X/Y)/Z Z Y
Z (X/Y)\Z Y
X/Y Y/Z Z
X/Y Z Y\Z => X/Y Y/(Y\Z) Y\Z
Y/Z Z X\Y
Z Y\Z X\Y
Y (X\Y)/Z Z => X/(X\Y) (X\Y)/Z Z
Y Z (X\Y)\Z => X/(X\Y) (X\Y)/((X\Y)\Z) (X\Y)\Z
Y X/Z Z\Y => ???
などのパターンがある。いくつかは自明にincremental parseが可能で、3つはtype raisingを必要とするが、incrementalにparseできる。最後のパターンをincrementalにparseするために、論文では、Geach ruleという新たな規則を追加している(Peter Geachという人がいたらしい)。combinator birdでは、bluebirdに相当し、
A/B : f => (A/T)/(B/T) : λg.λt.f(g t)
のように意味づけすることができる。論文には書かれてないが、
A\B : f => (A\T)\(B\T) : λg.λt.f(g t)
をBackward Geach ruleと(私が勝手に)呼ぶことにする。

1つ目の統語範疇にtype raisingを使い、2つ目にGeach's ruleを使うと、
Y X/Z Z\Y => X/(X\Y) (X\Y)/(Z\Y) (Z\Y)
のような形になって、incrementalにparseできる。

後者の論文では、incrementalにparseするのが難しい例として、以下のようなthat節を挙げている。最も標準的なCCG導出木は以下の形だろう。

the woman        that       every       man          saw        laughed
---------   -------------  -------     ------     ----------    --------
   NP       (NP\NP)/(S/NP)   NP/N         N        (S\NP)/NP      S\NP
                            ------------------
                                   NP
                            ------------------
                                S/(S\NP)
                            ---------------------------------
                                          S/NP
             -------------------------------------------------
                              NP\NP
--------------------------------------------------------------
                            NP
----------------------------------------------------------------------------
                                        S

thatは、目的語を残した文(今の場合、every man sawで、統語範疇はS/NP)を受け取って、名詞句を後ろから修飾し新たな名詞句を作り出す(NP\NPの部分)ので、(NP\NP)/(S/NP)のような統語範疇は、文法解釈的に自然である。

一応、Backward Geach ruleと前者の論文では導入されているargument swap(関数の引数を置換する操作で、(S\NP)/NPを(S/NP)\NPに置き換える)を使い、更にtype raisingを一つの単語で2回やるという反則っぽいことをすると、incrementalにparseできなくはない。

the woman        that              every                   man                                 saw        
----------  -------------  ----------------      ---------------------------                 ---------- 
   NP       (NP\NP)/(S/NP)        NP/N                       N                                (S\NP)/NP 
----------
NP/(NP\NP)
-------------------------
          NP/(S/NP) 
                          ---------------------                 
                     (S/NP)/((S/NP)\(NP/N))
----------------------------------------------   ------------------------------ (type raising)
            NP/((S/NP)\(NP/N))                              NP\(NP/N)
                                                ----------------------------------------------- (type raising)
                                                ((S/NP)\(NP/N))/(((S/NP)\(NP/N))\(NP\(NP/N)))
---------------------------------------------------------------------------------------------- --------------  (argument swap)
                        NP/(((S/NP)\(NP/N))\(NP\(NP/N)))                                          (S/NP)\NP
                                                                                                ------------- (Bwd Geach rule)
                                                                                               ((S/NP)\(NP\N))\(NP\(NP/N))
------------------------------------------------------------------------------------------------------------------------
                                                      NP

こういう無理矢理っぽいことをしても、semanticsの一貫性を保証できるのがCCGの良い点ではあるが、複雑すぎるので、人間の脳が、本当に、こんなことをしてるのか(出来るのか)という点は、疑問である(私は、この導出木を見つけるのに2時間くらい考えた)

実装上は、何回までtype raisingを許すのかという問題が出てくる。全ての単語とparse途中で現れる中間統語範疇が複数回type raisingする可能性があると考えだすと、場合によっては組み合わせが膨大になって大変なことになりそう。

しかし、incrementalにparseする場合、一見、文章として完成していても、続きがあるかもしれないという問題があるので、この困難は本質的には回避不能という気もする。

例えば、He ranという単語列は、2単語で一応完結しており、構文的には、これで一つの文でありえるが、He ran quickly.という文章では、"He ran"の部分の統語範疇は、S/( (S\NP)\(S\NP) )になるべきで、He ran quickly and stopped suddenly.という文章では、"He ran"の部分には、また別の統語範疇を付与する必要がある。

incrementalにparseする場合、"He ran"という2単語が提示された段階で、どこまで文章が続くかは全く未知であって、”He ran"に付与する統語範疇として想定しなければならないパターンは、おそらく無限個ある。そうであれば、完全にincrementalなCCG parserは、一単語目で足止めされることになって、計算できない。

incremental parserが不可能であっても、任意の有限な長さの文に対して、incrementalな導出木が必ず存在するという可能性はある。現実的には、人間が話したり書いたりする文章の長さは、限りがあるし、無限のパターンを記憶することもできないので、人間の脳は、何らかのヒューリスティックで個数を制限して、incrementalな導出木を計算してるのかもしれない。

type raisingは無限のパターンを作り出すための仕組みでもあるし、また、実装上は、多相型のように扱うのがよいと思われ、いつ終わるか分からない文章で統語範疇をfixするのを先送りする役割を果たす。と考えられる。

 He                ran                     quickly
----------     -----------------        -------------
 NP                S\NP                  (S\NP)\(S\NP)
------------   -----------------
∀X.X/(X\NP)    ∀Y.Y/(Y\(S\NP))
-------------------------------- (Y:=X\NP)
     ∀X.X/((X\NP)\(S\NP))
------------------------------------------------------- (X:=S)
                          S


ついでに、1997年にLambekが提案したpregroup grammarというものを読んだ。この文法では、argument swapは自動的に入っている。
Type Grammar Revisited
https://link.springer.com/chapter/10.1007/3-540-48975-4_1

pregroup grammar
https://ncatlab.org/nlab/show/pregroup+grammar

pregroupは、半順序モノイドで、ある性質を持つleft adjointとright adjointを持つ代数構造。順序構造については、 a \leq bの代わりに、簡約的なニュアンスで、 a \to bと書かれることがある。left adjointとright adjointは a^{l} a \to 1 , 1 \to a a^{l}及びa a^{r} \to 1 , 1 \to a^{r} aを満たす。

逆元のようではあるが、a^{l} a = 1というわけではない。実際、a^{l} a = 1だと左逆元そのものであるが、初歩的な代数学の教科書の最初に書いてある通り、左逆元と右逆元は一致してしまうので条件を緩めている。群でないpregroupが存在することは、Lambekの論文やncatlabのページに例が載っている(どっちも同じ例)。明らかに、群でないpregroupは、積について非可換である。

left adjointとright adjointは、通常の逆元が持つのと類似の性質を多く持ち、
1^{l} = 1^{r} = 1
(ab)^{l} = b^{l} a^{l}
(ab)^{r} = b^{r} a^{r}
が成り立つ。また、a^{ll} = (a^{l})^{l}などと表記すると、
 a^{ll} a^{l} \to 1 \to a a^{l}
なので、a^{ll}aが等しいとは限らない。a^{rr}も同様。a^{lr}=a^{rl}=aは成立する。

pregroupはleft dualとright dualが一致しないタイプのrigid category(autonomous category)の例を与えていて、そのような圏の別の例は、Joyal and Streetの論文
AN INTRODUCTION TO TANNAKA DUALITY AND QUANTUM GROUPS
http://maths.mq.edu.au/~street/CT90Como.pdf
の§9で見ることができる。大抵の数学の文献では、left dualとright dualが同型になるような圏しか扱われない(と思う)。


pregroup grammarは、combinatoryでない範疇文法とセットで議論されることが普通なので、\-application ruleが
Y X\Y => X
の形でなく、
Y Y\X => X
と書かれている。紛らわしい上に、面倒だけど、多分、Steedmanが悪い。ここでは、組み合わせ範疇文法の話を書いてきたので、\は、組み合わせ範疇文法の記法に合わせる。

で、A/Bは、\mathrm{A} \cdot \mathrm{B}^{l}に置き換えて、A\Bは、\mathrm{B}^{r} \cdot \mathrm{A}に置き換える。後は、普通の群やモノイドのように思って計算する。合流性は成立してないので、a^{l}aa^{r}a(a^{l}a)(a^{r}a) \to a^{r}aであると同時にa^{l}(aa^{r})a \to a^{l}a \to 1でもある。このへんがparseをめんどくさくするが、CFGなどと同様、O(N^3)でparseするアルゴリズムが知られている。

例えば、"I saw a cat"は

\mathrm{NP} \cdot (\mathrm{NP}^{r} \cdot \mathrm{S} \cdot \mathrm{NP}^{l}) \cdot (\mathrm{NP} \cdot \mathrm{N}^{l}) \cdot (\mathrm{N}) \to \mathrm{S}

と計算される。他動詞"saw"の統語範疇(S\NP)/NPが\mathrm{NP}^{r} \cdot \mathrm{S} \cdot \mathrm{NP}^{l}にマップされて、argument swapを行った統語範疇(S/NP)\NPの場合と一緒になる。"I saw a ..."という途中までの文だと

\mathrm{NP} \cdot (\mathrm{NP}^{r} \cdot \mathrm{S} \cdot \mathrm{NP}^{l}) \cdot (\mathrm{NP} \cdot \mathrm{N}^{l}) \to \mathrm{S} \cdot \mathrm{N}^{l}

となる。

the woman that every man sawという句は、(式が長くなるので)"the book"と"every man"の統語範疇をNPとして、

\mathrm{NP} \cdot (\mathrm{NP}^{r} \cdot \mathrm{NP} \cdot \mathrm{NP}^{ll} \cdot \mathrm{S}^{l}) \cdot \mathrm{NP} \cdot (\mathrm{NP}^{r} \cdot \mathrm{S} \cdot \mathrm{NP}^{l}) \to \mathrm{NP}

となる。

type raisingも整合的になる。例えば、A => T/(T\A)の場合、\mathrm{T} \cdot (\mathrm{T}^{l} \cdot \mathrm{A}^{rl}) = \mathrm{T} \cdot \mathrm{T}^{l} \cdot \mathrm{A}となるが、A \to \mathrm{T} \cdot \mathrm{T}^{l} \cdot \mathrm{A}は、正しいので、問題ない。

Geach ruleとBackward Geach ruleもpregroup grammarで解釈できる。A/B => (A/T)/(B/T)は \mathrm{A}\mathrm{B}^{l} \to \mathrm{A} (\mathrm{T}^{l} \mathrm{T}^{ll}) \mathrm{B}^{l} = (\mathrm{A}\mathrm{T}^{l})(\mathrm{B}\mathrm{T}^{l})^{l}から従う。Backward Geach rule A\B => (A\T)\(B\T)も\mathrm{B}^{r}\mathrm{A} \to \mathrm{B}^{r} \mathrm{T}^{rr} \mathrm{T}^{r} \mathrm{A}から従う。

組み合わせ範疇文法のコンビネータで、pregroup grammarが処理できなさそうのもある。backward crossing composition
Y/Z:g X\Y:f => X/Z:λz.f(g z)
は、英語では必要なことになってるけど、\mathrm{Y}\mathrm{Z}^{l}\mathrm{Y}^{r}\mathrm{X}\mathrm{X}\mathrm{Z}^{l}で、\mathrm{X}\mathrm{Z}^{l}の順序が入れ替わっているので、pregroup grammarでは困りそう。英語では、backward crossing compositionは、heavy NP shiftを説明するために、よく使われる。

ただ、英語でもbackward crossing compositionの無条件な適用は、非文も生み出すと考えられているので、CCGを拡張してslash typeを導入するなどの方法(Modalized CCGとか呼ばれる)で解決を図ろうとする場合もある。

言語によっては、他にも、pregroup grammarで処理できないコンビネータが必要かもしれない。


あと、incrementalにparseすることを考えると、組み合わせ範疇文法もpregroup grammarでも、言語固有の知識を追加で積極的に使わないと効率が悪そうではある。例えば、英語で、名詞句NPが連なることはない(I, Geras, am a fixed point in time.みたくカンマ区切りで列挙するのは別)けど、組み合わせ範疇文法やpregroup grammarの枠組みだけでは、それを捨てられない。

例えば、He she theyという単語列は、英語では出現しないだろうが、pregroup grammarだったら、続く単語列の統語範疇がX \cdot \mathrm{NP}^{l} \cdot \mathrm{NP}^{l} \cdot \mathrm{NP}^{l} \cdot \mathrm{S}で、X \to 1だったら、最終的にSに簡約される。そんなことがないかどうかは、pregroup grammarは教えてくれない。組み合わせ範疇文法だと、以下のようなことができる

  He          she            they
-------   -------------  ---------------
  NP           NP             NP
-------   -------------  ---------------
S/(S\NP)  ∀X.X/(X\NP)    ∀Y.Y/(Y\NP)
------------------------
    S/((S\NP)\NP)
-----------------------------------------
         S/(((S\NP)\NP)\NP)