局部最優和全局最優

07-28

局部最優和全局最優

來自專欄匠心觀道4 人贊了文章

無論是早期學演算法的時候，還是後來學習機器學習的時候，局部最優和全局最優都是演算法考慮的一個重要方面。站在上帝角度上當然知道需要全局最優是最好的，但是在設計演算法的時候，怎麼才能保持全局最優又不至於一個一個枚舉或者模擬，卻是一個非常複雜的問題。

時間和空間，歷史和演算法的局部最優

比如如何找到在容量有限的背包中放入最大價值的物品，可以用很簡單的演算法去在每一步的時候都選擇性價比最高的，但最後結果不一定最優；也可以把所有放置方案都試一遍，但問題複雜的時候會變得非常困難。這時候要設計一個時間上不會很久但又能確保最優的方案就非常困難了。

同樣的機器學習中，對於目標函數很有可能不斷調整參數過程中，越來越接近一個範圍內的極大值，但是卻不是整個問題的最大值，演算法很可能設計上就不可能跳出這個範圍。

其實社會或者歷史也是這個問題，比如中國兩千年封建史就是在一個局部最優的狀態下不斷優化的過程，最後的社會架構非常有益於封建統治者，但是卻不是人類歷史最優的，這直到光緒帝的時候才被大家認識清楚。

這當然不能完全歸罪於皇帝們只顧自己私利，不想著整個國家的優化。事實上，清朝以正統自居，皇帝們平均勤政程度可能也是歷朝歷代中在前列的。實在是因為，作為系統里的玩家，即便是最大權利和最重要玩家，也是沒有能力直到全局最優是怎麼樣的。

不像我們設計演算法的時候，明確知道問題的範圍和最優的標準，社會和歷史中的各個玩家是沒有辦法直到問題的範圍和最優標準的，所以最後很可能會陷入到局部最優的狀態中。這就好像下圍棋時的劫，如果沒有規則限定，雙方會互相打劫無限循環。

這種局部最優有空間上的，比如在一個缺乏競爭的社會系統中，個體晉陞的途徑是通過關係和血緣，這並不是因為大家意識不到任人唯賢的重要性，所有的教育考核系統的改革都是往這方面努力的，但從沒有成功過，這是因為沒有競爭的狀態，對於系統最優的方式是選用更加可靠的人，這導致了最終社會系統會選擇熟悉的人。

也有時間上的局部最優，比如中國封建社會隨著朝代的更迭，皇權是逐步加強的，這就是在時間軸上不斷優化前一個時間點的系統設計導致的。

為什麼至今人類歷史總是能跳出小歷史循環中的局部最優呢？

外部原因是因為走另一條道路的社會在擴張過程中和陷入局部最優的社會相遇，打破了原有的平衡，設定了新的全局最優方向。比如東亞在皇權局部最優過程中遭遇了西方文明，設定了新的走工業科技的方向，在優化過程中又不斷調整目標，如走政治文明路線等等。

內部原因是內部平衡因為氣候或其他意外打破，跌入一個並非最優的狀態，並探索到了走向更優的狀態。比如明末諸多事件導致漢族主體的華夏平衡被破壞，在過程中探索到了外東北外蒙和西北的狀態。

我很擔心的一點是，現在雖然有各種科技進步、政治改革，但本質上並沒有根本改變，是在加速進入一個更大的局部最優中，科技讓絕大多數人生活的很舒適，政治體系讓戰爭可能性變小。但是這個平衡更難打破，因為雖然有諸多問題，這些問題都沒有成為打破平衡的資格，所以大多是慈善機構和其他非營利機構略顯徒勞的進行改進。而如果平衡因為地球環境改變或外星入侵而打破，不是承平日久的人類所能承受的。

怎麼才能保持走向全局最優呢？

從演算法設計中的思路是這樣的，第一種方法是通過空間上的多方案備份來得到未來的最優，這個思路來自於當前的次優不意味著未來的次優。可惜在這個時間線上，西方文明擴張太快，導致大量其他大陸文明的消失。也許在另外一個時間線上，利用西方科技文明和瑪雅神秘主義會進化出不一樣的文明。比如瑪雅文明嚮往月球，可能在接受西方文明後，更多的社會資源會投向月球殖民。

第二種方法是不斷突變當前環境和方案，這個很難自我生成，因為很難強迫百分之多少的人口進行思維的突變，而且非常依賴於整個社會的狀態。而依靠外界的話，例如環境變化等等，那就是非常危險的了。