Category Archives: Computer Science

特征工程简介

January 26, 2016 zr9558 1 Comment

（I）特征工程可以解决什么样的问题？

特征工程是一个非常重要的课题，是机器学习中不可缺少的一部分，但是它几乎很少出现于机器学习书本里面的某一章。在机器学习方面的成功很大程度上在于如果使用特征工程。在机器学习中，经常是用一个预测模型（线性回归，逻辑回归，SVD等）和一堆原始数据来得到一些预测的结果，人们需要做的是从这堆原始数据中去提炼较优的结果，然后做到最优的预测。这个就包括两个方面，第一就是如何选择和使用各种模型，第二就是怎么样去使用这些原始的数据才能达到最优的效果。那么怎么样才能够获得最优的结果呢？贴上一句经典的话就是：

Actually the sucess of all Machine Learning algorithms depends on how you present the data.
—— Mohammad Pezeshki

直接翻译过来便是：事实上所有机器学习算法上面的成功都在于你怎么样去展示这些数据。由此可见特征工程在实际的机器学习中的重要性，从数据里面提取出来的特征好坏与否就会直接影响模型的效果。从某些层面上来说，所使用的特征越好，得到的效果就会越好。所需要的特征就是可以借此来描述已知数据的内在关系。总结一下就是：

Better feature means flexibility. Better feature means simpler models. Better feature means better results.

有的时候，可以使用一些不是最优的模型来训练数据，如果特征选择得好的话，依然可以得到一个不错的结果。很多机器学习的模型都能够从数据中选择出不错的结构，从而进行良好的预测。一个优秀的特征具有极强的灵活性，可以使用不那么复杂的，运算速度快，容易理解和维护的模型来得到不错的结果。

（II）什么才是特征工程？

Feature Engineering is the process of transforming raw data into features that better represent the underlying problem to the predictive models, resulting in improved model accuracy on unseen data.
—— Jason Brownlee

Feature Engineering is manually designing what the input x’s should be.
—— Tomasz Malisiewicz

从这个概念可以看出，特征工程其实是一个如何展示和表现数据的问题，在实际工作中需要把数据以一种“良好”的方式展示出来，使得能够使用各种各样的机器学习模型来得到更好的效果。如何从原始数据中去除不佳的数据，展示合适的数据就成为了特征工程的关键问题。

（III）特征有用性的预估

每次构造了一个特征，都需要从各个方面去证明该特征的有效性。一个特征是否重要主要在于该特征与要预测的东西是否是高度相关的，如果是高度相关，那么该特征就是十分重要的。比如常用的工具就是统计学里面的相关系数。

（IV）特征的构造过程

在实际工作中首先肯定要确定具体的问题，然后就是数据的选择和准备过程，再就是模型的准备和计算工作，最后才是展示数据的预测结果。构造特征的一般步骤：

［1］任务的确定：

根据具体的业务确定需要解决的问题。

［2］数据的选择：

整合数据，收集数据。这个时候需要对这些数据的可用性进行评估，可以分成几个方面来考虑。获取这批数据的难易程度，比方说有的数据非常隐私，这批数据获得的难度就很大。其次就是这批数据的覆盖率。比方说要构造某个年龄的特征，那么这些用户中具有年龄特征的比例是多少就是一个关键的指标。如果覆盖率低，那么最后做出的特征可以影响的用户数量就会有限制。如果覆盖率高，那么年龄特征做得好，对最后的模型训练结果都会有一个明显的提升。再就是这批数据的准确率，因为从网上或者其他地方获取的数据，会由于各种各样的因素（用户的因素，数据上报的因素）导致数据不能够完整的反映真实的情况。这个时候就需要事先对这批数据的准确性作出评估。

［3］预处理数据：

设计数据展现的格式，清洗数据，选择合适的样本使得机器学习模型能够使用它。比方说一些年龄特征是空值或者负数或者大于200等，或者说某个页面的播放数据大于曝光数据，这些就是数据的不合理，需要在使用之前把这一批数据排除掉。这个时候清洗异常样本就显得至关重要。

［4］特征的构造：

转化数据，使之成为有效的特征。常用的方法是标准化，归一化，特征的离散化等。

（4.1）标准化（Standardization）：

比方说有一些数字的单位是千克，有一些数字的单位是克，这个时候需要统一单位。如果没有标准化，两个变量混在一起搞，那么肯定就会不合适。

（4.2）归一化（Normalization）：

归一化是因为在特征会在不同的尺度下有不同的表现形式，归一化会使得各个特征能够同时以恰当的方式表现。比方说某个专辑的点击播放率一般不会超过0.2，但是专辑的播放次数可能会达到几千次，所以说为了能够在模型里面得到更合适结果，需要先把一些特征在尺度上进行归一化，然后进行模型训练。进行比例缩放或者归一化的时候，通常采取的方案有线性（linearization）最大最小归一化，对数（logarithm）归一化，或者 z-score 的归一化。其中 z-score 的归一化指的是 $(x-\mu)/\sigma$ ，这里 $\mu$ 是这个特征的均值， $\sigma$ 是这个特征的方差。这里的归一化的关键之处在于数据的变化（Data Transforming）。对于处理一些大尺度数据（比方说某个视频被所有用户观看的次数之类的），一般会使用对数来处理数据，或者双曲线函数。例如：

$f(x)=\log(1+x):[0,+\infty)\rightarrow [0,+\infty),$

或者

$f(x)=x/(x+1):[0,+\infty)\rightarrow [0,1).$

（4.3）特征的离散化（Discretization）：

