Тарануха Володимир Юрійович Моделі та алгоритми обробки природномовних текстів для флективних мов

Краткое описание

Тарануха Володимир Юрійович, асистент кафедри математичної інформатики Київського національного уні­верситету імені Тараса Шевченка: «Моделі та алгоритми обробки природномовних текстів для флективних мов» (01.05.01 - теоретичні основи інформатики та кіберне­тики). Спецрада Д 26.001.09 у Київському національному університеті імені Тараса Шевченка

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
ІМЕНІ ТАРАСА ШЕВЧЕНКА
Кваліфікаційна наукова
праця на правах рукопису
ТАРАНУХА ВОЛОДИМИР ЮРІЙОВИЧ
УДК 004.912:811.16
МОДЕЛІ ТА АЛГОРИТМИ ОБРОБКИ ПРИРОДНОМОВНИХ ТЕКСТІВ ДЛЯ
ФЛЕКТИВНИХ МОВ
01.05.01 – теоретичні основи інформатики та кібернетики
Подається на здобуття наукового ступеня кандидата фізико-математичних наук
Дисертація містить результати власних досліджень. Використання ідей, результатів
текстів інших авторів мають посилання на відповідне джерело.
_______ Тарануха В.Ю.
Науковий керівник
Анісімов Анатолій Васильович
доктор фізико-математичних наук,
професор
Київ – 2017

