利用K-Means LSH 加速求解格中的最短向量問題

金悅祺, 胡紅鋼

中國科學(xué)院 電磁空間信息重點(diǎn)實(shí)驗(yàn)室, 合肥230027

1 問題介紹

1.1 格密碼

隨著量子計(jì)算的深入研究, 越來越多的高性能量子算法被提出, 這使得某些傳統(tǒng)的密碼體系在未來的量子手段下不堪一擊. 比如著名的Shor 算法就能夠在多項(xiàng)式時(shí)間分解大整數(shù), 從而攻破目前廣泛應(yīng)用的RSA 公鑰體系. 基于格的密碼體系具有對抗量子計(jì)算攻擊的能力, 因此在近些年受到人們的廣泛關(guān)注. 眾所周知, 許多密碼體系都是基于困難問題建立的. 在格中, 最短向量問題(shortest vector problem, SVP)就是一個(gè)很著名的NP-Hard 問題[1], 因此對它的研究至關(guān)重要.

1.2 尋找短向量

至今為止, 在尋找短向量方面已經(jīng)有了很多種方法. 例如枚舉[2,3],(啟發(fā)式)篩法[4–6], 以及Micciancio 提出的構(gòu)造Voronoi 網(wǎng)格法[7], 還有2014 年提出的基于高斯采樣的方法[8]等等. 枚舉法從字面意思理解就可以看出它具有很高的時(shí)間復(fù)雜度(2Θ(nlog(n))), 但是其空間復(fù)雜度很低(poly(n)). 篩法通常基于啟發(fā)式假設(shè), 具有相對較低的時(shí)間復(fù)雜度(2Θ(n)), 較高的空間復(fù)雜度(2Θ(n)), 以及較大的常數(shù)因子. 從理論上來講, 在漸進(jìn)意義下, 啟發(fā)式篩法應(yīng)該在時(shí)間上優(yōu)于枚舉法, 但是在目前的實(shí)踐中, 相比于應(yīng)用了高效剪枝的枚舉, 篩法仍然要慢一些[9].

1.3 篩法

2008 年, Nguyen 與Vidick 提出了第一個(gè)啟發(fā)式篩法(NV-Sieve)[5], 這是在SVP 問題中第一次引入啟發(fā)式假設(shè)的解法. 雖然其效果不佳, 原始版本僅能解決不到50 維的SVP 問題, 但是它為解決SVP問題提供了一個(gè)新的思路. 2010 年, Micciancio 提出了一種新的篩法(GaussSieve)[6], 從實(shí)踐角度來講,它的表現(xiàn)非常出色, 以至于后續(xù)許多人的優(yōu)化版本都是以該方法為基礎(chǔ)的[10–14].

1.4 位置敏感哈希LSH

位置敏感哈希(locality-sensitive hashing,LSH)是在解決近鄰搜索問題(nearest neighbor searching,NNS)[9]中提出的. 它的思路是保留敏感信息, 模糊其余信息, 使得具有相同敏感信息的向量獲得同樣的哈希值. 這里的敏感信息可以理解為距離、角度等等. 在搜索近鄰的時(shí)候, 只需要搜索與目標(biāo)向量具有相同哈希值的向量即可. 通過計(jì)算哈希值, 降低搜索成本, 這個(gè)思路在篩法中也是可以應(yīng)用的.

1.5 篩法與LSH

2015 年, Laarhoven 提出了對于篩法的一種優(yōu)化[15], 其中第一次引入了LSH. 在篩法中引入LSH,效果是顯著的, 但是最初的Spherical LSH 似乎并不適用于GaussSieve, 只能用于NV-Sieve, 所以其實(shí)用性并不高. 后續(xù)他又使用Angular LSH[16]、Cross-Polytope LSH[17]來加速GaussSieve, 得到了更好的效果.

1.6 我們的結(jié)果

在本文中, 我們將K-Means LSH 引入GaussSieve, 對其進(jìn)行了優(yōu)化, 提高了其效率. 額外引入一個(gè)可調(diào)整的參數(shù), 我們提高了其使用的靈活性.

