Измеримые функции

Риман режет ось x. Лебег режет ось y. Кажется, косметическая деталь - но за ней стоит принципиальное различие: {x : f(x) in [a, b]} - прообраз - должен быть измеримым множеством. Когда в PyTorch пишут E[L(theta)] и запускают loss.backward() - неявно предполагается, что функция потерь измерима относительно sigma-алгебры данных. Без этого expectation не определён. Никакого autograd. Никакого градиентного спуска.

• **E[L(theta)] в ML:** функция потерь должна быть измеримой относительно sigma-алгебры данных. Измеримость = можно брать интеграл = можно брать градиент. autograd молча предполагает это при каждом вызове .backward()
• **Индикаторные функции в классификации:** 1_{y_hat = y} - простая функция. Accuracy = integral 1_{y_hat = y} d(empirical measure). ROC AUC = интеграл Лебега от TPR по FPR - то есть интеграл от индикатора по мере
• **Сходимость SGD:** mini-batch gradient сходится к full gradient по мере (при убывающем шаге). Закон больших чисел - сходимость почти всюду. Центральная предельная теорема - слабая сходимость. Разные теоремы о разных типах сходимости

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

• Мера Лебега

Измеримые функции

Риман режет ось x на интервалы. Лебег режет ось y: группирует точки по значению функции - {x : f(x) ∈ [a, b]}. Это и есть прообраз. Чтобы измерить такое множество, оно должно принадлежать sigma-алгебре. Функции, у которых это выполняется для любого борелевского множества, называются измеримыми.

**Измеримая функция:** f: (X, F) -> (R, B(R)) измерима, если для любого B из B(R): f^{-1}(B) = {x in X : f(x) in B} in F Достаточно проверить на порождающем классе: f^{-1}((-inf, a]) in F для всех a in R.

В ML каждая функция потерь L(theta, x) должна быть измеримой относительно sigma-алгебры данных. Измеримость = интегрируемость = можно брать математическое ожидание. Без этого запись E[L(theta)] бессмысленна - интеграл Лебега просто не определён. autograd PyTorch неявно предполагает это при каждом вызове loss.backward().

Хорошая новость: все непрерывные функции автоматически измеримы - прообраз открытого множества при непрерывном отображении открыт, а открытые множества борелевские. Монотонные функции тоже измеримы: f^{-1}((-inf, a]) всегда интервал или луч. Измеримость замкнута под арифметикой: сумма, произведение, предел последовательности измеримых функций - измеримы.

Простые функции и аппроксимация

Индикаторные функции 1_A в задачах классификации - это и есть простые функции. ROC AUC вычисляется как интеграл от TPR по FPR - интеграл Лебега от простой функции. За этой формулой стоит конструкция, которую Лебег придумал в 1902 году.

**Простая функция** - измеримая функция s: X -> R, принимающая конечное число значений: s(x) = sum_{i=1}^{n} a_i * 1_{A_i}(x) где a_1,...,a_n - различные значения, A_i = {x : s(x) = a_i} in F - измеримые множества, {A_1,...,A_n} - разбиение X. **Интеграл:** integral s dmu = sum_i a_i * mu(A_i) - никаких пределов, чистая алгебра.

Отличие от ступенчатых функций Римана принципиальное: множества A_i - произвольные измеримые, не обязательно интервалы. Можно задать «ступеньку» на множестве всех иррациональных в [0, 1] - и интеграл по-прежнему определён и равен мере этого множества (то есть единице). Риман с такой задачей не справится.

**Теорема о приближении:** если f: X -> [0, inf] измерима, то существует последовательность простых функций s_n такая, что: 1. 0 <= s_1 <= s_2 <= ... <= f (монотонно возрастает) 2. s_n(x) -> f(x) для каждого x (поточечная сходимость) 3. Если f ограничена - сходимость равномерная

Типы сходимости

