# 论文阅读 · Hinge-Loss Markov Random Fields and Probabilistic Soft Logic


## 基础信息
* 作者：Stephen H. Bach, Matthias Broecheler, Bert Huang, Lise Getoor
* 期刊/日期：Journal of Machine Learning Research 18 (2017) 1-67；Submitted 12/2015, Revised 12/2016, Published 10/2017
* 核心贡献：提出 Hinge-Loss Markov Random Fields (HL-MRFs) 和 Probabilistic Soft Logic (PSL)，用连续 [0,1] 变量、hinge/squared hinge loss 与一阶逻辑式规则统一表达结构化依赖，并用 ADMM MAP 推理和多种权重学习方法实现大规模可扩展建模。

## Q1. 研究动机

许多机器学习问题既结构复杂又规模很大，例如社交网络、知识图谱、Web、图像和自然语言。传统结构化模型越表达丰富，推理和学习越难扩展；作者希望找到一个兼具逻辑表达能力和大规模凸推理效率的建模形式。

## Q2. 核心问题

论文要解决的问题是：如何用一种统一框架表达离散、连续或混合的关系型结构依赖，同时让 MAP 推理保持凸优化并能在大规模数据上高效运行。它不是单纯提出一个新规则语言，而是把规则语言、概率图模型和可扩展推理算法绑定在同一形式下。

## Q3. 现有不足 & 本文改进

作者批评的核心不足有三类。第一，离散 MRF/MLN 能表达逻辑依赖，但 MAP 推理通常困难，常需要采样或搜索，难以扩展到大型结构化数据。第二，通用凸优化工具如 interior-point methods 虽能求解松弛问题，却没有利用图模型的稀疏依赖结构，面对大规模 HL-MRF 式问题会很慢。第三，一些统计关系学习和 ILP 方法要么难以处理不确定性，要么表达能力、推理算法和建模便利性之间不能兼顾。

本文的改进是：把 MAX SAT 松弛、离散 MRF 的 local consistency relaxation 和 Lukasiewicz fuzzy logic 统一到同一类凸目标；在此基础上定义 HL-MRF，用 [0,1] 连续变量和 hinge/squared hinge loss 表示软约束；再定义 PSL 作为一阶逻辑风格的概率编程语言，把逻辑规则、算术规则、domain/range 规则、similarity、prior、blocking、aggregate 等模式编译成 HL-MRF。算法上，作者用 ADMM 做可分解的精确 MAP 推理，并给出 lazy MAP inference、structured perceptron、MPLE 和 large-margin estimation 等学习方法。

## Q4. 方法流程

输入是 PSL 程序、常量集合、观测谓词、待预测谓词和一组带权规则。PSL 先把规则按数据集 grounding 成 HL-MRF：每个未观测 atom 变成 [0,1] 上的连续随机变量，每条带权规则变成 hinge 或 squared hinge loss，硬规则变成必须满足的线性约束。预测时，MAP 推理把全局问题拆成许多与势函数或约束相关的局部子问题，并通过 ADMM 在局部变量和全局共识变量之间迭代；若大量 ground potentials 在最优解中为零，还可用 lazy inference 从小子模型开始逐步加入违反项。训练时，规则模板共享权重，作者分别用 structured perceptron、maximum pseudolikelihood 和 large-margin estimation 学权重。输出是每个目标 atom 的连续置信值，必要时再转成类别、链接强度、评分或像素值。

## Q5. 实验设计与结论

- 理论统一实验/分析：Section 2 分析 MAX SAT relaxation、local consistency relaxation 和 Lukasiewicz logic，证明它们导向同一种凸优化目标。目的在于说明 HL-MRF 不是任意构造，而是对多个已有可扩展推理视角的统一和推广。

- MAP inference scalability：作者生成 22k 到 66k 顶点的社交网络，诱导 130k 到 397k 个 potentials 和 constraints，比较 ADMM 与 MOSEK interior-point method。Figure 1 显示，在 piecewise-linear MAP 中，最大问题上 IPM 平均约 2,200 秒，而 ADMM 约 70 秒，运行时间线性拟合 R2 = 0.9972；在 piecewise-quadratic MAP 中，IPM 只能跑三个最小问题，第三个约 21k 秒，ADMM 在最大问题仍约 70 秒，R2 = 0.9854。修复 infeasibility 后，ADMM 相对误差为 0.2% 到 0.4%。

