Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness

Thijs van Ommen; Wouter M. Koolen; Peter D. Grünwald

doi:10.1007/978-3-030-29765-7_28

Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness

Thijs van Ommen, Wouter M. Koolen, Peter D. Grünwald

Sub Algorithmic Data Analysis

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

When decisions must be based on incomplete (coarsened) observations and the coarsening mechanism is unknown, a minimax approach offers the best guarantees on the decision maker’s expected loss. Recent work has derived mathematical conditions characterizing minimax optimal decisions, but also found that computing such decisions is a difficult problem in general. This problem is equivalent to that of maximizing a certain conditional entropy expression. In this work, we present a highly efficient algorithm for the case where the coarsening mechanism can be represented by a tree, whose vertices are outcomes and whose edges are coarse observations.

Original language	English
Title of host publication	Symbolic and Quantitative Approaches to Reasoning with Uncertainty
Subtitle of host publication	15th European Conference, ECSQARU 2019, Belgrade, Serbia, September 18-20, 2019, Proceedings
Editors	Gabriele Kern-Isberner, Zoran Ognjanović
Publisher	Springer
Pages	336-347
Number of pages	12
Edition	1
ISBN (Electronic)	978-3-030-29765-7
ISBN (Print)	978-3-030-29764-0
DOIs	https://doi.org/10.1007/978-3-030-29765-7_28
Publication status	Published - Sept 2019

Publication series

Name	Lecture Notes in Artificial Intelligence
Volume	11726
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

coarse data
incomplete observations
minimax decision making
maximum entropy

Access to Document

10.1007/978-3-030-29765-7_28Licence: Unspecified

Ommen2019_Chapter_EfficientAlgorithmsForMinimaxDFinal published version, 300 KBLicence: Taverne

Cite this

van Ommen, T., Koolen, W. M., & Grünwald, P. D. (2019). Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness. In G. Kern-Isberner, & Z. Ognjanović (Eds.), Symbolic and Quantitative Approaches to Reasoning with Uncertainty: 15th European Conference, ECSQARU 2019, Belgrade, Serbia, September 18-20, 2019, Proceedings (1 ed., pp. 336-347). (Lecture Notes in Artificial Intelligence; Vol. 11726). Springer. https://doi.org/10.1007/978-3-030-29765-7_28

van Ommen, Thijs ; Koolen, Wouter M. ; Grünwald, Peter D. / Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness. Symbolic and Quantitative Approaches to Reasoning with Uncertainty: 15th European Conference, ECSQARU 2019, Belgrade, Serbia, September 18-20, 2019, Proceedings. editor / Gabriele Kern-Isberner ; Zoran Ognjanović. 1. ed. Springer, 2019. pp. 336-347 (Lecture Notes in Artificial Intelligence).

@inproceedings{3375e0011d3b40cb91d425279e2ab73a,

title = "Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness",

abstract = "When decisions must be based on incomplete (coarsened) observations and the coarsening mechanism is unknown, a minimax approach offers the best guarantees on the decision maker{\textquoteright}s expected loss. Recent work has derived mathematical conditions characterizing minimax optimal decisions, but also found that computing such decisions is a difficult problem in general. This problem is equivalent to that of maximizing a certain conditional entropy expression. In this work, we present a highly efficient algorithm for the case where the coarsening mechanism can be represented by a tree, whose vertices are outcomes and whose edges are coarse observations.",

keywords = "coarse data, incomplete observations, minimax decision making, maximum entropy",

author = "{van Ommen}, Thijs and Koolen, {Wouter M.} and Gr{\"u}nwald, {Peter D.}",

year = "2019",

month = sep,

doi = "10.1007/978-3-030-29765-7_28",

language = "English",

isbn = "978-3-030-29764-0",

series = "Lecture Notes in Artificial Intelligence",

publisher = "Springer",

pages = "336--347",

editor = "Gabriele Kern-Isberner and Zoran Ognjanovi{\'c}",

booktitle = "Symbolic and Quantitative Approaches to Reasoning with Uncertainty",

edition = "1",

}

van Ommen, T, Koolen, WM & Grünwald, PD 2019, Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness. in G Kern-Isberner & Z Ognjanović (eds), Symbolic and Quantitative Approaches to Reasoning with Uncertainty: 15th European Conference, ECSQARU 2019, Belgrade, Serbia, September 18-20, 2019, Proceedings. 1 edn, Lecture Notes in Artificial Intelligence, vol. 11726, Springer, pp. 336-347. https://doi.org/10.1007/978-3-030-29765-7_28

Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness. / van Ommen, Thijs; Koolen, Wouter M.; Grünwald, Peter D.
Symbolic and Quantitative Approaches to Reasoning with Uncertainty: 15th European Conference, ECSQARU 2019, Belgrade, Serbia, September 18-20, 2019, Proceedings. ed. / Gabriele Kern-Isberner; Zoran Ognjanović. 1. ed. Springer, 2019. p. 336-347 (Lecture Notes in Artificial Intelligence; Vol. 11726).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness

AU - van Ommen, Thijs

AU - Koolen, Wouter M.

AU - Grünwald, Peter D.

PY - 2019/9

Y1 - 2019/9

N2 - When decisions must be based on incomplete (coarsened) observations and the coarsening mechanism is unknown, a minimax approach offers the best guarantees on the decision maker’s expected loss. Recent work has derived mathematical conditions characterizing minimax optimal decisions, but also found that computing such decisions is a difficult problem in general. This problem is equivalent to that of maximizing a certain conditional entropy expression. In this work, we present a highly efficient algorithm for the case where the coarsening mechanism can be represented by a tree, whose vertices are outcomes and whose edges are coarse observations.

AB - When decisions must be based on incomplete (coarsened) observations and the coarsening mechanism is unknown, a minimax approach offers the best guarantees on the decision maker’s expected loss. Recent work has derived mathematical conditions characterizing minimax optimal decisions, but also found that computing such decisions is a difficult problem in general. This problem is equivalent to that of maximizing a certain conditional entropy expression. In this work, we present a highly efficient algorithm for the case where the coarsening mechanism can be represented by a tree, whose vertices are outcomes and whose edges are coarse observations.

KW - coarse data

KW - incomplete observations

KW - minimax decision making

KW - maximum entropy

U2 - 10.1007/978-3-030-29765-7_28

DO - 10.1007/978-3-030-29765-7_28

M3 - Conference contribution

SN - 978-3-030-29764-0

T3 - Lecture Notes in Artificial Intelligence

SP - 336

EP - 347

BT - Symbolic and Quantitative Approaches to Reasoning with Uncertainty

A2 - Kern-Isberner, Gabriele

A2 - Ognjanović, Zoran

PB - Springer

ER -

van Ommen T, Koolen WM, Grünwald PD. Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness. In Kern-Isberner G, Ognjanović Z, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty: 15th European Conference, ECSQARU 2019, Belgrade, Serbia, September 18-20, 2019, Proceedings. 1 ed. Springer. 2019. p. 336-347. (Lecture Notes in Artificial Intelligence). doi: 10.1007/978-3-030-29765-7_28

Efficient Algorithms for Minimax Decisions under Tree-Structured Incompleteness

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this