← 博客

Visual Search

bytebytego tutorial

dataset

  • 一个query image
  • (n-1)个negative images
  • 一个positive image, 即和query image最像的image.
  • positive image在所有images中的index label.

build dataset

  • human judgement: 人去annotate最像的image
  • user interaction
    • noisy
    • sparse: may not have click data available for lots of the images
  • generate similar images

Offline metrics

Mean reciprocal rank (MRR)

MRR=1/m * sum(1/rank_i)

downside

  • considers only the first relevant item and ignores other relevant items in the list, it does not measure the precision and ranking quality of a ranked list

Recall@k

recall@k= number of relevant items among the top k items in the output list / total relevant items

downside

  • in search engines, the total number of relevant items can be very high. 分母会太大。

Precision@k

Precision@k = number of relevant items among the top k items in the output list / k

downside

  • This metric measures how precise the output lists are, but it doesn’t consider the ranking quality

mAP

AP = Precision@i if i’th item is relevant to the user / total relevant items alt text mAP = AP / # of ranked lists ​ mAP is designed for binary relevances; in other words, it works well when each item is either relevant or irrelevant. For continuous relevance scores, nDCG is a better choice.

nDCG

alt text rank = 模型排出来的位置 rel = 这个位置上的 item 的真实相关性

Visual Search at Pinterest

paper

duplicate image

pinterest blog

  1. 上传了一张新图，想要知道这张图是否是已有图片的duplicate
  2. 等到生成embedding之后，把 embedding 转成 LSH terms
    • embedding = [0.12, -0.44, 0.07, …, 0.31]
    • LSH terms = {term_17, term_203, term_881, term_915, …}
  3. 产生一组duplicate candidates: 用new image的LSH terms去拿到一批对应的images, 比较哪些images和新图的shared LSH terms最多，从多到少排序
  4. 用TensorFlow classifier做精判，score大于某个threshold的，是dup，就放进现有的cluster

cluster

  • 每个cluster代表一组duplicate images
  • every cluster has a cluster head, 即cluster中的代表图片
  • 维护两种关系：Image → canonical image，以及 canonical image → cluster members

manas(search basic)

blog

Indexing

  • doc: 每个manas pin被当作一个doc, 里面包含matching terms和properties
    • matching terms：用来检索。比如red; dress
    • properties：用于 filtering 和 scoring。比如language = en; quality_score = 0.9
  • posting: Each posting records the internal doc ID and a payload.
  • inverted index：倒排索引：term → posting list
    • 有两种两种编码/存储方式
    • dense posting list：适合非常常见的 term，比如red
    • split posting list
  • Forward index: internal_doc_id → actual document

alt text

  • 不同的application有不同的pins,也就是manas doc. 比如普通visual search对应searchable pins, ads对应searchable Ads。他们被统一成manas doc
  • 每个application有自己的partitioner, 把manas doc分成不同的partition
  • index builder把每个partition里面的docs变成index segment

Serving

alt text

  • 一个corpus可以被理解为一个application可搜索到的图片集合. 比如Corpus A = organic Pins, Corpus B = shopping products, Corpus C = ads
  • Query Understasnding把user query变成一个详细的可执行的search plan
  • Blender 负责决定要搜哪些 corpus, 交给这些corpus的root
  • leaf是服务机器/节点，一个leaf可以是一个或多个index segment
  • root 收集每个 leaf 返回的结果,合并, 并 rerank
Leaf

alt text

一个leaf对应一个节点，Operator layer找完candidates之后，交给Model Runner执行ML scoring，然后暴露API给Root

blog

HNSW: Real-time with Embedding

Pinterest blog: manas-hnsw

alt text

  • 每次产生了embedding，该事件进入Kafka
  • Leaf shard 会从 Kafka 消费这些写入事件，然后写到自己的 realtime segment
  • Realtime Segment 是一个内存里的小 index。
    • Realtime Embedding Index: 存 doc_id → embedding
    • Realtime HNSW Graph: 把新 embedding 插入 HNSW 图里，支持 ANN search
  • 一段时间后，Realtime Segment变成sealed realtime segment，不再接受写入
  • Flush操作把内存里的 sealed segment 写到 SSD 上，变成 Static Segment。它不再频繁修改，适合 serving。
Operation
  • deletion: 若要删除一个doc, 给它加一个 in-memory deletion marker。serving 的时候如果搜到了这个 doc，就过滤掉。因为 HNSW 图里直接删除节点会比较麻烦，可能破坏图结构。
  • update: delete old+add new
  • Compaction: 如果static segments太多，就把多个 small static segments合并成更大的 static segment。此时也完成真正的删除

ANN