离散化是指把特征进行必要的离散处理，比方说年龄特征是一个连续的特征，但是把年龄层分成5－18岁（中小学生），19－23岁（大学生），24－29岁（工作前几年），30－40岁（成家立业），40－60岁（中年人）从某些层面来说比连续的年龄数据（比如说某人年龄是20岁1月3日之类的）更容易理解不同年龄层人的特性。这里可以根据特征的分布图像做出不同的分割，比方说通过等频率分割（Equal-Frequency）得到的特征比等区间分割（Equal-Interval）得到的特征具有更好的区分性。典型的离散化步骤：对特征做排序－> 选择合适的分割点－> 作出对整体的分割－> 查看分割是否合理，是否能够达到停止条件。

（4.4）特征的二值化（Binarization）：

二值化指的是把某个特征映射成 0 或者 1 两个值，比方说判断某个用户是否收听某个节目，用 1 表示该用户收听这个节目，否则用 0 表示该用户没有收听这个节目。

（4.5）特征的交叉：

比方说，某个男性用户在一级分类新闻资讯的取值是1，那么他在这个新闻咨询下的所有专辑和节目的取值都是1。对娱乐新闻的取值也是1，对八卦头条的取值也是1，对NBA战况直播的取值还是1。也就是说（男性，娱乐新闻），（男性，八卦头条），（男性，NBA战况直播）这三个分类的取值都是1。这样看起来就不符合常理，照理说男性用户对NBA的兴趣应该是远大于娱乐新闻的。比较合理的做法是男性在某个专辑的取值是所有男性在这个专辑的点击率，也就是说（男性，娱乐新闻）的取值是男性对娱乐新闻的点击率，（男性，NBA战况直播）的取值是男性对NBA战况的点击率。此时的值不再是 0 或者 1，而是 [0,1] 之间的某个实数，可以对这个实数进行加减乘除等运算操作。除了性别和点击率的交叉特征，还可以进行年龄，地域，收入等特征和点击率的交叉。

[5] 选择特征的常用方法：

（5.1）过滤（Filter）：

过滤这种方法是选定一个指标来评估这个特征的可行性，根据指标值来对已经构造的特征进行排序工作，去掉无法达到要求的特征。这个时候，选择一个合适的指标来判断特征是否有效就是关键所在。从统计学的角度来看，相关系数（Correlation Coefficient）是一个评价两个随机变量 X 和 Y 是否线性相关的一个重要指标。

$\rho_{XY}=cov(X,Y)/(\sigma_{X}\sigma_{Y})\in [-1,1]$

就是相关系数的计算方法。如果 $\rho_{XY}<0$ ，那么说明两个变量是线性反相关的；如果 $\rho_{XY}>0$ ，那么说明两个变量是线性相关的。不过需要主要的是，即使 $\rho_{XY}=0$ ，也只是说明两个变量是线性无关的，并不能推出它们之间是独立的。此时知道的就是一个线性分类器并不能把这个特征的正负样本分开，需要把该特征和其他特征交叉或者做其余的特征运算，形成一个或者多个新的特征，让这些新的特征发挥新的价值，做好进一步的分类工作。

（5.2）包装（Wrapper）：

包装这种方法和前面的过滤方法不一样。包装方法需要首先选定一种评估模型效果的方法，比方说 AUC（Area Under the Curve），MAE（Mean Absolute Error），Mean Squared Error（MSE）等。此时有两个不同的方案，分别是前向特征选择（Forward Feature Selection）和后向特征选择（Backward Feature Selection）。前向特征选择是从空集（Empty Set）开始，使用一种贪心算法，每次在现有特征的基础上逐渐添加一个使得模型效果更好的特征。反之，后向特征选择是从（Full Set）开始，每次去掉一个让模型效果提升最多的特征。或者可以使用增 L 去 R 算法（Plus-L Minus-R Selection），也就是说从空集开始，每次增加 L 个，同时减去 R 个，选择最优的特征，其中 L>R。或者从全集开始，每次减去 R 个，同时增加 L 个，选择最优的特征，其中 L<R。

（5.3）嵌入（Embedding）：

嵌入特征选择方法和算法本身紧密结合，在模型训练的过程中完成特征的选择。例如：决策树（Decision Tree）算法每次都是优先选择分类能力最强的特征；逻辑回归（Logistic Regression）算法加上 L1 和 L2 等惩罚项之后，也会使得某些信号比较弱的特征权重很小甚至为 0。至于 Logistic Regression 的一些算法，可以参考 TG（Truncated Gradient Algorithm），FOBOS（Forward and Backward Splitting），RDA（Regularized Dual Averaging Algorithm）， FTRL（Follow-the-Regularized-Leader Algorithm）算法，参考文献：Ad Click Prediction: a View from the Trenches。

［6］模型的使用：

创造模型，选择合适的模型（LR，SVM，SVD等），用合适的模型来进行预测，用各种统计指标来判断该特征是否合适。

［7］上线的效果：

通过在线测试来看效果。数据的转换（Transforming Data）就是把数据从原始的数据状态转换成适合模型计算的状态，从某些层面上来说，“数据转换“和”特征构造“的过程几乎是一致的。

（V）特征工程的迭代过程

特征工程的迭代步骤：

［1］选择特征：

需要进行头脑风暴（brainstorm）。通过分析具体的问题，查看大量的数据，从数据中观察出数据的关键之处；

［2］设计特征：

这个需要具体问题具体分析，可以自动进行特征提取工作，也可以进行手工进行特征的构造工作，甚至混合两种方法；

［3］判断特征：

使用不同的特征构造方法，来从多个层面来判断这个特征的选择是否合适；

［4］计算模型：

通过模型计算得到模型在该特征上所提升的准确率。

［5］上线测试：

通过在线测试的效果来判断特征是否有效。监控重要特征，防止特征的质量下滑，影响模型的效果。

Computer Science, 推荐系统

转行数据挖掘和机器学习

January 19, 2016 zr9558 4 Comments

半年前从数学专业转行到了互联网行业做数据挖掘和推荐系统，在做具体的业务的时候遇到了一些知识点，于是自己整理出来。如果有后来人需要转行的话，可以用这份资料来参考一下。大牛请忽视以下的内容，小白可以参考下。

