Линейная разделимость - Linear separability

Наличие линии, разделяющей точки двух типов, означает, что данные линейно разделимы.

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

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

Математическое определение

Позвольте и быть двумя наборами точек в n- мерном евклидовом пространстве. Тогда и являются линейно разделимы , если существуют п + 1 действительные числа , такие , что каждая точка удовлетворяет и каждая точка удовлетворяет , где это -й компонент . ${\ displaystyle X_ {0}}$${\ displaystyle X_ {1}}$${\ displaystyle X_ {0}}$${\ displaystyle X_ {1}}$${\ displaystyle w_ {1}, w_ {2}, .., w_ {n}, k}$${\ Displaystyle х \ в X_ {0}}$${\ displaystyle \ sum _ {я = 1} ^ {n} w_ {i} x_ {i}> k}$${\ Displaystyle х \ в X_ {1}}$${\ Displaystyle \ сумма _ {я = 1} ^ {п} ш_ {я} х_ {я} <к}$${\ displaystyle x_ {i}}$${\ displaystyle i}$${\ displaystyle x}$

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

Примеры

Три неколлинеарных точки в двух классах («+» и «-») всегда линейно разделимы в двух измерениях. Это проиллюстрировано тремя примерами на следующем рисунке (случай "+" не показан, но аналогичен случаю "-"):

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

Обратите внимание, что три точки, которые коллинеарны и имеют форму «+ ⋅⋅⋅ - ⋅⋅⋅ +», также не являются линейно разделимыми.

Линейная отделимость булевых функций от n переменных

Функции булева в п переменных можно рассматривать как присвоение 0 или 1 в каждую вершину булева гиперкуба в п измерений. Это дает естественное разделение вершин на два множества. Булева функция называется линейно разделимой, если эти два набора точек линейно разделимы. Количество различных логических функций - это где n - количество переменных, переданных в функцию. ${\ displaystyle 2 ^ {2 ^ {n}}}$

Опорные векторные машины

H ₁ не разделяет наборы. H ₂ делает, но только с небольшим запасом. H ₃ разделяет их с максимальным запасом.

Классификация данных - обычная задача машинного обучения . Предположим, что даны некоторые точки данных, каждая из которых принадлежит одному из двух наборов, и мы хотим создать модель, которая будет решать, в каком наборе будет находиться новая точка данных. В случае машин опорных векторов точка данных рассматривается как p -мерный вектор (список из p чисел), и мы хотим знать, можем ли мы разделить такие точки с помощью ( p  - 1) -мерной гиперплоскости . Это называется линейным классификатором . Есть много гиперплоскостей, которые могут классифицировать (разделять) данные. Один разумный выбор в качестве лучшей гиперплоскости - это та, которая представляет наибольшее разделение или запас между двумя наборами. Поэтому мы выбираем гиперплоскость так, чтобы расстояние от нее до ближайшей точки данных с каждой стороны было максимальным. Если такая гиперплоскость существует, она называется гиперплоскостью с максимальным запасом, а определяемый ею линейный классификатор называется классификатором максимального поля .

Более формально, учитывая некоторые данные обучения , набор из n точек вида ${\ displaystyle {\ mathcal {D}}}$

${\ displaystyle {\ mathcal {D}} = \ left \ {(\ mathbf {x} _ {i}, y_ {i}) \ mid \ mathbf {x} _ {i} \ in \ mathbb {R} ^ {p}, \, y_ {i} \ in \ {- 1,1 \} \ right \} _ {i = 1} ^ {n}}$

где y _i равно 1 или -1, что указывает на набор, которому принадлежит точка . Каждый является p -мерным вещественным вектором. Мы хотим найти гиперплоскость с максимальным запасом, которая отделяет точки, имеющие, от тех, которые имеют . Любую гиперплоскость можно записать как множество точек, удовлетворяющих ${\ Displaystyle \ mathbf {х} _ {я}}$${\ Displaystyle \ mathbf {х} _ {я}}$${\ displaystyle y_ {i} = 1}$${\ displaystyle y_ {i} = - 1}$${\ displaystyle \ mathbf {x}}$

${\ displaystyle \ mathbf {w} \ cdot \ mathbf {x} -b = 0,}$

где обозначает скалярное произведение и (не обязательно нормализованный) вектор нормали к гиперплоскости. Параметр определяет смещение гиперплоскости от начала координат по вектору нормали . ${\ displaystyle \ cdot}$${\ displaystyle {\ mathbf {w}}}$${\ Displaystyle {\ tfrac {b} {\ | \ mathbf {w} \ |}}}$${\ displaystyle {\ mathbf {w}}}$

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

Смотрите также

• Теорема о разделении гиперплоскостей
• Теорема Кирхбергера
• Перцептрон
• Размерность Вапника – Червоненкиса

использованная литература