SODAPDF

機器之心報道

編輯：小舟

「猜」也是解決問題的一種方法。

「今有雉兔同籠，上有三十五頭，下有九十四足，問雉兔各幾何？」

這是《孫子算經》中雞兔同籠問題的經典描述。我們知道，二元一次方程組可以解決這個問題。求解線性系統有矩陣乘法等多種方法，但或許你不知道，靠「猜」也是可以的。

來自佐治亞理工學院的兩位研究者給出了一種「猜」的方法，并斬獲算法研究頂會 SODA 2021 的最佳論文獎。

論文地址：https://arxiv.org/pdf/2007.10254.pdf

正如該方法的研究者之一 Vempala 所說，「線性系統是現代計算的主力軍」，在實際生活中的應用是非常廣泛的。建造一座堅固的橋梁、一架隱蔽的飛機都需要解決包含數百萬個方程的線性系統。此外，線性系統與許多計算機科學問題相關，這些問題涉及在約束系統內為一組變量尋找最佳值。如果可以更快地求解線性系統，那么我們也可以更快地解決這些計算機科學問題。

使用矩陣乘法求解線性系統的方法嚴重限制了計算速度。事實上，在這項研究提出的新方法中，矩陣乘法仍然發揮了一定作用，不過只起到補充作用。研究者將其與一種新方法結合起來：本質上，那是一種經過訓練的「猜測」方法。

動物同籠問題

回到經典的動物同籠問題，假設一個巨大的籠子中含有雞、單角犀牛和山羊三種動物，已知有 12 個頭，38 只腳和 10 只角。你能知道每只動物有多少只嗎？

首先為每只動物分配一個變量（c 代表雞，r 代表犀牛，g 代表山羊），并根據已知屬性（包括頭、腳、角）編寫多個方程式。每個變量前面的數字（或系數）反映了每只動物擁有該屬性的數量。

現在就有了三個方程式和三個未知數。

解決該問題的一種方法是操作一個方程式，并根據其他兩個方程式定義一個變量。例如，0c + 1r + 2g = 10 變成 r = 10 – 2g。在其他兩個方程式中用該值替換 r，然后像這樣繼續進行，直到僅用一個變量定義了所有變量，就可以精確求解。然后，你可以重復執行此過程，利用已求解的變量來求解下一個變量。

另一種更復雜的處理方式是創建一個方程組的系數矩陣，如下：

然后用另一個矩陣表示雞、犀牛、山羊的未知數量：

然后再用一個矩陣表示頭、腳、角的數量：

我們可以將上述 3 個矩陣組成一個線性系統，其中第一個矩陣乘第二個矩陣等于第三個矩陣。然后可以利用線性代數的知識求解第二個矩陣中的未知數。

無論是使用方程式還是采用矩陣的形式，計算復雜度都是 O(n^3)。例如有四種變量和四個方程，則需要 4^3，即 64 步操作。

降低計算復雜度

在現實應用的復雜問題中，變量數目很大，計算量也會非常大。幾十年來，研究人員們一直致力于發現更有效的求解方法。

1969 年，Volker Strasn 設計了一種算法，將矩陣乘法的復雜度降到了 O(n^2.81)。從那時起，數學家和計算機科學家們就致力于進一步降低指數。來自麻省理工學院的 Virginia Vassilevska Williams 以及哈佛大學的博士后研究員 Josh Alman，將計算復雜度降低到了 O(n^2.37286)，比此前最好的結果指數下降了 0.00001。

這些研究表明任何線性系統的求解都可以歸結為一個矩陣乘法的問題。到目前為止，理論上矩陣乘法的復雜度至少可以降至 O(n^2.37286)。

但是，多種方法表明，求解線性系統的速度應該比這更快，只需要 O(n^2)。使用矩陣乘法是因為它是目前可用的最佳工具，但這并不意味著不存在更好的工具。

Vempala 說：「求解線性系統的問題沒有理由只依賴于矩陣乘法的改進。」在新方法中，彭泱和 Vempala 將算法復雜度降到了。

靠「猜」的解決方案

為了了解新的改進工具，我們首先要了解另一種求解線性系統的方法。它是一種直觀的方法，回想雞兔同籠問題，你可以簡單猜測雞和兔子各有多少只，然后代入等式，看看離正確答案差了多遠，然后再猜一次。

這種「迭代方法」是工程師和科學家經常采用的方法。它可以很好地解決許多實際問題，因為專家通常不會盲目猜測，從而減少了在找到解決方案之前需要反復進行猜測的次數。

彭泱說：「對于現實世界中的科學計算問題，人類對答案應該具備良好的直覺。」

