Combining Association Measures for Collocation Extraction Pavel Pecina and Pavel Schlesinger Institute of Formal and Applied Linguistics Charles University, Prague, Czech Republic {pecina,schlesinger}@ufal.mff.cuni.cz Abstract We introduce the possibility of combining lexical association measures and present empirical results of several methods employed in automatic collocation extraction. First, we present a comprehensive summary overview of association measures and their performance on manually annotated data evaluated by precision-recall graphs and mean average precision. Second, we describe several classification methods for combining association measures, followed by their evaluation and comparison with individual measures. Finally, we propose a feature selection algorithm significantly reducing the number of combined measures with only a small performance degradation. 1 Introduction Lexical association measures are mathematical formulas determining the strength of association between two or more words based on their occurrences and cooccurrences in a text corpus. They have a wide spectrum of applications in the field of natural language processing and computational linguistics such as automatic collocation extraction (Manning and Schütze, 1999), bilingual word alignment (Mihalcea and Pedersen, 2003) or dependency parsing. A number of various association measures were introduced in the last decades. An overview of the most widely used techniques is given e.g. in Manning and Schütze (1999) or Pearce (2002). Several researchers also attempted to compare existing methods and suggest different evaluation schemes, e.g Kita (1994) and Evert (2001). A comprehensive study of statistical aspects of word cooccurrences can be found in Evert (2004) or Krenn (2000). In this paper we present a novel approach to automatic collocation extraction based on combining multiple lexical association measures. We also address the issue of the evaluation of association measures by precision-recall graphs and mean av651 erage precision scores. Finally, we propose a stepwise feature selection algorithm that reduces the number of combined measures needed with respect to performance on held-out data. The term collocation has both linguistic and lexicographic character. It has various definitions but none of them is widely accepted. We adopt the definition from Choueka (1988) who defines a collocational expression as "a syntactic and semantic unit whose exact and unambiguous meaning or connotation cannot be derived directly from the meaning or connotation of its components". This notion of collocation is relatively wide and covers a broad range of lexical phenomena such as idioms, phrasal verbs, light verb compounds, technological expressions, proper names, and stock phrases. Our motivation originates from machine translation: we want to capture all phenomena that may require special treatment in translation. Experiments presented in this paper were performed on Czech data and our attention was restricted to two-word (bigram) collocations ­ primarily for the limited scalability of some methods to higher-order n-grams and also for the reason that experiments with longer word expressions would require processing of much larger corpus to obtain enough evidence of the observed events. 2 Reference data The first step in our work was to create a reference data set. Krenn (2000) suggests that collocation extraction methods should be evaluated against a reference set of collocations manually extracted from the full candidate data from a corpus. To avoid the experiments to be biased by underlying data preprocessing (part-of-speech tagging, lemmatization, and parsing), we extracted the reference data from morphologically and syntactically annotated Prague Dependency Treebank 2.0 containing about 1.5 million words annotated on analytical layer (PDT 2.0, 2006). A corpus of this size is certainly not sufficient for real-world applications but we found it adequate for our evaluation purposes ­ a larger corpus would have made the manual collocation extraction task infeasible. Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions, pages 651­658, Sydney, July 2006. c 2006 Association for Computational Linguistics Dependency trees from the corpus were broken down into dependency bigrams consisting of lemmas of the head word and its modifier, their part-of-speech pattern, and dependency type. From 87 980 sentences containing 1 504 847 words, we obtained a total of 635 952 different dependency bigrams types. Only 26 450 of them occur in the data more than five times. The less frequent bigrams do not meet the requirement of sufficient evidence of observations needed by some methods used in this work (they assume normal distribution of observations and become unreliable when dealing with rare events) and were not included in the evaluation. We, however, must agree with Moore (2004) arguing that these cases comprise majority of all the data (the Zipfian phenomenon) and thus should not be excluded from real-world applications. Finally, we filtered out all bigrams having such part-of-speech patterns that never form a collocation (conjunction­ preposition, preposition­pronoun, etc.) and obtained a list consisting of 12 232 dependency bigrams, further called collocation candidates. 2.1 Manual annotation The list of collocation candidates was manually processed by three trained linguists in parallel and independently with the aim of identifying collocations as defined by Choueka. To simplify and clarify the work they were instructed to select those bigrams that can be assigned to these categories: idiomatic expressions multiple annotators. Only those bigrams that all three annotators independently recognized as collocations (of any type) were considered true collocations. The reference data set contains 2 557 such bigrams, which is 20.9% of all. between these two categories reanged from 0.52 to 0.58. The data was split into six stratified samples. Five folds were used for five-fold cross validation and average performance estimation. The remaining one fold was put aside and used as held-out data in experiments described in Section 5. 3 Association measures - studená válka (cold war) - visí otazník (question mark is hanging open question) technical terms - predseda vlády (prime minister) - ocitý svedek (eye witness) support verb constructions - mít pravdu (to be right) - ucinit rozhodnutí (make decision) names of persons, locations, and other entities - Prazský hrad (Prague Castle) - Cervený kríz (Red Cross) stock phrases - zásadní problém (major problem) - konec roku (end of the year) The first (expected) observation was that the interannotator agreement among all the categories was rather poor: the Cohen's between annotators ranged from 0.29 to 0.49, which demonstrates that the notion of collocation is very subjective, domain-specific, and somewhat vague. The reason that three annotators were used was to get a more precise and objective idea about what can be considered a collocation by combining outcomes from 652 In the context of collocation extraction, lexical association measures are formulas determining the degree of association between collocation components. They compute an association score for each collocation candidate extracted from a corpus. The scores indicate the potential for a candidate to be a collocation. They can be used for ranking (candidates with high scores at the top), or for classification (by setting a threshold and discarding all bigrams below this threshold). If some words occur together more often than by chance, then this may be evidence that they have a special function that is not simply explained as a result of their combination (Manning and Schütze, 1999). This property is known in linguistics as non-compositionality. We think of a corpus as a randomly generated sequence of words that is viewed as a sequence of word pairs (dependency bigrams in our case). Occurrence frequencies and marginal frequencies are used in several association measures that reflect how much the word cooccurrence is accidental. Such measures include: estimation of joint and conditional bigram probabilities (Table 1, 1­3), mutual information and derived measures (4­9), statistical tests of independence (10­14), likelihood measures (15­ 16), and various other heuristic association measures and coefficients (17­55) originating in different research fields. By determining the entropy of the immediate context of a word sequence (words immediately preceding or following the bigram), the association measures (56­60) rank collocations according to the assumption that they occur as (syntactic) units in a (information-theoretically) noisy environment (Shimohata et al., 1997). By comparing empirical contexts of a word sequence and of its components (open-class words occurring within # Name 1. Joint probability 2 Formula P (xy ) P (y |x) P (x|y ) log P (x)P (y) log P (x)P (y) log P (x)P (y) +log P (xy ) 2f (xy ) f (x)+f (y ) 2f (xy ) · P (xy ) f (x)+f (y ) P ( xy ) 2 log P (x)P (y) · logf (xy ) ^ P (fi -fi )2 j j ij , ^ fi j f (x)!f (x)!f (y )!f (y )! ¯ ¯ N !f (xy )!f (xy )!f (xy )!f (xy )! ¯ ¯ ¯¯ ^ f (xy )-f (xy ) f (xy )(1-(f (xy )/N )) ^ f (xy )-f (xy ) ^ ^ f (xy )(1-(f (xy )/N )) ^ ^ f (xy )-f (xy ) logf (xy )+logf (xy )! logN fi P j -2 ij fi log ^ ,j fi j P logfi 2 j -2 ij ^ , fi j P ( xy ) 2 P ( xy ) 2 P (xy ) # Name 47. Gini index Formula max[P (x)(P (y |x)2+ P (y |x)2 ) - P (y )2 ¯ ¯ +P (x)(P (y |x)2+ P (y |x)2 ) - P (y )2, ¯ ¯¯ ¯ P (y )(P (x|y )2+ P (x|y )2 ) - P (x)2 ¯ +P (y )(P (x|y )2+ P (x|y )2 ) - P (x)2 ] ¯ ¯ ¯¯ ¯ . Conditional probability 3. Reverse conditional prob. 4. Pointwise mutual inform. 5. Mutual dependency (MD) 6. Log frequency biased MD 7. Normalized expectation 8. Mutual expectation 9 48. Confidence 49. Laplace 50. Conviction 51. Piatersky-Shapiro 52. Certainity factor 53. Added value (AV ) 54. Collective strength 5 max[P (y |x), P (x|y )] max[ N P (x)+2 , N P (y )+2 ] P (x)P (y ) P (x)P (y ) ¯ max[ , ] P (xy ) ¯ P (xy ) ¯ N P (xy )+1 N P (xy )+1 P (xy ) - P (x)P (y ) max[ P (y |x)-P (y ) P (x|y )-P (x) , ] 1-P (y ) 1-P (x) . Salience 2 10. Pearson's test 11. Fisher's exact test 12. t test 13. z score 14. Poison significance measure 15. Log likelihood ratio 16. Squared log likelihood ratio Association coefficients: 17. Russel-Rao 18. Sokal-Michiner 19. Rogers-Tanimoto 20. Hamann 21. Third Sokal-Sneath 22. Jaccard 2 max[P (y |x) - P (y ), P (x|y ) - P (x)] P (xy )+P (xy ) ¯¯ · P (x)P (y )+P (x)P (y ) ¯ 1-P (x)P (y )-P (x)P (y ) ¯ 1-P (xy )-P (xy ) ¯¯ 5. Klosgen p P (xy ) · AV Context measures: 5 5 6. Context entropy 7. Left context entropy 58. Right context entropy 59. Left context divergence P - w P (w|C y ) logP (w|C y ) x x P - w P (w|C ly ) logP (w|C ly ) x x P r r - w P (w|Cxy ) logP (w|Cxy ) P (x) logP (x) P - w P (w|C ly ) logP (w|C ly ) x x P - w P (w|C ry ) logP (w|C ry ) x x P - w P (w|Cx ) log P (w|Cy ) P - w P (w|Cy ) log P (w|Cx ) x qP 2|Cx Cy | |C |+|Cy | 2 w (P (w |Cx ) - P (w|Cy )) P w P (w|Cx )P (w|Cy ) P 2P 2 w P (w|Cx ) · w P (w|Cy ) w 3. First Kulczynsky 24. Second Sokal-Sneath 25. Second Kulczynski 2 2 6. Fourth Sokal-Sneath 7. Odds ratio 28. Yulle's 29. Yulle's Q 30. Driver-Kroeber 31. Fifth Sokal-Sneath 32. Pearson 33. Baroni-Urbani 3 3 a a+b+c+d a +d a+b+c+d a +d a+2b+2c+d (a+d)-(b+c) a+b+c+d b+c a+d a a+b+c a b+c a a+2(b+c) a a 1 2 ( a +b + a +c ) 1 a a d ( a+b + a+c + d+b 4 ad bc ad-bc ad+ bc ad-bc ad+bc a (a+b)(a+c) 60. Right context divergence P (y ) logP (y ) 61. Cross entropy 62. Reverse cross entropy 63. Intersection measure 6 4. Euclidean norm 65. Cosine norm d + d+c ) 6 6. L1 norm P P |P (w|Cx ) - P (w|Cy )| 67. Confusion probability 6 6 8. Reverse confusion prob. 9. Jensen-Shannon diverg. P (x|Cw )P (y |Cw )P (w) P (x) P P (y |Cw )P (x|Cw )P (w) w P (y ) w 1 [D (p(w |C )|| 1 (p(w |C )+p(w |C ))) x x y 2 2 P , w MI (w x)M I (w y ) P , ,2 ,2 w MI (w x) · w MI (w y ) P P (w|C ) P (w|Cx ) log P (w|Cx ) w y P P (w|Cy ) w P (w |Cy ) log P (w|Cx ) +D (p(w|Cy )|| 1 (p(w|Cx ) +p(w|Cy )))] 2 4. Braun-Blanquet 5. Simpson 36. Michael 37. Mountford 38. Fager 39. Unigram subtuples 40. U cost 41. S cost 42. R cost 43. T combined cost 44. Phi 45. Kappa 46. J measure ad (a+b)(a+c)(d+b)(d+c) ad-bc (a+b)(a+c)(d+b)(d+c) a+ ad a+b+c+ ad a max(a+b,a+c) a min(a+b,a+c) 4(ad-bc) (a+d)2 +(b+c)2 2a 2bc+ab+ac a - 1 max(b, c) 2 (a+b)(a+c) 7 0. Cosine of pointwise MI P 71. KL divergence 72. Reverse KL divergence 7 3. Skew divergence D (p(w|Cx )||(w|Cy ) + (1-)p(w|Cx )) f (y |Cxy ) 1 f (x|Cxy ) 2 ( f (xy ) + f (xy ) ) f (y |Cx )-f (xy ) 1 f (x|Cy )-f (xy ) + ) 2( f (xy ) f (xy ) 1 (cos(cx ,cxy) + cos(cy ,cxy)) 2 P xy cz = (zi ); cos(cx ,cy) = P 2 i iP 2 x· y i i 74. Reverse skew divergence D(p(w|Cy )||p(w|Cx ) + (1-)p(w|Cy )) 75. Phrase word coocurrence 76. Word association Cosine context similarity: d log ac -3.29 b 1+1+1+1 a b c d min(b,c)+a log(1+ max(b,c)+a ) min(b,c) -1 log(1+ a+1 ) 2 a a log(1+ a+b ) · log(1+ a+c ) q 7 7. in boolean vector space zi = (f (wi |Cz )) zi = f (wi |Cz ) N fw { | zi = f (wi |Cz ) · df (w ); d ( i)= | x : wi Cx} i 1 2 (dice(cx ,cxy) + dice(cy ,cxy)) P 2 xy i cz = (zi ); dice(cx ,cy) = P 2 Pi 2 x+y i i 78. in tf vector space 79. in tf· idf vector space Dice context similarity: U ×S ×R P (x)P (y )(1-P (x))(1-P (y )) P (xy )+P (xy )-P (x) (y )-P (x) (y ) ¯¯ P ¯P ¯ 1-P (x) (y )-P (x) (y ) P ¯P ¯ P (y |x) P (y |x) ¯ max[P (xy )log P (y) +P (xy )log P (y ) , ¯ ¯ P (x|y ) P (x|y ) ¯ P (xy )log P (x) +P (xy )log P (x) ] ¯ ¯ P (xy )-P (x)P (y ) 80. in boolean vector space 81. in tf vector space 82. in tf· idf vector space zi = (f (wi |Cz )) zi = f (wi |Cz ) N zi = f (wi |Cz ) · df (w ); d ( i)= | x : wi Cx} fw { | i a = f (xy ) b = f (xy ) f (x) A contingency table contains observed frequencies and marginal frequencies for a bigram ¯ xy ; w stands for any word except w; stands for any word; N is a total number of bi¯ c = f (xy ) d = f (xy ) f (x) ¯ ¯¯ ¯ grams. The table cells are sometimes referred to as fij . Statistical tests of independence ^ f (y ) f (y ) ¯ N work with contingency tables of expected frequenciesf (xy ) = f (x)f (y )/N . Cw Cxy l Cxy r Cxy empirical context of w empirical context of xy left immediate context of xy right immediate context of xy d Table 1: Lexical association measures used for bigram collocation extraction. enotes those selected by the model reduction algorithm discussed in Section 5. 653 1.0 0.8 Average precision Precision 0.6 0.6 0.8 1.0 Unaveraged precision curve Averaged precison curve 0.2 0.0 0.2 0.4 0.6 0.8 1.0 0.2 0.0 Pointwise mutual information (4) Pearson's test (10) z score (13) Cosine context similarity in boolean vector space (77) Unigram subtuple measure (39) 0.2 0.4 0.6 0.8 1.0 0.4 Recall 0.4 Recall Figure 1: Vertical averaging of precision-recall curves. Thin curves represent individual non-averaged curves obtained by Pointwise mutual information (4) on five data folds. Figure 2: Crossvalidated and averaged precision-recall curves of selected association measures (numbers in brackets refer to Table 1). a specified context window), the association measures rank collocations according to the assumption that semantically non-compositional expressions typically occur as (semantic) units in different contexts than their components (Zhai, 1997). Measures (61­74) have information theory background and measures (75­82) are adopted from the field of information retrieval. 3.1 Evaluation Collocation extraction can be viewed as classification into two categories. By setting a threshold, any association measure becomes a binary classifier: bigrams with higher association scores fall into one class (collocations), the rest into the other class (non-collocations). Performance of such classifiers can be measured for example by accuracy ­ fraction of correct predictions. However, the proportion of the two classes in our case is far from equal and we want to distinguish classifier performance between them. In this case, several authors, e.g. Evert (2001), suggest using precision ­ fraction of positive predictions correct and recall ­ fraction of positives correctly predicted. The higher the scores the better the classification is. 3.2 Precision-recall curves Since choosing a classification threshold depends primarily on the intended application and there is no principled way of finding it (Inkpen and Hirst, 2002), we can measure performance of association measures by precision­recall scores within the entire interval of possible threshold values. In this manner, individual association measures can be thoroughly compared by their two-dimensional precision-recall curves visualizing the quality of ranking without committing to a classification threshold. The closer the curve stays to the top and right, the better the ranking procedure is. Precision-recall curves are very sensitive to data (see Figure 1). In order to obtain a good estimate of their shapes cross validation and averaging are necessary: all cross-validation folds with scores for each instance are combined and a single curve is drawn. Averaging can be done in three ways: vertical ­ fixing recall, averaging precision, horizontal ­ fixing precision, averaging recall, and combined ­ fixing threshold, averaging both precision and recall (Fawcett, 2003). Vertical averaging, as illustrated in Figure 1, worked reasonably well in our case and was used in all experiments. 3.3 Mean average precision Visual comparison of precision-recall curves is a powerfull evaluation tool in many research fields (e.g. information retrieval). However, it has a serious weakness. One can easily compare two curves that never cross one another. The curve that predominates another one within the entire interval of recall seems obviously better. When this is not the case, the judgment is not so obvious. Also significance tests on the curves are problematic. Only well-defined one-dimensional quality measures can rank evaluated methods by their performance. We adopt such a measure from information retrieval (Hull, 1993). For each cross-validation data fold we define average precision (AP) as the expected value of precision for all possible values of recall (assuming uniform distribution) and mean average precision (MAP) as a mean of this measure computed for each data fold. Significance testing in this case can be realized by paired t-test or by more appropriate nonparametric paired Wilcoxon test. Due to the unreliable precision scores for low recall and their fast changes for high recall, estimation of AP should be limited only to some narrower recall interval, e.g. 0.1,0.9 654 0.7 0.2 77 38 30 5 4 29 22 45 20 18 6 76 48 44 73 26 11 72 53 49 41 40 81 12 51 79 57 67 77 39 80 38 32 31 30 13 10 5 42 37 4 27 28 29 63 16 22 24 23 45 7 33 20 21 19 18 43 34 6 54 9 76 50 3 48 82 8 44 59 66 73 71 61 26 25 15 11 14 74 72 68 70 53 64 52 49 35 65 41 69 55 40 47 75 81 56 46 12 2 60 51 36 78 79 58 62 57 1 17 67 77 38 30 5 4 29 22 45 20 18 6 76 48 44 73 26 11 72 53 49 41 40 81 12 51 79 57 67 Mean average precision Figure 3: a) Mean average precision of all association measures in descending order. Methods are referred by numbers from Table 1. The solid points correspond to measures selected by the model reduction algorithm from Section 5. b) Visualization of p-values from the significance tests of difference between each method pair (order is the same for both graphs). The darker points correspond to p-values greater than = 0.1 and indicate methods with statistically indistinguishable performance (measured by paired Wilcoxon test on values of average precision obtained from five independent data folds). 0.3 0.4 0.5 0.6 3.4 Experiments and results In the initial experiments, we implemented all 82 association measures from Table 1, processed all morphologically and syntactically annotated sentences from PDT 2.0, and computed scores of all the association measures for each dependency bigram in the reference data. For each association measure and each of the five evaluation data folds, we computed precision-recall scores and drew an averaged precision-recall curve. Curves of some well-performing methods are depicted in Figure 2. Next, for each association measure and each data fold, we estimated scores of average precision on narrower recall interval 0.1,0.9 , computed mean average precision, ranked the association measures according to MAP in descending order, and result depicted in Figure 3 a). Finally, we applied a paired Wilcoxon test, detected measures with statistically indistinguishable performance, and visualized this information in Figure 3 b). A baseline system ranking bigrams randomly operates with average precision of 20.9%. The best performing method for collocation extraction measured by mean average precision is cosine context similarity in boolean vector space (77) (MAP 66.49%) followed by other 16 association measures with nearly identical performance (Figure 3 a). They include some popular methods well-known to perform reliably in this task, such as pointwise mutual information (4), Pearson's 2 test (10), z score (13), odds ratio (27), or squared log likelihood ratio (16). The interesting point to note is that, in terms of MAP, context similarity measures, e.g. (77), slightly outperform measures based on simple oc- curence frequencies, e.g. (39). In a more thorough comparison by percision-recall curves, we observe that the former very significantly predominates the latter in the first half of the recall interval and vice versa in the second half (Figure 2). This is a case where the MAP is not a sufficient metric for comparison of association measure performance. It is also worth pointing out that even if two methods have the same precision-recall curves the actual bigram rank order can be very different. Existence of such non-correlated (in terms of ranking) measures will be essential in the following sections. 4 Combining association measures Each collocation candidate xi can be described by the feature vector xi = (xi , . . . , xi 2 )T consisting 1 8 of 82 association scores from Table 1 and assigned a label y i {0, 1} which indicates whether the bigram is considered to be a collocation (y = 1) or not (y = 0). We look for a ranker function f (x) R that determines the strength of lexical association between components of bigram x and hence has the character of an association measure. This allows us to compare it with other association measures by the same means of precision-recall curves and mean average precision. Further, we present several classification methods and demonstrate how they can be employed for ranking, i.e. what function can be used as a ranker. For references see Venables and Ripley (2002). 4.1 Linear logistic regression An additive model for binary response is represented by a generalized linear model (GLM) in a form of logistic regression: logit( ) = 0 + 1 x1 + . . . + p xp 655 method R=20 NNet (5 units) NNet (3 units) NNet (2 units) SVM (linear) LDA SVM (quadratic) NNet (1 unit) GLM Cosine similarity (77) Unigram subtuples (39) 89.56 89.41 86.92 85.72 84.72 84.29 77.98 82.45 80.94 74.55 AP R=50 82.74 81.99 81.68 79.49 77.18 79.54 76.83 76.26 68.90 67.49 R=80 70.11 69.64 68.33 63.86 62.90 64.24 66.75 58.61 50.54 55.16 MAP R= 0.1,0.9 80.81 79.71 78.77 75.66 75.11 74.53 73.25 71.88 66.49 65.74 + 21.53 19.88 18.47 13.79 12.96 12.09 10.17 8.11 0.00 0.8 Average precision 0.6 1.0 Neural network (5 units) Support vector machine (linear) Linear discriminant analysis Neural network (1 unit) Linear logistic regression Cosine context similarity in boolean vector space (77) Unigram subtuple measure (39) 0.2 0.0 0.4 0.2 0.4 0.6 0.8 1.0 Recall Table 2: Performance of methods combining all association measures: average precision (AP) for fixed recall values and mean average precision (MAP) on the narrower recall interval with relative improvement in the last column (values in %). Figure 4: Precision-recall curves of selected methods combining all association measures compared with curves of two best measures employed individually on the same data sets. where logit( ) = log(/(1 - )) is a canonical link function for odds-ratio and (0, 1) is a conditional probability for positive response given a vector x. The estimation of 0 and is done by maximum likelihood method which is solved by the iteratively reweighted least squares algorithm. The ranker function in this case is defined as the predicted value , or equivalently (due to the monotonicity of logit link function) as the linear combination 0 + Tx. 4.2 Linear discriminant analysis The basic idea of Fisher's linear discriminant analysis (LDA) is to find a one-dimensional projection defined by a vector c so that for the projected combination cTx the ratio of the between variance B to the within variance W is maximized: max c search, Hastie (2004) proposed an effective algorithm which fits the entire SVM regularization path [0 (), ()] and gave us the option to choose the optimal value of . As an objective function we used total amount of loss on training data. 4.4 Neural networks Assuming the most common model of neural networks (NNet) with one hidden layer, the aim is to find inner weights wj h and outer weights whi for w y i = 0 0 + w hi h (h + w j h xj ) cTB c cTW c After projection, cTx can be directly used as ranker. 4.3 Support vector machines For technical reason, let us now change the labels y i {-1,+1}. The goal in support vector machines (SVM) is to estimate a functionf (x) = 0+ Tx and f w find a classifier y (x) = sign (x) hich can be solved through the following convex optimization: min 0 , here h ranges over units in the hidden layer. Activation functions h and function 0 are fixed. Typically, h is taken to be the logistic function h (z ) = exp(z )/(1 + exp(z )) and 0 to be the indicator function 0 (z ) = I (z > ) with as a classification threshold. For ranking we simply set 0 (z ) = z . Parameters of neural networks are estimated by the backpropagation algorithm. The loss function can be based either on least squares or maximum likehood. To avoid problems with convergence of the algorithm we used the former one. The tuning parameter of a classifier is then the number of units in the hidden layer. 4.5 Experiments and results in =1 1 - y (0 + x ) i T i + + || ||2 2 with as a regularization parameter. The hinge loss function L(y ,f (x)) = [1 - y f (x)]+ is active only for positive values (i.e. bad predictions) and therefore is very suitable for ranking models with 0 + Tx as a ranker function. Setting the regularization parameter is crucial for both the estimators 0 , and further classification (or ranking). As an alternative to a often inappropriate grid 656 To avoid incommensurability of association measures in our experiments, we used a common preprocessing technique for multivariate standardization: we centered values of each association measure towards zero and scaled them to unit variance. Precision-recall curves of all methods were obtained by vertical averaging in five-fold cross validation on the same reference data as in the earlier experiments. Mean average precision was computed from average precision values estimated on the recall interval 0.1,0.9 . In each cross-validation step, four folds were used for training and one fold for testing. All methods performed very well in comparison with individual measures. The best result was achieved by a neural network with five units in the hidden layer with 80.81% MAP, which is 21.53% relative improvement compared to the best individual associaton measure. More complex models, such as neural networks with more than five units in the hidden layer and support vector machines with higher order polynomial kernels, were highly overfitted on the training data folds and better results were achieved by simpler models. Detailed results of all experiment are given in Table 2 and precision-recall curves of selected methods depicted in Figure 4. Average precision 0.6 0.8 1.0 NNet (5 units) with 82 predictors NNet (5 units) with 42 predictors NNet (5 units) with 17 predictors NNet (5 units) with 7 predictors Cosine context similarity in boolean vector space (77) Unigram subtuple measure (39) 0.2 0.0 0.4 0.2 0.4 0.6 0.8 1.0 Recall Figure 5: Precision-recall curves of four NNet models from the model reduction process with different number of predictors compared with curves of two best individual methods. 5 Model reduction Combining association measures by any of the presented methods is reasonable and helps in the collocation extraction task. However, the combination models are too complex in number of predictors used. Some association measures are very similar (analytically or empirically) and as predictors perhaps even redundant. Such measures have no use in the models, make their training harder, and should be excluded. Principal component analysis applied to the evaluation data showed that 95% of its total variance is explained by only 17 principal components and 99.9% is explained by 42 of them. This gives us the idea that we should be able to significantly reduce the number of variables in our models with no (or relativelly small) degradation in their performance. 5.1 The algorithm A straightforward, but in our case hardly feasible, approach is an exhaustive search through the space of all possible subsets of all association measures. Another option is a heuristic step-wise algorithm iteratively removing one variable at a time until some stopping criterion is met. Such algorithms are not very robust, they are sensitive to data and generally not very recommended. However, we tried to avoid these problems by initializing our step-wise algorithm by clustering similar variables and choosing one predictor from each cluster as a representative of variables with the same contribution to the model. Thus we remove the highly corelated predictors and continue with the step-wise procedure. 657 The algorithm starts with the hierarchical clustering of variables in order to group those with a similar contribution to the model, measured by the absolute value of Pearson's correlation coefficient. After 82-d iterations, variables are grouped into d non-empty clusters and one representative from each cluster is selected as a predictor into the initial model. This selection is based on individual predictor performance on held-out data. Then, the algorithm continues with d predictors in the initial model and in each iteration removes a predictor causing minimal degradation of performance measured by MAP on held-out data. The algorithm stops when the difference becomes significant ­ either statistically (by paired Wilcoxon test) or practically (set by a human). 5.2 Experiments and results We performed the model reduction experiment on the neural network with five units in the hidden layer (the best performing combination method). The similarity matrix for hierarchical clustering was computed on the held-out data and parameter d (number of initial predictors) was experimentally set to 60. In each iteration of the algorithm, we used four data folds (out of the five used in previous experiments) for fitting the models and the held-out fold to measure the performance of these models and to select the variable to be removed. The new model was cross-validated on the same five data-folds as in the previous experiments. Precision-recall curves for some intermediate models are shown in Figure 5. We can conclude that we were able to reduce the NNet model to about 17 predictors without statistically significant difference in performance. The corresponding association measures are marked in Table 1 and highlighted in Figure 3a). They include measures from the entire range of individual mean average precision values. 6 Conclusions and discussion We created and manually annotated a reference data set consisting of 12 232 Czech dependency bigrams. 20.9% of them were agreed to be a collocation by three annotators. We implemented 82 association measures, employed them for collocation extraction and evaluated them against the reference data set by averaged precision-recall curves and mean average precision in five-fold cross validation. The best result was achieved by a method measuring cosine context similarity in boolean vector space with mean average precision of 66.49%. We exploit the fact that different subgroups of collocations have different sensitivity to certain association measures and showed that combining these measures aids in collocation extraction. All investigated methods significantly outperformed individual association measures. The best results were achieved by a simple neural network with five units in the hidden layer. Its mean average precision was 80.81% which is 21.53% relative improvement with respect to the best individual measure. Using more complex neural networks or a quadratic separator in support vector machines led to overtraining and did not improve the performace on test data. We proposed a stepwise feature selection algorithm reducing the number of predictors in combination models and tested it with the neural network. We were able to reduce the number of its variables from 82 to 17 without significant degradation of its performance. No attempt in our work has been made to select the "best universal method" for combining association measures nor to elicit the "best association measures" for collocation extraction. These tasks depend heavily on data, language, and notion of collocation itself. We demonstrated that combining association measures is meaningful and improves precission and recall of the extraction procedure and full performance improvement can be achieved by a relatively small number of measures combined. Preliminary results of our research were already published in Pecina (2005). In the current work, we used a new version of the Prague Dependecy Treebank (PDT 2.0, 2006) and the reference data was improved by additional manual anotation by two linguists. 658 Acknowledgments This work has been supported by the Ministry of Education of the Czech Republic, projects MSM 0021620838 and LC 536. We would like to thank our advisor Jan Hajic, our colleagues, and anonymous reviewers for their valuable comments. References Y. Choueka. 1988. Looking for needles in a haystack or locating interesting collocational expressions in large textual databases. In Proceedings of the RIAO. S. Evert and B. Krenn. 2001. Methods for the qualitative evaluation of lexical association measures. In Proceedings of the 39th Annual Meeting of the ACL, Toulouse, France. S. Evert. 2004. The Statistics of Word Cooccurrences: Word Pairs and Collocations. Ph.D. thesis, Univ. of Stuttgart. T. Fawcett. 2003. ROC graphs: Notes and practical considerations for data mining researchers. Technical report, HPL-2003-4. HP Laboratories, Palo Alto, CA. T. Hastie, S. Rosset, R. Tibshirani, and J. Zhu. 2004. The entire regularization path for the support vector machine. Journal of Machine Learning Research, 5. D. Hull. 1993. Using statistical testing in the evaluation of retrieval experiments. In Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, New York, NY. D. Inkpen and G. Hirst. 2002. Acquiring collocations for lexical choice between near synonyms. In SIGLEX Workshop on Unsupervised Lexical Acquisition, 40th meeting of the ACL, Philadelphia. K. Kita, Y. Kato, T. Omoto, and Y. Yano. 1994. A comparative study of automatic extraction of collocations from corpora: Mutual information vs. cost criteria. Journal of Natural Language Processing. B. Krenn. 2000. The Usual Suspects: Data-Oriented Models for Identification and Representation of Lexical Collocations. Ph.D. thesis, Saarland University. C. D. Manning and H. Schütze. 1999. Foundations of Statistical Natural Language Processing. The MIT Press, Cambridge, Massachusetts. R. Mihalcea and T. Pedersen. 2003. An evaluation exercise for word alignment. In Proceedings of HLT-NAACL Workshop, Building and Using Parallel Texts: Data Driven Machine Translation and Beyond, Edmonton, Alberta. R. C. Moore. 2004. On log-likelihood-ratios and the significance of rare events. In Proceedings of the 2004 Conference on EMNLP, Barcelona, Spain. D. Pearce. 2002. A comparative evaluation of collocation extraction techniques. In Third International Conference on language Resources and Evaluation, Las Palmas, Spain. P. Pecina. 2005. An extensive empirical study of collocation extraction methods. In Proceedings of the ACL 2005 Student Research Workshop, Ann Arbor, USA. S. Shimohata, T. Sugio, and J. Nagata. 1997. Retrieving collocations by co-occurrences and word order constraints. In Proc. of the 35th Meeting of ACL/EACL, Madrid, Spain. W. N. Venables and B. D. Ripley. 2002. Modern Applied Statistics with S. 4th ed. Springer Verlag, New York. C. Zhai. 1997. Exploiting context to identify lexical atoms: A statistical view of linguistic context. In International and Interdisciplinary Conf. on Modeling and Using Context. PDT 2.0. 2006. http://ufal.mff.cuni.cz/pdt2.0/.