- Node labeling：在 Cora 和 Citeseer 上进行 citation network 分类，比较 HL-MRF 与离散 MRF。Table 1 中，Citeseer 上 HL-MRF-Q (SP/MPLE) 和 HL-MRF-L (MPLE) 均为 0.729，高于最好的 MRF(MPLE) 0.715；Cora 上 HL-MRF-Q (MPLE) 为 0.818，高于最好的 MRF(MPLE) 0.797。结论是 HL-MRF 保持或提升分类准确率。

- Link labeling / social trust prediction：在 Epinions signed trust network 上做八折交叉验证。Table 2 中，HL-MRF-Q (MPLE) 在 ROC 0.832、P-R(+) 0.979、P-R(-) 0.482 上整体最好；MRF(LME) 的 P-R(+) 0.973 和 P-R(-) 0.441 接近但不超过最优。作者还指出 squared HL-MRF 在三个指标上显著更高。

- Inference time comparison：Table 3 显示单线程推理时间差距极大。Citeseer 上 HL-MRF-Q 0.42 秒、HL-MRF-L 0.46 秒，而 MRF 110.96 秒；Cora 上 HL-MRF-Q 0.70 秒、HL-MRF-L 0.50 秒，而 MRF 184.32 秒；Epinions 上 HL-MRF-Q 0.32 秒、HL-MRF-L 0.28 秒，而 MRF 212.36 秒。结论是凸推理相比离散采样具有明显扩展优势。

- Preference prediction：在 Jester 数据集上预测笑话评分，比较 HL-MRF 与 BPMF。Table 4 中 BPMF 最好，NMSE 0.0501、NMAE 0.1832；最接近的 HL-MRF 是 HL-MRF-L (MPLE) NMSE 0.0535 和 HL-MRF-L (LME) NMAE 0.1875。作者说明 BPMF 在 NMAE 上对 HL-MRF-L (LME) 的提升不显著。结论是 HL-MRF 可处理连续偏好预测，但并非在该任务上绝对最好。

- Image completion：在 Caltech101 faces 和 Olivetti faces 上做左半/下半图像补全。Table 5 中，HL-MRF-Q (SP) 在 Caltech-Left 1741、Caltech-Bottom 1910、Olivetti-Left 927 上优于 SPN/DBM/DBN/PCA/NN；但 Olivetti-Bottom 中 SPN 为 918，优于 HL-MRF 的 1226。Figure 2 的定性分析显示，HL-MRF 往往生成较模糊但亮度一致的补全，SPN 有时会 hallucinate different faces。

## Q6. 局限性

作者明确提到：

- Conclusion/Future work 中指出，需要进一步研究 HL-MRF MAP states 对离散模型 MAP 的近似保证，尤其是超出已有 rounding guarantees 的情形。
- 作者明确把 marginal inference 和 sampling from HL-MRFs 列为重要未来方向；当前论文主要围绕 MAP 推理展开，不能完整覆盖概率不确定性查询。
- Large-margin estimation 部分说明，当 ground truth 值位于 (0,1) 内部时，loss-augmented inference 会涉及非凸目标，作者使用 difference of convex functions algorithm 找局部最优。

以下为分析归纳，非原文明确说明：

- HL-MRF 使用连续 [0,1] 变量来表示离散、连续或混合状态；当任务本质上是离散类别时，仍需要解释、阈值化或取最大值，这可能带来校准问题。
- PSL 的规则设计依赖领域知识，实验中的规则多由研究者手工构造；若结构依赖写错或遗漏，模型表现会受影响。
- 虽然 ADMM 推理很快，但大规模 PSL grounding 仍可能造成存储和构图压力，lazy inference 只是缓解而非彻底消除。
- 实验比较对象主要是离散 MRF、BPMF、SPN/DBM/DBN/PCA/NN 等，当作 2017 年前后的基准是合理的，但不能说明相对现代 GNN、神经协同过滤或神经符号模型仍有优势。

## Q7. 学术价值

