Методичні вказівки до виконання та оформлення курсової роботи з дисципліни Основи проектування інтелектуальних систем, СДУ

Методичні вказівки до виконання та оформлення курсової роботи з дисципліни Основи проектування інтелектуальних систем

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

ТЕМА КУРСОВОЇ РОБОТИ

Розроблення інформаційного та програмного забезпечення системи прийняття рішень, що навчається

1. Мета виконання курсової роботи

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

2. Опис базового інформаційно-екстремального алгоритму навчання системи

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

Розглянемо етапи реалізації алгоритму:

1. Формування бінарної навчальної матриці , елементи якої дорівнюють

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

де r_m - рівень селекції координат вектора .

3. Розбиття множини еталонних векторів на пари найближчих ²сусідів²: =<x_m , x_l >, де x_l - еталонний вектор сусіднього класу , здійснюється за таким алгоритмом:

а) структурується множина еталонних векторів, починаючи з вектора x₁ базового класу , який характеризує найбільшу функціональну ефективність СПР;

б) будується матриця кодових відстаней між еталонними векторами розмірності M ´M;

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

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

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

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

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

На рис. 1 наведено структурну схему базового алгоритму навчання LEARNING. Тут показано такі вхідні дані: {Y[J,I,K]} - масив навчальних вибірок,  - змінна кількості випробувань, де NM -мінімальний обсяг репрезентативної навчальної вибірки, I= - змінна кількості ознак розпізнавання, K= - змінна кількості класів розпізнавання; {NDK[I]}, {VDK[I]}-масиви нижніх і верхніх контрольних допусків на ознаки відповідно. Результатом реалізації алгоритму є: {DOPT[K]}-цілий масив оптимальних значень радіусів контейнерів класів розпізнавання у кодовій відстані Хеммінга; {EV[K]}-масив еталонних двійкових векторів класів розпізнавання; {EM[K]}-дійсний масив максимальних значень інформаційного КФЕ процесу навчання; {D1[K]}, {A[K]}, {B[K]}, {D2[K]} - дійсні масиви оцінок екстремальних значень точнісних характеристик процесу навчання для відповідних класів розпізнавання: перша достовірність, помилки першого та другого роду і друга достовірність відповідно. Змінна D є робочою змінною кроків навчання, на яких послідовно збільшується значення радіуса контейнера.

У структурній схемі алгоритму (рис. 1) блок 3 формує масив навчальних двійкових вибірок {X[J,I,K]} шляхом порівняння значень елементів масиву {Y[J,I,K]} з відповідними контрольними допусками за правилом (2.4.1.1) і формує масив еталонних двійкових векторів {EV[K]} шляхом статистичного усереднення стовпців масиву {X[J,I,K]} за правилом (2.4.1.2) при відповідному рівні селекції, який за замовчуванням дорівнює .

Блок 4 здійснює розбиття множини еталонних векторів на пари “найближчих сусідів”. Блок 11 обчислює на кожному кроці навчання значення інформаційного КФЕ. При невиконанні умови блока порівняння 12 блок 13 оцінює належність поточного значення критерію  робочій області  визначення його функції і при позитивному рішенні блока 13 це значення запам’ятовується блоком 14. При негативному рішенні блока порівняння 15, в якому величина  дорівнює кодовій відстані між парою сусідніх еталонних векторів, блок 16 здійснює у робочій області  пошук глобального максимуму КФЕ – EM[K] і визначає для нього екстремальне значення радіуса гіперсфери – DOPT[K]. Аналогічно будуються оптимальні контейнери для інших класів.

Рисунок 1- Структурна схема базового алгоритму навчання

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

3. Критерії функціональної ефективності навчання СПР

3.1. Ентропійний КФЕ

Для оцінки функціональної ефективності СПР широко використовуються ентропійні інформаційні критерії. Наприклад, за Шенноном такий нормований критерій має вигляд

де - апріорна (безумовна) ентропія:

апостеріорна умовна ентропія, яка характеризує залишкову невизначеність після прийняття рішень:

де  – апріорна ймовірність прийняття гіпотези g_l; p(m_m/g_l) – апостеріорна ймовірність появи події m_m за умови прийняття гіпотези ; М– число альтернативних гіпотез.

