What question did this study set out to answer?

The aim is to analyze zero-error class identification using resources such as tag rate, identification cost, and distortion.

February 24, 2026Open Access

Identification Capacity and Rate-Query Tradeoffs in Classification Systems

Key Points

The aim is to analyze zero-error class identification using resources such as tag rate, identification cost, and distortion.
Proved information barrier regarding zero-error class identification under constrained observations.
Analyzed collision multiplicity for attribute-profile maps and derived bounds for tag rates.
Defined minimal sufficient query sets and linked them to zero-error source coding via graph entropy.
Established that L must be at least log₂(collision multiplicity) for zero-error identification schemes.
Identified unique Pareto-optimal points in maximal-barrier domains as (⌈log₂(k)⌉, O(1), 0).
Demonstrated that without tags, the query cost to achieve zero-error identification scales with the distinguishing dimension.

Abstract

We study zero-error class identification under constrained observations with three resources: tag rate L (bits per entity), identification cost W (attribute queries), and distortion D (misidentification probability). We prove an information barrier: if the attribute-profile map π is not injective on classes, then attribute-only observation cannot identify class identity with zero error. Let A_π = maxᵤ |c: π (c) =u| be collision multiplicity. Any D=0 scheme must satisfy L ≥ log₂ (A_π), and this bound is tight. In maximal-barrier domains (A_π = k), the nominal point (L, W, D) = (⌈log₂ (k) ⌉, O (1), 0) is the unique Pareto-optimal zero-error point. Without tags (L = 0), zero-error identification requires W = Ω (d) queries, where d is the distinguishing dimension (worst case d = n, so W = Ω (n) ). Minimal sufficient query sets form the bases of a matroid, making d well-defined and linking the model to zero-error source coding via graph entropy. We also state fixed-axis incompleteness: a fixed observation axis is complete only for axis-measurable properties. Results instantiate to databases, biology, typed software systems, and model registries, and are machine-checked in Lean 4. 14 pages; 296 machine-verified theorem/lemma statements; 6, 707 lines of Lean 4 across 14 files; 0 sorry.

AI से पूछें

Bookmark

View Full Paper