НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

“КИЄВО-МОГИЛЯНСЬКА АКАДЕМІЯ”

Департамент комп’ютерних технологій

Кафедра інформатики

Реферат з курсу:

“ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ІНТЕЛЕКТУАЛЬНИХ СИСТЕМ”

за осінній триместр 1999/2000 навчального року

ДСМ-МЕТОД

студентки ДКТ-5

Федосової Н. Є

Київ – 1999

Зміст.

Вступ.

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

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

Введемо три множини: причин А = {a₁, …, a_p}, наслідків B = {b₁, …, b_p} та оцінок Q = {q₁, …, q_p}. Вираз вигляду a_і => b_j; q_k будемо називати позитивною гіпотезою (h+_{i j k}). Вираз пов’язано з твердженням типу “a_i є причиною b_j з оцінкою достовірності q_k”. Вираз вигляду a_i ?> b_j; q_k будемо називати негативною гіпотезою (h^–_{i j k}). Його пов’язано з твердженням типу “a_i не є причиною b_j з оцінкою достовірності q_k”. Серед значень q_i виділимо два спеціальних, які можна позначити 0 та 1. Значення 0, приписане позитивній або негативній гіпотезі, означає, що відповідне твердження є хибним. Приписування гіпотезам значення 1 означає, що дана гіпотеза є тотожно істинною. Всі інші оцінки, відмінні від 0 та 1, будемо позначати раціональними числами вигляду s/n, де s пробігає значення від 1 до n – 1. Величина n характеризує “дробність” оцінок достовірності, що використовуються. Чим більше n, тим з більшою точністю оцінюється достовірність гіпотез.

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

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

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

Повернемося до ДСМ-методу. Розглянемо групу позитивних прикладів. Знаходимо деяку частину опису об’єктів, загальну для певної сукупності прикладів з цієї групи. З’являється кандидат в причини. Таких кандидатів може бути декілька. Утворимо матрицю М⁺, в якій рядки відповідають виділеним кандидатам а_і, а стовпчики – наслідки b_j, що нас цікавлять (при одному наслідку, що нас цікавить в М⁺ буде один стовпчик). На перетині рядків і стовпчиків будемо записувати оцінки достовірності q_k гіпотез h⁺_{i j k}. Для множини негативних прикладів будується інша матриця М^–, в якій містяться оцінки достовірності негативних гіпотез h^–_{i j k}. Кандидати в причини в матрицях М ⁺ та М^– можуть частково співпадати.

На кожному кроці роботи ДСМ-методу використовуються нові спостереження, що поповнюють множини позитивних та негативних прикладів. Ці нові спостереження можуть або підтверджувати сформовані гіпотези h⁺_{i j k} та h^–_{i j k}, або суперечити їм. В першому випадку треба збільшувати оцінки достовірності відповідних гіпотез, а в другому – зменшувати їх. Механізм зміни оцінок q_k в ДСМ-методі влаштовано наступним чином. Значення n співпадає з кількістю позитивних чи негативних прикладів, що є у нас в даний момент. Таким чином, для М⁺ та М^– значення n може бути різним. Зі збільшенням n росте “дробність” оцінок достовірності. Оцінка 1/n відіграє особливу роль. Вона відповідає повній невизначеності про достовірність гіпотези. Тому в початковий момент М⁺ та М^– заповнені лише нулями, одиницями та оцінками 1/n. Значення істини та хиби можуть мати гіпотези, у яких в якості причин дано повні описи об’єктів, що утворюють множини прикладів.

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

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

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

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

У спрощеному вигляді схема правдоподібного виведення в ДСМ-АПГ схожа на схему виведення в системі індуктивного навчання. Гіпотезу про закономірності отримують в результаті таких узагальнень позитивних прикладів, які заздалегідь не були б узагальненням негативних прикладів. Специфічним для ДСМ-АПГ рисами є спосіб вираження операції узагальнення, використання оригінальних “підсилень” гіпотез, що відповідають перевіркам на гіпотезах виконання деяких умов здорового глузду, використання так званого узагальненого методу, можливість отримання складних залежностей на даних за допомогою комбінації індуктивного та дедуктивного виведення. ДСМ-метод поділяється на три основні рівні, які умовно можна назвати рівнями схожості, правил та розмірковувань.

