С чего всё началось

\( \def \X {\mathcal X} \def \Y {\mathcal Y} \def \F {\mathcal F} \def \R {\mathbb R} \def \E {\mathbb E} \def \P {\mathbb P} \def \N {\mathcal N} \def \Ind {\mathrm{Ind}\;} \def \ch {\mathrm{ch}\;} \) Для третьекурсников в этом году существует факультативный курс «Стохастический анализ в задачах».

  • В прошлом семестре было законспектировано несколько занятий и опубликовано несколько листочков. Материалы и литературу можно найти в гугл-диске.
  • Идейным вдохновителем является сборник задач кафедры МОУ. Доступны Первая часть и Вторая часть сборника. Первая часть находится в процессе рецензирования и на пути к изданию, вторая часть пока в процессе редактирования.

Материал, который здесь приведен, рассказывал Никита Животовский.

Постановка задачи классификации

Практическая задача: пусть есть некоторые объекты \( \X \), и классы \( \Y \). Для удобства будем считать, что классов всего два, \( \Y \in \{-1, 1\} \). Объекты – произвольной природы.

Рассмотрим множество классификаторов: \[ \mathcal F = \{ f \mid f \colon \X \to \Y \} \]

Вероятностная модель: объекты приходят парами \( \X \times \Y \). Пусть пришло \( n \) объектов.

На этих парах \( (X_1, Y_1), (X_2, Y_2), \ldots, (X_n, Y_n) \) задана вероятностная мера. Таким образом, мы вводим некоторое распределение на \( \X \times \Y \), и будем считать, что все наблюдаемые пары получены независимо и согласно \( \P_{\X \times \Y} \).

Как же на самом деле взаимодействуют эти пары?

Предположение.

\( \exists f^{\ast} \in \F \colon Y = f^{\ast} (X) \).

Другими словами, мы предположили, что классы \( Y \) каким-то детерминированным образом зависят от \( X \), хотя она нам и неизвестна. Мы знаем, что эта функция лежит в классе \( \F \), и этот класс нам известен.

Не имеет значения, конечный он, счётный или несчётный. Он представляет собой некоторый «мешок», в котором лежат все «подозрительные» функции.

Наша задача стоит следующим образом: «приблизить» с помощью наблюдаемых данных функцию \( f^{\ast} \). Как можно это сделать?

Вопрос. В какой метрике происходит приближение?

Ответ. Наша задача – найти такую функцию \( \hat f(x) \) (построить её по данным), чтобы вероятность \[ \P(\hat f(x) \neq f^{\ast} (x)) \] была минимальна.

Давайте найдём процедуру, которая бы по данным строила такую оптимальную \( \hat f(x) \). Первое, что приходит в голову – минимизировать эмпирический риск: выбрать такую функцию \( \hat f \) по данным, что \[ \sum_{i=1}^{n} \Ind [\hat f(X_i) \neq Y_i] \to \min \] Такой минимизатор риска не может ошибаться на выборке, потому что истинная зависимость лежит в классе, а минимум мы ищем по функциям класса. Другое дело в том, что может найтись довольно много таких различных классификаторов, которые согласуются на точках выборки.

Наглядный пример: рассмотрим синусоиду и константу \( 0 \), при том, что выборка нами наблюдается в нулях синусоиды. С точки зрения наблюдателя эти функции проецируют одни и те же наблюдения.

Определение. Пусть \( X \) – случайная величина, \( \lambda \gt 0 \), \( \varphi_X \colon \R_+ \to \R_+. \)

Производящей функцией моментов называется функция вида \[ \varphi_X (\lambda) = \E \exp(\lambda X) \] Для каждого конкретного \( \lambda \) это матожидание является конкретным числом (для дискретной случайной величины это дискретное матожидание).

Характеристическая функция – это функция вида \[ \chi_X(t) = \E \exp( i t X) \]

Вопрос. Пусть мы знаем, что эта функция является гладкой, дифференцируемой. Как найти математическое ожидание \( X \), зная эту функцию?

Ответ. \[ \varphi’(0) = \E X \exp(0 X) = \E X %’ \]

Мы видим, что эта функция даёт довольно много информации о случайной величине, математическое ожидание, моменты.

Пример.

Рассмотрим бернуллиевскую случайную величину, принимающую значения \( \pm 1 \) с вероятностями \( p = 1/2 \). \[ \varphi_X(\lambda) = \dfrac{1}{2} ( \exp(\lambda) + \exp(-\lambda) ) = \ch(\lambda) \]

