A Unifying Approach to HTML Wrapper Representation and Learning

A Unifying Approach to HTML Wrapper Representation and

Learning

Gunter Grieser, Klaus P.Jantke, Steffen Lange, Bernd Thomas

Seminarvortrag - Informationsextraktion (1/2003)

21.01.2003 Seminarvortrag - Informationsextraktion

2

1.Motivation und Zielsetzung

• HTML ist Standardformat für Information aus dem Internet

• Informationsextraktion aus HTML kommerziell lohnend

• Ansatz auf beliebig formatierte Texte übertragbar

• Konstruktiver (algorithmischer) Beitrag zu bestehenden Theorien

• Existenz von Testumgebungen (http://Lexikon.dfki.de)


3

1.1 Information - eingebettet in HTML

<ul><li>Vortrag über: Line Eikvil (1999) Information extraction from the World Wide Web (Stephan Birkmann) (<a href="birkmann.ppt">ppt</a>/<a href="birkmann.pdf">pdf</a>)</li><li>Vortrag über: Ralph Grishman (1997) "Information Extraction: Techniques and Challenges" (Felix Jungermann) (<a href="jungermann.ppt">ppt</a>/<a href="jungermann.pdf">pdf</a>)</li><li>Vortrag über: Roman Yangarber, Ralph Grishman, Pasi Tapanainen, Silja Huttunen (2000) "Unsupervised Discovery of Scenario-Level Patterns for Information Extraction" (Bianca Selzam) (<a href="selzam.ppt">ppt</a>/<a href="selzam.pdf">pdf</a>)</li><li>Vortrag über: Karsten Winkler, Myra Spiliopoulou " Structuring Domain-Specific Text Archives by Deriving a Probabilistic XML DTD"<br>(Andrea Schweer) (<a href="AndreaSchweer-SeminarFolien-20021217.pdf">pdf</a>)</li></ul>

Automatische Extraktion der Namen der Referenten !?


4

2. Einordnung dieses Ansatzes

Informationsextraktion• Wrapper• Natürlichsprachlich

Prädikatenlogik• Logikprogramme• EFS, AEFS

Lernmodelle• Gold („in the limit“)• PAC-Modell

Rekursionstheorie (+KT)


5

3. Syntax/Semantik formaler SystemeGrundlegende Definitionen

: :onSubstituti

)Instance" ground" :(auch ,....,A :Regel

)Atom" ground" :(auch ),....,p( :Atom

)( aus Elemente :Pattern

Regeln von Menge Endliche :

Variablen von Menge:

Prädikaten von Menge Endliche :

en von ZeichMenge Endliche:

1

1

n

n

BB


6

3.1 Elementary Formal Systems (EFS)

Definition:

Instances groundaller Menge:G(S)

Basis) (Herbrand Atoms groundaller Menge:B(S)

EFSist ),,( S

Semantik:

)( :)( und ))((:)(:omit

}:, G(S) ,....,|{)(:)(

) )( ( :)(

1

11

0

Nn

nS

nSS

nS

ikn

Sn

S

S

TSSemITTITS

IBiBBAAITIT

SBIIIT

Smullyan (1961), Theory of Formal Systems


7

3.2 Advanced Elementary Formal SystemsDefinition: AEFSseien ),,(:),,,(:

EFS sei )',',(:'

222111

SS

S

Dann:1.2. 3.

4.

)()Sem(S Sem(S) AEFS,ist ),,(dann , Falls 21212121 SSemS

)}(),...,(,,...,|),...,({)()(

AEFSist )}),...,( ),...,({},{,(Dann

n.t Stelligkeider Prädikate und Seien

11111

1111

11

SSemssqsssspSSemSSem

xxqnotxxppS

qp

nnn

nn

))(()(

AEFSist )',',(dann ,)'( Sei

1'

111

SSemTSSem

Shead

Nn

nS

)'()( AEFS.ist ' SSemSSemSS

Vorteil: Negation as Failure


8

3.3 Formale Systeme-Formale Sprachen

Zusätzliche Definitionen für formale Systeme:

AEFS bounded"-length"aller Menge :

AEFS bounded"-variable"aller Menge :

AEFSaller Menge :

EFSaller Menge :

Alb

Avb

Übergang zu formalen Sprachen (->Wrapper):1.

2.

)}()(|{:),( seiDann

Prädikat. eseinstellig und AEFSein ),,( Sei

SSemspspSL

pS

können.werden definiert aus AEFSdurch die

Sprachen, von Menge die )(ist Dann . Sei

M

MLAM

-> Formale Sprachen sind durch formale Systeme definierbar


9

3.4 Ausdrucksfähigkeit von AEFS

Einordnung von formalen Systemen:

)( .4

)( .3

)( .2

)( .1

lbLL

vbLL

AlbLL

ALL

sitivkontextsen

aufzählbarrekursiv

sitivkontextsen

aufzählbarrekursiv

Ausserdem:1. Semantik von allgemeinen EFS nicht entscheidbar2. Semantik von „length-bounded“ AEFS entscheidbar


10

4. Lernen und Identifizieren

Abstraktes Modell einer Identifikation (Gold, 1967):

Objekten von ngNamensgebu 3.

tionnspräsentaInformatiozur Methoden 2.

tLernbarkei von Definition 1.

Objekten von Menge eine Sei

Zusammenhang zwischen Identifikation von Objekten und Lernen von Sprachen (z.b Wrapper)


11

4.1 Lernbarkeit

Zu jedem Zeitpunkt erfolgt ein Identifikationsversuch:

),....,( 1 tt iiGg G : „Guessing function“gt : „Guess“ zum Zeitpunkt t

„Language Identification in the Limit“: Nach endlicher Zeit treten keine falschen „guesses“ mehr auf-> Existenz zahlreicher Variationen des Lernmodells Beispiel: zusätzliche Monotonierestriktionen


12

4.2 Informationspräsentation

1. Text : Ausschließlich Positive Information Arbitrary: Sequenz wird bestimmt durch beliebige Funktion Recursive: Sequenz wird bestimmt durch rekursive Funktion

2. Informant: Positive und Negative Information Arbitrary: Sequenz wird bestimmt durch beliebige Funktion Methodical: Sequenz wird durch Aufzählung bestimmt Request: Sequenz wird bestimmt in Abhängigkeit der schon bestehenden Sequenz


13

4.3 Namensgebung

Namensgebung mittels einer Funktion:

Nf

:

Namen von Menge :N

(Sprachen)Objekten von Menge :

Für theoretische Untersuchungen üblich:1. Tester : Entscheidungsalgorithmus für eine Sprache 2. Generatoren: Aufzählung aller Wörter einer Sprache


14

4.4 Erkenntnisse zur Lernbarkeit


15

4.5 Lernbarkeit von AEFS

Theorem 1:

informant""durch lernbar ist )( 2.

informant""durch lernbar nicht ist )( .1

AlbL

AvbL

Theorem 2:

text""durch lernbar ist )( 2.

text""durch lernbar nicht ist )(,2Für 1.1

AlbL

AlbLk k


16

4.6 Beweisidee zu Theorem 2 (1)

Definition:

)})( )(,)({},,{,(: )(mit }|{:

))({},{,(:S }{\,}{:

}{:

2

000

xqnotxpaqqpSAlbLNjL

xppaLLaL

a

jjj

jj

Idee: Konstruktion eines Textes für L0, sodaß Identifizierung unmöglich wird.

1 bei weiter und 1 t: xsetze

, t) Zeitpunkt(zum von ErkennungNach .3

eReihenfolghischen Lexikograpder gFortsetzun 3.

aon von Präsentati ,L von ErkennungNach 2.

mit startend eReihenfolg hischeLexikograp 1.

:durchgebildet wird(Text) Sequenz ,1:mit Start

0

xx

1

L

a

xx

-> „Subset-Principle“


17

5. Wrapper für HTML-Dokumente

Semantik und Interpretation von Dokumenten:

ii

inn

n

ss

sDssIpp

s

S

D

von Endenach Din beginnt 2.

an )(der ionen Startposit diegibt )),,...,((),...,( 1.

:nBedingunge die S(D) )s,...,(erfüllt D, Dokumente alleFür

:gdw I,tion Interpretaunter Semantik heißt ))((:

Dokument.ein Sei

1

11

n1

Semantik eines Dokumentes ist Tupel aus Wörtern des Dokumentes


18

5.1 „Marked Text“ (1.Erweiterung)

Lernen von Wrappern durch Vorlage einer Sequenz von markierten Dokumenten

Definition:

)( Tupel jegliche DDokument jedesfür enthält Sequenz 3.

ation)(Interpret ),( und )( wobei,),( 2.

ausDokument ist 1.

:gdw , text"marked"heißt ),( Sequenz Eine

DSs

DsIpDSspsP

D

PDt

i

i

ii


19

5.2 Island WrapperIsland Wrapper <-> Kombination von mehreren AEFS

).()( ).()( ).()(

)( )(

).()( ).()( ).()(

)( )(

).(),(),(),(

),....,(),(),(),(

),(),(),(

)...,,...,(

2222

111

111111

2222

111

YpXYpcXpXYpcXpXpc

XpcnotXpnc

YpXYpcXpXYpcXpXpc

XpcnotXpnc

RpVpncLpXpnc

RpVpncLpXpnc

RpVpncLp

XRVLXRVLXVVw

iiiiii

ii

iiiiii

ii

nnnn

rrrrrr

rr

nrnrnn

rr

rr

nnnnnn

Gesucht sind Ankersprachen: ),( ),,(iiiiii rrr pSLLpSLL


20

5.3 Wrapper Learner (2.Erweiterung)Anwendung des Wrappers auf ein Dokument:

Ein Wrapper (AEFS Siw) beschreibt Semantik S, gdw: view(Siw,D) = S(D)

)}(),,...,(|),...,{(:),(

(AEFS) Wrapper Islandein Sei

11 iwnniw

iw

SSemDsswssDSview

S

1. Ein Wrapper-Learner (WIM) lernt Semantik S aus „marked Text“, falls nach endlicher Zeit der Wrapper diese Semantik beschreibt

2. Ein Wrapper-Learner (WIM) lernt eine Klasse C von Wrappern, falls er jegliche Semantiken lernen kann, die durch Wrapper aus C beschrieben werden können


21

5.4 Lernen mit Island Wrappern

Definition:

Lhen Ankerspracfür )(mit Wrapper Island bounded"-length"aller Menge :

(AEFS) Wrapper Island bounded"-length"aller Menge :kiw kLCardA

A iw

Theorem 3: text"marked"durch lernbar nicht ist Klasse Die iwA

Theorem 4:1 allefür text"marked"durch lernbar ist Klasse Die kA k

iw

Lernalgorithmus ?


22

6.1 Lernalgorithmus (Teil I)


23

6.2 Lernalgorithmus (Teil II)


24

6.3 Lernalgorithmus (Teil III)


25

7. Praxisrelevanz und Bewertung

• Algorithmus wurde bereits implementiert und an HTML getestet

• http://LExIKON.dfki.de

• Basisprinzip der Wrapper-Induction auch in diesem Ansatz vorhanden

• Theorie zeigt das Potential des gewählten Ansatzes

• Vorgestellte Wrapper-Induction bisher nur in der Praxis evaluiert

Documents

A Unifying Approach to HTML Wrapper Representation and Learning