標籤：

聖塔菲研究所提出的新排序演算法：從鸚鵡啄序到終身教職

08-21
聖塔菲研究所提出的新排序演算法：從鸚鵡啄序到終身教職

來自專欄人工智慧學習筆記6 人贊了文章

啄序（Pecking order）或啄食順序或啄食次序指群居動物通過爭鬥取得社群地位的階層化及支配等級區分現象。圖片來源：Greg Matthews

編譯：集智翻譯組

來源：santafe.edu

原題：Parakeet pecking orders, basketball match-ups, and the tenure-track: How analyzing winners and losers can reveal rank within networks

NCAA 籃球排名只是新演算法 SpringRank 勝出的領域之一。如上圖所示，高於分割線的點表明 SpringRank 預測的比賽結果更加準確。（圖片來自 Caterina De Bacco，Dan Larremore 和 Cris Moore）

有時候，知道誰贏誰輸比知道比賽怎麼打更加重要。

在7月20日發表在 Science Advances 上的一篇論文【1】中，來自聖塔菲研究所的研究員描述了一種名為 SpringRank 的新演算法，該演算法利用輸贏揭示潛藏於大型網路中的位次信息。本研究測試了大量的人工合成以及真實數據的數據集，從 NCAA 大學籃球聯賽團隊數據到動物社會行為學數據。測試結果表明，SpringRank 演算法的預測結果和效率優於其他排名演算法。

哥倫比亞大學的物理學家 Caterina De Bacco 是聖塔菲研究所的博士後，他表示，SpringRank 使用的是已經內置在網路中的信息。本演算法分析個體間兩兩相互作用的結果。例如，為了給 NCAA 籃球隊排名，該演算法會把每一個球隊視為一個單獨的節點，把一場比賽的輸贏關係視作一條邊，一條從勝利球隊指向失敗球隊的邊。SpringRank 會分析這些邊，沿著邊的方向遍歷，以此確定層次結構。但這個演算法過程不僅僅是「給贏的比賽最多的球隊最高排名」；畢竟，一支專門虐菜鳥的球隊不值得上榜。

現在科羅拉多大學博爾德分校的數學家 Dan Larremore 說，「這不僅僅是一個輸贏問題，而是你擊敗了哪支球隊以及你輸給了哪支球隊」。他曾是 Omidyar 的成員。Larremore、De Bacco 與聖塔菲的計算機學家 Cris Moore 合作了本論文。

顧名思義，SpringRank 將節點之間的連接視為可以伸縮的物理彈簧。 De Bacco 表示，因為物理學家早就知道描述彈簧運動的方程式，所以演算法就很容易實現。不同於其他的那種「非得排出個一二三」的次序排名演算法，SpringRank 為每一個節點分配一個實數值。因此，節點可以緊緊的挨在一起，也可以分離的很遠，甚至顯示出更為複雜的排列模式—— 相似的節點會組成集簇。

「來自物理學的思想經常為我們提供優雅又有效的演算法，」Moore 說，「本成果這種方法的又一次勝利。」

在本論文中，研究人員測試了 SpringRank 演算法在各種數據集和情境中的預測能力，包括體育比賽，圈養的鸚鵡與放養的亞洲象中的動物支配行為，以及大學裡的教職招聘實踐。

研究者把 SpringRank 的代碼發布到了線上代碼倉庫 Github 【2】上。他們希望其他的研究者（特別是社會科學的研究者）能夠試用本演算法。De Bacco 表示：「本演算法能勝任任何的資料庫。」

她和她的合作者計劃用 SpringRank 分析的下一個數據集與 Science Advances 精選過的任何論文都不同。他們將與聖塔菲研究所的外聘教授 Elizabeth Bruch 合作，分析在線約會平台的消息傳遞模式。

在真實排名是已知的人工合成數據集上進行測試時，SpringRank 的表現優於其他廣泛使用的演算法。

參考

  1. advances.sciencemag.org
  2. github.com/cdebacco/Spr

翻譯：Leo

審校：李時嘉

原文地址：

santafe.edu/news-center

推薦閱讀

一文讀懂複雜網路與群體智慧

論文解讀：複雜網路的多尺度動態嵌入技術

解讀冪律與無標度網路

加入集智，一起複雜！集智俱樂部團隊招新啦！

活動預告

公開活動：Python 過時了？和 C 一樣快的科學計算語言 Julia 了解一下！

集智QQ群｜292641157

商務合作及投稿轉載｜swarma@swarma.org

◆ ◆ ◆

搜索公眾號：集智俱樂部

加入「沒有圍牆的研究所」


推薦閱讀：

TAG:演算法 | 人工智慧 | 深度學習DeepLearning |