Курдюков Н.С.
Рязанский
Государственный Радиотехнический Университет, Россия
Введение
Дескриптивные логики(description logics) доказали свою эффективность как
инструмент представления знаний [1]. В
то же время разработка онтологий на их основе в среде Semantic Web
является ресурсоемким процессом. Во избежание плохих результатов после создания
онтологии необходимо использовать явный критерий выбора дескриптивной логики
для решения задач конкретной предметной области. Таким критерием может
послужить вычислительная сложность алгоритмов логического вывода в онтологиях.
В этой
статье раскрывается определение вычислительной сложности и способ ее применения
для выбора профилей языка веб-онтологий OWL 2[3].
Основы определения вычислительной сложности
Вычислительная сложность алгоритма определяет зависимость необходимого объёма памяти и
времени для выполнения этого алгоритма от размера входных данных[2]. Это
- одна из главных проблем в развитии дескриптивных логик. Исследование
оптимизации алгоритмов начинается с извлечения класса вычислительной сложности
задачи, которую алгоритм должен решать.
Ниже приведены классы сложности,
распространенные в области разработки алгоритмов для дескриптивных логик.
LogSpace ⊆ NLogSpace ⊆ P⊆NP⊆ExpTime⊆ NExpTime
Класс LogSpace содержит задачи, для решения которых детерминированной машине Тьюринга потребуется объем памяти, находящийся
в логарифмической зависимости от входных значений.
Приставка
N в названиях классов NlogSpace, NP и NexpTime означает,
что эти классы содержат задачи, которые могут разрешиться за
количество ресурсов, соответствующее их классу сложности с названием без
приставки на недетерминированной
машине Тьюринга. Так
как недетерминированная машина
Тьюринга всего лишь абстрактная модель, то
алгоритм этого класса вряд ли сможет разрешиться на реальном компьютере,
соответствующем детерминированной
машине, за тоже время.
Класс P вмещает
все те проблемы, решение которых детерминированной машиной Тьюринга
полиномиально зависит от размера
входа.
ExpTime - это класс, содержащий
задачи, которые детерминированная
машина Тьюринга решает за
количество времени, находящееся в экспоненциальной зависимости от входных
значений.
Первоначально
исследования о сложности вывода в дескриптивных логиках были более
сосредоточены на классе P без
рассмотрения неразрешимых NP или
CONP проблем. Это давало гарантированную вероятность
того, что алгоритм будет работать быстро. Но в дальнейшем было признано[1], что
базы знаний реального размера могут быть обработаны в разумные сроки, несмотря
на высокий класс сложности – ExpTime или выше.
Вычислительная сложность для фрагментов языка OWL 2
Рассмотрим
сложность языка для описания веб онтологий OWL 2, предложенного международным консорциумом по развитию
веб-стандартов для представления знаний в сфере Semantic Web [3].
Естественные
семантики OWL 2
охватывают фрагмент очень выразительной дескриптивной логики SROIQ, сложность которой достигает NExpTime. Данный язык стоит использовать, если необходимо описать очень
сложные концепты.
Для более эффективной работы
консорциумом W3C были разработаны облегченные профили языка OWL 2 c
ограниченной выразительностью, но более быстрыми алгоритмами для задач
логического вывода[3]:
- OWL 2 EL разрешает алгоритмы класса P для всех стандартных задач вывода, подходит для приложений, где необходимы
большой объем гипотез, и где выразительностью можно пренебречь;
- OWL 2 RL разрешает алгоритмы класса P для всех стандартных задач вывода, особенно подходит для приложений, где
относительно легкие онтологии используются для того, чтобы организовать большое
количество индивидов и где это будет полезно или необходимо работать с данными
в форме RDF-триплетов;
- OWL 2 QL разрешает PTime алгоритмы для стандартных задач вывода и LogSpace, алгоритмы для ответов
на запросы(query answering), с использованием технологии реляционных баз данных. Данный профиль позволяет
работать с большим объемом данных, хранящихся в реляционных базах данных.
Представленной выше информации достаточно
для того что бы, оценив предметную область задачи, выбрать подходящий язык для
описания онтологии этой предметной области.
Оценка вычислительной сложности
алгоритмов логического вывода в онтологиях позволяет выявить плюсы и минусы
конкретных дескриптивных логик. Этот критерий обеспечивает возможность выбрать дескриптивную
логику как основу для представления знаний определенной предметной области еще
до создания онтологии на этапе проектирования, тем самым значительно экономя
трудовые ресурсы.
Литература
1. Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The
description logic handbook: Theory, implementation, and applications. Cambridge
University Press, 2nd edition, 2010.
2. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages,
and Computation. — М.: «Вильямс», 2002. — С. 528.
3. OWL 2 Web Ontology Language Document Overview. [Электронный ресурс]: Официальный сайт международного консорциума W3C — Режим доступа:
http://www.w3.org/TR/owl2-overview/