Програмне забезпечення інтелектуальних систем:Іспит

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Програмне забезпечення інтелектуальних систем:Проект

Зміст

1 I триместр
2 II триместр
3 Література
4 Дивіться також

I триместр

Паралельна реалізація генетичного алгоритму

Алгоритм відпалу й оптимізаційна задача

Роєвий інтелект. Оптимізація часток роєм і модифікації алгоритму.
Еволюційне програмування
Генетичне програмування
Простий генетичний алгоритм. Теорема схем
Паралельна реалізація. Генетичні алгоритми
Алгоритм відпалу й оптимізаційна задача
Генетичні алгоритми в задачах багатокритерійної оптимізації
Генетичні алгоритми. Застосування ніш та видів
Генетичні алгоритми у комбінаторних задачах

---

Інтелект

Чіткого визначення інтелекту немає/

Інтелект - вміння логічно мислити, концепція, яка не піддається чіткому визначенню.

Інтелект - біологічна адаптація до життєвих обставин.

Поділяється на:

теоретичний

практичний

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

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

Штучний інтелект

Поділяється:

Сильний ШІ - програмні засоби, за допомогою яких машина здатна думати як людина

Слабкий ШІ - це широкий діапазон технологій, які можуть додаватись до наявних систем та додавати їм різні "розумні" властивості

Еволюційні алгоритми

Механізм Дарвіна (1):

спадковість
змінюваність
відбір

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

Основні властивості:

1. Обробляються закодовані значення параметрів

2. пошук розв'язку задачі здійснюється не з 1 точки, а з множини - популяції точок

3. будь-яка особина характеризується рівнем пристосованості.

Оптимізація функції пристосованості

4. Пошук особин з високою пристосованістю здійснюється на основі механізмів Дарвіна (1)

4 Напрями еволюційних алгоритмів:

Генетичні алгоритми - призначені для оптимізації функції дискретних змінних, акцент на рекомбінації геномів
Еволюційне програмування - оріоєнтоване на оптимізацію неперервних функцій без використання рекомбінації
Еволюційна стратегія - еволюційне програмування з використанням рекомбінації
Генетичне програмування - використовує еволюційний метод для оптимізації комп'ютерних програм

Простий генетичний алгоритм

0: двійкове кодування послідовностей фіксованої довжини

1: Початкова популяція |P|=n

2: Ітерація

2.1: $\forall x: f(x) \ge 0, max f(x)$ Якщо виконується умова зупинки, то переходимо на крок 3

2.1.2: Генерується популяція батьків |P|=n, для відбору використовується метод "рулетки": $P(x)=\frac{f(x)}{\Sigma f(x)}$ - кожна хромосома відбирається в батьківський пул з ймовірністю функції пристосованості.

$n=N \frac{f(x_j)}{x}$ -очікувана кількість копій в батьківському пулі

2.2:

2.2.1: кросинговер

P з використанням одноточкового кросинговера

Точка схрещування випадково з [1; l-1]. Кожна пара обмінюється частинами з ймовірністю P_c

2.2.2: З P енеруємо P шляхом застосування щільнісної мутації з ймовірністю P_m

Параметри алгоритму P_c, P_m:

0,5 ≤ P_c ≤ 1
0 ≤ P_m ≤ 0,1

2.2.3: Перейти на 2.1.1

3: Заверешення роботи, вибір найкращої хромосоми

Генетичні алгоритми з використанням ніш та видів

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

Використовується для відбору не тільки функція пристосованості, а й розподіл особин в просторі пошуку.

$S (d i j)$ - функція співучасті. Функція визначає рівень близькості та степінь співучасті для кожної хромосоми в популяції.

$d i j$ - міра відстані між хромосомами $x i$ та $x j$ (може бути введена у просторы генутипу та фенутипу)

$d_{ij}=\sqrt[2]{x}{\sum_{k=1}^{P}\frac{(x_i^k-x_j^k)}{(x_{max}^k-x_{min}^k)^2}}$ - у просторі фенотипу

$x_i: x_i^1 x_i^2 \dots x_i^p$ - хромосома що кодує p-параметрів

Умови, що накладаються на функцію співучасті:

$\forall d_{ij}: 0 \le S(d_{ij}) \le 1$
S(0)=1
$\lim_{d_{ij} \to \infty}(S(d_{ij}))=0$

Вводять ще параметр σ-розмір ніші та покладають $\forall d_{ij} > \sigma: S(d_{ij})=0$

Приклад функції співучасті:

$S(d_{ij}= \begin{cases} 1-(\frac{d_{ij}}{\sigma})^{\omega}, d_{ij}<\sigma \\ 0 \end{cases}$

σ, ω - const
$\sigma=\frac{1}{2} \frac{1}{\sqrt[2]{q}}$ , q = кількість локальних оптимумів, w=1

$f_s(x_j)= \begin{cases} f(x_j), \forall i: S(d_{ij})=0 \\ \frac{f(x_j)}{\sum_{i=1}^{n}S(d_{ij}), \exist i: S(d_{ij}) \ne 0} \end{cases}$

Генетичні алгоритми для багатокритеріальної оптимізації

$\begin{cases} y_k=f_k(x) \to max\\ k=1 \dots m, m>1\\ x \in X \in R \end{cases} x, x' \in R^n$

Визначення1 (домінування Парето)

Вектор x' домінується в смислі Парето з x:

$x {}^p > x' <=> \forall i=\overline{1, n} | x_i \ge x_i' and \exist j: x_j>x_j'$

$(13246) p > (12246)$

$(2489) p > (1379)$

Визначення 2

Розв'язок х' домінується в смислі Парето з x

$x {}^p > x' <=> \forall i=\overline{1, m} f_i(x) \ge f_i(x') and \exist j: f_j(x)>f_j(x')$

Визначення 3

Розв'язок x називається парето-оптимальним (оптимальним в смислі Парето) якщо він не домінується жодним іншим розв'язком.

Приклади

$f_1(x,y)=x \to max$

$f_2(x,y)=y \to max$

Методи критеріальної оптимізації:

1) Метод зваженої функції

2) Метод послідовних поступок - критерії ранжуються, шукається max по f₁

3) Метод послідовних обмежень:

$f'=(f_1' \dots f_m')$ - ідеальний вектор

Далі шукаємо максимум зваженої суми. Якщо кожний критерій сильно відрізняється від суми, то ми будемо шукати суму з певними обмеженнями на k.

4)метод одночасних обмежень

5) Генетичні алгоритми

