Apprendimento automatico e Reti Neurali - pagina 4

 

Lezione 6 - Teoria della generalizzazione




Corso di Machine Learning di Caltech - CS 156. Lezione 06 - Teoria della generalizzazione

La lezione discute la teoria della generalizzazione e la funzione di crescita come numero di dicotomie che possono essere generate da un'ipotesi posta su un insieme di N punti, con l'obiettivo di caratterizzare l'intera funzione di crescita e generalizzare per ogni N caratterizzando la rottura punto. Il relatore dimostra il processo di calcolo della funzione di crescita per diversi insiemi di ipotesi e dimostra il limite superiore per la funzione di crescita utilizzando l'identità combinatoria. La discussione tocca anche l'utilizzo della funzione di crescita nella disuguaglianza di Hoeffding, la VC destinata a caratterizzare le sovrapposizioni tra ipotesi e la disuguaglianza di Vapnik-Chervonenkis, che è un polinomio in N con l'ordine del polinomio deciso dal punto di rottura.

Il professore discute la teoria della generalizzazione, chiarendo i punti precedenti e spiegando il concetto di punto di rottura, che viene utilizzato per calcolare le risorse necessarie per l'apprendimento. L'obiettivo dell'apprendimento è l'approssimazione a E_out, non E_in, consentendo allo studente di lavorare con quantità familiari. Il professore spiega anche il ragionamento alla base della sostituzione di M con la funzione di crescita e come questa sia correlata alla quantità combinatoria B di N e k. Durante la discussione delle funzioni di regressione, il professore sottolinea il compromesso tra bias e varianza e come l'apprendimento sia indipendente dalla funzione target. Infine, il professore osserva che gli stessi principi si applicano a tutti i tipi di funzioni.

  • 00:00:00 In questa sezione, apprendiamo le dicotomie come mini-ipotesi limitate a un insieme finito di punti e alla funzione di crescita. La funzione di crescita conta il numero di dicotomie che possono essere generate da un'ipotesi posta su un insieme di N punti. Il punto di rottura per i percettroni è definito come il punto in cui i modelli iniziano a essere persi a causa dell'uso di ipotesi da un insieme ristretto. L'obiettivo teorico è caratterizzare l'intera funzione di crescita e generalizzare per ogni N caratterizzando il punto di rottura. Vediamo anche che una restrizione del numero di modelli su pochi punti comporta la perdita di molti modelli per un numero maggiore di punti, indipendentemente dall'insieme di ipotesi e dallo spazio di input.

  • 00:05:00 In questa sezione, il docente discute due argomenti: il primo dimostra che la funzione di crescita è polinomiale con un punto di interruzione e il secondo dimostra la sostituzione di M, il numero di ipotesi, nella disuguaglianza di Hoeffding. Il docente sottolinea che non hanno bisogno di determinare i dettagli della funzione di crescita, ma solo di dimostrare che è delimitata da un polinomio in modo che possa essere utilizzata nella disuguaglianza di Hoeffding. Il docente introduce una quantità chiave chiamata B di N e k, che è una quantità combinatoria che rappresenta il numero massimo di dicotomie su N punti con un break point k. Il limite per B di N, k viene trovato ricorsivamente riempiendo una tabella con N punti e isolando l'ultimo punto per introdurre una ricorsione.

  • 00:10:00 In questa sezione, il relatore discute come raggruppare le righe di una matrice che rappresentano l'estensione di una sequenza binaria. Il primo gruppo, S_1, è costituito da righe che vengono visualizzate solo una volta in base all'estensione. Il secondo gruppo, S_2, è costituito da righe visualizzate con entrambe le estensioni. Utilizzando questi raggruppamenti, l'oratore definisce il numero di righe nel gruppo S_1 come alfa e il numero di righe nel gruppo S_2 come beta. Con queste definizioni, il parlante è in grado di trovare una ricorsione per il numero massimo di righe/schemi che può essere ottenuto su N punti in modo tale che nessuna k colonna abbia tutti i possibili schemi.

  • 00:15:00 In questa sezione della conferenza, il relatore discute la teoria della generalizzazione e come stimare il beta. Spiega che analizzando la seconda parte della matrice S_2, che contiene blocchi di pattern ripetuti, può sostenere che questi blocchi di pattern hanno un break point di k meno 1, non di k. Spiega anche che prendendo alfa più beta, che è il numero totale di righe o modelli nella mini-matrice, può dire qualcosa su un punto di rottura per questa piccola matrice. Conclude affermando che, mettendo tutto insieme, può stimare l'intera matrice e il suo numero di righe.

  • 00:20:00 In questa sezione, il relatore analizza una matrice e ricava una formula ricorsiva per risolvere un limite superiore su B di N e k, dove B di N e k è la funzione di crescita massima di un'ipotesi impostata con un'interruzione punto di k. Calcolando i valori di B di N e k usando la formula ricorsiva, l'oratore riempie una tabella con un limite superiore su B di N e k. Le condizioni al contorno per la tabella vengono riempite per prime, quindi il resto della tabella viene riempito utilizzando la formula di ricorsione.

  • 00:25:00 In questa sezione, il relatore discute la teoria della generalizzazione e parla di una tabella che rappresenta il numero massimo di dicotomie o modelli dato un numero specifico di punti, N, e un punto di interruzione, k. Il relatore spiega come si riempie la tabella e come il vincolo può essere vuoto. Inoltre, presentano una formula che calcola il numero massimo di dicotomie o modelli come limite superiore per la funzione di crescita di qualsiasi insieme di ipotesi che abbia un punto di interruzione k, senza porre alcuna domanda sull'insieme di ipotesi o sullo spazio di input.

  • 00:30:00 In questa sezione, il docente discute il passo di induzione per dimostrare un teorema sulla formula per N e k. Il passo consiste nell'assumere che la formula valga per dati valori di N e k, e poi dimostrare che vale anche per N-1 e k-1. Il docente dimostra il processo di manipolazione delle due formule, unendo le somme e riducendole a un'unica quantità utilizzando argomenti algebrici o combinatori. Lo scopo è stabilire che la formula data vale per tutti i valori di N e k, che include i valori precedentemente assunti, e da lì il teorema è dimostrato.

  • 00:35:00 In questa sezione, il relatore spiega il processo di dimostrazione del limite superiore per B di N e k, la funzione di crescita per un insieme di ipotesi che ha un punto di rottura k, utilizzando l'identità combinatoria. Il polinomio risultante è utile perché il punto di interruzione è un numero fisso e non cresce con N. Il relatore illustra quindi che il limite superiore è un polinomio in N mostrando che la potenza massima è N su k meno 1, che è un costante. Infine, il relatore applica il limite superiore a tre esempi di insiemi di ipotesi e mostra che tutti soddisfano il limite.

  • 00:40:00 In questa sezione, il docente discute il calcolo della funzione di crescita per raggi positivi e intervalli positivi. Utilizzando il break point, che è l'unico input richiesto, è in grado di trovare la funzione di crescita senza considerare la geometria dell'insieme di ipotesi. Il docente applica quindi questo metodo al percettrone bidimensionale, dove la funzione di crescita è sconosciuta, ma è noto che il punto di rottura è 4. Usando il punto di rottura, è in grado di legare completamente la funzione di crescita, il che è importante nel semplificare la caratterizzazione degli insiemi di ipotesi. Il docente spiega quindi come questa funzione di crescita può essere utilizzata nella disuguaglianza di Hoeffding per sostituire il numero di ipotesi utilizzando l'union bound, che è quasi inutile quando M è significativo o infinito.

  • 00:45:00 In questa sezione, il docente spiega la dimostrazione grafica della limitatezza polinomiale della funzione di crescita. Lo spazio dei possibili insiemi di dati copre tutti gli assi e l'area colorata rappresenta la regione difettosa in cui E_in devia da E_out a causa di determinati insiemi di dati. Dipingendo di rosso questa brutta regione e utilizzando la disuguaglianza di Hoeffding, il docente mostra che l'area colorata è piccola, consentendo all'unione vincolata di rivendicare la possibilità di ipotesi multiple. Tuttavia, quando vengono aggiunte più ipotesi, l'area colorata riempie la tela, portando al problema con l'unione vincolata. Il docente spiega quindi i due aspetti necessari per stabilire la relazione tra la funzione di crescita e le sovrapposizioni e l'approccio per E_out per conformarsi all'argomento del campione finito.

  • 00:50:00 In questa sezione, il docente introduce il VC legato come una nuova tela per caratterizzare le sovrapposizioni tra ipotesi. Spiega che la funzione di crescita è una quantità astratta che caratterizza queste sovrapposizioni e ti dice il numero di dicotomie che si comportano allo stesso modo. Il docente spiega che la ridondanza è catturata dalla funzione di crescita e che il punto colorato non dipende solo dal campione ma anche dall'intero spazio. Il docente supera questo problema selezionando due campioni invece di uno, che sono generati indipendentemente dalla stessa distribuzione, per tracciare E_out ed E_in senza fare affidamento sull'intera ipotesi.

  • 00:55:00 In questa sezione, l'oratore discute il concetto di tracciamento tra E_in e E_in trattino, che sono due campioni diversi, e se si seguono o meno. Se vengono utilizzati più contenitori, il legame tra E_out e E_in diventa sempre più allentato. Inoltre si separano leggermente all'aumentare del numero di contenitori. Le ramificazioni matematiche di ipotesi multiple si verificano allo stesso modo qui come per un bidone. Man mano che l'oratore passa attraverso i tecnicismi della dimostrazione, l'epsilon diventa epsilon su 2 e poi diventa epsilon su 4. Quando sono collegati, ottengono epsilon al quadrato su 16, risultando in un fattore di 1/8. Il risultato ottenuto si chiama disuguaglianza di Vapnik-Chervonenkis, che è polinomiale in N e ha l'ordine del polinomio deciso dal break point.

  • 01:00:00 In questa sezione della videolezione, il moderatore chiede al professore di chiarire alcuni punti fatti nelle slide precedenti. Il professore spiega che gli N punti scelti nella diapositiva 5 corrispondono a un particolare insieme di punti in uno spazio di input nell'apprendimento automatico, ma nell'astrazione si tratta semplicemente di etichette astratte. Il professore chiarisce inoltre che il loro uso di alfa e beta nella lezione è semplicemente una convenzione di denominazione e non vi è alcuna affermazione sui valori relativi dei due. Infine, il professore spiega che il punto di interruzione viene calcolato visitando lo spazio di input e l'insieme di ipotesi e scoprendo, per un dato insieme di ipotesi, qual è il numero massimo di punti che non possono essere separati in ogni modo possibile.

  • 01:05:00 In questa sezione, il professore spiega che per la maggior parte dei modelli di apprendimento sono già stati stabiliti punti di interruzione esatti o vincolati, il che significa che le risorse necessarie per apprendere possono essere stimate prima di iniziare il processo di apprendimento. Sebbene possano esserci casi in cui i limiti non sono stretti, nella maggior parte dei casi la discrepanza tra la stima esatta della funzione di crescita e il limite quadratico sarà trascurabile. La lezione sottolinea che il focus dell'apprendimento non è sul valore effettivo di E_in, ma sulla sua approssimazione a E_out, consentendo allo studente di lavorare con quantità familiari. Infine, il professore assicura al pubblico che la dimensione VC, che è un elemento fondamentale per comprendere le teorie dell'apprendimento, sarà trattata in dettaglio nella prossima lezione.

  • 01:10:00 In questa sezione, il professore spiega il ragionamento alla base della sostituzione di M con la funzione di crescita e le modifiche che dovevano essere apportate per soddisfare i requisiti tecnici della dichiarazione. Il professore chiarisce anche la definizione di B di N e k, specificando come sia un limite superiore per qualsiasi ipotesi posta con un break point, e come sia una quantità puramente combinatoria. Il professore affronta quindi una domanda riguardante la dimostrazione di B di N e k, affermando che k non cambia riducendo x_N a x_N-1 poiché nessuna k colonna dell'insieme più piccolo può avere tutti i possibili modelli. Infine, il professore osserva che l'analisi e l'analisi VC sono applicabili alle funzioni binarie, sebbene possano essere estese a funzioni a valori reali.

  • 01:15:00 In questa sezione, il professore spiega come invece di addentrarsi in estensioni tecniche sull'apprendimento, preferirebbe utilizzare un approccio diverso, il compromesso bias-varianza, quando discute le funzioni di regressione. Chiarisce inoltre che l'apprendibilità è dimostrata in condizioni relative all'ipotesi impostata e che è indipendente dalla funzione target. Continua spiegando che la domanda di generalizzazione non dipende dalla funzione target, ma la questione se E_in possa essere minimizzata per rendere felice l'utente dipende dalla funzione target. Infine, il professore afferma che gli stessi principi si applicano a prescindere dal tipo di funzione.
Lecture 06 - Theory of Generalization
Lecture 06 - Theory of Generalization
  • 2012.04.21
  • www.youtube.com
Theory of Generalization - How an infinite model can learn from a finite sample. The most important theoretical result in machine learning. Lecture 6 of 18 o...
 

Lezione 07 - La dimensione VC




Corso di Machine Learning di Caltech - CS 156. Lezione 07 - La dimensione VC

La conferenza introduce il concetto di dimensione VC, che è il numero massimo di punti che possono essere infranti da un insieme di ipotesi, e ne spiega le applicazioni pratiche. La dimensione VC rappresenta i gradi di libertà di un modello e viene discussa la sua relazione con il numero di parametri in un modello. Vengono forniti esempi per dimostrare come calcolare la dimensione VC per diversi insiemi di ipotesi. Viene esplorata la relazione tra il numero di esempi necessari e la dimensione VC e si nota che esiste una relazione proporzionale tra i due. Vengono inoltre discusse le implicazioni dell'aumento della dimensione VC sulle prestazioni di un algoritmo di apprendimento. Nel complesso, la lezione fornisce approfondimenti sulla teoria VC e sulle sue implicazioni pratiche per l'apprendimento automatico.

