Лінійна сепарабельність в евклідовій геометрії — це геометрична властивість пари множин точок. Цю властивість легко унаочнити у двовимірному випадку ( евклідової площини). Нехай один набір точок буде пофарбований у синій колір, а інший набір точок буде пофарбований у червоний. Ці два набори є «лінійно відокремленими», якщо в площині існує принаймні одна пряма яка розділяє сині і червоні точки. Тобто всі сині точки розташовані по один бік від прямої, а всі червоні точки на іншому боці. Ця ідея очевидно узагальнюється на евклідові простори більшої розмірності, якщо пряму замінити на гіперплощину.

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

Математичне визначення

Нехай і - два набори точок в n-мірному евклідовому просторі. Тоді і є лінійно відокремленими, якщо існує n + 1 дійсне число , так що кожна точка задовольняє , і кожна точка задовольняє , де є -ю компонентою .

Аналогічно, два набори лінійно відокремлюються точно, коли їхні відповідні опуклі оболонки - це неперетинні множини.

Приклади

Три не-колініарних точки у двох класах ('+' та '-') завжди лінійно розділяються в двох вимірах. Це проілюстровано на трьох прикладах на наступному малюнку (усі праві "+" не відображаються, але схожі на всі "-"):

VC1.svg VC2.svg VC3.svg

Проте не всі набори з чотирьох точок, три з яких не колінеарні, лінійно розділяються в двох вимірах. Наступний приклад потребує двох прямих ліній і таким чином не може бути лінійно відокремлений:

VC4.svg

Також, зверніть увагу, що три колінеарні точки форми "+ ⋅⋅⋅ — ⋅⋅⋅ +" також не лінійно відокремлюються.

Метод опорних векторів

Докладніше: Метод опорних векторів
H 1 не розділяє набори. H 2 розділяє, але лише з невеликим покращенням. H 3 відокремлює їх з максимальною границею.

Класифікація даних - загальне задача у машинному навчанні. Припустимо, що вказуються деякі набори даних, кожен з яких належить до одного з двох наборів, і ми хочемо створити модель, яка вирішить, якою буде ​ нова точка даних. У випадку методу опорних векторів, точка даних розглядається як вектор розмірності p (список з p чисел), і ми хочемо дізнатись, чи можемо ми розділити ці точки (p − 1)-мірною гіперплощиною. Це називається лінійним класифікатором. Є багато гіперплощин, які можуть класифікувати (розділяти) дані. Розумний вибір найкращої гіперплощини, - це той, який дає найбільше відокремлення між двома наборами. Таким чином, ми вибираємо гіперплощину так, щоб відстань була максимальна як від неї, так і до найближчої точки даних з кожної сторони. Якщо така гіперплощина існує, вона відома як "максимальна розділова гіперплощина", а лінійний класифікатор, який він визначає, відомий як «максимальний класифікатор розділення [en] ». Більш формально, з урахуванням деяких тренувальних даних , набір n точок форми

де yi це - 1 або -1, що вказує на набір, до якого належить точка . Кожен - це p -мірний вектор Дійсних чисел. Ми хочемо знайти максимально розділова гіперплощину, яка розподіляє точки з з тих, що мають . Будь-яку гіперплощину можна записати як набір точок , що задовольняють

де позначає cкалярний добуток і (необов'язково нормований) вектор нормалі до гіперплощини. Параметр визначає зміщення гіперплощини від початку вздовж вектора нормалі .

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


У цій статті використовується матеріал з статті Вікіпедії Лінійна сепарабельність, який випущений під Creative Commons Attribution-Share-Alike License 3.0.