Dialogové systémy Luděk Bártek Dialogové systémy Modelování uživatele Dialog a strategické hry Luděk Bártek Laboratoř vyhledávání a dialogu, Fakulta Informatiky Masarykovy Univerzity, Brno jaro 2016 >0 0,0 Konečně stavová analýza dialogových systémů Motivace Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry 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. Matematický model dialogu Dialogové systémy ■ Skládá se z ■ Luděk Bártek Konečně stavová analýza dialogových systémů Modelování uživatele Dialog a ■ ■ dvou diskutujících stran, jejich proslovů, které se střídají. strategické hry Aplikace FSA modelů pro --► generování dialogových systémů i. 4 □ ► < r3P ► < -E ► < ^ Pragmatika dialogu Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry Analyzujeme záznam dialogu z pohledu: ■ teorie řeč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í Pragmatika dialogu Příklady Dialogové systémy Pragmatika obsahující modely uživatelů Luděk Bártek Modelování uživatele Dialog a strategické hry Pragmatika obsahující modely uživatelů a prostředí: >0 Q,o Dialog jako Pawlakův informační systém Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry Pawlakův IS S = (X, 7, V, f)\ ■ X - množina objektů IS. ■ T - množina jejich atributů. ■ V - množina hodnot atributů f\XxT^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 Luděk Bártek Modelování uživatele Dialog a strategické hry Mealyho automat M - konečný automat s výstupem M = (Q,X, Y,\,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 Sq - počáteční stav Modelovaní uživatele Poker Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry Karetní hra, kdy hráči sázejí na sílu karet, které drží v ruce. Základní pravidla: Bankéř (rozdávající), rozdá každému hráči 5 karet. 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 nehodia buď dorovnat poslední sázku nebo ji zvýšit. ■ Složit karty. 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 Modelování uživatele Dialog a strategické hry 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 Konečně stavová Atributy stavu hry (množiny As) ■ ASi - moje karty ■ AS2 - celková výše sázky ■ AS3 - důvěra ve vlastní karty ■ AS4. - protihráčovy karty ■ ASs - hráčova strategie Poker Hodnoty atributů stavu hry Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry moje karty - ASi G {bac/, medium, good} celková výše sázky - AS2 G {high, medium, low} důvěra ve vlastní karty - AS3 G {high, medium, low} protihráčovy karty - AS4 G {bad, medium, good} hráčova strategie - AS$ G {careful, risky, bluffing}. Poker Atributy dialogových proslovů (množiny Ax) Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry volba - AXi G {ca//, rise, fold} sebedůvěra proslovu - AX2 G {high, medium, low} důvěryhodnost proslovu - AX3 G {high, medium, low} vzrušení v hlase - AX4 G {high, medium, low} Poker Fragment vnitřních stavů Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry Aplikace FSA modelů pro generování dialogových systémů Stav moje karty celková výše sázky důvěra ve vlastní karty protihráčovy karty hráčova strategie 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 Konečně stavová analýza dialogových systémů Modelování uživatele Aplikace FSA modelů pro generování dialogových systémů Promluva AXľ AX2 AX3 AX4 (volba) (sebedůvěra) (věrohodnost) (vzrušení) raise high low high *2 raise high high low *3 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í Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry Zkušený hráč: ■ stav Si = (průměrné karty, vysoká sázka, střední důvěra ve vlastní karty, očekává průměrné karty protihráče, opatrná strategie), promluva Xi=(příhoz, velkou sebedůvěrou, malou důvěryhodností, velkým vzrušením v hlase): S{S1,X1) = S2,X{Si,X1) = X2 ■ stav S3= (výborné karty, vysoká sázka, střední důvěra ve vlastní karty, očekává průměrné karty protihráče, opatrná strategie), prohluva XI: č(S3, Xi) = S4, A(S3, Xi) = X3 Poker Ukázky dialogových strategií - dokončení Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry Začátečník: ■ stav S5 = (špatné karty, nízká sázka, střední důvěra ve vlastní karty, očekává špatné karty protihráče, riskuje), promluva X4 = (příhoz, velká sebedůvěra, střední věrohodnost, nízké vzrušení) ô(Ss, X4) = S2, A(S5, X4) = X5 ■ stav S7 = (dobré karty, průměrná sázka, střední důvěra ve vlastní karty, očekává průměrné karty protihráče, riskuje), promluva X4=(přihodit, velká sebedůvěra, střední věrohodnost, nízké vzrušení) ô(Sj, X4) — Ss, X(Sj, X4) — Xe Dialog a strategické hry Dialogové systémy Luděk Bártek Modelování uživatele 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)) Strategické hry Vězňovo dilema Dialogové systémy Luděk Bártek Modelování uživatele Dialog a strategické hry 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: Pokud oba vězni mlčí, jsou oba odsouzeni, za jiný, menší zločin, ke kratšímu trestu (např. 2 roky). 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).. 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-holubice Konečně stavová analýza dialogových systémů Modelování uživatele 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 Modelování uživatele Dialog a strategické hry 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 Modelování uživatele Dialog a strategické hry 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í uživatele 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 Luděk Bártek Modelování uživatele Dialog a strategické hry 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 Modelování uživatele Dialog a strategické hry 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 Luděk Bártek Modelování uživatele Dialog a strategické hry Na základě korpusu dialogů lze automaticky generovat dialogový korpus, který danému korpusu ,,vyhovuje". Postup: Vytvoříme korpus metodou Wizard of Oz (pracuje pouze ,,carodej j. Odstraníme konflikty a převedeme korpus na dialogové rozhraní. Kombinovaně vytvoříme nový korpus (,,čaroděj" se snaží maximálně využívat navržené dialogové rozhraní). Odstraníme konflikty a vygenerujeme z korpusu nové dialogové rozhraní. Pokud je rozhraní v pořádku, končíme, jinak pokračujeme krokem 3.