НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ | МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

МІЖНАРОДНИЙ НАУКОВО-НАВЧАЛЬНИЙ ЦЕНТР ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ТА СИСТЕМ

РАЧКОВСЬКИЙ Дмитро Андрійович

УДК 004.8 + 004.032.26

МЕТОДИ НЕЙРОМЕРЕЖЕВОГО РОЗПОДІЛЕНОГО ПРЕДСТАВЛЕННЯ ІНФОРМАЦІЇ ДЛЯ ВИРІШЕННЯ ЗАДАЧ ШТУЧНОГО ІНТЕЛЕКТУ НА ОСНОВІ ПРЕЦЕДЕНТІВ І АНАЛОГІЙ

05.13.23 – системи та засоби штучного інтелекту

Автореферат

дисертації на здобуття наукового ступеня

доктора технічних наук

Київ – 2007

Дисертацією є рукопис.

Робота виконана у Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН і МОН України.

Науковий консультант: доктор технічних наук
Куссуль Ернст Михайлович,
Міжнародний науково-навчальний центр
інформаційних технологій та систем
НАН і МОН України,
завідувач відділу.

Офіційні опоненти: доктор технічних наук, професор
Вінцюк Тарас Климович,
Міжнародний науково-навчальний центр інформаційних технологій та систем
НАН і МОН України,
завідувач відділу;

доктор технічних наук, професор
Замаруєва Ірина Вікторівна,
Військовий інститут Київського національного університету ім. Тараса Шевченка,
професор;

доктор технічних наук,
Різник Олександр Михайлович,
Інститут проблем математичних машин і систем
НАН України,
завідувач відділу.

Захист відбудеться « 31 » січня 2008 року о 14 годині на засіданні спеціалізованої вченої ради Д .171.01 в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН і МОН України за адресою: 03680, Київ, проспект акад. Глушкова, 40.

З дисертацією можна ознайомитися в бібліотеці Міжнародного науково-навчального центру інформаційних технологій та систем НАН і МОН України: 03680, Київ, проспект акад. Глушкова, 40.

Автореферат розісланий « 21 » грудня 2007 року.

Вчений секретар

спеціалізованої вченої ради Верещагін І.І.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Зростання обсягів, складності і різноманітності інформації, що доступна в електронній формі, вимагає підвищення ефективності та інтелектуалізації її обробки. Дослідження в цьому напрямку ведуться в області штучного інтелекту і тісно пов'язані з моделюванням інтелектуальної діяльності людини і механізмів структурно-функціональної організації мозку (М.М. Амосов, В.М. Глушков, О.Г. Івахненко, M.Minsky, F. Rosenblatt та ін.).

Продуктивним підходом, який використовується людьми при вирішенні складних задач в умовах неповноти, неточності, суперечності вхідної інформації є міркування на основі прикладів розв’язання схожих задач. Моделювання міркувань на основі прикладів і їхні різновиди – міркування за прецедентами і аналогіями – широко застосовується в системах штучного інтелекту для вирішення задач пошуку, класифікації, прогнозування, планування, моніторингу, діагностики, керування (J.G. Carbonell, K. Forbus, D. Gentner, J. Kolodner, C.K. Riesbeck, R.C. Shank, В.П. Гладун, Н.Г. Загоруйко, Д.О. Поспєлов, А.І. Уємов та ін.). У базі прикладів запам'ятовують прецеденти і аналоги, тобто описи задач разом з їхніми рішеннями, ситуації з прогнозами їхнього розвитку тощо. Для нової вхідної ситуації система знаходить в базі одну або декілька схожих ситуацій та приймає рішення, робить прогнози і висновки про вхідну ситуацію, адаптуючи до неї знання про наявні приклади.

Ефективність застосування міркувань на основі прецедентів і аналогій істотно залежить від форми представлення інформації. Застосування векторних і символьних представлень виявило ряд проблем, пов'язаних з пошуком схожих прикладів: вибір адекватних ознак для визначення схожості, необхідність врахування істотної інформації про структуру прикладів, складність визначення схожості структурованих представлень і врахування семантичної близькості об'єктів і відношень. Складність пошуку збільшується при зростанні об'ємів баз прикладів і складності опису прикладів. Проте саме етап пошуку схожих індивідуальних або узагальнених прикладів є центральним в багатьох прикладних системах, що пов’язані з класифікацією даних або пошуком релевантної інформації в базах знань, колекціях текстових документів, Інтернет тощо.

Моделювання представлення інформації в мозку є основою нейромережевого підходу (П.І. Бідюк, Є.В. Бодянський, О.І. Галушкін, В.Л. Дунін-Барковський, О.М. Касаткін, Л.М. Касаткіна, Б.В. Крижанівський, Н.М. Куссуль, Е.М. Куссуль, О.Л. Мікаелян, Д.В. Прохоров, В.Г. Редько, О.М. Різник, І.О. Рибак, О.О. Фролов, Ю.В. Чернухин, S. Amari, J. Hopfield, S. Grossberg, T. Kohonen, B. Widrow, D. Willshaw та ін.). Нейромережевий підхід призвів до ідеї розподіленого представлення інформації, що є формою векторного представлення, де кожен об'єкт (ознака, фізичний об'єкт, їх сукупність, відношення, сцена тощо) представлений сукупністю елементів вектора, а окремий елемент вектора може належати представленням різних об'єктів (D. Hebb, G. Hinton, P. Kanerva, J. McClelland, G. Palm, T. Plate, J. Pollack, D. Rumelhart, P. Smolensky, D. Touretzky та ін.). Розподілені представлення забезпечують високу інформаційну ємність, обчислювально ефективну оцінку схожості об'єктів скалярним добутком векторів, дозволяють використовувати відомі методи обробки векторної інформації.

Для подолання ряду недоліків розподілених представлень, пов'язаних з відсутністю єдиного формату, складністю реалізації та ін., Е.М. Куссулем запропонована парадигма асоціативно-проекційних нейронних мереж, що заснована на розподіленому представленні інформації у вигляді кодвекторів – розріджених (з малою часткою ненульових елементів) векторів з бінарними елементами (0 або 1). Проте теоретична база такого бінарного розрідженого розподіленого представлення інформації потребує розвитку для реалізації міркувань за прецедентами і аналогіями, а також для підвищення ефективності вирішення та розширення спектру прикладних задач. Необхідно розробити методи формування кодвекторів інформації різного типу – як реляційної структурованої (орієнтованих ациклічних графів з вершинами – об'єктами і відношеннями різного рівня ієрархії), так і неструктурованої (векторів числових ознак). Необхідно також розробити методи аналізу, оцінки й вибору параметрів і характеристик кодвекторів, провести аналітичні та експериментальні дослідження, удосконалити методи обробки на основі обчислення схожості кодвекторів.

Таким чином, в умовах зросту обсягів, складності та різноманітності оброблюваної інформації існує практична потреба в розширенні області застосування та підвищенні ефективності систем штучного інтелекту на основі реалізації міркувань за прецедентами і аналогіями саме за допомогою розподілених представлень. Водночас рівень розвитку теоретичної бази розподіленого представлення інформації є недостатнім для створення систем, ядром яких є розподілене представлення та обробка прецедентів і аналогій. Це зумовлює актуальність наукової проблеми розвитку теоретичних засад розподіленого представлення інформації в системах штучного інтелекту, що застосовують моделі міркувань людини за прецедентами та аналогіями. Практичні аспекти роботи вимагають також створення програмно-апаратних інструментальних засобів і прикладних систем, що реалізують і застосовують розроблені методи.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалася в рамках НДР: "Розробити принципи і методи рішення задач штучного інтелекту з використанням нейрокомп'ютерів", № державної реєстрації (ДР) 01.9.10013637 (1991-1993); "Розробка принципів і методів представлення знань на різних ієрархічних рівнях нейроподібних мереж", № ДР 0194U009547 (1994-1997); "Створення нейромережевих технологій обробки інформації і перевірка їх на прикладі вирішення задач підтримки прийняття рішень, розпізнавання образів й адаптивного керування", № ДР 0198U001768 (1998-2000); "Розробка і дослідження нейромережевих методів моделювання когнітивних процесів", № ДР 0101U002685 (2001-2003); "Дослідження та розроблення нових інтелектуальних інформаційних технологій на основі використання високоефективних нейромережевих методів та алгоритмів", № ДР 0102U002070 (2002-2006, науковий керівник); "Розробка і дослідження нейромережевих інформаційних технологій роботи з базами знань", № ДР 0104U003191 (2004-2006); "Дослідження можливостей створення, розробка і макетування обчислювальних засобів з нейроподібною архітектурою для існуючих і перспективних літальних апаратів" ("Лунодром-МАП", 1991, г/д); "Макетування вузлів технічних засобів систем штучного інтелекту (нейрокомп'ютера)" ("Анонс", 1990-1993, г/д); "Розробка теоретичних основ створення автоматизованих систем, що самонавчаються, для обробки інформації про стан об'єктів і прогнозування їхньої поведінки" ("Кипр-УН", 1991-1992, г/д); "Нейрокомп'ютер" (1992-1994); проект "High Performance Classification Based on Neural Networks with Fast Training" (INTAS-93-0560); проекти International Science Foundation "Knowledge Representation by Neural Network Structures" U4M000 (1994), U4M200 (1995); "Розробка автоматизованої системи збору та аналізу розсіяної інформації" ("Фрагмент", 1995-1996, в/ч 61330); "Створити дослідні зразки нейрокомп'ютерів нових поколінь", № ДР 0101U006718 (2000-2001, науковий керівник); "Розробити методи і створити засоби інтелектуалізації інформаційних технологій широкого використання", № ДР 0101U007953 (2001, науковий керівник); "Створити засоби автоматичної обробки інформації зі застосуванням міркувань за аналогіями", № ДР 0103U008280 (2003-2006, науковий керівник), ДНТП "Образний комп'ютер": "Розробка технології для створення систем смислової інтерпретації текстової інформації та смислового перекладу текстів з однієї мови на іншу", № ДР 0102U005512 (2002, науковий керівник розділу "Технологія, методи, алгоритми визначення міри семантичного зв'язку слів"); "Розробити комп'ютерну технологію цілеспрямованої обробки текстової й аудіо інформації" № ДР 0103U005770 (2003); "Розробити інтелектуальні інформаційні технології розпізнавання й ідентифікації аудіо-відео-інформації на основі нейромережевих технологій", № ДР 0104U008324 (2004).

Мета і завдання дослідження. Мета роботи – підвищення ефективності вирішення прикладних задач класифікації і пошуку релевантної інформації системами штучного інтелекту за рахунок розвитку і реалізації методів і засобів бінарного розрідженого розподіленого представлення та обробки інформації про прецеденти і аналоги.

Для досягнення цієї мети поставлені і вирішені наступні задачі:

1. Розробити методи бінарного розрідженого розподіленого представлення реляційної структурованої інформації.

2. Розробити методи обробки бінарних розріджених розподілених представлень реляційної структурованої інформації на основі моделювання міркувань за аналогією.

3. Розробити методи бінарного розподіленого представлення неструктурованої числової ознакової інформації.

4. Розвинути методи класифікації векторної інформації на основі бінарних розподілених представлень і моделювання міркувань за прецедентами.

