Advanced Machine Learning | AI351

MODULE 1
Generative Models for Discrete Data
Introduction
We discuss how to classify a feature vector x by applying Bayes rule to a generative
classifier of the form:
p(y = c|x, ) p(x|y = c, )p(y = c|

) where, y is a label that takes the value of c class.

The key to using such models is specifying a suitable form for the class-conditional
density ), which defines what kind of data we expect to see in each class. In
this lecture, we focus on the case where the observed data are [Link] also discuss
how to infer the unknown parameters of such models.

1.1:Bayesian concept learning

Concept learning is the task of learning a general rule (concept) from specific training
examples.
Concept learning is equivalent to binary classification, e.g. define f(x)=1 if x is an
example of the concept C, and f(x)=0, otherwise. The goal is to learn the indicator
function f which defines which elements are in the set C. Standard binary classification
techniques require positive and negative examples. However, here we consider a way
to learn only from positive examples.
We will consider a simple example of concept learning called the number game.
Choose a simple arithmetical concept C, such as "prime number" or "a number between
1 and 10". We then give you a series of randomly chosen positive examples D =
{x1,...,xN } drawn from C . We now ask you whether some new test case belongs to
C ( i.e., we ask you to classify ).
Given: all numbers are integers between 1 and 100.

Given: '16' is a positive example of the concept.

Question: What other numbers do you think are positive? 17? 6? 32? 99?
Analysis: It is hard to tell with only one example, so your predictions will be vague. Numbers

Similar in what way?

17 is similar, because it is "close by",

Dept of AIML, CIT 1

 Advanced Machine Learning | AI351

6 is similar because it has a digit in common,

32 is similar because it is also even and a power of 2,

but 99 does not seem similar.

Analysis: We can represent this as a probability distribution, ( ) which is the probability

that given the data D for any 1 100 .This is called the posterior predictive
distribution. The empirical predictive distribution averaged over 8 persons in the number
game is shown. E.g.

Given: = {16, 8, 2 64}

Analysis: guess that the hidden concept is

Given: = {16,23,19,20}
Analysis: you will get a different kind of
generalization (numbers near 20)
= {16}
= {60}

= {16,8,2,64}
= {16,23,19,20}
The classic approach to induction is to
assume that we have a hypothesis space
of concepts, H, such as:

odd numbers,

even numbers,

all numbers between 1 and 100,

powers of two, all numbers ending in j (for 0 j 9),

etc.

The subset of H that is consistent with the data D is called the version space. As we see more
examples, the version space shrinks and we become increasingly certain about the concept.

Likelihood
Why we choose htwo= "powers of two", and not, say, heven D=
{16, 8, 2, 64},? Can we provide a Bayesian explanation of this.

Dept of AIML, CIT 2

 Advanced Machine Learning | AI351

We assume that examples are sampled uniformly at random from a concept h. Given this
assumption, the probability of independently sampling N items (with replacement) from h is
given by

This crucial equation embodies what Tenenbaum calls the size principle, which
means the model favors the simplest (smallest) hypothesis consistent with the data.
To see how it works, let D = {16}. Then p(D|htwo) = 1/6, since there are only 6
powers of two less than 100, but p(D|heven) = 1/50, since there are 50 even numbers.
So the likelihood that h = htwo is higher than if h = heven. After 4 examples, the
likelihood of htwo is (1/6)4 = 7.7 × 10 4, whereas the likelihood of heven is (1/50)4 =
1.6 × 10 7. This is a likelihood ratio of almost 5000:1 in favor of htwo. This
quantifies our earlier intuition that D = {16, 8, 2, 64} would be a very suspicious
coincidence if generated by heven.

Prior
The example shows that although the data ( D = {16, 8, 2, 64} ) might make the

hypothesis why 32 is missing), it feels conceptually unnatural. In Bayesian reasoning, this

intuition is captured by assigning lower prior probability to such unnatural hypotheses.
Priors reflect background knowledge and can differ between individuals (e.g., a child vs. a
math professor), though this can be modeled by using the same hypothesis space but
assigning zero or low prior weight to advanced concepts.

Posterior
The posterior is simply the likelihood times the prior, normalized. In this context we have

h) is 1 iff (if and only if)all the data are in the extension of the hypothesis h.

In general, when we have enough data, the posterior p(h D) becomes peaked on a single
concept, namely the MAP estimate, i.e.,

Dept of AIML, CIT 3

 Advanced Machine Learning | AI351

Note that the MAP estimate can be written as

Since the likelihood term depends exponentially on N, and the prior stays constant, as we get
more and more data, the MAP estimate converges towards the maximum likelihood estimate
or MLE:

In other words, if we have enough data, we see that the data overwhelms the prior. In this
case, the MAP estimate converges towards the MLE.

