<mark id="oztn4"></mark>
0
| 本文作者： 我在思考中 | 2021-10-09 17:13 |
作者 | Stephen Ornes
編譯 | 王曄
校對(duì) | 維克多
用由點(diǎn)和線組成的網(wǎng)絡(luò)形式對(duì)現(xiàn)實(shí)世界建模，是自18世紀(jì)以來采用的主流方法。但隨著大數(shù)據(jù)的出現(xiàn)，研究人員開發(fā)了更多的數(shù)學(xué)工具，在大量的計(jì)算機(jī)資源加持下，數(shù)學(xué)研究不斷被發(fā)現(xiàn)。
正如科羅拉多大學(xué)博爾德分校的計(jì)算機(jī)科學(xué)家Josh Grochow說的那樣：“整個(gè)領(lǐng)域經(jīng)歷了一個(gè)令人興奮的快速增長期?！保爱吘?，新網(wǎng)絡(luò)模型的出現(xiàn)，讓我們有能力在大數(shù)據(jù)的噪音中找到有價(jià)值的東西：復(fù)雜的結(jié)構(gòu)和信號(hào)?！?/span>
在之前，業(yè)界往往用數(shù)學(xué)分支中的圖論表示兩個(gè)事物中的關(guān)系。但當(dāng)涉及到大數(shù)據(jù)時(shí)候，需要關(guān)系并不能用簡單的二元關(guān)系來表示，換句話說，傳統(tǒng)的圖論思維表現(xiàn)出了“短板”。
例如嘗試建立一個(gè)關(guān)于養(yǎng)育子女的網(wǎng)絡(luò)模型。圖論能表現(xiàn)出父母與孩子的聯(lián)系，但是對(duì)于同儕壓力等群體效應(yīng)往往束手無措，即二元網(wǎng)絡(luò)并不能捕捉到群體的影響。再例如，如果一位藥理學(xué)家想模擬藥物相互作用，圖論可能會(huì)顯示兩種藥物如何相互反應(yīng)。但三種藥物呢？或者四種呢？
對(duì)于群體效應(yīng)等的描述，數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家發(fā)明了"高階互動(dòng) "一詞。從量子力學(xué)中的相互作用到疾病在人群中傳播的軌跡，這些"高階互動(dòng) "的數(shù)學(xué)現(xiàn)象遍布各個(gè)方面。
最近幾年，高維數(shù)據(jù)集成為探索的引擎，給數(shù)學(xué)家和網(wǎng)絡(luò)理論家?guī)硇滤悸?。?duì)于圖論表示“高階互動(dòng)”有了新的研究成果。最直觀的表現(xiàn)是一些數(shù)學(xué)家已經(jīng)意識(shí)到：從數(shù)學(xué)角度來看，我們以為的數(shù)據(jù)結(jié)構(gòu)并不完全適合我們?cè)跀?shù)據(jù)中看到的情況。
Emilie Purvine
"網(wǎng)絡(luò)只是事物的影子，"Grochow表示。如果一個(gè)數(shù)據(jù)集有一個(gè)復(fù)雜的基礎(chǔ)結(jié)構(gòu)，那么把它作為一個(gè)圖來建?？赡苤唤沂玖苏麄€(gè)故事的有限投影。
尋找高維結(jié)構(gòu)使數(shù)學(xué)變得特別模糊而有趣。例如，圖的“高階類似物”被稱為超圖。結(jié)合圖，可以理解到超圖就是每一個(gè)邊可以包含兩個(gè)以上的點(diǎn)所構(gòu)成的圖，這意味著它可以代表多向（或多線性）關(guān)系。
超圖的邊（Hyperedge）可以被看作是一個(gè)表面，而不是一條線，就像在三個(gè)或更多地方釘了一塊油布一樣。
超圖如何從大數(shù)據(jù)集中挖掘關(guān)系類型？以科學(xué)出版為例，想象兩個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集都包含最多由三位數(shù)學(xué)家共同撰寫的論文；為了簡便，我們把它們命名為A、B和C。一個(gè)數(shù)據(jù)集包含六篇論文，其中三個(gè)不同的二人合著組（AB、AC和BC）各寫了兩篇論文。另一個(gè)數(shù)據(jù)集只包含兩篇論文，每篇都是由三位數(shù)學(xué)家合著的（ABC）。
從這兩組數(shù)據(jù)中提取的合著關(guān)系圖可能看起來像一個(gè)三角形，顯示每個(gè)數(shù)學(xué)家（三個(gè)節(jié)點(diǎn)）都與另外兩個(gè)數(shù)學(xué)家（三個(gè)鏈接）合作過。當(dāng)然，如果只有“誰與誰合作”這一個(gè)問題，那么就不需要超圖。
超圖可以回答關(guān)于不明顯結(jié)構(gòu)的問題。例如，第一個(gè)數(shù)據(jù)集的超圖（有六篇論文）可能包括顯示每個(gè)數(shù)學(xué)家對(duì)四篇論文有貢獻(xiàn)的超邊。對(duì)兩組超圖的比較將表明，第一個(gè)數(shù)據(jù)集中的論文作者不同，但在第二個(gè)數(shù)據(jù)集中是相同的。
這種高階方法在應(yīng)用研究中已經(jīng)被證明是有用的。例如，20世紀(jì)90年代，生態(tài)學(xué)家展示了向黃石國家公園重新引進(jìn)狼群時(shí)，生物多樣性和食物鏈結(jié)構(gòu)的變化過程。在最近的一篇論文中，美國西北太平洋國家實(shí)驗(yàn)室的數(shù)學(xué)家milie Purvine和她的同事分析了一個(gè)病毒感染的生物反應(yīng)數(shù)據(jù)庫，使用超圖來確定所涉及的最關(guān)鍵基因。在論文中，他們還展示了這些相互作用是如何被圖論提供的通常成對(duì)分析遺漏的。
康奈爾大學(xué)的Austin Benson最近使用高階馬爾科夫鏈和張量模擬了紐約市的出租車行程。雖然仍有改進(jìn)空間，但結(jié)果比傳統(tǒng)的馬爾科夫鏈要好。
然而，從圖到超圖的泛化很快就會(huì)變得復(fù)雜。例如圖論中的規(guī)范切割問題，該問題問道："給定一個(gè)圖上的兩個(gè)不同的節(jié)點(diǎn)，你最少可以切割多少條邊來完全切斷兩者之間的所有聯(lián)系？給定一個(gè)圖上的兩個(gè)不同的節(jié)點(diǎn)，要完全切斷這兩個(gè)節(jié)點(diǎn)之間的所有聯(lián)系，你能切斷的最少的邊數(shù)是多少？許多算法可以很容易地找到給定圖形的最佳切割數(shù)。
但是如何切割超圖呢？康奈爾大學(xué)的數(shù)學(xué)家Austin Benson說：“有很多方法可以將這種切割的概念推廣到超圖中。但沒有一個(gè)明確的解決方案”，他說“因?yàn)槌吙梢砸愿鞣N方式被切斷，創(chuàng)造出新的節(jié)點(diǎn)組”。
最近，Benson 與兩位同事一起，嘗試將分割超圖的所有不同方式正式化。但對(duì)于某些情況，這個(gè)問題基本上是無法解決，或者說無法確定是否存在解決方案。
超圖并不是探索高階互動(dòng)的唯一方法。拓?fù)鋵W(xué)是一種對(duì)幾何屬性的數(shù)學(xué)研究，其假設(shè)是：當(dāng)你拉伸、壓縮或以其他方式轉(zhuǎn)換對(duì)象時(shí)，這些屬性不會(huì)改變。拓?fù)鋵W(xué)提供了一種更直觀的方法。當(dāng)拓?fù)鋵W(xué)家研究一個(gè)網(wǎng)絡(luò)時(shí)，他們尋找形狀、表面和尺寸。他們可能會(huì)注意到連接兩個(gè)節(jié)點(diǎn)的邊是一維的，并詢問不同網(wǎng)絡(luò)中一維物體的屬性。或者他們可能會(huì)看到連接三個(gè)節(jié)點(diǎn)所形成的二維三角形表面，并提出類似的問題。
拓?fù)鋵W(xué)家把這些結(jié)構(gòu)稱為 simplicial complexes。實(shí)際上，這是通過拓?fù)鋵W(xué)的框架來看的超圖，神經(jīng)網(wǎng)絡(luò)提供了一個(gè)很好的例子。它們由旨在模仿我們大腦的神經(jīng)元如何處理信息的算法驅(qū)動(dòng)。圖形神經(jīng)網(wǎng)絡(luò)（GNNs）將事物之間的連接建模為成對(duì)連接，擅長推斷大數(shù)據(jù)集中缺失的數(shù)據(jù)，但在其他應(yīng)用中，它們可能會(huì)錯(cuò)過僅由三個(gè)或更多群體產(chǎn)生的相互作用。近年來，計(jì)算機(jī)科學(xué)家開發(fā)了 simplicial neural networks，它使用高階復(fù)數(shù)來概括GNN的方法，以求發(fā)現(xiàn)這些效應(yīng)。
simplicial complexes 將拓?fù)鋵W(xué)與圖論聯(lián)系起來，與超圖一樣，它們提出了引人注目的數(shù)學(xué)問題。例如，在拓?fù)鋵W(xué)中，simplicial complexes 的特殊類型的子集本身也是simplicial complexes ，因此具有相同的屬性。如果超圖也是如此，子集將包括其中的所有超邊——包括所有嵌入的雙向邊。
但情況并非總是如此。“我們現(xiàn)在看到的是，數(shù)據(jù)落入了中間地帶，你可以進(jìn)行三向互動(dòng)，但不是成對(duì)的互動(dòng)?！?/span>Purvine表示，“大數(shù)據(jù)集已經(jīng)清楚地表明，無論是在生物信號(hào)網(wǎng)絡(luò)中還是在同行壓力等社會(huì)行為中，群體的影響往往遠(yuǎn)遠(yuǎn)超過個(gè)人的影響”。
Purvine將數(shù)據(jù)描述為數(shù)學(xué)三明治的中間部分，上限是拓?fù)鋵W(xué)思想，下限是圖論。
這種創(chuàng)造性的 "游戲 "感也延伸到了其他工具。在圖和其他描述數(shù)據(jù)的工具之間存在著各種美妙的聯(lián)系。但是一旦你轉(zhuǎn)移到高階設(shè)置，這些聯(lián)系就難以出現(xiàn)了。當(dāng)你試圖考慮馬爾科夫鏈的高維版時(shí)，這一點(diǎn)尤其明顯。
馬爾科夫鏈描述了一個(gè)多階段的過程，其中下一階段只取決于元素的當(dāng)前位置；研究人員已經(jīng)使用馬爾科夫模型來描述信息、能量甚至金錢等事物如何在一個(gè)系統(tǒng)中流動(dòng)。馬爾科夫鏈最著名的例子也許是隨機(jī)漫步，它描述了一條路徑，其中每一步都是由之前的步驟隨機(jī)決定的。隨機(jī)漫步也是一個(gè)特定的圖。任何沿著圖的軌跡都可以顯示為一個(gè)沿著鏈接從節(jié)點(diǎn)到節(jié)點(diǎn)的序列。
但如何擴(kuò)大像步行這樣簡單的東西呢？研究人員轉(zhuǎn)向高階馬爾科夫鏈，它不僅取決于當(dāng)前的位置，還可以考慮許多以前的狀態(tài)。這種方法已被證實(shí)對(duì)網(wǎng)絡(luò)瀏覽行為和機(jī)場(chǎng)交通流等系統(tǒng)的建模非常有用。
Austin Benson
正如前文所言，Austin Benson最近描述了一個(gè)新的隨機(jī)過程模型，該模型將高階馬爾科夫鏈與張量結(jié)合起來。用紐約市的出租車乘坐數(shù)據(jù)集對(duì)其進(jìn)行了測(cè)試，以了解其預(yù)測(cè)軌跡的能力。結(jié)果是喜憂參半：模型對(duì)出租車運(yùn)動(dòng)的預(yù)測(cè)比通常的馬爾科夫鏈要好，但這兩個(gè)模型都不是很可靠。
張量本身是研究高階相互作用的另一種工具，近年來已經(jīng)開始發(fā)揮作用。要理解張量，首先考慮矩陣，它將數(shù)據(jù)組織成行和列的數(shù)組。現(xiàn)在想象一下由矩陣組成的矩陣，或者不僅有行和列，還有深度或其他維度的數(shù)據(jù)的矩陣。這些都是張量。如果每個(gè)矩陣都對(duì)應(yīng)于一個(gè)音樂二重奏，那么張量將包括所有可能的樂器配置。
對(duì)物理學(xué)家來說，張量并不新奇，例如用來描述一個(gè)粒子的不同可能的量子態(tài)。但網(wǎng)絡(luò)理論家采用這一工具來提高矩陣在高維數(shù)據(jù)集中的能力。
前文所述，Benson不確定的出租車模型表現(xiàn)出一個(gè)普遍存在的問題：研究人員何時(shí)真正需要超圖這樣的工具？在許多情況下，如果條件合適，超圖將提供與圖完全相同的預(yù)測(cè)和分析。"亞琛工業(yè)大學(xué)的Michael Schaub問道："如果某些東西已經(jīng)被封裝在網(wǎng)絡(luò)中，是否真的有必要對(duì)系統(tǒng)進(jìn)行建模為高階？
這取決于數(shù)據(jù)集，圖是社交網(wǎng)絡(luò)的一個(gè)很好的抽象，但社交網(wǎng)絡(luò)是如此之多。對(duì)于高階系統(tǒng)，有更多的方法可以建模。例如，圖論可能會(huì)顯示個(gè)人是如何連接的，但不能捕捉到社交媒體上的朋友群是如何影響彼此的行為的。
同樣的高階互動(dòng)不會(huì)出現(xiàn)在每一個(gè)數(shù)據(jù)集中，所以奇怪的是，新理論是由數(shù)據(jù)驅(qū)動(dòng)的：這挑戰(zhàn)了數(shù)學(xué)的基本邏輯。
Purvine表示，"我喜歡數(shù)學(xué)的原因是它是基于邏輯的，如果你遵循正確的方向，你會(huì)得到正確的答案。但有時(shí)，當(dāng)你定義整個(gè)數(shù)學(xué)的新領(lǐng)域時(shí)，會(huì)有種主觀性，即什么是正確的方法。"她說，"如果你不承認(rèn)有多種方法，你可能會(huì)把社區(qū)推向錯(cuò)誤的方向。"
但對(duì)工具的探索代表了一種自由，不僅允許研究人員更好地理解他們的數(shù)據(jù)，而且允許數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家探索新的可能性世界。有無盡的東西可以探索，這很有趣，也很美妙，是很多偉大問題的來源。
雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)
