Inductive Inference Theory - A Unified Approach to Problems in Pattern Recognition and Artificial Intelligence

INDtl:TIVE INF'E:RENCE THEORY - A UNIFIED APffiOACH TC FP.OELEl-5 IN PATTl.RN Rl<:CCXZNITIOll AND ARTJF'ICIAL IN'I'EUJGENCE

R. J. Solomonoff Rockford Re~earch Institute 140 1/2 Mt. Auburn Street Cambridge, Mass. 02138, U.S.A.

Recent results in in:iuction theory are reviewed that demonstrate the general adequacy of the in­ duction system of Solomoncff ar.d Willis. Several problems in pattern recognition and A.I. are in­ vestigated through these methods. The theory is used to obtain the a priori probabilities that are necessary in the application cf st.ochastic lang­ uages to pattern recognition. A simple, quanti­ tative solution is presentee for part of Winston's problem of learning structural descriptions from examples. In c ont.ra~t to work :l n non-prcbabi.lis­ tic prediction, the present methods give proba­ bility values that can be usee with decision theory to make critical decisions.

Introd uc~j,_op

The kin:i of ireuction theory that we will consider rr.ay be regarded as a Bayesian method in which the a priori probability of a hypothesis is related to the shortest descr:l.ptions of that hypothesis that are obtainable by programrr~ng a reference universal Turing machine.

The probabil:lty values obtained are ordinarily not effectively computable. They ca~ become effectively computable if we make certain reason­ able restrictions on the source cf the data, but in either case they do not appear to be Er!Ctical~ 1:£ calculable. Ho"rever, various approximation methods readily suggest themselve~, and indeed, all known methods of obtaining probability esti­ mates may be regarded as approx:imE.tions to the idealized method and they can be compared an:i crit.ic!zed on th:ls basis.

Several problem~ in patterr· recognition and A.I. will be discussed with respect. to this general formulation of in:iuction.

Inductio~ an:i pattern recognition thro~h stochastic grammar construct.ior. is. discussed !n a general way. The best work in this area involves a Bayesian analysis an:i the present. induction theories tell how to obtain the necessary a priori probabil:lt.ies of various grammars.

Next we discuss in scme cet.E.il part. of Winston's program for learning struc~t~al descrip­ tions frorr. example~. A simple vector model of the problem is described an:i various quantitative results are readily obtained. These agree for the

·

·

·

This research was sponsored in part by the Ad­ vanced Research Projects Agency of the Department of De·fense ur.der Office of Naval Research con­ tracts N00014-7Q-A-0362-0003 and N00014-7Q-A-03620005; USAF contract. AF-19(628)-5975: AFO!:>R con­ tract AF-49(638)-376, Grant AF-AFOSR 62-377, and Public Health Service NIH Grant GM 11021-01.

most part. with Winston's qualitative heuristic discu~sions of the relative likelihoods of various models of concepts, but the results are obtained very directly an:i do nc.t involve tree search of al'\Y kind.

In addition to resolving m&l'\Y otterwise ambi­ quous decisions, the quantitative probabilities obtained enablF. us to use decision theory to make critical decisions as in the mechanization of medical diagnosis.

I. Recent Work in Induction

We ~.11 present some recent results in the theory of indu::tive inf~rence - discussing what. is possible and what is no"' possible.

For the purposes of this discussio~. the pro­ blem of in:iuctive inference will be the extra­ polation of a sequence of symbols emitted by an unknown stochastic source. It is not difficult to show that almost all, if not all problems usually regarded as in:iuction, can be expressed in this form. Discovery of multidimensional patterns, curve fitting, time series extrapolation an:i weather prediction are but a few of the kin:is of problems that can be readily dealt with.

Although in:iuction has always been the most important thing going on in science an:i has con­ stituted a large part of the study of the philo­ sophy of science, there has not, until recently, been a rigorous formulation of the process with a clear un:ierstanding of the expected errors involved. We will discuss these recent results an:i what they imply about what is possible, impossible and approximatable.