Anche il video copre il concetto di generalizzazione e il limite di generalizzazione, che è un'affermazione positiva che mostra il compromesso tra la dimensione dell'insieme di ipotesi e una buona generalizzazione nell'apprendimento automatico. Il professore spiega la dimensione VC, che è il valore più grande prima del primo break point, e come può essere utilizzata per approssimare il numero di esempi necessari. Rileva l'importanza di scegliere la misura dell'errore corretta e chiarisce che la stima della dimensione VC è una stima approssimativa che può essere utilizzata per confrontare i modelli e approssimare il numero di esempi necessari. La conferenza si conclude evidenziando i punti in comune tra questo materiale e il tema della progettazione di esperimenti e come i principi dell'apprendimento si estendano ad altre situazioni al di là dei rigidi scenari di apprendimento.

  • 00:00:00 In questa sezione, il docente riassume il risultato principale della lezione precedente nella teoria dell'apprendimento, ovvero la disuguaglianza VC (Vapnik-Chervonenkis), che caratterizza la generalizzazione nell'apprendimento automatico. La funzione di crescita, che caratterizza la ridondanza necessaria per passare dalla disuguaglianza di Hoeffding alla disuguaglianza VC, è stata introdotta e correlata a eventi negativi con regioni sovrapposte. Il problema tecnico con E_out è stato risolto e la funzione di crescita è stata utilizzata per sostituire il numero di ipotesi M. La dimensione VC, che è correlata al punto di interruzione, viene quindi definita e calcolata esattamente per i percettroni in uno spazio a qualsiasi dimensione. Vengono discusse anche l'interpretazione della dimensione VC e le sue applicazioni pratiche.

  • 00:05:00 In questa sezione viene introdotto il concetto di dimensione VC come il numero massimo di punti che possono essere infranti da un insieme di ipotesi. La dimensione VC è indicata come d_VC ed è il valore più grande di N tale che la funzione di crescita è 2 alla N. È importante notare che la dimensione VC non garantisce che ogni N punti possa essere frantumato, ma solo che esistano N punti che possono essere frantumati. La sezione fornisce esempi, come i raggi positivi ei percettroni 2D, per dimostrare come calcolare la dimensione VC per un dato insieme di ipotesi. La dimensione VC viene utilizzata per delimitare la funzione di crescita di un insieme di ipotesi e funge da ordine del polinomio che delimita la funzione di crescita.

  • 00:10:00 In questa sezione, l'attenzione è rivolta alla dimensione VC degli insiemi convessi e alla sua relazione con l'apprendimento. La dimensione VC rappresenta il numero massimo di punti che possono essere infranti da un insieme di ipotesi. Se la dimensione VC è finita, l'ipotesi finale si generalizzerà, indipendentemente dalla distribuzione degli input o dall'algoritmo di apprendimento utilizzato. Il diagramma di apprendimento, che include la funzione target, l'algoritmo di apprendimento e la distribuzione degli input, mostra che la teoria VC è indipendente dall'algoritmo di apprendimento e dalla funzione target e dipende solo dall'insieme di ipotesi. Nel complesso, ci sono tre blocchi nella teoria VC: l'ipotesi, l'insieme di ipotesi e la dimensione VC.

  • 00:15:00 In questa sezione, apprendiamo la dimensione VC dei percettroni, che è l'insieme di ipotesi di cui si occupa l'intera teoria VC, poiché è l'insieme che ha la dimensione VC e ci dice se siamo in grado di generalizzare . Sebbene la dimensione VC dei percettroni nello spazio bidimensionale sia tre, una semplice formula afferma che nello spazio d-dimensionale, la dimensione VC è d più uno. Questo è importante per capire il significato della dimensione VC, e lo dimostreremo mostrando che la dimensione VC è al massimo d più uno e almeno d più uno. Per dimostrare, costruiremo un insieme specifico di N punti (N essendo d più uno) utilizzando una matrice da frantumare, purché sia possibile frantumarli.

  • 00:20:00 In questa sezione, il docente mostra un insieme specifico di punti d più 1 e dimostra che possono essere frantumati utilizzando una matrice invertibile. Quindi pone una domanda al pubblico sulla dimensione VC e chiede loro di scegliere quale conclusione possono trarre in base ai risultati della dimostrazione. La risposta corretta è b, che afferma che la dimensione VC è maggiore o uguale a d più 1.

  • 00:25:00 In questa sezione, il professore discute su come dimostrare che la dimensione VC è al massimo d più 1. Chiede al pubblico quale delle diverse affermazioni stabilirebbe la premessa e loro rispondono con "d". Il professore poi spiega che ha bisogno di dimostrare che esiste un insieme di d più 2 punti che non può frantumare.Lo fa mostrando che per un insieme di d più 2 punti, ci sarà sempre un punto che è una combinazione lineare degli altri. Pertanto, costruisce una dicotomia che mostra non può essere implementata con un perceptron.

  • 00:30:00 In questa sezione del video, l'oratore spiega il concetto di dicotomia in un percettrone, che consiste essenzialmente nell'assegnare etichette di +1 o -1 a punti specifici. Attraverso l'uso di proprietà algebriche, è dimostrato che è impossibile frantumare qualsiasi insieme di punti d più 2, con la dimensione VC che è d più 1. Ciò è dovuto al numero di parametri nel modello del percettrone, che è d più 1 e la dimensione VC fornisce il numero massimo di punti che possono essere frantumati.

  • 00:35:00 In questa sezione, la conferenza introduce il concetto di dimensione VC e la sua interpretazione. La dimensione VC è una misura dei gradi di libertà di un modello e di come si relaziona al numero di parametri che ha. La conferenza confronta questi gradi di libertà con le manopole di un sistema audio, dove più manopole possono darti un maggiore controllo sul suono, ma può essere difficile da usare in modo efficace. La conferenza spiega che la dimensione VC astrae i dettagli della matematica all'interno di un modello e si concentra sul suo potere espressivo. La conferenza discute anche la corrispondenza tra la dimensione VC ei gradi di libertà di vari modelli, come i raggi positivi, mostrando che la dimensione VC è uguale a uno quando c'è un grado di libertà, che corrisponde a un modello con un parametro.

  • 00:40:00 In questa sezione, il docente discute i gradi di libertà e la loro relazione con la dimensione VC nel contesto di modelli semplici. Mentre la dimensione VC conta il numero di ipotesi che possono essere raggiunte da un modello, non è necessariamente uguale al numero di parametri. Costruendo un esempio artificiale, il docente mostra che i parametri possono non sempre contribuire ai gradi di libertà. Invece, i gradi di libertà effettivi possono essere misurati in modo più affidabile dalla dimensione VC e il docente dimostra come un modello con otto parametri possa effettivamente avere la stessa dimensione VC di un modello con solo due parametri. Infine, il docente osserva che i professionisti potrebbero essere interessati al numero di punti dati necessari per un sistema e al modo in cui questo può essere correlato alla dimensione VC dell'insieme di ipotesi.

  • 00:45:00 In questa sezione, il relatore discute la relazione tra il numero di esempi necessari e il valore della dimensione VC. La disuguaglianza VC ha due piccole quantità di prestazioni che vogliono essere il più piccole possibile. Uno di questi è E_in non lontano da E_out, mentre l'altro è delta, che ha un valore piccolo. Dopo aver deciso su determinati valori epsilon e delta, il relatore spiega come determinare il numero di esempi necessari per raggiungerli osservando la funzione N alla potenza della dimensione VC per e alla potenza di -N tracciata su un grafico. La parte interessante della curva è dove la probabilità è inferiore a 1, e l'oratore esplora quindi le implicazioni dell'aumento della dimensione VC da 4 a 5.

  • 00:50:00 In questa sezione, il docente discute la relazione tra il numero di esempi in un set di dati e la dimensione VC, che è una misura della complessità di un algoritmo di apprendimento. Utilizza diversi grafici per illustrare come le prestazioni dell'algoritmo cambiano all'aumentare della dimensione VC e sottolinea che il numero di esempi necessari per raggiungere un certo livello di prestazioni è proporzionale alla dimensione VC. Tuttavia, osserva anche che mentre è garantito che i limiti della performance seguano una certa monotonia, la performance effettiva potrebbe non sempre farlo, il che può essere fonte di frustrazione per i professionisti.

  • 00:55:00 In questa sezione, il docente discute osservazioni e applicazioni pratiche della dimensione VC. La prima lezione è che esiste una relazione proporzionale tra la dimensione VC e il numero di esempi necessari per raggiungere un certo livello di performance. Il docente fornisce una regola empirica in cui è necessario 10 volte la dimensione VC per raggiungere la zona di comfort della disuguaglianza VC in cui l'affermazione di probabilità è significativa. La seconda osservazione pratica è che per una vasta gamma di ragionevoli epsilon e delta, vale anche la regola empirica. Il docente quindi semplifica la formula di disuguaglianza VC e la chiama formula maiuscola Omega, affermando che dipende dalla funzione di crescita e che all'aumentare della dimensione VC, la formula Omega peggiora.
  • 01:00:00 In questa sezione, il relatore discute il concetto di generalizzazione e come avere più esempi può influenzare la funzione di crescita e il comportamento del polinomio. Introduce l'idea del limite di generalizzazione, che è un'affermazione positiva invece di caratterizzare eventi negativi. Con probabilità maggiore o uguale a 1 meno delta, E_in traccia E_out, il che significa che sono all'interno di Omega, che dipende dal numero di esempi e dalla dimensione VC dell'insieme di ipotesi. L'oratore semplifica la generalizzazione vincolata riorganizzandola per mostrare che E_out è delimitato da E_in più Omega. Spiega come questo limite illustri il compromesso tra la dimensione dell'insieme di ipotesi e una buona generalizzazione, portando al concetto di regolarizzazione nell'apprendimento automatico.

  • 01:05:00 In questa sezione, il professore spiega che la dimensione VC è il valore più grande appena prima del primo punto di interruzione, il che significa che verrà conteggiato anche qualsiasi punto più grande che funge da punto di interruzione. La nozione di punto di interruzione copre molti valori, ma la dimensione VC è quella unica che spicca. Chiarisce anche che quando si discute di frantumare N punti, le persone possono scegliere i punti da frantumare. Il professore spiega che epsilon e delta sono due parametri di prestazione dell'apprendimento, dove epsilon è il parametro di approssimazione che garantisce che E_in tenga traccia di E_out, mentre delta è la misura di probabilità che determina la probabilità che l'affermazione di probabilità fallisca. Alla domanda sull'effetto della misura dell'errore sul numero di punti da scegliere, il professore spiega che quando si ha a che fare con la misura dell'errore in senso binario, non c'è bisogno di preoccuparsi della varianza perché c'è un limite superiore, ma quando si usano altri co-domini o misure di errore, sono necessarie modifiche.

  • 01:10:00 In questa sezione, il professore spiega che ottenere esattamente la dimensione VC è raro, ma conoscono la dimensione esatta per i percettroni. Quando si tratta di reti neurali, la stima della dimensione VC non può essere superiore a un certo numero a causa di ridondanze e cancellazioni. Il professore sottolinea che il limite della dimensione VC è una stima vaga, ma mantiene ancora il suo significato concettuale e può essere utilizzato come guida per confrontare i modelli e approssimare il numero di esempi necessari. La regola empirica consiste nell'utilizzare almeno 10 volte la dimensione VC per entrare nella regione interessante della disuguaglianza VC, che dipende dal livello di accuratezza desiderato dal cliente. Il professore osserva che ci sono punti in comune tra questo materiale e l'argomento della progettazione degli esperimenti, e i principi dell'apprendimento si estendono ad altre situazioni oltre i rigorosi scenari di apprendimento.
Lecture 07 - The VC Dimension
Lecture 07 - The VC Dimension
  • 2012.04.26
  • www.youtube.com
The VC Dimension - A measure of what it takes a model to learn. Relationship to the number of parameters and degrees of freedom. Lecture 7 of 18 of Caltech's...
 

Lezione 8 - Tradeoff Bias-Variance



Corso di Machine Learning di Caltech - CS 156. Lezione 08 - Bias-Variance Tradeoff

Il professore discute il compromesso bias-varianza nell'apprendimento automatico, spiegando come la complessità dell'insieme di ipotesi influisca sul compromesso tra generalizzazione e approssimazione. Il docente introduce il concetto di distorsione e varianza, che misurano la deviazione tra la media delle ipotesi prodotte da un algoritmo di apprendimento automatico e la funzione target effettiva e quanto varia la distribuzione delle ipotesi di un dato modello in base a diversi set di dati, rispettivamente. Il compromesso si traduce in un insieme di ipotesi più ampio con un pregiudizio minore ma una varianza maggiore, mentre un insieme di ipotesi più piccolo avrà un pregiudizio maggiore ma una varianza minore. Il docente sottolinea l'importanza di disporre di risorse di dati sufficienti per navigare efficacemente nell'insieme di ipotesi ed evidenzia la differenza di scala tra l'analisi della varianza di bias e l'analisi VC.

