Feature engineering

• 传统机器学习: 手动提取+非端到端

• 深度学习: 学习特征+端到端

抽取特征

特征需要在大小、旋转方向上robust

SIFT: 对不同大小的图片作高斯模糊, 得到不同分辨率, 相邻两张分辨率的图片作差, 得到DoG。 从DoG中获取局部最大值、最小值作为关键点, 抽取关键点四周的梯度（邻近的16个patch，形 成梯度直方图。可以根据梯度最多的主导方向, 进行图片像素的旋转校正。

预处理

LP normalization: 对单一特征进行标准化, 计算特征与 0 之间的距离之和作为 norm值, $\mathrm{x}$ 的 $\mathrm{p}$ 次方 求和的p分之一次方, 对于所有的 $x$ 除以这个norm。当p越大, $x$ 越接近1或-1。

Z-score normalization: 对同一维度的多个特征进行标准化, 所有x减去均值除以标准差, 拉到标准 高斯分布。

空间信息

Spatial pyramid: 将图片分成多个 $n^{*} n$ 的方块, 将不同方块依次拼接形成特征。比如 $16^{*} 256+4^{*} 256+256$

Position Embedding: 将图片分成 $n{ }^{*} \mathrm{n}$ 的方块, 将方块的位置信息和方块特征拼接, 最后将这些特 征进行average pool。

Curse of high-dimension

• 时间空间复杂度

• 需要更多的训练样本

高模型复杂度+少样本->过拟合, 低模型复杂度+多样本->欠拟合, 随着特征维度的升高, 模型先 欠拟合最后过拟合。

高维物体的体积集中在外壳, 且高维样本特征的均值升高、标准差降低, 导致基于距离度量的方 法失效, 比如KNN。

• 提高样本数量

• 降低特征维度

Dimension Reduction

解决过拟合问题

• Feature selection: forward, backward, genetic

• Feature projection: PCA, kernel PCA, LDA

• Feature learning: Auto-encoder, SNE, t-SNE, LLE, sparse coding

Kernel trick

解决欠拟合问题, 将数据升维使得线性可分, $x_{i} \rightarrow \varphi\left(x_{i}\right)$

比如 $\varphi(X)=\varphi\left(\left[x_{1}, x_{2}\right]\right)=\left[1, x_{1}, x_{2}, x_{1} x_{2}, x_{1}^{2}, x_{2}^{2}\right]$

引入 $K(x, y)=\varphi(x)^{T} \varphi(y)$

• Linear: $K(x, y)=x^{T} y, \varphi(x)=x$

• Poly: $K(x, y)=\left(x^{T} y+c\right)^{d}$

• Gaussian: $K(x, y)=\exp \left(-\frac{\|x-y\|^{2}}{2 \sigma^{2}}\right)$

SVM (hard margin):

两条直线 $w^{T} x+b=1 \vee-1$ 之间的 $\operatorname{margin} m=\frac{2}{\|w\|}, \mathrm{w}$ 越小, $\mathrm{m}$ 越大, 即距离越大越好。

• Hard margin:

$\begin{gathered} \min _{w, b} \frac{1}{2}\|w\|^{2} \\ \text { s.t. } y_{i}\left(w^{T} x_{i}+b\right) \geq 1 \end{gathered}$

• Soft margin:

$\begin{gathered} \min _{w, b} \frac{1}{2}\|w\|^{2}+C \sum_{i} \xi_{i} \\ \text { s.t. } y_{i}\left(w^{T} x_{i}+b\right) \geq 1-\xi_{i}, \xi_{i} \geq 0 \end{gathered}$

Soft margin引入变量 $\xi$ 以松驰约束

Lagrangian form, 引入 $\alpha$ 以及 $\beta$, 乘以约束项

Dual form: 对 $w, b, \xi$ 分别求导, 可得 $w=\sum_{i} \alpha_{i} y_{i} \varphi\left(x_{i}\right)$, 使用 $\mathrm{QP}$ 求解器求解, 对于kernel trick只能 用dual form求解

