We present a framework that couples the syntax and semantics of natural language sentences in a generative model, in order to develop a semantic parser that jointly infers the syntactic, morphological, and semantic representations of a given sentence under the guidance of background knowledge. To generate a sentence in our framework, a semantic statement is first sampled from a prior, such as from a set of beliefs in a knowledge base. Given this semantic statement, a grammar probabilistically generates the output sentence. A joint semantic-syntactic parser is derived that returns the $k$-best semantic and syntactic parses for a given sentence. The semantic prior is flexible, and can be used to incorporate background knowledge during parsing, in ways unlike previous semantic parsing approaches. For example, semantic statements corresponding to beliefs in a knowledge base can be given higher prior probability, type-correct statements can be given somewhat lower probability, and beliefs outside the knowledge base can be given lower probability. The construction of our grammar invokes a novel application of hierarchical Dirichlet processes (HDPs), which in turn, requires a novel and efficient inference approach. We present experimental results showing, for a simple grammar, that our parser outperforms a state-of-the-art CCG semantic parser and scales to knowledge bases with millions of beliefs.

§ INTRODUCTION

Accurate and efficient semantic parsing is a long-standing goal in natural language processing. There are countless applications for methods that provide deep semantic analyses of sentences. Leveraging semantic information in text may provide improved algorithms for many problems in NLP, such as named entity recognition [19, 20, 28], word sense disambiguation [51, 9], semantic role labeling [36], co-reference resolution [42, 39], etc. A sufficiently expressive semantic parser may directly provide the solutions to many of these problems. Lower-level language processing tasks, such as those mentioned, may even benefit by incorporating semantic information, especially if the task can be solved jointly during semantic parsing.

Knowledge plays a critical role in natural language understanding. The formalisms used by most semantic parsing approaches require an ontology of entities and predicates, with which the semantic content of sentences can be represented. Moreover, even seemingly trivial sentences may have a large number of ambiguous interpretations. Consider the sentence “She started the machine with the GPU,” for example. Without additional knowledge, such as the fact that “machine” can refer to computing devices that contain GPUs, or that computers generally contain devices such as GPUs, the reader cannot determine whether the GPU is part of the machine or if the GPU is a device that is used to start machines.

[remember picture,level distance=0.7cm,auto]
[cloud,draw,cloud puffs=11,cloud puff arc=120,aspect=2,inner ysep=0.06cm,thick] (KB) ;
[right of=KB,node distance=4.6cm,align=center,fill=sand,rounded corners=2pt] (semantics)
[below of=semantics,node distance=1.3cm,fill=lightblue,rounded corners=2pt,draw=black!80,thick,text width=5.4cm,align=center] (grammar) ;
[below of=KB,node distance=2.4cm,fill=lightorange,rounded corners=2pt,draw=black!80,thick] (parser) ;
[below of=grammar,node distance=2.0cm,rounded corners=2pt,fill=sand,text width=5.42cm] (syntax)
edge from parent/.style=draw,edge from parent path=(.south) – +(0,-3pt) -| (),rounded corners=0pt,text width=
[. ; [.(leftNP) ; ]
[. ; [.(V) aaaa; ]
[. ; [.(middleNP) aaaaaa; ]
; [.(P) aa; ]
; [.(rightNP) aaaa; ] ] ] ]

[below of=leftNP,node distance=2.40cm] (She) “She;
[below of=V,node distance=1.70cm] (started) started;
[below of=middleNP] (machine) the machine;
[below of=P] (with) with;
[below of=rightNP] (gpu) the GPU”;

[fit=(She) (started) (machine) (with) (gpu)] (sentence) ;

[below of=leftNP,node distance=2.40cm] (She) “She;
[below of=V,node distance=1.70cm] (started) started;
[below of=middleNP] (machine) the machine;
[below of=P] (with) with;
[below of=rightNP] (gpu) the GPU”;

[dashed,->] (leftNP)–(She);
[dashed,->] (V)–(started);
[dashed,->] (middleNP)–(machine);
[dashed,->] (P)–(with);
[dashed,->] (rightNP)–(gpu);

[draw,-latex,thick] (KB)–(semantics);
[draw,-latex,thick] (semantics)–(grammar);
[draw,-latex,thick] (grammar)–(syntax);
[draw=darkorange,color=darkorange,-latex,rounded corners,thick] (sentence)-|(parser);
(syntaxWest) at (1.78,-2.4);
(semanticsSouthWest) at (1.78,-0.48);
[draw=darkorange,color=darkorange,-latex,thick] (parser)–(syntaxWest);
[draw=darkorange,color=darkorange,-latex,thick] (parser)–(semanticsSouthWest);
[draw=darkorange,color=darkorange,-latex,thick] (KB)–(parser);

High-level illustration of the setting in which our grammar is applied. During parsing, the input is the observed sentence and knowledge base, and we want to find the $k$ most probable semantic-syntactic parses given this input and the training data.

The thesis underlying our research is that natural language understanding requires a belief system; that is, a large set of pre-existing beliefs related to the domain of discourse. Clearly, young children have many beliefs about the world when they learn language, and in fact, the process of learning language is largely one of learning to ground the meanings of words and sentences in these non-linguistically acquired beliefs. In some ways, the idea that language understanding requires a belief system is not new, as natural language researchers have been saying for years that background knowledge is essential to reducing ambiguity in sentence meanings [8, 4, 18, 1]. But despite this general acknowledgement of the importance of background knowledge, we see very few natural language understanding systems that actually employ a large belief system as the basis for comprehending sentence meanings, and for determining whether the meaning of a new sentence contradicts, extends, or is already present in its belief system.

We present here a step in this direction: a probabilistic semantic parser that uses a large knowledge base (NELL) to form a prior probability distribution on the meanings of sentences it parses, and that "understands" each sentence either by identifying its existing beliefs that correspond to the sentence's meaning, or by creating new beliefs. More precisely, our semantic parser corresponds to a probabilistic generative model that assigns high probability to sentence semantic parses resulting in beliefs it already holds, lower prior probability to parses resulting in beliefs it does not hold but which are consistent with its more abstract knowledge about semantic types of arguments to different relations, and still lower prior probability to parses that contradict its beliefs about which entity types can participate in which relations.

This work is only a first step. It is limited in that we currently use it to parse sentences with a simple noun-verb-noun syntax (e.g. "Horses eat hay."), and considers only factual assertions in declarative sentences. Its importance is that it introduces a novel approach in which the semantic parser (a) prefers sentence semantic parses that yield assertions it already believes, while  (b) still allowing with lower prior probability sentence interpretations that yield new beliefs involving novel words, and (c) even allowing beliefs inconsistent with its background knowledge about semantic typing of different relations. We introduce algorithms for training the probabilistic grammar and producing parses with high posterior probability, given its prior beliefs and a new sentence. We present experimental evidence of the success and tractability of this approach for sentences with simple syntax, and evidence showing that the incorporated belief system, containing millions of beliefs, allows it to outperform state-of-the-art semantic parsers that do not hold such beliefs. Thus, we provide a principled, probabilistic approach to using a current belief system to guide semantic interpretation of new sentences which, in turn, can be used to augment and extend the belief system. We also argue that our approach can be extended to use the document-level context of a sentence as an additional source of background beliefs.

For reasons including but not limited to performance and complexity, most modern parsers operate over tokens, such as words. While this has worked sufficiently well for many applications, this approach assumes that a tokenization preprocessing step produces the correct output. This is nontrivial in many languages, such as Chinese, Thai, Japanese, and Tibetic languages. In addition, a large portion of the English vocabulary is created from the combination of simpler morphemes, such as the words “build-er,” “in-describ-able,” “anti-modern-ist.” Moreover, language can be very noisy. Text messages, communication in social media, and real-world speech are but a few examples of noise obfuscating language. Standard algorithms for tokenization, lemmatization, and other preprocessing are oblivious to the underlying semantics, much less any background knowledge. Incorporating these components into a “joint parsing” framework will enable semantics and background knowledge to jointly inform lower-level processing of language. Our method couples semantics with syntax and other lower-level aspects of language, and can be guided by background knowledge via the semantic prior. We will demonstrate how this can be leveraged in our framework to model the morphology of individual verbs in a temporally-scoped relation extraction task.

Semantic statements are the logical expressions that represent meaning in sentences. For example, the semantic statement turn_on_device(person:Ada, device:gpu_cluster) may be used to express the meaning of the sentence example given earlier. There are many languages or semantic formalisms that can be used to encode these logical forms: first-order logic with lambda calculus [13], frame semantics [5], abstract meaning representation [6], dependency-based compositional semantics [35], vector-space semantics [48, 53], for example. Our approach is flexible and does not require the use of a specific semantic formalism.

In section <ref>, we review HDPs and describe the setting that we require to define our grammar. We present our approach in section <ref> to perform HDP inference in this new setting. In section <ref>, we present the main generative process in our framework, and detail our application of the HDP. Although we present our model from a generative perspective, we show in the description of the framework that discriminative techniques can be integrated. Inference in our model is described in section <ref>. There, we present a chart-driven agenda parser that can leverage the semantic prior to guide its search. Finally, in section <ref>, we evaluate our parser on two relation-extraction tasks: the first is a task to extract simple predicate-argument representations from SVO sentences, and the second is a temporally-scoped relation extraction task that demonstrates our parser's ability to model the morphology of individual words, leading to improved generalization performance over words. Moreover, we demonstrate that the inclusion of background knowledge from a knowledge base improves parsing performance on these tasks. The key contributions of this article are:

* a framework to define grammars with coupled semantics, syntax, morphology, etc.,

* the use of a prior on the semantic statement to incorporate prior knowledge,

* and an efficient and exact $k$-best parsing algorithm guided by a belief system.

§ BACKGROUND

Our model is an extension of context-free grammars (CFGs) [12] that couples syntax and semantics. To generate a sentence in our framework, the semantic statement is first drawn from a prior. A grammar then recursively constructs a syntax tree top-down, randomly selecting production rules from distributions that depend on the semantic statement. We present a particular incarnation of a grammar in this framework, where hierarchical Dirichlet processes (HDPs) [52] are used to select production rules randomly. The application of HDPs in our setting is novel, requiring a new inference technique.

The use of the term “generative” does not refer to the Chomskian tradition of generative grammar [11], although our approach does fall broadly within that framework. Rather, it refers to the fact that our model posits a probabilistic mechanism by which sentences are generated (by the speaker). Performing probabilistic inference under this model yields a parsing algorithm (the listener). This generative approach to modeling grammar underscores the duality between language generation and language understanding.

Our grammar can be related to synchronous CFGs (SCFGs) [2], which have been extended to perform semantic parsing [34, 55, 54]. However, in established use, SCFGs describe the generation of the syntactic and semantic components of sentences simultaneously, which makes the assumption that the induced probability distributions of the semantic and syntactic components factorize in a “parallel” manner. Our model instead describes the generation of the semantic component as a step with occurs prior to the syntactic component. This can be captured in SCFGs as a prior on the semantic start symbol, making no factorization assumptions on this prior. This is particularly useful when employing richer prior distributions on the semantics, such as a model of context or a knowledge base.

Adaptor grammars [27] provide a framework that can jointly model the syntactic structure of sentences in addition to the morphologies of individual words [26]. Unlike previous work with adaptor grammars, our method couples syntax with semantics, and can be guided by background knowledge via the semantic prior. We will demonstrate how this can be leveraged in our framework to model the morphology of individual verbs in a temporally-scoped relation extraction task. Cohen10 show how to perform dependency grammar induction using adaptor grammars. While grammar induction in our framework constitutes an interesting research problem, we do not address it in this work.

As in other parsing approaches, an equivalence can be drawn between our parsing problem and the problem of finding shortest paths in hypergraphs [30, 31, 40, 41, 21]. Our algorithm can then be understood as an application of $\textrm{A}^*$ search for the $k$-best paths in a very large hypergraph.

Our parser incorporates prior knowledge to guide its search, such as from an ontology and the set of beliefs in a knowledge base. Using this kind of approach, the parser can be biased to find context-appropriate interpretations in otherwise ambiguous or terse utterances. While systems such as DurrettK14, , KimMoldovan1995, and Salloum09 use background knowledge about the semantic types of different noun phrases to improve their ability to perform entity linking, co-reference resolution, prepositional phrase attachment, information extraction, and question answering, and systems such as RatinovR12, DurrettK14, and ProkofyevTLVDC15 link noun phrases to Wikipedia entries to improve their ability to resolve co-references, these uses of background knowledge remain fragmentary. Krishnamurthy2014 developed a CCG parser that incorporates background knowledge from a knowledge base during training through distant supervision, but their method is not able to do so during parsing. Our parser can be trained once, and then applied to a variety of settings, each with a different context or semantic prior.

§ HIERARCHICAL DIRICHLET PROCESSES

A core component of our statistical model is the Dirichlet process (DP) [17], which can be understood as a distribution over probability distributions. If a distribution $G$ is drawn from a DP, we can write $G\sim \text{DP}(\alpha,H)$, where the DP is characterized by two parameters: a concentration parameter $\alpha>0$ and a base distribution $H$. The DP has the useful property that $\mathbb{E}[G] = H$, and the concentration parameter $\alpha$ describes the “closeness” of $G$ to the base distribution $H$. In typical use, a number of parameters $\theta_i$ are drawn from a discrete distribution $G$, which is itself drawn from a Dirichlet process. The observations $y_i$ are drawn using the parameters $\theta_i$ from another distribution $F$. This may be written as:

\begin{align}
G &\sim \text{DP}(\alpha, H), \\
\theta_1,\dots,\theta_n &\sim G, \\
y_i &\sim F(\theta_i),
\end{align}

for $i=1,\hdots,n$. In our application, we will define $H$ to be a finite Dirichlet distribution and $F$ is a categorical distribution. $G$ can be marginalized out in the model above, resulting in the Chinese restaurant process representation [3]:

\begin{align}
\phi_1, \phi_2, \dots &\sim H, \\
z_i &=
\begin{cases}
j & \text{with probability } \frac{\#\{k < i : z_k = j\}}{\alpha + i - 1}, \\
j^{new} & \text{with probability } \frac{\alpha}{\alpha + i - 1},
\end{cases} \\
\theta_i &= \phi_{z_i} \text{ for } i = 1, \dots, n, \\
y_i &\sim F(\theta_i),
\end{align}

where $z_1 = 1$, $j^{new} = \max\{z_1,\dots,z_{i-1}\} + 1$ is the indicator of a new table, and the quantity $\#\{k < i : z_k = j\}$ is the number of observations that were assigned to table $j$. The analogy is to imagine a restaurant where customers enter one at a time. Each customer chooses to sit at table $j$ with probability proportional to the number of people currently sitting at table $j$, or at a new table $j^{new}$ with probability proportional to $\alpha$. The $i^{th}$ customer's choice is represented as $z_i$. As shown in later sections, this representation of the DP is amenable to inference using Markov chain Monte Carlo (MCMC) methods [22, 46].

The hierarchical Dirichlet process (HDP) is an extension of the Dirichlet process for use in hierarchical modeling [52]. An advantage of this approach is that statistical strength can be shared across nodes that belong to the same subtree. In an HDP, every node $\textbf{n}$ in a fixed tree $T$ is associated with a distribution $G^\textbf{n}$, and:

\begin{align}
G^\textbf{0} &\sim \text{DP}(\alpha^{\textbf{0}}, H), \\
G^\textbf{n} &\sim \text{DP}(\alpha^{\textbf{n}}, G^{\pi(\textbf{n})}),
\end{align}

where $\pi(\textbf{n})$ is the parent node of $\textbf{n}$, and $\textbf{0}$ is the root of $T$. In our application, the base distribution at the root $H$ is Dirichlet. We can draw observations $y_1,\hdots,y_n$ from the HDP, given a sequence $x_1,\hdots,x_n$ of $n$ paths from the root $\textbf{0}$ to a leaf:

\begin{align}
\theta_i &\sim G^{x_i}, \\
y_i &\sim F(\theta_i),
\end{align}

for $i=1,\hdots,n$. For notational brevity, we write this equivalently as $y_i\sim\text{HDP}(x_i,T)$.

Just as marginalizing the Dirichlet process yields the Chinese restaurant process, marginalizing the HDP yields the Chinese restaurant franchise (CRF). For every node in the HDP tree $\textbf{n} \in T$, there is a “Chinese restaurant” consisting of an infinite number of tables. Every table $i$ in this restaurant at node $\textbf{n}$ is assigned to a table in the parent restaurant. The assignment variable $z_i^\textbf{n}$ is the index of the parent table to which table $i$ in node $\textbf{n}$ is assigned.

\begin{align}
\phi_1^\textbf{0}, \phi_2^\textbf{0}, \dots &\sim H, \\
\text{ for every node } \textbf{n} \in T, \hspace{0.5cm} z_i^\textbf{n} &=
\begin{cases}
j & \text{with probability } \propto n^{\pi(\textbf{n})}_j, \\
j^{new} & \text{with probability } \propto \alpha^{\pi(\textbf{n})},
\end{cases} \\
\phi_i^\textbf{n} &= \phi_{z_i^\textbf{n}}^{\pi(\textbf{n})},
\end{align}

where $\pi(\textbf{n})$ is the parent of node $\textbf{n}$, and $n^{\pi(\textbf{n})}_j$ is the current number of customers at node $\pi(\textbf{n})$ sitting at table $j$. We are mildly abusing notation here, since $n^{\pi(\textbf{n})}_j$ and $n^{\pi(\textbf{n})}$ refer to the number of customers at the time $z_i^\textbf{n}$ is drawn (which increases as additional $z_i^\textbf{n}$ are drawn). To draw the observation $y_i$, we start with the leaf node at the end of the path $x_i$:

\begin{align}
\theta_i &= \phi^{x_i}_k, \\
y_i &\sim F(\theta_i),
\end{align}

where $k - 1 = \#\{j < i : x_j = x_i\}$ is the number of previous observations drawn from node $x_i$.

§.§ Inference

In this section, we describe our method for performing posterior inference in the HDP. Let $\bm{z} = \{z^\textbf{n}_i : \textbf{n} \in T, i = 1,2,\hdots\}$ be the set of table assignment variables in the HDP. If the distributions $H$ and $F$ are conditionally conjugate, as they are in our application, the $\bm{\phi}$ variables can be integrated out in closed form:

\begin{equation}
p(\bm{z}|\bm{x},\bm{y}) = p(\bm{x}) p(\bm{z}) \int p(\bm{y}|\bm{x},\bm{z},\bm{\phi}) d\bm{\phi}.
\end{equation}

The posterior $p(\bm{z}|\bm{x},\bm{y})$ is intractable to compute exactly, and so we approximate it by sampling. We obtain samples from $\bm{z}|\bm{x},\bm{y}$ by performing collapsed Gibbs sampling as described in section 5.1 of journals/jasa/Teh06: we repeatedly sample $\bm{z}$ from its conditional distribution, with $\bm{\phi}$ integrated out:

\begin{equation}
z^\textbf{n}_i | \bm{x}, \bm{y}, z^\textbf{n}_{-i} =
\begin{cases}
j &\text{with prob.} \propto \#\{k\ne i : z^\textbf{n}_k = j\} \cdot p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, z^\textbf{n}_i = j), \\
j^{new} &\text{with prob.} \propto \alpha^\textbf{n} \cdot p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, z^\textbf{n}_i = j^{new}),
\end{cases} \label{eq:z_sample}
\end{equation}

where $y^\textbf{n}_i$ is the set of “descendant” observations of table $i$ in node $\textbf{n}$ (this includes observations assigned directly to the table, in addition to those assigned to tables further down in the hierarchy which themselves are assigned to this table), $y^\textbf{n}_{-i} = \bm{y} \setminus y^\textbf{n}_i$ is the set of all other observations, and $z^\textbf{n}_{-i} = \bm{z} \setminus z^\textbf{n}_i$ is the set of all other table assignment variables. Computing $p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, z^\textbf{n}_i = j)$ is straightforward since we can follow the chain of table assignments to the root. Let $r^\textbf{n}_i$ be the root cluster assignment of the table $i$ at node $\textbf{n}$. In fact, we found it advantageous for performance to keep track of the root cluster assignments $\bm{r}$ for every table in the hierarchy. Thus, when $z^\textbf{n}_i = j$, it must be the case that $y^\textbf{n}_i$ were drawn from $F$ with parameter $\phi^\textbf{0}_{r^{\pi(\textbf{n})}_j}$.

Computing $p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, z^\textbf{n}_i = j^{new})$ requires marginalizing over the assignment of the new table $z^{\pi(\textbf{n})}_{j^{new}}$:

\begin{align}
p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, z^\textbf{n}_i = j^{new}) = &\sum_{k=1}^{m^{\pi(\textbf{n})}} \frac{n_k^{\pi(\textbf{n})}}{n^{\pi(\textbf{n})} + \alpha^{\pi(\textbf{n})}} p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, z^{\pi(\textbf{n})}_{j^{new}} = k) \nonumber \\
&+ \frac{\alpha^{\pi(\textbf{n})}}{n^{\pi(\textbf{n})} + \alpha^{\pi(\textbf{n})}} p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, z^{\pi(\textbf{n})}_{j^{new}} = k^{new}),
\end{align}

where $m^{\pi(\textbf{n})}$ is the number of occupied tables at the node $\pi(\textbf{n})$. At the root node $\pi(\textbf{n}) = \textbf{0}$, the above probability is just the prior of $y^\textbf{n}_i$. We observe that the above probabilities are linear functions of the likelihoods $p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, r^\textbf{n}_i = k)$ for various root cluster assignments $r^\textbf{n}_i = k$. Implemented naively, generating a single sample from equation <ref> can take time linear in the number of clusters at the root, which would result in a quadratic-time algorithm for a single Gibbs iteration over all $\bm{z}$. However, we can exploit sparsity in the root cluster assignment likelihoods to improve performance. When $H = \text{Dir}(\beta)$ is a Dirichlet distribution and $F$ is a categorical, then the collapsed root cluster assignment likelihood is:

