Computer-based probabilistic-network construction
Edward H. Herskovits · 1992
Faced with increasing amounts of data that they cannot analyze manually, biomedical researchers have turned increasingly to computational methods for exploring large databases. In particular, researchers might benefit from a nonparametric, efficient, computer-based method for determining the important associations among variables in a domain, particularly when human expertise is not readily available. In this dissertation, I demonstrate that such computer-based algorithms are conceptually feasible, robust to noise, computationally efficient, theoretically sound, and that they generate models that can classify new cases accurately. I first describe two algorithms that take as input a database of cases and optional user-supplied prior knowledge, and that generate a probabilistic network--in particular, a belief network--as output. The database may have incomplete data, and may contain noise. The resulting belief network may be used to determine important associations among variables in a poorly understood domain, or may be used as a classifier for new cases that were not used in learning. After describing the algorithms, I present simple examples of how these programs generate a belief network from a database. I then present the results of evaluating these algorithms on databases from several domains, including gynecologic pathology, lymph-node pathology, DNA-sequence analysis, and poisonous-mushroom classification. In most cases, the belief networks classify new test cases with high accuracy. In addition to discussing empirical results, I present an overview of proofs that these algorithms are based on metrics that will, as the number of cases in the database increases without limit, always prefer those networks that more closely approximate the true underlying distribution of the data in the database; that is, these algorithms are asymptotically correct. I conclude with a discussion of this work's contributions, and with a list of open research problems.