2 預(yù)備知識(shí)

2.1 格

這里先介紹一下格的基礎(chǔ)知識(shí). 所謂格, 一句話描述, 就是Rn下離散的加法子群. 但是通常來說, 我們研究的是Zn下的加法子群, 也就是由整點(diǎn)構(gòu)成的格. 我們定義L = L(B) 是由格基B ={b1,b2,··· ,bn} 生成的格, 即L(B) = {Bx|x ∈Zn}. 定義格的體積vol(L(B)) = det(B), 最短非零向量λ1(B)=λ1(L(B)).

2.2 近鄰搜索問題

近鄰搜索問題NNS 定義為: 給定向量集合L, 給定一個(gè)目標(biāo)向量v /∈L, 希望找到向量v0∈L 滿足d(v,v0) 最小. 如果在低維度的情況下, 向量集合L 的大小為N, 那么通過數(shù)據(jù)結(jié)構(gòu)的優(yōu)化與預(yù)處理, 可以在O(log(N)) 時(shí)間內(nèi)進(jìn)行查詢. 但是放到高維空間, 隨著維數(shù)n 增大, 似乎暴力搜索變成了復(fù)雜度最低的方法, 這個(gè)就是著名的“維數(shù)災(zāi)難(curse of dimensionality)” 現(xiàn)象[9].

為了解決這個(gè)問題, 我們希望將L 轉(zhuǎn)化為哈希桶的結(jié)構(gòu), 使得對于特定的一個(gè)桶中的所有向量vi滿足d(vi,v) <= r1, 而對于其余桶中的所有向量vi滿足d(vi,v) >= (1+?)r1, 這樣我們就可以只遍歷一個(gè)桶中的向量從而得到結(jié)果. 這個(gè)方法看上去很完美, 但是它只是理想情況下的方法. 實(shí)際上, 人們通常是使用LSH 得到近似結(jié)果.

2.3 LSH

一個(gè)LSH 是一個(gè)函數(shù)族, 類似于傳統(tǒng)的hash 函數(shù), 它也是將定義域中的向量映射為一個(gè)散列值. 不同于傳統(tǒng)的hash 函數(shù)的地方在于, LSH 會(huì)把相似的向量映射為同一個(gè)散列值, 而把不相似的向量映射為不同的散列值. 不妨設(shè)函數(shù)D 是衡量向量相似程度的函數(shù), 那么我們有下面的定義:

定義1[9]一個(gè)函數(shù)族H = h:Rn→U 定義為在相似函數(shù)D 下具有(r1,r2,p1,p2)-敏感的LSH,如果它滿足對于任意的v,w ∈Rn, 下面兩式成立:

(1) 如果D(v,w)≤r1, 那么Ph∈H[h(v)=h(w)]≥p1.

(2) 如果D(v,w)≥r2, 那么Ph∈H[h(v)=h(w)]≤p2.

根據(jù)定義我們也可以看出來, 為了明顯地區(qū)別v 和w, 我們希望p1?p2. 然而如果r1和r2比較接近, 那么我們很難滿足上面的需求. 因此可以考慮使用多個(gè)函數(shù)進(jìn)行比較, 這也是LSH 是一族函數(shù)而非一個(gè)函數(shù)的用意. 為了放大p1與p2的差距, 下面兩個(gè)操作是至關(guān)重要的[9].

AND. k 個(gè)不同的哈希函數(shù)h1,h2,··· ,hk的AND 操作定義為一個(gè)函數(shù)h′:Rn→Uk, 其中h′(v)的第j 維坐標(biāo)即為hj(v), 我們定義h′(v)=h′(u) 當(dāng)且僅當(dāng)對于任意i ∈{1,2,··· ,k} 有hi(v)=hi(u).這樣任取k 個(gè)哈希函數(shù)就構(gòu)成了一個(gè)新的LSH, 它是(d1,d2,pk1,pk2) 敏感的.

