learnable

From the perspective of an observer, a system is open-ended if and only if the sequence of artifacts it produces is both novel and learnable.

I.e. you have a system $S$ producing artefacts $X_{1\dots t\dots T}\in \mathcal{X}$ and an observer $O$ making statistical models $Y_t$ which based on $X$ up to $X_t$, which have a prediction error $l$ for arttifacts until $X_T$.

A system displays novelty if if artifacts become increasingly unpredictable with respect to the observersmodel at any fixed time $t$:

$$\forall t,\forall T>t,\exists T^{\prime }>T:\mathbb{E}[l(t,T^{\prime })]>\mathbb{E}[l(t,T)]$$

… there is always something more surprising coming in the future.

A system is learnable whenever conditioning on a longer history makes artifacts more predictable:

$$\forall T,\forall t<T,\forall T>t^{\prime }>t:\mathbb{E}[l(t^{\prime },T)]<\mathbb{E}[l,(,T)]$$

This can also be defined in terms of compression:

The observer $O$ processes an artifact $X_T$ to determine its information content given a history $h_t=X_{1:t}$ of past ones. $O$ posses a history-dependent compression map $C_{h_t}:\mathcal{X}\to \{0,1{\}}^{\ast }$ - the map encodes $X_T$ into a binary string of length $|C_{h_t}(X_T)$.

A system displays novelty if the information content increases, i.e. complexity increrases according to the observer:

$$\forall t,\forall T>t,\exists T^{\prime }>T:|C_{h_t}(X_{T^{\prime }})>|C_{h_t}(X_T)|$$

A system is learnable if conditioning on a longer history increaes compressibility:

$$\forall T,\forall t<T,\forall T>t^{\prime }>t:|C_{h_{t^{\prime }}}(X_T)|<|C_{h_t}(X_T)|$$

In other words, with a longer history (more data), the observer musst be able to keep extracting additional patterns that help it compress future artifacts.

Lossy compression is also allowed loss(decompress(compress(X)), X) < epsilon, can also get rid of explicit epsilon and analyse properties of the “rate-distortion” curves.

Link to original