5.1 Average precision

Average precision was originally designed as a performance measure for information retrieval systems. Suppose we have issued a query to a search engine and it has returned a ranked list of N documents, sorted in descending order of their automatically estimated degree of relevance for our query. Assume that human judges have manually labeled all of the documents as either relevant or irrelevant for the given query. Let P(r) be the fraction of the top r highest ranked documents that have the label relevant. That is, P(r) is the precision of the ranked list if we cut off the list after the rth document. Let rel(r) be 1 if the rth document is labeled relevant, 0 otherwise. Average precision is defined as follows (Buckley and Voorhees, Reference Buckley and Voorhees2000):

(1) \begin{equation} {\rm AP} = \frac{\displaystyle \sum ^{N}_{r=1} [{\rm P}(r) \cdot {\rm rel}(r)]}{\mbox{Total number of relevant documents}} \end{equation}

The definition of average precision reflects a bias in information retrieval. For a typical query and a typical document collection, most documents are irrelevant and the emphasis is on finding the few relevant documents. In machine learning, if we have two classes, 0 and 1, they are usually considered equally important. Kotlerman et al. (Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010) emphasize class 1 (entails), but we believe class 0 (does not entail) is also important. For example, the scoring of the RTE Challenge gives an equal reward for recognizing when a text sentence entails a hypothesis sentence and when it does not. Therefore, we report two variations of average precision, which we call AP₀ (average precision with respect to class 0) and AP₁ (average precision with respect to class 1), which we define in the next paragraph.

Suppose we have a dataset of word pairs manually labeled 0 and 1. Let N be the number of word pairs in the dataset. Let M(a, b) ∈ ℜ be a measure that assigns a real-valued score to each word pair, a: b. Sort the pairs in descending order of their M(a, b) scores. Let P₁(r) be the fraction of the top r highest ranked pairs that have the label 1. Let P₀(r) be the fraction of the bottom r lowest ranked pairs that have the label 0. Let C₁(r) be 1 if the rth document from the top is labeled 1, 0 otherwise. Let C₀(r) be 1 if the rth document from the bottom is labeled 0, 0 otherwise. Let N ₀ be the total number of pairs labeled 0 and let N ₁ be the total number of pairs labeled 1. We define AP₀ and AP₁ as follows:

(2) \begin{align} {\rm AP}_0 & = \frac{\displaystyle \sum ^{N}_{r=1} [{\rm P}_0(r) \cdot {\rm C}_0(r)]}{N_0} \end{align}

(3) \begin{align} {\rm AP}_1 & = \frac{\displaystyle \sum ^{N}_{r=1} [{\rm P}_1(r) \cdot {\rm C}_1(r)]}{N_1} \end{align}

In their experiments, Kotlerman et al. (Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010) report only AP₁. It is possible to increase a system’s performance according to AP₁ at the cost of lower AP₀ performance. The formula for AP₁ is more sensitive to the labels in the top of the list. What happens at the bottom of the list has little impact on AP₁, because P₁(r) gives a low weight to labels at the bottom of the list. On the other hand, the formula for AP₀ is more sensitive to labels at the bottom of the list. If we focus on AP₁ and ignore AP₀, we will prefer algorithms that get the top of the list right, even if they do poorly with the bottom of the list. Therefore, it is important to report both AP₀ and AP₁.

5.2 Precision, recall, F-measure, and accuracy

Like average precision, precision and recall were originally designed as performance measures for information retrieval systems. The precision of a system is an estimate of the conditional probability that a document is truly relevant to a query if the system says it is relevant. The recall of a system is an estimate of the conditional probability that the system will say that a document is relevant to a query if it is truly relevant.

There is a tradeoff between precision and recall; one may be optimized at the cost of the other. The F-measure is the harmonic mean of precision and recall. It is designed to reward a balance of precision and recall.

Accuracy is a natural and intuitive performance measure, but it is sensitive to the relative sizes of the classes. It is easy to interpret accuracy when we have two equal-sized classes, but it is difficult to interpret when one class is much larger than the other. The F-measure is a better measure when the classes are not balanced.

As with average precision, there are two variations of precision, recall, and F-measure, depending on whether we focus on class 0 or class 1. Let C be a 2 × 2 confusion matrix, where c_ij is the number of word pairs that are actually in class i and the algorithm has predicted that they are in class j (here i, j ∈ {0, 1}). We define precision, recall, and F-measure as follows:

(4) \begin{align} {\rm Pre}_0 & = c_{00} / (c_{00} + c_{10}) \end{align}

(5) \begin{align} {\rm Pre}_1 & = c_{11} / (c_{11} + c_{01}) \end{align}

(6) \begin{align} {\rm Rec}_0 & = c_{00} / (c_{00} + c_{01}) \end{align}

(7) \begin{align} {\rm Rec}_1 & = c_{11} / (c_{11} + c_{10}) \end{align}

(8) \begin{align} {\rm F}_0 & = 2 \cdot {\rm Pre}_0 \cdot {\rm Rec}_0 / ({\rm Pre}_0 + {\rm Rec}_0) \end{align}

(9) \begin{align} {\rm F}_1 & = 2 \cdot {\rm Pre}_1 \cdot {\rm Rec}_1 / ({\rm Pre}_1 + {\rm Rec}_1) \end{align}

Following standard practice (Witten, Frank and Hall Reference Witten, Frank and Hall2011), we merge the two variations of each measure by taking their weighted averages, where the weights are determined by the class sizes:

(10) \begin{align} w_0 & = (c_{00} + c_{01}) / (c_{00} + c_{01} + c_{10} + c_{11}) \end{align}

(11) \begin{align} w_1 & = (c_{11} + c_{10}) / (c_{00} + c_{01} + c_{10} + c_{11}) \end{align}

