что такое семантический граф
Семантика и деятельность
В тексте “Семантические цифровые системы” отмечалось, что современные семантические технологии пока не имеют полноценных инструментов для описания деятельности. Семантические данные традиционно представляются в виде объектного графа, узлами которого являются сущности или значения, а ребрами — свойства (отношения и атрибуты). Такие графы фиксируют статичное состояние предметной области. И такой одномоментно схваченный набор данных скорее следует рассматривать как граф знаний о предметной области, а не как ее модель, особенно если предметная область является деятельностью, а не набором неизменных фактов.
При рассмотрении предметной области как деятельности нас в первую очередь должны интересовать не сущности и их свойства, а акты, то есть события изменения свойств. И конечно же, множество актуальных, то есть необходимых для моделирования предметной области, утверждений не должно ограничиваться описанием текущего состояния деятельности, а должно представлять собой последовательности утверждений, фиксирующих события изменения сущностей. По сути, речь идет о том, что семантическая модель предметной области должна быть представлена не статичным объектным графом, а темпоральным ациклическим направленным графом.
Чтобы было понятнее, о чем речь, давайте рассмотрим несколько простых примеров.
Из отношения “Саша и Маша супруги” при фиксированных атрибутах индивидов “Саша мужчина”, “Маша женщина” однозначно следуют отношения “Саша муж Маши”, “Маша жена Саши”, а также еще отношения родства между супругами и их родителями: зять, невестка, теща, свекр и пр. Однако следует заметить, что все это множество фактов порождено одним событием “Саша и Маша поженились” (получили свидетельство о браке), которое и следует сохранить в виде утверждения, а все порождаемые этим событием отношения можно автоматически генерировать в ответ на поисковые запросы, используя аксиомы. Но самое интересное и важное в этом примере то, что за событием “поженились” может быть зафиксировано событие “Саша и Маша развелись”, которое должно отменить все отношения, порожденные первым событием.
Приведенные рассуждения предлагают нам строго различать акты деятельности, задающие семантику, и порождаемые ими отношения, которые, не добавляя содержания, используются лишь в коммуникации, то есть для упрощения общения. Упорядоченная последовательность событий типа “Авраам родил Исаака; Исаак родил Иакова; Иаков родил Иуду…” является исчерпывающим основанием для понимания того, кто тут кому сын, дед или прадед. То есть онтологию можно разделить на (1) содержательный (событийный, деятельный) уровень, на котором фиксируются события изменения статуса или свойств индивидов, и (2) сугубо языковой, в котором определяются правила поименования отношений между индивидами. Причем второй уровень онтологии необходим только для обслуживания поисковых запросов, ведь понятно, что пользователь поинтересуется “сколько племянников было у Магога?”, а не станет формулировать свой вопрос так “сколько детей родили те, которые родились от того же, от кого родился Магог?”.
Сказанное актуально для всех отношений — все они производны от актов деятельности. Отношение “Иванов работает в Газпроме” и “Газпром имеет сотрудника Иванов” порождаются событием “Иванов принят на работу в Газпром”. Именно последнее высказывание должно сохраниться как утверждение об индивидах, а нахождение Иванова в списке сотрудников Газпрома и место работы Иванова получаются из этого утверждения по элементарным правилам (аксиомам). Ну и очевидно, что данные об индивидах должны содержать последовательность всех событий приемов на работу и увольнений, то есть представлять собой темпоральный направленный ациклический граф.
В качестве примера, демонстрирующего не просто преимущества, а семантическую необходимость событийного подхода, можно привести фиксацию отношения “кусок — целое” (кусок хлеба — буханка). Попытка прямого описания через отношение “часть-целое” приведет к абсурду “кусок хлеба есть часть буханки”. Ведь понятно, когда перед нами буханка, то нет такого объекта, как кусок, а когда мы отрежем кусок хлеба, то уже не будет никакого целого, то есть буханки. Корректно данную ситуацию возможно описать только глагольным утверждением “кусок отрезали от буханки”, которое привязано к конкретному моменту времени и из которого можно сделать все выводы о связи буханки, существовавшей до акта отрезания куска, и нового индивида “кусок”, появившегося только после этого события.
Итак, если мы ставим перед собой цель моделировать деятельность, то должны в качестве утверждений фиксировать акты/события (с глагольной связкой), выстраивая их во временные последовательности — процессы и действия. При таком подходе данные будут организованы в направленные ациклические графы. При этом объектные графы, описывающие свойства сущностей предметной области, должны получаться в результате логического вывода из совокупности актов, то есть событий изменения свойств.
Миф семантического веба
В сфере семантического моделирования сложилась довольно странная ситуация: в качестве базовых используется набор стандартов и спецификаций от W3C, заточенных под проект “семантического веба” (RDF/OWL, SPARQL и пр.), хотя сам проект не только не реализован на данный момент, но и, по всей видимости, никогда не будет воплощен вследствие сомнительности исходных гипотез.
Семантический веб мыслился его автором Тимом Бернерсом Ли как следующий этап развития интернета. Идея была вполне рациональной: надо соединить все ресурсы сети не бессодержательными ссылками, отправляющими пользователя с одной страницы на другую, а осмысленными (семантическими) связями. Для этого предлагалось присвоить каждой онлайн и даже оффлайн сущности (объекту, свойству) уникальный идентификатор и объединить эти сущности в единый граф. После чего пользователи смогли бы быстро и точно находить нужную информацию, а самое главное, и у компьютеров появлялся бы доступ к смысловому содержанию сети. То есть ставилась цель создать распределенный граф знаний, связывающий в едином сетевом пространстве семантически определенные данные, с возможностью их машинной обработки и логического вывода новых фактов.
Так описанная идея семантической сети выглядит не только актуальной, востребованной, но и вполне реализуемой с использованием современных технологий — таких, как одноранговые сети с устойчивыми к атакам алгоритмами консенсуса, криптографическая идентификация пользователей и криптографическая же защита данных. Но основателями проекта исходно были приняты сомнительные архитектурные и идеологические решения, которые так и оставили семантический веб в статусе красивой мечты.
Поскольку основной целью создания семантического веба мыслилось совместное использование информации в интернете, в качестве технологической платформы проекта был выбран этот самый интернет, то есть хаотическая свалка сайтов, контентом которых распоряжаются не авторы, а владельцы доменов. Ориентация на современную сеть с необходимостью определила базовые принципы проекта: (1) использование в качестве основы для идентификаторов ресурсов (URI) интернет-адреса, (2) возможность любому делать утверждение о любом ресурсе, (3) предположение об открытом мире, то есть неполноте информации. Эти принципы и явились главными проблемами.
Прежде всего, очевидно, что адреса в интернете это не то, что может служить основой идентификации сущностей. Домен может сменить собственника, может быть заброшен, да и просто технически недоступен. Структура имен внутри домена может произвольно меняться. Не говоря о том, что множество разношерстных технологий и движков, на основе которых строятся сайты, не придерживаются никаких стандартов формирования адресов.
Но основной формальной причиной провала проекта семантического веба следует признать именно второй базовый принцип, то есть надежду на то, что единый сетевой семантический граф будут строить владельцы сайтов. Хотя уже при зарождении идеи проекта было очевидно, что владельцы сайтов пойдут на любой подлог, чтобы обмануть поисковые роботы (вплоть до прописывания на страницах невидимого текста и манипуляций с ключевыми словами). Среди тех же, кто честно захотел бы выполнить семантическую разметку страниц, справились бы с задачей только единицы. Но даже в идеальном варианте, если бы на все существующие сайты была грамотно накинута семантическая сеть, проект все равно бы не заработал. Ведь тогда вскрылось бы очевидное: мы имеем дело с сотнями и тысячами дубликатов одного и того же ресурса (текста, изображения, ролика) с разными идентификаторами (адресами). Да к тому же, у большинства экземпляров одной сущности не совпадали бы свойства, ведь «любой имеет право делать утверждение о любом ресурсе». Ну и понятно, что найти среди этих копий авторский оригинал не представляется возможным.
И конечно же, возникли большие проблемы и с третьим принципом, провозглашающим презумпцию открытого мира, то есть подразумевающего возможность свободного добавления фактов в общую сеть. Остановимся на нем подробнее.
По сути, идея открытого мира унаследована от стандартного интернета, где каждый волен добавлять любые домены, страницы, сущности и ссылаться при этом на любые другие сущности. Но семантический граф тем и отличается от ссылочной сети, что должен устанавливать логические, в идеале формально проверяемые, отношения между утверждениями о сущностях, а следовательно, для того, чтобы быть непротиворечивым, должен быть замкнутым. Составитель семантического графа, моделируя некоторый фрагмент предметной области, должен исходить из строгой концептуальной схемы, в которой принципиально недопустимы неоднозначность терминологии, неуникальность идентификаторов и, тем более, произвольное добавление утверждений любыми акторами. То есть, если и говорить об открытости логического мира, то эта открытость должна подразумевать свободное добавление в граф новых замкнутых моделей, а не произвольных фактов. Сеть должна составляться из независимых предметных и уровневых онтологий, взаимодействие между которыми обеспечивается использованием общих словарей. Требуется строго разделять две задачи: (1) построение онтологии предметной области и (2) решение проблемы взаимодействия/соотнесения разных онтологий, то есть согласование идентификаторов сущностей, поименования типов и логических ограничений для согласования обмена данными.
Следует также признать ошибочным решением и ориентацию проекта семантического веба на создание единственно верного, непротиворечивого графа, построенного по канонам формальной (монотонной) логики. С таким подходом еще можно согласиться при построении фиксированной базы знаний в некоторых практически завершенных предметных областях (география, инженерные стандарты и т.п.). Однако инструмент моделирования онтологий нужен не для описания статичных структур, а для поддержки функционирования реальных сложных систем, в которых не только во время их становления, но и в итоговом состоянии недостижимы монотонность и непротиворечивость описания. Тут стоит признать, что возникновение ошибки при построении системы является фактом, который изменяет ее состояние, и игнорирование этого факта может привести к катастрофическим последствиям. То есть логика семантического графа не должна быть монотонной. И тут следует вспомнить, что авторы идеи семантического веба оказались не единственными наступившими на грабли единой онтологии – после многолетних попыток построения единого непротиворечивого семантического пространства небезызвестный проект CYC отказался от этой идеи и перешел на работу с микротеориями – локально замкнутыми онтологиями отдельных предметных областей.
По сути, ошибка при проектировании инструментов семантического веба заключалась в том, что не было выявлено и учтено различие между двумя задачами. Первая — это создание локальной онтологии предметной области: добавление в нее утверждений, валидированных локальными же (оффлайн и онлайн) средствами, логический вывод новых утверждений по правилам, встроенным в локальную онтологию. Вторая — соединение локальных онтологий в единый сетевой граф и попытка получения выводов из множества независимых данных. Очевидно, что даже если все сетевые источники данных используют одинаковые словари и каждый из них сам по себе логически безупречен, то ответы, полученные на запросы к совокупному графу (если это вообще возможно) будут иметь принципиально иной статус достоверности по сравнению с результатами, полученными в каждой локальной онтологии.
Описанная разница в работе с локальными онтологиями и общим семантическим графом может быть формально выражена в терминах открытости мира: запрос к сети должен исходить из презумпции открытости мира, а логика работы с локальными онтологиями чаще всего будет строиться на гипотезе замкнутого мира. Можно сказать, что мир должен быть открыт, но не для отдельных утверждений, а для целостных онтологий.
Вот и получается, что стандарты W3C продолжают разрабатываться под мифический семантический веб, а все, кто пытается использовать их в реальных проектах, то есть для создания онтологий предметных областей, вынуждены постоянно придумывать костыли, чтобы получить работающий продукт.
Что такое семантический граф
Метод состоит из следующих пяти шагов: 1) извлечение терминов-кандидатов; 2) разрешение лексической многозначности терминов; 3) построение семантического графа; 4) обнаружение сообществ в семантическом графе; 5) выбор подходящих сообществ.
3.1. Извлечение терминов-кандидатов
Целью этого шага является извлечение всех терминов документа и подготовка для каждого термина набора статей Википедии, который потенциально могут описывать его значение.
Мы разбираем исходный документ на лексемы, выделяя все возможные N-граммы. Для каждой N-граммы мы строим ее морфологические вариации. Далее для каждой из вариации производится поиск по всем заголовкам статей Википедии. Таким образом, для каждой N-граммы мы получаем набор статей Википедии, которые могут описывать ее значение.
Построение различных морфологических форм слов позволяет нам расширить поиск по заголовкам статьей Википедии и, таким образом, находить соответствующие статьи для большей порции терминов. Например, слова drinks, drinking и drink могут быть связаны с двумя статьями Википедии: Drink и Drinking.
3.2. Разрешение лексической многозначности терминов
На данном шаге для каждой N-граммы мы должны выбрать наиболее подходящую статью Википедии из набора статей, который был построен для нее на предыдущем шаге.
Многозначность слов – распространенное явление естественного языка. Например, слово «платформа» может означать железнодорожную платформу, или платформу программного обеспечения, а также платформу, как часть обуви.
Правильное значение многозначного слова может быть установлено при помощи контекста, в котором это слово упоминается. Задача разрешения лексической многозначности слова представляет собой автоматический выбор наиболее подходящего значения слова (в нашем случае – наиболее подходящей статьи Википедии) при упоминании его в некотором контексте.
Существует ряд работ по разрешению лексической неоднозначности терминов с использованием Википедии [21, 8, 18, 10, 11]. Для экспериментов, обсуждаемых в данной работе, был реализован метод, предложенный Д. Турдаковым и П. Велиховым в работе [21]. В [21] авторы используют страницы для многозначных терминов и перенаправляющие страницы Википедии. С использованием таких страниц Википедии строится набор возможных значений термина. Далее наиболее подходящее значение выбирается при помощи знаний о семантической близости терминов: для каждого возможного значения термина вычисляется степень его семан-тической близости с контекстом. В итоге выбирается то значение термина, степень семантической близости с контекстом которого было наибольшим.
Распространенной проблемой традиционных методов извлечения ключевых терминов является наличие абсурдных фраз в результате, таких как, например, «using», «electric cars are». Использование Википедии как контролирующего тезауруса позволяет нам избежать данной проблемы: все ключевые термины, полученные в результате работы нашего метода, являются осмысленными фразами.
Результатом работы данного шага является список терминов, в котором каждый термин соотнесен с одной соответствующей статьей Википедии, описывающей его значение.
3.3. Построение семантического графа
На данном шаге по списку терминов, полученном на предыдущем шаге, мы строим семантический граф.
Семантический граф представляет собой взвешенный граф, вершинами которого являются термины документа, наличие ребра между двумя вершинами означает тот факт, что термины семантически связаны между собой, вес ребра является численным значением семантической близости двух терминов, которые соединяет данное ребро.
Рис. 1. Пример семантического графа, построенного по новостной статье «Apple to Make ITunes More Accessible For the Blind»
Рис. 1 демонстрирует пример семантического графа, построенного из новостной статьи «Apple to Make ITunes More Accessible For the Blind». В статье говорится о том, что главный прокурор штата Массачусетс и Национальная Федерация Слепых достигли соглашения с корпорацией Apple Inc., следуя которому Apple сделает доступным свой музыкальный Интернет-сервис ITunes для слепых пользователей посредством технологии screen-reading. На рис. 1 можно видеть, что термины, релевантные Apple Inc. и Blindness, образуют два доминантных сообщества, а термины Student, Retailing и Year оказались на периферии и слабо связаны с остальным графом.
Важно отметить тот факт, что термины – ошибки, возникшие при разрешении лексической многозначности терминов, проведенного на втором шаге, оказываются периферийными или даже изолированными вершинами графа, и не примыкают к доминантным сообществам.
3.4. Обнаружение сообществ в семантическом графе
Целью данного шага является автоматическое обнаружение сообществ в построенном семантическом графе. Для решения этой задачи мы применяем алгоритм Гирвана-Ньюмана. В результате работы алгоритма исходный граф разбивается на подграфы, которые представляют собой тематические сообщества терминов.
Для оценки качества разбиения некоторого графа на сообщества авторы [15] предложили использовать меру модулярности (modularity) графа. Модулярность графа является свойством графа и некоторого его разбиения на подграфы. Она является мерой того, насколько данное разбиение качественно в том смысле, что существует много ребер, лежащих внутри сообществ, и мало ребер, лежащих вне сообществ (соединяющих сообщества между собой). На практике значение модулярности, лежащее в диапазоне от 0.3 до 0.7, означает, что сеть имеет вполне различимую структуру с сообществами, и применение алгоритма обнаружения сообществ имеет смысл.
Мы отметили, что семантические графы, построенные из текстовых документов (таких как, например, новостная статья, или научная статья), имеют значение модулярности от 0.3 до 0.5.
3.5. Выбор подходящих сообществ
На данном шаге из всех сообществ необходимо выбрать те, которые содержат ключевые термины. Мы ранжируем все сообщества таким образом, чтобы сообщества с высокими рангами содержали важные термины (ключевые термины), а сообщества с низкими рангами – незначимые термины, а также ошибки разрешения лексической многозначности терминов, которые могут возникнуть на втором шаге работы нашего метода.
Ранжирование основано на использовании плотности и информативности сообщества. Плотностью сообщества является сумма весов ребер, соединяющих вершины этого сообщества.
Экспериментируя с традиционными подходами, мы обнаружили, что использование меры tf.idf терминов помогает улучшить ранжирование сообществ. Tf.idf дает большие коэффициенты терминам, соответствующим именованным сущностям (например, Apple Inc., Steve Jobs, Braille), а терминам, соответствующим общим понятиям (таким как, например, Consumer, Year, Student) дает низкие коэффициенты. Мы считаем tf.idf для терминов, используя Википедию так, как описано в работе [8]. Под информативностью сообщества мы понимаем сумму tf.idf-терминов, входящих в это сообщество, деленную на количество терминов сообщества.
В итоге, мы считаем ранг сообщества, как плотность сообщества, умноженная на его информативность, и сортирует сообщества по убыванию их рангов.
Приложение, использующее наш метод для извлечения ключевых слов, может использовать любое количество сообществ с наивысшими рангами, однако, на практике имеет смысл использовать 1-3 сообщества с наивысшими рангами.
4. Экспериментальная оценка
В этом разделе мы обсудим экспериментальные оценки предложенного метода. Поскольку не существуют стандартных бенчмарков для измерения качества извлеченных из текстов ключевых терминов, мы провели эксперименты с привлечением ручного труда, то есть полнота и точность извлеченных ключевых слов оценивались людьми – участниками эксперимента.
Мы собрали 30 блог-постов из следующих блогов технической тематики: «Geeking with Greg», автор Грег Линден, DBMS2, автор Курт Монаш, Stanford Infoblog, авторы – члены группы Stanford Infolab. В эксперименте приняли участие пять человек из отдела информационных систем ИСП РАН. Каждый участник должен был прочитать каждый блог-пост и выбрать в нем от 5 до 10 ключевых терминов. Каждый ключевой термин должен присутствовать в блог-посте, и для него должно быть найдено соответствующая статья в Википедии. Участники также были проинструктированы выбирать ключевые слова так, чтобы они покрывали все основные темы блог-поста. В итоге для каждого блог-поста мы выбрали такие ключевые термины, которые были выделены, по крайней мере, двумя участниками эксперимента. Названия перенаправляющих статей Википедии и название статей, на которые идет перенаправление, по сути, представляют собой синонимы, и мы в нашем эксперименте считали их одним термином.
Метод, представленный в данной статье, был реализован по следующим архитектурным принципам. Для достижения лучшей производительности мы не вычисляли семантическую близость всех пар терминов Википедии заранее. Данные, необходимые для подсчета семантической близости терминов на лету, а именно, заголовки статей Википедии, информация о ссылках между статьями, статистическая информация о терминах были загружены в оперативную память. В итоге полученная база знаний занимала в оперативной памяти 4.5 Гбайта. База знаний была установлена на выделенном компьютере с размером оперативной памяти, равным 8 Гбайт. Клиентское приложение работали с базой знаний посредством вызовов удаленных процедур.
4.1. Оценка полноты выделенных ключевых терминов
Под полнотой мы понимаем долю ключевых слов, выделенных вручную, которые так же были выделены автоматически нашим методом:
где под
Для 30 блог-постов мы имеем 180 ключевых терминов, выделенных участниками эксперимента вручную, 297 – выделенных автоматически, 127 вручную выделенных ключевых слов были также выделены автоматически. Таким образом, полнота равно 68%.
4.2. Оценка точности выделенных ключевых терминов
Мы оцениваем точность, используя ту же методологию, которой пользовались для оценки полноты. Под точностью мы понимаем долю тех слов, автоматически выделенных нашим методом, которые также были выделены вручную участниками эксперимента:
Итого, следуя показателям нашей тестовой коллекции, точность равна 41%.
4.3. Пересмотр оценки полноты и точности
С целью более качественной оценки работы метода мы также пересмотрели наши оценки полноты и точности. Важной особенностью нашего метода является факт, что он в среднем выделяет больше ключевых слов, чем человек. Более точно, наш метод обычно извлекает больше ключевых терминов, релевантных одной теме. Например, рассмотрим рис. 1. Для темы, относящейся к Apple Inc., наш метод выделяет термины: Internet, Information access, Music download, Apple Inc., ITunes, Apple Keyboard и Steve Jobs, в то время как человек обычно выделяет меньше терминов и склонен выделять имена и названия: Music download, Apple Inc., ITunes и Steve Jobs. Это означает, что, иногда метод извлекает ключевые термины с лучшим покрытием основных тем документа, чем это делает человек. Этот факт побудил нас пересмотреть оценку полноты и точности работы нашего метода.
Каждый участник эксперимента был проинструктирован пересмотреть ключевые термины, которые он сам выделил следующим образом. Для каждого блог-поста он должен был изучить ключевые термины, выделенные автоматически, и, по возможности, расширить свой набор ключевых слов, то есть дополнить его теми терминами, которые, по его мнению, относятся к главным темам документа, но не были выделены на первом этапе.
После такого пересмотра, мы получили 213 ключевых слов, выделенных вручную (вместо 180), таким образом, участники эксперимента добавили 33 новых ключевых термина, что означает, что наше предположение имело смысл, и такой пересмотр важен для полноценной оценки работы метода. В итоге, полнота равна 73% и точность – 52%.
5. Заключение
Мы предложили новый метод для извлечения ключевых терминов из текстовых документов. Одним из преимуществ нашего метода является отсутствие необходимости в предварительном обучении, поскольку метод работает над базой знаний, построенной из Википедии. Важной особенностью нашего метода является форма, в которой он выдает результат: ключевые термины, полученные из документа, сгруппированы по темам этого документа. Сгруппированные по темам ключевые термины могут значительно облегчить дальнейшую категоризацию данного документа и выведение его общей темы.
Эксперименты, проведенные с использованием ручного труда, показали, что наш метод позволяет извлекать ключевые термины с точностью и полнотой, сравнимой с теми, что дают современные существующие методы.
Мы отметили, что наш метод может быть с успехом применен для очистки сложных составных документов от неважной информации, и выделения главной темы в них. Это означает, что его интересно было бы применить для выделения ключевых терминов из Web-страниц, которые, как правило, загружены второстепенной информацией, например, меню, навигационные элементы, реклама. Это направление дальнейшей работы.