Zusammenfassung Wir stellen ein abstraktes Modell zur Informationsu¨bertragung per Dialog vor. Dieses Modell erweitert das Grundmodell eines Kommunikationssystems von Shannon um die Mo¨glichkeit der Nachfrage innerhalb einer Informationsu¨bertragung. Fu¨r die Modellierung von Information und Informationsbestandteilen fu¨hren wir Merkmal-Werte-Relationen ein. Die Steuerung des Informationsflusses repra¨sentieren wir durch ein farbiges Petrinetz. Hierbei konzentrieren wir uns auf einen Mensch-Maschine-Dialog und die Modellierung der Funktionalita¨t der Maschine. Eine zuku¨nftige industrielle Anwendung liegt im Bereich von Dialogsystemen zur Sprachverarbeitung.
2. die Steuerung des Informationsflusses durch ein farbiges Petrinetz.
Der erste Aspekt erlaubt es, bei der Repra¨sentation von Information mo¨gliche
Kanalsto¨rungen und Mißversta¨ndnisse angemessen zu beru¨cksichtigen, und geht damit
u¨ber das verbreitete Modell semantic slots [
In diesem Abschnitt wird ein abstraktes Modell zur Informationsu¨bertragung per Dialog vorgestellt. Da es mo¨glich ist, dass u¨bertragene Information nicht genau verstanden wird, kann mit einer Nachfrage reagiert werden. Dabei wird eine Erwartung daru¨ber generiert, was der Dialogpartner inhaltlich auf die Nachfrage antworten ko¨nnte. Zur Modellierung von Informationsbestandteilen fu¨hren wir sog. Merkmal-Werte-Relationen (MWRen) ein. Um einerseits die Erwartung an den Inhalt u¨bertragener Information und andererseits die Sicherheit mit der Information verstanden wurde ausdru¨cken zu ko¨nnen, ko¨nnen MWRen gewichtet werden. Zur Modellierung des Informationsflusses im Dialog verwenden wir ein farbiges Petrinetz. Im Vergleich zu (bisher u¨berwiegend verwendeten) Automaten hat das Petrinetz Vorteile in Ma¨chtigkeit, Kompaktheit, Lesbarkeit, Wartbarkeit und Erweiterbarkeit.
Es handelt sich um einen bisher noch vollsta¨ndig abstrakten Entwurf als ersten Schritt einer Top-Down-Modellierung. Wir interpretieren dabei die Transitionen als abstrakte Funktionen. Dazu definieren wir formal, was die Eingabe- und Ausgabeparameter dieser Funktionen sind (diese werden als farbige Marken in den Stellen modelliert), interpretieren die Ein- und Ausgabewerte der Funktionen und beschreiben deren grundsa¨tzliche funktionale Abha¨ngigkeit. Die Implementierung derselben, z.B. durch Transitionsverfeinerung, ist Gegenstand weiterer Forschungsarbeiten.
Im folgenden Abschnitt werden die grundlegenden Notationen eingefu¨hrt. Im Anschluss daran definieren und beschreiben wir den Begriff der Merkmal-Werte-Relation, der fu¨r die Systembeschreibung im dritten Abschnitt von zentraler Bedeutung sein wird. 2.1
Wir beginnen mit einigen grundlegenden mathematischen Notationen. Mit N bezeichnen wir die Menge der nicht-negativen ganzen Zahlen, mit R die Menge der reellen Zahlen und mit R+ die Menge der nicht-negativen reellen Zahlen. Ein Wahrscheinlichkeitsmaß ¼ auf einer endlichen Menge A ist eine Abbildung ¼ : A ! [0; 1] mit Pa2A ¼(a) = 1. Fu¨r eine endliche Menge A bezeichnet A+ wie u¨blich die Menge aller Worte u¨ber A. Eine Multi-Menge u¨ber einer Menge A ist eine Funktion m : A ! N. Fu¨r ein a 2 A bezeichnet m(a) die Anzahl von a’s in m. Fu¨r eine bina¨re Relation R µ A £ A u¨ber einer Menge A ist R+ der transitive Abschluss von R. Eine bina¨re Relation R u¨ber A heißt linkstotal, falls fu¨r jedes a 2 A ein b 2 A existiert mit (a; b) 2 R. Ein gerichteter Graph G ist ein Paar G = (A; !), wobei A eine endliche Menge von Knoten und !µ A£ A die Menge der Kanten ist. Wie u¨blich schreiben wir auch a ! b fu¨r (a; b) 2!. Fu¨r a 2 A bezeichnet ²a = fa0 2 A j a0 ! ag den Vorbereich und a² = fa0 2 A j a ! a0g den Nachbereich von a. Eine endliche Folge von Knoten a0 : : : an (n 2 N) mit ai¡1 ! ai ist ein Pfad von a0 nach an. Ein Pfad a0 : : : an mit a0 = an ist ein Zyklus. Eine partielle Ordnung ist ein gerichteter Graph (A; <), wobei < irreflexiv und transitiv ist. Eine Relation R u¨ber einer Menge A la¨sst sich als gerichteter Graph (A; R) auffassen und umgekehrt. Bekanntlich ist eine Relation R genau dann zyklenfrei, wenn R+ irreflexiv, d.h. eine partielle Ordnung, ist.
Zur Modellierung der Dialogsteuerung verwenden wir farbige Petrinetze [
Wir werden Informationsbestandteile durch Marken geeigneter Farben modellieren.
Grundsa¨tzlich eignet sich das vorgestellte Modell ganz allgemein zur Beschreibung eines Dialogs zwischen Systemen, zwischen Menschen oder auch zwischen Mensch und Maschine, also generelle Informationsu¨bertragung nicht nur per Sprache. O.B.d.A. wollen wir uns im Folgenden einen Mensch-Maschine-Dialog vorstellen, da sich dies vorteilhaft auf die Wahl geeigneter Abstraktionen auswirkt.
Im durchlaufenden Beispiel betrachten wir ein Mensch-Maschine-Dialogsystem, in dem der Benutzer des Systems einen Anruf mittels Spracheingabe ta¨tigen mo¨chte. Hierbei kann er die Nummer direkt angeben (falls er sie weiß), also z.B. “555666 anrufen” sagen. Oder er kann ihm bekannte Informationen zum gewu¨nschten Anrufpartner, wie Vorname, Nachname und Ort, angeben. Er kann also sagen “Maja anrufen”. Zur Un3 man sagt auch: die Variablen werden an Werte des entsprechenden Datentyps gebunden terstu¨tzung des Systems existiert ein, in einer Datenbank gespeichertes, Telefonbuch mit Eintra¨gen, die solche Informationen zur Verfu¨gung stellen (Abb. 2).
Erste Aufgabe des Systems ist, u¨bertragene Informationen zu verstehen. U¨blicherweise wird eine Information (oder ein Informationsbestandteil) mit einer bestimmten Wahrscheinlichkeit verstanden. Kann der gewu¨nschte Anrufpartner noch nicht mit ausreichender Sicherheit identifi- Abbildung 2. Die Telefondatenbank des ziert werden, wird das System weite- Sprachdialogsystems re spezifische Informationen erfragen.
So ist es beispielsweise mo¨glich, dass mit hoher Wahrscheinlichkeit ein bestimmter Nachname verstanden wurde, aber noch mehrere Personen mit diesem Nachnamen im Telefonbuch existieren. Diese ko¨nnten sich bzgl. des Wohnortes oder des Vornamens (oder beidem) unterscheiden lassen. Informationen werden so lange vom System “aufgesammelt” und “kombiniert”, bis der gewu¨nschte Anrufpartner mit ausreichender Sicherheit feststeht.
Dieser Beschreibung zufolge ko¨nnen Informationen also verschiedenen Merkmalen wie Vorname, Nachname und Ort zugeordnet werden. Diese nennen wir Werte. Die Menge der Merkmale kann hierbei strukturiert sein, z.B. lassen sich Vor- und Nachname zum Merkmal Name zusammenfassen. Formal werden wir Informationen in sog. Merkmal-Werte-Relationen darstellen.
Definition 1 (Merkmal-Werte-Relation). Gegeben seien zwei disjunkte endliche Mengen M (Merkmalmenge) und A (Menge atomarer Werte). Eine Merkmal-Werte-Relation (MWR) u¨ber M und A ist eine linkstotale, zyklenfreie Relation R ½ M £ (M [ A).
Eine gewichtete MWR ist ein Paar (R; ¼) bestehend aus einer MWR R und einer Menge ¼ = f¼m j m 2 M g von Gewichten ¼m 2 R+ auf den nicht-leeren Wertemengen W (m) = fw 2 M [ A j (m; w) 2 Rg (d.h. ¼m : W (m) ! R+). Handelt es sich bei ¼m um Wahrscheinlichkeitsmasse, so spricht man von einer stochastischen MWR.
Die MWR bzgl. eines Merkmals m notieren wir als Rm := Rjfmg£(M[A).
Zur Illustration der Zyklenfreiheit betrachten wir das Merkmal Ziffernfolge. U¨ blicherweise ist eine Ziffernfolge ein Element der unendlichen Menge f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g+, die mit Hilfe geeigneter Rekursionen dargestellt werden kann (Abb. 3 links oben). Allerdings sind in einer speziellen Anwendung nur endlich viele Ziffernfolgen als Werte relevant, z.B. besitzen interne Telefonnummern meist eine vorgegebene Stellenzahl. Deshalb verzichten wir durch die Forderung der Zyklenfreiheit auf die Mo¨glichkeit der Rekursion4, was in unserer Situation einige Vorteile mit sich bringt.
Eine MWR hat, als Graph betrachtet, nicht notwendigerweise eine Baumstruktur (Abb. 3, rechts oben und links unten), dennoch kann man von Wurzeln (Merkmale, die nicht als Werte auftreten) und Bla¨ttern (atomare Werte, die tatsa¨chlich als Werte auftre4 In unserem Kontext ko¨nnte z.B. das Merkmal m = Ziffernfolge als Wertemenge W (m) die
Menge der internen Telefonnummern haben. ten) sprechen. Falls nur eine Wurzel5 vorhanden ist (Abb. 3, unten) und es sich um eine stochastische MWR handelt, kann man aus den Wahrscheinlichkeitsmassen f¼mgm2M eindeutig ein Wahrscheinlichkeitsmaß ¼R auf der Menge der Bla¨tter konstruieren, und zwar ist fu¨r ein Blatt b 2 A seine Wahrscheinlichkeit ¼R(b) die Summe der Pfadwahrscheinlichkeiten der Pfade von der Wurzel zum Blatt b. Hierbei erha¨lt man eine Pfadwahrscheinlichkeit durch Multiplikation der Wahrscheinlichkeiten entlang des Pfades. Falls die MWR eine Baumstruktur hat (Abb. 3, rechts unten), ko¨nnen aus einem Wahrscheinlichkeitsmaß ¼R auf den Bla¨ttern auch umgekehrt die Wahrscheinlichkeitsmasse f¼mgm2M berechnet werden.
Die in Abbildung 3 rechts unten dargestellte MWR benutzen wir in unserem durchlaufenden Beispiel eines Dialogs zur Anbahnung eines Anrufs zur Modellierung von Informationsbestandteilen. Bla¨tter, die vom Merkmal Datenbank aus erreichbar sind, entsprechen grundsa¨tzlich genau Datenbankeintra¨gen (vgl. Abb. 2). Die hier gezeigte MWR hat bereits Gewichte, die wir aber spa¨ter erkla¨ren werden.
Abbildung 3. Zyklenfreiheit einer MWR und verschiedene Erscheinungsformen von MerkmalWerte-Relationen. 2.3
In diesem Abschnitt beschreiben wir das durch das Netz in Bild 4 modellierte Dialogsystem. Dazu bezeichnet M die Menge aller Merkmale und A die Menge aller atomaren Werte. Die Transitionen stellen bis dato abstrakte Funktionen dar, deren Ein- und Ausgabedaten durch Marken in den Stellen p1; : : : ; p6 repra¨sentiert werden. Die durch die Stellen p3; p4; p5 modellierten Daten repra¨sentieren hierbei gewichtete MWRen u¨ber M 0 und A0 fu¨r geeignete Mengen M 0 µ M und A0 µ A. Dabei betrachten 5 Gibt es in der MWR genau ein Merkmal, das nicht als Wert vorkommt, so bezeichnen wir dieses Merkmal als “Superwurzel”. wir o.B.d.A. nur MWRen mit Baumstruktur. Wir stellen eine solche gewichtete MWR (R; f¼mgm2M0 ) durch die Menge f(Rm; ¼m) j m 2 M 0g dar (Abb. 6). Eine Marke entspricht dann einem konkreten Paar (Rm; ¼m). Die Stellen p3; p4; p5 sind also mit der Farbmenge C = f(Rm; ¼m) j m 2 M g beschriftet. Die Stellen p1; p2; p6 haben einfachere Datenstrukturen, welche von der betrachteten Anwendung abha¨ngen.
Wie bereits erwa¨hnt, betrachten wir einen MenschMaschine-Dialog. Wir konzentrieren uns dabei auf die Modellierung der Funktionalita¨t der Maschine. Im dargestellten Netz beschreibt die graue Stelle Informationseingabe Funktionalita¨t des Senders (also des Menschen), wa¨hrend das restliche Netz die Funktionalita¨t des Abbildung 4. Abstraktes Petrinetz zur InformatiEmpfa¨ngers (also der Maschi- onsu¨bertragung per Dialog. ne) repra¨sentiert. Ziel ist es, die durch die Informationseingabe generierte Information in p2 so zu u¨bertragen, dass der Empfa¨nger diese in p6 erha¨lt. Dafu¨r ist es notwendig den Zustand in p5 so zu vera¨ndern, dass die Informationsu¨bertragung abgeschlossen werden kann. Um diesen Vorgang zu verstehen, werden wir im Folgenden jede Transition mit Ein- und Ausgaben in Struktur beschreiben und interpretieren. Wir verifizieren dies anhand des durchlaufenden Beispiels eines Dialogs zur Anbahnung eines Anrufs.
Wir beginnen bei der Informationsanforderung.6 Als Eingabe dieser Transition dienen Marken aus p5. Die Stelle p5 beinhaltet zwei voneinander unabha¨ngige gewichtete MWRen. Die eine MWR (RIS ) beschreibt den aktuellen Informationsstatus des Empfa¨ngers durch Gewichtung gi(Gu¨te) von bereits erkannten Informationsbestandteilen i. Die andere MWR RbI repra¨sentiert die noch beno¨tigten Informationsbestandteile zur Vervollsta¨ndigung der Informationsu¨bertragung. Je gro¨ßer das Gewicht eines Merkmals aus RbI ist, desto dringender wird diese Information beno¨tigt, um die Informationsu¨bertragung erfolgreich abzuschließen. RbI dient als Eingabe der Informationsanforderung, d.h. die Kantenbeschriftung ist derart, dass genau die den Merkmalen von RbI entsprechenden Marken konsumiert werden.7 Auf der Basis von RbI wird eine entsprechende Informationsanfrage (an den Sender) in p1 generiert (z.B. repra¨sentiert durch einen String). Diese Anfrage ist mit einer gewissen Erwartung an die na¨chste Informationseingabe durch den Sender verbunden. Grundsa¨tzlich ko¨nnen Informationen nur dann verstanden werden, wenn eine gewisse Erwartung an den Inhalt der u¨bertragenen Information existiert.8 Eine solche Erwartung modellieren wir durch eine stocha6 Die Informationsu¨bermittlung mit der Nachfrage beginnen zu lassen widerspricht zwar dem Shannonschen Kommunikationsgedanken, aber diese Transition eignet sich am Besten zur schrittweisen Beschreibung des Systems. Dies la¨sst sich aber ohne weiteres rechtfertigen, indem man die initiale Nachfrage als Kommunaktionsero¨ffnung interpretiert. 7 In dieser Arbeit verzichten auf die formale Angabe von Kantenbeschriftungen. 8 Dies ist sowohl beim Menschen als auch z.B. in existierenden Sprachdialogsystemen der Fall. stische MWR mit Superwurzel REH , die wir Erwartungshorizont nennen. Die zu den Merkmalen von REH geho¨renden Marken werden in p3 generiert.
Abbildung 5. Links: RIS - hier ist noch nichts erkannt worden. Rechts: RbI - hier wird im Beispiel die Information als am notwendigsten eingestuft, welche die meisten (lautlichen) Unterschiede liefert.
Eine Analogie zur Informationsanforderung ist in unserem Beispiel der “Prompt” (Abb. 7). Im ersten Schritt entspricht RbI einer Standardeinstellung und RIS ist “leer”, i.e. es ist gi = 0 fu¨r alle i (Abb. 5). Aufgrund dieser Information wird der Benutzer (visuell, akustisch, textuell,...) aufgefordert den Namen des Teilnehmers zu nennen (p1) und die entsprechende Erwartungshaltung (Erwartungshorizont in p3) wird generiert (Abb. 6 und 3 rechts unten), wobei aber geringfu¨gig beru¨cksichtigt bleibt, dass der Benutzer den Anrufvorgang abbrechen oder die Nummer direkt angeben ko¨nnte. Der Ort wird nicht beru¨cksichtigt, da ¼Datenbank(Ort) = 0. In p3 befinden sich jetzt also die Marken (RErwartung, ¼Erwartung), (RAbbruch, ¼Abbruch), (RDirekteingabe, ¼Direkteingabe), (RDatenbank, ¼Datenbank), (RName, ¼Name), (RV orname, ¼V orname) und (RNachname, ¼Nachname).
Aufgrund der Informationsanfrage in p1 liefert der Sender (Informationseingabe) eine Information in p2 (z.B. in Form einer Lautfolge oder eines Strings). In unserem Beispiel antwortet der Mensch mit “Maja” (Abb. 8).
Die Informationsverarbeitung besitzt eine eingehende Information aus p2 sowie den Erwartungshorizont REH aus p3 als Eingabe. Die Informationsverarbeitung ordnet in Verbindung mit REH die eingehende Information einem Merkmal zu. REH wird anschließend wieder unvera¨ndert in p3 zuru¨ckgelegt. Die Ausgabe in p4 ist strukturell diesselbe stochastische MWR mit Superwurzel, die wir hier “Ergebnishorizont” RErg nennen, allerdings nun mit anderen Gewichten. Die Wahrscheinlichkeitsverteilung auf den Bla¨ttern von RErg repra¨sentiert das Erkennergebnis.
Der Erkenner (Abb. 9 links) erha¨lt also die Information “Maja” als Sprachsignal. Gema¨ß des Erwartungshorizonts in p3 wird dieses Signal als Name identifiziert, allerdings kann aufgrund der Lauta¨hnlichkeit nicht festgestellt werden, ob nun tatsa¨chlich der Vorname “Maja” oder der Nachname “Meier” gemeint war. Sicher ist aber, dass es sich weder um eine Ziffernfolge (also Direkteingabe der Telefonnummer) noch um den Befehl “Abbruch” handelt. Diese Information befindet sich nun als Ergebnishorizont in p4 (Abb. 9 rechts).
Die Stellen p3, p4 und p5 liefern nun die Eingabeparameter fu¨r die Informationsdatenbank. REH und RErg bilden in Kombination die Information nach der in der Datenbank gesucht werden soll. RIS wird mit den Suchergebnissen aktualisiert und in p5 zuru¨ckgelegt. Sollte das Suchergebnis nicht eindeutig sein, wird u¨ber die Informationsdatenbank eine MWR RbI in p5 generiert, welche die noch beno¨tigten Informationen fu¨r den Abschluss der Informationsu¨bertragung repra¨sentiert.
Nachdem der Erkenner mit einer hohen Wahrscheinlichkeit die Erwartung des nachgefragten Namens besta¨tigt hat, wird nun also in der Datenbank in den Vornamen nach “Maja” und in den Nachnamen nach “Meier” gesucht (bzw. nach Eintra¨gen in Vor- und Nachname, die ausgesprochen der erkannten Lautfolge entsprechen)(Abb. 10). Beides existiert in der Datenbank und wird als Ergebnis in RIS gespeichert, indem die Gleichverteilung der Gewichte durch die entsprechende Erkenngu¨te ersetzt werden. Leider ist die Suche daher nicht eindeutig und es erfolgt eine Auswertung, die das Merkmal “Ort” als hochgradig identifizierend einstuft und diese Information in RbI eintra¨gt (sehr hohe Gewichtung von “Ort”, sehr geringe Gewichtung von “Name”).
In p5 befinden sich jetzt also aktualisierte MWRen RIS und RbI. Sofern der Informationsstatus vollsta¨ndig ist, kann die Informationsu¨bertragung abgeschlossen werden und die aktuelle Information, in Form der Marken RIS wird an p6 u¨bertragen. Falls es sich allerdings um unvollsta¨ndige Informationsbestandteile handelt, beginnt das System den eben erkla¨rten Zyklus von vorne, wobei durch den Prompt auf Basis der gerade aktualisierten MWR RbI wieder ein vollkommen neuer Erwartungshorizont erstellt wird.
Das Ende des ersten Durchlaufs in unserem Beispiel liefert uns die Information, dass der gewu¨nschte Teilnehmer entweder den Vornamen “Maja” oder den Nachnamen “Meier” besitzt.9 Diese Information ist nicht eindeutig und ermo¨glicht keinen Abschluss des Tasks. In diesem Fall wird also auf Basis von RbI ein neuer Zyklus gestartet. Der Prompt generiert einen neuen Erwartungshorizont, welcher einen Ort als Erwartung widerspiegelt, worauf der Anrufer ihm “Sidney” nennt. Ha¨tten wir nun keinen Erwartungshorizont, wu¨rde der Erkenner sowohl den Teilnehmer “Sidney Meyer” aus “Berlin” als auch “Maja Brandl” aus “Sydney” fu¨r mo¨glich halten. Das Ergebnis wird durch den Erwartungshorizont relativiert und wir erhalten nach zwei Schritten “Maja Brandl” aus “Sidney” als eindeutig indentifizierten Anrufpartner und sind in der Lage den Task abzuschließen. 3
Ziel ist es, dieses abstrakte Modell in die Realita¨t umzusetzen und die Transitionen zu implementieren. Nach Mo¨glichkeit wollen wir hierfu¨r weiter farbige Petrinetze verwenden. Als na¨chsten Schritt soll das vorgestellte Modell komplett mit Kanten- und evtl. Transitionbeschriftungen formalisiert werden.
Literatur Zur Illustration stellen wir hier einige erga¨nzende Bilder zur Verfu¨gung.
Abbildung 6. Jeder Kreis entspricht einer Marke (Rm, ¼m) in p3 in Abbildung 7 Abbildung 7. Der Prompt generiert aufgrund von RbI aus p5 eine Anfrage in p1 nach dem Namen und einen damit verbundenen Erwartungshorizont in p3.
Abbildung 8. Der Teilnehmer antwortet auf den Prompt mit “Maja” Abbildung 9. p2 und p3 dienen als Eingabe fu¨r den Erkenner. Dieser kann die Lautfolge “Maja” dem Merkmal “Name” zuordnen. “Abbruch” und “Direkteingabe” sind ausgeschlossen und deren Bla¨tter werden im Ergebnishorizont in p4 nicht beru¨cksichtigt.
Abbildung 10. Die Datenbank erha¨lt den Erwartungs- und Ergebnishorizont, sowie den Informationsstatus. Aufgrund dessen wird der Informationsstatus aktualisiert, sowie ggf. noch die beno¨tigten Informationen generiert.