Inoltre discute il compromesso tra modelli semplici e complessi in termini di capacità di approssimazione e generalizzazione, con meno esempi che richiedono modelli semplici e maggiori risorse di esempi che richiedono modelli più complessi. L'analisi bias-variance è specifica per la regressione lineare e presuppone la conoscenza della funzione target, con la convalida come gold standard per la scelta di un modello. L'apprendimento dell'ensemble viene discusso tramite Bagging, che utilizza il bootstrap per calcolare la media di più set di dati, riducendo la varianza. Viene anche spiegato l'equilibrio tra varianza e covarianza nell'apprendimento dell'insieme e la regressione lineare è classificata come una tecnica di apprendimento con l'adattamento come prima parte dell'apprendimento, mentre la teoria enfatizza le buone prestazioni fuori campione.

  • 00:00:00 In questa sezione, l'attenzione si sposta sul compromesso bias-varianza, che è un altro approccio alla comprensione della generalizzazione. Nelle lezioni precedenti, l'analisi VC ha stabilito la capacità di generalizzazione di un'ipotesi scelta, attraverso la dimensione VC di un insieme di ipotesi. Il limite VC vale per qualsiasi algoritmo di apprendimento, per qualsiasi dato di input e per qualsiasi funzione target. Un aspetto dell'analisi VC è che fornisce una misura pratica. Tracciando la probabilità di errore rispetto al numero di esempi, abbiamo scoperto che il numero di esempi necessari è proporzionale alla dimensione VC, o regola empirica, è necessario 10 volte la dimensione VC per iniziare a ottenere interessanti proprietà di generalizzazione. Infine, abbiamo riassunto l'analisi VC in un limite di generalizzazione, che utilizzeremo in tecniche successive come la regolarizzazione.

  • 00:05:00 In questa sezione, il docente discute il compromesso tra approssimazione e generalizzazione quando si tratta di apprendimento. L'apprendimento mira a ottenere un piccolo E_out, il che significa che l'ipotesi approssima bene la funzione target e che questa approssimazione è fuori campione. Tuttavia, avere un insieme di ipotesi più complesso aumenta la possibilità di approssimare bene f ma crea un problema nell'identificare l'ipotesi adatta. Un'ipotesi ideale impostata per l'apprendimento è un'ipotesi singleton che risulta essere la funzione target. Tuttavia, poiché non conosciamo la funzione obiettivo, abbiamo bisogno di un insieme di ipotesi sufficientemente ampio da avere una possibilità. Inoltre, il docente discute di come anche l'analisi di bias-varianza decompone E_out, mentre l'analisi VC enfatizza la quantificazione del compromesso.

  • 00:10:00 In questa sezione, il relatore introduce il compromesso bias-varianza e come si relaziona alle funzioni a valori reali e alla regressione usando l'errore al quadrato. L'obiettivo è scomporre l'errore fuori campione in due componenti concettuali: approssimazione e generalizzazione. Per fare ciò, il relatore utilizza il valore atteso dell'errore rispetto a un particolare set di dati poiché l'ipotesi finale dipende dal set di dati utilizzato, ma mira a rimuovere la dipendenza integrando il set di dati. Il risultato è un modo per analizzare il comportamento generale dell'errore quando viene fornito un numero specifico di punti dati con cui lavorare.

  • 00:15:00 In questa sezione il docente spiega come calcolare i valori attesi di un comportamento rispetto a tutte le possibili realizzazioni di 100 esempi. Invertendo l'ordine dell'integrazione e liberandosi di un'aspettativa, il conferenziere arriva a una scomposizione netta. Il passaggio successivo prevede la derivazione di un'ipotesi media ottenendo il valore atteso di tutte le possibili ipotesi. Anche se questo è certamente un compito impossibile, fornisce uno strumento concettuale per l'analisi. Comprendere l'utilità tecnica di g bar diventa importante quando si espande l'espressione superiore per ottenere un termine lineare che alla fine richiede la definizione di g bar.

  • 00:20:00 In questa sezione, il docente scompone una quantità in due passaggi che determinano quanto l'ipotesi che un algoritmo di apprendimento automatico deriva da un dato set di dati diverge dalla funzione target. Il primo passaggio valuta fino a che punto questa ipotesi devia dalla migliore ipotesi che l'algoritmo può produrre dato il set di dati dato, mentre il secondo passaggio valuta quanto questa migliore ipotesi devia dalla funzione target effettiva. Il docente arriva a due quantità, il bias e la varianza, per denotare questi due passi. Il bias misura la deviazione tra la media delle ipotesi prodotte da un algoritmo di apprendimento automatico e la funzione target effettiva, che imposta un valore finito per il set di ipotesi dell'algoritmo. Nel frattempo, la varianza misura quanto varia la distribuzione delle ipotesi di un dato modello in base a diversi set di dati.

  • 00:25:00 In questa sezione, il professore discute il compromesso tra bias e varianza nell'apprendimento automatico. Spiega che il bias è la limitazione del set di ipotesi e la varianza è la differenza di risultato quando si utilizzano set di dati diversi. Quindi mostra come esiste un compromesso tra generalizzazione e approssimazione quando si modifica la dimensione dell'insieme di ipotesi e illustra questa idea con un confronto tra un insieme di ipotesi piccolo e grande. Sostiene che un insieme di ipotesi più ampio avrà un pregiudizio minore ma una varianza maggiore, mentre un insieme di ipotesi più piccolo avrà un pregiudizio maggiore ma una varianza minore.

  • 00:30:00 In questa sezione, il relatore introduce il concetto di compromesso bias-variance, in cui il bias diminuisce e la varianza aumenta man mano che l'insieme di ipotesi diventa più grande. Per capirlo, il relatore fa un esempio concreto in cui la funzione target è una sinusoide e vengono forniti due diversi insiemi di ipotesi: un modello costante e un modello lineare. Il relatore mostra quindi che il modello lineare fornisce una migliore approssimazione della sinusoide, ma con alcuni errori. Questa non è una situazione di apprendimento, ma illustra il compromesso tra bias e varianza nell'approssimazione della funzione target, aprendo la strada a problemi di apprendimento più complessi.

  • 00:35:00 In questa sezione, il docente spiega il compromesso tra bias e varianza nell'apprendimento automatico. Usa l'esempio dell'adattamento di una linea a due punti, prima per approssimare una funzione target e poi per imparare dagli esempi. L'analisi bias-variance è necessaria per valutare le prestazioni di un modello indipendentemente da quali due punti vengono utilizzati e per superare le sfide di far fronte alla dipendenza dal set di dati. Il docente quindi genera set di dati di dimensioni pari a due punti, vi adatta una linea e mostra che l'errore previsto fuori campione è principalmente la somma di bias e varianza. La linea verde molto chiara, g barra di x, è l'ipotesi media che ottiene ripetendo questo gioco. Tuttavia, non è il risultato del processo di apprendimento perché set di dati diversi forniranno stime diverse.

  • 00:40:00 In questa sezione del video, il concetto di compromesso tra bias e varianza viene discusso nel contesto dell'apprendimento automatico. La varianza è calcolata come la deviazione standard dell'output del processo di apprendimento, mentre il bias è l'errore tra l'output previsto e la funzione target. Il compromesso tra bias e varianza è dimostrato utilizzando due modelli, uno con un piccolo bias e una grande varianza e l'altro con un grande bias e una piccola varianza. Resta inteso che in una situazione di apprendimento, la complessità del modello dovrebbe essere abbinata alle risorse di dati disponibili piuttosto che alla complessità dell'obiettivo.

  • 00:45:00 In questa sezione, il relatore discute il compromesso tra bias e varianza nell'apprendimento e introduce il concetto di curve di apprendimento. Le curve di apprendimento tracciano i valori attesi di E_out (errore fuori campione) e E_in (errore nel campione) in funzione di N, la dimensione del set di dati. All'aumentare di N, l'errore fuori campione generalmente diminuisce, ma questa tendenza può essere influenzata dalla complessità del modello utilizzato. Il relatore sottolinea l'importanza di disporre di risorse di dati sufficienti per navigare efficacemente nell'insieme di ipotesi e osserva che i dati rumorosi possono rendere questa navigazione ancora più difficile. Le curve di apprendimento forniscono una rappresentazione visiva del compromesso bias-varianza e di come cambia con l'aumentare di N.

  • 00:50:00 In questa sezione, il docente discute la relazione tra l'analisi bias-variance e l'analisi VC utilizzando le curve di apprendimento. Spiega che entrambe le teorie discutono di approssimazione e prendono in considerazione ciò che accade in termini di generalizzazione. Il docente evidenzia la differenza di scala tra le due teorie e afferma che il bias dipende dall'ipotesi impostata. Infine, il docente copre brevemente l'analisi per il caso di regressione lineare e lo raccomanda come un buon esercizio per ottenere informazioni sulla regressione lineare.

  • 00:55:00 In questa sezione, l'istruttore descrive il modello di errore nel campione e il modello di errore fuori campione, in particolare utilizzando le curve di apprendimento. L'istruttore utilizza la regressione lineare e il rumore per illustrare una semplice formula per l'errore previsto nel campione: è quasi perfetto e stai andando meglio che perfetto per il rapporto di d più 1. L'istruttore sottolinea una curva molto specifica, che mostra che più punti dati hai, meno rumore influirà sul tasso di errore. Tuttavia, quando ti adatti eccessivamente ai dati del campione, finisci per adattare il rumore e questo ti danneggerà invece di aiutarti a lungo termine.

  • 01:00:00 In questa sezione, il professore parla del compromesso tra modelli semplici e complessi e della loro capacità di approssimazione e generalizzazione. Mentre i modelli complessi possono approssimare meglio la funzione target e gli esempi di addestramento, i modelli semplici sono migliori in termini di capacità di generalizzazione. Questo perché c'è un compromesso tra i due e la somma di entrambe le quantità potrebbe andare in entrambe le direzioni. La chiave è abbinare la complessità del modello alle risorse di dati disponibili. Meno esempi significano che dovrebbero essere usati modelli semplici, mentre maggiori risorse di esempi richiedono modelli complessi per prestazioni migliori. L'errore di generalizzazione atteso può essere trovato utilizzando la formula, che è la dimensione VC divisa per il numero di esempi.

  • 01:05:00 In questa sezione, il professore discute di come l'analisi bias-variance sia specifica della regressione lineare e di come presupponga che tu conosca la funzione target. Sebbene sia una guida utile e possa essere utilizzata per capire come influenzare sia il bias che la varianza, non è qualcosa che può essere collegato per dirti qual è il modello. Afferma inoltre che il gold standard per la scelta di un modello è attraverso la convalida, che include metodi di insieme come il potenziamento. Il professore introduce quindi brevemente l'idea di g bar come strumento teorico per l'analisi, ma osserva che non è il fulcro di questa lezione.

  • 01:10:00 In questa sezione, il professore parla dell'apprendimento dell'ensemble tramite Bagging, che è il processo di utilizzo di un set di dati per generare un gran numero di set di dati diversi attraverso il bootstrap e la media. Ciò fornisce alcuni dividendi sull'apprendimento dell'insieme e può aiutare a ridurre la varianza calcolando la media di molte cose. Il moderatore chiede quindi se la varianza di bias appare ancora attraverso l'approccio bayesiano. Il professore spiega che sebbene l'approccio bayesiano faccia certe ipotesi, la varianza di bias esiste ancora. Infine, parla della relazione dell'approssimazione di funzioni numeriche con l'estrapolazione nell'apprendimento automatico e del dilemma bias-variance covariance.

  • 01:15:00 In questa sezione della lezione, il professore discute l'equilibrio tra varianza e covarianza nel contesto dell'apprendimento d'insieme. Spiega che nell'analisi della varianza di bias, ha avuto il lusso di scegliere set di dati generati in modo indipendente, generare modelli indipendenti e quindi calcolarne la media. Tuttavia, nella pratica reale, quando si costruiscono modelli basati su variazioni del set di dati, la covarianza tra i modelli inizia a svolgere un ruolo. Successivamente, quando gli viene chiesto se la regressione lineare è una tecnica di apprendimento o solo un'approssimazione di funzioni, il professore afferma che la regressione lineare è una tecnica di apprendimento e l'adattamento è la prima parte dell'apprendimento. L'elemento aggiunto è garantire che il modello funzioni bene fuori dal campione, che è ciò di cui tratta la teoria.
Lecture 08 - Bias-Variance Tradeoff
Lecture 08 - Bias-Variance Tradeoff
  • 2012.04.28
  • www.youtube.com
Bias-Variance Tradeoff - Breaking down the learning performance into competing quantities. The learning curves. Lecture 8 of 18 of Caltech's Machine Learning...
 

Lecture 9 - The Linear Model II



Caltech's Machine Learning Course - CS 156. Lecture 09 - The Linear Model II

This lecture covers various aspects of the linear model, including the bias-variance decomposition, learning curves, and techniques for linear models such as perceptrons, linear regression, and logistic regression. The speaker emphasizes the tradeoff between complexity and generalization performance, cautioning against overfitting and emphasizing the importance of properly charging the VC dimension of the hypothesis space for valid warranties. The use of nonlinear transforms and their impact on generalization behavior is also discussed. The lecture further covers the logistic function and its applications in estimating probabilities, and introduces the concepts of likelihood and cross-entropy error measures in the context of logistic regression. Finally, iterative methods for optimizing the error function, such as gradient descent, are explained.

Also the lecture covers a range of topics related to linear models and optimization algorithms in machine learning. The professor explains the compromise between learning rate and speed in gradient descent optimization, introducing the logistic regression algorithm and discussing its error measures and learning algorithm. The challenges of termination in gradient descent and multi-class classification are also addressed. The role of derivation and selection of features in machine learning is emphasized and discussed as an art in application domains, charged in terms of VC dimension. Overall, this lecture provides a comprehensive overview of linear models and optimization algorithms for machine learning.

  • 00:00:00 In this section, Yaser Abu-Mostafa discusses the bias-variance decomposition in the out-of-sample error and illustrates how it trades off with the hypothesis set. He also explains learning curves, which describes the generalization error, and how the number of examples, proportional to the VC dimension, will determine generalization properties. Techniques for linear models are also discussed.

  • 00:05:00 In this section of the lecture, the speaker briefly recaps the linear model in terms of linear classification and linear regression, which have been covered in previous lectures, and then moves to the third type of linear model - logistic regression. Before starting on logistic regression, the speaker ties up the loose ends in terms of nonlinear transforms and generalization issues. Nonlinear transforms offer a platform for applying learning algorithms in the Z space (feature space), with the final hypothesis still residing in the X space (input space). In the case of nonlinear transforms, the speaker emphasizes that the generalization issues were left out and that he will provide the missing piece in the lecture.

  • 00:10:00 In this section, the lecturer discusses the price that one pays for doing nonlinear transformations when it comes to generalization behavior in the X space. By using the linear model in the X space, you can get a weight vector of d+1 free parameters. However, the VC dimension in the feature space may potentially be much larger than that of the X space. If the VC dimension is too large, then although it is possible to fit the 17th-order polynomial, there is no real chance of generalization. Two cases are discussed where the first case is almost linearly separable, and the second case is genuinely nonlinear. In order to get E_in to be zero, one has to go to a high-dimensional space, which becomes a problem as there are only two points to classify.

  • 00:15:00 In this section of the lecture, the instructor discusses the approximation-generalization tradeoff when dealing with linear models. He talks about how using a more complex model, such as a fourth-order surface, can better approximate the data but may not generalize well. He also mentions the idea of using a transformation to a non-linear space, but cautions against seeking a discount in the number of parameters. The instructor explains that charging the VC dimension of the entire hypothesis space explored in the mind is important in order for the warranty provided by the VC inequality to be valid.

  • 00:20:00 In this section, the discussion is centered around the dangers of data snooping when choosing a model before looking at the data. It is emphasized that this practice can lead to a contaminated hypothesis set, meaning that the data is no longer trustworthy for reflecting real-world performance. The concept of logistic regression is introduced, along with its unique model, error measure, and learning algorithm. This linear model is considered to be a significant complement to the perceptron and linear regression models previously discussed, and provides a useful example of the complexities and variations that exist within machine learning.

  • 00:25:00 In this section, the lecturer discusses the linear model and the different ways it can be used, such as perceptrons, linear regression, and logistic regression. For linear classification, the hypothesis is a decision of +1 or -1, which is a direct thresholding of the signal. In the case of linear regression, the output is the same as the input, while logistic regression applies a nonlinearity called the logistic function to the signal, which is interpreted as a probability of something happening. The lecturer explains the shape of the logistic function and its applications in estimating probabilities for various problems, such as credit card applications.

  • 00:30:00 In this section, the concept of a soft threshold or sigmoid is introduced in the context of the logistic function. This function takes a linear signal as input and outputs a probability. It is particularly useful in predicting outcomes like the risk of a heart attack, where multiple factors contribute to the likelihood of an event occurring. The output of the logistic regression is treated as a genuine probability during the learning process, even though the input data does not directly provide that information.

  • 00:35:00 In this section, we discuss supervised learning in medical data and how to generate a model that approximates a hidden target function. The examples are given as binary output, which is affected by a probability, making this a noisy case. The target is from the d-dimensional Euclidean space to 0,1 with a probability interpretation, f of x. The hypothesis g of x is found by finding the weights and dot-producting them with x. The objective is to choose the weights in such a way that the logistic regression hypothesis reflects the target function using an error measure constructed by likelihood that is both plausible and friendly to the optimizer. The error measure grades different hypotheses according to the likelihood that they are actually the target that generated the data.

  • 00:40:00 In this section of the lecture, the speaker discusses the use of likelihood and the controversy around its application. He explains that the use of likelihood is to find the most plausible hypothesis given the data. However, it is not a completely clean process as likelihood is not the probability that is required. The speaker then introduces a formula for likelihood and explains how it can be used to derive a full-fledged error measure. The formula is then used to find the likelihood of an entire dataset, which is a product of the likelihoods of individual data points. He concludes that there will always be a compromise when choosing a hypothesis, as favoring one example may mess up the others.

  • 00:45:00 In this section of the lecture, the speaker explains how maximizing the likelihood of a hypothesis under a dataset can lead to minimizing the error measure. Taking the natural logarithm allows the maximization to become a minimization, which results in an error measure in the training set. After simplifying the formula, the speaker calls the error measure the in-sample error of logistic regression, and he defines it as the error measure between the hypothesis that depends on w, applied to x_n, and the value given as a label for that example, which is y_n. The speaker also discusses the interesting interpretation of the risk score, which identifies those at risk of heart attacks based on the sign of w transposed x_n.

  • 00:50:00 In this section, the cross-entropy error measure is introduced as a way to measure the accuracy of binary predictions. The goal is to minimize this error measure in order to improve the model's predictions. However, unlike linear regression, there is no closed-form solution to minimize the error measure for logistic regression. Instead, an iterative solution is needed, which will be achieved through the gradient descent method. This method involves taking a step along the steepest slope of the surface and repeating until the minimum is reached. The convexity of the error measure for logistic regression makes gradient descent a good choice for optimization.

  • 00:55:00 In this section of the lecture, the professor discusses the iterative methods used to find the minimum value of the error function in the linear model. He explains that these methods involve moving along the surface in small steps and making local approximations using calculus, specifically Taylor series. He then introduces the concept of gradient descent, where the next weight is determined by the current weight plus the move in a specific direction, which is determined by solving for the unit vector in the direction of steepest descent. The professor goes on to explain how the direction that achieves the most negative value for the inner product between a vector and a unit vector is chosen as the direction of movement.

  • 01:00:00 In this section, the lecturer discusses the compromise between the size of the step, or learning rate, in gradient descent optimization. Taking very small steps will eventually get to the minimum, but it would take forever, while taking bigger steps would be faster but may not apply linear approximation. After analyzing the graphs, the best compromise is to have initially a large learning rate to take advantage of steep slopes and become more careful when closer to the minimum to avoid overshooting. The lecturer then presents the formula for a fixed learning rate, where the learning rate is proportional to the size of the gradient. The logistic regression algorithm is then introduced, where the gradient is computed using the in-sample error formula, and the next weight is obtained by subtracting the learning rate times the gradient from the current weight. Finally, all three linear models, perceptron, linear regression, and logistic regression, are summarized in one slide and applied to the credit domain.

  • 01:05:00 In this section, the professor discusses the different types of linear models that can be implemented in credit analysis and the corresponding error measures and learning algorithms used. For example, the perceptron is used for binary classification and logistic regression is used to compute the probability of default. Different error measures were used for each model, such as binary classification error for the perceptron and cross-entropy error for logistic regression. The learning algorithm used was dependent on the error measure chosen, such as the perceptron learning algorithm for classification error and gradient descent for cross-entropy error. Lastly, the professor briefly discusses termination criteria and issues that arise with termination in gradient descent as a properly analyzed termination is a bit tricky due to many unknowns in the error surface.

  • 01:10:00 In this section, the speaker explains that gradient descent is an effective but not foolproof optimization algorithm. If the surface that the optimization algorithm is trying to navigate has multiple local minima, the algorithm might only find a local minimum instead of a global minimum that gives the best result. The speaker suggests using a combination of criteria to terminate the optimization algorithm and notes that the conjugate gradient is a valid alternative to gradient descent. The speaker suggests that if local minima become a real issue in an application, there are many approaches in the field of optimization to tackle this problem.

  • 01:15:00 In this section, the professor explains the concept of cross-entropy, which is a way of getting a relationship between two probability distributions using logarithmic and expected values. The professor also discusses the limitations of binary search and 2nd-order methods in optimization, emphasizing that while more sophisticated methods may lead to better results, they may be too expensive in terms of CPU cycles. Finally, in response to a question, the professor confirms that logistic regression can be applied to a multi-class setting, as demonstrated in the example of recognizing digits.

  • 01:20:00 In this section of the lecture, the professor discusses various methods for multi-class classification, including ordinal regression and tree-based binary decisions. The professor also introduces the use of the tanh function, which will be used as the neuronal function in neural networks. The concept of the learning rate is also discussed, with the professor mentioning that there are heuristics for adaptive learning rates that can be used, and a rule of thumb for choosing the learning rate is presented. Additionally, the distinction between meaningful features and features derived from looking at the specific data set is made, with the former being less likely to forfeit the VC warranty.

  • 01:25:00 In this section, the professor discusses the process of deriving features in machine learning and emphasizes that it is an art that depends on the application domain. While it is possible to derive features based on the data, the final hypothesis set will still determine the generalization behavior. The professor also notes that selecting features is automatically done in machine learning, but it becomes part of learning and is charged in terms of VC dimension. The topic of selecting features will be further addressed in the future lecture on neural networks and hidden layers.
