特征提取与特征选择。

Feature Extraction and Selection

特征提取问题:

有一串向量,$\{x_1,x_2,\cdots,x_p\}$,其中 $x_i=\{x_{i1},x_{i2},\cdots,x_{xN}\}$,每一个 $x_i$ 属于 $C_1$ 或 $C_2$。如果构造一个降维函数 $\{f_1(x_{i1}\sim x_{iN}),f_2(x_{i1}\sim x_{iN}),\cdots,f_M(x_{i1}\sim x_{iN})\}$,使其保留最大的可分类信息?

特征选择问题:

有一串向量,$x_1,x_2,\cdots,x_p$,其中 $x_i=\{x_{i1},x_{i2},\cdots,x_{xN}\}$,每一个 $x_i$ 属于 $C_1$ 或 $C_2$。$N$ 个维度有冗余,如何从 $N$ 个维度中选取 $M$ 个维度($M≤N$),使得识别率最高?

主成分分析(Principle Component Analysis)

主成分分析由卡尔·皮尔逊于 1901 年发明,用于分析数据及建立数理模型。

构造一个 $A$、$b$,使 $Y=Ax+b$,其中 $Y$ 是一个 Mx1 的矩阵,$X$ 是一个 Nx1 的矩阵,$A$ 是一个 MxN 的矩阵,$b$ 是一个 Mx1 的矩阵。即将 $X$ 由 N 维降至 M 维。故主成分分析可以看成是一个一层的有 M 个神经元的神经网络,且其中 $x$ 是没有标签(Label)的,和自编码器类似。

PCA 的做法:寻找使方差最大的方向,并在该方向上投影。最大限度地保存了训练样本的能量。

$$
\begin{cases}
Y=A(x-\bar{x}) & b=-A\bar{x}\\
\bar{x}=E(x)=\frac{1}{P}\sum_{p=1}^Px_p & \bar{x} 为x的均值
\end{cases}
$$

在 $Y=A(x-\bar{x})$ 中,$Y$ 是一个 Mx1 的矩阵,$A$ 是一个 MxN 的矩阵,$x$ 和 $\bar{x}$ 都是 Nx1 的矩阵。将 $A$ 写成行向量的形式,其中每个 $a_i$ 代表一个投影的方向:

$$
A=\begin{bmatrix}
a_1\\
a_2\\
\vdots\\
a_n
\end{bmatrix}
$$

那么 $Y$ 可以写成如下形式:

$$
Y_i=\begin{bmatrix}
a_1(x_i-\bar{x})\\
a_2(x_i-\bar{x})\\
\vdots\\
a_n(x_i-\bar{x})
\end{bmatrix}
=\begin{bmatrix}
y_{i1}\\
y_{i2}\\
\vdots\\
y_{iM}
\end{bmatrix}
(i=1\sim P)
$$

假设训练样本 $\{x_i\}{i=1\sim P}$。计算 $\bar{y{i1}}$ 的值如下:

$$
\begin{array}{l}
\bar{y_{i1}}=\frac{1}{P}\sum_{i=1}^Py_{i1}\\
\quad =\frac{1}{P}\sum_{i=1}^Pa_1(x_i-\bar{x})\\
\quad =\frac{a_1}{P}(\sum_{i=1}^Px_i-P\bar{x})=0
\end{array}
$$

最大化(其中 $\Sigma$ 是协方差矩阵):

