c 如何理解局部敏感散列?




machine-learning hashmap (4)

我注意到LSH似乎是找到具有高維特性的相似項目的好方法。

閱讀完這篇文章http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf ,我仍然對這些公式感到困惑。

有沒有人知道一個博客或文章解釋簡單的方法?


我是一個視覺的人。 這是對我來說直覺的作用。

說你想搜索的東西大概是物理對象,如蘋果,立方體,椅子。

我對LSH的直覺是,它類似於拍攝這些物體的陰影。 就像如果你拍攝一個3D立方體的陰影,你會在一張紙上得到一個2D方形,或者一個3D球體將在一張紙上得到一個圓形的陰影。

最終,在搜索問題中有三個以上的維度(文本中的每個單詞都可能是一個維度),但shadow比喻對我來說仍然非常有用。

現在我們可以高效比較軟件中的比特串。 一個固定長度的比特串是或多或少的,就像一個維度中的一條線。

因此,對於LSH,我最終將單個固定長度線/位串上的點(0或1)投影到物體的陰影上。

整個訣竅就是把陰影留下來,使它們在較低的維度上仍然有意義,例如它們以足夠好的方式類似於原始物體,並且可以被識別。

透視立方體的2D圖形告訴我這是一個立方體。 但是我無法輕易區分2D立方體與3D立方體陰影,而無需透視:它們對我來說都像一個方形。

我如何向燈光呈現我的物體將決定我是否獲得了可識別的陰影。 所以我想到一個“好”的LSH,它可以將我的物體在光線之前轉動,這樣它們的影子就可以很好地被識別為代表我的物體。

所以要回顧一下:我認為要用LSH作為像立方體,桌子或椅子這樣的物理對象進行索引,並且我將它們的陰影投影到2D中,最後沿著一條線(一個比特串)投影。 而一個“良好”的L​​SH“功能”就是我如何在燈光前呈現我的物體,以便在二維平面和後來的比特串中獲得大致可區分的形狀。

最後,當我想搜索一個物體是否與我索引的某些物體相似時,我使用相同的方式將這個“查詢”物體的陰影呈現在燈光前面(最終以一點點結束字符串也是)。 現在我可以比較這個位串與我所有其他索引位串的相似程度,如果我找到了一個很好且可識別的方法來將我的對象呈現給我的光源,那麼它就是搜索我的整個對象的代理。


斯坦福大學的演講解釋了這一點。 這對我來說有很大的不同。 第二部分更多的是關於LSH,但第一部分也涵蓋了它。

概述圖片(幻燈片中有更多內容):

高維數據中的近鄰搜索 - 第1部分: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf : http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

高維數據中的近鄰搜索 - 第2部分: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf : http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf


我在LSH看到的最好的教程在書中:海量數據集的挖掘。 檢查第3章 - 查找類似項目http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

另外我建議下面的幻燈片: http : //www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf 。 幻燈片中的示例有助於我理解餘弦相似性的哈希算法。

我從ACL2010的Benjamin Van Durme和Ashwin Lall那裡借了兩張幻燈片並試圖解釋LSH家庭對余弦距離的直覺。

  • 在圖中,有兩個帶紅色黃色的圓圈,代表兩個二維數據點。 我們試圖用LSH找到它們的餘弦相似性
  • 灰線是一些隨機挑選的飛機。
  • 根據數據點位於灰線之上還是之下,我們將此關係標記為0/1。
  • 在左上角有兩排白色/黑色正方形,分別表示兩個數據點的簽名。 每個正方形對應於位0(白色)或1(黑色)。
  • 所以一旦你有一個飛機池,你可以編碼數據點與他們的位置各自的飛機。 想像一下,當我們在池中有更多的平面時,簽名中編碼的角度差異更接近實際差異。 因為只有位於兩點之間的平面會給兩個數據不同的位值。

  • 現在我們看看兩個數據點的簽名。 正如在這個例子中,我們只用6位(方塊)來表示每個數據。 這是我們擁有的原始數據的LSH哈希值。
  • 兩個散列值之間的漢明距離為1,因為它們的簽名僅相差1位。
  • 考慮到簽名的長度,我們可以計算它們的角度相似性,如圖所示。

我有一些示例代碼(只有50行)在Python中使用餘弦相似性。 https://gist.github.com/94a3d425009be0f94751






locality-sensitive-hash