Information Technology Reference
In-Depth Information
fixed while determining the gradient with respect to the remaining matrix. The algo-
rithm switches matrices in the next iterative step. As soon as a stopping criterion
is matches, the procedure terminates providing the low rank approximation. Stop-
ping criteria include thresholds as well as maximum iterations. Thresholds define a
limit for the improvement between iterations. As we observe less improvement than
defined, we terminate the procedure. Conversely, a maximum number of iterations
aborts disregarding improvements. Both approaches have advantages. Thresholds
guarantee convergence to the desired quality. Unfortunately, this may lead to long
running times. In contrast, maximum iterations assure limited running. Still, the algo-
rithm may provide only sub-optimal solutions. We obtain recommendations as we
map user and item profiles onto the low ranked subspace.
Algorithm 6
Alternating Least Squares Matrix Factorization CF
Input
interaction matrix
R
u,
i
, number of latent factors to consider
k
, termination condition
,
optimization function
q
(
·
,
·
)
Output
predicted interactions
1:
P
ₐ
rand
(
|
U
|
, k)
randomly initialize latent user factors
2:
Q
ₐ
rand
(k,
|
I
|
)
randomly initialize latent item factors
3:
while
=
false
do
PQ
)
4:
P
ₐ
argmax
P
q
(
R
,
Optimize
P
keeping
Q
fixed
PQ
)
5:
Q
ₐ
argmax
Q
q
(
R
,
Optimize
Q
keeping
P
fixed
6:
end while
7: recommendations
ₐ
top
(k,
P
u
,
Q
i
,
R
)
Algorithm 7 illustrates an alternative way to obtain low rank approximations.
Instead of iteratively optimizing user or item factors, the algorithm randomly picks
interactions. Subsequently, we compute the gradients for both users and item factors
and adjust the factor matrices accordingly. Identical stopping criteria apply to this
setting.
Algorithm 7
Stochastic Gradient Descent Matrix Factorization CF
Input
interaction matrix
R
u,
i
, number of latent factors to consider
k
, termination condition
,
optimization function
q
(
·
,
·
)
, learning rate
ν
Output
predicted interactions
1:
P
ₐ
rand
(
|
U
|
, k)
randomly initialize latent user factors
2:
Q
ₐ
rand
(k,
|
I
|
)
randomly initialize latent item factors
3:
while
=
false
do
4:
(u,
i
)
ₐ
rand
(
R
)
pick random interactions
P
u
Q
i
)
5:
e
ₐ
q
(
R
(u,
i
),
determine prediction quality
6:
P
ₐ
P
·
ν
∇
e
P
update user factors
7:
Q
ₐ
Q
·
ν
∇
e
Q
update item factors
8:
end while
9: recommendations
ₐ
top
(k,
P
u
,
Q
i
,
R
)
Search WWH ::
Custom Search