ЗМІСТ
ВСТУП................................................................................................................................ 12
РОЗДІЛ 1 ОГЛЯД ІСНУЮЧИХ МОДЕЛЕЙ ТА АЛГОРИТМІВ В ОБЛАСТІ
РОЗПІЗНАВАННЯ УСНОГО МОВЛЕННЯ, ЗОБРАЖЕНЬ ТЕКСТУ І
МОРФОЛОГІЧНОГО АНАЛІЗУ..................................................................................... 19
1.1. Основні підходи до автоматичного розпізнавання усного мовлення та зображень
текстів ................................................................................................................................. 19
1.2. Приховані марковскі моделі для розпізнавання усного мовлення та зображень
текстів ................................................................................................................................. 21
1.2.1. Основні задачі.......................................................................................................... 21
1.2.2. Статистичне моделювання мови............................................................................ 24
1.3. Підходи: моделі, що можуть потенційно покращити розпізнавання для мов з
багатою морфологією ....................................................................................................... 24
1.3.1. Факторизована модель з використанням граматичних класів ........................... 25
1.3.2. Застосування n-грам з вільним порядком слів ..................................................... 26
1.3.3. Застосування синтаксичного аналізатора для наповнення бази n-грам............ 26
1.3.4. Моделі, які статистично враховують віддалений контекст ................................ 27
1.3.5. Моделі, засновані на класах ................................................................................... 28
1.3.6. Моделі на сумішах .................................................................................................. 29
1.3.7. Модель з переключенням....................................................................................... 29
1.3.8 Оптимізація ентропії моделі шляхом оцінки та вилучення шумів ..................... 30
1.3.9 Декомпозиції моделі на дві: модель, засновану на граматичних класах, і
модель, засновану на канонічних формах слів............................................................... 30
1.4. Основні підходи до визначення морфолексичних властивостей слів .................. 31
9
1.5. Залучення розширеного контексту та додаткових знань про мову до визначення
морфологічних характеристик невідомих слів. ............................................................. 32
1.5.1. Алгоритми лабораторії комп'ютерної лінгвістики ІППІ РАН............................ 33
1.5.2. Кластерний аналіз словоформ................................................................................ 35
1.5.3. „Кореляційний” аналіз дерев морфологічного аналізу. ...................................... 37
1.5.4. Модуль морфологічного аналізу незнайомих прізвищ (МАП) у системі Ісіда-Т38
1.6. Висновки до Розділу 1. .............................................................................................. 42
РОЗДІЛ 2. МОДЕЛЬ МОВИ ............................................................................................ 43
2.1. Аналіз морфологічної моделі.................................................................................... 44
2.1.1. Кодування словоформ............................................................................................. 45
2.1.2. Незмінні частини мови ........................................................................................... 46
2.1.3. Іменники................................................................................................................... 46
2.1.4. Прикметники............................................................................................................ 50
2.1.5. Числівники ............................................................................................................... 52
2.1.6. Займенник ................................................................................................................ 54
2.1.7. Дієслово.................................................................................................................... 55
2.1.8. Дієприкметник ......................................................................................................... 57
2.2. Нерегулярна омонімія................................................................................................ 58
2.3. Аналіз елементів моделі рівня речення ................................................................... 59
2.3.1. Іменникові конструкції........................................................................................... 60
2.3.2. Прикметникові та дієприкметникові конструкції................................................ 61
2.3.3. Дієслівні конструкції .............................................................................................. 62
2.3.4. Стійкі словосполучення та усталені вирази ......................................................... 62
10
2.3.5. Проблеми, спричинені нерегулярною омонімією та розривами у конструкціях63
2.3.6. Морфемні конструкції ............................................................................................ 63
2.4. Висновки до Розділу 2 ............................................................................................... 64
РОЗДІЛ 3. ЕВРИСТИЧНИЙ МОРФОЛЕКСИЧНИЙ АНАЛІЗ .................................... 65
3.1. Базовий алгоритм ....................................................................................................... 66
3.1.1. Оптимізація групування ......................................................................................... 66
3.1.2. Джерела даних ......................................................................................................... 70
3.1.3. Схема роботи алгоритму ........................................................................................ 72
3.2. Надбудова над базовим алгоритмом ........................................................................ 77
3.3. Результати комп’ютерних експериментів ............................................................... 81
3.3.1 Результати базового алгоритму .............................................................................. 81
3.3.2 Результати розширеного алгоритму евристичного аналізу................................. 89
3.4. Використання n-грам для визначення авторства тексту ........................................ 91
3.4.1 Трансформація тексту.............................................................................................. 92
3.4.2. Розстановка пауз...................................................................................................... 94
3.4.3. Збір даних на трансформованих текстах .............................................................. 96
3.4.4. Формування вектора ознак тексту......................................................................... 96
3.4.5. Визначення подібності текстів з використанням міри косинусів. ..................... 98
3.4.6. Визначення подібності текстів з використанням ланцюгів Маркова................ 99
3.4.7. Результати атрибуції текстів і їхня інтерпретація ............................................. 100
3.5. Експериментальна перевірка часової стійкості ознаки........................................ 104
3.6. Експерименти для української мови ...................................................................... 106
3.6. Висновки до Розділу 3 ............................................................................................. 107
11
РОЗДІЛ 4. МОДЕЛІ ДЛЯ РОЗПІЗНАВАННЯ ЗОБРАЖЕНЬ ТЕКСТУ ТА УСНОГО
МОВЛЕННЯ .................................................................................................................... 109
4.1. Невід’ємна тензорна факторизація......................................................................... 110
4.2 Керуючий простір структур природної мови......................................................... 112
4.3. Модель, оптимізована для флективних мов .......................................................... 114
4.4. Вхідні дані для експериментів ................................................................................ 118
4.5. Методи згладжування .............................................................................................. 119
4.6. Експеримент з фільтрації......................................................................................... 121
4.7. Теоретичні вимоги перерозподілу.......................................................................... 123
4.7.1 Теореми про збереження властивостей базової моделі у згладженій моделі.. 123
4.8. Експерименти з перерозподілу ............................................................................... 127
4.8.1. Перерозподіл та фільтрація.................................................................................. 129
4.8.2. Перерозподіл з максимальною якістю................................................................ 131
4.9. Висновки до Розділу 4 ............................................................................................. 132
ВИСНОВКИ..................................................................................................................... 133
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ....................................................................... 135
12
ВСТУП
Актуальність теми. Обробка природномовних текстів є однією з важливих
теоретичних і прикладних задач сучасних інформаційних технологій. Переклад,
визначення тематики, реферування, розпізнавання мовлення досліджувалися
починаючи з 70-х років 20-го століття. Зростання технічних можливостей
збереження інформації, швидкості її обробки, накопичення великого обсягу текстів
у цифровому вигляді, реформування державного апарату, перехід до електронного
документообігу, електронного уряду збільшують потребу в сучасних методах
обробки природномовних текстів.
Складна сутність мови з великою кількістю властивостей стала причиною
розробки різнорідних математичних моделей для вирішення задач обробки
природномовних текстів.
Оптимістичні прогнози потужності ЕОМ, роботи В.М. Глушкова та
О.А. Летичевського сприяли розробці методів розпізнавання текстів. Однак ці
результати не гарантували можливості перенесення методів з однієї задачі на іншу,
з обробки писемного мовлення на усне і навпаки. З цією метою Ф. Джелінек ввів до
вжитку серед комп’ютерних лінгвістів апарат прихованих марковських моделей,
розвивали цей напрямок Л. Рабінер, А. Вітербі, Л. Баум, Л. Уелш та ін. Серед
розробників, що працювали зі слов’янськими мовами, відзначилися Т.К. Вінцюк та
Є.К. Людовик. Спільним для цих підходів є використання n-грам (послідовностей з
n елементів тексту) зібраних з відповідних наборів текстів. Для оптимізації nграмних моделей мови використовувалися різні підходи. П. Браун та Р. Мерсер
виділяли кластери класів на одиницях більших ніж фонеми. І. Гуд, С. Катц,
Р. Кнесер займалися згладжуванням моделей мови. Вирішення цих задач було
необхідне для визначення граматичних характеристик (класів) та розпізнавання
мовлення, шляхом виділенні та класифікації слів і послідовностей слів, що
найкраще відповідають мовному сигналу.
Існує велика кількість суттєвих відмінностей між романо-германськими і
слов’янськими мовами: слов’янські мови утворюють групу синтетичних
13
(флективних) мов і наділені відчутною свободою порядку слів у реченні, інформація
про потенційні зв’язки слова зберігається у структурі самого слова. Особливістю
застосування n-грамних моделей мови передбачається щоб навчальний набір текстів
містив значну кількість даних про частоти n-грам (словосполучень). Спочатку
алгоритми розпізнавання розроблялися для англійської мови але при перенесенні
методів з аналітичних мов на флективні, результати виявилися гіршими, внаслідок
вільного порядку слів у реченні та великої кількості словоформ, що значно збільшує
простір станів та зменшує частоту, а відтак і достовірність, окремої n-грами. Крім
того, граматичні та морфологічні ознаки у флективних мовах у першу чергу
закодовані у самих словах, і лише частково – у порядку слів. Таким чином, виникла
необхідність у модифікації моделей мови та алгоритмів обробки текстів для
флективних мов.
Дослідження задач комп’ютерної лінгвістики в першу чергу для слов’янських
мов проводяться під керівництвом А.В. Анісімова на кафедрі математичної
інформатики. О.О. Марченко та О.В. Порхун будували лінгвістичні онтологічні баз
даних, розроблювали систему визначення авторства, вдосконалювали метод
невід’ємної матричної факторизації для побудови лінгвістичних баз даних.
Проте, не досліджувалися ще задачі, що вимагають оптимізація моделей
мови, для використання якомога більшого обсягу інформації з тексту, що і визначає
актуальність дисертаційної роботи.
Зв'язок роботи з науковими програмами, планами, темами. Основні
дослідження за темою дисертації проводились на кафедрі математичної
інформатики факультету кібернетики Київського національного університету імені
Тараса Шевченка в рамках:
1) Державної науково-технічної програми “Образний комп’ютер”, зокрема, у
науково-дослідних роботах за договорами:
 № 03ДП015-01 “Розробити інформаційну технологію синтезу, аналізу,
