How to solve a classification problem when the independent variables/covariates/feature vectors form a time series?

Question

Say we've a time indexed sequence of feature vectors/covariates/independent variables $x_t$ at time $t$. Say also we've a corresponding time indexed sequence of variates/dependent variables $y_t$. Now normally, when we solve classification problems, we assume that the covariates/features form a random sample, i.e. $x_i$'s are values of the random variables $X_i$'s, and that $X_i$'s are iid random variables. Clearly that assumption doesn't necessarily hold for time indexed covariates. So my question is: how to go about solving a classification problem where independent variables/covariates/feature vectors form a time series?

Now a direct aproaches that comes to mind is: Come up with a time dependent classification model (e.g. logistic regression) of the form: $y_t|x_t \sim Ber (<\theta_t, x_t>)$ for time variable $t$. Then we can try to construct the joint probability density $f(y_1, ...y_n|x_1, ... x_n)$ and maximize it w.r.t. $\theta_t$ and then try to learn about the function $\theta_t$. But we face the problem that unlike standard logistic regression we can NOT write $f(y_1, ...y_n|x_1, ... x_n)= \Pi_{t=1}^{n} f_t(y_t|x_t)$, as the the distribution of $y_t|x_t$ may depend on that of $y_s|x_s$ when $s < t$. Now of course, we can use Markov chain or hidden markov models to assume that $y_t|x_t$ depnds only on previous $d$ "events": $y_s|x_s, t-d+1 \leq s \leq t$. But all time series may not satisfy this assumtion. So how to get around that?

Is there a concre mathematical theory of time dependent classification models?

Answer 1

It all comes down to what you're able to assume for a particular problem. The more assumptions that can be reasonably made, the easier it will be to solve the problem. In the very worst case, it can only be assumed that the current output $y_t$ is conditionally independent of future inputs/outputs, given the current input $x_t$ and the entire history of inputs and outputs. In this case, the likelihood function factorizes as:

$$p(y_1, \dots, y_n \mid x_1, \dots, x_n, \theta) = \prod_{t=1}^n p(y_t \mid x_1, \dots, x_t, y_1, \dots, y_{t-1}, \theta)$$

where $\theta$ is a parameter vector. This hardly constrains the problem at all, as the conditional distribution of $y_t$ could be different at each moment in time. To have any hope of learning, further structure is necessary. For example, a common assumption might be that the conditional distribution of $y_t$ is the same for all timepoints. We might additionally assume that all outputs are conditionally independent, given the history of inputs (i.e. there's no correlated noise). Then, the likelihood function factorizes as:

$$p(y_1, \dots, y_n \mid x_1, \dots, x_n, \theta) = \prod_{t=1}^n p(y_t \mid x_1, \dots, x_t, \theta)$$

To learn in this setting, we'd have to specify a proper form for $p(y_t \mid x_1, \dots, x_t, \theta)$--a function that outputs a distribution over classes at each timepoint, given the entire history of inputs. For example, a recurrent neural net (RNN) with softmax outputs could work. Then, the parameters $\theta$ are learned by maximizing the likelihood, performing Bayesian inference, etc. Keep in mind that, even though the outputs of functions like RNNs technically depend on the entire input history, learning long-range temporal dependencies is very difficult. This is an active area of research, and we don't have a great solution yet.

In many problems, it can also be reasonable to assume that the data-generating process has finite memory, so the output at each timepoint only depends on the current input and the previous $d$ inputs. In this case, the likelihood function factorizes as:

$$p(y_1, \dots, y_n \mid x_1, \dots, x_n, \theta) = \prod_{t=1}^n p(y_t \mid x_{t-d}, \dots, x_t, \theta)$$

Note that, if we ignore the first $d$ timepoints, we can construct a set of 'augmented feature vectors' containing time-lagged inputs. That is, $z_t = [x_{t-d}, \dots, x_t]$. In this case, each output $y_t$ depends only on the augmented input $z_t$. The problem is then to predict $y_t$ as a function of $z_t$, which can be solved using any off-the-shelf classifier designed for i.i.d. data.

Finally, note that any cross-validation procedures used for model selection and/or performance evaluation must properly take temporal dependence into account. The usual procedures designed for i.i.d. data are not valid in this setting.