5. Дослідити метод пошуку схожих бінарних розріджених розподілених представлень за допомогою нейромережевої авто-асоціативної пам'яті.

6. Дослідити розроблені методи представлення та обробки інформації.

7. Розробити програмні та апаратні засоби, що реалізують запропоновані методи представлення та обробки інформації.

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

Предмет дослідження: розподілені представлення інформації, методи їхнього формування та обробки, штучні нейронні мережі, моделі асоціативної пам'яті, методи пошуку і класифікації, моделі міркування за аналогією.

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

Наукова новизна одержаних результатів. 1. Вперше розроблений підхід до представлення реляційної структурованої інформації, що відрізняється використанням бінарних розріджених розподілених представлень (кодвекторів) фіксованої розмірності для обробки знань на основі схожості (скалярного добутку) кодвекторів при реалізації міркувань за аналогією. В рамках підходу розроблені:

· метод збереження інформації про групування та порядок компонентів структурованої інформації, що відрізняється зв'язуванням кодвекторів компонентів процедурами контекстно-залежного проріджування і перестановок;

· метод представлення ієрархічних реляційних структур, що відрізняється продукуванням схожих кодвекторів для структур зі схожими об'єктами і відношеннями.

2. Вперше розроблені підхід і методи моделювання міркувань за аналогією як виду міркувань на основі прикладів, що відрізняються представленням фрагментів знань у вигляді кодвекторів і використанням схожості кодвекторів для обробки знань та їхніх компонентів.

3. Розроблені методи представлення векторної числової інформації, що продукують бінарні кодвектори, схожість яких відображає близькість вхідних числових даних, а нелінійність перетворення дозволяє використовувати лінійні моделі для функцій, нелінійних у вхідному просторі:

· вперше запропонований метод аналізу бінарного представлення векторних числових величин гіперпрямокутними рецептивними полями, що дозволив дослідити характеристики перекриття, щільності, розмірності рецептивних полів, роздільної здатності;

· вперше розроблений метод представлення числових векторів бінарними кодвекторами фіксованої розмірності шляхом порозрядно-векторних операцій над кодвекторами їхніх елементів-скалярів з лінійними, експоненційними, циклічними характеристиками перекриття;

· удосконалений метод представлення об'єктів контекстними числовими векторами за рахунок використання кодвекторів скороченої фіксованої розмірності і регульованої розрідженості, що забезпечує підвищення обчислювальної ефективності методів обробки контекстних векторів.

Проведений аналіз характеристик кодвекторів, що надає можливість цілеспрямованого вибору їхніх параметрів при обробці числової інформації.

4. Для класифікації векторної інформації на основі бінарних розподілених представлень:

· удосконалені методи класифікації числової ознакової векторної інформації за рахунок перетворення вхідних векторів у кодвектори, використання розроблених методів аналізу для вибору параметрів перетворення, використання ядра RSC-перетворення;

· запропонований новий критерій інформаційної надмірності бінарної ознаки стосовно множини ознак, який заснований на обчисленні величини її взаємної інформації за Шенноном з кожною ознакою цільової множини, що дозволив створити обчислювально ефективні методи скорочення розмірності бінарних векторних представлень у задачах класифікації;

· удосконалений метод генерації тестових даних для порівняльного дослідження класифікаторів векторної інформації за рахунок забезпечення можливості варіювання розподілу та параметрів даних і шуму.

5. Розвинені теоретичні основи нейромережевої розподіленої авто-асоціативної пам'яті з бінарними зв'язками:

· удосконалений метод аналітичної оцінки характеристик авто-асоціативної пам'яті за рахунок застосування обчислювально ефективних апроксимацій точної функції розподілу вхідних активацій нейронів мережі та розширення спектра досліджуваних інформаційних характеристик;

· вперше досліджені інформаційні навантаження та ефективність, імовірність відновлення, розмір областей відновлення для широкого діапазону розмірностей нейронних мереж, ступеня розрідженості й рівня шуму у вхідних кодвекторах; вперше проведений порівняльний аналіз із методом Гібсона-Робінсона і мережею Хопфілда.

6. Вперше запропонована концепція програмного нейрокомп'ютера для розробки та реалізації нових інформаційних технологій, що відрізняється гнучким візуальним конфігуруванням з використанням модулів, що мають зв'язки по даним і керуванню.

Практична значимість одержаних результатів. Розроблені в дисертаційній роботі методи та алгоритми реалізовані особисто здобувачем або при його участі й керівництві як уніфіковані програмні та апаратні засоби.

Створено базові програмні засоби: формування розподілених представлень числової інформації NumericCoding, символьної інформації RandomCoding, реляційної структурованої інформації StructureCoding, асоціативної пам'яті AssocMemToolbox, класифікаторів ClassifierToolbox, обробки структурованої інформації AnalogyToolbox та ін. Розроблено та реалізовано програмне забезпечення ряду апаратних нейрокомп'ютерів (у тому числі B-512 – спільний проект із японською фірмою WACOM), інструментальний засіб для створення інтелектуальних інформаційних технологій – програмний нейрокомп'ютер SNC.

На базі розроблених методів створено системи: фільтрації потоку текстових документів за інтересами користувачів Select (в інтересах в/ч 61330); визначення семантичної близькості текстової інформації SemanticSimilarity, пошуку і класифікації текстів з урахуванням їхньої семантичної близькості SemanticBookSearch, TextSearch і TextClassifier. Метод формування представлень слів, що відбивають їхню семантичну близькість, і система SemanticSimilarity можуть використовуватися в системах автоматичної перевірки правопису з урахуванням контексту і теми, для складання багатомовних тезаурусів, визначення змісту багатозначних слів, вибирання із текстів релевантної інформації та ін.

