机器学习技法笔记 – Matrix Factorization(矩阵分解)

Linear Network Hypothesis

一言以概之,Matrix Factorization是一种提取数据集隐藏特征的技术。

对于一些已有特征是类别(Categorical)的机器学习问题,我们通常需要对这些特征进行编码。

例如我们有关于用户信息的数据集,其输入为例如ID、血型、生日、爱好,输出则是某一个用户对多部电影的评分。

我们希望预测:对于一个数据集样本外的用户,他可能对现有的多部电影如何评分。

我们将以一个\(N-\tilde{d}-M\)的网络来说明Matrix Factorization是如何工作的:

可以看到,该网络具有一个输入层,一个隐含层,一个输出层。

我们用\(V^T\)与\(W\)表示每层网络的权重,在本问题中,输入X是一个\(N\)维列向量(\(N×1\)),因为该网络是一个\(N-\tilde{d}-M\)的网络,易知\(V^T\)是维度为\(\tilde{d}×N\),而\(W\)的维度为\(M×\tilde{d}\)

则输出层具有以下形式:

$$h(x) = W^TVx$$

为了简化问题,我们假设在本问题中只有一个特征(性别)需要被编码,那么对于输入\(x\)来说,这个列向量矩阵是非常稀疏的,它可能具有以下形式:

$$x = \begin{bmatrix} 0 & 1 & 0 & 0 \end{bmatrix}^T$$

试想,这样一个稀疏向量对矩阵\(V\)进行线性组合,结果显而易见地将是仅有在向量\(x\)中不为零的列\(n\)将会在矩阵\(V\)中保留下来,所以我们的\(h(x)\)可以进行如下简化:

$$h(x) = W^Tv_{n}$$

其中,\(v_n\)是矩阵\(V\)的第\(n\)列。

Basic Matrix Factorization

对于Matrix Factorization,我们希望:

$$y ≈ h(x) = W^Tv_{n} = W^TVx$$

在本问题中,输出\(y\)是一个\(M×1\)的列向量,代表了用户对每部电影的评分。

同时我们知道\(v_{n}\)是一个\(\tilde{d}×1\)的列向量,而\(W^T\)是\(M×\tilde{d}\)的矩阵,那么对于某一部电影的评分则有以下形式:

$$y_{m} = w_{m}^Tv_{n}$$

其中,\(w_m^T\)是矩阵\(W\)的第\(m\)行。

而\(W^TV\)与\(w_{m}^Tv_{n}\)的关系则有下图:

我们认为,\(W\)与\(v_n\)分别描述了电影的特征与用户的特征。

一个直观的结论即是,当\(v_n\)在对\(W\)做线性组合时,如果在用户特征矩阵(列向量)\(v_n\)与在电影特征矩阵\(W\)的第\(m\)行的内积,即是用户\(n\)对电影\(m\)的评分。

这个分数直观的反映了用户的某些特征对电影的某些特征的“接近程度”。

所以,Matrix Factorization的学习过程即最优化\(w_m^T\)与\(v_n\)的过程。

定义Matrix Factorization的Error Function如下:

$$E_{in}({w_m}, {v_n}) = \sum_{m = 1}^{M} \left( \sum\left( y_{nm} – w_m^T v_n \right)^2\right)$$

问题转化为了一个具有两个变量的最优化问题。

与上节在RBF Network中介绍的k-Means的最优化问题相同,我们首先为\(W\)与\(V\)设置初始值,然后固定一个优化另一个。

每一个优化过程都是一个Linear Regression的过程,最终他们将收敛于\(E_{in} = 0\)

这种算法被称为Alternating Least Squares,其具体流程如下:

我们可以发现,Matrix Factorization与Linear AutoEncoder具有相似和不同之处:

相对于Linear AutoEncoder而言,其最优解是一个全局的最优解,而对于Matrix Factorization而言,其最优解是一个局部的最优解。

它们都是一种网络的模型,用于提取数据集的隐藏特征。

Stochastic Gradient Descent

除了Alternating Least Squares,SGD同样可以用于求解Matrix Factorization的局部最优解。

同时SGD可能在一些情况相对于Alternating Least Squares而言具有更好的性能,同时由于实现简单,在实际问题在更常使用。

对于原Error Function:

$$err(v_n, w_m) = \left( y_{nm} – w_m^T v_n \right)^2$$

分别对\(v_n\)与\(w_m\)求其梯度:

$$\nabla_{v_n}\text{err}(n, m) = – 2(y_{nm} – w_m^T v_n)w_m\\ \nabla_{w_m}\text{err}(n, m) = – 2(y_{nm} – w_m^T v_n)v_n$$

我们可以发现\(w_m\)的梯度值正比于\(v_n\),反之亦然。

我们可以通过这一性质简化SGD的过程,我们通过计算下式:

$$\tilde{y}_{nm} = (y_{nm} – w^T_{m}v_{n})$$

然后通过下式更新变量:

$$v_n^{new} ← v_n^{old} + \eta ·  \tilde{y}_{nm} w_{m}^{old} \\ w_m^{new} ← w_m^{old} + \eta ·  \tilde{y}_{nm} v_{n}^{old}$$

从而通过SGD来做Matrix Factorization的训练过程。

Summary of Extraction Models

某种意义上,Feature Transform(特征转换)即是一种Extraction Models,截至目前,我们已经介绍了多种Aggregation Model,每种Aggregation Model都具有自己的Extraction Models,下图是一个简略的总结:

我们可以看到,各个Aggregation Model用于提取数据模型特征的方法不尽相同,具体的每一个方法,我们在前几章均已经做了详细的介绍。

最后我们将Neural Network、RBF Network、Matrix Factorization做一个简单的整理:

对于这三种非线性的模型,他们的优点是明显的,即他们足够强大,如果数据量足够大、隐含层足够多,他们的泛化能力将会非常强大。

但是缺点也显而易见,即这些模型面对的问题本身可能是非凸的,即可能本身没有一个最优解,同时我们需要时刻注意Regularization与Validation,以避免Overfitting的发生。

以上是对Matrix Factorization在台湾大学机器学习技法课程的笔记总结。

至此,所有课程中相关的机器学习技法已经全部介绍完毕了。

在下一篇文章中,我们将会对机器学习技法做最后的总结。