Расширение объектной модели Стэнфордского парсера для решения задачи идентификации семантических триплетов

Проблемы передачи и обработки информации

УДК 681.3.07

А.А. Иванков, А.Л. Шишагин расширение объектной модели сгэнфордского парсера

для решения задачи идентификации семантических триплетов

A.A. Ivankov, A.L. Shishagin stanford nlp parsers and semantic triplets identification

Изучен информационный поиск семантических триплетов в текстах англоязычного корпуса Википедии. Для идентфикации триплетов использован стэнфордский парсер, объектная модель которого расширена авторами. Приведены оценки вероятности ошибки идентфикации триплета.

ИНФОРМАЦИОННЫЙ ПОИСК. СЕМАНТИЧЕСКИЙ АНАЛИЗ. СТЭНФОРДСКИЙ ПАР-СЕР. СЕМАНТИЧЕСКИЙ ТРИПЛЕТ. ОШИБКИ ИДЕНТИФИКАЦИИ.

We developed some own classes for the object model of Stanford NLP parsers to implement our algorithm of semantic triplet identification. Results of information retrieving are discussed for en.Wikipedia articles.

INFORMATION RETRIEVING. SEMANTIC ANALYSIS. STANFORD NLP PARSERS. SEMANTIC TRIPLET. RETRIEVING ERRORS.

В работе [1], посвященной семантическому анализу и оцениванию различных характеристик документов на основе результатов такого анализа, алгоритмы ориентированы преимущественно на использование элементов метаданных, т. е. элементов разметки, определяющих структуру документа. Мы анализировали текст на уровне заголовков, подзаголовков и т. п., используя соответствующую грамматику языка разметки конкретного документа (в нашей работе это были подмножества грамматики HTML/XML) и модель «мешка слов».

Между тем структурообразующие элементы содержат существенно меньшую часть информации, чем предложения дискурсов в тексте самого документа. Задача семантического анализа не может быть решена в полном объеме, если не выполня-

ется семантический анализ каждого предложения дискурса.

Большинство лингвистов разделяют следующую точку зрения: актуальное членение предложения на естественном языке (ЕЯ) предполагает выделение особого уровня (отличного от синтаксического), на котором грамматическими средствами выражается субъектно-предикатная структура соответствующей мысли. На этом, особом, логико-грамматическом уровне предложения мы имеем дело с логико-грамматическим субъектом и логико-грамматическим предикатом, которые не обязательно должны совпадать с синтаксическими подлежащим и сказуемым. но в то же время давно замечено [2], что в научно-технической литературе такое соответствие имеет место почти всегда, если привлекать язык статистики.

В пределах отдельного предложения наибольший вклад в семантику этой элементарной части дискурса вносится триплетом (тройкой): подлежащее — сказуемое — дополнение. Научно-технические тексты характеризуют преимущественно как номинативные, но особую роль в них играет сказуемое. Глагол или существительное как часть составного сказуемого — это смысло-образующие элементы фразы (главные ее элементы) [3—5]. Более того, глагол-сказуемое поддерживает темо-рематическую прогрессию текста, что принципиально важно в рамках коммуникативно-функционального подхода к построению модели языка. напомним также, что язык RDF (Resource Definition Framework) создан консорциумом W3 как средство семантического описания интернет-ресурсов, ориентированное на триплеты: субъект — предикат — объект.

Следовательно, одной из важнейших задач семантического анализа предложений является идентификация семантических триплетов.

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

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

представлений семантической сети. Такое представление является весьма наглядным. Другое место приложения результатов решения этой задачи — автоматическое построение онтологий предметных областей и, разумеется, семантическое описание интернет-ресурсов с использованием языка RDF.

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

Результаты, доставляемые нам этими операторами в конечном итоге, — это лес случайных деревьев. Математические модели на классе случайных помеченных деревьев на практике приводят к ресурсоемким алгоритмам оценивания. Наш опыт работы с подобными моделями позволяет нам утверждать, что получение отдельных оценок на корпусе неаннотированных документов может потребовать до нескольких недель работы вычислительной системы.

тем самым становится очевидным, что выбор инструментария для реализации алгоритмов решения задачи — ключевой момент в таких исследованиях.

множество основных критериев выбора содержит по меньшей мере следующие:

форматы хранения входных данных и результатов;

портируемость решения на другие платформы;

язык реализации.

Большинство синтаксических анализаторов для представления результатов синтаксического анализа предложений используют формат Penn TreeBank [6] (рис. 1). такая форма представления дерева синтаксического разбора стала стандартом де факто для парсеров, работающих с текстами на английском языке. Это весьма удивительный факт, принимая во внимание, что в отношении других форматов эти

