Édouard Grave
email: grave@berkeley.edu

Guillaume Obozinski
email: guillaume.obozinski@imagine.enpc.fr

Francis Bach
email: francis.bach@ens.fr

A Markovian approach to distributional semantics with application to semantic compositionality

In this article, we describe a new approach to distributional semantics. This approach relies on a generative model of sentences with latent variables, which takes the syntax into account by using syntactic dependency trees. Words are then represented as posterior distributions over those latent classes, and the model allows to naturally obtain in-context and out-of-context word representations, which are comparable. We train our model on a large corpus and demonstrate the compositionality capabilities of our approach on different datasets.

Introduction

It is often considered that words appearing in similar contexts tend to have similar meaning [START_REF] Harris | Distributional structure[END_REF]. This idea, known as the distributional hypothesis was famously summarized by [START_REF] Firth | A synopsis of linguistic theory[END_REF] as follow: "you shall know a word by the company it keeps." The distributional hypothesis has been applied in computational linguistics in order to automatically build word representations that capture their meaning. For example, simple distributional information about words, such as co-occurence counts, can be extracted from a large text corpus, and used to build a vectorial representation of words [START_REF] Lund | Producing high-dimensional semantic spaces from lexical co-occurrence[END_REF][START_REF] Landauer | A solution to Plato's problem: The latent semantic analysis theory of acquisition, induction, and representation of knowledge[END_REF]. According to the distributional hypothesis, two words having similar vectorial representations must have similar meanings. It is thus possible and easy to compare words using their vectorial representations.

In natural languages, sentences are formed by the composition of simpler elements: words. It is thus reasonable to assume that the meaning of a sentence is determined by combining the meanings of its parts and the syntactic relations between them. This principle, often attributed to the German logician Frege, is known as semantic compositionality. Recently, researchers in computational linguistics started to investigate how the principle of compositionality could be applied to distributional models of semantics [START_REF] Clark | Combining symbolic and distributional models of meaning[END_REF][START_REF] Mitchell | Vector-based models of semantic composition[END_REF]. Given the representations of individual words, such as federal and agency, is it possible to combine them in order to obtain a representation capturing the meaning of the noun phrase federal agency?

Most approaches to distributional semantics represent words as vectors in a high-dimensional space and use linear algebra operations to combine individual word representations in order to obtain representations for complex units. In this article, we propose a probabilistic approach to distributional semantics. This approach is based on the generative model of sentences with latent variables, which was introduced by [START_REF] Grave | Hidden Markov tree models for semantic class induction[END_REF]. We make the following contributions:

• Given the model introduced by [START_REF] Grave | Hidden Markov tree models for semantic class induction[END_REF], we describe how in-context and ouf-of-context words can be represented by posterior distributions over latent variables (section 4).

• We evaluate out-of-context representations on human similarity judgements prediction tasks and determine what kind of semantic relations are favored by our approach (section 5).

• Finally, we evaluate in-context representations on two similarity tasks for short phrases (section 6).

Related work

Most approaches to distributional semantics are based on vector space models (VSM), in which words are represented as vectors in a high-dimensional space. These vectors are obtained from a large text corpus, by extracting distributional information about words such as the contexts in which they appear.

A corpus is then represented as a word-by-context co-occurence matrix. Contexts can be defined as documents in which the target word appear [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF][START_REF] Landauer | A solution to Plato's problem: The latent semantic analysis theory of acquisition, induction, and representation of knowledge[END_REF] or as words that appear in the neighbourhood of the target word, for example in the same sentence or in a fixed-size window around the target word [START_REF] Schutze | Dimensions of meaning[END_REF][START_REF] Lund | Producing high-dimensional semantic spaces from lexical co-occurrence[END_REF].

Next to vector space models, other approaches to distributional semantics are based on probabilistic models of documents, such as probabilistic latent semantic analysis (pLSA) introduced by Hofmann (1999) and which is inspired by latent semantic analysis, or latent Dirichlet allocation (LDA), introduced by [START_REF] Blei | Latent dirichlet allocation[END_REF]. In those models, each document is viewed as a mixture of k topics, where each topic is a distribution over the words of the vocabulary.

The previous models do not take into account the linguistic structure of the sentences used to build word representations. Several models have been proposed to address this limitation. In those models, the contexts are defined by using the syntactic relations between words [START_REF] Lin | Automatic retrieval and clustering of similar words[END_REF][START_REF] Curran | Scaling context space[END_REF][START_REF] Turney | Similarity of semantic relations[END_REF][START_REF] Padó | Dependency-based construction of semantic space models[END_REF][START_REF] Baroni | Distributional memory: A general framework for corpus-based semantics[END_REF]. For example, two words are considered in the same context if there exists a syntactic relation between them, or if there is a path between them in the dependency graph.