实际运算中, 可以将 $b$ 作为一个维度吸收进 $w^{T} \varphi(x)=\bar{w}^{T} \varphi(\bar{x})+b$, 少掉一个约束项更加简化。 Kernel in logistic regression, $w=\sum_{i} \alpha_{i} \varphi\left(x_{i}\right)$ (representation theorem)

Kernel properties:

• 对称性

• 柯西不等式

• 闭集性质

Distance metric

• Distance between two samples

• Distance between two distributions

Distance between two samples

Minkowski distance(LP): 每一维特征差值的p次方之和的p分之一次方

• $\mathrm{p}=\infty$, Chebyshev distance: 最大的某一维特征差值

$\cdot \mathrm{p}=2$, Euclidean distance: 欧式距离, $d=\|x-y\|=\sqrt{\|x\|^{2}+\|y\|^{2}+2 x^{T} y}$

• $\mathrm{p}=1$, Manhattan distance

Cosine similarity: $\operatorname{sim}_{\cos }=\frac{x^{T} y}{\|x\| y \|}$, similarity越大, distance越短。和欧式距离的关系。 如果维度分布差别太大，需要先用Z-score normalization

Metric learning: 计算两个差异大的样本间距离, 将特征投影到同一空间。使类间距离足够大, 类 内距离足够小。

Mahalanobis distance: 马氏距离, $d_{M(P x, P y)}=\|P x-P y\|=\sqrt{\left(x^{T}-y^{T}\right) M(x-y)}, M=P^{T} P$, 注 意 $M$ 矩阵是半正定的。

$\begin{gathered} \max _{x_{i}, x_{j} \in D} d_{M}^{2}\left(x_{i}, x_{j}\right) \\ \text { s.t. } \sum_{x_{i}, x_{j} \in S} d_{M}^{2}\left(x_{i}, x_{j}\right) \leq 1 \end{gathered}$

EMD: 度量两个集合之间的距离, 两个集合中元素的数量不一定相同, w表示权重。比如计算图 片间的距离, 根据两张图片可以得到颜色直方图, $\mathrm{x}$ 为颜色值, $\mathrm{w}$ 为颜色像素的个数。

推土距离, $\mathrm{S}$ 集合相当于土, T集合相当于坑, 先计算不同 $\mathrm{x}$ 之间的距离, 从 $w_{i}^{s}$ 移动 $f_{i, j}$ 的土到各个 $w_{j}^{t}$ 坑, 优化目标是最小化运的土。

$\begin{gathered} \min _{f_{i, j}} \sum_{i} \sum_{j} f_{i, j} d\left(x_{i}^{s}, x_{j}^{t}\right) \\ \text { s.t. } \sum_{i=1}^{m} f_{i, j} \leq w_{j}^{t}, \sum_{j=1}^{n} f_{i, j} \leq w_{i}^{s}, \sum_{i} \sum_{j} f_{i, j}=\min \left(\sum_{i}^{m} w_{i}^{s}, \sum_{j}^{n} w_{j}^{t}\right) \end{gathered}$

要么把土清空要么把坑填满

Application of distance: KNN, retrival（根据文本找图像), verification（人脸验证, 判断两个样本 是否属于一个种类), outlier detection（异常值检测）

Distance between two distributions

由直方图表示分布：

• Canberra distance: $d(p, q)=\sum_{i=1}^{d} \frac{\left|p_{i}-q_{i}\right|}{p_{i}+q_{i}}$

• Chi-square distance: $d(p, q)=\sum_{i=1}^{d} \frac{\left(p_{i}-q_{i}\right)^{2}}{p_{i}}$

• Intersection between two histograms: $d(p, q)=\sum_{i=1}^{d} \min \left(q_{i}, p_{i}\right)$

MMD: 两个分布均值间的距离, 只考虑中心的欧式距离, 最简单的。

$D_{M M D}:\left[\sum_{i} x_{i} p\left(x_{i}\right)-\sum_{i} x_{i} q\left(x_{i}\right)\right]^{2}$

KL divergence:

$D_{K L}(p \mid q)=\sum_{i} p\left(x_{i}\right) \log \frac{p\left(x_{i}\right)}{q\left(y_{i}\right)}=H(p, q)-H(p)$

