Dialogové systémy Luděk Bártek Laboratoř vyhledávání a dialogu, Fakulta Informatiky Masarykovy Univerzity, Brno jaro 2014 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. Analyzujeme záznam dialogu z pohledu: ■ teorie rečových aktů ■ řečový akt - čin vykonaný pomocí pomocí jazyka: ■ Sdělení: ,,Už je 9.;" ■ Pragmatika sdělení - Aktuální čas vs. je příliš brzy/pozd a je potřeba něco vykonat. ■ 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 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 V 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,:-)) Modelovaní dialogu Mealyho automat Dialogové systémy Mealyho automat M - konečný automat s výstupem. M = {Q,X, Y, X, s0) m Q - neprázdna 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 moje karty - ASi G {bad, medium, good} celková výše sázky - AS2 £ {high, medium, low} důvěra ve vlastní karty - AS3 G {high, medium, low} protihráčovi karty - AS4 G {bad, medium, good} hráčova strategie - AS5 G {careful, risky, bluffing}. Poker Atributy dialogových proslovů (množiny Ax) Dialogové systémy Luděk Bártek Konečně stavova analýza dialogových systémů ■ volba - AX\ 6 {call, rise, fold} Modelování Dialog a ■ sebedůvěra proslovu - AX2 £ {high, medium, low} strategické hry Aplikace FSA ■ důvěryhodnost proslovu - AX3 6 {high, medium, low} modelů pro generování dialogových systémů ■ vzrušení v hlase - AX4 £ {high, medium, low} Poker Fragment vnitřních stavů Dialogové systémy Stav moje celková důvěra ve protihráčovi hráčova karty výše vlastní karty strategie sázky karty 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 AX-y AX2 AX3 AXA (volba) (sebedůvěra) (věrohodnost) (vzrušení) Xl raise high low high X2 raise high high low X3 call low high medium M raise high medium low X5 fold low high low *6 call low high medium Poker Ukázky dialogových strategií Dialogové systémy Luděk Bártek Konečně stavova ■ Zkušený hráč: analýza dialogových systémů Xi) — ^2, A(Si. x2 Modelování Dialog a strategické hry S(S3, Xi) = S4, A(S3. = X3 Aplikace FSA modelů pro ■ Začátečník: generování dialogových systémů S(S5, x4) = 52, A(S5. ,x4) = x5 S(Sj, = Ss, A(S7. ,x4) = □ ► 4 (5? ► ■ < 1 ► < 1 ► 1 -00.0 Dialog a strategické hry 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 Dialogové systémy 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 Konečně stavová analýza dialogových systémů Modelováni Dialog a strategické hry Aplikace FSA modelů pro generování dialogových systémů holubice jestřáb holubice 5, 5 0, 10 jestřáb 10, 0 2, 2 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 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 Dialogové systémy ■ Vždy spolupracovat - vždy se přiznat bez ohledu na to, Luděk Bártek jak se dříve zachoval spoluhráč (naivní mírotvorce). Konečně ■ Vždy zradit - vždy zapírat. stavová analýza ■ Tit-for-tat - spolupracovat nebo nespolupracovat, podle dialogových systémů toho zda spoluobviněný minule Modelování spolu práčova 1 / nespol u práčova 1. Dialog a strategické hry ■ Zlomyslná - spolupracuje, dokud spoluobviněný nezradí. Aplikace FSA modelů pro Potom vždy zradí. generování dialogových ■ Mistrust - nejdřív zradí, a potom vždy opakuje tah systémů 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 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 Ekonomie - chování trhu, zákazníků, . . Sociologie Psychologie Politika ■ strategická rozhodnutí v zájmu státu. Ekologie 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"). Q 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í. S Pokud je rozhraní v pořádku, končíme, jinak pokračujeme krokem 3.