Gregory Grefenstette

Estimating the Number of Concepts

Most Natural Language Processing systems have been built around the idea of a word being something found between white spaces and punctuation. This is a normal and efficient way to proceed. Tasks such as Word Sense Disambiguation, Machine Translation, or even indexing rarely go beyond the single word. Language models used in NLP applications are built on the word, with a few multiword expressions taken as exceptions. But future NLP systems will necessarily venture out into the uncharted areas of multiword expressions. The dimensions and the topology of multiword concepts are unknown: Are there hundreds of thousands or tens of millions? Which words participate in multiword concepts and which do not? As the corpus grows, will their number keep on increasing? In this paper, I estimate the number of multiword concepts that are used in English, systematically probing the Web as our corpus.

Introduction

It may seem futile to try to estimate how many concepts 1 there are in a language. Since man can create new concepts at will, one of his conceits as a sentient being, counting concepts can seem as silly as trying to determine how many numbers there are. Everyone knows that one can continue counting forever.

This viewpoint would be held by those who have worked closest with the lexicon. Patrick Hanks, esteemed editor of the Encyclopedic World Dictionary (Hanks & Potter 1971), the Collins Dictionary of the English Language (Hanks et al. 1979), the Oxford English Reference Dictionary (Hanks et al. 1995), among others, has written:

It is impossible to say how many words there are in the English language, because writers and speakers constantly create new terms to suit their purposes. (Hanks 2005: 248) Kenneth Sisam, former Assistant Secretary at OUP, would concur, having written:

I am afraid it is entirely impossible for usor indeed for anyoneto say how many words there are in the English language. It depends on how many compounds etc. are counted and what are admitted as words. In the great Oxford English Dictionary there are said to be roundly 500,000 words defined. I am sorry I cannot be more precise. (Sisam 1930) 2 Indeed, unbridled creativity is one of the hopes that moves civilisation forward, and this creativity finds its expression in new concepts and new uses of language.

But if one cannot bound the number of concepts, one can examine what concepts are in current use, and attempt to count these. I make a first pass on such an estimation here. In doing so, I will make a number of no doubt egregious approximations, many of which will provoke a frustrating mixture of ire and disdain from traditional lexicographers. But at least, I will start the ball rolling.

From words to concepts

The reason why I think such an attempt is needed is to prod computational lexicography and computational linguistics into the new millennium. Until recently, until the computer era, dictionaries and lexicography were essentially a paperbound affair. Each new definition, each described concept, cost space on paper.

A dictionary was constrained by a budget, which limited the number of pages to be printed, which limited the number of words and concepts that could be included. Computational lexicons used for parsing have often been derived from printed dictionaries [START_REF] Guthrie | The Role of Lexicons in Natural Language Processing[END_REF]. Large hand-built computational lexical resources such as WordNet were also inspired by printed dictionaries [START_REF] Miller | Introduction to WordNet: An On-line Lexical Database[END_REF]). 3 Since the priority in dictionaries was to cover as many single words as possible in the limited space given, the decision to include a given multiword expression was problematic, a decision often based on nontransparency of meaning or frequency.

This essentially word-based approach to language led to the development of computational parsers also based on words. Individual words (space-separated tokens) are often ambiguous, both syntactically and semantically. This problem has led to much research in computational linguistics, from part of speech tagging to Word Sense Disambiguation. 4 The standard technique for disambiguating a word is to start with a manually tagged text, each word tagged with its proper part of speech or sense. Then, using standard machine learning techniques, 5 creating a statistical model of the context of each disambiguated word that can be applied to unlabeled text.

All these attempts start from the word to the structure. But I think it is a safe bet that computational linguistics in the 21 st century will work from larger structures than individual words and that these larger structures will no longer be seen as a pain 6 but as the normal structure that is manipulated and modelled by computational linguists.

Bank is an ambiguous word. River bank is not.

Computational lexicographers and linguists of the future will describe oneword or multiword concepts, no longer limited by space requirements. How much work will they have cut out for them? How many concepts will they have to model? We aim to provide the first estimate of this number in the next sections.

Concepts and two-word noun phrases

What is a concept? It has been explained as a mental representation, an abstract object, a cognitive unit of meaning [START_REF] Margolis | The Ontology of Concepts -Abstract Objects or Mental Representations?[END_REF]. Unfortunately, none of these explanations provides an operational definition.

We will start from a simpler definition and state that any noun is a concept. Verbs can also be concepts, of course, but in English, there is an order of magnitude more nouns than verbs. 7 If we find the number of concepts involving just nouns (and adjectives) we should not be very far from a good estimate.

