标签： AGI

一种基于约束的因果学习通用框架
引言

在因果推断中，因果发现是一个重要的目标，它旨在通过观察数据来揭示潜在的因果结构，即真实的因果图。然而，在缺乏干预数据的情况下，真实的因果图只能在其图形分离的基础上部分恢复。因果发现方法通常分为基于评分的方法和基于约束的方法，后者是本文关注的重点。基于约束的方法假设概率依赖结构能够很好地代表真实因果图的图形结构。一个常见的假设是“信忠性”，即数据生成分布中的每个条件独立关系都被真实因果图准确表示。在信忠性假设下，大多数基于约束的学习方法（如 PC 和 SGS 算法）被证明能够返回真实的因果图，尽管存在图形分离。然而，简单的例子表明，信忠性假设往往在实践和理论中容易被违反，因此可能过于严格。

近年来，为了放宽信忠性假设，出现了一些新的方法。例如，Raskutti 和 Uhler 提出的“稀疏排列”（SP）算法，以及 Sadeghi 和 Soo 提出的自然结构学习算法，这些算法在比信忠性更弱的假设下也能证明返回真实因果图的图形分离。本文旨在提供一个通用框架，以涵盖所有基于约束的因果学习算法的条件，并给出任何算法的条件。

约束因果学习的背景

在约束因果学习中，真实的因果图 G0 是我们希望从观察分布 P 中部分恢复的目标。因果学习算法的目标是从输入分布 P 输出图 G(P)，如果输出图 G(P) 与真实因果图 G0 是马尔可夫等价的，那么算法就是一致的。从 P 中，我们主要关注条件独立性 J(P)，通过假设条件独立性 Oracle 的可用性，我们始终知道给定的条件独立关系是否在分布中成立。

约束因果学习中的假设

在因果学习文献中，通常假设真实因果图与其观察分布之间存在关系。这些关系的成功依赖于假设的成立。最基本的关系是马尔可夫性质。马尔可夫性质表明，如果 P 是 G 的马尔可夫分布，那么所有的条件独立性关系都在图 G 中得到体现。信忠性则是一个更强的假设，表示图 G 中的所有条件独立性都能够在分布 P 中找到对应。

通用框架的定义

在本节中，我们将介绍一个通用框架，该框架允许我们通过占位符属性来表示任何基于约束的因果学习算法。给定一类图 G 和一个分布 P，我们定义属性 A(P, G) = ⊤，表示分布 P 满足属性 A 相对于图 G。如果我们能够识别出一个属性 A，使得输出图 G(P) 和输入分布 P 之间存在关系，那么我们就可以获得该算法的一致性条件。

框架的核心定理

根据框架的定义，如果属性 A 是类属性，并且对应于算法，则我们可以得出以下定理：

定理1：给定图类 G，设 A 是一个属性。考虑一个基于约束的因果学习算法，它从分布 P 输出图 G(P) ∈ G，使得 A(P, G(P)) = ⊤。如果 G0 ∈ G 是真实的因果图，则 A(P, G0) = ⊤ 且 UA(P) = ⊤ ⇒ 算法是一致的。

这个定理表明，只要我们能够识别出属性 A，并且它与真实因果图 G0 之间存在一致性条件，那么算法就会返回正确的因果图。

框架中的应用与实例

在这个框架下，我们可以通过不同的属性 A 来具体化一致性条件。比如，考虑“信忠性”作为属性 A，我们可以得出属性 A 和 UA(P) 的结合相当于 P 在 G 中的信忠性。

PC 算法的具体一致性条件

在基于约束的学习中，PC 算法是一个经典算法。根据不同的计算实现，PC 算法的方向规则可能会略有不同。我们可以利用框架中的定理，得出 PC 算法在不同方向规则下的必要和充分一致性条件。

例如，设定方向规则为：
1. 如果 ∀ C ⊆ V \ {i, j} 使得 i ⊥⊥ j | C，则 k ∈ C，则将 i ∼ k ∼ j 赋值为非碰撞点；否则赋值为碰撞点。
2. 如果 ∀ C ⊆ V \ {i, j} 使得 i ⊥⊥ j | C，则 k ̸∈ C，则将 i ∼ k ∼ j 赋值为碰撞点；否则赋值为非碰撞点。
通过这些方向规则，我们能够导出相应的属性 Vn,c，进而利用框架的定理得出以下结论：

命题6：设 P 为真实因果图 G0 的分布，V1, V2, V3 为各个方向规则对应的性质，则 VI(P, G0) = ⊤ ⇐⇒ 使用方向规则 I 的 PC 算法一致。

这一命题提供了 PC 算法一致性的充分和必要条件，且这些条件在文献中是首次被明确描述。

结论与未来工作

本文提出的基于约束的因果学习的通用框架为因果学习算法的一致性条件提供了理论基础。通过识别出属性 A，我们能够得到算法一致性的条件，从而提升因果发现的准确性。

未来的研究方向包括如何从 J(P) 中获得 Pearl 最小图的过程，以及探索如何将函数优化中的图作为生成的算法属性。通过这些研究，我们希望进一步提高因果学习算法的有效性和适用性。

