Швидке розроблення інтелектуальних додатків в адаптивній технології SmartBase

Виходячи з формули (6), значення A2(x) можна обчислити підбором, який може дати більш ніж один результат. Отже, традиційним підходом задача обчислення A2(x) вирішується не однозначно і не у всіх випадках. Наведені недоліки виключаються, якщо обчислення виконувати за такою схемою:

Крок 1. Розглядати лише правила вигляду (1), в яких консеквент містить не більше одного можливого наслідку.

Крок 2. Якщо |→ k А – твердження про те, що А має місце зі ступенем впевненості k, то ступені впевненості  обчислювати за допомогою формул:

якщо |→ k P і |→ l Q, то |→ k⊗l P∧Q;

якщо |→ k P і |→ l Q, то |→ k⊕l P∨Q;

якщо |→ k P і |→ l P→Q, то |→ k⊗l Q.

Крок 3. Перебір всіх можливих ланцюжків  замінити застосуванням матричного методу виведення. На кроці 2 у випадку  із двох способів визначення операцій ⊕ і ⊗ приймемо визначення (3). При виборі визначень (2) необхідно впевнитися, що результати не принесуть чисел, які виходять за межі діапазону [0,1]. Для a *T b == min{a, b} найбільше можливе значення a і b дорівнює 1, і менше з них принесе 1. Це значення не виходить за межі прийнятого діапазону. Для a +T b = max{a, b} найбільше можливе значення a і b дорівнює 1, і менше з них принесе 1. Це значення не виходить за межі прийнятого діапазону.

 

Матрична резолюція  для нечіткої логіки

Невід’ємною частиною розробки алгоритму  є застосування методу виведення, що дозволяє свідчити про суперечливість побудованих правил. Зокрема для клаузальної логіки найбільш простим і ефективним у даному випадку виступає матричний метод. Його основна ідея полягає у використанні матричного представлення вихідних даних і реалізації резолютивного методу у вигляді операції множення матриць. Такі матриці, очевидно, повинні мати стовпець і рядок для кожного літерала, а елемент на перетині рядка i та стовпця j буде мати ненульове значення лише тоді, коли знайдеться клауза, у безумовній частині якої знаходиться літерал рядка i, а умовна частина містить літерал стовпця j. Доведено, що множина клауз S суперечлива тоді і тільки p тоді, коли застосування процедури множення таких матриць приводить до побудови матриці M з ненульовою головною діагоналлю.

Наприклад, нехай маємо множину  клауз: A ← B; B ← C; C ← і необхідно обґрунтувати, що А є їх логічним наслідком. Добавляємо клаузу ← А. Нагадаємо, що запис клауз традиційно міняє місцями умовну і безумовну частини. Зрозуміло, що порожню клаузу можна отримати за допомогою трьох застосувань правила резолюції. Множення матриць підтверджує цей висновок. Отже, маємо:

 

 

 

Методи та засоби програмної інженерії

З огляду на суперечливість множини  клауз можлива ознака суперечливості у матричному варіанті –

наявність ненульової головної діагоналі  у матриці Mp, де p = 4, – підтверджується. При побудові матриці

застосовується два правила:

Правило А. Якщо в матриці є нульовий рядок, то вилучаємо його з матриці  разом з відповідним

стовпцем.

Правило В. Якщо в матриці є порожні  стовпці, то вилучаємо відповідні клаузи і після цього застосовуємо

правило А.

Застосуємо вищезазначений метод  виведення для встановлення того, що ступінь впевненості потрібного

висновку є ненульовим. Розглянемо приклад оцінок експертів, повертаючись до традиційного запису:

|→ 0.7 А1

|→ 0.4 (А1 → А3)

|→ 0.5 ((А3 ∧ А4) → А5)

|→ 0.7 А2

|→ 0.5 (А2 → А4)

|→ 0. 3 ((А3 ∧ А4) → А6)

