LibRec学习笔记（二）：SVD++算法
上一篇我们具体介绍了BiasedMF算法在LibRec库中的实现，实际上是为了本篇介绍SVD++算法实现做铺垫，在代码中我们也可以看到，SVDPlusPlusRecommender类继承了BiasedMFRecommender类，本篇主要也是从三个方面展开，分别是预测公式、损失函数公式和更新公式。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141package net.librec.recommender.cf.rating;
import java.util.Iterator;
import net.librec.annotation.ModelData;
import net.librec.common.LibrecException;
import net.librec.math.structure.DenseMatrix;
import net.librec.math.structure.DenseVector;
import net.librec.math.structure.SequentialSparseVector;
import net.librec.math.structure.VectorBasedDenseVector;
import net.librec.math.structure.Vector.VectorEntry;
public class SVDPlusPlusRecommender extends BiasedMFRecommender {
protected DenseMatrix impItemFactors;
private double regImpItem;
private DenseVector factorVector;
public SVDPlusPlusRecommender() {
}
protected void setup() throws LibrecException {
super.setup();
this.regImpItem = this.conf.getDouble("rec.impItem.regularization", 0.015D);
// 物品隐因子偏置向量 对应公式中的y
this.impItemFactors = new DenseMatrix(this.numItems, this.numFactors);
// 物品隐因子偏置向量初始化
this.impItemFactors.init((double)this.initMean, (double)this.initStd);
this.factorVector = new VectorBasedDenseVector(this.numFactors);
}
protected void trainModel() throws LibrecException {
for(int iterationStep = 1; iterationStep <= this.numIterations; ++iterationStep) {
this.loss = 0.0D;
for(int userIndex = 0; userIndex < this.numUsers; ++userIndex) {
SequentialSparseVector userVector = this.trainMatrix.row(userIndex);
if (userVector.size() != 0) {
double[] steps = new double[this.numFactors];
this.factorVector.assign((indexx, value) -> {
return 0.0D;
});
Iterator var5 = userVector.iterator();
while(var5.hasNext()) {
VectorEntry vectorEntry = (VectorEntry)var5.next();
this.factorVector.assign((indexx, value) -> {
return this.impItemFactors.row(vectorEntry.index()).get(indexx) + value;
});
}
double scale = Math.pow((double)userVector.getNumEntries(), -0.5D);
this.factorVector.assign((indexx, value) -> {
return value * scale;
});
Iterator var7 = userVector.iterator();
double factor;
while(var7.hasNext()) {
VectorEntry vectorEntry = (VectorEntry)var7.next();
int itemIndex = vectorEntry.index();
double error = vectorEntry.get() - this.predict(userIndex, itemIndex, this.factorVector);
this.loss += error * error;
factor = this.userBiases.get(userIndex);
this.userBiases.plus(userIndex, (double)this.learnRate * (error - this.regBias * factor));
this.loss += this.regBias * factor * factor;
double itemBias = this.itemBiases.get(itemIndex);
this.itemBiases.plus(itemIndex, (double)this.learnRate * (error - this.regBias * itemBias));
this.loss += this.regBias * itemBias * itemBias;
for(int factorIndex = 0; factorIndex < this.numFactors; ++factorIndex) {
double userFactor = this.userFactors.get(userIndex, factorIndex);
double itemFactor = this.itemFactors.get(itemIndex, factorIndex);
this.userFactors.plus(userIndex, factorIndex, (double)this.learnRate * (error * itemFactor - (double)this.regUser * userFactor));
this.itemFactors.plus(itemIndex, factorIndex, (double)this.learnRate * (error * (userFactor + this.factorVector.get(factorIndex)) - (double)this.regItem * itemFactor));
this.loss += (double)this.regUser * userFactor * userFactor + (double)this.regItem * itemFactor * itemFactor;
steps[factorIndex] += error * itemFactor * scale;
}
}
int size = userVector.getNumEntries();
Iterator var23 = userVector.iterator();
while(var23.hasNext()) {
VectorEntry vectorEntry = (VectorEntry)var23.next();
int index = vectorEntry.index();
for(int factorIndex = 0; factorIndex < this.numFactors; ++factorIndex) {
factor = this.impItemFactors.get(index, factorIndex);
this.impItemFactors.plus(index, factorIndex, (double)this.learnRate * (steps[factorIndex] - this.regImpItem * factor * (double)size));
this.loss += this.regImpItem * factor * factor * (double)size;
}
}
}
}
this.loss *= 0.5D;
if (this.isConverged(iterationStep) && this.earlyStop) {
break;
}
this.updateLRate(iterationStep);
}
}
private double predict(int userIndex, int itemIndex, DenseVector factorVector) {
double value = this.userBiases.get(userIndex) + this.itemBiases.get(itemIndex) + this.globalMean;
DenseVector userFactorVector = this.userFactors.row(userIndex);
DenseVector itemFactorVector = this.itemFactors.row(itemIndex);
for(int index = 0; index < this.numFactors; ++index) {
value += (factorVector.get(index) + userFactorVector.get(index)) * itemFactorVector.get(index);
}
return value;
}
protected double predict(int userIndex, int itemIndex) {
SequentialSparseVector userVector = this.trainMatrix.row(userIndex);
this.factorVector.assign((index, value) -> {
return 0.0D;
});
Iterator var4 = userVector.iterator();
while(var4.hasNext()) {
VectorEntry vectorEntry = (VectorEntry)var4.next();
this.factorVector.assign((index, value) -> {
return this.impItemFactors.row(vectorEntry.index()).get(index) + value;
});
}
double scale = Math.sqrt((double)userVector.getNumEntries());
if (scale > 0.0D) {
this.factorVector.assign((index, value) -> {
return value / scale;
});
}
return this.predict(userIndex, itemIndex, this.factorVector);
}
}
预测公式
\(\hat{r}_{u i}=\mu+b_{i}+b_{u}+q_{i}^{T}\left(p_{u}+|N(u)|^{-\frac{1}{2}} \sum_{j \in N(u)} y_{j}\right)\)
首先我们需要明确预测公式各部分的含义：
\(\mu\)：训练集中所有评分的均值，表示训练数据的总体评分情况，对于固定的数据集是一个常数，在代码中使用
this.globalMean表示。\(b_{u}\)：用户偏置，独立于物品特征的因素，表示某一特定用户的打分习惯，例如，对于批判型用户倾向于打低分，乐观型用户倾向于打高分，在代码中使用
this.userBiases.get(userIndex)表示，需要注意的是，特定用户的用户偏置需要使用用户ID来进行索引。\(b_{i}\)：物品偏置，独立于用户兴趣的因素，表示某一特定物品得到的打分情况，例如，好的电影获得的总体评分偏高，而坏的电影获得的评分偏低，在代码中使用
this.itemBiases.get(itemIndex)表示，需要注意的是，特定物品的物品偏置需要使用物品ID来进行索引。\(q_{i}\)：物品隐向量，对用户物品评分矩阵分解后得到，在代码中使用
itemFactorVector.get(index)表示，同样地，需要使用index来进行索引。\(p_{u}\)：用户隐向量，对用户物品评分矩阵分解后得到，在代码中使用
userFactorVector.get(index)表示，同样地，需要使用index来进行索引。\(|N(u)|\)：用户\(u\)在评分过的历史物品的数量，即在隐式反馈特征中有行为的个数。
\(y_{j}\)：用户\(u\)对于交互过的物品\(j\)的个人喜好偏置，在代码中，\(|N(u)|^{-\frac{1}{2}} \sum_{j \in N(u)} y_{j}\)整体使用
factorVector.get(index)表示。
SVD++中加入了隐式反馈信息，除了假设评分矩阵中的物品有一个隐因子向量外，用户有过交互行为的物品集合也都有一个隐因子向量，维度相同，将用户操作过的物品隐因子向量加起来可以用来表示用户的兴趣爱好。
以下我们可以来看一下预测函数的代码，首先展示\(\sum_{j \in N(u)} y_{j}\)这一部分：
1 | SequentialSparseVector userVector = this.trainMatrix.row(userIndex); |
这块的代码非常的简洁，但不是很好理解，这个Lambda表达式一上来就有一种云里雾里的感觉，我们首先需要明确Lambda表达式的作用，有一个例子可以帮助我们理解，
1 | (x, y) -> x - y; |
在以上的匿名方法中，接收了x和y两个参数，并返回它们的差值。与以上案例不同的是，程序中的Lambda表达式重写了接口类的方法，我们可以首先来观察一下接口类VectorAssigner中被重写的getValue()方法，代码如下所示，
1 | public interface VectorAssigner { |
可以看到，接口类的方法传入两个参数，一个是int类型，另外一个是double类型，这和Lambda表达式中传入的index和value正好对应。明确了以上之后，我们还需要搞清楚assign()方法的使用，在DenseVector中assign()方法如下所示，
1 | public DenseVector assign(VectorAssigner vectorAssigner) { |
在assign()方法中循环调用了set()方法对factorVector进行赋值，在初始的时候对其进行全0赋值，因为重写的getValue()方法return 0。
再来看以下一部分代码对\(\sum_{j \in N(u)} y_{j}\)进行计算，代码如下所示，
1 | while(var4.hasNext()) { |
首先我们需要明确迭代器是userVector的迭代器，也就是对用户交互过的每一个物品进行遍历，每一次调用assign()方法都遍历所有的index，这里的index可以理解为隐因子向量的维度索引，每一个用户交互过的物品都对应一个隐因子向量，迭代器将所有用户交互过的物品的隐因子向量进行相加，求得\(\sum_{j \in N(u)} y_{j}\)。
与公式进行比对，我们发现还缺少一部分\(|N(u)|^{-\frac{1}{2}}\)，公式的这一部分是为了消除不同\(|N(u)|\)个数引起的差异，如果使用\(|N(u)|\)，则用户交互过的物品个数也会对最后的效果产生影响，而这显然是不利的，我们再来看这一部分的代码实现，
1 | double scale = Math.sqrt((double)userVector.getNumEntries()); |
可以直接通过调用userVector.getNumEntries()方法来获得当前用户交互过的物品数量，开平方后得到缩放比例，再将隐因子向量的和除以缩放比例最终得到\(|N(u)|^{-\frac{1}{2}} \sum_{j \in N(u)} y_{j}\)这一部分的值。
预测函数到这里并没有结束，程序中将预测函数的上一部分进行讲解的代码进行了封装，然后在总的预测函数中进行调用，
1 | private double predict(int userIndex, int itemIndex, DenseVector factorVector) { |
value在初始化时就被赋上\(\mu+b_{i}+b_{u}\)的值，在这里主要是关注index的循环，index在这里指的是隐因子向量的维度索引，factorVector表示当前用户交互过的物品隐因子偏置向量，能够表现出用户对于交互过的一些物品的隐因子的倾向，userFactorVector表示用户隐因子向量，itemFactorVector表示物品隐因子向量，这些隐因子向量的维度是相同的，所以可以进行相同的循环操作，最后返回的值即预测值，至此预测函数的部分就结束了。
损失函数公式
\(\begin{aligned} \min _{b_{i}, b_{w}, q_{i}, p_{u}} &\sum_{(u, i) \in K}\left(r_{u i}-\mu-b_{u}-b_{i}-q_{i}^{T}\left(p_{u}+|N(u)|^{-\frac{1}{2}} \sum_{j \in N(u)} y_{j}\right)\right)^{2} \\&+\lambda\left\{\sum _ { u } \left(b_{u}^{2}\right.\right. \left.\left.+\left\|p_{u}\right\|^{2}\right)+\sum_{i}\left(b_{i}^{2}+\left\|q_{i}\right\|^{2}+\left\|y_{i}\right\|^{2}\right)\right\} \end{aligned}\)
我们首先来计算\(\sum_{(u, i) \in K}\left(r_{u i}-\mu-b_{u}-b_{i}-q_{i}^{T}\left(p_{u}+|N(u)|^{-\frac{1}{2}} \sum_{j \in N(u)} y_{j}\right)\right)^{2}\)这一部分的值，虽然看起来繁杂，但可以简化为\((r_{ui}-\hat{r}_{ui})^2\)，代码如下所示，
1 | VectorEntry vectorEntry = (VectorEntry)var7.next(); |
通过vectorEntry.get()方法可以获得实际的真实评分值，调用predict()方法可以获得预测评分值，二者相减得到误差，再进行平方即可求得这一部分的值。需要注意的是，在调用predict()方法时需要首先计算用户交互过物品的隐因子向量factorVector，求法与predict()方法中的求法相同，代码如下所示，
1 | this.factorVector.assign((indexx, value) -> { |
再接下来我们对公式的\(\lambda({\sum _ { u } b_{u}^{2} + \sum _ { i } b_{i}^{2}})\)进行求解，代码如下所示，其中factor指的是用户u的用户偏置，itemBias指的是物品i的物品偏置。
1 | factor = this.userBiases.get(userIndex); |
然后我们对公式的\(\lambda({\sum _ { u } ||p_{u}||^{2} + \sum _ { i } ||q_{i}||^{2}})\)进行求解，首先进入隐因子向量维度索引的循环，根据特定用户的用户索引userIndex和隐因子向量维度索引factorIndex得到用户隐因子值userFactor，根据特定物品的物品索引itemIndex和隐因子向量维度索引factorIndex得到物品隐因子值itemFactor，代码如下所示，
1 | for(int factorIndex = 0; factorIndex < this.numFactors; ++factorIndex) { |
最后我们对公式的\(\lambda \sum _ i ||y_{i}||^2\)进行求解，这里可以借鉴预测函数中\(y_{i}\)的求和，不过损失函数中是对其先平方之后再进行求和，代码如下，
1 | while(var23.hasNext()) { |
更新公式
最后我们关注一下更新函数的部分：
\(\begin{array}{c} e_{u i}=r_{u i}-\hat{r}_{u i} \\ b_{u} \leftarrow b_{u}+\gamma \cdot\left(e_{u i}-\lambda \cdot b_{u}\right) \\ b_{i} \leftarrow b_{i}+\gamma \cdot\left(e_{u i}-\lambda \cdot b_{i}\right) \\ p_{u} \leftarrow p_{u}+\gamma \cdot\left(e_{u i} \cdot q_{i}-\lambda \cdot p_{u}\right) \\ q_{i} \leftarrow q_{i}+\gamma \cdot\left(e_{u i} \cdot\left(p_{u}+\frac{1}{\sqrt{\left\|R_{u}\right\|}} \sum_{j \in R_{u}} y_{j}\right)-\lambda \cdot q_{i}\right) \\ y_{j} \leftarrow y_{j}+\gamma \cdot\left(e_{u i} \cdot \frac{1}{\sqrt{\left\|R_{u}\right\|}} \cdot q_{i}-\lambda \cdot q_{u}\right) \end{array}\)
- \(b_{u}\)的更新：
1 | this.userBiases.plus(userIndex, (double)this.learnRate * (error - this.regBias * factor)); |
- \(b_{i}\)的更新：
1 | this.itemBiases.plus(itemIndex, (double)this.learnRate * (error - this.regBias * itemBias)); |
- \(p_{u}\)和\(q_{i}\)的更新：
1 | for(int factorIndex = 0; factorIndex < this.numFactors; ++factorIndex) { |
需要注意的是，这里记录了step数组，其中记录的是\(e_{u i} \cdot \frac{1}{\sqrt{\left|R_{u}\right|}} \cdot q_{i}\)的值（为了\(y_{j}\)的更新）。
- \(y_{j}\)的更新：
1 | Iterator var23 = userVector.iterator(); |
这里需要区分一下，index指的是用户的索引，factorIndex指的是隐因子向量的索引，factor指的是与当前用户交互过的物品隐因子值（已知隐因子向量索引factorIndex）。