Dept of AIML, CIT 4

 Advanced Machine Learning | AI351

Posterior predictive distribution

The posterior predictive distribution in this context is given by

This is just a weighted average of the predictions of each individual hypothesis and is called
Bayes model averaging

Figure 3.4 Posterior over

hypotheses and the corresponding
predictive distribution after seeing
one example, D = {16}. A dot means
this number is consistent with this
hypothesis.
The graph p(h|D) on
the right is the weight given to
hypothesis h. By taking a weighed
sum of dots, we get p x C|D)
(top).
Based on Figure 2.9 of (Tenenbaum
1999). Figure generated by
numbersGame.

When we have a small and/or ambiguous dataset, the posterior p(h|D) is vague, which
induces a broad predictive distribution. However
posterior becomes a delta function centered at the MAP estimate. In this case, the predictive
distribution becomes

This is called a plug-in approximation to the predictive density and is very widely used, due
to its simplicity.

A more complex prior

To model human behavior, Tenenbaum used a slightly more sophisticated prior which was
derived by analysing some experimental data of how people measure similarity between
numbers Thus the prior is a mixture of two priors, one over arithmetical rules, and one over
intervals:

Dept of AIML, CIT 5

 Advanced Machine Learning | AI351

3.4 The Dirichlet-multinomial model

The Dirichlet Multinomial model estimates the probabilities of multiple categories. Example: A

dice with K sides, each with probability k.

Widely used in:

Text analysis
Biosequence analysis
Other categorical data applications

3.4.1 Likelihood
Suppose we observe N dice rolls:

D={X1,X2 XN} ,xi K}

Assume the data is independent and identically distributed (iid),the likelihood has
the form

Where, is the number of times event k occured (these are the sufficient
statistics for this model). The likelihood for the multinomial model has the same form, up to an
irrelevant constant factor.
 Advanced Machine Learning | AI351

3.4.2 Prior

= k) lies in the K-dimensional probability simplex

We need a prior that supports all values in the probability simplex and is conjugate
to the multinomial likelihood

The Dirichlet distribution satisfies both conditions and is used as the prior.

3.4.3 Posterior
Posterior=Likelihood * Prior

The posterior is obtained by adding the prior hyperparameters (pseudo-counts) k

to the empirical counts Nk.

The mode of this posterior, also called the MAP estimate, can be derived using
calculus. However, we must enforce the constraint that the probabilities sum to 1,
i.e., k k=1.

To handle this constraint, we use a Lagrange multiplier. The constrained objective

function, known as the Lagrangian, is given by the sum of the log-likelihood, the
log-prior, and the constraint term.
 Advanced Machine Learning | AI351

To simplify notation, we define .

Taking deriv the original constraint:

Takin k yields

-to-one constraint:

where is the equivalent sample size of the

prior. Thus the MAP estimate is given by
 Advanced Machine Learning | AI351

k= 1, we recover the MLE:

This is just the empirical fraction of times face k shows up.

3.4.4 Posterior predictive

The posterior predictive distribution for a single multinoulli trial is given by the
following expression:

Here, -j denotes all components of except j.

This expression avoids the zero-count problem, which is especially important in the
multinomial case. The likelihood of data sparsity increases when the data are divided
into many categories, making Bayesian smoothing crucial.
 Advanced Machine Learning | AI351

Worked Example 1: Language Models Using Bag of Words

One application of Bayesian smoothing with the Dirichlet-multinomial model is

language modeling, which involves predicting which words are likely to occur next
in a sequence. Here, we will use a simple approach, assuming that the i-th word,
Xi , is sampled independently from all other words according to a
categorical distribution ). This is known as the bag-of-words model.

Given a past sequence of words, we can predict the next word by estimating the
probability of each word in the vocabulary.

Mary had a little lamb, little lamb, little lamb,

Mary had a little lamb, its fleece as white as snow
Index 1 2 3 4 5 6 7 8 9 10
Fixed Mary lamb little big fleece white black snow rain unk
word
Count 2 4 4 0 1 1 0 1 0 4

Here, unk stands for unknown words that do not appear elsewhere in the vocabulary.

To encode each line of the nursery rhyme:

1. Strip punctuation.
2. Remove stop words
3. Optionally, perform stemming reducing words to their base form (e.g.,

4. Replace each word by its vocabulary index, giving:

1 10 3 2 3 2 3 2
1 10 3 2 10 5 10 6 8
 Advanced Machine Learning | AI351

Next, we ignore word order and count how often each word occurs, producing a
histogram of word counts:
Index 1 2 3 4 5 6 7 8 9 10
Fixed Mary lamb little big fleece white black snow rain unk
Word
Count 2 4 4 0 1 1 0 1 0 4

Denote the above word counts by Nj.. If we place a Dirichlet prior prior for
, the posterior predictive distribution is given by

j = 1, we get

The modes of this predictive distribution are X=2 X=10

-zero probability,
even though they have never been observed in the data.

More sophisticated language models can improve upon this simple bag-of-words
approach.
 Advanced Machine Learning | AI351

0+1 /10 +10,

0+1 /10 +10, 3+1 /10 +10)

= ( 3/20,3/20,3/20,1/20,2/20, 1/20,1/20,1/20,1/20,4/20)

The resulting distribution assigns higher probabilities to frequently occurring

words while also giving small non-zero probabilities to unseen words.
 SAMPLE QUESTIONS
1. What is meant by the version space?
2. State Bayes’ rule for generative classification.
3. Explain why prior knowledge is important in Bayesian learning.
4. Explain the difference between MLE and MAP.
5. Write the formula for the posterior in Dirichlet-multinomial model.
6. Write the probability density function of the Beta distribution.
7. Why is the Dirichlet distribution conjugate to the multinomial?
8. Why do we use Lagrange multipliers when deriving MAP in Dirichlet-
multinomial model.?
9. Explain Bayesian smoothing in simple terms.
10. Suppose D = {16}.
If hypothesis h₁ = “powers of two” (6 elements)
and h₂ = “even numbers” (50 elements),
compute:
a) p(D|h₁)
b) p(D|h₂)
c) Likelihood ratio
11. Given D = {16, 8, 2, 64}, compute the likelihood under:
a) h = powers of two
b) h = even numbers
12. A dice is rolled 10 times with counts:
(N1=3, N2=2, N3=1, N4=2, N5=1, N6=1)
a) Compute the MLE estimate.
b) Assume Dirichlet prior α = (1,1,1,1,1,1).
Compute the MAP estimate.
13. Vocabulary size K = 5.
Word counts: (4, 3, 2, 1, 0)
α = (1,1,1,1,1)
Compute posterior predictive probability.
[Link] of Words Assumption
Given the two sequences:
1. Mary had a little lamb, little lamb, little lamb
2. Mary had a little lamb, its fleece was white snow
Questions:
1. Write the count vector c
2. Compute the total number of words N.
3. Estimate the maximum likelihood estimate (MLE) of θ,
where: θj=cj/N
4. Write the probability distribution θ.
[Link] 2:
Given the two documents:
1. I love machine learning and AI
2. AI and machine learning are powerful
Questions:
1. Write the vocabulary.
2. Construct the count vector c.
3. Compute total number of words N.
4. Estimate the maximum likelihood estimate (MLE) of θ, where: θj=cj/N
5. Write the probability distribution θ.
15. Consider the dataset 𝐷 = {16,8,2,64}in the number concept learning
problem, where hypotheses include:
 ℎ1 : Powers of two
 ℎ2 : Even numbers
Answer the following:
a) Analyze why the dataset 𝐷strongly supports the hypothesis “powers of two”
over “even numbers” using the size principle and likelihood computation.
b) Derive why the likelihood of a hypothesis depends exponentially on the
number of observations 𝑁.
c) Compare the behavior of MAP and MLE estimates when:
i) Data is small
ii) Data is large
d) Analyze how the prior influences the posterior when the hypothesis is
conceptually “unnatural.”
16. Consider a Binomial likelihood with parameter 𝜃and a Beta prior 𝐵𝑒𝑡𝑎(𝛼, 𝛽).
a) Derive the likelihood, prior and posterior distribution.
b) Derive the MAP estimate.
c) Derive the posterior predictive distribution.

17. Explain the difference between Multinomial, Bernoulli, and Gaussian Naive
Bayes.
18. Derive the likelihood, prior, posterior distribution and posterior predictive of
Dirichlet multinomial model
19. Derive the MLE parameter estimates for Multinomial Naive Bayes.
20. Given a class with vocabulary size 𝑉=5
N=(8,2,0,0,0)
Total words = 10
Dirichlet prior: α=(1,1,1,1,1)
a) Compute MLE estimates.
b) Compute posterior parameters.
c) Compute posterior predictive probabilities.
d) Compare predictive probability with MLE for unseen words.
21. Consider the following training dataset used to build a Naive Bayes
classifier for medical diagnosis.
Training Data
Patient Fever Cough Fatigue Class
P1 1 1 1 Flu
P2 1 1 0 Flu
P3 1 0 1 Flu
P4 0 1 1 Cold
P5 0 1 0 Cold
P6 0 0 1 Allergy
P7 0 0 0 Allergy

Compute class priors (MLE).

b) Compute likelihoods using MLE.
c) Apply Laplace smoothing (α=1).
d) Classify new patient:
(𝐹𝑒𝑣𝑒𝑟 = 1, 𝐶𝑜𝑢𝑔ℎ = 1, 𝐹𝑎𝑡𝑖𝑔𝑢𝑒 = 0)