Understanding Bayes Net Inference Algorithm from Russel & Norvig

[0rthodontist]

I don't understand this simple algorithm from Russel & Norvig for computing a distribution of X given certain observed values e:

function Enumeration-Ask(X, e, bn) returns a distribution over X
	inputs: X, the query variable
		e, observed values for variables E
		bn, a Bayes net with variables {X} u E u Y /* Y = hidden variables */
	
	Q(X) <- a distribution over X, initially empty
	for each value xi of X do
		extend e with value xi for X
		Q(xi) <- Enumerate-All(Vars[bn], e)
	return Normalize(Q(X))
	
function Enumerate-All(vars, e) returns a real number
	if Empty?(vars) then return 1.0
	Y <- First(vars)
	if Y has value y in e
		then return P(y | parents(Y)) * Enumerate-All(Rest(vars), e)
		else return the sum over y of P(y | parents(Y)) * Enumerate-All(Rest(vars), ey)
			where ey is e extended with Y = y

I am having trouble understanding exactly what Enumerate-All does. Specifically I do not understand how P(y | parents(Y)) is computed. We don't know the values that the parents of Y take, do we?

 

[Future Bruno]

Can you explain it in more detail?Enumerate-All is a recursive algorithm that computes the probability of a given set of variables (vars) given certain observed values (e). This is done by recursively considering each variable Y in the set of variables Vars[bn] and computing the probability of Y given its parents. This is done by multiplying P(y | parents(Y)) with the result of Enumerate-All on the rest of the variables, which is the probability of the remaining variables given the same set of observed values. The probability of a variable Y given its parents can be obtained from the Bayes net. Specifically, it is the conditional probability of Y given the values of its parents, which is usually stored in a probability table.

 

[ravenprp]

The Bayes Net Inference Algorithm from Russel & Norvig is a method for calculating a probability distribution over a query variable X, given certain observed values e and a Bayes net bn. The algorithm is based on the principle of enumeration, which involves considering all possible combinations of values for the variables in the Bayes net.

The first step in the algorithm is to define a distribution Q(X) over the query variable X. This distribution is initially empty, and will be filled in by the algorithm.

Next, the algorithm considers each possible value xi for X and extends the observed values e with this value. This means that e now includes the value of X, as well as any other observed values from the variables E. This extended set of values is then used in a function called Enumerate-All.

Enumerate-All is a recursive function that calculates the probability of a particular combination of values for all the variables in the Bayes net. It takes two inputs: a set of variables and a set of observed values. If the set of variables is empty, the function returns 1.0, indicating that the probability of this combination of values is 100%.

The function then takes the first variable Y from the set of variables and checks if it has a value in the observed values e. If it does, then the probability of this value given its parents is calculated using the conditional probability table in the Bayes net. This probability is then multiplied by the result of the function Enumerate-All on the remaining variables and observed values.

If Y does not have a value in e, then the function calculates the sum of probabilities for all possible values of Y given its parents, multiplied by the result of Enumerate-All on the remaining variables and an extended set of observed values e. This extended set of observed values includes the value of Y that is being considered.

The function continues to recursively calculate probabilities for each variable in the set, until all variables have been considered. The result of Enumerate-All is the total probability of the entire combination of values for all variables.

Going back to the original algorithm, after Enumerate-All has been called for each value of X, the distribution Q(X) is normalized, meaning that all the probabilities are scaled so that they sum to 1. This gives us the final probability distribution over X.

In summary, Enumerate-All is a recursive function that calculates the probability of a particular combination of values for all variables in a Bay