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

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

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

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

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

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

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

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

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

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

,

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

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

,

де

.

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

(1)

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

, (2)

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

(3)

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

(4)

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

, (5)

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

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

(6)

Далі, для того щоб в процесі навчання синтезувати простір, в якому лінійне вирішальне правило (6) безпомилково розділило б навчальну вибірку довжини , і при цьому розмірність простору не перевищувала б < img src = "http://localhost/uploads/posts/2009-10/1255892862_Uslozhnenie_reshayushego_pravila_pri_upravlenii_v_zadachah_raspoznavaniya_obrazov_32.gif" alt = "" width = "13" height = "15" />, необхідно на ознаки накласти додаткові вимоги. Знаючи граничну розмірність простанства (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), то процедура дозволяє, при синтезі простору, використовувати не всі ознаки, а вибирати тільки ті, що розділяє сила яких дозволяє при заданих забезпечити необхідні значення