Методи представлення структурованої інформації реалізовано в системі моделювання міркувань за аналогією AnalogySearch, яка дозволяє обчислювально спростити роботу з базами знань.

Розроблені методи та програмні засоби розподіленого представлення числової інформації застосовано для класифікації даних мас-спектрометрії, зображень, текстур, акустичних сигналів та ін.

Розроблені з використанням запропонованого критерію надмірності методи відбору бінарних ознак FeatureToolbox забезпечують скорочення розмірності векторів ознак і підвищення обчислювальної ефективності при класифікації текстів і зображень і можуть використовуватися для аналогічних задач в інших предметних галузях. Розроблено програмний засіб генерації тестових даних DGen для тестування класифікаторів.

На базі AssocMem розроблено систему моделювання асоціативної пам'яті. Розроблений метод аналізу дозволяє оцінювати інформаційні характеристики, витрати пам'яті й обчислювальну складність, вибирати параметри в реалізаціях.

На основі нейромережевих лінійних моделей розроблено системи спектрометрії і подавлення активних завад.

Розроблене алгоритмічне та програмне забезпечення використовується в наукових і практичних цілях, що підтверджується відповідними актами Міністерства промислової політики України (від 26.10.2005), Інституту геохімії навколишнього середовища НАН України (від 16.11.2005), НДІ нейрокібернетики Ростовського державного університету (від 29.09.2005), Інституту вищої нервової діяльності та нейрофізіології Російської АН (від 9.09.2005), Інституту інформатики АН Чеської Республіки (від 21.11.2005) СК "Форміка" (від 19.01.2007), АКБ "Українська фінансова група" (від 24.01.2007), ДУ "Інститут гігієни та медичної екології ім. О.М. Марзєєва АМН України" (від 09.11.2006).

Розроблені при особистій участі здобувача архітектура асоціативно-проективних нейронних мереж і RSC-класифікатор вивчаються у Фізико-технічному інституті НТУУ КПІ, у Калузькій філії МГТУ, у Ростовському Державному університеті, в університетах UNAM й Mizteca (Мексика).

Особистий внесок здобувача. У роботах, які написані у співавторстві й опубліковані у профільних виданнях, внесок здобувача полягає в наступному: [] – аналіз моделей нейронних мереж і нейрокомп'ютерів (розділ 3, крім 3.5); [] – розподілене представлення (РП) звукових сигналів, метод розпізнавання для нейрокомп'ютера; [, ] – метод РП і архітектура класифікатора, експериментальне дослідження; [, ] – постановка задачі, ідея модульної архітектури і візуального конфігурування програмного нейрокомп'ютера, алгоритми блоків обробки; [, ] – методи зв'язування (крім субтрактивного); [, ] – підхід і методи РП та обробки ієрархічно структурованої реляційної інформації, моделювання міркувань за аналогією; [, ] – методи формування й аналізу характеристик перекриття РП скалярних і векторних числових величин; [] – постановка задачі, відновлення для РП зв'язуванням унікальних незалежних кодвекторів; [, , ] – постановка задачі, вибір досліджуваних характеристик і методи аналізу, отримання аналітичних характеристик для РП RSC, порівняльний аналіз; [] – постановка задачі, критерій надмірності ознак; [, ] – методи і дослідження РП слів, що відбивають схожість значень; [] – оцінки швидкодії асоціативної пам'яті; [, ] – способи РП порядку слідування; [] – виділення блоків генерації областей класів і генерації вибірок з мітками класу, методи додавання шуму і модифікації, алгоритмічна та програмна реалізація; [] – РП зображень і механізм керування активацією нейронів; [] – метод оцінки характеристик і розробка моделі нейромережевої асоціативної пам'яті, експериментальні дослідження; [] – підхід РП до міркувань за аналогією та їх використання для інтелектуалізації антитерористичних систем; [] – постановка задачі й нейромережеве представлення моделі; [] – розробка асоціативної пам'яті для формування представлень класів зображень.

Апробація результатів дисертації. Результати дисертаційного дослідження були представлені на: 4th and 6th Intern. Conf. "Neural Networks & their Applications" (Nimes, France, 1991, 1993); ANNIE'91 and '00 Сonf. "Intelligent engineering systems through artificial neural networks" (USA, 1991, 2000); I Всеукраїнській конференції "Обробка сигналів і зображень та розпізнавання образів" (Київ, 1992); Twelfth European Meeting on Cybernetics and Systems Research (Vienna, Austria, 1994); Second Intern. Symp. on Neuroinformatics and Neurocomputers (Rostov-on-Don, Russia, 1995); 5th European Congress on Intelligent Techniques and Soft Computing "EUFIT-97" (Aachen, Germany, 1997); Intern. Joint Conf. on Neural Networks (USA, 1998, 1999); XII, XIII, XIV Міжнародних конференціях по нейрокібернетиці (Ростов-на-Дону, 1999, 2002, 2005); 9th Intern. Conf. on Neural Information Processing ICONIP'02 (Singapure, 2002); V Всеросійській науково-технічній конференції "Нейроінформатика-2003" (Москва); X, XI, Intern. Conf. “Knowledge-Dialogue-Solution” (Bulgaria, 2003, 2005); Міжнародному семінарі по індуктивному моделюванню МСІМ-05 (Київ, 2005); наукових семінарах "Образний комп'ютер" (Київ, МННЦ ІТС) і "Проблеми нейрокомп'ютерів та нейромереж" Наукової ради НАНУ з проблеми “Кібернетика”.

Публікації. Основні результати дисертації викладені в 53 друкованих працях, з них 32 статті опубліковані в наукових профільних виданнях України та інших країн.

