arbitrariness: one design feature of human language, which refers to the face that the forms of linguistic signs bear no natural relationship to their meaning. duality: one design feature of human language, which refers to the property of having two levels of are composed of elements of the secondary level and each of the two levels has its own principles of organization.Creativity (productivity, open-endedness): language-uses can manipulate their linguistic resources to produce new expressions and new sentences. Productive refers to the ability to construct and understand an indefinitely large of number of sentences in one’s native language, including, those that he has never heard before, but that are appropriate the speaking situation. Displacement: one design feature of human language, which means human language enable their users to symbolize objects, events and concepts which are not present in time and space, at the moment of communication.Cultural transmission: the details of language system are not genetically transmitted, but instead have to be taught and learned. 文化传递性，语言不是靠遗传，而是靠教与学来传递的。
DRAFT!c January7,1999Christopher Manning&Hinrich Schütze.1415CollocationsA C O L L O C A T I O N is an expression consisting of two or more words thatcorrespond to some conventional way of saying things.Or in the wordsof Firth(1957:181):“Collocations of a given word are statements of thehabitual or customary places of that word.”Collocations include nounphrases like strong tea and weapons of mass destruction,phrasal verbs liketo make up,and other stock phrases like the rich and powerful.Particularlyinteresting are the subtle and not-easily-explainable patterns of word usagethat native speakers all know:why we say a stiff breeze but not??a stiff wind(while either a strong breeze or a strong wind is okay),or why we speak ofbroad daylight(but not?bright daylight or??narrow darkness).Collocations are characterized by limited compositionality.We call a nat-COMPOSITIONALITYural language expression compositional if the meaning of the expressioncan be predicted from the meaning of the parts.Collocations are not fullycompositional in that there is usually an element of meaning added to thecombination.In the case of strong tea,strong has acquired the meaningrich in some active agent which is closely related,but slightly different fromthe basic sense having great physical strength.Idioms are the most extremeexamples of non-compositionality.Idioms like to kick the bucket or to hearit through the grapevine only have an indirect historical relationship to themeanings of the parts of the expression.We are not talking about bucketsor grapevines literally when we use these idioms.Most collocations exhibitmilder forms of non-compositionality,like the expression international bestpractice that we used as an example earlier in this book.It is very nearly asystematic composition of its parts,but still has an element of added mean-ing.It usually refers to administrative efficiency and would,for example,not be used to describe a cooking technique although that meaning wouldbe compatible with its literal meaning.There is considerable overlap between the concept of collocation and no-tions like term,technical term,and terminological phrase.As these names sug-TERMTECHNICAL TERMTERMINOLOGICAL PHRASE1425Collocationsgest,the latter three are commonly used when collocations are extractedfrom technical domains(in a process called terminology extraction).The TERMINOLOGY EXTRACTIONreader be warned,though,that the word term has a different meaning ininformation retrieval.There,it refers to both words and phrases.So itsubsumes the more narrow meaning that we will use in this chapter.Collocations are important for a number of applications:natural lan-guage generation(to make sure that the output sounds natural and mis-takes like powerful tea or to take a decision are avoided),computational lexi-cography(to automatically identify the important collocations to be listedin a dictionary entry),parsing(so that preference can be given to parseswith natural collocations),and corpus linguistic research(for instance,thestudy of social phenomena like the reinforcement of cultural stereotypesthrough language(Stubbs1996)).There is much interest in collocations partly because this is an area thathas been neglected in structural linguistic traditions that follow Saussureand Chomsky.There is,however,a tradition in British linguistics,associ-ated with the names of Firth,Halliday,and Sinclair,which pays close at-tention to phenomena like collocations.Structural linguistics concentrateson general abstractions about the properties of phrases and sentences.Incontrast,Firth’s Contextual Theory of Meaning emphasizes the importanceof context:the context of the social setting(as opposed to the idealizedspeaker),the context of spoken and textual discourse(as opposed to theisolated sentence),and,important for collocations,the context of surround-ing words(hence Firth’s famous dictum that a word is characterized by thecompany it keeps).These contextual features easily get lost in the abstracttreatment that is typical of structural linguistics.A good example of the type of problem that is seen as important in thiscontextual view of language is Halliday’s example of strong vs.power-ful tea(Halliday1966:150).It is a convention in English to talk aboutstrong tea,not powerful tea,although any speaker of English would alsounderstand the latter unconventional expression.Arguably,there are nointeresting structural properties of English that can be gleaned from thiscontrast.However,the contrast may tell us something interesting aboutattitudes towards different types of substances in our culture(why do weuse powerful for drugs like heroin,but not for cigarettes,tea and coffee?)and it is obviously important to teach this contrast to students who wantto learn idiomatically correct English.Social implications of language useand language teaching are just the type of problem that British linguistsfollowing a Firthian approach are interested in.In this chapter,we will introduce the principal approaches tofinding col-5.1Frequency143locations:selection of collocations by frequency,selection based on mean and variance of the distance between focal word and collocating word,hy-pothesis testing,and mutual information.We will then return to the ques-tion of what a collocation is and discuss in more depth different definitionsthat have been proposed and tests for deciding whether a phrase is a col-location or not.The chapter concludes with further readings and pointersto some of the literature that we were not able to include.The reference corpus we will use in examples in this chapter consistsof four months of the New York Times newswire:from August through November of1990.This corpus has about115megabytes of text and roughly 14million words.Each approach will be applied to this corpus to makecomparison easier.For most of the chapter,the New York Times exampleswill only be drawn fromfixed two-word phrases(or bigrams).It is im-portant to keep in mind,however,that we chose this pool for convenience only.In general,bothfixed and variable word combinations can be colloca-tions.Indeed,the section on mean and variance looks at the more looselyconnected type.5.1FrequencySurely the simplest method forfinding collocations in a text corpus is count-ing.If two words occur together a lot,then that is evidence that they havea special function that is not simply explained as the function that resultsfrom their combination.Predictably,just selecting the most frequently occurring bigrams is not very interesting as is shown in Table5.1.The table shows the bigrams(sequences of two adjacent words)that are most frequent in the corpus andtheir frequency.Except for New York,all the bigrams are pairs of functionwords.There is,however,a very simple heuristic that improves these results alot(Justeson and Katz1995b):pass the candidate phrases through a part-of-speechfilter which only lets through those patterns that are likely to be “phrases”.1Justeson and Katz(1995b:17)suggest the patterns in Table5.2.Each is followed by an example from the text that they use as a test set.Inthese patterns A refers to an adjective,P to a preposition,and N to a noun.Table5.3shows the most highly ranked phrases after applying thefilter.The results are surprisingly good.There are only3bigrams that we wouldnot regard as non-compositional phrases:last year,last week,andfirst time.1445Collocations5.1Frequency145tag pattern1465Collocationsstrongsupport50computers10sales21men8showing18man7message15military6gains13country6criticism13post5feelings11nation5challenges11chip5case11senators4signal9magnet4Table5.4The nouns occurring most often in the patterns“strong”and“pow-erful”.However,searching the larger corpus of the World Wide Web wefind799examples of strong tea and17examples of powerful tea(the latter mostlyin the computational linguistics literature on collocations),which indicatesthat the correct phrase is strong tea.2Justeson and Katz’method of collocation discovery is instructive in thatit demonstrates an important point.A simple quantitative technique(thefrequencyfilter in this case)combined with a small amount of linguisticknowledge(the importance of parts of speech)goes a long way.In therest of this chapter,we will use a stop list that excludes words whose mostfrequent tag is not a verb,noun or adjective.Exercise5-1Add part-of-speech patterns useful for collocation discovery to Table5.2,includingpatterns longer than two tags.5.2Mean and Variance147Sentence:Stocks crash as rescue plan teetersBigrams:stocks crash stocks as stocks rescuecrash as crash rescue crash planas rescue as plan as teetersrescue plan rescue teetersplan teeters Figure5.1Using a three word collocational window to capture bigrams at a dis-tance.Exercise5-2Pick a document in which your name occurs(an email,a university transcript or a letter).Does Justeson and Katz’sfilter identify your name as a collocation?Exercise5-3We used the World Wide Web as an auxiliary corpus above because neither stong tea nor powerful tea occurred in the New York Times.Modify Justeson and Katz’s method so that it uses the World Wide Web as a resource of last resort.5.2Mean and VarianceFrequency-based search works well forfixed phrases.But many colloca-tions consist of two words that stand in a moreflexible relationship to one another.Consider the verb knock and one of its most frequent arguments, door.Here are some examples of knocking on or at a door from our corpus: (5.1) a.she knocked on his doorb.they knocked at the doorc.100women knocked on Donaldson’s doord.a man knocked on the metal front doorThe words that appear between knocked and door vary and the distance between the two words is not constant so afixed phrase approach would not work here.But there is enough regularity in the patterns to allow us to determine that knock is the right verb to use in English for this situation, not hit,beat or rap.A short note is in order here on collocations that occur as afixed phraseversus those that are more variable.To simplify matters we only look at fixed phrase collocations in most of this chapter,and usually at just bi-grams.But it is easy to see how to extend techniques applicable to bigrams1485Collocationsto bigrams at a distance.We define a collocational window(usually a win-dow of3to4words on each side of a word),and we enter every word pairin there as a collocational bigram,as in Figure5.1.We then proceed to doour calculations as usual on this larger pool of bigrams.However,the mean and variance based methods described in this sec-tion by definition look at the pattern of varying distance between twowords.If that pattern of distances is relatively predictable,then we haveevidence for a collocation like knock...door that is not necessarily afixedphrase.We will return to this point and a more in-depth discussion of whata collocation is towards the end of this chapter.One way of discovering the relationship between knocked and door is tocompute the mean and variance of the offsets(signed distances)between the MEANVARIANCE two words in the corpus.The mean is simply the average offset.For theexamples in(5.1),we compute the mean offset between knocked and door asfollows:(5.2)where is the number of times the two words co-occur,is the offset forco-occurrence,and is the mean.If the offset is the same in all cases,then the variance is zero.If the offsets are randomly distributed(whichwill be the case for two words which occur together by chance,but not in aparticular relationship),then the variance will be high.As is customary,weuse the standard deviation5.2Mean and Variance149 standard deviation means that the two words usually occur at about the same distance.Zero standard deviation means that the two words always occur at exactly the same distance.We can also explain the information that variance gets at in terms of peaks in the distribution of one word with respect to another.Figure5.2 shows the three cases we are interested in.The distribution of strong with respect to opposition has one clear peak at position(corresponding to the phrase strong opposition).Therefore the variance of strong with respect to opposition is small().The mean of indicates that strong usually occurs at position(disregarding the noise introduced by one occurrence at).We have restricted positions under consideration to a window of size 9centered around the word of interest.This is because collocations are essentially a local phenomenon.Note also that we always get a count of at position when we look at the relationship between two different words. This is because,for example,strong cannot appear in position in contexts in which that position is already occupied by opposition.Moving on to the second diagram in Figure5.2,the distribution of strong with respect to support is drawn out,with several negative positions having large counts.For example,the count of approximately20at position is due to uses like strong leftist support and strong business support.Because of this greater variability we get a higher()and a mean that is between positions and().Finally,the occurrences of strong with respect to for are more evenly dis-tributed.There is tendency for strong to occur before for(hence the neg-ative mean of),but it can pretty much occur anywhere around for. The high standard deviation of indicates this randomness.This indicates that for and strong don’t form interesting collocations.The word pairs in Table5.5indicate the types of collocations that can be found by this approach.If the mean is close to and the standard deviation low,as is the case for New York,then we have the type of phrase that Justeson and Katz’frequency-based approach will also discover.If the mean is much greater than,then a low standard deviation indicates an interesting phrase.The pair previous/games(distance2)corresponds to phrases like in the previous10games or in the previous15games;minus/points corresponds to phrases like minus2percentage points,minus3percentage points etc;hundreds/dollars corresponds to hundreds of billions of dollars and hundreds of millions of dollars.High standard deviation indicates that the two words of the pair stand in no interesting relationship as demonstrated by the four high-variance1505Collocations frequencyof strong50-4-3-2-101234Position of strong with respect to opposition().frequencyof strong50-4-3-2-101234Position of strong with respect to support().frequencyof strong50-4-3-2-101234Position of strong with respect to for().5.2Mean and Variance151Count Word2Newpreviousminushundreds4.030.4436Atlanta4.030.0078New3.960.19119hundredth3.960.29106bystrongpowerfulRichardGarrison1525Collocationsof words that are in a looser relationship thanfixed phrases and that arevariable with respect to intervening material and relative position.5.3Hypothesis TestingOne difficulty that we have glossed over so far is that high frequency andlow variance can be accidental.If the two constituent words of a frequentbigram like new companies are frequently occurring words(as new and com-panies are),then we expect the two words to co-occur a lot just by chance,even if they do not form a collocation.What we really want to know is whether two words occur together moreoften than chance.Assessing whether or not something is a chance eventis one of the classical problems of statistics.It is usually couched in termsof hypothesis testing.We formulate a null hypothesis that there is no NULL HYPOTHESISassociation between the words beyond chance occurrences,compute theprobability that the event would occur if were true,and then rejectif is too low(typically if beneath a significance level of,, SIGNIFICANCE LEVEL,or)and retain as possible otherwise.3It is important to note that this is a mode of data analysis where we lookat two things at the same time.As before,we are looking for particularpatterns in the data.But we are also taking into account how much datawe have seen.Even if there is a remarkable pattern,we will discount it ifwe haven’t seen enough data to be certain that it couldn’t be due to chance.How can we apply the methodology of hypothesis testing to the problemoffinding collocations?Wefirst need to formulate a null hypothesis whichstates what should be true if two words do not form a collocation.For sucha free combination of two words we will assume that each of the wordsand is generated completely independently of the other,and so theirchance of coming together is simply given by:The model implies that the probability of co-occurrence is just the productof the probabilities of the individual words.As we discuss at the end ofthis section,this is a rather simplistic model,and not empirically accurate,but for now we adopt independence as our null hypothesis.5.3Hypothesis Testing1535.3.1The testNext we need a statistical test that tells us how probable or improbable it isthat a certain constellation will occur.A test that has been widely used forcollocation discovery is the test.The test looks at the mean and varianceof a sample of measurements,where the null hypothesis is that the sampleis drawn from a distribution with mean.The test looks at the differencebetween the observed and expected means,scaled by the variance of thedata,and tells us how likely one is to get a sample of that mean and vari-ance(or a more extreme mean and variance)assuming that the sample isdrawn from a normal distribution with mean.To determine the proba-bility of getting our sample(or a more extreme sample),we compute thestatistic:If you look up the value of that corresponds to a confidence level of ,you willfind.4Since the we got is larger than, we can reject the null hypothesis with99.5%confidence.So we can saythat the sample is not drawn from a population with mean158cm,and ourprobability of error is less than0.5%.To see how to use the test forfinding collocations,let us compute thevalue for new companies.What is the sample that we are measuring the1545Collocationsmean and variance of?There is a standard way of extending the testfor use with proportions or counts.We think of the text corpus as a longsequence of bigrams,and the samples are then indicator random vari-ables that take on the value1when the bigram of interest occurs,and are0otherwise.Using maximum likelihood estimates,we can compute the probabilitiesof new and companies as follows.In our corpus,new occurs15,828times,companies4,675times,and there are14,307,668tokens overall.newThe null hypothesis is that occurrences of new and companies are indepen-dent.new companies new companiesIf the null hypothesis is true,then the process of randomly generating bi-grams of words and assigning1to the outcome new companies and0to anyother outcome is in effect a Bernoulli trial with for theprobability of new company turning up.The mean for this distribution isand the variance is(see Section2.1.9),whichis approximately.The approximation holds since formost bigrams is small.It turns out that there are actually8occurrences of new companies amongthe14307668bigrams in our corpus.So,for the sample,we have that thesample mean is:5.3Hypothesis Testing1552.32.21.3p1.20.8 Table5.6Finding collocations:The test applied to10bigrams that occur withfrequency20.Table5.6shows values for ten bigrams that occur exactly20times in thecorpus.For the topfive bigrams,we can reject the null hypothesis that thecomponent words occur independently for,so these are goodcandidates for collocations.The bottomfive bigrams fail the test for signif-icance,so we will not regard them as good candidates for collocations.Note that a frequency-based method would not be able to rank the tenbigrams since they occur with exactly the same frequency.Looking at thecounts in Table5.6,we can see that the test takes into account the numberof co-occurrences of the bigram()relative to the frequencies of thecomponent words.If a high proportion of the occurrences of both words(Ayatollah Ruhollah,videocassette recorder)or at least a very high proportionof the occurrences of one of the words(unsalted)occurs in the bigram,thenits value is high.This criterion makes intuitive sense.Unlike most of this chapter,the analysis in Table5.6includes some stopwords–without stop words,it is actually hard tofind examples that failsignificance.It turns out that most bigrams attested in a corpus occur sig-nificantly more often than chance.For824out of the831bigrams thatoccurred20times in our corpus the null hypothesis of independence canbe rejected.But we would only classify a fraction as true collocations.Thereason for this surprisingly high proportion of possibly dependent bigrams(1565CollocationsThe test and other statistical tests are most useful as a method for rankingcollocations.The level of significance itself is less useful.In fact,in mostpublications that we cite in this chapter,the level of significance is neverlooked at.All that is used is the scores and the resulting ranking.5.3.2Hypothesis testing of differencesThe test can also be used for a slightly different collocation discoveryproblem:tofind words whose co-occurrence patterns best distinguish be-tween two words.For example,in computational lexicography we maywant tofind the words that best differentiate the meanings of strong andpowerful.This use of the test was suggested by Church and Hanks(1989).Table5.7shows the ten words that occur most significantly more often withpowerful than with strong(first ten words)and most significantly more of-ten with strong than with powerful(second set of ten words).The scores are computed using the following extension of the test tothe comparison of the means of two normal populations:(5.4)Here the null hypothesis is that the average difference is(),so wehaveW e5.3Hypothesis Testing157strong)powerful)word4.690498622safety7.0710*******support6.32573616587enough4.58253741210sales4.024********opposition3.9000802181showing3.90001641181sense3.74162501140defense3.6055851130gains3.6055832130criticismTable5.7Words that occur significantly more often with powerful(thefirst ten words)and strong(the last ten words).where is the number of times occurs in the corpus.The application suggested by Church and Hanks(1989)for this form of the test was lexicography.The data in Table5.7are useful to a lexicogra-pher who wants to write precise dictionary entries that bring out the differ-ence between strong and powerful.Based on significant collocates,Church and Hanks analyze the difference as a matter of intrinsic vs.extrinsic qual-ity.For example,strong support from a demographic group means that the group is very committed to the cause in question,but the group may not have any power.So strong describes an intrinsic quality.Conversely,a pow-erful supporter is somebody who actually has the power to move things. Many of the collocates we found in our corpus support Church and Hanks’analysis.But there is more complexity to the difference in meaning be-tween the two words since what is extrinsic and intrinsic can depend on subtle matters like cultural attitudes.For example,we talk about strong tea1585Collocationscompanies(new companies)(e.g.,old companies)1582014287181(5.6)where ranges over rows of the table,ranges over columns,is the5.3Hypothesis Testing159 observed value for cell and is the expected value.One can show that the quantity is asymptotically distributed.In other words,if the numbers are large,then has a distribution.We will return to the issue of how good this approximation is later.The expected frequencies are computed from the marginal probabili-ties,that is from the totals of the rows and columns converted into propor-tions.For example,the expected frequency for cell(new companies) would be the marginal probability of new occurring as thefirst part of a bi-gram times the marginal probability of companies occurring as the second part of a bigram(multiplied by the number of bigrams in the corpus): That is,if new and companies occurred completely independently of each other we would expect occurrences of new companies on average for a text of the size of our corpus.The test can be applied to tables of any size,but it has a simpler form for2-by-2tables:(see Exercise5-9)Looking up the distribution in the appendix,wefind that at a probabil-ity level of the critical value is.(the statistic has one degree of freedom for a2-by-2table).So we cannot reject the null hypoth-esis that new and companies occur independently of each other.Thus new companies is not a good candidate for a collocation.This result is the same as we got with the statistic.In general,for the problem offinding collocations,the differences between the statistic and the statistic do not seem to be large.For example,the20bigrams with the highest scores in our corpus are also the20bigrams with the highest scores.However,the test is also appropriate for large probabilities,for which the normality assumption of the test fails.This is perhaps the reason that the test has been applied to a wider range of problems in collocation discovery.1605Collocationsvache8570934Table5.9Correspondence of vache and cow in an aligned corpus.By applying thetest to this table one can determine whether vache and cow are translations ofeach other.word150076word35.They actually use a measure they call,which is multiplied by.They do this sincethey are only interested in ranking translation pairs,so that assessment of significance is notimportant.5.3Hypothesis Testing161out of bigrams areout of bigrams areTable5.11How to compute Dunning’s likelihood ratio test.For example,thelikelihood of hypothesis is the product of the last two lines in the rightmostcolumn.Just as application of the test is problematic because of the underlyingnormality assumption,so is application of in cases where the numbersin the2-by-2table are small.Snedecor and Cochran(1989:127)adviseagainst using if the total sample size is smaller than20or if it is between20and40and the expected value in any of the cells is5or less.In general,the test as described here can be inaccurate if expected cell values are small(Read and Cressie1988),a problem we will return to below.5.3.4Likelihood RatiosLikelihood ratios are another approach to hypothesis testing.We will seebelow that they are more appropriate for sparse data than the test.Butthey also have the advantage that the statistic we are computing,a likelihood LIKELIHOOD RATIOratio,is more interpretable than the statistic.It is simply a number thattells us how much more likely one hypothesis is than the other.In applying the likelihood ratio test to collocation discovery,we examinethe following two alternative explanations for the occurrence frequency ofa bigram(Dunning1993):Hypothesis1.Hypothesis2.Hypothesis1is a formalization of independence(the occurrence of isindependent of the previous occurrence of),Hypothesis2is a formaliza-tion of dependence which is good evidence for an interesting collocation.6We use the usual maximum likelihood estimates for,and andwrite,,and for the number of occurrences of,and in。
