Розробка програми навчання нейронної мережі на основі таблиць маршрутизації в пакеті Microsoft Excel

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

– промислові застосування систем штучного інтелекту (експертні системи);

– моделювання мозку.

Проте декілька найбільш наполегливих вчених, таких як Тейво Кохонен, Стів Гросберг, Джеймс Андерсон (James A. Anderson) продовжили дослідження. Поступово з’явився теоретичний фундамент, на основі якого сьогодні конструюються найпотужніші багатошарові мережі. Оцінка Мінскі виявилася надто песимістичною, багато з поставлених в його книзі задач розв’язуються зараз мережами за допомогою стандартних процедур.

Наприкінці 1980-х років  теорія стала застосовуватися в прикладних областях і з’явилися нові корпорації, що займалися комерційним використанням цієї технології. Наростання наукової активності носило вибуховий характер. У 1987 було проведено чотири великих наради зі штучних нейронних мереж і опубліковано понад 500 наукових статей.

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

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

Класифікація за типом вхідної  інформації:

– аналогові нейронні мережі (використовують інформацію у формі дійсних чисел);

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

Класифікація за характером навчання:

– навчання з учителем – відомі вихідні результати нейронної мережі;

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

– навчання з підкріпленням  – система призначення штрафів і заохочень від середовища.

Класифікація за характером налаштування синапсів:

– мережі з фіксованими  зв’язками (вагові коефіцієнти нейронної мережі вибираються відразу, виходячи з умов завдання, при цьому: dW / dt = 0 , де W – вагові коефіцієнти мережі);

– мережі з динамічними зв'язками (для них в процесі навчання відбувається налаштування синаптичних зв’язків, тобто dW / dt ≠ 0, де W – вагові коефіцієнти мережі).

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

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

 

 

3.2 Методи  навчання штучних нейронних мереж

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

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

– зміна елементів  матриці зв’язку (ваг);

– зміна характеристик  нейронів (виду й параметрів активаційної функції й т. д.).

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

У зв’язку з цим  штучний нейрон може бути представлений у такий спосіб (рисунок 18).

Рисунок 18 – Модель штучного нейрона.

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

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

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

Сьогодні існує велика кількість алгоритмів навчання. Приведу найбільш відомі з них.

1) Правило навчання Гебба (корелятивне, співвідносне навчання).

Більшість сучасних алгоритмів навчання виросло із правила Гебба. Наприкінці 40-х років XX ст. років Д. О. Гебб теоретично встановив, що асоціативна пам’ять у біологічних системах викликається процесами, що змінюють зв’язки між нервовими клітинами. Відповідно до установленого їм правила, що називається «правилом Гебба», при одночасній активації (порушенні) двох нейронів синаптична сила (вага їхнього зв’язку) зростає. Таким чином, часто використовувані зв’язки в мережі підсилюються, що пояснює феномен звички й навчання повторенням.

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

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

2) Дельта-правило.

Це важливе правило  навчання було запропоновано Б. Уідроу й М. Е. Гоффом і найбільше відповідає одношаровим ШНМ прямого поширення. Ідея його полягає в тому, що якщо під час навчання мережі можна встановити розбіжність між її бажаною й наявною реакціями, ця розбіжність може бути усунута або зменшена шляхом зміни певним чином вагових коефіцієнтів зв’язку.

3) Розширене дельта-правило.

Розширене дельта-правило, на відміну від простого, знаходить застосування у багатошарових ШНМ прямого поширення другого порядку.

4) Конкурентне навчання.

У цьому виді навчання всі нейрони одного шару є конкуруючими, а перевага віддається тому нейрону, що найбільш сильно реагує на вхідний (дратівний) сигнал, тобто настроюються ваги тільки одного нейрона – нейрона-переможця (winner-takes-all).

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

5) Стохастичне навчання.

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

Стохастичні методи навчання базуються на псевдовипадкових змінах ваг зі збереженням тих змін, які ведуть до поліпшень. Для корекції ваг використовується деяка імовірнісна функція. Більші первинні і випадкові корекції зі збереженням певних змін ваг поступово зменшують, досягаючи при цьому мети навчання. Це нагадує процес відпалювання металу, коли атоми розплавленого металу, які перебувають у хаотичному русі при його поступовому охолодженні, гублячи енергію, досягають нижчого з можливих енергетичних станів (глобального мінімуму). Тому для опису цього виду навчання часто використовують термін «імітація відпалювання» (simulated annealing).

Таке стохастичне  навчання використовується в машинах Больцмана й Коші.

6) Градієнтні методи навчання.

Багато методів навчання засновано на мінімізації деякої цільової (вартісної, енергетичної й  т. д.) функції І, що являє собою звичайно деяку опуклу функцію. Якщо використовувані функції активації диференційовані, зручно застосовувати градієнтні методи мінімізації.

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

Градієнтні методи застосовуються також і для навчання стохастичних нейронів.

7) Навчання з підкріплюванням.

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

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

 

3.3 Розробка програми навчання нейронної мережі на основі таблиць маршрутизації в пакеті Microsoft Excel

Навчання нейронної  мережі буду проводити за методом  «Дельта-правило» запропонованого  Б. Уідроу й М. Е. Гоффом.

На рисунку 19 зображений граф мережі.

Рисунок 19 – Граф мережі.

Ребра графа неорієнтовані та мають певні вагові коефіцієнти, які я приведу до діапазону [0..1]:

; ;

; ; ;

; ;

Шляхи між вузлами  я розділю на прямі та зворотні. Прямі вузли (наприклад, від вузла 1 до вузла 2, або від вузла 3 до вузла 5 та ін.) будуть мати вхідний сигнал 1, а зворотні вузли (наприклад, від  вузла 2 до вузла 1, або ж від вузла 5 до вузла 3) будуть мати вхідний сигнал -1.

Для прикладу знайдемо оптимальний шлях між віддаленими  вузлами мережі, для графу заданого на рисунку 19, найбільш віддаленим є шлях від вузла 1 до вузла 5.

Визначимо всі можливі  шляхи між вузлами 1 та 5:

;

;

;

;

;

;

Перейдемо до навчання нейронної мережі (рисунок 20).

Рисунок 20 – Навчання нейронної мережі в Microsoft Excel.

Функція значить, що навчання нейронна пройшло успішно.

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

ВИСНОВКИ

При виконанні завдань курсової роботи були розглянуті та виконані наступні розділи:

1) Розробка системи підтримки прийняття рішень (СППР) для проектування комп’ютерної мережі.

Система підтримки прийняття  рішень, СППР, система підтримки  прийняття рішень, DSS – комп’ютерна автоматизована система, метою якої є допомога людям, що приймають рішення в складних умовах для повного і об'єктивного аналізу предметної діяльності.

2) Розрахунок оптимального маршруту.

В якості розрахунку оптимального маршруту був використаний матричний алгоритм пошуку найменших шляхів.

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

3) Розробка нейромережного алгоритму.

В даному розділі основною задачею була розробка програми навчання нейронної мережі на основі таблиць маршрутизації. В якості алгоритму навчання був використаний метод «Дельта-правило» запропонований вченими Б. Уідроу й М. Е. Гоффом.

Головним є те, що «Дельта-правило» модифікує ваги відповідно до необхідного і дійсними значеннями виходу кожної полярності як для безперервних, так і для бінарних входів і виходів. Ці властивості відкрили безліч нових додатків.

В процесі розрахунків  були використанні та більш детально освоєні програми:

– Microsoft Excel 2013;

– Matlab R2012a.

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

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Князєва Н.О. Князєва  О.А. Теорія проектування комп’ютерних  систем і мереж Ч 1. Основи  системного підходу до проектування  – Одеса: «ВМВ», 2008.-212с.

2. Князєва Н.О. Теорія  проектування комп’ютерних систем  і мереж Ч 2. Методи аналізу  і синтезу комп’ютерних мереж  – Одеса: СПД Бровкін О.В., 2012.-240с.

3. Осовский С.  Нейронные сети для обработки информации / Пер. с польского И. Д. Рудинского. – М.: Финансы и статистика, 2002. – 344 с.: ил.