Machine-learning methods for text named entity recognition
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 wa...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/190 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-190 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/0f/47e1a04415e43984685bf4392a93df0f.pdf |
| spelling |
pp_isofts_kiev_ua-article-1902024-04-28T13:09:57Z Machine-learning methods for text named entity recognition Машинно-учебные методы распознавания именуемых сущностей текста Машинно-навчальні методи розпізнавання іменованих сутностей тексту Marchenko, O.O. machine learning; natural language processing; named entity recognition UDC 004.85 машинное обучение; обработка естественного языка; распознавание именованных сущностей текста УДК 004.85 машинне навчання; обробка природної мови; розпізнання іменованих сутностей тексту УДК 004.85 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.Problems in programming 2016; 2-3: 150-157 В статье исследуются машинно-обучаемые методы распознавания именованных сущностей текста. Рассмотрены две базовые модели машинного обучения – наивная модель Байеса и модель условных случайных полей, которые были использованы для решения задачи идентификации и анализа именованных сущностей. Также исследована модель, в которой для мульти-классификации именованных сущностей текстов используются корректирующие выходные коды. В работе описаны процесс обучения и результаты экспериментов по тестированию построенных классификаторов. Условные случайные поля превзошли другие модели по оценкам точности и надежности работы метода.Problems in programming 2016; 2-3: 150-157 У статті розглянуто машинно-навчальні методи розпізнавання іменованих сутностей тексту. Розглянуто дві базові моделі ма-шинного навчання – наївна модель Байєса та модель умовних випадкових полів, застосовані для вирішення задачі ідентифікації та аналізу іменованих сутностей. Також досліджено модель, в якій для мультикласифікації іменованих сутностей текстів вико-ристовуються корегуючі вихідні коди. В роботі описано процес навчання та результати експериментів з тестування побудова-них класифікаторів. Умовні випадкові поля перевершили інші моделі за оцінками точності та надійності роботи методу.Problems in programming 2016; 2-3: 150-157 Інститут програмних систем НАН України 2018-07-06 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/190 10.15407/pp2016.02-03.150 PROBLEMS IN PROGRAMMING; No 2-3 (2016); 150-157 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2016); 150-157 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2016); 150-157 1727-4907 10.15407/pp2016.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/190/185 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T13:09:57Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
machine learning natural language processing named entity recognition UDC 004.85 |
| spellingShingle |
machine learning natural language processing named entity recognition UDC 004.85 Marchenko, O.O. Machine-learning methods for text named entity recognition |
| topic_facet |
machine learning natural language processing named entity recognition UDC 004.85 машинное обучение обработка естественного языка распознавание именованных сущностей текста УДК 004.85 машинне навчання обробка природної мови розпізнання іменованих сутностей тексту УДК 004.85 |
| format |
Article |
| author |
Marchenko, O.O. |
| author_facet |
Marchenko, O.O. |
| author_sort |
Marchenko, O.O. |
| title |
Machine-learning methods for text named entity recognition |
| title_short |
Machine-learning methods for text named entity recognition |
| title_full |
Machine-learning methods for text named entity recognition |
| title_fullStr |
Machine-learning methods for text named entity recognition |
| title_full_unstemmed |
Machine-learning methods for text named entity recognition |
| title_sort |
machine-learning methods for text named entity recognition |
| title_alt |
Машинно-учебные методы распознавания именуемых сущностей текста Машинно-навчальні методи розпізнавання іменованих сутностей тексту |
| description |
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.Problems in programming 2016; 2-3: 150-157 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/190 |
| work_keys_str_mv |
AT marchenkooo machinelearningmethodsfortextnamedentityrecognition AT marchenkooo mašinnoučebnyemetodyraspoznavaniâimenuemyhsuŝnostejteksta AT marchenkooo mašinnonavčalʹnímetodirozpíznavannâímenovanihsutnostejtekstu |
| first_indexed |
2024-09-16T04:08:14Z |
| last_indexed |
2024-09-16T04:08:14Z |
| _version_ |
1818568158236114944 |
| fulltext |
Інтелектуальні інформаційні технології
© О.О. Марченко, 2016
150 ISSN 1727-4907. Проблеми програмування. 2016. № 2–3. Спеціальний випуск
УДК 004.85
МАШИННО-НАВЧАЛЬНІ МЕТОДИ
РОЗПІЗНАВАННЯ ІМЕНОВАНИХ СУТНОСТЕЙ ТЕКСТУ
О.О. Марченко
У статті розглянуто машинно-навчальні методи розпізнавання іменованих сутностей тексту. Розглянуто дві базові моделі ма-
шинного навчання – наївна модель Байєса та модель умовних випадкових полів, застосовані для вирішення задачі ідентифікації
та аналізу іменованих сутностей. Також досліджено модель, в якій для мультикласифікації іменованих сутностей текстів вико-
ристовуються корегуючі вихідні коди. В роботі описано процес навчання та результати експериментів з тестування побудова-
них класифікаторів. Умовні випадкові поля перевершили інші моделі за оцінками точності та надійності роботи методу.
Ключові слова: машинне навчання, обробка природної мови, розпізнання іменованих сутностей тексту.
В статье исследуются машинно-обучаемые методы распознавания именованных сущностей текста. Рассмотрены две базовые
модели машинного обучения – наивная модель Байеса и модель условных случайных полей, которые были использованы для
решения задачи идентификации и анализа именованных сущностей. Также исследована модель, в которой для мульти -
классификации именованных сущностей текстов используются корректирующие выходные коды. В работе описаны процесс
обучения и результаты экспериментов по тестированию построенных классификаторов. Условные случайные поля превзошли
другие модели по оценкам точности и надежности работы метода.
Ключевые слова: машинное обучение, обработка естественного языка, распознавание именованных сущностей текста.
The article describes machine learning methods for the named entity recognition. To build named entity classifiers two basic models of ma-
chine 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. Con-
ditional Random Fields overcome other models in precision and recall evaluations.
Key words: machine learning, natural language processing, named entity recognition.
Вступ
Проблема визначення іменованих сутностей тексту не є новою, дослідження активно ведуться вже понад
20 років, і оприлюднені досить високі результати роботи прикладних систем (до 93 % точності у розпізнаванні
іменованих сутностей машиною проти 96 % точності у розпізнанні іменованих сутностей людиною). Незважа-
ючи на заявлений високий відсоток правильності розпізнавання, проблема досі вважається відкритою і за да-
ною проблематикою активно ведуться дослідження.
Актуальність проблеми пояснюється специфічністю середовища, в якому отримані надвисокі результати:
як правило таке середовище створюється штучно для тестування системи і не може бути відтворено в реально-
му світі. До штучного середовища можна віднести додаткові 100 % коректні дані про текст (наприклад, завжди
гарантовано правильні синтаксичні дерева речень, морфологічна, семантична та інша інформація), які є недо-
ступними в реальних умовах. Також до таких умов можна віднести надвисокі потужності задіяного обладнання,
коли задача вирішується в лабораторних умовах на суперкомп’ютерах, та специфіку корпусів тестування. На-
приклад, на тестові корпуси часто накладається умова обмеження словника іменованих сутностей до розміру
словника навчальної вибірки: в таких умовах задача NER (named entity recognition − розпізнавання іменованих
сутностей) зводиться до задачі розпізнавання сутностей за словником.
Через це різниця між заявленими в теорії та отриманими на практиці результатами є досить значною.
Проведена оцінка найбільш популярних систем на ринку показала їх низьку ефективність. Більшість типів іме-
нованих сутностей розпізнаються з точністю близько 60 % – 65 %, що є недостатнім для ефективного викорис-
тання в задачах аналізу текстів. Лише в деяких випадках реальна точність розпізнавання певних типів сутнос-
тей сягає 70 %.
Дане дослідження було проведено з метою розробки придатного для промислового використання класи-
фікатора, здатного розрізняти основні базові типи іменованих сутностей та ефективно працювати з реальними
текстами поза межами лабораторного середовища, і видавати результати на рівні найкращих існуючих аналогів
– state-of-the-art систем.
Система розпізнавання іменованих сутностей тексту
Основною задачею системи є розпізнавання у тексті іменованих сутностей та визначення типу цих сут-
ностей. Вхідними даними системи є текст, написаний правильною англійською мовою з мінімальним вживан-
ням сленгу та відсутністю орфографічних і граматичних помилок.
Архітектурно система складається з кількох ключових блоків, кожен блок виконує функції певного етапу
побудови розв’язку задачі. Усі модулі попередньої обробки тексту для перетворення його у необхідний системі
вигляд винесено за межі системи.
Система структурно складається з наступних блоків:
блок ідентифікації та аналізу іменованих сутностей на основі Байєсівської моделі;
Інтелектуальні інформаційні технології
151
блок ідентифікації та аналізу іменованих сутностей на основі моделі умовних випадкових полів −
Conditional random field (CRF).
Всі блоки є підсистемами, які паралельно і незалежно одна від одної виконують наступну обробку вхід-
ного тексту:
ідентифікація синтаксичних груп речень тексту, які містять іменовані сутності;
визначення меж знайдених іменованих сутностей (перше слово сутності – останнє слово сутності);
визначення типів знайдених іменованих сутностей.
Підсистеми виконують дану обробку тексту з відповідною розміткою.
Результатом роботи системи є текст з відповідною розміткою іменованих сутностей (id сутності, границі
сутності, тип сутності).
Система налаштована для розпізнавання наступних типів іменованих сутностей (Type in system), кожен
тип трактується у відповідності до його трактування у корпусі Ontonotes:
Ontonotes Type Description Type in system
PERSON People, including fictional PERSON
ORGANIZATION Companies, agencies, institutions, etc. ORGANIZATION
LOCATION Locations, mountain ranges, bodies of water LOCATION
Вхідними даними для розроблених класифікаторів є текст англійською мовою, дерева виведення та за-
лежностей речень вхідного тексту, а також всі дані стосовно лексичних значень слів речень тексту згідно розмі-
тки GOLD у корпусі Ontonotes.
Навчання класифікаторів на основі моделі Байєса та на основі моделі умовних випадкових полів −
Conditional random field (CRF) проводилося на базі розміченого текстового корпусу Ontonotes. Так як Байєсівсь-
кі класифікатори є відомим, розповсюдженим та досить простим методом, автор утримується від безпосеред-
нього опису самої моделі Байєса та переходить до методу класифікації на основі умовних випадкових полів −
Conditional random field (CRF) [1].
Класифікатор на основі моделі умовних випадкових полів − Conditional random fields
Метод умовних випадкових полів − Conditional random field (CRF) є аналогом методу марковських випа-
дкових полів (Markov random fields). Даний метод користується широкою популярністю у різних областях шту-
чного інтелекту. Зокрема його успішно використовують у задачах розпізнавання мовлення та образів, в обробці
текстової інформації, у комп’ютерній графіці та в інших задачах.
Марковським випадковим полем називають графову модель, яка використовується для представлення
сумісних розподілів набору декількох випадкових змінних. Формально марковське випадкове поле складається
з наступних компонентів:
неорієнтований граф або фактор-граф G = (V, E), де кожна вершина Vv – випадкова змінна Х і ко-
жне ребро Evu ),( – залежність між випадковими величинами u и v;
набір потенційних функцій (potential function) або факторів }{ k , одна для кожної кліки у графі (кліка
− повний підграф G неорієнтованого графу). Функція k ставить кожному можливому стану елементів кліки у
відповідність деяке невід’ємне дійсне число.
Вершини, що не є суміжними, мають відповідати умовно незалежним випадковим величинам. Група су-
міжних вершин формує кліку, набір станів вершин є аргументом відповідної потенційної функції.
Сумісний розподіл набору випадкових величин }{ kxX у марковському випадковому полі обчислю-
ється за формулою:
k
kk x
Z
xP )(
1
)( }{ ,
де )( }{kk x – потенційна функція, що описує стан випадкових величин у k -ій кліці; Z – коефіцієнт нормаліза-
ції, що обчислюється за формулою:
k
kk
Xx
xZ )( }{ .
Інтелектуальні інформаційні технології
152
Множина вхідних лексем }{ txX та множина відповідних їм типів }{ tyY у сукупності формують
множину випадкових змінних YXV . Для розв’язання задачі виділення інформації з тексту достатньо ви-
значити умовну ймовірність P( Y | X ). Потенційна функція має вигляд:
)),,(exp()( 1}{
k
tttkkkk xyyfx ,
де }{ k – дійснозначний параметричний вектор (множники Лагранжа), )},,({ 1 tttk xyyf – набір ознакових
функцій. Тоді лінійним умовним випадковим полем називається розподіл виду:
k k
tttkk xyyf
xZ
xyp )),,(exp(
)(
1
)|( 1 .
Коефіцієнт нормалізації Z(x) обчислюється за формулою:
k k
tttkk
Yy
xyyfxZ )),,(exp()( 1 .
Обчислення моделі )|( xyp відбувається як розв’язання оптимізаційної задачі з заданими обмеженнями
[2] (різниця між спостереженням та його оцінкою має бути нульовою та має виконуватися умова
Yy
xyp 1)|( по всім Xx .
На кожній ітерації заново обчислюються множники Лагранжа, обчислення проводиться з використанням
традиційних алгоритмів – «forward-backward» та Вітербі.
Метод CRF, як і метод марковські моделі максимальної ентропії (MMME), є дискримінативним імовірні-
сним методом, на відміну від генеративних методів, таких як приховані марковські моделі HMM та модель
Байєса (Naïve Bayes).
За аналогією з марковськими моделями максимальної ентропії, вибір факторів-ознак для завдання імові-
рності переходу між станами при наявності спостереження значення tx залежить від специфіки конкретних
даних, але на відміну від того ж МММЕ, CRF може враховувати будь-які особливості та взаємозв’язки у вхід-
них даних. Вектор ознак }{ k обчислюється на основі навчальної вибірки та визначає вагу кожної потен-
ційної функції.
В умовних випадкових полях відсутня так звана label bias problem – ситуація, коли перевагу мають
стани з меншою кількістю переходів, так як будується один єдиний розподіл імовірностей та нормалізація
(коефіцієнт Z(x)) виконується загалом, а не у рамках окремого стану. Це, безумовно, є перевагою метода:
алгоритм не потребує припущення незалежності спостережних змінних. Крім того, використання довільних
факторів дозволяє описати різноманітні ознаки об’єктів, що знижує вимоги до повноти та обсягу навчальної
вибірки. При цьому точність буде визначатися не лише обсягом вибірки, але й обраними факторами.
Недоліком підходу CRF є обчислювальна складність аналізу навчальної вибірки, що ускладнює пос-
тійне оновлення моделі при отриманні нових навчальних даних. Слід відзначити високу швидкість роботи
алгоритму CRF, що є дуже важливою перевагою при обробці великих обсягів інформації.
Навчання моделі
Для навчання моделі був обраний корпус текстів Ontonotes [3], який містить достатній обсяг текстів, ро-
змічених вручну. Розмітка текстів повністю відповідає задачі ідентифікації та аналізу іменованих сутностей та
обраним моделям машинного навчання. В рамках задачі аналізу іменованих сутностей тексти корпусу містять
розмітку:
задання меж іменованих сутностей (перше слово сутності – останнє слово сутності);
задання типів знайдених іменованих сутностей (Людина, Організація, Локація).
Розмічені тексти містять синтаксичні структури речень – дерева виведення та дерева залежностей. Тобто
доступними є межі синтаксичних груп речення та відношення залежностей між словами. Доступними є також
повні лексичні значення слів речень (частина мови, рід, число, час для дієслів і т. д.). Алгоритми використову-
ють також спеціальні словники імен, географічних назв та типових назв організацій для залучення додаткових
знань у систему.
Для формування базової множини ознакових функцій було проведено дослідження та аналіз найкращих
робіт за даною тематикою [4–6]. Побудовано набор базових ознакових функцій, наприклад:
інакше._,0
,"",ї_літерия_з_великопочинаєтьс_,_якщо_,1
),(
CityхyLOCу
yxf i
Інтелектуальні інформаційні технології
153
Далі в процесі дослідження були проведені чисельні експерименти з навчання моделей на розмічених те-
кстах корпусу Ontonotes, після чого виконувалося тестування навченого алгоритму на точність ідентифікації та
визначення типу іменованих сутностей на текстах з інших частин корпусу. Потім, згідно процедури кросваліда-
ції, навчальна та тестова частини корпусу мінялися місцями та процес навчання і тестування моделей повторю-
вався з початку. Із всіх отриманих оцінок точності обиралися мінімальні, як найбільш об’єктивні та гарантовано
досяжні.
Навчання та тестування моделей проводилось багато разів з різними наборами ознакових функцій. В ре-
зультаті проведення багатьох ітерацій етапів навчання-тестування з перебором множини функцій ознак були
визначені оптимальні набори ознакових функцій {
if } та {
if }, на яких досягнуто максимальні оцінки точно-
сті ідентифікації та визначення типів іменованих сутностей тексту класифікатором Байєса та класифікатором на
базі моделі умовних випадкових полів (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 та інші.
Задача мультикласифікації полягає у знаходженні невідомої функції )(xf , область значень якої дис-
кретна множина, що містить k значень (класів), 2k . Дана функція )(xf визначається у процесі навчання
на основі навчальної вибірки прикладів виду ),( ii dx , ni ,1 , де )( ii xfd – відоме значення класу для прик-
ладу ix .
Вирішення задачі мультикласифікації зводиться до розв’язання підзадач бінарної класифікації, а резуль-
татом мультикласифікації є поєднання отриманих розв’язків. Для поєднання розв’язків бінарних класифікаторів
було застосовано підхід розподіленого вихідного представлення (Distributed Output Representation); як бінарні
класифікатори використовуються класифікатори CRF.
Під розподіленим вихідним представленням розуміється задання кожного класу бінарним рядком дов-
жини n – “кодовим словом”. Кожен біт кодового слова відповідає окремому бінарному класифікатору, який
навчається. Вирішення задачі мультикласифікації зводиться до обробки так званої матриці кодових слів, ряд-
ки якої – кодові слова, що відповідають класам, об’єкти яких розпізнаються, а стовпчики відповідають бінар-
ним класифікаторам (це ті значення, що видають класифікатори на відповідних класах). Після навчання кла-
сифікаторів новий об’єкт x класифікується оцінюванням кожного з n бінарних класифікаторів для отри-
мання n -бітового кодового слова. Отримане кодове слово об’єкта x порівнюється з кожним із k кодових
слів матриці. Об’єкт x належить класу, чиє кодове слово є найближчим згідно вибраної метрики до його
власного слова. Визначення мінімальної відстані від отриманого кодового слова об’єкта x , що класифікуєть-
ся, до одного з кодових слів матриці розглядається як процес декодування. Для реалізації процесу декодуван-
ня використовується відстань Хемінга. Зокрема, мінімальна відстань між отриманим кодовим словом
))(,),(),(()( 21 xfxfxfxf n та кодовими словами матриці M визначається як число позицій, у яких відпо-
відні значення бітів різні.
Від виду матриці кодових слів залежить скільки помилок здатен виправити даний розподілений вихідний
код у процесі декодування. Коди, які дозволяють виправити помилки в процесі декодування називаються коре-
гуючі вихідні коди (Error-Correcting Output Codes). Мірою якості коду є мінімальна відстань Хемінга між парами
кодових слів матриці. Якщо мінімальна відстань Хемінга дорівнює d , відповідний код гарантовано може ви-
правити 2)1( d помилкових біт при декодуванні.
Моделі розподіленого вихідного коду будуються відповідно до різних представлень матриці кодових
слів nkM }1,0{ , де k – кількість класів, n – кількість бінарних класифікаторів, тобто довжина кодового
слова.
У рамках досліджень була використана модель корегуючих вихідних кодів Exhaustive Code. Згідно даної
моделі рядками матриці кодових слів є кодові слова довжини 12 1 k . Перший рядок матриці заповнюється
одиницями, далі i-й рядок матриці заповнюється ik2 нулями та ik2 одиницями, що чередуються, починаючи
з нулів. Приклад матриці з вичерпним кодом для 4-х класів наведено у табл. 1.
Інтелектуальні інформаційні технології
154
Таблиця 1. Вичерпний код для 4-х класів
Клас
Кодові слова
1f 2f 3f 4f 5f 6f 7f
1С 1 1 1 1 1 1 1
2С 0 0 0 0 1 1 1
3С 0 0 1 1 0 0 1
4С 0 1 0 1 0 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, Organization-
Begin, Organization-Inside, NE та OTHER. Матриця кодових слів у цьому випадку складається з 127 бінарних
класифікаторів.
Отримані результати дозволили зробити наступні висновки. У результаті надвеликої кількості лексем,
які відносяться до класу OTHER, та мають велику частоту вживання у корпусі, а також у результаті того,
що деякі ознаки сутностей (досить великий їх відсоток), що належать до основних класів (не до OTHER),
при формуванні бінарного класифікатора потрапляють в один клас, то бінарні класифікатори типу CRF
на таких нерівномірних вибірках показали невисоку якість роботи. Наприклад, при розділенні на два
класи отримаємо, що до одного класу належать високочастотні лексеми з OTHER та низькочастот-
ні з Event, Product, Location тощо, а до другого класу – виключно низькочастотні лексеми з Person
та Organization. Тоді елементи першого класу мають і високу частоту, і значну частину ознак другого класу,
що призводить до значного превалювання першого класу над другим. За рахунок великої кількості помилок,
отриманих бінарними класифікаторами (слід врахувати, що кожен з 15, у випадку 5 класів, та кожен із 127, у
випадку 8 класів, має великий відсоток помилок) застосування розподілених вихідних кодів, зокрема ECOC,
не дозволило отримати бажані високі оцінки якості. Для покращення результатів роботи моделі з викорис-
танням ECOC необхідно мати навчальну вибірку з більш рівномірним розподілом лексем по класах. Проте,
використання підходу ECOC (а саме матриці кодових слів та реалізації процесу декодування за допомогою
обчислення відстаней Хемінга) виправдане як одного з потенційних способів, коли треба знайти лексеми, що
можливо були віднесені не до свого класу.
Отримані результати
У таблицях 2–5 представлені оцінки роботи класифікатора Байєса та класифікатора на основі моделі
умовних випадкових полів (CRF), навчених на оптимальних наборах ознакових функцій { if } та { if }, відпо-
відно. У таблиці 6 надані оцінки роботи мультикласифікатора, побудованого з використанням корегуючих ви-
хідних кодів (ECOC).
В експериментах обчислювалися оцінки точності (Precision, P), повноти (Recall, R) та комбінована
міра 1F :
Recall) (Precision
Recall *Precision*2
1
F .
Таблиця 2. Оцінки класифікатора Байєса на підкорпусі Broadcast News (100 файлів)
Precision Recall F1
LOCATION 0,8242 0,7881 0,8057
ORGANIZATION 0,2552 0,4301 0,3203
PERSON 0,5188 0,9047 0,6594
Total 0,5493 0,7868 0,6469
Інтелектуальні інформаційні технології
155
Таблиця 3. Оцінки класифікатора Байєса на підкорпусі Web text (230 файлів)
Precision Recall F1
LOCATION 0,5423 0,6527 0,5924
ORGANIZATION 0,0412 0,0350 0,0379
PERSON 0,3311 0,6127 0,4299
Total 0,3450 0,4954 0,4067
Таблиця 4. Оцінки класифікатора Байєса на підкорпусі Newswire (1665 файлів)
Precision Recall F1
LOCATION 0,6498 0,8501 0,7365
ORGANIZATION 0,5022 0,7482 0,6010
PERSON 0,6673 0,8388 0,7433
Total 0,5813 0,8003 0,6734
Таблиця 5. Оцінки класифікатора на основі умовних випадкових полів (CRF)
Підкорпуси
Web text Broadcast News Newswire Total
LOC
Precision: 0.8679 Precision: 0.9283 Precision: 0.9198 Precision: 0.9395
Recall: 0.9323 Recall: 0.9530 Recall: 0.9190 Recall: 0.9369
F1: 0.8989 F1: 0.9405 F1: 0.9194 F1: 0.9382
ORG
Precision: 0.7939 Precision: 0.8118 Precision: 0.8810 Precision: 0.8858
Recall: 0.7324 Recall: 0.7768 Recall: 0.8863 Recall: 0.8830
F1: 0.7619 F1: 0.7939 F1: 0.8836 F1: 0.8844
PER
Precision: 0.9157 Precision: 0.8910 Precision: 0.9104 Precision: 0.9207
Recall: 0.9104 Recall: 0.9185 Recall: 0.8895 Recall: 0.9104
F1: 0.9130 F1: 0.9045 F1: 0.8998 F1: 0.9155
TOTAL
Precision: 0.8647 Precision: 0.8909 Precision: 0.9008 Precision: 0.9140
Recall: 0.8638 Recall: 0.9029 Recall: 0.8974 Recall: 0.9092
F1: 0.8643 F1: 0.8968 F1: 0.8991 F1: 0.9116
Інтелектуальні інформаційні технології
156
Таблиця 6. Оцінки мультикласифікатора з використанням корегуючих вихідних кодів (ECOC)
Оцінки точності та повноти, отримані в результаті тестування розробленої системи на базі моделі CRF
(табл. 5), демонструють найвищі значення на рівні найкращих існуючих світових аналогів. На тестових текстах
корпусу Ontonotes розроблена система змогла перевершити показники відомої системи Стенфордського універ-
ситету для розпізнавання іменованих сутностей тексту Stanford Named Entity Recognizer [8]. Це було досягнуто
завдяки успішно проведеній оптимізації набору ознакових функцій, що дало змогу отримати максимально ви-
сокі оцінки точності.
Висновки
На основі двох базових моделей машинного навчання – наївної моделі Байєса та умовних випадкових
полів, – було побудовано систему ідентифікації та аналізу іменованих сутностей тексту. Результати досліджен-
ня та експериментів показали високу якість роботи класифікатора, реалізованого на основі моделі умовних ви-
падкових полів. Досвід найкращих існуючих програмних реалізацій систем аналізу іменованих сутностей текс-
ту приводить до висновку, що саме модель умовних випадкових полів (CRF) оптимально підходить для розроб-
ки класифікаторів іменованих сутностей.
В процесі тестування реалізований алгоритм продемонстрував високу точність визначення типів імено-
ваних сутностей тексту на рівні найкращих існуючих світових аналогів.
Також була досліджена модель, в якій для мультикласифікації іменованих сутностей текстів використо-
вуються корегуючі вихідні коди (ЕСОС). Результати експериментів доводять наявність серйозних перспектив
застосування даного підходу для вирішення класичних та прикладних задач комп’ютерної лінгвістики.
1. Lafferty J., McCallum A., Pereira F. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data // The 18th
International Conference on Machine Learning, June 28-July 1, 2001. Proceedings – Williamstown, MA, USA, 2001 . – P. 282–289.
2. Klinger R., Tomanek K. Classical Probabilistic Models and Conditional Random Fields // Algorithm Engineering Report TR07-2-013,
Department of Computer Science, Dortmund University of Technology, December 2007.
Корпус
WB BN NW
LOC
Precision: 0.8179 Precision: 0.7328 Precision: 0.8271
Recall: 0.6547 Recall: 0.8012 Recall: 0.8113
F1: 0.7273 F1: 0.7655 F1: 0.8191
ORG
Precision: 0.5378 Precision: 0.7637 Precision: 0.7734
Recall: 0.3792 Recall: 0.6354 Recall: 0.7422
F1: 0.4448 F1: 0.6937 F1: 0.7575
PER
Precision: 0.7473 Precision: 0.7804 Precision: 0.8530
Recall: 0.5509 Recall: 0.8567 Recall: 0.8037
F1: 0.6342 F1: 0.816772 F1: 0.8276
TOTAL
Precision: 0.7253 Precision: 0.7590 Precision: 0.8178
Recall: 0.5420 Recall: 0.7644 Recall: 0.7857
F1: 0.6204 F1: 0.7617 F1: 0.8015
Інтелектуальні інформаційні технології
157
3. Linguistic Data Consortium (2011) Text Corpus Ontonotes 4.0 – https://catalog.ldc.upenn.edu/LDC2011T03
4. Turian J., Ratinov L., Bengio Y. Word representations: a simple and general method for semi-supervised learning // The 48th Annual Meeting of
the Association for Computational Linguistics, July 11–16, 2010. Proceedings – Uppsala, Sweden, 2010 . – P. 384–394.
5. Nadeau D., Sekine S. A survey of named entity recognition and classification // Lingvisticae Investigationes. – 2007. – 30 (1). – P. 3–26.
6. Nadeau D., Turney P., Matwin S. Unsupervised Named Entity Recognition: Generating Gazetteers and Resolving Ambiguity // Canadian
Conference on Artificial Intelligence-2006, June 7–9, 2006. Proceedings – Quebec, Canada, 2006 . – P. 266–277.
7. Антонова А.Ю., Соловьев А.Н. Метод условных случайных полей в задачах обработки русскоязычных текстов // Информационные
технологии и системы // Труды международной научной конференции. 1–6 сентября 2013. – Кенигсберг; 2013. – С. 321–325.
8. The Stanford NLP Group (2006–2015) Stanford Named Entity Recognizer. – http://www-nlp.stanford.edu/software//CRF-NER.html
References
1. LAFFERTY J., MCCALLUM A., PEREIRA F. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data.
in The 18th International Conference on Machine Learning. Williamstown, MA, USA. June 28-July 1, 2001. – Williamstown. P. 282–289.
2. KLINGER R., TOMANEK K. Classical Probabilistic Models and Conditional Random Fields. Algorithm Engineering Report TR07-2-013,
Department of Computer Science, Dortmund University of Technology, December 2007.
3. Linguistic Data Consortium (2011) OntoNotes Release 4.0 [Online] Available from: https://catalog.ldc.upenn.edu/LDC2011T03
4. TURIAN J., RATINOV L., BENGIO Y. Word representations: a simple and general method for semi-supervised learning. in The 48th Annual
Meeting of the Association for Computational Linguistics. Uppsala, Sweden. July 11–16, 2010. Uppsala. – P. 384–394.
5. NADEAU D., SEKINE S. A survey of named entity recognition and classification. Lingvisticae Investigationes. 30 (1). – P. 3–26.
6. NADEAU D., TURNEY P., MATWIN S. Unsupervised Named Entity Recognition: Generating Gazetteers and Resolving Ambiguity. in
Canadian Conference on Artificial Intelligence-2006. Quebec, Canada. June 7–9, 2006. Quebec. – P. 266–277.
7. ANTONOVA A.Y., SOLOVYOV A.N. Method of Conditional Random Fields in tasks of russian texts processing. in The International
Conference on Information technologies and systems-2013. Königsberg. September 1-6, 2013. Königsberg. – P. 321–325.
8. The Stanford NLP Group (2006-2015) Stanford Named Entity Recognizer [Online] Available from: http://www-nlp.stanford.edu/software/CRF-
NER.html
Про автора:
Марченко Олександр Олександрович,
доцент, доктор фізико-математичних наук,
доцент кафедри Математичної інформатики факультету кібернетики.
Кількість наукових публікацій в українських виданнях – 52.
Кількість наукових публікацій в іноземних виданнях – 10.
Індекс Гірша – 2.
http://orcid.org/ 0000-0002-5408-5279.
Місце роботи автора:
Київський національний університет імені Тараса Шевченка,
01601, Київ, вул. Володимирська, 64/13.
Факультет кібернетики, кафедра Математичної інформатики.
Тел.: (050) 440 7328.
Факс: (044) 259 0129.
E-mail: rozenkrans@yandex.ua
mailto:rozenkrans@yandex.ua
|