{'fraction_non_alphanumeric': 0.031226765799256505, 'fraction_numerical': 0.013605947955390335, 'mean_word_length': 4.479022403258655, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Naive Bayes Word Sense Induction

We introduce an extended naive Bayes model for word sense induction (WSI) and apply it to a WSI task. The extended model incorporates the idea the words closer to the target word are more relevant in predicting its sense. The proposed model is very simple yet effective when evaluated on SemEval-2010 WSI data.


Introduction
The task of word sense induction (WSI) is to find clusters of tokens of an ambiguous word in an unlabeled corpus that have the same sense. For instance, given a target word "crane," a good WSI system should find a cluster of tokens referring to avian cranes and another referring to mechanical cranes. We believe that neighboring words contain enough information that these clusters can be found from plain texts.
WSI is related to word sense disambiguation (WSD). In a WSD task, a system learns a sense classifier in a supervised manner from a sense-labeled corpus. The performance of the learned classifier is measured on some unseen data. WSD systems perform better than WSI systems, but building labeled data can be prohibitively expensive. In addition, WSD systems are not suitable for newly created words, new senses of existing words, or domainspecific words. On the other hand, WSI systems can learn new senses of words directly from texts because these programs do not rely on a predefined set of senses.
In Section 2 we describe relevant previous work. In Section 3 and 4 we introduce the naive Bayes model for WSI and inference schemes for the model. In Section 5 we evaluate the model on SemEval-2010 data. In Section 6 we conclude.
2 Related Work Yarowsky (1995) introduces a semi-supervised bootstrapping algorithm with two assumptions that rivals supervised algorithms: one-sense-percollocation and one-sense-per-discourse. But this algorithm cannot easily be scaled up because for any new ambiguous word humans need to pick a few seed words, which initialize the algorithm. In order to automate the semi-supervised system, Eisner and Karakos (2005) propose an unsupervised bootstrapping algorithm. Their system tries many different seeds for bootstrapping and chooses the "best" classifier at the end. Eisner and Karakos's algorithm is limited in that their system is designed for disambiguating words that have only 2 senses.
Bayesian WSI systems have been developed by several authors. Brody and Lapata (2009) apply Latent Dirichlet Allocation (LDA) (Blei et al., 2003) to WSI. They run a topic modeling algorithm on texts with some fixed number of topics that correspond to senses and induce a cluster by finding target words assigned to the same topic. Their system is evaluated on SemEval-2007 noun data (Agirre and Soroa, 2007). Lau et al. (2012) apply a nonparametric model, Hierarchical Dirichlet Processes (HDP), to SemEval-2010 data .

Model
Following Yarowsky (1995), we assume that a word in a document has one sense. Multiple occurrences of a word in a document refer to the same object or concept. The naive Bayes model is well suited for this one-sense-per-document assumption. Each document has one topic corresponding to the sense of the target word that needs disambiguation. Context words in a document are drawn from the conditional distribution of words given the sense. Context words are assumed to be independent from each other given the sense, which is far from being true yet effective.

Naive Bayes
The naive Bayes model assumes that every word in a document is generated independently from the conditional distribution of words given a sense, p(w|s). The mathematical definition of the naive Bayes model is as follows: where w is a vector of words in the document. With the model, a new document can be easily labeled using the following classifier: where s is the label of the new document. In contrast to LDA-like models, it is easy to construct the closed form classifier from the model. The parameters of the model, p(s) and p(w|s), can be learned by maximizing the probability of the corpus, where d is a vector of documents and d = w .

Distance Incorporated Naive Bayes
Intuitively, context words near a target word are more indicative of its sense than ones that are farther away. To account for this intuition, we propose a more sophisticated model that uses the distance between a context word and a target word. Before introducing the new model, we define a probability distribution, f (w|s), that incorporates distances as follows: where W is a set of types in the corpus. x is a tunable parameter that takes nonnegative real values. With the new probability distribution, the model and the classifier become: where f (w|s) replaces p(w|s). The naive Bayes model is a special case; set x = 0. The new model puts more weight on context words that are close to the target word. The distribution of words that are farther away approaches the uniform distribution. l(w) smoothes the distribution more as x becomes larger.

Inference
Given the generative model, we employ two inference algorithms to learn the sense distribution and word distributions given a sense. Expectation Maximization (EM) is a natural choice for the naive Bayes (Dempster et al., 1977). When initialized with random parameters, EM gets stuck at local maxima. To avoid local maxima, we use a Gibbs sampler for the plain naive Bayes to learn parameters that initialize EM.

Data
We evaluate the model on SemEval-2010 WSI task data . The task has 100 target words, 50 nouns and 50 verbs. For each target word, there are training and test documents.

Task
Participants induce clusters from the training data and use them to label the test data. Resources other than NLP tools for morphology and syntax such as lemmatizer, POS-tagger, and parser are not allowed. Tuning parameters and inducing clusters are only allowed during the training phase. After training, participants submit their sense-labeled test data to organizers. LDA models are not compatible with the scoring rules for the SemEval-2010 competition, and that is the work against which we most want to compare. These rules require that training be done strictly before the testing is done. Note however that LDA requires learning the mixture weights of topics for each individual document p(topic | document). These are, of course, learned during training. But the documents in the testing corpus have never been seen before, so clearly their topic mixture weights are not learned during training, and thus not learned at all. The way to overcome this is by training on both train and test documents, but this is exactly what SemEval-2010 forbids.

Implementation Details
The documents are tokenized and stemmed by Stanford tokenizer and stemmer. Stop words and punctuation in the training and test data are discarded. Words that occur at most 10 times are discarded from the training data. Context words within a window of 50 about a target word are used to construct a bag-of-words.
When a target word appears more than once in a document, the distance between that target word and a context word is ambiguous. We define this distance to be minimum distance between a context word and an instance of the target word. For example, the word "chip" appears 3 times. For · · · of memory chips . Currently , chips are produced by shining light through a mask to produce an image on the chip , much as · · · Example 1: an excerpt from "chip" test data a context word, e.g., "shining" there are three possible distances: 8 away from the first "chip," 4 away from the second "chip" and 11 away from the last "chip." We set the distance of "shining" from the target to 4.
We model each target word individually. We set α, a Dirichlet prior for senses, to 0.02 and β, a Dirichlet prior for contextual words, to 0.1 for the Gibbs sampler as in Brody and Lapata (2009). We initialize EM with parameters learned from the sampler. We run EM until the likehood changes less than 1%. We run the sampler 2000 iterations including 1000 iterations of burn-in: 10 samples at an interval of 100 are averaged. For comparison, we also evaluate EM with random initialization. All reported scores (described in Section 5.4) are averaged over ten different runs of the program. 1

Tuning Parameters
Two parameters, the number of senses and x of the function l(w), need to be determined before running the program. To find a good setting we do grid search on the trial data with the number of senses ranging from 2 to 5 and x ranging from 0 to 1.1 with an interval 0.1. Due to the small size of the training portion of the trial data, words that occur once are thrown out in the training portion. All the other parameters are as described in Section 5.3. We choose (4, 0.4), which achieves the highest supervised recall. See Table 2 for the performance of the model with various parameter settings. With a fixed value of x, a column is nearly unimodal in the number of senses and vice versa. x = 0 is not optimal and there is some noticeable difference between scores with optimal x and scores with x = 0.

Evaluation
We compare our system to other WSI systems and discuss two metrics for unsupervised evaluation (V-Measure, paired F-Score) and one metric for supervised evaluation (supervised recall). We refer to the true group of tokens as a gold class and to an induced group of tokens as a cluster. We refer to the model learned with the sampler and EM as NB, and to the model learned with EM only as NB0.

Short Descriptions of Other WSI
Systems Evaluated on SemEval-2010 The baseline assigns every instance of a target word with the most frequent sense (MFS). UoY runs a clustering algorithm on a graph with words as nodes and co-occurrences between words as edges (Korkontzelos and Manandhar, 2010). Hermit approximates co-occurrence space with Random Indexing and applies a hybrid of k-means and Hierarchical Agglomerate Clustering to co-occurrence space (Jurgens and Stevens, 2010). NMF lib factors a matrix using nonnegative matrix factorization and runs a clustering algorithm on test instances represented by factors (Van de Cruys et al., 2011).

V-Measure
V-Measure computes the quality of induced clusters as the harmonic mean of two values, homogeneity and completeness. Homogeneity measures whether instances of a cluster belong to a single gold class. Completeness measures whether instances of a gold class belong to a cluster. V-Measure is between 0 and 1; higher is better. See Table 3 for details of V-Measure evaluation (#cl is the number of induced clusters).
With respect to V-Measure, NB performs much better than NB0. This holds for paired F-Score and supervised recall evaluations. The sampler improves the log-likelihood of NB by 3.8% on average (4.8% on nouns and 2.9% on verbs). Pedersen (2010) points out that it is possible to increase the V-Measure of bad models by increasing

Paired F-Score
Paired F-Score is the harmonic mean of paired recall and paired precision. Paired recall is fraction of pairs belonging to the same gold class that belong to the same cluster. Paired precision is fraction of pairs belonging to the same cluster that belong to the same class. See Table 4 for details of paired F-Score evaluation.
As with V-Measure, it is possible to attain a high paired F-Score by producing only one cluster. The baseline, MFS, attains 100% paired recall, which together with the poor performance of WSI systems makes its paired F-Score difficult to beat. V-Measure and paired F-Score are meaningful when systems produce about the same numbers of clusters as the numbers of classes and attain high scores on these metrics.

Supervised Recall
For the supervised task, the test data is split into two groups: one for mapping clusters to classes and the other for standard WSD evaluation. 2 different split schemes (80% mapping, 20% evaluation and 60% mapping, 40% evaluation) are evaluated. 5 random splits are averaged for each split scheme. Mapping is induced automatically by the program provided by organizers. See Table 5   Overall our system performs better than other systems with respect to supervised recall. When a system has higher V-Measure and paired F-Score on nouns than another system, it achieves a higher supervised recall on nouns too. However, this behavior is not observed on verbs. For example, NB has higher V-Measure and paired F-Score on verbs than NMF lib but NB attains a lower supervised recall on verbs than NMF lib . It is difficult to see which verbs clusters are better than some other clusters.

Conclusion
Of the four SemEval-2010 evaluation metrics, and restricting ourselves to systems obeying the evaluation conditions for that competition, our new model achieves new best results on three. The exception is paired F-Score. As we note earlier, this metric tends to assign very high scores when every word receives only one sense, and our model is bested by the baseline system that does exactly that.
If we loosen possible comparison systems, the LDA/HDP model of Lau et al. (2012) achieves superior numbers to ours for the two supervised metrics, but at the expense of requiring LDA type processing on the test data, something that the SemEval organizers ruled out, presumably with the reasonable idea that such processing would not be feasible in the real world. More generally, their system assigns many senses (about 10) to each word, and thus nodoubt does poorly on the paired F-Score (they do not report results on V-Measure and paired F-Score).