On Autistic Interpretations of Occam’s Razor

Jose Hernández-Orallo^{1} and Ismael García-Varea^{2}

Abstract. Recently, an overhype about the MDL principle is surrounding some fields of Artificial Intelligence, especially machine learning, neural networks, ILP and many others, supported by recent proofs that the shorter the more likely. In this paper we discuss in a critical and sometimes informal way these justifications because they are proved for very ideal, infinite and, in our view, artificial situations. Using the same information-theoretic approach, we study the case for finite and short data and we arrive to a slightly different result: MDL is a good principle but not the best one for finite strings and perfect hypotheses. The argument is based upon recently introduced variants and definitions around the idea of Intensional Complexity, which penalise or ’simply’ do not allow exceptions, seen these as extensional descriptions. Intensional considerations change the statement that “optimal compression (Minimal Description Length (MDL)) gives you the best hypothesis provided the data are random with respect to the hypothesis, the data are not completely perfect and the data grow to infinity” into the following one “the intensionality criterion gives you a more feasible hypothesis when the data are perfect ensuring and not supposing that the data are random to the hypothesis.” Also it does not require that the data grow to infinity, so it can be used to “understand” finite real problems. More importantly, our definitions are free from the “MDL’s principle” paradox, since the shortest hypothesis is never random to the data. In one of the two formalisations we present, the connection with learning and Levin’s “Universal Search Problems” is made explicitly. In the end, and very far from the classical notion of ’identification’, we propose a different notion of learning: the more a system learns the more intensional the description is respect to the data. Consequently the blurry notions of underfitting and overfitting may be better understood.

1 Introduction

After the initial relevance of deduction in AI, nowadays its counterpart, inductive learning, and all its varieties (abductive reasoning, reasoning by analogy, connectionism, ILP, grammatical inference, HMM, EBR, etc.), are beginning to play the more central and still agglutinative role in the proper subset of AI devoted to make intelligent machines.

This has motivated new unified frameworks for understanding reasoning. In particular, a radical approach has been undertaken by Wolff, with the claim that “all kinds of computing and formal reasoning may usefully be understood as information compression by pattern matching, unification and search” [40].

In this paper, we will discuss critically a central and now classical issue in this line, which is based on the view of unsupervised learning as compression [31], its famous operative principle MDL [27] and, mainly, its formal justification. The

1 Universitat Politècnica de València, Departament de Sistemes Informàtics i Computació. Camí de Vera 14, Aptat. 22.012 E-46071, València, Spain. E-mail:jorallo@dsic.upv.es

2 Universitat Politècnica de València, Institut Tecnològic d’Informàtica. Camí de Vera 14, Aptat. 22.012 E-46071, València, Spain. E-mail:ivarea@iti.upv.es

discussion is motivated from the apparent contradiction between the so-called “no-free-lunch” theorems about induction [41] [29] stating that one learner cannot be better than another when performance is averaged uniformly over all possible problems. These results only allow that a learner could be better than another for a particular distribution of problems.

[36] show that the MDL principle is almost optimal for the universal distribution 2^{−K(x)}. Of course, universal distribution is an objective choice when you have not any information at all about the real origin of the information, but is this the case in real applications of machine learning? Are we always so autistic about the source of the information that we pretend to learn?

After this discussion under the view of an intensional variant of Kolmogorov Complexity, we will introduce some considerations on knowledge construction, meaning and ontology, which are also capital questions in AI.

2 Learning by Data Compression

Recently, there is some kind of overhype [26] [13] [16] [15]

[23] [42] [25] [14] about unsupervised learning and pattern recognition as data compression [39] and Rissanen’s Minimum Description Length Principle (MDL) [27]. This is a variant of the Minimum Message Length (MML) principle [38] but the idea is formally older [31]. They all are “fresh interpretations”

[14] under Algorithmic Information Theory of a much older idea attributed to William of Ockham 1290?-1349?:

Occam’s Razor Principle: “If there are alternative explanations for a phenomenon, then, all other things being equal, we should select the simplest one.”

