НАУКА и ОБРАЗОВАНИЕ

Россия, МГТУ им. Н.Э. Баумана

apkarepnko@mail.ru

trudonoshin@mail.ru

Введение

          Корпоративная база знаний представляет собой совокупность большого числа разного рода слабоструктурированных документов, в которых с той или иной степенью подробности описаны прецеденты – некоторые ситуации и решения, которые были приняты в этих ситуациях. В системах поддержки принятия решений (СППР), которые используют такие базы знаний, поиск решения заключается в поиске в них наиболее подходящих прецедентов и соответствующих им документов [1].

          Современные поисковые системы основаны, преимущественно, на применении полнотекстового поиска. При этом учитывается частота встречаемости терминов в документе, их средняя языковая частотность и так далее [2]. Альтернативой полнотекстовому поиску является поиск по метаданным, то есть поиск по атрибутам документов, содержащимся в их метаданных. Классический атрибутивный поиск основывается на использовании в качестве метаданных документа преимущественно его регистрационных атрибутов (авторы документа, название документа, дата создания, тема и т.п.) [3]. Эффективность поиска решений в базах знаний прецедентов можно повысить, основываясь не на регистрационных атрибутах документов, а на параметрах, характеризующих ситуацию принятия решения и само решение.

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

О задаче поиска информации в общей постановке говорят в терминах модели поиска, которая включает в себя способ представления документов, способ представления поисковых запросов, вид критерия релевантности документов [9]. В данной работе документы в базе знаний, а также поисковые запросы представляются в виде фреймов, которые называются паттерном проектирования и паттерном запроса соответственно. Слоты этих паттернов соответствуют ролям концептов используемой онтологии (предметная область, объект, свойство, действие, задача и т.д.) [1]. Указанные роли разбивают концепты онтологии, документа и запроса к базе знаний на кластеры. Предполагается, что по методике построения семантической сети документа, построены семантические сети указанных кластеров. Таким образом, поисковые образы документа и запроса представляются в виде совокупности семантических сетей, соответствующих слотам паттерна проектирования и паттерна запроса.

          В пером разделе работы приводим постановку задачи многокритериальной оценки релевантности документов корпоративной онтологической базы знаний. Во втором разделе даем определения множества и фронта Парето поставленной задачи. Третий раздел содержит обзор известных классов методов многокритериальной оптимизации и обоснование выбора класса адаптивных методов многокритериальной оптимизации. В четвертом разделе представляем предлагаемый адаптивный метод многокритериальной оценки релевантности. В заключении формулируем основные результаты работы и перспективы ее развития.

1. Постановка задачи

Положим, что, например, по методике, предложенной в работе [10], семантическая сеть  рассматриваемой онтологии  построена в виде взвешенного связного графа  с весами узлов  и весами ребер ; . Пусть аналогично определена семантическая сеть  рассматриваемого документа  в виде взвешенного связного графа , имеющего веса узлов , веса ребер  и «расстояние» между узлами ; , . Здесь и далее запись вида , где  - некоторое множество или вектор, означает мощность этого множества или размерность вектора соответственно.

Тем или иным способом, произведена ролевая кластеризация семантических сетей , , так что множество концептов  разделено на  непересекающихся «ролевых» кластеров , а множество концептов  документа  ‑ на такое же число ролевых кластеров ; . Кластерам ,  ставим в соответствие их семантические сети ,  и графы , . Обозначим  - вес узла  графа ,  - вес ребра этого графа, связывающего его узлы . Здесь ,;  ‑ число концептов в кластере  (равное числу узлов в графе). Аналогичные обозначения ,  введем для графа  [10].

Пусть паттерн проектирования  документа  имеет  слотов  и слот  соответствует роли . Поисковый образ документа  представляет собой  семантических сетей , формализованных в виде графов ; . Не ограничивая общности рассуждений, полагаем, что поисковый образ запроса  формирует паттерн , который также имеет  слотов  [10].

