PNAS:如何定量描述複雜度?新方法來了

2020-12-11 騰訊網

導語

系統的複雜度，雖然有很多定義方式，但作為複雜性科學的基本問題，遠遠沒有獲得確定的回答。重整化群可以通過數學變化，統一地考察不同尺度的物理系統。近日發表在PNAS的一篇論文，基於重整化群，提出了在多層級複雜系統中定量描述複雜度的新方法。

郭瑞東| 作者

鄧一雪| 編輯

論文題目：

Multiscale structural complexity of natural patterns

論文地址：

https://www.pnas.org/content/117/48/30241

1. 已有的複雜度定義的方法

最廣為人知的定義複雜度的方式，稱為Kolmogorov複雜度，該方法使用能夠對某一信息編碼的程序的最小長度，來代表一段信息的複雜度。例如101010相比110001，前者由於存在規律，能夠用更短的程序描述，其複雜度更低。

如果不同尺度的子系統間相似度較低，那麼系統的複雜性也越高。然而，我們對複雜度的直覺，告訴我們需要該定義同時反映系統中有多少組件及連接，以及系統中的這些組件及連接是否可見。基於系統自相似來定義複雜度的方式，只反映了後者，沒有考慮那些系統中隱藏的連接，不完全符合我們對複雜度的直觀映像。

在真實環境，例如生物系統、社會系統中，往往同時存在多個層級，不同層級的結構，以及受到的約束存在顯著區別。考慮到複雜系統往往是層級化的，對系統複雜度的定義就必須考慮到不同層級，而不能主觀地規定某一層級的特徵是本質的。複雜科學需要提出一個明確定義，能夠整合不同層級信息、且具有魯棒性的複雜度定義。對於那些完全有序或完全無序的系統，該定義得出的複雜度都應該極低。

這篇PNAS論文，提出了基於重整化群的複雜度定義方法。

2. 基於重整化群的複雜度定義

例如拍照的時候zoom in，發現看到的現象有些接近，將小尺度的現象，放到大尺度去分析。由於系統具有自相似性，通過對比兩種模式下分析的差異，可以用大尺度的分析，來作為對小尺度現象的建模。這可以看成是重整化群的通俗理解。

圖1. 基於重整化群計算圖片複雜度的方式

如何計算上面這幅圖片的複雜度？重整化群的方法，是將該圖分為16份，再將圖中的某一份放大之後分為16份，將其中像素平均後，得出該子圖的不同區域像素值。將原圖的16個子圖依次排列，得到A，再將子圖分割排列得出圖B，計算圖A和圖B之間的差異，得出圖O。將所有如此分割得出的圖O的複雜度加和，就完成了一個層級上的迭代，將不同層級的結果加和，即得出了原圖的複雜度。

圖2. 自然界和人工產生的圖像對應的複雜度

上圖中從左到右，該方法計算出的複雜度依次升高，這展示了使用該方法，可以衡量圖像的複雜度，符合人類直覺。具體對的計算方法和公式，請參考原文。

3. 通過複雜度判斷相變

在統計物理中，Ising 模型描述了磁性原子之間由於相互作用，而形成的晶格。由於該模型中，參數在某個閾值左右的細微變化，就能引起系統整體的顯著變化，這被稱為相變。發生相變前後，系統的複雜度會發生顯著變化，這可以用來驗證新提出的複雜性度量方法。

圖3. 二維Ising模型的模擬數據下，不同溫度和複雜度的對應關係

上圖中，橫軸溫度可以看成是系統具有的能量，能量越高，系統越無序。紅色和藍色的線代表計算複雜度時，迭代計算的次數不同，即對複雜度的計算方法有所不同。不論那種計算方法，當相變發生時，複雜度都會呈現顯著變化。而藍線對應的算法，當系統的無序程度進一步提升時，複雜度下降，這符合一個完全無序的系統沒有處在混沌邊緣系統複雜的直覺。而紅線對應的算法，由於迭代次數過少，導致其不會考慮更小尺度的差異，相變點之後，複雜度就不再變化。

