WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

2 Причём связь слова и концепта не указывается, если концепты получили небольшой вес для данного слова. Для вычисления взвешенного вектора используется параметр k – запись в инвертированном индексе, указывающая на степень связи слова и концепта. Из статьи [103] не ясно, как вычисляется эта степень связи слова и концепта, возможно, как (1) относительное число повторов слова в статье, (2) позиция в тексте (чем ближе к началу статьи, тем больше вес).

- 35 LSA [100], WikiRelate! [173] и других, выполняющими поиск на основе данных WordNet, Роже и ВП. Достоинство метода также в том, что он позволяет определять значение многозначного слова.

Метод извлечения контекстно связанных слов Метод извлечения контекстно связанных слов на основе частотности слово­ сочетаний предлагается в [146] для поиска контекстно похожих слов (КПС) и для машинного перевода. Данными для поиска КПС служат (1) семантически близкие слова из тезауруса, (2) словосочетания из базы данных (БД) с указанием типа связи между словами. Для слова w формируется cohort w, то есть группа слов, связанных одинаковыми отношениями со словом w, из базы словосочетаний. КПС слова w – это пересечение множества похожих слов (из тезауруса) с cohort w. Работа [146] интересна формулами, предлагаемыми для вычисления сходства между группами слов.

Обычно вычисляется сходство между отдельными парами слов.

В работе [146] вычисляется сходство между группами слов G и G на основе 1 формул, предложенных в [122]. Вершины графа – слова, взвешенные рёбра указывают степень сходства между словами (таким образом, матрица инциденций – sim – матрица сходства, хранит сходство между отдельными элементами). Вычисляются:

AI – absolute interconnectivity (абсолютная связность), как суммарная AI G1, G2= sim x, y сходство между всеми парами в группах:.

xG yG 1 AC – absolute closeness (абсолютная близость или плотность) определяется AC G1,G2= AI G1,Gкак среднее сходство между парами элементов:

G1G Разница между AI и AC в том, что в AC учитывается пары имеющие нулевое сходство (рис. 1).

В [122] предлагает нормализовать абсолютную связность и близость за счёт вычисления внутренней связности и близости отдельных групп.

Внутренняя связность и близость определяются на основе вычисления разбиения каждой группы (поиск за O(N) минимального числа рёбер, удаление которых приведёт к разбиению графа на две части).

- 36 Рис. 1. Пример, иллюстрирующий разницу между мерами AI и AC. Значение AI в случаях (a) и (b) остаётся постоянным, но значение AC в случае (a) больше, поскольку в (b) больше вершин, не имеющих похожих вершин [146] Можно упомянуть ещё ряд статистических алгоритмов для вычисления семантической близости слов: LSA [100], PMI-IR [180].

Метрики Выделяют несколько способов определения похожих документов1 [53].

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

Простой коэффициент соответствия X Y показывает количество общих индексных терминов. При вычислении коэффициента не берутся в рассмотрение размеры множеств X и Y.

Таблица 1.Коэффициенты сходства для документов, для ключевых слов [53] Формула Название Коэффициент Дайса (dice) X Y X Y X Y Коэффициент Джаккарда (jaccard) X Y X Y Косинусный коэффициент X 1/ 2Y 1/ 1 Речь идёт о текстовых документах, а не о интернет страницах, то есть нет ссылок. Документам можно поставить в соответствие вершины графа. Если степени сходства документов сопоставить расстояние между вершинами, то более похожим документам будут соответствовать более близкие вершины.

- 37 Коэффициент перекрытия X Y min X,Y В таблице 1.2 показаны способы вычисления степени сходства, основанные на учёте:

– частотности слов в корпусе;

– расстояния в таксономии;

– одновременно и частотности слов, и расстояния в таксономии.

Таблица 1.Классификация метрик и алгоритмов вычисления степени сходства слов Формула / ссылка на описание алгоритма Название 1. Учёт частотности слов в корпусе Нормализованное max log f x,log f y -log f x, y NGD x, y = log M -min log f x,log f y расстояние Google (NGD)jaccard2 [173] Hits x AND y jaccard x, y = Hits x Hits y -Hits x AND y Описание алгоритма см. на стр. 34. ESA [103] 2. Учёт расстояния в таксономииРасстояние соответствует числу ребер кратчайшего пути Метрика применялась для между концептами концептов Тезауруса Роже [117] Leacock & Chodorov 1997, length c c 1, lch c c =-log 1, 2D [99] стр. 265-Wu & Palmer [186] lcs c c 1, wup c c = 1, depth c depth cМетрика res [151], log hypo lcsc c 1, res c c =1hypo 1, адаптированная logC к таксономии категорий ВП [173] 1 NGD расшифровывается как normalized Google distance, http://en.wikipedia.org/wiki/Semantic_relatedness 2 Формула вычисления сходства слов с помощью коэффициента Джаккарда (см. предыдущую таблицу) предложена в работе [173], где Hits(x) – определяется как число страниц, которые возвращает Google для слова x.

3 В англоязычной литературе такие метрики называют: path based measures, edge counting methods [173].

- 38 3. Учёт частотности слов и расстояния в таксономии Расстояние res [151], [152] res c c =max [-logP C ] 1, 2 C S c c1, Расстояние lin1 [128] 2log P c lin c c = 1, log P c1log P c 4. Учёт пересечения текста пересечение текста (глоссы WordNet) Lesk, 1986 [74] extended gloss overlap – пересечение глосс с учётом глосс Banerjee & Pedersen, соседних концептов WordNet [75] [173] overlap t t 1, relate t t =tanh gloss /text 1, length t length t 1 Расстояние Google – это мера семантической связности, вычисленная на основе числа страниц, полученных с помощью поисковика Google для заданного набора ключевых слов. В таблице приведена формула вычисления нормализованного расстояния Google (NGD) для двух слов: x и y, где М – это общее число веб-страниц, проиндексированных Google; f(x) и f(y) – число страниц, содержащих ключевые слова x и y, соответственно; f(x, y) – число страниц, содержащих сразу и x, и y. Если x и y на всех страницах встречаются вместе, то полагают NGD=0, если только по отдельности, то NGD=.

Выделим класс метрик, вычисляющих сходство на основе данных таксономии (табл. 1.2). Данные метрики используются для вычисления сходства концептов WordNet [74], [99], [128], [151], [152], [186], GermaNet [139], ВП [173].

В книге [99] Leacock и Chodorov предложили вычислять близость концептов как расстояние между концептами в таксономии, нормализованное за счёт учёта глубины таксономии. В формуле length c c 1,, функция length(c, c ) – это число вершин 1 lch c c =-log 1, 2D вдоль кратчайшего пути между вершинами c и c ; D – максимальная глубина 1 таксономии. В работе [99] авторы рассмотрели только одно отношение is-a и только между существительными.

1 Данная метрика получила развитие в работе [146], см. метод извлечения контекстно связанных слов, стр. 35.

- 39 В работе [186] предложена формула, учитывающая как глубину концептов в иерархии, так и глубину ближайшего общего родителя lcs (least lcs c c 1, common subsumer): wup c c =.

1, depth c1depth cРезник [151] предложил считать, что два слова тем более похожи, чем более информативен концепт, к которому соотнесены оба слова, то есть чем ниже в таксономии находится общий верхний концепт (синсет в WordNet).При построении вероятностной функции P(C), потребуем, чтобы вероятность концепта не уменьшалась при движении вверх по иерархии:

res c c =max [-logP C ]. Тогда более абстрактные концепты 1, 2 C S c c1, будут менее информативны. Резник предложил оценивать вероятность через freq C P C = частоту синонимов концепта в корпусе таким образом:, N freq C = count n, где words(C) – это существительные2, n words C имеющие значение C; при этом N – общее число существительных в корпусе.

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

В работе [173] метрика Резника res была адаптирована к ВП и информативность категории P(C) вычислялась как функция от числа гипонимов (категорий в ВП), а не статистически3 (то есть не посчитали частотность термов в ВП):

log hypo lcsc c 1,, res c c =1hypo 1, logC где lcs — ближайший общий родитель концептов с и с, hypo — число 1 гипонимов4 этого родителя, а С — общее число концептов в иерархии.

1 Заметим, что в ВП у слова обычно несколько категорий, то есть может быть несколько ближайших общих категорий.

2 В экспериментах Резник оценивал сходство существительных, учитывал отношение WordNet IS-A (гипонимия).

3 Возможно, это одна из причин, почему мера res показала в экспериментах [173] относительно слабый hypo результат.

4 Гипонимы категории K в Википедии – это все подкатегории К, а также все статьи, принадлежащие этим подкатегориям и категории К.

- 40 Lin [128] определил сходство объектов А и B как отношение количества информации, необходимой для описания сходства А и B, к количеству информации, полностью описывающей А и B. Для измерения сходства между словами Lin учитывает частотное распределение слов в корпусе текстов 2log P c (аналогично мере Резника):, где c – lin c c = 1, log P c log P c 1 ближайший общий супер-класс в иерархии для обоих концептов c и c. P – 1 вероятность концепта, вычисляемая на основе частоты появления концепта в корпусе. Отличается от формулы res способом нормализации, корректным вычислением lin (x, x) (не зависит от положения концепта х в иерархии), учитывает наличие и общих, и различающихся свойств у объектов [152].