Когда в ML говорят «mini-batch gradient converges to full gradient» - какой именно тип сходимости имеется в виду? Ответ зависит от того, о чём идёт речь: о конкретных весах, о множестве мест где сходится, о средней ошибке. Теория меры различает четыре типа - и они не эквивалентны.

Четыре типа сходимости f_n -> f: 1. **Поточечная:** f_n(x) -> f(x) для каждого x in X 2. **Почти всюду (п.в.):** f_n(x) -> f(x) для всех x, кроме множества меры 0 3. **Равномерная:** sup_x |f_n(x) - f(x)| -> 0 4. **По мере:** mu({x : |f_n(x) - f(x)| > eps}) -> 0 для любого eps > 0

Закон больших чисел Колмогорова - это сходимость почти всюду: выборочное среднее сходится к E[X] для почти всех реализаций. Центральная предельная теорема - сходимость по распределению (слабее, чем по мере). SGD сходится по мере при убывающем шаге. Разные утверждения о разном - и теория меры разводит их по разным ящикам.

**Бегущий горб** - классический пример разрыва между сходимостью по мере и почти всюду. На [0,1] задаём f_n = 1_{I_n}, где интервалы I_n бегут по отрезку, сужаясь: [0,1], [0,1/2], [1/2,1], [0,1/3], [1/3,2/3], [2/3,1], ... Для каждой точки x: бесконечно много n с f_n(x) = 1 и бесконечно много n с f_n(x) = 0. Поточечной сходимости нет. Но длина I_n -> 0, поэтому lambda({x : |f_n(x) - 0| > 1/2}) = lambda(I_n) -> 0 - сходимость по мере к нулю есть.

Теорема Егорова соединяет два типа: если mu(X) < inf и f_n -> f почти всюду, то для любого delta > 0 найдётся множество E с mu(E) < delta такое, что на X \ E сходимость равномерна. На конечной мере почти всюду почти равномерно - за исключением сколь угодно малого остатка. Именно это используется при доказательстве теоремы Лебега о мажорируемой сходимости - основного инструмента обмена предела и интеграла в теореме сходимости SGD.

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

• **Измеримая функция** - f: X -> R, для которой прообраз любого борелевского множества лежит в F. Достаточно проверить на (-inf, a]. Непрерывные, монотонные, пределы измеримых - автоматически измеримы
• **Простая функция** - конечная линейная комбинация индикаторов: phi = sum a_i * 1_{A_i}. Интеграл = sum a_i * mu(A_i). Никаких пределов - чистая арифметика
• **Теорема о приближении:** любая неотрицательная измеримая функция - монотонный предел простых снизу. Это фундамент определения интеграла Лебега
• **Четыре типа сходимости** не эквивалентны: почти всюду, по мере, поточечная, равномерная. Теорема Егорова: на конечной мере почти всюду => почти равномерная

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

Измеримые функции - мост от sigma-алгебр к интегрированию:

• Мера Лебега — Измеримость функции определяется относительно sigma-алгебры, на которой живёт мера
• Интеграл Лебега — Строится через простые функции и предельный переход для неотрицательных измеримых
• Математическое ожидание — E[f(X)] = интеграл Лебега от f по мере распределения X

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

• Почему определение измеримости использует прообразы f^{-1}, а не образы f(A)? Что пошло бы не так с образами?
• loss.backward() в PyTorch работает даже для ReLU, несмотря на разрыв производной в нуле. Как это объясняется через понятие 'почти всюду'?
• Бегущий горб сходится по мере, но не поточечно. Можно ли построить последовательность, которая сходится поточечно почти всюду, но не по мере?

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

• mt-02 — Мера Лебега - среда, в которой живут измеримые функции
• mt-04 — Интеграл Лебега строится через простые функции из этого урока
• prob-07-expectation — E[f(X)] - интеграл Лебега от измеримой функции f
• prob-12-lln — Закон больших чисел требует измеримости случайных величин
• prob-20-convergence — Сходимость по мере и почти всюду - центральные понятия обоих уроков
• calc-05-continuity