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

ІНСТИТУТ ПРОБЛЕМ МАТЕМАТИЧНИХ МАШИН І СИСТЕМ

Дехтяренко Олексій Костянтинович

УДК 681.5

РОЗРОБКА І ДОСЛІДЖЕННЯ МЕТОДІВ ПОБУДОВИ НЕПОВНОЗВ’ЯЗНИХ АСОЦІАТИВНИХ НЕЙРОННИХ МЕРЕЖ

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

АВТОРЕФЕРАТ

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

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

Київ – 2006

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

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

Науковий керівник: доктор технічних наук,

старший науковий співробітник

Різник Олександр Михайлович,

Інститут проблем математичних машин

і систем НАН України,

завідувач відділу

Офіційні опоненти: доктор технічних наук,

професор

Гладун Віктор Полікарпович,

Інститут кібернетики ім. В.М. Глушкова

НАН України,

провідний науковий співробітник,

в.о. завідувача відділу

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

Гольцев Олександр Дмитрович,

Міжнародний науково-навчальний центр

інформаційних технологій та систем

НАН та МОН України,

старший науковий співробітник

Провідна установа: Національний технічний університет України "КПІ",

кафедра автоматизованих систем обробки інформації і

управління, м. Київ.

Захист відбудеться “ 11 ” жовтня 2006 р. о 14.00 годині на засіданні спеціалізованої вченої ради Д26.204.01 в Інституті проблем математичних машин і систем НАН України за адресою: 03187, Київ - 187, проспект Академіка Глушкова, 42.

З дисертацією можна ознайомитись у науковій бібліотеці Інституту проблем математичних машин і систем НАН України за адресою: 03187, Київ - 187, проспект Академіка Глушкова, 42.

Автореферат розісланий “ 29 ” _серпня__ 2006 р.

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

спеціалізованої вченої ради,

кандидат технічних наук Ходак В.І.

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

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

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Основні дослідження за темою дисертації проводилися у відділі нейротехнологій Інституту математичних машин і систем НАН України в межах виконання низки науково-дослідних робіт:

– “Дослідження й удосконалення засобів інтерфейсу нейрокомп’ютерів із застосуванням структурних методів кодування даних”, завдання № за програмою прикладних та фундаментальних досліджень ІПММС НАН України;

– “Розробка серії нейрокомп’ютерів загального призначення”, проект № .1.3.А за програмою науково-технічних робіт МОН України;

– “Smart Sensors for Field Screening of Air Pollutants” за програмою INTAS 2001-257;

– “Cellular Associative Neural Networks” за програмою INTAS YSF 03-55-795.

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

1. Визначена архітектура.

2. Визначена кількість зв’язків.

3. Визначена кількість зв’язків з вимогою їх мінімальної загальної протяжності.

Для досягнення мети дослідження в роботі поставлено і вирішено такі задачі:

– побудова методів аналізу якості моделей ННАП;

– теоретичний аналіз розроблених методів вибору архітектури і навчання ННАП;

– розробка програмних засобів для моделювання ННАП і алгоритмів навчання;

– експериментальна перевірка розроблених методів вибору архітектури і навчання ННАП для розв’язку прикладних задач.

Об’єкт дослідження. Об’єктом дослідження дисертаційної роботи є модель неповнозв’язної нейронної асоціативної пам’яті (ННАП).

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

Методи дослідження. При розробці та дослідженні моделей ННАП використовувалися методи лінійної алгебри, математичного моделювання, програмування, математичної статистики та інші.

Наукова новизна одержаних результатів.

1. Для моделі ННАП з фіксованою архітектурою запропоновано вдосконалення псевдоінверсного алгоритму навчання, яке покращило асоціативні якості мережі і дозволило навчання мереж з несиметричними архітектурами.

2. Вперше отримані теоретичні оцінки асоціативних якостей мережі і характеристик вагової матриці (значення сліду, ступінь виродження) для ННАП з проекційним і псевдоінверсним алгоритмами навчання.

3. Розроблена методика, яка дозволяє збільшити ємність пам’яті ННАП завдяки побудові архітектури мережі з урахуванням даних, що запам’ятовуються.

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

