Theorem 22.4 (Kleinberg): no clustering function on a domain with at least two points satisfies Scale Invariance, Richness and Consistency
ProvedUnderstandingML.kleinberg_impossibilityclusteringimpossibilitykleinberg-axioms
Theorem 22.4. There exists no function, , that satisfies all the three properties: Scale Invariance, Richness, and Consistency.
Formally: for a fixed finite domain with at least two points, no function from dissimilarities over to partitions of satisfies the three axioms. (The book's proof picks a domain with at least three points and uses only two of its partitions; dissimilarities are positive on distinct points, as in Kleinberg (2003), which the scaling step of the proof needs.)
Preamble
import Definitions.Def_UnderstandingML_Clustering open MeasureTheory
Formal statement
namespace UnderstandingML
/-- **Theorem 22.4 (Kleinberg 2003)** (p. 319). There exists no function `F` that satisfies all
the three properties: Scale Invariance, Richness, and Consistency.
Stated for clustering functions on a fixed finite domain with at least two points (the
proof picks a domain with at least three points and uses two of its partitions). -/
theorem kleinberg_impossibility {X : Type*} [Fintype X] (hX : 2 ≤ Fintype.card X) :
¬ ∃ F : Dissimilarity X → Setoid X, ScaleInvariant F ∧ Rich F ∧ Consistent F := by sorry
end UnderstandingML
Source
Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §22.5 p. 319, Theorem 22.4 with its proof (Kleinberg 2003)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.