視覺搜尋系統協助使用者發現與所選圖片在視覺上相似的圖片。本章設計一個類似 Pinterest 的視覺搜尋系統。

釐清需求#

以下是候選人與面試官之間的典型互動。

候選人：搜尋結果是否需要從最相似到最不相似排序？

面試官：是的，列表中較前面的圖片應與查詢圖片更相似。

候選人：系統是否也需要支援影片？

面試官：我們只聚焦於圖片。

候選人：像 Pinterest 這樣的平台允許使用者選取圖片的裁切區域並檢索相似圖片，我們是否需要支援此功能？

面試官：是的。

候選人：顯示的圖片是否會根據使用者進行個人化？

面試官：為了簡化，我們不考慮個人化。同一張查詢圖片無論誰搜尋，都會產生相同的結果。

候選人：模型是否可以使用查詢圖片的 metadata（例如圖片標籤）？

面試官：實務上模型會使用圖片 metadata，但為了簡化，我們假設僅依賴圖片像素。

候選人：使用者是否可以執行儲存、分享或按讚等操作？這些操作有助於標註訓練資料。

面試官：很好的觀點。為了簡化，我們假設唯一支援的操作是圖片點擊。

候選人：是否需要審核圖片內容？

面試官：維持平台安全很重要，但內容審核不在本次範圍內。

候選人：我們可以在線上建構訓練資料，並根據使用者互動進行標註。這是預期的建構方式嗎？

面試官：是的，這聽起來合理。

候選人：搜尋速度應該多快？假設平台上有 1,000 至 2,000 億張圖片，系統應能快速檢索相似圖片。這是合理的假設嗎？

面試官：是的，這是合理的假設。

問題摘要：設計一個視覺搜尋系統，根據使用者提供的查詢圖片檢索相似圖片，並按相似度排序後顯示。平台僅支援圖片（不含影片或文字查詢），且不需要個人化。

將問題框架化為 ML 任務#

本節選擇一個明確定義的 ML 目標，並將視覺搜尋問題框架化為 ML 任務。

定義 ML 目標#

為了使用 ML 模型解決此問題，需要建立明確的 ML 目標。潛在的 ML 目標為：準確檢索與使用者搜尋圖片在視覺上相似的圖片。

指定系統的輸入與輸出#

• 輸入：使用者提供的查詢圖片
• 輸出：與查詢圖片視覺上相似的圖片，按相似度排序

選擇合適的 ML 類別#

模型的輸出是一組按相似度排序的圖片，因此視覺搜尋系統可以框架化為排序問題（ranking problem）。排序問題的目標是根據與查詢的相關性，對一組項目（如圖片、網站、產品等）進行排序，使更相關的項目出現在搜尋結果的較高位置。許多 ML 應用，包括推薦系統、搜尋引擎、文件檢索和線上廣告，都可以框架化為排序問題。

本章使用一種廣泛採用的方法——表徵學習（representation learning），以下詳細說明。

表徵學習#

在表徵學習 中，模型被訓練為將輸入資料（如圖片）轉換為稱為 embedding 的表徵。換言之，模型將輸入圖片映射到一個 $N$ 維空間（稱為 embedding space）中的點。這些 embedding 經過學習，使得相似的圖片在空間中彼此靠近。

圖 2.3 說明兩張相似圖片如何被映射到 embedding space 中相近的位置。為便於展示，我們在 $2$ 維空間中視覺化圖片 embedding（以 ‘$x$’ 表示）。實際上，該空間為 $N$ 維，其中 $N$ 為 embedding 向量的大小。

如何使用表徵學習進行圖片排序？#

• 首先，將輸入圖片轉換為 embedding 向量
• 接著，透過測量 embedding space 中的距離，計算查詢圖片與平台上其他圖片之間的相似度分數
• 最後，根據相似度分數對圖片進行排序

此時你可能有許多疑問，包括如何確保相似圖片在 embedding space 中彼此靠近、如何定義相似度、以及如何訓練此類模型。我們將在模型開發章節中詳細討論。

