2.1 Taxonomy learning models

Models for automatically learning semantic networks of words, such as taxonomies, from texts use variants of the distributional hypothesis (DH) (Harris Reference Harris, Katz and Fodor1964) or exploit some induced lexico-syntactic patterns (LSP) (Robison Reference Robison1970).

The distributional hypothesis is widely used in many approaches for taxonomy induction from texts. For example, it is used in Cimiano et al. (Reference Cimiano, Hotho and Staab2005) for populating lattices, i.e. graphs of a particular class, of formal concepts. Namely, the distributional hypothesis is exploited to extract attributes for objects. Nodes of the lattice are obtained and clustering objects with similar attributes and hierarchical links are drawn between two nodes, A and B, if the set of attributes of A is an included subset of attributes of B. These lattices are then used to build taxonomic hierarchies. The idea of drawing taxonomy links using the inclusion of features derived by exploiting the distributional hypothesis has been also used by Geffet and Dagan (Reference Geffet and Dagan2005), where the distributional inclusion hypothesis is defined. The distributional inclusion hypothesis basically states that a word ‘a’ is a generalization of a word ‘b’ if the properties representing the context of ‘a’ are included in those representing the context of ‘b’. The DH methods implicitly use transitivity. Yet, these methods cannot be easily extended to semantic relations other than generalization and similarity. The LSP models are more general, as these models can be potentially used for deciding whether any type of semantic relation holds between two words. This approach has been widely used for detecting hypernymy relations (Hearst Reference Hearst1992; Morin Reference Morin1999), other ontological relations (Pantel and Pennacchiotti Reference Pantel and Pennacchiotti2006), more generic relations (Ravichandran and Hovy Reference Ravichandran and Hovy2002; Szpektor et al. Reference Szpektor, Tanev, Dagan and Coppola2004), and relations among verbs (Chklovski and Pantel Reference Chklovski and Pantel2004; Zanzotto, Pennacchiotti and Pazienza Reference Zanzotto, Pennacchiotti and Pazienza2006). The LSP learning models generally use the hypothesis that two words have a particular relation if they frequently appear in specific text fragments. LSP are prototypical text fragments related to a particular relation. For example, given the isa relation, X is a Y if X and Y are frequently found in contexts, such as ‘X is a Y’, ‘X as well as Y’, or ‘X, Y,’. Given the relation R, a pair of words (X, Y), and the patterns related to the relation R, the above-mentioned learning methods tend to determine a confidence weight that expresses to which degree the relation R holds for the pair (X, Y) according to a collection of documents. The LSP models are interesting as they can learn any semantic relation. Yet, structural properties of target relations, such as transitivity, are generally not exploited. Even where transitivity is explicitly used (Snow et al. Reference Snow, Jurafsky and Ng2006), it is not directly exploited in determining confidence values. On the contrary, it is used in the iterative maximization process of the likelihood of the entire semantic network.

A last but important aspect when learning taxonomies and semantic networks from text collections is how existing resources are used. The DH models generally start learning from scratch. In Cimiano et al. (Reference Cimiano, Hotho and Staab2005), for example, lattices and related semantic networks are built from scratch. Yet, even when such prior knowledge is used in the DH models (Pekar and Staab Reference Pekar and Staab2002), the status of prior knowledge and produced knowledge is extremely different. Inserting new words in taxonomic networks is seen as a classification problem. Target classes are nodes of existing hierarchies. A distributional description of words is used to make the decision with respect to target classes. A new word and a word (or concept) existing in the network are then treated differently as the first is represented with its distributional vector while the second is one of the final classes. On the contrary, the LSP models (e.g. Snow et al. Reference Snow, Jurafsky and Ng2006) offer a more uniform way to represent prior and extracted knowledge. The insertion of a new word in the hierarchy is seen as a binary classification problem. The classification decision is taken over a pair of words, i.e. a word and its possible generalization. The classifier should decide whether the pairs belong to the taxonomy. Both existing and produced taxonomic relations have the same nature, i.e. pairs of words.

