Category Archives: 数据挖掘与机器学习

异常点检测算法(三)Replicator Neural Networks

异常值检测算法在数据挖掘的诸多领域有着应用场景,例如金融领域,信息传输领域,图像领域等。在研究过程中,有学者给出了异常点的一个定义:

An outlier is an observation that deviates so much from other observations as as to arouse suspicion that it was generated by a different mechanism.

RNN 算法的主要思想

在这篇文章中,我们将会介绍一个多层的前馈神经网络,该神经网络可以用来进行异常值的检测。这个神经网络模拟的是一个恒等映射,输入层的神经元个数和输出层的神经元个数是一样的。这类的神经网络被称为 Replicator Neural Networks (RNNs),请注意这里的 RNN 算法指的并不是 Recurrent Neural Networks(RNNs),而是 Replicator Neural Networks,尽管它们拥有着同样的缩写名字 RNNs。具体来说, Replicator Neural Networks (RNNs),或者说自编码器,是一个多层前馈的神经网络 (multi-layer feed-forward neural networks)。在 Replicator Neural Networks 中,输入的变量也是输出的变量,模型中间层节点的个数少于输入层和输出层节点的个数。这样的话,模型就起到了压缩数据和恢复数据的作用。

rnn1

如图所示,这里的 RNNs 有三个隐藏层,输入层和输出层的节点个数都是6,第一个隐藏层和第三个隐藏层的节点个数(图中是4个节点)少于输入层,第二个隐藏层的节点个数是最少的(图中是2个节点)。在神经网络传输的时候,中间使用了 tanh 函数和 sigmoid 函数。这个神经网络是训练一个从输入层到输出层的恒等函数(identity mapping),传输的时候从输入层开始压缩数据,然后到了第二个隐藏层的时候开始解压数据。训练的目标就是使得整体的输出误差足够小,整体的误差是由所有的样本误差之和除以样本的个数得到的。由于图中只画出了6个特征,因此第 i 个样本的误差是

e_{i}=\sum_{j=1}^{6}(x_{i j}-r_{i j})^{2}/6

如果使用已经训练好的 RNN 模型,异常值的分数就可以定义为重构误差(reconstruction error)。

下面简要介绍一下 RNN 模型是如何构建的:

rnn2

根据上图所示,左边的是输入层,右边的输出层。假设第 k 层中第 i 个神经元的输出是 S_{k}(I_{ki}),其中 I_{ki} 表示第 k 层中第 i 个神经元的输入,S_{k} 表示第 k 层使用的激活函数。那么

\theta=I_{ki}=\sum_{j=0}^{L_{k-1}}w_{kij}Z_{(k-1)j}

其中 Z_{kj} 是第 k 层中第 j 个神经元的输出,L_{k} 是第 k 层神经元的个数。对于第二层和第四层而言 (k=2,4),激活函数选择为

S_{k}(\theta)=tanh(a_{k}\theta)  \text{ for } k=2 \text{ or } 4,

这里的 a_{k} 是一个参数,通常假设为1。对于中间层 (k=3) 而言,激活函数是一个类阶梯 (step-like) 函数。有两个参数 N 和 a_{3},N 表示阶梯的个数,a_{3} 表示从这一层到下一层的提升率 (transition rate):

S_{3}(\theta)=\frac{1}{2}+\frac{1}{4}\sum_{j=1}^{N-1}tanh(a_{3}(\theta-\frac{j}{N})).

在这里可以假设 a_{3}=100N=4. 那么 S_{3}(\theta) 就如下图所示。

S3

第三层的激活函数的输出就变成了 N 个离散的变量:0, 1/(N-1), 2/(N-1),…,1。这个阶梯型的激活函数是把第三层的连续输入值变成了一批离散的值。也就意味着把样本映射到了 N 个簇,那么 RNN 就可以计算出单个的异常点和一小簇的异常点。

备注:

根据上面的分析,可以看出如果按照以上算法,则不能使用反向传播算法来训练模型,原因是 S_{3}(\theta) 的导数不能够通过它的取值来表示。这一点与 tanh 函数,\sigma 函数是不一致的,因为 tanh^{'}(x) = 1-tanh^{2}(x)\sigma^{'}(x)=\sigma(x)(1-\sigma(x))。因此有学者指出 [1],使用三个隐藏层是没有必要的,使用1个或者2个隐藏层的神经网络也能够得到类似的结果;同样,没有必要使用 S_{3}(\theta) 这样类型的阶梯函数,使用传统的 \sigma 激活函数也能够得到类似的结果。并且 S_{3}(\theta) 是一个 step-like 函数,很多地方的导数取值都是接近于零的。

后向传播算法:

一般来说,为了训练神经网络模型,需要使用后向传播算法(back propagation),也简称为 BP 算法,或者误差逆传播算法(error back propagation)。在本文中,仅针对最简单的 RNN 模型介绍如何使用 BP 算法进行模型训练,至于多层的神经网络模型或者其他的神经网络模型,方法则是完全类似的。

rnn3

给定训练集合 D=\{(\bold{x}_{1},\bold{y}_{1}),...,(\bold{x}_{m},\bold{y}_{m})\},其中有 m 个样本,并且输入和输出是一样的值。换句话说,也就是 n 维向量

\bold{x}_{i}=\bold{y}_{i}\in\mathbb{R}^{n} \text{ for all } 1\leq i\leq m.

换句话说,输入样例是由 n 个属性描述,输出的结果也是 n 个属性。隐藏层只有一个,隐藏层的神经元个数是 q=[(n+1)/2],这里的 [] 表示 Gauss 取整函数。输出层第 j 个神经元的阈值使用 \theta_{j} 表示,隐藏层第 h 个神经元的阈值使用 \gamma_{h} 表示。输入层第 i 个神经元与隐藏层第 h 个神经元之间的连接权重是 v_{i h}, 隐藏层第 h 个神经元与输出层第 j 个神经元之间的连接权重是 w_{h j}, 其中 1\leq i \leq n, 1\leq h \leq q, 1\leq j \leq n.

记隐藏层第 h 个神经元接收到的输入为

\alpha_{h} = \sum_{i=1}^{n}v_{i h}x_{i} \text{ for all } 1\leq h \leq q.

写成矩阵形式就是:

(\alpha_{1},\cdot\cdot\cdot,\alpha_{q})=(x_{1},\cdot\cdot\cdot,x_{n})\begin{bmatrix} v_{11} & ... & v_{1q} \\ ... & ... & ... \\ v_{n1} & ... & v_{nq} \end{bmatrix}.

记输出层第 j 个神经元接收到的输入为

\beta_{j}=\sum_{h=1}^{q}w_{h j}b_{h} \text{ for all } 1\leq j\leq n,

其中 b_{h} 是隐藏层第 h 个神经元的输出,b_{h} = f(\alpha_{h}-\gamma_{h}) \text{ for all } 1\leq h \leq q, f 是激活函数。写成矩阵形式就是:

(\beta_{1},\cdot\cdot\cdot,\beta_{n})=(b_{1},\cdot\cdot\cdot,b_{q})\begin{bmatrix} w_{11} & ... & w_{1n} \\ ... & ... & ... \\ w_{q1} & ... & w_{qn} \end{bmatrix}.

输出层第 j 个神经元的输出是 f(\beta_{j}-\theta_{j}), 其中 1\leq j \leq n.

下面可以假定激活函数都使用 f(x)=1/(1+\exp(-x)), 那么直接通过导数计算可以得到 f^{'}(x)=f(x)(1-f(x)).

对于训练集 (\bold{x}_{k},\bold{y}_{k}), 通过神经网络得到的输出是 \hat{\bold{y}}_{k}=(\hat{y}_{k1},...,\hat{y}_{kn}), 并且 \hat{y}_{kj} = f(\beta_{j}-\theta_{j}) 对于 1\leq j \leq n 都成立。那么神经网络在训练集 (\bold{x}_{k},\bold{y}_{k}) 的均方误差是

E_{k} =\frac{1}{2}\sum_{j=1}^{n}(\hat{y}_{kj}-y_{kj})^{2},

其中 \bold{y}_{k}=(y_{k1},...,y_{kn}). 整体的误差是

E = \frac{1}{m}\sum_{k=1}^{m}E_{k} = \frac{1}{2m}\sum_{k=1}^{m}\sum_{j=1}^{n}(\hat{y}_{kj}-y_{kj})^{2}

标准 BP 算法:

网络中有 个参数需要确定:输入层到隐藏层的 n*q 个权重值,隐藏层到输出层的 n*q 个权重值,q个隐层神经元的阈值,n 个输出层神经元的阈值。BP 算法是一个迭代学习算法,在迭代的每一轮采用了梯度下降法来进行参数的更新。任意参数的更新规则是

v \leftarrow v+\Delta v.

标准 BP 算法是根据每一个 E_{k} 来获得更新规则,下面来推导每一个参数的更新规则。对于 1\leq h \leq q, 1\leq j \leq n, 计算梯度

\Delta w_{hj} = -\eta \frac{\partial E_{k}}{\partial w_{hj}},

注意到 w_{hj} 先影响到第 j 个输出层神经元的输入值 \beta_{j}, 再影响到第 j 个输出层神经元的输出值 \hat{y}_{kj},最后影响到 E_{k},根据高等数学的链式法则可以得到

\frac{\partial E_{k}}{\partial w_{hj}} = \frac{\partial E_{k}}{\partial \hat{y}_{kj}} \cdot \frac{\partial \hat{y}_{kj}}{\partial \beta_{j}} \cdot \frac{\partial \beta_{j}}{\partial w_{hj}}

根据定义 \beta_{j}=\sum_{h=1}^{q}w_{hj}b_{h} 可以得到 \frac{\partial \beta_{j}}{\partial w_{hj}}=b_{h} 对于 1\leq j \leq n 都成立。

根据定义 E_{k}=\frac{1}{2}\sum_{j=1}^{n}(\hat{y}_{kj}-y_{kj})^{2} 可以得到 \frac{\partial E_{k}}{\partial \hat{y}_{kj}}=(\hat{y}_{kj}-y_{kj}).

根据定义 \hat{y}_{kj}=f(\beta_{j}-\theta_{j})f^{'}(x)=f(x)\cdot(1-f(x)) 可以得到 \frac{\partial \hat{y}_{kj}}{\partial \beta_{j}}=f^{'}(\beta_{j}-\theta_{j})=f(\beta_{j}-\theta_{j})\cdot(1-f(\beta_{j}-\theta_{j}))=\hat{y}_{kj}\cdot (1-\hat{y}_{kj}).

所以可以计算出对于 1\leq h \leq q, 1\leq j \leq n,

\frac{\partial E_{k}}{\partial w_{hj}} = (\hat{y}_{kj}-y_{kj})\cdot\hat{y}_{kj}\cdot(1-\hat{y}_{kj})\cdot b_{h}

如果假设

g_{j}=-\frac{\partial E_{k}}{\partial \beta_{j}}=-\frac{\partial E_{k}}{\partial \hat{y}_{kj}}\cdot \frac{\hat{y}_{kj}}{\partial \beta_{j}}

那么可以得到

g_{j}=\hat{y}_{kj}\cdot(1-\hat{y}_{kj})\cdot(y_{kj}-\hat{y}_{kj})

因此对于 1\leq h \leq q, 1\leq j \leq n, 可以得到\Delta w_{hj}=\eta g_{j}b_{h}.

根据类似的想法,有

\Delta \theta_{j}=-\eta\cdot\frac{\partial E_{k}}{\partial \theta_{j}}, \Delta v_{ih}=-\eta\cdot\frac{\partial E_{k}}{\partial v_{ih}}, \Delta \gamma_{h}=-\eta\cdot\frac{\partial E_{k}}{\partial \gamma_{h}}.

逐个计算:

\frac{\partial E_{k}}{\partial \theta_{j}}=\frac{\partial E_{k}}{\partial \hat{y}_{kj}}\cdot\frac{\partial\hat{y}_{kj}}{\partial\theta_{j}}=(\hat{y}_{kj}-y_{kj})\cdot(-1)\cdot f^{'}(\beta_{j}-\theta_{j})=(y_{kj}-\hat{y}_{kj})\cdot\hat{y}_{kj}\cdot(1-\hat{y}_{kj})=g_{j}

\frac{\partial E_{k}}{\partial v_{ih}}=\frac{\partial E_{k}}{\partial\alpha_{h}}\cdot\frac{\partial\alpha_{h}}{\partial v_{ih}}=\frac{\partial E_{k}}{\partial b_{h}}\cdot\frac{\partial b_{h}}{\partial \alpha_{h}}\cdot\frac{\partial\alpha_{h}}{\partial v_{ih}}

由于

\frac{\partial \alpha_{h}}{\partial v_{ih}}=x_{ki}

\frac{\partial b_{h}}{\partial\alpha_{h}}=f^{'}(\alpha_{h}-\gamma_{h})=f(\alpha_{h}-\gamma_{h})\cdot(1-f(\alpha_{h}-\gamma_{h}))=b_{h}\cdot(1-b_{h})

\frac{\partial E_{k}}{\partial b_{h}}=\sum_{j=1}^{n}\frac{\partial E_{k}}{\partial \beta_{j}}\cdot\frac{\partial \beta_{j}}{\partial b_{h}}=\sum_{j=1}^{n}(-g_{j})\cdot w_{hj}

所以,

\Delta v_{ih}=\eta(\sum_{j=1}^{n}g_{j}w_{hj})\cdot b_{h}\cdot (1-b_{h})x_{ki} = \eta e_{h}x_{ki}, 其中 e_{h}=-\partial E_{k}/\partial\alpha_{h}=(\sum_{j=1}^{n}g_{j}w_{hj})\cdot b_{h}\cdot(1-b_{h}).

\Delta \gamma_{h}=(-\eta)\cdot\frac{\partial E_{k}}{\partial\gamma_{h}}=(-\eta)\cdot\frac{\partial E_{k}}{\partial b_{h}}\cdot\frac{\partial b_{h}}{\partial\gamma_{h}}=\eta\cdot(\sum_{j=1}^{n}g_{j}w_{hj})\cdot(-1)\cdot f^{'}(\alpha_{h}-\gamma_{h})=(-\eta)\cdot(\sum_{j=1}^{n}g_{j}w_{hj})\cdot b_{h}\cdot(1-b_{h})=(-\eta)\cdot e_{h} .

整理之后,任意参数 v 的更新式子是 v\leftarrow v+\Delta v, 并且更新的规则如下:

\Delta w_{hj}=\eta g_{j}b_{h} \text{ for all } 1\leq j\leq n, 1\leq h \leq q,

\Delta \theta_{j}=-\eta g_{j} \text{ for all } 1\leq j\leq n,

\Delta v_{ih}=\eta e_{h}x_{ki} \text{ for all } 1\leq i\leq n, 1\leq h\leq q,

\Delta \gamma_{h}=-\eta e_{h} \text{ for all } 1\leq h\leq q,

其中学习率 \eta\in(0,1) 控制着算法每一轮迭代中的更新步长,若步长太大则容易振荡,太小则收敛速度过慢,需要人工调整学习率。 对每个训练样例,BP 算法执行下面的步骤:先把输入样例提供给输入层神经元,然后逐层将信号往前传,直到计算出输出层的结果;然后根据输出层的误差,再将误差逆向传播至隐藏层的神经元,根据隐藏层的神经元误差来对连接权和阈值进行迭代(梯度下降法)。该迭代过程循环进行,直到达到某个停止条件为止。

标准 BP 算法的训练流程:
输入:训练集合 D={(\bold{x}_{k},\bold{y}_{k})}_{k=1}^{m} 和学习率 \eta.
过程:
1. 在 (0,1) 范围内随机神经网络中的所有连接权重和阈值
2. repeat
for all (\bold{x}_{k},\bold{y}_{k}) do
根据当前参数,计算出当前的样本输出 \bold{y}_{k}
计算输出层神经元的梯度项 g_{j}
计算隐藏层神经元的梯度项 e_{h}
更新连接权重 w_{hj}, v_{ih} 与阈值 \theta_{j},\gamma_{h}
end for
3. 达到停止条件
输出:链接权与阈值都确定的神经网络模型

累积 BP 算法:

BP 算法的目的是最小化训练集上的累计误差 E=\sum_{k=1}^{m}E_{k}/m, 其中 m 是训练集合中样本的个数。不过,标准的 BP 算法每次仅针对一个训练样例更新连接权重和阈值,也就是说,标准 BP 算法的更新规则是基于单个的 E_{k} 推导而得到的。通过类似的计算方法可以推导出累计误差的最小化更新规则,那就得到了累计误差逆传播(accumulate error backpropagation)算法。标准 BP 算法需要进行更多次的迭代,并且参数的更新速度快,累积 BP 算法必须扫描一次训练集合才会进行一次参数的更新,而且累计误差下降到一定的程度以后 ,进一步下降就会明显变慢,此时标准 BP 算法往往会更快的得到较好的解,尤其是训练集合大的时候。

训练方法:

(1)把数据集合的每一列都进行归一化;

(2)选择 70% 的数据集合作为训练集合,30% 的数据集合作为验证集合。或者 训练集合 : 验证集合 = 8 : 2,这个需要根据情况而定。

(3)随机生成一个三层的神经网络结构,里面的权重都是随机生成,范围在 [0,1] 内。输入层的数据和输出层的数据保持一致,并且神经网络中间层的节点个数是输入层的一半。

(4)使用后向传播算法(back-propagation)来训练模型。为了防止神经网络的过拟合,通常有两种策略来防止这个问题。(i)第一种策略是“早停”(early stopping):当训练集合的误差降低,但是验证集合的误差增加时,则停止训练,同时返回具有最小验证集合误差的神经网络;(ii)第二种策略是“正则化”(regularization):基本思想是在误差目标函数中增加一个用于描述网络复杂度的部分,例如链接权和阀值的平方和。

测试效果:

其中蓝色的点表示正常点,红色的点表示被 RNN 算法标记的异常点。

rnn_result1

rnn_result2

参考文献:

[1] Anomaly Detection Using Replicator Neural Networks Trained on Examples of One Class, Hoang Anh Dau, Vic Ciesielski, Andy Song

[2] Replicator Neural Networks for Outlier Modeling in Segmental Speech Recognition, Laszlo Toth and Gabor Gosztolya

[3] Outlier Detection Using Replicator Neural Networks, Simon Hawkins, Honxing He, Graham Williams and Rohan Baxter

 

聚类算法(一)

聚类是一种无监督学习(无监督学习是指事先并不知道要寻找的内容,没有固定的目标变量)的算法,它将相似的一批对象划归到一个簇,簇里面的对象越相似,聚类的效果越好。聚类的目标是在保持簇数目不变的情况下提高簇的质量。给定一个 n 个对象的集合。把这 n 个对象划分到 K 个区域,每个对象只属于一个区域。所遵守的一般准则是:同一个簇的对象尽可能的相互接近或者相关,而不同簇的对象尽可能的区分开。最常见的一种聚类算法则是 K-均值 算法。

K-均值(K-Means)聚类算法

K 均值聚类算法是用来发现给定数据集的 K 个簇的一种无监督学习算法,簇的个数是由人工给定的,每个簇使用质心(Centroid)和相应的半径(Radius)来描述。需要量化的误差指标有误差平方和(sum of squared error)等。

K-均值算法是一种启发式的算法。它会渐近地提高聚类的质量,达到局部的最优解,但是就是因为这样,才容易陷入局部最优解,而没有达到全局最优解,所有有人提出了二分 K-均值算法。启发式的聚类算法很适合发现中小规模的簇,对于大数据集合,从计算量来说成本则会很高。K-均值算法也有着自己的不足之处,通过下面算法可以发现 K-均值算法对离群点特别敏感,离群点的存在会直接影响着 K-均值算法的效果。

K 均值算法的流程是这样的。首先,随机确定 K 个初始点作为质心。然后将数据集中的每个点分配到每一个簇中,具体来讲,为每一个数据点找距离其最近的质心,并将其分配给该质心所对应的簇。这一步完成之后,每个簇的质心更新为该簇所有点的平均值。

K-Means 的伪代码:

创建K个点作为初始的质心(经常是随机选择数据点中的K个点,而不是平面上随机的K个点)

当任意一个点的簇分配结果发生变化时:

    对数据集中每个数据点

        对每个质心,计算质心与数据点之间的距离

        将数据点分配到距离其最近的簇

    对每一个簇,计算簇中所有点的均值并将均值作为质心

注:K 均值算法在某些时候容易收敛到局部最小值。

使用一批二维数据集合,进行 4 均值聚类算法可以得到下图:’+’ 表示的是质心的位置,其余就是数据点的位置。

聚类1

 

效果评估:

SSE 指的是 Sum of Squared Error(误差平方和)越小表示数据点越接近它们的质心,聚类的效果也就越好。质心使用 c[i] 表示,质心 c[i] 所包含的对象集合使用 C[i] 表示。如果用 p 表示 C[i] 中的某个对象,dist(p,c[i]) 表示的就是对象和质心 c[i] 的距离。那么误差平方和则定义为

E=\sum_{i=1}^{K}\sum_{p \in C[i]} dist(p, c[i])^{2}

 

二分 K 均值聚类(Bisecting K-Means)

为了解决 K 均值算法可能会收敛到局部最小值的情况,有人提出了二分 K 均值算法(bisecting K-means)。该算法首先将所有点作为一个簇,然后将该簇一分为二,之后选择其中的一个簇继续进行划分,选择哪一个簇进行划分取决于对其划分是否可以最大程度降低 SSE 的值。上述基于SSE的划分过程不断重复,直到得到用户指定的簇的数目为止。

二分 K-Means 的伪代码如下:

将所有的点看成一个簇

当簇的数量小于K时

    对于每一个簇

        计算总误差

        在给定的簇上面进行2均值聚类

        计算将该簇一分为二之后的总误差(指的是这两个簇的误差与其他剩余集的误差之和)

    选择使得总误差最小的那个簇进行划分操作

另一种做法就是:每次进行下一步划分的时候,选择误差平方和最大的簇进行划分,直到簇的数目达到用户指定的数目为止。这样的启发式算法就使得整体的误差平方和尽可能的小,也就是簇的划分更加精确。

使用一批二维数据集合,进行 3 均值聚类算法可以得到下图:’+’ 表示的是质心的位置,其余就是数据点的位置。

聚类2

 

KL散度(Kullback-Leibler Divergence)

在信息论和概率论里面,Kullback-Leibler 散度(简称KL散度,KL divergence)是两个概率分布 PQ 的一个非对称的度量公式。这个概念是由 Solomon Kullback 和 Richard Leibler 在 1951 年引入的。从概率分布 Q 到概率分布 P 的 KL 散度用 D_{KL}(P||Q) 来表示。尽管从直觉上看 KL 散度是一个度量或者是一个距离,但是它却不满足度量或者距离的定义。例如,从 QP 的 KL 散度就不一定等于从 PQ 的 KL 散度。

KL 散度的数学定义:

对于离散空间的两个概率分布 PQ 而言,从 QP 的KL散度被定义为

D_{KL}(P||Q)=\sum_{i}P(i)\log_{2}(P(i)/Q(i)).

换句话说,它是两个概率分布 PQ 的对数差的期望,这里的期望是以概率 P 来描述的。KL散度有定义当且 Q(i)=0 \implies P(i)=0 对于所有的 i 都成立。如果 P(i)=0, 那么可以假设KL散度的第 i 项是零,因为 \lim_{x\rightarrow 0^{+}}x\log_{2}x=0.

对于连续空间 X 的两个概率分布 PQ 而言,从 QP 的 KL 散度被定义为:

D_{KL}(P||Q)=\int_{X}p(x)\log_{2}(p(x)/q(x))dx,

这里的 pq 是概率分布 PQ 的概率密度。

KL 散度的基本性质:

(1)KL 散度总是非负的,并且只有 P(x)=Q(x) 几乎处处成立的时候,才会有

D_{KL}(P||Q)=0.

证明:利用Jensen’s Inequality。

D_{KL}(P||Q)=-E_{P}(\log_{2}(q(x)/p(x)))

\geq -log_{2}(E_{p}(q(x)/p(x)))=-log_{2}(\int_{X}q(x)dx)=0.

(2)如果 P_{1}, P_{2} 是独立分布,并且联合分布是 P(x,y)=P_{1}(x)P_{2}(y), Q_{1},Q_{2} 是独立分布并且联合分布是 Q(x,y)=Q_{1}(x)Q_{2}(y), 那么

D_{KL}(P||Q)=D_{KL}(P_{1}||Q_{1}) + D_{KL}(P_{2}||Q_{2}).

(3)如果定义分布 PQ 的交叉墒是

H(P,Q)=-\int_{X}p(x)\log_{2}q(x)dx,

分布P的熵是

H(P)=-\int_{X}p(x)\log_{2}p(x)dx,

那么 D_{KL}(P||Q)=H(P,Q)-H(P).

(4)KL 散度是两个概率分布 PQ 差别的非对称性的度量。 KL 散度是用来度量使用基于 Q 的编码来编码来自 P 的样本平均所需的额外的位元数。典型情况下, P 表示数据的真实分布,Q 表示数据的理论分布,模型分布,或 P 的近似分布。

(5)从KL散度的定义可以得出

D_{KL}(P||Q)\neq D_{KL}(Q||P),

所以 KL 散度不满足距离的对称性。当然,如果需要把它弄成对称的,可以定义

DS_{KL}(P,Q)=(D_{KL}(P||Q) + D_{KL}(Q||P))/2.

简单例子:

比如有四个类别,一个方法 P 得到四个类别的概率分别是0.1,0.2,0.3,0.4。另一种方法 Q(或者说是事实情况)是得到四个类别的概率分别是0.4,0.3,0.2,0.1,那么这两个分布的 KL 散度就是

D_{KL}(P||Q)

=0.1*\log_{2}(0.1/0.4) + 0.2*\log_{2}(0.2/0.3) + 0.3*\log_{2}(0.3/0.2) + 0.4*\log_{2}(0.4/0.1).

案例分析:

在实际的工作中,我们通常会有某个网页或者app被用户点击或者播放的数据,同时,我们会拥有用户画像(personas),此刻我们关心的问题就是如何计算网页里面的某个新闻或者app里面的某个专辑受到不同维度的用户画像的喜好程度。比如,如何判断该新闻是受到各个年龄层的用户的喜爱还是只是受到某个年龄层的用户的喜爱?如何判断某个电台节目是受到大众的喜爱还是更加受到男性或者女性的喜爱?此时,怎么计算物品被用户的喜欢程度就成为了一个重要的关键。

通常的方案就是,比方说:某个电台专辑被66.7%的男性用户播放过,被33.3%的女性用户播放过,那么该物品是不是真的就是更加受到男性用户的青睐呢?答案是否定的。如果使用这款app的用户的男女比例恰好是1:1,那么根据以上数据,该电台专辑显然更加受到男性用户的喜爱。但是,实际的情况,使用这款app的用户的男女比例不完全是1:1。如果男性用户:女性用户=2:1的话,如果某个电台专辑被66.7%的男性用户播放过,被33.3%的女性用户播放过,那么说明该专辑深受男女喜欢,两者对该专辑的喜好程度是一样的。因为基础的男女比例是2:1,该专辑被男女播放的比例是2:1,所以,该专辑对男女的喜爱程度恰好是1:1。

那么如何计算该专辑的喜好程度呢?首先我们会使用KL散度来描述这件事情。

 

 

 

 

 

 

 

 

 

机器学习的基本模型—入门知识

机器学习的各种算法在于如何使用特定函数与已知的数据集相匹配,从而达到训练和测试的目的。本篇文章对一些近似的模型做一些相应的介绍。

线性模型

一维输入变量

假设学习对象f函数的输入是一组实数,那么对该函数进行近似的时候,最简单的方案就是f_{\theta}(x)=\theta\cdot x。在这里,\theta是这个函数的斜率,也就是这个函数f_{\theta}(x)的参数。机器学习就是通过对这个参数的学习,完成函数的近似计算。这个模型对于\theta而言是一个线性函数,操作起来十分方便,但是对于实际的情况来说,该模型过于简单,没有太大的使用价值。 由于上面这个模型过于简单,那么在实际应用中,会对上述的模型进行必要的扩展,使得函数f_{\theta}(x)变成参数的线性模型,这样这个模型就可以用来表示非线性的输入和输出了。可以把\theta\cdot x扩展成如下形式:

f_{\theta}(x)=\sum_{j=1}^{b}\theta_{j}\cdot\phi_{j}(x).

在这个式子中,\phi_{j}(x)是基函数向量\phi(x)=(\phi_{1}(x),\cdot\cdot\cdot,\phi_{b}(x))^{T}的第j个分量,\theta_{j}\theta=(\theta_{1},\cdot\cdot\cdot,\theta_{b}))^{T}的第j个分量,b是基函数\phi(x)的维数。根据上面f_{\theta}(x)的定义,可以得到该函数是参数向量\theta的线性函数。也就是说对于b维参数\theta,\theta^{'}\alpha\in \mathbb{R},满足

f_{\theta+\theta^{'}}(x)=f_{\theta}(x)+f_{\theta^{'}}(x),

f_{\alpha \theta}(x)=\alpha f_{\theta}(x).

那么这个时候如何选择基函数\phi(x)就成为了一个关键所在。

数学分析里面有一个经典定理叫做Weierstrass定理,陈述如下:

Weierstrass第一逼近定理:假设f(x)是闭区间[a,b]上的连续函数,对于任意的\epsilon>0,则存在多项式P(x)使得对于所有的x\in [a,b],有|f(x)-P(x)|<\epsilon 

根据Weierstrass第一逼近定理,对于任何一个闭区间上面的连续函数,都可以用多项式去逼近。所以联系到机器学习,就可以把基函数\phi(x)的分量设置为多项式,换句话说

\phi_{j}(x)=x^{j-1}

\phi(x)=(1,x,x^{2},\cdot\cdot\cdot, x^{b-1})^{T}.

那么上述的\theta的线性函数却是关于自变量x的非线性函数,而且f_{\theta}(x)=\sum_{j=1}^{b}\theta_{j}\cdot x^{j-1}可以逼近关于x的闭区间上任何一个连续函数。

与Weierstrass逼近定理类似,用Fourier级数也可以逼近Lipchitz连续函数。所以也可以选择基函数

\phi_{0}(x)=1,\phi_{2j-1}(x)=\sin(jx),\phi_{2j}(x)=\cos(jx), 其中j\geq 1. 

简单来说就是令b=2m+1, \phi(x)=(1,\sin(x),\cos(x),\cdot\cdot\cdot,\sin(mx),\cos(mx))^{T}. 根据这些模型,f_{\theta}(x)就可以表示复杂的非线性模型了。

高维输入变量

对于高维的变量\textbf{x}=(x^{(1)},\cdot\cdot\cdot,x^{(d)}), 函数依旧可以扩展成如下模式:

f_{\theta}(\textbf{x})=\sum_{j=1}^{b}\theta_{j}\cdot\phi_{j}(\textbf{x})={\theta}^{T}\phi(\textbf{x}).

对于多维的输入向量\textbf{x},可以用一维的基函数来构造多维基函数的乘法模型加法模型

乘法模型指的是把一维的基函数作为因子,通过使其相乘而获得多维基函数的方法。表达式如下:

f_{\theta}(x)=\sum_{j_{1}=1}^{b^{'}}\cdot\cdot\cdot\sum_{j_{d}=1}^{b^{'}}\theta_{j_{1},\cdot\cdot\cdot,j_{d}}\phi_{j_{1}}(x^{(1)})\cdot\cdot\cdot \phi_{j_{d}}(x^{(d)}).

在上面的式子中,b^{'}是各个维数的参数个数。对于这个模型而言,它的表现力十分丰富,但是不足之处在于所有的参数个数是(b^{'})^{d}, 是一个非常巨大的数字,导致的维数灾难,所以在实际运用中,不主张用这个模型。

加法模型指的是把一维的基函数作为因子,通过相加而活得高维基函数的方法。表达式如下:

f_{\theta}(x)=\sum_{k=1}^{d}\sum_{j=1}^{b^{'}}\theta_{k,j}\phi_{j}(x^{(k)}).

加法模型中所有参数的个数是b^{'}d, 它是一个关于维数d的线性函数,复杂度没有乘法模型大,但是表现力和乘法模型比起来则差很多。

核模型

在线性模型中,多项式或三角函数等基函数的选择都是与训练样本无关的,核模型则与之相反,会在进行基函数构造的时候使用输入样本\{\mathbf{x}_{i}\}_{i=1}^{n}.  在核模型中,会使用核函数

K(\mathbf{x},\mathbf{c})=\exp(-||\mathbf{x}-\mathbf{c}||_{2}^{2}/(2h^{2})), 

其中||\cdot||_{2}指的是欧几里德2-范数,h表示核函数的带宽\mathbf{c}指的是核函数的均值 从核函数的定义可以可以延伸出模型

f_{\theta}(\mathbf{x})=\sum_{j=1}^{n}\theta_{j}\cdot K(\mathbf{x},\mathbf{x}_{j}).

在这个模型中,关于\theta而言仍然满足线性关系。换句话说,对于\theta,\theta^{'}\in\mathbb{R}^{n},f_{\theta+\theta^{'}}(x)=f_{\theta}(x)+f_{\theta^{'}}(x)f_{\alpha\theta}(x)=\alpha f_{\theta}(x). 对于核函数来说,无论输入的是一维变量还是高维变量,核函数都可以容易的进行扩展。

层级模型

对参数来说是非线性的模型,都称为非线性模型。下面要介绍的就是非线性模型中的层级模型,它在很多领域都有应用。假设模型是

f_{\theta}(\mathbf{x})=\sum_{j=1}^{b}\alpha_{j}\cdot\phi(\mathbf{x};\mathbf{\beta}_{j}).

上式中,\phi(\mathbf{x};\mathbf{\beta})是关于参数向量\mathbf{\beta}的基函数,层级模型是基于参数向量\mathbf{\alpha}=(\alpha_{1},\cdot\cdot\cdot,\alpha_{b})^{T}的线性形式。同时也包含参数向量\{\beta_{j}\}_{j=1}^{b}, 所以层级模型是基于参数向量\mathbf{\theta}=(\mathbf{\alpha}^{T},\mathbf{\beta}_{1}^{T},\cdot\cdot\cdot,\mathbf{\beta}_{b}^{T})^{T}的非线性形式。 基函数通常采用S型函数

\phi(\mathbf{x};\beta)=1/(1+\exp(-\mathbf{x}^{T}\omega-\gamma)), 其中\beta=(\omega^{T},\gamma)^{T}

或者高斯函数

\phi(\mathbf{x};\beta)=\exp(-||\mathbf{x}-\mathbf{c}||_{2}^{2}/(2h^{2})), 其中\beta=(\mathbf{c}^{T},h)^{T}.

其中S函数模仿的是人类脑细胞的输入输出函数,因此使用S函数的层级模型也被称为人工神经网络模型

针对像人工神经网络这样的层级模型,采用贝叶斯学习的方法是不错的选择。人工神经网络也以学习过程艰难异常而著称。