Распознавание на основе скрытых марковских моделей

9 декабря на семинаре «Образный компьютер», который ведет Михаил Иванович Шлезингер (один из авторов EM-алгоритма), я докладывал о структурном распознавании для биологических последовательностей — ДНК и белков.

Презентация доклада: Распознавание на основе скрытых марковских моделей (успел рассказать до композиций алгоритмов, слайд 23).

Как известные алгоритмы распознавания на основе обобщенных скрытых марковских моделей, так и предложенные мной модели, объединяющие в себе обыкновенные СММ и марковские цепи, максимизируют функцию совместного правдоподобия для последовательности наблюдаемых и скрытых состояний. В связи с этим на семинаре возник вопрос: действительно ли такой критерий качества адекватен для рассматриваемых задач?

Максимизация правдоподобия эквивалентна минимизации эмпирического риска с функцией потерь, равной нулю тогда и только тогда, когда мы угадали всю последовательность скрытых состояний; в противном случае функция потерь равна единице. Но для достаточно длинных последовательностей вероятность какой-либо цепочки скрытых состояний ничтожно мала! Логичнее использовать функцию потерь, которая оценивает качество распознавания отдельных скрытых состояний (поиск последовательности наиболее вероятных скрытых состояний) или фрагментов скрытых состояний (задача фрагментации). Решения таких задач известны и применяются, скажем, для анализа звуковых сигналов. Остается адаптировать их для задач биоинформатики.

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

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

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *