Введение к работе
Актуальность исследования. Понятие онтологии, заимствованное из философии (введено немецким философом R. Goclenius), в настоящее время активно используется в искусственном интеллекте и информатике. Все больше интеллектуальных задач, связанных с обработкой знаний, решаются с применением онтологий. В недалекой перспективе онтологии будут использоваться при решении очень многих задач.
Самым распространенным определением онтологии на данный момент является определение T.R. Gruber, согласно которому онтология является точной спецификацией концептуализации. С этой точки зрения для каждой из баз данных, или баз знаний, или систем, основанных на знаниях, или агентов знаний должны быть построены спецификации, основанные на некоторой концептуализации. Множества объектов и отношений между ними должны быть описаны в некотором словаре, в котором система, основанная на знаниях, представляет свои знания.
На сегодняшний день известен ряд зарубежных и отечественных систем (Ontolingua и Protg – разработки Стенфордского университета, OntoEdit – разработка университета Karlsruhe, OilEd – разработка Манчестерского университета, ВИКОНТ – разработка Санкт-Петербургского института высокопроизводительных вычислений и баз данных, Web-Deso – разработка Санкт-Петербургского института информатики и автоматизации РАН и др.), предназначенных для построения онтологий. В основе этих систем находятся различные формализмы описания знаний, разнообразные модели понятий и отношений, разные методы обработки знаний. В качестве формализма используется, в основном, логика предикатов первого порядка. Нередко встречаются в данной роли объектно-ориентированные сети ограничений, Description Logic, ОКВС-совместимая или RDF-совместимая фреймовая модель знаний. Понятия и отношения моделируются, как правило, в виде таксономии. Для объединения онтологий применяются методы интеграции и соединения.
К настоящему времени на основе этих и других систем созданы различные онтологии, многие из которых размещены в сети Интернет. В России к наиболее известным и качественным онтологиям можно отнести лингвистическую онтологию по естественным наукам и технологиям, многоуровневую онтологию химии, онтологию по медицинской диагностике и другие.
Анализ существующих методик и методологий построения онтологий показал, что процесс разработки онтологии включает следующие обязательные стадии: спецификации, концептуализации, формализации, объединения и реализации. Известно, что в основе концептуализации лежат некоторые категории абстракций, которые, по мнению ряда исследователей, носят субъективный характер, и каждая онтология обладает собственными категориями абстракций. Именно по этой причине разработка онтологии верхнего уровня является серьезной проблемой, решение которой пока не найдено. Все наиболее известные методологии создания онтологий объединяет то, что описание общих понятий, отношений между ними и утверждений при создании онтологии выполняется в интерактивном режиме с привлечением ручного труда экспертов. Более эффективное автоматическое построение онтологий основано на использовании методов искусственного интеллекта, способных извлекать из текста элементы знаний и нетривиально их перерабатывать.
В настоящее время методы автоматического построения онтологий развиваются недостаточно быстро, что обусловлено двумя факторами: слабым распространением систем лингвистического анализа текста, способных интерпретировать семантические отношения между словами, и относительно низкой достоверностью автоматически извлекаемых из текста утверждений и фактов, что обусловливается как несовершенством алгоритмов анализа текста, так и качеством источников информации.
Естественно, что любая научная дисциплина постепенно вырабатывает свои основные положения, понятия и средства их наименования. Результатом их анализа, состоящем в выявлении терминологии, её упорядочении, доведении до уровня, делающего эту терминологию доступной для освоения людьми, желающими приобрести соответствующие профессиональные знания, являются терминологические словари, которые и должны быть источниками знаний при формировании ядра онтологии. А извлечение знаний из научных текстов позволит расширить это ядро.
Выполненный обзор технологий, методов и средств автоматического создания онтологий актуализирует необходимость разработки методов автоматического построения онтологий.
В настоящее время достаточно широко используются технологии генетического и автоматного программирования, позволяющие максимально возможно автоматизировать процесс создания программного обеспечения. Надо отметить, что среди отечественных ученых в развитие данного направления исследований большой вклад внес А.А. Шалыто.
Таким образом, существует техническая проблема, заключающаяся в разработке технологии создания методов автоматического построения онтологий, позволяющей сформировать библиотеку методов, которую достаточно просто развивать и совершенствовать. Решение данной проблемы позволит в автоматическом режиме извлекать знания о терминах и отношениях между ними из терминологических словарей и научных текстов, что повысит эффективность построения онтологий.
Научная проблема заключается в разработке теоретических основ для решения технической проблемы. Разработка теоретических основ состоит в создании моделей и методов, необходимых для автоматического построения онтологий.
Работы исследователей в области автоматического построения онтологий частично решают научную проблему. В проекте «Система ONTOGRID для построения онтологий», выполняемая под руководством Н.Г. Загоруйко, реализованы: морфологическая база русского языка; блоки морфологического и статистического анализа; программы выделения устойчивых словосочетаний в тексте и выявления аномалий в позиционном распределении лексем по тексту, построение семантических сетей текстовых документов, которое выполняется в полуавтоматическом режиме.
Настоящая работа более близка к этой работе, так как предлагаемые методы построения онтологий основаны на естественно-языковой обработке научного текста, в которую также включены наряду с другими методами методы морфологического и статистического анализов, выделения устойчивых словосочетаний. Существенным отличием настоящей работы является разработка методов автоматического построения онтологий в виде систем продукций и применении генетического и автоматного программирования для создания требуемых моделей.
Объект исследований – естественно-языковая обработка научных текстов для построения онтологий.
Предмет исследований – методы и модели автоматического построения онтологий.
Целью работы является разработка и исследование методов и моделей автоматического построения онтологий, позволяющих ускорить процесс создания онтологий и повысить их качество.
Для достижения поставленной цели в работе решаются следующие задачи:
1. Обзор и анализ существующих решений в области автоматического построения онтологий.
2. Разработка категориального аппарата, как результата концептуализации знаний онтологий, на основе исследования языка научного текста и семиотического моделирования.
3. Разработка декларативных методов построения онтологий с использованием продукционной модели знаний.
4. Разработка и исследование модели генерации систем продукций на основе генетического программирования.
5. Разработка и исследование модели генерации преобразователя продукционных правил с применением генетического и автоматного программирования.
6. Разработка и исследование модели аппарата активации, как модуля управления продукционными знаниями, с применением генетического и автоматного программирования.
7. Апробация разработанных моделей и методов.
Основная идея диссертации. В основе автоматического построения онтологий находится естественно-языковая обработка научного текста, в большей мере связанная с методами извлечения и представления знаний. Однако такие методы невозможно построить без понимания того, какими именно знаниями необходимо оперировать. В связи с этим необходимо заранее решить, какой подход будет использован при концептуализации онтологии. Концептуализация, обеспечивая структурирование предметных знаний в рамках эксплицитной модели, предопределяет задачу построения категориального аппарата онтологии. При решении данной задачи выполняется классификация понятий и отношений между ними, которая чётко определяет семантику компонентов онтологии и возможные диагностические семантические конструкции, позволяющие в итоге извлечь знания из предложений научного текста. Компоненты онтологии и семантические конструкции, в свою очередь, оказывают значительное влияние не только на содержание методов извлечения и представления знаний, но и на принципы их построения.
Анализ трудов в области естественно-языковой обработки научного текста выявил существенное преобладание использования различных правил при решении задач в данной области. Этот факт и декларативный характер представления методов автоматического построения онтологий обуславливают применение систем продукций в качестве модели представления знаний о методе. Вместе с тем, продукционная модель имеет одно отрицательное качество, связанное с тем, что в истории использования продукций они всегда создавались экспертами. Однако известен, по крайней мере, один случай, когда правила создавались на основе генерации методами эволюционных вычислений. В связи с этим при разработке методов построения онтологий необходимо исследовать вопросы генерации систем продукционных правил на основе применения технологий генетического программирования.
Такой подход к созданию систем продукций как методов построения онтологий обуславливает решение задач, связанных с преобразованием продукционных правил в формальный вид и последующим определением их корректности. Достаточно распространенное применение симбиоза технологий генетического и автоматного программирования для создания систем со сложным поведением при решении широкого спектра задач определяет направление исследований, связанное с разработкой моделей преобразователя и аппарата активации продукций.
Таким образом, для создания методов автоматического построения онтологий необходимо разработать модель генерации систем продукций на основе применения генетического программирования, модель генерации преобразователей на основе генетического и автоматного программирования, модель генерации систем логического вывода на основе генетического и автоматного программирования и модель аппарата активации продукций на основе применения автоматного программирования. Аппарат активации может быть использован как для проверки систем продукций на корректность, так и для функционирования в реальном режиме. Предложенная технология обеспечит наиболее доступное совершенствование разработанных методов и моделей, что очень важно для новых направлений исследований, к которым относятся и исследования, связанные с созданием онтологий.
Методы исследований. Методологической и теоретической основой выполненного исследования послужили положения теории искусственного интеллекта, логики предикатов первого порядка, нечеткой логики, семиотического и ситуационного моделирования, генетического программирования, формальных грамматик и автоматов, математической лингвистики.
Для исследования понятий и отношений использованы методы анализа естественно-языковых текстов, рассмотренные в работах N.Chomsky, I.Dalberg, W. Humboldt, C.Fillmore, R.Schank, Н.Д.Арутюновой, Л.А.Беловольской, А.А.Залевской, С.Е.Никитиной, Ю.С.Степанова, В.А.Тузова и других. Построение методов извлечения и представления знаний базировалось на трудах M.Minsky, В.Н.Вагина, Е.П.Куршева, Г.С.Осипова, Д.А.Поспелова, В.Ф.Хорошевского и других. Моделирование понятий и отношений в виде сети знаков-фреймов базируется на применении аппарата семиотического моделирования как одного из наиболее приемлемых для символьной системы моделирования. Для логического вывода на ядрах классических продукций применяется эвристический метод линейной резолюции Д.Лавленда, Р.Ковальского и Д.Кюнера; для логического нечеткого вывода на ядрах нечетких продукций – метод нечеткого регулирования А.Kaufmann, E.Mamdani, L.A.Zadeh. Создание методов построения онтологии базировалось на трудах И.Л.Артемьевой, Т.А.Гавриловой, Б.В. Доброва, А.Е.Ермакова, Н.Г.Загоруйко, Ю.А.Загорулько, А.С.Клещева, Н.В.Лукашевич, А.С. Нариньяни, В.Ш. Рубашкина, А.В.Смирнова, В.Ф.Хорошевского, T.R.Gruber, N.Guarino, J.F.Sowa, M.Uschold, B.J.Wielinga и многих других. Построение моделей генераторов систем продукций и модели преобразователя основывалось на трудах М.Л.Кричевского, В.М.Курейчика, В.В.Курейчика, Л.Д.Гладкова, А.А.Шалыто, J.Holland, D.Goldberg, J.Koza, M.A.Lankhorst, S.M.Lucas, А.Naidoo и других.
Научная новизна. Научная новизна работы заключается в развитии теоретических основ проектирования и разработки технологии создания методов автоматического построения онтологий с применением генетического и автоматного программирования, что позволило автоматизировать процесс создания программного обеспечения. Данное утверждение формируется из следующих положений.
1. Новизна разработанных методов создания онтологий в виде классических и нечетких систем продукций заключается в развитии методов извлечения знаний о терминах и семантических отношениях между ними, построения семантической сети знаков-фреймов и соединения онтологий, которое состоит в уточнении представления ядра продукционного правила за счет использования простой ядерной конструкции языка ситуационного моделирования и в структуризации компонентов простой ядерной конструкции, что позволило выделить динамическую часть, содержание которой зависит от конкретного метода, и статическую часть – одинаковую для всех методов. Такой способ построения методов обеспечивает возможность их автоматической генерации.
2. Новизна предложенной модели генерации систем продукций заключается в том, что в ней с одной стороны, продукция как любое выражение представляется в виде дерева. С другой стороны, конструктивные знания эксперта, выявленные на основе анализа научного текста и разработанных методов, формализованы в виде конструкций и тоже представлены деревьями. Это определило структуру хромосомы и Fitness-функцию, что позволило применить генетическое программирование для генерации систем продукций. Разработанный генетический алгоритм обладает свойством универсальности по отношению к методу, настраиваясь на него посредством спецификации метода, содержащей конструктивные знания эксперта.
3. Новизна предложенной модели генерации преобразователя продукционных правил состоит в том, что она позволяет порождать модели конечных преобразователей, способных отображать классические и нечеткие продукции, представленные на ограниченном подмножестве естественного языка, в формулы логики предикатов, а их, в свою очередь, во множества дизъюнктов. Особенностью модели генератора является то, что порожденный преобразователь может переводить символы входного алфавита в символы выходного алфавита без явного задания грамматики перевода. Грамматики перевода определяются неявно посредством задания исходных объектов, описанных в символах входного алфавита, и эталонных объектов, описанных в символах выходного алфавита. Достижению такой универсальности генетического алгоритма в рамках класса задач преобразования с неявно заданной грамматикой способствовали направленный поиск и ряд генетических операторов, типовых по выполняемому действию. Кроме того, для получения кода конечных преобразователей применены технологии автоматного программирования.
4. Новизна разработанной автоматной модели аппарата активации состоит в том, что следование единообразию представления методов в виде классических и нечетких продукций определило необходимость реализации нечеткого логического вывода на основе применения методов нечеткого регулирования, которые хорошо вписались в предложенную технологию. Это позволяет разрешать конфликтные ситуации, возникающие при использовании классического логического вывода, а также решать задачи в условиях неопределенности. Реализация аппарата активации выполнена на основе применения технологий генетического и автоматного программирования.
Значение для теории. Разработанные модели и методы построения онтологий составляют теоретическую основу для разработки технологий автоматизированного решения различных задач, для которых в качестве моделей решения можно использовать системы продукций. Кроме этого, появилась возможность дальнейшего их развития с точки зрения объективизации категориального аппарата, уточнения множества типов предикатов, типов семантических отношений и исследования их свойств, необходимых для анализа онтологий.
Значение для практики. Разработка онтологий по предложенной технологии позволит облегчить процесс их создания, повысить доверие к хранилищам знаний и информации, снизить издержки на разработку программного обеспечения, обеспечить дальнейшее развитие информационных и интеллектуальных технологий. Кроме того, результаты, полученные в работе, окажут положительное влияние на конгломерацию частных онтологий в систему знаний, поскольку в настоящее время средств, позволяющих создать полную систему знаний («модель мира»), не существует.
Достоверность полученных результатов. Достоверность результатов и выводов работы подтверждается корректным использованием теоретических и экспериментальных методов обоснования полученных результатов и выводов. Положения теории основываются на известных достижениях фундаментальных и прикладных научных дисциплин в области инженерии знаний, классического и нечеткого логического вывода, генетического и автоматного программирования. Достоверность выводов и результатов подтверждается также их исследованием на конкретных задачах естественно-языковой обработки научного текста. Сопоставление полученных результатов показывает их согласованность с теоретическими выводами. Научная новизна технических решений подтверждена авторскими свидетельствами.
Личный вклад автора. Все основные результаты диссертации получены лично автором.
Рекомендации по использовании результатов диссертации. Результаты работы могут быть использованы при разработке системы автоматического построения онтологий. Программные средства, разработанные в процессе диссертационного исследования, составляют основные компоненты технологии, позволяющие проводить экспериментальные исследования генерируемых методов.
Апробация результатов диссертации. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийской научно-практической конференции «Управление созданием и развитием систем, сетей и устройств телекоммуникаций» (г.Санкт-Петербург, 2008 г.); Всероссийской научно-технической конференции «Информационные системы и модели в научных исследованиях, промышленности и экологии» (г.Тула, 2007 г.); Второй Международной конференции по когнитивной науке «The Second Conference on Cognitive Science» (г.Санкт-Петербург, 2006 г.); Международной научной конференции «Information Technologies and Telecommunications in Education and Science (IT@I ES’2005)» (г.Москва, 2005 г.); Общероссийском постоянно действующем семинаре «Интернет-порталы. Содержание и технологии» (г.Москва, 2005 г.), девятой Всероссийской научно-практической конференции «Проблемы информатизации региона» (г.Красноярск, 2005 г.); Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» (г.Улан-Удэ, 2000-2008 гг.); Всероссийской научно-технической конференции «Проблемы качества, безопасности и диагностики в условиях информационного общества» (г.Сочи, 2004 г.); Всероссийской научно-практической конференции-выставке «Единая образовательная информационная среда: Проблемы и пути развития» (г.Омск, 2004 г.); Всероссийской научно-практической конференции «Российская школа и Интернет» (г. Санкт-Петербург, 2002 г.); Международной научно-технической конференции «Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и СИИ» (г.Вологда, 2001 г.); Третьей Международной выставке-конференции «Информационные технологии и телекоммуникации в образовании» (г.Москва, 2001 г.); Международном семинаре «Искусственный интеллект в образовании» (г.Казань, 1996 г.) и другие.
Кроме того, результаты исследования вошли в материалы отчетов по госбюджетным научно-исследовательским работам «Теоретические и прикладные вопросы разработки интегрированных интеллектуальных информационных систем» (ГР № 01.200.205060; Инв. № 02.200305099, 2002 г.), «Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL-запросы» (ГР № 01.200.205060; Инв. № 0320.0501291, 2004 г.), «Модель МП-процессора, выполняющего преобразование естественно-языкового представления ядра продукции в формулу логики предикатов» (ГР № 01.200.205060; Инв. №0320.0603814, 2005 г.) и «Исследование проблем моделирования знаний и разработка методологии создания онтологий со встроенной семантикой и прагматикой» (ГР №01.2006.10552; Инв. №03200802713, 2007 г.), по научно-исследовательской работе: «Разработка генератора автоматов, основанного на использовании генетических алгоритмов», шифр «2007-4-1.4-18-01-037» (ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы», ГК № 02.514.11.4047 от 18.05.2007 г.).
Материалы диссертационных исследований используются в Московском авиационном институте при решении задачи ускорения процесса синтеза алгоритмов бортовых экспертных систем аэрокосмических летательных аппаратов; в Тверском государственном техническом университете при исследовании лингвистической семантики и прагматики в виде методов извлечений знаний и построения семантических сетей знаков-фреймов научного текста; в учебной и научной деятельностях Восточно-Сибирского государственного технологического университета и включены в программы учебных дисциплин «Системы искусственного интеллекта», «Теория искусственных нейронных сетей», «Теория вычислительных процессов и структур» специальности 010503 «Математическое обеспечение и администрирование информационных систем» в виде методических указаний.
Публикации. По теме диссертации опубликованы 73 работы, из них: 4 – монографии; 9 – статьи в изданиях по списку ВАК; 12 – статьи в сборниках; 48 – работы, опубликованные в материалах всесоюзных, всероссийских и международных конференций и симпозиумов. Автором получены 7 свидетельств об официальной регистрации программ для ЭВМ, разработанных в рамках тематики работы.
Содержание разделов диссертации. Диссертация состоит из введения, 5 разделов, заключения, списка использованных источников, содержащего 280 наименований, 10 приложений. Основная часть работы содержит 288 страниц, включая 34 рисунка, 14 таблиц.
В первом разделе приведены обзор и анализ существующих решений, приводится описание проблемы.
Второй раздел посвящен разработке категориального аппарата онтологий. Анализ работ по лингвистике, семиотике и информатике, касающихся построения терминологии области науки, показал, что качественная терминосистема является отражением структуры области науки. Это базируется на основном свойстве термина – системности, являющимся отраженным признаком системности знания, элементом которого и есть термин, то есть термин представляет собой фрагмент общего смыслового единства системы.
Структура терминосистемы должна определять связи терминов, переходы внутри общей совокупности терминов, описывать семантику, синтактику и прагматику отдельных терминов. Это означает, что схема знака-термина должна учитывать свойства термина как логоса и как лексиса, то есть интегрировать в себе логико-семантические и языковые свойства термина. Среди существующих схем знаков наиболее адекватной схемой знака является квадрат Д.А. Поспелова, содержащий метазнак и отображающий три основных аспекта знака, а именно имя знака, содержание знака, назначение знака. Однако по С.Е. Никитиной, термин, как знак специальной семиотической системы, должен обладать номинативно-дефинитивной функцией и внутренней формой. Учитывая это, на основе квадрата Поспелова и в соответствии с глобальной классификацией категорий объектов и отношений
И.Дальберг разработано шесть конструкций знака: понятие, свойство, действие, состояние, событие, величины. Глобальные классификации И. Дальберг представляют собой некоторые априорные схемы научного знания, которые могут накладываться на конкретную терминологию. Классификации показывают, как в семантической структуре организуется и воплощается знание терминологии. Поэтому связи между компонентами знака классифицированы в соответствии с глобальной классификацией отношений. Структурированность знака позволяет более четко описывать понятия и понимать лучше не только их содержание, но и какие знания о термине необходимо извлекать из научных текстов.
Автоматическое извлечение знаний из научных текстов предполагает не только выявление терминов, но и извлечение знаний о них. Для этого необходимо распознать в тексте семантические отношения между терминами, так как именно они задают семантическую структуру терминологии. В связи с этим в работе построена иерархия семантических отношений на основе классификации концептуальных отношений (табл. 1). Значимым признаком построения предложенной иерархии является принадлежность отношений понятийным сферам. Группировка отношений по понятийным сферам (уровням абстракции) дает возможность более четко описать семантику каждого отношения. Кроме того, такой подход позволяет в значительной степени уменьшить мощность множества типов предикатов, что является весьма важным фактором повышения эффективности резолютивного логического вывода.
Таблица 1. Иерархия отношений между терминами
Сфера абстрактного – конкретного
Отношения агрегации
Сфера
принадлежности
Функциональные отношения
Объект действия–действие–
субъект действия
Причина–следствие
Условие–действие
Событие–действие
Состояние–действие
Событие–состояние
Инструмент–действие
Данные–действие
Данные–величины
Сфера
процессуальности
Семиотические отношения
Сфера
формы и содержания
Сфера тождества и противопоставления
На рисунке 1 представлено концептуальное знание о термине. Роль знака играет термин t, изображенный на графе в одноименной вершине. Вершина T определяет множество терминов T, имеющих отношение с термином t. Если сравнить данную конструкцию с квадратом Поспелова, то вершине «знак» квадрата соответствует вершина t, вершине «смысл знака» – вершины D, C, P, S и T, вершине «действия, связанные со знаком» – вершина A, а вершине «метазнак» – вершина М. Дуги графа соответствуют концептуальным отношениям. Для отражения прагматического аспекта термина в конструкцию знака введена вершина A, и так как знания о прагматике несколько отличаются от знаний об объекте, то для них разрабатываются отдельные конструкции, необходимые для представления знаний о действиях, связанных с объектом.
Рис. 1. Графическая интерпретация знака “Понятие”: t – термин; QR1 – квалитативные отношения; QR2 – квантитативные отношения, – отношение включения
Таким образом, предложенный подход построения конструкций знака концептуальных объектов, как основных категорий абстракций, позволяет создать единую концептуализацию предметной области, которую смогут понимать различные системы. Единая концептуализация необходима для формирования терминосистемы, являющейся ядром онтологии предметной области. Терминосистема может служить одновременно лексикой информационно-поискового языка. С этой позиции она должна представляться в виде тезауруса. В работе разработана структура словарных статей тезауруса на основе конструкций знака для выбранных категорий концептуальных объектов. Для примера приведем словарную статью «Понятие», соответствующую конструкции знака, показанной на рис. 1, и имеющую вид:
Concept = <t, D, P, A, C, S, T, M>, (1)
где t. t=<t1, t2, t3>: t1 – имя термина; t2 – тип концептуального объекта «Понятие»;
t3 – вид сущности: материальный, нематериальный.
D. D = {di| di – субстанциальная дефиниция, i=1n, n – число дефиниций}.
P. P = {(p1, p2)i | p1 – имя свойства; p2 – ссылка на словарную статью, описывающую p1; i – число свойств понятия}.
A. A = {(a1, a2)i | а1 – действие; а2 – ссылка на словарную статью, описывающую а1 как термин; i=1n, n – число действий, релевантных термину}.
C. Множество терминов, имеющих квантитативные отношения с термином t, описывается двойкой <C1, C2>, где C1 ={(c11, c12)i | c11 – синоним; c12 – ссылка на словарную статью, описывающую c11 как термин; i=1k, k – количество синонимов}, а С2 ={(c21, c22)i | с21 – коррелят; c22 – ссылка на словарную статью, описывающую c21 как термин; i=1m, m – число коррелятов}.
S. S = {(s1, s2)i | s1 – имя термина, описывающего состояние сущности, s2 – ссылка на словарную статью, описывающую термин s1, i=1n, n=|S|}.
T. Множество понятий (терминов), имеющих квалитативные отношения с термином t, описывается четверкой < T1, T2, T3, T4>, где
T1 – понятия, составляющие родовидовые отношения с t,
T1 = <T11, T12>, где T11 – множество понятий, являющихся родом t; T12 – множество понятий, являющихся видом t; элементами множеств T11 и T12 являются двойки, компоненты двойки – это имя понятия и ссылка на словарную статью, описывающую это понятие;
T2 – понятия, составляющие отношение «целое–часть» с t;
T2 = <T21, T22>, где T21 – множество понятий, являющихся целым для t;
T22 – множество понятий, являющихся частью t; элементами множеств T21 и T22 являются двойки, компоненты двойки – это имя понятия и ссылка на словарную статью, описывающую это понятие;
T3 = <t31, t32>, где t31 – термин, обозначающий способ представления термина t, t32 – ссылка на словарную статью, описывающую t31 как термин;
T4 = <t41, t42>, где t41 – термин, обозначающий способ выражения термина t, t42 – ссылка на словарную статью, описывающую t41 как термин.
M. С помощью данного элемента определяются отношения между знаковыми системами. Он описывается двойкой <М1, М2>, где
М1 – способ метаязыкового представления, который позволяет зафиксировать связь термина и его представления в метаязыке;
М2 – термин другого языка, который позволяет зафиксировать связь терминов различных предметных областей.
Словарная статья «Понятие» является центральной. При описании термина посредством элементов P, A и S устанавливается связь со словарными статьями, описывающими свойства, действия и состояния, через элементы С и T – различные связи с другими терминами. Элемент M позволяет определить отношения с терминами смежной предметной области.
Структура словарных статей тезауруса позволила определить структуру прототипов знаков-фреймов, являющихся узлами семантической сети таксономии.
Следует отметить, что совокупность разработанных схем знаков для выбранных категорий глобальных объектов (понятие, свойство, действие, состояние, событие, величины) согласуется с соглашением, принятым в области искусственного интеллекта, и связанным с моделями представления знаний. Соглашение заключается в том, что в реальном мире есть объекты, которые могут состоять из частей. У объектов есть свойства, которые имеют значения. Объекты могут находиться в различных отношениях друг с другом. Свойства и отношения изменяются во времени. В различные моменты времени возникают события, активизирующие процессы, в которых участвуют объекты и которые также изменяются во времени. События могут вызывать другие события, то есть давать эффект. Мир и его объекты могут находиться в различных состояниях.
Разработав концептуализацию онтологии и поняв, что требуется извлекать из научных текстов, необходимо определить механизм извлечения знаний. На основе трудов K.I. Lewis, L. Wittgenstein, Д.А. Попелова, Г.С. Осипова, В.Н. Вагина, А.А. Залевской в работе обосновано, что лучшим подходом для извлечения знаний является ситуационный подход. Действительно, возможными ситуациями являются тот или иной предпорядок компонентов. Поэтому, выполняя морфологический или синтаксический анализ, извлекая знания о терминах из терминологических словарей или применяя другие методы анализа текста, мы всегда исследуем ситуации, в которых находятся морфемы в лексеме, лексемы – в предложении, предложения – в тексте. Методы естественно-языковой обработки текста почти всегда направлены на анализ ситуационного контекста, и в зависимости от метода объектом этого анализа является либо текст, либо предложение текста, либо лексема предложения. Из этого следует, что для решения различных задач естественно-языковой обработки научного текста необходимо разработать методы их решения, основываясь на ситуационном моделировании. В основе языка ситуационного моделирования лежит простая ядерная конструкция k=xRy, где x, y – термины, R – отношение между ними. В свою очередь, конструкция k имеет вид посылки ядра продукции. Поэтому в качестве модели представления знаний о методах избраны системы продукций, которые обладают простотой, модульностью, возможностью постепенного наращивания и модификации.
Таким образом, с целью концептуализации знаний онтологий, на основе исследования языка научного текста и семиотического моделирования:
– определены шесть категорий понятий на основе глобальных классификаций объектов И. Дальберг и соглашения, принятого в искусственном интеллекте; построены схемы знаков категорий понятий. Разработанные схемы знаков в отличие от существующих знаков понятий обладают лучшей структурированностью, что способствует более точному описанию понятий и отношений между ними и, как следствие, лучшему их пониманию людьми и машинами;
– построена иерархия семантических отношений на основе глобальных классификаций отношений И. Дальберг;
– разработана структура словарных статей тезауруса на основе схем знаков глобальных объектов, что позволило определить состав и структуру слотов протофреймов, образующих фундамент модели представления онтологии в виде семантической сети знаков-фреймов;
– определены типы предикатов как ядер продукционных правил на основе выявленных категорий семантических отношений.
В третьем разделе рассмотрены методы естественно-языкового (ЕЯ) анализа научного текста. Все методы условно разделены на две группы. К первой отнесены традиционные методы ЕЯ-обработки текста, ко второй – методы, касающиеся непосредственно построения онтологии. В работе рассмотрена обобщенная схема анализа научного текста, в соответствии с которой построены системы продукций для методов морфологического и синтаксического анализов, метода выделения именных субстантивных словосочетаний. Для построения онтологии эта схема модифицирована. В ней появились методы второй группы. Классические системы продукций построены для создания семантических сетей знаков-фреймов терминосистемы и номенклатуры, нечеткие – для соединения онтологий. В качестве примера рассмотрим извлечение знаний об отношении тождества категории квантитативных отношений.
Отношение тождества. В некоторых словарях синонимы термина не указываются явно и могут быть выявлены только в результате анализа текста словарной статьи, например: «Авизо (итал. avviso, англ, advice – сообщение, уведомление) – извещение, посылаемое одним контрагентом другому …». Здесь синонимом заголовочного термина является перевод аналога термина на иностранном языке. Наиболее распространенной является ситуация, когда синонимы заголовочного термина следуют за терм-признаком «Син.:». Пример: «Акция – осуществляемое по заранее разработанному плану масштабное действие, син.: деяние, действие». Тогда продукционное правило, распознающее синоним термина в этой ситуации имеет вид:
ЕСЛИ
<предложение> p содержит <термин> z И
<предложение> p содержит <список> q И
<список> q содержит <ЭлементСписка> e И
<предложение> p содержит <признак> h И
<признак> h имеет <значение> ["син.:"] И
<признак> h имеет <индекс> i И
<список> q имеет <индекс> (i+1)
<ЭлементСписка> e имеет <тип> ["синоним"].
Постдействием данной продукционного правила является выделение списка терминов, следующего за указанным в продукции признаком.
Формирование соответствующих слотов семантической сети знаков-фреймов осуществляется следующим образом. После активации продукции найденные синонимы "деяние" и "действие" выделяются и присваиваются атрибуту «VALUE» соответствующих слотов с элементом NAME="namesyn" экзофрейма Фi, релевантного термину «акция»:
.
Далее производится поиск терминов-синонимов во множестве фреймов Ф. Если экзофреймы ФСi и ФСj, описывающие данные термины, найдены, то в соответствующих слотах с атрибутом NAME="link" атрибуту FILE="Frame_#.xml" присваиваются ссылки на ФСi и ФСj (полный путь к файлу, символ # в имени файла Frame_#.xml обозначает порядковый номер файла). В противном случае создаются фреймы, релевантные терминам "деяние" и "действие", и после этого ссылки на них записываются в соответствующие слоты.
Система продукций, предназначенная для распознавания синонимов, должна содержать правила, анализирующие все возможные ситуации определения синонима в словарной статье терминологического словаря.
Продукции методов, представленных в данном разделе, были созданы в соответствии с результатами, полученными во втором разделе. Посылки антецедента и заключение консеквента каждого продукционного правила имеют вид простой ядерной конструкции языка ситуационного моделирования и соответствуют типам отношений, определенным в табл. 1. На примере методов извлечения знаний о различных компонентах конструкций знаков показан процесс заполнения словарных статей и построения узлов семантической сети знаков-фреймов.
При построении онтологии предметной области вначале создается терминосистема, а затем – номенклатура. Поэтому при создании номенклатуры используется терминосистема, в которой уже определены все основные термины предметной области. Присоединение номенклатуры к терминосистеме может осуществляться как в процессе, так и после её создания.
Для метода соединения онтологий должны быть построены помимо классических продукций и нечеткие. Рассмотрим процесс построения нечетких продукций. При создании терминосистемы и номенклатуры заполняется их заголовок, который включает имя предметной области для терминосистемы и имя области знаний для номенклатуры. Присоединение вновь создаваемой номенклатуры NS к существующей терминосистеме ТS той же предметной области выполняется в процессе представления нового термина.
По каждому новому термину tkNS TermNS, где TermNS – множество терминов номенклатуры NS, должен выполняться поиск по образцу данного термина в терминосистеме ТS. Пусть имеем два образца tiТS и tkNS, соответствующие имени термина в терминосистеме ТS и номенклатуре NS:
где z1 – имя термина, z2 – тип термина, z3 – вид сущности, хij – значение tiTS для терминосистемы, ykj – значения tkNS для номенклатуры.
Если соответствующие хij и ykj равны, то термину tkNS соответствует термин tiTS TermTS, где TermTS – множество терминов терминосистемы ТS.
Однако возможны случаи, когда в образце tkNS неизвестны значения yk2 и/или yk3, так как в научном тексте информация о термине может быть неполной. Тогда, если хi1 = yk1, будем считать, что термину tkNS соответствует термин tiTSTermTS. Если термин найден, то в соответствующую вершину семантической сети G или слота знака-фрейма F записывается ссылка на термин tiTS терминосистемы. Кроме того, необходимо добавить записи в заголовки терминосистемы и номенклатуры.
Вполне возможно, что термин номенклатуры имеет имя, не совпадающее с именем термина в терминосистеме, но, по сути, они являются квазисинонимами. Поэтому после создания номенклатуры необходимо выполнить сравнение интенсионалов терминов номенклатуры и терминосистемы.
Интенсионал термина типа «Понятие» определяется кортежем (1). Так как элементами вектора Т являются, в основном, множества, то анализ проводится по каждому элементу отдельно, причем существенными считаются множества Pr, Tj. Нельзя сказать, что множества C, М и A не существенны. Однако, как правило, в научном тексте рассматриваются отдельные стороны термина, касающиеся какой-либо проблемы, поэтому для номенклатуры можно допустить, что эти множества не существенны.
Для анализа интенсионалов используем отношение сравнения элементов вектора Т, которое рассмотрим для каждой пары терминов (ti, tj), такой, что tiTS TermTS, tjNS TermNS. Обозначим символом Х множества вектора TermTS, а Y – множества вектора TermNS, то есть при рассмотрении элемента «Свойства» вектора Т Х= PriTS, а Y=PrjNS, где PriTS= {pri1TS, …, prinTS} задает свойства термина tiTTermTS, а множество PrjNS= {prj1NS, …, prjnNS } задает свойства термина tiNS TermNS.
При анализе множеств TjTS и TjNS отношение сравнения должно применяться для множеств терминов, связанных родовидовым отношением и отношением «Целое – часть». При этом последовательно должны сравниваться множества родовых терминов, видовых терминов, терминов-целое, терминов-часть. Из этого следует, что в сравнении участвуют: множество свойств; множество терминов-род; множество терминов-вид; множество терминов-целое; множество терминов-часть.
Отношение сравнения множеств. Сравнение множеств X и Y будем осуществлять следующими отношениями: YХ, Y=Х, YХ, YХ, YХ.
Если для любых X и Y отношение неравенства существует, то следует, что термины tiTS и tjNS разные, и дополнительных действий не требуется, то есть номенклатура остается в той же конфигурации.
Если для любых X и Y отношение равенства существует, то это означает, что термины идентичны. В этом случае в знаке-фрейме FNS, соответствующем данному термину в номенклатуре NS, необходимо удалить всю информацию кроме заголовочной. В заголовочную часть нужно добавить ссылку на знак-фрейм FTS. Тогда в знаке-фрейме FNS остается только имя термина tjNS и ссылка на tiTS. В том случае, если имена терминов не совпали, а для остальных множеств существует отношение равенства, то из этого следует, что термин tjNS является синонимом tiTS, и во множество синонимов терминосистемы нужно включить имя термина и ссылку на него.
Если для любых X и Y отношение включения YХ истинно, то это означает, что рассматриваемый термин tjNS наследует все свойства термина tiTS. Из этого следует, что в знаке-фрейме FNS, соответствующем данному термину в номенклатуре NT, необходимо удалить всю информацию кроме заголовочной. В заголовочную часть добавляется ссылка на знак-фрейм FTS.
Если для любых X и Y отношение включения YХ истинно, то это означает, что рассматриваемый термин tjNS обладает более полным описанием, чем термин tiTS, и его знак-фрейм FST необходимо дополнить недостающей информацией из знака-фрейма FNS, затем удалить всю информацию из знака-фрейма FNS кроме заголовочной. В заголовочную часть добавляется ссылка на знак-фрейм FTS.
Надо отметить, что вероятность существования отношений равенства и включения на множествах X и Y невелика. Наиболее частым является случай, когда истинно отношение YХ. Для его анализа лучше всего использовать аппарат нечеткой логики, который позволяет рассматривать различные ситуации, например: часть свойств совпала в основном, и мощность конечного множества пересечения родовых понятий большая, мощность конечного множества пересечения видовых понятий небольшая, а мощности множеств пересечения других множеств ничтожно малы, то можно сказать, что термин tiTS в научном тексте рассматривается под другим углом. Этой ситуации, скорее всего, соответствует вывод, что в номенклатуре определен новый вид tjNS как отображение термина tiTS.
Таким образом, проекция терминосистемы TS на плоскость рассматриваемого научного текста в виде номенклатуры NS позволяет уточнять термины терминосистемы, определять новые виды терминов, новые компоненты терминов, то есть уточнять терминологию предметной области.
Для реализации анализа отношения YХ хорошо подходят методы нечеткого регулирования. Рассмотрим основные аспекты их применения.
Отношение YlХl, l=15, может быть истинно для "(Yl, "Хl,), где индекс l последовательно нумерует множества в следующем порядке: свойств, терминов-род; терминов-вид; терминов-целое; терминов-часть. На практике могут встречаться различные комбинации истинности отношения YlХl. Двумя наиболее интересными являются случаи, когда отношение YlХl истинно при l {1,2,3} и l {1,4,5}. Рассмотрим только первый случай.
Для нечеткого логического вывода анализа отношения YХ применим известный метод нечеткого регулирования Mamdani. Основные компоненты нечеткого вывода рассмотрим на примере определения степени достоверности того, что термин tjNS является новым видом термина ti-1TS.
Основой для проведения операции нечеткого логического вывода является база правил, содержащая нечеткие высказывания в форме "Если-то" и функции принадлежности для соответствующих лингвистических термов. Здесь рассмотрим только ядра правил для определения степени достоверности новизны термина tjNS относительно термина ti-1TS.
Условие ядра (A): составное нечеткое высказывание вида
«ISi = t И DTISi = t И DNISi = t», где индекс i{1,2,3} последовательно нумерует: множества свойств, множества родовых терминов, множества видовых терминов;
ISi – обозначения входных лингвистических переменных InterSection, соответствующих мощностям множеств YlХl;
DTISi – обозначения входных лингвистических переменных DifferenceTSInterSection, соответствующих мощностям множеств Хl/( YlХl);
DNISi – обозначения входных лингвистических переменных DifferenceNSInterSection, соответствующих мощностям множеств Yl/( YlХl);
терм t Т1 = {Низкая (Little), Средняя (Mean), Высокая (Big)}.
Заключение ядра (B): нечеткое высказывание вида «H_NKTi = Dt», где
H_NKT – обозначение выходной лингвистической переменной степень различия характеристик термина;
терм t Т2 и Т2 = {Низкая (Low), Средняя (Normal), Высокая (High)}, модификатор DM1 и M1 = {Ниже (Down), Выше (Up)}.
Так как условие ядра нечетких множеств лингвистических переменных включает три переменные, и каждое правило использует каждую из переменных в посылке, то было построено m=33=27 последовательностей длины три из переменных ISi, DTISi, DNISi. Анализ построенных правил показал, что не все правила могут быть использованы для проведения операции нечеткого логического вывода. Это объясняется тем, что некоторые наборы значений входных лингвистических переменных не имеют смысла в разрезе решаемой задачи. Поэтому из рассмотрения были исключены шесть правил. Таким образом, база правил содержит нечеткие правила Ri, где i=1m, m= 21 и является полной. На рис. 2 показан фрагмент базы правил:
Рис. 2. Фрагмент базы правил определения степени различия свойств терминов
Более подробное описание использования метода нечеткого регулирования Mamdani приведено в работе. Результатом нечеткого логического вывода по рассмотренной базе правил является числовое значение выходной переменной «степень достоверности новизны термина». В зависимости от полученного значения выполняются те или иные действия.
Методы построения семантических сетей терминосистемы и номенклатуры демонстрируют возможность первичного анализа понятий семантической сети в процессе её создания на основе сравнения их интенсионалов и применения метода поиска по образцу. Для этого выполняется анализ теоретико-множественных отношений между соответствующими компонентами-множествами сравниваемых терминов. Размытый характер мощности множества пересечения этих компонентов обусловил использование нечеткого логического вывода. В работе показан способ введения нечеткости и возможности применения методов нечеткого регулирования.
Кроме этого, методы нечеткого регулирования используются для разрешения конфликтного множества решений, которое иногда может иметь место в различных задачах ЕЯ-обработки научного текста. Данные методы, основанные на использовании систем нечетких продукций, обеспечивают единство подходов в представлении и обработке методов построения онтологий.
Таким образом, в данном разделе разработаны и исследованы декларативные методы построения онтологий:
– показано, что методы естественно-языковой обработки научного текста, являющиеся базой для методов построения онтологий, могут быть представлены в виде классических систем продукций. Для разрешения возможных конфликтных ситуаций предложено использовать нечеткие продукционные правила;
– разработаны методы построения понятийного базиса онтологии в виде семантических сетей знаков-фреймов, представляющих собой терминосистему;
– предложен метод соединения онтологий с применением аппарата нечеткого регулирования. Метод обеспечивает соединение онтологий, создаваемых из нескольких терминологических словарей путем анализа интенсионалов понятий, позволяя получить объективную терминосистему, а также соединение терминосистемы с номенклатурой, построенной на основе извлечения знаний из научных текстов. Главное достоинство этого метода заключается в том, что он позволяет строить иерархию онтологий по предметной области.
В четвертом разделе рассмотрена предложенная модель генерации систем продукций, которая описывается кортежем: MGSP = <KC, GASP>, где
KC – компонент «Конструктивные знания эксперта», GASP – компонент «Генетический алгоритм».
Компонент «Конструктивные знания эксперта». Каждая система продукций представляет собой модель решения (метод) некоторой прикладной задачи, например, задачи выделения словосочетаний или распознавания некоторого семантического отношения. Генератор (генетический алгоритм) должен настраиваться на прикладную задачу посредством заранее сформированной спецификации её предметной области. Спецификация формируется на основе конструктивных знаний эксперта – знаний о наборах возможных структур объектов и взаимодействии между их частями. Используем упрощенную модель предметной области: МSA = <Tk, Kk>, где Tk – множество понятий; Kk – кортеж, описывающий множество конструктов и их взаимосвязи. В решаемой задаче компонентами кортежа Kk являются множество конструктов Kkc, семейство множеств допустимых значений элементов конструктов Kkv, множество графов Kkg, определяющих допустимые взаимосвязи конструктов.
Рассмотрим создание модели МSA на примере метода извлечения знаний из терминологических словарей о квалитативном отношении «Целое – часть». Прежде всего определим понятийное множество Tk метода, которое включает следующие понятия: предложение р, композиционное словосочетание (КСС) k, именное субстантивное словосочетание (ИСС) s, семантическое отношение (СемОтношение) r, заголовочный термин z, термин t, лексема l, список q, элемент списка (ЭлСписка) e, глагол v, терм-спутникR tr, терм-спутникX tx, терм-спутникY ty, признак h, характеристика x, часть речи c1 (ЧастьРечи), падеж c2, значение.
В работе введена модель рассуждения эксперта: в каждом методе есть объект исследования; объект исследования содержит некоторые компоненты; компоненты, в свою очередь, могут включать в себя другие компоненты; все компоненты могут иметь характеристики; характеристики являются некоторыми свойствами; свойства имеют некоторые значения, тогда в зависимости от ситуации, которая определяется значениями характеристик и взаимным расположением компонентов (предпорядком), можно распознать в объекте анализа искомый элемент схемы знака.
В рассматриваемом методе объектом исследования является предложение, а искомым элементом схемы знака – семантическое отношение «Целое-часть». Сформированное множество конструктов Kkc как множество отношений Ri имеет вид:
Kkc={Ri| Ri={(x,y)| xХ; yY; ХY}; i=1n}, (2)
где Х, Y – множества понятий, используемых в методе.
Для рассматриваемого метода n=10. Тогда в общем виде множество Kkc составляют следующие отношения:
R1={(x,y)| x содержит y, x{Предложение}, yA};
R2={(x,y)| x содержит y, xВ, yC};
R3={(x,y)| x содержит y, x{ИСС}, yD};
R4={(x,y)| x содержит y, x{СемОтношение}, yE};
R5={(x,y)| x имеет y, xF, y{Характеристика}};
R6={(x,y)| x есть y, x{Характеристика}, yG};
R7={(x,y)| x есть y, x{ЭлементСписка}, yH};
R8={(x,y)| x имеет y, xI, y{Значение}};
R9={(x,y)| x имеет y, xA, y{Индекс}}.
R10={(x,y)| x эквивалентен х, xJ}}.
Каждый метод имеет собственное семейство множеств конструктов Kkc, которое должно быть конкретизировано. Для конкретизации отношения Ri представлены в виде xRiy. Тогда для рассматриваемого метода при А = {КСС, ИСС, СемОтношение, термин, лексема, список} первое отношение имеет вид:
R1={<Предложение> содержит <КСС>,
<Предложение> содержит <ИСС>,
<Предложение> содержит <СемОтношение>,
<Предложение> содержит <Термин>,
<Предложение> содержит <Лексема>,
<Предложение> содержит <Список>}.
Первые четыре множества конструктов с R1 по R4 отражают возможную иерархическую структуру понятий предметной области. Пятый конструкт позволяет задать характеристики понятий, если таковые имеются. Для данного метода важны характеристики следующих понятий F = {ИСС, Термин, Лексема, ЭлементСписка, Терм-спутникХ, Терм-спутникY}. Следующий конструкт уточняет значение характеристики как категории посредством отношения “IS-A”, G = {Падеж, ЧастьРечи}. Седьмой конструкт также уточняет значение понятия «Элемент списка» как категории, Н = {ИСС, Термин, Лексема}. Восьмой конструкт необходим для задания конкретных значений характеристикам понятий и некоторым вспомогательным понятиям, I = {Глагол, Терм-спутникR, Терм-спутникХ, Терм-спутникY, Признак, ЧастьРечи, Падеж}. Для определения местоположения компонентов в предложении используется девятый конструкт, задающий положение основных понятий в предложении посредством индекса. В данном конструкте в качестве левой части используются компоненты множества А. Последний конструкт связан с введением отношения тождества, которое в данном методе необходимо для проверки значений характеристик, J={Падеж, ЧастьРечи, Индекс}.
Таким образом, создается некоторая иерархическая организация, которая хорошо согласуется с теоретическими основаниями когнитивной психологии. Согласно ей при мышлении используются не языковые конструкции как таковые, а их коды в форме некоторых абстракций, которые образуют иерархические структуры.
Пример взаимосвязи конструктов представлен на рис. 3. В корне графа всегда находится объект исследования. Вершины первого уровня графа содержат основные компоненты предложения. Верхние дуги графа в основном помечены глаголом «содержит», что показывает иерархическую вложенность понятий. Листья графа содержат константные значения или индекс. Из анализа существующих продукций, разработанных для данного метода, было выявлено, что первый уровень вершин V1 графа могут составлять множество из одиннадцати альтернативных наборов компонентов: V1= {(k, r, q|s|l), (s, r, q|s|l), (z, r, q|s|t), (s|z, r, q, h)}.
Это множество определяет возможные ветки дерева: k, s, z, r, q, l, t, h. В работе приведены возможные варианты построения веток метода извлечения знаний об отношении «Целое – часть». Ниже приведены варианты построения ветки k.
содержит
содержит
содержит
содержит
содержит
содержит
содержит
содержит
имеет характеристику
содержит
имеет характеристику
имеет характеристику
есть
имеет индекс
имеет индекс
имеет индекс
имеет значение
имеет значение
имеет значение
есть
есть
есть
имеет значение
имеет значение
Для лучшего понимания приведенного описания веток рассмотрим в ветке branch_k вторую строку – <>. Она соответствует изображению ветки k на рисунке 3. Запись варианта означает, что вершина k распадается на две ветки с вершинами s и ветку с вершиной index, которая является листом. Ветки с вершинами s представляют собой последовательно расположенные вершины, заканчивающиеся листьями с константным значением.
Рис. 3. Пример графовой структуры, отражающей взаимосвязь конструктов метода извлечения знаний о семантическом отношении «Целое – часть»
Итак, каждое продукционное правило может быть представлено в виде дерева. Причем дерево строится на основе конструктов, состоящих из двух вершин и помеченной дуги. Допустимое соединение конструктов задается с помощью описаний веток дерева.
Из этого следует, что спецификация метода включает: множество понятий Тk, используемых в методе; семейство множеств конструктов Kkc, определяющих связь между двумя понятиями; множество графов Kkg в виде множества альтернативных кортежей, компоненты которых составляют вершины первого уровня графа, и множества возможных вариантов построения веток. Этой информации достаточно для генерации ядер продукционных правил, входящих в систему продукций. В качестве средства описания спецификации метода в работе использован язык XML.
Компонент «Генетический алгоритм GASP». Модель генератора систем продукций построена с применением генетического программирования.
Структура хромосомы имеет вид дерева продукции. Молекула ДНК состоит из динамического числа генов и представляется в виде
i b1, lc, b2, lc, …, lc, bm>,
где ai, b1, b2, …, bm, lc – гены, max(m)=7; ai, bj Tk, Tk – входной алфавит, |Tk|= k; символ ‘’ обозначает глагол; lc – логическая связка «И» или «ИЛИ».
Рис. 4. Пример молекулы ДНК
содержит
содержит
Например, если ai= p, b1,= k, b2 = h, то граф молекулы ДНК будет иметь вид, изображенный на рис. 4. Пара смежных веток, исходящих из одной вершины, связана между собой логической связкой «И» или «ИЛИ». Глагол может иметь отрицание – унарную логическую связку '', которая записывается над стрелкой ''.
Оценка особи. По каждой разрешенной ветке вычисляется Fitness-функция Fi по формуле Дайса: Fi = 2n(G1G2)/(n(G1)+n(G2)), где G1 – ветка дерева, описанная в спецификации метода; G2 – ветка порожденного дерева. Графы G1 и G2 имеют одинаковый корень. Общая формула для Fitness-функции F особи вычисляется как сумма Fi всех разрешенных веток в сгенерированном дереве. В процессе оценивания заполняется таблица помет, в которой по каждой особи отмечается, какой вид генетического оператора рекомендуется использовать для улучшения её свойств.
После оценивания выполняются операторы селекции, скрещивания и мутации с целью улучшения особей популяции. Когда функция оценки совокупности особей достигает единичного значения, данная особь копируется в конечное множество. В данном алгоритме используются классические одно- и двухточечные операторы кроссинговера, мутации вида: L1-мутация, Branch-мутация, А-мутация.
Оценка достоверности сгенерированных систем продукций. Для первичной оценки достоверности сгенерированной системы продукций использован подход, описанный в работе А.А. Асанова «Генетический алгоритм построения экспертных решающих правил в задаче многокритериальной классификации». Для этого введены коэффициенты абсолютной ошибки Eabs и относительной ошибки Erel, которые вычисляются по формулам:
где Kkc – множество исходных конструктов метода, определенных по формуле (2); – множество конструктов метода в порожденных продукциях.
Для метода «Распознавание семантического отношения «Целое – часть» число исходных конструктов |Kkc| = 43, количество конструктов в порожденных продукциях: Тогда коэффициент абсолютной ошибки будет равен Коэффициент относительной ошибки:
В работе введено понятие степени покрытия cd множеством порожденных конструктов множества исходных. Для порожденных множеств конструктов она равна Таким образом, полученное значение степени покрытия cd показывает, что достоверность порожденных продукций достаточно высока.
Для окончательной оценки порожденной системы продукций используется объект, внешний для генетического алгоритма – система логического резолютивного вывода LogResDed (Logical Resolutive Deduction). Система LogResDed должна окончательно определить приспособленность совокупности особей к решению поставленной прикладной задачи.
Предложенная модель генератора преобразователя продукционных правил позволяет порождать модели преобразователей, способных отображать продукции, представленные на ограниченном подмножестве естественного языка, в формулы логики предикатов первого порядка, а их, в свою очередь, во множества дизъюнктов.
Анализ результатов вычислительных экспериментов показал, что генетический алгоритм выдает лучший результат при использовании ряда операторов скрещивания 33Simple33Arithm34MixGen (рис. 5). Во-первых, применение ряда операторов показало наилучшую сходимость алгоритма. Во-вторых, графики лучшей и средней функций приспособленности особи имеют вид возрастающей функции. При этом среднее значение не становится очень близким и не удаляется сильно от лучшего значения. Все это позволяет утверждать об удовлетворительном качестве популяции. Различие между лучшим и средним значениями Fitness-функции поддерживает разнообразие генетического материала, которое увеличивает вероятность появления особи с лучшими свойствами.
Рис. 5. Результаты испытаний комбинированного оператора скрещивания
По результатам проведенных трех серий испытаний программного компонента «Генератор модели преобразователя продукционных правил» в генетический алгоритм были включены следующие генетические операторы:
1) ряд операторов селекции: 80% пропорциональной селекции и 20% турнирной селекции (80Ratio20Tourn);
2) ряд операторов скрещивания: 33% хромосом скрещиваются одноточечным кроссинговером, 33% – арифметическим и 34% – с использованием генного смешивания (33Simple33Arithm34MixGen);
3) ряд операторов мутации: 40%–a-Mutation, 40% – b-Mutation, 20% – А-Mutation.
В качестве Fitness-функции была использована модифицированная функция расчета меры близости графов, основанная на коэффициенте Дайса. Для двух графов GЕ и GТ мера близости FT вычисляется по формуле:
,
где n(S) – мощность множества вершин S графов GЕ и GТ; Е – индекс графа, представляющего входную эталонную продукцию; Т – индекс текущего выходного графа, представляющего преобразованную продукцию; i – индекс вершины; ki – масштабирующий коэффициент соответствующих вершин. Выходной граф GТ создается в результате прогона особей в инструментальной среде UniMod, поддерживающей технологии автоматного программирования. Хромосома представляет собой закодированную модель преобразователя. В среде UniMod разработан метод «Интерпретатор хромосомы в представление среды UniMod». Полученная модель преобразователя может быть запущенна в режиме интерпретации или преобразована в код на языке Java и скомпилированна.
Апробация модели преобразователя осуществлялась на множестве тестовых входных файлов с идентификаторами InPut#.xml. После прогона в UniMod создавался выходной файл OutPut#.xml, содержащий преобразованную продукцию. Каждому тестовому файлу InPut#.xml соответствовал эталонный файл Etalon#.xml, который был использован для расчета Fitness-функции особи.
Надежность алгоритма вычислялась как отношение числа успешных запусков kS порожденного преобразователя, при которых решение было найдено, к общему числу запусков k: S = kS /k. Если преобразователь правильно выполнил преобразование, запуск считался успешным. Все 98 исходных формул преобразователь правильно перевел во множество дизъюнктов, то есть kS=98. Тогда, S = 98/98=1. Это означает, что алгоритм абсолютно надежен для заданной выборки продукций и его надежность составляет 100%.
Таким образом, разработанные генераторы построены с использованием генетического программирования. В генераторах (генетических алгоритмах) использован единый способ представления хромосом популяции в виде деревьев, хотя структуры молекул ДНК хромосом различны. Общим является и то, что в генетических алгоритмах применены ряды однотипных генетических операторов. Единый подход к их подбору заключался в использовании не одного конкретного оператора, а ряда операторов: скрещивание хромосом производилось вероятностным смешивающим, одноточечным и арифметическим кроссинговерами; мутация – операторами a-мутации, b-мутации и А-мутации; селекция – операторами пропорциональной и турнирной селекции. Использование ряда генетических операторов во время эволюции позволяют создавать лучшие решения с меньшими вычислительными усилиями.
Следует также отметить то, что применение технологий генетического и автоматного программирования позволяет значительно ускорить процесс разработки программного обеспечения, так как в этом случае основной упор при программировании делается лишь на программирование методов, реализующих действия автомата.
Особенностью модели генератора является то, что порожденный преобразователь может переводить символы входного алфавита в символы выходного алфавита без явного задания грамматики перевода. При этом символы алфавитов могут иметь сложную синтаксическую конструкцию. Грамматики перевода определяются неявно посредством задания исходных объектов, описанных в символах входного алфавита, и эталонных объектов, описанных в символах выходного алфавита. Достижению такой универсальности генетического алгоритма в рамках класса задач преобразования с неявно заданной грамматикой способствовали направленный поиск и специфические генетические операторы, представляющие собой ряд типовых по выполняемому действию генетических операторов.
Пятый раздел посвящен описанию предложенной автоматной модели аппарата активации, необходимой для апробации сгенерированных методов естественно-языковой обработки научного текста. Принципиально аппарат активации построен как модуль управления продукционными знаниями.
Модуль управления разработан в среде Eclipse по технологии автоматного программирования, обеспечивающей широкие возможности модификации и совершенствования автоматных моделей с минимальным объемом прямого программирования. Для поддержки автоматного программирования в СПбГУ ИТМО создана инструментальная система Unimod с открытым исходным кодом, которая содержит набор инструментов, позволяющих проектировать и реализовывать программы по SWITCH-технологии. Система Unimod реализована на языке Java в виде плагина к среде разработки Eclipse. Программа, написанная с помощью Unimod и соответствующая концепции автоматного программирования, содержит схему связей, состоящую, как и в SWITCH-технологии, из источников событий, системы управления и объектов управления. Источник событий информирует систему управления о завершении выполнения действий в некотором состоянии. К выходным воздействиям автомата относятся выходные переменные и события, к входным – переменные, необходимые для вычисления условия перехода. Далее производится проверка переменной события и осуществляется соответствующий переход. Таким образом, объект управления инкапсулирует описание выходных воздействий и условий перехода. Автоматная модель модуля управления (рис. 6), построена в соответствии с её принципиальной схемой, приведенной в работе. В данной модели, осуществляется либо безусловный переход из одного состояния в другое, либо переход по возникновению событий (табл. 2). Модель автомата состоит из четырех групповых и одного нормального состояний:
1) SetActiveProdSystem – предназначено для выбора продукционного правила и баз фактов, формирования множества G, включающего множество {G2,…,Gk} баз фактов, используемых методом для логического вывода, G1 – множество дизъюнктов текущего правила;
2) SelectInSituationSet – предназначено для формирования и выгрузки в рабочую память множества дизъюнктов входных ситуаций d0;
3) SelDisjunctAndResolution – обеспечивает логический вывод для текущего правила на всех дизъюнктах входной ситуации и всех входных ситуациях;
4) SolvationOfConflictSet – предназначено для определения системы разрешения конфликтного множества, передачи ей управления и подготовки необходимой информации;
5) FuzzyLogic – простое состояние, предназначенное для вызова системы нечеткого логического вывода.
Групповое состояние SetActiveProdSystem. Оно включает три состояния. В состоянии Input выполняются следующие выходные воздействия (действия):
1) o2.z1 – ввод информации в буфер о порядке выполняемых методов, объектах их анализа и идентификаторах файлов InpMeth#Inf.xml, содержащих информацию о методе из файла CommonInfMethods.xml;
2) o2.z2 – определение текущего метода, подлежащего выполнению, поиск идентификатора файла InpMeth#Inf.xml, чтение файла и запись считанной информации в новый буфер. Если выполнены все методы, то переход по событию e100 на конечное состояние автомата ActivationMachine, иначе переход в состояние selFactsBase.
В состоянии selFactsBase в соответствии со списком баз фактов, содержащимся в слоте ListDictionary файла CommonInfMethods.xml, выполняется действие о2.z3 – выбор и запись в рабочую память фактов словарей в виде множеств дизъюнктов G2, …, Gk. В состоянии selProdSys выполняется действие o2.z4 – выбор активной системы продукций по аббревиатуре метода, которая задается в атрибуте short_name тега name файла CommonInfMethods.xml. Подсистема продукций уточняется по сфере применения, которая задается в том же теге в атрибуте useArea. Сформированное множество дизъюнктов G1 дописывается в рабочую память.
Рис. 6. Модель автомата модуля управления
Групповое состояние SelectInSituationSet. Оно включает два состояния. В первом состоянии readDataMeth выполняется действие о3.z1 – считывание информации об объекте анализа выполняемого метода из XML-файла InpMeth#Inf.xml. При достижении конца файла генерируется событие e1[o3.x1==1], и осуществляется переход в состояние Input группового состояния SetActiveProdSystem. Если конец файла не достигнут, то генерируется событие e1[o3.x1!=1], и выполняется переход в состояние selInSituationSet. Этому состоянию соответствуют следующие действия: o3.z2 – выбор множества входных ситуаций d0; o3.z3 – запись множества входных ситуаций в буфер. За одно обращение к состоянию в рабочую память загружается множество входных ситуаций.
В основном все переходы между состояниями групповых состояний SelectInSituationSet и SetActiveProdSystem носят безусловный характер. По окончании работы группового состояния SetActiveProdSystem управление передается в состояние readDataMeth, а группового состояния SelectInSituationSet – в состояние selNewRule автомата SelDisjunctAndResolution.
Таблица 2. Пометки переходов модели автомата ActivationMachine
Групповое состояние SelDisjunctAndResolution. Оно включает восемь состояний. В состоянии selNewRule реализуются следующие выходные воздействия:
1) о4.z1 – выборка нового правила из активной системы продукций;
2) о4.z2 – чтение файла InpMeth#Inf.xml, выборка из тегов paramscondition значений параметров условия применимости С;
3) о4.z3 – вычисление условия применимости С правила. Если С=true, то генерируется событие e3[o4.x2==1], и осуществляется переход в состояние selNewSituation, в противном случае – выполнение выходных воздействий о4.z1 и о4.z2, и вычисление условия применимости (петля при генерации события e3[o4.x2!=1]).
В состоянии selNewSituation осуществляется действие о4.z4 – выбор новой ситуации из множества ситуаций, находящихся в рабочей памяти. В состоянии isExecuted проверяется, все ли возможные ситуации доказаны для текущего правила (действие о4.z5). Если это истинно, то управление передается в состояние ifConflict (событие e2[o4.x1==1]), если нет (событие e[o4.x1!=1] ), то в состояние selNewDis. В состоянии selNewDis выбирается новый дизъюнкт из текущей ситуации, и если не все дизъюнкты перебраны, то генерируется событие e4[o4.x3!=1], и происходит переход в состояние Resolution. В этом состоянии осуществляется вызов системы линейного резолютивного вывода DedLogRes (действие о4.z9), которая осуществляет линейный резолютивный вывод. Переходы между состояниями selNewDis и Resolution выполняются до тех пор, пока не будут доказаны все дизъюнкты текущей ситуации (при генерации события e4[o4.x3!=1]). Если на всех дизъюнктах одной ситуации получен пустой дизъюнкт, то гипотеза, заложенная в текущем правиле и текущей входной ситуации, доказана. Таким образом, действие о4.z7 заключается в подсчете k, для которых получен пустой дизъюнкт, и его сравнении с числом дизъюнктов в текущей входной ситуации. Если они совпали, то генерируется событие e5[o4.x3==1 && o4.x4==1], и осуществляется переход в состояние searchMethPAP, иначе генерируется событие e5[o4.x3==1 && o4.x4!=1], и осуществляется переход в состояние selNewSituation. Если пустой дизъюнкт получен для нескольких входных ситуаций, то формируется конфликтное множество (выходное воздействие о4.z8). В состоянии searchMethPAP осуществляется поиск метода, указанного в постдействии H текущего продукционного правила (действие о4.z10). В состоянии execution осуществляются вызов и выполнение найденного метода – действие о4.z11. Затем осуществляется переход в состояние selNewRule.
В состоянии ifConflict проверяется конфликтное множество (действие о4.z6). Если оно непустое, то генерируется событие e6[o4.x5==1], и управление передается групповому состоянию SolvationOfConflictSet. Если конфликтное множество пустое, то генерируется событие e6[o4.x5!=1], и выполняется переход в состояние readDataMeth группового состояния ConstructInSituationSet.
Групповое состояние SolvationOfConflictSet. Оно включает четыре состояния. В состоянии solvator происходит определение средства разрешения конфликтного множества (действие o5.z1). В качестве средства разрешения может быть применена либо классическая система продукций, либо нечеткая система продукций, и, соответственно, должен выполняться либо логический резолютивный вывод (состояние selNewRule группового состояния SelDisjunctAndResolution), либо нечеткий логический вывод (состояние fuzzyLogic). После определения одного из вышеназванных средств осуществляется переход в состояние selSpecProdSys. В нем осуществляется поиск специальной системы продукций (классической или нечеткой), предназначенной для разрешения данного конфликтного множества (действие o5.z3). Затем выполняется безусловный переход в состояние formInSituation, в котором осуществляется формирование входной ситуации (действие o5.z2). Далее осуществляется безусловный переход в состояние activation. В нем специальная система продукций и входные ситуации помещаются в рабочую память, и если сгенерировано событие е7[o5.x1==1] управление передается в состояние selNewSituation группового состояния SelDisjunctAndResolution, иначе по событию е7[o5.x1!=1] управление передается в состояние fuzzyLogic.
В состоянии fuzzyLogic осуществляется вызов системы нечеткого логического вывода FuzzyRegulator. Из этого состояния управление передается снова в состояние readDataMeth группового состояния ConstructInSituationSet на цикл обработки следующего или нового объекта анализа.
Таким образом, в модели наряду с классическим логическим выводом реализован нечеткий логический вывод, так как задачам естественно-языковой обработки научного текста свойственна нечеткость. Для повышения эффективности поиска решения при разработке системы резолютивного логического вывода использованы технологии генетического и автоматного программирования. Для каждого метода в процессе эволюции строится собственная модель автомата, настроенная на множество дизъюнктов данного метода. Таким образом, система логического вывода, состоящая из множества конечных автоматов, модели которых построены на основе эволюций, а реализация – по технологии автоматного программирования, обладает действительно эффективными алгоритмами поиска решения.
Заключение по работе содержит перечень научных и практических результатов, полученных при решении поставленной в работе проблемы.
В приложениях приведены: прототипы базовых знаков-фреймов; примеры словарных статей терминосистемы и номенклатуры в формате XML; примеры систем продукций методов естественно-языковой обработки научного текста; пример XML-описания спецификации методов морфологического анализа, извлечения знаний о семантическом отношении «Часть-Целое»; результаты испытаний программного компонента «Генератор продукционных правил ProdGen» (пятая серия); множества конструктов методов естественно-языковой обработки текстов; примеры конфигурационного файла ConfigTask.xml и XML-документов Input.xml и Etalon.xml; результаты испытаний программного компонента «Генератор модели преобразователя продукционных правил FSTPSGen» (третья серия); результаты испытаний автоматной модели системы резолютивного логического вывода (первая серия); акты об использовании результатов диссертационного исследования.
