Моделювання систем розпізнавання на основі показників вірогідності для малих тестових вибірок

Размещено на http://www.allbest.ru/

Національний університет "Львівська політехніка"

УДК 519.2+004.93

Моделювання систем розпізнавання на основі показників вірогідності для малих тестових вибірок

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Таянов Віталій Анатолійович

Львів 2007

Дисертацією є рукопис

Робота виконана у Фізико-механічному інституті ім. Г.В.Карпенка НАН України.

Науковий керівник: доктор технічних наук, професор Русин Богдан Павлович завідувач відділу методів і систем обробки, аналізу та ідентифікації зображень Фізико-механічного інституту ім. Г.В.Карпенка НАН України, м. Львів

Офіційні опоненти:

доктор фізико-математичних наук, професор Яворський Ігор Миколайович завідувач відділу відбору та обробки стохастичних сигналів Фізико-механічного інституту ім. Г.В.Карпенка НАН України, м. Львів

кандидат технічних наук, доцент Яцків Василь Васильович доцент кафедри спеціалізованих комп'ютерних систем Тернопільського державного економічного університету Провідна установа:Інститут кібернетики ім. В.М. Глушкова НАН України, відділ керуючих машин та систем, м. Київ

Захист відбудеться “1” березня 2007 р. о 16⁰⁰ годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, Львів-13, вул. С. Бандери, 12).

З дисертацією можна ознайомитися у бібліотеці Національного університету “Львівська політехніка” (79013, Львів-13, вул. Професорська,1).

Автореферат розісланий “30” січня 2007 р.

Вчений секретар спеціалізованої вченої ради, д.т.н., проф. Бунь Р.А.

розпізнавання модель вірогідність

Загальна характеристика роботи

Актуальність теми. Системи розпізнавання (СР) широко використовуються в різноманітних сферах діяльності людини. Це однаково стосується робототехніки, медичної та технічної діагностики, метеорології, геології, криміналістики, біометрії, металофізики тощо. Розпізнавання довільних об'єктів або явищ вимагає створення спеціалізованих систем, що призначені для розпізнавання тих або інших об'єктів чи явищ. При проектуванні спеціалізованих СР зручно мати їх опис у вигляді математичної моделі, яка дає можливість встановити залежність вірогідності роботи систем від їх параметрів. Для багатьох спеціалізованих СР їх структура є сталою, а змінюються лише її параметри, що повинно бути відображено у моделі.

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

Для того, щоб провести швидку оптимізацію параметрів алгоритмів, потрібно мати високоінформативні показники оцінки вірогідності їх роботи, які достатньо чутливі до змін цих параметрів в умовах малих вибірок. Класичні статистичні методи оцінки вірогідності роботи СР нездатні задовольнити переліченим вище умовам. Це означає, що їх неможливо використовувати для проведення оптимізації параметрів моделі класифікаторів, а отже й синтезу СР.

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

Задача, що розв'язувалась в рамках дисертаційної роботи, полягала у створенні математичної моделі СР у вигляді функціоналу параметричної вірогідності, що задається на основі введених прототипних та ймовірнісних показників диференційної оцінки вірогідності роботи цих систем. Математична модель дає можливість встановити степінь впливу основних елементів СР на вірогідність їх роботи. Це дозволяє проводити різнобічний аналіз і синтез СР.

Теоретичні та практичні засади побудови оцінок вірогідності роботи СР розглядалися в роботах багатьох вчених, зокрема В. Берикова, С. Гурова, Ю. Журавльова, А. Івахненко, Г. Лбова, В. Неделько, Б. Русина, В. Рязанова, С. Струка, В. Фурсова, І. Яворського, В. Вапніка, А. Вальда, Р. Дуди, П. Харта, Л. Закса, Г. Крамера, С. Рао, П. Махаланобіса, Й. Неймана, Е. Пірсона, E. Парзена, Р.Фішера та ін., на доробку яких базуються результати досліджень даної дисертаційної роботи.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках держбюджетних тем: “Розробка методів автоматичного експрес-аналізу параметрів мікроструктури конструкційних матеріалів” (номер державної реєстрації 0102U002670), “Розробка інформаційних технологій реконструкції і кількісного аналізу тривимірних зображень поверхні зламів конструкційних матеріалів” (номер державної реєстрації 0105U004310) у Фізико-механічному інституті ім. Г.В. Карпенка НАН України у відділі “Методів та систем обробки, аналізу та ідентифікації зображень”, де автор приймав участь як виконавець.

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