(12) \begin{align} {\rm Pre} & = w_0 \cdot {\rm Pre}_0 + w_1 \cdot {\rm Pre}_1 \end{align}

(13) \begin{align} {\rm Rec} & = w_0 \cdot {\rm Rec}_0 + w_1 \cdot {\rm Rec}_1 \end{align}

(14) \begin{align} {\rm F} & = w_0 \cdot {\rm F}_0 + w_1 \cdot {\rm F}_1 \end{align}

Finally, we define accuracy as usual:

(15) \begin{equation} {\rm Acc} = 100 \cdot (c_{00} + c_{11}) / (c_{00} + c_{01} + c_{10} + c_{11}) \end{equation}

6.1 The context inclusion hypothesis: balAPinc

We include balAPinc in our experiments because Kotlerman et al. (Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010) experimentally compared it with a wide range of asymmetric similarity measures and found that balAPinc had the best performance. The balAPinc asymmetric similarity measure is a balanced combination of the asymmetric APinc measure (Kotlerman et al., Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010) with the symmetric LIN measure (Lin, Reference Lin1998). Balance is achieved by using the geometric mean:

(16) \begin{equation} {\rm balAPinc}(u, v) = \sqrt{ {\rm APinc}(u, v) \cdot {\rm LIN}(u,v) } \end{equation}

To define APinc and LIN, we must first introduce some terminology. Kotlerman et al. (Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010) define balAPinc with terminology from set theory, whereas ConVecs and SimDiffs are more naturally defined with terminology from linear algebra. We will use the set theoretical terminology of Kotlerman et al. (Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010) and the linear algebraic terminology of Turney and Pantel (Reference Turney and Pantel2010) so that the reader can easily see both perspectives. This leads to a small amount of redundancy, but we believe it is helpful to connect the two points of view.Footnote ⁴

First, some linear algebraic notation: Suppose that we have a word–context matrix in which each row vector corresponds to a word and each column vector corresponds to a context. Let F be the matrix of raw co-occurrence frequencies. If w is the word corresponding to the ith row vector, f_i:, and c is the context corresponding to the jth column vector, f_{: j}, then f_ij is the number of times w occurs in the context c in the given corpus.

Let the matrix X be the result of calculating the positive point-wise mutual information (PPMI) between the word w and the context c for each element f_ij in F (Bullinaria and Levy, Reference Bullinaria and Levy2007; Turney and Pantel, Reference Turney and Pantel2010). PPMI takes the raw co-occurrence frequencies and transforms them to weights that represent the importance of a given context for a given word. The PPMI matrix X is typically sparse (most cells are zero) and no cells are negative.Footnote ⁵

The matrix X has the same number of rows (n_r) and columns (n_c) as the raw frequency matrix F. The value of an element x_ij in X is defined as follows (Turney and Pantel, Reference Turney and Pantel2010):

(17) \begin{align} p_{ij} & = \frac{f_{ij}}{\displaystyle \sum _{i=1}^{n_r} \displaystyle \sum _{j=1}^{n_c} f_{ij}} \end{align}

(18) \begin{align} p_{i*} & = \frac{\displaystyle \sum _{j=1}^{n_c} f_{ij}}{\displaystyle \sum _{i=1}^{n_r} \displaystyle \sum _{j=1}^{n_c} f_{ij}} \end{align}

(19) \begin{align} p_{*j} & = \frac{\displaystyle \sum _{i=1}^{n_r} f_{ij}}{\displaystyle \sum _{i=1}^{n_r} \displaystyle \sum _{j=1}^{n_c} f_{ij}} \end{align}

(20) \begin{align} {\rm pmi}_{ij} & = \log \left( \frac{p_{ij}}{p_{i*} p_{*j}} \right) \end{align}

(21) \begin{align} x_{ij} & = \left\lbrace \begin{array}{rl}\rm pmi_{ij} & \mbox{if ${\rm pmi}_{ij} > 0$}\\ 0 & \mbox{otherwise} \end{array} \right. \end{align}

Now, some set theoretical notation: Given a word w corresponding to the ith row in X, let F_w be the set of contexts for which x_ij is nonzero. That is, c ∈ F_w if and only if x_ij ≠ 0, where w corresponds to row i and c corresponds to column j. We may think of the contexts in the set F_w as features that characterize the word w. Let |F_w| be the number of features in F_w. If w corresponds to the ith row in X, then |F_w| is the number of nonzero cells in the ith row vector, x_i:.

Each feature f in F_w corresponds to a PPMI value x_ij. Let us rank the features in F_w in descending order of their corresponding PPMI values. Let f_wr be the rth feature in the ranking of F_w, where r ranges from 1 to |F_w|. Let rank(f, F_w) be the rank of f in F_w. Thus, rank(f_wr, F_w) = r. We want to normalize this rank so that it ranges between 0 and 1, where higher PPMI values are closer to 1 and lower PPMI values are closer to 0. The function rel(f, F_w) provides this normalization:

(22) \begin{equation} {\rm rel}(f,F_w) = \left\lbrace \begin{array}{rl}1 - \frac{{\rm rank}(f,F_w)}{|F_w| + 1} & \mbox{if $f \in F_w$} \\ 0 & \mbox{if $f \notin F_w$} \end{array} \right. \end{equation}

Recall the context inclusion hypothesis: If a word u tends to occur in a subset of the contexts in which a word v occurs (v contextually includes u), then u (the narrower term) tends to entail v (the broader term). Suppose we test the features of u, f ∈ F_u, in order of their rank, r, to see which features of u are contextually included in v. Let inc(r, F_u, F_v) be the set consisting of those features, among the first r features in F_u, that are included in F_v:

