cs562 Notes
Mar. 31, 2014

Review of Neural Networks and Completion of the Perceptron Learning Rule

Next up: Bayes Theory

Based upon Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig

Previously we discussed agents

	This time we will discuss a new type of agent

	Decision Theoretic agent

	Decision Theory = probability theory + utility theory

	Utility theory says that we should try to maximize the expected utility of action
	choices

	Agents’ actions should yield the highest expected utility averaged over all 
	possible outcomes of the action

	A rational Decision Theory agent should have the following properties

	Inputs: Percepts

	Outputs: Actions

	Given: Rules consisting of a set of probabilistic beliefs about the state of the
	world


The DT agent should do the following:

	Calculate updated probabilities for the current state based upon evidence from
	the current percepts and previous actions

	Calculate resulting probabilities for actions given probabilities of current
	states and action rules/descriptions

	Select the action with the highest expected utility given probabilities of 
	outcomes and utility information

We need basic probability notation to understand probability theory

	Let P(A) represent the prior probability or unconditional probability that A
	is true.

	Example:

	P(Cavity) = 0.1

	Example of random variables:

	P(Weather = Sunny) = 0.7
	P(Weather = Rain) = 0.2
	P(Weather = Cloudy) = 0.08
	P(Weather = Snow = 0.02

	Notice the domain of values is for P(Weather) = <0.7,0.2,0.08,0.02>

	This defines a probability distribution for Weather, a random variable.

	It is possible to use combinations of variables such as P(Weather,Cavity)
	that represent the probability of combinations of values.

	We can also use logical connectors

	P(Cavity and not Insured) = 0.06

	Indicating there is a 6% chance that someone has a cavity and no insurance

Conditional probability

	Conditional or posterior probabilities use the notation P(A|B)

	This means the probability of A given that _all_we_know_is_ B

	P(Cavity|Toothache) = 0.8

	Conditional probabilities are defined in terms of unconditional probabilities

	P(A|B) = P(A and B) / P(B)

	This holds as long as P(B) > 0

	Additionally,

	P(A and B) = P(A | B) * P(B)

	and

	P(A and B) = P(B | A) * P(A)

Probability Axioms

	All probabilities are between 0 and 1

		0 <= P(A) <= 1

	True propositions have a probability of 1 and false propositions have a 
	probability of zero

		P(True) = 1  and P(False) = 0

	The probability of a disjunction is

		P(A or B) = P(A) + P(B) - P(A and B)

	This can be represented as a Venn Diagram


	Example:

		P(A) = 0.4
		P(B) = 0.3
		P(A and B) = 0
		P(A or B) = ?

	If an agent violates these axioms, it may be possible to construct an agent
	that wins in contests against the agent that violates the axioms.

Joint Probability Distribution

	Specifies an agent’s probability assignments to all propositions in the domain

	The Joint probability distribution is defined as P(X_1,. . ., X_n) for all 
	assignments of particular values to the variables.

	Example:

		Toothache	~Toothache
	Cavity	0.04		0.06
	~Cavity	0.01		0.89

	Find P(Cavity or Toothache)

	Find P(Cavity | Toothache)

Bayes Rule

	Recall that:

	P(A and B) = P(A|B)*P(B)
	P(A and B) = P(B|A)*P(A)

	Therefore

	P(A|B)*P(B) = P(B|A)*P(A)

	And

	P(A|B) = ( P(B|A)*P(A) ) / P(B)

	This also applies to more than one item of evidence


	Example:

	Assume a doctor knows the probability of a meningitis patient having a stiff neck
	is 50%

	Assume the probability of a patient having meningitis is 1/50000

	Assume the probability of a patient having a stiff neck is 1/20

	P(S|M) = 0.5

	P(M) = 1/50000

	P(S) = 1/20

	P(M|S) = 0.5*1/50000 / 1/20 = 0.0002