6
$\begingroup$

My apologies if the question is a tad vague—I did try to search the literature for more, but didn't find anything (the similarity between the keywords "Takens" and "taken" on Google may be partly to blame).

If I understood correctly the Wikipedia page on Takens' theorem, and some discussions I had with people in applied (physics-related) fields that mentioned it to me, Taken's theorem essentially states that

if one has a system parameterized by a state (time-dependent) $x(t)\in\mathbb{R}^d$, then under some natural assumptions on $x$ (in particular, smooth enough) there exists $k$—related to the underlying dimension of the manifold on which $x$ "lives— and some "lag" $\tau$ such that $$ y(t) \stackrel{\rm def}{=} (x_1(t), x_1(t+\tau),\dots,x_1(t+(k-1) \tau)\in\mathbb{R}^k $$ is information-theoretically equivalent to the original parameterization $x$; and moreover, this new parameterization, now living in a "shadow manifold," preserves the topology of the original manifold.

(All imprecisions above definitely mine, I cannot claim I fully understand the theorem.)

This does strike me as a very useful tool, similar in spirit to some type of dimension reduction:

  • bringing in domain-specific knowledge (to figure out $\tau$ and $k$, although apparently there have been recently methods designed to find these in a more automated way)
  • allowing easy measuring (no need to perform a computationally heavy mapping for the change of parameters: instead, focusing in a single lagged coordinate of the data is enough)

My question is: has this theorem, or some version of it, been applied or explored in the context of computational learning? If so, where can I find references of it? If not, is there a reason why—e.g., "it does not apply in the usual settings we consider because [...]"?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ It's not clear how to incorporate the temporal aspect -- the theorem, after all, deals with dynamical systems, while in classic dimensionality reduction applications (PCA, Johnson-Lindenstrauss), one is given a static point set. $\endgroup$ – Aryeh Jul 27 '17 at 13:32
  • $\begingroup$ @Aryeh Good point... however, there must be some relevant setting in CLT or theoretical ML where one has a time series, a Markov chain, or some process that can be cast under that time-varying formulation. $\endgroup$ – Clement C. Jul 28 '17 at 14:19
  • $\begingroup$ Certainly CLTs for Markov chains are known. $\endgroup$ – Aryeh Jul 28 '17 at 14:47
  • $\begingroup$ @Aryeh My bad, that was an acronym overload. By "CLT," I meant Computational Learning Theory (not Central Limit Theorem). $\endgroup$ – Clement C. Jul 28 '17 at 14:53
  • $\begingroup$ @ClementC. I would suggest the following query on google search, "takens -taken", without the quotes. $\endgroup$ – Tayfun Pay Jul 29 '17 at 13:58
2
$\begingroup$

Takens himself did some CS work although not TCS work. He did some attractor reconstruction stuff with neural networks, for example (https://clgiles.ist.psu.edu/papers/NC-2000-learning-chaos-nn.pdf) and it does use his embedding theorem to suggest nonlinear autoregressive (time delay) neural nets, and look towards actual recurrent networks.

Overall, dynamical systems is closest to CS in neural network land because of the easy dynamical interpretation of the models. Try some of the Ganguli gang's publications (https://ganguli-gang.stanford.edu/pubs.html), esp. Exponential expressivity in deep neural networks through transient chaos

apparently there have been recently methods designed to find these in a more automated way

Again, not theoretical, but I've used them for non-example time series data and they aren't incredible in practice, by the way. The denoising aspects of them is actually quite difficult.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the pointers—I'll have a look at these papers. I'm not quite following what you mean in your last sentence, however: what are these "denoising aspects" that become problematic in this context? $\endgroup$ – Clement C. Jul 29 '17 at 11:15
  • 1
    $\begingroup$ Taken's theorem is proved on a completely known dynamic time series. You're never going to encounter one of those in empirical data $\endgroup$ – Howon Aug 2 '17 at 19:06

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.