Метрические пространства

Почему Q-learning находит оптимальную политику? Почему метод Ньютона сходится квадратично? Почему Wasserstein GAN стабильнее обычного? За всем этим - теорема Банаха о неподвижной точке в метрическом пространстве. Метрика - это язык, на котором написана сходимость. Оператор Беллмана с gamma = 0.99 - сжатие с коэффициентом 0.99: через 1000 шагов ошибка уменьшается примерно в 4.3 * 10^-5 раз. Вот почему RL работает. Вот почему метрика важна.

• **Обучение с подкреплением:** оператор Беллмана - контракция с коэффициентом gamma; теорема Банаха гарантирует единственность оптимальной функции ценности и сходимость value iteration
• **Wasserstein GAN:** метрика Wasserstein на распределениях + Lipschitz-ограничение на дискриминатор = контракция; именно поэтому WGAN стабильнее классического
• **Метод Ньютона:** квадратичная сходимость - следствие того, что метод является контракцией в окрестности корня с коэффициентом q ~ 0 (почти мгновенное сжатие)
• **Липшицевые нейросети:** ограничение ||f(x)-f(y)|| <= L||x-y|| в WGAN и robust ML - это требование метрической совместимости в духе контракций Банаха
• **Расстояние Фреше (FID):** метрика на пространстве кривых, используемая в trajectory similarity и оценке качества генеративных моделей

Предварительные знания

• Связность и компактность

Определение метрического пространства

Расстояние - интуитивная идея. Метрическое пространство определяет его аксиомами. **Пара (X, d)**, где d: X x X -> R - метрика, удовлетворяющая четырём аксиомам: (M1) d(x,y) >= 0; (M2) d(x,y) = 0 тогда и только тогда, когда x = y; (M3) d(x,y) = d(y,x); (M4) d(x,z) <= d(x,y) + d(y,z). Нарушь любую - и алгоритмы, которые опираются на метрику, сломаются.

**Косинусная схожесть - не метрика.** 1 - cos(x,y) нарушает M2 без нормировки: два ненулевых вектора с одинаковым направлением дают расстояние 0, но x не равно y. Именно поэтому kNN с косинусной мерой ведёт себя иначе, чем kNN с евклидовой: они буквально живут в разных пространствах.

Разные метрики могут порождать одну и ту же топологию. Такие метрики называют **эквивалентными**: L1, L2 и L-inf на R^n эквивалентны, хотя числа расстояний различаются. Что меняется при замене метрики: геометрия шаров и, как следствие, понятие ближайшего соседа.

Шары и открытые множества

**Открытый шар** радиуса r > 0 с центром x: B(x, r) = {y : d(x, y) < r}. Замкнутый шар: B_closed(x, r) = {y : d(x, y) <= r}. Открытые шары образуют базу топологии: множество U открыто тогда и только тогда, когда в каждой точке U есть шар, целиком помещающийся в U.

**Шар не обязан выглядеть круглым.** В дискретной метрике (d(x,y) = 0 если x = y, иначе 1): B(x, 0.5) = {x} (одна точка), B(x, 2) = X (всё пространство). В метрике на графе шар - множество вершин в пределах расстояния r по рёбрам. Форма шара полностью определяется метрикой.

**Adversarial attacks и форма шара.** Adversarial perturbation в рамках L-inf epsilon-шара означает: изменить каждый пиксель не более чем на epsilon. Это квадрат в пространстве пикселей. L2-атака - круг. L1-атака - ромб. WGAN использует шары в метрике Wasserstein - совсем другая геометрия. Выбор метрики - это выбор того, что считать атакой.

Сходимость и полнота

Последовательность (x_n) **сходится** к x, если d(x_n, x) -> 0 при n -> бесконечность: для любого eps > 0 существует N такое, что d(x_n, x) < eps при всех n > N. Предел единственен - следствие хаусдорфовости. Это тот же epsilon-N язык, что в обычном матанализе, только расстояние теперь - произвольная метрика.