資料準備#

資料工程#

除了通用的資料工程基礎知識外，了解可用的資料至關重要。視覺搜尋系統主要關注使用者與圖片，可用的資料包括：

• 圖片
• 使用者
• 使用者與圖片的互動

圖片#

創作者上傳圖片，系統儲存圖片及其 metadata，如擁有者 ID、上下文資訊（例如上傳時間）、標籤等。表 2.1 為圖片 metadata 的簡化範例。

表 2.1：圖片 metadata

使用者#

使用者資料包含與使用者相關的人口統計屬性，如年齡、性別等。表 2.2 為使用者資料範例。

表 2.2：使用者資料

使用者與圖片的互動#

互動資料包含不同類型的使用者互動。根據需求，主要的互動類型為曝光（impression）和點擊（click）。表 2.3 為互動資料概覽。

表 2.3：使用者與圖片的互動資料

特徵工程#

本節討論如何工程化優質特徵並準備模型輸入。這通常取決於問題的框架化方式和模型的輸入。在前面的章節中，我們將視覺搜尋系統框架化為排序問題，並使用表徵學習來解決。具體而言，我們採用以圖片為輸入的模型，圖片在傳入模型前需進行預處理。以下是常見的圖片預處理操作：

• 調整大小（Resizing）：模型通常要求固定的圖片尺寸（例如 $224 \times 224$）
• 縮放（Scaling）：將圖片像素值縮放至 $0$ 到 $1$ 的範圍
• Z-score 標準化：將像素值縮放為均值 $0$、變異數 $1$
• 色彩模式一致性：確保圖片具有一致的色彩模式（例如 RGB 或 CMYK）

模型開發#

模型選擇#

選擇神經網路的原因：

• 神經網路擅長處理非結構化資料（如圖片和文字）
• 不同於許多傳統 ML 模型，神經網路能夠產生表徵學習所需的 embedding

在架構方面，需要選擇適用於圖片的架構。基於 CNN 的架構（如 ResNet）或較新的基於 Transformer 的架構（如 ViT）在圖片輸入上表現良好。圖 2.5 展示一個簡化的模型架構，將輸入圖片轉換為 embedding 向量。卷積層數量、全連接層神經元數量和 embedding 向量大小均為超參數，通常透過實驗選擇。

模型訓練#

為了檢索視覺上相似的圖片，模型必須在訓練過程中學習表徵（embedding）。本節討論如何訓練模型以學習圖片表徵。

常見的圖片表徵學習技術是對比訓練（contrastive training）。此技術訓練模型區分相似與不相似的圖片。如圖 2.6 所示，我們提供模型一張查詢圖片（左側）、一張與查詢圖片相似的圖片（右側高亮的狗圖片）以及數張不相似的圖片（右側其餘圖片）。在訓練過程中，模型學習產生表徵，使相似圖片比不相似圖片更接近查詢圖片。

為使用對比訓練技術訓練模型，首先需要建構訓練資料。

建構資料集#

每個訓練資料點包含：

• 一張查詢圖片
• 一張與查詢圖片相似的正樣本圖片
• ${n-1}$ 張與查詢圖片不相似的負樣本圖片

Ground truth 標籤為正樣本圖片的索引。如圖 2.7 所示，查詢圖片（q）搭配 $n$ 張其他圖片，其中一張是相似的（狗的圖片），其餘 ${n-1}$ 張是不相似的。此資料點的 ground truth 標籤為 $2$（即圖 2.7 中 $n$ 張圖片中的第二張）。

建構訓練資料點時，隨機選擇一張查詢圖片和 ${n-1}$ 張負樣本圖片。選擇正樣本圖片有以下三種方式：

• 人工判斷
• 使用互動資料（如使用者點擊）作為相似度的代理指標
• 自監督（self-supervision）：從查詢圖片人工生成相似圖片

以下評估各方式。

人工判斷#

此方式依賴人工標註者手動尋找相似圖片。人工參與可產生準確的訓練資料，但成本高昂且耗時。

使用互動資料作為相似度代理#

