# Thoughts on "learning systems"

Here are some general thoughts on what kind of learning systems we could hope to have, and what will a theory of those look like.
Given advances in ML, the guiding principle is that the default baseline is that with enough data and compute we can achieve any goal

Suppose that we have some domain $\mathcal{X}$ of natural data - images, texts, etc..

We also have access to some distributions $X$ over $\mathcal{X}$. We could imagine that there is a "baseline distribution" $X_0$ and these distributions are of the form $X = X_0|A$ for some event $A$ (e.g., Images conditioned on being one of 10 classes and sampled from Flickr).

We have a set $\mathcal{C}$ of "semantic properties" - let's assume that each such property $c\in \mathcal{C}$ is a function $c:\mathcal{X} \rightarrow \{ \pm 1 \}$.

Some tasks we would want to do are the following:

1. __Classification:__ compute $c(x)$ for $c\in \mathcal{C}$ and $x\in\mathcal{X}$.

2. __Likelihood:__ Given samples from $X$ and $x \in \mathcal{X}$, approximate $\log \Pr[ X=x]$.

3. __Generation:__ Given samples from $X$, generate fresh sample $x \sim X'$ from $X'$ that is close to $X$.

(we would also want to do tasks 2 and 3 for $X|A$ for some event $A$, as long as $A$ is "semantic" in the sense of being described via functions in $\mathcal{C}$)

These tasks are all inter-related:

1. The notion of indistinguishability for $X'$ will be that $\mathbb{E}[c(X)] \approx \mathbb{E}[c(X')]$ for every $c \in \mathcal{C}$.

