Abstract
In many domains where experts are the main source of knowledge, e.g., in reliability and risk management, a framework well suited for modeling, maintenance and exploitation of complex probabilistic systems is essential. In these domains, models usually define closed-world systems and result from the aggregation of multiple patterns repeated many times. Object Oriented-based Frameworks (OOF) such as Probabilistic Relational Models thus offer an effective way to represent such systems. OOFs define patterns as classes and substitute large Bayesian networks (BN) by graphs of instances of these classes. In this framework, Structured Inference avoids many computation redundancies by exploiting class knowledge, hence reducing BN inference times by orders of magnitude. However, to keep modeling and maintenance costs low, OOF classes often encode only generic situations. More complex situations, even those repeated many times, are only represented by combinations of instances. In this paper, we propose to determine such combination patterns and exploit them as classes to speed-up Structured Inference. We prove that determining an optimal set of patterns is NP-hard. We also provide an efficient algorithm to approximate this set and show numerical experiments that highlight its practical efficiency.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bangsø, O.: Object Oriented Bayesian Networks. Ph.D. thesis. Aalborg University (March 2004)
Bangsø, O., Sønderberg-Madsen, N., Jensen, F.: A bn framework for the construction of virtual agents with human-like behaviour. In: Proc. of PGM 2006 (2006)
Bangsø, O., Wuillemin, P.H.: Top-down construction and repetitive structures representation in Bayesian networks. In: Proc. of FLAIRS 2000, pp. 282–286 (2000)
Dechter, R.: Bucket elimination: A unifying framework for reasoning. Artificial Intelligence 113, 41–85 (1999)
Friedman, N., Getoor, L., Koller, D., Pfeffer, A.: Learning probabilistic relational models. In: Proc. of IJCAI 1999 (1999)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Getoor, L., Friedman, N., Koller, D., Pfeffer, A., Taskar, B.: Probabilistic relational models. In: Getoor, L., Taskar, B. (eds.) An Introduction to Statistical Relational Learning. ch. 5. MIT Press, Cambridge (2007)
Getoor, L., Koller, D., Taskar, B., Friedman, N.: Learning probabilistic relational models with structural uncertainty. In: ICML 2000 Workshop on Attribute-Value and Relational Learning: Crossing the Boundaries (2000)
Halldórsson, M.: Approximations of weighted independent set and hereditary subset problems. Journal of Graph Algorithms and Applications (2000)
Heckerman, D., Meek, C., Koller, D.: Probabilistic models for relational data. Tech. rep., WA: Microsoft Corporation, Redmond (2004)
Ide, J.S., Cozman, F.G., Ramos, F.T.: Generating random Bayesian networks with constraints on induced width. In: Proc. of ECAI 2004, pp. 323–327 (2004)
Inokuchi, A., Washio, T., Motoda, H.: A general framework for mining frequent subgraphs from labeled graphs. Fundamenta Informaticae (2005)
Jaeger, M.: Relational Bayesian networks. In: Proc. of UAI 1997 (1997)
Kersting, K., Raedt, L.D.: Bayesian logic programs. Technical report no. 151, Institute for Computer Science, University of Freiburg, Germany (April 2001)
Koller, D., Pfeffer, A.: Object-oriented Bayesian networks. In: Proc. of AAAI 1997, pp. 302–313 (1997)
Kuramochi, M., Karypis, G.: Frequent subgraph discovery. In: Proc. of ICDM 2001 (2001)
Madsen, A., Jensen, F.: LAZY propagation: A junction tree inference algorithm based on lazy inference. Artificial Intelligence 113(1–2), 203–245 (1999)
Mahoney, S., Laskey, K.: Network engineering for complex belief networks. In: Proc. of UAI 1996 (1996)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco (1988)
Pfeffer, A., Koller, D., Milch, B., Takusagawa, K.: SPOOK: A system for probabilistic object-oriented knowledge representation. In: Proc. of UAI 1999 (1999)
Pfeffer, A.: Probabilistic Reasoning for Complex Systems. Ph.D. thesis. Stanford University (2000)
Rose, D., Lueker, G., Tarjan, R.: Algorithmic aspects of vertex elimination on graphs. SIAM J. on Computing 5, 266–283 (1976)
Rose, D.: Triangulated graphs and the elimination process. J. Math. Analysis and Applications (1970)
Torti, L., Wuillemin, P.H.: Structured value elimination with d-separation analysis. In: Proc. of FLAIRS 2010, pp. 122–127 (2010)
Torti, L., Wuillemin, P.H., Gonzales, C.: Reinforcing the object-oriented aspect of probabilistic relational models. In: Proc. of PGM 2010 (2010)
Yan, X., Han, J.: gSpan: Graph-based substructure pattern mining. In: Proc. of ICDM 2002 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Torti, L., Gonzales, C., Wuillemin, PH. (2011). Patterns Discovery for Efficient Structured Probabilistic Inference. In: Benferhat, S., Grant, J. (eds) Scalable Uncertainty Management. SUM 2011. Lecture Notes in Computer Science(), vol 6929. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23963-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-23963-2_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23962-5
Online ISBN: 978-3-642-23963-2
eBook Packages: Computer ScienceComputer Science (R0)