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

Нехай ${\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 змінних можна вважати присвоюванням 0 або 1 для кожної вершини булевої гіперплощини розміру n. Це дає природний поділ вершин на дві множини. Булева функція вважається лінійно відокремленою, якщо ці два набори точок лінійно розділяються.

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

Класифікація даних - загальне задача у машинному навчанні. Припустимо, що вказуються деякі набори даних, кожен з яких належить до одного з двох наборів, і ми хочемо створити модель, яка вирішить, якою буде ​ нова точка даних. У випадку методу опорних векторів, точка даних розглядається як вектор розмірності p (список з p чисел), і ми хочемо дізнатись, чи можемо ми розділити ці точки (p − 1)-вимірною гіперплощиною. Це називається лінійним класифікатором. Є багато гіперплощин, які можуть класифікувати (розділяти) дані. Розумний вибір найкращої гіперплощини, - це той, який дає найбільше відокремлення між двома наборами. Таким чином, ми вибираємо гіперплощину так, щоб відстань була максимальна як від неї, так і до найближчої точки даних з кожної сторони. Якщо така гіперплощина існує, вона відома як "максимальна розділова гіперплощина", а лінійний класифікатор, який він визначає, відомий як «максимальний класифікатор розділення ». Більш формально, з урахуванням деяких тренувальних даних ${\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 }$ позначає cкалярний добуток і ${\displaystyle {\mathbf {w} }}$ (необов'язково нормований) вектор нормалі до гіперплощини. Параметр ${\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}}$ визначає зміщення гіперплощини від початку вздовж вектора нормалі ${\displaystyle {\mathbf {w} }}$.

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

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