(23) \begin{equation} {\rm inc}(r,F_u,F_v) = \left\lbrace f \, | \, {\rm rank}(f,F_u) \le r \mbox{ and } f \in (F_u \cap F_v) \right\rbrace \end{equation}

(24) \begin{equation} {\rm P}(r,F_u,F_v) = \frac{|{\rm inc}(r,F_u,F_v)|}{r} \end{equation}

Now we are ready to define APinc:

(25) \begin{equation} {\rm APinc}(u, v) = \frac{\displaystyle \sum ^{|F_u|}_{r=1} [{\rm P}(r,F_u,F_v) \cdot {\rm rel}(f_{ur},F_v)]}{|F_u|} \end{equation}

Let w_u(f) be the weight of the feature f in the word u. The weight is given by the PPMI value in X. If u corresponds to the ith row and f corresponds to the jth column, then w_u(f) = x_ij. (It may seem redundant to have both w_u(f) and x_ij. The first is set theoretical and the second is linear algebraic.) LIN is defined as follows (Lin, Reference Lin1998):

(26) \begin{equation} {\rm LIN}(u,v) = \frac{\displaystyle \sum _{f \in F_u \cap Fv} [w_u(f) + w_v(f)]}{\displaystyle \sum _{f \in F_u} w_u(f) + \displaystyle \sum _{f \in F_v} w_v(f)} \end{equation}

There are two parameters, max_F and T, that can be varied to control the performance of balAPinc. The parameter max_F sets the maximum number of features for each word. For a given word w, we calculate all of the features, F_w. If |F_w| > max_F, then we remove the lowest ranking features until |F_w| = max_F. This reduces the impact of low-ranking features on the APinc score. The parameter T is a threshold for classification. If balAPinc(u, v) < T, then the word pair u: v is classified as 0 (does not entail); otherwise u: v is classified as 1 (entails). We describe how these parameters are tuned in Section 8.

Kotlerman et al. (Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010) do not use the threshold T, since they do not evaluate balAPinc as a classifier. They also do not use the parameter max_F, although their analysis supports the utility of this parameter; see Section 5.4.4 of Kotlerman et al. (Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010).

In the experiments with balAPinc in Section 8, the PPMI matrix X is the same matrix as used by Turney et al. (Reference Turney, Neuman, Assaf and Cohen2011). The matrix has 114,501 rows and 139,246 columns. The rows correspond to single and multi-word entries (n-grams) in WordNet and the columns correspond to unigrams in WordNet, distinguished according to whether they appear in the left or right context of the given n-gram. The window size for context is four words to the left and four words to the right of the n-gram. The matrix has a density (percentage of nonzero values) of 1.22%.

The PPMI matrix is based on a corpus of 5 × 10¹⁰ words, collected from university websites by a webcrawler.Footnote ⁶ The corpus was indexed with the Wumpus search engine (Büttcher and Clarke, Reference Büttcher and Clarke2005), which is designed for passage retrieval rather than document retrieval.Footnote ⁷ Suppose f_ij is an element in the matrix of raw co-occurrence frequencies F. The ith row of the matrix corresponds to an n-gram w in WordNet and the jth column of the matrix corresponds to a unigram c. The value of f_ij was calculated by sending the query w to Wumpus and counting the frequency of c in the retrieved passages. The matrix is described in detail in Section 2.1 of Turney et al. (Reference Turney, Neuman, Assaf and Cohen2011).

It is common to smooth the PPMI matrix by applying a truncated singular value decomposition (SVD) (Turney and Pantel, Reference Turney and Pantel2010). On the development datasets, we experimented with smoothing the matrix, but the results were poor. The problem is that the truncated SVD yields a matrix with a density of 100%, but balAPinc is designed for highly sparse matrices.

Consider (23) for example. If the matrix has a density of 100%, then all of the contexts (all of the matrix columns) are nonzero, so F_u and F_v are simply the entire set of features, and (F_u∩F_v) is also the entire set of features. Likewise, in (26) all of the sums, ∑_f, range over the entire set of features. The equations behind balAPinc are based on the assumption that most of the elements in the matrix are zero (i.e. the matrix is sparse), but this assumption is false if we apply a truncated SVD.

In the experiments in Section 8, we use the raw PPMI matrix with no SVD smoothing. Baroni et al. (Reference Baroni, Bernardi, Do and Shan2012) also found that balAPinc works better without SVD smoothing (see their Footnote 3).

6.2 The context combination hypothesis: ConVecs

With the ConVecs algorithm, Baroni et al. (Reference Baroni, Bernardi, Do and Shan2012) were able to match the performance of balAPinc. In ConVecs, we represent a word pair a: b by the concatentation of the context vectors a for a and b for b. We apply a supervised learning algorithm to a training set of word pairs, where each word pair is represented by concatenated context vectors that are labeled entails or does not entail. The supervised learning algorithm generates a classification model which enables us to assign labels to new word pairs not present in the training data.

Let X be a word–context matrix where the value of the cell x_ij in X is given by the PPMI between the ith word w and the jth context c. In our experiments we use the word–context matrix X from Turney et al. (Reference Turney, Neuman, Assaf and Cohen2011), as in Section 6.1, but now we smooth X with a truncated SVD.

