|
|
LP relaxations and pruning for characteristic imsets
Studený, Milan
The geometric approach to learning BN structure is to represent it by a certain vector; a suitable such zero-one vector is the characteristic imset, which allows to reformulate the task of finding global maximum of a score over BN structures as an integer linear programming problem. The main contribution of this report is an LP relaxation of the corresponding polytope, that is, a polyhedral description of the domain of the respective integer linear programming problem.
|
|
|
On polyhedral approximations of polytopes for learning Bayes nets
Studený, Milan ; Haws, D.
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.
|
|
| |
|
| |
|
| |
|
|
Využití imsetů při učení bayesovských sítí
Vomlel, Jiří ; Studený, Milan
This paper describes a modification of the greedy equivalence search (GES) algorithm. The presented modification is based on the algebraic approach to learning. The states of the search space are standard imsets. Each standard imset represents an equivalence class of Bayesian networks. For a given quality criterion the database is represented by the respective data imset. This allows a very simple update of a given quality criterion since the moves between states are represented by differential imsets. We exploit a direct characterization of lower and upper inclusion neighborhood, which allows an efficient search for the best structure in the inclusion neighborhood. The algorithm was implemented in R and is freely available.
|
|
| |
|
| |
|
| |
|
|
Characterization of inclusion neighbourhood in terms of the essential graph: Lower neighbours
Studený, Milan
The topic of the paper is to characterize inclusion neighbourhood of a given equivalence class of Bayesian networks in terms of the respective essential graph. It is shown that every inclusion neighbour is uniquely described by a pair ([a,b],C) where [a,b] is a pair of distict nodes which is not an edge and C is a disjoint set of nodes. Given such [a,b] the collection of respective sets C is the union of two tufts. The least and maximal sets of these tufts can be read from the essential graph.
|
guest ::
RSS feed.