One of the first approaches to semantic compositionality using vector space models was proposed by [START_REF] Mitchell | Vector-based models of semantic composition[END_REF]. In this study, individual word representations are combined using linear algebra operations such as addition, componentwise multiplication, tensor product or dilation. Those different composition operations are then used to disambiguate intransitive verbs given a subject [START_REF] Mitchell | Vector-based models of semantic composition[END_REF] or to compute similarity scores between pairs of small phrases [START_REF] Mitchell | Composition in distributional models of semantics[END_REF].

Another approach to semantic compositionality is to learn the function used to compose individual word representations. First, a semantic space containing representations for both individual words and phrases is built. For example, the words federal, agency and the phrase federal agency all have a vectorial representation. Then, a function mapping individual word representations to phrase representations can be learnt in a supervised way. [START_REF] Guevara | A regression model of adjective-noun compositionality in distributional semantics[END_REF] proposed to use partial least square regression to learn this function. Similarly, [START_REF] Baroni | Nouns are vectors, adjectives are matrices: Representing adjective-noun constructions in semantic space[END_REF] proposed to learn a matrix A for each adjective, such that the vectorial representation p of the adjective-noun phrase can be obtained from the vectorial representation b of the noun by the matrix-vector multiplication: [START_REF] Socher | Semantic compositionality through recursive matrixvector spaces[END_REF] later generalized this model by proposing to represent each node in a parse tree by a vector capturing the meaning and a matrix capturing the compositional effects. A composition function, inspired by artificial neural networks, is recursively applied in the tree to compute those representations.

p = Ab.
Following the theoretical framework introduced by [START_REF] Coecke | Mathematical foundations for a compositional distributional model of meaning[END_REF], [START_REF] Grefenstette | Experimental support for a categorical compositional distributional model of meaning[END_REF] proposed to represent relational words (such as verbs) by tensors and theirs arguments (such as nouns) by vectors. Composing a relational word with its arguments is then performed by taking the pointwise product between the tensor and the Kronecker product of the vectors representing the arguments. [START_REF] Jenatton | A latent factor model for highly multi-relational data[END_REF] and [START_REF] Van De Cruys | A tensor-based factorization model of semantic compositionality[END_REF] proposed two approaches to model subject-verb-object triples based on tensor factorization.

Finally, research in computation of word meaning in context is closely related to distributional semantic compositionality. [START_REF] Erk | A structured vector space model for word meaning in context[END_REF] proposed a structured vector space model in which a word is represented by multiple vectors, capturing its meaning but also the selectional restrictions it has for the different arguments. Those different vectors can then be combined to compute a word representation in context. This model was later generalized by [START_REF] Thater | Contextualizing semantic representations using syntactically enriched vector models[END_REF]. [START_REF] Dinu | Measuring distributional similarity in context[END_REF] introduced a probabilistic model for computing word representations in context. In their approach, words are represented as probability distributions over latent senses.

Computers can be designed to do anything with information

c 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 w 1 w 2 w 3 w 4 w 5 w 6 w 7 w 8 w 9
Figure 1: Example of a dependency tree and its corresponding graphical model.

Model of semantics

In this section we briefly review the generative model of sentences introduced by Grave et al. ( 2013), and which serves as the basis of our approach to distributional semantics.

Generative model of sentences

We denote the tokens of a sentence of length K by the K-uple w = (w 1 , ..., w K ) ∈ {1, ..., V } K , where V is the size of the vocabulary and each integer represents a word. We suppose that each token w k is associated to a corresponding semantic class c k ∈ {1, ..., C}, where C is the number of semantic classes. Finally, the syntactic dependency tree corresponding to the sentence is represented by the function π : {1, ..., K} → {0, ..., K}, where π(k) represents the parent of word k and 0 is the root of the tree (which is not associated to a word). Given a tree π, the semantic classes and the words of a sentence are generated as follows. The semantic class of the root of the tree is set to a special start symbol, represented by the integer 0.1 Then, the semantic classes corresponding to words are recursively generated down the tree: each semantic class c k is drawn from a multinomial distribution p T (c k | c π(k) ), conditioned on the semantic class c π(k) of its parent in the tree. Finally, each word w k is also drawn from a multinomial distribution p O (w k | c k ), conditioned on its corresponding semantic class c k . Thus, the joint probability distribution on words and semantic classes can be factorized as

p(w, c) = K k=1 p T (c k | c π(k) )p O (w k | c k ),
where the variable c 0 = 0 represents the root of the tree. The initial class probability distribution p T (c k | c 0 = 0) is parameterized by the probability vector q, while the transition probability distribution between classes p T (c k | c π(k) ) and the emission probability distribution p O (w k | c k ) are parameterized by the stochastic matrices T and O (i.e., matrices with non-negative elements and unit-sum columns). This model is a hidden Markov model on a tree (instead of a chain). See Fig. 1 for an example of a sentence and its corresponding graphical model.

Corpus and learning

