Bayesian Networks and Related Formalisms
Here is a selection of pointers to information about the currently
hot topic of networks that represent probabilistic and decision
relationships. Probably the best starting point is a page collected
by Wray Buntine that refers to many excellent tutorial papers and
other recent collections.
A number of the references below were collected by Ira Haimowitz at
GE Research via a public appeal for such pointers.
See an interesting collection of material
related to
Decision Theory Group staffed by many excellent researchers trained in
medical decision making.
Hemant Bhargava maintains an interesting collection of information on
decision-support systems, many of which relate to Bayesian
networks and influence diagrams.
Here is the complete set of responses to Ira's request for
information:
Date: Thu, 23 Feb 95 13:42:04 EST
From: haimowit@oceana.crd.ge.com (Ira Haimowitz)
To: uai@maillist.CS.ORST.EDU
Subject: Responses: Learning belief nets (long).
Sender: owner-uai@maillist.CS.ORST.EDU
Precedence: bulk
Thanks to all who answered my query about learning Bayesian Belief
nets!!! The response was wonderful. Below I post the original query
and all replies with actual systems and contacts. The message is
fairly long.
-- Ira Haimowitz, GE Corp. Research & Development.
-----------------------------
*** Original query *************
: Dear Collaegues:
:
: Does anyone know of any WWW server or otherwise net-available code for
: automated learning of Bayesian belief nets? Either learning the
: structure from data, or learning probabilities given structure and
: data would be desirable. We are researching use of these techniques;
: we know of some papers, but could use pointers to available software.
:
: Thanks very much for any pointers.
***** Answers (In rough order of receipt) *************
-------------
From: A_J_Zawilski%mwcorp1@MWMGATE1.mitre.org
To: haimowit@oceana.crd.ge.com (Ira Haimowitz)
Subject: Re: Tools for inducing belief nets
You probably already know about the page that Russ Almond maintains on
belief networks http://www.stat.washington.edu/belief.html
you might also try the decision theory group at microsoft research
http://www.research.microsoft.com/research/dtg/
again you probably know everyone there too.
those are the only relevant web addresses that I know.
hope the info is of some use.
Tony Zawilski
-------------
From: Christopher Meek
To: haimowit@oceana.crd.ge.com (Ira Haimowitz)
Subject: Re: Tools for inducing belief nets
In-Reply-To: <9502012017.AA20919@oceana.crd.ge.com>
References: <9502012017.AA20919@oceana.crd.ge.com>
In regards to your querry about automated procedures I offer the
following inexpensive commercial alternative and a pointer to a list of
many commercial and non-commercial software packages.
http://www.stat.washington.edu/belief.html
The commercial package is described below.
Chris Meek
TETRAD II
Short Description
A multi-module program that assists in the construction of causal
explanations for sample data and their use in prediction. With
continuous variables
the program will aid in the search for "path models" or "structural
equation models;"
with discrete data the program will construct and update a Bayes network from
sample data and user knowledge of the domain; the program includes Monte Carlo
facilities. Proofs of the asymptotic correctness of all but one of the
search modules
are available in P. Spirtes, C. Glymour and R. Scheines, Causation,
Prediction and
Search, Springer Lecture Notes in Statistics, 1993.
Platform(s): DOS
In the future a Unix version may be available.
The DOS software comes with a ~250 page manual with chapters on theoretical
foundations, interpreting output, and a chapter on each of the software
modules.
Each of the chapters include many detailed example of running Tetrad II.
Authors: Richard Scheines, Peter Spirtes, Clark Glymour, and Christopher
Meek (1994).
TETRAD II: Tools for Discovery. Lawrence Erlbaum Associates,
Hillsdale, NJ.
Ordering information
Phone orders : 1-800-926-6579
Mail orders : Lawrence Erlbaum Associates
365 Broadway
Hillsdale, N.J.
07642
Extended description
TETRAD II has 10 modules, each of which has its own chapter in the
manual. They are:
Build Purify Makemodel
Estimate MIMbuild Monte
Update Search STATwriter
Tetrads
Build, Purify, MIMbuild, and Search are the main inference modules.
Using appropriate statistical tests, Build makes a series of decisions
about independence and conditional independence relations among
measured variables. This information is used to search for a class of
models that cannot be distinguished by conditional independence
relations alone, and that are compatible with user-entered background
knowledge. Purify, MIMbuild, and Search work on normally distributed
linear structural equation models with latent variables, and use
substantive assumptions provided by the user together with statistical
decisions about vanishing correlations and tetrad differences to
estimate features of the causal structure. If the variables modeled
are all discrete, then the Estimate module can calculate maximum
likelihood estimates of the parameters of a Bayesian network that
contains no latent variables, and the Update module can use these
estimates to calculate conditional distributions. Makemodel and Monte
provide a useful Monte Carlo simulation package. Makemodel takes an
unparameterized causal structure and, after prompting the user for an
interpretation of the structure as either a Bayesian network or a
recursive linear structural equation model, parameterizes the
structure and writes a fully parameterized statistical model to a
TETRAD II readable file. Monte can then be used to generate samples
of any size from such a model. Although TETRAD II does not estimate or
test linear models, it will automatically write out input files to
three popular packages that do: LISREL, EQS, and CALIS. The module
takes a path diagram and covariance or raw data and will automatically
write out an input file to the package Of your choice.
------------
I received your message from Neal Lovell, a former student. I have 2
suggestions for you:
1) Locate certain software by going to my "Decision Support Systems" page:
http://bhargava.as.nps.navy.mil/www/hkb/research/dss.html
Currrently there is a link that will be of use to you:
http://www.stat.washington.edu/belief.html
2) More generally, you may want to look at our DecisionNet page:
http://dnet.as.nps.navy.mil/dNethome.html
In the future (as we become public and get more "providers") you may find
much of use here. Further, if your organization could support this effort
in some way ... we are certainly looking for sponsors.
Hemant Bhargava
Naval PG School
------
From: "Kevin Korb"
Date: Thu, 2 Feb 1995 12:02:21 -0500
In-Reply-To: haimowit@oceana.crd.ge.com (Ira Haimowitz) "Tools for inducing belief nets" (Feb 1, 3:17pm)
References: <9502012017.AA20919@oceana.crd.ge.com>
X-Mailer: Z-Mail (3.1.0 22feb94 MediaMail)
To: haimowit@oceana.crd.ge.com (Ira Haimowitz)
Subject: Re: Tools for inducing belief nets
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0
Hi Ira,
I do not know of such; if you hear of any, I'd be interested. I am
investigating the learning of causal structure here at Monash & would
be happy to hear about your efforts/interests. I do know of
Glymour, et al.'s Tetrad II; I believe it's available for around
$150 (US) from Lawrence Erlbaum Associates. It is for learning
causal structure from correlational data, not for learning numerical
parameters. We've ordered it, but not yet received it. (It is not
Bayesian learning; for background see their 1993 book in the Springer
Verlag Statistics Lecture Notes series.)
Whether there's code available for Herskovitz's and others' approaches,
I don't know but would like to.
My guess would be that Heckerman's work for Microsoft is and will remain
unavailable.
Whatever code we end up producing here will be made available, at
least in its initial versions.
Any corrections as to matters of fact would be most welcome.
Regards, Kevin
P.S. Perhaps you can compile responses such as mine & repost them
collectively to uai? I'd be interested in seeing what others
have to say.
-------------------------------------------------------------------
Dr. Kevin Korb korb@bruce.cs.monash.edu.au
Dept. of Computer Science phone: +61 (3) 905-5198
Monash University fax: +61 (3) 905-5146
Clayton, Victoria 3168
Australia
---------
From: Stuart Russell
To: haimowitz@crd.Ge.Com
Subject: learning belief nets
Hugin has a version called aHugin that adjusts parameters as it goes along.
You can probably get the code from the same source as Hugin.
(If you are working with Piero Bonissone: I mentioned to him some new methods
we have for learning belief nets with hidden variables, which the Heckerman
and Cooper methods cannot do. If you are interested, we could work on your data
set, although we are not ready to release code yet.)
Stuart Russell
------
From: David Madigan
Subject: Re: Tools for inducing belief nets
To: Ira Haimowitz
In-Reply-To: <9502012017.AA20919@oceana.crd.ge.com>
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Check out:
http://www.stat.washington.edu/belief.html
-----------
From: Eero.Hyvonen@vtt.fi (Eero Hyvonen)
Subject: Re: Tools for inducing belief nets
Cc: janne.pesonen@vtt.fi
Dear Ira Haimowitz,
Unfortunately I cannot really help you with your question, but your
concern is something we will be encountering in our research project just
starting. Actually, I once implemented (ESCOM-meeting, Munich, 1992) the
Lauritzen-Spiegelhalter-algorithm in Lisp with a simple learning scheme for
tuning the conditional probabilities given the network, but that piece of
software was done just for experimentation and learning the formalism.
Until now, we have not been active on the topic.
We would be greatful, if you could forward us information you may get in
response to your request. It would also be nice to lear more on your own
work if you have published something (our address is below). It seems that
you are using some net-available code for belief nets already now (?) If
so, could you make a recommendation and how to get it?
Yours sincerely
Eero Hyvonen
-----------
From: Bo Thiesson
Date: Thu, 2 Feb 1995 09:26:15 +0100
To: haimowit@oceana.crd.ge.com
Subject: Re: Tools for inducing belief nets
X-Sun-Charset: US-ASCII
Dear Ira Haimowitz,
At the ftp site:
ftp.iesd.auc.dk
you can get the BIFROST program for structural learning:
pub/packages/BIFROST/bifrost.1.1
(I have discovered a bug in bifrost.1.2)
User's guide:
pub/reports/tech-reports/R92-2001.ps.Z
Theoretical report about BIFROST:
pub/reports/tech-reports/R92-2010.ps.Z
The program is available free of charge for non-commercial use.
BIFROST presupposes another program; CoCo to be installed too. Also
if you want to be able to use the exportation facility to HUGIN,
HUGIN has to be installed.
You can get CoCo at the same ftp site, where you will find it in
pub/packages/CoCo
HUGIN is a commercial product. For information, please, contact
info@hugin.dk
-Bo Thiesson
---------
From: sven@hugin.dk (Sven Vestergaard, Hugin Expert A/S)
Subject: Re: Tools for inducing belief nets
Dear Ira Haimowitz
A feature in our old version of Hugin Professional (version 3.3) is the
ability to learn.
We are using the algorithms described in:
David J. Spiegelhalter and Steffen L. Lauritzen. Sequentail updating of
conditional
probabilities on directed graphical structures. Networks, 20: 579-605, 1990.
LEARNING:
"A feature of Hugin (version 3.3) is the ability to learn from a set of data.
Hugins learning facilities has the following features: They work on
incomplete data,
and they work on a running system.
Thus, you can initiate Hugin with data from an existing database (which
need not to be
complete), and then let the running system continue to learn as new data
is generated.
The latter also allows a system using Hugin to adapt to a changing world,
thus preventing
the system to become out of date."
We have just introduced our new API with a lot of new features, and are going to
upgrade the Learning features .An updated version will be released April 95.
(the old algoritm is not implemented in the new code)
Some features of our new version of the Hugin system. (Version 4.0)
Influence diagrams. An influence diagram is a belief network argumented
with decisions and utilities. Arcs in the influence diagram into a
random variable represents probabilistic dependencies while arcs into
a decision variable represents availability of information at the time
the decision is taken. Assuming a total ordering of the decisions, an
optimal decision policy using maximization of expected utility for
choosing between decision alternatives can be computed.
The new version of the Hugin system allows specification of and
inference and decision making with influence diagram. This version
will also take advantage of the case where the overall utility is a
sum of a set of local utilities.
New propagation methods: A `max'-propagation to identify the most
probable configuration of all variables and compute its probability,
and a new way to incorporate evidence, known as `fast retraction',
permits the computation, for each variable, of the conditional
probability of that variable given evidence of the remaining variables
(useful for identifying suspicious findings). Thus, four different
ways of propagating evidence are now available.
Graphical models with undirected edges, so-called `chain graph'
models, are now permitted. This extends the class of models so that
automatically generated models are more easily used with Hugin (in
automatically generated models, the direction of an association is
only rarely identified).
The new version will allow extraction of joint probabilities on a
group of variables, even when the group is not a subset of any clique.
The new version of the Hugin API will allow the user to incorporate
these new features into his/her own programs. In addition, the new
Hugin API will allow construction and editing of belief networks and
influence diagrams. Analysis of data conflicts, which have previously
been available from within Hugin Runtime, is now also available via
the API. A `random' propagation method to simulate configurations,
given evidence, is also provided. The interface of the API has
undergone a major clean-up and redesign. But older programs, using
older versions of the API, will still compile with the new API via a
backwards compatibility mode.
***************************************************************
BAYESIAN NETWORKS, BELIEF NETWORKS,....
there is only one
HUGIN
A software package for construction and execution of model based
expert system.
Sven Vestergaard sven@hugin.dk
Phone: +45 98156644 Hugin Expert A/S
Fax: +45 98158550 Niels Jernes Vej 10
Internet: info@hugin.dk DK - 9220 Aalborg O
Mosaic: http://hugin.dk ftp: hugin.dk
***************************************************************
From: "Jirousek Radim, KIZI, 2435, 413nb"
Organization: University of Economics, Prague,CZ
To: haimowit@oceana.crd.ge.com
Date: Thu, 2 Feb 1995 09:40:32 CET
Subject: Bayesian net software
Priority: normal
X-Mailer: Pegasus Mail v3.1 (R1a)
X-Charset: ASCII
X-Char-Esc: 29
Dear colleague,
within some international grant we are preparing some software system.
If the officials in Brussels have no objection I would like to offer
you soem version of it for testing (if you are interested). I believe,
it may be in May.
Best regards,
Radim Jirousek
Prague, Czech Republic
-----------
From: Reimar Hofmann
To: haimowit@oceana.crd.ge.com
Subject: Re: Tools for inducing belief nets
Cc: Volker.Tresp@zfe.siemens.de
Dear Ira Haimowitz!
We are also interested in learning structure and/or parameters of
Bayesian belief networks or Markov networks from data.
We would therefore be happy if you could inform us about the
results of your survey.
We fond the paper
Operations for Learning with Graphical Models [75 pages]
Wray L. Buntine, RIACS \& NASA Ames Research Center
FTP-host: ack.arc.nasa.gov
FTP-file: /pub/buntine/lwgmja.ps.Z
an useful overview.
Concerning Software we have tested "Hugin". Hugin is a commercial system which
allows learning parameters of Bayesian belief networks with discrete variables,and propagation of evidence.
A free demo-version of hugin can be downloaded via ftp from
ftp-host: hugin.dk
Mosaic: http://hugin.dk
Email: info@hugin.dk
I hope this is of any help.
Thanks for any information about results
Reimar Hofmann
---------
Reimar Hofmann
ZFE T SN 41
Siemens AG Corporate Research and Development
Otto-Hahn-Ring 6 Phone: +49/89/636-46986
D-81730 Muenchen Fax: +49/89/636-3320
Germany e-mail: Reimar.Hofmann@zfe.siemens.de
--------------------------------------------
From: Geoffrey Rutledge
Reply-To: rutledge@CAMIS.Stanford.EDU
To: haimowit@oceana.crd.ge.com (Ira Haimowitz)
Subject: Re: Tools for inducing belief nets
In-Reply-To: Your message of Wed, 1 Feb 95 15:17:59 EST
Ira,
I do not know if it is net-available, but Eddit Herskovits (ehh@camis)
and Greg Cooper (cooper@camis) have developed extensive software to
accomplish this... you might inquire if they would help.
Geoff
Geoffrey Rutledge (rutledge@camis.stanford.edu)
-----------------------------------------------------------------
From: Greg.Cooper@smi.med.pitt.edu
To: haimowit@oceana.crd.ge.com
Subject: Re: Tools for inducing belief nets
I'd suggest you contact Peter Spirtes (ps7z+@andrew.cmu.edu)
and ask him how you obtain a copy of Tetrad II, which is
commercially available. It uses non-Bayesian methods to learn
the structure and parameterization of Bayesian belief networks.
Greg
-----------------------------------------
From: klaskey@osf1.gmu.edu (Kathryn Blackmond Laskey)
Subject: Re: Tools for inducing belief nets
A graduate student of mine acquired K2 from Eddie Herskovits. He supplies
his code with no guarantees. Matt was able to puzzle it out and get it
working in a different version of Pascal. Herskovits is at Noetic Systems
(the company that markets Ergo). I'll get you more detailed information if
you need it.
Kathy Laskey
George Mason University
-----------------------------------------------
From: Robert Cowell
You can obtain a copy of my BAIES program by anonymous ftp from my
machine 128.40.24.2 in subdirectory pub/BAIES. There are two versions
of the program, one for sparc and one for DOS. The relevant files are
freebaies.tar.Z and pcbaies.tar.Z (Note unix compression and packing
of pc version.)
The file command ls does not work on my server, and neither does mget
- i have not been able to set it up properly. You have to change
directory and use the get command with full file name, which is a bit
of a pain.
So assuming you have logged in:
ftp> cd pub/BAIES
ftp> bin
ftp> get freebaies.tar.Z
ftp> get pcbaies.tar.Z
ftp> bye
BAIES is restricted to analysing connected dags with discrete
variables. It is command line based, with options chosen using a
simple menu which scrolls off the screen. Although presenting a
primitive interface it does quite alot of things which you may have
read about in the literature. It has both probability learning and
model criticism features, though no structural search. There is also a
semi-complete postcript documentation in the tar file. It is fast for
small domains, but for large problems a bit slow.
Some people have had problems with the pc version so the sprac version
is probably better to use.
For the last couple of years i have been working on a successor to
BAIES, which I call Xbaies. A version is available by ftp, but this
release has no probablity learning features. However it does have a
friendlier windowing user interface, runs on Sparc, HP, DEC, Alphas
and Windows 3.1, and has other features. It is in the top level of
the ftp directory. So assuming you have just logged on:
ftp> bin
ftp> get alpha.tar.gz
ftp> get dec.tar.gz
ftp> get hp.tar.gz
ftp> get sparc.tar.gz
ftp> get xbaies.zip
ftp> bye
I have implemented probability learning for Dirichlet mixture priors
in a separate program but this is not yet available. It may or may not
become available.
Best wishes,
Robert Cowell
Department of Statistical Science | Tel: +44 071 387 7050 ext 3636
University College London, | Fax: +44 071 383 4703
Gower Street, | Email: rgc@uk.ac.ucl.stats
LONDON WC1E 6BT,
U.K.
PS. If your organisation has megabucks to spare, and you like my
xbaies program you might like to consider supporting my research here,
which is due to come to an end in April with my grant running out.
---------------------------------------------------------------------
From: almond@statsci.com (Russell G. Almond)
To: haimowit@oceana.crd.ge.com
Cc: uai@maillist.CS.ORST.EDU, haimowit@oceana.crd.ge.com, smithwd@crd.ge.com
In-Reply-To: <9502012017.AA20919@oceana.crd.ge.com> (haimowit@oceana.crd.ge.com)
Subject: Re: Tools for inducing belief nets
I would like to get a similar list of software. I'll add it to the
graphical model software page (or maybe make a separate one).
Here are the things I know about (First few taken from Steffan
Lauritzen's short course at AI & Stats):
K2 (Cooper and Herskovits) -- I don't have contact information for
this one.
BIFROST (Hojsgaard and Thiesson) -- Contact thiesson@iesd.auc.dk for
more details. (This may require Hugin to run, I'm not sure).
CoCo (Badsberg 1992) --- This is available from:
ftp://ftp.iesd.auc.dk/pub/packages/CoCo/CoCo.1.2/
You can contact the author at jhb@iesd.auc.dk
Less automated solutions involve software which will fit a given model
structure but not do model selection (improvement) for you.
MIM (Edwards 1990) --- This is a flexible program fitting many types
of grpahical models. It is not a complete data analysis environment.
Runs on PCs.
Available from the author:
David Edwards, Bymarken 38, DK-4000 Roskilde, DENMARK
I believe their is a small charge for the program.
Also, there is a close correspondence between undirected graphical
models and generalized linear models (GLMs). (Whittaker's book on
graphical models is probably a good starting place if you are
unfamiliar with GLMs and Log-linear models.) A number of mainstream
statistical packages fit GLMs, e.g., S-Plus, SAS and of course GLIM.
They are not free, but check around, your institution may already own
a site licence.
I'd be very grateful if people could help me add to/flesh out this
list. I'll try and make another web page for it.
BTW, I appologize for not getting updates to the belief software list.
UW has not had as rapid turn-around time on this as I would like. I'm
assured by my local system gurus that StatSci will have a web site
"real soon now" so I'll advertise again when I get all the updates
posted.
[in a later message from R. Almond:]
One other possibility is Graphical-Belief. Graphical-Belief is
StatSci's commercial system for manipulating graphical models. Its
currently a research prototype, but I'm hoping to have an alpha
release ready for other researchers by the summer.
Currently, Graphical-Belief contains relatively limited tools for
model updating (we have some tools for updating parameter estimates
based on new data, although we do get around the global independence
assumption of Spiegelhalter and Lauritzen [1990]). But I've felt for
a long time, that Graphical-Belief would be the ideal environment for
expirimenting with some of David Madigans ideas about Model
Uncertainty. The hooks are in place for this already and I'm currently
looking for funds to pursue that line of research and development.
One of the reasons I mention this is because I have been talking to
one of your colleagues, Mahesh Morjaria (Morjaria@crd.ge.com) about
potential applications of Graphical-Belief. I've sent him a number of
technical reports, some of which you may find interesting. I've CCed
him on this message.
Hope this answers some of your questions. If you have any more I'd be
happy to answer them.
Russell Almond
StatSci (a division of MathSoft)
1700 Westlake Ave., N Suite 500, Seattle, WA 98109
(206) 283-8802 x234 FAX: (206) 283-6310 Email: almond@statsci.com
-------------------------------------------------------------------