Марковські випадкові поля

Стаття присвячена опису методу CRF (Conditional Random Fields), який є різновидом методу Марковських випадкових полів (Markov random field). Даний метод знайшов широке застосування в різних областях ШІ, зокрема, його успішно використовують у задачах розпізнавання мови і образів, обробки текстової інформації, а також і в інших предметних областях: біоінформатики, комп'ютерної графіки тощо

Короткий опис методу
(хто не любить математики і боїться формул, можна відразу перейти на «порівняння методів»).
Марковським випадковим полем або Марківської мережею (не плутати з Маковскими ланцюгами) називають графову модель, яка використовується для представлення спільних розподілів набору декількох випадкових змінних. Формально Марковское випадкове поле складається з наступних компонентів:
  • неорієнтований граф або фактор-граф G = (V, E), де кожна вершина є випадковою змінною Х і кожне ребро представляє собою залежність між випадковими величинами u і v.
  • набір потенційних функцій (potential function) або факторів , одна для кожної кліки (кліку — повний підграф G неорієнтованого графа) у графі. Функція ставить кожного можливого стану елементів кліки у відповідність деяке невід'ємне вещественнозначное число.
Вершини, які не є суміжними, повинні відповідати умовно незалежною випадковим величинам. Група суміжних вершин утворює кліку, набір станів вершин є аргументом відповідної потенційної функції.

Спільне розподіл набору випадкових величин у Марківському випадковому полі обчислюється за формулою:

(1) ,
де — потенційна функція, що описує стан випадкових величин k-ої кліку; Z — коефіцієнт нормалізації обчислюється за формулою:

(2) .

Безліч вхідних лексем і безліч відповідних їм типів в сукупності утворюють безліч випадкових змінних . Для вирішення завдання добування інформації з тексту достатньо визначити умовну ймовірність P(Y | X). Потенційна функція має вигляд:
, де вещественнозначный параметричний вектор, та
— набір означальних функцій. Тоді лінійним умовним випадковим полем називається розподіл ймовірності виду:
.
Коефіцієнт нормалізації тоді Z(x) обчислюється за формулою:
.

Порівняння методів
Метод CRF, як і метод MEMM (Maximum Entropy Markov Models), відноситься до дискриминативным імовірнісних методів, на відміну від генеративних методів, таких як HMM (Hidden Markov Models) або метод «Наївного Баеса» (Naïve Bayes).

За аналогією з MEMM, вибір факторів-ознак для визначення ймовірності переходу між станами при наявності спостережуваного значення залежить від специфіки конкретних даних, але на відміну від того ж МЕММ,
CRF може враховувати будь-які особливості і взаємозалежності у вихідних даних. Вектор ознак розраховується на основі навчальної вибірки і визначає вагу кожної потенційної функції. Для навчання і застосування моделі використовуються алгоритми, аналогічні алгоритмам HMM: Вітербі і його різновид — алгоритм «вперед-назад» (forward-backward).

Приховану Марковскую модель можна розглядати як окремий випадок лінійного умовного випадкового поля (CRF). У свою чергу, умовне випадкове поле можна розглядати як різновид Марковського випадкового поля (див. рис).



Рис. Зображення у вигляді графів для методів HMM, MEMM і CRF. Незафарбовані кола позначають, що розподіл випадкової величини не враховується в моделі. Стрілки вказують на залежні вузли.

В умовних випадкових полях відсутня т.зв. label bias problem — ситуація, коли перевагу отримують стану з меншою кількістю переходів, так як будується єдине розподіл ймовірностей і нормалізація (коефіцієнт Z(x) з формули (5)) в цілому, а не в рамках окремого стану. Це, безумовно, є перевагою методу: алгоритм не вимагає припущення незалежності спостережуваних змінних. Крім того, використання довільних факторів дозволяє описати різні ознаки визначаються об'єктів, що знижує вимоги до повноти і обсягом навчальної вибірки. У залежності від розв'язуваної задачі, на практиці досить обсягу від декількох сотень тисяч до мільйонів термів. При цьому точність буде визначатися не тільки об'ємом вибірки, але і вибраними факторами.

Недоліком підходу CRF є обчислювальна складність аналізу навчальної вибірки, що ускладнює постійне оновлення моделі при надходженні нових навчальних даних.

Порівняння методу CRF з деякими іншими методами, що використовуються в комп'ютерній лінгвістиці можна знайти в роботі [3]. В роботі показано, що запропонований метод працює краще за інших (принаймні F1) при вирішенні різних лінгвістичних завдань. Наприклад, в задачах автоматичного знаходження в тексті іменованих сутностей CRF демонструє дещо меншу точність у порівнянні з методом MEMM, але при цьому значно виграє в повноті.

Слід додати, що реалізація алгоритму CRF має гарну швидкість, що дуже важливо при обробці великих обсягів інформації.

На сьогоднішній день саме метод CRF є найбільш популярним і точним способом вилучення об'єктів з тексту. Наприклад, він був реалізований у проекті Стенфордського університету Stanford Named Entity Recognizer. Так само цей метод успішно реалізований для різних видів лінгвістичної обробки тексту.

Список літератури
  1. Lafferty J., McCallum A., Pereira F. "Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data". Proceedings of the 18th International Conference on Machine Learning. 282-289. 2001.
  2. Klinger R., Tomanek K.: Classical Probabilistic Models and Conditional Random Fields. Algorithm Engineering Report TR07-2-013. of Computer Science. Dortmund University of Technology. December 2007. ISSN 1864-4503.
  3. Антонова А.Ю., Соловйов О.М. Метод умовних випадкових полів в задачах обробки російськомовних текстів. «Інформаційні технології і системи — 2013», Калінінград, 2013.
    http://itas2013.iitp.ru/pdf/1569759547.pdf
  4. Stanford Named Entity Recognizer // http://www-nlp.stanford.edu/software/CRF-NER.shtml


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.