Lindner S. Discrete optimisation in machine learning: learning of Bayesian network structures and conditional independence implication

Technical University of Munich, 2012. — 177 p.Learning of Bayesian network structures is a NP-hard nonlinear combinatorial optimisation problem. This problem can be transformed into a linear problem but in exponential dimension using the newly introduced characteristic imsets which are combinatorial representatives. These 0/1-vectors enable us to obtain theoretical results and to use well-known optimisation software for the learning of Bayesian network structures Moreover the conditional implication problem can be formulated with characteristic imsets as a geometric problem for which methods from linear optimisation obtain fast solutions.