src/math/ts/innovations.c

   1 /*
   2   src/math/ts/innovations.c
   3
   4   Copyright (C) 2006 Free Software Foundation, Inc. Written by Jason H. Stover.
   5
   6   This program is free software; you can redistribute it and/or modify it under
   7   the terms of the GNU General Public License as published by the Free
   8   Software Foundation; either version 2 of the License, or (at your option)
   9   any later version.
  10
  11   This program is distributed in the hope that it will be useful, but WITHOUT
  12   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14   more details.
  15
  16   You should have received a copy of the GNU General Public License along with
  17   this program; if not, write to the Free Software Foundation, Inc., 51
  18   Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
  19  */
  20 /*
  21   Find preliminary ARMA coefficients via the innovations algorithm.
  22   Also compute the sample mean and covariance matrix for each series.
  23
  24   Reference:
  25
  26   P. J. Brockwell and R. A. Davis. Time Series: Theory and
  27   Methods. Second edition. Springer. New York. 1991. ISBN
  28   0-387-97429-6. Sections 5.2, 8.3 and 8.4.
  29  */
  30
  31 #include <gsl/gsl_matrix.h>
  32 #include <gsl/gsl_vector.h>
  33 #include <math.h>
  34 #include <stdlib.h>
  35 #include <data/case.h>
  36 #include <data/casefile.h>
  37 #include <libpspp/alloc.h>
  38 #include <libpspp/compiler.h>
  39 #include <libpspp/message.h>
  40 #include <math/coefficient.h>
  41 #include <math/ts/innovations.h>
  42
  43 static void
  44 get_mean_variance (size_t n_vars, const struct casefile *cf,
  45                    struct innovations_estimate **est)
  46
  47 {
  48   struct casereader *r;
  49   struct ccase c;
  50   size_t n;
  51   double d;
  52   const union value *tmp;
  53
  54   for (n = 0; n < n_vars; n++)
  55     {
  56       est[n]->n_obs = 2.0;
  57       est[n]->mean = 0.0;
  58       est[n]->variance = 0.0;
  59     }
  60   for (r = casefile_get_reader (cf); casereader_read (r, &c);
  61        case_destroy (&c))
  62     {
  63       for (n = 0; n < n_vars; n++)
  64         {
  65           tmp = case_data (&c, est[n]->variable->fv);
  66           if (!mv_is_value_missing (&(est[n]->variable->miss), tmp))
  67             {
  68               d = (tmp->f - est[n]->mean) / est[n]->n_obs;
  69               est[n]->mean += d;
  70               est[n]->variance += est[n]->n_obs * est[n]->n_obs * d * d;
  71               est[n]->n_obs += 1.0;
  72             }
  73         }
  74     }
  75   for (n = 0; n < n_vars; n++)
  76     {
  77       /* Maximum likelihood estimate of the variance. */
  78       est[n]->variance /= est[n]->n_obs;
  79     }
  80 }
  81
  82 /*
  83   Read the first MAX_LAG cases.
  84  */
  85 static bool
  86 innovations_init_cases (struct casereader *r, struct ccase **c, size_t max_lag)
  87 {
  88   bool value = true;
  89   size_t lag = 0;
  90
  91   while (value && lag < max_lag)
  92     {
  93       lag++;
  94       value = casereader_read (r, c[lag]);
  95     }
  96   return value;
  97 }
  98
  99 /*
 100   Read one case and update C, which contains the last MAX_LAG cases.
 101  */
 102 static bool
 103 innovations_update_cases (struct casereader *r, struct ccase **c, size_t max_lag)
 104 {
 105   size_t lag;
 106   bool value = false;
 107
 108   for (lag = 0; lag < max_lag - 1; lag++)
 109     {
 110       c[lag] = c[lag+1];
 111     }
 112   value = casereader_read (r, c[lag]);
 113   return value;
 114 }
 115 static void
 116 get_covariance (size_t n_vars, const struct casefile *cf,
 117                 struct innovations_estimate **est, size_t max_lag)
 118 {
 119   struct casereader *r;
 120   struct ccase **c;
 121   size_t lag;
 122   size_t n;
 123   bool read_case = false;
 124   double d;
 125   double x;
 126   const union value *tmp;
 127   const union value *tmp2;
 128
 129   c = xnmalloc (max_lag, sizeof (*c));
 130
 131   for (lag = 0; lag < max_lag; lag++)
 132     {
 133       c[lag] = xmalloc (sizeof *c[lag]);
 134     }
 135
 136   r = casefile_get_reader (cf);
 137   read_case = innovations_init_cases (r, c, max_lag);
 138
 139   while (read_case)
 140     {
 141       for (n = 0; n < n_vars; n++)
 142         {
 143           tmp2 = case_data (c[0], est[n]->variable->fv);
 144           if (!mv_is_value_missing (&est[n]->variable->miss, tmp2))
 145             {
 146               x = tmp2->f - est[n]->mean;
 147               for (lag = 1; lag <= max_lag; lag++)
 148                 {
 149                   tmp = case_data (c[lag], est[n]->variable->fv);
 150                   if (!mv_is_value_missing (&est[n]->variable->miss, tmp))
 151                     {
 152                       d = (tmp->f - est[n]->mean);
 153                       *(est[n]->cov + lag) += d * x;
 154                     }
 155                 }
 156             }
 157         }
 158       read_case = innovations_update_cases (r, c, max_lag);
 159     }
 160   for (lag = 0; lag <= max_lag; lag++)
 161     {
 162       for (n = 0; n < n_vars; n++)
 163         {
 164           *(est[n]->cov + lag) /= (est[n]->n_obs - lag);
 165         }
 166     }
 167   for (lag = 0; lag < max_lag; lag++)
 168     {
 169       free (c[lag]);
 170     }
 171   free (c);
 172 }
 173 static double
 174 innovations_convolve (double **theta, struct innovations_estimate *est,
 175                       int i, int j)
 176 {
 177   int k;
 178   double result = 0.0;
 179
 180   for (k = 0; k < i; k++)
 181     {
 182       result += theta[i-1][i-k-1] * theta[j-1][j-k-1] * est->scale[k];
 183     }
 184   return result;
 185 }
 186 static void
 187 innovations_update_scale (struct innovations_estimate *est, double *theta,
 188                           size_t i)
 189 {
 190   double result = 0.0;
 191   size_t j;
 192   size_t k;
 193
 194
 195   result = est->cov[0];
 196   for (j = 0; j < i; j++)
 197     {
 198       k = i - j;
 199       result -= theta[k] * theta[k] * est->scale[j];
 200     }
 201   est->scale[i] = result;
 202 }
 203
 204 static void
 205 get_coef (size_t n_vars, const struct casefile *cf,
 206                 struct innovations_estimate **est, size_t max_lag)
 207 {
 208   size_t j;
 209   size_t i;
 210   size_t k;
 211   size_t n;
 212   double v;
 213   double **theta;
 214
 215   theta = xnmalloc (max_lag, sizeof (*theta));
 216   for (i = 0; i < max_lag; i++)
 217     {
 218       theta[i] = xnmalloc (i+1, sizeof (theta[i]));
 219
 220     }
 221   for (n = 0; n < n_vars; n++)
 222     {
 223       for (i = 0; i < max_lag; i++)
 224         {
 225           for (j = 0; j < i; j++)
 226             {
 227               theta[i][j] = 0.0;
 228             }
 229         }
 230       innovations_update_scale (est[n], theta[0], 0);
 231       for (i = 0; i < max_lag; i++)
 232         {
 233           v = est[n]->cov[i];
 234           for (j = 0; j < i; j++)
 235             {
 236               k = i - j;
 237               theta[i-1][k-1] = est[n]->cov[k] -
 238                 innovations_convolve (theta, est[n], i, j);
 239             }
 240           innovations_update_scale (est[n], theta[i], i);
 241         }
 242       /* Copy the final row of coefficients into EST->COEFF.*/
 243       for (i = 0; i < max_lag; i++)
 244         {
 245           /*
 246             The order of storage here means that the best predicted value
 247             for the time series is computed as follows:
 248
 249             Let X[m], X[m-1],... denote the original series.
 250             Let X_hat[0] denote the best predicted value of X[0],
 251             X_hat[1] denote the projection of X[1] onto the subspace
 252             spanned by {X[0] - X_hat[0]}. Let X_hat[m] denote the
 253             projection of X[m] onto the subspace spanned by {X[m-1] - X_hat[m-1],
 254             X[m-2] - X_hat[m-2],...,X[0] - X_hat[0]}.
 255
 256             Then X_hat[m] = est->coeff[m-1] * (X[m-1] - X_hat[m-1])
 257                           + est->coeff[m-1] * (X[m-2] - X_hat[m-2])
 258                           ...
 259                           + est->coeff[m-max_lag] * (X[m - max_lag] - X_hat[m - max_lag])
 260
 261             (That is what X_hat[m] SHOULD be, anyway. These routines need
 262             to be tested.)
 263            */
 264           pspp_coeff_set_estimate (est[n]->coeff[i], theta[max_lag - 1][i]);
 265         }
 266     }
 267   for (i = 0; i < max_lag; i++)
 268     {
 269       free (theta[i]);
 270     }
 271   free (theta);
 272 }
 273
 274 struct innovations_estimate **
 275 pspp_innovations (const struct variable **vars,
 276                   size_t *n_vars,
 277                   size_t lag,
 278                   const struct casefile *cf)
 279 {
 280   struct innovations_estimate **est;
 281   size_t i;
 282   size_t j;
 283
 284   est = xnmalloc (*n_vars, sizeof *est);
 285   for (i = 0; i < *n_vars; i++)
 286     {
 287       if (vars[i]->type == NUMERIC)
 288         {
 289           est[i] = xmalloc (sizeof **est);
 290           est[i]->variable = vars[i];
 291           est[i]->mean = 0.0;
 292           est[i]->variance = 0.0;
 293           est[i]->cov = xnmalloc (lag, sizeof (*est[i]->cov));
 294           est[i]->scale = xnmalloc (lag, sizeof (*est[i]->scale));
 295           est[i]->coeff = xnmalloc (lag, sizeof (*est[i]->coeff));
 296           for (j = 0; j < lag; j++)
 297             {
 298               est[i]->coeff[j] = xmalloc (sizeof (*(est[i]->coeff + j)));
 299             }
 300         }
 301       else
 302         {
 303           *n_vars--;
 304 /*        msg (MW, _("Cannot compute autocovariance for a non-numeric variable %s"), */
 305 /*                   var_to_string (vars[i])); */
 306         }
 307     }
 308
 309   get_mean_variance (*n_vars, cf, est);
 310   get_covariance (*n_vars, cf, est, lag);
 311   get_coef (*n_vars, cf, est, lag);
 312
 313   return est;
 314 }