Введем следующие обозначения:  - множество концептов запроса ;  - число концептов во множестве ;  - ролевые кластеры множества , ;  - множество концептов кластера ;  - число концептов в кластере ;  - семантическая сеть кластера ;  - граф семантической сети ;  - вес узла  графа ;  - вес ребра  графа . Здесь , . Таким образом, поисковый образ запроса  представляет собой  семантических сетей , формализованных в виде графов ;  [10].

Обозначим  совокупность критериев релевантности, формализующих близость семантических сетей  поискового образа документа  и семантических сетей  запроса ; . Полагаем, что большим значениям критерия  соответствует большая релевантность документа  поисковому запросу .

Ставим следующую дискретную задачу многокритериальной оптимизации (МКО). Среди всех документов , имеющихся в базе знаний, найти документ , который максимизирует векторный критерий релевантности :

.                                    (1)

          Поскольку речь идет о фиксированном запросе , в дальнейших записях символ  будем опускать.

2. Множество и фронт Парето задачи многокритериальной оценки релевантности

Критерии , , как правило, являются противоречивыми, так что документ , максимизирующий критерий , в общем случае не доставляет максимум остальным указанным критериям. Поэтому запись (1) следует понимать только в том смысле, что лицу, принимающему решения (ЛПР), желательна максимизация всех критериев , .

Критериальная вектор-функция  выполняет отображение множества  в некоторое множество  критериального пространства, которое называется множеством достижимости задачи (1). Введем на множествах ,  отношение доминирования.

Вектор  доминирует вектор , что записываем в виде , если среди равенств и неравенств ,  имеется, хотя бы одно строгое.

Документ  доминирует документ , то есть , если .

Выделим из множества  подмножество точек  ‑ фронт Парето МКО-задачи (1), которые не доминируются другими точками множества  и среди которых нет доминирующих друг друга. Множество , соответствующее множеству , называют множеством Парето указанной МКО-задачи. Таким образом, если , то .

          Множество Парето и фронт Парето занимают в теории многокритериальной оптимизации исключительное место. Это обусловлено тем обстоятельством, что согласно известному принципу Эджворта-Парето, при «разумном» поведении ЛПР выбор решения следует производить на множестве Парето.

Роль множества Парето при решении задач МКО определяет также следующая теорема [11].

Теорема. Если для некоторых весовых множителей ,  имеет место равенство

,                                     (2)

то вектор  оптимален по Парето, то есть .

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

Заметим, что теорема задает лишь необходимое условие оптимальности по Парето вектора . Другими словами, из того факта, что точка  принадлежит множеству Парето, не следует, что эта точка обязательно удовлетворяет условию (2).

Постановка МКО-задачи (1) фиксирует лишь множество допустимых значений  и вектор критериальных функций . Как правило, этой информации недостаточно для однозначного решения указанной задачи. Данная информация позволяет лишь выделить соответствующее множество Парето. Поэтому часто говорят, что решением МКО-задачи в постановке (1) является множество Парето этой задачи. Для однозначного решения задачи нужна дополнительная информация, которая в той или иной форме может быть предоставлена только ЛПР.

3. Обзор методов многокритериальной оптимизации

Методы решения задачи МКО чрезвычайно разнообразны. Существует несколько способов классификации этих методов. Используем в качестве основы классификацию, предложенную в работе [11], и выделим следующие классы методов решения МКО-задачи:

‑ априорные методы;

‑ апостериорные методы;

‑ адаптивные методы;

‑ методы Парето-аппроксимации.

Методы каждого из указанных классов имеет свои достоинства и ни один из них не свободен от недостатков, наличие которых не позволяет признать методы этого класса универсальными. Эти же классы методов в значительной мере переплетаются друг с другом так, что не всегда МКО-метод удается однозначно отнести к тому или иному классу. Так, в настоящее время развивается класс адаптивных эволюционных методов, которые основаны на многократном построении некоторых фрагментов множества Парето. Примером алгоритмов этого класса служит алгоритм MOEA/D (MultiobjectiveEvolutionaryAlgorithmbasedonDecomposition) [12].

          Общей идеей методов решения МКО-задачи является сужение множества  вплоть до одной или немногих точек. Построение множества Парето или его некоторой аппроксимации можно интерпретировать как часть этого пути.

Априорные методы предполагают формализацию дополнительной информации о предпочтениях ЛПР до начала решения задачи, то есть априори. Чаще всего эту информацию представляют в форме, позволяющей свести многокритериальную задачу к однокритериальной задаче оптимизации некоторой скалярной функции. Наиболее известным алгоритмом этого класса является алгоритм скалярной свертки. В данном случае указанную скалярную функцию образует, например, взвешенная сумма частных критериев (аддитивная скалярная свертка) вида (2), где  - априори назначаемые ЛПР веса частных критериев оптимальности. Недостатком аддитивной свертки является невозможность с ее помощью получить решения, принадлежащие невыпуклым частям фронта Парето МКО-задачи. Если вместо свертки вида (2) использовать известную свертку Джоффриона на основе лексикографического упорядочения [1], то этот метод можно использовать и в случае невыпуклого фронта Парето.

В силу простоты, априорные методы чаще всего использует в вычислительной практике решения МКО-задач. Недостатком этих методов является то обстоятельство, что в общем случае относительная важность частных критериев оптимальности может быть определена только в процессе многократного решения задачи (1), так что, в конечном счете, методы этого класса оказываются апостериорными.

Апостериорные методы предполагают внесение ЛПР в МКО-систему (программную систему, реализующую соответствующий апостериорный метод) дополнительной информации о своих предпочтениях в ходе решения задачи, то есть апостериори. При этом обычно дополнительную информацию, как и в априорных алгоритмах, формализуют в виде некоторой скалярной целевой функции. Примером апостериорного метода может служить известный метод последовательных уступок [11].

Адаптивные методы включают в себя некоторую совокупность итераций, каждая из которых содержит фазу анализа, выполняемого ЛПР, и фазу расчетов, выполняемых МКО-системой. По характеру информации, получаемой этой системой от ЛПР на фазе анализа, выделяют три класса адаптивных методов:

‑ методы, в которых ЛПР непосредственно назначает весовые коэффициенты частных критериальных функций;

‑ методы, в которых ЛПР накладывает ограничения на значения этих функций;

‑ методы, которые предполагают только оценку ЛПР альтернатив, предлагаемых ему МКО-системой.

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

В конечном счете, априорные, апостериорные и адаптивные методы сводят решение МКО-задачи к однокритериальной задаче глобальной (в нашем случае, дискретной) оптимизации.

Алгоритмы Парето-аппроксимации не предполагают формализации в той или иной форме дополнительной информации о предпочтениях ЛПР. Алгоритмы этого класса предполагают построение тем или иным способом аппроксимации множества и фронта Парето МКО-задачи и предъявление полученных результатов ЛПР для их неформального анализа и выбора одного из решений. В случае если полученные множества содержат большое число точек, их анализ ЛПР может быть затруднительным.

4. Адаптивный метод многокритериальной оценки релевантности

Авторы предлагают модификацию адаптивного метода PREF [13] для решения задачи многокритериальной оценки релевантности документов (1). Метод предполагает бальную оценка ЛПР альтернатив, предлагаемых ему МКО-системой.

Положим, что частные критерии оптимальности  тем или иным образом нормализованы [4], так что  для любого . Рассматриваем решение задачи (1) методом скалярной свертки. Способ свертки не фиксируем – это может быть аддитивная свертка, мультипликативная свертка, свертка Джоффриона и другие свертки [11]. Обозначим операцию свертки , где  - вектор весовых множителей,  - множество допустимых значений этого вектора.

          При каждом фиксированном векторе  метод скалярной свертки сводит решение задачи (1) к решению однокритериальной задачи глобальной условной дискретной оптимизации

, .                             (3)