We train the generative model of sentences on the ukWac corpus [START_REF] Baroni | The WaCky wide web: a collection of very large linguistically processed web-crawled corpora[END_REF]. This corpus, which contains approximately 1.9 billions tokens, was POS-tagged and lemmatized using TreeTagger [START_REF] Schmid | Probabilistic part-of-speech tagging using decision trees[END_REF] and parsed using MaltParser [START_REF] Nivre | Maltparser: A language-independent system for data-driven dependency parsing[END_REF]. Each word of our vocabulary is a pair of lemma and its part-of-speech. We perform smoothing by only keeping the V most frequent pairs, the infrequent ones being replaced by a common token. The parameters θ = (q, T, O) of the model are learned using the algorithm described by [START_REF] Grave | Hidden Markov tree models for semantic class induction[END_REF]. The number of latent states C and the number of lemma/POS pairs V were set using the development set of [START_REF] Bruni | Distributional semantics in technicolor[END_REF]. [START_REF] Borg | Modern multidimensional scaling: Theory and applications[END_REF]. See text for details.

Word representations

Given a trained hidden Markov model, we now describe how to obtain word representations, for both incontext and out-of-context words. In both cases, words will be represented as a probability distribution over the latent semantic classes.

In-context word representation. Obtaining a representation of a word in the context of a sentence is very natural using the model introduced in the previous section: we start by parsing the sentence in order to obtain the syntactic dependency tree. We then compute the posterior distribution of semantic classes c for that word, and use this probability distribution to represent the word. More formally, given a sentence w = (w 1 , ..., w K ), the kth word of the sentence is represented by the vector u k ∈ R C defined by

u k i = P(C k = i | W = w).
The vector u k is the posterior distribution of latent classes corresponding to the kth word of the sentence, and thus, sums to one. It is efficiently computed using the message passing algorithm (a.k.a. forwardbackward algorithm for HMM).

Out-of-context representation. In order to obtain word representations that are independent of the context, we compute the previously introduced in-context representations on a very large corpus, and for each word type, we average all the in-context representations for all the occurrences of that word type in the corpus. More formally, given a large set of pairs of tokens and their in-context representations (w k , u k ) ∈ N × R C , the representation of the word type a is the vector v a ∈ R C , defined by

v a = 1 Z a k : w k =a u k ,
where Z a is the number of occurrences of the word type a. The vector v a is thus the posterior distribution of semantic classes averaged over all the occurrences of word type a.

Comparing in-context and out-of-context representations. Since in-context and out-of-context word representations are defined on the same space (the simplex of dimension C) it is possible to compare in-context and out-of-context representations easily. As an example, we have plotted in Figure 2 the out-of-context representation for the words head, president, chief, chairman, director, executive, eye, face, shoulder, hand, leg, etc. and the in-context representations for the word head in the context of the two following sentences:

1. The nurse stuck her head in the room to announce that Dr. Reitz was on the phone. The two-dimensional visualization is obtained by using multidimensional scaling [START_REF] Borg | Modern multidimensional scaling: Theory and applications[END_REF]. First of all, we observe that the words are clustered in two groups, one containing words belonging to the body part class, the other containing words belonging to the leader class, and the word head, appears between those two groups. Second, we observe that the in-context representations are shifted toward the cluster corresponding to the disambiguated sense of the ambiguous word head.

A well-known

Out-of-context evaluation

In this section, we evaluate out-of-context word representations on a similarity prediction task and determine what kind of semantic relations are favored by our approach.

Similarity judgements prediction

In word similarity prediction tasks, pairs of words are presented to human subjects who are asked to rate the relatedness between those two words. These human similarity scores are then compared to distributional similarity scores induced by our models, by computing the correlation between them.

Methodology. We use the RG65 dataset, introduced by [START_REF] Rubenstein | Contextual correlates of synonymy[END_REF] and the WORDSIM353 dataset, collected by [START_REF] Finkelstein | Placing search in context: The concept revisited[END_REF]. These datasets comprise 65 and 353 word pairs respectively. Human subjects rated the relatedness of those word pairs. We use the Spearman's rank correlation coefficient ρ to compare human and distributional score distributions.

Comparison of similarity measures. Since words are represented by posterior distributions over latent semantic classes, we have considered distances (or divergences) that are adapted to probability distributions to compute the similarity between word representations: the symmetrised Kullback-Leibler divergence, the Jensen-Shannon divergence, and the Hellinger distance. We use the opposite of these dissimilarity measures in order to obtain similarity scores. We also included the cosine similarity measure as a baseline, as it is widely used in the field of distributional semantics. We report results on both datasets in Table 1. Unsurprisingly, we observe that the dissimilarity measures giving the best results are the one tailored for probability distribution, namely the Jensen-Shannon divergence and the Hellinger distance. The Kullback-Leibler divergence is too sensitive to fluctuations of small probabilities and thus does not perform as well as other similarity measures between probability distributions. In the following, we will use the Hellinger distance. It should be noted that the results reported by [START_REF] Agirre | A study on similarity and relatedness using distributional and wordnet-based approaches[END_REF] were obtained using a corpus containing 1.6 terawords, making it 1,000 times larger than ours. They also report results for various corpus sizes, and when using a corpus whose size is comparable to ours, their result on WORDSIM353 drops to 0.55. Relatedness v.s. similarity. As noted by [START_REF] Agirre | A study on similarity and relatedness using distributional and wordnet-based approaches[END_REF], words might be rated as related for different reasons since different kinds of semantic relations exist between word senses. Some words, such as telephone and communication might even be rated as related because they belong to the same semantic field. Thus, they proposed to split the WORDSIM353 dataset into two subsets: the first one comprising words that are similar, i.e., synonyms, antonyms and hyperonym-hyponym and the second cohyp hyper mero attri event randn randj randv 2 1 0 1 2 3 cohyp hyper mero attri event randn randj randv one comprising words that are related, i.e., meronym-holonym and topically related words. We report results on these two subsets in Table 1. We observe that our model capture similarity (ρ = 0.70) much better than relatedness (ρ = 0.34). This is not very surprising since our model takes the syntax into account.

