Машина висно́вування — програма, яка робить логічні висновки з попередньо побудованої бази фактів і правил згідно з законами формальної логіки.
Компоненти машини висновування
Правила продукційної моделі не впорядковані. Кожне з них існує незалежно від інших правил. У зв'язку з цим потрібний спеціальний механізм, який керуватиме перебиранням правил. Такий механізм і є машиною висновування.
Машина висновування є однією із складових експертної системи і своєю чергою складається з двох компонентів:
- Компонент висновування реалізує власний дедуктивний висновок. Тобто якщо в базі фактів є факт A, а в базі правил є правило If A then B, то робиться висновок про необхідність застосування дії B.
- Компонент керування, або інтерпретатор правил керує процесом перебирання фактів і застосування правил.
Інтерпретатор правил працює за таким алгоритмом:
- Зіставлення. Здійснюється пошук множини правил, посилки яких зіставляються хоча б з одним фактом із бази фактів. Усі правила з цієї множини є застосовними до поточної бази фактів. Якщо правил у цій множині більше одного, то кажуть, що множина правил є конфліктною (у тому розумінні, що будь-яке з правил можна застосувати і невідомо, яке саме).
- Вибір. Алгоритм роботи інтерпретатора є циклічним. На кожній ітерації циклу може бути застосовано лише одне правило. Якщо правил більше одного, інтерпретатор має вирішити конфлікт, тобто обрати з правил найвідповідніше. Вибір здійснюється на основі критерію, який може встановлюватися ззовні.
- Виконання. Відібране правило запускається на виконання (спрацьовує). Суть спрацьовування полягає у виконанні дії, описаної у висновку правила. Такими діями можуть бути:
- коректування критерію вибору правил;
- запис, видалення або коректування фактів у базі фактів;
- запис, видалення або коректування фактів у базі правил;
- виконання інших дій (ведення діалогу з людиною, перевірка цілісності тощо).
Схематично процес інтерпретації правил зображено на рисунку:
У цій схемі робота машини висновування залежить від стану бази знань і критерію вибору правил. Існує також варіант організації машини висновування, за якого враховується передісторія її роботи, тобто поведінка механізму виведення на попередніх ітераціях.
Стратегії керування висновуванням
Машина висновування має вирішувати, як перебирати факти і правила бази знань, а також на підставі якого критерію слід вибирати правила з конфліктної множини. Відповідні рішення приймаються згідно з обраною стратегією керування висновування. Зазвичай основні складові цієї стратегії вбудовані в машину висновування і їх не можна змінити.
Розробляючи стратегію керування висновуванням, слід вирішити такі питання:
- Яку точку в просторі станів обрати як початкову? Від вибору цієї точки залежить спосіб виконання пошуку — в прямому чи зворотному напрямку.
- Якою має бути стратегія перебирання правил — углибину чи вшир?
Пряме і зворотне висновування
У системах з прямим висновуванням за відомими фактами відшукується факт, який з них випливає (див. мал. 2). Якщо такий факт вдається знайти, то він записується в базу фактів. Пряме висновування називають також висновуванням, керованим даними, або висновуванням, керованим посилками правил.
Під час зворотного висновування спочатку висувається гіпотеза, а потім механізм висновування ніби повертається назад, переходячи до фактів і намагаючись знайти в базі фактів ті, які підтверджують гіпотезу (рис.2б). Якщо гіпотеза не підтверджується фактами з бази фактів, одна з її можливих посилок вважається гіпотезою, що деталізує початкову і є стосовно неї підціллю. Далі відшукуються факти, які могли б підтвердити дану підціль, тобто процес рекурсивно повторюється. Висновування цього типу називається також висновуванням, керованим цілями.
Пошук вглиб та вшир
Під час пошуку вглиб черговою підціллю стає та, що відповідає детальнішому рівню опису задачі. Виконуючи пошук ушир, машина висновування спочатку спробує знайти розв'язок серед можливих варіантів одного рівня і потім, за необхідності, перейде на наступний рівень деталізації.
Проблеми
Продукційна модель знімає обмеження, характерні для логіки, проте з нею пов'язані інші пробеми: нескінченні цикли, можлива суперечність знань і непрозорість поведінки машини висновування.
Нескінченні цикли виникають у тому випадку, коли машина висновування повертається до правил, які вже були переглянуті. Це можливо, наприклад, за наявності таких правил:
If A then B; If B then C; If C then A.
Суперечливі знання з'являються тоді, коли додавання нових правил призводить до суперечності тим фактам, які можна було отримати раніше.
Непрозорість поведінки обумовлена тим, що немає жодних принципів, які б встановлювали порядок перегляду правил і їхнього застосування в тому випадку, коли може бути застосовано кілька правил. Унаслідок цього досить важко обробляти всі продукційні бази знань великого обсягу, оскільки навіть за умов коректності всіх наявних правил хибний порядок їхнього виконання може привести до помилок, які важко виявити.
Частково зняти обмеження, характерні для формально-логічної та продукційної моделей, можна шляхом структуризації бази знань. Названі моделі допускають зображення в базі знань лише елементарних фактів. Структуризація фактів приводить до створення груп взаємопов'язаних фактів, тобто певних абстракцій. Структурні абстракції можуть мати свою семантику, щодо якої застосовуються правила висновування.
Семантичні мережі та фрейми, найчастіше використовуються у моделях, які підтримують структурні абстракції.
Література
- В.В. Пасічник, В.А. Резніченко "Організація баз даних та знань" Видавнича група BHV, 2006.
Див.також
- Машина вывода, подсистема моделирования и планировщики [ 1 жовтня 2008 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Mashina visno vuvannya programa yaka robit logichni visnovki z poperedno pobudovanoyi bazi faktiv i pravil zgidno z zakonami formalnoyi logiki Komponenti mashini visnovuvannyaPravila produkcijnoyi modeli ne vporyadkovani Kozhne z nih isnuye nezalezhno vid inshih pravil U zv yazku z cim potribnij specialnij mehanizm yakij keruvatime perebirannyam pravil Takij mehanizm i ye mashinoyu visnovuvannya Mashina visnovuvannya ye odniyeyu iz skladovih ekspertnoyi sistemi i svoyeyu chergoyu skladayetsya z dvoh komponentiv Komponent visnovuvannya realizuye vlasnij deduktivnij visnovok Tobto yaksho v bazi faktiv ye fakt A a v bazi pravil ye pravilo If A then B to robitsya visnovok pro neobhidnist zastosuvannya diyi B Komponent keruvannya abo interpretator pravil keruye procesom perebirannya faktiv i zastosuvannya pravil Interpretator pravil pracyuye za takim algoritmom Zistavlennya Zdijsnyuyetsya poshuk mnozhini pravil posilki yakih zistavlyayutsya hocha b z odnim faktom iz bazi faktiv Usi pravila z ciyeyi mnozhini ye zastosovnimi do potochnoyi bazi faktiv Yaksho pravil u cij mnozhini bilshe odnogo to kazhut sho mnozhina pravil ye konfliktnoyu u tomu rozuminni sho bud yake z pravil mozhna zastosuvati i nevidomo yake same Vibir Algoritm roboti interpretatora ye ciklichnim Na kozhnij iteraciyi ciklu mozhe buti zastosovano lishe odne pravilo Yaksho pravil bilshe odnogo interpretator maye virishiti konflikt tobto obrati z pravil najvidpovidnishe Vibir zdijsnyuyetsya na osnovi kriteriyu yakij mozhe vstanovlyuvatisya zzovni Vikonannya Vidibrane pravilo zapuskayetsya na vikonannya spracovuye Sut spracovuvannya polyagaye u vikonanni diyi opisanoyi u visnovku pravila Takimi diyami mozhut buti korektuvannya kriteriyu viboru pravil zapis vidalennya abo korektuvannya faktiv u bazi faktiv zapis vidalennya abo korektuvannya faktiv u bazi pravil vikonannya inshih dij vedennya dialogu z lyudinoyu perevirka cilisnosti tosho Shematichno proces interpretaciyi pravil zobrazheno na risunku ris 1 Interpretaciyi pravil U cij shemi robota mashini visnovuvannya zalezhit vid stanu bazi znan i kriteriyu viboru pravil Isnuye takozh variant organizaciyi mashini visnovuvannya za yakogo vrahovuyetsya peredistoriya yiyi roboti tobto povedinka mehanizmu vivedennya na poperednih iteraciyah Strategiyi keruvannya visnovuvannyamStrategiyi vivedennya Mashina visnovuvannya maye virishuvati yak perebirati fakti i pravila bazi znan a takozh na pidstavi yakogo kriteriyu slid vibirati pravila z konfliktnoyi mnozhini Vidpovidni rishennya prijmayutsya zgidno z obranoyu strategiyeyu keruvannya visnovuvannya Zazvichaj osnovni skladovi ciyeyi strategiyi vbudovani v mashinu visnovuvannya i yih ne mozhna zminiti Rozroblyayuchi strategiyu keruvannya visnovuvannyam slid virishiti taki pitannya Yaku tochku v prostori staniv obrati yak pochatkovu Vid viboru ciyeyi tochki zalezhit sposib vikonannya poshuku v pryamomu chi zvorotnomu napryamku Yakoyu maye buti strategiya perebirannya pravil uglibinu chi vshir Pryame i zvorotne visnovuvannya U sistemah z pryamim visnovuvannyam za vidomimi faktami vidshukuyetsya fakt yakij z nih viplivaye div mal 2 Yaksho takij fakt vdayetsya znajti to vin zapisuyetsya v bazu faktiv Pryame visnovuvannya nazivayut takozh visnovuvannyam kerovanim danimi abo visnovuvannyam kerovanim posilkami pravil Pid chas zvorotnogo visnovuvannya spochatku visuvayetsya gipoteza a potim mehanizm visnovuvannya nibi povertayetsya nazad perehodyachi do faktiv i namagayuchis znajti v bazi faktiv ti yaki pidtverdzhuyut gipotezu ris 2b Yaksho gipoteza ne pidtverdzhuyetsya faktami z bazi faktiv odna z yiyi mozhlivih posilok vvazhayetsya gipotezoyu sho detalizuye pochatkovu i ye stosovno neyi pidcillyu Dali vidshukuyutsya fakti yaki mogli b pidtverditi danu pidcil tobto proces rekursivno povtoryuyetsya Visnovuvannya cogo tipu nazivayetsya takozh visnovuvannyam kerovanim cilyami Poshuk vglib ta vshir Poshuk vshir Poshuk vglib Pid chas poshuku vglib chergovoyu pidcillyu staye ta sho vidpovidaye detalnishomu rivnyu opisu zadachi Vikonuyuchi poshuk ushir mashina visnovuvannya spochatku sprobuye znajti rozv yazok sered mozhlivih variantiv odnogo rivnya i potim za neobhidnosti perejde na nastupnij riven detalizaciyi Div takozh Poshuk u glibinu Div takozh Poshuk u shirinu Problemi Produkcijna model znimaye obmezhennya harakterni dlya logiki prote z neyu pov yazani inshi probemi neskinchenni cikli mozhliva superechnist znan i neprozorist povedinki mashini visnovuvannya Neskinchenni cikli vinikayut u tomu vipadku koli mashina visnovuvannya povertayetsya do pravil yaki vzhe buli pereglyanuti Ce mozhlivo napriklad za nayavnosti takih pravil If A then B If B then C If C then A Superechlivi znannya z yavlyayutsya todi koli dodavannya novih pravil prizvodit do superechnosti tim faktam yaki mozhna bulo otrimati ranishe Neprozorist povedinki obumovlena tim sho nemaye zhodnih principiv yaki b vstanovlyuvali poryadok pereglyadu pravil i yihnogo zastosuvannya v tomu vipadku koli mozhe buti zastosovano kilka pravil Unaslidok cogo dosit vazhko obroblyati vsi produkcijni bazi znan velikogo obsyagu oskilki navit za umov korektnosti vsih nayavnih pravil hibnij poryadok yihnogo vikonannya mozhe privesti do pomilok yaki vazhko viyaviti Chastkovo znyati obmezhennya harakterni dlya formalno logichnoyi ta produkcijnoyi modelej mozhna shlyahom strukturizaciyi bazi znan Nazvani modeli dopuskayut zobrazhennya v bazi znan lishe elementarnih faktiv Strukturizaciya faktiv privodit do stvorennya grup vzayemopov yazanih faktiv tobto pevnih abstrakcij Strukturni abstrakciyi mozhut mati svoyu semantiku shodo yakoyi zastosovuyutsya pravila visnovuvannya Semantichni merezhi ta frejmi najchastishe vikoristovuyutsya u modelyah yaki pidtrimuyut strukturni abstrakciyi LiteraturaV V Pasichnik V A Reznichenko Organizaciya baz danih ta znan Vidavnicha grupa BHV 2006 Div takozhMashina vyvoda podsistema modelirovaniya i planirovshiki 1 zhovtnya 2008 u Wayback Machine