而在更高維度，以及真實的微粒擴散過程中，該方法都能夠反映出相變現象。如下圖所示

圖4. 三維系統中，基於重整化群的複雜度算法得出的複雜度和系統溫度的關係

圖5. 微粒擴散過程中，隨時間變化的系統複雜度

4. 複雜度在各個領域的應用

以上實驗說明，在固態物理中，可以使用該方法，根據實驗得出的圖像來發現如法通過實驗找到的相變現象。

此外，在機器學習中，系統的複雜度可以成為額外的信息來源，例如在應對對抗性攻擊，即通過改變少數像素點，就改變對應分類標籤。例如本文作者假設上述改變會增加圖片局部的複雜度，從而改變原圖中各個子圖的複雜度分布，據此識別對抗性的訓練數據集。

而在生物領域，複雜度這一概念的應用雖然鮮有研究，但通過計算處在進化樹上不同物種的基因序列的複雜度，可以研究進化過程中的相變點，即生物集中爆發或產生顯著變化的過程。不同層級系統間的競爭和制約，被認為是生物體複雜性的來源之一。而這也反映了時間及空間層面上的不同系統存在的不相似性，在複雜性科學的核心位置。

測量複雜度還對因果發現有啟發。之前的研究中，根據對不同信號壓縮的難度差異，判斷信號間的因果方向，更難壓縮的信號是因[1]。據此我們可以推測，考慮不同系統間的複雜度隨時間變化的曲線的先後，有可能可以判斷出兩個系統間的因果箭頭。這有賴進一步的研究。

參考資料

