Question

红色石头的个人网站： redstonewill.com

上节课我们主要介绍了 Radial Basis Function Network。它的原理就是基于距离相似性（distance-based similarities）的线性组合（linear aggregation）。我们使用 k-Means clustering 算法找出具有代表性的 k 个中心点，然后再计算与这些中心点的 distance similarity，最后应用到 RBF Network 中去。

LinearNetwork Hypothesis

回顾一下，我们在机器学习基石课程的第一节课就提到过，机器学习的目的就是让机器从数据 data 中学习到某种能力 skill。我们之前举过一个典型的推荐系统的例子。就是说，假如我们手上有许多不同用户对不同电影的排名 rank，通过机器学习，训练一个模型，能够对用户没有看过的某部电影进行排名预测。

一个典型的电影推荐系统的例子是 2006 年 Netflix 举办的一次比赛。数据包含了 480189 个用户和 17770 部电影，总共 1 亿多个排名信息。该推荐系统模型中，我们用表示第 n 个用户，这是一个抽象的特征，常常使用数字编号来代替具体哪个用户。输出方面，我们使用表示第 n 个用户对第 m 部电影的排名数值。

下面我们来进一步看看这些抽象的特征，是用户的 ID，通常用数字表示。例如 1126,5566,6211 等。这些编号并没有数值大小上的意义，只是一种 ID 标识而已。这类特征被称为类别特征（categorical features）。常见的 categorical features 包括：IDs，blood type，programming languages 等等。而许多机器学习模型中使用的大部分都是数值特征（numerical features）。例如 linear models，NNet 模型等。但决策树（decision tree）是个例外，它可以使用 categorical features。所以说，如果要建立一个类似推荐系统的机器学习模型，就要把用户 ID 这种 categorical features 转换为 numerical features。这种特征转换其实就是训练模型之前一个编码（encoding）的过程。

一种最简单的 encoding 方式就是 binary vector encoding。也就是说，如果输入样本有 N 个，就构造一个维度为 N 的向量。第 n 个样本对应向量上第 n 个元素为 1，其它元素都是 0。下图就是一个 binary vector encoding 的例子。

经过 encoding 之后，输入是 N 维的 binary vector，表示第 n 个用户。输出是 M 维的向量，表示该用户对 M 部电影的排名数值大小。注意，用户不一定对所有 M 部电影都作过评价，未评价的恰恰是我们要预测的（下图中问号？表示未评价的电影）。

总共有 N 个用户，M 部电影。对于这样的数据，我们需要掌握每个用户对不同电影的喜爱程度及排名。这其实就是一个特征提取（feature extraction）的过程，提取出每个用户喜爱的电影风格及每部电影属于哪种风格，从而建立这样的推荐系统模型。可供选择使用的方法和模型很多，这里，我们使用的是 NNet 模型。NNet 模型中的网络结构是型，其中 N 是输入层样本个数，是隐藏层神经元个数，M 是输出层电影个数。该 NNet 为了简化计算，忽略了常数项。当然可以选择加上常数项，得到较复杂一些的模型。顺便提一下，这个结构跟我们之前介绍的 autoencoder 非常类似，都是只有一个隐藏层。

说到这里，有一个问题，就是上图 NNet 中隐藏层的 tanh 函数是否一定需要呢？答案是不需要。因为输入向量 x 是经过 encoding 得到的，其中大部分元素为 0，只有一个元素为 1。那么，只有一个元素与相应权重的乘积进入到隐藏层。由于，则相当于只有一个权重值进入到 tanh 函数进行运算。从效果上来说，tanh(x) 与 x 是无差别的，只是单纯经过一个函数的计算，并不影响最终的结果，修改权重值即可得到同样的效果。因此，我们把隐藏层的 tanh 函数替换成一个线性函数 y=x，得到下图所示的结构。

由于中间隐藏层的转换函数是线性的，我们把这种结构称为 Linear Network（与 linear autoencoder 比较相似）。看一下上图这个网络结构，输入层到隐藏层的权重维度是 Nx，用向量表示。隐藏层到输出层的权重维度是xM，用矩阵 W 表示。把权重由矩阵表示之后，Linear Network 的 hypothesis 可表示为：

如果是单个用户，由于 X 向量中只有元素为 1，其它均为 0，则对应矩阵 V 只有第 n 列向量是有效的，其输出 hypothesis 为：

Basic Matrix Factorization

刚刚我们已经介绍了 linear network 的模型和 hypothesis。其中 Vx 可以看作是对用户 x 的一种特征转换。对于单部电影，其预测的排名可表示为：

推导完 linear network 模型之后，对于每组样本数据（即第 n 个用户第 m 部电影），我们希望预测的排名与实际样本排名尽可能接近。所有样本综合起来，我们使用 squared error measure 的方式来定义，的表达式如下所示：

上式中，灰色的部分是常数，并不影响最小化求解，所以可以忽略。接下来，我们就要求出最小化时对应的 V 和 W 解。

我们的目标是让真实排名与预测排名尽可能一致，即。把这种近似关系写成矩阵的形式：。矩阵 R 表示所有不同用户不同电影的排名情况，维度是 NxM。这种用矩阵的方式进行处理的方法叫做 Matrix Factorization。

上面的表格说明了我们希望将实际排名情况 R 分解成两个矩阵（V 和 W）的乘积形式。V 的维度是xN 的，N 是用户个数，可以是影片类型，例如（喜剧片，爱情片，悬疑片，动作片，…）。根据用户喜欢的类型不同，赋予不同的权重。W 的维度是xM，M 是电影数目，同样是影片类型，该部电影属于哪一类型就在那个类型上占比较大的权重。当然，维特征不一定就是影片类型，还可以是其它特征，例如明显阵容、年代等等。

