We consider the MAP-inference problem for graphical models, which is a valued
constraint satisfaction problem defined on real numbers with a natural
summation operation. We propose a family of relaxations (different from the
famous Sherali-Adams hierarchy), which naturally define lower bounds for its
optimum. This family always contains a tight relaxation and we give an
algorithm able to find it and therefore, solve the initial non-relaxed NP-hard
problem.
The relaxations we consider decompose the original problem into two
non-overlapping parts: an easy LP-tight part and a difficult one. For the
latter part a combinatorial solver must be used. As we show in our experiments,
in a number of applications the second, difficult part constitutes only a small
fraction of the whole problem. This property allows to significantly reduce the
computational time of the combinatorial solver and therefore solve problems
which were out of reach before.

针对基于图模型的最大后验概率推断问题，本研究提出了一系列不同于 Sherali-Adams 层次结构的松弛方法，将问题分解为一个简单的 LP-tight 部分和一个困难的组合求解器部分，实验证明对小部分问题可以显著降低计算时间。

通过 LP 松弛约束组合搜寻实现精确 MAP 推断

Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation

We consider general discrete Markov Random Fields(MRFs) with additional
bottleneck potentials which penalize the maximum (instead of the sum) over
local potential value taken by the MRF-assignment. Bottleneck potentials or
analogous constructions have been considered in (i) combinatorial optimization
(e.g. bottleneck shortest path problem, the minimum bottleneck spanning tree
problem, bottleneck function minimization in greedoids), (ii) inverse problems
with $L_{\infty}$-norm regularization, and (iii) valued constraint satisfaction
on the $(\min,\max)$-pre-semirings. Bottleneck potentials for general discrete
MRFs are a natural generalization of the above direction of modeling work to
Maximum-A-Posteriori (MAP) inference in MRFs. To this end, we propose MRFs
whose objective consists of two parts: terms that factorize according to (i)
$(\min,+)$, i.e. potentials as in plain MRFs, and (ii) $(\min,\max)$, i.e.
bottleneck potentials. To solve the ensuing inference problem, we propose
high-quality relaxations and efficient algorithms for solving them. We
empirically show efficacy of our approach on large scale seismic horizon
tracking problems.

使用瓶颈势函数作为最大势值的惩罚项，提出基于最大后验概率（MAP）推理的马尔可夫随机场模型，通过高质量放松和有效的算法解决推理问题，并在大规模地震层跟踪问题上证明了方法的有效性。

Markov 随机场中的瓶颈潜力

Bottleneck potentials in Markov Random Fields

We consider the problem of distribution-free predictive inference, with the
goal of producing predictive coverage guarantees that hold conditionally rather
than marginally. Existing methods such as conformal prediction offer marginal
coverage guarantees, where predictive coverage holds on average over all
possible test points, but this is not sufficient for many practical
applications where we would like to know that our predictions are valid for a
given individual, not merely on average over a population. On the other hand,
exact conditional inference guarantees are known to be impossible without
imposing assumptions on the underlying distribution. In this work we aim to
explore the space in between these two, and examine what types of relaxations
of the conditional coverage property would alleviate some of the practical
concerns with marginal coverage guarantees while still being possible to
achieve in a distribution-free setting.

本文考虑面向分布无关的预测推断问题，目标是生成有条件而非边缘的预测覆盖保证。我们旨在探索边缘覆盖保证的实际问题，并研究一些能够缓解一些实际关注的条件覆盖性质松弛类型，同时仍能在分布无关的环境下实现。