Research proof index

In a saturated LTS, the transition and saturated transition relations are the same.

In totalize, the multistep transitions between non-sink states correspond exactly to the multistep transitions in the original LTS.

Under iid sampling from the realizable joint distribution induced by c ∈ C and a probability measure P on α, the target concept c lies in the version space almost surely.

The empirical 0-1 error equals the empirical miscount divided by the sample size.

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.