THE EM ALGORITHM

The EM algorithm can be used even for variables whose value is never directly observed, provided the general form of the probability distribution governing these variables is known. 

Estimating Means of k Gaussian's

• Consider a problem in which the data D is a set of instances generated by a probability distribution that is a mixture of k distinct Normal distributions.

• This problem setting is illustrated in Figure for the case where k = 2 and where the instances are the points shown along the x axis.
• Each instance is generated using a two-step process.
• First, one of the k Normal distributions is selected at random.
• Second, a single random instance xi is generated according to this selected distribution.
• This process is repeated to generate a set of data points as shown in the figure.
• To simplify, consider the special case
• The selection of the single Normal distribution at each step is based on choosing each with uniform probability
• Each of the k Normal distributions has the same variance σ², known value.
• The learning task is to output a hypothesis h = (μ1 , . . . ,μk) that describes the means of each of the k distributions.
• We would like to find a maximum likelihood hypothesis for these means; that is, a hypothesis h that maximizes p(D |h).

• Our problem here, however, involves a mixture of k different Normal distributions, and we cannot observe which instances were generated by which distribution.
• Consider full description of each instance as the triple (xi, zi1, zi2),
• where xi is the observed value of the ith instance and
• where zi1 and zi2 indicate which of the two Normal distributions was used to generate the value xi
• In particular, zij has the value 1 if xi was created by the j^th Normal distribution and 0 otherwise.
• Here xi is the observed variable in the description of the instance, and zil and zi2 are hidden variables.
• If the values of zil and zi2 were observed, we could use following Equation to solve for the means p1 and p2
• Because they are not, we will instead use the EM algorithm

EM algorithm

 

 

 

BAYESIAN BELIEF NETWORKS

• The naive Bayes classifier makes significant use of the assumption that the values of the attributes a1 . . .an are conditionally independent given the target value v.
• This assumption dramatically reduces the complexity of learning the target function 

A Bayesian belief network describes the probability distribution governing a set of variables by specifying a set of conditional independence assumptions along with a set of conditional probabilities

Bayesian belief networks allow stating conditional independence assumptions that apply to subsets of the variables

 

Notation

• Consider an arbitrary set of random variables Y1 . . . Yn , where each variable Yi can take on the set of possible values V(Yi).
• The joint space of the set of variables Y to be the cross product V(Y1) x V(Y2) x. . . V(Yn).
• In other words, each item in the joint space corresponds to one of the possible assignments of values to the tuple of variables (Y1 . . . Yn). The probability distribution over this joint' space is called the joint probability distribution.
• The joint probability distribution specifies the probability for each of the possible variable bindings for the tuple (Y1 . . . Yn).
• A Bayesian belief network describes the joint probability distribution for a set of variables. 

Conditional Independence 

Let X, Y, and Z be three discrete-valued random variables. X is conditionally independent of Y given Z if the probability distribution governing X is independent of the value of Y given a value for Z, that is, if

Where,

The above expression is written in abbreviated form as 

P(X | Y, Z) = P(X | Z) 

Conditional independence can be extended to sets of variables. The set of variables X1 . . . Xl is conditionally independent of the set of variables Y1 . . . Ym given the set of variables Z1 . . . Zn if

The naive Bayes classifier assumes that the instance attribute A1 is conditionally independent of instance attribute A2 given the target value V. This allows the naive Bayes classifier to calculate P(Al, A2 | V) as follows,

Representation 

A Bayesian belief network represents the joint probability distribution for a set of variables. Bayesian networks (BN) are represented by directed acyclic graphs.

The Bayesian network in above figure represents the joint probability distribution over the boolean variables Storm, Lightning, Thunder, ForestFire, Campfire, and BusTourGroup

 

A Bayesian network (BN) represents the joint probability distribution by specifying a set of conditional independence assumptions

• BN represented by a directed acyclic graph, together with sets of local conditional probabilities
• Each variable in the joint space is represented by a node in the Bayesian network
• The network arcs represent the assertion that the variable is conditionally independent of its non-descendants in the network given its immediate predecessors in the network.
• A conditional probability table (CPT) is given for each variable, describing the probability distribution for that variable given the values of its immediate predecessors 

The joint probability for any desired assignment of values (y1, . . . , yn) to the tuple of network variables (Y1 . . . Ym) can be computed by the formula

Where, Parents(Yi) denotes the set of immediate predecessors of Yi in the network.

Example:

Consider the node Campfire. The network nodes and arcs represent the assertion that Campfire is conditionally independent of its non-descendants Lightning and Thunder, given its immediate parents Storm and BusTourGroup

This means that once we know the value of the variables Storm and BusTourGroup, the variables Lightning and Thunder provide no additional information about Campfire

The conditional probability table associated with the variable Campfire. The assertion is P(Campfire = True | Storm = True, BusTourGroup = True) = 0.4

Inference

• Use a Bayesian network to infer the value of some target variable (e.g., ForestFire) given the observed values of the other variables.
• Inference can be straightforward if values for all of the other variables in the network are known exactly.
• A Bayesian network can be used to compute the probability distribution for any subset of network variables given the values or distributions for any subset of the remaining variables.
• An arbitrary Bayesian network is known to be NP-hard

Learning Bayesian Belief Networks 

Affective algorithms can be considered for learning Bayesian belief networks from training data by considering several different settings for learning problem

Ø  First, the network structure might be given in advance, or it might have to be inferred from the training data.

Ø  Second, all the network variables might be directly observable in each training example, or some might be unobservable.

• In the case where the network structure is given in advance and the variables are fully observable in the training examples, learning the conditional probability tables is straightforward and estimate the conditional probability table entries
• In the case where the network structure is given but only some of the variable values are observable in the training data, the learning problem is more difficult. The learning problem can be compared to learning weights for an ANN. 

Gradient Ascent Training of Bayesian Network 

The gradient ascent rule which maximizes P(D|h) by following the gradient of ln P(D|h) with respect to the parameters that define the conditional probability tables of the Bayesian network.

 

Let wijk denote a single entry in one of the conditional probability tables. In particular wijk denote the conditional probability that the network variable Yi will take on the value yi, given that its immediate parents Ui take on the values given by uik.

The gradient of ln P(D|h) is given by the derivatives 

 for each of the wijk. As shown below, each of these derivatives can be calculated as

Derive the gradient defined by the set of derivatives 

for all i, j, and k. Assuming the training examples d in the data set D are drawn independently, we write this derivative as

We write the abbreviation Ph(D) to represent P(D|h).

NAIVE BAYES CLASSIFIER

• The naive Bayes classifier applies to learning tasks where each instance x is described by a conjunction of attribute values and where the target function f (x) can take on any value from some finite set V.
• A set of training examples of the target function is provided, and a new instance is presented, described by the tuple of attribute values (al, a2.. .am).
• The learner is asked to predict the target value, or classification, for this new instance.

The Bayesian approach to classifying the new instance is to assign the most probable target value, VMAP, given the attribute values (al, a2.. .am) that describe the instance

Use Bayes theorem to rewrite this expression as 

• The naive Bayes classifier is based on the assumption that the attribute values are conditionally independent given the target value. Means, the assumption is that given the target value of the instance, the probability of observing the conjunction (al, a2.. .am), is just the product of the probabilities for the individual attributes:

Substituting this into Equation (1), 

Naive Bayes classifier:

Where, VNB denotes the target value output by the naive Bayes classifier

An Illustrative Example

• Let us apply the naive Bayes classifier to a concept learning problem i.e., classifying days according to whether someone will play tennis.
• The below table provides a set of 14 training examples of the target concept PlayTennis, where each day is described by the attributes Outlook, Temperature, Humidity, and Wind

Day	Outlook	Temperature	Humidity	Wind	PlayTennis
D1	Sunny	Hot	High	Weak	No
D2	Sunny	Hot	High	Strong	No
D3	Overcast	Hot	High	Weak	Yes
D4	Rain	Mild	High	Weak	Yes
D5	Rain	Cool	Normal	Weak	Yes
D6	Rain	Cool	Normal	Strong	No
D7	Overcast	Cool	Normal	Strong	Yes
D8	Sunny	Mild	High	Weak	No
D9	Sunny	Cool	Normal	Weak	Yes
D10	Rain	Mild	Normal	Weak	Yes
D11	Sunny	Mild	Normal	Strong	Yes
D12	Overcast	Mild	High	Strong	Yes
D13	Overcast	Hot	Normal	Weak	Yes
D14	Rain	Mild	High	Strong	No

• Use the naive Bayes classifier and the training data from this table to classify the following novel instance:

< Outlook = sunny, Temperature = cool, Humidity = high, Wind = strong >

• Our task is to predict the target value (yes or no) of the target concept PlayTennis for this new instance

The probabilities of the different target values can easily be estimated based on their frequencies over the 14 training examples

• P(P1ayTennis = yes) = 9/14 = 0.64
• P(P1ayTennis = no) = 5/14 = 0.36

 Similarly, estimate the conditional probabilities. For example, those for Wind = strong

• P(Wind = strong | PlayTennis = yes) = 3/9 = 0.33
• P(Wind = strong | PlayTennis = no) = 3/5 = 0.60

 Calculate VNB according to Equation (1) 

Thus, the naive Bayes classifier assigns the target value PlayTennis = no to this new instance, based on the probability estimates learned from the training data.

By normalizing the above quantities to sum to one, calculate the conditional probability that the target value is no, given the observed attribute values

 

 

Estimating Probabilities

• We have estimated probabilities by the fraction of times the event is observed to occur over the total number of opportunities.
• For example, in the above case we estimated P(Wind = strong | Play Tennis = no) by the fraction nc /n where, n = 5 is the total number of training examples for which PlayTennis = no, and nc = 3 is the number of these for which Wind = strong.
• When nc = 0, then nc /n will be zero and this probability term will dominate the quantity calculated in Equation (2) requires multiplying all the other probability terms by this zero value
• To avoid this difficulty we can adopt a Bayesian approach to estimating the probability, using the m-estimate defined as follows

 m -estimate of probability:

• p is our prior estimate of the probability we wish to determine, and m is a constant called the equivalent sample size, which determines how heavily to weight p relative to the observed data
• Method for choosing p in the absence of other information is to assume uniform priors; that is, if an attribute has k possible values we set p = 1 /k.