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

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

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

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

Теорема 1. Дана сітківка з двома станами вхідних сигналів (Так і Ні). Тоді клас елементарних перцептронів, для яких існує вирішення для будь-якої класифікації C(W) можливих середовищ W, не є порожнім.

Далі Ф. Розенблат показав і довів у теоремі 2, що необхідними, але ще не достатніми умовами існування рішення, є такі:

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

Друга умова потребує пояснення. Коефіцієнтом зміщення для А-елемента Ф. Розенблат називав відношення ${\displaystyle n_{i}^{+}/n_{i}^{-}}$ числа стимулів у навчальній вибірці, які відносяться до одного класу, і збуджують даний А — елемент, до числа стимулів, що відносяться до іншого класу, але також збуджують цей же А-елемент. Порушення другої умови робить відношення ${\displaystyle n_{i}^{+}/n_{i}^{-}}$ постійним для А-елементів, що реагують на стимули з такої підпослідовності появи стимулів на входах перцептрона. І через це, як доводиться в теоремі 2, щонайменше один зі стимулів буде класифікований неправильно.

Розенблат також показав, що цих умов буде недостатньо, на наступному прикладі:

Цей приклад задовольняє двом необхідним умовам, але з усім тим не має вирішення. Щоб отримати потрібну класифікацію для першого класу, потрібно:

• Для правильної класифікації стимулу № 1, щоб вага А-елемента № 1 була позитивною;
• Для правильної класифікації стимулу № 2, щоб вага А-елемента № 2 була позитивною;
• Для правильної класифікації стимулу № 3, щоб сума вагових коефіцієнтів А-елементів № 3 та № 4 була позитивною.

Щоб отримати потрібну класифікацію для другого класу, потрібно:

• Для правильної класифікації стимулу № 4, щоб сума вагових коефіцієнтів А-елементів № 1, № 2 і № 3 була негативною;
• Для правильної класифікації стимулу № 5, щоб сума вагових коефіцієнтів А-елементів № 1, № 2 і № 4 була негативною.

Звідси видно, що якщо вагові коефіцієнти для А-елементів № 1 і № 2 позитивні, і хоча б один з вагових коефіцієнтів для А-елементів № 3 та № 4 позитивний, то тим самим ми можемо домогтися, щоб сума ваг № 1(+), № 2(+) та № 3(-) була негативною, але в такому разі вага № 4 повинна залишатися позитивною, і тоді сума № 1(+), № 2(+) і № 4(+) ніяк не може бути від'ємною. Таким чином, або стимул № 4, або стимул № 5 будуть класифіковані неправильно. Це й називається відсутність сходження при вирішенні класифікації.

У чистому вигляді достатні умови Розенблат описує тільки пізніше в такій теоремі, запропонованій Джозефом:

Теорема 2. Дано елементарний перцептрон і класифікація C(W). Необхідна та достатня умова того, що методом корекції помилок за скінченний час і з довільного початкового стану може бути досягнуто рішення, зводиться до того, що не повинен існувати ненульовий вектор ${\displaystyle X^{**}}$, такий, що для всіх і показник зміщення ${\displaystyle b_{i}(X^{**})=0}$

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

Теорема 3. Дано елементарний перцептрон, простір стимулів W і якась класифікація C(W). Тоді для існування вирішення для C(W) необхідно і достатньо, щоб існував деякий вектор u, що лежить в тому ж ортанті, що і C(W), і деякий вектор x, такий, що Gx = u.

Але практично значимими є три наслідки з цієї теореми:

1. Якщо G-матриця перцептрона^[ru] особлива, тобто матриця, яка не має зворотної (це відбувається коли її детермінант дорівнює нулю), то може існувати деяка класифікація, яка не має рішення. У цьому випадку збіжності при навчанні перцептрона не буде.
2. Якщо число стимулів у навчальної вибірки більше числа А-елементів в елементарного перцептрона, то також існує деяка класифікація, яка не має рішення. Таким чином, визначається верхня межа числа формальних нейронів в прихованому шарі. Однак практично достатньо мати 60-80 % (і не менше 50 %) від цього числа залежно від числа класів на які потрібно класифікувати стимули.
3. Імовірність існування рішення для випадково вибраної класифікації при збільшенні числа стимулів (що безпосередньо, згідно з другим наслідком, веде до збільшення числа А-елементів) прямує до нуля. Практично це означає, що за наявності у перцептрона порядку 1000 А-елементів, ймовірність того, що його G-матриця буде особливою близька до нуля, а при збільшенні числа А-елементів така ймовірність прямує до нуля.

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