Semantic relations captured by our word representations

As we saw in the previous section, different semantic relations between words are not equally captured by our word representations. In this section, we thus investigate which kind of semantic relations are favored by our approach.

The BLESS dataset. The BLESS dataset [START_REF] Baroni | How we blessed distributional semantic evaluation[END_REF] comprises 200 concrete concepts and eight relations. For each pair of concept-relation, a list of related words, referred to as relatum, is given. Five semantic relations are considered: co-hyponymy, hypernymy, meronymy, attribute and event.

The attribute relation means that the relatum is an adjective expressing an attribute of the concept, while the event relation means that the relatum is a verb designing an activity or an event in which the concept is involved. The dataset also contains three random relations (randn, randj ans randv), obtained by the association of a random relatum, for different POS: noun, adjective and verb.

Methodology. We follow the evaluation proposed by the authors: for each pair of concept-relation, we keep the score of the most similar relatum associated to that pair of concept-relation. Thus, for each concept, we have eight scores, one for each relation. We normalize these eight scores (mean: 0, std: 1), in order to reduce concept-specific effects. We then report the score distributions for each relation as box plots in Figure 3 (left).

Results. We observe that the co-hyponymy relation is the best captured relation by a large margin. It is followed by the hypernymy and meronymy relations. The random noun relation is prefered over the attribute and the event relations. This happens because words with different part-of-speeches tend to appear in different semantic classes. It is thus impossible to compare words with different parts-ofspeeches and thus to capture relation such as the event or the attribute relation as defined in the BLESS dataset. It is however possible to make a more principled use of the model to overcome this issue.

Comparing adjectives with nouns and nouns with verbs. In syntactic relations between nouns and adjectives, the noun is the head word and the adjective is the dependent. Similarly, in syntactic relations between nouns and verbs, most often the verb is the head and the noun is the dependent. Given a vector v a representing an adjective and a vector v n representing a noun, it is thus natural to left multiply them by the transition matrix of the model to obtain a vector u a comparable to nouns and a vector u n comparable to verbs:

u a = T ⊤ v a and u n = T ⊤ v n .
small house emphasise need scholar write book

c 2 c 1 w 2 w 1 c 1 c 2 w 1 w 2 c 2 c 1 c 3 w 2 w 1 w 3
Figure 4: Graphical models used to compute in-context word representations for the compositional tasks.

We report in Figure 3 (right) the new score distributions obtained when adjective and noun representations are transformed before being compared to nouns and verbs. We observe that, when using these transformations, the attribute and event relations are better captured than the random relations. This demonstrates that the transition matrix T captures selectional preferences.

Compositional semantics

So far, we have only evaluated how well our representations are able to capture the meaning of words taken as individual and independent units. However, natural languages are highly compositional, and it is reasonable to assume that the meaning of a sentence or a phrase can be deduced from the meanings of its parts and the syntactic relations between them. This assumption is known as the principle of semantic compositionality.

In this section, we thus evaluate our representations on semantic composition tasks. More precisely, we determine if using in-context word representations helps to compute the similarity between short phrases such as adjective-noun, verb-object, compound-noun or subject-verb-object phrases. We use two datasets of human similarity scores, introduced respectively by [START_REF] Mitchell | Composition in distributional models of semantics[END_REF] and [START_REF] Grefenstette | Experimental support for a categorical compositional distributional model of meaning[END_REF].

Methodology

We compare different ways to obtain a representation of a short phrase given our model. First, as a baseline, we represent a phrase by the out-of-context representation of its head word. In that case, there is no composition at all. Second, following [START_REF] Mitchell | Vector-based models of semantic composition[END_REF], we represent a phrase by the sum of the out-of-context representations of the words forming that phrase. Third, we represent a phrase by the in-context representation of its head word. Finally, we represent a phrase by the sum of the two in-context representations of the words forming that phrase. The graphical models used to compute incontext word representations are represented in Fig 4 . The probability distribution p(c 1 ) of the head's semantic class is set to the uniform distribution (and not to the initial class distribution p T (c k | c 0 = 0)).

Datasets

