SVD

* 2006年netflix大赛

1. 基础知识

* 符号定义

用户：｛u, v｝
物品：｛i, j, l｝
评分：$$r_{ui}$$ => 取值范围1到5
预测评分：$$\hat{r}_{ui}$$
评分发生的时间：$$t{ui}$$ =>表示$$r{ui}$$发生的时间
数据集合的稀疏程度：99%
评分存放集合：$$K={(u,v)：r_{ui}已知}$$
用户u评分的物品集合：$$R(u)$$
对物品i评分的用户集合：$$R(i)$$
用户u提高了隐式偏好信息的物品集合：$$N(u)$$

svd方法建立的模型通过拟合已经观测的数据来学习，所以需要正则化；

2. 基准预测（预处理）

基准预测是用来处理与交互数据无关的因子(偏置)
用来消除用户间的评分偏差等

* 计算步骤

总体平均评分：$$\mu$$
未知评分 $$r{ui}$$ 的基准预测：$$b{ui}$$
用户$$u$$与平均评分值的偏差：$$b_u$$
物品$$i$$与平均评分值的偏差：$$b_i$$
$$b_{ui} = \mu+b_u+b_i$$

* 例如

预测用户joe对Titannic电影的评价
设：电影平均打分$$\mu=3.7$$；用户joe挑剔，打分一般比平均分低0.3；Titannic电影口碑好，比一般要高0.5分；
Joe对Titannnic的基准预测是：3.7-0.3+0.5=3.9

* $$b_u$$和$$b_i$$的计算方法

最小二乘法，来估计 $$b_u$$和$$b_i$$

* $$b_u$$和$$b_i$$的简单方法

$$bi=\frac{\sum{u \in R(i)}(r_{ui}-\mu)}{\lambda_2+|R(i)|}$$

$$bu=\frac{\sum{i \in R(u)}(r_{ui}-\mu-b_i)}{\lambda_3+|R(u)|}$$

3.Netfilix数据集

