Содержание к диссертации
Введение
ГЛАВА 1. Анализ путей построения интеллектуальных систем большой размерности и постановка проблемы исследования 20
1.1. Анализ современных исследований в области построения интеллектуальных систем большой размерности на продукционной модели знаний 20
1.1.1. Актуальность продукционной модели знаний в интеллектуальных системах 20
1.1.2. Место проблемы ускорения поиска в создании интеллектуальных систем на продукционной модели знаний 26
1.1.3. Анализ существующих методов повышения эффективности механизмов поиска в продукционных базах знаний большой размерности 29
1.1.4. Анализ существующих реализаций интеллектуальных систем с позиции антропоморфного подхода 35
1.2. Концептуальная модель интеллектуальной системы на основе базы знаний большой размерности 40
1.2.1. Принципы организации баз знаний с использованием прецедентов 40
1.2.2. Модель машины вывода для баз знаний большой размерности 42
1.3. Перспективные интеллектуальные системы большой размерности и постановка проблемы исследования 50
1.3.1. Структура и состав перспективных интеллектуальных систем большой размерности 50
1.3.2. Постановка проблемы исследования 54
Выводы 57
ГЛАВА 2. Общесистемные методы повышения эффективности поиска в базах знаний большой размерности 58
2.1. Редукция дерева решений путем устранения повторяющихся ветвей 58
2.1.1. Метод устранения повторяющихся ветвей в пределах одного дерева решений 58
2.1.2. Ускорение поиска при прямом и обратном логическом выводе 64
2.2. Методы организации поиска в интеллектуальных системах большой размерности 67
2.2.1. Методы обеспечения актуальности прецедентов в изменчивых базах знаний 67
2.2.2. Метод управления контекстом при поиске в базах знаний большой размерности 77
2.3. Методы создания прецедентов методом случайных блужданий с использованием множества агентов 82
2.3.1. Применение мультиагентного подхода и метода случайных блужданий к задаче поиска 82
2.3.2. Исследование эффективности создания прецедентов методом случайных блужданий 93
Выводы 99
ГЛАВА 3. Алгоритмические методы ускорения поиска в интеллектуальных системах на основе базы знаний большой размерности 101
3.1. Индексация и предварительный отбор фактов базы знаний, релевантных условиям правил 101
3.1.1. Теоретические предпосылки и обоснование целесообразности индексации фактов 101
3.1.2. Алгоритм индексации и предварительного отбора фактов для редуцирования пространства поиска 104
3.1.3. Оценка эффективности использования индексов и предварительного отбора фактов для редуцирования пространства поиска 106
3.2. Метод логического вывода на основе теоретико-множественных операций 110
3.2.1. Обоснование возможности реализации логического вывода в реляционной модели знаний 110
3.2.2. Реализация логического вывода с помощью теоретико-множественных операций 113
3.3. Реализация быстрых реляционных операций методами логического программирования 115
Выводы 125
ГЛАВА 4. Методы редуцирования пространства поиска на основе информационного подхода 126
4.1. Метод оценки информативности понятий и утверждений в базах данных и знаний 126
4.1.1. Словарно-контекстный метод оценки информативности понятий предметной области 126
4.1.2. Метод оценки информативности фактов в базах знаний 134
4.1.3. Оценка информативности данных в реляционной базе 147
4.1.4. Метод редуцирования пространства поиска за счет рационального порядка следования утверждений в запросе 151
4.2. Применение троичной логики для редуцирования пространства поиска154
4.2.1. Модель базы знаний в троичной логике 154
4.2.2. Визуализация и объяснение результатов рассуждений в троичной
логике 157
4.2.3. Исследование временных характеристик вывода в троичной логике 161
4.3. Анализ методов организации поиска в расширяющемся домене 163
4.3.1. Поиск решений в допущениях замкнутого и открытого мира 163
4.3.2. Исследование временных характеристик поиска в узком домене 166
4.3.3. Исследование скорости поиска в расширяющемся домене 168
Выводы 175
ГЛАВА 5 Практическая реализация и оценка эффективности разработанных методов 177
5.1. Применение разработанных методов в интеллектуальных системах большой размерности на воздушном транспорте 177
5.1.1 Реализация методов ускорения поиска решений в системе технологического обслуживания кассира 177
5.1.2. Реализация методов управления прецедентами в системе взаиморасчетов на воздушном транспорте 180
5.2. Планирование и организация экспериментального исследования 182
5.2.1. Обоснование выбора программно-аппаратной платформы для экспериментов 182
5.2.2. Состав и организация тестовой базы знаний 185
5.3. Практическая реализация разработанных методов и исследование их производительности 187
5.3.1. Реализация индексации и предварительного отбора фактов, релевантных условиям правил 187
5.3.2. Экспериментальное исследование времени обработки правил SWRL как запросов SQL 195
5.3.3. Реализация быстрых операций реляционной алгебры в среде Visual Prolog 197
5.3.4. Исследование быстродействия быстрых предикатов Пролога для операций над множествами 202
5.3.5. Методы управления прецедентами в условиях изменчивости баз знаний 207
5.3.6. Исследование временных издержек на поддержание актуальности
прецедентов 213
Выводы 220
Заключение 222
Список сокращений и условных обозначений 228
Термины и определения 229
Библиографический список
- Анализ существующих методов повышения эффективности механизмов поиска в продукционных базах знаний большой размерности
- Ускорение поиска при прямом и обратном логическом выводе
- Оценка эффективности использования индексов и предварительного отбора фактов для редуцирования пространства поиска
- Реализация методов управления прецедентами в системе взаиморасчетов на воздушном транспорте
Анализ существующих методов повышения эффективности механизмов поиска в продукционных базах знаний большой размерности
Формализация знаний в виде фреймов позволяет абстрагироваться от грамматики и синтаксиса, но сохраняет зависимость от терминологии. Кроме того, фреймовая структура диктует также ограниченность контекста заранее заданными формами. Фреймы широко используются для формализации анкет, платежных документов и т.п.
Семантические сети обладают хорошей наглядностью, обуславливающую их применение для визуализации знаний. При этом в них отсутствует универсальность, в частности, не отображаются отрицания и дизъюнкции, а попытки их добавить приводят к существенной потере наглядности.
Продукционная модель знаний в виде правил на основе импликации вида ЕСЛИ А ТО B свободна большинства перечисленных недостатков. Простота такого представления делает его понятным без специальной подготовки, достаточно только знать особенности операции импликации (из B не следует А и из А не следует В, но из В следует А).
Постоянный рост производительности ЭВМ привел к тому, что в последнее время стали появляться ИС большой размерности, базу знаний которых составляют сотни тысяч и миллионы фактов. Среди них следует упомянуть ResearchCyc, разработку компании Cycorp (www.cyc.com). Следует отметить исследовательский характер данной ИС и отсутствие коммерческих применений.
Кроме проекта Cyc можно отметить разработку ConceptNet, ведущуюся в MIT, база знаний которой насчитывает более миллиона утверждений на английском языке и еще базы знаний меньшего объема на девяти других языках. Изначально ConceptNet позиционировалась как инструмент для практического моделирования рассуждений над текстами на естественных языках. Как и Cyc, ConceptNet используется на практике для аннотации изображений и в задачах распознавания речи, но в силу высокой чувствительности к контексту, ее применение для декларированных авторами более сложных задач, в частности, смыслового расширения запросов к базам знаний (query expansion) остается неясным. ConceptNet имеет Web-сервис Open Mind Common Sense, запущенный в 2000г. и использующий около 14000 поставщиков Web-контента в стиле шаблонов предложений вида «The effect of eating food is ... » (Результат приема пищи это …), «A knife is used for ... » (Нож используется для …) и т.п. MIT также поддерживает проект ARIA (Annotation and Retrieval Integration Agent) – программный агент для автоматической иллюстрации сообщений электронной почты изображениями.
Еще один ресурс, предназначенный для смыслового расширения запросов, WordNet, разрабатываемый начиная с 1985г. в Принстоне и оптимизированный для лексической категоризации и определения схожести слов, состоит из английских слов, организованных в 200 тыс. смысловых единиц, и иерархических отношений типа «is a». В силу несложной структуры и вытекающей из этого простоты использования, WordNet является более успешным по сравнению с ConceptNet [73].
Практически все известные реализации интеллектуальных систем являются антропоцентрическими и только ассистируют пользователю. Например, в сервисе Open Mind Common Sense для предложения «A rocket can … » (ракета может) предлагается несколько десятков вариантов, ранжированных по семантической наполненности, например, hit, coach, land, slam (поразить цель, наводить, приземляться, наносить удар) и т.д.
Более чем скромные достижения интеллектуальных систем по сравнению с объемом вложенного труда обычно объясняются двумя причинами: недостаточным числом знаний начального уровня в базе и комбинаторной сложностью задачи логического вывода [74]. Действительно, в отличие от экспертных систем, в которых количество фактов ограничено возможностями диалога с пользователем или числом сенсоров в составе встраиваемых ЭС, интеллектуальные системы нуждаются в большом количестве фактов, которые должны храниться вместе с правилами. При этом умозаключения в любой предметной области могут потребовать знаний из других областей. М. Мински оценивает знания общего уровня на уровне 30-60 млн. понятий об окружающем мире.
В то же время, благодаря возросшей вычислительной мощности, существующие технические и информационные системы стали интеллектуализироваться, т.е. принимать на себя творческие функции. К таким системам можно отнести системы управления технологическими процессами, включающие в себя подсистемы SCADA, в которых с помощью интеллектуальных алгоритмов на основе продукционных правил выполняется ранняя диагностика, позволяющая предотвращать выход управляемых систем за пределы допустимых параметров или предотвращать аварии. Такие системы широко используются в энергетике, трубопроводном транспорте, на предприятиях нефтехимии и др.
Таким образом, продукционная модель знаний является наиболее предпочтительной для построения интеллектуальных систем в силу полноты, точности, универсальности, понятности для человека, возможности охвата широкого контекста, наглядности и независимости от национального языка.
В связи с тем, что интеллектуальными могут быть даже несложные функции, которые могут встраиваться в стиральные машины, пылесосы и т.п., необходимо ограничить область применения моделей и методов, разрабатываемых в рамках настоящего исследования. Здесь и далее речь будет идти об интеллектуальных системах большой размерности, где проблема экспоненциальной сложности поиска решений выступает на первый план. Интеллектуальной системой большой размерности будем называть ИС, оперирующей с числом фактов, измеряемым миллионами. Для таких систем существующие методы ускорения поиска решений являются неэффективными. 1.1.2. Место проблемы ускорения поиска в создании интеллектуальных систем на продукционной модели знаний
Понятие комбинаторного взрыва, т.е. экспоненциального или сверхэкспоненциального роста сложности решения от размерности входных данных было знакомо исследователям задолго до появления компьютеров и попыток их применения к решению задач поиска на дереве решений. Тем не менее, в основу первых языков логического программирования, в частности механизма вывода Пролога, был положен обратный логический вывод, от консеквента к антецедентам с обходом дерева решений сначала в глубину.
Ускорение поиска при прямом и обратном логическом выводе
Таким образом, представление фактов в пространстве «состояния – события» позволяет, во-первых, легко добавлять в базу новые первичные факты (события) по мере их появления, во-вторых, достаточно просто модифицировать базу вторичных фактов (состояний), последующее извлечение которых является такой же простой процедурой, как и обращение к первичным фактам.
Формирование базы знаний в пространстве «состояния-события» с использованием прецедентов влечет за собой проблему контроля актуальности прецедентов в условиях изменчивости базы фактов. В данной работе предлагаются три варианта организации контроля актуальности прецедентов, как показано на рисунке 2.11:
Алгоритмы управления прецедентами по запросу (а), по расписанию (б) и по наступлению события (в) Первый способ гарантирует актуальность прецедентов, но требует дополнительных временных затрат при каждом обращении к любому прецеденту.
Для этого выполняется обработка всех событий, произошедших с момента создания прецедента, т.е. вместо всех событий от состояния s0 обрабатываются только часть, от состояния st-1, где t-1 – момент выполнения предыдущего запроса. Чтобы это стало возможным, необходимо вместе с прецедентом сохранять время его создания. Второй вариант, управление прецедентами по расписанию имеет право на существование в тех случаях, когда появлением новых фактов, изменением или удалением существующих в промежутке между двумя обновлениям базы прецедентов можно пренебречь.
Первый вариант замедляет процесс извлечения фактов из базы знаний, второй приводит к увеличению времени удаления фактов из базы. Если изменчивость базы знаний невелика, то использование второго варианта является оправданным, в противном случае целесообразно применять первый вариант.
В связи с тем, что управление по расписанию не гарантирует актуальности прецедентов, в дальнейшем ограничимся первым и третьим способом:
Актуальность прецедента проверяется при каждом обращении к нему. В этом случае с прецедентом должны быть сопоставлены все факты, на основе которых он был получен. Триплет ff прецедента может быть представлен следующим образом: ff(s, p, o, n, L), где n – идентификатор прецедента, L – список идентификаторов первичных фактов, связанных с данным прецедентом.
При удалении каждого первичного факта удаляются все связанные с ним прецеденты. Для этого необходимо сканировать списки L во всех прецедентах. Очевидно, что такой подход может привести к большим временным затратам. Решение может заключаться в создании для каждого /–го первичного факта индекса в виде x(i, N), где / - идентификатор факта, N. - множество связанных с /– м фактом прецедентов. В таком случае при удалении /–го первичного факта необходимо удалить множество Nt вторичных фактов. При первом подходе среднее время tl извлечения прецедента с тестированием его актуальности определяется формулой tx = У т \Р\ + У zm\F\ = У т{\Р\ + m\F\\ (2.9) где г время извлечения одного факта, Р - множество прецедентов, m -среднее число первичных фактов, использованных при выводе прецедента. При втором подходе среднее время t2 извлечения прецедента t2 =V2T\P\, (2.10) а среднее время td удаления прецедентов для каждого удаляемого первичного факта потребует полного сканирования всей базы прецедентов и составит td = x\P\. (2.11) Как видно из приведенных формул, время обращения к базе прецедентов может существенно отличаться от времени извлечения первичного факта, но при увеличении размера базы знаний время растет линейно, а не экспоненциально. Если в условии правила присутствуют вызовы других правил, применение прецедентов позволяет устранить вложенность правил и существенно сократить время обработки правила. Среднее время t создания одного прецедента
Оценка эффективности использования индексов и предварительного отбора фактов для редуцирования пространства поиска
В отличие от Шеннона у Колмогорова количество информации -величина, которая может быть отрицательной [107]. Положительной стороной теории информации Колмогорова является возможность вычислять информативность связанных событий, однако сложность таких вычислений оказывается чрезмерной. На основании вышеизложенного представляется целесообразным использовать для оценки информативности понятий и фактов подход Шеннона.
Количество информации в одной букве русского алфавита (в предположении, что вероятности появления в слове всех букв равны) приблизительно равно пяти битам, что соответствует пяти двоичным разрядам, которыми русский алфавит как раз и может быть закодирован.
Следует признать, что механическое перенесение энтропии алфавита на составляемые с его помощью слова лишено смысла, иначе слова из редко встречающихся букв будут более информативными, а английский текст менее информативным, чем русский, поскольку не только латинский алфавит содержит меньше знаков, но и английские слова обычно короче русских. Существует гипотеза, выдвинутая 75 лет назад Г. Ципфом и заключающаяся в том, что часто используемые слова обычно короче, а значимость слова обратно пропорциональна его встречаемости [108]. Таким образом, длинные слова все же несут в себе больше информации. Один из аргументов в пользу данной гипотезы состоит в том, что количество информации, получаемое в единицу времени при чтении текста или слушании речи, не должно сильно варьироваться, иначе информация не будет усвоена [109]. Видимо, этим обстоятельством объясняется тот факт, что алфавитный подход к определению количества информации в тексте активно используется в школьных курсах 8 информатики [ПО], хотя количество информации в одном и том же слове «скорость» на английском языке {speed) и немецком (Geschwindigkeit) будет различаться в три раза.
Слово - это код для обозначения понятия, причем код - заведомо избыточный. Пусть средняя длина слова равна шести знакам, каждый из которых кодируется пятью битами, т.е. имеет 32 значения, если игнорировать букву «». В таком случае максимальное число слов равно 326 1 млрд. слов; это означает, что избыточность составляет не менее двух порядков. Если рассматривать слово как минимальную лексическую единицу (атом), то к его информативности можно применить подход Шеннона. Применяя формулу где \D\ - мощность словаря, w. - /-е слово словаря, /?(w.) - вероятность появления слова w., которая может быть вычислена следующим образом: где ni – число экземпляров слова wi в множестве текстов. Таким образом, энтропия словаря зависит от набора текстовых документов, использующих данный словарь. Вычисление энтропии словаря не представляется возможным по следующим причинам.
Постоянно растущее число документов. По состоянию на конец декабря 2011 года поисковая система Google проиндексировала более 25 млрд. ресурсов, в то время как на конец декабря 2009 года их число не превышало 10 млрд. Поисковые системы строят и поддерживают частотные словари для целей ранжирования результатов поиска и располагают возможностями для вычисления энтропии слов. Однако растущее число документов может 9 привести к тому, что информативность текста, не подверженного изменениям, будет постоянно меняться.
Синонимия и полисемия. Автоматическая обработка документов в целях вычисления энтропии словаря невозможна, поскольку одно и то же слово может использоваться для обозначения разных понятий (полисемия) равно, как разные слова могут обозначать одни и те же понятия (синонимия), а энтропия слова вне его значения лишена смысла.
Многоязычность. Глобальное множество текстовых документов разделяется на подмножества в соответствии с числом языков. Разные языки имеют отличающиеся по количеству слов словари. Данное обстоятельство может привести к тому, что один и тот же документ, переведенный на разные языки, будет обладать разной информативностью. Решением данной проблемы может быть создание глобального словаря, включающего в себя понятия из всех языков. Однако сложность этой задачи не оставляет надежд на ее решение в ближайшем будущем.
Если пренебречь разной частотностью слов, составляющих словарь, то количество информации I{w,D) в слове w, определенном на множестве D (словаре), можно определять как где \D\ - мощность словаря, we D. Здесь мы сталкиваемся с проблемой определения \D\. Автор текста владеет одним словарным запасом, а его читатели - другим. Следовательно, информативность текста становится субъективной характеристикой, что, впрочем, соответствует действительности. Например, если читатель встречает незнакомое слово, лежащее вне его словаря, то информативность этого слова для него равна
Реализация методов управления прецедентами в системе взаиморасчетов на воздушном транспорте
Если два аэропорта связывают несколько рейсов, это приводит к тому, что вершины аэропорта прилета на графе размножаются (пунктирные эллипсы). Поиск маршрута заключается в нахождении связи между исходным пунктом и пунктом назначения при выполнении множества ограничений, в т.ч. минимально и максимально допустимое время ожидания стыковочных рейсов, наличие мест на каждый рейс и др. После этого выбранные маршруты сортируются в порядке возрастания основного предпочтения клиента: времени в пути, числа пересадок или цены билета.
Метод индексации и предварительной обработки фактов, релевантных условиям запроса, предложенный в работах [54], [59], [56], в применении к поиску маршрута в упрощенном виде можно представить следующим образом. Для всех рейсов вида R=(D, dd, td, A, da, ta), где D – аэропорт вылета,
Здесь знак подчеркивания означает, что значение переменной для запроса несущественно (анонимная переменная), а t1+ – время, отличающееся в большую сторону от t1 на величину, превышающую время пересадки с рейса на рейс. В целях простоты изложения материала здесь не учитывается возможный переход через сутки для стыковочных рейсов.
Предварительный отбор фактов для каждого запроса состоит в составлении списков рейсов из каждого индекса и нахождении пересечений списков. Более подробно алгоритм обработки индексов изложен в работе [3]. Результатом поиска в индексах является список рейсов, удовлетворяющих условиям поиска, сокращенный на 1-3 порядка по сравнению с исходным. Такой разброс диапазона редукции пространства поиска объясняется различием степеней свободы в зависимости от конкретного запроса. Если исходный пункт или пункт назначения – небольшие города, то коэффициент ветвления дерева поиска существенно меньше, чем для авиационных хабов. 0
Поскольку зависимость предпочтений клиентов от характеристик маршрутов не всегда является монотонной, то либо предлагаемые варианты могут не устраивать пассажира, либо число вариантов может быть слишком большим. В этой связи целесообразно сохранять ранее составленные и оплаченные маршруты в качестве прецедентов и предлагать их следующим клиентам в качестве готовых вариантов.
Такой подход не только позволяет сократить время поиска решений, но также учитывать дополнительные факторы, которые не хранятся в базах знаний. В частности, недалеко от аэропорта г. Рейкьявика находится спа-курорт «Голубая лагуна» на геотермальном озере, и многие пассажиры трансатлантических рейсов предпочитают делать там остановку на несколько часов для посещения курорта. Сохранение истории бронирований в виде прецедентов позволяет в предлагать такой вариант в качестве приоритетного несмотря на то, что данные об этом курорте в системе отсутствуют, и предоставление такого рода сервисов в функционал системы бронирования перевозок не входит.
Таким образом, применение разработанных методов и алгоритмов в автоматизированной системе бронирования авиаперевозок обеспечило редукцию пространства поиска и сокращение времени обработки транзакций.
Применение в АРС «Сирена-Тревел» и СВВТ ТКП (отмечены на рисунке 1.11 заливкой) результатов диссертационного исследования заключалось в сохранении и использовании цепочек стыковочных маршрутов, составленных при выполнении предыдущих операций бронирования; формировании перечня услуг для часто летающих пассажиров; 1 сохранении типовых условий применения тарифов; формировании типовых реакций на отмены рейсов. Сохранение результатов предыдущих операций поиска и найденных решений в виде прецедентов позволило не только в среднем на 20% сократить время поиска в базах данных, но также предлагать в первую очередь апробированные решения, что сокращает время диалога с пользователем.
Целью организации взаиморасчетов на воздушном транспорте является исключение встречных платежей между участниками процесса перевозок, достигаемое за счет использования взаимозачетов (клиринга). Задача оптимизации взаиморасчетов в СВВТ не имеет формального алгоритма, но в силу наличия обширной статистики здесь может использоваться механизм прецедентов, изложенный в работах [35], [114], [69]. Рассмотрим упрощенную модель взаиморасчетов, в котором первичным фактом или событием является запись об одном проданном или отмененном месте на рейс Е = (R, Р, B, С, ds, dd), где R - номер рейса, Р - агент (принципал), В - перевозчик (бенефициар), С - уплаченная (возвращенная) сумма, ds - дата продажи билета, dd - дата перевозки. При этом дата расчетов dp находится в диапазоне ds dp dd. Вторичным фактом (состоянием) будем считать регистр S = (R, Р, С, dd\ который обновляется после каждого события Е.
Задача заключается в нахождении суммы платежа на дату расчетов dp, максимально приближенной к значению С на дату перевозки dd. Для включения механизма прецедентов предложено создавать факты вида Т = (R, Р, С\, Съ dd), где С\ - сумма в регистре S на дату dp, Сі - сумма окончательного расчета агента Р с перевозчиком Р за рейс R, выполняемый в день dd. Вместо расчета прогноза сумм, подлежащих уплате, может быть использован сохраненный прецедент. Поскольку суммы, уплаченные за билет, зависят от множества факторов, вероятность найти прецедент, в точности повторяющий текущую ситуацию, невелика. В связи с этим значение С округляется с точностью 10%. 2
Таким образом, применение прецедентов в алгоритмах взаиморасчетов на воздушном транспорте позволило приблизительно на треть сократить время обработки транзакций по интерактивной отчетности при сохранении точности прогнозирования взаимно компенсируемых объемов денежных потоков за счет клиринга.