The first dataset we consider was introduced by [START_REF] Mitchell | Composition in distributional models of semantics[END_REF], and is composed of pairs of adjective-noun, compound-noun and verb-object phrases, whose similarities were evaluated by human subjects on a 1 -7 scale. We compare our results with the one reported by [START_REF] Mitchell | Composition in distributional models of semantics[END_REF]. The second dataset we consider was introduced by [START_REF] Grefenstette | Experimental support for a categorical compositional distributional model of meaning[END_REF]. Each example of this dataset consists in a triple of subject-verb-object, forming a small transitive sentence, and a landmark verb. Human subjects were asked to evaluate the similarity between the verb and its landmark in the context of the small sentence. Following [START_REF] Van De Cruys | A tensor-based factorization model of semantic compositionality[END_REF], we compare the contextualized verb with the non-contextualized landmark, meaning that the landmark is always represented by its out-ofcontext representation. We do so because it is believed to better capture the compositional ability of our model and it works better in practice. We compare our results with the one reported by Van

Discussion

Before discussing the results, it is interesting to note that our approach provides a way to evaluate the importance of disambiguation for compositional semantics. Indeed, the in-context representations proposed in this paper are a way to disambiguate their out-of-context equivalents. It was previously noted by [START_REF] Reddy | Dynamic and static prototype vectors for semantic composition[END_REF] that disambiguating the vectorial representations of words improve the performance on compositional tasks.

Mitchell and Lapata (2010) dataset. We report results on the [START_REF] Mitchell | Composition in distributional models of semantics[END_REF] dataset in Table 2 (left). Overall, in-context representations achieves better performance than out-of-context ones.

For the adjective-noun pairs and the verb-noun pairs, using only the in-context representation of the head word works almost as well (AN) or even better (VN) than adding the representations of the two words forming a pair. This means that for those particular tasks, disambiguation plays an important role. On the other hand, this is not the case for the noun-noun pairs. On that task, most improvement over the baseline comes from the add operation.

Grefenstette and Sadrzadeh (2011) dataset. We report results in Table 2 (right). First, we observe that in-context representations clearly outperform out-of-context ones. Second, we note that adding the subject, object and verb representations does not improve the result over only using the representation of the verb. These two conclusions are not really surprising since this task is mainly a disambiguation task, and disambiguation is achieved by using the in-context representations. We also note that our approach yields better results than those obtained by [START_REF] Van De Cruys | A tensor-based factorization model of semantic compositionality[END_REF], while their method was specifically designed to model subject-verb-object triples.

Conclusion and future work

In this article, we introduced a new approach to distributional semantics, based on a generative model of sentences. This model is somehow to latent Dirichlet allocation as structured vector space models are to latent semantic analysis. Indeed, our approach is based on a probabilistic model of sentences, which takes the syntax into account by using dependency trees. Similarly to LDA, our model can be viewed as a topic model, the main difference being that the topics are generated using a Markov process on a syntactic dependency tree instead of using a Dirichlet process. The approach we propose seems quite competitive with other distributional models of semantics. In particular, we match or outperform state-of-the-art methods on semantic compositionality tasks. Thanks to its probabilistic nature, it is very easy to derive word representations for various tasks: the same model can be used to compute in-context word representations for adjective-noun phrases, subject-verb-object triples or even full sentences, which is not the case of the tensor based approach proposed by [START_REF] Van De Cruys | A tensor-based factorization model of semantic compositionality[END_REF].

Currently, the model of sentences does not use the dependency labels, which is the most significant limitation that we would like to address in future work. We also plan to explore spectral methods [START_REF] Anandkumar | Tensor decompositions for learning latent variable models[END_REF] to provide better initialization for learning the parameters of the model. Indeed, we believe this could speed up learning and yields better results, since the expectation-maximization algorithm is quite sensitive to bad initialization. Finally, the code corresponding to this article will be available on the first author webpage.

Figure 2 :

 2 Figure2: Comparison of out-of-context (black) and in-context (red) word representations. The twodimensional visualization is obtained by using multidimensional scaling[START_REF] Borg | Modern multidimensional scaling: Theory and applications[END_REF]. See text for details.

Figure 3 :

 3 Figure3: Similarity score distributions for various semantic relations on the BLESS dataset, without using the transition matrix (left) and with using the transition matrix (right) for comparing adjectives and verbs with nouns.

Table 1 :

 1 Wall Street figure may join the Cabinet as head of the Treasury Department. Left: Spearman's rank correlation coefficient ρ between human and distributional similarity, on the RG65 and WORDSIM353 datasets. Right: Spearman's rank correlation coefficient ρ between human and distributional similarity on two subsets (similarity v.s. relatedness) of the WORDSIM353 dataset.

	Distance	RG65 WS353	Distance	SIM. REL.
	Cosine	0.68	0.50	Cosine	0.68 0.34
	Kullback-Leibler	0.69	0.47	Kullback-Leibler	0.64 0.31
	Jensen-Shannon	0.72	0.50	Jensen-Shannon	0.69 0.33
	Hellinger	0.73	0.51	Hellinger	0.70 0.34
	Agirre et al. (BoW)	0.81	0.65	Agirre et al. (BoW) 0.70 0.62

