SVM di base implementato in MATLAB

Question

Linearly Non-Separable Binary Classification Problem 

Prima di tutto, questo programma non funziona correttamente per RBF (gaussianKernel()) e voglio correggerlo.

Si tratta di una Demo SVM non lineare per illustrare la classificazione di 2 classi con l'applicazione di margine duro.

• Il problema riguarda dati bidimensionali casuali distribuiti in modo radiale.

• ho usato Quadratic Programmazione Risolutore per calcolare Lagrange moltiplicatori (alfa)

xn = input .* (output*[1 1]); % xiyi 
phi = gaussianKernel(xn, sigma2); % Radial Basis Function 

k  = phi * phi';     % Symmetric Kernel Matrix For QP Solver 
gamma = 1;       % Adjusting the upper bound of alphas 
f  = -ones(2 * len, 1);   % Coefficient of sum of alphas 
Aeq = output';     % yi 
beq = 0;       % Sum(ai*yi) = 0 
A  = zeros(1, 2* len);   % A * alpha <= b; There isn't like this term 
b  = 0;       % There isn't like this term 
lb = zeros(2 * len, 1);   % Lower bound of alphas 
ub = gamma * ones(2 * len, 1); % Upper bound of alphas 

alphas = quadprog(k, f, A, b, Aeq, beq, lb, ub); 

• per risolvere questo problema non classificazione lineare, ho scritto alcune funzioni del kernel, come gaussiana (RBF), funzioni kernel polinomiali omogenee e non omogenee.

Per RBF, ho implementato la funzione nell'immagine qui sotto:

Utilizzando Tylor di espansione della serie, se ne ricava:

E, io seperated il gaussiano kernel come questo:

K (x, x ') = phi (x)' * phi (x ')

L'attuazione di questo pensiero è:

function phi = gaussianKernel(x, Sigma2) 

gamma = 1/(2 * Sigma2); 
featDim = 10; % Length of Tylor Series; Gaussian Kernel Converge 0 so It doesn't have to Be Inf Dimension 
phi  = []; % Kernel Output, The Dimension will be (#Sample) x (featDim*2) 

    for k = 0 : (featDim - 1) 

     % Gaussian Kernel Trick Using Tylor Series Expansion 
     phi = [phi, exp(-gamma .* (x(:, 1)).^2) * sqrt(gamma^2 * 2^k/factorial(k)) .* x(:, 1).^k, ... 
      exp(-gamma .* (x(:, 2)).^2) * sqrt(gamma^2 * 2^k/factorial(k)) .* x(:, 2).^k]; 
    end 

end 

*** credo che la mia implementazione RBF è sbagliato, ma io don' t know come risolvere il problema. Per favore aiutami qui.

Ecco cosa ho ottenuto come output:

dove,

1) la prima immagine: Campioni di classi
2) La seconda immagine: Marcatura I vettori di supporto delle classi
3) La terza immagine: Aggiunta di dati di test a caso
4) La quarta immagine: Classificazione

Inoltre, ho implementato omogenea polinomiale Kernel "K (x, x ') =()^2", il codice è:

function phi = quadraticKernel(x) 

    % 2-Order Homogenous Polynomial Kernel 
    phi = [x(:, 1).^2, sqrt(2).*(x(:, 1).*x(:, 2)), x(:, 2).^2]; 

end 

e ho avuto sorprendentemente bello di uscita:

In sintesi, il programma funziona correttamente con l'utilizzo omogeneo kernel polinomiale, ma quando uso RBF, isn' t funzionare correttamente, c'è qualcosa di sbagliato con l'attuazione RBF.

Se sai di RBF (gaussiana Kernel) per favore fatemi sapere come posso fare bene ..

Edit: Se avete lo stesso problema, utilizzare RBF direttamente che definito sopra e non lo séparé dal phi.

Answer 1

Perché vuoi calcolare phi per il kernel gaussiano? Phi sarà un vettore a dimensione infinita e tu stai legando i termini della tua serie di Taylor a 10 quando non sappiamo nemmeno se 10 è sufficiente per approssimare i valori del kernel o no! Di solito, il kernel viene calcolato direttamente invece di ottenere phi (e il calcolo k). Ad esempio [1].

Questo significa che non dovremmo mai calcolare phi per gaussiano? Non proprio, no, ma dobbiamo essere leggermente più intelligenti a riguardo. Ci sono stati lavori recenti [2,3] che mostrano come calcolare phi per gaussiano in modo da poter calcolare matrici kernel approssimative pur avendo solo phi dimensionali finiti. Qui [4] do il codice molto semplice per generare il kernel approssimativo usando il trucco della carta. Tuttavia, nei miei esperimenti avevo bisogno di generare ovunque da 100 a 10000 phi dimensionali per essere in grado di ottenere una buona approssimazione del kernel (a seconda del numero di caratteristiche che l'input originale aveva e della velocità con cui gli autovalori del matrice originale si assottiglia).

Per il momento, utilizzare solo il codice simile a [1] per generare il kernel gaussiano e quindi osservare il risultato di SVM. Inoltre, giocare con il parametro gamma, un parametro gamma errato può comportare una classificazione davvero scadente.

[1] https://github.com/ssamot/causality/blob/master/matlab-code/Code/mfunc/indep/HSIC/rbf_dot.m

[2] http://www.eecs.berkeley.edu/~brecht/papers/07.rah.rec.nips.pdf

[3] http://www.eecs.berkeley.edu/~brecht/papers/08.rah.rec.nips.pdf

[4] https://github.com/aruniyer/misc/blob/master/rks.m

Answer 2

Dato che il kernel gaussiano viene spesso definito come mappatura a dimensioni infinito, ho sempre fiducia nelle sue capacità. Il problema qui potrebbe essere dovuto a un parametro errato, ma tenere sempre presente la ricerca della griglia è sempre necessario per l'addestramento SVM. Quindi ti propongo di dare un'occhiata a here dove potresti trovare alcuni trucchi per la regolazione dei parametri. La sequenza esponenziale crescente viene solitamente utilizzata come candidato.