Conteggio delle etichette ottenibili: coefficienti di frantumazione canonici
A prima vista, definire verbalmente i coefficienti di frantumazione sembra semplice:
Data una classe di ipotesi H, suo Nᵗʰ coefficiente di frantumazione, indicato Sₙ(H), rappresenta il maggior numero di etichettature ottenibili dai classificatori in H su un campione di N vettori di caratteristiche.
Ma cos’è un “etichettatura“? E cosa lo rende”realizzabile“? Rispondere a queste domande ci aiuterà a gettare le basi per raggiungere una definizione più formale.
Nel contesto della classificazione binaria, a etichettatura di un campione di vettori di caratteristiche è semplicemente uno qualsiasi dei modi in cui possiamo assegnare valori dall'insieme { -1, 1 } a quei vettori. Come esempio molto semplice, consideriamo due vettori di caratteristiche unidimensionali (cioè punti su una linea numerica), X₁ = 1 e X₂ = 2.
Le possibili etichettature sono qualsiasi combinazione dei valori di classificazione che possiamo assegnare ai singoli vettori di caratteristiche indipendentemente l'uno dall'altro. Possiamo rappresentare ciascuna etichettatura come un vettore, dove la prima e la seconda coordinata rappresentano i valori assegnati X₁ e X₂, rispettivamente. L'insieme delle possibili etichettature è quindi { (-1, -1), (-1, 1), (1, -1), (1, 1) }. Nota che un campione di dimensione 2 produce 2² = 4 possibili etichettature: vedremo presto come questo si generalizza a campioni di dimensioni arbitrarie.
Lo diciamo un'etichettatura è realizzabile da una classe di ipotesi H se esiste un classificatore H ∈ H da cui può derivare tale etichettatura. Continuando con il nostro semplice esempio, supponiamo di essere limitati ai classificatori della forma X ≥ KK ∈ ℝ, cioè soglie unidimensionali tali che qualsiasi cosa a destra della soglia sia classificata positivamente. L'etichettatura (1, -1) non è ottenibile con questa classe di ipotesi. X₂ essendo maggiore di X₁ implica che qualsiasi soglia che classifica X₁ deve assolutamente fare lo stesso per X₂. L'insieme delle etichettature ottenibili è quindi { (-1, -1), (-1, 1), (1, 1) }.
Avendo compreso la terminologia di base, possiamo iniziare a sviluppare alcune notazioni per esprimere formalmente elementi della definizione verbale con cui siamo partiti.
Ci limiteremo a rappresentare le etichette come vettori come abbiamo fatto nel nostro semplice esempio, con ciascuna coordinata che rappresenta il valore di classificazione assegnato al corrispondente vettore di caratteristiche. Ce ne sono 2ⁿ possibili etichettature in totale: ci sono due scelte possibili per ciascun vettore di caratteristiche e possiamo pensare a un'etichettatura come a una raccolta di N tali scelte, ciascuna fatta indipendentemente dalle altre. Se una classe di ipotesi H può ottenere tutte le possibili etichettature di un campione 𝒞ₙ, cioè, se il numero di realizzabile etichettature di 𝒞ₙ equivale a 2ⁿ, lo diciamo H va in frantumi 𝒞ₙ.
Infine, utilizzando la notazione di cui sopra, convergiamo su una definizione più rigorosa di Sₙ(H):
In linea con la nostra spiegazione della frantumazione, Sₙ(H) pari a 2ⁿ implica che esista un campione di dimensioni N che è distrutto da H.
Stima dell'espressività delle classi di ipotesi: dimensione canonica VC
La dimensione Vapnik-Chervonenkis (VC) è un modo per valutare il potere espressivo di una classe di ipotesi. Si basa sull'idea di frantumazione che abbiamo appena definito e svolge un ruolo importante nell'aiutarci a determinare quali classi di ipotesi sono apprendibili tramite PAC e quali no.
Cominciamo tentando di definire intuitivamente la dimensione canonica VC:
Data una classe di ipotesi Hla sua dimensione VC, denominata VCdim(H), è definito come il numero naturale più grande N per il quale esiste un campione dimensionale N questo è in frantumi di H.
Utilizzando Sₙ(H) ci permette di esprimerlo in modo molto più chiaro e conciso:
VCdim(H) = massimo{ N ∈ ℕ : Sₙ(H) = 2ⁿ }
Tuttavia, questa definizione non è precisa. Si noti che l'insieme di numeri per i quali il coefficiente di frantumazione è uguale a 2ⁿ può essere infinito. (Di conseguenza, è possibile che VCdim(H) = ∞.) Se è così, l'insieme non ha un massimo ben definito. Affrontiamo questo problema prendendo invece il massimo:
VCdim(H) = sup{ N ∈ ℕ : Sₙ(H) = 2ⁿ }
Questa definizione rigorosa e concisa è quella che utilizzeremo in futuro.
Aggiungere preferenze al mix: coefficienti strategici sconvolgenti
Generalizzare le nozioni canoniche che abbiamo appena esaminato in modo che funzionino in un contesto strategico è abbastanza semplice. Ridefinire i coefficienti dirompenti in termini di migliore risposta del punto dati abbiamo definito in l'articolo precedente è praticamente tutto quello che dovremo fare.
Data una classe di ipotesi H, un insieme di preferenze Re una funzione di costo C, IL Nᵗʰ coefficiente di rottura di Sᴛʀᴀᴄ⟨H, R, C⟩, indicato σₙ(H, R, c), rappresenta il maggior numero di etichettature ottenibili dai classificatori in H su una serie di N vettori di caratteristiche potenzialmente manipolati, vale a dire N migliori risposte ai dati.
Come promemoria, ecco come abbiamo definito la migliore risposta del punto dati:
Possiamo modificare la notazione che abbiamo usato nella nostra discussione sui coefficienti di frantumazione canonici per formalizzarlo ulteriormente:
La differenza principale è che ciascuno X nel campione deve avere un corrispondente R. A parte questo, inserire la migliore risposta del punto dati dove avevamo x nel caso canonico funziona senza problemi.
Come rapido controllo di integrità, consideriamo cosa succede se R = {0}. Il termine della ricompensa realizzata 𝕀(H(z) = 1) ⋅ R sarà 0 in tutti i punti dati. Massimizzare l’utilità diventa quindi sinonimo di minimizzare i costi. Il modo migliore per ridurre al minimo il costo sostenuto da un punto dati è banale: senza mai manipolare il suo vettore di caratteristiche.
D(X, R; H) finisce sempre per essere e basta X, collocandoci saldamente nel territorio della classificazione canonica. Ne consegue che σₙ(H{0}, C) = Sₙ(H) per tutti H, c. Ciò è coerente con la nostra osservazione secondo cui la classe di preferenza imparziale rappresentata da R = { 0 } equivale alla classificazione binaria canonica.
Espressività con preferenze: dimensione strategica VC (SVC)
Avendo definito il Nᵗʰ coefficiente di frantumazione strategica, possiamo semplicemente scambiare il file Sₙ(H) nella definizione canonica della dimensione VC per σₙ(H, R, C).
SVC(H, R, c) = sup{ N ∈ ℕ : pagₙ(H, R, c) = 2ⁿ }
Sulla base dell'esempio considerato sopra, troviamo che SVC(H{0}, C) = VCdim(H) per ogni H, C. Infatti, SVC sta a VCdim come il coefficiente di frantumazione strategica sta al suo equivalente canonico: entrambi sono eleganti generalizzazioni di concetti non strategici.
Dall'SVC all'apprendimento strategico del PAC: il teorema fondamentale dell'apprendimento strategico
Ora possiamo usare SVC per enunciare il Teorema Fondamentale dell’Apprendimento Strategico, che mette in relazione la complessità di un problema di classificazione strategica con la sua apprendibilità (agnostica) del PAC.
Un'istanza di classificazione strategica Sᴛʀᴀᴄ⟨H, R, C⟩ è agnostico il PAC apprendibile se e solo se SVC(H, R, c) è finito. IL complessità del campione per l’apprendimento PAC agnostico strategico è M(D, e) ≤ Cε ⁻² ⋅ (SVC(H, R, c) + log(1/D))con C essendo una costante.
Non elaboreremo troppo su come ciò possa essere dimostrato. Basti dire che si tratta di un’intelligente riduzione al (ben documentato) Teorema Fondamentale di Statistico Apprendimentoche è essenzialmente la versione non strategica del teorema. Se sei portato per la matematica e sei interessato agli aspetti pratici della dimostrazione, puoi trovarlo in Appendice B del documento.
Questo teorema completa essenzialmente la nostra generalizzazione del classico apprendimento PAC a un contesto di classificazione strategica. Ciò dimostra che il modo in cui abbiamo definito SVC in realtà non ha senso solo nella nostra testa; in realtà funziona come una generalizzazione di VCdim dove conta di più. Armati del Teorema Fondamentale, siamo ben attrezzati per analizzare i problemi di classificazione strategica proprio come faremmo con qualsiasi vecchio problema di classificazione binaria. Secondo me, avere la capacità di determinare se un problema strategico è teoricamente apprendibile o meno è davvero incredibile!
Fonte: towardsdatascience.com
