Задача идентификации источника данных

[Anatoly]

Здравствуйте уважаемые форумчане!
Столкнулся со следующей задачей, которая по всей видимости является типовой, но поскольку я не дока в теории вероятности, то прошу консультации.

Итак, имеем два источника последовательности символов $H_1$ и $H_2$ из некоторого конечного алфавита $A_1,A_2,\cdots,A_N$. Символы, получаемые из каждого источника, являются независимыми.
Положим, что есть обучающие выборки символов длиной $M_1$ из источника $H_1$ и длиной $M_2$ из источника $H_2$. Задача состоит в том, что при наличии тестовой выборки символов $X_1,X_2,\cdots,X_R$ определить из какого источника она была получена.

Вариант решения.
Используя формулу Байеса и формулу произведения вероятностей независимых случайных величин, несложно получить следующие выражения:

$$P(H_1|X_1,X_2,\cdots,X_R) = \frac{P(H_1)\prod_{r=1}^{R}{P(X_r|H_1)}}{P(H_1)\prod_{r=1}^{R}{P(X_r|H_1)} + P(H_2)\prod_{r=1}^{R}{P(X_r|H_2)}}$$

$$P(H_2|X_1,X_2,\cdots,X_R) = \frac{P(H_2)\prod_{r=1}^{R}{P(X_r|H_2)}}{P(H_1)\prod_{r=1}^{R}{P(X_r|H_1)} + P(H_2)\prod_{r=1}^{R}{P(X_r|H_2)}}$$

Теперь осталось только оценить вероятности, входящие в данную формулу, на основе обучающих выборок.
Во-первых,

$$P(H_1) = \frac{M_1}{M_1+M_2}$$

,

$$P(H_2) = \frac{M_2}{M_1+M_2}$$

.
Во-вторых, если обозначить через $M_{1,2}^{(k)}$ - количество символов $A_k$ в обучающей выборке из источника $H_{1,2}$, то

$$P(A_k|H_1)=\frac{M_1^{(k)}}{M_1}$$

,

$$P(A_k|H_2)=\frac{M_2^{(k)}}{M_2}$$

.

Вопрос в том, насколько корректно такое построение и какие тут могут быть подводные камни. Например, не совсем очевидно что делать, если какой либо-символ алфавита отсутствует в обучающей выборке из одного или обоих источников, но зато есть в тестовой выборке. Возможно стоит ввести метрику близости символов алфавита (расстояние Хемминга, например) и опираться на неё каким-то образом. Или же исключить нулевую вероятность наблюдения символа, применив следующие оценки

$$P(A_k|H_1)=\frac{M_1^{(k)}+1}{M_1+1}$$

,

$$P(A_k|H_2)=\frac{M_2^{(k)}+1}{M_2+1}$$

.

[ozheredov]

Anatoly в сообщении #1372461 писал(а):

Во-первых,

$$P(H_1) = \frac{M_1}{M_1+M_2}$$

,

$$P(H_2) = \frac{M_2}{M_1+M_2}$$

Это оч круто, похоже на ответ девушки на вопрос о вероятности встретить динозавра. ИМХО Байес здесь неприменим именно из-за неизвестных априорных вероятностей, которые от так точно не оценить

-- 28.01.2019, 21:43 --

Anatoly в сообщении #1372461 писал(а):

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

Перечеркнуть обучающую выборку

-- 28.01.2019, 21:46 --

Anatoly в сообщении #1372461 писал(а):

Возможно стоит ввести метрику близости символов алфавита (расстояние Хемминга, например)

Тогда вы уничтожите модель независимых событий, это раз. Вам придётся вводить функцию, связывающую вероятность совместного появления последовательных символов и расстояние Хэмминга между ними

[Anatoly]

Если Байес не подходит, то какой тогда вариант?

-- Пн янв 28, 2019 23:11:33 --

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

[ozheredov]

Anatoly в сообщении #1372509 писал(а):

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

Это задача кластеризации транзакций. Загуглите алгоритм CLOPE