给定一个 query embedding，在海量 candidate embeddings 里面，快速找出最相似的 top-K。因为candidate太多，不可以算query和所有candidate的similarity，所以牺牲一点精度换速度

HNSW

HNSW 是一种 ANN 方法。它把所有 embeddings 组织成一个图，然后搜索时沿着图走，快速找到附近的点。

The HNSW index is essentially a multiple-layered sparse graph.

每个segment建一张HNSW graph.

  • 每个embedding是一个node，相似的embedding通过边连接
  • 用adjacency list存储
  • multiple-layered，类似skip list
    • 高层：快速跳到大概区域
    • 低层：精细找最近邻

插入新node

  • 找到和它similar的node，先更新adjacency list
  • 先插入到base layer,连接上similar nodes
  • 再往 upper layers 插入

删除node 加 in-memory deletion marker, serving 时过滤掉 deleted nodes, 真正删除留给 compaction

HNSW Graph Compaction

Problem：segment太多时，检索很慢

Add on Merger：

  • 选出最大的segment，复用它的 HNSW graph
  • 把其他小 segments 的 embeddings 插进去
  • 如果有deleted node, 就直接修改它的embedding,变成最近的alive node的embedding。比如Node 5 → Embedding 4
  • 代价是retrieval之后还要dedup

Online Recall Monitoring

recall@K = |ANN topK ∩ exact KNN topK| / K

算global recall, 即每个Leaf上的每个segment都做一次HNSW搜索，返回local top K, 然后root汇总结果，得到global top K.

只对少量 sampled queries 同时跑 ANN + exact KNN， 用来监控当前 realtime HNSW index 的质量。

Filtering

shop the look

Streaming Filtering

Pinterest blog: hnsw streaming filters

alt text

Query分成几个部分：HNSW retrieval + Filters + Scorer + Collector

这个 streaming algorithm 是在一个 Leaf 内部，对它local的每个HNSW segment 做的。

  1. HNSW Iterator：

    • 在 segment 的 HNSW graph 上按 approximate embedding distance 进行 traversal。类似prim算法思想
      • visited set:已经访问过哪些 nodes
      • candidate set:还没访问、但可达的 nodes，按距离排序。dist是query embedding到node embedding的distance
    • 每次输出mini-batch

  2. Filter：

    • 对这批 candidates 检查 metadata filters
    • 比如 safe=true, language=en, country=US, category=fashion, is_shoppable=true
    • 不符合 filter 的 candidates 会被丢掉

  3. Scorer：

    • 对通过 filter 的 candidates 做 scoring
    • 可以是 lightweight scoring，也可以接更复杂的 ranking score

  4. Collector：

    • 把通过 filter 且 scored 的 candidates 放进 result heap
    • heap 维护当前 local top results

  5. Repeat：

    • 如果还没有收集到足够多的 valid results，HNSW iterator 继续 traversal
    • 再 fetch 下一批 candidates
    • 继续 filter → score → collect

  6. Stopping condition：

    • 就算已经收集到Top K个nodes，还要比较candidate set 里未探索的最近 node的dist(query, node)和result heap里的最远距离。如果未探索node不能改善当前效果，就停止。
      • 只考虑符合filter条件的nodes
    • Production latency condition: 到了 time budget 就停，返回当前 best valid results

  7. Merge：

    • 每个 segment 产生 local results
    • Leaf 合并自己多个 segments 的 results
    • Root 再合并多个 Leaves 的 results
    • Blender 再合并多个 corpora 的 results

Amazon

Bringing Multimodality to Amazon Visual Search System

它把 catalog 里的每个商品表示成 product image embedding + product title embedding 的 fused vector，离线建 KNN/ANN index；

online 时 query 如果只有图片，就用 query image embedding 去搜这个 multimodal catalog index。

Pinterest

Pinterest Shop the Look

  • Scene decomposition (detection): 给定一个scene, 检测出所有shoppable regions
  • Candidate retrieval (embedding): uses visual embeddings to retrieve visually similar products from a large shopping corpus.

Evaluation

Coverage: scene closeup volume
用户看到了多少带可购物 object 的 scene

Engagement total: product click-through volume
用户总共点了多少商品

Quality/rate: product click-through rate
商品曝光后被点的比例

Human relevance: E2E Relevance@5
检测出来的 object 对应 top-5 商品像不像

Scene decomposition

ResNeXt101-FasterRCNN + FPN

  1. ResNeXt101 backbone 提取多层 feature maps
  2. FPN 把这些多层 features 变成 feature pyramid
    • FPN 的作用是让每个尺度的 feature 都有比较强的语义信息
  3. RPN 在 pyramid features 上生成 region proposals
  4. RoIAlign 从对应 pyramid level 里取出每个 proposal 的 fixed-size RoI feature
  5. detection head 对每个 RoI 做分类 + bbox regression
  6. 输出 category label + bounding box