The taxonomy learning models based on LSP have then three advantages with respect to the DH models. First, these models can be used to learn any semantic relation (Hearst Reference Hearst1992; Morin Reference Morin1999; Ravichandran and Hovy Reference Ravichandran and Hovy2002; Chklovski and Pantel Reference Chklovski and Pantel2004; Szpektor et al. Reference Szpektor, Tanev, Dagan and Coppola2004; Pantel and Pennacchiotti Reference Pantel and Pennacchiotti2006; Zanzotto et al. Reference Zanzotto, Pennacchiotti and Pazienza2006). Second, these models coherently exploit existing taxonomies in the expansion phase (Snow et al. Reference Snow, Jurafsky and Ng2006). Third, the classification is binary, i.e. a word pair belongs or does not belong to the taxonomy (Pantel and Pennacchiotti Reference Pantel and Pennacchiotti2006; Snow et al. Reference Snow, Jurafsky and Ng2006). In this way, a single classifier is associated to each treated relation. Among the LSP taxonomy learning models, we select a probabilistic approach because in this way we can model both existing and new knowledge with probabilities. This is needed to positively exploit transitivity during learning.

2.2 Feature selection models

In applications involving texts as the LSP taxonomy learners, machine learning or probabilistic models are exposed to huge feature spaces. This has not always positive effects. The first important problem is that huge feature spaces require large computational and storage resources. The second problem is that more features do not always result in better accuracies of learned classification models. Many features can be noisy. Feature selection, i.e. the reduction of the feature space offered to machine learners, is seen as a solution (Guyon and Elisseeff Reference Guyon and Elisseeff2003).

There is a wide range of feature selection models that can be classified in two main families: supervised and unsupervised models. The supervised models directly exploit the class of training instances for determining whether a feature is relevant or not. The idea is to select features that are highly correlated with final target classes. Information theoretic ranking criteria, such as mutual information and information gain, are often used (Dhillon et al. Reference Dhillon, Mallela, Guyon and Elisseeff2003). Unsupervised models are instead used when the classification of training instances is not available at the training time or it is inapplicable, such as in information retrieval. Straightforward and simple models for unsupervised feature selection can be derived from information retrieval weighting schemes, e.g. term frequency times inverse document frequency (tf * idf). In this case, relevant features are respectively those appearing more often or those being more selective, i.e. appearing in fewer instances.

Feature selection models are also widely used in taxonomy learning. For example, attribute selection for building lattices of concepts in Cimiano et al. (Reference Cimiano, Hotho and Staab2005) is done by applying specific thresholds on specific information measures on attributes extracted from corpora. This model uses conditional probabilities, point-wise mutual information, and a selectional-preference-like measure, as the one introduced in Resnik (Reference Resnik1993).

In taxonomy and semantic network learning, negative cases are few or artificially produced. In natural conditions for taxonomy learning, we have only positive cases as training, whereas in artificial conditions we can have both positive and negative cases as training examples. These latter conditions are less frequent. Then we can only apply unsupervised methods for feature selection because these methods can be applied in both natural and artificial conditions.

3.1 Confidence weights, probabilities, and corpus-based knowledge learning

Any corpus-based knowledge learning method augments existing knowledge repositories with new information extracted from texts. In this process, we have two big issues. First, we are mixing reliable with unreliable information. Second, we are dealing with the ambiguity of natural language that affects every bit of discovered knowledge. For these two issues, we believe that storing and exploiting the probability within semantic networks is needed.

Mixing reliable concepts, relations among concepts, and instances with semi-reliable extracted information is a big problem, as final knowledge repositories cannot be considered reliable. Generally, extracted knowledge items are included in final resources if the related estimated confidence weights are above a threshold. Accuracy of added information is generally evaluated over a small randomly selected portion (e.g. Lin and Pantel Reference Lin and Pantel2001; Pantel and Pennacchiotti Reference Pantel and Pennacchiotti2006; Snow et al. Reference Snow, Jurafsky and Ng2006). Final knowledge repositories then contain two different kinds of information. The first is reliable and controlled information, and the second, i.e. the above-a-threshold extracted information, is semi-reliable information. Its accuracy is below 100 percent and generally varies in different ranges of confidence weights. High confidence values guarantee higher accuracy (e.g. Snow et al. Reference Snow, Jurafsky and Ng2006). Therefore it is extremely important that corpus extracted knowledge items report confidence weights justifying the inclusion in the knowledge base. In this way, consumers of knowledge repositories can decide if information is ‘reliable enough’ to be applied in their task.

