Реферат: Анализ снизу вверх и сверху вниз
<span Times New Roman",«serif»">АНАЛИЗ СНИЗУ ВВЕРХ И СВЕРХУ ВНИЗ
<span Times New Roman",«serif»"><span Times New Roman",«serif»">
<span Times New Roman",«serif»">“Сверху вниз” vs. “снизу вверх”,“прямой” vs. “обратный”, “управляемый данными” vs. “движимый целью” — три парыопределений для таких терминов, как “цепной анализ”, “парсинг”, “синтаксическийразбор”, “логический анализ” и “поиск”. В принципе, все эти термины отражаютсходные отношения, и различие между ними состоит лишь в том, что они взяты изразличных подобластей компьютерной науки и искусственного интеллекта (парсинг,системы с заложенными в них правилами, поисковые системы и системы,направленные на решение проблем и т.д.)
<span Times New Roman",«serif»">Суть этих противопоставлений можнопроиллюстрировать на примере парадигмы поиска. Основная задача любого поискасостоит в том, чтобы определить маршрут, по которому вы будете перемещаться снастоящей позиции к вашей цели. Если вы начнете поиск с текущей позиции ибудете продолжать его, пока не наткнетесь на желаемый результат, — это такназываемый прямой поиск или поиск снизу вверх. Если вы мысленно ставите себя вто место, где вы хотите очутиться в результате поиска и определяете маршрут,двигаясь в обратном направлении, т.е. туда, где вы действительно находитесь внастоящий момент, — это поиск в обратном направлении или поиск сверху вниз.Обратите внимание на то, что, определив маршрут в результате обратного поиска,вам все же предстоит добраться до своей цели. Несмотря на то, что сейчас выдвижетесь вперед, это не является прямым поиском, т.к. поиск уже былосуществлен ранее, причем в обратном направлении.
<span Times New Roman",«serif»">Эти же противопоставления можнорассмотреть на примере систем с встроенными правилами. Представим себе, чтоправило состоит из набора антецедентов и набора следствий. Когда системаопределяет, что все антецеденты определенного правила удовлетворены, это правиловызывается и выполняется (выполняется ли каждое вызванное правило зависит отспецифики конкретной системы). Послеэтого в базу знаний заносятся утверждения, полученные в результате выполненияправила, и выполняются соответствующие операции. Данный процесс происходитвышеописанным образом, независимо от того, применяет ли система прямой илиобратный логический анализ. Чтобы проиллюстрировать различия между ними,следует отдельно рассмотреть процедуру активации правила. Вызываются толькоактивированные правила. При прямом логическом анализе (снизу вверх), когда всистему добавляются новые данные, они сравниваются со всеми антецедентами всехправил. Если данные соответствуют антецеденту правила, то это правилоактивируется (если оно еще не является активированным), и если подобраны всеантецеденты определенного правила, то оно вызывается. Утверждения, полученные врезультате выполнения правила, заносятся в базу знаний и рассматриваются вкачестве новых данных, сравниваются с антецедентами и могут вызвать активацию ивызов дополнительных правил. При обратном логическом анализе (сверху вниз) придобавлении данных правила не активируются. Когда система получает запрос, онсравнивается со всеми следствиями всех правил. Если запрос совпадает соследствием, то это правило активируется, а все его антецеденты рассматриваютсяв качестве вторичных запросов и могут вызвать активацию дополнительных правил.Когда запрос соответствует не ограниченному условием утверждению базы знаний,на него поступает ответ, и если этот запрос исходил от антецедента, считается,что он удовлетворяет последнему. Когда все антецеденты некоторого правилабудут удовлетворены, правило вызывается и выполняется. При выполнении правилаосуществляется ответ на запросы, которые его активировали, и теперь другиеантецеденты считаются удовлетворенными и могут вызываться соответствующие имправила. Обратите внимание на то, что вызов и выполнение правила всегдапроисходит в прямой последовательности, а отличие прямого цепного анализа отобратного состоит в том, когда активируется правило.
<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Примеры
<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Парсинг
<span Times New Roman",«serif»">.Попытаемся проиллюстрировать и объяснить разницу между синтаксическим анализомсверху вниз и снизу вверх на примере предложения “They are flying planes” ипростой грамматики, представленной в виде пронумерованных правил:<span Times New Roman",«serif»">
<span Times New Roman",«serif»"> 1. S <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:GreekMathSymbols">®<span Times New Roman",«serif»"> NP VP<span Times New Roman",«serif»"> 2. NP
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">N<span Times New Roman",«serif»"> 3. NP
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">PRO<span Times New Roman",«serif»"> 4. NP
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">ADJ N<span Times New Roman",«serif»"> 5. VP
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">VT NP<span Times New Roman",«serif»"> 6. VT
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">V<span Times New Roman",«serif»"> 7. VT
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">AUX V<span Times New Roman",«serif»"> 8. N
<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:GreekMathSymbols">®<span Times New Roman",«serif»"> planes<span Times New Roman",«serif»"> 9. PRO
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">they<span Times New Roman",«serif»"> 10.ADJ
<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:GreekMathSymbols">®<span Times New Roman",«serif»"> flying<span Times New Roman",«serif»"> 11.AUX
<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:GreekMathSymbols">®<span Times New Roman",«serif»"> are<span Times New Roman",«serif»"> 12.V
<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:GreekMathSymbols">®<span Times New Roman",«serif»"> are<span Times New Roman",«serif»"> 13.V
<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:GreekMathSymbols">®<span Times New Roman",«serif»"> flying<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Антецеденты указаны с правой стороны, аследствия — с левой. Например, правило 1 читается следующим образом: “Еслипоследовательность состоит из именной группы (NP), за которой следуетглагольная группа (VP), то эта последовательность является предложением (S).”
<span Times New Roman",«serif»"> Синтаксический разбор сверху вниз начинаетсяс символа S, который и будет являтьсявершиной дерева разбора. Эта процедураэквивалентна процедуре постановки задачи, которая заключается в том, чтобыопределить, является ли последовательность слов предложением. Правило 1 гласит,что каждое предложение состоит из именной группы (NP), за которой следуетглагольная группа (VP). При наличии нескольких правил, сперва применяетсяправило с наименьшим номером, а затем оно расширяется слева направо. Такимобразом следующим шагом является нахождение первой связи, т.е. NP. Сперваактивируется правило 2, а затем правило 8 (рис. 2а). Т.к. “planes” не соответствует ”they”, алгоритм срабатываетвновь, и теперь сперва активируется правило 3, а затем правило 9. Затем алгоритм возвращается к правилу 1 иследующей целью ставит определение VP. Сперва активируются правила 5, 6, а затем 12 (рис. 2b). Дальнейший ход разбора отржен на рисунке 2 (с, d, e).
<span Times New Roman",«serif»">Синтаксический разбор снизу вверхначинается со слов в предложении. Опять же разбор ведется слева направо, исперва применяется правило с наименьшим номером. Итак, сначала первое словопредложения “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).
<span Times New Roman",«serif»">Данный пример был приведен с цельюсравнения механизмов синтаксического разбора снизу вверх и сверху вниз.Установление строгого порядка разбора слева направо и нумерация правил обусловлены стремлением к применению внаибольшей степени сходного алгоритма, несмотря на то, что результаты разбораоказались различными.
<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Системысо встроенными правилами
<span Times New Roman",«serif»">. Рассмотримпрямой и обратный цепной анализ на примере выдуманного набора правил о том, какследует провести вечер. Правила расположены в обычном порядке, антецедентрасполагается слева, а следствие — справа, все вызванные правила выполняются, аразбор ведется параллельно.<span Times New Roman",«serif»">1.Хороший фильм по ТВ + Рано утром встреч нет
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">Позднее кино<span Times New Roman",«serif»">2. Рано утром встреч нет + Нужнопоработать
<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:GreekMathSymbols">®<span Times New Roman",«serif»"> Работа допоздна<span Times New Roman",«serif»">3. Нужно поработать + Необходимыдокументы
<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:GreekMathSymbols">®<span Times New Roman",«serif»"> Работа в офисе<span Times New Roman",«serif»">4. Позднее кино
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">Не спать допоздна<span Times New Roman",«serif»">5. Работа допоздна
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">Не спать допоздна<span Times New Roman",«serif»">6. Работа допоздна
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">Возвращение в офис<span Times New Roman",«serif»">7. Работа в офисе
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: GreekMathSymbols">®<span Times New Roman",«serif»">Возвращение в офис<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Например, правило 1 гласит, что если поТВ идет хорошее кино и у меня завтра рано утром встреч нет, тогда я следуюрежиму “Позднее кино”.
<span Times New Roman",«serif»">Рассмотрим сперва пример прямого цепногоанализа. Допустим, система получила начальную информацию о том, что завтра раноуторм у меня нет встреч. Активируются правила 1 и 2. Допустим, что далее система получила сообщениео том, что мне нужно поработать. Активируется правило 3, а правило 2 вызываетсяи выполняетя, откуда следует вывод, что я нахожусь в режиме “Работа допоздна”,в результате чего вызываются и выполняются правила 5 и 6. В итоге система заключает, что я должнавернуться в офис и не спать допоздна.
<span Times New Roman",«serif»">Теперь рассмотрим эту же проблему сприменением обратного цепного анализа. Допустим, что система получила исходнуюинформацию о том, что у меня нет завтра утром встреч, но мне нужно ещепоработать, а затем ее (систему) спросили, следует ли мне вернуться в офис.Данный запрос активирует правила 6 и 7. В свою очередь возникнет вопрос “Работадопоздна” или “Работа в офисе”? При этомактивируются правила 2 и 3, и возникает вопрос “Рано утром встреч нет”, “Нужно поработать” или “Нужны документы”? Первые два антецедента будут удовлетворены,таким образом правило 2 будет вызвано и выполнено, что повлечет за собойудовлетворение антецедента “Работа допоздна”, вызов и выполнение правила 6, врезультате чего система придет к заключению, что мне следует вернуться в офис.
<span Times New Roman",«serif»">Обратите внимание на то, что при прямомразборе порождается больше следствий, а при обратном — запросов. Т.к. в обоихпримерах использовались одни и те же данные, то в ходе анализа выполнялись однии те же правила, но активировались различные.
<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Сравнение
<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Эффективность.
<span Times New Roman",«serif»">Выбор вида анализа (сверху вниз илиснизу вверх) зависит от конфигурации дерева, по которому осуществляется поиск.Если в среднем каждому элементу следуетбольшее количество элементов, нежели предшествует,то анализ сверху вниз (или обратный анализ) будет более эффективным и наоборот.Рассмотрим крайний случай. Допустим, что поисковая область образует дерево свершиной в начальном состоянии. Тогда при использовании прямого подхода нам придется осуществлять поиск практически по всему дереву, тогда как приобратном подходе — только в его линейной части.<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Сравнениеи унификация.
<span Times New Roman",«serif»">В системах с заложеннымиправилами или системах логического анализа выбор прямого или обратного цепногоанализа влияет на степень трудности процесса сравнения. При прямом цепном анализе системе постояннопредъявляются новые факты, не имеющие свободных переменных. Таким образомпостоянно проводится сравнение антецедентов, вполне вероятно обладающихсвободными переменными, с фактами, не обладающими таковыми.<span Times New Roman",«serif»">С другой стороны, системам с обратным цепным анализом честозадают специальные вопросы. Если правила изложены в логике предикатов, ане логике суждений, тогда производитсясравнение вопроса с переменной со следствием с переменными. Вторичные запросытакже могут содержать переменные, поэтому, в общем, системы с обратным цепныманализом должны быть разработаны таким образом, чтобы они могли сравнивать двесимвольные структуры, каждая из которых может содержать переменные, для чегопотребуется создание алгоритма унификации.
<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Смешанныестратегии
<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Поискв двух направлениях.
<span Times New Roman",«serif»">Если не ясно,какой вид поиска — прямой или обратный — является наиболее приемлимым дляконкретного приложения, следует осуществлять поиск в двух направлениях. В такомслучае, отправными точками становятсяначальное и конечное состояние, и поиск осуществляется по направлению к центру.<span Times New Roman",«serif»">Выводпо двум направлениям
<span Times New Roman",«serif»">. При данномподходе изначальные данные применяются для активирования правил, котоыеперебирают другие антецеденты в обратном порядке. Вторичные запросы, которые несоответствуют ни следствиям, ни данным, сохраняются в качестве “демонов”,которые могут быть удовлетворены позднее за счет новых или позднее поступившихданных. Систему можно разработать таким образом, что данные, удовлетворяющие“демонам” (антецеденты активированных правил) не будут активироватьдополнительные правила, что “заставит” систему при предстоящем прямом выводесконцентрироваться на правилах, учитывающих предыдущий контекст.<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Разборс началом в левом углу
<span Times New Roman",«serif»">. Примениввышеописанный метод к парсингу, мы получим так называемый разбор с началом влевом углу. В терминах примера, приведенного в разделе парсинг, система сначаларассмотрит “they”, найдет правило 9 — единственное правило, которое можноприменить к этому слову, затем правило 3, объясняющее PRO, а затем правило 1,как единственное правило, следствие которого начинается с NP. Далее системапопытается разобрать сверху вниз “areflying planes” как VP.<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Заключение
<span Times New Roman",«serif»">
<span Times New Roman",«serif»">Обычно в системах искусственногоинтеллекта применяется один из двух видов анализа. Первый — это анализ снизувверх или прямой анализ, а второй- сверху вниз или обратный. Различие ихопределяется тем, в каком направлении ведется поиск (от начала в конец илинаоборот) и какой элемент (следствие или антецедент) активирует правила.
<span Times New Roman",«serif»">Фактор эффективности и легкостивнедрения может сыграть решающую роль при выборе вида анализа, который будетприменяться в определенном приложении, но следует помнить, что использованиесмешанных стратегий также возможно.
<span Times New Roman",«serif»"><span Times New Roman",«serif»">ПРИЛОЖЕНИЕ