Популяція розбивається на m- підпопуляцій однакового розміру.

Кожна підпопуляція відповідає за свою функцію пристосованості.

Селекція проводиться автономно для кожної групи.

Кросинговер виконується між групами.

Генетичні алгоритми - застосування

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

Способи паралельної реалізацій генетичного алгоритму

Типи паралельних ГА.

1) ПГА1 - параметри ГА на основі популяції (глобальні ГА)

Ці алгоритми використовують модель фермер-робітник

2) ПГА2 - ГА на основі підпопуляції (острівна модель)

Переваги:

1) Ймовірність зупинки в локальному оптимумі є меншою

2) середовище острівного типу є більш захищеним від збоїв

Параметри ПГА2:

обмеження на мінімальний розмір популяції
степінь обміну індивідумами
структура міграції індивідумів між популяціями (кожен з кожним - зірка)

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

Топологія зв'язків між популяціями:

1)кільце

2)повний граф

3) суміжна топологія

2а) ПГА2 - гібридний підхід:

розпаралелення на підпопуляції. Кожна підпопуляція розпаралелюється на основі глобльного підходу.

3)ПГА3 - на основі індивідів (дифузійна модель)

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

Генетичне програмування

Схема, як в Генетичному Алгоритмі

0) Кодування вводяться множини термінальних і функціональних змінних T-термінальні, F-функціональні

T={проблемно-орієнтовні константи}
F={елементарні функції}

кожна програма є композицією функцій із F та T. Множини F і T задовольняють властивості замкненості.

1) Кодування геномів у вигляді дерев:

внутрішні вузли - функціональні змінні
листя - термінальні символи

приклад: T={2,x,4,7}, F={+, *, /}

2) Ініціалізація:

Дві стратегії побудови програм:

метод росту - з однаковою ймовірністю весь час обираються функціональні і термінальні символи - доки серед листків є функціональні символи
метод повноти (повне бінарне дерево) - листки в самому кінці і бінарно розташовані
при побудові використовуються 10% термінальних символів і 90% нетермінальних символів - щоби запобігти термінальності дерева

3) Оцінювання - функція оцінюванння залежить від близкості значень особини і бажаних значень.

Береться середньокавдратична похибка: $f(x)=\sqrt{\frac{1}{N-1}\sum_{i=1}^N(y_i-t_i)^2}$

N - розмір вибірки
y_i - експерементальні дані
t_i - дані, обраховані програмою

4) Оцінювання - генетичні оператори

Основний генетичний оператор - кросинговер

Кросинговер - батьки обмінюються піддеревами

при побудові використовуються 10% термінальних символів і 90% нетермінальних символів - щоби запобігти термінальності дерева. Оператор кросинговеру дерева з самим собою дає новий результат. Поява та накопичення ІНТРОНІВ - ділянок коду, що нічого не роблять.

5) Умова завершення:

межа популяції
задоволення похибки

Параметри алгоритму:

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

Еволюційне програмування

Пошук розв"язків не на рівні фенотипу, а на генотипу.

Використовується лише оператор мутації

Схема алгоритму:

0) Кодування

1) Ініціалізація

1.1) Оцінка для мутації

2) Моделювання еволюційного процесу (репродукція)

2.1) Застосування генетичних операторів (рекомбінація)

2.2)Оцінювання

2.3) Відбір

2.4)Перехід на пункт 2.1

3) Завершення роботи.

Всі члени популяції можуть брати участь у породженні нащадків:

F:Rⁿ -> R

Теорема схем

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

У випадку бінарного кодування схемою є рядок довжини l.

{0, 1, *}

10**1

10001

10011

10101

10111

Хромомсома належить до даної схеми, якщо для $\forall j \in \overline{1,l}$ символ, що перебуває в j-ій позиції

хромосоми відповідає символу, що міститься в j-ій позиції

хромосоми відповідає символу, що міститься в j-ій позиції схеми.

Порядок схеми - кількість визначених бітів у схемі

O(10**1)=3

O(**01**11)=4

O(*****)=0

O=l-m(*)

Визначальна довжина схеми - відстань між крайніми визначеними бітами схеми

σ(10**1)=4

σ(**01**11)=5

σ(**1**)=0

Пристосованість схеми - це середнє значення пристосованості хромосом що міститься в ній:

$f(H)=\frac{\sum_{x \in \tilde{m}(H)}f(x)}{m(H)}$

$|\tilde{m}(H)|=m(H)$

Схема з високою пристосованістю короткою визначальною довжиною та низьким порядком має більше шансів перейти з покоління в покоління і називається корисною (за Холландом)

m(H, t) - кількість прикладів схеми H у поколінні t
$P(H)\frac{f(H)}{\sum_{i=1}^n f(x_i)}=m(H,t) \frac{f(H)}{\overline{f}}$ - ймовірність схеми бути обраною
$p_c \cdot \frac{\sigma (H)}{l-1}$ - ймовірність що кросинговер зруйнує схему
$1 - P m + O (H)$ - ймовірність того,що мутація не зруйнує схему

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

$f(H)=\overline{f} \cdot (1+c)$

m (H, t)(1 + c)

Алгоритми ніш та видів і генетичний алгоритм у комбінаторних задачах

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

Для відбору використовується не тільки функція пристосованості, а й розподіл особин в просторі пошуку.

S(d_ij)- функція співучасті - функція визначає рівень близькості на степінь співучасті для кожної хромосоми в популяції.

d_ij - міра відстані між хромосомами x_i та xd_j (може бути введена у просторі генотипу та фенотипу)

$d_{ij}=\sqrt{\sum_{k=1}^{p}\frac{(x_i^k-x_j^k)}{(x_{max}^k-x_{min}^k)^2}}$ - у просторі фенотипу

x_i: x_i¹, x_i², ..., x_i^p (i-та хромосома що кодує p параметрів)

Умови, що накладаються на функцію співучасті:

1) $\forall d_{ij}, 0 \le S(d_{ij}) \le 1$

2)

S (0) = 1

3) $\lim_{d_{ij} \to \infty}S(d_{ij})=0$

Вводять ще параметр σ - розмір ніші та накладають $\forall d_{ij} > \sigma , S(d_{ij})=0$

дописати: Picture 64

Алгоритм відпалу й оптимізаційна задача

Алгоритм відпалу

Основою процесу є керування графіком охолодження

Завжди тримаємо поточний та робочий розв'язки.

Схема:

1. Створити початковий розв'язок

T=const(100), N- кількість ітерацій при заданій температурі

