ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
# 15 -- Matrix Factorization 上节课我们主要介绍了Radial Basis Function Network。它的原理就是基于距离相似性(distance-based similarities)的线性组合(linear aggregation)。我们使用k-Means clustering算法找出具有代表性的k个中心点,然后再计算与这些中心点的distance similarity,最后应用到RBF Network中去。 ### **LinearNetwork Hypothesis** 回顾一下,我们在机器学习基石课程的第一节课就提到过,机器学习的目的就是让机器从数据data中学习到某种能力skill。我们之前举过一个典型的推荐系统的例子。就是说,假如我们手上有许多不同用户对不同电影的排名rank,通过机器学习,训练一个模型,能够对用户没有看过的某部电影进行排名预测。 ![这里写图片描述](https://img.kancloud.cn/d5/79/d5799c3b2e6a03e2d61ae03ec20e8e2a_581x127.jpg) 一个典型的电影推荐系统的例子是2006年Netflix举办的一次比赛。数据包含了480189个用户和17770部电影,总共1亿多个排名信息。该推荐系统模型中,我们用![](https://img.kancloud.cn/63/df/63dfbab3c59712ed7a0700431a1a0c36_67x18.jpg)表示第n个用户,这是一个抽象的特征,常常使用数字编号来代替具体哪个用户。输出方面,我们使用![](https://img.kancloud.cn/01/96/01966d28e5f970d700eb58c6e7078696_73x12.jpg)表示第n个用户对第m部电影的排名数值。 ![这里写图片描述](https://img.kancloud.cn/4a/cc/4acc2ade0847265668b07d50484a5ac7_580x182.jpg) 下面我们来进一步看看这些抽象的特征,![](https://img.kancloud.cn/63/df/63dfbab3c59712ed7a0700431a1a0c36_67x18.jpg)是用户的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)的过程。 ![这里写图片描述](https://img.kancloud.cn/05/a1/05a1a0f5e86694ec3d650b83445fa565_580x217.jpg) 一种最简单的encoding方式就是binary vector encoding。也就是说,如果输入样本有N个,就构造一个维度为N的向量。第n个样本对应向量上第n个元素为1,其它元素都是0。下图就是一个binary vector encoding的例子。 ![这里写图片描述](https://img.kancloud.cn/a9/9d/a99d35d4162575cc0118de0c0808672c_390x92.jpg) 经过encoding之后,输入![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg)是N维的binary vector,表示第n个用户。输出![](https://img.kancloud.cn/23/f1/23f1fdeb27de71b5e6113986f1b2bfa6_17x12.jpg)是M维的向量,表示该用户对M部电影的排名数值大小。注意,用户不一定对所有M部电影都作过评价,未评价的恰恰是我们要预测的(下图中问号?表示未评价的电影)。 ![这里写图片描述](https://img.kancloud.cn/ae/33/ae33332c3b268013bfa331b643160599_580x164.jpg) 总共有N个用户,M部电影。对于这样的数据,我们需要掌握每个用户对不同电影的喜爱程度及排名。这其实就是一个特征提取(feature extraction)的过程,提取出每个用户喜爱的电影风格及每部电影属于哪种风格,从而建立这样的推荐系统模型。可供选择使用的方法和模型很多,这里,我们使用的是NNet模型。NNet模型中的网络结构是![](https://img.kancloud.cn/52/8c/528c671e969c73fc8bdc65cd6557b6cc_89x17.jpg)型,其中N是输入层样本个数,![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)是隐藏层神经元个数,M是输出层电影个数。该NNet为了简化计算,忽略了常数项。当然可以选择加上常数项,得到较复杂一些的模型。顺便提一下,这个结构跟我们之前介绍的autoencoder非常类似,都是只有一个隐藏层。 ![这里写图片描述](https://img.kancloud.cn/72/22/722276bffce73be8ab47a66701d4bed3_580x167.jpg) 说到这里,有一个问题,就是上图NNet中隐藏层的tanh函数是否一定需要呢?答案是不需要。因为输入向量x是经过encoding得到的,其中大部分元素为0,只有一个元素为1。那么,只有一个元素![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg)与相应权重的乘积进入到隐藏层。由于![](https://img.kancloud.cn/c9/a6/c9a6d2c8ca779587ff6c84f5360af395_51x15.jpg),则相当于只有一个权重值进入到tanh函数进行运算。从效果上来说,tanh(x)与x是无差别的,只是单纯经过一个函数的计算,并不影响最终的结果,修改权重值即可得到同样的效果。因此,我们把隐藏层的tanh函数替换成一个线性函数y=x,得到下图所示的结构。 ![这里写图片描述](https://img.kancloud.cn/ca/31/ca3138df667147836e1aa4109cbce66c_581x190.jpg) 由于中间隐藏层的转换函数是线性的,我们把这种结构称为Linear Network(与linear autoencoder比较相似)。看一下上图这个网络结构,输入层到隐藏层的权重![](https://img.kancloud.cn/7d/08/7d081ee05b8c3c519c50054dd77a4299_35x25.jpg)维度是Nx![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg),用向量![](https://img.kancloud.cn/c9/79/c979394d7e367a97e365faa1e4f7e519_25x16.jpg)表示。隐藏层到输出层的权重![](https://img.kancloud.cn/6f/de/6fde8110f9a8b379ccd12d3a59be14ae_35x25.jpg)维度是![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)xM,用矩阵W表示。把权重由矩阵表示之后,Linear Network的hypothesis 可表示为: ![](https://img.kancloud.cn/83/e7/83e74060389f488f3ec797ec3c89bfa5_111x20.jpg) 如果是单个用户![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg),由于X向量中只有元素![](https://img.kancloud.cn/1d/eb/1debcab2fe3793b26ea9e43c365edf29_18x11.jpg)为1,其它均为0,则对应矩阵V只有第n列向量是有效的,其输出hypothesis为: ![](https://img.kancloud.cn/c5/26/c526a824de8a6dddc446dbdd13745fa6_113x20.jpg) ![这里写图片描述](https://img.kancloud.cn/67/b9/67b9fad05a9bf39198eed100dffb4efc_580x103.jpg) ### **Basic Matrix Factorization** 刚刚我们已经介绍了linear network的模型和hypothesis。其中Vx可以看作是对用户x的一种特征转换![](https://img.kancloud.cn/14/10/141069974357dc052c30231e17897586_36x18.jpg)。对于单部电影,其预测的排名可表示为: ![](https://img.kancloud.cn/0b/03/0b0319a865f1a0f41c947671bd048311_131x21.jpg) ![这里写图片描述](https://img.kancloud.cn/ec/c8/ecc82c34015cd0472e7e697016a266bb_581x136.jpg) 推导完linear network模型之后,对于每组样本数据(即第n个用户第m部电影),我们希望预测的排名![](https://img.kancloud.cn/2f/3d/2f3dcc2ccd4adfb48cca373c8b20e5aa_42x21.jpg)与实际样本排名![](https://img.kancloud.cn/23/f1/23f1fdeb27de71b5e6113986f1b2bfa6_17x12.jpg)尽可能接近。所有样本综合起来,我们使用squared error measure的方式来定义![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg),![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)的表达式如下所示: ![这里写图片描述](https://img.kancloud.cn/1c/d8/1cd8af81e93c382563204bfb99cf5ac2_580x151.jpg) 上式中,灰色的部分是常数,并不影响最小化求解,所以可以忽略。接下来,我们就要求出![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)最小化时对应的V和W解。 我们的目标是让真实排名与预测排名尽可能一致,即![](https://img.kancloud.cn/e9/59/e959919ad04471d72b3d120008bd23a7_163x21.jpg)。把这种近似关系写成矩阵的形式:![](https://img.kancloud.cn/99/83/9983338609d385202f3a58815c4dc738_82x16.jpg)。矩阵R表示所有不同用户不同电影的排名情况,维度是NxM。这种用矩阵的方式进行处理的方法叫做Matrix Factorization。 ![这里写图片描述](https://img.kancloud.cn/84/1c/841cd3e30579a9e24c1f682571394e06_580x136.jpg) 上面的表格说明了我们希望将实际排名情况R分解成两个矩阵(V和W)的乘积形式。V的维度是![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)xN的,N是用户个数,![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)可以是影片类型,例如(喜剧片,爱情片,悬疑片,动作片,…)。根据用户喜欢的类型不同,赋予不同的权重。W的维度是![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)xM,M是电影数目,![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)同样是影片类型,该部电影属于哪一类型就在那个类型上占比较大的权重。当然,![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)维特征不一定就是影片类型,还可以是其它特征,例如明显阵容、年代等等。 ![这里写图片描述](https://img.kancloud.cn/cf/ed/cfedd9a6942c33103e53d971fa199418_590x238.jpg) 那么,Matrix Factorization的目标就是最小化![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)函数。![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)表达式如下所示: ![这里写图片描述](https://img.kancloud.cn/b1/b3/b1b355c07a3b85ccdcf7ebcf9a954c5d_580x139.jpg) ![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)中包含了两组待优化的参数,分别是![](https://img.kancloud.cn/dc/f3/dcf3fc63de3965b8538f8346a365df96_17x11.jpg)和![](https://img.kancloud.cn/18/c7/18c7cc5d9ffae47d41bca7d224e2234f_25x11.jpg)。我们可以借鉴上节课中k-Means的做法,将其中第一个参数固定,优化第二个参数,然后再固定第二个参数,优化第一个参数,一步一步进行优化。 当![](https://img.kancloud.cn/dc/f3/dcf3fc63de3965b8538f8346a365df96_17x11.jpg)固定的时候,只需要对每部电影做linear regression即可,优化得到每部电影的![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)维特征值![](https://img.kancloud.cn/18/c7/18c7cc5d9ffae47d41bca7d224e2234f_25x11.jpg)。 当![](https://img.kancloud.cn/18/c7/18c7cc5d9ffae47d41bca7d224e2234f_25x11.jpg)固定的时候,因为V和W结构上是对称的,同样只需要对每个用户做linear regression即可,优化得到每个用户对![](https://img.kancloud.cn/0f/87/0f8783f57969e021137bc68a0300d5c7_11x17.jpg)维电影特征的喜爱程度![](https://img.kancloud.cn/dc/f3/dcf3fc63de3965b8538f8346a365df96_17x11.jpg)。 ![这里写图片描述](https://img.kancloud.cn/29/38/293891a0027c47fd6317233755c89f7f_580x177.jpg) 这种算法叫做alternating least squares algorithm。它的处理思想与k-Means算法相同,其算法流程图如下所示: ![这里写图片描述](https://img.kancloud.cn/0b/f6/0bf68a23695e70507b8fdd79b5fc2745_580x195.jpg) alternating least squares algorithm有两点需要注意。第一是initialize问题,通常会随机选取![](https://img.kancloud.cn/dc/f3/dcf3fc63de3965b8538f8346a365df96_17x11.jpg)和![](https://img.kancloud.cn/18/c7/18c7cc5d9ffae47d41bca7d224e2234f_25x11.jpg)。第二是converge问题,由于每次迭代更新都能减小![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg),![](https://img.kancloud.cn/1a/7b/1a7b854be0e1a2c00757595948b96a68_25x15.jpg)会趋向于0,则保证了算法的收敛性。 ![这里写图片描述](https://img.kancloud.cn/6e/fd/6efd3eb226a1ffe716ffe880f35faed6_580x83.jpg) 在上面的分析中,我们提过Matrix Factorization与Linear Autoencoder的相似性,下图列出了二者之间的比较。 ![这里写图片描述](https://img.kancloud.cn/7f/20/7f203f091c4cedab587e88013a9b7154_585x261.jpg) 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来实现。 ![这里写图片描述](https://img.kancloud.cn/ca/e3/cae36485eb2b4c0cdb48eb0d5a3157d9_580x254.jpg) 对于每笔资料,它的error function可表示为: ![这里写图片描述](https://img.kancloud.cn/87/fe/87feb667cd8f74c159d82fa72a535dc8_579x50.jpg) 上式中的err是squared error function,仅与第n个用户![](https://img.kancloud.cn/dc/f3/dcf3fc63de3965b8538f8346a365df96_17x11.jpg),第m部电影![](https://img.kancloud.cn/18/c7/18c7cc5d9ffae47d41bca7d224e2234f_25x11.jpg)有关。其对![](https://img.kancloud.cn/dc/f3/dcf3fc63de3965b8538f8346a365df96_17x11.jpg)和![](https://img.kancloud.cn/18/c7/18c7cc5d9ffae47d41bca7d224e2234f_25x11.jpg)的偏微分结果为: ![](https://img.kancloud.cn/3b/97/3b9762a3a0f6217e3fafdfac76d74c16_212x21.jpg) ![](https://img.kancloud.cn/2e/c8/2ec8b9e4fc3b4069f286d343a1f09da6_211x21.jpg) ![这里写图片描述](https://img.kancloud.cn/2e/05/2e053efc3a1fbad3ede7f0ae61da7c4d_582x167.jpg) 很明显,![](https://img.kancloud.cn/95/62/956261b578cf63688a47fb8c2d05d551_32x16.jpg)和![](https://img.kancloud.cn/d3/bb/d3bb6a313c10ef8c5eb93cfc3a873d4c_40x16.jpg)都由两项乘积构成。(忽略常数因子2)。第一项都是![](https://img.kancloud.cn/d4/51/d4519dacfc0d7e61ebb6250329173bfa_93x21.jpg),即余数residual。我们在之前介绍的GBDT算法中也介绍过余数这个概念。![](https://img.kancloud.cn/95/62/956261b578cf63688a47fb8c2d05d551_32x16.jpg)的第二项是![](https://img.kancloud.cn/18/c7/18c7cc5d9ffae47d41bca7d224e2234f_25x11.jpg),而![](https://img.kancloud.cn/d3/bb/d3bb6a313c10ef8c5eb93cfc3a873d4c_40x16.jpg)的第二项是![](https://img.kancloud.cn/dc/f3/dcf3fc63de3965b8538f8346a365df96_17x11.jpg)。二者在结构上是对称的。 计算完任意一个样本点的SGD后,就可以构建Matrix Factorization的算法流程。SGD for Matrix Factorization的算法流程如下所示: ![这里写图片描述](https://img.kancloud.cn/7e/27/7e27b164c41ed662f53a17b9cd79051f_580x270.jpg) 在实际应用中,由于SGD算法简单高效,Matrix Factorization大多采用这种算法。 介绍完SGD for Matrix Factorization之后,我们来看一个实际的应用例子。问题大致是这样的:根据现在有的样本资料,预测未来的趋势和结果。显然,这是一个与时间先后有关的预测模型。比如说一个用户三年前喜欢的电影可能现在就不喜欢了。所以在使用SGD选取样本点的时候有一个技巧,就是最后T次迭代,尽量选择时间上靠后的样本放入到SGD算法中。这样最后的模型受这些时间上靠后的样本点影响比较大,也相对来说比较准确,对未来的预测会比较准。 ![这里写图片描述](https://img.kancloud.cn/99/09/99093ed236fabd9ab5ba65e7c9a3e458_580x260.jpg) 所以,在实际应用中,我们除了使用常规的机器学习算法外,还需要根据样本数据和问题的实际情况来修改我们的算法,让模型更加切合实际,更加准确。我们要学会灵活运用各种机器学习算法,而不能只是照搬。 ### **Summary of Extraction Models** 从第12节课开始到现在,我们总共用了四节课的时间来介绍Extraction Models。虽然我们没有给出Extraction Models明确的定义,但是它主要的功能就是特征提取和特征转换,将原始数据更好地用隐藏层的一些节点表征出来,最后使用线性模型将所有节点aggregation。这种方法使我们能够更清晰地抓住数据的本质,从而建立最佳的机器学习模型。 下图所示的就是我们介绍过的所有Extraction Models,除了这四节课讲的内容之外,还包括之前介绍的Adaptive/Gradient Boosting模型。因为之前笔记中都详细介绍过,这里就不再一一总结了。 ![这里写图片描述](https://img.kancloud.cn/1e/ea/1eeaf8a8fc0e3e949c898a575997963d_584x279.jpg) 除了各种Extraction Models之外,我们这四节课还介绍了不同的Extraction Techniques。下图所示的是对应于不同的Extraction Models的Extraction Techniques。 ![这里写图片描述](https://img.kancloud.cn/b1/38/b13818dad5c0bde470eea457833ef5ed_584x278.jpg) 最后,总结一下这些Extraction Models有什么样的优点和缺点。从优点上来说: * **easy:机器自己完成特征提取,减少人类工作量** * **powerful:能够处理非常复杂的问题和特征提取** 另一方面,从缺点上来说: * **hard:通常遇到non-convex的优化问题,求解较困难,容易得到局部最优解而非全局最优解** * **overfitting:模型复杂,容易造成过拟合,需要进行正则化处理** 所以说,Extraction Models是一个非常强大的机器学习工具,但是使用的时候也要小心处理各种可能存在的问题。 ![这里写图片描述](https://img.kancloud.cn/59/f0/59f01226b17eecea5f0cec3fde8ca0a6_585x310.jpg) ### **总结** 本节课主要介绍了Matrix Factorization。从电影推荐系统模型出发,首先,我们介绍了Linear Network。它从用户ID编码后的向量中提取出有用的特征,这是典型的feature extraction。然后,我们介绍了基本的Matrix Factorization算法,即alternating least squares,不断地在用户和电影之间交互地做linear regression进行优化。为了简化计算,提高运算速度,也可以使用SGD来实现。事实证明,SGD更加高效和简单。同时,我们可以根据具体的问题和需求,对固有算法进行一些简单的调整,来获得更好的效果。最后,我们对已经介绍的所有Extraction Models做个简单的总结。Extraction Models在实际应用中是个非常强大的工具,但是也要避免出现过拟合等问题。 **_注明:_** 文章中所有的图片均来自台湾大学林轩田《机器学习技法》课程