#
#
# Bill MacCartney
# Spring 2015
#
#
#
# The idea is to achieve a [separation of concerns][]. We wish to endow the overall system with the ability to respond to linguistic inputs. The semantic parser focuses on dealing with the complexities of human language: [polysemy][], [syntactic ambiguity][], [indexicality][] and other forms of context-dependence, [ellipsis][], and so on. It emits an output which captures the key elements of the user's intent in a clear, unambiguous, fully-grounded, machine-readable representation. The executor is thereby freed of the burden of interpreting language, and can focus on its application-specific business.
#
# [separation of concerns]: http://en.wikipedia.org/wiki/Separation_of_concerns
# [polysemy]: http://en.wikipedia.org/wiki/Polysemy
# [syntactic ambiguity]: http://en.wikipedia.org/wiki/Syntactic_ambiguity
# [indexicality]: http://en.wikipedia.org/wiki/Indexicality
# [ellipsis]: http://en.wikipedia.org/wiki/Ellipsis
#
# Of course, semantic representations need not look like the example shown here. As we'll see in a moment, different problem settings may demand quite different semantic representations.
# ## Example applications
# In this codelab, we'll take a close look at three example applications of semantic parsing: one rather artificial, the others more realistic.
#
# Our [first case study][] will follow [Liang & Potts 2015][] in considering the problem of interpreting natural language arithmetic expressions, such as:
#
# [first case study]: ./sippycup-unit-1.ipynb
# [Liang & Potts 2015]: http://www.annualreviews.org/doi/pdf/10.1146/annurev-linguist-030514-125312
#
# "one plus one"
# "minus three minus two"
# "three plus three minus two"
# "two times two plus three"
#
# In this problem setting, we may wish to produce semantic representations which are [binary expression trees][]:
#
# [binary expression trees]: http://en.wikipedia.org/wiki/Binary_expression_tree
#
# (+ 1 1)
# (- (- 3) 2)
# (- (+ 3 3) 2)
# (+ (* 2 2) 3)
#
# These representations fully resolve the ambiguity present in the linguistic inputs, and can be evaluated by a simple, deterministic executor to produce a numeric answer.
#
# In our [second case study][], we'll examine a more realistic application: the domain of queries about travel and transportation, such as:
#
# [second case study]: ./sippycup-unit-2.ipynb
#
# "birmingham al distance from indianapolish in"
# "directions from washington to canada"
# "discount travel flights to austin texas"
#
# A possible style of semantic representation (described further in [Unit 2](./sippycup-unit-2.ipynb#A-semantic-representation-for-travel-queries)) for this domain is:
#
# {domain: travel, type: distance,
# origin: {id: 4259418, name: "Indianapolis, IN, US"},
# destination: {id: 4049979, name: "Birmingham, AL, US"}}
# {domain: travel, type: directions,
# origin: {id: 4140963, name: "Washington, DC, US"},
# destination: {id: 6251999, name: "Canada"}}
# {domain: travel, mode: air,
# destination: {id: 4671654, name: "Austin, TX, US"}}
#
# Here the request types and transportation modes have been resolved to canonical values, and the locations have been resolved to unique identifiers in the [GeoNames][] geographical database. It's easy to imagine passing representations like these to a backend API, such a route-planning service, for execution.
#
# [GeoNames]: http://www.geonames.org/
#
# Our [third case study][] will focus on the [Geo880][] corpus developed in Ray Mooney's group at UT Austin, which has for many years served as a standard evaluation for semantic parsing systems. (See, for example, [Zelle & Mooney 1996][], [Tang & Mooney 2001][], [Zettlemoyer & Collins 2005][], and [Liang et al. 2011][].) The Geo880 corpus contains 880 questions about U.S. geography, often with complex compositional structure. Examples include:
#
# [third case study]: ./sippycup-unit-3.ipynb
# [Geo880]: http://www.cs.utexas.edu/users/ml/geo.html
# [Zelle & Mooney 1996]: http://www.aaai.org/Papers/AAAI/1996/AAAI96-156.pdf
# [Tang & Mooney 2001]: http://www.cs.utexas.edu/~ai-lab/pubs/cocktail-ecml-01.pdf
# [Zettlemoyer & Collins 2005]: http://people.csail.mit.edu/lsz/papers/zc-uai05.pdf
# [Liang et al. 2011]: http://www.cs.berkeley.edu/~jordan/papers/liang-jordan-klein-acl2011.pdf
#
# "which states border texas?"
# "how many states border the largest state?"
# "what is the size of the capital of texas?"
#
# Here again, many styles of semantic representation are possible. One possibility (described further in [Unit 3](./sippycup-unit-3.ipynb#geoquery-semantic-representation)) is:
#
# (.and state (borders /state/texas))
# (.count (.and state (borders (.argmax area state))))
# ((/state/texas capital) population)
#
# The Geo880 corpus is a paired with a simple geographical database known as [Geobase][]. A suitable executor can evaluate these semantic representations against Geobase to return answers.
#
# [Geobase]: http://www.cs.utexas.edu/users/ml/nldata/geoquery.html
#
# Academic researchers have explored many other potential applications for semantic parsing, including:
#
# - robot control ([Matuszek et al. 2012][])
# - `"go to the third junction and take a right"`
# - question answering against Freebase ([Cai & Yates 2013][], [Kwiatkowski et al. 2013][], [Berant et al. 2013][])
# - `"how many countries use the euro"`
# - 3D scene generation ([Chang et al. 2014][])
# - `"there is a room with a desk and a red chair"`
# - teaching computers to play games ([Branavan et al. 2012][])
# - `"phalanxes are twice as effective at defending cities as warriors"`
# - solving algebra word problems ([Kushman et al. 2014][])
# - `"an amusement park sells two kinds of tickets ..."`
#
# [Matuszek et al. 2012]: http://www.csee.umbc.edu/~cmat/Pubs/MatuszekISER2012.pdf
# [Cai & Yates 2013]: http://www.cis.temple.edu/~yates/papers/textual-schema-matching.pdf
# [Kwiatkowski et al. 2013]: http://yoavartzi.com/pub/kcaz-emnlp.2013.pdf
# [Berant et al. 2013]: http://cs.stanford.edu/~pliang/papers/freebase-emnlp2013.pdf
# [Chang et al. 2014]: http://nlp.stanford.edu/pubs/scenegen-sp2014.pdf
# [Branavan et al. 2012]: https://jair.org/media/3484/live-3484-6254-jair.pdf
# [Kushman et al. 2014]: http://homes.cs.washington.edu/~lsz/papers/kazb-acl14.pdf
#
#
# In each case, the task is to map a linguistic input into a structured, machine-readable representation of meaning, on which some downstream component can take action.
# ## Why is semantic parsing hard?
# (TODO: flesh out a section explaining the key challenges of semantic parsing.)
#
# - the mind-boggling variability of linguistic expression: many expressions, one meaning
# - ambiguity: one expression, many meanings
# - context-dependence
# - messy inputs: typos, misspellings, loose or mangled syntax
# - scalability: don't want to have to manually engineer everything — automated learning instead
# - internationalization
# ## Designing a semantic representation
# When developing a semantic parsing system for a new domain, one of the first tasks must be to choose a good semantic representation. After all, this representation is the target output of the system, so its design will drive many other design decisions. We can't control the form of the linguistic inputs, but we *can* control the design of the semantic outputs.
#
# (Actually, in some problem settings, we have to work with a downstream executor over whose request language we have no control. For example, the executor may be an API provided by a third party, or it may be a relational database which only responds to SQL queries. However, even in such situations, we have the opportunity to control the design of our semantic representation, by inserting into the stack an *adapter* which performs a deterministic conversion from our semantic representation into the request language of the executor.)
#
# So what constitutes a good semantic representation? We can't make rigid generalizations, but we can identify some guiding principles. Above all, in order to achieve a separation of concerns between the semantic parsing system and the executor, the semantic representation must be straightforwardly machine-readable by the executor. Machine-readability means that executor can immediately understand what it needs to do, and get straight to work. (Actually, machine-*interpretable* would be a more accurate term. In some limited sense, any ASCII-encoded text is machine-readable, but it is usually not machine-interpretable. But we'll stick with the standard term.) With consideration, two hallmarks of machine-readability emerge: *ambiguity resolution* and *canonicalization*.
# ### Ambiguity resolution
# Ambiguity resolution means that if an input has two different meanings, it should have two different semantic representations. For example, consider the input "how big is new york". This has at least four different meanings, depending on whether we take "big" to refer to population or area, and on whether we take "new york" to refer to the city or the state. If all four interpretations are valid, then our semantic parser should generate four semantic representations, perhaps along with some kind of scores. But when the executor receives one of these semantic representations as input, it has no decisions to make — it can take action immediately without having to do further interpretation.
#
# 
# ### Canonicalization
# Canonicalization is the obverse of ambiguity resolution: it means that if two inputs have the same meaning, they should have the same semantic representation. For example, consider the inputs "nyc population" and "how many people live in new york city". These have the same meaning, so they should have the same representation — a *canonical* representation. Or consider the inputs "next thanksgiving" and "november 26". As of this writing (in early 2015), these phrases refer to the same date, so they should have the same representation — perhaps the [ISO 8601][] representation "2015-11-26". Canonicalization thus means using unique identifiers for entities, and fully grounding expressions whose meaning depends on context.
#
# [ISO 8601]: http://xkcd.com/1179/
#
# 
#
# In some problem settings, canonicalization is less critical than ambiguity resolution, because some downstream executors can tolerate two different ways of saying the same thing. But the great virtue of canonicalization is that it makes checking semantic *equivalence* as easy as checking *equality* of the semantic representations. For example, the semantic equivalence of "two forty five pm" and "quarter of three in the afternoon" may not be immediately obvious (to a machine), but becomes trivial if both are represented by 14:45.
# ### One representation to rule them all?
# In the example applications above, we showed three quite different styles of semantic representation. Indeed, most academic research in semantic parsing has used application-specific semantic representations, although many of these share some common elements (such as the use of the [simply typed lambda calculus][]).
#
# [simply typed lambda calculus]: http://en.wikipedia.org/wiki/Simply_typed_lambda_calculus
#
# But a natural question is: couldn't we design a single, universal semantic representation, capable of representing in machine-readable form all meanings which can be expressed in natural language? Such a representation would not only spare us the trouble of inventing a new representation for each application; it would also open the door to effortlessly combining semantic parsing models which had been developed for different domains. For example, we can imagine combining an arithmetic model with a travel model to interpret inputs like "four times the distance from boston to miami".
#
# It's a tempting idea, and an old one. [Leibniz][], for example, dreamed of creating a [*characteristica universalis*][] which would serve as a sort of algebra of ideas and thereby endow all thought with the exactitude of arithmetic. Since Leibniz's time, there have been [many attempts][] to construct universal logical languages for human use, such as [Lojban][]. However, such languages fail the test of true machine-readability. The ideal representation should enable a machine to take appropriate action, for example, by testing equivalence or performing simple inferences.
#
# [Leibniz]: http://en.wikipedia.org/wiki/Gottfried_Wilhelm_Leibniz
# [*characteristica universalis*]: http://en.wikipedia.org/wiki/Characteristica_universalis
# [many attempts]: http://en.wikipedia.org/wiki/Characteristica_universalis#More_recent_projects
# [Lojban]: http://en.wikipedia.org/wiki/Lojban
# [recognizing textual entailment]: http://en.wikipedia.org/wiki/Textual_entailment
#
# One recent creation that might seem like a better candidate is the [Abstract Meaning Representation][] (AMR) being developed at [ISI][]. As a simple example, all of these inputs:
#
# [Abstract Meaning Representation]: http://amr.isi.edu/
# [ISI]: http://www.isi.edu/home
#
# the boy wants the girl to believe him
# the boy wants to be believed by the girl
# the boy has a desire to be believed by the girl
# the boy's desire is for the girl to believe him
# the boy is desirous of the girl believing him
#
# are represented by the same AMR:
#
# (w / want-01
# :ARG0 (b / boy)
# :ARG1 (b2 / believe-01
# :ARG0 (g / girl)
# :ARG1 b))
#
# (Note that the variable `b` appears twice, once as the `:ARG0` of `want-01`, and once as the `:ARG1` of `believe-01`. You can learn more about how AMR works by reading the [AMR specification][].)
#
# [AMR specification]: https://github.com/amrisi/amr-guidelines/blob/master/amr.md
#
# These examples might give us hope that AMR can satisfy our goals for a semantic representation. By abstracting away from certain lexical choices ("want" vs. "desire") and syntactic choices (active vs. passive), AMR canonicalizes these inputs to a common representation, and thus renders obvious their semantic equivalence.
#
# But as Hal Daumé III argues in a persuasive [blog post][], AMR doesn't go nearly far enough in this direction to serve as a representation over which we can reliably perform automated reasoning. It resolves some kinds of ambiguity, but not others. It achieves some canonicalization, but not all. There are many kinds of semantically equivalent transformations — lexical, compositional, logical — whose AMR formulations are not obviously equivalent. In fact, AMR seems to be a bit of a hodge-podge, reflecting some information about lexical choice, some about syntactic structure, and some about semantic content. In many ways, it looks like a souped-up version of [semantic role labeling][]. Like SRL, AMR may be useful for some purposes, but it can't reliably be used as a vehicle for inference. (To be fair, the creators of AMR never promised this — they have been motivated rather by the goals of machine translation.)
#
# [blog post]: http://nlpers.blogspot.com/2014/09/amr-not-semantics-but-close-maybe.html
# [semantic role labeling]: http://en.wikipedia.org/wiki/Semantic_role_labeling
#
# (Note that if AMR *could* be used for automated reasoning, then a good AMR parser would provide a simple solution to the problem of [recognizing textual entailment][] (RTE), that is, recognizing whether one natural-language sentence can be inferred from another. One would simply parse both sentences into AMR, and then apply an automated reasoner to check entailment. To my knowledge, no one has demonstrated that this is possible.)
#
# [recognizing textual entailment]: http://en.wikipedia.org/wiki/Textual_entailment
#
# In short, my view is that AMR is not a suitable target representation for semantic parsing. Indeed, after decades (or even centuries!) of failures, I'm skeptical of any attempt to define a universal, machine-readable semantic representation, and prefer instead to develop application-specific representations as needed.
# ## Semantic parsing vs. machine translation
# (TODO)
# - Both tasks involve translating from one semantic representation into another.
# - In both tasks, the semantic representations often have complex structures which are related in complex ways.
# - But in machine translation, the target semantic representation is NOT machine-readable! Rather, it is _human_-readable.
# ## The SippyCup codebase
# The codelab you're reading has been published as an [IPython Notebook][], which makes it easy to combine text and interactive Python code. If you're new to Python, you might find this [Python tutorial][] useful.
#
# [IPython Notebook]: http://ipython.org/notebook.html
# [Python tutorial]: http://cs231n.github.io/python-numpy-tutorial/
#
# However, SippyCup is more than this codelab. First and foremost, it is a library of Python source files, which should be found in the [same directory](./) as the codelab you're reading. If not, you can find the codelab and the source files together in the [SippyCup GitHub repository][]. Note that this codelab uses `import` statements to pull in definitions of certain utility classes and functions from the accompanying source files. If the source files are missing, running the codelab code interactively will cause those imports to fail.
#
# [SippyCup GitHub repository]: https://github.com/wcmac/sippycup
#
# You will observe that the SippyCup code architecture does not always adhere to the principles of object-oriented design. Functionality which might naturally be captured by instance methods of classes will in some cases appear instead in standalone static functions. This is in order to facilitate an incremental presentation in this codelab format.
#
# Let's get started with [Unit 1](./sippycup-unit-1.ipynb)!
#
# Copyright (C) 2015 Bill MacCartney