Contrastive Identification and Generation in the Limit

Technische Zusammenfassung: Kontrastive Identifikation und Generierung im Limes

Problemdefinition
Diese Arbeit leitet die lerntheoretische Untersuchung der kontrastiven Identifikation und Generierung im Limes ein. Die Autoren adressieren eine Lücke in klassischen Limes-Lernmodellen (Gold, 1967; Angluin, 1980) und aktuellen Generierungsmodellen (Kleinberg und Mullainathan, 2024), die sich auf Ströme positiver Beispiele (Text) oder vollständig gelabelter Daten (Informant) stützen. In vielen natürlichen Szenarien – wie A/B-Tests, vergleichenden Experimenten und Ähnlichkeits-Unähnlichkeits-Annotationen – liegen Daten als ungeordnete Paare $\{x, y\}$ vor, wobei der Lerner weiß, dass die Beispiele unter der Zielhypothese $h$ disagree (d. h. $h(x) \neq h(y)$), aber nicht weiß, welches Element positiv ($h(x)=1$) und welches negativ ($h(x)=0$) ist.

Der Lerner beobachtet einen Strom solcher kontrastiver Paare, der schließlich jedes positive Beispiel abdeckt (Abdeckung der positiven Seite), aber niemals explizit einen einzelnen Punkt labelt. Das Ziel ist es, die Bedingungen zu bestimmen, unter denen ein Lerner:

1. Die Zielhypothese $h$ aus einer bekannten Klasse $\mathcal{H}$ identifizieren kann (Stabilisierung auf die korrekte Hypothese).
2. Neue positive Beispiele von $h$ generieren kann (Ausgabe von Elementen in $\text{supp}(h)$, die noch nicht im Strom gesehen wurden).

Methodik und technischer Rahmen
Der zentrale technische Beitrag ist die Einführung des gemeinsamen Kreuzungsgraphen, bezeichnet als $\Gamma(h, g) = \Delta(h) \cap \Delta(g)$, wobei $\Delta(h)$ die Menge aller Paare ist, die den durch $h$ definierten Schnitt kreuzen. Dieser Graph kodiert die paarweise Ambiguität zwischen Hypothesen: Eine Kante existiert in $\Gamma(h, g)$, wenn das Paar eine gültige Beobachtung sowohl für $h$ als auch für $g$ darstellt.

Die Autoren wenden dieses geometrische Objekt auf drei Skalen an:

• Paare: Zur Analyse der Eliminierbarkeit zwischen zwei Hypothesen.
• Endliche Familien: Zur Analyse von Generierungsobstruktionen durch gemeinsame Präsentationen.
• Unendliche Defektmengen: Zur Analyse der Robustheit gegenüber adversarischer Korruption.

Die Arbeit nutzt eine graphentheoretische Übersetzung, bei der paarweise kontrastive Ambiguität auf eine Abdeckungsfrage reduziert wird: Eine Hypothese $g$ ist genau dann nicht von $h$ eliminierbar, wenn der Träger von $h$ durch die Knoten abgedeckt wird, die zu den Kanten in $\Gamma(h, g)$ inzident sind.

Hauptbeiträge und Ergebnisse

1. Exakte Charakterisierung der kontrastiven Identifikation (CtrId)
Die Arbeit liefert eine notwendige und hinreichende Bedingung dafür, dass eine Klasse $\mathcal{H}$ aus kontrastiven Daten identifizierbar ist. Eine Klasse befindet sich in CtrId genau dann, wenn:

• Sie text-identifizierbar ist (die Tell-Tale-Bedingung von Angluin erfüllt).
• Überlappende-Abdeckungs-Bedingung: Jedes Paar inkomparabler Hypothesen in $\mathcal{H}$ muss eine „überlappende Abdeckung" bilden. Dies bedeutet, dass ihre Träger sich schneiden müssen ($\text{supp}(h) \cap \text{supp}(g) \neq \emptyset$) und ihre Vereinigung den gesamten Beispielraum abdecken muss ($\text{supp}(h) \cup \text{supp}(g) = X$).
• Implikation: Kontrastive Daten führen zu einer neuen Obstruktion: Wenn zwei Hypothesen inkomparabel, disjunkt oder sich schneidend sind, aber den Raum nicht abdecken, können sie nicht unterschieden werden.

2. Kontrastive Generierung und die Abschlussdimension
Die Autoren führen die kontrastive Abschlussdimension ($C^\Delta$) ein, eine kombinatorische Dimension, die analog zur Abschlussdimension für positive Daten ist (Raman et al., 2025).