Мета роботи передбачає розв'язання наступних наукових задач:

· побудова та дослідження математичної моделі СР, яка представляється у вигляді функціоналів диференційних прототипних та ймовірнісних показників оцінки вірогідності її роботи;

· проведення порівняльного аналізу класичних оцінок вірогідності розпізнавання і запропонованих, що отримані на основі диференційного підходу; визначення мінімального розміру тестових вибірок, необхідних при застосуванні запропонованих методів;

· розробка та дослідження моделі класифікації образів у межах довірчого інтервалу результататів роботи СР;

· розробка критеріїв оптимізації параметрів класифікаторів з метою побудови ефективних моделей при розв'язанні задач параметричного синтезу СР на основі послідовного аналізу, зокрема оптимізація векторів ознак блоків класифікації.

Об'єктом досліджень є СР, що функціонують в умовах малих тестових вибірок.

Предметом досліджень є методи аналізу вірогідності роботи СР на основі створеної математичної моделі, показники оцінки вірогідності, моделі класифікації, а також методи оптимізації параметрів моделі СР при синтезі систем.

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

Наукова новизна. Наукова новизна роботи полягає в отриманні наступних результатів:

· вперше запропоновано та обґрунтовано новий підхід до аналізу роботи СР, який на відміну від вже існуючих дозволяє отримати оцінки вірогідності розпізнавання систем в умовах класичних малих вибірок;

· на основі запропонованого підходу розроблено математичну модель СР, яка представляється у вигляді функціоналів диференційних прототипних та ймовірнісних показників оцінки вірогідності їх роботи;

· отримала подальший розвиток базована на новому підході модель класифікації об'єктів на основі статистичних критеріїв виявлення, яка дозволила проаналізувати процес розпізнавання при апроксимації класів об'єктів в просторі мір відстаней нормальними законами розподілу;

· вперше запропоновано і доведено ефективність моделі класифікації правильних образів у межах довірчого інтервалу, що підвищує вірогідність функціонування СР;

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

Практична цінність отриманих результатів. Отримані в дисертаційній роботі методи, алгоритми та програмні модулі оцінки вірогідності роботи СР орієнтовані здебільшого на проведення аналізу, оптимізації параметрів моделі класифікаторів та синтезу біометричних СР, що працюють в умовах малих вибірок. Загалом результати можуть бути використані як при проектуванні СР для довільної галузі науки, так і для проведення діагностики та класифікації тих або інших взірців об'єктів, наприклад, класу зернистості сталі на основі аналізу зображень її металографічних шліфів. Запропонований метод оцінки вірогідності роботи СР також дав можливість оцінити вплив алгоритмів обробки зображень (таких як фільтрація, компресія тощо) на зміну вірогідності їх розпізнавання, а також об'єктивно визначити, які з класичних оцінок вірогідності розпізнавання є більш ефективними в порівнянні з іншими.

Реалізація науково-технічних результатів. Теоретичні та практичні результати, отримані в дисертаційній роботі, використано в науково-дослідних програмах відділу “Методів та систем обробки, аналізу та ідентифікації зображень” Фізико-механічного інституту ім. Г.В. Карпенка НАН України, у навчальному процесі на кафедрі телекомунікацій Національного університету “Львівська політехніка” при викладанні дисципліни “Цифрова обробка сигналів”. Результати роботи у вигляді спеціальних програмних модулів впроваджено у ВАТ “Укртелеком” та Львівському науково-дослідному радіотехнічному інституті, що засвідчено актами впровадження.

