Семантическая классификация на основе обучения по деревьям синтаксического разбора

Размещено на http://www.allbest.ru/

СЕМАНТИЧЕСКАЯ КЛАССИФИКАЦИЯ НА ОСНОВЕ ОБУЧЕНИЯ ПО ДЕРЕВЬЯМ СИНТАКСИЧЕСКОГО РАЗБОРА

Б.А. Галицкий

С. О. Кузнецов

С. В. Якимович

Введение

Использование деревьев синтаксического разбора позволяет решать задачи, требующие высокого уровня понимания языка, например, извлечения информации и ответы на вопросы [Bar-Haim et al., 2005] [Ravihandran et al., 2002]. В данной работе на основе деревьев синтаксического разбора создаются наборы признаков, с помощью которых проводиться семантическая классификация предложений. Используются предложения, взятые из отзывов покупателей на цифровые камеры на сайте Amason.com. Они классифицируются на являющиеся информативными отзывами на продукт и на не являющиеся таковыми. Информативными считаются отзывы, которые содержат информацию о свойствах товара, например, “Auto focus is really quick”. Такие отзывы представляют потенциальный интерес для производителя и продавца товаров, в отличии от неинформативных вроде “I bought this as a gift”. Также информативные отзывы классифицируются на положительные, например, “Very little noise” и отрицательные, например “Battery life is short”. Рассматриваются различные способы введения признаков предложений на основе их деревьев синтаксического разбора: словосочетания, последовательности слов и их тэгов, поддеревьев дерева синтаксического разбора.

синтаксический дерево семантический предложение

1. Подходы к представлению предложений

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

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

В случае представления предложения в виде дерева синтаксического разбора обычно не вводят фиксированный набор свойств, а вводят меру сходства двух деревьев [Vishwanathan et al., 2002] [Collins et al., 2002] [Moschitti, 2004]. Для многих методов классификации, например, для метода k ближайших соседей этого достаточно, чтобы провести классификацию.

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

Классификация в данной работе осуществлялось на основе следующих признаков:

1.Слов

2.Словосочетаний

3.Последовательностей слов и их тэгов

4.Поддеревьев дерева синтаксического разбора предложения

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

Далее более подробно описываются признаки, введенные в работе.

Слово

В качестве признаков используются слова, содержащиеся в предложении. Используются алгоритмы морфологического поиска (stemming), позволяющие свести все формы одного и того же слова к одной. В работе используется открытая программа Snowball Stemmer.

Словосочетание

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

Последовательность слов и их тэгов

Под последовательностью в данной работе понимается последовательность слов и их тэгов, соответствующие некоторому узлу дерева синтаксического разбора. Каждой последовательности соответствует её тип, являющийся типом соответствующего узла. Опишем построение последовательности, соответствующей некоторому узлу синтаксического дерева. Берется некоторый узел синтаксического дерева, не являющийся терминальным, то есть словом. Затем строиться последовательность всех слов, являющихся потомками этого узла. Далее каждому слову поставим в соответствие его тэг, то есть непосредственного предка. В качестве примера последовательности можно привести [NP:JJ-great NN-picture NN-quality]. Вводится функция, которая возвращает меру схожести двух последовательностей. Если последовательности имеют разные типы, то возвращается 0. Если последовательности имеют один тип, находится наибольшая общая последовательность этих последовательностей. Если тэги каких-то слов совпадают, а сами слова нет, то в наибольшей общей подпоследовательности на месте этих слов стоит *. Вводиться вес общего слова и вес общего тэга. Функция, характеризующая сходство двух последовательностей, равна количеству слов в наибольшей общей подпоследовательности, умноженному на вес общего слова, плюс количеству общих тэгов, умноженному на вес тэга.

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

Поддерево дерева синтаксического разбора

Поддерево дерева синтаксического разбора предложения в данной работе использовалось как в качестве бинарного признака, так и в качестве числового признака. При использовании в качестве бинарного признака проверяется, является ли дерево-признак поддеревом дерева синтаксического разбора предложения.

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

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

2. Методы классификации и компьютерные эксперименты