This principle was rejected by Popper because he said that it had no sense because there is no objective criterion for simplicity. But Algorithmic Complexity C(x) or Kolmogorov Complexity K(x) is an objective criterion for simplicity. This is precisely what R.J.Solomonoff proposed as a perfect theory of induction, in [36] words. Algorithmic Complexity inspired J. Rissanen in 1978 to use it as a general modelling method, giving the popular MDL principle [27]:

Minimum Description Length (MDL) principle: The best theory to explain a set of data is the one which minimises the sum of: the length, in bits, of the description of the theory; and, the length, in bits, of data when encoded with the help of the theory. Then, we enclose the exceptions, if any.

This principle is not computable in general and it can only be used if we restrict the descriptive mechanism. The first justified reason to use the MDL principle is to avoid overgeneralisation.

But MDL is used mainly for another reason, “the shorter the hypothesis the more predictable it is”. This has been proved for statistical prediction. In [36] and [37] it is shown that in many cases Bayesian reasoning “is prone to overfitting” while MDL is not. [35] discuss an “ideal MDL principle” where “with a more complex description of the hypothesis H, it may fit the data better and therefore decreases the misclassified data. If H describes all the data, then it does not allow for measuring errors. A simpler description of H may be penalized by increasing the number of misclassified data. If H is a trivial hy-

\begin{matrix}c \\ ◯ \end{matrix} 1998

Submitted to ECAI 98 March 3, 1998

pothesis that contains nothing, then all the data are described literally and there is no generalization. The rationale of the method is that a balance in between seems required [...]”.

Based on a transcription of Bayes’ formula, [36] demonstrate that compression is almost always the best strategy in prediction methods in the style of R. Solomonoff [32]. With these considerations in mind it was recognised [31] that the unsupervised learning of a grammar from raw data may be understood as information compression.

3 Incremental Learning and MDL

With the ideas of compression more or less patent there were presented different models of learning: identification in the limit [18], PAC model [34], Query-Learning [2] and others, all based on the ideas of ’identification’. Although the other models have brought learning to tractability, it is identification in the limit “the model that embodies all the salient features of learning by example, and nothing else” [17]. Generally these paradigms are parametrised in the number of errors a, the number of mind changes b and, for PAC learning, other reliability considerations.

3.1 Cumulative Incremental Learning

Some recent different approaches [28] are beginning to question that the preceding models were sufficient to comprise some learning tasks. The most interesting objection is the view that learning is an incremental process [1]. The new goal is not necessarily to achieve the highest accuracy at the end of a learning session, but to maximise the cumulative benefits obtained throughout all the session. But is there any principle to achieve the best reliability during cumulative learning?

The relation between compression and function identification in the limit was studied by different authors [5], [12] and [10] under the notion of nearly minimal programs function identification. The results support the idea that MDL minimises the number of mind changes b. Consider that after a counterexample n, the MDL nth hypothesis generally remakes to the same n − 1th hypothesis just adding the exception. In this way, the hypothesis becomes patched for a time until the length of coding the exceptions forces the appearance of a new radical hypothesis. This makes the MDL rather conservative, so minimising mind changes.

But our goal in cumulative learning is to find the solution the sooner the better in order to begin to sum hits instead of prediction errors. Shortly; the more tolerant with exceptions the less the accuracy in cumulative incremental learning.

3.2 MDL and perfect finite data

MDL has another problem, it is usually not suitable for short finite strings, because exception-based descriptions are shorter. Let us see these three problems in an example:

EXAMPLE 3.1 Consider the finite sequence: x = 1, 2, 3, 5, 7. From the infinite number of hypotheses, we can guess some short hypotheses or descriptions for x, simply “the sequence 1,2,3,5,7”, or “the first four odd numbers and the number two, ordered”, or “the first three natural numbers and the number 5 and 7”, or “begin with numbers 1,2. The following three are the sum of their preceding two, but decrementing the last one” or “the first five numbers which are dividable only by 1 and itself”. Almost everybody would select the last hypothesis as the more explanatory. But it is not the shortest one. But it is a short exception-less hypothesis. In fact, it is able to predict reliably the following value (11) because using that description, the right half of x reinforces the hypothesis while the others are weakened.