Lecture 09 - The Linear Model II
Lecture 09 - The Linear Model II
  • 2012.05.02
  • www.youtube.com
The Linear Model II - More about linear models. Logistic regression, maximum likelihood, and gradient descent. Lecture 9 of 18 of Caltech's Machine Learning ...
 

Lezione 10 - Reti Neurali



Corso di apprendimento automatico di Caltech - CS 156. Lezione 10 - Reti neurali

Yaser Abu-Mostafa, professore al California Institute of Technology, discute la regressione logistica e le reti neurali in questa conferenza. La regressione logistica è un modello lineare che calcola un'interpretazione probabilistica di una funzione a valori reali limitata. Non è in grado di ottimizzare direttamente la misura dell'errore, quindi viene introdotto il metodo della discesa del gradiente per ridurre al minimo una funzione non lineare arbitraria che sia sufficientemente uniforme e differenziabile due volte. Sebbene non esista una soluzione in forma chiusa, la misura dell'errore è una funzione convessa, che rende relativamente facile l'ottimizzazione utilizzando la discesa del gradiente.

La discesa del gradiente stocastico è un'estensione della discesa del gradiente utilizzata nelle reti neurali. Le reti neurali sono un modello che implementa un'ipotesi motivata da un punto di vista biologico e relativa ai percettroni. L'algoritmo di backpropagation è un algoritmo efficiente che va con le reti neurali e rende il modello particolarmente pratico. Il modello ha un collegamento biologico che ha entusiasmato le persone ed è stato facile da implementare utilizzando l'algoritmo. Sebbene non sia il modello di scelta al giorno d'oggi, le reti neurali hanno avuto successo nelle applicazioni pratiche e sono ancora utilizzate come standard in molti settori, come quello bancario e l'approvazione del credito.

Breve riassunto:

  • La regressione logistica è un modello lineare che calcola un'interpretazione probabilistica di una funzione a valori reali limitata;
  • Il metodo della discesa del gradiente viene introdotto per ottimizzare la regressione logistica, ma non è in grado di ottimizzare direttamente la sua misura dell'errore;
  • La discesa del gradiente stocastico è un'estensione della discesa del gradiente utilizzata nelle reti neurali;
  • Le reti neurali sono un modello che implementa un'ipotesi motivata da un punto di vista biologico e relativa ai percettroni;
  • L'algoritmo di backpropagation è un algoritmo efficiente che si accompagna alle reti neurali e rende il modello particolarmente pratico;
  • Sebbene le reti neurali non siano il modello di scelta al giorno d'oggi, sono ancora utilizzate come standard in molti settori, come quello bancario e l'approvazione del credito.
Lecture 10 - Neural Networks
Lecture 10 - Neural Networks
  • 2012.05.06
  • www.youtube.com
Neural Networks - A biologically inspired model. The efficient backpropagation learning algorithm. Hidden layers. Lecture 10 of 18 of Caltech's Machine Learn...
 

Lezione 11 - Overfitting



Corso di Machine Learning di Caltech - CS 156. Lezione 11 - Overfitting

Questa lezione introduce il concetto e l'importanza dell'overfitting nell'apprendimento automatico. L'overfitting si verifica quando un modello viene addestrato sul rumore anziché sul segnale, con conseguente scarso adattamento fuori campione. La conferenza include vari esperimenti per illustrare gli effetti di diversi parametri, come il livello di rumore e la complessità del target, sull'overfitting. Il docente sottolinea l'importanza di individuare precocemente l'overfitting e l'uso di tecniche di regolarizzazione e validazione per prevenirlo. Viene anche discusso l'impatto del rumore deterministico e stocastico sull'overfitting e la lezione si conclude introducendo le due lezioni successive sull'evitare l'overfitting attraverso la regolarizzazione e la convalida.

Viene discusso il concetto di overfitting e viene sottolineata l'importanza della regolarizzazione per prevenirlo. Il professore evidenzia il compromesso tra overfitting e underfitting e spiega il ruolo della dimensione VC nell'overfitting, dove la discrepanza nella dimensione VC dato lo stesso numero di esempi si traduce in discrepanze nell'errore fuori campione e all'interno del campione. Viene trattata anche la questione pratica della convalida di un modello e di come può influire sull'overfitting e sulla selezione del modello. Inoltre, il professore sottolinea il ruolo delle funzioni lineari a tratti nella prevenzione dell'overfitting e sottolinea l'importanza di considerare il numero di gradi di libertà nel modello e di restringerlo attraverso la regolarizzazione.

  • 00:00:00 In questa sezione, il docente introduce il tema dell'overfitting nell'apprendimento automatico e la sua importanza, osservando che la capacità di affrontare l'overfitting separa i professionisti dai dilettanti nel settore. Il principale responsabile dell'overfitting è identificato come rumore e il docente introduce il concetto di regolarizzazione e validazione come tecniche per affrontare l'overfitting. La sezione funge da introduzione a un nuovo argomento che sarà trattato nelle prossime tre lezioni.

  • 00:05:00 In questa sezione, il docente spiega il concetto di overfitting mostrando come può verificarsi quando si adatta un polinomio di 4° ordine a una funzione target di 2° ordine con rumore aggiunto. Ciò si traduce in zero errori di addestramento e scarso adattamento fuori campione, che è un classico esempio di overfitting, in cui il modello è andato oltre il necessario. Questo punto viene ulteriormente enfatizzato quando si parla di overfitting nelle reti neurali, poiché E_in scende durante l'addestramento mentre E_out rimane alto. Il docente osserva inoltre che l'overfitting è un termine comparativo, poiché deve esserci un'altra situazione migliore e l'overfitting può verificarsi all'interno dello stesso modello.

  • 00:10:00 In questa sezione, il professor Abu-Mostafa discute l'overfitting, che si verifica quando E_in viene abbassato, ma E_out aumenta a causa dell'adattamento del rumore anziché del segnale. Spiega che la dimensione effettiva del VC cresce con il tempo, ma l'errore di generalizzazione peggiora sempre di più all'aumentare del numero di parametri. L'overfitting può verificarsi quando vengono confrontati due diversi modelli o istanze all'interno dello stesso modello. Un modo per risolvere questo problema è rilevare l'overfitting utilizzando l'algoritmo di arresto anticipato, basato sulla convalida, che funge da regolarizzazione per prevenire l'overfitting. Per evitare di adattare il rumore quando si verifica l'overfitting, è importante rilevarlo in anticipo e interromperlo piuttosto che continuare a ridurre al minimo E_in.

  • 00:15:00 In questa sezione, il docente discute di come può verificarsi l'overfitting a causa della presenza di rumore nei dati. Viene presentato un caso di studio con due diversi modelli: uno con un target rumoroso di ordine basso e un altro con un target silenzioso di ordine elevato. Per adattare i dati vengono utilizzati un polinomio di secondo ordine e un polinomio di decimo ordine. Per l'adattamento del secondo ordine, l'errore nel campione è 0,05 e l'errore fuori campione è leggermente superiore. Al contrario, l'adattamento del 10° ordine presenta un problema, con l'errore nel campione inferiore a quello dell'adattamento del 2° ordine. Tuttavia, l'errore fuori campione aumenta notevolmente, indicando un caso di overfitting in cui il rumore è stato adattato al modello.

  • 00:20:00 In questa sezione, il docente discute l'overfitting e come può verificarsi anche in situazioni silenziose quando il modello si adatta a un altro tipo di rumore. Fornisce un esempio di adattamento di un modello del 10° ordine a un target rumoroso del 10° ordine e di come ciò abbia portato all'overfitting. Quindi, mostra che abbinando la complessità del modello alle risorse di dati piuttosto che alla complessità di destinazione, è possibile ottenere prestazioni migliori nonostante si disponga di un modello più semplice. Il docente sottolinea che i problemi di generalizzazione dipendono dalla dimensione e dalla qualità del set di dati e che semplicemente abbinare la complessità del modello alla funzione target non è sempre l'approccio migliore.

  • 00:25:00 In questa sezione viene esplorato il concetto di overfitting nell'apprendimento automatico. La lezione utilizza le curve di apprendimento per dimostrare come l'errore nel campione per un modello più complesso sia minore, ma l'errore fuori campione sia maggiore, definendo l'area grigia in cui si verifica l'overfitting. La lezione mostra anche un esperimento con due studenti, uno che sceglie un 10° ordine e l'altro che sceglie un 2° ordine per adattarsi a un obiettivo del 50° ordine senza rumore. Nonostante l'assenza di rumore, entrambi gli studenti sperimentano ancora l'overfitting, che porta alla definizione di rumore effettivo e alla necessità di cautela nei problemi di machine learning del mondo reale. La conferenza conclude che l'overfitting si verifica nella maggior parte dei casi, sottolineando l'importanza di comprendere e affrontare questo problema.

  • 00:30:00 In questa sezione, il docente discute i parametri che influenzano l'overfitting, inclusi il livello di rumore, la complessità del target e il numero di punti dati. Per creare interessanti funzioni target ad alta complessità, il docente utilizza un set standard di polinomi di Legendre con coefficienti specifici tra loro ortogonali. Normalizzando il segnale a un'energia di 1, il docente può affermare che sigma al quadrato è la quantità di rumore. Durante la generazione di istanze dell'esperimento, il docente utilizza diverse combinazioni di rumore, complessità target e numero di punti dati per osservare la persistenza dell'overfitting.

  • 00:35:00 In questa sezione, il docente discute un metodo di misurazione dell'overfitting che confronta gli errori fuori campione di due diversi modelli: un polinomio di 2° ordine e un polinomio di 10° ordine. La misura è la differenza tra l'errore fuori campione per il modello complesso e l'errore fuori campione per il modello semplice. Se l'errore fuori campione del modello complesso è maggiore, rendendo la misura positiva, allora c'è un overfitting. Il docente mostra quindi come cambia la misura dell'overfitting al variare dei livelli di rumore e della complessità del target. All'aumentare del livello di rumore e della complessità dell'obiettivo, l'overfitting peggiora. Il docente osserva inoltre che l'overfitting è un problema significativo e deve essere affrontato.

  • 00:40:00 In questa sezione, il concetto di rumore nell'overfitting viene ampliato oltre il rumore convenzionale e suddiviso in rumore stocastico e rumore deterministico. Si noti che più dati di solito portano a un minore overfitting e un aumento del rumore stocastico o deterministico porta a un maggiore overfitting. Il rumore deterministico è definito come la parte della funzione target che un insieme di ipotesi non può catturare ed è etichettato come rumore perché un insieme di ipotesi non può gestirlo. Il concetto di come qualcosa che non può essere catturato sia rumore viene ulteriormente esplorato utilizzando uno scenario ipotetico che prevede la spiegazione di numeri complessi a un giovane fratello con una comprensione limitata dei numeri.

  • 00:45:00 In questa sezione della lezione viene spiegata la differenza tra rumore deterministico e stocastico e viene analizzato l'impatto del rumore deterministico sull'overfitting. Si sottolinea che il rumore deterministico dipende dall'insieme di ipotesi utilizzato e, all'aumentare della complessità del target, aumentano anche il rumore deterministico e l'overfitting. Tuttavia, ciò non si verifica finché la complessità dell'obiettivo non supera un certo livello. Per N finito, gli stessi problemi con il rumore stocastico si applicano al rumore deterministico in quanto è possibile catturarne una parte a causa della dimensione limitata del campione. Si dice anche che l'utilizzo di un set di ipotesi più complesso non è sempre migliore e può portare a un overfitting.

  • 00:50:00 In questa sezione, il docente discute il problema dell'overfitting quando viene fornito un campione finito. Spiega che una volta dato un campione finito, si ha la capacità di adattare il rumore, sia stocastico che deterministico, che può portare a prestazioni peggiori. Il docente fornisce un'analisi quantitativa che aggiunge rumore all'obiettivo per ottenere informazioni sul ruolo del rumore stocastico e deterministico. Aggiunge e sottrae il centroide e l'epsilon in preparazione per ottenere termini al quadrato e termini incrociati, che porta a un termine di varianza, un termine di bias e un termine aggiunto. Il termine aggiunto è solo sigma al quadrato, la varianza del rumore.

  • 00:55:00 In questa sezione della conferenza, il relatore discute la scomposizione del valore atteso in distorsione e varianza e come si relazionano al rumore deterministico e stocastico. Entrambi rappresentano rispettivamente la migliore approssimazione alla funzione target e al rumore che non può essere previsto. L'aumento del numero di esempi diminuisce la varianza, ma sia il bias che la varianza sono inevitabili data un'ipotesi. Il rumore deterministico e il rumore stocastico hanno entrambi una versione finita sui punti dati che influenzano la varianza rendendo l'adattamento più suscettibile all'overfitting. Il relatore dà una guida alle prossime due lezioni sull'evitare l'overfitting discutendo due approcci, regolarizzazione e convalida. La regolarizzazione è come frenare per evitare l'overfitting, mentre la validazione è controllare i profitti per evitare l'overfitting.

  • 01:00:00 In questa sezione, il professore discute il concetto di porre un freno all'overfitting utilizzando un adattamento contenuto o una regolarizzazione. Usa l'esempio di adattare i punti a un polinomio di 4° ordine, ma impedendogli di adattarsi completamente inserendovi un po' di attrito. La quantità di freno applicata è minima ma si traduce in una drastica riduzione dell'overfitting pur ottenendo una vestibilità fantastica. Il professore osserva che è importante comprendere la regolarizzazione e come sceglierla per evitare l'overfitting. La sessione di domande e risposte affronta l'importanza della randomizzazione nella discesa del gradiente stocastico e come disegnare errori fuori campione nei grafici della rete neurale.

  • 01:05:00 In questa sezione, il professore spiega che il rumore deterministico e stocastico in uno scenario di apprendimento sono gli stessi perché il rumore deterministico è causato dall'incapacità di un'ipotesi impostata di avvicinarsi alla funzione target. Nei problemi di apprendimento del mondo reale, la complessità della funzione target è generalmente sconosciuta e il rumore non può essere identificato. L'obiettivo di comprendere concettualmente l'overfitting è evitare l'overfitting senza i dettagli del rumore. Over-training è sinonimo di overfitting, relativamente allo stesso modello. Altre fonti di errore, come i numeri in virgola mobile, producono un effetto limitato sull'overfitting, che non viene mai menzionato. In termini di modello lineare di terzo ordine (regressione logistica), il professore chiarisce che se applicato a dati linearmente separabili, è possibile ottenere un minimo locale e zero errore nel campione.

  • 01:10:00 In questa sezione, il professore discute il problema dell'overfitting e la sua versione a campione finito, che si verifica a causa del contributo del rumore da fattori sia stocastici che deterministici in un campione finito. Questo porta l'algoritmo ad adattarsi a quel rumore, il che è dannoso quando si tratta di adattare modelli più grandi come H_10. Discutendo l'uso di funzioni lineari a tratti per prevenire l'overfitting, il professore sottolinea l'importanza di considerare il numero di gradi di libertà nel modello e adottare misure per restringere il modello in termini di adattamento attraverso la regolarizzazione. Infine, il professore copre la questione pratica della convalida di un modello e di come può influire sull'overfitting e sulla selezione del modello.

  • 01:15:00 In questa sezione, il professore discute il compromesso tra overfitting e underfitting e spiega che per arrivare a un'ipotesi migliore, potrebbe essere necessario privarsi di una risorsa che avrebbe potuto essere utilizzata per la formazione. Il professore approfondisce anche la dimensione VC (Vapnik-Chervonenkis) e come si relaziona con l'overfitting, affermando che la discrepanza nella dimensione VC, dato lo stesso numero di esempi, è la ragione delle discrepanze nel fuori campione e in -errore di esempio. Il professore chiarisce inoltre che anche se hanno illustrato la complessità dell'obiettivo nei grafici a colori, la complessità dell'obiettivo non è misurata esplicitamente e non esiste un modo chiaro per mapparla nell'energia del rumore deterministico. Infine, il professore discute di come la complessità target potrebbe tradursi in qualcosa nella decomposizione bias-variance e ha un impatto su overfitting e generalizzazione.