На практиці при оцінюванні функціональної ефективності СК, що навчається, можуть мати місце такі допущення:

• рішення є двоальтернативним (М=2);

• оскільки здатна навчатися СК слабо формалізованим процесом функціонує за умови невизначеності, то за принципом Бернуллі-Лапласа виправдано прийняття рівноймовірних гіпотез.

Тоді критерій (3.1.1) з урахуванням виразів (3.1.2) і (3.1.3) набирає такий частинний вигляд:

При двоальтернативному рішенні (M=2) за основну беремо гіпотезу g₁ про знаходження значення ознаки розпізнавання, що контролюється, в полі допусків d і як альтернативну їй - гіпотезу g₂. При цьому мають місце чотири можливих результати оцінки виміру ознаки (рис. 2), які характеризуються наступними ймовірностями – точнісними характеристиками: помилка першого роду –  (рис. 2а); помилка другого роду –  (рис. 2б); перша достовірність –  (рис. 2в) і друга достовірність –  (рис. 2г), де x, z - виміряне та дійсне значення ознаки розпізнавання відповідно.

Розіб’ємо множину значень ознак на області  та . Область  включає значення, що знаходяться в допуску , а – не в допуску. Тоді можна записати  

Рисунок 2 - Можливі результати оцінки виміру ознак розпізнавання при М=2

Виразимо апостеріорні ймовірності  через апріорні за формулою Байєса: 

та, прийнявши p(m₁)=p(m₂)=0,5, отримаємо:

Після підстановки (3.1.5) в (3.1.4) отримаємо формулу для обчислення КФЕ за Шенноном:

3.2. Інформаційна міра Кульбака

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

де , – гіпотези про належність контейнеру  реалізацій відповідно до класів  і

При допущенні, що , загальна міра Кульбака остаточно набуває вигляду

Нормовану модифікацію критерію Кульбака можна подати у вигляді

де – значення критерію при  і  для формули (3.2.1).

Нормування критеріїв оптимізації є доцільним при порівняльному аналізі результатів досліджень і при оцінці ступеня близькості реальної СПР до потенційної. 

3.3. Обчислення інформаційного КФЕ

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

Оскільки інформаційний критерій є мірою різноманітності не менше ніж двох об¢єктів, то для його обчислення потрібна навчальна матриця, яка складається із векторів-реалізацій двох класів:  і  Нехай клас  є основним, тобто найбільш бажаним для ОПР. Тоді належність вектора-реалізації із навчальної матриці класу  береться за основну гіпотезу g₁, а неналежність – за альтернативну гіпотезу g₂. Алгоритм зчитування навчальної матриці може бути побудовано двома способами. За першим способом послідовно зчитуються реалізації , а потім – реалізації . За іншим способом при кожному випробуванні обробляються реалізації обох класів.

Розглянемо обчислення модифікації ентропійного інформаційного КФЕ за Шенноном для двоальтернативного рішення при рівноймовірних гіпотезах згідно з формулою (3.1.2). Оскільки інформаційний критерій є функціоналом від точнісних характеристик, то при обмеженому обсязі навчальних вибірок слід користуватися їх оцінками

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

Після підстановки відповідних позначень (3.3.1) в (3.1.6), отримаємо робочу формулу для обчислення ентропійного КФЕ навчання СПР розпізнаванню реалізацій класу  для двоальтернативного рішення і при рівноймовірних гіпотезах:

Структурну схему алгоритму обчислення критерію (3.3.2) за паралельним способом оброблення навчальної матриці в процесі побудови у радіальному базисі оптимального контейнера класу  подано на рис. 3. Тут наведено такі вхідні дані: Х1, Х2 - еталонні двійкові вектори класів  і  відповідно;  – навчальна матриця, яка складається з реалізацій цих класів; N= , де NM - обсяг репрезентативної навчальної вибірки; D – радіус контейнера класу. 

Рисунок 3 – Структурна схема обчислення інформаційного КФЕ

Вихідні дані: Е – значення КФЕ; А, В, D1, D2 - значення точнісних характеристик процесу навчання СПР: помилки першого і другого родів, перша і друга достовірності відповідно. За схемою, що розглядається, блок 5 обчислює при кожному випробуванні кодову відстань D(N) шляхом складання за модулем два вектори Х1 з поточним вектором-реалізацією X(N) і підрахунку кількості одиниць в одержаній сумі.

