Часть 11.

<3> <цель, ><р, ><л, > <1,2,3,4,5> <4>

<4> <цель, ><р, ><и> <1,2,3,4,5> <5>

<5> <цель, ><и, > <1,2,3,4,5,6> <6>

<6> <цель, ><р, ><начало> <1,2,3,4,5,6> <останов>

<>

<Просмотренная ><часть ><пространства:>

<>

<Рис. ><5.9. ><Поиск ><от ><цели ><в ><продукционной ><системе>

<><208>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<>

<Рис. ><5.10. ><Двунаправленный ><расширенный ><поиск>

<>

<Рис. ><5.11. ><Двунаправленный ><поиск, ><отсекающий ><большую ><часть ><пространства, ><исследуе><мую ><при ><однонаправленном ><поиске>

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>

<209>

><<Управление ><поиском ><с ><помощью ><структуры ><правил>

<Структура ><правил ><в ><продукционной ><системе, ><включая ><различия ><между ><условием ><и ><действием, ><а ><также ><порядок ><проверки ><условий, ><определяет ><метод ><исследования ><про><странства. ><Описывая ><исчисление ><предикатов ><как ><язык ><представления, ><мы ><подчеркива><ли ><декларативный ><характер ><его ><семантики. ><Таким ><образом, ><выражения ><исчисления ><предикатов ><всего ><лишь ><определяют ><истинные ><отношения ><в ><области ><формулировки ><за><дачи ><и ><не ><делают ><никаких ><утверждений ><относительно ><порядка ><интерпретации ><их ><ком><понентов. ><Следовательно, ><некоторое ><частное ><правило ><может ><иметь ><вид ><"X ><(foo(X) ><^>< ><(Х) >®< ><тоо(Х)). ><Согласно ><правилам ><исчисления ><предикатов ><альтернативная ><форма ><того ><же ><правила ><может ><быть ><такой ><(foo(X) >®< ><тоо(Х) ><Эквивалент><ность ><этих ><двух ><выражений ><может ><быть ><продемонстрирована ><с ><помощью ><таблицы ><истинности ><(раздел ><2.1).>

<Хотя ><эти ><формулировки ><логически ><эквивалентны, ><они ><не ><ведут ><к ><одинаковым ><резуль><татам, ><если ><интерпретируются ><как ><продукции ><(продукционные ><правила), ><потому ><что ><реа><лизация ><продукционной ><системы ><обеспечивает ><определенный ><порядок ><проверки ><соот><ветствия ><и ><активизации ><правил. ><По ><этой ><причине ><форма ><представления ><правил ><определя><ется ><удобством ><(или ><возможностями) ><проверки ><соответствия ><правилам ><в ><конкретной ><задаче. ><Это ><является ><результатом ><выбора ><способа ><интерпретации ><правил ><продукционной ><системой. ><Продукционная ><система ><налагает ><на ><декларативный ><язык ><описания ><правил ><процедурную ><семантику.>

<Поскольку ><продукционная ><система ><проверяет ><правила ><в ><определенном ><порядке, ><про><граммист ><может ><управлять ><поиском ><через ><структуру ><и ><порядок ><следования ><правил ><в ><про><дукционном ><наборе.>