Ambiguity of natural language is the second reason why knowledge repositories should store confidence weights (or probabilities) of extracted knowledge items. For example, the word ‘dog’ can be generalized to the word ‘animal’ or to the word ‘device’, according to which sense is taken into account. A decision system working with words would have a beneficial effect on its accuracy knowing the probabilities of two different generalizations. The simple ordering of word senses in WordNet (Miller Reference Miller1995) (first sense heuristic) according to their frequencies is useful for open domain word sense disambiguation models. This effect is preserved in specific domains, as prior sense probabilities computed within specific domains has again a positive effect for word sense disambiguation processors (McCarthy et al. Reference McCarthy, Koeling, Weeds and Carroll2004). Experiences in different NLP tasks, such as part-of-speech (POS) tagging, suggest that it is important to model and store these probabilities. In Yoshida et al. (Reference Yoshida, Tsuruoka, Miyao, Tsujii and Veloso2007) comparison between three POS taggers is shown: first emitting one interpretation per word, second emitting multiple interpretations, and, finally, third emitting multiple interpretations with associated probabilities. These POS taggers are then evaluated with respect to the performances obtained by a parser. Even if the probabilistic model of the parser is different with respect to the one of the POS tagger, the parser has better performances with respect to the third POS tagger that emits tags and the associated probabilities.

Yet, even if it is important, including confidence weights in knowledge repositories is not a trivial problem when considering semantic relations with structural properties as transitivity. In methods such as given by Pantel and Pennacchiotti (Reference Pantel and Pennacchiotti2006), it seems possible to easily include some initial values in the final resource, as these have been used for deciding whether the knowledge base should include a relation. Yet, when we need to combine these values in transitive relations, we need to be extremely careful on how these values have been estimated and computed. For example, if we discover from corpus analysis that ‘dog’ is a ‘canine’ and we already know that ‘canine’ is an ‘animal’ (see Figure 1(a)), using transitivity we can derive the induced relation, i.e. dog is an animal (the dashed arrow in Figure 1(a)). Yet, we cannot easily combine confidence weights if the nature of these weights is obscure.

Fig. 1.

Examples of relations derived by exploiting the transitivity.

The solution generally proposed for combining confidence weights is neglecting their nature. The final relation between two words has the same confidence weight as that of a reliable and controlled information. Even in probabilistic models (Snow et al. Reference Snow, Jurafsky and Ng2006), these reliable and unreliable information is mixed during the knowledge acquisition process. In these models, if ‘canine’ is an ‘animal’ (see Figure 1(a)) is in the original manually controlled network and ‘dog’ is a ‘canine’ has a high probability from the corpus observations, this latter is included in the knowledge base with the same degree of plausibility as that of ‘canine’ is an ‘animal’. Then, the induced relation ‘dog’ is an ‘animal’ has again the same degree of plausibility as that of manually controlled information. This is a loss of information, as the uncertainty of the relation ‘dog’ is an ‘animal’ is neglected.

3.2 Probabilistic definitions for concepts

As keeping and propagating uncertainty in transitive semantic networks is important, we propose an inductive taxonomy learning model, i.e. a probabilistic taxonomy learning model based on LSP that exploits transitivity during learning for determining confidence weights. Our model stems from the intuition that the LSP learning models contribute to probabilistic definitions of target concepts and that it is possible to combine these definitions to determine confidence weights derived in transitive networks. We hereafter observe how the LSP models contribute to the formal definitions of concepts; then we define what is a probabilistic definition, and, finally, describe how these probabilistic definitions can be used to determine two LSP inductive learning models: the intensional and the extensional model.

The LSP methods derive formal definitions for concepts (or, better, for words or word sequences) from texts. Extracting evidence from corpora suggesting that ‘dog’ is an ‘animal’ contributes to the definitions of ‘dog’ and ‘animal’. In the case of ‘dog’, the relation between ‘dog’ and ‘animal’ contributes to the intensional definition of ‘dog’ as it is stating that a ‘dog’ is an ‘animal’ with specific features. In the case of ‘animal’, this relation contributes, in a wide sense, to the extensional definitionFootnote ¹ of ‘animal’. It is like we are giving one of the possible instancesFootnote ² of the concept ‘animal’. These formal intensional and extensional definitions are often used to derive the similarity among words or concepts. Cotopy (Maedche and Staab Reference Maedche and Staab2002), a measure for determining similarity between concepts in two different semantic networks, uses exactly this information.