Особистий внесок здобувача. Усі положення, які становлять суть дисертації, сформульовано та вирішено здобувачем самостійно. В роботах, написаних у співавторстві, автору дисертації належить: ідея визначення вірогідності роботи СР в цілому на основі визначення вірогідності розпізнавання окремо тестованого образу [1]; введення поняття коефіцієнта вірогідності розпізнавання (КВР) і дослідження поведінки його першого і другого моментів [2,3]; введення параметра вірогідності розпізнавання на основі стійкості КВР до внутрішніх і зовнішніх спотворюючих факторів, а також визначення міри скупченості образів в межах класів [7, 16]; дослідження кластерних можливостей перетворення Карунена-Лоєва на основі компактного опису швидкозмінних мовних сигналів [15]; аналіз коректності гіпотези про нормальність закону розподілу відстаней між образами в метричному просторі та дослідження впливу розміру бази даних на зміну першого і другого моментів цього розподілу [4]; застосування модифікованої концепції вінерівського процесу до визначення ймовірності незаміщення правильного образу неправильним у межах довірчого інтервалу; побудова ланцюгів, що визначають імовірності переходів КВР до перетворення його в нуль та до припинення галуження [9, 17]; визначення ймовірності попадання правильних образів у межі довірчого інтервалу; алгоритм визначення правильних образів у межах довірчого інтервалу, коли вони знаходяться на довільних позиціях [6]; визначення особливостей застосування статистичних критеріїв виявлення в задачах розпізнавання, коли класи задані розподілами відстаней в метричному просторі, аналіз випадків однопрототипних та багатопрототипних класів, визначення умов, яким мають задовольняти класи для отримання мінімальної сумарної помилки виявлення [8, 12, 20]; аналіз 3-х різновидів функцій відношення правдоподібностей у випадку нормально розподілених класів, визначення максимального за модулем значення порогу, який можна досягти, через довільні значення першого та другого моментів [5, 18]; введення критеріїв оптимізації параметрів класифікаторів, дослідження цієї оптимізації на тестовому прикладі при використанні диференційних показників вірогідності правильного розпізнавання [10, 19]; запропонування використання послідовного аналізу для оптимізації параметрів класифікаторів [24]; аналіз і параметричний синтез СР [22, 23]; розрахунок і порівняння класичних і диференційних оцінок імовірності неправильного розпізнавання для конкретної бази даних облич людей, процедури визначення розміру малої вибірки [11].

Апробація результатів роботи. Основні результати дисертаційної роботи доповідались на:

· XVII, XVIII та XIX науково-технічних конференціях молодих науковців і спеціалістів “КМН-2002”, “КМН-2003”, “КМН-2005” (Львів, 2002, 2003, 2005 рр.).

· XI міжнародній Польсько-Украінській конференції "САПР в машинобудуванні. Проблеми навчання та впровадження" (Варшава, Польща, 2003 р.);

· міжнародних конференціях TCSET'2004, TCSET'2006 "Сучасні проблеми радіоелектроніки, телекомунікацій, комп'ютерної інженерії" (Славсько, 2004, 2006 рр.);

· VII, VIII міжнародних конференціях УкрОбраз'2004, УкрОбраз'2006 “Оброблення сигналів і зображень та розпізнавання образів” (Київ, 2004, 2006 рр.).

· науково-практичній конференції “Сучасні проблеми телекомунікацій-2004” (Львів, 2004 р.);

· VIII міжнародній конференції CADSM'2005 "Досвід розробки та застосування приладо-технологічних САПР мікроелектроніки" (Львів, Поляна, 2005 р.);

· III міжнародній конференції “Фотоніка-ОДС 2005” “Оптоелектронні інформаційні технології” (Вінниця, 2005 р.);

· науково-методичній конференції “Сучасні проблеми телекомунікації і підготовка фахівців в галузі телекомунікацій -2006” (Львів, 2006 р.);

· міжнародній молодіжній науково-технічній конференції студентів, аспірантів і вчених "Молодёжь и современные проблемы радиотехники и телекоммуникаций РТ-2006" (Севастополь, 2006 р.);

· наукових семінарах Фізико-механічного інституту ім. Г.В. Карпенка НАН України (2002-2006 рр.).

Публікації. За темою дисертації опубліковано 24 наукових праці, в тому числі 1 монографія, 11 статей у фахових наукових журналах і збірниках, 12 статей в матеріалах конференцій.

Структура та обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаної літератури, що містить 120 найменувань, та додатків. Повний обсяг дисертації становить 159 сторінок, з яких 123 сторінки основного тексту і 11 сторінок додатків, містить 27 рисунків та 9 таблиць.

Основний зміст роботи

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

У першому розділі розглянуто відомі методи побудови оцінок вірогідності роботи СР. Чим точніше оцінена вірогідність розпізнавання, тим точніше вибрані параметри моделі СР, які максимізують цю вірогідність. Отже, методи оцінки вірогідності визначають точність вибору оптимальних параметрів моделі СР.

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

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