5. Отримала подальшого розвитку модель ННАП з архітектурою “тісного світу”, що дозволило покращити асоціативні якості при збереженні всіх відомих переваг цієї архітектури.

6. Експериментально показані можливість застосування і переваги моделей ННАП на прикладі задачі класифікації сигналів сенсорів запаху (система типу “Електронний ніс”).

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

Отримані результати, зокрема, використані при розробці професійного багатофункціонального комплексу програм “NeuroLand”, для якого було отримане свідоцтво про реєстрацію авторського права на твір № 6169 – “Комп’ютерна програма для моделювання нейронних мереж та проектування прикладних нейросистем “NeuroLand”, Міністерство освіти і науки України, Державний департамент інтелектуальної власності”.

Ефективність розроблених у роботі алгоритмів продемонстровано на прикладі розв’язання задачі розпізнавання хімічних образів.

Особистий внесок здобувача полягає у розробці нових методів, алгоритмів і програм, що забезпечують розв’язання поставленої задачі. Всі основні результати дисертаційної роботи отримані автором самостійно. В публікаціях, написаних у співавторстві, здобувачеві належить: [1-4] – створення програмних засобів і проведення експериментальних досліджень з використанням асоціативних нейронних мереж; в роботах [5, 6] – розробка і реалізація алгоритмів ННАП і вдосконалення алгоритму модульної НАП; в роботах [7-9] – постановка задачі, розробка та програмна реалізація алгоритмів; в роботі [10] – теоретичний та експериментальний аналіз явища, що вивчалося, співавторам належить постановка задачі; в роботі [11] автору належить реалізація програмної бібліотеки ННАП, співавтору – застосування НАП для задачі розпізнавання відеоданих з низьким розділенням; у роботах [12-17] автору належить програмна реалізація і експериментальний аналіз моделей, що вивчалися. Роботи [18-20] виконані без співавторів.

Апробація результатів роботи. Основні результати доповідалися та обговорювалися на таких наукових семінарах та конференціях:

- Міжнародній конференції з індуктивного моделювання “МКІМ – 2002” (Львів, 20-25 травня, 2002);

- VIII Всеросійській конференції “Нейрокомпьютеры и их применение” НКП-2002 (Москва, 21-22 березня, 2002);

- Міжнародній конференції “9th International Conference on Neural Information Processing” ICONIP'02 (Singapore, November 18-22, 2002);

- Міжнародній конференції “The 10-th International Symposium on Olfaction and Electronic Nose” ISOEN’03 (Riga, Latvia, June 25-28, 2003);

- Міжнародній конференції “The 8th IEEE International Biannual Workshop on Cellular Neural Networks and their Application” CNNA'04 (Budapest, Hungary, July 22-24, 2004);

- Міжнародній конференції “European Symposium on Artificial Neural Networks” ESANN'05 (Bruges, Belgium, April 27-29, 2005);

- Міжнародній конференції “International Joint Conference on Neural Networks” IJCNN'05 (Montreal, Quebec, Canada, July 31 - August 4, 2005).

Публікації. Основні результати роботи викладено в 20 наукових працях, з яких – 4 статті у наукових фахових журналах, рекомендованих ВАК України для спеціальності 05.13.23. З них 2 одноосібні.

Структура дисертації. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаних джерел з 138 найменувань. Обсяг дисертації становить 124 сторінки основного тексту, ілюстрованих 55 рисунками та 3 таблицями.

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

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

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

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

Найбільшим поштовхом для поглибленого вивчення моделей нейронних асоціативних мереж послугувала робота J. Hopfield (1982), в якій була показана можливість асоціативної обробки інформації за допомогою рекурентної нейронної мережі, а також запропонований метод доведення стійкості таких систем. З того часу асоціативні нейронні мережі часто називають мережами Хопфілда, хоча існує ряд більш ранніх робіт, присвячених асоціативним нейроподібним моделям (S.I.), J.A. Anderson (1972), K.(1972), T.(1974)).

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

Модель неповнозв’язної нейронної асоціативної пам’яті (ННАП) дозволяє реалізовувати мережі з більшою кількістю нейронів. Це є особливо важливим у випадку апаратної реалізації НАП, оскільки неповнозв’язна архітектура дає можливість суттєво зменшити кількість зв’язків у порівнянні з повнозв’язною моделлю, а також виключити зв’язки, які є складними для реалізації (наприклад, у випадку з НВІС-реалізацією такими зв’язками є зв’язки між просторово віддаленими нейронами).

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

Неповнозв’язна архітектура моделі, що розглядається, також відповідає способу організації біологічного мозку. Відомо, що для кори головного мозку людини відношення числа існуючих зв’язків (1014) до числа усіх можливих міжнейронних зв’язків для близько 1011 нейронів складає величину порядку 10-8, причому серед існуючих зв’язків домінують зв’язки локального характеру. Вивчення неповнозв’язної мережі Хопфілда дозволяє встановити вплив різних принципів побудови архітектури на асоціативні якості мережі, отримуючи результати, які можуть бути співвіднесені з даними нейрофізіологічних досліджень.

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

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

Розглядається модель неповнозв’язної мережі Хопфілда з біполярними станами і така, що функціонує в дискретні проміжки часу. Мережа складається з n нейронів, причому вихід нейрону j може впливати на вихід нейрону i лише за умови , де – підмножина індексів, що не повторюються. Сукупність множин індексів існуючих зв’язків кожного із нейронів задає архітектуру всієї мережі: .

Архітектура неповнозв’язної мережі характеризується густиною зв’язків, або ступенем зв’язності: , а також загальною протяжністю зв’язків: , де distT(i, j) – функція, яка визначає відстань між нейронами i та j і залежить від обраної топології мережі.

Типовими прикладами неповнозв’язних архітектур є клітинна мережа (також відома як мережа з регулярною архітектурою, або мережа з локальною зв’язністю, що визначається радіусом зв’язків r: – одномірній випадок), мережа з архітектурою “тісного світу”, а також мережа з випадковим розміщенням зв’язків (рис. 1).

a) | b) | c)

Рис. 1. Архітектури неповнозв’язних асоціативних мереж

а) клітинна (регулярна); b) “тісного світу”; c) випадкова

Асоціативна нейронна мережа є динамічною системою, яка обробляє інформацію шляхом еволюції свого стану з плином часу. Зважена сума входів i-го нейрона в момент дискретного часу t формує значення його постсинаптичного потенціалу , де – вагова, або синаптична матриця мережі, а B – вектор порогів. Вхідні дані задають початковий стан мережі. Часова динаміка мережі (процес конвергенції) описується рівнянням , а стійкі стани, в які потрапляє мережа (атрактори), формують її вихід .

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

Задача навчання неповнозв’язної мережі для заданого набору еталонів V полягає у знаходженні такої архітектури мережі N і значень вагових коефіцієнтів W та порогу B, які б забезпечували максимальні асоціативні якості відносно цього набору.

Чисельно асоціативні якості мережі можуть характеризуватися значенням абсолютного атракторного радіуса (найбільший ступень спотворення вхідних даних в одиницях метрики Хемінга, який все ще виправляється мережею в ході процесу конвергенції) з множиною значень 1…n або усередненого відносного атракторного радіуса з діапазоном значень [0, 1].

В розділі розглянуті два ітеративні та три неітеративні методи навчання:

1.1. Правило Хебба – ітеративний пошук розв’язку системи нерівностей за правилом .

1.2. Дельта-правило – градієнтна мінімізація .

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

2.2. Псевдоінверсний алгоритм з процедурою симетризації вагової матриці – пошук оптимального розв’язку системи рівнянь за допомогою операції псевдообернення і забезпеченням симетричності W.

2.3. Псевдоінверсний алгоритм без процедури симетризації – .

Псевдоінверсний алгоритм використовує оператор селекції , який залишає від свого матричного аргументу лише ті стовпчики, які відповідають існуючим ( – переддіагональним, – постдіагональним) зв’язкам i-го нейрона.

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

Для кліткової мережі з радіусом міжнейронних зв’язків r, що навчається за проекційним правилом з видаленням частини зв’язків, теоретична оцінка прямого атракторного радіуса (який проявляється за один крок процесу конвергенції) має вигляд

