机器学习

特征工程

计算机学院    张腾

tengzhang@hust.edu.cn

机器学习一般流程

原始数据：表格、图片、视频、文本、语音、……

特征工程：

• 提取：选取、构造对目标任务有用的潜在特征
• 处理：无序的离散类别特征 → 数值特征，缺失处理，标准化
• 变换：对特征进行挑选或映射得到对目标任务更有效的特征

特征提取 以文本为例

词袋模型 (bag-of-words)：文本是单词的集合，单词独立无序

• 所有文本全部$d$个不同的单词构成词典，每个文本提取$d$个特征
• 若词典第$i$个词在当前文本中出现过，则其第$i$个特征为$1$，否则为$0$

import pandas as pd
from sklearn.feature_extraction.text import CountVectorizer

document1 = "I have a pen, I have an apple, apple pen."
document2 = "I have a pen, I have pineapple, pineapple pen."

cv = CountVectorizer(lowercase=False, token_pattern='\w+', binary=True)
model = cv.fit_transform([document1, document2])
print(pd.DataFrame(model.toarray(), columns=cv.get_feature_names_out()))
#    I  a  an  apple  have  pen  pineapple
# 0  1  1   1      1     1    1          0
# 1  1  1   0      0     1    1          1

特征提取 以文本为例

词袋模型 (bag-of-words)：文本是单词的集合，单词独立无序

• 所有文本全部$d$个不同的单词构成词典，每个文本提取$d$个特征
• 若词典第$i$个词在当前文本中出现了$k$次，则其第$i$个特征为$k$

import pandas as pd
from sklearn.feature_extraction.text import CountVectorizer

document1 = "I have a pen, I have an apple, apple pen."
document2 = "I have a pen, I have pineapple, pineapple pen."

cv = CountVectorizer(lowercase=False, token_pattern='\w+')
model = cv.fit_transform([document1, document2])
print(pd.DataFrame(model.toarray(), columns=cv.get_feature_names_out()))
#    I  a  an  apple  have  pen  pineapple
# 0  2  1   1      2     2    2          0
# 1  2  1   0      0     2    2          2

特征提取 以文本为例

词频 - 逆文本频率：对当前文本重要的单词必然

• 在当前文本中出现的频率高，即词频 (term frequency, tf) 高
• 在其他文本中出现的频率低，即逆文本频率 (inverse document frequency, idf) 高

tf = 单词在当前文本中出现的次数 / 当前文本的总词数
idf = ln ((全部文本数 + C) / (包含该词的总文本数 + C)) + 1

• C = 0，若词典包含从未在任何文本中出现的词，会有分母为零的问题
• C = 1，sklearn 默认的平滑版本，等于额外有一个包含所有词的文本

tf - idf 特征 = normalize (tf × idf)，即将 tf 和 idf 相乘后再标准化

• $\ell_1$标准化，tf × idf / sum (tf × idf)，即线性变换成概率分布
• $\ell_2$标准化，tf × idf / sqrt(sum ([tf × idf]^2))，即线性变换成单位向量

特征提取 以文本为例

import pandas as pd
from sklearn.feature_extraction.text import TfidfVectorizer

document1 = "I have a pen, I have an apple, apple pen."
document2 = "I have a pen, I have pineapple, pineapple pen."

tv = TfidfVectorizer(lowercase=False, token_pattern='\w+',
                     norm='l1', smooth_idf=False)
model = tv.fit_transform([document1, document2])
print(pd.DataFrame(model.toarray(), columns=tv.get_feature_names_out()))
#           I         a        an     apple      have       pen  pineapple
# 0  0.165571  0.082785  0.140168  0.280335  0.165571  0.165571   0.000000
# 1  0.192561  0.096281  0.000000  0.000000  0.192561  0.192561   0.326035

特征 离散类别 → 数值

• 序数编码 (ordinal encoding)：清零 - 0、平缓 - 1、严峻 - 2，需类别特征本身有序，否则若吃饭 - 0、逛街 - 1、学习 - 2，为何 |吃饭 - 学习| > |吃饭 - 逛街| ？
• 独热编码 (one-hot encoding)：吃饭 - 001、逛街 - 010、学习 - 100，一碗水端平，所有取值距离相等，但若取值很多码会很长，且不适应动态出现的新取值
• 哈希编码 (hash encoding)：用哈希函数将任意输入映射到有限整数范围，码长固定，也能适应动态出现的新取值，但可能存在信息丢失

特征独热编码

import numpy as np
from sklearn.preprocessing import LabelBinarizer, OneHotEncoder

X = np.array([
    [1, '周六', '吃饭', '晴天', '轻松', '清零', '精彩'],
    [6, '周六', '逛街', '晴天', '轻松', '平缓', '无聊'],
    [10, '周六', '-', '雨天', '轻松', '严峻', '无聊'],
    [13, '周六', '逛街', '晴天', '正常', '清零', '精彩'],
])
y = np.array(['是', '是', '否', '否'])
print(LabelBinarizer().fit_transform(y).squeeze())  # 标记二值化
# [1 1 0 0]

enc = OneHotEncoder()
print(enc.fit_transform(X[:, 1:7]).toarray())  # 对6个类别特征采用独热编码
# [[1. 0. 1. 0. 1. 0. 0. 1. 0. 0. 1. 0. 1.]
#  [1. 0. 0. 1. 1. 0. 0. 1. 0. 1. 0. 1. 0.]
#  [1. 1. 0. 0. 0. 1. 0. 1. 1. 0. 0. 1. 0.]
#  [1. 0. 0. 1. 1. 0. 1. 0. 0. 0. 1. 0. 1.]]

print(enc.get_feature_names_out())  # 独热编码对应的原始特征
# ['x0_周六' 'x1_-' 'x1_吃饭' 'x1_逛街' 'x2_晴天' 'x2_雨天' 'x3_正常' 'x3_轻松' 'x4_严峻'
#  'x4_平缓' 'x4_清零' 'x5_无聊' 'x5_精彩']

特征缺失处理

最简单的方法就是直接删除有特征缺失的样本，信息丢失

补全：

• 用未缺失该特征的样本计算平均数、中位数、众数填充，引入噪声？
• 用没有缺失的特征学习并预测缺失特征的取值，若两者之间无关？
• 将“缺失”本身作为一种特征取值

特征缺失处理

import numpy as np
from sklearn.ensemble import ExtraTreesRegressor
from sklearn.experimental import enable_iterative_imputer
from sklearn.impute import IterativeImputer, SimpleImputer
from sklearn.neighbors import KNeighborsRegressor
from sklearn.tree import DecisionTreeRegressor

X = np.array([
    [1, '周六', '吃饭', '晴天', '轻松', '清零', '精彩', 25.2, 0.5],
    [6, '周六', '逛街', '晴天', '轻松', '平缓', '无聊', np.nan, 2.0],
    [10, '周六', '-', '雨天', '轻松', '严峻', '无聊', 32.6, 8.2],
    [13, '周六', '逛街', '晴天', '正常', '清零', '精彩', 36.4, 9.8],
])

imp_mean = SimpleImputer(strategy='mean')
print(imp_mean.fit_transform(X[:, [7]]))  # 用均值填充
# [[25.2]
#  [31.4]
#  [32.6]
#  [36.4]]

imp_median = SimpleImputer(strategy='median')
print(imp_median.fit_transform(X[:, [7]]))  # 用中位数填充
# [[25.2]
#  [32.6]
#  [32.6]
#  [36.4]]

imp_frequent = SimpleImputer(missing_values='-', strategy='most_frequent')
print(imp_frequent.fit_transform(X[:, [2]].astype('object')))  # 用众数填充
# [['吃饭']
#  ['逛街']
#  ['逛街']
#  ['逛街']]

# 回归器默认采用BayesianRidge
# 其它可选DecisionTreeRegressor ExtraTreesRegressor KNeighborsRegressor
imp_iter = IterativeImputer(estimator=KNeighborsRegressor(n_neighbors=2))
print(imp_iter.fit_transform(X[:, [0, 7, 8]]))
# [[ 1.  25.2  0.5]
#  [ 6.  28.9  2. ]
#  [10.  32.6  8.2]
#  [13.  36.4  9.8]]

特征标准化

也称归一化，旨在消除不同特征间的量纲影响

离差标准化：将原始特征线性变换到 [0, 1] 区间

$$ \begin{align*} \quad x \leftarrow \frac{x - x_\min}{x_\max - x_\min} \in [0,1] \end{align*} $$

最大值标准化：除以该特征的绝对值最大值

$$ \begin{align*} \quad x \leftarrow \frac{x}{\max_{i \in [m]} |x_i|} \in [-1,1] \end{align*} $$

标准差标准化：经过处理的特征近似符合标准正态分布$\Ncal(0,1)$

$$ \begin{align*} \quad x \leftarrow \frac{x - \mu}{\sigma}, \quad x \leftarrow \frac{x - x_{\text{median}}}{\sum_{i \in [m]} |x_i - x_{\text{median}}| / m} \end{align*} $$

特征标准化

import numpy as np
from sklearn.preprocessing import MaxAbsScaler, MinMaxScaler, scale

X = np.array([
    [1, '周六', '吃饭', '晴天', '轻松', '清零', '精彩', 25.2, 0.5],
    [6, '周六', '逛街', '晴天', '轻松', '平缓', '无聊', 27.4, 2.0],
    [10, '周六', '学习', '雨天', '轻松', '严峻', '无聊', 32.6, 8.2],
    [13, '周六', '逛街', '晴天', '正常', '清零', '精彩', 36.4, 9.8],
])

print(MinMaxScaler().fit_transform(X[:, [0, 7, 8]]))  # 最大值变成1 同时 最小值变成0
# [[0.         0.         0.        ]
#  [0.41666667 0.19642857 0.16129032]
#  [0.75       0.66071429 0.82795699]
#  [1.         1.         1.        ]]

