linear response can be computed exactly in respectively O(N) and $O(N^2)$ operations, thanks to a dual weight propagation (DWP) message passing procedure that we set up. When restricted to this subclass of models, the inverse Ising problem being convex, becomes tractable at any temperature. Experimental tests on various datasets with refined $L_0$ or $L_1$ regularization procedures indicate that these approaches may be competitive and useful alternatives to existing ones.'
author:
- Cyril Furtlehner
- Yufei Han
- 'Jean-Marc Lasgouttes'
- Victorin Martin
bibliography:
- 'invising.bib'
title: Pairwise MRF Calibration by Perturbation of the Bethe Reference Point
---

Introduction
============

The problem at stake is a model selection problem, in the MRF families, where $N$ variables are observed pair by pair. The optimal solution is the MRF with maximal entropy obeying moment constraints. For binary variables, this happens then to be the Ising model with highest log-likelihood. It is a difficult problem, where both the graph structure and the values of the fields and couplings have to be found. In addition, we wish to ensure that the model is compatible with the fast inference algorithm “belief propagation” (BP) to be useful at large scale for real-time inference tasks. This leads us 