Wie man einen Gaußschen Kernel effektiv in numpy berechnet [geschlossen]

12

Ich habe ein Numpy-Array mit m Spalten und n Zeilen, wobei die Spalten Dimensionen und die Zeilendatenpunkte sind.

Ich muss jetzt Kernelwerte für jede Kombination von Datenpunkten berechnen.

Für einen linearen Kernel kann ich einfach tunK(xi,xj)=xi,xjdot(X,X.T)

Wie kann ich effektiv alle Werte für den Gaußschen Kernel berechnen mit einem gegebenen s ?K(xi,xj)=expxixj22s2

Peter Smit
quelle
1
Nun, wenn Sie sich nicht zu sehr für einen Faktor zwei der Erhöhung der Berechnungen , können Sie immer einfach und dann wobei natürlich das te Element von . Dies ist jedoch wahrscheinlich auch nicht die numerisch stabilste. S=XXTK(xi,xj)=exp((Sii+Sjj2Sij)/s2)Sij(i,j)S
Kardinal
2
(Jahre später) Informationen zu großen, spärlichen Arrays finden Sie unter sklearn.metrics.pairwise.pairwise_distances.html in scikit-learn.
Denis

Antworten:

26

Ich denke, das Hauptproblem besteht darin, die paarweisen Abstände effizient zu ermitteln. Sobald Sie das haben, ist der Rest elementweise.

Dazu möchten Sie wahrscheinlich scipy verwenden. Die Funktion scipy.spatial.distance.pdistmacht das, was Sie brauchen, und scipy.spatial.distance.squareformwird möglicherweise Ihr Leben erleichtern.

Wenn Sie also die Kernel-Matrix möchten, tun Sie dies

from scipy.spatial.distance import pdist, squareform
  # this is an NxD matrix, where N is number of items and D its dimensionalites
X = loaddata() 
pairwise_dists = squareform(pdist(X, 'euclidean'))
K = scip.exp(-pairwise_dists ** 2 / s ** 2)

Dokumentation finden Sie hier

bayerj
quelle
3
Es scheint mir, dass Bayerjs Antwort einige kleine Änderungen erfordert, um der Formel zu entsprechen, falls jemand anderes sie benötigt:K = scipy.exp(-pairwise_dists**2 / s**2)
Chloe
Wenn jemand neugierig ist, ist der von verwendete Algorithmus pdistsehr einfach: Es ist nur eine C-implementierte Schleife, die Entfernungen auf offensichtliche Weise direkt berechnet , wobei die Schleife hier durchgeführt wird . Keine ausgefallene Vektorisierung oder irgendetwas anderes, was der Compiler automatisch erreichen kann.
Dougal
11

Als kleiner Nachtrag zu Bayerjs Antwort kann die pdistFunktion von scipy direkt euklidische Normen berechnen, indem sie als bezeichnet wird pdist(X, 'sqeuclidean'). Der vollständige Code kann dann effizienter geschrieben werden als

from scipy.spatial.distance import pdist, squareform
  # this is an NxD matrix, where N is number of items and D its dimensionalites
X = loaddata() 
pairwise_sq_dists = squareform(pdist(X, 'sqeuclidean'))
K = scip.exp(-pairwise_sq_dists / s**2)
Tenedor
quelle
1
Oder einfach pairwise_sq_dists = cdist(X, X, 'sqeuclidean')das gibt das gleiche.
user1721713
5

Sie können die quadratische Form auch von Hand schreiben:

import numpy as np
def vectorized_RBF_kernel(X, sigma):
    # % This is equivalent to computing the kernel on every pair of examples
    X2 = np.sum(np.multiply(X, X), 1) # sum colums of the matrix
    K0 = X2 + X2.T - 2 * X * X.T
    K = np.power(np.exp(-1.0 / sigma**2), K0)
    return K

PS, aber das funktioniert 30% langsamer

spetz911
quelle
Dies ist die von Kardinal in den Kommentaren vorgeschlagene Methode, die durch Inplace-Operationen etwas beschleunigt werden könnte. So macht es Scikit-Learn mit einem einsumAnruf für Sie X2.
Dougal
4
def my_kernel(X,Y):
    K = np.zeros((X.shape[0],Y.shape[0]))
    for i,x in enumerate(X):
        for j,y in enumerate(Y):
            K[i,j] = np.exp(-1*np.linalg.norm(x-y)**2)
    return K

clf=SVR(kernel=my_kernel)

das ist gleich

clf=SVR(kernel="rbf",gamma=1)

Sie können den RBF effektiv aus dem obigen Code berechnen. Beachten Sie, dass der Gammawert 1 ist, da es sich um eine Konstante handelt. Das von Ihnen angeforderte s ist ebenfalls dieselbe Konstante.

John
quelle
Willkommen auf unserer Webseite! Wir haben einen etwas anderen Schwerpunkt als Stack Overflow, da wir uns im Allgemeinen weniger auf Code als auf zugrunde liegende Ideen konzentrieren. Daher kann es sich lohnen, Ihren Code mit Anmerkungen zu versehen oder eine kurze Vorstellung von den wichtigsten Ideen zu geben andere Antworten haben getan. Das würde helfen zu erklären, wie sich Ihre Antwort von den anderen unterscheidet.
Silverfish
Dies ist viel langsamer als die anderen Antworten, da Python-Schleifen anstelle der Vektorisierung verwendet werden.
Dougal
-1

Ich denke, das wird helfen:

def GaussianKernel(v1, v2, sigma):
    return exp(-norm(v1-v2, 2)**2/(2.*sigma**2))
Kernel
quelle
3
Willkommen auf der Website @Kernel. Sie können Mathematik anzeigen, indem Sie den Ausdruck zwischen $ -Zeichen setzen und eine LateX-ähnliche Syntax verwenden. Sie können Code (mit Syntaxhervorhebung) anzeigen, indem Sie die Zeilen um 4 Leerzeichen einrücken. Formatierungsrichtlinien finden Sie in der Hilfe zur Markdown-Bearbeitung und allgemeinere in der FAQ .
Antoine Vernet
1
Entspricht dies nicht nur dem, was in Frage kommt?
whuber