A comparison of two approaches for solving unconstrained influence diagrams

Kristian S. Ahlmann-Ohlsen, Finn V. Jensen, Thomas Dyhre Nielsen, Ole Pedersen, Marta Vomlelová

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

9 Citationer (Scopus)
408 Downloads (Pure)

Resumé

Udgivelsesdato: JAN
OriginalsprogEngelsk
TidsskriftInternational Journal of Approximate Reasoning
Vol/bind50
Udgave nummer1
Sider (fra-til)153-173
ISSN0888-613X
DOI
StatusUdgivet - 2009

Fingerprint

Influence Diagrams
Decision trees
Specifications
Decision problem
Partial ordering
Modeling Language
Decision tree
Conditioning
Elimination
Efficient Algorithms
Linearly
Specification
Requirements
Framework
Modeling languages

Citer dette

@article{f389dac0683b11dd92a2000ea68e967b,
title = "A comparison of two approaches for solving unconstrained influence diagrams",
abstract = "Influence diagrams and decision trees represent the two most common frameworks for specifying and solving decision problems. As modeling languages, both of these frameworks require that the decision analyst specifies all possible sequences of observations and decisions (in influence diagrams, this requirement corresponds to the constraint that the decisions should be temporarily linearly ordered). Recently, the unconstrained influence diagram was proposed to address this drawback. In this framework, we may have a partial ordering of the decisions, and a solution to the decision problem therefore consists not only of a decision policy for the various decisions, but also of a conditional specification of what to do next. Relative to the complexity of solving an influence diagram, finding a solution to an unconstrained influence diagram may be computationally very demanding w.r.t. both time and space. Hence, there is a need for efficient algorithms that can deal with (and take advantage of) the idiosyncrasies of the language. In this paper we propose two such solution algorithms. One resembles the variable elimination technique from influence diagrams, whereas the other is based on conditioning and supports any-space inference. Finally, we present an empirical comparison of the proposed methods.",
author = "Ahlmann-Ohlsen, {Kristian S.} and Jensen, {Finn V.} and Nielsen, {Thomas Dyhre} and Ole Pedersen and Marta Vomlelov{\'a}",
year = "2009",
doi = "doi:10.1016/j.ijar.2008.08.001",
language = "English",
volume = "50",
pages = "153--173",
journal = "International Journal of Approximate Reasoning",
issn = "0888-613X",
publisher = "Elsevier",
number = "1",

}

A comparison of two approaches for solving unconstrained influence diagrams. / Ahlmann-Ohlsen, Kristian S.; Jensen, Finn V.; Nielsen, Thomas Dyhre; Pedersen, Ole; Vomlelová, Marta.

I: International Journal of Approximate Reasoning, Bind 50, Nr. 1, 2009, s. 153-173.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - A comparison of two approaches for solving unconstrained influence diagrams

AU - Ahlmann-Ohlsen, Kristian S.

AU - Jensen, Finn V.

AU - Nielsen, Thomas Dyhre

AU - Pedersen, Ole

AU - Vomlelová, Marta

PY - 2009

Y1 - 2009

N2 - Influence diagrams and decision trees represent the two most common frameworks for specifying and solving decision problems. As modeling languages, both of these frameworks require that the decision analyst specifies all possible sequences of observations and decisions (in influence diagrams, this requirement corresponds to the constraint that the decisions should be temporarily linearly ordered). Recently, the unconstrained influence diagram was proposed to address this drawback. In this framework, we may have a partial ordering of the decisions, and a solution to the decision problem therefore consists not only of a decision policy for the various decisions, but also of a conditional specification of what to do next. Relative to the complexity of solving an influence diagram, finding a solution to an unconstrained influence diagram may be computationally very demanding w.r.t. both time and space. Hence, there is a need for efficient algorithms that can deal with (and take advantage of) the idiosyncrasies of the language. In this paper we propose two such solution algorithms. One resembles the variable elimination technique from influence diagrams, whereas the other is based on conditioning and supports any-space inference. Finally, we present an empirical comparison of the proposed methods.

AB - Influence diagrams and decision trees represent the two most common frameworks for specifying and solving decision problems. As modeling languages, both of these frameworks require that the decision analyst specifies all possible sequences of observations and decisions (in influence diagrams, this requirement corresponds to the constraint that the decisions should be temporarily linearly ordered). Recently, the unconstrained influence diagram was proposed to address this drawback. In this framework, we may have a partial ordering of the decisions, and a solution to the decision problem therefore consists not only of a decision policy for the various decisions, but also of a conditional specification of what to do next. Relative to the complexity of solving an influence diagram, finding a solution to an unconstrained influence diagram may be computationally very demanding w.r.t. both time and space. Hence, there is a need for efficient algorithms that can deal with (and take advantage of) the idiosyncrasies of the language. In this paper we propose two such solution algorithms. One resembles the variable elimination technique from influence diagrams, whereas the other is based on conditioning and supports any-space inference. Finally, we present an empirical comparison of the proposed methods.

U2 - doi:10.1016/j.ijar.2008.08.001

DO - doi:10.1016/j.ijar.2008.08.001

M3 - Journal article

VL - 50

SP - 153

EP - 173

JO - International Journal of Approximate Reasoning

JF - International Journal of Approximate Reasoning

SN - 0888-613X

IS - 1

ER -