ВОЗНЮК Тарас Григорович. ЗАСТОСУВАННЯ СЕМАНТИКО-СИНТАКСИЧНОЇ ТЕНЗОРНОЇ МОДЕЛІ ПРИРОДНОЇ МОВИ ДЛЯ АНАЛІЗУ КОРЕФЕРЕНТНИХ ЗВ’ЯЗКІВ У ТЕКСТАХ

brief description

ВОЗНЮК Тарас Григорович. Назва дисертаційної роботи: "ЗАСТОСУВАННЯ СЕМАНТИКО-СИНТАКСИЧНОЇ ТЕНЗОРНОЇ МОДЕЛІ ПРИРОДНОЇ МОВИ ДЛЯ АНАЛІЗУ КОРЕФЕРЕНТНИХ ЗВ’ЯЗКІВ У ТЕКСТАХ"

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
ІМЕНІ ТАРАСА ШЕВЧЕНКА
На правах рукопису
ВОЗНЮК ТАРАС ГРИГОРОВИЧ
УДК 681.3
ЗАСТОСУВАННЯ СЕМАНТИКО-СИНТАКСИЧНОЇ ТЕНЗОРНОЇ
МОДЕЛІ ПРИРОДНОЇ МОВИ ДЛЯ АНАЛІЗУ
КОРЕФЕРЕНТНИХ ЗВ’ЯЗКІВ У ТЕКСТАХ
01.05.01 – теоретичні основи інформатики та кібернетики
Дисертація на здобуття наукового ступеня кандидата
фізико-математичних наук
Науковий консультант
МАРЧЕНКО ОЛЕКСАНДР ОЛЕКСАНДРОВИЧ
доктор фізико-математичних наук,
доцент
Київ – 2015
2
Зміст
Список умовних позначень .................................................................... 5
Вступ......................................................................................................... 6
Розділ 1. Аналіз сучасного стану галузі вирішення
кореферентностей ............................................................................................ 32
1.1 Постановка задачі вирішення кореферентностей..................... 32
1.2 Алгоритми вирішення проблеми анафори................................ 35
1.3 Алгоритм вирішення кореферентностей................................... 40
1.4 Формальні моделі мови............................................................... 45
1.4.1 Латентний семантичний аналіз. .......................................... 45
1.4.2 Невід’ємна тензорна факторизація. .................................... 46
1.4 Висновки....................................................................................... 49
Розділ 2. Побудова тензорної моделі керуючих просторів
природномовних речень.................................................................................. 51
2.1 Аналіз формальної моделі керуючих просторів
природномовних речень.............................................................................. 51
2.2 Постановка задачі побудови керуючого простору................... 56
2.3 Попередній синтаксичний аналіз............................................... 61
2.3.1 Розбиття тексту на речення. ................................................ 61
2.3.2 Розбиття речення на лексеми. ............................................. 62
2.3.3 Морфологічний аналіз.......................................................... 63
2.3.4 Виділення іменованих сутностей........................................ 65
2.3.5 Алгоритм виділення іменованих сутностей на основі
аналізу сторінок Вікіпедії ....................................................................... 66
2.3.6 Побудова дерева виведення................................................. 67
2.2.7 Побудова дерева залежностей............................................. 70
3
2.4 Алгоритм побудови шестивимірного тензора для задачі
пошуку прихованих семантичних зв’язків в корпусах природномовних
текстів............................................................................................................ 71
2.4.1 Мотивація побудови шестивимірного тензора.................. 71
2.4.2 Алгоритм виділення елементів тензора ............................. 73
2.4.3 Збереження даних................................................................. 76
2.4.4 Невід’ємна факторизація тензорів ...................................... 77
2.5 Алгоритм побудови керуючого простору природномовних
речень ............................................................................................................ 80
2.5.1 Конвертація типу зв’язку дерева залежностей в тип зв’язку
керуючого простору ................................................................................ 80
2.5.2 Створення елементу керуючого простору для двох слів.. 83
2.5.3 Створення складного елементу керуючого простору для
піддерева дерева виведення .................................................................... 84
2.5.4 Рекурсивний обхід дерева виводу для побудови керуючого
простору.................................................................................................... 88
2.5.5 Підвищення точності алгоритму побудови керуючого
простору за допомогою використання інформації про виділені
іменовані сутності.................................................................................... 93
2.6 Виділення типових елементів природномовних речень.......... 95
2.6.1 Збереження тензора в реляційній базі даних ..................... 95
2.6.2 Архітектура системи обробки великих текстових
корпусів..................................................................................................... 97
2.7 Профілювання та оцінка результатів....................................... 100
2.8 Висновки..................................................................................... 102
Розділ 3. Алгоритми визначення кореферентних зв’язків за
допомогою статистичної інформації типових структур
керуючих просторів ....................................................................................... 104
4
3.1 Пошук сутностей ....................................................................... 104
3.2 Зведення задачі знаходження кореферентних зв’язків до
тернарного класифікатора пари сутностей.............................................. 106
3.3 Порівняння піддерев ................................................................. 107
3.4 Оцінка наявності кореферентного зв’язку за допомогою
виявлення семантичного паралелізму керуючих просторів .................. 110
3.5 Визначення слів індикаторів як фактор-множин розкладених
тензорів ....................................................................................................... 112
3.6 Особливості тензорної факторизації розгорнутих та кільцевих
альфа-бета зв’язків..................................................................................... 113
3.7 Модифікація алгоритму опорних векторів для великих об’ємів
негативних прикладів ................................................................................ 115
3.8 Простір ознак машинного навчання ........................................ 119
3.9 Оцінка результатів роботи алгоритму пошуку
кореферентностей ...................................................................................... 122
3.10 Висновки................................................................................... 125
Висновки............................................................................................... 126
Список використаних джерел............................................................. 128
Додаток А. Опис тегів частин мови................................................... 140
Додаток Б. Таблиця відповідності тегів дерева залежностей типам
зв’язку керуючого простору ......................................................................... 145
Додаток В. Опис тегів дерева виводу ................................................ 148
5
Список умовних позначень
ДЗ – дерево залежностей
КП – керуючий простір
ЛСА – латентний семантичний аналіз
НТФ – невід’ємна тензорна факторизація
ПАРКС – паралельні асинхронні рекурсивно керовані системи
ШІ – штучний інтелект, AI, artificial intelligence
BCU – block coordinate update, поблоковий координатний спуск
ConLL – the Conference on Natural Language Learning
FP – false positive, хибний позитивний результат
MUC – message understanding conference,
SAX - Simple API for XML
TP – true positive, правильний позитивний результат
XML - Extensible Markup Language, розширювана мова розмітки
WSD – word sense disambiguation, вирішення лексичної
багатозначності
6
Вступ
Актуальність теми дослідження. В наш час бурхливого
розширення сфер застосування інформаційних технологій задачі обробки
текстів природною мовою набувають великого значення в науці, економіці
та інших сферах життя суспільства. Автоматичний переклад тексту
допомагає людям з різних країн розуміти один одного без докладання
значних зусиль та витрат часу. Компанії-гіганти, такі як Google та
Facebook застосовують методи комп’ютерної обробки текстів для
покращення точності цільової реклами, аналізуючи переписку та пошукові
запити користувачів. Фірми, що займаються соціологічними
дослідженнями, мають змогу оцінювати ставлення людей до певних осіб
чи подій на основі автоматичного аналізу публікацій у пресі, залишених
користувачами коментарів, повідомлень на форумах. І це далеко не
повний перелік практичних задач, для розв’язання яких використовуються
методи та алгоритми комп’ютерної лінгвістики.
Для того, щоб автоматичний переклад текстів одразу видавав
результат, який не потребує кропіткої додаткової вичитки, необхідно, щоб
комп’ютер був здатний розуміти текст на рівні людини. Для оцінки
складності задач штучного інтелекту аналогічно до класу NP-повних
задач, введено клас AI-повних (Artificial Intelligence) задач, повне
вирішення яких вимагає побудови штучного інтелекту, близького до рівня
інтелектуальних здібностей дорослої людини.
Задача повного розуміння текстів є вкрай складною, тому її
розбивають на підзадачі – розуміння значень окремих слів, розуміння
певних типів зв’язків між словами та їх залежностей, розуміння речень
природною мовою в контексті всього текста в цілому чи в контексті знань
людини про конкретну предметну область. При автоматичному аналізі
природномовних текстів, необхідно різні слова ототожнювати з однією
сутністю. Ця підзадача важлива для більш глибокого розуміння тексту.
7
Зв’язок що виникає між такими словами називається кореферентним. Він
виникає між словами та словосполученнями, що посилаються на один і
той самий об'єкт позамовної дійсності. Так як іменник “дівчина” та
займенник “вона” в загальному випадку не обов’язково вказують на одну і
ту саму людину, наявність такого зв’язку можна визначити лише з
контексту в якому слова були вжиті. Вирішенню задачі кореферентного
аналізу були присвячені роботи Шолома Лапіна, Герберта Ліса, Руслана
Міткова, Хійан Лі, Анатолія Анісімова, Олександра Марченка та багатьох
інших вчених.
Для аналізу текстів довільної тематики традиційні підходи зі
складанням словників та правил їх обробки вимагають багато кропіткої
праці. Саме тому актуальною є розробка систем, що здатні до
самонавчання із автоматизованим виділенням даних про навколишній світ
з нерозмічених природномовних текстів. Для вирішення даної задачі
можуть бути використані такі потужні моделі як керуючі простори
синтаксичних структур речень природною мовою, реалізовані за
допомогою методів невід’ємної факторизації лінгвістичних тензорів з
елементами машинного навчання. Це в свою чергу вимагає розвитку
зазначених моделей семантико-синтаксичних структур природної мови та
алгоритмів їх обробки. Важливість розв’язання задачі автоматизації
побудови кореферентних зв’язків при обробці природномовних текстів і
визначає актуальність дисертаційної роботи.
Зв'язок роботи з науковими програмами, планами, темами.
Дисертаційна робота є складовою частиною наукових робіт, які ведуться
на кафедрі математичної інформатики факультету кібернетики Київського
національного університету імені Тараса Шевченка при виконанні
фундаментальної теми “Створення теоретичних основ методів та
програмних засобів інтелектуалізації інформаційно–комунікаційних та
8
трансформерних технологій” (державний номер реєстрації – 0111U005416,
2011–2015 рр.)
Мета і задачі дисертаційного дослідження. Метою дисертаційної
роботи є побудова математичних моделей представлення семантикосинтаксичних структур текстів та розробка алгоритму кореферентного
аналізу на основі створених моделей.
З огляду на мету в роботі ставляться такі задачі:
1. Розробити нові методи оцінки наявності кореферентного зв’язку
між парою сутностей за допомогою методів машинного навчання на
розширеному семантико-синтаксичними ознаками просторі.
2. Побудувати та дослідити алгоритми оцінки синтаксичного та
семантичного паралелізму на основі тензорної моделі.
3. Розробити та математично обґрунтувати алгоритм побудови
багатовимірного тензору опису структур природної мови та
архітектуру системи, що здатна обробляти великі текстові корпуси.
4. Розробити алгоритм побудови керуючих просторів синтаксичних
структур для збагачення тензорної моделі мови та довести його
коректність та обчислити складність в термінах швидкодії та
пам’яті.
5. Провести експерименти з оцінки точності роботи алгоритму
знаходження кореферентних зв’язків та порівняти його результати з
іншими алгоритмами.
Об’єкт дослідження – моделі семантико-синтаксичних структур
природномовних текстів та методи аналізу текстів на їх основі.
Предмет дослідження – алгоритми кореферентного аналізу в
контексті семантико-синтаксичних тензорних моделей.
Методи дослідження. Дослідження базуються на методах та
алгоритмах теорії графів, теорії синтаксичного аналізу, тензорного
9
числення, штучного інтелекту, машинного навчання, методики побудови
комп'ютерно-лінгвістичних систем.
Наукова новизна одержаних результатів. У дисертаційній роботі
розроблено та математично обґрунтовано алгоритми для вирішення задачі
ідентифікації та аналізу кореферентних зв’язків у природномовних текстах
і отримано такі нові наукові результати:
1. Розроблено нові методи оцінки наявності кореферентного зв’язку
між парою слів за допомогою машинного навчання.
2. В методі опорних векторів удосконалено алгоритм навчання для
класифікації кореферентних сутностей. Це дало змогу одержати
більш точні результати класифікації для типової задачі
знаходження кореферентностей, коли кількість негативних
прикладів на декілька порядків перевищує кількість позитивних
прикладів.
3. Для підвищення точності роботи класифікатора було розроблено
розширений простір ознак із додаванням семантико-синтаксичних
ознак.
4. Для обчислення нових ознак для класифікатора було вперше
побудовано алгоритми оцінки синтаксичного та семантичного
паралелізму на основі тензорної моделі.
5. Для тензорної моделі мови розроблені алгоритм наповнення
багатовимірного тензору опису структур природної мови та
потокову архітектуру системи обробки великих текстових корпусів.
Тестування системи було проведено на корпусі розміром 100Гб.
6. Для покращення тензорної моделі мови розроблено алгоритм
побудови керуючих просторів синтаксичних структур, доведено
його коректність та обчислено складність в термінах швидкодії та
пам’яті.
10
7. В результаті реалізації даних алгоритмів було підвищено точність
системи знаходження кореферентних зв’язків на 3.5%.
Теоретичне і практичне значення одержаних результатів.
Наукове значення роботи полягає в розробці алгоритмів побудови
керуючих просторів для природномовних текстів за допомогою
конвертації дерев виведення та дерев залежностей, а також у побудові
тензорної моделі керуючих просторів на основі виділення
закономірностей з багатовимірних частотних словників типових керуючих
просторів, що є розвитком математичних моделей представлення
семантико-синтаксичних структур текстів.
Практичне значення роботи полягає в покращенні результатів
вирішення проблеми побудови відношення кореферентності. Зменшення
помилок роботи даної підсистеми автоматично покращує результати
наступних прикладних задач:
− автоматичний переклад текстів;
− автореферування;
− природномовні інтерфейси до експертних систем та баз даних
− пошукові системи.
Отримані результати впроваджуються для досліджень в області
розробки засобів інтелектуальної обробки текстів природною мовою та
для читання курсів "Штучний інтелект" та "Комп'ютерна лінгвістика" на
факультеті кібернетики Київського національного університету імені
Тараса Шевченка.
Особистий внесок здобувача. Всі результати дисертаційної роботи
отримані автором самостійно, сформульовані у вигляді теорем та
алгоритмів та строго доведені з використанням допоміжних лем та
тверджень, обґрунтовані з посиланнями на використані джерела.
11
За результатами дисертації опубліковано вісім робіт у наукових
фахових виданнях України [5-7, 87, 90-93], одна стаття у науковому
журналі, внесеному до міжнародних наукометричних баз [87].
У роботах, опублікованих у співавторстві:
– у статті [87] пошукачу належать результати роботи над розробкою
моделі природної мови та програмна реалізація алгоритмів побудови
розробленої моделі.
– у роботах міжнародних конференцій [5–7] пошукачу належать
результати досліджень над розробкою та реалізацією потокової
архітектури обробки великих текстових корпусів, уточненням деталей
алгоритмів та їх реалізації, проведення експериментів, розроблено методи
оцінки якості результатів та проведення тестування згідно з зазначеними
методами.
Апробація результатів дисертації. Результати дисертації були
представлені на міжкафедральних семінарах факультету кібернетики
Київського національного університету імені Тараса Шевченка та
Національного університету «Києво-Могилянсько академія» та
доповідались на міжнародних конференціях, зокрема на:
1. АNLDB’2014, 19-th International Conference on Applications of
Natural Language to Information Systems, Natural Language Processing
and Information Systems, Montpellier, France, June 18-20, 2014;
2. TSD’2014, 17th International Conference on Text, Speech and
Dialogue, Brno, Czech Republic, September 8–12, 2014;
3. PolTAL’2014, 9th International Conference on Natural Language
Processing, Warsaw, Poland 17–19 September 2014;
Публікації. За результатами дисертації опубліковано 8 наукових
праць, у тому числі 5 – статті у фахових виданнях наукових праць,
12
затверджених МОН України, 1 стаття у журналі, внесеному до
міжнародних наукометричних баз, 3 – публікації у матеріалах і працях
наукових конференцій.
Структура та обсяг дисертації. Дисертаційна робота складається із
вступу, трьох розділів, висновків та списку використаних джерел.
Загальний обсяг роботи становить 141 сторінка, основний текст роботи
викладено на 95 сторінках, список використаних джерел налічує 102
найменування на 11 сторінках. Текст роботи написаний українською
мовою.
ОСНОВНИЙ ЗМІСТ
У вступі обґрунтовано актуальність роботи, наведено короткий
огляд основних результатів досліджуваної галузі, сформульована мета
дисертаційної роботи, проаналізовані основні результати та наведено їх
новизну.
У розділі 1 “Аналіз сучасного стану галузі вирішення
кореферентностей” дано системний аналіз існуючих моделей мови та
алгоритмів, що використовуються для вирішення кореферентностей.
У підрозділі 1.1 “Постановка задачі вирішення кореферентностей”
визначено місце задачі вирішення кореферентностей в практичних задачах
комп’ютерної лінгвістики. Сформульовано означення кореферентного
зв’язку та наведені приклади речень з кореферентними сутностями.
У підрозділі 1.2 “Алгоритми вирішення проблеми анафори”
проаналізовано деталі роботи існуючих алгоритмів одного з типів
кореферентних зв’язків – анафоричних займенників. Один з перших
алгоритмів для вирішення займенникової анафори був розроблений
Джеррі Хоббсом [36]. В статті пропонується 2 підходи до вирішення
13
проблеми анафори. Перший наївний алгоритм обходить дерево виводу
спеціальним чином, пов’язуючи іменники коректного роду та числа з
займенниками. В наступному алгоритмі Хобса продемонстровано, як за
допомогою складної системи семантичного аналізу англомовних текстів
можна знаходити пари антецедент-анафора з більшою точністю. Робота
цього алгоритму була продемонстрована на декількох реченнях.
Іншим оригінальним алгоритмом вирішення проблеми анафори є
алгоритм Шалома Лаппіна та Герберта Лісса [65]. Алгоритм
застосовується до формальної моделі тексту, що породжена парсером
граматик слотів МакКорда і спирається на міри характерних
особливостей, отриманих з синтаксичної структури і динамічної моделі
станів. На простій тестовій вибірці з 360 займенниками, алгоритм успішно
ідентифікував антецедент в 86% випадків. Алгоритм Лаппіна та Ліса
показав на 4% кращий результат, ніж алгоритм Хоббса.
Один з найбільш розвинених на даний момент алгоритмом
вирішення проблеми анафори є алгоритм Міткова [55, 56]. Даний
алгоритм є розвитком ідей Лапіна і Ліса. В роботі вводяться нові критерії
оцінки: синтаксичний паралелізм, повторюваність кандидата, схоже
положення, підмет, доповнення, часте згадування. Також з’являються
штрафні критерії, наприклад у випадку не визначеної граматичної ролі
слова.
В роботі [85] для вирішення задачі знаходження анафоричних
зв’язків було використано методи машинного навчання. Для прийняття
рішення алгоритмом використовувалася система алгоритмів опорних
векторів (Support Vector Machines). В роботі представлені модифікації
класичного алгоритму навчання виходячи з особливостей тренувальної
вибірки поставленої задачі. В якості прецеденту виступає пара анафораантецедент, яка належить до одного з двох класів залежно від наявності в
ній референції.
14
В підрозділі 1.3 “Алгоритм вирішення кореферентностей”
досліджено алгоритми знаходження кореферентностей довільного типу.
Один з перших побудованих алгоритмів для знаходження
кореферентностей в нерозмічених текстах без обмежень тематики був
розроблений в 2001 році [35]. Метод заснований на машинному навчанні.
Для кожної пари слів та словосполучень (i,j), що перевіряються на
кореферентність, розглядаються 12 простих евристичних критеріїв. Для
побудови класифікатора формується тренувальна вибірка з пар слів, для
яких відомо, чи вони є кореферентними. Також для них відомо значення
12 сформованих критеріїв.
В роботі [39] представлено нове архітектурне рішення розв’язку
проблеми кореферентність в вигляді поєднання декількох “решіт”. Кожне
решето реалізовує деякий алгоритм оцінки пари слів чи словосполучень на
кореферентність, працює незалежно, та може повертати одне з трьох
значень : сутності кореферентні, не кореферентні чи “не знаю”.
Робота Лі [2] є розширенням розробленої в попередній дослідженій
системі архітектури заснованої на решетах. В ній вводяться додаткові
реалізації решіт, а також алгоритм визначення кандидатів слів та
словосполучень на кореферентність. Ця робота продемонструвала
найкращі результати на тестовій вибірці конференції CoNLL-2011 [22].
В підрозділі 1.4 “Формальні моделі мови” проаналізовано існуючі
моделі мови, що можуть бути використані для розв’язку
кореферентностей.
В підрозділі 1.4.1 досліджено латентний семантичний аналіз (ЛСА)
[44]. ЛСА – це метод обробки інформації природною мовою, що дозволяє
проаналізувати взаємозв'язок між колекцією документів і термінами, які в
них зустрічаються. Алгоритм зіставляє деякі фактори (теми) всім
документам і термам. В основі методу латентно-семантичного аналізу
лежать принципи факторного аналізу, зокрема, виявлення латентних
15
зв'язків досліджуваних явищ або об'єктів. При класифікації чи
кластеризації документів цей метод використовується для вилучення
контекстно-залежних значень лексичних одиниць за допомогою
статистичної обробки великих корпусів текстів.
Недоліком ЛСА є його обмеженість обробкою двовимірних матриць,
а значить виділяються тільки бінарні зв’язки. В природномовних текстах
зв’язки в загальному випадку можуть бути складнішими, і охоплювати
одразу групу слів. Для вирішення цієї проблеми, було використано
невід’ємну факторизацію тензорів.
В підрозділі 1.4.2 проаналізовано невід’ємну факторизацію тензорів
[75] як розвиток ідеї ЛСА.
Означення. Нехай �",�$, . . . ,�& ∈ ℕ – розміри тензора по кожному з
напрямків. В роботі тензор � ∈ ℝ,-×,/×...×,0 порядку N визначається як Nвимірний масив з елементами �2-,2/,...,20, �4 ∈ {1,2, . . . ,�&}, 1 ≤ � ≤ �.
Зовнішній добуток тензорів � ∈ ℝ,-×,/×...×,0 та � ∈ ℝ=-×=/×...×=>
визначається за допомогою формули:
� = � ∘ � ∈ ℝ,-×,/×...×,0×=-×=/×...×=>,
де ∘ – символ операції зовнішнього добутку.
По-елементно операція зовнішнього добутку визначається як:
�2-,2/,...,2C,D-,D/,...,DE = �2-,2/,...,2C�D-,D/,...,DE,
де �2-,2/,...,2C,D-,D/,...,DE, �2-,2/,...,2C та �D-,D/,...,DE −
елементи тензорів �, �, � відповідно
Особливими випадками є зовнішні добутки двох векторів � ∈ ℝ, та
� ∈ ℝ=:
� = � ∘ � = ��Y ∈ ℝ,×=
та трьох векторів � ∈ ℝ,
, � ∈ ℝ= та � ∈ ℝ[:
� = � ∘ � ∘ � ∈ ℝ,×=×[,
де �2D] = �2�D�]
16
Постановка задачі факторизації тензорів. Для даного тензора � ∈
ℝ,×Y×[ і додатнього індексу J знайти три матриці, що називаються
матриці навантаження або фактори, � = [�",
�$, . . . , �=] ∈ ℝ,×=, � =
[�",
�, . . . , �=] ∈ ℝY×=,� = [�",
�, . . . , �D] ∈ ℝ[×=, що задовільняють наступним
умовам:
� → ���
� = �D ∘ �D ∘ �D + � =
De" (*)
Умова (*) в поелементній формі:
�2f] = �2D�fD�]D
=
De"
+ �2f]
Індекс J в даній задачі називають кількістю фактор-множин.
В розділі 2 “Побудова тензорної моделі керуючих просторів
природномовних речень” розроблено алгоритми побудови формальних
моделей мови для заданого речення та встановлено їх обчислювальну
складність.
В підрозділі 2.1 “Аналіз формальної моделі керуючих просторів
природномовних речень” проаналізовано зазначену формальну модель
синтаксичного представлення [86]. На відміну від суто лінгвістичного
підходу, речення в цій моделі розглядається як деякий динамічний
обчислювальний рекурсивний процес, що розвивається в керуючому
просторі, що пов'язує синтаксично згруповані частини пропозиції
інформаційними каналами. Структура керуючого простору відображає
семантику визначальних і предикативних конструкцій мови.
Якщо два об'єкти А і В вступають у відношення С, то ми виділяємо
об'єкт (припустимо А), що викликає (ініціює, породжує) це відношення, і
об'єкт, на який передається це відношення. Таким чином, виділяємо два
види спрямованих зв'язків: від об'єкта-генератора відношення до самого
відношення і від відношення до підлеглого об'єкту. Перший вид зв'язку
17
називаємо α-зв'язком (зв'язок генерування), другий – β-зв'язком (зв'язок
поширення). Дієслова визначають відносини між об'єктами, тому в
стандартній схемі простого речення: “іменник – дієслово – іменник” αзв'язок направлений від першого іменника до дієслова і β-зв'язок
направлений від дієслова до іменника-визначення.
Розглянемо приклад. Дівчинка збирає квіти. Об'єкт “дівчинка”
генерує відношення збирає і направляє його на об'єкт “квіти”. Тому α-βструктура цього речення має вигляд Рис. 1.а). Розглянемо фразу: Красива
дівчинка. Тут об'єкт дівчинка генерує унарне ставлення красива і передає
це відношення собі ж (Рис. 1.б). Виникає кільцевий зв'язок, що
характеризує зміст словосполучення.
а)
б)
Рис. 1. Керуючий простори фрагментів речень а) “Дівчинка збирає
квіти” та б) “Красива дівчинка”.
У підрозділі 2.2 “Постановка задачі побудови керуючого простору”
наведено вхідні та вихідні дані алгоритму та спроектовано рекурсивні
структури даних для представлення керуючого простору.
Вхідними даними алгоритму є не розмічений текст природньої мови.
Вихідними даними алгоритму є керуючий простір природномовних
текстів в деякому представленні. Для повного опису вихідних даних
алгоритму залишилося дати формальний опис цієї структури даних.
Проведемо декомпозицію КП та формалізуємо його. Керуючий простір
складається з елементів та зв’язків між ними.