В силу счетности множества  решение этой задачи существует.

          Если при каждом  решение задачи (3) единственно (а при численной реализации это всегда можно обеспечить), то это решение ставит в соответствие каждому из допустимых векторов  единственный вектор  и соответствующие значения частных критериев оптимальности . Данное обстоятельство позволяет полагать, что в этом случае функция предпочтений ЛПР  определена не на множестве , а на множестве :

.

В результате МКО-задача (1) сводится к задаче выбора вектора  такого, что

, .                                         (4)

Если используется аддитивная свертка и множество достижимости  является выпуклым, то выражение (3) задает взаимно однозначное отображение множества  на множество . При этом для любого  вектор , являющийся решением задачи (3), принадлежит множеству Парето . Если вместо аддитивной свертки используется свертка Джоффриона, то для получения того же результата не требуется выпуклость множества достижимости [11].

          Величину  считаем лингвистической переменной со значениями представленными в таблице 1, где  - ядро нечеткой переменной  [14].

Таблица 1. Допустимые значения функции предпочтений ЛПР, как лингвистической переменной

В результате МКО-задача (1) сводится к задаче отыскания вектора , обеспечивающего максимальное значение дискретной функции :

, .                           (5)

          Общая схема предлагаемого метода решения задачи (1) является итерационной и состоит из следующих основных этапов.

          Этап «разгона» метода. МКО-система некоторым образом (например, случайно) последовательно генерирует  векторов  и для каждого из этих векторов выполняет следующие действия:

1)    решает задачу дискретной глобальной оптимизации

, , ;                       (6)

          2) предъявляет ЛПР найденный документ , а также соответствующие значение всех частных критериев оптимальности ;

          3) ЛПР оценивает эти данные и вводит в МКО-систему соответствующее значение своей функции предпочтений .

          Первый этап. На основе всех имеющихся в МКО-системе значений  вектора  и соответствующих оценок функции предпочтений  МКО-система выполняет следующие действия.

          1) Строит функцию , аппроксимирующую функцию  в окрестности точек .

          2) Отыскивает максимум функции  – решает задачу

, .

          3) С найденным вектором  решает задачу вида (6) – находит соответствующий документ и значения частных критериев оптимальности, а затем предъявляет их ЛПР. ЛПР оценивает указанные данные и вводит в систему соответствующее значение своей функции предпочтений .

          Второй этап.На основе всех имеющихся в системе значений  вектора  и соответствующих оценок функции предпочтений  МКО-система выполняет аппроксимацию функции  в окрестности точек  - строит функцию  по схеме первого этапа и так далее до тех пор, пока ЛПР не примет решение о прекращении вычислений.

В работе [15] для аппроксимации функции предпочтений ЛПР предложено использовать нейронные сети, аппарат нечеткой логики, а также нейро-нечеткие системы. В современной вычислительной практике эти средства широко применяют для решения плохо формализуемых задач, к которым относится задача аппроксимации функции предпочтений.

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

‑ нейронные сети способны моделировать широкий класс функциональных зависимостей, при использовании же полиномов класс функций, как правило, должен быть задан;

‑ для нейронных сетей существует эффективный способ настройки их параметров.

Заключение

          Задача оценки релевантности документа представляет собой, по сути, задачу многокритериальной оптимизации. До настоящего времени эта задача рассматривалась как однокритериальная или как многокритериальная, но сводящаяся к многокритериальной методом аддитивной скалярной свертки. Этот метод прост в реализации, но далеко не всегда является эффективным. В частности, в общем случае этот метод не гарантирует отыскание всех паретовских точек (если фронт Парето задачи не является выпуклым). На необходимость использования иных методов решения задачи многокритериальной оценки релевантности указывалось еще в работе [10].

          В работе предложен адаптивный метод многокритериальной оценки релевантности документов, основанный на ролевой кластеризации документов в корпоративной онтологической базе знаний и аппроксимации функции предпочтений ЛПР.

          Даже однокритериальный вариант этого метода обладает высокой вычислительной сложностью и требует использования параллельных вычислительных систем.[10]. Тем более использование этих систем необходимо при реализации многокритериального варианта метода.

          Одной из проблем, которая возникает при использовании рассмотренного подхода к определению релевантности документов (как в однокритериальном, так и в многокритериальном вариантах), является проблема лексической многозначности терминов. Правильное значение многозначного слова может быть установлено только путем анализа контекста, в котором это слово упоминается. Известен ряд методов решения данной задачи, например, методы, основанные на использовании Википедии [16].

          В развитие работы планируется экспериментальная проверка эффективности предложенного подхода.

          Работа выполнена при поддержке гранта РФФИ 10-07-00222-а.

