Contrastive Identification and Generation in the Limit

Technische Samenvatting: Contrastieve Identificatie en Generatie in de Limiet

Probleemdefinitie
Dit artikel initieert het leertheoretische onderzoek naar contrastieve identificatie en generatie in de limiet. De auteurs adresseren een lacune in klassieke limietleermodellen (Gold, 1967; Angluin, 1980) en recente generatiemodellen (Kleinberg en Mullainathan, 2024), die vertrouwen op stromen van positieve voorbeelden (tekst) of volledig gelabelde data (informant). In veel natuurlijke situaties—zoals A/B-tests, vergelijkende experimenten en gelijkenis-verschil-annotaties—komt data aan als ongesorteerde paren $\{x, y\}$ waarbij de leraar weet dat de voorbeelden het niet eens zijn onder de doelhypothese $h$ (d.w.z. $h(x) \neq h(y)$), maar niet weet welk element positief is ($h(x)=1$) en welk negatief ($h(x)=0$).

De leraar observeert een stroom van dergelijke contrastieve paren die uiteindelijk elk positief voorbeeld dekt (dekking aan de positieve kant), maar nooit expliciet een enkel punt labelt. Het doel is om de voorwaarden te bepalen waaronder een leraar kan:

1. De doelhypothese $h$ identificeren uit een bekende klasse $\mathcal{H}$ (stabiliserend op de juiste hypothese).
2. Genereren van nieuwe positieve voorbeelden van $h$ (het uitvoeren van elementen in $\text{supp}(h)$ die nog niet in de stroom zijn gezien).

Methodologie en Technisch Kader
De kern technische bijdrage is de introductie van de gemeenschappelijke kruisingsgraaf, aangeduid als $\Gamma(h, g) = \Delta(h) \cap \Delta(g)$, waarbij $\Delta(h)$ de verzameling is van alle paren die de door $h$ gedefinieerde snede kruisen. Deze graaf codeert de paarwijze ambiguïteit tussen hypothesen: een rand bestaat in $\Gamma(h, g)$ als het paar een geldige observatie is voor zowel $h$ als $g$.

De auteurs passen dit geometrische object toe op drie schalen:

• Paren: Om eliminatie tussen twee hypothesen te analyseren.
• Finiete Families: Om generatie-obstakels te analyseren via gedeelde presentaties.
• Oneindige Defectverzamelingen: Om robuustheid tegen adversariale corruptie te analyseren.

Het artikel maakt gebruik van een grafentheoretische vertaling waarbij paarwijze contrastieve ambiguïteit reduceert tot een dekkingsvraag: een hypothese $g$ is niet elimineerbaar uit $h dan en slechts dan als de ondersteuning van $h$ wordt gedekt door de hoekpunten die incident zijn aan randen in $\Gamma(h, g)$.

Belangrijkste Bijdragen en Resultaten

1. Exacte Karakterisering van Contrastieve Identificatie (CtrId)
Het artikel biedt een noodzakelijke en voldoende voorwaarde voor een klasse $\mathcal{H}$ om identificeerbaar te zijn vanuit contrastieve data. Een klasse zit in CtrId dan en slechts dan als:

• Het tekst-identificeerbaar is (voldoet aan Angluins 'tell-tale' voorwaarde).
• Overlappende Dekkingsvoorwaarde: Elk paar van niet-vergelijkbare hypothesen in $\mathcal{H}$ moet een "overlappende dekking" vormen. Dit betekent dat hun ondersteuningen moeten snijden ($\text{supp}(h) \cap \text{supp}(g) \neq \emptyset$) en hun vereniging het volledige voorbeeldruimte moet dekken ($\text{supp}(h) \cup \text{supp}(g) = X$).
• Implicatie: Contrastieve data introduceert een nieuw obstakel: als twee hypothesen niet-vergelijkbaar, disjunct, of snijdend zijn maar de ruimte niet dekken, kunnen ze niet worden onderscheiden.

2. Contrastieve Generatie en de Sluitingsdimensie
De auteurs introduceren de contrastieve sluitingsdimensie ($C^\Delta$), een combinatorische dimensie analoog aan de sluitingsdimensie voor positieve data (Raman et al., 2025).

