DIANA CAI

A Bayesian nonparametric view on count-min sketch

(with Michael Mitzenmacher and Ryan P. Adams).

The count-min sketch is a computationally-efficient randomized data structure that provides a point estimate of the number of times an item has appeared in a data stream. We present a Bayesian nonparametric view on the count-min sketch, using the same data structure, but providing a posterior distribution over the frequencies that characterizes the uncertainty arising from the hash-based approximation. We take a nonparametric approach and consider tokens generated from a from a Dirichlet process random measure, which allows for an unbounded number of unique tokens.
Advances in Neural Information Processing Systems (NIPS), 2018.
pdf spotlight video

Finite mixture models are typically inconsistent
for the number of components

(with Trevor Campbell and Tamara Broderick).

A generative model is a vast simplification of the complex real-world phenomena that govern any observed data set, and for any model of a real-world data set, model misspecification is necessary for tractable data analysis. But model misspecification can also lead to fundamentally inaccurate, misleading, or uninterpretable inferences. We study finite mixture models with a prior on the number of components under misspecification of the mixture family, focusing on the (in)consistency and finite-sample properties of the posterior on the number of components, and we discuss the implications of misspecification for cluster analysis.

Exchangeable trait allocations

(with Trevor Campbell and Tamara Broderick).

We study exchangeable trait allocations, a class of combinatorial models that generalizes partitions, feature allocations, and more. In this work, we characterize the class of exchangeable trait allocations, which we call the trait paintbox. We also characterize a subclass of models particularly amenable to MCMC and variational inference algorithms. We show how constrained trait allocations can be applied to graphs as a generalization of edge-exchangeable graphs and hypergraphs; additional details can be found here.
Electronic Journal of Statistics, 2018.
pdf arxiv

Efficient variational approximations for
online Bayesian changepoint detection

We develop a scalable method for online changepoint detection in conditionally-conjugate latent variable models, detecting global changes in the latent components. We develop a scalable online variational inference algorithm that adaptively decreases the number of sufficient statistics, and demonstrate inference on mixture models and topic modeling applications.
github

Edge-exchangeable graphs: sparsity, power laws,
paintboxes, and probability functions

(with Trevor Campbell and Tamara Broderick).

We study edge exchangeability; here the order of the edges does not affect the distribution of the graph. We show that, unlike many popular graph models that are traditionally vertex exchangeable, that edge exchangeability admits sparsity and power laws. We also characterize the class of edge-exchangeable graphs and a subclass that is particular amenable to posterior inference.

Edge-exchangeable graphs and sparsity.
Advances in Neural Information Processing Systems (NIPS), 2016.
pdf arXiv spotlight video poster

Paintboxes and probability functions for edge-exchangeable graphs.
NIPS Workshop on Adaptive and Scalable Nonparametric Methods in Machine Learning, 2016. pdf slides poster

Priors on exchangeable directed graphs

(with Nate Ackerman and Cameron Freer).

Exchangeable directed graphs are characterized by a sampling procedure given by the Aldous-Hoover theorem, determined by specifying a distribution on measurable objects known as digraphons. We present a new Bayesian nonparametric model for exchangeable directed random graphs.
Electronic Journal of Statistics (EJS), 2016.
pdf arXiv slides poster

Iterative step-function estimation for graphons

(with Nate Ackerman and Cameron Freer).

We present a method for estimating graphons (symmetric, measurable functions from which we can sample exchangeable random graphs) by iteratively refining a partition. Here we compute the similarity of vertices based on their respective neighborhoods with repsect to the previous partition's edge densities. A step-function estimator is then obtained by grouping vertices by taking the average edge density across each pair of classes in the partition.
pdf arXiv poster

The Ratio Project: Analyzing Online Recipes

We analyzed online recipes using computational methods and exploratory visualizations.
"A food pyramid made of cookies." The Boston Globe, Dec 2011. link
(with Elaine Angelino and Michael Brenner)
Cocktails Visualization, Jun 2013.
(with Elaine Angelino, Gabrielle Ehrlich, Brent Heeringa, Michael Mitzenmacher, Naveen Sinha).