我有一个标准的{-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一起使用,但是可以肯定的是,您失去了解决凸优化问题的好处。