Індуктивне навчання. Узагальнення дескрипторів

ІНДУКТИВНЕ НАВЧАННЯ (ІН)

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

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

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

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

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

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

Оскільки простір пошуку припустимих описів концептів надлишковий, то можна виконати часткове упорядкування зразків, сформованих описами концептів. Найважливішим є відношення «більш подібний, ніж... чи рівний», що формулюється в такий спосіб: «зразок В більш подібний зразку А чи дорівнює йому (), коли В зіставимий з підмножиною всіх зразків, з якими зіставимий зразок А».

Найбільш ефективним поданням просторів версій є подання граничними множинами, у якому є:

-  множина максимально специфічних зразків (S);

-  множина максимально узагальнених зразків (G);

-  всі описи концептів, що знаходяться між цими двома крайніми множинами.

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

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

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

Таким чином, у процесі навчання межі монотонно «рухаються» назустріч одна одній. Переміщення S у напрямку більшої спільності можна розглядати як виконання пошуку в ширину від специфічних зразків до більш загального. Мета пошуку – сформувати нову граничну множину, що матиме мінімально достатню спільність, щоб «охопити» новий позитивний екземпляр навчальної вибірки. Тобто межа S переміщається якщо новий позитивний екземпляр у навчальній вибірці не зіставимий з жодним зі зразків у множині S. Так само і переміщення межі G у напрямку більшої специфічності можна розглядати як пошук у ширину від більш загальних зразків до більш специфічного. Мета такого пошуку – сформувати нову граничну множину, що матиме мінімально достатню специфіку, щоб не «накрити» черговий негативний екземпляр у навчальній вибірці. Корекція межі G відбувається в тому випадку, коли програма виявляє, що черговий негативний екземпляр зіставими з яким-небудь зразком у G.