Table 2 :

 2 [START_REF] Van De Cruys | A tensor-based factorization model of semantic compositionality[END_REF]. Spearman's rank correlation coefficients between human similarity judgements and similarity computed by our models on the[START_REF] Mitchell | Composition in distributional models of semantics[END_REF] dataset (left) and on theGrefenstette and Sadrzadeh (2011) dataset (right). AN stands for adjective-noun, NN stands for compoundnoun and VN stands for verb-object.

		AN NN VN
	head (out-of-context)	0.44 0.26 0.41
	add (out-of-context)	0.50 0.45 0.42
	head (in-context)	0.49 0.42 0.43
	add (in-context)	0.51 0.46 0.41
	M&L (vector space model) 0.46 0.49 0.38
	Humans	0.52 0.49 0.55

We recall that the semantic classes corresponding to words are represented by integers between 1 and C.

Acknowledgments

Edouard Grave is supported by a grant from INRIA (Associated-team STATWEB). Francis Bach is partially supported by the European Research Council (SIERRA Project)


Edouard Grave
email: grave@berkeley.edu

Weakly supervised named entity classification

In this paper, we describe a new method for the problem of named entity classification for specialized or technical domains, using distant supervision. Our approach relies on a simple observation: in some specialized domains, named entities are almost unambiguous. Thus, given a seed list of names of entities, it is cheap and easy to obtain positive examples from unlabeled texts using a simple string match.

Those positive examples can then be used to train a named entity classifier, by using the PU learning paradigm, which is learning from positive and unlabeled examples. We introduce a new convex formulation to solve this problem, and apply our technique in order to extract named entities from financial reports corresponding to healthcare companies.

Introduction

We are interested in extracting named entities from specialized texts, such as financial reports. Most state-of-the-art approaches to named entity recognition are based on supervised machine learning. In the case of specialized or technical domains, these methods suffer from several limitations. First, they rely on labeled data, which are often scarce. Thus, for many specialized domains, practitioners face a lack of labeled data. Second, these methods suffer from domain shift. Even for extracting named entities belonging to general categories, such as person, organization or location, a NER system trained on news articles will make mistakes that could be easily avoided by using knowledge from the domain. For example, when extracting named entities from financial reports corresponding to healthcare companies, an open domain NER system systematically labels Henry Schein as a person and Aspen as a location, while both are healthcare companies.

On the other hand, obtaining a seed list of named entities that one wants to extract from a given specialized domain is usually cheap and easy. Moreover, we argue that for many domains, mentions of those entities are almost not ambiguous. Thus, using a simple string match between the seed list of named entities and unlabeled text from the specialized domain, it is easy to obtain positive examples of named entity mentions. Then, we propose to train a named entity classifier from those positive and unlabeled examples, a problem referred to as PU learning [START_REF] Liu | Partially supervised classification of text documents[END_REF][START_REF] Liu | Building text classifiers using positive and unlabeled examples[END_REF]. Our approach is also related to distant supervision, which has been successfully applied to relation extraction [START_REF] Craven | Constructing biological knowledge bases by extracting information from text sources[END_REF][START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF].

Contributions.

In this paper, we make the following contributions:

• We propose to frame the problem of learning to extract named entities using distant supervision as a PU learning problem (learning from positive and unlabeled examples only);

• We introduce a new method to solve this learning problem, based on a convex formulation;

• We apply our proposed method on a dataset of financial reports (10-Q) corresponding to healthcare companies, in order to automatically extract names of companies and drugs.

1

Related work

Learning to extract named entities from a small list of seeds and unlabeled texts has already been considered in the past. [START_REF] Riloff | Learning dictionaries for information extraction by multi-level bootstrapping[END_REF] introduced a method called mutual bootstrapping: given a small list of entities, a set of context in which those entities appear can be extracted from unlabeled text. In turn, this set of contextual rules can be used to extract new named entities. This procedure is then applied iteratively, in order to grow the sets of entities and rules. [START_REF] Collins | Unsupervised models for named entity classification[END_REF] proposed a closely related method, based on co-training, in which the two views of the data correspond to spelling rules and contextual rules. Similar kinds of techniques have been proposed to extract relations [START_REF] Brin | Extracting patterns and relations from the world wide web[END_REF][START_REF] Agichtein | Snowball: Extracting relations from large plain-text collections[END_REF]. One of the limitations of bootstrapping algorithms is semantic drift, which happens when labeling errors accumulate during the iterative learning process [START_REF] Curran | Minimising semantic drift with mutual exclusion bootstrapping[END_REF]. Finally, bootstrapping has been successfully applied to Web scale information extraction [START_REF] Etzioni | Unsupervised named-entity extraction from the web: An experimental study[END_REF][START_REF] Carlson | Toward an architecture for never-ending language learning[END_REF].

