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

Побудова на етапі навчання "точних" розділяючих гіперповерхней для заданого алфавіту класів розпізнавання. Концепція побудови алгоритмів навчання за методом функціонально-статистичних випробувань в рамках геометричного підходу до розпізнавання образів.

Рубрика Экономико-математическое моделирование
Вид статья
Язык украинский
Дата добавления 25.10.2010
Размер файла 81,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

Спроби побудови на етапі навчання "точних" розділяючих гіперповерхней (РГП) для заданого алфавіту класів розпізнавання {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

a

b

D1

D2

Em

1

1.00

0.00

0.00

1.00

0.50

2

0.89

0.00

0.11

1.00

0.51

3

0.70

0.06

0.30

0.94

0.29

4

0.39

0.14

0.61

0.86

0.20

5

0.17

0.25

0.83

0.75

0.27

6

0.03

0.36

0.97

0.64

0.48

7

0.03

0.53

0.97

0.47

0.38

8

0.00

0.70

0.97

0.30

0.51

9

0.00

0.83

1.00

0.17

0.51

10

0.00

0.94

1.00

0.06

0.51

11

0.00

1.00

1.00

0.00

0.50

12

0.22

0.14

0.78

0.84

0.33

При цьому, на першому кроці навчання обчислюється значення КФЕ для вершини 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 с.


Подобные документы

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

    курсовая работа [24,3 K], добавлен 18.01.2013

  • Сутність статистичних індексів в економічних дослідження. Індивідуальні та загальні індекси кількісних та якісних показників. Аналіз статистичних даних по купівельній спроможності середньої заробітної плати та середньої пенсії на продовольчих ринках.

    курсовая работа [666,4 K], добавлен 16.07.2010

  • Максимальна негативна кількість та індексний рядок. Розв'язання задачі лінійного програмування симплексним методом. Побудова першого опорного плану системи нерівностей. Метод штучного базису та матриця коефіцієнтів. Основний алгоритм симплекс-методу.

    контрольная работа [302,8 K], добавлен 28.03.2011

  • Елементи теорії статистичних рішень. Критерії вибору рішення в умовах невизначеності. Класифікація систем масового обслуговування. Основні характеристики та розрахунок їх параметрів. Елементи задачі гри з природою. Особливості критерій Гурвіца та Вальда.

    курсовая работа [94,6 K], добавлен 08.09.2012

  • Статистичний і економічний зміст коефіцієнтів кореляції і детермінації. Економічне тлумачення довірчих інтервалів коефіцієнтів моделі, точкового значення прогнозу. Форма відображення статистичних даних моделі. Параметри стандартного відхилення асиметрії.

    контрольная работа [20,1 K], добавлен 03.08.2010

  • Побудова математичної моделі плану перевезення зерна на елеватори, який мінімізує транспортні витрати. Розв’язок задачі симплексним методом. Знаходження графічним методом екстремумів функцій, визначеній нерівностями. Порядок рішення транспортної задачі.

    контрольная работа [326,2 K], добавлен 28.03.2011

  • Застосування електоронних таблиць та пакетів прикладних програм у статистичних та економетричних розрахунках. Побудова парної та непарної лінійної регресійної моделі економічних процесів. Моделювання економічних процесів для прогнозу та прийняття рішень.

    методичка [232,8 K], добавлен 17.10.2009

  • Складання математичної моделі задачі. Побудова симплексної таблиці. Розв’язок задачі лінійного програмування симплексним методом. Рішення двоїстої задачі та складання матриці. Знаходження графічним методом екстремумів функцій, визначеній нерівностями.

    контрольная работа [239,0 K], добавлен 28.03.2011

  • Загальний аналіз ризиків. Види несанкціонованого проникнення та загрози онлайн-платежів, їх сутність. Аутентифікація та електронно-цифровий підпис. Аналіз статистичних даних і побудова моделі злочинів інтернет-банкінгу. Практична реалізація моделі.

    курсовая работа [1,8 M], добавлен 13.04.2013

  • Побудова математичної моделі плану виробництва, який забезпечує найбільший прибуток. Розв’язок задачі симплекс-методом, графічна перевірка оптимальних результатів. Складання опорного плану транспортної задачі. Пошук екстремумів функцій графічним методом.

    контрольная работа [286,4 K], добавлен 28.03.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.