CS674 Natural Language Processing Last class– Intro to lexical semantics Today– Lexical semantic resources: WordNet– Word sense disambiguation» Dictionary-based approaches» Supervised machine learning methods» Issues for WSD evaluationWordNet Handcrafted database of lexical relations Three separate databases: nouns; verbs; adjectives and adverbs Each database is a set of lexical entries (according to unique orthographic forms)– Set of senses associated with each entrySample entry Distribution of senses Zipf distribution of sensesWordNet relations Nouns Verbs Adjectives/adverbsCS674 Natural Language Processing Last class– Intro to lexical semantics Today– Lexical semantic resources: WordNet– Word sense disambiguation» Dictionary-based approaches» Supervised machine learning methods» Issues for WSD evaluationWord sense disambiguation Given a fixed set of senses is associated with a lexical item, determine which of them applies to a particular instance of the lexical item Two fundamental approaches– WSD occurs during semantic analysis as a side-effect of the elimination of ill-formed semantic representations– Stand-alone approach» WSD is performed independent of, and prior to, compositional semantic analysis» Makes minimal assumptions about what information will be available from other NLP processes» Applicable in large-scale practical applicationsDictionary-based approaches Rely on machine readable dictionaries Initial implementation of this kind of approach is due to Michael Lesk (1986)– Given a word W to be disambiguated» Retrieve all of the sense definitions, S, for W from the MRD» Compare each s in S to the dictionary definitions of all the remaining words in the context» Select the sense s with the most overlap with (the definitions of) these context wordsExample Word: cone Context: pine cone Sense definitionspine 1 kind of evergreen tree with needle-shaped leaves2 waste away through sorrow or illnesscone 1 solid body which narrows to a point2 something of this shape whether solid or hollow3 fruit of certain evergreen trees Accuracy of 50-70% on short samples of text from Pride and Prejudice and an AP newswire article.Machine learning approaches Machine learning methods– Supervised inductive learning– Bootstrapping– Unsupervised Emphasis is on acquiring the knowledge needed for the task from data, rather than from human analysts.Inductive ML frameworkNovel example(features)classExamples of task(features + class)ML AlgorithmClassifier(program)learn one such classifier for each lexeme to be disambiguatedcorrect word sensedescription of contextRunning exampleAn electric guitar and bass player stand off to one side, not really part of the scene, just as a sort of nod to gringo expectations perhaps.1 Fish sense2 Musical sense3…Feature vector representation target: the word to be disambiguated context : portion of the surrounding text– Select a “window” size– Tagged with part-of-speech information– Stemming or morphological processing– Possibly some partial parsing Convert the context (and target) into a set of features– Attribute-value pairs» Numeric or nominal valuesCollocational features Encode information about the lexical inhabitants of specific positions located to the left or right of the target word.– E.g. the word, its root form, its part-of-speech– An electric guitar and bass player stand off to one side, not really part of the scene, just as a sort of nod to gringo expectations perhaps.– [guitar, NN1, and, CJC, player, NN1, stand, VVB]Co-occurrence features Encodes information about neighboring words, ignoring exact positions.– Features: the words themselves (or their roots)– Values: number of times the word occurs in a region surrounding the target word– Select a small number of frequently used content words for use as features» 12 most frequent content words from a collection of basssentences drawn from the WSJ: fishing, big, sound, player, fly, rod, pound, double, runs, playing, guitar, band» Co-occurrence vector (window of size 10) for the previous example:[0,0,0,1,0,0,0,0,0,0,1,0]Decision list classifiers Decision lists: equivalent to simple case statements.– Classifier consists of a sequence of tests to be applied to each input example/vector; returns a word sense. Continue only until the first applicable test. Default test returns the majority sense.Decision list example Binary decision: fish bass vs. musical bassLearning decision lists Consists of generating and ordering individual tests based on the characteristics of the training data Generation: every feature-value pair constitutes a test Ordering: based on accuracy on the training set Associate the appropriate sense with each test⎟⎟⎠⎞⎜⎜⎝⎛==)|()|(log21jijivfSensePvfSensePabsWSD Evaluation Corpora:– line corpus– Yarowsky’s 1995 corpus » 12 words (plant, space, bass, …)» ~4000 instances of each– Ng and Lee (1996)» 121 nouns, 70 verbs (most frequently occurring/ambiguous); WordNetsenses» 192,800 occurrences– SEMCOR (Landes et al. 1998)» Portion of the Brown corpus tagged with WordNet senses– SENSEVAL (Kilgarriff and Rosenzweig, 2000)» Annual performance evaluation conference» Provides an evaluation framework (Kilgarriff and Palmer, 2000) Baseline: most frequent senseWSD Evaluation Metrics– Precision» Nature of the senses used has a huge effect on the results» E.g. results using coarse distinctions cannot easily be compared to results based on finer-grained word senses – Partial credit» Worse to confuse musical sense of bass with a fish sense than with another musical sense» Exact-sense match Æ full credit» Select the correct broad sense Æ partial credit» Scheme depends on the organization of senses being usedSENSEVAL-2 Three tasks– Lexical sample– All-words– Translation 12 languages Lexicon– SENSEVAL-1: from HECTOR corpus– SENSEVAL-2: from WordNet 1.7 93 systems from 34 teamsLexical sample task Select a sample of words from the lexicon Systems must then tag several instances of the sample words in short extracts of text SENSEVAL-1: 35 words, 41 tasks– 700001 John Dos Passos wrote a poem that talked of `the <tag>bitter</> beat look, the scorn on the lip." – 700002 The beans almost double in size during roasting. Black beans are over roasted and will