上亿的item
48万用户
1.7万物品
1~5分（具有时间戳）
测试结果：(均方根误差：RMSE）

4. 隐式反馈

浏览历史
购买记录

5. 因子分解模型

* 因子分解模型

plsa模型

@@@Latent Semantic models for collaborative filtering

神经网络

@@@restricted boltzmann machines for collaborative filtering

@@@LDA（blei）

* svd的发展

1 源于隐语义变量LSA

@@@Indexint By Latent Semantic Analysis

2 问题：由于CF中缺失数据，简单使用已知数据，容易产生过拟合

3 简单填充的方法，会使得数据量增大，且不准确的数据也会使得数据倾斜

@@@Collaborative filtering based on iterative principal component analysis @@@Application of Dimensionally reduction in recommender system

4 采样直接利用数据建模的方法，并通过充分的正则化来避免过拟合

@@@modeling relationships at multiple scales to improve accuracy of large recommender systems @@@collaborative filtering with privacy via factor anlysis @@@netflix uodate:try this at home @@@ factorization meets the neighborhood: a multifaceted collaborative filtering model @@@improving regularized singular value decomposition for collaborative filtering @@@resticted bolzmann machines for collaborative filtering @@@ major components of the gravity recommendation algorithms

6. svd算法

svd：将用户和物品两方面的信息映射到一个纬度是f的联合隐语义空间
例如：物品是电影，分解为：喜欢/悲剧；情节数量；面向儿童的等级等，甚至是无法解释的情况

* 算法

1 物品 $$i$$ 和其相关 f 维向量 $$q_i$$

<$$q_i$$是代表了物品拥有这些隐因子的程度>

2 用户$$u$$ 和其相关 f 维向量 $$p_u$$

<$$p_u$$是代表用户对这些隐因子的喜欢程度>

3 $$q_i^T p_u$$ 点积，记录了用户和物品的交互程度，也就是用户对物品的喜欢程度

4 结合前面的基准预测，可以得到

$$\hat{r}_{ui} = \mu +b_i+b_u+q_i^Tp_u$$

=>正则化学习模型的参数，最小化评分误差

$$\min \limits{b, q, p} \sum \limits{(u,i) \in k} (r_{ui}-\mu-b_i-b_u-q_i^Tp_u)^2 + \lambda_4(b_i^2+b_u^2+||q_i||^2+||p_u||^2)$$

$$\lambda_4$$ 控制了正则化的程度，交叉验证获得

=>

最小化的求解：最小二乘或者交替最小二乘

@@@ scalable collaborative filtering with jointly derived neighborhood interpolation weights @@@modeling relationships at multiple scales to improve accuracy of large recommender systems

* netfilx上的svd

1. 给定训练样本集合$$r{ui}$$，其预测评分是$$\hat{r}{ui}$$；预测误差：

$$e{ui} = r{ui} - \hat{r}_{ui}$$

2. 梯度方向修正参数

$$bu \leftarrow b_u +\gamma(e{ui} -\lambda_4*b_u) $$

$$bi \leftarrow b_i +\gamma(e{ui} -\lambda_4*b_i) $$

$$qi \leftarrow q_i +\gamma(e{ui}p_u -\lambda_4q_i) $$

$$pu \leftarrow p_u +\gamma(e{ui}q_i -\lambda_4p_u) $$

参数：$$\gamma=0.005, \lambda_4=0.02$$

@@@ matrix factorization and neighbor based algorithms for the netflix prize problem

7. svd++

* 隐式反馈的算法

@@@ factorization meets the neighborhood: a multifaceted collaborative filtering model @@@improving regularized singular value decomposition for collaborative filtering @@@probabilistic matrix factorization

* 添加隐性反馈

$$\hat{r}{ui} = \mu +b_i+b_u+q_i^T(p_u+|R(u)|^{-\frac{1}{2}}\sum \limits{j \in R(u)} y_i)$$

其中：$$|R(u)|^{-\frac{1}{2}}\sum \limits_{j \in R(u)} y_i$$ 是补充项；

$$|R(u)|^{-\frac{1}{2}}$$ 是为了稳定方程，对其和做的规范化

1. 随机梯度法求解：

$$bu \leftarrow b_u +\gamma*(e{ui}-\lambda_5*b_u)$$
$$bi \leftarrow b_i +\gamma*(e{ui}-\lambda_5*b_i)$$
$$qi \leftarrow q_i +\gamma*(e{ui}(pu+|R(u)|^{-\frac{1}{2}}\sum \limits{j \in R(u)}y_j)-\lambda_6*q_i)$$
$$pu \leftarrow p_u +\gamma*(e{ui}q_i-\lambda_6p_u)$$
$$yi \leftarrow y_i +\gamma*(e{ui}|R(u)|^{-\frac{1}{2}}q_i-\lambda_6*y_i)$$

2. netflix数据集合30次后迭代停止

3. 引入多种隐性反馈

$$\hat{r}{ui} = \mu+b_i+b_u+q_i^T(p_u+|N^1(u)|^{-\frac{1}{2}}\sum\limits{j\in N^1(u)} yi^{(1)}+|N^2(u)|^{-\frac{1}{2}}\sum\limits{j\in N^2(u)}y_i^{(2)})$$

=>其中隐性反馈的重要性，通过算法自动学习权重

8. timesvd++

用户偏置：$$b_u(t)$$
物品偏置：$$b_i(t)$$
用户偏好：$$p_u(t)$$
物品的静态特征

* 时间变化的基准

物品的流行度或者是随时间的变化程度
人的评分标准的变化
$$t{ui}$$天内，$$用户 u 对 i 的评分$$ $$b{ui} = \mu+bu(t{ui})+bi(t{ui})$$

$$b_i$$的计算 (物品偏置)

$$bi(t) = b_i +b{i,Bin(t)}$$ ..........随时间固定变化

$$b_u$$的计算（用户偏置）

用户 $$u$$, 评分日期的均值 $$t_u$$; 设用户在t天评价了一部电影，则与该评分相关的时间偏置是

$$dev_u(t) = sign(t-t_u) * |t-t_u| ^ {\beta}$$

时间相关用户偏置

$$b^{(1)}_u(t) = b_u + \alpha_u dev_u(t)$$

netflix的用户偏置模型（ $$b_{u,t}$$反映特定天的变化）

$$p{uk} (t) = p{uk}+\alpha{uk} dev_u(t) + p{uk,t}$$

svd++

$$\hat{r}{ui} = \mu+ b{i(t{ui})} + b_u(t{ui}) + qi^T(p{u(t{ui})}) + |R(u)|^{-\frac{1}{2} }\sum \limits{j \in R(u)} y_i$$

SVD