A probabilistic definition of a concept is an intensional definition associated with its induced probabilities. These probabilities are derived from the topology of transitive semantic networks mixing of existing knowledge and corpus estimated probabilities. In Figure 1, we report two kinds of arrows: the solid and the dashed ones. The solid arrow indicates relations derived from the existing structured knowledge repositories and from corpus analysis. The dashed arrow indicates the probabilities induced from the structure of the network. We want to describe the probability of the dashed relations using the probabilities of the solid ones. We call direct probabilities the first type and induced probabilities the second one.

Within the idea described above, we propose two models that derive induced probabilitic definitions from direct probabilities: the first exploits intensional definitions of concepts and the second exploits extensional definitions. We then name these two ways: the intensional inductive probabilistic model and the extensional probabilistic inductive model. To give an intuitive idea of our model, we use the example given in Figure 1.

The intensional inductive model exploits direct intensional definitions to derive an induced intensional definition. In Figure 1(a), we have, as direct information, the probabilities of the relations ‘dog’ is a ‘canine’ and ‘canine’ is an ‘animal’. From these two relations, we can derive the induced probability of the intensional definition of ‘dog’ is an ‘animal’. In this case we are exploiting and modeling the transitivity of a relation.

The extensional inductive model uses solid arrows, i.e. direct probabilities, to form extensional definitions of the concepts and compare the different extensional definitions for determining the final induced probability. In Figure 1(b), the relations ‘dog’ is an ‘animal’ and ‘dog’ is a ‘canine’ are used to form a very small part of the extensional definitions of ‘animal’ and ‘canine’, respectively. The idea is that these extensional definitions can be used to determine the similarity of ‘animal’ and ‘canine’. Then, we can derive the induced probability of the relation ‘dog’ is an ‘animal’. Using the same intuition, the relations ‘dog’ is an ‘animal’ and ‘canine’ is an ‘animal’ contribute to the extensional definition of ‘animal’ (see Figure 1(c)). Using all the other relations, we want to derive the induced probability of the relation ‘dog’ is a ‘canine’.

4.1 Direct and inductive probabilistic models

As in Pantel and Pennacchiotti (Reference Pantel and Pennacchiotti2006) and Snow et al. (Reference Snow, Jurafsky and Ng2006)(Pantel and Pennacchiotti Reference Pantel and Pennacchiotti2006; Snow et al. Reference Snow, Jurafsky and Ng2006), we model the taxonomy learning problem as a binary classification task. Given a pair of words (i, j) and a vector of observed features _i,j, we want to build a binary classifier that determines if i is a j using _i,j and gives the related confidence weight. As in Snow et al. (Reference Snow, Jurafsky and Ng2006), we see this problem in a probabilistic setting, as it gives us the possibility to determine the direct probability model as well as the induced probabilistic model.

We here propose a model to exploit transitivity within probabilistic taxonomy learners that use LSP. Using LSP on a corpus, we can extract pairs of words in a given relation along with their reliability. These pairs of words and their reliabilities are directly observed. For example (see Figure 2), given the hyperonymy relation, we directly derive the reliabilities of the pairs ‘dog’ is a ‘canine’ (0.8), ‘canine’ is an ‘animal’ (0.7), and ‘dog’ is an ‘animal’ (0.2) (see the values on the solid arrows). If we now look at all these pairs together, we can observe that these words form a semantic network where transitive property holds. Even if the directly observed reliability of the pair ‘dog’ is an ‘animal’ is low (0.2), transitivity of the network suggests that this reliability should be higher (0.648). We exactly want to exploit the transitive network to induce the reliability of the relation between ‘dog’ and ‘animal’ (see the dashed arrow) using all the reliabilities of the involved pairs directly observed from the corpus. We then use a probabilistic setting where this composition of confidence weights can be better controlled.

