Ядро трюк отображает нелинейную задачу в линейную задачу.
Мои вопросы:
1. В чем основное отличие линейной и нелинейной задачи? Какова интуиция, лежащая в основе различия этих двух классов проблем? И как трюк ядра помогает использовать линейные классификаторы по нелинейной задаче?
2. Почему этот точечный продукт так важен в двух случаях?
Спасибо.
Многие классификаторы, среди которых линейная поддержка векторной машины (SVM), могут решать только проблемы, которые являются линейно разделяемыми, т.е. к классу 1 можно отделить от точек, принадлежащих классу 2 гиперплоскостью.
Во многих случаях проблема, которая не является линейно разделяемой, может быть решена путем применения преобразования phi() к точкам данных; это преобразование, как говорят, преобразует точки в пространство объектов. Надежда состоит в том, что в пространственном пространстве точки будут линейно разделяться. (Примечание: это еще не трюк с ядром... следите за обновлениями.)
Можно показать, что чем выше размерность пространства признаков, тем больше число проблем, которые линейно разделяются в этом пространстве. Поэтому в идеале желательно, чтобы пространство объектов было как можно более высоким.
К сожалению, по мере увеличения размера пространства функций, также требуется количество вычислений. В этом и заключается трюк ядра. Многие алгоритмы машинного обучения (в том числе SVM) могут быть сформулированы таким образом, что единственная операция, которую они выполняют в точках данных, является скалярным продуктом между двумя точками данных. (Я обозначаю скалярное произведение между x1 и x2 на <x1, x2>.)
Если мы преобразуем наши точки в пространство объектов, скалярное произведение теперь будет выглядеть так:
<phi(x1), phi(x2)>
Ключевым понятием является то, что существует класс функций, называемых ядрами, которые могут быть использованы для оптимизации вычисления этого скалярного произведения. Ядром является функция K(x1, x2), обладающая тем свойством, что
K(x1, x2) = <phi(x1), phi(x2)>
для некоторой функции phi(). Другими словами: мы можем оценить скалярное произведение в низкоразмерном пространстве данных (где x1 и x2 "жить" ), не переходя в пространственное пространственное пространство (где phi (x1) и phi (x2) "живут" ), но мы все же получаем преимущества преобразования в пространственное пространство с большими размерами. Это называется трюком ядра.
Многие популярные ядра, такие как гауссовское ядро фактически соответствуют преобразованию phi(), которое преобразуется в бесконечномерное пространственное пространство. Ядро-трюк позволяет вычислить скалярные произведения в этом пространстве без необходимости явно представлять точки в этом пространстве (что, очевидно, невозможно на компьютерах с конечным объемом памяти).
Когда люди говорят о линейной задаче относительно проблемы классификации, они обычно означают линейно разделяемую задачу. Линейно разделяемое означает, что существует некоторая функция, которая может разделять два класса, которые являются линейной комбинацией входной переменной. Например, если у вас есть две входные переменные, x1 и x2, то есть некоторые числа theta1 и theta2 такие, что функция theta1.x1 + theta2.x2 будет достаточной для прогнозирования вывода. В двух измерениях это соответствует прямой, в 3D она становится плоскостью, а в пространствах более высоких размеров она становится гиперплоскостью.
Вы можете получить какую-то интуицию об этих концептах, подумав о точках и строках в 2D/3D. Вот очень придуманная пара примеров...
Это график линейно неразрывной задачи. Нет прямой линии, которая может отделять красные и синие точки.
Однако, если мы даем каждой точке дополнительную координату (в частности, 1 - sqrt(x*x + y*y)... Я сказал вам, что это было надуманно), то проблема становится линейно отделимой, так как красные и синие точки могут быть разделены двумерной плоскостью пройдя через z=0.
Надеемся, что эти примеры демонстрируют часть идеи хитрости ядра:
Отображение проблемы в пространстве с большим числом измерений делает более вероятным, что проблема станет линейно разделяемой.
Вторая идея, лежащая в основе трюка ядра (и причина, почему это так сложно), заключается в том, что обычно очень сложно и вычислительно дорого работать в очень высокоразмерном пространстве. Однако, если алгоритм использует только точечные продукты между точками (которые вы можете рассматривать как расстояния), тогда вам нужно работать только с матрицей скаляров. Вы можете неявно выполнять вычисления в высокоразмерном пространстве, не имея при этом необходимости делать сопоставление или обрабатывать данные более высокого уровня.
Основное различие (для практических целей) заключается в следующем: линейная проблема либо имеет решение (а затем оно легко находит), либо вы получаете определенный ответ, что решения вообще нет. Вы знаете это много, прежде чем вы даже знаете проблему. Пока он линейный, вы получите ответ; быстро.
Интуиция заключается в том, что если у вас есть две прямые линии в каком-то пространстве, довольно легко увидеть, пересекаются они или нет, и если они это сделают, легко узнать, где.
Если проблема не линейна - ну, это может быть что угодно, и вы почти ничего не знаете.
Точечное произведение двух векторов означает только следующее: сумма произведений соответствующих элементов. Так что если ваша проблема
c1 * x1 + c2 * x2 + c3 * x3 = 0
(где вы обычно знаете коэффициенты c, и вы ищете переменные x), левая часть является точечным произведением векторов (c1,c2,c3) и (x1,x2,x3).
Вышеприведенное уравнение (в значительной степени) является самой проблемой линейной задачи, поэтому существует связь между точечным продуктом и линейными задачами.
Моя интуиция в этом вопросе больше основана на физике, поэтому мне сложно перевести ИИ.
Я думаю, что следующая ссылка также полезна...
http://www.simafore.com/blog/bid/113227/How-support-vector-machines-use-kernel-functions-to-classify-data