前言

最近在准备暑期实习面试，正好看到一本书叫《百面机器学习》。粗略翻了下，感觉知识点还比较全面，但是有些知识点讲解不够细致。所以准备按照书中知识点的顺序复习一下，同时对其中一些内容进行补充总结。

第一章 特征工程

1. 特征归一化

问题 特征归一化作用
数据标准化（归一化）处理是数据挖掘的一项基础工作，不同评价指标往往具有不同的量纲和量纲单位，这样的情况会影响到数据分析的结果，为了消除指标之间的量纲影响，需要进行数据标准化处理，以解决数据指标之间的可比性。原始数据经过数据标准化处理后，各指标处于同一数量级，适合进行综合对比评价。
两种常用方法：

1. 线性函数归一化（Min-Max Scaling）。对原始数据进行线性变换，使结果映射到[0, 1]的范围，实现对原始数据的等比缩放。
   $X_{norm}=\frac{X-X_{min}}{X_{max}-X_{min}}$Xnorm​=Xmax​−Xmin​X−Xmin​​
2. 零均值归一化（Z-Socre Normalization）。将原始数据映射到均值为0、标准差为1的分布上。具体来说，假设原始特征的均值为μ、标准差为σ，那么归一化公式定义为:
   $z=\frac{x-\mu }{\sigma }$z=σx−μ​

同时，特征归一化可以加快训练速度，具体见下图。

x1和x2的更新速度变得更为一致，容易更快地通过梯度下降找到最优解。
但是，数据归一化并不是万能的。在实际应用中，通过梯度下降法求解的模型通常是需要归一化的，包括线性回归、逻辑回归、支持向量机、神经网络等模型。但对于决策树模型则并不适用，以C4.5为例，决策树在进行节点分裂时主要依据数据集D关于特征x的信息增益比，而信息增益比跟特征是否经过归一化是无关的，因为归一化并不会改变样本在特征x上的信息增益。

2. 类别性特征

问题 在对数据进行预处理时，怎么样处理类别型特征？

类别型特征（categorical feature）主要是指年龄，职业，血型等在有限类别内取值的特征。它的原始输入通常是字符串形式，除了决策树族的算法能直接接受类别型特征作为输入，对于支持向量机，逻辑回归等模型来说，必须对其做一定的处理，转换成可靠的数值特征才能正确运行。

四种常见转换方法：

1. 序号编码
   序号编码通常用于处理类别间具有大小关系的数据。例如成绩，可以分为低、中、高三档，并且存在“高>中>低”的排序关系。序号编码会按照大小关系对类别型特征赋予一个数值ID，例如高表示为3、中表示为2、低表示为1，转换后依然保留了大小关系。
2. 独热编码（One-hot）
   独热编码通常用于处理类别间不具有大小关系的特征。例如血型，一共有4个取值（A型血、B型血、AB型血、O型血），独热编码会把血型变成一个4维稀疏向量，A型血表示为（1, 0, 0, 0），B型血表示为（0, 1, 0, 0），AB型表示为（0, 0, 1, 0），O型血表示为（0, 0, 0, 1）。对于类别取值较多的情况下使用独热编码需要注意以下问题。
   （1）使用稀疏向量来节省空间。在独热编码下，特征向量只有某一维取值为1，其他位置取值均为0。因此可以利用向量的稀疏表示有效地节省空间，并且目前大部分的算法均接受稀疏向量形式的输入。
   （2）配合特征选择来降低维度。高维度特征会带来几方面的问题。一是在K近邻算法中，高维空间下两点之间的距离很难得到有效的衡量；二是在逻辑回归模型中，参数的数量会随着维度的增高而增加，容易引起过拟合问题；三是通常只有部分维度是对分类、预测有帮助，因此可以考虑配合特征选择来降低维度。
3. 二进制编码
   二进制编码主要分为两步，先用序号编码给每个类别赋予一个类别ID，然后将类别ID对应的二进制编码作为结果。以A、B、AB、O血型为例，表1.1是二进制编码的过程。A型血的ID为1，二进制表示为001；B型血的ID为2，二进制表示为010；以此类推可以得到AB型血和O型血的二进制表示。可以看出，二进制编码本质上是利用二进制对ID进行哈希映射，最终得到0/1特征向量，且维数少于独热编码，节省了存储空间。
