Strategy Representation by Decision Trees with Linear
Classifiers

D 2019

Strategy Representation by Decision Trees with Linear Classifiers

ASHOK, Pranav, Tomáš BRÁZDIL, Krishnendu CHATTERJEE, Jan KŘETÍNSKÝ, Christoph LAMPERT et. al.

Základní údaje

Originální název

Strategy Representation by Decision Trees with Linear Classifiers

Autoři

ASHOK, Pranav (356 Indie), Tomáš BRÁZDIL (203 Česká republika, domácí), Krishnendu CHATTERJEE (356 Indie), Jan KŘETÍNSKÝ (203 Česká republika, garant, domácí), Christoph LAMPERT a Viktor TOMAN (703 Slovensko, domácí)

Vydání

Cham, Quantitative Evaluation of Systems (QEST 2019), od s. 109-128, 20 s. 2019

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00108295

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-30280-1

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-30281-8_7

UT WoS

000679281300007

Klíčová slova anglicky

Strategy Representation; Decision Trees; Linear Classifiers

Štítky

firank_B

Změněno: 27. 4. 2020 23:17, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Graph games and Markov decision processes (MDPs) are standard models in reactive synthesis and verification of probabilistic systems with nondeterminism. The class of omega-regular winning conditions; e.g., safety, reachability, liveness, parity conditions; provides a robust and expressive specification formalism for properties that arise in analysis of reactive systems. The resolutions of nondeterminism in games and MDPs are represented as strategies, and we consider succinct representation of such strategies. The decision-tree data structure from machine learning retains the flavor of decisions of strategies and allows entropy-based minimization to obtain succinct trees. However, in contrast to traditional machine-learning problems where small errors are allowed, for winning strategies in graph games and MDPs no error is allowed, and the decision tree must represent the entire strategy. In this work we propose decision trees with linear classifiers for representation of strategies in graph games and MDPs. We have implemented strategy representation using this data structure and we present experimental results for problems on graph games and MDPs, which show that this new data structure presents a much more efficient strategy representation as compared to standard decision trees.

Návaznosti

GA18-11193S, projekt VaV

Název: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Investor: Grantová agentura ČR, Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Citovat

ASHOK, Pranav, Tomáš BRÁZDIL, Krishnendu CHATTERJEE, Jan KŘETÍNSKÝ, Christoph LAMPERT a Viktor TOMAN. Strategy Representation by Decision Trees with Linear Classifiers. In Quantitative Evaluation of Systems (QEST 2019). Cham: Springer, 2019, s. 109-128. ISBN 978-3-030-30280-1. Dostupné z: https://dx.doi.org/10.1007/978-3-030-30281-8_7.

@inproceedings{1649049,
   author = {Ashok, Pranav and Brázdil, Tomáš and Chatterjee, Krishnendu and Křetínský, Jan and Lampert, Christoph and Toman, Viktor},
   address = {Cham},
   booktitle = {Quantitative Evaluation of Systems (QEST 2019)},
   doi = {http://dx.doi.org/10.1007/978-3-030-30281-8_7},
   keywords = {Strategy Representation; Decision Trees; Linear Classifiers},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-030-30280-1},
   pages = {109-128},
   publisher = {Springer},
   title = {Strategy Representation by Decision Trees with Linear Classifiers},
   year = {2019}
}

TY  - JOUR
ID  - 1649049
AU  - Ashok, Pranav - Brázdil, Tomáš - Chatterjee, Krishnendu - Křetínský, Jan - Lampert, Christoph - Toman, Viktor
PY  - 2019
TI  - Strategy Representation by Decision Trees with Linear Classifiers
PB  - Springer
CY  - Cham
SN  - 9783030302801
KW  - Strategy Representation
KW  - Decision Trees
KW  - Linear Classifiers
N2  - Graph games and Markov decision processes (MDPs) are standard models in reactive synthesis and verification of probabilistic systems with nondeterminism. The class of omega-regular winning conditions; e.g., safety, reachability, liveness, parity conditions; provides a robust and expressive specification formalism for properties that arise in analysis of reactive systems. The resolutions of nondeterminism in games and MDPs are represented as strategies, and we consider succinct representation of such strategies. The decision-tree data structure from machine learning retains the flavor of decisions of strategies and allows entropy-based minimization to obtain succinct trees. However, in contrast to traditional machine-learning problems where small errors are allowed, for winning strategies in graph games and MDPs no error is allowed, and the decision tree must represent the entire strategy. In this work we propose decision trees with linear classifiers for representation of strategies in graph games and MDPs. We have implemented strategy representation using this data structure and we present experimental results for problems on graph games and MDPs, which show that this new data structure presents a much more efficient strategy representation as compared to standard decision trees.
ER  -

ASHOK, Pranav, Tomáš BRÁZDIL, Krishnendu CHATTERJEE, Jan KŘETÍNSKÝ, Christoph LAMPERT a Viktor TOMAN. Strategy Representation by Decision Trees with Linear Classifiers. In \textit{Quantitative Evaluation of Systems (QEST 2019)}. Cham: Springer, 2019, s.~109-128. ISBN~978-3-030-30280-1. Dostupné z: https://dx.doi.org/10.1007/978-3-030-30281-8\_{}7.

Podrobný výpis o publikaci