Guido, 2004 - 2006
Guido was developed as a Software Project at Computer Science Department, Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic under the supervision of Mgr. Marta Vomlelová, Phd. by the following team members:
- Jiøí I¹a
- Viliam Lisý
- Zuzana Reitermanová
- Ondøej Sýkora
The aim of the Guido project is to develop an application for the work with Unconstrained Influence Diagrams (Jensen, Vomlelová - Unconstrained Influence Diagrams, or the same in the Citeseer cache), extension of the Influence Diagrams.
Influence diagrams
The theory of Influence diagrams covers the decisioning under uncertainty. Whenever we deal with the sequence of decisions and observations, that lead to some profit, depending on how we decided and what we observed, and we want to maximize the profit, expected utility, we deal with the task Influence diagrams were designed for.
The theory of Influence digrams is well understood and well covered.
Its disadvantage is, that decisions must be done in the predefined order. This limits the powerfull theory to very simple sequences of decisions.
Unconstrained Influence Diagrams
Unconstrained Influence Diagrams (UID) put no constraint on the order of the decisions. In some cases it may be better to perform the first decision before the second, because the information we obtain after the first decision is done may make us more informed for the second decision. In another situation, however, the same two decisions might be better done in the opposite order - the second first. For exactly the same reason!
Therefore UIDs suggest not only the best decisions, but also the order in which they should be performed. This feature makes it very suitable for problems with multiple decisions performed in parallel or partially in sequence.
The problem of this approach is, that the number of possible orders of decisions grows highly exponentially (factorial, in fact) with the number of decisions. If we add the fact, that one probability table can have millions of items, we may have tens of thousands of such tables, we get the reason, why there is no application capable of the exact problem solution. Although some approximations exist. Except of Guido.
Guido
Guido incorporates some highly advanced methods for the UID problem solving:
- Lazy evaluation: Tables are not multiplied until necessary. Multiplication of tables leads to their exponential growth.
- Compressed tables representation: The fact, that probability tables may contain uniform distribution of probability values or that they may be sparse could be exploited, which leads to the smaller memory representations of the tables.
- Shared substructures: During the calculation some parts of the calculation structures might be shared in different branches of calculation.
- Compact representation of all possible orders of decisions (GS-DAG): Even more effective, than the Viterbi algorithm widely used in computational linguistic. Drastically reduces the representation from the factorial to pure exponential complexity.
Guido is currently the one only known program capable of the exact UID evaluation.
Screenshot
