EDML for Learning Parameters in Directed and Undirected Graphical Models
EDML is a recently proposed algorithm for learning parameters in Bayesian networks. It was originally derived in terms of approximate inference on a metanetwork, which underlies the Bayesian approach to parameter estimation. While this initial derivation helped discover EDML in the first place and provided a concrete context for identifying some of its properties (e.g., in contrast to EM), the formal setting was somewhat tedious in the number of concepts it drew on. In this paper, we propose a greatly simplified perspective on EDML, which casts it as a general approach to continuous optimization. The new perspective has several advantages. First, it makes immediate some results that were non-trivial to prove initially. Second, it facilitates the design of EDML algorithms for new graphical models, leading to a new algorithm for learning parameters in Markov networks. We derive this algorithm in this paper, and show, empirically, that it can sometimes learn estimates more efficiently from complete data, compared to commonly used optimization methods, such as conjugate gradient and L-BFGS.
Summary: Overall, I think the paper is potentially 
      useful and a contribution to the community since it puts forth a simpler 
      framework for EDML (the previous works on EDML are quite dense). However, 
      I was disappointed that it presented it in a confusing manner and that it 
      didn't address a number of key issues such as convergence, relationship to 
      EM, etc. Further, the contribution to parameter estimation for undirected 
      models is quite incremental. Contribution: This paper portrays 
      EDML as fixed-point iteration where fixed points correspond to stationary 
      points of the log likelihood. Each iteration requires performing inference 
      and has a notion of soft evidence, like EM. Their application to 
      complete-data learning for Markov networks reduces to some Jacobi-style/ 
      coordinate descent-type method for the convex log likelihood and can be 
      used as a black-box optimizer for Markov networks. Novelty: 
      The connection between EDML and continuous optimization is novel. 
      However, the literature on alternatives to EM is vast, and I'm not sure 
      how novel it is as a learning method under missing data. For complete-data 
      Markov networks, the method is similar to basic, known methods for convex 
      optimization. Pros: Attractive method for learning in the 
      presence of missing data that points to fertile ground for future work. 
      Unified treatment of directed and undirected graphical models is also 
      interesting and potentially impactful. Many practitioners would benefit 
      from reading the paper in order to think about alternative perspectives on 
      parameter learning in the presence of unobserved data. Cons: 
      1) The paper casts EDML as an optimization technique, but lacks 
      necessary details for readers to understand this interpretation. 2) 
      Exposition, particularly notation, is sometimes confusing. 3) 
      insufficient conceptual or experimental comparison to EM. 4) 
      experiments only address an overly simple case of parameter learning 
      problems (complete data). 1) I found section 2 very confusing. It 
      first appears as though you're introducing some new family of optimization 
      algorithms, but then it becomes apparent that you're discussing the 
      general family of techniques described in the first paragraph of the 
      related work section. I would reshape this section to first state that 
      such a family exists and discuss their convergence properties. Then, I'd 
      state that for the particular class of problems you're dealing with, these 
      coordinate-wise minimizations are tractable. Claim1 is boring, and more 
      space should be made for previewing the sort of content discussed in the 
      first paragraph of the related work section. The paper also lacks 
      a formal discussion of convergence behavior for the method. How do we know 
      that the update rule at the top of page 5 will converge? I agree that its 
      fixed points are fixed points of the marginal likelihood, but how do we 
      know it will ever converge to one of these? This issue would be remedied 
      if you were much more straightforward in section 2 about what you need for 
      such coordinate minimization techniques to converge. Fixed point iteration 
      is not guaranteed to converge, you need some sort of contraction. See 
      proofs, for example, about the convergence of loopy belief propagation. 
      Why does section 3.4 have the title 'Finding the Unique Optimum?" 
      The subfunctions are convex, so each of them has a unique minimizer. 
      However, the overall problem doesn't have a unique stationary point, and 
      the algorithm you present in this section is for finding such a point. I 
      understand that the updates at the top of page 5 are obtained by 
      analytically minimizing simultaneously in every coordinate (where you find 
      a unique minimum), but the title is very confusing. 2) The 
      notation in section 3.2 (soft evidence) needs to be defined much more 
      clearly. In equation (3) is there implicitly a sum over possible values 
      that X_i can take on? I don't understand how you can get a marginal 
      likelihood without summing over the possible values for each X_i. What's 
      the difference between P(\eta_i|x) and P(X_i|x)? The corresponding 
      appendix does not clear things up either. Furthermore, I didn't find 3.2 
      particularly illuminating about the method without some comparison to 
      'soft evidence' in EM. Also, it's strange that you present an 
      algorithm at the top of page 5 based on an earlier work and leave it to 
      the reader to deduce that this can also be obtained by applying the 
      procedure from page 2 to the log likelihood. You should, at the very 
      least, say that the updates at the top of page 5 correspond to exact 
      simultaneous minimization of the subfunctions. You should also discuss 
      under what conditions such fixed point iteration will converge. 3) 
      In general, I'd like to see much more discussion about the relationship 
      between EDML and EM. EM has some desirable properties (monotonicity of the 
      updates) and some downsides (it's maximizing a concave lower bound on the 
      marginal likelihood rather than the actual likelihood). It would be good 
      to juxtapose these with the properties of EDML. Of course it would have 
      been nice to see experiments comparing the two as well. 4) The 
      experiments section only considers complete-data learning, in which the 
      log likelihood is convex. In this setting EDML is just another convex 
      optimization method, so a much more rigorous discussion of its convergence 
      behavior, memory requirements, per-iteration complexity, robustness to 
      errors in approximate inference, etc. is necessary. For future work, I 
      would make sure to do experiments with missing data and compare to EM. The 
      two methods are not guaranteed to converge to the same value of the 
      marginal likelihood, so comparing solution quality, and not just time, is 
      necessary. Minor points What exactly is the semantics of your 
      feasibility function g(y)? Are you always assuming it's a projection onto 
      the feasible set? Is the feasibility function you use in If you don't, g() 
      isn't guaranteed to give you what you want. First, you make it sound like 
      a projection function onto a feasible set, but then you use it as an 
      indicator function for the set? You should define somewhere early on 
      what EDML stands for. Is this technique stable if doing exact 
      inference in the bayes net is intractable? Discussion or experimental 
      evaluation in this setting would be useful. The update equation at the 
      top of page 5 should have a number. ----- Post Author Response 
      ----- In their response, the authors address many of the key omissions 
      in their paper, such as the lack of a proof of convergence, by referring 
      us to their other recent papers on EDML. This isn't quite sufficient to 
      address the confusion that will arise for future readers of the paper. 
      Some things, such as a comparison to EM can be addressed by providing a 
      pointer to the earlier papers. However, the discussion of EDML as an 
      optimization technique needs to be able to stand on its own. It is not 
      sufficient to present an optimization algorithm and not prove that it 
      converges or characterize what sorts of points it will converge to. 
      Overall, I am familiar with the modern literature on inference and 
      learning in graphical models, and this paper is not of sufficient quality 
      to be presented at NIPS. My concerns with this paper are mostly 
      presentation related. For subsequent versions of the paper, I hope the 
      authors will address the concerns that were raised. This is quite an 
      important contribution, and I hope authors will resubmit it again (if it 
      is rejected at NIPS).