缺点是非对称的。

根据KL散度的变体, 将其变成对称的:

• Jeffreys divergence: $D_{J D}=D_{K L}(q \mid p)+D_{K L}(p \mid q)$

• Jensen-Shannon divergence: $D_{J S}=\frac{1}{2} D_{K L}\left(q \mid \frac{1}{2}(p+q)\right)+\frac{1}{2} D_{K L}\left(p \mid \frac{1}{2}(p+q)\right)$

Bregman divergence: 更general的形式

$D_{\varphi}(p, q)=\varphi(p)-\varphi(q)-(p-q)^{T} \nabla \varphi(q)$

• $\varphi(z)=\frac{1}{2} z^{T} z$, 欧式距离

• $\varphi(z)=z^{T} \log z$, generalized KL散度

Single value decomposition

Best fitting line: 最大化所有点到这条线的投影平方和

PCA: 先decentralized再计算, Eigen Decomposition: $A^{T} A v=\lambda v$

Subspace: greedy algorithm, but can find the global optimum

$\begin{gathered} A v_{i}, d_{i}=\left\|A v_{i}\right\|, u_{i}=\frac{A v_{i}}{d_{i}} \\ d_{i} \rightarrow D, u_{i} \rightarrow U \\ A=U D V^{T}=\sum_{i=1}^{k} d_{i} u_{i} v_{i}^{T} \end{gathered}$

Norm based SVD:

• $\mathrm{p}=0, \operatorname{rank}$ of $A$

• $\mathrm{p}=1$, nuclear norm $\|A\|_{*}=\sum_{i}^{k} d_{i}$

• $\mathrm{p}=2$, Frobenius norm

• $\mathrm{p}=\infty$, spectral norm

Application of SVD:

• rank-k approximation, 将 $\mathrm{D}$ 的 $r+1 \sim k$ 维设为 0

• image compression, $r \times(1+n+m)$

• latent semantic analysis, $U$ : term-topic matrix, $D$ : topic weights, $V^{T}$ : topic-document matrix, boat 和ship

Zero-shot learning

Seen category $C^{s}$ 和 unseen category $C^{t}$

从 seen category中学习固有属性, 并告诉你unseen category的属性进行分类

• 人工标注, 准确率高但是麻烦

• 大规模语料库, 免费但是信息少

ZSL的关键在于：Visual space、semantic space和category space之间的桥接

semantic relatedness: 根据semantic space计算相似度矩阵, 作为分类器的权重, 对 seen category的 分类器施加不同的权重用以分类unseen category。

semantic embedding: 从visual space到semantic space学习一个映射, 训练的时候最小化映射后和 属性向量的loss, 测试的时候计算得出分数最高unseen category作为结果。

或者学习一个双重映射, 即 $x^{T} M a_{c}$

synthetic: 从semantic space生成visual space的样本, 用分类器分类。根据属性特征随机生成样本 特征, 放入discriminator中判断真实性, 同时也放入classifier中维持保类性。

ZSL的问题:

• Projection domain shift: seen和unseen的projection差异太大，使用属于unseen但不知道category的样本来调整映射矩阵

• Hubness problem: 很多样本都汇聚到少量unseen category中 normalize the distance或者use ranking, 测试样本对每个种类都维护一个排名

• Semantic gap: 存在一些non-visual特征, 需要将visual space和semantic space对齐, 对每个属性 特征, 计算它 $\mathrm{K}$ 个最相近的属性的平均值来代替它。

GZSL: 测试集包含一部分 seen category, 存在的问题是seen category分数比unseen的高

• 降低seen category的预测分数

• 先预测seen or unseen, 再预测类别。

Domain adaptation

source domain和target domain不匹配, 比如source domain是真实图片, target domain是卡通图片

Traditional era

• Projection to a common space

DIP: 只考虑domain的中心，利用MMD

先Projection再Kernalization

