Лінійна сепарабельність

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

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

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

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

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

Приклади

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

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

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

Лінійна сепарабельність булевих функцій у n змінних

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

Кількість лінійно відокремлених булевих функцій для кожної розмірності послідовність A000609 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

Кількість змінних	Лінійно відокремлені булеві функції
2	14
3	104
4	1882
5	94572
6	15028134
7	8378070864
8	17561539552946
9	144130531453121108

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

Докладніше: Метод опорних векторів

H ₁ не розділяє набори. H ₂ розділяє, але лише з невеликим покращенням. H ₃ відокремлює їх з максимальною границею.

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

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

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

Див. також

• Персептрон
• ВЧ-розмірність

Примітки

1. Gruzling Nicolle. Linear separability of the vertices of an n-dimensional hypercube. M.Sc Thesis. — University of Northern British Columbia, 2006.