{'fraction_non_alphanumeric': 0.03523343241825494, 'fraction_numerical': 0.014294457072914846, 'mean_word_length': 4.885515821970672, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 6, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Using Web-Search Results to Measure Word-Group Similarity

Semantic relatedness between words is important to many NLP tasks, and numerous measures exist which use a variety of resources. Thus far, such work is confined to measuring similarity between two words (or two texts), and only a handful utilize the web as a corpus. This paper introduces a distributional similarity measure which uses internet search counts and also extends to calculating the similarity within word-groups. The evaluation results are encouraging: for word-pairs, the correlations with human judgments are comparable with state-of-the-art web-search page-count heuristics. When used to measure similarities within sets of 10 words, the results correlate highly (up to 0.8) with those expected. Relatively little comparison has been made between the results of different search-engines. Here, we compare experimental results from Google, Windows Live Search and Yahoo and find noticeable differences.


Introduction
The propensity of words to appear together in texts, also known as their distributional similarity is an important part of Natural Language Processing (NLP): 'The need to determine semantic related-ness… between two lexically expressed concepts is a problem that pervades much of [NLP].' (Budanitsky and Hirst 2006) Such requirements are evident in word sense disambiguation (WSD) (Patwardhan et-al 2003), spelling correction (Budanitsky and Hirst 2006) and Lexical Chaining (Morris and Hirst 1991). As well as measuring the co-occurrence of word-pairs, it is also considered useful to extend these measures to calculate the likelihood of sets of words to appear together. For example, Caracciolo et-al (2004) evaluate two established topic area detection (TAD) algorithms and indicate text homogeneity as a document feature affecting the results. Furthermore, Gliozzo et-al (2004) and McCarthy et-al (2007) highlight the importance of topic features for WSD and Navigli and Velardi (2005) report differing WSD results for 3 types of text: unfocussed, mid-technical (eg finance articles) and overly technical (eg interoperability and computer networks). Measures of word-group similarity can be used to calculate the level of topic cohesion in texts, and the potential for this to be used to benefit NLP areas such as WSD and TAD has been indicated in Gledson and Keane (2008).
We consider web-searching an important part of measuring similarity, as it provides up-to-date information on word co-occurrence frequencies in the largest available collection of English language documents. We propose a simple measure that uses internet search counts by measuring the decline in the number of hits as more words (from the word-set to be measured) are appended to a query string using the 'AND' operator. To offset against the effect of individual word hitcounts, the above gradient is compared to that of the individual word hit counts -arranged in descending order of hits returned.
The paper is structured as follows: in Section 2 we describe related work in the areas of word similarity and the use of search-engine counts in NLP. Section 3 outlines the algorithm to be used for our similarity measure which can utilise any search-engine that is web-service enabled. Sec-tion 4 describes and discusses the results of the evaluation techniques used, one for evaluating word-pair similarities, which compares with previous work and human judgements, and three for evaluating word-group similarities. Section 5 outlines the conclusions drawn from these experiments and Section 6 discusses further work.

Related Work
The most commonly used similarity measures are based on the WordNet lexical database (eg Budanitsky andHirst 2006, Hughes andRamage 2007) and a number of such measures have been made publicly available (Pedersen et-al 2004).
The problem with such methods is that they are confined to measuring words in terms of the lexical connections manually assigned to them. Language is evolving continuously and the continual maintenance and updating of such databases is highly labour intensive, therefore, such lexical resources can never be fully up-to-date. In addition, the lexical connections made between words and concepts do not cover all possible relations between words. An important relationship between words is distributional similarity and Budanitsky and Hirst (2006) conclude that the capture of these 'non-classical' relationships is an important area of future research. Weeds and Weir (2006) use a 'co-occurrence retrieval method to compute word relatedness, which is described as analogous to the precision and recall metrics of document retrieval. They observe the 'plausibility' of substituting word-1 for word-2 within verb/object-noun grammatical relationships. This method is restricted to document retrieval from the BNC corpus, due to the pre-requisite that words are part-of-speech tagged and that some grammatical parsing is performed. The similarity measure that we have developed is simpler and does not rely on preprocessing of texts. This distributional similarity measure calculates the propensity of words to appear together, regardless of part-of-speech or grammatical functions.
We assert that the world-wide-web can be used to capture distributional similarity, and is less likely to suffer from problems of coverage, found in smaller corpora. The web as a corpus has been successfully used for many areas in NLP (Kilgarriff and Grefenstette 2003) such as WSD (Mihalcea and Moldovan 1999), obtaining frequencies for bigrams (Keller and Lapata 2003) and noun compound bracketing (Nakov and Hearst 2005). Such reliance on web search-engine results does come with caveats, the most important (in this context) being that the reported hit counts may not be entirely trustworthy (Kilgarriff 2007). Strube and Ponzetto's (2006) use the Wikipedia database, which includes a taxonomy of categories, and they adapt 'well established semantic relatedness measures originally developed for WordNet'. They achieve a correlation coefficient of 0.48 with human judgments, which is stated as being higher than a Google-only and WordNetonly based measure for the largest of their test datasets (the 353 word-pairs of 353-TC) Chen et-al (2006) use the snippet's returned from web-searches, in order to perform word similarity measurement that captures 'new usages' of ever evolving, 'live' languages. A double checking model is utilized which combines the number of occurrences of the first word in the snippets of the second word, and vice-versa. This work achieves a correlation coefficient of 0.85 with the Miller and Charles (1998) dataset of 28 word-pairs, but to achieve the best results, 600-700 snippets are required for each word-pair, requiring extra text-processing and searching.
The work most similar to ours is the set of page-counting techniques of Bollegala et-al (2007). They combine the use of web-search page-counts with the analysis of the returned text snippets and achieve impressive correlations with human judgment (0.834 with the Miller and Charles dataset). The text-snippet analysis is more complex than that of Chen et-al (2006), as the optimal number of snippets is over 1000, and their process involves complex pattern matching, which may not scale well to measuring wordgroups similarity. Their page counting heuristics utilize 4 popular co-occurrence methods: Jaccard, Overlap (Simpson), Dice and PMI (Pointwise mutual information) but again, these techniques are not designed to scale up to larger numbers of input words. Mihalcea et-al (2006) and Gabrilovich and Markovitch (2007) achieve good results when comparing texts, the former utilizing the inversedocument frequency heuristic and the latter indexing the entire Wikipedia database and comparing vector representations of the two inputs.
None of the above work is adapted to be used on single groups of words as a measure of topic cohesion. They could be adapted by combining similarity results between many pairs, but this might similarly have a high computational cost. In addition, no comparisons of different websearch engines are made when using web-counts.
As the use of web-counts is precarious (Kigarriff 2007), these types of comparisons are of high practical value.

Similarity Measure
The proposed measure can be used with any web-service enabled search-engine and in our experiments we compare three such searchengines: Yahoo [Yahoo], Windows Live Search [Live-Search] and Google [Google]. The similarity measure WebSim [search-engine] is calculated for each document d as follows: Step 1: Add the required set of n lemmas to the Lemmas list.
Step 2: Using an internet search-engine, obtain the hit counts of each member of Lemmas.
Step 3: Order the resulting list of n lemma/hitcounts combinations in descending order of hitcounts and save lemma/hit combinations to In-divHitsDesc.
Step 4: For each lemma of IndivHitsDesc, save to CombiHitsDesc preserving the ordering.
Step 5: For each member of CombiHitsDesc: CombiHitsDesci, obtain the hit counts of the associated lemma, along with the concatenated lemmas of all preceding list members of Combi-HitsDesc (CombiHitsDesc[0] to CombiHits-Desc[i-1]). This list of lemmas are concatenated together using ' AND ' as the delimiter.
Step 6: Calculate the gradients of the best-fit lines for the hit-counts of IndivHitsDesc and CombiHitsDesc: creating gradIndiv and grad-Combi respectively.
As WebSim [search-engine] is taken as the difference between the two descending gradients, the measure is more likely to reveal the affects of the probability of the set of lemmas co-occurring in the same documents, rather than by influences such as duplicate documents. If the decline in hitcounts from IndivHitsDesc[i-1] to IndivHits-Desc[i] is high, then the decline in the number of hits from CombiHitsDesc[i-1] to CombiHits-Desc[i] is also expected to be higher, and the converse, for lower drops is also expected. Deviations from these expectations are reflected in the final homogeneity measure and are assumed to be caused by the likelihood of lemmas cooccurring together in internet texts.
Search-engines are required that publish a set of web-services for a fully automated process. The Google, Yahoo and Windows Live Search search-engines have been selected and the results of each measure are compared. In response to important problems highlighted by Kilgarriff (2007) relating to the use of web counts in NLP experiments: firstly, a measure is proposed between words that does not require the preannotation of part-of-speech information and does not rely on query syntax / meta-language. Secondly, our measure relies on the use of websearch page counts (as opposed to word instance counts) as we are measuring the likelihood of cooccurrence in the same text. Finally, measures are taken to try to avoid the problem of arbitrary search-engine counts. For example, each measure is the result of a comparison between the decline rates of 2 sets of hit counts and the full set of queries for each input text are taken within a 20 second interval (for groups of 10 words). In addition, for the Google and Yahoo measures the web-service request parameter includes options to avoid the return of the same web-page (Google: 'filter_alike_results'; Yahoo: 'Al-lowSimilar').

Evaluation
Four methods of evaluation are used to verify that the similarity measure is capable of measuring similarity between words. These methods are selected to be as varied as possible, to provide a fuller understanding of the usefulness of our technique and to verify that it is working as expected.

Word-pairs
The results of Rubenstein and Goodenough (1965) (65 word-pairs), Miller and Charles (1998) (30 word-pair subset of Rubenstein and Goodenough 1965) and Finkelstein et-al (2002) (353 word-pairs) are used to evaluate the ability of the proposed method to calculate the similarity between word-pairs. These results sets list the similarity scores of the word-pairs as assigned by humans. Although this does provide a useful benchmark, extremely high, or perfect correlations are unrealistic, as those involved in the experiments were asked to think about the words association in terms of lexical relations such as synonymy as opposed to the broader idea of distributional similarity. Nevertheless, in conjunction with other evaluation techniques, these comparisons can still be useful, as some correlation would be expected if our measure was functioning as required.

Word-groups
In order to indicate whether the proposed measure is capable of measuring similarity amongst a set of words, a broad range of evaluation methods is required. No human evaluations exist, and to produce such a data-set would be difficult due to the larger quantity of data to evaluate. The following three methods are used:

Manual Selection of Word-groups
The manual selection of word-groups, for testing the proposed measure is an important part of its evaluation as it is possible to construct word-sets of varying similarity, so that expected results can be predicted and then compared with actual results. In addition, the datasets created can be easily manipulated to range from highly homogenous / similar sets of words to extremely heterogeneous -where words are highly unlikely to appear together. The latter is achieved by systematically merging the groups together, until a complete mixture of words from different wordsets is produced.
The method used to compile the words groups is as follows: firstly, groups of words with a known propensity to appear together were selected by browsing popular internet web-sites (see Table 4 for the words contained in each set). Secondly for each of these original sets, a series of 5 measures is taken, the first with all words from the original set (to illustrate, this might be represented as AAAAAAAAAA -where each letter represent a word from the set shown), this therefore is the most homogeneous group. Then two words from this set are replaced with two from a new set (eg B) (AAAAAAAABB). Then a further two words (again originally from set A) are replaced with two more words from another new set (eg from Set C) (AAAAAABBCC), and so on, until the final set of 10 words to be measured consists of 5 pairs of words, each from 5 different sets (AABBCCDDEE). These steps were first performed for sets A, B, C, D and E and then for sets F, G, H, J and K respectively. The results were compared (using Pearson's correlation) against the expected results. For example: AAAAAAAAAA = 10 points, AAAAAAAABB = 8 points, AAAAAABBCC = 6 points, AAAABBCCDD = 4 points and AABBCCDDEE = 2 points.
On the whole, the word-groups contained in each of these two sets of sets are considered to be heterogeneous (eg A is dissimilar to B, C, D and E etc). To introduce more 'blurring' of these categories, a third set of sets was measured, consisting of the word-sets A, D, H, M and N. It was considered more conceivable that the words in these sets could be found in the same documents. The expected results for this set of measures were modified slightly to become: AAAAAAAAAA = 8 points, AAAAAAAABB = 7 points, AAAAAABBCC = 6 points, AAAABBCCDD = 5 points and AABBCCDDEE = 4 points. This was done to reflect the fact that the differences between the highest and lowest were expected to be less. -.80** -.68** WebSim [LIVE-SEARCH] -.65** -.57** WebSim [GOOGLE] -.70** -.64** **Significant at the .01 level (2-tailed) Table 5: Correlation with expected scores for manually selected sets As illustrated in Table 5, the 'Heterogeneous Sets' group similarity scores were found to correlate very highly with those expected, with the WebSim [YAHOO] measure achieving .80. The Web-Sim [GOOGLE] measure was also found to improve when tested on groups of words.

Correlation (Pearson's R)
The measures were found to perform less well when the third set of word-sets, containing more closely related members, was introduced (Table  5, final column). This indicates that the measures are better at distinguishing between highly homogeneous and highly heterogeneous word-sets, but appear less proficient at distinguishing between word-sets with moderate levels of topic homogeneity.

WordNet::Domains Selection of Word-groups
The WordNet Domains package 2 (Magnini and Cavaglia 2000) assigns domains to each sense of the WordNet electronic dictionary. Therefore, for each domain a relevant list of words can be extracted. The domains are arranged hierarchically, allowing sets of words with a varied degree of topic homogeneity to be selected. For example, for a highly heterogeneous set, 10 words can be selected from any domain, including factotum (level-0: the non-topic related category). For a slightly less heterogeneous set, words might be selected randomly from a level-1 category (eg 'Applied_Science'), and any of the categories it subsumes (eg Agriculture, Architecture, Buildings etc). The levels range from level-0 (factotum) to level-4; we merge levels 3 and 4 as level-4 domains are relatively few and are viewed as similar to level-3. This combined set is henceforth known as level-3.

Measure
Correlation (Pearson's R) All Extreme Only WebSim [YAHOO] -0.46** -0.80** WebSim [LIVE-SEARCH] -0.06 -0.23** WebSim [GOOGLE] -0.42** -0.71** **Significant at the .01 level (2-tailed) For our experiments, we collected 2 random samples of 10 words for every WordNet domain (167 domains) and then increased the number of sets from level-0 to level-2 domains, to make the number of sets from each level more similar. The final level counts are: levels 0 to 2 have 100 word-sets each and level 3 has 192 word-sets. The word-sets contain 10 words each. We then assign an expected score to each set, equal to its domain level. Table 6 displays the resulting correlation between the WebSim scores and the expected scores (column: 'All'). In the previous section, we observed that the measures are less competent at distinguishing between moderate levels of homogeneity, and the WordNet::Domain test sets contain many sets which could be described as having moderate homogeneity. To further test this, we repeated the above WordNet::Domain tests, but included only those sets of level-0 and level-3. The results displayed in the final column of Table 6 and provide further evidence that this might be the case, as the correlations are significantly higher for these more extreme test sets.

SENSEVAL 2 & 3 Data
The selection of the most frequent words from natural language documents is another important part of our evaluation, as it is representative of real-world data-sets. As it is anticipated that our results could be of use for WSD, we opted to measure the topic homogeneity of a publicly available set of documents from a well established WSD competition. The documents of the SENSEVAL 2 & 3 3 English all-words WSD task were divided into 73 sub-documents, each containing approximately 50 content-words. The stop-words and non-topical 4 content words of each sub-document were then removed and the remaining words lemmatised and aggregated by lemma. This list of lemmas was then arranged in descending order of the number of occurrences in the sub-document. The top-10 most frequent lemmas were selected as input to the similarity measure. The results for each set along with descriptions of the documents used are displayed in Table 7.
The scientific documents (d01) could be viewed as the most homogeneous, with the earthquake accounts (d002) and the work of fiction (d000) being considered the most heterogeneous. With this in mind, it is evident in Table 7 that the WebSim [MSN] measure performed the least well and other two methods performed as expected, and with identical rankings.
Further analysis is required to compare these results with the WSD results for the same Text Description Average WebSim [YAHOO] Average WebSim [GOOGLE] Average WebSim [MSN] d00   Gledson and Keane (2008), and this is highlighted as part of the further work.

Conclusions
We proposed a simple web-based similarity measure which relies on page-counts only, can be utilized to measure the similarity of entire sets of words in addition to word-pairs and can use any web-service enabled search engine. When used to measure similarities between two words, our technique is comparable with other state-ofthe art web-search page-counting techniques (and outperforms most). The measure is found to correlate to a moderate level (the highest being .60 correlation) with human judgments. When used to measure similarities between sets of 10 words, the results are similarly encouraging and show the expected variations for word-groups with different levels of homogeneity. Where wordgroups are manually created, with known expectations of the similarities between each word-set, correlations with these expected results are as high as .80. Noticeable differences between the performances of each of the 3 search-engines, for each evaluation method, are evident. Google performs poorly for the word-pair similarity measures and Yahoo and Live Search both perform substantially better. For the word-set comparisons, Google performance improves (perhaps as the erratic single counts are stabilised as larger sets of words are used), but Yahoo is again superior and MSN performs much less well. Overall, our results indicate that the Yahoo measure is the most consistent and reliable.

Further Work
The group similarity measure calculates the propensity of words to co-occur with one-another, which can be described as a measure of the topic homogeneity of the set of input words. Gledson and Keane (2008) propose the use of further measures of topic homogeneity using a variety of available resources. These measures are compared with the results of WSD approaches reliant on topic features and low to moderate correlations are found to exist. It is also proposed that useful correlations with other NLP techniques utilising topical features (such as TAD and Malapropism Detection) might also exist. The word-group similarity measures performed better for extreme levels of topic homogeneity. The measures must be improved to enable them to distinguish between moderate homogeneity levels. This may be achieved by combining our simple measure with other word similarity/relatedness techniques such as the use of WordNet Domains, or Lexical Chaining.
It is expected that polysemy counts of words influence the outcome of these experiments, especially for the word-pairs which have less data and are more susceptible to erratic counts. Results might be improved by measuring and offsetting these effects.
In addition, an upper limit of word-set cardinality should be determined, which is the maximum number of input words that can be measured. Further testing is necessary using a range of set cardinalities, to obtain optimal values.