bibliography

Висновки
Основним результатом дисертації є розробка та математичне
обґрунтування нових алгоритмів ідентифікації та аналізу кореферентних
зв’язків у природномовних текстах, що має істотне значення для
розв’язання фундаментальної задачі комп’ютерної
лінгвістики - семантичного аналізу текстів. Для цього було застосовано
тензорну модель природної мови, керуючі простори синтаксичних
структур речень та методи машинного навчання. При виконанні роботи
одержано такі наукові результати:
1. В методі опорних векторів удосконалено алгоритм навчання для
класифікації кореферентних сутностей. Це дало змогу одержати
більш точні результати класифікації для типової задачі
знаходження кореферентностей, коли кількість не кореферентних
пар слів на декілька порядків перевищує кількість кореферентних
пар.
2. Для підвищення точності класифікації було розроблено
розширений простір ознак із додаванням семантико-синтаксичних
властивостей. Для обчислення параметрів кореферентних пар в
розширеному просторі ознак було вперше побудовано алгоритми
оцінки синтаксичного та семантичного паралелізму на основі
тензорної моделі.
3. Для тензорної моделі мови розроблено алгоритм побудови
багатовимірного масиву опису структур речень та потокову
архітектуру системи обробки великих текстів. Тестування системи
було проведено на наборі текстів сумарним розміром 100Гб.
4. Розроблено новий алгоритм побудови керуючих просторів
синтаксичних структур речень, який дозволив отримати зручне та
127
стисле представлення моделі, зменшити розмірність тензора,
отримати більш надійний та стійкий опис семантико-синтаксичних
зв’язків між словами. Доведено коректність та обчислено
складність алгоритму в термінах швидкодії та пам’яті.
5. Для тестування розробленої системи використовувалася введена
конференцією CoNLL-2011 вибірка, яка є стандартом для аналізу
роботи систем кореферентних зв’язків. В результаті інтеграції
розроблених алгоритмів в одну з найкращих систем визначення
кореферентних зв’язків Stanford Deterministic Coreference Resolution
вдалось покращити за запропонованою на конференції MUC-6
мірою точність визначення на вказаній тестовій вибірці з 61.03% до
64.45%