An immediate critique to this example is that the probability of 11 as being the correct answer is the same (or less according to the MDL) and it is only the assumption that the concept of prime is well known by humans which increases our probability of guessing 11. We think this is not accurate in this case because the shortest description “the first four odd numbers and the number 2” has an exception which “perverts” the hypothesis, although it would be the “elegant” program in Chaitin’s LISP. In general, MDL has been used successfully because the strings are long enough or the bias has been selected to ban exceptions.

The rationale is that if we fix a = 0 (i.e., no errors) “11” cannot be noise because we expect the source to be deterministically produced by an algorithm and to be without errors of production or transmission. In these cases, MDL fails. This has been recognised by [35]: “With some amount of overstatement one can say that if one obtains perfect data for a true hypothesis, then Ideal MDL interprets these data as data obtained from a simpler hypothesis subject to measuring errors. Consequently, in this case Ideal MDL is going to give you the false simple hypothesis and not the complex true hypothesis.”

In the end, [35] conclude “Ideal MDL only gives us the true hypothesis if the data satisfies certain conditions relative to the true hypothesis. Stated differently: there are only data and no true hypothesis for Ideal MDL. The principle simply obtains the hypothesis which is suggested by the data and it assumes that the data are random with respect to the hypothesis.”

The fact that MDL is not optimal when data are not statistically in nature or finite, may lead us to the despondent opinion that we will never be able to distinguish exceptions from noise. On the contrary, Kolmogorov complexity is the key to find a new principle that ensures (and not simply assumes) that “the data are random with respect to the hypothesis.”

4 Intensional Complexity

In the following subsection, we will require the concept of characteristic subprogram (or main rule), which is usually a problem of the meta-theory. We try to approximate it in the theory using the idea of a characteristic subsequence (or supersequence):

DEFINITION 4.1

A string y is close or characteristic to x, denoted y^{}x̸, iff C(y|x) ≤ C(y)^{1/2}.

Being C(y) the algorithmic complexity of y (the length of its shortest description) and C(y|x) the conditional complexity of y, given x. The use of the 1/2 exponent is arbitrary and we normally understand y is characteristic to x when C(y|x) ≪ C(y). Generally, any “quite random” substring y of x with length l(y) ≤ l(x)/2 is characteristic to x. Also in general, any short y will never be characteristic.

4.1 Exceptions in a Description

There is some ambiguity in the preceding definition. Now, we pretend to identify, in the very theory, the number of exceptions in a description (hypothesis) according uniquely to the information of both description and data. The following definition matches with intuition and works in many representation languages. Obviously, it can give some awkward results for some very special cases. Usually, it might be more practical to ban or to reckon quoted exceptions in the description mechanism, but this can be cheated in many ways, as we will see later.

The following is the more stable definition we have found of the number of exceptions in a hypothesis.

DEFINITION 4.2

The number of r−exceptions ∇_{x}(p_{x}) of a description p_{x} for x is defined in the following way:

∇_{x}(p_{x}) = max|l(y) − l(x)|, such that

∃y, p_{y} ϕ(p_{y}) = y and p_{y}^{}p̸_{x} and l(p_{x}) − l(p_{y}) ≥ C(y|x)/r.

∇_{x}(p_{x}) = 0 if such a y cannot be found.

From here, we can define that p_{x} is r-exception-free or rrobust iff ∇_{x}(p_{x}) = 0. Intuitively, p_{x} is r-exception-free iff there is not a subprogram (p_{y}^{}p̸_{x}) whose reduction in size (l(p_{x}) − l(p_{y})) is greater than the effect change C(y|x).

The parameter r may serve to adjust the definition to different representations or biased. If r = ∞ we have that there is no exception-free description. If r = 0 we have that no description has exceptions. The greatest value of r such that ∇_{x}(p_{x}) = 0 is the ’robustness’ of a description.

