Referring Expressions Generation

• Motivation

• Definition

• charkteristische Beschreibung

• Kontext-Menge

• potentielle Distraktoren

• Eigenschaft: <Attribut,Wert>

• Exkurs: Grice

• Full Brevity

• Greedy Heuristic

• Local Brevity

• Incremental Algorithm...

vs

Einleitung

?

!

?

2

Phrasen, die Objekte einer Domäne für den menschlichen Benutzer eines NLG-Systems identifizieren.

nach Dale und Reiter (1994)

Charakteristika

• erfüllt referentiellen kommunikativen Zweck

• evoziert keine falschen konversa-tionellen Implikaturen (Grice)

• effizient

• Eigenschaften schließen Distraktoren aus ("Trennschärfe")
• spezielles Attribut für Kopfnomen: type

alle Objekte aus der Kontext-Menge außer der Referent

• definite Nominalphrasen

• referieren auf physische Objekte

• einziger Zweck: Identifikation des Zielobjekts

alle Objekte im gegenwärtigen Aufmerksamkeitsbereich

präzise Beschreibung des Zielobjekts

(und nur dessen, keines anderen aus der Kontext-Menge)

... für einen Algorithmus:

Kriterien...

Ansätze

Vielen Dank für die

Aufmerksamkeit ☺

Gibt es Fragen?

verschiedene Ansätze :

• Full Brevity, Greedy Heuristic, Incremental Algorithm
• unterschiedliche Komplexität

Implementation:

• ad-hoc, graphentheoretisch (versch. Kostenfunktionen)

(nach Dale, Reiter)

• kürzestmögliche Referring Expression (minimale Anzahl an Attributen)

• exhaustive Suche (prüft alle ein-, zwei-,... n-komponentigen Beschreibungen)

• ineffizient, d.h. i.A. keine Algorithmen mit akzeptabler Performanz

• menschlicher Generierung wenig ähnlich

1

Theorie

Algorithmus

Praxis

Schritt 1:

• #Distraktoren == 0? Ja: fertig, nein: …

… Schritt 2:

• iteriere über alle Attribute:

wähle das, welches die meisten

Distraktoren ausschließt

• Schritt 1

Eigenschaften

• einfacher und schneller als FB

• generiert nicht in allen Fällen die kürzestmögliche RE

• verschiedene REs abhängig von Attributreihenfolge in r

• Beispiel

Forderungen

GIVE

• Szene
• Objekte
• Eigenschaften
• (Relationen)
• Position
• Ausrichtung

• keine Verwendung unnötiger Bestandteile

• Local Brevity (keine kürzere RE durch Ersetzung mehrerer vorhandener Eigenschaften durch eine neue möglich)

• Verwendung einfache Attribute

Algorithmus

Abschluss

• starte mit initialer char. Beschreibung

• lässt sich neue Beschreibung durch Anwendung der Forderungen zu erzeugen? ja: iterieren, nein: fertig

... im Detail

Annahmen

• Objekte werden durch <Attribut,Wert>-Paare beschrieben (Eigenschaften)
• jedes Objekt hat type-Attribut (typischerweise als Kopfnomen realisiert)
• Werte sind in einer Taxonomie geordnet (Hyponym-Hyperonym-Relationen)

Algorithmus

Interface

• charakteristische Beschreibung?

nein:

• iteriert durch die Liste der Attribute (absolut vor relativ)
• füge aktuelles Attribut hinzu, wenn es mindestens einen neuen Distraktor ausschließt

ja:

• fertig

• Input: Referent, Kontrast-Menge
• Output: Liste von <Attribut,Wert>-Paaren (semantischer Inhalt der RE)
• Funktionen:

• PreferredAttributes: list (global)

• MoreSpecificValue(o,a,v): str
• BasicLevelValue(o,a): str
• UserKnows(o,<a,v>): boolean

• effizient
• nicht-optimal (redundante Information möglich)
• nah an menschlicher Generierung von REs, daher implizite Beachtung der Maximen

Eigenschaften

Referring Expressions Generation

Eric Hildebrand

Natural Language Generation in Virtual Environments

3

4

Krahmer et al. (2003)

Idee

3.2

• Kontext-Menge ("Szene") als gerichteter Graph m Kantenbeschriftungen

• RE: Teilgraph, der Referenzobjekt eindeutig charakterisiert

• Knoten:Objekte,
• Kanten:Relationen

(Eigenschaften→Schleifen)

Details...

... Algorithmus:

... Kostenfunktion:

• Eingabe: Szenengraph
• Ausgabe: günstigster Teilgraph, der Referenten eindeutig identifiziert
• Beginne mit Knoten für r
• expandiere Graphen, bis eindeutige Beschreibung gefunden ist

• einzig strikte Anforderung: monoton
• z.B: Summe aller Kosten für Knoten und Kanten des Teilgraphen

3.1

Implementierung

3.3

• direkte Interpretation des Algorithmus'
• universeller (Relationen, Eigenschaften)

• Kosten für Kanten entsprechend Beschreibungs-mächtigkeit (umgekehrt proportional zur #Vorkommen)
• Kante hinzufügen, welche die meisten Distraktoren ausschließt

• type-Kanten haben keine Kosten (Basistypen)
• Kanten für Attribute mit absoluten günstiger als für A. mit relativen Werten
• taxonomische is-a-Relationen ebenfalls durch Kostenfunktion modellierbar

... Full Brevity:

... Greedy Heuristics

... Incremental Algorithm:

Anpassungen...

... entspricht set-covering-Problem (NP-schwer)

d4

d3

d2

d1

d4

d3

d2

d1