简介

老师开的课，主要是多媒体信息检索。作下记录。

Lec 3

检索改进

衡量文档相似性有两种常用的方法：

欧式距离-L2

$d(q,d_j)=\sqrt{\sum_i(w_{iq}-w_{ij})^2}$

余弦距离

$cos(q,d_j)=\frac{\sum_i w_{iq}·w_{ij}}{\sqrt{\sum_iw_{iq}^2}·\sqrt{\sum_i w_{ij}^2}}$

假设当前有一倒排表，且查询使用欧式距离计算相似性：

当有一查询时，需要对数据库中所有文档计算距离：

改进的方法：

数据库中的文档$W_ij$被分为两组，G1：出现在查询$q$中，G2：不出现在查询$q$中
预先计算数据库中所有文档的平方和，$W_j=\sum_iw_{ij}^2$

则：

$d^2(q,d_j)=\sum_{w_i \in G1}(w_{iq}-w_{ij})^2+W_j-\sum_{w_i \in G1}w_{ij}^2$

能加快检索速度。

Lec 4

Pagerank

更高的权重（pagerank）被分配给具有许多向内链接的页面
注意，向外链接不会影响页面的排名

建立模型

给出4个网页，以及它们之间的超链接。计算每个页面的pagerank如下，所有页面的$PR(·)$初始化为0.25

$PR(A)=\frac{PR(B)}{L(B)}+\frac{PR(C)}{L(C)}+\frac{PR(D)}{L(D)}$

其中$PR(·)$是当前的权重，$L(·)$是指向该节点的其他节点的出度数。

$PR(A)=\frac{0.25}{1}+\frac{0.25}{1}+\frac{0.25}{3},\\ PR(B)=\frac{0.25}{3}, \\ PR(C)=\frac{0.25}{3}, \\ PR(D)=0$

这样计算有一个缺点，一旦有一个节点没有向内链接，则它的权重会为0，几次迭代之后，其他被它所指的节点的权重也会为0。

所以有了下面的改进：

$PR(A)=(\frac{0.25}{1}+\frac{0.25}{1}+\frac{0.25}{3})·d+\frac{1-d}{N},\\ PR(B)=(\frac{0.25}{3})·d+\frac{1-d}{N}, \\ PR(C)=(\frac{0.25}{3})·d+\frac{1-d}{N}, \\ PR(D)=0·d+\frac{1-d}{N}$

评价指标

True Positive (TP)：相关文档被检索到的数量
False Negative (FN)：相关文档没被检索到的数量
False Positive (FP)：不相关文档被检索到的数量
True Negative (TN)：不相关文档没被检索到的数量
给定前$k$个检索结果，数据库中相关文档的数量为$R$，
$Recall = \frac{TP}{R} \\ Precision = \frac{TP}{K}$
F-measure定义为，
$F-measure=\frac{2·Recall·Precision}{Recall+Precision}$

在实际情况中，用户对准确率更加敏感。

Average Precision（AP）定义为，

$AP(i)=\frac{\sum_1^i(1)}{i}$

mean Average Precision（mAP）定义为，

$mAP=\frac{\sum_{i=1}^KAP(i)}{K}$

Lec 5

k-means

给定$N$个项和$K$，

选择$K$个项作为初始中心
1. 将所有项分配到最近的聚类中心（形成分区）
2. 用每个区域的所有项的平均值（或质心）更新每个中心
循环直到聚类中心不再改变

复杂度为$O(K·N·D)$，其中$D$为数据项的维数。$K$在该算法中是一个关键参数。而且该算法只能得到次优解，所有聚类算法都是如此。

k-means++

D. Arthur and S. Vassilvitskii, “k-means++: the advantages of careful seeding”,
18th ACM-SIAM symposium on Discrete algorithms, 2007.

动机：尝试优化聚类中心的初始化
想法：尽量选择彼此相距很远的点
目标：更好地适应数据分布

给定$N$个项和$K$，

随机选择一个项作为第一个聚类中心
重复以下步骤$K-1$次
1. 计算每个项$x$到现有中心的距离
2. 取每个项到其最近的中心的距离为$D(x)$
3. 选择一个新的聚类中心，选择概率为$D^2(x)$
4. 把这个新的聚类中心加入到现有的聚类中心
按照常规程序完成k-means聚类

k-means++只是修改了初始化阶段，这会导致更快的收敛，更好地适应数据分布。但该初始化的计算复杂度为$O(K·N·D)$，增加了大量的运算，减慢了速度。

boost k-means

Zhao W L, Deng C H, Ngo C W. k -means: a revisit[J]. Neurocomputing, 2018.

动机

k-means的复杂度为$O(n·d·k·t)$，当这四者很大时，计算速度会下降很多。

解决的方法：

$n$不可改变
$d$不可改变
可以采用分层聚类将$k$减小为$log(k)$
可以收敛得更快，导致$t$的减小

k-means的数学模型

$min\sum_{q(x_i)=r}||C_r-x_i||^2$

其中$q(x_i)$返回$x_i$最近的聚类中心。

k-means的新形式

定义$D_r=\sum_{x_i \in S_r}$和$n_r=|S_r|$，$C_r$是聚类集群$S_r$的中心。

$min \sum_{q(x_i)=r}||C_r-x_i||^2,变为\\ max \space \mathcal{I}_1=\sum_{r=1}^k\frac{D_r'D_r}{n_r}$

有了以上新的目标方程，采用贪心策略最大化（best）：

随机选择$x_i$，$x_i\in S_u$
对每个$S_v$，计算$\Delta \mathcal{I}_1$，当$x_i$从类别$S_u$移动到$S_v$

$\begin{align*} \Delta \mathcal{I}_1(x_i)&=\frac{(D_v+x_i)'(D_v+x_i)}{n_v+1}-\frac{(D_u-x_i)'(D_u-x_i)}{n_u-1}\\ &=\frac{D_v'D_v+2x_i'D_v+x_i'x_i}{n_v+1}-\frac{D_u'D_u-2x_i'D_u+x_i'x_i}{n_u-1} \end{align*}$

将$x_i$移动到$\Delta \mathcal{I}_1$最高的$S_v$

转化成这种新形式之后，是能够证明收敛的，k-means是否收敛的问题终于被解决了。

大体框架

为$x_i \in X$随机分配标签
计算$D_1,…,D_r,…,D_k$和$\mathcal{I}_1$
重复
1. 对于每个$x_i \in X$
  1. 找到$\Delta \mathcal{I}_1(x_i)$的$S_v$
  2. 如果$\Delta \mathcal{I}_1(x_i)>0$
    1. 将$x_i$移动到$S_v$
  3. 退出
2. 退出
退出

“best”策略的boost k-means会比普通的k-means更快，因为少了初始化的步骤。

另一种策略：fast

每次不必找到最大的$\Delta \mathcal{I}_1$，只要找到有一个$\Delta \mathcal{I}_1>0$，就向那里移动。

“fast”收敛到较低的偏离度，但需要更多的迭代数
“best”在每次迭代中收敛更快但更慢

对比

分层boost k-means

尽管boost k-means会比普通的k-means更快，但它们还是同一个计算复杂度$O(n·d·k·t)$。

可以以分层的方式执行boost k-means，

将$X$分为2个类
选择其中一个的类集群
将该类集群分成2个类
重复步骤2-3，直到类的个数达到$k$

分层boost k-means的复杂度为$O(n·d·log(k)·\bar t)$，计算复杂度比原本小了很多，但是精度也会降低很多。

各方法评价

$\bar E = \frac{\sum_{q(x_i)=r}||C_r-x_i||^2}{n}$

Lec 7

Harris&Hessian旋转不变性

综合转载以下文章：

Harris角点检测是一种非常经典而有效的角点检测方法，它主要是考虑到人眼对角点的识别通常是在一个局部的小区域或小窗口完成的。如果是在角点位置上的窗口，那么其在各个方向上移动，都会使区域内灰度发生了较大的变化。如果只在一个方向上移动时发生较大变化，那么这点需要是在直线上；如果在各个方向上移动都没有发生变化，那么窗口可能位于平滑的区域。

这里的移动发生变化是由窗口平移后的自相似性来衡量的。

$c(x,y;\Delta x,\Delta y)=\sum_{(u,v)\in W(x,y)}w(u,v)(I(u,v)-I(u+\Delta x,v+\Delta y))^2$

可以简化为：

$c(x,y;\Delta x,\Delta y) \approx \sum_w(I_x(u,v)\Delta x+I_y(u,v)\Delta y)^2=[\Delta x,\Delta y]M(x,y)\begin{bmatrix}\Delta x\\\Delta y\end{bmatrix}$

这其中Harris二阶矩表示为：

$M(x,y)=\sum_w \begin{bmatrix}I_x(x,y)^2 & I_x(x,y)I_y(x,y)\\I_x(x,y)I_y(x,y) & I_y(x,y)^2\end{bmatrix}=\begin{bmatrix}\sum_w I_x(x,y)^2 & \sum_w I_x(x,y)I_y(x,y)\\\sum_w I_x(x,y)I_y(x,y) &\sum_w I_y(x,y)^2\end{bmatrix}=\begin{bmatrix}A & C\\C &B\end{bmatrix}$

Hessian二阶矩表示为：

$M(x,y)=\begin{bmatrix}I_{xx}(x,y) & I_x(x,y)I_y(x,y)\\I_x(x,y)I_y(x,y) & I_{yy}(x,y)\end{bmatrix}=\begin{bmatrix}\lambda_{max} & ·\\· &\lambda_{min}\end{bmatrix}$

由此可以将自相关函数视为一个椭圆函数：

$c(x,y;\Delta x,\Delta y) \approx A\Delta x^2+2C\Delta x\Delta y+B\Delta y^2$

这个椭圆函数曲线实际上是指这个点附近的等相关线，椭圆曲线上的点同中心点的具有相同的相关程度，其长轴和短轴（可以由二阶矩的特征值来表示）表明了变化快慢的方向。椭圆的方向由$M(x,y)$的特征矢量来决定。椭圆的大小求取如下图所示：

这里在迭代椭圆过程中，通过 $M(x,y)$ 获取当前尺度下的椭圆长短半轴，随后还要进行尺度参数的归一化：即长短半轴要按比例乘以尺度的系数进行椭圆的放大或者缩小。因此迭代收敛之后的椭圆大小几乎一致。　　

当迭代收敛多尺度归一化椭圆之后，会存在许多接近的椭圆个数。通过非极大值抑制策略进行筛选出最优的仿射变换估计椭圆。最后，根据椭圆的长短半轴进行区域的仿射归一化插值还原（拉伸或者压缩取决于椭圆长短轴）。一般采取椭圆长轴经过插值到短轴的等比例大小。

1. Initialize T=E
2. Caculate M=H(x,y,σ)
3. Normalize region around (x,y) with M^−1
4. Check e1/e2≈1
5. T=T·M^−1
6. Go to Step 2 until e1/e2 close to 1

显然，若是角点的话，那么各方向的变化都比较大，即二阶矩 $M(x,y)$ 的特征值都较大，且接近相等。可以通过角点响应值cornerness来判断角点，计算每一像素点的角点响应值，并在域内进行非最大值抑制，找到局部最大值即为其角点。

$R=\text{det}M-\alpha(\text{trace}M)^2$

这里的计算主要是用到了二阶矩 $M(x,y)$，使用了微分算子对像素点进行微分运算，而微分运算对图像密度的拉升或收缩和对亮度的抬高或下降不敏感。所以对亮度和对比度的仿射变换并不改变Harris响应的极值点出现的位置，但是，由于阈值的选择，可能会影响角点检测的数量，同时角点判断主要是通过二阶矩 $M(x,y)$ 的特征值大小来判断的，特征值的方向角完全没有影响，所以Harris方法具有了仿射不变性。

SIFT镜像不变性

在提取SIFT特征之前，进行翻转。

涉及到绕哪根轴翻转，任选一个方向即可，因为在校准主方向之后，只有翻转和不翻转两种可能性。而翻不翻转由计算出的主角量决定，不知道咋翻译好，就是计算图像的中心点到所有特征点的切线方向，得到切线的主方向，设置所有图像的切线主方向朝向顺时针时，即翻转。

实际使用中，一张图像通过翻转得到另外一张图像，两张图像一起进行匹配，判断效果好坏。

Lec 8

图像检索结构的介绍，包括BoVW、HE和VLAD。具体参考我的相关博客。

Lec 9

Overview

即刻响应，要求复杂度 $O(D^{1/c}·\text{log}N)$，其中 $D$表示维数，$N$表示个体数， $c>1$。

根据 $D$ 和 $N$ 大小，分成以下四个问题：

稀疏一般为维数 $D$ 中，非零维数小于10%
高维一般为维数 $D\ge 10$
LD：X-Y，RGB和HSV；LS：时空数据，如GIS
HD：SIFT，VLAD；HS：文本文件，BoVW
LD和LS用KD-Tree解决；HS用倒排解决
主要研究集中在HD

Problem

问题一般分为两种：

$k-nn$，搜索出 $k$ 个最近邻的数据返回（主要研究）
$r-nn$，搜索出查询实例周围半径 $r$ 内的数据（少数）

Distance

Cosine distance & Euclidean distance

余弦距离：$d(x,y)=\frac{x^Ty}{||x||_2||y||_2}$，当用于计算欧式距离的两个向量 $x$ 和 $y$ 是经过正则化时，则欧式距离与余弦距离等价。

Mahalanobis distance

马氏距离，是为了解决各个维度中数据分布不均的问题，可以看成先将数据分布不均的椭圆转换成圆，再计算欧式距离。

给定一组数据，可以估计协方差矩阵
特征向量与椭圆轴线重合，特征值作为归一化因子处理
$d(x,y)=\sqrt{(x-\mu)^T\Sigma^{-1}(y-\mu)}$

Other distance spaces

对于这些非欧几里得空间，目前还没有有效的距离度量方法
很难计算出一种通用的距离测量方法

History

KD-Tree

具体参考我的博客 K-D TREE算法原理及实现

检索不能像预期的那样有效
在最坏的情况下，它几乎需要遍历整棵树
平衡KD树可以缓解这个问题
数据按照每次的轴差进行划分，而最近邻由l1或l2范数计算，最近邻不一定位于同一分支
对KD树的改进：$R$ 树试图将候选点分组到彼此接近的地方（不仅仅是一维）

FLANN

速度高，精度低。

分层量化

每个样本被量化到每个层次结构中最接近的词汇
每个样本沿着一条路径（从根到叶）量化
将查询与每层的单词进行比较
排名前 $k$ 的最接近的候选点被保留
将搜索扩展到这些最接近的候选点所涵盖的下一个点的词汇
缺点：需要大量内存

LSH

具体参考我的博客局部敏感哈希(Locality-Sensitive Hashing, LSH)。

一个LSH的简单实现：

随机取一个正则化的向量 $a$
对于一个向量 $h$，计算 $a$ 与 $h$ 的 $arccos$，则能确定 $a$ 在 $h$ 的左边或右边，即分配出 0 和 1
重复1~2步，能得到 $m$ 维的哈希编码

缺点：

不支持精确的范围搜索和Top k搜索，且精度低
对于非欧空间和非LP空间，很难设计好合适的哈希函数

PQ

具体参考我的博客 Product Quantization乘积量化。

Nearest Neighbor Descent

流形

转载：机器学习算法总结(十二)——流形学习（Manifold Learning）

什么是流形

流形学习的观点：认为我们所能观察到的数据实际上是由一个低维流行映射到高维空间的。由于数据内部特征的限制，一些高维中的数据会产生维度上的冗余，实际上这些数据只要比较低的维度就能唯一的表示。所以直观上来讲，一个流形好比是一个 $d$ 维的空间，在一个m维的空间中（$m>d$）被扭曲之后的结果。需要注意的是流形并不是一个形状，而是一个空间。举个例子来说，比如说一块布，可以把它看成一个二维的平面，这是一个二维的空间，现在我们把它扭一扭（三维空间），它就变成了一个流形，当然不扭的时候，它也是一个流形，欧式空间是流形的一种特殊情况。如下图所示

再比如对于一个球面上的一点（其实就是三维欧式空间上的点），可以用一个三元组来表示其坐标：

$\begin{align*} x & = x_0 + r\text{ sin}\theta \text{ cos}\varphi \\ y & = y_0 + r\text{ sin}\theta \text{ sin}\varphi \\ z & = z_0 + r\text{ cos}\theta \end{align*}$

但事实上这三维的坐标只由两个变量θ和φ生成的，也可以说成是它的自由度是2，也正好对应了它是一个二维的流形。

流形具有在局部与欧式空间同胚的空间，也就是它在局部具有欧式空间的性质，能用欧式距离来进行距离计算。这就给降维带来了很大的启发，若低维流形嵌入到了高维空间，此时样本在高维空间的分布虽然复杂，但在局部上仍具有欧式空间的性质，因此可以在局部建立降维映射关系，然后再设法将局部映射关系推广到全局。而且当数据被降维到二维和三维时，就可以进行可视化，因此流形学习也可以被用于可视化。

等度量映射（ISOMAP）

首先介绍下MDS算法，MDS算法的核心思想：找到一个低维空间使得样本间的距离在高维空间和低维空间基本一致。所以MDS算法是利用样本间的相似性来保持降维后的输出结果与降维前一致（此种算法的计算两很大），然而对于高维空间直接计算样本之间的直线距离（欧式距离）是具有很大的误导性的。举个例子，计算地球上南极到北极之间的距离，可以直接计算这两点之间的距离，但是这种距离是毫无意义的（你总不能从南极打个洞到北极吧），因此引入了测地距离，测地距离才是两点之间的本真距离。具体如下如所示

然而如何计算两点之间的测地距离呢，毕竟从南极到北极有很多条路径，不过我们要求的是从南极到北极之间的最短的测地距离。这时就可以利用流形在局部上与欧式空间同胚这个性质，对于每个点基于欧式距离找出其最近邻点，然后就能建立一个近邻连接图，于是计算两点之间的测地距离的问题，就转变成为计算近邻连接图上两点之间的最短路径问题（Dijkstra算法）。

那么什么是Isomap算法呢？其实就是MDS算法的变种，其思想和MDS一样，只不过在计算高维空间的距离时是采用测地距离的，而不是无法真实的表达两点之间的欧式距离。具体算法流程如下（来源：机器学习周志华版）

Isomap算法是全局的，它要找到所有样本全局的最优解，当数据量很大时或者样本维度很高时，计算量非常大。因此更常用的算法是LLE（局部线性嵌入），LLE放弃所有样本全局最优的降维，只是通过保证局部最优来降维。

局部线性嵌入（LLE）

局部线性嵌入的思想：只是试图去保持领域内样本之间的关系。具体如下图所示，样本从高维空间映射到低维空间后，各个领域内的样本之间的线性关系不变。

即样本点 $x_i$ 的坐标能通过它的领域样本 $x_j$，$x_l$，$x_k$ 重构出来，而这里的权值参数在低维和高维空间是一致的。

$x_i = w_{ij}x_j + w_{ik}x_k + w_{il}x_l$

LLE算法可以分为两步：

第一步根据领域关系计算出所有的样本的领域重构系数 $w$，也就是找出每一个样本和其领域内的样本之间的线性关系

$\text{min}_{w_1,w_2,...,w_m} \sum_{i=1}^m ||x_i-\sum_{j\in Q_i}w_{ij}x_j||^2 \\ s.t.\sum_{j \in Q_i}w_{ij}=1$

其中 $x_i$ 和 $x_j$ 均为已知，令 $C_{jk}=(x_i-x_j)^T(x_i-x_k)$，$w_{ij}$ 有闭式解。

$w_{ij}=\frac{\sum_{k\in Q_i}C_{jk}^{-1}}{\sum_{l,s \in Q_i} C_{ls}^{-1}}$

第二步就是根据领域重构系数不变，去求每个样本在低维空间的坐标

$\text{min}_{z_1,z_2,...,z_m}\sum_{i=1}^m||z_i-\sum_{j\in Q_i}w_{ij}z_j||_2^2$

令 $Z=(z_1,z_2,…,z_m) \in \mathbb{R}^{d’\times m}$，$(W)_{ij}=w_{ij}$，$M=(I-W)^T(I-W)$。

利用 $M$ 矩阵，可以将问题写成

$\text{min}_Z \text{tr}(ZMZ^T)\\ \text{s.t.} ZZ^T=1$

因此问题就成了对 $M$ 矩阵进行特征分解，然后取最小的d‘个特征值对应的特征向量组成低维空间的坐标 $Z$。LLE算法具体的流程如下（来源：机器学习周志华版）

LLE算法总结：

主要优点：

可以学习任意维的局部线性的低维流形
算法归结为稀疏矩阵特征分解，计算复杂度相对较小，实现容易。
可以处理非线性的数据，能进行非线性降维

主要缺点：　　

算法所学习的流形只能是不闭合的，且样本集是稠密的
算法对最近邻样本数的选择敏感，不同的最近邻数对最后的降维结果有很大影响。

Lec10

近似重复视频检测/检测

视频一般是24帧/s至30帧/s，切成帧处理意味着计算量巨大。

视频的构成

据 motion picture experts group (MPEG），视频 = 图像序列+[音频]+[字幕]+[特征]（用于索引）+[元数据]。

视频压缩一般用DCT（离散余弦变换）。

视频检索

基于视频签名的方法：

计算全局特征，例如每帧/镜头的CH值
将帧级到视频级的全局特征集合起来
也就是说，一个视频表示为一个特征向量

这种方法仅适用于完全复制或几乎相同的视频。

基于轨迹的方法：

在视频序列中跟踪物体的轨迹
一个轨迹表示一个物体的运动模式
沿着轨迹提取特征
将视频之间的比较转换为轨迹集之间的比较

这种方法内存和计算复杂度高，性能差。

基于帧的方法：

视频被看作是图像的集合
分别检索每个帧
将检索到的帧组合成视频

简单。

离线索引：

从待查询视频中采样帧
从每一帧中提取特征
对特征建立 BoW/VLAD 建立索引

在线检索：

从查询视频中采样帧
从每一帧中提取特征
使用 BoW/VLAD 进行检索

候选视频应该按照查询视频进行排名，但是如何将帧之间的相似性聚合成视频之间的相似性？

查询视频 $Q$ 中的帧 $i$ 与待查询视频中的 $V_k$ 的帧 $j$ 有相似性 $S_{ij}$，即 $\langle Q, V_k, F_i, M_j, S_{ij}\rangle$。

现在目标是聚合 $Q$ 与 $V_k$ 的相似性。$\langle Q,V_k,F_i,M_j,S_{ij}\rangle \rightarrow \langle Q,V_k,t_i,t_j,S_{ij}\rangle$，其中 $sim(Q,V_k)=\sum_{t_i-t_j} s_{ij}$，相同的时间戳差 $t_i-t_j$ 将会聚合。

$sim(Q,V_k,\Delta) = \sum_{\Delta_{ij}}s_{ij}$，其中 $\Delta=t_i-t_j$，将会有多个 $\Delta$。选择其最高作为 $sim(Q,V_k,\Delta)$。

该检索方法可以是任何图像检索方法，BoVW仍然是默认选项。

实例搜索

搜索特定对象、人员或位置的实例。定位图像中的实例（作为边框给出）。

挑战

与图像搜索类似：

全局特征不起作用
关键点特征容易受到物体形变的影响
包围框产生了太多没有意义的候选项
它需要一个对象级表示

假设一张图像中有40个实例，

内存消耗比图像搜索高一个数量级
定位信息应以索引结构保存
速度效率比图像搜索慢一个量级
随着问题规模的增长，也面临着类似的性能下降

代表性方法：NII INS system

基于 BoVW 的简单方法，没有什么特别的技巧，但是表现很好，适用于对象和定位。

关键点检测器：Hessian-Affine
描述符：RootSIFT
码本大小：1M，AKM训练
量化：BoVW
索引：tf-idf加权，倒排索引
融合：平均池化

优点：

充分展现了 BoVW 结合倒排索引的前景
采用非常大的词汇量(1M)²

缺点：

关键点特征（例如SIFT）在非刚性实例上表现不好
词汇量非常大的训练是非常耗时的。

基于深度特征的实例搜索

优点：

覆盖了大部分区域
强判别性

劣势：

数量大
对形变敏感
判别性过强
不能完全覆盖一个对象

引用

An image-based approach to video copy detection with spatio-temporal post-filtering: Matthijs Douze, et al. TMM 2010
On the Annotation of Web Videos by Efficient Near-duplicate Search: Wan-Lei Zhao, et al. TMM 2010
The PASCAL Visual Object Classes Challenge: A Retrospective, Mark Everingham, et al., IJCV 2015
Visualizing and Understanding Convolutional Networks, Matthew D. Zeiler and Rob Fergus, ECCV 2014