OR. t 個(gè)不同的哈希函數(shù)h1,h2,··· ,ht的OR 操作定義為一個(gè)函數(shù)h′: Rn→Ut, 其中h′(v) 的第j 維坐標(biāo)即為hj(v), 我們定義h′(v) = h′(u) 當(dāng)且僅當(dāng)存在某個(gè)i ∈{1,2,··· ,t} 有hi(v) = hi(u).這樣任取t 個(gè)哈希函數(shù)就構(gòu)成了一個(gè)新的LSH, 它是(d1,d2,1 ?(1 ?p1)t,1 ?(1 ?p2)t) 敏感的.

在LSH 中任意選取kt 個(gè)不同的函數(shù),通過AND 和OR 操作,就能得到一族(d1,d2,1?(1?pk1)t,1?(1 ?pk2)t) 敏感的LSH, 注意到如果p1>p2, 那么就有1 ?(1 ?pk1)t>>1 ?(1 ?pk2)t, 這就得到了我們想要的LSH. 對于k 和t 的選取, 我們有下面的定理:

定理1[9]對于一個(gè)(r1,r2,p1,p2) 敏感的LSH 函數(shù)族H, 以及一個(gè)大小為N 的向量集合L, 令

對于給定的向量v, 下面兩條結(jié)論很有可能至少有一條會(huì)滿足:

(a) 能夠找到向量w ∈L 滿足D(v,w)≤r2;

(b) 不存在向量w ∈L 滿足D(v,w)>r1.

其復(fù)雜度為:

(1) 對于列表L 的預(yù)處理時(shí)間: ?O(kN(1+ρ));

(2) 預(yù)處理之后列表的空間復(fù)雜度: ?O(N(1+ρ));

(3) 對于給定v 的一次查詢: ?O(Nρ).

2.4 K-Means LSH

本文中主要依賴的LSH 是K-Means LSH, 其中的K-Means 最早是機(jī)器學(xué)習(xí)中的最常用的聚類算法[18], 之后Lo?c Paulevé 等人根據(jù)該想法設(shè)計(jì)了K-Means LSH[19]. 對于固定的一個(gè)K 值, 一個(gè)KMeans LSH 函數(shù)族H 中的每個(gè)函數(shù)h 可以描述為:

選取K 個(gè)不同的向量構(gòu)成集合C ={ci|i=1,2,··· ,K}

點(diǎn)集C 通常稱作中心點(diǎn)集. 那么通過構(gòu)造不同的C 就可以得到哈希函數(shù)族H. 其具體的敏感度與點(diǎn)集C 的選取有關(guān). 在機(jī)器學(xué)習(xí)中, 中心點(diǎn)集一般是通過隨機(jī)選取數(shù)據(jù)集中的點(diǎn), 然后進(jìn)行迭代的方式得到的, 例如著名的SIFT 算法[20]. 在這里, 我們啟發(fā)式地假設(shè)格點(diǎn)在空間中分布是均勻的, 因此我們只需要使C 中的點(diǎn)的分布盡可能均勻即可. 下面是啟發(fā)式假設(shè):

假設(shè)1 在格中均勻隨機(jī)取兩個(gè)向量v 和w, 其角度Θ(v,w) 與在單位球中均勻隨機(jī)選取v 和w 得到的角度分布相同.

通俗地理解, 啟發(fā)式假設(shè)意思是說Rn中的格點(diǎn)分布可以看做是均勻的. 然而, 這個(gè)均勻的意思與二三維空間并不一樣. 事實(shí)上, 在高維空間中, 隨機(jī)取兩個(gè)點(diǎn)v 和w, 那么他們的角度Θ(v,w) 很有可能非常接近π/2, 而并不是通俗理解的[0,π] 中的均勻隨機(jī)值. 隨著維度的增高, 這個(gè)趨勢會(huì)越發(fā)明顯.

2.5 GaussSieve

2010 年, Micciancio 等人提出了一種新的篩法[6], 其思路類似于Gauss 在約簡二維格基時(shí)采用的方法, 因此命名為GaussSieve. 該算法偽代碼見算法1.

算法1 GaussSieve(B) [6]Input: 經(jīng)過LLL 約簡的格基B Output: 格中的短向量v 1 Function GaussSieve(B,μ):18 Function GaussReduce(v,L,S):2 Initialize L = {0},S = {},K = 0;3 while K ≤c do 19 while ?vi ∈L :20 ∥vi∥≤∥v∥∧∥v ?vi∥≤∥v∥do 4 if S ?= ?then 5 vnew = S.pop();6 else 7 vnew = SampleGaussian();21 v = v ?vi;22 end 23 while ?vi ∈L :24 ∥vi∥≥∥v∥∧∥vi ?v∥≤∥vi∥do 8 end vnew = GaussReduce(vnew,L,S);10 if vnew = 0 then 9 11 K = K +1;12 else 25 L = L{vi};26 S.push(vi ?v);27 end 28 Return v;29 End Function 13 L = L ∪{vnew};14 end 15 end 16 Return L 中最短向量;17 End Function

該算法的主要空間復(fù)雜度是棧S 和列表L 的大小, 主要空間復(fù)雜度是從L 中查找能約化向量的時(shí)間. 因此, 從減小時(shí)間復(fù)雜度的角度來考慮, 利用LSH 來加快查找速度是一個(gè)不錯(cuò)的想法.

對于兩個(gè)向量u 和v, 如果∥u ?v∥≤∥u∥或者∥u ?v∥≤∥v∥, 那么顯然有Θ(u,v)≤π/3, 反之則有Θ(u,v) > π/3. 看上去似乎不好區(qū)分兩種情況, 但是事實(shí)上, 在高維空間中, 能夠約化的向量對大概率滿足Θ(u,v) = π/3, 不能約化的向量對大概率滿足Θ(u,v) = π/2. 我們曾經(jīng)做過一個(gè)實(shí)驗(yàn), 對于50 維的空間, 隨機(jī)選取向量對u 和v, 那么Θ(u,v) 有超過99% 的幾率落在區(qū)間[85°, 95°] 中. 所以我們只需要選取形如(π/3,π/2,p1,p2) 的LSH 即可. 即我們考慮用

來代替

進(jìn)行判定.

在上面的討論中, 對于我們選取的參數(shù)為(π/3,π/2,p1,p2) 的LSH, 我們實(shí)際上只需要關(guān)心它的參數(shù)r1= π/3. 對于第二個(gè)參數(shù)r2= π/2, 實(shí)際上只是表明該LSH 能夠區(qū)分夾角小于r1= π/3 與夾角接近r2= π/2 的向量對. 嚴(yán)格來說, 可以改寫參數(shù)為r2= π/2 ?δ 使我們的表述更加嚴(yán)謹(jǐn), 其中δ << r2為一個(gè)常數(shù). 對應(yīng)的, p2也會(huì)增加一個(gè)可以忽略的常數(shù), 這是因?yàn)楦呔S空間中隨機(jī)選取的向量對幾乎都具有接近0 的內(nèi)積, 即夾角會(huì)大于r2= π/2 ?δ. 這些向量對是不能約化的, 因此利用具有r1= π/3 參數(shù)的LSH 能夠幫助我們篩選出能夠約化的向量對, 從而達(dá)到加速算法的目的.

3 應(yīng)用LSH 的GaussSieve

3.1 算法描述

結(jié)合上面介紹的內(nèi)容, 很自然的考慮用Θ(u,v) 來估算是否可以對u 和v 進(jìn)行約簡, 引入LSH 來估算Θ(u,v) 的大小. 于是考慮用一組哈希桶Ti代替GaussSieve 中的列表L, 用同一個(gè)哈希桶中的搜索取代原算法中對列表L 進(jìn)行蠻力搜索的步驟, 得到算法2[16].

