在過去的幾年裡,統計物理學、計算機科學與信息論領域的科學家們開展了意料之外的合作,給一些研究領域帶來了重要進展。但是,科學學科之間的這種對話並非沒有困難,因為每個領域都有其各自的目標和行為準則。盡管如此,人們仍更加一致認為,存在著一個或將碩果累累的共通點。本書旨在通過一種統一的方式,選取一些得益於學科融合的重要研究問題,方便大家更廣泛地了解這一共通點。
歷史上,自香農(Shannon)於60年前,使用熵(entropy)來量化消息的信息量以來,信息論和統計物理開始有了緊密的聯繫。熵在更早幾十年前就已經成為玻爾茲曼(Boltzmann)統計力學的基石。但是,這兩個主題卻一直分別朝著不同的方向發展。現在大多數統計物理學家對信息論知之甚少,而大多數信息理論家同樣對統計物理知之甚少。這讓人感到相當遺憾,因為自過去二十年以來,在各自領域核心問題上取得的進展,已經不知不覺地將這兩條路變越來越近。與此同時,人們對在計算機科學中應用概率概念越來越感興趣,其在設計和分析新算法上都能有用武之地。統計物理學家們已經開始在這一領域中應用他們發展出來的非嚴格技術來研究無序繫統。反過來,他們也已經逐漸意識到計算機科學家發明的計算技術之強大,並將其應用於大規模模擬。
在20世紀的後25年裡,我們見證了統計物理學中一個新課題的誕生。在此之前,我們主要著眼於“有序”材料:原子在周期性晶格中繞平衡位置振動的晶體,或是粒子密度均勻的液體和氣體。在70年代,隨著對自旋玻璃、結構玻璃、聚合物網絡等進行研究,人們對強無序繫統的興趣開始與日俱增。之後之所以發展得如此迅猛,是因為這些繫統湧現出了大量難以置信的特性,而且它們在材料科學中有著諸多應用,更何況其中的各種概念問題還牽扯到對這些特性的理解。統計物理學涉及到許多相互作用組分的集體行為。對於無序繫統而言,它起始於研究所有組分非均勻的繫統的集體行為。這為研究物理學之外的大量問題開闢了道路,而非均勻性(heterogeneity)便是它們之間的“通貨”。
近信息論中一些引人注目的進展與糾錯碼有關。香農定理問世五十多年後,接近香農理論極限的有效編碼已經被找到。Turbo碼和低密度奇偶校驗(LDPC)碼在錯誤校正性能上都有了極大提高。這些新型編碼的特點之一便是消息傳遞譯碼策略,比如著名的“信念傳播”算法。這些方法和發展於統計物理學的無序繫統平均場理論密切相關。
從隨機算法到概率組合學,概率論在理論計算機科學中扮演了一個重要角色。研究計算問題的隨機集成,是為了模擬真實世界的情況,測試現有的算法,或是開發新的算法。在這類研究中,人們通常定義一族實例並賦予它一個概率測度,就自旋玻璃或LDPC碼而言,如同對其定義一族樣本。我們發現,在所有的現有算法中,難解決的實例都與引發很大興趣的相變邊界息息相關。實際上,相變(phase transition)或閾值現像(threshold phenomenon)在這三個領域中都有被發現,並且在各自領域都起著核心作用。從分析角度去預測和理解它們是當下的一個主要挑戰。同時它也會影響到今後有效算法的設計。統計物理學表明,之所以隨機約束滿足問題(CSP)的難度與相變息息相關,是因為它與結構有關:其取決於解集幾何中玻璃轉變與結構改變是否存在。這種理解開闢了新的算法視角。
為了強調上述這些領域的研究興趣與方法開始真正地融合,本書采用一種統一化的處理方式。我們關注那些日益復雜的課題,在結構上組織成五大部分。每個部分通常包含三個章節,分別呈現了信息論、統計物理和組合優化這三門學科中的一些核心課題。而每部分課題都有一個共同的數學結構,其是連接各章的橋梁。
- 部分(第1-4章)包含對應三個學科的介紹性章節和一些常見的概率論工具。
- 第二部分(第5-8章)討論了扮演重要角色的獨立性(independence)問題:隨機能量模型(random energy model)、隨機碼集(random code ensemble)和數字分區(number partitioning)。由於隨機變量的獨立性,經典技術可成功地應用於這些問題。該部分以描述復本方法收尾。
- 第三部分(第9-13章)描述了圖(graph)上問題的集成:可滿足性(satisfiability)、低密度奇偶校驗碼(low-density parity-check code)和自旋玻璃(spin glass)。因子圖(factor graph)和統計推斷(statistical inference)為我們提供了一種通用語言。
- 第四部分(第14-17章)解釋了信念傳播(belief propagation)和相關的“復本對稱”空腔方法(“replica-symmetric” cavity method)。當相關性隨著距離的增加而衰減得足夠快時,這些方法被認為可用於研究大規模圖上的相關隨機變量繫統。該部分展示出此方法可成功用於以下三個問題:譯碼(decoding)、指派(assignment)和鐵磁體(ferromagnet)。
- 第五部分(第18-22章)主要關於長程關聯的一個重要結果,即純態的擴增(proliferation of pure states)和“復本對稱破缺(replica symmetry breaking)”。它從具有布爾變量(Boolean variable)的隨機線性方程這個更簡單的問題入手,然後發展出一般的方法,並將其應用於可滿足性和編碼。後一章回顧了一些有待解決的問題。
在每一章的末尾,都會有一段注釋用來指出相關的參考文獻。附錄A彙總了本書的記號和符號。在正文和索引中以粗體標記新概念的定義。這本書還包含了許多不同難度的例子和練習,用淺灰色背景來表示。它們也是本書重要的組成部分。
隨著本書內容的推進,我們開始探究一些越來越鮮為人知的課題。與此前內容的不同之處在於,有數學證明的陳述減少了,並且我們在某些地方開始依賴於啟發式的或直覺上的解釋。我們已經十分努力地去區分已經證明的和未被證明的,並盡可能清晰鮮明地介紹後者。我們希望這將激發有數學思維的讀者的興趣,並能嘗試為之做出貢獻,而不是疏遠它們。
這是一本研究生水平的書,旨在為任何有志於學習、了解這一交叉研究領域中主要概念與方法的學生或科研人員提供幫助。開篇的介紹性章節已幫助我們構建了共同語言,因此,任何具有一些數學標準背景(概率、線性代數和微積分)的理科研究生都應該可以理解本書的內容。
我們選擇詳細介紹一些選定的問題,有不少其他的有趣課題與應用沒有選入,而它們中的一部分也是信息、物理和計算三者交叉感興趣的課題,例如信源編碼(source coding)、多輸入多輸出通信(multiple-input multiple-output communication),以及神經網絡中的學習與推理。本書所研究的概念和技術也已被更廣泛地應用於“復雜繫統(complex system)”的研究之中——從神經生物學或繫統生物學,到經濟學和社會科學。一些相關參考文獻的介紹放在了第22章的注釋。
Heiko Bauke、Alfredo Braunstein、John Eduardo Realpe Gomez、Florent Krzakala、Frauke Liers、Stephan Mertens、Elchanan Mossel、Sewoong Oh、Lenka Zdeborová等人的批判性審讀和許多評論都對我們非常有幫助。我們十分感謝他們的反饋。我們也受到了Amir Dembo、Persi Diaconis、James Martin、Balaji Prabhakar、Federico Ricci-Tersenghi, Bart Selman和Rüdiger Urbanke的鼓勵,以及牛津大學出版社Sonke Adlung的周全關照與持續支持。