Fig. 2.

Example of relations derived by exploiting transitivity.

In the direct probabilistic model, we define the direct events R _i,j ∈ T, where T is the taxonomy. If R _i,j is in T, i is a concept and j is one of its generalizations. For example, R _dog,animal ∈ T describes that dog is an animal according to the taxonomy T. The learning problem in the direct setting is to determine the probabilities:

1. (1)

where E is a set of evidences extracted from corpus analysis, i.e. a set of _i,j. We will hereafter refer to this probability as P(R _i,j|E).

With some independence assumptions, we can rewrite (1) as P(R _i,j|_i,j), where _i,j is the set of evidences for (i, j) derived from the corpus. These evidences are derived from the contexts where the pair (i, j) is found in the corpus. The vector _i,j is a feature vector associated with a pair (i, j). For example, a feature may describe how many times i and j are seen in patterns like ‘i as j’ or ‘i is a j’. These among many other features are indicators of an is-a relation between i and j (as discovered in Hearst Reference Hearst1992).

These direct probabilities P(R _i,j|_i,j) only depend on what has been observed in the corpus for a particular pair of words (i, j). As transitivity has not been considered, P(R _i,j|_i,j) are initial probabilities of our probabilistic model for taxonomy learning. In the example of Figure 2 we have the following direct probabilities (where d = dog, a = animal, and c = canine): P(R_d,a|_d,a) = 0.2, P(R_d,c|_d,c) = 0.8, and P(R_c,a|_c,a) = 0.7.

The inductive probabilistic model is the main innovation of our approach to taxonomy learning. Here we want to define an event space that models transitivity. We then introduce the events _i,j and the related probability function:

1. (2)

This probability function should capture the fact that a decision on the pair (i, j) also depends on the transitive relations activated by (i, j). It is not always the case that these relations are activated by the existing taxonomy links. Yet, this inductive probability takes into account transitively related taxonomic links. We examine different models to exploit the transitive property of the R relation, and for each of these models we show that P(_i,j|E) can be rewritten in terms of the involved P(R_h,k|E).

For example, we can compute the inductive intensional probability for the pair (dog,animal) in Figure 2. The inductive intensional probability P(_d,a|E) can be computed as the probability of the event _d,a = R_d,a ∪ (R_d,c ∩ R_c,a). This captures that the inductive event _d,a is active when R_d,a happens or the joint event R_d,c ∩ R_c,a happens. Then, using the inclusion–exclusion property, the previous independence assumptions on the evidences E, and an independence assumption between R _i,j, we can compute P(R_d,a ∪ (R_d,c ∩ R_c,a)|E) as

Given this initial idea, we formalize our inductive probabilistic models in next sections.

4.2 Three inductive probabilistic models

We propose three different methods for modeling induced probabilities. We call these intensional (Section 4.2.1), extensional (Section 4.2.2), and mixed models (Section 4.2.3). These three models exploit different definitions of the event _i,j ∈ T. In the intensional model (Section 4.2.1), the event _i,j ∈ T is represented as the event R _i,j ∈ T and for any k all the alternative events R_i,k ∈ T and R_k,j ∈ T. In the extensional model (Section 4.2.2), the event _i,j ∈ T is represented as the event R _i,j ∈ T and for any k all alternative events R_i,k ∈ T and R_j,k ∈ T and all the events R_k,j ∈ T and R_k,i ∈ T. The last model, mixed model (Section 4.2.3), is a combination of the previous two models.

4.2.1 The intensional inductive model

In the intensional inductive model, we exploit direct probabilities to derive the induced probabilistic intensional definition P_I(_i,j|E). We evaluate this probability using the direct probability of R _i,j ∈ T and the direct probabilities of having a transitive connection between i and j of two direct relations. For each possible node k, we then consider all alternative events R_i,k ∈ T and R_k,j ∈ T. We use a running example to illustrate the idea.

