Chapter 19: Bernoulli labels and conditional-probability distributions, the Bayes rule, the k-NN rules (19.1), majority votes, the nearest-neighbor distance and the cube [0,1]^d
DefinitionUnderstandingML_NearestNeighborChapter 19 of Shalev-Shwartz and Ben-David. Labels. bernoulliLaw p is the law of a Bernoulli label with (the book's ); bernoulliErr p y' ; majority Z is the majority label of a finite family, iff strictly more than half are (the book's ); condLaw DX η is the distribution over with marginal and conditional probability , i.e. , then ; bayesRule η is the Bayes optimal rule . Rules (§19.1). In a metric space, nnDist S x is the distance to the nearest sample point; IsKNNRuleWith k φ h says is a -NN rule with respect to (19.1): there is a reordering of the sample indices by distance to , determined by the instances and alone, with for every sample of size . Ties in distance may be broken arbitrarily but not by the labels. A rule that chooses among equidistant neighbors by their labels is not the book's rule, and it defeats the chapter's bounds. For , , and a 1-NN rule predicting whenever some nearest neighbor has label , at ; IsKNNRule k h is the majority -NN rule and IsNN1Rule h the 1-NN rule . cube d is with the Euclidean distance.
import Definitions.Def_UnderstandingML_Linear
import Mathlib.MeasureTheory.Measure.GiryMonad
/-!
# Shalev-Shwartz and Ben-David, *Understanding Machine Learning*, Chapter 19: nearest neighbor
Shalev-Shwartz and Ben-David, *Understanding Machine Learning: From Theory to Algorithms*,
Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §19.1–§19.2.
**The `k`-NN rules (§19.1, p. 258–259).** The instance domain `X` carries a metric `ρ`. For a
training sample `S = (x₁, y₁), …, (x_m, y_m)` and a point `x`, let `π₁(x), …, π_m(x)` be a
reordering of `{1, …, m}` by distance to `x`, `ρ(x, x_{πᵢ(x)}) ≤ ρ(x, x_{πᵢ₊₁(x)})`. The `k`-NN
rule for binary classification returns the majority label among `{y_{πᵢ(x)} : i ≤ k}`; for
`k = 1` this is the 1-NN rule `h_S(x) = y_{π₁(x)}`; in general, for `φ : (X × Y)^k → Y`, the
`k`-NN rule with respect to `φ` is `h_S(x) = φ((x_{π₁(x)}, y_{π₁(x)}), …, (x_{π_k(x)}, y_{π_k(x)}))`
(19.1).
**The analysis (§19.2.1, p. 260).** `X = [0,1]^d` with the Euclidean distance, `Y = {0,1}`, the
0–1 loss. For a distribution `D` over `X × Y`, `D_X` is the marginal over `X` and
`η(x) = P[y = 1 | x]` the conditional probability; the Bayes optimal rule is
`h⋆(x) = 𝟙[η(x) > 1/2]`, and `η` is assumed `c`-Lipschitz.
**Conventions.** A distribution over `X × {0,1}` with marginal `D_X` and conditional probability
`η` is written `condLaw D_X η`: draw `x ∼ D_X`, then `y ∼ Bernoulli(η(x))`; every distribution
with a regression function `η` is of this form. A `k`-NN rule is any rule of the shape (19.1)
for *some* distance ordering of the sample (ties are broken arbitrarily), for `k ≤ m`; majority
votes predict `1` iff strictly more than half of the `k` labels are `1` (the book's
`𝟙[p' > 1/2]`, Lemma 19.7). Learning rules are deterministic, and the expectation statements
assume the rule is measurable in `(S, x)` (Remark 3.1). The nearest-neighbor distance
`‖x − x_{π₁(x)}‖` is the infimum of the distances to the sample points.
-/
open MeasureTheory
namespace UnderstandingML
/-! ### Labels drawn from a conditional probability -/
section Labels
/-- The Bernoulli law on `{0,1} = Bool` with `P[y = 1] = p` (`y ∼ p` in the book's shorthand,
p. 266). -/
noncomputable def bernoulliLaw (p : ℝ) : Measure Bool :=
ENNReal.ofReal p • Measure.dirac true + ENNReal.ofReal (1 - p) • Measure.dirac false
/-- `P_{y ∼ p}[y ≠ y']`: the probability that a Bernoulli(`p`) label differs from `y'`. -/
def bernoulliErr (p : ℝ) (y' : Bool) : ℝ := if y' then 1 - p else p
/-- The majority label of a finite family of labels: `1` iff strictly more than half are `1`. -/
noncomputable def majority {ι : Type*} [Fintype ι] (Z : ι → Bool) : Bool :=
decide ((Fintype.card ι : ℝ) / 2 < ∑ i, if Z i then (1 : ℝ) else 0)
variable {X : Type*} [MeasurableSpace X]
/-- The distribution `D` over `X × {0,1}` with marginal `D_X` and conditional probability
`η(x) = P[y = 1 | x]` (p. 260): sample `x ∼ D_X`, then `y ∼ Bernoulli(η(x))`. -/
noncomputable def condLaw (DX : Measure X) (η : X → ℝ) : Measure (X × Bool) :=
DX.bind (fun x ↦ (bernoulliLaw (η x)).map (fun y ↦ (x, y)))
/-- The **Bayes optimal rule** `h⋆(x) = 𝟙[η(x) > 1/2]` (p. 260). -/
noncomputable def bayesRule (η : X → ℝ) : X → Bool := fun x ↦ decide (1 / 2 < η x)
end Labels
/-! ### Nearest neighbor rules -/
section Rules
variable {X : Type*} [MetricSpace X]
/-- The distance `‖x − x_{π₁(x)}‖` from `x` to its nearest neighbor in the sample `S`. -/
noncomputable def nnDist {Y : Type*} {m : ℕ} (S : Fin m → X × Y) (x : X) : ℝ :=
⨅ i, dist x (S i).1
/-- `h` is a **`k`-NN rule with respect to `φ`** (19.1): there is a reordering `π(x)` of the
sample indices by distance to `x` that is determined by the instances `x₁, …, x_m` and `x` alone
(the book's `π₁(x), …, π_m(x)`), such that for every sample `S` of size `m ≥ k` and every `x`,
`h_S(x) = φ((x_{π₁(x)}, y_{π₁(x)}), …, (x_{π_k(x)}, y_{π_k(x)}))`. Ties in distance may be broken
arbitrarily, but not by looking at the labels: a rule that picks among equidistant neighbors by
label defeats Lemma 19.1 and Theorems 19.3 and 19.5 when `D_X` has atoms. -/
def IsKNNRuleWith {Y : Type*} (k : ℕ) (φ : (Fin k → X × Y) → Y)
(h : (m : ℕ) → (Fin m → X × Y) → X → Y) : Prop :=
∃ π : (m : ℕ) → (Fin m → X) → X → Fin m ≃ Fin m,
(∀ (m : ℕ) (xs : Fin m → X) (x : X) (i j : Fin m), i ≤ j →
dist x (xs (π m xs x i)) ≤ dist x (xs (π m xs x j))) ∧
∀ (m : ℕ) (hk : k ≤ m) (S : Fin m → X × Y) (x : X),
h m S x = φ (fun i ↦ S (π m (fun j ↦ (S j).1) x (Fin.castLE hk i)))
/-- `h` is a **`k`-NN rule** for binary classification (p. 259): the majority label among the
`k` nearest neighbors. -/
def IsKNNRule (k : ℕ) (h : Learner (X × Bool) (X → Bool)) : Prop :=
IsKNNRuleWith k (fun s ↦ majority (fun i ↦ (s i).2)) h
/-- `h` is a **1-NN rule** (p. 259): `h_S(x) = y_{π₁(x)}`, the label of a nearest neighbor. -/
def IsNN1Rule (h : Learner (X × Bool) (X → Bool)) : Prop :=
IsKNNRuleWith 1 (fun s ↦ (s 0).2) h
end Rules
/-- The unit cube `X = [0,1]^d ⊆ ℝ^d` with the Euclidean distance (p. 260). -/
abbrev cube (d : ℕ) := {x : Vec d // ∀ j, x j ∈ Set.Icc (0 : ℝ) 1}
end UnderstandingML