print(MaxAbsScaler().fit_transform(X[:, [0, 7, 8]]))  # 最大值变成1
# [[0.07692308 0.69230769 0.05102041]
#  [0.46153846 0.75274725 0.20408163]
#  [0.76923077 0.8956044  0.83673469]
#  [1.         1.         1.        ]]

x = scale(X[:, [0, 7, 8]])
print(x)
# [[-1.44444444 -1.1861146  -1.17034706]
#  [-0.33333333 -0.68429689 -0.79077504]
#  [ 0.55555556  0.50181772  0.77812264]
#  [ 1.22222222  1.36859377  1.18299946]]

print(x.mean(axis=0), x.std(axis=0))  # 均值为0 标准差为1
# [ 5.55111512e-17  2.22044605e-16 -5.55111512e-17] [1. 1. 1.]

特征变换

模型学习前的最后一步，亦有将该步与模型学习融合的做法

当部分特征冗余甚至有害时，挑选或生成有用的特征子集

• 去除低方差特征，特别是那些在所有样本上取值均不变的特征
• 先计算 F 检验值、卡方检验值、互信息、线性相关性等统计量，然后据此设立阈值选择特征
• 引入$\ell_1$等稀疏范数作为约束，将选择特征与模型学习合二为一
• 通过 PCA、随机投影等降维技术浓缩现有特征

当特征稀缺时，利用现有特征构造新的特征

• 凭经验显式构造：$[x_1; x_2] \xrightarrow{\Rbb^2 \mapsto \Rbb^6} [x_1^2; x_2^2; \sqrt{2} x_1 x_2; \sqrt{2} x_1; \sqrt{2} x_2; 1]$
• 利用核函数$\kappa(\xv, \zv) = \phi(\xv)^\top \phi(\zv)$隐式构造，代表性方法为支持向量机
• 利用非线性函数复合$f_n ( f_{n-1} ( \cdots f_2 (f_1 (\xv))))$，代表性方法为神经网络

特征选择 低方差过滤

import numpy as np
from sklearn.feature_selection import VarianceThreshold

# 对6个离散类别特征采用了独热编码
X = np.array([
    [1., 1., 0., 0., 1., 0., 0., 1., 0., 0., 1., 0., 1.],
    [1., 0., 0., 1., 1., 0., 0., 1., 0., 1., 0., 1., 0.],
    [1., 0., 1., 0., 0., 1., 0., 1., 1., 0., 0., 1., 0.],
    [1., 0., 0., 1., 1., 0., 1., 0., 0., 0., 1., 0., 1.]
])
print(X.shape)
# (4, 13)

# 第1列由特征“时间”而来 四个样本都取值“周六” 独热编码后都是1 方差为0
XX = VarianceThreshold(threshold=0.01).fit_transform(X)
print(XX)
# [[1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 1.]
#  [0. 0. 1. 1. 0. 0. 1. 0. 1. 0. 1. 0.]
#  [0. 1. 0. 0. 1. 0. 1. 1. 0. 0. 1. 0.]
#  [0. 0. 1. 1. 0. 1. 0. 0. 0. 1. 0. 1.]]

print(XX.shape)
# (4, 12)

特征选择 方差分析

设共有$k$个类别，总样本数为$m = \sum_{i \in [k]} m_i$，总体均值为$\xbar$
设第$i$类第$j$个样本为$x_{ij}$，第$i$类的均值为$\xbar_i$，则总体偏差

$$ \begin{align*} \quad \sum_{i \in [k]} & \sum_{j \in [m_i]} (x_{ij} - \xbar)^2 = \sum_{i \in [k]} \sum_{j \in [m_i]} (x_{ij} - \xbar_i + \xbar_i - \xbar)^2 \\ & = \sum_{i \in [k]} \sum_{j \in [m_i]} [ (x_{ij} - \xbar_i)^2 + (\xbar_i - \xbar)^2 ] + \sum_{i \in [k]} 2 \underbrace{\sum_{j \in [m_i]} (x_{ij} - \xbar_i)}_{=~0} (\xbar_i - \xbar) \\ & = \sum_{i \in [k]} \sum_{j \in [m_i]} (x_{ij} - \xbar_i)^2 + \sum_{i \in [k]} m_i (\xbar_i - \xbar)^2 = \SSE + \SSB \end{align*} $$

• $\SSE$为各类样本与均值的偏差，越小说明每个类别各自聚集越紧密
• $\SSB$为各类均值与总体的偏差，越小说明不同类别的均值差异越小
• $F = \frac{\SSB/(k-1)}{\SSE/(m-k)}$越小，说明类别间差异越小

特征选择 方差分析

对任意特征根据类别标记一分为二计算$F$值，判断差异是否显著

对特征“次序”，总体均值$\xbar = 7.5$

• 正类特征$1,6$，均值$3.5$、偏差$2.5^2 + 2.5^2 = 12.5$
• 负类特征$10,13$，均值$11.5$、偏差$1.5^2 + 1.5^2 = 4.5$
• $\SSE = 12.5 + 4.5 = 17$，$\SSB = 2(3.5-7.5)^2 + 2(11.5-7.5)^2 = 64$
• $F = \frac{\SSB/(k-1)}{\SSE/(m-k)} = \frac{64/(2-1)}{17/(4-2)} = 7.52941176$

特征选择 方差分析

经独热编码，特征“是否无聊”的四个取值是$0,1,1,0$，均值$0.5$

• 正类特征均值$0.5$、偏差$0.5$，负类特征均值$0.5$、偏差$0.5$
• $\SSE = 0.5 + 0.5 = 1$，$\SSB = 0$，$F = \frac{\SSB/(k-1)}{\SSE/(m-k)} = 0$

import numpy as np
from sklearn.feature_selection import SelectKBest, f_classif

X = np.array([  # 已去掉方差为零的特征
    [1., 1., 0., 0., 1., 0., 0., 1., 0., 0., 1., 0., 1.],
    [6., 0., 0., 1., 1., 0., 0., 1., 0., 1., 0., 1., 0.],
    [10., 0., 1., 0., 0., 1., 0., 1., 1., 0., 0., 1., 0.],
    [13., 0., 0., 1., 1., 0., 1., 0., 0., 0., 1., 0., 1.],
])
y = [1, 1, 0, 0]

sk = SelectKBest(f_classif)
sk.fit_transform(X, y)
print(sk.scores_)
# [7.52941176 1.         1.         0.         1.         1.
#  1.         1.         1.         1.         0.         0.
#  0.        ]

特征选择 卡方检验

• 若随机变量$X$和$Y$独立，则$p(X,Y) = p(X) p(Y)$
• $|p(X,Y) - p(X) p(Y)|$可衡量$X$和$Y$的独立程度

• $X$是约会方式，$Y$是约会与否，总样本数为$4$
• 括号前观测频数$o = 4 \cdot p(X,Y)$，括号内期望频数$e = 4 \cdot p(X) p(Y)$

$$ \begin{align*} \quad \chi^2 = \sum_{ij} \frac{(o_{ij}-e_{ij})^2}{e_{ij}} = 4 \times \frac{(1 - 0.5)^2}{0.5} = 2 \end{align*} $$

特征选择 卡方检验

import numpy as np
from sklearn.feature_selection import SelectKBest, chi2

X = np.array([  # 已去掉方差为零的特征
    [1., 1., 0., 0., 1., 0., 0., 1., 0., 0., 1., 0., 1.],
    [6., 0., 0., 1., 1., 0., 0., 1., 0., 1., 0., 1., 0.],
    [10., 0., 1., 0., 0., 1., 0., 1., 1., 0., 0., 1., 0.],
    [13., 0., 0., 1., 1., 0., 1., 0., 0., 0., 1., 0., 1.],
])
y = [1, 1, 0, 0]

sk = SelectKBest(chi2)
sk.fit_transform(X, y)
print(sk.scores_)
# [8.53333333 1.         1.         0.         0.33333333 1.
#  1.         0.33333333 1.         1.         0.         0.
#  0.        ]

独热编码将约会方式分成三个特征，卡方检验值为$1 + 1 + 0 = 2$

特征选择 熵

熵 (entropy) 可以度量随机变量的不确定性

$$ \begin{align*} \quad H(X) = - \sum_{i \in [m]} p(x_i) \log p(x_i) = - \Ebb [\log p(X)], \quad 0 \log 0 \triangleq 0 \end{align*} $$

设离散随机变量$X \in \{a,b,c,d\}$且

$$ \begin{align*} \quad p(a) = \frac{1}{2}, ~ p(b) = \frac{1}{4}, ~ p(c) = \frac{1}{8}, ~ p(d) = \frac{1}{8} \end{align*} $$

根据定义$H(X) = \frac{1}{2} \log 2 + \frac{1}{4} \log 4 + \frac{1}{8} \log 8 + \frac{1}{8} \log 8 = \frac{7}{4}$

霍夫曼编码：设最优前缀码为$a:0$、$b:10$、$c:110$、$d:111$

期望编码长度为$\frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 + \frac{1}{8} \cdot 3 = \frac{7}{4}$

霍夫曼编码是一种熵编码

特征选择 熵的极值

熵 (entropy) 可以度量随机变量的不确定性

$$ \begin{align*} \quad H(X) = - \sum_{i \in [m]} p(x_i) \log p(x_i) = - \Ebb [\log p(X)], \quad 0 \log 0 \triangleq 0 \end{align*} $$

当$p(x_1) = \cdots = p(x_m) = 1/m$时，熵达到最大值$\log m$

拉格朗日函数$L = - \sum_{i \in [m]} p(x_i) \log p(x_i) - \alpha (\sum_{i \in [m]} p(x_i) - 1)$

$$ \begin{align*} \quad \nabla_{p(x_i)} L = - \log p(x_i) - 1 - \alpha = 0 ~ \Longrightarrow ~ p(x_i) = \exp(-1-\alpha) = \frac{1}{m} \end{align*} $$

当某个$p(x_i) = 1$、其余为零时，熵达到最小值$0$

$$ \begin{align*} \quad H(X) = \sum_{i \in [m]} p(x_i) \log \frac{1}{p(x_i)} \ge \sum_{i \in [m]} p(x_i) \log 1 = 0 \end{align*} $$