从数学专业转行到工业界做数据挖掘需要的知识储备：

1. Hadoop，HIVE，SQL数据库操作。

Hive用于提取数据，做基本的数据分析。hive的基本函数，比如聚合函数，数学函数，字符串的函数，连接表格函数等。hive的各种语句，比如if else，case等语句。

EXCEL的基本操作需要掌握，可以进行各种数据的处理、统计分析和辅助决策操作，用熟悉了其实挺方便的。

2.编程语言

编程语言最好会python，c/c++，或者java，至少一种。做机器学习的话感觉用python会多一些。

3.操作系统

Linux系统，脚本语言Shell。

4. 数据挖掘和机器学习的基础知识和算法

逻辑回归算法 Logistic Regression（LR），

支持向量机算法 Support Vector Machine（SVM），

物质扩散和热传导算法（Heat Spreading），

Gradient Boosting Decision Tree（GBDT），

聚类算法，神经网络算法，决策树，随机森林，异常值检测等常用算法需要掌握。

特征工程的基础知识：根据相应的产品进行必要的特征构造，物品特征，交叉特征等。

其中LR使用广泛：由于LR是使用线性方法来处理非线性的问题，导致特征工程十分复杂，交叉项多（二维或者三维的交叉）。

工程上的最优化论文推荐：
Ad Click Prediction a View from the Trenches
需要了解的是相关论文的背景SGD算法，Truncated Gradient算法，RDA算法，FOBOS算法，FTRL算法等。

5. 统计学：

时间序列模型，变量的相关系数，ROC曲线和AUC，交叉验证，主成分分析。

6. 大数据，推荐系统，计算广告学的科普书籍

推荐系统

Truncated Gradient (TG) 算法简介

January 12, 2016 zr9558 2 Comments

现在做在线学习和 CTR 常常会用到逻辑回归（ Logistic Regression），而传统的批量（batch）算法无法有效地处理超大规模的数据集和在线数据流，美国的 Google 公司先后三年时间（2010年-2013年）从理论研究到实际工程化实现的 FTRL（Follow-the-regularized-Leader）算法，在处理诸如逻辑回归之类的带非光滑正则化项（例如 L1 范数，做模型复杂度控制和稀疏化）的凸优化问题上性能非常出色。

通常，优化算法中的 gradient descent 等解法，是对一批样本进行一次求解，得到一个全局最优解。但是，实际的互联网广告应用需要的是快速地进行模型的更新。为了保证快速的更新，训练样本是一条一条地过来的，每来一个样本，模型的参数对这个样本进行一次迭代，从而保证了模型的及时更新，这种方法叫做在线梯度下降法（Online gradient descent）。

在应用的时候，线上来的每一个广告请求，都提取出相应的特征，再根据模型的参数，计算一个点击某广告的概率。在线学习的任务就是学习模型的参数。所谓的模型的参数，其实可以认为是一个目标函数的解。跟之前说的根据批量的样本计算一个全局最优解的方法的不同是，解这个问题只能扫描一次样本，而且样本是一条一条地过来的。

当然这会有误差，所以为了避免这种误差，又为了增加稀疏性，有人又想到了多个版本的算法，Google 公司有人总结了其中几种比较优秀的，例如 FOBOS，AOGD 和微软的 RDA，同时提出了Google自己的算法 FTRL-Proximal。其中，FTRL-Proximal 在稀疏性和精确度等方面表现都比较好。

问题描述（最小化目标函数）

等价条件：

（1）约束优化（convex constraint formulation）：

$\hat{w}=argmin_{w}\sum_{i=1}^{n}L(w,z_{i})$ subject to $||w||_{1}\leq s$

（2）无约束优化描述（soft regularization formulation）：

$\hat{w}=argmin_{w}\sum_{i=1}^{n}L(w,z_{i})+\lambda ||w||_{1}$

注：当选择合适的常数 $\lambda$ 时，这两种描述是等价的。

损失函数：

Linear Regression：

$h(W,X_{j})=W^{T}X_{j}, \ell(W,Z)=\sum_{j=1}^{M}(y_{j}-W^{T}X_{j})^{2}$

Logistic Regression：

$h(W,X_{j})=1/(1+\exp(-W^{T}X_{j})), \ell(W,Z)=\sum_{j=1}^{M}\log(1+\exp(-y_{j}W^{T}X_{j}))$

传统算法（Gradient Descent）

Batch Gradient Descent: Repeat Until Convergence

{ $W^{(t+1)}=W^{(t)}-\eta^{(t)}\nabla\ell_{W}(W^{(t)},Z)$ }

这里的 Gradient Descent 是一种批量处理的方式（Batch），每次更新 W 的时候都需要扫描所有样本来计算一个全局梯度 $\nabla\ell_{W}\ell(W^{(t)},Z).$

传统算法（Stochastic Gradient Descent）

Stochastic Gradient Descent 是另外一种权重更新方法：

Loop{

for j=1 to M { $W^{(t+1)}=W^{(t)}-\eta^{(t)}\nabla\ell_{W}(W^{(t)},Z_{j})$ }

}

这里每次迭代仅仅根据单个样本更新权重 W，这种算法称为随机梯度下降法（Stochastic Gradient Descent）。

Truncated Gradient 算法简介

为了得到稀疏的特征权重 W，最简单粗暴的方式就是设定一个阈值，当 W 的某维度上系数小于这个阈值时将其设置为 0（称作简单截断）。这种方法实现起来很简单，也容易理解。但实际中（尤其在OGD里面）W 的某个系数比较小可能是因为该维度训练不足引起的，简单进行截断会造成这部分特征的丢失。

截断梯度法（TG, Truncated Gradient）是由John Langford，Lihong Li 和 Tong Zhang 在2009年提出，实际上是对简单截断的一种改进。下面首先描述一下 L1 正则化和简单截断的方法，然后我们再来看TG对简单截断的改进以及这三种方法在特定条件下的转化。