算法2 GaussSieve-with-LSH(B) [16]Input: 經(jīng)過LLL 約簡的格基B Output: 格中的短向量v 1 Function GaussSieve-with-LSH(B,μ):21 Function GaussReduce-with-LSH(v,L,S):2 Initialize L = {0},S = {},K = 0;3 Initialize k ?t random hash functions hi,j ∈H;4 Initialize t empty hash tables Ti;5 while K ≤c do 22 C = ∪t i=1 Ti[hi(v)];23 while ?vi ∈C :24 ∥vi∥≤∥v∥∧∥v ?vi∥≤∥v∥do 6 if S ?= ?then 7 vnew = S.pop();8 else 25 v = v ?vi;26 end 27 while ?vi ∈C :28 ∥vi∥≥∥v∥∧∥vi ?v∥≤∥vi∥do vnew = SampleGaussian();10 end 11 vnew=GaussReduce?with?LSH(vnew,L,S);12 if vnew = 0 then 9 13 K = K +1;14 else 29 L = L{vi};30 Delete v from all hash tables;31 S.push(vi ?v);32 end 33 Return v;34 End Function 15 L = L ∪{vnew};16 Insert v to all hash tables Ti;17 end 18 end 19 Return L 中最短向量;20 End Function

其實(shí)相比于以往的此類算法, 他們的框架(算法2) 都是相同的, 區(qū)別只在于LSH 的具體形式.

3.2 K-Means LSH

根據(jù)2.4 節(jié)中介紹的內(nèi)容明顯能看出來, 我們希望中心點(diǎn)集的分布盡可能均勻, 例如K =2n 的時(shí)候,取中心點(diǎn)集為C = {±ei} 或其一個(gè)旋轉(zhuǎn). 但是事實(shí)上, 對于高維空間, 這是一個(gè)名叫Tammes 的困難問題[21], 考慮到我們求解的格至少有50 維, 在這樣的維度下求解Tammes 問題并不可行. 那么我們退而求其次, 我們隨機(jī)選取K 個(gè)點(diǎn)組成中心點(diǎn)集C, 對于某個(gè)固定的角度α, 下式成立

上式通俗的理解就是希望C 中的點(diǎn)盡量相互遠(yuǎn)離. 為此, 我們設(shè)計(jì)了一個(gè)很簡單的算法可以實(shí)現(xiàn)這個(gè)目標(biāo), 即算法3.

算法3 很簡單, 而且作為篩法的預(yù)處理步驟, 我們并不需要過多的關(guān)注它的復(fù)雜度, 這一切似乎都很完美. 然而事實(shí)上, 如果假設(shè)α = π/2, 明顯最優(yōu)解是|C| = 2n, 但是如果使用算法3, 甚至連n 個(gè)點(diǎn)都很難取出來. 萬幸的是, 雖然對于任意維度, 在α = π/2 下的最優(yōu)解都是|C| = 2n, 但是隨著α 的減小, 例如α = 80?,70?, 那么通過算法3 得到的|C| 與維度n 至少是指數(shù)級的關(guān)系, 這個(gè)在文獻(xiàn)[12] 中有詳細(xì)的描述. 特別的, 我們?nèi)绻ˇ?π/3, 在n=10 的情況下, 利用算法3 得到的|C|≥104. 對于α=π/3 的情況, 文獻(xiàn)[5] 的結(jié)論告訴我們至多存在20.2075n個(gè)兩兩夾角大于α 的向量, 而在實(shí)際使用中, 我們只需要取K = kn 個(gè)中心點(diǎn)集. 因此, 在本文的主要算法中, 使用這個(gè)簡單的取樣算法是合理的. 得到中心點(diǎn)集后, 就可以根據(jù)(1)式計(jì)算出hash 值以完成算法2.

算法3 Central point set sampling Input: 最小角度α Output: 中心點(diǎn)集C 1 Const 最大碰撞次數(shù)m;2 Initialize C = {}, 當(dāng)前碰撞次數(shù)k = 0;3 while k ≤m do k = k+1;7 else 4 p = Simple_on_Unitsphere();5 if ?p0 ∈C : Θ(p,p0) ≤α then 6 8 Insert p into C;k = 0;10 end 11 end 12 Return C;9

3.3 與CP-Sieve 對比

先回憶一下CP-Sieve 中使用的Cross-Polytope LSH[22], 其哈希函數(shù)為