参考文献
1. Teh, K. Z., Sadeghi, K., & Soo, T. (2024). A General Framework for Constraint-based Causal Learning. arXiv:2408.07575.
2. Spirtes, P., & Glymour, C. (1991). An algorithm for fast recovery of sparse causal graphs.
3. Raskutti, G., & Uhler, C. (2018). Sparse Permutation algorithms for causal inference.
4. Pearl, J. (2009). Causality: Models, reasoning, and inference.
5. Forster, J., et al. (2018). Minimality assumptions in causal inference.
以上是根据您提供的文档撰写的文章。希望这篇文章能满足您的需求！如果您有任何具体的修改建议或其他要求，请告诉我！
2024 年 8 月 16 日
量化最优答案集的研究
引言：扩展回答集编程的边界

在过去的几十年里，回答集编程（ASP）作为一种强大的逻辑编程范式，已经被广泛应用于解决各种搜索和优化问题。尽管ASP在解决多种实际问题方面表现出色，但其原始形式的表达能力仍然受到限制，特别是在处理更高复杂度的问题时。随着对复杂问题需求的增加，研究者们提出了ASP的扩展版本，尤其是加入量化的版本——带量化的回答集编程（ASP(Q)）。然而，尽管这一扩展能够自然地表示多项式层次中的问题，但在处理需要多次调用Σp_n类的oracle（即Δp_{n+1}类问题）时，仍显得力不从心。

本篇文章将介绍一种新的ASP(Q)扩展形式，称为ASPω(Q)，该形式允许在量化的子程序中使用弱约束。这种弱约束使得在量化子程序内部可以表达局部优化，同时也能为全局优化标准建模。通过多个应用场景的实例，我们将展示这一新形式的建模能力及其计算性质。

理论基础：回答集编程

ASP的基本语法

在ASP中，程序由一组规则构成，每条规则的形式为：

$h \leftarrow b_1, \ldots, b_k, \sim b_{k+1}, \ldots, \sim b_m$

其中， $h$ 为规则的头， $b_i$ 为规则的身体， $\sim$ 表示否定。除了标准规则外，ASP中还引入了弱约束的概念，其形式为：

$\leftarrow_w b_1, \ldots, b_k, \sim b_{k+1}, \ldots, \sim b_m [w@l, T]$

这种弱约束被引入以便对答案集进行偏好排序，提供了一种在答案集之间进行比较的方法。

ASP(Q)的引入

ASP(Q)的引入为逻辑编程提供了一个自然的声明式手段，能够涵盖整个多项式层次中的问题。这种形式使得我们可以通过引入量化符号来扩展ASP的表达能力，例如，通过存在量化符号 $\exists$ 和全称量化符号 $\forall$ 来描述更加复杂的问题。

ASPω(Q)的提出

弱约束的双重功能

在ASPω(Q)中，弱约束的引入具有双重功能：一方面，它可以表达量化子程序内部的局部优化；另一方面，它也可以用于全局优化标准的建模。这一特性大大增强了语言的建模效率，使得ASP能够更有效地应对复杂的优化问题。

在此，我们将通过几个具体的案例来展示ASPω(Q)的建模能力和计算特性。

案例分析：最小最大团问题

最小最大团问题是一个著名的优化问题，涉及到在给定图中找到最小的最大团。我们可以通过以下程序来建模该问题：
```
P1 =
{
    v(i, j, a) ← ∀i ∈ I, j ∈ J, a ∈ A_{i,j}
    inI(i) ← ∀i ∈ I
    inJ(j) ← ∀j ∈ J
    e(x, y) ← ∀(x, y) ∈ E
    {f(i, j) : inJ(j)} = 1 ← inI(i)
    {valK(1); ...; valK(|V|)} = 1
}
```
在上述程序中， $P1$ 负责建模图的节点和边， $P2$ 则计算最大团的大小。通过使用弱约束，我们可以确保选出的团的大小尽可能小。

复杂性分析

在对ASPω(Q)程序的复杂性进行分析时，我们发现其一致性问题的复杂度在于：存在量化程序的复杂度为 $\Sigma^P_{n+1}$ ，而全称量化程序的复杂度则为 $\Pi^P_{n+1}$ 。这一发现提供了对ASPω(Q)的深刻理解，使我们能够在实际应用中进行合理的复杂性预期。

结论

本文提出的ASPω(Q)为回答集编程提供了新的扩展，能够有效地处理复杂的优化问题。通过引入弱约束，我们不仅增强了语言的表达能力，还开辟了新的研究方向。未来的工作将集中在进一步加强复杂性的界限、扩展ASPω(Q)以支持子集最小性以及基于ASPω(Q)的复杂性感知实现等方面。

参考文献
1. Amendola, R., Fandinno, J., & Ricca, F. (2019). Answer Set Programming with Quantifiers.
2. Brewka, G., Eiter, T., & McGuinness, D. L. (2011). Knowledge Representation.
3. Buccafurri, F., & Faber, W. (2000). Weak Constraints in Logic Programming.
4. Schaefer, M., & Umans, C. (2002). Completeness in the Polynomial-Time Hierarchy.
5. Wagner, K. W. (1990). Bounded Query Classes.
2024 年 8 月 16 日