Singular value decomposition decomposes X into the product of three matrices $\mathbf {U} \mathbf {\Sigma } \mathbf {V}^\mathsf {T}$, where U and V are in column orthonormal form (i.e. the columns are orthogonal and have unit length, $\mathbf {U}^\mathsf {T} \mathbf {U} = \mathbf {V}^\mathsf {T} \mathbf {V} = \mathbf {I}$) and Σ is a diagonal matrix of singular values (Golub and Van Loan, Reference Golub and VanAAAALoan1996). If X is of rank r, then Σ is also of rank r. Let Σ_k, where k < r, be the diagonal matrix formed from the top k singular values, and let U_k and V_k be the matrices produced by selecting the corresponding columns from U and V. The matrix $\mathbf {U}_k \mathbf {\Sigma }_k \mathbf {V}_k^\mathsf {T}$ is the matrix of rank k that best approximates the original matrix X, in that it minimizes the approximation errors. That is, ${\bf \hat{X}} = \mathbf {U}_k \mathbf {\Sigma }_k \mathbf {V}_k^\mathsf {T}$ minimizes $\Vert {{\bf \hat{X}} - \mathbf {X}} \Vert _F$ over all matrices ${\bf \hat{X}}$ of rank k, where ‖. . .‖_F denotes the Frobenius norm (Golub and Van Loan, Reference Golub and VanAAAALoan1996).

We represent a word pair a: b using row vectors from the matrix U_kΣ^p_k. If a and b correspond to row vectors a and b in U_kΣ^p_k, then a: b is represented by the 2k-dimensional vector that is the concatenation of a and b. We normalize a and b to unit length before we concatenate them.

There are two parameters in U_kΣ^p_k that need to be set. The parameter k controls the number of latent factors and the parameter p adjusts the weights of the factors, by raising the corresponding singular values in Σ^p_k to the power p.

The parameter k is well known in the literature (Landauer et al. , Reference Landauer, McNamara, Dennis and Kintsch2007), but p is less familiar. Caron (Reference Caron2001) introduced p for improving the performance of truncated SVD with term–document matrices in information retrieval. The use of p to improve the performance with word–context matrices in lexical semantics is supported by the empirical evaluations of Bullinaria and Levy (Reference Bullinaria and Levy2012) and Turney (Reference Turney2012). In the following experiments (Section 8), we explore a range of values for p and k. Baroni et al. (Reference Baroni, Bernardi, Do and Shan2012) use k = 300 and p = 1.Footnote ⁸

Recall the context combination hypothesis: The tendency of a to entail b is correlated with some learnable function of the contexts in which a occurs and the contexts in which b occurs; some conjunctions of contexts tend to indicate entailment and others tend to indicate a lack of entailment. Given the context combination hypothesis, vector concatenation is a natural way to represent a: b for learning lexical entailment.

For their supervised learning algorithm, Baroni et al. (Reference Baroni, Bernardi, Do and Shan2012) used Weka with LIBSVM.Footnote ⁹ They used a polynomial kernel for SVM. We also use Weka and a polynomial kernel, but we use the sequential minimal optimization (SMO) SVM in Weka (Platt, Reference Platt, Schölkopf, Burges and Smola1998) because it can generate real-valued probability estimates, as well as binary-valued classes. The probability estimates are based on fitting the outputs of the SVM with logistic regression models (Witten, Frank, and Hall, Reference Witten, Frank and Hall2011).

We tried various kernels with ConVecs on the development datasets (Dev1 and Dev2; see Section 8.1.1), and found that a second-degree polynomial kernel had the best performance. We use default settings for the polynomial kernel SMO SVM in Weka, except we disable normalization, because the vectors are already normalized to the same length.

It seems to us that ConVecs is a good algorithm for a generic semantic relation, but a representation that takes advantage of some background knowledge about lexical entailment might require less training data. One thing we know about lexical entailment is a⊧a, for any a. ConVecs can only reliably recognize that a⊧a if a is similar to some x such that the word pair x: x appears in the training data and has been labeled entails. To cover a broad range of possible values for a, there must be many different x: x pairs in the training data. The ConVecs representation does not make efficient use of the training data.

6.3 The similarity differences hypothesis: SimDiffs

SimDiffs uses two different word–context matrices, a domain matrix, D, and a function matrix, F (Turney, Reference Turney2012). The domain matrix is designed for measuring the domain similarity between two words (similarity of topic, subject, or field). For example, carpenter and wood have a high degree of domain similarity; they both come from the domain of carpentry. The function matrix is designed for measuring function similarity (similarity of role, relationship, or usage). For example, carpenter and mason have a high degree of function similarity; they both function as artisans.

The two matrices use different types of context. The domain matrix uses the nouns that occur near a given word as the context for the word, whereas the function matrix uses the verbs that occur near the given word. The part-of-speech information was generated with the OpenNLP tagger.Footnote ¹⁰ Our motivation for using two matrices in SimDiffs is to generate a larger and more varied set of features for the supervised learning algorithm. Turney (Reference Turney2012) demonstrated that domain and function matrices work together synergetically when applied to semantic relations.

In experiments with the development datasets (Dev1 and Dev2), we tried using the domain and function matrices with balAPinc and ConVecs, but both algorithms worked better with the word–context matrix from Turney et al. (Reference Turney, Neuman, Assaf and Cohen2011). For SimDiffs, the combination of the domain and function matrices from Turney (Reference Turney2012) had the best performance on the development datasets.

Both D and F use PPMI and SVD, as in Section 6.2. This results in a total of four parameters that need to be tuned, k _d and p _d for domain space and k _f and p _f for function space. In the following experiments (Section 8), to simplify the search through parameter space, we make k _d = k _f and p _d = p _f.

The domain and function matrices are based on the same corpus as the word–context matrix from Turney et al. (Reference Turney, Neuman, Assaf and Cohen2011). Wumpus was used to index the corpus and search for passages in the same way as described in Section 6.1. D has 114,297 rows and 50,000 columns. The PPMI matrix has a density of 2.62%. F has 114,101 rows and 50,000 columns. The PPMI matrix has a density of 1.21%. For both matrices, truncated SVD results in a density of 100%.

