Original title: On polyhedral approximations of polytopes for learning Bayes nets
Authors: Studený, Milan ; Haws, D.
Document type: Research reports
Year: 2011
Language: eng
Series: Research Report, volume: 2303
Abstract: We review three vector encodings of Bayesian network structures. The first one has recently been applied by Jaakkola et al., the other two use special integral vectors, called imsets. The central topic is the comparison of outer polyhedral approximations of the corresponding polytopes. We show how to transform the inequalities suggested by Jaakkola et al. to the framework of imsets. The result of our comparison is the observation that the implicit polyhedral approximation of the standard imset polytope suggested in (Studený Vomlel 2010) gives a closer approximation than the (transformed) explicit polyhedral approximation from (Jaakkola et al. 2010). Finally, we confirm a conjecture from (Studený Vomlel 2010) that the above-mentioned implicit polyhedral approximation of the standard imset polytope is an LP relaxation of the polytope.
Keywords: imsets; learning Bayesian networks; polytopes
Project no.: CEZ:AV0Z10750506 (CEP), GA201/08/0539 (CEP)
Funding provider: GA ČR

Institution: Institute of Information Theory and Automation AS ČR (web)
Document availability information: Fulltext is available at external website.
External URL: http://library.utia.cas.cz/separaty/2011/MTR/studeny-on polyhedral approximations of polytopes for learning bayes nets.pdf
Original record: http://hdl.handle.net/11104/0199217

Permalink: http://www.nusl.cz/ntk/nusl-55876


The record appears in these collections:
Research > Institutes ASCR > Institute of Information Theory and Automation
Reports > Research reports