На першому рівні, або рівні схожості, задається структура даних про об’єкти з предметної області, а також операція схожості, що співставляє двом об’єктам із предметної області третій об’єкт, що виражає схожість перших двох.

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

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

Схожість.

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

Поняття схожості, що використовується в ДСМ-методі, представляє собою один з можливих способів синтезу кількох напрямків: об’єкти структуровані (тобто на них задано відношення “бути більш загальним”), а їх схожість задається через операцію з визначеними алгебраїчними властивостями, що індуцирують відношення толерантності (тобто рефлексивне та симетричне відношення) на об’єктах. Та навпаки, відношення толерантності (схожості) вільного (але фіксованого) числа об’єктів може бути взаємно-однозначно співставлено деякій операції, яка може бути операцією схожості на об’єктах в ДСМ-методі. Більш формально, нехай S – множина об’єктів, яка представляє деяку предметну область. Операція ? на парах об’єктів із S задає нижню напіврешітку, якщо для будь-яких об’єктів s_i, s_j, s_k з S мають місце співвідношення (1)–(4)

(1) s_i?s_i = s_i,

(2) s_i?s_j = s_j?s_i,

(3) (s_i?s_j) ?s_k = s_i?(s_j?s_k),

(4) s_i?s₀ = s₀, для деякого s₀ з S, який називається порожнім об’єктом.

Поняття “порожнього об’єкта” може бути розширене до “множини порожніх об’єктів”. Такою може бути множина об’єктів із S, що включає s₀ та замкнуте відносно операції ?. Множина порожніх об’єктів може інтерпретуватися як “несуттєва”, “неінформативна” схожість. Такою, наприклад, можна рахувати схожість графів хімічних молекул, максимальний загальний підграф яких є одна ланка вуглеводневого ланцюжка: —С—C—.

Напіврешіточна операція ? задає на множині S відношення поглинання L наступним чином: для s_i та s_j з S, s_i + s_j тоді і тільки тоді, коли s_і ? s_j = s_i.

Означення 1.

Операцію, що задовольняє властивостям (1)–(4), назвемо операцією схожості.

Означення 2.

Нехай <S, ?, s₀> – нижня напіврешітка, X ? s₀ називається локальною схожістю об’єктів s₁, …, s_k (k = 2), якщо X = s₁?…?s_k.

Можна записати s₁?…?s_k замість s₁?(¬s₂?(…?s_k)…), використовуючи властивості (1)–(3) операції схожості ?. Загалом, при визначенні операції схожості можна обійтися без властивості асоціативності (3), що дозволяє однозначно задавати схожість n об’єктів через попарні схожості. В такому випадку, однак, довелося б вводити нескінчене сімейство операцій схожості ?₂, ?₃, …, кожне з яких відноситься до певної кількості об’єктів. При цьому результат операції міг би залежати від порядку операндів.

Означення 3.

Нехай <S, ?, s₀> – нижня напіврешітка. Пара <X, {s₁,…, s_k}>, де s₁,…, s_kS, називається глобальною схожістю, якщо Х = s₁?…?s_k, тобто Х є локальна властивість об’єктів s₁,…, s_k та для будь-якого sS\{s₁,…, s_k} має місце X ? s ? X. Так як k заздалегідь невідоме, то глобальна схожість не є відношенням, на відміну від локальної схожості. Помітимо, що відношення

def

R (x, y)  (S \ {s₀})  (S \ {s₀}), (x, y)  R = x ? y ? s₀