$$
\begin{array}{l}
\sum_{i=1}^P(y_{i1}-\bar{y_{i1}})^2=\sum_{i=1}^Py_{i1}^2\\
\quad\quad\quad\quad\quad\quad =\sum_{i=1}^P[a_1(x_i-\bar{x})]^2\\
\quad\quad\quad\quad\quad\quad =\sum_{i=1}^P[a_1(x_i-\bar{x})][a_1(x_i-\bar{x})]^T\\
\quad\quad\quad\quad\quad\quad =\sum_{i=1}^Pa_1[(x_i-\bar{x})(x_i-\bar{x})^T]a_1^T\\
\quad\quad\quad\quad\quad\quad =a_1[\sum_{i=1}^P(x_i-\bar{x})(x_i-\bar{x})^T]a_1^T\\
\quad\quad\quad\quad\quad\quad =a_1\Sigma a_1^T & (\Sigma=\sum_{i=1}^P(x_i-\bar{x})(x_i-\bar{x})^T
\end{array}
$$

最终得到最大化优化问题如下:

  • 最大化:$a_1\Sigma a_1^T$
  • 限制条件:$a_1a_1^T=\lVert a_1\rVert^2=1$

拉格朗日乘子法:

$$
\begin{array}{l}
E(a_1)=a_1\Sigma a_1^T-\lambda(a_1a_1^T-1)\\
\frac{\partial E}{\partial a_1}=(\Sigma a_1^T-\lambda a_1^T)^T=0
\end{array}
$$

因此:

$$
\begin{array}{l}
\Sigma a_1^T=\lambda a_1^T & (a_1^T是\Sigma的特征向量,\lambda是\Sigma的特征值)\\
a_1(\Sigma a_1^T)=a_1(\lambda a_1^T)=\lambda(a_1a_1^T)=\lambda
\end{array}
$$

故可以得出 $\lambda$ 是 $\Sigma$ 最大的特征值,$a_1$ 是 $\Sigma$ 最大特征值对应的特征向量,且 $a_1a_1^T=1$。

改造优化问题:

  • 最大化:$a_2\Sigma a_2^T$
  • 限制条件:
    • $a_2a_2^T=\lVert a_2\rVert^2=1$;
    • $a_2a_1^T=a^1a_2^T=0$,即 $a_1$ 与 $a_2$ 正交。

拉格朗日乘子法:

$$
\begin{array}{l}
E(a_2)=a_2\Sigma a_2^T-\lambda(a_2a_2^T)-\beta a_1a_2^T\\
\frac{\partial E}{\partial a_2}=(\Sigma a_2^T-\lambda a_2^T-\beta a_1^T)^T=0\\
\Sigma a_2^T-\lambda a_2^T-\beta a_1^T=0
\end{array}
$$

证明 $\beta=0$:

$$
\begin{array}{cc}
(\Sigma a_2^T-\lambda a_2^T-\beta a_1^T)^T=0\\
a_2\Sigma^T-\lambda a_2-\beta a_1=0
\end{array}
$$

因为 $\Sigma$ 是一个对称阵,即 $\Sigma=\Sigma^T$,得到:

$$
\begin{array}{cc}
a_2\Sigma-\lambda a_2-\beta a_1=0\\
a_2(\Sigma a_1^T)-\lambda(a_2a_1^T)-\beta a_1a_1^T=0\\
a_2\lambda_1a_1^T-0-\beta=0\\
\lambda_1 a_2a_1^T-\beta=0\\
\beta=0
\end{array}
$$

由于 $\beta=0$,故有:

$$
\begin{cases}
\Sigma a_2^T=\lambda a_2^T\\
a_2a_2^T=1\\
a_2\Sigma a_2^T=\lambda
\end{cases}
$$

所以 $a_2$ 是 $\Sigma$ 的特征向量,$\lambda$ 是 $\Sigma$ 的第二大的特征值。以此类推,同理可以得到 $a_3$ 是 $\Sigma$ 第三大特征值特征向量;$a_4$ ……;$a_5$ ……

Summary

PCA 算法总结如下:

  1. 求协方差矩阵:$\Sigma=\sum_{i=1}^P(x_i-\bar{x})(x_i-\bar{x})^T$;
  2. 求协方差矩阵 $\Sigma$ 的特征值,并从大到小排序:$[\lambda_1,\lambda_2,\cdots,\lambda_M,\lambda_{M+1},\cdots]$,对应的特征向量:$[a_1^T,a_2^T,\cdots,a_M^T,a_{M+1}^T,\cdots]$;
  3. 归一化所有 $a_i$,使 $a_ia_i^T=1$;
  4. $A=\begin{bmatrix}a_1\\ a_2\\ \cdots\\ a_M\end{bmatrix}$;
  5. 降维:$Y_i=A(x_i-\bar{x})$,其中 $(i=1\sim P)$。

相关:SVD(Singular Value Decomposition)

自适应提升算法(AdaBoost)

自适应增强是一种机器学习方法,由 Yoav Freund 和 Robert Schapire 于 1995 年提出。

特征选择:$x=\begin{bmatrix}x_1\\ x_2\\ \cdots\\ x_N\end{bmatrix}$,从 N 个特征中选 M 个使识别率最高。共有 $C_N^M=\frac{N!}{M!(N-M)!}$ 种选法。启发式方法:

  1. 递增法;
  2. 递减法。

数据集 $T=\{(x_1,y_1),\cdots,(x_N,y_N)\}$,二分类问题:$y_i=\{-1,+1\}$。AdaBoost 算法流程:

  • 输入:$T=\{(x_i,y_i)\}_{i=1\sim N}$;
  • 输出:分类器 $G(x)=±1$。
  1. 初始化采样权值:$D_1=(\omega_{11},\omega_{12},\omega_{13},\cdots,\omega_{1N})$,且 $\omega_{1i}=\frac{1}{N}$,其中 $i=1\sim N$;
  2. 对 $m=1,2,\cdots,M$($M$ 是弱分类器个数),用 $D_M$ 采样 $N$ 个训练样本,在训练样本上获得弱分类器 $G_m(x)=±1$;
  3. 计算加权错误率:$\begin{array}{l}e_m=P(G_m(x_i)≠y_i)=\sum_{i=1}^N\omega_{m_i}I(G_m(x_i)≠y_i) & e_m<\frac{1}{2}\end{array}$,识别器 $G_m(x_i)$ 的权重为 $\begin{array}{l}\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m} & \alpha_m>0\end{array}$;
  4. 更新权值分布:$D_{m+1}=\{\omega_{m+1,1},\omega{m+1,2},\cdots,\omega_{m+1,N}\}$,其中 $\begin{cases}\omega_{m+1,i}=\frac{\omega_{mi}}{Z_m}e^{-\alpha_my_iG_m(x_i)}\\ Z_m=\sum_{i=1}^N\omega_{mi}e^{-\alpha_my_iG_m(x_i)}\end{cases}$;
  5. 回到 2;
  6. 定义 $f(x)=\sum_{m=1}^M\alpha_mG_m(x)$,得到最终识别器 $G(x)=sign(f(x))=sign[\sum_{m=1}^M\alpha_mG_m(x)]$。