2. Скопіювати початковий розв'язок в поточний розв'язок

3. Оцінити поточний розв'язок

4. u:=0

5. Скопіювати поточний розв'язок в робочий розв'язок

6. Змінити робочий розв'язок випадковим чином

7. Оцінити новий розв'язок

8. Якщо робочий розв'язок кращий за поточний, то скопіювати робочий розв'язок в поточний і перейти на крок 10. Інакше перейти на крок 9.

9. Критерій допуску на крок 5.

10. Якщо u<N, то n++, перейти на крок 5, інакше на крок 11.

11. Зменшення Т, перейти на крок 4.

T_i+1=αT_i, 0<α<1, 0,8 ≤ α ≤ 0,99

Оцінка розв'язку складається з декодування розв'язку та зведені до мінімуму енергетичної функції (виражає відхилення розв'язку від шуканого)

E_{робочий} < E_{поточний} - приймаємо поточний за робочий
$P(\Delta E)=e^{-\frac{\Delta E}{T}}$ - ймовірність прийняття поганого розв'язку.
$Δ E$ = E_{робочий} - E_{поточний} > 0

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

Оптимізація часток роєм

PSO (particle swarm optimization)

Агенти розпорошуються в просторі.

Схема алгоритму

0) Кодування розв'язків.

1) Ініціалізація.

2) Ітераційний процес для кожної частки:

2.1) Обчислення функції здоров'я та модифікіція локального та голобального найкращих розв'язків.

2.2) Обчислення вектора швидкості.

2.3) Обчислення нової позиції.

2.4) перехід на пункт 2.1.

3.) Завершення роботи

$X_i=(x_{i1}, x_{i2}, \dots, x_{iN})$ - точка в N-вимірному просторі
$V_i=(v_{i1}, v_{i2}, \dots, v_{iN})$ - вектор швидкості
$P_i=(p_{i1}, p_{i2}, \dots, p_{iN})$ - локальний найкращий розв'язок

$G=(g_1, g_2, \dots, g_N)$ - глобальний найкращий розв'язок (max p_i)

1. Координати генеруються випадковим чином (x-рівномірно, v=0)

$f(x_i) > f(p_i) \Rightarrow p_i:=x_i$

$f(x_i) > f(G) \Rightarrow G:=x_i$

: $V_{m_i}^{new}=V_{m_i}^{old} + \Gamma_1 \times r_1(p_{m_i}-x_{m_i}^{old})+ \Gamma_2 \times r_2(g-x_{m_i}^{old})$

$r 1, r 2$ - незалежны випадковы величини рівномірно розподілені в [0, 1]
$Γ 1,Γ 2$ - навчальні множини

Γ 1

- когнітивний параметр (контролює вплив пізнавальної компоненти)

Γ 2

- соціальний параметр (вплив соціальної компоненти)

$\Gamma_1, \Gamma_2 \approx 2$

$X_{m_i}^{new}=V_{m_i}^{old} +V_{m_i}^{new})$

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

Модифікація алгоритму

(стохастичність вносить невизначеність, r1, r2 випадкові)

1) $| V_{m_i} | < V_{max}$

2) обмежена множина допустимих розв'язків.

- підхід поглинають стіни

- якщо частка дійшла φ межі, то її швидкість обнуляється = підхід відштовхують стіни

- підхід поглинають стіни

3) введення інерційної ваги

$V_{m_i}^{new}=w \cdot V_{m_i}^{old} + \Gamma_1 \cdot r_1(p_{m_i-x_{m_i}^{old}}) +\Gamma_2 \cdot r_2 (g_i -x_{m_i}^{old})$

4) введення стискаючого множника

5) $V_{m_i}^{new}=V_{m_i}^{old} + \Gamma_1 \cdot r_1(p_{m_i-x_{m_i}^{old}}) +\Gamma_2 \cdot r_2 (g_i -x_{m_i}^{old}) + \Gamma_3 \cdot r_3 (p_{l_i}-x_{m_i}^{old})$

$p_{l_i}$ - найкращий сусід

6) бінарний варіант алгоритму

простір розв'язків кодується бінарними значеннями

Значення V max так само, як і в звичайному.

$S(V_{m_i})=\frac{1}{1+e^{-V_{m_i}}}$

$x_{m_i}=1$ .

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

Роєвий алгоритм

Взаємодія між індивідами

Ройовий інтелект - методи ШІ в основу яких покладено вивчення колективної поведінки в децентралізованій системі.

Приклад - Алгоритм Мурашки

Алгоритм бджілки

Для знаходження глобального оптимуму

Бджоли-розвідники (scout)
робітники (employee)
спостеріагчі (onlooker)

Параметри алгоритму:

n- кількість розвідників
m- кількість ділянок, обраних з n штук
e- кількість найкращих ділянок
nep- кількість бджіл на найкращих ділянках
m-e- кількість непоганих ділянок
usp - кількість бджіл на непоганих ділянках
ngh- радіус ділянки (окіл кожної ділянки)

nep та usp бджіл досліджують окіл усіх найкращих ділянок

Еволюційна стратегія

Пристосування особин на рівні фенотипу

швидкість еволюції
еволюційне вікно
крок мутації

Схема алгоритму як і в еволюційному програмуванні.

c=(op,cp)

op=(o₁, o₂, ..., o_m) - параметри об"єму

sp=(s₁, s₂, ..., s_m)

Оператори кросинговеру:

1. Однорыдний, в якосты батьків беруться 2 фіксовані особини, іноді n- по кількості параметрів.

2. Проміжний

Мутація

Генетичне програмування

Особина кодує програму

Основна відмінність - оцінка здоров'я. Треба запустити програму

Треба за виходом (y) та входом (x) відновити F(x)

0 Кодування

Кожна хромосома кодує програму.

Вводяться множини термінальних символів Т та функціональних символів F

Т складається з проблемно-орієнтовних змінних, констант або директив

F складається з елементарних функцій, які використовують інші термінальні функції.

Кожна комп'ютерна програма є композиційною функцією з множини F та терміналів з Т

Множини F та Т повинні задовольняти властивості замкненості

Є декілька видів кодування геномів - лінійне, деревовидне.

Кодування геномів у вигляді дерев

Внутрішні вузли - функціональні символи, листки -термінальні символи

T={2,x,y,4,7}

F={+,*,%}

Зображення:Genetic programming $2+\frac{4*x}{7}$

1 Ініціалізація

Корінь - з множини F
Листя - з множини T