Another line of research strongly related to our approach is distant supervision for information extraction. Distant supervision refers to a set of methods that use a knowledge base, instead of labeled examples, to learn to extract information. Different knowledge bases have been proposed to learn to extract relations, such as the Yeast Protein Database [START_REF] Craven | Constructing biological knowledge bases by extracting information from text sources[END_REF], BibTex entries [START_REF] Bellare | Learning extractors from unlabeled text using relevant databases[END_REF], Wikipedia infoboxes [START_REF] Wu | Autonomously semantifying wikipedia[END_REF] or Freebase [START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF]. In the context of named entity recognition, Talukdar and Pereira ( 2010) proposed a graph-based semisupervised learning method, Ritter et al. ( 2011) introduced a technique based on LabeledLDA and Ritter et al. ( 2013) described a method based on an undirected graphical model.

The method described in this paper is strongly influenced by the framework of discriminative clustering [START_REF] Xu | Maximum margin clustering[END_REF]. The goal of discriminative clustering is to assign labels to points, such that learning a discriminative classifier using those labels would lead to low empirical risk. Different loss functions have been considered, such as the hinge loss [START_REF] Xu | Maximum margin clustering[END_REF], the squared loss [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF] or the logistic loss [START_REF] Joulin | Discriminative clustering for image co-segmentation[END_REF]. Discriminative clustering has recently been applied to weakly supervised face recognition (Bojanowski et al., 2013;[START_REF] Ramanathan | Linking people in videos with their names using coreference resolution[END_REF] and weakly supervised relation extraction [START_REF] Grave | A convex relaxation for weakly supervised relation extraction[END_REF].

Description of our approach

In this section we describe our approach to the problem of named entity classification using distant supervision. First, we extract named entity mentions, for example by extracting sequences of contiguous tokens with the part-of-speech NNP or NNPS1 . Second, we try to match each of these mentions to a named entity from our seed list, using an exact string match. Thus, we obtain a set of positive and unlabeled examples, from which we train a multiclass classifier. It must be noted that contrary to classical semi-supervised problems, in our case, the labeled set contains only positive examples and no negative examples. This problem is an instance of PU learning [START_REF] Liu | Building text classifiers using positive and unlabeled examples[END_REF]. In the following, we describe a new approach to learn a multi-class classifier from positive and unlabeled examples, inspired by discriminative clustering.

Notations

We start by setting up some notations. We suppose that we have N named entity mentions represented by the feature vectors (x n ) 1≤n≤N . Let P be the set of indices of positive examples and U be the set of indices of unlabeled examples. For each positive example n ∈ P, we denote by the integer c n ∈ {1, ..., K} its corresponding label. The integer K + 1 will represent the class OTHER.

Our goal is to jointly infer a binary matrix Y ∈ {0, 1} N ×(K+1) , such that

Y nk = 1 if named entity mention n is of type k, 0 otherwise.
and a corresponding multiclass classifier f such that f (x n ) = y n , where y n is the nth line of the matrix Y. Of course, thanks to the distant supervision, we already know the part of the matrix Y corresponding to the positive examples. We will thus add constraints to impose the matrix Y to agree with the labels obtained using distant supervision.

Distant supervision by constraining Y

First, each named entity mention belongs to exactly one class, which means that each line of the matrix Y contains exactly one 1. This is equivalent to the linear constraints:

∀n ∈ {1, ..., N }, K+1 k=1 Y nk = 1.
Second, for all the positive examples, we impose the matrix Y to agree with the labels obtained through distant supervision: ∀n ∈ P, Y ncn = 1. These constraints can be relaxed, by enforcing only a certain percentage or number of positive examples to be classified according to the labels obtained using distant supervision. This new kind of constraint is related to the at-least-one constraint described by [START_REF] Riedel | Modeling relations and their mentions without labeled text[END_REF]. In our convex modeling framework, it can be formulated as follow:

∀k ∈ {1, ..., K}, n∈P k Y nk ≥ Z k ,
where P k represents the set of positive examples corresponding to class k. In particular, using this kind of constraints, our approach can leverage ambiguous named entities. We reserve to future work the application of our approach to ambiguous named entities.

Finally, we want the percentage of examples to be classified as OTHER to be at least p, in order to avoid semantic drift. This is equivalent to imposing the linear constraint:

n∈U Y n(K+1) ≥ pN.
The set of matrices Y verifying those constraints is denoted by Y. It should also be noted that all those constraints are linear, thus defining a convex set.

Problem formulation and convex relaxation

Inspired by the discriminative clustering framework, introduced by [START_REF] Xu | Maximum margin clustering[END_REF], we jointly learn the classifier f and the matrix Y by minimizing the cost function:

min Y,f N n=1 ℓ (y n , f (x n )) + Ω(f ) s.t. Y ∈ {0, 1} N ×(K+1) , Y ∈ Y,
where ℓ is a multiclass loss function, Ω is a regularizer and Y is the set defined by the constraints introduced in section 2.2. Following [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF], we use linear classifiers W ∈ R d×(K+1) , the squared loss and the ℓ 2 norm regularizer, and thus obtain the following cost function:

min Y,W 1 2 Y -XW 2 F + λ 2 W 2 F s.t. Y ∈ {0, 1} N ×(K+1) , Y ∈ Y.
We can then relax the constraint K+1) , in order to obtain the problem

