Введение
В евклидовой геометрии линейная разделимость — это свойство двух множеств точек. Это легче всего представить в двух измерениях (на евклидовой плоскости), рассматривая одно множество точек как окрашенное в синий цвет, а другое — в красный. Эти два множества линейно разделимы, если существует хотя бы одна прямая на плоскости, по одну сторону от которой находятся все синие точки, а по другую — все красные. Эта идея непосредственно обобщается на евклидовы пространства более высокой размерности, если прямую заменить гиперплоскостью. Задача определения линейной разделимости пары множеств и нахождения разделяющей гиперплоскости возникает в различных областях. В статистике и машинном обучении классификация определенных типов данных представляет собой задачу, для решения которой существуют эффективные алгоритмы, основанные на этой концепции.
Математическое определение
Пусть и будут двумя множествами точек в n-мерном евклидовом пространстве. Тогда и линейно разделимы, если существуют n + 1 действительных чисел , таких что каждая точка удовлетворяет , а каждая точка удовлетворяет , где – -я компонента .
Equivalently, two sets are linearly separable precisely when their respective convex hulls are disjoint (colloquially, do not overlap). In simple 2D, it can also be imagined that the set of points under a linear transformation collapses into a line, on which there exists a value, k, greater than which one set of points will fall into, and lesser than which the other set of points fall.
Эквивалентно, два множества линейно разделимы тогда и только тогда, когда их соответствующие выпуклые оболочки не пересекаются (в разговорном смысле, не перекрываются). В простейшем случае 2D можно также представить, что множество точек при линейном преобразовании сжимается в линию, на которой существует значение k, такое что все точки одного множества оказываются больше k, а все точки другого множества – меньше k.
Equivalently, two sets are linearly separable precisely when their respective convex hulls are disjoint (colloquially, do not overlap). In simple 2D, it can also be imagined that the set of points under a linear transformation collapses into a line, on which there exists a value, k, greater than which one set of points will fall into, and lesser than which the other set of points fall.
Примеры
Три неколлинеарные точки, принадлежащие двум классам ('+' и ' '), всегда линейно разделимы в двух измерениях. Это иллюстрируется тремя примерами на следующем рисунке (случай, когда все точки '+', не показан, но аналогичен случаю, когда все точки ' '):
Однако не все наборы из четырех точек, не лежащих на одной прямой, линейно разделимы в двух измерениях. Для следующего примера потребуется две прямые, и, следовательно, он не является линейно разделимым:
Обратите внимание, что три точки, лежащие на одной прямой и имеющие вид "+ ⋅ ⋅ ⋅ — ⋅ ⋅ ⋅ +", также не являются линейно разделимыми.
Количество линейных разделений
Пусть — число способов линейно раздели́ть N точек (в общем положении) в K измерениях. Тогда, когда K велико, очень близко к единице при , но очень близко к нулю при . Иными словами, один перцептрон почти наверняка может запомнить случайное присвоение бинарных меток N точкам при , но почти наверняка не может при .