3.1 Overview

Having sketched our concepts of lexical and relational similarity, we proceed in this section to provide technical details of the methods we use to implement them. Kernel methods is the name given to a statistical modelling paradigm in which data items are viewed by the learning algorithm in terms of their similarity to other items (Shawe-Taylor and Cristianini Reference Shawe-Taylor and Cristianini2004). This similarity is captured through a function known as the kernel function (or simply kernel). Kernel-based learning has a number of advantages, including the facilitation of efficient methods for non-linear classification and classification with complex feature spaces, and has become very popular in NLP and many other disciplines. Furthermore, kernel algorithms are modular in the sense that switching to a new kernel does not require a new learning algorithm. While traditional feature-based learning can also exploit rich feature mappings, one cannot simply ‘slot in’ a new inner product geometry as we do here without altering the learning algorithm.

A kernel is a function $k:\mathcal {X}\times \mathcal {X}\mapsto {\mathbb {R}}_+$ which is equivalent to an inner product $\langle \cdot ,\cdot \rangle _\mathcal {F}$ in some inner product space $\mathcal {F}$ (the feature space):

(1) \begin{equation} k(\mathbf {x}_i,\mathbf {x}_j) = \langle \phi (\mathbf {x}_i),\phi (\mathbf {x}_j) \rangle _\mathcal {F} \end{equation}

(2) \begin{equation} \mathbf {v}^{\prime}K\mathbf {v} \ge 0, \forall \mathbf {v} \in {\mathbb {R}}^n \end{equation}

$\mathcal {X}$

$\mathcal {F}$

$\binom{d+l}{l} = 10$

$X = \lbrace \mathbf {x}_1, \mathbf {x}_2,\dots , \mathbf {x}_n \in \mathcal {X}\rbrace$

$\mathcal {X}$

$X \subseteq \mathcal {X}$

$\langle \cdot ,\cdot \rangle _{{\mathbb {R}}^d}$

$k = \operatorname{exp}(-\beta \sum _d (x_{id} - x_{jd})^2)$

$\mathcal {X}$

Given training data X={x₁, . . ., x_n} drawn identically and independently from some set $\mathcal {X}$, with corresponding labels Y={y ₁, . . ., y_n} belonging to a set $\mathcal {Y}$, the supervised classification task is to learn a function $f:\mathcal {X}\mapsto \mathcal {Y}$ that best predicts the unknown label y_j for a data point $\mathbf {x}_j \in \mathcal {X}$ that was not seen in training. In order to render learning feasible, f is usually restricted to a particular functional class; for binary classification (i.e. $\mathcal {Y} = \lbrace -1,1\rbrace$) we might define $f(\mathbf {x}) = \operatorname{sign}g(\mathbf {x})$, where $g:\mathcal {X}\mapsto {\mathbb {R}}$ belongs to the class of linear functions:

(3) \begin{align} g(\mathbf {x}) &= \langle \mathbf {w},\phi (\mathbf {x}) \rangle _{{\mathbb {R}}^d} + b \end{align}

(4) \begin{align} &= \sum _i w_i \phi (\mathbf {x})_i + b \end{align}

$\phi:\mathcal {X}\mapsto {\mathbb {R}}^d$

$\langle \cdot ,\cdot \rangle _{{\mathbb {R}}^d}$

${\mathbb {R}}^d$

$\langle \mathbf {w},\phi (\mathbf {x}) \rangle _{{\mathbb {R}}^d} = 0$

${\mathbb {R}}^d$

A dataset is linearly separable if a hyperplane exists such that all instances with label –1 are on one side and all instances with label 1 are on the other. Linear separability is usually an unrealistic condition for complex problems. The support vector machine (SVM) is a classifier that aims to find the ‘best’ decision boundary in the sense that violations of the boundary are minimised and the separation between classes (the ‘margin’) is maximised (Cortes and Vapnik Reference Cortes and Vapnik1995). The (dual) SVM optimisation problem is:

(5) \begin{align} {\mathbf {\alpha}}^* = \operatorname{argmax}_{\mathbf \alpha} W({\mathbf \alpha}) &= -\sum _{i=1}^n\sum _{j=1}^n \alpha _i\alpha _jy_iy_j\phi (\mathbf {x}_i)\phi (\mathbf {x}_j) \\ \mathrm{subject\ to}\ \ &\sum_{i=1}^ny_i\alpha _i = 0,\ \sum _{i=1}^n \alpha _i = 1,\nonumber \\ & 0 \le \alpha _i \le C,\ \mathrm{for\ all}\ i=1,\dots ,l\nonumber \end{align}

(6) \begin{equation} W({\mathbf \alpha}) = -\sum _{i=1}^n\sum _{j=1}^n \alpha _i\alpha _jy_iy_jk(\mathbf {x}_i,\mathbf {x}_j) \end{equation}

$\phi (\mathbf {x}_i)\phi (\mathbf {x}_j) = \langle \mathbf {x}_i,\mathbf {x}_j \rangle _{\mathcal {F}}$

$\mathcal {X}$

$f(\mathbf {x}) = \mathrm{sign}(\langle \mathbf {w},\phi (\mathbf {x}) \rangle _\mathcal {F} + b)$

$\mathcal {F}$

$\mathcal {X}$

Support vector machines have been shown to achieve state-of-the-art performance on a great number of classification problems in NLP and other fields. Good performance with SVMs is contingent on the choice of an appropriate kernel function. The kernel chosen determines both the feature mapping φ and the inner product used to compare data points in feature space. If a kernel function induces a mapping into a space where the data classes are well separated, then learning a decision boundary in that space will be easy. Conversely, if the feature space mapping of the data does not contain discriminative information, SVM classification will perform poorly. Hence, if we can use a kernel function tailored to the prior knowledge we have about our classification problem, we expect to do better than we would with a less appropriate kernel. In the following sections we discuss how our intuitions about lexical and relational similarity can be applied to improve performance on the compound classification task.

3.2 Kernels on probability distributions

The most commonly used kernels on vectors of real numbers (including co-occurrence vectors) are the linear and Gaussian kernels. It can be shown that these kernels are related to the Euclidean L ₂ distance by two transformations that relate positive semi-definite kernels k to squared metrics $\tilde{k}$, also known as negative semi-definite kernels (Berg, Christensen and Ressel Reference Berg, Christensen and Ressel1984):

(7a) \begin{align} k(\mathbf {x}_i,\mathbf {x}_j) &= \tilde{k}(\mathbf {x}_i,\mathbf {x}_0) + \tilde{k}(\mathbf {x}_j,\mathbf {x}_0) - \tilde{k}(\mathbf {x}_i,\mathbf {x}_j) - \tilde{k}(\mathbf {x}_0,\mathbf {x}_0),\ \mathbf {x}_0 \in \mathcal {X}\ \mathrm{(linear)} \end{align}

(7b) \begin{align} k(\mathbf {x}_i,\mathbf {x}_j) &= \exp (-\beta \cdot \tilde{k}(\mathbf {x}_i,\mathbf {x}_j)),\ \beta > 0 \ \mathrm{(RBF)} \end{align}

(8) \begin{align} k_{L_2 (\text{linear})}(\mathbf {x_i},\mathbf {x_j}) &= \sum _i x_{ii}x_{ji} \end{align}

(9) \begin{align} k_{L_2 (\text{RBF})}(\mathbf {x_i},\mathbf {x_j}) &= \operatorname{exp}\left(-\beta \cdot \tilde{k}_{L_2}(\mathbf {p},\mathbf {q})\right) \end{align}

$\tilde{k}$

$\tilde{k}_{L_2} = \sum _d(x_{id} - x_{jd})^2$

Research on distributional lexical semantics has shown that the L ₂ distance performs relatively poorly compared with other distance and similarity measures (Lee Reference Lee1999). Hein and Bousquet (Reference Hein and Bousquet2005) describe a family of kernels that relate to well-known distance measures on probability distributions, including the Jensen–Shannon Divergence (JSD), L ₁ distance and Hellinger Divergence, using the transformations (7a) and (7b). Ó Séaghdha and Copestake (Reference Ó Séaghdha and Copestake2008) observe that these kernels include a number of well-established distributional similarity measures and demonstrate empirically that performance on classification tasks involving lexical similarity can be improved by using such distributional kernels. A representative example is the JSD

