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 set X and a finite class C of Boolean concepts on X, a partial labeled sample is inconsistent if no member of C agrees with every label. A specifying restriction is a subset of the sample's labels that leaves at most one member of C consistent. For each inconsistent sample, find the minimum size of such a restriction; sample exclusion dimension SXD(C) is the maximum of these minima.[1]

This account covers classes with at least one inconsistent partial sample. If none exists, the maximum above has no witnesses; a convention for that case is outside this bounded definition.

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.

Structural Signature

Sig role-phrases:

  • Finite domain: X supplies the coordinates that a sample can label.
  • Concept class: C is a specified finite set of Boolean functions on X.
  • Inconsistent partial sample: The outer range contains partial assignments that no concept in C extends.
  • Specifying restriction: A subset of the sample's labels leaves zero or one class member consistent.
  • Local minimum: For each eligible sample, minimize the number of labels in such a restriction.
  • Class maximum: Take the largest local minimum over the eligible samples, provided at least one exists.[1]

What It Is Not

A single sample requiring three labels shows SXD is at least three, but it does not alone show that no other eligible sample requires more. A specifying restriction need not eliminate every class member: one may remain. A class with no inconsistent partial sample is outside the stated scope rather than being assigned a value here.

Scope of Application

The examples use finite Boolean functions and partial labeled assignments. They are two mathematical concept classes, one source-reported and one independently derived. The definition does not by itself establish an algorithm's query bound, a mind-change guarantee, or results for automata and geometric boxes.

Clarity

State which labels are present, which class concepts agree with them, and whether a restriction is tested against the original class. Keep the minimum for a particular sample distinct from the maximum over samples.

Manages Complexity

The dimension compresses a family of potentially many inconsistent partial samples into one worst-case count. That count depends on the chosen class and on the order of the minimum and maximum; it does not retain the full pattern of which samples produce each minimum.

Abstract Reasoning

A restriction only needs to leave at most one candidate. When a sample is inconsistent, choosing labels that contradict some concepts may still leave one survivor. A worst-case assertion requires both a sample achieving the claimed minimum and an argument that no eligible sample exceeds it.

Knowledge Transfer

For another finite class, enumerate or otherwise characterize inconsistent samples, minimize specifying restrictions for each, and establish the maximum. A familiar concept-class label is not a substitute for those steps; a derived example should be identified as derived.

Examples

Canonical: four-concept addressing class

Angluin's indexed Figure 7 describes four concepts on coordinates (x1,x2,y1,y2,y3,y4): 001000, 010100, 100010 and 110001. The sample assigning zero to y1–y4 and leaving x1,x2 unassigned is inconsistent. Any two of the four zero labels leave two concepts, while any three leave one; its minimum specifying size is three.[1]

Mapped back: The six coordinates are X and the four vectors form C; the four zero labels are an inconsistent partial sample. The indexed source reports the three-label minimum. An independent enumeration of all 3⁶ partial assignments finds 506 inconsistent samples, with 457 requiring one label, 48 requiring two and one requiring three; therefore SXD(C)=3 for this class. The enumeration is a derivation, not an attribution to Angluin. The complete chapter was not inspected.

Applied/practice: worked singleton-indicator class

Take X={1,2,3} and C={100,010,001}. The sample 000 is inconsistent: no class concept assigns zero at every point. One zero leaves two concepts consistent; any two zeros leave one. Thus that sample has minimum specifying size two.

Mapped back: The three positions are X, the singleton indicators are C, and the zero labels form an inconsistent sample. An independently derived enumeration of all 3³ partial assignments finds eight inconsistent samples: seven have minimum one and 000 has minimum two. Hence SXD(C)=2. This is a derived mathematical example, not a second published case; XD(C)=2 for it, so it does not demonstrate strict separation of the two dimensions.

Structural Tensions

No independent structural tradeoff is established by these examples. A hard witness and an upper bound for all eligible samples are complementary parts of establishing an exact maximum; neither is a cost incurred by choosing the other. The distinction between those proof obligations remains useful when calculating the dimension.

Structural–Framed Character

The structure combines a class, inconsistent samples, a minimum restriction and a maximum over samples. It is mathematically framed: finite Boolean concepts and agreement tests are part of the named parameter, rather than incidental examples. Researchers choose the class and domain for their learning problem, and the count is evaluated by whether the specifying and extremal claims hold; the number is not a moral assessment. Its documented setting is mathematical research on exact concept learning: the addressing example appears in an indexed Angluin proceedings excerpt, while the singleton case is an independently checked derivation. Words such as “exclusion” or “worst case” can travel to other subjects, but applying this parameter imports its class, sample-consistency test and max–min rule; merely recognizing a generic worst case does not. Its character: a domain-framed class parameter whose structural relation is an extremum over local specifying minima.

Structural Core vs. Domain Accent

The portable skeleton is a worst case of local minimum witness sizes. Finite Boolean concepts, partial labels and the at-most-one agreement test are core to this named parameter. Those commitments keep the identity in computational learning theory; a cross-domain Prime for max–min witness size would require its own evidence and substantive test.

Teaching Dimension asks about identifying an inside-class target, while Witness Set distinguishes a declared target from rivals. Concept Class supplies the carrier and Sample Complexity concerns observations under a learning model; none alone states the SXD max–min. No typed parent is asserted here.

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

Not to Be Confused With

The related exclusion dimension XD ranges over full concepts outside C. Such concepts produce eligible inconsistent full samples, so XD(C)≤SXD(C) under the corresponding finite definitions; the outer ranges differ and equality is not a definition. The source's empty-witness convention, query theorems and the frozen automata and geometric examples are outside this account.[1]

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 ↩c ↩d