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

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

«Сверху вниз» 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. У результаті система укладає, що має повернутися до офісу і спати допоздна.

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

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

Сравнение

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

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

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

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

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

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

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

Заключение

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

Фактор ефективності і легкості впровадження може зіграти на вирішальній ролі під час виборів виду аналізу, який застосовуватися у певному додатку, однак слід пам’ятати, що використання змішаних стратегій також возможно.

Список литературы

Для підготовки даної роботи було використані матеріали із російського сайту internet.