Аналіз знизу вгору і за згори вниз

АНАЛІЗ ЗНИЗУ ДОГОРИ І ЗГОРИ ВНИЗ.

«Згори донизу» vs. «знизу вгору», «прямий» vs. «зворотний», «керований даними» vs. «спонукуваний метою» — три пари визначень для таких термінів, як «ланцюгової аналіз», «парсинг», «синтаксичний розбір», «логічний аналіз» і «пошук». У принципі так, всі ці терміни відбивають подібні відносини, і розбіжності з-поміж них лише у цьому, що вони взяті з різних подобластей комп’ютерна наука і штучного інтелекту (парсинг, системи з закладені у них правилами, пошукові системи та системи, створені задля розв’язання проблеми і т.д.).

Суть цих протиставлень можна проілюструвати з прикладу парадигми пошуку. Основне завдання будь-якого пошуку у тому, щоб визначити маршрут, яким ви переміщатися зі справжньою позиції до вашої мети. Якщо ви хоч почнете пошук із поточною позиції і продовжуватимете його, доки наткнетеся на бажаного результату, — це званий прямий пошук чи пошук знизу вгору. Якщо вже ви подумки ставите себе у те місце, де ви бажаєте опинитись у результаті пошуку це й визначаєте маршрут, рухаючись в напрямку, тобто. туди, де справді перебуваєте у сьогодні, — це пошук у напрямі чи пошук згори донизу. Зверніть увагу, що, визначивши маршрут внаслідок зворотного пошуку, вам все-таки доведеться дістатись своєї мети. Попри те що, що зараз рухаєтеся вперед, не є прямим пошуком, т.к. пошук вже було здійснено раніше, причому у напрямку. Ці самі протиставлення можна розгледіти з прикладу систем з умонтованими правилами. Уявімо, що правило складається з набору антецедентов і набору наслідків. Коли система визначає, що це антецеденты певного правила задоволені, цього правила викликається і виконується (виконується чи кожне викликане правило залежить від специфіки конкретної системи). Після цього, у базу знань заносяться затвердження, отримані у виконання правила, і виконуються відповідні операції. Цей процес відбувається вищеописаним чином, незалежно від того, застосовує чи система прямій чи зворотний логічний аналіз. Щоб проілюструвати різницю між ними, слід окремо розглянути процедуру активації правила. Викликаються лише активовані правила. При прямому логічному аналізі (знизу вгору), як у систему додаються нові дані, вони порівнюються з усіма антецедентами всіх правил. Якщо є відповідають антецеденту правила, це правило активується (коли вона ще є активованим), і якщо підібрані все антецеденты певного правила, воно викликається. Твердження, отримані в результаті виконання правила, заносять у базу знань і розглядаються в ролі нових даних, порівнюються з антецедентами і може викликати активацію і виклик додаткових правил. При зворотному логічному аналізі (згори донизу) при додаванні даних правила не активуються. Коли система отримує запит, він порівнюється з усіма наслідками всіх правил. Якщо запит збігається з наслідком, це правило активується, проте його антецеденты розглядаються як вторинних запитів і може викликати активацію додаткових правил. Коли запит відповідає не обмеженому умовою утвердженню бази знань, нею надходить відповідь, і коли цей запит виходив від антецедента, вважається, що він задовольняє останньому. Коли всі антецеденты деякого правила задовольняться, правило викликається і виконується. За виконання правила здійснюється у відповідь запити, що його активували, і тепер інші антецеденты вважаються задоволеними і може викликатися відповідні їм правила. Зверніть увагу, що виклик і виконання правила завжди відбувається у прямий послідовності, а відмінність прямого ланцюгового аналізу протилежного у тому, коли активується правило.

Примеры.

Парсинг. Спробуємо проілюструвати і пояснити відмінність між синтаксичним аналізом згори донизу і знизу вгору з прикладу пропозиції «They are flying planes» та простий граматики, поданої у вигляді пронумерованих правил:

1. P. S (NP VP.

2. NP (N.

3. NP (PRO.

4. NP (ADJ N.

5. VP (VT NP.

6. VT (V.

7. VT (AUX V.

8. N (planes.

9. PRO (they.

10. ADJ (flying.

11. AUX (are.

12. V (are.

13. V (flying.

Антецеденты вказані з боку, а слідства — з лівого. Наприклад, правило 1 читається так: «Якщо послідовність складається з іменний групи (NP), яку слід глагольная група (VP), ця послідовність є пропозицією (S).».

Синтаксичний розбір згори донизу починається з символу P. S, що й буде вершиною дерева розбору. Цю процедуру еквівалентна процедурі постановки завдання, що полягає у тому, щоб визначити, чи є послідовність слів пропозицією. Правило 1 говорить, що кожне пропозицію складається з іменний групи (NP), яку слід глагольная група (VP). За наявності кількох правил, спочатку застосовується правило з найменшою номером, та був воно розширюється зліва-направо. Таким чином наступним кроком є перебування першої зв’язку, тобто. NP. Спочатку активується правило 2, та був правило 8 (рис. 2а). Т.к. «planes» не відповідає «they», алгоритм спрацьовує знову, і тепер спочатку активується правило 3, та був правило 9. Потім алгоритм повертається до правилу 1 і такий метою ставить визначення VP. Спочатку активуються правила 5, 6, та був 12 (рис. 2b). Подальший хід розбору отржен на малюнку 2 (з, d, e). Синтаксичний розбір знизу вгору починається зі слів у пропозиції. Знову ж розбір ведеться зліва-направо, і спочатку застосовується правило з найменшою номером. Отже, спочатку перше слово пропозиції «they» співвідноситься з антецедентом правила 9, яке після виконання видає твердження, що «they» є займенником (PRO). Потім виконується правило 3 видає, що «they» є NP. NP відповідає антецедентам правил 1 і п’яти, але й одна з цих правил ще викликано, тому розбір переходить до «are». Виконується правило 11 (як і раніше, що правило 12 також викликано, воно не виконується відповідно до правилом про послідовності виконання правил). Потім виконуються правила 10, 8 і 2 (рис. За). На даної стадії подальший розбір послідовності NP+AUX+ADJ+NP неможливий, тому ми повертаємося до останнього викликаного, але ще виконаного правилу, тобто. до правилу 4. Розбір послідовності NP+AUX+NP як і неможливий, тому знову виконується останнє викликане невиконану правило. Зараз цього правила 13, яке видає, що «flying» є V. Потім виконуються правила 6 і п’яти (рис. 3с). Розбір последователльности NP+AUX+VP неможливий, тому виконується правило 7 видає твердження, що «are flying» є VT. Потім знову виконуються правила 5 і одну, тоді і закінчується синтаксичний розбір (рис. 3d). Цей приклад було наведено із єдиною метою порівняння механізмів синтаксичного розбору знизу вгору й за згори донизу. Встановлення суворого порядку розбору зліва праворуч і нумерація правил зумовлені намаганням до застосування в найбільшою мірою подібного алгоритму, як і раніше, що результати розбору виявилися различными.

Системи з умонтованими правилами. Розглянемо прямий і зворотний ланцюгової аналіз з прикладу вигаданого набору правил у тому, як слід провести вечір. Правила перебувають у звичайному порядку, антецедент розташовується зліва, а слідство — справа, все викликані правила виконуються, а розбір ведеться паралельно. 1. Хороший фільм на ТБ + Раннього ранку зустрічей немає (Пізніше кіно 2. Раннього ранку зустрічей немає + Потрібно попрацювати (Робота допізна 3. Потрібно попрацювати + Необхідні документи (Праця у офісі 4. Пізніше кіно (Не спати допізна 5. Робота допізна (Не спати допізна 6. Робота допізна (Повернення до офісу 7. Праця у офісі (Повернення в офис.

Наприклад, правило 1 говорить, що й на ТБ йде хороше кіно України й в мене завтра рано-вранці зустрічей немає, тоді вже іду режиму «Пізніше кіно». Розглянемо спочатку приклад прямого ланцюгового аналізу. Припустимо, система отримала початкову інформацію у тому, що назавтра рано уторм не маю зустрічей. Активуються правила 1 і 2. Припустимо, що далі системі поставлено повідомлення у тому, що це слід попрацювати. Активується правило 3, а правило 2 викликається і выполняетя, звідки напрошується висновок, що перебуваю в режимі «Робота допізна», у результаті викликаються і виконуються правила 5 і шість. У результаті система укладає, що має повернутися до офісу і не спати допізна. Тепер на цю проблему із застосуванням зворотного ланцюгового аналізу. Припустимо, що систему отримала вихідну інформацію у тому, що з мене завтра вранці зустрічей, але щоб мені потрібно ще попрацювати, та був її (систему) запитали, чи варто мені повернутися до офіс. Цей запит активує правила 6 і аналогічних сім. Натомість постане кадрове питання «Робота допізна» чи «Праця у офісі»? У цьому активуються правила 2 і трьох, і виникає питання «Раннього ранку зустрічей немає», «Потрібно попрацювати» чи «Потрібні документи»? Перші дві антецедента задовольняться, в такий спосіб правило 2 буде зумовлене виконано, що воно потягне у себе задоволення антецедента «Робота допізна», виклик і виконання правила 6, у результаті система дійшов висновку, що слід повернутися до офіс. Зверніть увагу, що з прямому розборі породжується більше наслідків, а при зворотному — запитів. Т.к. в обох прикладах використовувалися одні й самі дані, то процесі проведення аналізу виконувалися одні й самі правила, але активировались различные.

Сравнение.

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

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

Смешанные стратегии.

Пошук у двох напрямах. Не ясно, якого вигляду пошуку — прямій чи зворотний — є найбільш приемлимым конкретної докладання, слід здійснювати пошук у двох напрямах. У разі, відправними точками стають початкова й кінцеве стан, та відшуковування здійснюється за до центру. Висновок в двох напрямах. При даному підході найперші дані застосовуються для активирования правил, котоые перебирають інші антецеденты у порядку. Побічні запити, які відповідають ні слідством, ні даним, зберігаються як «демонів», які можна задоволені пізніше з допомогою нових, або пізніше які поступили даних. Систему можна розробити в такий спосіб, що ці, задовольняють «демонам» (антецеденты активованих правил) ні активувати додаткові правила, що «змусить» систему при майбутньому прямому виведення сконцентруватися на правилах, які враховують попередній контекст.

Розбір з початком у лівій розі. Застосувавши вищеописаний метод до парсингу, ми матимемо так званий розбір з початком у лівій розі. У термінах прикладу, наведеного розділ парсинг, система спочатку розгляне «they», знайде правило 9 — єдине правило, що можна застосувати до цього слову, потім правило 3, що пояснювало PRO, та був правило 1, як єдине правило, слідство якого починається з NP. Далі система спробує розібрати згори донизу «are flying planes» як VP.

Заключение

.

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

ПРИЛОЖЕНИЕ.