透過互動資料衡量相似度，例如當使用者點擊某張圖片時，該圖片被視為與查詢圖片相似。

• 優點：不需要人工操作，可自動生成訓練資料
• 缺點：點擊訊號通常非常嘈雜（使用者有時會點擊不相似的圖片），且資料非常稀疏（許多圖片可能沒有點擊資料）。使用嘈雜且稀疏的訓練資料會導致效能不佳

從查詢圖片人工生成相似圖片#

透過資料增強（data augmentation）從查詢圖片生成相似圖片。例如，旋轉查詢圖片並將生成的新圖片作為相似圖片。近期開發的框架如 SimCLR 和 MoCo 採用相同方式。

• 優點：不需要人工操作，可透過簡單的資料增強邏輯建立相似圖片；訓練資料不嘈雜，因為增強圖片總是產生相似圖片
• 缺點：建構的訓練資料與真實資料不同。實務上，相似圖片並非查詢圖片的增強版本，而是在視覺和語意上相似但本質不同的圖片

哪種方式最適合我們的情境？#

在面試中，提出多種方案並討論其權衡至關重要。通常不存在單一最佳解決方案。

本案例選擇自監督方式，原因如下：

• 沒有前期成本，流程可完全自動化
• 各種框架（如 SimCLR）在大型資料集上已展現良好成果。由於平台上有數十億張圖片，此方式非常合適

若實驗結果不理想，可隨時切換到其他標註方式。例如：

• 先使用自監督方式，之後改用點擊資料進行標註
• 結合多種方式：使用點擊資料建構初始訓練資料，再依賴人工標註者識別並移除嘈雜的資料點

與面試官討論不同方案和權衡，是做出良好設計決策的關鍵。

選擇損失函數#

如圖 2.9 所示，模型以圖片為輸入，並為每張輸入圖片產生一個 embedding。${E_x}$ 表示圖片 $x$ 的 embedding。

訓練目標是最佳化模型參數，使相似圖片的 embedding 在 embedding space 中彼此靠近。如圖 2.10 所示，正樣本圖片和查詢圖片在訓練過程中應越來越接近。

為達成此目標，需要使用損失函數來衡量所產生 embedding 的品質。不同的損失函數專為對比訓練設計，面試官通常不期望深入討論，但對對比損失函數的高層次理解至關重要。

以下簡要說明簡化版對比損失的運作方式。如需深入了解，請參閱。

如圖 2.11 所示，對比損失的計算分為三個步驟：

1. 計算相似度

計算查詢圖片與其他圖片 embedding 之間的相似度。常用的度量方式包括：

• 內積（dot product） 和 餘弦相似度（cosine similarity）：廣泛用於衡量 embedding space 中點之間的相似度
• 歐式距離（Euclidean distance）：也可衡量相似度，但在高維空間中因維度詛咒（curse of dimensionality） 的影響，效能通常較差。詳情可參閱

2. Softmax

對計算出的距離應用 softmax 函數，確保值的總和為 1，使其可被解釋為機率。

3. 交叉熵（Cross-entropy）

交叉熵 衡量預測機率與 ground truth 標籤的接近程度。當預測機率接近 ground truth 時，表示 embedding 足以區分正樣本與負樣本。

在面試中，也可以討論使用預訓練模型的可能性。例如，利用預訓練的對比模型並使用訓練資料進行微調（fine-tune）。這些預訓練模型已在大型資料集上訓練，因此已學到良好的圖片表徵，相比從頭訓練可大幅縮短訓練時間。

評估#

模型開發完成後，可進行評估。本節涵蓋離線和線上評估的重要指標。

離線指標#

根據需求，離線評估有可用的評估資料集。假設每個資料點包含一張查詢圖片、數張候選圖片，以及每對候選圖片與查詢圖片的相似度分數。相似度分數為 $0$ 到 $5$ 之間的整數，其中 $0$ 表示不相似，$5$ 表示在視覺和語意上非常相似。對於評估資料集中的每個資料點，我們比較模型產生的排序與基於 ground truth 分數的理想排序。