$\begin{gathered} M M D(P, Q)=\| \mathbb{E}_{X \sim P}[\varphi(X)]-\mathbb{E}_{Y \sim Q}[\varphi(Y) \| \\ \left.\left.d\left(W^{T} X_{s}, W^{T} X_{t}\right)=\| \frac{1}{n_{s}} \sum_{i=1}^{n_{s}} \varphi\left(W^{T} X_{s}\right\}\right)-\frac{1}{n_{t}} \sum_{i=1}^{n_{t}} \varphi\left(W^{T} X_{t}\right\}\right) \|^{2}=\operatorname{tr}\left(K_{W} L\right) \end{gathered}$

TCA: 引入变换矩阵 $\widetilde{W}$ 表示假的

先Kernalization再Projection

$\widetilde{K}=\left(\tilde{\varphi}\left(X_{s t}\right)^{T} \widetilde{W}\right)\left(\widetilde{W} \tilde{\varphi}\left(X_{s t}\right)^{T}\right)=K W W^{T} K$

SA:

用PCA获取 $X_{s}, X_{t}$ 的投影 $P_{s}, P_{t}$

$\begin{gathered} \min _{M}\left\|M P_{s}-P_{t}\right\|_{F}^{2} \\ M=P_{t} P_{s}^{T} \end{gathered}$

取主导的向量 $\bar{P}_{s}, \bar{P}_{t}, M=\bar{P}_{t} \bar{P}_{s}^{T}$

$\bar{X}_{s}=\bar{P}_{t} \bar{P}_{s}^{T} \bar{P}_{s} X_{s}, \bar{X}_{t}=\bar{P}_{t} X_{t}$

CORAL: DIP是一阶距离(mean vector), CORAL是二阶距离(covariance matrix)

• Sample selection

KMM: 对 source domain的样本加上不同的权重, 分别利用MMD+SVM, 缩小两个domain中心

KTM: 和KMM类似，但将MMD和SVM拼在一起

• Fix $w$, update $\beta_{i}$, QP问题 - Fix $\beta_{i}$, update $w$, weighted SVM问题

DASVM:

• 将置信度高的target domain的样本加入source domain

• 逐渐去除一些 source domain样本

Learn how to transfer: 用于选择哪一种TF方法, 根据之前TF的经验, 学习相关知识

$\begin{gathered} l_{i}=f\left(S_{i}, T_{i}, W_{i}\right) \\ W^{*}=\arg \max _{W} f\left(S_{N_{e}+1}, T_{N_{e}+1}, W\right) \end{gathered}$

Early deep era

• DL feature + traditional methods(SA)

• DL feature + traditional idea(MMD, CORAL)

reconstruction+classification, 加权分类损失和重构损失

Domain separation networks:

• Private target encoder

• Shared encoder

• Private source encoder

两两之间有difference loss和similarity loss

target、部分shared以及source、部分source输出到shared decoder重建feature, shared中的source 信息输出到classifier中。

reconstruction loss有两个, classifier loss仅有一个

• Batch normalization based

Batch normalization:利用Z-score normalization, 训练集都用source domain的分布标准化, 测试集 用target domain的分布标准化。 domain adaptive batch normalization

• Adversarial learning

Adversarial learning: 分类+分domain, 拉近source domain和target domain之间的数据分布 feature extractor, label classifer, domain classifier, gradient reversal layer

GAN era

Generative Adversarial Network: 从fearture-level到image-level

Unconditional GAN

用数据分布以及generator随机产生样本, 将假样本和真样本放入discriminator中判断是real还是 fake

$\min _{G} \max _{D} \mathbb{E}_{z[\log D(G(z))]}+\mathbb{E}_{y[\log (1-D(y))]}$

左边一项生成的误差降低, 右边一项判断准确率降低, 达到以假乱真

Conditional GAN: 有先验知识, 不需要用数据分布产生随机样本, $z$ 改变为 $x$ 。

Paired GAN: pix2pix, 有成对的数据, 既可以用于生成新样本又可以和新样本一起放入 discriminator中判断 训练阶段:

$\left.\min _{G} \max _{D} \mathbb{E}_{z[\log D(x, G(x))]}+\mathbb{E}_{y[\log (1-D(x, y))]}+\mathbb{E}_{x, y} [\| y-G(x) \|\right]$

