3 Data Structures

Statistics and bounded rationality¶

Statistics studies methods of making inferences and decisions when we aren’t sure what is happening. For economists, statistics has long been the place to go prospecting for hypotheses to understand how people behave under conditions of uncertainty and ignorance. It must be our starting place, because we propose to make our agents even more like statisticians or econometricians than they are in rational expectations models.

The purpose of this chapter is to review the workings of that centerpiece of econometrics, least squares regression, and how in many contexts it can be implemented recursively. This review will set the stage for the following chapter on neural networks and artificial intelligence, material that is less familiar to most economists, but which we shall see just implements recursive least squares in various ingenious contexts. In this chapter and the next we shall be looking for devices to hand over to the boundedly rational agents that will be created in Chapter 5.

Representation and estimation¶

From statistics, economists have borrowed and adapted a set of methods for describing and interpreting relationships within data sets. The task of description has fruitfully been subdivided into two logically distinct but interrelated pieces: representation and estimation. Representation of a relationship means positing a mathematical model that is assumed to have generated the data.

Usually, the data are taken to be a random sample drawn from a particular probability distribution, and the task of representation is to select a tractable model describing that probability distribution, typically in terms of a small number of parameters. The mathematical model chosen to represent the data is sometimes called the ‘data generating mechanism.’ The job of representation is ‘purely mathematical’ and in itself involves no use of statistical inference. Statistical methods are used to estimate the free parameters of the mathematical model, on the basis of the data set under study.

This chapter briefly describes some of the data-generating mechanisms that economists widely use, and also the sorts of procedures that they use to estimate the parameters of those models. My purpose is to convey the flavor of these data-generating mechanisms and statistical procedures, and to set the stage for our subsequent comparisons with neural networks.^[1]

Two versions of the linear regression model¶

Population version¶

Linear regression, a pillar of econometrics, is a tool for summarizing the linear structure of a vector of random variables. We have a probability distribution function $F(y_t, x_t)$ for $(y_t, x_t)$ where $y_t$ is a scalar and $x_t$ is a $k \times 1$ vector. We assume that the probability distribution has well defined first and second moments. We want to represent the probability distribution in the form

where $\beta' x_t$ approximates $y_t$ in the sense that $e_t = y_t - \beta' x_t$ is as small as possible in the mean square norm $Ee_t^2$, where $E$ is the mathematical expectation. The object is to select $\beta$ to minimize $V(\beta) = 0.5 Ee_t^2 = 0.5 E(y_t - \beta' x_t)^2$.

The first-order condition for minimization of $V(\beta)$ is $V'(\beta) = 0$, where $V'(\beta) = Ex_t(y_t - x_t'\beta)$. Thus, the (population) least squares $\beta$ satisfies the orthogonality condition

or

Notice that the population least squares regression coefficients $\beta$ is a mathematical object defined in terms of the population second moments of the distribution $F(y_t, x_t)$. By virtue of the orthogonality condition (2), because $e_t = y_t - x_t'\beta$, the least squares regression represents $y_t$ as the sum of a linear function of $x_t$ and a piece $e_t$ that is orthogonal to $x_t$.

The sample version¶

We have a sample of observations $\{y_t, x_t\}$, drawn from the distribution $F(y_t, x_t)$. Everything that we know about the moments of $F(y_t, x_t)$ is contained in the sample $\{y_t, x_t\}_{t=1}^T$. From these data, we want to estimate the unknown value of $\beta$ in the model

We can accomplish this by replacing expectations with sample means in formula (3); namely, we use

This is ‘ordinary least squares.’

Vector autoregressions¶

Following the advice of Sims (1980), macroeconomists often use systems of linear regressions, with one equation for each variable being studied, to represent the dynamics within a collection of economic time series. Each variable is regressed against lagged values of itself and all of the other variables in the model.

Let $z_t$ be an $(n \times 1)$ covariance stationary stochastic process (i.e., one for which the vector of means $Ez_t$ is independent of time and the matrix covariances $C_z(k) = Ez_t z_{t-k}'$ are well defined and independent of calendar time $t$). For convenience, assume that $Ez_t = 0$. Under particular conditions, such a process has the autoregressive representation

where $\epsilon_t$ is an $(n \times 1)$ vector of least squares residuals or ‘innovations’ that satisfies the extensive orthogonality conditions

This model is called a vector autoregression. The force of the extensive orthogonality conditions in the last equation is to decompose $z_t$ into a piece $\sum_{j=1}^{\infty} A_j z_{t-j}$, which is linearly predictable from past values of the vector process itself, and a part $\epsilon_t$, which cannot be predicted linearly from past $z$’s (i.e., it is orthogonal to each element of past $z$’s). The matrices of autoregressive coefficients $A_j$ are determined by the normal equations

which are equivalent with the least squares orthogonality conditions.

The vector autoregressive representation is a workhorse. Following the lead of Sims and Litterman, it is often used to represent systems of interrelated time series for the purposes of describing their dynamic structure and forecasting them. In constructing our models of economic agents, economists often describe their beliefs about the dynamics of the environment in terms of a vector autoregression. We use vector autoregressions to formulate our own forecasting problems, and often model economic actors as doing the same.

Estimation of vector autoregressions¶

If enough data were available, vector autoregressions could be well estimated by applying ordinary least squares, equation by equation. But economists usually don’t have enough data to use ordinary least squares, so Sims and Litterman have shown how to use modified versions of least squares. I postpone discussing why in practice they deviate from using ordinary least squares in its unadulterated form.

Stochastic approximation¶

Robbins and Monro (1951) considered the problem of finding a value of a vector $\alpha$ that solves the equation

where $Q$ is a function that is decreasing in $\alpha$, and $\{z_t\}$ is a sequence of vectors of random variables $z_t$ drawn from some sequence of probability distributions $F_t(z^t)$ where $z^t = \{z_t, z_{t-1}, \ldots, z_0\}$. It is assumed that

• (a) either a sample $\{z_t\}_{t=1}^{\infty}$ has been generated by ‘nature,’ or one can be generated by simulation; or

• (b) the function $Q(z_t, \alpha)$ can be evaluated for the generated $z_t$ and any admissible candidate $\alpha$.

The stochastic approximation algorithm for computing a sequence of estimates $\alpha_t$ of the value $\alpha^*$ that solves (9) is

where $\{\gamma_t\}$ is a nonincreasing sequence of positive numbers satisfying

Robbins and Monro (1951) and their followers described conditions under which

where $\alpha^*$ solves either $EQ(z_t, \alpha^*) = 0$ (in the case that $\{z_t\}$ is drawn from a distribution that is stationary) or $\lim_{t \to \infty} EQ(z_t, \alpha^*) = 0$ (in the case that $\{z_t\}$ is asymptotically stationary).^[2]

It has been discovered that the limiting behavior of a sequence $\{\alpha_t\}$ determined by stochastic difference equation (10) is described by an associated differential equation,

where $EQ(z, \alpha)$ is the expected value of $Q(z, \alpha)$, evaluated with respect to the asymptotic stationary distribution of $\{z_t\}$.

A heuristic justification for (13) notes that for large values of $t$ algorithm (10) is approximated by

where replacing $Q(z_t, \alpha_{t-1})$ in (10) with an expected value at a fixed $\alpha$, namely, $E(Q(z, \alpha))$, is justified by observing that, for large $t$, $\alpha_t \approx \alpha_{t-1}$, and that the randomness in $z$ will make its variation large relative to the variation in $\alpha_t$. Use the time transformation $\tau(t) = \log(t)$ to write this differential equation as

which is the ordinary differential equation (13) to be used to approximate the limiting behavior of $\alpha_t$ in (10).

A recursive formulation of the least squares estimate of the mean $Ez_t = \mu$ provides a simple example of stochastic approximation. The least squares estimate is the sample mean $\bar{z}_t = (1/t) \sum_{s=1}^t z_s$. Subtracting the sample mean at $t-1$ from both sides of this formula and rearranging gives

which is in the form of (10) with the ‘gain’ $\gamma_t = 1/t$. The usual initial condition for this equation is $\bar{z}_0 = 0$.^[3],^[4]

Recursive least squares¶

The stochastic approximation algorithm can be used to implement the least squares formulas recursively. Suppose that we set $z_t = (y_t, x_t)$, $\alpha = (\beta, R)$, $\gamma_t = 1/t$, and

Then the stochastic approximation scheme becomes

Starting from appropriate initial conditions $(\beta_0, R_0)$, this is a method for calculating (5). Alternatively, it can be interpreted as a Bayesian procedure for updating estimates starting from a prior distribution $(\beta_0, R_0)$.

Least squares as stochastic Newton procedures¶

Sometimes we want to minimize the function $V(\theta)$ with respect to $\theta$. The gradient descent method is iteratively to choose $\theta_k$ according to

for some positive step-size sequence $\{\gamma_k\}$. Newton’s method is to choose $\{\theta_k\}$ according to

For the regression problem, we choose $\theta = \beta$ and $V(\beta) = 0.5 E(y_t - \beta' x_t)^2$. Since $V'(\beta) = -Ex_t(y_t - x_t'\beta)$ and $V''(\beta) = Ex_t x_t'$, a gradient descent and Newton’s method become, respectively,

Notice that, with $\gamma_k = 1$ for all $k$, Newton’s method converges in one step to the population least squares vector $\beta$ given by (3).

A comparison of the population formula (2) with the recursive least squares formula (18) motivates the interpretation of (18) as a stochastic Newton algorithm.

Nonlinear least squares¶

Suppose that we want to fit the nonlinear regression model

using the sample $\{y_t, x_t\}_{t=1}^T$. In population, our problem is to choose $\beta$ to minimize

where $\epsilon_t(\beta) = y_t - g(x_t, \beta)$. In this problem, the least squares orthogonality condition is

where $\psi_t(\beta) \equiv \nabla \epsilon_t(\beta)$ is the gradient of $\epsilon_t(\beta)$ with respect to $\beta$. Various recursive algorithms are designed to find solutions of (25). Stochastic gradient algorithms iterate on

Stochastic Newton algorithms iterate on versions of

Unlike the linear case, for nonlinear regressions these algorithms are not equivalent with corresponding ‘off-line’ algorithms.^[5],^[6]

Classification¶

Classification with known moments¶

Following Fisher (1936), least squares regression can be used to find a linear discriminant function for determining to which of two predetermined classes an individual belongs.^[7] We are given two populations, $x_1 \in X_1$ and $x_2 \in X_2$, of $k \times 1$ random vectors, each with common covariance matrix $V$, but with different mean vectors $Ex_1 = \mu_1$, $Ex_2 = \mu_2$. Vectors $x$ will be drawn from a mixture of the two distributions, with equal probability. Our task is to find a rule for classifying an $x$ that is randomly drawn from this mixture of populations $X_1$ and $X_2$, i.e., we want to say whether $x$ is from $X_1$ or from $X_2$. Note that the classification into $X_1$ and $X_2$ is given. For now, we assume that the means $\mu_1$ and $\mu_2$ and the common covariance matrix $V$ are known.

A solution of this problem is attained with the linear discriminant function. We want to find a linear function $\beta' x - \beta_0$, where $\beta$ is a $k \times 1$ vector and $\beta_0$ is a scalar, so that our decisions can be made according to the rule

For a given variance of the random variable $\beta' x$, which equals $\beta' V \beta$ and can be interpreted as ‘variance within a population,’ we want to choose $\beta$ to separate the two populations as much as possible. Discrepancy between the two populations is to be measured by the criterion $\beta'(\mu_1 - \mu_2)$. Our goal is to choose $\beta$ to maximize $\beta'(\mu_1 - \mu_2)$, subject to $\beta' V \beta = c$, where $c > 0$ is a constant. The maximizing value of $\beta$ is

where $\lambda$ is a Lagrange multiplier on the constraint, which can be set equal to one (which amounts to a choice of the variance $c$ in the constraint).

For a sample equally likely to be drawn from populations $X_1$ and $X_2$, the expected value $E\beta'x$ is $\beta'(\mu_1 + \mu_2)/2$. For the discriminant function, we therefore choose $\beta_0$ in (28) according to $\beta_0 = \beta'(\mu_1 + \mu_2)/2$.

When $X_1$ and $X_2$ are each multivariate normal, the discriminant function (28) has an interpretation in terms of a likelihood ratio test. This is because the log likelihood ratio can be represented as

so that (28) can be read as stating that $x$ should be assigned to population $X_1$ whenever the likelihood ratio exceeds one (or the log likelihood ratio exceeds zero).^[8]

Estimated parameters¶

When the means $(\mu_1, \mu_2)$ and covariance matrix $V$ are not known a priori, they are estimated by sample means and covariances, where the sample covariance is estimated by pooling observations across the $X_1$ and $X_2$ populations. Sample estimates are substituted into (29) to obtain the sample discriminant function.

Fisher (1936) showed that the linear discriminant function can be derived by a regression on dummy variables on $x$. For a sample of $k \times 1$ vectors $x_t$, where observations for $t = 1, \ldots, N_1$ are drawn from population $X_1$ and observations $t = N_1 + 1, \ldots, N_1 + N_2$ from population $X_2$, define $y_t = \frac{N_2}{N_1 + N_2}$ for $t = 1, \ldots, N_1$, $y_t = -\frac{N_1}{N_1 + N_2}$ for $t = N_1 + 1, \ldots, N_1 + N_2$. Then the estimated linear discriminant function can be obtained from an ordinary least squares regression of $y_t$ on $x_t$ for this sample.

Principal components analysis¶

Population theory¶

Let $x_t$ again be a $k \times 1$ random vector with second moment matrix $V = Ex_t x_t'$. The method of principal components analysis is based on the eigenvector decomposition of $V$, namely, $V = PDP^{-1}$, where $P$ is an orthogonal matrix whose columns are eigenvectors of $V$, and $D$ is the corresponding diagonal matrix of eigenvalues of $V$. This decomposition of $V$ induces a transformation of the $k \times 1$ vector $x_t$ into a $k \times 1$ vector $z_t = P'x_t$ with the following properties:

• (a) The $k$ elements of $z_t$ are mutually orthogonal.

• (b) The eigenvalues associated with the $k$ respective $z_t$’s equal the variances of the components of $z_t$.

The first principal component is the linear combination of the $x_t$’s (with norm of the weights constrained to 1) with the most variance, while the second component is the linear combination (orthogonal to the first one) with the next highest variance, and so on.

Thus, in principal components analysis, we seek a $z_t$ that satisfies

where the components of $z_t$ are mutually orthogonal, so that $Ez_t z_t' = D$ is a diagonal matrix; and where successive rows of $P'$ are orthogonal and of unit norm, so that $P'P = I$. The eigenvector decomposition of the covariance matrix $V$ of $x_t$ delivers the appropriate linear transformation $P$ of $x_t$.

The eigenvector $p_1$ that is associated with the largest eigenvalue of $D$ is called the first principal component of $x_t$. This eigenvector solves the problem of maximizing over $p_1$ the second moment $E(p_1' x)^2 = p_1' V p_1$, subject to the unit norm side condition $p_1' p_1 = 1$. The first-order necessary condition for this problem is

where $d/2$ is the Lagrange multiplier on the constraint. Evidently, $E(p_1' x)^2 = p_1' V p_1 = d^2 \|p_1\|^2 = d^2$ is maximized by choosing $d$ to be the largest eigenvalue of $V$ and $p_1$ to be the associated eigenvector. The second principal component maximizes $E(p_2' x)^2$ subject to $p_2' p_2 = 1$ and $p_1' p_2 = 0$, and so on. Furthermore, $d_i^2$ is the second moment of $z_{it} = p_i' x_t$.

Data reduction¶

Sometimes principal components analysis is used for building linear models designed to summarize the most important source of (generalized) variance within a data set $x_t$. For example, in economic time series data, the first one or two principal components often account for a dominant proportion of variance. The first principal component is a linear combination of the data along which most of the variation occurs.^[9]

Estimation¶

Estimation of principal components proceeds by substituting for $Ex_t x_t'$ the sample moment matrix $T^{-1} \sum_{t=1}^T x_t x_t'$. To estimate principal components, one simply computes the eigenvalues and normalized eigenvectors of the sample moment matrix.^[10]

Factor analysis¶

Factor analysis represents the covariance within a $k \times 1$ vector $x_t$ of observables in terms of their mutual dependence on a smaller $\ell \times 1$ vector $f_t$ of hidden ‘factors,’ where $\ell \ll k$. The second-moment matrix $V = Ex_t x_t'$ is restricted to be the sum of a matrix of rank $\ell$ and a diagonal matrix

where $L$ is a $(k \times \ell)$ matrix and $D$ is a $(k \times k)$ diagonal matrix. The model can also be represented as

where $Ef_t f_t' = I_\ell$, the $(\ell \times \ell)$ identity matrix, $E\epsilon_t \epsilon_t' = D$, and $Ef_t \epsilon_t' = 0$. The $(\ell \times 1)$ vector $f_t$ is composed of hidden factors, while the $(k \times 1)$ vector $\epsilon_t$ contains idiosyncratic noises.

The model asserts that all of the covariance within the $x_t$ vector is intermediated via the action of a much smaller number of hidden factors. A classic use of the model is interpreting students’ test scores. Here $x_t$ is a vector of student $t$’s scores on $k$ tests on various subjects, such as history, French, English, algebra, physics, and so on. It is posited that there are two hidden orthogonal factors, ‘mathematical intelligence’ and ‘verbal intelligence,’ that explain the structure of correlations among the test scores. A second example comes from the field of business cycle analysis, where it is possible to read Burns and Mitchell (1946) as asserting that there is one underlying factor called ‘business conditions’ or the ‘business cycle,’ dependence upon which intermediates most or all of the correlation among measures of economic activity at business cycle frequencies.^[11]

For a given sample $\{x_t\}_{t=1}^T$, let $S_T = \sum_{t=1}^T x_t x_t'/T$. For a Gaussian likelihood function, maximum likelihood estimation seeks values for $L, V$ that satisfy the normal equations

See Jöreskog (1967) for efficient ‘off-line’ methods of solving these normal equations. In the spirit of stochastic approximation, one might use the ‘on-line’ algorithm

Overfitting and choice of parameterization¶

Economists are familiar with the phenomenon of overfitting. The term overfitting is meant to describe a circumstance in which a researcher can get a good fit for the data set in hand by estimating so many parameters that out of sample the model does much worse than an alternative model that fits fewer parameters, thereby giving up the ability to fit the sample data as well in exchange for increased precision of the estimated parameters.^[12] Figure 1 and Figure 2 show a standard example in which two ‘wrong’ models (polynomials in time) are fitted to a random walk (i.e., a $y_t$ process $y_t = y_{t-1} + \epsilon_t$, where $\epsilon_t$ is a serially uncorrelated Gaussian variable). Evidently, the higher-order model fits much better within the sample, but will do a much worse job of predicting $y$ if it is extrapolated.

Parameterizing vector autoregressions¶

The autoregressive representation has too many parameters to be useful for applications to the short data sets that economists work with. It imposes little more than that $C_z(k)$ are well defined, i.e. that the process is covariance stationary. In terms of describing a data-generating mechanism, the representation affords no economies in terms of numbers of parameters vis-à-vis either the entire list of covariance matrices $C_z(k)$ or, equivalently, the spectral density $S_z(\omega) = \sum_{k=-\infty}^{\infty} C_z(k) \exp(-i\omega k)$. (Even though it provides no economies in terms of representation, the vector autoregression might provide insights.)

Applying vector autoregressions requires adopting special versions in which the numbers of parameters are kept small relative to the length of the data sets being studied. Economists have devised differing specializations designed to render the vector autoregressive model applicable.

Rational expectations macroeconomists and econometricians have devised one set of procedures for reducing the number of parameters. In addition to restricting the lag-length (instead of fitting an infinite-order vector autoregression, they fit models in which $z_t$ depends on only $m$ lagged values of itself), they typically restrict the number of coefficients that describe the cross-variable dynamics. They use theories that imply a particular class of functions $A_j = A_j(\theta)$ expressing each coefficient matrix in the vector autoregression as a function of a much smaller number of free parameters $\theta$. These parameters are interpreted as describing the preferences, technologies, and information sets of the agents whose behavior is determining $z_t$. Such rational expectations models typically claim to be complete and fully interpreted models in the sense that they purport to describe the covariation through time of all of the variables modelled in ways consistent with general equilibrium theory, with the parameters being economically interpretable as preference, technology, or information parameters.^[13]

Sims, Litterman, and their co-workers have invented a different way of coping with the overfitting problem. In principle, their procedures do not restrict the number of parameters (beyond their use of some restrictions on lag lengths), but work by heavily exploiting some of the computational features associated with a recursive form of estimation that is applicable to vector autoregressions. Rather than adopting a function $A_j = A_j(\theta)$ as the rational expectations modellers do, Sims and Litterman carry along all of the elements of the $A_j$’s as free parameters, but restrict the initial coefficients and covariance matrix. Then they update all of the coefficients via recursive least squares. Evidently, their estimation procedures (or sometimes important parts of them) have interpretations as stochastic approximation algorithms.^[14] Litterman and Sims have devoted much effort to devising specifications of these initial conditions that are designed to forecast macroeconomic time series well out of the sample used to estimate the parameters. Litterman and Sims’s choice of these initial conditions has involved less formal use of economic theory than that used by rational expectations econometricians in deducing their functions $A_j = A_j(\theta)$.^[15]

Statistics for bounded rationality¶

The boundedly rational agents that we shall put into our example economic environments will all use versions of the stochastic approximation algorithm to estimate decision functions or parameters. This strategy for modelling boundedly rational agents starts from the observation that first-order conditions for stochastic estimation and optimization take exactly the form of the equation being solved by stochastic approximation, namely,

Further, stochastic approximation is designed to solve this equation under the conditions of limited knowledge (i.e., insufficient knowledge to use the differential calculus or the expectational calculus) with which we want to endow our artificially intelligent agents.

We shall see stochastic approximation algorithms applied over and over again, in superficially different contexts. Sometimes they will be used with versions of boundedly rational agents’ first-order conditions that come from estimation problems like those described in this chapter. Stochastic approximation algorithms will also be used where (9) is interpreted as the ‘Euler equation’ from a boundedly rational agent’s optimum problem.

Before handing stochastic approximation algorithms to our boundedly rational economic agents, we turn in the next chapter to survey some of the themes in the recent literature on neural networks and other forms of artificial intelligence. In reading this material, watch for stochastic approximation methods to make appearances.