реферування, пошуку і смислової інтерпретації текстової інформації та
смислового перекладу текстової інформації з однієї мови на іншу” (№
14
держреєстрації 0103U005499). Замовник – Міністерство промислової
політики;
 № 04ДП015-06 “Розробити експериментальну комп'ютерно-лінгвістичну
технологію змістовного аналізу текстової інформації” (№ держреєстрації
0104U004834). Замовник – Міжнародний науково-навчальний центр
інформаційних технологій та систем;
 № 06ДП015-05 “Розробити ескізний проект системи мультилінвістичної
фільтрації та семантичного аналізу текстової інформації на базі
мультилінгвістичної бази знань типу WordNet” (№ держреєстрації
0106U006685). Замовник – Міжнародний науково-навчальний центр
інформаційних технологій та систем;
 № 07ДП015-04 “Розробити систему смислового контекстного аналізу
текстових документів на основі онтологічної бази знань” (№ держреєстрації
0107U003920). Замовник – Міжнародний науково-навчальний центр
інформаційних технологій та систем;
 № 08ДП015-07 “Розробити системи смислової класифікації, рубрикації та
кластеризації природно мовних текстових документів на основі
семантичного аналізу” (№ держреєстрації 0108U007255). Замовник –
Міжнародний науково-навчальний центр інформаційних технологій та систем.
2) науково-технічних робіт за договорами:
 № 05ДП015-03 “Створення технології комп’ютерно – лінгвістичної обробки
