src/math/linreg/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_fit.h>
  19 #include <gsl/gsl_multifit.h>
  20
  21 #include <gsl/gsl_blas.h>
  22 #include <gsl/gsl_cblas.h>
  23
  24
  25
  26 /*
  27   Find the least-squares estimate of b for the linear model:
  28
  29   Y = Xb + Z
  30
  31   where Y is an n-by-1 column vector, X is an n-by-p matrix of
  32   independent variables, b is a p-by-1 vector of regression coefficients,
  33   and Z is an n-by-1 normally-distributed random vector with independent
  34   identically distributed components with mean 0.
  35
  36   This estimate is found via the sweep operator or singular-value
  37   decomposition with gsl.
  38
  39
  40   References:
  41
  42   1. Matrix Computations, third edition. GH Golub and CF Van Loan.
  43   The Johns Hopkins University Press. 1996. ISBN 0-8018-5414-8.
  44
  45   2. Numerical Analysis for Statisticians. K Lange. Springer. 1999.
  46   ISBN 0-387-94979-8.
  47
  48   3. Numerical Linear Algebra for Applications in Statistics. JE Gentle.
  49   Springer. 1998. ISBN 0-387-98542-5.
  50 */
  51
  52 #include <math/linreg/linreg.h>
  53 #include <math/coefficient.h>
  54 #include <gsl/gsl_errno.h>
  55 #include <linreg/sweep.h>
  56 /*
  57   Get the mean and standard deviation of a vector
  58   of doubles via a form of the Kalman filter as
  59   described on page 32 of [3].
  60  */
  61 static int
  62 linreg_mean_std (gsl_vector_const_view v, double *mp, double *sp, double *ssp)
  63 {
  64   size_t i;
  65   double j = 0.0;
  66   double d;
  67   double tmp;
  68   double mean;
  69   double variance;
  70
  71   mean = gsl_vector_get (&v.vector, 0);
  72   variance = 0;
  73   for (i = 1; i < v.vector.size; i++)
  74     {
  75       j = (double) i + 1.0;
  76       tmp = gsl_vector_get (&v.vector, i);
  77       d = (tmp - mean) / j;
  78       mean += d;
  79       variance += j * (j - 1.0) * d * d;
  80     }
  81   *mp = mean;
  82   *sp = sqrt (variance / (j - 1.0));
  83   *ssp = variance;
  84
  85   return GSL_SUCCESS;
  86 }
  87
  88 /*
  89   Set V to contain an array of pointers to the variables
  90   used in the model. V must be at least C->N_COEFFS in length.
  91   The return value is the number of distinct variables found.
  92  */
  93 int
  94 pspp_linreg_get_vars (const void *c_, const struct variable **v)
  95 {
  96   const pspp_linreg_cache *c = c_;
  97   struct pspp_coeff *coef = NULL;
  98   const struct variable *tmp;
  99   int i;
 100   int result = 0;
 101
 102   /*
 103      Make sure the caller doesn't try to sneak a variable
 104      into V that is not in the model.
 105    */
 106   for (i = 0; i < c->n_coeffs; i++)
 107     {
 108       v[i] = NULL;
 109     }
 110   /*
 111      Start at c->coeff[1] to avoid the intercept.
 112    */
 113   v[result] = pspp_coeff_get_var (c->coeff[1], 0);
 114   result = (v[result] == NULL) ? 0 : 1;
 115
 116   for (coef = c->coeff[2]; coef < c->coeff[c->n_coeffs]; coef++)
 117     {
 118       tmp = pspp_coeff_get_var (coef, 0);
 119       assert (tmp != NULL);
 120       /* Repeated variables are likely to bunch together, at the end
 121          of the array. */
 122       i = result - 1;
 123       while (i >= 0 && v[i] != tmp)
 124         {
 125           i--;
 126         }
 127       if (i < 0 && result < c->n_coeffs)
 128         {
 129           v[result] = tmp;
 130           result++;
 131         }
 132     }
 133   return result;
 134 }
 135
 136 /*
 137   Allocate a pspp_linreg_cache and return a pointer
 138   to it. n is the number of cases, p is the number of
 139   independent variables.
 140  */
 141 pspp_linreg_cache *
 142 pspp_linreg_cache_alloc (size_t n, size_t p)
 143 {
 144   pspp_linreg_cache *c;
 145
 146   c = (pspp_linreg_cache *) malloc (sizeof (pspp_linreg_cache));
 147   c->depvar = NULL;
 148   c->indep_means = gsl_vector_alloc (p);
 149   c->indep_std = gsl_vector_alloc (p);
 150   c->ssx = gsl_vector_alloc (p);        /* Sums of squares for the
 151                                            independent variables.
 152                                          */
 153   c->ss_indeps = gsl_vector_alloc (p);  /* Sums of squares for the
 154                                            model parameters.
 155                                          */
 156   c->cov = gsl_matrix_alloc (p + 1, p + 1);     /* Covariance matrix. */
 157   c->n_obs = n;
 158   c->n_indeps = p;
 159   /*
 160      Default settings.
 161    */
 162   c->method = PSPP_LINREG_SWEEP;
 163   c->predict = pspp_linreg_predict;
 164   c->residual = pspp_linreg_residual;   /* The procedure to compute my
 165                                            residuals. */
 166   c->get_vars = pspp_linreg_get_vars;   /* The procedure that returns
 167                                            pointers to model
 168                                            variables. */
 169   c->resid = NULL;              /* The variable storing my residuals. */
 170   c->pred = NULL;               /* The variable storing my predicted values. */
 171
 172   return c;
 173 }
 174
 175 bool
 176 pspp_linreg_cache_free (void *m)
 177 {
 178   int i;
 179
 180   pspp_linreg_cache *c = m;
 181   if (c != NULL)
 182     {
 183       gsl_vector_free (c->indep_means);
 184       gsl_vector_free (c->indep_std);
 185       gsl_vector_free (c->ss_indeps);
 186       gsl_matrix_free (c->cov);
 187       gsl_vector_free (c->ssx);
 188       for (i = 0; i < c->n_coeffs; i++)
 189         {
 190           pspp_coeff_free (c->coeff[i]);
 191         }
 192       free (c->coeff);
 193       free (c);
 194     }
 195   return true;
 196 }
 197
 198 /*
 199   Fit the linear model via least squares. All pointers passed to pspp_linreg
 200   are assumed to be allocated to the correct size and initialized to the
 201   values as indicated by opts.
 202  */
 203 int
 204 pspp_linreg (const gsl_vector * Y, const gsl_matrix * X,
 205              const pspp_linreg_opts * opts, pspp_linreg_cache * cache)
 206 {
 207   int rc;
 208   gsl_matrix *design = NULL;
 209   gsl_matrix_view xtx;
 210   gsl_matrix_view xm;
 211   gsl_matrix_view xmxtx;
 212   gsl_vector_view xty;
 213   gsl_vector_view xi;
 214   gsl_vector_view xj;
 215   gsl_vector *param_estimates;
 216
 217   size_t i;
 218   size_t j;
 219   double tmp;
 220   double m;
 221   double s;
 222   double ss;
 223
 224   if (cache == NULL)
 225     {
 226       return GSL_EFAULT;
 227     }
 228   if (opts->get_depvar_mean_std)
 229     {
 230       linreg_mean_std (gsl_vector_const_subvector (Y, 0, Y->size),
 231                        &m, &s, &ss);
 232       cache->depvar_mean = m;
 233       cache->depvar_std = s;
 234       cache->sst = ss;
 235     }
 236   for (i = 0; i < cache->n_indeps; i++)
 237     {
 238       if (opts->get_indep_mean_std[i])
 239         {
 240           linreg_mean_std (gsl_matrix_const_column (X, i), &m, &s, &ss);
 241           gsl_vector_set (cache->indep_means, i, m);
 242           gsl_vector_set (cache->indep_std, i, s);
 243           gsl_vector_set (cache->ssx, i, ss);
 244         }
 245     }
 246   cache->dft = cache->n_obs - 1;
 247   cache->dfm = cache->n_indeps;
 248   cache->dfe = cache->dft - cache->dfm;
 249   cache->n_coeffs = X->size2 + 1;       /* Adjust this later to allow for
 250                                            regression through the origin.
 251                                          */
 252   if (cache->method == PSPP_LINREG_SWEEP)
 253     {
 254       gsl_matrix *sw;
 255       /*
 256          Subtract the means to improve the condition of the design
 257          matrix. This requires copying X and Y. We do not divide by the
 258          standard deviations of the independent variables here since doing
 259          so would cause a miscalculation of the residual sums of
 260          squares. Dividing by the standard deviation is done GSL's linear
 261          regression functions, so if the design matrix has a poor
 262          condition, use QR decomposition.
 263
 264          The design matrix here does not include a column for the intercept
 265          (i.e., a column of 1's). If using PSPP_LINREG_QR, we need that column,
 266          so design is allocated here when sweeping, or below if using QR.
 267        */
 268       design = gsl_matrix_alloc (X->size1, X->size2);
 269       for (i = 0; i < X->size2; i++)
 270         {
 271           m = gsl_vector_get (cache->indep_means, i);
 272           for (j = 0; j < X->size1; j++)
 273             {
 274               tmp = (gsl_matrix_get (X, j, i) - m);
 275               gsl_matrix_set (design, j, i, tmp);
 276             }
 277         }
 278       sw = gsl_matrix_calloc (cache->n_indeps + 1, cache->n_indeps + 1);
 279       xtx = gsl_matrix_submatrix (sw, 0, 0, cache->n_indeps, cache->n_indeps);
 280
 281       for (i = 0; i < xtx.matrix.size1; i++)
 282         {
 283           tmp = gsl_vector_get (cache->ssx, i);
 284           gsl_matrix_set (&(xtx.matrix), i, i, tmp);
 285           xi = gsl_matrix_column (design, i);
 286           for (j = (i + 1); j < xtx.matrix.size2; j++)
 287             {
 288               xj = gsl_matrix_column (design, j);
 289               gsl_blas_ddot (&(xi.vector), &(xj.vector), &tmp);
 290               gsl_matrix_set (&(xtx.matrix), i, j, tmp);
 291             }
 292         }
 293
 294       gsl_matrix_set (sw, cache->n_indeps, cache->n_indeps, cache->sst);
 295       xty = gsl_matrix_column (sw, cache->n_indeps);
 296       /*
 297          This loop starts at 1, with i=0 outside the loop, so we can get
 298          the model sum of squares due to the first independent variable.
 299        */
 300       xi = gsl_matrix_column (design, 0);
 301       gsl_blas_ddot (&(xi.vector), Y, &tmp);
 302       gsl_vector_set (&(xty.vector), 0, tmp);
 303       tmp *= tmp / gsl_vector_get (cache->ssx, 0);
 304       gsl_vector_set (cache->ss_indeps, 0, tmp);
 305       for (i = 1; i < cache->n_indeps; i++)
 306         {
 307           xi = gsl_matrix_column (design, i);
 308           gsl_blas_ddot (&(xi.vector), Y, &tmp);
 309           gsl_vector_set (&(xty.vector), i, tmp);
 310         }
 311
 312       /*
 313          Sweep on the matrix sw, which contains XtX, XtY and YtY.
 314        */
 315       reg_sweep (sw);
 316       cache->sse = gsl_matrix_get (sw, cache->n_indeps, cache->n_indeps);
 317       cache->mse = cache->sse / cache->dfe;
 318       /*
 319          Get the intercept.
 320        */
 321       m = cache->depvar_mean;
 322       for (i = 0; i < cache->n_indeps; i++)
 323         {
 324           tmp = gsl_matrix_get (sw, i, cache->n_indeps);
 325           cache->coeff[i + 1]->estimate = tmp;
 326           m -= tmp * gsl_vector_get (cache->indep_means, i);
 327         }
 328       /*
 329          Get the covariance matrix of the parameter estimates.
 330          Only the upper triangle is necessary.
 331        */
 332
 333       /*
 334          The loops below do not compute the entries related
 335          to the estimated intercept.
 336        */
 337       for (i = 0; i < cache->n_indeps; i++)
 338         for (j = i; j < cache->n_indeps; j++)
 339           {
 340             tmp = -1.0 * cache->mse * gsl_matrix_get (sw, i, j);
 341             gsl_matrix_set (cache->cov, i + 1, j + 1, tmp);
 342           }
 343       /*
 344          Get the covariances related to the intercept.
 345        */
 346       xtx = gsl_matrix_submatrix (sw, 0, 0, cache->n_indeps, cache->n_indeps);
 347       xmxtx = gsl_matrix_submatrix (cache->cov, 0, 1, 1, cache->n_indeps);
 348       xm = gsl_matrix_view_vector (cache->indep_means, 1, cache->n_indeps);
 349       rc = gsl_blas_dsymm (CblasRight, CblasUpper, cache->mse,
 350                            &xtx.matrix, &xm.matrix, 0.0, &xmxtx.matrix);
 351       if (rc == GSL_SUCCESS)
 352         {
 353           tmp = cache->mse / cache->n_obs;
 354           for (i = 1; i < 1 + cache->n_indeps; i++)
 355             {
 356               tmp -= gsl_matrix_get (cache->cov, 0, i)
 357                 * gsl_vector_get (cache->indep_means, i - 1);
 358             }
 359           gsl_matrix_set (cache->cov, 0, 0, tmp);
 360
 361           cache->coeff[0]->estimate = m;
 362         }
 363       else
 364         {
 365           fprintf (stderr, "%s:%d:gsl_blas_dsymm: %s\n",
 366                    __FILE__, __LINE__, gsl_strerror (rc));
 367           exit (rc);
 368         }
 369       gsl_matrix_free (sw);
 370     }
 371   else if (cache->method == PSPP_LINREG_CONDITIONAL_INVERSE)
 372     {
 373       /*
 374         Use the SVD of X^T X to find a conditional inverse of X^TX. If
 375         the SVD is X^T X = U D V^T, then set the conditional inverse
 376         to (X^T X)^c = V D^- U^T. D^- is defined as follows: If entry
 377         (i, i) has value sigma_i, then entry (i, i) of D^- is 1 /
 378         sigma_i if sigma_i > 0, and 0 otherwise. Then solve the normal
 379         equations by setting the estimated parameter vector to
 380         (X^TX)^c X^T Y.
 381        */
 382     }
 383   else
 384     {
 385       gsl_multifit_linear_workspace *wk;
 386       /*
 387          Use QR decomposition via GSL.
 388        */
 389
 390       param_estimates = gsl_vector_alloc (1 + X->size2);
 391       design = gsl_matrix_alloc (X->size1, 1 + X->size2);
 392
 393       for (j = 0; j < X->size1; j++)
 394         {
 395           gsl_matrix_set (design, j, 0, 1.0);
 396           for (i = 0; i < X->size2; i++)
 397             {
 398               tmp = gsl_matrix_get (X, j, i);
 399               gsl_matrix_set (design, j, i + 1, tmp);
 400             }
 401         }
 402
 403       wk = gsl_multifit_linear_alloc (design->size1, design->size2);
 404       rc = gsl_multifit_linear (design, Y, param_estimates,
 405                                 cache->cov, &(cache->sse), wk);
 406       for (i = 0; i < cache->n_coeffs; i++)
 407         {
 408           cache->coeff[i]->estimate = gsl_vector_get (param_estimates, i);
 409         }
 410       if (rc == GSL_SUCCESS)
 411         {
 412           gsl_multifit_linear_free (wk);
 413           gsl_vector_free (param_estimates);
 414         }
 415       else
 416         {
 417           fprintf (stderr, "%s:%d: gsl_multifit_linear returned %d\n",
 418                    __FILE__, __LINE__, rc);
 419         }
 420     }
 421
 422
 423   cache->ssm = cache->sst - cache->sse;
 424   /*
 425      Get the remaining sums of squares for the independent
 426      variables.
 427    */
 428   m = 0;
 429   for (i = 1; i < cache->n_indeps; i++)
 430     {
 431       j = i - 1;
 432       m += gsl_vector_get (cache->ss_indeps, j);
 433       tmp = cache->ssm - m;
 434       gsl_vector_set (cache->ss_indeps, i, tmp);
 435     }
 436
 437   gsl_matrix_free (design);
 438   return GSL_SUCCESS;
 439 }