Є відношенням толерантності, тобто воно рефлексивне ((х, х)  R) та симетричне ((x, y)  R ? (y, x)  R). Тим самим операція ? задає бінарне відношення схожості, але не лише його. В силу асоціативності операції ? можна ввести наступне k-арне відношення R_k для довільного k. R_k  (S \ {s₀})  … (S \ {s₀}); (x_1,… x_k)  R_k, якщо x₁? … ?x_k ? s₀. Тоді відношення буде мати наступні властивості:

xS \ {s₀}, (x,…x)R_k (Re)

k

pqi   1 = i = p = i + q = k

(x₁, …, x_i, …, x_p, …, x_i+q, …, x_k)R_k ? (x₁, …, x_i-1, x_i, …, x_p, x_i+q+1, …, x_k)R_k (PR) (x_1,… x_k)  R_k ? (x_j1,… x_jk)  R_k, (Si)

де (j₁, …, j_k) – будь-яка перестановка (1, …, k).

Відношення, що мають властивості (Re), (PR), (Si) називаються k-арними відношеннями толерантності. Ці відношення природнім чином узагальнюють відношення бінарної толерантності.

Правила.

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

Припустимо, що предметна область задана деякої нижньою напіврешіткою SL = <S, ?, 0>, а база даних системи включає в себе деяку множину об’єктів ?  S. Нехай нас цікавлять властивості цих об’єктів з деякої множини U² ={w₁, …, w_k} та про кожний об’єкт s_iΩ ςа кожну властивість w_iU² або відомо, що s_i має властивість w_j ( і тоді він називається позитивним або (+)­­­­-прикладом відносно w_j), або відомо, що s_i не має властивість w_j (s_i є (–)-прикладом відносно w_j), або не відомо ні те ні інше (тоді він називається невизначеним або (τ)-прикладом відносно w_j). Таким чином, для фіксованої властивості w_j всі об’єкти з Ω поділяються на три класи Ω⁺, Ω^–, Ω^τ позитивних, негативних та невизначених прикладів відповідно.

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

Означення 4.

Нехай Ω⁺, Ω^– – множина вихідних (+)- та (–)-прикладів. Позитивною (або (+)-) гіпотезою І роду, отриманою за правилом І_а⁺, називається глобальна схожість вигляду <h, {s_i1, …, s_it}> на напіврешітці <Ω⁺, ?, s₀>, де s_i1, …, s_it – об’єкти з ?⁺ (позитивні приклади), для котрого h не є локальною схожістю яких-небудь об’єктів з ?^–. Будемо називати h головою, а {s_i1, …, s_it} – хвостом гіпотези.

Негативна (або (–)-) гіпотеза І роду, отримана за правилом І_а^–, визначається двояко.

Якщо схожість деяких позитивних прикладів s_i1, …, s_it співпадає зі схожістю деяких негативних прикладів s_i1, …, s_it, тобто

s_i1 ?…? s_it = s_j1 ?…? s_jr = h,

то обидві пари

<h, {s_i1, …, s_it}>, <h, {s_j1, …, s_jr}>

називаються суперечливими (або (0)-) гіпотезами, отриманими за правилом І_а⁰. Таке означення гіпотез близьке до типових означень гіпотез в системах машинного навчання, де будується таке узагальнення позитивних прикладів, яке не було б узагальненням негативних.

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

Означення 5.

Позитивна або (+)-гіпотеза ІІ роду, отримана за правилом П⁺, є той об’єкт НΩ^τ, для якого існує (+)-гіпотеза І роду <h⁺, {s_i1, …, s_it}> така, що h⁺H та для довільної (–)-гіпотези І роду <h^–, {s_i1, …, s_it}> має місце h^–H.

Негативні (або (–)-) гіпотези визначаються двояко. НΩ^τ називається суперечливою (або (0)-) гіпотезою, отриманою за правилом П⁰, якщо Н включає голови як позитивних, так і негативних гіпотез І роду.

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

Вивід правдоподібних гіпотез в ДСМ-методі здійснюється в рамках квазіаксіоматичних теорій (КАТ). КАТ є трійка

<, , >,

