Dimensionality Reduction 降维

若原特征空间是D维的,现希望降至d维的。降维的概念相信大家都已经有了解了，就不介绍了，首先从为什么需要降维理解其必要性，然后讲解具体实现。

在这里先简单介绍下矩阵的秩

矩阵的秩

把矩阵看成线性映射那么秩就是象空间的的维数。通俗一点说，如果把矩阵看成一个个行向量或者列向量，秩就是这些行向量或者列向量的秩，也就是极大无关组中所含向量的个数。

从例子中我们可以看到矩阵A的秩为2，因为第三行向量可以通过第二行和第一行线性表示，因此，我们可以将矩阵A中的维数降到2维就可以表示了。这里可能说的还不够明确，后面的SVD奇异值分解中将能帮助我们深刻理解矩阵的秩的作用。

Singular-Value Decomposition 奇异值分解

这部分我之前转载过一篇文章，写得蛮好，附链接http://blog.csdn.net/sherrylml/article/details/43052325原文链接在文章开头。

图示如下，可以看到通过存储矩阵U， ∑ $\sum$和 VT $V^T$来表示矩阵A可以大大缩减存储空间

CUR Decomposition

前面说到的SVD分解虽然可以提供最小误差的压缩，但是还是存在两个问题。一个是计算比较耗时，另一个是分解后的矩阵密度很高浪费存储空间。而CUR分解则是另外一种降维方法，可以减少SVD的这些缺点。
CUR分解是将矩阵A压缩为C，U，R三个矩阵的乘积，使得 ||A−C⋅U⋅R||F $||A-C\cdot U\cdot R||_F$尽可能小。其中 ||X||F=∑ijX2ij−−−−−−√ $||X||_F = \sqrt{\sum_{ij}X_{ij}^2}$
C 矩阵是从A的列中挑选的，所以简称C（columns），
而R矩阵是从A的行中挑选的所以简称R，
矩阵U是由C和R的交集求伪逆得到。
很明显从A中挑选行或列操作起来是很快的，因此整个计算时间将会加快很多。
下面我们看看CUR分解相比SVD好在哪里以及它为何可行。

假定矩阵 Ak $A_k$是矩阵A的最好（误差最小）分解，即SVD分解取k为矩阵A的秩。
由Mahoney&Drineas提出的理论证明：
CUR分解在 O(m⋅n) $O(m\cdot n)$时间内可以有 1−δ的概率 $1-\delta的概率$达到误差接近于SVD分解的误差结果，即
||A−CUR||F≤||A−Ak||F+ε||A||F $||A-CUR||_F\le||A-A_k||_F+\varepsilon||A||_F$
其中C选择A中的 O(klog(1/δ)/ε2)列，R选择A中的O(k2log3(1/δ)/ε6)行 $O(k log(1/\delta)/\varepsilon^2)列，R选择A中的O(k^2{log}^3(1/\delta)/\varepsilon^6)行$。在实际应用中通常取4k行4k列。

因此，CUR分解可以在相对SVD短很多的时间内将矩阵分解，且误差只比SVD大一点。下面我们就来具体讲解CUR分解的实现。

CUR Algorithm

首先，我们看Ｃ和Ｒ矩阵是如何从Ａ中挑选的。由于两者类似，下面仅说明矩阵Ｃ。
列向量采样

Ｒ矩阵的获取同理，取 AT $A^T$按上面操作可得。

计算矩阵U

1. 取C矩阵和R矩阵的“交集”W
2. U为W的伪逆

优缺点

Latent Factor Recommender System

Latent Factor Model

前面我们讲到的协同过滤算法使用的是local effect，即考虑的是相似用户对商品的评价或者是用户对相似商品的评价

下面我们结合Global effect，即所有用户的评价情况来调整协同过滤算法：

这种方法在实际应用中表现已经很好了，虽然有上图中的三个问题残留。

Latent-Factor Recommender System

其实推荐系统也可以看做是对商品的评分问题，只是我们要的是评分高的物品。因此，推荐系统也是一种最优化问题，最优化评分结果的误差。因此我们用RMSE来评估推荐系统的好坏。
We want our systerm to predict well the hidden(known) ratings.

Finding Latent Factor

Dealing with Missing Entries
根据前面的介绍我们知道这个将原来的矩阵用P，Q表示就是一个压缩过程，从中找到Latent factor，而这个P，Q矩阵的获取根据的就是最小化SSE来得到的，即：

那么我们如何最小化这个误差函数呢？用的是梯度下降法
我们希望通过尽可能大的k(factor number)来获取原矩阵中尽可能多的信息从而对于训练数据有尽可能有的误差，但是这样会导致测试数据上的SSE增大（k>2)。即会导致过拟合问题。
为了解决过拟合问题，引入regularization 正则化。

这样一来就能平缓这个Model的performance和它的complexity。
然后我们用梯度下降法来处理正则化后的表达式，从而找到合适的Ｐ，Ｑ矩阵

Extending Latent Factor Model to Include Global Effects

Fitting the New Model