Другий розділ присвячений дослідженню ефективності введених прототипних та ймовірнісних показників диференційної оцінки вірогідності роботи СР в умовах малих тестових вибірок. На основі цих показників побудовані моделі класифікації образів та СР в цілому, що відображено у третьому та четвертому розділах.

В якості базового показника прототипної групи введено КВР, який має наступні властивості:

1. КВР дорівнює одиниці тоді, коли всі базові образи, що відповідають вхідному, попадають у заданий довірчий інтервал розміром .

2. КВР дорівнює нулю тоді, коли у заданий довірчий інтервал не попадає жодного з правильно ідентифікованих базових образів.

Доведено наступні три теореми:

Теорема 1. Значення першої моментної функції сімейства випадкових величин дорівнює 1, якщо існує лише один клас образів. Перша моментна функція, а відповідно і ймовірність розпізнавання образів прямує до 0, якщо кількість класів прямує до .

Теорема 2. Значення другої центральної моментної функції сімейства випадкових величин дорівнює 0, якщо кількість класів дорівнює 1, та прямує до 0, якщо кількість класів прямує до .

Теорема 3. Існує таке скінченне число класів образів у базі даних, при якому ймовірність того, що образи будуть розпізнаватись, не перевищуватиме наперед заданого, як завгодно малого значення.

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

Проведено дослідження диференційних імовірнісних показників вірогідності. При цьому показано коректність гіпотези про те, що розподіл відстаней між образами в метричних просторах є нормальним. В рамках доведення показано, що відстані між образами в метричних просторах задовольняють умовам процесу із незалежними приростами або вінерівському процесу. Оскільки закон розподілу відстаней між образами є нормальний, то на основі функції розподілу ймовірностей можна визначити ймовірність заміщення (незаміщення) правильного образу неправильними. Внаслідок того, що розмір бази, на основі якого визначені моменти першого та другого порядку, є скінчений і не всі образи глобально незалежні, то розглянуто похибку визначення 1-го та 2-го моментів, яка обумовлена цими двома факторами. Показано на експериментальному прикладі, що при зменшенні існуючої бази образів в 10 разів, значення середньої повної помилки та її кореляційної складової для моментів 1-го та 2-го роду змінюється в межах 1-2%. Звужена база даних містить при цьому 72 образи.

Ймовірність правильного розпізнавання, коли відома початкова ймовірність незаміщення правильного образу неправильними , дорівнює

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

(1)

Проведено порівняльний аналіз запропонованих і класичних оцінок результатів роботи алгоритму розпізнавання та визначено розмір тестової вибірки, яку можна використовувати при застосуванні запропонованого підходу щодо оцінювання цієї вірогідності. Для точкових оцінок виграш в дисперсії порівняно з класичною оцінкою максимальної правдоподібності складає 2.54, а в порівнянні з класичною баєсівською - 1.8 разів. Виграш в розмірах інтервалів порівняно з класичними фішерівськими та нейманівськими досягнуто в 1.77, 1.74, 1.71 рази для коефіцієнтів довіри , та , відповідно. Верхня межа розміру тестової малої вибірки складає 30 елементів.

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

, (2)

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

Далі розглянуто особливості застосування диференційного підходу до аналізу моделі класифікації. Нехай вхідний образ породжує суміш з гаусіан - . Розглянуто випадок коректного розпізнавання, коли для всіх нормально розподілених класів бази даних має виконуватися умова (, - математичне сподівання та дисперсія нормально розподіленого правильного класу).

Нехай . Розглянуто спочатку модель класифікації у випадку однопрототипного класу. При цьому математичне сподівання розподілу кожного класу дорівнює відстані кожного образу бази до вхідного образу. Якщо подати на вхід СР довільний базовий образ, то і . Можливість варіації вхідного образу відносно базового за умови збереження прийнятного рівня ймовірності правильної класифікації визначена відстанню Махаланобіса між густинами розподілів та :

(3)

Оскільки , то цей ідеалізований випадок не має практичного інтересу.

Розглянуто фізичний зміст математичних сподівань та дисперсій нормально розподілених класів в моделі (2). Чим більше значення , тим більший допуск можна зробити на варіацію образів у межах класів, яка задана дисперсіями . Цим визначена якість алгоритму розпізнавання, а отже й багато інших похідних параметрів - у тому числі допуск на рівень спотворюючих факторів. Найбільшою завадою для класифікації є неправильні класи, що мають розподіли образів з найменшими значеннями математичного сподівання.

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

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

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

