You are an expert at summarizing long articles. Proceed to summarize the following text: 
we address the problem of clustering words , or that of constructing a thesaurus , based on co - occurrence data . we view this problem as that of estimating a joint probability distribution over word pairs , specifying the joint probabilities of word pairs , such as noun verb pairs . in this paper , we assume that the joint distribution can be expressed in the following manner , which is stated for noun verb pairs for the sake of readability : the joint probability of a noun and a verb is expressed as the product of the joint probability of the noun class and the verb class which the noun and the verb respectively belong to , and the conditional probabilities of the noun and the verb given their respective classes .    as a method for estimating such a probability distribution , we propose an algorithm based on the minimum description length ( mdl ) principle . our clustering algorithm iteratively merges noun classes and verb classes in turn , in a bottom up fashion . for each merge it performs , it calculates the increase in data description length resulting from merging any noun ( or verb ) class pair , and performs the merge having the least increase in data description length , provided that the increase in data description length is less than the reduction in model description length . there have been a number of methods proposed in the literature to address the word clustering problem ( e.g. , @xcite ) . the method proposed in this paper is a natural extension of both li & abe s and brown et al s methods , and is an attempt to overcome their drawbacks while retaining their advantages . the method of brown et al , which is based on the maximum likelihood estimation ( mle ) , performs a merge which would result in the least reduction in ( average ) mutual information . our method turns out to be equivalent to performing the merge with the least reduction in mutual information , provided that the reduction is below a certain threshold which depends on the size of the co - occurrence data and the number of classes in the current situation . this method , based on the mdl principle , takes into account both the fit to data and the simplicity of a model , and thus can help cope with the over - fitting problem that the mle - based method of brown et al faces .    the model employed in @xcite is based on the assumption that the word distribution within a class is a uniform distribution , i.e. every word in a same class is generated with an equal probability . employing such a model has the undesirable tendency of classifying into different classes those words that have similar co - occurrence patterns but have different absolute frequencies . the proposed method , in contrast , employs a model in which different words within a same class can have different conditional generation probabilities , and thus can classify words in a way that is not affected by words absolute frequencies and resolve the problem faced by the method of @xcite . we evaluate our clustering method by using the word classes and the joint probabilities obtained by it in syntactic disambiguation experiments . our experimental results indicate that using the word classes constructed by our method gives better disambiguation results than when using li & abe or brown et al s methods . by combining thesauruses automatically constructed by our method and an existing hand - made thesaurus ( wordnet ) , we were able to achieve the overall accuracy of @xmath0 for pp - attachment disambiguation , which compares favorably against the accuracy ( @xmath1 ) obtained using the state - of - the - art method of @xcite . suppose available to us are co - occurrence data over two sets of words , such as the sample of verbs and the head words of their direct objects given in fig . [ fig : co - occurrence ] . our goal is to ( hierarchically ) cluster the two sets of words so that words having similar co - occurrence patterns are classified in the same class , and output a thesaurus for each set of words .    we can view this problem as that of estimating the best probability model from among a class of models of ( probability distributions ) which can give rise to the co - occurrence data .    in this paper , we consider the following type of probability models . assume without loss of generality that the two sets of words are a set of nouns @xmath2 and a set of verbs @xmath3 . a partition @xmath4 of @xmath2 is a set of noun - classes satisfying @xmath5 and @xmath6 . a partition @xmath7 of @xmath3 can be defined analogously . we then define a probability model of noun - verb co - occurrence by defining the joint probability of a noun @xmath8 and a verb @xmath9 as the product of the joint probability of the noun and verb classes that @xmath8 and @xmath9 belong to , and the conditional probabilities of @xmath8 and @xmath9 _ given _ their classes , that is , @xmath10 where @xmath11 and @xmath12 denote the ( unique ) classes to which @xmath8 and @xmath9 belong . in this paper , we refer to this model as the ` hard clustering model , ' since it is based on a type of clustering in which each word can belong to only one class . [ fig : hardmodel ] shows an example of the hard clustering model that can give rise to the co - occurrence data in fig . [ fig : co - occurrence ] . a particular choice of partitions for a hard clustering model is referred to as a ` discrete ' hard - clustering model , with the probability parameters left to be estimated . the values of these parameters can be estimated based on the co - occurrence data by the maximum likelihood estimation . for a given set of co - occurrence data @xmath13 the maximum likelihood estimates of the parameters are defined as the values that maximize the following likelihood function with respect to the data : @xmath14    it is easy to see that this is possible by setting the parameters as @xmath15 @xmath16 here , @xmath17 denotes the entire data size , @xmath18 the frequency of word pairs in class pair @xmath19 , @xmath20 the frequency of word @xmath21 , and @xmath22 the frequency of words in class @xmath23 . the question now is what criterion should we employ to select the best model from among the possible models . here we adopt the minimum description length ( mdl ) principle . mdl @xcite is a criterion for data compression and statistical estimation proposed in information theory .    in applying mdl , we calculate the code length for encoding each model , referred to as the ` model description length ' @xmath24 , the code length for encoding the given data through the model , referred to as the ` data description length ' @xmath25 and their sum : @xmath26 the mdl principle stipulates that , for both data compression and statistical estimation , the best probability model with respect to _ given data _ is that which requires the least total description length .    the data description length is calculated as @xmath27 where @xmath28 stands for the maximum likelihood estimate of @xmath29 ( as defined in section  [ sec : estimate ] ) . we then calculate the model description length as @xmath30 where @xmath31 denotes the number of _ free _ parameters in the model , and @xmath17 the entire data size . , and the conditional probabilities @xmath32 and @xmath33 . since these alternatives are approximations of one another asymptotically , here we use only the simplest formulation . in the full paper , we plan to compare the empirical behavior of the alternatives . ] in this paper , we ignore the code length for encoding a ` discrete model , ' assuming implicitly that they are equal for all models and consider only the description length for encoding the parameters of a model as the model description length . if computation time were of no concern , we could in principle calculate the total description length for each model and select the optimal model in terms of mdl . since the number of hard clustering models is of order @xmath34 , where @xmath35 and @xmath36 denote the size of the noun set and the verb set , respectively , it would be infeasible to do so . we therefore need to devise an efficient algorithm that heuristically performs this task . the proposed algorithm , which we call ` 2d - clustering , ' iteratively selects a suboptimal mdl - model from among those hard clustering models which can be obtained from the current model by merging a noun ( or verb ) class pair . as it turns out , the minimum description length criterion can be reformalized in terms of ( average ) mutual information , and a greedy heuristic algorithm can be formulated to calculate , in each iteration , the reduction of mutual information which would result from merging any noun ( or verb ) class pair , and perform the merge having the least mutual information reduction , _ provided that the reduction is below a variable threshold_.    2d - clustering@xmath37 + ( @xmath38 is the input co - occurrence data , and @xmath39 and @xmath40 are positive integers . )    1 . initialize the set of noun classes @xmath4 and the set of verb classes @xmath7 as : @xmath41 where @xmath2 and @xmath3 denote the noun set and the verb set , respectively . 2 .   repeat the following three steps : 1 .   execute merge@xmath42 to update @xmath4 , 2 . execute merge@xmath43 to update @xmath7 , 3 . if @xmath4 and @xmath7 are unchanged , go to step 3 . 3 .   construct and output a thesaurus for nouns based on the history of @xmath4 , and one for verbs based on the history of @xmath7 . next , we describe the procedure of ` merge , ' as it is being applied to the set of noun classes with the set of verb classes fixed . merge@xmath42    1 .   for each class pair in @xmath4 , calculate the reduction of mutual information which would result from merging them . ( the details will follow . ) discard those class pairs whose mutual information reduction ( [ eq : implement ] ) is not less than the threshold of @xmath44 where @xmath17 denotes the total data size , @xmath45 the number of free parameters in the model before the merge , and @xmath46 the number of free parameters in the model after the merge . sort the remaining class pairs in ascending order with respect to mutual information reduction . 2 .   merge the first @xmath39 class pairs in the sorted list . 3 .   output current @xmath4 . we perform ( maximum of ) @xmath39 merges at step 2 for improving efficiency , which will result in outputting an at - most @xmath39-ary tree . note that , strictly speaking , once we perform one merge , the model will change and there will no longer be a guarantee that the remaining merges still remain justifiable from the viewpoint of mdl . next , we explain why the criterion in terms of description length can be reformalized in terms of mutual information . we denote the model before a merge as @xmath47 and the model after the merge as @xmath48 . according to mdl , @xmath48 should have the least increase in data description length @xmath49 and at the same time satisfies @xmath50 this is due to the fact that the decrease in model description length equals @xmath51 and is identical for each merge . in addition , suppose that @xmath48 is obtained by merging two noun classes @xmath52 and @xmath53 in @xmath47 to a single noun class @xmath54 . we in fact need only calculate the difference between description lengths with respect to these classes , i.e. , @xmath55 now using the identity @xmath56 we can rewrite the above as @xmath57 thus , the quantity @xmath58 is equivalent to the mutual information reduction times the data size . and @xmath7 is defined as @xmath59 ] we conclude therefore that in our present context , a clustering with the least data description length increase is equivalent to that with the least mutual information decrease . canceling out @xmath60 and replacing the probabilities with their maximum likelihood estimates , we obtain @xmath61 therefore , we need calculate only this quantity for each possible merge at step 1 of merge .    in our implementation of the algorithm , we first load the co - occurrence data into a matrix , with nouns corresponding to rows , verbs to columns . when merging a noun class in row @xmath62 and that in row @xmath63 ( @xmath64 ) , for each @xmath12 we add @xmath65 and @xmath66 obtaining @xmath67 , write @xmath67 on row @xmath62 , move @xmath68 to row @xmath63 , and reduce the matrix by one row .    by the above implementation , the worst case time complexity of the algorithm is @xmath69 where @xmath35 denotes the size of the noun set , @xmath36 that of the verb set . if we can merge @xmath39 and @xmath40 classes at each step , the algorithm will become slightly more efficient with the time complexity of @xmath70 . we can restrict the hard clustering model ( [ eq : hardmodel ] ) by assuming that words within a same class are generated with an equal probability , obtaining @xmath71 which is equivalent to the model proposed by @xcite . employing this restricted model has the undesirable tendency to classify into different classes those words that have similar co - occurrence patterns but have different absolute frequencies . the hard clustering model defined in ( [ eq : hardmodel ] ) can also be considered to be an extension of the model proposed by brown et al . first , dividing ( [ eq : hardmodel ] ) by @xmath72 , we obtain @xmath73 since hard clustering implies @xmath74 holds , we have @xmath75 in this way , the hard clustering model turns out to be a class - based bigram model and is similar to brown et al s model . the difference is that the model of ( [ eq : hardmodel2 ] ) assumes that the clustering for @xmath11 and the clustering for @xmath12 can be different , while the model of brown et al assumes that they are the same . a very general model of noun verb joint probabilities is a model of the following form : @xmath76 here @xmath77 denotes a set of noun classes satisfying @xmath78 , but not necessarily disjoint . similarly @xmath79 is a set of not necessarily disjoint verb classes . we can view the problem of clustering words in general as estimation of such a model . this type of clustering in which a word can belong to several different classes is generally referred to as ` soft clustering . ' if we assume in the above model that each verb forms a verb class by itself , then ( [ eq : softmodel ] ) becomes @xmath80 which is equivalent to the model of pereira et al . on the other hand , if we restrict the general model of ( [ eq : softmodel ] ) so that both noun classes and verb classes are disjoint , then we obtain the hard clustering model we propose here ( [ eq : hardmodel ] ) . all of these models , therefore , are some special cases of ( [ eq : softmodel ] ) . each specialization comes with its merit and demerit . for example , employing a model of soft clustering will make the clustering process more flexible but also make the learning process more computationally demanding . our choice of hard clustering obviously has the merits and demerits of the soft clustering model reversed . our method is also an extension of that proposed by brown et al from the viewpoint of estimation criterion . their method merges word classes so that the reduction in mutual information , or equivalently the increase in data description length , is minimized . their method has the tendency to overfit the training data , since it is based on mle . employing mdl can help solve this problem . we apply the acquired word classes , or more specifically the probability model of co - occurrence , to the problem of structural disambiguation . in particular , we consider the problem of resolving pp - attachment ambiguities in quadruples , like ( see , girl , with , telescope ) and that of resolving ambiguities in compound noun triples , like ( data , base , system ) . in the former , we determine to which of ` see ' or ` girl ' the phrase ` with telescope ' should be attached . in the latter , we judge to which of ` base ' or ` system ' the word ` data ' should be attached . we can perform pp - attachment disambiguation by comparing the probabilities @xmath81 if the former is larger , we attach ` with telescope ' to ` see ; ' if the latter is larger we attach it to ` girl ; ' otherwise we make no decision . ( disambiguation on compound noun triples can be performed similarly . )    since the number of probabilities to be estimated is extremely large , estimating all of these probabilities accurately is generally infeasible ( i.e. , the data sparseness problem ) . using our clustering model to calculate these conditional probabilities ( by normalizing the joint probabilities with marginal probabilities ) can solve this problem . we further enhance our disambiguation method by the following back - off procedure : we first estimate the two probabilities in question using hard clustering models constructed by our method . we also estimate the probabilities using an existing ( hand - made ) thesaurus with the ` tree cut ' estimation method of @xcite , and use these probability values when the probabilities estimated based on hard clustering models are both zero . finally , if both of them are still zero , we make a default decision . in this experiment , we used heuristic rules to extract verbs and the head words of their direct objects from the _ tagged _ texts of the wsj corpus ( acl / dci cd - rom1 ) consisting of 126,084 sentences . we then constructed a number of thesauruses based on these data , using our method . [ fig : exthesau ] shows a part of a thesaurus for 100 randomly selected nouns , based on their appearances as direct objects of 20 randomly selected verbs . the thesaurus seems to agree with human intuition to some degree , although it is constructed based on a relatively small amount of co - occurrence data . for example , ` stock , ' ` security , ' and ` bond ' are classified together , despite the fact that their absolute frequencies in the data vary a great deal ( 272 , 59 , and 79 , respectively . ) the results demonstrate a desirable feature of our method , namely , it classifies words based solely on the similarities in co - occurrence data , and is not affected by the absolute frequencies of the words . we extracted compound noun doubles ( e.g. , ` data base ' ) from the tagged texts of the wsj corpus and used them as training data , and then conducted structural disambiguation on compound noun triples ( e.g. , ` data base system ' ) . we first randomly selected 1,000 nouns from the corpus , and extracted compound noun doubles containing those nouns as training data and compound noun triples containing those nouns as test data . there were 8,604 training data and 299 test data . we hand - labeled the test data with the correct disambiguation ` answers . ' we performed clustering on the nouns on the left position and the nouns on the right position in the training data by using both our method ( ` 2d - clustering ' ) and brown et al s method ( ` brown ' ) . we actually implemented an extended version of their method , which separately conducts clustering for nouns on the left and those on the right ( which should only improve the performance ) . 4.5 cm    we next conducted structural disambiguation on the test data , using the probabilities estimated based on 2d - clustering and brown . we also tested the method of using the probabilities estimated based on word co - occurrences , denoted as ` word - based . ' fig . [ fig : compound ] shows the results in terms of accuracy and coverage , where coverage refers to the percentage of test data for which the disambiguation method was able to make a decision . since for brown the number of classes finally created has to be designed in advance , we tried a number of alternatives and obtained results for each of them . ( note that , for 2d - clustering , the optimal number of classes is automatically selected . ) [ tab : compound ]    .compound noun disambiguation results [ cols="<,^",options="header " , ]     we then enhanced each of these methods by using a default rule when a decision can not be made , which is indicated as ` + default . ' [ tab : pp - attach - final ] shows the results of these experiments . we can make a number of observations from these results . ( 1 ) 2d - clustering achieves a broader coverage than nounclass-2dc . this is because in order to estimate the probabilities for disambiguation , the former exploits more information than the latter . ( 2 ) for brown , we show here only its best result , which happens to be the same as the result for 2d - clustering , but in order to obtain this result we had to take the trouble of conducting a number of tests to find the best level of clustering . for 2d - clustering , this was done once and automatically . compared with li - abe96 , 2d - clustering clearly performs better . therefore we conclude that our method improves these previous clustering methods in one way or another . ( 3 ) 2d - clustering outperforms wordnet in term of accuracy , but not in terms of coverage . this seems reasonable , since an automatically constructed thesaurus is more domain dependent and therefore captures the domain dependent features better , and thus can help achieve higher accuracy . on the other hand , with the relatively small size of training data we had available , its coverage is smaller than that of a general purpose hand made thesaurus . the result indicates that it makes sense to combine automatically constructed thesauruses and a hand - made thesaurus , as we have proposed in section  [ sec : disam ] . this method of combining both types of thesauruses ` 2d - clustering+wordnet+default ' was then tested . we see that this method performs the best . ( see tab . [ tab : pp - attach - final ] . ) finally , for comparison , we tested the ` transformation - based error - driven learning ' proposed in @xcite , which is a state - of - the - art method for pp - attachment disambiguation . tab . [ tab : pp - attach - final ] shows the result for this method as ` brill - resnik . ' we see that our disambiguation method also performs better than brill - resnik . ( note further that for brill & resnik s method , we need to use quadruples as training data , whereas ours only requires triples . ) we have proposed a new method of clustering words based on co - occurrence data . our method employs a probability model which naturally represents co - occurrence patterns over word pairs , and makes use of an efficient estimation algorithm based on the mdl principle . our clustering method improves upon the previous methods proposed by brown et al and @xcite , and furthermore it can be used to derive a disambiguation method with overall disambiguation accuracy of @xmath0 , which improves the performance of a state - of - the - art disambiguation method . the proposed algorithm , 2d - clustering , can be used in practice , as long as the data size is at the level of the current penn tree bank . yet it is still relatively computationally demanding , and thus an important future task is to further improve on its computational efficiency . we are grateful to dr . s.  doi of nec c&c media res . labs .  for his encouragement . we thank ms . y.  yamaguchi of nis for her programming efforts .
we address the problem of clustering words ( or constructing a thesaurus ) based on co - occurrence data , and using the acquired word classes to improve the accuracy of syntactic disambiguation . 
 we view this problem as that of estimating a joint probability distribution specifying the joint probabilities of word pairs , such as noun verb pairs . 
 we propose an efficient algorithm based on the minimum description length ( mdl ) principle for estimating such a probability distribution . 
 our method is a natural extension of those proposed in @xcite and @xcite , and overcomes their drawbacks while retaining their advantages . 
 we then combined this clustering method with the disambiguation method of @xcite to derive a disambiguation method that makes use of both automatically constructed thesauruses and a hand - made thesaurus . 
 the overall disambiguation accuracy achieved by our method is @xmath0 , which compares favorably against the accuracy ( @xmath1 ) obtained by the state - of - the - art disambiguation method of @xcite .