У статті розглянуто машинно-навчальні методи розпізнавання іменованих сутностей тексту. Розглянуто дві базові моделі машинного навчання - наївна модель Байєса та модель умовних випадкових полів, застосовані для вирішення задачі ідентифікації та аналізу іменованих сутностей. Також досліджено модель, в якій для мультикласифікації іменованих сутностей текстів використовуються корегуючі вихідні коди. В роботі описано процес навчання та результати експериментів з тестування побудованих класифікаторів. Умовні випадкові поля перевершили інші моделі за оцінками точності та надійності роботи методу. Ключові слова: машинне навчання, обробка природної мови, розпізнання іменованих сутностей тексту. В статье исследуются машинно-обучаемые методы распознавания именованных сущностей текста. Рассмотрены две базовые модели машинного обучения - наивная модель Байеса и модель условных случайных полей, которые были использованы для решения задачи идентификации и анализа именованных сущностей. Также исследована модель, в которой для мультиклассификации именованных сущностей текстов используются корректирующие выходные коды. В работе описаны процесс обучения и результаты экспериментов по тестированию построенных классификаторов. Условные случайные поля превзошли другие модели по оценкам точности и надежности работы метода. Ключевые слова: машинное обучение, обработка естественного языка, распознавание именованных сущностей текста. The article describes machine learning methods for the named entity recognition. To build named entity classifiers two basic models of machine learning, The Naїve Bayes and Conditional Random Fields, were used. A model for multi-classification of named entities using Error Correcting Output Codes was also researched. The paper describes a method for classifiers' training and the results of test experiments. Conditional Random Fields overcome other models in precision and recall evaluations.
• блок ідентифікації та аналізу іменованих сутностей на основі моделі умовних випадкових полів − Conditional random field (CRF).
Всі блоки є підсистемами, які паралельно і незалежно одна від одної виконують наступну обробку вхідного тексту: − ідентифікація синтаксичних груп речень тексту, які містять іменовані сутності; − визначення меж знайдених іменованих сутностей (перше слово сутності – останнє слово сутності); − визначення типів знайдених іменованих сутностей. Підсистеми виконують дану обробку тексту з відповідною розміткою.
Результатом роботи системи є текст з відповідною розміткою іменованих сутностей (id сутності, границі сутності, тип сутності).
Система налаштована для розпізнавання наступних типів іменованих сутностей (Type in system), кожен тип трактується у відповідності до його трактування у корпусі Ontonotes:
Вхідними даними для розроблених класифікаторів є текст англійською мовою, дерева виведення та залежностей речень вхідного тексту, а також всі дані стосовно лексичних значень слів речень тексту згідно розмітки GOLD у корпусі Ontonotes.
Навчання класифікаторів на основі моделі Байєса та на основі моделі умовних випадкових полів −
Conditional random field (CRF) проводилося на базі розміченого текстового корпусу Ontonotes. Так як
Байєсівські класифікатори є відомим, розповсюдженим та досить простим методом, автор утримується від
безпосереднього опису самої моделі Байєса та переходить до методу класифікації на основі умовних випадкових полів −
Conditional random field (CRF) [
Марковським випадковим полем називають графову модель, яка використовується для представлення сумісних розподілів набору декількох випадкових змінних. Формально марковське випадкове поле складається з наступних компонентів:
• неорієнтований граф або фактор-граф G = (V, E), де кожна вершина v ∈V – випадкова змінна Х і кожне ребро (u, v) ∈ E – залежність між випадковими величинами u и v;
• набір потенційних функцій (potential function) або факторів {ϕ k } , одна для кожної кліки у графі (кліка − повний підграф G неорієнтованого графу). Функція ϕ k ставить кожному можливому стану елементів кліки у відповідність деяке невід’ємне дійсне число.
Вершини, що не є суміжними, мають відповідати умовно незалежним випадковим величинам. Група суміжних вершин формує кліку, набір станів вершин є аргументом відповідної потенційної функції.
Сумісний розподіл набору випадкових величин X = {xk } у марковському випадковому полі обчислюється за формулою:
P(x) = 1
∏ϕ k (x{k} ) ,
Z k Z = ∑ ∏ϕ k (x{k}) .
x∈X k де ϕ k (x{k}) – потенційна функція, що описує стан випадкових величин у k -ій кліці; Z – коефіцієнт нормалізації, що обчислюється за формулою: Множина вхідних лексем X = {xt } та множина відповідних їм типів Y = {yt } у сукупності формують множину випадкових змінних V = X U Y . Для розв’язання задачі виділення інформації з тексту достатньо визначити умовну ймовірність P( Y | X ). Потенційна функція має вигляд: де ∑{λk } – дійснозначний параметричний вектор (множники Лагранжа), ∑{ fk ( yt , yt−1, xt )} – набір ознакових функцій. Тоді лінійним умовним випадковим полем називається розподіл виду: ϕ k (x{k}) = exp(∑λk fk ( yt , yt−1, xt )) ,
k p( y | x) = 1
∏ exp(∑λk fk ( yt , yt−1, xt )) .
Z (x) k k Z (x) = ∑ ∏ exp(∑λk fk ( yt , yt−1, xt )) .
y∈Y k k
Коефіцієнт нормалізації Z(x) обчислюється за формулою:
Обчислення моделі p( y | x) відбувається як розв’язання оптимізаційної задачі з заданими обмеженнями
[
На кожній ітерації заново обчислюються множники Лагранжа, обчислення проводиться з використанням традиційних алгоритмів – «forward-backward» та Вітербі.
Метод CRF, як і метод марковські моделі максимальної ентропії (MMME), є дискримінативним імовірнісним методом, на відміну від генеративних методів, таких як приховані марковські моделі HMM та модель Байєса (Naïve Bayes).
За аналогією з марковськими моделями максимальної ентропії, вибір факторів-ознак для завдання імовірності переходу між станами при наявності спостереження значення xt залежить від специфіки конкретних даних, але на відміну від того ж МММЕ, CRF може враховувати будь-які особливості та взаємозв’язки у вхідних даних. Вектор ознак Λ = {λk } обчислюється на основі навчальної вибірки та визначає вагу кожної потенційної функції.
В умовних випадкових полях відсутня так звана label bias problem – ситуація, коли перевагу мають стани з меншою кількістю переходів, так як будується один єдиний розподіл імовірностей та нормалізація (коефіцієнт Z(x)) виконується загалом, а не у рамках окремого стану. Це, безумовно, є перевагою метода: алгоритм не потребує припущення незалежності спостережних змінних. Крім того, використання довільних факторів дозволяє описати різноманітні ознаки об’єктів, що знижує вимоги до повноти та обсягу навчальної вибірки. При цьому точність буде визначатися не лише обсягом вибірки, але й обраними факторами.
Недоліком підходу CRF є обчислювальна складність аналізу навчальної вибірки, що ускладнює постійне оновлення моделі при отриманні нових навчальних даних. Слід відзначити високу швидкість роботи алгоритму CRF, що є дуже важливою перевагою при обробці великих обсягів інформації. Навчання моделі
Для навчання моделі був обраний корпус текстів Ontonotes [
задання типів знайдених іменованих сутностей (Людина, Організація, Локація).
Розмічені тексти містять синтаксичні структури речень – дерева виведення та дерева залежностей. Тобто доступними є межі синтаксичних груп речення та відношення залежностей між словами. Доступними є також повні лексичні значення слів речень (частина мови, рід, число, час для дієслів і т. д.). Алгоритми використовують також спеціальні словники імен, географічних назв та типових назв організацій для залучення додаткових знань у систему.
Для формування базової множини ознакових функцій було проведено дослідження та аналіз найкращих
робіт за даною тематикою [
⎪⎩0, _ інакше. Далі в процесі дослідження були проведені чисельні експерименти з навчання моделей на розмічених текстах корпусу Ontonotes, після чого виконувалося тестування навченого алгоритму на точність ідентифікації та визначення типу іменованих сутностей на текстах з інших частин корпусу. Потім, згідно процедури кросвалідації, навчальна та тестова частини корпусу мінялися місцями та процес навчання і тестування моделей повторювався з початку. Із всіх отриманих оцінок точності обиралися мінімальні, як найбільш об’єктивні та гарантовано досяжні.
Навчання та тестування моделей проводилось багато разів з різними наборами ознакових функцій. В результаті проведення багатьох ітерацій етапів навчання-тестування з перебором множини функцій ознак були визначені оптимальні набори ознакових функцій { fi′ } та { fi″ }, на яких досягнуто максимальні оцінки точності ідентифікації та визначення типів іменованих сутностей тексту класифікатором Байєса та класифікатором на базі моделі умовних випадкових полів (CRF), відповідно. Розпізнавання іменованих сутностей тексту з використанням корегуючих вихідних кодів (ECOC)
Для вирішення задачі визначення іменованих сутностей у тексті як альтернативний підхід були використані корегуючі вихідні коди (Error-Correcting Output Codes, ECOC). Даний підхід застосовують при вирішенні задач мультикласифікації, коли число класів перевищує два. У випадку визначення іменованих сутностей як класи маємо класи слів, такі як Person, Location, Organization, Event, Product та інші. Також в іншій серії експериментів використовувалась розмітка на класи з використанням boundary-тегів, в цьому випадку маємо наступні класи: Person-Begin, Person-Inside, Location-Begin, Location-Inside, Organization-Begin, Organization-Inside та інші.
Задача мультикласифікації полягає у знаходженні невідомої функції f (x) , область значень якої дискретна множина, що містить k значень (класів), k > 2 . Дана функція f (x) визначається у процесі навчання на основі навчальної вибірки прикладів виду (xi , di ) , i = 1, n , де di = f (xi ) – відоме значення класу для прикладу xi .
Вирішення задачі мультикласифікації зводиться до розв’язання підзадач бінарної класифікації, а результатом мультикласифікації є поєднання отриманих розв’язків. Для поєднання розв’язків бінарних класифікаторів було застосовано підхід розподіленого вихідного представлення (Distributed Output Representation); як бінарні класифікатори використовуються класифікатори CRF.
Під розподіленим вихідним представленням розуміється задання кожного класу бінарним рядком довжини n – “кодовим словом”. Кожен біт кодового слова відповідає окремому бінарному класифікатору, який навчається. Вирішення задачі мультикласифікації зводиться до обробки так званої матриці кодових слів, рядки якої – кодові слова, що відповідають класам, об’єкти яких розпізнаються, а стовпчики відповідають бінарним класифікаторам (це ті значення, що видають класифікатори на відповідних класах). Після навчання класифікаторів новий об’єкт x класифікується оцінюванням кожного з n бінарних класифікаторів для отримання n -бітового кодового слова. Отримане кодове слово об’єкта x порівнюється з кожним із k кодових слів матриці. Об’єкт x належить класу, чиє кодове слово є найближчим згідно вибраної метрики до його власного слова. Визначення мінімальної відстані від отриманого кодового слова об’єкта x , що класифікується, до одного з кодових слів матриці розглядається як процес декодування. Для реалізації процесу декодування використовується відстань Хемінга. Зокрема, мінімальна відстань між отриманим кодовим словом f (x) = ( f1(x), f 2 (x),K, f n (x)) та кодовими словами матриці M визначається як число позицій, у яких відповідні значення бітів різні.
Від виду матриці кодових слів залежить скільки помилок здатен виправити даний розподілений вихідний код у процесі декодування. Коди, які дозволяють виправити помилки в процесі декодування називаються корегуючі вихідні коди (Error-Correcting Output Codes). Мірою якості коду є мінімальна відстань Хемінга між парами кодових слів матриці. Якщо мінімальна відстань Хемінга дорівнює d , відповідний код гарантовано може виправити (d −1) 2 помилкових біт при декодуванні.
Моделі розподіленого вихідного коду будуються відповідно до різних представлень матриці кодових слів M ∈{0,1}k×n , де k – кількість класів, n – кількість бінарних класифікаторів, тобто довжина кодового слова.
У рамках досліджень була використана модель корегуючих вихідних кодів Exhaustive Code. Згідно даної моделі рядками матриці кодових слів є кодові слова довжини 2k−1 − 1 . Перший рядок матриці заповнюється одиницями, далі i-й рядок матриці заповнюється 2k−i нулями та 2k−i одиницями, що чередуються, починаючи з нулів. Приклад матриці з вичерпним кодом для 4-х класів наведено у табл. 1. Таблиця 1. Вичерпний код для 4-х класів Клас С1 С2 С3 С4 f1 1 0 0 0 f2 1 0 0 1 f3 1 0 1 0 Кодові слова f4 1 0 1 1 f5 1 1 0 0 f6 1 1 0 1 f7 1 1 1 0 При дослідженні було проведено наступні експерименти. Для розпізнавання іменованих сутностей класів Person, Location, Organization було залучено також класи слів NE (куди відносяться всі інші сутності, які не належать до Person, Location, Organization, наприклад, сутності класів Event, Product, WorkArt, Money тощо), а також OTHER, які включають всі інші лексеми, які не відносяться до переліку іменованих сутностей. Таким чином у даному експерименті було використано 5 класів. Матриця кодових слів у цьому випадку містить 15 стовпчиків (бінарних класифікаторів).
У другому експерименті були залучені спеціальні boundary-тегі для формування класів, таким чином використовувалися наступні 8 класів: Person-Begin, Person-Inside, Location-Begin, Location-Inside, OrganizationBegin, Organization-Inside, NE та OTHER. Матриця кодових слів у цьому випадку складається з 127 бінарних класифікаторів.
Отримані результати дозволили зробити наступні висновки. У результаті надвеликої кількості лексем, які відносяться до класу OTHER, та мають велику частоту вживання у корпусі, а також у результаті того, що деякі ознаки сутностей (досить великий їх відсоток), що належать до основних класів (не до OTHER), при формуванні бінарного класифікатора потрапляють в один клас, то бінарні класифікатори типу CRF на таких нерівномірних вибірках показали невисоку якість роботи. Наприклад, при розділенні на два класи отримаємо, що до одного класу належать високочастотні лексеми з OTHER та низькочастотні з Event, Product, Location тощо, а до другого класу – виключно низькочастотні лексеми з Person та Organization. Тоді елементи першого класу мають і високу частоту, і значну частину ознак другого класу, що призводить до значного превалювання першого класу над другим. За рахунок великої кількості помилок, отриманих бінарними класифікаторами (слід врахувати, що кожен з 15, у випадку 5 класів, та кожен із 127, у випадку 8 класів, має великий відсоток помилок) застосування розподілених вихідних кодів, зокрема ECOC, не дозволило отримати бажані високі оцінки якості. Для покращення результатів роботи моделі з використанням ECOC необхідно мати навчальну вибірку з більш рівномірним розподілом лексем по класах. Проте, використання підходу ECOC (а саме матриці кодових слів та реалізації процесу декодування за допомогою обчислення відстаней Хемінга) виправдане як одного з потенційних способів, коли треба знайти лексеми, що можливо були віднесені не до свого класу. Отримані результати
У таблицях 2–5 представлені оцінки роботи класифікатора Байєса та класифікатора на основі моделі умовних випадкових полів (CRF), навчених на оптимальних наборах ознакових функцій { fi′ } та { fi′′ }, відповідно. У таблиці 6 надані оцінки роботи мультикласифікатора, побудованого з використанням корегуючих вихідних кодів (ECOC).
В експериментах обчислювалися оцінки точності (Precision, P), повноти (Recall, R) та комбінована міра F1 :
F1 =
(Precision + Recall) . Таблиця 2. Оцінки класифікатора Байєса на підкорпусі Broadcast News (100 файлів)
Proceedings of the 10th International Conference of Programming UkrPROG’2016 (Kyiv, Ukraine) Таблиця 3. Оцінки класифікатора Байєса на підкорпусі Web text (230 файлів) Таблиця 4. Оцінки класифікатора Байєса на підкорпусі Newswire (1665 файлів) Recall: 0.6547
WB Таблиця 6. Оцінки мультикласифікатора з використанням корегуючих вихідних кодів (ECOC)
Оцінки точності та повноти, отримані в результаті тестування розробленої системи на базі моделі CRF
(табл. 5), демонструють найвищі значення на рівні найкращих існуючих світових аналогів. На тестових текстах
корпусу Ontonotes розроблена система змогла перевершити показники відомої системи Стенфордського
університету для розпізнавання іменованих сутностей тексту Stanford Named Entity Recognizer [
На основі двох базових моделей машинного навчання – наївної моделі Байєса та умовних випадкових полів, – було побудовано систему ідентифікації та аналізу іменованих сутностей тексту. Результати дослідження та експериментів показали високу якість роботи класифікатора, реалізованого на основі моделі умовних випадкових полів. Досвід найкращих існуючих програмних реалізацій систем аналізу іменованих сутностей тексту приводить до висновку, що саме модель умовних випадкових полів (CRF) оптимально підходить для розробки класифікаторів іменованих сутностей.
В процесі тестування реалізований алгоритм продемонстрував високу точність визначення типів іменованих сутностей тексту на рівні найкращих існуючих світових аналогів.
Також була досліджена модель, в якій для мультикласифікації іменованих сутностей текстів використовуються корегуючі вихідні коди (ЕСОС). Результати експериментів доводять наявність серйозних перспектив застосування даного підходу для вирішення класичних та прикладних задач комп’ютерної лінгвістики.