Четвертий розділ присвячений задачам застосування диференційного підходу в процесі оптимізації параметрів моделі СР при її синтезі. Математична модель СР представлена у вигляді наступного функціоналу вірогідності: , де - узагальнений класифікатор (надалі - просто класифікатор); - кількість класів; - розмір класу; - розмір довірчого інтервалу .

Модель класифікатора у загальному вигляді представлена як

,(4)



де - відрізки функцій ознак, - метрика між образами в просторі ознак, - вирішуючі функція або правило. В формулі (4) аргументи класифікатора мають символічне позначення і не стосуються певного координатного простору.

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

1. пошук параметрів класифікатора в заданому діапазоні значень, при яких забезпечена задана дисперсія і максимальне середнє значення показника диференційної оцінки вірогідності розпізнавання для тестової послідовності образів;

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

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

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

Побудовано структурну схему СР, центральним елементом якої є блок оцінки вірогідності її роботи, та описано особливості її функціонування. Наведено узагальнену структурну схему алгоритму розпізнавання, що працює в автономному режимі та з оператором. Відзначено, що блок оцінки вірогідності роботи СР має 2 частини. Одна частина використана на етапі аналізу СР, а друга для її параметричного синтезу. У розгляданому випадку параметричний синтез СР дає наступні результати для помилок виявлення 1-го та 2-го роду (, ): розмір вектора ознак дорівнює 100 елементів (200 байт на образ), рекомендований порядок метрики Мінковського складає 1.25 або 1.5, усереднений за базою даних середній розмір класу рівний 5, розмір бази даних складає 200 зображень.

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

Висновки

В дисертаційній роботі розроблено модель СР і процесу класифікації на основі оцінки параметричної вірогідності розпізнавання в умовах малих тестових вибірок. Модель системи розпізнавання і процесу класифікації дозволила провести аналіз і параметричний синтез тестованої системи, а також оцінити вірогідність роботи класифікаторів.

Основні наукові результати дисертаційної роботи полягають в наступному:

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

2. Вперше запропоновано та обґрунтовано диференційний підхід до аналізу роботи СР, який дозволяє отримати оцінки вірогідності розпізнавання системи в умовах класичних малих вибірок. Підхід дає можливість встановити нестаціонарний характер вірогідності розпізнавання, а саме: вона прямує до нуля, якщо розмір бази даних прямує до нескінченності, а розмір класу обмежений.

3. На основі диференційного підходу створено математичну модель СР у вигляді диференційних прототипних та ймовірнісних показників оцінки вірогідності їх роботи. В рамках прототипних показників вперше проведено апроксимацію вірогідності розпізнавання при дії внутрішніх (недосконалість алгоритму) та зовнішніх спотворюючих факторів, що дало можливість отримати усереднене на діапазоні дій цих факторів значення вірогідності. Коректність гіпотези про нормальність закону розподілу відстаней між образами в метричному просторі дозволила отримати ряд диференційних імовірнісних показників оцінки вірогідності розпізнавання, а також визначити міру компактності класу в імовірнісному просторі.

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

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

6. На основі отриманих результатів проведено оптимізацію класифікатора СР та її параметричний синтез, що дає наступні результати для помилок виявлення 1-го та 2-го роду (, ): розмір вектора ознак дорівнює 100 елементів (200 байт на образ), усереднений за базою даних середній розмір класу рівний 5, розмір бази даних складає 200 зображень.

7. Порівняно класичні точкові та інтервальні оцінки ймовірності неправильного розпізнавання з оцінками, отриманими на основі диференційного підходу. У випадку точкових оцінок виграш в дисперсії порівняно з оцінкою максимальної правдоподібності складає 2.54, а в порівнянні з баєсівською - 1.8 разів. Виграш в розмірах інтервалів порівняно з фішерівськими та нейманівськими досягнуто в 1.77, 1.74, 1.71 рази для коефіцієнтів довіри , та , відповідно. Визначено розмір малої вибірки, який для тестованої бази даних складає 30 образів.

8. Розроблено програмні модулі, що дають можливість проводити аналіз СР, оптимізацію їх класифікаторів та здійснювати параметричний синтез систем на основі побудованої моделі.

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

Список опублікованих праць за темою дисертації

