Искусственный интеллект. Современный подход

МИР ПОКУПОК В INTERNET

Flash, протоколы защиты от роботов, плохо сформированный код HTML, звуковые файлы, фильмы и текст, который появляется только в составе графического изображения, например в формате JPEG. Агент, способный действовать в пределах всей Internet, должен быть почти таким же сложным, как и робот, способный двигаться в реальном мире. Поэтому мы сосредоточимся на описании простого агента, в котором не учитывается большая часть этих осложнений.
Листинг 10.1. Web-страница типичного оперативного магазина в форме, воспринимаемой человеком — пользователем браузера (вверху), и соответствующая строка HTML, принимаемая браузером или воспринимаемая торговым агентом (внизу). В языке HTML символы между знаками < и > представляют собой директивы разметки, которые указывают, как должна отображаться страница. Например, строка Select означает, что нужно переключиться на курсивный шрифт, отобразить слово Select, а затем отменить использование курсивного шрифта. Идентификатор страницы, такой как http://gen-store.cam/books, называется унифицированным локатором ресурсов, или URL (Uniform Resource Locator). Разметка <а href ="url">anchor означает, что должна быть создана гипертекстовая ссылка на локатор url с текстом анкера anchor
Generic Online Store
Select from our fine line of products:
• Computers
• Cameras
• Books
• Videos
• Music
Generic Online Store
Select from our fine line of products:

В первую очередь задача агента состоит в том, чтобы найти соответствующие товарные предложения (ниже будет показано, как выбрать наилучшие из искомых предложений). Допустим, что query — описание товара, которое вводит пользователь (например, "laptops" — портативные компьютеры); в таком случае некоторая страница представляет собой предложение, соответствующее запросу query, если страница действительно ему соответствует и содержит подходящее предложение. Мы должны также следить за URL, связанным с этой страницей:
RelevantOffer {раде, url, query) Relevant {page, url, query) A Offer(page)
Запросу будет соответствовать страница с обзором новейших портативных компьютеров высокого класса, но если она не предоставляет способ купить такой компьютер, то ее нельзя рассматривать как предложение. Например, можно утверждать, что страница является предложением, если на ней содержится слово "buy" (покупка) или "price" (цена) в какой-то ссылке HTML или в форме, относящейся к этой странице. Иными словами, если страница содержит строку в виде "<а ... buy ... то является предложением; на ней может также применяться слово "price" вместо "buy", а вместо дескрип-