（1）L1 正则化法

由于 L1 正则项在 0 处不可导，往往会造成平滑的凸优化问题变成非平滑凸优化问题，因此在每次迭代中采用次梯度计算 L1 正则项的梯度。权重更新方式为：

$W_{(t+1)}=W_{(t)}-\eta^{(t)}G^{(t)}-\eta^{(t)}\lambda sgn(W^{t})$

注意，这里 $\lambda \in \mathbb{R}$ 是一个标量，且 $\lambda\geq 0$ ，为 L1 正则化参数。 $sgn(v)$ 是符号函数，如果 $V=(v_{1},...,v_{N})\in \mathbb{R}^{N}$ 是一个向量，那么 $sgn(V)=(sgn(v_{1}),...,sgn(v_{N}))\in\mathbb{R}^{N}$ 。 $\eta^{(t)}$ 是学习率，通常假设为 $t^{-0.5}$ 的函数。 $G^{(t)}=\nabla \ell(W^{(t)},Z^{(t)})$ 代表了第 t 次迭代中损失函数的梯度，由于 OGD 每次仅根据观测到的一个样本进行权重更新，因此也不再使用区分样本的下标 j。

（2）简单截断法

以 k 为窗口，当 t/k 不为整数时采用标准的SGD进行迭代，当 t/k 为整数时，采用如下权重更新方式：这里的 $T_{0}(v_{i},\theta)$ 是分段函数，

$W^{(t+1)}=T_{0}(W^{(t)}-\eta^{(t)}G^{(t)},\theta)$

$T_{0}(v_{i},\theta)=0 \text{ if } |v_{i}|\leq \theta,$

$T_{0}(v_{i},\theta)=v_{i} \text{ otherwise}.$

这里 $\theta\in \mathbb{R}$ 并且 $\theta\geq 0$ 。如果 $V=(v_{1},...,v_{N})\in \mathbb{R}^{N}$ 是一个向量，那么 $T_{0}(V,\theta)=(T_{0}(v_{1},\theta),...,T_{0}(v_{N},\theta))\in \mathbb{R}^{N}$ 。

（3）截断梯度法（Truncated Gradient）

上面的简单截断法看上去十分 aggressive，因此截断梯度法在此基础上进行了改进工作。

$W^{(t+1)}=T_{1}(W^{(t)}-\eta^{(t)}G^{(t)},\eta^{(t)}\lambda^{(t)},\theta)$

这里的方程 $T_{1}$ 定义为：

$T_{1}(v_{i},\alpha,\theta)=\max(0,v_{i}-\alpha) \text{ if } v_{i}\in [0,\theta]$

$T_{1}(v_{i},\alpha,\theta)=\min(0,v_{i}+\alpha) \text{ else if } v_{i}\in [-\theta,0)$

$T_{1}(v_{i},\alpha,\theta)=v_{i} \text{ otherwise }$

其中 $\lambda^{(t)}\in \mathbb{R}$ ，并且 $\lambda^{(t)}\geq 0$ 。Truncated Gradient 方法同样是以 k 作为窗口，每进行 k 步就进行一次截断操作。当 t/k 不是整数时， $\lambda^{(t)}=0$ ，当 t/k 是整数时， $\lambda^{(t)}=k\lambda$ 。从上面的公式可以看出， $\lambda, \theta$ 决定了 W 的稀疏程度，如果 $\lambda$ 和 $\theta$ 都很大，那么稀疏性就会越强。特别的，当 $\lambda=\theta$ 时，此时只需要控制一个参数就可以控制稀疏性。

Truncated Gradient 的算法：

输入 ，初始化 
for t = 1,2,3,... 计算 
按照下面规则更新 W,

    （i）当 t/k 不是整数时，采用标准的 SGD (Stochastic Gradient Descent) 进行迭代。，并且  for all .

    （ii）当 t/k 是整数时，采取截断技术。

     , if 

     , else if 

     , otherwise
return W.

（4）Truncated Gradient，简单截断法，L1 正则化之间的关系。

简单截断法和截断梯度法的区别在于选择了不同的截断公式 $T_{0}$ 和 $T_{1}$ 。如下图所示：

T0 and T1

Truncated Gradient -> 简单截断法

从上图可以直接看出：选择 $\alpha=\theta$ ，截断梯度法就可以变成简单截断法。从公式上也可以通过计算直接得出。

Truncated Gradient -> L1 正则化

貌似有一点问题，需要重新推导。

推荐系统

Forward-Backward Splitting (FOBOS) 算法简介

January 12, 2016 zr9558 Leave a comment

FOBOS 算法简介

（1）FOBOS（Forward Backward Splitting）算法原理

前向后向切分（FOBOS，Forward Backward Splitting）是 John Duchi 和 Yoran Singer 提出的。在该算法中，权重的更新分成两个步骤：

$W^{(t+0.5)}=W^{(t)}-\eta^{(t)}G^{(t)}$

$W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}$

第一个步骤实际上是一个标准的梯度下降（SGD），第二个步骤是对第一个步骤的结果进行局部调整。写成一个公式那就是：

$W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}$

假设 $F(W)=\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)$ ，如果 $W^{(t+1)}$ 存在一个最优解，那么可以推断 0 向量一定属于 $F(W)$ 的次梯度集合：

$0 \in \partial F(W)=W-W^{(t)}+\eta^{(t)}G^{(t)}+\eta^{(t+0.5)}\partial\Psi(W)$ .

因为 $W^{(t+1)}=argmin_{W}F(W)$ , 那么可以得到权重更新的另外一种形式：

$W^{(t+1)}=W^{(t)}-\eta^{(t)}G^{(t)}-\eta^{(t+0.5)}\partial\Psi(W^{(t+1)})$