The rows for both the matrices correspond to single and multi-word entries (n-grams) in WordNet. The columns are more complex; Turney (Reference Turney2012) provides a detailed description of the columns and other aspects of the matrices. The matrices have different numbers of rows because, before applying SVD, we removed rows that were entirely zero. The function matrix, with its lower density, had more zero-valued rows than the domain matrix.

Suppose that the words a and b correspond to the row vectors a_d and b_d in the domain matrix, D. Let sim_d(a, b) be the similarity of a and b in domain space, as measured by the cosine of the angle between a_d and b_d, cos(a_d, b_d). Likewise, let sim_f(a, b) be cos(a_f, b_f), the cosine in function space.

Let R be a set of reference words. Recall the similarity differences hypothesis: The tendency of a to entail b is correlated with some learnable function of the differences in their similarities, sim(a, r) − sim(b, r), to a set of reference words, r ∈ R; some differences tend to indicate entailment and others tend to indicate a lack of entailment. In SimDiffs, we represent a word pair a: b with a feature vector comprising four sets of features, S ₁, S ₂, S ₃, and S ₄, defined as follows:

(27) \begin{align} S_1 & = \left\lbrace {\rm sim_d}(a,r) - {\rm sim_d}(b,r) \, | \, r \in R \right\rbrace \end{align}

(28) \begin{align} S_2 & = \left\lbrace {\rm sim_f}(a,r) - {\rm sim_f}(b,r) \, | \, r \in R \right\rbrace \end{align}

(29) \begin{align} S_3 & = \left\lbrace {\rm sim_d}(a,r) - {\rm sim_f}(b,r) \, | \, r \in R \right\rbrace \end{align}

(30) \begin{align} S_4 & = \left\lbrace {\rm sim_f}(a,r) - {\rm sim_d}(b,r) \, | \, r \in R \right\rbrace \end{align}

The cross-spatial differences (S ₃ and S ₄) may seem counterintuitive. Consider the example murder ⊧ death, suggested by the quotation from Zhitomirsky-Geffet and Dagan (Reference Zhitomirsky-Geffet and Dagan2009) in Section 3. Murder typically involves two people, the victim and the aggressor, whereas death typically involves one person, the deceased. This suggests that there is a functional difference between the words, hence the function similarities of murder may be quite different from the function similarities of death. However, perhaps the domain similarities of murder are somewhat similar to the function similarities of death (S ₃) or perhaps the function similarities of murder are somewhat similar to the domain similarities of death (S ₄). We include these similarities here to see if the supervised learning algorithm can make use of these.

For R, the set of reference words, we use 2,086 words from Basic English (Ogden, Reference Ogden1930).Footnote ¹¹ Thus, a word pair a: b is represented by 2,086 × 4 = 8,344 features. The words of Basic English were selected by Ogden (Reference Ogden1930) to form a core vocabulary, sufficient to represent most other English words by paraphrasing. We chose this set of words because it is small enough to keep the number of features manageable yet broad enough to cover a wide range of concepts. Other reference words may also be suitable; this is a topic for future work.

We mentioned in Section 6.2 that ConVecs may be inefficient for learning a⊧a. On the other hand, consider how a⊧a is represented in SimDiffs. Looking at (27) and (28), we see that, given the word pair a: a, every feature in S ₁ and S ₂ will have the value zero. Therefore, it should not take many examples of x: x in the training data to learn that a⊧a, for any a.

For our supervised learning algorithm, we use the SMO SVM in Weka. Based on the experiments with the development datasets (Dev1 and Dev2), we use a radial basis function kernel. We use the default settings, except we disable normalization. We generate probability estimates for the classes.

7.1 The KDSZ dataset

The KDSZ dataset was introduced by Kotlerman et al. (Reference Kotlerman, Dagan, Szpektor and Zhitomirsky-Geffet2010) to evaluate balAPinc. The dataset contains 3,772 word pairs, 1,068 labeled entails, and 2,704 labeled does not entail. It was created by taking a dataset of 3,200 labeled word pairs from Zhitomirsky-Geffet and Dagan (Reference Zhitomirsky-Geffet and Dagan2009) and adding 572 more labeled pairs.Footnote ¹² The labeling of the original subset of 3,200 pairs is described in detail by Zhitomirsky-Geffet and Dagan (Reference Zhitomirsky-Geffet and Dagan2009). The definition of lexical entailment that the judges used was the substitutional definition given in Section 2. Three judges labeled the pairs with inter-annotator agreement between any two of the three judges varying from 90.0% to 93.5%.

This dataset has two properties that complicate the experiments. First, the class sizes are not balanced; 71.7% of the pairs are labeled does not entail and 28.3% are labeled entails. Second, although every word pair is unique, there are a few words that appear many times, in many different pairs. We address these points in our experiments.

The words in the word pairs are mainly unigrams, but there are a few bigrams (central bank, higher education, state government). Fortunately, all of the bigrams appear in WordNet, so they have corresponding row vectors in our matrices.

7.2 The BBDS dataset

The BBDS dataset was created by Baroni et al. (Reference Baroni, Bernardi, Do and Shan2012) and has been applied to evaluating both balAPinc and ConVecs. In their paper, Baroni et al. (Reference Baroni, Bernardi, Do and Shan2012) discuss several different datasets. We use the dataset they call N₁⊧N₂, described in their Section 3.3. The dataset contains 2,770 word pairs, 1,385 labeled entails, and 1,385 labeled does not entail. All of the 1,385 pairs labeled entails are hyponym–hypernym noun–noun pairs, such as pope ⊧ leader. The pairs were generated automatically from WordNet and then validated manually.

Although the class sizes are balanced, 50% entails and 50% does not entail, the BBDS dataset is not representative of the variety of semantic relations that involve entailment as we will see in Section 7.3. Also, although every word pair is unique, there are a few words that appear many times. All of the word pairs comprise unigrams and all the unigrams appear in WordNet, so they have corresponding row vectors in our matrices.

