Parameter Learning for Log-supermodular Distributions
We consider log-supermodular models on binary variables, which are probabilistic models with negative log-densities which are submodular. These models provide probabilistic interpretations of common combinatorial optimization tasks such as image segmentation. In this paper, we focus primarily on parameter estimation in the models from known upper-bounds on the intractable log-partition function. We show that the bound based on separable optimization on the base polytope of the submodular function is always inferior to a bound based on "perturb-and-MAP" ideas. Then, to learn parameters, given that our approximation of the log-partition function is an expectation (over our own randomization), we use a stochastic subgradient technique to maximize a lower-bound on the log-likelihood. This can also be extended to conditional maximum likelihood. We illustrate our new results in a set of experiments in binary image denoising, where we highlight the flexibility of a probabilistic model to learn with missing data.
This work considers the class of probabilistic models whose log-densities are supermodular.  For such models, [5] and [9] give upper-bounds "L-Field" and "Logistic", respectively, on the intractable log-partition normalizer.  This paper first shows that Logistic is always a tighter upper bound than L-Field. It then goes on to show that L-Field is also not useful for parameter learning (gives degenerate solution setting all parameters to 0), but that Logistic gives an expression for log-likelihood that can be optimized via projected stochastic gradient.  Finally, it shows that for the problem of image de-noising, even with just the noisy images available, parameter learning is possible.
Technical quality:    The math seems correct, though in general showing a few more intermediate   steps in derivations would make the work of the reader easier (can push the   proof to the supplement to make room).  In the proof of Proposition 1 for   instance, it would be nice to have more detail on how the final equality is   obtained.    The experiments compare to an SVM baseline, but not to the parameter learning   done in [9].  Specifically, [9] does parameter learning for the spin glass   model and shows that it achieves an error of 1.8% compared to an SVM's 8.2%.   What is different about the learning done in this work (besides the use of a   different probabilistic model)?  Novelty/originality: Section 4.2 is the main contribution of this work, but it does not seem like a very large delta on the work of [9].  Plugging the A_{Logistic} approximation for the partition function into the log likelihood directly yields the learning algorithm.  Potential impact or usefulness: The ability to estimate model parameters even without the original (non-noisy) images is useful.  However, experiments on more realistic data (a variety of more complex images for instance, rather than a single horse silhouette) would be better evidence of this usefulness.  Clarity and presentation: The paper is generally well-written, though, as mentioned above, a few more intermediate steps in some of the derivations would be helpful.  Additional minor notes below.  Minor notes:  Figure 1: It's hard to see the superdifferential lower bound line at all here. Maybe state in the figure caption that it is entirely covered by the logistic upper bound's line.  Experiments: The paper states "using mean marginals (which is optimal given our loss measure) lead to slightly better performance".  This is true or the supervised results (Table 1), but the opposite is true for the unsupervised results (Table 2).  Is there a logical explanation for why max-marginals does better in the unsupervised setting?  Line 92: "The method exploits" -> "This method exploits"  Line 115: "log Z" -> "log Z(f)"  Line 270: "allowing to benefit" -> "allowing us to benefit"