Як порахувати експресивність нейрона| задача_ші #01

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

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

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

Отже, перша...

В попередній статті я писав, що нейрон інтегрує інформацію і в найпростішому випадку його можна вважати функцією (хоча й біологічний нейрон значно складніший). Функція ця параметрична y=f(x,w) (x вхід, y вихід) і змінюючи параметри (w) можна змінювати вид функції. Експресивність нейрона — це кількість функцій, що він може реалізувати. Функцію можна представити таблицею, де кількість рядків — це кількість можливих входів, кількість стовпчиків — це експресивність. Отже, давайте порахуємо для конкретного випадку.

Задача

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

Розв’язок

Скільки всього існує функцій? Класичний результат з математики: якщо треба відобразити X елементів в Y елементах, то таких способів є Y^X (“^” — степінь). В нас кількість X елементів 2^N (всі можливі бінарні вектори довжиною N), а Y елементів 2 (нейрон активний чи ні), тому кількість всіх можливих функцій:

Скільки функцій реалізує нейрон?

1.Виберемо такі ваги w, щоб серед них було рівно q одиниць і зафіксуємо їх. Тоді перебираючи всі пороги (t=0,1,2,…,N)ми отримаємо рівно q+2 функцій. +2 тому, що за t>q нейрон ніколи не активується і всі функції однакові (y=0); і потрібно врахувати випадок, коли нейрон завжди активується(t=0, y=1).

2.Всього кількість способів вибрати q одиниць серед N дорівнює С(q,N) (комбінації q з N):

Тому для фіксованої кількості одиниць у вагах маємо C(q,N)q+2 функцій. (+2 не множимо на комбінації, бо все одно для різних комбінацій маємо однакові функції (для всі x, y=0 або y=1)
3. Просумуємо всі можливі q і отримаємо відповідь.

Пізніше я випадково побачив, що можна спростити:

Хто хоче, може спробувати довести цю рівність. Бачимо, що це значно менше, ніж всі можливі функції 2^(2^N). Тому й об’єднують нейрони в мережі, щоб отримати більшу експресивність разом.

А тепер до гарного. Ці всі функції можна отримати обчислювально на комп’ютері і подивитися як вони виглядають.

Ось зображення для N=10. По вертикалі пронумеровані всі x (від 000..0 до 111…1), по горизонталі всі можливі функції. Білий відповідає одиниці, нейрон активний за цього входу (y=1), чорний нулю (y=0).

А ось анімація для різних N.

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

Я думаю, що цю задачку вирішили ще в 60–70х і розв’язок десь лежить в статтях. Але ці малюнки без комп’ютера намалювати важко. Я раніше їх не бачив і, мабуть, ще ніхто не бачив. Будете перші) А якщо десь вже були, дайте знати в коментарях.

Можна задачу трохи модифікувати і прийняти, що зв’язки можуть бути плюс-мінус один (w=-1, w=1) і поріг t може приймати від’ємні значення. Тоді експресивність буде майже вдвічі більшою. Ось малюночки. Додається права частина, що повторює ліву з інверсією.

Найбільше мені подобається випадок коли, ваги плюс мінус один, вхідні стани (x=-1 або x=1) і поріг викинути (t=0). Тут експресивність дорівнює кількості вхідних векторів (2^N), тому малюнок квадратний. Випадок для N=10 показаний в заголовку статті.

Якщо взяти ваги дискретні (w=1,2,3,…), то виявляється, що є верхня межа, вище якої дискретизація не дає нові функції. Для бінарного входу і виходу ці межі від -N до N, тобто максимум є сенс брати 2N+1 різних станів ваг (реальні ваги не дадуть більше функцій). І це максимум, що можна витиснути з цієї простої моделі.

Мотивація

Навіщо вивчати таку просту модель нейрона та ще й з дискретними вагами і станами?

Перш за все, так краще зрозуміти суть навчання. Для класифікації з вчителем є певна невідома функція f*. Вчитель показує приклади (x, y) і по них треба вгадати цю функцію або вибрати найбільш схожу. Якби вчитель показав всі 2^N прикладів(для бінарного випадку), це було б те ж саме що й він нам показав f*, і тоді треба підібрати параметри (w,t), що її реалізують, або що дають найбільш схожу функцію до f* (стовпчик в матриці експресивності). Але даних завжди мало і треба підібрати функцію, щоб і повторювала те, що вже показано і вгадувала те, що ще не показано(це називається похибка генералізації і матриця експресивності може її оцінити).

Якщо ж стоїть задача без учителя, то шукана функція f* вибирається по іншому. Наприклад, для стиснення даних потрібно вибрати таку функцію за якої нейрон активувався б в 50% випадків. Тоді його ентропія максимальна і він передає максимум інформації про x. Матриця експресивності показує як близько нейрон може наблизитися до 50%.

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

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

Це шоста стаття в блозі “Територія штучного інтелекту”.

Підписуйтеся на сторінки:
fb.com/ai.territory/
t.me/aiterritory

Читайте інші:
1.Територія штучного інтелекту. Про себе, про блог, як створити ШІ в Україні
2.Що таке інтелект?
3.Навіщо насправді потрібен штучний інтелект
4.Карта штучного інтелекту (2020)
5.Нейрон. Основні принципи роботи
6.Як порахувати експресивність нейрона| задача_ші #01
7.Принципи кодування інформації. Частина 1. Комп’ютер vs мозок
8.Принципи кодування інформації. Частина 2. SDR
9.Простий спосіб закодувати щось в нейронну мережу| задача_ші #02
10.Як сенсори формують нейронний код
11.Що таке і в чому суть інформації?
12.Скільки інформації передається в нейронних мережах. Ч.1
13.Скільки інформації передається в нейронних мережах. Ч.2
14.Кінець першої частини. Де ми so far?