Conditional Probability

When One Label Is Not Enough

A traditional learning model may assume that the features of every input determine one correct label with complete certainty. Under that assumption, learning means finding a hypothesis that agrees perfectly with a true labeling function. This is called the realizability assumption. The difficulty is that measured features may not completely determine labels in many practical problems. The same feature description can therefore be associated with different labels in the data-labels model.

From Inputs to Labeled Examples

Agnostic PAC learning relaxes realizability. Instead of requiring one perfectly correct labeling function, it uses a joint data-labels distribution over X × Y. Here, X represents domain points and Y represents labels. A draw from this joint distribution produces a combination: one domain point together with one label. The distribution describes how these combinations are generated together.

Marginal Versus Conditional

The joint data-labels distribution contains two connected views. The marginal distribution over domain points describes which feature descriptions are likely to appear, without focusing on one particular label. The conditional probability over labels answers a different question: once a particular domain point or feature description is given, how likely is each label? The first view concerns the distribution of inputs; the second concerns the labels associated with a selected input.

Repeated Inputs with Different Labels

The joint distribution does not require every domain point to have only one possible label. A particular feature description can be paired with different labels. This is how the data-labels model represents situations in which measured features do not completely determine the label. The conditional probability over labels records the likelihood of the possible labels after that feature description is given.

Common Reasoning Errors

• Assuming that every domain point must have one certain label.

  The agnostic data-labels model permits different labels for the same domain point when measured features do not completely determine labels.

  Fix: Use the conditional probability over labels to describe how likely each label is for the selected domain point.

• Confusing the marginal distribution with the conditional probability.

  The marginal distribution concerns which domain points or feature descriptions are likely to appear, while the conditional probability concerns labels after a particular domain point is given.

  Fix: First identify whether the question is about the inputs that occur or about labels associated with one selected input.

• Treating realizability as a requirement of every learning problem.

  Many practical problems do not satisfy realizability because measured features may not completely determine labels.

  Fix: Recognize that agnostic PAC learning relaxes this requirement by modeling a joint distribution over domain points and labels.

Check Your Understanding

Key Takeaways

1. Realizability requires perfect agreement between some hypothesis in H and a target labeling function.
2. Measured features may not completely determine labels, so many practical problems do not satisfy realizability.
3. Agnostic PAC learning uses a joint data-labels distribution over domain points and labels.
4. The marginal distribution describes which domain points are likely to appear.
5. The conditional probability describes how likely each label is after a particular domain point is given, and it permits different labels for the same domain point.