其正負(fù)號(hào)等于絕對值最大坐標(biāo)的符號(hào). 然后將這個(gè)哈希函數(shù)拓展為一族哈希函數(shù)

其中A 是滿足每一個(gè)元素ai,j～N[0,1] 的矩陣, N[0,1] 表示[0,1] 上的正態(tài)分布. 現(xiàn)在讓我們從幾何的角度理解一下這一族函數(shù): 顯然h 的取值跟v 的模長無關(guān), 所以不妨將其看成是單位球面上的哈希函數(shù),A 可以看做是旋轉(zhuǎn)矩陣. 因此其幾何含義便是找到C = {±ei} 中距離目標(biāo)v 最近的點(diǎn), 其函數(shù)族即為對C 進(jìn)行了旋轉(zhuǎn)A?1.

因此我們可以看出, Cross-Polytope LSH 是K-Means LSH 在α = π/2 時(shí)的最優(yōu)解, 可以看做是K-Means LSH 的一種特殊情況. 相比于Cross-Polytope LSH, K-Means LSH 可以通過更大的C 以及更小的α 來提高其精確度.

對于Cross-Polytope LSH, 文獻(xiàn)[23] 中給出了其單次的精確程度, 如下引理

引理1 記H 為Cross-Polytope LSH 函數(shù)族, 記θ =Θ(u,v) 為兩個(gè)向量u 和v 的夾角, 那么對于較大的n, 有下式成立

雖然這個(gè)引理看上去結(jié)果很漂亮, 但是事實(shí)上, 在我們的應(yīng)用范圍內(nèi), 即維數(shù)n 相對比較小的時(shí)候,O(log log n) 對于性能的影響是相當(dāng)大的. 例如在n=50 的時(shí)候, CP-LSH 的實(shí)驗(yàn)結(jié)果顯示其p1≈3.5%,p2≈1%, 這與引理1 去掉O(log log n) 的結(jié)果相去甚遠(yuǎn). 在實(shí)踐中, K-Means LSH 的表現(xiàn)相對優(yōu)秀一些,針對這方面的對比, 我們會(huì)在后面進(jìn)行展示.

從計(jì)算hash 值的復(fù)雜性上對比, CP-LSH 的計(jì)算過程是旋轉(zhuǎn)O(n2) 與尋找最大坐標(biāo)O(n), 通過尋找特殊形式的旋轉(zhuǎn)矩陣A, 可以將旋轉(zhuǎn)的復(fù)雜度降為O(n log n). K-Means LSH 的計(jì)算過程是計(jì)算K 個(gè)內(nèi)積O(Kn) 與尋找最大值O(K), 考慮到K 的大小一般正比于n, 因此其復(fù)雜度也是O(n2), 這與未經(jīng)優(yōu)化的CP-LSH 復(fù)雜度相同. K-Means LSH 在復(fù)雜度上還有優(yōu)化空間, 這是一個(gè)開放性問題.

另外, Thijs Laarhoven 提出了一種步進(jìn)式的優(yōu)化[14], 能夠提高框架(算法2) 的性能, 也可以對本算法進(jìn)一步優(yōu)化.

4 實(shí)驗(yàn)結(jié)果

本文中提到的K-Means-LSH 與機(jī)器學(xué)習(xí)中聚類分析使用的同名LSH 并不完全相同, 這是因?yàn)榫垲惙治鲋惺歉鶕?jù)已有的固定的樣本點(diǎn)通過迭代的方式生成中心點(diǎn)集, 而本文針對的是球面上均勻分布的點(diǎn)確定中心點(diǎn)集, 相比前者, 該方法更像對球面的均分, 這與文獻(xiàn)中提到的Angular-LSH 和CP-LSH 的目的是一樣的. 為了觀察K-Means-LSH 能否適應(yīng)這個(gè)目的, 本節(jié)中前兩小節(jié)先對該LSH 進(jìn)行一些實(shí)驗(yàn)測試.

4.1 不同K 值對應(yīng)LSH 的性能對比