Правила побудови:

1. Правило росту - з однаковою ймовірністю обираються функціональні та термінальні символи, доти доки серед листків є хоча б один функціональний

2. Правило повноти - наперед визначена висота дерева. Весь час обирають функціональні символи, лише на нижньому рівні обирають термінальні символи.

2 Оцінювання

Для оцінювання розв'язку береться середньоквадратична похибка

$f_i=\sqrt{\frac{1}{N-1}\sum_{k=1}^{n}(y_i-t_i)^2}$

N -розмір тестової вибірки
y_i - експерементальні дані
t_i - обраховані дані

3 Генетичні оператори

Основний генетичний оператор - кросинговер

Випадковим чином обирається піддерева (2ох) батьків і відбувається обмін піддеревами

В результаті можлива зміна висоти дерева (довжина хромосоми змінюється)

Особливостікросинговера:

1) дерево саме з собою => отримуємо інше дерево

2) зміна довжини хромосоми

3) щоб запобігти постійному обміну термінальними символами, в якості піддерев брати 10%-терміналів, а 90%-функціональних символів

4) Поява та нокопичення інтронів - ділянок коду, які нічого не роблять (тільки впливають на довжину хромосоми)

$A_i(t+1) \sim A_i(t) \cdot \frac{\Phi(a_i)}{\Phi(t)} \cdot (1-p_i \cdot f \frac{c_l}{c_a} \cdot \frac{a_i}{a_1})$

Мутація -видаляє випадково обране піддерево і замінює його іншим, або просто замінюється листок

p_m << 1

4 Завершення

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

Параметри алгоритму

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

II триместр

Метод групового урахування аргументів

f - елементарний класифікатор

1) f - лінійна функція:

f(x₁, x₂)=a₀ + a₁x₁ + a₂x₂

2) f - лінійна з коваріяціями функція

f(x₁, x₂)=a₀ + a₁x₁ + a₂x₂ + a₃x₁x₂

3) f - квадратична функція

f(x₁, x₂)=a₀ + a₁x₁ + a₁x₂ + a₁x₁x₂ + a₁x₁²+a₅x₂²

4) f - дробно-поліномільна функція $f(x_1, x_2)=\frac{a_0+a_1x_1+ a_2x_1x_2+a_1x_1^2}{1+ b_1x_1+b_2x_2+ b_1x_1x_2}$

Кінематична модель самовідтворення

(Фон-Нейман)

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

Фон Нейман запропонував 8 видів елементарних частин:

1) імпульсний орган

2) орган співпадіння

3) гальмівний орган

4) джерело імпульсів

5) елементи жорсткості

6) орган, що скріплює

7) орган, що розділяє

8) м'язи

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

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

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

Мета Штучного Життя - розробити універсальну теорію життя

Кріс Лантон - сильне штучне життя (ШЖ, створення людиною нових форм)

Сильне Штучне Життя - розглядає створення істоти як реалізацію життя, слабке ШЖ розглядає створення істоти як моделювання життя.

Основні напрями:

1) Еволюційні алгоритми

2) Синтез ... про поведінку

3) Штучна хімія

4) Нейронні мережі

Еволюційна кібернетика

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

Основні методи дослідження:

математичне та комп"ютерне моделювання
експерименти

Галузі дослідження еволюційної кібернетики:

Еволюційна кібернетика:

- еволюційне моделювання:

- моделі виникнення молекулярно-генетичних інформаційних та кібернетичних систем

- прикладне еволюційне моделювання

- загальні моделі еволюції

- моделювання інтелектуальних винаходів біологічної еволюції

Еволюційне моделювання

Моделі виникли дослідженням як в процесі походження життя виникли найпростіші молекулярно-генетичні інформаційної системи та перші кібернетичні системи. Вчені: Крік, Андерсен, Ейген.

Модель квазівидів (Ейген 1971) - еволюція популяції популяції ланцюжків РНК.

В результаті формується квазівидів - розподіл ланцюжків РНК в околі оптимальної РНК.

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

Модель Сайзерів (Ратнер, Шанін 1980) макромолекул системи взаємодіючих полінуклеотидних ланцюжків та ферментів.

Квазівиди -> гіперцикли -> сайзери -> протоклітини ->найпростіші організми.

Загальні моделі еволюції:

Еволюційна генетика систем та моделі загальної кібернетики закономірності біологічної еволюції.

Теорія популяційної генетики

Еволюція - динамічний процес зміни в часі розподілу частот генів в популяції.

Теорія нейтральної еволюції (1985, Кімура)

Мутації на молекулярному рівні є переважно нейтральними або слабко невигідними.

Теорія НК-автоматів (Кавфи 1991)

Розглядається автомати з ще складною з множини випадкових зв"язних елементів. Окремий автомат - модель молекулярно-генетичної системи керування живої клітини.

Модель квазівидів

ТРНК - транспортні РНК
МНРНК - матричні РНК (інформація)
РРНК - рибосомні РНК

Білки - органічна речовина в складі клітини полімери

Ланцюжки РНК здатні до самовідтворення. Розмноження РНК - копіювання спадкової інформації

При копіюванні можливі помилки - мутації.

Нехай окрема особина (ланцюжок РНК) задається своїм генотипом.

S_k

{S₁,S₂, ..., S_n} - популяція.

S_k - ланцюжок із N символів S_k₁,S_k₂, ..., S_{k_N}

n, N - const, досить великі S_{k_i} обираються з алфавіту A, |A|= ν

f(s) ≥ 0 пристосованість

1) n >> ν^N

Евол. розглядається як детермінований процес. Динаміка популяції описується:

а) в неперервному випадку системою диф. рівнянь.

б) в дискретному сист. різнощевих рівнянь

2) ν^N >> n

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

Модель квазівидів - аналіз еволюції ланцюжків.

Розглянемо 1ий випадок.

В неперервному часі. При переході від покоління до покоління чисельність видів змінюється несуттєво, покоління перекриваються. Для побудови сист. диф. рівнянь з"ясуємо необхідні умови для селекцій та евол. поведінки. Пропонуються такі:

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

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

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

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

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

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

$\frac {\partial x_k}{\partial t} = (A_k Q_k -D_k) \cdot x_k + \sum_l \phi_{k_l} x_l + \Phi_k$ ,

де: $(A_k Q_k -D_k) \cdot x_k$ - метаболізми