特征选择 条件熵

联合熵：两个随机变量的联合不确定性

$$ \begin{align*} \quad H(X,Y) = - \sum_{i \in [m]} \sum_{j \in [n]} p(x_i,y_j) \log p(x_i,y_j) = - \Ebb [\log p(X,Y)] \end{align*} $$

条件熵：给定一个随机变量，另一个随机变量还具有的不确定性

$$ \begin{align*} \quad H(X|Y) & = H(X,Y) - H(Y) \\ & = - \sum_{i \in [m]} \sum_{j \in [n]} p(x_i,y_j) \log p(x_i,y_j) + \sum_{j \in [n]} \class{blue}{p(y_j)} \log p(y_j) \\ & = - \sum_{i \in [m]} \sum_{j \in [n]} p(x_i,y_j) \log p(x_i,y_j) + \sum_{j \in [n]} \class{blue}{\sum_{i \in [m]} p(x_i,y_j)} \log p(y_j) \\ & = - \sum_{i \in [m]} \sum_{j \in [n]} p(x_i,y_j) \log p(x_i|y_j) \\ & = - \Ebb [\log p(X|Y)] \end{align*} $$

特征选择 互信息

互信息：给定一个随机变量，另一个随机变量不确定性的缩减量

$$ \begin{align*} \quad I(X; Y) & = H(X) - H(X|Y) \\ & = - \sum_{i \in [m]} \class{blue}{p(x_i)} \log p(x_i) + \sum_{i \in [m]} \sum_{j \in [n]} p(x_i,y_j) \log p(x_i|y_j) \\ & = - \sum_{i \in [m]} \class{blue}{\sum_{j \in [n]} p(x_i,y_j)} \log p(x_i) + \sum_{i \in [m]} \sum_{j \in [n]} p(x_i,y_j) \log \frac{p(x_i,y_j)}{p(y_j)} \\ & = - \sum_{i \in [m]} \sum_{j \in [n]} p(x_i,y_j) \log \frac{p(x_i)p(y_j)}{p(x_i,y_j)} \\ & = \Ebb \left[ \log \frac{p(X,Y)}{p(X)p(Y)} \right] \end{align*} $$

由对称性可知$I(X; Y) = H(Y) - H(Y|X)$

特征选择 互信息

互信息 (交集) 与熵、联合熵 (并集)、条件熵 (差集) 的关系为

$$ \begin{align*} \quad I(X;Y) & = H(X) - H(X|Y) = H(Y) - H(Y|X) \\ & = H(X) + H(Y) - H(X,Y) \\ & = H(X,Y) - H(X|Y) - H(Y|X) \end{align*} $$

特征选择 互信息

利用每个特征和类别标记之间的互信息进行挑选

import numpy as np
from sklearn.feature_selection import SelectKBest, mutual_info_classif

np.random.seed(0)

X = np.array([  # 已去掉方差为零的特征
    [1., 1., 0., 0., 1., 0., 0., 1., 0., 0., 1., 0., 1.],
    [6., 0., 0., 1., 1., 0., 0., 1., 0., 1., 0., 1., 0.],
    [10., 0., 1., 0., 0., 1., 0., 1., 1., 0., 0., 1., 0.],
    [13., 0., 0., 1., 1., 0., 1., 0., 0., 0., 1., 0., 1.],
])
y = [1, 1, 0, 0]

sk = SelectKBest(mutual_info_classif)
sk.fit_transform(X, y)
print(sk.scores_)
# [0.58333333 0.20833333 0.08333333 0.         0.08333333 0.
#  0.         0.         0.20833333 0.         0.         0.
#  0.        ]

特征选择 稀疏范数

范数$\|\cdot\|$：长度概念的推广，对任意标量$\alpha$和向量空间中的$\uv, \vv$

• 正定性：$\| \uv \| \ge 0$，且$\| \uv \| = 0$当且仅当$\uv = \zerov$
• 齐次性：$\| \alpha \uv \| = |\alpha| \cdot \| \uv \|$
• 三角不等式：$\| \uv + \vv \| \le \| \uv \| + \| \vv \|$

机器学习中常用的是向量的$\ell_p$范数：$\| \wv \|_p \triangleq (\sum_{i \in [d]} |w_i|^p)^{1/p}$

• $\ell_1$范数：$\| \wv \|_1 = \sum_{i \in [d]} |w_i|$，各元素绝对值之和
• $\ell_2$范数：$\| \wv \|_2 = \sqrt{\sum_{i \in [d]} w_i^2}$，各元素平方和的正平方根
• $\ell_\infty$范数：$\| \wv \|_\infty = \max_{i \in [d]} |w_i|$，各元素绝对值的最大值

当$0 \le p < 1$时，$\| \cdot \|_p$不再是合法的范数，不满足三角不等式

• $\ell_0$范数：$\| \wv \|_0 = |\{ i \in [d] \mid w_i \ne 0 \}|$，非零元素的个数

特征选择 稀疏范数

$\Rbb^2$上的 5 个$\ell_p$范数球$\{ \wv \mid \| \wv \|_p \le t \}$

