Inhalt | Index

←zurück | vorwärts→

11Verarbeitung natürlicher Sprachen

Natural Language Processing (NLP), Natural Language Understanding

Natürliche Sprache:

Zeichen menschlicher Intelligenz
Kommunikation zwischen Menschen
unterstützt (ermöglicht ?) Denken
Mensch viel besser als Computer

Warum sollte der Computer natürliche Sprache verstehen:

Ergründung natürlicher Sprache als Teil menschlicher Inteligenz (kognitive Psychologie)
menschengerechte Kommunikation mit Computersystemen (angewandte AI)
Unterstützung des Menschen beim Umgang mit natürlicher Sprache (angewandte AI)

Anwendungen:

1) Benützerfreundliche Kommunikation mit Computersystemen

Computer ist kein Mensch ⇒ Kommunikation muss nicht in natürlicher Sprache sein; auch Menus, Icons, etc.

a) Datenbankabfragen

Datenbankabfragen (auch syntaktisch falsche) sollten semantisch richtig verstanden und beantwortet werden, ohne Rücksicht auf die Speicherungsform.

Beispiel:

Frage:	Antwort:
Fliegt der Vogel ?	yes (richtig)
Bewegung Vogel ? ...ungrammatikalische Frage	Fliegen (richtig)
get_value( vogel, fliegt, ja)	yes (richtig; wurde so gespeichert)
get_value( vogel, bewegungsart, fliegt)	no ("yes" wäre erwünscht) (wurde nicht so gespeichert)

b) Kommunikation mit dem Betriebssystem

Oft wissen wir genau was wir machen wollen, wissen aber nicht wie wir es dem Computer mitteilen sollen.

Beispiel:
Copy f1.txt to Max Kunz as f2.txt !
Ist es: copy f1.txt kunz:f2.txt ?
oder: cp f1.txt ~kunz/f2.txt ?

2) Übersetzung: Sprache 1 ⇒ Sprache 2

3) Wissensextraktion: Sprache (z.B. Lehrbuch, Zeitung) ⇒ Wissen

4) Sprachgenerierung: Wissen ⇒ Sprache (Erklärungen, Dokumentation)

Hauptziel von NLP: Aus dem geschriebenen Satz die "Bedeutung" extrahieren und womöglich eine Aktion ausführen.

Satz	Bedeutung	Aktion
Please, copy ...	copy( f1, f2)	Kopiere
$copy ...	copy( f1, f2)	Kopiere
Dogs chase cats	∀ D, C {dog(D), cat(C) ⇒ chase(D, C)}	-

Sprache:

Phonologie, Morphologie:
Aufbau von Wörtern
Syntax:
charakterisiert korrekt aufgebaute Sätze
korrekt: The man goes home.
falsch: The man go haus.
Semantik (Bedeutung):
relativ: verschieden Darstellungen möglich, z.B. copy( from: f1, to: f2) .
mehrdeutig: He saw the man on the hill with a telescope.
(telescope kann sich beziehen auf: he, the man, the hill)
Pragmatik
Abhängigkeit der Syntax und Semantik vom Kontext, z.B.: Sprachregion (Süden / Norden), soziale Schicht (slang), Individuum, Anlass, etc.
Can you close the door?... Yes.

NLP:

Satz als Folge von Buchstaben (aus einem Alphabet)
	Lexikalische Analyse: Buchstaben ⇒ Wörter ("Tokenizing")
Satz als Folge von Wörtern (aus einem Lexikon)
	Syntaktische Analyse: Wörter ⇒ Satzstruktur