Рис. 1. Графическое представление дерева синтаксического разбора

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

Основное системное требование — программное обеспечение должно легко разворачиваться на платформе WINTEL или в одной из популярных Unix-систем. С точки зрения портируемости программного обеспечения исследователи отдают предпочтение решениям на объектно-ориентированном языке программирования JAVA. Наиболее доступные решения с открытым JAVA-кодом уже более 10 лет предлагаются на сайтах http://opennlp.apache.org и http://sourceforge.net/projects/opennlp.

Принимая во внимание указанные выше критерии, наш выбор осуществлялся из небольшого множества анализаторов с открытым кодом: LinkParser, MSTParser, MultParser, Stanford Core NLP.

Необходимость идентификации грамматических отношений в пределах отдельного дерева синтаксического разбора — это

еще одно функциональное требование к инструментарию. Номенклатура грамматических отношений (отношений зависимости, определяемых на узлах дерева синтаксического разбора) существенно отличается от парсера к парсеру. наименьшая мощность множества грамматических отношений у консервативной схемы [7]. Парсер ЬткРагеег напротив предлагает исследователю более тонкую структуру этого множества. Мощность множества и качество идентификации ее элементов в тексте на ЕЯ — еще два критерия выбора инструмента. Они не взаимодополняющие: выбор в пользу одного может привести к потерям в отношении другого.

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

Помимо критериев портируемости и

4

English symbols

Рис. 2. Графическое представление результатов семантического анализа отдельного предложения

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

мы остановили свой выбор на пакете Stanford Core NLP [8] по следующим соображениям:

• структуры дерева синтаксического разбора совпадают с классическим форматом Penn TreeBank;

• множество идентифицируемых грамматических отношений расширено по сравнению с классической схемой [7], добавлены дополнительные отношения (см. рис. 2), играющие важную роль, обеспечивая успех последующего семантического анализа;

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

хорошо зарекомендовали себя на практике;

• семантический анализ можно параметризовать с помощью шаблонов, определяющих правила разбора;

• исходный код доступен под лицензией GPL;

• кроссплатформенный язык разработки — JAVA, на этот язык уже портировали и ряд других анализаторов.

Наибольшие сложности порождало отсутствие качественной документации. Единственно эффективным инструментом для изучения пакета как всегда оказался отладчик. Библиотеку из 467 классов, около 150 000 строк исходного кода, мы подвергли рефакторингу, исключив «грязную» сборку, и дополнительно разработали 45 классов, реализующих недостающую в

исходном пакете функциональность.

Все другие модификации кода были вынужденной мерой в условиях ограниченности аппаратных ресурсов, которыми мы располагали для проведения исследования. Заметим, что одни лишь словари парсера требовали более 7Г адресного пространства, не говоря уже об объеме собственно байт-кода.

Идентификация триплетов

В ходе анализа публикаций, посвященных семантическому анализу текстов на английском языке, наше внимание привлекли работы, упоминаемые в [9]. Это, пожалуй, один из немногих апробированных подходов к решению задачи идентификации триплетов, алгоритм которого опубликован.

Решение задачи авторы излагают в виде списка правил, применяемых к дереву синтаксического разбора предложения. Структура этого дерева (S в нотации Penn TreeBank) содержит два дочерних элемента: NP — именное словосочетание; VP — глагольное словосочетание. Поиск подлежащего (SUBJ) выполняется в пределах NP — первый дочерний элемент NP, грамматическая категория «часть речи» которого указана как «существительное», атрибутируется как подлежащее (SUBJ). Поиск сказуемого (PRED) осуществляется в пределах VP — наиболее удаленный по уровню иерархии терминальный элемент, грамматическая категория «часть речи» которого указана как «глагол», атрибутируется как сказуемое (PRED).

Наконец, поиск дополнения осуществляется в элементах того же уровня иерархии (по отношению к S), что и VP. По меньшей мере три различных поддерева рассматриваются как потенциальные контейнеры дополнения ((OBJ)):

словосочетание, содержащее предлог

(pp);

именное словосочетание (NP);

словосочетание с прилагательным (ADJP).

В первых двух типах словосочетаний осуществляют поиск первого вхождения существительного, в последнем случае — вхождение первого прилагательного.

К сожалению, авторы не привели количественных оценок качества идентификации, ограничившись иллюстрацией работы парсеров на десяти английских предложениях.

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