4.2 Intensional Complexity

DEFINITION 4.3 The Shortest r−Intensional Description p of a string x, denoted SID_{r,e}(x), is defined as follows: SID_{r,e}(x) = argmin{l(p) : ϕ(p) = x ∧ ∇_{x}(p_{x}) = e}

With this definition we can formulate the: Shortest Intensional Description (SID_{1,0}) principle:

The best theory to explain a set of data is the one that minimises the length, in bits, of the description of the theory; and contains no implicit or explicit exceptions.

This idea of implicit exception tries to emphasise that the concept of exception is deep, and it follows from the preceding definition 4.2. Due to the non-computability of SID (as the MDL principle) it may be understood as a limit to come close. Comparably we have,

DEFINITION 4.4 The Intensional Complexity of a string x, denoted E_{r,e}(x), is defined as E_{r,e}(x) = l(SID_{r,e}(x)).

Clearly it can be seen that E_{0,0}(x) = E_{∗,l(x)}(x) = C(x) and that E_{∞,0}(x) is undefined. In this way, E_{r,e}(x) can be regarded as a generalised version of C(x).

4.3 Hypothesis Reliability and SID

DEFINITION 4.5 An nth hypothesis (given n+1 examples) is k−reliable iff the hypothesis has remained unchanged during the m last examples, being k = m/n.

CRITERION The SID principle is a right principle to achieve Hypothesis Reliability during Cumulative Incremental Learning from exact (a = 0) and ’non-whimsical’ sources.

INFORMAL JUSTIFICATION The probability that the last hypothesis had been older is greater because exception-avoidance discards whimsical and noisy descriptions and consequently the “correct” hypothesis has been sought sooner, maximising m and k accordingly.

The criterion is reinforced intuitively. Note that the assumptions that the data are random with respect to the hypothesis, the data are not perfect and grow to infinity are changed into the claim: “intensional criteria gives you the more feasible hypothesis to a perfect sequence of data the more the intensionality (randomness between data and description)”.

5 On Randomness and Intensionality

The preceding definitions try to ensure that there is no extensionality, i.e., the hypothesis is really random to the data. Their introduction is supported by the MDL principle’s paradox: to prove the optimality of the MDL principle, it must be supposed the “randomness of the hypothesis to the data”. But given the data x and the hypothesis x^{∗} obtained from the MDL principle, we have that x^{∗} can be described from the data very shortly in the following way “the shortest description for x”. So, C(x^{∗}|x) is very short and consequently x^{∗} is not random to x. Strictly, this is a paradox and not a formal contradiction because the shortest string is not computable. But this does not relieves us too much. In our opinion, the only way out is a length-time (LT) foundation.

DEFINITION 5.1

The Intensionality of a description (hypothesis) h for data x is defined as:

I(h|x) = Ct(h|x)/Ct(h) being Ct(x) = argmin{LT (p) : ϕ(p) = x} and Ct(h|x) = argmin{LT (p) : ϕ(p, x) = h}

We choose LT_{β}(p) = l_{β}(p)+log cost_{β}(p) (the same weighing as [21]’s Kt) because it provides a good compromise between space and time, but another relation could be tuned.

The definition yields an interval (0, 1] of intensionality that comes to say that when I is near to the maximum 1, a great computational effort (in information and time) is needed to compute the hypothesis from the data. Therefore, the data are useless to describe it. Contrariwise, when I is near to the minimum log l(z)/l(z) (very close to 0) it means the data have been described completely in an extensional way.

