Алгоритм навчання системи розпізнавання за методом функціонально-статистичних випробувань

АЛГОРИТМ НАВЧАННЯ СИСТЕМИ РОЗПІЗНАВАННЯ ЗА МЕТОДОМ ФУНКЦІОНАЛЬНО-СТАТИСТИЧНИХ ВИПРОБУВАНЬ

Краснопоясовський А.С., доц.;

Черниш А.В., асп.

Спроби побудови на етапі навчання "точних" розділяючих гіперповерхней (РГП) для заданого алфавіту класів розпізнавання {X0m}, m=1..M, виявилися неспроможними через такі принципові обставини:

- неоднозначність розв'язання задачі, оскільки в багатовимірному просторі ознак розпізнавання (ОР) може бути побудовано нескінчену кількість "точних" РГП;

- перетинаємість класів розпізнавання;

- неповна апріорна інформація про властивості класів розпізнавання.

Один із підходів до подолання цих утруднень грунтується на ідеях статистичної теорії прийняття рішень і полягає в знаходженні у процесі навчання деякої розділяючої функції, що є функцією правдоподібності, з наступним прийняттям на екзамені рішення за одним із статистичних критеріїв. Оскільки умовні щільності розподілу ймовірностей апріорно невідомі, то було запропоновано алгоритми навчання [1], які дозволяли відновлювати ці щільності шляхом пошуку апроксимуючих РГП, які за теоремою Вейерштрасса про наближення функцій мали звичайно поліномінальний вигляд. Проте на практиці апроксимуючі алгоритми навчання характеризуються відносно низькими оперативністю та достовірністю розпізнавання на екзамені. Якщо низька оперативність пов'язана із розв'язанням проблеми збіжності, то низька достовірність розпізнавання обумовлена як неповною інформацією про образи, так і обмеженістю навчаючої вибірки (НВ), що робить необхідним екстраполювання даних, отриманих на частині реалізацій образів, на всю множину. Розглянута нижче концепція побудови алгоритмів навчання за методом функціонально-статистичних випробувань (МФСВ) займає в рамках геометричного підходу до розпізнавання образів проміжне становище між алгоритмами побудови "точних" РГП і класичними алгоритмами ітераційної оптимізації апроксимуючих розділяючих функцій і дозволяє виключити недоліки та зберегти переваги цих алгоритмів.

Методологічні та теоретичні положення підходу. Ідея навчання в рамках МФСВ полягає в знаходженні для кожного класу Xm0 максимуму критерія функціональної ефективності (КФЕ) Em, який визначає екстремальні значення, наприклад, таких параметрів навчання:

- радіуси РГП dm* в кодовій відстані Хеммінга, які визначаються за формулою:

,

- система контрольних припусків {d*k,i} на ОР;

- рівні селекції {rm} вхідних даних для заданого алфавіту {Xm0};

- екстремальні порядкові статистики {S*m,n}, які є одномірними статистичними характеристиками НВ, де n=1..nmin - випробування, мінімальна кількість яких nmin визначається за умови забезпечення репрезентативності НВ [2]. Якщо статистика S*m,n має розподіл , то вона є інваріантною в межах своєї статистичної структури і містить ряд властивостей, які в рамках МФСВ використовуються як для прогнозування моменту перенавчання системи, так і в алгоритмах кластер-аналізу.

Як КФЕ в МФСВ виступає інформаційний критерій:

,(1)

де

- апріорна (безумовна) ентропія;

- апостеріорна (умовна) ентропія, що характеризує залишкову невизначеність після прийняття рішення; - імовірність прийняття гіпотези ; - імовірність прийняття рішення за умови, що прийнята гіпотеза ; М - кількість гіпотез.

Розглянемо для двохальтернативної системи оцінок (M=2) найбільш важкий у статистичному сенсі випадок прийняття рішень, коли безумовні ймовірності та гіпотези є рівноймовірними. Тоді після заміни в (1) апостеріорних ймовірностей на апріорні за формулою Байеса отримаємо [3]

(2)

де , D1, D2 - точнісні характеристики (ТХ), помилки першого та другого роду, перша та друга достовірності відповідно. Отже, критерій (2) є нелінійним функціоналом від ТХ процесу навчання і виступає як інтегральна оцінка її точності. Оскільки значення критерія (1) залежать від ТХ, то для пошуку максимуму КФЕ в процесі навчання необхідно здійснювати варіювання їх значень. Хай сформовано вектор оптимізованих параметрів навчання g = <g1,..,gL>, елементи якого впливають на значення ТХ. Тоді задача оптимізації процесу навчання в МФСВ полягає в знаходженні такого вектора g, який забезпечує

,

де область G задається системою рівнянь Rj(g1,..,gL)=0, j=1..J.

Розглянемо алгоритми оптимізації в рамках МФСВ вищезазначених параметрів навчання. Визначення оптимальної в інформаційному сенсі кодової відстані dm* здійснюється за послідовним алгоритмом

де dm(0)=0; k - число прирощень радіуса РГП; h - крок прирощення;

,

де {d}={0,1,2,..d(xmЕxm+1)} - множина радіусів гіперсфер класу Xm0; xm+1 - ЕВ найближчого (до класу Xm0) сусіднього класу X0m+1.

Оптимізація контрольних припусків здійснюється після вибору d1* для класу X01, який є бажаним для розробника системи, за алгоритмом {dk,i} = {d*k,i}, якщо

,

де {de,i} - система експлуатаційних (нормованих) полів допусків на ОР.

Оптимізація рівня селекції вхідних даних r=ni/nmin, де ni - кількість появи і-ої ознаки в реалізаціях одного класу здійснюється після вибору {d*k,i} і {dm*} за алгоритмом rm=rm*, якщо

де [0;1] - нормований інтервал значень рівня селекції.