1. Капустій Б.О., Русин Б.П., Таянов В.А. Системи розпізнавання образів з малими базами даних. - Львів: СПОЛОМ, 2006. - 152 с.

2. Капшій О.В., Русин Б.П., Таянов В.А. Критерій оцінки якості розпізнавання системою підтримки прийняття рішення // Электроника и связь. - 2002. №15. - C. 89-93.

3. Капустій Б.О., Русин Б.П., Таянов В.А. Про особливості стохастичних характеристик коефіцієнта надійності розпізнавання для об'єктів з класу R³ // Вісник Національного університету “Львівська політехніка”. Радіоелектроніка та телекомунікації.-2003. - №477. - С 69-76.

4. Капустій Б.О., Русин Б.П., Таянов В.А. Розподіл середньоквадратичних відстаней між об'єктами в просторі R² // Відбір і обробка інформації. - 2003. - Вип. 19(95). - C.110-114.

5. Капустій Б.О., Русин Б.П., Таянов В.А. Особливості застосування моделей функції відношення правдоподібностей до задач розпізнавання // Моделювання та інформаційні технології. - 2004. - Вип. 26. - С. 49-55.

6. Капустій Б.О., Русин Б.П., Таянов В.А. Критерії оптимізації набору спектральних складових перетворення Карунена-Лоєва при розрахунку диференційної ймовірності правильного розпізнавання // Радиоэлектроника и информатика. - 2004. - № 3. - С. 118-121.

7. Капустій Б.О., Русин Б.П., Таянов В.А. Визначення апостеріорної надійності системи підтримки прийняття рішення методом верифікації мір локальних переходів коефіцієнта надійності розпізнавання // Вісник Національного університету “Львівська політехніка”: Радіоелектроніка та телекомунікації.-2004. - №508. - С. 46-52.

8. Капустій Б.О., Русин Б.П., Таянов В.А. Особенности применения критериев обнаружения к задачам распознавания объектов // Проблемы управления и информатики. - 2005. - № 1. - С. 107-114.

9. Капустій Б.О., Русин Б.П., Таянов В.А. Новый подход к определению вероятности правильного распознавания объектов множеств // УСиМ. - 2005. - № 2. - С. 8-13.

10. Капустій Б.О., Русин Б.П., Таянов В.А. Нові підходи до параметричного синтезу алгоритмів розпізнавання // Радиоэлектроника и информатика. - 2005. - № 3. - С. 128-134.

11. Капустий Б.Е., Русын Б.П., Таянов В.А. Сравнительный анализ различных оценок вероятности распознавания // Проблемы управления и информатики. - 2006. - № 4. - С.89-96.

12. Капустій Б.О., Русин Б.П., Таянов В.А. Реалізація статистичних критеріїв виявлення в задачах розпізнавання // Радиоэлектроника и информатика. - 2006. - № 1. - С. 91-96.

13. Таянов В.А. Оптимізація вибору ознак у системах розпізнавання, побудованих на основі ортогональних перетворень / Матер. XVII відкр. наук.-техн. конф. молодих науковців і спеціалістів “Діагностичні системи та сигнали”. - Львів, 2002. - С. 175-178.

14. Таянов В.А. Про деякі похибки, що виникають при визначенні параметрів надійності систем підтримки прийняття рішень / Матер. XVIII відкр. наук.-техн. конф. молодих науковців і спеціалістів “Діагностичні системи”. - Львів, 2003. - С. 210-213.

15. Tayanov V.А., Tayanov S.A. The error analysis of speech signal computer compression by Karhunen-Loeve transform / Proc. of the 11-th Polish-Ukrainian Conf. on "Cad in Machinery Design - Implementation and Educational Problems”. - Warsaw, 2003. - P. 113-119.

16. Kapustiy B.O., Rusyn B.P., Tayanov V.A. Definition of the object density measure in class boundary / Proc. of the Intern. Conf. TCSET'2004 “Modern Problems of Radio Engineering, Telecommunications and Computer Science”. - Lviv-Slavsko, 2004. - P. 253.

17. Капустій Б.О., Русин Б.П., Таянов В.А. Про концепції оптимально-надійнісного розпізнавання / Оброблення сигналів і зображень та розпізнавання образів: Праці 7 - ї Всеукр. міжнар. конф. - Київ, 2004. - С. 29-32.

