Spectral Unsupervised Parsing with Additive Tree Metrics

Let $𝒘=\left(w_1,\mathrm{\dots },w_{\mathrm{\ell }}\right)$ be a vector of words corresponding to a sentence of length $\mathrm{\ell }$. Each $w_i$ is represented by a vector in ${ℝ}^p$ for $p\in \mathbb{N}$. The vector is an embedding of the word in some space, chosen from a fixed dictionary that maps word types to ${ℝ}^p$. In addition, let $𝒙=\left(x_1,\mathrm{\dots },x_{\mathrm{\ell }}\right)$ be the associated vector of part-of-speech (POS) tags (i.e. $x_i$ is the POS tag of $w_i$).

In our learning algorithm, we assume that examples of the form $\left({𝒘}^{\left(i\right)},{𝒙}^{\left(i\right)}\right)$ for $i\in \left[N\right]=\left\{1,\mathrm{\dots },N\right\}$ are given, and the goal is to predict a bracketing parse tree for each of these examples. The word embeddings are used during the learning process, but the final decoder that the learning algorithm outputs maps a POS tag sequence $𝒙$ to a parse tree. While ideally we would want to use the word information in decoding as well, much of the syntax of a sentence is determined by the POS tags, and relatively high level of accuracy can be achieved by learning, for example, a supervised parser from POS tag sequences.

Just like our decoder, our model assumes that the bracketing of a given sentence is a function of its POS tags. The POS tags are generated from some distribution, followed by a deterministic generation of the bracketing parse tree. Then, latent states are generated for each bracket, and finally, the latent states at the yield of the bracketing parse tree generate the words of the sentence (in the form of embeddings). The latent states are represented by vectors $z\in {ℝ}^m$ where .

For intuition, consider the simple tag sequence $𝒙=\left(\mathrm{𝚅𝙱𝙳},\mathrm{𝙳𝚃},\mathrm{𝙽𝙽}\right)$. Two candidate constituent parse structures are shown in Figure 2 and the correct one is boxed in green (the other in red). Recall that our training data contains word phrases that have the tag sequence $𝒙$ e.g. ${𝒘}^{\left(1\right)}=\left(\mathrm{𝚑𝚒𝚝},\mathrm{𝚝𝚑𝚎},\mathrm{𝚋𝚊𝚕𝚕}\right)$, ${𝒘}^{\left(2\right)}=\left(\mathrm{𝚊𝚝𝚎},\mathrm{𝚊𝚗},\mathrm{𝚊𝚙𝚙𝚕𝚎}\right)$.

Intuitively, the words in the above phrases exhibit dependencies that can reveal the parse structure. The determiner ($w_2$) and the direct object ($w_3$) are correlated in that the choice of determiner depends on the plurality of $w_3$. However, the choice of verb ($w_1$) is mostly independent of the determiner. We could thus conclude that $w_2$ and $w_3$ should be closer in the parse tree than $w_1$ and $w_2$, giving us the correct structure. Informally, the latent state $z$ corresponding to the $\left(w_2,w_3\right)$ bracket would store information about the plurality of $z$, the key to the dependence between $w_2$ and $w_3$. It would then be reasonable to assume that $w_2$ and $w_3$ are independent given $z$.

Following this intuition, we propose to model the distribution over the latent bracketing states and words for each tag sequence $𝒙$ as a latent tree graphical model, which encodes conditional independences among the words given the latent states.

Let $𝒱:=\left\{w_1,\mathrm{\dots },w_{\mathrm{\ell }},z_1,\mathrm{\dots },z_H\right\}$, with $w_i$ representing the word embeddings, and $z_i$ representing the latent states of the bracketings. Then, according to our base model it holds that:

where ${\pi }_{𝒙}(\cdot )$ returns the parent node index of the argument in the latent tree corresponding to tag sequence $𝒙$.¹¹At this point, $\pi$ refers to an arbitrary direction of the undirected tree $u\left(𝒙\right)$. If $z$ is the root, then ${\pi }_{𝒙}\left(z\right)=\mathrm{\varnothing }$. All the $w_i$ are assumed to be leaves while all the $z_i$ are internal (i.e. non-leaf) nodes. The parameters $\theta \left(𝒙\right)$ control the conditional probability tables. We do not commit to a certain parametric family, but see more about the assumptions we make about $\theta$ in §3.2. The parameter space is denoted $\mathrm{\Theta }$. The model assumes a factorization according to a latent-variable tree. The latent variables can incorporate various linguistic properties, such as head information, valence of dependency being generated, and so on. This information is expected to be learned automatically from data.