k - індекс, що помічає всі розрзізнювані молекулярних одиниць, що самовідтворюються.
x_k -чисельність особини k-го виду
$A k Q k x k$ - спонтанне утворення макромолекул
$D k x k$ - спонтанний розпад
$A k$ - функія, яка включає концентрацію високоенергетичного будівельного матеріалу.

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

$Q k$ - фактор якості 0 < Q_k < 1, задає ту долю репродукції, яка відбувається з утворенням точної копії k-молекули.

Клітинна модель самовідтворення. Конфігурація райського саду

Клітинна або стільнико-подібна структура визначається як п'ятірка:

(N, T, S, q₀, f)

N - додатнє ціле, розмір простору
T - власне стільники, розбиття n-вимірного евклідового простору на комірки
S - скінченна множина станів

Кожна комірка - це n-вимірний одиничний куб з цілочисловими координатами центру

q₀ - стан спокою
f - функція, яка відображає множину ставнів комірки та її сусідів в момент часу t-1 у стан комірки в момент t

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

Функція f має бути однаковою для всіх комірок на площині. Функція повинна бути такою, що якщо всі комірки в часі t-1 знаходяться в стані спокою, то сама комірка переходить в стан спокою в момент t

В початковий момент часу t₀ всі комірки, за виключенням скінченної кількості, перебувають в стані спокою.

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

Конфігурація або стан блоку - це функція, яка ставить у відповідність кожній комірці певний стан.

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

Конфігурація - це машина, здатна сама себе відтворювати

Комірка відповідає одній з елементарних моделей, з яких будують машину

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

Конфігурація С* містить n-копій конфігурацій С, якщо у блока С* існує n-підмножин, що не перетинаються, кожна з яких є копією блоку С.

Конфігурація райського саду

Конфігурація райського саду - конфігурація, яка існує тільки в момент часу t=0

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

Жодна конфігурація, яка містить конфігурацію райського саду не буде здатна до самовідтворенння

Спін-стекольна модель

Для інтерпритації фазових станів у фізиці.

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

S-система спінів

S₁, S₂, ..., S_N

N>>1

$S_i \in {-1; 1}$

Взаємодії між спінами є випадковими. Енергія системи визначається:

$E (S) = - Σ J i j S i S j$

$i,j = \overline{1, N}$

$J i j$ - елементи матриці взаємодії між спінами

Інтелектуальні винаходи

Моделювання інтелектуальних винаходів біологічної еволюції

Основна проблема - чому людська логіка може застосуватись до пізнання природи?

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

Ця теорія повинна містити:

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

2) моделі еволюції переходів як інтелектуальними винаходами різних рівнів.

Розташування моделей виникли ключових винаходів біологічної еволюції.

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

Причина - перехід з нижніх рівнів на верхні. Додатковий механізм керування об"єднані підсистемами С . Кожен перехыд об"єднується в підсистему S_i.

В результаті метасистем переходів форм. S_i- система нового рівня.

$S' = C + Σ i S i$

Штучні нейронні мережі

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

Основні труднощі при використанні нейронних мереж: 1. Непередбачувана поведінка 2. Логічна непрозорість

Елементами штучних нейронних мереж є:

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

Функція стану S є правилом комбінуваннявхідних сигналів.

$net_j=S(a_{j1}, ..., a_{jn})=\sum_{k=1}^{n}a_{jk}+\Theta_j=\sum_{k=1}^{n}D(w_{jk}, \hat{x}_{jk})+\Theta_j$

$Θ j$ - зсув або поріг

1) лінійне правило комбінування вхідних сигналів $a_{jk}=D(w_{jk}, \hat{x}_{jk})=w_{jk}\sum_{i \in I_{jk}}x_{jki}$

$net_{j}=\sum_{i=1}^{n}+\Theta_j=\sum_{k=1}^{n}w_{jk}\sum_{i \in I_{jk}} + \Theta_j$

$I j k$ - множина елементів, що беруть участь в утворенні k-го з"єднання j-го нейрона

$| I j k i | = 1$

$net_j=\sum_{k=1}^n a_{jk} + \Theta_j = \sum_{k=1}^n D(w_{jk}, x_{jk})$ = \sum_{k=1}^n w_{jk}x_{jk}+\Theta_j

Нейронні елементи з лінійним правилом називаються сигма-елементами

2)полілінійне правило $net_j=\sum_k w_{jk} \cdot \prod_{i \in I_{jki}}+\Theta_j$

$\Sigma=\prod$ - елементи з такою ж функцією стану

3)дендритне перетворення задається як відстань між вектором входів та вектором ваги входів

$net_j=\sum_k^n a_{jk}= \sum_{k=1}^n ||w_{jk}-x_{jk}||$

$| w j k - x j k | = Δ$

$net_j=\sqrt{\sum_{k=1}^n(w_{jk}-x_{jk})^2}$

Функція активації (виходу)

Як правило є неспадною

Мережа утворюється шляхом з"єднання виходів нейронів з їхніми входами. Структуру зв"язку задають у вигляді графу міжнейронних з"єднань або матриці вагових коефіцієнтів, де $w j k$ - вага зв"язку між і-тим та j-тим елеметами.

-|1 2 3

1|0 1 4 2|-2 0 1,1 3|0,8 0 0

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

Класифікація штучних нейронних мереж

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

За топологією

1) мережі прямого поширення - вихідний сигнал елемента в майбутньому не може повернутися на його вхід

шарові мережі - нейрони розміщуються в декілька шарів

2) мережі зворотнього поширення (рекурентні мережі) - є зворотні зв"язки (вихідний сигнал може в майбутньому повернутися на вхід).

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

шарово-циклічні мережі - шари замкнені в кільце

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

повнов"язно-шарові

За апроксимацією до вирішення заданої задачі

1) мережі що конструюються

2) мережі що навчаються

2.1) ті, що спостерігаються (supervised)

2.2)ті, що не спостерігаються (неконтрольоване навчання)

2.3)гібридні (змішані)

Приклад нейронної мережі, що моделює відношення XOR

$F(net)= \begin{cases} \\1, net>0 \\0, net \le 0 \end{cases}$

net₃=0*(-1)+1(-1)+1,5=0,5
net₄=0*(-1)+1*(-1)+0,5=-0,5

F(net₅)=1

F(net₄)=0

net₅=0*(-1)+1*1+(-0,5)=-0,5

F(net₅)=1

Проектування штучних нейронних мереж

1. Модель

2. Архітектура

3. дані для навчання

3.1 Дані мають бути повними

3.2 Дані мають бути узгодженими

3.3 Надлишковість даних

