Realizable Bayes-Consistency for General Metric Losses

Sintesi Tecnica: Bayes-Consistenza Realizzabile per Perdite Metriche Generali

1. Enunciato del Problema

Questo articolo affronta il problema della Bayes-consistenza universale forte nel setting realizzabile per l'apprendimento con perdite metriche generali. Il setting coinvolge:

• Uno spazio delle istanze $(X, \rho)$ e uno spazio delle etichette $(Y, \ell)$, dove $\ell$ è una metrica che può essere illimitata.
• Una classe di ipotesi $\mathcal{H} \subseteq Y^X$.
• Una distribuzione generatrice di dati $\bar{\mu}$ su $X \times Y$ che è realizzabile da $\mathcal{H}$, il che significa che il rischio ottimo è zero ($\inf_{h \in \mathcal{H}} R_{\bar{\mu}}(h) = 0$).

L'obiettivo è determinare condizioni necessarie e sufficienti su $\mathcal{H}$ tali per cui esista una regola di apprendimento libera dalla distribuzione il cui rischio converga a zero quasi certamente per ogni distribuzione realizzabile $\bar{\mu}$.

Gli autori evidenziano una distinzione critica tra perdite limitate e illimitate. Nei setting limitati, controllare la probabilità di errore è sinonimo di controllare il rischio. Nei setting metrici illimitati, un apprendista può commettere errori su eventi con probabilità decrescente, eppure la magnitudine di questi errori può crescere così rapidamente che il rischio atteso rimane infinito o non converge a zero. L'articolo cerca di caratterizzare quando tali "fallimenti catastrofici di eventi rari" sono evitabili.

2. Metodologia e Quadro Teorico

L'articolo adotta un approccio combinatorio radicato nella teoria dei giochi infinita e negli ostacoli ad albero, estendendo framework precedentemente sviluppati per la classificazione 0-1 e la regressione limitata.

Definizioni Chiave:

• Albero di Littlestone $(\gamma_k)$ non decrescente infinito: Un albero binario completo in cui i nodi interni alla profondità $k$ sono istanze $x_{k,i}$, e gli archi uscenti sono etichettati con $y_{k,i,1}, y_{k,i,2} \in Y$ tali che la distanza metrica $\ell(y_{k,i,1}, y_{k,i,2}) \ge \gamma_k$. La sequenza $(\gamma_k)$ è non decrescente e diverge all'infinito ($\gamma_k \to \infty$). L'albero è "realizzabile" se ogni percorso finito radice-foglia è coerente con qualche ipotesi in $\mathcal{H}$.
• Assunzione di Realizzabilità: Gli autori assumono una condizione di "parametrizzazione compatta" (Lemma 4.3): $\mathcal{H}$ è parametrizzato da uno spazio compatto $\Theta$ con una mappa di valutazione continua. Sotto questa lieve assunzione, la realizzabilità dei prefissi finiti implica che ogni percorso infinito è realizzato da una singola ipotesi.

Architettura della Dimostrazione:
Il risultato principale è stabilito tramite un limite inferiore (necessità) e un limite superiore (sufficienza).

