Misplaced Pages

Inductive probability: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 02:46, 26 October 2014 editThepigdog (talk | contribs)Extended confirmed users5,174 edits Bayesian hypothesis testing← Previous edit Revision as of 02:49, 26 October 2014 edit undoThepigdog (talk | contribs)Extended confirmed users5,174 edits Probabilities for inductive inferenceNext edit →
Line 294: Line 294:
: <math>P(T \mid F) = \frac{P(T)}{P(F)}</math> : <math>P(T \mid F) = \frac{P(T)}{P(F)}</math>


or in terms of information, or in terms of information, the relative probability is,
: <math>P(T \mid F) = 2^{-(L(T) - L(F))} </math> : <math>P(T \mid F) = 2^{-(L(T) - L(F))} </math>


For a set of theories <math>T_i = H_i</math>, For a set of theories <math>T_i = H_i</math>, such that <math>L(T_i) < L(F)</math>,


: <math>P(T_i \mid F) = \frac{P(T_i)}{P(F \mid R) + \sum_j{P(T_j)}}</math> : <math>P(T_i \mid F) = \frac{P(T_i)}{P(F \mid R) + \sum_j{P(T_j)}}</math>

Revision as of 02:49, 26 October 2014

Inductive probability attempts to give the probability of future events based on past events. It is the basis for inductive reasoning, and gives the mathematical basis for learning and the perception of patterns. It is a source of knowledge about the world.

There are three sources of knowledge.

  • Inference
  • Communication
  • Deduction

Communication relays information found using other methods. Deduction established new facts based on existing facts. Only inference establishes new facts from data.

The basis of inference is Bayes law. But this law is sometimes hard to apply and understand. The simpler method to understand inference in terms of quantities of information.

Information describing the world is written in a language. For example a simple mathematical language of propositions may be chosen. Sentences may be written down in this language as strings of characters. But in the computer it is possible to encode these sentences as strings of bits (1s and 0s). Then the language may be encoded so that the most commonly used sentences are the shortest. This internal language implicitly represents probabilities of statements.

Occam's Razor says the "simplest theory, consistent with the data is most likely to be correct". The "simplest theory" is interpreted as the representation of the theory written in this internal language. The theory with the shortest encoding in this internal language is most likely to be correct.

Inferred probability

Probability is the representation of uncertain or partial knowledge about the truth of statements. Probabilities are subjective and personal estimates of likely outcomes based on past experience and inferences made from the data.

Probabilities are personal because they are conditional on the knowledge of the individual. Probabilities are subjective because they always depend, to some extend, on prior probabilities assigned by the individual. Subjective should not be taken here to mean vague or undefined.

The term intelligent agent is used to refer to the holder of the probabilities. The intelligent agent may be a human or a machine. If the intelligent agent does not interact with the environment then the probability will converge over time to the frequency of the event.

If however the agent uses the probability to interact with the environment there may be a feedback, so that two agents in the identical environment starting with only slightly different priors, end up with completely different probabilities. In this case optimal decision theory as in Marcus Hutter's Universal Artificial Intelligence will give Pareto optimal performance for the agent. This means that no other intelligent agent could do better in one environment without doing worse in another environment.

This description of probability may seem strange at first. In natural language we refer to "the probability" that the sun will rise tomorrow. We do not refer to "your probability" that the sun will rise. But in order for inference to be correctly modeled probability must be personal, and the act of inference generates new posterior probabilities from prior probabilities.

Comparison to classical probability

In classical probability theories, probabilities are absolutes, independent of the individual making the assessment. But classical probabilities are based on,

  • Shared knowledge.
  • Assumed facts, that should be inferred from the data.

For example in a trial the participants are aware the outcome of all the previous history of trials. They also assume that each outcome is equally probable. Together this allows a single unconditional value of probability to be defined.

But in reality each individual does not have the same information. And in general the probability of each outcome is not equal. The dice may be loaded, and this loading needs to be inferred from the data.

Probability and information

Whereas logic represents only two values; true and false as the values of statement, probability associates a number between 0.0 and 1.0 with each statement. If the probability of a statement is 0 the statement is false. If the probability of a statement is 1 the statement is true.

