【代數】AI 的矩陣遊戲
發布時間: 2023.01.06
作者：郭君逸 副教授（國立臺灣師範大學數學系）
※ 引言 ※
大家是否還記得在《 ［乘法突破］衝向數字相乘的運算極限》一文中所介紹的歷史。2019 年時，David Harvey 與 Joris Van Der Hoeven 成功證明了 Schönhage 與 Strassen 在 1971 年所猜測兩數字相乘所需乘法運算次數的上界，有興趣了解這段歷史發展的人可以到上面的連結觀看。今天我們要聊聊主角之一的 Volker Strassen，給我們這個世界帶來的衝擊與目前最新的發展。
※ 人類的第一步 ※
Volker Strassen 最著名的貢獻，是他在 1969 年證明了 n 階矩陣乘法運算複雜度可以比 O(n3) 還要快，而且方法並不難。我們先來簡單體會一下，以二階方陣來說，照矩陣乘法定義去計算時，總共需要進行 8 次乘法，但 Strassen 發現只要 7 次就夠了。
這裡先說明一下，上述的加減法雖然從 4 個增加到 18 個，多了 14 個，但因為同樣 k 位數的乘法，大約要消耗 O(k3) 的時間(每個位數相乘後再將每個位數加起來)，而加法只要 O(k) 的時間(只跑過每個位數一次)，乘法的時間成長規模是三次函數比起加法的線性函數大多了。所以數量大的話，只要比乘法數量即可。
剛剛只是針對二階方陣。那更大一點呢？
當考慮四階方陣時，線性代數告訴我們，可以從中間劃開切成 4 個二階矩陣相乘
同樣的方式，就可以只用到 7 個二階方陣相乘，其它都是加減法，然後每次二階方陣相乘要花 7 個乘法，所以總共要花七七四十九個乘法。同理，八階方陣就是 73 =243 個乘法。
那三階方陣呢？簡單的想法就是把它補零補成四階方陣去處理，也是 49 個乘法，但因為裡面有 10 個元素已確定是零了，所以它們的乘法可以完全不用做，當然加法也不用。 讀者們可以自行驗證，三階方陣相乘，扣掉確定是零的，僅需要 23 個乘法，而五階方陣需要 98 個乘法。請暫時記住這幾個數字（三階、四階、五階）＝（23, 49, 98）!
當 n 階方陣而且 n 很大時，可以證明所需乘法數的增長為 O(nlg 7 )= O(n2.8074 )，【註: 本文中所使用 lg 代表 log2 】。
這就是著名的 Strassen Algorithm，Strassen 當時的論文 [1] 標題為《高斯消去法並非最佳》，只有 3 頁，但到現在已被引用快四千次了。
※ 大矩陣乘法的改進 ※
從 1969 年以來，超多數學家、資訊科學家基於 Strassen 的方法去改進，在我們之前的報導，提到最新的進展是 2014年François Le Gall [2] 的 O(n2.3728639 )。但，就在最近，2021 年，由 MIT 的兩位電腦科學家 Josh Alman 與Virginia Vassilevska Williams [3] 改進到了 O(n2.3728596 ) 。在這篇文章完稿以前，筆者去查了一下 arXiv，未經論文審查證實的最新結果是 2022 年 10 月 18 日，由北京清華大學的段然 [4] 等人發表，採用不同進路將結果推進到 O(n2.37188 )。
※ 小矩陣乘法的改進 –「遊戲」才剛開始 ※
看到 Strassen 神奇的方法後，聰明的讀者有沒有想到要怎麼改進呢？或許有人會想，有沒有可能只用 6 個乘法做二階矩陣相乘？如果可行，立刻就可以改進成 O(nlg 6 )=O(n2.584965)了。
那要怎麼去找這 6 個乘法呢？當然，我們可以用電腦暴力法去試所有可能！
但……要怎麼個暴力法呢？
我們使用不同的角度去審視一下 Strassen 的方法:
問題來了，要怎麼去找這些牌呢？共有多少候選牌？
四列每一列可選 1, －1, 與 0，但不能全 0，所以有 34－1 = 80 種，因為整張牌 1 與 －1 可以互換，所以除以 4 變 20 種；而行也有 20 種，總共有 400 張候選牌從裡面選 6 張出來的所有組合數有約 5.5x1012 種，看看有沒有哪種可以組出 A,B,C,D 這四個位置。
這過程很像是在驗證三階魔術方塊的 4.3x1019 種可能狀態是否都能在 20 步內轉出來。
整個搜尋數量規模驚人，但 Shmuel Winograd 把它驗證完了，證明無法只用 6 個乘法來完成二階矩陣乘法，也就是說，Strassen 的方法是最佳的。
「天啊! 太神奇了! 必須再說一次，他到底是怎麼在沒有電腦的輔助下找到這 7 張牌的…」
二階矩陣用電腦找最佳解都這麼困難，更別提想用同樣方式找三階矩陣的乘法運算最佳解了，總共有大約 2.4x10141 這麼多種。
正如 DeepMind 的研究員 Alhussein Fawzi 所說: 「找三階方陣乘法運算的最佳解，必須要搜尋的方法數超過整個宇宙的原子數量。」
※ AlphaTensor 橫空出世 ※
不久前( 2022 年 10 月 5 日)，DeepMind 在國際頂尖期刊《Nature》 上發表了一篇文章 [5]。
當期《Nature》雜誌封面
在摘要中就宣布他們利用 AlphaTensor，打破目前乘法次數的紀錄。其中第三作者 Aja Huang 就是師大資工系碩士班畢業的黃士傑，也就是前陣子首次電腦在圍棋上打敗人類的 AlphaZero 主要開發者之一。此文章也是該期的封面頭條。
DeepMind 和我們常用的 Google 都是 Alphabet 的子公司之一。DeepMind 先是開發了 AlphaZero，一款會下圍棋的 AI，成功打敗人類棋王。在此之前，沒人覺得人類會在圍棋競賽輸給人工智慧，因為圍棋的搜尋樹之大，不是接下來四五十年的電腦可以窮盡的，但它終究發生了。
而減少矩陣乘法使用的乘法數，就很像在一堆牌中找一些有效牌來滿足某個條件的遊戲，於是 DeepMind 就把它真的改成一個遊戲，然後把 AlphaZero 改成 AlphaTensor，來執行這項尋找有效牌的任務。
依 DeepMind 所述，這遊戲每一步的搜尋分支，是 AlphaZero 的三十倍規模，可見其複雜度。不過他們做到了，使用人工智慧改進了人類的演算法。
文章中，AlphaTensor 在三、四和五階方陣乘法中分別找到的乘法數為 23, 49, 98，這部份跟文獻一致。但若是在 Z2 的話(矩陣元素只有0,1)，就會是 23, 47, 96 個乘法數。
不只方陣，AlphaTensor 也嘗試一般矩陣相乘，論文中把行列數在 5 以下的結果列舉出來，如右表。
其實他們找了所有 12 以下的矩陣乘法，其中有 70 幾種，都改進了文獻中的已知結果，實在太驚人了。AlphaTensor 程式碼都是公開的，有興趣的人，可以到 GitHub 下載來試試。
※ 人類的逆襲 ※
先別急著把視窗關掉，故事還沒完。
DeepMind 的論文在 2022 年 10 月 5 日才剛發表，奧地利「約翰克卜勒林茲大學(Johannes Kepler University Linz, JKU)」的代數研究所 (他們竟有代數研究所) 的 Manuel Kauers 教授，與他的博士生 Jakob Moosbauer，才過三天就在 arXiv 上發表了一篇文章 [6]，標題非常聳動(如圖)：
標題的 FBHHRBNRSSSHK，指的就是 DeepMind 在 Nature的論文作者姓氏縮寫。AlphaTensor 在五階 Z2 矩陣相乘的運算量已經降低到 96 個乘法數，但他們又再降了一點，變成了 95 個，然後也找了另一種 47 步的四階的 Z2 矩陣乘法，論文很短，就是把這 47 張與 95 張牌列了出來。
真可謂為人類的逆襲啊！
※ 結語 ※
目前深度學習非常火紅，有可以作畫的 AI，像 Dall-E、Disco Diffusion、…之類的；
可以像人類一樣對話的 AI，像 ChatGPT、YouChat、…等等；
可以寫長篇文章的 AI，像 Jasper Chat；
可以幫你寫程式的 AI，像 Ghostwriter Chat；
幫你做投影片的 AI，像 ChatBCG…。
這些深度學習的 AI 都要用到大量的矩陣運算，而 AlphaTensor 的出現，在演算法層面加快了現有的矩陣運算，而硬體層面也可以把這些寫到處理器上，稱為 TPU(Tensor Processing Unit)，可以讓 AI 的矩陣運算快 10% 以上，目前Google 出的手機 Pixel 6 與 7 代，所使用的處理器就稱為 Tensor，專為人工智能而生的 TPU。(可以參閱泛科學的Youtube影片：https://youtu.be/K1Hs-k19EwQ )
若說 DeepMind 的 AlphaTensor 是『拋磚引玉』，啟發大家，AI 是可以用來輔助研究工作的工具；那麼 Kauers 和 Moosbauer 兩人的文章，可算是『拋玉引鑽石』，展示人類憑藉「真．人工智能」，還是有機會打敗「人工智能」的。
但若人類跟 AI 能相輔相成，或許很多的研究工作都能因而往前跨一大步，像是用來輔助數學證明，例如圖論中的四色定理，或許可以用 AI 降低需驗證的潛在反例數量也說不定。
未來，人工智能只會越來越強大，筆者預估，十年之後，很多的電話客服、線上客服都會變成是人工智能。然後再過個十年，或許像「百科」一樣的真人 AI 客服也會出現。
參考文獻
1. Volker Strassen, Gaussian Elimination is not Optimal, Number. Math. 13, 354-356(1969).
2. François Le Gall, Powers of tensors and fast matrix multiplication, ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. July 2014 Pages 296–303https://doi.org/10.1145/2608628.2608664
3. Alman, Josh & Williams, Virginia. (2021). A Refined Laser Method and Faster Matrix Multiplication. 10.1137/1.9781611976465.32.
4. Ran Duan, Hongxun Wu, Renfei Zhou, Faster Matrix Multiplication via Asymmetric Hashing, https://arxiv.org/abs/2210.10173
5. Fawzi, A., Balog, M., Huang, A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610, 47–53 (2022). https://doi.org/10.1038/s41586-022-05172-4
6. Manuel Kauers, Jakob Moosbauer, The FBHHRBNRSSSHK-Algorithm for Multiplication in Z5×52 is still not the end of the story, https://arxiv.org/abs/2210.04045