DisCoCat

{{Short description|Mathematical framework for natural language processing}}

DisCoCat (Categorical Compositional Distributional) is a mathematical framework for natural language processing which uses category theory to unify distributional semantics with the principle of compositionality. The grammatical derivations in a categorial grammar (usually a pregroup grammar) are interpreted as linear maps acting on the tensor product of word vectors to produce the meaning of a sentence or a piece of text. String diagrams are used to visualise information flow and reason about natural language semantics.

History

The framework was first introduced by Bob Coecke, Mehrnoosh Sadrzadeh, and Stephen Clark{{cite arXiv |last1=Coecke |first1=Bob |last2=Sadrzadeh |first2=Mehrnoosh |last3=Clark |first3=Stephen |date=2010-03-23 |title=Mathematical Foundations for a Compositional Distributional Model of Meaning |class=cs.CL |eprint=1003.4394 }} as an application of categorical quantum mechanics to natural language processing. It started with the observation that pregroup grammars and quantum processes shared a common mathematical structure: they both form a rigid category (also known as a non-symmetric compact closed category). As such, they both benefit from a graphical calculus, which allows a purely diagrammatic reasoning. Although the analogy with quantum mechanics was kept informal at first, it eventually led to the development of quantum natural language processing.{{Cite journal |last1=Zeng |first1=William |last2=Coecke |first2=Bob |date=2016-08-02 |title=Quantum Algorithms for Compositional Natural Language Processing |arxiv=1608.01406 |journal=Electronic Proceedings in Theoretical Computer Science |volume=221 |pages=67–75 |doi=10.4204/EPTCS.221.8 |s2cid=14897915 |issn=2075-2180}}{{cite arXiv |last1=Coecke |first1=Bob |last2=de Felice |first2=Giovanni |last3=Meichanetzidis |first3=Konstantinos |last4=Toumi |first4=Alexis |date=2020-12-07 |title=Foundations for Near-Term Quantum Natural Language Processing |class=quant-ph |eprint=2012.03755 }}{{Cite journal |last=Rai |first=Anshuman |date=2022-01-31 |title=A Review Article on Quantum Natural Language Processing |url=http://dx.doi.org/10.22214/ijraset.2022.40103 |journal=International Journal for Research in Applied Science and Engineering Technology |volume=10 |issue=1 |pages=1588–1594 |doi=10.22214/ijraset.2022.40103 |issn=2321-9653|doi-access=free }}

Definition

There are multiple definitions of DisCoCat in the literature, depending on the choice made for the compositional aspect of the model. The common denominator between all the existent versions, however, always involves a categorical definition of DisCoCat as a structure-preserving functor from a category of grammar to a category of semantics, which usually encodes the distributional hypothesis.

The original paper used the categorical product of FinVect with a pregroup seen as a posetal category. This approach has some shortcomings: all parallel arrows of a posetal category are equal, which means that pregroups cannot distinguish between different grammatical derivations for the same syntactically ambiguous sentence.{{Cite journal |last=Preller |first=Anne |date=2014-12-27 |title=From Logical to Distributional Models |arxiv=1412.8527 |journal=Electronic Proceedings in Theoretical Computer Science |volume=171 |pages=113–131 |doi=10.4204/EPTCS.171.11 |s2cid=18631267 |issn=2075-2180}} A more intuitive manner of saying the same is that one works with diagrams rather than with partial orders when describing grammar.

This problem is overcome when one considers the free rigid category $\mathbf{G}$ generated by the pregroup grammar.{{Cite journal |last1=Preller |first1=Anne |last2=Lambek |first2=Joachim |date=2007-01-18 |title=Free Compact 2-Categories |url=https://hal-lirmm.ccsd.cnrs.fr/lirmm-00137681 |journal=Mathematical Structures in Computer Science |language=en |volume=17 |issue=doi: 10.1017/S0960129506005901 |pages=309 |doi=10.1017/S0960129506005901|s2cid=10763735 }} That is, $\mathbf{G}$ has generating objects for the words and the basic types of the grammar, and generating arrows $w \to t$ for the dictionary entries which assign a pregroup type $t$ to a word $w$ . The arrows $f: w_1 \dots w_n \to s$ are grammatical derivations for the sentence $w_1 \dots w_n$ which can be represented as string diagrams with cups and caps, i.e. adjunction units and counits.{{cite book |last=Selinger |first=Peter |title=New Structures for Physics |chapter=A survey of graphical languages for monoidal categories |series=Lecture Notes in Physics |year=2010 |arxiv=0908.3347 |volume=813 |pages=289–355 |doi=10.1007/978-3-642-12821-9_4|isbn=978-3-642-12820-2 |s2cid=8477212 }}

With this definition of pregroup grammars as free rigid categories, DisCoCat models can be defined as strong monoidal functors $F : \mathbf{G} \to \mathbf{FinVect}$ . Spelling things out in detail, they assign a finite dimensional vector space $F(x)$ to each basic type $x$ and a vector $F(w) \in F(t) = F(t_1) \otimes \dots \otimes F(t_n)$ in the appropriate tensor product space to each dictionary entry $w \to t$ where $t = t_1 \dots t_n$ (objects for words are sent to the monoidal unit, i.e. $F(w) = 1$ ). The meaning of a sentence $f: w_1 \dots w_n \to s$ is then given by a vector $F(f) \in F(s)$ which can be computed as the contraction of a tensor network.{{Cite journal |last1=de Felice |first1=Giovanni |last2=Meichanetzidis |first2=Konstantinos |last3=Toumi |first3=Alexis |date=2020-09-15 |title=Functorial Question Answering |arxiv=1905.07408 |journal=Electronic Proceedings in Theoretical Computer Science |volume=323 |pages=84–94 |doi=10.4204/EPTCS.323.6 |s2cid=195874109 |issn=2075-2180}}

The reason behind the choice of $\mathbf{FinVect}$ as the category of semantics is that vector spaces are the usual setting of distributional reading in computational linguistics and natural language processing. The underlying idea of distributional hypothesis "A word is characterized by the company it keeps" is particularly relevant when assigning meaning to words like adjectives or verbs, whose semantic connotation is strongly dependent on context.

Variations

Variations of DisCoCat have been proposed with a different choice for the grammar category. The main motivation behind this lies in the fact that pregroup grammars have been proved to be weakly equivalent to context-free grammars.{{Cite journal |first1=Wojciech |last1=Buszkowski |date=2001 |title=Lambek grammars based on pregroups. |journal=In International Conference on Logical Aspects of Computational Linguistics}} One example of variation{{cite arXiv |eprint=2105.07720 |first1=Richie |last1=Yeung |first2=Dimitri |last2= Kartsaklis |title=A CCG-based version of the DisCoCat framework. |date=2021|class=cs.CL }} chooses Combinatory categorial grammar as the grammar category.

List of linguistic phenomena

The DisCoCat framework has been used to study the following phenomena from linguistics.

Entailment{{Cite journal |last1=Sadrzadeh |first1=Mehrnoosh |last2=Kartsaklis |first2=Dimitri |last3=Balkır |first3=Esma |date=2018 |title=Sentence entailment in compositional distributional semantics |url=https://scholar.googleusercontent.com/scholar.bib?q=info:RmKmNl-W7K8J:scholar.google.com/&output=citation&scisdr=CgUx7uJgEJT6uf2eIyQ:AAGBfm0AAAAAY2uYOyQroAN5jVsHpnOm5INOsOVv3JV6&scisig=AAGBfm0AAAAAY2uYO6CoH69A34XAjBGynCL94eJzJkU5&scisf=4&ct=citation&cd=-1&hl=en |journal=Annals of Mathematics and Artificial Intelligence |volume=82 |issue=4 |pages=189–218|doi=10.1007/s10472-017-9570-x |s2cid=5038840 |doi-access=free |arxiv=1512.04419 }}
Coordination{{cite journal |arxiv=1606.01515 |first=Dimitri |last=Kartsaklis |title=Coordination in Categorical Compositional Distributional Semantics |journal=Electronic Proceedings in Theoretical Computer Science |date=2016|volume=221 |pages=29–38 |doi=10.4204/EPTCS.221.4 |s2cid=10842035 }}
Hyponymy and hypernymy{{Cite journal |last1=Bankova |first1=Dea |last2=Coecke |first2=Bob |last3=Lewis |first3=Martha |last4=Marsden |first4=Dan |date=2018 |title=Graded hyponymy for compositional distributional semantics |url=https://scholar.googleusercontent.com/scholar.bib?q=info:j1036XEK5QkJ:scholar.google.com/&output=citation&scisdr=CgUx7uJgEJT6uf2R5bU:AAGBfm0AAAAAY2uX_bXvCx4aD6Lbg5B_hkLURh-yXa9_&scisig=AAGBfm0AAAAAY2uX_TXADdSVe7bfdiBIjsXni3_b_ynE&scisf=4&ct=citation&cd=-1&hl=en |journal=Journal of Language Modelling |volume=6 |issue=2 |pages=225–260}}
Ambiguity with density matrices{{cite arXiv |last1=Meyer |first1=Francois |last2=Lewis |first2=Martha |date=2020-10-12 |title=Modelling Lexical Ambiguity with Density Matrices |class=cs.CL |eprint=2010.05670 }}
Discourse analysis{{Cite journal |last1=Coecke |first1=Bob |last2=de Felice |first2=Giovanni |last3=Marsden |first3=Dan |last4=Toumi |first4=Alexis |date=2018-11-08 |title=Towards Compositional Distributional Discourse Analysis |journal=Electronic Proceedings in Theoretical Computer Science |volume=283 |pages=1–12 |doi=10.4204/EPTCS.283.1 |arxiv=1811.03277 |issn=2075-2180|doi-access=free }}
Anaphora and ellipsis{{Cite journal |last1=Wijnholds |first1=Gijs |last2=Sadrzadeh |first2=Mehrnoosh |date=2019 |title=A type-driven vector semantics for ellipsis with anaphora using lambek calculus with limited contraction |url=https://scholar.googleusercontent.com/scholar.bib?q=info:BocKa55sSXwJ:scholar.google.com/&output=citation&scisdr=CgUx7uJgEJT6uf2e35I:AAGBfm0AAAAAY2uYx5LJVXM0Ps9f8FNWD-l28jb9P1ln&scisig=AAGBfm0AAAAAY2uYx8mr7fiIjCQUup-bBjEWSa4DQms5&scisf=4&ct=citation&cd=-1&hl=en |journal=Journal of Logic, Language and Information |volume=28 |issue=2 |pages=331–358|doi=10.1007/s10849-019-09293-4 |s2cid=146120631 |doi-access=free |arxiv=1905.01647 }}
Language evolution{{cite journal |arxiv=1811.11041 |first1=Tai-Danae |last1=Bradley |first2=Martha |last2=Lewis |title=Translating and Evolving: Towards a Model of Language Change in DisCoCat |date=2018 |last3=Master |first3=Jade |last4=Theilman |first4=Brad|journal=Electronic Proceedings in Theoretical Computer Science |volume=283 |pages=50–61 |doi=10.4204/EPTCS.283.4 |s2cid=53775637 }}

Applications in NLP

The DisCoCat framework has been applied to solve the following tasks in natural language processing.

Word-sense disambiguation{{Cite arXiv |last1=Grefenstette |first1=Edward |last2=Sadrzadeh |first2=Mehrnoosh |date=2011-06-20 |title=Experimental Support for a Categorical Compositional Distributional Model of Meaning |class=cs.CL |eprint=1106.4058 }}{{Cite journal |last1=Kartsaklis |first1=Dimitri |last2=Sadrzadeh |first2=Mehrnoosh |date=2013 |title=Prior disambiguation of word tensors for constructing sentence vectors |url=https://www.researchgate.net/publication/262373873}}
Semantic similarity{{Cite arXiv |last1=Grefenstette |first1=Edward |last2=Dinu |first2=Georgiana |last3=Zhang |first3=Yao-Zhong |last4=Sadrzadeh |first4=Mehrnoosh |last5=Baroni |first5=Marco |date=2013-01-30 |title=Multi-Step Regression Learning for Compositional Distributional Semantics |class=cs.CL |eprint=1301.6939 }}
Question answering{{cite journal |arxiv=1905.07408 |first1=Giovanni |last1=de Felice |first2=Konstantinos |last2=Meichanetzidis |title=Functorial Question Answering |date=2019 |last3=Toumi |first3=Alexis|journal=Electronic Proceedings in Theoretical Computer Science |volume=323 |pages=84–94 |doi=10.4204/EPTCS.323.6 |s2cid=195874109 }}
Machine translation{{Cite journal |last=Tyrrell |first=Brian |date=2018-11-08 |title=Applying Distributional Compositional Categorical Models of Meaning to Language Translation |journal=Electronic Proceedings in Theoretical Computer Science |volume=283 |pages=28–49 |doi=10.4204/EPTCS.283.3 |arxiv=1811.03274 |issn=2075-2180|doi-access=free }}
Anaphora resolution{{Cite journal |last1=Coecke |first1=Bob |last2=de Felice |first2=Giovanni |last3=Marsden |first3=Dan |last4=Toumi |first4=Alexis |date=2018-11-08 |title=Towards Compositional Distributional Discourse Analysis |journal=Electronic Proceedings in Theoretical Computer Science |volume=283 |pages=1–12 |doi=10.4204/EPTCS.283.1 |arxiv=1811.03277 |issn=2075-2180|doi-access=free }}

External links

[https://discopy.readthedocs.io DisCoPy], a Python toolkit for computing with string diagrams
[https://cqcl.github.io/lambeq/ lambeq], a Python library for quantum natural language processing

References

Category:Computational linguistics

Category:Category theory