Fabian M. Suchanek Named Entity Recognition 59 >intro
Semantic IE You are here 2 Source Selection and Preparation Entity Recognition Entity Disambiguation singer Fact Extraction Reasoning Instance Extraction singer Elvis
Overview 3 • Named Entity Recognition •  ...by dictionary •  ...by regex
Named Entity named entity  is an instance that has a name. This typically concerns people, organizations, and artifacts. Hitchhiker’s guide to the galaxy 4 Douglas Adams Télécom Paris
Def: Named Entity Recognition Named entity recognition  (NER) is the task of finding entity names in a corpus. 5 (In its basic form, NER does not care to which entity the name belongs. It just finds names.) In homage to Douglas Adams’ book “Hitchhiker’s Guide to the Galaxy” Google replies to the question of “life, the universe, and everything” with the number “42”. Try it out
NER is difficult 6 Alexander the Great ? ? Douglas Adam wrote the book The Hitchhiker’s guide to the galaxy in... Cable and Wireless, a major company... Microsoft and Dell both agreed... In the beginning the Universe was created. This has made a lot of people very angry and been widely regarded as a bad move. Quotes form Douglas Adams. Capital Letters Were Always The Best Way Of Dealing With Things You Didn't Have A Good Answer To. ?
Def: Dictionary A dictionary (also: gazetteer, lexicon) is a set of entity names. NER by dictionary finds only names of the dictionary. It can be used if the entities are known upfront. • US states • countries • Dow Jones companies • Actors of a   given movie • ... 7 ...lived in Los Angeles, California, while... US states: {Alabama, Alaska, California, ...}
Books by Douglas Adams: {   Life, the Universe and Everything   Hitchhiker’s Guide to the Galaxy   Mostly Harmless   ... } Naive Dictionary NER is slow The Hitchhiker’s Guide to the Galaxy has “Don't Panic” on it, in large, mostly friendly letters. 8 ?
Books by Douglas Adams: {   Life, the Universe and Everything   Hitchhiker’s Guide to the Galaxy   Mostly Harmless   ... } Naive Dictionary NER is slow The Hitchhiker’s Guide to the Galaxy has “Don't Panic” on it, in large, mostly friendly letters. 9 ?
Def: Trie A trie is a tree, where nodes are labeled with booleans and edges are labeled with characters. 10 A D A O M S R A
A trie contains strings A trie contains a string, if the string denotes a path from the root to a node marked with “true”. 11 A D A O M S R A {ADA, ADAMS, ADORA}
Adding strings (1) To add a string that is a prefix of an existing string, switch node to “true”. 12 A D A O M S R A {ADA, ADAMS, ADORA} + ADAM
Adding strings (1) {ADA, ADAM, ADAMS, ADORA} 13 A D A O M S R A To add a string that is a prefix of an existing string, switch node to “true”.
Adding strings (2) To add another string, make a new branch. {ADA, ADAM, ADAMS, ADORA} + ART 14 A D A O M S R A
Adding strings (2) {ADA, ADAM, ADAMS, ADORA, ART} 15 A D A O M S R A R T To add another string, make a new branch. >task
Task: Tries Start with an empty trie. Add • bon • bonbon • on 16 A D A O M S R A
Tries can be used for NER For every character in the doc • advance as far as possible   in the trie and   • report match whenever     you meet a “true” node Adams adores Adora. 17 A D A M S R A O ...
Tries have good runtime Adams adores Adora. 18 A D A M S R A O ... >tasks
Task: NER with tries Do NER with the trie from the last task on the document on aime un bon bonbon. 19 >tasks
One more example 20 kofi anan eats an ananas in panama, ana! a n a n i
Tricks with Tries In practice, you can • force tries  to respect   word boundaries • ignore upcase/lowcase • preprocess the string • ignore nested words • ... 21 kofi anan eats an ananas in panama, ana! a n a n i
Dictionary NER Advantages: • very efficient, Disadvantages: dictionaries • have to be given upfront • have to be maintened to accommodate new names • cannot deal with name variants • cannot deal with infinite or unknown sets of names   (e.g., people’s names) 22
Overview 23 • Named Entity Recognition •  ...by dictionary •  ...by regex
Some names follow patterns The trilogy consist of 5 books, written in 1979, 1980, 1982, 1984, and 1992, respectively. Dr. Frankie and Dr. Benjy have no doctoral title. Main street 42 West Country People with titles 24 Years Addresses >alphabet
Def: Alphabet, Word An  alphabet  is a set of symbols. We will use as alphabet always implicitly the set of all unicode characters. 25 A={a,b,c,d,e,f,0,1,2,3,4,5,6,7,8,9} A={0,...9,a...,z,A...Z,!,?,...} word  over an alphabet A is a sequence of symbols from A. Since we use the alphabet of unicode characters, words are just strings. hello!, 42, 3.141592, Douglas and Sally  also with spaces!
Def: Language language  over an alphabet S is a set of words over S. 26 Set of strings we want to describe L1 = {Arthur Dent, Ford Prefect, Marvin} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = {ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...}
Def: Language A language over an alphabet S is a set of words over S. 27  a* Our description (much shorter than the original set!) Set of strings we want to describe L1 = {Arthur Dent, Ford Prefect, Marvin} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = {ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...}
Def: Language A language over an alphabet S is a set of words over S. 28 ca*  a* L1 = {Arthur Dent, Ford Prefect, Marvin} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...} Our description (much shorter than the original set!) Set of strings we want to describe
Def: Language A language over an alphabet S is a set of words over S. 29 ca*  a* Our description (much shorter than the original set!) Set of strings we want to describe (ab)* L1 = {Arthur Dent, Ford Prefect, Marvin} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...}
Def: Language A language over an alphabet S is a set of words over S. 30 aa* = a+ ca*  a* Our description (much shorter than the original set!) Set of strings we want to describe (ab)* L1 = {Arthur Dent, Ford Prefect, Marvin} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...}
Def: Language A language over an alphabet S is a set of words over S. 31 a+ | b+ aa* = a+ ca*  a* Our description (much shorter than the original set!) Set of strings we want to describe (ab)* L1 = {Arthur Dent, Ford Prefect, Marvin} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...}
Def: Language A language over an alphabet S is a set of words over S. 32 aa* = a+ ca*  a* Our description (much shorter than the original set!) Set of strings we want to describe (ab)* L1 = {Arthur Dent, Ford Prefect, Marvin} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...} (a | b)+ a+ | b+
Def: Language A language over an alphabet S is a set of words over S. 33 (0 | 1 | ... | 9) = [0-9] aa* = a+ ca*  a* Our description (much shorter than the original set!) Set of strings we want to describe (ab)* L1 = {Arthur Dent, Ford Prefect, Marvin} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...} (a | b)+ a+ | b+
Def: Language A language over an alphabet S is a set of words over S. 34 [0-9][0-9][0-9][0-9] = [0-9]{4} (0 | 1 | ... | 9) = [0-9] aa* = a+ ca*  a* Our description (much shorter than the original set!) Set of strings we want to describe (ab)* L1 = {Arthur Dent, Ford Prefect, ...} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...} (a | b)+ a+ | b+
Def: Language A language over an alphabet S is a set of words over S. 35 [A-Z][a-z]+ [A-Z][a-z]+ [0-9][0-9][0-9][0-9] = [0-9]{4} (0 | 1 | ... | 9) = [0-9] (a | b)+ a+ | b+ aa* = a+ ca*  a* Our description (much shorter than the original set!) Set of strings we want to describe (ab)* L1 = {Arthur Dent, Ford Prefect, ...} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...}
Regular expressions A regular expression (regex) describes a language. 36 The language of a regular expression [0-9][0-9][0-9][0-9] = [0-9]{4} (0 | 1 | ... | 9) = [0-9] (a | b)+ a+ | b+ aa* = a+ ca*  a* [A-Z][a-z]+ [A-Z][a-z]+ L1 = {Arthur Dent, Ford Prefect, ...} L2 = {1900, 1901, 1982, 2013, 2017, ...} L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L4 = {a, ab, abb, bbba, aaabbab, ababa, ...} L5 = {a, b, aa, bb, aaa, bbb, ...} L6 = {a, aa, aaa, ...} L7 = { , ab, abab, ababab, ...} L8 = {c, ca, caa, caaa, ...} L9 = { , a, aa, aaa, ...} *   for symbols 
Def: Regular expressions regular expression  (regex) over an alphabet   is one of the following: • the empty string • an element of  • a string of the form XY    • a string of the form (X|Y)  • a string of the form (X)* where X and Y are regexes A regex is associated to a language: 37 its language the regular expression (0 is a special regex that cannot appear as part of other regexes. It represents the empty language and does not match any string.) *   for symbols  ->formal-grammars
Real-world example 38