424. Геометричний метод розпізнавання (Розпізнавання образів і навчання)

Досягнення в галузі програмних засобів обробки відеоінформації для роботів відкривають нові перспективи як для автомобільної, так і для інших галузей промисловості. Ці досягнення пов'язані з геометричним методом розпізнавання об'єктів, який усуває деякі недоліки технологій машинного зору. У системах машинного зору використовуємо метод виявлення, який розпізнає будь-який предмет, незалежно від розміру і форми. Цей метод має назву PatMax. PatMax може точно розпізнавати об'єкти, коли їх розміри варіюються, обриси розмиті, і навіть коли вони знаходяться частково поза полем зору. Традиційні машинні системи відеоідентифікацією грунтувалися на піксельної-растровому аналізі, так званої кореляції. Принцип роботи методу PatMax полягає в зіставленні еталонної моделі предмета з самим чином предмета. Обчислюється та позиція об'єкта в системі координат XY, в якій він найбільш точно збігається з моделлю, і, виходячи з цього, визначається місцезнаходження предмета. На виробництві, в умовах нерівномірного освітлення та утрудненою видимості, кореляційні методи не спрацьовують. Замість кореляції PatMax використовує геометричну інформацію. Він, наприклад, інтерпретує квадрат як чотири прямих відрізка, а футбольний м'яч v як дві дуги. Для цього застосовуються триступінчаті геометричні вимірювання. Спочатку PatMax ідентифікує і відокремлює від фону ключові видимі риси об'єкта і визначає його форму, розміри, кути, вигини і ступінь затінення. Після цього зіставляються просторові відносини об'єкта і шаблону. Аналізуючи геометричну інформацію, метод PatMax дозволяє точно і багаторазово визначати розташування об'єкта, не дивлячись на його розмір і зовнішній вигляд.

425. Індуктивний алгоритм побудови дерева рішень id3 (Машинне навчання, засноване на символьному представленні інформації)

Алгоритм ID3 подібно методом виключення кандидата забезпечує вивчення понять на прикладах. Особливий інтерес представляють спосіб зберігання отриманих знань, підхід до управління складністю, евристика для вибору понять- кандидатів і можливості обробки зашумлених даних. В алгоритмі ID3 поняття представляються у вигляді дерева рішень (decision tree). Таке представлення дозволяє класифікувати об'єкт шляхом перевірки значення певних властивостей. Маючи набір навчальних прикладів і кілька дерев рішень, що дозволяють коректно класифікувати ці приклади, слід вибрати дерево, яке з найбільшою ймовірністю дозволить коректно класифікувати невідомі екземпляри. За алгоритмом ID3 таким деревом вважається найпростіше дерево рішень, покриває всі навчальні приклади. В основу такого припущення покладена перевірена часом евристика, згідно з якою перевагу віддається простоті без додаткових обмежень. Цей принцип уперше був сформульований у 1324 році філософом-схоластом Вільямом з Оккама (William of Occam) і отримав назву "бритви Оккама "(Occam's Razor)." Нерозумно докладати більше зусиль, ніж потрібно для досягнення мети ... Не варто примножувати суті понад необхідного ". Більше сучасна версія цього принципу зводиться до вибору найпростішого відповіді, відповідного вихідними даними. У даному випадку це найменше дерево рішень, яке дозволяє коректно класифікувати всі наявні приклади. Аналіз алгоритму ID3. Незважаючи на те що алгоритм ID3 будує просте дерево рішень, зовсім не очевидно, що за допомогою цих дерев можна ефективно класифікувати невідомі приклади. Тому алгоритм ID3 був протестований на контрольних прикладах і реальних додатках. Тести підтвердили його гарну працездатність. Наприклад, у роботі (Quinlan, 1983) досліджена продуктивність алгоритму ID3 на прикладі задачі класифікації ендшпілі при грі в шахи. У прикладах ендшпілі брали участь білі король і тура і чорні король і кінь. Завданням алгоритму було навчитися розпізнавати позиції, призводять до ураження чорних за три ходи. У Як властивостей використовувалися різні високорівневі ознаки, такі як "Неможливість безпечного переміщення короля". При цьому враховувалися 23 подібних ознаки. З урахуванням симетрії область визначення завдання включає 1,4 мільйона різних позицій, серед яких 474 тисячі призводять до ураження чорних за три ходи. Алгоритм ID3 будував дерево на випадково вибраному навчальній множині і тестувався на 10000 різних комбінацій, які теж вибиралися випадковим чином. Результати тестування наведені в табл. 9.2. Більш докладний аналіз результатів тестування наводиться в роботі (Quinlan, 1983). Ці результати підтверджуються й іншими тестами і конкретними додатками. Існують варіанти алгоритму ID3, що дозволяють вирішувати завдання в умовах зашумить- лених даних і дуже великих навчальних множин.