Марковские случайные поля

[sanok]

>но в отличие от того же МЕММ, CRF может учитывать любые особенности и взаимозависимости в исходных данных

Честно говоря не совсем понял этот момент. Можете привести пример особенностей и/или взаимозависимостей в исходных данных, которые может учитывать CRF но не может учитывать MEMM?

[elingur]

Попробую. Например, мы решаем задачу выделения именованных сущностей в тексте (NER). В МЕММ используется, как правило, контекст, т.е. частотность окружения, по которому вычисляется максимум энтропии. В CRF помимо словесного контекста может параллельно (или одновременно) использоваться морфологические, синтаксические и пр. характеристики окружения. Иными словами: MEMM — это линейный одномерный граф (точнее просто перебор цепочек), а CRF — это многомерный граф, который учитывает целый комплекс факторов, влияющих на результат.

[romka777]

Расскажите подробнее про задачу NER. Удалось ли получить хорошие результаты? Какая точность, полнота? Можно где-то посмотреть, как оно работает?

[elingur]

Точность и полнота зависит от кол-ва определяемых сущностей. Скажем, при определении медицинских или биологических терминов (их десятки, а иногда и сотни) точность достигает 75-80%. Если стандартный набор: люди, компании, гео — то более 90%. Сравнительный анализ методов есть в работе . Хороший обзор с демо можно посмотреть тут, тут (наиболее интересный вариант) или почитать с примерами тут .

[sanok]

По-видимому имеется в виду, что CRF «концептуально» может содержать признаки вида F(Y,X), где X — вектор данных «на входе», Y — вся разметка «на выходе» (например, при разметке частей речи (part-of-speech, POS) — сразу все части речи для всех слов предложения), в то время как MEMM может содержать лишь признаки вида F(y[i],y[i-1],...,y[i-n],X), то есть например, для данного слова мы «видим» лишь часть речи самого этого слова и его ближайших соседей. Однако если мы хотим использовать быстрые алгоритмы Витерби и forward-backward, то это преимущество CRF уходит, так как мы вынуждены ограничить признаки тем же видом, что в MEMM. Хотя другое преимущество — отсутствие проблемы labeling bias остаётся.

Что касается морфологических и синтаксических характеристик именно локального «окружения», то насколько я могу судить это «видит» и MEMM.

[elingur]

Да, МЕММ может «видеть» морфо и синт. характеристики, но не за один проход, а за несколько, в итоге решение задачи сведется к Марковской сети.

Однако если мы хотим использовать быстрые алгоритмы Витерби и forward-backward, то это преимущество CRF уходит, так как мы вынуждены ограничить признаки тем же видом, что в MEMM.

— не понял, почему? СRF работает не по всему тексту, а в пределах графа, который мы сами выберем соответственно выбранным признакам, последовательно проходя по тексту (если мы говорим о линейном CRF).

[kashey]

Если при переводе текста каждое слово переводить во все его варианты, то потом можно «схлопнуть» на основе цепей Маркова эти «вероятности» и получить более менее правильный текст.

[elingur]

Разница цепей Маркова от сетей Маркова заключается в том, что первые генеративны (т.е. предсказывают вероятность следующего шага), а вторые — дискриминатины, т.е. рассчитывают вероятность текущего состояния. Использовать тот или иной алгоритм зависит от решаемой задачи. А второе, и наиболее важное отличие — это то, что сети Маркова учитывают не только шаг (два и т.д.) вправо-влево по какому-либо из параметров, а по пучку взаимосвязанных параметров. Скажем, для перевода это не только все его варианты, а и тематический контекст перевода, синтаксис и пр.

[kashey]

Я взял лук, и, скушав лук, начал луком резать лук.
Цепи Маркова «обученные» по двум языкам подскажут кто их них bow, а кто onion. Но подскажут именно вероятность выбора.

[elingur]

Аналогично и сети Макрова, только за счет многофакторности (графа) дают предсказание более точное.

[vato35]

А почему бы не использовать раскрашенные сети Петри?

[elingur]

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

[kraidiky]

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