Lecture 11 - Overfitting
Lecture 11 - Overfitting
  • 2012.05.10
  • www.youtube.com
Overfitting - Fitting the data too well; fitting the noise. Deterministic noise versus stochastic noise. Lecture 11 of 18 of Caltech's Machine Learning Cours...
 

Lezione 12 - Regolarizzazione



Corso di Machine Learning di Caltech - CS 156. Lezione 12 - Regolarizzazione

Questa conferenza sulla regolarizzazione inizia con una spiegazione dell'overfitting e del suo impatto negativo sulla generalizzazione dei modelli di machine learning. Vengono discussi due approcci alla regolarizzazione: matematico ed euristico. La lezione approfondisce quindi l'impatto della regolarizzazione su distorsione e varianza nei modelli lineari, utilizzando l'esempio dei polinomi di Legendre come componenti in espansione. Viene trattata anche la relazione tra C e lambda nella regolarizzazione, con un'introduzione all'errore aumentato e al suo ruolo nel giustificare la regolarizzazione per la generalizzazione. Vengono anche discusse le tecniche di decadimento/crescita del peso e l'importanza di scegliere il giusto regolarizzatore per evitare l'overfitting. La conferenza si conclude con un focus sulla scelta di un buon omega come esercizio euristico e spera che lambda serva come grazia salvifica per la regolarizzazione.

La seconda parte discute il decadimento del peso come un modo per bilanciare la semplicità della rete con la sua funzionalità. Il docente mette in guardia contro l'eccessiva regolarizzazione e le prestazioni non ottimali, sottolineando l'uso della convalida per determinare parametri di regolarizzazione ottimali per diversi livelli di rumore. La regolarizzazione è discussa come sperimentale con una base teorica e pratica. Vengono introdotti tipi comuni di regolarizzazione come L1/L2, interruzione anticipata e abbandono, insieme a come determinare il metodo di regolarizzazione appropriato per diversi problemi. Vengono inoltre discussi gli iperparametri comuni associati all'implementazione della regolarizzazione.

  • 00:00:00 In questa sezione, Yaser Abu-Mostafo approfondisce i dettagli dell'overfitting, che si verifica quando un modello si adatta troppo bene ai dati, a costo di una scarsa generalizzazione. Anche se i dati non sono rumorosi, può verificarsi rumore deterministico a causa delle limitazioni del modello, che porta a uno schema che danneggia l'errore fuori campione e causa l'overfitting. Tuttavia, Abu-Mostafo introduce la regolarizzazione come prima cura per l'overfitting, che è una tecnica utilizzata in quasi tutte le applicazioni di machine learning ed è importante da comprendere.

  • 00:05:00 In questa sezione, il docente discute due approcci alla regolarizzazione nell'apprendimento automatico. Il primo approccio è matematico, in cui vengono imposti vincoli di scorrevolezza per risolvere problemi mal posti, ma le ipotesi fatte in questi sviluppi non sono sempre realistiche per le applicazioni pratiche. Il secondo approccio è euristico e comporta l'handicap della minimizzazione dell'errore nel campione mettendo i freni sull'adattamento, che aiuta a combattere l'overfitting. Il docente fornisce un esempio utilizzando una sinusoide e un adattamento di linea, dimostrando che regolarizzando e controllando l'offset e la pendenza delle linee, potremmo essere in grado di ottenere migliori prestazioni fuori campione.

  • 00:10:00 In questa sezione, il docente discute l'impatto della regolarizzazione sulla distorsione e sulla varianza di un modello lineare. Utilizzando la regolarizzazione, la varianza viene ridotta mentre il bias viene leggermente aumentato a causa dell'adattamento imperfetto. Il docente utilizza l'esempio di un modello polinomiale con polinomi di Legendre come componenti di espansione per dimostrare l'effetto della regolarizzazione su distorsione e varianza. Con la regolarizzazione, il modello lineare supera il modello non regolarizzato e persino il modello costante. La conferenza approfondisce lo sviluppo matematico di una delle tecniche di regolarizzazione più famose nell'apprendimento automatico con un focus su conclusioni e lezioni concrete che possono essere apprese per affrontare situazioni del mondo reale.

  • 00:15:00 In questa sezione, il docente introduce i polinomi di Legendre e spiega come possono essere utilizzati per costruire un insieme di ipotesi per la regressione polinomiale. Usando questi polinomi, che sono ortogonali e trattano coordinate diverse, il parametro rilevante è una combinazione di pesi, piuttosto che un solo singolo peso. L'insieme di ipotesi può essere parametrizzato e rappresentato in forma lineare, consentendo facili soluzioni analitiche. La funzione target è sconosciuta e l'obiettivo è ottenerne una buona approssimazione utilizzando un set di addestramento finito. Il docente esamina anche le soluzioni non vincolate e vincolate per ridurre al minimo l'errore nel campione utilizzando la regressione lineare.

  • 00:20:00 In questa sezione, il docente discute il concetto di regolarizzazione, che è un vincolo applicato ai pesi degli insiemi di ipotesi. La regolarizzazione implica l'impostazione di un budget C per la grandezza totale al quadrato dei pesi, il che significa che non puoi avere tutti i pesi troppo grandi. Il problema è ridurre al minimo l'errore nel campione mentre è soggetto a questo vincolo. La soluzione si ottiene utilizzando i moltiplicatori di Lagrange o KKT, che fornisce una nuova soluzione chiamata w_reg. Il docente spiega che l'obiettivo è scegliere un punto all'interno di un cerchio che riduca al minimo l'errore nel campione, il che richiede di andare il più lontano possibile senza violare il vincolo.

  • 00:25:00 In questa sezione viene discusso il concetto di regolarizzazione, in cui l'obiettivo è derivare un modello che si generalizzi bene ai dati invisibili. La soluzione della regressione lineare è il minimo assoluto, che soddisfa il vincolo. L'obiettivo principale è derivare la condizione analitica per raggiungere il minimo di E_in, soggetto al vincolo, al fine di trovare un compromesso tra l'obiettivo e il vincolo. Il gradiente della funzione obiettivo deve essere ortogonale all'ellisse e il vettore w è nella direzione della superficie rossa. La condizione analitica per w_reg è che il gradiente sia proporzionale al negativo della soluzione. Minimizzando l'equazione della soluzione si ottiene il minimo di E_in, incondizionatamente.

  • 00:30:00 In questa sezione, la lezione discute la relazione tra i parametri C e lambda nella regolarizzazione. Maggiore è il valore di C, minore è il valore di lambda in quanto vi è minore enfasi sul termine di regolarizzazione. Al contrario, al diminuire di C, il termine di regolarizzazione diventa più significativo e il valore di lambda deve aumentare per far rispettare la condizione. La lezione introduce anche l'errore aumentato, che è la somma della funzione di errore e del termine di regolarizzazione. È equivalente a un problema di ottimizzazione non vincolato di minimizzazione della funzione di errore mentre è soggetto al vincolo. Questa corrispondenza giustifica la regolarizzazione in termini di generalizzazione ed è applicabile a qualsiasi regolarizzatore. Infine, la lezione fornisce la formula per minimizzare l'errore aumentato e si conclude fornendo la soluzione.

  • 00:35:00 In questa sezione, il relatore discute la soluzione al problema della regolarizzazione. La soluzione è rappresentata da w_reg, che è una modifica della soluzione pseudo-inversa con un termine di regolarizzazione aggiuntivo. Sotto presupposti chiari, abbiamo un apprendimento in un'unica fase, inclusa la regolarizzazione. In altre parole, possiamo avere una soluzione definitiva senza eseguire un'ottimizzazione vincolata. Il termine di regolarizzazione nella soluzione diventa dominante all'aumentare di lambda, il che porta w_reg a zero, creando una soluzione sempre più piccola. L'oratore applica quindi la regolarizzazione a un problema familiare, dimostrando che la scelta di lambda è fondamentale e che sarà necessaria una scelta euristica per il tipo di regolarizzatore.

  • 00:40:00 In questa sezione viene introdotto il concetto di regolarizzazione e il relativo metodo noto come decadimento del peso. Il decadimento del peso è un famoso regolarizzatore nell'apprendimento automatico che implica la riduzione al minimo di w trasposto w e l'assicurarsi che i pesi siano piccoli in modo da dare il nome "decadimento". Quando si utilizzano reti neurali, il decadimento del peso può essere implementato attraverso la discesa del gradiente batch, in cui l'aggiunta di questo termine riduce i pesi prima di qualsiasi movimento nello spazio del peso, il che limita quanto si può apprendere sulla funzione quando λ è grande. Le variazioni del decadimento del peso includono l'assegnazione di fattori di importanza a determinati pesi e l'utilizzo di costanti diverse per sperimentare il tipo di regolarizzatore utilizzato.

  • 00:45:00 In questa sezione, il docente discute le tecniche di decadimento del peso e di crescita del peso, che sono vincoli utilizzati nell'apprendimento automatico per limitare l'intervallo di pesi utilizzato dai modelli. Il decadimento del peso comporta la limitazione dei modelli all'utilizzo di pesi più piccoli, mentre la crescita del peso impone pesi maggiori. Il docente spiega che è necessario scegliere un valore lambda ottimale per entrambe le tecniche per ottenere le migliori prestazioni fuori campione. Inoltre, il docente discute come scegliere il giusto regolarizzatore, sottolineando l'importanza di evitare l'overfitting attraverso l'uso di linee guida che aiutano a guidare la scelta dei regolarizzatori. In definitiva, il docente consiglia di utilizzare regole pratiche per aiutare a trovare i regolarizzatori ottimali, come evitare il rumore stocastico ad alta frequenza.

  • 00:50:00 In questa sezione della lezione, l'istruttore spiega i diversi tipi di rumore che possono portare all'overfitting e perché è importante scegliere un regolarizzatore che tende a scegliere ipotesi più uniformi. Definisce la forma generale di regolarizzazione e l'errore aumentato che viene minimizzato, che è simile all'equazione utilizzata nell'analisi VC. Discute anche la corrispondenza tra la complessità di un'ipotesi individuale e la complessità dell'insieme di oggetti, e come E_aug sia una stima migliore per E_out rispetto a E_in.

  • 00:55:00 In questa sezione della lezione sulla regolarizzazione, viene discussa l'idea dell'errore aumentato come migliore proxy dell'errore fuori campione. La regolarizzazione mira a ridurre l'overfitting, che essenzialmente adatta il rumore più del segnale. Il principio guida per la scelta di un regolarizzatore è quello di muoversi nella direzione di un rumore più uniforme, poiché il rumore non è uniforme e le soluzioni più uniformi tendono a danneggiare il rumore più del segnale di adattamento. Il concetto di più semplice viene introdotto anche nel caso in cui più agevole non si applica bene. La scelta di un buon omega è un esercizio euristico e la matematica coinvolta è valida solo quanto il presupposto su cui si basa. La conferenza si conclude con la speranza che lambda serva come grazia salvifica per la scelta del regolarizzatore.

  • 01:00:00 In questa sezione della lezione viene esplorato il concetto di decadimento del peso per le reti neurali, in cui pesi piccoli determinano la semplicità della funzione e pesi maggiori determinano una dipendenza logica per consentire l'implementazione di qualsiasi funzionalità. Un'altra forma di regolarizzazione è l'eliminazione del peso, in cui alcuni dei pesi all'interno di una rete sono forzati a essere zero, determinando una dimensione VC più piccola, consentendo una migliore generalizzazione e minori possibilità di overfitting. Viene introdotta l'eliminazione del peso morbido, per cui una funzione continua viene applicata alla rete per enfatizzare alcuni dei pesi rispetto ad altri. Infine, l'interruzione anticipata viene discussa come una forma di regolarizzazione, che raccomanda di interrompere l'allenamento prima della fine, in quanto è un modo per fornire indirettamente semplicità alla funzione.

  • 01:05:00 In questa sezione, il professore spiega che la regolarizzazione avviene tramite l'ottimizzatore e che non cambiamo la funzione obiettivo. Invece, consegniamo la funzione obiettivo, che è l'errore nel campione, all'ottimizzatore e gli diciamo di minimizzarlo. Il professore quindi mette in guardia dal mettere semplicemente il regolarizzatore nell'ottimizzatore, che può portare a un'eccessiva regolarizzazione e prestazioni non ottimali se non eseguita correttamente. Sottolinea l'importanza di catturare il più possibile nella funzione obiettivo e quindi utilizzare la convalida per determinare il valore ottimale per il parametro di regolarizzazione, lambda. Il professore mostra quindi come la scelta di lambda cambia con diversi livelli di rumore e come l'utilizzo della convalida può aiutare a determinare il miglior risultato possibile dato il rumore. Infine, discute l'uso di diversi tipi di regolarizzatori con parametri diversi, a seconda delle prestazioni.

  • 01:10:00 In questa sezione, il professore discute l'uso dei regolarizzatori nell'apprendimento automatico, che è un'attività sperimentale piuttosto che un'attività completamente basata su principi. L'approccio dell'apprendimento automatico è da qualche parte tra teoria e pratica, il che significa che ha una solida base in entrambi. Il professore utilizza i polinomi di Legendre come funzioni ortogonali perché forniscono un livello di generalità interessante e la soluzione è semplice. La regolarizzazione consente a un utente di trovare un punto debole per le migliori prestazioni, che potrebbe trovarsi tra due passaggi discreti. Il termine di regolarizzazione aggiunto non dipende esplicitamente dal set di dati. Tuttavia, il parametro ottimale, lambda, dipenderà dal training set, che sarà determinato dalla validazione.

  • 01:15:00 In questa sezione viene introdotto il concetto di regolarizzazione, che prevede l'aggiunta di un termine di penalità alla funzione di perdita al fine di evitare l'overfitting nei modelli di machine learning. Vengono discussi i due tipi più comuni di regolarizzazione, L1 e L2, insieme ai rispettivi vantaggi e svantaggi. Inoltre, viene spiegato l'uso dell'interruzione anticipata e dell'abbandono come tecniche di regolarizzazione alternative. La lezione si conclude con una panoramica su come determinare il metodo di regolarizzazione appropriato per un dato problema, nonché gli iperparametri comuni da considerare quando si implementa la regolarizzazione.
