Markov Categories and Entropy

馬爾可夫范疇與熵

https://arxiv.org/pdf/2212.11719

摘要
馬爾可夫范疇是一種用于描述和處理概率論與信息論問題的新穎框架。本研究將范疇論形式體系與熵、互信息、數據處理不等式等傳統量化概念相結合，證明信息論的多個量化維度可以通過增強型馬爾可夫范疇來捕捉——該范疇中的態(tài)射空間需配備散度甚至度量結構。

遵循信息論的常規(guī)實踐，我們通過選定散度來量化聯合信源與其獨立分量狀態(tài)之間的偏離程度，從而獲得互信息的度量方法。更具突破性的是，馬爾可夫范疇為信源與信道提供了確定性的定義方式，使得熵能夠通過量化信源或信道偏離確定性的程度來精確界定。這一方法不僅重構了香農熵、雷尼熵以及生態(tài)學中用于量化多樣性的基尼-辛普森指數，更為廣義熵的概念化定義提供了理論框架。

本文無需讀者具備范疇論基礎知識。

引言
本研究致力于融合信息論的兩大核心主題：一方面是對信息流的定性描述，例如通過隨機依賴關系的圖形化表示或范疇論思想進行刻畫；另一方面是基于熵、互信息等度量以及數據處理不等式等工具的定量推理。我們借助豐富范疇理論將定量維度納入范疇論框架（但理解本文無需預先掌握該理論）。

自信息論發(fā)展初期，學界便對用范疇結構描述概率過程產生興趣（最早公開文獻可追溯至欽佐夫1965年的著作）。近年來，由弗里茨在2020年系統定義的馬爾可夫范疇引發(fā)持續(xù)關注1，這類范疇可視為核范疇的抽象化，其內置的圖形演算能忠實反映信息流特征。事實上，馬爾可夫范疇的圖形演算已被證明滿足d-分離定理[FK22]，因此可與貝葉斯網絡、馬爾可夫隨機場并列，視作概率圖模型的一般性理論。這種圖形表示與數學結構間的對應關系，使我們得以通過圖形操作簡潔證明定理。

概率論及相關領域的多項定理已通過該方式被重新證明乃至推廣，包括：充分統計量相關定理[Fri20, Jac22]、科爾莫戈羅夫與休伊特-薩維奇零一律[FR20]、統計實驗比較的布萊克韋爾-謝爾曼-斯坦定理[FGPR20]、德菲內蒂定理[FGP21, MP22b]，以及遍歷分解定理[MP22a]。馬爾可夫范疇還被用于建模信息流特性[FGGHL+22]，成功捕捉依賴性與獨立性、信號傳遞等定性概念。

本研究轉向信息論的量化概念，重點探討散度與熵，并揭示其如何適配馬爾可夫范疇體系。為將定量表述融入范疇論框架，我們采用豐富范疇理論[Kel82]——該理論以更廣義結構替代傳統范疇中對象間的態(tài)射集合。具體而言，我們引入度量或散度空間，用以衡量兩態(tài)射間的"差異程度"，即判定圖表偏離交換性的程度。盡管度量看似比廣義散度更具理想性質，但本文框架將保持普適性。我們重點考察三類散度：庫爾貝克-萊布勒散度（相對熵）、更廣義的雷尼散度，以及全變分距離。

信息論常將互信息定義為對隨機獨立性狀態(tài)的偏離度量。這天然契合馬爾可夫范疇體系——其中基于兩個特定態(tài)射的等式關系（詳見第3節(jié)）可抽象定義隨機獨立性。通過量化該等式的偏離程度，能精確重構香農互信息與雷尼互信息等度量。

馬爾可夫范疇同樣通過態(tài)射等式定義確定性概念（詳見第4節(jié)）。通過量化該等式的偏離程度，并選擇恰當散度，可完整復現香農熵與雷尼熵；若采用全變分距離，則得到生態(tài)學中用于量化多樣性的基尼-辛普森指數[Lei21]。因此，本方法為（至少離散情形下的）廣義熵提供了等價的抽象定義。

