Undecidability of determining if a pattern exists in a dataset [Proof request or work on it]

[JOSE ANTONIO MARTIN HERNANDEZ]

Hello, very often (mucho more than desired) I have to confront in my working place with people very tight to first principles modelling to create models or forward models about some plants or dynamical systems.

They usually argue that the proposed models learnt from data are not valid because there will be some patterns that are not in the historic data and then since models will not extrapolate well the data based models can not be used and first principles models should always be the choice.

Even after explaining many representation learning theories, about manifold learning in latent spaces, symmetry etc they still reduce the problem to the classical view of (inter/extra)polation.

Now my point is to find a proof, or develop a single one about that

1.- Determining if a pattern (in general) is in a dataset is an undecidable problem.

2.- It is more a regularity than an exception that argued non present patterns in a dataset are indeed contained, but implicitly, and that there exists a way of learning from them or that the learning machine is already affected by these hidden patterns.

Where to find material for  (1) ?

Any ideas or help?

Thanks a lot!

JAMH

[David Dowe]

Hi, Jose Antonio and other AIT readers, and I hope that all are well.

I hope that I have understood what you seek and that my answer is relevant, correct and clear.

Let D be a data-set and P be a pattern.

If we are doing inference relative to a (Bayesian) choice of (universal) Turing machine - let's

call it U - then the answers to the question(s) will sometimes depend upon the choice of U.

There will be cases where we can prove that D does have pattern P.

There will be cases where we can prove that D does not have pattern P.

The halting problem (or Entscheidungsproblem) is undecidable (Turing, 1936).  And, in turn,

there will be cases where (using UTM, U), for some D and P, we can't prove whether or not

D has pattern P.

There will also be cases of D where we can't decide whether or not D has any pattern (i.e.,

for all patterns P', we can't prove that D has pattern P'; and for at least one pattern P'', we

can't prove that D does not have pattern P'').

To see this described formally, then, as above, I first mention Turing (1936).

More recently than (Turing, 1936), with a view to data-sets and inferences (or

patterns), I would refer you to

Wallace, C.S. and D.L. Dowe (1999a), "Minimum Message Length and Kolmogorov Complexity", Computer J (special issue on Kolmogorov complexity), Vol. 42, No. 4, pp270-283 - and perhaps especially (within that

paper) to sec. 4, p275, col. 1, C6 and the non-computability of K_T (S).

I hope that I have understood what you seek and that my answer above is relevant,

correct and sufficiently clear.

This all said (at least partly by way of theory), in practice, many data-sets have patterns

and we can often do many useful things with a pattern in a data-set even if we possibly

don't have the best possible pattern.

As a simple case in point, Einsteinian special relativity currently appears to be a better

theory than Newtonian mechanics but we can still do many useful things with Newtonian

mechanics (and we can indeed see Newtonian mechanics as something of a small-speed

approximation to Einsteinian special relativity).

That's probably an okay time to stop.

In the rest of this e-mail, which you can safely ignore, we assume that determining

whether a pattern is in a dataset is decidable in general - and then see the resultant

paradox and contradiction.

For what it's worth, I'd now like to use our inference techniques to make an

uncomputable sequence.  Put another way, we assume that determining whether a

pattern is in a dataset is decidable - and, in turn, that finding the best pattern in a

dataset is decidable (or determining whether or not a pattern is the best pattern in a

dataset is decidable) - and then see where this leads us.  (As we shall see below, it

will lead us to a paradox and contradiction.)  We start with a problem which can be

viewed as infinitely iterated matching pennies, or what has previously been called the

elusive model paradox.  We have a matcher and a mismatcher, where the matcher is

like a tennis receiver or soccer goalie/goalkeeper trying to match where the server /

/ striker directs the ball; and the mismatcher is like a tennis server or soccer striker

trying to place the ball where the receiver / goalkeeper does not go.

Having set things up (as above), the argument continues as follows.  After many iterations,

the mismatcher should be able to infer the matcher's algorithm (with very high probability)

and (vice versa) the matcher should be able to infer the mismatcher's algorithm (with very

high probability).  In turn, the mismatcher can then make sure of a mismatch (with very

high probability) and the matcher can then make sure of a match (with very high probability).

This gives a paradox - and the resolution of the paradox is that the inference/s is/are (in

general) not computable.

Various people to have written on this - in one form or another - include M Scriven (1965),

D K Lewis and Jane Shelby Richardson (1966), A P Dawid (approx 1985), D L Dowe (2008, 2011),

R J Solomonoff (2011).  Perhaps most recent is Michael Brand and David L. Dowe (2017),

"The IMP game: Learnability, approximability and adversarial learning beyond Σ01", J Logic and

