0

I have a dataset from custom abstract objects and a custom distance function. Is there any good SVM libraries that allows me to train on my custom objects (not 2d points) and my custom distance function?

I searched the answers in this similar stackoverflow question, but none of them allows me to use custom objects and distance functions.

Community
  • 1
  • 1
Chan Kha Vu
  • 9,834
  • 6
  • 32
  • 64

2 Answers2

3

First things first.

SVM does not work on distance functions, it only accepts dot products. So your distance function (actually similarity, but usually 1-distance is similarity) has to:

  • be symmetric s(a,b)=s(b,a)
  • be positive definite s(a,a)>=0, s(a,a)=0 <=> a=0
  • be linear in first argument s(ka, b) = k s(a,b) and s(a+b,c) = s(a,c) + s(b,c)

This can be tricky to check, as you actually ask "is there a function from my objects to some vector space, phi such that s(phi(x), phi(y))" is a dot-product, thus leading to definition of so called kernel, K(x,y)=s(phi(x), phi(y)). If your objects are themselves elements of vector space, then sometimes it is enough to put phi(x)=x thus K=s, but it is not true in general.

Once you have this kind of similarity nearly any SVM library (for example libSVM) works with providing Gram matrix. Which is simply defined as

G_ij = K(x_i, x_j)

Thus requiring O(N^2) memory and time. Consequently it does not matter what are your objects, as SVM only works on pairwise dot-products, nothing more.

If you look appropriate mathematical tools to show this property, what can be done is to look for kernel learning from similarity. These methods are able to create valid kernel which behaves similarly to your similarity.

lejlot
  • 64,777
  • 8
  • 131
  • 164
  • Thanks. Actually my "objects" are samples (each of them is a set of sample values), and my "distance function" is a similarity metric between two sets of samples, thus, it is symmetric and positive definite, but i'm not sure about linearity in first argument because I can't define addition and multiplication operations. – Chan Kha Vu Dec 11 '15 at 10:50
  • Linearity is the most difficult part. What you can do is try to check empiricaly. Create Matrix of all pairwise similarities and check if it is a PSD Matrix. – lejlot Dec 11 '15 at 11:42
3

Check out the following:

  • MLPack: a lightweight library that provides lots of functionality.
  • DLib: a very popular toolkit that is used both in industry and academia.

Apart from these, you can also use Python packages, but import them from C++.

banach_tarski
  • 31
  • 2