Using the same, possibly faulty, reasoning, we will also ignore any concepts composed of three or more words. One justification for this last simplification of our task is the fact that most terms used in both folksonomies (Bibsonomy, CiteULike, Connotea) and edited thesauri (the Academic Computing Machinery subject listing, the Agriculture Information and Standards ontology, BioLinks, the thesaurus of the European Environment Information and Observation Net-work, and Medical Subject Headings) are composed of one and two-word terms (cf. [START_REF] Good | Term Based Comparison Metrics for Controlled and Uncontrolled Indexing Languages[END_REF].

So if we can estimate the number of two-word phrases in common use, we can get an idea of how many concepts future computational linguists will have to model. 8

A lower bound

Oxford University Press, on its AskOxford website, declares:

The Second Edition of the Oxford English Dictionary contains full entries for 171,476 words in current use, and 47,156 obsolete words. To this may be added around 9,500 derivative words included as subentries. Over half of these words are nouns, about a quarter adjectives, and about a seventh verbs; the rest is made up of interjections, conjunctions, prepositions, suffixes, etc. 9

If we take this number of 90 thousand nouns from OUP, and suppose that each noun corresponds to a concept, our lower bound is 90,000 concepts.

An upper bound

If we take each of the 90,000 nouns and suppose that they can be modified by another noun, e.g. fire engine, or by one of the 50,000 adjectives, then we have 90,000 x 140,000 ≈ 12 billion possibilities.

The question now becomes, between 90,000 and 12 billion, how many twoword terms are in current use?

Methodology

In order to estimate the number of current two-word noun phrases, I will use a list of nouns and adjectives from a downloadable dictionary, and a copy of the index of the Web.

Probing the Web

At Exalead, we crawl and index the Web. We hold 8 billion URLs to Web pages in our index at the moment, corresponding to about 4 billion Web pages crawled and indexed. The other 4 billion URLs are found in these Web pages and have not yet been crawled, but they can be indexed by using the text point-ing to them. 4 billion pages is a subset of the entire Web. The estimates of the number of pages available on the Web run over 50 billion.

If we take this (large) sample of 4 billion pages, we can probe its index and find out which words are found together. The simplest method would be to take all the nouns and all the adjectives of English and to look for all two-word combinations.

To specify what we mean by adjective and noun, we began with the DELA dictionaries (downloaded in October 2008). From this lexicon, we extracted all unique surface forms tagged as nouns and containing only lowercase letters. There are 160,966 such nouns (from aah, aahs, aalii, aaliis, aandblom, aandbloms, aardvark, aardvarks, … through … zymoses, zymosimeter, zymosimeters, zymosis, zymotechnics, zymurgies, zymurgy, zythum. Similarly for adjectives, we find 46,759 adjectives (from abactinal, abandoned, abapical, abased, abatable, abatised, abattoirlike, abaxial, abbatial, … through … zygoneurous, zygophyllaceous, zygose, zygosporic, zygotic, zymogenic, zymologic, zymological, zymolytic, zymotic. If we generated all adjective-noun and noun-noun pairs, we would have over 7.5 billion combinations.

Some combinations appear often on the Web. For example, mad dog appears on over 400,000 Web pages (out of 8 billion). Some never appear. For example, there is no Web page with the phrase abactinal zymosis. 10 If the present paper were to be indexed someday on the Web, we would then find the hithertounknown concept of abactinal zymosis. In this way the formerly nonsensical phrase colorless green ideas, that Noam Chomsky invented for Syntactic Structures in 1957 has found its way onto over 4,000 Web pages in our index. 11 In order to estimate real concepts, whatever that might mean, we decided to only consider two-word combinations that appeared on over 5 different Web pages. This threshold is chosen without any justification whatsoever, except that it would eliminate the indexed version of this article (and the four other articles that would cite the abactinal zymosis example from this text).

From another partial crawl of the Web, we have the word counts of the 2 million most-frequent strings. In that crawl, we find the string the 1.77 billion times, which, in other words, allows us to estimate the total number of English words crawled to be about 100 billion. In this large sample of English there are some of the DELA words that are never found. If we take only those nouns that appear more than 5 times, we are left with 89,257 nouns, from aah, aahs, aalii, aaliis, aardvark, aardvarks, aardwolf, aardwolves, … through … zygote, zygotene, zygotes, zymase, zymogen, zymogens, zymology, zymolysis, zymosis, zymurgy. Similar filtering with the adjective list leaves us with 25,687 adjectives, from abactinal, abandoned, abased, abatable, abaxial, abbatial, abbrevi-ate, abdicable, abdominal, … through … zoophilic, zootechnical, zwitterionic, zygodactyl, zygomatic, zygomorphic, zygomorphous, zygotic, zymolytic, zymotic. We still have the potential pair abactinal zymosis, but now we are down to (89,257 + 25,687) x 89,257, or a little over 10 billion combinations to check.

Most Web search engines will allow you to make up to one query per second without blacklisting your computer. We could test all the possible two-word combinations, but at 1 query per second, it would still take 325 years. To speed things up, we decided to generate random samples of adjective-noun and nounnoun pairings from the attested nouns and adjectives, and to check their frequency in our Exalead online Web index. Here are some examples: enhydra encyclopedists, cylindric chelicerate, radionics convoker, zoophile cognitions, nonrenewal cheerlessness, infidel kyanites, nondrying dormitories, languorous cyclohexanol, sawbones mortars, hedges braais. 12 Over 1 million such pairs were generated, covering 0.01% of the possibilities. Each pair was used as a contiguous query (the two words had to appear next to each other on the same page). Of these million possibilities, about 61,000 were attested in the index of 4 billion Web pages. About 21 thousand appeared on only one page, 8,663 appeared on 2 pages, 4,932 appeared on 3, etc. Table 1 shows a breakdown of the types of pairs found.

Estimate

If we take this sample, and consider those appearing on over 10 Web pages (out of 4 billion) as in common use, then we find 18,396, or about 1.8% of the generated pairs. If we extrapolate this to the entire sample of 10 billion combinations, this leaves us with about 180 million two-word combinations in "common use" on the Web. This is an extremely rough estimate, and probably more of an upperbound than a true estimate of actual two-word noun phrases that are commonly used. But it gives a first idea of the scale that computational lexicography will have to deal with in the future.

Improvements

As anyone can see, even in the small samples of pairs listed, there is much room for improvement.

A number of suggestions for improving the counts follow, revolving around: Language identification, Not ignoring punctuation, Part of Speech tagging, Shallow parsing, Two-word phrases, Proper Name recognition, Ignoring spam, and Starting from the most common words.  Language identification: Some words listed in the DELA English dictionary used here are also common words in other languages. For example, both the words de and ras were listed as nouns in this dictionary, one as a singular and the second as a plural noun. In our simple juxtaposition method, the pair ras de was generated among the million pairs, and it was found on 76,144 Web pages. When the English language filter is turned on (not used in the counts here), this page count descends to 4,000. Using language tags to restrict counts to English pages may reduce the upper bound.  Not ignoring punctuation: The index used to find the counts has removed punctuation, so that if two words are found next to each other with an intervening punctuation mark, these are considered as adjacent. For example, the snippet of text … What are the symptoms of gallstones? People with gallstones don't know they have them until … will match the query gallstones people.  Part of Speech tagging: Similarly part of speech tagging can be used to identify that words such as extracts or mention are being used as verbs rather than nouns, for example in It can decrease swelling, blood pressure and it extracts deposits left in lymph nodes.  Shallow parsing: If the inputs text were correctly chunked into noun phrases and verb phrases, then we would not recognize the phrase training resellers from In the last several years I wrote the training materials and conducted the training resellers must attend to qualify for the …  Two-word phrases: Do not count subphrases appearing in a longer phrase. For example, the partial phrase comfortable beachfront is almost always part of a longer expression: Comfortable beachfront home surrounded by old growth forests …, Stay at a comfortable beachfront hotel …, etc.  Proper Name recognition: We wouldn"t recognize assistants mike from … Assistants Mike Gallizzi, …  Ignoring spam: Spam is prevalent on the Web. Many Web pages exist only to post advertising, and they pilfer their content from elsewhere (newsfeeds, blog entries, Wikipedia). See the next section for more about spam.  Starting from the most common words: Start from the most common words in each language, and build complete pair models for these words. We could also gather all the Web pages for words appearing 1,000 times or less and treat these pages completely, extracting all pairs found for each word. These techniques will lead to better counts, and better approximations, but each has a processing cost that we could not incur here. A better-structured project on producing this estimate should implement most of them.

Caveats

This approach to mining the Web assumes that the Web contains raw material of worth. Unfortunately, it seems that in any human form of communication when someone is allowed to write, spam is a by-product. Over half of the emails sent these days is spam, and possibly half of the Web pages are also spam. Search engines implement procedures to recognize spam and to remove detected pages from their indexes. But every technique implemented to detect spam inspires new creativity in escaping detection.

(i) Bait and switch spam Looking through generated pairs with low page counts, I checked a few to see where they came from. One combination, eradicated compilation, came from a Web page which contained the following paragraph, with only compilation appearing on the page:

The target of poker texas holdem game is to mix those 2 cards along with the five cards, that will at the end be situated before the dealer ('the board') in order to form the highest card combination. The winning hand can comprise any compilation of hole cards plus board-cards.

But this text is not what the search engine sees or indexes. When the URL of the page is fetched from the Internet, a search engine finds the following text, in which I have underlined extra words not appearing on the final displayed page:

The gratuito target of poker texas holdem game is em to mix caesars those 2 cards along em with the five cards, stuff that will at mac the end be situated daytona before the dealer ('the home board') in original order to form the ich highest card combination.

approximations The winning hand can use comprise any eradicated compilation of hole cards postmaster plus boardcards. Peruvianizes

The extra text does not appear on the final page shown to the user because there is an obfuscated redirection implemented in javascript that is executed as soon as the page is loaded in a browser that shows the cleaned-up text.

The extraneous words appear to have been inserted randomly every three to ten words, and also randomly drawn from a list of English words. The purposes of the extra words are twofold: (i) increase the likelihood the page is returned by a random query containing one of the added words, and (ii) primarily hide the fact that this cleaned text on the page has been stolen from some other site, since most search engines have implemented near-duplicate page detection. Near-duplicate detection will strip out side bars, menus, advertisements, and some numbers, and then compare the remaining text. If the same text is found on a higher ranking page, then this page is further deprecated, or removed from the index if from an already suspicious site.

The disadvantage of such spam, for language modelling purposes, is that odd combinations are created. Since they are random events, their frequencies remain low, but with over millions of spam pages, their cumulative counts can mask low-frequency but legitimate combinations. 13 For such reasons, we cannot trust low-frequency counts as legitimate common usages.

(ii) Generated text Another form of spam that creates unwanted phrases is found in the following example of generated text. The following Web page clearly wants to attract buyers of Zithromax (an Italian and Finnish brand name of a widely sold antibiotic, also called Azithromycin) to their Web page which directs to an online pharmacy store (of dubious authenticity). The page replicates structures of legitimate pages, with blog-like entries, but it seems to generate text using an algorithm that mixes text from a variety of sources, skipping from one text to another at stop words, as well as mixing in random words, words from a medical domain, and ensuring that sentence length falls within normal limits.

This page and five other spam pages attest the phrase transnational distress which probably originated as a typo of the medical term translational distress.

Abrade the ulterior.

And it's true, it has barely happened thousands of tetrahedron, so it must overly adapt to right itself on time otherwise I wouldn't be here, that's for sure. So perhaps you didn't know which drug they were helped or not you who amphoteric that here. I don't care. That's grouchy because we're taking these drugs increase cyclo levels to a multi-year stoned course for low-dose accutane, which I think I am a troll over a year and you can't kill the zaire deader than dead, and extra drugs in TEST subjects. Propionibacterium acnes vacillate haven't clarification is the same guarantor that causes pimples (acne) in tyrant when our hormones start to spike unenlightened reason this salting sanity like the fickleness diluent. I've done that with abx and was disappointed in the long term aspects. Try taking an antihistamine for a number of clientele who visit this f'ing newsgroup for 10 whodunit, or 5 utilization if Zithromax . Dawn I find ZITHRO-MAX scraped, not because of anything on his site about that. I'm not in transnational distress, but my liver enzymes are still closing up, a whole month after the end of May. Oh that ZITHROMAX may need to get him to educate it. First, I think the ZITHROMAX is that i have no reason to doubt the hell of your toxoid -why should I.

The random nature of such text assembly would throw noise into any language modelling. Consider calculating word association norms for the phrase liver enyzymes, for example, from such data.

(iii) Google counts A final caveat is against using Google counts for any finer-grained statistical comparisons. As Jean Veronis 14 , one of the first to detect this phenomenon, points out, the counts provided by Google are probably the result of extrapolating data from a smaller index. These counts depend on frequencies in this smaller index and the extrapolation is not reliable. I know that such extrapolation is not performed in the Exalead index used here.

Conclusion

Some of the potential applications of building a large-scale statistical description of word associations in the seminal paper Word Association Norms, Mutual Information, and Lexicography [START_REF] Church | Word Association Norms, Mutual Information, and Lexicography[END_REF] were to provide better language models for speech recognition and optical character recognition, as well as to help the lexicographer in making decisions on common usages of a word. Such techniques are also useful in determining proper translation in context. 15 The same language modelling applications (speech, OCR, translation) are still useful applications when we pass from word-based models to phrase-based models. Here we have tried to provide a first estimate of how many entries such a phrase-based model should include if we want to cover all the commonly used concepts expressed as phrases. We estimate this to be about 200 million concepts that future computational lexicographers and linguists will have to find a way to model.

Notes

1 Without ever really defining what I mean by "concept," operationally I will be using the word concept to mean something that is expressed using one or more words. When I use the word "word," I will mean a one-word concept.

2 Cited in Brewer (2007: 102 The meaning potential of each word is made up of a number of components, which may be activated cognitively by other words in the context in which it is used. These cognitive components are linked in a network which provides the whole semantic base of the language, with enormous dynamic potential for saying new things and relating the unknown to the known. The target of "disambiguation" presupposes competition among different components or sets of components. And sometimes this is true. But we also find that the different components coexist in a single use, and that different uses activate a kaleidoscope of different combinations of components. So rather than asking questions about disambiguation and sense discrimination ("Which sense does this word have in this text?"), a better sort of question would be "What is the unique contribution of this word to the meaning of this text?" (Hanks 2000: 214-215) 5 See chapters 7 and 10 in Manning & Schütze (1999). 6 Cf. Sag et al. (2002). 7 In WordNet 3.0, there are 146,347 word entries with a noun tag and only 25,047 with a verb tag. Patrick has also called for the elimination of a number of unattested words from WordNet, such as the verbs minify and desquamate which would reduce this number of verbs (cf. Hanks 2004: 3). 8 This depends, of course, on the ultimate application. Currently, for retrieving video, it is estimated that "a few thousand semantic concepts could be sufficient to support high accuracy video retrieval systems" (Hauptmann et al. 2007: 633).

9 Cf. http://www.askoxford.com/asktheexperts/faq/aboutenglish/ numberwords. 10 Which would mean some kind of infectious fermentation located on the end opposite to that on which the mouth is situated. 11 The complete utterance from which it is drawn even has its own Wikipedia entry, at http://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously. 12 One could easily imagine a parlour game built around these pairs. 13 For example, the generated phrase dusky chum appears only once in our

Table 1 :

 1 Breakdown of the types of two-word pairs.

	attested	number	percent	sample
	on pages	of pairs	generated	pairs
	0 977,161	97.2% reallocation trination, aestheticians gully, jump-
				ier jerkin, unillustrated spanks, pastoral intem-
				perateness, donax directives, hoofprints hygro-
				mas, teleworks pronoun, grout mas, cooptation
				geometries
	1 20,950	2% dusky chum, inevitable starling, sharpshooter
				planes, excipients abusing, comparative practis-
				ing, spelt thundering, reserves onions, rotgut
				rotter, differences chroniclers, catalogs recom-
				menders
	2	8,663	0.8% chough topping, crosslines request, expediency
				breakup, marksmanship centre, skirts hijack,
				loves mope, beautification risk, privacy psycho-
				therapies, bounds genoa, treatment ascender
	3-5 10,655	1.1% gulfs handbooks, shores limbo, frigates minus,
				abuse spokes, limes mise, tear butts, dreary
				glumness, stylite eremite, blunders firms, ma-
				nure hoeing
	6-10	8,935	0.9% prostitution commentary, minimal resists,
				stroller calls, opinion revel, perks peach,
				mommas japan, brook sheets, pedigree death,
				awed trade, jink bender
	11-30 10,365	1% brokenhearted advisor, vibration extremes, es-
				teem ticket, plywood terminology, list levels,
				high carnations, microbial slaughter, egotism
				good, introductions occult, mystifying facial
	31-99	7,806	0.8% electronic retriever, old rattlers, shirts dancing,
				guitar desecrator, foreman children, sap esprit,
				toyland beach, komondor purebred, peeping
				caddis, imperative win
	100-999	3,991	0.4% blow rim, cheapest studio, zygomatic complex,
				lake shrinking, view pedestal, viper differential,
				seas kayaks, gallstones people, artwork mascot,
				story varieties
	1,000-	1,163	0.1% comfortable beachfront, learning behavior, sup-
	over			plier enablement, important metal, factual ques-
				tions, protease lactase, training resellers, particle
				precipitation, dentistry professionals, karmic
				patterns, login functionality

  ). 3 Version 3.0 of WordNet contains 84,487 distinct words, plus 64,243 distinct multiword phrases. Cf. http://wordnet.princeton.edu/.

4

Patrick believes that it is misleading to talk about a word having one sense or the other. He argues:

  index, but from a legitimate textual source: O'Tway's last recorded telephone call was to fellow Gibbon Martyn Johansson, to assure him that all was well, and that he was at that moment drinking several pints of cider in the company of a dusky chum of his, NKPWW Salve. However, according to the black box data recorder, he was actually sitting in the back of a Heathrow taxi, heading for Hampshire …14 See his blog at http://aixtal.blogspot.com/2005/02/web-googles-missingpages-mystery.html. We should remark that Mark Liberman also warned about using Google as a statistics machine for linguistic processing as early as 2003, see his blog at http://itre.cis.upenn.edu/~myl/languagelog/archives/000194.html.A more recent examination is[START_REF] Eu | Testing Search Engine Frequencies: Patterns of Inconsistency[END_REF].

15

Cf.

[START_REF] Jang | Using Mutual Information to Resolve Query Translation Ambiguities and Query Term Weighting[END_REF]

.


Gregory Grefenstette

The Future of Linguistics and Lexicographers: Will there be Lexicographers in the year 3000?

Keywords: computational linguistics, lexicography, linguistics schools, parsing, lexical modeling

Lexicography has been a respected tradition of scientific pursuit since the eighteenth century. Will the science of lexicography survive into the third millennium? I will discuss what presentday computational linguistics can offer the lexicographer in the lexicographic task. I will show that the data can be purified in clearer and clearer forms through approximate linguistics. I will then speculate about what aspects of the lexicographic task can be automated, what tasks remain incumbent on humans, and wonder whether a new vision of the lexicon will • emerge .

Introduction

Lexicology has been posed as a science ever since the 18th century. In the article Grammaire from Diderot and D'Alembert's Encyclopedia, lexicology is described as the explanation of three aspects of knowledge about each of the words from a language: its Material, its Value, and its Etymology. The Material is described as how a given word is put together: the syllables that compose it, how it is pronounced. The Value of a word is divided into three parts: the fundamental sense (proper or figurative), the specific sense (now called the partof speech), and the accidental sense (morphological variants of the word). The Etymology concerns the rules by which new words are formed, as well as the historical sources of a word interesting as an aid to understanding the word's current meaning. Lexicology dealt with words taken in isolation, while syntax concerned words in the context of other words. The section ends: "Tels sont les points de vue fondamentaux auxquels on peut rapporter les principes de la Lexicologie. C'est aux dictionnaires de chaque langue a marquer sur chacun des mots qu 'Us renferment, les dicisions propres de I 'usage, relatives a ces points de vue".

Looking at modern dictionaries, we find that lexicographers in every language have taken these words to heart. The same principles are found in today's dictionary entries. The Material is presented in a word's spelling, pronunciation, and syllabification. The Etymology is often covered by a succinct presentation of the word's origins. Two of the three parts of the word's Value, the partofspeech and special morphological variants, are almost invariably included in the entry. The remaining point of view on a word, a description of the fundamental sense, composes the meat of the dictionary entry, and, to push the culinary metaphor, is the breadandbutter of the lexicographer.

In this paper I discuss what help the field of Computational Linguistics will bring to this task of describing the fundamental meaning of a word, and how the tools that will foreseeably be developed in this field may radically alter this two hundred yearold image of lexicographical description.

Linguistics, Computational Linguistics, and Approximate Linguistics

It is clear that one of the things that a computer can do well is treat a large amount of data, and that, with more and more text becoming available online, there is a lot of data with which a computer could work. 1 What is not clear is why Linguistics and, more recently and more blamably, Computational Linguistics have been so slow in providing adequate computer tools for aiding lexicographers in their task of describing word meaning.

Linguists used to be polyglots who were able to cite and qualitatively compare lexical and grammatical similarities and differences between languages. The systems that were devised in this old school of Linguistics mixed semantics, history, phonetics, into rules that were com prehensible to humans but not formally specifiable.

The idea of mathematical or computational linguistics appeared after the advent of the computer and following the mathematical classification of formal languages that [START_REF] Chomsky | Three models for the description of language[END_REF] produced. There was a certain heady glory in the idea that man's languages could be reducible to mathematical principles, now implementable in such calculating machines as were only a dream in Pascal's time. This computational idea was new, exciting, and a propos as Universities grew and were restructured during the academic buildup of the 1960s. Purveyed by these new, young linguists, the idea that all languages were merely variations on a set of formal principles, and that discovery of the parametric settings for each principle might be determined, became the dominant theory in Linguistics and in Linguistic departments. Poor working lexicographers, with their downtoearth questions about one particular language's vocabulary, were left in the dust as the linguists of the new generation pursued the more glorious goal of uniting the world's languages.

By the end of the 1980's two conflicting schools of computational linguistics were sharing the stage: the universal grammar school of Chomskian linguistics, and the nogrammar school of corpus linguistics. Here, if the reader permits, I will digress into a metaphorical comparison of these schools, inspired by Umberto Eco's comparison of the preWindows worlds of the DOS and of the Macintosh to Protestantism and Catholicism. 2 In my metaphor, one can map the Chomskyinspired school to the communist ideology; and the corpusbased school, of which the late IBM research [START_REF] Brown | Class based ngram models of Natural Language[END_REF] was the most flamingly brilliant example, to pure capitalism.

The communist ideology is firmly anchored in the belief that there is a unifying logic underlying human life, a logic that can be understood, a logic of which one can tease the thesis and antithesis from objective historical events by the power of reason. Understanding this logic leads to perceiving the communist ideal, the final classless unity to which humankind is tending in its spiraling crises of production and revolution. In the same Utopian vein, we find the linguistic endeavor to understand the underlying parameters whose discovery will render the masses of languages simply variations of one universal language. The Chomskian linguist is out there, searching for truth among the conflict. Not concerned by the trivial, quotidian of languages, the Chomskian is looking for hidden currents, running through history and cultures, because their discovery will solve the divisions, and bring about the golden age. On the darker side, we find the same fanaticism concerning the unadulterated truth of the believer's path. Just as factions among the far left (and the far right) are violently opposed to deviance from their party line, we find a plethora of acronyms GB, HPSG, CG, LFG, covering groups who ostracise and disparage their philosophical neighbors. 3 The competing school of corpus linguists can be compared to pure capitalism in that they feel that the market (corpus) has its own selfdefining logic (Adam Smith's the invisible hand of God) that should not be impeded by outside theories. Contrary to the Chomskian school, motivated by the goal of making all languages one, the corpus linguistic approach is undirected, taking an empirical approach of "seeing what is in die corpus". It is concerned with maximising what can profitably be extracted from the corpus, and in this sense, in order to increase its gains, its market must continually expand, encompassing ever larger corpora.

What is needed is a middle way between these two extremes of laissezfaire and linguistic dirigisme, that is, a recognition that there is some structure in text that can be recognised by machines, and that this recognition can be done in a useful way before the final goal of ultimate language unity is achieved. This middle linguistic ground is somewhat like the socialdemocratic approach of Western Europe: not theoretically pure, but containing a smattering of principles; recognising market forces, but ready to stick a political hand into the market. In lexicography, this approach has been attempted by a few computer scientists, such as Kenneth Church 4 , who has taken the time to sit and watch eminent lexicographers at work, seeing what parts of their task might be readably computerisable, using a "combination of data and theory". Lexicographers such as Jeremy [START_REF] Clear | I can't See the Sense in Large Corpus[END_REF] have also explored this middle ground, attacking their real problems of lexicography, particularly the search for a description of words' fundamental meanings, with the computer. This middle approach can be named approximate linguistics. Not perfect, but not bad. Until now, the use of computer parsers m lexicography has been considered limited by the unavailability of swift, robust parsers with which to process large corpora of naturally occurring texts. This dearth of practical parsers can be explained by the aptitude_of.linguists. to consider that the inability to properly treat the least counter^xamr^^a_fimg^mentel flaw mTpjrserTso, they consider, no parser can yet be proposed; it has also been sustained by the highly publicised belief in the allcomputational camp that no parser is needed, since statistics can find any structure in a large enough corpus. Bridging these two extremes, approximate linguisticsisbased on the idea that higher lmgn|ticjmajxses_such as those to be produced by perfect fullsentence parsing, can be represented more or Jess^tJi^j^Jqr^ipeTJ^gt.sjs^^i. that the accuracy of the approximations produced by these systems can be measured, and that the approximations can be successively refined by incremental improvements to the system to reduce error to desired proportions. In the next sections I illustrate an approximate linguistics approach to a lexicographical problem, showing both how the desired answers become clearer and clearer as more linguistic knowledge is injected into the system, and how one higher level linguistic analysis can be approximated by lower level functions.

Approximate Linguistics and Lexicography

One of the principal tasks of lexicography, as stated above, is to describe the fundamental sense of a given word. Currently, a lexicographer does this by seeing how the word is ordinarily used in the language, calling upon intuition or upon corpus citations (Kilgarriff, 1992:51). When a corpus is being used, the idea of ordinary use shifts somewhat, becoming quantifiable. How a word is ordinarily used in a corpus brings in the idea of frequency, how often a word is used in a certain way, and the idea of relative frequency, how often it is being used one way as opposed to another. Now, having shifted the problem of fundamental meaning to ordinary meaning to a process involving counting, let us see how the computer enters the picture. We can observe that the computer is very good at counting, but unfortunately not very good at knowing what to count. Contrary to what a small child can do, a computer can only count things which are made to look exactly alike. One programming task, then, involved in making languagerelated things countable by computer, is trarisforming them, abstracting away surface difference between two variant manifestations of the same phenomenon until the computer can see them as the same string of characters, of zeroes and ones in the same pattern. This is actually one of the aims of a complete parser: to produce a unique internal structure so that different sentences, even in different languages (Butt et al, 1998), can be matched, compared, and counted by a computer. Until such parsers become widely available, the abstraction process provided by them can be approximated using existing technology involving lesser text processing means, by approximate linguistics. The successfulness of these approximations depends, as we will see, on the amount of linguistic information included in the technology.

Abstraction Levels and Approximate Linguistic Tools

If one thinks of the process of abstracting away surface differences in text as a linguistic process, then one can consider that there is a continuum of abstraction levels between the original text and the completely parsed version (whatever that might be) of a text. In the first steps of computer treatment of text, converting physically printed text into an electronic form, some meaningcarrying aspects of the text are regularly abstracted away. The meaning carried by differences in fonts, in type size, and in page layout often disappear in the electronic ASCII version of a text. For corpus analysis, this loss of information carries the advantage that the computer can now compare two strings of characters in an electronic corpus, rather than comparing pixel equalities, in order to determine whether the two words are the same. This first level of text abstraction requires linguistic information, either on the part of the person who retyped in the text and who was able to correctly recognise each letter, or by the optical character reading program, programs which commonly contain characterlevel language models.

Here are some other more evident linguisticallyinformed levels of abstraction which erase surface differences in words: • tokenisation deciding where to find the boundaries of the objects to be compared, • lemmatisation conflating inflected forms of words to normalised lemmas, • partofspeech tagging abstracting away from individual words to grammatical classes of words, • shallow parsing abstracting away from positional information to syntactic function, • semantic tagging abstracting away from individual words to semantic classes.

Each of these tasks can be attacked more or less successfully with different computer tools.

The tools used for one level can be stretched to perform tasks on a higher level. Just as when one only has one tool, like a screwdriver, one uses it as a hammer, a knife, or whatever is needed, so one can make do with inadapted computer tools to perform linguistic tasks. To illustrate what different levels of abstraction can provide to the lexicographer using current technology, let us consider a typical lexicographic problem. Suppose that the lexicographer has a large corpus of English text, and is working on the fundamental meaning of the word check. More precisely, suppose that she is currently looking for the typical arguments of the verb check, an interesting example since the verbal and nominal forms of the word are written the same: to write a check, to check. Further suppose that, in order to grasp the ordinary senses for check, she is looking for the common direct objects (what can be checked) and the common objects of prepositional adjuncts (e.g., what can be checked for) of the verb check. If a full parser existed that could treat the entire corpus, one might then parse the corpus and the results of the parser would indicate these common arguments with precision. In the next few sections, I show what different levels of abstraction, made possible by incrementally more complicated linguistic tools, provide as an answer to this task. We shall see that simple tools provide an answer, but the answers become clearer as more linguistic knowledge is added, and as the approximations more accurately approach the goal of complete parsing.

Tokenisation as an Approximation to Parsing

In this task of finding common arguments of a word, tokenisation is the simplest tool that can be used to approximate parsing. Tokenisation defines mebojundarie3^fJhe.units.that^ilJ^e counted by the computer, and allows us to recognise contiguous but separate units. In printed 4anguages*wfiich use spaces, the techniques of tokenisation usually involve using regular expressions to describe contexts where the input string needs to be separated into units [START_REF] Karttunen | Regular Expressions for Language Engineering[END_REF]. Since tokenisation is a well known problem in computer science, being an inherent part of computer language compiler construction, many computerbased tools have been developed that can be used for tokenising, e.g. lex, awk, and perl. 5 A tokeniser for a natural human language contains simple linguistic information about how words are formed in that language: what characters are letters, what characters are numbers, what characters are punctuation, what elements of punctuation can appear within a word (like the apostrophe or the dash in English). The more linguistic information that the tokeniser has access to, the better the results [START_REF] Grefenstette | What is a word, what is a sentence? Problems of tokemzation[END_REF].

As a first approach to our lexicographical problem, we can process our corpus in the following way: whenever the token check appears we store the next three tokens that occur in the input. This simple heuristic is based on the rudimentary linguistic knowledge that English verbal arguments and adjuncts generally occur shortly after the verb, so this threetoken window is where we are likely to find the arguments we want. Once we have gone through the whole corpus, we count each occurrence of each token found in this small window, and then sort the tokens according to frequency. The computer is good at this counting and sorting. This same heuristic is similar to that used by practicing lexicographers visually scanning rightsorted KWIC (Key Word In Context) files for regularities. Table 1 shows the most common tokens extracted using this windowing technique for the token check over the British National Corpus. 6 (Here, even for this simple task, we can use different levels of approximation. The simplest tokeniser just splits words on spaces. The first three columns, in Table 1 use this spaceonly approach. The last column uses a slightly more informed tokeniser integrating English wordstructure knowledge to divide the input text into separate tokens.) The first column gives the most frequent tokens found in this three word window, with their frequency. This list is not very interesting for finding the direct objects and objects of prepositional adjuncts of check. We find check it and check this but this does not tell us very much about what the typical arguments of the verb check are. There is interesting information about check nonetheless: we find that the most likely prepositions associated with check are on, of, out, with, and that check seems to subcategorise for subclauses introduced by that and whether. This is interesting, but not what we were looking for. One improvement to this simple approach is found in subsequent columns from which are removed a list of common function words, called stopwords in the Information Retrieval community. Stopword lists 7 are comprised of personal pronouns, articles, prepositions, conjunctions, etc., the closed class function words of the language. For English such a list runs to about one hundred words. Of course, such a list can be counted as a slight injection of linguistic knowledge into the system. Filtering out such words provides a much cleaner list using this simple threeword window technique. Column two in Table 1 shows a more plausible list of common objects of check: lists, things, progress, details, accuracy...

Column three introduces a minor linguistic fact, i.e. that upper and lower case distinctions do not affect meaning inordinately in English, since such typographical variations can appear in headers, or in quoted speech. The input corpus for columns three and four has been transliterated into lower case, so we find more instances of both check as well as its possible arguments. The final refinement shown in Table 1 is the results of using a proper English tokeniser and not just spaces to separate words. We see that the counts for checking a list rises to 92 from column two's 55 count, since now we find cases where periods, commas, and parenthesis were stuck to list, effectively biding it from our computer which could not recognise in column two that the two strings list and list) [with a postpended parenthesis] were the same word. What we see in the four columns of Table 1 are that little injections of linguistic knowledge make the lexicographer's task easier, by making surface differences disappear. These little improvements become especially evident as we go further down the list. For example, we see that check.. shirt appears whereas in the simpler approaches we would have had to scan further down the list to find it.

Space

The results seem rather noisy, and require a certain patience and habit in order to extract any information. One can derive even from this noisy data that details and prices seem to be common arguments of check. But the confusion between nominal forms and verbal forms renders speculative any conjectures about whether number is a common argument of the verb check or whether it appears in a common noun phrase such as check number. In addition to confusing verbal and nominal forms of check, show the tokens appearing within 3 words after various forms of check Column 5 unions these lists. The last column gives the lemmas after any form of the lemma check. This last treatment finds more corpus samples.

Adding Morphological Analysis and Lemmatisation to the Approximation

A next level of linguistic sophistication, beyond tokenisers and lists of function words, is the ability to morphologically analyse and to lemmatise surface forms of words into some canonical form, for example, masculine singular for nouns, or an infinitive form for verbs. This requires the linguistic resources of a lexicon and an analyser, but thanks to the efforts of computational linguists and lexicographers [START_REF] Karttunen | KTMMO: a general morphological processor[END_REF][START_REF] Chanod | Finite state composition of French verb morphology[END_REF]) over recent years, these basic resources are becoming available in more and more languages. 8 The last column of Table 2 shows the lemmas found after the lemmatised forms of the word check. We can approximate a lemmatiser, tediously, by explicitly detailing the forms we are looking are, such as are given in the first four columns of Table 2. The fifth column accumulates all four forms into one total column. The lemmaderived list in the sixth column is not all that very different at first glance from the fifth column, yet we have included a relatively expensive resource, a morphological analyser and lemmatiser in the process. In fact, the greatest difference comes in the numbers. Thus, in the same corpus, after lemmatisation, the number of recognised instances of check ... spelling grows from 27 to 41. This growth comes from the fact that the lemmatiser allows the computer to match variants such as check my spellings and checked my spelling to a single form check ... spelling, abstracting away morphological variation and intervening words within the window. The number of recognised instances of the desired phenomena grows as more linguistic information is added. Since the number of recognised instances grows, we can consider rarer phenomena. The morphological analysis and lemmatisation, by abstracting away differences, improves the counts of the data. instances preposition 1050 on 652 for 619 of 582 with 507 to Table 3: Prepositions in a three word window after the lemma check in the British National Corpus.

Another advantage provided by a lemmatiser that returns the possible parts of speech as well as the lemmas, is that one can start to reason in terms of partofspeech as well as in terms of strings. For example, one finds the most common prepositions in this window of three words after any form of the word check to be those given in Table 3. We will see the usefulness of this abstraction to partofspeech as well as the improvement in recognition due to the abstraction derived from lemmatisation in the next section.

Adding PartofSpeech Tagging to the Approximation

Table 2 shows a confusion between verbal and nominal uses of check. In order to distinguish these uses when the surface form is check used as a noun or check used as verb, we can supplement the tokeniser, morphological analyser and lemmatiser, with one additional linguistic tool: a partofspeech disambiguator. 9 Partofspeech taggers have been around for thirty years, based on handwritten rules, and statistics, attaining correct tag rates of 95% to 99% according to the languages [START_REF] Karlsson | Constraint Grammar : a language-independent system for parsing unrestricted text, volume 4 of Natural Language Processing[END_REF][START_REF] Schiller | Multilingual PartofSpeech Tagging and Noun Phrase Markup[END_REF]. Using such a tool is important for our problem since the identical nominal and verbal forms are both frequent. On top of the linguistic information contained in morphological analysers and lemmatisers about word forms, partofspeech taggers contain models of word sequences to be found in the language. These models are either derived from introspection by linguistics, or from a training set of manually tagged text [START_REF] Church | A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text[END_REF]. Using this linguistic tool allows us to further approximate perfect parsing, since now we can distinguish between verbal and nominal uses of check and look for arguments of the verb.

The first column of Table 4 shows the results of applying the threeword, windowbased, parsing approximation technique to verbal uses of check, as well as to consider, if we wish, only nominal arguments to the verb. Here the solution to our original problem becomes even clearer. We see that one checks watches, the time, progress; details, lists, records, files; names, information, the car, levels, spelling, etc. From this list of potential arguments we see that some of the words appearing in the last column of Table 3, which came from a lemmatiser without a partofspeech tagger, disappear. For example, balance is no longer present. This is because balance is almost exclusively found in the nominal expression checks and balances. The additional linguistic processing refines the search. This additional tool allows us to more accurately consider more specific and rarer phenomena. The second and third columns of Table 4 show the nouns appearing in a window of three words after the most common prepositions found in Table 3, on and for, themselves appearing within three words of a verbal use of check. From this, the lexicographer can be led to discover common uses involving prepositions: check on progress/performance, check on car/gas/health/child, or check for damage/wear/crack etc. These samples are relatively rare in the corpus, and would have been further down the list in Tables 1 and2 where they would have been swamped in noise, but here as the approximations to full linguistic analysis improve, they become evident.

Shallow Parsing as an Approximation to Full Parsing

As the previous sections have shown, some aspects of syntax can be ajoproximated by simple position information, i.e. the window appearing"afterthe word being examined. We have been supposing that'words appearing in this window probably play some role as an argument.

Other words appearing in the window are abstracted away so that different surface configurations can be made to look equal for the computer.

A further linguistic refinement that can be applied is to use regular patterns of the tags provided by the partofspeech disambiguator to partially recreate the syntactic structure of the sentence. Recognising nominal chains and verbal chains as sequences of partofspeech tags allows us to recognise certain syntactic relations, such as government of a noun by a preposition, or the voice of a verbal chain. This classification allows us to further pinpoint possible objects and prepositional arguments while eliminating others. This area of computational linguistics [START_REF] Debili | Analyse Syntaxico-Sémantique Fondée sur une Acquisition Automatique de Relations Lexicales-Sémantiques Phd[END_REF][START_REF] Abney | Parsing by Chunks[END_REF][START_REF] Grefenstette | What is a word, what is a sentence? Problems of tokemzation[END_REF]AitMoktar & Chanod 1997) is gaining more attention and more respect as much work progresses on creating such lowlevel parsers in a number of languages. Using such a lowlevel syntactic pattern extractor [START_REF] Grefenstette | Light parsing as finite state filtering[END_REF] built using finitestate regular expressions and transllu^ersrwfcan analyse the corpus at a higher level of abstraction. Table 5 shows the improvement in the data that the shallow parser tool gives over the lower level 3word window approximation for the pattern check..with.... As before, the lists become cleaner as noise becomes more properly eliminated. One can see, in the first column, that in the corpus people check with their bosses, editors, and banks. This shallow parsing information can be used to extract the corresponding KWIC lines automatically for the lexicographer, as shown in The first column shows nouns extracted as direct objects by a lowlevel parser, the second column shows words within a window of three words after check. In the first column, we see that noise coming from prepositional objects (check with doctor), and noise coming from nonrecognition of structure (check your blood pressure) which clutter the list supplied with the simpler approximation, disappears from the first column.

