Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations

Technisches Fazit: Adaptive Zuweisung von Messungen zum Erlernen von Kernel-SVMs unter verrauschten Beobachtungen

Problemformulierung
Kernel-Methoden, insbesondere Support Vector Machines (SVM), werden traditionell unter der Annahme formuliert, dass die Gram-Matrix (Kernel-Matrix) mit exakter, rauschfreier Präzision verfügbar ist. In aufkommenden Domänen wie dem Quanten-Machine-Learning (QML) können Kernel-Einträge jedoch nicht durch geschlossene Funktionen berechnet werden. Stattdessen müssen sie aus verrauschten Beobachtungen abgeleitet werden, die typischerweise als wiederholte Bernoulli- oder multinomiale „Shots" parametrisierter Quantenschaltkreise modelliert werden. In diesen Szenarien wird die Genauigkeit eines Kernel-Eintrags $K_{ij}$ direkt durch die Anzahl der für seine Schätzung zugewiesenen Mess-Shots ($N_{ij}$) bestimmt.

Die zentrale Herausforderung besteht in der Zuweisung eines begrenzten globalen Messbudgets ($N_{tot}$) auf die $O(n^2)$ unabhängigen Kernel-Einträge. Der Standardansatz in der Literatur ist die uniforme Zuweisung, bei der jeder Eintrag die gleiche Anzahl an Shots erhält. Während die uniforme Zuweisung die maximale Varianz unter den Einträgen minimiert und eine symmetrische Fehlerverteilung gewährleistet, ist sie „aufgabenagnostisch". Sie berücksichtigt nicht die hochgradig nicht-uniforme Abhängigkeit des SVM-Klassifizierers von der Gram-Matrix. Spezifisch wird die SVM-Lösung primär durch eine spärliche Teilmenge von Trainingspunkten (Support Vectors) und deren Wechselwirkungen bestimmt. Folglich ist eine uniforme Schätzung für SVMs inhärent suboptimal, da sie Ressourcen für Kernel-Einträge verschwendet, die einen vernachlässigbaren Einfluss auf die Entscheidungsgrenze haben, während kritische Regionen unterabgetastet werden.

Methodik
Die Autoren schlagen eine aufgabenbewusste adaptive Strategie zur Zuweisung von Messungen vor, die darauf ausgelegt ist, kernelisierte SVMs aus verrauschten Bernoulli-Beobachtungen zu erlernen. Die Methode basiert auf dem Prinzip, dass Messressourcen auf die Regionen der Kernel-Matrix konzentriert werden sollten, die für die Geometrie und Stabilität des Klassifizierers am kritischsten sind.

Der Ansatz stützt sich auf zwei komplementäre Signale:

1. Geometrische Sensitivität: Dies erfasst den Einfluss erster Ordnung eines Kernel-Eintrags $K_{ij}$ auf den quadrierten Rand $\|w\|^2$. Unter Verwendung des Einhüllenden-Theorems (Envelope Theorem) wird die Sensitivität als proportional zu $\alpha_i \alpha_j y_i y_j$ hergeleitet, wobei $\alpha$ die dualen Koeffizienten sind. Einträge, die Support Vectors betreffen (wo $\alpha > 0$), haben einen direkten, nicht-null Einfluss auf den Rand, während Nicht-Support-Vectors keinen Einfluss erster Ordnung haben.
2. Instabilität des aktiven Sets: Dies quantifiziert die Wahrscheinlichkeit diskreter struktureller Änderungen im Klassifizierer, spezifisch die Wahrscheinlichkeit, dass ein Datenpunkt aufgrund von Messrauschen in das oder aus dem Support-Vector-Set ein- oder austritt. Dies wird modelliert, indem die Wahrscheinlichkeit geschätzt wird, dass das Rand-Residuum $\Delta_i = y_i f(x_i) - 1$ Null kreuzt, approximiert durch die Varianz der Entscheidungsfunktion und die kumulative Verteilungsfunktion (CDF) der Standardnormalverteilung.

Algorithmisches Framework
Der vorgeschlagene Algorithmus verläuft in einer mehrstufigen adaptiven Schleife:

• Pilotphase: Eine kleine, uniforme Anzahl von Shots wird allen Einträgen zugewiesen, um eine initiale Kernel-Schätzung $\hat{K}^{(0)}$ zu generieren und eine vorläufige SVM zu trainieren. Dies liefert grobe Schätzungen des Support-Vector-Sets und der dualen Koeffizienten.
• Adaptive Runden: In jeder nachfolgenden Runde berechnet der Algorithmus einen paarweisen Zuweisungsscore $s_{ij}$ für jeden Kernel-Eintrag. Dieser Score kombiniert die geometrische Sensitivität ($|\alpha_i \alpha_j y_i y_j|$) und die Instabilität des aktiven Sets ($P_i P_j$), gewichtet mit einem Parameter $\lambda$. Die Scores werden zusätzlich durch den Bernoulli-Varianzterm moduliert, um statistisch unsichere Einträge zu priorisieren.
• Ressourcen-Umverteilung: Ein Teil des verbleibenden Budgets wird durch multinomiale Stichprobenziehung proportional zu diesen Scores verteilt, um ganzzahlige Shot-Anzahlen sicherzustellen. Die Kernel-Schätzung wird aktualisiert und die SVM wird neu trainiert.
• Frühes Stoppen: Der Prozess endet, wenn das Gesamtbudget erschöpft ist oder wenn sich die dualen Koeffizienten stabilisieren (gemessen an der relativen Änderung von $y_i \alpha_i$ zwischen den Runden). Dieses Kriterium ermöglicht es dem Algorithmus, zu stoppen, sobald der Klassifizierer effektiv konvergiert ist, und vermeidet unnötige Messungen.