Теорема 4. Дано елементарний перцептрон, простір стимулів W і деяка класифікація C(W), для якої відомо, що рішення існує. Припустимо, що усі стимули з W з'являються в будь-якій послідовності, але за умови, що кожен стимул з'являється повторно через деякий скінченний інтервал часу. Тоді процес навчання з корекцією помилок (з квантуванням або без квантування підкріплення), що починається з довільного початкового стану, завжди приведе до досягнення рішення для C(W) протягом скінченного проміжку часу. При цьому всі вхідні сигнали до R - елементів досягнуть значення, принаймні рівного деякій довільній величині d> = 0.

У ряді наступних теорем Ф. Розенблат показує якими характеристиками повинен володіти алгоритм навчання, щоб він міг досягти рішення.

• У теоремі 5 він показує, що метод корекції помилок з випадковим знаком підкріплення, хоча і поступається методу з корекцією помилок по швидкості, але, з усім тим, може досягти рішення.
• У теоремі 6 доведено, що при S-керованому навчанні може бути отримане рішення, але воно може виявитися нестабільним. А при R-керованому навчанні взагалі не має сенсу говорити про ймовірність збіжності процесу навчання.
• У теоремі 7 показано, що метод корекції випадковими збуреннями (по суті, метод корекції без вчителя), також поступаючись за швидкістю методом з корекцією помилок, дозволяє отримати рішення за скінченний час.
• У теоремі 8 Показується, що для Гамма-перцептрона (перцептрон в якому ваги всіх активних зв'язків спершу змінюються на рівну величину, а потім з вагів всіх зв'язків віднімається інша величина, що дорівнює повній зміні ваг всіх активних зв'язків, поділеній на число всіх зв'язків) може існувати рішення, якого він досягти не зможе.

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

Для оцінки ємності пам'яті необхідної для зберігання вагових коефіцієнтів, при вирішенні навчанні предиката «парність», Мінський виходив з нижченаведених міркувань. Для будь-якого однакового подання коефіцієнтів необхідно по ${\displaystyle |R|-1}$ біт на кожен, де ${\displaystyle |R|}$ — кількість точок на сітківці перцептрона. Це випливає з того, що таким має бути вага найбільш великого коефіцієнта, щоб виконувалися умови існування рішення. Максимальна необхідна кількість коефіцієнтів буде ${\displaystyle 2^{|R|}}$. Отже, буде потрібно ${\displaystyle (|R|-1)*2^{|R|}}$ біт. Якщо порівнювати це число з тим, що вийде у разі, якщо запам'ятати всі можливі зображення, які можуть бути нанесені на сітківку перцептрона, то знадобиться ємність = ${\displaystyle |R|*2^{|R|-1}}$. За таких припущень виходить, що для вагових коефіцієнтів перцептрона ємності потрібно практично стільки ж, як для запам'ятовування всіх можливих зображень.

Для оцінки числа ітерацій, потрібних елементарному перцептрону, щоб визначити вагові коефіцієнти, Мінський проаналізував навчання предиката «парність», який є одним з найбільш теоретично складних для перцептрона. При цьому він узяв перцептрон з найменшим можливим числом А-елементів, а отже, і з найменшим числом вагових коефіцієнтів. І для цього випадку він визначив нижньою і верхньою межами числа корекцій: ${\displaystyle 5^{|R|}<n<10^{|R|}}$, де ${\displaystyle |R|}$ — кількість точок на сітківці перцептрона.

Тому критика Мінського щодо збіжності перцептрона вказує на те, що:

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

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

Тут, слід додати тільки те, що для більшості задач розпізнавання реальних зображень не потрібно знаходити такі математичні функції, а відмінні риси зображень різного класу можуть бути знайдені враховуючи лише маленьку область, яка, наприклад, складається з 20 точок з 8000 можливих. А побудувавши такі предикати від 20 елементів (предикати відповідають А-елементам) можна не враховуючи всі особливості зображення, класифікувати їх за класами з огляду на лише деякі з них (як правило число таких предикатів, як було сказано вище знаходяться в межах 60-80 % від числа всіх зображень). Це вказує на той факт, що кількість осмислених зображень в певній розмірності на кілька порядків менше, ніж число всіх можливих зображень. І якщо не вимагати виконання певної математичної функції (зсув, поворот) над такими осмисленими зображеннями, стає ясним, що перцептрон може не тільки оптимально запам'ятовувати для класифікації ряд зображень, але і працювати у певному сенсі алгоритмом стиснення зображень із втратами, і точно відносити їх до потрібного класу.

• Перцептрон
• Теорема Цибенка