Computation, Volume 27, Issue 7, October 2017, pp 2171–2192, https://doi.org/10.1093/logcom/exw031 .

I hope that all of this helps.

Keep well,  cheers  and  best    from David D

More information: http://www.hutter1.net/ait.htm
---
You received this message because you are subscribed to the Google Groups "Algorithmic Information Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ait0+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ait0/CAL_Z42WW5xga54oPxmLTQ-jWfKj7iqxhkw%3Drg4-bCsVKQpBjiQ%40mail.gmail.com.

[Schmidhuber Juergen]

Sorry to chime in here. The result on the halting problem is NOT due to Turing (1936) [TUR]. The halting problem was named by Davis in 1958 [HLT58] and formulated by Kleene in 1952 [HLT52][HLT21]. Interestingly, Church’s 1935 notion of computation [CHU] included termination, Turing’s of 1936 [TUR] did not!

The result on the decision problem wasn’t due to Turing either. In 1935, Church derived a corollary / extension of Gödel's results (1931-34) [GOD][GOD34] on the limits of computation and theorem proving, by demonstrating that Hilbert & Ackermann's Entscheidungsproblem (decision problem) does not have a general solution [CHU]. All references and more in:

[TUR21] J. Schmidhuber (AI Blog, Sep 2021). Turing Oversold. It's not Turing's fault, though. https://people.idsia.ch/~juergen/turing-oversold.html

BTW, what exactly did Turing [TUR] and Post [POS] do in 1936 that hadn't been done earlier by Gödel [GOD][GOD34] (1931-34) and Church [CHU] (1935)? There is a seemingly minor difference whose significance emerged only later. Many of Gödel's instruction sequences were series of multiplications of number-coded storage contents by integers. Gödel did not care that the computational complexity of such multiplications tends to increase with storage size. Similarly, Church also ignored the context-dependent spatio-temporal complexity of the basic instructions in his algorithms. Turing and Post, however, adopted a traditional, reductionist, minimalist, binary view of computing. Their machine models permitted only very simple elementary binary instructions with constant complexity, like the early binary machine model of Leibniz (1679)[L79][LA14][HO66] and Zuse's 1936 patent application [ZU36]. They did not exploit this—Turing used his (quite inefficient) model only to rephrase the results of Gödel and Church on the limits of computability. Later, however, the simplicity of these machines made them a convenient tool for theoretical studies of complexity. (I also happily used and generalized them to obtain results on Kolmogorov complexity for the case of never-ending computations [ALL2].)



Jürgen Schmidhuber
Director, AI Initiative, KAUST
Scientific Director, Swiss AI Lab IDSIA
Adj. Prof. of Artificial Intelligence, USI
Co-Founder & Chief Scientist, NNAISENSE
https://people.idsia.ch/~juergen/blog.html

> To view this discussion on the web visit https://groups.google.com/d/msgid/ait0/CAB-hagSoU8O-WDBPObrtrCOCPUo5dxweP5y7GAvyuz0xyGyomw%40mail.gmail.com.

[Marcus Hutter]

Symposium on Algorithmic Information Theory and Machine Learning,
4 -5 July 2022, Alan Turing Institute, London, UK
https://sites.google.com/site/boumedienehamzi/symposium-on-algorithmic-information-theory-and-machine-learning

The goal of this symposium is to explore the interface between
Algorithmic Information Theory (AIT) and Machine Learning (ML).

Algorithmic Information Theory studies complexity measures on data
structures and the goal of this symposium is to bring together
researchers applying tools of AIT, and particularly Kolmogorov
Complexity, to ML in order to identify the domain of applicability of
certain ML methods and explain, for example, why certain methods in ML
will a priori work so well for certain problems or a priori won't work
for other problems. Other questions of interest are the applications of
Solomonoff induction, algorithmic probability approaches to probability
predictions, links between information, learning, and data compression,
developing/using ML algorithms for (better) compression/prediction
trying to approximate Kolmogorov Complexity etc.

Organizing committee: Boumediene Hamzi, Kamaludin Dingle, Marcus Hutter,
and Robert MacKay.

If you are interested in attending the event in-person or online, please
fill the form here.
https://docs.google.com/forms/d/1pYp0x5qTQNj7tfElsXx-TninWvSEU1neCd1EnEnsjpo/edit

If you are interested in giving a talk, please contact Boumediene Hamzi,
<bha...@turing.ac.uk>

Food and Refreshments: During all days, morning and afternoon drinks and
snacks are provided during dedicated Refreshment Breaks. Participants
are advised to make their own arrangements during the Lunch Breaks
(there are different options inside and around the British Library).