Ускладнення вирішального правила при управлінні у задачах розпізнавання образів

Бекмуратов К.А.

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

У роботі [1] описаний метод формування простору безперервних ознак, що приводить до безпомилкового поділу образів. Введено поняття безперервного ознаки і показано, що якщо набирати простір тільки з визначених у [1] ознак, то можна досягти безпомилкового поділу образів.

У даній роботі так само, як і в [2], розглянемо випадок, коли в просторі безперервних ознак розмірності n безпомилкове роздiлення навчальної послідовності неможливо.

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

Припустимо, що - Підмножина на , Відповідне конкретному способу , А - Підмножина на , Відповідне іншим чином

Потрібно з використанням навчальну вибірки знайти вирішальне правило , Яке вказує приналежність будь-якого об'єкта з одному

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

Якщо навчальна послідовність не може бути безпомилково роздільна обраним вирішальним правилом, то в загальному випадку справедлива теорема Вапніка - Червоненкіса [3], зміст якої полягає в тому, що якщо в n-мірному просторі ознак вирішальне правило здійснює помилок при класифікації навчальної послідовності довжини , То з ймовірністю можна стверджувати, що ймовірність помилкової класифікації складе величину, меншу ,

,

де N-число всіляких правил заданого класу, яке можна побудувати у просторі заданої розмірності.

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

,

де

.

Логаріфміруя отримаємо

(1)

Якщо врахувати , То (1) набуває вигляду

, (2)

де можна оцінити у вигляді

(3)

Підставляючи (3) в (2), отримуємо

(4)

Використовуючи теорему Вапніка-Червоненкіса [3], можна обчислити граничну розмірність простору

, (5)

яка при заданих гарантує необхідні e і h.

Нехай обчислено максимально допустиме значення розмірності простору у вигляді (5) і в цьому просторі фіксована лінійна вирішальна функція

(6)

Далі, для того щоб у процесі навчання синтезувати простір, в якому лінійне вирішальне правило (6) безпомилково розділило б навчальну вибірку довжини , І при цьому розмірність простору не перевищувала б , Необхідно на ознаки накласти додаткові вимоги. Знаючи граничну розмірність простанств (8), можна оцінити мінімально допустиму розділяє силу кожного обраного ознаки у вигляді

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

Припустимо, що в синтезованому просторі безперервних ознак розмірності n лінійна вирішальна функція (9) робить помилки з частотою . Тоді розглянемо співвідношення

, (7)

де N * - відповідає вирішального правилом, що працює з частотою помилки , N **- безпомилково розділяє навчальна послідовність довжини .

З використанням цього співвідношення, можна встановити доцільність ускладнення вирішального правила у разі, якщо в просторі розмірності n ще не досягнуто безпомилкове поділ навчальної вибірки.

Відомо [3], що якщо замість лінійного правила використовується кусково-лінійне і воно безпомилково поділяє навчальну вибірку довжини l, то відповідно (7) замість n слід вибирати величину

n = nk + k, (8)

де k - число лінійних вирішальних правил, складових шукане кусково - лінійне правило. Використовуючи співвідношення (7) і (8), відповімо на запитання: чи варто ускладнювати рішення, якщо лінійне правило в просторі розмірності n не забезпечує безпомилкового поділу навчальної вибірки. Для цього потрібно зробити підстановку:

, (9)

У цьому випадку ускладнення вирішального правила, що визначається числом k, не призведе до зниження ймовірності помилки, якщо буде виконано співвідношення (7) після підстановки (8). З цієї умови можна знайти таке значення k, вище якого втрачає всякий сенс ускладнення вирішального правила, що діє в просторі безперервних ознак розмірності n:

. (10)

Таким чином, якщо вибирати n і k згідно (5) і (10), то процедура дозволяє, при синтезі простору, використовувати не всі ознаки, а вибирати тільки ті, що розділяє сила яких дозволяє при заданих забезпечити необхідні значення ε і η.

Список літератури

1. Бекмуратов. К.А. Процедура формування безперервних ознакових просторів при послідовному навчанні. Узб. Журнал / / «Проблеми інформатики та енергетики» .- 1994 .- № 4.-С.17-20.

2. К.А. Бекмуратов. Покрокова перевірка доцільності ускладнення вирішального правила при послідовному навчанні задачі розпізнавання. Узб. Журнал / / «Проблеми інформатики й енергетики». -2000. - № 1. - С. 16-19.

3. Вапнік В.М., Червоненкіса А.Я. Теорія розпізнавання образів. (Статистичні проблеми навчання). - М.: Наука, 1974. -С. 415.