迭代方法在特定示例下是非常有效的，當求解的線性系統中包含大量系數為 0 的變量時，迭代方法也是很有效的。

在更復雜的線性系統中，這種關系（其中并非所有屬性都與所有變量相關）可以普遍存在。有些線性系統可能有數百萬個變量和數百萬個方程式，但是每個方程式中可能只含有部分變量，這類線性系統稱為「稀疏」，意味著大多數方程中大多數變量取零值，線性系統中經常會出現這種情況。

Williams 說：「只有當矩陣足夠稀疏時，這種方法才會有效。」但是在這項研究之前，沒有人能夠證明對于所有稀疏線性系統，迭代方法總是快于矩陣乘法。

協調隨機性

彭泱和 Vempala 的新方法采用了迭代猜測策略的增強版本：他們的算法不僅可以進行單個猜測，而且還可以并行進行多個猜測。這種方法可以加快搜索速度?；F盧大學教授 Giesbrecht 說：「并行才是魔法所在。」

一次進行多個猜測似乎是有用的，但是想讓該策略起作用并不是那么簡單。新算法的有效性在很大程度上取決于如何聰明地做出引發迭代過程的初始猜測，以及找到將并行猜測的結果組合成單個最終答案的巧妙方法。

回到動物同籠的問題，該算法可能會首先進行三個初始猜測，其中每個猜測都是一個 3×1 矩陣，該矩陣指定了雞、犀牛和山羊的數量。該算法將觀察每個猜測距離正確答案有多遠，然后進行更多猜測，持續進行并行猜測線程。

該算法最終成功的關鍵在于，它會隨機進行三個初始猜測。隨機性似乎并不適合猜測，但它作為一種通用方法具備其獨特的優勢，尤其是在處理大量問題時，優勢更加明顯。也就是說，隨機性能夠保證最終搜索不會偏向問題的某一部分，否則可能會忽略實際上解所在的空間。

彭泱說：「我需要確保所有的猜測都是足夠隨機的，以便它們涵蓋所有可能的組合。這是一種非常糟糕的猜測方法，但隨著問題變得越來越大，這最終成為首選方法?！?/p>

在該研究中，許多技術問題都涉及證明隨機猜測的不同部分也可以協同工作，包括實際上是最終解的任何特定猜測。Vempala 表示：「存在協調隨機性」。

這意味著隨機猜測不僅可以包含猜測本身的確切值，還可以涵蓋介于兩者之間的所有潛在猜測。這類似于兩個人在森林中搜尋并不只是搜尋他們所走的地面，還會搜尋他們的整個視野區域。Vempala 說：[兩個猜測之間的所有內容也包括在內。]

此搜索功能可確保算法將在某處找到答案。但是它本身并不能識別答案。因此彭泱和 Vempala 還需要進行進一步的證明工作。

該算法將隨機猜測作為矩陣中的條目進行追蹤。在矩陣的各個條目中尋找解使得問題變成了矩陣乘法問題，這當然是他們要規避的障礙。但是在此，他們再次利用了隨機性。因為矩陣中的條目是隨機的，并且經過了協調，矩陣最終會具有一些對稱性。這些對稱性使得計算過程中可以利用一些快捷計算方法。

矩陣的對稱性還有另一個好處，即能夠保證猜測永遠不會太大，避免在算法效率的層面上難以理解。彭泱和 Vempala 的算法可以比沒有對稱性的矩陣更快地在矩陣中找到解。

作者介紹

個人主頁：https://www.cc.gatech.edu/~rpeng/

該論文的一作是是佐治亞理工學院計算機科學學院的助理教授彭泱。

彭泱是江蘇南京人，本科畢業于滑鐵盧大學數學專業，后在卡內基梅隆大學取得計算機科學博士學位，以及在 MIT 擔任博士后。他的研究興趣是高效算法的設計，分析和實現，曾獲 NSF 職業獎，微軟研究博士獎學金和 CMU SCS 杰出論文獎。2015 年起擔任佐治亞理工計算機科學學院助理教授。

2000 年，彭泱隨家人移民至加拿大，曾獲得 2004 年和 2005 年加拿大計算機比賽金牌。8 年級時，彭泱參加 10 年級水平的美國數學比賽，并取得滿分的成績。在 2005 年的第 46 屆國際奧林匹克數學比賽中，他代表加拿大隊摘得銀牌，2006 年又摘得銅牌。

個人主頁：https://www.cc.gatech.edu/people/santosh-vempala

論文另外一位作者是佐治亞理工學院計算機科學系的教授 Santosh Vempala。他的研究興趣包括算法、隨機性、計算幾何、計算學習理論等。

參考鏈接：

https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/