Dear Richard,
in recent years, I have devoted a lot of my research effort to the development
of (theoretical basis for) the
geometric methods, which can be used to find a global maximum of quality
criterion (=score) over BN structures.
This, in the end, seems to lead to the application of methods of (integer)
linear programming, for which wonderful
speedy software packages have been developed by specialists in mathematical
optimization
Thus, I have mentioned that there were some papers devoted to the algorithms
for finding the global maximum and some computational experiments based on that
have been made.
These are mainly
- dynamic programming approach by Silander+Myllymakki
- integer linear programming approach by Jaakkolla, Sontag, Globerson and Meila
- integer linear programming approach by Cussens (2 papers)
- higly relevant is also the research by C.deCampos +Ji on "pruning"
Of course, my co-authors (in particular S.Lindner) also made some preliminary
computational experiments.
You may find references to the above mentioned papers (and some description of
our approach) in a couple of papers:
- M. Studený, J. Vomlel, R. Hemmecke ``A geometric view on learning Bayesian
network structures''
International Journal of Approximate Reasoning 51 (2010), n.5, 578-586.
a preprint available through staff.utia.cas.cz/studeny/a28.html
[BTW: in this paper a very simple example is given showing that GES can fail to
find the global maximum]
- R. Hemmecke, S. Lindner, M. Studený ``Characteristic imsets for learning
Bayesian network structure''
International Journal of Approximate Reasoning 53 (2012) 1336-1349.
a preprint available through staff.utia.cas.cz/studeny/a31.html
[Here you find most of the references]
I hope this helps. Regards from
Milan Studeny
PS: in my view, the application of the integer linear programming approach in
particularly promising
research direction
Richard E. Neapolitan napsal:
> Dear Colleagues,
> This note concerns learning Bayesian networks from data,
> an area in which I wrote a book in 2003. However, since then I have not kept
> that close of a track of developments in the area.
> The GES algorithm assumes the composition property,
> and the
> constraint-based PC algorithm and more
> advanced constraint-based algorithms
> assume faithfulness or embedded
> faithfulness. So none of
> them would discover a
> DAG in which
> two variables
> together have
> an effect on a
> third variable,
> but neither of
> the variables has a
> marginal effect. I
> am wondering if
> there are any heuristic
> search
> algorithms,
> in a particular
> ones implemented
> in available
> software, that
> address this
> situation. Clearly,
> there are
> modifcations of
> these algorithms
> that would do
> so.
> Thanks,
> Rich
>
> -- Richard E. Neapolitan, Ph.D., ProfessorDivision of
> Health and Biomedical InformaticsDepartment of Preventive
> MedicineNorthwestern University Feinberg School of Medicine750 N. Lake Shore
> Drive, 11th floorChicago IL 60611
--
_______________________________________________
uai mailing list
uai@ENGR.ORST.EDU
https://secure.engr.oregonstate.edu/mailman/listinfo/uai