- 理论价值：HL-MRF 把 Boolean logic、probabilistic graphical models 和 fuzzy logic 的若干可扩展推理形式统一到同一个凸 hinge-loss 能量框架中，明确了表达能力与可优化性之间的折中点。
- 方法价值：PSL 提供了可复用的概率规则语言；ADMM MAP、lazy inference、SP/MPLE/LME 学习方法构成一套完整工具链，使用户能快速修改规则并重复推理、学习。
- 应用价值：可落地于知识图谱补全、社交网络推断、信任预测、推荐系统、图像补全、信息抽取、自然语言语义、药物发现等关系型结构预测任务。

## Q8. 延伸研究方向

1. 如何给出更一般的理论保证，说明 HL-MRF 的连续 MAP 解何时能近似离散 MRF/MLN 的 MAP 解？
2. 如何为 HL-MRF 设计高效 marginal inference 和 sampling 算法，使其不仅能做 MAP 预测，也能给出可靠不确定性估计？
3. 如何自动学习 PSL 规则结构，减少领域专家手工写规则的负担，并避免错误规则导致系统性偏差？
4. 如何进一步降低 grounding 成本，尤其是在知识图谱、Web-scale 网络或高阶关系规则下？
5. 如何把 PSL/HL-MRF 与神经表示学习结合，例如用神经模型产生 soft evidence，再由 HL-MRF 执行可解释约束推理？

## Q9. 反直觉发现与方法失效分析

- Table 4 中，HL-MRF 在 Jester preference prediction 上没有击败 BPMF。BPMF 的 NMSE/NMAE 为 0.0501/0.1832，而最好的 HL-MRF NMSE 是 HL-MRF-L (MPLE) 的 0.0535，最好的 HL-MRF NMAE 是 HL-MRF-L (LME) 的 0.1875。
  - 作者解释 / 作者未讨论：作者承认 BPMF 分数最好，并补充 BPMF 相比 HL-MRF-L (LME) 的 NMAE 提升不显著。这个结果说明 HL-MRF 的优势不在所有连续预测任务上都压过专门的 latent factor model。

- Table 5 中，HL-MRF 在 Olivetti-Bottom 图像补全上失败于 SPN：HL-MRF-Q (SP) 的 MSE 为 1226，而 SPN 为 918。
  - 作者解释 / 作者未讨论：作者讨论了 bottom-half face reconstruction 本身较难，并指出 SPN 与 HL-MRF 的定性差异：SPN 可能生成不同脸和 artifacts，HL-MRF 更倾向于生成亮度一致但模糊的形状。因此 HL-MRF 的图像补全优势是数据集和遮挡方向相关的。

- Table 1 中，Large-margin estimation 在 node labeling 上明显弱于 SP/MPLE。Citeseer 上 HL-MRF-Q (LME) 为 0.683、HL-MRF-L (LME) 为 0.695，而 HL-MRF-Q (SP/MPLE) 和 HL-MRF-L (MPLE) 均达到 0.729；Cora 上 LME 为 0.789，低于 HL-MRF-Q (MPLE) 的 0.818。
  - 作者解释 / 作者未讨论：作者没有对这个具体退化给出详细解释。结合 Section 6.3，LME 在连续输出和 squared potentials 下有额外复杂性与 slack tradeoff，可能导致该任务上不如更直接的 SP/MPLE。

- Table 2 中，linear HL-MRF 明显弱于 squared HL-MRF。HL-MRF-L (MPLE) 的 ROC/P-R(+)/P-R(-) 为 0.757/0.963/0.333，而 HL-MRF-Q (MPLE) 为 0.832/0.979/0.482。
  - 作者解释 / 作者未讨论：作者明确指出 squared potentials 在三个 trust prediction 指标上显著更高。这支持论文前面对 squared hinge loss 的动机：在冲突证据和硬约束下，squared loss 更能反映相对证据强度。

- 整体评价：论文对“可扩展推理”的证据非常强，尤其 Figure 1 和 Table 3 展示了数量级差异；但预测性能不是全任务碾压，推荐和部分图像补全任务显示 HL-MRF 的优势是条件性的。更稳妥的结论是：HL-MRF/PSL 在结构化关系建模中提供了非常有价值的 expressivity-scalability tradeoff，而不是替代所有专门模型。


---

> Author: [Ting](Tin10g.github.io)  
> URL: http://localhost:1313/posts/%E8%AE%BA%E6%96%87%E9%98%85%E8%AF%BB-hinge-loss-markov-random-fields-and-probabilistic-soft-logic/