The principle of indifference is used to establish other probability values. Each probability is always associated with the state of knowledge at a particular point in the argument. Probabilities before an inference are known as prior probabilities, and probabilities after are known as posterior probabilities.

In considering some data as a string of bits the prior probabilities for a sequence of 1 and 0s, the probability of 1 and 0 is equal. Therefore each extra bit halves the probability of a sequence of bits. This leads to the conclusion that,

P ( x ) = 2 L ( x ) {\displaystyle P(x)=2^{-L(x)}}

Where

  • P ( x ) {\displaystyle P(x)} is the probability of a string of bits x
  • L ( x ) {\displaystyle L(x)} is the length of the string of bits x.
  • 2 L ( x ) {\displaystyle 2^{-L(x)}} means 1 divided by 2 to the power of the length of the string of bits x.

We may consider the prior probability of any statement as the number of bits needed to state it.

Combining information

Two statements A and B may be represented by two separate encodings. Then the length of the encoding is,

L ( A B ) = L ( A ) + L ( B ) {\displaystyle L(A\land B)=L(A)+L(B)}

or in terms of probability,

P ( A B ) = P ( A ) P ( B ) {\displaystyle P(A\land B)=P(A)P(B)}

But this law is not always true because there may be a shorter method of encoding B if we assume A. So the above probability law applies only if A and B are "independent".

Conditional probability

Probability depends on the facts known. Prior probabilities are the probabilities before a fact is known. Posterior probabilities are after a fact is known. The posterior probabilities are said to be conditional on the fact. Conditional probabilities are written,

P ( B | A ) {\displaystyle P(B|A)}

This means the probability that B is true given that A is true.

All probabilities are in some sense conditional. The prior probability of B is,

P ( B ) = P ( B | true ) {\displaystyle P(B)=P(B|{\text{true}})}

The Frequentest Approach applied to possible worlds

In the frequentest approach, probabilities are defined as the ratio of the number of outcomes within an event to the total number of outcomes. In the possible world model each possible world is an outcome, and statements about possible worlds define events. The probability of a statement being true is the number of possible worlds divided by the total number of worlds.

The total number of worlds may be infinite. In this case instead of counting the elements of the set a measure must be used. In general the cardinality |S|, where S is a set, is a measure.

The probability of a statement A being true about possible worlds is then,

P ( A ) = | { x : A ( x ) } | | x : t r u e | {\displaystyle P(A)={\frac {|\{x:A(x)\}|}{|x:true|}}}

For a conditional probability.

P ( B | A ) = | { x : A ( x ) B ( X ) } | | x : A ( x ) | {\displaystyle P(B|A)={\frac {|\{x:A(x)\land B(X)\}|}{|x:A(x)|}}}

then

P ( A B ) {\displaystyle P(A\land B)}
= | { x : A ( x ) B ( x ) } | | x : t r u e | {\displaystyle ={\frac {|\{x:A(x)\land B(x)\}|}{|x:true|}}}
= | { x : A ( x ) B ( x ) } | | { x : A ( x ) } | | { x : A ( x ) } | | x : t r u e | {\displaystyle ={\frac {|\{x:A(x)\land B(x)\}|}{|\{x:A(x)\}|}}{\frac {|\{x:A(x)\}|}{|x:true|}}}
= P ( A ) P ( B | A ) {\displaystyle =P(A)P(B|A)}

Using symmetry this equation may be written out as Bayes' law.

P ( A B ) = P ( A ) P ( B | A ) = P ( B ) P ( A | B ) {\displaystyle P(A\land B)=P(A)P(B|A)=P(B)P(A|B)}

This law describes the relationship between prior and posterior probabilities when new facts are learnt.

Written as quantities of information Bayes' Theorem becomes,

L ( A B ) = L ( A ) + L ( B | A ) = L ( B ) + L ( A | B ) {\displaystyle L(A\land B)=L(A)+L(B|A)=L(B)+L(A|B)}

Two statements A and B are said to be independent if knowing the truth of A does not change the probability of B. Mathematically this is,

P ( B ) = P ( B | A ) {\displaystyle P(B)=P(B|A)}