• 将$\ell_p~(0 \le p \le 1)$范数球作为学习模型的可行域，可导出稀疏的解
• 所有$\ell_p~(p \ge 1)$范数球都是凸集，数学性质好

$\ell_1$唯一既凸且稀疏，将其范数球作为$\Rbb^2$上最小二乘的可行域

$$ \begin{align*} \quad \min_{w_1, w_2} ~ \left \| \begin{bmatrix} 6.590 & -0.654 \\ 1.498 & 0.413 \\ -2.550 & 1.682 \\ -5.538 & -1.441 \\ \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ \end{bmatrix} \right\|^2, \quad \st ~ |w_1| + |w_2| \le t \end{align*} $$

特征选择 稀疏范数

• 左图中以原点为中心的同心正方形是$\ell_1$范数球的等高线
• 右图中以原点为中心的同心圆是$\ell_2$范数球的等高线
• 两图中右边的一系列同心椭圆是$\| \Xv \wv - \yv \|^2$的等高线

椭圆与正方形必然交于正方形的顶点处，即最优的$w_2 = 0$

特征变换 主成分分析

构造$\Rbb^D$中的标准正交基$\wv_1, \ldots, \wv_d$，将样本投到该$d$维子空间

$$ \begin{align*} \quad \Xv \in \Rbb^{m \times D} \xrightarrow[\text{降维}]{\Wv = [\wv_1, \ldots, \wv_d] \in \Rbb^{D \times d}} \Xv \Wv \in \Rbb^{m \times d} \xrightarrow[\text{重构}]{\Wv^\top \in \Rbb^{d \times D}} \Xv \Wv \Wv^\top \end{align*} $$

投影到$d ~ (<D)$维子空间存在信息损失，$\Wv$应使得重构误差小

$$ \begin{align*} \quad \| \Xv & - \Xv \Wv \Wv^\top \|_F^2 = \tr [(\Xv - \Xv \Wv \Wv^\top) (\Xv - \Xv \Wv \Wv^\top)^\top] \\ & = \tr [\Xv \Xv^\top - 2 \Xv \Wv \Wv^\top \Xv^\top + \Xv \Wv \class{blue}{\Wv^\top \Wv} \Wv^\top \Xv^\top] \\ & = \tr [\Xv \Xv^\top - \Xv \Wv \Wv^\top \Xv^\top] \qquad \longleftarrow ~ \Wv^\top \Wv = \Iv \\ & = \const - \tr [\Wv^\top \Xv^\top \Xv \Wv] \qquad \longleftarrow ~ \tr [\Av \Bv] = \tr [\Bv \Av] \\ & = \const - \wv_1^\top \Xv^\top \Xv \wv_1 - \cdots - \wv_d^\top \Xv^\top \Xv \wv_d \\[5pt] & \Longrightarrow \quad \mathop{\mathrm{argmin}}_{\Wv^\top \Wv = \Iv} \| \Xv - \Xv \Wv \Wv^\top \|_F^2 = \mathop{\mathrm{argmax}}_{\Wv^\top \Wv = \Iv} \sum_{i \in [d]} \wv_i^\top \Xv^\top \Xv \wv_i \end{align*} $$

特征变换 主成分分析

$$ \begin{align*} \quad \mathop{\mathrm{argmin}}_{\Wv^\top \Wv = \Iv} \| \Xv & - \Xv \Wv \Wv^\top \|_F^2 = \mathop{\mathrm{argmax}}_{\Wv^\top \Wv = \Iv} \sum_{i \in [d]} \wv_i^\top \Xv^\top \Xv \wv_i \end{align*} $$

假设已平移样本使其中心在原点，即$\onev^\top \Xv = \zerov$

$\Xv \wv_1$是样本在投影方向$\wv_1$上的投影，投影均值$\onev^\top \Xv \wv_1 = 0$

$$ \begin{align*} \quad \wv_1^\top \Xv^\top \Xv \wv_1 = \sum_{i \in [m]} (\xv_i^\top \wv_1)^2 = \sum_{i \in [m]} (\xv_i^\top \wv_1 - 0)^2 = \var [\xv_i^\top \wv_1] \end{align*} $$

最小化重构误差等价最大化投影方差，即投影后样本尽可能散开

拉格朗日函数$L = \wv_1^\top \Xv^\top \Xv \wv_1 - \alpha (\wv_1^\top \wv_1 - 1)$

$$ \begin{align*} \quad \nabla_{\wv_1} L = 2 \Xv^\top \Xv \wv_1 - 2 \alpha \wv_1 = \zerov \Longrightarrow \mathtip{\wv_1^\top \Xv^\top \Xv \wv_1 = \alpha}{\wv_1应为\Xv^\top \Xv最大特征值对应的特征向量} \end{align*} $$

特征变换 主成分分析

主成分分析 (PCA)：寻找一组投影方向 (成分) 使重构误差最小

特征变换 主成分分析

主成分分析 (PCA)：寻找一组投影方向 (成分) 使重构误差最小

import numpy as np
from sklearn.decomposition import PCA

