Skip to content

Sample exclusion dimension

Sample exclusion dimension measures the largest minimum specifying restriction among inconsistent partial samples of a finite Boolean concept class.

Version
v1 · 2026-10-31 · History
Domain-specific #
14573
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Exact Learning, Concept Classes → Computer Science & Software Engineering
Aliases
SXD

Core Idea

For a finite Boolean concept class C over finite X, consider a partial labeled sample inconsistent with every concept in C. A specifying restriction is a subset of its labels that leaves at most one C member consistent. Sample exclusion dimension SXD(C) takes the smallest such restriction for each inconsistent sample and then the largest of those minima.[1]

This account is restricted to classes with at least one inconsistent partial sample. It does not assign a value to an empty maximum.

How would you explain it like I'm…

The Hardest Clue Pile

Imagine a box of possible secret rules, and a pile of clues that no rule in the box fits all of. You want to keep only a few clues, just enough so that at most one rule still fits them. Sample exclusion dimension is how many clues you'd need to keep for the very hardest pile.

Worst-Case Clue Count

Imagine a guessing game with a fixed list of possible secret rules, each sorting a set of things into 'yes' and 'no.' Someone hands you labels for some of the things, and it turns out no rule on the list fits all of them. You then ask: what is the smallest handful of those labels that already leaves at most one rule that still fits? Do this for every such mismatched set of labels. The Sample exclusion dimension is the biggest of those smallest numbers, so it tells you the worst case.

Worst-Case Specifying Sample Size

In computational learning theory, a concept class C is a set of possible yes/no labelings of a finite set X. A partial labeled sample gives labels to some elements of X. It is inconsistent if no concept in C agrees with all of its labels. For such a sample, a specifying restriction is a subset of its labels that leaves at most one concept in C still agreeing. Find the smallest such subset for each inconsistent sample; the sample exclusion dimension SXD(C) is the largest of those smallest sizes. This definition assumes at least one inconsistent sample exists; otherwise a separate convention is needed.

 

Let X be a finite domain and C a finite class of Boolean concepts on X. A partial labeled sample assigns labels to a subset of X; it is inconsistent with C if no concept in C agrees with every label. Given an inconsistent sample, a specifying restriction is a sub-sample whose labels are consistent with at most one concept in C (that is, with zero or one). For each inconsistent sample, take the minimum cardinality of a specifying restriction; the sample exclusion dimension SXD(C) is the maximum of these minima over all inconsistent partial samples. It thus measures, in the worst case, how many labels are needed to narrow C down to at most one surviving concept starting from data that C cannot fit. The definition presupposes that C has at least one inconsistent partial sample; if none exists, the maximum is over an empty set and requires a separate convention not covered here.

Examples

For the four-concept addressing class in Angluin's indexed Figure 7, assigning zero to each of four output coordinates gives an inconsistent sample; three zeros are needed to leave at most one concept. Independent enumeration of all partial samples gives SXD 3.[1]

For a separately derived class C={100,010,001} on three points, 000 is inconsistent and two zeros leave one concept. Enumerating all partial samples gives SXD 2. This second example is a mathematical derivation, not an Angluin example.

Boundaries

Exclusion dimension XD uses total concepts outside C rather than all inconsistent partial samples; XD≤SXD under the finite definitions, but the metrics are not identical. “At most one” permits zero or one survivor. The complete Angluin chapter and the source's empty-witness convention remain library follow-ups. DFA, geometric-box and query-theorem claims require separate evidence.

Neighborhood in Abstraction Space

Sample exclusion dimension sits in a sparse region of the domain-specific corpus (75th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2835 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-31

References

[1] Dana Angluin, “Queries Revisited,” in Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence 2225 (2001), 12–31, DOI 10.1007/3-540-45583-3_3. Publisher abstract: https://link.springer.com/chapter/10.1007/3-540-45583-3_3; indexed proceedings §12.2 and Figure 7 were reviewed, while the complete chapter remains a library follow-up. registry ↩a ↩b