We present here, TagMiner, a data mining approach for part-of-speech (POS) tagging, an important Natural language processing (NLP) classification task. It is a semi-supervised associative classification method for POS tagging. Existing methods for building POS taggers require extensive domain and linguistic knowledge and resources. Our method uses combination of a small POS tagged corpus and a raw untagged text data as training data to build the classifier model using association rules. Our tagger works well with very little training data also. The use of semi-supervised learning provides the advantage of not requiring a large high quality tagged corpus. These properties make it especially suitable for resource poor languages. Our experiments on various resource-rich, resource-moderate and resource-poor languages show good performance without using any language specific linguistic information. We note that inclusion of such features in our method may further improve the performance. Results also show that for smaller training data sizes our tagger performs better than state-of-the-art CRF tagger using same features as our tagger.
Part-of-speech (POS) tagging is an important NLP classification task that takes
a word or a sentence as input, assigns a POS tag or other lexical class marker
to a word or to each word in the sentence, and produces the tagged text as
output. For this task several rule based [
The creation of linguistic resources is a time consuming expensive process which requires expert linguistic knowledge. So, there is a need to develop semisupervised and generic POS tagging methods which take advantage of raw untagged corpus and require less or no lexical resources. A few such available techniques are mentioned in Sect. 2. In order to perform well, these techniques require a large raw untagged corpus. Unfortunately, for many resource poor languages, even obtaining this is hard.
This motivates us to explore data mining methods to build generic POS tagger. Data mining, being composed of data driven techniques, is a promising direction to explore or to develop language/domain independent POS tagging methods. However, direct application of data mining concepts for this task is not feasible and requires handling various challenges like 1) mapping POS tagging task to association rule mining problem, 2) developing semi-supervised methods to extract association rules from training set of tagged and raw untagged data combined and 3) handling challenges of POS tagging task (discussed in Sect. 4.2), like class imbalance, data sparsity and phrase boundary problems.
Associative classification [
Our method is generic in two aspects: (1) it does not use any language specific linguistic information such as morphological features and there is ample scope to improve further by including such features, (2) it does not require a large, high quality, tagged corpus and uses the POS tags of the tagged corpus only to calculate scores of “context based lists” which are used to form association rules. This can be easily adapted for various languages. Also, as an additional benefit model made by our tagger is human understandable since it is based on association rules.
Our algorithm has following advantages, especially suitable for resource poor languages, arising due to the use of raw untagged data: (1) it tags unknown words without using smoothing techniques, (2) the coverage of words present in the classifier model is increased which in turn increases tagging accuracy and (3) it creates additional linguistic resources from raw untagged data in the form of word clusters.
Remainder of this paper is as follows: Section 2 surveys related work. Section 3 formally presents the problem. Section 4, 5 and 6 present details of our proposed approach. Section 7 gives details of the datasets, various experiments and discusses the performance. Section 8 concludes our work. 2
Associative classifiers use association rules to build a classifier model. They
have been successfully applied for various classification tasks, for example, [
For POS tagging, one of the first semi-supervised methods was proposed
by [
To the best of our knowledge no semi-supervised tagging method has been employed for resource moderate Hindi and resource poor Telugu and Tamil languages. Also to the best of our knowledge no fully data mining based generic POS tagger exists for any language. Baseline POS taggers for various languages are discussed below. We note that all the reported accuracy values were obtained for very small sized test sets. All the mentioned POS taggers use linguistic (especially morphological) knowledge in some or the other form, while our approach uses only the POS tags of the tagged set in an indirect form and learns from the raw untagged data.
For Hindi language, [
For Bengali language, [
Automated POS tagging is a classification task which takes a word or a sentence as input, assigns a POS tag or other lexical class marker to a word or to each word in the sentence, and produces the tagged text as output. In semi-supervised paradigm the POS tagger is built from a corpus of untagged sentences and a set of tagged sentences. The POS tagging classification problem is formally defined as follows:
Given a set of tags = {T1, T2, . . . , Tn}, an annotated set of tagged sentences AS = {St1, St2, . . . StN }, where Sti = hW1/Ti, W2/Tj . . . Wn/Tki (where Wi is a word and Ti is a tag from ) and a raw untagged training corpus of sentences D = {S1, S2 . . . SM }, where Si = hW1W2 . . . Wmi, the goal is to build a classifier model which outputs the best tag sequence hT1T2 . . . Tli for an input sequence of words hW1W2 . . . Wli. 4 4.1
According to the one sense per collocation [
By experimenting with two varieties of bi-gram (one with preceding word and the other with succeeding word as context) and trigram as possible contexts we found that trigram works best for our method. For a word instance Wi, we fix its context as a trigram containing Wi in the middle and we use this context to find the context based list. Any other notion of context can be used as long as it fits into the formalism given below.
Context Based List: If is a function mapping from a word instance Wi in the data to its context (Wi), then 1( (Wi)) is a list of words instances sharing the same context. We refer to this list as context based list of (Wi). It denotes words of similar category or type as Wi in a specific context and can store multiple instances of a word. For a given trigram (Wi 1 Wi Wi+1) of words, (Wi) = (Wi 1, Wi+1). The preceding word Wi 1 and succeeding word Wi+1 are called context words and (Wi) is called the context word pair of Wi. Context Based Association Rule: For each context based list L, our approach finds association rule of the form L ) T . This rule maps the context based list L to a POS tag T with support and confidence parameters defined below. Since each list L is obtained from a unique context word pair, so each association rule uniquely associates a context to a POS tag and works as the context based tagging rule.
In the following definitions and formulas we develop the intuition and the method to compute the interestingness measures of the significant association rules. The complexity in defining support is due to the presence of raw untagged training data required for semi-supervised learning. The support is the frequency (count) of occurrences of the context in the dataset. Context based lists are made from raw untagged data D and we are interested in the words of this list for which we know the tag in annotated set AS. Hence, we define Support of a context as follows: AllTagContextSupport: Number of unique words of a context based list L whose tags are available (in annotated set AS) is denoted as AllT agContextSupport(L). This measure gives the number of tagged words of L.
ContextSupport: For a list of words L in which duplicates may be present, ContextSupport(L) is defined as the set of unique words present in L. Coverage: For a context based list L, (1) (2) Coverage(L) =
|ContextSupport(L)| This measure represents the confidence that enough number of tagged samples are present in L.
ContextTagSupport: Number of unique words of a context based list L present in annotated set AS with a particular tag T is denoted as ContextT agSupport(L, T ). Confidence: For a context based list L and tag T ,
Conf idence(L, T ) =
|ContextSupport(L)| This measure represents the confidence that considerable number of words in list L have a particular tag T and leads to rules of the form Context ) T ag. WordTagSupport: Frequency of tag T for a word W in the annotated set AS is denoted as W ordT agSupport(T, W ).
WordTagScore: For a word W and tag T , W ordT agScore is defined as: W ordT agScore(W, T ) =
max W ordT agSupport(Ti, W )
Ti2 This represents how good the tag fits the word on a scale of 0 to 1. ListTagScore: For a tag T in context based list L, ListT agScore is defined as: (3) (4) ListT agScore(L, T ) =
P Wi2 ContextSupport(L)
|{Wi 2 ContextSupport(L) : Wi/T 2 AS}|
Where, AS is the annotated set. This formula represents the average frequency
of tag T in context based list L. Intuitively, it represents how good the tag fits
the list. Unfortunately, this is not always indicative of the correct tag for the list.
For example, if a tag is overall very frequent, it can bias this score. Therefore, we
compare this with the following score, inspired by the notion of Conviction [
P Wi2 ContextSupport(AS) |{Wi 2 ContextSupport(AS) : Wi/T 2 AS}|
(5)
BackgroundT agScore(T ) = This represents the average frequency of tag T in annotated set AS. 4.2
POS tagging, especially for resource poor languages, involves three major
challenges listed below. In our approach we handle each of them explicitly.
1. Data sparsity problem: Some POS tag classes are present in the annotated
set with very few representations. This is not enough to derive statistical
information about them. In our approach, the use of raw untagged data
reduces this problem (shown in Sect. 7.4).
2. Class imbalance problem: POS tag classes are highly imbalanced in their
occurrence frequency. While selecting a tag this may lead to biasing towards
the most frequent tags. Existing solutions of class imbalance problem
typically favor rare classes [
Ti2 7. M axconf = Conf idence(L, Tmax) // Use Equation (2) 8. if M axconf > M inConf idence: 9. M axT set = {Ti | ContextT agSupport(L, Ti) == ContextT agSupport(L, Tmax)} 10. BestP ref T ag = F indBestP ref T ag(L, M axT set) 11. Return BestP ref T ag 12. else: Return NOTVALIST 13. else: Return NOTVALIST 22. 23. 24.
The first step in our classifier model building method is to compute context based lists from an untagged training corpus D. It may be noted that a context based list can store multiple instances of a word. We use a sliding window of size three to collect the context based lists from D, in a single iteration, taking care of sentence boundaries.
In the next step we use the algorithm shown in Fig. 1 to find association rules for all the context based lists. In this algorithm, BackgroundT agScore of all the POS tags present in the annotated set AS (lines 1-2) are computed first. Then for a context based list satisfying the threshold values of Coverage and Conf idence (lines 3-9), function F indBestP ref T ag (described in Sect. 5.2) finds the best preferred tag (lines 10-11, 14-24) from the set of tags with maximum ContextT agSupport (lines 7-9).
For a context based list L present as antecedent in association rule L ) T , tag T returned by this algorithm becomes the consequent. This algorithm outputs best preferred tags for all the context based lists and hence finds association rules for all of them.
We handle the class imbalance problem by using a novel Minmax approach in the function F indBestP ref T ag (lines 14-24 in Fig. 1) and parameters ListT agScore and BackgroundT agScore. In Minmax approach the preferred tag Ti for context based list L, is the one which has maximum ContextT agSupport(L, Ti) but minimum W ordT agSupport(Ti, W ) among those words of list L which have tag Ti as the best tag in AS. This takes care that the selected tag is supported by majority of the words in the list and is not biased by the most frequent tag of the annotated set.
To find the best preferred tag in function F indBestP ref T ag, from the set of all the tags with maximum ContextT agSupport value (line 9), at first we found those tags which were best tags (having maximum W ordT agSupport value) for the words of list L in AS (lines 15-20). Next, from this set of preferred tags we find the tag with minimum W ordT agSupport value (line 21). Then criteria
selected tag has above average support in the annotated set and the context based list, both. If none of the tags satisfy this criteria, then we tag the list as “NOTVALIST” (line 24). 5.3
To filter out context based lists with the phrase boundary problem (see Sect. 4.2) we use two suitable threshold values for parameters Confidence and Coverage. Coverage takes care of the fact that a context based list has considerable number of words to map it to a tag and Confidence ensures that the tag found for the list is the one which is supported by majority of the words in the list.
If context based list L has Coverage and Confidence values less than the corresponding threshold values M inCoverage and M inConf idence, we tag L as “NOTVALIST” (lines 3-8, 12, 13 in Fig. 1). If L satisfies both of the threshold values then only we find the set of all the tags which have maximum value of ContextT agSupport(L, Ti) and use this set (lines 9-10) to find the best preferred tag for the list (lines 14-24). 5.4
In the last step, we group context based lists according to their POS tags to get clusters of context based lists as classifier model. We exclude context based lists with tag “NOTVALIST” from the grouping process. Then we process these clusters to store word frequencies, corresponding context word pairs and their frequencies in each cluster. We represent the set of clusters as Clustset.
Since we are highly confident about the tags of the words present in the annotated set AS so, to improve cluster quality we apply a pruning strategy on the words of the clusters present in AS and remove those words from each cluster which do not have a matching cluster tag in AS. Finally, we get a set of clusters in which each cluster has a set of words with their frequencies and a set of associated context word pairs with their frequencies. Each cluster has a unique POS tag. These clusters are overlapping in nature and words can belong to multiple clusters. 6
To tag the words of a test sentence we make use of the test word’s context word pair, preceding word and the word frequency in a cluster to decide the tag of the word (see Fig. 2). When a test word is found in only one cluster then we output the cluster tag as the tag of the test word. But when a test word is found in many clusters, then to select the suitable clusters following priority order is followed: 1. Criteria 1: Highest priority is given to the presence of matching context word pair of the test word in the clusters. 2. Criteria 2: Second highest priority is given to the presence of matching preceding word of the test word as first word of the context word pairs in clusters. 3. Criteria 3: Last priority is given to the frequency of the test word in the clusters.
For test words not present in any cluster we use criterion 1 and 2 to select appropriate clusters. Based on the priority order, only one of the criterion is used to select the suitable clusters. If we are not able to find any suitable cluster then we return “NOTAG” as the tag of the test word.
Even when we find suitable clusters, to increase precision, our method finds POS tags only for those cases where it is confident. It avoids to wrongly classify non confident cases and returns “NOTAG” for them. This is especially useful when the cost of misclassifying (false positive) is high. This also gives opportunity to integrate other language/domain specific POS taggers as they can be used for the non-confident cases.
After selecting the suitable clusters we need to make sure that we have enough confidence in the highest probability tag obtained from the clusters. To ensure this we use the parameter TagProbDif, which gives the fractional di↵erence between the highest and the second highest cluster tag probabilities and is defined as follows:
T agP robDif =
Where, Cmax is the cluster with highest T agP rob(Ci) value and Csecmax is the cluster with second highest T agP rob(Ci) value. T agP rob(Ci) of a cluster is defined as follows:
T agP rob(Ci) =
Frequency of X in Ci
P Frequency of X in Cj 8 Cj2 Clustset (6) (7) Where, X is set as follows: If the test word is present in cluster Ci then X = test word. For test word not present in any cluster, if the clusters are selected based on the presence of the context word pair of the test word then X = context for each word W mid in sentence S with context word pair CWp and CWs do: 1. Initialize P redClustset = {} 2. if 9 cluster Ci 2 Clustset | W mid 2 Ci: (a) Find P Clustset = {Ci | W mid 2 Ci} (b) if 9 cluster Cj 2 P Clustset | CWp and CWs pair is present as context word pair in cluster Cj :
Find all such clusters from P Clustset and append to P redClustset #Criteria 1 (c) else: if 9 cluster Cj 2 P Clustset | CWp is present as preceding word in a context word pair in cluster Cj :
Find all such clusters from P Clustset and append to P redClustset #Crit. 2 else: Append P redClustset = P redClustset [ P Clustset #Criteria 3 3. else: (a) if 9 cluster Ci 2 Clustset | CWp and CWs pair is present as context word pair in cluster Ci:
Find all such clusters from Clustset and append to P redClustset #Criteria 1 (b) else: if 9 cluster Ci 2 Clustset | CWp is present as preceding word in a context word pair in cluster Ci:
Find all such clusters from Clustset and append to P redClustset #Crit. 2 else: Return NOTAG 4. 8 Ci 2 P redClustset Find T agP rob(Ci) // Use Equation 7 5. Find Cmax = cluster with highest T agP rob(Ci) value in P redClustset 6. Find Csecmax = cluster with second highest T agP rob(Cj ) value in P redClustset 7. Find T agP robDif // Use Equation 6 8. if T agP robDif M inprobdif : Return P redT ag = POS tag label of cluster Cmax 9. else: Return NOTAG word pair. If the clusters are selected based on the presence of the preceding word of the test word as first word of the context word pairs in clusters then X = preceding word of the test word. In this way we are able to tag some unseen/unknown words also which are not present in the training data. This, in a way, acts as an alternative of smoothing technique for them.
After selecting the clusters (based on priority order) we compute their T agP rob values using (7) and then compute T agP robDif using (6). For T agP robDif value above a suitable threshold value M inprobdif we output the tag of cluster with highest T agP rob value as the tag of the test word, otherwise we return “NOTAG”(see Fig. 2). 7 7.1
We have done our experiments on resource-rich English1(uses Biber tag set [
Govt. of India Reference No: 11(10)/2006-HCC(TDIL) 3 Available at http://sanskrit.jnu.ac.in/ilci/index.jsp gali4 languages. Table 1 gives details of all the language datasets. All the five language datasets have flat tag sets present in annotated training and test sets without any hierarchy and considerable number of lexical ambiguities are also present. We note that except English all the other four languages are morphologically rich and have free word-order property. The POS tag data distribution in the resource-moderate and resource-poor language datasets are highly imbalanced and sparse. We observed that following set of threshold values M inConf idence = 60%, M inCoverage = 60% and M inprobDif = 30% for the three parameters gives best AverageAcuracy (defined below) values for all the five languages. Tables 1 and 2 show the results for this set of parameter values.
Number of correctly tagged test words AverageAccuracy = (8) |Test set| No. of test words tagged as NOTAG Where, |Test set| = No. of words in the test set.
For both known and unknown test words, for all the five languages, maximum number of correct tagging was done by giving highest priority to presence of context word pair in the cluster. Here, known words means test set words which are present in untagged training set and unknown word means unseen test set words which are not present in the untagged training set. Note that words of annotated set are not included in the classifier model, only their tags 4 Available at http://sanskrit.jnu.ac.in/ilci/index.jsp are used indirectly while building the model. In the results shown in Table 1, around 46% unknown English words, 60% unknown Hindi words, 67% unknown Telugu words, 52% unknown Bengali words and 57% unknown Tamil words were correctly tagged using their context word pair. This shows the strength of our tagger to tag unknown words without using any smoothing technique used by other POS taggers.
In Table 2, we compare our results with a supervised CRF5 tagger [
We varied the size of annotated set of Tamil (see Table 3) while keeping the raw untagged set constant and observed that the coverage of words by the clusters in the classifier model increases with the increase in the size of annotated data, the tagging accuracy increases while the number of words missed by the model (tagged as “NOTAG”) decreases. For all languages we observed that increasing the annotated training data size improves cluster quality which increases the AverageAcuracy values but only up to a certain size. We also observed that there is only a slight decrease in AverageAcuracy value with decrease in annotated set size, so performance does not decrease drastically when the annotated set is made smaller. Our tagger gives above 70% AverageAcuracy for annotated data size as low as 5K and raw untagged data size 10K on all the languages. This justifies the use of small annotated set to build a semi-supervised POS tagging model for resource poor languages. 7.4
In Tables 1, 2 and 4 , we observe that increasing the raw untagged training data size initially increases word coverage of clusters which in turn increases the AverageAcuracy values but stabilizes after a certain size. For all languages we observed that the coverage of words by the clusters in the classifier model increases with the increase in the size of untagged data (while keeping the size of annotated set constant). This accounts for the increase in tagging accuracy and decrease in the number of words missed by the model (tagged as NOTAG). Other interesting observation is that AverageAccuracy does not vary much as 5 Available at http://crfpp.googlecode.com/svn/trunk/doc/index.html, CRF model outputs tag for all test words. So, for CRF tagger AverageAccuracy = (No. of correctly tagged test words)/(No. of test words). the untagged data size varies, so our algorithm is able to perform well even with a small sized untagged data. 7.5
We made the following observations about the e↵ect of parameter values: (1) Increasing threshold values of M inConf idence for parameter Confidence, it increases the quality of clusters but at the same time it also increases the number of context based lists tagged as “NOTVALIST” which decreases the word coverage of clusters. (2) Decreasing threshold values of M inCoverage for parameters Coverage although decreases the quality of clusters but at the same time it increases the word coverage of clusters by decreasing the number of context based lists tagged as “NOTVALIST”. (3) By varying the threshold value of Minprobdif from 5% to 30% for parameter TagProbDif we found that increasing the threshold value increases the precision values of POS tags but slightly decreases their recall because the number of words tagged as “NOTAG” increases. Practical advantage of this parameter is that it ensures that tagging of ambiguous and non-confident cases is avoided. (4) The number of POS tag clusters obtained in the classifier model is almost independent of the selected threshold values of the parameters. For the datasets given in Table 1 and for the range of threshold values M inConf idence = 60% to 90% and M inCoverage = 0% to 75%, number of POS tag clusters found for English was 100 to 101, for Hindi was 29 to 31, for Tamil was 22 to 26, for Bengali was 25 and for Telugu was 23. We noted that the POS tags missing from the set of clusters were the rare POS tags having very low frequencies. 8
In this work we developed TagMiner, a semi-supervised associative classification method for POS tagging. We used the concept of context based list and context based association rule mining. We developed a method to find interestingness measures required to find the association rules in a semi-supervised manner from a training set of tagged and raw untagged data combined. We showed that TagMiner gives good performance for resource rich as well as resource poor languages without using extensive linguistic knowledge. It works well even with less tagged training data and less untagged training data. It can also tag unknown words. To some extent, it handles class imbalance and data sparsity problems using the untagged data and a special method to find interestingness measures. It handles phrase boundary problem using a set of parameters. These advantages make it very suitable for resource poor languages and can be used as an initial POS tagger while developing linguistic resources for them.
Future work includes (1) using other contexts instead of trigram, (2) finding methods to include linguistic features in the current approach, (3) mining tagging patterns from the clusters to find tag of a test word and (4) using this approach for other lexical item classification tasks.