从上面的公式可以看出，更新后的 $W^{(t+1)}$ 不仅和 $W^{(t)}$ 有关，还和自己 $\Psi(W^{(t+1)})$ 有关。这也许就是”前向后向切分”这个名称的由来。

（2）FOBOS（Forward Backward Splitting）的 L1 正则化

假设 $\Psi(W)$ 是 L1 范数，中间向量是 $W^{(t+0.5)}=(v_{1},...,v_{N})\in\mathbb{R}^{N}$ , 并且参数 $\tilde{\lambda}=\eta^{(t+0.5)}\lambda$ ，那么公式就可以展开得到

$W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t+0.5)}||_{2}^{2}+\eta^{(t+0.5)}\Psi(W)\}$

$=argmin_{W}\sum_{i=1}^{N}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|).$

所以，可以对特征权重 W 的每一个维度进行单独求解：

$w^{(t+1)}_{i}=argmin_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|)$ for all $latex 1\leq i \leq N$.

Claim. 如果 $w_{i}^{*}$ 是 $\min_{w_{i}}(\frac{1}{2}(w_{i}-v_{i})^{2}+\tilde{\lambda}|w_{i}|)$ 的最优解，那么 $w_{i}^{*}v_{i}\geq 0$ .

证明：反证法，如果 $w_{i}^{*}v_{i}<0$ ，那么 $\frac{1}{2}v_{i}^{2}<\frac{1}{2}(w_{i}^{*}-v_{i})^{2}+\tilde{\lambda}|w_{i}^{*}|$ ，这与条件矛盾。

通过数学计算可以证明：在 L1 正则化下，FOBOS 的特征权重的各个维度的更新公式是：

$w_{i}^{(t+1)}=sgn(v_{i})\max(0,|v_{i}|-\tilde{\lambda})$

$= sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})\max\{0,|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|-\eta^{(t+0.5)}\lambda\}$ for all $1\leq i \leq N,$

其中 $g_{i}^{(t)}$ 是梯度 $G^{(t)}$ 在第 i 个维度的分量。

从公式上看，

如果 $|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\leq\eta^{(t+0.5)}\lambda$ ，则有 $w_{i}^{(t+1)}=0.$ 意思就是如果这次训练产生梯度的变化不足以令权重值发生足够大的变化时，就认为在这次训练中该维度不够重要，应该强制其权重是0.

如果 $|w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)}|\geq\eta^{(t+0.5)}\lambda$ ，那么则有

$w_{i}^{(t+1)}=(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})-\eta^{(t+0.5)}\lambda \cdot sgn(w_{i}^{(t)}-\eta^{(t)}g_{i}^{(t)})$

L1-FOBOS 的算法：

（1）输入 ，初始化 
（2）for , 计算 
     按照公式更新 ， 
     for all 
（3）Return W

（3）L1-FOBOS 与 Truncated Gradient 的关系

令 $\theta=+\infty, k=1, \lambda_{TG}^{(t)}=\eta^{(t+0.5)}\lambda$ ，可以得到 L1-FOBOS 与 Truncated Gradient 完全一致，换句话说 L1-FOBOS 是 Truncated Gradient 在一些特定条件下的形式。

推荐系统

Regularized Dual Averaging Algorithm (RDA)

January 12, 2016 zr9558 Leave a comment

Regularized Dual Averaging Algorithm 算法介绍

（一）RDA（Regularized Dual Averaging Algorithm）算法原理

RDA（Regularized Dual Averaging Algorithm）叫做正则对偶平均算法，特征权重的更新策略是：

$W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \Psi(W) +\frac{\beta^{(t)}}{t}h(W)\}$

其中 $G^{(t)}\cdot W$ 指的是向量 $G^{(t)}$ 和 $W$ 的内积， $\Psi(W)$ 是正则项， $h(W)$ 是一个严格凸函数， $\{\beta^{(t)}|t\geq 1\}$ 是一个非负递增序列。

从公式中可以看出：

$\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W$ 包括了之前所有梯度的平均值。
具有正则项 $\Psi(W)$ 。
额外项 $\frac{\beta^{(t)}}{t}h(W)$ 。

（二）RDA 的 L1 正则化

假设 $\Psi(W)=||W||_{1}$ ； $h(W)=\frac{1}{2}||W||_{2}^{2}$ ，i.e. $h(W)$ 是一个严格凸函数； $\beta^{(t)}=\gamma\sqrt{t} \text{ with } \gamma>0$ 是一个非负递增序列。那么 RDA 算法就可以写成：

$W^{(t+1)}=argmin_{W}\{\frac{1}{t}\sum_{r=1}^{t}G^{(r)}\cdot W + \lambda||W||_{1}+\frac{\gamma}{2\sqrt{t}}||W||_{2}^{2}\}$

此时可以采取同样的策略，把各个维度拆分成 N 个独立的问题来处理。也就是：

$w_{i+1}^{(t+1)}=argmin_{w_{i}}\{\overline{g}_{i}^{(t)}+\lambda|w_{i}|+\frac{\gamma}{2\sqrt{t}}w_{i}^{2}\}$

其中， $\lambda>0, \gamma>0,$ $\overline{g}_{i}^{(t)}=\frac{1}{t}\sum_{r=1}^{t}g_{i}^{(r)}.$

通过数学推导可以证明：

$w_{i}^{(t+1)}=0,$ if $|\overline{g}_{i}^{(t)}|<\lambda$

$w_{i}^{(t+1)}=-\frac{\sqrt{t}}{\gamma}(\overline{g}_{i}^{(t)}-\lambda\cdot sgn(\overline{g}_{i}^{(t)})),$ otherwise

意思就是：当某个维度的累加平均值 $|\overline{g}_{i}^{(t)}|$ 小于 $\lambda$ 时，该维度的权重被设置成零，此时就可以产生特征权重的稀疏性。

RDA 的算法

（1）输入 ，初始化 
（2）for  
         
         更新 ：
         
     end
     return W

（三）L1-RDA 与 L1-FOBOS 的对比