Структура дисертації. Дисертація складається із вступу, семи розділів, висновків, списку використаних джерел із 369 найменувань (33 сторінки), семи додатків (83 сторінки). Основна частина займає 291 сторінку, ілюстрована 88 рисунками та 22 таблицями. Загальний обсяг дисертаційної роботи – 407 сторінок.

Здобувач глибоко вдячний академікові НАН України Амосову Миколі Михайловичу за підтримку в наукових дослідженнях.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми дисертаційної роботи, сформульовано мету і завдання дослідження, визначено наукову новизну і практичне значення отриманих результатів, зазначено особистий внесок здобувача.

У першому розділі дано аналіз особливостей підходу до вирішення задач штучного інтелекту (ШІ) міркуваннями на основі прецедентів і аналогій (прикладів), а також сучасного стану розподіленого представлення та обробки інформації в проблематиці ШІ. Для реалізації міркувань на основі прикладів показана важливість створення адекватних для вирішуваних задач представлень інформації та мір схожості, що забезпечують ефективний пошук найближчих відомих прикладів та їхню обробку.

Дано аналіз сучасних моделей міркувань за аналогією, що враховують реляційну схожість відношень, і виявлено їхні недоліки, які пов'язані з використанням символьних представлень інформації: ручне конструювання описів об'єктів, висока обчислювальна складність визначення схожості, складність врахування семантики. Альтернативою символьним представленням є векторні ознакові представлення, які широко використовуються в рамках нейромережевого підходу, у тому числі, розподілені представлення (РП). Розглянуто підходи до формування векторних представлень для інформації різних модальностей, а також методи вирішення задач класифікації (лінійні моделі, найближчих сусідів та ін.) і пошуку схожих векторів (асоціативна пам'ять).

На основі проведеного аналізу обґрунтовано вибір напряму розвитку теоретичної бази розподіленого представлення інформації (РПІ) шляхом розробки методів формування, обробки та аналізу бінарних розріджених (з малим числом одиничних елементів) РП як реляційної структурованої інформації, так і векторної інформації, для якої структура не виділена, з метою підвищення ефективності систем ШІ, що застосовують міркування на основі прикладів.

У другому розділі викладені концептуальні основи підходу, що розвинутий в дисертаційній роботі, до РПІ в міркуваннях за прикладами (рис. 1). Підхід базується на використанні кодвекторів – бінарних, розріджених РП структурованої та неструктурованої інформації.

Рис. . Загальна схема формування та обробки РПІ в міркуваннях за прикладами

Методи РПІ трансформують опис об'єктів x у кодвектори X (x X). Кодвектор є формою векторного представлення інформації з властивостями бінарності (X{0,1}N) і розрідженості частка ненульових елементів M кодвектора X розмірності N мала: M/N<<1). Схожі кодвектори повинні відповідати об'єктам, схожим в контексті вирішуваної задачі.

У роботі використано міри схожості кодвекторів на основі їхнього скалярного добутку, що для бінарних кодвекторів дорівнює числу співпадаючих одиничних елементів, тобто перекриттю ov:

ov(X, Y) = i=1,N Xi Yi. = |X Y|, | ()

де Xi – елемент X, – поелементна кон’юнкція, |Z| – кількість ненульових елементів в Z. ov/N – оцінка ймовірності p(Yi=1,Xi=1). Відносне перекриття (оцінка p(Yi=1|Xi=1)=p(Yi=1,Xi=1)/p(Xi=1)) є

v(X,Y) = |XY|/|X|. | ()

Його маточікування E: V(X,Y) = E{v(X,Y)}.

Показано, що використання кодвекторів забезпечує можливість підвищення ефективності міркувань за прикладами за рахунок представлення великої кількості різних об'єктів і градацій їхньої схожості, обчислювально ефективної обробки на основі асоціацій за схожістю, а також успадкування переваг традиційних РП.

Рис. 2. Приклад

фрагмента БЗ

Реляційна структурована інформація сучасних декларативних баз знань (БЗ) розглядається в роботі як позначений спрямований упорядкований ациклічний граф, де вершини-нащадки (аргументи відношень, що представлені вершинами-батьками), у свою чергу, можуть бути як об'єктами, так і відношеннями (рис. 2).

Розвиток підходу РПІ стосовно структурованої інформації полягає в його поширенні на область представлення декларативних знань і їхньої обробки в БЗ. У традиційних РП використання операцій поелементного векторного додавання для формування представлення сукупності компонентів не забезпечує адекватного представлення ієрархічних структур через втрату інформації про групування і послідовність об'єктів та відношень. У дисертації (розділ 3) розроблені методи формування кодвекторів ієрархічних реляційних структур БЗ, де ця інформація враховується. Методи засновані на використанні процедур зв'язування кодвекторів (функціонального аналога дужок, що групують, для представлення сукупності компонентів у символьній нотації): (a,b,c...)A,B,C..., де (a,b,c....) – компоненти групи, A,B,C...– їхні кодвектори, ... – процедура зв'язування кодвекторів. Формування з використанням процедур зв'язування РП реляційної структурованої інформації дозволило розробити новий підхід і методи роботи з БЗ на основі визначення схожості РП і моделювання міркувань за аналогією (розділ 3).

Розвиток підходу РП стосовно неструктурованої інформації у форматі числових векторів полягає в розробці та дослідженні методів перетворення векторного опису xA об'єктів у кодвектори X{0,1}N.

1. Методи виділення вторинних ознак реалізують нелінійне перетворення вхідного простору у вторинний. У п. 5.1 досліджені методи цієї групи, де вторинні ознаки Xi = i(x), i=1,N – бінарні елементи кодвектора X. Кожна ознака це індикатор розташування вектора x у деякій підобласті вхідного простору – рецептивному полі. Розмірність кодвектора визначається кількістю вторинних ознак N, які виділяються у вхідному просторі. Значне перекриття кодвекторів близьких вхідних векторів забезпечується завдяки наявності великої кількості спільних вторинних ознак.

2. Композиційні методи формують кодвектори X вхідних векторів x з кодвекторів їхніх елементів-скалярів хi (аналогічно формуванню кодвекторів структурованої інформації). Розмірність кодвекторів для скалярів і векторів однакова. Для кожної градації кожного елемента-скаляра формується кодвектор, причому близьким значенням (градаціям) скалярів відповідають схожі кодвектори, а далеким – несхожі. У методах п. 5.2 кодвектор X формується з кодвекторів Xiq(i) значень елементів скалярів хi=q(i) як X = X1q(1),X2q(2),...,XAq(A), де q(i) – значення xi,   – процедура зв'язування. Зв'язування (розділ 3) реалізує нелінійне перетворення. Значне перекриття кодвекторів близьких вхідних векторів забезпечується за рахунок конструювання їх зі схожих кодвекторів елементів.

3. Проекційні методи формують РП шляхом випадкової проекції вхідних векторів x у вторинний простір іншої розмірності. Перетворення в п. 5.3 має вигляд X = f(RTx). R(AN) – матриця, де кожному з A вимірів відповідає вектор-стовпець розмірністю N із випадково розташованими елементами з {1,0,–1}. f – нелінійна порогова функція. При N<A здійснюється скорочення розмірності. Відбиття величини кута між вхідними векторами у величині перекриття кодвекторів забезпечується властивостями випадкових проекцій R.

На основі розроблених методів формування кодвекторів створено і досліджено ряд класифікаторів векторної інформації (розділ 6). Відповідно до підходу міркувань за прикладами класифікація здійснюється шляхом знаходження приклада (індивідуального або узагальненого) xk, найближчого до вхідного об'єкта xвх, і переносу мітки ck класу приклада на вхідний об'єкт: {kl=1,Lsim(xвх,xl), cвх=ck}. Міра близькості sim об'єкта і приклада визначається як міра схожості кодвекторів.

Обчислювальна ефективність класифікації і пошуку релевантної інформації значною мірою залежить від розмірності векторних представлень. Для скорочення розмірності в роботі використовуються РП, що сформовані проекційними методами (розділи 5, 6), а також методами відбору інформативних ознак, для підвищення ефективності яких запропоновано обчислювально ефективний критерій оцінки інформаційного дублювання ознак (розділ 6).

Для зберігання великих баз прикладів, що представлені у вигляді кодвекторів, і швидкого пошуку схожих кодвекторів, перспективним засобом є нейромережева розподілена асоціативна пам'ять (НРАП). В розділі 4 досліджується НРАП матричного типу з бінарними зв'язками (зв'язок – елемент матриці W розмірністю NN), у якій запам'ятовування L кодвекторів Xv (l=1,L) розмірністю N здійснюється за правилом Вілшоу: Wij=l=1,L XilXjl. Кожен кодвектор містить M=pN випадково розміщених одиничних елементів. НРАП здійснює на виході відтворення кодвектора, найближчого до вхідного. На вхід подається кодвектор X(t=0)=Xin. На кожному кроці (ітерації) t роботи мережі, аж до стабілізації її стану X(t+1)=X(t), визначається X(t+1):

Xi(t+1) = (ki(t) –T(t)), | ()

де ki(t) = j Wij Xj(t) – вхідна активація нейрона, – функція Хевісайда, T(t) – поріг активації нейронів, що забезпечує |X(t+1)|=M.

Частка одиничних елементів в Xin, яка належить Xs, що запам’ятований у НРАП, дорівнює minm(Xs,Xin), де m(X,Y)=|XY|/M=v(X,Y) . Для аналізу мережі використано метод апроксимації одного кроку (АОК), який передбачає, що перекриття m(t)=m(X(t),Xs) змінюється монотонно в процесі відновлення: якщо на першому кроці m(t=1)>min, процес зійдеться до кодвектора, що запам’ятований, інакше – не зійдеться. При АОК виконання m(t=1)=min задає чітку границю mab областей притягання кодвекторів, що запам’ятовані: при min>mab виконується m(t=1)>min. p=P(Xi=1|Xis=) – імовірності того, що нейрони, які належать (=1) і не приналежні (=0) кодвектору Xs є активними в X. За визначенням p1=m(X,Xs). Необхідні для визначення m(t=1) імовірності p обчислюються як p=kT(0)P(k), де випадкова змінна k – вхідна активація нейронів . Також досліджено метод Гібсона і Робінсона АГР, що аналізує мережу на всіх кроках функціонування, але застосовує гаусову апроксимацію розподілу k. Аналітичні результати АОК і АГР порівнювалися з результатами експериментального дослідження моделі даного типу НРАП, а також мережі Хопфілда. Проведене в роботі дослідження інформаційних характеристик НРАП (навантаження, корегуюча здатність, ефективність та ін.) створює необхідну теоретичну базу для її використання при вирішенні задач методом міркування за прикладами.

Програмно-апаратні інструментальні засоби і прикладні системи для вирішення задач ШІ на основі розроблених методів розглянуто в розділі 7.

Третій розділ присвячено розробці підходу і методів РП складної ієрархічно структурованої реляційної інформації БЗ та її обробки шляхом моделювання міркувань за аналогією. Методи засновані на зв'язуванні кодвекторів процедурами поелементної кон’юнкції, контекстно-залежного проріджування, перестановки.

Розроблено процедуру зв'язування аддітивним контекстно-залежним проріджуванням (CDT, context-dependent thinning). Перша стадія процедури – формування кодвектора Z як диз'юнкції кодвекторів компонентів Xi:

Z = i=1,S Xi, | ()

Друга стадія:

Z = k=1,K ( Z Z*(k) ) = Z k=1,K Z*(k) = Z T(Z). | ()

Тут Z – результат зв'язування X1, X2 ,..., XS, Z*(k) = PkZ – Z з переставленими елементами, P – матриця перестановок, T(Z)=k=1,K Z*(k). Для кожного k використовується незалежна випадкова перестановка. Кількість одиничних елементів в Z регулюється вибором значення K. Однакова розмірність Z і Xi забезпечує можливість рекурсивного застосування процедур зв'язування. Схожість Z з Xi дозволяє відновлювати Xi по Z.

Показано, що трансформує величину перекриття як (рис. 3а)

V(Z1,Z2) = [ V(Z1, Z2) ]b, b [1,2]; | ()

b залежить від глибини проріджування K: b=2 відповідає зв'язуванню кон’юнкцією (K=1), b=1 – відсутності зв'язування (K>>1).

У результаті зв'язування склад підмножини одиничних елементів будь-якого кодвектора-компонента в результуючому кодвекторі залежить від всіх інших компонентів групи і в результуючому прорідженому кодвекторі зберігається інформація про групування (комбінації) кодвекторів-компонентів. Залежність схожості підмножин кодвектора того самого компонента в різних Z1 і Z2: V (Xi, Z1Z2) від схожості Z1 і Z2 показана на рис. 3б.

а | б

Рис. . Залежність: а – V(Z1,Z2) від V(Z1,Z2), б – V(XiZ1,XiZ2) від V(Z1,Z2)

Розроблено методи формування кодвекторів відношень виду R(A,B,....), (де R – ідентифікатор відношення, A,B.... – аргументи), що відповідають схемам роль-заповнювач (role-filler) і предикат-аргументи (predicate-arguments), які традиційно використовуються у символьних представленнях.

Методом роль-заповнювач кодвектор відношення формується як R(A,B,....)  Ra, A,Ro, B, .... , де A, B, ... – кодвектори аргументів (об'єктів-заповнювачів), Ra, Ro, ... – кодвектори ролей. Методом предикат-аргументи кодвектор відношення формується як R(A,B,....) R~1, A~2, B~3,..., де R, A, B, ... – кодвектори предиката (відношення) і аргументів, R~i – зв'язування перестановкою кодвектора, де i – порядковий номер аргументу (який задає його роль).

Розмірність кодвекторів відношень і їхніх аргументів однакова, що дозволяє формувати кодвектори складних ієрархічних реляційних структур, які містять відношення вищих порядків, рекурсивним застосуванням розроблених методів побудови кодвекторів відношень (роль-заповнювач і предикати-аргументи). Наприклад, для реляційної структури рис. 2 кодвектор, сформований методом предикат-аргументи, має вигляд:

RA~1 R1 C~1~2 R1 C~1 R A~1 B~2 ~2 ~3. | ()

Для структур зі схожими об'єктами і відношеннями продукуються схожі кодвектори. Схожість кодвекторів тим більше, чим більше схожість відношень та їхніх аргументів.

На базі розроблених РП реляційної структурованої інформації розвинено новий підхід до моделювання міркувань за аналогією, який спрямований на застосування у системах ШІ, що засновані на знаннях. Аналоги є ієрархічно структурованими описами епізодів або ситуацій у БЗ. Розроблено нові методи, що реалізують етапи міркувань за аналогією: представлення інформації про аналоги; пошук у пам'яті аналога, найближчого до вхідного; відображення – встановлення відповідності компонентів аналогів (рис. 4).

Представлення аналогів здійснюється за допомогою розроблених методів РП реляційної структурованої інформації.

Пошук найближчих аналогів здійснюється за величиною перекриття їхніх кодвекторів Xl з кодвектором вхідного аналога Xвх:

l*(xвх) = argmax l=1,L V(Xвх, Xl), | ()

l – індекс, L – число аналогів (епізодів) у БЗ.

Методи відображення, що засновані на використанні схожості кодвекторів, вперше дозволили реалізувати відображення аналогів зі складною структурою за допомогою РП:

· метод, заснований на безпосередньому визначенні максимальної схожості кодвектора компонента xi аналога x, що відображається, до кодвекторів компонентів аналога y:

j*(xi) = argmax j=1,J V(Xi, Yj), | ()

j і J – індекс і число компонентів аналога y, Xi – кодвектор компонента xi, Yj – кодвектор j-го компонента аналога;

· метод, що використовує синхронний обхід структур аналогів з постановкою у відповідність компонентів одного типу (ролі, об'єкту, відношення тощо)

j*(xi,h) = argmax V(Xi,h, Yj,h) при h=hmax;

j*(xi,h) = argmax V( roleXi,h, roleYj,h) при h < hmax, | ()

Рис. . Міркування за аналогією з використанням РП

де h – рівень компонента аналога, xi,h і yj,h – компоненти рівня h аналогів x і y, Xi,h і Yj,h – їхні кодвектори, roleXi,h і roleYj,h – кодвектори, що відповідають ролям компонентів xi,h і yi,h у відображених компонентах рівня h+1.

Для відображення компонентів аналогів зі складною структурою за-пропоновано використати модифікації РП у процесі відображення.

Розроблені методи реалізовані програмними засобами та експеримен-тально досліджені на фрагментах БЗ, що використовуються для дослідження моделей міркувань за аналогією. Проведені дослідження довели адекватність запропонованого підходу до моделювання міркувань за аналогією i більш високу обчислювальну ефективність його реалізації в порівнянні із традиційними символьними методами. Обчислювальна складність пошуку становить O(1)-O(L) у порівнянні з O(n2L)-O(n!L), або O(n4L2) для традиційних методів, де n – число компонентів аналога. Обчислювальна складність відображення становить O(n2) у порівнянні з O(n4)-O(n!) для традиційних методів. На основі запропонованого підходу С.В. Сліпченко розроблені програмні засоби пошуку, відображення та виводу за аналогією в БЗ, що дозволило на базі ThinkNet підвищити повноту пошуку до 20% і точність в 3-4 рази.

Четвертий розділ присвячений дослідженню інформаційних характеристик нейромережевої розподіленої авто-асоціативної пам'яті (НРАП), як перспективного засобу пошуку найближчих прикладів, що представлені кодвекторами.

Інформаційне навантаження (інформація, завантажена в НРАП з матрицею зв'язків NN при запам'ятовуванні L незалежних кодвекторів) є Il = LNh(p), де h(p) = –plog p–(1–p)log(1–p) – функція Шеннона. Відносне інформаційне навантаження, що припадає на один зв'язок:

= Il/N2 = Lh(p)/N. | ()

Як міру розрідженості кодвекторів використано

= (1/M) log2 (1/p), тобто N=M2M. | ()

Після запам'ятовування L кодвекторів (з p<<1) частка одиничних зв'язків

= 1 – (1 – p2)L 1 – exp(–Lp2) 1 – exp(–/). | ()

Аналіз НРАП здійснювався при наступних умовах:

Lp2 порядку 1, a порядку 1, р 1, тоді NL i =Np2 M2/N 1. | ()

Використовувався точний розподіл ("подвійний біноміальний" DouBin) вхідних активацій P(k) на першому кроці процесу відновлення (k=0,...,M):

P(k) = u=1,LP(u)P(k|u), P(u) = CL–1u pu(1 – p)L–1–u. | ()

P(u)– імовірність того, що нейрон був активним u разів при запам'ятовуванні L–1 інших кодвекторів. P(k|u) – імовірність, що у такого нейрона активовані k зв'язків:

P0(k | u) = CMk uk(1–u)M–k, k=0,...,M, u=1,...,L; | ()

, k = minM,…,M, u=1,...,L. | ()

u=1– (1–p)u, при p1 u = 1 – exp(–pu). | ()

Показано, що з точністю 3 (де 2 = p3L) для маточікувань E і дисперсій D

E0=M [1–((1–)/ ) ln(1/(1–))p/2], E1= Mmin+(1–min)M( – (1–) ln(1/1–)p/2). | ()

D0 = M (1–)+(1–)2 ln(1/(1–)) M; | ()

D1 = M(1–min) (1–)+ (1–min)2(1–)2 ln(1/(1–)) M. | ()

По P(k) при значенні порога T(0) , що забезпечує M,

p1M + p0(N–M) = M | ()

можна визначити p1 m(t=1) і порівняти його з min для визначення, чи зійдеться процес відновлення до вектора в пам'яті згідно АОК. При min = m(t=1) одержуємо шукану границю області притягання mab(a, b і M), або граничне інформаційне навантаження aab (min,M,b), що відповідає mab. Для великих мереж прямі обчислення P(k) по вимагають значних витрат пам'яті та часу. Тому розроблені обчислювально ефективні апроксимації: гаусова (Norm), біноміальна (Bin), скорегована біноміальна (CorBin) і проведено оцінку їхньої точності.

Для аналітичних методів i експериментальних даних ab апроксимувалося як

ab = as + a0/M + a1/M, | ()

де as – асимптотичне значення ab при M, a0 i a1 – коефіцієнти, що залежать тільки від і min, визначалися за методом найменших квадратів.

Показано, що для гаусової апроксимації i заданих min i b значення as:Norm (однозначно пов'язане з ) може бути знайдено із рівняння

(2 (1–)b ln2)1/2 = mab (1–). | ()

Для біноміальної апроксимації as:Bin може бути знайдено із

h(x)ln2 + xln(k) + (1–x)ln(1–k) + b ln2 = 0, де x T(0)/M mab + (1–mab)k. | ()

Апроксимація P0(k) скорегованим біноміальним розподілом має вигляд

P0(k)=(1+ln(1/(1–k))(k/M)(1–k)/k2)–1/2CMkk k(1–k)M–kexp(1/p)Lp22((k/M–k)/k))2/2). | ()

При =0 вона збігається з біноміальним розподілом.

Експериментальне дослідження інформаційних характеристик НРАП проводилося у широкому діапазоні параметрів = {0.05, 0.1, 0.2, 0.3}, N103 до N105, min= {0.1, 0.3, 0.5}. Дослідження не підтвердило прогнозований АОК різкий перехід між умовами відновлення та невідновлення і показало нечіткість цих границь. Тому визначалося значення mab(P), що забезпечує деяку фіксовану ймовірність P відновлення кодвектора в пам'яті. Приклад отриманих залежностей ab від lgM при = 0.05 наведений на рис. 5 як для апроксимації експериментальних даних (Exp:P=0.5), так і для АОК (SS) і АГР (GibRob). Експерименти довели, що в широкому діапазоні параметрів АОК дає більш точні результати ніж АГР. Проаналізовано причини й параметри, при яких це спостерігається.

На основі апроксимації експериментальних даних отримано залежності ймовірності відновлення P від (приклад наведений на рис. 6), що дозволяє оцінювати параметри, які забезпечують надійне функціонування НРАП. Отримано також залежності ab від M для різних значень імовірності відновлення P. Показано, що для дослідженої НРАП ab має максимум при невеликих