Lecture 12 - Regularization
Lecture 12 - Regularization
  • 2012.05.14
  • www.youtube.com
Regularization - Putting the brakes on fitting the noise. Hard and soft constraints. Augmented error and weight decay. Lecture 12 of 18 of Caltech's Machine ...
 

Lezione 13 - Validazione




Corso di Machine Learning di Caltech - CS 156. Lezione 13 - Convalida

Nella lezione 13, l'attenzione è rivolta alla convalida come tecnica importante nell'apprendimento automatico per la selezione del modello. La conferenza approfondisce le specifiche della convalida, incluso il motivo per cui si chiama convalida e perché è importante per la selezione del modello. La validazione incrociata viene discussa anche come un tipo di validazione che consente l'uso di tutti gli esempi disponibili per l'addestramento e la validazione. Il docente spiega come stimare l'errore fuori campione utilizzando la variabile casuale che prende un punto fuori campione e calcola la differenza tra l'ipotesi e il valore target. La conferenza discute anche il bias introdotto quando si utilizza la stima per scegliere un particolare modello, in quanto non è più affidabile poiché è stato selezionato in base al set di validazione. Viene introdotto il concetto di convalida incrociata come metodo per valutare l'errore fuori campione per diverse ipotesi.

Copre anche l'uso della convalida incrociata per la selezione e la convalida del modello per prevenire l'overfitting, con particolare attenzione a "lasciarne fuori uno" e alla convalida incrociata di 10 volte. Il professore dimostra l'importanza di tenere conto della discrepanza fuori dal campione e dello snooping dei dati e suggerisce di includere metodi di randomizzazione per evitare bias di campionamento. Spiega che sebbene la convalida incrociata possa aggiungere complessità, combinandola con la regolarizzazione è possibile selezionare il modello migliore e, poiché la convalida non richiede presupposti, è unica. Il professore spiega inoltre come la convalida incrociata può aiutare a fare scelte di principio anche quando si confrontano diversi scenari e modelli e come i punti di convalida totali determinano la barra di errore e il bias.

  • 00:00:00 In questa sezione, l'attenzione è rivolta alla convalida, un'altra tecnica importante nell'apprendimento automatico utilizzata per la selezione del modello. Il processo prevede la scelta di una dimensione del set di convalida e il suo utilizzo per convalidare il processo di selezione del modello. La conferenza approfondisce le specifiche della convalida, incluso il motivo per cui si chiama convalida e perché è importante per la selezione del modello. La discussione copre anche la convalida incrociata, che è un tipo di convalida che consente l'uso di tutti gli esempi disponibili per l'addestramento e la convalida. La conferenza contrappone la validazione alla regolarizzazione, per quanto riguarda il controllo.

  • 00:05:00 In questa sezione, il docente discute la validazione e la regolarizzazione nel contesto della ben nota equazione che si occupa della differenza tra l'errore in-sample e l'errore out-of-sample dovuto alla complessità del modello. La regolarizzazione stima la penalità per la complessità dell'overfit mentre la convalida tenta di stimare direttamente l'errore fuori campione. Il docente spiega come stimare l'errore fuori campione utilizzando la variabile casuale che prende un punto fuori campione e calcola la differenza tra l'ipotesi e il valore target. Il docente sottolinea come la varianza influisca sulla qualità della stima e propone di utilizzare una serie completa di punti invece di uno.

  • 00:10:00 In questa sezione viene introdotta la nozione di un insieme di validazione e l'errore di validazione come stima imparziale dell'errore fuori campione. Il valore atteso dell'errore di convalida è E_out, che è un'altra forma del valore atteso su un singolo punto. La varianza dell'errore di validazione viene analizzata per mostrare che c'è un miglioramento nella stima basata su E_val rispetto a un singolo punto. La varianza finisce per essere proporzionale a 1/K, il che significa che l'aumento di K può ridurre la barra di errore e migliorare l'affidabilità della stima. Tuttavia, il numero di punti di convalida non è gratuito e ha un impatto diretto sul numero di punti disponibili per la formazione.

  • 00:15:00 In questa sezione, l'attenzione è rivolta al processo di validazione, per cui K punti vengono prelevati da N punti a scopo di validazione, mentre il restante sottoinsieme D_train viene utilizzato per l'addestramento. È anche importante notare l'utilità di disporre di una stima affidabile di un set di convalida per garantire che l'ipotesi finale sia affidabile. Tuttavia, avere una stima affidabile di una quantità errata non dovrebbe essere l'obiettivo. All'aumentare del valore di K, la stima diventa più affidabile, ma la qualità dell'ipotesi diminuisce. Pertanto, è fondamentale trovare un modo per non dover pagare il prezzo che deriva dall'aumento di K. Un modo è ripristinare il set di dati dopo aver stimato l'errore e allenarsi sull'intero set per ottenere risultati migliori.

  • 00:20:00 In questa sezione, l'attenzione si concentra sul compromesso in termini di prestazioni quando si utilizza un set di convalida durante l'allenamento. L'insieme ridotto di D_train avrà meno esempi rispetto all'insieme di addestramento completo D, utilizzando il quale otteniamo l'ipotesi finale g meno. Per ottenere una stima, valutiamo g meno su un set di convalida D_val, quindi aggiungiamo il resto degli esempi nel piatto e riportiamo g. Tuttavia, una K grande significa che la differenza tra g meno e g è maggiore, e questo influisce sull'affidabilità della stima che riportiamo. Quindi, esiste una regola empirica per utilizzare un quinto per la convalida per ottenere il meglio da entrambi i mondi. La chiamiamo convalida perché influisce sul processo di apprendimento e aiuta a fare delle scelte.

  • 00:25:00 In questa sezione, l'obiettivo è comprendere la differenza tra errore di test ed errore di convalida. Quando il set di test è imparziale e viene utilizzato per stimare E_out, ci saranno fluttuazioni nella stima. Se si utilizza l'arresto anticipato, la distorsione della stima cambia. In uno scenario di mini-apprendimento, è facile vedere che il valore atteso del minimo è inferiore a 0,5, il che lo rende un pregiudizio ottimistico. La stessa cosa accade quando viene scelto un punto per l'arresto anticipato: il punto scelto è minimo sulla realizzazione e viene introdotto un pregiudizio ottimistico.

  • 00:30:00 In questa sezione, la lezione discute l'uso del set di convalida per la selezione del modello nell'apprendimento automatico. Il processo prevede l'addestramento di modelli M utilizzando un set di dati suddiviso in set di addestramento e convalida, quindi la valutazione delle prestazioni di ciascun modello sul set di convalida per ottenere stime dell'errore fuori campione. Viene scelto il modello con l'errore di validazione più piccolo, ma c'è il rischio di bias introdotto a causa di questo processo di selezione. Tuttavia, la distorsione è generalmente minore nella pratica e può essere accettata per ottenere una stima affidabile dell'errore fuori campione.

  • 00:35:00 In questa sezione, il docente discute il bias introdotto quando si utilizza la stima per scegliere un particolare modello, in quanto non è più affidabile poiché è stato selezionato in base al set di validazione. Il valore atteso dello stimatore diventa una stima distorta dell'errore fuori campione. Un esperimento con due modelli ha generato una curva che indicava una distorsione sistematica verso un modello o l'altro. Le curve sul grafico indicano la curva di apprendimento all'indietro e come diminuisce l'errore fuori campione con più esempi per l'addestramento. Man mano che la dimensione del set di validazione aumenta, la stima diventa più affidabile e le curve che indicano gli errori dei modelli convergono.

  • 00:40:00 In questa sezione, la lezione spiega come stimare la discrepanza o il bias tra l'addestramento su un set di ipotesi speciali e la ricerca dell'ipotesi finale utilizzando un set di convalida. Il set di convalida è visto come l'errore di addestramento per il set di ipotesi finale e, con un po' di matematica relativa alla dimensione VC e alla complessità effettiva, è possibile ottenere una stima dell'errore fuori campione. Sebbene più esempi miglioreranno la stima, i contributi logaritmici devono essere presi in considerazione quando si seleziona da un numero maggiore di ipotesi. Tuttavia, quando si ha a che fare con un singolo parametro, la complessità effettiva va con una dimensione VC pari a 1, che non è troppo difficile da gestire. Pertanto, se si dispone di un set adatto, la stima dell'errore fuori campione non differirà troppo dal valore effettivo.

  • 00:45:00 In questa sezione, il relatore discute l'idea di contaminazione dei dati quando si utilizzano stime di errore per prendere decisioni, in particolare nel contesto della convalida. Il training set è considerato completamente contaminato, mentre il test set è completamente pulito e fornisce una stima imparziale. Tuttavia, il set di validazione è leggermente contaminato perché viene utilizzato per prendere alcune decisioni, quindi è importante non farsi prendere la mano e passare a un altro set di validazione quando necessario. L'oratore introduce quindi la convalida incrociata come un regime di convalida che può ottenere una stima migliore con una barra di errore più piccola, purché non sia distorta nel processo.

  • 00:50:00 In questa sezione il professore introduce il concetto di validazione tramite validazione incrociata, nello specifico il metodo "leave one out". In questo metodo, il set di dati è diviso in due, con un punto utilizzato per la convalida e il resto utilizzato per l'addestramento. Il processo viene ripetuto per diversi punti, risultando in molteplici stime imparziali e imperfette. Poiché tutte le stime si basano sull'addestramento con punti dati N meno 1, hanno un filo comune. Nonostante siano imperfette, le stime ripetute forniscono informazioni sul comportamento del modello e aiutano a ottimizzarlo per ottenere le migliori prestazioni fuori campione.

  • 00:55:00 In questa sezione viene introdotto il concetto di convalida incrociata come metodo per valutare l'errore fuori campione per diverse ipotesi. Dividendo il set di dati in set di addestramento e validazione, è possibile stimare le prestazioni del modello su dati invisibili. Il metodo "lasciane fuori uno" viene utilizzato per illustrare il processo. Viene discussa l'efficacia della convalida incrociata, dimostrando che l'utilizzo di N meno 1 punti per l'addestramento e N punti per la convalida è notevolmente efficiente per ottenere risultati accurati.

  • 01:00:00 In questa sezione, il professore discute l'uso della convalida incrociata per la selezione del modello. Lo dimostra confrontando i modelli lineare e costante con tre punti e mostra come vince il modello costante. Quindi applica la convalida incrociata al problema di trovare una superficie di separazione per le cifre scritte a mano utilizzando una trasformazione non lineare di 5° ordine con 20 caratteristiche. Utilizza la convalida incrociata "lasciane fuori uno" per confrontare 20 modelli e sceglie dove interrompere l'aggiunta di funzionalità. Mostra che l'errore di convalida incrociata segue da vicino l'errore fuori campione e che utilizzarlo come criterio per la scelta del modello porta a minimi a 6 funzionalità con prestazioni migliorate rispetto all'utilizzo del modello completo senza convalida.

  • 01:05:00 In questa sezione, il professore discute l'uso della convalida per prevenire l'overfitting e come sia considerata simile alla regolarizzazione. Spiega come la convalida "lasciane fuori uno" non sia pratica per la maggior parte dei problemi reali e suggerisce invece di utilizzare la convalida incrociata 10 volte. Fornisce inoltre indicazioni sul numero di parametri da utilizzare in base alle dimensioni del set di dati e chiarisce perché la scelta del modello mediante convalida non conta come snooping dei dati.

  • 01:10:00 In questa sezione, il professore discute l'importanza di tenere conto della discrepanza fuori campione e dello snooping dei dati quando si utilizza il set di convalida per effettuare scelte di modello. Sottolinea la necessità di utilizzare metodi di randomizzazione come il lancio di monete per evitare errori di campionamento e l'utilizzo di tecniche di convalida incrociata per scegliere il parametro di regolarizzazione in molti casi pratici. Sebbene la convalida incrociata possa aggiungere complessità computazionale, può anche essere combinata con la regolarizzazione per selezionare l'ipotesi migliore per un modello. Il professore osserva che sebbene esistano altri metodi per la selezione del modello, la convalida è unica in quanto non richiede ipotesi.

  • 01:15:00 In questa sezione, il professore discute come la validazione può aiutare a fare scelte di principio nella selezione dei modelli, indipendentemente dalla natura della scelta, e come può essere utilizzata anche per aggiornare il modello in caso di evoluzione temporale o sistema di tracciamento Evoluzione. Confrontando la convalida e la convalida incrociata, spiega che entrambi i metodi presentano pregiudizi, ma la convalida incrociata consente di utilizzare più esempi sia per l'addestramento che per la convalida, risultando in una barra di errore più piccola e una minore vulnerabilità al pregiudizio. Sebbene sia possibile avere set di dati così grandi da non richiedere la convalida incrociata, il professore fornisce un esempio in cui anche con 100 milioni di punti, la convalida incrociata è stata comunque vantaggiosa a causa della natura dei dati.

  • 01:20:00 In questa sezione, il professore discute gli scenari in cui la convalida incrociata è utile e affronta i potenziali problemi con essa. Spiega che la convalida incrociata diventa rilevante quando la parte più rilevante di un grande set di dati è più piccola dell'intero set. Quando si decide tra modelli concorrenti, è necessaria l'evidenza statistica per determinare la significatività dell'errore fuori campione. Il professore afferma che con un set di dati più piccolo, non esiste una risposta definitiva se sia meglio ricampionare o suddividere il set in blocchi per la convalida incrociata. Il professore discute anche del ruolo dell'equilibrio tra le classi e di come si comporta il pregiudizio quando si aumenta il numero di punti lasciati fuori. Infine, il professore spiega che il numero totale di punti di convalida determina la barra di errore e il bias è una funzione di come viene utilizzata la convalida incrociata.

  • 01:25:00 In questa sezione, il professore discute la barra di errore e come può fornire un'indicazione di vulnerabilità al bias in una stima. Se due scenari hanno barre di errore comparabili, non c'è motivo di credere che uno sia più vulnerabile al bias. Tuttavia, è necessaria un'analisi dettagliata per vedere la differenza tra prendere uno scenario alla volta e considerare le correlazioni. Il professore conclude che fintanto che viene eseguito un numero di pieghe e ogni esempio appare nella stima della convalida incrociata esattamente una volta, non c'è preferenza tra gli scenari in termini di bias.
