问题

在电影销售系统中,可以得到部分人对部分电影的评分,评分属于区间[1,5],我们希望可以得到其他用户对这些电影评分的预期值,以便将用户喜欢的电影推荐给用户:

用户\电影 流浪地球 齐天大圣 白蛇 海王 我不是药神
Alice 1 2
Bob 4
Charlie 2 4 5
Daniel 3
Eric 1 3
Frank 5 2

我们可以将所有这些数据放入一个名为R的矩阵中:

R = \left( \begin{array} { l l l l l } { 1 } & \color{#e74c3c}{?} & { 2 } & \color{#e74c3c}{?} & \color{#e74c3c}{?} \\ \color{#e74c3c}{?} & \color{#e74c3c}{?} & \color{#e74c3c}{?} & \color{#e74c3c}{?} & { 4 } \\ { 2 } & \color{#e74c3c}{?} & { 4 } & { 5 } & \color{#e74c3c}{?} \\ \color{#e74c3c}{?} & \color{#e74c3c}{?} & { 3 } & \color{#e74c3c}{?} & \color{#e74c3c}{?} \\ \color{#e74c3c}{?} & { 1 } & \color{#e74c3c}{?} & { 3 } & \color{#e74c3c}{?} \\ { 5 } & \color{#e74c3c}{?} & \color{#e74c3c}{?} & \color{#e74c3c}{?} & { 2 } \end{array} \right)

矩阵R超过99%的条目缺失,而我们的目标就是预测缺失的条目,即预测矩阵中的“问号”。

评级预测有许多不同的技术,在我们的例子中,我们将分解矩阵R。该矩阵分解基本上与SVD相关联,SVD代表奇异值分解。但在深入研究SVD之前,我们需要回顾一下PCA是什么。

一点点PCA

让我们忘记推荐问题2分钟。这是一组40人的面部灰度图像,共计400张图像。这是前10个人:

image.png

没什么特别的,对吗?好吧,等一下…

每个图像大小为64 x 64像素。我们将展平每个图像(我们因此获得400个向量,每个向量具有64 x 64 = 4096个元素)。我们可以用400 x 4096矩阵表示我们的数据集:

\newcommand{\horzbar}{\Rule{2.5ex}{0.5pt}{0.1pt}}
\newcommand{\vertbar}{\Rule{0.5pt}{1pt}{2.5ex}}
X=\begin{pmatrix}
\horzbar & \text{Face 1} & \horzbar\\
\horzbar & \text{Face 2} & \horzbar\\
& \vdots &\\
\horzbar & \text{Face 400} & \horzbar\\
\end{pmatrix}

我们用PCA算法计算X的主要成分,并将每个主要成分作为一张图片展示出来:
image.png

令人毛骨悚然,对吧 😉?

实际上这些毛骨悚然的图片是原图的特征,我们可以称它们为特征脸。任何一张原始图片都可以表达成这些特征脸的线性组合,也就是说,我们可以将第一个原始照片表达为第一个特征脸的一点点,再加上一点点第二个特征脸,加上一点点的第三个等等,直到最后一个特征脸。所有其他原始面孔都是如此:它们都可以表达为每个特征脸的一点点。在数学上,我们这样写:

\begin{aligned} \text { Face } 1 & = \alpha _ { 1 } \cdot \color{#048BA8}{\text{特征脸1}}   + \alpha _ { 2 } \cdot \color{#048BA8}{\text{特征脸2}}  + \cdots + \alpha _ { 400 } \cdot \color{#048BA8}{\text{特征脸400}} \\
\text { Face } 2 & = \beta_{ 1 } \cdot \color{#048BA8}{\text{特征脸1}}  + \beta_{ 2 } \cdot \color{#048BA8}{\text{特征脸2}}  + \cdots  + \beta_{ 400 } \cdot \color{#048BA8}{\text{特征脸400}} 
\end{aligned}

隐因子

你有可能觉得特征脸很可怕,但事实上它们很典型,它们是在人脸中出现最多的特点。

PCA的目标是揭示典型的向量:每个特征脸代表数据的一个特定方面。在一个理想的世界中,第一个特征脸会代表(例如)一个典型的老年人,第二个特征脸会代表一个典型的眼镜佩戴者,而其他一些特征脸会代表一些概念,如笑脸,悲伤的样子,大鼻子,等等。通过这些概念,我们可以将面部定义为年龄,笑脸,大鼻子等的线性组合,PCA揭示的向量有的时候很难语义的解释它代表了什么。但重要的事实仍然是: 每个典型的人都捕获了数据的特定方面。我们将这些方面称为隐因子。PCA的每个主要成分都是一个隐因子。

PCA用在人脸图像矩阵上可以为我们发现特征脸,即隐因子,那么如果将它用在评级矩阵R上会发生什么呢?

将PCA用在评级矩阵上

PCA不能用在有缺失值的矩阵上,但是我们先假设评级矩阵是没有缺失值的,看看会发生什么。

关于用户的PCA

这是我们的评级矩阵,其中行是用户,列是电影:

R = \begin{pmatrix}
\horzbar & \text{Alice} & \horzbar\\
\horzbar & \text{Bob} & \horzbar\\
& \vdots &\\
\horzbar & \text{Zoe} & \horzbar\\
\end{pmatrix}

看起来很熟悉?我们现在让用户用他们的评级来表示,而不是在由像素值表示的行中有面孔。就像PCA之前给我们一些特征脸一样,它现在会帮我们找到一些典型的评分者。

我们的每个初始用户(Alice,Bob …)都可以表示为典型用户的组合。例如,爱丽丝可以被定义为一个动作迷,一点点喜剧粉丝,很多浪漫爱好者等等。至于鲍勃,他可能更热衷于动作电影:

\begin{align*}
\text{Alice} &= 10\% \color{#048BA8}{\text{动作迷}} + 10\%
\color{#048BA8}{\text{喜剧迷}} +
50\% \color{#048BA8}{\text{爱情迷}} +\cdots\\
\text{Bob} &= 50\% \color{#048BA8}{\text{动作迷}} + 30\%
\color{#048BA8}{\text{喜剧迷}} + 10\%
\color{#048BA8}{\text{爱情迷}}  +\cdots\\
\text{Zoe} &= \cdots
\end{align*}

关于电影的PCA

下面我们转置矩阵R,让每行是每个电影的评分。

R^T = \begin{pmatrix}
\horzbar & \text{流浪地球} & \horzbar\\
\horzbar & \text{白蛇} & \horzbar\\
& \vdots &\\
\horzbar & \text{我不是药神} & \horzbar\\
\end{pmatrix}

在这种情况下,这用情况PCA会发现什么隐因子呢?

\begin{align*}
\text{流浪地球} &= 60\% \color{#048BA8}{\text{动作片}} + 15\%
\color{#048BA8}{\text{喜剧片}} +
20\% \color{#048BA8}{\text{爱情片}} +\cdots\\
\text{白蛇} &= 30\% \color{#048BA8}{\text{动作片}} + 10\%
\color{#048BA8}{\text{喜剧片}} + 30\%
\color{#048BA8}{\text{爱情片}}  +\cdots\\
\text{我不是药神} &= \cdots
\end{align*}

SVD用在评级矩阵上

PCA算法其实就是对矩阵进行了SVD分解:

R=U\Sigma V^T

其中U是用户的主要特征,V是电影的主要特征,\Sigma是特征值。

为了简单起见,我们可以忽略矩阵\Sigma,它是一个对角矩阵相当对原矩阵进行了缩放,因此我们假设它已经合并到两个矩阵中了,简化后的矩阵分解为:

R = UV^T

用户u对项目i的评分r_{ui},可以表示为第u个用户的特征p_u与第i个项目的特征q_i的乘积:

\newcommand{\horzbar}{\Rule{2.5ex}{0.5pt}{0.1pt}}
\newcommand{\vertbar}{\Rule{0.5pt}{1pt}{2.5ex}}
\begin{pmatrix}
&&&&\\
&&r_{ui}&&\\
&&&&\\
\end{pmatrix}
=
\begin{pmatrix}
&&&&\\
&\horzbar&p_u& \horzbar&\\
&&&&\\
\end{pmatrix}
\begin{pmatrix}
&&\vertbar&&\\
&&q_i&&\\
&&\vertbar&&\\
\end{pmatrix}

即:

r_{ui} = p_u \cdot q_i

还记得我们是如何描述我们的用户和电影的么?

\begin{array}{ll}
\text{Alice} &= 10\% \color{#048BA8}{\text{动作迷}} + 10\%
\color{#048BA8}{\text{喜剧迷}} +
50\% \color{#048BA8}{\text{爱情迷}} +\cdots\\
\text{Bob} &= 50\% \color{#048BA8}{\text{动作迷}} + 30\%
\color{#048BA8}{\text{喜剧迷}} + 10\%
\color{#048BA8}{\text{爱情迷}}  +\cdots\\
\text{流浪地球} &= 60\% \color{#048BA8}{\text{动作片}} + 15\%
\color{#048BA8}{\text{喜剧片}} +
20\% \color{#048BA8}{\text{爱情片}} +\cdots\\
\text{白蛇} &= 30\% \color{#048BA8}{\text{动作片}} + 10\%
\color{#048BA8}{\text{喜剧片}} + 30\%
\color{#048BA8}{\text{爱情片}}  +\cdots\\
\end{array}

向量p_uq_i完全对应用户特征与电影特征的系数:

\begin{align*}
p_\text{Alice} &= (10\%,~~ 10\%,~~ 50\%,~~ \cdots)\\
p_\text{Bob} &= (50\%,~~ 30\%,~~ 10\%,~~ \cdots)\\
q_\text{流浪地球} &= (60\%,~~ 15\%,~~ 20\%,~~ \cdots )\\
q_\text{白蛇} &= (30\%,~~ 10\%,~~30\%,~~ \cdots )
\end{align*}

评分r_{ui}是综合用户的特征p_u和电影的特征q_i的结果。这完全合理,用户特征的不同或是电影特征的不同都会影响评分。

当我们对评分矩阵进行分解,会提取出用户和电影特征,反过来我们又可以根据用户和电影的特征来计算评分。

推荐系统中的SVD

以上我们对评级矩阵的SVD分解是假设矩阵是缺失值的,遗憾的是评级矩阵大部分值都是缺失的。

R = \left( \begin{array} { l l l l l } { 1 } & \color{#e74c3c}{?} & { 2 } & \color{#e74c3c}{?} & \color{#e74c3c}{?} \\ \color{#e74c3c}{?} & \color{#e74c3c}{?} & \color{#e74c3c}{?} & \color{#e74c3c}{?} & { 4 } \\ { 2 } & \color{#e74c3c}{?} & { 4 } & { 5 } & \color{#e74c3c}{?} \\ \color{#e74c3c}{?} & \color{#e74c3c}{?} & { 3 } & \color{#e74c3c}{?} & \color{#e74c3c}{?} \\ \color{#e74c3c}{?} & { 1 } & \color{#e74c3c}{?} & { 3 } & \color{#e74c3c}{?} \\ { 5 } & \color{#e74c3c}{?} & \color{#e74c3c}{?} & \color{#e74c3c}{?} & { 2 } \end{array} \right)

如果R没有缺失值,有很成熟的方法将其进行矩阵分解,但R有缺失值我们就要另想办法。

一种可行的方法是通过解决下列优化问题来解决

f(p_*, q_*) =\sum_{r_{ui} \in R} (r_{ui} - p_u \cdot q_i)^2

优化过程对于缺失的评分,只需将其忽略就可以了。

这个优化问题并不是凸的。也就是说优化起来可能比较困难,并且可能不止有一个最优解。但是我们仍然有很多方案可以解决这个优化问题,比如说随机梯度下降算法。

\begin{array}{l} \hline
\hline
1: 随机初始化p,q。\\
2: 对于k次迭代循环以下过程\\
\qquad 	1: 计算p和q的梯度 \\
\qquad \qquad \frac{\partial f_{ui}}{\partial p_u} = \frac{\partial}{\partial p_u}  (r_{ui} - p_u \cdot
q_i)^2 = - 2 q_i (r_{ui} - p_u \cdot q_i)\\
\qquad \qquad \frac{\partial f_{ui}}{\partial q_i} = \frac{\partial}{\partial q_i}  (r_{ui} - p_u \cdot
q_i)^2 = - 2 p_u (r_{ui} - p_u \cdot q_i)\\
\qquad  2:更新p和q \\
\qquad \qquad p_u \leftarrow p_u + \alpha \cdot q_i (r_{ui} - p_u \cdot q_i)\\
\qquad \qquad q_i \leftarrow q_i + \alpha \cdot  p_u (r_{ui} - p_u \cdot q_i)
\\ \hline \end{array}

一旦通过迭代得到了p和q,我们就可以通过下式计算评分:

r_{ui} = p_u \cdot q_i

如何来衡量模型的好坏?可以使用均方误差:

\text{RMSE} = \sqrt{\sum_{u,i} (\hat{r}_{ui} - r_{ui})^2}.

最后我们需要考虑一下p_uq_i的长度,我们真的需要所有的特征么?不是的,这和使用PCA进行降维很类似,仅仅需要少量的主要特征就可以将大多数的信息描绘出来。通常情况下我们可以设置p和q的长度为10。


参考:
http://nicolas-hug.com/blog/
https://www.cnblogs.com/pinard/p/6351319.html

posted @ 2019-03-03 08:58:58
评论加载中...

发表评论