测试阶段同conditional GAN

Unpaired GAN: 没有成对的数据, cycle GAN, 互相学习从 $X$ 到 $Y 、 Y$ 到 $X$ 的映射, 希望两次映射后 和原来接近, $D_{Y} 、 D_{G}$ 分别用来判断两个域。

$\begin{aligned} & X \rightarrow G(x) \rightarrow F(G(X)) \\ & Y \rightarrow F(Y) \rightarrow G(F(Y)) \end{aligned}$

reconstruction loss、discriminator loss各两个

Data sampling

• From sample to distribution

• From distribution to sample

常见的分布类型:

• Binominal (二项分布)

• Poisson

• Gaussian

From sample to distribution

MLE最大似然估计

$\begin{gathered} p(x \mid \theta)=\frac{1}{\sqrt{2 \pi \sigma^{2}}} \exp \left(-\frac{(x-\mu)^{2}}{2 \sigma^{2}}\right) \\ p\left(x_{1}, x_{2}, \ldots, x_{N} \mid \theta\right)=\Pi_{i=1}^{N} p\left(x_{i} \mid \theta\right)=\left(\frac{1}{2 \pi \sigma^{2}}\right)^{\frac{N}{2}} \exp \left(-\frac{\sum_{i=1}^{N}(x-\mu)^{2}}{2 \sigma^{2}}\right) \\ \hat{\mu}=\frac{1}{N} \sum_{i=1}^{N} x_{i} \\ \hat{\sigma}^{2}=\frac{1}{N} \sum_{i=1}^{N}\left(x_{i}-\hat{\mu}\right)^{2} \end{gathered}$

有偏估计

Define $\lambda_{i}=\mu-x_{i}, \mathbb{E}\left[\lambda_{i}\right]=0, \mathbb{E}\left[\lambda_{i}^{2}\right]=\sigma^{2}$, 计算可得 $\mathbb{E}\left[\hat{\sigma}^{2}\right]=\frac{N-1}{N} \sigma^{2}$, 样本越多，偏差越小。

GMM高斯混合模型：K个高斯分布+各自权重

$p\left(x_{i} \mid \theta\right)=\sum_{k=1}^{K} p\left(x_{i} \mid \mu_{k}, \sigma_{k}\right) \pi_{k}$

引入 $\gamma_{i(k)}$, 第 $\mathrm{i}$ 个sample属于第 $\mathrm{k}$ 个分布模型的概率, 用EM算法估计 $\gamma$ 和 $\theta$ 。

• E-step: 根据每个高斯模型的概率和权重估计 $\gamma$, 权重乘概率比上所有权重乘概率

• M-step: 利用 $\gamma$ 进行最大似然估计得出 $\theta$

GMM和K-means的区别在于计算了属于每个分布的概率，相当于 soft clustering。K-means在 $\gamma$ 和 $\mu$ 之间交替更新。

From distribution to sample

对于uniform distribution可以直接均匀随机采样

Rejection sampling:

• 先找到一个envelope distribution $k q(z) \geq p(z)$ 包住原有的分布

• 从这个分布中进行采样

• 计算接受概率 $\frac{p\left(z_{0}\right)}{k q\left(z_{0}\right)}$ 决定是否接受

难点在于找到一个envelope distribution

Adaptive rejection sampling: 分段考虑, 找近似

当原有分布具有log concave性质时, 可以用多个exponential envelope distribution来包住原有分布

$\begin{gathered} \log q(z) \geq \log (p(z)) \\ q(z)=k_{i} \lambda_{i} \exp \left(-\lambda_{i}\left(z-z_{i-1}\right)\right), z_{i-1}<z<z_{i} \end{gathered}$

有时候不需要采样具体 $\mathrm{x}$, 而是只需要 $f(x)$ 的期望

Importance sampling: 用 $\mathrm{q}$ 代替采样