Our generative model deterministically maps a POS sequence to a bracketing via an undirected latent-variable tree. The orientation of the tree is determined by a direction mapping $h_{\mathrm{dir}}\left(u\right)$, which is fixed during learning and decoding. This means our decoder first identifies (given a POS sequence) an undirected tree, and then orients it by applying $h_{\mathrm{dir}}$ on the resulting tree (see below).

Define $𝒰$ to be the set of undirected latent trees where all internal nodes have degree exactly $3$ (i.e. they correspond to binary bracketing), and in addition $h_{\mathrm{dir}}\left(u\right)$ for any $u\in 𝒰$ is projective (explained in the $h_{\mathrm{dir}}$ section). In addition, let $𝒯$ be the set of binary bracketings. The complete generative model that we follow is then:

• •

  Generate a tag sequence $𝒙=\left(x_1,\mathrm{\dots },x_{\mathrm{\ell }}\right)$

• •

  Decide on $u\left(𝒙\right)\in 𝒰$, the undirected latent tree that $𝒙$ maps to.

• •

  Set $t\in 𝒯$ by computing $t=h_{\mathrm{dir}}\left(u\right)$.

• •

  Set $\theta \in \mathrm{\Theta }$ by computing $\theta =\theta \left(𝒙\right)$.

• •

  Generate a tuple $𝒗=\left(w_1,\mathrm{\dots },w_{\mathrm{\ell }},z_1,\mathrm{\dots },z_H\right)$ where $w_i\in {ℝ}^p,z_j\in {ℝ}^m$ according to Eq. 1.

See Figure 1 (left) for an example.

Let $u\left(𝒙\right)$ be the true undirected tree of sentence $𝒙$ and assume the nodes $𝒱$ to be indexed by $\left[M\right]=\left\{1,\mathrm{\dots },M\right\}$ such that $M=\left|𝒱\right|=H+\mathrm{\ell }$. Furthermore, let $v\in 𝒱$ refer to a node in the undirected tree (either observed or latent). We assume the existence of a distance function that allows us to compute distances between pairs of nodes. For example, as we see in §3.2 we will define the distance $d\left(i,j\right)$ to be a function of the covariance matrix $𝔼\left[v_i{v}_j^{\top }\right|u\left(𝒙\right),\theta \left(𝒙\right)]$. Thus if $v_i$ and $v_j$ are both observed variables, the distance can be directly computed from the data.

Moreover, the metrics we construct are such that they are tree additive, defined below:

As we describe below, given the tree structure, the additive tree metric property allows us to compute “backwards” the distances among the latent variables as a function of the distances among the observed variables.

Define $𝑫$ to be the $M\times M$ distance matrix among the $M$ variables, i.e. $D_{ij}=d_{u\left(𝒙\right)}\left(i,j\right)$. Let ${𝑫}_{WW}$, ${𝑫}_{ZW}$ (equal to ${𝑫}_{WZ}^{\top }$), and ${𝑫}_{ZZ}$ indicate the word-word, latent-word and latent-latent sub-blocks of $𝑫$ respectively. In addition, since $u\left(𝒙\right)$ is assumed to be known from context, we denote $d_{u\left(𝒙\right)}\left(i,j\right)$ just by $d\left(i,j\right)$.

Given the fact that the distance between a pair of nodes is a function of the random variables they represent (according to the true model), only ${𝑫}_{WW}$ can be empirically estimated from data. However, if the underlying tree structure is known, then Definition 1 can be leveraged to compute ${𝑫}_{ZZ}$ and ${𝑫}_{ZW}$ as we show below.

We first show how to compute $d\left(i,j\right)$ for all $i,j$ such that $i$ and $j$ are adjacent to each other in $u\left(𝒙\right)$, based only on observed nodes. It then follows that the other elements of the distance matrix can be computed based on Definition 1. To show how to compute distances between adjacent nodes, consider the two cases: (1) $\left(i,j\right)$ is a leaf edge; (2) $\left(i,j\right)$ is an internal edge.

In constructing our distance metric, we begin with the following assumption on the distribution in Eq. 1 (analogous to the assumptions made in Anandkumar et al., 2011).