При кожному непарному випробуванні визначається відстань D(N) між вектором Х1 і реалізацією свого класу, а на кожному парному - між вектором Х1 і реалізацією іншого класу. Обчислення коефіцієнтів К1, К2, К3 і К4 здійснюється за таким алгоритмом (блоки 6 – 12):

а) порівняння (блок 6): якщо D(N) £ D (реалізація належить області класу ), то при непарному випробуванні обчислюється К1:=К1+1 (²своя² реалізація), а при парному - К3:=К3+1 (²чужа² реалізація). Визначення парності або непарності реалізацій здійснюють блоки 7 і 8, які перевіряють виконання умови N/2=F, де F – ціле число. Якщо умова виконується, то випробування парне, інакше - непарне. Якщо D(N)>D (реалізація не належить області класу ), то при непарному випробуванні обчислюється коефіцієнт К2:=К2+1 (²своя² реалізація), а при парному – К4:=К4+1 (²чужа² реалізація);

б) порівняння (блок 13): якщо N=NM , то обчислюються оцінки точнісних характеристик за (4.2.3.1), інакше обробляється наступна реалізація;

в) при виконанні умови блока 15: (D1>0,5 і D2>0,5) обчислюється інформаційний критерій, наприклад, за формулою (4.2.1.6), інакше видається повідомлення «КФЕ не визначено».

Знання точнісних характеристик процесу навчання дозволяє визначати робочу область значень КФЕ. Виходячи із вимоги практичної цінності рішень, які приймаються СПР, на робочу область визначення функції інформаційного КФЕ необхідно вводити обмеження знизу. Так, для двоальтернативного рішення такими обмеженнями є: D₁>0,5 і D₂>0,5, тобто значення першої та другої достовірностей у робочій області не можуть бути менше значень відповідних помилок.

Після відповідної підстановки (3..3.1) у (3.2.1) отримаємо робочу формулу для обчислення міри Кульбака:

де r - число цифр у мантисі значення критерію. 

4. Опис алгоритму екзамену

На рис. 4 показано структурну схему алгоритму екзамену для нечіткого розбиття простору ознак розпізнавання, яке має місце у загальному випадку. Алгоритм має такі вхідні дані: - масив еталонних двійкових векторів: -змінна числа класів розпізнавання; - цілий масив оптимальних радіусів контейнерів класів розпізнавання у кодовій відстані Хеммінга;  - двійкова реалізація образу, що розпізнається.

Рисунок 4– Структурна схема алгоритму екзамену:

Виходом алгоритму є повідомлення про належність реалізації, що розпізнається, деякому класу  із сформованого на етапі навчання алфавіту класів . На рис.4 блок 5 обчислює, починаючи з базового класу, кодову відстань  між поточним еталонним вектором і реалізацією ХР. Блок 6 для кожного класу обчислює значення функції належності , яка для гіперсферичного класифікатора має вигляд

Після виходу із циклу блок 8 визначає клас, до якого належить реалізація ХР за максимальним значенням функції належності (4..1). 

5. ВИКОНАННЯ КУРСОВОЇ РОБОТИ

5.1. Завдання на курсову роботу

Розробити та програмно реалізувати базовий алгоритм навчання системи за критерієм Шеннона для двох класів розпізнавання (табл. 1: варіант 7). 

5.2. Результати, одержані при виконанні курсової роботи

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

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

5.3. Вимоги до оформлення курсової роботи

Оформити пояснювальну записку (приблизний обсяг до 20 сторінок на форматі А4, шрифт TNR, міжрядковий інтервал 1,5) відповідно до існуючого стандарту СумДУ для оформлення курсових і дипломних робіт.

Мова програмування за вибором студента.

Пояснювальна записка повинна мати таку структуру:

Титульний аркуш;

Зміст;

Вступ;

1. Основні положення методу.

2. Математична (категорійна) модель.

3. Критерій оптимізації.

4. Опис алгоритму навчання.

5. Коротка характеристика програми.

6. Результати моделювання на ЕОМ.

Висновки.

Список літератури.

Додаток. Текст програми.

З повагою ІЦ "KURSOVIKS"!