定理:随着 $M$ 增加,AdaBoost 最终的分类器 $G(x)$ 在训练样本上的错误将会越来越小。

  • 错误率:$\begin{array}{l}E=\frac{1}{N}\sum_{i=1}^NI(G(x_i)≠y_i)≤\frac{1}{N}\sum_{i=1}^Ne^{-y_if(x_i)}\\ \quad=\Pi_{m=1}^MZ_m\end{array}$;
  • $\begin{array}{l}E≤\frac{1}{N}\sum_{i=1}^Ne^{-\sum_{m=1}^M\alpha_my_iG_m(x_i)}\\ \quad=\sum_{i=1}^N\omega_{1i}\Pi_{m=1}^Me^{-\alpha_my_iG_m(x_i)}\\ \quad=\sum_{i=1}^M[\omega_{1i}e^{-\alpha_1y_iG_1(x_i)}][\Pi_{m=2}^Me^{-\alpha_my_iG_m(x_i)}]\\ \quad=\sum_{i=1}^M[\omega_{2i}Z_i][\Pi_{m=2}^Me^{-\alpha_my_iG_m(x_i)}]\\ \quad=Z_1\sum_{i=1}^M\omega_{2i}[\Pi_{m=2}^Me^{-\alpha_my_iG_m(x_i)}]\\ \quad=\Pi_{m=1}^MZ_m\end{array}$

证明:$Z_m=2\sqrt{e_m(1-e_m)}$

$$
\begin{array}{l}
Z_m=\sum_{i=1}^N\omega_{mi}e^{-\alpha_my_iG_m(x_i)}\\
\quad=\sum_{i=1\And y_i=G_m(x_i)}^N\omega_{mi}e^{-\alpha_m}+\sum_{i=1\And y_i≠G_m(x_i)}^N\omega_{mi}e^{\alpha_m}\\
\quad=(1-e_m)e^{-\alpha_m}+e_me^{\alpha_m}
\end{array}
$$

将 $\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$ 代入,得:

$$
Z_m≤2\sqrt{e_m(1-e_m)}
$$

若 $e_m<\frac{1}{2}$,则 $Z_m<1$。

References

浙江大学信电学院《机器学习》课程


ml

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

Moving on
Reiforcement Learning