Learning with Complete Data

Reading the two tables

Eight numbers describe this network, against 15 for the full joint distribution over the same four variables. Bayesian Networks argued that; here it is the count of things that have to be learned.

The estimates converge, but not at the same speed, and the second table says why. Set the two side by side for the four alarm rows:

The last row cannot be estimated from two hundred thousand nights. It needs a burglary and an earthquake on the same night, and the true probability of that is 0.001 * 0.002 = 0.000002, about one night in five hundred thousand. More data does not help a network evenly. It helps each table row in proportion to how often that row's parent values occur, so the rarest rows stay unlearned however large the sample.

Two consequences worth stating in an answer.

A node with many parents is expensive. Its table has 2 to the power of the number of parents rows, and each row needs its own observations, so the data required grows exponentially in the number of parents. That is a practical argument for the sparse graphs Bayesian Networks prized, quite separate from the argument about storage.

Small denominators give wild estimates. At 2,000 rows, two of the alarm rows had two observations each and both returned 1.0000 against true values of 0.940 and 0.290. The estimate 2/2 is the honest maximum likelihood answer and it is useless, which is the next section.

The learned parameters beat the truth

On forty thousand rows:

The learned parameters explain the sample better than the parameters that generated it. That is not an error, and it is not a sign of a good fit either. Maximum likelihood returns whatever best explains this sample, and the sample is not the world: its counts are a little off the true proportions, and the estimate follows them exactly.

This is Overfitting and Underfitting seen inside a network, and it gives a clean general statement: the training likelihood of a maximum likelihood fit is always at least the training likelihood of the truth, so a high likelihood on the training data is never evidence that the parameters are right.

The zero row, and the repair

Plain counting on a row with no observations is 0/0, undefined. A program that quietly returns 0 instead makes a much worse claim: that the alarm cannot sound during a burglary in an earthquake. Then any night on which it does has probability zero under the whole model, and the network is unusable, exactly as in Maximum Likelihood Estimation.

Laplace smoothing repairs it, by adding one imagined observation of each value to every row:

Read the first line: with nothing observed the smoothed estimate is 0.5000, the honest statement that nothing is known. And read the last: with four observations the smoothing still moves the estimate a long way, which is the right behaviour on four observations and would be the wrong behaviour on four thousand, where it barely moves it at all.

So the practical algorithm is counting plus a smoothing rule, and on a network with rare parent combinations the rule is not optional.

What this chapter does not do

Two things are deliberately outside it, and a paper may ask a student to say so.

The structure was given. Which node is a parent of which was fixed in advance, by someone who understood the domain. Learning the structure from data is a much harder problem: the number of possible graphs grows faster than exponentially in the number of nodes, and adding an edge can never lower the training likelihood, so the search needs a penalty for complexity. It is a real subject and it is not this one.

Every value was observed. That is the assumption that made the sum separate. Hidden Variables removes it.

Distinctions

What it does not mean

Counting is not a heuristic here. It is the exact maximum likelihood estimate, because the log likelihood separates.

More data does not fix every row. It fixes each row in proportion to how often that row's parent values occur.

A high training likelihood is not evidence of correct parameters. The learned ones beat the truth by 6.0088 on the sample that produced them.

An estimate of 1.0000 from two observations is not a certainty. It is maximum likelihood with a denominator of two.

A count of zero is not a probability of zero. It is the absence of evidence, and treating it as zero destroys the model.

Learning the parameters is not learning the network. The graph was given.

Quick revision

• Complete data: every variable observed in every row. Then ln L separates into one term per node and per parent configuration, so each table row is estimated on its own.
• The estimate: P(node = true given a parent row) = (rows with both) / (rows with those parent values). One counting pass, no search.
• Ancestral sampling draws data from a known network: parents before children, one pass per row.
• Measured: 8 parameters against 15 for the full joint. Estimates converge, but each row at its own rate, set by its denominator.
• P(Alarm given burglary and earthquake) had 0 observations in 200,000 rows, since its parent values co-occur with probability 0.000002. Not estimable.
• A node with k parents has 2k rows, so the data needed grows exponentially in the number of parents**. Another reason for sparse graphs.
• The learned parameters scored -9501.9179 against the truth's -9507.9267 on the same 40,000 rows: the MLE beats the truth on its own sample, so training likelihood is never evidence of correctness.
• Laplace smoothing: add one of each value. 0 of 0 becomes 0.5000, 1 of 1 becomes 0.6667, and the effect fades as real counts grow.
• Out of scope here: structure learning, which searches a super-exponential space and needs a complexity penalty, and missing values, which break the separation.

Test yourself

1. Why does learning a Bayesian network from complete data reduce to counting? The likelihood is a product over rows and nodes of each node's probability given its parents, so the log likelihood is a sum in which every term mentions only one node and its parents. The sum therefore separates into independent pieces, one per node and per combination of parent values, and each piece is the coin problem whose maximum likelihood answer is the observed proportion.

2. Write the estimate for one table row. The number of rows in which the node is true and its parents have the given values, divided by the number of rows in which its parents have those values.

3. What is ancestral sampling? Drawing a row from a known network by taking the nodes in an order that puts every parent before its children and sampling each node from the table row its already-drawn parents select. One pass gives one complete sample.

4. In the measurement, one parameter could not be estimated from 200,000 rows. Which, and why? The probability of the alarm given both a burglary and an earthquake. The two parents are independent with probabilities 0.001 and 0.002, so they co-occur about once in five hundred thousand rows, and 200,000 rows contained none. Data helps each table row only in proportion to how often that row's parent values occur.

5. Why is a node with many parents expensive to learn? Its table has two to the power of the number of parents rows, and each row needs its own observations to be estimated, so the amount of data required grows exponentially in the number of parents. This is an argument for sparse graphs independent of the argument about storage.

6. The learned parameters gave a higher log likelihood on the training data than the true parameters. Explain, and give the consequence. Maximum likelihood returns the parameters that best explain the particular sample, and the sample's counts differ slightly from the true proportions, so the estimate follows the sample rather than the truth. It follows that a high training likelihood can never be evidence that the parameters are correct, since the fitted parameters beat the truth on that data by construction.

7. A table row has no observations. Give the plain estimate, what is wrong with it, and the repair. Plain counting gives zero over zero, which is undefined, and a program that returns 0 instead asserts the event is impossible, so any row exhibiting it has likelihood zero and the whole model becomes unusable. Laplace smoothing adds one imagined observation of each value, which turns nothing observed into 0.5, the honest statement that nothing is known, and its influence fades as real observations accumulate.