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

最佳答案

如果对于任何一对示例x和z,核k为正定,则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] \点[1,0,0,1,0,1]。


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


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


如果海明实例不是正定的,则​​并不意味着它不能与SVM一起使用,但是可以肯定的是,您失去了解决凸优化问题的好处。

07-24 09:51
查看更多