Оказывается, что для нормальной случайной величины выполнено свойство \[ \varphi_X(\lambda) \leqslant \exp \left( \dfrac{\lambda^2 \sigma^2}{2} \right) \] Заметим, что для экспоненты выполнено разложение в ряд: \[ \E \exp(\lambda X) = \E (1 + \lambda x + \dfrac{\lambda^2 x^2}{2} + \ldots) \]

Определение.

Субгауссовской случайной величиной будем называть такую случайную величину, матожидание которой равно нулю, и для которой найдётся \( \sigma \colon \) \[ \varphi_X(\lambda) \leqslant \exp \left(\dfrac{\lambda^2 \sigma^2}{2} \right) \]

Некоторый физический смысл: мы хотим, чтобы моменты случайной величины не росли слишком быстро. Сейчас не нужно даже понимать, что такое гауссовская случайная величина, главное – это как ограничена производящая функция моментов субгауссовской случайной величины.

Пусть \( Y_1, \ldots, Y_n \) – субгауссовские величины с параметром \( \sigma \) (могут быть зависимы между собой). Посмотрим на максимум от этих случайных величин (это случайная величина).

Обозначим случайную величину \( Z \): \[ Z = \E \max_{i=1, \ldots, n} Y_i \]

Мы хотим ограничить этот максимум сверху. Чуть позже мы поймём, что максимум будет тем больше, чем больше в этих случайных величинах «независимости». \[ \varphi_Z(\lambda) = \E \exp (\lambda Z) = \E \exp( \lambda \max_i Y_i) = \E \max_i \exp(\lambda Y_i) \]

Вопрос. Как максимум от неотрицательных случайных величин можно ограничить сверху каким-нибудь наивным способом?

Ответ. Максимум можно оценить суммой. В случае в экспонентами это не будет очень грубо.

\[ \E \max_i \exp(\lambda Y_i) \leqslant \E \sum_{i} \exp(\lambda Y_i) = \sum_i \E \exp(\lambda Y_i) = n \exp(\lambda^2 \sigma^2 / 2) \]

Неравенство Йенсена.

Пусть \( \psi \) – выпуклая функция. \[ \psi(\E X) \leqslant \E \psi (X) \]

Вопрос. Как с помощью этого неравенства, зная верхнюю оценку на производящую функцию, достать матожидание? \[ \varphi_Z(\lambda) \leqslant n \exp( \lambda^2 \sigma^2 / 2) \]

Ответ. Просто «в лоб» дифференцировать под знаком неравенства нельзя. Но у нас есть неравенство Йенсена, его и нужно использовать! Обратите также внимание на то, что хоть величины \( Y_i \) были центрированные, но максимум из них, то есть величина \( Z \) уже не является центрированной. \[ \E \exp(\lambda Z) \geqslant \exp( \lambda \E Z) \] \[ \dfrac{1}{\lambda} \log \varphi_Z(\lambda) \geqslant \E Z \] \[ \E \max_i Y_i \leqslant \dfrac{1}{\lambda} \ln \left( n \exp (\lambda^2 \sigma^2 / 2) \right) = \dfrac{1}{\lambda} \ln n + \dfrac{\lambda \sigma^2}{2}, \quad \lambda \gt 0 \] Так как это верно для любого \( \lambda \), давайте найдём минимум: \[ \lambda^\ast = \dfrac{\sqrt{2 \ln n}}{\sigma}, \qquad \E \max_i Y_i \leqslant \sigma \sqrt{2 \ln n}. \] Пусть \( Z = \max_i |Y_i| \), где \( Y_i \) – центрированные субгауссовские величины. Заметим, что \[ Z = \max_i (Y_i, -Y_i), \qquad \E Z \leqslant \sigma \sqrt{2 \ln (2n)}. \]

Снова классификация