Satz als Struktur von Satzteilen (phrases) (gemäss einer Grammatik
	Syntax-basierte Analyse: Satzstruktur ⇒ Satzbedeutung Semantische Analyse: Wörter ⇒ Satzbedeutung
Bedeutung des Satzes (in einer internen Darstellung)
	Aktion: Bedeutung ⇒ Resultat
Resultat (beantwortete Frage, ausgeführter Befehl)

11.1Semantische Analyse

Betonung der Semantik. Semantik wird ziemlich direkt aus den Wörtern unter (teilweise) Umgehung der Syntaxanalyse erzeugt. Gut geeignet für beschränkte Gebiete, oder als Prototypen; schnelle Realisierbarkeit.

11.1.1Pattern Matching

Auch: Template Matching, Keyword Analysis

Beispiel.:

Pattern für copy: " * copy * FILENAME1 to FILENAME2 *"
* : 0, 1, oder mehrere Wörter
copy, to: Schlüsselwörter (keywords)
FILENAME1, FILENAME2: Variablen
Semantik: copy( FILENAME1, FILENAME2)

ELIZA (Weizenbaum, 1966)

Simulation eines Psychologen, "vernünftige" Konversation ohne Verständnis. Prolog-Implementierung von Sterling, Shapiro, p. 275. Die "Variablen" $1, $2, ... matchen ein Wort oder einen Satzteil. Die Variable X matcht ein Wort.

Beispiel einer Konversation

Patient	Computer
i am so unhappy.	How long have you been so unhappy ?
can you help me?	What makes you think I can help you ?
you remind me of my father	Please tell me more about father
i like teasing father	Does anyone else in your family like teasing father?
no, only me	Please go on.

Pattern matching

Patient	/Pattern/ Computer
i am so unhappy.	/i am $1/ How long have you been $1?
can you help me?	/$1 you $2 me/ What makes you think I $1 $2 you ?
you remind me of my father	/$1 X $2 important(X)/ Please tell me more about X
i like teasing father	/i like $1/ Does anyone else in your family like $1 ?
no, only me	/$1/ Please go on.

Eliza in Prolog

eliza( [bye]) :-
    write( 'Goodby. I hope I have helped you.'), nl,
    !.
eliza( Input) :-
    pattern( Stimulus, Response),
    match( Stimulus, Table, Input), 
    match( Response, Table, Output), 
    write_list( Output),
    !.
    
match( [N| Pattern], Table, Words) :-
    integer( N), lookup( N, Table, Words1),
    append( Words1, Words2, Words),
    match( Pattern, Table, Words2).
match( [Word| Pattern], Table, [Word| Words]) :-
    atom( Word), match( Pattern, Table, Words).
match( [], Table, []).

lookup( Key, [(Key, Value)| Dict], Value).
lookup( Key, [(Key1, Value1)| Dict], Value) :-
    Key \= Key1, lookup( Key, Dict, Value).

pattern( [i, am, 1], ['How long have you been', 1, ?]).
pattern( [1, you, 2, me], ['What makes you think I', 1, 2, you, ?]).
pattern( [i, like, 1], ['Does anyone else in your family like', 1, ?]).
pattern( [i, feel, 1], ['Do you often feel that way?']).
pattern( [1, X, 2], ['Please tell me more about', X, .]) :- important( X).
pattern( [1], ['Please go on.']).

important( father).
important( mother).

11.1.2Case Grammars

Im Zentrum des Satzes steht das Verb (Fillmore 1968).

Beispiel:
Satz 1: The man opened the door with a key.
Satz 2: The door was opened with a key by the man.

Beide Sätze haben die gleiche Semantik:

opened
- agent: the man
- object: the door
- instrument: the key

Allgemein:

verb
- case_1: value_1
- case_2: value_2
- . . .

Verb: zentrales Element (Aktion, ...)

Cases (of the verb):

agent (who)
instrument (with what)
dative (to whom)
factitive (result)
locative (where)
source (from ...)
goal (to ...)
time (when)
object (what).

11.1.3Semantic Grammar

( Burton 1976; Hendrix, Sacerdoti 1977 ) LADDER, LIFER: natürlichsprachliche Interfaces zu NAVY-Datenbanken

Semantische Grammatik:

question → what is PROPERTY of SHIP ?
PROPERTY → the PROP | PROP
PROP → speed | length | ...

11.2Syntaktische Analyse (Grammar-based Analysis)

Betonung der Syntax. Zuerst wird der Satz syntaktisch analysiert. Aus der syntaktischen Darstellung (z.B. Parse Tree) wird die Semantik generiert. Die Semantik kann auch gleichzeitig mit der Syntax erzeugt werden. Allgemein für alle Gebiete.

11.2.1Grammatik

Grammatik = endliche Anzahl Regeln (Produktionen), die alle syntaktisch korrekte Sätze charakterisieren, d.h. die Syntax definieren.

Beispiel:

Fig 11.1: Syntax-Baum

Nonterminals (Satzteil):

s	sentence
np	noun phrase
vp	verb phrase
noun	noun
verb	verb
adj	adjective

Terminals (Wörter):

'the', 'man', 'reads', 'good', 'books', ...

Produktionen

(→ bedeutet "besteht aus", | bedeutet "oder", Terminals in Anführungszeichen '...') :

s -> np vp
np -> noun | adj noun | det noun | det adj noun
vp -> verb | verb np
det -> 'the' | 'a'
noun -> 'man' | 'books' | ...
verb -> 'reads' | ...
adj -> 'good' | ...

Syntaxanalyse: Satz ⇒ Satzstruktur (Parse Tree)

Top-down (goal driven, "backward")
s → np vp → det noun vp → the noun vp → ... → the man reads good books
Bottom-up (data-driven, "forward")
the man reads good books → det man reads good books → ... → np vp → s

11.2.2Augmented Transition Networks (ATN)

(Woods, 1970: Implementierungen in Lisp). Grundidee: Rekursiver Zustandsgrap (Recursive Transition Network).

Beispiel:

Fig. 11.2: Augmented Transition Network

Interpretation durch eine Zustandsmachine: Ein Satzteil (Nichterminal) wird erkannt, wenn man vom entprechenden Anfangsknoten (Rechteck) über Zwischenzustände zum entsprechenden Endknoten gelangen kann. Die Transitionen können benutzt werden, falls man die zugehörigen Graphen auch durchlaufen kann.

ATN ist eine Erweiterung dieses Formalismus: Beim Durchlaufen des Graphen können Rechnungen ausgeführt und Information in Variablen gespeichert werden.

11.2.3Definite Clause Grammars (DCG)

Definite Clause = Horn Klausel mit genau einem positivem Literal, also:
p :- p1, ..., pn .
(Colmerauer: Prolog, ca. 1972).

Beispiel: Satz
S = [the, man, reads, good, books]

1. Ansatz

s( S) = S ist ein korrekter Satz
s( S) :- append( NP, VP, S), 
    np( NP), vp( VP).
….
noun( man).

append wirkt als Generator aller Sublisten. Dies ist ineffizient, da alle Sublisten zuerst ganz erzeugt werden und erst dann auf ihre grammatikalische Korrektheit überprüft werden ("Generate-and test").

2.Ansatz (Differenzlisten, DCG)

Fig. 11.3: Differenzlisten ("np = S0 - S1")

Nur solche Sublisten werden erzeugt, die überhaupt grammatikalisch richtig sein können. So muss z.B. am Anfang der ganzen Liste eine 'noun phrase' stehen (Fig. 11.3).

s( S0, S) :- 
    np( S0, S1), 
    vp( S1, S). 
np( S0, S) :- 
    d( S0, S1), /* d = determiner */
    n( S1, S).   
np( S0, S) :- 
    n( S0, S). /* n = noun */
np( S0, S) :- 
    name( S0, S). /* proper name */
vp( S0, S) :- 
    v( S0, S). /* v = verb */
vp( S0, S) :- 
    v( S0, S1), 
    np( S1, S).
d( [ D| S], S) :- 
    d_( D).
n( [ N| S], S) :- 
    n_( N).
name( [ N| S], S) :- 
    name_( N).
v( [ V| S], S) :- 
    v_( V).
    
/* dictionary */
d_( the).
d_( a).
n_( man).
n_( book).
name_( john).
v_( reads).

Bedeutung: np( S0, S): "Am Anfang der Liste S0 steht noun phrase; die Restliste ist S"
Aufruf: ?- s([the, man, reads, a, book], []) -> yes
Effizient, mächtig, elegant.

Eine vereinfachte Darstellung, die oft verwendet wird, lässt die Argumente S, S0, S1, … weg:

s -> np, vp
np -> d, np
d -> d_
d_ -> [the] ; [a]
...

Für ein funktionierendes Prolog-Programm muss natürlich die vereinfachte Darstellung entweder von Hand oder durch einen Prolog-Translator (der in vielen kommerziellen Prologs enthalten ist) übersetzt werden.

Erweiterungen:

1) Aufbau vom Syntax Tree (Parse Tree)

(vgl. Proof Tree bei der How-Erklärung von Expertensystemen)

s( S0, S, s( NP, VP)) :- 
    np( S0, S1, NP), 
    vp( S1, S, VP). 
np( S0, S, np( D, NP)) :- 
    d( S0, S1, D),
    n( S1, S, NP).
d( [ D| S], S, d( D)) :- 
    d_( D).
. . .
?- s([the, man, reads, a, book], [], Tree).
 ⇒  Tree = s( np( d( the), n( man)), vp( v( reads), np( d( a), n( book))))

Vereinfachte Darstellung:

s(s( NP, VP)) -> np(NP), vp(VP) 
np(np( D, NP)) -> d(D), np(NP)
d(d( D)) -> d_( D)
. . .

Der Syntaxbaum kann mit einem einfachen Prolog-Programm übersichtlich ausgedruckt werden (Übung):

|-  s
    |-  np
    |   |-  d
    |   |   |-  the
    |   |-  n
    |       |- man
    |-  vp
        |-  v
        |   |- reads
        |-  np
            |-  d
            |   |-  a
            |-  n
                |- book

2) Kontextabhängigkeit

Beispiel: Übereinstimmung singular/singular, plural/plural

s(S0, S, Type) :- 
    np(S0, S1, Type), 
    vp(S1, S, Type).

