Markov Categories and Entropy

馬爾可夫范疇與熵

https://arxiv.org/pdf/2212.11719

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這些結(jié)構(gòu)和性質(zhì)正是構(gòu)成馬爾可夫范疇所需要的。為便于參考，以下給出嚴(yán)格而簡潔的定義。

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

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

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

2 馬爾可夫范疇上的散度

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

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

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

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

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

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

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

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