注1：此處"當前形式"特指弗里茨2020年論文中確立的馬爾可夫范疇公理化體系。

關于范疇論與熵的前期研究熵及其性質歷來受到范疇論學界的關注。文獻[BFL11][Lei19][FP21]從范疇論角度對香農熵進行了刻畫，形式化了信息損失度量的思想；文獻[BF14]針對離散情形，文獻[GP18]針對一般標準博雷爾情形，通過貝葉斯推斷刻畫了相對熵（KL散度）；文獻[Ful22]給出了二維推廣。熵可通過凸空間操作胚的視角研究，文獻[Bra21]證明熵是該操作胚上的導子，其導子性質的同調視角研究見于[BB15]。熵的組合性質亦通過多項式函子得以探究[Spi22]。在量子領域，馮·諾依曼熵的范疇刻畫[Par22]與量子相對熵的刻畫研究[Par21]相繼出現。從熱靜力學與熱力學視角出發(fā)，熵及相關量的范疇意義研究可見[BLM21]。代數層面，文獻[DGB13]給出了代數熵概念的范疇推廣。此外，經典與量子熵及其與語境性的關聯在[CD20]中亦有探討。

本研究并非度量幾何與范疇論結合研究熵的首例。該思想的早期雛形可追溯至格羅莫夫[Gro13]，其工作除啟發(fā)了本研究外，還催生了若干獨立研究路徑，如熱帶概率論[MP17, MP19c, MP19d, MP19b, MP19a]。最后，范疇論、度量幾何與熵亦是專著[Lei21]的核心主題，該書探討了作為多樣性度量（如生態(tài)學語境）的類熵量。

本文結構第1節(jié)概述馬爾可夫范疇，重點介紹兩大實例：有限字母表與隨機矩陣（含噪信道）構成的范疇FinStoch，以及無限可測字母表與馬爾可夫核構成的范疇Stoch。

第2節(jié)回顧散度（統計距離）概念，定義馬爾可夫范疇的豐富結構（定義2.5），解析相關不等式（特別是數據處理不等式，第2.1節(jié)）。通過回顧馬爾可夫范疇中的聯合分布與邊緣分布概念，給出豐富結構的等價刻畫——該刻畫可視為觀測變量數量單調性條件與廣義鏈式法則的結合（第2.2節(jié)）。隨后通過實例證明：KL散度（相對熵）、雷尼α散度、全變分距離均可賦予Stoch與FinStoch以豐富結構，而察利斯q散度一般無法實現此結構。第2.4節(jié)證明，在實例中，非離散概率測度間的散度可表示為可數劃分上的上確界，并將此結果表述為本文框架的首個豐富泛性質。第2.5節(jié)進而定義條件散度，用以量化信道間幾乎必然等價的偏離程度。

第3節(jié)回顧馬爾可夫范疇中的獨立性與條件獨立性概念，將互信息定義為對獨立性狀態(tài)的偏離度量。該定義契合傳統信息論視角，并在對應散度下重構香農互信息與α互信息（第3.2節(jié)）。通過構造證明：所有互信息度量均滿足數據處理不等式（第3.1節(jié)），這再次導出觀測變量數量的單調性條件。同時證明，用于量化幾乎必然條件獨立性偏離的條件散度度量，可復現經典條件互信息（第3.3節(jié)）。

第4節(jié)回顧馬爾可夫范疇中的確定性信源與信道概念，將熵定義為對確定性狀態(tài)的偏離度量。該定義在離散情形下復現若干經典隨機性度量（第4.2節(jié)）：KL散度對應香農熵，雷尼α散度對應（階數為2-α的）雷尼熵，全變分距離對應基尼-辛普森指數。類似地，對幾乎必然確定性偏離的量化可得條件熵（第4.4節(jié)）。在非離散情形下，這些熵度量對無原子分布取最大值（第4.3節(jié)）。我們論證此現象源于可測空間在描述連續(xù)情形的局限性，并提出更具幾何性的研究路徑（第4.5節(jié)）。

附錄A詳述作為馬爾可夫范疇豐富基底的散度空間范疇結構。理解正文無需閱讀附錄或預先掌握豐富范疇論知識。

