Learning in belief networks and its application to distributed databases.

Abstract

In this thesis we study the problem of learning in belief networks and its application to caching data with repeated read-only accesses in distributed databases. Bayesian Belief Networks (BBNs) have been studied in the literature, and two classes of techniques for constructing BBNs from distributions have been studied. These schemes are methods based on probabilistic-graph models, and Bayesian methods for learning Bayesian networks. In this thesis we first consider methods to build tree structures and use these trees as a basis to build a richer structure, namely a polytree graph. We study the problem of traversing the tree and present a depth first search traversal of the tree in order to orient it so as to yield the polytree. The algorithm to yield the above polytrees uses independence tests between two random variables to detect multiple parents of a given node in the tree structure. Consequently we investigate the use of various independence tests to infer independence of random variables encountered in real-life data. We also present formal techniques to generate random distributions obeying polytree dependence models. The thesis also develops machine learning schemes to detect sequences of repeated queries to remote databases. The answers to these queries (tables) from remote servers are retrieved only once and cached locally in memory. Subsequent access to the same data or sequence of data is faster as there is no need to re-fetch it over the network. The learning algorithms we present are based on constructing polytree structures from a set of queries. Once constructed, such networks can provide insight into probabilistic dependencies that exist among the queries and thus enhance distributed query optimization.