Рішальні межи як гіперплощини
Двійковий класифікатор присвоює кожному вхідному значенню один з двох класів. Рішальна межа класифікатора розділяє простір вхідних значень на два регіони: один для кожного класу. Геометрія цієї межи визначає, які закономірності може навчитися класифікатор.
Гіперплощина в ℝ^n: набір всіх точок x, які задовольняють w·x + b = 0, де w — вектор ваги в ℝ^n, а b — скалярне зміщення. Гіперплощина має n−1 вимірів.
У 2D: гіперплощина — це лінія. У 3D: плоска площина. У n-D: плоский підпростір розмірності (n−1).
Перцептрон класифікує, обчислюючи w·x + b і повертаючи клас 1, якщо значення додатне, клас 0, якщо від'ємне. Його рішальна межа — гіперплощина.
Лінійна розділяємість
Набір даних лінійно розділюється в ℝ^n, якщо існує гіперплощина, яка розміщує всі точки класу 0 з одного боку й усі точки класу 1 з іншого. Це чисто геометрична властивість набору даних.
Тестування лінійної розділяємості
Набір даних логічного елемента AND у 2D: точки класу 0 в (0,0), (1,0), (0,1); точка класу 1 в (1,1). Цей набір даних лінійно розділюється.
Набір даних XOR у 2D: точки класу 0 в (0,0) і (1,1); точки класу 1 в (1,0) і (0,1). Ці два класи лежать на протилежних діагоналях.
Піднесення до вищих вимірів
XOR не лінійно розділюється у 2D. Розв'язання: змапуйте дані в простір вищої розмірності, де він стає лінійно розділяємим. Це основна ідея трюку з ядром.
Карта ознак: функція φ: ℝ^n → ℝ^m (m > n), яка трансформує кожну вхідну точку в представлення вищої розмірності.
Для XOR одна корисна карта ознак: φ(x₁, x₂) = (x₁, x₂, x₁x₂)
Це додає третій вимір z = x₁ × x₂. Точки XOR трансформуються в:
- (0,0) → (0, 0, 0), клас 0
- (1,0) → (1, 0, 0), клас 1
- (0,1) → (0, 1, 0), клас 1
- (1,1) → (1, 1, 1), клас 0
У 3D: точки класу 0 знаходяться в (0,0,0) і (1,1,1); точки класу 1 знаходяться в (1,0,0) і (0,1,0). Тепер знайдіть розділяючу площину.
Розділяюча площина в 3D
Після карти ознак φ(x₁, x₂) = (x₁, x₂, x₁x₂) дані XOR живуть у 3D. Гіперплощина у 3D має рівняння w₁x₁ + w₂x₂ + w₃z + b = 0.
Теорема Кавера: Чому високі вимірності допомагають
Теорема Кавера (1965): складна задача класифікації, розглянута у просторі високої розмірності, більш ймовірно буде лінійно розділяємою, ніж у просторі низької розмірності, за умови, що простір не густо заселений.
Неформальне твердження: якщо ви змапуєте n точок даних у простір розмірності d >> n, ймовірність того, що випадкове позначення лінійно розділюється, наближається до 1.
Формальна версія: для n точок у загальному положенні в ℝ^d кількість лінійно розділяємих дихотомій (призначень класів) дорівнює рівно 2 × Σ_{k=0}^{d} C(n−1, k) для d < n і дорівнює 2^n (всі дихотомії) для d ≥ n − 1.
Практичне наслідок: карта ознак φ, яка піднімає XOR до 3D, є спеціальним випадком цього загального принципу. Піднесення до вищих вимірів збільшує шанс розділяємості. Ціна: більше параметрів для підгонки, вищий ризик переневідповідності.
Компроміс Зміщення-Дисперсія як Геометрія
Рішальна межа низької розмірності (кілька параметрів): висока зміщення (не може захопити складні закономірності), низька дисперсія (стабільна за вибірками). Межа високої розмірності (багато параметрів): низька зміщення, висока дисперсія (може переневідповідати до шуму в навчальних даних).
Розмірність VC: Наскільки експресивний класифікатор?
Розмірність Вапніка-Червоненко (VC) класу гіпотез H вимірює, наскільки складний цей клас: найбільша кількість точок, які H може розбити (правильно класифікувати у всіх 2^n можливих позначеннях).
Перцептрон у ℝ^d: розмірність VC = d + 1. d-розмірна гіперплощина може розбити d + 1 точок (у загальному положенні), але не d + 2.
Розмірність VC визначає складність вибірки: щоб навчитися гіпотезі з помилкою узагальнення ε з ймовірністю 1 − δ, вам потрібно приблизно n ≥ (d × log(1/ε) + log(1/δ)) / ε зразків, де d — розмірність VC.
Рішальні межи & межи спроможності машини
Геометрія рішальних меж пов'язується безпосередньо з межами машинного розуміння Хеммінга.
Однорівневий перцептрон (класифікатор гіперплощини) не може розв'язати XOR. Це була критика Мінського та Папера щодо ранніх перцептронів у 1969 році. Геометричний аргумент: XOR не лінійно розділюється. Машина не може розв'язати його не через брак обчислювальної потужності, а через фундаментальну геометричну несумісність між класом гіпотез і задачею.
Розв'язання: багаторівневі мережі можуть представляти нелінійні межи. Приховані шари впроваджують карту ознак φ — піднесення даних до вищих вимірів, де лінійне розділення стає можливим. Кожен прихований нейрон обчислює одну гіперплощину; комбінація кількох гіперплощин наближується до кривих.
Ця історія відображається на спостереженні Хеммінга: кожна межа машинного розуміння має геометричну структуру під нею. Завдання не в тому, щоб сперечатися, чи можуть машини 'думати', а в тому, щоб визначити геометричні обмеження та знайти способи їх обходу.