1 Introduction
Natural language inherently has ambiguity. There are many words in all languages that have two or more meanings. For example, palm is a noun in English, but depending on its context can mean surface of the hand or a type of tree. Clarifying this ambiguity and selecting the proper meaning based on the context is called Word Sense Disambiguation (WSD). Hence, many people are interested in automating WSD in machine translation process. In addition to machine translation, fields such as information retrieval, search engines technologies, speech processing and speech to text translations may also benefit from this technology. For instance, Hayat in Persian means life or yard with the same pronunciation but different spellings.
Word Sense Disambiguation based on supervised learning methods produce the best results for distinguishing sense of the word in public evaluation (Palmer et al. Reference Palmer, Fellbaum, Cotton, Delfs and Dang2001; Snyder and Palmer, Reference Snyder and Palmer2004; Pradhan et al. Reference Pradhan, Loper, Dligach and Palmer2007; Zhong and Ng Reference Zhong and Ng2010). Preprocessing and creating effective and efficient feature sets increase their prediction rate and accuracy. Some of the previous works, which are discussed in the related work section, took into account the ordered sequences of words in this context. However, to the best of our knowledge, this is the first work that shows the effectiveness of iterative patterns as a means for WSD algorithms. Iterative patterns are ordered sequences of words in the context that are not necessarily consecutive. Grammatical structure of most languages is based on rules that are iterative; therefore, considering the iterative patterns to correctly identify word senses is essential.
According to Markov assumptions (Jurafsky and Martin Reference Jurafsky and martin2008), which state that current word does not depend on the entire history of the words in the context but at most on the last few words, sequence of n words, which is a subset of sentence, is investigated to help WSD. The size of ‘n’ is very important in order to generate effective models. Unfortunately, no consensus exists on the value of ‘n’ for all WSD problems. Considering a large ‘n’ for n-grams means increasing the probability of getting the correct sense in WSD problems, but large n-grams may not occur in the training data. In contrast, as the size of ‘n’ in n-grams decreases, the total number of generated n-grams increases exponentially leading to more computational overhead and even lower results. So we tried to give a new framework to this problem by using a ‘variable length size n-gram’.
In this paper, our goal is to extend the definition of n-gram to a new structure by introducing iterative patterns. It means that related words are found dynamically irrespective of where they have occurred in the sentence. We use such patterns to evaluate the effectiveness of frequent pattern-based classification in WSD. The rest of the paper is structured as follows: In Section 2 the related work(s) are described. Section 3 presents the proposed method. Experimental results are presented in Section 4, and finally conclusions and future work wraps up the paper in Section 5.
2 Related work(s)
The first work in WSD was in the late 1940s (Weaver Reference Weaver, Locke and Booth1949). Researcher Bar-Hillel (Reference Bar-Hillel1960) knew that WSD was not a simple problem and has many challenges. During the 1970s the problem was attacked with artificial intelligence approaches aiming at language understanding (e.g. Wilks Reference Wilks and Keenan1975). Since the 1990s, many methods deployed statistics and artificial intelligence for WSD. In the area of artificial intelligence, researchers often use both supervised and unsupervised learning to distinguish the sense of a word.
In WSD, predicting the sense of a word can be seen as a classification problem. Supervised learning methods build a model based on a set of instances converted to feature vectors, called train set, and then the model can predict the meaning of the other unlabeled set, called test sets. Different classifiers were applied to the WSD problem such as Decision Tree (Mooney Reference Mooney1996), Neural Networks (Cottrell Reference Cottrell1989; Tsatsaronis et al. Reference Tsatsaronis, Vazirgiannis and Androutsopoulos2007), Memory-Based (Hoste et al. Reference Hoste, Hendrickx, Daelemans and Van Den Bosch2002; Decadt et al. Reference Decadt, Hoste, Daelemans and Van Den Bosch2004) and Naive Bayes (Banea and Mihalcea Reference Banea and Mihalcea2011). Other works such as Lefever, Hoste and De Cock (Reference Lefever, Hoste and De Cock2011) used multiple classifiers which consider both English local context and a set of generated multilingual bag-of-words from the aligned translations as features and then builds five classifiers by incorporating English and five other languages. The key point in creating an effective model is taking into account influential features. Although many of the similar approaches considered n-grams or n-grams in combination with other features (Stevenson and Guo Reference Stevenson and Guo2010), considering the sequential order of words in the whole context was not addressed well. Similar approaches used non-contiguous n-grams but they were concerned with the proper size of the window as well as size of ‘n’. We believe considering the sequence in the whole context, and a variable length ‘n’ can be helpful for prediction.
The idea behind using unsupervised approaches in WSD is that many words closely similar to the meaning of each word exist. Word frequencies can be used to cluster, and clusters are used for labeling test data. The disadvantage of unsupervised methods is that they do not achieve accuracy levels of supervised methods. In Navigli (Reference Navigli2009) such methods are divided into three categories: context clustering (Ji Reference Ji2010), word clustering (Lin and Pantel Reference Lin and Pantel2002) and co-occurrence graphs (Veronis Reference Veronis2004; Agirre and Edmonds Reference Agirre and Edmonds2006). Graph-based WSD is usually performed on a graph made by senses (nodes) and relations (co-occurrence relations, lexico-semantic etc.) between nodes (edges). The disambiguation process is usually performed by applying a ranking algorithm over the graph and assigning a rank to each sense. These approaches usually have the cost of using additional knowledge, for instance Agirre and Soroa (Reference Agirre and Soroa2009) proposed a graph-based method that uses the knowledge in a lexical knowledge base (LKB; based on WordNet) to perform unsupervised WSD. In another approach, Navigli and Ponzetto (Reference Navigli and Ponzetto2012) proposed a graph-based approach that uses an immense multilingual lexical knowledge, called BabelNet (Navigli and Ponzetto Reference Navigli and Ponzetto2010), and used it for disambiguating in an arbitrary language. Acquiring the sense clue of a word from each language and joining these together can lead us to the target word meaning. Although graphs have a complete structure compared with sequences, the complexity of graphs is more and their efficiency is less in WSD (Veronis Reference Veronis2004; Agirre and Edmonds Reference Agirre and Edmonds2006).
Word Sense Disambiguation approaches, however, can be further classified as knowledge-based (or knowledge-rich) and corpus-based (or knowledge-poor) approaches (Navigli Reference Navigli2009). Knowledge-based approaches depend on the use of external lexical resources, such as dictionaries, ontologies, collocations etc. whereas corpus-based approaches does not make use of any other resource for disambiguation. They usually have lower performance than their supervised alternatives. Ponzetto and Navigli (Reference Ponzetto and Navigli2010) showed that injecting vast amount of knowledge into WordNet enables simple knowledge-based as well as the highest performing supervised WSD systems to perform. They prove that knowledge-rich disambiguation is a competitive alternative to supervised systems even when relying on a simple algorithm.
A famous feature extraction approach in WSD is based on the Markov model. Shannon (Reference Shannon1951) states that a language could be approximated by the nth order Markov model, where ‘n’ is extended to infinity. Lots of work have been done for calculating the size of ‘n’ in WSD problems (Brown et al. Reference Brown, Della Pietra, Pietra, Mercer and Lai1992; Iyer, Ostendorf and Meteer Reference Iyer, Ostendorf and Meteer1997; Chen, Beeferman and Rosenfeld Reference Chen, Beeferman and Rosenfeld1998). Marti and Bunke (Reference Marti and Bunke2001) concluded that using a large size for ‘n’ makes the model more powerful after testing different sizes for ‘n’. Jason and Lethal (Reference Jason and Lethal2008) investigated that using a combination of lower order n-grams instead of generating a higher order model of n-gram improves WSD for Punjabi language.
In this study we tried to present a general framework, SePaS, to the problem of investigating the size of ‘n’ in the Markov model by using a variable length window and variable sequence size. We use patterns as variable length sequences of words that are not necessarily consecutive. In other words, we believe that the size of ‘n’ must be decided based on iterative sequences presented in the context, and the variable length window must also be decided dynamically. That is, two words may have a very distinctive characteristic to identify the correct WSD, but may have a low frequency in sentences. In comparison, four or more words with higher frequency may do the same. Thus, the number of words to be considered in each case must be dynamic. Moreover, each sentence length may vary considerably from one to the other.
3 Proposed method
In general, supervised learning methods achieved better results compared with unsupervised approaches (Navigli Reference Navigli2009). The main point in supervised methods is selecting proper features. Most of the related work(s), which were described in the previous section, considered features such as single words or n-grams or combinations with n-grams. In order to build a powerful model, in addition to single words, we also considered dependencies and word order. Without considering the order, ‘buildings of computer department are old’ can be changed to ‘department are computer of old building’, which is not the same. Therefore, a greater semantics must exist in the word order. Although n-grams consider the word order, they only consider close sequential proximity. We believe that contiguous sequence of ‘n’ items from a given context like n-gram is not highly important. In contrast, sequences of words that are not consecutive may be more effective than considering only a close proximity or contiguity of words. To address this proximity limitation, we use frequent iterative patterns because they consider sequential order of the words in the whole context and not just in close proximity.
Previous studies (Cheng et al. Reference Cheng, Yan, Han and Hsu2007) show the effectiveness of frequent pattern-based classification, where frequent patterns are used as features for improving the classification step. Follow the following definitions:
Definition 1. Itemset : Let Γ = {I 1, I 2, . . ., Im} be a set of items. A subset of Γ is called an itemset. An itemset that contains k items is a k-itemset. The occurrence frequency of an itemset is the number of transactions that contain the itemset. This is also simply known as the frequency of the itemset. Let D be a set of database transactions, D = {T 1, T 2, . . ., Tm}, where each transaction Ti is a non-empty itemset such that T⊑Γ.
Definition 2. Frequent Itemset : An itemset T is frequent for a transaction dataset D if 
$\frac{|D_T|}{|D|}$ ≥ α, where DT is any dataset transaction containing T. $\frac{|D_T|}{|D|}$is called the support of T in D, written s(T) and α is the minimum support threshold 0 ≤ α ≤ 1.
A challenging step toward mining frequent itemsets from a large dataset, using a low support, is that such mining often leads to generating a large number of itemsets. This is because if an itemset is frequent, each of its subsets is also frequent. To overcome this difficulty, the concept of closed frequent itemset was introduced.
Definition 3. Closed Frequent Itemset : An itemset T is closed in a dataset D if there exists no super-itemset Γ such that Γ has the same support count as X in D. An itemset T is a closed frequent itemset in set D if T is both closed and frequent in D.
For example if {A, B} is an itemset that has support = 5 and all of its supersets have support < 5, then {A, B} is a closed itemset. In contrast, if {A, B, C} is an itemset that has support = 5, then {A, B} is not a closed itemset anymore.
Although there are many algorithms (Agrawal and Srikant Reference Agrawal and Srikant1994; Han et al. Reference Han, Pei, Yin and Mao2004) for finding frequent itemsets, they do not consider the temporal order of elements in the sequence. Nature of sentence is sequential and considering the order helps create influential patterns. One of the most effective algorithms in the area of sequence mining is iterative patterns (Lo and Khoo Reference Lo and Khoo2007), which consider closed unique repetitive patterns. This algorithm has shown promising results in the fields such as software fault detection (Lo et al. Reference Lo, Cheng, Han, Khoo and Sun2009) and dynamic malware detection (Ahmadi et al. Reference Ahmadi, Sami, Rahimi and Yadegari2013). In this paper, application of this concept in WSD is presented. In order to understand the closed unique iterative characteristic of such patterns, consider the following definitions:
Definition 4. Iterative Pattern Instance : Given a pattern P(e1, e2, . . ., en), a consecutive series of words SB = (sb1, sb2, . . ., sbn) in a sentence (word sequence) S in WSD database (WSDDB) is an instance of P iff it is of the following quantified regular expression (QRE):
\begin{equation}
e_1;[-e_1,\ldots,e_n]*e_2;\ldots;[-e_1,\ldots,e_n]*;e_n
\end{equation}
QRE resembles the standard regular expression with ‘;’ as the concatenation operator, ‘[−]’ as the exclusion operator (e.g. [− P, S] means any word except P and S), and ‘*’ as the standard Kleene star.
The minimum size of patterns is one single word and the maximum size is the whole context. Any ordered combination of the words in the context can be a pattern. For example, consider the following sentences which were extracted from ‘bass.n’[corpus in a two-way ambiguities (TWA) dataset:
Sentence #1 :
Charlie no longer played rhythm guitar but stood clutching a mike stand at the edge of the stage, howling at the kids, who pogoed like road drills beside me, Eva gasped and covered her face. Then Charlie was smearing blood over his face and wiping it over the <head> bass </head> guitarist.
Sentence #2 :
Tommy is still obviously the leader and driving force, very much in the Art Blakeymould, and once again he’s selected a group of talented young players. For this tour the final line-up had Dave Lewis on Saxes, Les Miller double <head> bass </head>, and guitarist Chris Watson who replaced the previously announced Hammond organist.
After the stemming step, two words ‘played’ and ‘players’ become equal to a single word ‘play’. Then we look for instances of the defined pattern. As you can see in the contexts, two instances satisfy the QRE for pattern < play, bass, guitarist > which is of size 3. We highlight the instances in both contexts and show them in a set of triples. For example, in the previous samples, assuming that we do not count hypertext mark-up language (HTML) tags, the set of instances is
\begin{equation}
< 1, 4, 50 >, < 2, 27, 44 >
\end{equation}
For each triple, the first number is the sequence ID, the second is the start index and the third is the end index.
Definition 5. Frequent Iterative Pattern : An iterative pattern P is frequent if its instances occur above a certain threshold of a minimum support in WSDDB (which stands for the corpuses of WSD).
For very long contexts there are a large number of patterns. We only consider the closed and unique patterns.
Definition 6. Closed Iterative Pattern : A frequent iterative pattern P is closed if there exists no super sequence Q such that:
(1) P and Q have the same support.
(2) Every instance of P corresponds to a unique instance of Q, denoted as Inst(P) ≈ Inst(Q).
An instance of P (seqP; startP; endP) corresponds to an instance of Q(seqQ; startQ; endQ) iff seqP = seqQ and startP ≥ startQ and endP ≤ endQ. Where ‘seq’ means each record in WSDD.
However, even by using closed patterns, we may still generate a large number of iterative patterns. Consider the following transactions:
\begin{eqnarray*}
S1 = \{B, C, B, B, C, B, B, C\}\\
S2 = \{B, B, B, C, B, B, B, C\}
\end{eqnarray*}
Using minimum absolute support = 2, patterns like {B, C}, {B, B, C} and {B, B, B, C} will be extracted. These patterns have different support values and hence if we mine closed patterns, all three will be extracted. If the sentences are reasonably long and the word B appears very often, the pattern set is likely to explode. To avoid this problem, we mine a compact set of closed patterns that are composed of unique words.
Definition 7. Closed Unique Pattern : A frequent pattern P is a closed unique pattern if P contains no repeated constituent words, and there exists no super-sequence Q such that:
(1) P and Q have the same support.
(2) Every instance of P corresponds to a unique instance of Q.
(3) Qcontains no constituent words that repeat.
Consider a database with two sequences:
\begin{eqnarray*}
S1 = \{A, B, A, B, B, C, E, D, A, B, B\} \\
S2 = \{C, E, D, A, B, B, B, B, B\}
\end{eqnarray*}
Assuming minimum support = 2, the pattern {A, B} is a closed unique pattern. It contains unique words A and B, and there is no longer unique pattern having the same support as {A, B}. Consider another pattern {C, D} which is unique. This pattern is not closed, as there exists a longer pattern {C, E, D} which is also unique and the two patterns have corresponding instances. In the experiments, the set of closed unique patterns is much less than the set of closed patterns, and it is more efficient to mine closed unique patterns. So in addition to single words, we also consider closed unique patterns as features. Because grammatical structure of all languages is rule-based, such features can help to improve the classification step by considering the word’s order in the whole corpus.
Proper selection of support value is a challenging problem in SePaS deployment. Very small supports produce too many features that may lead to over-fitting, which reduces the applicability of the algorithm. On the other hand, large supports may cause missing of so many discriminative features. The proper methodology to select proper support value based on each problem is not addressed in this paper. However, the best obtained results are illustrated. This type of contradiction has been addressed extensively in quantitative association rule mining (Srikant and Agrawal Reference Srikant and Agrawal1996) as the selection of proper size of discrimination for maximizing support and confident at the same time.
An overview of the method is shown in Figure 1.
System overview.
The method is outlined in the following steps:
(1) Preprocessing of the corpus
(2) Looking for frequent sequential patterns in corpus
(3) Using single words and patterns as features
(4) Feature selection and classification
3.1 Preprocessing
Preprocessing plays an important role in the quality of evaluation process. In most practical applications, it takes more than 60 percent of the process. Preprocessing is considered an important step because there are many meaningless words with little information. In this work, we first omit insignificant words, such as stop words,Footnote 1 prepositions etc., from every context. Then we use stemming, which pertains to finding the origin of the words and removing prefixes and postfixes. This means, forms like adjectives, nouns and verbs are converted to homological-like words. For instance, both ‘travelling’ and ‘traveled’ are converted to the same word, ‘travel’. Stemming assures that the two sequences, ‘going to drive’ and ‘goes to driving’ are seen as a single sequence ‘go drive’. The Porter stemmer (Porter Reference Porter1980) as a popular open-source application for stemming was used.
3.2 Feature selection
Feature selection is the procedure of choosing a subset of features happening in the training set. This subset contains more discriminative features that can help improve the accuracy in classification. CfsSubsetEval algorithm (Hall Reference Hall1998) was used for feature selection. CFS is a filtering algorithm that ranks feature subsets according to a correlation-based heuristic evaluation function. The evaluation bias is toward subsets that contain features that are highly correlated with the class and uncorrelated with each other. Irrelevant features should be ignored because they will have low correlation with one or more of the remaining features. The acceptance of a feature depends on the extent to which it predicts classes in areas of instance space not already predicted by other features,
\begin{equation}
M_S=\frac{k\overline{r_c{}_f}}{\sqrt{k+k(k-1)\overline{r_f{}_f}}}
\end{equation}
where MS is the heuristic ‘merit’ of a feature subset S containing k features, 
$\overline{r_c{}_f}$ is the mean feature-class correlation (f ∈ S) and 
$\overline{r_f{}_f}$ is the average feature–feature inter-correlation. The numerator of (1) can be thought of as providing an indication about the predictiveness of the set of features of the class; and the denominator providing an indication about redundancy in the set of features. Equation forms the core of CFS and imposes a ranking on feature subsets in the search space of all possible feature subsets. The algorithm is implemented in Waikato Environment for Knowledge Analysis (WEKA)Footnote 2 platform (Hall et al. Reference Hall, Frank, Holmes, Pfahringer, Reutemann and Witten2009).
3.3 Classification
Classification is a data analysis technique that extracts models describing important data classes. Such models, called classifiers, predict categorical class labels. For example, suppose a translator wants to find the proper meaning of the word ‘palm’ in the following context extracted from ‘palm.n’ corpus in a TWA dataset:
The fats found in your food Saturated Watch out! These are the greatest danger so avoid them: palm kernel oil.
Here a model or classifier must be constructed to predict class (categorical) labels, such as ‘hand’ or ‘tree’. Data classification is a two-step process. In the first step, a classification algorithm builds the classifier by analyzing or ‘learning from’ a training set made up of database tuples and their associated class labels. In the second step, the model is used for classification. A different set, called the test set, is used to evaluate the correctness of the built model. Test data are independent of the training data, meaning that they were not used to construct the model. For the first two experiments, we used WEKA’s ten-fold cross validation on the train dataset of the corpus, where the train dataset is divided into ten sub-samples with the same number of instances. Each time, nine of them are used as train data and the remainder is used for testing.
The main matter in classification to improve accuracy is removing irrelevant data and creating influential features. After stemming and finding iterative patterns, we consider both single words and closed unique patterns as features of the dataset. We use frequency for the value of each word and support for the value of the patterns and build a feature vector for each sample. To tune the support of iterative patterns, we examined accuracies with relative supports of between 0.06 to 0.01 for each category and selected the support with the highest accuracy. For the classification step, Random Forest and SVM were applied. First experiments were done using Weka’s ten-fold cross validation.
4 Experimental results
This section presents various evaluations of SePaS. For these experiments, we used different benchmark datasets, namely TWA, SemEval-2007 English lexical-sample, SenseEval3 English lexical-sample and SemEval-2007 Word Sense Induction. The first two datasets contain many contexts, which are manually labeled based on the real sense of the ambiguous word. In the incoming sections, each section describes experiments performed on a specific dataset.
4.1 Two-way ambiguities dataset
First dataset, called TWAFootnote 3 dataset, has six categories. These categories are actually ambiguous words with two meanings, e.g. bass, crane, motion, palm, plant and tank. These contexts were originally extracted from British National Corpus with nearly one hundred to 200 instances for each ambiguous word. TWA on SePaS was evaluated based on accuracy and Root Mean Square Error (RMSE), which is a quadratic scoring rule that measures the average magnitude of the error.
Comparison of results on TWA dataset with two previous works (Ji Reference Ji2010; Banea and Mihalcea Reference Banea and Mihalcea2011) is presented in Table 1. Ji (Reference Ji2010) proposed an unsupervised method for WSD. They clustered contexts, instead of words, and considered more knowledge regarding relationship between words by applying Google n-gram (n = 5) corpus Version II,Footnote 4 other than only WordNet (Fellbaum Reference Fellbaum1998) relatedness measure for contexts. This method used extra knowledge that is not presented in the monolingual dataset. They used the consequent clusters. Clustering 1.2 billion 5-grams is also a time-consuming task. Banea and Mihalcea (Reference Banea and Mihalcea2011) showed that creating features based on a multilingual translation can improve the performance of the WSD system by a significant margin as compared with other systems that use only monolingual features. They used all the translations of text in German, French and Spanish, in addition to English text. The permutation of these four languages was used to build fifteen new cases, four of which are monolingual, six are bilingual, four trilingual and one four-lingual. The average accuracy of the classifier on each group was considered based on binary features representing each word. The results are shown in Table 1. The Most Common Sense (MCS) column shows the accuracies achieved from the MCS method (Banea and Mihalcea Reference Banea and Mihalcea2011). MCS used WEKA’s ZeroR algorithm. Mono is the result obtained by applying multi-nominal Naive Bayes classifier on monolingual features, where the features are individual English words, and the existence of a word in the context is shown with a binary value as the weight (Banea and Mihalcea Reference Banea and Mihalcea2011). Multi is the maximum of accuracies, obtained by applying multi-nominal Naive Bayes classifier on different combinations of English and three other languages (Banea and Mihalcea Reference Banea and Mihalcea2011). Ji (Reference Ji2010) applied unsupervised learners and web-scale phrases for clustering TWA, which are shown in WSC. Although some accuracies of this method are better than multilingual classification, overall average is lower (Table 1). COL shows the results obtained by applying SVM classifier on collocation features. Collocations, which are formally described in Section 4.5, are similar to iterative patterns, but they are not ordered. We used a minimum support of 0.03 for extracting collocations which showed the best performance as described in Section 4.5.
Achieved accuracies on the TWA dataset
*Number of instances
The acquired accuracies and RMSE of SePaS are shown in the last three columns by SP_RF using Random Forest and SP_SVM by applying SVM respectively. RMSE shows the error obtained from SVM. As Table 1 indicates, in addition to improving monolingual classification results with significant margin, our proposed method also improves multilingual classifications, even though we are not using the information that the multilingual has used. On average, SePaS based on Random Forest classification improved the accuracy by 4.27 percent higher than multilingual classifiers. We want to emphasize that SePaS uses only English translation of contexts. Both Banea and Mihalcea (Reference Banea and Mihalcea2011) and Ji (Reference Ji2010) considered a large amount of data for classification. As stated, SePaS uses only train dataset, i.e. less data, and achieves better results, so the results are statistically significant.
4.2 SemEval-2007 English lexical-sample dataset
The second standard dataset that was used for evaluation is SemEval-2007 English lexical-sample datasetFootnote 5 (Pradhan et al. Reference Pradhan, Loper, Dligach and Palmer2007), consisting of one hundred sections, including thirty-five nouns and sixty-five verbs. The samples for each word have been extracted from Brown Corpus, Penn Tree Bank and OntoNotes sense tags (Hovy et al. Reference Hovy, Marcus, Palmer, Ramshaw and Weischedel2006). The number of contexts in each section is considerably diverse for each ambiguous word. To make comparison, only thirty-one sections used in Banea and Mihalcea (Reference Banea and Mihalcea2011) were analyzed.
The analysis results are presented in Table 2. The MCS column shows the accuracies (Banea and Mihalcea Reference Banea and Mihalcea2011) achieved from the MCS method. Mono presents the results of multi-nominal Naive Bayes classifier on monolingual features (Banea and Mihalcea Reference Banea and Mihalcea2011). Multi presents the maximum of accuracies (Banea and Mihalcea Reference Banea and Mihalcea2011) based on the combinations of English and three other languages. COL shows the results of applying SVM classifier on collocation features with minimum support of 0.03, which provided the best result. Finally, accuracies and RMSE of SePaS are shown in the last three columns by SP_RF using Random Forest and SP_SVM by applying SVM respectively. RMSE shows the error obtained from SVM.
Achieved accuracies on the SemEval dataset
*Number of the senses
SePaS, a monolingual WSD, on average outperforms even multilingual WSD presented by Banea and Mihalcea (Reference Banea and Mihalcea2011). It is worth to note that generating multilingual dataset is a time-consuming task and requires extra knowledge that may not be present all the time. Since SePaS uses only English translation of the corpus, the difference of 0.34 is empirically significant. Figure 2 summarizes the obtained results of previous experiments. The left-hand side in the figure shows the average accuracies on TWA dataset and the right-hand side shows the average accuracies on SemEval dataset. The columns correspond to the columns in Tables 1 and 2. Although SePaS based on SVM achieved high results, in total and compared with multilingual classifier, SePaS based on Random Forest produces the highest results and outperforms the previous works.
Comparison among average accuracies of different methods and SePaS, the left on TWA dataset and the right on SemEval dataset.
4.3 SenseEval-3 lexical-sample dataset
SenseEval-3 lexical-sample taskFootnote 6 is used to compare results of SePaS and the state-of-the-art supervised method, IMS (Zhong and Ng Reference Zhong and Ng2010). In the preprocessing step, IMS uses WordNet to find the lemma form of each token. These use part-of-speech (POS) tags of surrounding words, surrounding words and local collocations as three different kinds of features. Then they apply classifiers such as SVM for prediction and achieve strong results.
As illustrated in Table 3, SePaS performs significantly better than MFS, but compared with IMS it shows lower performance. Although IMS uses a complex preprocessing and also multiple knowledge-based features, the main reason lies in feature extraction. SePaS needs a perfect relative support to perform well. Lower supports cause generating features that appear rarely, which decrease the classification accuracy due to ‘overfitting’ issue – features are not representatives. They also cause extracting many features, thus slowing down the model learning process, and even worse the classification accuracy deteriorates (another kind of ‘overfitting’ issue – features are too many). On the other hand, a high support results in extracting a subset of discriminating features. Although the problem with low supports is handled using feature selection, finding the perfect support is not addressed. The perfect support depends on the size of the corpus. Tasks such as SensEval include various categories, each of which having a different size, so applying a general support to the whole corpus yields decrease in the total performance of the system. For this comparison, the best results were obtained from relative support of 0.03 using SVM, but as mentioned, applying this support to the whole task decreases the performance.
WSD accuracies on SenseEval3 lexical-sample task
4.4 Comparison with n-grams
n-gramsFootnote 7 are a general approach for feature extraction in WSD. As mentioned, these approaches are investigated after Markov assumptions. However, they have the drawback of finding the proper size of ‘n’. Iterative patterns is a similar approach which uses variable ‘n’ and a variable size window, hence can be a general n-gram approach. To have a comparison, we performed additional experiments on SemEval-2007 English lexical-sample dataset. For each category, 2-grams, 3-grams, 4-grams and iterative patterns are extracted. We did not include single words in the feature vector. To evaluate the performance, we performed ten-fold cross validation on the train dataset. The results are shown in Table 4. To select the classifier, different classifiers are applied such as Naive Bayes, SVM and Random Forest. SePaS based on Random Forest performed better as indicated in the first experiment. No feature selection was applied. The results retain the same pattern for most categories as discussed in the following, so we selected a portion of the results for comparison. We consider the relative support of 0.02 for both iterative patterns and n-grams, which also improved the results of n-grams. In Table 4, columns 2 to 7 show the accuracy of n-grams and columns 8 and 9 show the results of iterative patterns.
Comparison between n-gram features and iterative patterns
*Root mean squared error
†Iterative patterns
As Table 4 shows, usually lower n-grams have a higher accuracy, but in some cases the higher n-grams have a better accuracy (e.g. ‘job.n’). Because we need the highest accuracy, we must evaluate many higher n-grams and not just lower n-grams. In other words, the proper size of ‘n’ must be determined according to the context. The results of iterative patterns are the same or even better than the results of the best n-grams. This pattern of results was the same among most of the categories that we evaluated. It is obvious from the results that the iterative patterns can be a general n-gram approach which does not need a predefined size. There is no statistical difference between the results because as we have indicated before, iterative patterns are a general n-gram solution where the best size for ‘n’ in terms of performance is chosen.
4.5 Comparison with collocations
A collocation is an arrangement or juxtaposition of two or more words or other elements, especially those that co-occur commonly. Collocations and iterative patterns are almost similar but are different from aspects of size and order. The length of collocations must be defined whereas iterative patterns can have various lengths based on their frequency, and opposite to iterative patterns collocations are not ordered. Two sets of experiments for comparison of collocations and iterative patterns are performed.
The first experiment was performed on the framework of SemEval-2007 WSI task (SWSI) (Agirre and Soroa, Reference Agirre and Soroa2007) under the second evaluation setting, i.e. supervised evaluation. The corpusFootnote 8 consists of texts of the Wall Street Journal corpus and is hand-tagged with OntoNotes senses. We focused on all thirty-five nouns and partitioned them according to train and test-separated in key files in the corpus.
After training the model using provided senses with SVM, we tagged instances of the test set and evaluated the performance with the official scoring software of the task. We used the standard measures of recall and precision in order to produce their harmonic mean (F-score). The results are compared with the state-of-the-art WSD system that used collocation, Hierarchical Random Graphs (HRG) (Klapaftis and Manandhar Reference Klapaftis and Manandhar2010). The HRG system presented a hierarchical grouping (binary tree) of the senses of ambiguous word using collocations of two words. The referred tree uses a graph in which the contexts of the polysemous word are represented as vertices and the contexts’ similarities are considered as edges. The similarity is based on the collocational and bag-of-word weights. The results are shown in Table 5. As indicated in the table, the HRG system achieved better result than SePaS in the current evaluation settings.
Comparison among SePaS and HRG-based system
The HRG system used an external corpus (British National Corpus) for finding the distribution of nouns in the contexts of the base corpus whereas SePaS used only frequency in the base corpus. The HRG also created graphs and extracted binary trees from them which has more computational complexity than manipulating the sequences used in our approach.
The second experiment is a comprehensive analysis on TWA dataset between iterative patterns and collocations. This comparison is performed to create more justifiable setting between iterative patterns and collocations. We considered only nouns in the context and extracted iterative patterns and collocations with different minimum relative supports. The evaluation results are presented from three different aspects: pattern extraction time, number of patterns and accuracy. As shown in Figure 3, by applying ten-fold cross validation using Random Forest, iterative patterns achieved higher accuracies compared with collocations. The trend between the number of generated patterns and the time of pattern extraction is shown in Figure 4. The best accuracy is obtained using a relative support of 0.04 and 0.03 for iterative patterns and collocations respectively. For these supports, Figure 4 shows that iterative patterns need less than a second for extraction, while collocations need 145.74 seconds. By using minimum supports of less than 0.02, iterative patterns take much more processing time for extraction, while collocations extraction takes almost the same amount of time. On the other hand, for lower supports, the number of extracted collocations increases substantially whereas iterative patterns do not increase very radically and stay almost the same. In conclusion, based on proper supports, by using iterative patterns more meaningful results can be obtained in lesser processing time.
Comparison among accuracy of iterative patterns and collocations using different supports.
Comparison of time(second) of pattern extraction and number of generated patterns between iterative patterns and collocations.
5 Conclusions and future work
This paper presents SePaS, a new approach toward word sense disambiguation based on iterative patterns. These patterns are sequences of words that are not necessarily consecutive, but the order of words in the context is preserved. We evaluated framework SePaS with different evaluations and achieved high accuracies compared with the current state-of-the-art WSD systems. Our method is also more efficient than many of the previous methods by considering less information to correctly classify the proper WSD. We compared iterative patterns with n-gram features and showed that iterative patterns can be a general solution to the problem of identifying the proper size of ‘n’ in n-gram approaches. We also made a comprehensive analysis between iterative patterns and collocations and showed that using the proper minimum supports, iterative patterns perform much better in terms of accuracy and time of pattern extraction. In conclusion, iterative patterns show promising results in various tasks of WSD and require more attention. In the future, we are interested in proposing solutions for finding the best relative support. We will also attempt to replace synonyms in the corpus that may lead to better patterns. For a better comparison with the HRG system, we are planning to propose an unsupervised system based on iterative patterns, so that the setting could become more justifiable. Another future work may consider multilingual iterative patterns for building a model. Other values except frequency or presence in the dataset may also improve the results.
Acknowledgments
We would like to appreciate Rada Mihalcea and Carmen Banea for their valuable comments. We would also like to thank anonymous reviewers for their useful comments.
