-
Notifications
You must be signed in to change notification settings - Fork 10
/
best_averages.cpp
204 lines (178 loc) · 6.51 KB
/
best_averages.cpp
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <algorithm>
#include "globals.h"
#include "load.h"
#include "fmin.h"
#include "stdafx.h"
#include "optimization.h"
using namespace std;
extern const int MAX_USERS; // users in the entire training set
extern const int MAX_MOVIES; // movies in the entire training set (+1)
static const int PROBE_SIZE = 1408395;
static const int NON_PROBE_SIZE = 99072112;
static const int MAX_ITS = 0;
static Data *ratings;
static Data *cv_ratings;
static int iteration = 0;
const static float avg = 3.6033;
static double *movie_avg;
static double *user_avg;
double cost(Data *ratings, int num_ratings);
double f(double K);
double predict(int user, int movie) { return avg + user_avg[user] + movie_avg[movie]; }
void cg(Data *ratings, int num_ratings, double K);
void cg_grad(const alglib::real_1d_array& x, double &f, alglib::real_1d_array& grad, void *p);
double compute_gradient(Data *ratings, int num_ratings, double *movie_gradient, double *user_gradient, double K);
void callback(const alglib::real_1d_array &x, double f, void *p);
struct cg_ptr {
cg_ptr(Data *r, int n, double *m, double *u, double k):
ratings(r), num_ratings(n), movie_gradient(m), user_gradient(u), K(k) {}
Data *ratings;
int num_ratings;
double *movie_gradient;
double *user_gradient;
double K;
};
// args: min_lambda max_lambda
int main(int argc, char **argv) {
double min_lambda, max_lambda;
if (argc != 3) {
cout << "usage: ./best_averages min_lambda max_lambda" << endl;
exit(1);
}
min_lambda = atof(argv[1]);
max_lambda = atof(argv[2]);
ratings = new Data[NON_PROBE_SIZE]; load_binary(ratings, "cpp/train.bin");
cv_ratings = new Data[PROBE_SIZE]; load_binary(cv_ratings, "cpp/cv.bin");
movie_avg = new double[MAX_MOVIES+MAX_USERS] ();
user_avg = movie_avg + MAX_MOVIES;
double best_lambda = fminbnd(f, min_lambda, max_lambda);
cout << "optimal lambda is " << best_lambda << endl;
return 0;
}
double f(double K) {
cout << "iteration " << ++iteration;
cout << " using K = " << K << endl;
time_t start, end;
double total_time, train_cost, cv_cost;
time(&start);
for (int i=0; i<MAX_MOVIES+MAX_USERS; i++)
movie_avg[i] = 0;
cg(ratings, NON_PROBE_SIZE, K);
time(&end);
total_time = difftime(end,start);
train_cost = cost(ratings, NON_PROBE_SIZE);
cv_cost = cost(cv_ratings, PROBE_SIZE);
cout << "total time: " << total_time << "s" << endl;
cout << "training set cost: " << train_cost << endl;
cout << "cross validation cost: " << cv_cost << endl;
cout << endl;
return cv_cost;
}
double cost(Data *ratings, int num_ratings) {
double err, prediction, sq = 0;
int user; short movie;
Data *rating;
for (int i=0; i<num_ratings; i++) {
rating = ratings + i;
movie = rating->movie;
user = rating->user;
prediction = predict(user, movie);
err = (1.0 * rating->rating - prediction);
sq += err*err;
}
return sqrt(sq/num_ratings);
}
double compute_gradient(Data *ratings, int num_ratings, double *movie_gradient, double *user_gradient, double K) {
int nm = MAX_MOVIES, nu = MAX_USERS;
for (int i=0; i<nm+nu; i++) movie_gradient[i] = 0;
//time_t start,end; time(&start);
double sq=0;
#pragma omp parallel
{
int user;
short movie;
double err, prediction, lcl_sq=0;
Data *rating;
double *lcl_movie_gradient = new double[nm+nu] ();
double *lcl_user_gradient = lcl_movie_gradient + nm;
#pragma omp for
for (int i=0; i<num_ratings; i++) {
rating = ratings + i;
user = rating->user;
movie = rating->movie;
prediction = predict(user, movie);
err = (1.0 * rating->rating - prediction);
lcl_sq += err*err;
lcl_movie_gradient[movie] += -err + K*movie_avg[movie];
lcl_user_gradient[user] += -err + K*user_avg[user];
}
#pragma omp critical
{
sq += lcl_sq;
cblas_daxpy(nm+nu, (double)10/num_ratings, lcl_movie_gradient, 1, movie_gradient, 1);
}
delete [] lcl_movie_gradient;
}
//time(&end); cout << "time: " << difftime(end,start) << "s " << sqrt(sq/num_ratings) << endl;
return sqrt(sq/num_ratings);
}
void cg(Data *ratings, int num_ratings, double K) {
using namespace alglib;
int nm = MAX_MOVIES, nu = MAX_USERS, n; n= nm+nu;
double *movie_gradient = new double[n];
double *user_gradient = movie_gradient + nm;
real_1d_array x; x.setlength(n);
x.setcontent(n, movie_avg);
double epsg = 0;
double epsf = 0.001;
double epsx = 0;
ae_int_t maxits = MAX_ITS;
mincgstate state;
mincgreport rep;
cg_ptr b(ratings, num_ratings, movie_gradient, user_gradient, K);
mincgcreate(n, x, state);
mincgsetcond(state, epsg, epsf, epsx, maxits);
mincgsetxrep(state, true);
cout << "optimizing" << endl;
alglib::mincgoptimize(state, cg_grad, callback, &b);
cout << "getting results" << endl;
mincgresults(state, x, rep);
cout << rep.iterationscount << " iterations " << rep.nfev << " function evaluations" << endl;
switch(rep.terminationtype) {
case -2:
cout << "rounding errors prevent further improvement. X contains best point found." << endl;
break;
case -1:
cout << "incorrect parameters were specified" << endl;
break;
case 1:
cout << "success. relative function improvement is no more than " << epsf << endl;
break;
case 2:
cout << "success. relative step is no more than " << epsx << endl;
break;
case 4:
cout << "success. gradient norm is no more than " << epsg << endl;
break;
case 5:
cout << "MaxIts steps was taken" << endl;
break;
case 7:
cout << "stopping conditions are too stringent, further improvement is impossible" << endl;
break;
}
}
void cg_grad(const alglib::real_1d_array& x, double &f, alglib::real_1d_array& grad, void *p) {
cg_ptr *b = (cg_ptr *)p;
int n = x.length();
for (int i=0; i<n; i++)
movie_avg[i] = x[i];
f = compute_gradient(b->ratings, b->num_ratings, b->movie_gradient, b->user_gradient, b->K);
for (int i=0; i<n; i++)
grad[i] = b->movie_gradient[i];
}
void callback(const alglib::real_1d_array &x, double f, void *p) {
static int i = 0;
i++;
cout << "step " << i << " rmse: " << f << endl;
}