Even much further down the list, one can capture rarer but true arguments more often with the shallow parser.

Table 7 shows the lemmas identified as direct objects that are extracted using a lowlevel parser over the same BNC corpus used throughout this presentation. Though noise persists, as is the case with all the previous approximations to full linguistic parsing, the lists produced are more precise. In both columns of Table 7, there is much overlap with the most frequent cases, but the focusing power of adding more linguistic knowledge appears more clearly at the end of the list where one discovers only with the lowlevel parser that one can check symptoms, signs, shoes, security. These lemmas would also appear further down the list of the second column but they would be swamped in the noise there and be harder to discern.

The initial problem of finding argument for the verb check has been treated with a sequence of increasingly sophisticated linguistic tools: from tokenisers, to eliminating a list of stopwords, to morphological analysers and lemmatisers, to partofspeech disambiguators, and finally to lowlevel parsers. The results obtained in Tables 1 to 7 show a gradual focusing in which more noise is eliminated and in which more infrequent phenomena are brought to light as more linguistic information is incorporated into the process.

Semantic Tags

One further linguistic refinement, this time using the WordNet [START_REF] Miller | Introduction to WordNet: An online lexical database[END_REF] thesaurus as a linguistic resource, is shown in Table 8. This table shows the semantic tags associated with each of the most frequent direct objects recognised for check. Semantic tags are not as well defined as grammatical tags where the classes are more constrained and better understood [START_REF] Bolinger | The Atomization of Meaning[END_REF]. Ideally, a semantic partofspeech tagger would use context, as a grammatical partofspeech tagger does, in order to choose the most likely tag. This research area has had limited success [START_REF] Segond | An Experiment in Semantic Tagging Using Hidden Markov Model Tagging[END_REF], impeded by a lack of semantic dictionaries and due to the fact that the problem is no longer one of simple structure but also of meaning.