Спочатку застосуванням визначення операцій (3) і правил виведення кроку 2 вище наведеної схеми:

1) обчислимо |→ 0.7 ⊗ 0.4 А3:

0.7 ⊗ 0.4 = min{0.7, 0.4} = 0.4,

тобто |→ 0.4 А3;

2) обчислимо |→ 0.7 ⊗ 0.5 А4:

0.7 ⊗ 0,5 = min{0.7, 0.5} = 0.5,

тобто |→ 0,5 А4;

3) обчислимо |→ 0.4 ⊗ 0.5 (А3 ∧ А4):

0.4 ⊗ 0,5 = min{0.4, 0.5} = 0.4,

тобто |→0. 4 А3 ∧ А4;

4) обчислимо |→ 0. 4 ⊗ 0.5 А5:

0. 4 ⊗ 0,5 = min{0.4, 0.5} = 0.4,

тобто |→0. 4 А5;

5) обчислимо |→ 0. 4 ⊗ 0.3 А6:

0. 4 ⊗ 0.3 = min{0.4, 0.3} = 0.3,

тобто |→0.3 А6;

Отже,

|→ 0.4 А5, |→ 0.3 А6.

Тепер застосуємо матричний метод. Спочатку побудуємо матрицю для  перевірки висновку А5. Наявність  оцінок впевненості правил і тверджень  вимагає вдосконалити процедуру побудови матриць. Вони, як і для двозначної логіки, повинні мати стовпець і рядок для кожного літерала, а елемент на перетині рядка i та стовпця j буде мати ненульове значення лише тоді, коли знайдеться клауза, у безумовній частині якої знаходиться літерал рядка i, а умовна частина містить літерал стовпця j. Але це значення буде нечіткою оцінкою. Добавляємо клаузу ← А5. З огляду на можливість існування декількох клауз із однаковою безумовною частиною і клауз із умовною частиною з декількома літералами (наприклад, порівняйте |→ 0.4 А1, |→ 0.6 (А2 → А3), |→ 0.2 (А1 → А3), |→ 0.7 А2 і |→ 0.4 А1, |→ 0.7 А2, |→ 0.8 (А1,А2 → А3)), наявність першого випадку будемо позначати індексом „∨” біля кожного літерала умовної частини однієї клаузи, а наявність останнього випадку – індексом „∧” біля кожного літерала умовної частини однієї клаузи. Матриця має вигляд

 

Застосовуючи правила A та B приведемо  матрицю до вигляду матриці M1. Модифікуємо  також алгоритм множення матриць. У випадку наявності правил |→ k А1, |→ l (А1 → А2), множення k⊗l необхідно виконувати за формулою min{k, l}. У випадку наявності правил |→ k А1, |→ l А2, |→ q (А1, А2 → А3), у матриці у рядку з’являються індекси „∧” у стовпцях для літералів А1, А2 і множення (k⊗l) ⊗q необхідно виконувати за формулою min{min{k, q}, min{l, q}}. У випадку наявності правил |→ k А1, |→ l А2, |→ q (А1 → А3), |→ r (А2 → А3), у матриці у рядку з’являються два ненульових елементи з індексами „∨”, у стовпцях для літералів А1, А2 і при множенні необхідно вибрати максимальний із двох добутків у рядку max {min{k, q}, min{l, r}}.

 

 

 

Перемноження матриці M 1 призводить до підтвердження суперечливості вихідної множини клауз при p = 4 за ознакою суперечливості для традиційної клаузальної логіки [3], що доводить вищенаведене припущення

про логічний наслідок А5. Залишається  визначитися з нечіткою оцінкою  результату. Оскільки застосуванням

визначення операцій (3) і правил виведення кроку 2 вищенаведеної  схеми ми одержали |→ 0.4 А5, то нечітка

оцінка результату належить діагональному елементу останньої матриці на перетині рядка і стовпця А5.

