如何找到距離最近的TA？
如果你想要開一家咖啡店，你或許會想問一個問題：附近最近的咖啡店在哪裡？這個問題的答案可以幫你了解競爭對手的情況。
這是計算機科學中廣泛研究的「最近鄰」搜索問題的一個例子。這個問題研究的是：在給定一個數據集合和一個新的數據點的情況下，在現有數據集合中，哪個點距離新的點最近？這個問題出現在很多日常情境中，例如基因組研究、圖像搜索、歌曲推薦等。
與咖啡店這個例子不同的是，最近鄰問題往往非常難解答。問題的複雜性主要在於，對於不同類型的數據集，兩點間距離的定義可能截然不同。
什麼是距離？
我們已經完全習慣的一種定義距離的方式，就是在兩點之間繪製直線，也就是我們通常所說的歐幾里德距離（Euclidean distance）。
然而，在有些情況下，其他定義距離的方式更為合理。例如，在街道縱橫如網格的大城市中，從一個地點到另一個地點的最短距離會是，橫著向東走3公里，然後向北走4公里，而不是飛躍所有房屋的直線距離5公里。這種強迫你轉90度彎的定義方式就是所謂的曼哈頓距離（Manhattan Distance）。
紅、藍、黃三個線分別都曼哈頓距離，且距離都一樣長（12），綠線則表示歐幾里得距離。| 圖片來源：Wikipedia
國際象棋的棋盤上，「王」從一個位置走到另一個位置需要的最少步數，被稱為切比雪夫距離（Chebyshev Distance），也叫棋盤距離。
國際象棋中，「王」每次可以向周圍八個方向走任意步數。棋盤格中的數字表示「王」所在位置（f6）與其餘位置的切比雪夫距離。| 圖片來源：Wikipedia
曼哈頓距離、歐幾里德距離與切比雪夫距離，分別對應於p-範數距離中的1-範數、2-範數、無窮範數。
除了從空間地理位置的角度來思考距離，還存在許多適用於其他特定類型問題的距離度量。比如說，社交網路上的兩個人、兩部電影、或者兩個基因組之間的距離是多少？在這些例子中，「距離」是指兩個事物有多大的相似度。
計算機科學中用「編輯距離」（Edit Distance）來量化比較兩個字元串（例如英文單詞）的差異程度。生物學家也常使用「編輯距離」，例如基因序列可被看作是A、T、C、G 四個字母組成的字元串，編輯距離可用來量化比較兩個基因組的相似度：兩個基因序列之間的編輯距離，就是將一個序列轉換成另一個序列過程中，所需的添加、刪除、插入和替換的數量。
基因序列可以看作是A、T、C、G 四個字母組成的字元串。| 圖片來源：Wikipedia
編輯距離和歐幾里德距離是關於距離的兩個完全不同的概念，其中一種定義無法被歸結為另一種。這種不可通約性出現在很多距離度量對中。這意味著適用於某種距離度量的演算法對另一種並不適用。這對試圖開發最近鄰演算法的計算機科學家是極大的挑戰。
尋找最近鄰
尋找最近鄰的標準方法，是將現有數據劃分成組。例如想像一下，你的數據是草地上綿羊的位置，將成群的綿羊圈起來，如果這時草地上來了一隻新綿羊，它會落入哪個圈呢？新來綿羊的最近鄰在很大概率上、甚至是必然的情況下，也會在那個圈裡。
然後重複這個過程，將這些圈再次劃分成更小的圈，不斷地對它們繼續進行劃分……最終，劃分的圈子將只包含兩個點：一個是原來就已存在的點，一個是新的點。而原來存在的點就是新點的最近鄰。
這些區域的劃分由演算法進行繪製，好的演算法能很好很快地完成劃分，「好」的意思是，不太可能出現新的綿羊落入一個圈、而它的最近鄰卻出現在另一個圈中的情況。通過劃分成組，我們希望距離近的點落入相同分區的概率高，而距離遠的點落入相同分區的概率很低。
最近鄰搜索的方法：不斷分割數據點的集合，最後添加新的點，那麼，新的點（紅點）及其最近鄰將極有可能落入同一個小分區。| 圖片來源：QuantaMagazine
多年來，計算機科學家已經提出了各種劃分區域的演算法。對於每個點僅由幾個值定義的低維數據（如草地上綿羊的位置），演算法會生成沃羅諾伊圖（Voronoi diagram）來精確地求解最近鄰問題。
沃羅諾伊圖（Voronoi diagram）：給定一系列點，平面上到任意一個給定點的距離小於到其他給定點距離的點的集合，組成一個沃羅諾伊原胞。每一個原胞為凸的多邊形，原胞邊界上的點到最近鄰兩個給定點的距離相等。圖中是分別根據歐幾里得距離（左）與曼哈頓距離（右）劃分的沃羅諾伊圖。| 圖片來源：Wikipedia
對於每個點可以由成百上千個值定義的更高維度的數據，沃羅諾伊圖的計算量過大。因此，計算機科學家轉而用一種被稱為「局部敏感散列」（locality sensitive hashing，LSH）的演算法來進行劃分。LSH演算法會隨機地進行劃分，因而它的運行速度更快，但卻不那麼準確。也就是說，它不會精確地找到一個點的最近鄰點，但能確保找到一個在實際最近鄰點一定距離範圍內的點。這就像是有的網站為你推薦的是「足夠好」、但並非「最好」的資源。
自二十世紀九十年代代末以來，計算機科學家就提出了對特定距離度量能夠近似求解最近鄰問題的LSH演算法。這些演算法往往非常具有針對性，為一種距離度量開發的演算法無法應用於另一種。對於特定的重要情形，存在非常高效針對歐幾里得距離、曼哈頓距離的演算法。然而，沒有一個對一大類距離度量都行之有效的演算法。
因此，計算機科學家只能採取迂迴戰術。他們通過一個名為「嵌入」（embedding）的過程，用沒有高效演算法的那種距離度量，覆蓋有高效演算法的距離度量。然而不同距離度量的拼接往往並不精確，頗有些牛頭不對馬嘴。在某些情況下，甚至連嵌入都根本不可能。我們真正需要的是一種解決最近鄰問題的普遍方法。
最近，五位計算機科學家組成的一個團隊提出了一種全新的方法來解決最近鄰問題。在相繼發表的兩篇論文中，他們闡述了解決複雜數據最近鄰問題的第一個通用方法。
論文的作者之一、麻省理工學院的計算機科學家、在開發最近鄰問題演算法方面很有影響力的人物Piotr Indyk說：「這是第一個使用單個演算法捕捉到多種空間度量的成果。」
擴展圖的阻礙
在這項新的工作中，計算機科學家不再追尋特定的最近鄰演算法，而是退後一步，思考一個更廣泛的問題：對於一個距離度量，是什麼因素阻止了最近鄰演算法的存在？
他們認為，這與尋找擴展圖（expander graph）的最近鄰問題有關，是一個非常困難的問題。擴展圖是一種特定類型的圖，它們由頂點和連接頂點的邊組成，具有自己的距離度量。圖上兩點間的距離，是從一點到另一點需要經過的邊的最小數目。例如，對於社交網路中表示人群連接關係的圖，人與人之間的距離是他們之間的分離程度，也就是說，如果X和Y之間通過兩個朋友A和B才能建立朋友關係X-A-B-Y，那麼X和Y的距離就是3。
擴展圖是一種特殊類型的圖，有著兩個看似矛盾的屬性：一方面，它連接良好，要想斷開這些點就必須切斷許多的邊；然而與此同時，大多數的點僅與極少的點連接。第二個特點導致大多數點最終彼此遠離，因為低的連接度意味著在大多數點之間，都需要經過漫長、曲折的路徑。
擴展圖的兩個特點：（1）擴展圖中由邊連接的兩個頂點是一對近鄰，大多數的點僅與極少的點連接。（2）擴展圖中連接良好，例如，圖中有許多路徑連接著A、B兩點，不切斷這許多邊就無法使它們分離。切斷點的連接意味著切斷邊，讓近鄰點分開。擴展圖的特點成為了點集分區的障礙，因此，對於擴展圖，最近鄰搜索演算法不可能實現。| 圖片來源：QuantaMagazine
將連接良好，與總體來說邊卻很少這兩個特點結合，會導致在擴展圖上無法進行快速的最近鄰搜索，因為在擴展圖上劃分點集的任何努力都可能導致近鄰點的分離。
這項工作的共同作者Waingarten說：「任何在擴展圖上切割點集的方式，都可能導致很多的邊被切斷，並使近鄰點被分離。」
擴展圖的阻礙
在2016年夏，Andoni，Nikolov，Razenshteyn和Waingarten四人就已經知道，擴展圖不可能有好的最近鄰演算法。然而，他們真正想要證明的是，對於許多其他的距離度量（那些計算機科學家一直試圖為之尋找好的演算法的度量），好的最近鄰演算法也是不可能的。
他們證明不可能有這種演算法的策略是，尋找一種方法，將擴展圖的距離度量嵌入其他類型的距離度量中。這樣他們就可以確認，那些其他的度量具有不可行的、與擴展圖類似的屬性。
普林斯頓大學的數學家和計算機科學家Assaf Naor之前的工作似乎非常適合解決擴展圖的問題，於是四位計算機科學家便請求Naor幫助證明擴展圖嵌入多種類型距離度量的問題。很快，Naor很快就帶來了答案，然而結果與四人期待的完全相反。
Naor證明，擴展圖無法嵌入被稱為「賦范空間」（normed space，包括歐幾里德距離、曼哈頓距離等距離度量）的一類大的距離度量。有了Naor的證明做基礎，他們循著邏輯鏈條：如果擴展圖無法嵌入距離度量，而與擴展圖類似的屬性是良好分區的唯一障礙，那麼，在賦范空間，良好的分區必然是有可能的。因而，良好的最近鄰演算法也必然是有可能的，即使計算機科學家還未能找到。
（1）數據集合。（2）將一個子集的幾個點連接。（紅色）（3）比較子集的圖與擴展圖的結構能夠幫助確定是否可以找到最近鄰點，如果新子集的圖與擴展圖結構相似，那麼良好的分區演算法將不可能存在。| 圖片來源：QuantaMagazine
五位研究人員將他們的結果相繼發表在兩篇論文里。在四月份發布的第一篇論文中，他們證明了存在一種方法可以將將點集一分為二，卻並沒有給出快速實現的方法。在這個月發布的第二篇論文中，他們利用第一篇論文的信息，找到了賦范空間的快速最近鄰演算法。
總的來說，新的論文首次重塑了對高維數據的最近鄰搜索。計算機科學家不再需要為每一個特定的距離度量設計一個演算法，現在，他們有了一個適合所有度量的最近鄰演算法。
編譯：烏鴉少年
參考鏈接：
https://www.quantamagazine.org/universal-method-to-sort-complex-information-found-20180813/
TAG:原理 |