X = np.array([
    [1., 1., 0., 0., 1., 0., 0., 1., 0., 0., 1., 0., 1.],
    [6., 0., 0., 1., 1., 0., 0., 1., 0., 1., 0., 1., 0.],
    [10., 0., 1., 0., 0., 1., 0., 1., 1., 0., 0., 1., 0.],
    [13., 0., 0., 1., 1., 0., 1., 0., 0., 0., 1., 0., 1.],
])

pca = PCA(n_components=3)
XX = pca.fit_transform(X)
print(XX)
# [[ 6.59008618 -0.65420003 -0.62672674]
#  [ 1.49765996  0.41345689  1.35501589]
#  [-2.55003899  1.68197454 -0.64673241]
#  [-5.53770716 -1.4412314  -0.08155674]]

print(np.linalg.norm(X - pca.inverse_transform(XX)))
# 3.1659611182970852e-15

pca = PCA(n_components=2)
XX = pca.fit_transform(X)
print(XX)
# [[ 6.59008618 -0.65420003]
#  [ 1.49765996  0.41345689]
#  [-2.55003899  1.68197454]
#  [-5.53770716 -1.4412314 ]]

print(np.linalg.norm(X - pca.inverse_transform(XX)))
# 1.6290392142641008

特征变换 随机投影

Johnson–Lindenstrauss (JL) 定理：给定$\epsilon \in (0,1)$和正整数$m$，设整数$d$满足$d \ge 4 (\epsilon^2/2 - \epsilon^3/3)^{-1} \ln m$，则对$\Rbb^D$中的任意$m$个点组成的集合$\Scal$，存在可在随机多项式时间内得到的线性映射$f: \Rbb^D \mapsto \Rbb^d$使得对$\forall \uv, \vv \in \Scal$有

$$ \begin{align*} \quad (1 - \epsilon) \| \uv -\vv \|^2 \le \| f(\uv) - f(\vv) \|^2 \le (1 + \epsilon) \| \uv - \vv \|^2 \end{align*} $$

高维空间中的点集可线性映射到低维空间且相对保持距离

投影矩阵通常采用

• 高斯随机矩阵：从高斯分布$\Ncal(0,1/d)$中采样
• 稀疏随机矩阵：以$1/2s$的概率取$\pm \sqrt{s/d}$，以$1-1/s$的概率取$0$

特征变换 随机投影

import numpy as np
from scipy.spatial import distance
from sklearn import random_projection

np.random.seed(0)

X = np.random.rand(100, 10000)
D1 = distance.cdist(X, X, 'euclidean')  # 原样本的成对距离矩阵

transformer = random_projection.GaussianRandomProjection()  # 高斯随机矩阵
XX = transformer.fit_transform(X)
print(XX.shape)
# (100, 3947)

D2 = distance.cdist(XX, XX, 'euclidean')  # 投影后样本的成对距离矩阵
print(np.linalg.norm(D1 - D2, ord='fro'))  # 两个成对距离矩阵差的F范数
# 45.5042470391125

transformer = random_projection.SparseRandomProjection()  # 稀疏随机矩阵
XX = transformer.fit_transform(X)
print(XX.shape)
# (100, 3947)

D2 = distance.cdist(XX, XX, 'euclidean')  # 投影后样本的成对距离矩阵
print(np.linalg.norm(D1 - D2, ord='fro'))  # 两个成对距离矩阵差的F范数
# 45.20040904607192

特征变换

模型学习前的最后一步，亦有将该步与模型学习融合的做法

当部分特征冗余甚至有害时，挑选或生成有用的特征子集

• 去除低方差特征，特别是那些在所有样本上取值均不变的特征
• 先计算 F 检验值、卡方检验值、互信息、线性相关性等统计量，然后据此设立阈值选择特征
• 引入$\ell_1$等稀疏范数作为约束，将选择特征与模型学习合二为一
• 通过 PCA、随机投影等降维技术浓缩现有特征

当特征稀缺时，利用现有特征构造新的特征

• 凭经验显式构造：$[x_1; x_2] \xrightarrow{\Rbb^2 \mapsto \Rbb^6} [x_1^2; x_2^2; \sqrt{2} x_1 x_2; \sqrt{2} x_1; \sqrt{2} x_2; 1]$
• 利用核函数$\kappa(\xv, \zv) = \phi(\xv)^\top \phi(\zv)$隐式构造，代表性方法为支持向量机
• 利用非线性函数复合$f_n ( f_{n-1} ( \cdots f_2 (f_1 (\xv))))$，代表性方法为神经网络

特征变换 构造新特征

凭经验显式构造映射$\phi$，如二次多项式特征：

$$ \begin{align*} \quad [x_1; x_2] \xrightarrow{\phi: ~ \Rbb^2 \mapsto \Rbb^6} [x_1^2; x_2^2; \sqrt{2} x_1 x_2; \sqrt{2} x_1; \sqrt{2} x_2; 1] \end{align*} $$

• 圆内是一类样本，圆外是另一类样本，它们无法线性可分
• 令$[x_1; x_2] \mapsto [z_1 = x_1^2; z_2 = x_2^2]$，在新的$(z_1,z_2)$空间中就线性可分了

