Research proof index

Under a realizable distribution P.map (x ↦ (x, c(x))), the general 0-1 error coincides with the binary hypothesisError P h c, where h and c are viewed as subsets of α via the characteristic function decide (· ∈ ·).

The deterministic PAC learner predicate is antitone in the concept class: a learner for a larger class C' is also a learner for any subclass C ⊆ C', since the agnostic benchmark optimalError _ C ≥ optimalError _ C' makes the error requirement easier.

A PAC learner with accuracy ε₁ is also a PAC learner with any weaker accuracy ε₂ ≥ ε₁: the bad event {error > opt + ε} only shrinks.

Shattering is anti-monotone in the shattered set: if C shatters W and V ⊆ W, then C shatters V.

The version-space meet law. The version space of an appended sample is the intersection of the version spaces of the two parts: constraints accumulate by intersection.

Posterior probabilities joint(a, b) / marginal(b) sum to 1 when b is in the support of the marginal.