machine-learning - svm 用于具有汉明距离的二进制数据

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) 不是一个实数值，因此它不是一个有效的内核。

除非我遗漏了什么，否则我认为它是一个有效的内核，因为它是以下空间中的内积：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 一起使用，但肯定会失去解决凸优化问题的好处。

Answer 2

这可能最好使用允许您创建自定义内核函数（例如 libSVM、SVMLight、scikits）的 SVM 库来处理。然后你必须编写一个汉明距离函数来计算两个字符串之间的距离并将其作为核函数插入。

唯一的问题是，我不确定汉明距离实际上是一个内核，因为它满足Mercer 的条件。它显然是对称的，但我不知道它是否是正定的。

Answer 3

本文提出了一种用于测量分类特征之间的汉明距离的核。只需用汉明替换标准指数内核中的欧几里德距离即可。

也可以将欧几里得距离和汉明距离组合到一个核中，这对于混合了连续变量和离散变量的数据集非常有用。

好消息是他们还证明了这个内核确实是正定的（第 14 页）。

Answer 4

就像 StompChicken 所说，目前尚不清楚汉明距离是否是有效的内核。

除非我遗漏了什么，否则我认为它是一个有效的内核，因为它是以下空间中的内积：K("aab","baa") = [0,1,0,1,1,0] \dot [1,0,0,1,0,1]。

在理解了这种“编码”之后，你可以真正使用任何支持线性内核的 SVM 库，像前面的例子一样对你的字符串进行编码。