• Computers
• Books
• Videos
• Offer(page) {InTag{"a", str, page) v 1пТад{11 form", str, page))
  л (In{11 buy", str) v In ("price", str)) InTagi tag, str, page) In{"<" + tag + str + " Теперь необходимо найти соответствующие страницы. Применимая для этого стратегия состоит в том, чтобы начать с начальной страницы некоторого оперативного магазина и рассмотреть все страницы, которых можно достичь, следуя по соответствующим ссылкам6. Агент должен обладать знаниями о многих магазинах, например, в таком виде:
  Amazon е OnlineStores л Homepage{Amazon, "amazon.com")
  Ebay е OnlineStores л Homepage(Ebay, "ebay.com")
  GenStore ? OnlineStores л Homepage(GenStore, "gen-store.com")
  В этих магазинах товары классифицируются по категориям товаров, а на начальной странице предоставляются ссылки на основные категории товаров. К младшим категориям можно перейти, следуя по цепочке соответствующих ссылок, что позволяет в конечном итоге проложить путь к требуемым предложениям. Иными словами, страница соответствует запросу, если ее можно достичь, проследовав по цепочке соответствующих ссылок на категории от начальной страницы магазина, а затем пройдя еще по одной ссылке к предложению товара:
  .Relevant (page, url, guery)
  3store,home store e OnlineStores л Homepage(store, home) л 3url2 RelevantChain (home, url2, query) л Link(url2, url) л page = GetPage(url)
  Здесь предикат Link(from, to) означает, что имеется гиперссылка от URL from к URL to (см. упр. 10.13); чтобы определить, какая цепочка ссылок может рассматриваться как соответствующая запросу, RelevantChain, необходимо следовать не просто по любым существующим гиперссылкам, а только по таким ссылкам, связанный с которыми текст анкера указывает, что эта ссылка соответствует данному запросу на приобретение товара. Для этого используется предикат LinkText(from, to, text), который означает, что имеется ссылка между URL from и to, текстом анкера которой является text. Цепочка ссылок между двумя URL, start и end, соответствует описанию d, если текст анкера каждой ссылки представляет собой соответствующее имя категории для d. Существование самой цепочки определяется с помощью рекурсивной формулировки, в которой в качестве базового случая используется пустая цепочка (st RelevantChain (start, end, query) <> (start=end) v
  (3u, text LinkText(start,u, text) л RelevantCategoryName(query, text) A RelevantChain(u, end, query))
  • Строки text и query именуют одну и ту же категорию, например "laptop computers"и"laptops".
  • В строке text именуется надкатегория, такая как " computers".
  • В строке text именуется подкатегория, такая как "ultralight notebooks".
  Логическое определение предиката RelevantCategoryName состоит в следующем:
  RelevantCategoryName {query, text)
  3ci,C2 Name {query, c±) л Name {text, C2)
  A { Ci С C2 V C2 С Ci) (10.1)
  В противном случае текст анкера не соответствует запросу, поскольку в нем именуется категория, не соответствующая данному описанию, такая как "mainframe computers" (мэйнфреймы) или "lawn & garden" (газон и сад).
  Поэтому, чтобы обладать способностью следовать по искомым ссылкам, необходимо иметь широкие знания об иерархии категорий товаров. Верхняя часть этой иерархии может выглядеть, как показано в табл. 10.1, а. Задача перечисления всех возможных товарных категорий неосуществима, поскольку у покупателя всегда могут
  Теперь необходимо определить, что подразумевается под высказыванием, будто текст text является соответствующим именем категории RelevantCategoryName для запроса query. Прежде всего необходимо связать строки с категориями, именуемыми с помощью этих строк. Такую задачу можно решить с использованием предиката Name{s, с), который сообщает, что строка s является именем категории с, например, чтобы можно было сформулировать утверждение, что Name{ "laptops", LaptopComputers). Некоторые дополнительные примеры применения предиката Name приведены в табл. 10.1, б. Затем определим понятие соответствия. Допустим, что запросом query является "laptops" (Портативные компьютеры). В таком случае предикат RelevantCategoryName {query, text) принимает истинное значение, когда выполняется одно из приведенных ниже условий.
  возникнуть какие-то новые пожелания, а производители всегда готовы предложить новые товары для их удовлетворения (возможно, скоро будут даже продаваться обогреватели для коленных чашечек?). Тем не менее онтология, состоящая примерно из тысячи категорий, должна оказаться очень полезным инструментом для большинства покупателей.
  Кроме самой иерархии товаров, необходимо иметь богатый словарь имен для категорий. Жизнь была бы гораздо проще, если бы существовало взаимно однозначное соответствие между категориями и символьными строками, которые их именуют. Мы уже сталкивались с проблемой синонимов — двух имен для одной и той же категории, таких как "laptop computers" and "laptops". Кроме того, существует также проблема омонимов — обозначения одним именем двух или нескольких разных категорий. Например, если в базу знаний, приведенную в табл. \0А,б, будет добавлено следующее вполне допустимое высказывание, что словом "CDs" обозначаются депозитные сертификаты:
  Name (11 CDs 11 , Certifi catesOfDeposi t)
  то имя "CDs" будет относиться к двум различным категориям.
  Наличие синонимов и омонимов может стать причиной значительного увеличения количества путей, по которым должен следовать агент, и иногда может затруднить определение того, действительно ли данная страница соответствует запросу. Гораздо более серьезная проблема состоит в том, что пользователь может вводить очень широкий спектр описаний, а магазин может использовать не такие имена категорий, о которых знает агент. Например, в ссылке может быть указано " laptop", тогда как в базе знаний имеется только имя "laptops", или пользователь может ввести запрос: "компьютер, который помещается на откидном столике сидения экономического класса в самолете Boeing 737". Невозможно заранее перечислить все способы, с помощью которых могут присваиваться имена какой-то категории, поэтому в некоторых случаях агент должен проявлять способность проводить дополнительные рассуждения для определения того, соответствует ли рассматриваемый текст отношению Name. В наихудшем случае для этого требуется полное понимание естественного языка, но отложим эту тему до главы 22. На практике многое можно сделать с помощью нескольких простых правил, например, позволяющих согласовать слово " laptop" с категорией, названной как " laptops". В упр. 10.15 предлагается разработать множество таких правил после проведения некоторых исследований, касающихся оперативных магазинов.
  Готовы ли мы применить некоторый алгоритм логического вывода для получения множества предложений, соответствующих нашему запросу, после того как составлены логические определения, описанные в предыдущих абзацах, и подготовлены приемлемые базы знаний о категориях товаров и соглашениях об именовании? К сожалению, не совсем! Недостающим элементом является функция GetPage(url), которая ссылается на HTML-страницу, находящуюся по заданному URL. Агент не хранит в своей базе знаний содержимое страниц с каждым URL, а также не располагает явными правилами дедуктивного вывода того, каким должно быть это содержимое. Вместо этого можно предусмотреть, чтобы правильная процедура HTTP выполнялась каждый раз, когда какая-то подцель требует применения функции выборки страницы GetPage. Благодаря этому машина логического вывода сталкивается с такой ситуацией, как если бы вся система Web находилась в базе знаний. В этом состоит пример применения общего метода, называемого процедурным вложением, с помощью которого конкретные предикаты и функции могут выполняться с использованием методов специального назначения.