Machine Learning Techniques Lecture 15: Matrix Factorization | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 15: Matrix Factorization


 
 

内容:

Matrix Factorization(矩阵分解)模型,一开始先讲linear network里面通过对ID这样的特征编码来萃取特征,然后讲基本的 matrix factirization演算法,要做的事情就是在两个特征之间交互的 做 linear regression,同时你也可以用SGD来做,这是一个有效率的方法,而且可以根据应用做适当的调整,最后总结了一下 extraction model。

 
 


 
 

上一讲:

Raidal Basis Function Network,就是把原来的原始数据通过k-means算法来找出代表,通过使用RBF函数来替代,然后整个方法就可以转化成linear aggregation问题来求解了。

 
 

这里:

Matrix Factorization

 
 


 
 

我们首先来回到机器学习基石课程最早讲过的,机器学习的目标就是从资料里面学习的到技能。例如从很多使用者那里收集的到了很多喜欢的电影的数据,每一笔资料就是某个使用者给某一部电影的分数,我们目标是得到那个使用者喜不喜欢还没上映的那部电影。棕色框就是一个实际问题的例子。

 
 

在上面的例子里面,x是一个抽象的特征,是一个编号。这样的数据怎么去做机器学习,就是这里要讲解的问题。

 
 


 
 

X 是抽象的,就是数值上没有意义,只是用来分类别的数据,比如ID,血型,程序语言。

 
 

但是我们目前学过的ML Model都作用于有数值特征的数据,例如线性模型,算分数的方式的前提就是数值有举例意义,NN等基于线性模型的方法也有这个要求。只有很少数的机器学习方法可以直接处理类别特征数据,比如讲过的 decision tree。

 
 

所以如果我们要对类别特征做机器学习,那么第一步就是将类别特征数据转换成数字数据特征,这个过程叫做encoding。

 
 

一种简单的encoding方法叫做 Binary Vector Encoding。比如血型有四种,用一个四维的向量来表示,每一种可能性占一行,1表示是的。

 
 


 
 

原来的数据每一条,都是一个( 类别 x_n, 分数 y_n)的向量表示,可以把数据整合一下,把所有相同的x_n数据合成一个,就有(类别x_n,分数向量(分数向量里面存在不知道的数据用?表示))。

 
 

我们怎么样从这么复杂的抽象数据里面做特征萃取呢,NN是典型的特征转换模型,NN里面每一层都可以看作是特征的萃取。例如电影偏好的问题,可以把NN里面的x看作是用户,y看作是电影,整个学习参数的过程就是特种萃取。N-d~-M NNet,N表示的是使用者的个数,M表示的是电影的个数,d~就是中间节点的个数。

 
 

tanh在这里不是必要的,因为这里的输入向量的特征是,里面只有一个1,其他都是0,也就是进出都是sparse的,简单,不需要转换了,因此可以使用这个特征来简化模型,也就是linear Network。

 
 


 
 

因此我们考虑 Linear Network,先来命名如上面所述,这样以后就有 h(x) = W^T * V * X。因为X只有n列是1,其他都是0,因此我们可以用 V_n 来表示 V * X 的结果,这样就有了上面表示的 hypothesis 结果。

 
 


 
 

练习

 
 


 
 

上面我们讲到了 Linear Network Model,在电影这个应用里面 V * x 的意义是对所有的电影序列 x 做了转换,然后再跟 w 做线性组合就是结果。或者对于某一部电影m来讲,关心的就只是 h_m(x) ,对应的x的那一行只有m列是1,其他都是0,这就是一个转换过了以后的线性模型。

 
 

我们想要的输出是 r_nm = W_m(权重)* V_n(n个使用者),这个结果要和我们已知的一些数据 y_n 接近,那么对于总体来说就可以写成一个Ein最小化的公式,如上面所示, r_nm – W_m^T * V_n 表示的就是已知的使用者评价和模型输出结果的误差,灰色的部分不影响最佳化结果。Ein 最小化,表示的是这个网路我们可以学到的是,一个是怎么做转换,一个是第二层的权重是多少。

 
 


 
 

矩阵化:

 
 

R每一行代表一个使用者,每一列代表一部电影,格子里面就是评分;原来的目标求解公示就可以表示成矩阵形式,如上面所示。如果我们可以把不健全的R分解成V,W,那我们就得到了使用者的特征,得到了每一部电影怎么样对这个特征做线性组合来做最佳化预测。我们从已经知道的评分出发,想办法去反推到底对于使用者来说哪些特征是重要的,对于电影来说他有那些元素,也就是说对于R的每一格都有这样的物理上的意思。举例说就是这个用户喜欢喜剧片,这部电影是喜剧片,那么用户喜欢,反之侧不然。

 
 

矩阵分解这样的方法常常被用来把抽象的特征转化成真正有意义可以进一步处理的特征。

 
 


 
 

我们怎么来做学习呢?

 
 

