Основи проектування систем штучного інтелекту:Іспит
Матеріал з USIC Wiki
|
Ця стаття відноситься до групи довідкових статей для студентів ФІН. |
Базові поняття штучного інтелекту. Алгоритмічний та декларативний підходи до програмування.
Під інтелектом у першому наближенні мається на увазі здатність до розумової діяльності - як на свідомому, так і на підсвідомому рівні. Штучно створені пристрої, здатні до розумової діяльності або принаймні до вирішення окремих задач, характерних для людського мозку, можна охарактеризувати як “штучний інтелект”. Прагматичний аспект: створення пристроїв або програм, які б допомагали людині у вирішенні тих чи інших задач. Тісно пов’язаний з проблемою автоматизації. Основний напрямок розвитку інформаційних технологій - їх інтелектуалізація, тобто наділення комп’ютерних систем здатністю до вирішення інтелектуальних задач; перехід від алгоритмічного стилю програмування до декларативного.
Алгоритмічний та декларативний підходи до програмування і керування
алгоритмічний - “як” вирішувати задачу; необхідність детального розписування інструкцій;
декларативний - “що” треба робити; формулюється постановка задачі (мета), а виконавець сам виробляє та реалізує алгоритм вирішення цієї задачі; для цього він повинен мати або отримати певну суму знань.
Одна з центральних тем теорії та практики штучного інтелекту є методи розв’язання недостатньо формалізованих задач.
- відсутність задовільної моделі (формалізованого опису) предметної області;
- відсутність постановки задачі, або цю постановку важко формалізувати;
- відсутні або невідомі ефективні методи розв’язання задачі, які дозволили б прийняти рішення за прийнятний час і врахувати всі ситуації, які можуть виникнути.
Інша проблема - ми хочемо, щоб система штучного інтелекту вирішувала задачу не будь-яким чином, а діяла б так, як діяла б на її місці людина - з урахуванням практичної доцільності; правових, морально-етичних та інших норм. Визначення Мінського: ШІ - це дисципліна, яка вивчає можливість створення програм для вирішення задач, які при вирішенні їх людиною потребують інтелектуальних зусиль. Уточнення: “сюди не входять задачі, для яких відома процедура їх вирішення”.
Евристичний пошук. Планування в просторі задач і в просторі станів.
Інтуїтивно - “метод проб та помилок”, систематизований перебір варіантів можливих дій.
- Спробувати перший варіант.
- якщо підходить - в залежності від постановки задачі або прийняти його як остаточний, або розвинути далі.
- Якщо ні - спробувати інший варіант.
- Задача про виконуваність булевого виразу, про 8 ферзів і т.п.
- Досить типовим є застосування бектрекінгових алгоритмів.
Евристичний пошук: продовження
- Складність задачі; експоненційне зростання дерева перебору.
- Ключовими є проблеми скорочення перебору та підвищення цілеспрямованості пошуку.
- Важливе значення має інформованість алгоритму пошуку, тобто наявність тієї чи іншої додаткової інформації, врахування якої дозволяє відкинути гілки, які завідомо не призведуть до результату, або упорядкувати пошук так, щоб в першу чергу розглядалися найбільш перспективні гілки.
- Обмежуючі правила та евристики.
- Важливий тип евристик - “жадібні” алгоритми.
Пошук вглиб – стек, вшир – черга: неінформований пошук
Планування
Термін планування тут розглядається в дещо звуженому значенні, а саме - знаходження послідовності операцій, за допомогою яких можна розв’язати задачу (або знаходження плану вирішення задачі).
Потрібно: формалізовані описи станів (ситуацій) та певний набір можливих операцій. Проблема в такому випадку описується на основі дерева або графу, і багато методів планування грунтуються на евристичному пошуку на дереві або графі. Граф або дерево може бути заданий експліцитно (явно) або імпліцитно (вершини можуть породжуватися динамічно). Два основні принципи планування:
- в просторі станів;
- в просторі задач.
Планування в просторі станів
Основний принцип: розв’язок задачі зводиться до пошуку на графі станів. Граф станів задачі - це граф, вершини якого відповідають ситуаціям, які виникають або можуть виникнути в ході розв’язку задачі, а дуги відповідають операціям, які дозволяють перейти від одного стану до іншого. Основна проблема - побудувати модель предметної області у вигляді графа станів. Якщо ж така модель побудована, то розв’язок задачі - це шлях від початкової вершини (яка відповідає початковій ситуації) до цільової вершини (яка відповідає цілі), якщо цей шлях проінтерпретувати відповідним чином. В тому числі може бути поставлено питання про найкоротший шлях
Планування в просторі задач
Основна ідея - розбиття (декомпозиція) початкової задачі на підзадачі; кожна з них розбивається далі, поки ми не дійдемо до елементарних задач, для яких є готові процедури розв’язку (якщо це можливо).
В основі - формалізм І-АБО-графів
І-АБО-граф - це орієнтований граф, вершини якого відповідають задачам предметної області, а дуги - зв’язкам між ними. Точніше, якщо для вирішення задачі А потрібно вирішити або задачу В, або задачу С, то в графі є дуги (А,В) та (А,С), зв’язані відношенням АБО. Якщо ж для вирішення задачі А потрібно вирішити і задачу В, і задачу С - дуги (А,В) та (А,С) пов’язані відношенням І. І-вершини та АБО-вершини.
Елементарна задача - задача, для якої існує готова процедура розв’язку.
Тупикова задача - задача, для якої готової процедури розв’язку не існує, і вона не може бути розбита на підзадачі.
Вершина називається розв’язною, якщо пов’язана з нею задача має розв’язок.
Розв’язок задачі (точніше - план розв’язку) можна уявляти собі як побудову підграфа (як правило, дерева), корінь якого відповідає початковій задачі, а листки - елементарним задачам.
Елементарна вершина є розв’язною. АБО-вершина є розв’язною, якщо розв’язною є хоча б одна з її дочірніх вершин. І-вершина є розв’язною, якщо розв’язними є всі її дочірні вершини. Одне з найбільш відомих застосувань І-АБО-графів - символьні обчислення, зокрема - символьне інтегрування. Вираз розбивається на підвирази, які інтегруються незалежно один від одного; окремі операції відповідають типовим підстановкам або іншим перетворенням.
Ігрові задачі. Мінімаксна процедура; альфа-бета-відтинання.
Ігрові задачі тісно пов’язані з прийняттям рішень: вибір чергового ходу - це не що інше, як прийняття рішень. Характерна особливість - наявність суперника, який перешкоджає здійсненню цілей. В ряді випадків ігрові задачі можна описати на основі І-АБО-графів (подумайте, як).
Теорія ігор - математична дисципліна, яка вивчає методи прийняття рішень в умовах конфлікту. Під конфліктом мається на увазі ситуація, коли гравці мають різні цілі та мають різні засоби (стратегії) для досягнення цих цілей
Функція виграшу гравця визначає його виграш в ситуації, коли гра закінчилася, відповідно до правил гри. Цей виграш безпосередньо залежить від того, які рішення він приймав на протязі гри (яку стратегію він обирав).
Ми будемо розглядати ігри двох осіб.
Гра називається грою з нульовою сумою, якщо для будь-якої завершальної ситуації сума виграшів усіх гравців дорівнює нулю.
Антагоністична гра - це гра двох осіб з нульовою сумою. В антагоністичній грі виграш одного гравця дорівнює програшеві суперника, і ми можемо розглядати лише функцію виграшу першого гравця. Неформально: матрична гра - це антагоністична гра двох осіб, в якій кожний гравець має скінченну множину стратегій. Кожний з гравців вибирає одну з своїх стратегій незалежно від інших; стратегії обираються одночасно; результат гри (функція виграшу) визначається тим, яку стратегію вибрав кожний гравець.
Матричні ігри зручно характеризувати матрицею виграшів.
- Можливі дії (стратегії) першого гравця: a1, …, am.
- Можливі дії (стратегії) другого гравця : b1, …, bn.
- Матриця виграшів: M={Mik}, Mik - виграш першого гравця, якщо він вибирає стратегію ai , а суперник - стратегію bk .
a <- maxi mink Mik - максимінна стратегія першого гравця;
b <- mink maxi Mik - мінімаксна стратегія другого гравця.
Ситуація є нестійкою; гра не має розв’язку (в чистих стратегіях).
Пара (a1, b2) - ситуація рівноваги, сідлова точка - тобто a1 та b2 - оптимальні стратегії для кожного гравця. Є рішенням гри. Оптимальна стратегія гравця - стратегія, яку йому невигідно змінювати за умови, що його суперник буде притримуватися своєї оптимальної стратегії. Матрична гра не завжди має рішення в чистих стратегіях (але завжди має рішення в змішаних). Позиційна гра передбачає послідовну зміну позицій; гравці роблять ходи по черзі на основі аналізу поточної позиції; кожний хід призводить до нової позиції.
Основні методи аналізу полягають в побудові та аналізу дерева гри.
Дерево аналізу
- кожна вершина відповідає позиції;
- корінь дерева відповідає позиції, яка аналізується; листки - завершальним позиціям;
- дуги відповідають ходам гравців. Точніше, якщо існує хід з позиції А до позиції В, то В є сином А.
Має наступні особливостіЖ
- функція виграшу, визначена на завершальних позиціях;
- ми розглядаємо тільки антагоністичні позиційні ігри;
- альфа-гравець і бета-гравець; відповідно, альфа-вершини і бета-вершини;
тоді функція виграшу задає виграш альфа-гравця в даній завершальній позиції;
Оптимальний варіант - послідовність ходів, яка призводить до певного визначеного результату, і відхилятися від якої невигідно жодному з гравців.
Оптимальна стратегія полягає в виборі ходів, які лежать на оптимальному варіанті (починаючи з позиції, що аналізується).
Клас позиційних ігор двох осіб, для яких існує оптимальна стратегія
- антагоністичні;
- скінченні (в кожній позиції гравець має скінченну кількість стратегій, гра закінчується за скінченну кількість ходів;
- детерміновані (перебіг гри та вибір ходу не залежать від випадкових чинників);
- з повною інформацією.
Отже, для ігор даного класу результат гри для будь-якої позиції є наперед визначеним (за умови, що обидва гравці грають оптимальним для себе чином). Якщо ж хтось відхилиться, він від цього тільки втратить.
Таким чином, для кожної позиції визначена мінімаксна функція, яка задає мінімаксну оцінку - виграш альфа-гравця в цій позиції. Мінімаксна оцінка може бути отримана для будь-якої позиції за допомогою мінімаксної процедури. Відповідно, може бути отриманий і оптимальний варіант, починаючи з цієї позиції.
Мінімаксна оцінка завершальних (листових) вершин дорівнює функції виграшу.
Мінімаксна оцінка нелистової позиції дорівнює найкращій мінімаксній оцінці її синів. Точніше, мінімаксна оцінка альфа-вершини дорівнює максимумові мінімаксних оцінок її синів, бета-вершини - мінімумові мінімаксних оцінок її синів.
Відповідно, найкращий хід повинен бути зроблений до дочірньої вершини з найкращою оцінкою.
Основна характеристика складності - кількість завершальних позицій, які аналізуються.
Якщо коефіцієнт розгалудження (кількість ходів з кожної позиції) дорівнює b, а глибина дерева аналізу (кількість півходів на кожному варіанті) дорівнює d, то потрібно проаналізувати bd завершальних позицій. Обмеження глибини перебору
Ідея - обмежити кількість півходів у кожному варіанті, тобто припиняти аналіз, коли довжина варіанту стає більшою за задану величину d (наз. глибина перебору).
Отже, до усікненого дерева аналізу включаються лише позиції, відстань від яких до кореня дерева аналізу не перевищує d.
Горизонтом називається множина позицій, відстань від яких до кореня дерева аналізу точно дорівнює глибині перебору d.
Ясно, що позиції, які лежать на горизонті, як правило, не є завершальними для повного дерева (хоча можуть виявитися такими). З іншого боку, не всі позиції, що є завершальними для усікненого дерева, лежать на горизонті. Абсолютно завершальними називатимемо позиції, в яких гра завершується, тобто позиції, завершальні для повного дерева аналізу. Відносно завершальними називатимемо позиції, які є завершальними для скороченого дерева гри, але не для повного дерева. Основна проблема: для відносно завершальних позицій результат гри ще не є відомим. Тому замість функцій виграшу для оцінки таких позицій використовуються статичні оцінки, отримані на основі статичних оціночних функцій.
Статичною оціночною функцією називається функція, яка залежить виключно від самої позиції та не враховує динаміки гри. Часто використовуються лінійні статичні оціночні функції: зважені суми значень факторів, які впливають на оцінку позиції. Статичні функції залежать від самої гри. Вони повинні бути підібрані належним чином.
Існують підходи до автоматизованого підбору статичних оціночних функцій (приклад - програма Семюеля для гри в шашки; 1968 р). Для усікненого дерева
- Мінімаксна оцінка абсолютно завершальних позицій дорівнює функції виграшу; мінімаксна оцінка відносно завершальних позицій обчислюється за допомогою статичної оціночної функції.
- Мінімаксна оцінка нелистової позиції дорівнює найкращій мінімаксній оцінці її синів. Точніше, мінімаксна оцінка альфа-вершини дорівнює максимумові мінімаксних оцінок її синів, бета-вершини - мінімумові мінімаксних оцінок її синів.
- Відповідно, найкращий хід повинен бути зроблений до дочірньої вершини з найкращою оцінкою.
Альфа-бета відтинання
Альфа-бета-процедура є по суті мінімаксною процедурою з використанням альфа-бета-відтинань. Ключова ідея: припинення аналізу вершин, про які стає відомо, що вони не можуть лежати на оптимальному варіанті.
Відтинанням у деякій вершині називається припинення аналізу цієї вершини разом з усіма її наступниками. З кожною вершиною пов’язується попередня оцінка, яка змінюється в ході аналізу. На початку роботи алгоритму попередня оцінка альфа-вершини дорівнює -∞; бета-вершини - +∞. Надалі попередня оцінка альфа-вершини може тільки зростати, бета-вершини - тільки зменшуватися.
Оцінка вершини стає остаточною, коли проаналізовані всі її наступники або коли в цій вершині відбулося відтинання. Попередня оцінка альфа-вершини дорівнює максимумові з остаточних оцінок синів, бета-вершини - мінімумові. Вона переглядається щоразу, коли дочірня вершина набуде остаточної оцінки.
- Відтинання в альфа-вершині відбувається, коли попередня оцінка цієї вершини стає не меншою, ніж деякого бета-попередника цієї вершини.
- Відтинання в бета-вершині відбувається, коли попередня оцінка цієї вершини стає не більшою, ніж деякого альфа-попередника цієї вершини.
- Варіант: не будь-якого бета (альфа) - попередника, а тільки батька.
Альфа-бета-відтинання є найбільш ефективними (тобто забезпечують максимальне скорочення перебору), якщо в першу чергу аналізуються найкращі ходи. Оцінка максимальної ефективності
Кількість завершальних позицій, які доводиться аналізувати: 2bd/2 -1 для парних d;
b(d+1)/2 + b(d-1)/2 -1 для непарних d.
Приблизно - подвоєний квадратний корінь від загальної кількості завершальних вершин. Зокрема, при заданих часових обмеженнях приблизно вдвічі збільшується глибина перебору.
Порядок перебору
Найпростіший підхід - в першу чергу розглядати дочірні вершини з найкращими статичними оцінками.
Поняття знань. Властивості знань і моделі подання знань.
Інформаційна система (ІС) - сукупність засобів, які забезпечують операції, пов’язані зі збором, зберіганням та обробкою даних, а також доступ до цих даних користувачів.
Інтелектуальна (інтелектуалізована) інформаційна система - це інформаційна система, в якій у тій чи іншій мірі реалізовані певні елементи штучного інтелекту. В першу чергу - подання знань і дедуктивне логічне виведення.
Традиційні ІС спираються на роботу з даними. Інтелектуальні інформаційні системи - системи, що базуються на знаннях (knowledge-based systems); орієнтовані на роботу зі знаннями. Магістральний напрямок розвитку ІС - перехід від даних до знань.
- Знання - інформаційна основа інтелектуальних систем.
- Знання - це систематизована інформація, яка може певним чином поповнюватися, і на основі якої можна отримувати нові знання.
- Знання - високоорганізована інформація про об’єкти та поняття предметної області, їх властивості та зв’язки між ними.
Властивості знань
- внутрішня інтерпретованість;
- структурованість;
- зв’язність;
- шкальованість;
- семантична метрика;
- активність.
База знань (БЗ) - сукупність знань, записаних у деякому формалізованому вигляді на основі тієї чи іншої мови подання знань, що зберігається в пам’яті інформаційної системи.
Система управління базою знань - сукупність засобів, які дозволяють зберігати знання в БЗ, отримувати інформацію з БЗ та маніпулювати знаннями.
Інформаційна одиниця - відображення певного об’єкта або поняття предметної області в БЗ. Просто ім’я або деякий опис.
База знань - це формальне уявлення розумового образу предметної області в інформаційній системі.
Основні компоненти: множина сутностей предметної області, перелік їх властивостей та зв’язки між ними (статична схема, яка визначає можливі стани), актуальний стан (наповнення схеми конкретними фактами), можливі переходи з одного стану до іншого (динаміка).
Концептуальна схема - формальне уявлення в базі знань сукупності суджень, які характеризують множину можливих станів предметної області та множину можливих переходів предметної області з одного стану до іншого. Концептуальна база - формальне уявлення в базі знань сукупності суджень, які характеризують конкретний актуальний стан предметної області.
База знань - це сукупність концептуальної схеми та концептуальної бази. Класичні моделі подання знань
- логічні моделі;
- продукційні системи;
- семантичні мережі;
- фреймові моделі.
Загальні підходи до проектування інтелектуальних ІС
- чисто логічний підхід на основі логіки предикатів;
- онтологічний та об’єктно-орієнтований аналіз.
Логічний підхід до подання знань. Автоматичне доведення теорем на основі методу резолюцій
В основі - логіка предикатів (найчастіше - першого порядку). Предикатом називається функція, яка в залежності від значень своїх змінних набуває одне з двох значень: 0 (інтерпретується як хибність) та 1 (інтерпретується як істинність).
Два типи тверджень: факти і правила: Факт - конкретна інформація про ту чи іншу інформаційну одиницю; ця інформація зберігається в пам’яті системи в явному вигляді та може бути знайдений безпосереднім пошуком; без залучення логічного виведення та інших подібних механізмів. Правило - твердження, яке дозволяє отримувати інші твердження, які в системі явно не фігурують; зокрема, на основі логічного виведення.
Екстенсіональні та інтенсіональні знання Екстенсіональні знання - сукупність явно заданих фактів. Інтенсіональні знання - сукупність правил, які дозволяють отримувати нові твердження.
Два типи запитів: перевірка істинності того чи іншого конкретного твердження; пошук значень змінних, які задовольняють умові запиту; в результаті відповідні змінні набувають конкретних значень, або відбувається конкретизація змінних.
Механізм логічного виведення: Потрібний певний механізм, який забезпечує логічне виведення (часто наз. машиною виведення). Пролог надає такий вбудований механізм, що грунтується на бектрекінгу (переборі з поверненням). Зворотне логічне виведення (від мети до фактів). Математична основа - метод резолюцій (Робінсон, 1965 р).
Відоме вербально-дедуктивне визначення знань Знання - це трійка <F,P,M>, де F - сукупність явних фактів, які задають властивості окремих інформаційних одиниць та зберігаються в БЗ в явному вигляді; P - сукупність правил, які дозволяють шляхом логічного виведення отримати нові твердження на основі існуючих; M - механізм логічного виведення.
Логічний підхід: основна проблема: Основна проблема чисто логічного підходу до проектування інтелектуальних ІС - недостатність та недосконалість засобів для задання структури інформаційних одиниць та зв’язків між ними. Зокрема, всі зв’язки за замовченням обробляються однаково і т.п. В принципі, можна відобразити, але потрібно знати, що саме і як відображати. Зокрема, такий аналіз зумовив би більш чітку і раціональну систему предикатів.
Автоматизація дедуктивних логічних побудов: Одна з постановок - автоматичне доведення теорем. Тут ми розглядаємо базу знань як логічну теорію, тобто як сукупність аксіом і правил виведення. Формули вважаємо правильно побудованими. Постановка задачі: дана теорія S. Потрібно встановити, чи є твердження q теоремою, тобто чи можна його логічно вивести з аксіом теорії після скінченного числа застосувань правил виведення.
Автоматичне доведення теорем і логічне програмування Механізм автоматичного доведення теорем лежить в основі логічного програмування і прологівського механізму виконання програм. ПРОЛОГ - декларативна мова програмування, в основі якої лежить концепція логічного програмування. Основна ідея логічного програмування - програма розглядається як певна теорія, тобто як певний набір тверджень (аксіом і правил виведення); виконання програми є доведенням певної теореми (або перевіркою певного твердження). Іншими словами, ціль прологівської програми - перевірка істинності певного твердження (доведення теореми). Аксіоми по суті відповідають прологівським фактам; правила виведення - прологівським правилам. Найбільш відомий метод - метод резолюцій (Робінсон, 1965 р).
Метод резолюцій: основні визначення:
Атомарна формула (літерал) - предикат, який залежить від певної кількості аргументів - термів: констант, змінних і функторів (тобто функціональних символів від термів).
Літерал негативний, якщо він стоїть під знаком заперечення; позитивний - якщо не стоїть.
Диз’юнкт (фраза) - диз’юнкція певної кількості літералів.
Пустий диз’юнкт ?(квадратик), який не містить літер. Якщо теорія містить ? (або з теорії можна вивести ?), то вона суперечлива.
Позначення: константи будемо позначати першими літерами латинського алфавіту (a,b,…); змінні - останніми (x,y,z).
Метод резолюцій: загальні слова: Метод резолюцій полягає в послідовному виконанні резолюцій, в кожній з яких беруть участь дві фрази, поки не буде досягнено певного результату. Метод резолюцій працює з формулами, записаними у вигляді набору фраз, тобто диз’юнкцій літералів, що не містять кванторів (кожна фраза - безкванторна диз’юнкція атомарних формул). Є певна послідовність перетворень, яка дозволяє звести будь-яку формулу числення предикатів до такої форми.
Основні кроки зведення: Усунення імплікацій та тотожностей. Втягнення заперечень всередину (зведення до вигляду, коли всі заперечення знаходяться тільки над літералами). Перейменування змінних (щоб не було випадкового співпадіння імен змінних в області дії кванторів). Зведення до пренексної нормальної форми: K1 … Kn M(x1, …, xn), де M - формула, яка містить тільки кон’юнкції та диз’юнкції атомарних формул і не містить кванторів. Усунення кванторів існування (сколемізація, введення констант і функцій Сколема). Усунення кванторів узагальнення. Зведення до кон’юнктивної нормальної форми. Розділення кон’юнкцій.
Сколемізація: Якщо квантор існування не стоїть в області дії квантора узагальнення - константа Сколема: від існує x P(x) до P(c). В іншому випадку - функція Сколема: від будь-який y існує x: P(x,y) до P(h(y),y). Перетворення не еквівалентні, але можна довести наступне: Теорія А суперечлива тоді і тільки тоді, коли невиконувана її сколемівська форма SA.
Зведення до КНФ: Від A або (B&C) до (A або B) &(A або C).
Правило резолюцій: Фраза Хорна - це диз’юнкт, який містить не більш ніж один позитивний літерал. Дозволяє здійснити окрему резолюцію над двома твердженнями. Це правило для предикатів є розширенням правила Девіса і Патнема для висловлювань. Правило Девіса і Патнема. Резольвента двох фраз утворюється як диз’юнкція цих фраз, з яких викреслюється контрарна пара. Дві фрази містять контрарну пару, якщо одна з них містить позитивний літерал, а інша - негативний з тим самим предикатним ім’ям.
Алгоритм автоматичного доведення теорем на основі методу резолюцій: Дана теорія, або набір тверджень S. Треба перевірити істинність твердження q (точніше, чи є q логічним наслідком S). Сама теорія S при цьому має бути несуперечливою. Фактично - доведення від супротивного. Утворюється пробна теорія S’ шляхом додавання до S заперечення q: S’ := S U { !q}. Послідовно здійснюються резолюції, їх результати (резольвенти) додаються до пробної теорії. Якщо на певному кроці утворюється пустий диз’юнкт, то S’ суперечлива, і відповідно, твердження q істинне. Якщо чергову резолюцію здійснити неможливо - q хибне.
Повнота методу резолюцій: Теорія S суперечлива тоді і тільки тоді, коли з неї можна вивести пустий диз’юнкт. Це означає, що якщо твердження істинне, то алгоритм рано чи пізно доведе, що воно є істинним. Числення предикатів є алгоритмічно нерозв’язним, і тому можуть бути твердження, для яких алгоритм працюватиме нескінченно довго.
Продукційні системи. Цикл "співставлення-дія"; пряме та зворотне логічне виведення.
Продукційні моделі і системи пов’язуються з іменем Поста. Продукційна модель передбачає подання знань у вигляді набору продукцій (або продукційних правил). Кожне продукційне правило - це правило типу “якщо А, то В”. Продукція описується як п"ятірка виду: (i) Q;P;K;N,
де (i) - номер продукції; Q - сфера застосування продукції; P - передумова виконання продукції; K - ядро продукції (А=>B); N - постумова продукції, або в іншій інтерпретації дії, які повинні бути виконані після виконання продукції.
Основні типи (можливі інтерпретації) продукцій:
- імплікації (якщо А істинне, то і В істинне);
- умовні операції (якщо А істинне, то виконати операцію В);
- правила підстановок (А можна замінити на В).
Продукційну систему прийнято визначати як сукупність продукцій разом з механізмом керування ними. Винятково популярна модель подання знань; багато експертних і інтелектуальних інформаційних систем побудовані саме на цій моделі. На відміну від фреймово-семантичних моделей, продукційні системи більше тяжіють до програмування (хоча й декларативного) та до планування і прийняття рішень. Очевидний зв’язок продукцій з алгоритмами (програмами), які працюють паралельно та асинхронно. Заздалегідь невідомо, коли саме і в якій послідовності вони будуть викликатися; саме це вирішує механізм керування.
Механізм управління продукціями: основні компоненти:
- цикл “співставлення-дія” (або розпізнавання-дія) - в основі роботи;
- механізм розв’язання конфліктів;
- передача інформації між продукціями;
- засоби, спрямовані на підвищення ефективності роботи продукційної системи (один з найбільш відомих - алгоритм RETE).
Робота циклу “співставлення-дія”:
- До робочої пам’яті заносяться умови задачі: ціль та факти, які описують ситуацію; туди ж заносяться проміжні результати обчислень.
- Механізм виконання співставляє факти, які знаходяться в робочій пам’яті, з продукціями, які знаходяться в БЗ.
- Якщо співставлення успішне - продукція включається до конфліктного набору (інша назва - фронт готових продукцій). В результаті після завершення циклу співставлення формується конфліктний набір - множина продукцій, які можуть бути виконані в даній ситуації.
- З цієї множини вибирається одна продукція, яка й буде виконана (відповідно до тієї чи іншої стратегії розв’язання конфліктів). В результаті ситуація, тобто стан робочої пам’яті, змінюється, і цикл повторюється.
Методи роботи з недостовірними знаннями.
Недостовірне твердження (інша назва - неточне твердження) - твердження, істинність або хибність якого не встановлена точно, тобто твердження, яке не є ні достовірно істинним, ні достовірно хибним.
Неточне (недостовірне) логічне виведення - виведення в умовах недостовірних знань.
Типові задачі
- Дано А (можливо, недостовірно); дано правило A=>B (можливо, недостовірне). Чи має місце В?
- З’ясування причин тієї чи іншої події.
Постулати “чіткого універсуму”
Діє закон виключеного третього: будь-яке твердження є або істинним, або хибним. Будь-яке інше істинносне значення пов’язано з суб’єктивним незнанням. Постулюється існування гіпотетичного “ідеального” агента, який знає оцінку істинності (0 або 1) для будь-якого твердження.
Типи невизначеності
- об’єктивна (в основному пов’язується з імовірностями);
- суб’єктивна;
- комбінована.
Коефіцієнти упевненості
Коефіцієнти упевненості характеризують міру невизначеності твердження. Від 0 до 1 або від -1 до 1. Можуть носити імовірносний характер, але не обов’язково. Найбільшого поширення набули методи логічного виведення приєднаного типу. Постановка задачі: дано ρ(А) та ρ(A=>B); визначити ρ(В) .
Стендфордська теорія фактору впевненості (схема EMYCIN):
- Міра впевненості в твердженні Н при заданому свідоцтві Е: МВ(Н|Е); 0<МВ(Н|Е)<1.
- Міра недостовірності твердження Н при заданому свідоцтві Е: МD(Н|Е); 0<МD(Н|Е)<1.
Комбінована міра впевненості, фактор упевненості, коефіцієнт упевненості: CF(H|E) = MB(H|E)-MD(H|E).
Коефіцієнти упевненості CF: від -1 до 1.
Якщо дані CF(A) (коефіцієнт упевненості передумови) та CF(A=>B) (коефіцієнт упевненості правила), то коефіцієнт упевненості висновку CF(B)=CF(A)*CF(A=>B).
CF(не А) = - CF(A).
CF (A or B) = max(CF(A),CF(B)).
CF (A and B) = min(CF(A),CF(B)).
Комбінування свідоцтв:
r = r1+r2-r1*r2, якщо r1 та r2 >0;
r = r1+r2+r1*r2, якщо r1 та r2 <0;
r=(r1+r2)/(1-min(|r1|,|r2|)), якщо r1 та r2 різних знаків. Якщо r1 = -1, r2 = 1, то r = 0.
Розпізнавання образів. Метод найближчого сусіда та алгоритм персептрона побудови лінійної розділяючої функції.
Метод найближчного сусіда - детерміністський. Суть: об"єкт відноситься до того ж класу, до якого належить його найближчий сусід у навчальній вибірці. Гіпотеза компактності - класу відповідає компактна множина у деякому просторі ознак.
Алгоритм персептрона Класи К1, К2б розділяюча функція g(x) визначена наступним чином для будь-якого х, що належить К1: g(x)>0; для будь-якого y, що належить К2: g(y)<0.
Початковий вектор параметрів w(0) уточнюється по мірі розпізнання елементів з навчальної вибірки.
- якщо черговий х(і) належить К1, а g(x)<=0
w(i+1):=w(i)+c*x(i), c>0
- якщо черговий х(і) належить К2, а g(x)>=0
w(i+1):=w(i)-c*x(i), c>0
Конекціоністський підхід до побудови систем штучного інтелекту. Штучні нейрони та персептрон Розенблатта
Нейронні мережі, або штучні нейронні мережі, діють за принципами, подібними до принципів функціонування людського мозку. Невербальність і недедуктивність; символьні знання не використовуються. Конекціоністський підхід. Штучний нейрон - деяка модель, яка імітує найважливіші риси природного нейрону, або реалізація такої моделі (апаратна або програмна). Нейронна мережа - сукупність взаємопов'язаних штучних нейронів.
Основна ідея - навчання. Основний принцип навчання нейронної мережі полягає в налаштуванні зв'язків між нейронами: зміні коефіцієнтів зв'язків, перебудові структури тощо.
Основна характеристика нейромережевого алгоритму: 1. задання структури (топології) нейронної мережі; 2. задання правила навчання.
Нейронні мережі застосовуються при розпізнаванні образів, прогнозуванні, фільтрації, організації пам"яті тошо. Модель штучного нейрона:
Є x1.. xn вхідних сигналів з ваговими коефіцієнтами w1.. wi. Ці сигнали поступають на суматор, який після виконання певних дій передає результат до активаційної функції. Отриманий результат y передається на вихід. y = F(Сума(i=1..n)(wi*xi+w0*x0)). Тут x0 з ваговим коефіцієнтом w0 - додатковий вхід, який використовується для ініціалізації нейрона (в Олецького юзається sigma. sigma=-w0*x0). Під ініціалізацією розуміють зміщення активаційної функції по горизонтальній осі, тобто формування порогу чутливості нейрона. Основний принцип навчання - корекція вагових коефіцієнтів.
АКТИВАЦІЙНА ФУНКЦІЯ.
1. Порогова. F(s)=1, якщо s>=0; F(s)=0, якщо s<0;
2. Лінійна. F(s)=k*s;
3. Сигмоїдна. F_a(s)=1/(1+e^(-a*s)), a>0.
Ключовий результат Мак-Каллока і Піттса: певним чином організована сукупність нейронів може обчислювати будь-яку обчислювану функцію.
ПЕРСЕПТРОН РОЗЕНБЛАТТА - одна з перших мереж, здатна до сприйняття і формування рекації на сприйнятий стимул. Містить нейрополібні елементи трьох типів:
1. S-елементи - формують сітківку сенсорних клітин, що сприймають двійкові сигнали від зовнішнього світу.
2. А-елементи - виконують нелінійну обробку інформації і змінюють вагові коефіцієнти зв"язків.
3. R-елементи - з фіксованими ваговими коефіцієнтами. Формують сигнал реакції персептрона на вхідний стимул.
Основна ідея навчання: корекція коефіцієнтів у випадку, якщо після пред'явлення чергового навчального вектора фактичний вихід не збігається з бажаним. Така корекція може здійснюватися після кожного пред'явлення чергового вектора. Коефіцієнти корегуються таким чином, аби мінімізувати середньоквадратичну похибку E=(Сума(k=1..L)(y^(k)-d^(k)))^2, де L - кількість вхідних образів, y - фактичний вихід, d - бажаний вихід (формула - для одного нейрона).
Правило навчання: грунтується на методі градієнтного спуску: задаємо початкові значення коефіцієнтів та рухаємося в напрямку антиградієнта.
w_j = w_j - alpha * dE/dw_j;
sigma = sigma - alpha * dsigma/dw_j;
0<alpha<1/2;
Обмеженість простих персептронів: по суті - алгоритми навчання таких систем еквівалентні знаходженню лінійної розділяючої функції. Якщо нема лінійної розділимості - алгоритм не знайде параметр розділяючої ф-ції.
Операції з нечіткими знаннями.
В ряді тверджень можуть фігурувати поняття, що є нечіткими за своєю природою; напр., “великий”, “маленький” і т.п. Відповідно - нечітко сформульовані твердження; опис за допомогою формалізму нечітких множин (fuzzy sets), які пов’язуються з іменем Заде. Опис множин: від характеристичної функції до функції належності.
Визначення: Нехай Е - деяка базова множина. Нечіткою підмножиною А множини Е називається множина пар { (x,muA(x) }, де x належить E, muA(x) :E->[0,1]. Примітка - тут і далі mu позначатиме однойменну літеру грецього алфавіту. muA(x) - функція належності множини А, а її конкретне значення для елемента х - ступінь належності (в якій мірі елемент x належить нечіткій множині А, або ж в якій мірі він відповідає поняттю, що описується цією множиною). Ступені належності: від 0 до 1. Отже, нечітка підмножина характеризується функцією належності елементів цій множині.
Ступені належності. Важливі риси:
- вони суб’єктивні;
- певні природні обмеження;
- самі ступені належності можна розглядати як нечіткі.
Основні операції:
- рівність: А=В, якщо muA(x) = muB(x);
- підмножина: А підмножина В, якщо muA(x) <= muB(x);
- перетин: muA перетинається із B(x) визначається як: min(muA(x), muB(x));
- об’єднання: muA об"єднати із B(x) визначається як: max(muA(x), muB(x));
- доповнення: muᾹ(x) визначається як: 1-muA(x).
Зауваження: перетин "А" та "не А" не зажди порожня множина, так само як і об"єднання А та її доповнення не завжди універсальна множина - різниця між звичайними та нечіткими множинами.
