ACL Wiki - User contributions [en]

Combinatory Categorial Grammar

2009-08-10T11:03:57Z

Smerity: According to all pages and sources, it's Stephen and not Stephan - http://www.cl.cam.ac.uk/~sc609/

== Introduction ==

[[Image:Steedman2001.jpg|thumb|right|Steedman (2001): The Syntactic Process. MIT Press]]

Combinatory Categorial Grammar (CCG) is an efficiently parseable, yet linguistically expressive grammar formalism. It has a completely transparent interface between surface syntax and underlying semantic representation, including predicate-argument structure, quantification and information structure.
CCG relies on combinatory logic, which has the same expressive power as the lambda calculus, but builds its expressions differently.

The first linguistic and psycholinguistic arguments for basing the grammar on combinators were put forth by Mark Steedman and Anna Szabolcsi. More recent proponents of the approach are Jacobson and Baldridge.
For example, the [[combinator]] B (the compositor) is useful in creating long-distance dependencies, as in "Who do you think Mary is talking about?" and the combinator W (the duplicator) is useful as the lexical interpretation of reflexive pronouns, as in "Mary talks about herself". Together with I (the identity mapping) and C (the permutator) these form a set of primitive, non-interdefinable combinators. Jacobson interprets personal pronouns as the combinator I, and their binding is aided by a complex combinator Z, as in "Mary lost her way". Z is definable using W and B.

CCG is known to define the same language class as tree-adjoining grammar, linear indexed grammar, and head grammar, and is said to be mildly context-sensitive.

One of the key publications of CCG is ''The Syntactic Process'' by Mark Steedman. There are various efficient parsers available for CCG.

== Software ==

=== OpenCCG: The OpenNLP CCG library ===