7.3 The JMTH dataset

Jurgens et al. (Reference Jurgens, Mohammad, Turney and Holyoak2012) created a semantic relation dataset for SemEval-2012 Task 2: Measuring Degrees of Relational Similarity.Footnote ¹³ This dataset contains 3,218 word pairs labeled with seventy-nine types of semantic relations. In this section, we describe the original SemEval-2012 dataset and the process we used to convert the dataset into 2,308 word pairs, 1,154 labeled entails, and 1,154 labeled does not entail.

The original dataset consists of word pairs labeled using the relation classification scheme of Bejar et al. (Reference Bejar, Chaffin and Embretson1991). This is a hierarchical classification system with ten high-level categories, each of which has between five and ten subcategories, for a total of seventy-nine distinct subcategories.

For each subcategory in Bejar et al.'s (Reference Bejar, Chaffin and Embretson1991) relation taxonomy, we have several types of information, as shown in Table 1. The first four types of information come from Bejar et al. (Reference Bejar, Chaffin and Embretson1991) and the rest were added by Jurgens et al. (Reference Jurgens, Mohammad, Turney and Holyoak2012).Footnote ¹⁴

Table 1.

Types of information about the classes in the relation taxonomy

The original SemEval-2012 dataset was generated in two phases, using Amazon’s Mechanical Turk (Jurgens et al., Reference Jurgens, Mohammad, Turney and Holyoak2012).Footnote ¹⁵ We refer to Mechanical Turk workers as Turkers. In the first phase, for each of the seventy-nine subcategories, Turkers were shown paradigmatic examples of word pairs in the given subcategory, and they were asked to generate more word pairs of the same semantic relation type. In the second phase, for each of the seventy-nine subcategories, Turkers were shown word pairs that were generated in the first phase, and they were asked to rate the pairs according to their degree of prototypicality for the given semantic relation type. (See Table 1 for examples of the results of the two phases.)

We transformed the original SemEval-2012 semantic relation dataset to the new lexical entailment dataset in the following four steps:

1. (1) Cleaning: To improve the quality of the dataset, we removed the ten lowest rated word pairs from each subcategory. Since the original dataset has 3,218 word pairs, the average subcategory has 40.7 word pairs. Our cleaning operation reduced this to 30.7 pairs per subcategory, a total of 2,428 word pairs (3218 − 79 × 10 = 2, 428).

2. (2) Doubling: For each word pair a: b labeled with a subcategory X, we generated a new word pair b: a and labeled it X ⁻¹. For example, car:engine is labeled object:component, so we created the pair engine:car and labeled it object: component⁻¹. This increased the number of pairs to 4,856 and the number of subcategories to 158.

3. (3) Mapping: We then mapped the 158 subcategory labels to the labels 0 (does not entail) and 1 (entails). The mapping is given in Tables 2 and 3. We assume that all word pairs within a subcategory belong to the same class (either all entail or none entail). (This assumption is tested in Section 7.3.2.) The result of mapping was 4,856 word pairs with two labels. There were 1,154 pairs labeled 1 and 3,702 pairs labeled 0.

4. (4) Balancing: To make a balanced dataset, we randomly removed pairs labeled 0 until there were 1,154 pairs labeled 0 and 1,154 pairs labeled 1, a total of 2,308 word pairs.

Table 2.

Semantic relation categories 1 to 5, based on Bejar et al. (Reference Bejar, Chaffin and Embretson1991)

Table 3.

Semantic relation categories 6 to 10, based on Bejar et al. (Reference Bejar, Chaffin and Embretson1991)

Here is how to interpret Tables 2 and 3. Given the pair anesthetic:numbness with the label instrument:goal, we see from Table 3 (ID 8f in the semantic relation taxonomy) that a⊧b has the value 1, so we map the label instrument:goal to the label 1 (entails). Given the pair numbness:anesthetic labeled instrument: goal⁻¹, we see from the table (ID 8f in the semantic relation taxonomy) that b⊧a has the value 0, so we map the label instrument: goal⁻¹ to the label 0 (does not entail). In other words, anesthetic ⊧ numbness:

• Text: Due to the anesthetic, Jane felt no pain.

  Hypothesis: Due to the numbness, Jane felt no pain.

  Text ⊧ Hypothesis

However, numbness $\not\models$anesthetic; for example, the numbness might be caused by cold temperature, not anesthetic:

• Text: George had frostbite. Due to the numbness, he felt no pain.

  Hypothesis: Due to the anesthetic, he felt no pain.

  Text $\not\models$ Hypothesis

Of the seventy-nine subcategories, twenty-five were labeled with class 1 for a⊧b and twelve were labeled with class 1 for b⊧a. Note that two of the subcategories are labeled with class 1 for both a⊧b and b⊧a (IDs 3a and 9e). This shows that our transformation handles both symmetric and asymmetric semantic relations.

7.3.2 Inter-annotator agreement

As we have mentioned above, we assume that all word pairs within a subcategory belong to the same class (either all entail or none entail). To test this assumption, we randomly selected one hundred word pairs, fifty labeled entails and fifty labeled does not entail. We hid the labels and then we each independently labeled the pairs manually, first using the relational definition of lexical entailment and then a second time using the substitutional definition of lexical entailment (see Section 2). Table 4 shows the percentage agreement between our manual labels and automatic labeling, generated from the SemEval-2012 dataset by the mapping in Tables 2 and 3.

Table 4.

Agreement and entailment for the two definitions of lexical entailment

With the relational definition of lexical entailment, we agreed on 81% of the labels. The agreement between our manual labels and the labels that were generated automatically, by applying the mapping in Tables 2 and 3 to the SemEval dataset, varied from 70% to 81%. These numbers suggest that our assumption that all word pairs within a subcategory belong to the same class is reasonable. The assumption yields levels of agreement that are comparable with the agreement in our manual labels.

