113 Прикладна математика
Permanent URI for this collection
Освітньо-професійна програма / Освітньо-наукова програма: Прикладна математика
Browse
Recent Submissions
Item Дослідження взаємозв’язків у даних з використанням штучних нейронних мереж : дисертація на здобуття наукового ступеня доктора філософії(2024) Іванюк, Андрій; Крюкова, ГалинаДисертація на здобуття наукового ступеня доктора філософії у галузі знань 11 "Математика та статистика" за спеціальністю 113 "Прикладна математика". — Національний університет "Києво-Могилянська академія", Київ, 2024. Ця дисертація зосереджена на вивченні зв’язків у даних за допомогою застосування штучних нейронних мереж. Ці зв’язки можуть бути представлені в різних формах, і моделюватись по-різному. Їх правильне моделювання є ключовим для успішного вирішення різноманітних завдань, таких як класифікація, регресія та генеративне моделювання. У сучасних нейронних мережах широко використовуються стандартні метрики для оцінки їх продуктивності, наприклад, класифікаційна точність, середньоквадратична похибка тощо. Проте, високі показники цих метрик не гарантують відсутності помилок або вразливостей у моделях. Моделі можуть видавати помилкові результати з високим рівнем впевненості, особливо при взаємодії з адверсаріальними прикладами — спеціально створеними вхідними даними, які вводять модель в оману. Це дослідження стосується цієї важливої проблеми шляхом детального вивчення кількісної оцінки невизначеності та стійкості нейронних мереж до адверсаріальних атак. Використовуючи адверсаріальні дані як інструмент, ця робота спрямована на поглиблення розуміння надійності моделей та розрореальних застосуваннях. Досліджуючи адверсаріальні взаємозв’язки та патерни в даних, ця робота має на меті використовувати їх як метрику генералізації для виявлення слабких місць моделей та оцінки їх здатності до узагальнення. Розуміння того, як моделі реагують на суперечливі збурення, відкриває унікальний погляд на їх внутрішню структуру та механізми прийняття рішень. Це дозволяє не лише виявляти вразливі місця, але й розробляти методи для їх усунення, що підвищує загальну надійність та ефективність моделей. У рамках цього дослідження вивчаються різні параметризації нейронних мереж для моделювання послідовностей та їх вплив на продуктивність моделей і стійкість до адверсаріальних атак. Особлива увага приділяється новим архітектурам та активаційним функціям, які можуть покращити здатність моделей до генералізації та їхню стійкість. Адверсаріальна стійкість розглядається як важлива метрика для виявлення слабких місць моделей та оцінки їх загальної ефективності. Дослідження охоплює ефективні параметризації для різних типів вхідних даних, включаючи зображення, мовні сигнали та текст. Застосовуються ці параметризації до різних завдань машинного навчання, таких як класифікація зображень, моделювання мови та регресія на основі латентних дифузійних моделей. Проведені експерименти спрямовані на виявлення того, як різні стратегії параметризації можуть покращити продуктивність моделей, зберігаючи або навіть підвищуючи їх стійкість до адверсаріальних атак. Отримані результати надають важливі знання для розробки більш надійних та здатних до генералізації моделей машинного навчання. Це сприяє прогресу у цій галузі шляхом виявлення оптимальних технік параметризації, які збалансовують продуктивність та стійкість, та можуть бути застосовані у широкому спектрі практичних задач. Дисертація складається з кількох розділів, кожен з яких охоплює ключові аспекти дослідження. Розроблення більш стійких систем на основі нейронних мереж, які можуть протистояти різноманітним атакам та забезпечувати стабільну продуктивність у Перший розділ, "Геометричні властивості адверсаріальних прикладів", надає глибоке визначення адверсаріальним атакам, класифікує їх за різними типами та досліджує їх геометричні властивості. Тут розглядаються різні методи створення адверсаріальних прикладів, такі як атаки за градієнтами, методи з обмеженням норми збурення та інші. Аналізуються механізми, за допомогою яких адверсаріальні атаки експлуатують вразливості моделей, та як ці вразливості пов’язані з геометрією простору ознак. Наступний розділ, "Моделювання сигналів за допомогою механізму уваги з ковзним середнім”, зосереджується на оцінці модифікованої функції уваги для ефективного моделювання послідовностей. Механізм уваги з ковзним середнім пропонується як альтернатива традиційним методам, таким як рекурентні нейронні мережі та стандартні механізми уваги. Розділ детально описує методологію, математичний апарат та алгоритмічну реалізацію запропонованого підходу. Проводиться оцінка його ефективності у завданнях моделювання мовленнєвих сигналів. Крім того, дисертація містить розділ "Аналіз дифузійного моделювання на прикладі аудіо сигналів", у якому досліджується використання латентних дифузійних моделей для синтезу аудіо. Розглянуто методи компресії ознак за допомогою маскованих та варіаційних автокодувальників, а також адаптацію компонентів попередньо навченої моделі AudioLDM2 для покращення генерації мовлення. Проведено оцінювання запропонованої моделі за метриками схожості голосу, точності класифікації емоцій та похибок розпізнавання мовлення, що дозволило виявити її переваги та напрямки для подальшого вдосконалення. Далі йде розділ "Багатовимірні активаційні функції", який досліджує нові види активаційних функцій, що моделюють взаємозв’язки між багатьма нейронами одночасно. Традиційні активаційні функції зазвичай діють на рівні окремого нейрона, але запропоновані багатовимірні функції дозволяють моделювати складніші залежності та взаємодії у нейронній мережі. Розглянуто декілька видів таких функцій, їх математичні властивості та вплив на навчання моделі. Емпіричні результати демонструють покращення продуктивності у різних завданнях машинного навчання, включаючи класифікацію, регресію та генеративні моделі. Розділ "Адверсаріальна стійкість" надає результати експериментів, що оцінюють стійкість розглянутих параметризацій до різних типів адверсаріальних атак. Тут проводиться порівняльний аналіз моделей з різними параметризаціями щодо їх здатності протистояти атакам, таким як PGD (Projected Gradient Descent) та інші. Надано уявлення про те, як різні стратегії параметризації та архітектурні рішення впливають на стійкість моделей до адверсаріальних атак, а також розглянуто методи для покращення цієї стійкості, такі як регуляризація, згладжування міток (англ. label smoothing) та змагальне навчання (англ. adversarial training). У розділ "Висновки" представлені загальні результати дисертації, підсумовано ключові висновки та їх вплив на сферу машинного навчання. Обговорено значення отриманих результатів для практичного застосування, а також запропоновано потенційні напрямки для майбутніх досліджень. Зокрема, обговорюється можливість подальшого розвитку багатовимірних активаційних функцій, дослідження нових механізмів уваги та глибше вивчення геометричних аспектів адверсаріальної стійкості. Проведені дослідження підтверджують ефективність використання розглянутих нейронних мережевих моделей для підвищення точності класифікації та демонструють складності, які виникають при адверсаріальному тренуванні. Загалом, ця дисертація робить вагомий внесок у розуміння та покращення стійкості нейронних мереж до адверсаріальних атак, пропонуючи нові підходи до параметризації та моделювання, які можуть бути застосовані у різних сферах машинного навчання. Результати цього дослідження можуть стати основою для розробки більш надійних та ефективних моделей, здатних забезпечувати високу продуктивність та безпеку у реальних застосуваннях. Проведені експерименти підтверджують, що використання розглянутих параметризацій може підвищити точність класифікації, але також виявляють складності, пов’язані з їх адверсаріальним тренуванням. Подальші дослідження у цьому напрямку можуть призвести до створення моделей, які не лише демонструють високу продуктивність, але й є стійкими до різноманітних атак, що є критично важливим у сучасному світі, де безпека та надійність моделей машинного навчання набувають все більшого значення.Item Алгоритми і коди над силовськими 2-підгрупами симетричних груп S2n : дисертація на здобуття наукового ступеня доктора філософії(2023) Ольшевська, Віта; Олійник, БогданаДисертація на здобуття наукового ступеня доктора філософії в галузі знань 11 "Математика та статистика" за спеціальністю 113 "Прикладна математика" — Національний університет "Києво-Могилянська академія", Київ, 2023. Дисертаційна робота присвячена побудові і аналізу алгоритмів над силовськими 2-підгрупами симетричних груп та дослідженню властивостей кодів на цих групах. Силовські p-підгрупи є класичними об’єктами в теорії груп, опис таких підгруп допомагає зрозуміти структуру самої групи. Зокрема, словські р-підгрупи симетричної групи досліджувалися професором Л. Калужніним та описані в його працях за допомогою вінцевих добутків циклічних груп. Він запропонував зображати елементи таких груп у вигляді спеціальних таблиць, а саме - впорядкованих наборів многочленів певного вигляду. Ю. Дмитрук у своїй праці описав алгебраїчні структури силовських 2-підгруп симетричних груп. Основою для створення означення та отриманих головних результатів послугували саме статті Л. Калужніна. Елементи силовських підгруп симетричних груп можна розглядати як портери автоморфізмів кореневих дерев, які наведені в роботі В. Некрашевича. Мінімальна система твірних та графи Келлі на силовських р-підгрупах симетричних груп S2n описані А. Слупік та В. Сущанським. Нехай маємо ціле та додатнє число п > 1. Силовську 2-підгрупу симетричної групи S2n позначимо S2n as Syl2(S2n). Група Syl2(S2n) ізоморфна кінцевому добутуку р-циклічних груп, що мають порядок 2, а саме: Sylr2 (S2n ) = Z 2 I . . . I Z2 n разів. Б. Павлик використав поліноміальне представлення елементів групи Syl2(S2n). Він описав дії над Syl2(S2n) на множині мінімальних систем твірних цієї групи. Нижній центральний ряд силовських підгруп симетричних груп Sn було досліджено А. Віером. Оскільки такі структури досить зручні та ефективні в обчисленнях, природним продовженням є дослідження алгоритмічних властивостей та створення алгоритмів для обрахунків у силовських 2-підгрупах симетричних груп, елементи яких представлені саме деревами. Враховуючи характеристику порядку групи, особливої уваги заслуговує випадок, коли р = 2. У дисертаційній роботі дослідження ґрунтується на властивостях бінарних кореневих p-рівневих дерев з мітками. У тому числі розглянуті алгоритми основних групових операцій для таких структур, алгоритми зв’язку між деревами та підстановками з силовських 2-підгруп симетричних груп. Окрім того, для кожного алгоритму доведено коректність та досліджено часову складність. Використовуючи зв’язок підстановок з бінарними кореневими деревами з мітками, в дисертаційній роботі побудовано алгоритм пошуку кількості рухомих точок підстановок та відстані Хеммінга між елементами групи Syl2(S2n). Логічним продовженням роботи стало дослідження кодів над підстановками із силовських 2-підгруп симетричних груп. Починаючи із 1970-х років коди, побудовані на підстановках, та їх властивості широко досліджуються у різних сферах. Так І. Блейк у своїй роботі коротко розглянув та узагальнив відомі того часу результати про перестановочні масиви. Метою статті Дж. Денеса було показати, як використовувати перестановочне кодування для голосових операцій та паралельних обчислень. П. Камероном було отримано низку результатів про групи перестановок і перестановочні коди та зроблено огляд про відомі результати. Описано декілька відкритих проблем. Під кодом на групі підстановок розуміють множину елементів із групи Sn, де довільна пара із множини має відстань не меншу від заданої. При цьому можуть використовувати як різні підгрупи симетричної групи, так і різні метрики, наприклад, Хеммінга, Улама, Левенштейна тощо. Перестановочні коди використовуються як коди корекції помилок в каналах комунікацій з малою пропускною здатністю. Одним з напрямків є дослідження кодів на алгебраїчних структурах. Р. Бейлі у своїй роботі наводить ефективні алгоритми декодування, коли перестановочні коди є підмножинами з Sn. У дисертації розглядаються властивості кодів, які визначені на підстановках із силовської 2-підгрупи Syl2(S2n). симетричної групи Syl2 з відстанню Хеммінга dH над ними. Для їх дослідження також використано зв’язок групи Syl2(S2n) із групою бінарних кореневих n-рівневих дерев з мітками. Досліджено метричні властивості кодів на підстановках. Також описано властивості відстані Хеммінга на підстановках із силовської 2-підгрупи Syl2(S2n) симетричної групи S2n та побудовано алгоритм пошуку відстані Хеммінга для підстановок групи, що має складність 0 (2 n). Окрім того, досліджено метричні властивості кодів на підстановках із Syl2(S2n) та знайдено розміри і кількість кодів для максимальної та мінімальної ненульової відстані Хеммінга. Таким чином, у дисертаційній роботі містяться наступні нові наукові результати: 1. Запропоновано алгоритми перетворення підстановки із силовської 2-підгрупи симетричної групи у кореневе бінарне n-рівневе дерево з мітками та обернений перехід від дерева з LT2,n до підстановки із Syl2(S2n). Доведено їхню коректність і обчислено часову складність. 2. Запропоновано алгоритм множення підстановок силовської 2-підгрупи симетричної групи, що використовує зображення груп бінарними деревами з мітками, та обчислено його часову складність. Описано алгоритм знаходження оберненого елемента. Доведено його коректність та обчислено часову складність. 3. Описано алгоритм пошуку кількості рухомих точок підстановок силовських 2-підгруп симетричних груп з часовою складністю 0 (2n). Пораховано, що в середньому алгоритм виконує т кроків для групи Syl2(S2n). 4. Запропоновано формулу, за якою можна визначити кількість підстановок із Syl2(S2n), що мають задану, зокрема максимальну, кількість рухомих точок. 5. Наведено алгоритм пошуку відстані Хеммінга для підстановок із силовських 2-підгруп симетричних груп з часовою складністю O(2n). Оцінено, що в середньому алгоритм виконує n кроків для групи Syl2(S2n). 6. Запропоновано рекурсивну формулу для обчислення кількості підстановочних кодів CH over Syl2(S2n) з максимальною відстанню Хеммінга та обчислено кількість таких кодів. Практичне значення отриманих результатів. Результати дисертації мають теоретичний характер. Вони можуть використовуватися в теорії кодування, теорії груп підстановок. Дисертація може бути використана для читання спеціалізованих курсів з теорії алгоритмів та теорії кодування для студентів математичних спеціальностей.Item Марковська Ідеальна Рівновага у грі видобутку ресурсів зі степеневими перевагами агентів : дисертація на здобуття наукового ступеня доктора філософії за спеціальністю "Прикладна математика"(2023-07) Силенко, Ілля; Чорней, РусланДисертаційна робота присвячена дослідженню виду стохастичної гри з ненульовою сумою, що є відомою в науковій літературі з теорії ігор як гра видобутку ресурсів або гра накопичення капіталу. Теоретичною особливістю цієї гри є незліченний простір станів та незліченні простори рішень її учасників. Маючи практичне значення, концепція гри моделює економічну задачу зі стратегічної взаємодії, що інтерпретується таким чином. Кілька агентів мають у спільній власності деякий відновлюваний актив (капітал, ресурс), що здатен генерувати певну вигоду від його використання. Протягом послідовності з дискретних моментів часу всі гравці одночасно приймають рішення щодо власної поточної кількості до споживання з цього ресурсу, згідно з якою визначається їхній миттєвий прибуток через особисту сталу функцію корисності. Кількість доступного для використання ресурсу в кожен момент часу з'ясовується відповідно до відомого стохастичного закону переходу, що залежить від попередньої кількості ресурсу та обсягів видобутку з нього. Загальний виграш кожного учасника гри обчислюється як дисконтована сума всіх його миттєвих прибутків, очікувану величину якої кожен гравець прагне максимізувати обираючи власну стратегію на початку гри. Основною метою дослідження є доповнити попередні результати з існування в цій грі (Стаціонарної) Марковської Ідеальної Рівноваги, яка вважається концепцією розв'язку в подібних некооперативних іграх. Проблематика її існування є відкритою проблемою в загальній постановці задачі гри видобутку ресурсів, проте становить науковий та практичний інтерес, і тому широко вивчається. У дисертації розглядається модель гри видобутку ресурсів з недослідженого досі класу, для якого характерна довільна кількість учасників, необмежений простір станів та необмежені функції корисності гравців, а також закон переходу між станами у вигляді стохастичного ядра, залежного від спільної інвестиції агентів. Запропонована модель будується набором особливих припущень стосовно переваг гравців та стохастичного закону переходу між станами, які мають широке застосування в економічному моделюванні. По-перше, припускається, що всі гравці володіють ізоеластичними функціями корисності (або CRRA згідно з економічною термінологією) у вигляді степеневих та строго опуклих вгору. По-друге, кожна наступна кількість доступного ресурсу (або стан гри) є лінійним перетворенням залишку від споживання агентів (тобто їхньої спільної інвестиції) з мультиплікативним випадковим збуренням, однаково розподіленим на кожному етапі гри. В економічному моделюванні та фінансовій літературі такий стохастичний процес є поширеним під назвою геометричне випадкове блукання. Запропоновану модель розглянуто як у симетричному, так і несиметричному форматі гри. У симетричній моделі методом зворотної індукції побудовано єдину Марковську Ідеальну Рівновагу в ситуації коли горизонт гри є скінченним. Завдяки монотонній збіжності положень рівноваг та відповідних їм цінових функцій агентів при спрямуванні значення горизонту до нескінченності, встановлено існування симетричної Стаціонарної Марковської Ідеальної Рівноваги в чистих стратегіях для гри з необмеженим горизонтом. Доведено, що отримане положення рівноваги не є оптимальним за Парето, та знайдено формулу для визначення соціально-оптимального профілю стратегій. Також підтверджено надмірне споживання ресурсу гравцями, що перебувають у ситуації рівноваги, порівняно з їхньою соціально-оптимальною поведінкою. Згідно з цим результатом, симетричній моделі гри властива "трагедія спільного поля". Для несиметричної моделі гри з нескінченним горизонтом іншим способом доведено існування Стаціонарної Марковської Ідеальної Рівноваги в чистих стратегіях, й додатково висвітлено її єдиність серед профілів лінійних стратегій. Причому метод доведення, будучи відмінним від випадку симетричності в моделі, так само забезпечує алгоритм побудови положення рівноваги, що особливо доречно для використання результатів на практиці. Симетричну модель гри з нескінченним горизонтом додатково розглянуто в контексті існування чітко виражених соціальних зв'язків між агентами. А саме, передбачено кооперування гравців у межах окремих коаліцій, що не перетинаються та є сталими протягом усієї тривалості гри. Доведено, що для будь-якого розбиття множини гравців на коаліції, між ними існує міжкоаліційна рівновага, тобто положення, від якого жодна коаліція не здатна відхилитися узгодженими діями її учасників у односторонньому порядку так, щоб збільшити сумарний очікуваний дисконтований виграш всієї коаліції. Продовжуючи заглиблення в проблематику трагедії спільного поля у симетричній моделі, встановлено, що для сталої кількості гравців, величина їхнього спільного споживання ресурсу є тим більшою, чим більшою є кількість утворених конкуруючих за ресурс коаліцій, що перебувають у міжкоаліційній рівновазі. Окрім цього, розглядаючи гру видобутку ресурсів з долученою до неї коаліційною складовою, проведено аналіз економічної вигоди для її учасників від утворення певних коаліцій порівняно з іншими. Структура дисертації є такою. У розділі 1 проведено огляд релевантної наукової літератури, що охоплює поточний стан досліджень з тематики та ознайомлення з ключовими модельними припущеннями, що застосовувалися в стохастичних іграх видобутку ресурсів до моменту написання дисертаційної роботи. У розділі 2 представлено основні припущення досліджуваної моделі стосовно функцій корисності гравців та закону переходу між станами, а також обґрунтовано значущість їхнього використання. Результати, отримані для симетричного формату окресленої моделі гри видобутку ресурсів, висвітлено у розділі 3. Концепцію фіксованої коаліційної структури у симетричній моделі гри втілено й досліджено в розділі 4. Насамкінець у розділі 5 охоплено несиметричний випадок запропонованої моделі гри видобутку ресурсів.Item Метрична розмірність метричних та ультраметричних просторів з умовами скінченності : дисертація на здобуття наукового ступеня доктора філософії(2021) Пономарчук, Богдан; Олійник, БогданаУ дисертаційній роботі розглянуто задачу пошуку метричної розмірності для скінченних ультраметричних просторів, а також описано метричну розмірність для деяких конструкцій метричних просторів з умовами скінченності. Визначення метричної розмірності метричного простору було запропоноване Блюменталем в 1953 році. 20 років потому Харарі та Мелтер у своїй роботі застосували це визначення до метричних просторів визначених графами. Після чого, концепт метричної розмірності знайшов широке коло застосувань: комбінаторний аналіз, робототехніка, біологія, хімія та інші. У 2013 році С. Бау та Ф. Беардон продовжили ідеї Блюменталя щодо дослідження метричної розмірності метричних просторів. Вони вивчали метричну розмірність підпросторів Евклідового простору. Пізніше, М. Хейдарпур та С. Магсауді підрахували метричну розмірність геометричних просторів. Відомо що, пошук метричної розмірності метричного простору є NP-складною задачею. Є декілька шляхів дослідження метричної розмірності. Один з них — дослідження метричної розмірності для певних родин метричних просторів чи графів. Другим підходом є дослідження метричної розмірності конструкцій метричних просторів, що побудовані на основі метричних просторів, метрична розмірність яких вже відома. У дисертаційній роботі дослідження здійснюються в обох описаних вище напрямках. А саме повністю охарактеризовано метричну розмірність скінченних ультраметричних або неархімедових просторів. Показано, що для довільного скінченного ультраметричного простору його метрична розмірність може бути знайдена за поліноміальний час. Наведено поліноміальний алгоритм знаходження метричної розмірності для довільного ультраметричного простору. Для побудови цього алгоритму було використано ізометричне зображення ультраметричних просторів деревами. Показано, що складність побудови такого зображення дорівнює O(n5), де n — кількіств точок ультраметричного простору. Також доведено, що метрична розмірність ультраметричного простору, який визначається на кореневому дереві, або дорівнює метричній розмірності цього дерева як графа, або на одиницю менше. В роботі також повністю описано ультраметричні простори метрична розмірність яких дорівнює одиниці. Окрім ультраметричних просторів в дисертаційній роботі розглянуто метричну розмірність різних конструкцій метричних просторів. Зокрема показано, що для довільної шкали трансформації метрична розмірність метричного простору дорівнює метричній розмірності його трансформації. Наведено формулу для підрахунку метричної розмірності вінцевого добутку скінченного метричного простору і рівномірно дискретного метричного простору. У випадку коли метрична розмірність рівномірно дискретно метричного простору дорівнює нескінченності, метрична розмірність конструкції також дорівнює нескінченності. Крім того, для прямої суми метричних просторів скінченого діаметра показано, що її метрична розмірність дорівнюватиме сумі метричних розмірностей цих просторів. Показано, що для довільних метричних просторів скінченного діаметра метрична розмірність їх прямої суми дорівнює двом тоді і тільки тоді коли метрична розмірність кожного з просторів дорівнює 1. В останньому розділі також розглянуто метричну розмірність прямого добутку еквідистантних метричних просторів з метриками di, та dTO. Показано, що хоча ці метрики є топологічно еквівалентними, відповідні метричні простори мають різну метричну розмірність. Таким чином, в дисертаційній роботі містяться наступні нові наукові результати: 1. Наведено алгоритм зображення ультраметричного простору кореневим деревом, часова складність якого O(n5). 2. Для довільного скінченного ультраметричного простору показано, що існує поліноміальний алгоритм обчислення його метричної розмірності. 3. Охарактеризовано всі ультраметричні простори розмірність яких дорівнює одиниці. 4. Отримано формулу для обчислення метричної розмірності вінцевого добутку скінченного метричного та рівномірно дискретного метричного просторів. 5. Охарактеризовано метричну розмірність прямої суми метричних просторів скінченного діаметра. 6. Описано метричну розмірність прямого добутку еквідистантних метричних просторів з метриками di, d2 та dTO. Практичне значення отриманих результатів. Результати дисертації мають теоретичний характер. Вони можуть використовуватися в теорії графів, робототехніці, теорії метричних просторів. Дисертація може бути використана для читання спецкурсів з теорії графів для студентів математичних спеціальностей.