.

Ця оцінка коректно описує атракторні властивості мережі для малих ступенів заповнення пам’яті m, а також коректно оцінює верхню межу ємності мережі величиною m ~ 2r.

Твердження 2.1. Для кліткової мережі з псевдоінверсним алгоритмом навчання без симетризації мають місце наступні вирази для сліду, норми і ступеня виродження вагової матриці W:

.

Наслідок 2.1. Останній вираз накладає обмеження на ємність мережі з клітковою архітектурою m ~ 2r.

Для довільного набору даних V, що запам’ятовуються, доведено властивість збіжності дельта-правила до вагової матриці мережі з псевдоінверсним алгоритмом навчання.

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

Рис. 2. Ємність клітинних мереж з різними алгоритмами навчання (n = 256, R = 30)

При експериментальній оцінці атракторного радіуса мереж використовувалося 100 тестових епох. На рис. 2 наведені експериментальні значення ємності клітинних мереж з проекційним (Pro-jective) і псевдоінверсними алгоритмами навчання без/з симетризацією (PI Asym/ Sym), а також з викори-станням порогу (PI Asym with Bias). Ємність визначалась як максимальна кількість еталонів m з набору Vuncorr, що здатна зберігати мережа, забезпечуючи певне значення атракторного радіуса R.

Шляхом експериментального порівняння алгоритмів одержано такі результати:

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

2. Меншу в 5-15 разів обчислювальну складність неітеративних методів (проекційного і псевдоінверсних алгоритмів) у порівнянні з ітеративними методами (правило Хебба і дельта-правило).

3. Використання порогу для псевдоінверсного алгоритму дозволяє збільшити ємність мережі в середньому на один еталон.

Для псевдоінверсного алгоритму було встановлено, що використання процедури симетризації призводить до:

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

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

Модифікація псевдоінверсного алгоритму шляхом відмови від процедури симетризації дозволяє:

1. Покращити асоціативні якості мережі (збільшити ємність у 2-3 рази).

2. Проводити навчання мереж з несиметричними архітектурами.

3. Не призводить до суттєвої втрати стійкості мережі під час процесу конвергенції (для n = 256, m = 4, r = 12 з’являється ~0.0001 імовірність появи динамічних атракторів кратності 4).

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

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

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

Рис. 3. Значення атракторного радіуса R в залежності від густини зв’язків ?

На рис. 3 показані експериментальні значення атракторного радіуса, отримані на наборі еталонів Vuncorr для мереж з псевдоінверсним алгоритмом навчання без симетризації з різними принципами побудови архітектури: адаптивною (Adaptive), випадковою (PI Random), клітинною (PI Cell) та адаптивною зі зворотною селекцією (побудова архітектури з використанням розміщення найменш інфор-мативних зв’язків – PI Adaptive Reverse).

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

Для мережі з однокроковим процесом конвергенції і проекційним алгоритмом навчання була отримана теоретична оцінка прямого атракторного радіуса в залежності від густини зв’язків ?: , де T – величина порогу селекції, який забезпечує потрібну зв’язність мережі. Значення порогу, а також підкореневих дисперсій випливають зі статистичних властивостей проекційної матриці. Побудова залежностей атракторного радіуса (рис. 4а) для різних значень розмірності мережі n і кількості еталонів, що зберігаються m, дозволило теоретично оцінити поведінку критичної густини зв’язків, і продемонструвати її зменшення із зростанням n і зменшенням m (рис. 4b).

Рис. 4. Оцінка критичної густини зв’язків

Рис. 5. Залежність критичної густини зв’язків від нормалізованого ступеня заповнення пам’яті мережі

Для набору даних Vrandom було отримано експериментальну зале-жність критичної густини зв’язків (Transition Connectivity) від нормалізованого ступеня запов-нення пам’яті мережі – m/n, яка виявилася практично лінійною, з коефіцієнтом кореляції R2 = 0.993 (рис. 5). Можливість оцінки зна-чення густини зв’язків, яке лежить у правій частині околу точки фазового переходу, є важливою інформацією, оскільки дозволяє будувати неповнозв’язну мережу з асоціативними якостями, що практично не поступаються її повнозв’язному аналогу, при цьому уникаючи процесу перебору неповнозв’язних мереж з різними ступенями зв’язності архітектури.