де  – множина аксіом, що неповно описує предметну область (ПО),  – множина емпіричних елементарних речень про об’єкти з ПО. Зазвичай вони відповідають твердженням вигляду “Об’єкт має властивість А”. Множина  відкрита та може поповнюватися за рахунок проведення нових експериментів, спостережень та ін.,  – множина правил виведення.  = ¹⁰, де ¹ – множина правил правдоподібного виведення (ППВ) та ⁰ – множина правил достовірного виведення.

Розмірковування в КАТ є побудова ланцюжка формул ₁, …, _n, де кожна _і або аксіома з , або фактичне висловлювання з  (відповідає (+)- чи (–)-прикладу – тобто об’єкту з ?⁺ чи ?^–), або отримана з попередніх формул ланцюжка ₁, …, _n шляхом застосування правил з  як, наприклад, гіпотези І та ІІ роду. Визначення розмірковування в КАТ відрізняється від визначення логічного виведення тим, що:

1.  – відкрита множина, елементи якої _і, релевантні цілі _n, вставляються в ланцюжок, якщо має місце відношення схожості цілі – _і R _n.

2. Серед правил , що застосовуються при побудові вказаного ланцюжка формул, є правили з  , де  – множина правил правдоподібного виведення.

3. В процесі побудови ланцюжка ₁, …, _n можуть використовуватися металогічні засоби, наприклад, перевірка на несуперечливість, на невиводимість, на виконуваність або невиконуваність деяких умов та ін.

Множина аксіом  складається з множини процедурних аксіом _pr та множини декларативних аксіом _dc. Аксіоми з _pr формально виражають собою застосування правил І та ІІ роду з врахуванням їх часткового впорядкування. Частина декларативних аксіом з _dc (позначимо її _dc⁰) описує структуру даних (алгебру схожості, сполучення та різниці) предметної області, що розглядається. Інша частина декларативних аксіом, _dc¹, описує деякі природні властивості причинних відношень та гіпотез про них: правила комбінації наслідків одних і тих самих причин, а також принципи казуальної несуперечливості та повноти.

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

Декларативні аксіоми ДСМ-методу можуть бути засобом керування розмірковуванням: при невиконанні якої-небудь аксіоми ДСМ-“розмірковувач” може вимагати поповнення бази даних новими прикладами та вказувати вид прикладів, що дозволяють добитися виконання аксіоми після застосування ДДСМ-ППВ. Перевірка виконуваності аксіом може здійснюватися часто дедуктивним шляхом з використанням засобів логічного виведення, основаних на логічній теорії ДСМ-методу. Система логічного виведення інтегрована з засобами правдоподібного виведення ДСМ-методу в єдину логіко-інформаційну обчислювальну систему та дозволяє отримувати дедуктивний доказ або спростування виконання тих чи інших залежностей на об’єктах та гіпотезах із ДСМ-бази даних. Об’єднання в ДСМ-розв’язувачі індуктивного та дедуктивного виведення дає можливість бачити схожість ДСМ-розмірковувань з навчанням в системах, основаних на поясненні: складні залежності на об’єктах з бази даних є тут аналогами тверджень, що не задовольняють критерію операціональності. “Навчання” їм можливо лише після навчання елементарним гіпотезам (тобто отримання їх за допомогою правил І та ІІ роду) та проведення на їх основі логічного виведення.

Висновок.

В даній роботі було розглянуто ДСМ-метод, я саме загальний опис цього методу, а також основи ДСМ-методу автоматичного породження гіпотез, що об’єднує в собі риси індуктивних методів (навчання на позитивних та негативних прикладах) та методів, основаних на поясненні (використання дедуктивного виведення).

Література.

• Д. А. Поспелов. Моделирование рассуждений. Опыт анализа мыслительных актов. Москва, “Радио и связь”, 1989

• О. М. Анашков, Д. П. Скворцов, В.К. Финн, В. Г. Ивашко. Логические средства ДСМ-метода автоматического порождения гипотез: основные понятия и система правил вывода. НТИ, 1987.