This paper, "Implicit Differentiation by Perturbation" by Justin Domke, presents a surprisingly simple yet powerful technique for training discrete graphical models. It bypasses the traditional computational bottlenecks of learning by treating the inference process as a "black box" that can be differentiated through simple perturbations.
TL;DR
The paper proposes a finite-difference method to compute gradients for learning in graphical models by running the inference procedure twice on slightly perturbed parameters. This approach is algorithm-agnostic, computationally efficient, and allows researchers to optimize complex, task-specific loss functions in high-treewidth graphs where traditional methods fail.
What Problem Does This Paper Address?
In machine learning with graphical models (like Conditional Random Fields), we often want to learn parameters $\theta$ that minimize a loss function $L$. Ideally, this loss is defined over the "marginals" $\mu$ (the probabilities of variables taking certain values).
However, calculating the gradient of the loss with respect to the parameters ($\frac{dL}{d\theta}$) is notoriously difficult. For complex, "high-treewidth" graphs, exact inference is impossible, so we use approximate inference. Differentiating through these approximations usually requires either:
- Solving a massive, sparse linear system: This is computationally expensive and often numerically unstable.
- Back Belief Propagation (BBP): An efficient "automatic differentiation" style approach, but one that is strictly tied to specific algorithms (like Loopy Belief Propagation) and hard to generalize.
The gap addressed here is the need for a method that is as fast as BBP but as flexible and easy to implement as a simple finite difference.
Methods: The Perturbation Trick
The core contribution is a perturbation trick that leverages a key mathematical property: for marginal inference, the Jacobian matrix (which describes how marginals change with parameters) is symmetric.
Because of this symmetry, the total gradient of the loss can be approximated by:
- Performing standard inference to get marginals $\mu$.
- Calculating the partial derivative of the loss with respect to those marginals ($\frac{\partial L}{\partial \mu}$).
- The Perturbation: Running inference again, but with the model parameters slightly shifted (perturbed) in the direction of the loss gradient.
- Taking the difference between the "perturbed" marginals and the original marginals.
This "two-sided" finite difference approach allows the gradient to be recovered using only two calls to any existing inference engine.
Key Insights
- Symmetry is the Secret Sauce: The realization that the symmetry of the Jacobian $\frac{d\mu}{d\theta^T}$ allows a directional derivative (easy to compute via finite differences) to represent the full gradient.
- Algorithm Agnostic: Unlike previous "implicit differentiation" methods, this doesn't care how you get your marginals. Whether you use Loopy BP, Tree-Reweighted BP, or a custom solver, the perturbation method remains the same.
- Task-Specific Learning: This method makes it practical to use specialized loss functions, like Univariate Classification Error, which might be more relevant to a specific application than standard Maximum Likelihood.
Experimental Results
The paper evaluates the method using synthetic grid models to benchmark scalability, as well as image denoising and segmentation datasets to test real-world applicability.
Efficiency and Numerical Stability
The perturbation method is significantly faster than solving linear systems (the "direct" method). In tests, the direct method's time exploded as grid sizes increased, while the perturbation method scaled linearly, matching the efficiency of the specialized BBP algorithm. Furthermore, while iterative linear solvers (like symmlq) struggled and slowed down when variable interactions were strong, the perturbation method remained stable.
Accuracy on Image Tasks
On the Berkeley Segmentation dataset and corrupted image denoising tasks, optimizing for specific marginal-based losses using this method proved highly effective. For instance, training with Univariate Likelihood or Smooth Classification Error resulted in lower test errors and visually superior denoising compared to the standard "Surrogate Likelihood" approach.
Limitations and Future Work
- The Perturbation Constant ($r$): Like all finite-difference methods, choosing the step size $r$ is a balancing act. If $r$ is too large, the approximation is inaccurate; if it's too small, numerical precision errors take over. The paper suggests a heuristic, but it remains a parameter to watch.
- Local Optima: For non-convex inference (like Bethe/Loopy BP), the method assumes that the perturbed inference "tracks" the same local optimum as the original inference. If the perturbation causes the solver to jump to a different local peak, the gradient estimate could be wrong.
- Future Directions: The author suggests extending this to even more complex inference approximations, such as those used in structured prediction or dual decomposition.
Summary updated