текстової інформації на природній мові” (№ держреєстрації 0105U008126).
Замовник – Міністерство освіти та науки України;
 № 07ДП015-06 “Створення глобальної україномовної лексико-семантичної
онтологічної бази лінгвістичних знань та розробка пакету програм
інтелектуальної обробки текстових документів” (№ держреєстрації
0107U006801). Замовник – Міністерство освіти та науки України.
Мета і задачі дослідження. Метою дисертаційної роботи є розробка методу
оптимізації моделей мови для розпізнавання, розробка алгоритмів евристичного
15
морфолексичного аналізу, розробка супровідних алгоритмів на основі аналізу
властивостей моделей мови для слов’янських мов.
Відповідно до сформульованої мети визначено основні завдання роботи:
 дослідження структури внутрішньотекстових залежностей;
 побудова оптимальних моделей представлення внутрішньотекстових
залежностей на рівнях морфем і лексем;
 розробка оптимізованого алгоритму евристичного морфолексичного аналізу;
 вивчення можливостей використання результатів роботи евристичного
морфолексичного аналізу в оптимізованій моделі внутрішньо текстових
залежностей;
 проведення експериментів, що показують дієвість оптимізованих моделей та
алгоритмів;
 розробка програмних засобів, які використовують вищезгадані алгоритми та
