We establish a theoretical link between evolutionary algorithms and variational parameter optimization of probabilistic generative models with binary hidden variables. While the novel approach is independent of the actual generative model, here we use two such models to investigate its applicability and scalability: a noisy-OR Bayes Net (as a standard example of binary data) and Binary Sparse Coding (as a model for continuous data). Learning of probabilistic generative models is first formulated as approximate maximum likelihood optimization using variational expectation maximization (EM). We choose truncated posteriors as variational distributions in which discrete latent states serve as variational parameters. In the variational E-step, the latent states are then optimized according to a tractable free-energy objective. Given a data point, we can show that evolutionary algorithms can be used for the variational optimization loop by (A) considering the bit-vectors of the latent states as genomes of individuals, and by (B) defining the fitness of the individuals as the (log) joint probabilities given by the used generative model. As a proof of concept, we apply the novel evolutionary EM approach to the optimization of the parameters of noisy-OR Bayes nets and binary sparse coding on artificial and real data (natural image patches). Using point mutations and single-point cross-over for the evolutionary algorithm, we find that scalable variational EM algorithms are obtained which efficiently improve the data likelihood. In general we believe that, with the link established here, standard as well as recent results in the field of evolutionary optimization can be leveraged to address the difficult problem of parameter optimization in generative models.
## Review summary
Overall, the paper makes an interesting effort to tightly integrate
expectation-maximization (EM) training algorithms with evolutionary algorithms
(EA). However, I found the technical description lacking key details and the
experimental comparisons inadequate. There were no comparisons to non-
evolutionary EM algorithms, even though they exist for the models in question.
Furthermore, the suggested approach lacks a principled way to select
and tune key hyperparameters. I think the broad idea of using EA as a substep
within a monotonically improving free energy algorithm could be interesting,
but needs far more experimental justification.
## Pros / Stengths
+ effort to study more than one model family
+ maintaining monotonic improvement in free energy
## Cons / Limitations
- poor technical description and justification of the fitness function
- lack of comparisons to other, non-EA algorithms
- lack of study of hyperparameter sensitivity
## Paper summary
The paper suggests a variant of the EM algorithm for binary hidden variable
models, where the M-step proceeds as usual but the E-step is different in two
ways. First, following work by J. Lucke et al on Truncated Posteriors, the
true posterior over the much larger space of all possible bit vectors is
approximated by a more tractable small population of well-chosen bit vectors,
each with some posterior weight. Second, this set of bit vectors is updated
using an evolutionary/genetic algorithm. This EA is the core contribution,
since the work on Trucated Posteriors has appeared before in the literature.
The overall EM algorithm still maintains monotonic improvement of a free
energy objective.
Two well-known generative models are considered: Noisy-Or models for discrete
datasets and Binary Sparse Coding for continuous datasets. Each has a
previously known, closed-form M-step (given in supplement). The focus is on
the E-step: how to select the H-dimensional bit vector for each data point.
Experiments on artificial bars data and natural image patch datasets compare
several variants of the proposed method, while varying a few EA method
substeps such as selecting parents by fitness or randomly, including crossover
or not, or using generic or specialized mutation rates.
## Significance
Combining evolutionary algorithms (EA) within EM has been done previously, as
in Martinez and Vitria (Pattern Recog. Letters, 2000) or Pernkopf and
Bouchaffra (IEEE TPAMI, 2005) for mixture models. However, these efforts seem
to use EA in an "outer loop" to refine different runs of EM, while the present
approach uses EA in a substep of a single run of EM. I guess this is
technically different, but it is already well known that any E-step method
which monotonically improves the free energy is a valid algorithm. Thus, the
paper's significance hinges on demonstrating that the particular E step chosen
is better than alternatives. I don't think the paper succeeded very well at
this: there were no comparisons to non-EA algorithms, or to approaches that
use EA in the "outer loop" as above.
## Clarity of Technical Approach
What is \tilde{log P} in Eq. 7? This seems a fundamental expression. Its
plain-text definition is: "the logarithm of the joint probability where
summands that do not depend on the state s have been elided". To me, this
definition is not precise enough for me to reproduce confidently... is it just
log p(s_n, y_n | theta)? I suggest revisions include a clear mathematical
definition. This omission inhibits understanding of this paper's core
contributions.
Why does the fitness expression F defined in Eq. 7 satisfy the necessary
condition for fitness functions in Eq. 6? This choice of fitness function does
not seem intuitive to me. I think revisions are needed to *prove* this fitness
function obeys the comparison property in Eq. 6.
How can we compute the minimization substep in Eq. 7 (min_s \tilde{logP})? Is
this just done by exhaustive search over bit vectors? I think this needs
clarification.
## Quality of Experiments
The experiments are missing a crucial baseline: non-EA algorithms. Currently
only several varieties of EA are compared, so it is impossible to tell if the
suggested EA strategies even improve over non-EA baselines. As a specific
example, previous work already cited in this paper -- Henniges et al (2000) --
has developed a non-EA EM algorithm for Binary Sparse Coding, which already
uses the truncated posterior formulation. Why not compare to this?
The proposed algorithm has many hyperparameters, including number of
generations, number of parents, size of the latent space H, size of the
truncation, etc. The current paper offers little advice about selecting these
values intelligently, but presumably performance is quite sensitive to these
values. I'd like to see some more discussion of this and (ideally) more
experiments to help practitioners know which parameters matter most,
especially in the EA substep.
Runtime analysis is missing as well: Is runtime dominated by the EA step? How
does it compare to non-EA approaches? How big of datasets can the proposed
method scale to?
The reader walks away from the current toy bars experiment somewhat confused.
The Noisy-Or experiment did not favor crossover and and favored specialized
mutations, while the BSC experiment reached the opposite conclusions. How does
one design an EA for a new dataset, given this knowledge? Do we need to
exhaustively try all different EA substeps, or are there smarter lessons to
learn?
## Detailed comments
Bottom of page 1: I wouldn't say that "variational EM" is an approximation to
EM. Sometimes moving from EM to variational EM can mean we estimate posteriors
(not point estimates) for both local (example-specific) and global parameters.
Instead, the *approximation* comes simply from restricting the solution space
to gain tractability.
Sec. 2: Make clear earlier that hidden var "s" is assumed to be discrete, not
continuous.
After Mutation section: Remind readers that "N_g" is number of generations