以下是搜尋系統常用的離線指標。搜尋、資訊檢索和推薦系統通常共享相同的離線指標。

• Mean Reciprocal Rank (MRR)
• Recall@k
• Precision@k
• Mean Average Precision (mAP)
• Normalized Discounted Cumulative Gain (nDCG)

MRR#

此指標透過考慮每個輸出列表中第一個相關項目的排名，然後取平均值來衡量模型品質。公式為：

$MRR= \frac{1}{m} \sum_{i=1}^m \frac{1}{rank_i}$

其中 $m$ 是輸出列表的總數，$rank_i$ 是第 i 個輸出列表中第一個相關項目的排名。

圖 2.13 說明其運作方式。對於 4 個排序列表中的每一個，計算倒數排名（RR），然後計算 RR 的平均值以獲得 MRR。

MRR 的缺點：由於 MRR 僅考慮第一個相關項目而忽略列表中的其他相關項目，因此無法衡量排序列表的精確度和排序品質。例如，圖 2.14 顯示兩個不同模型的輸出：模型 1 有 3 個相關項目，模型 2 僅有 1 個相關項目，但兩者的 reciprocal rank 均為 0.5。基於此缺點，我們不採用此指標。

Recall@k#

此指標衡量輸出列表中相關項目數量與整個資料集中相關項目總數的比率。公式為：

$\text {recall@k} =\frac{\text { number of relevant items among the top } k \text { items in the output list }}{\text { total relevant items }}$

儘管 recall@k 衡量了模型遺漏多少相關項目，但此指標並不總是適用。在某些系統（如搜尋引擎）中，相關項目的總數可能非常多，導致分母過大而負面影響 recall。例如，當查詢圖片是一張狗的圖片時，資料庫可能包含數百萬張狗的圖片。目標不是回傳每一張狗的圖片，而是檢索最相似的少數幾張。

由於 recall@k 無法衡量模型的排序品質，我們不採用此指標。

Precision@k#

此指標衡量輸出列表前 k 個項目中相關項目的比例。公式為：

$\text { precision@k } =\frac{\text { number of relevant items among the top } {k} \text { items in the output list }}{{k}}$

此指標衡量輸出列表的精確度，但不考慮排序品質。例如，在圖 2.15 中，即使將更相關的項目排在更高位置，precision 也不會改變。此指標不適合我們的使用情境，因為我們需要同時衡量結果的精確度和排序品質。

mAP#

此指標首先為每個輸出列表計算 Average Precision (AP)，然後取 AP 值的平均。

AP 的定義：取一個包含 $k$ 個項目（如圖片）的列表，並對不同 $k$ 值的 precision@k 取平均。如果更多相關項目位於列表頂端，AP 值會更高。對於大小為 $k$ 的列表，AP 公式為：

$AP= \frac{\sum_{i=1}^k \text { Precision@$i$ if $i$‘th item is relevant to the user }}{\text { total relevant items }}$

圖 2.16 展示模型產生的 4 個輸出列表的 AP 計算。

由於取 precision 的平均值，列表的整體排序品質被納入考量。然而，mAP 是為二元相關性設計的，即每個項目要麼相關要麼不相關。對於連續的相關性分數，nDCG 是更好的選擇。

nDCG#

此指標衡量輸出列表的排序品質，並展示與理想排序相比的表現。首先說明 DCG，再討論 nDCG。

DCG（Discounted Cumulative Gain）

DCG 透過累加列表中每個項目的相關性分數來計算，分數從列表頂端累加至底端，較低排名的結果分數會被折扣。公式為：

$\mathrm{DCG_p}=\sum_{i=1}^p \frac{r e l_i}{\log _2(i+1)}$

其中 $rel_i$ 是排在位置 $i$ 的圖片的 ground truth 相關性分數。

nDCG（Normalized DCG）

由於 DCG 累加相關性分數並折扣位置，結果可能是任意值。為獲得更有意義的分數，nDCG 將 DCG 除以理想排序的 DCG。公式為：