моделі.
Об’єктом дослідження дисертаційної роботи є моделі та алгоритми обробки
текстів природною мовою, адаптовані для слов’янських мов, предметом
дослідження – алгоритми евристичного морфолексичного аналізу, моделі опису
мови для розпізнавання мови та методи оптимізації моделей для отримання кращого
розпізнавання.
Методи дослідження - методи теорії імовірності, методи комбінаторної
оптимізації, теорії прийняття рішень, штучного інтелекту тощо.
Дослідження існуючих алгоритмів розпізнавання показали, що найбільш
доцільним для оптимізації розпізнавання буде оптимізація основного джерела даних
алгоритму розпізнавання – бази знань про зв’язки у мові. Завдяки аналізу умов
роботи алгоритмів евристичного морфолексичного аналізу було з’ясовано, що в
тексті є додаткові недосліджені джерела даних, які дозволяють підвищити точність
визначення морфолексичних характеристик.
. Наукова новизна одержаних результатів. Наукова новизна одержаних
результатів полягає у наступному:
16
1. Досліджено структуру взаємозв’язків у тексті з метою виділення ознак,
придатних для морфолексичного аналізу.
2. Розроблено оптимізований евристичний алгоритм морфолексичного аналізу.
Проведено комп’ютерні експерименти, які доводять ефективність
оптимізованого евристичного алгоритму.
3. На основі результатів порівняння моделей морфемного рівня досліджено
властивість мелодійності тексту та сформульовано критерій визначення
авторства для слов’янських мов, який спирається на рефлекторні звички мовця
при формулюванні думки та мелодійність тексту. Проведено комп’ютерні
експерименти, які показують ефективність критерію мелодійності тексту для
визначення авторства.
4. Розроблено систему визначення авторства на основі критерію мелодійності
тексту.
5. Досліджено новий метод оптимізації моделі мови, заснованої на марковських
ланцюжках, для використання в обробці слов’янських мов, який полягає у
декомпозиції моделі мови на модель синтаксичного рівня, модель рівня
семантики ланцюжків лем та подальшу побудову оптимізованої об’єднаної
моделі мови.
6. Сформульовано та доведено теореми, які описують умови збереження та
покращення якості об’єднаної моделі мови після застосування методу
оптимізації.
7. Досліджено вплив фільтрації як допоміжного засобу оптимізації моделі мови,
заснованої на марковських ланцюжках.
8. Проведено комп’ютерні експерименти, що доводять ефективність нового
методу оптимізації моделі мови для слов’янських мов.
Практичне значення одержаних результатів роботи полягає у підвищенні
якості евристичного морфолексичного аналізу, якості визначення авторства та,
головне, якості розпізнавання мови та зображень текстів.
17
Критерій визначення авторства та алгоритм, який на ньому заснований,
використовує ознаки, що слабо контролюються свідомістю, якщо про них не знати,
а отже, дозволяє надійніше віднаходити імітації в текстах.
Алгоритм евристичного морфолексичного аналізу суттєво скорочує час
післяобробки при ручному заповненні словника, та кількість хибних версій
синтаксичного розбору – при автоматичному аналізі текстів.
Метод оптимізації моделі відкриває шлях новому підкласу моделей, що будуть
краще розпізнавати саме слов’янські мови, зокрема українську.
Області використання:
- Системи автоматичної та автоматизованої обробки текстів природною мовою, що
передбачають використання морфолексичного аналізу – від поповнення словників
до здобуття знань з тексту.
- Системи розпізнавання зв’язного мовлення та зображень текстів.
- Системи визначення авторства та системи визначення запозичень.
Особистий внесок здобувача. Усі основні результати дисертації автором
одержано самостійно.
У працях, опублікованих у співпраці з науковим керівником [4, 3, 2], професору
Анісімову А.В. належить постановка задачі та участь в обговоренні результатів.
У роботах [4, 3, 40] автор розробив алгоритми аналізу словоформ в групах,
виконав програмну реалізацію алгоритмів та вніс модифікації.
У роботах [37, 45] дисертант дослідив якість визначення авторства за
допомогою аналізу звукового представлення писаного тексту, дійшов висновку про
придатність цього критерію в якості допоміжного для визначення авторства.
Ідея та реалізація робіт [40, 41, 42, 44] повністю належить автору.
У роботі [41] дисертант побудував оцінку для елементів стандартної моделі і
виконав основні обчислення для аналізу покращення якості розпізнавання шляхом
фільтрації зайвих елементів моделі. У роботі [42] дисертант побудував первинну
згладжену модель та виконав основні обчислення для аналізу покращення якості
моделі оціненої за допомогою ентропії. Робота [44] присвячена розробці
18
теоретичних вимог до згладжування, що дозволяють опрацьовувати стандартну
модель з мінімальними спотвореннями.
У роботі [46] автору належить постановка задачі.
У працях[54, 56, 57], опублікованих з колективом, автору належить частина
практичного доробку.
У роботі [39] дисертант продовжив дослідження особливостей згладженої
моделі.
Апробація результатів роботи дисертаційного дослідження.
Основні результати роботи доповідалися та обговорювалися на наукових
семінарах та конференціях, у тому числі на:
1. Міжнародній конференції з автоматичного управління „Автоматика-2009” ,
м. Чернівці, 22–25 вересня 2009 р.
2. Міжнародній конференції „Обчислювальний інтелект 2011 (Результати,
проблеми, перспективи)” , м. Черкаси, 10–13 травня, 2011 р.
3. Міжнародній науково-практичній конференції з програмування
„УкрПРОГ’2014” , м. Київ, 20–22 травня , 2014 р.
4. 19th International Conference on Application of Natural Language to Information
Systems (NLDB'2014) – Montpellier, France, 18–20 June 2014
5. 17th International Conference on Text, Speech, and Dialogue (TSD 2014) Brno,
Czech Republic 8–12 September 2014
6. 9th International Conference on Natural Language Processing (PolTAL 2014)
Warsaw, Poland 17–19 Sep, 2014
7. Міжнародній науково-практичної конференції «Проблеми інформатики та
комп’ютерної техніки» (ПІКТ – 2016) м. Чернівці 21–24 травня, 2016 р.
Публікації. За темою дисертації основні результати роботи викладено в 14
друкованих роботах, загальним обсягом 6,9 умовних друкованих аркушів, з яких 8 –
статті у наукових фахових журналах, рекомендованих ВАК України (особисто
автору належить 2,5 д.а.). З них 3 виконано без співавторів та 2 статті – у науковому
виданні, що входить до Scopus. Отримано 1 авторське свідоцтво

Список литературы

ВИСНОВКИ
У дисертації проаналізовано особливості моделі мови для слов’янських мов та
на основі результатів аналізу розроблено ряд алгоритмів та методів обробки текстів
природною мовою. Отримані алгоритми та методи здатні покращити роботу
багатьох систем обробки текстів природною мовою.
Алгоритми евристичного морфолексичного аналізу здатні покращити роботу
систем автоматичного та автоматизованого реферування, індексування, смислового
перекладу з однієї мови на іншу, підтримки зв’язного природномовного діалогу.
Алгоритм визначення авторства спрощує задачу визначення авторства
анонімних текстів та задачу визначення плагіату.
Метод згладжування n-грамних моделей потенційно здатний покращити
роботу систем розпізнавання зв’язного мовлення та зображень текстів.
При виконанні роботи були одержані такі результати:
1. Розроблено дієві алгоритми евристичного морфолексичного аналізу та
перевірено якість їхньої роботи. Алгоритм евристичного морфолексичного
аналізу суттєво скорочує час післяобробки при ручному заповненні
словникових баз, тазменшує кількість хибних версій синтаксичного розбору –
при автоматичному аналізі текстів.
2. Використання у якості джерела даних як словника тексту так і
безпосереднього контексту дає найточніший результат.
3. Розроблено критерії визначення авторства на основі псевдозвучання та
перевірено якість роботи алгоритму заснованого на них. Алгоритм
використовує ознаки, які слабо контролюються свідомістю.
4. Завдяки тому, що зазначений алгоритм спирається на нові ознаки, що
практично не враховуються іншими алгоритмами (як-то словникові,
граматичні тощо), його можна зручно додавати до вже існуючих алгоритмів і
отримувати приріст у якості розпізнавання.
134
5. Проаналізовано можливості оптимізації моделі мови у задачах розпізнавання
зв'язного мовлення та зображень текстів. Запропоновано новий метод
згладжування на основі декомпонованої моделі мови за двома групами класів:
лематичних та граматичних.
6. Комп’ютерні експерименти показали, що такий метод як, і очікувалося,
демонструє ознаки, які вказують на можливість зростання якості
розпізнавання.
7. Отриманий приріст якості в отриманому методі згладжування дозволяє
сподіватися, що дослідження в цьому напрямку приведуть у майбутньому до
побудови більш якісних моделей мови адаптованих для флективних мов
взагалі і, зокрема, для слов’янських мов.