В третій частині розділу запропонований метод систематичного переносу зв’язків при побудові мережі з архітектурою “тісного світу”. Феномен “тісного світу” вперше був виявлений в царині соціології в роботі S._Milgram в 1967 році, де було встановлено факт, що будь-які дві людини на Землі знайомі між собою через ланцюжок в середньому з шести проміжних знайомих. Формальне математичне описання моделі “тісного світу” було подано в роботі D.J. Watts, H. Strogatz в 1998 р., визначаючи під цією моделлю систему з малою середньою протяжністю зв’язків і з великим ступенем кластеризації. Також в цій роботі було запропоновано спосіб побудови архітектури “тісного світу” на основі регулярної архітектури, використовуючи випадкове перенесення невеликої кількості зв’язків.

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

Рис. 6. Етапи навчання неповнозв’язної мережі з архітектурою “тісного світу” і систематичним переносом зв’язків

Рис. 7. Експериментальне значення відносного атракторного радіуса мережі в залежності від частини перенесених зв’язків (дані Vuncorr)

Запропонований в даній роботі метод систематичного (Systematic) переносу зв’язків на відміну від вихідного методу випадкового переносу (Random), використовує заміну найменш інформативних локальних зв’язків на найбільш інформативні, які відібрані за допомогою правила селекції вагових коефіцієнтів повнозв’язної мережі (рис. 6). Такий підхід дозволяє покращити атракторні властивості мережі в 3-10 разів (рис. 7).

В четвертій частині розділу проводиться перевірка встановлених закономірностей асоціативної поведінки мереж з різними алгоритмами

Рис. 8. Ємність мережі (m) для різних алгоритмів навчання і принципів побудови архітектури. Некорельовані і корельовані дані (Uncorr/Corr)

навчання і принципами побудови архітектури для корельованих зміщених даних Vcorr з розмірністю n = 256. Ці дані були отримані за допомогою Марківського про-цесу з двома станами і ймовірностями переходів p-1>+1 = 0.3, p+1>-1 = 0.2 (математичне очікування M(xi) = 0.2, corr(xi, xi+1) = 0.5, середня довжина послідовності з +1 M(lpos) = 5). На рис. 8 наведені експериментальні значення ємностей (за умови забезпечення АР R = 30) мережі з адаптивною архітектурою (PI Adaptive) і клітинних мереж з псевдоінверсним (PI Cell) і проекційним (Projective Cell) алгоритмами навчання. Взаємна поведінка ємностей мереж відповідає вже з’ясованій для некорельованих даних, хоча слід зазначити загальне зменшення показників ємностей для набору Vcorr.

Рис. 9. Відносна інформаційна ємність неповнозв’язної мережі

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

.

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

1. Ефективна (з точки зори обчислювальних ресурсів і ресурсів пам’яті) реалізація моделей і алгоритмів навчання ННАП.

2. Розвинуті засоби тестування асоціативних мереж.

3. Зручний програмний інтерфейс, який спрощує використання бібліотеки іншими прикладними програмами.

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

На рис. 10 показано структуру частини бібліотеки, яка відповідає за множину мереж асоціативної пам’яті.

Рис. 10. Ієрархія мереж асоціативної пам’яті

В другій частині розділу розглянуто приклад практичного застосування неповнозв’язних асоціативних нейронних мереж для задачі класифікації сигналів сенсорів запаху (система типу “Електронний ніс”).

Для навчання нейронної мережі були використані дані, отримані з використанням експериментальної установки, яка працює на принципі мікробалансу пластин кварцових кристалів (зміна власної частоти коливань при вибірковому поглинанні поверхнею кристала молекул ароматичних речовин). Класифікація проводилася проміж 6 класів хімічних речовин з 5-15 представниками кожного класу. Через невелику кількість навчальних прикладів тестування відбувалося за принципом n-Fold крос-валідації, в якій здійснювалося 10 випадкових розбиттів даних на множини для навчання і тестування таким чином, щоб множина для тестування включала по одному представникові кожного класу. За цими 10 розбиттями були отримані середнє значення і дисперсія класифікаційних результатів.