Тестирование выполнялось на статьях англоязычного корпуса Wikipedia, срез на 01.01.2011. Наш выбор обусловлен тем, что в большинстве работ, где обсуждается качество идентификации грамматических отношений и синтаксического анализа, оценки получают на текстах, составленных профессионалами, журналистами СМИ. Мы же хотим получить оценки на текстах «живого» языка, на текстах, которые практически не подвергались редакторской правке.

Результаты тестирования указывают на то, что предложенные авторами [9] приводят к потере большой части семантических триплетов. Рассмотрим итоги разбора первых предложений статьи «Ada (programming language)».

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

Подлежащее идентифицировано успешно: (NNP Ada). В нотации [9] — subj, в оригинальной стэнфордской нотации — nsubj. Однако сказуемое (NN language) было утеряно, а вместо него в качестве предиката предложено причастие (VBN extended).

В качестве дополнения — (NNP Pascal) — ошибочная интерпретация предложного дополнения из причастного оборота.

Еще один пример:

Подлежащее и в этом предложении было успешно идентифицировано: (NNP Ada). Сказуемое (VBN designed) утеряно, а в его качестве предложено (VBN used) из придаточного предложения.

Мы убедились, что правила идентификации семантических триплетов из [9] приводят к потере значимой информации.

Приняв во внимание результаты тестирования правил идентификации триплетов, изложенных в [9], был предложен собственный алгоритм. Он (алгоритм идентификации триплетов) определяется набором структурных и грамматических правил, которые на уровне реализации хранятся во внешнем файле-шаблоне. Эти правила последовательно применяются ко всему дереву синтаксического разбора или отдельным его частям.

Правила идентификации семантических триплетов

Алгоритм реализован на основе набора правил, которые применяются к дереву, полученному по итогам разбора структуры предложения, и к семантическому дереву отношений:

SR (Structure Rules) — структурные правила;

GR (Grammar Rules) — грамматические правила.

Структурные правила служат для идентификации в пределах одного предложения его придаточных предложений, причастных и деепричастных оборотов, отдельных фраз. Таким образом мы определим, в каких частях предложения содержатся объекты «семантический триплет» (далее — ST) из одной группы.

К структурным правилам мы отнесли следующие:

1. одной семантической группе принадлежат все терминальные узлы дерева структурного разбора и соответствующие им объекты ST, которые имеют одинаковый ближайший вверх по дереву узел S (Sentence) или (Root).

2. Одной семантической группе принадлежат все терминальные узлы дерева структурного разбора и соответствующие им объекты ST, которые имеют одинаковый ближайший вверх по дереву узел VP или NP. В этом случае на узлы VP и NP накладываются дополнительные ограничения: их родительский узел должен быть S и среди дочерних узлов S исходные узлы должны следовать после первого вхождения узла VP.

3. Если в поддереве с корневым узлом PP обнаружено поддерево PP, то в нем игнорируются все поддеревья, кроме тех, у которых корневой узел S.

Основное грамматическое правило определяет обобщения и фильтрации грамматических отношений:

1. Из всех типов грамматических зависимостей, которые имеются в иерархическом дереве стэнфордского парсера, для построения наших правил оставлены и обобщены следующие грамматические отношения:

PRED = {pred, aux, auxpass, cop }

SUBJ = { subj, nsubk, nsubjpass, csubj, csubjpass, xsubj }

OBJ = { conj, prep, partmod, obk, iobj, dobj, pobj }

Помимо этого, определяются несколько правил включения очередного объекта ST на основе уже определенных в группе объектов. эти аспекты поиска триплетов будут изложены в другой нашей работе.

Результаты такого обобщения положительные. В первом из указанных выше предложений подлежащее — (NNP Ada), сказуемое — (NN language). Во втором примере подлежащее — (NNP Ada), обобщенное сказуемое — (VBN designed) совместно с (VBD was), предложное дополнение — (NN team). Но не все результаты так же хорошо согласуются с экспертной оценкой. Приведем еще один характерный пример (в нашей XML нотации): <sentence>

<text>It has strong built-in language support for explicit concurrency, offering tasks, synchronous message passing, protected objects and nondeterminism. </text> <tokens>

<token> <value > It</value> <role>nsubj</role> </token>

<token> <value > has</value> <role>pred</role> </token>

<token> <value > strong</value> </

token>

<token> <value > built-in</value>

</token>

<token> <value > language</value>

</token>

^океп> <уа1ие > support</value> <ro1e>dobj</ro1e> <Докеп>