1 背景：馬爾可夫范疇
馬爾可夫范疇是對含噪處理單元及其可共享輸入輸出數據系統的抽象。

字母表與信道
首先，馬爾可夫范疇由一系列對象（記為X、Y等）構成，我們將這些對象視為可能的狀態(tài)空間、數據空間或字母表。在本文中，我們將其表示為水平走向的導線。

這些可視為無噪聲的信道。
我們可以將概率測度建模為無輸入的信道，具體方式如下。首先，我們有一個稱為單位元的特定對象，記作 I，它在圖示中不畫出（以空白區(qū)域表示）。它代表無信息的狀態(tài)。在 FinStoch 和 Stoch 中，它是單點空間，即無需對狀態(tài)進行區(qū)分。X 上的一個信源或（隨機）狀態(tài)現在是一個態(tài)射 p : I → X，我們將其描繪如下。

在 Stoch 和 FinStoch 中，該態(tài)射只是以概率 1 交換坐標，即 ( x , y ) ? ( y , x )
。這些同構必須以構成所謂對稱幺半范疇的方式兼容（更多信息參見例如 [ML98, 第七章第 1 節(jié)]）。

在 FinStoch 中，這恰好是隨機矩陣每列之和為 1 的條件，即轉移概率歸一化。

這些結構和性質正是構成馬爾可夫范疇所需要的。為便于參考，以下給出嚴格而簡潔的定義。

定義 1.1.馬爾可夫范疇是一個對稱幺半范疇 ( C , ? , I )
，并為每個對象 X X選定一個與張量積相容的交換余半群結構，且滿足所有態(tài)射都是余幺的。

有時會省略余幺性或歸一化條件，此時不稱馬爾可夫范疇而稱為垃圾共享（GS）范疇[Gad96, FL22] 或拷貝丟棄（CD）范疇[CJ19]。

關于馬爾可夫范疇理論的更多信息，我們推薦原始文獻 [Fri20] 以及引言中引用的其他材料。需注意，在大多數其他文章中，圖形演算采用垂直方向（從下到上）而非從左到右。

2 馬爾可夫范疇上的散度

不等式 (2) 和 (3) 的一個解釋是：可以通過更簡單的組件來界定通過順序組合與并行組合獲得的信源與信道復雜配置之間的散度。例如，下圖所示兩個系統之間的距離或散度：

熟悉豐富范疇論的讀者可能會在定義 2.5 中識別出豐富結構。確實如此，感興趣的讀者可參閱附錄 A 中的更多細節(jié)。另請注意，該定義中我們使用了 C 的幺半結構，但未使用其馬爾可夫結構。然而后者將在定理 2.7 中用于給出更簡潔的描述。

2.1 數據處理及其他不等式
在定義 2.5 中，我們已看到，為了通過 (4) 式在馬爾可夫范疇上定義散度，對于如下形式的每個圖表：

我們實際上可以得到序貫不等式 (10)。

張量積條件 (3) 同樣是一種三角不等式，但作用于另一種"方向"，即并行處理的方向。它表明我們可以通過獨立過程的各組件來界定并行組合后的散度。同樣，這通常與散度是否滿足度量三角不等式無關。

2.2 用聯合分布與邊緣分布刻畫
我們擁有帶散度馬爾可夫范疇的等價刻畫，該刻畫聚焦于聯合態(tài)射、邊緣態(tài)射及其分布，而非序貫組合。首先回顧：給定 X 上的有限支撐概率分布 p 和 Y 上的有限支撐概率分布 q，p 與 q 的聯合分布（若將 X 與 Y 視為隨機變量，亦可稱為 X 與 Y 的聯合分布）是 X × Y 上的一個概率分布 r，使得：

2.3 特定散度
信息論、概率論和統計學中使用的若干散度，都是定義 2.5 意義下 Stoch 與 FinStoch 上散度的實例。以下給出一些例子及一個反例（第 2.3.4 節(jié)）。對 Stoch 與 FinStoch 上所有散度的完整分類目前仍是一個開放問題。

原文鏈接：https://arxiv.org/pdf/2212.11719