**Последовательность Коши:** (x_n) - фундаментальная (Коши), если d(x_n, x_m) -> 0 при n, m -> бесконечность. Каждая сходящаяся - Коши. Обратное верно только в **полных** пространствах. **Полнота:** (X, d) полно, если каждая последовательность Коши сходится. Полнота = нет «дыр», куда может провалиться алгоритм.

Полнота определяет, работает ли итеративный алгоритм в данном пространстве. Численные методы анализируются в полных пространствах - банаховых и гильбертовых. Пространство L^2(R) - основа теории сигналов, квантовой механики и анализа сходимости нейросетей (gradient flow).

Теорема Банаха о неподвижной точке

**Теорема Банаха:** Если (X, d) - полное метрическое пространство и T: X -> X - **сжимающее отображение** (существует 0 <= q < 1 такое, что d(Tx, Ty) <= q * d(x,y) для всех x, y), то T имеет единственную неподвижную точку x* = T(x*), и итерации x_{n+1} = T(x_n) сходятся к x* из любой начальной точки.

**Скорость сходимости:** d(x_n, x*) <= q^n / (1-q) * d(x_1, x_0). Геометрическая скорость: каждая итерация умножает ошибку на q < 1. Оператор Беллмана с gamma = 0.99 - сжатие с коэффициентом 0.99. Через 1000 шагов ошибка уменьшается в 0.99^1000 примерно в 4.3 * 10^-5 раз. Вот почему RL-агенты сходятся.

**Контракции в ML и численном анализе.** Оператор Беллмана (RL, gamma < 1) - сжатие в sup-норме. Метод Ньютона на строго выпуклых функциях - сжатие в окрестности корня, поэтому квадратичная сходимость. Wasserstein GAN с Lipschitz-ограничением (||f(x)-f(y)|| <= L||x-y||) - чтобы дискриминатор был контракцией. Якоби и Гаусс-Зейдель для СЛАУ - контракции при диагональном доминировании. Теорема Банаха объясняет их всех.

Теорема Банаха даёт три вещи сразу: существование решения, единственность и конструктивный алгоритм с оценкой скорости. Именно эта тройка нужна практику при разработке итеративных методов - не просто «решение есть», а «вот алгоритм и вот гарантия».

Ключевые идеи

• **Метрика d:** 4 аксиомы (неотрицательность, тождество, симметрия, треугольник); L1/L2/L-inf - эквивалентные метрики на R^n с разной геометрией шаров; косинусная схожесть - не метрика
• **Шары B(x,r):** база топологии; форма шара полностью определяется метрикой; adversarial epsilon-шары в L-inf, L2, L1 - разные объекты
• **Полнота:** каждая последовательность Коши сходится; R и L^2 полны, Q и C([0,1]) с L2-нормой - нет; полнота гарантирует нет дыр для итеративных алгоритмов
• **Теорема Банаха:** сжимающее T на полном (X,d) имеет единственную неподвижную точку; итерации T^n(x_0) -> x* с геометрической скоростью q^n; Беллман, Ньютон, Якоби - все здесь

Связанные темы

Метрические пространства - специальный случай топологических с дополнительной структурой для анализа сходимости:

• Компактность — В метрических пространствах компактность эквивалентна последовательной компактности (Больцано-Вейерштрасс)
• Многообразия — Риманово многообразие - метрическое пространство с гладкой структурой; геодезические обобщают прямые

Вопросы для размышления

• Докажи, что замкнутое подпространство полного метрического пространства тоже полно. Что это означает для замкнутых выпуклых множеств в L^2?
• Метод Ньютона: x_{n+1} = x_n - f(x_n)/f'(x_n). При каком условии это контракция и почему сходимость квадратичная, а не линейная?
• C([0,1]) с sup-нормой полно, с L2-нормой - нет. Что изменится, если ограничиться полиномами степени <= n?

Связанные уроки

• top-03 — Компактность и связность - предыдущий урок
• top-05 — Следующий шаг: топологические группы и однородные пространства
• fa-01 — Банахово пространство = полное нормированное - метрика из нормы
• la-01-vectors-intro
• stats-21