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