根据 Stanford CS131 课程写的笔记（大部分为 note 翻译），英语水平一般，如有错误请评论指正

Lecture 13 Face Recognition and LDA

Introduction to Facial Recognition

Applications

• 数字摄影：聚焦人脸
• 监视器
• 组织相册：将相同的人放在同一相册
• 人物追踪
• 动作和表情：构建基于心情互动的智能设备
• 安全和战争：检测特殊人物、敌军
• 电话会议：提供正在视频的人的信息

A Key Distinction: Detection vs. Recognition

Face Detection: 检测照片是否包含人脸和照片上人脸的位置

Face Recognition: 检测照片包含谁的脸

Space of Faces

如果我们考虑一张大小为 m×n$m\times n$灰度图，这张图可以用一个在高维空间 Rmn$R^{mn}$上的点表示。一张图不止包含脸，所以脸只占了相对小的子空间。我们的任务就是对脸的子空间建模。

我们计算出 K 维子空间，这样数据点在子空间的投影在所有子空间中都有最大的方差。这个低维子空间捕捉了脸部关键样貌特点。

The Eigenfaces Algorithm

Key Ideas and Assumptions

• 假设大多数脸部图像都位于低维子空间，由最大方差的前 k$k$个方向决定
• 用 PCA 检测旋转子空间的向量或特征面
• 将所有数据集中的脸部图像表现为特征面的线性组合，特征面被定义为 SVD 分解的主成份

What are eigenfaces?

特征面是最大方差方向的特征向量的视觉呈现。

Training Algorithm

1. 排列训练图像：x1,...,xn$x_1,...,x_n$

2. 计算平均脸：
   

   μ=1N∑xi$$\mu =\frac{1}{N}\sum x_i$$

3. 计算协方差矩阵：
   

   Σ=1NXcXTc$$\mathrm{\Sigma }=\frac{1}{N}{X}_c{X}_c^T$$

4. 用 PCA 计算协方差矩阵Σ$\mathrm{\Sigma }$的特征向量

5. 计算每个训练图像 xi$x_i$的投影
   

   xi→(xci⋅ϕ1,xci⋅ϕ2,...,xci⋅ϕk)≡(a1,a2,...,ak)$$x_i\to (x_i^c·{\varphi }_1,x_i^c·{\varphi }_2,...,x_i^c·{\varphi }_k)\equiv (a_1,a_2,...,a_k)$$
   
   其中ϕi${\varphi }_i$是第i$i$个特征向量。

6. 重构的脸xi≈μ+a1⋅ϕ1+...+ak⋅ϕk$x_i\approx \mu +a_1·{\varphi }_1+...+a_k·{\varphi }_k$

Why can we do this?

因为特征值（特征向量的方差）随着主成份数目的增加迅速下降

Reconstruction and Error

我们只需要前k$k$个特征面用于减少维度。特征面越少损失越多，脸部越不明显。

Testing Algorithm

1. 取查询图像t$t$

2. 映射至特征向量：
   

   t→((t−μ)⋅ϕ1,(t−μ)⋅ϕ2,...,(t−μ)⋅ϕk)≡(w1,w2,..,wk)$$t\to ((t-\mu )·{\varphi }_1,(t-\mu )·{\varphi }_2,...,(t-\mu )·{\varphi }_k)\equiv (w_1,w_2,..,w_k)$$

3. 比较投影w$w$和所有N$N$个训练投影。用欧几里德距离和 KNN 算法输出标签。

Advantages and Disadvantages

Advantages

• 这个方法不需要预先知道脸部、表情信息
• 快速、全局最优

Disadvantages

• 要求小心控制的数据
  
  1. 所有脸部必须集中在框架。否则结果噪音大
  2. 图像必须大小相同
  3. 对脸的角度敏感
• 方法不需要预先知识
  
  1. 脸的类别之间没有差别
  2. PCA 不考虑与脸相关的标签。因此它可能将不同的脸对应到相同的子空间，使得分类器难以区别这些脸。
