ENCP: Episode-Normalized Conformal Prediction for Vision-and-Language Navigation

Technisches Resümee: Episoden-normalisierte konforme Prädiktion (ENCP) für Vision-and-Language Navigation

1. Problemstellung

Vision-and-Language Navigation (VLN) ermöglicht es verkörperten Agenten, physische Umgebungen mithilfe natürlicher Sprachinstruktionen zu navigieren. Eine kritische Herausforderung beim sicheren Einsatz dieser Agenten ist die Unsicherheitsschätzung. Die sequentielle Navigation ist anfällig für kumulative Fehler; eine einzige falsche Aktion verändert den Zustand des Agenten und die nachfolgenden Beobachtungen, was potenziell zum Scheitern der Aufgabe oder zu physischen Kollisionen führt.

Obwohl moderne VLN-Policies hohe Erfolgsraten erzielen, sind Standard-Konfidenzmetriken (z. B. Softmax-Wahrscheinlichkeiten) oft unkalibriert und übermäßig selbstbewusst (overconfident), insbesondere wenn die Einsatzumgebungen von den Trainingsdaten abweichen. Bestehende Selbstüberwachungsmechanismen stützen sich auf empirische Heuristiken statt auf formale Garantien.

Konforme Prädiktion (Conformal Prediction, CP) bietet einen statistischen Rahmen zur Generierung von Prädiktionsmengen mit garantierter Abdeckung (d. h. die Menge enthält die wahre Aktion mit einer Wahrscheinlichkeit von $1-\alpha$). Die Standard-CP setzt jedoch austauschbare (exchangeable) Datenpunkte voraus. In der VLN versagt diese Annahme, weil:

1. Schrittabhängigkeit: Aktionen innerhalb einer einzelnen Episode sind aufgrund der gemeinsamen Historie und des kausalen Einflusses auf zukünftige Beobachtungen statistisch abhängig.
2. Variable Länge: Episoden haben unterschiedliche Längen.
3. Versagen der schrittweisen Pool-Kalibrierung: Die Anwendung der Standard-CP auf einzelne Schritte (gepoolt über Episoden hinweg) führt nicht dazu, dass eine Garantie besteht, dass die korrekte Aktion bei jedem Schritt einer Route enthalten ist. Dies führt häufig zu einer Unterdeckung, was bedeutet, dass die tatsächliche Fehlerrate das Zielrisiko $\alpha$ überschreitet.

2. Methodik: Episoden-normalisierte konforme Prädiktion (ENCP)

Die Autoren schlagen ENCP vor, einen Post-Training-Framework, der die zugrunde liegende Navigations-Policy unverändert lässt. ENCP adressiert die Probleme der Abhängigkeit und der variablen Länge, indem es die Kalibrierungseinheit von einzelnen Schritten auf vollständige Episoden verschiebt.

Kernmechanismen:

1. Episoden-basierte Kalibrierung: Anstatt zu kalibrieren, indem man einen Pool von Einzelschritten verwendet, aggregiert ENCP die Nichtkonformitäts-Scores aller Schritte innerhalb einer einzigen Episode zu einem einzigen Skalarwert. Konkret wird der maximale normalisierte Nichtkonformitäts-Score über die gesamte Episode berechnet. Dieser einzelne Wert repräsentiert die „Worst-Case“-Abweichung für diese Trajektorie.
2. Konfidenz-angepasste Score-Normalisierung: Um die variierende Policy-Konfidenz über die Schritte hinweg zu handhaben, skaliert ENCP den Basis-Nichtkonformitäts-Score ($s_{base}$) durch die residuelle Konfidenz der Policy um.
   • Parameterfreie Variante: Verwendet ein festes Gewicht $w(x_t) = 1 - p_{max}(x_t)$, wobei $p_{max}$ die höchste von der Policy zugewiesene Wahrscheinlichkeit ist. Der normalisierte Score lautet:
     $$s_{norm}(x_t, a) = \frac{s_{base}(x_t, a)}{1 + (1 - p_{max}(x_t))} = \frac{s_{base}(x_t, a)}{2 - p_{max}(x_t)}$$
   • Lernbasierte Variante: Verwendet ein neuronales Netz, um Gewichte basierend auf Merkmalen wie Entropie, Wahrscheinlichkeitslücken und dem Schritt-Index vorherzusagen, trainiert darauf, Schritte zu identifizieren, in denen die Policy zwar konfident, aber dennoch falsch liegt.
3. Generierung des Prädiktionssets:
   • Ein konformer Schwellenwert $\hat{q}(\alpha)$ wird aus der Verteilung der episodenbasierten Maximalwerte auf einem Kalibrierungsdatensatz berechnet.
   • Zur Testzeit enthält das Prädiktionsset $C_\alpha(x_t)$ alle Aktionen $a$, für die gilt: $s_{norm}(x_t, a) \le \hat{q}(\alpha)$.
   • Act-or-Ask Regel: Wenn die Größe des Prädiktionssets $|C_\alpha(x_t)|$ ein benutzerdefiniertes Budget $\tau$ überschreitet, bittet der Agent um menschliche Unterstützung (oder überträgt die Aufgabe an einen Simulator). Andernfalls fährt er autonom fort.