процедурами контрастування називаються процедури аналізу значущості та скорочення опису які виділяють найбільш важливі параметри та зв"язки в мережі

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

4. Попередня обробка вхідних та інтерпретація вихідних даних

4.1 масштабування

$y=\frac{0,9-0,1}{x_{max}-x_{min}}\cdot x + (0,9 - \frac{0,9 - 0,1}{x_{max}-x_{min}})\cdot(0,1 \cdot 0,9), x \in [2,20]$

4.2 нормування та центрування (при різному розподілі ознак).

$X^{P}, p=\overline{1,M}$
$x_i=\frac{x_i-M(x_i)}{G(x_i)}=$
$M(x_i)=\frac{1}{M}\sum_p x_i^P$
$G(x_i)=\sqrt{\frac{1}{M}\sum_p(x_i^p-M(x_i))^2}$

або

$x_i=\frac{x_i-M(x_i)}{\underset{max}{p}(x_i^p-M(x_i))}$

4.3 перетворення вихідного сигналу

$y=\frac{a+b}{2}+\frac{b-a}{2}x$

Теоретичні можливості штучних нейронних мереж

Наслідок з теореми Стоуна:

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

Перцептрон

обчислювальні можливості

Елементарний перцептрон є нейроелементом з n- входами, лінійною функцією стану і пороговою функцією активації

За допомогою елементарного перцептрона можна конструювати базові логічні функції:

диз"юнкція
заперечення

В багатьох випадках дозволяє проводити бінарну класифікацію

маса > 0,8 AND швидкість < 0,55 - бомбардувальник
маса < 0,9 AND швидкість > 0,25 - винищувач

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

Навчання елементарного перцептрона

Властивість синапса змінюється пропорційно добутку перед- та постсинаптичної активності:

$Δ w i j = η x i y j$ - правило Хеба
$η$ -коефіцієнт норми начання від 0 до 1 керує середньою величиною зміни коефіцієнтів
$Δ w i j$ - величина, на яку змінюється вага
$x i$ - сигнал від і-того нейрону
$y i$ - бажана величина активації

Алгоритм Відроу-Хоупфа, дельта-правило

$Δ w i j = η x i σ j + σ j = y j - o j$

o_j - реальний вихід

1. Ініціювати вагові коефіцієнти невеликими випадковими величинами від -1 до 1

2. Взяти вектор х з навчальної вибірки

3. Розрахувати вихід перцептрона

4. якщо $y_j \ne o_j$ , провести корекцію вагових коефіцієнтів за дельта-правилом

Теорема Розенблата про процедурну збіжність перцептрона

Розенблат довів теорему процедурної збіжності перцептрона:

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

$E j$ - середньоквадратична похибка на j-му вхідному зв"язку

$E_j=\frac{1}{2}(y_j-o_j)^2$

o_j =	∑	x_iw_ij
	i

$\frac{\partial E_j}{\partial w_{ij}}= \frac{\partial E_j}{\partial \nu_j} = -(y_j-o_j) \cdot x_i$

$\partial \nu_j = \frac{1}{2}\cdot 2(y_j-o_j)(-1)=-(y_j-o_j)$

Алгоритм зворотнього поширення (error back propagation)

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

$\frac{1}{1-e^x}$ - сигмоїдна
$\frac{1-e^x}{1+e^x}$ - тангенс-гіперболічна

Епохою називається повний цикл розгляду всіх наявних прикладів

Умова закінчення навчання:

1) середньоквадратична помилка при переході від епохи до епохи стає меншою за наперед-задану

2) для кожного зразка, якщо вихід лежить в заданому діапазоні (відхил від цільового виходу)

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

Алгоритм

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

1. Взяти черговий вектор з навчальної вибірки

2. Розрахувати вихідний вектор

$net_j = w_{oj}+ \sum_{i=1}^{n}w_{ij}\cdot x_i$
$o_j=f(net_j)= \begin{cases} \\ \frac{1}{1+e}net_j \\ th(net_j) \end{cases}$ - логістична та гіперболічний тангенс

3. Якщо різниця між цільовим вихідним зразком та реальним виходом мережі не потрапляє в допустимі границі, повертається на п.4 Інакше на пункт 7

4. Для кожного нейронного елементу вихідного шару розрахувати помилку

$\sigma=(y_j-o_j)\cdot f'(net_j)$
$\sigma=(y_j-o_j)\cdot o_j(1-o_j)$ - для логістичної

o j (1 - o j) = f'(n e t j)

$\sigma_i=(y_j-o_j)\cdot (1-o_j^2)$

5. Для кожного елементу схованого шару обчислюється помилка:

$\sigma_j=f'(net) \cdot \sum_k \sigma_k w_{jk}$
$f_i=o_j(1-o_j) \cdot \sum_k f_k w_{jk}$

6. Для всіх шарів оновити значення вагових коефіцієнтів кожного зв"язку

$Δ w i j = ησ j o i$
$0,01 < η < 1$

7. Якщо не пройшли всю вибірку - на 1 крок

8. Якщо виконується критерій закінчення - завершення, інакше на крок 1

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

1. Введеня інертного члена

$Δ w i j (n + 1) = ησ j o j + αΔ w i j (n)$
$w i j (n + 1) = w i j (n) + Δ w i j (n + 1)$

2. Згладжування

$w i j (n + 1) = (1 - α)σ j o i + αΔ w i j (n)$
$w i j (n + 1) = w i j (n) + ηΔ w i j (n + 1)$
α приблизно дорівнює 1 і з часом зменшується до 0

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

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

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

Приклади:

метод відпалу
метод Коші

Недоліки алгоритму зворотнього поширення помилки

Основний недолік - невизначено тривалий термін навчання може ніколи не навчитись

1) параліч мережі - величина вагових коефіцієнтів стає дуже великою

$n e t j$ - може стати великим, значення похідної буде дуже малим

Щоб запобігти паралічу мережі використовуються різні евристики

1. ініціалізація вагових коефіцієнтів малими випадковими значеннями

2. обмеження діапазону зміни вагових коефіцієнтів

3. рандомізація ваг тих нейронів що опинилися в стані насичення

$w_{ij}^{new}=\frac{-5+10}{1+e^{-\frac{w_{ij}}{S}}}, (-5; 5)$

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

Стани в які може потрапляти ШНМ - параліч, локальний мінімум

Основний недолік - невизначено тривалий термін навчання може ніколи не навчитись

1) параліч мережі - величина вагових коефіцієнтів стає дуже великою