18. Капустій Б.О., Русин Б.П., Таянов В.А. Функції відношення правдоподібностей та їх застосування для розв'язку частинних випадків задачі розпізнавання / Матер. наук.-практ. конф. “Сучасні проблеми телекомунікацій-2004”. - Львів, 2004. - С. 29-31.

19. Капустій Б.О., Русин Б.П., Таянов В.А. Параметричний синтез алгоритмів розпізнавання за диференційними показниками вірогідності / Тези доп. Третьої міжнар. наук.-техн. конф. з оптоелектронних інформаційних технологій “Фотоніка-ОДС-2005”. - Вінниця, 2005. - С. 103-104.

20. Kapustiy B.O., Rusyn B.P., Tayanov V.A. Realization of the statistical detection methods in pattern recognition tasks / Proc. of the Intern. Conf. “The Experience of Designing and Application of CAD Systems in Microelectronics” CADSM'2005. - Lviv-Polyana, 2005. - P. 99-101.

21. Таянов В.А. Оптимізація класифікаторів в умовах малих вибірок / Матер. XIX відкр. наук.-техн. конф. молодих науковців і спеціалістів “Діагностичні системи”. - Львів, 2005. - С. 367-370.

22. Kapustiy B.O., Rusyn B.P., Tayanov V.A. Parametrical recognition algorithm synthesis based on the sequential analysis / Proc. of the Intern. Conf. TCSET'2006 “Modern Problems of Radio Engineering, Telecommunications and Computer Science”. - Lviv-Slavsko, 2006. - P. 294-296.

23. Капустий Б.Е., Русын Б.П., Таянов В.А. Параметрический синтез систем распознавания / Материалы международной молодежной научн.-техн. конф. студентов, аспирантов и ученых “Молодежь и современные проблемы радиотехники и телекоммуникаций РТ-2006”. - Севастополь, 2006. - С. 181.

24. Капустій Б.О., Русин Б.П., Таянов В.А. Оптимізація класифікатора в ознаковому і метричному просторах / Оброблення сигналів і зображень та розпізнавання образів: Праці 8-ї Всеукр. міжнар. конф. - Київ, 2006. - С. 31-34.

Анотації

Таянов В.А. Моделювання систем розпізнавання на основі показників вірогідності для малих тестових вибірок. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи.-Національний університет “Львівська політехніка”, Львів, 2007.

Дисертація присвячена розробці моделі систем розпізнавання (СР) в умовах малих вибірок на основі оцінки вірогідності їх роботи. В подібних випадках використання класичних оцінок часто веде до некоректного їх визначення. Для розв'язання проблеми пропонуються диференційні прототипні та ймовірнісні показники оцінки вірогідності роботи СР. Ці показники дають можливість оцінювати вірогідність розпізнавання кожного окремого образу. В рамках прототипного підходу досліджено статистичні властивості коефіцієнта вірогідності розпізнавання (КВР). Запропоновано спосіб порівняння ефективності роботи двох систем розпізнавання на основі 1-го та 2-го моментів КВР. Введено параметр вірогідності розпізнавання, що визначає стійкість КВР до впливу різних видів спотворюючих факторів. В рамках імовірнісного підходу показано коректність гіпотези, що розподіл відстаней між образами в межах класів і всієї бази даних є нормальним, визначено ймовірність розпізнавання окремого образу та ймовірності переходів КВР з різних станів. Запропоновано модель класифікації образів у межах довірчого інтервалу. Крім того, для побудови моделі класифікації образів за допомогою диференційного підходу досліджено особливості використання статистичних критеріїв виявлення. На основі розроблених показників проводиться швидкий, різнобічний та ефективний аналіз і синтез СР в умовах малих вибірок як результат оптимізації параметрів моделі, який неможливо реалізувати за допомогою класичних підходів.

Ключові слова: модель системи розпізнавання, класифікатор, вірогідність розпізнавання, оцінка, мала вибірка, аналіз, синтез.

Таянов В.А. Моделирование систем распознавания на основании показателей достоверности для малых тестовых выборок.- Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы.-Национальный университет “Львовская политехника”, Львов, 2007.

