HSSS Research Kitchen on
Learning Conditional Independence Models
held
from October 16 to October 21, 2000
at academic
hotel TŘEŠŤ, Třešť
Czech Republic
organized within the
European Science Foundation scientific program for 1997-2000
Highly Structured Stochastic Systems
by
Institute of Information
Theory and Automation,
Academy of Sciences
of the Czech Republic
and
Laboratory of Intelligent
Systems,
University of Economics Prague
.......................................................................................................................................................
REPORT FOR EUROPEAN SCIENCE FOUNDATION
is available here. Moreover, its postscript
version (100kB) also is available.
.............................................................................................................................................................................
OPEN PROBLEMS
The participants formulated during the kitchen several
open problems related to the topic of the kitchen. Some mathematical problems
are described in an attached postscript file
openpro.ps
and some other problems are formulated (in general terms) in web references:
It is the
problem of voting and
the
problem of topic maps.
..............................................................................................
GENERAL INFORMATION
The program will consist of informal talks given by the
participants and intensive debate on the topics described below. Details
can be specified later. Emphasis will be put on discussion about open mathematical
problems mentioned in the original proposal. The meeting is strongly topic-oriented
and participation will be limited to the persons mentioned in the original
proposal.
..............................................................................................
PARTICIPANTS
Remco Bouckaert, Crystal
Mountain Information Technology
Eva-Maria Fronk, University
of Munich
Paolo
Giudici, University of Pavia
Tomáš
Kočka, University of Economics Prague
František Matúš, Academy of Sciences of the Czech
Republic
Thomas Richardson, University
of Warwick
Tams Rudas, Eotvos
University, Budapest
Milan
Studený, Academy of Sciences of the Czech
Republic
Claudia Tarantola, University
of Pavia
................................................................................................................................................................................................
SCIENTIFIC DESCRIPTION
Graphs, whether directed, undirected or both, provide a natural framework for representing highly structured systems of statistical dependence relations among a large set of variables. This use of graphs has a long history in statistics. In spatial statistics and image analysis, Markov random fields correspond to undirected graphs (e.g. Besag, 1974); path models or structural equation models, which have been applied in population genetics, psychometrics and econometrics are represented by directed graphs (Wright, 1934; Hood and Koopmans 1953; Blalock, 1971). This development accelerated in the late 1970's with the work of Lauritzen, Speed and Wermuth on graphical log-linear and recursive linear models, later continued by Dawid, Spiegelhalter, Frydenberg, Cox and many others. The recent books by Edwards (1995), Cox and Wermuth (1996), Lauritzen (1996) give excellent overviews.
At the same time, separate, but convergent developments of these ideas occurred in computer science, decision analysis, epidemiology and philosophy, where graphical Markov models have been called influence diagrams, belief networks or Bayesian networks, and causal models. The application of graphical Markov models in the construction of expert systems has proved particularly fruitful - any recent proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI) provide numerous real world applications. Prominent examples include the trouble-shooting software, and help systems that are incorporated into Microsoft Windows '95, and Office '97, which are based on Bayesian networks. The books by Pearl (1988), Neapolitan (1990), Oliver and Smith, eds. (1990), Heckerman (1991), Spirtes, Glymour and Schienes (1993), Almond (1995) and Jensen (1996) survey these areas.
The emerging area of data mining offers many fruitful applications of graphical models, particularly in the fields of finance and marketing, where increasingly complex databases demand appropriate modular modelling. Employment of graphical models in this area is still at a preliminary stage, but one can foresee their development in the near future.
Several different classes of graphs have been used for the purpose of representing systems of dependence: the original theory was based on undirected graphs (UGs) and directed acyclic graphs (DAGs); chain graphs (CGs) which generalize both DAGs and UGs have also been used. More recently several other classes of graphs have been proposed for describing CI structures that arise from certain types of data generating process: mixed ancestral graphs (MAGs), reciprocal graphs, joint-response chain graphs and alternative (AMP) chain graphs. However, existing graphical models can only describe a very small subset of the possible probabilistic CI structures. Thus, a second line of work has developed non-graphical methods which have the advantage that they allow all probabilistic CI structures to be described: semi-graphoids, imsets and matroids.
For practical applications, methods for learning CI models from data are required. Various approaches have been applied to UG and DAG models, including maximum likelihood and Bayesian, both exact and with Markov chain Monte Carlo (MCMC) methods. These approaches have two basic ingredients: a score for evaluating a given model in the light of data; a search method for considering new candidate models. For several of the classes of graphs listed: chain graphs and Gaussian ancestral graphs, scoring procedures exist. However, a number of basic graph-theoretic questions remain unsolved:
Characterize in graphical terms when one CG is a submodel of another CG.One promising approach is to try to reformulate the question in terms of conditions on largest chain graphs which serve as natural representatives of Markov equivalence classes of CGs. On the other hand, for several other classes of models that are listed it is also necessary to develop scoring procedures. This is true for ancestral graph models for discrete data and all of the non-graphical representations of CI structure. A second focus of the workshop will be to develop fitting algorithms and/or parametrizations for these classes of models. Recent work on the method of minimizing Kullback-Leibler divergence provides a promising starting point.
Main participants are listed below together with rough description of their areas of interest (for details see the Appendix):
APPENDIX - some relevant recent
publications of main participants
kitchapp.ps
..............................................................................................
VENUE
The venue is a small village Te, in south-eastern Bohemia,
approximately 150 kilometers from Prague. The hotel
(a former castle), is owned by Academy of Sciences of the Czech Republic
and is used as a venue for small workshops. Photos
and more detailed information in Czech is available.
..............................................................................................
ADDRESS (coordinator)
Milan Studený
Institute of Information Theory and Automation
Academy of Sciences of the Czech Republic
Pod vodárenskou věží 4
18208 Prague, Czech Republic
Phone: (420-2) 6605 2304
Fax: (420-2) 688 4903
E-mail: studeny@utia.cas.cz
..............................................................................................
This page was created by M. Studený with substantial help of J. Pánková.
Last updated December 6, 2001
..............................................................................................
Photos of several participants are below:
Working atmoshere in the kitchen: |
kitchn1 |
kitchn2 |
kitchn3 |
kitchn4 |
kitchn5 |
kitchn6 |
kitchn7 |
kitchn8 |
kuch1 |
kuch2 |
kuch3 |
......................................................................................................