<token> <va1ue > for</va1ue> <го1е>ргер</го1е> </token>

<token> <va1ue > exp1icit</va1ue>

</token>

<token> <va1ue > concurrency</ va1ue> <ro1e>pobj</ro1e> </token>

<token> <va1ue > ,</va1ue> </token>

<token> <va1ue > offering</va1ue>

</token>

<token> <va1ue > tasks</va1ue> <ro1e ест=Ошибочная идентификация грамматического отношения >conj</

ro1e>

</token>

<token> <va1ue > synchronous</ va1ue> </token>

<token> <va1ue > message</va1ue>

</token>

<token> <va1ue > passing</va1ue> <ro1e err=Ошибочная идентификация грамматического отношения >conj</

го1е>

</token>

С ft Q Le*2/sesa/data/c_colored jaa ges/col ored jjages/Ad а%ЭДргод ra m mi пд %20 lang ua ge), fitrn^ ^

да.п.чЬк,... n.e.af"*d >í»[ Аа^'чЬзр... l3v,i,c,pobJ r wtlon>ubj ^luiqxn

biing^P гг.* ? : -  г г-—:- pra g г жт=лтРг ^ .

Features

VU1UJ4»" oii3iji»lliF t.zg.T..dPr«d .-_р«р .Et.dd.d ind I.il-ïu.1™] .

Th» M» SS uvijion"^ . byP-'P 3, Tuck«r TíítP°bJ o£P«P InnribtTiinP0^ Ькиип'г,Г

л up pe ^obj fQE i^jtusj r nuoccical r financial , and object-oritnttd

progressing 4

Notable features'1*^ of Ada incl"jdePred : strong ï^ing^' , sodularity sechanissa , run-ciœa checking , parallel processing , exception handling , and generics .

j^^nsubj g g addedPced support ^obj Qj^^Cfprienteii ргсдгатптгл nq , including dynamic dispatch .

The synta*n,Xib3 0f i»MP i¿splePr*d , consistent sad readable .

Itnsubj minimijEeaPred choicesdabJ of ways toaux perfor=Pred basic operationsdob3 , and pre fers con3 English Jceyvordsdob3 to*11* systole .

Adansubj uaaaPred tha faaaic Bathematical syiEbolsdab3 for basic mathematical operations but avoidscori3 usingPred

flthflbJMhauáaj_

Рис. 3. Форма представления результатов синтаксического и семантического анализа статьи для выполнения ручной разметки экспертом

Оценивание уровня ошибок в результатах

Обобщенное грамматическое отношение Общее количество Количество ошибочно идентифицированных Процент ошибок, %

OBJ 3214 607 18,89

PRED 1835 222 12,1

SUBJ 857 114 13,3

Сумма 5906 943 15,97

<token> <value > protected</value>

</token>

<token> <value > objects</value> <role err=Ошибочная идентификация грамматического отношения > conj</

role>

</token> <token> <value > and</value> </

token>

<token> <value > nondeterminism</

value>

<role err=Ошибочная идентификация грамматического отношения > conj</

role>

</token>

</tokens> </sentence Обеспечив результаты синтаксического и семантического анализа HTML разметкой, мы предоставили эти материалы экспертам в виде (рис. 3), пригодном для выполнения ручной разметки этих же статей.

Ошибки в идентификации грамматических отношений лексемы очень критичны для последующего семантического анализа. Следует заметить, что в данном примере мы выбрали из случайного леса деревьев, порождаемых стэнфордским парсером, дерево, оптимальное по критерию согласия, построенному авторами пакета на основе модели порождающих грамматик, они в бинарной форме хранятся в этой программной системе (файл объемом более 7Г, загружаемый в адресное пространство приложения в ходе его работы).

В нашей работе предпринята попытка провести семантический анализ текстов англоязычной Википедии, т. е. текстов, которые подготовлены различными специалистами, не являющимися профессиональными журналистами или писателями. Мы подчеркиваем это обстоятельство, т. к. в большинстве других работ (в т. ч. в [9]) использовались размеченные экспертами журнальные статьи. Расхождения результатов идентфикации семантических триплетов, полученных с помощью нашего алгоритма и алгоритма из [9] в нашей интерпретации, позволяют предположить, что в [9] и последующих работах этой группы исследователей изложен подход, нуждающийся в существенном дополнении как с точки зрения статистической обработки текстов на ЕЯ, так и с точки зрения лингвистики.

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

СПИСОК ЛИТЕРАТУРЫ