$n e t j$ - може стати великим, значення похідної буде дуже малим

Щоб запобігти паралічу мережі використовуються різні евристики

1. ініціалізація вагових коефіцієнтів малими випадковими значеннями

2. обмеження діапазону зміни вагових коефіцієнтів

3. рандомізація ваг тих нейронів що опинилися в стані насичення

$w_{ij}^{new}=\frac{-5+10}{1+e^{-\frac{w_{ij}}{S}}}, (-5; 5)$

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

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

1. Введеня інертного члена

$Δ w i j (n + 1) = ησ j o j + αΔ w i j (n)$
$w i j (n + 1) = w i j (n) + Δ w i j (n + 1)$

2. Згладжування

$w i j (n + 1) = (1 - α)σ j o i + αΔ w i j (n)$
$w i j (n + 1) = w i j (n) + ηΔ w i j (n + 1)$
α приблизно дорівнює 1 і з часом зменшується до 0

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

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

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

Приклади:

метод відпалу
метод Коші

Мережі з радіальними базисними функціями

Є представником класу мереж прямого поширення.

Мотивуються математичними проблемами апроксимації.

В найпростішому випадку 3 шари:

1. Вхідний - кількість елементів шару дорівнює розмірності

вхідного простору ознак. Кожен нейрон першого шару зв'язується з усіма нейронами наступного шару.

2. Схований (радіальний) - функція стану визначає відсань вхідного вектора від вагових коефіцієнтів:

$net_j = \sum_{i=1}^n(w_{ij}-x_{i})$
$\sum_{i=1}^n(w_{ij}-x_{i})^2$

Функція активації є функцією з локалною поведінкою (відрізняється від о на обмеженій ділянці)

$f(x, a, \sigma) = e^{-\frac{(x-a)^2}{\sigma^2}}$

$f(x)-\frac{sin(x)}{x}$

3. Вихідний - утворюється сигма-елементами з лінійною функцією активації.

Задача апроксимації функції з використанням мереж RBF

$F(x)=\Sigma_{k=1}^{n} x_k f_k(x)$

Недолік - наявність провалів

$f_j= e^{-\frac{\Sigma(x_i-w_{ij})^2}{\sigma^2}}=\prod e^{\frac{(x_i - w_k)^2}{\sigma^2}}$

Перевага - швидкість навчання

Недоліки:

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

Ймовірнісні нейронні мережі

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

Для цього, для кожного зразка навчальна вибірка будується формула Гауса

Архітектура мережі

Вхідний шар - кількість вхідних елементів розмірності простору ознак
Шар зразків = кількість елементів = кількість навчальних зразків

$\phi = e^{\frac{net_j}{\sigma^2}}$

$net_j = \sum_{i=1}^{n}(x_i - w_{ij})^2$

Вагові коефіцієнти встановлюються рівними коефіцієнтами вектору зразка.

Шар підсумовування = кількість елементів = кількість класів (клас A/B)

Зв'язки йдуть тільки від тих елементів, які належать відповідному класу

Вагові коефіцієнти = 1

Елемент підсумовує значення входу шару зразків.

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

Відповідний елемент є класом, до якого належить вхідний зразок.

Скорочена ймовірнісна нейронна мережа

Спрямована на знаходження кількості елементів вхідного шару.

Поле впливу нейрона - це точки багатовимірного просору, які лежать з центром

Δ w i j

і радіусом

f (σ)

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

Переваги та недоліки ймовірнісної нейронної мережі

Перевага:

1. швидко навчається

2. допускає наявність помилкових даних

3. дає корисні результати навіть при малій навчальній вибірці

Недолік:

1. Ресурсоємність

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

Рекурентні мережі

Твердження:

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

Для навчання рекурентної мережі можна скористатися алгоритмами зворотнього поширення помилки (певні модифікації).

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

Треба враховувати $Δ w$ різні, а мережа функцій та ж, то береться середнє значення $Δ w$

Мережа Хопфілда

Є авто-асоціативною.

Пам'ять називається автоасоціативною, якщо пара зразків, що асоціюються, утворюються однаковими зразками.

Інтерасоціативною, якщо різними.

Мережа Хопфілда є автоасоціативною, вона може розпізнати зразок за його спотвореною версією.

Гетероасоціативна є прикладом ВАМ.

Архітектура

1. Має один шар нейронів, кожен найрон зв'язується з усіма іншими, але не з самим собою, входи та виходи нейронів є бінарними (як і 0 та 1, так і +1 та -1)

2. Нейрон має пам'ять, запам'ятовує що він перед цим посилає на вихід.

$net_j=\sum_{i}^{n}f_i w_{ij}$

f i w i j

- локальна пам'ять.

$f(net_j)= \begin{cases} +1, net_j>0\\ -1, net_j<0 \end{cases}$

$f j = f (n e t j)$

Якщо вхід =0, то нейрон видає те й що було на вихід перед цим.

Мережа X не має вхідних елементів, вхідний вектор визначає початкові значення активності елементів.

Як працює мережа:

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

Мережа Хопфілда відноситься до тих мереж, що конструюються.

Вагова матриця, яка відповідає за збереження x:

$W' = x \cdot x^T$

$W = W' - E$ - матриця вагових коефіцієнтів

$\begin{cases} 0, 1=k\\ x_i x_n, i \ne k \end{cases}$

Cтійкість мережі

Для стійкої мережі послідовні (вихід - на вхід) ітерації приводять до все меншої зміни виходу, доки вихід не є постійним.

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

Поняття стійкості та нестійкості стосується рекурентних мереж

Мережа Хопфілда є стійкою.

Умова стійкості мережі

Рекурентна мережа є стійкою, якщо її матриця є симетричною та має 0-лі на головній діагоналі.

Доведення

Треба взяти функцію f, яка спадає

Для мережі Хопфілда, функція енергії:

$E=-\frac{1}{2} \sum_j \sum_i s_j s_i w_{ij}$ - схожа на спін-стекольна модель еволюції

ΔE = − Δs_j	∑	s_iw_ij
	i

, якщо $s j$ змінює свій стан.

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

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

Кластеризація

Використовується для задач кластеризації

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

Алгоритм кластеризації

1. вхідний шар: множина векторів ознак (кількість елементів розмірності ознак вхідного простору)

2. вихідний шар: вихідні елементи шару - кластерні елементи; шар, елементи є прототипами кластерів (множина кластерів, до якого кластеру відноситься вихід)

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

Самоорганізована карта Ознака Кохоненна (SOFM)

