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 . . .