Note that the matrices $𝑨$ and $𝑪$ are a direct function of $\theta \left(𝒙\right)$, but we do not specify a model family for $\theta \left(𝒙\right)$. The only restriction is in the form of the above assumption. If $w_i$ and $z_i$ were discrete, represented as binary vectors, the above assumption would correspond to requiring all conditional probability tables in the latent tree to have rank $m$. Assumption 1 allows for the $w_i$ to be high dimensional features, as long as the expectation requirement above is satisfied. Similar assumptions are made with spectral parameter learning methods e.g. Hsu et al.2009, Bailly et al.2009, Parikh et al.2011, and Cohen et al.2012.

Furthermore, Assumption 1 makes it explicit that regardless of the size of $p$, the relationships among the variables in the latent tree are restricted to be of rank $m$, and are thus low rank since $p>m$. To leverage this low rank structure, we propose using the following additive metric, a normalized variant of that in Anandkumar et al.2011:

where ${\mathrm{\Lambda }}_m\left(𝑨\right)$ denotes the product of the top $m$ singular values of $𝑨$ and ${𝚺}_{𝒙}(i,j):=𝔼\left[v_i{v}_j^{\top }\right|𝒙]$, i.e. the uncentered cross-covariance matrix.

We can then show that this metric is additive:

A proof is in the supplementary for completeness. From here, we use $d$ to denote $d^{\mathrm{spectral}}$, since that is the metric we use for our learning algorithm.

It has been shown [Rzhetsky and Nei1993] that for any additive tree metric, $u\left(𝒙\right)$ can be recovered by solving $\arg {min}_{u\in 𝒰}c\left(u\right)$ for $c\left(u\right)$:

where ${ℰ}_u$ is the set of pairs of nodes which are adjacent to each other in $u$ and $d\left(i,j\right)$ is computed using Eq. 3 and Eq. 4.

Note that the metric $d$ we use in defining $c\left(u\right)$ is based on the expectations from the true distribution. In practice, the true distribution is unknown, and therefore we use an approximation for the distance metric $\widehat{d}$. As we discussed in §3.1 all elements of the distance matrix are functions of observable quantities if the underlying tree $u$ is known. However, only the word-word sub-block ${𝑫}_{WW}$ can be directly estimated from the data without knowledge of the tree structure.

This subtlety makes solving the minimization problem in Eq. 6 NP-hard [Desper and Gascuel2005] if $u$ is allowed to be an arbitrary undirected tree. However, if we restrict $u$ to be in $𝒰$, as we do in the above, then maximizing $\widehat{c}\left(u\right)$ over $𝒰$ can be solved using the bilexical parsing algorithm from Eisner and Satta1999. This is because the computation of the other sub-blocks of the distance matrix only depend on the partitions of the nodes shown in Figure 3 into $A$, $B$, $G$, and $H$, and not on the entire tree structure.

Therefore, the procedure to find a bracketing for a given POS tag $𝒙$ is to first estimate the distance matrix sub-block ${\widehat{𝑫}}_{WW}$ from raw text data (see §3.4), and then solve the optimization problem $\arg {min}_{u\in 𝒰}\widehat{c}\left(u\right)$ using a variant of the Eisner-Satta algorithm where $\widehat{c}\left(u\right)$ is identical to $c\left(u\right)$ in Eq. 6, with $d$ replaced with $\widehat{d}$.

[t!]Inputs: Set of examples $\left({𝒘}^{\left(i\right)},{𝒙}^{\left(i\right)}\right)$ for $i\in \left[N\right]$, a kernel $K_{\gamma }(j,k,j^{\prime },k^{\prime }|𝒙,{𝒙}^{\prime })$, an integer $m$

Data structures: For each $i\in \left[N\right],j,k\in \mathrm{\ell }\left({𝒙}^{\left(i\right)}\right)$ there is a (uncentered) covariance matrix ${\widehat{𝚺}}_{{𝒙}^{\left(i\right)}}\left(j,k\right)\in {ℝ}^{p\times p}$, and a distance ${\widehat{d}}^{\mathrm{spectral}}\left(j,k\right)$.

Algorithm:

(Covariance estimation) $\forall i\in \left[N\right],j,k\in \mathrm{\ell }\left({𝒙}^{\left(i\right)}\right)$

