Change search
ReferencesLink to record
Permanent link

Direct link
Efficient Calculation of Optimal Decisions in Graphical Models
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Mathematical Sciences.
2012 (English)MasteroppgaveStudent thesis
Abstract [en]

We present a method for finding the optimal decision on Random Variables in a graphical model. Upper and lower bounds on the exact value for each decision are used to reduce the complexity of the algorithm, while we still ensure that the decision chosen actually represents the exact optimal choice. Since the highest lower bound value is also a lower bound on the value of the optimal decision, we rule out any candidate with an upper bound of lower value than the highest lower bound. By this strategy, we try to reduce the number of candidates to a number we can afford to do exact calculations on. We generate five Bayesian Networks with corresponding value functions, and apply our strategy to these. The bounds on the values are obtained by use of an available computer program, where the complexity is controlled by an input constant. We study the number of decisions accepted for different values of this input constant. From the first Network, we learn that the bounds does not work well unless we split the calculations into parts for different groups of the nodes. We observe that this splitting works well on the next three Networks, while the last Network illustrates how the method fails when we add more edges to the graph. We realize that our improved strategy is successful on sparse graphs, while the method is unsuccessful when we increase the density of edges among the nodes.

Place, publisher, year, edition, pages
Institutt for matematiske fag , 2012. , 137 p.
Keyword [no]
ntnudaim:8128, MTFYMA fysikk og matematikk, Industriell matematikk
URN: urn:nbn:no:ntnu:diva-18860Local ID: ntnudaim:8128OAI: diva2:566327
Available from: 2012-11-08 Created: 2012-11-08

Open Access in DiVA

fulltext(2679 kB)140 downloads
File information
File name FULLTEXT01.pdfFile size 2679 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(184 kB)26 downloads
File information
File name COVER01.pdfFile size 184 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Mathematical Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 140 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 30 hits
ReferencesLink to record
Permanent link

Direct link