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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

Классификация данных это обычная задача в машинное обучениеПредположим, что даны некоторые точки данных, каждая из которых принадлежит одному из двух наборов, и мы хотим создать модель, которая будет определять, какой набор новый точка данных будет внутри. В случае опорные векторные машины, точка данных рассматривается как п-мерный вектор (список п числа), и мы хотим знать, можем ли мы разделить такие точки с помощью (п - 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 {х} _ {я}}$ принадлежит. Каждый ${ Displaystyle mathbf {х} _ {я}}$ это п-размерный настоящий вектор. Мы хотим найти гиперплоскость с максимальным запасом, которая разделяет точки, имеющие ${ 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}}}$.

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

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

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

Рекомендации