git.sesse.net Git - wloh/blob - bayeswf.cpp

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5
   6 #include <map>
   7 #include <vector>
   8 #include <string>
   9 #include <algorithm>
  10
  11 using namespace std;
  12
  13 #define PRIOR_MU 1500
  14 #define PRIOR_WEIGHT 1.0
  15 #define MAX_PLAYERS 4096
  16 #define DUMP_RAW 0
  17
  18 float mu[MAX_PLAYERS];
  19 float mu_stddev[MAX_PLAYERS];
  20 float global_sigma = 70.0f;
  21 float prior_sigma = 70.0f;
  22
  23 #define EPSILON 1e-3
  24
  25 /*
  26  * L(mu_vec, sigma_vec, matches) = product[ L(mu_A, sigma_A, mu_B, sigma_B, score_AB - score_BA) ]
  27  * log-likelihood = sum[ log( L(mu_A, sigma_A, mu_B, sigma_B, score_AB - score_BA) ) ]
  28  *
  29  * L(mu1, sigma1, mu2, sigma2, score2 - score1) = sigmoid(mu2 - mu1, sqrt(sigma1² + sigma2²), (score2 - score1))
  30  *
  31  * pdf := 1/(sigma * sqrt(2*Pi)) * exp(-(x - mu)^2 / (2 * sigma^2));
  32  * pdfs := subs({ mu = mu1 - mu2, sigma = sqrt(sigma1^2 + sigma2^2) }, pdf);
  33  * diff(log(pdfs), mu1);
  34  */
  35
  36 struct match {
  37         int player, other_player;
  38         int margin;
  39         float weight;
  40 };
  41 map<int, vector<match> > matches_for_player;
  42 vector<match> all_matches;
  43
  44 void dump_scores(const vector<string> &players, const float *mu, const float *mu_stddev, int num_players)
  45 {
  46 #if 0
  47         for (int i = 0; i < num_players; ++i) {
  48                 printf("%s=[%5.1f, %4.1f] ", players[i].c_str(), mu[i], sigma[i]);
  49         }
  50         printf("\n");
  51 #elif 0
  52         for (int i = 0; i < num_players; ++i) {
  53                 printf("%5.1f ", mu[i]);
  54         }
  55         printf("\n");
  56 #else
  57         for (int i = 0; i < num_players; ++i) {
  58                 printf("%f %f %s\n", mu[i], mu_stddev[i], players[i].c_str());
  59         }
  60 #endif
  61 }
  62
  63 /*
  64  * diff(logL, mu1) = -w * (mu1 - mu2 - x) / sigma_c^2
  65  * maximizer for mu1 is given by: sum_i[ (w_i/sigma_c_i)^2 (mu1 - mu2_i - x_i) ] = 0
  66  *                                sum_i[ (w_i/sigma_c_i)^2 mu1 ] = sum_i [ (w_i/sigma_c_i)^2 ( mu2_i + x_i ) ]
  67  *                                mu1 = sum_i [ (w_i/sigma_c_i)^2 ( mu2_i + x_i ) ] / sum_i[ (w_i/sigma_c_i)^2 ]
  68  */
  69 void update_mu(float *mu, int player_num, const vector<match> &matches)
  70 {
  71         if (matches.empty()) {
  72                 return;
  73         }
  74
  75         float nom = 0.0f, denom = 0.0f;
  76
  77         // Prior.
  78         {
  79                 float inv_sigma2 = 1.0f / (prior_sigma * prior_sigma);
  80                 nom += PRIOR_WEIGHT * PRIOR_MU * inv_sigma2;
  81                 denom += PRIOR_WEIGHT * inv_sigma2;
  82         }
  83
  84         // All matches.
  85         for (unsigned i = 0; i < matches.size(); ++i) {
  86                 float inv_sigma_c2 = matches[i].weight / (global_sigma * global_sigma);
  87                 float x = matches[i].margin; // / 70.0f;
  88
  89                 nom += (mu[matches[i].other_player] + x) * inv_sigma_c2;
  90                 denom += inv_sigma_c2;
  91         }
  92         mu[player_num] = nom / denom;
  93 }
  94
  95 void dump_raw(const float *mu, int num_players)
  96 {
  97         for (unsigned i = 0; i < all_matches.size(); ++i) {
  98                 const match& m = all_matches[i];
  99
 100                 float mu1 = mu[m.player];
 101                 float mu2 = mu[m.other_player];
 102                 float sigma = global_sigma;
 103                 float mu = mu1 - mu2;
 104                 float x = m.margin;
 105                 float w = m.weight;
 106
 107                 printf("%f %f\n", (x - mu) / sigma, w);
 108         }
 109 }
 110
 111 /*
 112  * diff(logL, sigma) = w ( (x - mu)² - sigma² ) / sigma³
 113  * maximizer for sigma is given by: sum_i[ (w_i/sigma)³ ((x - mu)² - sigma²) ] = 0
 114  *                                   sum_i[ w_i ( (x - mu)² - sigma² ) ] = 0                            |: sigma != 0
 115  *                                   sum_i[ w_i (x - mu)² ] = sum[ w_i sigma² ]
 116  *                                   sigma = sqrt( sum_i[ w_i (x - mu)² ] / sum[w_i] )
 117  */
 118 void update_global_sigma(float *mu, int num_players)
 119 {
 120         float nom = 0.0f, denom = 0.0f;
 121         for (unsigned i = 0; i < all_matches.size(); ++i) {
 122                 const match& m = all_matches[i];
 123
 124                 float mu1 = mu[m.player];
 125                 float mu2 = mu[m.other_player];
 126                 float mu = mu1 - mu2;
 127                 float x = m.margin;
 128                 float w = m.weight;
 129
 130                 nom += w * ((x - mu) * (x - mu));
 131                 denom += w;
 132         }
 133
 134         global_sigma = sqrt(nom / denom);
 135 }
 136
 137 /*
 138  * diff(priorlogL, sigma) = w ( (x - mu)² - sigma² ) / sigma³
 139  * maximizer for sigma is given by: sum_i[ (w_i/sigma)³ ((x - mu)² - sigma²) ] = 0
 140  *                                   sum_i[ w_i ( (x - mu)² - sigma² ) ] = 0                            |: sigma != 0
 141  *                                   sum_i[ w_i (x - mu)² ] = sum[ w_i sigma² ]
 142  *                                   sigma = sqrt( sum_i[ w_i (x - mu)² ] / sum[w_i] )
 143  */
 144 void update_prior_sigma(float *mu, int num_players)
 145 {
 146         float nom = 0.0f, denom = 0.0f;
 147         for (int i = 0; i < num_players; ++i) {
 148                 float mu1 = mu[i];
 149
 150                 nom += ((mu1 - PRIOR_MU) * (mu1 - PRIOR_MU));
 151                 denom += 1.0f;
 152         }
 153
 154         prior_sigma = sqrt(nom / denom);
 155         if (!(prior_sigma > 40.0f)) {
 156                 prior_sigma = 40.0f;
 157         }
 158 }
 159
 160 float compute_logl(float z)
 161 {
 162         return -0.5 * (log(2.0f / M_PI) + z * z);
 163 }
 164
 165 float compute_total_logl(float *mu, int num_players)
 166 {
 167         float total_logl = 0.0f;
 168
 169         // Prior.
 170         for (int i = 0; i < num_players; ++i) {
 171                 total_logl += PRIOR_WEIGHT * compute_logl((mu[i] - PRIOR_MU) / prior_sigma);
 172         }
 173
 174         // Matches.
 175         for (unsigned i = 0; i < all_matches.size(); ++i) {
 176                 const match& m = all_matches[i];
 177
 178                 float mu1 = mu[m.player];
 179                 float mu2 = mu[m.other_player];
 180                 float sigma = global_sigma;
 181                 float mu = mu1 - mu2;
 182                 float x = m.margin;
 183                 float w = m.weight;
 184
 185                 total_logl += w * compute_logl((x - mu) / sigma);
 186         }
 187
 188         return total_logl;
 189 }
 190
 191 /*
 192  * Compute Hessian matrix of the negative log-likelihood, ie. for each term in logL:
 193  *
 194  * M_ij = D_i D_j (- logL) = -w / sigma²                                for i != j
 195  *                            w / sigma²                                for i == j
 196  *
 197  * Note that this does not depend on mu or the margin at all.
 198  */
 199 double hessian[MAX_PLAYERS][MAX_PLAYERS];
 200 void construct_hessian(const float *mu, int num_players)
 201 {
 202         memset(hessian, 0, sizeof(hessian));
 203
 204         for (unsigned i = 0; i < all_matches.size(); ++i) {
 205                 const match &m = all_matches[i];
 206
 207                 int p1 = m.player;
 208                 int p2 = m.other_player;
 209
 210                 double sigma_sq = global_sigma * global_sigma;
 211                 float w = m.weight;
 212
 213                 hessian[p1][p2] -= w / sigma_sq;
 214                 hessian[p2][p1] -= w / sigma_sq;
 215
 216                 hessian[p1][p1] += w / sigma_sq;
 217                 hessian[p2][p2] += w / sigma_sq;
 218         }
 219 }
 220
 221 // Compute uncertainty (stddev) of mu estimates, which is 1/sqrt(H_ii),
 222 // where H is the Hessian (see construct_hessian()).
 223 void compute_mu_uncertainty(const float *mu, int num_players)
 224 {
 225         memset(mu_stddev, 0, sizeof(mu_stddev));
 226
 227         for (unsigned i = 0; i < all_matches.size(); ++i) {
 228                 const match &m = all_matches[i];
 229
 230                 int p1 = m.player;
 231                 int p2 = m.other_player;
 232
 233                 double sigma_sq = global_sigma * global_sigma;
 234                 float w = m.weight;
 235
 236                 // Temporarily use mu_stddev to store the diagonal of the Hessian.
 237                 mu_stddev[p1] += w / sigma_sq;
 238                 mu_stddev[p2] += w / sigma_sq;
 239         }
 240         for (int i = 0; i < num_players; ++i) {
 241                 mu_stddev[i] = 1.0f / sqrt(mu_stddev[i]);
 242         }
 243 }
 244
 245 int main(int argc, char **argv)
 246 {
 247         int num_players;
 248         if (scanf("%d", &num_players) != 1) {
 249                 fprintf(stderr, "Could't read number of players\n");
 250                 exit(1);
 251         }
 252
 253         if (num_players > MAX_PLAYERS) {
 254                 fprintf(stderr, "Max %d players supported\n", MAX_PLAYERS);
 255                 exit(1);
 256         }
 257
 258         vector<string> players;
 259         map<string, int> player_map;
 260
 261         for (int i = 0; i < num_players; ++i) {
 262                 char buf[256];
 263                 if (scanf("%s", buf) != 1) {
 264                         fprintf(stderr, "Couldn't read player %d\n", i);
 265                         exit(1);
 266                 }
 267
 268                 players.push_back(buf);
 269                 player_map[buf] = i;
 270         }
 271
 272         int num_matches = 0;
 273         for ( ;; ) {
 274                 char pl1[256], pl2[256];
 275                 int score1, score2;
 276                 float weight;
 277
 278                 if (scanf("%s %s %d %d %f", pl1, pl2, &score1, &score2, &weight) != 5) {
 279                         //fprintf(stderr, "Read %d matches.\n", num_matches);
 280                         break;
 281                 }
 282
 283                 ++num_matches;
 284
 285                 if (player_map.count(pl1) == 0) {
 286                         fprintf(stderr, "Unknown player '%s'\n", pl1);
 287                         exit(1);
 288                 }
 289                 if (player_map.count(pl2) == 0) {
 290                         fprintf(stderr, "Unknown player '%s'\n", pl2);
 291                         exit(1);
 292                 }
 293
 294                 match m1;
 295                 m1.player = player_map[pl1];
 296                 m1.other_player = player_map[pl2];
 297                 m1.margin = score1 - score2;
 298                 m1.weight = weight;
 299                 matches_for_player[player_map[pl1]].push_back(m1);
 300
 301                 match m2;
 302                 m2.player = player_map[pl2];
 303                 m2.other_player = player_map[pl1];
 304                 m2.margin = score2 - score1;
 305                 m2.weight = weight;
 306                 matches_for_player[player_map[pl2]].push_back(m2);
 307
 308                 all_matches.push_back(m1);
 309         }
 310
 311         float mu[MAX_PLAYERS];
 312
 313         for (int i = 0; i < num_players; ++i) {
 314                 mu[i] = PRIOR_MU;
 315         }
 316
 317         for (int j = 0; j < 1000; ++j) {
 318                 float old_mu[MAX_PLAYERS];
 319                 float old_global_sigma = global_sigma;
 320                 float old_prior_sigma = prior_sigma;
 321                 memcpy(old_mu, mu, sizeof(mu));
 322                 for (int i = 0; i < num_players; ++i) {
 323                         update_mu(mu, i, matches_for_player[i]);
 324                 }
 325                 update_global_sigma(mu, num_players);
 326                 update_prior_sigma(mu, num_players);
 327                 /* for (int i = 0; i < num_players; ++i) {
 328                         update_sigma(mu, sigma, i, matches_for_player[i]);
 329                         dump_scores(players, mu, sigma, num_players);
 330                 } */
 331
 332                 float sumdiff = 0.0f;
 333                 for (int i = 0; i < num_players; ++i) {
 334                         sumdiff += (mu[i] - old_mu[i]) * (mu[i] - old_mu[i]);
 335                 }
 336                 sumdiff += (prior_sigma - old_prior_sigma) * (prior_sigma - old_prior_sigma);
 337                 sumdiff += (global_sigma - old_global_sigma) * (global_sigma - old_global_sigma);
 338                 if (sumdiff < EPSILON) {
 339                         //fprintf(stderr, "Converged after %d iterations. Stopping.\n", j);
 340                         printf("%d -1\n", j + 1);
 341                         break;
 342                 }
 343         }
 344
 345 #if DUMP_RAW
 346         dump_raw(mu, num_players);
 347 #else
 348         compute_mu_uncertainty(mu, num_players);
 349         dump_scores(players, mu, mu_stddev, num_players);
 350         //fprintf(stderr, "Optimal sigma: %f (two-player: %f)\n", sigma[0], sigma[0] * sqrt(2.0f));
 351         printf("%f -2\n", global_sigma / sqrt(2.0f));
 352         printf("%f -3\n", prior_sigma);
 353
 354         float total_logl = compute_total_logl(mu, num_players);
 355         printf("%f -4\n", total_logl);
 356
 357 //      construct_hessian(mu, sigma, num_players);
 358 #endif
 359 }