The Balancing Act: Combining Symbolic and Statistical Approaches to Language (Language, Speech, and Communication)

Table of Contents Preface Acknowledgments Ch. 1 Statistical Methods and Linguistics 1 Ch. 2 Qualitative and Quantitative Models of Speech Translation 27 Ch. 3 Study and Implementation of Combined Techniques for Automatic Extraction of Terminology 49 Ch. 4 Do We Need Linguistics When We Have Statistics? A Comparative Analysis of the Contributions of Linguistic Cues to a Statistical Word Grouping System 67 Ch. 5 The Automatic Construction of a Symbolic Parser via Statistical Techniques 95 Ch. 6 Combining Linguistic with Statistical Methods in Automatic Speech Understanding 119 Ch. 7 Exploring the Nature of Transformation-Based Learning 135 Ch. 8 Recovering from Parser Failures: A Hybrid Statistical and Symbolic Approach 157 Contributors 181 Index 183

file:///C|/Documents%20and%20Settings/Admin/Desktop/New%20Folder/TOC.txt[6/17/2009 10:22:27 PM]

Preface

The chaptersin this book comeout of a workshopheld at the 32nd Annual Meetingof theAssociationfor ComputationalLinguistics, at NewMexicoState University in Las Cruces, New Mexico, on 1 July 1994. Thepurpose of the workshopwas to provide a forum in which to explorecombinedsymbolicand statisticalapproachesin computationallinguistics. esto the study To manyresearchers , the merenotion of combiningapproach has . Indeed, in the past it of languageseemsanathema appearednecessaryto , studyingtwo essentially choosebetweentwo radically different researchagendas different kinds of data. On the one hand, we find cognitively motivated theoriesof languagein thettadition of generativelinguistics, with introspective es motivated by data as primary evidence. On the other, we fmd approach empiricalcoverage,with collectionsof naturallyoccurringdataasprimary evidence . Eachapproachhasits own kinds of theory, methodology, and criteria . for success Although underlying philosophicaldifferencesgo back much further, the genesisof generativegrammarin the late 1950sandearly 1960sdrew attention to the issuesof concernin this book. At that time, therewasa thriving quantitative linguistics community, in both the United Statesand Europe, that had originatedfollowing World War II in the surgeof developmentof sophisticated es to scientific problems[Shannonand Weaver, 1949] . quantitativeapproach es werebuilt on the foundationof observabledata Thesequantitativeapproach as the primary sourceof evidence. The appearanceof generativegrammar [Chomsky, 1957], with its emphasison intuitive grammaticalityjudgments, led to confrontationwith the existing quantitativeapproach,and the rift between the two communities, arising from fmnly held opinions on both sides, prevented esto languagegrew up productiveinteraction. Computationalapproach during this feud, with muchof computationallinguisticsdominatedby the theoretical perspectiveof generativegrammar, hostile to quantitativemethods,

viii

Preface

and much of the speechcommunitydominatedby statisticalinfonnation theory , hostileto theoreticallinguistics. Although a few naturallanguageprocessing( NLP) groupspersistedin taking a probabilisticapproachin the 1970sand 1980s,therule-governed,theorydriven approachdominatedthe field, even amongthe many industrial teams working on NLP (e.g. [ WoodsandKaplan, 1971; Petrick, 1971; Grosz, 1983]). The influenceof thelinguists' generativerevolutionon NLP projectswasoverwhelmi . Statisticalor evensimply quantitativenotionssurvivedin this environmen , included for the purpose of only as secondaryconsiderations ' but optimization rarely thoughtof asan integralpart of a systems coredesign. At the sametime, speechprocessinggrew more mature, building on an information -theoretictradition that emphasizedthe induction of statisticalmodels from training data(e.g. [Bahl .et al., 1983; Flanagan, 1972]). For quite sometime, the two communitiescontinuedwith little to sayto each other. However, in the late 1980sandearly 1990s,the field of NLP underwenta radical shift. Fueledpartly by the agendaof the DefenseAdvancedResearch ProjectsAgency (DARPA), a major sourceof American funding for both , and partly by the dramaticincrease speechand natural languageprocessing world wide in the availability of electronictexts, the two communitiesfound themselvesin close contact. The result for computationallinguists was that long-standingproblemsin their domain- for example, identifyingthe syntactic , or resolvingprepositionalphraseambiguity categoryof thewordsin a sentence in parsing- weretackledusingthe samesortsof statisticalmethodsprevalentin . Thespecifictechniquesvaried, but speechrecognition, oftenwith somesuccess all werefoundeduponthe ideaof inducingthe knowledgenecessaryto solvea problem by statistically analyzing large corpora of naturally occurring text, ratherthanbuilding in suchknowledgein the fonn of symbolicrules. Initially , the interestin corpus-basedstatisticalmethodsrekindledall the old controversies- rationalist vs. empiricist philosophies, theory-driven vs. datadrivenm , symbolic vs. statisticaltechniques(e.g., seediscussion in [ChurchandMercer, 1993]) . The BalancingAct workshopwe held in 1994 wasplannedwhenthe rhetoricwasat its height, at a time whenit seemedto us that, evenif somepeoplewereworking on commonground, not enoughpeople were talking about it. The field of computationallinguistics is now settling down somewhat:for themostpart, researchers havebecomelessunwaveringly adversarialover ideologicalquestions,andhaveinsteadbegunto focuson the searchfor a coherentcombinationof approach es. have Why things changed? First, there is an increasingrealization, within eachcommunity, that achievingcoregoalsmay requireexpertisepossessed by

Preface

esaddrobustnessandcoverageto traditionally the other. Quantitativeapproach brittle andnarrowsymbolicnaturallanguagesystems,permitting, for example, the automatedor semiautomated acquisitionof lexical knowledge(e.g., term inology, names, translationequivalents). At the sametime, quantitativeap aboutthe nature proachesare critically dependenton underlyingassumptions of the data, and more peopleare concludingthat pushingapplicationsto the next level of performancewill require quantitativemodelsthat are linguistically betterinformed; inductivestatisticalmethodsperformbetterin the faceof limited datawhenthey arebiasedwith accurateprior knowledge. A secondsourceof changeis the critical computationalresourcesnot widely availablewhenquantitativemethodswerelast in vogue. Fastcomputers,cheap disk space, CD-ROMs for distributing data, andfundeddata-collection initiatives have becomethe rule rather than the exception. The Brown Corpusof ' American English, Francis and KuCeras landmark project of the 1960s areannotated [KuCeraandFrancis, 1967], now hascompanionsthat arelarger, that from data of consist that multiple languages in morelinguistic detail, and . 1996 ICAME 1996 LDC , ]) . e. ; , [ ( g Third, thereis a generalpushtowardapplicationsthat work with languagein a broad, real-world context, rather than within the narrow domainsof traditional symbolicNLP systems.With the adventof suchbroadcoverageapplications , languagetechnologyis positionedto help satisfysomereal demandsin : large-vocabularyspeechrecognitionhasbecomea daily part the marketplace of life for many peopleunableto use a computerkeyboard[ Wilpon, 1994], into on-line rough automatictranslationof unrestrictedtext is finding its way services, and locating full text information on the World Wide Web has becomea priority [Foley andPitkow, 1994] . Applicationsof this kind arefaced with unpredictableinput from userswho are unfamiliar with the technology andits limitations, which makestheir tasksharder; on the otherhand, usersare adjusting to less than perfect results. All these considerations coverage, robustness , acceptabilityof gradedperformance- call out for systemsthattake advantageof large-scalequantitativemethods. is Finally, the resurgenceof interest in methodsgroundedin empiricism direction. in that back partly the result of an intellectualpendulumswinging Thus, evenindependentof applications, we seemore of a focus, on the scientific sideof computationallinguistics, on the propertiesof naturallyoccurring data, the objectiveandquantitativeevaluationof hypothesesagainstsuchdata, and the constructionof modelsthat explicitly take variability and uncertainty into account. Developmentsof this kind also have parallels in related areas ; in the latter such as sociolinguistics[Sankoff, 1978] and psycholinguistics

Preface

field, for example, probabilistic modelsof on-line sentenceprocessingtteat frequencyeffects, and more generally, weightedprobabilistic interactions, as fundamentalto the descriptionof on-line performance , in much the sameway that empiricistsseethe probabilistic natureof languageas fundamentalto its description(e.g. [ Tabossiet al., 1992]; also see [ Ferstl, 1993]) . This book focuseson the ttend toward empirical methodsas it bearson the engineering side of NLP, but we believe that ttend will also continueto have important implicationsfor the studyof languageasa whole. The premiseof this book is that there is no necessityfor a polar division. Indeed, oneof our goalsin this book is to changethat perception. We hold that es. thereis in fact no contradictionof defectioninvolvedin combiningapproach es to languageis a Rather, combining " symbolic" and " statistical" approach kind of balancingact in which the symbolic and the statisticalare properly thoughtof asparts, both essential,of a unified whole. The complementarynatureof the contributionof theseseeminglydiscrepant esis not ascontradictoryasit seems.An obviousfact that is often forgottenis approach that everyuseof statisticsis basedupona symbolicmodel. No matter what the application, statisticsare founded upon an underlying probability model, andthat modelis, at its core, symbolicandalgebraicratherthancontinuous andquantitative. For language,in particular, the naturalunits of manipulation in any statistical model are discrete constructs such as phoneme, morpheme, word, and so forth, as well as discreterelationshipsamongthese constructssuch as surface adjacencyor predicate-argument relationships. Regardlessof the detailsof the model, the numericalprobabilitiesare simply ' . On meaninglessexceptin the contextof the model s symbolicunderpinnings " " this view, thereis no suchthings asa purely statistical method. Evenhidden Markov models, the exemplarof statisticalmethodsinheritedfrom the speech community, arebasedupon an algebraicdescriptionof languagethat amounts to an assumptionof fmite-state generativecapacity. Conversely, symbolic underpinningsalonearenot enoughto capturethe variability inherentin naturally occurring linguistic data, its resistanceto inflexible, tersecharacteriza tions. In short, the essenceof the balancingact can be found in the opening chaptersof any elementarytext on probability theory: the core, symbolic underpinningsof a probability model reflect thoseconstraintsand assumptions that mu~t be built in, and form the basisfor a quantitativeside that reflects of preferences . uncertainty, variability, andgradedness The aim of this book is to explore the balancingact that must take place es are brought together- it contains when symbolic and statisticalapproach foreshadowingsof powerful partnershipsin the makingbetweenthe more lin -

Preface

es within the tradition of generativegrammar guistically motivatedapproach and the more empirically driven approach es from the tradition of infonnation . Research of this kind theory requiresbasicchoices: What knowledgewill be representedsymbolically and how will it be obtained? What assumptions underliethe statisticalmodel? What principlesmotivatethe symbolic model? Whatis theresearchergainingby combiningapproach es? Thesequestions,and the metaphorof the balancingact, provide a unifying themeto the contributions in this volume. References

L. R. BabI, F. Jelinek . 1983.A maximumlikelihoodapproach , andR. L. Mercer to continuous . IEEETransactions on speech Pattern recognition and Machine IntelAnalysis . liRence --190. , PAMI-5:179 NoamChomsky. 1957. SyntacticStructures. The Hague, Mouton. KennethW. ChurchandRobertMercer. 1993. Introductionto the specialon computationallinguistics usinglargecorpora. ComputationalLinguistics, 19( 1) :1- 24. JamesL. Flanagan. 1972. Speechanalysis, synthesisandperception, 2nd edition. New York, Springer-Verlag. Evelyn Ferstl. 1993. The role of lexical informationand discoursecontextin syntactic : a review of psycholinguisticstudies. Cognitive ScienceTechnical processing Report 93-03, Universityof Coloradoat Boulder. Jim Foley and JamesPitkow, editors. 1994. ResearchPriorities for the World-Wide Web: Reportofthe NSF workshopsponsoredby theIn/ormation, Robotics, and Intelligent SystemsDivision. NationalScienceFoundation, October1994. BarbaraGrosz. TEAM : a transportablenaturallanguageinterfacesystem. InProceedings of the Conferenceon AppliedNatural LanguageProcessing.Associationfor ComputationalLinguistics, Morristown, N.J., February1983. ICAME. ICAME corpuscollection. World Wide Web page, 1996. http:// nora.hd.uib. no/corpora.html. H. KuCeraand W. Francis. 1967. ComputationalAnalysis of PresentDay American English. Providence,R.I ., Brown University Press. LOC. Linguistic Data Consortium( LDC) home page. World Wide Web page, June 1996. http:// www.cis.upenn.edu/ - idc/ . StanleyR. Petrick. 1971. Transformationalanalysis. In RandallRustin, editor, Natural LanguageProcessing.New York, Algorithmics Press. David Sankoff. 1978. Linguistic variation: Modelsandmethods. New York, Academic Press. ClaudeE. ShannonandWarrenWeaver. 1949. TheMathematicalTheory Communication of . Urbana, University of Dlinois Press.

Preface

. Patrizia Tabossi, Michael Spivey-Knowlton, Ken McRae, and Michael Tanenhaus 1992. Semanticeffects on syntacticambiguity resolution: evidencefor aconstraintbasedresolutionprocess.Attentionand Performance, 15: 598- 615. Jay G. Wilpon. 1994. Applicationsof Voice-ProcessingTechnologyin Telecommunications . In David B. Roe andJay G. Wilpon, editors, VoiceCommunicationsBetween Humansand Machines. WashingtonD .C., National Academyof Sciences , National Press . Academy W. A. Woods and R. Kaplan. 1971. The lunar sciencesnatural languageinfonnation system. TechnicalReport2265. Cambridge,Mass., Bolt, Beranek, andNewman.

Acknowledgments

Sincetimeis theoneimmaterialobjectwhichwecannotinfluence- neitherspeedup norslowdown, addto nordiminish- it ~s animponderably valuablegift. ' - MayaAngelou , Wouldnt TakeNothing/or MyJourneyNow Many peoplehavegiven of their time in the preparationof this book, from its first stagesasa workshopto its fmal stagesof publication. The first setof pe0Pie to thankarethosewho submittedpapersto the original workshop. We had an overwhelmingnumberof very high-quality paperssubmitted, andregretted not being able to run a longer workshopon the topic. The issueof combining es is clearly part of the researchagendaof many computationallinapproach as . Thoseauthorswho havechapters guists, demonstrated by thesesubmissions in this book have revised them severaltimes in responseto two rounds of reviews, andwe aregrateful to themfor their efforts. Our anonymousreviewers for thesechaptersgavegenerouslyof their time- each article wasreviewed severaltimes, andeachreviewerdid a carefulandthoroughjob- - andalthough they are anonymousto the outsideworld, their generosityis known to themselves , andwe thankthemquietly. We alsodeeplyacknowledgethe time Amy Pierceof The MIT Pressgaveto us at many stagesalong the way. Her vision and insight havebeena gift , and shehascontributedto ensuringthe excellent quality of the fmal setof chaptersin the book. We aregratefulto the Associationfor ComputationalLinguistics (ACL ) for its supportandsupportiveness , especiallyits fmancialcommitmentto the Balancing Act workshop- anddoublypleasedthat theattendanceat the workshop helpedus give somethingtangible back to the organization. The ACL 1994 conferenceand post-conferenceworkshopswere held at New Mexico State University, with local arrangementshandled efficiently and graciously by JanyceWiebe; we thank her for her time and generosityof spirit. We would also like to thank Sun MicrosystemsLaboratoriesfor its supportiveness

throughoutthe processof organizingthe workshopand putting togetherthis book, especially Cookie Callahanof Sun Labs. Finally, we thank Richard . SproatandEvelyneTzoukennannfor their valuablediscussions We have enjoyedthe experienceof working on this topic, since the challenge of combiningwaysof looking at the world intriguedeachof us independently beforewe joined forcesto run the workshopand subsequentlyedit this book. Oneof ushastraining in theoreticallinguistics, andhasslowly beenconverted to an understandingof the role of perfonnancedataeven in linguistic . theory Theotherhadfonnal educationin computerscience,with healthydoses of linguistics and psychology, and so arrived in the field with both points of view. We are finding that more and more of our colleaguesare coming to believe that maintaining a balanceamong several approach es to language and is an act worth . analysis understanding pursuing

Chapter Statistical

1 Methods

Steven Abney

In general , the view of the linguist toward the use of statistical methods was shaped by the division that took place in the late 1950s and early 1960s between the language engineering community ( e.g . [ f ngve, 1954] ) and the linguistics community (e.g . [ Chomsky, 1964] ) . When Chomsky outlined the three levels of adequacy- observational , descriptive , and explanatory - much of what was in progress in the computational community of the time was labeled as either observational or descriptive with relatively little or no impact on the goal of producing an explanatorily adequate theory of language . The compu tationallinguist was said to deal just with perfonnance , while the goal of linguistics is to understand competence. This point of view was highly influential then and persists to this day as a set of a priori assumptions about the nature of computational work on language . ' Abney s chapter revisits and challenges these assumptions, with the goal of illustrating to the linguist what the rationale might be for the computational linguist in pursuing statistical analyses. He reviews several key areas of linguistics , specifically language acquisition , language change, and language variation , showing how statistical models reveal essential data for theory building and testing . Although these areas have typically used statistical modeling , Abney goesfurther by addressing the central figure of generative grammar : the adult monolingual speaker. He argues that statistical methods are of great interest even to the theoretical linguist , because the issues they bear on are in fact linguistic issues, basic to an understanding of human language . Finally , Abney defends the provocative position that a weighted grammar is the correct model for explanation of several central questions in linguistics , such as the nature of parameter setting and degrees of grammaticality .- - Eds.

1 Chapter In the spaceof the last 10 years, statisticalmethodshavegonefrom beingvirtually unknownin computationallinguistics to being a fundamentalgiven. In 1996, no one can professto be a computationallinguist without a passing ' knowledgeof statisticalmethods. HMM s are as de rigeur as LR tables, and anyonewho cannotat leastusethe tenninology persuasivelyrisks being mistaken for kitchenhelp at the ACL banquet. More seriously, statisticaltechniqueshave broughtsignificant advancesin broad-coverage language processing . Statistical methods have made real progresspossibleon a numberof issuesthat had previouslystymiedattempts to liberatesystemsfrom toy domains: issuesthat includedisambiguation , error correction, and the inductionof the sheervolume of infonnation requisitefor handlingunrestrictedtext. And the senseof progresshasgenerateda greatdeal of enthusiasmfor statisticalmethodsin computationallinguistics. However, this enthusiasmhasnot beencatchingin linguistics proper. It is alwaysdangerousto generalizeaboutlinguists, but I think it is fair to saythat mostlinguistsareeither unaware(and unconcerned ) abouttrendsin computa. The gulf in basicassumptions tionallinguistics, or hostileto currentdevelopments is simply too wide, with the resultthatresearchon the othersidecanonly seemnaive, ill -conceived, anda completewasteof time andmoney. In part the differenceis a differenceof goals. A largepart of computational linguisticsfocuseson practicalapplications,andis little concernedwith human . Nonetheless , at leastsomecomputationallinguistsaim to languageprocessing advanceour scientific understandingof the humanlanguagefaculty by better the computationalpropertiesof language . Oneof the mostinteresting understanding andchallengingquestionsabouthumanlanguagecomputationisjust how peopleareableto dealsoeffortlesslywith the very issuesthat makeprocessing unrestrictedtext so difficult . Statisticalmethodsprovide the most promising currentanswers , andasa resultthe excitementaboutstatisticalmethodsis also sharedby thosein the cognitivereachesof computationallinguistics. In thischapter,I would like to communicatesomeof thatexcitementto fellow . Thereis no denying , to makeit comprehensible linguists, or at least, perhaps that there is a culture clashbetweentheoreticaland computationallinguistics thatservesto reinforcemutualprejudices.In caricature,computationallinguists believe that by throwing more cycles and more raw text into their statistical black box, they candispensewith linguistsaltogether,alongwith their fanciful RubeGoldbergtheoriesaboutexoticlinguisticphenomena . The linguist objects that, evenif thoseblack boxesmakeyou oodlesof moneyon speechrecognizers andmachine-translationprograms(which they do not), they fail to advance our understanding . I will try to explainhow statisticalmethodsjust might contribute to understanding of the sortthat linguistsareafter.

StatisticalMethodsandLinguistics

This paper, then, is essentiallyanapology, in the old senseof apology. I wish to explainwhy we would do sucha thing asto usestatisticalmethods, andwhy they arenot really sucha badthing, maybenot evenfor linguisticsproper.

I think the mostcompelling, thoughleastwell-developed,argumentsforstatistical methodsin linguistics comefrom the areasof languageacquisition, language variation, andlanguagechange. LanguageAcquisition Under standardassumptionsaboutthe grammar, we would expectthecourseof languagedevelopmentto be characterized by abrupt , eachtime thechild learnsor altersa rule or parameterof the grammar. changes If , as seemsto be the case, changesin child grammarare actuallyreflectedin changesin relativefrequenciesof structuresthatextendover monthsor more, it is hard to avoid the conclusionthat the child has a probabilisticor weighted grammarin somefonn. Thefonn that wouldperhapsbe leastoffensiveto mainstream sensibilitiesis a grammarin which the child " tries out" rulesfor a time. During the trial period, both the new andold versionsof a rule coexist, andthe probabilityof usingoneor the otherchangeswith time, until the probabilityof using the old rule finally dropsto zero. At any given point, in this picture, a child' s grammaris a stochastic(i.e., probabilistic) grammar. An aspectof this little illustration that bearsemphasizingis that the probabilities are addedto a grammar of the usual sort. A large part of what is meant by " statistical methods" in computationallinguistics is the study of stochasticgrammarsof this fonn: grammarsobtainedby addingprobabilities in a fairly transparentway to " algebraic" (i.e., nonprobabilistic) grammars. Stochasticgrammarsof this sort do not constitutea rejection of the underlying . This is quite different from algebraicgrammars, but a supplementation someusesto which statisticalmodels(mostprominently, neuralnetworks) are put, in which attemptsare madeto model someapproximationof linguistic behaviorwith an undifferentiatednetwork, with the result that it is difficult or ' impossibleto relatethe network s behaviorto a linguistic understandingof the sort embodiedin an algebraicgrammar. (It should, however, be pointed out that the problemwith suchapplicationsdoesnot lie with neuralnets, but with the unenlighteningway they aresometimesput to use.) Language Change Similar commentsapply, on a larger scale, to language change. If the units of changeare as algebraicgrammarslead us to expectrules or parametersor the like - we would expectabrupt changes.We might

ChapterI

" " expectsomeoneto go down to the local pub oneevening, order Ale!, andbe servedan eel instead, becausethe Great Vowel Shift happenedto him a day too early.1 In fact, linguistic changesthat are attributed to rule changesor changes of parameter settings take place gradually, over considerable stretches of time measuredin decadesor centuries. It is more realistic to assumethat the languageof a speechcommunity is a stochasticcompositeof the languagesof the individual speakers , describedby a stochasticgrammar. " " In the stochastic community grammar, the probability of a given construction reflects the relative proportion of speakerswho use the constructionin question. Languagechangeconsistsin shifts in relative frequency of construction (rules, parametersettings, etc.) in the community. If we think of speechcommunities as populations of grammarsthat vary within certain bounds, and if we think of languagechangeas involving gradualshifts in the center of balanceof the grammarpopulation, then statisticalmodels are of immediateapplicability [Tabor, 1994] . In this picture, we might still continueto assumethat an adult monolingual es a particular algebraicgrammar, and that stochasticgrammars speakerpossess areonly relevantfor the descriptionof communitiesof varyinggrammars. However, we must at leastmake allowancefor the fact that individuals routinely comprehendthe languageof their community, with all its variance. This rather suggeststhat at leastthe grammarusedin languagecomprehensionis stochastic . I returnto this issuebelow.

of language variationI havein LanguageVariation Therearetwo senses mindhere:dialectology , ontheonehand,andtypology , ontheother.It hasbeen that somelanguages consistof a collectionof dialectsthat blend suggested one into the other to the aremoreorlessarbitrary , smoothly pointthatthedialects in . Forexample Inuit as" a fairly unbroken , Tait describes points a continuum chainof dialects , with mutualintelligibilitylimitedto proximityof contact , the furthestextremes of the continuumbeingunintelligibleto eachother " [ Tait, 1994 , p. 3] . To describethedisbibutionof Latin-Americannativelanguages , Kaufman definesa language as" a geographic zonethat complex ally continuous contains thanthatfoundwithina singlelanguage ..., linguisticdiversitygreater butwhereinternallinguisticboundaries similarto thosethatseparate clearlydiscrete " Kaufman1994 . 31 . Thecontinuousness are of , ,p ] languages lacking [ with distance is consistent withthepictureof a speech community changes geographic withgrammatical variance above . Withgeographic distance , assketched , 1. I havereadthis anecdotesomewherebefore, but havebeenunableto fmd the citation . My apologiesto the unknownauthor.

andLin9.Uistics Methods Statistical the mix of frequencyof usageof variousconstructionschanges , anda stochastic , 1995]. grammarof somesortis an appropriatemodel[ Kessier Similar commentsapply in the areaof typology, with a twist. Many of the universalsof languagethat have been identified are statistical rather than absolute, including rough statementsaboutthe probability distributionof language features(" head-initial and head-final languagesare about equally frequent " " or conditional ) probability distributions( postpositionsin verb-initial " languagesare more common than prepositions in verb final languages) [Hawkins, 1983, 1990]. Thereis asyet no modelof how this probability distribution comesabout, that is, how it arisesfrom the statisticalpropertiesof language change.Which aspectsof thedistributionarestable, andwhich would be ' different if we took a sampleof the world s languages10,000 yearsago or 10,000 yearshence? There is now ~ vast body of mathematicalwork on stochastic esandthe dynamicsof complexsystems(which includes, but is process not exhaustedby, work on neuralnets), much of which is of immediaterelevance to thesequestions. In short, it is plausibleto think of all of theseissues- languageacquisition, languagechange, and languagevariation- in terms of populationsof ~ mars, whetherthosepopulationsconsistof grammarsof different speakersor setsof hypothesesa languagelearnerentertains. When we examine.populations of grammarsvarying within bounds, it is naturalto expectstatisticalmodels to provideusefultools.

2 Adult MonolingualSpeakers ? Ever sinceChomsky, linguistics But whataboutanadultmonolingualspeaker hasbeenfmnly committedto the idealizationto an adult monolingualspeaker in a homogeneousspeechcommunity. Do statisticalmodelshaveanythingto sayaboutlanguageunderthat idealization? In a narrowsense,I think the answeris probablynot. Statisticalmethodsbear mostly on all the issuesthat are outsidethe scopeof interestof currentmainstream , though, I think that saysmore aboutthe linguistics. In a broadersense narrownessof the currentscopeof interestthanaboutthe linguistic importance of statisticalmethods.Statisticalmethodsareof greatlinguistic interestbecause the issuestheybearon arelinguistic issues,andessentialto anunderstandingof what humanlanguageis and what makesit tick. We must not forget that the idealizationsthat Chomskymadewere an expedient, a way of managingthe vastnessof our ignorance. One aspectof languageis its algebraicproperties, but that is only one aspectof language, and certainly not the only important

Chapter!

aspect. Also importantare the statisticalpropertiesof languagecommunities. And stochasticmodelsare also essentialfor understandinglanguageproduction andcomprehension , particularly in the presenceof variation andnoise. (I focus here on comprehension , though considerationsof languageproduction have also provided an important impetusfor statisticalmethodsin computationallinguistics [Smadja, 1989, 1991] .) To a significantdegree, I think linguisticshaslost sight of its original goal, andturnedChomsky's expedientinto anendin itself. Currenttheoreticalsyntax givesa systematicaccountof a very narrowclassof data, judgmentsaboutthe well-formednessof sentencesfor which the intendedstructureis specified, wherethejudgmentsareadjustedto eliminategradationsof goodnessandother complications.Linguistic dataother than structurejudgmentsare classifiedas " " performance data, andthe adjustmentsthat areperformedon structure-judgment dataaredeemedto be con-ectionsfor " performanceeffects." Performance is consideredthedomainof psychologists , or at least, not of concernto linguists. The term performance suggeststhat the things that the standardtheory abstractsawayfrom or ignoresarea naturalclass; they aredatathatbearon language processingbut not languagestructure. But in fact a good deal that is " is not labeled" performance computationalin any essentialway. It is more accurateto considerperformanceto be negativelydefmed: it is whateverthe grammardoesnot accountfor. It includesgenuinelycomputationalissues,but a gooddealmorethat is not. OneissueI would like to discussin somedetail is the issue of grammaticality and ambiguity judgments about sentencesas opposedto structures.Thesejudgmentsareno moreor lesscomputationalthan , but it is difficult to give a good accountof them judgmentsabout structures with grammarsof the usual sort; they seemto call for stochastic, or at least weighted, grammars. 2.1 Grammaticality and Ambiguity Considerthe following : ( I ) a. The a areof I b. The cowsaregrazingin the meadow c. JohnsawMary The questionis the statusof theseexampleswith respectto grammaticalityand ambiguity. The judgmentshere, I think, are crystal clear: ( I a) is word salad, and ( I b) and(c) areunambiguoussentences . In point of fact, ( I a) is a grammaticalnoun phrase, and ( I b) and (c) are ambiguous,the nonobviousreadingbeingasa nounphrase.Consider: anare is a measureof area, asin a hectareis a hundredares, andlettersof the alphabet

StatisticalMethodsandLinguistics

" may be usedasnounsin English( Writtenon the sheetwasa singlelowercase " " a, As describedin section2, paragraph b . . ." ). Thus ( 1a) hasa structurein which are andI are headnouns, anda is a modifier of are. This analysiseven becomesperfectlynaturalin the following scenario.Imaginewe aresurveyors, and that we havemappedout a pieceof land into large segments , designated with capitalletters, andsubdividedinto one-are subsegments , designatedwith lowercaseletters. ThenThea are of I is a perfectlynaturaldescriptionfor a particular parcelon our map. As for ( 1b), are is againthe headnoun, cowsis a premodifier, andgrazingin the meadowis a postmodifier. It might be objectedthat plural nounscannotbe nominalpremodifiers, but in fact they often are: considerthe bondsmarket, a securitiesexchange , he is vicepresidentandmediadirector, an in-homehealth care servicesprovider, Hartford ' s claims division, the financial -services industry, its line of systemsmanagementsoftware. (Severalof theseexamples areextractedfrom the Wall StreetJournal.) It mayseemthatexamples( la ) and(b) areillustrativeonly of a trivial andartificial problemthat arisesbecauseof a rare usageof a commonword. But the " " problemis not trivial: withoutanaccountof rareusage, we haveno way of distinguishing betweengenuineambiguitiesandthesespuriousambiguities.Alternatively one , might objectthat if onedoesnot know that are hasa readingasa noun, thenare is actuallyunambiguousin one' s idiolect, and ( la ) is genuinely . But in thatcasethequestionbecomeswhy a hectareis a hundred ungrammatical aresis notjudgedequallyungrammaticalby speakersof theidiolectin question. Further, ( lc ) illustratesthattherareusageis not anessentialfeatureof examples (a) and (b). Sawhasa readingasa noun, which may be lessfrequentthan the verb reading, but is hardly a rareusage. Propernounscanmodify (Gatling gun) and be modified by (TyphoidMary) commonnouns. Hence, John saw Mary hasa readingas a noun phrase, referring to the Mary who is associated with a kind of sawcalleda Johnsaw. It may be objectedthat constructionslike Gatling gun and TyphoidMary belongto the lexicon, not thegrammar, but howeverthat maybe, they arecompletely productive. I may not know whatCohenequations,theRussiahouse, or ' Abney sentencesare, but if not, then the denotataof Cohens equations, the ' Russianhouse, or thosesentencesof Abney s are surely equally unfamiliar.2 2. There are also syntactic groundsfor doubt about the assumptionthat noun-noun modificationbelongsto the lexicon. Namely. adjectivescanintervenebetweenthemodifying noun and the headnoun. (Examplesare given later in this section.) If adjective modification belongsto the syntax, and if thereare no discontinuouswords or movement of piecesof lexical items, thenat leastsomemodificationof nounsby nounsmust tllke placein the syntax.

