Dialogové systémy
Luděk Bártek
Laboratoř vyhledávání a dialogu, Fakulta Informatiky Masarykovy Univerzity,
Brno
jaro 2011
Konečně stavová analýza dialogových systémů
Motivace
Dialogové systémy
■ Sjednocení přístupu k dialogovým strategiím a uživatelským modelům.
■ Affective computing - práce s emocemi.
■ Kompatibilita s dalšími disciplínami:
■ teorie automatů a formálních jazyků
■ teorie her
■ univerzální algebra
■ .. .
■ Predikce kroků dialogu.
■ Kompatibilita s VoiceXML.
Pragmatika dialogu
Dialogové systémy
Luděk Bártek
■ Analyzujeme záznam dialogu z pohledu:
■ teorie řečových aktů
■ lexikální sémantiky a pragmatiky
■ dynamické sémantiky
■ dynamické epistemické logiky
■ teorie konverzace.
■ Pragmatika může dále zahrnovat:
■ model uživatele/ů
■ model prostředí
	Dialog jako Pawlakův informační systém
Dialogové	
systémy	
Luděk Bártek	■ Pawlakův IS S = (X, T, V, f):
	m X - množina objektů IS.
	■ T - množina jejich atributů.
	■ V - množina hodnot atributů.
	f : X x T ^ V
	m Příklad - dialog na trhu:
	■ Atributy:
	■ navrhovaná cena: -, 1 — 1000
	■ nonverbální postoj: :-), :-, :-(, :->
	■ Možný průběh dialogu: (1000, :-)), (500, :-), (900, :-)),
	(600, :-(), (800,:-), (-,:->), (700, :-(), (700,:-))
	<!►    1 -o^O
	Modelování dialogu Mealyho automat	
Dialogové		
systémy		
Luděk Bártek		
	■ Mealyho automat M - konečný automat s výstupem.	
	■ M = {Q,X, Y,X,sq)	
	■ Q - neprázdná množina stavů	
	■ X - konečná vstupní abeceda	
	■ Y - konečná výstupní abeceda	
	■ A - přechodová funkce:	
	X: QxX^QxY	
		
Modelovaní uživatele
Poker
Dialogové systémy
■ Karetní hra, kdy hráči sázejí na sílu karet, které drží v ruce.
■ Základní pravidla:
Q Bankéř (rozdávající), rozdá každému hráči 5 karet. B Hráči na základě karet, které jim byly rozdány mohou:
■ vsadit na karty určitou částku s případnou výměnou karet, které se jim nehodí a bud' dorovnat poslední sázku nebo ji zvýšit.
■ Složit karty.
Q Jakmile všichni pouze dorovnají poslední navýšenou sázku, popřípadě složí všichni hráči, až na jednoho, hra končia v případě, že zůstalo více jak jeden hráč, potom ten, který má vyšší hodnotu karet v ruce, vyhrává veškeré vsazené peníze. Pokud nesložil pouze jeden hráč, je tento vítězem dané hry.
Poker
pokračování
Dialogové systémy
Luděk Bártek
■ Tato hra má řadu variant.
■ Při použití dobré strategie lze vyhrát i s velmi nízkými kartami:
■ minimalizace neverbálních projevů
■ vhodně zvolená strategie přihazování, která budí zdání, že karty mají velmi vysokou hodnotu
■ vyhnutí se podobné strategii v následujících hrách - nemělo by jít vysledovat společné rysy chování pro danou situaci.
Poker
Konečně stavová analýza ala dialog
Dialogové systémy
Luděk Bártek
■ Atributy stavu hry (množiny As): m ASi - moje karty
■ AS2 - celková výše sázky
■ AS3 - důvěra ve vlastní karty
■ AS4 - protihráčovi karty
■ AS5 - hráčova strategie
Poker
Hodnoty atributů stavu hry
Dialogové systémy
Luděk Bártek
■ moje karty - ASi G {bad, medium, good}
m celková výše sázky - AS2 £ {high, medium, low}
■ důvěra ve vlastní karty - AS3 G {high, medium, low} m protihráčovi karty - AS4 G {bad, medium, good}
m hráčova strategie - AS5 G {careful, risky, bluffing}.
	Poker Atributy dialogových proslovů (množiny Ax)	
Dialogové		
systémy		
Luděk Bártek		
	■ volba - AX\ 6 {call, rise, fold}	
	■ sebedůvěra proslovu - AX2 £ {high, medium, low}	
		1 -00.0
Poker
Fragment vnitřních stavů
Dialogové systémy
Luděk Bártek
Stav	iASi	AS2	As3	ASA	AS5
Si	medium	high	medium	medium	careful
s2	medium	high	high	medium	risky
s3	high	high	medium	medium	risky
s4	high	high	medium	medium	bluffing
s5	bad	low	medium	low	risky
s6	bad	low	low	medium	careful
s7	good	medium	medium	medium	risky
s8	good	medium	low	good	careful
Poker
Fragment promluv dialogu
Dialogové systémy
Luděk Bártek
Promluva		AX2	AX3	AXA
Xl	raise	high	low	high
X2	raise	high	high	low
X3	call	low	high	medium
x4	raise	high	medium	low
*5	fold	low	high	low
*6	call	low	high	medium
Poker Ukázky dialogových strategií						
■ Zkušený hráč:						
		= S2,	■ A(Si.		x2	
<J(S3!		= 54.	A(S3,	=	X3	
■ Začátečník:						
S(S5t	x4)	= S2,	A(S5,	,x4) =	x5	
S(St.,		= 58,	A(S7,	,x4) =		
			4	□ ►   4 (5? *	< 1 ► < š ►	1 -o^o
Dialog a strategické hry
Dialogové systémy
Luděk Bártek
■ Dialog lze považovat za strategickou hrou.
■ Strategická hra obsahuje množinu hráčů.
■ Každý hráč má množinu akcí (strategií).
■ Každý hráč ma preferenční relaci (výplatní funkci (payoff function))
4Ľ3k4l3*4 = k4 = *      -š -O^O
Strategické hry
Vězňovo dilema
■ Strategická hra dvou hráčů.
■ Předpokládá, že každý hráč se stará především o svůj prospěch.
■ Simuluje vyšetřování zločinu, ze kterého jsou podezřelí dva lidé.
■ Pravidla:
Q Pokud oba vězni mlčí, jsou oba odsouzeni, za jiný, menší
zločin, ke kratšímu trestu (např. 2 roky). Q Pokud jeden mlčí a druhý se přizná, ten který se přiznal, je
osvobozen a ten, který mlčel je odsouzen k maximálnímu
trestu (10 let).. Q Pokud se oba přiznají, oba jsou odsouzeni k polovičnímu
trestu (5 let).
■ Vězňovo dilema - jak se zachová parťák?
Přístup jestřáb-hol u bice
Dialogové systémy
Luděk Bártek
	holubice	jestřáb
holubice	5, 5	1, 10
jestřáb	10, 1	0, 0
Strategické hry s podobnou výplatní funkcí
Dialogové systémy
Luděk Bártek
■ Válka pohlaví
■ Manželé preferují společně strávený čas. Co budeme dělat dnes odpoledne? Půjdeme (budeme se dívat) na módní přehlídku nebo na fotbal?
■ Hlava - Orel
■ Dva lidé se sázejí, co padne na minci. Hlava nebo orel?
Iterované strategické hry
Dialogové systémy
Luděk Bártek
■ Hráče necháme opakovaně hrát strategickou hru.
■ Vzniká extenzivní hra s dokonalou informací.
■ Extenzivní hra - opakující se hra.
■ Dokonalá informace - znáte předchozí tahy všech hráčů.
■ Příklady:
■ iterované vězňovo dilema
■ iterovaná hra "Válka pohlaví"
Iterované vězňovo dilema
Strategie
■ Vždy spolupracovat - vždy se přiznat bez ohledu na to, jak se dříve zachoval spoluhráč (naivní mírotvorce).
■ Vždy zradit - vždy zapírat.
■ Tit-for-tat - spolupracovat nebo nespolupracovat, podle toho zda spoluobviněný minule
spolu práčova I / nespol u práčova I.
■ Zlomyslná - spolupracuje, dokud spoluobviněný nezradí. Potom vždy zradí.
■ Mistrust - nejdřív zradí, a potom vždy opakuje tah spoluobviněného.
■ Pavlov - spolupracuje pouze tehdy, pokud si spoluobviněný zvolil stejnou možnost v předchozím kole.
■ Hard Tit-for-tat - spolupracuje, pokud spoluobviněný nezradil v žádném z dvou předchozích kol.
■ Náhodná - spolupracuje s pravděpodobností 0.5.
Iterované prostorové vězňovo dilema
Dialogové systémy
Luděk Bártek
■ Objekty (buňky, jednotlivci, hráči) hrají iterované vězňovo dilema se svými sousedy.
■ Po skončení hry objekty v závislosti na výsledku mění strategii pro další kolo.
■ Chování kolonie strategií je nerozhodnutelný problém.
■ Důkaz - P. Grim 1994.
Aplikace strategických her
Dialogové systémy
Luděk Bártek
■ Ekonomie - chování trhu, zákazníků, . ..
■ Sociologie
■ Psychologie
■ Politika
■ strategická rozhodnutí v zájmu státu. Ekologie
4Ľ3k4l3*4 = k4 = *      -š -O^O
Generovaní dialogových rozhraní z korpusů
Dialogové systémy
■ Na základě korpusu dialogů lze automaticky generovat dialogový korpus, který danému korpusu „vyhovuje".
■ Postup:
Q Vytvoříme korpus metodou Wizard of Oz (pracuje pouze „čaroděj").
B Odstraníme konflikty a převedeme korpus na dialogové rozhraní.
Q Kombinovaně vytvoříme nový korpus („čaroděj" se snaží maximálně využívat navržené dialogové rozhraní).
Q Odstraníme konflikty a vygenerujeme z korpusu nové dialogové rozhraní.
B Pokud je rozhraní v pořádku, končíme, jinak pokračujeme krokem 3.