Recent work in in:iuction has centered about the concept of the "description" of a string of symbols. A "description" cf a string with respect to a particular reference computer is an input to that computer that gives the described string as output. Solomonoff (8) used the lengths of short descriptions of a str:lng and its possible continu­ ations to define the a priori probability of that string. Bayes' Theorem was then used to find the probability of any particular continuation of the string. He also showed that using a universal Turing machine for reference made the a priori probabHities relatively insensitive to choice of reference computer ·

the prol::.abH:I ty of the described string and Ni is the ler.gthof the ith possible description. We sum over al.l possible descri.ptions of the string are all J:ossible contir.uations of it. Clearly the shortest descriptions get most weight, but the other descriptions can't be ignored.

later, Kolmogorov (1) and Chaitin (13) proposed that a random sequence be defined to be one whose shortest description with respect to a universal Turing ma~hire is about the same length as the sequence itself. Martin Ulf (2), Loveland (3) and Schrtorr (4) cortinuocl work on randomness defini­ tions. For a review of this work as well as subsequent. research in the Soviet Union, see Zvor.kin and Levin (5).

More recently, Chaitin (6) has proposed expres­ siorls for entropies of sequences based on descrip­ tions that form a prefix set. The expressions, however, have error terms that. do not occur in the earlier, rrore exact formulation of Willis (9).

WilJjs refined Solomonoff 1 s model and overcame several difficulties in it. The theorems in the present paper usually follow directly from his work. Because of the"halting problem': it is often impossible to tell if one string is a descriptior. of another with respect to a specific machine. Willis dealt with this problem by considering an infinite sequence of machines, each more powerful than the last, but all of them sufficiently limited so that they have no "halting problen:." Associated with each of these machines is a com­ putable pr~babilit.y assigned to the string ir questiol'l.

Or:e seque!'1ce of such machines is obtainable by considering a universal 3 tape Turing machine with unidirection input and output tapes and a bidirec­ tional working tape. The Tth machine in the sequence is obtained by stopping the universal machine after T steps (if it has not already stopped). It is not difficult to show that the sequence of probabilities obtained by these machines approaches a limit as T approaches infin­ ity, b'd that the limit is not effectively con:­ putable.

Suppose that A(m) is a string of length m, and that we have a st9cbastic fe~erator that assigns a probability P(A\m)) to Am · Suppose this generator is describable by a finite string b bits il'l length. Then for sufficiently powerful refer­ ence machines,

MT (m) Here P is the probability assigned to A by the reference machine, MT· From this, it is clear that the limit machine must satisfy this inequal­ ity, so if we define

The1'1,

Note that the factor 2-b is independent of m. the length of the sequence. The error between pM and P is

One interpretatior. of the result is given by the work of Cover (7), who shows that if one places bets at even odds on a stochastic seque!'1ce generated by P, but bases one's bets on pM, then the ratio of one's fortune to the optimum obtain­ able (which would use Pas basis) will be just rJ'l/P.

Cover also prgposed a somewhat d:l.fferent expression for pn from Willis 1 , basing it upo1'1 Chaitii'1 1 S (6) definition of prefix code complexity. ~~:hen showed that for his probability definition,

which is a somewhat weaker result than Willis'. We have been able to show, however, that for a very broad class of stochastic sources, Cover's probability estimate is negligably worse than Willis'.