Definition 5.1 clarifies some open questions of the convenience of both compression and exception-allowance. First, the shortest hypothesis h_{z} for random data z is the most extensional one “print z”. Clearly, no learning has taken place and no prediction accuracy can be expected for future data. In fact I(hz|z) ≈ log l(z)/[l(z)+log l(z)]. If z is slightly long, this is practically zero. Secondly, a 6th order polynomial p_{w} for the string w = “1,2,3,5,7,11” would be ’intensional’ according to definition 4.2. But such a polynomial is simply the extensional data ’hidden’ in a very convenient way, but no intensionality exists and not much learning has taken place. In fact I(p_{w}|w) is low because p_{w} can be better described (according to LT) from the data w because the operations op to transform them into p_{w} are short enough to make log(op) lower than describing directly p_{w}. Compare to the case where the hypothesis is p′_{w} = “the first 6 primes”. Maybe Ct(p′_{w}) is quite long but Ct(p′_{w}|w) is just the same, giving an I(p′_{w}|w) = 1.

6 Is MDL a myth?

Definitions of section 4 are introduced for “perfect origins”. These kind of data is only present in human problems because the world (the real environment) is essencially a statistical source. In fact, Occam’s Razor has been proved using a similar approach to the preceeding one, but using Jeffrey’s prior and Statistical Mechanics techniques [3] or shown useful under energy/entropy considerations [19] [33] [20].

So, with deterministic and perfect data, is it an illusion to think that the shortest program without exceptions is good? Is it just a matter of ease of management? Why do we have to suppose the universal distribution for practical problems?

In our opinion, the limited resources of the learning machine makes that the real reasons why the MDL principle is “right” are:

1. In any problem (and the world in general), there is no infinite (in space and time resources) source machine. The more common cases are short machines whose effects are almost immediately perceived.

2. Any learning machine has not infinite resources, either.

3. According to point 1, it is usually computational easier to deduce the facts from the rules than to induce the rules from the facts. That is to say, information is not reversible under deduction transformations in normal (non-reversible) machines [36].

4. The longer the hypothesis, the more difficult to check that there are not “hidden” exceptions, i.e., the data is explained extensionally and not intensionally, given a “fantastic” abstraction (in some way this is overfitting the data). Recall that the better way to cheat someone is using long and intricate arguments.

The last point can be stated more formally:

Theorem 1 If the hypothesis is very short respect to the data there is a great probability that it is intensional. That is to say, if the data grows to infinity and the hypothesis remains finite, the intensionality is always 1.

PROOF The compression ratio is defined ρ(h|x) = l(h)/l(x). The more ρ(h|x) → 0 the more that Ct(h|x) ≈ Ct(h) since the data are so large and the hypothesis is so short that the data is useless to help to describe the hypothesis. Consequently I(h|x) = Ct(h|x)/Ct(h) → 1.⋄

It is important to make clear that Theorem 1 does not say that the shorter the hypothesis respect to the data the more likely that it is intensional. This is only the case when ρ(h|x) → 0, i.e., for good compression ratios, as when x is infinite and h finite, obviously.

MDL works well because in general the biases or representation used ban or penalise exceptions, the computational time is not much variable or the number of samples is great enough to make the compression ratio appropiate. This is the case in ILP, decision trees and grammatical inference where the MDL principle has been used succesfully because their deductive relation between semantics and syntax is clear, not like Turing Machines or other mechanisms. [30] said that logic has natural semantics and quantification is a very easy way to ease intensionality (Non-Terminals make the same role in grammatical inference). So, the MDL principle has been used successfully to the inference of logic programs [30] [22] [24].

However, the following theorem advocate for the claim that deduction has to be much simpler than induction.

Theorem 2 If an algorithm A^{∗} ∈ p (i.e. polynomic), say O(n^{p} − 1) ≤ O(A^{∗}) ≤ O(n^{p}), is used to learn some data x, being n = l(x), then no hypothesis with Ct(h) > p log n can make I(h|x) = 1.

Theorem 2 means that, when using a polynomic learning algorithm, a compression ratio between data and hypothesis much greater than n/(p log n) is required, which, for n great and p low (as it is usually the case) is a very strict and difficult requirement. This supports the thesis that efficient algorithms that work exclusively from the data cannot learn intensional hypothesis or, seen the other way, efficient algorithms always quote ’shallowly’ part of the data. Only the context, that thing which is not pretended to be learned, serves to generate the hypothesis by trial and error or by less drastical approaches, like genetic algorithms. Example: By a learning algorithm of O(n^{5}) and n = 4096, we require that Ct(h) ≪ 60 to have some probability that the intensionality of the hypothesis could be 1.

