Computational Approaches to Measuring the Similarity of Short Contexts : A Review of Applications and Methods <s> First-order Similarity <s> A well constructed thesaurus has long been recognized as a valuable tool in the effective operation of an information retrieval system. This paper reports the results of experiments designed to determine the validity of an approach to the automatic construction of global thesauri (described originally by Crouch in [1] and [2] based on a clustering of the document collection. The authors validate the approach by showing that the use of thesauri generated by this method results in substantial improvements in retrieval effectiveness in four test collections. The term discrimination value theory, used in the thesaurus generation algorithm to determine a term's membership in a particular thesaurus class, is found not to be useful in distinguishing a “good” from an “indifferent” or “poor” thesaurus class). In conclusion, the authors suggest an alternate approach to automatic thesaurus construction which greatly simplifies the work of producing viable thesaurus classes. Experimental results show that the alternate approach described herein in some cases produces thesauri which are comparable in retrieval effectiveness to those produced by the first method at much lower cost. <s> BIB001 </s> Computational Approaches to Measuring the Similarity of Short Contexts : A Review of Applications and Methods <s> First-order Similarity <s> Query expansion methods have been studied for a long time - with debatable success in many instances. In this paper we present a probabilistic query expansion model based on a similarity thesaurus which was constructed automatically. A similarity thesaurus reflects domain knowledge about the particular collection from which it is constructed. We address the two important issues with query expansion: the selection and the weighting of additional search terms. In contrast to earlier methods, our queries are expanded by adding those terms that are most similar to the concept of the query, rather than selecting terms that are similar to the query terms. Our experiments show that this kind of query expansion results in a notable improvement in the retrieval effectiveness when measured using both recall-precision and usefulness. <s> BIB002 </s> Computational Approaches to Measuring the Similarity of Short Contexts : A Review of Applications and Methods <s> First-order Similarity <s> Human evaluations of machine translation are extensive but expensive. Human evaluations can take months to finish and involve human labor that can not be reused. We propose a method of automatic machine translation evaluation that is quick, inexpensive, and language-independent, that correlates highly with human evaluation, and that has little marginal cost per run. We present this method as an automated understudy to skilled human judges which substitutes for them when there is need for quick or frequent evaluations. <s> BIB003
First-order methods are the most intuitive approaches to measuring the similarity of short contexts. They rely on finding the number of words that are shared (or overlapping) between the contexts. Two contexts that share a large percentage of their words are likely to be similar, and this can be detected by simple string matching. The effectiveness of first order matching when contexts share many words can be seen in the following example: (13) I visited Russia in 1996. (14) In 1996 I went to Russia. Contexts (13) and (14) are similar to the point of being nearly identical, and it's clear that the differences in word order have no impact on this judgment. The count of the number of words they share will depend on if a stop-list is used; this is simply a list of non-content words such as conjunctions, articles, etc. that occur in all kinds of contexts and are not considered useful for discriminating between contexts and are therefore removed prior to matching. In (13) and (14) I, in, and to would likely be removed as stop words, leaving Russia and 1996 as matches. First-order similarity scores are based on the number of matching words. For example the Matching Coefficient reports the number of shared words, while the Jaccard and Dice Coefficients scale the number of matches by the length of the contexts. Regardless of the measure used, the key piece of information for first-similarity scores is the number of shared or overlapping words. These methods all treat the contexts as "bags of words" and do not consider the position of words when finding matches. This type of matching has been extended in various measures of first-order similarity by giving extra credit for matches that are longer than one word (e.g., BIB003 ,  ). This is based on the premise that matches of more than one word are significantly rarer and more informative than just one word matches. First-order similarity can also be measured using the vector space model. Each word in a collection of contexts is treated as a feature, and each context is represented by a vector that shows which of these features occur within it. Feature values can be binary and indicate if the feature occurs or not, or the frequency of the feature in the context can be shown. Then, two contexts that share words in common will both have non-zero values for their associated features in the vector space model. Once these vectors are constructed the similarity between pairs of contexts can be measured using the cosine measure, and clusters of contexts can be formed based on these scores if desired. While there are many possible clustering algorithms, in general they all rely on similarity scores like the cosine to determine which contexts are most like each other and belong in the same cluster, and which should be separated into different clusters. First-order similarity can be effective for longer contexts and full length documents, especially when the objective is to make broad topic level distinctions. In general for longer texts there will be some number of shared words, however, lack of consistent vocabulary and variations in lexical choice can still be a problem. First-order methods can also perform well with short contexts; however this requires that the vocabulary be somewhat regular or standardized, as would be the case with abstracts of technical articles, or weather and stock market reports. For many other short contexts even slight variations in terminology and lexical choice can leave little or no information for such methods. A further complication with short contexts is that similar contexts may not be of similar lengths. A Question Answering or Intelligent Tutoring system must determine if a response to a question is relevant, and in general questions and answers can be of very different lengths. This is similar to the problem of passage retrieval, where the goal is to identify a passage of text that is similar to or satisfies a user query. Both the query and the passages to be retrieved are kinds of short contexts, they are just of different length and structure. The query terms represent an extremely short context, especially since a user is not likely to specify all the possible variations of their query. For example a user may mention oil but not petroleum in a query. This may be addressed via Query Expansion  , which automatically adds related and synonymous words to a query, so that it has a better chance of finding matches. In the case of (12) and (13), visited could be expanded to went (and vice versa) on the basis of synonym or near-synonym entries in a dictionary or other lexical resource. If this expansion was made, then these two contexts would match exactly despite differences in word order and lexical choice. While hand-crafted resources such as dictionaries and thesauruses are invaluable for these operations, they may lack coverage and not scale to new domains or languages. As a result there is a long history of work in automatically creating thesauruses by clustering words from large corpora (e.g., BIB001 , BIB002 ). Beyond expanding words in the context, it may be possible to increase the effectiveness of first-order similarity matching by augmenting a context with related text (assuming that such texts can be identified, since this is in fact an instance of our original problem of measuring the similarity of contexts). One method of augmentation is found in the Adapted Lesk Measure  , which measures first-order similarity between definitions of concepts found in WordNet to measure their relatedness. Dictionary definitions tend to be very short and are often hard to match since they contain few shared words. However, the Adapted Lesk Measure overcomes this by utilizing the networked structure of WordNet so that a definition is augmented to include other definitions that are directly linked via a WordNet relation (is-a, is-a-part-of,  etc. ). This increases the size of the contexts considerably, and improves the chances of finding direct first-order matches. Finally, another possible enhancement to first-order similarity is to loosen the matching criteria, and allow for fuzzy or partial matches. This can be achieved by matching n-character sequences rather than entire words, or using edit distances, where words that only differ by a few edit operations are considered similar. For example, industry and industrial would not match directly, but industrial can be transformed via three edit operations into industry (remove the a and the l and change the final i to y). Edit distance can be problematic however, in that there are many words that differ by just a few edit operations and yet have completely different meanings (e.g., cat and hat, abduction and deduction, etc.) It might be more reliable to stem the words in the contexts to reduce them to their morphological base forms (e.g., reducing digging, digs, and dug to the stem dig). However, stemmers are language dependent and may suffer from limitations in coverage especially for certain domains, and they may simply not be available for many languages. First-order similarity is a reasonable option for many kinds of texts, although it has limitations for short contexts since there are often few shared words. This can be addressed by stemming the contexts, expanding words with synonyms or other related words, augmenting the contexts with additional related texts, or by employing fuzzy matching techniques. However, stemming is a language and domain dependent operation, query expansion requires some knowledge of the intended sense of a word (e.g., if bank is the query term, should it be expanded to shore or credit union?), context augmentation requires the ability to identify similar contexts in the first place, and fuzzy matching can sometimes be too generous and introduces false similarities. First-order similarity measures might best be viewed as appropriate for applications where identifying direct matches is a priority, as would be the case in plagiarism detection. However, in many other cases direct matching is simply too restrictive and is unable to detect many more subtle instances of similarity. First-order methods will not suffer from many false positives; if two contexts share many words then they are likely similar. However, there will be many false negatives. Many short contexts that are similar do not share many words, but first-order methods will not detect this.