Support Vector Machine (SVM) for classification problem based on Earth Mover's Distance (EMD)

Question

I would like to run SVM for my classification problem using the Earth Mover's Distance (EMD) as a distance measurement. As I understood the documentation for Python scikit-learn (https://scikit-learn.org/stable/modules/svm.html#svm-kernels) it is possible to use custom kernel functions:

import numpy as np
from sklearn import svm

def my_kernel(X, Y):
    return np.dot(X, Y.T)

clf = svm.SVC(kernel=my_kernel)

Also there is a package with EMD implemented (https://pypi.org/project/pyemd/). I tried to run it similar as in example using my own data (below). I have distributions of eigenvalues. But there is an error and can't figure out what does it mean.

from pyemd import emd
from sklearn.svm import SVC
from sklearn.model_selection import train_test_split

# Construct train and test data
X = np.concatenate((eigs_ctrl_fmri, eigs_pat_fmri))
y = np.concatenate(([0] * eigs_ctrl_fmri.shape[0], [1] * eigs_pat_fmri.shape[0]))

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.30, random_state=42) # 70% training and 30% test

model_svm = SVC(kernel=emd)
model_svm.fit(X_train, y_train)

TypeError: emd() takes at least 3 positional arguments (2 given)

So, it means that for emd function we need one more argument. Example in documentation says that this is distance matrix:

from pyemd import emd
import numpy as np
first_histogram = np.array([0.0, 1.0])
second_histogram = np.array([5.0, 3.0])
distance_matrix = np.array([[0.0, 0.5],
                             [0.5, 0.0]])
emd(first_histogram, second_histogram, distance_matrix)

3.5

But how I should construct distance matrix for SVM model - in advance calculate the distance between all samples in my data? If it is, I don't really understand how I should provide an input to SVM model.

And one thing about EMD - why do I need the distance matrix to calculate the earth mover's distance? For me it looks strange that I need to calculate the distance and provide it as an input to the function which calculating the distance. I undertstand that I missing something in basic understanding the EMD principle and how to use it for SVM. Can somebody help me please with that?

Thank you for any info to boost my understanding!

Answer 1

pyemd has a different API than scikit-learn. Per the scikit-learn docs:

"Your kernel must take as arguments two matrices of shape (n_samples_1, n_features), (n_samples_2, n_features) and return a kernel matrix of shape (n_samples_1, n_samples_2)."

As you rightly point out, the EMD implemented by pyemd takes three arguments, but the distance_metric is not the distance matrix between the distributions. It defines the distance between the histogram bin edges, which is independent of the particular distribution.

If you want to use the EMD implemented by pyemd, I'd suggest wrapping it in another function so that you match the function signature expected by scikit-learn. That will require you to compute distance_metric in the wrapper and pass it as an argument to pyemd.emd(). Again, the distance_metric argument only depends on how you have chosen the bin edges for the discretized distribution.