В работе [173] мера lesk, основанная на вычислении степени пересечения глосс концептов WordNet, была адаптирована к ВП (за глоссу авторы взяли первый абзац в статье ВП). Итак, сходство двух текстов t, t 1 вычисляется с двойной нормализацией (по длине текста и с помощью гиперболического тангенса) так:

overlap t t 1, relate t t =tanh, gloss /text 1, length t length t 1 overlap t t = m 1,, где пересекаются n фраз, m слов1.

n В работе [139] (стр. 4) приведённая в таблице 1.2 формула lin была адаптирована к поиску в структуре GermaNet. В данной работе приведены две TF-IDF схемы для вычисления сходства между запросом и текстом документа.

Глава о метриках была бы неполной без упоминания того, что кроме сходства, метрики позволяют вычислять степень различия объектов. Так например, в задачах кластеризации используются функции, определяющие степень различия2 между документами. Если P – множество объектов, 1 Закон Ципфа утверждает, что чем длиннее фраза, тем реже она встречается в корпусе. На основании этого, было предложено наличие общих фраз длиной в n слов (в глоссах сравниваемых слов) оценивать как n2 [75].

2 Любая функция оценки степени различия между документами D может быть преобразована в функцию, определяющую степень соответствия S следующим образом:

S =1D -1.

- 41 предназначенных для кластеризации, то функция D определения степени различия документов удовлетворяет следующим условиям [53]:

D X,Y 1. для X,Y P D X, X =2. для X P D X,Y =D Y, X 3. для X,Y P D X,Y D X,Z D Z, Y 4. для X,Y,Z P При анализе свойств Интернет сетей1, при оценке свойств графов, созданных с помощью генератора случайных чисел, используют такие метрики [130]:

1. Распределение расстояний d(x) – число пар вершин на расстоянии х, делённое на общее число пар n2 (включая пары типа (a,a));

2. betweeness – мера центральности – взвешенная сумма числа кратчайших путей, включающих данную вершину (ребро);

3. вероятностное распределение вершин P(k) – число вершин степени k в графе;

4. правдоподобие (likelihood) – сумма произведений степеней смежных вершин;

5. кластеризация2 С(k) – отношение среднего числа ссылок между соседями вершины степени k к максимально возможному числу таких C ссылок.

k 1 Виды сетей, их топологические свойства и приложения см. в обзорных работах [70], [96], [142].

2 В работе [77] эта метрика называется коэффициент кластеризации вершины и вычисляется по формуле E i C i =, где k – степень вершины i, E – число ссылок между k соседями.

i i i k k -1/i i Усреднение C(i) по всем вершинам даёт коэффициент кластеризации графа.

- 42 1.2 Системы и ресурсы для обработки текста Автоматическая обработка текстов (АОТ) на естественном языке (ЕЯ) подразумевает наличие как программных систем1, обрабатывающих тексты, так и корпусов, содержащих эти тексты. Общие проблемы создания программных систем рассматриваются в работе [12].

В данной работе под корпусом текстов понимают «набор текстов доступных для машинной обработки, на основе которых можно проводить какие-либо лингвистические исследования» [133].

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

GATE Система GATE (General Architecture for Text Engineering) предлагает инфраструктуру для разработки и внедрения программных компонент с целью обработки текста на ЕЯ. Эта система (i) определяет архитектуру, то есть способ организации данных и программных компонент, обрабатывающих текст, (ii) предлагает реализацию архитектуры (набор классов, который может встраиваться в программные приложения независимо от GATE), (iii) помогает разрабатывать и использовать компоненты с помощью графического инструментария [92].

Система GATE написана на языке Java [8], [25], [68], [115], имеет модульную структуру, предоставляется на правах лицензии GNU library licence2. С научной точки зрения достоинство GATE заключается в возможности проводить численные измерения текста, которые можно повторить. В работе [109] критикуют систему GATE за плохую масштабируемость и за то, что она плохо справляется с большими 1 На сегодняшний день существует огромное количество программных систем для поиска и обработки текста, см. например, каталог программ Data Mining (http://www.togaware.com/datamining/catalogue.html и http://www.togaware.com/datamining/gdatamine/index.html).

2 Это ограниченная форма лицензии GNU, позволяющая, в случае необходимости, встраивать GATE в коммерческие продукты - 43 коллекциями документов. Однако отмечают «большой потенциал GATE как инструмента для планирования и разработки приложений АОТ в области Information Extraction».

Модульность архитектуры позволяет (i) включать только необходимые компоненты, (ii) использовать имеющиеся наработки, (iii) начать работу с уже существующими компонентами, по мере необходимости, создавая новые.

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.