• •

  Let $C_{j^{\prime },k^{\prime }|i^{\prime }}=w_{j^{\prime }}^{\left(i^{\prime }\right)}{\left(w_{k^{\prime }}^{\left(i^{\prime }\right)}\right)}^{\top }$, $k_{j,k,j^{\prime },k^{\prime },i,i^{\prime }}=K_{\gamma }(j,k,j^{\prime },k^{\prime }|{𝒙}^{\left(i\right)},{𝒙}^{\left(i^{\prime }\right)})$ and ${\mathrm{\ell }}_{i^{\prime }}=\mathrm{\ell }\left({𝒙}^{\left(i^{\prime }\right)}\right)$, and estimate each $p\times p$ covariance matrix as:

  	${\widehat{𝚺}}_{𝒙}\left(j,k\right)=$
  		${\displaystyle \frac{{\sum }_{i^{\prime }=1}^N{\sum }_{j^{\prime }=1}^{{\mathrm{\ell }}_{i^{\prime }}}{\sum }_{k^{\prime }=1}^{{\mathrm{\ell }}_{i^{\prime }}}{k}_{j,k,j^{\prime },k^{\prime },i,i^{\prime }}{C}_{j^{\prime },k^{\prime }|i^{\prime }}}{{\sum }_{i^{\prime }=1}^N{\sum }_{j^{\prime }=1}^{{\mathrm{\ell }}_{i^{\prime }}}{\sum }_{k^{\prime }=1}^{{\mathrm{\ell }}_{i^{\prime }}}{k}_{j,k,j^{\prime },k^{\prime },i,i^{\prime }}}}$

• •

  Compute ${\widehat{d}}^{\mathrm{spectral}}\left(j,k\right)\forall j,k\in \mathrm{\ell }\left({𝒙}^{\left(i\right)}\right)$ using Eq. 5.

(Uncover structure) $\forall i\in \left[N\right]$

• •

  Find ${\widehat{u}}^{\left(i\right)}=\arg {min}_{u\in 𝒰}\widehat{c}\left(u\right)$, and for the $i$th example, return the structure $h_{\mathrm{dir}}\left({\widehat{u}}^{\left(i\right)}\right)$.

The learning algorithm for finding the latent structure from a set of examples $\left({𝒘}^{\left(i\right)},{𝒙}^{\left(i\right)}\right)$, $i\in \left[N\right]$.

Summary. We first defined a generative model that describes how a sentence, its sequence of POS tags, and its bracketing is generated (§2.3). First an undirected $u\in 𝒰$ is generated (only as a function of the POS tags), and then $u$ is mapped to a bracketing using a direction mapping $h_{\mathrm{dir}}$. We then showed that we can define a distance metric between nodes in the undirected tree, such that minimizing it leads to a recovery of $u$. This distance metric can be computed based only on the text, without needing to identify the latent information (§3.2). If the true distance metric is known, with respect to the true distribution that generates the words in a sentence, then $u$ can be fully recovered by optimizing the cost function $c\left(u\right)$. However, in practice the distance metric must be estimated from data, as discussed below.

We now address the data sparsity problem, in particular that $𝒟\left(𝒙\right)$ can be very small, and therefore estimating $d$ for each POS sequence separately can be problematic.³³This data sparsity problem is quite severe – for example, the Penn treebank [Marcus et al.1993] has a total number of 43,498 sentences, with 42,246 unique POS tag sequences, averaging $\left|𝒟\left(𝒙\right)\right|$ to be 1.04.

In order to estimate $d$ from data, we need to estimate the covariance matrices ${𝚺}_{𝒙}\left(i,j\right)$ (for $i,j\in \left\{1,\mathrm{\dots },\mathrm{\ell }\left(𝒙\right)\right\}$) from Eq. 5.

To give some motivation to our solution, consider estimating the covariance matrix ${𝚺}_{𝒙}\left(1,2\right)$ for the tag sequence $𝒙=\left({\mathrm{𝙳𝚃}}_{\mathrm{𝟷}},{\mathrm{𝙽𝙽}}_{\mathrm{𝟸}},{\mathrm{𝚅𝙱𝙳}}_{\mathrm{𝟹}},{\mathrm{𝙳𝚃}}_{\mathrm{𝟺}},{\mathrm{𝙽𝙽}}_{\mathrm{𝟻}}\right)$. $𝒟\left(𝒙\right)$ may be insufficient for an accurate empirical estimate. However, consider another sequence ${𝒙}^{\prime }=\left({\mathrm{𝚁𝙱}}_{\mathrm{𝟷}},{\mathrm{𝙳𝚃}}_{\mathrm{𝟸}},{\mathrm{𝙽𝙽}}_{\mathrm{𝟹}},{\mathrm{𝚅𝙱𝙳}}_{\mathrm{𝟺}},{\mathrm{𝙳𝚃}}_{\mathrm{𝟻}},{\mathrm{𝙰𝙳𝙹}}_{\mathrm{𝟼}},{\mathrm{𝙽𝙽}}_{\mathrm{𝟽}}\right)$. Although $𝒙$ and ${𝒙}^{\prime }$ are not identical, it is likely that ${𝚺}_{{𝒙}^{\prime }}\left(2,3\right)$ is similar to ${𝚺}_{𝒙}\left(1,2\right)$ because the determiner and the noun appear in similar syntactic context. ${𝚺}_{{𝒙}^{\prime }}\left(5,7\right)$ also may be somewhat similar, but ${𝚺}_{{𝒙}^{\prime }}\left(2,7\right)$ should not be very similar to ${𝚺}_{𝒙}\left(1,2\right)$ because the noun and the determiner appear in a different syntactic context.