Chapter}

LikewiseI maynotknowwhopeglegPeterefersto, or riverboatSally, butthat . doesnotmaketheconstructions or productive anylessgrammatical Theproblemis epidemic and it snowballs as sentences , growlonger. One unremarkable sentences oftenhearsin computational linguisticsaboutcompletely . Nor is it with hundreds of parses , andthatis in fact no exaggeration If theundesired a of a . one examines merely consequencehaving poorgrammar one finds that are , and , analyses generally they extremelyimplausible " " violenceto soft constraints like heaviness constraints oftendo considerable or thenumberandsequence of modifiers , butno onepieceof thestructureis . outrightungrammatical consider this sentence To illustrate , , drawnmoreor lessat randomfrom a ' book(Quines WordandObject) drawnmoreor lessatrandomfrommy shelf: relevant is epistemologically , assuggesting (2) In a generalwaysuchspeculation in the environment howorganisms and maturing evolving physical endupdiscoursing of abstract weknowmightconceivably objects aswedo [Quine, 1960,p. 123]. thissentence Oneof themanyspuriousstructures mightreceiveis thefollowing : (3)

s === : == : = = ---::== -----== --- ----- ------:: : = :::: : :: Absolute PP AdiP "'- - - - -- - - -- - - - - "'-----...",,~ PP organisms andevolving .. relevant Inageneral maturing wayRC epistemologically ...",,~ .....",,~ how such is assuggesting speculation ,

- - - - ----- NP - - - - - --.......VP -- - ....-........ I we know -S - - -- - - NP VP "' ...",,~ --- ----aswedo objects

AP might Ptcpl " " " -""of '"abstrac " " " " ' " end conceivably up discoursin

There are any number of criticisms one can direct at this structure, but I believe none of them are fatal . It might be objected that the PP-AdiP - Absolute sequenceof sentential premodifiers is illegitimate , but each is individually fine , and there is no hard limit on stacking them. One can even come up with relatively good examples with all three modifiers , e.g . [ppon the beach] [ AdiPnaked

StatisticalMedIads andLlDgni ~tic~

asjaybirds] [Absolute waveslappingagainsttheshore] the wild boyscarriedout their bizarre rituals. Anotherpoint of potentialcriticismis thequestionof licensingtheelidedsentence afterhow. In fact its contentcouldeitherbe providedfrom precedingcontext or from therest of the sentence , asin thoughas yet unableto explainhow, astronomersnow knowthat starsdevelopfrom specksof grit in giant oysters. Might is takenhereasa noun, asin mightand right. The AP conceivablyend up maybea bit mysterious: endup is hereanadjectival, asin we turnedthebox end up. Abstractis unusualasa massnoun, but can in fact be usedasone, as, for example, in the article consistedof threepagesof abstract and only two pagesof actual text. Onemight object that the NP headedby might is badbecauseof the multiple postmodifiers,but in fact thereis no absoluteconstraintagainststackingnominal postmodifiers,andgoodexamplescanbe constructedwith the samestructure : marlinespikes , businessend up, sprinkled with tabascosauce, can be a poweiful deterrent against pigeons. Even the commas are not absolutely required. The strengthof preferencefor themdependson how heavythe modifiers are: cf. strengthjudiciously applied increasesthe effectiveness of diplomacy , a cupof peanutsunshelledin the stockaddscharacter.3 In short, the structure(3) seemsto be best characterizedas grammatical, thoughit violatesany numberof parsingpreferencesandis completelyabsurd. Onemight think that onecouldeliminateambiguitiesby turning someof the into absoluteconstraints.But attemptingto eliminateunwanted dispreferences readingsthat way is like squeezinga balloon: everydispreferencethat is turned into an absoluteconstraintto eliminateundesiredstructureshasthe unfortunate side effect of eliminating the desiredstructurefor some other sentence . No matterhow difficult it is to think up a plausibleexamplethat violatesthe constraint , somewriter hasprobablyalreadythoughtone up by accident, and we will improperlyreject his sentenceas ungrammaticalif we turn the dispreference into an absoluteconstraint. To'illustrate: if a noun is premodifiedby both an adjective and anothernoun, standardgrammarsrequire the adjectiveto comefirst, inasmuchasthe nounadjoinsto ~ but the adjectiveadjoinsto N. It is not easyto th~ up goodexamplesthat violate this constraint. Perhapsthe readerwould careto try beforereadingtheexamplesin the footnote.4 3. Cf. this passagefrom Tolkien: "Their clotheswere mendedas well as their bruises their tempersand their hopes. Their bagswere filled with food and provisions light to carry but strongto bring themover the mountainpasses ." [ Tolkien, 1966, p. 61] 4. Maunder climatic cycles, ice-core climatalogical records, a Kleene-star transitive closure, Precambrianera solar activity, highlandigneousformations.

1 Chapter Not only is my absurdanalysis(3) arguablygrammatical, there are many, many equally absurdanalysesto be found. For example, general could be a noun (the army officer) insteadof an adjective, or evolving in could be analyzed as a particle verb, or the physical could be a noun phrase(a physical exam} - not to mention various attachmentambiguitiesfor coordinationand modifiers, giving a multiplicative effect. The consequenceis considerable . ambiguityfor a sentencethat is perceivedto be completelyunambiguous a I am. But it is and I I am Now perhapsit seems perversity suppose beingperverse, that is implicit in grammaticaldescriptionsof the usual sort, and it emergesunavoidablyassoonaswe systematicallyexaminethe structuresthat . Either the grammarassignstoo many structures the grammarassignsto sentences 2 it or like to sentences ( ), incorrectly predictsthat exampleslike three pages of abstract or a cup of peanutsunshelledin the stock have no well formedstructure. To sumup, thereis a problemwith grammarsof the usualsort: their predictions aboutgrammaticalityandambiguityaresimply not in accordwith human . The problemof how to identify the correctstructurefrom among perceptions the in-principle possiblestructuresprovidesone of the centralmotivationsfor the use of weighted grammarsin computationallinguistics. A weight is assignedto eachaspectof structurepermittedby the grammar, andthe weight of a particular analysisis the combinedweight of the structuralfeaturesthat make it up. The analysiswith the greatestweight is predictedto be the perceived . analysisfor a given sentence Before describingin more detail how weightedgrammarscontributeto a solution to the problem, though, let me addressan evenmore urgentissue: is this evena linguistic problem?

2.2 Is This Linguistics? Under the usual assumptions , the fact that the grammarpredicts grammaticality and ambiguity wherenoneis perceivedis not a linguistic problem. The usual opinion is that perceptionis a matter of performance, and that grammaticality alone does not predict performance; we must also include nonlinguisti factors like plausibility and parsing preferencesand maybe even probabilities. Grammaticality and Acceptability The implication is that perceptionsof grammaticalityand ambiguity are not linguistic data, but performancedata. ? And This stanceis a bit odd- are not grammaticalityjudgmentsperceptions what do we meanby " performancedata?" It would be one thing if we were

StatisticalMethodsandLinguistics

talking aboutdatathat clearly haveto do with the courseof linguistic computation , datalike responsetimesandreadingtimes, or regressiveeyemovement , or even more outlandish things like positron emission tomofrequencies graphicscansor early receptorpotentialtraces. But humanperceptions(judgments , intuitions) about grammaticalityand ambiguity are classic linguistic data. What makesthe judgments concerningexamples( 1a--c) performance data? AU linguistic dataarethe resultof little informal psycholinguistic experiments thatlinguistsperformon themselves , andtheexperimentalmaterialsare " questionsof the form Can you say this?" " Does this mean this?" " Is this " " ? Are thesesynonymous ?" ambiguous Part of the answeris that the judgmentsabout examples( la--c) are judgments aboutsentencesaloneratherthan aboutsentenceswith specifiedstructures . The usualsortof linguisticjudgmentis ajudgmentaboutthe goodnessof a particularstructure, andexamplesentencesareonly significantasbearersof the structurein question. If any choiceof wordsandany choiceof contextcan be found that makesfor a good sentence , the structureis deemedto be good. The basic data arejudgmentsabout structuredsentencesin context- that is, sentences plus a specificationof the intendedstructureandintendedcontextbut thesebasicdataare usedonly groupedin setsof structuredcontextualized sentenceshavingthe same( possiblypartial) structure. Sucha setis defmedto begoodjust in caseany structuredcontextualizedsentenceit containsis judged to be good. Hencea greatdealof linguists' time is spentin trying to find some choiceof wordsandsomecontextto get a clearpositivejudgment, to showthat a structureof interestis good. As a result, thereis actuallyno intent that thegrammarpredict- that is, generate - individual structuredsentencejudgments. For a given structuredsentence , the grammaronly predictswhetherthereis somesentencewith the same structurethat is judged to be good. For the examples( 1), then, we shouldsaythat the structure [NPthe [Na] [Nare] [ppof [NI ]]] is indeedgrammaticalin the technicalsense, sinceit is acceptablein at least one context, and since every piece of the structureis attestedin acceptable sentences . The groupingof databy structureis not the only way that standard grammars fail to predict acceptability and ambiguity judgments. Judgmentsare rather smoothly graded, but goodnessaccording to the grammar is allor nothing. Discrepanciesbetweengrammar and data are ignored if they involve sentencescontainingcenterembedding, parsingpreferenceviolations,

Chapterl

" garden-patheffects, or in generalif their badnesscanbe ascribedto processing " S complexity. Grammar and Computation The differencebetweensttucturejudgments " data" in somesense andsbingjudgmentsis not thatthe formerare competence " " andthe latterare performancedata. Rather, the distinctionrestson a working assumptionabouthow the dataareto be explained, namely, that the dataarea result of the interactionof grammaticalconstraintswith computationalconstraints . Certainaspectsof thedataareassumedto bereflectionsof grammatical constraints , andeverythingelseis ascribedto failuresof the processorto translate grammaticalconstraintstransparentlyinto behavior, whetherbecauseof memorylimits or heuristicparsingstrategiesor whateverobscuremechanisms of judgments.We arejustified in ignoringthoseaspectsof the creategradedness . to the idiosyncraciesof the processor we ascribe that data . But this distinctiondoesnot hold up underscrutiny Dividing the humanlanguage capacityinto grammarand processoris only a mannerof speaking, a . It is naiveto expectthe of way dividing things up for theoreticalconvenience to to division correspond anymeaningfulphysiologlogical grammar/processor , onefunctioning ical division say, two physically separateneuronalassemblies es asa storeof grammarrules and the other as an activedevicethat access the grammar-rule store in the course of its operation. And even if we did , we have believein a physiologicaldivision betweengrammarand processor with not a distinction no evidenceat all to supportthat belief; it is any empirical content. A coupleof examplesmight clarify why I say that the grammar/processor . Grammarsand syntacticsttucdistinction is only for theoreticalconvenience , but turesareusedto describecomputerlanguagesaswell ashumanlanguages typical compilersdo not accessgrammarrules or consttuctparsetrees. At the level of descriptionof the operationof the compiler, grammar-rules andparse" treesexist only " virtually asabstractdescriptionsof the courseof the compu5. In addition, therearepropertiesof grammaticalityjudgmentsof a different sort that arenot beingmodeled, propertiesthat arepoorly understoodandsomewhatworrisome. arisenot infrequentlyamongjudges - it is moreoften the casethan not Disagreements that I disagreewith at leastsomeof thejudgmentsreportedin syntaxpapers,andI think seemto changewith changingtheoretical my experienceis not unusual. Judgments " : a sentencethat sounds" not too good whenoneexpectsit to be bad may assumptions ' " " . Andjudg in the if a sound not too bad grammarchangesone s expectations change mentschangewith exposure.Someconstructionsthat soundterrible on a first exposure improveconsiderably with time.

Statistical MethodsandLinguistics

13

tation beingperformed. What is separatelycharacterizedas, say, grammarvs. parsingstrategyat the logical level is completelyintenningledat the level of compileroperation. At the other extreme, the constraintsthat probablyhavethe strongestcomputationalflavor are the parsingstrategiesthat are consideredto underliegarden -path effects. But it is equally possibleto characterizeparsingpreferences in grammaticalterms. For example, the low attachmentstrategycanbe characterizedby assigninga cost to structuresof the form [ Xi+l Xi YZ] proportional to thedepthof the subtreeY.The optimal structureis theonewith the leastcost. Nothing dependson how treesare actually computed: the characterizationis only in termsof the shapesof trees. If we wish to makea distinction betweencompetenceand computation, an appropriatedistinction is betweenwhat is computedand how it is computed. " " issuesare , most performance not computationalissuesat all. By this measure the of Characterizing perceptions grammaticalityand ambiguity describedin the previoussectiondoesnot necessarilyinvolve any assumptionsabout the computationsdoneduring sentenceperception. It only involvescharacterizing the set of structuresthat are perceivedas belongingto a given sentence . That canbedone, for example, by defining a weightedgrammarthat assignscoststo trees, andspecifyinga constantC suchthatonly structureswhosecostis within distanceC of the beststructurearepredictedto be perceived. How the setthus definedis actuallycomputedduring perceptionis left completelyopen. We may think of competencevs. performancein terms of knowledgevs. computation,but that is merelya mannerof speaking.What is really at issueis an idealizationof linguistic datafor the sakeof simplicity. The Frictionless Plane, Autonomy and Isolation Appeal is often madeto an analogybetweencompetenceandfrictionlessplanesin mechanics . Syntacticians focus on the data that they believe to contain the fewestcomplicating factors, and " cleanup" the datato removewhat they believeto be remaining complicationsthat obscuresimple, generalprinciplesof language. That is properandlaudable, but it is importantnot to lose sight of the original problem, andnot to mistakecomplexityfor irrelevancy. The testof whether the simpleprincipleswe think we havefound actuallyhaveexplanatorypower is how well they fare in makingsenseof the largerpicture. Thereis alwaysthe dangerthat the simpleprincipleswe arrive at areartifactsof our dataselection and data adjustment. For example, it is sometimesremarkedhow marvelous it is that a biological systemlike languageshouldbe so discreteandclean, but in fact there is abundantgradednessand variability in the original data; the

Chapter1 evidence for the discretenessand cleannessof language seemsto be mostly evidence we ourselves have planted . It has long been emphasized that syntax is autonomous. The doctrine is older " 6 than Chomsky ; for example, Tesniere [ Tesniere, 1959, p . 42 ] writes . . . la " ' ' syntaxe n a a chercher sa propre loi qu en elle meme. Elle est autonome . To illustrate that structure cannot be equated with meaning, he presents the sentence pair : Ie signal vert indique Ie Vole libre Ie symbole veritable impose Ie vitesse lissant ' The similarity to Chomsky s later but more famous pair revolutionary new ideas appear infrequently colorless green ideas sleep furiously is striking . But autonomy is not the same as isolation . Syntax is autonomous in the sense that it cannot be reduced to semantics; well - formedness is not identical to meaningfulness. But syntax in the sense of an algebraic grammar is only one piece in an account of language, and it stands or falls on how well it fits into the larger picture .

The Holy Grail The largerpicture, andthe ultimategoal of linguistics, is to describelanguagein the senseof that which is producedin languageproduction in languagecomprehension , acquiredin languageacquisition , comprehended varies in which that in and , , aggregate , languagevariation andchangesin languagechange. I havealwaystakenthe Holy Grail of generativelinguisticsto be to characterize a class of models, each of which representsa particular (potentialor actual) human languageL , and characterizesa speakerof L by defming the classof sentencesa speakerof L produces, the structuresthat a speakerof L ; in short, by predictingthe linguistic datathat characterize perceivesfor sentences a speakerof L. A "Turing test" for a generativemodelwould be somethinglike the following that are at random, the sentences . If we usethe modelto generatesentences producedarejudged by humansto be clearly sentencesof the language- to " soundnatural." And in the otherdirection, if humans judge a sentence(or non' 6. The cited work was completedbeforeTesnieres deathin 1954, thoughit was not publisheduntil 1959.

StatisticalMethodsandLinguistics

15

sentence) to have a particular sbUcture, the model should also assign precisely that sbUcture to the sentence.

Natural languagesare such that these tests cannot be passedby an unweighted grammar. An unweighted grammar distinguishes only between grammaticalandungrammaticalsb' uctures,andthat is not enough. " Sounding natural" is a matterof degree. What we must meanby " randomlygenerating " is that natural-soundingsentences sentencesare weightedby the degreeto which they sound natural, and we samplesentenceswith a probability that accordswith their weight. Moreover, the sb' ucturethat peopleassignto a sentence is the sb' ucturetheyjudge to havebeenintendedby the speaker,andthat judgmentis alsoa matterof degree. It is not enoughfor the grammarto define the set of sb' ucturesthat could possibly belong to the sentence ; the grammar shouldpredictwhich sb' uctureshumansactuallyperceive, andwhattherelative weights are in caseswhere humansare uncertainabout which sb' ucturethe speakerintended. The long andlittle of it is, weightedgrammars(andother speciesof statistical methods) characterizelanguagein sucha way asto makesenseof language , acquisition, variation, and change. Theseare linguistic production, comprehension , andnot computationalissues,a fact that is obscuredby labelingeverything " " perfonnance that is not accountedfor by algebraicgrammars.What is " " really at stakewith competence is a provisionalsimplifying assumption , or an expressionof interestin certain subproblemsof linguistics. There is certainly no indicting an expressionof interest, but it is importantnot to losesight of the largerpicture.

3 HowStatisticsHelps Acceptingthat thereare divergencesbetweentheory and data- for example, the divergencebetweenpredictedand perceivedambiguity- and accepting that this is a linguistic problem, and that it is symptomaticof the incompleteness of standardgrammars, how does adding weights or probabilities help makeup the difference? Disambiguation As alreadymentioned, the problemof identifying the correct parse- the parsethat humansperceive- amongthe possibleparsesis a central applicationof stochasticgrammarsin computationallinguistics. The problemof defmingwhich analysisis correctis not a computationalproblem, however; thecomputationalproblemis describingan algorithmto computethe correctparse. Thereare a variety of approach es to the problemof defining the

Chapter1

correctparse. A stochasticcontext-freegrammarprovidesa simpleillustration. Considerthe sentenceJohn walks, andthe grammar (4) 1. 2. 3. 4. 5. 6. 7.

S - NPV S - NP NP - N NP - NN N - John N - walks V - walks

.7 .3 .8 .2 .6 .4 1.0

, oneasa sentenceand Accordingto grammar(4), John walkshastwo analyses oneasa nounphrase. (The rule S NP representsan utteranceconsistingof a single noun phrase.) The nu. mbersin the rightmost column representthe weightsof rules. The weight of an analysisis the productof the weightsof the rules usedin its derivation. In the sententialanalysisof John walks, the derivation consistsof rules 1, 3, 5, 7, so the weight is (.7)(.8)(.6)( 1.0) = .336. In the noun-phraseanalysis, the rules 2, 4, 5, 6 are used, so the weight is (.3)(.2)(.6)(.4) = .0144. The weight for the sententialanalysisis muchgreater, predicting that it is the one perceived. More refined predictions can be obtainedby hypothesizingthat an utteranceis perceivedas ambiguousif the " " next-best caseis not too much worsethan the best. If not too much worse is interpretedasa ratio of , say, not more than 2:1, we predict that John walks is perceivedas unambiguous, as the ratio betweenthe weights of the parses is 23: 1: Gradations of acceptability are not accommodated Degrees of Grammaticality in algebraic grammars: a structure is either grammatical or not. The idea of degrees of grammaticality has been entertained from time to time , and some " " classes of ungrammatical structures are informally considered to be worse than others (most notably , Empty Category Principle (ECP) violations vs. sublacency violations ) . But such degrees of gramrnaticality as have been considered have not been accorded a formal place in the theory . Empirically , acceptability judgments vary widely across sentences with a given structure, depending on lexical choices and other factors. Factors that cannot be reduced 7. The hypothesisthat only the beststructure(or possibly, structures ) areperceptibleis esto syntaxin which grammaticalityis definedas somewhatsimilar to currentapproach optimal satisfactionof constraintsor maximal economyof derivation. But I will not . hazarda guesshereaboutwhetherthat similarity is significantor merehappenstance

StatisticalMethodsandLinguistics

to a binary grammaticalitydistinction areeither poorly modeledor ignoredin standardsyntacticaccounts. Degreesof grammaticalityarise as uncertaintyin answeringthe question " Can " you sayX? or perhapsmore accurately, " If you said X , would you feel " you had madean error? As such, they reflect degreesof error in speechproduction . The null hypothesisis that the samemeasureof goodnessis usedin both speechproduction and speechcomprehension , though it is actually an open question. At any rate, the measureof goodnessthat is important for is not degreeof grammaticalityalone, but a global measure speechcomprehension that combinesdegreesof grammaticalitywith at least naturalnessand " . structuralpreference(i.e., " parsingstrategies ) We must also distinguish degreesof grammaticality, and indeed, global , from theprobability of pro. ducinga sentence goodness . Measuresof goodness and probability are mathematicallysimilar enh cementsto algebraicgrammars ~ , but goodnessalonedoesnot determineprobability. For example, for an infinite language, probability must ultimately decreasewith length, though arbitrarily long sentences may be perfectlygood. Perhapsonereasonthat degreesof grammaticalityhavenot found a placein standardtheory is the questionof wherethe numberscomefrom, if we permit continuousdegreesof grammaticality. The answerto wherethe numberscome from is parameterestimation. Parameterestimationis well-understoodfor a numberof modelsof interest, andcan be seenpsychologicallyaspart of what goeson during languageacquisition. Naturalness It is a bit difficult to say preciselywhat I meanby naturalness . A large componentis plausibility, but not plausibility in the senseof world knowledge, but ratherplausibility in the senseof selectionalpreferences , that is, semanticsortalpreferencesthat predicatesplaceon their arguments . Another important componentof naturalnessis not semantic, though, but " " simply how you sayit. This is whathasbeencalledcollocationalknowledge, like the fact that one saysstrong tea and poweiful car, but not vice versa [Smadja, 1991], or that you say thick accent in English, but starker Akzent " " ( strongaccent ) in German. Thoughit is difficult to definejust what naturalnessis, it is not difficult to recognizeit. If onegeneratestext at randomfrom anexplicit grammarplus lexicon , the shortcomingsof the grammarare immediatelyobviousin the unnatural - sentencesthat are - even if not ungrammatical produced. It is alsoclear that naturalnessis not at all the samething as meaningfulness . For example, I think it is clearthatdifferential structureis morenaturalthandifferential child,

Chapterl

eventhoughI could not saywhat a differential structuremight be. Or consider thefollowing examplesthat werein fact generatedat randomfrom a grammar: (5) a. matter-like , complete, allegedstrips a stratigraphic,dubiousscattering a far alternativeshallowmodel b. indirect photographic-drill sources earlier stratigraphicallypreciseminimums ' Europes cyclic existence , but I think All theseexamplesare abouton a par asconcernsmeaningfulness . a than the natural more the (b) examplesarerather ( ) examples Collocationsand selectionalrestrictionshave beentwo importantareasof applicationof statisticalme~ ods in computationallinguistics. Questionsof , interesthavebeenboth how to include themin a global measureof goodness for as a tool both Resnik 1993 , ], and how to induce them distributionally [ investigations,andasa modelof humanlearning. , have , or parsing strategies Structural Preferences Structuralpreferences " " is one match A . example. The preference longest alreadybeenmentioned example (6) The emergencycrewshatemostis domesticviolence is a garden-path becauseof a strong preferencefor the longest initial NP, . (The Theemergencycrews, ratherthanthe correctalternative, Theemergency correctinterpretationis: Theemergency[that crewshatemost] is domesticviolence .) The longest-matchpreferenceplays an importantrole in the dispreference for the structure(3) that we examinedearlier. As alreadymentioned, thesepreferencescan be seenas structuralpreferences . They interactwith the otherfactorswe , ratherthanparsingpreferences . For example, in (6), an of goodness measure in a havebeenexamining global is evenlongermatch, The emergencycrewshate, actuallypossible, but it violates the dispreferencefor havingplural nounsasnominalmodifiers. Error Tolerance A remarkablepropertyof humanlanguagecomprehension that an algebraicgrammarwould simply is its error tolerance.Many sentences classifyasungrammaticalareactuallyperceivedto havea particularstructure. A simpleexampleis wesleeps,a sentencewhoseintendedstructureis obvious, . In fact, an erroneousstructuremay actuallybe preferred albeit ungrammatical to a grammaticalanalysis; consider

StatisticalMethodsandLinguistics

(7) Thanksfor all you help. which I believeis preferentiallyinterpretedasan erroneousversionof Thanks for all your help. However, there is a perfectly grammaticalanalysis: Thanks for all thosewhoyou help. We canmakesenseof this phenomenonby supposingthat a rangeof errorcorrectionoperationsare available, thoughtheir applicatiol~imposesa certain cost. This cost is combinedwith the otherfactorswe havediscussed , to determine a global goodness , andthe bestanalysisis chosen.In (7), thecostof error or correctionis apparentlylessthanthe costof the alternativein unnaturalness structuraldispreference . Generally, error detectionand correctionare a major selling point for statisticalmethods. They wereprimary motivationsfor Shannon' s noisychannelmodel[Shannon,1948], which providesthe foundationfor . manycomputationallinguistic techniques Learning on the Fly Not only is the languagethat one is exposedto full of errors, it is producedby otherswhosegrammarsand lexica vary from one' s own. Frequently, sentences thatoneencounterscanonly be analyzedby adding new constructionsor lexical entries. For example, when the averageperson hearsa hectareis a hundredares, they deducethat are is a noun, and succeed in parsingthe sentence . But therearelimits to learningon the fly , just asthere arelimits to error correction. Learningon the fly doesnot help oneparsethe a are of I . Learningon the fly can be treatedmuch like error correction. The simplest - for example, assigninga approachis to admit a spaceof learningoperations frameto a verb, new part of speechto a word, addinga new subcategorization etc.- andassigna costto applicationsof the learningoperations.In this way it is conceptuallystraightforwardto include learningon the fly in a global optimization . Peopleare clearly capableof error correctionand learningon the fly ; they are highly desirableabilities given the noise and variancein the typical linguistic environment. They greatly exacerbatethe problem of picking out the intendedparsefor a sentence , becausethey explodethe candidatespaceeven of candidatesthat the grammarprovides. To the set beyond already large how it is nonetheless possibleto identify the intendedparse, thereis no explain seriousalternativeto the useof weightedgrammars. the problemof identifying Lexical Acquisition A final factor that exacerbates the correctparseis the sheerrichnessof natural languagegrammarsand

Chapter1