Для класифікації було використано модель модульного асоціативного класифікатора. Цей класифікатор складається з модулів, в ролі яких виступають окремі асоціативні нейронні мережі. Кількість модулів відповідає кількості класів даних, і кожен модуль зберігає представників відповідного класу. На етапі тестування для кожного модуля i з ваговою матрицею Wi обчислюється значення коефіцієнта відмінності – величини, яка характеризує ступінь лінійної незалежності вхідного вектора даних X від набору даних, що зберігається у цьому модулі. Рішення про клас вхідного вектора приймається за найменшим значенням коефіцієнта відмінності. Як асоціативні модулі були використані неповнозв’язні асоціативні мережі з адаптивною архітектурою, що розглянуті в третьому розділі.

Рис. 11. Середнє значення і с.к.в. помилки класифікації в залежності від густини зв’язків мережі

На рис. 11 показано залежність якості класифікації та її середньо-квадратичного відхилення (с.к.в.) від ступеня зв’язності (густини зв’язків с) модулів. Видно, що якість класифікації зростає з ростом ступеня зв’язності модуля, причому для досягнення максимального резуль-тату класифікації, властивого повнозв’язній мережі (CR [0.7, 0.8]), досить використання модуля зі ступенем зв’язності ? = 0.2 (точка (0.2, 0.74) на рис. 10).

ВИСНОВКИ

Результатом дисертаційної роботи є розробка нових методів побудови асоціативної пам’яті на базі неповнозв’язних нейронних мереж типу Хопфілда. Ці методи охоплюють як етап побудови архітектури мережі, так і етап знаходження ваги міжнейронних зв’язків, дозволяючи збільшити ємність пам’яті моделей ННАП при обмеженнях на густину зв’язків або на густину і загальну протяжність зв’язків. У практичному плані використання одержаних в роботі результатів дозволяє підвищити ефективність роботи неповнозв’язних асоціативних нейромереж; дозволяє моделювання і апаратну побудову мереж з більшою кількістю нейронів; може бути використаним для моделювання асоціативної поведінки неповнозв’язних структур нейронів мозку.

Головні наукові та практичні результати:

1. Для моделі ННАП з фіксованою архітектурою запропонована модифікація псевдоінверсного алгоритму навчання, яка полягає у відмові від процедури симетризації, тим самим дозволяючи поліпшити асоціативні якості мережі (збільшити обсяг пам’яті в 2-3 рази) і будувати мережі з несиметричними архітектурами.

2. Вперше отримані теоретичні оцінки для асоціативних властивостей і характеристик вагової матриці (значення сліду, ступінь виродження) ННАП з проекційним і псевдоінверсним алгоритмами навчання.

3. Розроблено методику побудови мережі з адаптивною архітектурою, що дозволило збільшити ємність пам’яті ННАП в 2-4 рази у порівнянні з мережею з фіксованою архітектурою.

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

5. Отримала подальшого розвитку модель ННАП з архітектурою “тісного світу”, що дозволило покращити асоціативні якості відповідної мережі в 3-10 разів при збереженні всіх відомих переваг даної архітектури.

6. Розроблено підсистему мереж асоціативної пам’яті програмного нейрокомп’ютера NeuroLand, яка включає як одномодульні, так і багатомодульні мережі.

7. Створено алгоритмічну бібліотеку неповнозв’язних мереж з розвиненими засобами тестування й аналізу.

8. Експериментально показані можливість застосування і переваги моделей ННАП на прикладі задачі класифікації сигналів сенсорів запаху (система типу “Електронний ніс”).

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Резник А.М., Ширшов Ю.М., Снопок Б.А., Новицкий Д.В., Дехтяренко А.К., Кругленко И.В. Ассоциативная память в задачах распознавания химических образов // Праці Міжнародної конференції з індуктивного моделювання (МКІМ’02). – Львів. – 2002. – С. 246-252.

2. Reznik A.M., Shirshov Y.M., Snopok B.A., Nowicki D.W., Dekhtyarenko O.K., Kruglenko I.V. Associative memories for chemical sensing // 9th International Conference on Neural Information Processing (ICONIP’02). – Singapore. – 2002. – P. 205-211.