Классификатор, который минимизирует эмпирический риск, не ошибается на наблюдениях, где количество наблюдений-пар равно \( m \). \[
\P( \hat f(x) \neq f^\ast (x)) \] В этом выражении есть некоторая тонкость: \( x \) – случайная величина, но при этом \( \hat f \) тоже строится по наблюдениям, то есть является случайной функцией. Вероятность берётся только по «новому наблюдению» \( x \), а затем можно усреднить эту величину по пространству вероятностей для классификатора: \[ \E^{(m)} \P ( \hat f(x) \neq f^{\ast} (x) ) = (1) \] Пусть \( \hat f \) не ошибается на обучающей выборке \( (X_1, Y_1), \ldots, (X_m, Y_m) \). \[ (1) = \E^{(m)} \left( \P\left( \hat f(X) \neq f^{\ast} (X) \right) - \dfrac{1}{m} \sum_{i=1}^{m} \Ind \left(\hat f(X_i) \neq Y_i\right) \right) = (2) \] Это выражение тождественно равняется \( (1) \), потому что второе слагамемое равно нулю. \[ (2) \leqslant \E^{(m)} \sup_{f \in \F} \left( \P \left( f(X) \neq f^{\ast} (X) \right) - \dfrac{1}{m} \sum_{i=1}^{m} \Ind \left( f(X_i) \neq Y_i \right) \right) = (3) \] Здесь второе слагаемое уже ненулевое по матожиданию. Заметим, что \[ \E \Ind \left( f(X_i) \neq Y_i \right) = \P \left( f(X_i) \neq Y_i \right) \] Можно из того же распределения \( \P \) сгерерировать новую выборку из \( m \) объектов. При этом в выражении \( (3) \) в первом слагаемом вероятности для \( \P(f(x) \neq f^{\ast}(x)) \) одинаковые для всех «искусственных» точек выборки. Это позволяет записать выражение в виде: \[ (3) = \E^{(m)} \sup_{f \in \F} \left( \E^{(m)} \left( \dfrac{1}{m} \sum \Ind (f(X’_i) \neq Y’_i) \right) - \dfrac{1}{m} \sum_i \Ind (f(X_i) \neq Y_i) \right) = (4) \] Воспользуемся неравенством Йенсена. Оказывается, что если класс счётный, то супремум \( \sup_{f \in \F} (\cdot) \) является выпуклой функцией (это известный и несложный факт из выпуклого анализа: надграфик от максимума является пересечением надграфиков выпуклых функций, каждый из которых является выпуклым множеством). \[ (4) \leqslant \E^{(m)} \E^{(m’)} \sup_{f \in \F} \left( \dfrac{1}{m} \sum_{i = 1}^{m} \Big( \Ind (f(X’_i) \neq Y’_i) - \Ind (f(X_i) \neq Y_i) \Big) \right) = (5) \] Рассмотрим отдельно разность индикаторов. \[ \Ind(f(X’_i) \neq Y_i) - \Ind (f(X_i) \neq Y_i) \] Эта случайная величина может принимать всего три значения: \( \{0, -1, 1\}. \) Между ними есть некоторое «равноправие»: пары \( (X_i, Y_i) \) распределены так же, как пары \( (X’_i, Y’_i) \). Значит, мы смотрим разность между одинаково распределёнными независимыми случайными величиными. Поэтому можно домножить выражение на независимый случайно распределённый знак \( \varepsilon_i \): \[ \varepsilon_i \Big( \Ind(f(X’_i) \neq Y_i) - \Ind (f(X_i) \neq Y_i) \Big). \] \[ (5) = \E^{(m)} \E^{(m)} \E_{\varepsilon_i} \sup_{f \in \F} \left( \dfrac{1}{m} \sum_{i = 1}^{m} \varepsilon_i\Big( \Ind (f(X’_i) \neq Y’_i) - \Ind (f(X_i) \neq Y_i) \Big) \right) = (6) \] Сейчас мы упростим выражение, и этот крокодил превратится в очень простую штуку! Заметим, что \( \sup (a + b) \leqslant \sup (a) + \sup (b). \) Поэтому можно оценить выражение как \[ (6) \leqslant 2 \E^{(m)} \E_{\varepsilon} \sup_{f \in \F} \left( \dfrac{1}{m} \sum_{i=1}^{m} \varepsilon_i \Ind (f(X_i) \neq Y_i) \right) \] Практически уже сейчас можно применить нашу субгауссовскую технологию, главное – это понять, какие здесь нужно рассмотреть случайные величины. Зафиксируем \( m \) точек, по которым рассматривается матожидание, и рассмотрим выражение, которое стоит внутри скобки: \[ \E_{\varepsilon} \sup_{f \in \F} \left( \sum_{i=1}^{m} \varepsilon_i \Ind (f(X_i) \neq Y_i) \right) \] Заметим, что случайные величины, которые стоят под матожиданием, являются субгауссовскими (просто потому, что они принимают конечный набор значений, а точнее, \(\{0, \pm 1\}.\) Докажем это.

Утверждение.

Случайная величина вида \[ \sum_{i=1}^{m} \varepsilon_i \Ind (f(X_i) \neq Y_i) \] является субгауссовской.

Доказательство.

\[ \E \exp(\lambda \sum_{i=1}^{m} \varepsilon_i \Ind (f(X_i) \neq Y_i) ) = (7) \] Экспонента от суммы является произведением экспонент, а матожидание произведения независимых случайных величин равняется произведению матожиданий. Кроме того, можно заметить, что \( \ch x \geqslant 1 \), поэтому можно «не учитывать» нулевые значения внутри экспоненты, если мы хотим оценить выражение сверху: \[ (7) = \Big(\E_{\varepsilon} \exp (\lambda \varepsilon_i \Ind (f(X_i) \neq Y_i)) \Big)^m = ( \ch \lambda )^{m} \] Заметим, что для гиперболического косинуса выполнено неравенство (оно доказывается разложением в бескеонечный ряд Тейлора): \[ \ch \lambda \leqslant \exp \left( \dfrac{\lambda^2}{2} \right) \] Значит, \[ (7) \leqslant \exp \left( \dfrac{\lambda^2 m}{2} \right) \] Таким образом, мы доказали, что наша величина является субгауссовской, с константой \( \sigma^2 = m \).

Конец доказательства.

Пусть класс функций является конечным: \( |\F| = N \). Мы знаем, что максимум из субгауссовских случайных величин ведёт себя следующим образом: \[ (6) \leqslant \dfrac{2 \E^{(m)} \sqrt{m} \sqrt{2 \ln (N)}}{m} = 2\sqrt{\dfrac{2 \ln N}{m}}. \] Таким образом, ожидаемая вероятность ошибки построенного нами алгоритма можно оценить сверху. С ростом числа точек это выражение будет стремиться к нулю.

Примечание. Оказывается, можно показать, что лучше, чем \( \sqrt{\ln N} \) в общем случае показать нельзя, но в нашей задаче результат можно улучшить. Можно доказать, что \[ \E^{(m)} \P (\hat f(x) \neq f^{\ast} (x)) \leqslant \dfrac{4 \ln N}{m}. \] Эта оценка является «самой лучшей». Предположим, что существует некоторый «противник», который умеет варьировать \( N \) в зависимости от \( m \). Если словарь функций становится слишком большим, то техника рушится.

Пусть \( \F \) – пространство всех измеримых функций. Мы рассмотрим ситуацию, которую принять называть переобучением. Вероятность ошибки может оказаться очень большой, и даже стремиться к единице. Ясно, что так как мы наблюдаем выборку лишь в конечном числе точек, то найдётся функция, которая не ошибается на наблюдённых точках. Вывод: нельзя использовать слишком сложную идею, имея слишком мало данных!

Упражнения.

  1. Найдите характеристическую случайную функцию нормально распределённой случайной величины: \( X \sim \N(0, 1). \) \( \varphi_X(\lambda) = ? \)
  2. Метод Чернова. Используя неравенство Маркова, докажите, что для случайной величины \( X \) с производящей функцией моментов \(\psi_{X}:\) \[ \P(X \ge \varepsilon) \le \inf\limits_{\lambda > 0}\exp(\psi_{X}(\lambda) - \lambda\varepsilon) \] Подсказка: Функция \( g \), заданная \( g(x) = \exp(\lambda x) \) является возрастающей для \( \lambda \gt 0\).
  3. С помощью метода Чернова оцените \( P(X \ge \varepsilon) \), где \( X \sim \mathcal{N}(0, 1).\)
  4. Неравенство Чернова. Пусть \( S \sim \mathrm{Bi}(n, p)\). Докажите, что \[
    \P \left(\frac{S - \E S}{n} \ge \varepsilon\right) \le \exp(-2\varepsilon^{2}n). \] Подсказка: Как задается производящая функция моментов для суммы независимых случайных величин?
  5. Докажите, что для неотрицательной случайной величины \( X \): \[ \E X \le \int\limits_{0}^{\infty} \P(X \ge \varepsilon) d\varepsilon. \] 6. Пусть для \( c_{1} \gt e^{-1}, c_{2} \gt 0 \) для некоторой неотрицательной случайной величины \( X_n \) выполнено: \[ \P(X_n \ge \varepsilon) \le c_{1}\exp(-c_{2}n\varepsilon^{2}). \] Докажите, что \[ \E X_n \le \sqrt{\frac{C}{n}}, \] где \( C = (1 + \ln(c_{1}))/c_{2}. \)