伯克利提出 AdaSearch：一種用於自適應搜尋的逐步消除方法
在機器學習領域的諸多工當中，我們通常希望能夠立足預先給定的固定資料集找出問題的答案。然而，在某些應用場景下我們並沒有先驗資料可供參考 ; 相反，我們必須自行收集資料以回答那些自己感興趣的問題。舉例來說，這種情況在環境汙染物監測以及人口普查類調查中就比較常見。自行收集資料的方式，使得我們能夠將注意力集中在相關度最高的資訊來源身上。然而，確定哪些資訊來源能夠生成有用的指標同樣不是件易事。此外，當物理代理（例如機器人、衛星、人類等）進行資料收集時，我們必須首先規劃需要測量的指標，以便縮短代理活動時長並降低相關成本。我們將這個抽象問題，稱為 自適應感測 。
我們引入了一種新的方法以體現自適應感知問題，其中的機器人必須遍歷所處環境以識別值得關注的位置或物件。自適應感測涵蓋機器人技術當中眾多已經得到充分研究的問題，包括快速識別意外汙染洩漏與放射源，以及在搜尋與救援任務當中尋找人類目標等。在這類場景當中，設計一條能夠儘快返回正確解決方案的感測軌跡往往直接決定著任務的成敗。
在這裡，我們以放射源搜尋（簡稱 RSS）問題為例，其中無人機必須在所處環境中發現 K 個最為嚴重的發射性源頭，而 K 為使用者定義的引數。放射源搜尋屬於自適應感測問題中一類特別有趣的例子，這主要是因為其中往往存在大量異質化明顯的背景干擾，此外我們還很難找到適合統計置信區間且擁有良好表徵的感測模型。
在這裡我們引入了 AdaSearch，一套用於常規自適應感測問題的逐步消除框架，這裡將在放射源搜尋場景下進行演示。AdaSearch 能夠持續且明確地提供環境中每點放射率的置信區間。利用這些置信區間，演算法將以迭代方式識別可能作為主要放射源的一組候選點，同時排除掉其它的點。
以體現搜尋作為多重假設檢驗場景
從傳統角度來講，機器人社群一直將體現搜尋（embodied search）目標設想為連續運動規劃問題。其中，機器人必須在環境探索與有效軌跡選擇之間做出有效平衡。這一基本思路意味著原有演算法會將軌跡優化與探索結合至單一目標當中，從而利用滾動優化控制進行優化（參見 ofollow,noindex">Hoffman 與 Tomlin、 Bai 等人、以及 Marchant 與 Ramos 的各自相關論文）。但我們的想法與此不同：我們希望建立起一種替代性方法，通過假設檢驗將問題表述為一種可排序的最佳行動識別。
在可排序的假設檢驗當中，我們的目標是通過迭代方式收集資料，從而針對多個單獨問題得出結論。我們為代理提供一組 N 個測量行動，其中每種行動都根據不同的固定分佈產生觀察結果。
代理的目標是學習這些 N 個觀測分佈的一些預先指定的性質。舉例來說，在“A/B 測試”這一統計問題當中，測量行動對應於向新客戶展示產品 A 或產品 B，同時記錄他們對於相關產品的評估意見。在這裡，N=2，因為其中只涉及兩種行動——向客戶展示產品 A，以及向客戶展示產品 B。其中需要關注的屬性，在於哪款產品得到的平均反饋更好（如下圖所示，B 的反饋更好）。隨著收集到客戶的偏愛情況，我們將能夠獲得產品樣本平均反饋以及與之相關的置信區間，這一區間由每款產品的置信區間下限（簡稱 LCB）與置信區間上限（簡稱 UCB）予以描述。隨著收集到的測量值不斷增加，我們對於每款產品的反饋預估將更為自信，換言之我們能夠進一步確定兩款產品的真實排名。從結果來看，只要達成下述條件，則產品 B 的反饋要好於產品 A：如果產品 B 的置信下限高於產品 A 的置信上限，即可基本斷定產品 B 的平均反饋情況有很大機率高於產品 A。
在環境感測場景下，每種行為都對應著一組來自給定位置與方向的感測器讀數。通常來講，代理希望瞭解哪項單一度量行為能夠帶來最大的平均觀察訊號值，或者說一組 K 項行為能夠帶來更高的總體平均觀察值。為了實現這一目標，代理可能會利用以往觀察到的結果按排序選擇行為，從而儘可能採取具有最大平均觀察值的行為以實現潛在的行動收益。
乍看起來，最佳行為排序識別這種方法似乎過於抽象了，很難在具體的移動感測代理當中發揮作用。但事實上，代理可以選擇任意度量行為序列，而無需考慮潛在成本，例如與變更行為相關的活動時間。與此同時，最佳行動排序識別機制自身的抽象性質正是其最強大的力量所在。通過以精確的統計語言制定具體的搜尋問題，我們得以制定出與每項感測行為相關的可操作觀察置信區間，同時在確定需要關注的目標觀察點之前整理出所需採取的所有行為集合。
我們提出的具體搜尋方法正是 AdaSearch，其利用來自最佳行為排序識別與全域性軌跡規劃的啟發式置信區間，從而分步漸近地實現複雜度最優度量，同時有效分攤活動成本。
放射源搜尋
為使闡述更加具體，我們將以單一放射源搜尋問題為場景解讀 AdaSearch 的工作原理。我們將環境建模為一套平面網路，如下圖所示。其中只存在一個高強度放射性源（下圖中紅點位置）。然而，定位該位置非常困難，因為感測器的測量功能會被背景輻射（即粉紅點位置）所幹擾。我們通過在網格上方部署配有輻射感測器的四旋翼飛行器來獲取感測測量值。這一案例的目標，在於設計出一系列軌跡以確保機載感測器能夠獲得正確的測量值，從而使我們能夠儘快將放射源位置與背景放射位置區分開來。
AdaSearch
我們的 AdaSearch 演算法將全域性覆蓋規劃方法與基於假設檢驗的自適應感測規則相結合，旨在定義出最優軌跡。在第一次進行網格探索時，我們會對整體環境進行均勻取樣。
在經過第一輪探索與測量結果觀察之後，我們可以略去其中一部分割槽域。如果某個點的置信區間上限低於其周邊任何點的平均觀察值置信區間下限，則將該點排除——這意味著其不太可能是我們需要搜尋的放射來源。
在下一輪搜尋中，AdaSearch 將專注於對作為潛在放射源位置的剩餘點（即綠色方塊）進行更細緻地取樣。
整個過程將不斷繼續，每輪的候選放射源數量也將持續減少，直到最終只剩下一個點。AdaSearch 會返回此點（即放大的紅點），這就是搜尋工作最終給出的放射源答案。
由於整個統計公式清晰可信，因此我們基本可以肯定在已知的感測模型下，AdaSearch 有很高機率能夠返回正確的放射源位置。我們在演算法的整個執行過程當中設立固定的各單獨區域周邊置信界限寬度（以標準差方式），從而確保該概率具有一定程度的置信度。此外，AdaSearch 還提供特定於具體環境的執行時保證，更多詳情請參考我們的論文。（ https://arxiv.org/abs/1809.10611 ）。
實驗基準
對於常規自適應搜尋問題，目前最流行的解決方案當數資訊最大化（ Bourgault 等人 提出）。資訊最大化方法的基本思路在於根據資訊理論標準在高機率位置收集測量值，並遵循滾動優化規劃以進行軌跡規劃。下面，我們將把 AdaSearch 與同樣針對放射源搜尋場景定製的資訊最大化方案 InfoMax 進行比較。
遺憾的是，對於規模較大的搜尋區域，這種方法的實時計算存在諸多侷限，例如只能給出規劃範圍與軌跡引數化的近似結果。這些近似結果可能導致演算法貪婪性過高，且浪費太多時間以追蹤無法解決問題的錯誤線索。
為了消除統計置信區間與全域性規劃啟發（這一組合直接對打 InfoMax 中的資訊指標與滾動優化規劃）間的歧義，我們選擇一種簡單的全域性規劃方法 NaiveSearch 作為輔助基準。該方法會均勻地對網格進行取樣，且保證在每個網格單元處花費相同的取樣時間。
實驗結果
我們建立起全部三種演算法，並立足一套以 4 米為基本網格單位的 64 x 64 環境下利用模擬四旋翼無人機加模擬輻射感測器讀數對其進行了測試，希望瞭解三者在十種隨機例項排佈下的具體效能。
在我們的實驗中，我們觀察到 AdaSearch 在計算完成速度總體上快於 NaiveSearch 以及 InfoMax。隨著我們不斷增加背景輻射的最高水平，AdaSearch 相較於 NaiveSearch 的執行時間比較優勢亦持續提升，這與論文中提出的理論界限相符。
AdaSearch 相較於 NaiveSearch 的效能提升表明，自適應性方法確實比非自適應方法更具優勢。同樣令人驚訝甚至出乎意料的是，即使是 NaiveSearch，在處理此類問題時也往往能夠帶來優於 InfoMax 的表現。這意味著 InfoMax 中採用的滾動優化控制方法存在區域性貪婪性，並因此損害了其實際效能。相比之下，AdaSearch 則優雅地將自適應策略與全域性覆蓋保證加以結合。
AdaSearch 更具通用性
在放射源搜尋案例中大獲得成功的無人機載 AdaSearch 演示，不禁令我們想到這種新型演算法還能夠在哪些更為常規 / 通用的問題中帶來良好表現？事實證明，這種核心演算法擁有相當廣泛的適用範圍，甚至適用於多種非機器人體現型感測問題。
舉例來說，我們可以考慮在某一地區分佈的 100 家醫療診所中為 10 家規劃試點計劃的問題。我們可能需要立足診所的具體位置進行調查，從而評估哪裡才是某種特定罕見疾病發病率最高的區域或者各地區的具體發病率水平。這是一項具體型感測問題，因為診斷工作由醫師親自進行。很明顯，人力調查員的數量有限，而且同一組調查員的工作時間需求以及在各診所之間的往來成本都屬於客觀存在的物理限制。
調查工作的排程人員可以利用 AdaSearch 的指導意見整理各診所位置在計算該疾病新病例時的具體用時，外加由此前往其它診所的距離，從而權衡往來行程時長以確保調查人員能夠在單位時間之內收集到更多相關資料。
一般來講，當我們認為測量過程中的干擾因素足以保證演算法在資料收集過程中完成多輪區域探索時，AdaSearch 即可帶來良好的預期表現。無論是搜尋放射源頭還是調查罕見疾病的發病率，我們都可以將其建模為泊松分佈隨機變數，其中的方差會隨平均值變化而變化。AdaSearch 能夠輕鬆適應不同的噪聲模型（例如高斯模型），從而對接存在此類模型的多種不同應用場景。只要我們能夠計算或者框定出適當的置信區間邊界，AdaSearch 就能夠保證有效遍歷該區域以找到需要關注的目標點。
如果您希望瞭解關於 AdaSearch 的更多細節資訊，可通過以下連結獲取論文全文: https://arxiv.org/abs/1809.10611 。