<Несмотря ><на ><то ><что ><выражения ><"X(foo(X) ><®® ><тоо(Х)) ><и ><"X ><(foo(X) ><®® ><тоо(Х) ><- ><логически ><эквивалентны, ><при ><реализации ><поиска ><они ><обрабатыва><ются ><не ><одинаково.>

<Квалифицированные ><специалисты ><кодируют ><наиболее ><значащие ><(ключевые) ><эв><ристики, ><руководствуясь ><своими ><профессиональными ><знаниями. ><В ><очередности ><предпосылок ><содержится ><важная ><процедурная ><информация, ><необходимая ><для ><ус><пешного ><решения ><проблемы. ><Очень ><важно, ><чтобы ><эта ><формулировка ><(форма ><выра><жения) ><сохранялась ><при ><написании ><программы. ><Например, ><когда ><механик ><говорит: ><"Если ><двигатель ><не ><вращается, ><и ><фары ><не ><горят, ><проверьте ><аккумулятор", ><водителю ><предлагается ><определенная ><последовательность ><действий. ><В ><логически ><эквивалент><ном ><предложении ><"Двигатель ><вращается ><или ><фары ><горят, ><или ><проверьте ><аккумуля><тор" ><эта ><информация ><теряется. ><Такая ><формулировка ><правил ><не ><выдерживает ><крити><ки, ><так ><как ><при ><управлении ><поиском ><необходимо, ><чтобы ><система ><вела ><себя ><логично, ><а ><последовательность ><активизации ><правил ><была ><понятной.>

<Управление ><поиском ><через ><разрешение ><конфликтов>

<Продукционные ><системы ><(как ><и ><все ><системы, ><основанные ><на ><знаниях) ><позволяют ><представлять ><эвристики ><непосредственно ><в ><правилах, ><описывающих ><знания. ><Кроме ><того, ><они ><предлагают ><другой ><метод ><эвристического ><управления ><- ><через ><разрешение ><конфликтов. ><Простейшая ><подобная ><стратегия ><сводится ><к ><тому, ><чтобы ><выбирать ><пер><вое ><соответствующее ><правило ><из ><рабочей ><памяти. ><Однако ><для ><разрешения ><конфлик><тов ><(conflict ><потенциально ><может ><быть ><применена ><любая ><стратегия. ><На><пример, ><в ><поддерживаются ><следующие ><стратегии ><разрешения ><конфликтов ><[Brownston ><и ><др., ><1985].>

<><210>< ><Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<Рефракция ><(><Рефракция ><означает, ><что ><после ><активизации ><правила ><оно ><не

><может ><быть ><запущено ><снова, ><пока ><не ><изменятся ><элементы ><рабочей ><памяти, ><соответ><ствующие ><его ><условиям. ><Рефракция ><препятствует ><зацикливанию.>

<Новизна ><(><Стратегия ><новизны ><отдает ><предпочтение ><правилам, ><условия ><ко><торых ><соответствуют ><образцам, ><добавленным ><в ><рабочую ><память ><последними. ><Это ><позволяет ><сосредоточить ><поиск ><на ><одной ><линии ><рассуждения.>

<Специфичность ><(><Согласно ><этой ><стратегии ><целесообразнее ><использовать

><более ><конкретное, ><а ><не ><более ><общее ><правило. ><Одно ><правило ><более ><специфично

><(конкретно) ><чем ><другое, ><если ><оно ><содержит ><больше ><условий, ><а ><значит, ><соответству><ет ><меньшему ><количеству ><образцов ><в ><рабочей ><памяти.>

<5.3.4. ><Преимущества ><продукционных ><систем ><для ><ИИ>

<Как ><видно ><из ><предыдущих ><примеров, ><продукционная ><система ><обеспечивает ><общую ><струк><туру ><осуществления ><поиска. ><Благодаря ><ее ><простоте, ><модифицируемости ><и ><гибкости ><в ><приме><нении ><знаний ><для ><решения ><задач ><продукционная ><система, ><как ><оказалось, ><может ><быть ><важным ><механизмом ><для ><конструирования ><экспертных ><систем ><и ><других ><приложений ><ИИ. ><Главные ><преимущества ><продукционных ><систем ><искусственного ><интеллекта ><описаны ><ниже.>

<Разделение ><знания ><и ><управления. ><Продукционная ><система ><- ><изящная ><модель ><раз><деления ><знания ><и ><управления ><в ><компьютерной ><программе. ><Управление ><обеспечивается ><циклом ><"распознание-действие" ><продукционной ><системы. ><При ><этом ><знания ><о ><методах ><решения ><задач ><сосредоточены ><непосредственно ><в ><правилах. ><Преимущество ><такого ><разде><ления ><заключается ><в ><простоте ><изменения ><базы ><знаний, ><при ><котором ><не ><требуется ><изме><нять ><код ><программы ><управления. ><И, ><наоборот, ><это ><позволяет ><изменять ><код ><управляющей ><части ><программы, ><не ><трогая ><набор ><правил ><вывода.>

<Естественное ><соответствие ><поиску ><в ><пространстве ><состояний. ><Компоненты ><продукци><онной ><системы ><естественно ><отображаются ><в ><логическую ><структуру ><поиска ><в ><пространстве ><со><стояний. ><Последовательные ><состояния ><рабочей ><памяти ><составляют ><вершины ><графа ><простран><ства ><состояний. ><Правила ><вывода ><- ><набор ><возможных ><переходов ><между ><состояниями. ><Разре><шение ><конфликтов ><обеспечивает ><выбор ><перехода ><(ветви) ><в ><пространстве ><состояний. ><Эти ><правила ><упрощают ><выполнение, ><отладку ><и ><документирование ><алгоритмов ><поиска.>

<Модульность ><продукционных ><правил. ><Важный ><аспект ><в ><моделировании ><продукци><онных ><систем ><- ><это ><отсутствие ><синтаксического ><взаимодействия ><между ><продукционны><ми ><правилами. ><Правила ><могут ><только ><влиять ><на ><активизацию ><других ><правил, ><изменяя ><об><разец ><в ><рабочей ><памяти. ><Правила ><не ><могут ><"вызывать" ><другие ><правила ><непосредственно, ><как ><подпрограммы. ><При ><этом ><они ><не ><могут ><устанавливать ><значения ><переменных ><в ><других ><продукционных ><правилах. ><Область ><действия ><переменных ><этих ><правил ><ограничена ><от><дельным ><правилом. ><Эта ><синтаксическая ><независимость ><способствует ><инкрементальной ><разработке ><экспертных ><систем ><путем ><последовательного ><добавления, ><удаления ><или ><изме><нения ><знаний ><(правил) ><системы.>

<Управление ><на ><основе ><образцов ><(pattern-directed ><Задачи, ><решаемые ><с ><по><мощью ><программ ><ИИ, ><требуют ><особой ><гибкости ><при ><выполнении ><программы. ><Это ><вызва><но ><еще ><и ><тем ><фактом, ><что ><правила ><в ><продукционной ><системе ><могут ><запускаться ><в ><любой ><последовательности. ><Описание ><задачи, ><представляющее ><текущее ><состояние ><мира, ><опре><деляет ><конфликтное ><множество ><и, ><следовательно, ><конкретный ><путь ><поиска ><и ><решения.>

<Возможности ><эвристического ><управления ><поиском. ><Несколько ><методов ><эвристи><ческого ><управления ><были ><описаны ><в ><предыдущем ><разделе.>

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><211>

><<Трассировка ><и ><трактовка. ><Модульность ><правил ><и ><итерационный ><характер ><их ><вы><полнения ><облегчают ><контроль ><за ><работой ><продукционной ><системы. ><На ><каждой ><стадии ><цикла ><"распознание-действие" ><рассматривается ><некоторое ><правило. ><Поскольку ><каждое ><правило ><соответствует ><отдельной ><"порции" ><(chunk) ><знаний ><о ><методах ><решения ><задач, ><со><держание ><правила ><должно ><давать ><ясную ><интерпретацию ><текущего ><состояния ><системы ><и ><действия. ><Более ><того, ><цепочка ><правил, ><используемых ><в ><процессе ><решения, ><отражает ><как ><путь ><на ><графе, ><так ><и ><"цепочку ><рассуждений", ><приводящую ><к ><решению ><задачи ><человека-><эксперта. ><В ><главе ><7 ><это ><будет ><описано ><детально. ><Напротив, ><единая ><линия ><управления ><или ><процедура, ><написанная ><на ><традиционном ><языке ><программирования, ><например, ><или ><фактически ><бессмысленна.>

<Независимость ><от ><выбора ><языка. ><Модель ><управления ><продукционной ><системой ><не ><зависит ><от ><представления ><правил ><и ><рабочей ><памяти, ><если ><это ><представление ><поддержива><ет ><сравнение ><с ><образцами. ><Мы ><описали ><продукционные ><правила ><как ><импликации ><исчис><ления ><предикатов ><вида ><А ><В, ><где ><истинность ><А ><и ><правило ><вывода ><модус ><поненс ><позво><ляют ><сделать ><заключение ><В. ><Существует ><немало ><преимуществ ><применения ><логического ><представления ><знаний ><и ><обоснования ><правил ><вывода, ><однако ><модель ><продукционной ><сис><темы ><может ><работать ><и ><с ><другими ><представлениями.>

<Исчисление ><предикатов ><обеспечивает ><преимущество ><логически ><обоснованного ><выво><да, ><однако ><немало ><задач ><требует ><рассуждений, ><которые ><не ><обоснованы ><в ><логическом ><смысле. ><Для ><них ><необходимы ><вероятностные ><рассуждения, ><правила ><умолчания ><и ><недос><товерные ><свидетельства. ><В ><главах ><6, ><7 ><и ><8 ><мы ><обсудим ><альтернативные ><правила ><вывода, ><предоставляющие ><такие ><возможности. ><Независимо ><от ><типа ><используемых ><правил ><вывода, ><продукционная ><система ><обеспечивает ><средства ><поиска ><в ><пространстве ><состояний.>

<Правдоподобная ><модель ><решения ><задачи ><человеком. ><Среди ><первых ><моделей, ><исполь><зующих ><продукционные ><системы, ><были ><модели ><нахождения ><решения ><задач ><человеком ><[Newell ><и ><1972]. ><Эти ><системы, ><главным ><образом, ><использовались ><в ><качестве ><модели ><че><ловеческой ><деятельности ><в ><различных ><областях ><научных ><исследований ><(глава ><16).>

<Поиск ><на ><основе ><образцов ><(pattern-directed ><позволяет ><исследовать ><пространст><во ><логического ><вывода ><в ><исчислении ><предикатов. ><На ><этой ><методике ><основано ><немало ><за><дач. ><В ><них ><исчисление ><предикатов ><используется ><для ><моделирования ><таких ><специфиче><ских ><аспектов ><мира, ><как ><время ><и ><изменения. ><В ><следующем ><разделе ><представлена ><методо><логия ><"классной ><доски" ><как ><разновидность ><продукционной ><системы. ><В ><методологии ><"классной ><доски" ><группы ><однотипных ><продукционных ><правил ><объединены ><в ><источники ><знаний, ><которые ><участвуют ><в ><решении ><задачи ><путем ><общения ><через ><глобальную ><рабочую ><память ><"классной ><доски".>

<5.4. ><Архитектура ><"классной ><доски">

<><Методология ><"классной ><доски" ><(blackboard) ><- ><заключительный ><механизм ><(алгоритм) ><управления, ><представленный ><в ><этой ><главе. ><Если ><необходимо ><исследовать ><состояния ><в ><про><странстве ><логического ><вывода ><некоторым ><детерминированным ><способом, ><применение ><про><дукционных ><систем ><обеспечивает ><значительную ><гибкость, ><позволяя ><одновременно ><предста><вить ><в ><рабочей ><памяти ><множество ><частных ><решений ><и ><выбрать ><следующее ><состояние ><путем ><разрешения ><конфликтов. ><Методология ><"классной ><доски" ><расширяет ><возможности ><продук><ционных ><систем, ><позволяя ><организовать ><рабочую ><память ><в ><виде ><отдельных ><модулей, ><каж><дый ><из ><которых ><соответствует ><подмножеству ><продукционных ><правил. ><"Классная ><доска" ><ин->

<><212>< ><Часть ><И. ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<><тегрирует ><отдельные ><наборы ><продукционных ><правил ><и ><координирует ><действия ><многочис><ленных ><решателей ><задач ><в ><пределах ><единой ><глобальной ><структуры.>

<Решение ><многих ><задач ><требует ><координации ><ряда ><различных ><типов ><знания. ><На><пример, ><программа ><понимания ><(распознавания) ><речи ><должна ><сначала ><обработать ><фрагменты ><речи, ><представленные ><в ><виде ><оцифрованной ><волны. ><Далее ><в ><процессе ><распознавания ><необходимо ><выделить ><в ><этом ><речевом ><фрагменте ><отдельные ><слова, ><сформировать ><их ><в ><предложения ><и, ><наконец, ><синтезировать ><семантическое ><представ><ление ><полученного ><значения.>

<При ><взаимодействии ><множества ><процессов ><в ><ходе ><решения ><одной ><большой ><задачи ><может ><возникнуть ><немало ><сопутствующих ><проблем. ><Примером ><этого ><служит ><задача ><слияния ><(объединения) ><показаний ><датчиков ><[Lesser ><и ><1983]. ><Предположим, ><имеется ><сеть ><датчиков, ><соответствующих ><различным ><процессам. ><Предположим ><так><же, ><что ><процессы ><могут ><сообщаться. ><Поэтому ><соответствующая ><интерпретация ><дан><ных ><каждого ><отдельного ><датчика ><зависит ><от ><данных, ><полученных ><другими ><датчика><ми ><этой ><единой ><сети. ><Эта ><проблема ><возникает ><и ><в ><задаче ><управления ><траекторией ><движения ><самолета, ><находящегося ><в ><поле ><обзора ><многочисленных ><радарных ><устано><вок ><с ><последующим ><объединением ><показаний ><всех ><датчиков ><в ><процессе ><обработки ><информации.>

<Архитектура ><"классной ><доски" ><(стратегия ><решения ><сложных ><системных ><задач ><с ><при><влечением ><разнородных ><источников ><знаний, ><взаимодействующих ><через ><общее ><информа><ционное ><поле) ><- ><модель ><управления, ><которая ><успешно ><применяется ><для ><решения ><этой ><и ><других ><задач, ><требующих ><координации ><различных ><процессов ><или ><источников ><знания. ><"Классная ><доска" ><- ><центральная ><глобальная ><база ><данных, ><предназначенная ><для ><связи ><не><зависимых ><асинхронных ><источников ><знаний. ><На ><рис. ><5.12 ><дано ><схематичное ><представле><ние ><архитектуры ><"классной ><доски".>

<На ><рис. ><5.12 ><каждый ><источник ><знаний ><(knowledge ><получает ><свои ><данные ><от ><"классной ><доски", ><обрабатывает ><их ><и ><возвращает ><результаты ><"классной ><доске" ><для ><их ><дальнейшего ><использования ><другими ><источниками ><знаний. ><Это ><изолированные ><процес><сы, ><действующие ><согласно ><своим ><собственным ><спецификациям ><(описанию). ><Поэтому ><при ><параллельной ><обработке ><информации ><или ><мультипроцессорной ><системы ><эти ><системы ><участвуют ><в ><решении ><единой ><задачи ><независимо ><друг ><от ><друга. ><Это ><асинхронная ><система, ><поскольку ><каждый ><источник ><знаний ><начинает ><свою ><работу, ><когда ><находит ><соответст><вующие ><входные ><данные ><на ><"классной ><доске". ><Закончив ><обработку ><данных, ><он ><возвраща><ет ><свои ><результаты ><и ><ожидает ><новых ><входных ><данных.>

<Подход ><"классной ><доски" ><к ><организации ><большой ><программы ><изначально ><был ><реализован ><в ><системе ><[Erman ><и ><др., ><1980], ><[Reddy, ><1976]. ><- ><это ><программа ><понимания ><речи. ><Первоначально ><она ><была ><разработана ><как ><внешний ><интерфейс ><для ><базы ><данных ><публикаций ><по ><теории ><вычислительных ><систем. ><Пред><полагалось, ><что ><абонент ><библиотеки ><может ><обратиться ><к ><компьютеру ><на ><английском ><языке ><с ><запросом ><типа: ><"Есть ><ли ><у ><вас ><какие-нибудь ><работы ><авторов ><Фейгенбаума ><(Feigenbaum) ><и ><Фельдмана ><(Feldman)?". ><Компьютер ><должен ><ответить ><на ><этот ><вопрос, ><предоставив ><информацию ><из ><базы ><данных ><библиотеки. ><Понимание ><речи ><требует ><ин><теграции ><ряда ><различных ><процессов, ><которым ><необходимы ><различные ><знания ><и ><ал><горитмы. ><Сложность ><этих ><алгоритмов ><и ><знаний ><может ><расти ><экспоненциально. ><Об><работка ><сигналов, ><распознавание ><фонем, ><слогов ><и ><слов, ><синтаксический ><анализ ><и ><се><мантический ><анализ ><- ><все ><эти ><процессы ><связаны ><друг ><с ><другом ><в ><процессе ><интерпретации ><речи.>

<><Глава ><5. ><Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>< ><213>

><<>

<Рис. ><5.12. ><Архитектура ><"классной ><доски ><">

<Архитектура ><"классной ><доски" ><позволила ><скоординировать ><в ><системе ><несколько ><различных ><источников ><знания, ><необходимых ><для ><этой ><сложной ><задачи. ><"Классная ><доска" ><обычно ><организована ><в ><двух ><измерениях. ><В ><этими ><изме><рениями ><были ><время, ><в ><течение ><которого ><звучала ><речь, ><и ><уровень ><анализа ><фрагмента ><ак><тивной ><речи. ><Каждый ><уровень ><анализа ><реализовывался ><различными ><классами ><источников ><знания. ><Эти ><уровни ><анализа ><таковы.>

< ><Форма ><волны ><(временная ><диаграмма) ><акустического ><сигнала.>

< ><Фонемы ><или ><возможные ><звуковые ><сегменты ><акустического ><сигнала.>

< ><Слоги, ><которые ><могут ><быть ><составлены ><из ><фонем.>

< ><Возможные ><слова, ><результат ><анализа ><первого ><.>

< ><Возможные ><слова, ><результат ><анализа ><второго ><(обычно ><рассматриваются>

<слова ><из ><различных ><частей ><данных).>

< ><Генерация ><возможных ><последовательностей ><слов.>

< ><Связывание ><последовательности ><слов ><в ><фразы.>

<Эти ><процессы ><можно ><визуализировать ><в ><виде ><компонентов ><(см. ><рис. ><5.12). ><При ><обра><ботке ><устной ><речи ><форма ><волны ><произнесенного ><сигнала ><рассматривается ><на ><самом ><ниж><нем ><уровне. ><Обработку ><этих ><данных ><выполняют ><определенные ><источники ><знаний. ><Ре><зультаты ><их ><анализа ><переносятся ><на ><доску ><и ><используются ><другими ><процессами. ><Из-за ><неоднозначности ><разговорного ><языка ><на ><каждом ><уровне ><доски ><могут ><присутствовать ><многочисленные ><конкурирующие ><гипотезы. ><Источники ><знаний ><более ><высоких ><уровней ><пытаются ><устранить ><неоднозначности ><конкурирующих ><гипотез.>

<Процесс ><анализа ><в ><не ><следует ><рассматривать ><просто ><как ><последователь><ность ><этапов ><анализа ><на ><низком ><уровне ><и ><создания ><данных, ><которые ><затем ><могут ><быть ><проанализированы ><на ><более ><высоком ><уровне. ><Система ><значительно ><слож><нее. ><Если ><на ><одном ><уровне ><не ><может ><обработать ><(осмыслить) ><переданные ><ему ><данные, ><то ><он ><делает ><запрос ><к ><соответствующему ><источнику ><о ><новых ><данных. ><Затем, ><получив ><но><вые ><данные, ><делает ><еще ><одну ><попытку ><их ><обработки ><или ><принимает ><другую ><гипотезу ><от><носительно ><первоначально ><полученных ><данных. ><Кроме ><того, ><различные ><могут ><одно><временно ><работать ><над ><разными ><фрагментами ><речи. ><Все ><процессы, ><как ><было ><уже ><сказано, ><являются ><асинхронными ><и ><управляемыми ><на ><основе ><данных. ><Они ><запускаются ><с ><появле><нием ><входных ><данных ><и ><продолжают ><работу, ><пока ><не ><закончат ><задание, ><затем ><возвраща><ют ><свои ><результаты ><и ><ждут ><следующего ><задания.>

<Один ><из >< ><называемый ><планировщиком, ><обрабатывает ><сообщения ><о ><результатах ><обработки ><информации, ><передаваемые ><между ><другими ><Планировщик ><ранжирует ><ре->