Оценка качества восстановления распределения вероятностей

[PAV]

Привет всем.

Мне бы хотелось обсудить с заинтересованными лицами или узнать какие-нибудь идеи по поводу следующей прикладной задачи.

Предположим, что мы хотим восстановить неизвестное распределение вероятностей. Дискретное, с известными $n$ исходами $\Omega=\{1,\ldots,n\}$. Имеется множество из $M$ результатов экспериментов $(D_m,x_m)$, где $D_m$ - некоторые данные, по которым предполагается восстанавливать распределение, которое имело место в данном эксперименте, а $x_m\in\Omega$ - наблюдаемый исход в данном эксперименте. Предполагается, что в разных экспериментах распределения могут быть разными.

Предположим, что есть некоторый алгоритм $A$, который в каждом конкретном случае по данным $D$ строит распределение вероятностей на $\Omega$: $(p_1,\ldots,p_n)$.

Хотелось бы понять, как оценить качество его работы, учитывая, что для каждого предсказанного им распределения имеется только одно наблюдение.

В частности, предположим, что имеется два алгоритма $A_1$ и $A_2$, которые предсказывают распределения по различным методикам. Можно попробовать объединить их результаты с весами $(\lambda_1,\lambda_2)$, $\lambda_1+\lambda_2=1$. Хочется понять, как выбирать эти коэффициенты $\lambda$.

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

[fiktor]

Когда-то давно я уже задавался похожим вопросом. И задавал его здесь (получилось у меня очень коряво). Вы на него даже отвечали. Мне тоже будет очень интересен ответ на этот вопрос.

[PAV]

Ну, в той теме я помню, что мне было более-менее понятно, как подойти к вопросу. А тут не очень.

Единственое, что здесь приходит в голову - это в каждом эксперименте вычислять, например, среднее значение предсказанного распределения, и сравнивать его с наблюденным значением. В качестве оценки работы алгоритма можно брать сумму квадратов разностей этих величин. Но я не очень понимаю, насколько такой способ оправдан математически. В частности, правильно ли это будет себя вести, если дисперсии истинных распределений в разных опытах будут разными. И также не очень понятно, можно ли как-то находить веса алгоритмов, кроме как подбирать, стараясь минимизировать эту величину. Если алгоритмов всего два, то в принципе подбор по сетке может быть приемлемым решением, но если их много, то тут уже могу быть сложности.

[fiktor]

Пока абсолютно не понимаю, как бороться с проблемой overfitting-а.
Если же $M$ достаточно большое или количество алгоритмов достаточно маленькое, то можно в качестве первого приближения рассмотреть следующее решение.

В качестве оценки качества работы алгоритма $A$ предлагается функция

$$F(A)=\frac1M \sum_{m} Log[A(D_m)(x_m)].$$

Иными словами это $\frac1M$ от логарифма вероятности того, что выпала последовательность $x_m$ при условии того, что алгоритм работал идеально. Она максимальна, когда максимальна вероятность выпадения последовательности $x_m$ при условии вероятностей, выдаваемых алгоритмом.

Она всегда будет отрицательной. Обычно, порядка $-Log[n]$.

Если алгоритмов несколько (cкажем, $K$), то стоит рассмотреть функцию

$$f(\lambda_1,...,\lambda_k)=F(\sum_k \lambda_k A_k),$$

определенную при $\sum_k\lambda_k=1$ и найти ее максимум.

Функция выпукла вверх, а множество допустимых значений $\lambda$ выпукло, поэтому локальный максимум совпадет с глобальным. Можно взять $\lambda_k$, скажем, все по $1/K$ и, затем, в несколько итераций дойти до максимума с помощью какого-нибудь быстро-сходящегося метода (производные функции f можно сосчитать явно).

P.S. Если что-то по теме придумаете, буду рад увидеть это здесь, т.к. мне, например, очень интересна эта задача.

P.P.S. Если вы выложите реальные данные, то будет проще сравнивать различные методы. Например, если скажите, какого порядка $M$, $n$ и $K$, то можно будет оценить быстродействие.
Хотя и сейчас можно. Оно порядка $M K Log[K]\left|Log[Accuracy]\right| + M K \text{Time}(A)$, где $Accuracy$ --- требуемая точность (то есть, допустимая погрешность) определения вероятностей ($Log[K]\left|Log[Accuracy]\right|$ --- оценка количества необходимых итераций), а $\text{Time}(A)$ --- время, необходимое для вычисления числа $A_k(D_m)(x_m)$.

[Андрей1]

PAV в сообщении #311378 писал(а):

Мне бы хотелось обсудить с заинтересованными лицами или узнать какие-нибудь идеи по поводу следующей прикладной задачи.

У меня есть вот эта книга: http://www.amazon.com/Combinatorial-Met ... 837&sr=1-6

Может там что-нибудь есть ценное?

Я там не понял, применима ли эта вся теория к дискретным распределениям, правда.