Künstliche Intelligenz und Prolog
Copyright © 2020 Jiri Kriz, www.nosco.ch

11Verarbeitung natürlicher Sprachen

Natural Language Processing (NLP), Natural Language Understanding

Natürliche Sprache:

Warum sollte der Computer natürliche Sprache verstehen:

  1. Ergründung natürlicher Sprache als Teil menschlicher Inteligenz (kognitive Psychologie)
  2. menschengerechte Kommunikation mit Computersystemen (angewandte AI)
  3. 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 ?
...un­gramma­tikalische Frage
Fliegen (richtig)
get_value( vogel, fliegt, ja)yes (richtig; wurde so gespeichert)
get_value( vogel, bewegungs­art, 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.

SatzBe­deutungAktion
Please, copy ... copy( f1, f2) Kopiere
$copy ...copy( f1, f2) Kopiere
Dogs chase cats∀ D, C {dog(D), cat(C) ⇒ chase(D, C)}-

Sprache:

  1. Phonologie, Morphologie:
    Aufbau von Wörtern
  2. Syntax:
    charakterisiert korrekt aufgebaute Sätze
    korrekt: The man goes home.
    falsch: The man go haus.
  3. 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)
  4. 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

PatientComputer
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 fatherPlease tell me more about father
i like teasing fatherDoes anyone else in your family like teasing father?
no, only mePlease 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):

11.1.3Semantic Grammar

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

Semantische Grammatik:

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:

Syntax-Baum

Fig 11.1: Syntax-Baum

Nonterminals (Satzteil):

ssentence
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)

  1. Top-down (goal driven, "backward")
    s → np vp → det noun vp → the noun vp → ... → the man reads good books
  2. 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:

Augmented Transition Network

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)

Differenzlisten

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)))
ConstituentLogicProlog
Proper noun: Johnjohnjohn
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 singssings(john)sings(john)
John loves Maryloves(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:

singssings(X)
X ist der Subjekt, der singt
manman(X)
man ist eine Eigenschaft der Individuen X
aexists(X, Scope, Pred)
everyall(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:

singsX^sings(X)
manX^man(X)
aX^Scope^Pred^ exists(X, Scope, Pred)
a manX^ Pred^ exists(X, man(X), Pred)
a man singsexists(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).