本節(jié)中, 我們觀察不同K 值對于LSH 性能的影響, 從而在后面的分析中選擇更合適的LSH. 在這里, 我們只考慮單個(gè)LSH 的結(jié)果. 對于單個(gè)LSH 而不是LSH 函數(shù)族, CP-LSH 的復(fù)雜度是O(n), 因?yàn)椴恍枰M(jìn)行旋轉(zhuǎn), 從均勻取樣的角度來看, 只需要尋找最大的坐標(biāo)分量即可, 然而K-Means-LSH 的復(fù)雜度是O(Kn). 受限于計(jì)算能力, 我們只在中維度(n ∈[30,70]) 進(jìn)行觀察. 為了結(jié)果的準(zhǔn)確性, 我們?nèi)×藃2=85°. 結(jié)果如圖1.

由于該LSH 的具體性能受中心點(diǎn)集位置的影響, 而均勻布點(diǎn)又是困難問題, 所以這里只能通過多次試驗(yàn)給出數(shù)值模擬, 具體的理論值有待研究.

圖1 記錄了該實(shí)驗(yàn)的結(jié)果. 看起來似乎違背了我們的直覺, 隨著K 的增大, 參數(shù)p1有明顯的的下降趨勢. 事實(shí)上, 回到定義, 實(shí)驗(yàn)中的p1表示的是下式的值:

那么我們考慮哈希值不同且夾角小于π/3 的向量對, 這樣的向量對會(huì)出現(xiàn)在兩個(gè)中心點(diǎn)“控制范圍” 的邊界附近一定范圍內(nèi)(中心點(diǎn)p 控制范圍指的是集合{u : Θ(u,p) ≤minp′?=pΘ(u,p′)}, 其邊界附近的一定區(qū)域可以用集合?p= {u : minp′?=pΘ(u,p′)?δp≤Θ(u,p) ≤minp′?=pΘ(u,p′)} 來表示, 其中δp是常數(shù)). 隨著K 的增大, 這些區(qū)域的并集∪p?p會(huì)具有更大的面積, 從而導(dǎo)致p1的下降.

4.2 K-Means-LSH 與CP-LSH 的性能對比

本節(jié)中, 我們來對比兩種不同的LSH 在不同維度下的p1與p2值, 以此反映兩種LSH 的性能. 考慮到實(shí)際應(yīng)用, 我們?nèi)∷惴? 中的α=π/3, 結(jié)果如圖2(a).

從實(shí)踐結(jié)果上來看, K-Means LSH 的效果要明顯優(yōu)于CP-LSH. 當(dāng)K = N 時(shí), 值p1與p1/p2都是K-Means-LSH 更優(yōu). 當(dāng)K = 2N 時(shí), 兩種LSH 具有相似的p2值, 這很好理解, 因?yàn)镃P-LSH 就是均勻情況下的K-Means-LSH. 然而, K-Means-LSH 的p1值遠(yuǎn)大于CP-LSH. 這種情況隨著維數(shù)的增加表現(xiàn)的更明顯, 因?yàn)樵诟呔S, 隨機(jī)取兩個(gè)向量, 它們之間的夾角有很大概率接近π/2, 在這種情況下, 由于中心點(diǎn)集的不均勻會(huì)造成某些局部中心點(diǎn)比較密集, 這個(gè)子中心點(diǎn)集能夠過濾接近但是小于π/2 的點(diǎn)對, 從而提高p1值. 隨著K 的增大, K-Means-LSH 的p1會(huì)降低, p2也會(huì)略微降低, 但是p1/p2會(huì)升高(如圖2(b)).

4.3 K-Means Sieve 性能測試

本節(jié)中, 我們將對使用了K-Means-LSH 的GaussSieve 進(jìn)行測試. 本算法涉及三個(gè)參數(shù): AND 操作次數(shù)k、OR 操作次數(shù)t、中心點(diǎn)集大小K. 根據(jù)定理1 與文獻(xiàn)[17], 考慮到兩種LSH 的參數(shù)p1與p1/p2對比, 我們?nèi) = 30, 對不同的K, 在維度[35,70] 之間測試其漸進(jìn)復(fù)雜度. 在這里, 為了排除計(jì)算機(jī)性能對于算法的干擾, 我們先同文獻(xiàn)[17] 一樣, 考慮Operations 參數(shù)(這里Operations = Comparisons +Hashes, 第一項(xiàng)表示比較兩個(gè)向量能否約減的次數(shù), 第二項(xiàng)表示計(jì)算hash 值的次數(shù)). 測試結(jié)果如圖3(圖中的小數(shù)表示直線的斜率):

