---
tags: 'ML notes'
---
# Survey of vector space search
這個主題的目的在於如何快速從龐大的高維特徵空間查找到與 query vector 最相似的 ID。

特徵降維 (PCA, LDA)、最近鄰居演算法(KD-Tree, LSH, Product/Vector quant)、分層辨識 (利用年齡、性別等顯性特徵分層儲存特徵) 都是常見的方法

# KD-Tree

常見的 tree-based search algo，是這個領域的經典演算法。他透過不斷地找出變異數最大的維度來將整個特徵空間用一個超平面分割成兩塊來使得特徵空間變成一個二元樹，每一個特徵空間的點都對應到二元樹中的節點，以此來搜尋到 nearest point。但是，K-D tree 在高維度的線性搜尋的時候效率就會變差，因為高維空間的資料分布非常稀疏會導致搜尋的準度下降很多。**現在已經不太會用這個方法來做了**。


# Quantization

**在量級到幾百 millions 以上的時候幾乎是唯一一個可以用的方法**，只是量化方法永遠無法避免精度的下降。[faiss](https://github.com/facebookresearch/faiss) 提供了許多方便的用法供參。

## Vector quantization
**向量量化 (Vector quantization)** 是將特徵空間 encode 到一個點集合 (set of points) 的流程，經過 encode 之後，這些點集合被稱為 codebook，而codebook中的每一個點都可以代表特徵空間的一個區域 (資料中心的概念，類似K-means)。Vector quantization 就是在加速計算這些向量之間的距離運算，當 m 個向量被一個 N size 的 codebook (m>>N) encode 之後，向量之間要做比較的次數就可以從 m 次減少為 N 次。

VQ 由 encoder 和 decoder 構成，encoder會產出每一個codebook中作為代表向量的 codeword 的index，之後會去計算這些 input vector 和 codeword of codebook 之間的距離，找出最靠近的 codeword 然後把他的 index 通過 channel(the channel could be a computer storage, communications channel, and so on) 送過去 decoder 解出最靠近的 vector。


## Product quantization
在 [Product Quantization for Nearest Neighbor Search, 2010](https://ieeexplore.ieee.org/document/5432202) 中提出。

乘積量化 (Product quantization) 是一個基於近似最近鄰的 vector quantization 方法，他是透過 divide-and-conquer 的方法去做 quant。首先他會將特徵空間的向量先分割成 m 個子向量 (sub-vector)，然後用 m 群 codebook 來對這些子向量做 quant，最後再用一個可以結合這些子向量的方法來合回去，叫做 inverted file system with the asymmetric distance computation (IVFADC)，也被稱為 IVFAQ。詳細流程可參考 ANN 之 Product Quantization, IVFPQ + HNSW for Billion-scale Similarity Search。

- 舉例來說，下圖是一個128維的向量，先做完 PCA (16 components) 之後被切為8個子向量(m=8)，其中每一個子向量都是16個components (16維)
- [Product quantization for nearest neighbor search](https://ieeexplore.ieee.org/document/5432202)

PQ 相關研究發展 - from https://github.com/facebookresearch/faiss/wiki#research-foundations-of-faiss


# Graph-based

Graph-based search algo 的想法則是將特徵空間的點變成一個 graph，在每一次的搜尋擷取都隨機從一個 $node_{curr}$ 開始搜尋。他會先去計算這個 $node_{curr}$ 的 neighbor point 與 query vector 之間的距離，選出最小距離的 neighbor point 作為下一個 $node_{curr}$，然後一直做到不再有任何 neighbor point 跟 query vector 的距離比 $node_{curr}$跟 query vector 的距離小的時候，這時 $node_{curr}$就是在 graph 中離 query vector 最近的點。

## Navigable small world (NSW)

**Navigable small world (NSW)** 就是 graph-based search alglo 可以套用到 massive ID search 的一個案例，在建構 NSW 的時候，每一個點都會被插進一個序列然後從一個隨機點開始去找出這個點的鄰居，將這些鄰居跟這個新點做連接。在建構的過程中會有兩種邊 (edges)，short-range 用來近似 [delaunay graph](https://chtseng.wordpress.com/2019/08/07/delaunay-triangulation-voronoi-diagrams/)，long-range 用來在指數規模上減少搜尋的次數。隨著迭代的進行，這些 short-range 會逐漸變成 long-range，而 long-ragne 則構成了整個 NSW。這裡他不使用 Delaunay Triangulation 而只是近似他的原因是計算複雜度太高。

- https://www.youtube.com/watch?v=SKrHs03i08Q&list=PLKQB14e0EJUWaTnwgQogJ3nSLzEFNn9d8

在記憶體考量上，NSW或是HNSW (Hierarchical Navigable Small Worlds)不是最好的選擇，因為資料量並沒有減少，只不過是搜尋變快而已，要追求最快的還是 PQ，但 PQ 會降精度。

- https://www.youtube.com/watch?v=SKrHs03i08Q&list=PLKQB14e0EJUWaTnwgQogJ3nSLzEFNn9d8

# LSH

**區域性敏感雜湊 (Locality sensitive hashing, LSH)** 的做法是將去建構一個 hash function h 使得當 vector p 和 q 足夠靠近的時候，機率 h(p) = h(q)。在搜尋的時候 LSH 會對所有資料的特徵做雜湊來得到每一個點的值，之後就可以找到與 query point 有最相似的雜湊值的點，那些就是與 query vector 最相近的那群特徵。

- https://randorithms.com/2019/09/19/Visual-LSH.html

LSH 在小規模或是中規模的資料集都可以用 (幾 millions ~ 幾十 millions)，而且搜尋的速度是最快的，也不會掉太多精度。開源工具有 nmslib, FALCONN, LSHash。而Hash的有 Average Hash, Perceptual Hash, Difference Hash 等方法可以使用 ([reference](https://erdogant.github.io/undouble/pages/html/hash_functions.html))

以建構搜索圖片特徵的情況為例，使用Hash算法的主要觀念即為將圖片進行Hash轉化後，生成一組二進制(0、1)的數字串，接著透過比對不同圖片之間的Hash值，計算出圖片之間的相似度，即可得出圖片之間的相似性。

## Average Hash (AHash) 指的是採用圖片的平均像素來作為 hash 計算的基準

- 流程: 把圖片轉為灰階
→ resize image to 8x8
→ 計算所有64個畫素的灰度平均值
→ 比較每個化素的灰度：將64個畫素的灰度與平均值進行比較，如果該畫素點的值大於等於平均值，則將該點註記為1；小於平均值則註記為0
→ 計算Hash value：該圖片計算出來的 Hash Value是由64位的1或0所組成，這即為這張圖片的指紋，其數字的組合順序並不重要，只要確保每張圖片的組成方式均為相同即可
- 最後就可以得到像是1111110001100010110011100001001110100101101000111111011111000111 的一串數值，這就是這張圖片的 hash value，我們拿兩張圖片的 hash value 之間算 hamming distance 就可以簡單地獲得他們的相似度 (假如 hamming distance 為 3，表示兩個圖片有 3 個 hash value 不同)

## Perceptual Hash (PHash) 是採用DCT（離散餘弦變換）來獲取圖片低頻資訊的 Hash 方法

- DCT（離散餘弦變換）是一種用於影像壓縮的演算法，可以將影像從畫素轉換到頻域，透過兩次的DCT後，把頻率按照頻率大小進行分離。低頻率的訊息會集中於左上角，右下角則集中高頻率訊息
- 主要基於計算低頻的均值哈希值，對每張影像產生一組指紋字符串，透過漢明距離來比對影像之間的相似度

流程:
把圖片轉為灰階
→ resize image to 32x32
→ 做 DCT trasnformation，得到一個 32x32 的 DCT matrix 後只取 DCT matrix 最左上角的 8x8 矩陣出來算平均值。每一個像素點均與像素平均值進行比對，大於等於avreage的像素點就設為1，小於的則設為0，最後就會得到一串 64 位由 0 和 1 所組成的 hash value。
- 結果並不能告訴我們真實性的低頻率，只能粗略地告訴我們相對於平均值頻率的相對比例。只要圖片的整體結構保持不變，hash結果值就不變。能夠避免伽馬校正或顏色直方圖被調整帶來的影響。對於變形程度在25%以內的圖片也能精準識別。

→ 利用 hamming distance 來算兩張圖片的相似度


## Differential Hash (DHash)，顧名思義是利用圖片像素的差值作為 hash 的計算基準

流程: 把圖片轉灰階
→ 計算差值: 從左邊的像素點往右邊比較，如果左邊的像素點大於右邊，則標記為1，反之則為零，最後會產生一個8*8的共64個差異值。計算完成後，產生的數值即為該圖片的Hash value


綜合以上三種常見方式，DHash 是其中計算最簡單最快速的方式且準確度並不低，只略低於 PHash，因此大多是使用 DHash 來算 hash ([reference](https://zx7978123.medium.com/%E5%9C%96%E5%83%8F%E7%9B%B8%E4%BC%BC%E5%BA%A6%E7%AE%97%E6%B3%95-google%E4%BB%A5%E5%9C%96%E6%90%9C%E5%9C%96-2-bde3d8c9568d))

# **Knowledge distillation**

**知識蒸餾 (Knowledge distillation)** 原本是用來將 large pre-trained CNN 壓縮成小模型好在 mobile 或是 embedded device 上面跑的技巧，[Exclusivity-consistency regularized knowledge distillation for face recognition](https://www.ecva.net/papers/eccv_2020/papers_ECCV/papers/123690324.pdf) 將知識蒸餾應用在 FR 上面用來改進 FR student network 的能力。他的做法是先把一個 conv layer 中所有的 filters 從 $W \in R^{MNK_1K_2}$reshape 為 $R^{N \times D}$ where N and M
are numbers of filters and input channels。K1 and K2 are the spatial height and width of filters。$D = M \times K_1 \times K_2$。reshape function 如下，其中 $w_i \in R^{1 \times D}$ 是一個 $W$ 中 index 為 i 的 filter。


這個映射的概念可以看成 $L_{WE}(W)$ 鼓勵 W 中的兩個不同 filter 越不一樣越好，將這個映射應用在 student network 就可以使得他在有限的架構下學到更多東西。他應用的方式是把他加入 loss 當中，變成


where $L_{HFC}$ is L2 based hardness-aware feature consistency loss, which encourages the face features from teacher and student as similar as possible. $L_{WD}$ is L2 weight decay.

知識蒸餾的方法將樣本之間的關係視為知識，迫使學生模型學習樣本的相關性，而不是從教師模型中嵌入特徵，但在 [Evaluation-oriented knowledge distillation for deep face recognition](https://arxiv.org/abs/2206.02325) 中，作者發現只允許 student model 去研究相關性是很沒有彈性的，因此提出了一個 evalution-oriented technique 來改善。從教師和學生模型中獲得不同評價結果的關係被定義為關鍵關係 (crucial relationship)。通過一種新穎的基於等級的損失函數，學生模型可以在訓練中專注於這些關鍵關係。

# Reference

- [What are some fast similarity search algorithms and data structures for high-dimensional vectors? - Quora](https://www.quora.com/What-are-some-fast-similarity-search-algorithms-and-data-structures-for-high-dimensional-vectors)
- [图像检索：再叙ANN Search (yongyuan.name)](https://yongyuan.name/blog/ann-search.html)
- [PQ(product quantization) 算法---(一)_hairuiJY的博客-CSDN博客](https://blog.csdn.net/u010368556/article/details/80960510)
- [EE523 Ch. 10 Vector Quantization Overview](http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE523_files/Ch_10_1%20VQ%20Description%20(PPT).pdf)