In der vereinfachten Darstellung:

s(Type) -> np(Type), vp(Type). 
n(Type) -> n_(Type).
v(Type) -> v_(Type).
n_(singular) -> [man]
n_(plural) -> [men]
v_(singular) -> [reads]
v_(plural) -> [read]

11.2.4 Semantik

Die Semantik ist die Bedeutung der natürlichen Sprache im Kontext der realen Welt. In der syntax-basierten Analyse wird die Semantik des ganzen Satzes durch Kombination der Semantik der einzelnen Satzteile gewonnen.

Proper noun: John
Logic:	john
Prolog:	john
Common noun: man
Logic:	(λX) man(X)
Prolog:	X^man(X)
Adjective: big
Logic:	(λX) big(X
Prolog:	X^big(X)
Noun with adj.: big man
Logic:	(λX) [big(X)∧man(X)]
Prolog:	X^(big(X) ∧ man(X))
Intransitive verb: sings
Logic:	(λX) sings(X)
Prolog:	X^sings(X)
Transitive verb: loves
Logic:	(λXλY) loves(X, Y)
Prolog:	X^Y^loves(X, Y
Verb phrase: loves Mary
Logic:	(λX) loves(X, mary)
Prolog:	X^loves(X, mary)
John sings
Logic:	sings(john)
Prolog:	sings(john)
John loves Mary
Logic:	loves(john, mary)
Prolog:	loves(john, mary)
Every man loves a woman
Logic:	∀M(man(M) ⇒ ∃W( woman(W) ∧ loves(M, W))
Prolog:	all(M, man(M), exists(W, woman(W), loves(M,W)))

Constituent	Logic	Prolog
Proper noun: John	john	john
Common noun: man	(λX) man(X)	X^man(X)
Adjective: big	(λX) big(X)	X^big(X)
Noun with adj.: big man	(λX) [big(X)∧man(X)]	X^(big(X) ∧ man(X))
Intransitive verb: sings	(λX) sings(X)	X^sings(X)
Transitive verb: loves	(λXλY) loves(X, Y)	X^Y^loves(X, Y)
Verb phrase: loves Mary	(λX) loves(X, mary)	X^loves(X, mary)
John sings	sings(john)	sings(john)
John loves Mary	loves(john, mary)	loves(john, mary)
Every man loves a woman	∀M(man(M) ⇒ ∃W( woman(W) ∧ loves(M, W))	all(M, man(M), exists(W, woman(W), loves(M,W)))

Die Notation (λX)sings(X) ist ein Lambda-Ausdruck, der das Prädikat sings/1 mit dem Platzhalter X bezeichnet. Er kann in Prolog mit dem rechtsassoziativen Operator ^ dargestellt werden op( 200, xfy, ^).

Die Semantik des Satzes "A man sings" ist ∃ X(man(X) ∧ sings(X)) und wird im Prolog durch den Term exists(X, man(X), sings(X)) repräsentiert. Die Semantik des Satzes "Every man sings" ist ∀X(man(X) ⇒ sings(X)) und wird im Prolog durch den Term all(X, man(X), sings(X)) repräsentiert. Was ist nun die Semantik der beteiligten Satzteile und wie wird aus ihnen die Semantik des Satzes komponiert? Ein plausibler Ansatz, der zum Ziel führt, ist:

sings	sings(X) X ist der Subjekt, der singt
man	man(X) man ist eine Eigenschaft der Individuen X
a	exists(X, Scope, Pred)
every	all(X, Scope, Pred)

Bei der Bildung der Noun Phrase "a man" wird exists(X, Scope, Pred) und man(Y) durch die Unifikation Scope = man(Y) zu exists(X, man(Y), Pred) kombiniert. Damit die Variablen X und Y die gleichen sind (sharen), müssen sie in den obigen Ausdrücken durch die "Lambda-Notation" sichtbar gemacht werden. Auch Scope und Pred müssen sichtbar gemacht werden:

sings	X^sings(X)
man	X^man(X)
a	X^Scope^Pred^ exists(X, Scope, Pred)
a man	X^ Pred^ exists(X, man(X), Pred)
a man sings	exists(X, man(X), sings(X))

Die entsprechende Grammatik ist:

s(S0, S, s(NP, VP), Statement) :- 
    np(S0, S1, NP, Subj^Ass^Statement), 
    vp(S1, S, VP, Subj^Ass). 

np(S0, S, np(D, N), X^Ass^Statement) :- 
    d(S0, S1, D, X^Scope^Ass^Statement), 
    n(S1, S, N, X^Scope).
np(S0, S, np(Name), Sem) :- 
     name( S0, S, Name, Sem). 

vp(S0, S, vp(V, NP), Subj^Statement) :- 
    v( S0, S1, V, Subj^Obj^Pred), 
    np( S1, S, NP, Obj^Pred^Statement).
vp(S0, S, vp(V), Sem) :- v( S0, S, V, Sem).
 
n([N|S], S, n(N), Sem) :- 
	n_(N, Sem).

name([N| S], S, name(N), Sem) :- 
	name_(N, Sem).

v([V|S], S, v(V), Sem) :- 
	v_(V, Sem).

d([D|S], S, d(D), Sem) :- 
	d_(D, Sem).
 
n_(book, X^book(X)).
n_(man, X^man(X)).
n_(woman, X^woman(X)).

v_(love, X^Y^loves(X, Y)).
v_(loves, X^Y^loves(X, Y)).
v_(loved, X^Y^loves(X, Y)).
v_(reads, X^Y^reads(X, Y)).
v_(sing, X^sings(X)).
v_(sings, X^sings(X)).
 
d_(a, X^Scope^Ass^exists(X, Scope, Ass)).
d_(every, X^Scope^Ass^all(X, Scope, Ass)).
d_(the, X^Scope^Ass^the(X, Scope, Ass)).

name_(jack, jack^Ass^Ass).
name_(john, john^Ass^Ass).
name_(mary, mary^Ass^Ass).

Inhalt | Index

←zurück | vorwärts→