PROOF OF THEOREM 2: For every string of data x to be learned, let us take the hypothesis which is constructed in the following way: h = “apply A^{∗} to x”. Since Ct reckons the best case, we have that Ct(h|x) ≤ O(1) + log Cost(A^{∗}, x) ≤ log n^{p} = p log n. If, as supposed, Ct(h) is greater than p log n, then the quotient Ct(h|x)/Ct(h) < 1.⋄

We have essayed adaptations of the SID principle (or the corresponding variant based on Ct instead of C) on some typical problems of ILP and grammatical inference and it selects the ’correct’ hypothesis with a minimal number of samples.

Also a similar principle derived from I(h|x) can be used instead. The risk to ’inflate’ the hypothesis from the data in order to approach to 1 is diminished by the fact that it would make Ct(h) also very great. In this case, the ideas of exception and intensionality are mixed in a single principle. This makes possible the learning form imperfect finite data, where the distinction cannot be made. Suppose you have a source where you expect an error range of [5% - 10%] of transmission or measurement to some data x. If you find a hypothesis where I(h_{u}|x) ≈ 1 you must discard it because it is too much perfect for the data (and it is not much probable that the errors would eventually fit in the correct hypothesis). Also, if you find another hypothesis where I(h_{o}|x) is too low you must also discard it because it is too much extensional for the data. Loosely, h_{u} and h_{o} can be considered under- and over-fitting, respectively.

7 On Meaning and Ontology

In general, when no information about the source of the data is known, an intensional short hypothesis for a data is so rare that our belief in it is much greater than whatever other less intensional hypothesis. Our ontology of the hypothesis as the cause of the data is reinforced.

Although the idea of intension is older in philosophy, Carnap [9] suggested that the intension of a predicate is its extension in all possible worlds. If we regard the input samples given to the learner upto a moment as “the real world”, a concept G used for all the given data (always true in a real world) rather than only a part, is more probable to hold for every future input sample (every possible world).

Suppose we have a set of data S, where we found a minimal description T = {T_{1}, T_{2}, ..., T_{n}} being T_{i} aparently independent among them and covering completely and disjointly S. T is clearly non intensional and it can be considered a clustering of data S. We found another description T = {G, T′_{1}, T′_{2}, ..., T′_{n}}, which is longer, where some scarce common information of the T_{i} has been extracted using a huge generalisation theory G yielding the T′_{i}. Now T′ is more intensional because only subprograms composed of G and some T_{i} could cover some data. If n would never great enough to justify (by the MDL point of view) the introduction of G we realise that the point in this process is that some information is shared, although compression has not taken place. This allows that some ontology and reinforcement can be partaken among previously “independent” data. Another interesting detail here is that this contrastation can be made now using G in a deductive way.

8 Conclusions

Theoretical models of learning based on the idea of ’identification’ which have been thoroughfully studied in machine learning (especially COLT), affirm that a system S has learned a language L when you find a hypothesis H such that S(H) = L. This is effectively so because L is considered infinite and therefore I(H|L) = 1. But under this paradigm, given a finite L, a simple parrot-fashion “memoing” algorithm would formally learn.

It is the avoidance of extensionality the right principle that must be ensured to affirm that real learning has taken place. SID also explains why there is nothing like “hyper-learning” or “poverty of stimulus” in those cases where MDL cannot give the “intuitive” hypothesis in most of the bias. In fact, the data are sufficient to induce the hypothesis. Theorem 1 shows that the more you compress the more probability that you have learned, but some examples on definition 5.1 show that when the compression ratio is not good, it is more reliable to compute which is the real intensionality of the hypothesis.

