Coreference resolution algorithm for Ukrainian-language texts using decision trees

The paper examines the problem of coreference resolution in Ukrainian-language texts using decision trees. An application that uses vector representations of Elmo words and other characteristics for the automated formation of a decision tree has been developed. A set of prepared texts containing mor...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2023
Автори:	Pogorilyy, S. D., Biletskyi, P. V.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2023
Теми:	coreference resolution; natural language processing (NLP); decision trees; artificial intelligence (AI); vector words representation neural networks UDC 004.8
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/510
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-510
record_format	ojs
resource_txt_mv	ppisoftskievua/ca/241063af375c7402df28f9ba9c7ee3ca.pdf
spelling	pp_isofts_kiev_ua-article-5102023-06-24T12:25:37Z Coreference resolution algorithm for Ukrainian-language texts using decision trees Алгоритм пошуку кореферентних об’єктів в україномовних текстах з використанням дерев рішень Pogorilyy, S. D. Biletskyi, P. V. coreference resolution; natural language processing (NLP); decision trees; artificial intelligence (AI); vector words representation, neural networks UDC 004.8 кореферентність; обробка природних мов; дерева рішень; штучний інтелект; векторні представлення слів; нейронні мережі УДК 004.8 The paper examines the problem of coreference resolution in Ukrainian-language texts using decision trees. An application that uses vector representations of Elmo words and other characteristics for the automated formation of a decision tree has been developed. A set of prepared texts containing more than 360,000 words was used to form the decision tree and evaluate the accuracy of the algorithm. The decision tree created to determine whether a pair of objects is coreference was used to form clusters of coreference objects. Special metrics were used for comparison with the results obtained by other algorithms in the Ukrainian language.Prombles in programming 2022; 3-4: 85-91 В роботі розглядається проблема пошуку кореферентних об’єктів в україномовних текстах використовуючи дерева рішень. Роз- роблено застосунок, що використовує векторні представлення слів Elmo та інші характеристики для автоматизованого форму- вання дерева рішень. Для формування дерева та оцінки точності роботи алгоритму використано набір підготовлених текстів, що вміщає понад 360000 слів. Дерево рішень, створене для визначення, чи пара об’єктів є кореферентними, використано для фор- мування кластерів кореферентних об’єктів. Використано спеціальні метрики для порівняння з результатами, отриманих іншими алгоритмами для української мови.Prombles in programming 2022; 3-4: 85-91 Інститут програмних систем НАН України 2023-01-23 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/510 10.15407/pp2022.03-04.085 PROBLEMS IN PROGRAMMING; No 3-4 (2022); 85-91 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3-4 (2022); 85-91 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3-4 (2022); 85-91 1727-4907 10.15407/pp2022.03-04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/510/563 Copyright (c) 2023 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2023-06-24T12:25:37Z
collection	OJS
language	Ukrainian
topic	coreference resolution; natural language processing (NLP); decision trees; artificial intelligence (AI); vector words representation neural networks UDC 004.8
spellingShingle	coreference resolution; natural language processing (NLP); decision trees; artificial intelligence (AI); vector words representation neural networks UDC 004.8 Pogorilyy, S. D. Biletskyi, P. V. Coreference resolution algorithm for Ukrainian-language texts using decision trees
topic_facet	coreference resolution; natural language processing (NLP); decision trees; artificial intelligence (AI); vector words representation neural networks UDC 004.8 кореферентність обробка природних мов дерева рішень штучний інтелект векторні представлення слів нейронні мережі УДК 004.8
format	Article
author	Pogorilyy, S. D. Biletskyi, P. V.
author_facet	Pogorilyy, S. D. Biletskyi, P. V.
author_sort	Pogorilyy, S. D.
title	Coreference resolution algorithm for Ukrainian-language texts using decision trees
title_short	Coreference resolution algorithm for Ukrainian-language texts using decision trees
title_full	Coreference resolution algorithm for Ukrainian-language texts using decision trees
title_fullStr	Coreference resolution algorithm for Ukrainian-language texts using decision trees
title_full_unstemmed	Coreference resolution algorithm for Ukrainian-language texts using decision trees
title_sort	coreference resolution algorithm for ukrainian-language texts using decision trees
title_alt	Алгоритм пошуку кореферентних об’єктів в україномовних текстах з використанням дерев рішень
description	The paper examines the problem of coreference resolution in Ukrainian-language texts using decision trees. An application that uses vector representations of Elmo words and other characteristics for the automated formation of a decision tree has been developed. A set of prepared texts containing more than 360,000 words was used to form the decision tree and evaluate the accuracy of the algorithm. The decision tree created to determine whether a pair of objects is coreference was used to form clusters of coreference objects. Special metrics were used for comparison with the results obtained by other algorithms in the Ukrainian language.Prombles in programming 2022; 3-4: 85-91
publisher	Інститут програмних систем НАН України
publishDate	2023
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/510
work_keys_str_mv	AT pogorilyysd coreferenceresolutionalgorithmforukrainianlanguagetextsusingdecisiontrees AT biletskyipv coreferenceresolutionalgorithmforukrainianlanguagetextsusingdecisiontrees AT pogorilyysd algoritmpošukukoreferentnihobêktívvukraínomovnihtekstahzvikoristannâmderevríšenʹ AT biletskyipv algoritmpošukukoreferentnihobêktívvukraínomovnihtekstahzvikoristannâmderevríšenʹ
first_indexed	2024-09-12T19:29:38Z
last_indexed	2024-09-12T19:29:38Z
_version_	1815407479926816768
fulltext	85 Методи і засоби програмної інженерії УДК 004.8 https://doi.org/10.15407/pp2022.03-04.085 АЛГОРИТМ ПОШУКУ КОРЕФЕРЕНТНИХ ОБ’ЄКТІВ В УКРАЇНОМОВНИХ ТЕКСТАХ ІЗ ВИКОРИСТАННЯМ ДЕРЕВ РІШЕНЬ Сергій Погорілий, Павло Білецький В роботі розглядається проблема пошуку кореферентних об’єктів в україномовних текстах використовуючи дерева рішень. Роз- роблено застосунок, що використовує векторні представлення слів Elmo та інші характеристики для автоматизованого форму- вання дерева рішень. Для формування дерева та оцінки точності роботи алгоритму використано набір підготовлених текстів, що вміщає понад 360000 слів. Дерево рішень, створене для визначення, чи пара об’єктів є кореферентними, використано для фор- мування кластерів кореферентних об’єктів. Використано спеціальні метрики для порівняння з результатами, отриманих іншими алгоритмами для української мови. Ключові слова: кореферентність, обробка природних мов, дерева рішень, штучний інтелект, векторні представлення слів, не- йронні мережі. The paper examines the problem of coreference resolution in Ukrainian-language texts using decision trees. An application that uses vector representations of Elmo words and other characteristics for the automated formation of a decision tree has been developed. A set of prepared texts containing more than 360,000 words was used to form the decision tree and evaluate the accuracy of the algorithm. The decision tree created to determine whether a pair of objects is coreference was used to form clusters of coreference objects. Special metrics were used for comparison with the results obtained by other algorithms in the Ukrainian language. Keywords: coreference resolution, natural language processing (NLP), decision trees, artificial intelligence (AI), vector words representa- tion, neural networks. Вступ Обробка природних мов (natural language processing, NLP) – велика галузь, що включає безліч задач: переклад між природними мовами, інтерфейси людина-комп’ютер, аналіз та генерація природного мовлення, виділення інформації з текстів. Однією із задач обробки природних мов є пошук кореферентних об’єктів у тек- стах. Кореферентність у текстах розуміється як відношення між синтаксичними одиницями, що вказують на один і той самий об’єкт (референт) в даному контексті [1]. Далі наведені приклади кореферентності (референт виділений жирним шрифтом, займенники - під- креслені). Приклад простої анафори: Він перейшов через гору. Вона була високою. Приклад простої катафори: Вона вийшла на дорогу, що вела праворуч. Марія сьогодні мала гарний настрій. Приклад складеного антецеденту. Іван, Михайло та Остап – всі вони працювали під землею. У порівнянні з іншими мовами Європи – англійською, німецькою, французькою, італійською, іспан- ською – для української мови властивий довільний порядок слів, як і для інших слов’янських мов – польської, російської, сербської, хорватської. До прикладу, для української мови: Карпо прикинув таке слівце, що батько перестав стругати і почав прислухатись. Він глянув на синів через хворостяну стіну. Сини стояли без діла й балакали, поспиравшись на заступи (Іван Нечуй-Левицький, «Кайдашева сім’я», оригінальний порядок слів). Із другого речення в прикладі можна перестановкою слів утворити інші граматично коректні речення з дуже близькими значеннями, але різними наголосами, залежно від задуму автора: - Через хворостяну стіну він глянув на синів. - На синів він глянув через хворостяну стіну. - Через стіну хворостяну він глянув на синів. - Через хворостяну стіну глянув він на синів. - Через хворостяну стіну на синів глянув він. Водночас в англійській мові можлива тільки одна комбінація: «He looked at his sons through the twig wall», оскільки в ній використовується стандартний порядок слів суб’єкт – дієслово – об’єкт (SVO, subject verb object). В інших мовах також поширений порядок суб’єкт – об’єкт – дієслово (SOV, subject object verb). У зв’язку з цим алгоритм для української мови має передбачати роботу з різним порядком слів. Виділення кореферентних об’єктів дозволяє знаходити зв’язки між реченнями та всередині них, виді- ляти інформацію із текстів, покращувати результати аналізу текстів в інших задачах, таких, як переклад з однієї мови іншою, оцінка когерентності текстів. © С.Д. Погорілий, П.В. Білецький, 2022 ISSN 1727-4907. Проблеми програмування. 2022. № 3-4. Спеціальний випуск 86 Методи і засоби програмної інженерії На початкових етапах досліджень для пошуку кореферентних об’єктів використовували алгоритми на основі правил, сформованих досвідченими лінгвістами вручну. Такі алгоритми створювалися для конкретної мови та мали враховувати багато особливостей для досягнення якісного аналізу. Із часом для розв’язання задачі почали використовувати автоматизовані підходи, такі як нейронні ме- режі та дерева рішень. Вони не вимагають створення правил вручну, але для їх підготовки необхідні великі на- бори даних. Часто в автоматизованих алгоритмах використовують прості правила для формування початкових кластерів. У статті запропоновано метод пошуку кореферентних об’єктів з використанням дерев рішень. Розро- блено застосунок, що використовує векторні представлення слів Elmo та інші характеристики для автоматизо- ваного формування дерева рішень. Для формування дерева та оцінки точності роботи алгоритму використано набір підготовлених текстів, що містить понад 360000 тисяч слів. Підібрано параметри формування дерева. Дерево рішень, створене для визначення, чи пара об’єктів є кореферентними, використано для формування кластерів кореферентних об’єктів. Використано спеціальні метрики для порівняння з результатами, отримани- ми іншими алгоритмами в українській мові. Засоби, використані для реалізації алгоритму пошуку кореферентних об’єктів Застосунок використовує векторні представлення слів, отримані за допомогою бібліотеки ELMo[2]. Ця бібліотека дозволяє перетворювати слова на вектори, що відповідають їхньому семантичному, лексичному, синтаксичному значенню. На відмінну від інших бібліотек, які дозволяють формувати векторні представлен- ня слів, таких як Word2Vec[3], векторні представлення, сформовані в ELMo, враховують не тільки значення окремого слова, а й значення навколишніх слів. Це дозволяє краще знаходити зв’язки між окремими словами та реченнями. ELMo використовує нейронні мережі для отримання векторних представлень слів та потребуєє навчання. Використана версія адаптована для української мови. Використовується бібліотека Scikit-learn[4]. Ця бібліотека включає багато засобів для розв’язання задач регресії, кластеризації, класифікації. Зокрема, містить оптимізовану реалізацію дерев рішень із можливістю налаштування параметрів побудови дерева. Однією з головних переваг дерев рішень над іншими алгоритмами є можливість візуалізації побудова- ного дерева. Для цього використано бібліотеку Graphviz[5]. Для створення дерева рішень використано підготовлений корпус україномовних текстів, що містить по- над 360000 слів (> 2500 текстів). Розмітка кореферентних об’єктів у ньому проведена вручну, а для отримання додаткової інформації (рід, число лематизована (початкова) версія слова) використано бібліотеку UDpipe[6], що використовує нейронні мережі та навчена на україномовному корпусі текстів. Формат даних для представлення кореферентних об’єктів та їх аналізу Для аналізу текстів за допомогою дерев рішень, їх потрібно подати у правильному вигляді. У роботі використані такі характеристики для опису кореферентних об’єктів (розглядалися у статті [7]): - Косинусна схожість векторів семантичного представлення об’єктів, що розглядаються. Для цього використовувалася попередньо навчена модель ELMo. Якщо кількість слів, що входить в об’єкт > 1, викорис- товується середнє арифметичне векторів слів. - Кількість слів між обраними об’єктами. - Кількість об’єктів між обраними потенційно кореферентними об’єктами. - Булеве значення, правдиве, якщо перший об’єкт займенник. - Булеве значення, правдиве, якщо другий об’єкт займенник. - Булеве значення, правдиве, якщо лематизовані версії (початкові форми слів) об’єктів збігаються. В алгоритмі співпадіння лематизованих версій визначено як співпадіння хоча б одного слова в обох об’єктах, що розглядаються. - Булеве значення, правдиве, якщо в обох об’єктів однакове число (однина чи множина). - Булеве значення, правдиве, якщо в обох об’єктів однаковий рід. - Булеве значення, правдиве, якщо обидва об’єкти власні назви. На вхід алгоритму подається текст, що складається із окремих слів, пунктуації, та додаткової інформа- ції, підготовленої за допомогою бібліотеки UDpipe. Сюди входить рід, число, лематизовані версія слова, час- тина мови. Також, для слів, що входять в кореферентні групи вказується ідентифікатор. Це дозволяє віднести конкретне слово або словосполучення до кореферентної групи (підготовлений вручну). Для роботи алгоритму для кожного тексту, що розглядається, формуються список (Python list), що вміщуєш індекси слів, що входять в словосполучення, які є потенційно кореферентними об’єктами, до їх об’єднання в кореферентні кластери, але у форматі, що полегшує подальше їх об’єднання (1), – окреме сло- во, - словосполучення. (1) Також створюються списки із правильно сформованими кластерами кореферентних об’єктів. Ці списки необхідні на етапі порівняння кластерів, отриманих у результаті передбачень дерева рішень та вірних кластерів (2), , – окремий кластер. 87 Методи і засоби програмної інженерії (2) Оскільки задача кластеризації зведена в алгоритмі до задачі класифікації, для створення дерев рі- шень та передбачень з їхньою допомогою, необхідні списки з параметрами кожної пари потенційно коре- ферентних об’єктів (3), де – косинусна схожість об’єктів, – кількість слів між об’єктами, що розглядаються, – кількість об’єктів між об’єктами, що розглядаються, – довжина (кількість слів) першого об’єкту, – довжина другого об’єкту, – чи перший об’єкт – займенник, – чи другий об’єкт – займенник, – чи перший об’єкт – власна назва, - чи другий об’єкт – власна на- зва, – чи лематизовані версії об’єктів збігаються, – чи об’єкти мають однаковий рід, – чи об’єкти мають однакове число. (3) Також необхідні мітки, що вказують, чи є пара об’єктів, що розглядаються, кореферентними (4). (4) Після створення дерева рішень під час його використання для передбачень із списку (1) утворюється список (5), що містить перелік передбачених кластерів. (5) Отримані списки з характеристиками груп кореферентних об’єктів (3) а також їхнього маркування (4), що містять 2400000 зразків кореферентних та некореферентних об’єктів, діляться на дві частини – перша (1500 текстів, ~ 60%) використовується для формування дерева рішень, друга (1015 текстів, ~ 40%) – для перевірки результативності алгоритму (аналіз отриманих результатів). Алгоритм пошуку кореферентних об’єктів з використанням дерев рішень Формування дерева рішень: Дерево рішень реалізоване з використанням бібліотеки sklearn, яка має клас дерева рішень sklearn.tree.DecisionTreeClassifier. При створенні екземпляру класу визначаються параметри дерева рішень – критерії розділення на піддерева під час формування, максимальна глибина дерева, мінімальна кількість елементнів для розділення, мінімальна кількість елементів в одному листку дерева, ваги для класів, що передбачаються,тощо. За замовчуванням параметри дерева вказані для отри- мання безпомилкової конфігурації дерева на вибірці, що використовується для його формування. Такий підхід призводить до надмірної адаптації дерева до даних, що використовуються при його формуванні та знижує точність роботи на наборах, які раніше не аналізувалися алгоритмом. Також, для великих об’ємів даних внаслідок використання такої конфігурації створюється надміру велике дерево, формування якого забирає багато часу. Отож, постає необхідність обмежити розміри дерева для досягнення вищих результатів на да- них, що не використовувалися для формування дерева. Для цього застосовано параметр min_impurity_ decrease, що дозволяє визначати мінімально достатнє значення зменшення неоднорідності в наступних піддеревах при розділенні. На відмінну від інших способів обмеження розмірів дерева, таких як об- меження глибини або обмеження на кількість елементів у листях, цей показник дозволяє рівномірніше обмежувати розміри дерева. Для формування дерева підготовлені дані пар потенційно кореферентних об’єктів (3) із маркуван- ням, чи є вони кореферентними (4) подаються в функцію fit. На виході отримується дерево, здатне аналі- зувати пари кореферентних об’єктів. Таким чином задачу кластеризації кореферентних об’єктів зведено до задачі класифікації деревом рішень. Частина отриманого дерева показана на Рис. 1. Для ілюстрації глибина дерева та кількість текстів, що аналізуються, штучно обмежена, щоб мати змогу помістити отримане дерево на екрані. Як видно з рисунка, розбиття на кореферентні та некореферентні об’єкти починається із характеристики, що дозволяє найкраще розділити поточну групу об’єктів – співпадіння лематизованих версій об’єктів. Далі, завдяки ви- користанню дерев рішень, в піддереві дерева (Рис. 2) можна прослідкувати наступну логіку – якщо лема- тизовані версії об’єктів співпадають, довжина першого та другого об’єкту – 1 та перший об’єкт є власною назвою, тоді з високою імовірністю пара об’єктів є кореферентними. Використання дерева рішень для пошуку кореферентних об’єктів: після формування дерева рішень створене дерево використовується для отримання кластерів кореферентних об’єктів: відбувається перебір пар об’єктів – кандидатів на кореферентність (1). Для кожної пари об’єктів визначаються параме- три (3), необхідні для класифікації об’єктів деревом рішень. Якщо пара класифікована як кореферентна, відбувається злиття об’єктів. Після утворення кластерів, що містять декілька об’єктів, їх злиття відбува- ється, якщо хоча б одна пара об’єктів із першого та другого кластеру розпізнана кореферентною. Під час експериментальних досліджень виявлено, що при використанні декількох циклів проходів, поки можливе злиття кластерів, результати на метриках (наступний пункт) виявлялися на 2-5% вищими, ніж без викорис- тання циклічних проходів. Тому в фінальній версії алгоритму використовується декілька проходів, допоки в циклі відбувається хоча б одне злиття. В результаті роботи алгоритму утворюється список кластерів, що містить кореферентні об’єкти всередині спільних кластерів(5). 88 Методи і засоби програмної інженерії Методи і засоби програмної інженерії Рис. 1. Дерево рішень Рис. 2. Піддерево дерева рішень Використання дерева рішень для пошуку кореферентних об’єктів: після формування дерева рішень створене дерево використовується для отримання кластерів кореферентних об’єктів: відбувається перебір пар об’єктів – кандидатів на кореферентність (1). Для кожної пари об’єктів визначаються параметри (3), необхідні для класифікації об’єктів деревом рішень. Якщо пара класифікована як кореферентна, відбувається злиття об’єктів. Після утворення кластерів, що містять декілька об’єктів, їх злиття відбувається, якщо хоча б одна пара об’єктів із першого та другого кластеру розпізнана кореферентною. Під час експериментальних досліджень ви- явлено, що при використанні декількох циклів проходів, поки можливе злиття кластерів, результати на метри- ках (наступний пункт) виявлялися на 2-5% вищими, ніж без використання циклічних проходів. Тому в фіналь- ній версії алгоритму використовується декілька проходів, допоки в циклі відбувається хоча б одне злиття. В ре- зультаті роботи алгоритму утворюється список кластерів, що містить кореферентні об’єкти всередині спільних кластерів(5). Рис. 1. Дерево рішень Методи і засоби програмної інженерії Рис. 1. Дерево рішень Рис. 2. Піддерево дерева рішень Використання дерева рішень для пошуку кореферентних об’єктів: після формування дерева рішень створене дерево використовується для отримання кластерів кореферентних об’єктів: відбувається перебір пар об’єктів – кандидатів на кореферентність (1). Для кожної пари об’єктів визначаються параметри (3), необхідні для класифікації об’єктів деревом рішень. Якщо пара класифікована як кореферентна, відбувається злиття об’єктів. Після утворення кластерів, що містять декілька об’єктів, їх злиття відбувається, якщо хоча б одна пара об’єктів із першого та другого кластеру розпізнана кореферентною. Під час експериментальних досліджень ви- явлено, що при використанні декількох циклів проходів, поки можливе злиття кластерів, результати на метри- ках (наступний пункт) виявлялися на 2-5% вищими, ніж без використання циклічних проходів. Тому в фіналь- ній версії алгоритму використовується декілька проходів, допоки в циклі відбувається хоча б одне злиття. В ре- зультаті роботи алгоритму утворюється список кластерів, що містить кореферентні об’єкти всередині спільних кластерів(5). Рис. 2. Піддерево дерева рішень Аналіз отриманих результатів Для оцінки результатів, отриманих внаслідок використання алгоритму пошуку кореферентних об’єктів, використовуються метрики [8] і MUC [9]. Ці метрики дозволяють порівнювати групи класте- рів – із правильним упорядкуванням кореферентних об’єктів (2) та із передбачуваним упорядкуванням (5), чисельно відображаючи різницю між кластерами. Для кожної метрики обчислюється влучність – precision (відношення вірно обраних алгоритмом об’єктів до усіх обраних об’єктів), повнота – recall (відношення вірно обраних алгоритмом об’єктів до усіх об’єктів, що належать до даного кластеру), та F1 міра (середнє гармонійне повноти та влучності). Метрика використовується в широкому колі задач кластеризації. Метрика розглядає окремі еле- менти в списку передбачених кластерів, для яких розраховується інтегральний показник. Влучність для метри- ки визначається як середнє арифметичне влучностей для кожного елемента: Методи і засоби програмної інженерії Аналіз отриманих результатів Для оцінки результатів, отриманих внаслідок використання алгоритму пошуку кореферентних об’єктів, використовуються метрики 𝑏𝑏3 [8] і MUC [9]. Ці метрики дозволяють порівнювати групи кластерів – із правиль- ним упорядкуванням кореферентних об’єктів (2) та із передбачуваним упорядкуванням (5), чисельно відобра- жаючи різницю між кластерами. Для кожної метрики обчислюється влучність - precision (відношення вірно об- раних алгоритмом об’єктів до усіх обраних об’єктів), повнота - recall (відношення вірно обраних алгоритмом об’єктів до усіх об’єктів, що належать до даного кластеру), та F1 міра (середнє гармонійне повноти та влучнос- ті). Метрика 𝑏𝑏3 використовується в широкому колі задач кластеризації. Метрика 𝑏𝑏3 розглядає окремі елеме- нти в списку передбачених кластерів, для яких розраховується інтегральний показник. Влучність для метрики 𝑏𝑏3 визначається як середнє арифметичне влучностей для кожного елемента: 𝑃𝑃 = 1 𝑁𝑁 ∑ 𝑍𝑍𝑛𝑛 𝑇𝑇𝑛𝑛𝑁𝑁 (6) де n – номер обраного елемента, N – кількість елементів у списку, 𝑍𝑍𝑛𝑛 – кількість елементів, що належать до тої ж кореферентної групи, що й обраний елемент (включаючи обраний елемент), та входять у передбачува- ний кластер, 𝑇𝑇𝑛𝑛 – загальна кількість елементів у передбаченому кластері. Повнота для метрики 𝑏𝑏3 визначається як середнє арифметичне повноти для кожного елемента: 𝑅𝑅 = 1 𝑁𝑁 ∑ 𝑍𝑍𝑛𝑛 𝑀𝑀𝑛𝑛𝑁𝑁 (7) де n – номер обраного елемента, N – кількість елементів у списку, 𝑍𝑍𝑛𝑛 – кількість елементів, що належать до тої ж кореферентної групи, що й обраний елемент (включаючи обраний елемент) та входять в передбачува- ний кластер, 𝑀𝑀𝑛𝑛 – загальна кількість елементів в тій же групі, що й обраний елемент. Метрика MUC спеціально розроблена для оцінки ефективності роботи алгоритмів, що розв’язують задач пошуку кореферентних об’єктів. У метриці MUC розглядається весь список кластерів, для якого розраховують- ся показники . Для MUC повнота визначається формулою: 𝑅𝑅 = ∑(\|𝑆𝑆𝑖𝑖\|−\|𝑝𝑝(𝑆𝑆𝑖𝑖)\|) ∑\|𝑆𝑆𝑖𝑖\| (8) де \|𝑆𝑆𝑖𝑖\| –кількість елементів в істинному кореферентному кластері, \|𝑝𝑝(𝑆𝑆𝑖𝑖)\|- кількість підгруп, на які іс- тинний кореферентний кластер ділять передбачувані кластери. Влучність визначається як: 𝑃𝑃 = ∑(\|𝑆𝑆𝑖𝑖 , \|−\|𝑝𝑝,(𝑆𝑆𝑖𝑖 ,)\|) ∑\|𝑆𝑆𝑖𝑖 , \| (9) де \|𝑆𝑆𝑖𝑖 ,\| –кількість елементів у передбачуваному кореферентному кластері, \|𝑝𝑝,(𝑆𝑆𝑖𝑖 ,)\|- кількість підгруп, на які передбачуваний кореферентний кластер ділять істинні кластери. Для кожної метрики обчислюється F1 міра, що визначається формулою: 𝐹𝐹1 = 2∗𝑅𝑅∗𝑃𝑃 𝑅𝑅+𝑃𝑃 (10) де R – повнота, P – влучність. Оцінка результатів роботи отриманого дерева рішень виконується на частині корпусу, що не використо- вувалася під час його формування (1015 текстів). Під час проведення експереминтальних досліджень визначено оптимальне значення параметру min_impurity_decrease, за якого досягнуто найвищих результатів на метриках 𝑏𝑏3 і MUC. Результати порівняння роботи з іншими алгоритмами, що використовувалися для аналізу україномо- вних текстів [1, 7], наведені в табл. 1. Для метрики 𝑏𝑏3 дерево рішень показує найвищі результати порівняно з іншими підходами. На метриці MUC підхід з використанням дерев рішень показує значно вищі результати, ніж досягнуті з використанням зго- рткової нейронної мережі (CNN) [7] та моделі природної мови RoBERTa [1], на рівні двозв’язної нейронної ме- режі з довгою та короткочасною пам’яттю (BiLSTM) [7]. Варто зазначити, що влучність алгоритму для даного дерева рішень на метриці MUC та 𝑏𝑏3 найвища порівняно з іншими підходами, водночас повнота перебуває на рівні варіанту BiLSTM з одним проходом. При цьому параметри формування дерева рішень дозволяють підви- щити його влучність за рахунок зниження повноти або навпаки, тим самим адаптуючись до випадків, для яких важливіша точність для знайдених кореферентних об’єктів (влучність) чи знаходження більшої частини коре- ферентних об’єктів (повнота). (6) де n – номер обраного елемента, N – кількість елементів у списку, – кількість елементів, що належать до тої ж кореферентної групи, що й обраний елемент (включаючи обраний елемент), та входять у передбачуваний кластер, – загальна кількість елементів у передбаченому кластері. 89 Методи і засоби програмної інженерії Повнота для метрики визначається як середнє арифметичне повноти для кожного елемента: (7) де n – номер обраного елемента, N – кількість елементів у списку, – кількість елементів, що належать до тої ж кореферентної групи, що й обраний елемент (включаючи обраний елемент) та входять в передбачуваний кластер, – загальна кількість елементів в тій же групі, що й обраний елемент. Метрика MUC спеціально розроблена для оцінки ефективності роботи алгоритмів, що розв’язують задач пошуку кореферентних об’єктів. У метриці MUC розглядається весь список кластерів, для якого роз- раховуються показники. Для MUC повнота визначається формулою: (8) де – кількість елементів в істинному кореферентному кластері, – кількість підгруп, на які істинний коре- ферентний кластер ділять передбачувані кластери. Влучність визначається як: (9) де – кількість елементів у передбачуваному кореферентному кластері, – кількість підгруп, на які передбачуваний кореферентний кластер ділять істинні кластери. Для кожної метрики обчислюється F1 міра, що визначається формулою: (10) де R – повнота, P – влучність. Оцінка результатів роботи отриманого дерева рішень виконується на частині корпусу, що не викорис- товувалася під час його формування (1015 текстів). Під час проведення експереминтальних досліджень ви- значено оптимальне значення параметру min_impurity_decrease, за якого досягнуто найвищих результатів на метриках і MUC. Результати порівняння роботи з іншими алгоритмами, що використовувалися для аналізу україномовних текстів [1, 7], наведені в табл. 1. Таблиця 1. Порівняння ефективності алгоритмів на метриках та MUC Модель Метрика MUC CNN Влучність 24.23 97.88 Повнота 12.45 84.99 F1 16.44 92.11 BiLSTM (1 прохід) Влучність 56.91 95.94 Повнота 30.20 88.76 F1 29.46 92.21 BiLSTM (декілька проходів) Влучність 56.36 93.13 Повнота 39.68 90.43 F1 45.88 91.76 RoBERTa Влучність 27.39 91.22 Повнота 13.10 89.65 F1 17.72 90.43 Дерево рішень Влучність 73.46 98.15 Повнота 29.08 88.14 F1 41.67 92.87 Для метрики дерево рішень показує найвищі результати порівняно з іншими підходами. На метри- ці MUC підхід з використанням дерев рішень показує значно вищі результати, ніж досягнуті з використанням згорткової нейронної мережі (CNN) [7] та моделі природної мови RoBERTa [1], на рівні двозв’язної нейрон- ної мережі з довгою та короткочасною пам’яттю (BiLSTM) [7]. Варто зазначити, що влучність алгоритму для даного дерева рішень на метриці MUC та найвища порівняно з іншими підходами, водночас повнота перебуває на рівні варіанту BiLSTM з одним проходом. При цьому параметри формування дерева рішень до- зволяють підвищити його влучність за рахунок зниження повноти або навпаки, тим самим адаптуючись до випадків, для яких важливіша точність для знайдених кореферентних об’єктів (влучність) чи знаходження більшої частини кореферентних об’єктів (повнота). 90 Методи і засоби програмної інженерії Висновки У процесі виконання роботи розглянуто задачу пошуку кореферентних об’єктів в українській мові. Створено застосунок, що використовує дерева рішень для пошуку кореферентних об’єктів: під- готовлено дані для аналізу, побудовано дерево рішень, модифіковано його параметри для досягнення вищих результатів, оцінено продуктивність застосунку на метриках і MUC. Дерева рішень завдяки можливості графічного представлення дозволяють полегшити аналіз отриманих результатів та поясни- ти, як саме отримується той чи інший результат, що відрізняє їх від інших популярних методів аналізу даних, зокрема, нейронних мереж. Отримані результати показують порівняно високу ефективність алгоритму – досягнуто найвищі показники на метриці та порівняно високі на метриці BiLSTM, із найвищими показниками влучності, що вказує на доцільність використання дерев рішень для пошуку кореферентних об’єктів в україномов- них текстах. Література 1. С.Д. Погорілий, П.В. Білецький. Використання графічного процесора для прискорення пошуку кореферентних об’єктів з використан- ням моделі RoBERTa. Наукові праці ДонНТУ, Серія: “Інформатика, кібернетика та обчислювальна техніка”, 2022. № 2. С. 4-9. 2. M. Peters, M. Neumann, M. Iyyer, M. Gardner, C. Clark, K. Lee, L. Zettlemoyer.. Deep contextualized word representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2018, № 1. С. 2227–2237. 3. T. Mikolov, I. Sutskever, K. Chen, G. Corrado, J. Dean. Distributed Representations of Words and Phrases and their Compositionality. Proceedings of the 26th International Conference on Neural Information Processing Systems, 2013, № 2, С. 3111–3119. 4. Бібліотека Scikit-learn. https://scikit-learn.org/ 5. Бібліотека Graphviz. https://graphviz.org/ 6. Бібліотека UDpipe. https://lindat.mff.cuni.cz/services/udpipe/ 7. S. Telenyk, S. Pogorilyy, A. Kramov. The complex method of coreferent clusters detection based on a BiLSTM neural network, Knowledge Based Systems. 2021. C. 205-210. 8. A. Bagga, B. Baldwin, Algorithms for Scoring Coreference Chains, The First International Conference on Language Resources and Evaluation Workshop on Linguistics Coreference, 1998, C. 563-566. 9. M. Vilain, J. Burger, J. Aberdeen, D. Connolly, L. Hirschman, A Model-Theoretic Coreference Scoring Scheme, Proceedings of the 6th Conference on Message Understanding (MUC), 1995. References 1. POGORILYY S. & BILETSKYI P. (2022) Usage of a graphics processor to accelerate coreference resolution while using the RoBERTa model. Scientific works of DonNTU, Series: “Informatics, cybernetics and computer technology”. (2) P. 4-9. 2. PETERS M., NEUMANN M., IYYER M., GARDNER M., CLARK C., LEE K., ZETTLEMOYER L.. (2018) Deep contextualized word representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, (1). P. 2227–2237. 3. MIKOLOV T., SUTSKEVER I., CHEN K., CORRADO G., DEAN J.. (2013) Distributed Representations of Words and Phrases and their Compositionality. Proceedings of the 26th International Conference on Neural Information Processing Systems, (2). P. 3111–3119. 4. Scikit-learn library. https://scikit-learn.org/ 5. Graphviz library. https://graphviz.org/ 6. UDpipe library. https://lindat.mff.cuni.cz/services/udpipe/ 7. TELENYK S., POGORILYY S., KRAMOV A. (2021) The complex method of coreferent clusters detection based on a BiLSTM neural network, Knowledge Based Systems. P. 205-210. 8. BAGGA A., BALDWIN B., (1998) Algorithms for Scoring Coreference Chains, The First International Conference on Language Resources and Evaluation Workshop on Linguistics Coreference, P. 563-566. 9. VILAIN M., BURGER J., ABERDEEN J., CONNOLLY D., HIRSCHMAN L. (1995) A Model-Theoretic Coreference Scoring Scheme, Proceedings of the 6th Conference on Message Understanding (MUC). Одержано 17.08.2022 Про авторів: Погорілий Сергій Дем’янович доктор технічних наук, професор, Кількість публікацій в українських виданнях – 109. Кількість зарубіжних публікацій – 67. https://orcid.org/0000-0002-6497-5056. Білецький Павло Володимирович, аспірант, Кількість публікацій в українських виданнях – 3. https://orcid.org/0000-0002-4248-4766. 91 Методи і засоби програмної інженерії Місце роботи авторів: Факультет радіофізики, електроніки та комп’ютерних систем, Київський національний університет імені Тараса Шевченка, 03187, м. Київ, проспект Академіка Глушкова, 4г Тел.: (38)(044) 521-05-32 E-mail: rex@knu.ua Прізвища та ініціали авторів і назва доповіді англійською мовою: Pogorilyy S. D.. Biletskyi P. V. Coreference resolution algorithm for Ukrainian-language texts using decision trees Прізвища та ініціали авторів і назва доповіді українською мовою: Погорілий С. Д., Білецький П. В. Алгоритм пошуку кореферентних об’єктів в україномовних текстах з використанням дерев рішень Контакти для редактора: Погорілий Сергій Дем’янович, доктор технічних наук, професор, кафедра Комп’ютерної інженерії факультету радіофізики, електроніки та комп’ютерних систем, Київський національний університет імені Тараса Шевченка, e-mail: sdp77@i.ua. Білецький Павло Володимирович, аспірант, кафедра Комп’ютерної інженерії факультету радіофізики, електроніки та комп’ютерних систем, Київський національний університет імені Тараса Шевченка, e-mail: 1234bpv@i.ua, тел.: (38)(050) 735-59-35.

Coreference resolution algorithm for Ukrainian-language texts using decision trees

Репозитарії

Схожі ресурси