那么，Matrix Factorization 的目标就是最小化函数。表达式如下所示：

中包含了两组待优化的参数，分别是和。我们可以借鉴上节课中 k-Means 的做法，将其中第一个参数固定，优化第二个参数，然后再固定第二个参数，优化第一个参数，一步一步进行优化。

当固定的时候，只需要对每部电影做 linear regression 即可，优化得到每部电影的维特征值。

当固定的时候，因为 V 和 W 结构上是对称的，同样只需要对每个用户做 linear regression 即可，优化得到每个用户对维电影特征的喜爱程度。

这种算法叫做 alternating least squares algorithm。它的处理思想与 k-Means 算法相同，其算法流程图如下所示：

alternating least squares algorithm 有两点需要注意。第一是 initialize 问题，通常会随机选取和。第二是 converge 问题，由于每次迭代更新都能减小，会趋向于 0，则保证了算法的收敛性。

在上面的分析中，我们提过 Matrix Factorization 与 Linear Autoencoder 的相似性，下图列出了二者之间的比较。

Matrix Factorization 与 Linear Autoencoder 有很强的相似性，都可以从原始资料汇总提取有用的特征。其实，linear autoencoder 可以看成是 matrix factorization 的一种特殊形式。

Stochastic Gradient Descent

我们刚刚介绍了 alternating least squares algorithm 来解决 Matrix Factorization 的问题。这部分我们将讨论使用 Stochastic Gradient Descent 方法来进行求解。之前的 alternating least squares algorithm 中，我们考虑了所有用户、所有电影。现在使用 SGD，随机选取一笔资料，然后只在与这笔资料有关的 error function 上使用梯度下降算法。使用 SGD 的好处是每次迭代只要处理一笔资料，效率很高；而且程序简单，容易实现；最后，很容易扩展到其它的 error function 来实现。

对于每笔资料，它的 error function 可表示为：

上式中的 err 是 squared error function，仅与第 n 个用户，第 m 部电影有关。其对和的偏微分结果为：

很明显，和都由两项乘积构成。（忽略常数因子 2）。第一项都是，即余数 residual。我们在之前介绍的 GBDT 算法中也介绍过余数这个概念。的第二项是，而的第二项是。二者在结构上是对称的。

计算完任意一个样本点的 SGD 后，就可以构建 Matrix Factorization 的算法流程。SGD for Matrix Factorization 的算法流程如下所示：

在实际应用中，由于 SGD 算法简单高效，Matrix Factorization 大多采用这种算法。

介绍完 SGD for Matrix Factorization 之后，我们来看一个实际的应用例子。问题大致是这样的：根据现在有的样本资料，预测未来的趋势和结果。显然，这是一个与时间先后有关的预测模型。比如说一个用户三年前喜欢的电影可能现在就不喜欢了。所以在使用 SGD 选取样本点的时候有一个技巧，就是最后 T 次迭代，尽量选择时间上靠后的样本放入到 SGD 算法中。这样最后的模型受这些时间上靠后的样本点影响比较大，也相对来说比较准确，对未来的预测会比较准。

所以，在实际应用中，我们除了使用常规的机器学习算法外，还需要根据样本数据和问题的实际情况来修改我们的算法，让模型更加切合实际，更加准确。我们要学会灵活运用各种机器学习算法，而不能只是照搬。

Summary of Extraction Models

从第 12 节课开始到现在，我们总共用了四节课的时间来介绍 Extraction Models。虽然我们没有给出 Extraction Models 明确的定义，但是它主要的功能就是特征提取和特征转换，将原始数据更好地用隐藏层的一些节点表征出来，最后使用线性模型将所有节点 aggregation。这种方法使我们能够更清晰地抓住数据的本质，从而建立最佳的机器学习模型。

下图所示的就是我们介绍过的所有 Extraction Models，除了这四节课讲的内容之外，还包括之前介绍的 Adaptive/Gradient Boosting 模型。因为之前笔记中都详细介绍过，这里就不再一一总结了。

除了各种 Extraction Models 之外，我们这四节课还介绍了不同的 Extraction Techniques。下图所示的是对应于不同的 Extraction Models 的 Extraction Techniques。

最后，总结一下这些 Extraction Models 有什么样的优点和缺点。从优点上来说：

• easy：机器自己完成特征提取，减少人类工作量
• powerful：能够处理非常复杂的问题和特征提取

另一方面，从缺点上来说：

• hard：通常遇到 non-convex 的优化问题，求解较困难，容易得到局部最优解而非全局最优解
• overfitting：模型复杂，容易造成过拟合，需要进行正则化处理

所以说，Extraction Models 是一个非常强大的机器学习工具，但是使用的时候也要小心处理各种可能存在的问题。

总结

本节课主要介绍了 Matrix Factorization。从电影推荐系统模型出发，首先，我们介绍了 Linear Network。它从用户 ID 编码后的向量中提取出有用的特征，这是典型的 feature extraction。然后，我们介绍了基本的 Matrix Factorization 算法，即 alternating least squares，不断地在用户和电影之间交互地做 linear regression 进行优化。为了简化计算，提高运算速度，也可以使用 SGD 来实现。事实证明，SGD 更加高效和简单。同时，我们可以根据具体的问题和需求，对固有算法进行一些简单的调整，来获得更好的效果。最后，我们对已经介绍的所有 Extraction Models 做个简单的总结。Extraction Models 在实际应用中是个非常强大的工具，但是也要避免出现过拟合等问题。

注明：

文章中所有的图片均来自台湾大学林轩田《机器学习技法》课程

更多 AI 资源请关注公众号：红色石头的机器学习之路（ID：redstonewill）