Local Regularization Does Not Characterize Multiclass PAC Learnability

Sintesi Tecnica: La Regolarizzazione Locale non Caratterizza la Apprendibilità PAC Multiclasse

Enunciato del Problema
Una questione centrale nella teoria dell'apprendimento statistico è l'identificazione di principi algoritmici semplici che caratterizzino l'apprendibilità di classi di ipotesi. Nella classificazione binaria, l'ERM (Empirical Risk Minimization) caratterizza l'apprendibilità PAC. Tuttavia, il contesto multiclasse è più complesso; l'apprendimento appropriato può fallire per classi apprendibili, e gli apprenditori ottimali spesso si affidano a strutture dipendenti dal campione piuttosto che a ordinamenti fissi delle ipotesi.

Asilis et al. hanno proposto la regolarizzazione locale come una potenziale generalizzazione dell'ERM per il contesto multiclasse. Un regolarizzatore locale assegna un punteggio fisso $\psi(h, x)$ a ogni ipotesi $h$ in ogni punto di test $x$, indipendentemente dal campione di addestramento. Un apprenditore indotto da tale regolarizzatore predice l'etichetta dell'ipotesi con il punteggio minimo tra quelle coerenti con il campione osservato. Sebbene Jafar, Asilis e Dughmi avessero precedentemente dimostrato che la regolarizzazione locale fallisce nel caratterizzare l'apprendibilità nel modello transduttivo (dove un punto specifico trattenuto viene testato), rimaneva aperto il quesito se tale principio caratterizzasse l'apprendibilità PAC, dove il punto trattenuto può avere una massa di popolazione trascurabile e il campionamento ripetuto potrebbe teoricamente rivelarlo.

Metodologia e Costruzione
L'articolo costruisce un controesempio utilizzando una classe di ipotesi numerabile basata su tornei (grafi completi diretti).

• Classe di Ipotesi ($H$): Per un intero $q \ge 3$, le ipotesi corrispondono agli archi di un grafo completo $K_q$. Un'ipotesi $h_{q,e}$ predice la "testa" (vertice target) dell'arco $e$ all'interno di un'istanza di torneo $\tau$.
• Spazio delle Istanze: Le istanze sono coppie $(q, \tau)$, dove $\tau$ è un torneo su $q$ vertici.
• Distribuzioni Difficili: Gli autori definiscono una famiglia di distribuzioni "difficili" $D_{e,v}$ per un arco target $e=\{u,v\}$ e un estremo $v$. Queste distribuzioni sono uniformi sui tornei in cui l'arco $e$ è orientato verso $v$. Di conseguenza, tutte le etichette osservate nel campione di addestramento sono identiche: $(q, v)$.
• Il Meccanismo del Fallimento:
  1. Filtraggio: Il campione di addestramento (tutte le etichette uguali a $v$) filtra lo spazio delle versioni, trattenendo solo le ipotesi corrispondenti agli archi incidenti a $v$ che sono orientati verso $v$ nei tornei campionati.
  2. Classifica Fissa: Il regolarizzatore locale $\psi$ impone un ordinamento totale stretto sugli archi incidenti a $v$ al punto di test prima che il campione venga osservato.
  3. Inversioni Cicliche: La difficoltà principale deriva dai triangoli ciclici nel torneo. Anche se il campione di addestramento rimuove molti concorrenti, l'ordinamento fisso degli archi rimanenti può essere "invertito" rispetto al vero target a causa della struttura ciclica. Nello specifico, se un arco uscente (che non dovrebbe essere il target) sopravvive al processo di filtraggio e appare prima dell'arco entrante target nella classifica fissa del regolarizzatore, l'apprenditore commette un errore.

Contributi Chiave e Risultati

1. Esistenza di un Controesempio: L'articolo dimostra l'esistenza di una classe di ipotesi multiclasse numerabile $H$ che è PAC apprendibile ma non apprendibile da alcun regolarizzatore locale.

   • Apprendibilità: La classe è PAC apprendibile con una complessità di campionamento di $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$. Un apprenditore esplicito ha successo identificando l'arco target una volta che entrambi gli estremi delle etichette appaiono nel campione.
   • Limite della Dimensione: La classe ha una dimensione di Daniely–Shalev-Shwartz (DS) di al massimo 2. Ciò è stabilito mostrando che l'immagine di ogni ipotesi contiene al massimo due etichette, impedendo la formazione di un pseudo-cubo a 3 dimensioni.

2. Teorema di Impossibilità: Per qualsiasi regolarizzatore locale $\psi$, esiste un apprenditore indotto $A_\psi$ che fallisce nell'apprendere PAC $H$.

   • Modalità di Fallimento: Per ogni regolarizzatore fisso, gli autori mostrano che per dimensioni di campione arbitrariamente grandi, esistono distribuzioni realizzabili in cui la probabilità di errore supera una costante $\delta_0 = \frac{1}{192e}$.
   • Limiti Quantitativi: La probabilità di errore è limitata lontano dallo zero ($\varepsilon_0 = \frac{1}{96e}$) perché il numero atteso di "inversioni" (archi uscenti classificati prima di archi entranti) nella struttura del torneo rimane significativo. La prova sfrutta il fatto che un torneo casuale contiene $\Theta(q^3)$ triangoli ciclici, garantendo che per qualsiasi ordinamento stretto degli archi, una frazione costante di incidenze target risulterà in un errore di predizione.

Significato e Rivendicazioni
L'articolo conclude che la regolarizzazione locale non caratterizza l'apprendibilità PAC multiclasse realizzabile.

• Distinzione dai Risultati Transduttivi: A differenza del limite inferiore transduttivo di Jafar et al., che si basa su un singolo punto trattenuto con potenzialmente massa trascurabile, questa costruzione distribuisce l'errore su una popolazione di tornei. Il fallimento persiste anche quando le dimensioni del campione crescono arbitrariamente grandi, impedendo all'apprenditore di "imparare" la struttura nascosta attraverso il campionamento ripetuto.
• Limitazione dei Punteggi Fissi: Il risultato evidenzia una rigidità fondamentale nella regolarizzazione locale: poiché la classifica delle ipotesi al punto di test è fissata prima di osservare il campione, l'apprenditore non può adattare l'ordinamento relativo dei concorrenti superstiti in base alla specifica struttura dei dati di addestramento. Nel contesto dei tornei, questa incapacità di riordinare porta a un errore di popolazione costante nonostante la classe abbia una bassa dimensione DS e sia efficientemente apprendibile per altri mezzi.
• Ambito: Il risultato si applica specificamente ai regolarizzatori in cui i punteggi sono fissi indipendentemente dal campione. Non affronta i framework non supervisionati in cui la regola di regolarizzazione potrebbe dipendere dal campione non etichettato.

In sintesi, l'articolo fornisce una risposta negativa definitiva alla domanda se la regolarizzazione locale caratterizzi l'apprendibilità PAC multiclasse, dimostrando che anche per classi con bassa dimensione combinatoria (DS-dim $\le 2$) e complessità di campionamento ottimale, i regolarizzatori a punteggio fisso possono fallire l'apprendimento.