<p>I think this is a similar approach to Shnor's Martingale characterisation of algorithmic randomness, I have sent you an email with more info, but it is a potential nice non-overfitting test and also alternative characterisation.</p>

CC BY-SA 4.0
2021-02-22T09:16:46.727Z
2021-02-22T09:16:46.727Z
Hector Zenil
<h2>Motivation:</h2>
<p>The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of algorithmic randomness is transformation-invariant. I was motivated to find such a theorem for a couple reasons.</p>
<p>Such a theorem may be used to perform empirical tests using machine learning to determine whether a dataset was sampled from an algorithmically random process as well as to test extraordinary claims that a machine learning model can efficiently simulate algorithmically random processes.</p>
<p>Might this theorem be known by a particular name?</p>
<h3>The learning problem:</h3>
<p>Let's suppose <span class="math-container">$F_{\theta}$</span> is a function space that is useful for statistical learning(ex. Deep Neural Networks) such that <span class="math-container">$D_N = (X_N,Y_N)$</span> is a dataset where <span class="math-container">$X_N=\{X_i\}_{i=1}^{2N}$</span>, the <span class="math-container">$X_i$</span> are sampled i.i.d. from a discrete random variable <span class="math-container">$X$</span>, and <span class="math-container">$Y_N=\{Y_i\}_{i=1}^{2N} \in \{0,1\}^{2N}$</span> are the class labels.</p>
<p>If <span class="math-container">$D_N$</span> is split into balanced training and test sets <span class="math-container">$D_N^\text{train}$</span> and <span class="math-container">$D_N^\text{test}$</span> then we have <span class="math-container">$D_N^\text{train}=(X_N^\text{train},Y_N^\text{train})$</span> and <span class="math-container">$D_N^\text{test}=(X_N^\text{test},X_N^\text{test})$</span> such that <span class="math-container">$\lvert X_N^\text{train} \rvert = \lvert X_N^\text{test} \rvert = N$</span> and <span class="math-container">$X_N^\text{train} \cup X_N^\text{test} = X_N$</span>.</p>
<p>Furthermore, we shall assume that the training and test sets are balanced so we have:</p>
<p><span class="math-container">\begin{equation}
\frac{1}{N} \sum_i Y_i^\text{train} = \frac{1}{N} \sum_i Y_i^\text{test} = \frac{1}{2} \tag{1}
\end{equation}</span></p>
<h3>Defining algorithmic randomness:</h3>
<p>Now, <span class="math-container">$X$</span> is algorithmically random relative to <span class="math-container">$F_{\theta}$</span> if <span class="math-container">$X$</span> is incompressible relative to <span class="math-container">$F_{\theta}$</span> in the sense that for any choice of train-test split we have:</p>
<p><span class="math-container">\begin{equation}
\mathbb{E}[K(X |F_{\theta})] = \min_{f \in F_{\theta}} \mathbb{E}[K(X |f)] \sim N \cdot \ln \lvert X \rvert \tag{2}
\end{equation}</span></p>
<p>where I used the fact that the expected Kolmogorov Complexity equals the Shannon entropy, and applied the Shannon source-coding theorem to i.i.d. data.</p>
<h3>The conjecture:</h3>
<p>In consequence, (1) implies that for a particular sample <span class="math-container">$X_N \sim X$</span> it may be possible to find <span class="math-container">$f \in F_{\theta}$</span> such that <span class="math-container">$\forall i \in [1,2N], f(X_i) = Y_i$</span> on the condition that the Kolmogorov Complexity:</p>
<p><span class="math-container">\begin{equation}
K(f) \sim 2N  \tag{3}
\end{equation}</span></p>
<p>as this would amount to memorisation and not discovering regularities in <span class="math-container">$D_N$</span> since <span class="math-container">$X$</span> is algorithmically random relative to <span class="math-container">$F_{\theta}$</span>. To be precise, if an arbitrary mathematical  transformation <span class="math-container">$T$</span>(ex. random matrix) is applied to <span class="math-container">$D_N$</span> so:</p>
<p><span class="math-container">\begin{equation}
X'_N = T \circ X_N \tag{4}
\end{equation}</span></p>
<p>given that <span class="math-container">$f(X_i)=Y_i \implies \delta_{f(X_i),Y_i} = 1$</span>, the solution to the empirical risk minimisation problem may be formulated as follows:</p>
<p><span class="math-container">\begin{equation}
\hat{f} = \max_{f \in F_{\theta}} \frac{1}{N} \sum_{i=1}^N \delta_{f(X'_i),Y_i} \tag{5}
\end{equation}</span></p>
<p>and for large <span class="math-container">$N$</span>, the expected performance on the test set is approximated by:</p>
<p><span class="math-container">\begin{equation}
\lim_{N \to \infty} \frac{1}{N} \sum_{i=N+1}^{2N} \delta_{\hat{f}(X'_i),Y_i} = \frac{1}{2} \tag{6}
\end{equation}</span></p>
<p><strong>Note:</strong> I am implicitly interested in natural signals which exhibit algorithmic randomness, and the transformations <span class="math-container">$T$</span> are arbitrary to the extent that they don't change the phase-space dimension of the processes responsible for generating natural signals.</p>
<h2>References:</h2>
<ol>
<li>Peter Grünwald and Paul Vitányi. Shannon Information and Kolmogorov Complexity. 2010.</li>
<li>Jerome H. Friedman, Robert Tibshirani, and Trevor Hastie. The Elements of Statistical Learning. Springer. 2001.</li>
</ol>

CC BY-SA 4.0
2021-02-21T17:11:04.613Z
This is probably of minor importance to the core of the discussion, but you're having index problems when splitting you dataset between train and test. Are your samples (and labels) indexed between $1$ and $N$ or between $1$ and $2N$ ?
Hugo Manet
CC BY-SA 4.0
2021-02-21T17:22:06.753Z
My samples are indexed between 1 and 2N. Regarding (2), this amounts to saying that the model must memorise the labels Y_i.
Aidan Rocke
CC BY-SA 4.0
2021-02-22T00:41:54.630Z
What is your question, specifically?
D.W.
<reference-request><machine-learning><kolmogorov-complexity>
An invariance theorem for algorithmically random data in statistical learning
Aidan Rocke
# An invariance theorem for algorithmically random data in statistical learning

(Asked by: username_0 on 2021-02-21)

## Motivation:

The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of algorithmic randomness is transformation-invariant. I was motivated to find such a theorem for a couple reasons.

Such a theorem may be used to perform empirical tests using machine learning to determine whether a dataset was sampled from an algorithmically random process as well as to test extraordinary claims that a machine learning model can efficiently simulate algorithmically random processes.

Might this theorem be known by a particular name?

### The learning problem:

Let's suppose $F\_{\theta}$ is a function space that is useful for statistical learning(ex. Deep Neural Networks) such that $D\_N = (X\_N,Y\_N)$ is a dataset where $X\_N=\{X\_i\}\_{i=1}^{2N}$, the $X\_i$ are sampled i.i.d. from a discrete random variable $X$, and $Y\_N=\{Y\_i\}\_{i=1}^{2N} \in \{0,1\}^{2N}$ are the class labels.

If $D\_N$ is split into balanced training and test sets $D\_N^\text{train}$ and $D\_N^\text{test}$ then we have $D\_N^\text{train}=(X\_N^\text{train},Y\_N^\text{train})$ and $D\_N^\text{test}=(X\_N^\text{test},X\_N^\text{test})$ such that $\lvert X\_N^\text{train} \rvert = \lvert X\_N^\text{test} \rvert = N$ and $X\_N^\text{train} \cup X\_N^\text{test} = X\_N$.

Furthermore, we shall assume that the training and test sets are balanced so we have:

\begin{equation}
\frac{1}{N} \sum\_i Y\_i^\text{train} = \frac{1}{N} \sum\_i Y\_i^\text{test} = \frac{1}{2} \tag{1}
\end{equation}

### Defining algorithmic randomness:

Now, $X$ is algorithmically random relative to $F\_{\theta}$ if $X$ is incompressible relative to $F\_{\theta}$ in the sense that for any choice of train-test split we have:

\begin{equation}
\mathbb{E}[K(X |F\_{\theta})] = \min\_{f \in F\_{\theta}} \mathbb{E}[K(X |f)] \sim N \cdot \ln \lvert X \rvert \tag{2}
\end{equation}

where I used the fact that the expected Kolmogorov Complexity equals the Shannon entropy, and applied the Shannon source-coding theorem to i.i.d. data.

### The conjecture:

In consequence, (1) implies that for a particular sample $X\_N \sim X$ it may be possible to find $f \in F\_{\theta}$ such that $\forall i \in [1,2N], f(X\_i) = Y\_i$ on the condition that the Kolmogorov Complexity:

\begin{equation}
K(f) \sim 2N \tag{3}
\end{equation}

as this would amount to memorisation and not discovering regularities in $D\_N$ since $X$ is algorithmically random relative to $F\_{\theta}$. To be precise, if an arbitrary mathematical transformation $T$(ex. random matrix) is applied to $D\_N$ so:

\begin{equation}
X'\_N = T \circ X\_N \tag{4}
\end{equation}

given that $f(X\_i)=Y\_i \implies \delta\_{f(X\_i),Y\_i} = 1$, the solution to the empirical risk minimisation problem may be formulated as follows:

\begin{equation}
\hat{f} = \max\_{f \in F\_{\theta}} \frac{1}{N} \sum\_{i=1}^N \delta\_{f(X'\_i),Y\_i} \tag{5}
\end{equation}

and for large $N$, the expected performance on the test set is approximated by:

\begin{equation}
\lim\_{N \to \infty} \frac{1}{N} \sum\_{i=N+1}^{2N} \delta\_{\hat{f}(X'\_i),Y\_i} = \frac{1}{2} \tag{6}
\end{equation}

**Note:** I am implicitly interested in natural signals which exhibit algorithmic randomness, and the transformations $T$ are arbitrary to the extent that they don't change the phase-space dimension of the processes responsible for generating natural signals.

## References:

1. Peter Grünwald and Paul Vitányi. Shannon Information and Kolmogorov Complexity. 2010.
2. Jerome H. Friedman, Robert Tibshirani, and Trevor Hastie. The Elements of Statistical Learning. Springer. 2001.

**Tags:** reference-request, machine-learning, kolmogorov-complexity

> **Comments:**
> **username_1**: This is probably of minor importance to the core of the discussion, but you're having index problems when splitting you dataset between train and test. Are your samples (and labels) indexed between $1$ and $N$ or between $1$ and $2N$ ?  
> **username_0**: My samples are indexed between 1 and 2N. Regarding (2), this amounts to saying that the model must memorise the labels Y_i.  
> **username_2**: What is your question, specifically?  

---

## 1 answers

### Answer by username_3 on 2021-02-22. Score: 2 | Accepted answer

I think this is a similar approach to Shnor's Martingale characterisation of algorithmic randomness, I have sent you an email with more info, but it is a potential nice non-overfitting test and also alternative characterisation.


---