We mentioned in Section 7.1 that Zhitomirsky-Geffet and Dagan (Reference Zhitomirsky-Geffet and Dagan2009) had inter-annotator agreements in the 90% range, whereas our agreement is 81%. We hypothesize that substitutability is a relatively objective test that leads to higher levels of agreement but excludes important cases of lexical entailment. We discussed some examples of cases that are missed by the substitutional definition in Section 2.

Table 4 shows that the agreement in our manual labels is 81% for the relational definition and 89% for the substitutional definition. This supports our hypothesis that substitutability is more objective. The agreement of 89% is close to the levels reported by Zhitomirsky-Geffet and Dagan (Reference Zhitomirsky-Geffet and Dagan2009). On the other hand, the number of pairs labeled entails drops from 48%–51% for the relational definition to 22%–25% for the substitutional definition. This supports our hypothesis that substitutability excludes many cases of entailment. The relational definition yields approximately twice the number of lexical entailments that are captured by the substitutional definition.

As expected, the automated labeling using SemEval corresponds more closely to manual labeling with the relational definition (70%–81%) than manual labeling with the substitional definition (65%–68%). This confirms that the construction of the dataset is in accordance with the intention of our relational definition.

8.1 Experiments with the JMTH dataset

For the first set of experiments, we used the JMTH dataset (Section 7.3). This dataset has 2,308 word pairs, 1,154 in class 0 and 1,154 in class 1.

8.1.1 Experimental setup

For the experiments, we split the dataset into three (approximately) equal parts, two development sets (Dev1 and Dev2) and one test set (Test). The splits were random, except that the balance of the class sizes was maintained in all the three subsets. Both Dev1 and Dev2 contain 768 pairs and Test contains 772 pairs.

Table 5 shows the number of word pairs in the Test set for each of the ten high-level categories. In Tables 2 and 3, we see that a⊧b is 0 for all subcategories of the category class-inclusion, hence there are zero pairs for a⊧b in the row for class-inclusion in Table 5 but there are twelve pairs for $a \not\models b$. On the other hand, in Tables 2 and 3, b⊧a is 1 for all subcategories of the category class-inclusion, so it is not surprising to see that there are fifty-five pairs for b⊧a in the row for class-inclusion in Table 5 and zero pairs for $b \not\models a$. The number of pairs labeled entails is 261 + 125 = 386 and the number of pairs labeled does not entail is 176 + 210 = 386.

Table 5.

The distribution of the ten high-level categories in the Test set

The balAPinc measure has two parameters to tune, max_F for the maximum number of features and T as a threshold for classification. On Dev1, we calculated balAPinc five times, using five different values for max_F, 1,000, 2,000, 3,000, 4,000, and 5,000. For each given value of max_F, we set T to the value that optimized the F-measure on Dev1. This gave us five pairs of values for max_F and T. We tested each of these five settings on Dev2 and chose the setting that maximized the F-measure, which was max_F = 1, 000. The balAPinc measure is robust with respect to the parameter settings. The accuracy on Dev2 ranged from 56.5% with max_F = 1, 000 to 52.5% with max_F = 5, 000. We kept the best max_F setting, but we tuned T again on the union of Dev1 and Dev2. With these parameter settings, we then applied balAPinc to the Test set.

ConVecs has two parameters to tune, k and p for U_kΣ^p_k. For k, we tried 100, 200, 300, 400, and 500. For p, we tried ten values, from 0.1 to 1.0 in increments of 0.1. For each of the fifty pairs of values for k and p, we ran Weka, using Dev1 as training data and Dev2 as testing data. The maximum F-measure on Dev2 was achieved with k = 100 and p = 0.4. ConVecs is robust with respect to the parameter settings. The accuracy on Dev2 ranged from a high of 70.1% to a low of 64.6%. We then ran Weka for one more time, using k = 100 and p = 0.4, with the union of Dev1 and Dev2 as training data and Test as testing data.

SimDiffs has four parameters to tune, k _d and p _d for domain space and k _f and p _f for function space, but we reduced this to two parameters, k and p, by setting k = k _d = k _f and p = p _d = p _f. We tried the same fifty pairs of values for k and p as we did with ConVecs. The maximum F-measure on Dev2 was achieved with k = 200 and p = 0.6. SimDiffs is robust with respect to the parameter settings. The accuracy on Dev2 ranged from 74.1% to 68.2%. We then ran Weka one more time, with the union of Dev1 and Dev2 as training data and Test as testing data.

8.1.2 Results

Table 6 shows the performance of all three algorithms on the Test set. According to Fisher’s Exact Test (Agresti, Reference Agresti1996), the accuracy of ConVecs (70.2%) is not significantly different from the accuracy of SimDiffs (72.4%). However, both ConVecs and SimDiffs are more accurate than balAPinc (57.3%) at the 95% confidence level. The other performance measures (AP₀, AP₁, Pre, Rec, and F) follow the same general pattern as accuracy, which is what we would usually expect for a balanced dataset. The final column in Table 6 shows the 95% confidence interval (CI) for accuracy, calculated using the Wilson method.

Table 6.

Comparison of the three algorithms on the JMTH dataset

Table 7 shows how the accuracies of the three algorithms vary over the ten high-level categories in the Test set. ConVecs and SimDiffs have roughly similar profiles but balAPinc is substantially different from the other two. This is what we would expect, given that both ConVecs and SimDiffs approach lexical entailment as a semantic relation classification problem, whereas balAPinc approaches it as a problem of designing an asymmetric similarity measure. The approach of balAPinc is near the level of the other two for some relation categories (e.g. class-inclusion, non-attribute) but substantially below for others (e.g. attribute, case relations, reference).

