Hacker News Reader

Comment by taliesinb | Hacker News Reader

Interesting project!

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?

View on HN

Thanks!

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.

What about the individual cluster models -- can they represent dependencies of variables within a cluster? For instance, I'm thinking about the "salary prediction" example. Is the salary variable considered to be conditionally independent of all the other variables, given the cluster assignment? Or can it learn something like an additive model, where categorical variables are associated with higher or lower salaries within a cluster?

Or to use another example, can it learn correlations between two continuous variables, to solve things like linear regression?

You are correct that each variable is considered conditionally independent of the other variables given the cluster assignment. CrossCat learns additive models and correlations between continuous variables by using many clusters (the clusters don't necessarily have meaningful real-world interpretations).

Does this mean that it always uses CrossCat for predictions, or is there some other mechanism?

Ah, good question. Currently, it's implemented to only use CrossCat for predictions.

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.

Sounds great

Reply on news.ycombinator.com