Марковскі алгоритми

Продукційні системи Поста

В символьній логіці продукційні системи вперше були використані Е. Постом. Він довів, що будь-яка система математики чи логіки може бути оформлена у вигляді системи продукційних правил певного типу.

Крім того, продукційні правила використаються в лінгвістиці у формі правил підстановки для визначення граматики мови. Комп'ютерні мови звичайно визначаються за допомогою продукційних правил, відомих як нормальна форма Бекуса-Наура (BNF).

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

Продукційна система Поста складається із групи продукційних правил, наприклад

(1) двигун автомобіля не запускається → перевірити акумулятор

(2) двигун автомобіля не запускається → перевірити наявність бензину

(3) перевірити акумулятор AND акумулятор несправний → замінити акумулятор

(4) перевірити наявність бензину AND бензин відсутній → заповнити бак бензином

Якщо є рядок "двигун автомобіля не запускається", то можна використати правило (1) або (2) для вироблення рядків "перевірити акумулятор" й "перевірити наявність бензину". Але може бути застосовано лише одне з них, обоє правила послідовно або жодного з правил. Якщо є рядок "перевірити акумулятор", а також рядок "акумулятор несправний", то може бути застосоване правило (3) для вироблення рядка "замінити акумулятор".

На відміну від звичайної мови програмування, такої як С або С++, порядок, у якому записані правила, не має значення.

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

Наступний великий крок у розробці методів застосування продукційних правил зроблений на основі відкриття Маркова щодо визначення структури керування для продукційних систем.

Марковський алгоритм - це застосування впорядкованої групи продукцій до вхідного рядка в порядку пріоритету. Якщо правило з найвищим пріоритетом є непридатним, то виконується наступне правило і т.д.

Марковський алгоритм завершує роботу за умов:

§ остання з продукцій не застосовна до рядка,

§ виконано продукцію, що кінчається крапкою.

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

AB → HIJ

після її застосування до вхідного рядка GABKAB виробляє новий рядок GHIJKAB. Оскільки тепер продукція застосовується до нового рядка, кінцевим результатом стає рядок GHIJKHIJ.

Окрім констант передбачено два типи змінних:

§ односимвольні змінні (a, b, c, …, x, y, z) представляють будь-який окремий символ;

§ грецькі букви α, β і т.д. використаються в рядках як спеціальні знаки пунктуації.

Сховані марковські моделі (Hidden Marcov Model – HMM) використаються в розпізнаванні образів, зокрема, розпізнаванні мови.

Дата добавления: 2014-01-07