свм для двоичных данных с расстоянием Хэмминга

Question

У меня стандартная проблема машинного обучения {-1, + 1}.Основное отличие состоит в том, что точки данных являются двоичными строками, поэтому их близость измеряется расстоянием Хэмминга.Может ли SVM применяться в этом случае?Какая библиотека SVM лучше подходит для этой задачи?

Answer 1

Если ядро ​​k положительно определено для любой пары примеров x и z, определитель матрицы грамм неотрицателен.

|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

Как и в StompChicken, неясно, является ли расстояние Хемминга допустимым ядром.

Если я что-то упускаю, я думаю, что это допустимое ядро, потому что это внутренний продукт в следующем пространстве: K ("aab", "baa") = [0,1,0,1,1 , 0] \ точка [1,0,0,1,0,1].

Поняв эту «кодировку», вы действительно можете использовать любую библиотеку SVM, которая поддерживает линейное ядро, кодировать ваши строки, как в предыдущем примере.

Answer 3

Это, вероятно, лучше всего обрабатывать с помощью библиотеки SVM, которая позволяет вам создавать собственные функции ядра (например, libSVM, SVMLight, scikits). Затем вам нужно написать функцию расстояния Хэмминга, чтобы вычислить расстояние между двумя строками, и подключить его как функцию ядра.

Единственная проблема в том, что я не уверен, что расстояние Хемминга на самом деле является ядром, поскольку в нем удовлетворяет условиям Мерсера . Это явно симметрично, но я не знаю, положительно ли оно определено.