Разница между линейной задачей и нелинейной задачей? Суть Dot-Product и Трюк с Ядром

Question

Трюк с ядром переводит нелинейную задачу в линейную задачу.

Мои вопросы:
1. В чем основное отличие линейной задачи от нелинейной? Какова интуиция, лежащая в основе различия этих двух классов проблем? И как уловка ядра помогает использовать линейные классификаторы в нелинейной задаче?
2. Почему скалярное произведение так важно в обоих случаях?

Спасибо.

Answer 1

Когда люди говорят о линейной задаче относительно проблемы классификации, они обычно имеют в виду линейно отделимую проблему. Линейное разделение означает, что существует некоторая функция, которая может разделять два класса, которая является линейной комбинацией входной переменной. Например, если у вас есть две входные переменные x1 и x2, существует несколько чисел theta1 и theta2, так что функции theta1.x1 + theta2.x2 будет достаточно для прогнозирования выходных данных. В двух измерениях это соответствует прямой линии, в 3D она становится плоскостью, а в пространствах более высоких измерений она становится гиперплоскостью .

Вы можете получить некоторую интуицию об этих понятиях, думая о точках и линиях в 2D / 3D. Вот очень надуманная пара примеров ...

Это сюжет линейно неразделимой проблемы. Нет прямой линии, которая могла бы разделить красные и синие точки.

Однако, если мы дадим каждой точке дополнительную координату (в частности, 1 - sqrt(x*x + y*y) ... я же говорил, что она придумана), тогда проблема станет линейно разделимой, поскольку красные и синие точки могут быть разделены двухмерной плоскостью. проходит через z=0.

Надеемся, что эти примеры демонстрируют часть идеи, лежащей в основе уловки ядра:

Отображение задачи в пространство с большим числом измерений повышает вероятность того, что проблема станет линейно отделимой.

Вторая идея, лежащая в основе трюка с ядром (и причины, по которой он так сложен) заключается в том, что работать в очень многомерном пространстве обычно очень неудобно и вычислительно дорого. Однако если алгоритм использует только точечные произведения между точками (которые вы можете рассматривать как расстояния), то вам нужно работать только с матрицей скаляров. Вы можете неявно выполнять вычисления в многомерном пространстве без необходимости фактически выполнять сопоставление или обработку многомерных данных.

Answer 2

Многие классификаторы, в том числе линейная машина опорных векторов (SVM) , могут решать только задачи, которые линейно отделимы, т. Е. Где точки, принадлежащие к классу 1, могут быть отделены от точек, принадлежащих к классу 2 по гиперплоскости.

Во многих случаях проблему, которая не является линейно разделимой, можно решить, применив преобразование phi () к точкам данных; говорят, что это преобразование преобразует точки в пространство признаков . Надежда состоит в том, что в пространстве признаков точки будут линейно разделены. (Примечание: это еще не трюк с ядром ... следите за обновлениями.)

Можно показать, что чем выше размерность пространства признаков, тем больше число задач, линейно разделимых в этом пространстве. Поэтому в идеале хотелось бы, чтобы пространство элементов было как можно более масштабным.

К сожалению, по мере того, как размер пространства пространственных объектов увеличивается, увеличивается и объем необходимых вычислений. Вот тут-то и кроется хитрость ядра. Многие алгоритмы машинного обучения (среди них SVM) могут быть сформулированы таким образом, что единственная операция, которую они выполняют над точками данных, - это скалярное произведение между двумя точками данных. (Я буду обозначать скалярное произведение между x1 и x2 как <x1, x2>.)

Если мы преобразуем наши точки в пространство признаков, скалярное произведение теперь будет выглядеть так:

<phi(x1), phi(x2)>

Ключевое понимание заключается в том, что существует класс функций, называемый kernels , который можно использовать для оптимизации вычислений этого скалярного произведения. Ядро - это функция K(x1, x2), обладающая свойством

K(x1, x2) = <phi(x1), phi(x2)>

для некоторой функции phi (). Другими словами: мы можем оценить скалярное произведение в низкоразмерном пространстве данных (где x1 и x2 "живут") без необходимости преобразования в многомерное пространство признаков (где phi (x1) и phi (x2) "живут ") - но мы все же получаем преимущества от преобразования в пространство пространственных объектов. Это называется трюк с ядром .

Многие популярные ядра, такие как гауссово ядро ​​, на самом деле соответствуют преобразованию phi (), которое преобразуется в бесконечномерное пространство функций . Уловка ядра позволяет нам вычислять скалярные произведения в этом пространстве без необходимости явно представлять точки в этом пространстве (что, очевидно, невозможно на компьютерах с конечным объемом памяти).

Answer 3

Основное отличие (для практических целей) заключается в следующем: линейная задача либо имеет решение (и тогда его легко найти), либо вы получите определенный ответ, что решения вообще не существует. Вы знаете это очень много, еще до того, как узнаете проблему. Пока он линейный, вы получите ответ; быстро.

Интуиция, лежащая в основе этого, состоит в том, что если у вас есть две прямые линии в некотором пространстве, довольно легко увидеть, пересекаются ли они или нет, и если они делают, легко узнать, где.

Если проблема не является линейной - ну, это может быть что угодно, и вы почти ничего не знаете.

Точечное произведение двух векторов просто означает следующее: Сумма произведений соответствующих элементов. Так что, если ваша проблема

c1 * x1 + c2 * x2 + c3 * x3 = 0

(где вы обычно знаете коэффициенты c и ищете переменные x), левая часть - это произведение точек векторов (c1,c2,c3) и (x1,x2,x3).

Вышеприведенное уравнение (в значительной степени) само по себе является определением линейной задачи, поэтому существует ваша связь между точечным произведением и линейными задачами.

Answer 4

1. Линейные уравнения однородны, и применяется суперпозиция. Вы можете создавать решения, используя комбинации других известных решений; это одна из причин, почему преобразования Фурье так хорошо работают. Нелинейные уравнения не являются однородными, и суперпозиция не применяется. Нелинейные уравнения обычно должны решаться численно с использованием итерационных, инкрементальных методов.
2. Я не уверен, как выразить важность скалярного произведения, но он принимает два вектора и возвращает скаляр. Конечно, решение скалярного уравнения - это меньше работы, чем решение векторного или тензорного уравнения высшего порядка, просто потому, что приходится иметь дело с меньшим количеством компонентов.

Моя интуиция в этом вопросе больше основана на физике, поэтому мне трудно переводить на ИИ.

Answer 5

Я думаю, что следующая ссылка также полезна ...
http://www.simafore.com/blog/bid/113227/How-support-vector-machines-use-kernel-functions-to-classify-data