To obtain a different(m~asure of the accuracy of Willis' method, let A nJ represent th~ string consisting of the first n symbols of AlmJ.

are the conditional probabilities of the n+1th symbol, given the previous symbols, and

From these definitions we obtain directly,

This expression is the ratio of the products of the conditional probabilities for the nth symbols.

If we want to know the mean error in this ratio we take the mth root a~ obtain 2-i. It is clear that it must approach unity as m becon:es very large.

Although this is a ve1y pow~rful result and gives real assurance that S'm converges to&m very rapidly as m increases, it lacks a certain intuitive appeal. One asks whether it could not be possible that. the ratio might be« i for some factors and >> 1 for others. While the mean could be close to unity the individual deviations could be qdte large.

This difficulty does not arise, however, and from the foregoing result it is possible to show that the expected value of the total squared error between the conditional probabilities 6 n and cS 1 remains ~ bln ./2 n

~ef:, E is the expected value with respect to P. A is the kth sequence of length m. There are · m k t: r k C JUSt 2 of them. 0· and 0· are the cond:ltior.- l. l.

k (m) _M al probabilities for the ith bit of A for ~- an:! P, respectively.

The expected value of ~he mean square error be­ tween the conditio~al probabilities is less than !!.1n{2. m

A few objections suggest themselves. First, this error is unreasonably smaller than those ob­ talned in ordinary statistical analysis. For a simple Bernoulli S£1Cl.'l:ence, the expected squared error in the mth symbol is proportional to ~ and

m the total square error is of the order of ln m rather than bln.J2 ·

The reason for this discrepancy is that we have assumed that the stochastic source had a finite description. If th~ source cojlisted of zeros and ones with probabilities ~ and 8 respectively, we could, in:leed have a f1.r~te description - perhaps of t.ha order of 4 cr 5 bits. Ordinarily in stat­ istics, however, the stochastic sources are des­ cribable as continuous functio~s of a finite number of parameters. The param~ters themselves each have infinitely long descriptions.

For situations of this sort, the expected total squared error is not bounded, but is roughly pro­ portional to the log of the sequence length as in conventional statistical analysis. The error itself, however, approaches zero.

If there are k different parameters in the model, the expected total sqt:ared error will be bounded by

Here, m is the number of symbols in the string being described, A is a constant that is charact­ eristic of the accuracy of the model and b is the number of bits in the description of the expres­ sion containing the k parameters.

If we are c~paring several differer.t models and we have much data (i.e. large m), then the ·~· terms will be of little significance and we need only compare the correspc.nding Ak values to determine the best model.

A technique very similar to this has been successfully used by Akaike (10) to determine the optimum number of parameters to use in linear regressior. analysis. The present rrethods are, however, usually of most interest when the amount of directly relevant data is relatively small.

Another objectior, is that ~ is incomputable. This makes it impossible to calculate it exactly. Is there not a better solution possible? We can obtain progressively more computable solutions by making more and rnore restrictions on the sto­ chastic source.

If there are no restrictions at all, there is no prediction at all possible. If we restrict tho stochastic source only to be finitely describable then 1t. is well known that there can be no effect· ively computable solutions, thot:gh as we have seen, there is a ncn effectively computable If we restr1ct the "computational complexity" of the stochastic source, so that we have an upper bound on how long it takes the so~ce to compute the probability of a sequer.ce of length m, then the prcbabili ties are, indeed computable, and they converge as rapidly as they do in incomputab].e cases. They are, however, no mere practically computable than the incomputable solutions.

In any case, we must use approximatior, methccs. It is c~. ear that the i.ncomputable n:ethod described converges very rapidl:y - it is likely that it has less error for a given amount of data than any other· probability evall:ation methc-d, and so we will do welJ to try to approximate it..

In most cases, our arproximations consist of finding not tr.e shortest description of the string of interest (this, too, being i.ncomputable), but rather the set of the shortest descriptions that we can find with the resources available to us. All of the methods ordinarily used tc estimate probability by finding regularities in data can be expressed in the form of discoveries of short descriptions of the data and +.herefore are approx­ imations to the ideal method. In thi s corr.mon format, various approxi.mations can be compared, so we can select the best ones - the ones most likely to give good predictions.

~.EP.lication to Pattern Recognition Stochastic Language

To illustrate the problere, suppose we are given a set of strings of symbols, such as aa,abba, aabbaa, baaabbaaab etc., and we are told that these strings were acceptable sentences in some simple formal language. We are required to find a grammar that could generate these strings.

In general, there will be an 1 nfini te nlllT.ber of grammars that can generate the set even if we restrict the grammars, say,to be finite state cr to be context free grammars. Early investigators proposed that some criterion of "simplicity" be imposed on the grammar, and various explications of this concept were devised, but with no basis for preferring one explication over any other.

By assuming the set of strings was produced by some unknown stochastic generator, and using some of the previously described methods to give an a priori probability distribl:tion over all such generators, a very general solution to this problem is obtained, and the concept of "simplici­ ty" is unnecessary. A stochastic language is an assignment of probabilities to all strings being considered. A stochastic generator or grammar is a means for carrying out this assignment.

One very general fern. of stochastic grammar consists of a Turing machine. One inserts the string into the machine and it prints out the probability of t.hE.t string. Many of the stri ngs may have zero probability assigned t o therr .

Another very general form of stochastic grammar is a generative grammar. Again we t.ave a Turing machine, but we insert a random s trir g of zeros and on~s. The output strings of tr.:.s machine then have the probability distribution associated with the desired stochastic language.

To use stochastic languages to solve induction problerns, such as the one of guessing the grammar that produced a given set of strings, we first assume an a priori distribution on all possibla stochastic languages. If Pi is the a priori r:robabili ty of tha i th stochastic language, and I,_j is the probability that the i th language will produce the jth sample string (there being m sample strings), then the rnost likely grammar is the one for which

is maximtun.

Often we are not interested in knowing which grammar produced the set of strings, we only want to know the probability that a particular new string is in the set - this new Etring being the m + 1th. A Bayesian analysis g~ves us

for this . probability, the surr.mation being taken over all grammars for which Pi > O.

The a priori prabability of a language cor­ responds roughly to the earlier concept of simplicity, but it is a more clearly defined quantity.

To generate a stochastic grammar from a non­ stochastic generative grammar is usually very easy. In the generative grammar, at each point in the construction of the final object, there will be choices to be made. If we assigr· pr·cbabilities to each of these choices, we have a stochastic generative gramnar. The probability of any particular derivation will be the product of the probabilities of the choices involved in that derivation. If the language is ambiguous, some objects wiD be deri.vable in more than one way · and the probabilities of each of thase derivations must be added to obtain the total probability of the final object.

Many different kinds of grammars have been ~a­ vised for various problem areas (11 ). In part~­ cular, they have been used for two dimensional scena analysis, recognition of handwritten phar&cters, chromosome pattern recognition, recognition of spoken wcrds, etc.

Tha basic model that stochastic grammars propose is a very attractive one. It assumes that the sample set was created by some s~rt of mech: anism and that thEt mAchanism had v·arJous probabJ­ listi c elemants. It enables us to put. intc the model any informatior1 that we have about the problem, either d etermini.st.ic o~· probabH is tic · For somA time, however, the ass~gnment of a priori probabilit.ias to the different possible mechanisms was a problem of uncertain solution.

Induction theory made a11 importar1t brftakthrough by providing a gerttral method to assign probabj] i­ ties to these mechanisms, whether the: assigrment is to be purely a pric·ri or whether they are dependent in any way on available information.