• PCA 投影在从低维重构上可能是最优的，但在在辨别方面不是最优的。

Beyond Facial Recognition: Expressions and Emotions

这项技术也可以用于检测表达和情绪，且算法不改变。

高兴↓

厌恶↓

Linear Discriminant Analysis (LDA)

PCA vs. LDA

PCA 与 LDA 都能减少样本的维度。但是，PCA 偏重于重建物体，LDA 偏重于分类。LDA 会将不同的类相互远离。

• PCA 保持最大方差
• LDA 找到能够在类之间最大化散射和在类中最小化散射的投影。

如图，PCA 保持了最大方差，并将所有类的点都映射在正斜率方向上，因此难以判别类别。但是，LDA 将点映射到负斜率，导致点被映射到接近同类点，与非同类点相反的位置。

General Idea

LDA 用两个值运行：类间散度、类内散度。类间散度指不同类之间的距离，类内散度指类内点之间的距离。LDA 最大化类间散度，最小化类内散度。

Mathematical Formulation of LDA with 2 Variables

我们想要找到一个投影w$w$在x∈Rn$x\in R^n$空间中映射出 0 和 1 的点到一个新的空间z∈Rm$z\in R^m$，例如z=wTx$z=w^{T}x$。其中，m<n$m<n$，且投影必须最大化以下公式：

公式中，SB$S_B$代表类间散度，SW$S_W$代表类内散度。接下来定义一个代表类内点的平均的变量μi${\mu }_i$：

定义变量Σi${\mathrm{\Sigma }}_i$代表类的协方差矩阵：

用以上变量，可以定义SB$S_B$和SW$S_W$：

将变量放回原式J(w)$J(w)$可得：

我们要最大化J(w)$J(w)$，即最大化分子，保持分母为常数：

用拉格朗日乘数法，我们定义拉格朗日算子为：

我们必须最大化L$L$对λ$\lambda$和w$w$的值。我们可以通过用其关于w$w$的梯度和找到关键点的位置：

用这个公式，我们可以得到关键点位置：

这是一个广义的特征向量问题。在S−1W=(Σ1+Σ0)−1$S_W^{-1}=({\mathrm{\Sigma }}_1+{\mathrm{\Sigma }}_0{)}^{-1}$存在的情况下，我们得到：

代入SB$S_B$得：

w$w$的大小并不重要，所以我们可以得到映射w$w$：

LDA with N Variables and C Classes

Preliminaries

Variables:

• N 个样本：{x1,...,xN}$\{x_1,...,x_N\}$

• C 个类:{Y1,Y2,...,YC}$\{Y_1,Y_2,...,Y_C\}$。每一类都有 N 个样本。

• 每个类的平均：类i$i$的平均为
  

  μi=1Ni∑xk∈Yixk$${\mu }_i=\frac{1}{N_i}\sum _{x_k\in Y_i}{x}_k$$

• 所有数据的平均：
  

  μ=1N∑k=1Nxk$$\mu =\frac{1}{N}\sum _{k=1}^N{x}_k$$

Scatter Matrices:

• 类i$i$散度：Si=∑xk∈Yi(xk−μi)(xk−μi)T$S_i=\sum _{x_k\in Y_i}(x_k-{\mu }_i)(x_k-{\mu }_i{)}^T$
• 类内散度：Sw=∑ci=1Si$S_w=\sum _{i=1}^c{S}_i$
• 类间散度：Sb=∑ci=1Ni(μi−μ)(μi−μ)T$S_b=\sum _{i=1}^c{N}_i({\mu }_i-\mu )({\mu }_i-\mu {)}^T$

Mathematical Formulation

我们需要一个将所有点从x∈Rm$x\in R^m$映射到z∈Rn$z\in R^n$的投影：

Results: Eigenface(PCA) vs. Fisherface(LDA)