4. 统计编码
   统计各类别在训练集中出现的频率，并将频率作为新的特征。统计各类别在训练集中出现的频率，并将频率作为新的特征。在某些情况下，具有统计意义的统计编码也是一种值得尝试的技巧。

3. 组合特征处理

问题 什么是组合特征？如何处理高维组合特征？

为了提高复杂关系的拟合能力，在特征工程中经常会把一阶离散特征两两组合，构成高阶组合特征。

高维组合特征可以进行矩阵分解。

问题 怎样有效找到组合特征？

在很多实际问题中，我们常常需要面对多种高维特征。如果简单地两两组合，依然容易存在参数过多、过拟合等问题，而且并不是所有的特征组合都是有意义的。因此，需要一种有效的方法来帮助我们找到应该对哪些特征进行组合。

可以利用决策树进行特征选择。构造决策树具体请见后面决策树部分。

4. 文本表示模型

问题 有哪些文本表示模型？它们各有什么优缺点？

• 词袋模型
  最基础的文本表示模型是词袋模型。顾名思义，就是将每篇文章看成一袋子词，并忽略每个词出现的顺序。具体地说，就是将整段文本以词为单位切分开，然后每篇文章可以表示成一个长向量，向量中的每一维代表一个单词，而该维对应的权重则反映了这个词在原文章中的重要程度。常用TF-IDF来计算权重，公式为
  $TFIDF(t,d)=TF(t,d)\ast IDF\left(t\right)$TFIDF(t,d)=TF(t,d)∗IDF(t)
  其中，TF(t,d)为单词t在文档d中出现的频率，IDF(t)是逆文档频率，用来衡量单词t对表达语义所起的重要性。
  $T{F}_{i,j}=\frac{n_{i,j}}{\sum _k{n}_{k,j}}$TFi,j​=∑k​nk,j​ni,j​​
  $ID{F}_i=log\frac{文章总数}{包含单词i的文章总数+1}$IDFi​=log包含单词i的文章总数+1文章总数​