Список литературы

1. Норенков И.П. Интеллектуальные технологии на базе онтологий // Информационные технологии. 2010. № 1. С. 17-23.

2. Толчеев В.О. Методы выявления информационных признаков в задачах классификации текстовых документов // Информационные технологии. 2005. № 8. С. 14-21.

3. The Dublin Core® Metadata Initiative. Режимдоступа: http://dublincore.org/ (датаобращения 01.10.2013).

4. Карпенко А.П., Соколов Н.К. Оценка сложности семантической сети в обучающей системе // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2008. № 11. Режим доступа: http://technomag.edu.ru/doc/106658.html  (дата обращения 01.10.2013).

5. Карпенко А.П., Соколов Н.К. Расширенная семантическая сеть обучающей системы и оценка ее сложности // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2008. № 12. Режим доступа: http://technomag.edu.ru/doc/111716.html  (дата обращения 01.10.2013).

6. Галямова Е.В., Карпенко А.П., Соколов Н.К. Методика контроля понятийных знаний субъекта обучения в обучающей системе // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 2. Режим доступа: http://technomag.edu.ru/doc/115086.html  (дата обращения 01.10.2013).

7. Карпенко А.П., Соколов Н.К. Меры сложности семантической сети в обучающей системе // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2009. № 1 (74). С. 50-66.

8. Галямова Е.В., Карпенко А.П., Соколов Н.К., Ягудаев Г.Г. Контроль понятийных знаний субъекта обучения в обучающей системе // Вестник МАДИ (ГТУ). 2009. № 2 (17). С. 82-86.

9. Когаловский М.Р. Перспективные технологии информационных систем. М.: ДМК Пресс; Компания АйТи, 2003. 288 с.

10. Карпенко А.П. Оценка релевантности документов онтологической базы знаний // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 9. Режим доступа: http://technomag.edu.ru/doc/157379.html (дата обращения 01.10.2013).

11. Лотов А.В., Поспелова И.И. Многокритериальные задачи принятия решений: учеб. пособие. М.: МАКСПресс, 2008. 197 c.

12. Zhang Q., Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition // IEEE Transactions on Evolutionary Computation. 2007. Vol. 11, no. 6. P. 712-731. DOI: 10.1109/TEVC.2007.892759

13. Карпенко А.П., Мухлисуллина Д.Т., Овчинников В.А. Нейросетевая аппроксимация функции предпочтений лица, принимающего решения, в задаче многокритериальной оптимизации // Информационные технологии. 2010. № 10. С. 2-9.

14. Мухлисуллина Д.Т., Моор Д.А., Карпенко А.П. Многокритериальная оптимизация на основе нечеткой аппроксимации функции предпочтений лица, принимающего решения // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн.  2010. № 1. Режим доступа: http://technomag.edu.ru/doc/135375.html  (дата обращения 01.10.2013).

15. Карпенко А.П., Федорук В.Г. Аппроксимация функции предпочтений лица, принимающего решения, в задаче многокритериальной оптимизации. 3. Методы на основе нейронных сетей и нечеткой логики // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2008. № 4. Режим доступа: http://technomag.edu.ru/doc/86335.html (дата обращения 01.10.2013).

16. Mihalcea R. Using Wikipedia for Automatic Word Sense Disambiguation // Proceedings of the North American Chapter of the Association for Computational Linguistics (NAACL 2007). Rochester, NY, USA, April 2007. P. 196-203.