machine-learning - 具有汉明距离的二进制数据的支持向量机

Question

我有一个标准的 {-1,+1} 机器学习问题。主要区别在于数据点是二进制字符串，因此它们的接近度通过汉明距离来衡量。在这种情况下可以应用SVM吗？哪个 SVM 库更适合这项任务？

Answer 1

如果核 k 对于任何一对示例 x 和 z 都是正定的，则​​ gram 矩阵的行列式是非负的。

|k(x, x) k(x, z)|
|               | = k(x,x)k(z,z) - k(x,z)^2 >= 0
|k(z, x) k(z, z)|

对于距离(包括汉明距离)，以下属性成立:

For any x, y:

1) d(x, z) >= 0 and d(x, z) = 0 <=> x = z
2) symmetry d(x, z) = d(z, x)
3) triangular inequality d(x, z) <= d(x, y) + d(y, z)

将 k 视为汉明距离，根据 1)，我们将得到:

a) k(x,x) = k(z,z) = 0

但是为了成为正定核，我们需要:

b) k(x,x)k(z,z) - k(x,z)^2 >= 0

应用 a) 到 b) 我们有:

-k(x,z)^2 >= 0
k(x,z)^2 <= 0

这意味着 k(x,z) 不是一个真实值，因此它不是一个有效的内核。

Unless I'm missing something, I think it is a valid kernel, because it is an inner product in the following space: K("aab","baa") = [0,1,0,1,1,0] \dot [1,0,0,1,0,1].

这是定义内核特征的好方法，但它不是汉明距离。“aab”和“baa”之间的汉明距离为2，第一个和第三个字符不同。但是

[0,1,0,1,1,0] \dot [1,0,0,1,0,1] = 1.

如果汉明实例不是正定的，并不意味着它不能与 SVM 一起使用，但肯定会失去解决凸优化问题的好处。