從圖3 可以看出, 我們的算法在具體復(fù)雜度的數(shù)值上略低于CP-Sieve, 這是因?yàn)镃P-LSH 在計(jì)算量上相當(dāng)于K = N 的K-Means LSH, 但是由于中心點(diǎn)集分布不均勻, 在K = N 的時(shí)候效率比CPSieve 差. 但是從漸進(jìn)復(fù)雜度的角度來看, 我們的算法是有優(yōu)勢的, 隨著K 的增加, 漸進(jìn)復(fù)雜度是優(yōu)于CP-Sieve 并且還有下降空間的. 更重要的是, 上面采用Operations 作為比較參數(shù)其實(shí)并不是很合適, 因?yàn)橛?jì)算一次Comparison 需要進(jìn)行O(n) 次運(yùn)算(加法與乘法), 而計(jì)算一次hash 需要進(jìn)行O(n2) 次運(yùn)算(CP-LSH 需要計(jì)算一次旋轉(zhuǎn), K-Means LSH 需要計(jì)算K = kn 次內(nèi)積), 因此這里我們考慮使用參數(shù)Complexity=Comparisons+Hashes2來衡量其復(fù)雜度, 測試結(jié)果如圖4(圖中的小數(shù)表示直線的斜率):

從圖4 中可以看出, 在Complexity 參數(shù)下, 無論是在漸進(jìn)復(fù)雜度意義下還是具體數(shù)值下, 我們的算法都是有優(yōu)勢的.

綜合來看, 我們的算法相比于現(xiàn)有的CP-Sieve 是有優(yōu)勢的, 不僅僅是因?yàn)閺?fù)雜度上的優(yōu)勢, 更因?yàn)槲覀兊乃惴ǘ嘁粋€(gè)參數(shù)K, 使得在實(shí)際應(yīng)用中有更大的選擇空間, 對于較低維度的空間, 可以不考慮漸進(jìn)復(fù)雜度以獲得更優(yōu)的時(shí)間性能, 而對于高維空間, 可以通過增大K 以獲得更好的Operation 意義下的漸進(jìn)復(fù)雜度(這點(diǎn)從圖中能看出, 對于固定的k, 增大參數(shù)K 的值能明顯優(yōu)化其漸進(jìn)復(fù)雜度).

由于Tammes 問題的復(fù)雜性, 對于高維空間, 我們甚至無法對均勻布點(diǎn)的個(gè)數(shù)進(jìn)行估計(jì), 從算法3 測試的結(jié)果來看, 它至少是指數(shù)級別的. 從實(shí)驗(yàn)結(jié)果上來看, 對于略高維度的空間, 增大K 的效果是明顯的,這就說明中心點(diǎn)集與維度n 之間的關(guān)系在最優(yōu)情況下很可能不是線性的. 因此, 中心點(diǎn)集的大小或許可以進(jìn)一步優(yōu)化. 除此之外, 它還有兩個(gè)很大的優(yōu)化空間: 一是能否通過選取特定形式而又不失均勻性的中心點(diǎn)集, 以達(dá)到降低計(jì)算hash 值復(fù)雜度的目的; 二是優(yōu)化中心點(diǎn)集的均勻性, 以提高其性能.

總的來說, CP-Sieve 可以看做是本方法的特殊情況. 受限于Tammes 問題, K-Means Sieve 的潛力并沒有被完全地挖掘出來. 考慮到K-Means LSH 性能優(yōu)秀, 我們完全有理由相信, 當(dāng)中心點(diǎn)集足夠均勻的情況下, K-Means Sieve 會(huì)有更好的結(jié)果.