[http://openccg.sourceforge.net OpenCCG], the [http://opennlp.sf.net OpenNLP] CCG Library,
is an open source natural language processing library written in
Java, which provides parsing and realization services based on Mark Steedman's
Combinatory Categorial Grammar (CCG) formalism.
The library makes use of multi-modal extensions to CCG developed by
[http://comp.ling.utexas.edu/jbaldrid Jason Baldridge] as part of the [http://grok.sourceforge.net/ Grok] system
(the precursor to OpenCCG). Current development efforts, led by [http://www.ling.ohio-state.edu/~mwhite/ Michael White], are focused on making the realizer practical to use in dialogue systems. For the latest news about OpenCCG, check out the
[http://openccg.sourceforge.net/ OpenCCG page] on SourceForge. You can also look at [http://comp.ling.utexas.edu/wiki/doku.php/openccg/projects_using_openccg some of the projects using OpenCCG].

The VisCCG tool for working with grammars is available as part of the OpenCCG source code and distribution. There are [http://comp.ling.utexas.edu/wiki/doku.php/openccg several tutorials available for learning how to edit grammars with VisCCG and use OpenCCG].

=== The C&C Parser and Supertagger ===

The [http://svn.ask.it.usyd.edu.au/trac/candc/wiki C&C CCG parser and supertagger] form
part of the language processing tools developed by James Curran and Stephen Clark.
The tools are written in C++ and have been designed to be efficient enough for large-scale NLP tasks.

=== StatCCG ===

StatCCG is a statistical CCG parser (trained on CCGbank) written by Julia Hockenmaier. Executables are available [http://www.cis.upenn.edu/~juliahr/Parser/index.html here]

=== Boxer ===

[http://svn.ask.it.usyd.edu.au/trac/candc/wiki/boxer Boxer] is developed by [http://homepages.inf.ed.ac.uk/jbos/ Johan Bos] and generates formal semantic representations for CCG grammars. Boxer takes as input CCG (Combinatory Categorial Grammar) derivations and produces DRSs (Discourse Representation Structures, from Hans Kamp's Discourse Representation Theory) as output. It is distributed with the C&C tools. Boxer produces standard DRS syntax, uses a neo-Davidsonian analysis for events (with thematic roles from VerbNet), incorporates Van der Sandt's algorithm for presupposition, is 100% compatible with first-order logic (FOL), and normalises cardinal and date expressions. DRSs can be generated in various output formats: resolved or underspecified, in Prolog or XML, flattened or recursive structures, with discourse referents represented by Prolog atoms or variables, and with pretty printed DRSs or not. It is also possible to output FOL formulas translated from the DRSs.

== CCGbank ==

CCGbank is a translation of the [http://www.cis.upenn.edu/~treebank/home.html Penn Treebank]
into a corpus of Combinatory Categorial Grammar derivations, created by [http://www.cis.upenn.edu/~juliahr Julia Hockenmaier] and [http://www.inf.ed.ac.uk/~steedman Mark Steedman]. You can get it [http://www.ldc.upenn.edu/Catalog/CatalogEntry.jsp?catalogId=LDC2005T13 here] from the [http://www.ldc.upenn.edu Linguistic Data Consortium]. You can also have a look at this [http://www.cis.upenn.edu/~juliahr/CCGbankDemo demo] of the HTML version included in the LDC distribution.

CCGbank pairs syntactic derivations with sets of word-word dependencies which
approximate the underlying predicate-argument structure.
The translation process and linguistic analyses are explained in the [http://www.cis.upenn.edu/~juliahr/Papers/CCGbank/CCGbankManual.pdf manual].
CCGbank contains 99.44% of the sentences in the Penn Treebank, for
which it corrects a number of inconsistencies and errors in the
original annotation.

The LDC distribution also contains machine-readable versions
of the data, which contain the syntactic derivations and the corresponding lists of word-word dependencies,
as well as a file that is searchable by [http://tedlab.mit.edu/~dr/ Doug Rohde]'s [http://tedlab.mit.edu/~dr/TGrep2/index.html TGrep2] (version 1.15).

In all versions, the file structure corresponds exactly to that of the original Treebank.

== Publications ==

This is a very incomplete list of publications. Follow the links to homepages in the People section to see more, and see the [http://groups.inf.ed.ac.uk/ccg/publications.html CCG site publications page].

=== Books ===

* Curry, Haskell B. and Richard Feys (1958), Combinatory Logic, Vol. 1. North-Holland.

* Steedman, Mark (1996), Surface Structure and Interpretation. The MIT Press.

* Steedman, Mark (2000), The Syntactic Process. The MIT Press.

=== Journal Articles ===

* Jacobson, Pauline (1999), “Towards a variable-free semantics.” Linguistics and Philosophy 22, 1999. 117-184

* Steedman, Mark (1987), “Combinatory grammars and parasitic gaps”. Natural Language and Linguistic Theory 5, 403-439.

=== Articles in books or collections ===

* Szabolcsi, Anna (1989), "Bound variables in syntax (are there any?)." Semantics and Contextual Expression, ed. by Bartsch, van Benthem, and van Emde Boas. Foris, 294-318.

* Szabolcsi, Anna (1992), "Combinatory grammar and projection from the lexicon." Lexical Matters. CSLI Lecture Notes 24, ed. by Sag and Szabolcsi. Stanford, CSLI Publications. 241-269.

* Szabolcsi, Anna (2003), “Binding on the fly: Cross-sentential anaphora in variable-free semantics”. Resource Sensitivity in Binding and Anaphora, ed. by Kruijff and Oehrle. Kluwer, 215-229.

=== Conference and workshop papers ===

* Jason Baldridge and Geert-Jan Kruijff. 2002. [http://www.aclweb.org/anthology-new/P/P02/P02-1041.pdf Coupling CCG with Hybrid Logic Dependency Semantics]. In Proceedings of ACL 2002.

* Jason Baldridge and Geert-Jan Kruijff. 2003. [http://www.aclweb.org/anthology-new/E/E03/E03-1036.pdf Multi-Modal Combinatory Categorial Grammar]. In Proceedings of EACL 2003.

* Jason Baldridge, Sudipta Chatterjee, Alexis Palmer, and Ben Wing. 2007. [http://comp.ling.utexas.edu/jbaldrid/papers/baldridge_etal_geaf07.pdf DotCCG and VisCCG: Wiki and Programming Paradigms for Improved Grammar Engineering with OpenCCG]. In Proceedings of the Workshop on Grammar Engineering Across Frameworks. Stanford, CA.

* Jason Baldridge. 2008. [http://comp.ling.utexas.edu/jbaldrid/papers/BaldridgeColing08.pdf Weakly supervised supertagging with grammar-informed initialization]. In Proceedings of COLING-2008. Manchester, UK.

* Fred Hoyt and Jason Baldridge. 2008. [http://aclweb.org/anthology-new/P/P08/P08-1038.pdf A Logical Basis for the D combinator and normal form constraints in Combinatory Categorial Grammar]. In Proceedings of ACL/HLT-2008. Columbus, OH.
* Geert-Jan Kruijff and Jason Baldridge. 2004. [http://www.aclweb.org/anthology-new/C/C04/C04-1028.pdf Generalizing Dimensionality in Combinatory Categorial Grammar]. Proceedings of COLING 2004.

* Mike White and Jason Baldridge. 2003. [http://comp.ling.utexas.edu/jbaldrid/papers/White-Baldridge-ENLG-2003 Adapting Chart Realization to CCG]. In Proceedings of ENLG 2003.

=== Dissertations and Masters Theses ===

* Baldridge, Jason (2002). [http://comp.ling.utexas.edu/jbaldrid/papers/dissertation.html "Lexically Specified Derivational Control in Combinatory Categorial Grammar."] PhD Dissertation. Univ. of Edinburgh.

* Gann Bierner (2001). Alternative Phrases: Theoretical Analysis and Practical Applications, PhD thesis, University of Edinburgh.

* Julia Hockenmaier (2003). Data and Models for Statistical Parsing with Combinatory Categorial Grammar, PhD thesis, University of Edinburgh.

* Beryl Hoffman. 1995. Computational Analysis of the Syntax and Interpretation of ‘Free’ Word-order in Turkish. Ph.D. thesis, University of Pennsylvania. IRCS Report 95-17.

* Nobo Komagata. 1999. [http://nobo.komagata.net/thesis A Computational Analysis of Information Structure Using Parallel Expository Texts in English and Japanese]. PhD thesis. University of Pennsylvania.

* Mark McConville (2001) Incremental natural language understanding with Combinatory Categorial Grammar. MSc thesis, School of Cognitive Science, Division of Informatics, University of Edinburgh.

* Jong C. Park. 1996. [http://portal.acm.org/citation.cfm?id=923558 A Lexical Theory of Quantification in Ambiguous Query Interpretation]. Ph.D Dissertation, Department of Computer and Information Science, University of Pennsylvania.

== People ==

* [http://comp.ling.utexas.edu/jbaldrid Jason Baldridge]
* [http://homepages.inf.ed.ac.uk/jbos/ Johan Bos]
* [http://www.ceng.metu.edu.tr/~bozsahin/ Cem Bozsahin]
* [http://web.comlab.ox.ac.uk/oucl/work/stephen.clark/ Stephen Clark]
* [http://www.it.usyd.edu.au/about/people/staff/james.shtml James Curran]
* [http://www.cis.upenn.edu/~juliahr Julia Hockenmaier]
* [http://www.iccs.inf.ed.ac.uk/~steedman/ Mark Steedman]
* [http://www.ling.ohio-state.edu/~mwhite/ Michael White]

Noun-Modifier Semantic Relations (State of the art)

2009-07-13T03:11:47Z

Smerity: Repairing download link - /nn/vivi... leads to 404, but following the pattern of others /nn/data/vivi... leads to correct file

* 600 noun-modifier pairs labeled with 30 classes of semantic relations
* 30 classes organized into 5 superclasses
* introduced in Nastase and Szpakowicz (2003)
* subsequently used by many other researchers
* data available from [http://www.cs.utexas.edu/~mfkb/nn/data/vivi.tar.gz UT Repository]
* information about data available from [http://www.site.uottawa.ca/~vnastase/noun_modifier_data.html Vivi Nastase] and [http://www.csi.uottawa.ca/~vnastase/papers/wn_roget.ps Nastase and Szpakowicz (2003)]

== Five superclasses ==

* '''Causality:''' "cold virus", "onion tear"
* '''Temporality:''' "morning frost", "summer travel"
* '''Spatial:''' "aquatic mammal", "west coast", "home remedy"
* '''Participant:''' "dream analysis", "mail sorter", "blood donor"
* '''Quality:''' "copper coin", "rice paper", "picture book"

== Table of results ==

{| border="1" cellpadding="5" cellspacing="1" width="100%"
|-
! Algorithm
! Reference
! 5-class F-measure
! 5-class accuracy
! 95% confidence for accuracy
|-
| Baseline
| Majority class (Participant)
| NA
| 43.3%
| 39.39-47.30%
|-
| VSM
| Turney and Littman (2005)
| 43.2%
| 45.7%
| 41.75-49.70%
|-
| SVM+28
| Nulty (2007)
| NA
| 50.1%
| 46.11-54.09%
|-
| PERT
| Turney (2006a)
| 50.2%
| 54.0%
| 50.00-57.95%
|-
| TiMBL+WordNet
| Nastase et al. (2006)
| 51.5%
| NA
| NA
|-
| LRA
| Turney (2006b)
| 54.6%
| 58.0%
| 54.01-61.89%
|-
|}

== Explanation of table ==

* '''Algorithm''' = name of algorithm
* '''Reference''' = where to find out more about given algorithm and experiments
* '''5-class F-measure''' = macroaveraged F-measure for the 5 superclasses
* '''5-class accuracy''' = accuracy for the 5 superclasses
* '''95% confidence for accuracy''' = confidence interval calculated using [http://www.quantitativeskills.com/sisa/statistics/onemean.htm Wilson Test]
* table rows sorted in order of increasing performance
* Baseline = always guess the majority class (Participant)
* VSM = Vector Space Model
* LRA = Latent Relational Analysis
* PERT = Pertinence
* TiMBL+WordNet = Tilburg Memory Based Learner + WordNet-based representation with word sense information
* SVM+28 = Support Vector Machine + all 28 joining terms

== References ==

Nastase, Vivi and Stan Szpakowicz. (2003). [http://www.csi.uottawa.ca/~vnastase/papers/wn_roget.ps Exploring noun-modifier semantic relations]. In ''Fifth International Workshop on Computational Semantics (IWCS-5)'', pages 285–301, Tilburg, The Netherlands.

Nastase, Vivi, Jelber Sayyad Shirabad, Marina Sokolova, and Stan Szpakowicz. (2006). [http://rali.iro.umontreal.ca/Publications/files/compare_contexts_NMRs.pdf Learning noun-modifier semantic relations with corpus-based and Wordnet-based features]. In ''Proceedings of the 21st National Conference on Artificial Intelligence (AAAI-06)'', pages 781-787. Boston, Massachusetts.

Nulty, Paul. (2007). [http://acl.ldc.upenn.edu/P/P07/P07-3014.pdf Semantic classification of noun phrases using web counts and learning algorithms]. In ''Proceedings of the ACL 2007 Student Research Workshop (ACL-07)'', pages 79-84. Prague, Czech Republic.

Turney, Peter D. (2005). [http://arxiv.org/abs/cs.LG/0508053 Measuring semantic similarity by latent relational analysis]. In ''Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05)'', pages 1136–1141, Edinburgh, Scotland.

Turney, Peter D. and Michael L. Littman. (2005). [http://arxiv.org/abs/cs.LG/0508103 Corpus-based learning of analogies and semantic relations]. ''Machine Learning'', 60(1–3):251–278.

Turney, P.D. (2006a). [http://arxiv.org/abs/cs.CL/0607120 Expressing implicit semantic relations without supervision]. In ''Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics (Coling/ACL-06)'', Sydney, Australia, pp. 313-320.

Turney, P.D. (2006b). [http://arxiv.org/abs/cs.CL/0608100 Similarity of semantic relations]. ''Computational Linguistics'', 32 (3), 379-416.

== See also ==

* [[Noun compound repository]]
* [[Citations of the Diverse Noun Compound Dataset]]
* [[SAT Analogy Questions]]

[[Category:State of the art]]

Noun compound repository

2009-07-13T03:10:51Z

Smerity: Repairing download link - /nn/vivi... leads to 404, but following the pattern of others /nn/data/vivi... leads to correct file

'''University of Texas Noun-Compound Repository'''

The University of Texas is hosting several noun-compound datasets that can be used to empirically evaluate noun-compound interpretation or classification algorithms. The table below summarizes the datasets in the UT Repository. If you have a noun-compound dataset that you would like to add to the UT Repository, contact [mailto:jfan@cs.utexas.edu James Fan]. If you have any publications based on data obtained from this repository, UT requests that you acknowledge the assistance you received by using the UT Repository. The following reference format is suggested for referring to the repository:

: Fan, J. & Porter, B. (2006). ''UT Repository of noun-compounds'', http://www.cs.utexas.edu/~mfkb/nn. Austin, TX: University of Texas, Department of Computer Sciences.

{| border="1"
!Dataset Name!!Contributor!!Size!!Domain!!Text Source!!Annotated?!!Citations of Dataset!!Download
|-
|Engines||Ken Barker||505||Small engine repair||Atkinson, H. Mechanics of Small Engines||Yes||K. Barker and S. Szpakowicz. Semi-automatic recognition of Noun Modifier Relationships Proceedings of COLING-ACL 1998||[http://www.cs.utexas.edu/~mfkb/nn/data/engines.tar.gz UT Repository]
|-
|Sparc||Ken Barker||335||Sparcstation manual||Chan, L. (1989) SPARCstation 1 Installation Guide||Yes||K. Barker and S. Szpakowicz. Semi-automatic Recognition of Noun Modifier Relationships Proceedings of COLING-ACL 1998||[http://www.cs.utexas.edu/~mfkb/nn/data/nmrDict.sparc.gz UT Repository]
|-
|Cell||James Fan||224||Cell biology||Alberts, B & et al. (1998) Essential Cell Biology: An Introduction to the Molecular Biology of the Cell||No||J. Fan, K. Barker and B. Porter. The Knowledge Required to Interpret Noun Compounds Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence 2003||[http://www.cs.utexas.edu/~mfkb/nn/data/alberts.zip UT Repository]
|-
|Diverse||Vivi Nastase||600||Various||[http://www.site.uottawa.ca/~vnastase/noun_modifier_data.html See Details]||Yes||[[Citations of the Diverse Noun Compound Dataset|Citations of "Diverse"]]||[http://www.cs.utexas.edu/~mfkb/nn/data/vivi.tar.gz UT Repository]
|}