Перейдемо до узагальнення. Спочатку опишемо власне процедуру Matrix-fuzzy-deduction нечіткого виведення

на основі матричного методу:

Крок 1. Будуємо матрицю M для вихідної множини нечітких правил.

Крок 2. Застосовуємо правило A до матриці M.

Крок 3. Застосовуємо правило B до матриці M.

Крок 4. За необхідності повертаємося на крок 2, інакше p = 1 і переходимо на крок 5.

Крок 5. Отримуємо матрицю Mp, модифікуючи  операцію множення матриць: у випадку наявності

індексів „∧” у стовпцях для  літералів А1, Аі множення (k⊗l) ⊗q необхідно виконувати за формулою min{min{k,

q}, min{l, q}}; у випадку наявності  індексів „∨” у стовпцях для  літералів А1, А2 для множення  необхідно вибрати максимальний  із двох добутків у рядку max {min{k, q}, min{l, r}}. Якщо виконується ознака суперечливості або супротивного випадку, то кінець, інакше p = p + 1 і переходимо на крок 5.

Оскільки ознака виводимості –  наявність певної структури С  на головній діагоналі – сформульована, залишається довести правомірність її застосування.

Теорема 1. Множина нечітких правил S суперечлива тоді і тільки тоді, коли застосування процедури Matrix-fuzzy-deduction приводить до побудови матриці МР з ненульовою головною діагоналлю. При цьому нечітка оцінка належить діагональному елементу останньої матриці на перетині рядка і стовпця, які відповідають нечіткому твердженню, що перевіряється, і відповідає оцінці, отриманій застосуванням визначення операцій (3) і правил виведення кроку 2 вищенаведеної схеми.

Доведення. Пряма теорема. Нехай  застосуванням процедури Matrix-deduction встановлено існування такого натурального p, що матриця МР має ненульову  головну діагональ. Доведемо, що множина  клауз суперечлива.

По-перше, доведемо, що правило A залишає  суперечливу множину клауз суперечливою. Дійсно, якщо множина клауз суперечлива, то існує послідовність резолюцій, останньою резольвентою якої є порожня клауза.

З визначення правила резолюції  негайним наслідком є те, що в  зазначеній послідовності не може приймати участь клауза, в яку входить вилучений за допомогою правила A літерал, адже відповідний літерал не зустрічається в правих частинах клауз. Тоді застосування правила A не може привести до зникнення зазначеної послідовності, тобто множина клауз залишається суперечливою.

По-друге, доведемо, що правило B залишає  суперечливу множину клауз суперечливою. Дійсно, якщо множина клауз суперечлива, то існує послідовність резолюцій, останньою резольвентою якої є порожня  клауза.

З визначення правила резолюції  негайним наслідком є те, що в зазначеній послідовності не може приймати участь вилучена за допомогою правила B клауза, адже відповідний літеральне не зустрічається в лівих частинах клауз. Тоді застосування правила B не може привести до зникнення зазначеної послідовності, тобто множина

клауз залишається суперечливою.

Нехай застосування правил A, B не привело  до встановлення несперечливості множини  клауз і побудовою матриць  МР встановлено існування такого натурального p, що матриця МР має  ненульову головну діагональ. Доведемо, що множина клауз суперечлива.

 

Методи та засоби програмної інженерії

Будемо використовувати індукцію за максимальною резолютивною відстанню (максимальною довжиною від літерала у правій частині кляузи до порожнього літерала у лівій частині кляузи через резолютивні переходи). Тоді базис індукції пов’язаний з правилом |→ k А1 і встановленням того, що А1 є логічним наслідком цієї клаузи. Очевидно, що в цьому випадку множина клауз суперечлива, а нечітка оцінка належить діагональному елементу для А1 і відповідає оцінці, отриманій застосуванням визначення операцій (3) і правил виведення кроку 2 вищенаведеної схеми. Індуктивне припущення: теорема виконується для довільної системи клауз з максимальною резолютивною відстанню n. Залишається довести, що теорема виконується для довільної системи клауз з максимальною резолютивною відстанню n+1. Дійсно, відома теорема про відповідність циклів і ненульових елементів головної діагоналі матриці суміжності графа на основі індуктивного припущення свідчить про заповнення всіх діагональних елементів для всіх шляхів довжини n.