1. SY, Pranay, and Nithin Nagaraj. "Causal Discovery using Compression-Complexity Measures." arXiv preprint arXiv:2010.09336 (2020）

複雜科學最新論文

相關焦點

  • PNAS:人腦脊液中的朊蛋白定量——助力朊病毒病藥物開發
    任何PrP降低治療劑的臨床開發將需要適當的藥效學生物標誌物：用於量化PrP的實用且穩健的方法，並且可靠地證明其在活體患者的中樞神經系統（CNS）中的減少。最近，研究人員評估了基於ELISA的人類腦脊液（CSF）中人類PrP定量的潛力，作為PrP減少治療的生物標誌物。研究人員表明，CSF PrP在處理和儲存過程中對塑料吸附非常敏感，但通過添加洗滌劑可以使其損失最小化。
  • 時間複雜度的表示、分析、計算方法……一文帶你看懂時間複雜度!
    ，那你是來對地方了！名詞解釋：在計算機科學中，時間複雜性，又稱時間複雜度，算法的時間複雜度是一個函數，它定性描述該算法的運行時間。這是一個代表算法輸入值的字符串的長度的函數。時間複雜度常用大O符號表述，不包括這個函數的低階項和首項係數。
  • 算法的時間複雜度到底如何計算
    \n");      4    }5    return 0;       6}這個方法需要 (n + 1 + n + 1) = 2n + 2 次運算。我們把 算法需要執行的運算次數 用 輸入大小n 的函數 表示，即 T(n) 。此時為了 估算算法需要的運行時間 和 簡化算法分析，我們引入時間複雜度的概念。
  • 探索定量社會學的新範式
    定量社會學面臨雙重危機近十年來，我國定量社會學發展迅速，但也遭遇了雙重危機——基於內生性問題的因果邏輯危機和基於時空問題的理論視野危機。儘管量化分析方法發展迅速，但我國定量社會學研究總體上對內生性問題認識不足，且囿於研究設計、數據質量和模型設置，仍停留在簡單統計回歸的驗證關聯階段，缺乏基於因果推斷的解釋能力。
  • 時空複雜度(時間複雜度/空間複雜度)O(1)、O(n)、O(n^2)、O(log n)、O(n log n)是什麼意思?
    它描述了時空複雜度.大O符號是我在大學裡學過的東西之一，我了解過這個算法的概念。我知道的不算多，可以回答一些基本的問題，僅此而已。從大學畢業以後，我對這個算法的了解基本沒有改變，因為自從我開始工作以來，我沒有使用過它，也沒有聽到任何同事提到過它。所，我想我應該花點時間回顧一下它，並在這篇文章中總結大O符號的基礎知識，以及一些代碼示例來幫助解釋它。什麼是大O符號?
  • 30天學會醫學統計與SPSS公益課程(Day 2-2):定量數據統計描述
    ，這一不同體現在統計描述和統計比較（專業來說是統計推斷），統計比較內容後期逐步展開，今日首先介紹下定量數據正態和偏態分布的的統計描述方法、SPSS操作和統計表格繪製。P25、P75操作如下圖：統計選項一般情況下，醫學研究論文，常見的數據，有定量數據和定性數據，定量數據又有正態分布和偏態分布，採用的一般是描述均數和中位數，定性數據，一般採用率和構成比描述。同時，往要採用差異性比較的方法來探討不同組間有無統計學差異。這些結果在論文中往往要同時呈現在一張表格中。特別是統計學分析的第一張表格，研究對象基本特徵及其組間差異性。
  • 阿里研究員:警惕軟體複雜度困局
    本文將分享阿里研究員谷樸關於軟體複雜度的思考：什麼是複雜度、複雜度是如何產生的以及解決的思路。較長，同學們可收藏後再看。 寫在前面 軟體設計和實現的本質是工程師相互通過「寫作」來交流一些包含豐富細節的抽象概念並且不斷迭代過程。
  • 關於時間複雜度,你不知道的都在這裡!
    究竟什麼是時間複雜度「時間複雜度是一個函數，它定性描述該算法的運行時間」。我們在軟體開發中，時間複雜度就是用來方便開發者估算出程序運行的答題時間。那麼該如何估計程序運行時間呢，通常會估算算法的操作單元數量來代表程序消耗的時間，這裡默認CPU的每個單元運行消耗的時間都是相同的。假設算法的問題規模為n，那麼操作單元數量便用函數f(n)來表示，隨著數據規模n的增大，算法執行時間的增長率和f(n)的增長率相同，這稱作為算法的漸近時間複雜度，簡稱時間複雜度，記為 O(f(n))。
  • 信息處理方法定性與定量相結合的UX研究
    那麼我們如何對定性和定量進行比對？在定量方法中，我們非常專注為什麼和怎麼樣，並且有很多的描述性的語言。比如說描述他們的情感、挫折、開心等等。我們根據這些語言去做一些分析，當然還有語言本身。我們的定性是能夠幫助你去開發一些想法的，得到一些消費者的見解，我們就把這兩個方法在這張表格上進行定量和定性進行比對。
  • 一種混沌組合序列密碼電路設計與複雜度分析方法
    利用組合LFSR序列作為序列密碼的前饋電路，可充分利用m序列的良好統計特性和加大輸出序列周期和線性複雜度的優勢，但如何在保證前饋電路輸出統計特性不被破壞的基礎上，置換與混亂輸出關係，增強密碼的保密性仍是該領域研究必須思考的問題。
  • 複雜度和臨界點
    後面慢慢發現出抽象的東西，從造字方法，象形、指事、會意、專注、形聲、假借也可以看出是從具象到抽象，從客觀到主觀。這是我們感知、認知、理解世界的內在邏輯順序。3、學生常常難以理解新的概念，尤其是新穎的，不能聯繫到任何其他已知概念的內容。解決這個問題的辦法是用已知的前置知識以不同的表現形式來反覆衝擊這個新知識，來理解新的概念。
  • 如何學習定量研究方法(8條經驗)
    定量研究方法的重要性是不言而喻的，經常碰到同事、朋友、甚至素不相識的年輕人跟我諮詢如何掌握科研中常用的一些定量研究方法，以下是我的一些心得體會，希望能對各位有所幫助。許多初學者由於各種條件所限，面臨著許多問題：老師講得太深，自己聽不懂；一些定量研究方法，根本就沒有相關的課程可以學習，更沒有老師專門講授；自己自學吧，苦於統計學和數學基礎不夠；網上下載軟體，用起來和使用手冊上的完全是兩碼事，根本出不來預想的結果；英文基礎不夠，計算結果的許多統計量根本看不懂……其實，對絕大多數學者而言，我們所需要的並不是創新定量研究方法
  • 定量研究方法真的比定性研究複雜難懂嗎?
    定量研究其實沒那麼難，本文筆者通過對量化研究方法的一些最常見用例的介紹，以及對每個實例的成本和難度進行估計，來幫大家更好地去找我定量研究的方法。你是否需要有關產品用戶體驗的數字數據, 但卻不確定應該如何做？
  • 時間複雜度的分析及排序算法總結
    算法時間複雜度是一個函數，它定性描述該算法的運行時間（也就是所花費時間的消耗）。，這種複雜度⽆論數據規模n如何增⻓，計算時間是不變的。不管n如何增⻓，都不會影響到這個函數的計算時間，因此這個代碼的時間複雜度都是O(1)。
  • 社工實務刷題17|定量研究方法
    個案研究在方法論上遇到的最大問題是如何處理參與和超脫的關係。參與會帶來研究對象的接納，理解即是價值關聯。超脫則與價值中立相連，有時會形成研究者與研究對象之間的障礙。因此如何把握個案研究中的參與程度，在哪些問題上應該持超脫態度，都是研究者必須認真處理的。 2.如何認識定性研究與定量研究的關係？
  • PNAS | 在活細胞中無痕合成磷脂質導致濃度依賴性細胞凋亡效應
    目前研究磷脂類的方法，主要是非天然的短鏈磷脂類，因為它的穿膜性比天然的長鏈磷脂類好，但是在生理活性上無法完全比擬天然的長鏈磷脂類。最近，光保護的磷脂類已被開發用於將磷脂類遞送至巨噬細胞，但其生物活性和其他細胞系的功效尚未見報導。 然而，在本文中作者開發了一種策略，該方法是通過使用兩種細胞滲透性和化學選擇性結合配偶體原位合成天然磷脂類來克服這些問題。
  • 如何設置windows的密碼複雜度?
    當我們安裝好windows作業系統之後就發現電腦是必須要設置密碼的；這不是重點；重點是密碼長度有要求；而且密碼複雜度也有要求；必須英文大小寫+數字組合；這其實非常的麻煩啦；所以我們這次要來關閉密碼的複雜度以及密碼長度；請自行安裝好windows作業系統從開始菜單選擇控制面板
  • 何謂法律定量研究方法 | 掌握高深分析工具方法的法律人必讀
    它是20世紀社會科學領域成熟使用的一種基本研究方法，也是自然科學領域數百年來一直使用的核心方法。所謂的定量研究，與定性研究相對，是指通過一定方法收集數據資料，運用統計工具對數據資料進行分析、檢驗，並據此推斷事物背後的因果律的研究，也稱量化研究。它是20世紀社會科學領域成熟使用的一種基本研究方法，也是自然科學領域數百年來一直使用的核心方法。本書之所以選擇定量研究，而非實證研究這一國內更為流行的術語來界定研究對象，主要出於以下幾點考慮。
  • PNAS:水如何「潤滑」蛋白質
    科學家們首次直接觀察到了水是如何潤滑蛋白質分子運動的。水的潤滑作用幫助蛋白質擔負各種不同的功能。     美國俄亥俄大學研究人員在《國家科學院學報》的在線版中發表了一篇論文。他們使用超速光脈衝來展示水分子是如何與蛋白質連接在一起，幫助蛋白質移動和擔負各種功能的。
  • 算法的時間複雜度和空間複雜度-總結
    第一是從數學上證明算法的正確性，這一步主要用到形式化證明的方法及相關推理模式，如循環不變式、數學歸納法等。而在證明算法是正確的基礎上，第二部就是分析算法的時間複雜度。算法的時間複雜度反映了程序執行時間隨輸入規模增長而增長的量級，在很大程度上能很好反映出算法的優劣與否。因此，作為程式設計師，掌握基本的算法時間複雜度分析方法是很有必要的。