УПРАЖНЕНИЯ

10.1. Запишите высказывание, позволяющее определить результаты действия Shoot в мире вампуса. Опишите эти результаты применительно к вампусу, но не забудьте, что после выстрела у агента больше нет стрелы.
10.2. С помощью ситуационного исчисления запишите аксиому, чтобы связать время 0 с ситуацией 50, и еще одну аксиому, чтобы связать время t с любой ситуацией, которая развилась из S0 в результате последовательности из t действий.
10.3. В данном упражнении рассматривается проблема планирования маршрута для робота, чтобы он мог добраться из одного города в другой. Основным действием, предпринимаемым роботом, является действие Go (х, у), которое позволяет ему добраться из города х в город у, если между этими городами есть прямой путь. Предикат DirectRoute{x,у) принимает истинное значение тогда и только тогда, когда есть прямой путь из х в у, вы можете принять предположение, что все соответствующие факты уже находятся в базе знаний (см. карту на с. 114). Робот начинает движение с Арада и должен достичь Бухареста.
а) Запишите подходящее логическое описание начальной ситуации для робота.
б) Запишите подходящий логический запрос, решения которого могут слу-
жить описаниями возможных путей к цели.
в) Запишите высказывание, описывающее действие Go.
г) Теперь предположим, что, следуя по прямому пути между двумя города-
ми, агент тратит топливо, количество которого равно расстоянию между
этими городами. Робот начинает движение с полной загрузкой топлива.
Дополните разработанное вами представление с учетом этих соображе-
ний. Предложенное вами описание действий должно быть таковым, что-
бы сформулированный вами ранее запрос все еще приводил к получению
осуществимых планов.
д) Опишите начальную ситуацию и запишите новое правило (или правила),
определяющее действие Go.
е) Теперь допустим, что в некоторых узлах маршрута имеются также бензо-
заправочные станции, в которых робот может пополнить свой топливный
бак. Дополните разработанное вами представление и запишите все пра-
вила, необходимые для описания бензозаправочных станций, включая
действие Fillup (Заправка).
10.4. Исследуйте способы дополнения исчисления событий, позволяющие учитывать в нем одновременные события. Возможно ли избежать комбинаторного взрыва количества аксиом?
10.5. Представьте приведенные ниже семь высказываний, используя и дополняя средства представления, описанные в этой главе.
а) Вода находится в жидком состоянии при температуре от 0 до 100 градусов
Цельсия.
б) Вода кипит при температуре 100 градусов Цельсия.
в) Вода в бутылке для воды, принадлежащей Джону, замерзла.
г) Минеральная вода "Перрье" — это тоже вода.
д) Джон держит в своей бутылке для воды минеральную воду "Перрье".
е) Все жидкости имеют определенную температуру замерзания.
ж) Литр воды весит больше, чем литр алкоголя.
Теперь повторите это упражнение с использованием представления, основанного на мереологическом подходе, в котором, например, Water — это объект, содержащий в качестве частей всю воду в мире.
10.6. Запишите определения для следующих предикатов:
а) ExhaustivePartDecomposition
б) PartPartition
в) PartwiseDis joint
Эти определения должны быть аналогичными определениям для предикатов ExhaustiveDecomposition, Partition и Disjoint. Является ли, по вашему мнению, общезначимым выражение PartParti tion (s, BunchOf (s) ) ? Если да, докажите его общезначимость; в противном случае приведите контрпример и определите достаточные условия, при которых это выражение становится истинным.
10.7. Запишите множество высказываний, которое позволяет рассчитать цену отдельного помидора (или другого объекта), если указана цена за килограмм. Дополните эту теорию, чтобы иметь возможность рассчитать цену пакета помидоров.
10.8. Одна из альтернативных схем представления мер предусматривает применение функции единиц к абстрактному объекту длины. В такой схеме следует писать Inches (Length (Li) ) =1. 5. Как выгладит эта схема по сравнению с той, что описана в данной главе? Заслуживают внимания такие вопросы, как аксиомы преобразования, имена для абстрактных количеств (такие как "50 долларов") и сравнения абстрактных мер в различных единицах (например, "50 дюймов больше 50 сантиметров").
10.9. Разработайте средство представления для курсов обмена валют, которое допускает ежесуточные колебания курсов.
10.10. Это упражнение касается связей между категориями событий и интервалами времени, в которые они происходят.
а) Определите предикат Т( с, i) в терминах отношений During и е.
б) Дайте точное объяснение причин, по которым не требуются две различ-
ные системы обозначений для описания конъюнктивных категорий со-
бытий.
в) Дайте формальное определение для предикатов T{OneOf{p,q) , i) и
T(Either(p,q) , i).
г) Объясните, почему целесообразно иметь две формы отрицания событий,
аналогичные двум формам дизъюнкции событий. Назовите их Not
и Never и дайте им формальные определения.
10.11. Определите предикат Fixed, где Fixed(Location(x) ) означает, что местонахождение объекта х постоянно во времени.
10.12. Определите предикаты Before, After, During и Overlap с использованием предиката Meet и функции Start и End, но не функции Time или предиката <.
10.13. В разделе 10.5 предикаты Link и LinkText использовались для описания связей между Web-страницами. Запишите определения для Link и LinkText, используя, кроме всего прочего, предикаты InTag и Get Раде.
10.14. Одна из составляющих процесса совершения покупок, которая не рассматривалась в этой главе, касается проверки совместимости товаров. Например, если клиент заказывает компьютер, будет ли этот компьютер совместимым с имеющимися у него периферийными устройствами? Если же оформляется заказ на цифровую камеру, то будут ли к ней прилагаться подходящие плата памяти и аккумулятор? Разработайте базу знаний, позволяющую принимать решение о том, является ли множество товаров совместимым, которая может использоваться для предоставления консультаций, касающихся замены или приобретения дополнительных товаров, если имеющиеся товары являются несовместимыми. Убедитесь в том, что эта база знаний может применяться по меньшей мере с одной номенклатурой товаров и что ее несложно дополнить для использования с другими номенклатурами.
10.15. Введите правила, позволяющие расширить определение предиката Name(s,c) так, чтобы строка, подобная "laptop computer", согласовывалась с соответствующей категорией имен, применяемых в самых различных магазинах. Попытайтесь добиться того, чтобы предложенное вами определение стало наиболее общим. Проверьте его, изучив десять оперативных магазинов и ознакомившись с тем, какие имена в них присвоены трем различным категориям. Например, применительно к категории портативных компьютеров авторы обнаружили имена "Notebooks", "Laptops", "Notebook Computers", "Notebook", "Laptops and Notebooks" и "Notebook PCs". Некоторые из них могут быть описаны с помощью явно заданных фактов Name, а для других могут применяться правила образования множественного числа, оформления перечислений и т.д.
10.16. Полное решение проблемы неточных соответствий описаниям, сформулиро-
ванным покупателем при совершении покупок, является очень сложным и
требует применения полного спектра средств обработки естественного языка
и методов выборки информации (см. главы 22 и 23). Одним из небольших
шагов в этом направлении является предоставление пользователю возможно-
сти задавать минимальные и максимальные значения для различных атрибу-
тов. Допустим, что мы требуем от покупателя, чтобы он использовал следую-
щую грамматику для формулировки описаний товаров:
Description _> Category [Connector Modifier]*
Connector _> "with" | "and" | ","| "с" | "u"
Modifier —> Attribute \ Attribute Op Value
Op -> "=" I ">" I "<"
Здесь Category обозначает категорию товара, Attribute — это некоторая характеристика, такая как "частота процессора" или "цена", a Value — желаемое значение этой характеристики. Поэтому запрос "компьютер с частотой процессора по меньшей мере 2,5 ГГц по цене меньше $1000" должен быть выражен так: "компьютер с частотой процессора > 2,5 ГГц и ценой < $1000". Реализуйте торгового агента, который принимает описания на этом языке.
10.17. В нашем описании процесса осуществления покупок в Internet упущен наиболее важный этап — фактическая покупка товара. Предоставьте формальное логическое описание этапа покупки с использованием исчисления событий. Иначе говоря, определите последовательность событий, которая происходит, когда покупатель приобретает товар по кредитной карточке, а затем в конечном итоге получает выставленный ему счет и ему вручается товар.
10.18. Опишите событие, в котором один объект обменивается на какой-то другой. Опишите процесс покупки как разновидность обмена, в которой одним из объектов, участвующих в обмене, является некоторая денежная сумма.
10.19. Ш В двух предыдущих упражнениях подразумевается использование довольно примитивного понятия владения. Например, покупатель приступает к приобретению товара, овладев денежными купюрами. Такое описание процесса покупки становится неадекватным, если, например, деньги покупателя хранятся в банке, поскольку у него на руках больше нет какой-то конкретной совокупности денежных купюр, которыми он может немедленно распорядиться. Ситуация становится еще более сложной, если учесть возможность займа, сдачи в аренду, взятия в аренду и передачи в залог. Исследуйте различные обыденные и юридические понятия владения и предложите схему, с помощью которой их можно представить формально.
10.20. Вы должны разработать систему предоставления консультаций студентам отделения компьютерных наук в части того, какие курсы они должны пройти в течение некоторого продолжительного периода, чтобы выполнить условия учебной программы (исходите из тех требований, которые предъявляются в вашем учебном заведении). Прежде всего подготовьте словарь, позволяющий представить всю информацию, а затем представьте эту информацию; после этого примените подходящий запрос к системе, которая должна возвратить в качестве решения приемлемую программу обучения. Вы должны предусмотреть в определенной степени необходимость учитывать подготовку отдельных студентов в том смысле, что система должна спрашивать, какие основные или эквивалентные курсы уже прошел студент, и не формировать программы, в которых повторяются эти курсы.
Предложите способы усовершенствования этой системы, например, для того, чтобы в ней учитывались сведения о предпочтениях студента, рабочей нагрузке, о том, какие преподаватели ему нравятся или не нравятся, и т.д. Рассматривая каждую разновидность знаний, объясните, как она может быть представлена логически. Способна ли ваша система легко учитывать эту информацию и находить наилучшую программу обучения для студента?
10.21. На рис. 10.1 показаны верхние уровни иерархии для всех понятий. Дополните
ее, чтобы включить максимально возможное количество реальных категорий.
Удобным способом выполнения этого требования является описание всего,
с чем приходится сталкиваться в повседневной жизни. К этому относятся объ-
екты и события. Начните с утреннего пробуждения и последовательно учиты-
вайте все, что вы видите, чего касаетесь, что делаете и о чем думаете. Напри-
мер, случайно выбранный день может свестись к цепочке: музыка, новости,
молоко, ходьба, поездка, заправка топливом, вестибюль университета, ковер,
разговор, профессор Фейтмен, цыпленок под острым соусом, обожженный
язык, 7 долларов, солнце, дневная газета и т.д.
Вы должны подготовить единственную схему иерархии (на большом листе бумаги), а также список объектов и категорий с отношениями, которым соответствуют элементы каждой категории. Каждый объект должен находиться в некоторой категории, а каждая категория должна относиться к этой иерархии.
10.22. (Адаптировано на основании примера Дуга Лената (Doug Lenat).) Ваша задача состо-
ит в том, чтобы представить в логической форме достаточный объем знаний, по-
зволяющий ответить на ряд вопросов о следующем простом высказывании:
Вчера Джон отправился в супермаркет North Berkeley Safeway и купил два фунта помидоров и фунт говяжьего фарша.
Начните с попытки представить содержимое этого высказывания в виде ряда утверждений. Вы должны записать высказывания, которые имеют простую логическую структуру (например, утверждения, согласно которым объекты имеют определенные свойства, связаны определенными отношениями, и все объекты, удовлетворяющие некоторому свойству, удовлетворяют также какому-то другому свойству). Для начала может помочь получение ответов на приведенные ниже вопросы.
• Какие классы, объекты и отношения вам потребуются? Есть ли у них родительские объекты, сестринские объекты и т.д.? (Кроме всего прочего, вам может потребоваться учитывать упорядочение событий и временное упорядочение.)
• В каком месте эти объекты должны войти в более общую иерархию?
• Каковы ограничения и взаимосвязи между ними?
• Насколько подробно следует определять каждое из различных понятий?
Созданная вами база знаний должна предоставлять возможность найти ответ на список вопросов, который будет вскоре приведен. Некоторые вопросы касаются материала, явно сформулированного в этом кратком рассказе, но для большинства из них требуется, чтобы тот, кто на них отвечает, обладал другими фоновыми знаниями — умел читать между строк. Вам придется вспомнить о том, какого рода товары бывают в супермаркете, что связано с покупкой выбранных товаров, для чего могут использоваться покупки, и т.д. Попытайтесь сделать применяемое вами представление настолько общим, насколько это возможно. Приведем тривиальный пример: не следует вводить в базу знаний высказывание: "Люди покупают продукты в супермаркете Safeway", поскольку это не позволяет учесть существование тех, кто покупает продукты в другом супермаркете. Нет смысла вводить информацию о том, что "Джо готовит спагетти с помидорами и говяжьим фаршем", поскольку она вообще не позволит сделать какие-либо полезные выводы. Кроме того, не превращайте вопросы в ответы; например, в вопросе 10.22, в сказано: "Купил ли Джон какие-либо мясные продукты?", а не "Купил ли Джон фунт говяжьего фарша?"
Наметьте цепочки рассуждений, которые позволили бы ответить на эти вопросы. В процессе этого вам несомненно потребуется создать дополнительные понятия, ввести дополнительные утверждения и т.д. Если это возможно, воспользуйтесь какой-то системой формирования логических рассуждений, чтобы продемонстрировать достаточность вашей базы знаний. Многие из составленных вами высказываний в реальности могут оказаться лишь приближенно правильными, но не следует об этом слишком беспокоиться; идея состоит в том, чтобы извлечь обыденные знания (на уровне здравого смысла), которые, в принципе, позволяют вам ответить на эти вопросы. Задача составления действительно полного ответа на многие из этих вопросов является чрезвычайно трудной и, по-видимому, выходит за рамки современных средств представления знаний. Но вы должны быть способны составить непротиворечивое множество аксиом для получения ответов на поставленный здесь ограниченный круг вопросов.
а) Джон — ребенок или взрослый? [Взрослый]
б) У Джона теперь имеется не меньше двух помидоров? [Да]
в) Купил ли Джон какие-либо мясные продукты? [Да]
г) Если бы Мэри покупала помидоры в то же время, что и Джон, увидел бы
он ее? [Да]
д) Сделаны ли помидоры в супермаркете? [Нет]
е) Что Джон собирается сделать с помидорами? [Съесть их]
ж) В супермаркете Safeway продаются дезодоранты? [Да]
з) Джон принес какие-то деньги в супермаркет? [Да]
и) Стал ли Джон иметь меньше денег после поездки в супермаркет? [Да]
10.23. Внесите необходимые дополнения или изменения в вашу базу знаний, разработанную в предыдущем упражнении, так, чтобы можно было отвечать на вопросы, которые следуют из этих знаний. Покажите, что на них действительно можно найти ответы с помощью этой базы знаний, и включите в ваш отчет описание исправлений, объяснение того, почему они потребовались, указание, являются ли эти исправления мелкими или крупными, и т.д.
а) Находились ли другие люди в супермаркете Safeway в то время, как там
был Джон? [Да — работники супермаркета!]
б) Является ли Джон вегетарианцем? [Нет]
в) Кому принадлежит дезодорант в супермаркете Safeway? [Корпорации
Safeway]
г) Имеется ли у Джона унция говяжьего фарша? [Да]
д) Имеется ли бензин в расположенной рядом бензозаправочной станции
Shell? [Да]
е) Имеются ли помидоры в багажнике автомобиля Джона? [Да]
10.24. Напомним, что информация о наследовании в семантических сетях может быть
представлена логически с помощью подходящих импликационных высказыва-
ний. В данном упражнении рассматривается эффективность использования по-
добных высказываний для представления информации о наследовании.
а) Рассмотрим содержание каталога подержанных автомобилей, такого как
Kelly's Blue Book, например, сведения о том, что микроавтобусы типа 1973
Dodge Van стоят 575 долларов. Предположим, что вся эта информация
(об 11 тысячах моделей) закодирована в виде логических правил, как бы-
ло предложено в данной главе. Запишите три таких правила, включая
правило, касающееся микроавтобусов типа 1973 Dodge Van. Как вы смо-
жете воспользоваться этими правилами, чтобы найти стоимость конкрет-
ного автомобиля (например, модели JB, которая относится к типу 1973
Dodge Van) при наличии такого средства автоматического доказательства
теорем по методу обратного логического вывода, как Prolog?
б) Сравните временную эффективность использования для решения этой
задачи метода обратного логического вывода и метода наследования, ис-
пользуемого в семантических сетях.
в) Объясните, как метод прямого логического вывода позволяет использовать
систему на основе логики для эффективного решения той же задачи, при условии, что база знаний содержит только 11 тысяч правил, касающихся цен.
г) Опишите ситуацию, в который ни прямой, ни обратный логический вывод с помощью этих правил не позволяет эффективно выполнить запрос
о цене на какой-то отдельный автомобиль.
д) Можете ли вы предложить решение, позволяющее эффективно отвечать
на запросы этого типа во всех вариантах логических систем? (Подсказка.
Напомним, что два автомобиля одной и той же категории имеют одинаковую цену.)
10.25. Можно было бы предположить, что не требуется подчеркивать в семантических сетях синтаксические различия между связями с метками, не заключенными в прямоугольники, и связями с метками в одинарном прямоугольнике,
поскольку связи с метками в одинарном прямоугольнике всегда закреплены за
категориями; а в алгоритме наследования, допустим, можно было бы просто
принять допущение, что связь с меткой без прямоугольника, закрепленная за
некоторой категорией, предназначена для применения ко всем элементам
этой категории. Покажите, что такое утверждение является ошибочным,
и приведите примеры ошибок, которые могут возникнуть из-за этого.







Материалы

Яндекс.Метрика