Классификация осуществлялась с помощью следующих методов:

Метод K ближайших соседей (KNN)

Наивный байесовский классификатор (NB)

SVM методы (методы опорных векторов):

SVM light (Joachims 1998)

SMO (Platt 1998)

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

Для обучения и проверки результатов использовались 1600 предложений. Проводилась кросс-валидация с разбиением на 4 группы.

Табл. 1. Результаты классификации

3. Временные затраты

Для вычислений использовался компьютер с процессором Intel Core 2 Duo 2.0 GHz и памятью 2GB. В таблице 14 приведено время, затраченное на кросс-валидацию при использовании метода SVM SMO и различных атрибутов классификации.

Табл. 2. Время, затраченное на кросс-валидацию

4. Лучшие атрибуты

Далее (таблицы 3, 4) приведены слова и деревья, которые являются наиболее характерными атрибутами семантических классов, рассматриваемых в работе. Атрибуты выбирались в соответствии с критерием ч2. ч2 является мерой отсутствия статистической независимости между классом и свойством. В каждой таблице первые 5 отзывов являются наиболее характерными для 1 класса, а последние 5 для 2.

Табл. 3. Лучшие атрибуты при классификации отзывов на информативные и неинформативные

Табл. 4. Лучшие атрибуты при классификации отзывов на положительные и отрицательные

Роль синтаксической информации при классификации отзывов на информативные и неинформативные значительно больше, чем при классификации на положительные и отрицательные. Если среди самых характерных поддеревьев информативных и неинформативных отзывов поддеревьев с узлами-словами практически нет, то в случае положительных и отрицательных отзывов они составляют большинство. Даже те конструкции, которые не являются словами, например, (VP(RB *)) без слов не имеют классификационной ценности. (VP(RB *)) встречается в положительных и отрицательных отзывах 7 и 51 раз. При этом конструкция (VP(RB not)) встречается 4 и 48 раз, то есть без слова “not” конструкция (VP(RB *)) встречается только 6 раз, 3 раза в положительных отзывах и 3 раза в отрицательных, то есть не имеет самостоятельной классификационной ценности. Есть и обратный пример.

На первом месте в списке самых характерных слов для информативных отзывов оказалось слово “is”. В информативных и неинформативных предложениях оно встречается 178 и 68 раз. В списке самых характерных конструкций есть конструкция (VP(VBZ is)(ADJP *)) (к сожалению, она не попала в таблицу) которая встречается 107 и 10 раз. Отсюда видно, что вне конструкции слово “is” встречается 61 и 58 раз, то есть практически не имеет классификационной ценности.

Заключение

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

Словосочетания

последовательности слов и их тэгов

поддеревья дерева синтаксического разбора.

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

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

[Bar-Haim еt al., 2005] Bar-Haim R., Dagan I., Greental I. Shnarch E. Semantic inference at the lexical-syntactic level. // In proceeding of AAAI-05, 2005.

[Collins еt al., 2002] Collins M. and Duffy N. Convolution Kernels for Natural Language. // In proceeding of ACL-02, 2002.

[Galitsky et al., 2009] Galitsky Inferring semantic properties of sentences mining syntactic parse trees. // In proceeding of ICCS-09, 2009.

[Joachims, 1998] Making large-Scale SVM Learning Practical. // Advances in Kernel Methods - Support Vector Learning, chapter 11. MIT Press, 1998.

[Jurafsky еt al., 2000] Semantic Speech And Language Processing. // Prentice Hall, 2000.

[Moschitti, 2004] A study on convolution kernels for shallow semantic parsing. // In proceeding of ACL-04, 2004.

[Platt., 1998] Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. // Advances in Kernel Methods - Support Vector Learning, chapter 12. MIT Press, 1998.

[Ravichandran еt al., 2002] Learning surface text patterns for a Question Answering system. // In proceeding of ACL-02, 2002.

[Vishwanathan еt al., 2002] Vishwanathatn S.V.N. and Smola A.J. Fast kernels on strings and trees.// In proceeding of Neural Information Processing Systems, 2002.

Размещено на Allbest.ru