Розв'язання логічних задач на основі машинного навчання

У статті запропоновано спосіб розв’язання логічних задач‑головоломок на основі машинного навчання. Спосіб розраховано на попередню формалізацію задач у вигляді опису властивостей та відношень між ними. Оскільки кожна властивість має множину можливих значень, розв’язання задачі методами перебору має...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2020
Hauptverfasser:	Шаповалова, С.І., Бараніченко, О.М.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2020
Schriftenreihe:	Математичне та комп'ютерне моделювання. Серія: Технічні науки
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/181477
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Розв'язання логічних задач на основі машинного навчання / С.І. Шаповалова, О.М. Бараніченко // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 20. — С. 121-130. — Бібліогр.: 6 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-181477
record_format	dspace
spelling	irk-123456789-1814772021-11-18T01:26:44Z Розв'язання логічних задач на основі машинного навчання Шаповалова, С.І. Бараніченко, О.М. У статті запропоновано спосіб розв’язання логічних задач‑головоломок на основі машинного навчання. Спосіб розраховано на попередню формалізацію задач у вигляді опису властивостей та відношень між ними. Оскільки кожна властивість має множину можливих значень, розв’язання задачі методами перебору має комбінаторну складність. При великій кількості властивостей та їх значень час розв’язання стрімко зростає. The article proposes a method of solving logical puzzles on the basis of machine learning. The method is designed for the preliminary formalization of tasks in the form of description of properties and relations between them. Be-cause each property has a set of possible values, the solution of the puzzle by the methods of search has a combinatorial complexity. With a large number of properties and their values, the time of the solving is rapidly increasing. 2020 Article Розв'язання логічних задач на основі машинного навчання / С.І. Шаповалова, О.М. Бараніченко // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 20. — С. 121-130. — Бібліогр.: 6 назв. — укр. 2308-5916 DOI: https://doi.org/10.32626/2308-5916.2019-20.121-130 http://dspace.nbuv.gov.ua/handle/123456789/181477 004.032.26:004.832 uk Математичне та комп'ютерне моделювання. Серія: Технічні науки Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	У статті запропоновано спосіб розв’язання логічних задач‑головоломок на основі машинного навчання. Спосіб розраховано на попередню формалізацію задач у вигляді опису властивостей та відношень між ними. Оскільки кожна властивість має множину можливих значень, розв’язання задачі методами перебору має комбінаторну складність. При великій кількості властивостей та їх значень час розв’язання стрімко зростає.
format	Article
author	Шаповалова, С.І. Бараніченко, О.М.
spellingShingle	Шаповалова, С.І. Бараніченко, О.М. Розв'язання логічних задач на основі машинного навчання Математичне та комп'ютерне моделювання. Серія: Технічні науки
author_facet	Шаповалова, С.І. Бараніченко, О.М.
author_sort	Шаповалова, С.І.
title	Розв'язання логічних задач на основі машинного навчання
title_short	Розв'язання логічних задач на основі машинного навчання
title_full	Розв'язання логічних задач на основі машинного навчання
title_fullStr	Розв'язання логічних задач на основі машинного навчання
title_full_unstemmed	Розв'язання логічних задач на основі машинного навчання
title_sort	розв'язання логічних задач на основі машинного навчання
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2020
url	http://dspace.nbuv.gov.ua/handle/123456789/181477
citation_txt	Розв'язання логічних задач на основі машинного навчання / С.І. Шаповалова, О.М. Бараніченко // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 20. — С. 121-130. — Бібліогр.: 6 назв. — укр.
series	Математичне та комп'ютерне моделювання. Серія: Технічні науки
work_keys_str_mv	AT šapovalovasí rozvâzannâlogíčnihzadačnaosnovímašinnogonavčannâ AT baraníčenkoom rozvâzannâlogíčnihzadačnaosnovímašinnogonavčannâ
first_indexed	2025-07-15T22:42:25Z
last_indexed	2025-07-15T22:42:25Z
_version_	1837754586844102656
fulltext	Серія: Технічні науки. Випуск 20 121 УДК 004.032.26:004.832 DOI: 10.32626/2308-5916.2019-20.121-130 С. І. Шаповалова, канд. техн. наук, О. М. Бараніченко, аспірант Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», м. Київ РОЗВ’ЯЗАННЯ ЛОГІЧНИХ ЗАДАЧ НА ОСНОВІ МАШИННОГО НАВЧАННЯ У статті запропоновано спосіб розв’язання логічних за- дач-головоломок на основі машинного навчання. Спосіб розрахо- вано на попередню формалізацію задач у вигляді опису властиво- стей та відношень між ними. Оскільки кожна властивість має множину можливих значень, розв’язання задачі методами пере- бору має комбінаторну складність. При великій кількості власти- востей та їх значень час розв’язання стрімко зростає. В останні роки окремим напрямом досліджень з машинно- го навчання стало розв’язання логічних задач такого типу. Од- нак існуючі рішення цього напряму мають ряд недоліків, на- самперед вони не завжди гарантують коректне розв’язання. У роботі представлено спеціальну мережу зв’язків для на- вчання розв’язанню логічних задач, а також їх формалізацію для представлення цій мережі. Мережа містить обчислювальні вузли, які відображають відношення між властивостями, та ву- зли вхідних шарів, які задають значення цих відношень. Розв’язання кожної задачі відбувається шляхом автоматично- го створення мережі зв’язків з її подальшим навчанням до отри- мання розв’язку. Приведено геометричну інтерпретацію n-мірної мережі зв’язків та її (n – 1)-мірних шарів. Наведено формалізацію представлення навчальної вибірки та алгоритм навчання. Пред- ставлено механізм розв’язання логічних комбінаторних задач. Наведено приклади задач, які є традиційними тестами в системах логічного програмування та продукційних (експерт- них) системах, а також задач з ресурсу bAbI таких класів: two supporting facts, two arguments relations, positional reasoning. Експериментально доведено ефективність запропоновано- го способу. Визначено перспективи подальших досліджень, які по- в’язані зі створенням лексико-синтаксичного аналізатора для автоматичного представлення властивостей, їх значень та від- ношень між ними. Запропонований спосіб є універсальним і не залежить від характеристик поточної задачі, таких як кількості властивос- тей та їх значень. Ключові слова: логічні головоломки, машинне навчання. © С. І. Шаповалова, О. М. Бараніченко, 2019 Математичне та комп’ютерне моделювання 122 Вступ. В сучасних прикладних програмних системах часто виникає необхідність у розв’язанні логічних задач. Різновидом таких задач є за- дача підбору значень властивостей на основі опису об’єктів і зв’язків між ними. В таких задачах кожен об’єкт має набір властивостей. Кожна властивість має множину можливих значень. Задача полягає у визначен- ні такої комбінації значень властивостей всіх об’єктів, що не суперечать заданим умовам. Прикладами таких задач є створення розкладів, логіс- тика, розподіл ресурсів. Як правило, алгоритми розв’язання мають ком- бінаторну складність, завдяки перебору значень аргументів задач. Зі збі- льшенням кількості аргументів на порядки зростає час розв’язання. Зі стрімким розвитком нейронних мереж з’явилися дослідження з розв’язання цих задач на основі машинного навчання. Однак існуючі рішення цього напряму мають ряд недоліків, насамперед вони не завжди гарантують коректне розв’язання. Тому задача автоматичного розв’яза- ння логічних задач на основі машинного навчання є актуальною. Аналіз останніх досліджень. Розв’язання комбінаторних логіч- них задач відноситься до одного з історично перших напрямів штуч- ного інтелекту. Для їх розв’язання були створені спеціальні механіз- ми. Одним з найбільш відомих механізмів логічного висновування є Prolog. Для перевірки ефективності його реалізації використовуються тестові задачі (benchmarks), якими є саме логічні задачі зазначеного типу. Колекції таких задач представлено на ресурсах [1, 2]. Інший підхід представлено в роботі [3]. Автор запропонував пред- ставлення логічної задачі у вигляді набору булевих виразів. На їх основі будуються і заповнюються таблиці властивостей. Однак метод не дозволяє реалізовувати складні відношення значень властивостей логічної задачі. У роботі [4] задача представляється таблицею зв’язків між зна- ченнями властивостей. Автори запропонували універсальний алго- ритм розв’язання логічних задач на основі розрахунків сум існуючих значень таких зв’язків. Однак цей метод враховує лише наявність зв’язку між атрибутами і не дозволяє призначити додаткові умови. Сучасною тенденцією досліджень зі штучного інтелекту є спро- би розв’язання таких задач на основі машинного навчання. В роботі [5] було представлено систему Sherlock, яка вирішує логічні задачі на основі парадигми об’єднання індуктивного навчання і логічного про- грамування. Для спрощення логічного висновування як правило за- дача формалізується в представлення, пристосоване для комп’ю- терної обробки. В цій роботі задача представляється за допомогою запропонованої авторами мови з синтаксисом, схожим на Prolog. Од- ним з недоліків даної системи є залежність від умов задачі. В роботі [6] наведено результати розв’язання логічних задач проекту bAbI [1] за допомогою нейронних мереж. Однак для деяких різновидів задач відсоток коректних відповідей є досить низьким, зокрема для задач Counting, Lists/Sets, Positional Reasoning, Path Find. Серія: Технічні науки. Випуск 20 123 Тому необхідно розробити універсальний механізм автоматич- ного розв’язання логічних задач на основі машинного навчання. Мета і задачі. Метою роботи є створення обчислювальної стру- ктури, яка розв’язує логічні задачі на основі навчання за їх формалі- зованим описом. Для виконання даної мети необхідно було вирішити такі завдання: 1. Виконати формалізацію логічних комбінаторних задач. 2. Розробити спеціальну мережу для навчання розв’язанню логічних задач. 3. Розробити алгоритм навчання. 4. Провести обчислювальні експерименти на тестових задачах. Формалізація логічної задачі. Логічна задача складається з на- бору властивостей, кожна з яких має набір можливих значень. Нехай задача складається з n властивостей, кожна з яких має m значень. На- приклад, для задачі Ейнштейна: n = 6 (номер будинку, його колір, національність мешканця, його улюблені напій, цигарки та тварина), m = 5 для всіх властивостей (номери будинків — 1, 2, 3, 4, 5; кольори будинків — білий, жовтий, зелений, червоний, синій; національнос- ті — англієць, данець, німець, норвежець, швед; напої — вода, кава, молоко, пиво, чай; цигарки — Dunhill, Marlboro, Pall-Mall, Philip Morris, Rothmans; тварини — кішка, кінь, пташка, риба, собака). Таким чином, кожну властивість iP (property) можна представи- ти множиною її значень j iv (value):  ji iP v , де iP — і-та властивість, 1..i n , j iv — значення j властивості i, 1..i n , 1..j m . Для задачі Ейнштейна: 1P — номер будинку, 2P — колір будин- ку, … , 6P — тварина. Наприклад, 3P ={англієць, данець, німець, норвежець, швед}. Кожна k-та можлива комбінація значень властивостей Ck (combi- nation), матиме вид:  1 2 , ,..., n k k k kC x x x , (1) де k — номер поточної комбінації, k iv — можливе значення i-ї влас- тивості, k i iv P . Наприклад, 1C = (1, білий, англієць, вода, Dunhill, кішка), 2C = (1, білий, англієць, вода, Dunhill, кінь), та інші. Максимальна кількість комбінацій без урахування додаткових умов: Математичне та комп’ютерне моделювання 124 n q m , (2) де n — кількість властивостей задачі, m — кількість значень власти- востей задачі Рішенням задачі буде множина комбінацій, що не суперечать всім умовам задачі:  1 2, , , oS C C C , (3) де o — кількість коректних комбінацій значень властивостей, o q . Для вирішення задачі використовуються умови відношень між двома значеннями властивостей: 1 2 1 2 j j i i v rel v (4) де 1 1 j iv — значення 1j властивості 1i , 1 1..j m , 1 1..i n , 2 2 j iv — зна- чення 2j властивості 2i , 2 1..j m , 2 1..i n , rel — визначене відношення між властивостями з зазначеними значеннями. При формалізації задачі всі зв’язки предметної області зводяться до тверджень про наявність/відсутність відповідного зв’язку, що позначає- ться є / не є . Наприклад: 1 є білий, 2 не є зелений. Обчислювальна структура розв'язання логічних задач. Для розв’язання логічних задач було розроблено спеціальну структуру — мережу зв’язків. Мережа представляє собою n-мірну «решітку» вуз- лів. Розмірність мережі n дорівнює кількості властивостей задачі. Приклад мережі в початковому стані для 2-х властивостей, кожна з яких має по 3 значення, зображено на рисунку 1. Цей при- клад відображає частину задачі Ейнштейна для трьох будинків з номерами: 1, 2, 3, та можливими кольорами: синім, червоним, зе- леним. Вхідним шаром мережі зв’язків є вузли, які представляють со- бою значення властивостей задачі. На рисунку 1 властивість «номер будинку» зі значеннями 1, 2, 3 представляється вузлами 1 1v – 3 1v відпо- відно, а властивість «колір будинку» зі значеннями синій, червоний, зелений — вузлами 1 2v – 3 2v . Після визначення вхідних шарів необхідно побудувати внутріш- ню структуру мережі, яка містить обчислювальні вузли. Кожен обчислювальний вузол фактично представляє Ck комбі- націю значень всіх властивостей (2). Загальна кількість вузлів складає q (3). На кожному етапі обчислювальний вузол містить власне зна- чення Nv (Node value), отримане при ініціалізації, або внаслідок нав- чання. Вузол може приймати значення 1, тобто комбінація Ck можли- ва, або 0 — комбінація неможлива. Серія: Технічні науки. Випуск 20 125 Рис. 1. Приклад мережі зв’язків Приклад наведено для двомірної мережі зв’язків для наочності графічного представлення. Але принципи побудови можна розпо- всюдити на n-мірну мережу. В алгоритмі використовується поняття (n – 1)-мірного шару. Та- кий шар представляє деякий зріз з фіксованим значенням однієї влас- тивості. В наведеному прикладі (n – 1)-мірним шаром для фіксовано- го значення 2 1v буде набір вузлів зі значеннями Nv4, Nv5, Nv6, для 1 2v — зі значеннями Nv1, Nv4, Nv7. Виходячи з геометричних предста- влень (n – 1)-мірний шар мережі при: 1) n = 2, є рядком або стовбцем; 2) n = 3, є площиною; 3) n = 4, є паралелепіпедом. Запропонована мережа може мати будь-яку розмірність, однак для випадків n > 3 це важко інтерпретувати геометрично. Для отримання розв’язку задачі побудована мережа повинна пройти навчання. Навчання мережі зв’язків. Навчання полягає у встановленні значень Nv для всіх вузлів мережі. Критерієм закінчення навчання є відсутність змін значень Nv всіх вузлів по відношенню до поперед- Математичне та комп’ютерне моделювання 126 ньої епохи. Епохою вважається представлення мережі всіх навчаль- них прикладів з подальшим уточненням значень вузлів. Навчальним прикладом є відношення між значеннями двох властивостей (4). Представлення прикладу полягає в послідовному перерахунку значень всіх вузлів мережі. Перерахунок значення поточного вузла здійснюється за таким алгоритмом: 1. Визначення кількості збігів значень властивостей в поточній ком- бінації Ck з поточним прикладом. 2. Оновлення значення вузла: ' ( , )v vN N F S R  , де ' vN — нове значення вузла, vN — значення, встановлене після представлення попереднього прикладу, S — кількість збігів значень властивостей, R — відношення між значеннями властивостей, ( , )F S R — функція, яка залежить від кількості збігів значень власти- востей і визначається в таблиці 1. Таблиця 1 Значення функції оновлення Вхідні параметри Значення функції R S F є 0 1 є 1 0 є 2 1 не є 0 1 не є 1 1 не є 2 0 Після представлення всіх прикладів здійснюється уточнення значень мережі за таким алгоритмом: 1. Виокремлення всіх можливих (n – 1)-мірних шарів. 2. Обчислення суми встановлених значень всіх вузлів поточного s-го шару Sls (Sum of layer). 3. Оновлення значень за схемою: 3.1. Якщо сума Sl=1 — формується додаткова навчальна вибірка зі всіх відношень «є», які відображають поточний вузол: , 1.. , 1.. , ji k kx є x i n j n i j   , де k — номер поточного вузла, n — кількість властивостей задачі. Після цього здійснюється представлення всіх цих прикладів за вищеописаним алгоритмом. Серія: Технічні науки. Випуск 20 127 3.2. Якщо 1Sl  — здійснюється обробка наступного (s + 1)-го шару поточного вузла. 4. Перевірка закінчення алгоритму уточнення: 4.1. Якщо є необроблені шари поточного вузла, здійснюється об- робка наступного шару — повернення до пункту 2 поточного алгоритму. 4.2. Якщо всі шари поточного вузла оброблено, здійснюється пе- рехід до обробки наступного вузла — повернення до пункту 1. Навчання відбувається за схемою: 1. Ініціалізація вузлів мережі: в кожному вузлі встановлюється зна- чення 1. 2. Навчання за поточною епохою: представлення всіх навчальних прикладів з подальшим уточненням мережі за кожним з них. 3. Перевірка закінчення навчання: якщо умова закінчення навчання не виконується — перехід до наступної епохи. В іншому випад- ку — отримання розв’язку задачі у вигляді (5). Обчислювальні експерименти. Для апробації запропонованого алгоритму було використано представлення n-мірної мережі зв’язків у вигляді одновимірного масиву. Представлення n-мірності організо- вано за допомогою вирахування індексів. На рисунку 2 наведено фрагмент інтерфейсу програмної системи з формалізацією задачі Ейнштейна за властивостями та їх значеннями. Рис. 2. Формалізація задачі Ейнштейна Математичне та комп’ютерне моделювання 128 Навчальна вибірка для задачі Ейнштейна представлена на рисунку 3. Рис. 3. Навчальна вибірка для задачі Ейнштейна Розв’язок задачі представлено на рисунку 4. Рис. 4. Розв’язок задачі Ейнштейна У випадку, якщо задача має декілька розв’язків, система видає рішення як перелік коректних комбінацій значень параметрів Ck. Та- кий приклад з варіантами розв’язання задачі Ейнштейна при вида- ленні першої умови наведено на рисунку 5. Рис. 5. Можливі комбінації для задачі Ейнштейна з неповною навчальною вибіркою Серія: Технічні науки. Випуск 20 129 Розроблене програмне забезпечення реалізовано на платформі .Net Framework 4.6, мовою C#. Тестування та апробація системи від- бувалися під керуванням операційної системи Windows 10 x64. Для експериментів було обрано задачі, які є традиційними тес- тами в системах логічного програмування та продукційних системах: задача Ейнштейна, розміщення за столом. Крім того, було розв’язано задачі з ресурсу bAbI [1] таких класів: two supporting facts, two argu- ments relations, positional reasoning. В таблицю 2 зведено інформацію з тестових задач, а також хара- ктеристики їх розв’язання. Таблиця 2 Результати обчислювальних експериментів № Назва задачі Параметри задачі Час розв’я- зання, с Кіль- кість епох Кількість коректних комбіна- цій o Кількість власти- востей n Кількість значень m 1 Задача Ейнштейна 6 5 5.71 6 5 2 Розміщення за столом 3 4 1.12 3 4 3 Розміщення за столом 4 3 1.53 3 3 4 bAbI, two supporting facts 2 3 0.76 3 3 5 bAbI, two arguments relations 2 3 0.83 3 3 6 bAbI, positional reasoning 3 4 1.78 4 4 Таким чином, представлено механізм розв’язання логічних ком- бінаторних задач. Розв’язання кожної задачі відбувається шляхом автоматичного створення мережі зв’язків з її подальшим навчанням до отримання розв’язку. Висновки. 1. Розроблено формалізацію логічних комбінаторних задач як набо- ру властивостей та їх значень. 2. Розроблено представлення задачі у вигляді мережі зв’язків для навчання розв’язанню логічних задач. 3. Розроблено алгоритм навчання. 4. Експериментально доведено ефективність запропонованого способу. Перспективою подальших досліджень є створення системи з ле- ксико-синтаксичним аналізатором для автоматичного представлення властивостей, їх значень та відношень між ними. Список використаних джерел: 1. bAbI — Facebook research // Facebook research. — 2015. — Access mode: https://research.fb.com/downloads/babi/. Математичне та комп’ютерне моделювання 130 2. Einstein's riddle and grid puzzles. — 2012. — Access mode: http://brainden.com/einsteins-riddles.htm. 3. Filho W. Solving the Zebra Puzzle with Boolean Algebra / W. Filho. — 2017. — Access mode: https://code.energy/solving-zebra-puzzle/. 4. Application of «Einstein's riddle» in solving construction machine allocation prob- lems / B. Dasović, M. Čorak, M. Galić, U. Klanšek // E-gfos. — 2016. — P. 12–22. 5. Zhang Q. Sherlock — A Neural Network Software for Automated Problem Solv- ing. — 2011. — Access mode: http://www.macs.hw.ac.uk/~ek19/QK.pdf. 6. Tovards AI-complete question anwering: a set of prerequisite toy tasks / [J. Weston, A. Bordes, S. Chopra a.o.] // arXiv. — 2015. — Access mode: https://arxiv.org/pdf/1502.05698.pdf. LOGICAL PUZZLES SOLVING BASED ON MACHINE LEARNING The article proposes a method of solving logical puzzles on the basis of machine learning. The method is designed for the preliminary formalization of tasks in the form of description of properties and relations between them. Be- cause each property has a set of possible values, the solution of the puzzle by the methods of search has a combinatorial complexity. With a large number of properties and their values, the time of the solving is rapidly increasing. In recent years, a separate area of research in machine learning has been the solution to logical tasks of this type. However, existing solutions to this area have a number of shortcomings, first and foremost, they do not always guarantee a correct solution. The paper presents a special network of connections for learning the solution of logical puzzles, as well as their formalization for the representa- tion of this network. The network contains computing nodes that represent the relationship between properties, and the nodes of the input layers that specify the values of these relationships. Every task is solved by automatically creating a network of links with its further training until the solution is obtained. The geometric interpreta- tion of the n-dimensional network of bonds and its (n-1) -dimensional lay- ers is given. The formalization of the presentation of the study sample and the learning algorithm are presented. The mechanism of solving logical combinatorial problems is presented. The article presents examples of tasks that are traditional tests in sys- tems of logical programming and production (expert) systems, as well as tasks from the resource bAbI of such classes: two supporting facts, two ar- gument relations, positional reasoning. The efficiency of the proposed method has been experimentally proved. The prospects of further researches, which are connected with the crea- tion of a lexical-syntactic analyzer for automatic representation of proper- ties, their values and relations between them, are determined. The proposed method is universal and does not depend on the characteris- tics of the current task, such as the number of properties and their values. Key words: logical puzzles, machine learning. Отримано: 13.08.2019

Розв'язання логічних задач на основі машинного навчання

Institution

Ähnliche Einträge