The only conclusion to be drawn from Table 8 is that the direct object of check is likely to be something classified as a communication or an artifact, but the meanings of these semantic tags are not very clear in themselves. Choosing between the semantic tags using context is a problem akin to partofspeech disambiguation, but on a much larger scale, as the ambiguity of words is greater than with grammatical tags, and because there are many more potential semantic tags than grammatical ones.

Extrapolation to the Future

So far, I have presented the historical argument that the main task of the lexicographer is to describe the usual meanings of the words in a language. I have also argued that classical linguistics (1956present) has not been supplying the tools necessary for mis task because it has been concentrating on the universal (universal grammar formalisms or universal statistical techniques) and not on the everyday routine. Springing up, and gaining weight in compu tational linguistics, are techniques that can be called approximate linguistics, i.e., approx imations to linguistic theory that are both incrementally perfectible as well as being robust and immediately useful.

The previous section gives a hint of what approximate linguistics can offer working lexicographers today in their task of describing some fundamental sense of a word. Though the tools used there have not all been packaged as a shrinkwrapped product with lively colours and series of ergonomic pulldown menus, all the tools exist today from a variety of resource providers and in a variety of languages: corpora, tokenisers, morphological analysers and lemmatisers, partofspeech taggers, shallow parsers, and assorted bookkeeping tools which count, sort, calculate cooccurrence statistics (mutual information, tscores, etc.), and so on. Let us return to the question of corpus size, which is one of the major aspects of the theory less corpus linguistics approach. All the tables and charts in this paper were derived from the 100million word British National Corpus. In this large corpus, the lemma check appears about 13,000 times. This great number of occurrences allows us to aid our imaginary lexicographer by showing the common arguments of the word check as a verb. With little linguistic information, e.g. stopwords, we already get some answers; as more linguistic information is added to the system, the results become clearer, and rarer phenomena can be considered, as can be seen at the bottom of the first column of Table 7. As an example of how more complex structures become rarer, in our Xeroxparsed version of the BNC, there are 4854 instances of check with a direct object; when we consider prepositional adjuncts, a structure that involves three words: the verb check, a preposition, and the object of the preposition, there are 2893 cases; when we consider the more specific structure of prepositional adjuncts to check beginning with the preposition with, there are only 417 cases (see Table 5). In true Zipfian fashion, the more complicated the structure, the rarer it is. The rarer something is, the more corpus you need to find it reliably. Now, on the Altavista Web browser in Spring of 1998, there were 13 million indexed occurrences of a form of check, one thousand times more data than was used for the data appearing in this presentation. The data is there for extracting all the information one might want about a word in more and more complicated patterns.