$\mathrm {nDCG_p}=\frac{DCG_p}{IDCG_p}$

其中 ${IDCG_p}$ 是理想排序（按項目相關性分數排列的排序）的 $DCG$。在完美的排序系統中，DCG 等於 IDCG。

以下透過範例理解 nDCG。圖 2.17 展示搜尋系統產生的輸出圖片列表及其對應的 ground truth 相關性分數。

nDCG 的計算分為 3 個步驟：

1. 計算 DCG
2. 計算 IDCG
3. DCG 除以 IDCG

步驟一：計算 DCG

$\mathrm {DCG_p}=\sum_{i=1}^p \frac{r e l_i}{\log _2(i+1)}=\frac{0}{\log _2(2)}+\frac{5}{\log _2(3)}+\frac{1}{\log _2(4)}+\frac{4}{\log _2(5)}+\frac{2}{\log _2(6)}=6.151$

步驟二：計算 IDCG

理想排序的計算方式與 DCG 相同，只是先推薦最相關的項目（圖 2.18）。

$\text {IDCG}p=\sum{i=1}^\nu \frac{r e l_i}{\log _2(i+1)}=\frac{5}{\log _2(2)}+\frac{4}{\log _2(3)}+\frac{2}{\log _2(4)}+\frac{1}{\log _2(5)}+\frac{0}{\log _2(6)}=8.9543$

步驟三：DCG 除以 IDCG

$\mathrm {nDCG_p}=\frac{DCG_p}{IDCG_p}=\frac{6.151}{8.9543}=0.6869$

nDCG 在大多數情況下表現良好。其主要缺點是推導 ground truth 相關性分數並非總是可行。在本案例中，由於評估資料集包含相似度分數，我們可以使用 nDCG 在離線評估中衡量模型效能。

線上指標#

本節探討衡量使用者發現喜愛圖片速度的常用線上指標。

點擊率（Click-through Rate, CTR）

此指標顯示使用者點擊顯示項目的頻率。CTR 公式為：

$\mathrm{CTR}= \frac{\text { Number of clicked images }}{\text { Total number of suggested images }}$

高 CTR 表示使用者經常點擊顯示的項目。CTR 在搜尋和推薦系統中是常見的線上指標。

每日/每週/每月平均停留時間

此指標顯示使用者對建議圖片的參與程度。當搜尋系統準確時，預期此指標會上升。

服務部署#

在服務時，系統根據查詢圖片回傳一組排序後的相似圖片。圖 2.19 展示預測管線和索引管線。以下逐一說明。

預測管線#

Embedding 生成服務#

此服務計算輸入查詢圖片的 embedding。如圖 2.20 所示，它先預處理圖片，再使用已訓練的模型產生 embedding。

最近鄰搜尋服務#

取得查詢圖片的 embedding 後，需要從 embedding space 中檢索相似圖片，這由最近鄰搜尋服務負責。

更正式地定義：給定查詢點 “q” 和一組其他點 S，找出 S 中最接近 “q” 的點。圖片 embedding 是 $N$ 維空間中的點，其中 $N$ 為 embedding 向量的大小。圖 2.21 顯示圖片 q 的前 3 個最近鄰。查詢圖片標記為 q，其他圖片標記為 $x$。

重新排序服務#

此服務結合業務層級邏輯和政策，例如：

• 過濾不當結果
• 確保不包含私人圖片
• 移除重複或近似重複的結果
• 執行其他類似邏輯

最終結果顯示給使用者前，均經過此服務處理。

索引管線#

索引服務#

平台上所有圖片均由此服務進行索引，以提升搜尋效能。

索引服務的另一職責是保持索引表的更新。例如，當創作者在平台上新增圖片時，該服務會索引新圖片的 embedding，使其可被最近鄰搜尋發現。

索引會增加記憶體使用量，因為需要在索引表中儲存所有圖片的 embedding。可透過向量量化（vector quantization） 和乘積量化（product quantization） 等方式進行最佳化以降低記憶體用量。

最近鄰（NN）演算法的效能#

