Between Markov and restriction. Two more monads on categories for relations

想象你正在试图组织一个包含各种不同类型“关系”的海量图书馆。在数学和计算机科学中，这些关系被建模为一种称为**范畴（Categories）**的结构。有些范畴描述的是确定且完整的事物（比如一张完美的地图），而另一些则描述的是部分、概率性或混乱的事物（比如一张草图或一个猜测）。

这篇题为**《在马尔可夫与限制之间》（Between Markov and restriction）的论文，就像一位图书管理员，刚刚发现了两个非常具体的、可以用来放置这些“关系之书”的新书架。这两个新书架恰好位于两个已知的、著名的章节中间：一个是马尔可夫（Markov）章节（处理概率与随机性），另一个是限制（Restriction）**章节（处理部分或不完整的信息）。

以下是使用简单类比对该论文主要思想的拆解：

1. 大局观：“关系”图书馆

将**对称单群范畴（Symmetric Monoidal Category）**想象成一个巨大的仓库，在这里你可以组合事物（比如混合食材），也可以复制它们（比如复印文件）。

• **马尔可夫范畴（Markov Categories）**是像这样一种仓库：你取出的每一件物品都保证是“完整”且“完备”的。没有任何东西丢失了。这非常适合处理概率。
• **笛卡尔限制范畴（Cartesian Restriction Categories）**则是像这样一种仓库：其中的物品可能是“破碎”或“不完整”的。你可以拥有一个仅在某些输入上起作用、而非在所有输入上都起作用的函数。这非常适合处理部分函数。

作者此前创建了一张图（分类法），展示了这些不同的仓库是如何相互关联的。在这篇新论文中，他们发现实际上存在着两种新型仓库，它们正好位于“完美”与“破碎”的仓库之间。

2. 两个新概念：“质量”与“定义域”

作者引入了两种衡量范畴中“箭头”（即关系或过程）的新方法。

• 质量（Mass，箭头的“重量”）：
  想象你正在运送一个包裹。箭头的质量就像是在检查包裹离开仓库时的总重量。

  • 在一个**质量范畴（Mass Category）**中，规则是：“如果你在过程结束后检查包裹的重量，只要忽略目的地细节，它与过程开始前的重量是一致的。”
  • 这是一种表达方式，即该过程不会以某种特定的、抽象的方式凭空创造或销毁“物质”（概率质量）。

• 定义域（Domain，箭头的“有效区域”）：
  想象一个只能在纸的特定区域留下印记的印章。定义域就是印章实际留下痕迹的具体区域。

  • 在一个**定义域范畴（Domain Category）**中，规则是：“如果你观察印章起作用的区域，然后让印章运行该过程，你会得到与直接运行印章完全相同的结果。”
  • 这是对“部分函数”概念的一种推广。它确保如果一个过程对于特定的输入是定义的，那么它的行为就是一致的。

3. 发现：一个新的中间地带

作者意识到，你并不一定非要完全是“马尔可夫”（完全全函数）或完全是“限制”（完全部分函数）才能拥有一个有用的系统。

• 你可以拥有一个尊重**质量（Mass）**但未必是完全马尔可夫的系统。
• 你可以拥有一个尊重**定义域（Domain）**但未必是完全限制的系统。

他们证明了著名的马尔可夫范畴实际上是这两类新范畴的交集：一个范畴是马尔可夫范畴，当且仅当它既是一个质量范畴，又是一个“弱马尔可夫”范畴（一种特定的质量范畴）。这就像是在说，“完全正方形”就是一个既是“完全矩形”又是“完全菱形”的形状。

4. “提升”机制：克莱斯利范畴（Kleislian Categories）

在计算机科学中，有一种工具叫做单子（Monad）（把它想象成一个将数据包装在特殊容器中的机器，比如一个盒子）。当你对一个范畴应用一个单子时，你会得到一个新的范畴，称为克莱斯利范畴（Kleisli Category）。

论文提出了一个问题：如果我从一个“定义域”或“质量”范畴开始，并将其通过这个单子机器，新生成的范畴是否会保留这些属性？

• 答案是： 是的，但前提是这个机器（单子）构建得当。
• 他们定义了**“定义域保持型”（Domain-preserving）和“质量保持型”（Mass-preserving）**机器。如果机器的设计能够尊重“定义域”或“质量”的规则，那么通过该机器得到的另一个范畴也将尊重这些规则。
• 这是一个重大的突破，因为它允许研究人员构建复杂的概率或部分系统，同时确切地知道哪些规则（公理）仍然成立。

5. 现实世界案例（案例研究）

为了证明其理论有效，作者研究了两个具体的例子：

1. 半环加权关系（Semiring-Weighted Relations）： 想象一个关系不仅仅是“是/否”（如标准映射）而是带有“权重”的系统（例如一条道路带有交通评分的地图）。他们表明，如果这些权重背后的数学基础（称为“半环”）具有某些特性（例如是“幂等”的，即 $x + x = x$），那么生成的系统会自动成为一个定义域范畴。这解释了为什么某些模糊逻辑或概率系统会表现出那样的行为。
2. 部分马尔可夫范畴（Partial Markov Categories）： 他们研究了一个处理可能不存在的概率分布（部分性）的系统，即 Partial(FinStoch)。他们利用自己新开发的“定义域保持型”工具证明了该系统确实是一个定义域范畴，从而为之前难以证明的一个事实提供了一个更简洁、更直观的证明。

总结

简而言之，这篇论文关于精炼数学逻辑的地图。

• 作者发现了两个新的“社区”（质量范畴和定义域范畴），它们位于“概率”和“部分性”这两个社区之间。
• 他们展示了如何构建机器（单子），使数据能够在这些社区之间移动而不破坏社区的规则。
• 他们证明了著名的“马尔可夫”社区实际上就是这两个新社区的重叠部分。

这有助于计算机科学家和数学家更好地理解其在代码和逻辑中建模不确定性、部分信息以及关系的结构化规则。