$$ \begin{align*} \quad x_1^2 + x_2^2 \le t ~ \longrightarrow ~ z_1 + z_2 \le t \end{align*} $$

特征变换 核函数

核函数$\kappa(\cdot, \cdot)$是双变量对称函数，常见的有：

• 线性核$\kappa (\xv, \zv) = \xv^\top \zv$，相当于用了恒等核映射$\phi(\xv) = \xv$
• 多项式核$\kappa (\xv, \zv) = (\xv^\top \zv + k)^d$，$k = 0$则为齐次多项式核，$d \in \Zbb_+$
• 高斯核$\kappa (\xv, \zv) = \exp (- \| \xv - \zv \|_2^2 / 2 \sigma^2)$，$\sigma > 0$为高斯核的带宽 (width)
• 拉普拉斯核$\kappa (\xv, \zv) = \exp (- \| \xv - \zv \|_1 / \sigma)$，$\sigma > 0$

将 PCA 中的样本$\xv$用$\phi(\xv)$替代即核 PCA，先升维再降维

$\quad \max_{\|\wv\|_2^2 = 1} \wv^\top \Xv^\top \Xv \wv \overset{\phi}{\longrightarrow} \max_{\|\wv\|_2^2 = 1} \wv^\top \phi(\Xv)^\top \phi(\Xv) \wv$

其中$\Xv = \begin{bmatrix} \xv_1^\top \\ \vdots \\ \xv_m^\top \end{bmatrix}$、$\phi(\Xv) = \begin{bmatrix} \phi(\xv_1)^\top \\ \vdots \\ \phi(\xv_m)^\top \end{bmatrix}$，注意$\wv$的维度不一样

特征变换 核 PCA

问题：如何让模型中只出现内积$\phi(\xv_i)^\top \phi(\xv_j)$的形式？

对$\wv$做正交分解$\wv = \sum_{i \in [m]} \alpha_i \phi(\xv_i) + \vv = \phi(\Xv)^\top \alphav + \vv$，其中

$$ \begin{align*} \quad \vv \perp \span \{ \phi(\xv_1), \ldots, \phi(\xv_m) \} ~ \Longrightarrow ~ \phi(\Xv) \vv = \zerov \end{align*} $$

于是

$$ \begin{align*} \quad & \|\wv\|_2^2 = \alphav^\top \phi(\Xv) \phi(\Xv)^\top \alphav + \vv^\top \vv = \alphav^\top \Kv \alphav + \vv^\top \vv \\ & \phi(\Xv) \wv = \phi(\Xv) (\phi(\Xv)^\top \alphav + \vv) = \phi(\Xv) \phi(\Xv)^\top \alphav = \Kv \alpha \\ & \Kv = \phi(\Xv) \phi(\Xv)^\top = \begin{bmatrix} \phi(\xv_1)^\top \phi(\xv_1) & \cdots & \phi(\xv_1)^\top \phi(\xv_m) \\ \vdots & \ddots & \vdots \\ \phi(\xv_m)^\top \phi(\xv_1) & \cdots & \phi(\xv_m)^\top \phi(\xv_m) \end{bmatrix} \end{align*} $$

核 PCA 可重写为 $\max_{\alphav, \vv} ~ \alphav^\top \Kv \Kv \alphav, ~ \st ~ \alphav^\top \Kv \alphav + \vv^\top \vv = 1$

特征变换 核 PCA

核 PCA：$\max_{\alphav, \vv} ~ \alphav^\top \Kv \Kv \alphav, ~ \st ~ \alphav^\top \Kv \alphav + \vv^\top \vv = 1$

设最优解为$(\alphav_\star, ~ \vv_\star)$，下面说明$\vv_\star = \zerov$

• 若$\vv_\star^\top \vv_\star = c > 0$，则$\alphav_\star^\top \Kv \alphav_\star = 1 - c < 1$
• $(\alphav_0 = 1 / \sqrt{1-c} ~ \alphav_\star, ~ \vv_0 = \zerov)$也是一组可行解
• 显然$\alphav_0^\top \Kv \Kv \alphav_0 = \alphav_\star^\top \Kv \Kv \alphav_\star / (1-c) > \alphav_\star^\top \Kv \Kv \alphav_\star$，这与$\alphav_\star$最优矛盾

核 PCA 的最终形式为 $\max_\alphav ~ \alphav^\top \Kv \Kv \alphav, ~ \st ~ \alphav^\top \Kv \alphav = 1$

通过拉格朗日乘子法求得$\alphav$后，样本$\xv_j$在成分$\wv$上的投影为

$$ \begin{align*} \quad \wv^\top \phi(\xv_j) = \sum_{i \in [m]} \alpha_i \phi(\xv_i)^\top \phi(\xv_j) = \sum_{i \in [m]} \alpha_i \kappa (\xv_i, \xv_j) \end{align*} $$

通过核 PCA 可以看出，全程我们都用不到$\phi(\cdot)$，只需要$\kappa(\cdot, \cdot)$