$\int f(x) p(x) d x=\int f(x) \frac{p(x)}{q(x)} q(x) d x=\frac{1}{S} \sum_{i=1}^{S} f\left(x^{s}\right) \frac{p\left(x^{s}\right)}{q\left(x^{s}\right)}$

$f\left(x^{s}\right) \frac{p\left(x^{s}\right)}{q\left(x^{s}\right)}$ 为权重, 最终结果是加权平均

MCMC蒙特卡罗采样：一大类方法, 逐个采样, 根据数据分布进行biased random walk

• Metropolis-Hostings: 单变量

  • 根据常用的数据分布概率随机产生candidate

  • 根据公式计算接受概率

  • 生成 $0 \sim 1$ 之间的随机数, 选择下一个 $x_{t+1}$

• Gibbs sampling: 多变量

  • 将所有维度分成两组, 交替采样

  • $j=mod (t, d)$, 根据 $p\left(x^{j} \mid x_{t}^{1}, x_{t}^{2}, \ldots x_{t}^{j-1}, x_{t}^{j+1}, \ldots, x_{t}^{d}\right)$ 随机产生 $x_{t+1}^{j}, t=t+1$

Privileged information(PI)

训练集的特权, 即training feature有多个, testing feature只有一个，通常test的PI难以获取

• 同multi-viewing, 但在test中不用PI, CCA和SVM-2K

• • 为 test生成虚假的PI, 利用conditional GAN比如pix2pix

• 直接用RGB图片建立到depth特征的映射, Hallucination network

Hallucination network: RGB网络抽取RGB特征, 幻影网络抽取depth特征, depth网络仅在训练阶 段抽取depth特征, 并与幻影网络进行loss的计算。

• 用PI控制训练进程, SVM+

SVM+: 利用slack function代替slack variable, 用函数拟合所能接受犯的错误

$\min _{w, b, \tilde{w}, \tilde{b}} \frac{1}{2}\|w\|^{2}+\frac{\gamma}{2}\|\tilde{w}\|^{2}+C \sum_{i=1}^{N}\left(\tilde{w}^{T} \tilde{x}_{i}+\tilde{b}\right)$

$\text { s.t. } y_{i\left(w^{T} x_{i}+b\right)} \geq 1-\left(\tilde{w}^{T} \tilde{x}_{i}+\tilde{b}\right),\left(\tilde{w}^{T} \tilde{x}_{i}+\tilde{b}\right) \geq 0$

测试集的特权, 即testing feature有多个, training feature只有一个

• 用测试集中的depth特征学一个 对称相似矩阵D

Decision values: $\tilde{y}_{a, i}=w_{a}^{T} x_{a, i}^{t}+b_{a}$

$\min \sum_{i<j} D_{i, j}\left(\tilde{y}_{a, i}-\tilde{y}_{a, j}\right)$

$\mathrm{D}$ 相似度越大，预测值就会更加接近

构建对角阵 $A_{i, i}=\sum_{j} D_{i, j}$, Laplacian matrix $L=A-D$, 可将形式化简为 $\min \operatorname{trace}\left(\tilde{Y}_{a}^{t} L Y_{a}^{t}\right)$

Multi-task learning

多个分类任务放在一起做，不同task之间信息共享

Traditional method

single: $\min _{w}\left\|w^{T} X-y\right\|^{2}$

multi: $\min _{w_{t}} \sum_{t=1}^{T}\left\|w_{t}^{T} X_{t}-y_{t}\right\|^{2}$

根据task之间的关系, 添加一些约束项

• Coherence regularizer: 要求不同分类任务彼此接近, 求分类器的均值, 使各个分类器和均值接 近

• Low-rank regularizer: 最小化nuclear norm, 最小化这个矩阵的秩

• Similarity among different tasks: 考虑不同task之间的相似性

Deep learning method

• Hard sharing: 前面网络之间的参数完全共享

• Soft sharing: 网络之间的参数按照一定程度接近, 不同网络层间的loss, 利用 Cross-stitch 不同层 之间的feature特征传递共享

• Conditional variable:将vector拼接嵌入一些层, 预测每个通道, scale和bias作用于每个通道

• One encoder and multi decoder: 经典架构, 实现多种任务