The observation that the covariance matrices depend on local syntactic context is the main driving force behind our solution. The local syntactic context acts as an “anchor,” which enhances or replaces a word index in a sentence with local syntactic context. More formally, an anchor is a function $G$ that maps a word index $j$ and a sequence of POS tags $𝒙$ to a local context $G\left(j,𝒙\right)$. The anchor we use is $G\left(j,𝒙\right)=\left(j,x_j\right)$. Then, the covariance matrices ${𝚺}_{𝒙}$ are estimated using kernel smoothing [Hastie et al.2009], where the smoother tests similarity between the different anchors $G\left(j,𝒙\right)$.

The full learning algorithm is given in Figure 3.3. The first step in the algorithm is to estimate the covariance matrix block ${\widehat{𝚺}}_{{𝒙}^{\left(i\right)}}\left(j,k\right)$ for each training example ${𝒙}^{\left(i\right)}$ and each pair of preterminal positions $\left(j,k\right)$ in ${𝒙}^{\left(i\right)}$. Instead of computing this block by computing the empirical covariance matrix for positions $\left(j,k\right)$ in the data $𝒟\left(𝒙\right)$, the algorithm uses all of the pairs $\left(j^{\prime },k^{\prime }\right)$ from all of $N$ training examples. It averages the empirical covariance matrices from these contexts using a kernel weight, which gives a similarity measure for the position $\left(j,k\right)$ in ${𝒙}^{\left(i\right)}$ and $\left(j^{\prime },k^{\prime }\right)$ in another example ${𝒙}^{\left(i^{\prime }\right)}$. $\gamma$ is the kernel “bandwidth”, a user-specified parameter that controls how inclusive the kernel will be with respect to examples in $𝒟$ (see § 4.1 for a concrete example). Note that the learning algorithm is such that it ensures that ${\widehat{𝚺}}_{{𝒙}^{\left(i\right)}}\left(j,k\right)={\widehat{𝚺}}_{{𝒙}^{\left(i^{\prime }\right)}}\left(j^{\prime },k^{\prime }\right)$ if $G\left(j,{𝒙}^{\left(i\right)}\right)=G\left(j^{\prime },{𝒙}^{\left(i^{\prime }\right)}\right)$ and $G\left(k,{𝒙}^{\left(i\right)}\right)=G\left(k^{\prime },{𝒙}^{\left(i^{\prime }\right)}\right)$.

Once the empirical estimates for the covariance matrices are obtained, a variant of the Eisner-Satta algorithm is used, as mentioned in §3.3.

Our main theoretical guarantee is that Algorithm 1 will recover the correct tree $u\in 𝒰$ with high probability, if the given top bracket is correct and if we obtain enough examples $\left({𝒘}^{\left(i\right)},{𝒙}^{\left(i\right)}\right)$ from the model in §2. We give the theorem statement below. The constants lurking in the $O$-notation and the full proof are in the supplementary.

Denote ${\sigma }_{𝒙}{\left(j,k\right)}^{\left(r\right)}$ as the $r^{th}$ singular value of ${𝚺}_{𝒙}\left(j,k\right)$. Let ${\sigma }^{\ast }\left(x\right):={min}_{j,k\in \mathrm{\ell }\left(𝒙\right)}min\left({\sigma }_{𝒙}{\left(j,k\right)}^{\left(m\right)}\right)$.

where ${\nu }_{𝒙}\left(\gamma \right)$, defined in the supplementary, is a function of the underlying distribution over the tag sequences $𝒙$ and the kernel bandwidth $\gamma$.

Thus, the sample complexity of our approach depends on the dimensionality of the latent and observed states ($m$ and $p$), the underlying singular values of the cross-covariance matrices (${\sigma }^{\ast }\left(𝒙\right)$) and the difference in the cost of the true tree compared to the cost of the incorrect trees ($\mathrm{△}\left(𝒙\right)$).