从截断方式来看，在 RDA 的算法中，只要梯度的累加平均值小于参数 $\lambda$ ，就直接进行截断，说明 RDA 更容易产生稀疏性；同时，RDA 中截断的条件是考虑梯度的累加平均值，可以避免因为某些维度训练不足而导致截断的问题，这一点与 TG，FOBOS 不一样。通过调节参数 $\lambda$ 可以在精度和稀疏性上进行权衡。

（四）L1-RDA 与 L1-FOBOS 形式上的统一

在 L1-FOBOS 中，假设 $\eta^{(t+0.5)}=\eta^{(t)}=\Theta(t^{-0.5})$ ，可以得到：

$W^{(t+1)}=argmin_{W}\{\frac{1}{2}||W-W^{(t)}+\eta^{(t)}G^{(t)}||_{2}^{2}+\eta^{(t)}\lambda||W||_{1}\}$

通过计算可以把 L1-FOBOS 写成：

$W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2\eta^{(t)}}||W-W^{(t)}||_{2}^{2}$

同时 L1-RDA 可以写成：

$W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W + t\lambda||W||_{1}+\frac{1}{2\eta^{(t)}}||W-0||_{2}^{2} \}$

其中 $G^{(1:t)}=\sum_{s=1}^{t}G^{(s)}$ 。如果令 $\sigma^{(s)}=\frac{1}{\eta^{(s)}}-\frac{1}{\eta^{(s-1)}},$ $\sigma^{(1:t)}=\frac{1}{\eta^{(t)}},$ $\sigma^{(1:t)}=\sum_{s=1}^{t}\sigma^{(s)},$ 上面的公式可以写成：

L1-FOBOS：

$W^{(t+1)}=argmin_{W}\{G^{(t)}\cdot W+\lambda||W||_{1}+\frac{1}{2}\sigma^{(1:t)}||W-W^{(t)}||_{2}^{2}\}$

L1-RDA ：

$W^{(t+1)}=argmin_{W}\{G^{(1:t)}\cdot W + t\lambda||W||_{1}+\frac{1}{2}\sigma^{(1:t)}||W-0||_{2}^{2} \}$

可以看出：

L1-FOBOS 考虑了梯度和当前模的 L1 正则项，L1-RDA 考虑的是累积梯度。
L1-FOBOS 的第三项限制 W 不能够距离已经迭代过的 $W^{(t)}$ 值太远，L1-RDA 的第三项限制的是 W 不能够距离 0 太远。

数据挖掘与机器学习

KL散度（Kullback-Leibler Divergence）

November 17, 2015 zr9558 4 Comments

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

KL 散度的数学定义：

对于离散空间的两个概率分布 $P$ 和 $Q$ 而言，从 $Q$ 到 $P$ 的KL散度被定义为

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

换句话说，它是两个概率分布 $P$ 和 $Q$ 的对数差的期望，这里的期望是以概率 $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$ 的两个概率分布 $P$ 和 $Q$ 而言，从 $Q$ 到 $P$ 的 KL 散度被定义为：

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

这里的 $p$ 和 $q$ 是概率分布 $P$ 和 $Q$ 的概率密度。

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）如果定义分布 $P$ 和 $Q$ 的交叉墒是

$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 散度是两个概率分布 $P$ 和 $Q$ 差别的非对称性的度量。 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散度来描述这件事情。

数据挖掘与机器学习

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

November 13, 2015 zr9558 1 Comment

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

线性模型

一维输入变量

假设学习对象 $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第一逼近定理：假设是闭区间上的连续函数，对于任意的，则存在多项式使得对于所有的，有。

根据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函数的层级模型也被称为人工神经网络模型。

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

推荐系统

点击率(CTR)融入物品相似度

October 9, 2015 zr9558 Leave a comment

假设物品 $A$ 与其余三个物品1，2，3的相似度分别是 $S_{A1}, S_{A2}, S_{A3}.$ 物品1，2，3的点击率（click through rate）分别是 $CTR(1), CTR(2), CTR(3).$ 此刻如果物品3的点击率过低，那么需要把第3个物品与物品 $A$ 的相似度降低，使得第4个物品与A的相似度 $S_{A4}>S_{A3},$ 从而使得第4个物品能够取代第3个物品。

定义物品 $A$ 与物品1，2，3的相似度如下：

