Даний приклад задовольняє двом необхідним умовам, але тим не менш не має рішення. Щоб отримати потрібну класифікацію для першого класу, потрібно:
- Для правильної класифікації стимулу № 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 будуть класифіковані неправильно. Це і називається відсутність сходження при вирішенні класифікації.
У чистому вигляді достатні умови Розенблатт описує тільки пізніше в наступній теоремі, запропонованої Джозефом:
Теорема 9.
Дано елементарний перцептрон і класифікація C (W). Необхідна і достатня умова того, що методом корекції помилок за кінцевий час і з довільного початкового стану може бути досягнуто рішення, зводиться до того, що не повинно існувати ненульового вектора X * *>. такого, що для всіх и показник зміщення b i (X * *) = 0 (X ^) = 0>
але так як це математичне уявлення, хоча і більш елегантне, але тим не менше мало що говорять про те які потрібно виконати умови в термінах архітектури перцептрона, Розенблатт перш доводить наступну теорему:
Теорема 3.
Дано елементарний перцептрон, простір стимулів W і якась класифікація C (W). Тоді для існування рішення для C (W) необхідно і достатньо, щоб існувала певна вектор u, що лежить в тому ж ортанте, що і C (W), і деякий вектор x, такий, що Gx = u.
Але практично значущими є три слідства з цієї теореми:
- Якщо G - матриця перцептрону особлива, тобто матриця, яка не має зворотної (це відбувається коли її детермінант дорівнює нулю), то може існувати деяка класифікація, яка не має рішення. В цьому випадку збіжності при навчанні перцептрона не буде.
- Якщо число стимулів в навчальній вибірці більше числа А-елементів в елементарному перцептроном, то також існує деяка класифікація, яка не має рішення. Таким чином, визначається верхня межа числа формальних нейронів в прихованому шарі. Однак практично досить мати 60-80% (і не менше 50%) від цього числа в залежності від числа класів на які потрібно класифікувати стимули.
- Можливість існування рішення для випадково вибраної класифікації при збільшенні числа стимулів (що безпосередньо, згідно з другим слідству, веде до збільшення числа А-елементів) прагне до нуля. Практично це означає, що при наявності у перцептрону близько 1000 А-елементів, ймовірність того, що його G-матриця буде особливою близька до нуля, а при збільшенні числа А-елементів така ймовірність прагне до нуля.
Основна теорема збіжності Правити
В основній теоремі збіжності Ф. Розенблатт показує, що існуючі можливі рішення можуть бути досягнуті саме при застосуванні алгоритму навчання з корекцією помилки:
Теорема 4.
Дано елементарний перцептрон, простір стимулів W і деяка класифікація C (W), для якої відомо, що рішення існує. Припустимо, що всі стимули з W з'являються в будь-якій послідовності, але за умови, що кожен стимул з'являється повторно через деякий кінцевий інтервал часу. Тоді процес навчання з корекцією помилок (з квантуванням або без квантування підкріплення), що починається з довільного початкового стану, завжди приведе до досягнення рішення для C (W) протягом кінцевого проміжку часу. При цьому всі вхідні сигнали до R - елементам досягнуто значення, принаймні рівного деякої довільної величиною d> = 0.
Додаткові теореми збіжності Правити
У ряді наступних теорем Ф. Розенблатт показує, якими характеристиками повинен володіти алгоритм навчання, щоб він міг досягти рішення.
- У теоремі 5 він показує, що метод корекції помилок з випадковим знаком підкріплення, хоча і поступається методу з корекцією помилок по швидкості, але, тим не менш, може досягти рішення.
- У теоремі 6 доведено, що при S-керованому навчанні може бути отримано рішення, але воно може виявитися нестійким. А при R-керованому навчанні взагалі не має сенсу говорити про ймовірність збіжності процесу навчання.
- У теоремі 7 показано, що метод корекції випадковими збуреннями (по суті, метод корекції без вчителя), також поступаючись по швидкості методу з корекцією помилок, дозволяє отримати рішення за кінцеве час.
- У теоремі 8 показується, що для гамма-перцептрону (перцептрон в якому ваги всіх активних зв'язків спочатку змінюються на рівну величину, а потім з ваг всіх зв'язків віднімається інша величина, що дорівнює повній зміні ваг всіх активних зв'язків, поділеній на число всіх зв'язків) може існувати рішення, якого він досягти не зможе.
Не існує кінцевого автомата, що виконував функцію множення двох двійкових чисел a і b довільної розрядності
Марвін Мінський навів ряд своїх доказів теореми збіжності перцептрона. Але його докази дозволили судити про величину вагових коефіцієнтів, що істотно для зберігання їх в пам'яті комп'ютера, а також про кількість необхідних корекцій вагових коефіцієнтів, що важливо при оцінці швидкості навчання перцептрона.
Для оцінки ємності пам'яті необхідної для зберігання вагових коефіцієнтів, при вирішенні навчанні предикату «парність», Мінський виходив з нижченаведених міркувань. Для будь-якого однакового подання коефіцієнтів необхідно по | R | - 1 біт на кожен, де | R | - число точок на сітківці перцептрона. Це випливає з того, що таким повинен бути вага найбільшого коефіцієнта, щоб виконувалися умови існування рішення. А необхідне число коефіцієнтів (максимально необхідне) 2 | R |>. Отже, потрібно (| R | - 1) * 2 | R |> біт. Якщо порівнювати це число з тим, що вийде в разі, якщо запам'ятати всі можливі зображення, які можуть бути нанесені на сітківку перцептрона, то знадобиться ємність = | R | * 2 | R | - 1>. При таких припущеннях виходить, що перцептроном для вагових коефіцієнтів ємності потрібно практично стільки ж, як для запам'ятовування всіх можливих зображень.
Для оцінки числа ітерацій. потрібних елементарному перцептроном щоб визначити вагові коефіцієнти, Мінський проаналізував навчання предикату «парність», яка є одна з найбільш теоретично складних для перцептрону. При цьому він взяв перцептрон з найменшим можливим числом А-елементів, а отже і з найменшим числом вагових коефіцієнтів, і для цього випадку визначив нижню і верхню межу числа корекцій: 5 | R |
Тому критика Мінського щодо збіжності перцептрона вказує на те, що:
- якщо потрібно працювати з досить великою роздільною здатністю зображень, наприклад 800х600 пікселів,
- і потрібно вирішити якусь математичну функцію, яка залежить цілком від усіх точок (наприклад, предикат парність, про який не можна сказати, чётен він чи ні поки не будуть проаналізовані всі точки простору послідовно)
то перцептрон зажадає нереально великий пам'яті комп'ютера і тривалого часу навчання, навіть не дивлячись на те, що теорема збіжності говорить про кінцевий числі ітерацій.
Тут, слід додати тільки те, що для більшості завдань розпізнавання реальних зображень не потрібно знаходити такі математичні функції, а відмінні риси зображень різного класу можуть бути знайдені враховуючи лише маленьку область, наприклад, що складається з 20 точок з 8000 можливих. Побудувавши такі предикати від 20 елементів (предикати відповідають А-елементів), можна класифікувати зображення, не враховуючи всі їх особливості (як правило число таких предикатів, як було сказано вище, знаходиться в межах 60-80% від числа всіх зображень). Це вказує на той факт, що число осмислених зображень в певній розмірності на кілька порядків менше, ніж число всіляких зображень. Якщо не вимагати виконання певної математичної функції (зрушення, поворот) над такими осмисленими зображеннями, стає зрозумілим, що перцептрон може не тільки оптимально запам'ятовувати для класифікування ряд зображень, але і працювати в певному сенсі алгоритмом стиснення зображень з втратами. точно відносить їх до необхідного класу.