Combinatory Categorial Grammar
というものを最近調べた。前身として、Categorial Grammar(範疇文法)というものがあったらしい。
歴史的には、範疇文法は文脈自由文法(CFG)より古いっぽいが、範疇文法は、文脈自由文法と同等の計算能力しかないことが知られているらしい。基本的には、
S -> NP VP
のような生成規則があったら、VP=S\NPないしNP=S/VPとして、前者であれば、VPは、"左に型NPの引数を受け取って、型Sの値を返す関数"と見なし、後者なら、NPは、"右に型VPの引数を受け取って型Sの値を返す関数"と見なす。一般的なプログラム言語で、普通の中置きされた(int型同士の)"+"演算子であれば、(int\int)/intのような型になる感じだと理解すると、分かりやすい気がする。
CFGと比較した場合
・CFGと比べるとラムダ計算で意味付けする方法が明確なので、意味論に繋げやすい
・各単語ごとに、"型"が付いて、統語規則の方は変更しない語彙化文法というものになっている(実用上のメリットとして、CFGで文法ルールを作って、生成規則を増やす場合、影響範囲を予測するのが難しいけど、語彙化文法なら、追加した語彙が出てこない文には影響しない)
というメリットがある。CFGから範疇文法への変換は、一回標準形にする必要があり、例えば、二重他動詞DTVは、CFGでは生成規則VP->DTV NP NPを持つと思われるけど、直接対応する範疇文法は作れない(範疇文法なら、DTV=(VP/NP)/NPという形にするのが普通)。
NPやVPやSは、型とは呼ばずに、(統語)範疇と呼ぶのが普通ぽい。時制や人称のような情報は、統語素性として扱って、単数形名詞をN[sg]、複数形名詞をN[pl]などと書いたりする(場合もある)。この場合、実用上は、N[sg]とN[pl]は、特に何の関係もない、別の素性という扱いになる。現実的に、文法的に許される文章を過不足なく記述しようと思うと、かなり多くの統語素性は必要になると思う(時制や人称がないと、"He meet ..."とか"him looks ..."みたいな文章も合法となったりする)。
組み合わせ範疇文法(CCG)。範疇文法には関数適用しかないけど、ラムダ計算で意味付けされることを考えると、関数合成を許すのは自然に思える。関数適用が左と右の2つあるので、合成のバリエーションも多い。関数合成があると、
He conjectured and might prove completeness.
のような文章で、
conjectured |- (S\NP)
might |- (S\NP)/(S\NP)
prove |- (S\NP)
から、
might prove |- S\NP
とできて、conjecturedとmight provedが同じ型になって対をなすようにできる。andは、forall x,(x\x)/xという多相関数みたいな型として実現されるとする。他に、
(X/Y)/Z Y/Z => X/Z
(X/Y)\Z (Y\Z) => X\Z
Y\Z (X\Y)\Z => X\Z
Y/Z (X\Y)/Z => X/Z
のような代入規則も、CCGでは使われる
ここまでは、いわば"二項演算"であるけども、CCGには、もう一つ、type raisingというのもあって、これは、一項演算みたいなもの。インフォーマルには、S->NP VPをCG/CCGに変換するとき、VP=S\NPとしても、NP=S/VPとしてもよいという任意性があり(意味論の自然さから、普通は、NPを基本範疇にして、VP=S\NPとする)、VP=S\NPと、NP=S/VPを組み合わせると、NP=S/(S\NP)と"解ける"。一般に、XとY=T\Xがあれば、X=T/Yでもあり、X=T/(T\X)と解ける。これがtype raisingの由来と思う
#左右の区別を忘れると、Type raisingは、イメージ的には、型Aから、多相型forall X,(A->X)->Xを作り出すような操作と見なせる。一方、多相型ラムダ計算では、最小不動点のChurch Encodingとして、forall X,(F(X) -> X) -> Xというのがあって、その特殊な場合と思える。
#日本語(トルコ語とかもそうらしい)などは、語順の自由度が英語より高い(と一般的に言われる)が、それらを系統的に扱うために、scramblingというものも追加する場合があるらしい
type raisingの恩恵として、関係代名詞の扱いが自然になるという説明が、よく書いてある。例えば、the company which Microsoft bought
だと、(boughtは他動詞なので)
Microsoft |- NP
bought |- (S\NP)/NP
だけど、type raisingによって
Microsoft |- S/(S\NP)
となって、関数合成によって
Microsoft bought |- S/NP
となって、
which |- (N\N)/(S\NP)
が適用できる形になる
意味が扱えるという話。例として、"0"と"1"と"+"だけで構成される算術式を、範疇文法(<=>文脈自由文法)で考える(個人的な感覚としては、CCGは、数式やプログラミング言語のような形式言語を扱うには、自由度が高すぎて、制御しづらいという気がする)。この場合、"0","1","+"の範疇として
"0" |- S : 0
"0" |- S\S : (\x -> 10*x)
"1" |- S : 1
"1" |- S\S : (\x -> 10*x + 1)
"+" |- (S\S)/S : (\x y -> x+y)
があるとする("001"のような表記も許容する)。':'の後ろにあるのが、意味。範疇文法なので、右適用と左適用だけ考えればよく、右適用を>で、左適用を<で表すと、"110+1"の導出木は、例えば
(< (< (< "1"|S "1"|(S\S)) "0"|(S\S)) (> "+"|( (S\S)/S ) "1"|S))
みたいになる。対応する意味を
(< (< (< 1 (\x -> 10*x + 1)) (\x -> 10*x)) (> (\x y -> x+y) 1))
のように置き換えて、簡約化していくと
(< (< (< 1 (\x -> 10*x + 1)) (\x -> 10*x)) (> (\x y -> x+y) 1))
=> (< (< 11 (\x -> 10*x)) (> (\x y -> x+y) 1))
=> (< 110 (> (\x y -> x+y) 1))
=> (< 110 (\y -> 1+y))
=> 111
という風に計算できる。というわけで、"110+1"の意味は、今の場合、111となる。
どういう意味を付けるかは、CGやCCGとは独立の話で、JSONパーサーなんかだと、対応するJSONオブジェクトが意味ということになるし、英語の意味を表すのに、日本語を使ってもいい。自然言語の形式意味論としては、discourse representation theory(DRT)というものが比較的よく使われているっぽい(あまり調べていない)。一階述語論理との違いがよく分からないけど、東ロボくんの数学部分は、問題を計算機代数システムで処理できる形に変換するのに、CCG+DRTを使っているらしい(と書いてある)
cf.深い言語理解と数式処理の接合による入試数学問題解答システム
https://kaigi.org/jsai/webprogram/2013/pdf/622.pdf
CCGはCFGより計算能力が高いことが知られている(文脈依存文法よりは弱いらしい)けど、CCGまでいくと、主に関数合成を許しているせいで、導出木は、一般に非常に沢山ある。が、意味の方で見ると同じになる擬似的曖昧性(spurious ambiguity。導出木は違うけど、意味は同じと見なせる)と、そもそも、異なる意味に対応する、本質的な曖昧性が存在する
(本質的曖昧性の例1)有名な例
I saw a girl with a telescope
で、withが動詞句"saw a girl"にかかるか、名詞句"a girl"にかかるか、で、withの範疇は、( (S\NP)\(S\NP) )/NPと(NP\NP)/NPになって、意味的に異なる
(本質的曖昧性の例2)
The fish twisted and turned on the bent hook.
で、"on"の範疇が、( (S\NP)\(S\NP) )/NPであるとすると、"on the bent hook"は、turnedのみにかかると見ることもできるし、"twisted and turned"にかかると見ることもできる(あくまで、文法的には)。というわけで、全ての範疇が決まっても、、意味の異なる導出木が複数存在する場合がある
慣用表現の扱い。特に体系的な扱いは存在しない。英語には、色々な慣用表現がある。特に、句動詞(phrasal verb)というものが多い。look at ...みたいなの。こういう時には、at ...がlookにかかるというより、look atが他動詞であるかのように見たい。こういう時は、"at ..."の範疇をPP(前置詞句)とする。atの範疇はPP/NPとなる。lookの範疇は(S\NP)/PPとなる。look atの範疇は合成によって(S\NP)/NPとなるので、目的は果たせられる。ただ、どこからが句動詞とするのか、明確な線引きはない気がする。take ... apartみたいなパターンを慣用表現として捉えたければ、apartの範疇を何か新しいXPとして、takeの範疇を(VP/XP)/NPとすれば、一応、そういう扱いもできる
別の慣用表現の例。"It is easy to show that."とか"There is ...."みたいな文で、ItやThereに、もはや意味はない。これらは、CCGBankなどでは、それぞれNP[expl]とか、NP[thr]という範疇を持ち、isは((S\NP[expl])/VP[to])/VP[adj]とか(S\NP[thr])/NPみたいな特殊な範疇となる。
実際の構文解析は、例えばCYK法で行うことができる。英語のCCG parserを手っ取り早く試すには、
EasyCCG
http://homepages.inf.ed.ac.uk/s1049478/easyccg.html
とかがいい気がする(多分、これはProbabilistic CCG parserで、CCGBankで学習してるのだと思う。命令文は、実質対応できてないっぽい？)(CCGBankはPenn Treebankから機械的に生成されたものだと思う)(何故か、自然言語parser業界では、Javaが使われることが多く、これもJavaで書かれている)。python nltkにもCCG parserはあるけど、lexiconを自分で定義する必要がある。
日本語のCCG parserは、自分で作るしかない気がする