Самонавчання

Використовується для задач кластеризації

Мережа Кохоннена

Має 2 шари:

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

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

Найчастіше використовується двовимірний простір.

Вихідний шар можна розглянути як двовимірну решітку.

Властивість мережі Коханана:

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

Околом нейрона називається множина нейронів, які знаходяться всередині кола, заданого радіуса з центром в цьому елементі.

Алгоритм навчання мережі Кохоннена

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

1. Ініціювати вагові значення випадковими малими значеннями елементами.

2. Надати мереж новий вхідний сигнал (навчальний вектор x)

3. Для кожного кластерного елемента вирахувати відстань до навчального елемента:

$d_j = \sum_{i=1}^{n} (w_{ij} - x_i)^2$
$w i j$ - вагові значення
j - номер елементу кластеру
$x i$ - i-та координата вхідного вектору

4. Знайти елемент-переможець j^*, який розташований найближче до вхідного елементу (min d_j)

5. для елементів з кола заданого радіусу з центром в елементі j^* нормувати вагові коефіцієнти.

$w i j (n + 1) = w i j (n) + η(n)(x i - w i j (n)),0 < η < 1$ - пряма навчання

6. Якщо необхідно оновити значення радіусу та норми навчання

7. Перейти на крок 2

Алгоритм закінчує роботу коли всі зміни вагових коефіцієнтів є дуже малими.

Норма навчання з часом, від 1 до 0.

Коханен рекомендував: 1000 ітерацій - норма близько одиниці.

Потім поступово зменшувати, наприклад до 0,1. І на цьому значенні прокрутити близько 1000 ітерацій.

Радіус дуже великими, щоб оновлювалися всі елементи.

Далі радіус зменшується протягом 1000 ітерацій. А потім залишити рівним 1 або 0.

Кількість ітерацій - 10 тисяч -100 тисяч.

Кількість епох - як мінімум в 500 раз більше за кількість векторів які розбиваються на класи.

Модифікації мережі

(алгоритм навчання)

в центр класу

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

Для позбавлення цього:

1. метод опуклої комбінації

Вхідні нормальні вектори подаються перетвореню:

$x_i= \alpha(n)x_i + (1-\alpha(n))\frac{1}{\sqrt{N}}$

α - коефіцієнт, що змінюється від 0 до 1.
N - розмірність вектора

Вагові коефіцієнти під час ініціалізації = $\frac{1}{\sqrt{N}}$

2. До вхідних векторів додається якийсь мінімум - цей метод дуже повільний

3. Кожному нейрону надається "відчуття справедливості"

Б. $w i j (n + 1) = w i j (n) + η(n)(x i - w i j (n)),0 < η < 1$ - пряма навчання

6. Якщо необхідно оновити значення радіусу та норми навчання

7. Перейти на крок 2

Алгоритм закінчує роботу коли всі зміни вагових коефіцієнтів є дуже малими.

Норма навчання з часом, від 1 до 0.

Коханен рекомендував: 1000 ітерацій - норма близько одиниці.

Потім поступово зменшувати, наприклад до 0,1. І на цьому значенні прокрутити близько 1000 ітерацій.

Радіус дуже великими, щоб оновлювалися всі елементи.

Далі радіус зменшується протягом 1000 ітерацій. А потім залишити рівним 1 або 0.

Кількість ітерацій - 10 тисяч -100 тисяч.

Кількість епох - як мінімум в 500 раз більше за кількість векторів які розбиваються на класи.

Б.

По різному визначається кут між векторми.

Якщо як Евклідів простір - то a ближчий до p1
Якщо як кут то a ближчий до p2
Якщо по cos кута, то перемагають той, у кого максимальний cos(j).

Оновлення відбувається за такою формулою:

$w_j(n+1)=\frac{w_j(n)+ \eta x_j}{|| w(n)+ \eta x_i ||}$ Перетворення мережі:

Перевага мережі: здатна функціонувати в умовах перешкод
Недолік: кількість кластерів повинно бути зазначено заздалегідь (повинні їх знати)

Література

Дивіться також

Досліждення проблем розпізнавання образів‎

Програмне забезпечення інтелектуальних систем:Іспит

Матеріал з USIC Wiki

Зміст

I триместр

Інтелект

Штучний інтелект

Еволюційні алгоритми

Простий генетичний алгоритм

Генетичні алгоритми з використанням ніш та видів

Генетичні алгоритми для багатокритеріальної оптимізації

Генетичні алгоритми - застосування

Способи паралельної реалізацій генетичного алгоритму

Генетичне програмування

Еволюційне програмування

Теорема схем

Алгоритми ніш та видів і генетичний алгоритм у комбінаторних задачах

Алгоритм відпалу й оптимізаційна задача

Алгоритм відпалу

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

Оптимізація часток роєм

Модифікація алгоритму

Роєвий алгоритм

Алгоритм бджілки

Еволюційна стратегія

Генетичне програмування

II триместр

Метод групового урахування аргументів

Кінематична модель самовідтворення

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

Еволюційна кібернетика

Модель квазівидів

Клітинна модель самовідтворення. Конфігурація райського саду

Конфігурація райського саду

Спін-стекольна модель

Інтелектуальні винаходи

Штучні нейронні мережі

Функція активації (виходу)

Класифікація штучних нейронних мереж

За топологією

За апроксимацією до вирішення заданої задачі

Проектування штучних нейронних мереж

Теоретичні можливості штучних нейронних мереж

Перцептрон

Навчання елементарного перцептрона

Алгоритм Відроу-Хоупфа, дельта-правило

Теорема Розенблата про процедурну збіжність перцептрона

Алгоритм зворотнього поширення (error back propagation)

Алгоритм

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

Недоліки алгоритму зворотнього поширення помилки

Стани в які може потрапляти ШНМ - параліч, локальний мінімум

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

Мережі з радіальними базисними функціями

Задача апроксимації функції з використанням мереж RBF

Ймовірнісні нейронні мережі

Архітектура мережі

Скорочена ймовірнісна нейронна мережа

Переваги та недоліки ймовірнісної нейронної мережі

Рекурентні мережі

Мережа Хопфілда

Архітектура

Cтійкість мережі

Умова стійкості мережі

Кластеризація

Самоорганізована карта Ознака Кохоненна (SOFM)

Мережа Кохоннена

Алгоритм навчання мережі Кохоннена

Модифікації мережі

Література

Дивіться також

Перегляди

Особисті інструменти

Навігація

Пошук

Інструменти