Research Commons
      • Browse 
        • Communities & Collections
        • Titles
        • Authors
        • By Issue Date
        • Subjects
        • Types
        • Series
      • Help 
        • About
        • Collection Policy
        • OA Mandate Guidelines
        • Guidelines FAQ
        • Contact Us
      • My Account 
        • Sign In
        • Register
      View Item 
      •   Research Commons
      • University of Waikato Research
      • Computing and Mathematical Sciences
      • Computing and Mathematical Sciences Papers
      • View Item
      •   Research Commons
      • University of Waikato Research
      • Computing and Mathematical Sciences
      • Computing and Mathematical Sciences Papers
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.

      Efficient algorithms for conditional independence inference

      Bouckaert, Remco R.; Hemmecke, Raymond; Lindner, Silvia; Studený, Milan
      Thumbnail
      Files
      bouckaert Efficient Algorithms.pdf
      212.9Kb
      Link
       jmlr.csail.mit.edu
      Citation
      Export citation
      Bouckaert, R., Hemmecke, R., Lindner, S. & Studeny, M. (2010). Efficient algorithms for conditional independence inference. Journal of Machine Learning Research, 11, 3453-3479.
      Permanent Research Commons link: https://hdl.handle.net/10289/5120
      Abstract
      The topic of the paper is computer testing of (probabilistic) conditional independence (CI) implications by an algebraic method of structural imsets. The basic idea is to transform (sets of) CI statements into certain integral vectors and to verify by a computer the corresponding algebraic relation between the vectors, called the independence implication. We interpret the previous methods for computer testing of this implication from the point of view of polyhedral geometry. However, the main contribution of the paper is a new method, based on linear programming (LP). The new method overcomes the limitation of former methods to the number of involved variables. We recall/describe the theoretical basis for all four methods involved in our computational experiments, whose aim was to compare the efficiency of the algorithms. The experiments show that the LP method is clearly the fastest one. As an example of possible application of such algorithms we show that testing inclusion of Bayesian network structures or whether a CI statement is encoded in an acyclic directed graph can be done by the algebraic method.
      Date
      2010
      Type
      Journal Article
      Rights
      © 2010 Remco Bouckaert, Raymond Hemmecke, Silvia Lindner and Milan Studeny.
      Collections
      • Computing and Mathematical Sciences Papers [1452]
      Show full item record  

      Usage

      Downloads, last 12 months
      20
       
       

      Usage Statistics

      For this itemFor all of Research Commons

      The University of Waikato - Te Whare Wānanga o WaikatoFeedback and RequestsCopyright and Legal Statement