Главная arrow Логика arrow Хранение и выборка
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Хранение и выборка Печать

В основе функций Tell и Ask, применяемых для ввода информации и передачи запросов в базу знаний, лежат более примитивные функции Store и Fetch. Функция Store (s) сохраняет некоторое высказывание s в базе знаний, а функция Fetch (q) возвращает все унификаторы, такие, что запрос д унифицируется с некоторым высказыванием из базы знаний. Описанная выше задача, служившая для иллюстрации процесса унификации (поиск всех фактов, которые унифицируются с высказыванием Knows (John, х)), представляет собой пример применения функции Fetch.

Проще всего можно реализовать функции Store и Fetch, предусмотрев хранение всех фактов базы знаний в виде одного длинного списка, чтобы затем, после получения запроса q, можно было просто вызывать алгоритм Unify(g, s) для каждого высказывания s в списке. Такой процесс является неэффективным, но он осуществим, и знать об этом — это все, что нужно для понимания последней части данной главы. А в оставшейся части данного раздела описаны способы, позволяющие обеспечить более эффективную выборку, и он может быть пропущен при первом чтении.

Функцию Fetch можно сделать более эффективной, обеспечив, чтобы попытки унификации применялись только к высказываниям, имеющим определенный шанс на унификацию. Например, нет смысла пытаться унифицировать Knows (John, х) и Brother (Richard, John). Такой унификации можно избежать, индексируя факты в базе знаний. Самая простая схема, называемая индексацией по предикатам, предусматривает размещение всех фактов Knows в одном сегменте, а всех фактов Brother— в другом. Сами сегменты для повышения эффективности доступа можно хранить в хэш-таблице.

Индексация по предикатам является удобной, когда имеется очень много предикатных символов, но лишь небольшое количество выражений в расчете на каждый символ. Однако в некоторых приложениях имеется много выражений в расчете на каждый конкретный предикатный символ. Например, предположим, что налоговые органы желают следить за тем, кто кого нанимает, с использованием предиката Employs (х, у). Такой сегмент, возможно, состоящий из миллионов нанимателей и десятков миллионов наемных работников, был бы очень большим. Для поиска ответа на такой запрос, как Employs (х, Richard) ("Кто является нанимателем Ричарда?"), при использовании индексации по предикатам потребовался бы просмотр всего сегмента.

Поиск ответа на данный конкретный запрос стал бы проще при использовании индексации фактов и по предикату, и по второму параметру, возможно, с использованием комбинированного ключа хэш-таблицы. В таком случае существовала бы возможность просто формировать ключ из запроса и осуществлять выборку именно тех фактов, которые унифицируются с этим запросом. А для ответа на другие запросы, такие как Employs (AIMA. org, у), нужно было бы индексировать факты, комбинируя предикат с первым параметром. Поэтому факты могут храниться под разными индексными ключами, что позволяет моментально сделать их доступными для разных запросов, с которыми они могли бы унифицироваться.

Если дано некоторое высказывание, которое подлежит хранению, то появляется возможность сформировать индексы для всех возможных запросов, которые унифицируются с ними.

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

Примеры решеток обобщения: решетка обобщения, самым нижним узлом которой является высказывание Employs fAIMA.org,Richard; (а);решетка обобщения для высказывания Employs (John, John).

Только что описанная схема применяется очень успешно, если решетка содержит небольшое количество узлов. А если предикат имеет п параметров, то решетка включает 0BП) узлов. Если же разрешено применение функциональных символов, то количество узлов также становится экспоненциально зависимым от размера термов в высказывании, подлежащем хранению. Это может вызвать необходимость создания огромного количества индексов. В какой-то момент затраты на хранение и сопровождение всех этих индексов перевесят преимущества индексации.

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