最近鄰搜尋是資訊檢索、搜尋和推薦系統的核心元件。其效率的微幅提升可帶來顯著的整體效能改善。鑑於此元件的關鍵性，面試官可能要求你深入探討此主題。

NN 演算法可分為兩類：精確（exact）和近似（approximate）。

精確最近鄰#

精確最近鄰（也稱為線性搜尋）是最簡單的 NN 形式。其運作方式為搜尋整個索引表，計算每個點與查詢點 q 的距離，並檢索 $k$ 個最近的點。時間複雜度為 $O(N \times D)$，其中 $N$ 為總點數，$D$ 為點的維度。

在大規模系統中（$N$ 可能輕易達到數十億），線性時間複雜度過慢。

近似最近鄰（ANN）#

在許多應用中，向使用者展示足夠相似的項目已足夠，無需執行精確最近鄰搜尋。

ANN 演算法使用特定的資料結構將 NN 搜尋的時間複雜度降至次線性（如 $O(D \times logN)$），通常需要前期預處理或額外的儲存空間。

ANN 演算法可分為以下三類：

• 基於樹（Tree-based）的 ANN
• 基於局部敏感雜湊（LSH）的 ANN
• 基於聚類（Clustering-based）的 ANN

每個類別中有多種演算法，面試官通常不期望你了解每個細節，擁有高層次的理解即可。以下簡要介紹每個類別。

基於樹的 ANN#

基於樹的演算法透過將空間分割為多個分區來形成樹結構，然後利用樹的特性執行更快的搜尋。

透過迭代地為每個節點新增標準來形成樹。例如，根節點的一個標準可以是：gender = male。這表示任何具有 female 屬性的點屬於左子樹。

在樹中，非葉節點根據標準將空間分割為兩個分區；葉節點表示空間中的特定區域。圖 2.23 展示空間被分割為 7 個區域的範例。演算法僅搜尋查詢點所屬的分區。

典型的基於樹方法包括 R-trees、Kd-trees 和 Annoy（Approximate Nearest Neighbor Oh Yeah）。

基於局部敏感雜湊（LSH）的 ANN#

LSH 使用特定的雜湊函數降低點的維度並將其分組到桶（bucket）中。這些雜湊函數將彼此靠近的點映射到同一個桶。LSH 僅搜尋與查詢點 q 在同一桶中的點。詳情可參閱。

基於聚類的 ANN#

這些演算法根據相似度將點分組成群集（cluster）。群集形成後，演算法僅搜尋查詢點所屬群集中的子集點。

應該使用哪種演算法？#

• 精確最近鄰：結果保證準確，適合資料點數量有限或要求精確最近鄰的場景。但當資料點數量龐大時，無法有效運行
• ANN：雖然可能不回傳精確的點，但在尋找最近點方面更有效率

鑑於當今系統的資料量，ANN 是更務實的解決方案。在我們的視覺搜尋系統中，使用 ANN 尋找相似的圖片 embedding。

對於應用型 ML 職位，面試官可能要求你實作 ANN。兩個廣泛使用的函式庫為 Faiss（Meta 開發）和 ScaNN（Google 開發），各自支援本章描述的大多數方法。建議至少熟悉其中一個函式庫，以更好地理解概念並在 ML 程式碼面試中自信地實作最近鄰搜尋。

其他討論主題#

若面試尾聲有額外時間，可能會被要求討論進階主題。以下列出應準備的主題（尤其是資深職位）：

• 透過識別和封鎖不當圖片來進行內容審核
• 系統中存在的不同偏差（bias），例如位置偏差（positional bias）
• 如何使用圖片 metadata（如標籤）改善搜尋結果（第 3 章 Google Street View Blurring System 有詳細說明）
• 使用物件偵測進行智慧裁切（smart crop）
• 如何使用**圖神經網路（graph neural networks）**學習更好的表徵
• 支援使用文字查詢搜尋圖片（第 4 章詳細討論）
• 如何使用主動學習（active learning） 或人機協作 ML（human-in-the-loop） 更有效地標註資料