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

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

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

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

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

Позволять ${\displaystyle X_{0}}$ и ${\displaystyle X_{1}}$ быть двумя наборами точек в п-мерное евклидово пространство. потом ${\displaystyle X_{0}}$ и ${\displaystyle X_{1}}$ находятся линейно отделимый если есть п + 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}$.

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

Примеры

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

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

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

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

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

Количество линейно разделимых булевых функций в каждом измерении^[2] (последовательность A000609 в OEIS )

Количество переменных	Логические функции	Линейно разделимые булевы функции
2	16	14
3	256	104
4	65536	1882
5	4294967296	94572
6	18446744073709552000	15028134
7	3.402823669 ×10^38	8378070864
8	1.157920892 ×10^77	17561539552946
9	1.340780792 ×10^154	144130531453121108

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

Основная статья: Машина опорных векторов

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

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

Более формально, учитывая некоторые данные обучения ${\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}}$

где у_я равно 1 или -1, что указывает на набор, к которому точка ${\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. 1962-, Рассел, Стюарт Дж. (2016). Искусственный интеллект - современный подход. Норвиг, Питер 1956- (Третье изд.). Бостон. п. 766. ISBN  978-1292153964. OCLC  945899984.
2. Gruzling, Nicolle (2006). «Линейная отделимость вершин n-мерного гиперкуба. Дипломная работа». Университет Северной Британской Колумбии.