• Definition: $C^\Delta(\mathcal{H})$ ist das Supremum der Größe endlicher „hohler" Kantenmengen (Mengen von Paaren, die keine neuen positiven Elemente außerhalb der beobachteten Knoten erzwingen).
• Ergebnis: Eine Klasse erlaubt einen uniformen kontrastiven Generator genau dann, wenn $C^\Delta(\mathcal{H}) < \infty$. Die enge Stichprobenkomplexität beträgt $C^\Delta(\mathcal{H}) + 1$.
• Nicht-uniforme Generierung: Eine Klasse ist nicht-uniform generierbar, wenn sie in eine Kette von Unterklassen mit endlichen kontrastiven Abschlussdimensionen zerlegt werden kann.
• Obstruktionen: Die Arbeit identifiziert „Obstruktionen endlicher Familien", bei denen eine Menge von Hypothesen eine gemeinsame kontrastive Präsentation mit einem endlichen Schnitt der Träger zulässt, was die Generierung neuer Elemente verhindert.

3. Die Diamant-Hierarchie
Auf abzählbaren Klassen mit gleichmäßig unbeschränktem Träger (UUS) bilden die vier Lernfamilien eine strikte Diamant-Hierarchie anstelle einer linearen Kette:

• Strikte Enthaltenseine: $\text{CtrId} \subsetneq \text{CtrGen}$ und $\text{CtrId} \subsetneq \text{TxtId}$. Sowohl $\text{CtrGen}$ als auch $\text{TxtId}$ sind strikt in $\text{TxtGen}$ enthalten.
• Inkomparabilität: $\text{CtrGen}$ und $\text{TxtId}$ sind gegenseitig inkomparabel.
  • TxtId $\not\subseteq$ CtrGen: Klassen mit disjunkten Trägern sind text-identifizierbar, aber durch Obstruktionen endlicher Schnitte von der kontrastiven Generierung blockiert.
  • CtrGen $\not\subseteq$ TxtId: Klassen mit „gelochten Trägern" (Entfernung eines Elements aus einer unendlichen Menge) sind kontrastiv generierbar über eventual cores, fehlen aber endliche Tell-Tale-Mengen für die Text-Identifikation.

4. Umkehrung der Robustheit unter adversarischer Korruption
Die Arbeit beweist eine scharfe Umkehrung der Beziehung zwischen Identifikationsmodi unter endlicher adversarischer Korruption:

• Text-Fragilität: Ein einziges korruptes positives Beispiel kann eine Klasse im Text-Setting unidentifizierbar machen.
• Kontrastive Robustheit: Die Autoren definieren eine Defektzahl $\kappa(h \to g)$, die die minimale Anzahl erzwungener Verletzungen einer Hypothese $g$ in jeder gültigen Präsentation von $h$ zählt. Wenn $\kappa(h \to g) = \infty$, kann keine endliche Korruption die Verletzungen maskieren.
• Co-Singleton-Klasse: Die Klasse, bei der jede Hypothese alle Beispiele als positiv labelt, außer einem „Loch", ist unter jedem endlichen Korruptionsbudget im kontrastiven Setting identifizierbar (unter Verwendung eines „Abwesenheitszähl"-Algorithmus), aber unter selbst nur einer Korruption im Text-Setting unidentifizierbar.
• Ergebnis: Für jedes $k \ge 1$ sind $k$-korrupte kontrastive Identifikation und $k$-korrupte Text-Identifikation gegenseitig inkomparabel.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass der gemeinsame Kreuzungsgraph als vereinheitlichendes technisches Objekt dient, das paarweise Ambiguität, familienweite Generierungsobstruktionen und Korruptionsdefekte in einer einzigen Sprache kodiert. Die Autoren argumentieren, dass zwar das Fehlen einer Richtung in kontrastiven Daten in sauberen Settings eine Schwäche ist (im Vergleich zu Text werden neue Obstruktionen eingeführt), es sich jedoch unter adversarischer Korruption zu einer Stärke entwickelt, da korrupte Paare strukturell detektierbare „Nicht-Kanten" erzeugen, die die XOR-Bedingung verletzen.

Die Arbeit legt nahe, dass klassische Limes-Lernparadigmen fruchtbare Verfeinerungen zulassen, wenn Beobachtungen nicht-singleton sind, und enthüllt eine zweiseitige graphentheoretische Struktur: kostspielig im Vergleich zu gelabelten Daten, wenn sie sauber sind, aber schützend, wenn sie adversarisch gestört werden. Die Arbeit weist explizit darauf hin, dass ihre Konstruktionen für Identifikation und nicht-uniforme Generierung informationstheoretischer Natur sind (sie verlassen sich auf die Existenz von Tell-Tale-Familien oder Dimensionsketten) und die Frage nach effektiven, konstruktiven Verfahren für breitere Klassen als offenes Problem lässt.