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

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

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

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

Математическое определение [ править ]

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

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

Примеры [ править ]

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

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

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

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

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

Поддержка векторных машин [ править ]

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} }}$

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

См. Также [ править ]

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

Ссылки [ править ]