Y ∈ {0, 1} N ×(K+1) into Y ∈ [0, 1] N ×(
min Y,W 1 2 Y -XW 2 F + λ 2 W 2 F s.t. Y ∈ [0, 1] N ×(K+1) , Y ∈ Y,
which is jointly convex in Y and W. Following Grave (2014), we solve the dual problem using the accelerated projected gradient descent algorithm [START_REF] Nesterov | Gradient methods for minimizing composite objective function[END_REF][START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF].

DRUGS ALL P R F1 P R F1 P R F1 Stanford NER N/A 52.6 N/A N/A N/A N/A N/A N/A N/

Experiments

In this section, we describe the application of our method to the extraction of the named entities from financial reports corresponding to healthcare companies. In particular, we are interested in extracting mentions of companies and drugs from those reports.

Data

Our dataset consists of quarterly financial reports (form 10-Q), filed by publicly traded healthcare companies, corresponding to the years 2013 and 2014. Our dataset contains 2, 588 reports, corresponding to 578 companies. We use the names of those 578 companies as the seed list for companies and the list of the 200 most searched drugs on the website http://www.rxlist.com as the seed list for drugs. We tagged and parsed this dataset using the Stanford part-of-speech tagger [START_REF] Toutanova | Feature-rich part-of-speech tagging with a cyclic dependency network[END_REF] and the MaltParser [START_REF] Nivre | Maltparser: A language-independent system for data-driven dependency parsing[END_REF]. We manually labeled a set of 1, 659 named entity mentions corresponding to one 10-Q report, for evaluation. 405 of those named entity mentions are labeled as COMPANY and 251 are labeled as DRUG. Thus, 60% of named entity mentions correspond to the class OTHER. The long term goal of this project is to extract relations between companies, such as collaborations to develop new drugs.

Features

Each named entity mention is represented by the following features: the (lowercased) tokens that form the mention, a window of k words to the left and a window of k words to the right of the mention and the k ancestors, with their syntactic roles, of the mention in the dependency tree, for k ∈ {1, 2, 3}. Finally, we obtain a vectorial representation of each named entity mention by using the distributional model of semantics introduced by [START_REF] Grave | A markovian approach to distributional semantics with application to semantic compositionality[END_REF]. We trained a model with 100 classes on the full dataset of financial reports corresponding to healthcare companies.

Baselines

Our first baseline is a string match between named entity mentions and our seed lists. The second baseline, which can only be evaluated on the extraction of company names, is the Stanford named entity recognizer [START_REF] Finkel | Incorporating non-local information into information extraction systems by gibbs sampling[END_REF], which was trained on the CoNLL and MUC datasets. Finally, we compare our method with a linear SVM with asymmetric costs for positive and unlabeled examples. This approach is very competitive, obtaining state-of-the-art results for text classification using PU learning [START_REF] Liu | Building text classifiers using positive and unlabeled examples[END_REF].

Results

We trained our classifiers on 10, 000 examples, 593 of which being positive and the rest being unlabeled. We report precision, recall and F1 measures for the different methods in Table 1. First, we observe that the string match baseline achieves a high precision of 99.2, as expected, while having a low recall. Second, we observe that the Stanford named entity recognizer has a low recall on companies, retrieving only half of their mentions. An example of error is labeling Merck as PERSON. Third, we observe that both PU learning approaches outperform the two baselines by a large margin: SVM and our approach achieve F1 scores of 87.2 and 89.5 respectively. In particular,

Table 1 :

 1 Results for different methods.

	A

Alternatively, we could also classify each token individually, a possibility we would like to explore in future work.

Acknowledgments

The author is supported by a grant from Inria (Associated team STATWEB) and would like to thank the anonymous reviewers for their helpful feedback.

our method outperforms SVM for extracting mentions of drugs, obtaining a F1 score of 90.6 while SVM have a F1 score of 82.7.

In Figure 1, we plot the precision, recall and F1 measures achieved by our method for different values of the parameter p, to illustrate its influence. We recall that the higher p, the more unlabeled examples are classified as negative. Unsurprisingly, we observe that when p increases, the precision increases while the recall drops. The parameter p thus allows to control the trade-off between precision and recall, and therefore to limit the semantic drift.

Discussion

In this paper, we introduced a novel method for weakly supervised named entity classification, based on discriminative clustering. We demonstrated that our approach seems competitive, on the task of extracting mentions of companies and drugs from financial reports corresponding to healthcare companies. As future work, we plan to evaluate our approach more extensively, on a larger number of classes and in other domains, such as biomedical articles. We would also like to explore the possibility of classifying all the tokens (instead of classifying only named entity mentions), in order to train a full named entity recognizer (and not only a named entity classifier). Finally, we also want to generalize this approach to ambiguous named entities, by relaxing the constraints that enforce the infered labels to be equal to the labels obtained using the seed list.