Theoretische Garantie:
Unter der Annahme, dass Kalibrierungs- und Testepisoden austauschbar sind (z. B. aus derselben Verteilung gezogen wurden), garantiert ENCP, dass die wahre Aktion mit einer Wahrscheinlichkeit von mindestens $1-\alpha$ bei jedem Schritt einer Testepisode in dem Prädiktionsset enthalten ist. Dies bietet eine simultane Trajektorien-Abdeckung, eine stärkere Garantie als die schrittweise Abdeckung.

3. Wichtigste Beiträge

1. Identifikation des Versagens der Standard-CP: Die Arbeit zeigt auf, dass die schrittweise gepoolte Conformal Prediction aufgrund der intra-episodischen Abhängigkeiten in der VLN versagt und häufig zu einer schweren Unterdeckung führt.
2. Entwicklung von ENCP: Die Autoren führen eine episodische Kalibrierungsmethode ein, die Scores durch die Policy-Konfidenz skaliert und sie mittels eines Maximum-Operators aggregiert. Diese Konstruktion stellt eine simultane Abdeckung über die gesamte Trajektorie sicher.
3. Empirische Validierung: Die Methode wird auf vier VLN-Policies (DUET, HAMT, R-prev, R-osc) über zwei Datensätze (R2R und REVERIE) evaluiert. Die Studie umfasst:
   • Verifizierung der Schritt-Abdeckungsziele auf Seen-to-Unseen-Splits.
   • Vergleich zwischen parameterfreien und lernbasierten Gewichtungsschemata.
   • Ein simuliertes Experiment zur Hilfesuche, das demonstriert, wie die Größe des Prädiktionssets eine menschliche Intervention auslösen kann, um die Erfolgsraten zu verbessern.

4. Ergebnisse

• Abdeckungsziele: Über alle getesteten Policies und Nichtkonformitäts-Scores (THR, APS, RAPS) auf den R2R- und REVERIE-Val-Unseen-Splits hin erfüllte ENCP erfolgreich die empirischen Schritt-Abdeckungsziele (z. B. Erreichung von $\ge 90\%$ Abdeckung für $\alpha=0,10$) unter der Bedingung der Austauschbarkeit. Im Gegensatz dazu kam die Standard-Split-CP konsistent zu einer Unterdeckung.
• Verteilungsverschiebung (Distribution Shift): Die Arbeit stellt explizit fest, dass die Abdeckung im „Seen-to-Unseen“-Szenario sinkt (wo die Kalibrierung an gesehenen Gebäuden und der Test an ungesehenen Gebäuden erfolgt). In diesem Szenario wird die Austauschbarkeit der Episoden nicht vorausgesetzt, und die formale Abdeckungsgarantie gilt streng genommen nicht, obwohl ENCP die Standard-CP weiterhin übertrifft.
• Gewichtungs-Varianten: Das parameterfreie Gewichtungsschema (unter Verwendung von $1-p_{max}$) erreichte eine vergleichbare Abdeckung wie die lernbasierte Variante, resultierte jedoch in kleineren Prädiktionsmengen und erforderte kein zusätzliches Modell-Fitting.
• Nutzen der Hilfesuche: In einer Simulation, in der der Agent an ein Ground-Truth-„Oracle“ delegiert, wenn die Größe des Prädiktionssets einen Schwellenwert $\tau$ überschreitet, verbesserte sich die Erfolgsrate signifikant. Beispielsweise steigerte die Senkung des Schwellenwerts für die Häufigkeit von Anfragen bei der DUET-Modell die Erfolgsrate von 71,2 % (ohne Hilfe) auf 98,8 % (Abfrage bei jeder Nicht-Singleton-Menge), allerdings zu einer höheren „Ask-Rate“.

5. Bedeutung und Ansprüche

Das Paper behauptet, dass ENCP eine modellagnostische Methode zur Quantifizierung der Unsicherheit in der VLN bietet, die formale, endliche-Stichproben-Abdeckungsgarantien über abhängige, variabel lange Trajektorien liefert.

• Sicherheit und Zuverlässigkeit: Durch die Bereitstellung eines statistisch validen Prädiktionssets ermöglicht ENCP es Agenten, unzuverlässige Schritte zu identifizieren und vor der Kumulation von Fehlern um menschliche Hilfe zu bitten, was eine kritische Sicherheitslücke in der autonomen Navigation schließt.
• Praktische Implementierung: Die Größe des Prädiktionssets dient als praktisches Signal für eine Intervention. Die Autoren argumentieren, dass dies einen abstimmbaren Kompromiss zwischen Autonomie und Sicherheit ermöglicht und Agenten befähigt, „zu wissen, wann sie es nicht wissen“.
• Limitierungen: Die Autoren merken bescheiden an, dass die Closed-Loop-Evaluierung auf einem simulierten Oracle statt auf menschlichen Operatoren basiert. Zudem setzt die Methode einen endlichen Aktionsraum voraus, und die Abdeckungsgarantie ist marginal über die Episodenverteilung, was bedeutet, dass sie bei signifikanten Verteilungsverschiebungen (z. B. ungesehene Gebäude) ohne Rekalibrierung möglicherweise nicht perfekt hält, wie die beobachtete Abnahme der Abdeckung im Seen-to-Unseen-Szenario zeigt.

Zusammenfassend schließt ENCP die Lücke zwischen theoretischen Unsicherheitsgarantien und der praktischen, sequentiellen Natur der VLN, indem es einen robusten Mechanismus für den sicheren Einsatz von Agenten bietet.