then Bayes' Theorem reduces to,

P ( A B ) = P ( A ) P ( B ) {\displaystyle P(A\land B)=P(A)P(B)}

The law of total of probability

For a set of mutually exclusive possibilities A i {\displaystyle A_{i}} , the sum of the posterior probabilities must be 1.

i P ( A i | B ) = 1 {\displaystyle \sum _{i}{P(A_{i}|B)}=1}

Substituting using Bayes' theorem gives the law of total probability

i P ( B | A i ) P ( B ) = P ( B ) {\displaystyle \sum _{i}{P(B|A_{i})P(B)}=P(B)}
P ( B ) = i P ( B | A i ) P ( A i ) {\displaystyle P(B)=\sum _{i}{P(B|A_{i})P(A_{i})}}

This result is used to give the extended form of Bayes' theorem,

P ( A i | B ) = P ( B | A i ) P ( A i ) j P ( B | A j ) P ( A j ) {\displaystyle P(A_{i}|B)={\frac {P(B|A_{i})P(A_{i})}{\sum _{j}{P(B|A_{j})P(A_{j})}}}}

This is the usual form of Bayes' theorem used in practice, because it guarantees the sum of all the posterior probabilities for A i {\displaystyle A_{i}} is 1.

Alternate possibilities

For mutually exclusive possibilities, the probabilities add.

P ( A B ) = P ( A ) + P ( B ) {\displaystyle P(A\lor B)=P(A)+P(B)} if P ( A B ) = 0 {\displaystyle P(A\land B)=0}

Using

A B = ( A ¬ ( A B ) ) ( B ¬ ( A B ) ) ( A B ) {\displaystyle A\lor B=(A\land \neg (A\land B))\lor (B\land \neg (A\land B))\lor (A\land B)}

Then the alternatives

A ¬ ( A B ) {\displaystyle A\land \neg (A\land B)}
B ¬ ( A B ) {\displaystyle B\land \neg (A\land B)}
A B {\displaystyle A\land B}

are all mutually exlusive

Also,

( A ¬ ( A B ) ) ( A B ) = A {\displaystyle (A\land \neg (A\land B))\lor (A\land B)=A}
P ( A ¬ ( A B ) ) + P ( A B ) = P ( A ) {\displaystyle P(A\land \neg (A\land B))+P(A\land B)=P(A)}
P ( A ¬ ( A B ) ) = P ( A ) P ( A B ) {\displaystyle P(A\land \neg (A\land B))=P(A)-P(A\land B)}

so, putting it all together,

