АНАЛІЗ ЗНИЗИТИ ВГОРУ І СВЕРХУ ВНИЗ

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

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

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

Приклади

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

1. 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 )."

Синтаксичний розбір зверху вниз починається з символу 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 і 5, але жодне з цих правил ще не викликане, тому розбір переходить до "are". Виконується правило 11 (незважаючи на те, що правило 12 також викликано, воно не виконується відповідно до правила про послідовності виконання правил). Потім виконуються правила 10, 8 і 2 (рис. 3а). На даній стадії подальший розбір послідовності NP + AUX + ADJ + NP неможливий, тому ми повертаємося до останньому викликаному, але ще не виконаному правилом, тобто до правила 4. Розбір послідовності NP + AUX + NP так само неможливий, тому знову виконується останнє викликане невиконане правило. Зараз це правило 13, яке видає, що "flying" є V. Потім виконуються правила 6 і 5 (рис. 3с). Розбір последователльності NP + AUX + VP неможливий, тому виконується правило 7 і видає твердження, що "are flying "є VT. Потім знову виконуються правила 5 і 1, на чому і закінчується синтаксичний розбір (рис. 3d).

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

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

1. Хороший фільм по ТВ + Рано вранці зустрічей немає ® Пізніше кіно

2. Рано-вранці зустрічей немає + Треба попрацювати ® Робота допізна

3. Потрібно попрацювати + Необхідні документи ® Робота в офісі

4. Пізніше кіно ® Не спати допізна

5. Робота допізна ® Не спати допізна

6. Робота допізна ® Повернення в офіс

7. Робота в офісі ® Повернення в офіс

Наприклад, правило 1 свідчить, що якщо по ТВ йде добре кіно і в мене завтра рано вранці зустрічей ні, тоді я дотримуюся режиму "Пізніше кіно".

Розглянемо спершу приклад прямого ланцюгового аналізу. Припустимо, система отримала початкову інформацію про те, що завтра рано уторм у мене немає зустрічей. Активуються правила 1 і 2. Припустимо, що далі система отримала повідомлення про те, що мені потрібно попрацювати. Активується правило 3, а правило 2 викликається і виполняетя, звідки випливає висновок, що я знаходжуся в режимі "Робота допізна", в результаті чого викликаються і виконуються правила 5 і 6. У результаті система робить висновок, що я повинна повернутися в офіс і не спати допізна.

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

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

Порівняння

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

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

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

Змішані стратегії

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

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

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

Висновок

Зазвичай в системах штучного інтелекту застосовується один з двох видів аналізу. Перший - це аналіз знизу вгору або прямий аналіз, а другий-зверху вниз або зворотний. Відмінність їх визначається тим, в якому напрямку ведеться пошук (від початку в кінець або навпаки) і який елемент (наслідок або антецедент) активує правила.

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

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

Для підготовки даної роботи були використані матеріали з сайту http://www.ed.vseved.ru/