【導(dǎo)讀】盡我所知，除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外，論文中不。教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任。何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意。申請學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切相關(guān)責(zé)任。研究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬北京郵電大學(xué)。復(fù)制手段保存、匯編學(xué)位論文。

　　

【正文】 h 值，仍相似，此外， LSH 對這種相似性進(jìn)行建模， 給出 了一定的概率保證，此外， LSH之所以廣泛應(yīng)用，是因?yàn)樵跈z索規(guī)模以及數(shù)據(jù)維度不斷增長的條件下，仍能具有線性的檢索速度的特性【 1】 。 【 Indyk P,Motwani nearest neighbortowards removing the curse of dimesionality】 LSH 的基本思想是， 選擇 超平面對數(shù)據(jù)進(jìn)行映射，原始數(shù)據(jù)空間中相鄰的數(shù)據(jù)點(diǎn)，通過 Hash 函數(shù)變換后，在新空間中 具有 相同值的概率很大，相反，不相鄰的數(shù)據(jù)點(diǎn)在新空間中具有相同值的概率很小。也就是說， LSH目標(biāo)是找到一組映射函數(shù)，映射前后點(diǎn)的相似性不變。同時(shí) LSH 也保留的其他 Hash 的一些特征，原始圖片集合經(jīng)映射后， 分散于 整個(gè) hash 表中，命中同一 Hash 值的數(shù)據(jù)就有很大概率在原空間相近?？梢哉f，通過 LSH 我們將原檢索候選集分成了多個(gè)子集合，而每個(gè)子集合中的數(shù)據(jù)是相似的，轉(zhuǎn)換成近似檢索問題，減少計(jì) 算量， 提高 檢索速度。 LSH 函數(shù)的設(shè)計(jì)需要滿足 LSH 特性， 即 ： 1）如果 d(x,y) ≤ d1， 則 h(x) = h(y)的概率至少為 p1； 2）如果 d(x,y) ≥ d2， 則 h(x) = h(y)的概率至多為 p2； 其中 d(x,y)表示 x 和 y 之間的距離， d1 d2， h(x)和 h(y)分別表示對 x和 y 進(jìn)行 hash 變換。通常來說， 這 些 LSH 函數(shù)是由人工設(shè)計(jì)出來， LSH 構(gòu)建 Hash函數(shù)的過程是獨(dú)立于數(shù)據(jù)分布的， 使用 中需要對數(shù)據(jù)有較深的理解才能設(shè)計(jì)出來。 在很多應(yīng)用領(lǐng)域中，我們面對和需要處理的數(shù)據(jù)往往是海量并且具有很高的 維度，怎樣快速地從海量的高維數(shù)據(jù)集合中找到與某個(gè)數(shù)據(jù)高度相似的點(diǎn)有了很多的需求。在這些高度相似檢索領(lǐng)域中， LSH均得到很大程度的發(fā)展，可以說凡是需要進(jìn)行大量數(shù)據(jù)之間的相似度（或距離）計(jì)算的地方都可以使用 LSH來加快查找匹配速度。例如：查找網(wǎng)絡(luò)上的重復(fù)網(wǎng)頁、查找相似新聞網(wǎng)頁或文章、圖像檢索、音樂檢索、指紋匹配?？梢钥闯鲞@些應(yīng)用均為高度相似的圖片檢索，在這一領(lǐng)域， LSH 具有很大的優(yōu)勢。 實(shí)現(xiàn)及訓(xùn)練 可以說，找到滿足條件的映射 Hash函數(shù)為使用中的重點(diǎn)，限制求解除 Hash函數(shù)的條件為距離度量，距離度量的不同決定找到的位置敏感 Hash函數(shù)也不相同。本文分別實(shí)現(xiàn)了 Cosine distance 和 normal Euclidean distance 對應(yīng)的LSH hash 方程。 Cos_dist = A B / |A||B| 公式【 】 為余弦夾角距離常用來判斷兩個(gè)向量之間的夾角距離，余弦值越大，表示它們越相似。若 AB 為向量，則 |A|為向量 A的模。余弦夾角距離對應(yīng)的 LSH Hash 方程為： H(V) = sign(V R)，其中 R 是一個(gè)隨機(jī)向 量。 V R可以看做是將向量 V在平面 R上進(jìn)行投影操作。 H(V)利用隨機(jī)的超平面將原始數(shù)據(jù)空間進(jìn)行劃分，數(shù)據(jù)投影后會被超平面二分，這樣的多個(gè)劃分后，原始數(shù)據(jù)被空間中一個(gè)個(gè)單元容納，而位于每個(gè)單元內(nèi)的數(shù)據(jù)在原空間是相鄰的， 只是 換了一種編碼表示，新 表示空間中相鄰的在原空間中很大概率相鄰。 歐氏距離是衡量空間中兩個(gè)點(diǎn)之間的距離最重要的距離度量方式。歐氏距離對應(yīng)的 LSH hash 方程為： H(V) = |V R + b| / a，其中 R 是一個(gè)隨機(jī)向量， a是代表放縮的常量， b 是一個(gè)在 [0,a]之間均勻分布的隨機(jī)變量。公式中 V R可以看做是將 V 向 R 上進(jìn)行投影操作， 與 余弦距離類似， 同樣 對空間進(jìn)行劃分， 只是 此時(shí)， 劃分 的對象為投影后的線段，將所有數(shù)據(jù)都投影到直線上后，位于同一個(gè)線段內(nèi)的數(shù)據(jù)很大概率在原空間是相鄰的。 本文所實(shí)現(xiàn)的方式即為這兩種 LSH hash 方程，但由于他們均使用隨機(jī)生成的變量構(gòu)成 LSH hash 方程，是一種與數(shù)據(jù)無關(guān)的一種構(gòu)建方式，故無法進(jìn)行訓(xùn)練。在實(shí)際中，進(jìn)行多次實(shí)驗(yàn)，生成不同的 LSH hash 方程，將其中效果最好的hash 方程保留下來與其他模型進(jìn)行對比。 基于 Spectical Hash 的圖像檢索索引算法 研究 背景技術(shù) 【 Yair Weiss, Antonio B. Torralba, Robert Fergus Conference: Neural Information Processing Systems NIPS , pp. 17531760, 2021】 一個(gè) 好的 Hash 碼應(yīng)該具有這樣特性： （ 1） 計(jì)算簡單，對未觀測數(shù)據(jù)有較好的支持（ 2） 用較小的 bit就能夠編碼整個(gè)數(shù)據(jù)集， bit 位利用率高（ 3） 相似的數(shù)據(jù)集合應(yīng)該對應(yīng)相似的 Hash碼。 Spectral Hashing 是 2021 年 Yair Weiss 建 模這些特性提出的一種 Hash方法，他通過對 Hash過程進(jìn)行建模， 構(gòu)建 數(shù)學(xué)模型，解出與數(shù)據(jù)分布相關(guān)的 Hash 方程。 由于要找的目標(biāo)盡可能短， bit 位利用率高， 這需要 每一位上出現(xiàn) 0或者 1的概率相同，并且每個(gè)維度相互獨(dú)立。 不僅 如此， 還需要 尋找，原空間中相近的點(diǎn)， 在 目的空間 仍然 相近。若原數(shù)據(jù) nRX? ， y表示原數(shù)據(jù)轉(zhuǎn)換后的 Hash 值 ,則原空間中兩者之間的距離表示為： 這樣，在相似點(diǎn)對應(yīng)的 Hamming 空間中各點(diǎn)距離和可寫為 如果加上獨(dú)立性條件，則可以將原問題建模如下： 其中，表示每個(gè)每個(gè) bit 命中 0、 1概率相同， 使 每個(gè) bit 能夠表示更多的信息，表示對每個(gè) bit 相關(guān)性的約束， 表示 每個(gè)維度需盡可能獨(dú)立。 為了使 Hash 函數(shù)能夠覆蓋未觀測樣本，不直接使用樣本集， 而是 對樣數(shù)據(jù)實(shí)際分布進(jìn)行估計(jì)，假設(shè)數(shù)據(jù) nRX? 是概率分布 P（ x）的樣本， 則 這個(gè)問題就可以將原離散問題轉(zhuǎn)化為期望問題。 這可以看做積分方程的問題，通過相關(guān)文獻(xiàn)可知，它的解為LaplaceBeltrami 算子的奇異方程，解方程為具有最小 奇異值的解方程。為了簡化該問題的求解過程，現(xiàn)假設(shè)樣本分布為均勻分布，即分布 P（ x）為均勻分 布，則可以的到奇異方程和奇異值分別為： Spectral Hashing 方法通過統(tǒng)計(jì)現(xiàn)有樣本對數(shù)據(jù)分布進(jìn)行估計(jì)，根據(jù)預(yù)估分布，求出模型解析解的方法。 Spectral Hashing 是一種數(shù)據(jù)相關(guān)的算法，整個(gè)算法建立在數(shù)據(jù)分布估計(jì)上， 若 預(yù)估分布吻合， 則 Hash 效果具有理論保證，基于 Spectral Hashing 方法自發(fā)表以來越來越多，也更受關(guān)注。 Hashing 實(shí)現(xiàn)及訓(xùn)練 首先探索均勻分布 假設(shè)下， Spectral Hashing 的求解過程，為了使結(jié)果符合獨(dú)立性假設(shè)，可對輸入數(shù)據(jù)進(jìn)行 PCA 分解，使各維度相互獨(dú)立，然后根據(jù)奇異值公式，求出每個(gè)維度的奇異值方程，并選擇出奇異值較小的奇異方程為最終Hash 方程。針對均勻分布數(shù)據(jù)具體求解操作步驟如算法【 1】 ， 計(jì)算 Hash 值步驟如【 】 。 算法 1 均勻分布下 Spectral Hashing訓(xùn)練步驟 輸入： 部分原始數(shù)據(jù) 輸出： PCA降低緯度向量、 Spectral Hashing二進(jìn)制 hash 函數(shù) 算法： 使用 PCA降低緯度到 d 維 針對每個(gè)維度，根據(jù)公式找出 k 個(gè)最小的特征值并記錄特征方程，總共可得到 dk個(gè)。 從 dk 個(gè)中找到 k 個(gè)最小的特征值，對應(yīng)的 k 個(gè)特征方程為最終解（同一維度也可以） 將最終得到的 k 個(gè)特征方程，外部嵌套 sign 函數(shù)就成為二進(jìn)制 hash 函數(shù) 返回 算法 2 均勻分布下 Spectral Hashing 計(jì)算 Hash 步驟 輸入： 原始數(shù)據(jù)、 PCA分解向量、 Spectral Hashing二進(jìn)制 hash 函數(shù) 輸出： 對應(yīng)的 k 維二進(jìn)制 hash 值 算法： 使用 PCA分解向量將原始數(shù)據(jù)降緯到 d 維 使用 Spectral Hashing二進(jìn)制 hash 函數(shù)將 d 維數(shù)據(jù) 轉(zhuǎn)換成 k 維二進(jìn)制 hash 值 返回 其次，本文對數(shù)據(jù)真實(shí)分布進(jìn)行探索，通過對 4096圖像數(shù)據(jù)統(tǒng)計(jì)，發(fā)現(xiàn) PCA 分解后的數(shù)據(jù)符合正態(tài)分布，結(jié)果如圖【 】 ，所以均勻假設(shè)就不與條件相符，需求解高斯分布下 Spectral Hashing 模型的解，但由于能力所限，基于高斯分布的 Spectral Hashing 并未求得結(jié)果，現(xiàn)采用等價(jià)方式， 即 ：將高斯分布數(shù)據(jù)轉(zhuǎn)換到均勻分布，進(jìn)而利用已知均勻分布下的解求高斯分布下 Spectral Hashig。高斯分布數(shù)據(jù)轉(zhuǎn)換成均勻分布可用公式表示，其中， PDF 為高斯分布累計(jì)概率分布， 使 用 這種逆函數(shù)的方法轉(zhuǎn)換數(shù)據(jù)即可得到均勻數(shù)據(jù)。然后，這樣轉(zhuǎn)換成的均勻分布可能丟失了方差信息，可以通過實(shí)驗(yàn)確認(rèn)，補(bǔ)償這種方差的方法是對均勻數(shù)據(jù)乘以標(biāo)準(zhǔn)差。由此形成了對比實(shí)驗(yàn)，基于數(shù)據(jù)轉(zhuǎn)換的 Spectral Hashing，和外加方差補(bǔ)償?shù)?Spectral Hashing 進(jìn)行對比， 最終 得到最適合的 Spectral Hashing 方法。求解方法可表述為算法【 】 ，計(jì)算 Hash 用算法【 】 表示。 【分布圖】 算法 3 高斯分布下 Spectral Hashing訓(xùn)練步驟 輸入： 部分原始數(shù)據(jù) 輸出： PCA降低緯度向量、 d 維數(shù)據(jù)各自維度對應(yīng)的 PDF函數(shù)（，及標(biāo)準(zhǔn)差）、 Spectral Hashing二進(jìn)制 hash 函數(shù) 算法： 使用 PCA降低緯度到 d 維 求解 d 維數(shù)據(jù)各自維度對應(yīng)的 PDF 函數(shù) 將數(shù)據(jù)進(jìn)行轉(zhuǎn)換的到均勻分布數(shù)據(jù)（，外加乘以標(biāo)準(zhǔn)差補(bǔ)償） 針對每個(gè)維度，根據(jù)公式找出 k 個(gè)最小的特征值并記錄特征方程，總共可得到 dk個(gè)。 從 dk 個(gè)中找到 k 個(gè)最小的特征值，對應(yīng)的 k 個(gè)特征方程為最終解（同一維度也可以） 將最終得到的 k 個(gè)特征方程，外部嵌套 sign 函數(shù)就成為二進(jìn)制 hash 函數(shù) 返回 算法 4 高斯分布下 Spectral Hashing計(jì)算 Hash 步驟 輸入： 原始數(shù)據(jù)、 PCA降低緯度向量、 d維數(shù)據(jù)各自維度對應(yīng)的 PDF函數(shù)（，及標(biāo)準(zhǔn)差）、 Spectral Hashing二進(jìn)制 hash 函數(shù) 輸出： 對應(yīng)的 k 維二進(jìn)制 hash 值 算法： 使用 PCA分解向量將原始數(shù)據(jù)降緯到 d 維 使用每維對應(yīng)的 PDF 函數(shù)將數(shù)據(jù)轉(zhuǎn)換到均勻分布（，外加乘以標(biāo)準(zhǔn)差補(bǔ)償） 使用 Spectral Hashing二進(jìn)制 hash 函數(shù)將 d 維數(shù)據(jù)轉(zhuǎn)換成 k 維二進(jìn)制 hash 值 返回 本算法的訓(xùn)練過程從算法 1 及算法 3 可以看出，先選出部分?jǐn)?shù)據(jù)依據(jù)算法求得結(jié)果，再根據(jù)算法 2 及算法 4 求得 Hash 值。 基于深度神經(jīng)網(wǎng)絡(luò) Hash 的圖像檢索索引算法研究 背景技術(shù) 【 Using Very Deep Autoencoders for ContentBased Image Retrieval Alex Krizhevsky and Georey E. HintonGE Hinton 2021 】 2021 年 Alex Krizhevsky 和 Georey E. Hinton 提出使用 Autoencoder 進(jìn)行大規(guī)模圖像檢索。這篇文章使用深度 Autoencoder 將小圖片（共 32*32=1024 像素）映射到二進(jìn)制短碼，成為倒排索引。對于 圖像檢索來說，二進(jìn)制 Hash 碼比原始像素的匹配耗時(shí)更短，檢索速度更快。檢索過程中，將圖片直接作為輸入，經(jīng)過 Autoencoder 網(wǎng)絡(luò)抽取得到 Hash 值，使用 Hash 值進(jìn)行檢索，得到對應(yīng)的圖片集合， 給出 檢索結(jié)果。文中深度 Autoencoder 采用的網(wǎng)絡(luò)結(jié)構(gòu)如圖所示，采用全連接神經(jīng)網(wǎng)絡(luò)，逐層減半直到目標(biāo)大小，訓(xùn)練中，采用 RBM 逐層訓(xùn)練得到初始 權(quán)值，再用其初始化 Autoencoder 網(wǎng)絡(luò)，通過 Autoencoder 整體調(diào)權(quán)的到最終模型，精細(xì)調(diào)整權(quán)值， 最終 得最優(yōu)網(wǎng)絡(luò)。 RBM 與 Autoencoder 同樣為無監(jiān)督網(wǎng)絡(luò)，從某程度上，可以認(rèn)為 Autoencoder為 RBM 疊加而成，所以可以用 RBM 預(yù)訓(xùn)練。 RBM 為雙層結(jié)構(gòu)，可見層和隱層，模擬動力系統(tǒng)中穩(wěn)態(tài)的定義，尋找網(wǎng)絡(luò)穩(wěn)態(tài)的定義， RBM 的詳細(xì)介紹可以由論文【】獲得。該文使用標(biāo)準(zhǔn)的 RBM 訓(xùn)練過程進(jìn)行預(yù)先訓(xùn)練。 【 G. E. Hinton. A practical guide to training restricted boltzmann Report UTML2021003, University of Toronto, 2021.】 整體調(diào)權(quán) Autoencoder 過程仍然使用自恢復(fù)誤差，即網(wǎng)絡(luò)輸入與輸出的歐氏距離，距離越小， 中間層 保留的輸入信息越多。在 Autoencoder 中每層神經(jīng)元逐層減半直至達(dá)到目標(biāo)長度，特別值得注意的是，為了強(qiáng)制實(shí)現(xiàn)二值化，整個(gè)網(wǎng)絡(luò)前傳過程中，將中間層強(qiáng)制將數(shù)據(jù)轉(zhuǎn)換成 0和 1，后傳時(shí)直接將梯度后傳。這種方法比較簡單的實(shí)現(xiàn)，改動很不大即可在現(xiàn)有工具上實(shí)現(xiàn)該過程。