上面已经得到了一个最佳化问题,变数是W,V,也就是说有两个Sum动作。这个问题有两组变数,因此可以考虑 alternating minimization方法,k-means里面讲过。首先固定V,最佳化W,就是一堆的线性模型,对于每一部电影就是一个线性模型,就是做linear regression解决问题。然后固定W,最佳化V,由于上面的问题WV的角色可以看作是对称的,因此也是一个linear regression求解。这个算法叫做 alternating least squares algorithm。

 
 


 
 

alternating least squares algorithm

  1. 初始化随机的设定值,
  2. 固定V求解W,固定W求解V,
  3. 交叉迭代第二步优化直到Converge,而且一定会收敛。

 
 


 
 

这两者都存在着矩阵分解的概念,来做比较。

 
 

Linear Autoencoder:X = W(W^T * X)

第一层的W做编码,第二层的W做解码,出发点是特别的线性NN,可以看作是分解成一号矩阵W,二号矩阵(W^T * X);错误衡量用的是平方错误,但是矩阵中每一格都知道,因此算所有格子;解是全局最优,就是eigenvector;适合用来做资料的降维。

 
 

Matrix Factorization:R = V^T * W

也是一个线性NN,分解成一号矩阵V,二号矩阵W;错误衡量用的是平方错误,但是矩阵中有很多不知道,因此只算知道的;解是局部最优;适合萃取特征。

 
 

Linear autoencoder 可以看作是 matrix factorization 的特例。

 
 


 
 

练习

 
 


 
 

我们上面讲了 alternating least squares algorithm 来解决 Matrix Factorization 的问题,这里带大家来看能不能使用 Stochastic gradient descent (随机的从资料里面选取一笔资料,在这比资料有关的error衡量上面去算梯度,做梯度下降,好处是每一轮只涉及到一个点,计算很有效率,程序实现容易,可以使用不同的错误衡量方式)来求解 Matrix Factorization。

 
 


 
 

首先写出错误衡量公式,用的是平方错误。然后对模型里面所有的变数做偏微分,同样因为W,V是只有一行有意义,对于每一个nm对来说,所以就有蓝色的部分结果。

 
 

我们来看 Gradient 其包含两项,第一项是 residual(余数,我们的目标和现实的差距),第二项是 the other feature vector(另外一个特征向量)。

 
 


 
 

由上面就可以得到用 SGD 做矩阵分解的方法:

一开始的WV是随机的设置一些值,然后

  1. 随机选择一个点
  2. 计算余数项
  3. 更新SGD,公式如上面所示

 
 

非常的有效率,非常的常用。

 
 


 
 

最后给一个例子。

 
 

训练的资料比测试的资料获得的时间是比较早的,也就是有时间上的分布关系。这时候需要注重时间比较晚的资料。

 
 


 
 

练习

 
 


 
 

到此的四讲里面我们讲的是 Extraction Model,就是把资料的转换纳入到机器学习的过程中来,通过资料的转换来学习到隐藏的特征,再使用线性模型来求解的完整过程。

 
 

NN/DL :前面所有的层都是在做特征转换,最后一层就是线性模型

RBF Network:最后是一个线性模型,前面求RBF的中心就是转换后的特征

Matrix Factorization:同样最后一层是线性模型W,前面在做特征转换V,但是这里面WV是对称的,可以互换。

Adaptive/Gradient Boosting:其中的hypothesis可以看作是资料转换,最后一层就是带权重的线性转换。

K Nearest Neighbor:可以看作是用最近的中心点当作是原来的特征,就是特征转换,最后也是一个线性模型得结果。

 
 


 
 

除了模型之外,我们还通过模型来交给大家一些技巧:怎么从你的资料里面萃取出有用的特征。

 
 

NN/DL :SGD,透过 backprop 来很有效率的算出梯度的值;autoencoder,通过非监督式的方法让整个方法在一个比较好的权重开始。

RBF Network:介绍了 k-means clustering,非监督式的方式来获得分群的资料

Matrix Factorization:SGD,alternating leastQSR 交互的做线性回归

Adaptive/Gradient Boosting:functional gradient descent 来推导出怎么萃取g。

K Nearest Neighbor:lazy learning 方法,就是训练的时候不做什么事情,而是测试的时候做事情。

 
 


 
 

Extraction Models

 
 

好处:对人来说容易使用,不用拍脑袋设计特征;非常的powerful;

坏处:不是凸函数,容易得到局部最优解而不是全局最优解;容易overfitting,

 
 


 
 

练习

 
 


 
 

总结:

Matrix Factorization(矩阵分解)模型,一开始先讲linear network里面通过对ID这样的特征编码来萃取特征,然后讲基本的 matrix factirization演算法,要做的事情就是在两个特征之间交互的 做 linear regression,同时你也可以用SGD来做,这是一个有效率的方法,而且可以根据应用做适当的调整,最后总结了一下 extraction model。

 
 

下一讲:

给大家一些机器学习技法方面的总结


One Comment

Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags