Поднятие в более высокие измерения

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: насколько выразителен классификатор?

Размерность Vapnik-Chervonenkis (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 не линейно разделим. Машина не может его решить, не потому, что ей не хватает вычислительной мощности, а потому, что существует фундаментальная геометрическая несовместимость между классом гипотез и задачей.

Решение: многослойные сети могут представлять нелинейные границы. Скрытые слои реализуют отображение признаков φ — поднятие данных в более высокие измерения, где линейное разделение становится возможным. Каждый скрытый нейрон вычисляет одну гиперплоскость; комбинация нескольких гиперплоскостей приближает кривые.

Эта история соответствует замечанию Хэмминга: каждое ограничение машинного рассуждения имеет геометрическую структуру под собой. Задача не в том, чтобы спорить о том, могут ли машины 'думать', а в том, чтобы определить геометрические ограничения и найти способы их обойти.