Lecture 13 - Validation
Lecture 13 - Validation
  • 2012.05.17
  • www.youtube.com
Validation - Taking a peek out of sample. Model selection and data contamination. Cross validation. Lecture 13 of 18 of Caltech's Machine Learning Course - C...
 

Lezione 14 - Support Vector Machines



Corso di Machine Learning di Caltech - CS 156. Lezione 14 - Support Vector Machines

La conferenza copre l'importanza della convalida e del suo utilizzo nell'apprendimento automatico, nonché i vantaggi della convalida incrociata rispetto alla convalida. Il focus della lezione è sulle macchine vettoriali di supporto (SVM) come il modello di apprendimento più efficace per la classificazione, con uno schema dettagliato della sezione che coinvolge la massimizzazione del margine, la formulazione e le soluzioni analitiche attraverso l'ottimizzazione vincolata presentata. La lezione copre una serie di aspetti tecnici, tra cui come calcolare la distanza tra un punto e un iperpiano negli SVM, come risolvere il problema di ottimizzazione per gli SVM e come formulare il problema di ottimizzazione SVM nella sua doppia formulazione. Il docente discute anche gli aspetti pratici dell'utilizzo della programmazione quadratica per risolvere il problema di ottimizzazione e l'importanza di identificare i vettori di supporto. La lezione si conclude con una breve discussione sull'uso delle trasformazioni non lineari nelle SVM.

Nella seconda parte di questa lezione sulle macchine a vettori di supporto (SVM), il docente spiega come il numero di vettori di supporto diviso per il numero di esempi dia un limite superiore alla probabilità di errore nella classificazione di un punto fuori campione, rendendo il uso di vettori di supporto con trasformazione non lineare fattibile. Il professore discute anche la normalizzazione di w trasposto x più b per essere 1 e la sua necessità di ottimizzazione, così come la versione soft-margin di SVM, che consente errori e li penalizza. Inoltre, viene spiegata la relazione tra il numero di vettori di supporto e la dimensione VC e viene menzionata la resistenza del metodo al rumore, con la versione soft del metodo utilizzato nei casi di dati rumorosi.

  • 00:00:00 In questa sezione, il docente discute l'importanza della convalida, in particolare in termini di utilizzo nell'apprendimento automatico. Viene anche spiegato il concetto di distorsione imparziale e ottimistica come risultato dell'errore di convalida e il suo effetto sulla selezione del modello. Il vantaggio della convalida incrociata rispetto alla convalida è ulteriormente evidenziato nella sezione. Inoltre, il docente introduce le macchine vettoriali di supporto come il modello di apprendimento più efficace per la classificazione, citando la sua interpretazione intuitiva, una derivazione basata su principi e il pacchetto di ottimizzazione come vantaggi significativi per il modello di apprendimento. Viene inoltre presentato uno schema dettagliato della sezione, che prevede la massimizzazione del margine, la formulazione e le soluzioni analitiche attraverso l'ottimizzazione vincolata.

  • 00:05:00 In questa sezione è stato spiegato il concetto di massimizzare il margine nella separazione lineare. Sebbene tutte le righe che separano i dati linearmente separabili abbiano zero errori nel campione, alcune potrebbero avere margini migliori che consentono una maggiore generalizzazione. Viene spiegato che un margine maggiore è migliore perché, in situazioni rumorose, la probabilità che il nuovo punto venga classificato correttamente è maggiore. Ciò è correlato alla funzione di crescita e al modo in cui una funzione di crescita più grande è svantaggiosa per la generalizzazione nell'apprendimento automatico. È dimostrato che massimizzare il margine può aiutare con la generalizzazione cercando linee che non solo separino correttamente i dati, ma abbiano anche il margine massimo possibile per quei punti dati.

  • 00:10:00 In questa sezione, il docente discute i margini grassi e come possono migliorare le prestazioni di un classificatore. Richiedendo che un classificatore abbia un margine di una certa dimensione, il numero di possibili dicotomie viene ridotto, portando a una funzione di crescita più piccola ea una dimensione VC più piccola. Maggiore è il margine, migliori sono le prestazioni fuori campione del classificatore. Il docente spiega quindi come risolvere il margine più grande possibile, trovando la distanza tra l'iperpiano e il punto dati più vicino e normalizzando il vettore w per semplificare l'analisi. Il segnale, o la distanza tra l'iperpiano ei punti dati, non è la distanza euclidea, ma l'ordine dei punti più vicini e più lontani e deve essere convertito per ottenere la distanza euclidea.

  • 00:15:00 In questa sezione, il docente spiega alcuni aspetti tecnici relativi all'analisi della macchina a vettori di supporto. In primo luogo, per confrontare le prestazioni di diversi piani, la distanza euclidea viene utilizzata come metro di paragone. In secondo luogo, w viene estratta dal vettore X per analizzare più convenientemente le macchine a vettori di supporto, e viene estratta w₀ in modo che non venga confusa con il vettore w che ora ha un nuovo ruolo. L'obiettivo è calcolare la distanza tra xₙ (il punto più vicino) e il piano. Il docente mostra che il vettore w è ortogonale al piano ea ogni vettore sul piano, il che significa che è ortogonale a ogni vettore normale sul piano, quindi ora possiamo ottenere la distanza tra xₙ e il piano.

  • 00:20:00 In questa sezione, il relatore discute come calcolare la distanza tra un punto e un iperpiano negli SVM. Questo può essere fatto proiettando il vettore che va dal punto ad un generico punto dell'iperpiano sulla direzione ortogonale all'iperpiano. Il vettore unitario in questa direzione viene calcolato normalizzando la lunghezza del vettore. Usando un po' di algebra, il parlante ricava una formula per la distanza che viene semplificata aggiungendo un termine mancante. Questa formula può essere utilizzata per scegliere la combinazione di w che offre il miglior margine possibile. Il problema di ottimizzazione che ne deriva non è molto intuitivo a causa del minimo dei vincoli. Tuttavia, facendo alcune semplici osservazioni, questo problema può essere riformulato in uno quadratico più amichevole.

  • 00:25:00 In questa sezione, il docente spiega come risolvere il problema di ottimizzazione per Support Vector Machines (SVM). Iniziano mostrando come le SVM possono essere formulate come un problema di ottimizzazione vincolata in cui devono minimizzare una funzione obiettivo soggetta a vincoli di disuguaglianza lineare. Dimostrano che è possibile utilizzare i moltiplicatori di Lagrange per trasformare i vincoli di disuguaglianza in vincoli di uguaglianza e quindi risolvere la nuova lagrangiana. Notano che questo approccio è stato scoperto indipendentemente da Karush e Kuhn-Tucker ed è indicato come KKT Lagrangiano. Il docente sottolinea che il processo è simile alla procedura per la regolarizzazione, e richiamano la condizione del gradiente per la soluzione.

  • 00:30:00 In questa sezione il docente spiega la relazione tra SVM e regolarizzazione e la formulazione di Lagrange. È essenziale notare che i vincoli portano a un gradiente diverso da zero, a differenza del problema non vincolato in cui il gradiente è uguale a 0. La formulazione di Lagrange dipende da variabili come w e b, e ci sono nuove variabili, moltiplicatori di Lagrange come il vettore alfa . Il problema in questione è minimizzare la funzione obiettivo soggetta ai vincoli della forma, e quindi darle un nome lagrangiano. La parte interessante è che in realtà stiamo massimizzando rispetto all'alfa, anche se gli alfa devono essere non negativi, e quindi dobbiamo prestare attenzione a questo. La sezione si conclude con una breve spiegazione della parte non vincolata, dove occorre minimizzare il gradiente della Lagrangiana rispetto a w e b.

  • 00:35:00 In questa sezione della lezione, il relatore spiega come formulare il problema di ottimizzazione SVM nella sua formulazione duale. Per prima cosa ottimizza il problema rispetto a w e b, risultando in due condizioni che sostituisce nella lagrangiana originale, portando alla formulazione duale del problema, che è una bella formula in termini di soli moltiplicatori di Lagrange alfa. Quindi imposta il vincolo per gli alfa in modo che non sia negativo e risolve il problema di massimizzazione soggetto a questi vincoli, ottenendo i valori ottimali di alfa che determinano i vettori di supporto.

  • 00:40:00 In questa sezione, il relatore discute gli aspetti pratici dell'utilizzo della programmazione quadratica per risolvere il problema di ottimizzazione presentato in precedenza per le macchine a vettori di supporto. L'obiettivo e i vincoli vengono tradotti in coefficienti che vengono passati al pacchetto di programmazione quadratica per la minimizzazione. La dimensione della matrice dipende dal numero di esempi e questo diventa una considerazione pratica per grandi insiemi di dati. L'oratore avverte che quando il numero di esempi è elevato, la programmazione quadratica ha difficoltà a trovare la soluzione e potrebbe richiedere l'uso dell'euristica.

  • 00:45:00 In questa sezione, la lezione approfondisce le soluzioni offerte dalla programmazione quadratica, in particolare l'alfa, e come si collega al problema originale di determinare i pesi, la superficie, il margine e b. La conferenza sottolinea l'importanza di identificare i vettori di supporto, che sono i punti che definiscono il piano e il margine. La matematica alla base dei lambda positivi (alfa in questo caso) offre un modo per identificare i vettori di supporto, poiché considera solo i punti con valori positivi. Ciò significa che questi valori alfa sono cruciali per definire il confine tra le due classificazioni e identificare la loro posizione è fondamentale per ottimizzare i pesi e creare il margine massimo.

  • 00:50:00 In questa sezione, il concetto di vettori di supporto viene introdotto e discusso nel contesto dell'algoritmo della macchina vettoriale di supporto (SVM). I vettori di supporto sono definiti come i punti dati più vicini al confine decisionale o all'iperpiano che separa le classi di dati. L'algoritmo SVM ottimizza un problema di programmazione quadratica per determinare i vettori di supporto ei parametri della funzione di decisione. I valori dei parametri dipendono solo dai vettori di supporto, che sono i punti critici, consentendo al modello di generalizzare bene. Anche le trasformazioni non lineari vengono discusse brevemente come un modo per gestire dati non separabili. La trasformazione dei dati in uno spazio di dimensioni superiori non complica il problema di ottimizzazione e la stessa tecnica può essere utilizzata per trovare i vettori di supporto e la funzione di decisione.

  • 00:55:00 In questa sezione del video, il docente discute l'uso delle trasformazioni non lineari nelle SVM. Le trasformazioni non lineari vengono utilizzate quando i dati non sono separabili linearmente, come nel caso dello spazio X. Il docente dimostra come utilizzare una trasformazione non lineare e lavorare nello spazio Z per ottenere un risultato linearmente separabile. Spiega che la soluzione è semplice e il numero di alfa dipende dal numero di punti dati, non dalla dimensionalità dello spazio in cui stai lavorando. L'idea chiave è che puoi andare in uno spazio enorme senza pagare un prezzo in termini di ottimizzazione. I vettori di supporto sono identificati nello spazio Z, ma nello spazio X sembrano punti dati.

  • 01:00:00 In questa sezione, il docente discute il risultato della generalizzazione che rende fattibile l'utilizzo di vettori di supporto con trasformazione non lineare. Il numero di vettori di supporto, che rappresenta il numero di parametri effettivi, diviso per il numero di esempi fornisce un limite superiore alla probabilità di errore nella classificazione di un punto fuori campione. Se il valore atteso di diverse esecuzioni di questo macchinario è valido, allora l'effettivo E_out che otterrai in un caso particolare sarà delimitato sopra da un tipo familiare di limite (ad esempio, il numero di parametri, gradi di libertà e dimensione VC diviso per il numero di esempi). Questo risultato fa sì che le persone utilizzino vettori di supporto e vettori di supporto con la trasformazione non lineare, poiché non paghi per il calcolo dell'andare a una dimensione superiore o per la generalizzazione che ne consegue.

  • 01:05:00 In questa sezione, il professore spiega perché sceglie di normalizzare w trasposto x più b a 1, e perché questa normalizzazione è necessaria per l'ottimizzazione. Risponde anche a una domanda su come SVM gestisce i punti non linearmente separabili attraverso trasformazioni non lineari e su come la versione a margine morbido di SVM consente errori e li penalizza. Inoltre, il professore tocca brevemente la relazione tra il numero di vettori di supporto e la dimensione VC e come gli alfa rappresentano i parametri in SVM.

  • 01:10:00 In questa sezione, il docente discute la relazione tra il numero di parametri diversi da zero e la dimensione VC, che è equivalente al numero di vettori di supporto per definizione. La misura del margine può variare a seconda della norma utilizzata, ma non vi è alcun motivo valido per preferire l'uno all'altro in termini di prestazioni. Sebbene non esista un metodo diretto per eliminare i vettori di supporto, prendere sottoinsiemi e ottenere i vettori di supporto dei vettori di supporto sono possibili considerazioni computazionali. Il metodo SVM non è particolarmente suscettibile al rumore e, in caso di dati rumorosi, viene utilizzata la versione soft del metodo, che è notevolmente simile al caso non rumoroso.
