Kernel counting is a geometric approach to holographic algorithms that explores the power of evaluating partition functions through geometrically-motivated kernels. It remains an open question whether the apparent additional power of quantum computation derives inherently from quantum mechanics, or merely from the flexibility obtained by ``lifting'' Boolean functions to linear operators and evaluating their composition cleverly. Holographic algorithms provide a useful avenue for exploring this question.

In Pfaffian Circuits, we describe a new, simplified construction of holographic algorithms in terms of Pfaffian circuits. Novel proofs of some key results are provided, and we extend our approach in Holographic algorithms without matchgates to nonsymmetric, odd, and homogenized signatures, circuits, and various models of execution flow. This shows our approach is as powerful as the matchgate approach and allows us to derive some interesting new algorithms.
Sponsor: DARPA.

While DBNs are a promising class of machine learning models, their representational power and performance characteristics are poorly understood. We are investigating the algebraic geometry of the space of probability distributions they can model and the polyhedral and tropical geometry of the space of functions they can compute. Goals include precisely characterizing the trade-offs among different choices of network shape in terms of geometry, representational power, numerical stability, and learning rate. In Geometry of the restricted Boltzmann machine, we showed that the one-layer restricted Boltzmann machine architecture is already optimal in terms of dimension in most cases. In When Does a Mixture of Products Contain a Product of Mixtures? we find that an exponentially larger mixture model, requiring an exponentially larger number of parameters, is required to represent the distributions that can be represented by the restricted Boltzmann machine. Other work on the algebraic statistics of discrete graphical models includes Graphical models for correlated default and Equations defining hidden markov models.
Sponsor: DARPA.

Covariance matrices, and methods for estimating and modeling them, are very well studied. When the probability distribution in question is multivariate normal, the first two cumulants (the mean vector and covariance matrix) tell the whole story. However, for non-Gaussian distributions, simply studying covariance gives an incomplete picture. Extending the expansion a few terms gives the $p \times p \times p$ skewness tensor, the $p \times p \times p \times p$ kurtosis tensor, and so on. We are building multilinear factor models of cumulant tensors and studying the associated statistical theory in order to extend useful strategies for covariance modeling to non-Gaussian dependence structures.
Sponsor: NSF.

In Convex rank tests and semigraphoids, we established a bijection between coarsenings of the $S_n$-fan and probabilistic conditional independence structures known as semigraphoids. This was exploited in Three counterexamples on semigraphoids to provide counterexamples to several open problems. In The Cyclohedron test for finding periodic genes, we used the technique to develop a novel procedure for periodic gene detection.

In Relations among conditional probabilities, we found the algebraic relations that must hold among discrete conditional probabilities. In this paper, we also develop a multigraded moment map which has proven useful in establishing the existence of maximum likelihood estimators for random graph models and other exponential families with a multigraded structure.