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

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

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

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

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

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

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

В простом 2D можно также представить, что множество точек при линейном преобразовании схлопывается в линию, на которой существует значение k, больше которого попадет один набор точек, и меньше которого попадет другой набор точек.

Примеры

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

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

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

Количество линейных разделений

Пусть — число способов линейного разделения N точек (в общем положении) в K измерениях, тогда ^[2] Когда K велико, очень близко к единице при , но очень близко к нулю при . Другими словами, один персептронный блок почти наверняка может запомнить случайное назначение двоичных меток на N точках при , но почти наверняка нет при . ${\displaystyle T(N,K)}$ $${\displaystyle T(N,K)=\left\{{\begin{array}{cc}2^{N}&K\geq N\\2\sum _{k=0}^{K-1}\left({\begin{array}{c}N-1\\k\end{array}}\right)&K<N\end{array}}\right.}$$ ${\displaystyle T(N,K)/2^{N}}$ ${\displaystyle N\leq 2K}$ ${\displaystyle N>2K}$ ${\displaystyle N\leq 2K}$ ${\displaystyle N>2K}$

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

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

Такие функции также называются линейной пороговой логикой или персептронами . Классическая теория обобщена в ^[4] , как утверждает Кнут. ^[5]

Значение известно только с точностью до случая, но порядок величины известен довольно точно: он имеет верхнюю и нижнюю границу . ^[6] ${\displaystyle n=9}$ ${\displaystyle 2^{n^{2}-n\log _{2}n+O(n)}}$ ${\displaystyle 2^{n^{2}-n\log _{2}n-O(n)}}$

Задача NP-полна для того, чтобы решить, является ли булева функция, заданная в дизъюнктивной или конъюнктивной нормальной форме, линейно разделимой. ^[6]

Машины опорных векторов

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 {x} _{i}}$ ${\displaystyle \mathbf {x} _{i}}$ ${\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} }}$

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

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

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

Ссылки

1. Бойд, Стивен; Ванденберг, Ливен (2004-03-08). Выпуклая оптимизация. Cambridge University Press. doi :10.1017/cbo9780511804441. ISBN 978-0-521-83378-3.
2. Маккей, Дэвид (25.09.2003). Теория информации, вывод и алгоритмы обучения. Cambridge University Press . стр. 483. ISBN 9780521642989.
3. Рассел, Стюарт Дж. (2016). Искусственный интеллект: современный подход . Норвиг, Питер 1956- (Третье изд.). Бостон. стр. 766. ISBN 978-1292153964. OCLC  945899984.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
4. Мурога, Сабуро (1971). Пороговая логика и ее приложения . Нью-Йорк: Wiley-Interscience. ISBN 978-0-471-62530-8.
5. Кнут, Дональд Эрвин (2011). Искусство программирования . Верхняя Сэддл-Ривер: Addison-Wesley. С. 75–79. ISBN 978-0-201-03804-0.
6. Šíma, Jiří; Orponen, Pekka (2003-12-01). "Универсальные вычисления с нейронными сетями: обзор результатов теории сложности". Neural Computation . 15 (12): 2727–2778. doi :10.1162/089976603322518731. ISSN  0899-7667. PMID  14629867. S2CID  264603251.
7. Gruzling, Nicolle (2006). «Линейная отделимость вершин n-мерного гиперкуба. Диссертация на степень магистра наук» (Документ). Университет Северной Британской Колумбии.