Визначення екстремальних порядкових статистик {S*m,n} здійснюється за алгоритмом Sm(K)= S*m,n, якщо

.

На підготовчому етапі здійснюється: формування алфавіту класів розпізнавання , НВ

та формування ЕВ шляхом статистичного усереднення відповідних реалізацій , визначення мінімальної довжини репрезентативної НВ за методом динамічних довірчих інтервалів [3], вибір вихідної системи контрольних припусків за умови

,

розбиття множини на пари сусідніх ЕВ за умови мінімальної відстані між ними.

ПРИКЛАД ОПТИМІЗАЦІЇ ПАРАМЕТРІВ РГП

Оптимальна в інформаційному сенсі (далі просто оптимальна) РГП повинна охоплювати максимальне число "своїх" реалізацій і мінімальне число "чужих", що забезпечує досягнення на екзамені достовірності розпізнавання, наближеної до асимптотичної. З метою ілюстрації концепції навчання за МФСВ розглянемо побудову оптимальної РГП для класу Xm0 на прикладі розподілу реалізацій {xm(n)} і {xm+1(n)}, які наведено на рисунку 1. Тут умовно показано гомоморфну проекцію 36 вершин векторів {xm(n)}, які позначено "+", і 36 вершин векторів {xm+1(n)}, що позначаються "V". Зірочками позначено вершини ЕВ xm і xm+1. Одинадцять концентричних кіл з центром у вершині xm і сталим прирощенням радіуса, яке дорівнює одиниці кодової відстані, є гомоморфними проекціями гіперсфер, з яких необхідно знайти оптимальну РГП для класу Xm0. Для порівняння на рисунку 1 показано проекцію РГП 12, яка побудована за методом еталонів [4] за умови отримання максимального відношення числа "своїх" реалізацій до числа "чужих" реалізацій. За алгоритмом (3) в процесі пошуку оптимальної РГП на кожному кроці навчання обчислюється значення КФЕ, наприклад за формулою (2). Для цього визначимо оцінки ТХ з урахуванням співвідношень

і .

Так, візуальний підрахунок реалізацій, наприклад, для РГП 3 дає

,

оскільки на цьому кроці навчання 25 "своїх" реалізацій не належать до класу Xm0, і

,

оскільки 2 "чужих" реалізації належать до класу Xm0. В таблиці 1 наведено значення ТХ та КФЕ для одинадцяти кроків навчання і окремо з метою порівняння для РГП 12.

Таблиця 1

При цьому, на першому кроці навчання обчислюється значення КФЕ для вершини xm (нульовий радіус гіперсфери). Оскільки жодна реалізація не збігається з xm, то і є максимальними.

На рисунку 2 наведено побудований за таблицею 1 графік зміни значень КФЕ в процесі навчання.

ПРИКІНЦЕВІ ПОЛОЖЕННЯ

Багатомодальність функції КФЕ обумовлена її неоднозначністю і потребує додаткового аналізу з метою визначення області припустимих значень, робочої області та області спостережуваності образу. На підставі співвідношень між ТХ кожного кроку навчання та відповідних їм розтинів поверхні функції (2) (див. [5]) всі значення КФЕ є припустимими, оскільки виконуються умови другого принципу адитивності інформації: чим більше отримано кількість інформації, тим більша достовірність рішення, що приймається. Аналіз таблиці показує, що робочою областю значень КФЕ з практичних міркувань є область II на рисунку 2, де помилки першого та другого роду менші відповідних достовірностей. Крім того, є доцільним допущення при нульовому радіусі, що виключає можливість його використання як оптимального. Отже, в розглянутому прикладі оптимальний радіус гіперсфери для класу Xm0 знайдено на шостому кроці навчання і він дорівнює . Область спостережуваності характеризується розрізнюваністю образів розпізнавання. За таблицею межею такої області є гіперсфера 11. При цьому і є максимальними, оскільки всі "свої" та "чужі" реалізації відносяться до одного класу Xm0 , і значення КФЕ в подальшому не змінюються.

Розглянутий приклад ілюструє працездатність алгоритму оптимізації параметрів навчання за інформаційним критерієм. При цьому алгоритм є відносно "прозорим", дозволяє отримати на екзамені наближену до асимптотичної достовірність розпізнавання. Здобуття такої достовірності можливо при адекватності за статистичними параметрами навчаючої та екзаменаційної вибірок. Простота класифікаційного правила забезпечується використанням гіперсфери за апроксимуючу РГП, що доцільно при прийнятності гіпотези компактності реалізацій образу, яка має місце в задачах контролю та управління. Спроба побудови складнішої РГП, яка охоплює тільки "свої" реалізації, приводить в загальному випадку, як це наведено в прикладі, до зниження достовірності за рахунок збільшення помилки першого роду. В іншому крайньому випадку, коли РГП охоплює всі "свої" реалізації, то одночасно збільшується належність до області класу Xm0 “чужих” реалізацій, що збільшує помилку другого роду.

СПИСОК ЛІТЕРАТУРИ

Васильев В.И. Распознающие системы: Справочник. - 2-е изд., перераб. и доп.- Киев: Наукова думка, 1983. - 422 с.

Краснопоясовський А.С., Черниш А.В. Оцінка функціональної ефективності системи розпізнавання, що навчається // Вісник Сумського університету, 1998. - №2(8). - С.112-118.

Сергеев В.П., Проценко И.Г., Краснопоясовский А.С. Опыт проектирования информационного обеспечения обучающейся АСУТП// Электронная техника. Сер.9. Экономика и системы управления. -1987. Вып.2.- С.53-56.

Турбович И.Т., Гитис В.Г., Маслов В.К. Опознание образов. Детерминир.-статист. подход. -М.: Наука, 1971.- 246 с.