Quantum Bayesian Networks

October 21, 2015

Snow White Bayesian Network For a Collection of Sets

Filed under: Uncategorized — rrtucci @ 5:21 pm

CB net= Classical Bayesian Network
DAG= directed acyclic graph

In supervised learning, you are given the graph (aka structure) of a CB net, and some data, and you evaluate the node probability matrices from the data. In unsupervised learning, you are given only data, and you are expected to come up with the structure and node probability matrices of the CB net from that data. Nowadays there are computer programs that do both supervised and unsupervised learning of a CB net on classical computers. I believe a quantum computer can do unsupervised learning of a CB net at least quadratically faster (due to Grover’s algo) than a classical computer. In fact, I have a patent for doing unsupervised learning of a CB net on a gate model QC. (The Quail group at NASA has proposed doing this also with a D-Wave annealer QC).

And yet, many of the examples of CB nets that show up in the literature (See, for example, the wonderful work of Andrew Gelman) were obtained “by hand”—their structure was derived without the help of a computer, arrived at partly by logic and partly by hunch. The quality and value of these CB net models depends on how well they fit the data.

So can I provide some guidance on how to find the structure of a CB net by hand? I don’t know how the experts do it, but I’ll tell you how I think about it.

There is one situation that I like to call the Snow White CB net (I call it Snow White because it’s the fairest CB net of them all). It concerns finding a CB net that connects a collection of sets.

Snow White DAG
Suppose you have n sets A_1, A_2, \ldots A_n which are not necessarily mutually disjoint.

  1. Merge all sets that are equal into a single set.
  2. Write an undirected line connecting those pairs of sets that overlap (but not if they don’t overlap).
  3. If A_i \subset A_j, then replace the undirected line joining them by an arrow pointing from A_i to A_j. Thus

    A_i \subset A_j
    A_i \rightarrow A_j
    x\in A_i \implies x\in A_j

    all mean the same thing.

  4. If A_i and A_j overlap, but neither is a proper subset of the other, then replace the undirected line between A_i and A_j by

    A_i \leftarrow A_i\cap A_j \rightarrow A_j

  5. Go back to step 1. Exit loop when last two repetitions yield the same DAG.

At the end, you will have a DAG in which the arrows all indicate a subset relationship. Also, by the end, all the root nodes (the ones with no incomming, only outgoing arrows) will be mutually disjoint sets. This is all very trivial and I’m sure a lot of people have come up with the Snow White DAG on their own. I just mention it in case you haven’t yet.

PS. In the above convention, a typical operating system with folders is represented by a tree, with the arrows pointing away from the multiple innermost folders towards the single outermost folder. The outermost folder is often called the root directory in operating system parlance, but here I am calling the innermost folders the root nodes.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: