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

<p>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 (<a href="https://ganguli-gang.stanford.edu/pubs.html" rel="nofollow noreferrer">https://ganguli-gang.stanford.edu/pubs.html</a>), esp. <em>Exponential expressivity in deep neural networks through transient chaos</em></p>

<blockquote>
  <p>apparently there have been recently methods designed to find these in a more automated way</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2017-07-29T11:15:27.270Z
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?
Clement C.
CC BY-SA 3.0
2017-08-02T19:06:54.250Z
Taken's theorem is proved on a completely known dynamic time series. You're never going to encounter one of those in empirical data
Howon
CC BY-SA 3.0
2017-07-28T17:35:04.257Z
2017-07-28T17:41:37.190Z
2017-07-28T17:41:37.190Z
Howon
<p>Theoretically, Takens's theorem implies that a deterministic system attractor of finite dimension <span class="math-container">$D$</span> can be reconstructed by a <em>finite</em> number of time delays <span class="math-container">$k$</span> if
<span class="math-container">$$
k \geq 2D + 1.
$$</span>
This implies that the dynamics of eligible non-linear functions can be replicated by a non-linear autoregressive model of <span class="math-container">$k$</span> delays. Such a model can, and has been, realized with neural networks (See Eric A. Wan's <em>Modeling Nonlinear Dynamics with Neural Networks: Examples in Time Series Prediction</em>). </p>

<p>The same paper by Wan trains a neural network to predict the sum of Henon iterations. Of course, the predicted and actual iterates diverge, but the attractor is nonetheless replicated by the neural network, realizing Takens's theorem. So, Howon's observation rings true: while the dynamics of certain non-linear functions can be captured with finite delay, their values cannot be so captured perfectly.</p>

<p>Further sources:
Chapter 5 of <em>Recurrent Neural Networks for Prediction: Learning Algorithms, Architectures and Stability</em> by Mandic and Chambers </p>

CC BY-SA 4.0
2019-08-24T02:08:08.427Z
2019-08-24T02:08:08.427Z
Kalinda Vathupola
<p><em>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).</em></p>

<p>If I understood correctly the <a href="https://en.wikipedia.org/wiki/Takens%27_theorem" rel="noreferrer">Wikipedia page</a> 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 </p>

<blockquote>
  <p>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.</p>
</blockquote>

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

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

<ul>
<li>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)</li>
<li>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)</li>
</ul>

<p>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., <em>"it does not apply in the usual settings we consider because [...]"</em>?</p>

CC BY-SA 3.0
2017-07-27T13:32:35.373Z
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.
Aryeh
CC BY-SA 3.0
2017-07-28T14:19:27.210Z
@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.
Clement C.
CC BY-SA 3.0
2017-07-28T14:47:00.493Z
Certainly CLTs for Markov chains are known.
Aryeh
CC BY-SA 3.0
2017-07-28T14:53:45.703Z
@Aryeh My bad, that was an acronym overload. By "CLT," I meant Computational Learning Theory (not Central Limit Theorem).
Clement C.
CC BY-SA 3.0
2017-07-29T13:58:29.813Z
@ClementC. I would suggest the following query on google search, "takens -taken", without the quotes.
Tayfun Pay
<machine-learning><lg.learning><physics>
Applications of Takens' theorem to TCS?
Clement C.
# Applications of Takens' theorem to TCS?

(Asked by: username_0 on 2017-07-27)

*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](https://en.wikipedia.org/wiki/Takens%27_theorem) 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 [...]"*?

**Tags:** machine-learning, lg.learning, physics
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: Certainly CLTs for Markov chains are known.  
> **username_0**: @Aryeh My bad, that was an acronym overload. By "CLT," I meant Computational Learning Theory (not Central Limit Theorem).  
> **username_2**: @ClementC. I would suggest the following query on google search, "takens -taken", without the quotes.  

---

## 2 answers

### Answer by username_3 on 2017-07-28. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_3**: Taken's theorem is proved on a completely known dynamic time series. You're never going to encounter one of those in empirical data  

---

### Answer by username_4 on 2019-08-24. Score: 1

Theoretically, Takens's theorem implies that a deterministic system attractor of finite dimension $D$ can be reconstructed by a *finite* number of time delays $k$ if
$$
k \geq 2D + 1.
$$
This implies that the dynamics of eligible non-linear functions can be replicated by a non-linear autoregressive model of $k$ delays. Such a model can, and has been, realized with neural networks (See Eric A. Wan's *Modeling Nonlinear Dynamics with Neural Networks: Examples in Time Series Prediction*).

The same paper by Wan trains a neural network to predict the sum of Henon iterations. Of course, the predicted and actual iterates diverge, but the attractor is nonetheless replicated by the neural network, realizing Takens's theorem. So, Howon's observation rings true: while the dynamics of certain non-linear functions can be captured with finite delay, their values cannot be so captured perfectly.

Further sources:
Chapter 5 of *Recurrent Neural Networks for Prediction: Learning Algorithms, Architectures and Stability* by Mandic and Chambers


---

