Насіров Еміл Мехдієвич Паралелізація невід’ємної факторизації розріджених лінгвістичних матриць та тензорів надвеликої розмірності : Насиров Эмил Мехдиевич параллелизация неотъемлемой факторизации разреженных лингвистических матриц и тензоров сверхбольшой размерности Nasirov Emil Mehdiyevich Parallelization of integral factorization of sparse linguistic matrices and tensors of very large dimension

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

Насіров Еміл Мехдієвич, аспірант кафедри математичної інформатики, Київський національний університет імені Тараса Шевченка. Назва дисертації: «Паралелізація невід’ємної факторизації розріджених лінгвістичних матриць та тензорів надвеликої розмірності». Шифр та назва спеціальності 01.05.01 - теоретичні основи інформатики та кібернетики. Спецрада Д26.001.09 Київського національного університету імені Тараса Шевченка

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

Зміст
Умовні позначення ......................................................................................... 16
Вступ................................................................................................................ 17
Розділ 1. Аналіз сучасного стану галузі факторизації матриць та тензорів
надвеликої розмірності ............................................................................................ 35
1.1 Постановка задачі факторизації розріджених матриць та тензорів
надвеликої розмірності ........................................................................................ 35
1.2 Підходи до невід’ємної факторизації матриць та тензорів .......... 36
1.3 Лінгвістичні матриці та тензори ..................................................... 42
Висновки до Розділу 1 ............................................................................... 51
Розділ 2. Паралелізація невід’ємної факторизації розріджених матриць
надвеликої розмірності ............................................................................................ 52
2.1 Алгоритм невід’ємної факторизації матриць ................................ 52
2.2 Паралелізація алгоритму з використанням GPU........................... 57
2.3 Розподілена версія алгоритму ......................................................... 64
2.4 Оптимізація зберігання та передачі розріджених матриць .......... 70
2.5 Нормалізація ненульових елементів блоків матриці .................... 75
2.6 Тестування швидкодії ...................................................................... 78
Висновки до Розділу 2 ............................................................................... 84
Розділ 3. Паралелізація невід’ємної факторизації розріджених тензорів
надвеликої розмірності ............................................................................................ 86
3.1 Невід’ємна факторизація тензору ................................................... 86
3.2 Розподілення алгоритму невід’ємної факторизації тензорів ....... 88
15
3.3 Зведення задачі невід’ємної факторизаціх тензорів рангу 3 до
невід’ємної факторизації матриць ...................................................................... 89
Висновки до Розділу 3 ............................................................................... 93
Розділ 4. Блочно-діагональний підхід до невід’ємної факторизації
матриць та тензорів .................................................................................................. 94
4.1 Аналіз блочно-діагонального підходу............................................ 95
4.2 Приведення матриці до блочно-діагональної форми.................... 98
4.3 Проблема приведення розріджених матриць та тензорів до блочнодіагонального виду ............................................................................................. 101
Висновки до Розділу 4 ............................................................................. 112
Розділ 5. Формування тематичних діагональних блоків........................ 113
5.1 Тематичне моделювання текстового корпусу ............................. 114
5.2 Використання латентного розподілу Діріхле для приведення
матриць та тензорів до блочно-діагонального форми .................................... 118
5.3 Підтримка збагачення моделі новими даними ............................ 120
5.4 Порівняння швидкодії.................................................................... 122
Висновки до Розділу 5 ............................................................................. 123
Висновки ....................................................................................................... 125
Список використаних джерел ..................................................................... 127
ДОДАТОК А. ................................................................................................ 134
ДОДАТОК Б.................................................................................................. 136
ДОДАТОК В. ................................................................................................ 137
16
Умовні позначення
NF – невід’ємна факторизація;
NMF - невід’ємна матрична факторизація;
NTF - невід’ємна тензорна факторизація;
TD-матриця – матриця зв’язності Слово-Документ, що містить частоту
входження слова в документі;
sizeof (X) – об’єм пам’яті, необхідний для зберігання матриці Х;
nnz(S) – кількість ненульових елементів матриці S;
СОО – координатний формат зберігання матриць;
CSR - формат стиснутих розріджених рядків зберігання матриць;
CSС - формат стиснутих розріджених стовпчиків зберігання матриць;
GPU(Graphics Proccesing Unit) - графічний процесор;
CPU(Central processing unit) - центральний процесор;
SM - потоковий мультипроцесор графічного процесору;
SP - потоковий процесор графічного процесору;
SIMT – виконання однієї команди на декількох потоках;
FLOPS - одиниця вимірювання швидкодії обчислювальних приладів;
GPGPU - Обчислення загального призначення на графічних процесорах;
I/O – операції читання-запису даних;
PLSA (probabilistic latent semantic analysis) - Імовірнісний латентний
семантичний аналіз;
BDF – блочно-діагональна форма.
17
Вступ
Актуальність теми дослідження. Сьогодні для багатьох задач
інформаційної галузі постає проблема автоматичного виділення важливої
інформації з тексту та здобування лінгвістичних знань з великих наборів текстів
природною мовою. Однією з найважливіших та найскладніших задач є
розуміння природномовного тексту. Невід’ємна матрична та тензорна
факторизація використовується в комп’ютерній лінгвістиці для розв’язання
таких прикладних задач, як класифікація, кластеризація текстів та термінів,
побудова мір семантичної близькості, автоматичне виділення лінгвістичних
структур та відношень, для автоматизації створення опису лінгвістичних
структур та інших в рамках методу латентно-семантичного аналізу. Такий підхід
дає можливість отримання ключових ознак тексту природною мовою, які дають
уявлення про його зміст та смисл, а саме теми, концепції та семантика.
Невід’ємна факторизація великих багатовимірних масивів даних, знайшла
своє використання і в інших галузях та є широко вживаною технологією для
обробки звукових спектрограм або м'язової активності, обробки та аналізу
графічних зображень, обробки відео-зображень та багатьох інших задач обробки
та аналізу великих масивів даних.
Ще в середині 1990-х фінською групою дослідників були проведені
дослідження невід'ємного матричного розкладу під назвою позитивне
розкладання матриці. Метод став більш широко відомий як невід'ємний
матричний розклад, після того як Лі і Сонг побудували ітеративний алгоритм та
досліджували його властивості. Застосування невід’ємної матричної та тензорної
факторизації для обробки природної мови та побудови онтологічних баз знань
досліджувалось Анісімовим А.В., Марченко О.О., але були обмежені обробкою
не великих корпусів даних.
Обчислення невід’ємної факторизації розріджених матриць надвеликої
розмірності представляє особливий інтерес та актуальність з точки зору її
18
застосування у великих системах обробки природної мови загального
тематичного призначення, не обмежених використанням лише для вузьких
предметних областей. При побудові таких систем необхідна обробка надвеликих
невід’ємних матриць та тензорів, таких як матриці Слова-Статті або лінгвістичні
тензори Підмет-Присудок-Додаток. Для підтримання якості роботи таких систем
в умовах стрімкого росту текстових даних також є потреба в постійній обробці
нових текстів та донаповнення системи новими даними, що в існуючих
алгоритмах потребує багато часу та обчислювальних ресурсів для повторної
факторизації всієї матриці або тензору.
Використання стандартних алгоритмів факторизації стає практично
неможливим через поліноміальну складність існуючих алгоритмів та NPповноту даної задачі. Разом із надвеликими розмірами лінгвістичних матриць та
тензорів це призводить до неприйнятно великих об’ємів обчислень. Такі
обчислення не можуть бути виконані за реальний час без ефективного
розпаралелення та відповідних обчислювальних потужностей. Для обробки
великих корпусів текстів може бути використане виконання паралельних
розрахунків на графічних процесорах. Це в свою чергу вимагає розробки
спеціального методу паралелізації матричних та тензорних обчислень та
приведення до блочно-діагонального виду.
Сказане вище обґрунтовує теоретичну та практичну актуальність
дисертаційної роботи.
Зв'язок роботи з науковими програмами, планами, темами.
Дисертаційна робота є складовою частиною наукових робіт, які велися на
кафедрі математичної інформатики факультету кібернетики Київського
національного університету імені Тараса Шевченка при виконанні
фундаментальної теми “Створення теоретичних основ методів та програмних
засобів інтелектуалізації інформаційно–комунікаційних та трансформерних
технологій” (державний номер реєстрації – 0111U005416, 2011-2015 рр.) та
держбюджетної науково-дослідної роботи РОЗРОБКА ЛОГІКО-
19
АЛГОРИТМІЧНИХ МЕТОДІВ ДОСЛІДЖЕННЯ ФОРМАЛЬНИХ МОДЕЛЕЙ
ПРИРОДНИХ МОВ (ТЗ НДР № 16БФ015-04, 2016-2018 р.р.)
Мета і задачі дисертаційного дослідження. Метою дисертаційної роботи
є побудова моделей паралельних алгоритмів невід’ємної факторизації
лінгвістичних розріджених матриць та тензорів надвеликої розмірності для
зменшення необхідного часу та обчислювальних ресурсів.
З огляду на мету в роботі ставляться такі задачі:
1. Розробити паралельний алгоритм факторизації матриць та тензорів для
виконання обчислень на графічних процесорах.
2. Побудувати розподілений алгоритм факторизації матриць та тензорів
надвеликої розмірності для виконання обчислень не мережі
обчислювальних вузлів та зменшення необхідного часу.
3. Розробити метод факторизації лінгвістичних матриць та тензорів за
допомогою приведення до блочно-діагонального виду для зменшення
оброблюваних об’ємів даних.
4. Розробити алгоритм формування тематичних діагональних блоків
лінгвістичних матриць та тензорів з використанням генеративних
статистичних моделей для отримання додаткових семантичних зв’язків
меж термами.
5. Провести експерименти з оцінки швидкодії запропонованого алгоритму
та порівняти його результати з іншими алгоритмами.
Об’єкт дослідження – алгоритми невід’ємної факторизації матриць та
тензорів.
Предмет дослідження – моделі паралелізації алгоритмів невід’ємної
факторизації розріджених матриць та тензорів надвеликої розмірності.
Методи дослідження. Дослідження базуються на методах та алгоритмах
багатовимірного аналізу та лінійної алгебри, тензорного числення, паралельних
20
обчислень, теорії синтаксичного аналізу, штучного інтелекту, методики
побудови комп'ютерно-лінгвістичних систем.
Наукова новизна одержаних результатів. У дисертаційній роботі
розроблено нові моделі паралелізації для вирішення задачі факторизації
надвеликих розріджених матриць та тензорів і отримано такі нові наукові
результати:
1. Розроблено нову модель паралелізації алгоритмів факторизації
матриць та тензорів з виконанням обчислень на графічних
процесорах з оптимальним порядком виконанням операції, для
зменшення часу читання та запису даних в пам’ять графічних
процесорів.
2. Розроблено нову модель розподіленого алгоритму факторизації
матриць та тензорів надвеликої розмірності оптимізувавши
використанням мережевих ресурсів для зменшення часу,
необхідного для передачі даних.
3. Розроблено новий метод факторизації розріджених лінгвістичних
матриць та тензорів за допомогою приведення до блочнодіагонального виду з можливістю донаповнення новими даними.
4. Вперше розроблено алгоритм формування тематичних діагональних
блоків лінгвістичних матриць та тензорів з використанням моделі
латентного розподілу Діріхле.
5. Проведене тестування показало, що реалізація даних алгоритмів
підвищує швидкодію факторизації матриць та тензорів, зменшує
необхідні обчислювальні ресурси та об’єм необхідних операцій
читання-запису та мережевих операцій.
Теоретичне і практичне значення одержаних результатів. Наукове
значення роботи полягає в розробці моделі паралелізації алгоритмів
21
факторизації лінгвістичних матриць та тензорів надвеликої розмірності
побудованих з природньомовних текстів.
Практичне значення роботи полягає в значному покращенні швидкодії
алгоритмів факторизації. Зменшення необхідних обчислювальних ресурсів для
виконання невід’ємної факторизації надвеликих матриць та тензорів дозволяє
проводити подальші дослідження в умовах обмежених ресурсів.
Отримані результати впроваджуються для досліджень у області розробки
засобів інтелектуальної обробки текстів природною мовою та в якості матеріалів
для курсів "Штучний інтелект" та "Комп'ютерна лінгвістика" на факультеті
комп'ютерних наук та кібернетики Київського національного університету імені
Тараса Шевченка.
Особистий внесок здобувача. Всі результати дисертаційної роботи
отримані автором самостійно, сформульовані у вигляді алгоритмів та методів та
обґрунтовані з посиланнями на використані джерела.
За результатами дисертації опубліковано одинадцять робіт у наукових
фахових виданнях України [1–5], одна стаття у науковому журналі, внесеному
до міжнародних наукометричних баз [5].
У роботах, опублікованих у співавторстві:
– у статтях [1,5] пошукачу належать результати роботи над розробкою
моделей паралелізації факторизації матриць та тензорів та програмна реалізація
розроблених моделей паралелізації алгоритмів.
– у тезах міжнародних конференцій [6,7] пошукачу належать результати
роботи над розробкою паралельних та розподілених алгоритмів та їх реалізації ,
проведення експериментів та проведення тестування.
Апробація результатів дисертації. Результати дисертації були
представлені на міжкафедральних семінарах факультету комп'ютерних наук та
22
кібернетики Київського національного університету імені Тараса Шевченка та
доповідались на міжнародних конференціях, зокрема на:
1. TSD’2014, 17th International Conference on Text, Speech and Dialogue, Brno,
Czech Republic, September 8–12, 2014;
2. PolTAL’2014, 9th International Conference on Natural Language Processing,
Warsaw, Poland 17–19 September 2014;
3. TAAC’2015, Міжнародна наукова конференція студентів, аспірантів та
молодих вчених «Теоретичні та прикладні аспекти кібернетики», 23-27
листопада 2015 року
4. MPZIS-2015, XIІI міжнародна науково-практична конференція
«Математичне та програмне забезпечення інтелектуальних систем», м.
Дніпропетровськ, Україна, 18-20 листопада 2015 року
5. AIIS’2015, Міжнародної науково-технічної конференції «ШТУЧНИЙ
ІНТЕЛЕКТ ТА ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ», м. Бердянськ, Україна.
21– 26 вересня 2015 р.
6. IEEE ATIT 2019, IEEE International Conference on Advanced Trends in
Information Theory, Kyiv, Ukraine, 18-20.12.2019
Публікації. За результатами дисертації опубліковано 11 наукових праць, у
тому числі 5 – статті у фахових виданнях наукових праць, затверджених МОН
України, 1 стаття у журналі, внесеному до міжнародних наукометричних баз, 6
– публікації у матеріалах і тезах наукових конференцій.
Структура та обсяг дисертації. Дисертаційна робота складається із
вступу, п’яти розділів, висновків, списку використаних джерел та трьох
додатків. Загальний обсяг роботи становить 149 сторінок, основний текст роботи
викладено на 114 сторінках, список використаних джерел налічує 55
найменувань на 7 сторінках. Текст роботи написаний українською мовою

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