• Limite Inferiore (Impossibilità): Se $\mathcal{H}$ contiene un albero di Littlestone $(\gamma_k)$ non decrescente infinito, gli autori costruiscono una distribuzione realizzabile in cui l'avversario nasconde una sequenza di scelte di etichette sempre più separate dietro masse di probabilità in rapida decrescita. Utilizzando un argomento di Borel-Cantelli, dimostrano che per qualsiasi algoritmo di apprendimento, il rischio atteso è infinito per ogni dimensione del campione $n$. L'apprendista è costretto a indovinare tra etichette separate da $\gamma_k$ su nodi non visti, portando a un rischio divergente.
• Limite Superiore (Algoritmo Costruttivo): Se un tale albero non esiste, gli autori costruiscono una regola di apprendimento libera dalla distribuzione. La dimostrazione procede in quattro passaggi:
  1. Codifica Teorico-Giochistica: L'assenza dell'ostacolo ad albero implica che l'apprendista ha una strategia vincente in un specifico gioco infinito di Gale-Stewart contro un avversario.
  2. Stabilizzazione: Simulando questo gioco su un campione i.i.d., il processo si stabilizza quasi certamente dopo un numero finito di turni. Ciò produce, per ogni $x$, un insieme di etichette "ammissibili" $H_K(x)$ con diametro limitato.
  3. Partizionamento: Lo spazio delle istanze $X$ è partizionato in un numero numerabile di celle basate su un sottoinsieme denso di $Y$. All'interno di ogni cella, l'insieme delle etichette ammissibili ha un diametro limitato.
  4. Riduzione: Il problema è ridotto a un numero numerabile di sottoproblemi con perdite limitate. Gli autori applicano l'esistente algoritmo MedNet (Tsir Cohen & Kontorovich, 2022), che è fortemente universalmente Bayes-consistente per perdite metriche limitate, a ciascuna cella e aggregano i risultati.

3. Contributi Chiave

1. Caratterizzazione Netta: L'articolo fornisce una condizione necessaria e sufficiente per la Bayes-consistenza universale forte realizzabile sotto perdite metriche generali (eventualmente illimitate). La condizione è la non-esistenza di un albero di Littlestone $(\gamma_k)$ non decrescente infinito nella classe di ipotesi.
2. Risoluzione di un Problema Aperto: Questo lavoro risolve il caso realizzabile di un problema aperto posto da Tsir Cohen & Kontorovich (2022). Dimostra che condizioni naturali di tipo finito, come la finitezza del rischio Bayesiano ($R^* < \infty$) o la condizione "limitata in aspettativa" (BIE) sullo spazio delle etichette, sono insufficienti a garantire la consistenza nel setting illimitato.
3. Regola di Apprendimento Costruttiva: In assenza dell'ostacolo ad albero, l'articolo presenta una regola di apprendimento esplicita (basata sull'algoritmo MedNet e sulla stabilizzazione teorico-giochistica) che raggiunge la Bayes-consistenza universale forte.
4. Costruzione di un Controesempio: Gli autori forniscono un controesempio concreto (Sezione 3) che mostra che anche quando $R^* < \infty$, non esiste un apprendista consistente libero dalla distribuzione se la classe di ipotesi ammette la specifica struttura ad albero con gap illimitato.

4. Risultati e Significato

Il teorema centrale (Teorema 4.5) afferma che per spazi di Polish $(X, \rho)$ e $(Y, \ell)$ e una classe di ipotesi $\mathcal{H}$ che soddisfa lievi condizioni di misurabilità e compattezza, sono equivalenti:

1. Esiste una regola di apprendimento libera dalla distribuzione che è fortemente universalmente Bayes-consistente per ogni distribuzione realizzabile.
2. $\mathcal{H}$ non contiene un albero di Littlestone $(\gamma_k)$ non decrescente infinito con $\gamma_k \to \infty$.

Significato:
L'articolo chiarisce che la difficoltà dell'apprendimento con perdite metriche illimitate non è meramente una questione di integrabilità o condizioni sui momenti della distribuzione. Piuttosto, l'ostacolo è combinatorio e intrinseco alla classe di ipotesi. La scala dell'ambiguità (il gap tra le etichette) può crescere senza limite lungo la profondità di un albero, creando uno scenario in cui eventi rari dominano il rischio. Questo estende il classico framework dell'albero di Littlestone (usato per la perdita 0-1) e gli alberi di Littlestone scalati (usati per la regressione limitata) al setting metrico generale illimitato, individuando l'interazione precisa tra le magnitudini delle perdite illimitate e la realizzabilità.

Gli autori notano che estendere questa caratterizzazione al setting agnostico (dove la distribuzione non è necessariamente realizzabile) rimane una direzione aperta, citando le barriere discusse nel loro Appendice.