We suppose to have four elements in a network (see Figure 3): ‘lettuce’ (i), ‘food’ (j), ‘vegetable’ (k ₁), and ‘animal’ (k ₁). We empirically estimated the direct probabilities represented with bold arrows and want to determine the induced probability of the dashed arrow. Both the i − k ₁ − j and i − k ₂ − j paths offer some information to the final induced probability even if we expect that P(R _{i,k 1}|E), i.e. the direct probability of ‘lettuce’ is a ‘vegetable’, is near to 1 and that P(R _{i,k 2}|E), i.e. the direct probability of ‘lettuce’ is an ‘animal’, is near to 0. We compute the induced probability as the probability of alternative events that represents the sub-part of the network of direct events. In this case the induced probability is as follows:

Fig. 3.

Example of internal inductive model.

We can compute this probability using the inclusion–exclusion principle and some assumptions on the independence among events. The inclusion–exclusion principle gives the possibility of computing the probabilities of alternative events. Given n probabilistic events A ₁, A ₂,. . ., A_n in a probability space, the probability of the union of these events is as follows:

where A_J = ⋂_i∈JA_i. The probability P_I(_i,j|E) can then be rewritten as

Finally, assuming that the probabilities of the direct events, R_n,m, are independent, we can determine the probabilities of any of the joint events as products of the probabilities of the events, e.g.: P(R _{i,k 1} ∩ R _k1,j|E) = P(R _{i,k 1}|_{i,k 1})P(R _{k 1,j}|_{k 1,j}).

The general equation for the induced intensional probability is as follows:

where K = {k ₁,. . ., k_n} is the set of the intermediate nodes considered between i and j. As in the case of (3), we can compute this equation using the inclusion–exclusion principle as follows:

where R_J = ⋂_k∈JR_k. Each R_k is defined as R _ε = R _i,j and R_k = (R_i,k ∩ R_k,j) if k ≠ ε. Using the assumption that direct probabilities of R_m,n are independent, we can also rewrite P(R_J|E) as

where P(R _ε|E) = P(R _i,j|_i,j) and P(R_k|E) = P(R_i,k|_i,k)P(R_k,j|_k,j), if k ≠ ε.

4.2.2 The extensional inductive model

The extensional inductive model exploits the extensional definitions of the concepts to derive the induced probabilities. Figure 4 reports an example where two different models are adopted. The first model (see Figure 4(a)) uses the extensional definition of the two involved concepts, i.e. ‘turkey’ and ‘boat’, to determine the probability of the induced relation ‘bird’ is a ‘beast’, i.e. P(_i,j|E). The similarity between the extensional definition of ‘bird’ (i) and ‘beast’ (j) should help in determining the probability of the relation between the two concepts. In the second model (see Figure 4(b)), ‘animal’ and ‘penguin’ contribute to the extensional definition of both organism and ‘artifact’. This should help in determining the probability P(_i,j|E) of the induced event _i,j. In the case of the reported running examples, the probability of the induced event is

1. (3)

These probability equations can be reduced using the inclusion–exclusion principle and the independence assumption between the direct events. We can then rewrite this equation as

Fig. 4.

Example of external inductive model.

We can finally write the general equation using the extensional probabilistic definitions of the concepts. In this model we mix the two previous models in one single equation. The probability P(_i,j|E) of the induced event _i,j is then rewritten in term of the probabilities of the direct events as follows:

4.2.3 The mixed inductive model

The mixed inductive model unifies the above-mentioned methods, considering both the intensional and the extensional probabilistic models. Formally,

Similarly, the inclusion–exclusion principle can be used to evaluate the alternative probability for the mixed method.

The complete computation of the inductive probabilistic models presented in this section is unfeasible, as the computation of inclusion–exclusion principle is combinatorial with respect to the set of alternative events J. We then use an approximated computation derived from the method described in Kahn, Linial and Samorodnitsky (Reference Kahn, Linial and Samorodnitsky1993).

5.1 Logistic regression

Logistic regression (Cox Reference Cox1958) is a particular type of statistical model for relating responses Y to linear combinations of predictor variables X. It is a specific kind of generalized linear model (see Nelder and Wedderburn Reference Nelder and Wedderburn1972), where its function is the logit function and the dependent variable Y is a binary or dicothomic variable, which has a Bernoulli distribution. The dependent variable Y takes value 0 or 1. The probability that Y has value 1 is a function of the regressors x = (1, x ₁,. . .,x_k).

