Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

МЕТОД МІНІМІЗАЦІЇ ЕМПІРИЧНОГО РИЗИКУ

Нехай z - (rr, i) - деяка ситуація, що складається в тому, що об'єкт х відноситься до класу Ki. Якщо F (x, а) - деякий вирішальне правило, то функція Q (z, a) = (г - F (x, а)) 2 визначає величину втрат при появі ситуації г, тобто вона дорівнює 1, якщо вирішальне правило неправильно класифікував об'єкт х, і 0 - в іншому випадку.

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

визначального середню величину втрат.

Один із шляхів вирішення цього завдання пов'язаний з ідеєю заміни невідомого функціоналу

функцією

побудованої за випадковою і незалежної навчальній вибірці

1

Функція РЕМП отримала назву функції, обчислюється величину емпіричного ризику. Для кожного фіксованого значення параметра а вона визначає середню величину втрат на вибірці z , zi , ..., zi.

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

Виникають питання, для яких функцій Q (z, a) така підміна можлива, і яка при цьому відбувається помилка?

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

Теорема 5. Якщо з безлічі, що складається з N вирішальних правил , серед яких є правило, яке не помиляється ні

Мал. 1.10 :

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

Доведення. Згідно класичним теорем теорії ймовірностей частота появи будь-якої події сходиться до ймовірності цієї події при необмеженому збільшенні числа випробувань. Однак з цих теорем ніяк не випливає, що вирішальне правило F (x, a *), яке має мінімальну частоту помилок РЕМП ( «), буде мати мінімальну або близьку до мінімальної ймовірність помилки.

Припустимо для наочності, що вирішальні правила F (x, а) задаються скаляром а, який може приймати значення від 0 до 1. Кожному значенню а ставиться в відповідність вирішальне правило, для якого існує ймовірність помилки

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

Метод мінімізації емпіричного ризику пропонує по мінімуму функції РЕМП (<*) судити про мінімумі функції Р (а). Для того щоб по точці мінімуму і мінімального значення функції РЕМП (<*) можна було судити про точку мінімуму функції Р (а) і її мінімальному значенні, досить, щоб крива РЕМП (а) перебувала всередині е -трубка кривої Р (а). Навпаки, викид хоча б в одній точці (як на малюнку 1.10) може привести до того, що в якості точки мінімуму Р (а) буде обрана точка викиду. В цьому випадку мінімум РЕМП (<*) ніяк не характеризує мінімум функції Р (а).

Це означає, що нас цікавлять не класичні умови, коли для будь-яких а і е має місце

при I -? оо, а більш сильні умови рівномірного наближення, коли для будь-якого е справедливо

при I -? оо.

Отже, нехай клас вирішальних правил складається з кінцевого числа N елементів (Р (х, а, -): j = 1,2, ..., N}.

Позначимо i / j = Р Е мп (<* Д А Ч = P (<* i)>

За умовою теореми серед функцій

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

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

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

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

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

Підставляючи оцінку Pj в (1.3), отримаємо

Для того щоб ймовірність P {supj vj - pj> ?} НЕ

перевершувала т /, досить виконання умови

Вирішуючи щодо / це нерівність, отримаємо

Теорема доведена. ?

вправи

  • 1.23. Образи Si і «5> 2 задані нормальними розподілами N (0,1) і N (1,1). Обчислити ймовірність помилки розпізнавання за правилом Байеса за умови, що апріорне розподіл ймовірностей появи образів Si і таке: а) {1 / 2,1 / 2};
  • б) {1 / 3,2 / 3}.
  • 1.24. Образи Si, S 2 і S3 задані рівномірними розподілами на відрізках [0; 1/2), [1/3; 2/3] і [0; 2] відповідно. Обчислити ймовірність помилки розпізнавання за правилом Байеса, якщо апріорний розподіл ймовірностей появи образів Si, S2 і S3 таке: {1/2; 1/4; 1/4}.
  • 1.25. Довести, що якщо задано два нормальних розподілу з однаковими ковариационную матрицями, що відрізняються тільки векторами середніх, то байєсівської кордоном буде гіперплоскость.
  • 1.26. Довести, що якщо два нормальних розподілу мають однакові коваріаційні матриці і ці матриці діагональні, то алгоритм максимальної правдоподібності (метод Байеса) еквівалентний методу еталонів.
  • 1.27. Величина з класу Si має нормальний розподіл JVi, а з S2 - N 2 . Імовірність події Si дорівнює Pi, a Si - А- Ціна помилки першого роду (тобто подія Si розпізнати як S2) дорівнює Ci, а ціна помилки другого роду - С2. Визначити вирішальне правило і висловити математичне очікування ціни помилки через ERF (x) =

/ 0 * ехр (- t 2 ) dt за умови що

 
<<   ЗМІСТ   >>