Оценивание дискретных распределений при дополнительных ограничениях на вероятности некоторых событий (виртуальный семинар)
Материал из MachineLearning.
(категория) |
|||
(40 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | + | Этот [[:Категория:Виртуальные семинары|виртуальный семинар]] посвящён осбуждению некоторых обобщений классической задачи [[Восстановление плотности распределения|восстановления плотности распределения]] по конечной выборке данных. | |
- | + | == Общие постановки задач == | |
+ | Основные особенности рассматриваемых здесь постановок задачи: | ||
+ | * имеется точная априорная информация о вероятности некоторых событий; это приводит к появлению дополнительных ограничений типа равенств в задаче [[Принцип максимума правдоподобия|максимизации правдоподобия]]; | ||
+ | * выборка может быть «немного» неоднородной; | ||
+ | * рассматривается несколько разновидностей задачи: объектами выборки могут быть как элементарные исходы, так и последовательности ([[временной ряд|временные ряды]]) элементарных исходов; | ||
+ | * рассматриваются только дискретные распределения (множество элементарных исходов конечно); | ||
- | + | === Стационарный однородный случай === | |
+ | Задано конечное множество элементарных исходов <tex>\Omega</tex>. | ||
+ | Для каждого <tex>\omega\in\Omega</tex> вероятность исхода <tex>p(\omega)</tex> неизвестна. | ||
+ | Имеется информация двух типов: | ||
+ | # ''эмпирические данные'': выборка наблюдений <tex>\{\omega_1,\ldots,\omega_m\},\; \omega_i\in\Omega</tex>, случайных, независимых из распределения <tex>\{p(\omega):\: \omega\in\Omega\}</tex>; | ||
+ | # ''априорные ограничения'': известны точные значения <tex>P_j</tex> вероятностей событий <tex>A_j\subseteq\Omega,\; j=1,\ldots,J</tex>: | ||
- | + | ::<tex>P(A_j) = \sum_{\omega\in A_j} p(\omega_j) = P_j.</tex> | |
+ | |||
+ | Требуется найти оценки вероятностей исходов <tex>\hat p(\omega)</tex>. | ||
+ | Эти оценки должны вычисляться достаточно эффективно — за доли секунды при <tex>m\sim 10^4,\; |\Omega|\sim 10^2</tex>. | ||
+ | |||
+ | Предполагается, что число априорных ограничений много меньше числа элементарных исходов, | ||
+ | поэтому однозначно определить вероятности исходов из априорной информации невозможно. | ||
+ | |||
+ | Обозначим через <tex>\nu(\omega)</tex> частоту исхода <tex>\omega</tex> в выборке: | ||
+ | |||
+ | ::<tex>\nu(\omega) = \frac1m \sum_{i=1}^m \left[ \omega_i=\omega \right].</tex> | ||
+ | |||
+ | ==== Непараметрическая оценка максимума правдоподобия ==== | ||
+ | Найти ''[[Принцип максимума правдоподобия|оценку максимума правдоподобия]]'', решив оптимизационную задачу | ||
+ | |||
+ | ::<tex>\sum_{\omega\in\Omega} \nu(\omega) \ln \hat p(\omega) \to \max</tex> | ||
+ | |||
+ | при ограничениях нормировки | ||
+ | |||
+ | ::<tex>\sum_{\omega\in\Omega}\hat p(\omega) = 1, \quad \hat p(\omega)\ge 0,</tex> | ||
+ | |||
+ | и априорных ограничениях-равенствах | ||
+ | |||
+ | ::<tex>\sum_{\omega\in A_j} \hat p(\omega) = P_j,\quad j=1,\ldots,J.</tex> | ||
+ | |||
+ | Вопросы: | ||
+ | * Решается ли данная задача аналитически? (предположительно, да) | ||
+ | * Обладают ли эти оценки свойствами [[несмещённость|несмещённости]], [[состоятельность|состоятельности]], [[эффективность|эффективности]]? (предположительно, да) | ||
+ | * Какие свойста этих оценок «испортятся», и насколько сильно, если априорная информация <tex>P(A_j)=P_j</tex> будет не согласована с неизвестным истинным распределением, то есть с эмпирическими данными? (предположительно, возникнет смещение) | ||
+ | * Как число априорных ограничений влияет на дисперсию оценок? (предположительно, дисперсия уменьшается с ростом ''J'') | ||
+ | |||
+ | ==== Параметрическая оценка максимума правдоподобия ==== | ||
+ | Эмпирических данных может оказаться не достаточно для получения надёжных оценок, особенно для маловероятных исходов. | ||
+ | Тогда вводится ещё один тип информации — параметрическая модель распределения | ||
+ | <tex>\hat p(\omega) = \phi(\omega,\theta)</tex>, | ||
+ | где <tex>\phi</tex> — фиксированная функция, <tex>\theta</tex> — вектор параметров модели. | ||
+ | Постановка задачи остаётся той же, только теперь решением задачи является вектор параметров <tex>\theta</tex>. | ||
+ | |||
+ | Возможен также полупараметрический подход, когда | ||
+ | вероятности часто встречающихся исходов (скажем, при <tex>\nu(\omega)>\nu_0</tex>) оцениваются непараметрически, | ||
+ | а маловероятные исходы оцениваются согласно параметрической модели. | ||
+ | |||
+ | Вопросы: | ||
+ | * Для каких параметрических моделей возможно получить эффективное численное решение? | ||
+ | * Как определить порог <tex>\nu_0</tex> при полупараметрическом оценивании? | ||
+ | * Как ввести «размытый» порог, чтобы решение определялось моделью в тем большей степени, чем меньше <tex>\nu(\omega)</tex>, без резкого перехода от параметрического оценивания к непараметрическому? | ||
+ | |||
+ | ==== Двухэтапное решение ==== | ||
+ | Для получения вычислительно эффективного метода оценивания предлагается разделить решение задачи на два этапа. | ||
+ | |||
+ | '''Этап 1.''' | ||
+ | Оценить вероятности исходов <tex>\hat p(\omega)</tex>, параметрически или непараметрически, не учитывая априорные ограничения <tex>P(A_j) = P_j</tex>. | ||
+ | Эта задача решается стандартными методами. | ||
+ | Например, при непараметрическом подходе оценка максимума правдоподобия есть просто | ||
+ | |||
+ | ::<tex>\hat p(\omega) = \nu(\omega).</tex> | ||
+ | |||
+ | '''Этап 2.''' | ||
+ | Согласовать полученное на этапе 1 решение с априорными ограничениями. | ||
+ | При параметрическом подходе согласование сводится к поиску таких оценок | ||
+ | <tex>\hat p(\omega)</tex>, | ||
+ | которые в точности удовлетворяют априорным ограничениям | ||
+ | и как можно лучше приближают модель. | ||
+ | Например, можно воспользоваться приближением в среднеквадратичном: | ||
+ | |||
+ | ::<tex>\sum_{\omega\in\Omega} \left( \phi(\omega,\theta) - \hat p(\omega) \right)^2 \to \min</tex>, | ||
+ | |||
+ | при ограничениях нормировки | ||
+ | <tex>\textstyle\sum_{\omega\in\Omega}\hat p(\omega) = 1,\; \hat p(\omega)\ge 0</tex> | ||
+ | и априорных ограничениях | ||
+ | <tex>\textstyle\sum_{\omega\in A_j} \hat p(\omega) = P_j,\; j=1,\ldots,J</tex>. | ||
+ | |||
+ | Вопросы: | ||
+ | * Обосновано ли применение метода наименьших квадратов (или какого-либо другого функционала) на втором этапе, если на первом этапе применяется принцип максимума правдоподобия? | ||
+ | * Эквивалентно ли двухэтапное решение исходной постановке задачи? (предположительно, нет) | ||
+ | * Хотя бы асимптотически? (предположительно, да) | ||
+ | * Что нужно сделать, чтобы они стали эквивалентными? | ||
+ | |||
+ | === Стационарный неоднородный случай === | ||
+ | Предположим, что объекты выборки | ||
+ | <tex>\omega_i</tex> | ||
+ | взяты по-прежнему случайно и независимо, но теперь из разных (неизвестных) распределений | ||
+ | <tex>\{p_i(\omega):\: \omega\in\Omega\}</tex>. | ||
+ | Для каждого объекта известны ''априорные ограничения'' — точные значения <tex>P_{ij}</tex> вероятностей событий | ||
+ | <tex>A_j\subseteq\Omega,\; j=1,\ldots,J</tex>. | ||
+ | Для некоторого нового объекта <tex>\omega\in\Omega</tex>, | ||
+ | взятого из неизвестного распределения | ||
+ | <tex>\{p(\omega):\: \omega\in\Omega\}</tex>, | ||
+ | также заданы ''априорные ограничения'' — точные значения <tex>P_j</tex> вероятностей событий | ||
+ | <tex>A_j\subseteq\Omega,\; j=1,\ldots,J</tex>. | ||
+ | |||
+ | Требуется найти оценки вероятностей исходов <tex>\hat p(\omega)</tex>. | ||
+ | Эти оценки должны вычисляться достаточно эффективно. | ||
+ | |||
+ | Чтобы учесть неоднородность выборки, предлагается ввести веса объектов. | ||
+ | Вес объекта <tex>\omega_i</tex> тем меньше, чем сильнее отличаются | ||
+ | априорные вероятности <tex>P_{ij}</tex> для объекта <tex>\omega_i</tex> от | ||
+ | априорных вероятностей <tex>P_{j}</tex> для объекта <tex>\omega</tex>. | ||
+ | Далее вся методика, разработанная для однородного случая, | ||
+ | переносится на неоднородный, с тем отличием, что теперь выборка взвешенная. | ||
+ | |||
+ | Функцию веса можно задать, опираясь на идею [[ядерное сглаживание|ядерного сглаживания]]: | ||
+ | |||
+ | ::<tex>w_i = K \left( \frac{1}{h} \textstyle \sum_{j=1}^J |P_{ij}-P_{j}| \right),</tex> | ||
+ | |||
+ | где ''K'' — неотрицательная невозростающая функция, называемая ''[[ядро]]м''; | ||
+ | ''h'' — [[ширина окна]] сглаживания. | ||
+ | |||
+ | Вопросы: | ||
+ | * Каким должно быть ядро? | ||
+ | * Как подобрать ширину окна, иными словами, как быстро должен убывать вес с возростанием различия априорных вероятностей? | ||
+ | * Какую метрику использовать для оценивания различия априорных вероятностей? | ||
+ | * Будет ли оценка состоятельной, несмещённой, эффективной? Как эти свойства зависят от ширины окна? | ||
+ | * Верна ли догадка, что ядерное сглаживание эквивалентно тихоновской регуляризации — введению штрафа за различия между неизвестными распределениями? Например так: | ||
+ | ::<tex>\sum_{i\neq k}\sum_{\omega}\left(p_i(\omega)-p_k(\omega)\right)^2 \to \min</tex> | ||
+ | |||
+ | === Нестационарный неоднородный случай === | ||
+ | Нестационарная (динамическая) задача является дальнейшим обобщением стационарной (статической). | ||
+ | |||
+ | Теперь объектами являются не элементарные исходы, а последовательности элементарных исходов | ||
+ | <tex>x_i = \{\omega^1_i,\ldots,\omega^t_i,\ldots,\omega^T_i\}\in\Omega^T</tex>. | ||
+ | Индекс <tex>t=1,\ldots,T</tex> будем называть ''временем''. | ||
+ | Время считается дискретным. | ||
- | |||
- | |||
== Ссылки == | == Ссылки == | ||
Строка 15: | Строка 145: | ||
== Литература == | == Литература == | ||
- | + | [[Категория:Оценивание вероятностных распределений]] | |
- | [[Категория: | + | |
- | + |
Текущая версия
Этот виртуальный семинар посвящён осбуждению некоторых обобщений классической задачи восстановления плотности распределения по конечной выборке данных.
Содержание |
Общие постановки задач
Основные особенности рассматриваемых здесь постановок задачи:
- имеется точная априорная информация о вероятности некоторых событий; это приводит к появлению дополнительных ограничений типа равенств в задаче максимизации правдоподобия;
- выборка может быть «немного» неоднородной;
- рассматривается несколько разновидностей задачи: объектами выборки могут быть как элементарные исходы, так и последовательности (временные ряды) элементарных исходов;
- рассматриваются только дискретные распределения (множество элементарных исходов конечно);
Стационарный однородный случай
Задано конечное множество элементарных исходов .
Для каждого
вероятность исхода
неизвестна.
Имеется информация двух типов:
- эмпирические данные: выборка наблюдений
, случайных, независимых из распределения
;
- априорные ограничения: известны точные значения
вероятностей событий
:
Требуется найти оценки вероятностей исходов .
Эти оценки должны вычисляться достаточно эффективно — за доли секунды при
.
Предполагается, что число априорных ограничений много меньше числа элементарных исходов, поэтому однозначно определить вероятности исходов из априорной информации невозможно.
Обозначим через частоту исхода
в выборке:
Непараметрическая оценка максимума правдоподобия
Найти оценку максимума правдоподобия, решив оптимизационную задачу
при ограничениях нормировки
и априорных ограничениях-равенствах
Вопросы:
- Решается ли данная задача аналитически? (предположительно, да)
- Обладают ли эти оценки свойствами несмещённости, состоятельности, эффективности? (предположительно, да)
- Какие свойста этих оценок «испортятся», и насколько сильно, если априорная информация
будет не согласована с неизвестным истинным распределением, то есть с эмпирическими данными? (предположительно, возникнет смещение)
- Как число априорных ограничений влияет на дисперсию оценок? (предположительно, дисперсия уменьшается с ростом J)
Параметрическая оценка максимума правдоподобия
Эмпирических данных может оказаться не достаточно для получения надёжных оценок, особенно для маловероятных исходов.
Тогда вводится ещё один тип информации — параметрическая модель распределения
,
где
— фиксированная функция,
— вектор параметров модели.
Постановка задачи остаётся той же, только теперь решением задачи является вектор параметров
.
Возможен также полупараметрический подход, когда
вероятности часто встречающихся исходов (скажем, при ) оцениваются непараметрически,
а маловероятные исходы оцениваются согласно параметрической модели.
Вопросы:
- Для каких параметрических моделей возможно получить эффективное численное решение?
- Как определить порог
при полупараметрическом оценивании?
- Как ввести «размытый» порог, чтобы решение определялось моделью в тем большей степени, чем меньше
, без резкого перехода от параметрического оценивания к непараметрическому?
Двухэтапное решение
Для получения вычислительно эффективного метода оценивания предлагается разделить решение задачи на два этапа.
Этап 1.
Оценить вероятности исходов , параметрически или непараметрически, не учитывая априорные ограничения
.
Эта задача решается стандартными методами.
Например, при непараметрическом подходе оценка максимума правдоподобия есть просто
Этап 2.
Согласовать полученное на этапе 1 решение с априорными ограничениями.
При параметрическом подходе согласование сводится к поиску таких оценок
,
которые в точности удовлетворяют априорным ограничениям
и как можно лучше приближают модель.
Например, можно воспользоваться приближением в среднеквадратичном:
,
при ограничениях нормировки
и априорных ограничениях
.
Вопросы:
- Обосновано ли применение метода наименьших квадратов (или какого-либо другого функционала) на втором этапе, если на первом этапе применяется принцип максимума правдоподобия?
- Эквивалентно ли двухэтапное решение исходной постановке задачи? (предположительно, нет)
- Хотя бы асимптотически? (предположительно, да)
- Что нужно сделать, чтобы они стали эквивалентными?
Стационарный неоднородный случай
Предположим, что объекты выборки
взяты по-прежнему случайно и независимо, но теперь из разных (неизвестных) распределений
.
Для каждого объекта известны априорные ограничения — точные значения
вероятностей событий
.
Для некоторого нового объекта
,
взятого из неизвестного распределения
,
также заданы априорные ограничения — точные значения
вероятностей событий
.
Требуется найти оценки вероятностей исходов .
Эти оценки должны вычисляться достаточно эффективно.
Чтобы учесть неоднородность выборки, предлагается ввести веса объектов.
Вес объекта тем меньше, чем сильнее отличаются
априорные вероятности
для объекта
от
априорных вероятностей
для объекта
.
Далее вся методика, разработанная для однородного случая,
переносится на неоднородный, с тем отличием, что теперь выборка взвешенная.
Функцию веса можно задать, опираясь на идею ядерного сглаживания:
где K — неотрицательная невозростающая функция, называемая ядром; h — ширина окна сглаживания.
Вопросы:
- Каким должно быть ядро?
- Как подобрать ширину окна, иными словами, как быстро должен убывать вес с возростанием различия априорных вероятностей?
- Какую метрику использовать для оценивания различия априорных вероятностей?
- Будет ли оценка состоятельной, несмещённой, эффективной? Как эти свойства зависят от ширины окна?
- Верна ли догадка, что ядерное сглаживание эквивалентно тихоновской регуляризации — введению штрафа за различия между неизвестными распределениями? Например так:
Нестационарный неоднородный случай
Нестационарная (динамическая) задача является дальнейшим обобщением стационарной (статической).
Теперь объектами являются не элементарные исходы, а последовательности элементарных исходов
.
Индекс
будем называть временем.
Время считается дискретным.