Will we need lexicographers in the future? What are lexicographej5,rieededforriQjv?^ According the Adam [START_REF] Kilgarriff | Polysemy PhD Thesis[END_REF], the ideal lexicographer must (i) jatiiCT_corpus of citatiojisJfor_ajiyen word, (ii) divide the citations intc*. clusters, (iii) decide why the cluster member belong together, ar^(^jjpjd^3teu r conclusions into a aUctionary'defimSoii. "As ibr the^firsJL two steps, we can easily predict that approximations to proper parsing that computetionad^linguistics can provide will become"rnore_and rnore^ accurate, that the structures that will be recognised will be more and more complex, that the corpus to which the techniques will have access will be bigger and bigger, and that more and more usage patterns of words can be extracted from this text corpus. The computer will have better numbers to count with, to cluster with, to separate with. Thejse Jeav&s the rational steps of three and four, synthesTsuig'and explaining. Synthesising means finding a higher level description of the things found in certain "positions. different from other groups that the human user knows. In this sense, that of providing shortcuts to understanding to other users, a lexicographer will always be needed.

Yet it might also happen that lexicographers may be needed less and less for some of the tasks that they spend much time on now. What if endusers had access to clustered and filtered KWIC lines when they wondered how a word was iisedTWhat {i^e'compufefw^* able to analyse any^ wo^dlncon^c^xtflct*all > me , patterns that the word was found in, cluster them in a coherent way 10 , and display these further examples succinctly for the user? For translation dictionaries, for knowing the patterns that words appear in, with what preposition, what if patterns were able to be predigested and scanned by the user, could they induce meaning from these examples? Would the user need a humansupplied explanation? I believe that in the coming years we shall see a new way at looking at the lexicon that is no longer twodimensional: a list of words, and their explanations, but rather three and four and five dimensional in which information is stored about how each word is used with each other word, and how that pair of words is used with a third word, and that triple with a fourth word. This vision requires massive data structures and robust linguisticapproximation tools to fill them, and a new way of sifting and handling this data. It also requires a lot of disk space, but this, contrary to the space requirements that governed paper dictionaries, is now the least of our concerns when we remain in the electronic world.

But paper still has a long life in front of itself, and as long as things are printed we will need the reasoned condensations that only lexicographers provide. No one can make a proposal so that someone will stand up in the audience and say: 'Ah, but that is not a GB grammar!' Similarly, I could add a bunch of features and devices to HPSG and no one could say: 'That is not HPSG.' You can say that it is not in the spirit of HPSG, or not in the spirit of GB, but it is really all just a matter of esthetics. So I think insofar as people really want to make theories of a universal grammar, then they should be honest and lay out the possible grammars. Again, GPSG perhaps came the closest to this goal in spirit, but it didn't really excite many linguists. Once you lay something out concretely, it's just a little too easy to see where it falls down."

  These tools allow the lexicographer to see what words cooccur with a given word, to examine what syntactic structures the word occurs in, what other words enter into what syntactic relations with the word and how often, and to retrieve all the corpus lines corresponding to any of these configurations.

•" 3 Ivan

 3 Altavista web browser has encountered the word the 1.4 billion times in its latest monthly trawl of the Internet. With its frequency of about 1 per 7 English words, we can roughly estimate that there are 10 billion English words to be computationally digested on the Web pages accessible through Altavista. The words are certainly there, accessible for lexicographical study, in this large distributed corpus. 2 See http://www.huLfi/~tsiivoIa/EcoMac_vs_Dos.html. Here is an excerpt: "The fact is that the world is divided between users of the Macintosh computer and users of MSDOS compatible computers. I am firmly of the opinion that the Macintosh is Catholic and that DOS is Protestant. Indeed, the Macintosh is counterreformist and has been influenced by the 'ratio studiorum' of the Jesuits. It is cheerful, friendly, conciliatory, it tells the faithful how they must proceed step by step to reach if not the Kingdom of Heaven the moment in which their document is printed. It is catechistic: the essence of revelation is dealt with via simple formulae and sumptuous icons. Everyone has a right to salvation. DOS is Protestant, or even Calvinistic. It allows free interpretation of scripture, demands difficult personal decisions, imposes a subtle hermeneutics upon the user, and takes for granted the idea that not all can reach salvation. To make the system work you need to interpret the program yourself: a long way from the baroque community of revelers, the user is closed within the loneliness of his own inner torment.Sag raged against the hubris of the Chomskians in a 1993 interview (http://www.coli.unisb.de/ mineur/Itv/Sag.html) in which he bemoaned that GB (Government & Binding) practitioners "can simply condemn a whole tradition to irrelevance, like Relational Grammar, whose systématisations of complex grammatical systems constitute to my mind a longlasting and significant contribution to the field of syntax. It is an antiintellectual attitude, and in fact I think it is dangerous for the entire field of linguistics." He complained that GB "also has heresy essentially what everyone else in linguistics does, not to mention the work on language done in other fields, e.g. psychology or computer science." Bob Carpenter, in a 1995 interview (http^/www.<»U.unisb.de/Mnmeur/Itv/(^rpenter.html), describes the theoretical correctness that this school of Linguistics searches for "I really hated HPSG (Pollard et al., 1987) at that time, because to me it looked like a complete Frankenstein theory. Not because it is built up from all these other grammar formalisms, like LFG and GPSG and CG and all that, but I had a real bias against the fact that it was using different sorts of mechanisms to do everything. You can look at Categorial Grammar, and you can say there is a pure logical reasoning mechanism on which everything is based. But in HPSG that uniformity comes only at the level of the feature structure logic. It is important not to confuse the kind of underlying attributevalue logic formalism with the linguistic theory. In HPSG there is mis whole linguistic theory that contains things like the Head Feature Principle and the Quantifier Binding Condition and Principle A of the Binding Theory. That is the linguistic theory. HPSG should not be criticised on the fact that it is based on a Turingpowerful constraint resolution system. You just cannot do in the linguistic theory, everything you can do in the underlying theory. Shieber originally pointed this out in the context of PATR." He continues with a description of how none of the theories propounded in this linguistic school are aimed at producing anything practical for NLP: "Now of course no linguistic theory, GB, HPSG, any of these, have really laid out a meta theory of what really counts as a grammar. You will never find anybody saying: 'A GB grammar is the following thing: one of these versions of this, one of these versions of that.' They talk about it that way, they say it is somehow parameterised, but you never actually see a list of parameters.

Table 1 :

 1 Finding and counting the three words appearing after the token check in order to find the arguments of the verb check Columns 1 to 3 use just spaces to find

		-only		No Stop		No Case		Tokeniser
				Words		Distinction
	1753	the	55	list	65	list	92	list
	722	that	24	make	30	carefully	40	carefully
	620	on	23	things	29	local	34	progress
	398	and	22	carefully	26	make	28	things
	336	of	21	progress	24	things	28	local
	317	out	21	local	24	details	28	details
	281	with	20	details	21	progress	25	price
	272	for	19	own	21	price	25	make
	257	your	19	accuracy	21	erm	25	lists
	242	it	18	blood	20	own	24	accuracy
	217	to	16	new	20	new	21	facts
	195	in	16	made	20	back	21	erm
	185	is	16	back	19	lists	21	balance
	180	a	15	time	19	accuracy	21	back
	172	you	15	spelling	18	time	20	water
	152	whether	15	facts	18	blood	20	spelling
	131	if	14	sure	17	spelling	20	own
	122	all	14	lists	17	made	20	number
	120	their	14	information	17	level	20	new
	116		14	erm	17	facts	20	made
	112	up	14	ensure	17	ensure	19	information
	112	his	13	water	16	water	18	action
	104	this	11	validity	16	number	17	shirt
	99	before	11	suit	15	sure	17	level
	90 89	they are	11 11	quality points	15 15	information balance	17 17	increase ensure
	84	at	11	list,	14	increase	17	doctor
	81	what	11	doctor	14	doctor	17	blood
	80	by	11	data	14	correct	16	work
	79	I	11	actual	13	work	16	time

tokens. Column 4 uses a linguistically motivated tokeniser for English. Stopwords (closedclass words) are removed from columns 2 to 4. Columns 3 and 4 ignore case distinctions. As more linguistic information is added, the lists present the possible arguments more cleanly and more completely. Note: erm comes from the recorded speech in the BNC.

Table 2 :

 2 Table 1 ignores variant verbal forms of check. The next level of linguistic refinement, lemmatisation, addresses this problem. Approximating a lemmatiser by explicitly listing forms. Columns 1 to 4

		checking	checked	checks	check	check,-ed,		lemmas
						-s,-ing
	17 watch	watch watch	58 balances	92 list	107 list	137 list
	11 time	ensure ensure	45 made	40 carefully	95 watch	118 make
	10 records	hotel hotel	21 carried	34 progress	67 made	98 watch
	8 checking	16 carefully carefully	7 performed 28 things	62 carefully	S3 balance
	7 stock	15 regularly regularly	7 ensure	28 local	61 balances	62 carefully
	7 progress	14 time time	7 controls	28 details	49 make	57 number
	7 erm	14 shirt shirt	6 three	25 price	47 progress	51 ensure
	7 back	14 checked checked	6 new	25 make	45 ensure	47 progress
	6 times	number number	6 make	25 lists	41 time	46 detail
	6. quality	using using	6 checks	24 accuracy	41 number	45 record
	6 procedure	sure sure	6 built	21 facts	40 local	45	level
	6 number	make make	5 people	21 erm	37 things	44 shirt
	6 make	11 list list	5 gas	21 balance	37 back	44 price
	6	local	three three	5 files	21 back	36 erm	43 use
	6 information	state state	5 credit	20 water	36 carried	42 thing
	6 facts	records records	5 car	20 spelling	35 records	41 time
	6 accounts	room room	4 work	20 own	34 information 40	local
	5 understanding yesterday yesterday	4 traders	20 number	34 details	40 carry
	5 system	times times	4 take	20 new	34 accuracy	39 spelling
	5 supplies	shirts shirts	4 successful 20 made	33 new	38 car
	5 purposes	rechecked 7 rechecked	4 required	19 information	31 shirt	37 back
	5 possible	pulse 7 pulse	4 regularly	18 action	31 facts	36 work
	5 people	informatic 7 information 4 patients	17 shirt	29 regularly	36 erm
	5 old	file 7 file	4 levels	17 level	28 water	34 information
	5 notes	car 7 car	4 going	17 increase	28 sure	34	file
	5 names	approved 7 approved	4 data	17 ensure	28 price	p4	accuracy

Table 4 :

 4 Once

		Nouns after		nouns found	after	nouns found after check
		check...		check., on...		..for...
	97	watch	28	progress	21	sign
	51	time	12	movement	14	error
	44	number	11	thing	12	accuracy
	43	progress	11	number	11	leak
	37	record	9	file	11	damage
	35	detail	8	use	10	check
	33	thing	8	time	8	consistency
	33	list	8	quality	7	time
	32	accuracy	8	people	7	possible
	31	fact	8	level	7	level
	30	check	8	activity	7	correct
	29	level	7	make	5	square
	29	information	7	car	5	pulse
	27	name	6	record	5	free
	27	date	6	performance	5	flight
	27	car	6	material	5	fingerprint
	25	hotel	6	health	5	detail
	23	work	6	gas	5	crack
	23	spelling	6	child	4	wear
	22	file	6	calculator	4	virus

we can use a partofspeech tagger with the morohologicjdanalyser and^lemmatjser, rarer phenςln^ha^cm^e more accurately counted. We can specify what nouns appear after theyirbal use of check in" column l.In Columns 2 and 3, we can find nouns appearing after certain prepositions after verbal uses of check. This additional tool provides a closer approximation to full parsing.

parsed 3 words after check... with... check... with 20 office

		parsed		3 words after
		check... with...		check... with...
	2	time	4	own
	2	thermometer	4	manufacturer
	2	test	4	language
			19	local
	8	doctor	19	doctor
	7	authority	13	office
	5	agent	12	level
	4	number	9	spirit
	4	manager	7	bank
	4	detector	6	manager
	4	company	6	erm
	4	bank	6	company
	3	staff	6	check
	3	police	6	authority
	3	hotel	5	travel
	3	editor	5	police
	3	consulate	5	agent
	3	centre	4	time
	3	boss	4	radio
	3	association	4	parent

Table 5 :

 5 Comparing results returned with a shallow parser to those returned by a windowbased approximation to parsing. The first column gives the objects of the preposition.

shops and

other establishments abroad check So it is essential to check No, cheque but it's good Josh checked this was a good idea but would have to check Universe editor Anne Noels checked It is sensible, however, to check On being told by the manager to check Then, posing as a relative, she checked She checked with drivers stranded in France checking with your bank for details . with your travel agent or bank on with the bank, called Hnatiuk with his immediate boss with bosses about the ban in with editors of really specialist with the bank, he pretended to with the editor. with all the contributing editors in with their boss .

Table 6 :

 6 KWIC lines associated with check .. with (bank or editor or boss) lines returned by the shallow parser.

Table 6 .

 6

	watch	92	list
	number	84	check
	record	40	carefully
	detail	34	progress
	time	28	things
	item	28	local
	feet	28	details
	level	25	price
	date	25	make
	accuracy	25	lists
	list	24	accuracy
	work	21	facts
	condition	17	ensure
	answer	17	doctor
	story	17	blood
	room	16	work
	symptom	5	vehicle
	structure	5	various
	string	5	use
	status	5	ups

Table 7 :

 7 Parsing vs. Window. Looking for direct object collocates of check.

Table 8 :

 8 The WordNet semantic tags associated with the most common direct objects of a verbal form of check. The semantic tag communication (16 of 31 words) or artifact (12 of 31) appear most frequently.

  Table 8, the WordNet semantic abstractions, shows that this goal is far from being satisfied. jLJSuSorneJhing that humans are ^ernjnentiygoodatH3utmachines still poor. Explaining what makes a cluster coherent in a way understandable for a human is beyond the scope of a computer. It means drawing distinctions and contrasts between shared experiences and expectations, explaining what makes this group