Hauptbeiträge

1. Aufgabenbewusste Formulierung: Das Papier formuliert die Messzuweisung nicht als isoliertes Schätzproblem, sondern als integralen Bestandteil der SVM-Lernpipeline und hebt explizit die nicht-uniforme Abhängigkeit des Klassifizierers von Kernel-Einträgen hervor.
2. Neues Zuweisungskriterium: Die Autoren führen ein Kriterium ein, das Randsensitivität und Instabilität des aktiven Sets kombiniert. Dies bietet eine interpretierbare Alternative zu gradientenbasierten Zuweisungsstrategien (wie sie in der adaptiven Quanten-Kernel-Zuweisung verwendet werden) und zielt direkt auf die SVM-Entscheidungsgrenze ab.
3. Theoretische Analyse: Die Arbeit liefert eine theoretische Analyse, die zeigt, dass der Vorteil einer adaptiven Zuweisung durch die Heterogenität der induzierten Kernel-Wichtigkeitsstruktur bestimmt wird. Sie identifiziert distincte Regime:
   • Hochstruktur-Regime: Wo duale Koeffizienten spärlich und Gewichte heterogen sind, übertrifft die adaptive Zuweisung das uniforme Sampling erheblich.
   • Niedrigstruktur-Regime: Wo die Lösung nahezu uniform ist, nehmen die Vorteile der Adaptivität ab, und die uniforme Zuweisung kann aufgrund ihrer Robustheit gegenüber Schätzrauschen vorzuziehen sein.
4. Empirische Validierung: Umfassende Experimente auf synthetischen Datensätzen und realen Quanten-Kernels (abgeleitet vom Indian-Pines-Datensatz) zeigen, dass die adaptive Strategie die Wiederherstellung von Support Vectors, die Randschätzung und die Genauigkeit der Entscheidungsfunktion unter festen Budgets verbessert.

Ergebnisse und Leistung

• Leistung bei festem Budget: Unter festen Messbudgets übertrifft die adaptive Strategie die uniforme Zuweisung konsistent in aufgabenrelevanten Metriken (SV-Block-RMSE, Wiederherstellung von Support Vectors und Fehler der Entscheidungsfunktion), und zwar bereits nach der ersten Verfeinerungsrunde. Bemerkenswerterweise erreicht die uniforme Zuweisung oft einen niedrigeren globalen Kernel-Rekonstruktionsfehler (RMSE über alle Einträge), schneidet jedoch bei den spezifischen Einträgen, die den Klassifizierer bestimmen, schlecht ab.
• Frühes Stoppen: Das Stabilitätskriterium für duale Koeffizienten ermöglicht es dem Algorithmus, frühzeitig zu terminieren, wobei oft nur ein Bruchteil (z. B. ~16 %) des gesamten Messbudgets verwendet wird, während eine Leistung erzielt wird, die mit dem uniformen Sampling unter vollem Budget vergleichbar ist oder dieses übertrifft.
• Quanten-Kernel-Regime: Experimente mit Quanten-Kernels offenbaren ein Drei-Regime-Verhalten basierend auf der Systemgröße (Qubit-Anzahl):
  • Niedrige Qubit-Anzahl: Uniformes Sampling ist wettbewerbsfähig aufgrund schwacher struktureller Differenzierung.
  • Mittlere Qubit-Anzahl: Adaptive Zuweisung erzielt erhebliche Gewinne, da der Kernel eine strukturierte, heterogene SVM-Lösung induziert.
  • Hohe Qubit-Anzahl: Kernel-Konzentrationseffekte verschlechtern das Signal für beide Methoden, obwohl die adaptive Zuweisung in der Ressourcennutzung effizienter bleibt.
• Kosteneffizienz: Das Papier analysiert den Trade-off zwischen Quantenmesskosten und klassischem Neu-Trainings-Overhead. Es kommt zu dem Schluss, dass in typischen QML-Szenarien (wo Messkosten hoch und Datensatzgrößen moderat sind), das adaptive Schema einen doppelten Vorteil bietet: verbesserte Klassifizierer-Fidelity und reduzierte Gesamtrechenkosten.

Bedeutung
Das Papier etabliert die adaptive Messzuweisung als prinzipielle und effektive Alternative zum uniformen Sampling für das Lernen mit verrauschten Kernels. Durch den Wechsel des Fokus von der Minimierung des globalen Schätzfehlers zur Minimierung des Einflusses von Rauschen auf die spezifische Lernaufgabe (SVM-Klassifizierung) bietet die vorgeschlagene Methode erhebliche Verbesserungen in der Klassifizierer-Fidelity und der Recheneffizienz. Die Arbeit ist insbesondere für das Quanten-Machine-Learning von großer Bedeutung, wo Messressourcen knapp sind und Phänomene wie die Kernel-Konzentration schwere Herausforderungen darstellen. Die Ergebnisse deuten darauf hin, dass „intelligente" Zuweisungsstrategien das Betriebsregime kernelbasierter Lernverfahren erweitern können, wodurch sinnvolles Training in Szenarien möglich wird, in denen uniformes Sampling versagen oder prohibitiv teuer wäre.