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

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

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

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

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

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

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

Примеры

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

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

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

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

Позволять $T(N,K)$ — количество способов линейно разделить N точек (в общем положении) в K измерениях, тогда ^[2] $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.$ Когда К велико, $T(N,K)/2^{N}$ очень близко к тому, когда $N\leq 2K$ , но очень близко к нулю, когда $N>2K$ . Другими словами, одна единица перцептрона почти наверняка может запомнить случайное назначение двоичных меток в N точках, когда $N\leq 2K$ , но почти наверняка не тогда, когда $N>2K$ .

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

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

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

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

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

Количество линейно разделимых логических функций в каждом измерении ^[7] (последовательность 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

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

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

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

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

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

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

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

См. также

Ссылки

^ Бойд, Стивен; Ванденберге, Ливен (8 марта 2004 г.). Выпуклая оптимизация . Издательство Кембриджского университета. дои : 10.1017/cbo9780511804441 . ISBN 978-0-521-83378-3 .
^ Маккей, Дэвид (25 сентября 2003 г.). Теория информации, логический вывод и алгоритмы обучения . Издательство Кембриджского университета . п. 483. ИСБН 9780521642989 .
^ Рассел, Стюарт Дж. (2016). Искусственный интеллект – современный подход . Норвиг, Питер 1956- (Третье изд.). Бостон. п. 766. ИСБН 978-1292153964 . OCLC 945899984 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Мурога, Сабуро (1971). Пороговая логика и ее приложения . Нью-Йорк: Wiley-Interscience. ISBN 978-0-471-62530-8 .
^ Кнут, Дональд Эрвин (2011). Искусство компьютерного программирования . Река Аппер-Седл: Аддисон-Уэсли. стр. 75–79. ISBN 978-0-201-03804-0 .
^ Перейти обратно: ^а ^б Шима, Иржи; Орпонен, Пекка (1 декабря 2003 г.). «Вычисления общего назначения с использованием нейронных сетей: обзор результатов теории сложности» . Нейронные вычисления . 15 (12): 2727–2778. дои : 10.1162/089976603322518731 . ISSN 0899-7667 . ПМИД 14629867 . S2CID 264603251 .
^ Грузлинг, Николь (2006). «Линейная разделимость вершин n-мерного гиперкуба. Кандидатская диссертация» (Документ). Университет Северной Британской Колумбии.

[1] Бойд, Стивен; Ванденберге, Ливен (8 марта 2004 г.). Выпуклая оптимизация . Издательство Кембриджского университета. дои : 10.1017/cbo9780511804441 . ISBN 978-0-521-83378-3 .

[:2-2] Маккей, Дэвид (25 сентября 2003 г.). Теория информации, логический вывод и алгоритмы обучения . Издательство Кембриджского университета . п. 483. ИСБН 9780521642989 .

[3] Рассел, Стюарт Дж. (2016). Искусственный интеллект – современный подход . Норвиг, Питер 1956- (Третье изд.). Бостон. п. 766. ИСБН 978-1292153964 . OCLC 945899984 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[4] Мурога, Сабуро (1971). Пороговая логика и ее приложения . Нью-Йорк: Wiley-Interscience. ISBN 978-0-471-62530-8 .

[5] Кнут, Дональд Эрвин (2011). Искусство компьютерного программирования . Река Аппер-Седл: Аддисон-Уэсли. стр. 75–79. ISBN 978-0-201-03804-0 .

[:0-6] Перейти обратно: ^а ^б Шима, Иржи; Орпонен, Пекка (1 декабря 2003 г.). «Вычисления общего назначения с использованием нейронных сетей: обзор результатов теории сложности» . Нейронные вычисления . 15 (12): 2727–2778. дои : 10.1162/089976603322518731 . ISSN 0899-7667 . ПМИД 14629867 . S2CID 264603251 .

[7] Грузлинг, Николь (2006). «Линейная разделимость вершин n-мерного гиперкуба. Кандидатская диссертация» (Документ). Университет Северной Британской Колумбии.

[1]

[2]

[3]

[4]

[5]

[6]

[7]