Large-Scale Image Retrieval with Elasticsearch.md

CNN特征的文本表示方法

基于排列的索引

• 基本思想：一个对象可以用一系列参考对象的排列表示

• 形式化定义：

  • 一系列参照物 $ P = \lbrace p_1 ... p_n \rbrace \in D $， D是一个域，距离$ d: D\times D \to R $
  • 一个对象o基于排列的表示 $\Pi_{o} = ( \Pi_{o}(1), ..., \Pi_{o}(n) ) $， 按对象o到$p_i$的距离从小到大排列, $ \Pi_{o}(i) $是排在第i位的参考对象的索引
  • 等价的索引排列为 $\Pi_{o}^{-1} = ( \Pi_{o}^{-1}(1), ..., \Pi_{o}^{-1}(n) )$， $\Pi_{o}^{-1} (i)$是每个参考对象的Rank

• 在DL向量中的应用

  • DL高层向量的每个维度都是一种视觉概念
  • 直接把每个维度看作参考对象，按激活值从大到小排序
  • 向量取Top K表示，相当于用用最明显的特征来表示图片
  • 用CRelu来保存向量中的负值携带的信息

• 基于$ \Pi_{o}^{-1} $ 构建转为文本倒排索引

  • 只取Top K进行编码，每个维度用符号表示$ \tau_i $
  • 为直接使用Elasticsearch，使之能计算tf-idf，令:
    • Top 1的符号出现K次
    • Top 2的符号出现K-1次
    • Top 3的符号出现K-2次
    • ...
    • Top K的符号出现1次

• 计算实例

  • $ f_v = [0.1, -0.3, -0.4, 0, 0.2] $
  • $ f_v^+ = f_v = [0.1, -0.3, -0.4, 0, 0.2] $
  • $ f_v^- = -f_v = [-0.1, 0.3, 0.4, 0, -0.2] $
  • $ f_v = [f_v^+, f_v^-] = [0.1, -0.3, -0.4, 0, 0.2, -0.1, 0.3, 0.4, 0, -0.2] $
  • $ Relu(f_v) = [0.1, 0, 0, 0, 0.2, 0, 0.3, 0.4, 0, 0] $
  • $ \Pi_{f_v}^{-1} = [4, 5, 6, 7, 3, 8, 2, 1, 9, 10] $
  • 取K=4: $ [4, 5, 5, 5, 3, 5, 2, 1, 5, 5] $
  • 编码为文本：$ \tau_1 \tau_5 \tau_5 \tau_7 \tau_7 \tau_7 \tau_8 \tau_8 \tau_8 \tau_8 $

RMAC提取图片特征向量

• 将图片的几个区域聚合成一个稠密压缩的全局图像表示
• 详见RMAC

三种排列的距离函数

• Spearman Rho Distance
  • 对应位置差的平方和
  • $ \sum_k(X_{ik} - X_{jk})^2 $
• Kendall Tau
  • 两序列中大小顺序不同的pair数，可以画成二分图，图中交点的个数
• Spearman Footrule Distance
  • 对应位置差的绝对值
  • $ \sum_k|X_{ik} - X_{jk}| $

PQ量化

• 原向量切分成M个子向量
• 每个子向量
  • K-Means学习各子向量集合CodeBook(需预训练)
  • 各子向量用K-Means得到的中心表示

稀疏

• 每个索引的倒排表不要过长，希望数据能均匀分布在每个倒排项上
• 本文用4096大小的词向量相当于词典的总大小为4096，对于10亿文档而言每个词项任然存在分到大量的文档的问题

References

• Large-Scale Image Retrieval with Elasticsearch