Aprile 2017
Volume 32 Numero 4
Il presente articolo è stato tradotto automaticamente.
Esecuzione di test - Percettroni kernel in C#
.jpg "James McCaffrey")
Una percezione di kernel è un classificatore di machine learning (ML) che può essere utilizzato per ottenere stime binarie. Ad esempio, una percezione kernel possibile stimare il sesso di una persona (maschio = -1, femminile = + 1) in base all'età, reddito, altezza e peso. Kernel percettroni sono una variante avanzate di percettroni normali e la gestione dei dati più complessi.
Un buon metodo per vedere futuro in questo articolo è di ottenere un quadro il programma demo in figura 1 e i dati associati in figura 2. L'obiettivo del programma demo consiste nel prevedere la classe, -1 o + 1, dati di input fittizio che ha solo due variabili predittive, x0 e x1. Ad esempio, i dati di training primo elemento sono (2.0, 3.0, -1), vale a dire che se i valori di input sono x0 = 2.0 e x1 = 3.0, la classe corretta è -1.
.png "Demo di percezione del kernel")
Figura 1 Kernel percezione Demo
.png "Dati di Training percezione del kernel")
Figura 2 i dati di Training percezione del Kernel
Il 21 punti dati di training hanno una geometria circolare, ovvero le tecniche di classificazione lineare semplice, ad esempio percettroni normali o di regressione logistica, sono inefficaci. Tali dati sono definiti separabili in modo non lineare.
Il programma demo utilizza i dati di training per creare un modello di stima utilizzando una percezione del kernel. A differenza di molti modelli di stima che comprendono una serie di valori numerici chiamato pesi, un modello di stima kernel crea un set di valori dei contatori, uno per ogni elemento di dati di training. Il programma demo vengono visualizzati i valori del contatore per i primi due elementi di dati (1 e 2) e le ultime due elementi di dati (0 e 1).
Dopo il training, il kernel percezione modello stima tutti gli elementi 21 dati correttamente, che è previsto. Il modello con Training viene applicato a quattro elementi di dati nuovi test che non sono stati utilizzati durante il training. Il primo elemento di test con input (2.0, 4.0) e una classe di -1. Il modello di stima consente di stimare correttamente tale elemento. In generale, il modello stima correttamente tre dei quattro elementi di test per verificarne l'accuratezza 0,75.
Dietro le quinte, la percezione del kernel utilizza una funzione denominata kernel base radiale function (RBF). La funzione kernel richiede un parametro denominato sigma. Il valore di sigma deve essere determinato da tentativi ed errori e sigma = 1.5 nella demo. Si noti che per impostazione sigma su 0,5, il programma demo sarebbe ottenere precisione pari al 100%. Ho utilizzato sigma = 1.5 per sottolineare che per la maggior parte dei set di dati non raggiungere la precisione al 100%.
In questo articolo si presuppone che si intermedio o versioni successive delle competenze di programmazione, ma non si supponga che si conoscono i percettroni kernel. Il programma demo è codificato tramite c#, ma è non necessario alcun problema di refactoring del codice in un altro linguaggio, ad esempio Python o JavaScript, se si desidera. Tutto il codice chiave demo, fatta eccezione per i dati codificati e alcune istruzioni di visualizzazione, presentato in questo articolo. Il codice sorgente di dimostrazione completo, inclusi i dati, è disponibile nel download associato.
Informazioni sulle funzioni Kernel
Per comprendere i percettroni kernel è necessario comprendere le funzioni kernel in generale. Sono disponibili molte funzioni kernel, ma la più comune uno e il tipo utilizzato dal programma di dimostrazione, viene chiamato il kernel RBF. La funzione kernel RBF accetta due vettori (vale a dire, matrici) e un parametro denominato sigma e restituisce un valore compreso tra 0,0 e 1,0 che è una misura della somiglianza tra le due matrici. Il valore restituito indica esattamente 1.0 le due matrici sono identiche. Le due matrici sono meno simile, minore sarà il valore di RBF è, raggiungendo ma trascurato raggiungere 0,0.
L'equazione per RBF è:
K(x1, x2) = exp( - || x1 - x2 ||^2 / (2 * sigma^2) )
In questo caso, K è l'acronimo di kernel, x1 e x2 sono due le matrici che contengono la stessa lunghezza, sigma è un parametro gratuito con un valore come 1,0 o 1.5, il | | indica la distanza euclidea ed exp indica il numero di Eulero (e) elevato a potenza.
RBF la risposta è chiarita da esempio. Si supponga che x1 = (2.0, 3.0, 1.0) e x2 = (0.0, 1.0, 5.0), e sigma è 1.0. In primo luogo, per calcolare la distanza euclidea quadratica:
|| x1 - x2 ||^2 = (2.0 - 0.0)^2 + (1.0 - 1.0)^2 + (3.0 - 5.0)^2
= 4.0 + 0.0 + 4.0
= 8.0
Successivamente, si divide la distanza quadratica per sigma 2 volte al quadrato:
8.0 / (2 * (1.0)^2) = 8.0 / 2.0 = 4.0
Infine, si accettano il numero di Eulero (e = circa 2.71828) e generarlo il corrispondente negativo del risultato precedente:
K = e^(-4.0) = 0.0183
Si noti che se uguale a x1, x2, la distanza euclidea quadratica sarà pari a 0 e quindi dividendo per 2 volte sigma quadratico saranno pari a 0 ed e elevato alla potenza 0 è 1.0. X1 meno simile e x2 sono, maggiore sarà il quadrato della differenza e ottiene molto piccolo, raggiungendo 0,0 e generato su un valore negativo elevato. Il valore di sigma è maggiore, maggiore sarà il valore di K è, ma K ancora varia da 1.0 (vettori uguale) fino a 0,0 esclusivo (vettori molto diversi). L'ordine dei parametri di matrice non è rilevante, pertanto K (x1, x2) = K (x2, x1).
Il programma demo definisce la funzione kernel RBF come:
static double Kernel(double[] d1, double[] d2, double sigma) {
double num = 0.0;
for (int i = 0; i < d1.Length - 1; ++i)
num += (d1[i] - d2[i]) * (d1[i] - d2[i]);
double denom = 2.0 * sigma * sigma;
double z = num / denom;
double result = Math.Exp(-z);
return result;
}
La funzione presuppone che l'ultima cella di ogni matrice contiene l'etichetta di classe (+ 1 o -1), in modo che all'ultima cella non è incluso nel calcolo. Esistono diverse altre funzioni di kernel che possono essere utilizzati con una percezione del kernel, tra cui il kernel lineare, kernel polinomiale, kernel Fisher e kernel sigmoid. Il calcolo funzioni kernel è relativamente semplice. Che cosa non è ovvio, tuttavia, è che le funzioni kernel presentano alcune proprietà matematiche notevole che consentono i classificatori semplici, come un normale percezione, devono essere trasformati in classificatori in grado di gestire dati separabili in modo non lineare.
Informazioni sulle Percettroni ordinari
Un normale percezione eseguibili classificazione binaria per dati separabili in modo lineare semplici. Una percezione comune è costituito da un insieme di pesi, in cui il numero di pesi uguale al numero di valori predittive e il peso speciale chiamata il valore della distorsione. Ad esempio, si supponga di avere un problema di classificazione binaria in cui sono presenti tre variabili predittive. E si supponga che i pesi di percettrone sono w0 = 1.5, w1 = 1.1 e w2 = -3.0, e tre variabili predittive presentano valori x0 = 4.0, x1 = 3.0, x2 = 5.0 e il valore della distorsione è b = 2.5. La stima viene calcolata come il segno di somma dei prodotti di peso e valori di input, nonché la deviazione (positivo o negativo):
sum = (w0)(x0) + (w1)(x1) +(w2)(x2) + b
= (1.5)(4.0) + (1.1)(3.0) + (-3.0)(5.0) + 2.5
= 6.0 + 3.3 + (-15.0) + 2.5
= -3.2
prediction = sign(sum)
= -1
È semplice. Ma i pesi e i valori di compensazione da dove provengono? Si accettano dati di training sono noti i valori di input e corretta la classe e quindi utilizzarla un algoritmo di ottimizzazione matematici per trovare i valori per i pesi e distorsione in modo che i valori calcolati classe similarità con i valori di classe corretto noti.
Si noti che nella documentazione di percezione, il valore della distorsione è spesso considerato un peso regolare associato a un valore fittizio input pari a 1,0. Utilizzando tale schema, l'esempio precedente avrebbe input x = (1.0, 4.0, 3.0, 5.0) e pesi w = (2.5, 1.5, 1.1, -3.0), restituendo il codice seguente (che è lo stesso risultato, come in precedenza):
sum = (2.5)(1.0) + (1.5)(4.0) + (1.1)(3.0) + (-3.0)(5.0)
= -3.2
In altre parole, il valore della deviazione percezione può essere esplicite o implicite. Non si deve sottovalutare la confusione in questo modo.
A questo punto, Sfortunatamente, percettroni ordinari possono classificare dati separabili solo in modo lineare, che li rende molto limitato nella pratica. Tuttavia, utilizzando una funzione kernel in combinazione con una percezione, è possibile creare un classificatore che possono essere usate con dati separabili in modo non lineare, ad esempio i dati demo illustrati figura 2.
L'algoritmo del Percettrone del Kernel
A prima vista, l'algoritmo del percettrone kernel viene visualizzato per l'algoritmo del percettrone ordinario indipendente dalla, ma in realtà, i due sono profondamente correlati. Si supponga che esistono solo quattro elementi di dati di training: td [0] = (2.0, 3.0, -1), td [1] = (3.0, 2.0, + 1), td [2] = (3.0, 5.0, + 1), td [3] = (4.0, 3.0, -1). E si supponga che il modello di percezione kernel sottoposto a training ha fornito i valori di contatore errato di un = (1, 2, 3, 4). (Utilizzare "a" minuscola inglese per i contatori errate perché nella letteratura di ricerca vengono regalati sigma greco il simbolo, che è simile a "a".)
Per stimare la classe di nuovi dati elemento x = (3.0, 6.0), si calcola la somma ponderata (da un valore e classe corretto dell'elemento training) della funzione kernel applicata per il nuovo elemento di dati e ognuno dei quattro elementi di formazione:
K(td[0], x) = 0.1083
K(td[1], x) = 0.0285
K(td[2], x) = 0.8007
K(td[3], x) = 0.1083
sum = (1)(0.1083)(-1) + (2)(0.0285)(+1) + (3)(0.8007)(+1) + (4)(0.1083)(-1)
= +1.9175
prediction = sign(sum)
= +1
Dichiarato in qualche modo regime di controllo libero, esamina la somiglianza dell'elemento di dati da classificare e tutti gli elementi di dati di training, la percezione del kernel e aggrega i valori di somiglianza, utilizzando i contatori non corretti come pesi, in un singolo valore che indica una classe stimata.
Per eseguire una stima di percezione kernel occorre pertanto i dati di training e i valori di contatore errato associato. Quando si esegue il training una percezione normale, utilizzare un processo iterativo. In ogni iterazione, utilizzare i valori correnti dei pesi e distorsione per calcolare una classe stimata. Se la classe stimata è corretta (non corrisponde alla classe nei dati di training) è regolare i pesi leggermente in modo che la classe stimata è più vicina al valore di classe corretto noti.
In una percezione del kernel, utilizzare un simile iterativo training processo, ma viene invece regolare i valori di peso quando una classe calcolata è errata, è incrementare il contatore errato per l'elemento corrente di training. Davvero sorprendente! La prova matematica di motivi del funzionamento è incredibilmente accattivante e sono reperibili nella voce di Wikipedia per percettroni kernel.
Espresso in pseudo-codice ad alto livello, l'algoritmo di training percezione di kernel è:
loop a few times
for each curr training item, i
for each other training item, j
sum += a[j] * K(td[i], td[j], sigma) * y[j];
end-for
pred = sign(sum)
if (pred is wrong) increment a[i]
end-for
end-loop
I due parametri necessari nell'algoritmo di training sono il numero di iterazioni da eseguire e il valore di sigma per la funzione kernel. Entrambi questi valori devono essere determinati da un po' di tentativi ed errori. Il programma demo esegue l'iterazione 10 volte e Usa 1.5 per sigma.
Si noti che l'algoritmo di training percezione ordinario utilizza dati di training per generare i pesi e distorsioni valori e quindi rimuove concettualmente i dati di training. L'algoritmo di training percezione kernel genera valori di contatore errato matematicamente correlate a pesi, ma l'algoritmo deve mantenere i dati di training per eseguire stime.
La struttura del programma Demo
La struttura generale del programma demo, con poche modifiche minori per risparmiare spazio, viene presentata in figura 3. Per semplicità, ho utilizzato lo stile di un metodo statico anziché uno stile di programmazione orientata agli oggetti. Il metodo Main contiene tutta la logica di controllo. Esistono due metodi helper, Kernel e accuratezza.
Figura 3 struttura del programma Demo percezione del Kernel
using System;
namespace KernelPerceptron
{
class KernelPerceptronProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin demo ");
int numFeatures = 2;
Console.WriteLine("Goal is classification(-1/+1) ");
Console.WriteLine("Setting up 21 training items ");
double[][] trainData = new double[21][];
trainData[0] = new double[] { 2.0, 3.0, -1 };
trainData[1] = new double[] { 2.0, 5.0, -1 };
. . .
trainData[20] = new double[] { 5.0, 6.0, +1 };
int numTrain = trainData.Length;
double[][] testData = new double[4][];
testData[0] = new double[] { 2.0, 4.0, -1 };
. .
testData[3] = new double[] { 5.5, 5.5, +1 };
int[] a = new int[trainData.Length];
int maxEpoch = 10;
int epoch = 0;
double sigma = 1.5; // for the kernel function
Console.WriteLine("Starting train, sigma = 1.5 ");
...
Console.WriteLine("Training complete ");
double trainAcc = Accuracy(trainData, a,
trainData, sigma, false); // silent
Console.WriteLine("Accuracy = " +
trainAcc.ToString("F4"));
Console.WriteLine("Analyzing test data: ");
double testAcc = Accuracy(testData, a,
trainData, sigma, true); // verbose
Console.WriteLine("End kernel perceptron demo ");
Console.ReadLine();
} // Main
static double Kernel(double[] d1, double[] d2,
double sigma) { . . }
static double Accuracy(double[][] data, int[] a,
double[][] trainData, double sigma, bool verbose)
{ . . }
} // Program
} // ns
Il programma demo di codice, avviato Visual Studio e creato un nuovo programma dell'applicazione di console in c# e denominato KernelPerceptron. Ho utilizzato Visual Studio 2015, ma il programma demo non è presenti dipendenze di .NET Framework significative in modo da qualsiasi versione recente funzionerà.
Dopo che il codice del modello caricato nella finestra dell'editor, pulsante destro del mouse sul file Program.cs nella finestra Esplora soluzioni e rinominato il file in KernelPerceptronProgram.cs, quindi Visual Studio rinominare automaticamente classe Program per me è consentito. Nella parte superiore del codice generati da un modello, eliminato tutto inutili istruzioni using, lasciando solo quella che fa riferimento lo spazio dei nomi principale di sistema.
Il metodo Main imposta backup dei dati di training e di test nel modo seguente:
int numFeatures = 2;
double[][] trainData = new double[21][];
trainData[0] = new double[] { 2.0, 3.0, -1 };
. .
trainData[20] = new double[] { 5.0, 6.0, +1 };
int numTrain = trainData.Length;
double[][] testData = new double[4][];
testData[0] = new double[] { 2.0, 4.0, -1 };
. .
testData[3] = new double[] { 5.5, 5.5, +1 };
La demo usa due variabili predittive (detta anche funzionalità nella terminologia ML) per semplicità, ma i percettroni kernel in grado di gestire un numero qualsiasi di variabili predittive. I dati sono hardcoded, ma in uno scenario dimostrativo non è probabile che carica i dati da un file di testo. La demo Usa -1 e + 1 per rappresentare le due classi possibili. Questa codifica è tipica per percettroni, ma le classi possono essere codificate come 0 e 1 invece (anche se questa codifica richiede alcune modifiche alla logica del codice).
Formazione viene preparata con queste istruzioni:
int[] a = new int[numTrain]; // "Wrong counters"
double sigma = 1.5; // For the kernel function
int maxEpoch = 10;
int epoch = 0;
Una contiene i contatori non corretti per ogni elemento di formazione come matrici e sigma è il parametro disponibile per la funzione kernel RBF. Il valore del controllo del ciclo maxEpoch e sigma individuati mediante tentativi ed errori. I valori di funzione kernel quindi, tutti i possibili sono pre-calcolati e archiviati in una matrice:
double[][] kernelMatrix = new double[numTrain][];
for (int i = 0; i < kernelMatrix.Length; ++i)
kernelMatrix[i] = new double[numTrain];
for (int i = 0; i < numTrain; ++i) {
for (int j = 0; j < numTrain; ++j) {
double k = Kernel(trainData[i], trainData[j], sigma);
kernelMatrix[i][j] = kernelMatrix[j][i] = k;
}
}
L'idea è che durante il training, la somiglianza kernel tra tutte le coppie di elementi di formazione dovrà essere utilizzato più volte, pertanto è sensato per pre-calcolare tali valori.
Il ciclo di formazione è:
while (epoch < maxEpoch) {
for (int i = 0; i < numTrain; ++i) {
// Get "desired" correct class into di
for (int j = 0; j < numTrain; ++j) {
// Get "other" desired class into dj
// Compute y = weighted sum of products
}
if ((di == -1 && y >= 0.0) || (di == 1 && y <= 0.0))
++a[i]; // increment wrong counter
}
++epoch;
}
La classe desiderata, corretta (-1 o + 1) viene estratto l'elemento corrente di formazione con questo codice:
int di = (int)trainData[i][numFeatures];
Di seguito viene utilizzato per l'acronimo di valore desiderato. Due altri nomi di variabili comuni sono t (per il valore di destinazione) e y (acronimo solo di output generale).
Interna annidato per ciclo che calcola la somma ponderata dei valori di kernel è il fulcro dell'algoritmo di apprendimento di percezione kernel:
double y = 0.0; // Weighted sum of kernel results
for (int j = 0; j < numTrain;; ++j) {
int dj = (int)trainData[j][numFeatures];
double kern = kernelMatrix[i][j];
y += a[j] * dj * kern;
}
Il codice demo calcola il kernel per tutte le coppie di elementi di formazione. Ma quando un contatore errato associato ha valore 0, il termine prodotto sarà pari a 0. Pertanto, un'importante ottimizzazione facoltativi quando il numero di elementi di training è di grandi dimensioni è da ignorare il calcolo del kernel quando il valore di [i] o [j] è 0. Allo stesso modo, gli elementi di formazione che hanno un valore di contatore errato 0 possono essere rimossa completamente.
Non calcolerò di una classe stimata esplicita poiché è più semplice verificare se la classe stimata è errata direttamente:
if ((di == -1 && y >= 0.0) || (di == 1 && y <= 0.0))
++a[i]; // wrong counter for curr data
È necessario prestare attenzione a controllare y > = 0,0 o y < = 0,0 anziché > 0,0 y o y < 0,0 perché la prima volta il ciclo di formazione, tutti errato valori dei contatori in di una matrice sono pari a zero e quindi la somma dei prodotti pesata saranno 0,0.
Una volta terminato il ciclo di formazione, la percezione del kernel è definito in modo efficace i dati di training, la matrice di contatore errato e il sigma parametro kernel RBF.
Esecuzione di stime
Funzione di supporto accuratezza esegue le stime. Definizione del metodo inizia con:
static double Accuracy(double[][] data, int[] a,
double[][] trainData, double sigma, bool verbose)
{
int numFeatures = data[0].Length - 1;
double[] x = new double[numFeatures];
int numCorrect = 0;
int numWrong = 0;
...
Il parametro denominato data contiene una matrice di matrici di matrici stile dei dati da valutare. Matrice di parametri a contiene i valori di contatore errato generati eseguendo il training.
All'interno del corpo della funzione, il codice è esattamente il codice di training, ma anziché incrementare un contatore errato per i dati di training corrente viene incrementato l'elemento in una stima errata, una variabile numWrong singolo o numCorrect:
if ((di == -1 && y >= 0.0) || (di == 1 && y <= 0.0))
++numWrong;
else
++numCorrect;
Dopo che sono stati esaminati tutti gli elementi di dati in corso il controllo, viene restituita la percentuale di stime corrette:
return (1.0 * numCorrect) / (numCorrect + numWrong);
Il metodo accuratezza ha un parametro verbose, determinando se true, le informazioni di diagnostica da visualizzare:
if (verbose == true)
{
Console.Write("Input: ");
for (int j = 0; j < data[i].Length - 1; ++j)
Console.Write(data[i][j].ToString("F1") + " ");
// Etc.
}
Utilizzare il codice dal metodo accuratezza, è possibile scrivere un metodo Predict dedicato che accetta una matrice di valori (senza una classe corretto noto), i dati di training, la matrice di contatore errato e il valore di sigma kernel RBF, che restituisce il valore di-1 stima o un + 1.
Conclusioni
Molto spesso non vengono utilizzati i percettroni kernel. Il problema è dovuto in gran parte al fatto che siano disponibili più potenti tecniche di classificazione binaria e che vi sia molta Mistero che circonda metodi kernel ML in generale. Se si esegue una ricerca Internet per i percettroni kernel, sono disponibili molti riferimenti che mostrano le relazioni matematiche accattivanti tra percettroni normali e kernel percettroni, ma poche informazioni di implementazione pratica. A mio parere, il valore della comprensione del kernel percettroni primaria è che la Knowledge Base rende più facile da comprendere più sofisticati i metodi kernel ML (che descriverò in un prossimo articolo).
Uno dei punti di debolezza del kernel percettroni è che per effettuare una stima, è necessario esaminare il set di dati di training intero (ad eccezione degli elementi che hanno un valore di contatore errato pari a 0). Se il set di training è enorme, questo potrebbe rendere impraticabile in alcuni scenari stime in tempo reale.
I percettroni kernel sono senza dubbio il tipo più semplice dei metodi kernel. Il trucco kernel può essere applicato a altri classificatori lineari. In effetti, applicare il trucco kernel a un classificatore lineare margine massimo costituisce la base per i classificatori di machine (SVM) vettore di supporto, che sono stati utilizzati di frequente nei 1990s tardiva.
Ripristino di emergenza. James McCaffreylavora per Microsoft Research a Redmond, Washington. Ha lavorato di diversi prodotti Microsoft, inclusi Internet Explorer e Bing. Dr. È possibile contattarlo McCaffrey jammc@microsoft.com.
Grazie per i seguenti esperti tecnici Microsoft che ha esaminato in questo articolo: ANI Anirudh e Chris Lee
Viene illustrato in questo articolo nel forum di MSDN Magazine