lexica. A goal of earlierlinguistic work, andonethat is still a centtalgoalof the linguistic work that goeson in computationallinguistics, is to developgrammars that assigna reasonablesyntacticstructureto every sentenceof English, as or nearlyeverysentenceaspossible. This is not a goal that is currentlymuch -Binding theory in fashionin theoreticallinguistics. Especiallyin Government (GB), the developmentof large fragmentshas long sincebeenabandonedin favor of the pursuitof deepprinciplesof grammar. The scopeof the problemof identifying the correctparsecannotbe appreciated by examining behavior on small fragments, however deeply analyzed. Large fragmentsare not just small fragmentsseveraltimes over- there is a qualitativechangewhenonebeginsstudyinglargefragments. As the rangeof increases constructionsthat the grammaraccommodates , the numberof undesired increasesdramatically. parsesfor sentences In-breadthstudiesalso give a different perspectiveon the problemof language acquisition. When one attemptsto give a systematicaccountof phrase structure,it becomesclearjust how manylittle factstherearethat do not fallout from grandprinciples, butjust haveto belearned.Thesimple, generalprinciples in thesecasesarenot principlesof syntax, but principlesof acquisition. Examples arethecomplexconstraintson sequencingof prenominalelementsin English , or the syntaxof dateexpressions(MondayJune the 4th, MondayJune4, * MondayJune the4, *June4 Monday) or the syntaxof propernames(Greene . ) , or the syntaxof numeralexpressions CountySheriff' s DeputyJim Thurmond -setting The largestpieceof whatmustbe learnedis the lexicon. If parameter views of syntaxacquisitionare correct, thenlearningthe syntax(which in this casedoesnot includethe low-level messybits discussedin the previousparagraph ) is actuallyalmosttrivial. The really hardjob is learningthe lexicon. Acquisition of the lexicon is a primary areaof applicationfor distributional esto acquisition. Methodshavebeendevelopedfor the andstatisticalapproach acquisitionof partsof speech[Brill , 1993; Schiitze, 1993], terminologicalnoun compounds[Bourlgault, 1992], collocations [Smadja, 1991], support verbs frames[Brent, 1991; Manning, 1993], , 1995], subcategorization [Grefenstette 1993 restrictions selectional ], and low-level phrasestructurerules [ Resnik, [Finch, 1993; Smith andWitten, 1993]. Thesedistributionaltechniquesdo not so muchcompetewith parametersettingasa modelof acquisition, asmuchas -settingaccountspassover complementit , by addressingissuesthat parameter also not are . Distributional in silence adequatealoneas modelsof techniques humanacquisition whateverthe outcomeof the syntacticvs. semanticbootstrappingdebate, children clearly do make use of situationsand meaningto learn language- but the effectivenessof distributionaltechniquesindicatesat leastthat they might accountfor a componentof humanlanguagelearning.

StatisticalMethodsandLinguj ~tic~ 4

Objections

There are a couple of generalobjectionsto statistical methodsthat may be ' lurking in the backsof readers minds that I would like to address.First is the sentimentthat, however relevant and effective statistical methods may be, ' they areno morethan an engineers approximation, not part of a properscientific theory. Secondis the nagging doubt: did not Chomskydebunk all this agesago? 4.1 Are StochasticModels Only for Engineers? Onemight admit that onecan accountfor parsingpreferencesby a probabilistic model, but insistthat a probabilisticmodelis at bestan approximation,suitable for engineeringbut not for science. On this view, we do not needto talk about degreesof grammaticality, or preferences , or degreesof plausibility. Granted, humansperceiveonly one of the many legal structuresfor a given sentence , but the perceptionis completelydeterministic. We needonly give a properaccountof all the factorsaffectingthejudgment. Considerthe example:

threeshotswerefiredat Humberto Yesterday Calvados assistant to the , personal famous tenorEnrique Felicidad , whowasin Parisattending to unspecified personal matters . ' Supposefor arguments sakethat 60% of readerstake the tenorto be in Paris, and40% take the assistantto be in Paris. Or more to the point, supposea particular infonnant, John Smith, choosesthe low attachment60% of the time whenencounteringsentences with preciselythis structure(in the absenceof an infonnativecontext), andlow attachment40% of thetime. Onecouldstill insist thatno probabilisticdecisionis beingmade, but ratherthat therearelexical and semanticdifferencesthat we have inappropriatelyconflatedacrosssentences with " preciselythis structure," andif we takeaccountof theseothereffects, we endup with a detenninisticmodelafterall. A probabilisticmodelis only a stopgap in absenceof an accountof the missing factors: semantics , pragmatics, what topics I have beentalking to other peopleaboutlately, how tired I am, whetherI atebreakfastthis morning. By this speciesof argument,stochasticmodelsarepracticallyalwaysa stopgap approximation. Take stochasticqueuetheory, for example, by which one can give a probabilistic model of how many trucks will be arriving at given depotsin a transportationsystem. Onecould arguethat if we couldjust model everythingaboutthestateof thetrucksandtheconditionsof theroads, the location of every nail that might causea flat , and every drunk driver that might

Chapter1 cause an accident, then we could in principle predict detenninistically how many trucks will be arriving at any depot at any time , and there is no need of stochastic queue theory . Stochastic queue theory is only an approximation in lieu of infonnation that it is impractical to collect . But this argument is flawed . If we have a complex detenninistic system, and if we have access to the initial conditions in complete detail , so that we can compute the state of the system unerringly at every point in time , a simpler stochastic description may still be more insightful . To use a dirty word , some properties of the system are genuinely emergent, and a stochastic account is not just an approximation , it provides more insight than identifying every deterministic factor . Or to use a different dirty word , it is a reductionist error to stochastic account and insist that only a more complex , a successful reject lower level , detenninistic model advances scientific understanding. 4.2 Chomsky v. Shannon In one' s inttoductory linguistics course, one learns that Chomsky disabused the field once and for all of the notion that there was anything of interest to statistical models of language. But one usually comes away a little fuzzy on the question of what , precisely , he proved . " ' The arguments of Chomsky s that I know are from Three Models for the " Description of Language [Chomsky , 1956] and Syntactic Structures [Chomsky , 1957] (essentially the same argument repeated in both places), and from the Handbook of Mathematical Psychology , chapter 13 [Miller and Chomsky , 1963] . I think the fIrSt argument in Syntactic Structures is the best known . It goes like this. It is fair to assumethat neithersentence( 1) [colorlessgreenideassleepfuriously] nor ) has (2) [furiously sleepideasgreencolorless], (nor indeedany part of thesesentences ever occurredin an English discourse. . . Yet ( 1), thoughnonsensical , is grammatical, while (2) is not. [Chomsky, 1957, p. 16] This argument only goes through if we assumethat if the frequency of a sentence " or " part is zero in attaining sample, its probability is zero. But in fact , there is quite a literature on how to estimate the probabilities of events that do not occur in the sample, and in particular how to distinguish real zeros from zeros that just reflect something that is missing by chance. Chomsky also gives a more general argument: of a given lengthin orderof statisticalapproximationto English If we rank the sequences scatteredthroughout , we will fmd both grammaticalandungrammaticalsequences the list; thereappearsto be no particularrelation betweenorder of approximationand . [Chomsky, 1957, p. 17] grammaticalness

StatisticalMethodsandLinguistics Because for any n , there are sentences with grammatical dependencies spanning more than n words , so that no nth order statistical approximation can sort out the grammatical from the ungrammatical examples. In a word , you cannot define grammaticality in terms of probability . " " It is clear from context that statistical approximation to English is a reference to nth - order Markov models, as discussed by Shannon. Chomsky is saying that there is no way to choose n and E such that for all sentencess, grammatical (s) +-+Pn(s) > E " " where Pn(s) is the probability of s according to the best nth- order approximation to English . But Shannon himself was careful to call attention to precisely this point : that for any n , there will be some depende;ncies affecting the well -formedness of a ' sentence that an nth - order model does not capture. The point of Shannon s approximations is that , as n increases, the total mass of ungrammatical sentences that are erroneously assignednon-zero probability decreases. That is , we in can fact defme grammaticality in terms of probability , as follows : Jim P n(s) > 0 grammatical (s) +-+ n~ A third variant of the argument appears in the Handbook . There Chomsky states that parameter estimation is impractical for an nth -order Markov model " " where n is large enough to give a reasonablefit to ordinary usage. He emphasizes that the problem is not just an inconvenience for statisticians , but renders " the model untenable as a model of human language acquisition : we cannot parameters in a childhood seriously propose that a child learns the values of " lasting only 108 seconds. This argument is also only partially valid . If it takes at least a second to estimate each parameter, and parameters are estimated sequentially , the argument is correct. But if parameters are estimated in parallel , say, by a high -dimensional iterative or gradient -pursuit method , all bets are off . Nonetheless, I think even the most hardcore statistical types are willing to admit that Markov models represent a brut~ force approach, and are not an adequatebasis forpsycho logical models of language processing. However , the inadequacy of Markov models is not that they are statistical , but ' that they are statistical versions of fmite -state automata. Each of Chomsky s arguments turns on the fact that Markov models are fmite state, not on the fact that they are stochastic. None of his criticisms are applicable to stochastic models generally. More sophisticated stochastic models do exist: stochastic context free grammars are well understood, and stochastic versions of Tree Adjoining

Chapter1

Grammar[Resnik, 1992], GB [ FordhamandCrocker, 1994], andHPSG[Brew, 1995] havebeenproposed. m fact, probabilitiesmakeMarkov modelsmoreadequatethantheir nonprobabilistic . Markov modelsare surprisinglyeffective , not lessadequate counterparts . For example, they are the workhorseof , given their finite statesubstrate . Stochastic grammarscan alsobe easierto learn speechrecognitiontechnology . For than their nonstochastic counterparts example, thoughGold [Gold, 1967] showedthattheclassof context-freegrammarsis not learnable , Horning [ Horning . , 1969] showedthattheclassof stochasticcontext-freegrammarsis learnable m short, Chomsky's argumentsdo not bearat all on the probabilisticnature of Markov models, only on thefact that they arefinite-state. His argumentsare not by any stretchof the imaginationa sweepingcondemnationof statistical methods. 5

Conclusion

In closing, let me repeatthe main line of argumentas conciselyas I can. Statistical methods- by which I meanprimarily weightedgrammarsand distributional induction methods- are clearly relevant to languageacquisition, languagechange, languagevariation, languagegeneration,andlanguagecomprehens . Understandinglanguagein this broadsenseis the ultimategoal of linguistics. The issuesto which weightedgrammarsapply, particularlyasconcernsperception of grammaticalityand ambiguity, one may be temptedto dismissas " " performanceissues. However, the set of issueslabeled performance are not " " essentiallycomputational,asoneis often led to believe. Rather, competence representsa provisionalnarrowingandsimplificationof datain orderto understand " is a the algebraicpropertiesof language." Performance misleadingterm " " for everything else. Algebraic methodsare inadequatefor understanding many importantpropertiesof humanlanguage,suchas the measureof goodness that permitsoneto identify the correctparseout of a largecandidatesetin the faceof considerablenoise. Many other propertiesof language, as well, that are mysteriousgiven unweighte grammars, propertiessuch as the gradualnessof rule learning, the gradualnessof languagechange, dialect continua, and statisticaluniversals, makea greatdeal more senseif we assumeweightedor stochasticgrammars. ? tec?mlquesmat computatIolla?1mguists Thereis a hugebody of mamemadca have begunto tap, yielding tremendousprogresson previously intransigent problems. The focusin computationallinguisticshasadmittedlybeenon tech-

Statistical MethodsandLinguistics

25

nology. But the sametechniquespromiseprogresson issuesconcerningthe natureof languagethat haveremainedmysteriousfor so long. The time is ripe to apply them. Acknowledgments

I thankTilmanHoehle , GrahamKatz, MarcLight, andWolfgangStemefeld for theircomment ~onanearlierdraftof thischapter . All errorsandoutrageous

opinions are, of course, my own . References

DidierBourigault . Surfacegrammatical analysisfor theextractionof tenninoiogical -92, Vol. 3, pp. 977- 981, 1992 nounphrases . In COLING . MichaelR. Brent. Automaticacquisitionof subcategorization framesfrom untagged , free-text corpora . In Proceedings of the29thAnnualMeetingof theAssociation for Computational , pp. 209-214, 1991. Linguistics ChrisBrew. Stochastic HPSG . In Proceedings of EACL-95, 1995. -BasedLearning Eric Brill. Transformation . PhiD. thesis , Universityof Pennsylvania , , 1993. Philadelphia NoamChomsky . Threemodelsfor thedescription of language . IRE Transactions on InformationTheory , IT-2(3): 113- 124, 1956.NewYork, Instituteof RadioEngineers . NoamChomsky . Syntactic Structures . TheHague , Mouton,1957.

NoamChomsky . Thelogicalbasisof linguistic . In Horace Lunt, editor theory , Proceedings of theNinthInternational Congress , pp. 914-978,TheHague of Linguists , Mouton . 1964 . Steven PaulFinch . FindingStructure in Language . PhDthesis of Edinburgh , University . , 1993 Andrew Fordham andMatthew Crocker . Parsing withprinciples andprobabilities . In TheBalancing Act: Combining andStatistical Symbolic estoLanguage . Approach , 1994 E. MarkGold.Language identification in thelimit. Information andControl , 10(5): 447-474, 1967 . -based Grefenstette . Corpus Gregory method for automatic identification of support -95, 1995 verbsfornominalizations . InEACL . JohnA. Hawkins . WordOrderUniversals . NewYork,Academic Press . , 1983 JohnA. Hawkins . A parsing of wordorderuniversals . Linguistic theory , 21(2): Inquiry 223-262, 1990 . James . A Studyof Grammatical JayHoming . PhiD . thesis Inference , Stanford (Computer Science . ), 1969 Terrence Kaufman . Thenative ofLatinAmerica : languages remarks . In 's general . 31- Christopher andRE. Asher Moseley , editors ,AtlasoftheWorld , Languages pp 33, London . , Routledge , 1994

Chapter1

in IrishGaelic.In EACL-95, 1995. . Computational BrettKessier dialectology of a largesubcategorization . Automatic . Manning dictionary acquisition ChristopherD , . In 31stAnnualMeetingof theAssociation fromcorpora Linguistics for Computational . 242 1993 . 235 , pp users . In R. D. . Finitarymodelsof language GeorgeA. Miller andNoamChomsky , chapter Luce, R. Bush,andE. Galanter , Handbook Psychology , editors of Mathematical 13. NewYork, Wiley, 1963. natural for statistical asaframework Tree-AdjoiningGrammar . Probabilistic PhilipResnik . In COUNG-92, pp. 418- 424, 1992. language processing . PhiD. thesis , . SelectionandInformation , Universityof Pennsylvania Philip Resnik . 1993 , Philadelphia . In Proceedings HinrichSchUtte. Part-of-speechinductionfrom scratch of the 31st . 251 258 the Association , 1993. , AnnualMeetingof Linguisticspp for Computational Technical . TheBellSystem . A mathematical ClaudeE. Shannon theoryof communication Journal,27(3- 4): 379- 423, 623- 656, 1948. . In Uri Zemik, editor, thelexiconfor language . Microcoding FrankSmadja generation . Cambridge to Builda Lexicon : UsingOn-LineResources , Mass.: LexicalAcquisition TheMIT Press , 1989. : Language Generation . ExtractingCollocations FrankSmadja from Text.AnApplication . PhiD. thesis , NewYork, 1991. , ColumbiaUniversity inferencefrom functionwords. Manuscript TonyC. SmithandIan H. Witten. Language , January1993. , Universityof CalgaryandUniversityof Waikato Model. PhDthesis : A Connectionist , Stanford WhitneyTabor. SyntacticInnovation . 1994 , University . In Christopher NorthAmerica ,Atlasof the MoseleyandRE . Asher,editors MaryTait. . World's Languages , 1994 , Routledge , pp. 3- 30, London . 2ndedition. Paris: Klincksieck , . Elementsde SyntaxeStructurale LucieneTesniere 1959. Mifflin, 1966. J. R. R. Tolkien.TheHobbit. Boston , Houghton , 1960. WillardvanOrmanQuine.WordandObject.Cambridge , Mass., TheMIT Press asan.errorcorrectingcode.TechnicalReport33:XV, Quarterly VictorYngve. Language Instituteof of Electronics , TheMassachusetts Laboratory Reportof theResearch , April 15, 1954,pp. 73- 74. Technology

Chapter 2 Qualitative and Quantitative Models of SpeechTranslation

Hiyan Alshawi

Alshawi achieves two goals in this chapter . First , he challenges the notion that the identification of a statistical -symbolic distinction in language processing is an instance of the empirical vs. rational debate. Second, Alshawi proposes models for speech translation that retain aspects of qualitative design while moving toward incorporating quantitative aspectsfor structural dependency, lexical transfer , and linear order . On the topic of the place of the statistical -symbolic distinction in natural lan guage processing , Alshawi points to the fact that rule -based approach es are becoming increasingly probabilistic . However , at the same time , since language is symbolic by nature , the notion of building a "purely " statistical model may not be meaningful . Alshawi suggests that the basis for the contrast is in fact a distinction between qualitative systemsdealing exclusively with combinatoric constraints , and quantitative systems dealing with the computation of numerical functions . Of course, the problem still remains of how and where to introduce quantitative modeling into language processing . Alshawi proposes a model to do just this , specifically for the language translation task. The design reflects the conventional qualitative transfer ' approach , that is , starting with a logic -based grammar and lexicon to produce a set of logical forms that are then filtered , passed to a translation component , and then given to a generation component mappinglogicalforms to surface syntax , which is then fed to the speech synthesizer. Alshawi then methodically analyzes which of these steps would be improved by the introduction of quantitative modeling . His step-by-step analysis , considering specific ways to improve the basic qualitative model , illustrates the variety of possibilities still to be explored in achieving the optimal balance among types ofmodels .- Eds .

Chapter2 1

Introduction

In recent years there has been a resurgence of interest in statistical approaches to natural language processing . Such approaches are not new , witness the statistical approach to machine translation suggested by Weaver [ 1955] , but the current level of interest is largely due to the success of applying hidden Markov models and N - gram language models in speech recognition . This success was directly measurable in terms of word recognition error rates, prompting language processing researchers to seek corresponding improvements in performance and robustness. A speech translation system, which by necessity combines speech and language technology , is a natural place to consider combining the statistical and conventional approaches, and much of this chapter describes probabilistic models of structural language analysis and translation . My aim is to provide an overall model for translation with the best of both worlds . Various factors lead us to conclude that a lexicalist statistical model with dependency relations is well suited to this goal . As well as this quantitative approach, we consider a constraint , logic -based approach and try to distinguish characteristics that we wish to preserve from those that are best replaced by statistical models. Although perhaps implicit in many conventional approaches to translation , a characterization in logical terms of what is being done is rarely given , so we attempt to make that explicit here, more or less from fIrst principles . Before proceeding, I first examine some fashionable distinctions in section 2 in order to clarify the issues involved in comparing these approaches. I argue that the important distinction is not so much a rational - empirical or symbolic statistical distinction but rather a qualitative - quantitative one. This is followed in section 3 by discussion of the logic -based model , in section 4 by the overall quantitative model , in section 5 by monolingual models, in section 6 by translation models, and, in section 7 , some conclusions. I concentrate throughout on what information about language and translation is coded and how it is expressed as logical constraints in one model or statistical parameters in the other. At Bell Laboratories , we have built a speechtranslation system with the same underlying motivation as the quantitative model presentedhere. Although the quantitative model used in that system is different from the one presented here, they can both be viewed as statistical models of dependency grammar . In building the system, we had to address a number of issuesthat are beyond the scope of this chapter, including parameter estimation and the development of efficient search algorithms .

QualitativeandQuantitativeModelsof SpeechTranslation 2

Qualitative and Quantitative Models

One conttastoften takenfor grantedis the identification of a statistical-symbolic distinction in languageprocessingas an instanceof the empirical vs. rationaldebate.I believethis contrasthasbeenexaggerated , thoughhistorically it hashad somevalidity in termsof acceptedpractice. Rule-basedapproach es have becomemore empirical in a number of ways: First, a more empirical approachis being adoptedto grammardevelopmentwherebythe rule set is modified accordingto its performanceagainstcorpora of natural text (e.g. [ Tayloret al., 1989]). Second, there is a classof techniquesfor learningrules from text, a recentexamplebeing [Brill , 1993]. Conversely, it is possibleto imagine building a languagemodel in which all probabilities are estimated accordingto intuition without referenceto any real data, giving a probabilistic modelthat is not empirical. Most languageprocessinglabeled as statisticalinvolves associatingrealnumber- valuedparametersto configurationsof symbols. This is not surprising giventhatnaturallanguage,at leastin written form, is explicitly symbolic. Presumably, classifyinga systemassymbolicmustrefer to a different setof (internal ) symbols, but eventhis doesnot rule out manystatisticalsystemsmodeling eventsinvolving nonterminalcategoriesandword senses . Giventhatthenotion of a symbol, let alonean " internal symbol," is itself a slipperyone, it may be unwiseto build our theoriesof language,or eventhe way we classifydifferent theories, on this notion. Instead, it would seemthatthe real conttastdriving the shift towardstatistics in languageprocessingis a conttastbetweenqualitativesystemsdealingexclusively with combinatoricconstraints, and quantitative systemsthat involve computingnumericalfunctions. This bearsdirectly on the problemsof brittleness and complexity that discreteapproach es to languageprocessingshare with, for example, reasoningsystemsbasedon traditional logical inference. It relatesto the inadequacyof the dominant theoriesin linguistics to capture " shades " of meaningor degreesof acceptabilitywhich areoften recognizedby outside the field as importantinherentpropertiesof natural language . people The qualitative-quantitativedistinctioncan also be seenasunderlyingthe difference betweenclassificationsystemsbasedon featurespecifications , asused in unification formalisms[Shieber, 1986], and clusteringbasedon a variable degreeof granularity(e.g. [Pereiraet al., 1993]). It seemsunlikely that thesecontinuouslyvariableaspectsof fluent natural languagecanbe capturedby a purely combinatoricmodel. This naturallyleads

2 Chapter to the questionof how bestto introducequantitativemodelinginto language . It is not, of course, necessaryfor the quantitiesof a quantitative processing modelto beprobabilities. For example,we may wish to definereal-valuedfunctions on parsetreesthat reflect the extentto which the treesconform to, say, minimal attachmentand parallelismbetweenconjuncts. Such functionshave beenusedin tandemwith statisticalfunctionsin experimentson disambiguation (e.g. [Alshawi andCarter, 1994]). Anotherexampleis connectionstrengthsin neuralnetwork approach es to languageprocessing , thoughit hasbeenshown thatcertainnetworksareeffectivelycomputingprobabilities[RichardandLippmann, 1991]. Nevertheless , probability theory doesoffer a coherentand relatively wellunderstoodframeworkfor selectingbetweenuncertainalternatives,making it a naturalchoicefor quantitativelanguageprocessing . The casefor probability is a well theory strengthened by developedempiricalmethodologyin the form of statisticalparameterestimation. Thereis alsothe strongconnectionbetween probability theoryandthe formal theoryof informationandcommunication,a connectionthat hasbeenexploited in speechrecognition, for example, using the conceptof entropyto provide a motivatedway of measuringthe complexity of a recognitionproblem[Jelineket al., 1992] . Evenif probability theoryremains, asit currentlyis, themethodof choicein makinglanguageprocessingquantitative, this still leavesthefield wide openin termsof carving up languageprocessinginto an appropriateset of eventsfor probability theory to work with. For translation, a very direct approachusing parametersbasedon surfacepositionsof words in sourceandtargetsentences was adoptedin the Candidesystem[Brown et al., 1990]. However, this does not captureimportantstructuralpropertiesof naturallanguage.Nor doesit take into accountgeneralizationsabouttranslationthat areindependentof the exact word orderin sourceandtargetsentences . Suchgeneralizationsare, of course, central to qualitative structural approach es to translation(e.g. [Isabelle and Macklovitch, 1986; Alshawi et al., 1992]) . The aim of thequantitativelanguageandtranslationmodelspresentedin sections 5 and6 is to employprobabilisticparameters thatreflectlinguisticstructure withoutdiscardingrich lexical informationor makingthemodelstoo complexto train automatically.In termsof a traditionalclassification,this would be seenas a " hybrid symbolic-statistical" systembecauseit dealswith linguistic structure. From our perspective , it canbe seenasa quantitativeversionof the logic-based model becauseboth modelsattemptto capturesimilar information(aboutthe organizationof wordsinto phrasesandrelationsholdingbetweenthesephrases or their referents ), thoughthetoolsof modelingaresubstantiallydifferent.

andQuantitative Modelsof Speech Translation Qualitative 3 Dissectinga Logic-BasedSystem We now consider a hypothetical speech ttanslation system in which the language processing components follow a conventional qualitative ttansfer design . Although hypothetical , this design and its components are similar to those used in existing database query [Rayner and Alshawi , 1992] and ttanslation systems [ Alshawi et al., 1992] . More recent versions of these systems have been gradually taking on a more quantitative flavor , particularly with respect to choosing between alternative analyses, but our hypothetical system will be more purist in its qualitative approach. The overall design is as follows . We assume that a speech recognition subsystem delivers a list of text sttings corresponding to ttanscriptions of an input utterance. These recognition hypoth ~ses are passedto a parser which applies a logic - basedgrammar and lexicon to produce a set of logical forms , specifically formulas in first order logic corresponding to possible interpretations of the utterance. The logical forms are filtered by contextual and word - sense constraints , and one of them is passedto the ttanslation component . The ttanslation relation is expressedby a set of first order axioms which are used by a theorem prover to derive a target language logical form that is equivalent ( in some context ) to the source logical form . A grammar for the target language is then applied to the target form , generating a syntax ttee whose fringe is passed to a speech synthesizer. Taking the various components in turn , we make a note of undesirable properties that might be improved by quantitative modeling . 3.1 Analysis and Generation A grammar , expressed as a set of syntactic rules ( axioms ) Gsynand a set of semantic rules (axioms ) Gsemis used to support a relation form holding between sbings s and logical fonD S cp expressed in fIrSt order logic : GsynU GsemFform (s, cp) The relation form is many -to -many , associating a sbing with linguistically possible logical fonD interpretations . In the analysis direction , we are given s and search for logical fonD Scp, while in generation we search for sbings s given cp. For analysis and generation, we are treating sbings s and logical fonD S cp as object level entities. In interpretation and translation , we will move down from this meta- level reasoning to reasoning with the logical fonD S as propositions . The list of text strings handed by the recognizer to the parser can be assumed to be ordered in accordance with some acoustic scoring scheme internal to the

Chapter2