Lecture 14 - Support Vector Machines
Lecture 14 - Support Vector Machines
  • 2012.05.18
  • www.youtube.com
Support Vector Machines - One of the most successful learning algorithms; getting a complex model at the price of a simple one. Lecture 14 of 18 of Caltech's...
 

Lezione 15 - Metodi Kernel



Corso di apprendimento automatico di Caltech - CS 156. Lezione 15 - Metodi del kernel

Questa lezione sui metodi del kernel introduce le macchine vettoriali di supporto (SVM) come un modello lineare che è più orientato alle prestazioni rispetto ai tradizionali modelli di regressione lineare a causa del concetto di massimizzare il margine. Se i dati non sono separabili linearmente, le trasformazioni non lineari possono essere utilizzate per creare superfici ondulate che consentono comunque ipotesi complesse senza pagare un prezzo elevato in termini di complessità. Il video spiega i metodi del kernel che vanno nello spazio Z ad alta dimensione, spiegando come calcolare il prodotto scalare senza calcolare i singoli vettori. Il video delinea anche i diversi approcci per ottenere un kernel valido per problemi di classificazione e spiega come applicare SVM a dati non separabili. Infine, il video spiega il concetto di slack e quantifica la violazione del margine in SVM, introducendo una variabile xi per penalizzare la violazione del margine e rivedendo la formulazione lagrangiana per risolvere l'alfa.

La seconda parte tratta gli aspetti pratici dell'utilizzo delle macchine a vettori di supporto (SVM) e dei metodi del kernel. Spiega il concetto di macchine vettoriali di supporto del margine morbido e come consentono una classificazione errata pur mantenendo un ampio margine. Parla dell'importanza del parametro C, che determina quanta violazione può verificarsi, e suggerisce di utilizzare la convalida incrociata per determinarne il valore. Affronta anche le preoccupazioni sulla coordinata costante nei dati trasformati e assicura agli utenti che svolge lo stesso ruolo del termine bias. Inoltre, discute la possibilità di combinare i kernel per produrre nuovi kernel e suggerisce metodi euristici che possono essere utilizzati quando la programmazione quadratica non riesce a risolvere SVM con troppi punti dati.

  • 00:00:00 In questa sezione della conferenza sui metodi del kernel, Yaser Abu-Mostafa introduce il concetto di macchine a vettori di supporto (SVM), osservando che non sono altro che un modello lineare nella forma più semplice, ma sono più orientate alle prestazioni a causa dell'idea di massimizzare il margine. Utilizzando un pacchetto di programmazione quadratica, possiamo risolvere il problema SVM e recuperare gli alfa, il che ci aiuta a identificare i vettori di supporto. Se i dati non sono separabili linearmente, possiamo utilizzare la trasformazione non lineare, ma la superficie ondulata risultante ci consente comunque di ottenere un'ipotesi complessa senza pagare un prezzo elevato in termini di complessità. Possiamo prevedere l'errore fuori campione in base al numero di vettori di supporto, che è una quantità nel campione.

  • 00:05:00 In questa sezione, il video spiega il concetto di metodi kernel e il loro ruolo nell'estendere le macchine vettoriali di supporto oltre il caso linearmente separabile. L'idea alla base dei metodi del kernel è quella di andare in uno spazio Z ad alta dimensione senza pagare il prezzo per la complessità. Il video spiega che la chiave per raggiungere questo obiettivo è essere in grado di calcolare il prodotto scalare nello spazio Z senza calcolare effettivamente i singoli vettori in quello spazio. È qui che entrano in gioco i kernel, poiché consentono il calcolo di prodotti interni utilizzando solo input espliciti. Il video prosegue spiegando le implicazioni di questi metodi per gestire trasformazioni non lineari e margini morbidi e come possono essere utilizzati nella pratica per gestire problemi complessi.

  • 00:10:00 In questa sezione, la lezione spiega l'uso del prodotto scalare nello spazio Z e come si collega ai metodi del kernel. Il prodotto scalare è necessario per formare la lagrangiana e passare i vincoli alla programmazione quadratica, ma può essere calcolato utilizzando solo i prodotti scalari per eseguire la macchina dei vettori di supporto. Usando un prodotto interno generalizzato o kernel che corrisponde a uno spazio Z, si possono trasformare due punti x e x trattino in una funzione determinata da x e x trattino, che è chiamata kernel. Viene fornito un esempio di uno spazio euclideo bidimensionale utilizzando una trasformazione polinomiale di 2° ordine.

  • 00:15:00 In questa sezione, il docente discute il concetto di metodi del kernel e come calcolare i kernel senza trasformare x e x trattino. Il docente improvvisa un kernel che non trasforma le cose nello spazio Z e convince il pubblico che il kernel corrisponde a una trasformazione in uno spazio Z, portando lì un prodotto interno. Elevando al quadrato un kernel con 1 + x_xdash elevato alla potenza Q, il docente spiega come questo diventi un prodotto interno in un certo spazio, rendendolo un kernel valido. Inoltre, il docente confronta la quantità di calcolo necessaria per farlo con altre dimensioni, indipendentemente dalla complessità di Q, che rimane la stessa.

  • 00:20:00 In questa sezione, il docente spiega un metodo kernel per la trasformazione polinomiale che può essere eseguita senza espandere effettivamente il polinomio. Prendendo il logaritmo e esponendolo, il polinomio diventa un'operazione semplice che non richiede un'enorme espansione. Questo è un semplice polinomio che può essere visualizzato in 2D ed estrapolato per altri casi. Un kernel che si associa a uno spazio dimensionale superiore può essere ottenuto prendendo un prodotto scalare in quello spazio. Il docente introduce un esempio di kernel che non ha un prodotto scalare nello spazio X o Z ma corrisponde a un prodotto scalare in uno spazio a dimensione infinita. Nonostante le sfide di andare in uno spazio a dimensione infinita, il metodo del kernel è ancora utile e il numero di vettori di supporto può essere utilizzato per determinare la generalizzazione di un modello.

  • 00:25:00 In questa sezione, il docente dimostra il kernel della funzione a base radiale, un kernel sofisticato che corrisponde a uno spazio a dimensione infinita, e mostra come funziona in azione prendendo un caso leggermente non separabile. Il docente genera 100 punti a caso e mostra che non esiste una linea che li separi. Quindi, il docente trasforma X in uno spazio a dimensione infinita e calcola il kernel, che è un semplice esponenziale. Il docente lo passa alla programmazione quadratica, che restituisce i vettori di supporto. Quando il docente oscura i vettori di supporto, diventa più facile vedere le due classi.

  • 00:30:00 In questa sezione, il relatore discute l'idea dei metodi del kernel e come possono essere usati per la classificazione. Presenta un esempio di utilizzo di un kernel su un set di dati di punti per trasformarli in uno spazio a dimensione infinita dove possono essere separati da un piano lineare. I vettori margine e supporto risultanti vengono utilizzati per determinare la quantità nel campione che guida la proprietà di generalizzazione. L'oratore prosegue poi spiegando come un kernel valido corrispondente a un prodotto scalare in un certo spazio Z possa essere utilizzato per formulare il problema e costruire l'ipotesi. Nel complesso, sottolinea l'utilità dei metodi kernel e come possono essere applicati per risolvere problemi di classificazione.

  • 00:35:00 In questa sezione impariamo come tradurre il modello lineare in una forma kernel, dove le macchine vettoriali di supporto diventano un modello che consente la scelta del kernel. Il kernel prende il posto del prodotto interno dopo che i prodotti interni sono stati presi con lo spazio Z. Il modello risultante dipende dalla scelta del kernel e possiamo anche risolvere b inserendo un vettore di supporto. Il kernel, tuttavia, è difficile da determinare poiché non è possibile verificarne la validità senza visitare lo spazio Z. Tuttavia, illustriamo come possiamo confrontare gli approcci osservando la forma funzionale di diversi kernel.

  • 00:40:00 In questa sezione, il docente spiega le condizioni per ottenere un kernel valido nei metodi del kernel. Esistono tre approcci: costruzione, in cui un nucleo è costruito da un insieme concettuale o esplicito di trasformazioni; La condizione di Mercer, che richiede che un dato kernel sia simmetrico e che una matrice costruita dai valori del kernel sia semi-definita positiva; e infine, un approccio all'improvvisazione, in cui la fattibilità del nucleo è una preoccupazione molto pratica, e due condizioni devono essere soddisfatte contemporaneamente. Questi sono che il kernel è simmetrico e la matrice costruita dai valori del kernel deve essere semidefinita positiva per qualsiasi scelta di punti, come richiesto dalla condizione di Mercer.

  • 00:45:00 In questa sezione, il docente descrive situazioni in cui i dati non sono linearmente separabili e come applicare l'algoritmo delle macchine vettoriali di supporto in tali casi. Potrebbero esserci due scenari di dati non separabili, uno in cui la non separabilità è minima e l'altro in cui la non separabilità è significativa. Per gestire dati separabili non lineari, si possono commettere errori e apprendere con la generalizzazione invece di provare a utilizzare spazi complessi di dimensioni eccessivamente elevate che contengono tutti i punti dati, mantenendo così basso l'errore. Nel caso di grave non separabilità, si deve optare per una trasformazione non lineare e utilizzare kernel o macchine vettoriali di supporto a margine morbido. Il docente parla quindi dell'idea di violazione del margine e di come quantificarla per tenere conto degli errori di classificazione.

  • 00:50:00 In questa sezione il docente introduce il concetto di slack e la quantificazione della violazione del margine in SVM. Spiega che introdurrà un gioco per ogni punto che misura la violazione del margine e penalizzerà la violazione totale fatta sommando questi giochi. Sceglie questa misura dell'errore, che è ragionevole e misura la violazione del margine, invece di altre. Quindi introduce la nuova ottimizzazione, che riduce al minimo il termine di errore di violazione del margine, insieme alla massimizzazione del margine. La costante C fornisce l'importanza relativa di questo termine di violazione del margine rispetto al termine precedente che massimizza il margine. A seconda del valore di C, il risultato finale potrebbe essere un dato linearmente separabile o un compromesso in quanto rappresenta il compromesso tra margine e flessibilità. Infine, passa in rassegna la formulazione lagrangiana con l'aggiunta dei nuovi termini.

  • 00:55:00 In questa sezione il docente spiega il nuovo problema di programmazione quadratica introdotto aggiungendo la variabile xi per penalizzare le violazioni di margine. La Lagrangiana include nuovi vincoli su xi che devono essere risolti per utilizzare i moltiplicatori di Lagrange, beta. Il docente mostra quindi come la minimizzazione di w e b rimane invariata e scopre che risolvendo per xi risulta una quantità che è sempre zero. Questa scoperta porta all'abbandono della lagrangiana beta, lasciando la stessa soluzione di prima, con l'unica conseguenza che alfa ora non solo è maggiore o uguale a zero ma è anche minore o uguale a C.

  • 01:00:00 In questa sezione del video, il docente esamina il concetto di macchine vettoriali di supporto del margine morbido, che consentono una classificazione errata pur mantenendo un ampio margine. La soluzione implica un vincolo aggiuntivo che richiede che alfa sia al massimo C, insieme al vincolo di uguaglianza già esistente. Le macchine vettoriali di supporto del margine morbido includono sia vettori di supporto del margine che non del margine, con questi ultimi i punti che violano il margine, causando un allentamento rappresentato dal valore xi. Il valore di C è un parametro importante che determina la quantità di violazione che può verificarsi e questo viene solitamente determinato attraverso la convalida incrociata.

  • 01:05:00 In questa sezione, il docente discute punti pratici sull'utilizzo di macchine a vettori di supporto (SVM) e metodi del kernel. Spiega che se i dati non sono separabili linearmente, la programmazione quadratica potrebbe non convergere, portando a una situazione in cui non esiste una soluzione fattibile. Tuttavia, incoraggia gli utenti a essere pigri ea passare comunque gli alfa dalla programmazione quadratica alla soluzione per valutare se separa o meno i dati. Inoltre, affronta le preoccupazioni sulla coordinata costante, 1, che viene trasformata con i dati, spiegando che svolge effettivamente lo stesso ruolo del termine bias, b, e che gli utenti non devono preoccuparsi di avere più coordinate con lo stesso ruolo.

  • 01:10:00 In questa sezione, il professore spiega che la linearità delle macchine a vettori di supporto (SVM) dipende da determinati presupposti e in alcuni casi può essere migliore di quella lineare. La dimensione dei dati può influenzare l'efficacia di SVM, ma il kernel RBF può gestire dimensioni infinite se i termini di ordine superiore decadono rapidamente. Un kernel valido deve avere un prodotto interno ben definito, che dipende dalla convergenza. Il professore non tocca gli SVM generalizzati ai casi di regressione poiché richiedono maggiori dettagli tecnici e il maggior successo degli SVM è nella classificazione. Infine, potrebbero esserci lamentele da parte dei pacchetti di programmazione quadratica per non essere definiti positivamente, ma le soluzioni potrebbero comunque andare bene con una certa affidabilità.

  • 01:15:00 In questa sezione, il professore discute la possibilità di combinare i kernel per produrre nuovi kernel e il requisito della combinazione per mantenere un prodotto scalare in uno spazio Z. Accenna inoltre al fatto che il problema della programmazione quadratica è il collo di bottiglia nella risoluzione dei problemi con le SVM e fornisce una stima del numero di punti che possono essere gestiti dalla programmazione quadratica. Inoltre, suggerisce metodi euristici che possono essere utilizzati quando la programmazione quadratica non riesce a risolvere SVM con troppi punti dati.
Lecture 15 - Kernel Methods
Lecture 15 - Kernel Methods
  • 2012.05.24
  • www.youtube.com
Kernel Methods - Extending SVM to infinite-dimensional spaces using the kernel trick, and to non-separable data using soft margins. Lecture 15 of 18 of Calte...