BayesDB - a Bayesian database table
probcomp.csail.mit.edu
probcomp.csail.mit.edu
It will be interesting to see how far the database analogy can be pushed. The key thing to realize is that BayesDB is based on a particular model, CrossCat (http://probcomp.csail.mit.edu/crosscat/). If your database table is an adjacency list that represents a graph, for instance, it's not going to perform very well compared to a more tailored model. On the other hand, a generic approach to high-dimensional imputation is very useful.
The reality is that almost any model that lets you build up a good joint density estimate of the data can be useful for this sort of tabular data. CrossCat assumes that your joint factors in to several independent factors -- that is, p(x, y, z, w) = p(x, y) p(z, w), for example. Of course, because it's a dirichlet process of dirichlet processes, all that's learned from the data. But that's not always the best approach, there are others, and it will be fun to see what else comes out of the research community.
And Tristan's also right that this is not always a great fit for your data -- if it's graph based, or if your data are super-high-dimensional, or whatever, it's not a perfect fit. But it is a good start.
For a great review of the Dirichlet Process/CRP, the Indian Buffet Process, and other probability distributions over infinite structures, I highly recommend this great tech report from Zoubin and Tom:
I have some questions that I couldn't immediately answer from skimming either the BayesDB documentation or the paper linked from http://probcomp.csail.mit.edu/crosscat/
* The CrossCut paper seems to focus on binary features and categorical learning. How does BayesDB generalize that? Does it quantize continuous features first to make it all categorical, or does it generalize CrossCut somehow?
* How are we to think about what BayesDB doing? Is the underlying model most similar to a graphical model? A Bayesian network? A Markov field?
* On an informal level, how is the factorization structure learned?
* What's the time and memory complexity in terms of number of features and examples for different operations? Is insertion constant time? Is it storing sparse contingency tables of some kind?
While the original CrossCat paper focused on binary features, it is in fact much more general. For example, CrossCat uses a beta-bernoulli model for binary features, normal-gamma for continuous, and dirichlet-multinomial for categorical data.
CrossCat is a generative bayesian nonparametric probabilistic model. Informally, the generative process assumed by CrossCat is that the columns are clustered (into "views") according to a Dirichlet Process, then the rows within each view are clustered by another Dirichlet Process. Then, the data is generated by the datatype-appropriate component model for each cluster.
INFER, SIMULATE, and INSERT are all constant time, and most other operations scale linearly with the number of rows or columns, including inference. It doesn't store any sparse contingency tables or anything like that -- all it stores are CrossCat posterior samples.
However, the great thing about the Bayesian Query Language (BQL, BayesDB's extension of SQL) is that it can be implemented by any joint density estimator. So, you could implement BayesDB with Bayes net structure learning, kernel density estimation, or almost anything else instead of CrossCat, if you wanted.
Or to use another example, can it learn correlations between two continuous variables, to solve things like linear regression?
I'm quite familiar with generative models and MCMC sampling and reasonably familiar with the Dirichlet process though I've never implemented it.
I would love to see a full set of QL primitives for common data science operations.
So far, we have been focusing on smaller dataset sizes, such as 10,000 rows by 100 columns, but everything scales linearly (both query processing and offline inference) so you could use it for larger datasets too. The current version is all in memory, though, so you're limited there.
Right now you must import data from csv, so no images, and you must do all preprocessing of your data before loading it in. We hope to add more and more of this kind of functionality in later releases. I'd love to hear suggestions! I recommend trying out the VM installation if you want to quickly play around with it.
Yes, the install process is a pain in the current release (sorry!), but the next release (almost ready) will be much more friendly and granular to install.
That said, BayesDB is really about the classic multivariate statistics setting: each row is a sample from some population. We think that a streaming Bayesian database, that models sequences of timestamped UPDATEs to a DB (and with FORECAST in addition to INFER) is an interesting, distinct project that we've done a little work on.
Contact us if you're interested in this kind of data and we'd be happy to talk more.