• Definitie: $C^\Delta(\mathcal{H})$ is het supremum van de grootte van finiete "holle" randverzamelingen (verzamelingen van paren die geen nieuwe positieve elementen buiten de waargenomen hoekpunten afdwingen).
• Resultaat: Een klasse staat een uniforme contrastieve generator toe dan en slechts dan als $C^\Delta(\mathcal{H}) < \infty$. De strakke steekproefcomplexiteit is $C^\Delta(\mathcal{H}) + 1$.
• Niet-uniforme Generatie: Een klasse is niet-uniform genereerbaar als deze kan worden ontbonden in een keten van subklassen met finiete contrastieve sluitingsdimensies.
• Obstakels: Het artikel identificeert "finiete-familie-obstakels" waarbij een verzameling hypothesen een gedeelde contrastieve presentatie toelaat met een eindige doorsnede van ondersteuningen, wat de generatie van nieuwe elementen verhindert.

3. De Diamanthiërarchie
Op telbare klassen met uniform onbegrensde ondersteuning (UUS) vormen de vier leerfamilies een strikte diamanthiërarchie in plaats van een lineaire keten:

• Strikte Bevattingen: $\text{CtrId} \subsetneq \text{CtrGen}$ en $\text{CtrId} \subsetneq \text{TxtId}$. Zowel $\text{CtrGen}$ als $\text{TxtId}$ zijn strikt bevat in $\text{TxtGen}$.
• Niet-vergelijkbaarheid: $\text{CtrGen}$ en $\text{TxtId}$ zijn onderling niet-vergelijkbaar.
  • TxtId $\not\subseteq$ CtrGen: Klassen met disjuncte ondersteuningen zijn tekst-identificeerbaar maar geblokkeerd voor contrastieve generatie door eindige-snij-obstakels.
  • CtrGen $\not\subseteq$ TxtId: Klassen met "geperforeerde ondersteuningen" (het verwijderen van één element uit een oneindige verzameling) zijn contrastief genereerbaar via uiteindelijke kernen maar missen finiete 'tell-tale' verzamelingen voor tekst-identificatie.

4. Omkering van Robuustheid onder Adversariale Corruptie
Het artikel bewijst een scherpe omkering in de relatie tussen identificatiemodi onder finiete adversariale corruptie:

• Tekst-Fragiliteit: Een enkel gecorrumpeerd positief voorbeeld kan een klasse onidentificeerbaar maken in de tekstsetting.
• Contrastieve Robuustheid: De auteurs definiëren een defectgetal $\kappa(h \to g)$, dat het minimum aantal gedwongen schendingen van een hypothese $g$ telt in elke geldige presentatie van $h$. Als $\kappa(h \to g) = \infty$, kan geen enkele finiete corruptie de schendingen maskeren.
• Co-singleton Klasse: De klasse waarbij elke hypothese alle voorbeelden positief labelt behalve één "gat", is identificeerbaar onder elk finiet corruptiebudget in de contrastieve setting (met behulp van een "afwezigheids-tel" algoritme) maar is onidentificeerbaar onder zelfs één corruptie in de tekstsetting.
• Resultaat: Voor elke $k \ge 1$ zijn $k$-gecorrumpeerde contrastieve identificatie en $k$-gecorrumpeerde tekst-identificatie onderling niet-vergelijkbaar.

Betekenis en Beweringen
Het artikel beweert dat de gemeenschappelijke kruisingsgraaf dient als een verenigend technisch object dat paarwijze ambiguïteit, generatie-obstakels op familienniveau en corruptiedefecten codeert in één taal. De auteurs betogen dat terwijl het gebrek aan richting in contrastieve data een zwakte is in schone settings (wat nieuwe obstakels introduceert in vergelijking met tekst), het een kracht wordt onder adversariale corruptie, aangezien gecorrumpeerde paren structureel detecteerbare "niet-randen" creëren die de XOR-beperking schenden.

Het werk suggereert dat klassieke limietleerparadigma's vruchtbare verfijningen toelaten wanneer observaties niet-singleton zijn, wat een tweezijdige grafentheoretische structuur blootlegt: kostbaar ten opzichte van gelabelde data wanneer schoon, maar beschermend wanneer adversariaal verstoord. Het artikel merkt expliciet op dat zijn constructies voor identificatie en niet-uniforme generatie informatietheoretisch zijn (afhankelijk van het bestaan van 'tell-tale' families of dimensieketens) en laat de vraag naar effectieve, constructieve procedures voor bredere klassen als een open probleem.