$S_{Aj}^{'}(x)=\frac{S_{Aj}\cdot(x+CTR(j))}{x+(\sum_{k=1}^{3}S_{Ak}\cdot CTR(k))/(\sum_{k=1}^{3}S_{Ak})} \text{ for all }1\leq j\leq 3.$

其中 $x\geq 0$ 是待定的系数。下面就来研究新的相似度满足的性质。

性质1. 相似度的总和没有变化。i.e. $\sum_{j=1}^{3}S_{Aj}^{'}(x)=\sum_{j=1}^{3}S_{Aj}$ 对任何的实数 $x\geq 0$ 都成立。

性质2. 如果 $CTR(1)=\max_{1\leq k\leq 3}CTR(k),$ i.e. 第1个物品的点击率最高，那么

(i) $S_{A1}^{'}(x)\geq S_{A1}$ 对于任何 $x\geq 0$ 都成立。

(ii) $S_{A1}^{'}(x)$ 对于 $x$ 是非增函数，i.e. 导数 $DS_{A1}^{'}(x)\leq 0.$

(iii) $\lim_{x\rightarrow \infty}S_{A1}^{'}(x)=S_{A1}.$ 换句话说，随着 $x$ 的增大， $S_{A1}^{'}(x)$ 是递减趋向于原始的相似度 $S_{A1}.$

性质3. 如果第3个物品的点击率最低，i.e. $CTR(3)=\min_{1\leq k\leq 3} CTR(k),$ 那么

(i) $S_{A3}^{'}(x)\leq S_{A3}$ 对于任何 $x\geq 0$ 都成立。

(ii) $S_{A3}^{'}(x)$ 对于 $x$ 是非减函数，i.e. 导数 $DS_{A3}^{'}(x)\geq 0.$

(iii) $\lim_{x\rightarrow \infty}S_{A3}^{'}(x)=S_{A3}.$ 换句话说，随着 $x$ 的增大， $S_{A3}^{'}(x)$ 逐渐增大趋向于原始的相似度 $S_{A3}.$

(iv) 特别的，如果 $CTR(3)=0,$ 那么 $S_{A3}^{'}(0)=0,$ 通过选择合适的 $x_{0}\geq 0,$ 可以使得 $S_{A3}^{'}(x_{0})<S_{A4}.$ 在这里的 $S_{A4}$ 指的是物品 $A$ 与第4个物品的相似度。

推荐系统

物质扩散模型

September 27, 2015 zr9558 Leave a comment

引言

在推荐系统中，常常用二部图来表示用户和物品的关系：把用户（Users）看成一类点，把物品（Objects）看成另一类点。如果用户购买了某种物品，那么用户和物品之间就存在一条连线，也就是一条边。如果用户没有购买某种物品，那么用户和物品之间就没有连线。但是用户和用户之间，物品和物品之间是不存在连线的。换句话说就是同一类点之间是不存在连线的。这样的图结构就叫做二部图。电子商务中间的物品推荐，可以看成是二部图的边的挖掘问题。扩散过程可以用来寻找二部图中两个节点的关联强度。经典的扩散过程分成两类：一种叫做物质扩散（Probabilistic Spreading），它满足能量守恒定律；另一种叫做热传导（Heat Spreading），一般由一个或多个热源（物品）驱动，不一定满足能量守恒定律。

物质扩散（Probabilistic Spreading）算法流程

如图所示，用黄色的点来表示用户，用红色的点表示物品。用户有三位，物品有四个。第一个用户和第一个物品有连线表示第一个用户购买了第一个物品，而与第二个物品没有连线表示第一个用户没有购买第二个物品。根据图像(a)所示，第一个物品和第三个物品有能量1，第二个物品和第四个物品有能量0.对于物质扩散过程，第一个物品需要把自己的能量1平均分配给购买过它的用户一和用户二。第三个物品也需要把自己的能量1平均分配给购买过它的用户一和用户三。用户的能量就是所有用物品得到的能量的总和。正如图像(b)所示，第一个用户此时具有能量1，第二个和第三个用户都具有能量1/2.接下来，每个用户再把自身的能量平均分配给所有购买过的物品，物品的能量则是从所有用户得到的能量的总和。所以第一个物品的能量就是第一个用户的能量乘以0.5加上第二个用户的能量乘以1/3，所得的能量则是2/3.其他物品的能量用类似的方法计算。

物质扩散（Probabilistic Spreading）数学模型

假设有m个用户（Users）和n个物品（Objects），可以构造矩阵 $A_{m\times n},$ 如果 $a_{ij}=1$ ，那么表示用户i购买了物品j；如果 $a_{ij}=0$ , 那么表示用户i没有购买物品j。用 $(c_{1},\cdot\cdot\cdot, c_{n})$ 来表示物品1到物品n的能量。用 $k(U_{\alpha})=\sum_{j=1}^{n}a_{\alpha j}$ 表示用户 $\alpha$ 的度，也就是该用户购买的物品数量。用 $k(O_{j})=\sum_{i=1}^{m}a_{ij}$ 表示物品j的度，也就是该物品被多少个用户购买过。根据物质扩散的算法描述，第一步需要计算出用户从物品那里得到的能量，此时用户 $i$ 得到的能量用 $b_{i}$ 表示，那么

$b_{i}=\sum_{\ell=1}^{n} a_{i\ell}\cdot c_{\ell}/k(O_{\ell}) \text{ for all } 1\leq i\leq m.$

后面需要通过用户的能量来更新物品的能量，假设物品 $j$ 的新能量用 $c_{j}^{'}$ 表示，那么

$c_{j}^{'}=\sum_{i=1}^{m}a_{ij}\cdot b_{i}/ k(U_{i}) \text{ for all } 1\leq j \leq n.$

把 $b_{i}$ 的公式带入上面可以得到对于 $1\leq j\leq n,$ 我们有

$c_{j}^{'}=\sum_{\ell=1}^{n}\left(\frac{1}{k(O_{\ell})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}\right)\cdot c_{\ell}=\sum_{\ell=1}^{n}w_{j\ell}^{P}\cdot c_{\ell}.$

在这里对于 $1\leq j\leq n, 1\leq \ell \leq n,$

$w_{j\ell}^{P}=\frac{1}{k(O_{\ell})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}.$

假设 $n\times n$ 矩阵 $W^{P}=(w_{j\ell}^{P}),$ 列向量 $\vec{C}=(c_{1},\cdot\cdot\cdot,c_{n})^{T}$ 和 $\vec{C^{'}}=(c_{1}^{'},\cdot\cdot\cdot,c_{n}^{'})^{T}$ ，那么 $\vec{C^{'}}=W^{P}\vec{C}.$

性质1. 矩阵每列的和都是1，i.e. 对于所有的都成立。

证明. $\sum_{j=1}^{n}w_{j\ell}^{P}=\sum_{j=1}^{n}\sum_{i=1}^{m}\frac{1}{k(O_{\ell})}\cdot\frac{a_{ij}a_{i\ell}}{k(U_{i})}=\sum_{i=1}^{m}\frac{a_{i\ell}}{k(O_{\ell})}=1.$

性质2. 对于所有的都成立。换言之，矩阵不一定是对称矩阵，只有在所有物品的度都完全一致的情况下才是对称矩阵。

证明. 根据 $w_{j\ell}^{P}$ 和 $w_{\ell j}^{P}$ 的定义可以得到结论。

性质3. 矩阵对角线上的元素是该列的最大值。i.e. 对于所有的都成立。

证明. 根据矩阵 $A$ 的定义，对于所有的 $1\leq j,\ell\leq n,$ 可以得到

$w_{jj}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{ij}^{2}}{k(U_{i})}\geq\frac{1}{k(O_{j})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}=w_{\ell j}^{P}.$

性质4. 能量守恒定律：

证明. 根据前面的性质，已经知道 $W^{P}$ 矩阵每一列的和都是1，i.e. $\sum_{j=1}^{n}w_{j\ell}^{P}=1.$ 可以直接计算得到： $\sum_{j=1}^{n}c_{j}^{'}=\sum_{j=1}^{n}\sum_{\ell=1}^{m}w_{j\ell}^{P}c_{\ell}=\sum_{\ell=1}^{n}c_{\ell}\cdot\sum_{j=1}^{n}w_{j\ell}^{P}=\sum_{\ell=1}^{m}c_{\ell}.$

性质5. 如果物品的用户都是物品的用户，换句话说，如果 则有那么对于所有的都成立。反之，如果那么物品的用户都是物品的用户。

证明. 根据 $w_{j\ell}^{P}$ 的定义，可以得到

$w_{jj}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{ij}^{2}}{k(U_{i})}=\frac{1}{k(O_{j})}\cdot \sum_{\{1\leq i\leq m, a_{ij}=1\}}\frac{1}{k(U_{i})},$

$w_{\ell j}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{i\ell}a_{ij}}{k(U_{i})}=\frac{1}{k(O_{j})}\cdot \sum_{1\leq i\leq m, a_{ij}=1}\frac{a_{i\ell}}{k(U_{i})}.$

根据条件，如果 $a_{ij}=1,$ 则有 $a_{i\ell}=1,$ 那么上面两个式子相等。i.e. $w_{jj}^{P}=w_{\ell j}^{P}$ 对于所有的 $1\leq \ell \leq n$ 都成立。

根据上面性质，可以定义变量

$I_{j}=\sum_{\ell=1}^{n}(w_{\ell j}^{P}/w_{jj}^{P})^{2},$

其中 $w_{\ell j}^{P}/w_{jj}^{P}$ 可以看成物品 $O_{j}$ 与物品 $O_{j}$ 的独立程度。如果 $w_{\ell j}^{P}/w_{jj}^{P}=1,$ 那么说明物品 $O_{j}$ 的用户都是物品 $O_{\ell}$ 的用户。如果 $w_{\ell j}^{P}/w_{jj}^{P}=0,$ 那么说明物品 $O_{j}$ 的用户与物品 $O_{\ell}$ 的用户则没有交集。换言之，物品 $O_{j}$ 与物品 $O_{\ell}$ 则相对独立。根据这个性质，如果 $I_{j}$ 越小，那么物品 $O_{j}$ 与其他物品就相对独立。

性质6. 对于所有的都是成立的。

证明. 根据以上性质可以得到 $w_{\ell j}^{P}\leq w_{jj}^{P}$ 对于 $1\leq \ell \leq n$ 都成立，并且 $I_{j}\geq (w_{jj}^{P}/w_{jj}^{P})^{2}=1,$ 所以上面性质成立。

基于物质扩散算法的用户相似度

回顾一下基于用户的协同过滤算法：用户 $U_{\alpha}, U_{\beta}$ 的相似度是

$S_{\alpha \beta}=(\sum_{j=1}^{n}a_{\alpha j}\cdot a_{\beta j})/\min\{k(U_{\alpha}),k(U_{\beta})\}$

或者使用余弦表达式

$S_{\alpha \beta}=(\sum_{j=1}^{n}a_{\alpha j}\cdot a_{\beta j})/\sqrt{k(U_{\alpha})\cdot k(U_{\beta})}.$

如果用户 $U_{i}$ 并没有选择物品 $O_{j},$ 那么预测分数则是

$v_{ij}=(\sum_{1\leq \ell \leq m, \ell\neq i} S_{i\ell}\cdot a_{j\ell}) / \sum_{1\leq \ell \leq m, \ell\neq i} S_{i\ell}.$

这里的求和指的把除了用户 $i$ 的其他用户做相似度的加权，看用户 $U_{\ell}$ 是否购买了物品 $O_{j}.$ 然后对于任意的用户和物品组成的对 $(i,j),$ 只要 $a_{ij}=0$ （意思是用户 $U_{i}$ 并没有购买过物品 $O_{j}$ ），根据预测分数 $v_{ij}$ 从大到小对 $1\leq j\leq n$ 排序，推荐 $v_{ij}$ 值大的物品给用户 $U_{i}$ 即可。以上就是基于用户的协同过滤算法。

下面来介绍基于物质扩散方法的算法。与上面的方法类似，第一步就是定义用户相似度 $S_{\alpha \beta}^{P}$ 如下：

$S_{\alpha \beta}^{P}=\frac{1}{k(U_{\beta})}\cdot \sum_{j=1}^{n}\frac{a_{\alpha j}\cdot a_{\beta j}}{k(O_{j})}.$

上面定义表示物品 $O_{j}$ 购买的人越多，用户的相似度 $S_{\alpha \beta}^{P}$ 就会减少。原因就是比方说像新华字典这种购买的人非常多的物品，并不能说明大多数人都是相似的，反而是购买数学分析这种物品的人相似性比较大。也就是说物品的热门程度 $k(O_{j})$ 对计算用户相似度的时候有抑制作用。此时的评分系统则是：如果用户 $U_{\alpha}$ 之前没有购买物品 $O_{i},$ 那么其预测分数则是

$v_{\alpha i}=(\sum_{1\leq \beta\leq m, \beta\neq\alpha}S_{\alpha \beta}^{P}\cdot a_{\beta i})/\sum_{1\leq \beta\leq m, \beta\neq\alpha}S_{\alpha \beta}^{P}$