Estimates structural breaks in non-stationary univariate time series.
Synopsis
#include <imsls.h>
int *imsls_f_auto_parm (int nobs, float y[], int *npcs, ..., 0)
The type double function is imsls_d_auto_parm.
Required Arguments
int nobs
(Input)
The number of observations in the time series (y).
float y[]
(Input)
An array of length nobs containing the
time series.
int *npcs
(Input/Output)
The number of requested/estimated pieces or
segments of the time series. npcs is considered
input only when IMSLS_AR_MODEL is
provided.
Return Value
A pointer to an array (arp) of length npcs × 2 containing the break points and AR orders for the derived model. If IMSLS_AR_MODEL is used, the return value is NULL.
|
Column Index |
Description |
|
0 |
Structural break points |
|
1 |
AR order ( |
Synopsis with Optional Arguments
#include <imsls.h>
int
*imsls_f_auto_parm (int
nobs,
float y[],
int
*npcs,
IMSLS_MAX_AR_ORDER,
int max_ar_order,
IMSLS_METHOD,
int method,
IMSLS_MODEL_SELECTION_CRITERION, int criterion,
IMSLS_MAXIMUM_LIKELIHOOD,
int likelihood,
IMSLS_AR_MODEL,
int arp[],
IMSLS_PRINT,
int print,
IMSLS_RANDOM_SEED,
int seed,
IMSLS_PROB_DISTRIBUTION,
float pdistn[],
IMSLS_MIN_OBSERVATIONS,
int mspan[],
IMSLS_GA_PARAMETERS,
float gaparm[],
IMSLS_ISLAND,
int island[],
IMSLS_MAX_MIGRATIONS,
int maxmig,
IMSLS_STOP_ITERATIONS,
int stopiters,
IMSLS_SELECTION_CRITERION_VALUE,
float *value,
IMSLS_AR_FIT,
float **arfit,
IMSLS_AR_FIT_USER,
float arfit[],
IMSLS_AR_STATS,
float **arstat,
IMSLS_AR_STATS_USER,
float arstat[],
0)
Optional Arguments
IMSLS_MAX_AR_ORDER,
int max_ar_order
(Input)
Maximum order to consider for each AR model.
Default: max_ar_order = 20.
IMSLS_METHOD, int method
(Input)
Method of
estimation.
|
method |
Method Used |
|
0 |
Yule –Walker |
|
1 |
Least Squares |
|
2 |
Burg |
Default: method = 0.
IMSLS_MODEL_SELECTION_CRITERION,
int
criterion (Input)
Selection criterion.
|
criterion |
Criterion Used |
|
0 |
Minimum Description Length (MDL) |
|
1 |
Akaike’s Information Criterion (AIC) |
Default: criterion = 0.
IMSLS_MAXIMUM_LIKELIHOOD,
int likelihood
(Input)
Likelihood computation method.
|
likelihood |
Computation Method |
|
0 |
Exact |
|
1 |
Approximate |
Default: likelihood = 0.
IMSLS_AR_MODEL,
int arp[]
(Input)
A user specified array of length npcs × 2
containing the break points and AR orders. When this argument is used, only the
AR parameters and quality of the fit are determined.
|
Column Index |
Description |
|
0 |
Structural break points |
|
1 |
AR
order ( |
IMSLS_PRINT,
int print
(Input)
Printing option.
|
|
Action |
|
0 |
No printing |
|
1 |
Prints final results only |
|
2 |
Prints intermediate and final results |
Default: print = 0.
IMSLS_RANDOM_SEED,
int seed
(Input)
Seed of the random number generator.
For the same data and
parameter settings, imsls_f_auto_parm will return
the same results each time if a seed is set. If
seed = 0,
the system clock will be used to generate a seed. The result will be
nondeterministic.
Default: seed = 0.
Note: The following input arguments are for setting up and running the embedded Genetic Algorithm. In most situations, the default values should be used for these arguments. Users may wish to change some or all for testing or research purposes.
IMSLS_PROB_DISTRIBUTION,
float
pdistn[]
(Input)
Array of length max_ar_order + 1
giving the probability distribution over the AR order variable
p = 0,…, max_ar_order.
i = 0,…, max_ar_order is
used to randomly assign an AR order to breakpoint position for a given
chromosome. pdistn[i] > = 0
and if ∑pdistn
is not equal to 1, the values will be normalized, i.e., pdistn[i] = pdistn[i]/ ∑pdistn.
Default:
pdistn[i] = 1/(max_ar_order + 1)
for all i.
IMSLS_MIN_OBSERVATIONS,
int mspan[]
(Input)
Array of length max_ar_order + 1
containing minimum number of observations required for valid estimates of AR
model with order p = 0, …, max_ar_order.
Default:
mspan
[p] = 2 *(number of
parameters) + 2 = 2 * (p + 2) + 2.
IMSLS_GA_PARAMETERS,
float
gaparm[]
(Input)
Array of length 4 containing parameters that control the
behavior of the genetic algorithm. These values should be strictly greater
than zero and less than one to avoid unexpected results.
|
Index |
Behavior |
|
0 |
Probability used to set initial break points in a chromosome. Default: min (mspan) / nobs. |
|
1 |
Probability of crossover used to decide between a
crossover and a mutation. |
|
2 |
In
the mutation operation, probability an AR(p) model is enforced at
the current position. |
|
3 |
In
the mutation operation, probability a break point is disallowed at the
current position. |
Note: gaparm[2] and gaparm[3] must be valid probabilities and their sum must be between 0 and 1. 1 – gaparm[2] – gaparm[3] is the probability that the chromosome j inherits the parent's chromosome j.
IMSLS_ISLAND,
int island[]
(Input)
Array of length 5 containing the migration policy parameters.
|
Index |
Policy |
|
0 |
Number of islands. |
|
1 |
Number of generations that pass before migration
occurs. Note that the convergence of the algorithm is revised
whether migrations take place or not (see argument island[4]). |
|
2 |
Number of subjects that migrate at each migration
event. |
|
3 |
Population size (number of chromosomes) per
island. |
|
4 |
Migration flag. If 1, migration is
performed. |
IMSLS_MAX_MIGRATIONS,
int
maxmig (Input)
Maximum number of times that migrations may
take place before the function is stopped if convergence has not
occurred.
Default: maxmig = 20.
IMSLS_STOP_ITERATIONS,
int
stopiters (Input)
Number of iterations. The function
will declare convergence and stop the iterations if the criterion value
(MDL/AIC) has not changed after stopiters consecutive
migrations. Otherwise, the algorithm will declare non-convergence and stop
after maxmig
migrations have taken place. See also IMSLS_MAX_MIGRATIONS
and island[1].
Note that logically, stopiters < maxmig.
Default:
stopiters =
10.
IMSLS_SELECTION_CRITERION_VALUE,
float
*value (Output)
Final value of the selection
criterion.
IMSLS_AR_FIT,
float
**arfit
(Output)
Address of a pointer to an internally allocated array of
length npcs × max_ar_order
containing the AR coefficient estimates φ for each segment. arfit[i*max_ar_order+j] is the
j-th
coefficient for segment i where
i = 0, …, npcs - 1
and j = 0, …, arp[i*2 + 1].
Note that the
intercept is not reported.
IMSLS_AR_FIT_USER,
float
arfit[]
(Output)
Storage for array arfit is provided by
the user. If npcs is output, the
user should allocate (nobs - 1) × max_ar_order to assure
sufficient space. See IMSLS_AR_FIT.
IMSLS_AR_STATS,
float
**arstat
(Output)
Address of a pointer to an internally allocated array of
length npcs × 2.
|
Column Index |
Description |
|
0 |
Likelihood values for each of the fitted AR models |
|
1 |
Residual variances for each of the fitted AR models |
IMSLS_AR_STATS_USER,
float arstat[]
(Output)
Storage for array arstat is provided by
the user. If npcs is output, the
user should allocate (nobs - 1) × 2
to assure sufficient space. See IMSLS_AR_STATS.
Description
Function imsls_f_auto_parm estimates the structural breaks of a non-stationary time series using, with permission from the authors, the method developed by Davis et al (2006). imsls_f_auto_parm estimates a partition of the time index and models the time series in each segment as a separate auto-regressive (AR(p)) process. The function returns the estimated breakpoints, the estimated AR(p) models, and supporting statistics.
For the observed time
series 
,
the problem is to find
m, the number of breaks, their locations, 
, and 
, 
, the order of the AR process in
which the j-th segment is
modeled. That is, 
for
(for convenience, 
and
), where
is an AR process of order
and
, the noise sequence, is
independent and identically distributed with mean 0 and variance 1. Note that a
series with m breaks will have m + 1 segments
(m + 1 = npcs).
The vector
completely specifies a
piecewise AR model. To estimate this vector imsls_f_auto_parm
optimizes, with respect to this vector, one of two selection critieria:
the first is a Minimum Description Length (MDL) criterion, and the second
is the Akaike's Information Criterion (AIC). The MDL is defined as
while the AIC criterion is given by
where, given a candidate value of the vector, 
is the likelihood of the fitted
piecewise AR model evaluated at the parameter estimates,
The parameters
of the j--th
AR segment are estimated by the choice of one of three estimation
methods: Yule-Walker, Burg, or
Least Squares.
For simplicity, assume the mean of each series is 0 and that the errors are
Gaussian. Then, the piecewise AR model has Gaussian likelihood
where 
is the
variance-covariance of the j-th AR segment
(of order) and
is the vector of observations
of the j-th segment,
i.e., 
.
To find the minimizer 
of either MDL or AIC, imsls_f_auto_parm employs a Genetic Algorithm with
islands, migration, cross-over and mutations. See Davis et.al. (2006) for
further details.
Remarks
Function imsls_f_auto_parm approximates locally stationary time series by independent auto-regressive processes. Experimental results suggest that imsls_f_auto_parm gives reasonable estimates of the structural breaks of a given time series, even if the segment series are not autoregressive. Also, based on experimental results, MDL gives better results than AIC as a selection criterion.
If seed is set out of range, an informational (error) message is issued indicating that the seed will be reset to 123457. Also if maxmig migrations are reached in the genetic algorithm before the selection criterion value converges an informational message is issued suggesting the increase of maxmig or the use of the double precision function.
Example
The examples below illustrate different scenarios using imsls_f_auto_parm. The example series used in each case is the airline demand data (Box, Jenkins and Reinsel, 1994), which gives monthly total demand for the period January 1949 through December 1960. Each scenario sets the optional argument, seed = 123457.
#include <imsls.h>
#include <stdio.h>
int main()
{
#define N 144
int n=N, npcs=0, iseed=123457, *arp=NULL, iper, iord, nlost;
int maxarorder, *arpnull=NULL, arp2[4]={0,2,59,1};
float x[N], *arfit=NULL, *arstat=NULL, sc, dx[N];
/* get data */
imsls_f_data_sets(4, IMSLS_RETURN_USER, x, 0);
/* Example 1: Use default values */
printf ("Example 1: Use defaults\n\n");
arp = imsls_f_auto_parm(n, x, &npcs,
IMSLS_PRINT, 1,
IMSLS_RANDOM_SEED, iseed,
IMSLS_SELECTION_CRITERION_VALUE, &sc,
IMSLS_AR_FIT, &arfit,
IMSLS_AR_STATS, &arstat,
0);
imsls_free(arp);
imsls_free(arfit);
imsls_free(arstat);
/* Example 2: differenced series set period for the difference.
iper is in years for this data set */
printf ("\n\nExample 2: differenced series\n\n");
iper = 1;
/* set the order for the difference. */
iord = 1;
/* get differenced series dx */
imsls_f_difference(n, x, 1, &iper,
IMSLS_ORDERS, &iord,
IMSLS_LOST, &nlost,
IMSLS_RETURN_USER, dx,
0);
arp = imsls_f_auto_parm(n-nlost, &dx[nlost], &npcs,
IMSLS_PRINT, 1,
IMSLS_RANDOM_SEED, iseed,
IMSLS_SELECTION_CRITERION_VALUE, &sc,
IMSLS_AR_FIT, &arfit,
IMSLS_AR_STATS, &arstat,
0);
imsls_free(arp);
imsls_free(arfit);
imsls_free(arstat);
/* Example 3: original series, lower order allowed
lower maximum AR order */
printf("\n\nExample 3: original series, lower order allowed\n\n");
maxarorder=5;
arp = imsls_f_auto_parm(n, x, &npcs,
IMSLS_MAX_AR_ORDER, maxarorder,
IMSLS_PRINT, 1,
IMSLS_RANDOM_SEED, iseed,
IMSLS_SELECTION_CRITERION_VALUE, &sc,
IMSLS_AR_FIT, &arfit,
IMSLS_AR_STATS, &arstat,
0);
imsls_free(arp);
imsls_free(arfit);
imsls_free(arstat);
/* Example 4: differenced series, lower order allowed */
printf("\n\nExample 4: differenced series, lower order allowed\n\n");
maxarorder=5;
arp = imsls_f_auto_parm(n-nlost, &dx[nlost], &npcs,
IMSLS_MAX_AR_ORDER, maxarorder,
IMSLS_PRINT, 1,
IMSLS_RANDOM_SEED, iseed,
IMSLS_SELECTION_CRITERION_VALUE, &sc,
IMSLS_AR_FIT, &arfit,
IMSLS_AR_STATS, &arstat,
0);
imsls_free(arp);
imsls_free(arfit);
imsls_free(arstat);
/* Example 5: original series, force fit the segments
Fit only at the break points */
printf("\n\nExample 5: original series, force fit the segments\n\n");
npcs=2;
arpnull = imsls_f_auto_parm(n, x, &npcs,
IMSLS_AR_MODEL, arp2,
IMSLS_PRINT, 1,
IMSLS_RANDOM_SEED, iseed,
IMSLS_SELECTION_CRITERION_VALUE, &sc,
IMSLS_AR_FIT, &arfit,
IMSLS_AR_STATS, &arstat,
0);
}
Output
Example 1: Use defaults
============== final results ===============
number of pieces: 2
selection criteria value: 684.243164
total time: 3.203000 conv: 1
==================== final model estimates =====================
break point order est. coeff. likelihood resid. var
arp[ 0] arp[ 1] arfit[ 0- 0] arstat[ 0] arstat[ 1]
0 1 0.77542
186.945 355.025
arp[ 2] arp[ 3] arfit[20-32] arstat[ 2] arstat[ 3]
43 13 1.03700
-0.07801
-0.03891
-0.03452
0.11961
-0.12851
0.01990
-0.04885
0.08089
-0.13117
0.22122
0.53862
-0.61515
486.666 691.486
Example 2: differenced series
============== final results ===============
number of pieces: 1
selection criteria value: 624.283508
total time: 3.031000 conv: 1
==================== final model estimates =====================
break point order est. coeff. likelihood resid. var
arp[ 0] arp[ 1] arfit[ 0-11] arstat[ 0] arstat[ 1]
0 12 -0.02842
-0.22436
-0.16846
-0.24267
-0.10573
-0.22429
-0.12126
-0.26446
-0.07087
-0.24327
-0.07136
0.57129
619.321 297.352
Example 3: original series, lower order allowed
============== final results ===============
number of pieces: 2
selection criteria value: 705.296631
total time: 2.312000 conv: 1
==================== final model estimates =====================
break point order est. coeff. likelihood resid. var
arp[ 0] arp[ 1] arfit[ 0- 0] arstat[ 0] arstat[ 1]
0 1 0.89533
270.393 333.563
arp[ 2] arp[ 3] arfit[ 5- 6] arstat[ 2] arstat[ 3]
62 2 1.19788
-0.35922
424.270 1632.335
Example 4: differenced series, lower order allowed
============== final results ===============
number of pieces: 2
selection criteria value: 698.359497
total time: 2.219000 conv: 1
==================== final model estimates =====================
break point order est. coeff. likelihood resid. var
arp[ 0] arp[ 1] arfit[ 0- 0] arstat[ 0] arstat[ 1]
0 0 -------
335.565 357.388
arp[ 2] arp[ 3] arfit[ 5- 5] arstat[ 2] arstat[ 3]
76 1 0.33310
352.175 1786.345
Example 5: original series, force fit the segments
============== final results ===============
number of pieces: 2
selection criteria value: 712.521
==================== final model estimates =====================
break point order est. coeff. likelihood resid. var
arp[ 0] arp[ 1] arfit[ 0- 1] arstat[ 0] arstat[ 1]
0 2 1.12156
-0.24876
258.192 313.889
arp[ 2] arp[ 3] arfit[20-20] arstat[ 2] arstat[ 3]
59 1 0.88605
443.696 1937.633
Warning Errors
|
IMSLS_MAX_MIGRATIONS_EXCEEDED |
“maxmig” migrations or “stopiters” iterations were reached in the genetic algorithm before the selection criterion value converged. Try increasing “maxmig”, “stopiters” or using the double precision routine. |