The direct probability P(R _i,j|_i,j) falls in the category of probabilistic models, where the logistic regression, which can be applied as R _i,j ∈ T, is the binary-dependent variable and _i,j is the vector of its regressors.

We start from formally describing the logistic regression model. Given a binary stochastic variable Y and a generic stochastic variable X for the regressors, we can define p as the probability of Y to be 1 given X = , i.e.

The distribution of the variable Y is a Bernoulli distribution. Given the definition of the logit(p) as

1. (4)

and given the fact that Y is a Bernoulli distribution, the logistic regression predicts that the logit is a linear combination of the values of the regressors, i.e.

1. (5)

where β₀, β₁,. . ., β_k are called regression coefficients of the variables x ₁,. . ., x_k, respectively.

5.2 Estimating regression coefficients

The second issue is how to estimate the regression coefficients. This estimation can be done using the maximal likelihood estimation. The above logit definition generate a set of linear equations. The linear problem is then solved by introducing a pseudo-inverse matrix, the original matrix being usually rectangular and singular.

Once we have calculated the regression coefficients, we have the possibility of estimating a probability P(R _i,j|_i,j) given any configuration of the values of the regressors _i,j, i.e. the observed values of the features.

The estimation of the β coefficients can be obtained as follows. Let us assume to have a multiset O of observations extracted from a corpus. Elements of the multiset are (y,_i,j), where y = 1 if (i, j) is a positive case and y = 0 if (i, j) is a negative case. We can now derive the set E of all the different vectors _i,j. For the sake of simplicity, we call these vectors . For each ∈ E, we can use the maximum likelihood to estimate the initial probability P(Y = 1|) as the frequency of the pair (1, ) in O divided by the frequency of . For each ∈ E, we have a set of equations of this kind:

1. (6)

where m is the size of the feature space. This set of equations can be written as a linear equation system:

1. (7)

where Q is a matrix that includes a constant column of 1, necessary for the β₀ of the linear combination of the values of the regression. The matrix is

The set of equations in (7) is a particular case of multiple linear regression (Caron, Hospital and Corey Reference Caron, Hospital and Corey1998).

As Q is a rectangular and singular matrix, Q is not invertible and the system = Qβ has no solutions. Yet, it is possible to use the principle of least square estimation. With this principle we can determine the solution β that minimize the residual norm, i.e.

1. (8)

This problem can be solved by the Moore–Penrose pseudoinverse Q ⁺ (Penrose Reference Penrose1995) that gives the following final equation:

1. (9)

It is important to remark that if the inverse matrix exists, then Q ⁺ = Q ⁻¹ and Q ⁺Q, QQ ⁺ are symmetric.

5.3 Computing pseudoinverse matrix with SVD analysis

We can finally illustrate why it is natural to use SVD as feature selection in a probabilistic taxonomy learner. In the previous sections we described how the probabilities of the taxonomy learner can be estimated using logistic regressions and concluded that a way to determine the regression coefficients β is by computing the Moore–Penrose pseudoinverse Q ⁺. Here we compute Moore–Penrose pseudoinverse Q ⁺ by using SVD in the following way (Penrose Reference Penrose1955). Given an SVD decomposition of the matrix Q = UΣV^T, the pseudo-inverse matrix that minimizes the (8) is

1. (10)

The diagonal matrix Σ⁺ is the r × r transposed matrix of Σ having as diagonal elements the reciprocals of the Σ singular values .

As we are using SVD in the computation of the pseudo-inverse matrix, we have the possibility of exploiting it as an unsupervised feature selection model. We can compute different approximations of the pseudo-inverse matrix. The algorithm for computing the singular value decomposition is iterative (Golub and Kahan Reference Golub and Kahan1965). The firstly derived dimensions are those with higher singular values. We can consider different k in order to obtain different SVD as approximations of the original matrix (10). We can define different approximations of the inverse matrix Q ⁺ as Q_k ⁺, i.e.

where Q_k ⁺ is a matrix n by m obtained considering the first k singular values.

