.......................................................................................................................................................

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:

• Can a computationally tractable representation of Markov equivalence classes of graphs (i.e. graphs with the same CI structure) be developed?
•  Is there a natural neighbourhood concept for Markov equivalence classes?
• Are there computationally efficient methods for moving from one Markov equivalence class to another?

Characterize in graphical terms when one CG is a submodel of another CG.

Main participants are listed below together with rough description of their areas of interest (for details see the Appendix):

• Remco Bouckaert -- chain graphs and learning algorithms for Bayesian networks
• Paolo Giudici -- MCMC methods for Bayesian learning UG models
• František Matúš -- conditional independence, mimimum entropy estimates
• Thomas Richardson -- mixed ancestral graphs, alternative chain graphs
• Tams Rudas -- parameterizations of discrete distributions, fitting algorithms for graphical models, generalization of log-linear models
• Milan Studený -- chain graphs, conditional independence

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

......................................................................................................