/
DCF.m
142 lines (125 loc) · 3.78 KB
/
DCF.m
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
141
142
function [B,D,X,Y] = DCF(maxS, minS, S, ST, IDX, IDXT, r, alpha, beta, option)
%DCF: Dicrete Collaborative Filtering described in Algorithm 1.
%Input:
%maxS: max rating score
%minS: min rating score
%S: user-item score matrix, [m,n] = size(S)
%ST: transpose of ST, for efficient sparse matrix indexing in Matlab, i.e.,
%matlab can only efficiently access sparse matrix by column.
%IDX: nonzero (observed) entry index of S
%IDXT: transpose of IDX for efficient sparse matrix indexing in Matlab.
%r: bit length
%alpha: trade-off paramter. good default = 0.001.
%beta: trade-off paramter. good default = 0.001.
%option:
%option.maxItr: max iterations. Default = 50.
%option.maxItr2: max iteration for cylic binary loop. Default = 5.
%option.tol: tolerance. Default = 1e-5.
%option.debug: show obj?. Default = false.
%Output:
%B: user codes
%D: item codes
%X: surrogate user vector
%Y: surrogate item vector
%Reference:
% Hanwang Zhang, Fumin Shen, Wei Liu, Xiangnan He, Huanbo Luan, Tat-seng
% Chua. "Discrete Collaborative Filtering", SIGIR 2016
%Version: 1.0
%Written by Hanwang Zhang (hanwangzhang AT gmail.com)
[m,n] = size(S);
converge = false;
it = 1;
if isfield(option,'maxItr')
maxItr = option.maxItr;
else
maxItr = 50;
end
if isfield(option,'maxItr2')
maxItr2 = option.maxItr2;
else
maxItr2 = 5;
end
if isfield(option, 'Init')
Init = option.Init;
else
Init = True;
end
if Init
if (isfield(option,'B0') && isfield(option,'D0') && isfield(option,'X0') && isfield(option,'Y0'))
B0 = option.B0; D0 = option.D0; X0 = option.X0; Y0 = option.Y0;
else
[U,V,X0,Y0] = DCFinit(maxS,minS, S, ST, IDX, IDXT, r, alpha, beta, option);
B0 = sign(U); B0(B0 == 0) = 1;
D0 = sign(V); D0(D0 == 0) = 1;
end
else
U = rand(r,m);
V = rand(r,n);
B0 = sign(U); B0(B0 == 0) = 1;
D0 = sign(V); D0(D0 == 0) = 1;
X0 = UpdateSVD(B0);
Y0 = UpdateSVD(D0);
end
if isfield(option,'debug')
debug = option.debug;
else
debug = false;
end
B = B0;
D = D0;
X = X0;
Y = Y0;
if debug
[loss,obj] = DCFobj(maxS,minS,S,IDX,B,D,X,Y,alpha,beta);
disp('Starting DCF...');
disp(['loss value = ',num2str(loss)]);
disp(['obj value = ',num2str(obj)]);
end
while ~converge
B0 = B;
D0 = D;
parfor i = 1:m
%B(:,i) = DCD(D(:,IDX(i,:)),B(:,i),ScaleScore(full(S(i,IDX(i,:))'),r,maxS,minS), alpha*X(:,i),maxItr2);
%B(:,i) = DCD(D(:,IDX(i,:)),B(:,i),ScaleScore(nonzeros(ST(:,i)),r,maxS,minS), alpha*X(:,i),maxItr2);
d = D(:,IDXT(:,i));
b = B(:,i);
DCDmex(b,d*d',d*ScaleScore(nonzeros(ST(:,i)),r,maxS,minS), alpha*X(:,i),maxItr2);
B(:,i) = b;
end
parfor j = 1:n
b = B(:,IDX(:,j));
d = D(:,j);
DCDmex(d,b*b',b*ScaleScore(nonzeros(S(:,j)),r,maxS,minS), beta*Y(:,j),maxItr2);
D(:,j)=d;
end
X = UpdateSVD(B);
Y = UpdateSVD(D);
if debug
[loss,obj] = DCFobj(maxS,minS,S,IDX,B,D,X,Y,alpha,beta);
disp(['loss value = ',num2str(loss)]);
disp(['obj value = ',num2str(obj)]);
end
disp(['DCF at bit ',int2str(r),' Iteration:',int2str(it)]);
if it >= maxItr || (sum(sum(B~=B0)) == 0 && sum(sum(D~=D0)) == 0)
converge = true;
end
it = it+1;
end
end
function [loss,obj] = DCFobj(maxS,minS,S,IDX,B,D,X,Y,alpha,beta)
[~,n] = size(S);
r = size(B,1);
loss = zeros(1,n);
parfor j = 1:n
dj = D(:,j);
Bj = B(:,IDX(:,j));
BBj = Bj*Bj';
term1 = dj'*BBj*dj;
Sj = ScaleScore(nonzeros(S(:,j)),r,maxS,minS);
term2 = 2*dj'*Bj*Sj;
term3 = sum(Sj.^2);
loss(j) = term1-term2+term3;
end
loss = sum(loss);
obj = loss-2*alpha*trace(B*X')-2*beta*trace(D*Y');
end