Hidden Variables
Chapter Seventy
Syllabus topic Module 2, "Hidden variables"
Pages 412 to 419 of 591
In one line
A hidden variable is one the model needs and the data does not record, and its absence destroys the counting that made the previous chapter easy.
A hidden variable, also called a latent variable, appears in the model but never in the data. Common cases across this syllabus: which cluster a point belongs to, which coin or which component produced an observation, the state of a system in Hidden Markov Models, the underlying cause behind a set of symptoms.
Why anyone would want one
A hidden variable is not a nuisance forced on the modeller. It is often the whole reason the model is small enough to learn, and a paper may ask why.
Take three lifestyle causes and three symptoms, all binary, where each symptom depends on all three causes.
Without a hidden node, each symptom's table has one row per combination of its three parents:
3 causes, one number each = 3
3 symptoms, 2**3 = 8 rows each = 24
total = 27 numbers
With one hidden node between them, standing for the underlying condition, the causes point at the hidden node and each symptom depends only on it:
3 causes, one number each = 3
the hidden node, 2**3 = 8 rows = 8
3 symptoms, one parent, 2 rows each = 6
total = 17 numbers
Twenty-seven numbers become seventeen, and the saving grows sharply with the number of symptoms: each further symptom costs 8 numbers in the first model and 2 in the second. And the second model says something the first does not, that the symptoms are conditionally independent given the condition, which is a claim about the world and may be false. A hidden variable buys a smaller model at the price of an assumption.
The measurement
# Hidden variables: what breaks when one column of the data is missing. The same
# twelve experiments are solved by counting when the coin is known, and are not
# solvable by counting at all when it is hidden.
import math
def lcg(seed):
x = seed
while True:
x = (1664525 * x + 1013904223) % (2 ** 32)
yield x / 2 ** 32
gen = lcg(20260930)
rnd = lambda: next(gen) # noqa: E731
P_A, P_B, MIX = 0.80, 0.30, 0.5 # the truth, which the learner never sees
FLIPS, RUNS = 10, 12
records = [] # (which coin, heads) -- 'which' is HIDDEN
for _ in range(RUNS):
coin = "A" if rnd() < MIX else "B"
p = P_A if coin == "A" else P_B
heads = sum(1 for _ in range(FLIPS) if rnd() < p)
records.append((coin, heads))
print("TWELVE EXPERIMENTS. each one: pick one of two coins, flip it %d times," % FLIPS)
print("record the number of heads. the COIN USED is the hidden variable.")
print()
print(" what was actually recorded:")
print(" heads out of %d : %s" % (FLIPS, " ".join("%2d" % h for _, h in records)))
print(" and what was NOT recorded, shown here only to prove the point:")
print(" coin used : %s" % " ".join(" %s" % c for c, _ in records))
print()
# ---- 1. with the hidden column, it is counting ------------------------------
print("IF THE COIN WERE KNOWN the data would be COMPLETE and the answer is a")
print("count, exactly as in the previous chapter:")
for label in ("A", "B"):
h = sum(x for c, x in records if c == label)
n = FLIPS * sum(1 for c, _ in records if c == label)
print(" coin %s: %d heads in %d flips -> p = %.4f (true %.2f)"
% (label, h, n, h / n, P_A if label == "A" else P_B))
print(" and the mixing weight is just how often each coin was chosen:")
print(" P(coin A) = %d/%d = %.4f (true %.2f)"
% (sum(1 for c, _ in records if c == "A"), RUNS,
sum(1 for c, _ in records if c == "A") / RUNS, MIX))
print()
# ---- 2. without it, there is nothing to count ------------------------------
print("WITHOUT IT, THERE IS NOTHING TO COUNT. to count the heads of coin A you")
print("must know which experiments used coin A, and that is the column you do")
print("not have. the two unknowns are locked together:")
print(" to estimate the parameters you need the coin assignments,")
print(" to infer the coin assignments you need the parameters.")
print()
# ---- 3. the naive repair, and how badly it does ---------------------------
pooled = sum(h for _, h in records) / (FLIPS * RUNS)
print("THE NAIVE REPAIR: ignore the hidden variable and pool every flip.")
print(" %d heads in %d flips -> one coin with p = %.4f"
% (sum(h for _, h in records), FLIPS * RUNS, pooled))
print(" which is neither %.2f nor %.2f. it is their average, and it describes"
% (P_A, P_B))
print(" NO coin in the experiment. worse, it is a measurably poorer")
print(" explanation of the same data:")
def loglik_one(p, heads):
return (heads * math.log(p) + (FLIPS - heads) * math.log(1 - p))
def loglik_single(p):
return sum(loglik_one(p, h) for _, h in records)
def loglik_mixture(pa, pb, w):
"""The likelihood SUMS over the hidden variable, one sum per experiment."""
total = 0.0
for _, h in records:
inner = w * math.exp(loglik_one(pa, h)) + (1 - w) * math.exp(loglik_one(pb, h))
total += math.log(inner)
return total
print(" one coin at p = %.4f log likelihood %.4f"
% (pooled, loglik_single(pooled)))
print(" the true mixture %.2f / %.2f log likelihood %.4f"
% (P_A, P_B, loglik_mixture(P_A, P_B, MIX)))
print(" the mixture explains the data far better, and the single coin cannot")
print(" be rescued by choosing p differently: %.4f is already its best value."
% pooled)
print()
# ---- 4. why there is no closed form ---------------------------------------
print("WHY NO FORMULA EXISTS. with the coin known, the log likelihood is a sum")
print("of logs, and each parameter appears in its own term, so differentiating")
print("gives one equation per parameter. with the coin hidden, each experiment")
print("contributes")
print(" log( w * P(heads | A) + (1-w) * P(heads | B) )")
print("a LOG OF A SUM. the parameters no longer separate, the derivative of one")
print("involves all of them, and there is no closed-form solution. in a general")
print("network the inner sum runs over every configuration of the hidden")
print("variables, so it is exponential in their number as well.")
print()
# ---- 5. the surface, searched --------------------------------------------
print("SO SEARCH IT. the log likelihood over a grid of (p for A, p for B), with")
print("the mixing weight held at %.1f:" % MIX)
print(" p_B \\ p_A " + "".join("%8.1f" % (i / 10) for i in range(1, 10)))
for j in range(1, 10):
pb = j / 10
row = " %8.1f " % pb
for i in range(1, 10):
row += "%8.1f" % loglik_mixture(i / 10, pb, MIX)
print(row)
best = None
for i in range(1, 100):
for j in range(1, 100):
v = loglik_mixture(i / 100, j / 100, MIX)
if best is None or v > best[0]:
best = (v, i / 100, j / 100)
print()
print(" searched on a grid of 1/100, the best is p_A = %.2f, p_B = %.2f at"
% (best[1], best[2]))
print(" log likelihood %.4f." % best[0])
print()
print(" READ THE SURFACE. it has TWO maxima, mirror images in the diagonal,")
print(" because calling the coins A and B the other way round describes the")
print(" same world: 'LABEL SWITCHING'. and along the diagonal, where the two")
print(" coins are equal, the surface is flat in the direction that would")
print(" separate them. a grid search of this kind costs 9801 evaluations for")
print(" two parameters and is hopeless for a real model, which is why the")
print(" next chapter derives an iteration instead.")Hidden Variables
TWELVE EXPERIMENTS. each one: pick one of two coins, flip it 10 times,
record the number of heads. the COIN USED is the hidden variable.
what was actually recorded:
heads out of 10 : 9 8 9 9 9 4 8 3 7 6 1 2
and what was NOT recorded, shown here only to prove the point:
coin used : A A A A A B A B A A B B
IF THE COIN WERE KNOWN the data would be COMPLETE and the answer is a
count, exactly as in the previous chapter:
coin A: 65 heads in 80 flips -> p = 0.8125 (true 0.80)
coin B: 10 heads in 40 flips -> p = 0.2500 (true 0.30)
and the mixing weight is just how often each coin was chosen:
P(coin A) = 8/12 = 0.6667 (true 0.50)
WITHOUT IT, THERE IS NOTHING TO COUNT. to count the heads of coin A you
must know which experiments used coin A, and that is the column you do
not have. the two unknowns are locked together:
to estimate the parameters you need the coin assignments,
to infer the coin assignments you need the parameters.
THE NAIVE REPAIR: ignore the hidden variable and pool every flip.
75 heads in 120 flips -> one coin with p = 0.6250
which is neither 0.80 nor 0.30. it is their average, and it describes
NO coin in the experiment. worse, it is a measurably poorer
explanation of the same data:
one coin at p = 0.6250 log likelihood -79.3876
the true mixture 0.80 / 0.30 log likelihood -69.2691
the mixture explains the data far better, and the single coin cannot
be rescued by choosing p differently: 0.6250 is already its best value.
WHY NO FORMULA EXISTS. with the coin known, the log likelihood is a sum
of logs, and each parameter appears in its own term, so differentiating
gives one equation per parameter. with the coin hidden, each experiment
contributes
log( w * P(heads | A) + (1-w) * P(heads | B) )
a LOG OF A SUM. the parameters no longer separate, the derivative of one
involves all of them, and there is no closed-form solution. in a general
network the inner sum runs over every configuration of the hidden
variables, so it is exponential in their number as well.
SO SEARCH IT. the log likelihood over a grid of (p for A, p for B), with
the mixing weight held at 0.5:
p_B \ p_A 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0.1 -177.4 -137.3 -112.4 -96.4 -85.6 -78.4 -74.1 -72.7 -75.9
0.2 -137.3 -130.7 -111.3 -95.7 -84.7 -77.0 -71.9 -69.6 -72.1
0.3 -112.4 -111.3 -106.3 -95.1 -84.8 -77.1 -71.9 -69.3 -70.8
0.4 -96.4 -95.7 -95.1 -91.7 -84.9 -78.2 -73.1 -70.3 -71.1
0.5 -85.6 -84.7 -84.8 -84.9 -83.2 -79.4 -75.3 -72.6 -72.8
0.6 -78.4 -77.0 -77.1 -78.2 -79.4 -79.5 -78.1 -76.2 -76.2
0.7 -74.1 -71.9 -71.9 -73.1 -75.3 -78.1 -80.9 -81.7 -82.0
0.8 -72.7 -69.6 -69.3 -70.3 -72.6 -76.2 -81.7 -89.2 -92.5
0.9 -75.9 -72.1 -70.8 -71.1 -72.8 -76.2 -82.0 -92.5 -111.5
searched on a grid of 1/100, the best is p_A = 0.28, p_B = 0.82 at
log likelihood -69.1228.
READ THE SURFACE. it has TWO maxima, mirror images in the diagonal,
because calling the coins A and B the other way round describes the
same world: 'LABEL SWITCHING'. and along the diagonal, where the two
coins are equal, the surface is flat in the direction that would
separate them. a grid search of this kind costs 9801 evaluations for
two parameters and is hopeless for a real model, which is why the
next chapter derives an iteration instead.Hidden Variables
With the column, it is counting
Shown once so the contrast is exact. Given the hidden column, Learning With Complete Data applies unchanged:
Hidden Variables
| Counted | Estimate | True | |
|---|---|---|---|
| coin A | 65 heads in 80 flips | 0.8125 | 0.80 |
| coin B | 10 heads in 40 flips | 0.2500 | 0.30 |
| mixing weight | 8 of 12 experiments | 0.6667 | 0.50 |
Hidden Variables
Note that even with the labels the estimates are not the true values, because twelve experiments are twelve experiments. That is ordinary sampling error and it is not the subject of this chapter.
Without it, three separate things break
A paper asking what goes wrong wants these three distinguished, not one vague answer.
1. There is nothing to count. To count the heads of coin A you must know which experiments used coin A. The estimate needs the assignments and the assignments need the estimate:
parameters <- need the coin assignments
assignments <- need the parameters
That circularity is the shape of the whole problem, and The EM Algorithm is the observation that a circle can be walked round.
2. The log likelihood no longer separates. With the coin known, each experiment contributes a sum of logs and each parameter sits in its own term, so differentiating gives one independent equation per parameter. With the coin hidden, each experiment contributes
log( w P(heads given A) + (1 - w) P(heads given B) )
a log of a sum. The parameters are tangled inside one logarithm, the derivative with respect to one of them involves all of them, and there is no closed-form solution. That is the technical heart of the chapter.
3. In a general model the sum itself is exponential. Here the inner sum has two terms because one coin is hidden. In a network with k hidden variables the sum runs over every configuration of them, so it has 2**k terms before any maximisation begins.
The naive repair, and how badly it does
The obvious move is to ignore the hidden variable and pool everything. Measured:
| Log likelihood of the same 12 experiments | |
|---|---|
One coin at its best value, p = 0.6250 | -79.3876 |
| The true mixture, 0.80 and 0.30 | -69.2691 |
Hidden Variables
The pooled estimate is 0.6250, which is neither coin and describes no coin in the experiment. And it is not merely inelegant: it explains the data ten log units worse, which is a factor of about twenty two thousand in probability. Nor can it be rescued by choosing p differently, since 0.6250 is already the best single-coin value; the failure is in the model, not the fit.
This is the general danger of ignoring a latent structure: averaging two populations produces a description of neither, and the result can look perfectly reasonable while being wrong about every individual.
The surface, and the two things it shows
Since no formula exists, the program searches. Read the printed grid.
It has two maxima. The best point on a grid of one hundredth is p_A = 0.28, p_B = 0.82 at -69.1228, and the mirror point 0.82, 0.28 scores identically. Calling the coins the other way round describes the same world, so the likelihood must be symmetric, and every mixture model has as many equivalent optima as there are ways to permute its components. The name is label switching, and it means the parameters of a mixture are only identifiable up to a relabelling.
And the diagonal is a trap. Where p_A = p_B the two coins are the same coin, and because the surface is symmetric about that diagonal, the slope in the direction that would separate them is exactly zero there. So a search started with the two coins equal has no reason to move them apart and never will. That single geometric fact is why the next chapter's algorithm must not be initialised symmetrically, and a paper asking why EM can fail completely is answered by it.
Note also the cost. Nine thousand eight hundred and one evaluations bought two parameters to two decimal places. A model with twenty parameters cannot be searched this way at all, which is the practical reason an iteration is needed and not merely an elegant one.
Distinctions
| Complete data | Hidden variable | |
|---|---|---|
| The log likelihood is | a sum of logs | a log of a sum |
| Parameters | separate | are tangled |
| Solution | closed form, a count | none |
| Cost per extra hidden variable | not applicable | doubles the inner sum |
| Pooling the data | Modelling the mixture | |
|---|---|---|
| Parameters | one, 0.6250 | two, plus a weight |
| Describes | no coin present | both |
| Log likelihood | -79.3876 | -69.2691 |
| Missing at random | Hidden by design | |
|---|---|---|
| Example | a student left a field blank | which coin was used |
| Sometimes observed | yes | never |
| Could be filled from other rows | sometimes | no |
What it does not mean
A hidden variable is not missing data. Missing data is sometimes observed and sometimes not; a hidden variable is never observed in any row.
Hidden Variables
A hidden variable is not a defect of the model. It can cut 27 parameters to 17 here, and the saving grows with the number of observed children.
It is not free, either. It asserts that the children are conditionally independent given it, which may be false.
Pooling is not a conservative approximation. It returns a value describing neither component and loses about ten log units here.
There is no closed-form maximum likelihood estimate. Not a hard one: none, because the parameters sit inside a logarithm of a sum.
The maximum is not unique. Every permutation of the components gives an equal maximum, which is label switching.
A search started with equal components does not converge slowly. It does not converge at all, because the surface has no slope in the separating direction along the diagonal.
Quick revision
- A hidden or latent variable is in the model and never in the data: a cluster label, a mixture component, an HMM state, an underlying cause.
- It shrinks the model: three causes and three symptoms need 27 numbers directly and 17 through one hidden node, and each further symptom costs 8 against 2. The price is an assumed conditional independence.
- Three things break: nothing to count (parameters need assignments, assignments need parameters); the log likelihood becomes a log of a sum, so no closed form exists; and in a general model the inner sum has
2**kterms forkhidden variables. - Measured: pooling gives one coin at
0.6250, which is neither of 0.80 and 0.30, at a log likelihood of -79.3876 against the mixture's -69.2691. - The searched surface has two maxima, mirror images in the diagonal: label switching, so mixture parameters are identifiable only up to relabelling. Best on a grid of 1/100:
0.28, 0.82at-69.1228. - On the diagonal, where the components are equal, the slope that would separate them is zero, so a symmetric start never moves. Never initialise EM symmetrically.
- The grid cost 9801 evaluations for two parameters, which is why an iteration is needed rather than a search.
Test yourself
1. Define a hidden variable and give three examples from this syllabus. One that the model contains but the data never records. Which cluster a point belongs to in k-means; which component of a mixture produced an observation; the underlying state of the system in a hidden Markov model.
2. Show with a count why a hidden variable can make a model smaller, and state the price. Three binary causes and three binary symptoms, each symptom depending on all three causes, need 3 numbers for the causes and 8 for each symptom's table, 27 in all. Inserting one hidden node between them gives 3 for the causes, 8 for the hidden node and 2 for each symptom, 17 in all, and each further symptom then costs 2 instead of 8. The price is the assumption that the symptoms are conditionally independent given the hidden node, which may be false.
Hidden Variables
3. Explain precisely why maximum likelihood has no closed form when a variable is hidden. With complete data each experiment contributes a sum of logarithms in which each parameter appears in its own term, so setting the derivatives to zero gives one independent equation per parameter. With a hidden variable each experiment contributes the logarithm of a sum over that variable's values, so all the parameters sit inside one logarithm, the derivative with respect to any one of them involves all the others, and the equations cannot be solved separately.
4. What is the circularity at the heart of the problem? Estimating the parameters requires knowing which component produced each observation, and inferring which component produced each observation requires the parameters.
5. A data set is a mixture of two coins at 0.80 and 0.30. What happens if the mixture is ignored and all flips pooled? The estimate is the overall proportion of heads, 0.6250 here, which describes neither coin. It is also a measurably worse explanation of the data: log likelihood -79.3876 against -69.2691 for the true mixture, and it cannot be improved by choosing a different single value, because 0.6250 is already the best one.
6. What is label switching, and what does it imply about a mixture's parameters? The likelihood is unchanged by permuting the names of the components, so every optimum has a mirror image with the labels exchanged. The parameters of a mixture are therefore identifiable only up to a relabelling, and two fits that look different may be the same model.
7. Why must an iterative search for mixture parameters not be started with the components equal? Because the likelihood surface is symmetric about the line where the components are equal, its slope in the direction that would separate them is exactly zero on that line. A search started there has no reason to move the components apart and will never separate them, so the failure is total rather than slow.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.