Named Entity Recognition and Classification 90 Fabian M. Suchanek
Semantic IE You are here 2 Source Selection and Preparation Entity Recognition Entity Disambiguation singer Fact Extraction Reasoning Instance Extraction singer Elvis
Overview •  Named Entity Recognition and Classification (NERC) •  NERC Features •  NERC by rules •  NERC by Classification •  NERC by Conditional Random Fields 3
Def: NE Recognition & Classification Named Entity Recognition and Classification  (NERC) is the task of (1) finding entity names in a corpus and (2) annotating each name with a class out of a set of given classes. 4 classes={Person, Location, Organization} Arthur Dent eats at Milliways. (This is often called simply “Named Entity Recognition”. We use “Named Entity Recognition and Classification” here to distinguish it from bare NER.)
5 classes={Person, Location, Organization}  Person Organization Arthur Dent eats at Milliways. Named Entity Recognition and Classification  (NERC) is the task of (1) finding entity names in a corpus and (2) annotating each name with a class out of a set of given classes. Def: NE Recognition & Classification >examples (This is often called simply “Named Entity Recognition”. We use “Named Entity Recognition and Classification” here to distinguish it from bare NER.)
Classes 6 NERC usually focuses the classes person, location, and organization. But some also extract money, percent, phone number, job title, artefact, brand, product, protein, drug, etc. [Sobha Lalitha Devi] >examples
NERC examples Try this 7 Arthur Dent visits Milliways, a restaurant located at End of the Universe Street 42. 41 towel OTHER 41 . OTHER 42 Arthur PER 42 Dent PER 42 visits OTHER 42 Milliways ORG in XML in TSV <per>Arthur Dent</per> visits <org>Milliways</org>, a restaurant located at <loc>End of the Universe Street 42</loc>. TSV file of • sentence number • token • class >examples
NERC examples 8 Arthur D. Dent visits Milliways, a restaurant located at End of the Universe Street 42. 42 Arthur  PER 42 D.  PER 42 Dent  PER 42 visits OTHER 42 Milliways ORG 42 , OTHER One way to deal with multi-token words is to annotate each of them (which is what we will do). >examples
NERC examples 9 Arthur D. Dent visits Milliways, a restaurant located at End of the Universe Street 42. 42 Arthur  PER_START 42 D.  PER_MIDDLE 42 Dent  PER_END 42 visits OTHER 42 Milliways ORG 42 , OTHER Another way to deal with multi-token words is to mark the start, middle, and end. >examples
Now do it here: We have determined the crystal structure of a triacylglycerol lipase from Pseudomonas cepacia (Pet) in the absence of a bound inhibitor using X-ray crystallography. The structure shows the lipase to contain an alpha/beta-hydrolase fold and a catalytic triad comprising of residues Ser87, His286 and Asp264. The enzyme shares ... Diana Maynard: Named Entity Recognition 10 >examples
NERC is not easy • Organization vs. Location     • Company vs Artefact     • Location vs. Organization • Ambiguity England won the World Cup. The World Cup took place in England. shares in MTV watching MTV she met him at Heathrow the Heathrow authorities Diana Maynard: Named Entity Recognition 11 May (month, person, or verb?), Washington, etc.
Overview 12 •  Named Entity Recognition and Classification (NERC) •  NERC Features •  NERC by rules •  NERC by Classification •  NERC by Conditional Random Fields
Window 13 token  is a sequence of characters that forms a unit, such as a word, a punctuation symbol, a number, etc. window  of width   of a token   in a corpus is the sequence of   tokens before  , the token   itself, and   tokens after  . Window of width   around ”: Position 0 Position -1 Position +1 [“, you, know , ”, said, Arthur, “] “You know” said Arthur “I really wish I’d listened to what my mother told me when I was young.” — “Why, what did she tell you?” “I don’t know, I didn’t listen.”
Window 14 token  is a sequence of characters that forms a unit, such as a word, a punctuation symbol, a number, etc. window  of width   of a token   in a corpus is the sequence of   tokens before  , the token   itself, and   tokens after  . Window of width   around “said”: Position 0 Position -1 Position +1 [you, know , ”, said, Arthur, “, I] “You know” said Arthur “I really wish I’d listened to what my mother told me when I was young.” — “Why, what did she tell you?” “I don’t know, I didn’t listen.”
Window 15 token  is a sequence of characters that forms a unit, such as a word, a punctuation symbol, a number, etc. window  of width   of a token   in a corpus is the sequence of   tokens before  , the token   itself, and   tokens after  . Window of width   around “Arthur”: Position 0 Position -1 Position +1 [know , ”, said, Arthur, “, I, really] “You know” said Arthur “I really wish I’d listened to what my mother told me when I was young.” — “Why, what did she tell you?” “I don’t know, I didn’t listen.”
NERC Feature 16 An  NERC feature  is a property of a token that could indicate a certain NERC class for the main token of a window. is stopword matches [A-Z][a-z]+ is punctuation [know , ”, said, Arthur, “, I, really] 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 >features
Syntactic Features • capitalized word • all upper case word • smallcase word • mixed letters/numbers • number • special symbol • space • punctuation • Regular expression The Stanford NERC system uses string patterns:    Paris  —>  Xxxx    M2 D&K  —>  X# X&X    +33 1234  —>  +## #### Fenchurch WSOGMM planet HG2G 42     .,;:?! [A-Z][a-z]+ 17 a [Jenny Rose Finkel] >features
Dictionary Features 18 • cities • countries • titles • common names • airport codes • words that identify a company • common nouns • hard‐coded words Vassilian UK Dr. Arthur CDG Inc, Corp, ... car, president, ... M2 ... if you have a dictionary. The dictionary can be implemented, e.g, as a trie. Michael Loster, Zhe Zuo, Felix Naumann, Oliver Maspfuhl,  Dirk Thomas: “Improving Company Recognition from Unstructured Text by using Dictionaries” EDBT 2017 >features
19 Proper Name Verb Determiner Adverb Adjective Noun Preposition Pronoun Part-of-Speech  (also: POS, POS-tag, word class, lexical class, lexical category) is a set of words with the same grammatical role. Def: POS Alizée wrote a really great song by herself >features
POS Tag Features for NERC 20 [Penn Treebank symbols] DT IN JJ NN NNP PRP RB SYM VBZ ... Determiner Preposition or subordinating conjunction  Adjective Noun, singular or mass  Proper noun, singular  Personal pronoun  Adverb Symbol Verb, 3rd person singular present  >features
Morphological features • word endings • word contains an n‐gram • word contains n‐grams at boundaries -ish, -ist, ... Par, ari, ris #Par, ari, ris# 21 Intuition: quite often, the morphology of the word gives a hint about its type. Examples:    London Bank  —>  ORG    Cotramoxazole  —>  DRUG
Overview 22 •  Named Entity Recognition and Classification (NERC) •  NERC Features •  NERC by rules •  NERC by Classification •  NERC by Conditional Random Fields
Def: NERC by rules NERC by rules  uses rules of the form               ...where   are features and   is a class.   are the  designated features . If a window of tokens matches  , we annotate the tokens of the designated features with  . “in” [ ([A-Z][a-z]+) ] “City” => Location She works in London City each day. 23 Location >examples
Examples for NERC rules Dictionary:Title “.” [ CapWord{2} ] => Person 24 Features Features, their syntax, and their language are system dependent. [ CapWord (Street|Av|Road) ] => Location “a pub in” [CapWord] => Location  “based in” [CapWord] => Location “to the” Compass “of” [CapWord] => Location Designated features >examples
NERC examples from GATE Sunita Sarawagi: Information Extraction 25 task>24
Task: NERC patterns Design NERC patterns that can find planets in the following text. Describe each feature. Lamuella is the nice planet where Arthur Dent lives. Santraginus V is a planet with marble-sanded beaches.  Magrathea is an ancient planet in Nebula. The fifty-armed Jatravartids live on Viltvodle VI. 26 (Patterns should generalize beyond the names in this text.) Example: [CapWord] “is a planet” (this pattern does not work, it's here for inspiration)
Possible Solution: NERC patterns   • CapWord: A word that starts with a  capital letter. • “is”, “planet”: plain strings • (the|a|an): the words “the”, “a”, or “an” • Adj: an adjective (dictionary lookup)   • CapWord: as above • RomanNumeral: A roman numeral (I, II, V, X, ...) 27 [CapWord] "is" (the|a|an) Adj "planet" [CapWord RomanNumeral]
Conflicting NERC rules If two NERC rules match overlapping strings, we have to decide which one to apply. Possible strategies: • annotate only with the rule that has a longer match • manually define order of precedence CapWord CapWord RomanNum => planet CapWord “Minor” => illness 28 He lives on Ursa Minor IV. >cascade
Def: Cascaded NERC Cascaded NERC applies NERC to the corpus annotated by a previous NERC run. 29 Main Street 42, West City <street>Main Street 42</street>, <city>West City</city> <adr><street>Main Street 42</street>, <city>West City</city></adr> First NERC run Second NERC run [Street City] => Adr  • Street: a previously annotated street • City: a previously annotated city  Cascaded NERC rule: >task
Task: Cascaded NERC Write NERC rules for the first run and the second, cascaded run of a NERC to recognize person names as in Dr. Bob Miller Monsieur François Hollande Mademoiselle Alizée Jacozey Ms Gary Day-Ellison 30
Possible Solution: Cascaded NERC First run:   Dictionary:AcademicTitle => Title   Dictionary:FrenchTitle => Title   Dictionary:EnglishTitle => Title   CapWord-CapWord => Name   CapWord => Name   Second run:   Title Name Name => Person 31
Matching NERC rules Given a NERC rule and a corpus, how can we match the rule on the corpus? Another possibility is to compile the rule to a regex: 32 Dict:Title  [CapWord] => Person (Dr|Prof|Mr|Ms)  [A-Z][a-z]+ => Person One possibility is to hard-code the rule: if(window.getWordAt(-1)=="in") return(LOCATION); ...
Learning NERC Rules NERC rules are often designed manually (as in the GATE system). However, they can also be learned automatically (as in the Rapier, LP2, FOIL, and WHISK systems). We will now see a blueprint for a bottom-up rule learning algorithm. 33 >learn
Example: Rule learning 0. Start with annotated     training corpus 34 <pers>Arthur</pers> says “Hello”
Example: Rule learning 0. Start with annotated     training corpus 1. Find a NERC rule    for each annotation 35 <pers>Arthur</pers> says “Hello” [Arthur] "says “Hello”" => pers
Example: Rule learning 0. Start with annotated     training corpus 1. Find a NERC rule    for each annotation 36 <pers>Arthur</pers> says “Hello” [Arthur] "says “Hello”" => pers [Ford] "says “Hello”" => pers
Example: Rule learning 37 <pers>Arthur</pers> says “Hello” [Arthur] "says “Hello”" => pers [Ford] "says “Hello”" => pers 2. Merge two rules by replacing    a feature by a more general    feature [CapWord] "says “Hello”" => pers Generalize 0. Start with annotated     training corpus 1. Find a NERC rule    for each annotation
Example: Rule learning 38 <pers>Arthur</pers> says “Hello” [Arthur] "says “Hello”" => pers 2. Merge two rules by replacing    a feature by a more general    feature [CapWord] "says “Hello”" => pers Generalize [Ford] "says “Hello”" => pers [CapWord] "says “Bye”" => pers 0. Start with annotated     training corpus 1. Find a NERC rule    for each annotation
Example: Rule learning 39 <pers>Arthur</pers> says “Hello” [Arthur] "says “Hello”" => pers 2. Merge two rules by replacing    a feature by a more general    feature [CapWord] "says “Hello”" => pers Generalize [Ford] "says “Hello”" => pers [CapWord] "says “Bye”" => pers Drop 3. Merge two rules by dropping    a feature [CapWord] "says" => pers 0. Start with annotated     training corpus 1. Find a NERC rule    for each annotation
Example: Rule learning 40 <pers>Arthur</pers> says “Hello” [Arthur] "says “Hello”" => pers 2. Merge two rules by replacing    a feature by a more general    feature [CapWord] "says “Hello”" => pers Generalize [Ford] "says “Hello”" => pers [CapWord] "says “Bye”" => pers Drop 3. Merge two rules by dropping    a feature [CapWord] "says" => pers [CapWord] (says|yells|screams)=>pers 0. Start with annotated     training corpus 1. Find a NERC rule    for each annotation
Example: Rule learning 41 <pers>Arthur</pers> says “Hello” [Arthur] "says “Hello”" => pers 2. Merge two rules by replacing    a feature by a more general    feature [CapWord] "says “Hello”" => pers Generalize [Ford] "says “Hello”" => pers [CapWord] "says “Bye”" => pers Drop 3. Merge two rules by dropping    a feature [CapWord] "says" => pers [CapWord] (says|yells|screams)=>pers 4. Remove redundant rules 5. Repeat 0. Start with annotated     training corpus 1. Find a NERC rule    for each annotation
NERC rule learning is not easy 42 Then [Ford] "says “Hello”" => pers And [Arthur] "yells “Bye”" => pers
NERC rule learning is not easy 43 Conj Cap Word Drop Then [Ford] "says “Hello”" => pers And [Arthur] "yells “Bye”" => pers
NERC rule learning is not easy Conj Cap Word Drop 44 Name Cap Word 1stNam Verb (s.|y.) Word Drop String (Hello|Bye) Word Drop Then [Ford] "says “Hello”" => pers And [Arthur] "yells “Bye”" => pers
NERC rule learning is not easy Conj Cap Word Drop 45 Name Cap Word 1stNam Verb (s.|y.) Word Drop String (Hello|Bye) Word Drop There are exponentially many ways to merge rules. Then [Ford] "says “Hello”" => pers And [Arthur] "yells “Bye”" => pers
Goal of NERC rule learning Learn rules that • cover all training examples (high recall) • don’t cover non-annotated strings (high precision) • are not too specific/numerous   (we do not want 1 rule for each annotation) 46
Overview 47 •  Named Entity Recognition and Classification (NERC) •  NERC Features •  NERC by rules •  NERC by Classification •  NERC by Conditional Random Fields ->total-2018
NERC by Classification NERC can be seen as a classification task: • given training examples (a corpus tagged with classes) • determine the class of an untagged word Any classification algorithm can be used:  k-Nearest-Neighbors, Decision Trees, SVMs, ... 48 x x x x x x x + + + + + + + o >kNN >details
kNN kNN  (k nearest neighbors) is a simple classification algorithm that assigns the class that dominates among the   nearest neighbors of the input element. 49 x x x x x x x + + + + + + + o The class  +  dominates among the   nearest neighbors of  o   => classify  o  as  +  is a constant that is fixed a priori. It serves to make the algorithm more robust to noise. To avoid ties,   is chosen odd. x kNN (and other classification algorithms) require a  distance function on the examples. >details
Naïve distance function 50 Represent each example window as a vector  if Feature   applies to the token at position  relative to the main token  is upper case  is stopword Everyone loves <per>Fenchurch</per> because... < >
Naïve distance function 51 Represent each example window as a vector  if Feature   applies to the token at position  relative to the main token  is upper case  is stopword Everyone loves <per>Fenchurch</per> because... < > < >
Naïve distance function 52 Represent each example window as a vector  if Feature   applies to the token at position  relative to the main token  is upper case  is stopword Everyone loves <per>Fenchurch</per> because... Represent the input also as a (potentially weighted) feature vector: < > Nobody loves <?>Arthur</?> because... < > < >
Naïve distance function 53 Represent each example window as a vector  if Feature   applies to the token at position  relative to the main token  is upper case  is stopword Everyone loves <per>Fenchurch</per> because... Represent the input also as a (potentially weighted) feature vector: Nobody loves <?>Arthur</?> because... Then use the Euclidian distance. < > < > < >
Overview 54 •  Named Entity Recognition and Classification (NERC) •  NERC Features •  NERC by rules •  NERC by Classification •  NERC by Conditional Random Fields ->total-2018
Conditional Random Fields We assume a probability distribution over all possible sentences and all possible annotations. 55 Hidden variables Visible variables X1 Arthur Arthur Arthur Arthur He She X2 Dent Dent Dent Dent loves does Y2 PER PER PER LOC OTH OTH Y1 PER PER LOC PER OTH LOC X3 sleeps sleeps sleeps sleeps her not Y3 OTH LOC OTH LOC PER OTH P( P( P( P( P( P( >details )= 0.2 )= 0.1 )= 0.1 )= 0.05 )= 0.01 )= 0.01
Conditional Random Fields 56 Let us look at the conditional probability X1 Arthur Arthur Arthur Arthur X2 Dent Dent Dent Dent Y2 PER PER LOC LOC Y1 PER PER PER PER X3 sleeps sleeps sleeps sleeps Y3 OTH LOC OTH LOC P( P( P( P( >details )= 0.2 )= 0.1 )= 0.1 )= 0.05 PER OTH
Conditional Random Fields 57 Let us look at the conditional probability X1 Arthur Arthur X2 Dent Dent Y2 PER LOC Y1 PER PER X3 sleeps sleeps Y3 OTH OTH P( P( >details )= 0.2 )= 0.1 PER OTH