- •Лекція 6 Розпізнавання без навчання.
- •6.1 Параметричне оцінювання.
- •6.2 Непараметричне оцінювання.
- •2. Методи локального оцінювання.
- •Лекція 7
- •7.1. Суть процедури навчання.
- •7.2. Постановка задачі
- •7.5 Обмежуюча умова на пошук екстремуму.
- •8.1 Постановка задачі.
- •7.3. Найкращий стан системи
- •7.4 Алгоритм навчання
- •8.2 Метод розділяючої функції.
- •8.3 Метод комітетів розв’язку задач розпізнавання
- •8.4 Метод потенціальних функцій
- •8.5 Метод штрафних функцій
8.2 Метод розділяючої функції.
Для окреслення
чітких границь класів будемо шукати L
функцій
,
таких, що для всіх
,
Такі функції
називають розділяючими (дискримінантними).
Якщо не задати апріорі ніяких додаткових
властивостей функції
,
то знайти їх буде дуже складно. Тому
переважно беруть не довільні розділяючі
функції, а ті які мають деякі прості
властивості. Як приклад – розглянемо
лінійні розділяючі функції, тобто
функції виду:
Тоді рівняння границі між класами k і l:
або
,
де
.
Очевидно, що останнє рівняння є рівнянням гіперплощини в просторі ознак Х. Приймемо L=2, не обмежуватиме викладу.
Отже, задача
побудови розділяючої гіперплощини,
тобто задача навчання, це задача
знаходження (n+1)
чисел
,
таких, що
для деяких
,
а також:
для
і
для
.
Якщо ми будемо
розглядати простір
розмірності
,
отриманий з простору Х
додаванням однієї координати, рівної
всіх точок
одиниці, то в
нам необхідно знайти гіперплощину, яка
проходить через початок координат і
розділяє два класи:
для
і
для
,
де
є нормаль до шуканої гіперплощини.
Якщо припустити,
що така гіперплощина існує, то за скінчене
число кроків можна добитися побудови
розділяючої гіперплощини, а саме, якщо
і
при
,
то
,
а якщо
при
,
то
,
де
є значенням вектора
після розпізнавання
-го
члена навчаючої послідовності.
Якщо не припускати існування гіперплощини, яка розділяє два класи, то лінійна розділяюча функція повинна будуватися так, щоб число неправильних розпізнавань елементів навчаючої послідовності було мінімальним.
В отму випадку,
коли
,
можна вважати, що лінійна розділяюча
функція будується спочатку для
відокремлення зображень першого класу
(образу) від всіх решта. Далі процедура
побудови розділяючої функції повторюється
на множині решти зображень з метою
виділення другого класу і т.д. Оскільки
аналогічне міркування можна провести
для будь-якої задачі розпізнавання, то
це значить, що число класів, на які
класифікуються зображення, завжди можна
вважати рівним двом.
Розглянемо
кусково-лінійну розділяючу функцію.
Визначимо відстань
між
довільним зображенням
та класом
як:
,
де
відстань між зображеннями, тобто відстань
від вектора
до класу
рівна мінімальній серед відстаней від
вектора
до векторів
з класів
.
Нехай розділяюча функція відносить
довільне зображення
до того класу
,
відстань до якого мінімальна, тобто
,
якщо
.
Якщо припустити
,
то
.
Оскільки
від
не залежить, то можна взяти розділяючу
функцію
.
Дійсно, якщо
є найближчим до
,
то це означає, що по всіх класах комбінація
буде найбільшою для
,
а це значить, що:
.
Так як максимум береться від лінійної комбінації ознак, то розділяюча функція називається кусково-лінійною.
В якості розділяючої функції можна брати і більш складні. Наприклад, квадратична розділяюча функція має вид:
.
Навчання для такої функції полягає у
підбиранні коефіціентів
таким чином, щоб на навчальній послідовності
кількість помилок була мінімальною.