Диссертация посвящена разработке модели систем распознавания (СР) в условиях мылых выборок на основании оценки достоверности их работы. В подобных случаях использование классических оценок часто приводит к некорректному их определению. Для решения проблемы предложены дифференциальные прототипные и вероятностные показатели оценки достоверности работы СР. Эти показатели дают возможность оценивать достоверность распознавания каждого образа в отдельности. В рамках прототипного подхода исследовано статистические свойства коэффициента достоверности распознавания (КДР). Предложен способ сравнения эффективности работы двух систем распознавания на основании 1-го и 2-го моментов КДР. Введён параметр достоверности распознавания, определяющий устойчивость КДР к воздействию различных видов искажающих факторов. В рамках вероятностного подхода показана корректность гипотезы, что распределение расстояний между образами в пределах классов и всей базы данных является нормальным, определена вероятность распознавания отдельного образа и вероятности переходов КДР из различных состояний. Предложена модель классификации образов в пределах доверительного интервала. Кроме того, для построения модели классификации образов с помощью дифференциального подхода исследовано особенности применения статистических критериев обнаружения. На основании разработанных показателей проводится быстрый разносторонний и эффективный анализ и синтез СР в условиях малых выборок как результат оптимизации параметров модели, что не удаётся реализовать при помощи классических подходов.

Ключевые слова: модель системы распознавания, классификатор, достоверность распознавания, оценка, малая выборка, анализ, синтез.

Tayanov V. Recognition systems modeling by reliability indexes for small test samples.- Manuscript. Thesis for the candidate's degree in technical sciences by speciality 01.05.02 - Mathematical Modeling and Methods of Calculation. - Lviv Polytechnic National University, Lviv, 2007.

The dissertation is devoted to the development of the recognition system (RS) model by reliability estimation when sample size is small. Often in such case the classical estimations usage leads to the incorrect determining of them. It is conditioned by the fact that necessary conditions of the representation hypothesis are not satisfied when sample size is small. At the same time statistical characteristics are irregular. In order to solve this problem the differential prototypal and the differential probabilistic indexes of the RS reliability estimation are proposed. Such indexes enable to give an opportunity for the RS reliability estimation of the single tested pattern. Due to the recognition reliability information getting from the single tested pattern one can specify the reliability estimation of the whole recognition algorithm.

In the context of prototypal approach the statistical characteristics of recognition reliability coefficient (RRC) are investigated. Three theorems have been proved. These theorems establish the tendency to 0 of the mean, variance of the RRC and correct recognition probability when the class number tends to infinity. The method to compare of the two recognition systems based on the mean and variance of the RRC has been proposed. At the same time priority is after the RRC mean. The recognition reliability parameter that determines the different corruption factors stability of the RRC has been introduced. One kind of the corruption factors is conditioned by the imperfection of an algorithm and the second one is conditioned by the outside corruption factors. In the context of the probabilistic approach it has been showed the correctness of the hypothesis that probability density function (PDF) of the distances between patterns inside the class and the whole database is normal. It has been carried out both theoretically and practically. The theoretical method is based on the fact that distances between patterns generate the Wiener process and that is why having normal PDF. In the context of the experimental approach two methods has been used. The first method is based on the variance comparison. The variances have been determined by two different expressions and equal to each other only when the PDF is normal. The second method is based on the nonparametric estimation by the Parzen window and the support vector machines with some kernel functions for every approach. On the basis of the normal PDF the recognition probability of the single pattern and RRC from different states transfer probability within the bounds of the fiducial interval has been defined. It has been marked that tending the class number to infinity leads to the true recognition probability substitution equalization for the true pattern within the bounds of the fiducial interval.

The classification model of the pattern within the bounds of the fiducial interval has been proposed. The fiducial interval size is taken basing on the fiducial probability value of the true pattern presentation within the bounds of the fiducial interval. At the same time the pattern searching within the bounds of the fiducial interval is carried out much faster than within the whole database. Furthermore the classification model of the pattern using the peculiarities of the differential approach for the statistical classification methods has been investigated. At the same time the conditions of the minimal sum of the type I and II errors achievement has been discovered. The area of application of the statistical Neyman-Pearson test, Ziegert test and Wald test has been defined.

Basing on the developed coefficients one can provide fast, multifaceted, effective analysis and synthesis of the RS in small sample size conditions as the result of the RS optimization model parameters procedure. Such an analysis and synthesis one can not realize using classical approaches only.

Keywords: recognition system model, classifier, recognition reliability, estimation, small sample, analysis, synthesis.

Размещено на Allbest.ru