src/math/linreg.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2005 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18 #include <gsl/gsl_blas.h>
  19 #include <gsl/gsl_cblas.h>
  20 #include <gsl/gsl_errno.h>
  21 #include <gsl/gsl_fit.h>
  22 #include <gsl/gsl_multifit.h>
  23 #include <linreg/sweep.h>
  24 #include <math/coefficient.h>
  25 #include <math/linreg.h>
  26 #include <math/coefficient.h>
  27 #include <src/data/variable.h>
  28 #include <src/data/value.h>
  29 #include <gl/xalloc.h>
  30
  31 /*
  32   Find the least-squares estimate of b for the linear model:
  33
  34   Y = Xb + Z
  35
  36   where Y is an n-by-1 column vector, X is an n-by-p matrix of
  37   independent variables, b is a p-by-1 vector of regression coefficients,
  38   and Z is an n-by-1 normally-distributed random vector with independent
  39   identically distributed components with mean 0.
  40
  41   This estimate is found via the sweep operator or singular-value
  42   decomposition with gsl.
  43
  44
  45   References:
  46
  47   1. Matrix Computations, third edition. GH Golub and CF Van Loan.
  48   The Johns Hopkins University Press. 1996. ISBN 0-8018-5414-8.
  49
  50   2. Numerical Analysis for Statisticians. K Lange. Springer. 1999.
  51   ISBN 0-387-94979-8.
  52
  53   3. Numerical Linear Algebra for Applications in Statistics. JE Gentle.
  54   Springer. 1998. ISBN 0-387-98542-5.
  55 */
  56
  57
  58 /*
  59   Get the mean and standard deviation of a vector
  60   of doubles via a form of the Kalman filter as
  61   described on page 32 of [3].
  62  */
  63 static int
  64 linreg_mean_std (gsl_vector_const_view v, double *mp, double *sp, double *ssp)
  65 {
  66   size_t i;
  67   double j = 0.0;
  68   double d;
  69   double tmp;
  70   double mean;
  71   double variance;
  72
  73   mean = gsl_vector_get (&v.vector, 0);
  74   variance = 0;
  75   for (i = 1; i < v.vector.size; i++)
  76     {
  77       j = (double) i + 1.0;
  78       tmp = gsl_vector_get (&v.vector, i);
  79       d = (tmp - mean) / j;
  80       mean += d;
  81       variance += j * (j - 1.0) * d * d;
  82     }
  83   *mp = mean;
  84   *sp = sqrt (variance / (j - 1.0));
  85   *ssp = variance;
  86
  87   return GSL_SUCCESS;
  88 }
  89
  90 /*
  91   Set V to contain an array of pointers to the variables
  92   used in the model. V must be at least C->N_COEFFS in length.
  93   The return value is the number of distinct variables found.
  94  */
  95 int
  96 pspp_linreg_get_vars (const void *c_, const struct variable **v)
  97 {
  98   const pspp_linreg_cache *c = c_;
  99   const struct variable *tmp;
 100   int i;
 101   int j;
 102   int result = 0;
 103
 104   /*
 105      Make sure the caller doesn't try to sneak a variable
 106      into V that is not in the model.
 107    */
 108   for (i = 0; i < c->n_coeffs; i++)
 109     {
 110       v[i] = NULL;
 111     }
 112   for (j = 0; j < c->n_coeffs; j++)
 113     {
 114       tmp = pspp_coeff_get_var (c->coeff[j], 0);
 115       assert (tmp != NULL);
 116       /* Repeated variables are likely to bunch together, at the end
 117          of the array. */
 118       i = result - 1;
 119       while (i >= 0 && v[i] != tmp)
 120         {
 121           i--;
 122         }
 123       if (i < 0 && result < c->n_coeffs)
 124         {
 125           v[result] = tmp;
 126           result++;
 127         }
 128     }
 129   return result;
 130 }
 131
 132 /*
 133   Allocate a pspp_linreg_cache and return a pointer
 134   to it. n is the number of cases, p is the number of
 135   independent variables.
 136  */
 137 pspp_linreg_cache *
 138 pspp_linreg_cache_alloc (size_t n, size_t p)
 139 {
 140   pspp_linreg_cache *c;
 141
 142   c = (pspp_linreg_cache *) malloc (sizeof (pspp_linreg_cache));
 143   c->depvar = NULL;
 144   c->indep_means = gsl_vector_alloc (p);
 145   c->indep_std = gsl_vector_alloc (p);
 146   c->ssx = gsl_vector_alloc (p);        /* Sums of squares for the
 147                                            independent variables.
 148                                          */
 149   c->ss_indeps = gsl_vector_alloc (p);  /* Sums of squares for the
 150                                            model parameters.
 151                                          */
 152   c->cov = gsl_matrix_alloc (p + 1, p + 1);     /* Covariance matrix. */
 153   c->n_obs = n;
 154   c->n_indeps = p;
 155   /*
 156      Default settings.
 157    */
 158   c->method = PSPP_LINREG_SWEEP;
 159   c->predict = pspp_linreg_predict;
 160   c->residual = pspp_linreg_residual;   /* The procedure to compute my
 161                                            residuals. */
 162   c->get_vars = pspp_linreg_get_vars;   /* The procedure that returns
 163                                            pointers to model
 164                                            variables. */
 165   c->resid = NULL;              /* The variable storing my residuals. */
 166   c->pred = NULL;               /* The variable storing my predicted values. */
 167
 168   return c;
 169 }
 170
 171 bool
 172 pspp_linreg_cache_free (void *m)
 173 {
 174   int i;
 175
 176   pspp_linreg_cache *c = m;
 177   if (c != NULL)
 178     {
 179       gsl_vector_free (c->indep_means);
 180       gsl_vector_free (c->indep_std);
 181       gsl_vector_free (c->ss_indeps);
 182       gsl_matrix_free (c->cov);
 183       gsl_vector_free (c->ssx);
 184       for (i = 0; i < c->n_coeffs; i++)
 185         {
 186           pspp_coeff_free (c->coeff[i]);
 187         }
 188       free (c->coeff);
 189       free (c);
 190     }
 191   return true;
 192 }
 193
 194 /*
 195   Fit the linear model via least squares. All pointers passed to pspp_linreg
 196   are assumed to be allocated to the correct size and initialized to the
 197   values as indicated by opts.
 198  */
 199 int
 200 pspp_linreg (const gsl_vector * Y, const gsl_matrix * X,
 201              const pspp_linreg_opts * opts, pspp_linreg_cache * cache)
 202 {
 203   int rc;
 204   gsl_matrix *design = NULL;
 205   gsl_matrix_view xtx;
 206   gsl_matrix_view xm;
 207   gsl_matrix_view xmxtx;
 208   gsl_vector_view xty;
 209   gsl_vector_view xi;
 210   gsl_vector_view xj;
 211   gsl_vector *param_estimates;
 212
 213   size_t i;
 214   size_t j;
 215   double tmp;
 216   double m;
 217   double s;
 218   double ss;
 219
 220   if (cache == NULL)
 221     {
 222       return GSL_EFAULT;
 223     }
 224   if (opts->get_depvar_mean_std)
 225     {
 226       linreg_mean_std (gsl_vector_const_subvector (Y, 0, Y->size),
 227                        &m, &s, &ss);
 228       cache->depvar_mean = m;
 229       cache->depvar_std = s;
 230       cache->sst = ss;
 231     }
 232   for (i = 0; i < cache->n_indeps; i++)
 233     {
 234       if (opts->get_indep_mean_std[i])
 235         {
 236           linreg_mean_std (gsl_matrix_const_column (X, i), &m, &s, &ss);
 237           gsl_vector_set (cache->indep_means, i, m);
 238           gsl_vector_set (cache->indep_std, i, s);
 239           gsl_vector_set (cache->ssx, i, ss);
 240         }
 241     }
 242   cache->dft = cache->n_obs - 1;
 243   cache->dfm = cache->n_indeps;
 244   cache->dfe = cache->dft - cache->dfm;
 245   cache->n_coeffs = X->size2;
 246   cache->intercept = 0.0;
 247
 248   if (cache->method == PSPP_LINREG_SWEEP)
 249     {
 250       gsl_matrix *sw;
 251       /*
 252          Subtract the means to improve the condition of the design
 253          matrix. This requires copying X and Y. We do not divide by the
 254          standard deviations of the independent variables here since doing
 255          so would cause a miscalculation of the residual sums of
 256          squares. Dividing by the standard deviation is done GSL's linear
 257          regression functions, so if the design matrix has a poor
 258          condition, use QR decomposition.
 259
 260          The design matrix here does not include a column for the intercept
 261          (i.e., a column of 1's). If using PSPP_LINREG_QR, we need that column,
 262          so design is allocated here when sweeping, or below if using QR.
 263        */
 264       design = gsl_matrix_alloc (X->size1, X->size2);
 265       for (i = 0; i < X->size2; i++)
 266         {
 267           m = gsl_vector_get (cache->indep_means, i);
 268           for (j = 0; j < X->size1; j++)
 269             {
 270               tmp = (gsl_matrix_get (X, j, i) - m);
 271               gsl_matrix_set (design, j, i, tmp);
 272             }
 273         }
 274       sw = gsl_matrix_calloc (cache->n_indeps + 1, cache->n_indeps + 1);
 275       xtx = gsl_matrix_submatrix (sw, 0, 0, cache->n_indeps, cache->n_indeps);
 276
 277       for (i = 0; i < xtx.matrix.size1; i++)
 278         {
 279           tmp = gsl_vector_get (cache->ssx, i);
 280           gsl_matrix_set (&(xtx.matrix), i, i, tmp);
 281           xi = gsl_matrix_column (design, i);
 282           for (j = (i + 1); j < xtx.matrix.size2; j++)
 283             {
 284               xj = gsl_matrix_column (design, j);
 285               gsl_blas_ddot (&(xi.vector), &(xj.vector), &tmp);
 286               gsl_matrix_set (&(xtx.matrix), i, j, tmp);
 287             }
 288         }
 289
 290       gsl_matrix_set (sw, cache->n_indeps, cache->n_indeps, cache->sst);
 291       xty = gsl_matrix_column (sw, cache->n_indeps);
 292       /*
 293          This loop starts at 1, with i=0 outside the loop, so we can get
 294          the model sum of squares due to the first independent variable.
 295        */
 296       xi = gsl_matrix_column (design, 0);
 297       gsl_blas_ddot (&(xi.vector), Y, &tmp);
 298       gsl_vector_set (&(xty.vector), 0, tmp);
 299       tmp *= tmp / gsl_vector_get (cache->ssx, 0);
 300       gsl_vector_set (cache->ss_indeps, 0, tmp);
 301       for (i = 1; i < cache->n_indeps; i++)
 302         {
 303           xi = gsl_matrix_column (design, i);
 304           gsl_blas_ddot (&(xi.vector), Y, &tmp);
 305           gsl_vector_set (&(xty.vector), i, tmp);
 306         }
 307
 308       /*
 309          Sweep on the matrix sw, which contains XtX, XtY and YtY.
 310        */
 311       reg_sweep (sw);
 312       cache->sse = gsl_matrix_get (sw, cache->n_indeps, cache->n_indeps);
 313       cache->mse = cache->sse / cache->dfe;
 314       /*
 315          Get the intercept.
 316        */
 317       m = cache->depvar_mean;
 318       for (i = 0; i < cache->n_indeps; i++)
 319         {
 320           tmp = gsl_matrix_get (sw, i, cache->n_indeps);
 321           cache->coeff[i]->estimate = tmp;
 322           m -= tmp * gsl_vector_get (cache->indep_means, i);
 323         }
 324       /*
 325          Get the covariance matrix of the parameter estimates.
 326          Only the upper triangle is necessary.
 327        */
 328
 329       /*
 330          The loops below do not compute the entries related
 331          to the estimated intercept.
 332        */
 333       for (i = 0; i < cache->n_indeps; i++)
 334         for (j = i; j < cache->n_indeps; j++)
 335           {
 336             tmp = -1.0 * cache->mse * gsl_matrix_get (sw, i, j);
 337             gsl_matrix_set (cache->cov, i + 1, j + 1, tmp);
 338           }
 339       /*
 340          Get the covariances related to the intercept.
 341        */
 342       xtx = gsl_matrix_submatrix (sw, 0, 0, cache->n_indeps, cache->n_indeps);
 343       xmxtx = gsl_matrix_submatrix (cache->cov, 0, 1, 1, cache->n_indeps);
 344       xm = gsl_matrix_view_vector (cache->indep_means, 1, cache->n_indeps);
 345       rc = gsl_blas_dsymm (CblasRight, CblasUpper, cache->mse,
 346                            &xtx.matrix, &xm.matrix, 0.0, &xmxtx.matrix);
 347       if (rc == GSL_SUCCESS)
 348         {
 349           tmp = cache->mse / cache->n_obs;
 350           for (i = 1; i < 1 + cache->n_indeps; i++)
 351             {
 352               tmp -= gsl_matrix_get (cache->cov, 0, i)
 353                 * gsl_vector_get (cache->indep_means, i - 1);
 354             }
 355           gsl_matrix_set (cache->cov, 0, 0, tmp);
 356
 357           cache->intercept = m;
 358         }
 359       else
 360         {
 361           fprintf (stderr, "%s:%d:gsl_blas_dsymm: %s\n",
 362                    __FILE__, __LINE__, gsl_strerror (rc));
 363           exit (rc);
 364         }
 365       gsl_matrix_free (sw);
 366     }
 367   else if (cache->method == PSPP_LINREG_CONDITIONAL_INVERSE)
 368     {
 369       /*
 370         Use the SVD of X^T X to find a conditional inverse of X^TX. If
 371         the SVD is X^T X = U D V^T, then set the conditional inverse
 372         to (X^T X)^c = V D^- U^T. D^- is defined as follows: If entry
 373         (i, i) has value sigma_i, then entry (i, i) of D^- is 1 /
 374         sigma_i if sigma_i > 0, and 0 otherwise. Then solve the normal
 375         equations by setting the estimated parameter vector to
 376         (X^TX)^c X^T Y.
 377        */
 378     }
 379   else
 380     {
 381       gsl_multifit_linear_workspace *wk;
 382       /*
 383          Use QR decomposition via GSL.
 384        */
 385
 386       param_estimates = gsl_vector_alloc (1 + X->size2);
 387       design = gsl_matrix_alloc (X->size1, 1 + X->size2);
 388
 389       for (j = 0; j < X->size1; j++)
 390         {
 391           gsl_matrix_set (design, j, 0, 1.0);
 392           for (i = 0; i < X->size2; i++)
 393             {
 394               tmp = gsl_matrix_get (X, j, i);
 395               gsl_matrix_set (design, j, i + 1, tmp);
 396             }
 397         }
 398
 399       wk = gsl_multifit_linear_alloc (design->size1, design->size2);
 400       rc = gsl_multifit_linear (design, Y, param_estimates,
 401                                 cache->cov, &(cache->sse), wk);
 402       for (i = 0; i < cache->n_coeffs; i++)
 403         {
 404           cache->coeff[i]->estimate = gsl_vector_get (param_estimates, i + 1);
 405         }
 406       cache->intercept = gsl_vector_get (param_estimates, 0);
 407       if (rc == GSL_SUCCESS)
 408         {
 409           gsl_multifit_linear_free (wk);
 410           gsl_vector_free (param_estimates);
 411         }
 412       else
 413         {
 414           fprintf (stderr, "%s:%d: gsl_multifit_linear returned %d\n",
 415                    __FILE__, __LINE__, rc);
 416         }
 417     }
 418
 419
 420   cache->ssm = cache->sst - cache->sse;
 421   /*
 422      Get the remaining sums of squares for the independent
 423      variables.
 424    */
 425   m = 0;
 426   for (i = 1; i < cache->n_indeps; i++)
 427     {
 428       j = i - 1;
 429       m += gsl_vector_get (cache->ss_indeps, j);
 430       tmp = cache->ssm - m;
 431       gsl_vector_set (cache->ss_indeps, i, tmp);
 432     }
 433
 434   gsl_matrix_free (design);
 435   return GSL_SUCCESS;
 436 }
 437
 438 /*
 439   Is the coefficient COEF contained in the list of coefficients
 440   COEF_LIST?
 441  */
 442 static int
 443 has_coefficient (const struct pspp_coeff **coef_list, const struct pspp_coeff *coef,
 444                  size_t n)
 445 {
 446   size_t i = 0;
 447
 448   while (i < n)
 449     {
 450       if (coef_list[i] == coef)
 451         {
 452           return 1;
 453         }
 454       i++;
 455     }
 456   return 0;
 457 }
 458 /*
 459   Predict the value of the dependent variable with the
 460   new set of predictors. PREDICTORS must point to a list
 461   of variables, each of whose values are stored in VALS,
 462   in the same order.
 463  */
 464 double
 465 pspp_linreg_predict (const struct variable **predictors,
 466                      const union value **vals, const void *c_, int n_vals)
 467 {
 468   const pspp_linreg_cache *c = c_;
 469   int j;
 470   size_t next_coef = 0;
 471   const struct pspp_coeff **coef_list;
 472   const struct pspp_coeff *coe;
 473   double result;
 474   double tmp;
 475
 476   if (predictors == NULL || vals == NULL || c == NULL)
 477     {
 478       return GSL_NAN;
 479     }
 480   if (c->coeff == NULL)
 481     {
 482       /* The stupid model: just guess the mean. */
 483       return c->depvar_mean;
 484     }
 485   coef_list = xnmalloc (c->n_coeffs, sizeof (*coef_list));
 486   result = c->intercept;
 487
 488   /*
 489      The loops guard against the possibility that the caller passed us
 490      inadequate information, such as too few or too many values, or
 491      a redundant list of variable names.
 492    */
 493   for (j = 0; j < n_vals; j++)
 494     {
 495       coe = pspp_linreg_get_coeff (c, predictors[j], vals[j]);
 496       if (!has_coefficient (coef_list, coe, next_coef))
 497         {
 498           tmp = pspp_coeff_get_est (coe);
 499           if (var_is_numeric (predictors[j]))
 500             {
 501               tmp *= vals[j]->f;
 502             }
 503           result += tmp;
 504           coef_list[next_coef++] = coe;
 505         }
 506     }
 507   free (coef_list);
 508
 509   return result;
 510 }
 511
 512 double
 513 pspp_linreg_residual (const struct variable **predictors,
 514                       const union value **vals,
 515                       const union value *obs, const void *c, int n_vals)
 516 {
 517   double pred;
 518   double result;
 519
 520   if (predictors == NULL || vals == NULL || c == NULL || obs == NULL)
 521     {
 522       return GSL_NAN;
 523     }
 524   pred = pspp_linreg_predict (predictors, vals, c, n_vals);
 525
 526   result = gsl_isnan (pred) ? GSL_NAN : (obs->f - pred);
 527   return result;
 528 }
 529
 530 /*
 531   Which coefficient is associated with V? The VAL argument is relevant
 532   only to categorical variables.
 533  */
 534 const struct pspp_coeff *
 535 pspp_linreg_get_coeff (const pspp_linreg_cache * c,
 536                        const struct variable *v, const union value *val)
 537 {
 538   int i;
 539   struct pspp_coeff *result = NULL;
 540   const struct variable *tmp = NULL;
 541
 542   if (c == NULL)
 543     {
 544       return NULL;
 545     }
 546   if (c->coeff == NULL || c->n_indeps == 0 || v == NULL)
 547     {
 548       return NULL;
 549     }
 550   i = 0;
 551   result = c->coeff[0];
 552   tmp = pspp_coeff_get_var (result, 0);
 553   while (tmp != v && i < c->n_coeffs)
 554     {
 555       result = c->coeff[i];
 556       tmp = pspp_coeff_get_var (result, 0);
 557       i++;
 558     }
 559   if (tmp != v)
 560     {
 561       /*
 562         Not found.
 563        */
 564       return NULL;
 565     }
 566   if (var_is_numeric (v))
 567     {
 568       return result;
 569     }
 570   else if (val != NULL)
 571     {
 572       /*
 573          If v is categorical, we need to ensure the coefficient
 574          matches the VAL.
 575        */
 576       while (tmp != v && i < c->n_coeffs
 577              && compare_values (pspp_coeff_get_value (result, tmp),
 578                                 val, var_get_width (v)))
 579         {                       /* FIX THIS */
 580           i++;
 581           result = c->coeff[i];
 582           tmp = pspp_coeff_get_var (result, 0);
 583         }
 584       if (i == c->n_coeffs && tmp != v)
 585         {
 586           return NULL;
 587         }
 588       return result;
 589     }
 590   return NULL;
 591 }