Висновки
У дисертації приділено багато уваги попереднім роботам та проведено
ретельний аналіз існуючих підходів до невід’ємної факторизації матриць та
тензорів, з точки зору швидкодії та можливості використання для обробки
надвеликих лінгвістичних матриць та тензорів. Проте існуючі підходи мають
суттєві недоліки що робить не можливим їх використання в великих системах
обробки природньої мови. Цим зумовлюється важливість проведеного
дослідження. Детальний огляд літератури, джерел та подальше дослідження і
розробка нових методів та алгоритмів дозволило значно зменшити час
факторизації та об’єми необхідних обчислювальних ресурсів.
У дисертаційній роботі розроблено нові моделі паралелізації алгоритмів
факторизації надвеликих розріджених лінгвістичних матриць та тензорів:
локальна модель паралелізації з використанням жорсткого диску для зберігання
даних та паралельних обчислень на графічних процесорах GPU і розподілений
алгоритм з використанням мережі вузлів для розрахунків та виконанням
паралельних обчислень на графічних процесорах GPU, що дало змогу зменшити
необхідний час, обчислювальні ресурси та отримана можливість збагачення
систем обробки природньої мови новими даними без необхідності повторної
факторизації
В результаті проведеної роботи отримано такі наукові результати:
1. Для виконання обчислень на графічних процесорах з оптимальним
порядком виконанням операції, для зменшення часу читання та запису
даних в пам’ять графічних процесорів розроблено модель паралелізації
алгоритмів факторизації матриць та тензорів.
2. Оптимізовано використанням мережевих ресурсів для зменшення часу,
необхідного для передачі даних, розробивши модель розподіленого
алгоритму факторизації матриць та тензорів надвеликої розмірності.
126
3. Розроблено новий метод факторизації розріджених лінгвістичних
матриць та тензорів за допомогою приведення до блочно-діагонального
виду, що дозволяє зменшити об’єм даних для факторизації та надає
можливість збагачення системи новими даними.
4. Вперше розроблено алгоритм формування тематичних діагональних
блоків лінгвістичних матриць та тензорів з використанням моделі
латентного розподілу Діріхле, що дозволяє отримати необхідну кількість
діагональних блоків, а також можливість аналізу додаткових зв’язків між
блоками та термами.
5. Проведено тестування та порівняння швидкодії розроблених алгоритмів
та методів на надвеликій матриці зв’язності Слова-Статті та тензорі
Підмет-Присудок-Додаток. Експерименти показали, що реалізація
запропонованих алгоритмів підвищує швидкодію факторизації матриць
та тензорів, зменшує необхідні обчислювальні ресурси та об’єм
необхідних операцій читання-запису та мережевих операцій.