• N-gram模型
  将文章进行单词级别的划分有时候并不是一种好的做法，比如英文中的natural language processing（自然语言处理）一词，如果将natural，language，processing这3个词拆分开来，所表达的含义与三个词连续出现时大相径庭。因此考虑N-gram模型。
  假设我们有一个由n个词组成的句子 $S=(w_1,w_2,\cdots ,w_n)$S=(w1​,w2​,⋯,wn​)，如何衡量它的概率呢？让我们假设，每一个单词 $w_i$wi​都要依赖于从第一个单词 $w_1$w1​到它之前一个单词 $w_{i-1}$wi−1​的影响：
  $p\left(S\right)=p(w_1,w_2,...,w_n)=p\left(w_1\right)p\left(w_2\mid w_1\right)...p(w_n\mid w_1,w_2...w_{n-1})$p(S)=p(w1​,w2​,...,wn​)=p(w1​)p(w2​∣w1​)...p(wn​∣w1​,w2​...wn−1​)
  原理很好理解，但是这种衡量方法有两个重大缺陷：
  1.参数空间过大，概率 p(wn|wn−1⋯w2w1)p(wn|wn−1⋯w2w1) 的参数有 O(n)O(n) 个。
  2.数据稀疏严重，词同时出现的情况可能没有，组合阶数高时尤其明显。
  为了解决第一个问题，引入马尔科夫假设（Markov Assumption）：一个词的出现仅与它之前的若干个词有关。即 $p(w_1\cdots w_n)=\prod p\left(w_i\mid wi-1...w_1\right)\approx \prod p\left(w_i\mid w_{i-1}...w_{i-N+1}\right)$p(w1​⋯wn​)=∏p(wi​∣wi−1...w1​)≈∏p(wi​∣wi−1​...wi−N+1​)
  如果一个词的出现仅依赖于它前面出现的一个词，那么我们就称之为 Bi-gram：
  $p\left(S\right)=p\left(w_1{w}_2...w_n\right)=p\left(w_1\right)p\left(w_2\mid w_1\right)...p\left(w_n\mid w_n-1\right)$p(S)=p(w1​w2​...wn​)=p(w1​)p(w2​∣w1​)...p(wn​∣wn​−1)
  如果一个词的出现仅依赖于它前面出现的两个词，那么我们就称之为 Tri-gram：
  $p\left(S\right)=p\left(w_1{w}_2...w_n\right)=p\left(w_1\right)p\left(w_2\mid w_1\right)...p\left(w_n\mid w_{n-1}{w}_{n-2}\right)$p(S)=p(w1​w2​...wn​)=p(w1​)p(w2​∣w1​)...p(wn​∣wn−1​wn−2​)
  具体如何计算其中的每一项条件概率 p(wn|wn−1⋯w2w1)p(wn|wn−1⋯w2w1) 呢？答案是极大似然估计（Maximum Likelihood Estimation，MLE）。
  $p\left(w_n\mid w_{n-1}\right)=\frac{C\left(w_{n-1}{w}_n\right)}{C\left(w_{n-1}\right)}$p(wn​∣wn−1​)=C(wn−1​)C(wn−1​wn​)​
  $p\left(w_n\mid w_{n-1}...w_2{w}_1\right)=\frac{C\left(w_1{w}_2...w_n\right)}{C\left(w_1{w}_2...w_{n-1}\right)}$p(wn​∣wn−1​...w2​w1​)=C(w1​w2​...wn−1​)C(w1​w2​...wn​)​
  一个简单的例子：
  垃圾短信分类问题，我们可以用N-gram来解决。在朴素贝叶斯的基础上，稍微对条件概率做一点改动即可。
  $p\left(垃圾短信\mid \mathrm{\"}在家日赚百万\mathrm{\"}\right)\propto p\left(垃圾邮件\right)p\left(\mathrm{\"}在家日赚百万\mathrm{\"}\mid 垃圾短信\right)$p(垃圾短信∣"在家日赚百万")∝p(垃圾邮件)p("在家日赚百万"∣垃圾短信)
  条件概率不再是各词语之间独立：
  $p\left(\mathrm{\"}在家日赚百万\mathrm{\"}\mid J\right)=p(\mathrm{\"}在\mathrm{\"},\mathrm{\"}家\mathrm{\"},\mathrm{\"}日\mathrm{\"},\mathrm{\"}赚\mathrm{\"},\mathrm{\"}百\mathrm{\"},\mathrm{\"}万\mathrm{\"}\mid J)=p\left(\mathrm{\"}在\mathrm{\"}\mid J\right)\times p(\mathrm{\"}家\mathrm{\"}\mid \mathrm{\"}在\mathrm{\"},J)\times p(\mathrm{\"}日\mathrm{\"}\mid \mathrm{\"}家\mathrm{\"},J)\times p(\mathrm{\"}赚\mathrm{\"}\mid \mathrm{\"}日\mathrm{\"},J)\times p(\mathrm{\"}百\mathrm{\"}\mid \mathrm{\"}赚\mathrm{\"},J)\times p(\mathrm{\"}万\mathrm{\"}\mid \mathrm{\"}百\mathrm{\"},J)$p("在家日赚百万"∣J)=p("在","家","日","赚","百","万"∣J)=p("在"∣J)×p("家"∣"在",J)×p("日"∣"家",J)×p("赚"∣"日",J)×p("百"∣"赚",J)×p("万"∣"百",J)
  垃圾短信分类问题可以总结为以下三个步骤：
  步骤一：给短信的每个句子断句。
  步骤二：用N-gram判断每个句子是否垃圾短信中的敏感句子。
  步骤三：若敏感句子个数超过一定阈值，认为整个邮件是垃圾短信。
  更多细节可以参考这篇博客
• 主题模型
  主题模型用于从文本库中发现有代表性的主题（得到每个主题上面词的分布特性），并且能够计算出每篇文章的主题分布，具体细节在概率图模型部分再讲。
• 词嵌入与深度学习模型
  所谓词嵌入，主要是将每个词都映射成低维空间上的一个稠密向量。K维空间的每一位可以看做一个隐含的主题，只是不像主题模型中的主题那样直观。
  词向量提出之前，一般使用one-hot编码进行文本特征表示。但one-hot存在以下缺陷：
  1.它是一个词袋模型，没考虑词的顺序。词嵌入弥补了one-hot向量表示过于稀疏的特性。
  2.one-hot向量非常稀疏，造成维度灾难。
  3.任意词之间都是孤立的，不能体现语义层面上词语之间的相关性。
  为了解决以上缺陷，人们提出词嵌入的想法。
  关于词向量的使用，我们可以利用余弦距离等方法衡量词的相似性。另外，在做一些有监督的上游任务时，我们可以将预训练的词向量作为文本底层特征输入CNN、RNN等网络。

5. Word2Vec & GloVe

Word2Vec

模型结构：

word2vec对原始的NNLM模型做如下改造：

• 移除前向反馈神经网络中非线性的hidden layer，直接将中间层的Embedding layer与输出层的softmax layer连接；
• 忽略上下文环境的序列信息：输入的所有词向量均汇总到同一个Embedding layer；
• 将Future words纳入上下文环境

word2vec有两种网络结构——CBOW和Skip-gram。
CBOW模型的任务是利用一个词的上下文预测这个词，对数似然函数：
$L=\sum _{w\in C}logp\left(w\mid Context\right(w\left)\right)$L=w∈C∑​logp(w∣Context(w))

• 输入层：上下文单词的one-hot. {假设单词向量空间dim为V，上下文单词个数为C}
• 所有one-hot分别乘以共享的输入权重矩阵W. （VxN矩阵，N为词向量维数，初始化权重矩阵W）
• 所得的向量 相加求平均作为隐层向量, size为1xN.
• 乘以输出权重矩阵W’ {NxV}
• 得到向量 {1V} 激活函数处理得到V-dim概率分布 {PS: 因为是onehot嘛，其中的每一维斗代表着一个单词}
• 概率最大的index所指示的单词为预测出的中间词（target word）与true label的one-hot做比较，误差越小越好（根据误差更新权重矩阵）

Skip-gram模型的任务与CBOW相反，是利用一个词去预测上下文的词，基本步骤也与CBOW类似。其对数似然函数：
$L=\sum _{w\in C}logp\left(Context\right(w\left)\mid w\right)$L=w∈C∑​logp(Context(w)∣w)
另外，为了提高训练效率，对于CBOW和Skip-gram两个模型，word2vec给出两套框架，分别基于Hierarchical Softmax和Negative Sampling进行设计。详细的数学公式推导可以看这篇博客和这篇博客，感觉写的很不错。
总结：

• CBOW训练速度快，适合语料较多的情况。因为Skip-gram进行预测的次数是要多于CBOW的：因为每个词在作为中心词时，都要使用周围词进行预测一次。这样相当于比cbow的方法多进行了K次（假设K为窗口大小），因此时间的复杂度为O(KV)，训练时间要比CBOW要长。当数据量较少，或者词为生僻词出现次数较少时， Skip-gram训练的词向量相对更加准确。
• Hierarchical Softmax相对比Negative Sampling要慢，但是对生僻字有利。

GloVe

GloVe的全称叫Global Vectors for Word Representation，它是一个基于全局词频统计（count-based & overall statistics）的词表征（word representation）工具，它可以把一个单词表达成一个由实数组成的向量，这些向量捕捉到了单词之间一些语义特性，比如相似性（similarity）、类比性（analogy）等。

GloVe与word2vec虽然都是词向量，但思路完全不同。GloVe主要利用统计共现矩阵。

定义符号：
$X_i=\sum _{j=1}^N{X}_{i,j}$Xi​=j=1∑N​Xi,j​ $P_{i,k}=\frac{X_{i,k}}{X_i}$Pi,k​=Xi​Xi,k​​ $rati{o}_{i,j,k}=\frac{P_{i,k}}{P_{j,k}}$ratioi,j,k​=Pj,k​Pi,k​​

推导：
假设已经得到词向量，则词向量和共现矩阵应该具有很好的一致性。假设词向量 $v_i,v_j,v_k$vi​,vj​,vk​计算 $rati{o}_{i,j,k}$ratioi,j,k​的函数为 $g(v_i,v_j,v_k)$g(vi​,vj​,vk​),则：
$\frac{P_{i,k}}{P_{j,k}}=rati{o}_{i,j,k}=g(v_i,v_j,v_k)$Pj,k​Pi,k​​=ratioi,j,k​=g(vi​,vj​,vk​)
需要等式左右尽可能接近，所以代价函数：
$J=\sum _{i,j,k}^N(\frac{P_{i,k}}{P_{j,k}}-g(v_i,v_j,v_k){)}^2$J=i,j,k∑N​(Pj,k​Pi,k​​−g(vi​,vj​,vk​))2
但是模型包括三个单词，复杂度N*N*N。
如何简化:

1. 要考虑单词i和j之间的关系，则g大概会有 $v_i-v_j$vi​−vj​;
2. $rati{o}_{i,j,k}$ratioi,j,k​是标量，g也应该是标量，所以g应该包含 $(v_i-v_j{)}^T{v}_k$(vi​−vj​)Tvk​;
3. 再套上指数运算$exp()$,最终 $g(v_i,v_j,v_k)=exp\left(\right(v_i-v_j{)}^T{v}_k)$g(vi​,vj​,vk​)=exp((vi​−vj​)Tvk​)

$\frac{P_{i,k}}{P_{j,k}}=g(v_i,v_j,v_k)$Pj,k​Pi,k​​=g(vi​,vj​,vk​) $\frac{P_{i,k}}{P_{j,k}}=exp\left(\right(v_i-v_j{)}^T{v}_k)$Pj,k​Pi,k​​=exp((vi​−vj​)Tvk​) $\frac{P_{i,k}}{P_{j,k}}=exp(v_i^T{v}_k-v_j^T{v}_k)$Pj,k​Pi,k​​=exp(viT​vk​−vjT​vk​) $\frac{P_{i,k}}{P_{j,k}}=\frac{exp\left(v_i^T{v}_k\right)}{exp\left(v_j^T{v}_k\right)}$Pj,k​Pi,k​​=exp(vjT​vk​)exp(viT​vk​)​
可以看出：
$P_{i,j}=exp\left(v_i^T{v}_j\right)$Pi,j​=exp(viT​vj​) $log\left(X_{i,j}\right)-log\left(X_i\right)=v_i^T{v}_j$log(Xi,j​)−log(Xi​)=viT​vj​ $log\left(X_{i,j}\right)=v_i^T{v}_j+b_i+b_j$log(Xi,j​)=viT​vj​+bi​+bj​
损失函数变为：
$J=\sum _{i,j}^N(v_i^T{v}_j+b_i+b_j-log(X_{i,j}){)}^2$J=i,j∑N​(viT​vj​+bi​+bj​−log(Xi,j​))2
基于出现频率越高的词对权重应该越大的原则，损失函数添加权重项：
$J=\sum _{i,j}^{N}f\left(X_{i,j}\right)(v_i^T{v}_j+b_i+b_j-log(X_{i,j}){)}^2$J=i,j∑N​f(Xi,j​)(viT​vj​+bi​+bj​−log(Xi,j​))2 $x=\{\begin{array}{cc}(x/xmax{)}^0.75,& \text{if }x\&lt;xmax\\ 1,& \text{if }x\&gt;=xmax\end{array}$x={(x/xmax)0.75,1,​if x<xmaxif x>=xmax​

6. 图像数据不足时的处理方法

一个模型所能提供的信息一般来源于两个方面，一是训练数据中蕴含的信息；二是在模型的形成过程中（包括构造、学习、推理等），人们提供的先验信息。

当训练数据不足时，往往会遇到过拟合的问题。对应的解决方法可以分为两大类：

1. 基于模型的方法：常用的降低过拟合的方法有简化模型、正则化、集成学习、Dropout、Early stopping等。
2. 基于数据的方法：主要通过数据扩充（Data Augmentation），即根据一些先验知识，在保持特定信息的前提下，对原始数据进行适当变换以达到扩充数据集的效果。

图像方面常用的数据增强方法有：

1. 空间几何变换类
   一定程度内的随机旋转、平移、缩放、裁剪、填充、左右翻转等，这些变换对应着同一个目标在不同角度的观察结果。
2. 对图像中的像素添加噪声扰动，比如椒盐噪声、高斯白噪声等。
3. 像素颜色变换类，高斯噪声等
4. 改变图像的亮度、清晰度、对比度、锐度等。

除了直接在图像空间进行变换，还可以先对图像进行特征提取，然后在图像的特征空间内进行变换，利用一些通用的数据扩充或上采样技术，例如SMOTE（Synthetic Minority Over-sampling Technique）算法。抛开上述这些启发式的变换方法，使用生成模型也可以合成一些新样本，例如现在非常流行的生成式对抗网络模型。

此外，借助已有的其他模型或数据来进行迁移学习在深度学习中也十分常见。例如，对于大部分图像分类任务，并不需要从头开始训练模型，而是借用一个在大规模数据集上预训练好的通用模型，并在针对目标任务的小数据集上进行微调（fine-tune），这种微调操作就可以看成是一种简单的迁移学习。