3. Reznik A.M., Galinskaya A.A., Dekhtyarenko O.K., Nowicki D.W. A comparison of preprocessing techniques for matrix QCM sensors data classified by neural network // The 10-th International Symposium on Olfaction and Electronic Nose (ISOEN’03). – Riga, Latvia. – 2003. – P. 189-192.

4. Reznik A.M., Galinskaya A.A., Dekhtyarenko O.K., Nowicki D.W. Preprocessing of matrix QCM sensors data for the classification by means of neural network // Sensors and Actuators B. – 2005. – №106. – P. 158-163.

5. Резник А.М., Калина Е.А., Сычев А.С., Садовая Е.Г., Дехтяренко А.К., Галинская А.А. Многофункциональный нейрокомпьютер NeuroLand // Праці Міжнародної конференції з індуктивного моделювання (МКІМ’02). – Львів. – 2002. – С. 82-88.

6. Резник А.М., Калина Е.А., Сычев А.С., Садовая Е.Г., Дехтяренко А.К., Галинская А.А. Многофункциональный нейрокомпьютер NeuroLand // Математичні машини і системи. – 2003. – №1. – С. 36-45.

7. Дехтяренко А.К., Новицкий Д.В. Нейронная ассоциативная память с клеточной структурой // Математичні машини і системи. – 2002. – №3. – С. 37-44.

8. Дехтяренко А.К., Новицкий Д.В. Ассоциативная память на основе неполносвязных нейронных сетей // Труды VIII Всеросийской конференции “Нейрокомпьютеры и их применение” (НКП’02). – Москва. – 2002. – С. 934-941.

9. Dekhtyarenko O., Reznik A., Sitchov A. Associative Cellular Neural Networks with Adaptive Architecture // The 8th IEEE International Biannual Workshop on Cellular Neural Networks and their Application (CNNA’04). – Budapest, Hungary. – 2004. – P. 219-224.

10. Dekhtyarenko O., Tereshko V., Fyfe C. Phase transition in sparse associative neural networks // European Symposium on Artificial Neural Networks (ESANN'05). – Bruges, Belgium. – 2005. – P. 387-392.

11. Dekhtyarenko O.K., Gorodnichy D.O. High Performance Associative Neural Networks: Overview and the Library // Submitted to Canadian Conference on Artificial Intelligence 2006. – Quebec City, Canada. – 2006.

12. Reznik A.M., Dekhtyarenko O.K. Modular neural associative memory capable of storage of large amounts of data // International Joint Conference on Neural Networks (IJCNN'03). – Portland, Oregon, USA. – 2003. – P. 3031-3035.

13. Reznik A.M., Sitchov A.S., Dekhtyarenko O.K., Nowicki D.W. Associative memories with "killed" neurons: the methods of recovery // International Joint Conference on Neural Networks (IJCNN'03). – Portland, Oregon, USA. – 2003. – P. 2579-2582.

14. Nowicki D., Dekhtyarenko O. Kernel-based associative memory // International Joint Conference on Neural Networks (IJCNN'04). – Budapest, Hungary. – 2004.

15. Nowicki D., Dekhtyarenko O. Averaging on Riemannian manifolds and unsupervised learning using neural associative memory // European Symposium on Artificial Neural Networks (ESANN'05). – Bruges, Belgium. – 2005. – P. 181-186.

16. Резник А., Дехтяренко А. Модульная нейронная ассоциативная память для запоминания данных большого объема // X-th International Conference “Knowledge - Dialog - Solution” (KDS’03). – Varna, Bulgaria. – 2003. – С. 32-38.

17. O’Keefe S., Dekhtyarenko O.K. SOM-Based Sparse Binary Encoding for AURA Classifier // IEEE World Congress on Computational Intelligence (WCCI’06). – Vancouver, BC, Canada. – 2006.

18. Дехтяренко А.К. Ассоциативные клеточные нейронные сети с адаптивной архитектурой // Математичні машини і системи. – 2004. – №1. – С. 17-27.

