Reasoning Under Uncertainty
Logic based knowledge representation and reasoning methods mostly assume that knowledge is certain. Often, this is not the case (or it is impossible to list all assumptions that make it certain):
- When going to the airport by car, how early should I start? 45 minutes should be enough from Liverpool to Manchester Airport, but only under the assumption that there are no accidents, no lane closures, that my car does not break down, and so on.
-
A dental patient has a toothache. Does the patient have a cavity? You might say:
\[\text{Toothache}(x)\rightarrow\text{Cavity}(x)\]This is not right as there are many factors that play into this and not just the fact that they have a toothache.
Uncertainty
Trying to use exact rules to cope with a domain like medical diagnosis or traffic fails for three main reasons:
- Laziness
- It is too much work to list an exception-less set of rules.
- Theoretical ignorance
- Medical science has, in many cases, no strict laws connecting symptoms with diseases.
- Practical ignorance
- Even if we have strict laws, we might be uncertain about a particular patient because not all the necessary tests have been or can be run.
Probability in AI
Probability provides a way of summarising the uncertainty that comes form our laziness and ignorance.
We might not know for sure what disease a particular patient has, but we believe that there is an 80% chance that a patient with toothache has a cavity. The 80% summarises those cases in which all the factors needed for a cavity to cause a toothache are present and other cases in which the patient has both toothache and cavity but the two are unconnected.
The missing 20% summarises all the other possible causes we are too lazy or ignorant to find.
Discrete Probability
We represent random experiments using discrete probability spaces $(S,P)$ consisting of:
- The sample space $S$ of all elementary events $x\in S$. Members of $S$ are also called outcomes of the experiment.
- A probability distribution $P$ assigning a real number $P(x)$ to every elementary event $x\in S$ such that:
- For every $x\in S: 0\leq P(x) \leq 1$
- And $\sum_{x\in S}P(x)=1$
Recall that if $S$ consists of $x_1,\ldots,x_n$, then:
\[\sum_{x\in S}P(x)=P(x_1)+\ldots+P(x_n)\]Example - Flipping a Fair Coin
Consider the random experiment of flipping a coin. The then corresponding probability space $(S,P)$ is given by:
- $S=\{H,T\}$
- $P(H)=P(T)=\frac{1}{2}$
Consider the random experiment of flipping a count two times, one after the other. Then the corresponding probability space $(S,P)$ is:
- $S=\{HH,HT,TH,TT\}$
- $P(HH)=P(HT)=P(TH)=P(TT)=\frac{1}{4}$
Example - Rolling a fair die
Consider the random experiment of rolling a die. Then the corresponding probability space $(S, P)$ is given by:
- S = {1, 2, 3, 4, 5, 6};
- For every $x ∈ S: P(x) = \frac{1}{6}$
Consider the random experiment of rolling a die $n$ times. Then the corresponding probability space $(S, P)$ is given as follows:
- $S$ is the set of sequences of length $n$ over the alphabet $\{1,\ldots, 6\}$
- Sometimes denoted $\{1,\ldots, 6\}^n$
- $P(x) = \frac{1}{6^n}$ for every elementary event $x$, since $S$ has $6^n$ elements.
Uniform Probability Distributions
A probability distribution is uniform if every outcome is equally likely. For uniform probability distributions, the probability of an outcome $x$ is 1 divided by the number $\vert S\vert$ of outcomes in $S$:
\[P(x)=\frac{1}{\vert S\vert }\]