在 YouTube 等影片分享平台上，影片數量可迅速成長至數十億部。本章設計一個能高效處理此規模內容的影片搜尋系統。如圖 4.1 所示，使用者在搜尋框中輸入文字，系統顯示與該文字最相關的影片。

釐清需求#

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

候選人： 輸入查詢僅限文字，還是也能以圖片或影片搜尋？

面試官： 僅限文字查詢。

候選人： 平台上的內容僅限影片嗎？是否包含圖片或音訊檔案？

面試官： 平台僅提供影片。

候選人： YouTube 搜尋系統非常複雜。我可以假設影片的相關性僅由其視覺內容和相關文字資料（如標題與描述）決定嗎？

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

候選人： 是否有可用的訓練資料？

面試官： 有，假設我們有一千萬組 $\langle$ video, text query $\rangle$ 配對。

候選人： 搜尋系統是否需要支援其他語言？

面試官： 為簡化起見，假設僅支援英文。

候選人： 平台上有多少影片？

面試官： 十億部影片。

候選人： 是否需要個人化結果？是否應依據使用者過去的互動行為，為不同使用者提供不同的排序結果？

面試官： 與推薦系統中個人化至關重要不同，搜尋系統不一定需要個人化結果。為簡化問題，假設不需要個人化。

問題摘要： 設計一個影片搜尋系統，輸入為文字查詢，輸出為與該查詢相關的影片清單。搜尋時同時利用影片的視覺內容與文字資料。訓練資料集為一千萬組 $\langle$ video, text query $\rangle$ 配對。

將問題框架化為 ML 任務#

定義 ML 目標#

使用者期望搜尋系統提供相關且實用的結果。將此需求轉化為 ML 目標的方式之一是：依據影片與文字查詢的相關性進行排序。

指定系統的輸入與輸出#

如圖 4.2 所示，搜尋系統接受文字查詢作為輸入，輸出按相關性排序的影片清單。

選擇合適的 ML 類別#

為判斷影片與文字查詢之間的相關性，我們同時利用視覺內容與影片的文字資料。系統設計的高層概覽如圖 4.3 所示。

以下簡要說明各元件。

Visual search（視覺搜尋）#

此元件接受文字查詢作為輸入，輸出一份影片清單。影片依據文字查詢與其視覺內容的相似度進行排序。

表示學習（Representation learning）是透過處理視覺內容搜尋影片的常用方法。在此方法中，文字查詢與影片分別由兩個編碼器進行編碼。如圖 4.4 所示，ML 模型包含：

• Video encoder：從影片生成 embedding 向量
• Text encoder：從文字生成 embedding 向量

影片與文字之間的相似度分數透過其表示向量的內積（dot product）計算。

為了排序與文字查詢在視覺與語義上相似的影片，我們在 embedding 空間中計算文字與每部影片的內積，再依據相似度分數進行排序。

Text search（文字搜尋）#

圖 4.5 展示當使用者輸入文字查詢「dogs playing indoor」時，文字搜尋的運作方式：標題、描述或標籤與查詢最相似的影片會作為輸出呈現。

倒排索引（Inverted index）是建構文字搜尋元件的常用技術，能在資料庫中進行高效的全文檢索。由於倒排索引不基於機器學習，因此沒有訓練成本。企業常用的搜尋引擎為 Elasticsearch，它是一個可擴展的搜尋引擎與文件儲存系統。更多細節請參考。

資料準備#

Data engineering（資料工程）#

由於已有標註資料集用於訓練與評估模型，因此不需要額外的資料工程。表 4.1 為標註資料集的範例。

表 4.1：標註資料集

Feature engineering（特徵工程）#

幾乎所有 ML 演算法僅接受數值輸入。文字和影片等非結構化資料需在此步驟轉換為數值表示。以下說明如何為模型準備文字與影片資料。

準備文字資料#

如圖 4.6 所示，文字通常透過三個步驟表示為數值向量：文字正規化、分詞（tokenization）與 tokens 轉 IDs。

以下逐一說明各步驟。

Text normalization（文字正規化）#

文字正規化（又稱文字清理）確保詞彙與句子的一致性。例如，同一個詞可能有不同拼寫方式：「dog」、「dogs」和「DOG!」指的是同一事物。句子也是如此，例如：

• “A person walking with his dog in Montréal !”
• “a person walks with his dog, in Montreal.”

兩句意思相同，但標點與動詞形式不同。常見的文字正規化方法包括：

• Lowercasing：將所有字母轉為小寫，不改變詞義
• Punctuation removal：移除標點符號（句號、逗號、問號、驚嘆號等）
• Trim whitespaces：移除前導、尾隨及多餘空白
• Normalization Form KD（NFKD）：將組合字形分解為簡單字形的組合
• Strip accents：移除重音符號，例如：Màlaga → Malaga、Noël → Noel
• Lemmatization and stemming：為一組相關詞形找出標準代表詞，例如：walking、walks、walked → walk

Tokenization（分詞）#

Tokenization 是將一段文字拆分為更小單位（稱為 token）的過程。主要有三種類型：

• Word tokenization：依據特定分隔符將文字拆分為單詞。例如 “I have an interview tomorrow” 變為 [“I”, “have”, “an”, “interview”, “tomorrow”]
• Subword tokenization：將文字拆分為子詞（或 n-gram 字元）
• Character tokenization：將文字拆分為單一字元

不同 tokenization 演算法的細節通常不是 ML 系統設計面試的重點。若有興趣深入了解，請參考。

Tokens 轉 IDs#

取得 token 後，需將其轉換為數值（IDs）。有兩種方式：

• Lookup table（查找表）
• Hashing（雜湊）

Lookup table： 每個唯一 token 對應一個 ID，並建立查找表儲存這些 1:1 的映射。圖 4.7 為映射表範例。

Hashing： 又稱「feature hashing」或「hashing trick」，是一種記憶體高效的方法，使用雜湊函數取得 ID，不需維護查找表。圖 4.8 展示如何使用雜湊函數將詞彙轉換為 ID。

兩種方法的比較如下：

表 4.2：Lookup table vs. Feature hashing

準備影片資料#

圖 4.9 為原始影片預處理的典型流程。

模型開發#

模型選擇#

如「將問題框架化為 ML 任務」一節所述，文字查詢由 text encoder 轉換為 embedding，影片由 video encoder 轉換為 embedding。本節探討各編碼器的可能模型架構。

Text encoder（文字編碼器）#

典型 text encoder 的輸入與輸出如圖 4.10 所示。

Text encoder 將文字轉換為向量表示。例如，兩個語義相似的句子，其 embedding 也會更接近。建構 text encoder 有兩大類方法：統計方法與基於 ML 的方法。

統計方法#

這些方法依靠統計將句子轉換為特徵向量。兩種常見的統計方法為：

• Bag of Words（BoW）
• Term Frequency Inverse Document Frequency（TF-IDF）

BoW： 將句子轉換為固定長度向量，透過建立矩陣（行代表句子、列代表詞彙索引）來建模句子中的詞彙出現次數。圖 4.11 為 BoW 範例。

圖 4.11：不同句子的 BoW 表示

BoW 簡單且計算速度快，但有以下限制：

• 不考慮詞序：例如 “let’s watch TV after work” 與 “let’s work after watch TV” 會有相同的 BoW 表示
• 無法捕捉語義：兩個意思相同但用詞不同的句子會有完全不同的表示
• 表示向量稀疏：向量大小等於所有唯一 token 的數量，通常非常大，因此大部分元素為零

TF-IDF： 一種數值統計方法，反映某個詞對文件集合中某份文件的重要程度。TF-IDF 建立與 BoW 相同的句子-詞彙矩陣，但根據詞頻進行正規化。數學細節請參考。

由於 TF-IDF 對高頻詞給予較低權重，其表示通常優於 BoW。但仍有以下限制：

• 新增句子時需重新計算詞頻以進行正規化
• 不考慮詞序
• 無法捕捉語義
• 表示向量稀疏

統計方法通常較快，但無法捕捉句子的上下文語義，且表示向量稀疏。基於 ML 的方法可解決這些問題。

基於 ML 的方法#

在這些方法中，ML 模型將句子轉換為有意義的 word embedding，使得兩個 embedding 之間的距離反映對應詞彙的語義相似度。例如，語義相似的詞（如 “rich” 與 “wealth”）在 embedding 空間中會靠近彼此。圖 4.12 為 2D embedding 空間中的簡單視覺化。

三種常見的 ML 方法將文字轉換為 embedding：

• Embedding（lookup）layer
• Word2vec
• Transformer-based 架構

Embedding（lookup）layer： 使用 embedding 層將每個 ID 映射到一個 embedding 向量。圖 4.13 為範例。

Embedding 層是一種簡單有效的方法，可將稀疏特徵（如 ID）轉換為固定大小的 embedding。後續章節將有更多使用範例。

Word2vec： Word2vec 是一系列用於產生 word embedding 的相關模型。這些模型使用淺層神經網路架構，利用詞彙在局部上下文中的共現關係學習 word embedding。訓練階段中，模型學習從周圍詞彙預測中心詞。訓練完成後，模型能將詞彙轉換為有意義的 embedding。

基於 Word2vec 的兩個主要模型為 Continuous Bag of Words（CBOW） 和 Skip-gram。圖 4.14 展示 CBOW 的高層運作方式。若有興趣，請參考。

儘管 Word2vec 和 embedding 層簡單有效，近年基於 Transformer 的架構已展現出更優異的結果。

Transformer-based 模型： 這些模型在將詞彙轉換為 embedding 時會考慮句子中的上下文。與 Word2vec 不同，它們會根據上下文為同一詞彙產生不同的 embedding。

圖 4.15 展示 Transformer-based 模型的運作：接受一個句子（一組詞彙）作為輸入，為每個詞彙產生一個 embedding。

Transformer 在理解上下文與產生有意義的 embedding 方面非常強大。BERT、GPT-3 和 BLOOM 等模型已展示 Transformer 在各種自然語言處理（NLP）任務中的潛力。本設計中，我們選擇 BERT 等 Transformer-based 架構作為 text encoder。

在某些面試中，面試官可能會要求深入探討 Transformer-based 模型的細節。更多內容請參考。

Video encoder（影片編碼器）#

影片編碼有兩種架構選項：

• Video-level 模型
• Frame-level 模型

Video-level 模型處理整部影片以建立 embedding，如圖 4.16 所示。模型架構通常基於 3D convolution 或 Transformer。由於模型處理整部影片，計算成本較高。

Frame-level 模型的運作方式不同，可透過三個步驟從影片提取 embedding：

1. 預處理影片並取樣影格（frame）
2. 對取樣的影格執行模型以建立 frame embedding
3. 聚合（例如取平均）frame embedding 以生成 video embedding

由於此模型在影格層級運作，通常更快且計算成本更低。然而，frame-level 模型通常無法理解影片的時間面向（如動作與運動）。在實務中，當影片的時間理解不是關鍵時，frame-level 模型較常被採用。本設計選用 ViT 等 frame-level 模型，原因如下：

• 提升訓練與推論速度
• 減少計算量

模型訓練#

為訓練 text encoder 與 video encoder，我們使用 contrastive learning（對比學習）方法。若有興趣深入了解，請參考第 2 章「Visual Search System」中的「模型訓練」一節。

圖 4.18 說明模型訓練期間如何計算損失。

評估#

離線指標#

以下是搜尋系統常用的離線指標，逐一分析其適用性。

Precision@k 與 mAP#

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

在評估資料集中，一個文字查詢僅關聯一部影片，意味著 precision@k 公式的分子最多為 1，導致 precision@k 值偏低。例如，即使將相關影片排在第一位，precision@10 也僅為 0.1。因此，precision 相關指標（如 precision@k 和 mAP）幫助有限。

Recall@k#

衡量搜尋結果中相關影片數量與相關影片總數的比率。

$\text { recall@k }=\frac{\text { Number of relevant videos among the top } k \text { videos }}{\text { Total number of relevant videos }}$

如前所述，「相關影片總數」始終為 1，因此 recall@k 可簡化為：

recall@k = 1（若相關影片在前 k 名中），否則為 0

優點：

• 能有效衡量模型為給定文字查詢找到相關影片的能力

缺點：

• 依賴 k 值的選擇，選擇合適的 k 可能具有挑戰性
• 當相關影片不在前 k 名時，recall@k 始終為 0。例如，模型 A 將相關影片排在第 15 位，模型 B 排在第 50 位，若使用 recall@10，兩者皆為 0，即使模型 A 明顯較優