19. Дехтяренко А.К. Метод вычисления размещения протяженных связей в нейронных ассоциативных сетях с архитектурой “тесного мира” // Математичні машини і системи. – 2005. – №2. – С. 25-32.

20. Dekhtyarenko O. Systematic Rewiring in Associative Neural Networks with Small-World Architecture // International Joint Conference on Neural Networks (IJCNN’05). – Montreal, Quebec, Canada. – 2005. – P. 1178-1181.

АНОТАЦІЯ

Дехтяренко О.К. Неповнозв’язні асоціативні нейронні мережі. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 – Системи і засоби штучного інтелекту. – Інститут проблем математичних машин і систем НАН України, Київ, 2006.

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

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

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

Ключові слова: неповнозв’язна нейронна мережа, асоціативна пам’ять, кліткова архітектура, архітектура “тісного світу”, неітеративні алгоритми навчання, псевдоінверсний алгоритм.

АННОТАЦИЯ

Дехтяренко А.К. Неполносвязные ассоциативные нейронные сети. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 – Системы и средства искусственного интеллекта. – Институт проблем математических машин и систем НАН Украины, Киев, 2006.

Диссертационная работа посвящена разработке методов построения ассоциативной памяти на базе неполносвязных нейронных сетей Хопфилда. В работе рассматриваются методы обучения сетей, которые ставят своей целью максимизацию ассоциативных качеств при условии определенных ограничений на архитектуру сети (структуру межнейронных связей).

В работе предложено и исследовано усовершенствование псевдоинверсного алгоритма обучения неполносвязных сетей, которое путем отказа от процедуры симметризации весовой матрицы позволило улучшить ассоциативные качества сети, избежать численной нестабильности алгоритма, а также расширило область применения на сети с несимметричными архитектурами. Для сетей с проекционным и псевдоинверсным алгоритмами обучения получены теоретические оценки ассоциативных качеств и характеристик весовых матриц.

Предложен метод построения сети с адаптивной архитектурой, зависящей от хранимых в памяти данных, что позволило увеличить емкость памяти сети при фиксированном числе межнейронных связей. Для сети с адаптивной архитектурой обнаружено и исследовано явление фазового перехода в ассоциативное состояние. Суть данного явления заключается в резком возникновении ассоциативных свойств сети при малых изменениях в ее архитектуре. Установлена взаимосвязь между критическими значениями параметров сети.

Для сетей с архитектурой “тесного мира” разработан метод систематического переноса связей. Использование данного метода позволяет улучшить ассоциативные качества сети при сохранении всех известных достоинств архитектурной модели “тесного мира”.

Рассмотренные в работе методы и алгоритмы построения неполносвязных ассоциативных нейронных сетей реализованы в составе программного комплекса “NeuroLand”, а также в виде алгоритмической библиотеки с открытым кодом.

Эффективность разработанных моделей продемонстрирована на примере задачи распознавания данных сенсоров запаха (система типа “Электронный нос”). Использование модульного классификатора на основе неполносвязных ассоциативных сетей позволило уменьшить вычислительную сложность процесса распознавания и требования к ресурсам памяти в 5 раз по сравнению с его полносвязным аналогом.

Ключевые слова: неполносвязная нейронная сеть, ассоциативная память, клеточная архитектура, архитектура “тесного мира”, неитеративные алгоритмы обучения, псевдоинверсный алгоритм.

ABSTRACT

Dekhtyarenko O.K. Sparse Associative Neural Networks. – Manuscript.

Ph.D. thesis for acquiring scientific degree of Candidate of Technical Sciences in the subject 05.13.23 – Systems and Tools of Artificial Intelligence. – Institute of Problems of Mathematical Machines and Systems, National Academy of Sciences of Ukraine, Kyiv, 2006.

In this thesis we study the models of associative memory based on sparsely connected Hopfield-type network. The main consideration is given to learning rules that are aiming the maximization of associative properties subject to certain architectural constraints.

An improvement of pseudoinverse learning rule is introduced and investigated for the networks with predefined architectures. This improvement eliminated the numerical instability of weights calculation and increased memory capacity of the network. Theoretical estimations of the network associative behaviour and weight matrix properties are