P ( A B ) {\displaystyle P(A\lor B)}
= P ( ( A ¬ ( A B ) ) ( B ¬ ( A B ) ) ( A B ) ) {\displaystyle =P((A\land \neg (A\land B))\lor (B\land \neg (A\land B))\lor (A\land B))}
= P ( A ¬ ( A B ) + P ( B ¬ ( A B ) ) + P ( A B ) {\displaystyle =P(A\land \neg (A\land B)+P(B\land \neg (A\land B))+P(A\land B)}
= P ( A ) P ( A B ) + P ( B ) P ( A B ) + P ( A B ) {\displaystyle =P(A)-P(A\land B)+P(B)-P(A\land B)+P(A\land B)}
= P ( A ) + P ( B ) P ( A B ) {\displaystyle =P(A)+P(B)-P(A\land B)}

Negation

As,

A ¬ A = t r u e {\displaystyle A\lor \neg A=true}

then

P ( A ) + P ( ¬ A ) = 1 {\displaystyle P(A)+P(\neg A)=1}

Implication and condition probability

Implication is related to conditional probability by the following equation,

A B P ( B A ) = 1 {\displaystyle A\to B\iff P(B\mid A)=1}

Derivation,

A B {\displaystyle A\to B}
P ( A B ) = 1 {\displaystyle \iff P(A\to B)=1}
P ( A B ¬ A ) = 1 {\displaystyle \iff P(A\land B\lor \neg A)=1}
P ( A B ) + P ( ¬ A ) = 1 {\displaystyle \iff P(A\land B)+P(\neg A)=1}
P ( A B ) = P ( A ) {\displaystyle \iff P(A\land B)=P(A)}
P ( A ) P ( B A ) = P ( A ) {\displaystyle \iff P(A)\cdot P(B\mid A)=P(A)}
P ( B A ) = 1 {\displaystyle \iff P(B\mid A)=1}

Probability priors from encoding length

Knowledge may be represented as statements. Each statement is a Boolean expression. Expressions may encode by a function that takes a description (as against the value) of the expression and encodes it as a bit string.

The length of the encoding of a statement gives an estimate of the probability estimate for a statement. This probability estimate will often be used as the prior probability of a statement.

Technically this estimate is not a probability because it is not constructed from a frequency distribution. The probability estimates given by it do not always obey the law of total of probability. Applying the law of total probability to various scenarios will usually give a more accurate probability estimate of the prior probability than the estimate from the length of the statement.

Encoding expressions

An expression is constructed from sub expressions,

  • Constants (including function identifier).
  • Application of functions.
  • quantifiers.

A code must distinguish the 3 cases. The length of each code is based on the frequency of each type of sub expressions.

Initially constants are all assigned the same length/probability. Later constants may be assigned a probability using the prefix code based on the number of uses of the function id in the expression.

The length of a function application is the length of the function identifier constant plus the sum of the sizes of the expressions for each parameter.

The length of a quantifier is the length of the expression being quantified over.

Distribution of numbers

No explicit representation of natural numbers is given. However natural numbers may be constructed by applying the successor function to 0, and then applying other arithmetic functions. A distribution of natural numbers is implied by this, based on the complexity of constructing each number.

Rational numbers are constructed by the division of natural numbers. The simplest representation has no common factors between the numerator and the denominator. This allows the probability distribution of natural numbers may be extended to rational numbers.

Bayesian hypothesis testing

Bayes' theorem may be used to estimate the probability of a hypothesis or theory H, given some facts F. The posterior probability of H is then

P ( H | F ) = P ( H ) P ( F | H ) P ( F ) {\displaystyle P(H|F)={\frac {P(H)P(F|H)}{P(F)}}}

or in terms of information,

P ( H | F ) = 2 ( L ( H ) + L ( F | H ) L ( F ) ) {\displaystyle P(H|F)=2^{-(L(H)+L(F|H)-L(F))}}

By assuming the hypothesis is true, a simpler representation of the statement F may be given. The length of the encoding of this simpler representation is L(F|H).

L(H) + L(F|H) represents the amount of information needed to represent the facts F, if H is true. L(F) is the amount of information needed to represent F without the hypothesis H. The difference is how much the representation of the facts has been compressed by assuming that H is true. This is the evidence that the hypothesis H is true.

If L(F) is estimated from encoding length then the probability obtained will not be between 0 and 1. The value obtained is proportional to the probability, without being a good probability estimate. The number obtained is sometimes referred to as a relative probability, being how much more probable the theory is than not holding the theory.

If a full set of mutually exclusive hypothesis that provide evidence is known, a proper estimate may be given for the prior probability P ( F ) {\displaystyle P(F)} .

Set of hypothesis

Probabilities may be calculated from the extended form of Bayes' theorem. Given all mutually exclusive hypothesis H i {\displaystyle H_{i}} which give evidence, such that,

L ( H i ) + L ( F | H i ) < L ( F ) {\displaystyle L(H_{i})+L(F|H_{i})<L(F)}

and also the hypothesis R, that none of the hypothesis is true, then,

P ( H i | F ) = P ( H i ) P ( F | H i ) P ( F | R ) + j P ( H j ) P ( F | H j ) {\displaystyle P(H_{i}|F)={\frac {P(H_{i})P(F|H_{i})}{P(F|R)+\sum _{j}{P(H_{j})P(F|H_{j})}}}}
P ( R | F ) = P ( F | R ) P ( F | R ) + j P ( H j ) P ( F | H j ) {\displaystyle P(R|F)={\frac {P(F|R)}{P(F|R)+\sum _{j}{P(H_{j})P(F|H_{j})}}}}

In terms of information,

P ( H i | F ) = 2 ( L ( H i ) + L ( F | H i ) ) 2 L ( F | R ) + j 2 ( L ( H j ) + L ( F | H j ) ) {\displaystyle P(H_{i}|F)={\frac {2^{-(L(H_{i})+L(F|H_{i}))}}{2^{-L(F|R)}+\sum _{j}{2^{-(L(H_{j})+L(F|H_{j}))}}}}}
P ( R | F ) = 2 L ( F | R ) 2 L ( F | R ) + j 2 ( L ( H j ) + L ( F | H j ) ) {\displaystyle P(R|F)={\frac {2^{-L(F|R)}}{2^{-L(F|R)}+\sum _{j}{2^{-(L(H_{j})+L(F|H_{j}))}}}}}

In most situations it is a good approximation to assume that F is independent of R,

P ( F | R ) = P ( F ) {\displaystyle P(F|R)=P(F)}

giving,

P ( H i | F ) 2 ( L ( H i ) + L ( F | H i ) ) 2 L ( F ) + j 2 ( L ( H j ) + L ( F | H j ) ) {\displaystyle P(H_{i}|F)\approx {\frac {2^{-(L(H_{i})+L(F|H_{i}))}}{2^{-L(F)}+\sum _{j}{2^{-(L(H_{j})+L(F|H_{j}))}}}}}
P ( R | F ) 2 L ( F ) 2 L ( F ) + j 2 ( L ( H j ) + L ( F | H j ) ) {\displaystyle P(R|F)\approx {\frac {2^{-L(F)}}{2^{-L(F)}+\sum _{j}{2^{-(L(H_{j})+L(F|H_{j}))}}}}}

Boolean inductive inference

Abductive inference starts with a set of facts F which is a statement (Boolean expression). Abductive reasoning is of the form,

A theory T implies the statement F. As the theory T is simpler than F, abduction says that there is a probability that the theory T is implied by F.

The theory T, also called an explanation of the condition F, is an answer to the ubiquitous factual "why" question. For example for the condition F is "Why do apples fall?". The answer is a theory T that implies that apples fall;

F = G m 1 m 2 r 2   {\displaystyle F=G{\frac {m_{1}m_{2}}{r^{2}}}\ }

Inductive inference is of the form,

All observed objects in a class C have a property P. Therefore there is a probability that all objects in a class C have a property P.

In terms of abductive inference, all objects in a class C or set have a property P is a theory that implies the observed condition, All observed objects in a class C have a property P.

So inductive inference is a special case of abductive inference. In common usage the term inductive inference is often used to refer to both abductive and inductive inference.

Probabilities for inductive inference

Implication determines condition probability as,

T F P ( F T ) = 1 {\displaystyle T\to F\iff P(F\mid T)=1}

So,

P ( F T ) = 1 {\displaystyle P(F\mid T)=1}
L ( F T ) = 0 {\displaystyle L(F\mid T)=0}

This result may be used in the probabilities given for Bayesian hypothesis testing. For a single theory, H = T and,

P ( T F ) = P ( T ) P ( F ) {\displaystyle P(T\mid F)={\frac {P(T)}{P(F)}}}

or in terms of information, the relative probability is,

P ( T F ) = 2 ( L ( T ) L ( F ) ) {\displaystyle P(T\mid F)=2^{-(L(T)-L(F))}}

For a set of theories T i = H i {\displaystyle T_{i}=H_{i}} , such that L ( T i ) < L ( F ) {\displaystyle L(T_{i})<L(F)} ,

P ( T i F ) = P ( T i ) P ( F R ) + j P ( T j ) {\displaystyle P(T_{i}\mid F)={\frac {P(T_{i})}{P(F\mid R)+\sum _{j}{P(T_{j})}}}}
P ( R F ) = P ( F R ) P ( F R ) + j P ( T j ) {\displaystyle P(R\mid F)={\frac {P(F\mid R)}{P(F\mid R)+\sum _{j}{P(T_{j})}}}}

giving,

P ( T i F ) 2 L ( T i ) 2 L ( F ) + j 2 L ( T j ) {\displaystyle P(T_{i}\mid F)\approx {\frac {2^{-L(T_{i})}}{2^{-L(F)}+\sum _{j}{2^{-L(T_{j})}}}}}
P ( R F ) 2 L ( F ) 2 L ( F ) + j 2 L ( T j ) {\displaystyle P(R\mid F)\approx {\frac {2^{-L(F)}}{2^{-L(F)}+\sum _{j}{2^{-L(T_{j})}}}}}

Inference based on program complexity

Solomonoff's theory of inductive inference is also inductive inference. A bit string x is observed. Then consider all programs that generate strings starting with x. Cast in the form of inductive inference, the programs are theories that imply the observation of the bit string x.

The method used here to give probabilities for inductive inference is based on Solomonoff's theory of inductive inference.

Detecting patterns in the data

If all the bits are 1, then people infer that there is a bias in the coin and that it is more likely also that the next bit is 1 also. This is described as learning from, or detecting a pattern in the data.

Such a pattern may be represented by a computer program. A short computer program may be written that produces a series of bits which are all 1. If the length of the program K is L ( K ) {\displaystyle L(K)} bits then it's prior probability is,

P ( K ) = 2 L ( K ) {\displaystyle P(K)=2^{-L(K)}}

The length of the shortest program that represents the string of bits is called the Kolmogorov complexity.

Kolmogorov complexity is not computible. This is related to the halting problem. When searching for the shortest program some programs may go into an infinite loop.

Considering all theories

The Greek philosopher Epicurus is quoted as saying "If more than one theory is consistent with the observations, keep all theories".

As in a crime novel all theories must be considered in determining the likely murderer, so with inductive probability all programs must be considered in determining the likely future bits arising from the stream of bits.

Programs that are already longer than n have no predictive power. The raw (or prior) probability that the pattern of bits is random (has no pattern) is 2 n {\displaystyle 2^{-n}} .

Each program that produces the sequence of bits, but is shorter than the n is a theory/pattern about the bits with a probability of 2 k {\displaystyle 2^{-k}} where k is the length of the program.

The probability of receiving a sequence of bits y after receiving a series of bits x is then the conditional probability of receiving y given x, which is the probability of x with y appended, divided by the probability of x.

Universal priors

The programming language effects the predictions of the next bit in the string. The language acts as a prior probability. This is particularly a problem where the programming language codes for numbers and other data types. Intuitively we think that 0 and 1 are simple numbers, and that prime numbers are somehow more complex the numbers may be factorized.

Using the Kolmogorov complexity gives an unbiased estimate (a universal prior) of the prior probability of a number. As a thought experiment an intelligent agent may be fitted with a data input device giving a series of numbers, after applying some transformation function to the raw numbers. Another agent might have the same input device with a different transformation function. The agents do not see or know about these transformation functions. Then there appears no rational basis for preferring one function over another. A universal prior insures that although two agents may have different initial probability distributions for the data input, the difference will be bounded by a constant.

So universal priors do not eliminate an initial bias, but they reduce and limit it. Whenever we describe an event in a language, either using a natural language or other, the language has encoded in it our prior expectations. So some reliance on prior probabilities are inevitable.

A problem arises where an intelligent agents prior expectations interact with the environment to form a self reinforcing feed back loop. This is the problem of bias or prejudice. Universal priors reduce but do not eliminate this problem.

Minimum description/message length

The program with the shortest length that matches the data is the most likely to predict future data. This is the thesis behind the Minimum message length and Minimum description length methods.

At first sight Bayes' theorem appears different from the minimimum message/description length principle. At closer inspection it turns out to be the same. Bayes' theorem is about conditional probabilities. What is the probability that event B happens if firstly event A happens?

P ( A B ) = P ( B ) P ( A B ) = P ( A ) P ( B A ) {\displaystyle P(A\land B)=P(B)\cdot P(A\mid B)=P(A)\cdot P(B\mid A)}

Becomes in terms of message length l,

L ( A B ) = L ( B ) + L ( A B ) = L ( A ) + L ( B A ) {\displaystyle L(A\land B)=L(B)+L(A\mid B)=L(A)+L(B\mid A)}

What this means is that in describing an event, if all the information is given describing the event then the length of the information may be used to give the raw probability of the event. So if the information describing the occurrence of A is given, along with the information describing B given A, then all the information describing A and B has been given.

Overfitting

Overfitting is where the model matches the random noise and not the pattern in the data. For example take the situation where a curve is fitted to a set of points. If polynomial with many terms is fitted then it can more closely represent the data. Then the fit will be better, and the information needed to describe the deviances from the fitted curve will be smaller. Smaller information length means more probable.

However the information needed to describe the curve must also be considered. The total information for a curve with many terms may be greater than for a curve with fewer terms, that has not as good a fit, but needs less information to describe the polynomial.

Universal artificial intelligence

The theory of universal artificial intelligence applies decision theory to inductive probabilities. The theory shows how the best actions to optimize a reward function may be chosen. The result is a theoretical model of intelligence.

It is a fundamental theory of intelligence, which optimizes the agents behavior in,

  • Exploring the environment; performing actions to get responses that broaden the agents knowledge.
  • Competing or co-operating with another agent; games.
  • Balancing short and long term rewards.

In general no agent will always provide the best actions in all situations. A particular choice choice made by an agent may be wrong, and the environment may provide no way for the agent to recover from an initial bad choice. However the agent is Pareto optimal in the sense that no other agent will do better than this agent in this environment, without doing worse in another environment. No other agent may, in this sense, be said to be better.

At present the theory is limited by incomputability (the halting problem). Approximations may be used to avoid this. Processing speed and combinatorial explosion remain the primary limiting factors for artificial intelligence.

Derivations

Derivation of inductive probability

Make a list of all the shortest programs K i {\displaystyle K_{i}} that each produce a distinct infinite string of bits, and satisfy the relation,

T n ( R ( K i ) ) = x {\displaystyle T_{n}(R(K_{i}))=x}

where,

R ( K i ) {\displaystyle R(K_{i})} is the result of running the program K i {\displaystyle K_{i}} .
T n {\displaystyle T_{n}} truncates the string after n bits.

The problem is to calculate the probability that the source is produced by program K i {\displaystyle K_{i}} , given that the truncated source after n bits is x. This is represented by the conditional probability,

P ( s = R ( K i ) T n ( s ) = x ) {\displaystyle P(s=R(K_{i})\mid T_{n}(s)=x)}

Using the extended form of Bayes' theorem

P ( A i B ) = P ( B A i ) P ( A i ) j P ( B A j ) P ( A j ) {\displaystyle P(A_{i}\mid B)={\frac {P(B\mid A_{i})\,P(A_{i})}{\sum \limits _{j}P(B\mid A_{j})\,P(A_{j})}}\cdot }

where,

B = ( T n ( s ) = x ) {\displaystyle B=(T_{n}(s)=x)}
A i = ( s = R ( K i ) ) {\displaystyle A_{i}=(s=R(K_{i}))}

The extended form relies on the law of total probability. This means that the A i {\displaystyle A_{i}} must be distinct possibilities, which is given by the condition that each K i {\displaystyle K_{i}} produce a different infinite string. Also one of the conditions A i {\displaystyle A_{i}} must be true. This must be true, as in the limit as n tends to infinity, there is always at least one program that produces T n ( s ) {\displaystyle T_{n}(s)} .

Then using the extended form and substituting for B {\displaystyle B} and A i {\displaystyle A_{i}} gives,

P ( s = R ( K i ) T n ( s ) = x ) = P ( T n ( s ) = x s = R ( K i ) ) P ( s = R ( K i ) ) j P ( T n ( s ) = x s = R ( K j ) ) P ( s = R ( K j ) ) {\displaystyle P(s=R(K_{i})\mid T_{n}(s)=x)={\frac {P(T_{n}(s)=x\mid s=R(K_{i}))\,P(s=R(K_{i}))}{\sum \limits _{j}P(T_{n}(s)=x\mid s=R(K_{j}))\,P(s=R(K_{j}))}}\cdot }

As K i {\displaystyle K_{i}} are chosen so that T n ( R ( K i ) ) = x {\displaystyle T_{n}(R(K_{i}))=x} , then,

P ( T n ( s ) = x s = R ( K i ) ) = 1 {\displaystyle P(T_{n}(s)=x\mid s=R(K_{i}))=1}

The a-priori probability of the string being produced from the program, given no information about the string, is based on the size of the program,

P ( s = R ( K i ) ) = 2 I ( K i ) {\displaystyle P(s=R(K_{i}))=2^{-I(K_{i})}}

giving,

P ( s = R ( K i ) T n ( s ) = x ) = 2 I ( K i ) j 2 I ( K j ) {\displaystyle P(s=R(K_{i})\mid T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{\sum \limits _{j}2^{-I(K_{j})}}}\cdot }

Programs that are the same or longer than the length of x provide no predictive power. Separate them out giving,

P ( s = R ( K i ) T n ( s ) = x ) = 2 I ( K i ) j : I ( K j ) < n 2 I ( K j ) + j : I ( K j ) >= n 2 I ( K j ) {\displaystyle P(s=R(K_{i})\mid T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{\sum \limits _{j:I(K_{j})<n}2^{-I(K_{j})}+\sum \limits _{j:I(K_{j})>=n}2^{-I(K_{j})}}}\cdot }

Then identify the two probabilities as,

Probability that x has a pattern = j : I ( K j ) < n 2 I ( K j ) {\displaystyle =\sum \limits _{j:I(K_{j})<n}2^{-I(K_{j})}}

The opposite of this,

Probability that x is a random set of bits = j : I ( K j ) >= n 2 I ( K j ) {\displaystyle =\sum \limits _{j:I(K_{j})>=n}2^{-I(K_{j})}}

But the prior probability that x is a random set of bits is 2 n {\displaystyle 2^{-n}} . So,

P ( s = R ( K i ) T n ( s ) = x ) = 2 I ( K i ) 2 n + j : I ( K j ) < n 2 I ( K j ) {\displaystyle P(s=R(K_{i})\mid T_{n}(s)=x)={\frac {2^{-I(K_{i})}}{2^{-n}+\sum \limits _{j:I(K_{j})<n}2^{-I(K_{j})}}}\cdot }

The probability that the source is random, or unpredictable is,

P ( random ( s ) T n ( s ) = x ) = 2 n 2 n + j : I ( K j ) < n 2 I ( K j ) {\displaystyle P(\operatorname {random} (s)\mid T_{n}(s)=x)={\frac {2^{-n}}{2^{-n}+\sum \limits _{j:I(K_{j})<n}2^{-I(K_{j})}}}\cdot }

Key people

See also

References

  1. "Abduction".
  2. Pfeifer, Niki; Kleiter, Gernot D. (2006). "INFERENCE IN CONDITIONAL PROBABILITY LOGIC". Kybernetika. 42 (4): 391–404.
  3. "Conditional Probability". Artificial Intelligence - Foundations of computational agents.
  4. "Introduction to the theory of Inductive Logic Programming (ILP)".
  5. Li, M. and Vitanyi, P., An Introduction to Kolmogorov Complexity and Its Applications, 3rd Edition, Springer Science and Business Media, N.Y., 2008, p 347
  6. Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma. Feb 4, 1960, revision, Nov., 1960.
  7. Solomonoff, R., "A Formal Theory of Inductive Inference, Part I" Information and Control, Vol 7, No. 1 pp 1–22, March 1964.
  8. Solomonoff, R., "A Formal Theory of Inductive Inference, Part II" Information and Control, Vol 7, No. 2 pp 224–254, June 1964.
  9. Wallace, Chris; Boulton (1968). "An information measure for classification". Computer Journal. 11 (2): 185–194.
  10. Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0005-1098(78)90005-5, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0005-1098(78)90005-5 instead.
  11. Allison, Lloyd. "Minimum Message Length (MML) – LA's MML introduction".
  12. Oliver, J. J.; Baxter, Rohan A. "MML and Bayesianism: Similarities and Differences (Introduction to Minimum Encoding Inference – Part II)".
  13. Hutter, Marcus (1998). Sequential Decisions Based on Algorithmic Probability. Springer. ISBN 3-540-22139-5.

External links

Categories: