Fast Discovery of Unexpected Patterns in Data Relative to a Bayesian Network Szymon Jaroszewicz and Tobias Scheffer   View Paper (PDF)   Return to Research Session 13 [Novel Learning Algorithms] Abstract We consider a model in which background knowledge on a given domain of interest is available in terms of a Bayesian network, in addition to a large database. The mining problem is to discover unexpected patterns: our goal is to find the strongest discrepancies between network and database. This problem is intrinsically difficult because it requires inference in a Bayesian network and processing the entire, potentially very large, database. A sampling-based method that we introduce is efficient and yet provably finds the approximately most interesting unexpected patterns. We give a rigorous proof of the method's correctness. Experiments shed light on its efficiency and practicality for large-scale Bayesian networks and databases. ©2006 Association for Computing Machinery