Mean Reciprocal Rank（MRR）#

此指標透過對每個搜尋結果中第一個相關項目的排名取倒數平均來衡量模型品質：

$M R R=\frac{1}{m} \sum_{i=1}^m \frac{1}{\operatorname{rank}_i}$

MRR 解決了 recall@k 的不足之處，適合作為離線指標。

線上指標#

在線上評估中，企業會追蹤各種指標。以下是幾個最重要的指標：

• Click-through rate（CTR）
• Video completion rate（影片完整觀看率）
• Total watch time of search results（搜尋結果總觀看時間）

CTR： 衡量使用者點擊檢索到影片的頻率。主要問題是 CTR 無法追蹤被點擊的影片是否與使用者相關。儘管如此，CTR 仍是有價值的指標，因為它顯示了多少人點擊了搜尋結果。

Video completion rate： 衡量搜尋結果中有多少影片被使用者觀看至結束。問題在於使用者可能只觀看部分影片但仍認為其相關。此指標單獨使用無法反映搜尋結果的相關性。

Total watch time of search results： 追蹤使用者觀看搜尋結果影片的總時間。若搜尋結果相關，使用者傾向花更多時間觀看。此指標是衡量搜尋結果相關性的良好指標。

服務架構#

在推論時，系統針對給定的文字查詢顯示排序後的相關影片清單。圖 4.19 為簡化的 ML 系統設計。

以下詳細說明各 pipeline。

Prediction pipeline（預測管線）#

此管線包含以下元件：

• Visual search（視覺搜尋）
• Text search（文字搜尋）
• Fusing layer（融合層）
• Re-ranking service（重新排序服務）

Visual search： 此元件對文字查詢進行編碼，並使用最近鄰服務找到與文字 embedding 最相似的影片 embedding。為加速最近鄰搜尋，我們使用近似最近鄰（ANN）演算法，詳見第 2 章「Visual Search System」。

Text search： 使用 Elasticsearch，找到標題和標籤與文字查詢重疊的影片。

Fusing layer： 將前一步驟中兩份不同的相關影片清單合併為一份新清單。

融合層可透過兩種方式實作：

• 加權分數加總：根據預測相關性分數的加權總和重新排序影片（較簡單）
• 額外模型：採用另一個模型進行重新排序（需額外訓練成本，推論速度也較慢）

本設計採用前者。

Re-ranking service： 此服務透過納入業務邏輯與政策來調整排序後的影片清單。

Video indexing pipeline（影片索引管線）#

使用已訓練的 video encoder 計算影片 embedding，然後建立索引。這些索引後的 embedding 供最近鄰服務使用。

Text indexing pipeline（文字索引管線）#

使用 Elasticsearch 為標題、手動標籤與自動生成的標籤建立索引。

通常使用者上傳影片時會提供標籤以幫助辨識影片。但若使用者未手動輸入標籤怎麼辦？一個方案是使用獨立模型生成標籤，稱為 auto-tagger。此元件在影片沒有手動標籤時特別有價值。自動生成的標籤可能比手動標籤更具雜訊，但仍然有價值。

其他討論要點#

在結束本章之前，需注意我們已簡化了影片搜尋系統的設計。實務中系統遠比此複雜。可能的改進包括：

• 使用多階段設計（candidate generation + ranking）
• 使用更多影片特徵，如影片長度、熱門程度等
• 不依賴標註資料，而是利用互動行為（如點擊、按讚等）建構與標記資料，實現模型持續訓練
• 使用 ML 模型尋找與文字查詢語義相似的標題與標籤，結合 Elasticsearch 以提升搜尋品質

若面試結束時還有時間，以下是一些額外的討論要點：

• 搜尋系統中的重要主題是 query understanding（查詢理解），如拼寫修正、查詢類別辨識與實體辨識。如何建構查詢理解元件？
• 如何建構多模態系統處理語音與音訊以改善搜尋結果
• 如何將此系統擴展至支援其他語言
• 最終輸出中的近似重複影片可能負面影響使用者體驗。如何偵測近似重複影片以在顯示結果前移除？
• 文字查詢可分為 head、torso 和 tail 查詢。各類型常用的不同方法為何？
• 如何在產生輸出清單時考慮熱門程度與新鮮度？
• 真實世界搜尋系統的運作方式