Тоді ще одне множення матриць приводить  до заповнення всіх інших діагональних елементів. При цьому визначення операцій через мінімальні і максимальні  елементи належить діагональному елементу останньої матриці на перетині рядка і стовпця, які відповідають нечіткому твердженню, що перевіряється, і відповідає оцінці, отриманій застосуванням визначення операцій (3) і правил виведення кроку 2 вищенаведеної схеми.

Обернена теорема. Нехай множина  нечітких правил суперечлива і застосуванням визначення операцій (3) і правил виведення кроку 2 вищенаведеної схеми отримана нечітка оцінка. Доведемо, що застосування процедури Matrix-fuzzy-deduction приводить до побудови такої матриці МР, що її головна діагональ ненульова, а діагональний елемент для твердження, що перевіряється, містить нечітку оцінку, яка відповідає оцінці, отриманій застосуванням визначення операцій (3) і правил виведення кроку 2 вищенаведеної схеми.

Застосування правил A, B не змінить  суперечливість множини правил. За умови суперечливості множини правил існує така послідовність застосувань правила резолюцій, що остання резольвента є порожньою. Тоді за побудовою матриця М1 містить шляхи довжини 1 від літерала в рядку до літерала в стовпці. Тоді із визначення множення матриць М2 містить шляхи довжини 2 від літерала в рядку до літерала в стовпці. В загальному випадку МР містить шляхи довжини p від літерала в рядку до літерала в стовпці.

Якщо всі застосування правил A, B відсікають літерали, які не приймають участь у резолюціях, то тоді залишаються лише літерали, які безпосередньо приймають участь у резолюціях. Отже, всі діагональні елементи повинні врешті решт стати ненульовими, а ті які вже стали ненульовими, не перетворяться у нульові. При цьому визначення операцій через мінімальні і максимальні елементи повторює резолюції, а діагональний елемент останньої матриці на перетині рядка і стовпця, які відповідають нечіткому твердженню, що перевіряється, буде відповідати оцінці, отриманій застосуванням визначення операцій (3) і правил виведення кроку 2 вищенаведеної схеми. Теорема доведена.

 

Висновки

Застосування першої версії платформи SmartBase підтвердило працездатність закладених в її основу ідей. З її використанням швидко створено інформаційно-керуюче ядро та декілька застосувань системи управління одного з міністерств. На базі платформи, наприклад, ефективно функціонує комплекс електронного діловодства, документообігу і контролю рішень. Розвиток платформи пов’язаний із залученням алгоритмів інтелектуального аналізу даних і адаптації, схем розрахунків. Запропонована нова стратегія резолютивного виведення для нечітких правил на основі застосування матричних форм дозволяє застосовувати механізми виведення за умов нечіткої інформації. Подальший розвиток досліджень пов’язаний з розробкою методик відтворення виводів за послідовністю результатів множення матриць а також застосуванням методу для нечітких нейромереж.

Література

1. Павлов А.А., Теленик С.Ф. Адаптивные технологии и алгоритмизация в системах управления. – Киев: Техника, 2003. – 340 с.

2. Ковальски Р. Логика в решении проблем. – М.: Наука, 1990. – 280 с.

3. Теленик С.Ф., Амонс О.А., Смічик Р.В., Хмелюк В.С. Матрична резолюція для клаузальної логіки // Вісник ХНАДУ, 2005. – вип. 22. –

С. 94 – 97.

4. Nguyen H.T, Walker E.A. A First Course in Fuzzy Logic. – CHAPMAN & HALL/CRC. – 2000.