We are conscious that the sketch we have presented must be ensured before beginning to question some classical approaches in machine learning. For the moment, a lot of work has to be done to develop, improve and connect these ideas, possibly toward the related area of cryptography, because (from our definition of intensional) a good hypothesis is that which is hidden from the data in one sense (data → hypothesis) but plain in the other (hypothesis → data). This supports the idea of learning by trial and error, guided by the context and not by the data. Any heuristic that works strictly from the data will require a lot of “asymmetrical” computation in order to ensure that Ct(h|x) ≈ Ct(h). So it cannot be an efficient heuristic.

In conclusion, MDL principle works well in those environments where the bias does not allow extensional descriptions or where the data are huge and from statistical or imperfect sources. But, when faced to a concrete learning problem, we have to tune length, computational time and robustness (or intensionality) of descriptions according to the expectation we have about the source of knowledge. In our view, Occam’s Razor should be understood in this non-autistic way.

REFERENCES

[1] Abe, N. “Towards Realistic Theories of Learning”. New Generation Computing, 15, 1997.

[2] Angluin, D. “Queries and concept learning”. Machine Learning 2, No. 4, pp. 319-342, 1988.

[3] Balasubramanian, V. “Statistical Inference, Occam’s Razor, and Statical Mechanics on the Space of Probability Distributions”. Neural Computation, 9, pp. 349-368, 1997.

[4] Blum, M. “A machine-independent theory of the complexity of recursive functions”. J. ACM 14, 4, 322-6, 1967.

[5] Blum, L.; Blum, M. “Towards a mathematical theory of inductive inference”. Inform. and Control 28, pp. 125-155, 1975.

[6] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M.K. “Occam’s razor”. Inf.Proc.Lett. 24, pp. 377-380, 1987.

[7] Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. “Learnability and the Vapnik-Chervonenkis Dimension”. Journal of ACM, 36, pp. 929-965, 1989.

[8] Board, R.; Pitt, L. “On the necessity of Occam algorithms”. In Proc., 22nd ACM Symp. Theory of Comp., 1990.

[9] Carnap, R. “Meaning and necessity: A study in semantics and modal logic”. Chicago, University of Chicago Press, 1947.

[10] Case J.; Smith, C. “Comparison of identification criteria for machine inductive inference”. Theoret. Comput. Sci. 25, pp. 193-220, 1983.

[11] Chaitin, G.J. “Algorithmic Information Theory”. Fourth printing, Cambridge University Press, 1992.

[12] Chen, K. “Tradeoffs in inductive inference of nearly minimal sized programs”. Inform. and Control 52, pp. 68-86, 1982.

[13] Cheeseman, P. “On finding the most probable model”. In Shrager, J. and Langley, P. “Computational models of scientific discovery and theory formation”, chapter 3, Morgan Kaufmann, 1990.

[14] Conklin, D.; Witten, I. H. “Complexity-Based Induction”. Machine Learning, 16, pp. 203-225, 1994.

[15] Derthick, M. “The Minimum Description Length Principle Applied to Feature Learning and Analogical Mapping”. MCC Technical Report Number ACT-CYC-234-90, 1990.

[16] Freivalds, R. “Inductive inference of minimal size programs”. In M. Fulk and J. Case (eds) “Proceedings of the third Annual Workshop on Computational Learning Theory”, pp. 1-20, Morgran Kaufman, San Mateo, CA, 1990.

[17] Freivalds, R.; Kinber, E.; Smith, C.H. “On the Intrinsic Complexity of Learning”. Inf. and Control 123, pp. 64-71, 1995.

[18] Gold, E. M. “Language Identification in the Limit”. Inform and Control, 10, pp. 447-474, 1967.

[19] Gull, S.F. “Bayesian inductive inference and maximum entropy”. In Maximum Entropy and Bayesian Methods in Science and Engineering, Vol. 1: Foundations, de. by G.J. Erickson and C.R. Smith, pp. 53-74. Dordrecht: Kluwer 1988.