recognizer.The magnitudeof the scoresis ignoredby our qualitativelanguage esthehypothesesoneat a time until it fmds onefor ; it simply process processor which it canproducea completelogical form interpretationthat passesgrammatical andinterpretationconstraints,at which point it discardsthe remaining . Clearly, discardingthe acousticscoreandtaking the fIrSthypothesis hypotheses that satisfiesthe constraintsmay leadto an interpretationthat is lessplausible than one derivablefrom a hypothesisfurther down in the recognitionlist. But there is no point in processingtheselater hypothesessince we will be forcedto selectoneinterpretationessentiallyat random. " " Syntax The syntacticrulesin Gsynrelate category predicatesco' CI, C2holding of a string and two spanningsubstrings(we limit the rules here to two daughtersfor simplicity) : Co(So) A daughters(so, sl ' S2) CI(SI) AC2(S2) A (So= concat(SI ' S2 , variableslike Soand SI are implicitly universally (Here, and subsequently quantified.) Gsynalsoincludeslexical axiomsfor particularstringsw consisting of singlewords: CI(W), ... cm(w) For a feature-basedgrammar, theserules can include conjunctsconstraining the values, aI , a2," ' , of discrete-valuedfunctionsfon the strings: f (w) = aI , f (so) = f (sl) The main problemhereis that suchgrammarshaveno notion of a degreeof grammaticalacceptability- a sentenceis either grammaticalor ungrammatical . For small grammarsthis meansthat perfectly acceptablestringsare often rejected; for large grammarswe get a vast numberof alternativetreesso the chanceof selectingthe correcttree for simple sentencescan get worseas the . There is also the problem of requiring increasgrammarcoverageincreases ingly complexfeaturesetsto describeidiosyncrasiesin the lexicon.

Semantics Semanticgrammaraxiomsbelongingto Gsemspecify a " composition " function for g deriving a logical form for a phrasefrom thosefor its subphrases :

form(so, g(cf>l ' cf>2 ) daughters(so, Sl, SVACI(SI) AC2(SV A Co(SO Aform (sl' <1>1) Aform (S2' v

QualitativeandQuantitativeMntip;1~ of SpeechTranslation

The interpretationrulesfor stringsbottomout in a setof lexical semanticrules " ." associatingwords with predicates(PI,p2,...) correspondingto word senses For a particularword and syntacticcategory, there will be a (small, possibly : empty) fmite setof suchword-sensepredicates c;(w) - form ( w, p; ) .. .

c;(w) - +form(w, pin) First order logic was assumedas the semanticrepresentationlanguage becauseit comes with well-understood , if not very practical, inferential for constraint . However , applying this machineryrequires machinery solving makinglogical forms fme-grainedto a degreeoften not warrantedby the information the speakerof an utterance.intendedto convey. An exampleof this is explicit scopingwhich leads(again) to largenumbersof alternativeswhich the qualitative model has difficulty choosingbetween. Also, many natural language cannotbe expressedin first orderlogic without resortto elaborate sentences formulasrequiringcomplexsemanticcompositionrules. Theserulescan be simplified by usinga higherorderlogic but at theexpenseof evenlesspractical inferentialmachinery. In applyingthe grammarin generationwe arefacedwith the problemof balancing over- and undergeneration by tweakinggrammaticalconstraints,there no to being way prefer fully grammaticaltargetsentencesover more marginal ones. Qualitativeapproach es to grammartendto emphasizethe ability to capture generalizationsasthemainmeasureof successin linguistic modeling. This might explain why producing appropriatelexical collocations is rarely addressed seriouslyin thesemodels, eventhoughlexical collocationsareimportant for fluent generation.The studyof collocationsfor generationfits in more , as illustratedby Smajdaand McKeown naturally with statisticaltechniques [ 1990] . 3.2 Interpretation In the logic-basedmodel, interpretationis the processof identifying from the possibleinterpretationsof s for which! orm(s, Here, we haveseparatedthe contextinto a contingentsetof contextualpropositionsS " and a set R of (monolingual) " meaningpostulates , or selectional restrictions, thatconstrainthe word sensepredicatesin all contexts.A is a setof

Chapter2 assumptions sufficient to support the interpretation given Sand R . In other " " words , this is interpretation as abduction [ Hobbs et al . , 1988 ] , since abduction , not deduction , is needed to arrive at the assumptions A . The most common types of meaning postulates in R are those for restriction , hyponymy , and disjointness , expressed as follows : restriction Pl (Xl , X2) - P2 (Xl ) P2(X) - P3 (X ) hyponymy -' ( P3(X) Ap4 (X disjointness Although there are compilation techniques ( e.g . [ Mellish , 1988 ] ) which allow selectional constraints stated in this fashion to be implemented efficiently , the scheme is problematic in other respects . To start with , the assumption of a small set of senses for a word is at best awkward because it is difficult

to arrive

at an optimal granularity for sense distinctions . Disambiguation with selectional restrictions expressed as meaning postulates is also problematic because it is virtually impossible to devise a set of postulates that will always filter all but one alternative . Weare

thus forced to underfilter

and make an arbitrary

choice between remaining alternatives .

3.3 Logic-BasedTranslation In both the quantitativeand qualitative models we take a transfer approach to translation. We do not dependon interlingual symbols, but insteadmap a representationwith constantsassociatedwith the source languageinto a correspondingexpressionwith constantsfrom the target language. For the is basedon logical qualitative model, the operablenotion of correspondence and the constants are source word sense equivalence predicatesPI , P2,' " and targetsensepredicatesql , q2," " More specifically, we will saythe translationrelationbetweena sourcelogical form cJ>s anda targetlogical form cJ>, holds if we have BUS U A ' F (cJ>s" " cJ>,) whereB is a setof monolingualandbilingual meaningpostulates , andS is a set of formulascharacterizingthe currentcontext. A ' is a set of assumptionsthat includesthe assumptionsA which supportedcJ>s' Herebilingual meaningpostulates arefirst orderaxiomsrelatingsourceandtarget-sensepredicates . Atypical for between and be of the form: bilingual postulate translating PI ql might PS(XI) - + (PI(Xl, X2) .... ql (Xl , X2 The need for the assumptionsA ' ariseswhen a sourcelanguageword is vaguerthanits possibletranslationsin the targetlanguage,so different choices

Translation Modelsof Speech andQuantitative Qualitative

35

. For of targetwordswill correspondto translationsunderdifferentassumptions example, the conditionPS(Xl ) abovemight be proved from the input logical . form, or it might needto be assumed ' solutions case In the general , fmding (i.e. A , <1>, pairs) for the abductive schemais an undecidabletheorem-proving problem. This canbe alleviatedby placingrestrictionson the form of meaningpostulatesandinput formulasand using heuristicsearchmethods. Although suchan approachwas appliedwith somesuccessin a limited-domain systemtranslatinglogical forms into database queries[RaynerandAlshawi, 1992], it is likely to be impracticalfor language translation with tens of thousandsof sensepredicatesand related axioms. Settingasidetheintractabilityissue, this approachdoesnot offer a principled way of choosingbetweenalternativesolutionsproposedby the prover. One " " , but it is difficult would like to prefersolutionswith minimal setsof assumptions to fmd motivateddefinitionsfor this minimizationin a purely qualitative framework. 4

Quantitative Model Components

4.1 Moving to a Quantitative Model In movingto a quantitativearchitecture,we proposeto retainmanyof thebasic characteristicsof the qualitativemodel: . A transferorganizationwith analysis, transfer, andgenerationcomponents . Monolingualmodelsthat canbe usedfor both analysisandgeneration . Translation models that exclusively code contrastive (cross-linguistic) information . Hierarchicalphrasescapturingrecursivelinguistic structure Insteadof feature-basedsyntaxtreesand first order logical forms we will that is morecloselyrelatedto those adopta simpler, monostratalrepresentation . Hudson e. found in dependencygrammars( g [ , 1984]). Dependencyrepresentations havebeenusedin large scalequalitativemachinetranslationsystems, " " notablyby McCord [ 1988] . The notionof a lexical head of a phraseis central becausethey concentrateon relationsbetweensuch to theserepresentations case lexical heads.In our , the dependencyrepresentationis monostratalin that the relations may include ones normally classified as belonging to syntax, semantics , or pragmatics. One salientpropertyof our languagemodel is that it is strongly lexical: it consistsof statistical parametersassociatedwith relations betweenlexical

Chapter2

itemsandthe numberandorderingof dependents of lexical heads.This lexical facilitates statistical and anchoring ttaining sensitivityto lexical variation and collocations. In orderto gainthe benefitsof probabilisticmodeling, we replace the taskof developinglargerule setswith the taskof estimatinglargenumbers of statisticalparametersfor the monolingualandtranslationmodels. This gives riseto a newcosttradeoffin humanannotationandjudgmentvs. barelytractable further researchon lexical similarity fully automaticttaining. It alsonecessitates and clustering(e.g. [ pereiraet al., 1993; Daganet al., 1993]) to improve parameterestimationfrom sparsedata. We should emphasizeat the outset that the quantitativemodel presented below is not a way of augmentinga logic-basedsystemby associatingprobabilities or costswith the axiomsor rulesof that model. Instead, the parameters of the quantitativemodelencodeall the structuraland preferenceinformation necessaryto apply the model. 4.2 Translation via Lexical Relation Graphs The model associatesphraseswith relation graphs. A relation graph is a directedlabeledgraphconsistingof a setof relation edges. Eachedgehasthe form of an atomicproposition r (Wi' wfl

wherer is a relationsymbol, Wiis the lexical headof a phrase,andWjis the lexical headof anotherphrase(typically a subphraseof the phraseheadedby Wi). The nodesWi and Wj are word occurrencesrepresentableby a word and an index, the indicesuniquelyidentifying particularoccurrencesof the wordsin a discourseor corpus. The set of relation symbolsis open-ended, but the fIrSt argumentof the relationis alwaysinterpretedasthe headandthe secondasthe dependentwith respectto this relation. The relations in the models for the sourceandtargetlanguagesneednot be the same, or evenoverlap. To keepthe languagemodelssimple, we will mainly restrictourselveshereto dependency graphsthat aretreeswith unorderedsiblings. In particular, phraseswill always be contiguousstringsof words and dependentswill always be headsof subphrases . Ignoring algorithmic issuesrelating to compactly representingand efficiently , the overall designof the searchingthe spaceof alternativehypotheses is as follows. The quantitativesystem speechrecognizerproducesa set of word-positionhypotheses(perhapsin theform of a word lattice) corresponding to a setof stringhypothesesfor the input. The sourcelanguagemodelis usedto computea set of possiblerelation graphs, with associatedprobabilities, for

QualitativeandQuantitativeModelsof SpeechTranslation

eachstring hypothesis.A probabilisticgraphtranslationmodel thenprovides, for each sourcerelation graph, the probabilities of deriving corresponding graphswith word occurrencesfrom the target language. Thesetarget graphs includeall the wordsof possibletranslationsof the utterancehypothesesbut do not specifythe surfaceorderof thesewords. Probabilitiesfor differentpossible word orderingsare computedaccordingto ordering parameterswhich fonn part of the targetlanguagemodel. In the following subsectionwe explain how the probabilitiesfor thesevarious processingstagesare combined to select the most likely target word . . This word sequencecan then be handedto the speechsynthesizer sequence the about For tighter integrationbetweengenerationandsynthesis,infonnation . derivationof the targetutterancecanalsobe passedto the synthesizer 4.3 Integrated Statistical Model The probabilities associatedwith phrasesin the abovedescriptionare computed accordingto the statisticalmodelsfor analysis, translation, and generation . In this subsectionwe showtherelationshipbetweenthesemodelsto arrive at an overall statisticalmodel of speechtranslation. We are not considering training issuesin this paper, thougha numberof now familiar techniquesranging from methodsfor unsupervisedmaximumlikelihood estimationto direct estimationusingfully annotateddataareapplicable. The objectsinvolved in the overall model are as follows (we omit target speechsynthesisunderthe assumptionthat it proceedsdeterministicallyfrom a targetlanguageword string) : . . . . .

As: (acousticevidencefor) sourcelanguagespeech Ws: sourcelanguageword string Wt: targetlanguageword string Cs: sourcelanguagerelationgraph Ct: targetlanguagerelationgraph

Given a spokeninput in the sourcelanguage, we wish to fmd a targetlanguage string that is the most likely translationof the input. We are thus interested in theconditionalprobability of Wt givenAs. This conditionalprobability canbe expressedasfollows (cf. [ChangandSu, 1993]) : P{WtIAs) =

) )P(CsIWs'As ,Cs ,C,P(WsIAs LWs P(CtI Cs'Ws' As) P(Wt I Ct, Cs'Ws' As)

Chapter2

We now apply somesimplifying independence assumptionsconcerningrelation : that their derivation from word stringsis independent , graphs specifically of acousticinformation; that their translationis independentof theoriginal wordsandacousticsinvolved; andthat targetword string generationfrom target relation edgesis independentof the sourcelanguagerepresentations . The extentto which these(Markovian) assumptionshold dependson the extentto which relation edgesrepresentall the relevantinformation for translation. In particularit meansthey shouldexpressaspectsof surfacerelevantto meaning, suchastopicalization, aswell aspredicateargumentstructure. In any case, the simplifying assumptionsgive the following : P(W, I As) = ( W s I As) P ( Cs I.w s) P (Ct I Cs) P ( W tiC ,) LWs ,Cs,CtP This can be rewritten with two applications of Bayes' s rule :

) .Cs .C,P(AsIWs) (l /P(As P(WsiCs LWs P (Cs) P (C, I Cs) P (W, I C,) SinceAs is given, liP (As) is a constantwhich can be ignoredin fmding the maximumof P(W, I As) . DetenniningW, that maximizesP (W, I As) therefore involvesthe following factors: . . . . .

P (As I Ws) : sourcelanguageacoustics P (Wsi Cs) : sourcelanguagegeneration P(Cs) : sourcecontentrelations P (C, I Cs) : source-to-targettransfer P (W, I C,) : targetlanguagegeneration

We assumethat the speechrecognizerprovidesacousticscoresproportional to P(As I Ws) (or logs thereof) . Suchscoresare nonnally computedby speech recognitionsystems,althoughthey are usually also multiplied by word-based languagemodelprobabilitiesP(Ws) which we do not requirein this application context. Our approachto languagemodeling, which coversthe contentanalysis and languagegenerationfactors, is presentedin section5 and the transfer probabilitiesfall underthe translationmodelof section6. ' Finally note that by anotherapplicationof Bayess rule we can replacethe two factorsP(Cs)P (C, I Cs) by P (C,)P (CsiC ,) without changingotherpartsof the model. This latter fonnulation allows us to apply constraintsimposedby the target language model to filter inappropriate possibilities suggested ' by analysisand transfer. In somerespectsthis is similar to Daganand Itai s

QualitativeandQuantitativeModelsof SpeechTranslation

39

approach [ 1994] to word sensedisambiguation using statistical associations in a second language.

5 LanguageModels 5.1 LanguageProduction Model Our languagemodel can be viewed in terms of a probabilistic generative " " processbasedon thechoiceof lexical heads of phrasesandtherecursivegeneration of subphrasesand their ordering. For this purpose, we can define the headwordof a phraseto be the word that most stronglyinfluencesthe way the . This notion hasbeencentralto a phrasemay be combinedwith other phrases es to grammar for some time, including theories like number of approach dependencygrammar [Hudson, 19.84] and HPSG [Pollard and Sag, 1987] . More recently, the statisticalpropertiesof associationsbetweenwords, and moreparticularlyheadsof phrases , hasbecomean activeareaof research(e.g. [Changet al., 1992; Hindle andRooth, 1993]). The languagemodelfactorsthe statisticalderivationof a sentencewith word string W asfollows: P(W) =

PC PW C Lc ( ) ( I ) whereC rangesover relationgraphs. The contentmodel, P (C), andgeneration model, P(W I C), are componentsof the overall statisticalmodel for spoken languagetranslationgiven earlier. This decompositionof P(W) canbe viewed as first decidingon the contentof a sentence , formulatedas a set of relation edgesaccordingto a statisticalmodel for P(C), and then deciding on word orderaccordingto P(W I C) . Of course, this decompositionsimplifiestherealitiesof languageproduction in thatreal languageis alwaysgeneratedin thecontextof somesituationS(real or imaginary), so a more comprehensivemodel would be concernedwith P(C I S), that is, languageproductionin context. This is lessimportant, however , in the translationsettingsincewe produceCt in the contextof a source relationgraphCs andwe assumethe availability of a modelfor P (CtiCs ) . 5.2 Content Derivation Model The model for deriving the relation graph of a phraseis taken to consist of " " choosinga lexical head ho for the phrase(what the phraseis about ) followed " " by a seriesof nodeexpansion steps. An expansionsteptakesa node andchoosesa possiblyempty setof edges(relation labelsandendingnodes)

40

Chapter2

startingfrom that node. Here we consideronly the caseof relation graphsthat are treeswith unorderedsiblings. To start with, let us take the simplified casewhere a headword h has no optional or duplicateddependents(i.e., exactly one for eachrelation). There will be a setof edges E (h) = {rl (hiwI ), r2(h, W2) ...rk(h, Wk)} correspondingto the local ttee rootedat h with dependentnodeswI ' " Wk' The set of relation edgesfor the entire derivation is the union of theselocal edge sets. To determinethe probability of deriving a relation graph C for a phrase " headedby howe makeuseof parameters(" dependencyparameters ) P(r (h, w) I h, r ) for the probability, given a nodeh anda relationr , that w is an r -dependentof h. Under the assumptionthat the dependentsof a headare chosenindependently from oneanother, the probability of deriving Cis :

P(C) = P(Top(ho n Pr h w h r r(h, w)EC ( ( , ) I , ) whereP(TOP(ho is the probability of choosinghoto startthe derivation. If we now remove the assumptionmade earlier that there is exactly one r dependentof a head, we needto elaboratethe derivation model to include . We modelthis by parameters choosingthe numberof suchdependents P(N (r , n) I h) that is, the probability that headh has n r -dependents . We will refer to this " detail " Our as a . probability parameter previousassumptionamountedto stating that this wasalways 1 for n = 1 or for n = ODetailparametersallow us to model, for example, the number of adjectival modifiers of a noun or the " " degree to which a particularargumentof a verb is optional. The probability of an expansionof h giving rise to local edgesE (h) is now: P(E (h) I h) = nr P (N (r , nr) I h) k (nr) nl Sisnr P ( r (h, w'; ) I h, r ) wherer rangesoverthe setof relationlabelsandh hasnr r -dependents ;;. w'i . . .MI k(nr) is a combinatoricconstantfor taking accountof the fact that we are not distinguishingpermutationsof the dependents(e.g., therearenr! permutations of the r -dependents ofh if thesedependentsareall distinct). So if hois the root of a treeC, we have

andQuantitative Modelsof Speech Translation Qualitative

41

P(C) = P(Top(ho n P (Ec (h) I h) hEheads (C) whereheads(C) is the setof nodesin C andE c(h) is the setof edgesheadedby h in C. The above ; formulationis only an approximationfor relation graphsthat are not treesbecausethe independence assumptionswhich allow the dependency to be simply multiplied togetherno longerhold for thegeneralcase. parameters Dependencygraphswith cyclesdo ariseasthe mostnaturalanalysesof certain , but calculatingtheir probabilitieson a node-by-node linguistic constructions basisasabovemay still provideprobabilityestimatesthat areaccurateenough for practicalpurposes. 5.3 Generation Model We now return to the generationmodelP(W I C) . As mentionedearlier, since C includesthe words in Wand a set of relationsbetweenthem, the generation modelis concernedonly with surfaceorder. Onepossibility is to use" bi-relation " parametersfor the probability that an r ,- dependentimmediatelyfollows an r}- dependent . This approachis problematicfor our overall statisticalmodel becausesuchparametersarenot independentof the " detail" parametersspecifying the numberof r-dependentsof a head. " We thereforeadoptthe useof " sequencing , thesebeingprobaparameters bilities of particularorderingsof dependentsgiven that the multiset of dependency relationsis known. We let the identityrelation e standfor the headitself. Specifically, we haveparameters P(s I M (s wheres is a sequenceof relation labelsincluding an occurrenceofe andM (s) is the multisetfor this sequence . For a headh in a relation graphC, let sWCh be the sequence of dependentrelationsinducedby a particularword string Wgenerated from C. We now have

P(WIC)=nhEW IM(SWCh (nr ~ )P(SWCh whereh rangesover all the headsin C, andnr is the numberof occurrencesof r in SWCh ' assumingthat all orderingsofnr -dependentsareequally likely. We canthususethesesequencingparametersdirectly in our overall model. To summarize,our monolingualmodelsarespecifiedby: . TopmostheadparametersP{Top{h . DependencyparametersP{r {h, w) I h, r )

Chapter2

. Detail parametersP(N (r , n) I h) . SequencingparametersP (s I M (s The overall model splits the contributionsof content P (C) and ordering P(W I C) . However, we may also want a model for P(W), for example, for -recognitionhypotheses . Combining our contentand ordering pruning speech modelswe get: P(W) = LP (C) P (W I C) c = I h) LP (Top(hc n P (SWCh ChEW P (r (h, w) I h, r ) n r(h, w)EEc(h) The parametersP(s I h) can be derived by combining sequencingparameters with the detail parametersfor h. 6 Translation Model 6.1 Mapping Relation Graphs As alreadymentioned, the translationmodel definesmappingsbetweenrelation graphsCs for the sourcelanguageandCt for the targetlanguage.A direct (though incomplete) justification of translation via relation graphs may be basedon a simplereferentialview of naturallanguagesemantics . Thus nominals andtheir modifierspick out entitiesin a (real or imaginary) world; verbs andtheir modifiersrefer to actionsor eventsin which the entitiesparticipatein roles indicatedby the edgerelations. On this view, the purposeof the translation mappingis to determinea targetlanguagerelationgraphthat providesthe best approximationto the referentialfunction inducedby the sourcerelation . graph. We call this approximatingreferentialequivalence This referentialview of semanticsis not adequatefor takingaccountof much of the complexity of natural language, including many aspectsof quantification , distributivity, andmodality. This meansit cannotcapturesomeof the subtleties that a theory basedon logical equivalencemight be expectedto. On the otherhand, whenwe proposeda logic-basedapproachasour qualitativemodel, we hadto restrictit to a simplefirst orderlogic anywayfor computationalreasons , and even then it did not appearto be practical. Thus using the more impoverishedlexical relationsrepresentationmay not be costing us much in practice. One aspectof the representationthat is particularly useful in the translation applicationis its conveniencefor partial or incrementalrepresentationof con-

Qualitative and Quantitative Models of Speech Translation

tent- we canrefine the representation by the additionof further edges.A fully specifieddenotationof the meaningof a sentenceis rarely requiredfor translation , a complete , andas we pointedout when discussinglogic representations not have been intended the . by specificationmay speaker Although we have not provideda denotationalsemanticsfor setsof relation edges, we anticipate that this will be possiblealong the lines developedin monotonicsemantics [Alshawi andCrouch, 1992] . 6. TranslationParameters To be practical, a modelfor P(C, I Cs) needsto decomposethe sourceandtarget graphsCs and C, into subgraphssmall enoughthat subgraphtranslation " parameterscanbe estimated.We do this with the help of nodealignmentrelations " betweenthenodesof these graphs. Thesealignmentrelationsaresimilar in somerespectsto the alignmentsusedby Brown et al. [ 1990] in their surface translationmodel. The translationprobability is then the sum of probabilities over different alignmentst

ttanslationmapping. For our quantitativedesign, we adopta simple model in which lexical and . In this model relation(structural) probabilitiesare assumedto be independent the alignmentrelationsarefunctionsfrom the word occurrencenodesof C, to the word occurrencesof Cs. The idea is that I (vp = Wimeansthat the source word occurrenceWi" gaverise" to the target word occurrenceVjoThe inverse relation1 1neednot be a function, allowing different numbersof wordsin the . sourceandtargetsentences We decomposeP(C" I I Cs) into " lexical" and " structural" probabilitiesas follows: P (C" I I Cs) = P (N ,, 1 IN s)P (E , IN ,, 1 , Cs) whereN , andNsarethe nodesetsfor C, andCsrespectively,andE, is the setof edgesfor the targetgraph. The first factor P(N ,, 1 IN s) is the lexical componentin that it doesnot take into accountanyof therelationsin the sourcegraphCs' This lexical component is the productof alignmentprobabilitiesfor eachnodeof Ns: P(N " I I Ns) =

n WiENs

p( fl (Wi)= {vl...v'!} I Wi).

Chapter2

That is, theprobability that/ mapsexactlythe (possiblyempty) subset{ vI ...v'/} of Nt to Wi. Thesesetsare assumedto be disjoint for different sourcegraph nodes, so we canreplacethe factorsin the aboveproductwith parameters : P (M I w) where W is a sourcelanguageword and M is a multiset of target language words. We will derivea targetsetof edgesEt of Ct by k derivationstepswhich partition the setof sourceedgesEs into subgraphsS1. . . Sk. Thesesubgraphsgive riseto disjoint setsof relationedgesT1... T k which togetherform Et. The structural componentof our translationmodel will be the sumof derivationprobabilities for suchan edgesetEt. For simplicity, we assumeherethatthe sourcegraphCsis a tree. This is consistent with our earlierassumptionsaboutthe sourcelanguagemodel. We take our partitionsof the sourcegraph to be the edgesetsfor local trees. This ensures that the partitioning is deterministicso the probability of a derivationis theproductof theprobabilitiesof derivationsteps. More complexmodelswith largerpartitionsrootedat a nodearepossible, but theserequireadditionalparameters for partitioning. For the simple model it remainsto specify derivation stepprobabilities. The probability of a derivationstepis given by parametersof the form: p (TI I Si' , / i ) whereSi' andTi ' areunlabeledgraphsand/ i is a nodealignmentfunctionfrom Ti ' to Si' . Unlabeledgraphsarejust like our relationedgegraphsexceptthatthe nodesarenot labeledwith words(theedgesstill haverelationlabels). To apply a derivationstepwe needa notion of graphmatchingthat respectsedgelabels: g is an isomorphism(modulonodelabels) from a graphG to a graphH if g is a one-oneandonto function from the nodesof G to the nodesof H suchthat r (a, b) EG iff r (g(a),g(b EH . The derivationstepwith parameterP( T i' I Si' , / i ) is applicableto the source edgesSi, underthe alignment/ . giving rise to the targetedgesTi if (i ) thereis an isomorphismhi from SI to Si, (ii ) thereis an isomorphismgi from Ti to TI , and (iii ) for any nodev of Ti it mustbe the casethat hi( f i(gi(V ) = f (v) . This lastconditionensuresthat the targetgraphpartitionsjoin up in a way that is compatiblewith the nodealignmentf

andQuantitative Modelsof Speech Translation Qualitative

45

The factoringof the translationmodel into theselexical andstructuralcomponents meansthat it will overgeneratebecausetheseaspectsarenot independent . It is thereforeappropriateto in translationbetweenreal naturallanguages filter translationhypothesesby rescoringaccordingto the versionof the overall statisticalmodelthat includedthe factorsP (C,)P (Cs I C,) so that the target languagemodel constrainsthe output of the translationmodel. Of course, in this casewe needto model the translationrelation in the " reverse" direction. This canbe donein a parallelfashionto the forward directiondescribedabove.

7 Conclusions Our qualitative and quantitativemodelshave a similar overall sttuctureand thereareclear parallelsbetweenthe factoringof logical constraintsand statistical , for example, monolingualpostulatesand dependencyparameters parameters . The parallelismwould , bilingual postulatesandtranslationparameters havebeencloserif we hadadoptedID/ LPstylerules[Gazdaret al., 1985] in the qualitativemodel. However, we arguedin section3 that our qualitativemodel suffered from lack of robustness , from having only the crudest meansfor between , and from being computationally competing hypotheses choosing . intractablefor largevocabularies The quantitativemodel is in a muchbetterpositionto copewith theseproblems . It is lessbrittle becausestatisticalassociationshavereplacedconstraints featural , selectional, etc.) that must be satisfied exactly. The probabilistic ( modelsgive us a systematicand well-motivated way of ranking alternative . Computationally, the quantitativemodel lets us escapefrom the hypotheses undecidabilityof logic-basedreasoning. Becausethis model is highly lexical, we can hopethat the input words will allow effective pruning by limiting the numberof searchpathshavingsignificantly high probabilities. We retainedsomeof the basicassumptionsaboutthe sttuctureof language whenmoving to the quantitativemodel. In particular, we preservedthe notion of hierarchicalphrasesttucture. Relationsmotivatedby dependencygrammar madeit possibleto do this without giving up sensitivityto lexical collocations which underpinsimplestatisticalmodelslike N-grarns. The quantitativemodel also reducedoverall complexity in termsof the setsof symbolsused. Inaddition to words, it only requiredsymbolsfor dependencyrelations, whereasthe qualitativemodel requiredsymbol setsfor linguistic categoriesand features, anda setof word sensesymbols. Despitetheir apparentimportanceto translation , thequantitativesystemcanavoid the useof word-sensesymbols(andthe

Chapter2 problems of granularity they give rise to ) by exploiting statistical associations between words in the target language to filter implicit sensechoices. Finally , here is a summary of our reasons for combining statistical methods with dependency representations in our language and translation models: . Inherent lexical sensitivity of dependency representations, facilitating parameter estimation . Quantitative preference based on probabilistic derivation and translation . Incremental or partial , or incremental and partial , specification of the content of utterances, particularly useful in translation . Decomposition of complex utterances through recursive linguistic structure These factors suggest that dependency grammar will play an increasingly important role as language processing systems seek to combine both structural

andcollocational infonnation . Acknowledgments

I am grateful to Fernando Pereira, Mike Riley , and Ido Dagan for valuable discussions on the issues addressedin this paper. Fernando Pereira and Ido Dagan also provided helpful comments on a draft of the paper. References H. Alshawi and D. Carter. Training and ScalingPreferenceFunctionsfor Disambiguation . ComputationalLinguistics, 20: 635- 648, 1994. H. AIshawi, D. Carter, B. Gamback,andM. Rayner. Swedish-EnglishQL F Translation. In H. Alshawi, editor, TheCore LanguageEngine. Cambridge, Mass.: The MIT Press, 1992. H. AIshawi and R. Crouch, Monotonic SemanticInterpretation. In Proceedingsof the 30th Annual Meetingof the Associationfor ComputationalLinguistics, Newark, Del., 1992. E. Brill . Automatic Grammar Induction and ParsingFree Text: A TransfonnationBasedApproach. In Proceedingsof the 31st Annual Meeting of the Associationfor ComputationalLinguistics, pp. 259- 265. Columbus, Ohio, 1993. P. Brown, J. Cocke, S. Della Pietra, F. Jelinek V. Della Pietra, J. Lafferty, R. Mercer, andP. Rossin. A StatisticalApproachto MachineTranslation, ComputationalLinguistics , 16: 79- 85, 1990. J. Chang, Y. Luo, and K. SuoGPSM: A GeneralizedProbabilisticSemanticModel for Ambiguity Resolution. In Proceedingsof the 30th Annual Meeting of the Association ' for ComputationalLinguistics, pp. 177- 192. Newark, Del., 1992.

QualitativeandQuantitativeMnde1sof Speech Translation J. Chang and K . Su, A Corpus-Based Statistics-Oriented Transfer and Generation Model for MachineTranslation. In Proceedingsof the 5th International Conference on Theoretical and Methodological Issues in Machine Translation, Kyoto, Japan, 1993. I. DaganandA . Itai. Word SenseDisambiguationUsing a SecondLanguageMonolingual Corpus. ComputationalLinguistics, 20: 563- 596, 1994. I. Dagan, S. Marcus, and S. Markovitch. ContextualWord Similarity and Estimation from SparseData. In Proceedingsof the 31st Annual Meeting of the Associationfor ComputationalLinguistics, pp. 164- 171. Columbus, Ohio, 1993. G. Gazdar, E. Klein, G. K. Pullum, andI . A . Sag. GeneralisedPhraseStructureGrammar . Oxford, Blackwell, 1985. D. Hindle and M. Rooth. StructuralAmbiguity and Lexical Relations, Computational Linguistics, 19: 103- 120, 1993. J. R. Hobbs, M. Stickel, P. Martin, andD; Edwards. InterpretationasAbduction. In Proceedings of the 26th Annual Meetingof the Associationfor ComputationalLinguistics, pp. 95- 103. Buffalo, 1988. R. A. Hudson, WordGrammar. Oxford, Blackwell, 1984. P. IsabelleandE. Macklovitch, TransferandMT Modularity. In Proceedingsof the 11th InternationalConferenceon ComputationalLinguistics, pp. 115- 117. Bonn, Germany, 1986. F. Jelinek, R. L. Mercer, and S. Roukos. Principlesof Lexical LanguageModeling for . Sondhi, editors, Advancesin SpeechSignal SpeechRecognition. In S. Furui andMM Processing.New York, Marcel Dekker, 1992. M. McCord. A MultiTarget MachineTranslationSystem. In Proceedingsof the International Conferenceon Fifth GenerationComputerSystems , pp. 1141- 1149. Tokyo, 1988. C. S. Mellish. ImplementingSystemicClassificationby Unification. Computational Linguistics, 14: 40- 51, 1988. : Volumel- Fundamentals C. J. Pollard and I. A. Sag. Information BasedSyntaxand Semantics . Stanford, Calif., Centerfor the Studyof LanguageandInformation, 1987. F. Pereira, N. Tishby, and L. Lee. DistributionalClusteringof English Words. In Proceediny -, Qfthe Associationfor ComputationalLinguistics, ~,s of. the31st Annual M eetiny

- 190 . . Columbus , Ohio,1993 pp. 183

M. RaynerandH. Alshawi. Deriving DatabaseQueriesfrom Logical Formsby Abductive Definition Expansion. In Proceedingsof the Third Conferenceon Applied Natural LanguageProcessing.Trent, Italy, 1992. M. D. Richardand R. P. Lippmann. Neural Network ClassifiersEstimateBayesiana posteriori Probabilities. Neural Computation, 3: 461- 483, 1991. S. M. Shieber. An Introduction to Unification-BasedApproaches to Grammar. Stanford , Calif., Centerfor the Studyof LanguageandInformation, 1986.

Chapter3 of StudyandImplementation Combined for Techniques AutomaticExtractionof Tenninology

BeatriceDaille

The acquisition of terminology for particular domains has long been a significant problem in natural language processing , requiring a great deal of manual effort . Statistical techniques hold out the promise of identifying likely candidates for domain -specific terminology , but analyzing word co-occurrences in text often uncovers collocations that are statistically significant but termino logically irrelevant - for example, frozen forms , collocations more characteristic of the language in general than the particular domain , and the like . . Assessing statistical significance is certainly part of the problem , for exampIe , Dunning [ 1993] argues convincingly that many commonly used statistics , such as the x2 test, are based on assumptions that do not generally hold for text. One might conjecture , however , that the problem lies not only in the statistics per se, but in deciding what counts as a co-occurrence. " In her Study and Implementation of Combined Techniquesfor Automatic " Extraction of Terminology , Beatrice Daille takes this conjecture seriously , and explores a method in which the co -occurrences of interest are defined in terms of surface syntactic relationships rather than proximity of words or tags within a fixed window (compare with [ Smadja, 1993] , for example) . Shefinds that filtering based on even shallow a priori linguistic knowledge proves useful ,. in addition , she investigates a number of alternative statistics (simple frequency , mutual information , likelihood ratio , etc.) in order to identify which of them is best for the purpose of identifying lexical patterns that constitute domain -specific terminology . The approach to combining linguistic and statistical methods taken in ' Daille s work- using shallow syntactic relationships to define the co-occur rences over which statistical methods operate - is quite general , and has also proved useful in work other than terminology extraction , notably in word clustering and automatic thesaurus generation ( e.g . [ Grefenstette, 1994; Hindle , 1990,. Pereira etal ., 1993] ,. also see Hatzivassiloglou , chapter4 ) .- Eds .

3 Chapter 1

Introduction

A tenninology bank containsthe vocabularyof a techliical domain: tenDs, which refer to its concepts. Building a terminologicalbank requiresa lot of time andboth linguistic andtechnicalknowledge.The issueat stakeis theautomatic extractionof tenninology of a specific domain from a corpus. Current researchon extractingtenninology useseither linguistic specificationsor statistical es. Concerningthe fonner, [Bourigault, 1994] hasproposeda approach of lexical units programwhich extractsautomaticallyfrom a corpussequences . This list whosemorphosyntaxcharacterizesmaximal technicalnoun phrases is given to a tenninologistto be checked. For the latter, several of sequences works ([Lafon, 1984; Church and Hanks, 1990; Calzolari and Bindi , 1990; Smadjaand McKeown, 1990]) haveshownthat statisticalscoresare usefulto extract collocationsfrom corpora. The main problem with one or the other " " approachis the noise : indeed, morphosyntacticcriteria are not sufficient to isolatetenDs, andcollocationsextractedby statisticalmethodsbelongto various : functional, semantic, thematic, or uncharacterizable typesof associations ones. Our goal is to use statisticalscoresfor extractingdomain-specific collocations only and to forget aboutthe other types of collocations. We proceedin two steps: fIrSt, by applyinga linguistic filter which selectscandidatesfrom the corpus; thenby applyingstatisticalscoresrankingthesecandidatesandselecting the scoresthat fit our purposebest, in other words, scoresthat concentrate their high valuesto tenDSand their low valuesto co-occurrencesthat are not tenDS.

2 LinguisticData First, we studythe linguistic specificationson the natureof tenDsin the technical for French. Then, taking into accountthese domainof telecommunications the method and the program that extract and results we , present linguistics countthe candidatetenDs. 2.1 Linguistic Specifications Termsaremainly multiword units of nominal type. They could be considered as a subclassof nominal compoundsthat inherit morphologicaland syntactic properties which have been stressedby studies on nominal compounding ([Grosset al., 1986; Noally, 1990], etc.) . To be more precise, the structureof termsbelongsto well-known morphosyntacticstructuressuchasN ADJ,N } de

CombinedTechniquesfor Extractionof Terminology

N2, etc. and fits the generaltypology of French compoundselaboratedby [Mathieu-Colas, 1988] . Some graphic indications (hyphen), morphological indications(restrictionsin inflection), andsyntacticones(lack of article inside the structure) could alsobe goodcluesthat a nounphraseis a term. [But these propertiesare not discriminatorycontrary to the semanticproperty of terms: their referentialmonosemy.] A term is a label that refersto a concept, and in the bestof all possibleworlds, a term refersuniquelyto oneandonly oneconcept within a given subjectfield , andthis independentlyof its textualcontext. Terminologists, themselvesagreethat they encounterdifficulty in defining exactly how to chooseand delimit terms, sincethis semanticcriterion relies mainly upon intuition. So, we havereinforcedthe criterion of uniquereferent with that of unique translation. A term as it refers to a unique and universal conceptis ideally alwaystranslatedby anothersuchterm in anotherlanguage (though terms may have free or even contextuallydeterminedvariants). We havemanuallyextractedFrenchterms, following thesecriteria from our bilingual corpusavailablein both Frenchand English, the Satellite Communication Handbook (SCH), containing 200,000 words in each language. The translationsof theseterms mostly possessthe morphosyntacticstructuresof English compoundstoo. Then, we classifiedterms accordingto their length; the lengthof a term is definedasthe numberof main items it contains.} From this classification, it appearsthat termsof length2 areby far the mostfrequent ones. Becausestatisticalmethodsdemanda goodrepresentationin numberof samples, we decidedto extract in a first round only terms of length 2, which we will call base-terms, and which matcheda list of previously determined patterns: N ADJstationterrienne(Earth station) N } de (DET ) N2 zonede couverture(coveragezone) N } a (DET ) N2 reflecteura grille (grid reflector) N } PREP N2 liaisonpar satellite(satellite link) N } N2diodetunnel(tunneldiode) Of course,termsexistwhoselengthis greaterthan2. But themajorityof termsof lengthgreaterthan 2 are createdrecurrentlyfrom base-terms. We havedistinguished threeoperationsthatleadto a termof length3 from a termof length1 or 1. Main itemsarenouns, adjectives, adverbs,etc. Neitherprepositionsnor detenniners aremain items.

Chapter3

" 2: " overcomposition , modification, and coordination. We will illusttate these operationswith a few exampleswherethebase-tenDSappearinsidebrackets: 1. Overcomposition Two kinds of overcompositionhavebeenpointedout: overcompositionby juxtapositionandovercompositionby substitution. (a) Juxtaposition A tenD obtainedby juxtaposition is built with at least one base-tenD whosestructurewill not be altered. The examplebelow illustratesthe juxtapositionof a base-tenDand a simplenoun: N ) PREP ) [N2 PREP2 N3] modulationpar [deplacementde phase] ([phaseshift] keying) (b) Substitution Given a base-tenD, one of its main items is substitutedby a base-tenD whoseheadis this main item. For example, in the N ) PREP ) N2structure, N ) is substitutedby a basetenDof N ) PREP2 N3structureto createa tenD PREP structure : of N ) PREP2 N3 ) N2 reseaua satellites+ reseaude transit - reseaude transit a satellites (satellitetransit network).

We note in the aboveexamplethat the structureof reseaua satellites (satellitenetwork) is altered. 2. Modification Modifiers that could generatea new tenD from a base-tenD appeareither insideor after it. (a) Insertionof modifiers Adjectivesand adverbsare the currentmodifiersthat could be inserted inside a base-tenD structure: adjectivesin the N ) PREP (DET) N2 structure andadverbsin the N ADJone: liaisonsmultiples par satellite(multiple [ satellite links] ) reseauxentierement numeriques(all [ digital networksJ) (b) Post-modification ADJN structure Adjectivesand adverbialprepositionalphrasesof PREP main modifiers that lead to are the the creation of new tenDS: postadjectiv can modify any kind of base-tenD; for example [ station terrienne] brouilleuse(interfering[ earth(-)stationJ) . Adverbialprepositional phrasesmodify either simple nouns or base-tenns2: amplifica2. In this case, the lengthof the tenDis equalto 4.

CombinedTechniquesfor Extractionof Tenninology

teur( s) [afaible bruit] ([ low noise] amplifiers , [ interfaces) usagerreseau ] [ user-networkinterfaces)]) . ] [ a usagemultiple] ([multipurpose 3. Coordination Coordinationis a rather complex syntacticphenomenon(term coordination has been studied in [Jacquemin, 1991]) and seldom generatesnew terms. Let us examinea rare exampleof a term of length 3 obtainedby coordination: Nt de N3 + N2de N3- + Nt et N2 de N3 assemblagede paquet + desassemblagede paquets - + assemblageet !disassembly desassemblagedepaquets(packetassembly ) It is difficult to determinewhethera modified or overcomposedbase-term is or is not a term. Take, for example~bandelaterale unique(singlesideband): bandelaterale (sideband ) is a base-term of structureN ADJandunique(single) modifier a very commonpost adjectivein French. The fact that bandelaterale unique is a term is indicatedby the presenceof the abbreviationBLU (88B). As abbreviationsare not introducedfor all terms, the right way is surely to fIrst extract base-terms, that is, bande laterale (sideband ) . Once you have of terms from the extract baseterms, you caneasily lengthgreaterthan corpus 2, at leastpost modified baseterms and overcomposedbase-terms by juxtaposition. But~evenif we havedecidedto exb' actonly base-tenDs(length2), we have to takeinto accounttheir variations, or at leastsomeof them. Variantsof base: tenDSareclassifiedunderthe following categories 1. Graphicandorthographicvariants By graphicvariants, we meaneithertheuseor not of capitalizedletters(Service national or servicenational (Did )omesticservice), or the presenceor not of a hyphen inside the N I N2 structure(modepaquet or mode-paquet (packet (-)mode)). N2 structure. For this structure, the OrthographicvariantsconcernN I PREP numberof N2 is generallyfixed, either singularor plural. However, we have encounteredsome exceptions: reseau(x) a satellite, reseaux(x) a satellites (satellitenetworks)). 2. Morphosyntacticvariants Morphosyntacticvariantsrefer to thepresenceor not of an articlebeforetheN2 ' ' in the N I PREP N2 structure: ligne d abonne, lignes de I abonne(subscriber lines), to the optional characterof the preposition: tension helice, tension d' helice (helix voltage), andto synonymyrelation betweentwo base-tenDsof

Chapter3 different sttuctures: for example, N ADJand ni a N2: reseau commute, reseau a commutation (switched network ) . 3. Elliptical variants A base- tenD of length 2 could be called up by an elliptical fonD: for example , debit , which is used instead of debit binaire (bit rate ) . After this linguistic investigation , we concentrate on ten DSof length 2 (basetenns ) which seem by far the most frequent ones. Moreover , the majority of ten D Swhose length is greater than 2 are built from base-tenDs. A statistical approach requires a good sampling , which base- tenDs provide . To filter basetenDS from the corpus, we use their morphosyntactic sttuctures. For this task, we need a tagged corpus where each item comes with its part of speech and its lemma. The part of speech is used to filter and the lemma to obtain an optimal sampling . We have used the stochastic tagger and the lemmatizer of the Scientific Center of mM -France developed by the speech recognition team ([Derouault , 1985; and EI -Beze, 1993]) .

2.2 Linguistic Filters We now face a choice: we can either isolategeneralcollocationsusing statistics and then apply linguistic filters to retain only morphosyntacticsequences that characterizebase-terms, or apply, first, linguistic filters, andthenstatistics. It is the latter strategythat has beenadopted; indeed, the former has already beenproposedby [Smadja, 1993] and doesnot seemadequateto take into accountterm variations. Indeed, computingstatisticsfirst involves collecting thepossiblecollocatesusinga window of an arbitrarysize. The sizeof the window is generallya compromisebetweena small or a largewindow: If you take a small window size, you miss many occurrences , mainly morphosyntactic variantsasbase-termsmodified by severalinsertedmodifiers, very frequentin French, and multiple coordinatedbase-terms; if you take a longer one, you obtain occurrencesthat do not refer to the sameconceptualentity, many ill formed sequences that do not characterizesterms, and, thus, wrong frequency counts may be. First, using linguistic filters basedon part-of-speechtags appearsto be the bestsolution. Moreover, aspatternsthat characterizesbasetermscanbedescribedby regularexpressions , the useof finite automataseems a naturalway to extractandcountthe occurrencesof the candidatebase-terms. Thefrequencycountsof theoccurrencesof thecandidatetermsarecrucial as they are the parametersof the statistical scores. A wrong frequencycount implies wrong or not relevantvaluesof statisticalscores. The objectiveis to optimize the count of base-term occurrencesand to minimize the count of

CombinedTechniquesfor Extractionof Tenninology

. Graphic, orthographic, andmorphosyntacticvariantsof incorrectoccurrences base-term (exceptsynonymicvariants) aretakeninto accountas well as some syntacticvariationsthat affect the base-term structure: coordinationandinsertion of modifiers. Coordinationof two base-termsrarely leadsto the creation of a new term of length greaterthan 2, so it is reasonableto think that the sequenceequipementsde modulation et de demodulation(modulation and demodulationequipment) is equivalentto the sequenceequipementdemodulation et equipementde demodulation(modulationequipmentand demodulation ). Insertionof modifiers inside a base-term structuredoesnot raise equipment problems, exceptwhenthis modifier is an adjectiveinsertedinsidean N I PREP N2 structure. Let us examinethe sequenceantenneparabolique de reception (parabolic receiving antenna). This sequencecould be a term of length 3 (obtainedeither by overcomposition.or by modification) or a modified baseterm, namely, antenne de reception, modified by the inserted adjective parabolique. On theonehand, we do not wantto extracttermsof lengthgreater than2, but on theotherhand, it is not possibleto ignoreadjectiveinsertion. So, we havechosento acceptinsertionof the adjectiveinsideN I PREP N2 structure. This choiceimpliesthe extractionof termsof length3 of N I ADJPREP N2 structure that areconsideredastermsof length2. However, suchcasesarerareand refer to a N I PREP the majority of N I ADJPREP N2base-term modN2 sequences ified by an adjective. Eachoccurrenceof a base-term is countedequally; we considerthat thereis of the term in the corpus. The occurrenceof equiprobabilityof the appearance base-terms are classifiedunder which characterize morphologicalsequences pairs: a pair is composedof two main itemsin a fixed orderandcollectsall the wherethe two lemmasof the pair appearin oneof the allowedmorsequences ' : ligne d abonne, lignes de phosyntacticpatterns; for example, the sequence ' ' l abonne(subscriberlines), andligne numeriqued abonne(digital subscriber line) areeachone occurrenceof the pair (ligne , abonne ) . lfwe havethe ' coordinatedsequencelignes et servicesd abonne(subscriberlines and services ), we countoneoccurrencefor the pair (ligne , abonne ) andoneoccurrencefor the pair (service , abonne ). Our programscansthe corpus and countsand extractscollocationswhosesyntax characterizesbase-terms. Undereachpair, we find all the differentoccurrencesfoundwith their frequencies and their location in the corpus(file , sentence , item). This programruns extract 8 000 2 minutes to it took fast: for example, , pairsfrom our corpusSCH ) N2 on a Sparcstation ELC (200,000 words) for the structureni prep (DET (551) under Sun-Os Release4.1.3. Resultspresentedin table 3.1 summarize

Chapter3

Table3.1 Exb'aCtion results Corpora

NADJ

N) (prep (Det N2

SCH 1 occurrence 2 occurrences > 2 occurrences total

3,144 655 684 4,483

6,834 1,503 1,616 9,953

5,201 1,507 2,113 8,821

12,167 3,481 6,288 21,936

CBB 1 occurrence 2 occurrences >2 occurrences total

the frequenciesof co-occurrencesexpressedin termsof pairs extractedfrom two corpora, SCHandCBB (CommunicationBlue Book) (800,000 words). In orderto manuallycheckif the candidatebase-termswe haveidentifiedare indeedtermswhenseenin context, andthat we havenot missedany, we have developeda Shell programwhich insertsopeningandclosing bracketsaround the occurrencesof the candidatepairs through the corpora. A sampleof the CBB corpuswherecandidatepairs arebracketedis the following: 582822 on pentmontrerquetoute [2 [ 1 onderadioelectrique] 1 a [3 polarisation] 2 elliptique ] 3 pentetreconsiderecommela sommede deux [4 composantes orthogonales]4 , par exemplede deux [6 [5 ondesa [7 polarisation] 5 rec' tiligne ] 7 perpendiculaires]6 ou d une [8 ondea [ 10 [9 polarisation] 8 circulaire ]9 levogyre] 10et d' une [ 11 ondea [ 13 [ 12polarisation] 11circulaire ] 12dextrogyre] 13 . 582823 une [2 [ 1 caracteristiqueirnportante] 1 du [3 diagramme] 2 de [4 rayonnement ' ] 3 d une antenne]4 ( notamrnentlorsquecelle-ci estmiseen oeuvredansun [5 systemede [6 reutilisation] 5 desfrequences]6 [7 par doublepolarisation ] 7 ) est sa [ 8 puretede polarisation] 8 . The bracketsareindexedto determinetheright openingandclosingbracketof a candidateterm; indeed, somecandidateterms can also appearinside more

CombinedTechniquesfor Extractionof Terminology

complex candidatetenDs: in the aboveexample, the N ADJsequence(onde radioelectrique) inside the N I ADJPREP N2 (onderadioelectriquea polarisalion) correspondsto a tenDof structureni PREP N2 (ondeapolarisation) modified by the insertedadjective(radioelectrique). Twenty bracketedsentences takenat randomhavebeencheckedand only two occurrencesof a researched patternweremissing: . The first miss belongs to the N ADJpattern: the adjective brouilleuse appearsinside parenthesisand is separatedfrom the noun composanteby : une [ 5 composantecontrapolaire] 5 (x) anotheritem itself insideparentheses brouilleuse , ( ) . the secondmissconcernsalsothe N ADJpattern: in the sequence : les polarisationsquasi circulaires, the pair (p.olarisation, circulaire) is not recognized. This error comesfrom the tagger: indeed, the N ADJfmite-statemachineasks for an agreementbetweenthe noun and the adjective and in this sequence , polarisation is well-tagged(feminine substantivein the plural inflection) but circulaire badly (adjectivein the masculineandplural inflection). So, asthere is no agreementbetweenthe adjective and the noun, this occurrenceis not takeninto account. Thesemissesshowthat: 1. It is not possibleto encodein the fmite-statemachineall the marginalpossible . wherea candidatebase-tenDappears sequences 2. The accuracyof this base-tenDextractionprogramreliesuponthe accuracy of the tagger. Now that we haveobtaineda set of pairs, eachpair representinga candidate base-tenD, we apply statistical scoresto distinguish tenDS from non-tenDS . amongthe candidates 3

Lexical Statistics

The problemto solve now is to discoverwhich statisticalscoreis the bestto . So, we computeseveralmeasures : isolatetenDsamongour list of candidates and distance scores . All , associationcriteria, Shannondiversity, frequencies thesemeasurescould not be usedfor the samepurpose: frequenciesare the parametersof the associationcriteria, associationcriteria proposea conceptual sortof the pairs, andShannondiversity anddistancemeasuresarenot discriminatory scoresbut provideothertypesof infonnation.

Chapter3

3.1 Frequenciesand AssociationCriteria From a statisticalpoint of view, the two lemmasof a pair could be considered astwo qualitativevariableswhoselink hasto be tested. A contingencytableis

definedfor eachpair(LitLfl : L,. ' Li' with i + i

4 a c

' Ljl withj +j b d

where: a stands for the frequency of pairs involving both Li and , Lj b stands for the frequency of p.airs involving Li and '" LJ c stands for the frequency of pairs involving L ,.. and , and Lj d standsfor the frequency of pairs involving L ,.. and LJ". The statistical literature proposes many scores which can be used to test the strength of the bond between the two variables of a contingency table. Some are well -known , ~uch as the association ratio , close to the concept of mutual information introduced by [Church and Hanks , 1990] :

1M= log2(a + baa + c )( )

(1)

the<J>2coefficientintroduced by [GaleandChurch,1991]:

or the Loglike coefficientintroducedby [Dunning, 1993] : Loglike = a log a + b log b + clog c + d log d - (a + b) log (a + .b) - (a + c) log (a + c) - (b + d) log (b + d) - (c + d) log (c + d) + (a + b + c + d) log (a + b + c + d)

(4)

A propertyof thesescoresis that their valuesincreasewith the strengthof the bond of the lemmas. We havetried out severalscores(more than 10) including 1M, 2, and Loglike, and we have sorted the pairs following the score value. Eachscoreproposesa conceptualsort of the pairs. This sort, however, could put at the top of the list compoundsthat belong to generallanguage ratherthan to the telecommunications domain. Sincewe want to obtain a list

CombinedTechniquesfor Extractionof Terminology

of telecommunicationterms, it is essentialto evaluatethe correlationbetween the score values and the pairs and to fmd out which scoresare the best to extract terminology. Therefore, we comparedthe values obtained for each scoreto a referencelist of the domain. We obtaineda list of over 6,000 French terms from EURODICAUTOM, the terminology data bank of the EEC, telecommunicationssection, which was developedby experts. We purchased the evaluationon 2,200 Frenchpairs3of N 1de (DET ) N2structure, the mostfrequent and common French term structure, extractedfrom our corpus SCH (200,000 words). To limit the size of the referencelist , we retainedthe intersection betweenour list of candidatesand the EURODICAUTOM list , 1,200 thus gettingrid of termswhich we would not fmd in our corpusanyway, pairs, evenif they belongto this technicaldomain. We assumethat the referencelist , 1,200 pairs of our list of 2,200 candidatepairs, is as completeas possible, so that base-terms that we might identify in our corpusare indeedfound in the referencelist. Eachscoreyields a list wherethe candidatesare sortedaccording to the decreasingscore value. We have divided this list in equivalence classeswhich generallycontain50 successivepairs. The resultsof a scoreare representedgraphically by a histogramin which the x-axis representsdifferent classes, and the y-axis the ratio of good pairs. If all the pairs in a class belongto the referencelist , we obtain the maximumratio of 1; if noneof the pairs appearsin the referencelist , the minimum ratio of 0 is reached.The ideal scoreshouldassignhigh (low) valuesto good (bad) pairs, that is, candidates which belong (which do not belong) to the referencelist (in other words, the histogramof the ideal scoreshould assignto equivalenceclassescontaining the high (low) valuesof the scorea ratio closeto 1 [0]) . We are not going to presenthereall the histogramsobtained(see[Daille, 1994]). All of themshow a generaltrendthat confirms that the scorevaluesincreasewith the strengthof the bond of the lemma. However, the growth is more or lessclear, with more or lesssharpvariations. The most beautiful histogramis the simple frequency of the pair (seefigure 3.1). This histogramshowsthat the more frequentthe pair is, the more likely the pair is a term. Frequencyis the most significant scorefor detectingtermsof a technicaldomain. This resultcontradictsnumerous resultsof lexical resources , which claim that associationcriteria are more : for than example, all the mostfrequentpairs whoseterfrequency significant minological statusis undoubtedsharelow valuesof associationratio [equation ( 1)], as, for example, reseaua satellites (satellite network) 1M = 2.57, 3. Only pairs which appearat leasttwice in the corpushavebeenretained.

Chapter3

Figure 3.1 Frequencyhistogram.

liaisonpar satellite (satellite link) 1M = 2.72, circuit telephonique(telephone circuit ) 1M = 3.32, station spatiale (space station) 1M = 1.17, etc. The remainingproblemwith the sort proposedby frequencyis that it very quickly , that is, pairs which are not terms. So, we havepreferred integratesbad candidates to elect the Loglike coefficient [equation(3)] the best score. Indeed, Loglike coefficient, which is a real statisticaltest, takesinto accountthe pair frequencybut acceptsvery little noisefor high values. To give an elementof comparison, the fIrSt bad candidatewith frequencyfor the generalpatternN 1 (PREP (OET N2 is the pair (cas , transmission ) which appearsin 56th this which is also the fIrst bad candidate with , ; place pair Loglike, appearsin 176thplace. We give in table 3.2 the topmost 11 Frenchpairs sortedby the Loglike coefficient (Logl) (Nbc is the numberof the pair occurrencesand1M the value of associationratio). 3.2 Diversity the marginaldistribution Diversity, introducedby [Shannon, 1949], characterizes of the lemmaof a pair throughthe rangeof pairs. Its computationusesa

CombinedTechniquesfor Extractionof Terminology

Table3.2 Topmostpairs Pairsof Nl (PREP (DET N2 sbucture

The mostfrequent pair sequence

(largeur, bande)

largeurde bande( 197) (bandwidth) temperaturede bruit 110 (noisetemperature ) bandede base( 142) (baseband ) amplificateur(s) de puissance( 137) (poweramplifier) tempsdepropagation (93) (propagationdelay) reglementdes radiocommunications (60) (radio regulation) produit{s) d' intermodulation(61) (intermoduationproduct) taux d' erreur (70) (error ratio) miseen oeuvre(47) (implementation ) telecommunications ) par satellite(88) (satellite communications) bilan de liaison (37) (link budget)

, bruit) (temperature (bande, base) (amplificateur, puissance )

(temps, propagation ) (reglement. radiocommunication)

{produit, intermodulation}

(taux, en-eur) (mise, oeuvre)

, satellite) (telecommunication

(bilan, liaison)

Logl Nbc 1M 1328 223

5.74

777

126 6.18

745

145 5.52

728

137 5.66

612

94 6.69

521

60 8.14

458

61 7.45

420

70

6.35

355

47

7.49

353

99

4.09

344

55 6.42

contingencytable of length n: we give below as an examplethe contingency tablethat is associatedwith the pairsof the N ADJsttucture: N; Adjj

progressif

onde cornet . .. Total

porteur

Total

.. .

19

4

nb

( onde , . )

9

0

nb

( cornet , . )

...

.. .

.. . nb

...

( . , progress

i />

nb

( . , porteur

)

nb(.,.)

Chapter3

Thelinecountsnb;., whicharefoundin therightmostcolumn,represent thedistributio of theadjectives widtregardto a givennoun.ThecolumncountsnbJt whicharefoundon thelastline, represent thedistributionof thenounswith to a . These distributions arecalled" marginaldistributions regard givenadjective " of thenounsandthe for theN ADJstructure . Diversityis computed adjectives for eachlemmaappearing in a pair, usingtheformula: $ ~ nb.. .. HI. = nbI.. lognI.. - L. lJlognbIJ . J- 1 (4) $ ~ .. lognb.. HJ. = nbJ.IognJ. L. nbIJ lJ ;=1 Forexample tableof theN ADJstructure above , usingdIecontingency , diversity of the noun onde is equal to: = H (onde . .) nb(onde ..) log nb(onde ..) (nb(onde . progress . progress if) log nb(onde if) + nb(onde + . l KJrteur . porteur ) log nb(onde ) ...) We note HI , diversity of the first lemma of a pair , and H2' diversity of the second lemma. We take into account the diversity normalized by the number of occurrences of the pairs :

Hi hi= "iiij

Hj hj='iiij The normalizeddiversitieshI andh2aredefinedfrom HI andH2. The normalizeddiversity providesinterestinginformationaboutthe distribution of the pair lemmasin the set of pairs. A lemma with a high diversity meansthat it appearsin severalpairs in equalproportion; conversely,a lemma that appearsonly in one pair owns a zero diversity (minimal value) and this whateverthe frequencyof the pair. High valuesof hI appliedto the pairs of N ADI structurecharacterizesnounsthat could be seenas keywordsof the domain : reseau(network), signal, antenne(antenna), satellite. Conversely, high valuesof h2appliedto the pairsof N ADIstructurecharacterizes adjectivesthat do not takepart in base-termssuchasnecessaire(necessary ), suivant(following ), important, different (various), tel (such), etc. The pairswith a zerodiversity on one of their lemmasreceivehigh valuesof associationratio and other associationcriteria and a nondefinitevalue of Loglike coefficient However, thediversity is moreprecisebecauseit indicatesif the two lemmasappearonly togetherasfor (ocean , indien ) (indian ocean) (HI = hi = H2 = h2 = 0),

Combined ITechniquesfor Extractionof Tenninolog~ or if not, which of the two lemmas appear only with the other , as for ( r6s eau , mail16 ) ( mesh network ) ( H2 = h2 = 0), where the adjective maille appears = = only with reseau or for ( codeur , id6al ) (ideal coder ) ( H. h . 0 ) where the noun codeur appears only with the adjective ideal. Oilier examples are: ( ile , salomon ) (solomon island) , ( h6lium , gazeux ) (helium gas), , 6cho ) (echo suppressor) . These pairs collect many frozen (suppresseur compounds and collocations of the current language. In future work, we will investigate how to incorporate the good results provided by diversity into an automatic extraction algorithm .

3.3 DistanceMeasures Frenchbase-termsoften acceptmodificationsof their internalstructure, ashas beendemonstratedpreviously. Eachtime an occurrenceof a pair is extracted and counted, two distancesare computed: the numberof items, Dist, and the numberof main items, MDist, which occurbetweenthe two lemma.~. Then, for eachpair, the meanandthe varianceof thenumberof itemsandmainitemsare computed.The varianceformula is:

V(X) =*L (Xi- xf U (X ) = JV ( X) The distance measuresbring interesting information concerningthe morphosyntacticvariationsof the base-terms, but theydo not allow makinga decision on thestatusof term or non-tenDof a candidate.A pair thathasno distance variation, whateverthe distance, is or is not a term; we give now someexamples of pairswhich haveno distancevariationsandwhich arenot terms: paire designal (a pair of signal), typed 'antenne(a typeof antenna), organigramme de la figure (diagramof thefigure), etc. We illustratebelow how the distance measuresallow attributing to a pair its elementarytype automatically, for DETN2, or N I AD] PREP ) N2for (OET N2, N I PREP example,eitherN I N2, N I PREP . the generalN I (PREP OET structure ( N2 1. Pairswith no distancevariation V(X ) = 0 (a) N I N2: Dist = 2 MDist = 2 . liaison semaphore , liaisonssemaphores(commonsignalinglink(s . canal support, canauxsupport, canauxsupports(bearerchannel) (b) N I PREP N2: Dist = 3 MDist = 2 . accuses) de reception(acknowledgement of receipt) . refroidissementa air , refroidissementpar air (cooling by air )

Chapter3

DETN2: Dist = 4 MDist= 2 (c) N} PREP

. sensibiliteau bruit (susceptibilityto noise) . reconnaissance dessignaux(signal recognition) (d) Nt AD] PREP N2: Dist = 4 MDist = 3 . reseaulocal de lignes, reseauxlocauxde lignes(local line networks ) . servicefixe par satellite
Conclusion

We have presented a combining approach for automatic term extraction . Starting from a first selection of lemma pairs representing candidate terms from a morphosyntactic point of view , we have applied and evaluated several statistical scores. The results were surprising : most association criteria ( e.g ., mutual association) did not give good results contrary to frequency . This bad behavior of the association criteria could be explained by the introduction of linguistic filters . We can note in any event that frequency undoubtedly characterizes terms, contrary to association criteria , which select in their high values frozen compounds belonging to general language. However , we preferred to elect the Loglike criterion rather than frequency as the best score. This latter takes into account the frequency of the pairs but provides a conceptual sort of high accuracy. Our system, which uses fmite automata, allows us to increase the results of the extraction of lexical resources and to demonstrate the efficiency of incorporating linguistics in a statistical system. This method has

CombinedTechniquesfor Extractionof Terminology

been extendedto bilingual terminologyexttactionusing alignedcorpora [Daille et al., 1994] . Acknowledgments I thank the mM -France team, and in particular Eric Gaussier and Jean- Marc Lange, for the tagged and lemmatized version of the French corpus and for their evaluation of statistics, and Owen Rambow for his review of the manuscript . Researchwas supported by the European Commission and mM -France, through the ET - 10/63 project . References Didier Bourigault. Acquisitionde terminologie. Pill thesis, EHESS, France, 1994. Nicoletta Calzolari and Remo Bindi. Acquisition of lexical information from a large textual italian corpus. In Proceedingsof the ThirteenthInternational Conferenceon ComputationalLinguistics, Helsinki, 1990. KennethWard Church and Patrick Hanks. Word associationnorms, mutual information , andlexicography. ComputationalLinguistics, 16( 1) : 22- 29, 1990. BeatriceDaille. Approchemixtepour I ' extractionautomatiquede terminologie: statistiqueslexicaiesetfiltres linguistiques. Pill thesis, Universityof Paris7, 1994. BeatriceDaille, Eric Gaussier,andJean-Marc Lange. Towardsautomaticextractionof monolingualand bilingual terminology. In Proceedingsof the FifteenthInternational Conferenceon ComputationalLinguistics- COUNG-94, Kyoto, Japan, 1994. Anne-Marie Derouault. Modelisationd' une languenaturel/e pour la disambiguation . Pill thesis, University of Parisvll , 1985. deschainesphonetiques Ted Dunning. Accuratemethodsfor the statisticsof surpriseandcoincidence.Computational Linguistics, 19( 1) : 61- 76, 1993. ' Marc EI-Beze. LesModeiesde LangageProbabilistes: QuelquesDomainesd Applications . Pill thesis, University of Paris-Nord, 1993. Habilitation a diriger les recherches [thesisrequiredin Franceto be a professor]. for paralleltexts. InProceedings William A. GaleandKennethW. Church. Concordances of the SeventhAnnual Conferenceof the UW Centrefor the New OED and Text Research,UsingCorpora, pp. 40- 62, Oxford, 1991. . Explorationsin AutomaticThesaurusDiscovery. Kluwer, 1994. GregoryGrefenstette GastonGross, JacquesChaurand, Robert Vives, Michel Mathieu-Colas, and Pierre . Technicalreport, A.TiP.- Nouvel/es recherches Billy . Typologiedes nomscomposes sur Ie langage, University of Paris 13, Villetaneuse, 1986. D. Hindle. Noun classificationfrom predicate-argumentstructures. In Proceedingsof the 28th Annual Meeting of the Assocationof ComputationalLinguistics, Pinsburgh, Penna., pages268- 275, 1990. Associationfor ComputationalLinguistics, Morristown, NJ.

Chapter3

ChristianJacquemin . Transformationsdes nomscomposes . PhD thesis, University of Paris7, 1991. Pien-e Lafon. Depouillementset Statistiquesen Lexicometrie. Geneva, Slatkine-Champion , 1984. Michel Mathieu-Colas. Typologiedesnomscomposes . TechnicalReport7, programme de recherchescoordonees..il #!ormatiQueet linp,uistiQue," University of Paris13. Paris. France, 1988. michele Noally. Le substantifep;thete. Paris, PUF, 1990.

Fernando Pereira , NaftaliTishby - , andLillianLee. Distributionalclustering - of English words. In Proceedingsof the31stAnnualMeetingof theAssociationfor Computational

. , June1993 Linguistics

C. E. Shannon, A Mathematicaltheory of communication. Urbana: University of Dlinois Press, 1949. Frank Smadja. Retrieving collocationsfrom text: Xtract. ComputationalLinguistics, 19( 1) : 143- 177, 1993. FrankA. Smadjaand KathleenR. McKeown. Automatically extractingand representing collocationsfor languagegeneration.In Proceedingsof the28th AnnualMeetingof theAssociationfor ComputationalLinguistics, pp. 252- 259, 1990.

Chapter 4 Do We Need Linguistics When We Have Statistics? A Comparative Analysis of the Contributions of Lin2- Uistic

Vasileios Hatzivassiloglou

Cuesto a StatisticalWord GroupingSystem

Is linguistic knowledge useful for a particular task, and what kinds of linguistic knowledge furnish the most benefit ? Whether in the affirmative or in the ' negative, the answer to these questions often comesfrom a researcher s unsystematic past experience - or , equally often ,from intellectual blases rather than careful exploration of the alternatives . ' li Hatzivassiloglou s chapter , Do We Need Linguistics When We Have Statistics ? A Comparative Analysis of the Contributions of Linguistic Cues to a " Statistical Word Grouping System, represents an exemplary model of how such a careful exploration can be done. Like Daille (chapter 3 ) and others , Hatzivassiloglou adopts an approach in which linguistic knowledge is used to define the space of lexical co- occurrences, and then straightforward statistical methods are applied to the resulting co- occurrence frequencies . What distin guishes this work from most other efforts of this kind , however, is its attention to methodology : the variables of interest are carefully motivated and defined , a complete experimental design is used, and observed differences are evaluated in terms of statistical significance . Moreover , Hatzivassiloglou explicitly considers the cost of incorporating linguistic knowledge into his system, both in development and on -line performance . Since the most successful combinations of linguistic and statistical approach es still rely on relatively shallow methods, this is an underappreciated topic ,.for real applications , deciding whether deeper linguistic analysis is worthwhile will require not only a rigorous analysis of performance , asillus trated here, but also a careful consideration of whether the benefits of added linguistic sophistication balance out the costs.- Eds .

68

Chapter4

1 Introduction

es were among the fIrSt Historically, pure statistical, corpus-basedapproach onesthat wereappliedto naturallanguageprocessingproblemsin generaland lexical knowledgeacquisitionproblemsin particular. Suchefforts took place very early: in the 1950sand early 1960sa considerableamountof research work wasunderway addressingproblemssuchasmachinetranslationandlexicon and thesaurusconstructionwith purely statisticalmethods. However, the lack of sophisticatedstatisticalmodelsandpowerful hardwareled to ratherdisappointin results, and the statisticalapproachwas largely abandonedin the 1970sin favor of knowledge-based, artificial intelligence(AI ) approach es. Yet, pure knowledge-basedapproach es, which useknowledgecollectedby humanexpertsandenteredin the systemasanexternalsource,alsoseeminsufficient for providing an adequatesolutionto naturallanguageproblems. Such systemsareeffectivewhenthedomainandthevocabularyaretightly controlled, but fail to scale up in more general settingswhere knowledgeacquisition becomesa major bottleneck. Whenthis limitation of currentknowledge-based systemsbecameapparent, interestin statisticalmethodswas renewedin the mid- and late 1980's, and continuesunabateduntil now. This renaissanceof statisticalmethodswasparticularlyhelpedby recentsuccess esof such" knowledge -poor" methods in problems such as part-of-speechtagging [Church, 1988; Kupiec, 1992; Cutting et al., 1992] andspeechrecognition[Waibel and Lee, 1990] . Once more, however, systemsbasedon statisticalmethodsalonehavenot beentotally successfulin solvingmostof thenaturallanguageprocessingproblems . Consequently , a numberof researchershave turned to they addressed hand encoded combininglinguistic, knowledgewith statisticaltechniquesasa meansto improveoverall performance , sinceit is reasonableto expectthat the combinedapproachwill potentiallyoffer significantlybetterperformanceover either methodologyalone. The interactionof statisticaland linguistics-based componentsin a systemis thus a topic of considerablecurrentinterest. However , whenwe considersucha hybrid system, severalquestionsarise. Perhaps the most pressingonesare whetherthe linguistic knowledgeactuallyhelpsin , andif so, whetherthe improvementis worth the effort improvingperformance neededto implementthe linguistic modulesand incorporatethem in the system . In most casesanswersto thesequestions, if suppliedat all , are derived from intuitive beliefs and anecdotalevidence, rather than from a rigorous, quantitativecomparison.

Do We Need Linguistics When We Have Statistics?

This chaptersupplementstheseintuitive beliefswith actualevaluationdata, obtainedwhenseveralsymbolic, linguistics-basedmoduleswereintegratedin a statisticalsystem. As the basisfor our comparativeanalysis, we useda system we previously developedfor the separationof adjectivesinto semantic groups[Hatzivassiloglouand McKeown, 1993] . We identified severaldifferent types of shallow linguistic knowledgethat can be efficiently introduced into our system. We evaluatedthe systemwith andwithout eachsuchfeature, ' obtainingan estimateof eachfeatures positiveor negativecontributionto the overall performance . By matchingcaseswhereall systemparametersare the sameexceptfor onefeature, we assessthe statisticalsignificanceof the differences found. Also, a statisticalmodelof the system's performancein termsof the active featuresfor eachrun offers a view of the contributionsof features from a different angle, contrastingthe significanceof linguistic features(or othermodeledsystemparameters ) againstoneanother. Our analysisof the experimentalresultsshowedthat manyforms of linguistic knowledgemake a significant positive contributionto the performanceof the system. Otherstatisticalsystemsthat addressword classificationproblems do not emphasizethe useof linguistic knowledgeand do not deal with a specific word class [Brown et al., 1992], or do not exploit as much linguistic knowledgeas we do [Pereiraet al., 1992] . As a result, a coarserclassification is usuallyproduced.In contrast, by limiting the system's input to adjectives,we can take advantageof specific syntacticrelationshipsand additionalfiltering . Thesesourcesof linguistic proceduresthat applyonly to particularword classes in turn the extra for knowledgeprovide edge discriminating among the adjectivesat the semanticlevel. In what follows, we briefly review our adjectivegroupingsystem, anddiscuss how the lexical semanticknowledgeextractedby it canbe usedin a variety of natural languageprocessingapplications. We then present several different types of shallow linguistic knowledgethat can be, and have been, efficiently introducedinto this system. In section6 we give the resultsof our evaluationof the system's performanceon different combinationsof features (linguistic modules) and analyzetheir statistical significance. We also estimate the relative importanceof the linguistic modulesand we measurethe overall effect linguistic knowledgehasin the word groupingsystem. We then proceedto discussthe cost of incorporatinglinguistic knowledgein the statistical system, and concludeby presentingargumentsin favor of the relevance of theseresultsto statisticalapproachesfor other naturallanguageprocessing problems.

Chapter4 2

Overview of the Adjective Grouping System

2.1 Definitions Our adjectivegroupingsystem[Hatzivassiloglouand McKeown, 1993] starts with a set of adjectivesto be clusteredinto groups of semanticallyrelated words. In linguistics, thereis a long tradition of work associatedwith " semantic " and" " relatedness groupsof semanticallyrelatedwords. Trier [ 1934] proposed that the vocabularyof a naturallanguageis organizedin groupsthat he called lexical fields (Wort/elder), which representconceptualfields (Sinn' felder), the latter being setsof closely relatedconcepts. Trier s lexical fields " " closelycorrespondto the groupsof semanticallyrelatedwords that our system aimsto fmd. The work of Trier focusedmoreon the diachronicandcross, but a considerablenumberof linguists linguistic aspectof lexical semantics followed and extendedhis approach; see[Lehrer, 1974] for a comprehensive treatmentof thetheoryof lexical andsemanticfields. Unfortunately, thetheory is mostly basedon intuitive judgments; asLyons [ 1977, p. 277] remarks, Whatis lackingsofar . . . is a moreexplicitfonnulationof thecriteriawhichdefmea lexicalfield. . . Themajorityof lexicalfieldsarenotsoneatlystructured or asclearly asTrieroriginallysuggested . separated

Given the lack of a formal defmition of semanticgroups, we will use an informal, intuitive definition for semanticrelatedness , and treating semantic relatedness asanequivalencerelationin thevocabulary, we will thendefinethe semanticgroupsas the equivalenceclassesinducedby this relation. What we mean by " semanticallyrelated" is that words belonging to the samegroup shouldconsistentlyexpressa closenessin their meaning, for example, by being synonyms, antonyms, complementaryterms, hyponyms, specialcasesof the same superordinateconcept (co-hyponyms), or terms describing the same property. Informal criteria suchasthe abovehavebeenfrequentlyusedin linguistics . As in many caseswherean informal definition is used, resultsbased on this defmition are opento criticism, suchas the remarksby Lyons above, andthereis disagreement on whatexactlyis the correctanswer, given the same , thereis difficulty in interpretingthe results, and special input. Correspondingly careis neededduring evaluation. Nevertheless , humansare able to judge the quality of semanticgroupings, evenif they frequentlydisagreeandcannot fully externalizethe criteria they use. Furthermore,groupingsproducedindependent by severalhumanstendto agreeto a degreethat cannotbe expected chance , thus establishingthat the organizationof words into semantic by classesis not arbitraryor artificial.

DoWeNeedLin .2;uistic~ WhenWe HaveStatistics? 2.2 Algorithm and Implementation Our systemgenerallyoperateson a set of words from a particular syntactic class, using distributionalcriteria to measurethe semanticsimilarity between thesewords. In other words, the semanticrelatednessbetweenwordsX and Y is measuredon the basisof the similarity of the co-occurrencepatternsof these . The relevant words with words from other informative syntactic classes classesof wordsareselectedso that semanticconstraintsareexpectedto apply betweenthem andthe words from the original set that co-occur with them. In the versionof the systemusedin the experimentsdescribedin this chapter, we group adjectivesand we usenounsthat are modified by the adjectivesas this secondinformative syntacticclass. We are currently extendingthe systemto group nounson the basisof co-occurringadjectivesand verbsthat participate in appropriatesyntacticrelationshipswith thesenouns. The systemhasaccessto a text coipus, which hasbeenautomaticallytagged with part-of -speechinformation. All lexical semanticknowledgefor thegrouping taskis extractedfrom the corpus; no semanticinformationaboutthe adjectives or any other words is availableto the system. The systemoperatesby extractingmodified nounsfor eachadjective, and, optionally, pairs of adjectives thatwe canexpectto be semanticallyunrelatedon linguistic grounds.The latter are adjectivesthat either modify the samenoun in the samenounphrase (e.g., big red truck) or oneof themmodifiesthe other(e.g., light bluescarf) ; see , [Hatzivassiloglouand McKeown, 1993] and especially [Hatzivassiloglou . The estimateddistribution 1995a] for a detailedanalysisof this phenomenon asa vector, anda similarity of modifiednounsfor eachadjectiveis represented ' scoreis assignedto eachpossiblepair of adjectives.This is basedon Kendall s T, a nonparametric , robustestimatorof correlation[Kendall, 1938, 1975]. ' Kendall sT comparesthe two vectorsby repeatedlycomparingtwo pairsof . Formally, if (Xi, Y;) and (Xj ' Yfl are two their correspondingobservations for the of adjectivesX and Y that we are interestedin grouping pairs frequencies i and on the nouns j respectivel)' , we call thesepairsconcordantif Xi > Xj andYi > Yj or if Xi < Xj and Yi < Yr If Xi > Xj but Yi < Yj ' or if Xi < Xj and Yi > Yj ' the two pairs arediscordant. In general, if the distributionsof the two randomvariablesX and Y acrossthe various modified nounsare similar, we , and consequentlya small numberof expecta large numberof concordances sincethetotal numberof pairsof observationsis fixed for thetwo discordances indicate variables. This is justified by the fact that a largenumberof concordances " that whenoneof the variablestakesa " large valuethe other also takesa " " " " large value on the correspondingobservation; of course, large is a term that is interpretedin a relativemannerfor eachvariable.

Chapter4

Kendall' s Tis defmedasPc- Pd, wherePc andPd are the probabilitiesof observinga concordanceor discordancerespectively. It rangesfrom - 1 to + 1, with + 1 indicating completeconcordance , - 1 completediscordance , and 0 = i.e. no correlation between X and Y. T We use an unbiased estimator , ( Pc Pd) for T , which incorporatesa correctionfor ties, that is, pairs of observations whereXi = Xj or Yi = Yj [Kendall, 1975, p. 75] . The estimatoris also made asymmetricby ignoring observationsfor which the nounfrequencyis zerofor bothX and Y. For moredetailson the similarity measureandits advantages for our task, see[Hatzivassiloglou, 1995a]. Using the computedsimilarity scoresand, optionally, the establishedrelationship of non-relatedness , a nonhierarchical clustering method [Spath, 1985] assignsthe adjectivesto groupsin a way that maximizesthe withingroup similarity (and therefo~ also maximizesthe between-group dissimilarity .1 ). The systemis given the numberof groupsto form asan input parameter The clusteringalgorithm operatesin an iterative manner, startingfrom a random partitionof theadjectives.An objectivefunction is usedto scorethecurrent clustering. Eachadjectiveis consideredin turn and all possiblemovesof . The move that leadsto the that adjectiveto anothercluster are considered largestimprovementin the value of is executed, and the cycle continues throughthe setof wordsuntil no moreimprovementsto thevalueof arepossible . Note that in this way a word may be movedseveraltimesbeforeits fmal groupis detennined. This is a hill -climbing methodand thereforeis guaranteedto convergein fmite time, but it may leadto a local minimum of <1>, inferior to the global minimum that correspondsto the optimal solution. To alleviatethis problem, the partitioningalgorithmis calledrepeatedly2with different randomstartingpartitions andthe bestsolutionproducedfrom theserunsis kept. Figure4.1 showsan exampleclusteringproducedby our systemfor one of the adjectivesetsanalyzedin this chapter. 2. 3 Evaluation In many natural language processing applications , evaluation is performed either by using internal evaluation measures ( such as perplexity [ Brown et al., 1. Detennining this numberfrom the data is probably the hardestproblem in cluster , 1990] . However, a reasonably good analysisin general; see[KaufmanandRousseeuw valuefor this parametercanbe selectedfor our problemusingheuristicmethods. 2. In thecurrentimplementation , 50 timesfor eachvalueof thenumberof clustersparameter .

Do We NeedLinguisti C5WhenWe HaveStatistics ~ 13. communistleftist 14. astonishingmeagervigorous 15. catasttophicdisastrousharmful 16. dry exotic wet 17. chaoticturbulent 6. generousoub' ageousunreasonable 7. endlessprob' acted

18. confusingmisleading 19. dismalgloomy

8. plain 9. hostile unfriendly

20. dual multiple pleasant 21. fat slim

10. delicatefragile unstable 11. affluent impoverishedprosperous

22. affordableinexpensive 23. abruptgradualstunning

12. brilliant cleverenergeticsmartstupi~

24. flexible lenientrigid strict stringent

Figure 4.1

foundby thesystemusingall linguisticmodules . Exampleclustering 1992]) or by havinghumanjudgesscorethe system's output. However, thefIrSt approachproducesresultsthat dependon the adoptedmodel, while the second approachfrequently introducesbias and inflation of the scores, especially whenthe " correct" answeris not well defmed(asis the casewith mostnatural languageprocessingproblems). To addressthesedeficienciesof traditional evaluationapproach es, we employ model solutionsconstructedby humans ' independentlyof the systems proposedsolution. The humansreceivethe list of adjectivesthat are to be clustered, a descriptionof the domain, and general instructionsabout the task. To avoid introducing bias in the evaluation, the instructionsdo not include low-level detailssuchasthe numberof clustersor specifictestsfor decidingwhetherany two wordsshouldbe in the samegroup. In orderto comparetwo partitionsof the samesetof words, we converteach " " partition to a list of yes/no decisionsasfollows: We view eachpossiblepair of the words in the set as a decisionpoint, with a " yes" answerin the current " " partition if the two adjectivesareplacedin the samegroup anda no answer otherwise.Then, we canapplythestandardinformationretrievalmeasuresprecision and recall [ Frakesand Baeza-Yates, 1992] to measurehow close any two suchlists of decisionsare, or moreprecisely, how similar onesuchlist is to anotherwhich is consideredasthereferencemodel. Consideringtheanswersin the referencelist as the correctones, precision is defmedas the percentageof correct" yes" answersreportedin the list that is evaluatedover the total number of " yes" answersin that list. Similarly, recall is defmedasthe percentage

Chapter4

of correct" yes" answersin the testedlist over the total numberof (by definition " " , correct) yes answersin the referencelist. The two evaluationmeasuresdefinedaboveratecomplementaryaspectsof the correctnessof the evaluatedpartition. In order to perform comparisons betweendifferent variantsof the grouping system, correspondingto the use of different combinationsof linguistic modules, we needto convert this pair of scoresto a single number. For this purposewe usethe F-measurescore [ Van Rijsbergen, 1979], which producesa number betweenprecision and recall that is larger when the two measuresareclosetogether, and thusfavors partitionsthat arebalancedin the two typesof errors(falsepositivesandfalse negatives). Placing equal weight on precision and recall, the F -measureis definedas

Up to this point, we haveconsideredcomparisonsof onepartition of words againstanothersuchpartition. However, given the considerabledisagreement that existsbetweengroupingsof the sameset of wordsproducedby different humans, we decidedto incorporatemultiple m~ ls in the evaluation. Previously " " , multiple modelshavebeenusedindirectly to constructa single best or most representativemodel, which is then usedin die evaluation[Gale et al., and Litman, 1993]. Although this approachreducesthe 1992a; Passonneau problemscausedby relying on a singlemodel, it doesnot allow thedifferences betweenthe modelsto be reflectedin the evaluationscores.Consequently , we that uses models an evaluation method , simultaneously multiple developed in the of between tlte models reflects the produced directly degree disagreement scores,andautomaticallyweighsthe importanceof eachdecisionpoint according to tlte homogeneityof the answersfor it in the multiple models. We have extendedthe informationretrievalmeasuresof precision, recall, fallout, andFmeasurefor this purpose;themathematicalformulationof thegeneralizedmeasures is givenin [HatzivassiloglouandMcKeown, 1993] and[Hatzivassiloglou , 1995a]. In the experimentsreportedin this chapter, we employeight or nine humanconstructedmodelsfor eachadjectiveset. We baseour comparisonson and report the generalizedF~measurescores.In addition, sincethe correctnumber of groupingsis somethingthat the systemcannotyet determine(and, incidentally , somethingthat humanevaluatorsdisagreeabout), we run the systemfor the five casesin the range- 2 to + 2 aroundthe averagenumber of clusters employedby the humansand averagethe results. This smoothingoperation

Do We NeedLinguisticsWhenWe HaveStatistics?

preventsan accidentalhigh or low scorebeingreportedwhena small variation in the numberof clustersproducesvery different scores. It shouldbe notedherethat the scoresreportedshouldnot be interpretedas linearpercentages . The problemof interpretingthe scoresis exacerbated in our contextbecauseof the structuralconstraintsimposedby the clusteringand the presenceof multiple models. Even the bestclusteringthat could be produced would not receivea scoreof 100, becauseof the disagreementamonghumans on what is the correctanswer; applying the sameevaluationmethodto score eachmodelconstructedby humansfor thethreeadjectivesetsusedin this comparative studyagainstthe otherhuman-constructedmodelsleadsto an average scoreof 60.44 for the humanevaluators.To clarify the meaningof the scores, we accompanythem with lower and upper boundsfor eachadjectiveset we examine. Theseboundsare obtained.by the performanceof a systemthat creates randomgroupings(averagedover manyruns) andby the averagescoreof the human-producedpartitions when evaluatedagainstthe other human-produced modelsrespectively. 3

Motivation

3.1 Applications The outputof the word groupingsystemthat we describedin the previoussection is usedas the basisfor the further processingof the retrievedgroups: the classificationof groups into scalar and nonscalarones, the identification of synonymsandantonymswithin eachsemanticgroup, the labelingof wordsas positive or negativewithin a scale, and the orderingof scalartermsaccording to semanticstrength. In this way, thegroupingsystemis usedasthefirst part of a larger systemfor corpus-basedcomputationallexicography, which in turn producesinformationusefulfor a variety of naturallanguageprocessingapplications . We briefly list below someof theseapplications: . The organizationof words into semanticgroupscan be exploitedin statistical languagemodeling, by pooling togetherthe estimatesfor the variouswords in eachgroup [Sadier, 1989; Hindle, 1990; Brown et al., 1992]. This approach of the data, especiallyfor low-frequency significantly reducesthe sparseness words. . A study of medical casehistories and reports has shown that frequently physiciansusemultiple modifiersfor the sametermthat areincompatible(e.g., they are synonyms,contradicteachother, or onerepresentsa specializedcase of the other) [Moore, 1993]. Given the technicalcharacterof thesewords, it is

Chapter4

, evento identify quite hard for non-specialiststo edit theseincorrectexpressions suchproblematiccases.But the outputof the word groupingsystem, which identifiessemanticallyrelatedwords, canbe usedto flag occurrencesof incompatible modifiers. . Knowledgeof the synonymsand antonymsof particularwordscan be used during both understandingand generationof text. Such knowledgecan help with the handling of unknown words during understandingand increasethe paraphrasingpowerof a generationsystem. . Knowledgeof semanticpolarity (positive or negativestatuswith respectto a norm) can be combined with corpus-based collocation extraction tools [Smadja, 1993] to automaticallyproduceentriesfor the lexicalfunctions used in Meaning-Text Theoryfor text generation[Mel ' cuk andPertsov, 1987]. For example, if the collocationextractiontool identifiesthe phraseheartyeater as a recurrentone, thenknowing that heartyis a positiveterm enablesthe assignment of hearty to the lexical function MAGN(standingfor magnify), that is, MAGN (eater) = hearty. . Therelativesemanticstrengthof scalaradjectivesdirectly correlateswith the , the relative argumentativeforce of the adjectivesin the text. Consequently semanticstrengthinformationcan be usedin languageunderstandingto properly interpretthemeaningof scalarwordsandin generationto selectthe appropriate word to lexicalize a semanticconceptwith the desiredargumentative force [Elhadad, 1991] . . Scalar words obey pragmaticconstraints, for example, scalar implicature [Levinson, 1983; Hirshberg, 1985] . If the position of the word on the scaleis known, the systemcan draw the implied pragmatic inferencesduring text analysis, or usethem for appropriatelexical choice decisionsduring generation . In particular, such information can be usedfor the proper analysisand . For example, not hot usuallymeanswarm, generationof negativeexpressions but not warm usuallymeanscold. 3.2 The Needfor Automatic Methods for Word Grouping In recentyears, the importanceof lexical semanticknowledgefor language processinghasbecomerecognized.Someof the latestdictionariesdesignedfor humanuseincludeexplicit lexical semanticlinks; for example, the COB~ D dictionary [Sinclair, 1987] explicitly lists synonyms,antonyms,andsuperordinates for manyword entries. WordNet [Miller et al., 1990] is perhapsthe bestknown example of a large lexical databasecompiled by lexicographers specificallyfor computationalapplications,andit hasbeenusedin severalnatural languagesystems(e.g., [Resnik, 1993; Resnik and Hearst, 1993; Knight

Do We NeedLinguisticsWhenWe HaveStatistics?

and Luk, 1994; Basili et al., 1994]). Yet, WordNet and the machine-readable versionsof dictionariesand theusaristill suffer from a numberof disadvantages when comparedwith the alternative of an automatic, corpus-based approach: . All entriesmust be encoded hand, which by representssignificant manual effort. . Changesto lexical entries may necessitatethe careful examinationand potential revision of other relatedentriesto maintain the consistencyof the database . . Many typesof lexical semantic knowledgearenot presentin currentdictionaries or in WordNet. Most dictionariesemphasizethe syntacticfeaturesof words, suchas part of speech,number, and form of complement.Even when dictionarydesignerstry to focuson the semanticcomponentof lexical knowledge , the results have not yet been fully satisfactory. For example, neither COBUll. .O nor WordNet includesinformationaboutscalarsemantic strength. . The lexical information is not specific to any domain. Rather, the entries attemptto capturewhat appliesto the languageat large, or representspecialized sensesin a disjunctive manner. Note that semanticlexical knowledgeis most sensitiveto domainchanges.Unlike syntacticconstraints, semanticfeatures tend to change as the word is used in a different way in different domains. For example, our word grouping systemidentifiedpreferred as the word mostcloselysemanticallyrelatedto common,. this association may seem peculiarat fIrst glance, but is indeeda correctonefor thedomainof stockmarket reports and financial information from which the training material was collected. . Time-varying information, that is, the currencyof words, compounds , and collocations, is not adjustedautomatically. . The validity of any particular entry dependson the assumptionsmadeby the particularlexicographer (s) who compiledthat entry. In contrast, an automatic systemcan be more thorough and impartial, since it basesits decisionson actualexamplesdrawnfrom the corpus. An automaticcorpus-basedsystemfor lexical knowledgeextractionsuchas our word grouping systemoffsets thesedisadvantagesof static human-constructed knowledgebasesby automaticallyadaptingto the domain sublanguage . Its disadvantageis that while it offers potentially higher recall, it is generallylessprecisethan knowledgebasescarefully constructedby human . This disadvantagecan be alleviatedif the output of the automatic lexicographers systemis modified by humanexpertsin a post-editing phase.

Chapter4

4 Linguistic Featuresand Alternative Values for Them We haveidentified severalsourcesof symbolic, linguistic knowledgethat can be incorporatedin the word groupingsystem, augmentingthe basicstatistical component. Each suchsourcerepresentsa parameterof the system, that is, a featurethat canbe presentor absentor moregenerallytakea valuefrom a predefined set. In this sectionwe presentfirst oneof theseparametersthatcantake severalvalues, namelythe methodof extractingdatafrom the corpus, andthen severalotherbinary-valuedfeatures.

4.1 Extracting Data from the Corpus When the word-clusteringsystempartitions adjectivesin groupsof semantically relatedones, it determinesthedistributionof related(modified) nounsfor eachadjectiveand eventuallythe similarity betweenadjectivesfrom pairs of the form (adjective, modified noun) that have beenobservedin the corpus. Direct information about semanticallyunrelatedadjectives(in the form of appropriateadjective-adjectivepairs) can also be collectedfrom the corpus. Therefore, a first parameterof the systemand a possibledimensionfor comparisons is the methodemployedto identify suchpairsin free text. Thereareseveralalternativemodelsfor this taskof datacollection, with different degreesof linguistic sophistication.A fIrSt model is to useno linguistic : we collect for eachadjectiveof interestall words that fall knowledgeat al13 within a window of some predeterminedsize. Naturally, no negativedata (adjective-adjectivepairs) can be collected with this method. However, the methodcan be implementedeasily and doesnot require the identification of any linguistic constraintsso it is completely general. It has been used for diverseproblemssuchasmachinetranslationandsensedisambiguation[Gale et al., 1992b; Schutte, 1992] . A secondmodelis to restrictthe wordscollectedto the samesentenceasthe adjective of interest and to the word class(es) that we expect on linguistic groundsto berelevantto adjectives.For our application, we collect all nounsin the vicinity of an adjectivewithout leaving the current sentence . We assume that thesenounshave somerelationshipwith the adjectiveand that semantically different adjectiveswill exhibit different collectionsof suchnouns. This model requires only part-of-speechinformation (to identify nouns) and a methodof detectingsentenceboundaries . It usesa window of fixed lengthto 3. Aside from the conceptof a word, which is usually approximatedby defining any string of charactersseparatedby white spaceor punctuationmarksas a word.

Do We NeedLinguisticsWhenWe HaveStatistics?

defmethe neighborhoodof eachadjective. Again, negativeknowledgesuchas pairs of semanticallyunrelatedadjectivescannotbe collectedwith this model. Nevertheless , it hasalsobeenwidely used, for example, for collocationextraction [Smadja, 1993] andsensedisambiguation[Liddy andPaik, 1992] . Sincewe are interestedin nounsmodified by adjectives, a third modelis to collect a nounimmediatelyfollowing an adjective, assumingthat this impliesa modificationrelationship. Pairsof consecutiveadjectives, which arenecessar unrelated can also be collected. ily semantically , Up to this point we have successivelyrestrictedthe collectedpairs on linguistic grounds, sothat lessbut moreaccuratedataarecollected. For the fourth model, we extendthe simplerule given above, using linguistic informationto catch more valid pairs without sacrificing accuracy. We employ a pattern matcherthat retrievesany sequenceof oneor moreadjectivesfollowed by any sequenceof zero or more nouns. These sequencesare then analyzedwith heuristicsbasedon linguisticsto obtainpairs. The regularexpressionandpatternmatchingrulesof the previousmodelcan be extendedfurther, forming a grammarfor the constructsof interest. This approachcandetectmorepairs, andat the sametime addressknown problematic casesnot detectedby the previousmodels. We implementedthe abovefive dataextractionmodels, using typical window sizesfor the first two methods(50 and 5 on each side of the window respectively) which have beenfound appropriatefor other problemsbefore. Unfortunately, thefirst modelprovedto beexcessivelydemandingin resources 4 for our comparativeexperiments , so we droppedit from further consideration andusethe secondmodelasthe baselineof minimal linguistic knowledge. For the fifth model, we developeda fmite-stategrammarfor nounphraseswhich is ableto handleboth predicativeandattributivemodificationof nouns, conjunctions of adjectives,adverbialmodificationof adjectives,quantifiers, andapposition of adjectivesto nounsor otheradjectives.5 A detaileddescriptionof this grammarandits implementationcanbe found in [Hatzivassiloglou, 1995b]. 4.2 Other Linguistic Features In additionto the dataextractionmethod, we identifiedthreeotherareaswhere linguistic knowledgecan be introducedin our system. First, we can employ 4. For example, 12,287,320word pairsin a 151MB file wereextractedfor the21 adjectives in our smallesttest set. Other researchers havealso reportedsimilar problemsof excessiveresourcedemandswith this " collect all neighbors" model[Galeet al., 1992b]. 5. For efficiency reasonswe did not considera morepowerful formalism.

Chapter4

morphologyto convert plural nounsto the correspondingsingular ones and adjectivesin comparativeor superlativedegreeto their baseform. This conversion combinescountsof similar pairs, thus raising the expectedand estimated frequenciesof eachpair in any statisticalmodel. Another potentialapplicationof symbolic knowledgeis the useof a spellchecking procedureto eliminate typographical errors from the corpus. We implementedthis componentusing the UNIX spell program and associated . Unfortunately, sincea word list, with extensionsfor hyphenatedcompounds fixed anddomain independentword list is usedfor this process,somevalid but overspecialized wordsmay be discardedtoo. Finally, we have identified severalpotential sourcesof additional knowledge that can be extractedfrom the corpus(e.g., conjunctionsof adjectives) and can supplementthe primary similarity relationships. In this comparison studywe implementedandconsideredthe significanceof one of theseknowledge sources, namely the negativeexamplesoffered by adjective-adjective where the two adjectiveshavebeenobservedin a syntacticrelationship pairs . that stronglyindicatessemanticunrelatedness 5

The Comparison Experiments

In the previoussectionwe identifiedfourparametersof the system, the effects of which we wantto analyze. But in additionto theseparameters , which canbe variables values several other varied and have , predetenninedpossible directly canaffect the perfonnanceof the system. First, the perfonnanceof the systemdependsnaturally on the adjectiveset that is to be clustered. Presumably , variationsin the adjectivesetcanbe modeled as the sizeof the set, the numberof semantic several such , by parameters relatednessamongits members,plus in it and the of semantic , strength groups severalparametersdescribingthe propertiesof the adjectivesin the set in isolation , suchasfrequency, specificity, etc. A secondvariablethat affectsthe clusteringis the corpusthat is usedasthe main knowledgesource, throughthe observedco-occurrencepatterns. Again theeffectsof different corporacanbe separatedinto severalfactors, for example , the sizeof the corpus, its generality, the genreof the texts, etc. Sincein theseexperimentswe are interestedin quantifyingthe effect of the linguistic knowledgein the system, or morepreciselyof the linguistic knowledge that we can explicitly control through the four parametersdiscussed above, we did not attemptto model in detail the various factors enteringthe systemas a result of the choiceof adjectiveset and corpus. However, we are

Do We NeedLinguisticsWhenWe HaveStatistics?

interestedin measuringthe effectsof the linguistic parametersin a wide range of contexts. Therefore, we included in our experimentmodel two additional , representingthe corpusandthe adjectivesetused. parameters We usedthe 1987Wall StreetJournal articlesfrom the ACL -DCI (Association for ComputationalLinguistics-Data Collection Initiative) as our corpus. We selectedfour subcorporato study the relationshipof corpussize with linguistic featureeffects: subcorporaof 330,000 words, 1 million words, 7 million words, and21 million words(the lastconsistingof the entire 1987corpus) were selectedasrepresentative . Eachselectedsubcorpuscontainedthe selectedsubcorpora of smaller sizes, and was constructedby samplingacrossthe whole rangeof theentirecoIpus at regularintervals. Sincewe usesubsetsof the same corpus, we areessentiallymodelingthe corpussizeparameteronly. For eachcorpus, we analyzedthr~ different setsof adjectives, listed in figures 4.2, 4.3, and4.4. The first of theseadjectivetest setswas selectedfrom a similar corpus, contains21 words of varying frequenciesthat all associate strongly with a particular noun (problem), and was analyzedin [Hatzivassiloglou and McKeown, 1993]. The secondset (43 adjectives) was selected with the constraintthat it containhigh-frequencyadjectives(more than 1000 occurrencesin the 21-million -word corpus). The third set(62 adjectives) satisfies the oppositeconstraint, containingadjectivesof relatively low frequency (between50 and 250). Figure 4.1 on page73 showsa typical groupingfound by our systemfor the third setof adjectives, whenthe entirecorpusandalllin guistic moduleswereused. Thesethreesetsof adjectivesrepresentvariouscharacteristics of theadjective setsthat the systemmay be calledon to cluster. First, they explicitly represent increasingsizesof thegroupingproblem. The secondandthird setsalsocontrast the independentfrequenciesof their memberadjectives.Furthermore , the less of the third set tend to be more than the more frequent frequentadjectives specific ones. The humanevaluatorsreportedthat the task of classificationwas antib' Ust

international

big economic

legal little

fmancial foreign

major mechanical

global

new

old political potential real serious severe

Figure 4.2 Test set 1: Adjectivesstronglyassociatedwith the word problem.

staggering technical unexpected

Chapter4 annual

hard

big chief

high

negative net new

commercial

important initial

current

international

old

daily different

likely local

past

difficult

low

easy fmal

military modest

possible pre-tax

future

national

next

positive

previous

public quarterly recent regional senior significant similar small strong weak

private

Figure 4.3 Test set2: High-frequencyadjectives. abrupt affluent affordable

dismal

hostile

slim

dry dual

impoverished inexpensive insufficient leftist lenient

smart

astonishing brilliant

dumb

capitalist

energetic exotic

catastrophic chaotic

endless

fat

clean

fatal

clever

flexible

communist

fragile

confusing

generous

deadly delicate

gloomy

dirty disastrous

Figure 4.4

gradual hanDful hazardous

meager misleading multiple outrageous plain pleasant prosperous protracted rigid scant

Test set 3: Low - to medium -frequency adjectives .

socialist strict stringent stunning stupid toxic turbulent unfriendly unreasonable unstable vigorous wet

Do We NeedLinguisticsWhenWe HaveStatistics?

easierfor the third set, and their modelsexhibitedabout the samedegreeof agreementfor the secondand third sets, althoughthe third set is significantly larger. " " " " By including the parameters corpussize and adjectiveset, we have six . Any remainingfactorsaffecting parametersthat we canvary in the experiments the performanceof the systemaremodeledasrandomnoise,6 so statistical methodsare usedto evaluatethe effects of the selectedparameters . The six chosenparametersarecompletelyorthogonal, with the exceptionthat parameter " " " " negativeknowledge must have the value not used when parameter " extractionmodel" has " " the value nounsin vicinity . In order to avoid introducing imbalancein the experiment, we constructeda complete designed experiment [Hicks, 1982] for all their (4 X 2 - 1) X 2 X 2 X 4 X 3 = 336 valid combinations! 6

Experimental Results

6.1

Average Et Tectof Each Linguistic Parameter Presenting the scores obtained in each of the 336 individual experiments performed , which correspond to all valid combinations of the six modeled parameters , is both too demanding in spaceand not especially illuminating . Instead, we present several summary measures. We measured the effect of each particular setting of each linguistic parameter of section 4 by averaging the scores obtained in all experiments where that particular parameter had that particular value. In this way , table 4.1 summarizes the differences in the performance of the system caused by each parameter. Because of the complete design of the experiment , each value in table 4.1 is obtained in runs that are identical to the runs used for estimating the other values of the same parameter except for the difference in the parameter itselfS Table 4.1 shows that there is indeed improvement with the introduction of any of the proposed linguistic features, or with the use of a linguistically more sophisticated extraction model. To assessthe statistical significance of these differences , we compared each run for a particular value of a parameter with 6. Includingsomelimited in extentbut ttuly randomeffectsfrom our nondetenninistic clusteringalgorithm. 7. Recallthat a designedexperimentis completewhenat leastone trial, or run, is performed for everyvalid combinationof the modeledpredictors. 8. The slight asymmetryin parameters" extractionmodel" and " negativeknowledge" is accountedfor by leavingout non-matchingruns.

Chapter4 Table 4.1 AverageF-measurescoresfor eachvalueof eachlinguistic feature Parameter

Value

Averagescore

Extract inn model

Parsing Patternmatching Observedpairs Nounsin vicinity Yes No

30.29 28.88 27.87 22.36 28.60 27.53 28.12 28.00 29.40 28.63

Morphology Spell-checking

Yes No

Useof negativeknowledge

Yes No

thecorrespondingidentical(exceptfor thatparameter ) run for a differentvalue of theparameter . Eachpair of valuesfor a parameterproducesin this way a set of pairedobservations . On eachof thesesets, we perfonneda sign test [Gibbons and Chakraborti, 1992] of the null hypothesisthat thereis no real difference in the system's perfonnancebetweenthe two values, that is, that any observeddifferenceis dueto chance.We countedthe numberof timesthat the fIrStof thetwo comparedvaluesled to superiorperfonnancerelativeto the second , distributingties equallybetweenthe two casesasis the standardpractice in classifierinductionandevaluation. Underthe null hypothesis,thenumberof timesthat the fIrStvalueperfonnsbetterfollows the binomial distributionwith parameterp = 0.5. Table4.2 givestheresultsof thesetestsalongwith theprobabilities that the same or more extreme results would be encounteredby chance.We canseefrom the tablethat all typesof linguistic knowledgeexcept spell-checking have a beneficial effect that is statistically significant at, or below, the 0.1% level. 6.2 Comparison Among Linguistic Features In orderto measuredie significanceof die conbibutionof eachlinguisticfeature relative to die oilier linguistic features , we fitted a linear regressionmodel [Draperand Smidt, 1981] to die data. We usedie six parametersof die experiments asdie predictors,anddie F-measurescoreof die corresponding clustering9 9. Averagedoverfive adjacentvaluesof thenumberof clustersparameter , asexplained in section2.3.

Do We NeedLinguisticsWhenWe HaveStatistics?

Table4.2 Statistical of thedifference in perfonnance offeredby eachlinguisticfeature analysis

asthe responsevariable. In sucha modelthe responseR is assumedto bea linearfunction (weightedsum) of the predictorsVi. that is.

n R = /30+ L .B;V; =

; 1

(1)

where V; is the ;-th predictor and .8; is its correspondingweight. Table 4.3 showsthe weightsfound by the fitting processfor the experimentaldatacollected for all valid combinationsof the six parametersthat we model. These weightsindicateby their absolutemagnitudeandsignhow importanteachpredictor is and whetherit contributespositively or negativelyto the final result. Numericalvaluessuchasthe corpussizeenterequation( 1) directly aspredictors, so table 4.3 indicatesthat eachadditionalmillion words of ttaining text

Chapter4 Table 4.3 Fitted coefficientsfor the linear regressionmodel that contrasts the effects of various parametersin overall systemperformance Variable Intercept Corpussize(in millions of words) Extractionmethod(pairsvs. nounsin vicinity ) Exttactionmethod(sequences vs. nounsin vicinity) Extractionmethod(parservs. nounsin vicinity) Morphology Spell- checking Adjective set(2 vs. 1) Adjective set(3 vs. I ) Useof negativeknowledge

Weight

18.7997 0.9417 5.1307 6.1418 7.5423 0.5371 0.0589 2.5996 - 11.4882 0.3838

increasesthe performanceof the systemby 0.9417on average . For binary features , theweightsin table4.3 indicatethe increasein the system's performance when the featureis present, so the introductionof morphologyimprovesthe ' systems performanceby 0.5371 on average.The different possiblevaluesof thecategoricalvariables" adjectiveset" and" extractionmodel" areencodedas contrastswith a basecase; the weightsassociatedwith eachsuchvalue show the changein scorefor the indicatedvalue in contrastto the basecase(adjective set I and the minimal linguistic knowledgerepresentedby extraction model " nounsin vicinity ," respectively). For example, using the fmite-state " " parserinsteadof the nounsin vicinity modelimprovesthescoreby 7.5423on the score , while going from adjectiveset2 to adjectiveset3 decreases average = 2.5996 11 .4882 14.0878 on . the ( ) by averageFinally intercept.8ogives a baselineperformanceof a minimal systemthat usesthe basecasefor each ; the effectsof corpussizeareto be addedto this system. parameter From table 4.3 we can seethat the dataextractionmodel has a significant effect on the quality of the producedclustering, andamongthe linguistic parameters is the mostimportantone. Increasingthe sizeof the corpusalsosignificantly increasesthe score. The adjectiveset that is clusteredalso hasa major influenceon the score, with rareradjectivesleadingto worseclusterings.Note, however, thattheseareaverageeffects, takenover a wide rangeof differentsetringsfor the system. In particular, while the systemproducesbadpartitionsfor

Do We NeedLinguisticsWhenWe HaveStatistics?

adjectiveset 3 when the corpusis small, when the largestcorpus(21 million words) is usedthe partitionsproducedfor test set3 areequalin quality or better thanthepartitionsproducedfor theothertwo setswith the samecorpus. The two linguistic features" morphology" and" negativeknowledge" havelesspronounced althoughstill significanteffects, while spell-checkingoffers minimal improvementthat probably does not justify the effort of implementingthe moduleandthe costof activatingit at run-time. 6.3 Overall Et Tectof Linguistic Knowledge Up to this point we havedescribedaveragesof scoresor of scoredifferences, takenover manycombinationsof featuresthat areorthogonalto the one studLed. Theseaveragesare good for establishingthe existenceof a performance differencecausedby the different v~ ues of eachfeature, acrossall possible combinationsof theotherfeatures.Theyarenot, however, representative of the performanceof the systemin a particular settingofparameters, nor are they suitablefor describingthe differencebetweenfeaturesquantitatively, since ' they are averagestakenover widely differing settingsof the systems parameters . In particular, the inclusionof very smallcorporadrivesthe averagescores down, aswe haveconfirmedby computingaveragesseparatelyfor eachvalue of the corpussizeparameter ."To give a feeling of how importantthe introduction of linguistic knowledgeis quantitatively, we comparein table 4.4 the

Randompartitions

linguistic

Adjective set 1

Adjective set2

Adjective set3

9.66(17.90%) 24.51(45.41%)

6.21(9.66%) 38.51(59.92%)

3.80(6.03%) 33.21(52.66%)

/( 39.06(72.360

44.73(69.60%)

46.17(73.20%)

53.98

64.27

63.07

components active

All linguistic components active

Humans

Two versionsof the system(with all or none of the linguistic modulesactive) are contrastedwith the performanceof a randomclassifier and that of the humans. The scoreswereobtainedon the 21-million-word corpus, usinga smoothingwindow of three adjacentvaluesof thenumberof clustersparametercenteredat theaveragevaluefor that parameterin the human-preparedmodels. We also showthe percentageof the scoreof the humansthat is attainedby the randomclassifierandeachversionof the system.

Chapter4

resultsobtainedwith the full corpusof 21 million words for the two casesof having all or none of the linguistic componentsactive. The scoresobtained by a randomsystemthat producespartitions of the adjectiveswith no knowledge exceptthe numberof groupsare included asa lower bound. Theseestimates are obtained after averaging the scores of 20,000 such random partitions for eachadjective set. The averagescoresthat eachhumanmodel receiveswhencomparedwith all otherhumanmodelsarealso included, asan estimateof the maximum score that can be achievedby the system. That maximum dependson the disagreementbetweenmodels for eachadjective set. For thesemeasurementswe use a smaller smoothingwindow of size 3 insteadof 5, which is fairer to the systemwhen its performanceis compared with the humans. We also give in figure 4.5 the grouping producedby the systemfor adjectiveset 3 using the entire 21-million -word corpusbut without any of the linguistic modules active. This partition is to be contrasted with the one given in figure 4.1 on page 73 which was producedfrom the samecorpusand with the samenumberof clusters, but with all the linguistic modulesactive. 1. catastrophichannful 2. dry wet 3. lenientrigid strict stringent 4. communistleftist 5. clever 6 . abrupt chaotic disasttous gradual turbulent vigorous

7. affluent affordableinexpensive prosperous 8. outrageous

13. brilliant energetic 14. dual multiple stupid 15. hazardoustoxic unreasonable unstable 16. plain 17. confusing 18. flexible hostileprob' acted unfriendly 19. endless

11. generousinsufficient meager scantslim

20. cleandirty impoverished 21. deadlyfatal 22. astonishingmisleading stunning 23. dumbfat smart

12. delicatefragile

24. exotic

9. capitalistsocialist 10. dismalgloomy pleasant

Figure 4.5 Partitionwith 24 clustersproducedby the systemfor the adjectivetestset3 of figure 4.4 usingthe entire 21-milIion -word corpusandno linguistic modules.

? DoWeNeedLinguisticsWhenWeHaveStatistics 7 Cost of Incorporating the Linguistic Knowledge in the System The cost of incorporatingthe linguistics-basedmodulesin the systemis not prohibitive. The effort neededto implement all the linguistic moduleswas about5 person-months, in contrastwith 7 person-monthsneededto developthe basic statisticalsystem. Most of this time was spentin designingand implementing the fmite-stategrammarthat is usedfor extractingadjective-nounand adjective-adjectivepairs [Hatzivassiloglou, 1995b]. Furthermore, the run-time overheadcausedby the linguistic modules is not significant. Each linguistic module takes from 1 to 7 minutes on a Sun SparcStation 10 to processa million items (words or pairs of words, as appropriate for the module), and all except the negative knowledge module needprocessa corpusonly once, reusing the sameinformation for different probleminstances(word sets). This shouldbe comparedto the approximately 15 minutes needed by the statistical component for grouping about 40 adjectives.

8 Generalizingto Other Applications In section6 we showedthat the inttoduction of linguistic knowledgein the word groupingsystemresultsin a performancedifferencethat is not only statistically observablebut also quantitatively significant (cf. table 4.4). We believethat thesepositive resultsshouldalso apply to other corpus-basednatural languageprocessingsystemsthat employ statisticalmethods. essharethe samebasicmethodologywith our system Many statisticalapproach : a setof words is preselected , relatedwords areidentified in a corpus, the words and of of pairsof relatedwordsareestimated,and a statistical frequencies model is usedto makepredictionsfor the original words. Acrossapplications , thereare differencesin what words are selected,how relatedwords are defmed, andwhat kinds of predictionsaremade. Nevertheless , the basiccomponents in the . For the same adjectivegroupingapplicationthe example, stay original words are the adjectives and the predictions are their groups; in machinettanslation, the predictionsare the ttanslationsof the words in the sourcelanguagetext; in sensedisambiguation , the predictionsare the senses in of interest words of to the ; part speechtaggingor in classification, assigned the predictionsare the tagsor classesassignedto eachword. Becauseof this underlyingsimilarity, the comparativeanalysispresentedin this chapteris relevant to all theseproblems.

Chapter4

For a concreteexample, considerthe caseof collocationextractionthat has beenaddressedwith statisticalmethodsin the past. Smadja[ 1993] describesa " " systemthat initially usesthe nounsin vicinity extractionmodelto collectco occurrenceinformation about words, and then identifies collocationson the basisof distributionalcriteria. A later componentfilters the retrievedcollocations , removing the oneswhere the participatingwords are not usedconsistently in thesamesyntacticrelationship.This post-processingstagedoublesthe precisionof the system. We believethat using from the start a more sophisticated extractionmodelto collect thesepairsof relatedwordswill havesimilar , such as a morphologymodule positive effects. Other linguistic components that combinesfrequencycounts, shouldalso improvethe performanceof that system. In this way, we canbenefitfrom linguistic knowledgewithout having to usea separatefiltering processafter expendingthe effort to collect the collocation . Similarly, the sensedisambiguationproblem is' typically attackedby comparing the distributionof the neighborsof a word s occurrenceto prototypical ' distributionsassociatedwith each of the word s senses[Gale et al., 1992b; SchUtte, 1992] . Usually, no explicit linguistic knowledgeis usedin defining theseneighbors, which are taken as all words appearingwithin a window of .10Many wordsunrelated fIXedwidth centeredat theword beingdisambiguated to the word of interestarecollectedin this way. In contrast, identifying appropriate word classesthat can be expectedon linguistic groundsto convey significant information aboutthe original word shouldincreasethe performance of the disambiguationsystem. Suchclassesmight be modifiednounsfor adjectives , nounsin a subjector object position for verbs, etc. As we have shown in section6, less but more accurateinformation increasesthe quality of the results. An interestingtopic is theidentificationof parallelsof the linguistic modules thathavebeendesignedwith thepresentsystemin mind for theseapplications, at leastfor thosemoduleswhich, unlike morphology, arenot ubiquitous. Negative knowledge, for example, improvesthe performanceof our system, suppleme the positiveinformationprovidedby adjective-nounpairs. It could be useful for other systemsas well if an appropriateapplication-dependent methodof extractingsuchinformationis identified. , haveusedlimitedlinguisticknowledgein selecting 10. Althoughsomeresearchers and 1991 Hearst for see , ] these , [ and ; , example neighbors , processing classifying , 1994 ]. [Yarowsky

Do We NeedLinguisticsWhenWe HaveStatistics? 9

Conclusions and Future Work

We haveshownthat all linguistic featuresconsideredin this studyhad a positive contributionto the perfonnanceof the system. Exceptfor spell-checking, all thesecontributionswere both statistically significant and large enoughto makea differencein practicalsituations. The costof incorporatingthe linguistics -basedmodulesin the systemis not prohibitive, both in tenDSof development time and in tenDsof actualrun-time overhead.Furthennore, the results canbeexpectedto generalizeto a wide varietyof corpus-basedsystemsfor different applications. We shouldnote herethat in our comparativeexperimentswe havefocused on analyzingthe benefitsof symbolicknowledgethat is readily availableand canbe efficiently incorporatedinto the system. We haveavoidedusinglexical semanticknowledgebecauseit is not generallyavailableand becauseits use would defeatthe very purposeof the word groupingsystem. However, on the basisof the measurableperfonnancedifferenceofferedby the shallowlinguistic knowledgewe studied, it is reasonableto conjecturethat deeperlinguistic knowledge, if it becomesreadily accessible , would probablyincreasethe perfonnanceof a hybrid systemevenmore. In the future, we plan to extendthe resultsdiscussedin this chapterwith an of theeffectsof eachparameteron the valuesof the analysisof the dependence other parameters . We are currently stratifying the experimentaldataobtained to studytrendsin the magnitudeof parametereffectsasother parametersvary in a controlled manner, and we will examinethe interactionswith corpussize and specificity of clusteredadjectives. Preliminary results indicate that the importanceof linguistic knowledgeremains high even with large corpora, showingthat we cannotoffset the advantagesof linguistic knowledgejust by increasingthe corpussize. We plan to investigatethesetrendsandinteractions with extendedexperimentsin the future.

Acknowledgments Thisworkwassupported Research jointly by theAdvanced ProjectsAgency andtheOfficeof NavalResearch undergrantNOOO 14-89-J- 1782,by theOffice of NavalResearch undergrantNOOOI4 -95- 1-0745,andby theNationalScience Foundation undergrantGER-90-24069 . It wasperfonned undertheauspices of theColumbiaUniversityCATin HighPerfonnance andCommunications Computing in Health care, a New York StateCenterfor AdvancedTechnology

Chapter4

supportedby the New York StateScienceand TechnologyFoundation. Any opinions, findings, conclusions, or recommendationsexpressedin this publication aremine anddo not necessarilyreflect the views of the New York State Science and Technology Foundation. I thank Kathy McKeown, Jacques Robin, the anonymousreviewers, andthe BalancingAct workshoporganizers andeditorsof this book for providing useful comnientson earlier versionsof the chapter. References , and PaolaVelardi. The Noisy Channelandthe RobertoBasili, Maria TeresaPazienza the ACL WorkshopTheBalancingAct: Combining In . Braying Donkey Proceedingsof to es and Statistical Language, pp. 21- 28, Las Cruces, New Mexico Approach Symbolic , July 1994, Associationfor ComputationalLinguistics. PeterF. Brown, Vincent J. della Pietra, PeterV . de Souza, JenniferC. Lai, and Robert L. Mercer. Class-Basedn-gram Models of Natural Language.ComputationalLinguistics , 18(4) : 467- 479, 1992. KennethW. Church. A StochasticParts Programand Noun PhraseParserfor Unrestricted Text. In Proceedingsof the SecondConferenceon Applied Natural Language Processing,pp. 136- 143, Austin, Texas, February1988. , andPenelopeSibun. A Practical DouglasR. Cutting, Julian M. Kupiec, JanO. Pedersen Part-of-SpeechTagger. In Proceedingsof the Third Conferenceon AppliedNatural LanguageProcessing,pp. 133--140, Trent, Italy, April 1992. Nonnan R. Draper and Harry Smith. Applied RegressionAnalysis, 2nd edition, New York, Wiley , 1981. ' Michael Elhadad. GeneratingAdjectives to Express the Speakers Argumentative Intent. In Proceedingsof the 9th National Conferenceon Artificial Intelligence(AAAI91), pp. 98- 104, Anahelm, California, July 1991. AmericanAssociationfor Artificial Intelligence. William B. Frakes and Ricardo Baeza-Yates, editors. Information Retrieval: Data StructuresandAlgorithms. EnglewoodCliffs , N.J., PrenticeHall, 1992.

William A. Gale, KennethW ~Church, and David Y arowsky. EstimatingUpper and Lower Boundson the Perfonnanceof Word-SenseDisambiguationPrograms.In Proceeding of the30thAnnualMeetingof theACL, pp. 249--256, Newark, Del., June1992. Associationfor ComputationalLinguistics. William A. Gale, KennethW. Church, andDavid Y arowsky. Work on StatisticalMethods for Word SenseDisambiguation. In Probabilistic Approaches to Natural Language , : Papersfrom the 1992Fall Symposium , pp. 54- 60, Cambridge, Massachusetts October 1992. Menlo Park, Calif., American Associationfor Artificial Intelligence, AAAI Press, 1992. JeanDickinsonGibbonsandSubhabrataChakraborti. NonparametricStatisticalInference , 3rd edition, New York, Marcel Dekker, 1992.

Do We NeedLinguisticsWhenWe HaveStatistics?

Vasileios . Automatic Retrieval ofSemantic Hatzivassiloglou andScalar WordGroups fromFreeText -OI8-95, NewYork . Technical CUCS Report , Columbia , University 1995 . VasileiosHatzivassiloglou -Noun, Adjective . RetrievingAdjective -Adjective , and -AdverbSyntagmatic Adjective from Corpora : Extractionvia aFiniteRelationships StateGrammar , HeuristicSelection , andMorphological . TechnicalReport Processing CUCS-019-95, NewYork, ColumbiaUniversity , 1995. VasileiosHatzivassiloglou andKathleen McKeown . Towards theAutomaticIdentification of AdjectivalScales : Clustering . In Proceedings Adjectives Accordingto Meaning ofthe31stAnnualMeetingof theACL, pp. 172- 182,Columbus , Ohio, June1993.Association for Computational . Linguistics MartiA. Hearst . NounHomograph Disambiguation UsingLocalContextin LargeText . In Proceedings Corpora of the7thAnnualConference of theUniversityof Waterloo Centre for thetheNewOEDandTextRe~earch: UsingCorpora,Oxford, 1991. CharlesR. Hicks. Fundamental in theDesignof Experiments Concepts , 3rd edition, NewYork, Holt, Rinehart , andWilson, 1982. DonaldHindle. NounClassification -ArgumentStructures fromPredicate . InProceedings of the28thAnnualMeetingof theACL, pp. 268-275, Pittsburgh , June1990.Association for Computational . Linguistics JuliaB. Hirshberg . A Theoryof ScalarImplicature . Pill thesis of Computer , Department andInformationScience , Universityof Pennsylvania , Philadelphia , 1985. LeonardKaufmanandPeterJ. Rousseeuw . FindingGroupsin Data: AnIntroductionto ClusterAnalysis . NewYork, Wiley, 1990. MauriceG. Kendall. A New Measureof RankCorrelation . Biometrika , 30: 81- 93, 1938. MauriceG. Kendall.RankCorrelationMethods , 4thedition.London . , Griffin, 1975 KevinKnightandSteveK. Luk. Buildinga Large-ScaleKnowledge Basefor Machine Translation . In Proceedings of the12thNationalConference onArtijiciallntelligence (AAAl -94), vol. I , pp. 773- 778, Seattle , July- August1994.AmericanAssociation for ArtificialIntelligence . JulianM. Kupiec. RobustPart-of-SpeechTaggingUsinga HiddenMarkovModel. andLanguage Computer Speech , 6: 225-242, 1992 . AdrienneLehrer.Semantic FieldsandLexicalStructure . Amsterdam , NorthHolland. 1974. C. Levinson . Pragmatics . Cambridge Stephen , England , Cambridge , UniversityPress 1983. ElizabethD . LiddyandWoojinPaik. Statistically -GuidedWordSense . Disambiguation In Probabilistic esto NaturalLanguage : Papersfromthe1992Fall Symposium Approach , pp. 98--107,Cambridge , Massachusetts . October1992.MenloPark.Calif., American Association for ArtificialIntelligence , AAAI Press . , 1992 JohnLyons.Semantics , vol. I . Cambridge , England , Cambridge . 1977. UniversityPress

Chapter4 Igor A . MeI'cuk and Nikolaj V. Pertsov. SurfaceSyntaxof English: a Formal Model within theMeaning-TextFramework. Amsterdam, Benjamins, 1987. GeorgeA . Miller , RichardBeckwith, ChristianeFellbaum, DerekGross, andKatherine . /nternationaI Journal J. Miller . Introductionto WordNet: An On-Line Lexical Database of Lexicography(specialissue), 3(4) : 235- 312, 1990. JohannaD. Moore. Personalcommunication.June1993. : Human and Diane J. Litman. Intention-BasedSegmentation RebeccaJ. Passonneau Reliability and Correlationwith Linguistic Cues. In Proceedingsof the 31st Annual Meetingof the ACL, pp. 148- 155, Columbus, Ohio, June 1993. Associationfor Com . putationalLinguistics FernandoPereira, Naftali Tishby, andLillian Lee. DistributionalClusteringof English Words. In Proceedingsof the31stAnnualMeetingof theACL, pp. 183- 190, Columbus, Ohio, June1993. Associationfor ComputationalLinguistics. Philip Resnik. SemanticClassesandSyntacticAmbiguity. In Proceedingsof theARPA Workshopon Human LanguageTechnology, pp. 278- 283, Plainsboro, N.J., March 1993. ARPA Software and Intelligent SystemsTechnology Office, San Francisco, MorganKaufmann, 1993. Philip Resnikand MartiA . Hearst. StructuralAmbiguity and ConceptualRelations. In Proceedingsof the ACL Workshopon Very Large Corpora, pp. 58- 64, Columbus, Ohio, June1993. Associationfor ComputationalLinguistics.

: DisambiguationTechniquesin Victor Sadier. Working with Analogical Semantics DLT. Dordrecht, The Netherlands , Foris Publications, 1989. . In Proceedings Hinrich Schiitze. Word SenseDisambiguationWith SublexicalRepresentations . 109 - 113, NLP Based on , A A Al 92 Techniquespp Workshop Statistically of the SanJose, Calif., July 1992. AmericanAssociationfor Artificial Intelligence. John M. Sinclair (editor in chief) . Collins COBU/W English LanguageDictionary. London, Collins, 1987. Frank Smadja. RetrievingCollocationsfrom Text: Xtract. ComputationalLinguistics, 19( 1) : 143- 177, March 1993. HelmuthSpith. ClusterDissectionandAnalysis: Theory, FORTRANPrograms, Examples . Chichester,WestSussex,England, Ellis Horwood, 1985. . NeueJahrbecherfUr WissJostTrier. Das sprachlicheFeld. Eine Auseinandersetzung . 1934 10: 428449 , , wenschaftundJugenbildung C. J. van Rijsbergen./ nformation Retrieval, 2nd edition, London, Butterworths, 1979. Alex Waibel and Kai-Fu Lee, editors. Readingsin SpeechRecognition. San Mateo, Calif., MorganKaufmann, 1990. David Y arowSky. Decision Lists for Lexical Ambiguity Resolution: Application to AccentRestorationin SpanishandFrench. In Proceedingsof the 32ndAnnual Meeting of the ACL, pp. 88- 95, Las Cruces, NiM ., June 1994. Associationfor Computational Linguistics.

Chapter 5 The Automatic Construction of a Symbolic Parser via Statistical Techniques

Shyam Kapur and Robin Clark

At thecoreof contemporarygenerativesyntaxis thepremisethat all languages obeya set of universalprinciples, and syntacticvariation amonglanguagesis confinedto afinite numberof parameters. On this model, a child' s acquisition of the syntaxof his or her native languagedependson identifying the correct parameter settingsfor that language based on observation- for example, determiningwhethertoform questionsbyplacing questionwordsat the beginning of the sentence(e.g., English: Who did Mary say John saw) or leaving themsyntacticallyin situ (e.g., Chinese: Mary said John saw who) . Prevalent work onparametersettingfocuseson thewaythat observedeventsin thechild' s " " input might trigger settingsforparameters (e.g. [ Manzini and Wexier, 1987J), to the exclusionof inductiveor distributional analyses. In " TheAutomaticConstructionof a SymbolicParser via StatisticalTechniques " , Kapur and Clark build on their previouswork onproving learnability resultsin a stochasticsetting[Kapur, 1991Jand exploring the complexityof parametersetting in theface of realistic assumptionsabout how parameters interact [ Clark, 1992J. Here theycombineforces to presenta learning model in which distributional evidenceplays a critical role - while still adheringto an orthodox, symbolicview of languageacquisitionconsistentwith the Chomskianparadigm. Notably, they validatetheir approachby meansof an implementedmodel,testedon naturally occurringdata of the kind availableto child languagelearners.- Eds.

1 Motivation We report on the progresswe have madetoward developinga robust " selfconstructing " parsingdevicethat usesindirect negativeevidence[Kapur and Bilardi, 1991] to setitsparameters.Generally, by parameterwe meananypoint of variationbetweenlanguages ; thatis, a propertyon which two languagesmay

Chapter5

differ. Thus, therelativeplacementof anobjectwith respectto theverb, a determiner with respectto a noun, the differencebetweenprepositionaland postposition languagesand the presenceof long distanceanaphorslike Japanese " zibun" and Icelandic " " are all . A self-constructingparsing parameters sig devicewould be exposedto an input text consistingof simpleunpreprocessed . On the basisof this text, the devicewould induceindirect negative sentences evidencein supportof someoneparsingdevicelocatedin the parameterspace. The developmentof a self-constructingparsingsystemwould havea number of practical and theoreticalbenefits. First, such a parsing device would reducethe developmentcostsof new parsers.At the moment, grammarsmust be developedby hand, a techniquerequiringa significantinvestmentin money andman-hours. If a basicparsercouldbedevelopedautomatically,costswould be reducedsignificantly, evenif the parserrequiredsomefme-tuning after the initial automaticlearningprocedure. Second, a parsercapableof self-modificationis potentiallymorerobustwhenconfrontedwith novel or semigrammatical input. This type of parserwould haveapplicationsin informationretrieval as well as languageinstruction and grammarcorrection. As far as linguistic , the developmentof a parsercapableof self-modification theory is concerned would give us considerableinsight into the formal propertiesof complexsystems aswell asthetwin problemsof languagelearnabilityandlanguageacquisition , the researchproblemsthat haveprovidedthe foundationof generative grammar. Given a linguistic parameterspace,theproblemof locatinga targetlanguage somewherein the spaceon the basisof a text consistingof only grammatical is far from trivial. Clark [ 1990, 1992] hasshownthat the complexity sentences of the problemis potentially exponentialbecausethe relationshipbetweenthe pointsof variationandthe actualdatacanbe quite indirect andtangled. Since, given nparameters, thereare 2npossibleparsingdevices, enumerativesearch throughthe spaceis clearly impossible. Becauseeachdatummay besuccess fully parsedby a number of different parsing deviceswithin the spaceand the properties becausethe surfacepropertiesof grammaticalstringsunderdetermine of the parsing device which must be fixed by the learni~g algorithm, standarddeductivemachinelearningtechniquesareascomplexasa bruteenumerati search[Clark, 1992, 1994a]. In order to solve this problem, robust techniquesthat canrapidly eliminateinferior hypothesesmustbe developed. We proposea learningprocedurethat unitessymboliccomputationwith statistical tools. Historically, symbolic techniqueshave proved to be a versatile of . Thesetechniqueshavethe disadvantage tool in naturallanguageprocessing and error user or ) costly (as being both brittle (easily brokenby new input by

The AutomaticConSb'uctionof a SymbolicParservia StatisticalTechniques

97

grammars are extended to handle new constructions , development becomes more difficult owing to the complexity of rule interactions within the grammar ) . Statistical techniques have the advantage of robustness, although the resulting grantmars may lack the intuitive clarity found in symbolic systems. We propose to fuse the symbolic and statistical techniques, a development we view both as inevitable and welcome ; the resulting system will use statistical learning techniques to output a symbolic parsing device. We view this development to provide a nice middle ground between the problems of overtraining vs. undertraining . That is , statistical approaches to learning often tend to overfit the training set of data. Symbolic approaches, on the other hand, tend to behave as though they were undertrained (breaking down on novel input) since the grammar tends to be compact . Combining statistical techniques with symbolic parsing would give the adv~ tage of obtaining relatively compact descriptions (symbolic processing) with robustness ( statistical learning) that is not overtuned to the training set. We believe that our approach not only provides a new technique of obtaining robust parsers in natural language systems but also provides partial explanation for child language acquisition . Traditionally , in either of these separate fields of inquiry , two widely different approaches have been pursued. One of them is largely statistical and heavily data-driven ; another one is largely symbolic and theory -driven . Neither approach has proved exceptionally successful in either field . Our approach not only bridges the symbolic and statistical approaches but also tries to bring closer the two disparate fields of inquiry . We claim that the final outcome of the learning process is a grammar that is not simply some predefmed template with slots that have been filled in but rather crucially a product of the process itself . The result of setting a parameter to a certain value involves not just the fixing of that parameter but also apotential ' reorganization of the grantmar to reflect the new parameter s values. The final result must not only be any parser consistent with the parameter values but one that is also self -modifiable and .furthermore one that can modify itself along one of many directions depending on the subsequent input . Exactly for this reason, the relevance of our solution to a purely engineering solution to parser building remains- the parser builder cannot simply look up the parameter values in a table. In fact , parameter setting has to be a part , even just a small part , of the parser construction process. If this were not the case, we probably would have had little difficulty in building excellent parsers for individual languages . Equally , the notion of self- modification is of enormous interest to linguistic typologists and diachronic linguists . In particular , a careful study of self-modification would place substantive limits on linguistic variation and on

Chapter5

the ways in which languagescould, in principle, changeover time. The information -theoretic analysisof linguistic variation is still in its infancy, but it promisesto providean importanttheoreticaltool for linguists. (See[Clark and Roberts, in preparation] for applicationsto linguistic typology and diachronic change.) As far aschild languageacquisitionis concerned , viewing the parametersetting problemin an information theoreticlight seemsto be the bestperspective onecanput togetherfor this problem[Clark, 1994b; KapurandClark, in press]. Linguistic representationscarry information, universal grammar encodes informationaboutall naturallanguages , andthe linguistic input from the target languagemustcarry informationaboutthe targetlanguagein someform. The taskof the learnercanbe viewedasthat of efficiently andaccuratelydecoding the informationcontainedin !;heinput in order to haveenoughinformationto build the grammarfor the targetlanguage. To date, the information-theoreticprinciples underlying the entire process have not receivedadequateattention. For example, the most commonlyconsidered learningalgorithmis onethat simply movesfrom oneparametersetting to anotherparametersettingbasedonly on failure in parsing. That suchan algorithm is entirely implausibleempirically is one issue; in addition, it can be shownthat one of the fastestways for this algorithm to convergeis to take a randomwalk in the parameterspace, which is clearly grosslyinefficient. Such an approachis also inconsistentwith a maxim true about much of learning: " " We learn at the edgeof what we alreadyknow. Furthermore, in no sense would one be able to maintainthat thereis a monotonicincreasein the information thechild hasaboutthetargetlanguagein anyreal sense.We know from observationandexperimentationthat children' s learningappearsto be largely monotonic and fairly uniform acrosschildren. Finally and most important, thesealgorithmsfail to accountfor how certain information is necessaryfor children' s learningto proceedfrom stagen to stagen + I . Justas somebackground information is necessaryfor children' s learningto proceedfrom stage 0 (the initial state) to stageI , thereis goodreasonto believethat theremustbe somebackground+ acquiredinformationthat mustbe crucial to takethe child from stagen to stagen + I . In the algorithmswe consider, we provide arguments that the child canproceedfrom onestageto the next only becauseat the earlierstagethechild hasbeenableto acquireenoughinformationto be ableto build enoughstructure. This, in turn, is necessaryto in fact efficiently extract further informationfrom the input to learnfurther. The restrictivelearningalgorithmsthat we considerhereallow the process of informationextractionfrom a plausibleinput text to be investigatedin both

The AutomaticConstructionof a SymbolicParservia StatisticalTechniques

99

complete formal and computational detail . We hope to show that our work is leading the way to establish precisely the information -theoretic details of the entire learning process, from what the initial state needs to be to what can be learned and how . For example, another aspect in which previous attempts have been deficient is in their varying degrees of assumptions about what information the child has accessto when in the initial state. We feel that the most logical approach is to assumethat the child has no accessto any information unless it can be argued that without some information , learning would be impossible or at least infeasible . Some psycholinguistic consequences of our proposal appear to be empirically valid . For example, it has been observed that in relatively free word order languages such as Russian, the child fIrSt stabilizes on some word order , although not the same word order across children . Another linguistic and psycholinguistic consequenceof this proposal is that there is no need to stipulate markedness or initial preset values. Extensional relationships between languages and their purported consequences, such as the Subset Principle , are irrelevant . Furthermore , triggers need not be single utterances; statistical properties of the corpus may trigger parameter values. 2

Preliminaries

In this section, we fIrSt list some parameters that give some idea of the kinds of variations between languages that we hope our system is capable of handling . We then illustrate why parameter setting is difficult by standard methods. This provides some additional explanation for the failure so far in developing a truly universal parameterized parser.

2.

LioeuisticParameters Naturally, a necessarypreliminaryto our work is to specifya setof parameters that will serveas a testinggroundfor the learningalgorithm. This set of parameters must be embeddedin a parsingsystemso that the learningalgorithm can be testedagainstdata setsthat approximatethe kind of input that parsing devicesarelikely to encounterin real-world applications. Our goal, then, will be to first developa prototype. We do not requirethat the prototypeacceptany arbitrarily selectedlanguageor that the coverageof the prototype parser be complete in any given language. Instead, we will developa prototypewith coveragethat extendsto somebasic structuresthat any languagelearningdevicemustaccountfor , plus somestructuresthat have proved difficult for various learning theories. In particular, given an already

100

Chapter5

existing parser, we will extendits coverageby parameterizingit , asdescribed below. Our initial setof parameterswill includethe following otherpointsof variation :

1. Relative order of specifiersand heads: This parametercoversthe placement of determinersrelative to nouns, relativeposition of the subject, andthe placementof certainVP-modifying adverbs. : This parameterdealswith the 2. Relativeorder of headsand complements or orders), placementofnomi relative to the verb VO OV of ( position objects betweenprepositionsand as well as the choice nal andadjectivalcomplements , . postpositions 3. Scrambling: Somelanguagesallow (relatively) free word order. For example , Germanhas rules for displacing definite NPs and clausesout of their allows relatively free orderingof NPs andpostpositio canonicalpositions. Japanese phrasesso long as the verbal complex remainsclausefmal. Other languagesallow evenfreer word orders. We will focuson GermanandJapanese scrambling, bearingin mind that the model shouldbe extendibleto other typesof scrambling. 4. Relativeplacementof negativemarkersand verbs: Languagesvary as to wheretheyplacenegativemarkers, like Englishnot. Englishplacesits negative markerafterthefIrSttensedauxiliary, thusforcing do insertionwhenthereis no other auxiliary, whereasItalian placesnegationafter the tensedverb. French usesdiscontinuouselementslike ne . . . pas or ne . . . plus, which arewrapped aroundthe tensedverb or occur as continuouselementsin inflnitivals. The , giventherangeof propertreatmentof negationwill requireseveralparameters variation. 5. Root word order changes: In general, languagesallow for certain word order changesin root clausesbut not in embeddedclauses. An exampleof a root word orderchangeis subject-auxiliary inversionin English, which occurs in root questions(Did John leave? vs. * 1 wonder did John leave?). Another examplewould be inversionof the subjectclitic with the tensedverb in French " " (QuelIe pommeat -il mangee[ Which appledid he eat? ]) andthe processof subjectpostpositionand PP prepositionin English (A man walked into the room vs. Into the room walkeda man). 6. Rightwarddislocation: This includesextrapositionstructuresin English (That John is late amazesme. vs. It amazesme that John is late.), presentational there structures(A man was in the park. vs. There was a man in the park.), and stylistic inversionin French(Quellepiste Marie at -elle choisie?

The AutomaticConstructionof a SymbolicParservia StatisticalTechniques

101

" [ What path has Marie chosen?" ]) . Each of these constructions presentsunique problems so that the entire data set is best handled by a system of interacting parameters. 7. Wh -movement vs. wh - in situ: Languages vary in the way they encode whquestions. English obligato rily places one and only one wh phrase (e.g ., who or which picture ) in first position . In French the wh -phrase may remain in place ( in situ ) although it may also form wh questions as in English . Polish allows wh phrasesto be stacked at the beginning of the question. 8. Exceptional casemarking , structural casemarking : These parameters have little obvious effect on word order , but involve the treatment of infmitival complements . Thus , exceptional case marking and structural case marking allow " " for the generation of the order V [+tense ] is a ], where V [ +tense ] NP VP [-tense " " tensed verb and VP [-tense ] is a VP ~eaded by a verb in the infinitive . Both parameters involve the semantic relations between the NP and the infmitival VP as well as the treatment of case marking . These relations are reflected in constituent structure rather than word order and thus pose an interesting problem for the learning algorithm . 9. Raising and control : In the case of raising verbs and control verbs, the learner must correctly categorize verbs that occur in the same syntactic frame into two distinct groups based on semantic relations as reflected in the distribution of elements (e.g ., idiom chunks) around the verbs. " 10. Long - and short- distance anaphora: Short-distance anaphors, like himself " in English , must be related to a coreferential NP within a constrained " " " " local domain. Long - distance anaphors (Japanese zibun , Korean caki ) must also be related to a coreferential NP , but this NP need not be contained within the same type of local domain as in the short-distance case. The above sampling of parameters has the virtue of being both small (and therefore possible to implement relatively quickly ) and posing interesting learnability problems which will appropriately test our learning algorithm . Although the above list can be described succinctly , the set of possible targets will be large and a simple enumerative search through the possible targets will not be efficient .

2.2 Complexities of Parameter Setting Theoriesbasedon the principlesandparameters(P&P) paradigmhypothesize that languagessharea centralcore of universalpropertiesand that language variationcanbe accountedfor by appealto a fmite numberof points of variation . The parametersthemselvesmay take on only a , the so-calledparameters

102

Chapter5

finite numberof possiblevalues, prespecifiedby UniversalGrammar(UG). A fully specifiedP&P theorywould accountfor languageacquisitionby hypothesizing that the learnersetsparametersto the appropriatevaluesby monitoring the input stteamfor " triggering data" ; triggersare sentenceswhich causethe learnerto set a particular parameterto a particular value. For example, the " " imperativein ( 1) is a trigger for the order V (erb) O(bject) : ( 1) Kiss grandma. underthehypothesisthat the learneranalyzesgrandmaasthe patientof kissing andis predisposedto tteat patientsasstructuralobjects. Notice that trigger-basedparametersettingpresupposes that for eachparameter p andeachvaluev the learnercan identify the appropriatetrigger in the input stream. This is the prob~em of trigger detection. That is, given aparticular input item, the learnermust be able to recognizewhetheror not it is a trigger and, if so, what parameterand value it is a trigger for. Similarly, the learnermustbe able to recognizethat a particular input datumis not a trigger for a certainparametereventhoughit may sharemany propertieswith a trigger . In order to make the discussionmore concrete, considerthe following example: (2) a. Johnithinks that Mary likes himib. * Johnthinks that Maryj likes herj. Englishallowspronounsto becoreferentwith a c-comrnandingnominaljust in casethatnominalis not containedwithin thesamelocal syntacticdomainasthe pronoun; this is a universalpropertyof pronounsandwould seemto presentlittle problemto the learner. Note, however, that somelanguages , including Chinese, Icelandic, Japanese . Theseare elementswhich , and Korean, allow for long-distanceanaphors areobligatorily coreferentwith anothernominalin the sentence , but which may be separatedfrom that nomin.al by severalclauseboundaries . Thus, the following examplefrom Icelandicis grammaticaleventhoughthe anaphorsig is separated from its antecedent Jon by a clauseboundary[Anderson, 1986] : (3) J6nisegirad Maria elski sigi/ hanni Johnsaysthat Mary lovesself/him Johnsaysthat Mary loveshim. Thus, UG includes a parameterthat allows some languagesto have longdistanceanaphorsand that, perhaps,fiXescertainotherpropertiesof this class of anaphora .

The Automatic Construction of a Symbolic Parser via Statistical Techniques

103

Note that the example in ( 3 ) is of the same sttucture as the pronominal example in ( 2a ) . A learner whose target is English must not take examples like ( 2a ) as a bigger for the long distance anaphor parameter ; what prevents the ' learner from being deceived ? Why doesn t the learner conclude that English him is comparable to Icelandic sig ? We would argue that the learner is sensitive evidence . For example , the learner is aware of examples to disbibutional like ( 4 ) : ( 4 ) Johni likes himj ' where the pronoun is not co referential with anything else in the sentence . The existence of ( 4 ) implies that him cannot be a pure anaphor , long - distance or otherwise . Once the learner is aware of this disbibutional property of him , he or she can correctly rule out ( 2a ) as a potential bigger for the long - distance anaphor parameter . evidence , then , is crucial for parameter setting ; no theory of Disbibutional parameter setting can avoid statistical properties of the input text . How far can we push the statistical component of parameter setting ? In this chapter , we suggest that statistically based algorithms can be exploited to set parameters involving phenomena as diverse as word order , particularly verb second con sttuctions , and cliticization , the difference between free pronouns and proclitics . The work reported here can be viewed