2016年7月27日 星期三

如螞蟻般聰明的網路?

Analysis of ant colony behavior could yield better algorithms for network communication
July 13, 2016 
Larry Hardesty
paper


螞蟻很擅長判斷在他附近螞蟻的密集程度。這能力在螞蟻的公共事務特別有用,尤其當他們投票要遷去哪個新巢。生物學家猜測當螞蟻在隨機的探索環境時,他們就可以用遇到螞蟻的頻率來估計螞蟻群的密度。



前述的理論最近獲得新的支持。麻省理工的電腦科學及人工智慧實驗室即將向 ACM PODC (Association for Computing Machinery's Symposium on Principles of Distributed Computing conference) 發表有關的論文,該論文內提及隨機探索環境可以很快速又準確地得知分布的密度,這個方法推算的速度基本上近乎理論值的極限。


除了支持生物學家預測之外,這裡論的架構更應用到社群網路、機器人的共同決定、隨機網路(ad-hoc network)的溝通,例如:散步於有限區域的低成本感測器之間的溝通。

MIT 電資學院的研究生 Cameron Musco 說道:「當我們在一個區域裡隨意走動時,我們可以很直觀的了解,我們碰到人的頻率是可以轉換成分佈密度的。我們在做的事,只是給出個很嚴謹的證明並證實他的準確性相較於其他粗糙的方法。且隨著時間的推移,這方法推斷的結果就越發準確,並且速度達到我們所預期的極限。」

Cameron Musco 、指導教授 Nancy Lynch、博士後研究員 Hsin-Hao Su,把螞蟻的環境比喻成一格格的網格(grid),裡面有一些螞蟻。其中有一隻螞蟻,我們特別有興趣。它移動到周圍格子的機率相同,然後就繼續動下去,那隻螞蟻會細數它究竟遇見多少隻螞蟻。在統計學的觀點下,這被稱為隨機漫步(Random walks)。

在他們的論文裡,研究員拿隨機取樣(
random sampling)和隨機漫步做比較,網格是隨機的、螞蟻數是用數的。這兩種方法的準確性都隨著增加的取樣數而提高,值得注意的是,隨機漫步的方法和隨機取樣的速度是一樣快的。

這個推論很重要,因為我們常常不是用隨機取樣去做統計。據個例子,假設我們要分析在自己的臉書上表明自己是親民黨員的比例,我們不可能取的社群網路上所有人的名單,我們只好從隨機一個人下手,然後從他的朋友慢慢去過濾,這方法就會比較可行。

同理,在隨機網路裡,一個裝置只會知道它很進的附近有哪些其他的裝置。以隨機漫步的演算法對食物上比較容易收集到所需的感測資料。

這結果令人震驚,因為那隻探索環境的螞蟻即有可能重複採樣到同一個格子,然而隨機取樣的方法就不會。

起初,Cameron Musco 和他的同事都認為,重複取樣將是這個演算法計算密度最大的缺點。所以他們設法排除重複取樣的可能性,萬萬沒想到,這樣反而降低隨機漫步的效能。直到最近,他們終於有辦法解釋了。

Cameron Musco 提及,當我們在一個網格面上面隨機漫步時,我們不可能和每個人相遇,因為我們不太可能會走遍全網格。所以我遇到遠方人們的機率近乎是0,然而如此,我遇到比較近的人的機率就大幅提升,我可以拿我遇到重複的人來代替(隨機取樣中可以遇到)遠方的人,結果顯示,他們會達到美好的平衡,這個很容易證明卻不太直觀。

這種網格狀的東西,是研究員將螞蟻環境簡化成為一個模型(graph),裡面有些點(螞蟻可能的所在),點和點是用線(螞蟻路線)連結,在這樣的假設下,螞蟻夏禕不一定是鄰近的格點。

研究員所使用的分析方法卻可以套用到任何相似的圖形,如社群網路、隨機網路之類的。

但是如果這個點線圖形沒有很好的連接如一串點在同一條直線上,重複取樣將會是個大問題,因為那隻螞蟻將會重複地在特定幾個鄰近點徘徊。

當兩個人隨機漫步但起始於同一起點,他們最後的方向大致是不一樣的。社交網路的模型也有類似的概念,但是隨機漫步的精準度並不因為如此而降低。

而且,研究員在論文上是用一個探索者。但如果有多個探索者,正確結果就更容易且更快速準確地出現。他們玩笑地說到,如果那些探索者是機器人不是螞蟻,他們就可以在相遇時和對方問好並交換資料和結果。

亞利桑那州大學的環境生物學助理教授 Anna Dornhaus 說道,教授 Nancy Lynch 的專業領域是分散式運算,教授深刻的了解,生物學皆對這方面不太了解,但是當他們了解這方面,生物學家對大自然的了解程度將會有長足的進步,所以 Nancy Lynch 不斷的在做跨領域的研究期望能使大自然的奧秘更加顯露。