Table 7.

Accuracy for each of the ten high-level categories in the Test set

We explore the contribution of each set of features to the performance of SimDiffs in Table 8. In the columns for S ₁ to S ₄, a value of 1 indicates that the set is included in the feature vector and 0 indicates that the set is excluded (see Section 6.3). S ₁ is the difference between a and b in domain space with respect to their similarities to the reference words, R. S ₂ is the difference between a and b in function space. S ₁ and S ₂ are based on differences in the same spaces, whereas S ₃ and S ₄ are based on differences in different spaces. The parameters are tuned individually for each row in Table 8 in the same way as they are tuned for SimDiffs in Table 6. The results are based on the Test set.

Table 8.

Experiments with subsets of SimDiffs features

Most of the differences in the accuracies in Table 8 are not significant, but according to Fisher’s Exact Test at the 95% confidence level, the accuracy of all of the features together (72.4%) is significantly higher than the accuracy of S ₁ and S ₂ without the help of S ₃ and S ₄ (68.0%). This supports the view that working with two different spaces has a synergetic effect, since each feature in S ₃ and S ₄ is based on two different spaces, whereas each feature in S ₁ and S ₂ is based on one space. (See the discussion of this in Section 6.3.)

Let Gen (general) refer to the matrix from Turney et al. (Reference Turney, Neuman, Assaf and Cohen2011), and let Dom and Fun refer to the domain and function matrices from Turney (Reference Turney2012). In Section 6, we mentioned that we performed experiments on the development datasets (Dev1 and Dev2) in order to select the matrices for each algorithm. Based on these experiments, we chose the Gen matrix for both balAPinc and ConVecs, and chose the Dom and Fun matrices for SimDiffs.

In Table 9, we vary the matrices and evaluate the performance on the Test set to see whether the development datasets were a reliable guide for choosing the matrices. The matrices that were chosen based on the development datasets are in bold font. For balAPinc, Gen (57.3%) is indeed the best matrix. For ConVecs, it seems that Fun (71.9%) might be a better choice than Gen (70.2%), but the difference in their accuracy is not statistically significant. For SimDiffs, Dom and Fun (72.4%) are slightly less accurate than Gen and Fun (72.8%), but again the difference is not significant. As expected, no matrices are significantly better on the Test set than the matrices that were chosen based on the development datasets.

Table 9.

Effect of the matrices on the performance of the algorithms

8.2 Experiments with the KDSZ dataset

The second set of experiments used the KDSZ dataset (Section 7.1). This dataset has 3,772 word pairs, 2,704 in class 0 and 1,068 in class 1.

8.2.1 Experimental setup

We experimented with four different ways of splitting the dataset. The Evaluation column in Table 10 indicates the experimental setup (dataset splitting).

Table 10.

Comparison of the three algorithms on the KDSZ dataset

The standard evaluation is ten-fold cross-validation in which the folds are random. This evaluation yields relatively high scores, because, although every pair in the KDSZ dataset is unique, many pairs share a common term. This makes supervised learning easier, because a pair in the testing fold will often share a term with several pairs in the training folds.

The clustered evaluation is designed to be more challenging than the standard evaluation. The clustered evaluation is ten-fold cross-validation with non-random folds. We put pairs that share a common term into the same fold. Due to the large number of pairs with shared terms, it is not possible to construct ten folds such that there are absolutely no terms that are shared by any two folds. Therefore, we gave a high priority to isolating the most common shared words to single folds, but we allowed a few less common shared words to appear in more than one fold. Thus, a pair in the testing fold will only rarely share a term with pairs in the training folds.

The standard and clustered evaluations have more examples in class 0 (does not entail) than in class 1 (entails). The balanced dataset takes the clustered evaluation a step further, by first clustering folds and then randomly removing pairs labeled as class 0 until all the folds have an equal number of pairs in both the classes.

For the different evaluation, instead of cross-validation, the algorithms are trained on the JMTH dataset and tested on the KDSZ dataset after the KDSZ dataset has been balanced by randomly removing pairs labeled as class 0.

The balAPinc measure has two parameters, max_F for the maximum number of features and T as a threshold for classification. In all the four experimental setups, we used the setting max_F = 1, 000, based on the tuning experiments with the JMTH dataset (Section 8.1). For T, we used the training split in each of the four experimental setups. For the standard, clustered, and balanced setups, the training split is the nine folds used for training in each step of the ten-fold cross-validation. For the different setup, the training split is the whole JMTH dataset. For all four setups, we set T to the value that optimized the F-measure on the training split.

ConVecs has two parameters to tune, k and p for U_kΣ^p_k. In all the four experimental setups, we used k = 100 and p = 0.4, based on the experiments with the JMTH dataset. The training splits were used to teach the supervised learning algorithm (the polynomial kernel SMO SVM in Weka).

SimDiffs has four parameters to tune. We used k _d = k _f = 200 and p _d = p _f = 0.6, based on the experiments with the JMTH dataset. The training splits were used to teach the supervised learning algorithm (the radial basis function kernel SMO SVM in Weka).

8.3 Experiments with the BBDS dataset

The final set of experiments used the BBDS dataset (Section 7.2). The dataset has 2,770 word pairs, 1,385 in class 0 and 1,385 in class 1.

8.3.1 Experimental setup

We experimented with three different ways of splitting the dataset. In Table 11 the evaluations follow the same setups as in Table 10. However, there is no balanced setup, since the BBDS dataset is already balanced. In the different evaluation, the algorithms are trained on the JMTH dataset and evaluated on the BBDS dataset. This is the most realistic evaluation setup.

Table 11.

Comparison of the three algorithms on the BBDS dataset