If the proq4bility is purely a priori, one method of probability assignment proceeds by writing out a minimal description of the non­ stochastic grammar from which the stochastic grammar is derived. The details of how this is done for a kind of finite state grammar and for a general context free grammar are given in Ref. 8, pp. 2)2-253.

If there is some data available on the rela­ tive frequencies with which the primitive con­ cepts have been used in the past for other induction problems, this information can be used to assign initial ''bit costs" to these concepts when constructing new grammars.

III. Application to A.I. Learning Structural Descriptions from Examples

Winston's program for learning various structural concepts from both positive and careful~ chosen negative examples of those concepts (12) is perhaps the most competent induction program yet completed.

The program does much more than learn concepts, but we shall discuss only this parti­ cular part of the program. It begins with a line drawing of three dimensional objects. This con­ sists of one or more objects in various positions, having various relations with respect to one another. There is a preprocessing program that translates this drawing into a description that is in the form of a net.

The nodes of the net are objects in the drawing, properties of objects and classes of objects. There are arrows connecting the nodes that denote relations between them.

For an example, suppose the original drawing pictured a cube on the left and a vertical brick on the right. A possible net describing this scene would have four nodes: a brick; a cube; the property, "standing" and the class of solids, "prism". The brick and cube are connected by an arrow labelled "to the right of". The brick has an arrow labelled ''bas the property of" connecting it to "standing". Both the brick and cube have arrows going to prism labelled "a-kind-of", indi­ cating class inclusion.

After being shown several scenes that are given as positive, and several as negative exam­ ples of a certain concept, such as a table, the program tries to induce the concept by making a model of it. These models consist of networks similar to those used to describe scenes, but the nodes and arrows of the net are usually classes of objects, classes cf properties and classes of relations. These classes may sometimes be ex­ pressed as negations, e.g. "not a brick", or "is not to the left of".

For purposes of comparing scenes to one another and scenes to models, we will consider a scene description to be an ordered sequence of objects and relations - a vector whose components are a mixture of objects and relations. A "Model" is a vector whose components are classes.* Formalized in this way, it is clear that given a set of posi­ tive and negative examples, there will ordinarily be an enormous number of models such that

1. In each of the positive examples, all of the components are members of the corresponding classes in the model.
2. In each of the negative examples, at least one component is not a member of the corresponding class in the model.

Winston has devised a system for ordering the models, so that after each example is given, it picks the ''best" model that is consistent with the data thus far- i.e. highest in the ordering. His ordering of models is very close to that of a priori probabilities as calculated by induction theory.

In one case we are given as a positive example, a brick that is standing on one end. The nega­ tive example is a brick lying on one side. The classes that are considered for the "property" component of the vector of the model are:

1. Standing
2. Not lying

Winston notes that since most concepts are defined in terms of properties rather than anti-proper­ ties, "standing" is more likely. In the language of induction theory, positive concepts that have names in the language are usually of high a priori probability. A negative concept consists of a positive concept with a negation symbol - which increases description length and decreases a priori probability. If a negative concept is of much utility in description, and of high a priori probability, it will have been useful to define a special word for it, e. g. "dirty" is the word for "not clean." Reference 8, pp. 232-240 treats the problem of when it is worth while to define new symbols.

Another reason why "standing" is a better choice than "not lying" is that "standing" probably has fewer members. This is brought out more clearly in the next example.

Here we have two positive cases: 1) Apple 2) Orange. Three classes for the model are considered. First, the Boolian sum class of apples and oranges. Second, the class "fruit". Third, the universal class. Though this is not the example Winston gives, the choice he would make would be "fruit". He regards this as a sort of middle-of-the-road stand in a difficult in­ duction problem.

Induction theory gives a quantitative discus­ sion. To make this particular problem non­ trivial, we assume that the positive examples given are in some sense "typical". If they are not constrained in this way, then the Universal class is the best response. Let Pi and Ni be the

*

*

*

• This differs slightly from Winston's defini­ tion of "model", but should cause no great difficulty.

respective a priori probability of a class and the number of members in that class. Then if the positive examples are "typical" or, more narrowly, if all positive cases of the concept have equal likelihood of being given as examples, then by Bayes, the most likely class is the one for which Pi/Nr is maximum, n being the nwr.ber of positive cases - two in the present situation.

The universal class is of high a priori pro­ bability, but it has very many members. The Boolian sum class has only two members, but its a priori likelihood tends to be low. This is because the symbol for Boolian sum is "expensive" - i.e. concepts formed using it, tend to be rather ad-hoc and not very useful in prediction.· If the class "fruit" is, indeed, of fair a priori probability and there aren't too many kinds of fruit, it may well be the best choice. We might also consider "eatable fruit" or "plants" depending on the sizes and a priori probabilities of these classes.

From these and similar heuristic arguments, Winston is able to order the possible models with respect to likelihood. The result is a remarkably capable program in the problem area he has selected. However, even ·in this limited area it is easy to get into complexities that are well beyond the capacity of the program. Winston deals with these by arbitrarily cutting off the consid­ eration of certain possibility branches.

With expansion of the language to deal with a larger universe of problems - e.g. the inclusion of facilities for making recursive definitions - the necessary complexity would rapidly get beyond the capabilities of the heuristic discussions of likelihood that Winston uses.

We will describe a system of learning concepts that is similar to Winston's, but obtains quanti­ tative probabilities and appears to be far simpler to implement. It is hoped that this simplifica­ tion will make it possible to extend Winston's methods to much richer worlds of problems.

The system consists of a proceedure for ob­ taining an initial model and for modifying the model as each new positive or negative example is given. At each point in time several of the best models are stored and these can be used to give the probability of any particular object being an example of the concept being learned.

We start out with a positive example of the concept.

Our first model has for its components, those classes of which the corresponding components of the example are members, and for which Pi/N. is maximum, i being the component considered. ~Often these classes will have but one component and Winston uses classes of this kind for his initial model.

Subsequently, there are four possible example situations with respect to the model. A positive example can be either accepted or rejected by the model or a negative example can be accepted or rejected by the model. We will treat these one by one.

If a negative example is rejected ~ the model, we leave the model invariant. Our criterion of choice of class is maximum Pi/Il{. Since n is the number of positive examples thus far, the new negative example does not modifY this quantity in any way for a~ class, so a class that was optimal before the example must be optimal after the example. No change need be made in the model.

On the other hand, if a positive example is given and this is accepted ~the model, the model may or may not need to be changed. Each of the components must be examined in:lividually. The class with maximum Pi/Nr may or may not be the class with maximum Pi/~+1. The modification of the model is relatively simple because the compo­ nents are optimized independently of one another.

A similar situation arises if we are given a positive example that is rejected by the model. Each of the component classes in the model that rejects the corresponding example component must be expanded to incltrle the example component. There will usually be ma~ ways to expand a~ in each case we chose the class for which Pi/Ni.l is maximum, n+l being the number of positive examples thus far.

Consider next a negative case that is accepted ~ the model. Each component class in the model can b3 contracted in various ways so that it will not :inclu:ie the corresponding component of the negative example. For each component, i there will be a satisfactory rejecting class with a maximum Pi/~.

Let cx 1 be Pi/Ni for the ith component of the model before the negative case occurred. Leto<i be Pi/~ for the best acceptable class that can reject the ith component of the new negative case. Note that o<i ~ o(i for all i. Then we will modifY the single component class for which 0(~/ o(i is maximum.

The reason is that the likelihood of the model before the negative cas·e wasT] O(i. We want to replace only~ of the o(i with its correspond­ ing o<~ and to do this we will choose i such that the new product is maximum - i.e. decreased least. ModifYing more than one component would have to give a smaller product. --

The treat.ment of these four cases appears to be simpler and more precise than Winston's heuristic discussions on the relative likelihoods of several possible-models. No tree exploration is necessary.

The Pi values are readily approximated by counting the relative frequencies of various classes. If the samples are small, the accuracy can be improved ~ considering how the classes were constructed.

The t\ are obtainable ~ counting the number of different members of each class that have occurred up to now.

There are two other methods of class construction that can sometimes be more appropriate.

One possibility is to assume that the positive examples are not necessarily typical. The pro­ blem is then merely to find the model of highest a priori probability that accepts all known positive and rejects all known negative examples. Instead of Pi/Nr , the quantity that we want to maximize is Pi. This is mathematically equiva­ lent to having all of the Ni constant - the same for all classes. The discussions of what to do when a positive case fits the model or when a negative case doesn't are similar to those used before, but if a positive case fits the model, the model is always left invariant.

The other alternative is to use the more general model of induction given by stochastic languages. Here, the classes usually do not have sharp edges. The description of a stochastic language (which we will identify with a component class in our model) at once gives the a priori probability of that class as well as the proba­ bility of a~ particular element being chosen. The latter correspon:ls to the 1/Ni that was used earlier.

If Pi is as before an:l aij is the probability that the ith class assigns to the jth positive example, then we want a class that assigns zero probability to all negative examples such that

corresponds to the earlier approximation Pi/~ ·

The three methods of class definition des­ cribed above are not mutually exclusive. It is possible to describe some vector components ~ means of the Pi/!\ model, others by means of the Pi model and still others by means of the stochas­ tic language model.

In the foregoing analysis, we have assumed that the vector components are statistically indepen­ dent, an:l the conclusions obtained follow rigorously from this. If there is reason to believe that several components are statistically dependent, a suitable joint a priori probability distribution for them can be obtained. This dependent set would be treated as a single vector component, but the rest of the analysis would be the same.

If we have training sequences with only posi­ tive examples, neither Winston's system nor +.he Pi system can operate, but both the P 1 /Nr system and the stochastic language system have no par­ ticular difficulty.

l.r·other important advantage of the analysis techniq~es described is the use of quantitative probabilities for the vector class~s of the model. From them it is possibl~ to ca.lculate readily the probability that ar,y ur.identified new examrle is or is not an exampl~ of the concept being learrted.

To comp'"te this, take t.he total probabi.lities of all models of the concept that are consistent with the data thus far (i.e. they accept. all pos:i.tive an::! reject all negative examples) that accept the new exampla. Divide this qy the total probabilities of all models of the concept that are consistent with the data thus far, whether or not they accept the new example.

Quantitative probability estimates are neces­ sary to make critical decisions through decision thao~. The mechanization of medical diagnosis is one important area. Decisions in econorr~cs, ecology an::! agriculture are but a few other areas where probabi 1i ties of this kin::! are of paramount importance.

Bibliograpt:y

1. Kolmogorov, A.N. "Logical Basis for Informa­ tion Theory an::! Probability Theory", IEEE Transactions on Information Theory IT-14, pp. 662-68i. 1968.

"Three Approaches to the Quantitative Definition of Information", Information Transmission, Vol I, PP· 3-11, 1965.

1. Martin Ilif, P. "The Definition of Ran::!om Sequences", Info:rmation and Control, Vol. 9, no. 6, Dec. 1966, PP· 6o2-619.
2. Loveland, D.W. "A Variant of the Kolmogorov Cone ept of Complexity", Information and Control 1.2 (1969), PP· 510.. 526.
3. Schnorr, C.P. "Process Corr.plexity an::! Effec­ tive Ram om Tests", Journal of Computer System Sciences 1 (1973), PP· 376-388.
4. Zvonkin, A.K., and Levin, L.A. "The Complex­ ity of Finite Cbjects and the Development of the Concepts of Inforn~ation at¥1 Randomness by Means of the Theory of Algorithms 11 , Russian Mathematical Surv2Ys £2, 6 (Nov.-Dec. 1970), 'PP· 83-124.
5. Chaitin, G.J. "A Theory of Program Size Fomally Identical to Information Theory", To appear in Journal of the Association of Computing Machinery.
6. Cover, T. M. "Universal Gambling Schemes and the Complexity Measures of Kolmogorov and Chaitin", Report No. 12, Statistics Dept., Stanford Univ., Stanford, Calif., 19~. Submitted to Annals of Statistics.
7. Solomonoff, R.J. "A Formal Theory of In::!uc­ tive Inference." Information and Cqntrol, March 19€JI., pp. 1-22; June 1984, pp. 22~-2_5!1..
8. Willis, D.G. "Compdational Complex:lty and Probability Constructions", Journal of the Assoc. of Computing Machinery, April 1970, pp. 241-259.
9. .Al<aike. H. "Infomation Theory and an Extension of the Maximum Likelihood Princi­ ple", Proc. Second Int. Symp. on Information Theory, Supplement to Problems of Control and Information Theory (1972) pp. 267-281.
10. Fu, K.S. "Syntactic Methods in Pattern Recognition", Academic Press, 19~.
11. Winston, P.H. "Learning Structural Des­ criptions from Exarr.ples", Repcrt AI-TR231, Artificial Intelligence Lab., Mass. Inst. Technol., 1972. Also car. be four.d in TI-.e PsycholEQ __ £f_..f_orr.puter_Dsion, edHed by P.H. Winston; MCGraw Hill, 1974.
12. Chai tin, G. J. "On the Length of Programs for Computing Finite Binary Sequences", Journal of the Assoc. of Computing Machinery, Vol. 13, No. 4 (Oct 1966), PP· ~7-569.