ОСОБЛИВОСТІ МЕТОДІВ ВИРІШЕННЯ ЗАВДАНЬ У ПСШІ
ПЕРЕЛІК ЗНАНЬ ТА НАВИЧОК
Після опанування теми студент має знати:
• моделі евристичного пошуку розв’язання, засновані на представленні завдання в просторі станів;
• індуктивні методи Д. С. Мілля;
• правила випускання несуттєвих умов, заміни констант в описі об’єктів на змінні, замикання інтервалу для числових даних, узагальнення «вгору по дереву» класифікації для структурованих фактів;
• правила «конструктивної» індукції;
• особливості завдання з технологією розв’язання, орієнтованою на ПСШІ;
• правила випускання неістотних даних;
• використання слабких методів для завдань орієнтованих на технологію ПСШІ; має вміти:
• окреслити концептуальну сферу дослідження;
• сформувати понятійний базис для вивчення всіх аспектів проблеми, що цікавить;
• пояснити модель процедурних знань — рекурсивну мережу переходів (recursive transition network (RTN)).
Розділ 3
• визначати нормалізацію функціонального графа;
• навести приклади стратегії пошуку на основі евристичної функції оцінки станів, пошуку в глибину, стратегії пошуку з відсіканнями.
ЗМІСТ ПИТАНЬ З ТЕМИ
9.1. Правила індуктивного узагальнення автоматичного формування знань
Кожна ПСШІ, автоматично формуючи знання з фактів, використовує свої специфічні правила індуктивного узагальнення, записані відповідною формальною мовою. Проте можна виділити деякі типи правил, загальні для таких систем. Відмінність полягатиме в умовах достатньої підстави для використання правил.
Правило випускання неістотних умов. При індукції через простий перелік істотними є ті умови, яким задовольняє деяка множина спостережуваних об’єктів і які потім поширюються, через індуктивне припущення, на будь-які об’єкти відповідного класу.
В індуктивних методах Д. С. Мілля істотні ознаки виділяються встановленням максимальної схожості та відмінності спостережуваних явищ, причому максимальна множина загальних ознак вважається виявленою причиною приналежності об’єкта до класу (у методі відмінності виділення множини істотних ознак відразу порушує приналежність об’єкта до відповідного класу).
Правила випускання неістотних умов найбільш використовувані в системах машинного навчання.
Правило заміни констант в описі об’єктів на змінні. Прикладом правил такого типу можуть служити: процедура антиуніфікації, правила розширення області визначення змінних і області дії кванторів.
Правило замикання інтервалу для числових даних. Нехай задано числовий інтервал [а, b] і умову ? (х), що містить єдиний числовий параметр х. Нехай далі ? (а) < ? (b) — істині. Тоді вважатимемо, що ? (х) істинне для будь-яких значень х, таких, що х ? [а, b].
Правило узагальнення «вгору по дереву» класифікації для структурованих фактів. Нехай ? (х) — умова із структурним па-
1 ), ?(х
2 ), ?(х
3 ) — істинні, то вважатимемо істинним ?(х).
Правила «конструктивної» індукції. Під «конструктивною» індукцією розуміється процедура породження нових параметрів, що характеризують спостережувані об’єкти, з початкових параметрів. Фактично це правило полягає в розширенні простору ознак на підставі вивчення відповідної вибірки об’єктів. Серед перших спроб застосування «конструктивної» індукції можна виділити такі системи, як AM, EURISKO, INDUCE.
Технологія розроблення систем ШІ в рамках аналізу ПРГ переслідує такі основні цілі: окреслити концептуальну сферу дослідження; сформувати понятійний базис для вивчення всіх аспектів проблеми, що цікавить.
Для досягнення таких цілей етап аналізу поділяється на дві стадії: добування і формалізація знань. На стадії формалізації знань здійснюється структуризація і класифікація знань, на основі яких і будується концептуальна модель ПРГ. Побудувавшиконцептуальну модель, необхідно рішення Р представити у формі такого кортежу:
Р = <Модель, Початковий_стан, [Критерій],
Рішення, Вирішальна _процедура [Доказ]>
Рішення, Вирішальна _процедура [Доказ]>
Р = <Модель, Початковий_стан, [Критерій],
Рішення, Вирішальна _процедура [Доказ]>
При цьому під станом завдання розуміється множина пар
<V i1 , V i2 >, ,1, Ii = де i відповідає множині індексів усіх термів, визначених у завданні.
Процес (спосіб) відшукання рішення називається вирішальною процедурою.
Доказ може бути потрібним як свідоцтво того, що знайдене рішення дійсно задовольняє критерію завдання або служить допустимою інтерпретацією для заданої моделі.
Особливості завдань, що вирішуються в ПСШІ, значною мірою визначають вибір методів і підходів до розв’язання задач. Завдання з технологією рішення, орієнтованою на ПСШІ, відрізняють такі особливості: модель може бути частково визначеною; критерій, як правило, відсутній; вирішальна процедура заснована на так званих слабких методах; доказ відсутній.
Часткова визначеність моделі пов’язана з недостатніми знаннями ПРГ (слабо- або середньодокументовані ПРГ). Для деяких завдань ця властивість є характерною. Наприклад, це стосуєтьсяi1 i2 ,1, Ii = значених у завданні.
Процес (спосіб) відшукання рішення називається вирішальною процедурою.
Доказ може бути потрібним як свідоцтво того, що знайдене рішення дійсно задовольняє критерію завдання або служить допустимою інтерпретацією для заданої моделі.
Особливості завдань, що вирішуються в ПСШІ, значною мірою визначають вибір методів і підходів до розв’язання задач. Завдання з технологією рішення, орієнтованою на ПСШІ, відрізняють такі особливості: модель може бути частково визначеною; критерій, як правило, відсутній; вирішальна процедура заснована на так званих слабких методах; доказ відсутній.
Часткова визначеність моделі пов’язана з недостатніми знаннями ПРГ (слабо- або середньодокументовані ПРГ). Для деяких завдань ця властивість є характерною. Наприклад, це стосується<V i1 , V i2 >, ,1, Ii = де i відповідає множині індексів усіх термів, визначених у завданні.
Процес (спосіб) відшукання рішення називається вирішальною процедурою.
Доказ може бути потрібним як свідоцтво того, що знайдене рішення дійсно задовольняє критерію завдання або служить допустимою інтерпретацією для заданої моделі.
Особливості завдань, що вирішуються в ПСШІ, значною мірою визначають вибір методів і підходів до розв’язання задач. Завдання з технологією рішення, орієнтованою на ПСШІ, відрізняють такі особливості:
• модель може бути частково визначеною;
• критерій, як правило, відсутній;
• вирішальна процедура заснована на так званих слабких методах;
• доказ відсутній.
Часткова визначеність моделі пов’язана з недостатніми знаннями ПРГ (слабо- або середньодокументовані ПРГ). Для деяких завдань ця властивість є характерною. Наприклад, це стосується
раметром х. Якщо ?(x
Крім того, деякі знання не формалізуються або погано формалізуються (слабо- або середньоструктуровані ПРГ). У певних моделях простір станів завдання не повний, через що висновки ПСШІ носять вирогідний або рекомендаційний характер.
Наявність критерію властива обчислювальним і оптимізаційним завданням, для яких існує багатий арсенал математичних детермінованих методів. Можливість використання точного математичного алгоритму взагалі не потребує допомоги експерта, виключаючи, хіба що, вибір самого алгоритму на підставі аналізу властивостей завдання. Як правило, наявність критерію і строга формалізованність моделі взаємопов’язані.
Важливим аспектом, характерним для завдань, орієнтованих на технологію ПСШІ, є використання слабких методів. До них належать:
• обмежений направлений перебір;
• виключення і відсікання;
• евристики;
• дедукція;
• індукція.
Механізм логічного висновку є тією чи іншою мірою різновидом стратегії направленого перебору. При цьому проблема полягає або у виборі відповідної продукції на кожному кроці висновку з деякої множини альтернативних продукцій, для яких виконуються частина «якщо ...» у поточному стані завдання, або у виборі нової підцілі (як, наприклад, у мові Пролог). У першому випадку висновок називається керованим даними, у другому — керованим, виходячи з мети. Детальніше ці варіанти висновку розглянуто далі.
Виключення (відсікання)
— це ефективний механізм скорочення зони пошуку. Якщо рішення не володіє властивістю Р, то всі варіанти, які встановлюють Р, або випливають з нього відкидаються. Інакше кажучи, якщо: W ? Р, де ? — імплікація, W — часткове рішення, Р — властивість шуканого рішення, то W відкидається так само як і будь-яке інше рішення U, що логічно припускає W. Відзначимо, якщо P ? W, то відсікання в цьому разі є лише правдоподібним.
Найцікавіша реалізація механізму відсікання пов’язана з побудовою пропозицій. Справедливе таке правило: «Зняття» деякої умови завдання породжує альтернативи, а «допущення» умови — знімає їх.
завдань логічного висновку, а також комбінаторних оптимізаційних завдань, з якими доводиться мати справу під час проектування складних систем, зокрема.
Завжди потрібно шукати такі умови, «зняття» яких породжує мінімум альтернатив, а «допущення» — усуває максимум альтернатив. Як випливає з теореми дедукції, гіпотеза приймається, якщо ухвалення зворотної гіпотези веде до суперечності.
Нехай F
— множина умов задачі. Нехай f — додаткові умови і {F ? f} — умови для деякої часткової задачі, рішення R якої знайдено. Це рішення буде рішенням початкової задачі, якщо F |? f, де |? — символ операції виведення. Рішення R можна вважати опорним, якщо: (F ? f) &( F ? f), тобто з F не виходить ні f, ні f.
Опорне рішення може не бути оптимальним, але воно не суперечить умовам завдання. Ефективна стратегія відсікання базується на введенні взаємовиключних умов f і f.
Хай F
— множина умов задачі. Якщо, наприклад, допущення f веде до, то автоматично передбачається f, і навпаки.
суперечності (F, {f} |?f)
При цьому раціональним варіантом відсікання є допущення такої альтернативи, яка найімовірніше не має місця (на цьому, зокрема, ґрунтується ідея доказу від осоружного).
Евристики. По суті, евристика — це емпіричне правило, ефективність якого достатня, щоб застосовувати це правило на практиці. Значну частину експертних знань представляють евристики. Евристика, наприклад, використовується для вибору продукції з множини альтернативних продукцій. Формальний механізм організації евристичного пошуку відомий під назвою Алгоритму А* Нільсона (A star). Індукція. Наступна логічна схема ілюструє механізм індукції протилежнеовстановленнеякщо,імовірно ,
А BBA? (3.2)
Ця індукційна схема встановлює, що якщо із формули А слідує В і має місце В, то ймовірно справедлива формула А, якщо не встановлено протилежне.
Розглянемо детальніше зв’язок методів розв’язання задач у ПСШІ з класами завдань, на які вони орієнтовані.
Клас 1: малий простір пошуку з надійними знаннями і даними. Для цього класу завдань основним методом рішення є вичерпний перебір. За вичерпного пошуку максимальний розмір простору пошуку залежить від часу, необхідного на проглядання одного рішення. Якщо на проглядання одного рішення витрачається 25 мс., то 10! рішень можуть бути послідовно переглянуті за 24
Клас 2: малий простір пошуку з ненадійними знаннями. У цьому випадку використовуються методи послідовного аналізу варіантів на діаграмі стану завдання. Основою методів є теорема Байеса, інші ймовірнісні підходи, наприклад метод Вальда.
Клас 3: модель завдання змінюється в часі. Наприклад, завдання планування і прогнозу вимагають міркувань про всі можливі майбутні ситуації або події. Методи цієї групи утворюють так зване ситуативне числення. Основу ситуативного численнястановить математична логіка та її сучасні варіанти, наприклад тимчасова логіка.
Клас 4: великий простір станів. Основним підходом до розв’язання задач такого типу є механізм відсікань, що використовує породження гіпотез та їх перевірку. Ключовим моментом є виконання відсікань на найбільш ранніх етапах побудови рішення, що скорочує перебір і забезпечує підвищення ефективності пошуку рішення. Існують різні стратегії, що використовують відсікання: механізм евристичного пошуку, метод гілок і меж, принцип стискаючих відображень.
Клас 5: завдання, що вимагають висунення гіпотез і правдоподібні міркування. Методи, використовувані для вирішення цих завдань, засновані на різних некласичних логіках: імовірнісної, нечіткої, немонотонної, логіки можливостей та ін. У даному розділі детально розглядаються основні методи, використовувані для рішення вказаних класів завдань.
Схема управління розв’язуванням задачі може бути або формалізована в самій моделі знань, або бути зовнішньою стосовно до неї. У першому випадку ми маємо справу з процедурними знаннями, у другому — з декларативними.
Розглянемо модель процедурних знань, відому як рекурсивна мережа переходів (recursive transition network (RTN)). Кожній дузі RTN приписаний деякий предикат (функція), дійсне значення якого необхідне для дозволу переходу по даній дузі. На кожному такті функціонування мережі проводиться оцінка всіх предикатів. При цьому порядок проглядання предикатів не має значення. У результаті визначається множина маршрутів, що сполучають початковий і кінцевий стани, переходи вздовж усіх дуг яких дозволені. Розглянемо RTN на рис. 3.1.
Вершини мережі відповідають станам системи і утворюють множину {початок S
2 , S
3 , кінець}. Переходи між станами позначені TR
1 , TR
2 , TR
3 , TR
4 і TR
5 . Переходу TR i приписаний
предикат T i (4,1=i). Крім того, з деякими з переходівпредикат T i (4,1=i). Крім того, з деякими з переходів
год. Такий розмір простору часто відповідає верхній межі для реальних завдань при повному переборі.
1 , ..., T
5 виявилися істинними. У цьому випадку всі маршрути, що зв’язують вершинупочаток і вершину-кінець, будуть дозволені й усі оператори А
2 , А
3 , А
4 , А
5 будуть виконані.
Рис. 3.1. Рекурсивна мережа переходів (recursive transition network (RTN))
При цьому обумовлюється, що порядок виконання операторів установлюється відповідно до зростання їх індексів. З іншого боку, якщо, наприклад, помилковий предикат Т
2 , то буде активований єдиний маршрут (TR
1 , TR
5 ) і, можливо, єдина дія A
5 . Отже, управління висновком в RTN реалізується за допомогою включення структури, що управляє, у модель знань.
Мережа RTN є прикладом моделі знань із вбудованою детермінованою процедурою управління. У графі І/АБО процедура управління є недетермінованою. Хай x
1 , x
2 , ..., x N
— об’єкти деякої ПРГ, причому для кожного об’єкта x i відома одна або кілька процедур його обчислення через інші об’єкти. Позначимо через ? i (x i1 , x i2 , ..., x it ) процедуру обчислення об’єкта i через об’єкти x i1 , x i2 , ..., x it . Кожний з об’єктів x i1 , x i2 , ..., x it , у свою чергу, обчислюється аналогічно через інші об’єкти і т. д. Отже, є таке функціональне відношення:
зв’язуються оператори A i , які виконуються при активації переходу. Допустимо, що всі предикати T
Очевидно, що якщо процедура ? i не має вхідних даних, то об’єкт х i являє собою деяке фіксоване значення, або запрошується у користувача. У цьому випадку:
x i = i ( ) (3.4) x i = ? i ( ) (3.4)
Співвідношенню (3.3) відповідає графічний фрагмент, поданий на рис. 3.2. Подвійна дужка на рис. 3.2 відповідає кон’юнктивній зв’язці вершин (зв’язці типу «І»). Очевидно, що цілком допустимо більше однієї процедури обчислення об’єкта x i , причому в процедурі ? j можуть брати участь інші аргументи, ніж у процедурі ? i ; графічно це зображено на рис. 3.2.
Рис. 3.2. Кон’юнктивна зв’язка вершин (зв’язки типу «І»)
Рис. 3.3. Диз’юнктивні зв’язки (зв’язки типу «АБО»)
Множина аргументів процедури ? i і ? j , утворюють диз’юнктивні зв’язки (зв’язки типу «АБО»). Для обчисленняоб’єкта достатньо процедури над однією альтернативною множиною об’єктів, що входять в одну загальну кон’юнктивну зв’язку.
Формалізуємо завдання управління на функціональному «І — АБО» графі. Нехай x
1 , x
2 , ..., x N
— множина об’єктів ПРГ. Хай дані процедури k n k nn ???...,,,
21
21 обчислення одних об’єктів через інші з числом аргументів, які дорівнюють відповідно n
1 , n
2 , ..., n k .
Визначимо стан системи S i як множина змінних, значення яких відомі на кроці i. Нехай S
0 — початковий стан, S e — кінцевий стан, причому кінцевий стан у загальному випадку позначатиметься як де * — будь-яка, наперед не обумовлювана множина змінних (можливо порожня), а x e1 , x e2 , ..., x ez
— множина змінних, які обов’язково мають бути визначені в кінцевому стані.
Стверджуємо, що процедура ? k (x k1 , x k2 , ..., x km ) застосована у стані S j , якщо (x k1 , x k2 , ..., x km ) ? S j .(3.6)
Коротко цей факт позначається як S j ? m k ?
На користь спільності далі припустимо, що кожна процедура ? i обчислює в цілому більше однієї змінної. Зрозуміло, що застосування ? i
— процедури у стані S j , в якому вона застосована,
j + 1 результативні змінні процедури ? i .
Завдання управління полягає в побудові ланцюжка процедур C = <? i0 , ? i1 , ..., ? iz > такої, яка забезпечує досягнення кінцевого стану S e з початкового стану S
0 у результаті послідовного виконання процедур із С в указаному порядку.
Позначення ? i <x i1 , x i2 , ..., x in
|x in+1 , x i+2 , ..., x im >(3.8) означає, що x i1 , x i2 , ..., x in — це вхідні об’єкти — змінні процедури, на підставі яких обчислюються вихідні об’єкти-змінні x in+1 , x in+2 , ..., x im .
Нехай задано наступну систему функцій: ii1 i2 in in+1 i+2 im означає, що x i1 , x i2 , ..., x in — це вхідні об’єкти — змінні процедури, на підставі яких обчислюються вихідні об’єкти-змінні x in+1 , x in+2 , ..., x im .
Нехай задано наступну систему функцій: in+1 x in+2 , ..., x im .
Нехай задано наступну систему функцій: in+2 im
Нехай задано наступну систему функцій: приводить у загальному випадку до нового стану S j + 1 , що містить результативні змінні процедури ? i .
Завдання управління полягає в побудові ланцюжка процедур C = <? i0 , ? i1 , ..., ? iz > такої, яка забезпечує досягнення кінцевого стану S e з початкового стану S
0 у результаті послідовного виконання процедур із С в указаному порядку.
Позначення ? i <x i1 , x i2 , ..., x in
|x in+1 , x i+2 , ..., x im >(3.8) означає, що x i1 , x i2 , ..., x in — це вхідні об’єкти — змінні процедури, на підставі яких обчислюються вихідні об’єкти-змінні x in+1 , x in+2 , ..., x im .
Нехай задано наступну систему функцій: ?
Поставимо у відповідність їй функціональний граф «І — АБО», зображений на рис. 3.4. Вершини графа відповідають об’єктам ПРГ, а дуги марковані так, що над дугою, котра виходить з вершини x i і заходить у вершину x j , стоять індекси функцій, в яких x i є вхідним аргументом, а x j — вихідним результатом. Наприклад, дугу (x
1 , x
4 ) позначено як ?
1 , ?
3 , оскільки в цих функціях x
1 є вхідним аргументом, а x
4 — вихідним. Нехай S
0 = <x
1 , x
3 , x
5 >, а S e = <x
7 , x
9 , *>. Побудову ланцюжка функцій С, що виконує перехід e C SS???
0 (3.10) робимо в два етапи.
Етап 1. Нормалізація функціонального графа.
Нормалізація полягає у виконанні в довільному порядку таких операцій, поки це можливо: (О
1 ) видалення позначок усіх тих функцій, для яких видалені одна або більше вхідних вершин-змінних; (О
2 ) видалення всіх вхідних дуг, антецедентних вершинам з S
Поставимо у відповідність їй функціональний граф «І — АБО», зображений на рис. 3.4. Вершини графа відповідають об’єктам ПРГ, а дуги марковані так, що над дугою, котра виходить з вершини x i і заходить у вершину x j , стоять індекси функцій, в яких x i є вхідним аргументом, а x j — вихідним результатом. Наприклад, дугу (x
1 , x
4 ) позначено як ?
1 , ?
3 , оскільки в цих функціях x
1 є вхідним аргументом, а x
4 — вихідним. Нехай S
0 = <x
1 , x
3 , x
5 >, а S e = <x
7 , x
9 , *>. Побудову ланцюжка функцій С, що виконує перехід e C SS???
0 (3.10) робимо в два етапи.
Етап 1. Нормалізація функціонального графа.
Нормалізація полягає у виконанні в довільному порядку таких операцій, поки це можливо: (О
1 ) видалення позначок усіх тих функцій, для яких видалені одна або більше вхідних вершин-змінних; (О
2 ) видалення всіх вхідних дуг, антецедентних вершинам з S
Поставимо у відповідність їй функціональний граф «І — АБО», зображений на рис. 3.4. Вершини графа відповідають об’єктам ПРГ, а дуги марковані так, що над дугою, котра виходить з вершини x i і заходить у вершину x j , стоять індекси функцій, в яких x i є вхідним аргументом, а x j — вихідним результатом. Наприклад, дугу (x
1 , x
4 ) позначено як ?
1 , ?
3 , оскільки в цих функціях x
1 є вхідним аргументом, а x
4 — вихідним. Нехай S
0 = <x
1 , x
3 , x
5 >, а S e = <x
7 , x
9 , *>. Побудову ланцюжка функцій С, що виконує перехід e C SS???
0 (3.10) робимо в два етапи.
Етап 1. Нормалізація функціонального графа.
Нормалізація полягає у виконанні в довільному порядку таких операцій, поки це можливо: (О
1 ) видалення позначок усіх тих функцій, для яких видалені одна або більше вхідних вершин-змінних; (О
2 ) видалення всіх вхідних дуг, антецедентних вершинам з S
Поставимо у відповідність їй функціональний граф «І — АБО», зображений на рис. 3.4. Вершини графа відповідають об’єктам ПРГ, а дуги марковані так, що над дугою, котра виходить з вершини x i і заходить у вершину x j , стоять індекси функцій, в яких x i є вхідним аргументом, а x j — вихідним результатом. Наприклад, дугу (x
1 , x
4 ) позначено як ?
1 , ?
3 , оскільки в цих функціях x
1 є вхідним аргументом, а x
4 — вихідним. Нехай S
0 = <x
1 , x
3 , x
5 >, а S e = <x
7 , x
9 , *>. Побудову ланцюжка функцій С, що виконує перехід e C SS???
0 (3.10) робимо в два етапи.
Етап 1. Нормалізація функціонального графа.
Нормалізація полягає у виконанні в довільному порядку таких операцій, поки це можливо: (О
1 ) видалення позначок усіх тих функцій, для яких видалені одна або більше вхідних вершин-змінних; (О
2 ) видалення всіх вхідних дуг, антецедентних вершинам з S
Поставимо у відповідність їй функціональний граф «І — АБО», зображений на рис. 3.4. Вершини графа відповідають об’єктам ПРГ, а дуги марковані так, що над дугою, котра виходить з вершини x i і заходить у вершину x j , стоять індекси функцій, в яких x i є вхідним аргументом, а x j — вихідним результатом. Наприклад, дугу (x
1 , x
4 ) позначено як ?
1 , ?
3 , оскільки в цих функціях x
1 є вхідним аргументом, а x
4 — вихідним. Нехай S
