Metodi kernel per set di dati su larga scala

Question

Il classificatore basato su kernel di solito richiede tempo di allenamento O (n^3) a causa del calcolo del prodotto interno tra due istanze. Per accelerare la formazione, i valori del prodotto interno possono essere pre-calcolati e memorizzati in una matrice bidimensionale. Tuttavia quando il no. di istanze è molto grande, diciamo oltre 100.000, non ci sarà memoria sufficiente per farlo.

Quindi un'idea migliore per questo?

Answer 1

La macchina vettoriale di rilevanza ha una modalità di addestramento sequenziale in cui non è necessario conservare l'intera matrice del kernel in memoria. Puoi fondamentalmente calcolare una colonna alla volta, determinare se sembra pertinente e buttarla via altrimenti. Non ho avuto molta fortuna con me stesso, però, e l'RVM ha altri problemi. Molto probabilmente c'è una soluzione migliore nel regno dei processi gaussiani. Non mi sono mai seduto molto con quelli, ma ho visto menzionare un algoritmo online per questo.

Answer 2

io non sono un analista numerico, ma non è il QR decomposition che è necessario fare ordinarie dei minimi quadrati di regressione lineare anche O (n^3)?

In ogni caso, probabilmente vorrai cercare nella letteratura (poiché si tratta di cose abbastanza nuove) per le versioni di apprendimento online o di apprendimento attivo dell'algoritmo che stai utilizzando. L'idea generale è quella di scartare i dati lontano dal limite delle decisioni o di non includerli in primo luogo. Il pericolo è che potresti essere bloccato in un brutto massimo locale e quindi il tuo algoritmo online/attivo ignorerà i dati che potrebbero aiutarti a uscire.

Answer 3

Per le moderne implementazioni di macchine vettoriali di supporto, il ridimensionamento dell'algoritmo di addestramento dipende da molti fattori, come la natura dei dati di addestramento e del kernel che si sta utilizzando. Il fattore di scala di O (n^3) è un risultato analitico e non è particolarmente utile nel predire come l'allenamento SVM si ridimensionerà in situazioni reali. Ad esempio, le stime empiriche dell'algoritmo di addestramento utilizzato da SVMLight mettono il ridimensionamento rispetto alla dimensione dell'insieme di allenamento da approximately O(n^2).

Suggerirei di fare questa domanda nello kernel machines forum. Penso che tu abbia più probabilità di ottenere una risposta migliore rispetto a Stack Overflow, che è più di un sito di programmazione generico.