The property of the singular values computed by the Golub and Kahan (Reference Golub and Kahan1965) algorithm, i.e. δ₁ ≥ δ₂ ≥ ⋅⋅⋅ ≥ δ_r > 0, guarantees that the first k are bigger than the discarded ones. There is a direct relation between the informativeness of the i-th new dimension and the singular value δ_i. High singular values correspond to dimensions of the new space where examples have more variability, whereas low singular values determine dimensions where examples have a smaller variability (Liu Reference Liu2007). These latter dimensions can then be hardly used as efficient features in learning. The possibility of computing approximated versions of matrices gives a powerful method for feature selection and filtering as we can decide in advance the number of features or, better, linear combinations of original features we want to use.

7.1 Experimental set-up

To completely define the experiments we need to describe some issues: How do we define the taxonomy to replicate; which corpus have we used to extract evidences for pairs of words; and which feature space have we used.

As target taxonomy we selected a portion of WordNetFootnote ³ (Miller Reference Miller1995). Namely, we started from 44 concrete nouns divided into three classes: animal, artifact, and vegetable. For each word w, we selected the synset s_w that generalizes with the class it belongs to. We then obtained a set S of synsets, and expanded the set to S′ by adding the siblings (i.e. the coordinate terms) for each synset in S. The set S′ contains 265 coordinate terms plus the forty-four original concrete nouns. For each element in S we collected its hypernyms, obtaining the set H. We then removed from the set H the top four classes: entity, unit, object, and whole. The set H contains seventy-seven hypernyms. For the purpose of the experiments we derived a taxonomy T from the previous sets and produced a set of negative examples T. The two sets have been obtained as follows. The taxonomy T is the portion of WordNet implied by O = H ∪ S′, i.e. T contains all the (s, h) ∈ O × O that are in WordNet. On the contrary, T contains all the (s, h) ∈ O × O that are not in WordNet. We then have 4,596 positive pairs in T and 48,354 negative pairs in T.

To obtain the training and the testing sets, we randomly divided the set T ∪ T in two parts T_tr ∪ T_tr and T_ts ∪ T_ts, respectively, the 70per cent and 30per cent of the original T ∪ T.

As a corpus we used the English Web as Corpus (ukWaC) (Baroni et al. Reference Baroni, Bernardini, Ferraresi and Zanchetta2009). This is a web-extracted corpus of about 2,700,000 web pages containing more than two billion words. The corpus contains documents of different topics, such as web, computers, education, public sphere, etc. It has been largely demonstrated that the web documents are good models for natural language (Lapata and Keller Reference Lapata and Keller2004).

We used a bag-of-n-gram feature space for implicitly modeling LSP. Features are words, bigrams, and trigrams. These n-grams represent specific LPS. Given a pair (i, j) ∈ T ∪ T, we build the related feature vector _i,j using the contexts where the the words i and j appear in a window of at most five words. For each context of (i, j), the word sequence between i and j is used to increment the frequency of the related n-grams. For example, given the pair (car, vehicle), we can retrieve the context:

Considering only word sequences between the two target words, this context contributes to the features: as, a, motor, as a, a motor, and as a motor. These feaures are approximations of LSP.

7.3 Qualitative analysis of dimensionality reduction

The experiments show that we can positively use dimensionality reduction of SVD within the computation of the pseudo-inverse matrix. We now want to analyze the first dimensions to understand which linear combination of the original features is relevant for the specific task of learning taxonomies using lexical patterns. As the decomposition algorithm that we are using sorts the eigenvectors according to decreasing eigenvalues, we will examine the first eigenvector that should be more significant and the eigenvector number 400. In Table 2, we present only some of these eigenvectors. We present the dimensions with the ten largest values. The first ten dimensions of the first eigenvector are presented in column 2 and 3. The first ten dimension of the 400th eigenvector are presented in column 4 and 5.

Table 2.

Two selected eigenvectors on the bag-of-n-grams

The first eigenvector is very interesting as it mixes many classical indicators of hypernymy, e.g. ‘,’, ‘be’, ‘&’, etc. These indicators appear with different relative weights in many of the first eigenvectors. It is worth noticing that the forms of the verb to be are present in the considered eigenvector. On the contrary, the eigenvector number 400 does not contain any relevant information related to the hypernymy phenomenon in the first positions. This qualitatively explains what has been shown by the experiments in the previous section. Many dimensions in the reduced space are totally irrelevant.