\begin{equation}
p(y^\textbf{n}_i | \bm{x}, y^\textbf{n}_{-i}, z^\textbf{n}_{-i}, r^\textbf{n}_i = k) = \frac{\prod_t \left( \beta_t + \#\{t \in y^\textbf{0}_k\} \right)^{(\#\{t \in y^\textbf{n}_i\})}}{\left(\sum_t \beta_t + \# y^\textbf{0}_k \right)^{(\# y^\textbf{n}_i)}}.
\end{equation}

Here, $a^{(b)}$ is the rising factorial $a(a + 1)(a + 2)\hdots(a + b - 1) = \frac{\Gamma(a + b)}{\Gamma(a)}$, and $\#\{t \in y^\textbf{n}_i\}$ is the number of elements in $y^\textbf{n}_i$ with value $t$. Notice that the denominator depends only on the sizes and not on the contents of $y^\textbf{n}_i$ and $y^\textbf{0}_k$. Caching the denominator values for common sizes of $y^\textbf{n}_i$ and $y^\textbf{0}_k$ can allow the sampler to avoid needless recomputation. This is especially useful in our application since many of the tables at the root tend to be small. Similarly, observe that the numerator factor is $1$ for values of $t$ where $\#\{t \in y^\textbf{n}_i\} = 0$. Thus, the time required to compute the above probability is linear in the number of unique elements of $y^\textbf{n}_i$, which can improve the scalability of our sampler. We perform the above computations in log space to avoid numerical overflow.

§.§.§ Computing probabilities of paths

In previous uses of the HDP, the paths $x_i$ are assumed to be fixed. For instance, in document modeling, the paths correspond to documents or predefined categories of documents. In our application, however, the paths may be random. In fact, we will later show that our parser heavily relies on the posterior predictive distribution over paths, where the paths correspond to semantic parses. More precisely, given a collection of training observations $\bm{y} = \{y_1,\hdots,y_n\}$ with their paths $\bm{x} = \{x_1,\hdots,x_n\}$, we want to compute the probability of a new path $x^{new}$ given a new observation $y^{new}$:

\begin{align}
p(x^{new}|y^{new},\bm{x},\bm{y}) &\propto p(x^{new}) \int p(y^{new}|\bm{z},x^{new}) p(\bm{z}|\bm{x},\bm{y}) d\bm{z}, \label{eq:hdp_predictive} \\
&\approx \frac{p(x^{new})}{N_{samples}} \sum_{\bm{z}^* \sim \bm{z}|\bm{x},\bm{y}} p(y^{new}|\bm{z}^*,x^{new}). \label{eq:hdp_approx_predictive}
\end{align}

Once we have the posterior samples $\bm{z}^*$, we can compute the quantity $p(y^{new}|\bm{z}^*,x^{new})$ by marginalizing over the table assignment for the new observation $y$:

\begin{align}
p(y^{new}|\bm{z}^*,x^{new}) = &\sum_{j=1}^{m^{x^{new}}} \frac{n_j^{x^{new}}}{n^{x^{new}} + \alpha^{x^{new}}} \hspace{0.1cm} p(y^{new} | \bm{z}^*, \theta^{new} = \phi^{x^{new}}_j) \nonumber \\
&+ \frac{\alpha^{x^{new}}}{n^{x^{new}} + \alpha^{x^{new}}} \hspace{0.1cm} p(y^{new} | \bm{z}^*, \theta^{new} = \phi^{x^{new}}_{j^{new}}).
\end{align}

Here, $m^{x^{new}}$ is the number of occupied tables at node $x^{new}$, $n^{x^{new}}_j$ is the number of customers sitting at table $j$ at node $x^{new}$, and $n^{x^{new}}$ is the total number of customers at node $x^{new}$. The first term $p(y^{new} | \bm{z}^*, \theta^{new} = \phi^{x^{new}}_j)$ can be computed since the $j^{th}$ table exists and is assigned to a table in its parent node, which in turn is assigned to a table in its parent node, and so on. We can follow the chain of table assignments to the root. In the second term, the observation is assigned to a new table, whose assignment is unknown, and so we marginalize again over the assignment in the parent node for this new table:

\begin{align}
p(y^{new} | \bm{z}^*, \theta^{new} = \phi^{x^{new}}_{j^{new}}) = &\sum_{j=1}^{m^{\pi(x^{new})}} \frac{n_j^{\pi(x^{new})}}{n^{\pi(x^{new})} + \alpha^{\pi(x^{new})}} \hspace{0.2cm} p\left(y^{new} \Big| \bm{z}^*, \theta^{new} = \phi_j^{\pi(x^{new})}\right) \nonumber \\
&+ \frac{\alpha^{\pi(x^{new})}}{n^{\pi(x^{new})} + \alpha^{\pi(x^{new})}} \hspace{0.2cm} p\left(y^{new} \Big| \bm{z}^*, \theta^{new} = \phi_{j^{new}}^{\pi(x^{new})}\right),
\end{align}

where $\pi(x^{new})$ is the parent node of $x^{new}$. Again, the probability in the first term can be computed as before, but the probability in the second term depends on the assignment of the new table, which is unknown. Thus, since it is possible that a new table will be created at every level in the hierarchy up to the root, we can apply this formula recursively. At the root $\textbf{0}$, the probability $p(y^{new} | \bm{z}^*, \theta^{new} = \phi_{j^{new}}^\textbf{0})$ is just the prior probability of $y^{new}$.

If the tree $T$ is small, it is straightforward to compute the quantity in equation <ref> for every path $x^{new}$ in the tree, using the method described above. In our application however, the size of $T$ depends on the size of the ontology, and may easily become very large. In this case, the naïve approach becomes computationally infeasible. As such, we develop an algorithm to incrementally find the $k$ best paths that maximize the quantity in equation <ref>. For sparse distributions, where most of the probability mass is concentrated in a small number of paths $x^{new}$, this algorithm can effectively characterize the predictive distribution in equation <ref>. The algorithm is essentially a search over nodes in the tree, starting at the root and descending the nodes of the tree $T$, guided through paths of high probability. Each search state $\texttt{s}$ consists of the following fields:

* $\texttt{s.n}$ is the current position of the search in the tree.

* $\texttt{s.v}$ is an array of probability scores of length $N_{samples}$. Each element in this array represents the probability of drawing the observation $y^{new}$ from the current node $\texttt{s.n}$, and thus is identical to the probability of assigning $y^{new}$ to a new table at any child node of $\texttt{s.n}$. This is useful to compute the quantity in equation <ref> using the recursive method as described above.

The search is outlined in algorithm <ref>. We observe that the quantity in equation <ref> is a sum of independent functions, each being a linear combination of the terms $p(y^{new}|\bm{z}^*_i,\theta^{new} = \phi_j^\textbf{n})$ over the tables available at node $\textbf{n}$ and the new table $p(y^{new}|\bm{z}^*_i,\theta^{new} = \phi_{j^{new}}^\textbf{n})$ (this latter probability is stored in $\texttt{s.v}_i$). Thus, the upper bound on equation <ref> over all paths that pass through node $\texttt{s.n}$ is:

\begin{equation}
\max_{\{x^{new}:\texttt{s.n} \in x^{new}\}} \frac{p(x^{new})}{N_{samples}} \sum_{i=1}^{N_{samples}} \max_{j=1,\hdots,m^\texttt{s.n}} \left\{ p(y^{new}|\bm{z}^*_i,\theta^{new}=\phi_j^\texttt{s.n}) , \texttt{s.v}_i \right\}. \label{eq:hdp_path_key}
\end{equation}

We sort elements in the priority queue using this expression.

IfElseIfElseif elifelse

initialize priority queue with initial state $\texttt{s}$
$\texttt{s.n} \leftarrow \textbf{0}$  *[h]start at the root
$\normalfont i=1,\hdots,N_{samples},$
$\texttt{s.v}_i \leftarrow \sum_{j=1}^{m^\textbf{0}} \frac{n_j^\textbf{0}}{n^\textbf{0} + \alpha^\textbf{0}} p(y^{new}|\bm{z}^*_i, \theta^{new} = \phi_j^\textbf{0}) + \frac{\alpha^\textbf{0}}{n^\textbf{0} + \alpha^\textbf{0}} p(y^{new} | \bm{z}^*_i, \theta^{new} = \phi^\textbf{0}_{j^{new}})$

there are $k$ completed paths
pop state  from the priority queue
$\normalfont\texttt{s.n}$ is a leaf
complete the path  with probability $\frac{p\{x^{new} = \texttt{s.n}\}}{N_{samples}} \sum_{i=1}^{N_{samples}} \texttt{s.v}_i$

child node $\normalfont\textbf{c}$ of $\normalfont\texttt{s.n}$,
create new search state $\texttt{s}^*$
$\texttt{s}^*\texttt{.n} \leftarrow \textbf{c}$
$\normalfont i=1,\hdots,N_{samples},$
$\texttt{s}^*\texttt{.v}_i \leftarrow \sum_{j=1}^{m^\textbf{c}} \frac{n_j^\textbf{c}}{n^\textbf{c} + \alpha^\textbf{c}} p(y^{new}|\bm{z}^*_i, \theta^{new} = \phi_j^\textbf{c}) + \frac{\alpha^\textbf{c}}{n^\textbf{c} + \alpha^\textbf{c}} \texttt{s.v}_i$

push $\texttt{s}^*$ onto priority queue with key in equation <ref>

Search algorithm to find the $k$ best paths in the HDP that maximize the quantity in equation <ref>.
As a result, once the algorithm has completed $k$ items, we are guaranteed that the search has found $k$ best paths. Thus, an “iterator” data structure can be efficiently implemented using this algorithm, which returns paths $x^{new}$ in order of decreasing predictive probability, with the first item being optimal. The search algorithm can be modified for other representations of the HDP, and can be extended to the case where $H$ and $F$ are not conjugate. It may also be incorporated into a larger inference procedure to jointly infer the paths $\bm{x}$ and the latent variables in the HDP. It is also straightforward to compute predictive probabilities where the path $x^{new}$ is restricted to a subset of paths $X$: $p(x^{new}|y^{new},\bm{x},\bm{y},x^{new} \in X)$. To do so, the algorithm is restricted to only expand nodes that belong to paths in $X$.

An important concern when performing inference with very large trees $T$ is that it is not feasible to explicitly store every node in memory. Fortunately, collapsed Gibbs sampling does not require storing nodes whose descendants have zero observations. In addition, algorithm <ref> can be augmented to avoid storing these nodes, as well. To do so, we make the observation that for any node $\textbf{n} \in T$ in the tree whose descendants have no observations, $\textbf{n}$ will have zero occupied tables. Therefore, the probability $p(y^{new}|\bm{z}^*,x^{new}) = p(y^{new}|\bm{z}^*,\theta^{new}=\phi^\textbf{n}_{j^{new}})$ is identical for any path $x^{new}$ that passes through $\textbf{n}$. Thus, when the search reaches node $\textbf{n}$, it can simultaneously complete all paths $x^{new}$ that pass through $\textbf{n}$, and avoid expanding nodes with zero observations among its descendants. As a result, we only need to explicitly store a number of nodes linear in the size of the training data, which enables practical inference with very large hierarchies.

There is a caveat that arises when we wish to compute a joint predictive probability $p(x^{new}_1, \hdots, x^{new}_k | y^{new}_1, \hdots, y^{new}_k, \bm{x}, \bm{y})$, where we have multiple novel observations. Re-writing equation <ref> in this setting, we have:

\begin{align}
p(x^{new}_1, \hdots, x^{new}_k &| y^{new}_1, \hdots, y^{new}_k, \bm{x}, \bm{y}) \nonumber \\
&\propto p(\bm{x}^{new}) \int p(y^{new}_1,\hdots,y^{new}_k|\bm{z}^*,\bm{x}^{new}) p(\bm{z}|\bm{x},\bm{y})d\bm{z}. \label{eq:hdp_joint_predictive}
\end{align}

For the CRF, the joint likelihood $p(y^{new}_1,\hdots,y^{new}_k|\bm{z}^*,\bm{x}^{new})$ does not factorize, since the observations are not independent (they are exchangeable). One workaround is to use a representation of the HDP where the joint likelihood factorizes, such as the direct assignment representation [52]. Another approach is to approximate the joint likelihood with the factorized likelihood. In our parser, we instead make the following approximation:

\begin{align}
p(y^{new}_1,\hdots,y^{new}_k | \bm{x}^{new},\bm{x},\bm{y}) &= \prod_{i=1}^k p(y^{new}_i | y^{new}_1,\hdots,y^{new}_{i-1}, \bm{x}^{new},\bm{x},\bm{y}) \\
&\approx \prod_{i=1}^k p(y^{new}_i | \bm{x}^{new},\bm{x},\bm{y}). \label{eq:hdp_approximation}
\end{align}

Substituting into equation <ref>, we obtain:

\begin{equation}
p(\bm{x}^{new} | \bm{y}^{new}, \bm{x}, \bm{y}) \propto p(\bm{x}^{new}) \prod_{i=1}^k \int p(y^{new}_i|\bm{z}^*,\bm{x}^{new}) p(\bm{z}|\bm{x},\bm{y})d\bm{z}.
\end{equation}

When the size of the training data $(\bm{x},\bm{y})$ is large with respect to the test data $(\bm{x}^{new},\bm{y}^{new})$, the approximation works well, which we also find to be the case in our experiments.

§ GENERATIVE SEMANTIC GRAMMAR

We present a generative model of text sentences. In this model, semantic statements are generated probabilistically from some higher-order process. Given each semantic statement, a formal grammar selects text phrases, which are concatenated to form the output sentence. We present the model such that it remains flexible with regard to the semantic formalism. Even though our grammar can be viewed as an extension of context-free grammars, it is important to note that our model of grammar is only conditionally context-free, given the semantic statement. Otherwise, if the semantic information is marginalized out, the grammar is sensitive to context.

§.§ Definition

Let $\mathcal{N}$ be a set of nonterminals, and let $\mathcal{W}$ be a set of terminals. Let $\bm{R}$ be a set of production rules which can be written in the form $\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_k$ where $\textrm{A}\in\mathcal{N}$ and $\textrm{B}_1,\hdots,\textrm{B}_k\in\mathcal{W}\mspace{2mu}\cup\mspace{2mu}\mathcal{N}$. The tuple $(\mathcal{W},\mathcal{N},\bm{R})$ is a context-free grammar (CFG) [12].

We couple syntax with semantics by augmenting the production rules $\bm{R}$. In every production rule $\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_k$ in $\bm{R}$, we assign to every right-hand side symbol $B_i$ a surjective operation $f_i : \mathcal{X}_A\mapsto\mathcal{X}_{B_i}$ that transforms semantic statements, where $\mathcal{X}_A$ is the set of semantic statements associated with the symbol $\textrm{A}$ and $\mathcal{X}_{B_i}$ is the set of semantic statements associated with the symbol $\textrm{B}_i$. Intuitively, the operation describes how the semantic statement is “passed on” to the child nonterminals in the generative process. During parsing, these operations will describe how simpler semantic statements combine to form larger statements, enabling semantic compositionality. For example, suppose we have a semantic statement $x = \textit{has\_color(reptile:frog,color:green)}$ and the production rule $\textrm{S} \to \textrm{NP}\hspace{0.25cm}\textrm{VP}$. We can pair the semantic operation $f_1$ with the $\textrm{NP}$ in the right-hand side such that $f_1(x) = \textit{reptile:frog}$ selects the subject argument. Similarly, we can pair the semantic operation $f_2$ with the $\textrm{VP}$ in the right-hand side such that $f_2(x) = x$ is the identity operation. The augmented production rule is $(\textrm{A},\textrm{B}_1,\hdots,\textrm{B}_k,f_1,\hdots,f_k)$ and the set of augmented rules is $\bm{R}^*$. In parsing, we require the computation of the inverse of semantic operations, which is the preimage of a given semantic statement $f^{-1}(x) = \{ x' : f(x') = x \}$. Continuing the example above, $f_1^{-1}(\textit{reptile:frog})$ returns a set that contains the statement $\textit{has\_color(reptile:frog,color:green)}$ in addition to statements like $\textit{eats\_insect(reptile:frog,insect:fly)}$.

To complete the definition of our grammar, we need to specify the method that, given a nonterminal $\mathrm{A} \in \mathcal{N}$ and a semantic statement $x \in \mathcal{X}_A$, selects a production rule from the set of rules in $\bm{R}^*$ with the left-hand side nonterminal $A$. To accomplish this, we define $\texttt{select}_{A,x}$ as a distribution over rules from $\bm{R}^*$ that has $\textrm{A}$ as its left-hand side, dependent on $x$. We will later provide a number of example definitions of this $\texttt{select}_{A,x}$ distribution. Thus, a grammar in our framework is fully specified by the tuple $(\mathcal{W},\mathcal{N},\bm{R}^*,\texttt{select})$.

Note that other semantic grammar formalisms can be fit into this framework. For example, in categorical grammars, a lexicon describes the mapping from elementary components of language (such as words) to a syntactic category and a semantic meaning. Rules of inference are available to combine these lexical items into (tree-structured) derivations, eventually resulting in a syntactic and semantic interpretation of the full sentence [49, 25]. In our framework, we imagine this process in reverse. The set $\mathcal{X}_S$ is the set of all derivable semantic statements with syntactic category $S$. The generative process begins by selecting one statement from this set $x \in \mathcal{X}_S$. Next, we consider all applications of the rules of inference that would yield $x$, with each unique application of an inference rule being equivalent to a production rule in our framework. We select one of these production rules according to our generative process and continue recursively. The items in the lexicon are equivalent to preterminal production rules in our framework. Thus, the generative process below describes a way to endow parses in categorical grammar with a probability measure. This can be used, for example, to extend earlier work on generative models with CCG [23, 24]. Different choices of the $\texttt{select}$ distribution induce different probability distributions over parses.

We do not see a straightforward way to fit linear or log-linear models over full parses into our framework, where a vector of features can be computed for each full parse [7, 45]. This is due to our assumption that, given the semantic statement, the probability of a parse factorizes over the production rules used to construct that parse. However, the  distribution can be defined using linear and log-linear models, as we will describe in section <ref>.

§.§ Generative process

The process for generating sentences in this framework begins by drawing a semantic statement $x\in\mathcal{X}_S$ where $\textrm{S}$ is the root nonterminal. Thus, there is a prior distribution $p(x)$ for all $x\in\mathcal{X}_S$. Next, the syntax is generated top-down starting at $\textrm{S}$. We draw a production rule with $\textrm{S}$ as the left-hand side from $\texttt{select}_{S,x}$. The semantic transformation operations $f_i$ are applied to $x$ and the process is repeated for the right-hand side nonterminals. More concretely, we define the following operation $\texttt{expand}$ which takes two arguments: a symbol $\textrm{A}\in\mathcal{W}\cup\mathcal{N}$ and a semantic statement $x\in\mathcal{X}_A$.

$x$, A
${\rm A}\in\mathcal{W}$
*[h]simply return the word if A is a terminal

*[h]select a production rule with form $\textrm{A}\to \textrm{B}_1,\hdots,\textrm{B}_k$

$(\textrm{A}, \textrm{B}_1, \hdots, \textrm{B}_k, f_1, \hdots, f_k) \sim \FSelect_{\textrm{A},x}$
$\FYield(\FExpand(f_1(x), \textrm{B}_1), \hdots, \FExpand(f_k(x), \textrm{B}_k))$

The  operation concatenates strings into a single output string. Then, the output sentence $y$ is generated simply by $y=\texttt{expand}(x, \textrm{S})$. Depending on the application, we may require that the generative process capitalizes the first letter of the output sentence, and/or appends terminating punctuation to the end. A noise model may also be appended to the generative process. The above algorithm may be easily extended to also return the full syntax tree.

§.§ Selecting production rules

There are many possible choices for the $\texttt{select}$ distribution. The most straightforward is to define a categorical distribution over the available production rules, and simply draw the selected rule from this distribution. The result would be a simple extension of probabilistic context-free grammars (PCFGs) that couples semantics with syntax. However, this would remove any dependence between the semantic statement and the production rule selection.

To illustrate the importance of this dependence, consider generating a sentence with the semantic statement athlete_plays_sport(athlete:roger_federer,sport:tennis) using the grammar in figure <ref> (the process is graphically depicted in figure <ref>). We start with the root nonterminal $\textrm{S}$:

* We can only select the first production rule, and so we apply the semantic operation  on the semantic statement to obtain athlete:roger_federer for the right-hand side nonterminal $\textrm{N}$. We apply the semantic operation  to obtain athlete_plays_sport($\cdot$,sport:tennis) for $\textrm{VP}$.

* Expanding $\textrm{N}$, we  a terminal symbol given the semantic statement athlete:roger_federer. Suppose “Andre Agassi” is returned.

*  Now, we expand the $\textrm{VP}$ symbol. We draw from $\texttt{select}_{\textrm{VP}}$ to choose one of the two available production rules. Suppose the rule $\textrm{VP} \to \textrm{V \hspace{0.1cm} N}$ is selected. Thus, we apply the  operation for the $\textrm{V}$ nonterminal to obtain athlete_plays_sport($\cdot$,sport:tennis). We similarly apply  for the $\textrm{N}$ nonterminal to obtain sport:tennis.

* We expand the $\textrm{V}$ nonterminal, drawing from $\texttt{select}_{\textrm{V}}$ on the semantic statement athlete_plays_sport($\cdot$,sport:tennis). Suppose “plays” is returned.

* Finally, we expand the $\textrm{N}$ nonterminal, drawing from $\texttt{select}_{\textrm{N}}$ with the statement sport:tennis. Suppose “tennis” is returned. We concatenate all returned strings to form the sentence “Andre Agassi plays tennis.”

S $\to$ N :   VP :       N $\to$ “tennis”

VP $\to$ V :   N :      N $\to$ “Andre Agassi”

VP $\to$ V :      N $\to$ “Chopin”

V $\to$ “swims”

V $\to$ “plays”

Example of a grammar in our framework. This grammar operates on semantic statements of the form predicate(first argument, second argument). The semantic operation  returns the first argument of the semantic statement. Likewise, the operation  returns the second argument. The operation  removes the first argument, and  returns the semantic statement with no change.

nonterminal=[circle,draw,fill=lightgrey,inner sep=0,minimum size=0.7cm,thick]

step 0:

[level/.style=sibling distance=20mm/#1,level distance=1cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (S) ;
[below of=S,node distance=1.3cm,text width=3.6cm] athlete_plays_sport(

step 1:

[level/.style=sibling distance=35mm/#1,level distance=1.4cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (S)
child[edge from parent/.style=draw,-latex] node[nonterminal] (N)
child[edge from parent/.style=draw,-latex] node[nonterminal] (VP) ;
[below of=N,node distance=0.8cm,align=center,text width=3.6cm] athlete:roger_federer;
[below of=VP,align=center,text width=3.6cm] athlete_plays_sport(
$\cdot$, sport:tennis);

step 2:

[level/.style=sibling distance=30mm/#1,level distance=1.4cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (S)
child node[nonterminal] (N)
child[edge from parent/.style=draw,-latex] node (roger_federer) “Roger Federer”

child node[nonterminal] (VP) ;
[below of=VP,align=center,text width=3.6cm] athlete_plays_sport(
$\cdot$, sport:tennis);

step 3:

[level/.style=sibling distance=35mm/#1,level distance=1.4cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (S)
child node[nonterminal] (N)
child node (roger_federer) “Roger Federer”

child node[nonterminal] (VP)
child[sibling distance=28mm,edge from parent/.style=draw,-latex] node[nonterminal] (V)
child[sibling distance=28mm,edge from parent/.style=draw,-latex] node[nonterminal] (Nobj)
[below of=V,align=center,text width=3.6cm] athlete_plays_sport(
$\cdot$, sport:tennis);
[below of=Nobj,node distance=0.8cm,align=center,text width=3.6cm] sport:tennis;

step 4:

[level/.style=sibling distance=30mm/#1,level distance=1.4cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (S)
child node[nonterminal] (N)
child node (roger_federer) “Roger Federer”

child node[nonterminal] (VP)
child node[nonterminal] (V)
child[edge from parent/.style=draw,-latex] node (plays) “plays”

child node[nonterminal] (Nobj)
[below of=Nobj,node distance=0.8cm,align=center,text width=3.6cm] sport:tennis;

step 5:

[level/.style=sibling distance=30mm/#1,level distance=1.4cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (S)
child node[nonterminal] (N)
child node (roger_federer) “Roger Federer”

child node[nonterminal] (VP)
child node[nonterminal] (V)
child node (plays) “plays”

child node[nonterminal] (Nobj)
child[edge from parent/.style=draw,-latex] node (tennis) “tennis.”

A depiction of the generative process producing a sentence for the semantic statement athlete_plays_sport(athlete:roger_federer,sport:tennis) using the grammar in figure <ref>.

However, now consider generating another sentence with the same grammar for the statement athlete_plays_sport(athlete:roger_federer, sport:swimming). In <ref> of the above process, the  distribution would necessarily have to depend on the semantic statement. In English, the probability of observing a sentence of the form $\textrm{N} \hspace{0.1cm} \textrm{V} \hspace{0.1cm} \textrm{N}$ ('Rachmaninoff makes music') versus $\textrm{N} \hspace{0.1cm} \textrm{V}$ ('Rachmaninoff composes') depends on the underlying semantic statement.

To capture this dependence, we use HDPs to define the  distribution. Every nonterminal $\textrm{A}\in\mathcal{N}$ is associated with an HDP, and in order to fully specify the grammar, we need to specify the structure of each HDP tree. Let $T_A$ be the tree associated with the nonterminal $\textrm{A}$. The model is flexible with how the trees are defined, but we construct trees with the following method. First, select $m$ discrete features $g_1,\hdots,g_m$ where each $g_i : \mathcal{X} \mapsto \mathbb{Z}$ and $\mathbb{Z}$ is the set of integers. These features operate on semantic statements. For example, suppose we restrict the space of semantic statements to be the set of single predicate instances (triples). The relations in an ontology can be assigned unique integer indices, and so we may define a semantic feature as a function which simply returns the index of the predicate given a semantic statement. We construct the HDP tree $T_A$ starting with the root, we add a child node for every possible output of $g_1$. We repeat the process recursively, constructing a complete tree of depth $m + 1$.

As an example, we will construct a tree for the nonterminal $\textrm{VP}$ for the example grammar in figure <ref>. Suppose in our ontology, we have the predicates athlete_plays_sport and musician_plays_instrument, labeled $0$ and $1$, respectively. The ontology also contains the concepts athlete:roger_federer, sport:tennis, and sport:swimming, also labeled $0$, $1$, and $2$, respectively. We define the first feature $g_1$ to return the predicate index. The second feature $g_2$ returns the index of the concept in the second argument of the semantic statement. The tree is constructed starting with the root, we add a child node for each predicate in the ontology: athlete_plays_sport and musician_plays_instrument. Next, for each child node, we add a grandchild node for every concept in the ontology: athlete:roger_federer, sport:tennis, and sport:swimming. The resulting tree $T_{VP}$ has depth $2$, with a root node with $2$ child nodes, and each child node has $3$ grandchild nodes. This construction enables the  distribution for the nonterminal $\textrm{VP}$ to depend on the predicate and the second argument of the semantic statement.

With the fully-specified HDPs and their corresponding trees, we have fully specified . When sampling from $\texttt{select}_{\textrm{A},x}$ for the nonterminal $\textrm{A} \in \mathcal{N}$ and a semantic statement $x \in \mathcal{X}$, we compute the $m$ semantic features for the given semantic statement: $g_1(x), g_2(x), \hdots, g_m(x)$. This sequence of indices specifies a path from the root of the tree down to a leaf. We then simply draw a production rule observation from this leaf node, and return the result: $r \sim \text{HDP}(x, T_A) = \texttt{select}_{\textrm{A},x}$.

There are many other alternatives for defining the  distribution. For instance, a log-linear model can be used to learn dependence on a set of features. The HDP provides statistical advantages, smoothing the learned distributions, resulting in a model more robust to data sparsity issues.

In order to describe inference in this framework, we must define additional concepts and notation. For a nonterminal $\textrm{A}\in\mathcal{N}$, observe that the paths from the root to the leaves of its HDP tree induce a partition on the set of semantic statements $\mathcal{X}_A$. More precisely, two semantic statements $x_1,x_2 \in \mathcal{X}_A$ belong to the same equivalence class if they correspond to the same path in an HDP tree.

nonterminal=[circle,draw,fill=lightgrey,inner sep=0,minimum size=0.7cm,thick]
[level/.style=sibling distance=20mm/#1,level distance=1cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (S)
child node[nonterminal] (NPsbj)
child node[nonterminal] (Nsbj)

child node[nonterminal] (VP)
child node[nonterminal] (V)
child node[nonterminal] (NPobj)
child node[nonterminal] (Nobj)

child[sibling distance=12mm] node[nonterminal] (PP)
child[sibling distance=7mm] node[nonterminal] (P)
child[sibling distance=10mm] node[nonterminal] (Nprep)

[below left of=Nobj] full parse;

[level/.style=sibling distance=20mm/#1,level distance=1cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (S)
child node[nonterminal] (NP)
child node[nonterminal] (N)

child node[nonterminal] (VP)
child node[nonterminal] (V)
child[opacity=0.15] node (NP)
child[opacity=0.15] node (PP)
[below left of=NP] left outer parse;

[level/.style=sibling distance=20mm/#1,level distance=1cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (NP)
child node[nonterminal] (N) ;
[below of=N,text width=1cm,align=center] inner parse;

[level/.style=sibling distance=20mm/#1,level distance=1cm,line width=0.9pt,edge from parent path=() – ()]
[nonterminal] (PP)
child[sibling distance=7mm] node[nonterminal] (P)
child[sibling distance=10mm] node[nonterminal] (N) ;
[below of=N] right outer parse;

An example decomposition of a parse tree into its left outer parse, inner parse (of the object noun phrase), and its right outer parse. This is one example of such a decomposition. For instance, we may similarly produce a decomposition where the prepositional phrase is the inner parse, or where the verb is the inner parse. The terminals are omitted and only the syntactic portion of the parse is displayed here for consiseness.

Every parse $(x, s)$ consists of a semantic statement $x$ and a syntax tree $s$. The syntax tree $s$ is a rooted tree containing an interior vertex for every nonterminal and a leaf for every terminal. Every vertex is associated with a start position and end position in the sentence. An interior vertex along with its immediate children corresponds to a particular production rule in the grammar $(\textrm{A} \to \textrm{B}_1\mathalpha{:}{f_1} \hdots \textrm{B}_n\mathalpha{:}{f_n}) \in \bm{R}^*$, where the interior vertex is associated with the nonterminal $\textrm{A}$ and its children respectively correspond to the symbols $\textrm{B}_1,\hdots,\textrm{B}_n$, left-to-right. Thus, every edge in the tree is labeled with a semantic transformation operation. A subgraph $s_I$ of $s$ can be called an inner syntax tree. The corresponding outer syntax tree $s_O$ is $s_O = s \setminus s_I$ is the syntax tree with $s_I$ deleted. We further draw a distinction between left and right components of an outer syntax tree. Define the left outer syntax tree $s_L$ as the minimal subgraph of $s_O$ containing all subtrees positioned to the left of $s_I$, and containing all ancestor vertices of $s_I$. The right outer syntax tree $s_R$ forms the remainder of the outer parse, and so $s$ can be decomposed into three distinct trees: $s = s_L \cup s_R \cup s_I$. See figure <ref> for an illustration. Note that it is possible that $s_R$ consists of multiple disconnected trees. In the description of our parser, we will frequently use the notation $p(s)$ to refer to the joint probability of all the production rules in the syntax tree $s$; that is, $p(s) = p(\bigcap_{(\textrm{A}\to\beta)\in s} \textrm{A}\to\beta)$, where $\beta$ is the right-hand side of some production rule.

§ INFERENCE

Let $\bm{y} \triangleq \{y_1,\hdots,y_n\}$ be a collection of training sentences, along with their corresponding syntax trees $\bm{s} \triangleq \{s_1,\hdots,s_n\}$ and semantic statement labels $\bm{x} \triangleq \{x_1,\hdots,x_n\}$. Given a new sentence $y^{new}$, the goal of parsing is to compute the probability of its semantic statement $x^{new}$ and syntax $s^{new}$:

\begin{equation}
p(x^{new}, s^{new} | y^{new}, \bm{x}, \bm{s}, \bm{y}) \propto \int p(x^{new}, s^{new}, y^{new} | \bm{\theta}) p(\bm{\theta} | \bm{x}, \bm{s}, \bm{y}) d\bm{\theta}. \label{eq:predictive}
\end{equation}

In this expression, $\bm{\theta}$ are the latent variables in the grammar. Different applications will rely on this probability in different ways. For example, we may be interested in the semantic parse that maximizes this probability. The above integral is intractable to compute exactly, so we use Markov chain Monte Carlo (MCMC) to approximate it:

\begin{equation}
\approx \frac{1}{N_{samples}} \sum_{\bm{\theta}^* \sim \bm{\theta} | \bm{x}, \bm{s}, \bm{y}} p(x^{new}, s^{new}, y^{new} | \bm{\theta}^*), \label{eq:approx_predictive}
\end{equation}

where the sum is taken over samples from the posterior of the latent grammar variables $\bm{\theta}$ given the training data $\bm{x}$, $\bm{s}$, and $\bm{y}$.[We also attempted a variational approach to inference, approximating the integral as $\mathbb{E}_q[p(x^{new}, s^{new}, y^{new} | \bm{\theta})]$, where $q$ was selected to minimize the KL divergence to the posterior $p(\bm{\theta} | \bm{x}, \bm{s}, \bm{y})$. We experimented with a number of variational families, but we found that they were not sufficiently expressive to accurately approximate the posterior for our purposes.]

We make the assumption that the likelihood factorizes over the nonterminals. More precisely:

\begin{equation}
p(y^{new}, s^{new} | x^{new}, \bm{\theta}) = \prod_{A\in\mathcal{N}} p(\{\textrm{A} \to \beta \in s^{new}\} | x^{new}, \theta_A), \label{eq:factor_assumption}
\end{equation}

where $\theta_A$ are the latent variables specific to the nonterminal $\textrm{A}$, and $\{\textrm{A}\to\beta \in s^{new}\}$ is the set of production rules in $s^{new}$ that have $\textrm{A}$ as the left-hand side nonterminal. Thus, we may factorize the joint likelihood as:

\begin{equation}
p(x^{new}, s^{new}, y^{new} | \bm{\theta}) = p(x^{new}) \prod_{\textrm{A}\in\mathcal{N}} p\left(\{\textrm{A}\to\beta \in s^{new}\} | x^{new}, \theta_A\right), \label{eq:likelihood}
\end{equation}

where the first product is over the nonterminals $\textrm{A}\in\mathcal{N}$ in the grammar. Note that the probability $p\left(\textrm{A}\to\beta | x^{new}, \theta_A\right)$ is equivalent to the probability of drawing the rule $\textrm{A}\to\beta$ from $\texttt{select}_{\textrm{A},x^{new}}$ for nonterminal $\textrm{A}$ and semantic statement $x^{new}$. Plugging equation <ref> into <ref> and <ref>, we obtain:

\begin{align}
p(x^{new}, s^{new} &| y^{new}, \bm{x}, \bm{s}, \bm{y}) \nonumber \\
&\propto p(x^{new}) \prod_{\textrm{A}\in\mathcal{N}} \int p\left(\{\textrm{A}\to\beta \in s^{new}\} | x^{new}, \theta_A\right) p(\theta_A | \bm{x}, \bm{s}, \bm{y}) d\theta_A, \label{eq:factored_predictive} \\
&\approx \frac{p(x^{new})}{N_{samples}^{|\mathcal{N}|}} \prod_{\textrm{A}\in\mathcal{N}} \prod_{(\textrm{A}\to\beta)\in s^{new}} \sum_{\theta_A^* \sim \theta_A|\bm{x},\bm{s},\bm{y}} p\left(\textrm{A}\to\beta | x^{new}, \theta_A^*\right), \label{eq:factored_approx_predictive}
\end{align}

where the second product iterates over the production rules that constitute the syntax $s^{new}$. Note that we applied the approximation as described in equation <ref>. The semantic prior $p(x^{new})$ plays a critically important role in our framework. It is through this prior that we can add dependence on background knowledge during parsing. Although we present a setting in which training is supervised with both syntax trees and semantic labels, it is straightforward to apply our model in the setting where we have semantic labels but syntax information is missing. In such a setting, a Gibbs step can be added where the parser is run on the input sentence with the fixed semantic statement, returning a distribution over syntax trees for each sentence.

Now, we divide the problem of inference into two major components:

Inference over HDP paths: Given a set of semantic statements $X\subseteq\mathcal{X}$, incrementally find the $k$ best semantic statements $x \in X$ that maximize the sum $\sum p(\textrm{A} \to \beta | x, \theta_A)$ within equation <ref>. We observe that this quantity only depends on the HDP associated with nonterminal $\textrm{A}$. Note that this is exactly the setting as described in section <ref>, and so we can directly apply algorithm <ref> to implement this component.

Parsing: Efficiently compute the $k$ most likely semantic and syntactic parses $\{x^{new},s^{new}\}$ that maximize $p(x^{new}, s^{new} | y^{new}, \bm{x}, \bm{s}, \bm{y})$ for a given sentence $y^{new}$. We describe this component in greater detail in the next section. This component utilizes the previous component.

§.§ Parsing

We develop a top-down parsing algorithm that computes the $k$-best semantic/syntactic parses $(x^{new},s^{new})$ that maximize $p(x^{new}, s^{new} | y^{new}, \bm{x}, \bm{s}, \bm{y})$ for a given sentence $y^{new}$. We emphasize that this parser is largely independent of the choice of the distribution . The algorithm searches over a space of items called rule states, where each rule state represents the parser's position within a specific production rule of the grammar. Complete rule states represent the parser's position after completing parsing of a rule in the grammar. The algorithm also works with nonterminal structures that represent a completed parse of a nonterminal within the grammar. The parser keeps a priority queue of unvisited rule states called the agenda. A data structure called the chart keeps intermediate results on contiguous portions of the sentence. A predefined set of operations are available to the algorithm. At every iteration of the main loop, the algorithm pops the rule state with the highest weight from the agenda and adds it to the chart, applying any available operation on this state using any intermediate structures in the chart. These operations may add additional rule states to the agenda, with priority given by an upper bound on $\log p(x^{new}, s^{new} | y^{new}, \bm{x}, \bm{s}, \bm{y})$. The overall structure of our parser is reminiscent of the Earley parsing algorithm, which is the classical example of a top-down parsing algorithm for CFGs [16]. We will draw similarities in our description below. The parsing procedure can also be interpreted as an $\textrm{A}^*$ search over a large hypergraph.

Each rule state $\texttt{r}$ is characterized by the following fields:

*  is the production rule currently being parsed.

*  is the (inclusive) sentence position marking the beginning of the production rule.

*  is the (exclusive) sentence position marking the end of the production rule.

*  is the current position in the sentence.

*  is the current position in the production rule. Dotted rule notation is a convenient way to represent the variables  and . For example, if the parser is currently examining the rule $\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_n$ at rule position  (omitting semantic transformation operations), we may write this as $\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_k \bullet \textrm{B}_{k+1} \hdots \textrm{B}_n$ where the dot denotes the current position of the parser.

*  is a set of semantic statements.

*  is a partially completed syntax tree. As an example, if the parser is currently examining rule $\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_n$ at position $\texttt{k}$, the tree will have a root node labeled $\textrm{A}$ with $\texttt{k}$ child subtrees each labeled $\textrm{B}_1$ through $\textrm{B}_k$, respectively.

*  is the inner log probability of the rule up to its current position.

Every complete rule state $\texttt{r}$ contains the above fields in addition to an  field which keeps intermediate state for the inference method described in section <ref> (see description of the iteration operation below for details on how this is used).

Every nonterminal structure $\texttt{n}$ contains the fields:

* , , , , and  are identical to the respective fields in the rule states.

*  is the nonterminal currently being parsed.

The following are the available operations or deductions that the parser can perform while processing rule states:

expansion takes an incomplete rule state $\texttt{r}$ as input. For notational convenience, let $k = \texttt{r.k}$ and $\texttt{r.rule}$ be written as $\textrm{A} \to \textrm{B}_1\hdots \textrm{B}_n$. This operation examines the next right-hand symbol $\textrm{B}_k$. There are two possible cases:

If $\textrm{B}_k$ is a nonterminal: For every production rule in the grammar $\textrm{B}_k \to \beta$ whose left-hand symbol is $\textrm{B}_k$, for every $j \in \{\texttt{r.i}, \hdots, \texttt{r.end}\}$, create a new rule state $\texttt{r}^*$ only if $\textrm{B}_k$ was not previously expanded at this given start and end position:

$\texttt{r}^*\texttt{.rule} = \textrm{B}_k \to \beta,$  $̄^* = ,$ \hspace{0.8cm} \=$\texttt{r}^*\texttt{.end} = j,$

$\texttt{r}^*\texttt{.i} = \texttt{r.i},$ $\texttt{r}^*\texttt{.k} = 0,$ $\texttt{r}^*\texttt{.log\_probability} = 0.$

The semantic statement field of the new state is set to be the set of all semantic statements for the expanded nonterminal: $\texttt{r}^*\texttt{.semantics} = \mathcal{X}_{B_k}$. The syntax tree of the new rule state $\texttt{r}^*\texttt{.syntax}$ is initialized as a single root node. The new rule state is added to the agenda (we address specifics on prioritization later). This operation is analogous to the “prediction” step in Earley parsing.

If $\textrm{B}_k$ is a terminal: Read the terminal $\textrm{B}_k$ in the sentence starting at position $\texttt{r.i}$, then create a new rule state $\texttt{r}^*$ where:

$\texttt{r}^*\texttt{.rule} = \texttt{r.rule},$  $̄^* = ,$ \hspace{1cm} $^* = ,$ \\
$^* =  + |B_k|,$ \>$^* =  + 1,$ \\
$^* = ,$ \\
$^* = .$
\end{tabbing}
The new syntax tree is identical to the old syntax tree with an added child node corresponding to this terminal symbol $B_k$. The new rule state is then added to the agenda. This operation is analogous to the ``scanning'' step in Earley parsing.
\end{description}
\item[\emph{completion}] takes as input an incomplete rule state $$, and a nonterminal structure $$ where $$ matches the next right-hand nonterminal in $$, and where the starting position of the nonterminal structure $$ matches the current sentence position of the rule state $$. For notational convenience, let $$ be written as $A →B_1:f_1 B_n:f_n$. The operation constructs a new rule state $^*$:
\vspace{-\itemsep}
\begin{tabbing}
$\texttt{r}^*\texttt{.rule} = \texttt{r.rule},$ \hspace{1cm} \=$\texttt{r}^*\texttt{.start} = \texttt{r.start},$ \hspace{0.8cm} $\texttt{r}^*\texttt{.end} = \texttt{r.end},$ \\
$\texttt{r}^*\texttt{.i} = \texttt{n.end},$ \>$\texttt{r}^*\texttt{.k} = \texttt{r.k} + 1.$
\end{tabbing}
\vspace{-\itemsep}
To compute the semantic statements of the new rule state, first invert the semantic statements of the nonterminal structure $\texttt{n}$ with the semantic transformation operation ${f^{-1}_k}$, and then intersect the resulting set with the semantic statements of the incomplete rule state: $\texttt{r}^*\texttt{.semantics} = \texttt{r.semantics} \cap \{{f^{-1}_k}(x) : x \in \texttt{n.semantics}\}$. The syntax tree of the new rule state $\texttt{r}^*\texttt{.syntax}$ is the syntax tree of the old incomplete rule state $\texttt{r.syntax}$ with the added subtree of the nonterminal structure $\texttt{n.syntax}$. The log probability of the new rule state is the sum of that of both input states: $\texttt{r}^*\texttt{.log\_probability} = \texttt{r.log\_probability} + \texttt{n.log\_probability}$. The new rule state $\texttt{r}^*$ is then added to the agenda. This operation is analogous to the ``completion'' step in Earley parsing.
\item[\emph{iteration}] takes as input a complete rule state $\texttt{r}$. Having completed parsing the production rule $\texttt{r.rule} = \textrm{A} \to \beta$, we need to compute $\sum_{\theta_A^*} p(\textrm{A} \to \beta | x^{new}, \theta_A^*)$ as in equation \ref{eq:factored_approx_predictive}. To do so, we determine HDP paths in order from highest to lowest posterior predictive probability using the HDP inference approach described in section \ref{section:hdp_inference}. We store our current position in the list as $\texttt{r.iterator}$. This operation increments the iterator and adds the rule state back into the agenda (if the iterator has a successive element). Next, this operation creates a new nonterminal structure $\texttt{n}^*$ where:
\vspace{-\itemsep}
\begin{tabbing}
$\texttt{n}^*\texttt{.nonterminal} = \textrm{A},$ \hspace{1cm} \=$\texttt{n}^*\texttt{.start} = \texttt{r.start},$ \\
$\texttt{n}^*\texttt{.end} = \texttt{r.end},$ \>$\texttt{n}^*\texttt{.syntax} = \texttt{r.syntax}.$
\end{tabbing}
\vspace{-\itemsep}
Recall that the paths in an HDP induce a partition of the set of semantic statements $\mathcal{X}_A$, and so the path returned by the iterator corresponds to a subset of semantic statements $X\subseteq\mathcal{X}_A$. The semantic statements of the nonterminal structure is computed as the intersection of this subset with semantic statements of the rule state: $\texttt{n}^*\texttt{.semantics} = X \cap \texttt{r.semantics}$. The log probability of the new nonterminal structure $\texttt{n}^*\texttt{.log\_probability}$ is the sum of the log probability of the path returned by the iterator and $\texttt{r.log\_probability}$. The new nonterminal structure is added to the chart.
\end{description}

\noindent The algorithm is started by executing the \emph{expansion} operation on all production rules of the form $\textrm{S} \to \beta$ where $\textrm{S}$ is the root nonterminal, starting at position 0 in the sentence, with $\texttt{semantics}$ initialized as the set of all possible semantic statements $\mathcal{X}_S$. To describe the prioritization of agenda items, recall that any complete syntax tree $s$ can be decomposed into inner, left outer, and right outer portions: $s = s_L \cup s_R \cup s_I$. Observe that the probability of the full parse (equation \ref{eq:factored_approx_predictive}) can be written as a product of four terms: (1) the semantic prior $p(x^{new})$, (2) the left outer probability $p(s_L | x^{new},\bm{x},\bm{s},\bm{y})$, (3) the right outer probability $p(s_R | x^{new},\bm{x},\bm{s},\bm{y})$, and (4) the inner probability $p(s_I | x^{new},\bm{x},\bm{s},\bm{y})$.

Items in the agenda are sorted by an upper bound on the log probability of the entire parse. In order to compute this, we rely on an upper bound on the inner probability that only considers the syntactic structure:
\begin{equation}
\mathcal{I}_{\textrm{A},i,j} \triangleq \max_{\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_n} \left( \max_{x'} \log p(\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_n | x',\bm{x},\bm{s},\bm{y}) + \max_{m_2\le\hdots\le m_n} \sum_{k=1}^n \mathcal{I}_{\textrm{B}_k,m_k,m_{k+1}} \right),
\end{equation}
where $m_1 = i$ and $m_{n+1} = j$. In the sum, if $\textrm{B}_k$ is a terminal, then $\mathcal{I}_{\textrm{B}_k,m_k,m_{k+1}} = 0$ if $m_{k+1}-m_k = |\textrm{B}_k|$ is the correct length of the terminal; otherwise $\mathcal{I}_{\textrm{B}_k,m_k,m_{k+1}} = -\infty$. The term $\max_{x'} \log p(\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_n | x',\bm{x},\bm{s},\bm{y})$ can be computed exactly using algorithm \ref{alg:hdp_path_inference}, but a tight upper bound can be computed more quickly by terminating algorithm \ref{alg:hdp_path_inference} early and using the priority value given by equation \ref{eq:hdp_path_key} (we find that for preterminals, even using the priority computed at the root provides a very good estimate). The value of $\mathcal{I}$ can be computed efficiently using existing syntactic (e.g., PCFG) parsers in time $\mathcal{O}(n^3)$.

We also compute an upper bound on the log probability of the outer portion of the syntax tree and the semantic prior. To be more precise, let $\mathcal{P}(\textrm{A},i,j)$ be the set of all parses $(x, s_L, s_R, s_I)$ such that $s = s_L \cup s_R \cup s_I$ is the syntax and $s_I$ is the inner syntax tree with root $\textrm{A}$ that begins at sentence position $i$ (inclusive) and ends at $j$ (exclusive). Then, a bound on the outer probability is:
\begin{equation}
\mathcal{O}_{\textrm{A},i,j} \triangleq \max_{(x, s_L, s_R, s_I) \in \mathcal{P}(\textrm{A},i,j)} \log p(x) + \log p(s_L | x,\bm{x},\bm{s},\bm{y}) + \sum_{(\textrm{A}',i',j')\in \mathcal{R}(s_R)} \mathcal{I}_{\textrm{A}',i',j'}. \label{eq:outer_probability}
\end{equation}
where $\mathcal{R}(s_R)$ is the set of root vertices of the trees contained in $s_R$, and $p(x)$ is the prior probability of the semantic statement $x\in\mathcal{X}_S$. Note that the third term is an upper bound on the right outer probability $p(s_R|x,\bm{s},\bm{x},\bm{y})$.

Using these bounds, we can compute an upper bound on the overall log probability of the parse for any state. For a rule state $\texttt{r}$, the search priority is given by:
\begin{align}
\texttt{r.}&\texttt{log\_probability} + \max_{m_{k+1} \le \hdots \le m_n} \sum_{l = k}^{n} \mathcal{I}_{\textrm{B}_l,m_l,m_{l+1}} \nonumber \\
&+ \min\left\{ \log p(\texttt{r.semantics}), \mathcal{O}_{\textrm{A},\texttt{r.start},\texttt{r.end}} \right\}, \label{eq:rule_state_bound}
\end{align}
where $\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_k$ is the currently-considered rule $\texttt{r.rule}$, $m_k = \texttt{r.i}$, and $m_{n+1} = \texttt{r.end}$. Note the first two terms constitute an upper bound on the inner probability of the nonterminal $\textrm{A}$, and the third term is an upper bound on the outer probability and semantic prior. The second term can be computed efficiently using dynamic programming. We further tighten this by adding a term that bounds the log probability of the rule $\log p(\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_k | x',\bm{x},\bm{s},\bm{y})$. The items in the agenda are prioritized by this quantity. As long as the $\texttt{log\_probability}$ field remains exact, as it does in our approach, the overall search will yield exact outputs. The use of a syntactic parser to compute a tigher bound on the outer probability in an $\textrm{A}^*$ parser is similar to the approach of \namecite{Klein2003a}.

Naive computation of equation \ref{eq:outer_probability} is highly infeasible, as it would require enumerating all possible outer parses. However, we can rely on the fact that our search algorithm is \emph{monotonic}: the highest score in the agenda never increases as the algorithm progresses. We prove monotonicity by induction on the number of iterations. For a given iteration $i$, by the inductive hypothesis, the parser has visited all reachable rule states with priority strictly larger than the priority of the current rule state. We will show that all new rule states added to the priority queue at iteration $i$ must have priority at most equal to the priority of the current rule state. Consider each operation:
\setlength{\abovedisplayskip}{0.2cm}
\setlength{\belowdisplayskip}{0.3cm}
\setlength{\abovedisplayshortskip}{0.2cm}
\setlength{\belowdisplayshortskip}{0.3cm}
\begin{description}[itemsep=0.2cm,topsep=0.2cm]
\item[] In the \emph{expansion} operation, let $i = \texttt{r.i}$ and $k = \texttt{r.k}$. If the next right-hand side symbol $\textrm{B}_k$ is a terminal, the new agenda item will have score at most that of the old agenda item, since $\texttt{r}^*\texttt{.log\_probability} = \texttt{r.log\_probability}$ and the sum of inner probability bounds in equation \ref{eq:rule_state_bound} cannot increase. If the $\textrm{B}_k$ is a nonterminal, then we claim that any rule state created by this operation must have priority at most the priority of the old agenda item. Suppose to the contrary that there exists a $j\in\{i,\hdots,\texttt{r.end}\}$, a rule $\textrm{B}_k \to \textrm{C}_1 \hdots \textrm{C}_{u}$, and $m_2'\le\hdots\le m_{u}'$ such that:
\begin{align*}
\min\{ &\log p(\mathcal{X}_{\textrm{B}_k}), \mathcal{O}_{\textrm{B}_k,i,j} \} + \sum_{l=1}^{u} \mathcal{I}_{\textrm{C}_l,m_l',m_{l+1}'} \\
&> \texttt{r.log\_probability} + \max_{m_{k+1}\le\hdots\le m_n} \sum_{l=k}^n \mathcal{I}_{\textrm{B}_l,m_l,m_{l+1}} \\
&\quad{} + \min\left\{ \log p(\texttt{r.semantics}), \mathcal{O}_{\textrm{A},\texttt{r.start},\texttt{r.end}} \right\},
\end{align*}
where $m_k = m_1' = i$, $m_{u}' = j$, and $m_{n+1} = \texttt{r.end}$. Note that the left-hand side is bounded above by $\mathcal{I}_{\textrm{B}_k,i,j} + \mathcal{O}_{\textrm{B}_k,i,j}$ which implies, by the definition of $\mathcal{O}_{\textrm{B}_k,i,j}$, that there exists a parse $(x^*,s_L^*,s_R^*,s_I^*)\in\mathcal{P}(\textrm{B}_k,i,j)$ such that:
\begin{align*}
&\log p(x^*) + \log p(s_L^*|x^*,\bm{x},\bm{s},\bm{y}) + \mathcal{I}_{\textrm{B}_k,i,j} + \sum_{(\textrm{A}',i',j')\in\mathcal{R}(s_R^*)} \mathcal{I}_{\textrm{A}',i',j'} \\
&\hspace{1cm}> \texttt{r.log\_probability} + \max_{m_{k+2}\le\hdots\le m_n} \sum_{l=k}^n \mathcal{I}_{\textrm{B}_l,m_l,m_{l+1}} \\
&\hspace{1.4cm} + \min\left\{ \log p(\texttt{r.semantics}), \mathcal{O}_{\textrm{A},\texttt{r.start},\texttt{r.end}} \right\},
\end{align*}
where $m_{k+1} = j$. Let $\textrm{C} \to \textrm{D}_1 \hdots \textrm{D}_v$ be the production rule in the syntax tree $s^*$ containing $s_I^*$. In addition, let $s_i^*$ be the sibling subtree of $s_I$ rooted at $\textrm{D}_i$. This parse implies the existence of a rule state $\texttt{r}^*$ where $\texttt{r}^*\texttt{.rule} = (\textrm{C} \to \textrm{D}_1 \hdots \textrm{D}_v)$, $\texttt{r}^*\texttt{.start}$ and $\texttt{r}^*\texttt{.end}$ are the start and end positions of the vertex corresponding to $\textrm{C}$, $\texttt{r}^*\texttt{.i} = \texttt{r.i}$, $\texttt{r}^*\texttt{.log\_probability} = \sum_{i=1}^{\texttt{r}^*\texttt{.k}} \log p(s_i^*|x^*,\bm{x},\bm{s},\bm{y})$. The search priority of this rule state would be:
\begin{align*}
\sum_{i=1}^{\texttt{r}^*\texttt{.k} - 1} \log p(s_i^*|x^*,\bm{x},\bm{s},\bm{y}&) + \max_{m_{k+1}\le\hdots\le m_v} \sum_{l=\texttt{r}^*\texttt{.k}}^v \mathcal{I}_{\textrm{D}_l,m_l,m_{l+1}} \\
&+ \min \{ \log p(\texttt{r}^*\texttt{.semantics}), \mathcal{O}_{\textrm{C},\texttt{r}^*\texttt{.start},\texttt{r}^*\texttt{.end}} \}
\end{align*}
We claim that this search priority must be strictly greater than that of the old agenda item $\texttt{r}$. By the definition of $\mathcal{O}$:
\begin{align*}
\mathcal{O}_{\textrm{C},\texttt{r}^*\texttt{.start},\texttt{r}^*\texttt{.end}} &\ge \log p(x^*) + \log p(s_L^* \setminus \{s_1^*,\hdots,s_{\texttt{r}^*\texttt{.k} - 1}^*\} | x^*,\bm{x},\bm{s},\bm{y}) \\
&\quad{} + \sum_{(\textrm{A}',i',j')\in\mathcal{R}(s_R^* \setminus \{s^*_{\texttt{r}^*\texttt{.k} + 1},\hdots,s^*_v\})} \mathcal{I}_{\textrm{A}',i',j'},
\end{align*}
combined with the fact that $\log p(x^*) \le \log p(X)$ for any $X\in\mathcal{X}_C$, observe that the search priority of $\texttt{r}^*$ must be at least:
\begin{align*}
\log p(x^*) + \log p(&s_L^* | x^*, \bm{x},\bm{s},\bm{y}) + \mathcal{I}_{\textrm{B}_k,i,j} + \sum_{(\textrm{A}',i',j')\in\mathcal{R}(s_R^*)} \mathcal{I}_{\textrm{A}',i',j'},
\end{align*}
which, in turn, is strictly greater than the priority of $\texttt{r}$. Thus, the priority of $\texttt{r}^*$ is strictly larger than that of $\texttt{r}$, which would imply that the nonterminal $\textrm{B}_k$ was previously expanded with start position $i$ and end position $j$, which is a contradiction.
\item[] In the \emph{completion} operation, the inner log probability of the new rule state $\texttt{r}^*\texttt{.log\_probability}$ is at most the sum of the inner log probability of the old rule state $\texttt{r.log\_probability}$ and the bound $\max_j \mathcal{I}_{\textrm{B}_k,i,j}$. Thus, the priority of the new rule state is bounded by the priority of the old rule state.
\item[] In the \emph{iteration} operation, monotonicity is guaranteed since the iterator structure returns items in order of non-increasing probability.
\end{description}
Therefore, the parser is monotonic. As a consequence, whenever the algorithm first expands a nonterminal $\textrm{B}_k$ from a rule $\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_n$, at start position $i$ and end position $j$ in the sentence, we have found the left outer parse that maximizes equation \ref{eq:outer_probability}:
\begin{align*}
\mathcal{O}_{\textrm{B}_\texttt{r.k},i,j} &= \texttt{r.log\_probability} + \max_{m_{k+2}\le\hdots\le m_n} \sum_{l=k+1}^n \mathcal{I}_{\textrm{B}_l,m_l,m_{l+1}} \\
&\quad{} + \min\left\{ \log p(\texttt{r.semantics}), \mathcal{O}_{\textrm{A},\texttt{r.start},\texttt{r.end}} \right\},
\end{align*}
thereby computing $\mathcal{O}_{\textrm{B}_\texttt{r.k},i,j}$ at no additional cost. Similarly, when the parser first constructs a nonterminal structure for the symbol $\textrm{A}$ at start position $i$ and end position $j$, monotonicity guarantees that no other nonterminal structure at $(\textrm{A},i,j)$ will have higher probability. We exploit this by updating the value of $\mathcal{I}_{\textrm{A},i,j}$ as the algorithm progresses, incorporating more semantic information in the values of $\mathcal{I}$.

\begin{figure}[H]
\caption{A step-by-step example of the parser running on the sentence ``Chopin plays'' using the grammar very similar to the one shown in figure \ref{fig:example_grammar}. The top-left table lists the semantic statements sorted by their log probability of drawing the observation ``Chopin'' from the HDP associated with the nonterminal N. The top-center and top-right tables are defined similarly.}
\def\arraystretch{1.25}
\begin{tabular}{ | p{2.7cm} c | }
\hline
\hspace{0.3cm}N $\to$ ``Chopin'' & \hspace{-0.5cm}\color{grey}{log prob}. \\
\hline
\textit{musician:chopin} & -2 \\
\textit{sport:swimming} & -8 \\
\textit{sport:tennis} & -8 \\
\textit{instrument:piano} & -8 \\
\hspace{1cm}\textbf{*} & -8 \\
\hline
\multicolumn{2}{p{3.8cm}}{
\setlength{\parindent}{0.2cm} \vspace{-0.2cm}
\color{grey}{The symbol} \textbf{*} \color{grey}{is a \emph{wildcard}, referring to any entity in the ontology excluding those listed. \newline
\indent In this example, we use the grammar in figure \ref{fig:example_grammar}.}}
\end{tabular} %
\begin{tabular}{ | p{3.0cm} c | }
\hline
\hspace{0.5cm}V $\to$ ``plays'' & \hspace{-0.5cm}\color{grey}{log prob}. \\
\hline
\hangindent=0.8cm \textit{athlete\_plays\_sport(\textbf{*}, \textbf{*})} & -2 \\
\hangindent=0.8cm \textit{musician\_plays\_inst(\textbf{*}, \textbf{*})} & -2 \\
\hangindent=0.8cm \textit{musician\_plays\_inst(\textbf{*}, \newline instrument:piano)} & -2 \\
\hangindent=0.8cm \textit{athlete\_plays\_sport(\textbf{*}, \newline sport:tennis)} & -2 \\
\hangindent=0.8cm \textit{athlete\_plays\_sport(\textbf{*}, \newline sport:swimming)} & -8 \\
\hangindent=0.8cm \textit{athlete\_plays\_sport(\textbf{*}, \newline instrument:piano)}\vspace{-0.12cm} & -8\vspace{-0.12cm} \\
\hspace{1.4cm}\small\vdots & \small\vdots \\
\hline
\end{tabular} %
\begin{tabular}{ | p{3.0cm} c | }
\hline
\hspace{0.9cm}VP $\to$ V & \hspace{-0.5cm}\color{grey}{log prob}. \\
\hline
\hangindent=0.8cm \textit{athlete\_plays\_sport(\textbf{*}, \textbf{*})} & -4 \\
\hangindent=0.8cm \textit{musician\_plays\_inst(\textbf{*}, \textbf{*})} & -4 \\
\hangindent=0.8cm \textit{athlete\_plays\_sport(\textbf{*}, \newline sport:swimming)} & -4 \\
\hangindent=0.8cm \textit{musician\_plays\_inst(\textbf{*}, \newline instrument:piano)} & -5 \\
\hangindent=0.8cm \textit{athlete\_plays\_sport(\textbf{*}, \newline sport:tennis)} & -5 \\
\hangindent=0.8cm \textit{athlete\_plays\_sport(\textbf{*}, \newline instrument:piano)}\vspace{-0.12cm} & -8\vspace{-0.12cm} \\
\hspace{1.4cm}\small\vdots & \small\vdots \\
\hline
\end{tabular}}

\vspace{0.2cm}
\begin{tabular}{ m{1.0cm} m{4.0cm} m{7.1cm} }
\hline
\textbf{\textit{iteration}} & \centering \textbf{\textit{operation}} & \centering \textbf{\textit{new states created}} \tabularnewline
\hline
\centering \textbf{\textit{0}} & \textit{expand} S at start position 0, end position 12 & %
\vspace{0.2cm}
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={S $\to \bullet$ N VP},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{c}
\texttt{i}: 0, \texttt{end}: 12 \\
\texttt{log\_prob}: 0
\end{tabular} %
} \tabularnewline

\centering \textbf{\textit{1}} & \vspace{0.12cm} pop the S $\to \bullet$ N VP state and \textit{expand} N at start position 0 and end positions $0,\ldots,12$ &
\hspace{0.4cm}\scriptsize
\tcbox[left=1mm,right=1mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={N $\to$ ``Chopin'' $\bullet$},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 6 , \texttt{end}: 6 \\
\texttt{log\_prob}: 0
\end{tabular} %
} \tabularnewline

\centering \textbf{\textit{2}} & \textit{iterate} the complete rule state N $\to$ ``Chopin'' $\bullet$ & %
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedred,coltitle=black,title={N},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{start}: 0, \texttt{end}: 6 \\
\texttt{log\_prob}: -2 \\
\textit{musician:chopin}
\end{tabular} %
} \tabularnewline

\centering \textbf{\textit{3}} & pop the N nonterminal state and \textit{complete} any waiting rule states & %
\vspace{0.1cm}
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={S $\to$ N $\bullet$ VP},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 7, \texttt{end}: 12 \\
\texttt{log\_prob}: -2 \\
\textbf{*} \textit{(musician:chopin, \textbf{*})}
\end{tabular} %
} \tabularnewline

\centering \textbf{\textit{4}} & \vspace{0.15cm} pop the S $\to$ N $\bullet$ VP state and \textit{expand} VP at start position 7 and end position 12 & %
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={VP $\to \bullet$ V},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 7, \texttt{end}: 12 \\
\texttt{log\_prob}: 0
\end{tabular}} %
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={VP $\to \bullet$ V N},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 7, \texttt{end}: 12 \\
\texttt{log\_prob}: 0
\end{tabular}} %
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={VP $\to \bullet$ V},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 7, \texttt{end}: 11 \\
\texttt{log\_prob}: 0
\end{tabular} %
} \hspace{0.1cm}\raisebox{0.36cm}{${\ldots}$} \tabularnewline

\centering \vspace{0.25cm} \textbf{\textit{5}} & \vspace{0.25cm} pop the VP $\to \bullet$ V state and \textit{expand} V & %
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={V $\to$ ``plays'' $\bullet$},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 12, \texttt{end}: 12 \\
\texttt{log\_prob}: 0
\end{tabular} %
} \tabularnewline

\centering \textbf{\textit{6}} & \textit{iterate} the complete rule state V $\to$ ``plays'' $\bullet$ & %
\vspace{0.1cm}
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedred,coltitle=black,title={V},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{start}: 7, \texttt{end}: 12 \\
\texttt{log\_prob}: -2 \\
\textit{athlete\_plays\_sport(\textbf{*}, \textbf{*})}
\end{tabular}} %
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedred,coltitle=black,title={V},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{start}: 7, \texttt{end}: 12 \\
\texttt{log\_prob}: -2 \\
\textit{musician\_plays\_inst(\textbf{*}, \textbf{*})}
\end{tabular} %
} \hspace{0.1cm}\raisebox{0.54cm}{${\ldots}$} \tabularnewline

\centering \textbf{\textit{7}} & pop a V nonterminal state and \textit{complete} any waiting rule states & %
\vspace{0.1cm}
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={VP $\to$ V $\bullet$},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 12, \texttt{end}: 12 \\
\texttt{log\_prob}: -2 \\
\textit{musician\_plays\_inst(\textbf{*}, \textbf{*})}
\end{tabular}} %
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={VP $\to$ V $\bullet$ N},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 12, \texttt{end}: 12 \\
\texttt{log\_prob}: -2 \\
\textit{musician\_plays\_inst(\textbf{*}, \textbf{*})}
\end{tabular} %
} \hspace{0.1cm}\raisebox{0.54cm}{${\ldots}$} \tabularnewline

\centering \textbf{\textit{8}} & \textit{iterate} the complete rule state VP $\to$ V $\bullet$ & %
\vspace{0.1cm}
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedred,coltitle=black,title={VP},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{start}: 7, \texttt{end}: 12 \\
\texttt{log\_prob}: -6 \\
\textit{musician\_plays\_inst(\textbf{*}, \textbf{*})}
\end{tabular} %
} \tabularnewline

\centering \textbf{\textit{9}} & pop the VP nonterminal state and \textit{complete} any waiting rule states & %
\vspace{0.1cm}
\hspace{0.4cm}\scriptsize
\tcbox[left=0mm,right=0mm,top=0mm,bottom=0mm,boxsep=0mm,toptitle=0.3mm,bottomtitle=0.2mm,colbacktitle=fadedblue,coltitle=black,title={S $\to$ N VP $\bullet$},center title,nobeforeafter,boxrule=0.3mm]{
\begin{tabular}{ c }
\texttt{i}: 12, \texttt{end}: 12 \\
\texttt{log\_prob}: -8 \\
\multicolumn{1}{p{3.0cm}}{
\centering \textit{musician\_plays\_inst( \newline
musician:chopin, \textbf{*})}}
\end{tabular} %
} \tabularnewline
\end{tabular}
\end{figure}

\section{Results} \label{section:results}

The experiments in this section evaluate our parser's ability to parse semantic statements from short sentences, consisting of a subject noun, a simple verb phrase, and an object noun. We also evaluate the ability to incorporate background knowledge during parsing, through the semantic prior. To do so, we used the ontology and knowledge base of the Never-Ending Language Learning system (NELL) [37]. We use a snapshot of NELL at iteration 905 containing 1,786,741 concepts, 623 relation predicates, and 2,212,187 beliefs (of which there are 131,365 relation instances). The relations in NELL are \emph{typed}, where the domain and range of each relation is a category in the ontology. We compare our parser to a state-of-the-art CCG parser [33] trained and tested on the same data.

\begin{figure}
\tikzstyle{nonterminal}=[circle,draw,fill=lightgrey,inner sep=0,minimum size=0.7cm,thick]
\centering
\small
\vspace{0.2cm}
\hspace{-0.2cm} \begin{tikzpicture}[level/.style={sibling distance=22mm/#1,level distance=0.9cm,line width=0.9pt,edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}}]
\node[nonterminal] (S) {\textsf{\textbf{S}}}
child {node[nonterminal] (N) {\textsf{\textbf{N}}}
child {node (federer) {Federer}}
child {node[nonterminal] (VP) {\textsf{\textbf{VP}}}
child {node[nonterminal] (V) {\textsf{\textbf{V}}}
child {node (plays) {plays}}
child {node[nonterminal] (Nobj) {\textsf{\textbf{N}}}
child {node (tennis) {tennis}}
\node[above of=S,node distance=0.8cm,align=center] {\textbf{simple grammar}};
\node[below of=V,node distance=2.7cm,text width=3.0cm,xshift=-0.2cm] {\textit{athlete\_plays\_sport( athlete:roger\_federer, sport:tennis)}};
\end{tikzpicture} \hspace{0.5cm} %
\hspace{0.2cm} \begin{tikzpicture}[level/.style={sibling distance=28mm/#1,level distance=0.9cm,line width=0.9pt,edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}}]
\tikzstyle{level 1}=[sibling distance=22mm]
\node[nonterminal] (S) {\textsf{\textbf{S}}}
child {node[nonterminal] (N) {\textsf{\textbf{N}}}
child {node (federer) {Federer}}
child {node[nonterminal] (VP) {\textsf{\textbf{VP}}}
child {node[nonterminal] (V) {\textsf{\textbf{V}}}
child {node[nonterminal] (Vroot) {\textsf{\textbf{V{\tiny root}}}}
child {node (plays) {play}}
child {node[nonterminal] (Vaffix) {\textsf{\textbf{V{\tiny affix}}}}
child {node (plays) {s}}
child {node[nonterminal] (Nobj) {\textsf{\textbf{N}}}
child {node (tennis) {tennis}}
\node[above of=S,node distance=0.8cm,align=right] {\textbf{verb morphology grammar}\hspace{-0.8cm}};
\node[below of=V,node distance=2.7cm,text width=3.6cm,xshift=0.3cm] {\textit{athlete\_plays\_sport( athlete:roger\_federer, sport:tennis, \textcolor{MidnightBlue}{time:present})}};
\end{tikzpicture} \hspace{-0.4cm}
\vspace{-0.4cm}
\caption{An example of a (simpified) labeled data instance in our experiments. For brevity, we omit semantic transformation operations, syntax elements such as word boundaries, irregular verb forms, etc.}
\vspace{-0.4cm}
\end{figure}

\subsection{Relation extraction}

We first evaluate our parser on a relation extraction task on a dataset of subject-verb-object (SVO) sentences. We created this dataset by filtering and labeling sentences from a corpus of SVO triples [50] extracted from dependency parses of the ClueWeb09 dataset [10]. NELL provides a \texttt{can\_refer\_to} relation, mapping noun phrases to concepts in the NELL ontology. We created our own mapping between verbs (or simple verb phrases) and 223 relations in the NELL ontology. Using these two mappings, we can identify whether an SVO triple can refer to a belief in the NELL knowledge base. We only accepted sentences that referred to high-confidence beliefs in NELL (for which NELL gives a confidence score of at least 0.999). The accepted sentences were labeled with the referred beliefs. For this experiment, we restrict all verbs to the present tense. This yielded a final dataset of 2,546 SVO three-word sentences, along with their corresponding semantic statement from the NELL KB, spanning over 74 relations and 1,913 concepts. We randomly split the data into a training set of 2,025 sentences and a test set of 521 sentences. In the task, each parser makes predictions on every test sentence, which we mark as correct if the output semantic statement exactly matches the label. The main difficulty in this task is to learn the mapping between relations and the sentence text. For example, the dataset contains verbs such as `makes' which can refer to at least five NELL relations, including \textit{companyeconomicsector}, \textit{directordirectedmovie} and \textit{musicartistgenre}. The semantic types of the subject and object concepts are very informative in resolving ambiguity, and prior knowledge in the form of a belief system can further aid parsing. The precision-recall curves in figure \ref{fig:simple_precision_recall} were generated by sorting the outputs of our parser by posterior probability, which was computed using the top $k=10000$ output parses for each test sentence (see section \ref{section:k_experiments} for experiments with varying $k$).
% TODO: uncomment this
% The grammar and dataset are available at \abucomment{add url}\href{https://www.google.com}{\texttt{anonymized}} (including all hyperparameters).

We call a semantic statement ``type-correct'' if the subject and object concepts agree with the domain and range of the instantiated relation, under the NELL ontology. We experimented with three prior settings for our parser: (1) uniform prior, (2) a prior where all type-correct semantic statements have a prior probability that is larger by 4 units (in terms of log probability) than type-incorrect statements, and (3) a prior where all semantic statements that correspond to true beliefs in the KB have a prior probability that is 8 larger than type-incorrect statements and all type-correct correct statements have probability 4 larger than type-incorrect statements.

In the simple relation extraction task, we find that CCG performs comparably to our parser under a uniform and type-correct prior. In fact, the parsers make the almost identical predictions on the test sentences. The differences in the precision-recall curves arise due to the differences in the scoring of predictions. The primary source of incorrect predictions is when a noun in the test set refers to a concept in the ontology but does not refer to the same concept in the training set. For example, in the sentence ``Wilson plays guitar,'' both parsers predict that ``Wilson'' refers to the politician Greg Wilson. The similarity in the performance of our parser with the uniform prior and the type-correct prior suggests that the parser learns ``type-correctness'' from the training data. This is due to the fact that, in our grammar, the distribution of the verb depends jointly on the types of both arguments. With the KB prior, our parser outperforms CCG, demonstrating that our parser effectively incorporates background knowledge via the semantic prior to improve precision and recall.

\begin{figure}
\centering
\vspace{-0.5cm}
\includegraphics[scale=0.45]{figures/simple.pdf}
\vspace{-0.5cm}
\caption{Precision-recall curves for the standard relation extraction task. We compare our approach with three different settings of the prior (yellow, orange, red) and CCG (blue). The uniform prior places equal probability mass on all semantic statements. The ``type-correct'' prior places higher mass (+4 in log probability) on semantic statements with subject and object types that agree with the domain and range of the relation predicate. The ``knowledge base prior'' is similar to the type-correct prior, except that it additionally places higher probability mass on semantic statements that correspond to true beliefs in the NELL knowledge base (an additional +4 in log probability).} \label{fig:simple_precision_recall}
\end{figure}

\begin{table}
\caption{A sample of two randomly selected parses from the simple relation extraction task, using a uniform prior and $k = 10^7$. For each of the two sample sentences, the top few parse outputs are displayed, along with their log probabilities. Recall that our parser operates over \emph{sets} of semantic statements, so some of the outputs contain wildcards. It is evident from the output on the right that the phrase ``Kidneys'' did not appear in the training set, and so the highest-ranked parse is ambiguous.}
\centering
\def\arraystretch{1.25}
\begin{tabular}{ p{4.3cm} c }
\hline
\hangindent=0.5cm \hspace{0.5cm}``Mickey Rourke \newline stars in Wrestler'' & \hspace{-0.2cm}\color{grey}{log prob}. \\
\hline
\hangindent=0.6cm \textit{actor\_starred\_in\_movie( \newline actor:mickey\_rourke, \newline movie:wrestler)} & -10.50 \\
\hangindent=0.6cm \textit{actor\_starred\_in\_movie(} \newline any \textit{actor} except \textit{actor:miley\_cyrus, actor:mike\_myers, etc.}, \textit{\newline movie:wrestler)} & -15.11 \\
\hangindent=0.6cm \textit{actor\_starred\_in\_movie( \newline actor:mickey\_rourke, \newline } any \textit{movie} except \textit{movie:austin\_powers, movie:cold\_mountain, etc.}\textit{)} & -15.11 \\
\hangindent=0.6cm \textit{actor\_starred\_in\_movie( \newline actor:anne\_hathaway, \newline movie:wrestler)} & -15.11 \\
\hspace{2cm}\vdots & \vdots \\
\hline
\end{tabular} %
\hspace{0.5cm} %
\begin{tabular}{ p{4.3cm} c }
\hline
\hangindent=0.6cm \hspace{0.5cm}``Kidneys contain \newline blood vessels'' & \hspace{-0.2cm}\color{grey}{log prob}. \\
\hline
\hangindent=0.6cm \textit{bodypart\_contains\_bodypart(} \newline any \textit{bodypart} except \textit{artery:hand, braintissue:brains, etc.}, \textit{\newline artery:blood\_vessels)} & -15.11 \\
\hangindent=0.6cm \textit{bodypart\_contains\_bodypart( \newline bodypart:blood, \newline artery:blood\_vessels)} & -15.11 \\
\hangindent=0.6cm \textit{bodypart\_contains\_bodypart( \newline bodypart:legs, \newline artery:blood\_vessels)} & -15.11 \\
\hangindent=0.6cm \textit{bodypart\_contains\_bodypart( \newline braintissue:parts, \newline artery:blood\_vessels)} & -15.11 \\
\hangindent=0.6cm \textit{bodypart\_contains\_bodypart( \newline bodypart:nerves001, \newline artery:blood\_vessels)} & -15.11 \\
\hspace{2cm}\vdots & \vdots \\
\hline
\end{tabular}
\end{table}

\subsection{Modeling word morphology}
In the second experiment, we demonstrate our parser's ability to extract semantic information from the morphology of individual verbs, by operating over characters instead of preprocessed tokens. We generated a new labeled SVO dataset using a process similar to that in the first experiment. In this experiment, we did not restrict the verbs to the present tense. This dataset contains 3,197 sentences spanning 56 relations and 2,166 concepts. The data was randomly split into a set of 2,538 training sentences and 659 test sentences. We added a simple temporal model to the semantic formalism: all sentences in any past tense refer to semantic statements that were true in the past; all sentences in any present tense refer to presently true statements; and sentences in any future tense refer to statements that will be true in the future. Thus the task becomes one of \emph{temporally-scoped relation extraction}. A simple verb morphology model was incorporated into the grammar. Each verb is modeled as a concatenated root and affix. In the grammar, the random selection of a production rule captures the selection of the verb tense. The affix is selected deterministically according to the desired tense and the grammatical person of the subject. The posterior probability of each parse was estimated using the top $k=10000$ parses for each test example. Results are shown in figure \ref{fig:verb_precision_recall}.

\begin{figure}
\centering
\includegraphics[scale=0.45]{figures/verb_morphology.pdf}
\caption{Precision-recall curves for the temporally-scoped relation extraction task. We compare our approach with three different settings of the prior (yellow, orange, red) and CCG (blue). The solid lines denote our parser's performance when using a grammar that models the morphology of verbs, whereas the dashed lines are produced when our parser is trained with a grammar that does not model verb morphology. The uniform prior places equal probability mass on all semantic statements. The ``type-correct'' prior places higher mass (+4 in log probability) on semantic statements with subject and object types that agree with the domain and range of the relation predicate. The ``knowledge base prior'' is similar to the type-correct prior, except that it additionally places higher probability mass on semantic statements that correspond to true beliefs in the NELL knowledge base (additional +4 in log probability).} \label{fig:verb_precision_recall}
\end{figure}

In this temporally-scoped relation extraction task, our parser demonstrates better generalization over verb forms. Our parser performs better when trained on a grammar that models verb morphology (solid lines) than when trained on a simpler grammar that does not consider the morphology of verbs (dashed lines). The parser is able to accomplish this due to its ability to model the semantics in the morphology of individual words. As in the first experiment, the performance of our parser improves when we use the knowledge base prior, supporting the observation that our parser can effectively leverage background knowledge to improve its accuracy. There is, again, no difference in performance when using the uniform prior vs. the type-correct prior.

\begin{figure}
\centering
\includegraphics[scale=0.45]{figures/ambiguous.pdf}
\includegraphics[scale=0.45]{figures/ambiguous_filtered.pdf}
\caption{(\textbf{top}) Precision and recall for the simple relation extraction task, including unambiguous outputs, and (\textbf{bottom}) on the subset of sentences for which CCG did not provide output. We compare our approach with three different settings of the prior (yellow, orange, red) and CCG (blue). The uniform prior places equal probability mass on all semantic statements. The ``type-correct'' prior places higher mass (+4 in log probability) on semantic statements with subject and object types that agree with the domain and range of the relation predicate. The ``knowledge base prior'' is similar to the type-correct prior, except that it additionally places higher probability mass on semantic statements that correspond to true beliefs in the NELL knowledge base (additional +4 in log probability).} \label{fig:ambiguous}
\end{figure}

\subsection{Out-of-vocabulary behavior}
Recall that our parser operates over sets of semantic statements, as opposed to individual statements. Thus, it is possible that when parsing completes, the output is a non-singleton set of semantic statements that all share the highest probability parse. In our first two experiments, we counted these outputs as a ``non-parse'' to more fairly compare with CCG. However, we can evaluate the quality of these \emph{ambiguous} outputs. In figure \ref{fig:ambiguous}, we again perform the simple relation extraction task with a modification: we measure the correctness of our parser's output by whether the ground truth semantic statement is contained within the set of semantic statements that share the highest probability parse. CCG does not produce output on sentences that contain tokens which did not appear in the training data. In a sense, this evaluation measures out-of-vocabulary performance. Although precision is not as high as the in-vocabulary test, recall is much improved. The knowledge base prior again results in improved performance over the less informative priors.

\subsection{Effect of changing the parameter $k$} \label{section:k_experiments}
In our parser, the search algorithm does not terminate until it has found the $k$-best semantic parses. This is useful for evaluating the confidence of the parser in its output, and for estimating the posterior probability of each parse. We examine the behavior of the parser as a function of $k$ in figure \ref{fig:average_k}. The timing results demonstrate that the parser can scale to large knowledge bases while maintaining efficiency during parsing.

\begin{figure}
\centering
\includegraphics[scale=0.45]{figures/average_k.pdf}
\caption{Area under the precision-recall curve and average parse time versus $k$, for the simple relation extraction task and a uniform prior. The dark green curve measures the area under the precision-recall curve without considering ambiguous outputs (as in figure \ref{fig:simple_precision_recall}), whereas the light green curve measures the area under the precision-recall curve taking into account the ambiguous outputs (as in the top plot in figure \ref{fig:ambiguous})} \label{fig:average_k}
\end{figure}

Recall that, in order to produce the precision-recall curves for our parser's output, we sort the outputs by their confidence scores (estimates of the posterior probability). In the figure, the area under the precision-recall curve (AUC) converges quickly at fairly small values of $k$, indicating that the relative ordering of the parse outputs converges quickly. We found this behavior to be consistent for other choices of prior distributions and for the more complex temporally-scoped relation extraction task. For values of $k$ smaller than $\sim10^6$, the parser provides outputs very quickly. This is due to the fact that, as the parser performs its search, it can quickly find a set of semantic statements of size roughly $10^6$ (e.g., when parsing ``Federer plays golf'', it will quickly find an output that looks like \textit{athlete\_plays\_sport(athlete:roger\_federer,\textbf{*})} where \textbf{*} is a wildcard that denotes any concept in the ontology). The parser will require additional time to search beyond this initial ambiguous output. Note that this threshold value of $k$ is identical to the number of concepts in the ontology: 1,786,741. The second threshold is likely related to the product of the number of concepts and the number of relations in the ontology: $623 \cdot 1786741 \approx 1.11\cdot 10^9$.

\begin{table}
\caption{Precision and recall of the parsers evaluated on the out-of-knowledge base dataset. The uniform prior places equal probability mass on all semantic statements. The ``type-correct'' prior places higher mass (+4 in log probability) on semantic statements with subject and object types that agree with the domain and range of the relation predicate. The ``knowledge base prior'' is similar to the type-correct prior, except that it additionally places higher probability mass on semantic statements that correspond to true beliefs in the NELL knowledge base (additional +4 in log probability).} \label{tbl:out_of_kb}
\begin{tabularx}{\textwidth}{ l c c c }
\hline
\textit{simple relation extraction} & \textbf{precision} & \textbf{recall} & \textbf{F1} \\
\hline
CCG & 0.65 & 0.44 & 0.52 \\
our parser (no prior) & 0.78 & \textbf{0.58} & \textbf{0.66} \\
our parser (type-correct prior) & 0.84 & 0.46 & 0.60 \\
our parser (KB prior) & \textbf{0.90} & 0.45 & 0.60 \\
\end{tabularx}

\vspace{0.2cm}
\begin{tabularx}{\textwidth}{ l c c c }
\hline
\textit{temporally-scoped relation extr.} & \textbf{precision} & \textbf{recall} & \textbf{F1} \\
\hline
CCG & 0.78 & 0.63 & 0.69 \\
our parser (no prior) & 0.81 & \textbf{0.68} & \textbf{0.73} \\
our parser (type-correct prior) & \textbf{0.84} & 0.59 & 0.69 \\
our parser (KB prior) & \textbf{0.84} & 0.54 & 0.65 \\
\end{tabularx}
\end{table}

\subsection{Out-of-knowledge base relation extraction}
In all earlier experiments, we used a dataset that only contained sentences that refer to beliefs in the NELL knowledge base. In order to inspect the performance of the parser on sentences that do not refer to NELL beliefs, we create a new dataset. We again start with the SVO sentence corpus and modify the filtering process: we only accept sentences that (1) contain noun phrases that also exist in the first dataset (to ensure the parsers at least have a chance to unambiguously understand the sentences), (2) contain verb phrases that exist in the hand-constructed verb-relation map we used to create the first dataset, (3) cannot refer to any NELL belief, according to the \texttt{can\_refer\_to} instances and the verb-relation map. More precisely, for every sentence, the \texttt{can\_refer\_to} relation maps each noun phrase to a set of possible referent concepts; the relation-verb map provides a set of possible referent relations; and so their Cartesian product provides a set of possible referent semantic statements. We discard those sentences where the set of referent semantic statements contains a NELL belief. We sorted the resulting sentence list by frequency and labeled them by hand. Of the 1365 most frequent sentences in the filtered set, we labeled 100, since some sentences referred to concepts outside of the ontology or their verbs referred to unrecognized relations (i.e., not in the verb-relation map). This dataset is referred to as the \emph{out-of-knowledge base} dataset, since the sentences refer to beliefs outside the knowledge base%
% TODO: uncomment this
% (this dataset is also available at \abucomment{add url}\href{https://www.google.com}{\texttt{anonymized}})
. We selected 20 sentences from this dataset as training sentences. We trained all parsers on these sentences in addition to the entirety of the first dataset. We tested the parsers on the remaining 80 sentences.

Table \ref{tbl:out_of_kb} displays the performance results of our parser and CCG on this out-of-knowledge base dataset, in both the simple relation extraction task as well as the temporally-scoped task. Our parser is trained with the simple grammar in the simple relation extraction task, and with the grammar that models verb morphology in the temporally-scoped relation extraction task. As expected, the more informative priors do not uniformly improve parsing performance in this evaluation. Interestingly, the parser behaves more conservatively when incorporating the stronger priors, outputting a smaller set of the most confident responses, which results in higher precision and reduced recall. Our parser is indeed capable of extracting the correct semantic statements from sentences that refer to beliefs outside the knowledge base, and the use of the informative priors does not obviously hurt performance.

\section{Discussion}

In this article, we presented a generative model of sentences for semantic parsing, extending the CFG formalism to couple semantics with syntax. In the generative process, a semantic statement is first generated, for example, from a knowledge base. Next, the tree is constructed top-down using a recursive procedure: production rules are selected randomly, possibly depending on features of the semantic statement. Semantic transformation operations specify how to decompose the semantic statement in order to continue recursion. We presented a particular construction where production rules are selected using an HDP. We applied MCMC to perform inference in this model, and constructed a chart-driven agenda parser. Our application of the HDP is distinct from previous uses, since in our construction, the path indicator for each observation is not assumed to be fixed. We evaluate our parser on a dataset of SVO sentences, labeled with semantic statements from NELL. The results demonstrate that our parser can incorporate prior knowledge from a knowledge base via the semantic prior. With an informative prior, our parser outperforms a state-of-the-art CCG parser. In addition, we demonstrate that our model can be used to jointly model the morphology of individual verbs, leading to improved generalization over verbs in a temporally-scoped relation extraction task. The results indicate that our framework can scale to knowledge bases, such as NELL, with millions of beliefs, and can be extended to more complex grammars and richer semantic formalisms without sacrificing exact inference and the principled nature of the model.

An interesting parallel can be drawn between our inference problem and the problem of finding shortest paths in hypergraphs. Similar parallels have been drawn in other parsers [30, 31, 40, 41]. Since our approach is top-down, the specification of our hypergraph is more involved. Imagine a hypergraph containing a vertex for every semantic statement $x\in\mathcal{X}$, a vertex for every intermediate rule state $\textrm{A} \to \textrm{B}_1 \hdots \textrm{B}_k \bullet \textrm{B}_{k+1} \hdots \textrm{B}_n$, and two vertices for every nonterminal (one indicating that parsing is incomplete and one for completed parses). Add a hyperedge to this graph for every allowable operation by the parser. A hyperedge is a generalization of an edge where both its ``head'' and ``tail'' can be sets of vertices. Then, the problem of parsing can be equivalently stated as finding the shortest ``path'' from two sets of vertices: the source set of vertices are those representing the incomplete $\textrm{S}$ nonterminal and all elements of $\mathcal{X}_S$, and the destination vertex is the complete $\textrm{S}$ nonterminal. See \namecite{Gallo93,Klein01} for definitions and further details. Our algorithm can then be understood as an application of $\textrm{A}^*$ search for the $k$-best paths in this hypergraph. The monotonicity property of our algorithm is a consequence of Dijkstra's theorem generalized to hypergraphs [21]. This also suggests that our parser can be improved by utilizing a tighter heuristic.

In the parser, the prior contribution is rather loosely incorporated into the objective (equation \ref{eq:rule_state_bound}). This is due to the fact that we assumed nothing about the structure of the semantic prior. However, the algorithm could potentially be made more efficient if we could factorize the prior, for example, over nonterminals or rules in the grammar. This could provide an additive term to equation \ref{eq:rule_state_bound}.

We presented our inference approach as a combination of two search algorithms: (1) the HDP inference component, and (2) the joint syntactic-semantic parser. However, it is possible to merge these two searches into a single search (the priority queues of each algorithm would be unified into a single global priority queue), potentially improving the overall efficiency.

In this article, we showed how to utilize HDPs to add dependence between semantic features and the probabilistic selection of production rules in the generative process. It would be interesting to explore the application of other dependent Dirichlet processes and random probability measures, possibly as a means to induct a grammar in our framework.

Another highly promising avenue of research is to explore more complex prior structures. For instance, a generative model of a knowledge base could be composed with the framework we present here. This would result in a parser that would learn new beliefs as it reads text. Another direction is to model the generation of a sequence of sentences (such as in a paragraph), where complex relationships between concepts bridge across multiple sentences. Such an approach would likely contain a model of \emph{context} shared across sentences. An example of such a generative process would be to ``generate'' a representation of the document context using a background knowledge base. Then, semantic statements for each sentence in the document can be generated from this intermediate document-level representation in addition to other sources of document-level information. Finally, our grammar would generate sentences for each semantic statement. The problem of co-reference resolution also becomes more apparent in these settings with more complex sentences. In both the single-sentence and multiple-sentence settings, co-reference resolution can be integrated into parsing. Incorporating these extensions into a richer unified parsing framework would be promising.

\section*{Acknowledgments}

%The acknowledgments should go immediately before the references.  Do
%not number the acknowledgments section. Do not include this section
%when submitting your paper for review.

We thank Emmanouil A. Platanios and Jayant Krishnamurthy for the insightful discussion and helpful comments on the draft. We also thank anonymous reviewers for their feedback on the shortened version of this manuscript. This work was supported in part by NSF grant IIS1250956, and in part by DARPA DEFT contract FA87501320005.

\bibliographystyle{fullname}
\begin{thebibliography}{}

[1]
Adams, Beverly~Colwell, Laura~C. Bell, and Charles~A. Perfetti.
\newblock 1995.
\newblock A trading relationship between reading skill and domain knowledge in
children's text comprehension.
\newblock {\em Discourse Processes}, 20(3):307--323.

[2]
Aho, Albert~V. and Jeffery~D. Ullman.
\newblock 1972.
\newblock {\em The Theory of Parsing, Translation, and Compiling}, volume~1.
\newblock Prentice-Hall, Englewood Cliffs, NJ.

[3]
Aldous, David~J.
\newblock 1985.
\newblock Exchangeability and related topics.
\newblock In {\em \'{E}cole d'\'et\'e de probabilit\'es de {S}aint-{F}lour,
{XIII}---1983}, volume 1117 of {\em Lecture Notes in Math.} Springer, Berlin,
pages 1--198.

[4]
Anderson, Richard~C. and P.~David Pearson.
\newblock 1984.
\newblock {\em A schema-theoretic view of basic processes in reading
\newblock University of Illinois at Urbana-Champaign Champaign, Ill. : Bolt,
Beranek, and Newman Inc.

[5]
Baker, Collin~F., Charles~J. Fillmore, and John~B. Lowe.
\newblock 1998.
\newblock The berkeley {FrameNet} project.
\newblock In {\em Proceedings of the 17th International Conference on
Computational Linguistics}, volume~1, pages 86--90, Montreal, Quebec, Canada.
Association for Computational Linguistics.

[6]
Banarescu, Laura, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt,
Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan
\newblock 2013.
\newblock Abstract meaning representation for sembanking.

[7]
Berger, Adam, Stephen~Della Pietra, and Vincent~Della Pietra.
\newblock 1996.
\newblock A maximum entropy approach to natural language processing.
\newblock {\em Computational Linguistics}, 22:39--71.

[8]
Bloom, Paul.
\newblock 2000.
\newblock {\em How Children Learn the Meanings of Words}.
\newblock MIT Press, Cambridge, MA.

[9]
Bordes, Antoine, Xavier Glorot, Jason Weston, and Yoshua Bengio.
\newblock 2012.
\newblock Joint learning of words and meaning representations for open-text
semantic parsing.
\newblock In Neil~D. Lawrence and Mark Girolami, editors, {\em AISTATS},
volume~22 of {\em JMLR Proceedings}, pages 127--135. JMLR.org.

[10]
Callan, Jamie, Mark Hoy, Changkuk Yoo, and Le~Zhao.
\newblock 2009.
\newblock The clueweb09 dataset.

[11]
Chomsky, N., editor.
\newblock 1957.
\newblock {\em Syntactic structures}.
\newblock Mouton \& Co., The {H}ague.

[12]
Chomsky, Noam.
\newblock 1956.
\newblock Three models for the description of language.
\newblock {\em IRE Transactions on Information Theory}, 2:113--124.

[13]
Church, A.
\newblock 1932.
\newblock A set of postulates for the foundation of logic part i.
\newblock {\em Annals of Mathematics}, 33(2):346--366.

[14]
Cohen, Shay~B., David~M. Blei, and Noah~A. Smith.
\newblock 2010.
\newblock Variational inference for adaptor grammars.
\newblock In {\em HLT-NAACL}, pages 564--572. The Association for Computational

[15]
Durrett, Greg and Dan Klein.
\newblock 2014.
\newblock A joint model for entity analysis: Coreference, typing, and linking.
\newblock {\em TACL}, 2:477--490.

[16]
Earley, Jay.
\newblock 1970.
\newblock An efficient context-free parsing algorithm.
\newblock {\em Communications of the ACM}, 6(8):451--455.
\newblock Reprinted in Grosz et al. (1986).

[17]
Ferguson, Thomas~S.
\newblock 1973.
\newblock A {B}ayesian analysis of some nonparametric problems.
\newblock {\em The Annals of Statistics}, 1(2):209--230.

[18]
Fincher-Kiefer, Rebecca.
\newblock 1992.
\newblock The role of prior knowledge in inferential processing.
\newblock {\em Journal of Research in Reading}, 15:12--27.

[19]
Finkel, Jenny~Rose and Christopher~D. Manning.
\newblock 2009.
\newblock Joint parsing and named entity recognition.
\newblock In {\em HLT-NAACL}, pages 326--334. The Association for Computational

[20]
Finkel, Jenny~Rose and Christopher~D. Manning.
\newblock 2010.
\newblock Hierarchical joint learning: Improving joint parsing and named entity
recognition with non-jointly labeled data.
\newblock In Jan Hajic, Sandra Carberry, and Stephen Clark, editors, {\em ACL},
pages 720--728. The Association for Computer Linguistics.

[21]
Gallo, Giorgio, Giustino Longo, and Stefano Pallottino.
\newblock 1993.
\newblock Directed hypergraphs and applications.
\newblock {\em Discrete Applied Mathematics}, 42(2):177--201.

[22]
Gelfand, Alan~E. and Adrian F.~M. Smith.
\newblock 1990.
\newblock Sampling-based approaches to calculating marginal densities.
\newblock {\em Journal of the American Statistical Association},

[23]
Hockenmaier, Julia.
\newblock 2001.
\newblock Statistical parsing for ccg with simple generative models.
\newblock In {\em ACL (Companion Volume)}, pages 7--12. CNRS, Toulose, France.

[24]
Hockenmaier, Julia and Mark Steedman.
\newblock 2002.
\newblock Generative models for statistical parsing with combinatory categorial
\newblock In {\em ACL}, pages 335--342. ACL.

[25]
J{\"a}ger, Gerhard.
\newblock 2004.
\newblock {\em Anaphora and type logical grammar}.
\newblock Universitätsbibliothek Johann Christian Senckenberg.

[26]
Johnson, Mark and Katherine Demuth.
\newblock 2010.
\newblock Unsupervised phonemic chinese word segmentation using adaptor
\newblock In Chu-Ren Huang and Dan Jurafsky, editors, {\em COLING}, pages
528--536. Tsinghua University Press.

[27]
Johnson, Mark, Thomas~L. Griffiths, and Sharon Goldwater.
\newblock 2007.
\newblock Adaptor grammars: A framework for specifying compositional
nonparametric {B}ayesian models.
\newblock In {\em Advances in Neural Information Processing Systems (NIPS)}.

[28]
Kazama, Jun'ichi and Kentaro Torisawa.
\newblock 2007.
\newblock Exploiting wikipedia as external knowledge for named entity
\newblock In {\em Joint Conference on Empirical Methods in Natural Language
Processing and Computational Natural Language Learning}, pages 698--707.

[29]
Kim, J. and D.~Moldovan.
\newblock 1995.
\newblock Acquisition of linguistic patterns for knowledge-based information
\newblock {\em IEEE Transactiops on Knowledge and Data Engineering},

[30]
Klein, Dan and Christopher~D. Manning.
\newblock 2001.
\newblock Parsing and hypergraphs.
\newblock In {\em IWPT}. Tsinghua University Press.

[31]
Klein, Dan and Christopher~D. Manning.
\newblock 2003a.
\newblock A* parsing: Fast exact viterbi parse selection.
\newblock In {\em HLT-NAACL}.

[32]
Klein, Dan and Christopher~D. Manning.
\newblock 2003b.
\newblock Fast exact inference with a factored model for natural language
\newblock In {\em In Advances in Neural Information Processing Systems 15

[33]
Krishnamurthy, Jayant and Tom~M. Mitchell.
\newblock 2014.
\newblock Joint syntactic and semantic parsing with combinatory categorial
\newblock In {\em Proceedings of the 52nd Annual Meeting of the Association for
Computational Linguistics (Volume 1: Long Papers)}, pages 1188--1198,
Baltimore, Maryland, June. Association for Computational Linguistics.

[34]
Li, Junhui, Muhua Zhu, Wei Lu, and Guodong Zhou.
\newblock 2015.
\newblock Improving semantic parsing with enriched synchronous context-free
\newblock In Llu\'{i}s M\`{a}rquez, Chris Callison-Burch, Jian Su, Daniele
Pighin, and Yuval Marton, editors, {\em EMNLP}, pages 1455--1465. The
Association for Computational Linguistics.

[35]
Liang, Percy, Michael~I. Jordan, and Dan Klein.
\newblock 2013.
\newblock Learning dependency-based compositional semantics.
\newblock {\em Computational Linguistics}, 39(2):389--446.

[36]
Merlo, Paola and Gabriele Musillo.
\newblock 2008.
\newblock Semantic parsing for high-precision semantic role labelling.
\newblock In Alexander Clark and Kristina Toutanova, editors, {\em CoNLL},
pages 1--8. ACL.

[37]
Mitchell, T., W.~Cohen, E.~Hruscha, P.~Talukdar, J.~Betteridge, A.~Carlson,
B.~Dalvi, M.~Gardner, B.~Kisiel, J.~Krishnamurthy, N.~Lao, K.~Mazaitis,
T.~Mohammad, N.~Nakashole, E.~Platanios, A.~Ritter, M.~Samadi, B.~Settles,
R.~Wang, D.~Wijaya, A.~Gupta, X.~Chen, A.~Saparov, M.~Greaves, and
\newblock 2015.
\newblock Never-ending learning.
\newblock In {\em AAAI}.
\newblock : Never-Ending Learning in AAAI-2015.

[38]
Nakashole, Ndapandula and Tom~M. Mitchell.
\newblock 2015.
\newblock A knowledge-intensive model for prepositional phrase attachment.
\newblock In {\em ACL (1)}, pages 365--375. The Association for Computer

[39]
Ng, Vincent.
\newblock 2007.
\newblock Shallow semantics for coreference resolution.
\newblock In {\em IJCAI}, pages 1689--1694.

[40]
Pauls, Adam and Dan Klein.
\newblock 2009.
\newblock K-best a* parsing.
\newblock In Keh-Yih Su, Jian Su, and Janyce Wiebe, editors, {\em ACL/IJCNLP},
pages 958--966. The Association for Computer Linguistics.

[41]