Candidate Retrieval

Version 1: Pre-filtering: per-category index

Offline:

  1. 对每个 product image 计算 visual embedding
  2. 给每个 product 分 category
    • 用 in-house Google Product Taxonomy classifier
    • 或者用 merchant-provided category label
  3. 按 category 把 products 分组
  4. 每个 category 单独建一个 nearest-neighbor index

Online:

  1. detector 输出 query object 的 bbox + category label
  2. 对 query object crop 算 visual embedding
  3. 根据 predicted category 选择对应 category index
  4. 只在这个 category index 里做 ANN retrieval

Version 2: LSH ANN + metadata restrictions

  • product image → visual embedding
  • product embedding → LSH tokens
  • inverted index:
    • LSH token → product IDs
    • metadata value → product IDs
  • forward index:
    • product ID → original visual embedding
  • online:
    • query object crop → visual embedding
    • query embedding → LSH tokens
    • query tokens + metadata restrictions form a tree-structured query
    • inverted index retrieves matched-token candidates(ANN)
    • exact embedding distance reranks candidates

Complete the Look

pinterest blog

Input:

  • scene image：一张场景图，比如一个 outfit / 房间 / 街拍
  • product image：一个候选商品，比如一双鞋 / 一个包 / 一把椅子

Output:

  • 一个 distance / score
  • 这个分数表示：这个 product 和这个 scene 搭不搭

VPG

pinterest paper

  1. 找包含query product / similar product 的 real-world scene
  2. 从 scene 里提取其他 shoppable objects alt text

Feature Storage

alt text

KV Store

  1. full-image embedding 整张图的 embedding

  2. object coordinates 图里每个 object 的位置，比如 bbox: x, y, w, h

  3. object embedding 每个 detected object crop 的 embedding

Initial Backfill

  • 用spark做离线批处理，把现有的所有图片，经过object detector, 识别出物品
  • 对每个物品做embedding, 放进KV Store

Incremental updates

  • 对于新图片，用flink做near real-time的stream处理

Online Fallback

  • 有时候用户点了一张新图，但 Flink 还没来得及处理完, 所以KV Store里面没有这张图
  • 系统 fallback 到在线实时计算

Reverse-STL

用一个物体图片去做ANN 找到相似的物体，然后再拿到相似物体属于的原始图片

Forward-STL

  • 对top scene images做object detection
  • 对 scene 里的其他 objects 找 matching product images

Design

以图搜图

  1. Query 理解

区分 query 类型:站内 Pin(embedding 离线算好,直接查表)vs 外部/拍照图(需在线编码,要提一句 Lens 那种 camera→Pin 的 domain shift)。 可选物体检测(Shop the Look 场景):若是杂乱场景图(街拍),先检测出"鞋/包"的 crop 再分别检索。用两步检测省算力——先用便宜的分类门控判断"这图里有没有可购物体",有才跑昂贵检测器,而不是每张图都跑。

  1. 召回(Retrieval)

算 query 的 PinCLIP image embedding,在候选 image-embedding 索引上做 HNSW + 点积(embedding 已 L2 归一化)。 MRL 粗到细:先用 64d 前缀向量高速召回一大批,再用完整 256d 对 top 候选重打分(论文里就是这么做 adaptive retrieval 的)。 int8 量化索引,内存和服务成本砍一半。 并行多路召回:PinCLIP 视觉召回 + 引擎共现图召回(board co-engagement / Pixie 随机游走)+ 文本召回,合并取 ~1k–10k。

  1. 预排(Pre-ranking)

轻量双塔,把万级砍到几百。特征:各路 embedding 相似度 + 便宜的质量/互动先验。

  1. 精排
  • 互动特征(Repin 率、点击、closeup)、元数据(类目、新鲜度、创作者信誉)、个性化(用户历史)。
    • 交叉特征(query×candidate): 把 query 特征和候选特征拼在一起喂进同一个模型
  • 多目标:主目标 pRepin(Pinterest 最核心动作),辅以 pClick、pLongClick,加权融合。技术决策一定绑回 Repin/engagement。
  • PinCLIP 相似度本身就当一个强特征喂进来(论文把 PinCLIP 加进 organic ranker 就拿到 Repin 提升)。
  • 加权 BCE、输出 logit 代表概率(点击或 repin 都行)、XGBoost 或 MLP

或者：MLLM+Prompt

  1. 混合/策略

近重复去重(以图搜图最容易返回一堆几乎一样的图)、多样性(别返回 10 个同款)、新鲜度加权(冷启动——PinCLIP 对 fresh content 特别有效)、trust/safety 过滤。