REFERATUA.ORG.UA — База українських рефератів



Головна Інформатика, комп'ютери, програмування → ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ІНТЕЛЕКТУАЛЬНИХ СИСТЕМ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "КИЄВО-МОГИЛЯНСЬКА АКАДЕМІЯ" Департамент комп'ютерних технологій Кафедра інформатики Реферат з курсу: "ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ІНТЕЛЕКТУАЛЬНИХ СИСТЕМ" за осінній триместр 1999/2000 навчального рокуДСМ-МЕТОД студентки ДКТ-5 Федосової Н. Є

Київ – 1999

Зміст.

Зміст. 2

Вступ. 3

Загальний опис ДСМ-методу. 4

ДCМ-метод автоматичного породження гіпотез (ДСМ-АПГ). 7

Схожість. 8

Загальні визначення. 8

Правила. 10

Простий метод. 10

Правила І роду 10

Правила ІІ роду. 11

Розмірковування. 11

Висновок. 14

Література. 15

Вступ.

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

Загальний опис ДСМ-методу.

Введемо три множини: причинА = {a1, ..., ap}, наслідків B = {b1, ..., bp} та оцінокQ = {q1, ..., qp}. Вираз вигляду aі => bj; qk будемо називати позитивною гіпотезою (h+i j k). Вираз пов'язано з твердженням типу "ai є причиною bj з оцінкою достовірності qk". Вираз вигляду ai ?> bj; qk будемо називати негативною гіпотезою (hi j k). Його пов'язано з твердженням типу "ai не є причиною bj з оцінкою достовірності qk". Серед значень qi виділимо два спеціальних, які можна позначити 0 та 1. Значення 0, приписане позитивній або негативній гіпотезі, означає, що відповідне твердження є хибним. Приписування гіпотезам значення 1 означає, що дана гіпотеза є тотожно істинною. Всі інші оцінки, відмінні від 0 та 1, будемо позначати раціональними числами вигляду s/n, де s пробігає значення від 1 до n – 1. Величина n характеризує "дробність" оцінок достовірності, що використовуються. Чим більше n, тим з більшою точністю оцінюється достовірність гіпотез.

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

Додаткові причини мають ту властивість, що їх наявність не викликає наслідок bj. Для того, щоб з'явилося bj, необхідна наявність певного набору додаткових причин, яких виступає в ролі узагальненої достатньої причини появи bj. Серед додаткових причин можуть бути необхідні додаткові причини. Їх входження до набору, що утворює узагальнену достатню причину, обов'язкове для того, щоб bj реалізувалося. Інші додаткові причини можна назвати факультативними. До кінцевого набору можуть входити ти чи інші комбінації факультативних причин. Нарешті, можливі причиниаі мають ту властивість, що поява аі необов'язково викликає bj, але збільшує можливість появи bj.

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

Повернемося до ДСМ-методу. Розглянемо групу позитивних прикладів. Знаходимо деяку частину опису об'єктів, загальну для певної сукупності прикладів з цієї групи. З'являється кандидат в причини. Таких кандидатів може бути декілька. Утворимо матрицю М+, в якій рядки відповідають виділеним кандидатам аі, а стовпчики – наслідки bj, що нас цікавлять (при одному наслідку, що нас цікавить в М+ буде один стовпчик). На перетині рядків і стовпчиків будемо записувати оцінки достовірності qk гіпотез h+i j k. Для множини негативних прикладів будується інша матриця М–, в якій містяться оцінки достовірності негативних гіпотез hi j k. Кандидати в причини в матрицях М + та М– можуть частково співпадати.

На кожному кроці роботи ДСМ-методу використовуються нові спостереження, що поповнюють множини позитивних та негативних прикладів. Ці нові спостереження можуть або підтверджувати сформовані гіпотези h+i j k та hi j k, або суперечити їм. В першому випадку треба збільшувати оцінки достовірності відповідних гіпотез, а в другому – зменшувати їх. Механізм зміни оцінок qk в ДСМ-методі влаштовано наступним чином. Значення n співпадає з кількістю позитивних чи негативних прикладів, що є у нас в даний момент. Таким чином, для М+ та М– значення n може бути різним. Зі збільшенням n росте "дробність" оцінок достовірності. Оцінка 1/n відіграє особливу роль. Вона відповідає повній невизначеності про достовірність гіпотези. Тому в початковий момент М+ та М– заповнені лише нулями, одиницями та оцінками 1/n. Значення істини та хиби можуть мати гіпотези, у яких в якості причин дано повні описи об'єктів, що утворюють множини прикладів.

Якщо деяка позитивна чи негативна гіпотеза hi j k мала оцінку k/n, то при появі нового прикладу (n замінюється на n + 1) перевіряється підтверджує чи не підтверджує новий приклад цю гіпотезу. При підтвердженні оцінка k замінюється на (k + 1)/(n + 1), а при непідтвердженні новим прикладом раніше висуненої гіпотези її оцінка змінюється з k/n на (k – 1)/(n + ). Таким чином, в процесі накопичування нової інформації оцінки гіпотез або наближаються до 0 чи 1, або якось "коливаються ". В першому випадку гіпотеза на деякому кроці може зникнути з М+ або М–. В другому при досягненні верхньої межі достовірності гіпотеза може отримати оцінку, що відображає емпіричну істину, та запам'ятатися як деякий встановлений факт в системі або ця гіпотеза повідомляється людині, що працює з ДСМ-програмами. В третьому випадку, якщо коливання оцінок достатньо сильні, може також відбутися виключення сформованої раніше гіпотези з тих, які описані в М+ та М–.

Нові гіпотези формуються не лише на основі виділення в прикладах певної схожості. Вони можуть використовувати і метод відмінностей, також сформульований Міллєм. Відмінність виявляється для прикладів, що відносяться до груп позитивних та негативних прикладів. Знайдена відмінність служить кандидатом для гіпотез, що включаються в М+ або М–.

В ДСМ-методі крім прямої реалізації ідей Мілля використовуються ще деякі виведення за аналогією. Для цього на множині описів об'єктів вводиться тим чи іншим чином поняття схожості. Якщо встановлене відношення схожості, то в ДСМ-методі відбувається виведення за аналогією. Він здійснюється наступним чином. Якщо гіпотеза hi jk має оцінку k/n та така, що причини, що використовується в ній, схожа з причиною в гіпотезі hi j 1, що знаходиться в тій самій матриці М та оцінюється з точки зору достовірності значенням 1/n, то на гіпотезу hi j 1 переноситься оцінка гіпотези hi j k та вона отримує оцінку достовірності k/n. Подібна процедура в ДСМ-методі називається правилом позитивної аналогії. Існує в цьому методі і правило негативної аналогії, а також градація тих та інших правил по силі схожості, що в них враховується. Таким чином, ДСМ-метод демонструє


 
Загрузка...