4
$\begingroup$

Say we want to learn a function:

$f(\mathbf{x} \in \mathbf{R}^p) \rightarrow \mathbf{y} \in \mathbf{R}^q$

where $\mathbf{x}$ and $\mathbf{y}$ are vectors representing time series.

We have multiple examples of this mapping, i.e.:

$$\begin{pmatrix}\mathbf{x_0}\\...\\\mathbf{x_N}\end{pmatrix}\rightarrow \begin{pmatrix}\mathbf{y_0}\\...\\\mathbf{y_N} \end{pmatrix} $$

What type of problem is this? Is it a regression problem? If so, what metrics (loss functions) and methods would be appropiate for this problem? Anything specifically available in Python?

$\endgroup$
6
  • $\begingroup$ I am a bit confused with your notation. Specifically $\mathbf{t}_x$ vs $\mathbf{t}_X$ and $t_X$. Perhaps standard (statistical) notation like $X_t$ or $X_{it}$ will help? Otherwise, example data will also help clarify things. $\endgroup$
    – qoheleth
    Aug 15 '14 at 3:03
  • $\begingroup$ Thanks @qoheleth I just simplified the notation significantly. Hopefully it is a lot clearer now. $\endgroup$ Aug 15 '14 at 3:24
  • $\begingroup$ Did you really intend to imply that $N+1=p=q$? $\endgroup$
    – whuber
    Aug 15 '14 at 5:41
  • 2
    $\begingroup$ @whuber: I think $N$ is the number of paired sample time series, each of length $p$ (for the series that is mapped from) or $q$ (for the series that is mapped to). $\endgroup$ Aug 15 '14 at 10:42
  • $\begingroup$ Correct me if I'm wrong, but it looks like this the same problem as classifying elements of $\mathbf{x}$ with integers $\{1, \dots, N\}$. Not sure if that helps at all. $\endgroup$ Aug 15 '14 at 12:39
3
$\begingroup$

This problem falls to the class called structured-output learning. First, you need to define a function $F(\mathbf{y}; \mathbf{x}, \mathbf{w})$ that scores predictions. It is supposed to return large values for the correct $\mathbf{y}$ and those similar to it. It is parametrized by the vector $\mathbf{w}$; usually $F$ depends linearly on $\mathbf{w}$. At test time, the decision is thus made by maximization:

$\hat{\mathbf{y}} = \arg\!\max_{\bar{\mathbf{y}}} F(\bar{\mathbf{y}}; \mathbf{x}, \mathbf{w})$.

So $F$ should be chosen the way to perform this maximization efficiently. See below for an example.

At training time, you need to find the parameters $\mathbf{w}^*$ such that for each training example $\mathbf{x}_i$ the corresponding prediction $\hat{\mathbf{y}}_i$ should be close $\mathbf{y}_i$ in some sense. Similarly to regression, it is unlikely to match perfectly, so one needs to define a loss function.

One such method is provided by structured SVM. The methods tries to find parameters $\mathbf{w}$ to maximize the margin

$F(\mathbf{y}_i; \mathbf{x}_i, \mathbf{w}) - \max_{\bar{\mathbf{y}}: \bar{\mathbf{y}} \ne \mathbf{y}_i} F(\bar{\mathbf{y}}; \mathbf{x}_i, \mathbf{w})$

for each training example $(\mathbf{x}_i, \mathbf{y}_i)$. To account for similarity in $\mathbf{y}$'s, it is usually augmented with the empirical loss function $\Delta(\bar{\mathbf{y}}; \mathbf{y})$ that measures some sort of distance; for discrete vectors it may measure Hamming distance. Thus, for each training example we want to maximize the following:

$F(\mathbf{y}_i; \mathbf{x}_i, \mathbf{w}) - \max_{\bar{\mathbf{y}}} \{ F(\bar{\mathbf{y}}; \mathbf{x}_i, \mathbf{w}) + \Delta(\bar{\mathbf{y}}; \mathbf{y}_i) \}$.

The idea is to strive for the larger margin if $\bar{\mathbf{y}}$ is more different from $\mathbf{y}_i$. We can put it together and add $L_2$ regularization to get the SVM-style optimization problem:

$\textrm{minimize}_{\mathbf{w}, \boldsymbol{\xi}} \quad \frac{\|\mathbf{w}\|^2}{2} + C \sum_{i=0}^N \xi_i,$

$\textrm{s.t.} \quad F(\mathbf{y}_i; \mathbf{x}_i, \mathbf{w}) - \max_{\bar{\mathbf{y}}} \{ F(\bar{\mathbf{y}}; \mathbf{x}_i, \mathbf{w}) + \Delta(\bar{\mathbf{y}}; \mathbf{y}_i) \} \ge -\xi_i, \quad \forall i.$

It is not trivial to solve, but there are well-studied methods that perform it, including the cutting-plane algorithm and subgradient descent. For implementations, you can try SVMstruct and pystruct.


What is left is the design of the scoring function $F$. It really depends on the problem you solve, but often some kind of graphical model is useful. Given that your data are sequential, something like Hidden Markov Model or some its generalization may be useful. For example, you may consider the following “factorization”:

$F(\mathbf{y}; \mathbf{x}, \mathbf{w}) = \psi(y_{0}; \mathbf{x}, \mathbf{w}) + \sum_{j=1}^q \Big( \phi(y_{j-1}, y_{j}; \mathbf{w}) + \psi(y_{j}; \mathbf{x}, \mathbf{w}) \Big).$

It allows performing maximization over $\mathbf{y}$ in $\mathcal{O}(q)$ time using dynamic programming. The potential functions $\psi$ and $\phi$ should depend linearly on (different parts of) $\mathbf{w}$, but specific form depends on your problem (in particular, if the output variables are discrete or continuous). You also need to figure out the components of $\mathbf{x}$ the potential function depends on.

This form of scoring functions accounts for the “correlations” of neighbouring $y$'s, but it is possible to add higher-order connections at some computational cost (i.e. potentials like $\phi_4(y_{j-4}, y_{j}; \mathbf{w})$). SVMstruct library contains an example of training HMM.

Note that in case of such sequential models training can be done by maximizing likelihood, which leads to a different objective function, but in general case it is infeasible. See this paper for more details on probabilistic training of sequential models.

$\endgroup$
0
$\begingroup$

This problem is too general to be useful. A solution would be to map each $\mathbf{x}_i$ to $\mathbf{y}_i$ and to continue this mapping arbitrarily on $\mathbb{R}^p\setminus\{\mathbf{x}_i|i=1,\ldots,N\}$. So there is no unique solution for exactly this general problem. The function space $f$ belongs to is too large. If you could restrict $f$ to some parametrized function family (like polynomial regression) it might become feasible.

(Maybe you edit your question to make it more precise)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.