1. Иванков, А.А. Динамическое отслежива- ресурса [Текст] / А.А. Иванков, Д.С. Елисеев // ние модулем информационно-поисковой систе- Научно-технические ведомости СПбГПУ. Ин-мы изменений в структуре или тексте интернет- форматика. Телекоммуникации. Управле-

ние. —СПб.: Изд-во Политехн. ун-та, 2010. -№ 3 (101). -С. 86-93.

2. Пумпянский, А.Л. Информационная роль порядка слов в научной и технической литературе [Текст] / А.Л. Пумпянский. -М.: Наука, 1974. - 247 с.

3. Апресян, Ю.Д. Лексическая семантика. Синонимические средства языка [Текст] / Ю.Д. Апресян. - М.: Наука, 1974. - 367 с.

4. Филлмор, Ч. Основные проблемы лексической семантики [Текст] / Ч. Филлмор // Новое в зарубежной лингвистике. - М.: Радуга, 1983. -Вып. XII. Прикладная лингвистика. - С. 74-122.

5. Сильницкий, Г.Г. Соотношение глагольных признаков различных уровней в английской

речи [Текст] / Г.Г. Сильницкий, С.Е. Андреев, Л.А. Кузьмин, М.И. Кусков. — Минск: Наука i тэхшка, 1990. - 182 с.

6. [Электронный ресурс] / Режим доступа: http://www.ldc.upenn.edu/Catalog/docs/ LDC99T42/prsguid1.pdf

7. Treebanks: Building and Using Parsed Corpora [Text] / Ed. A. Abeille. — Springer, 2003.

- P. 302—312.

8. [электронный ресурс] / режим доступа: http://nlp.stanford.edu

9. Rusu, Delia. Semantic Graphs Derived from Triplets with Application in Document Summarization [Text] / Delia Rusu [et al.] // Informatica.

— 2009. —Vol. 33. P. 357—362.

REFERENCES

1. Ivankov A.A., Eliseev D.S. Dinamicheskoe otslezhivanie modulem informatsionno-poisko-voi sistemy izmenenii v strukture ili tekste Inter-net-resursa / Nauchno-tekhnicheskie vedomosti SPbGPU. Informatika. Telekommunikatsii. Uprav-lenie. —St-Petersburg: Izd-vo Politehn. un-ta, 2010. -№ 3

2. Pumpianskii A.L. Informatsionnaia rol' pori-adka slov v nauchnoi i tekhnicheskoi literature. -Moscow: Nauka, 1974. - 247 s.

3. Apresian Iu.D. Leksicheskaia semantika. Si-nonimicheskie sredstva iazyka. — Moscow: Nauka, 1974. - 367 s.

4. Fillmor Ch. Osnovnye problemy leksicheskoi semantiki / Novoe v zarubezhnoi lingvistike.

— Moscow: Raduga, 1983. —Vyp. XII. Prikladnaia lingvistika. — S. 74—122.

5. Sil'nitskii G.G., Andreev S.E., Kuz'min L.A., Kuskov M.I. Sootnoshenie glagol'nykh priznakov razlichnykh urovnei v angliiskoi rechi. — Minsk: Nauka i tekhnika, 1990. - 182 s.

6. http://www.ldc.upenn.edu/ Catalog/docs/ LDC99T42/prsguid1.pdf

7. Treebanks: Building and Using Parsed Corpora; Ed. A. Abeille. - Springer, 2003. - P. 302-312.

8. http://nlp.stanford.edu

9. Delia Rusu et al. Semantic Graphs Derived from Triplets with Application in Document Summarization / Informatica. -2009. -Vol. 33. -P. 357-362.

ИВАНКОВ Алексей Александрович — доцент кафедры прикладной математики Санкт-Петербургского государственного политехнического университета, кандидат физико-математических наук. 195251, Россия, Санкт-Петербург, ул. Политехническая, д. 29. E-mail: ivankov@stu.neva.ru

IVANKOV, Alexei A. St. Petersburg State Polytechnical University. 195251, Politekhnicheskaya Str. 29, St.-Petersburg, Russia. E-mail: ivankov@stu.neva.ru

ШИШАГИН Алексей Леонидович — выпускник кафедры прикладной математики Санкт-Петербургского государственного политехнического университета, магистр. 195251, Россия, Санкт-Петербург, ул. Политехническая, д. 29.

SHISHAGIN, Alexei L. St. Petersburg State Polytechnical University. 195251, Politekhnicheskaya Str. 29, St.-Petersburg, Russia.

© Санкт-Петербургский государственный политехнический университет, 2013