В евклидовой геометрии , линейная разделимость является свойством двух наборов точек . Это легче всего визуализировать в двух измерениях ( евклидова плоскость ), считая, что один набор точек окрашен в синий цвет, а другой набор точек - в красный. Эти два набора линейно разделимы, если существует хотя бы одна линия на плоскости со всеми синими точками на одной стороне и всеми красными точками на другой стороне. Эта идея немедленно распространяется на евклидовы пространства более высокой размерности, если прямая заменяется гиперплоскостью .
Проблема определения, является ли пара наборов линейно разделимой, и поиска разделяющей гиперплоскости, если они есть, возникает в нескольких областях. В статистике и машинном обучении классификация определенных типов данных является проблемой, для которой существуют хорошие алгоритмы, основанные на этой концепции.
Математическое определение
Позволять а также - два набора точек в n- мерном евклидовом пространстве. потом а также являются линейно разделимы , если существует п + 1 действительных чисел, так что каждая точка удовлетворяет и каждая точка удовлетворяет , где это -й компонент .
Эквивалентно, два набора линейно разделимы именно тогда, когда их соответствующие выпуклые оболочки не пересекаются (в просторечии не перекрываются). [ необходима цитата ]
Примеры
Три неколлинеарных точки в двух классах («+» и «-») всегда линейно разделимы в двух измерениях. Это проиллюстрировано тремя примерами на следующем рисунке (случай "+" не показан, но аналогичен случаю "-"):
Однако не все наборы из четырех точек, ни три коллинеарных, линейно разделимы в двух измерениях. В следующем примере потребуются две прямые линии, поэтому его нельзя разделить линейно:
Обратите внимание, что три точки, которые коллинеарны и имеют форму «+ ⋅⋅⋅ - ⋅⋅⋅ +», также не являются линейно разделимыми.
Линейная разделимость булевых функций от n переменных
Функции булева в п переменных можно рассматривать как присвоение 0 или 1 в каждую вершину булева гиперкуба в п измерений. Это дает естественное разделение вершин на два множества. Булева функция называется линейно разделимой, если эти два набора точек линейно разделимы. Количество различных булевых функций равногде n - количество переменных, переданных в функцию. [1]
Количество переменных | Логические функции | Линейно разделимые булевы функции |
---|---|---|
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) -мерной гиперплоскости . Это называется линейным классификатором . Есть много гиперплоскостей, которые могут классифицировать (разделять) данные. Один разумный выбор в качестве лучшей гиперплоскости - это та, которая представляет наибольшее разделение или запас между двумя наборами. Поэтому мы выбираем гиперплоскость так, чтобы расстояние от нее до ближайшей точки данных с каждой стороны было максимальным. Если такая гиперплоскость существует, она называется гиперплоскостью с максимальным запасом, а определяемый ею линейный классификатор называется классификатором максимального поля .
Более формально, учитывая некоторые данные обучения , набор из n точек вида
где y i равно 1 или -1, что указывает на набор, к которому точкапринадлежит. Каждыйявляется p -мерным вещественным вектором. Мы хотим найти гиперплоскость с максимальным запасом, которая разделяет точки, имеющие от тех, у кого есть . Любую гиперплоскость можно записать как набор точек удовлетворение
где обозначает скалярное произведение, а(не обязательно нормализованный) нормальный вектор к гиперплоскости. Параметр определяет смещение гиперплоскости от начала координат вдоль вектора нормали .
Если данные обучения линейно разделимы, мы можем выбрать две гиперплоскости таким образом, чтобы они разделяли данные и между ними не было точек, а затем попытаться максимизировать их расстояние.
Смотрите также
Рекомендации
- ^ 1962-, Рассел, Стюарт Дж. (2016). Искусственный интеллект - современный подход . Норвиг, Питер 1956- (Третье изд.). Бостон. п. 766. ISBN 978-1292153964. OCLC 945899984 .CS1 maint: числовые имена: список авторов ( ссылка )
- ^ Gruzling, Nicolle (2006). «Линейная отделимость вершин n-мерного гиперкуба. Дипломная работа». Университет Северной Британской Колумбии. Цитировать журнал требует
|journal=
( помощь )