2. The likelihood and generation should be related to each other where $\log Pr[ X' = x]$ should approximately be equal to the estimate of $\log \Pr[ X =x]$.

They can also be used to achieve other tasks. For example, the "philosophically right way" to achieve adversarial robustness with respect to some distance measure $\Delta$ and radius $\delta$ is, given $x$ to "decode it" to $x'$ such that $\Delta(x,x')\leq \delta$ and maximizes $\Pr[ X=x']$.

This would correspond to a "consistent system of reasoning".

Let's define a _good representation_ of $\mathcal{X}$ to be a function $Enc:\mathcal{X} \rightarrow \mathbb{R}^m$ such that for every $c \in \mathcal{C}$ there is a _linear_ function $\hat{c}:\mathbb{R}^m \rightarrow \mathbb{R}$ such that for every natural distribution $X$ over $\mathcal{X}$,

$$\Pr_{x \sim X}[ c(x) \neq \mathrm{sign}(\hat{c}(\hat{x})) ] < \epsilon$$

where $\hat{x} = Enc(x)$.

Another way to say this is that the $m$-dimensional random variables $\hat{x}|c(x)=1$ and $\hat{x}|c(x)=-1$ will have different means $\mu_+ , \mu_- \in \mathbb{R}^m$, and whose means will be well separated enough so that if we let $v = \mu_+ - \mu_i$ then the univariate random variables $\langle \hat{x}, v \rangle |c(x)=1$ and $\langle \hat{x}, v \rangle | c(x)=-1$ will be well separated.

Advances in machine learning strongly suggest that (1) good representations exist, and (2) with enough data and computational resources we can find them.
Such representations directly implies classification (since it reduces tasks to linearly separable data).

While usually in theory we aim to explain why we can classify well, let's try to just assume we have a representation $Enc$ as a black box, and moreover that the representation is in the form of a Neural Network, and then try to work from there.
Maybe we can even assume that we have $Dec:\mathbb{R}^n \rightarrow \mathcal{X}$ as a black box.
That would mean that we can operate in the "good space" $\mathbb{R}^m$, and leave the question of how we get there to practice.

Note that we do _not_ assume that such a representation is "succinct". In particular it could well be the case that $\hat{x}$ contains some "spurious information" such as the raw pixels of $x$ in Images etc. We just assume that the representation of $\hat{x}$ is rich enough so that it can translate semantic functions to linear ones. In particular the distribution $\hat{X}$ will certainly have many correlations and so it will _not_ be distributed close to Normal.

We still need a notion of what it means to be a "natural distribution" $\hat{X}$ over $\mathbb{R}^m$.
One notion could be the following:

$\Pr[ \hat{X} = x] \propto \exp(-\parallel f(x) \parallel^2)$ for some "nice" function $f:\mathbb{R}^m \rightarrow \mathbb{R}^d$ and let's say that moreover the distribution $f(\hat{X})$ is indistinguishable from the normal distribution over $\mathbb{R}^d$.

This would mean that if we have an "inverter" $g:\mathbb{R}^d \rightarrow \mathbb{R}^m$ such that $g(f(\hat{x})) \approx \hat{x}$ with high probability over $\hat{x} \sim \hat{X}$, then we can sample from $X'$ by choosing $y \sim N(0,I_d)$ and outputting $g(y)$.

Indeed, suppose otherwise that there was a distinguisher $\hat{c} \in \hat{\mathcal{C}}$ between $g(N(0,I_d))$ and $\hat{X}$.

Then $\hat{c} \circ g$ would distinguish $N(0,I_d)$ and $f(\hat{X})$.

We call $f$ the "extractor", denote it by $Ext$ and $g$ the "generator" and denote it by $Gen$. Note that $Dec \circ Gen$ is a GAN.

## How to find such components

Suppose we have a pre-trained encoder $Enc$ and access to a natural distribution $X$. We can then try to find the smallest $d$ and NNs $Ext,Gen, Dec$ such that

$$Dec(Gen(Ext(Enc(x)))) \approx x$$

for $x\sim X$.

The idea is that by finding the smallest $d$ we force $Ext$ to erase any "raw pixel" or other "cheating methods", and this might ensure that $Ext(Enc(x))$ is as "distilled" as possible would would encourage it to be come indistinguishable from $N(0,I_d)$.

We can also try to look at variants such as checking that

$$Dec(Gen(\eta + Ext(Enc(x)))) \approx x$$

where $\eta \sim N(0,\delta \cdot I_d)$ is some "noise vector". This might help in ensuring we are not cheating by encoding in $d$ dimensions $\gg d$ numbers by abusing the low order digits.

### Completing a "learning system" without access to data

Suppose that we already have a "pre-trained" $Enc$ and $Dec$.
(This might happen if $Enc$ was obtained by taking a large corpus of data and doing completion tasks, which naturally yield $Dec$ as well.)
Then the following is a natural approach to complete the system and get $Ext$ and $Gen$ _without access to data_.
This can be useful if $Enc$ and $Dec$ have been trained with lots of data and compute that we don't have access to.

If we have both $Enc$ and $Dec$ then we could try to attempt to get $Ext$ and $Gen$ _without any access to data_ by trying to find the __largest__ $d$ and algorithms $Gen,Ext$ such that

$$Ext(Enc(Dec(Gen(y)))) \approx y$$

for $y \sim N(0,I_d)$. (Note that the larger $d$ is, since for example if we can solve the task for $d$, we can solve it for $d-1$ by just hardwiring a constant picked as random Gaussian to the last coordinate.)

The philosphy here is that if we assume that the set $\{ \hat{x}\in \mathbb{R}^m | Enc \circ Dec(\hat{x}) = \hat{x} \}$ corresonds to the manifold of the support of $\hat{X}$, then by making $d$ large we force $Gen$ to saturate this manifold.

Once again, we can also look at the noisy variant, looking for $Gen,Ext$ such that

$$Ext(Enc(Dec(Gen(\eta + y)))) \approx y$$

for $y \sim N(0,I_d)$ and $\eta \in N(0,\delta \cdot I_d)$.

### Thoughts on Preetum's comment

Preetum makes the very correct observation that the Decoder could be trivial.

To make this concrete, suppose that our data is composed of sentences or paragraphs, and we obtain the encoding by trying to impute 10% missing words from the remaining 90%.
The encoding of a sentence $x$ can be a concatenation of the values all the neurons of the networks when we do this for several different subsets.

The encoding contains inside it all the original words and there is a trivial decoder that will be successful with 100% probabilty, but we the "right" decoder would use the imuputations and so we can assume that the right decoder is not completely trivial.

One way to think of this is as follows - let $S \subseteq \mathbb{R}^m$ be the set of actual encodings that can arise from real sentences. For simplicity we can assume that the true distribution on data induces the uniform distribution over $S$.

If we are given an encoder and a decoder then we get from them the set $\tilde{S}$ which is the set of all encodin
gs $\hat{x}$ such that the encoding of the decoding of $\hat{x}$ is close to $\hat{x}$.

If the decoder is trivial then this set could be very large, but if the decoder is not trivial then $\tilde{S}$ could be a good approximation of $S$, and now we can hope to find $Ext,Gen$ that would allow us to give an approximation of the uniform distribution over $\tile{S}$.