Создание марковской модели максимальной энтропии из существующего классификатора максимальной энтропии с несколькими входами

9

Я заинтригован концепцией модели максимальной энтропии Маркова (MEMM), и я думаю об использовании ее для тегера части речи (POS). В настоящее время я использую традиционный классификатор Maximum Entropy (ME), чтобы пометить каждое отдельное слово. При этом используется ряд функций, в том числе два предыдущих тега.

MEMM используют алгоритм Витерби, чтобы найти оптимальный путь через цепь Маркова (то есть найти полный оптимальный набор тегов для предложения, а не отдельные оптимумы для каждого слова). Читая об этом, это, кажется, имеет удивительную элегантность и простоту. Однако каждый этап зависит только от «результатов» предыдущего этапа (т. Е. В соответствии с цепью Маркова).

Однако моя модель ME использует два предыдущих этапа (т. Е. Теги для двух предыдущих слов). Кажется, у меня есть два возможных подхода:

  • Как и в обычной реализации Витерби, используйте набор путей, сохраненных в соответствии с одним (предыдущим) этапом. Мой классификатор ME использовал бы эту и «замороженную» стадии перед этим (замороженные в рассматриваемом пути) для получения передаточной функции.

  • Или я пишу алгоритм для отслеживания двух этапов. Это более сложно и больше не будет истинной марковской моделью, потому что каждая передаточная функция (т.е. из модели ME) будет зависеть от двух предыдущих этапов, а не от одного этапа.

Меня поражает, что второе будет точнее, хотя и сложнее.

Я еще не нашел каких-либо примеров этого во время поиска литературы. Это было опробовано? Дает ли двухэтапный подход улучшение общей точности?

winwaed
источник

Ответы:

4

(Это действительно реальный вопрос, с которым я сталкиваюсь, и запуск сайта ML StackExchange был практически идеальным временем: я провел несколько дней чтения книг и онлайн-исследований и собирался приступить к реализации. Вот мои результаты. Хотя они не являются строгими, я думаю, что они действительно отвечают на мой собственный вопрос. Я оставлю вопрос открытым пока что, если у кого-то есть какие-либо полезные предложения, попробовал что-то подобное, или есть некоторые полезные ссылки.)

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

Я делю свои данные случайным образом на два списка: данные обучения и данные испытаний. Я запускаю тестовые данные с помощью обычного POS-тега Maximum Entropy; и мой новый тег MEMM. Следовательно, они видят одни и те же тестовые данные, что позволяет проводить прямые сравнения - из-за случайности выбранных данных я вижу некоторые различия между тестами (обычно около 0,2-0,4%).

В первом тесте используется тег MEMM с одним этапом (т. Е. Истинная цепь Маркова). Это стабильно работало лучше, чем простой ME-тэгер, примерно на 0,1-0,25%.

Затем я попробовал двухэтапный подход, который кажется более правильным. Однако результаты были еще более незначительными. Часто результаты были бы идентичными, иногда это было бы немного хуже, но, вероятно, в большинстве случаев это было немного лучше (так +/- 0,05%).

MEMM-тегер работает медленно. Хорошо, я не применил никаких оптимизаций, но 1 этап (истинная цепь Маркова) медленнее в N раз (где N = количество меток), потому что это число путей, которые передаются между каждым шагом. Двухэтапная реализация медленнее на N * N (из-за большего количества передаваемых путей). Хотя оптимизация может улучшить ситуацию, я, вероятно, слишком медленный для большинства практических приложений.

Одна вещь, которую я пытаюсь - это применить более низкий предел вероятности к путям. То есть. пути Витерби сокращаются во время каждой итерации, и все пути ниже определенной вероятности (в настоящее время сокращается Log (общий путь P) <- 20,0). Это работает немного быстрее, но остается вопрос, стоит ли оно того. Я думаю, что это, вероятно, нет.

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

winwaed
источник