Das System KnowItAll
Transcrição
Das System KnowItAll
Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen Gliederung Dokumentverarbeitung – Materialien zur Vorlesung 1 Motivation 2 Instanzen 3 Subklassen 4 Listen Informationsextraktion im System KnowItAll D. Rösner Institut für Wissens- und Sprachverarbeitung Fakultät für Informatik Otto-von-Guericke Universität Magdeburg c WS 2013/14, 10. Februar 2014, 2010 - 2014 D.Rösner D. Rösner D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen DokV 2013/14 . . . Motivation Instanzen Subklassen Listen IE IE das System KnowItAll das System KnowItAll ein IE-System, das unüberwacht und gebietsunabhängig arbeiten soll unüberwacht . . . keine manuell ausgezeichneten Daten erforderlich Ziel: Information zu Instanzen finden (vgl. [ECD+ 05]) In our initial experiments with KnowItAll, we have focused on a sub-problem of information extraction, building lists of named entities found on the Web, such as instances of the class City or the class Film. KnowItAll is able to extract instances of relations, such as capitalOf(City,Country) or starsIn(Actor,Film), but the focus of this paper is on extracting comprehensive lists of named entities. (vgl. [ECD+ 05]) D. Rösner DokV 2013/14 . . . D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen KnowItAll KnowItAll Architektur: generiere und teste (generate-and-test) zum Generieren von Kandidaten werden gebietsunabhängige Extraktionsmuster verwendet Beispiel: NP1 such as NPList2 instantiiert als cities such as NPList2 liefert z.B. We provide tours to cities such as Paris, London, and Berlin. Architektur: generiere und teste (generate-and-test) zum Testen der Plausibilität von Kandidaten werden mit Hilfe von Suchmaschinen statistische Werte bestimmt dazu werden Anfragen mit sog. Diskriminator-Phrasen gestellt (vgl. [ECD+ 05]) + (vgl. [ECD 05]) D. Rösner DokV 2013/14 . . . D. Rösner Motivation Instanzen Subklassen Listen DokV 2013/14 . . . Motivation Instanzen Subklassen Listen KnowItAll KnowItAll ein generisches Regeltemplat einzige gebietsspezifische Eingabe: Menge sog. Prädikate diese benennen Bezeichner (labels), die bei der Gewinnung spezifischer Extraktionsregeln aus generischen Regeltemplaten verwendet werden Beispiele: Predicate: City Predicate: Film labels: ’city’, ’town’ labels: ’film’, ’movie’ (vgl. Fig. 6 in [ECD+ 05]) Predicate: Class1 Pattern: NP1 ’such as’ NPList2 Constraints: head(NP1)= plural(label(Class1)) & properNoun(head(each(NPList2))) Bindings: Class1(head(each(NPList2))) wird z.B. Class1 durch ’City’ ersetzt, dann sucht das instantiierte Muster nach ’cities such as’ und gewinnt aus den Köpfen der dieser Phrase nachfolgenden NPs dann Kandidaten für mögliche Städtenamen (vgl. Fig. 1 in [ECD+ 05]) D. Rösner DokV 2013/14 . . . D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen KnowItAll KnowItAll Beispielergebnisse einer Altavista-Suche mit ’cities such as’ aber auch ... from major cities, such as power plants, dams and oil ... in Intelligence gathered by the U.S. government indicates that al-Qaeda terrorists have a keen interest in striking targets far from major cities, such as power plants, dams and oil facilities in Alaska. Beispielergebnisse einer Altavista-Suche mit ’cities such as’ The Major Cities, such as Boston, Chicago, and New York, face many of the same ... ... away from crowded major cities such as Beijing and Shanghai, ... Midsize airports outside major cities, such as New York and Los Angeles, are the ... (vgl. [ECD+ 05]) (vgl. [ECD+ 05]) D. Rösner D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen DokV 2013/14 . . . Motivation Instanzen Subklassen Listen KnowItAll KnowItAll Extraktor Altavista-Suche mit ’mayors of major cities such as’ liefert Beispiele wie The mayors of major cities such as Atlanta and Milwaukee have jumped into the ... aber auch State governors and mayors of major cities such as Mayor Shirley Franklin in Atlanta, Georgia. verwendet reguläre Ausdrücke auf POS-Tags des sog. Brill-Taggers, um einfache Nominalphrasen und Listen von NPs zu identifizieren als Kopf wird im allgemeinen das letzte Wort der Phrase genommen es sei denn, dieses beginnt mit Grossbuchstaben dann wird nach links nach weiteren mit Grossbuchstaben beginnenden Token gesucht Beispiel: (vgl. [ECD+ 05]) The tour includes major cities such as New York, central Los Angeles, and Dallas D. Rösner DokV 2013/14 . . . D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen KnowItAll KnowItAll eine aus einem generischen Regeltemplat gewonnene Extraktionsregel für Städtenamen Predicate: City Pattern: NP1 ’such as’ NPList2 Constraints: head(NP1)= ’cities’ & properNoun(head(each(NPList2))) Bindings: City(head(each(NPList2))) Keywords: ’cities such as’ (vgl. Fig. 4 in [ECD+ 05]) D. Rösner Diskriminatoren: sind Extraktionsmuster aus Kontextstrings und Platzhaltern (sog. Slots) für die Argumente des Prädikats Beispiele: Discriminator for: City ’city X’ Discriminator for: CeoOf(Person,Company) ’X CEO of Y’ zum Validieren einer Extraktion wird die extrahierte Phrase anstelle des Platzhalters eingesetzt und mit dem entstandenen String dann eine Suchanfrage an eine Suchmaschine gestellt (vgl. [ECD+ 05]) D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen KnowItAll KnowItAll Bootstrapping damit System auf neue Klassen unaufwändig erweiterbar, soll dies ohne menschliche Intervention geschehen Vorgehen: aus generischen Regeltemplaten werden Extraktionsregeln und Queries und aus den Keyword-Phrasen der Regeln und den Klassennamen werden Diskriminatorphrasen erzeugt Beispiele für Klasse Country: ’country X’, ’X country’, ’countries such as X’, ’X is a country’ (vgl. DokV 2013/14 . . . Bootstrapping Erfahrung: günstig ist, wenn für jede Klasse mindestens zwei Namen verwendet werden Beispiele für Klasse Country: ’country’, ’nation’, damit kann inhärenter Mehrdeutigkeit einzelner Bezeichner entgegengewirkt werden ’country’ allein könnte auch Musikrichtung oder Landschaft bezeichnen (vgl. [ECD+ 05]) [ECD+ 05]) D. Rösner DokV 2013/14 . . . D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen KnowItAll KnowItAll ein ausführliches Beispiel für die Rolle der (gelernten) Diskriminatoren liefert 2.8. in [ECD+ 05] Ausschnitte: Suppose that the query is ’and other cities’, from a rule with extraction pattern: NP ’and other cities’. zwei mögliche Fundstellen: ’Short flights connect Casablanca with Fes and other cities.’ ’Since 1984, the ensemble has performed concerts throughout the East Coast and other cities.’ Wie unterscheidet der sog. Assessor mithilfe der Diskriminatoren zwischen der korrekten Extraktion von ’Fes’ und der inkorrekten von ’East Coast’? To compute the probability of City(Fes), the Assessor sends six queries to the Web, and finds the following hit counts. ’Fes’ has 446,000 hits; ’Fes is a city’ has 14 hits, giving a PMI score of 0.000031 for this discriminator, which is over the threshold for this discriminator. Fes is also above threshold for ’cities Fes’ (201 hits); ’cities such as Fes’ (10 hits); and ’cities including Fes’ (4 hits). It is below threshold on only one discriminator, with 0 hits for ’Fes and other towns’. The final probability is 0.99815. (vgl. 2.8. in [ECD+ 05]) D. Rösner D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen DokV 2013/14 . . . Motivation Instanzen Subklassen Listen KnowItAll KnowItAll: Extraktion von Subklassen In contrast, the Assessor finds that City(East Coast) is below threshold for all discriminators. Even though there are 141 hits for ’cities East Coast’, 1 hit for ’cities such as East Coast’, and 3 hits for ’cities including East Coast’, the PMI scores are below threshold when divided by 1.7 million hits for ’East Coast’. The final probability is 0.00027. nicht alle Wissenschaftler sind als ’scientists’ auffindbar einige werden als Astronomen, Biologen, Chemiker, usw. aufgeführt wenn sich solche Subklassen automatisch lernen lassen, dann können damit evtl. größere Mengen von Instanzen gefunden werden (vgl. [ECD+ 05]) (vgl. 2.8. in [ECD+ 05]) D. Rösner DokV 2013/14 . . . D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen KnowItAll: Extraktion von Subklassen Kandidaten für Subklassen werden – wie auch Kandidaten für Instanzen – mit gebietsunabhängigen Extraktionsregeln gewonnen der Unterschied liegt in den Tests Regeln für die Extraktion von Subklassen prüfen, ob Kandidaten echte Nomen sind (und daher im Englischen klein geschrieben) umgekehrt wird für Instanzen auf Grossschreibung getestet als Indiz für Eigennamen (vgl. [ECD+ 05]) D. Rösner KnowItAll: Regeln zur Extraktion von Subklassen Pattern Extraction C1 {’,’} ’such as’ CN isA(CN,C1) ’such’ C1 ’as’ CN isA(CN,C1) CN {’,’} ’and other’ C1 isA(CN,C1) CN {’,’} ’or other’ C1 isA(CN,C1) C1 {’,’} ’including’ CN isA(CN,C1) C1 {’,’} ’especially’ CN isA(CN,C1) C1 ’and’ CN isA(CN, class(C1)) C1 {’,’} C2 {’,’} ’and’ CN isA(CN, class(C1)) hierbei: C1 und C2 bezeichnen Klassen und CN ein echtes Nomen (engl. common noun) bzw. eine Phrase mit einem echten Nomen (vgl. Table 2 in [ECD+ 05]) D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen DokV 2013/14 . . . Motivation Instanzen Subklassen Listen KnowItAll: Extraktion von Subklassen wieder Ansatz des Generiere-und-Teste erster Test: Morphologie des Kandidaten betrachten, denn einige Namen von Subklassen entstehen durch Verknüpfen des Klassennamens mit einem Präfix Beispiel: Mikrobiologe als Subklasse von Biologe KnowItAll: Extraktion von Subklassen Generiere-und-Teste zweiter Test: Ist die Subklasse als Hyponym (d.h. Spezialisierung) der Klasse in WordNet vorhanden? Falls ja, dann hohe Wahrscheinlichkeit zuweisen. (vgl. [ECD+ 05]) (vgl. [ECD+ 05]) D. Rösner DokV 2013/14 . . . D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen KnowItAll: Extraktion von Subklassen Beispiele: WordNet nennt u.a. die folgenden Hyponyme von biologist: bacteriologist – (a biologist who studies bacteria) botanist, phytologist, plant scientist – (a biologist specializing in the study of plants) cytologist – (a biologist who studies the structure and function of cells) ecologist – (a biologist who studies the relation between organisms and their environment) geneticist - (a biologist who specializes in genetics) (vgl. [ECD+ 05]) KnowItAll: Extraktion von Subklassen weitere Unterscheidungen kontextunabhängige Extraktion kontextabhängige Extraktion: durch Menge von Schlüsselwörtern wird der Kontext charakterisiert diese werden bei den Suchanfragen mitverwendet Beispiel: bei kontextunabhängiger Extraktion von Subklassen von Person ist Priester guter Kandidat dies ist anders bei kontextabhängiger Extraktion im Kontext Pharmazie (vgl. [ECD+ 05]) D. Rösner DokV 2013/14 . . . D. Rösner Motivation Instanzen Subklassen Listen DokV 2013/14 . . . Motivation Instanzen Subklassen Listen KnowItAll: Extraktion von Subklassen KnowItAll: Extraktion aus Listen Grundidee der Listenextraktion (LE): weitere Unterscheidung: benannte Subklassen: haben einen eigenen Bezeichner abgeleitete Subklassen: Kopfnomen ist identisch mit dem Bezeichner der Superklasse Beispiele: benannte Subklassen: ’capital’ als Subklasse von ’city’ abgeleitete Subklassen: ’European city’ als Subklasse von ’city’ benannte Subklassen liefern mehr neue Instanzen (vgl. [ECD+ 05]) mit bereits bekannten Instanzen einer Klasse (den sog. ’seeds’) werden Listen aufgespürt, die diese Instanzen enthalten für diese Listen werden sog. ’Wrapper’, d.h. strukturbezogene Extraktionsmuster, gelernt mit diesen werden weitere Elemente aus den Listen extrahiert und nach Anzahl der Fundstellen sortiert Hintergrund: strukturierte Webseiten mit Listen und Tabellen oft aus Datenbanken generiert (vgl. [ECD+ 05]) D. Rösner DokV 2013/14 . . . D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Motivation Instanzen Subklassen Listen KnowItAll: Extraktion aus Listen Beispiel: (vgl. Fig. 15 in [ECD+ 05]) 1 <html> 2 <body> 3 My favorite countries: 4 <table> 5 <tr><td><a>Italy</a></td><td><a>Japan</a></td><td><a>France</a></td></tr> 6 <tr><td><a>Israel</a></td><td><a>Spain</a></td><td><a>Brazil</a></td></tr> 7 </table> 8 My favorite pets: 9 <table> 10 <tr><td><a>Dog</a></td><td><a>Cat</a></td><td><a>Alligator</a></td></tr> 11 </table> 12 </body> 13 </html> D. Rösner DokV 2013/14 . . . Motivation Instanzen Subklassen Listen Literatur: I Oren Etzioni, Michael Cafarella, Doug Downey, Ana-Maria Popescu, Tal Shaked, Stephen Soderland, Daniel S. Weld, and Alexander Yates. Unsupervised Named-Entity Extraction from the Web: An Experimental Study. AI Journal, 2005. D. Rösner DokV 2013/14 . . . KnowItAll: Extraktion aus Listen Beispiel: (vgl. Fig. 15 in [ECD+ 05]) Keywords: Italy, Japan, Spain, Brazil Wrappers (at least 2 keywords match): w1 (1 - 13): <td><a>TOKEN</a></td> w2 (2 - 12): <td><a>TOKEN</a></td> w3 (4 - 7): <td><a>TOKEN</a></td> w4 (5 - 5): <td><a>TOKEN</a></td><td><a> W5 (6 - 6): </a></td><td><a>TOKEN</a></td> D. Rösner DokV 2013/14 . . .