1. Теоретичні відомості
1.1 Аналіз предметної області розпізнавання рукописних символів на основі машини Больцмана
Розпізнавання - це віднесення конкретного об'єкта (реалізації), представленого значеннями його властивостей (ознак), до одного з фіксованого переліку образів (класів) з певного вирішального правилом у відповідності з поставленою метою.
Звідси випливає, що розпізнавання може здійснюватися будь-якою системою (живої або неживої), що виконує наступні функції: вимірювання значень ознак, виробництво обчислень, що реалізують вирішальне правило. При цьому перелік образів, інформативних ознак та вирішальні правила або задаються розпізнає системі ззовні, або формуються самою системою.
Допоміжна, але важлива функція систем, що розпізнають - оцінка ризику втрат. Без цієї функції неможливо, наприклад, побудувати оптимальні вирішальні правила, вибрати найбільш інформативну систему ознак, які використовуються при розпізнаванні, та інші [1].
1. Введемо наступні позначення:
2. 2≤ S< ∞ - Безліч підтримуваних образів (класів), зване іноді алфавітом;
3. N - Розмірність знакового простору (кількість ознак, що характеризують розпізнавані об'єкти);
4. D(X) - Безліч вирішальних правил, за якими здійснюється віднесення об'єкта, що розпізнається до того чи іншого образу;
5. R - Ризик втрат при розпізнаванні.
Кількість розпізнаваних образів S завжди звичайно і не може бути менше двох. Гіпотетично, звичайно, можна розглядати випадок S=1, Але він є виродженим, тому всі реалізації відносять до одного і того ж образу. Для цього не потрібно вимірювати значення яких би то не було ознак, вирішальне правило тривіальне, а практичний сенс вирішення подібного роду задачі розпізнавання навряд чи можна помітити.
Перелік образів, як уже згадувалося, може здаватися розпізнає системі ззовні (вчителем). Наприклад, якщо система призначена для автоматичного стенографування, то розпізнаваними образами є фонеми - елементи усного мовлення.
У багатьох випадках розпізнає система сама формує перелік розпізнаваних образів. У літературі цей процес називають навчанням без вчителя, самонавчанням, кластерним аналізом (таксономією). Ця функція реалізується найчастіше в дослідницькому процесі: природничо-наукова класифікація, аналіз даних, виявлення закономірностей і т.п.
Розмірність знакового простору N зазвичай прагнуть зробити якомога менше, оскільки при цьому скорочується кількість необхідних вимірювань, спрощуються обчислення, формують і реалізують вирішальні правила, підвищується статистична стійкість результатів розпізнавання. Разом з тим зменшення N, Взагалі кажучи, веде до зростання ризику втрат. Тому формування знакового простору є компромісною завданням, яку можна розділити на дві частини: формування вихідного знакового простору і мінімізація розмірності цього простору. У частині, що стосується мінімізації розмірності, існують формальні методи, алгоритми та програми. Що ж стосується початкового простору, то його формування поки що засноване на досвіді, інтуїції, а то й везіння [2]. Теоретично обґрунтовані підходи до вирішення цього завдання в літературі не зустрічаються.
Побудова вирішальних правил, мабуть, найбільш багата щодо розроблених підходів і методів вирішення компонента задач розпізнавання. Основна мета, яка при цьому переслідується, - мінімізація ризику втрат.
Ризик втрат R фактично є критерієм, за яким формується найбільш інформативне знакового простору і найбільш ефективні вирішальні правила. І алфавіт, і ознаки, і вирішальні правила повинні бути такими, щоб по можливості мінімізувати ризик втрат. Цей критерій (характеристика системи, що розпізнає) є складовим. У нього в загальному випадку входять втрати (штрафи) за помилки розпізнавання і витрати на вимірювання ознак розпізнаваних об'єктів. У приватному найбільш широко використовуваному випадку в якості ризику втрат фігурує середня ймовірність помилки розпізнавання або максимальна компонента матриці ймовірностей помилок. На практиці, звичайно, мова йде не про ймовірностях, а про їх вибіркових оцінках.
Розпізнавання образів (pattern recognition) — це розділ теорії штучного інтелекту (artificial intelligence), що вивчає методи класифікації об’єктів. За традицією об’єкт, що піддається класифікації, називається образом (pattern). Образом може бути цифрова фотографія (розпізнавання зображень), буква або цифра (розпізнавання символів), запис мови (розпізнавання мови) тощо [3].
В межах теорії штучного інтелекту розпізнавання образів включається в більш широку наукову дисципліну — теорію машинного навчання (machine learning), метою якої є розробка методів побудови алгоритмів, що здатні навчатися.
Існує два підходи до навчання: індуктивне і дедуктивне. Індуктивне навчання, або навчання за прецедентами, засноване на виявленні загальних властивостей об’єктів на підставі неповної інформації, отриманих емпіричним шляхом. Дедуктивне навчання передбачає формалізацію знань експертів у вигляді баз знань (експертних систем тощо). В нашому курсі нас буде цікавити лише індуктивне навчання, тому будемо вважати машинне навчання і навчання за прецедентами синонімами.
Слід зауважити, що, як кожна математична дисципліна, розпізнавання образів має власний математичний апарат, який включає математичну статистику, методи оптимізації, дискретну математику, алгебру і геометрію.
Розпізнавання образів має широке застосування і використовується при створенні усіх комп’ютерних систем, на які покладаються інтелектуальні функції, тобто функції, пов’язані із прийняттям рішень замість людини: медична діагностика, криміналістична експертиза, пошук інформації та інтелектуальний аналіз даних тощо.
Прецедент — це об’єкт, приналежність якого до заданого класу визначена заздалегідь. Прецедентом може бути, наприклад, набір ознак пацієнта із відомим діагнозом, з яким слід порівнювати набір ознак людини, діагноз якої ще невідомий.
Кожний образ являє собою набір чисел, що описують його властивості і називаються ознаками (feature). Упорядкований набір ознак об’єкта називається вектором ознак (feature vector). Вектор ознак — це точка в просторі ознак (feature space).
Класифікатор, або вирішальне правило (decision rule) — це функція, яка ставить у відповідність вектору ознак образу клас, до якого він належить. Задачу розпізнавання образів можна розділити на ряд під задач [4].
1. Генерування ознак (feature generation) — вимірювання або обчислення числових ознак, що характеризують об’єкт.
2. Вибір ознак (feature selection) — визначення найбільш інформативних ознак для класифікації (в цей набір можуть входити не лише первинні ознаки, але й функції від них).
3. Побудова класифікатора (classifier construction) — конструювання вирішального правила, на підставі якого здійснюється класифікація.
4. Оцінка якості класифікації (classifier estimation) — обчислення показників правильності класифікації (точність, чутливість, специфічність, помилки першого та другого роду).
Машина Больцмана (англ. Boltzmann machine) - вид стохастичною рекуррентной нейронної мережі, винайденої Джеффрі Хінтон і Террі Сейновскі. Машина Больцмана може розглядатися як стохастичний генеративний варіант мережі Хопфілда. Ця модель виявилася першою нейронною мережею, здатної навчатися внутрішнім репрезентаціям, і може представляти і вирішувати складні комбінаторні завдання. Незважаючи на це, через низку проблем, машини Больцмана з необмеженою зв’язністю не можуть використовуватися для вирішення практичних проблем. Якщо ж зв'язність обмежена, то навчання може бути досить ефективним для вирішення практичних проблем.
Машина Больцмана схожа по функції і дії на мережу Хопфілда і включає поняття "модельованого відпалу" для пошуку в просторі станів шару образів глобального мінімуму.
Еклі (Ackley), Хінтон (Hinton) і Сейновскі (Sejnowski) розробили правило больцманівського навчання в 1985 р. Подібно до мережі Хопфілда, машина Больцмана має простір станів, який базується на вагах з'єднань у прошарку образів. Процеси навчання мережі, наповненої образами, включає вивчення рельєфу простору станів.
Машина Больцмана відрізняються від мережі Хопфілда тим, що має стохастичну природу, а нейрони поділені на дві групи: видимі і скриті нейрони. Структурна схема машини Больцмана зображена на рисунку 1.3.
Рисунок 1.3 – Структурна схема машини Больцмана
Машина Больцмана, навчаючись на високій температурі, веде себе як випадкова модель, а на низьких температурах вона як детермінована. Через випадкову компоненти в відпаловому навчанні, нейрон може прийняти нове значення стану, що збільшується швидше, ніж зменшується загальний простір станів. Імітація фізичного відпалу дозволяє просуватися до глобального мінімуму, уникаючи локальний.
Як і в мережі Хопфілда, мережі може бути представлений частковий образ для відсутньої інформації. Обмеження на число класів менше 15% від загальної кількості елементів у прошарку образів, все ще застосовується.
Алгоритм функціонування мережі
1. Визначити змінну T, що представляє штучну температуру.
2. Пред'явити мережі безліч входів і обчислити виходи і цільову функцію.
3. Дати випадкову зміну вагам і перерахувати вихід мережі та зміну цільової функції відповідно до зміни ваг.
4. Якщо цільова функція зменшилась, тоді множина ваг зберігається.
Якщо зміна ваг приводить до збільшення цільової функції, то імовірність збереження цієї зміни обчислюється за допомогою розподілу Больцмана:
(1.5)
де P(c) - імовірність зміни c у цільовій функції; k - константа, аналогічна константі Больцмана, вибирається залежно від завдання; T - штучна температура.
Вибирається випадкове число r з рівномірного розподілу від нуля до одиниці. Якщо P(c) більше, ніж r, то зміна зберігається, в іншому випадку величина ваги повертається до попереднього значення.
Ця процедура дає можливість системі робити випадковий крок у напрямку, що псує цільову функцію, дозволяючи їй вириватися з локальних мінімумів, де будь-який малий крок збільшує цільову функцію.
Для завершення навчання машини Больцмана кроки 3 і 4 повторюються для всіх ваг мережі, поступово зменшуючи температуру T, поки не буде досягнуте припустиме низьке значення цільової функції. У цей момент пред'являється інший вхідний вектор і процес навчання повторюється. Мережа навчається на всіх векторах навчальної множини, поки цільова функція не стане допустимою для всіх з них.
Властивості машини Больцмана широко вивчалися. В роботі показано, що швидкість зменшення температури повинна бути обернено пропорційна логарифму часу. При цьому мережа збігається до глобального мінімуму.
Швидкість охолодження в такій системі виражається таким чином:
……………………………………(1.6)
де T (t) - штучна температура як функція часу; Т0 - початкова штучна температура; t - штучний час.
Цей результат пророкує дуже повільну швидкість охолодження і дані обчислення. Машини Больцмана часто вимагають для навчання дуже великого ресурсу часу.
Машина Больцмана надає такі переваги:
1) можливість мережі вибиратися з локальних мінімумів адаптивного рельєфу простору станів;
2) велика точність розпізнавання образів (вчасності рукописних символів).
До недоліків мережі можна віднести повільний алгоритм навчання. Та за допомогою модифікації можливо частково усунути цей недолік. Випадкові зміни можуть проводитися не тільки для окремих ваг, але і для всіх нейронів шарів в багатошарових мережах або для всіх нейронів мережі одночасно. Ці модифікації алгоритму дають можливість скоротити загальне число ітерацій навчання.
1.2 Постановка задачі розпізнавання рукописних символів на основі машини Больцмана
При постановці задач розпізнавання намагаються користуватися математичною мовою, стараючись, на відміну від теорії штучних нейронних мереж, де основою є одержання результату шляхом експерименту, замінити експеримент логічними міркуваннями й математичними доказами.
Найчастіше в задачах розпізнавання образів розглядаються монохромні зображення, що дає можливість розглядати зображення як функцію на площині. Якщо розглянути множину точок на площині 
, де функція 
виражає в кожній точці зображення його характеристику — яскравість, прозорість, оптичну щільність, то така функція є формальним записом зображення [5].
Множина ж усіх можливих функцій на площині — є моделлю множини всіх зображень 
. Уводячи поняття подібності між образами можна поставити задачі розпізнавання. Конкретний вид такої постановки сильно залежить від наступних етапів при розпізнаванні відповідно до того або іншого підходу.
Методи розпізнавання образів та технічні системи, що реалізують ці методи, широко використовуються на практиці. Наведемо деякі з них [6]:
1) технічна діагностика. На виробництві часто виникає проблема автоматизувати контроль якості деталей. Задача полягає у тому, щоб виявити, чи є деталь дефектною, чи ні. Якщо ж з'ясовується, що деталь має дефект, часто потрібно визначити тип цього дефекту;
2) медична діагностика. Системи розпізнавання часто використовуються в медичній практиці. Найтиповіша ситуація полягає в тому, що ті чи інші захворювання діагностуються на основі аналізу кардіограм, рентгенівських знімків і т.п;
3) розпізнавання літер і чисел. Окрім усього іншого, ця проблема має велике значення для власне комп'ютерних технологій. Системи розпізнавання літер працюють разом зі сканерами — пристроями, які використовуються для введення до комп'ютера друкованих зображень і текстів. При введенні друкованого тексту сканер формує лише графічне зображення; для того, щоб створити текстовий документ, з яким може працювати текстовий редактор, необхідно впізнати на цьому зображенні окремі літери. Аналогічним чином, розпізнавання літер є необхідним для підтримки пристроїв рукописного введення. Цими пристроями, зовні схожими на звичайну авторучку, часто комплектуються над портативні комп'ютери (персональні помічники). Основна мета цих пристроїв — замінити введення з клавіатури, що є незручним для багатьох користувачів;
4) розпізнавання мови. Сьогодні інтенсивно розвиваються технології, пов'язані, по-перше, з голосовим керуванням комп'ютером, а по-друге — з введенням текстів з голосу. Робототехніка. Застосування методів розпізнавання в робототехніці є абсолютно природним і необхідним, оскільки роботи повинні безпосередньо сприймати зовнішній світ, і, відповідно, мати пристрої машинного зору;
Вихідними даними до роботи є:
- кількість основних нейронів в мережі – не менше 500,
- кількість навчальних пар сигналів – 100,
- кількість тестових пар сигналів – 50,
- кількість шаблонів вхідних сигналів – 10.
2. Розробка математичної моделі
2.1 Аналіз існуючих математичних моделей
До середини 70-х років розпізнавання як самостійний науковий напрям досяг такої стадії розвитку, що виникла можливість створення математичної теорії розпізнавання. Стисло розглянемо основні математичні моделі алгоритмів розпізнавання.
Моделі, засновані на використанні принципу розділення (R-модели). Ці моделі основани на завданні класу поверхонь, серед яких вибираються поверхня, що в деякому розумінні найкращим чином розділяє елементи різних класів.
Статистичні моделі засновані на використанні апарату математичної статистики. Застосовуються в тих випадках, коли відомі або можуть бути визначені імовірнісні характеристики класів, наприклад відповідні функції розподілу.
Моделі, побудовані на основі так званого «методу потенційних функцій» (П-моделі). Базуються на запозиченої з фізики ідеї потенціалу, визначеного для будь-якої точки простору і залежного від розташування джерела потенціалу. У качестсве функції приналежності об'єкту класу використовується потенційна функція – усюди позитивна і монотонно-убуваюча функція відстані.
Моделі обчислення оцінок (голосування) (Г – моделі) засновані на принципі часткової прецедентности. Аналізується «близькість» між частинами описів раніше класифікованих об'єктів і об'єктів, які треба розпізнати. Наявність близькості служить частковим прецедентом і оцінюється за заданим правилом (за допомогою числової оцінки) по набору оцінок близькості Виробляється загальна оцінка розпізнаваного об'єкту для класу яка і є значенням функції приналежності об'єкту класу.
Моделі, засновані на апараті алгебри логіки (Л-моделі). У них класи і ознаки об'єктів розглядаються як логічні змінні, а опис класів на мові ознак представляється у формі булевих співвідношень.
Отже, опишемо загальну математичну постановку завдання розпізнавання.
Хай дана безліч М об'єктів w. На цій множині існує розбиття на кінцеве число підмножин (класів)
Кi,, i= 1,m, M = K U m i 1 = i.
Розбиття визначено не повністю. Задана лише деяка інформація I0 про класи Ki. Об'єкти w задаються значеннями деяких ознак xj, j = 1, N. Причому цей набір ознак завжди один і той же для всіх об'єктів, що розглядаються при рішенні певної задачі. Сукупність значень ознак xj визначає опис I(w) об'єкту w. Кожна з ознак може приймати значення з різної безлічі допустимих значень, наприклад: {0, 1} – ознака не виконана або виконана; {0,1 Δ}, Δ - інформація про ознаку відсутня; {0,1...,d-1} - ступінь вираженості ознаки має різні градації, d > 2; {a1,... ad} - ознака має кінцеве число значень, d > 2; значеннями ознаки xj є функції некотрого класу. Опис об'єкту I(w)=(x1(w),...,xN(w)) називають стандартним, якщо xj(w) приймає значення з безлічі допустимих значень.
Завдання розпізнавання полягає в тому, щоб для даного об'єкту w і набору класів к1..., кm за повчальною інформацією I0(k1..., km) про класи і описом I(w) обчислити значення предикатів Pi (wKi∈), i=1,m. Інформація про входження об'єкту w в клас Ki кодується символами 1 (wKi), 0 (wKi∉), Δ (невідомо, належить w класу Ki чи ні) і записується у вигляді так званого інформаційного вектора
а(w)= (a1(w)..., am(w)), ai ∈ {0, 1 Δ}.
Алгоритм навчання Больцмана має стохастичний характер, що сприяє пошуку абсолютного мінімуму цільової функції і виходу системи зі стану локального мінімуму цільової функції. Здатність знаходити абсолютний мінімум цільової функції забезпечила широке застосування машини Больцмана для вирішення задач класифікації образів.
Мається на увазі, що в такій мережі застосовуються симетричні синаптичні зв'язки, тобто Wij=Wji.
Можна виділити два режими функціонування машини Больцмана:
- скований стан, в якому всі видимі нейрони знаходяться в станах, певних зовнішнім середовищем;
- Вільний стан, в якому всі нейрони можуть вільно функціонувати.
В процесі функціонування мережі вибирається один з вільних нейронів, і його стан змінюється з ймовірністю:
,
де E - це енергія машини, обумовлена співвідношенням:
,
а ΔE - зміна енергії машини, викликане перемиканням стану обраного нейрона. Багаторазове повторення цієї процедури призводить до досягнення машиною стану термального рівноваги.
Процедура навчання для такої мережі складається з наступних кроків:
1. Обчислити закріплені імовірності.
а) надати вхідним і вихідним нейронам значення навчального вектора;
б) надати мережі можливість шукати рівновагу;
в) запам'ятати вихідні значення (стану) для всіх нейронів;
г) повторити кроки від а до с для всіх навчальних векторів;
д) обчислити ймовірність Pij+, тобто по всій множині навчальних векторів обчислити вірогідність того, що стану обох нейронів рівні одиниці.
2. Обчислити незакріплені імовірності.
а) надати мережі можливість "вільного руху» без закріплення входів або виходів, почавши з випадкового стану;
б) повторити попередній багато разів, запам'ятовуючи стану всіх нейронів;
в) обчислити ймовірність Pij --, тобто ймовірність того, що стану обох
нейронів рівні одиниці.
3. Скорегувати ваги мережі таким чином:), 
де 
зміна ваги, а η - константа швидкості навчання.
Навчена відповідно до алгоритму Больцмана нейронна мережа має здатністю до доповнення вхідних образів. Тобто, якщо вхідний вектор з неповною інформацією надходить на вхід мережі, мережа доповнить відсутню інформацію.
Основним недоліком алгоритму навчання Больцмана є велика тривалість процесу навчання.
2.2 Розробка математичної моделі інтелектуального модуля розпізнавання рукописних символів на основі машини Больцмана
Введемо наступні позначення:
w_ij - вага між i-им нейроном
a_i - зміщення видимого нейрона
b_j - зміщення прихованого нейрона
v_i - стан видимого нейрона
h_j - стан прихованого нейрона
Ми будемо розглядати навчальну множину, що складається з бінарних векторів, але це легко узагальнюється до векторів з дійсних чисел. Припустимо, що у нас n видимих нейронів і m прихованих. Введемо поняття енергії для RBM (3.1):
(3.1)
Нейромережа буде обчислювати спільну ймовірність всіляких пар v і h наступним чином(3.2):
(3.2)
де Z - це статсума або нормалізатор (partition function) наступного виду (припустимо, у нас є всього N образів v, і M образів h)(3.3):
………………………….(3.3)
Очевидно, що повна ймовірність вектора v буде обчислюватися підсумовуванням по всіх h (3.4):
…………………(3.4)
Розглянемо вірогідність того, що при даному v одне з прихованих станів h_k = 1. Для цього представимо один нейрон, тоді енергія системи при 1 буде E1, а при 0 буде E0, а ймовірність 1 дорівнюватиме сігмоідной функції від лінійної комбінації поточного нейрона з вектором станів оглядає, шару разом зі зміщенням(3.5):
(3.5)
А так як при даному v все h_k не залежать один від одного, (3.6) то:
(3.6)
Аналогічний висновок робиться і для ймовірності v при даному h.
Як ми пам'ятаємо, мета навчання - це зробити так, щоб відновлений вектор був найбільш близький до оригіналу, або ж, іншими словами, максимізувати ймовірність p (v). Для цього необхідно обчислити приватні похідні ймовірності за параметрами моделі. Почнемо з диференціювання енергії за параметрами моделі (3.7):
………… …………..((
(3.7)
………………………
Також нам знадобляться похідні експоненти від негативної енергії (3.8):
……………………………………(3.8)
Продиференціюємо рівняння (3.9):
(3.9)
Розглянемо похідну ймовірності v по вагах (3.10):
(3.10)
Очевидно, що максимізація ймовірності це теж саме, що максимізація логарифма ймовірності, цей трюк допоможе прийти до красивого рішенням. Розглянемо похідну натурального логарифма за вагою (3.11):
(3.11)
Об'єднуючи дві останні формули, отримуємо такий вираз (3.12):
(3.12)
До множимо чисельник і знаменник кожного доданка на Z і, спростивши до ймовірностей, отримаємо такий вираз:
(3.13)
А за визначенням математичного сподівання ми отримуємо підсумковий вираз (M перед квадратною дужкою - це знак мат. очікування):
(3.14)
Аналогічно виводяться і похідні по зсувах нейронів:
(3.15)
І в підсумку виходять три правила оновлення параметрів моделі, де η- це швидкість навчання (3.16):
(3.16)
Дата добавления: 2015-09-29; просмотров: 66 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| 1-ый и 2-ой ряд - три бусинки. Вид плетения - встречное нанизание. | | | Тубулоинтерстициальный нефрит |