(10) \begin{equation} \tilde{k}_{\text{JSD}}(\mathbf {p},\mathbf {q}) = \sum _i p_i \log _2 \left(\frac{2p_i}{p_i+q_i} \right) + q_i \log _2 \left(\frac{2q_i}{p_i+q_i} \right) \end{equation}

(11a) \begin{align} k_{\text{JSD} (\text{linear})}(\mathbf {p},\mathbf {q}) &= - \sum _i p_i \log _2 \left(\frac{p_i}{p_i+q_i} \right) + q_i \log _2 \left(\frac{q_i}{p_i+q_i} \right) \end{align}

(11b) \begin{align} k_{\text{JSD} (\text{RBF})}(\mathbf {p},\mathbf {q}) &= \operatorname{exp}\left(-\beta \cdot \tilde{k}_{\text{JSD}}(\mathbf {p},\mathbf {q}\right) \end{align}

To compare two words w, w′ with a distributional kernel, we compare their estimated co-occurrence distributions. As our goal is to apply distributional kernels to compound interpretation, we must proceed from comparing individual words to comparing pairs of words. A lexical kernel on compounds can be defined as the normalised sum of a kernel function on heads and a kernel function on modifiers:

(12) \begin{equation} k_{\text{lex}}((w_m,w_h),(w_m^{\prime},w_h^{\prime})) = \frac{1}{2}k(w_m,w_m^{\prime}) + \frac{1}{2}k(w_h,w_h^{\prime}) \end{equation}

The development of new kernels on distributions is an area of active research in the machine learning community. In addition to the family of kernels described by Hein and Bousquet (Reference Hein and Bousquet2005), further distributional kernels have been proposed by Lafferty and Lebanon (Reference Lafferty and Lebanon2005), Martins et al. (Reference Martins, Smith, Xing, Aguiar and Figueiredo2009) and Agarwal and Daumé III (Reference Agarwal and Daumé2011). The experiments described in Ó Séaghdha (Reference Ó Séaghdha2008) and preliminary experiments on some of these more recent proposals suggest that while most of these distributional kernels consistently outperform Euclidean linear and RBF kernels, their performance on semantic classification tasks is often similar. As the focus of this paper is on integrating semantic information sources rather than a comprehensive investigation of alternative kernels on distributions, we use only the L ₂ (8) and JSD (11a) linear kernels in our experiments.

3.3 Kernels on strings and sets

The necessary starting point for our implementation of relational similarity is a means of comparing contexts. Contexts can be represented in a variety of ways, from unordered bags of words to rich syntactic structures. The context representation adopted here is based on strings, which preserve useful information about the order of words in the context yet can be processed and compared quite efficiently. String kernels are a family of kernels that compare strings s, t by mapping them into feature vectors $\phi _{\text{String}}(\mathbf {s})$, $\phi _{\text{String}}(\mathbf {t})$ whose non-zero elements index the subsequences contained in each string. Once an embedding is defined, any inner product can be used to compare items.

A string is defined as a finite sequence s=(s ₁, . . ., s_l) of symbols belonging to an alphabet Σ. Σ^l is the set of all strings of length l, and Σ* is the set of all strings or the language. A subsequence u of s is defined by a sequence of indices i=(i ₁, . . ., i _|u|) such that 1≤i ₁<. . .<i _|u|≤|s|, where |s| is the length of s. len(i)=i _|u|−i ₁+1 is the length of the subsequence in s. An embedding $\phi _{\text{String}}:\Sigma ^*\rightarrow {\mathbb {R}}^{|\Sigma |^l}$ is a function that maps a string s onto a vector of positive ‘counts’ that correspond to subsequences of exactly l symbols contained in s.

One example of an embedding function is a gap-weighted embedding, which incorporates information about non-contiguous as well as contiguous subsequences. This is an intuitively useful property for semantic classification, as words in a sentence need not be adjacent to be semantically related. The gap-weighted embedding is defined as

(13) \begin{equation} \phi _{\text{gap}_l}(\mathbf {s}) = \left[ \sum _{\mathbf {i}:\mathbf {s}[\mathbf {i}] = \mathbf {u}} \lambda ^{len(\mathbf {i})} \right]_{\mathbf {u} \in \Sigma ^l} \end{equation}

An alternative embedding is that used by Turney (Reference Turney2008) in his PairClass system for analogical classification. For the PairClass embedding $\phi _{\text{PC}}$, an n-word context

\begin{equation*} [0-1\ \mathrm{words}]\ N_{1|2}\ [0-3\ \mathrm{words}]\ N_{1|2}\ [0-1\ \mathrm{words}] \end{equation*}

Relational similarity relies on comparing sets of contexts, i.e. sets of strings. In order to derive useful kernels on such sets, we use an embedding function for sets that uses an embedding of set members as a building block. A natural approach is to map a set to the normalised aggregate of the embeddings of its members:

(14) \begin{equation} \phi _{\text{Set}}(A) = \frac{1}{Z}\sum _{\mathbf {s}\in A}\phi _{\text{String}}(\mathbf {s}) \end{equation}

(15) \begin{equation} k_{\text{rel}}((w_m,w_h),(w_m^{\prime},w_h^{\prime})) = k_{\text{JSD}(\text{linear})}\left(\phi _{\text{Set}}(S(w_m,w_h)),\phi _{\text{Set}}(S(w_m^{\prime},w_h^{\prime}))\right) \end{equation}

$\phi _{\text{Set}}(A)$

$\phi _{\text{gap}_l}$

$\phi _{\text{PC}}$

3.4 Kernel combination

The set of kernels is closed under addition and multiplication by a positive scalar (Shawe-Taylor and Cristianini Reference Shawe-Taylor and Cristianini2004). It follows that a linear combination of l kernels with positive weights μ is also a valid kernel:

(16) \begin{equation} k_{\text{comb}}(\mathbf {x}_i,\mathbf {x}_j) = \sum _l \mu _l k_l(\mathbf {x}_i,\mathbf {x}_j), {\mathbf \mu} \in {\mathbb {R}}_+^l \end{equation}

Multiple kernel learning (MKL) is the name usually given to the task of optimising the combination weights in (16). Finding the best μ is a non-trivial optimisation problem for more than a small number of kernels, as it is not practical to perform an exhaustive search. As far as we are aware, multiple kernel learning methods have not previously been applied in NLP research; we performed experiments using a multiclass adaptation of the two-stage algorithm proposed by Cortes, Mohri and Rostamizadeh (Reference Cortes, Mohri and Rostamizadeh2010), but our findings were inconclusive. Multiple kernel learning can give a small boost in performance but it is not always reliable, especially for larger label sets, and our best results were achieved through uniform weighting.

4.1 Compound dataset

Our experiments use the dataset of 1,443 unique two-noun English compounds described at length in Ó Séaghdha (Reference Ó Séaghdha2008). These compounds were randomly sampled from a collection of 430,555 types (covering over 1.5 million tokens) harvested from the written component of the British National Corpus (BNC) (Burnard Reference Burnard1995) and annotated in context for their semantic relations. The inventory of semantic relations consists of six coarse-grained relations: BE, HAVE, IN, ACTOR, INST(RUMENT) and ABOUT. Each is a binary relation; a compound expressing a particular relation is assumed to fill one argument slot with its head and the other with its modifier. With the exception of BE, the argument slots for each relation are semantically distinct and it is useful to note which constituent fills which slot. Thus, pig pen would be labelled IN _(M,H) as the head denotes the location and the modifier denotes the located entity; pen pig would be labelled IN _(H,M) as the head and modifier roles are reversed.

Furthermore, each compound in the dataset is annotated with the annotation rule that licenses the assignment of its coarse-grained label. For example, the rules licensing IN distinguish between spatially located objects (pig pen), spatially located events (air disaster), temporally located objects (evening edition) and temporally located events (dawn attack). The table in Appendix A summarises the various annotation rules and their distribution over the dataset. The design of the inventory was motivated by a desire to avoid inconsistent or overlapping relations and by a concern for general linguistic and psycholinguistic principles. The dataset is freely available online, as are the detailed guidelines used by the annotators.Footnote ³

Ó Séaghdha (Reference Ó Séaghdha2008) reports an inter-annotator agreement analysis performed on a more complex task which contained as a part the semantic annotation used here but also involved the detection of extraction errors and non-compositional or lexicalised compounds. Overall agreement was 66.2% (Cohen's κ=0.62) for coarse-grained annotation, 64.0% (κ=0.61) for coarse-grained labels with role order and 58.8% (κ=0.56) for fine-grained annotation. Further analysis by Ó Séaghdha suggests that agreement on the semantic relation annotation is probably a few points higher (estimated κ=0.68), as a significant amount of disagreement relates to decisions about lexicalisation. These agreement figures are not as high as those reported for some other tasks but are comparable to those reported in the literature on semantic annotation of compounds (Tratz and Hovy Reference Tratz and Hovy2010).

Prior work on this dataset has restricted itself to the coarse-grained annotation with six semantic relation labels (Ó Séaghdha and Copestake Reference Ó Séaghdha and Copestake2008, Reference Ó Séaghdha and Copestake2009; Tratz and Hovy Reference Tratz and Hovy2010). In this paper we consider the tasks of classification at the following three levels of granularity:

• Coarse: Predicts coarse-grained relations (six labels).

• Directed: Predicts coarse-grained relations and which constituents fill which relation slots (eleven labels).

• Fine: Predicts fine-grained labels corresponding to annotation rules and which constituents fill which relation slots (thirty-seven labels).

Not all potential labels are well-represented in the dataset; for example, there are only five examples of ABOUT _(H,M) (e.g. sitcom family). In our classification experiments all labels occurring ten times or fewer in the dataset were excluded, with the result that in practice the Directed and Fine inventories contain ten and twenty-seven labels respectively.

4.2 Corpora

In order to extract data for the lexical and relational kernels we used three source corpora:

• • The written component of the British National Corpus (BNC), consisting of 90 million words (Burnard Reference Burnard1995), lemmatised, POS-tagged and parsed with the RASP toolkit (Briscoe, Carroll and Watson Reference Briscoe, Carroll and Watson2006).

• • A Wikipedia dump (WIKI), consisting of almost 1 billion words, collected by Clark et al. (Reference Clark, Copestake, Curran, Zhang, Herbelot, Haggerty, Ahn, Wyk, Roesner, Kummerfeld and Dawborn2009), lemmatised, POS-tagged and parsed with the fast Combinatory Categorial Grammar (CCG) pipeline described by Clark et al.

• • The English Gigaword Corpus (GW), 2nd Edition, consisting of 2.3 billion words (Graff et al. Reference Graff, Kong, Chen and Maeda2005), lemmatised and tagged with RASP but not parsed.

These corpora are also used to produce two larger corpora by concatenation: BNC+WIKI and BNC+GW.

The BNC and BNC+WIKI corpora were used to extract distributional lexical information based on grammatical relations (GRs) in the parser output. Although the BNC and WIKI corpora were processed with different parsers, both the RASP and CCG parsers can produce grammatical relations in the same format and therefore their outputs are interoperable. In order to maximise the yield of semantically salient information, the GR graph for each sentence was preprocessed with the transformations specified in Figure 1. All parts of speech other than nouns, verbs, adjectives, prepositions and adverbs were ignored, as were stopwords, tokens of fewer than three characters and the semantically weak lemmas be and have. The following feature sets were extracted for each noun w that appears as a constituent in the compound dataset:

• Coordination: All nouns w′ appearing linked to w in a coordinative structure (labelled n:and:n in Figure 1). This is the same feature specification as in Ó Séaghdha and Copestake (Reference Ó Séaghdha and Copestake2008); it is very sparse but rich in semantic class information. For example, if a noun is frequently coordinated with cat, dog and goldfish, then it is most likely a household animal.

• All GRs: All tuples (w′, r) where w′ is a word appearing as the dependent of w in the GR graph and r is the GR label on the edge connecting w and w′, and all tuples (w′, r ⁻¹) where w′ appears as the head of w. For example, given the GR graph fragment

  • 
  the set of context features for the noun body is {(executive,j:ncmod⁻¹:n), (decide,v:ncsubj:n)}, where ncmod ⁻¹ denotes that body stands in an inverse non-clausal modifier relation to executive (we assume that nouns are the heads of their adjectival modifiers).

• GR Clusters: Rather than using the very sparse All GRs feature space, we can use clusters of GRs induced by applying the ‘topic modelling’ approach of Ó Séaghdha and Korhonen (Reference Ó Séaghdha and Korhonen2011). This method, based on the Latent Dirichlet Allocation model proposed for document analysis by Blei, Ng and Jordan (Reference Blei, Ng and Jordan2003), associates each word with a multinomial distribution over latent variables and associates each latent variable with a multinomial distribution over GR tuples. Given that the number of latent variables |Z| is generally much lower than the number of GR tuples, the parameters of a word's distribution over latent variables can be interpreted as defining a low-dimensional distribution over clusters of GR tuples. In order to estimate the parameters of this model, we use the efficient Gibbs sampling algorithm of Yao, Mimno and McCallum (Reference Yao, Mimno and McCallum2009) and estimate the probability P(z|w) that a GR involving word w is associated with latent variable z as the proportion of GR instances involving w in the training corpus to which z is assigned in the final sampling state. We run the Gibbs sampler for 1,000 iterations and set |Z|=1, 000. We have not investigated the effect of modifying |Z|, although it would be feasible to combine feature sets with different parameterisations to exploit multiple granularities or to combine feature sets derived from multiple sampling runs to reduce variance.

Fig. 1.

Dependency graph preprocessing.

The BNC+GW corpus was used to extract sets of string contexts for each pair of compound constituents. For each compound in the dataset, the set of sentences in the combined corpus containing both constituents of the compound was identified. As the Gigaword Corpus contains many duplicate and near-duplicate articles, duplicate sentences were discarded so that repeated strings would not dominate the similarity estimates. Sentences in which the head and modifier words were more than ten words apart were also discarded, as it is plausible that there is no direct relation between the words in such sentences. The modifier and head were replaced with placeholder tokens M:n and H:n in each sentence to ensure that the classifier would learn from relational information only and not from lexical information about the constituents. Punctuation and tokens containing non-alphanumeric characters were removed. Finally, all tokens more than five words to the left of the leftmost constituent or more than five words to the right of the rightmost constituent were discarded; this has the effect of speeding up the set kernel computations and should also focus the classifier on the most informative parts of the context sentences. Examples of the context strings extracted for the modifier-head pair (history,book) are

This extraction procedure resulted in a corpus of 1,472,798 strings. There was significant variation in the number of context strings extracted for each compound: 288 compounds were associated with 1,000 or more sentences, while 191 were associated with ten or fewer and no sentences were found for forty-five constituent pairs. The largest context sets were predominantly associated with political or economic topics (e.g. government official, oil price), reflecting the journalistic sources of the Gigaword sentences.

4.3 Classification setup

All experiments were performed using the SVM training algorithm implemented in LIBSVM.Footnote ⁴ We decompose the multiclass classification problem into a set of binary classification problems through the one-against-all method: a single classifier is trained for each class label, treating data instances with that class as positive examples and all other instances as negative, and the final prediction for a test instance is the label for which that instance has the greatest positive (or least negative) distance from the corresponding decision boundary. In each cross-validation fold, the SVM cost parameter C is optimised through a grid search over the set {2⁻⁴, 2⁰, . . ., 2¹²}, selecting the value that gives the best ten-fold cross-validation performance on that fold's training set. For each feature set and each set embedding vector, L ₁ normalisation (normalisation to unit sum) was performed before computing the JSD kernel; for the experiments with the L ₂ linear kernels, L ₂ normalisation (normalisation to unit Euclidean norm) was performed.

We compute evaluation results for five-fold cross-validation on the 1,443-compound dataset. As well as prediction accuracy (the proportion of compounds that were correctly labelled), we also report macro-averaged F-score, the average of the standard F-score measure calculated individually for each label. Accuracy rewards good performance on the most frequent labels, while macro-averaged F-score rewards performance on all labels equally. The best previously reported results for this dataset are 63.1% accuracy, 61.6 F-score (Ó Séaghdha and Copestake Reference Ó Séaghdha and Copestake2009) and 63.6% accuracy (Tratz and Hovy Reference Tratz and Hovy2010). The random-guess baseline is 16.3% accuracy for the Coarse label set, 10.0% accuracy for the Directed label set and 3.7% accuracy for the Fine label set. Where we wish to measure the statistical significance of a difference between two methods, we use paired t-tests (two-tailed, df = 4) on the cross-validation folds following the recommendation of Dietterich (Reference Dietterich1998).