[20] Hinton, G.; Zemel, R. “Autoencoders, minimum description length, and Helmholtz free energy”. In Cowan, J., Tesauro, G., and Alspector, J. (eds.) Advances in Neural Information Processing Systems 6, Morgan Kaufmann Publishers, San Francisco, CA., 1994.

[21] Levin, L.A. “Universal search problems”. Problems Inform. Transmission, 9, pp. 265-266, 1973.

[22] Muggleton, S. “Inductive Logic Programming”. New Generation Computing, 8, 4, pp. 295-318, 1991.

[23] Muggleton, S.; Srinivasan, A.; Bain, M. “Compression, significance and accuracy”. In D. Sleeman and P. Edwards (eds.) Machine Learning: Proceedings of the Ninth International Conference (ML92), pp. 523-527, Wiley 1992.

[24] Muggleton, S. “Inverse Entailment and Progol” New Generation Computing, 13, pp. 245-286, 1995.

[25] Pfahringer, Bernhard. “Controlling Constructive Induction in CiPF: An MDL Approach”. In F. Bergadano and L. de Raedt (eds) Machine Learning, Proceedings of the European Conference on Machine Learning (ECML-94), pp. 242-256, Lecture Notes in AI 784, Springer-Verlag 1994.

[26] Quinlan, J.; Rivest. R. “Inferring decision trees using the minimum description length principle”. Information and Computation, vol. 80, pp. 227-248., 1989.

[27] Rissanen, J. “Modelling by the shortest data description” Automatica-J.IFAC, 14, pp. 465-471, 1978.

[28] Rivest, R.L.; Sloan, R. “A Formal Model of Hierarchical Concept Learning”. Inf. and Comp. 114, pp. 88-114, 1994.

[29] Schaffer, C. i “A conservation law for generalization performance”. In Proceedings of the Eleventh International Conference on Machine Learning, pp. 259-265, Morgan Kaufmann, 1994.

[30] Shapiro, E. “Inductive Inference of Theories form Facts”. RR 192, D. Comp. Science, Yale Univ., 1981, in Lassez, J.; Plotking, G. (eds.) “Computational Logic”, The MIT Press 1981.

[31] Solomonoff, R.J. “A formal theory of inductive inference”. Inf. Control. Vol. 7, 1-22, Mar., pp. 224-254, June 1964.

[32] Solomonoff, R.J. “Complexity-based induction systems: comparisons and convergence theorems”. IEEE Trans. Inform. Theory, IT-24, pp. 422-432, 1978.

[33] Stolcke, A.; Omohundro, S. “Inducing Probabilistic Grammars by Bayesian Model Merging”. In R.C. Carrasco and J. Oncina (Eds.) Grammatical Inference and Applications, Lecture Notes in Artificial Intelligence, 862, pp. 106-118, Springer-Verlag 1994.

[34] Valiant, L. “A theory of the learnable”. Communication of the ACM 27(11), pp. 1134-1142, 1984.

[35] Vitanyi, P.; Li, M. “Minimum Description Length Induction, Bayesianism, and Kolmogorov Complexity”.

[36] Li, M.; Vitanyi, P. “An Introduction to Kolmogorov Complexity and its Applications” 2nd Ed. Springer-Verlag, 1997.

[37] Vitanyi, P.; Li, M. “On Prediction by Data Compression”.

[38] Wallace, C.S; Boulton, D.M. “An information measure for classification”. Computing Journal 11, pp. 185-195, 1968.

[39] Watanabe, S. “Pattern Recognition as Information Compression”. In Watanabe (ed.) Frontiers of Pattern Recognition New York: Academic Press, 1972.

[40] Wolff, J.G. “Computing as Compression: An Overview of the SP Theory and System”. New Gen. Computing 13, pp. 187-214, 1995.

[41] Wolpert, D. “On the connection between in-sample testing and generalization error”. Complex Systems, 6, pp. 47-94, 1992.

[42] Zemel, R. “A minimum description length framework for unsupervised learning”. Ph. D. Thesis, Dept. of Computer Science, University of Toronto, Toronto, Canada, 1993.