Диссертация (1137276), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

. ,| | ) Компоненты вектора – это либо частоты слов, либо − веса, которые вычисляются по формуле, = × = × log( ) + 1где – частота слова в тексте , ( ) – число текстов, содержащихслово , – – количество текстов. Каждому тексту соответствует вектор в про­странстве слов.

Размерность этого вектора совпадает с количеством различныхслов во всех текстах из коллекции. Составим аналогичный вектор для строкис использованием − весов для слов из строки. Релевантность строки тек­сту определяется через косинусную меру близости между соответствующимивекторами:relevance(,) = cos(,) =2.1.3 × |||| × ||||(2.1)Релевантность в бинарной модели независимостиРелевантность строки тексту в бинарной модели независимости определя­ется по следующему Байесовскому правилу:relevance(,) = (|,) = (|,) × (|), (|)(2.2)39где – бинарная переменная, принимающая два значения, 1, если строкарелевантна тексту и 0 в обратном случае. Следовательно, (| = 1,)и (| = 0,) – вероятности того, что строка релевантна тексту и то­го, что строка нерелеватна тексту, соответственно. Заметим, что (| =1,) + (| = 0,) = 1.2.1.4Релевантность в вероятностной моделиВероятностная модель представления текста используется, в основном, взадачах извлечения/поиска информации и сформулирована в терминах зада­чи поиска по запросу.

Она основана на теоретическом принципе ранжированиявероятностей (“Probability Ranking Principle”, PRP) [2]: наиболее эффективнаяпоисковая машина выдает тексты пользователю в соответствии с убываниемвероятности релевантности его запросу. Здесь под релевантностью понимает­ся соответствие содержания текста запросу (более широкое понимание поня­тия релевантности будет изложено ниже). Предполагается, что релевантность – это случайная величина, которая принимает бинарные значения: – если¯ – в обратном случае.запрос релевантен тексту, Она построена в предположениях теоретической модели, согласно которойкаждый текстовый текст представляется как смесь двух Пуассоновских распре­делений [2].

Одно из них отвечает за распределение обычных слов, другое – зараспределение «элитных» слов, то есть, тех, на которых лежит основная смыс­ловая нагрузка в разрезе рассматриваемой тематики. Обычно тематика задаёт­ся тем запросом на извлечение информации, относительно которого и оценива­ется релевантность. Релевантность строки тексту в этой модели определяетсяпо вероятности того, что слова, принадлежащие строке, окажутся элитными втексте.Следуя векторной модели представления текстов вероятностная модельрелевантности предполагает, что строка и текст – два набора слов.

Ставшаяочень популярной в последнее время мера релевантности BM25 придаёт боль­ший вес значимым словам и меньший – незначимым:40relevance(,) =∑︁IDF( )=1(1 + 1) + 1 (1 − +| | ),(2.3)где – среднее количество слов в тексте, а , 1 – константы, равные,как правило 1.5 и 0.75, соответственно, согласно citerobertson2009probabilistic.В качестве нормализующего сомножителя используется функция IDF, име­ )+0.5, где ( ) – число текстов, со­ющая следующий вид: IDF( ) = log −(( )держащих слово .

Функции IDF имеет смысл обратной частоты: чем большетекстов содержат данное слово, тем менее он значим.2.1.5Релевантность в тематических моделяхРелевантность строки тексту в модели латентно-семантического анализаопределяется следующим образом. Пусть для строки определен вектор частотслов в исходном пространстве слов. Представим в его новом простран­ˆ = Σ−1 . Релевантность строки тек­стве меньшей размерности: сту определяется по косинусной мере близости между преобразованным векто­ром, соответствующем строке, и вектором, соответствующем тексту, т.е.

столбцуˆв матрице .В генеративных моделях представления текста, таких как языковая мо­дель или модель латентного размещения Дирихле, релевантность строки текстусоставляет вероятность порождения текстом строки, то есть, (|) =∏︁ (|),∈где – слова из которых состоит строка .В [64] предложены следующие оценки вероятностей (|) = (|) + (1 −) (|), + + где – параметр распределения Дирихле (в [64] предложено использовать = 1000), – количество текстов в коллекции, (|), (|) – оцен­ки по принципу максимального правдоподобия вероятностей слова в тексте и коллекции , соответственно.41Альтернативная схема вычисления оценок вероятностей предложена в[37]: (|) + (1 −) (|)) + (1 − ) (|) + + (2.4)которая отличается от предыдудщей схемы наличием последнего чле­на формулы (1 − ) (|). Здесь – это нормировочный показатель, а (|) – оценка вероятности слова в тексте по модели ЛРД, которая нахо­дится по стандартному алгоритму ЛРД, примененному к проиндексированнойколлекции текстов.

(|) = (2.1.6Релевантность в теоретико-множественной моделипредставления текстовВ предложенной в данном диссертационном исследовании теоретико-мно­жественной модели представления текстов каждый текст представляется набо­ром всех фрагментов строк и их частотами. В качестве строк выступают одно-,двух- или трехсловные последовательности. Для определения релевантностистроки тексту в данной модели введем понятие совпадения. Совпадение – этотакая подстрока входной строки, которая встречается и в множестве фрагмен­тов текста. Максимальным совпадением назовем такое совпадение, которое придобавлении символа в начало или в конец, перестает быть совпадением.Допустим, что существует совпадение строки с текстом .

. . . Опреде­лим его вероятность, как условную частоту последнего символа в совпадении : ( . . . ) = ( | . . . −1 ) (УВС). Вероятностью максимального совпа­дения тогда являетсясредняя сумма совпадений, в него входящих (СУВС):∑︀ ( ... ) ( . . . ) = =1(−) . Полной релевантностью строки тексту являетсясредняя сумма вероятностей максимальных совпадений данному тексту (чтоэквивалентно средней условной вероятности символа в совпадении, СУВСС):relevance(,) =.∑︀||=1 ( ...

),где – количество символов в строке42Для эффективной реализации вычисления оценок релевантности следуетиспользовать аппарат аннотированного суффиксного дерева. Оценивание реле­вантности строки тексту с использованием АСД предполагает построение АСДдля текста и последующее наложение строки на АСД [5].Метод AST оценивания релевантности строки текстуКаждый текст представляется собственным АСД, с которым слича­ется строка для вычисления оценок релевантности. Оценка релевантностиrelevance(,) строки тексту вычисляется следующим об­разом:1. Выделяются все суффиксы строки 2.

Для каждого суффикса вычисляется оценка его совпадения match сАСД:score(match( ,)) =∑︁(∈ℎ (node)), (node )(2.5)где совпадение – это путь от корня дерева, кодирующий совпадающийс ним префикс суффикса или суффикс целиком, (node) – частота,приписанная узлу node АСД из совпадения, (node ) – частота,приписанная родителю данного узла3.

Оценка релевантности вычисляется как сумма всех оценок:relevance(,) = SCORE(,) =∑︁score(match( ,)) (2.6)В формуле 2.5 – это шкалирующая функция, переводящая оценку совпа­дения в уровень релевантности. Рассмотрим три вида шкалирующей функции, рекомендованных в [5] на основе экспериментов по категоризации электрон­ной почты:– () = 1 – константа (обозначение – constant);– () = – линейная (обозначение – linear);– () = log 1−– логистическая (обозначение – logit);43√– () = – корень квадратный (обозначение – root);– () = 2 – квадратичная функция (обозначение – square);– () = log() – логарифмическая функция (обозначение – log);– () = 1+1 − – сигмоида (обозначение – sigmoid).Из этих трёх только линейная, ничего не меняющая функция, имеет оче­видный операциональный смысл – средней условной вероятности символа всовпадении (СУВСС); две нелинейные шкалы из [5] могут быть использованыдля контроля.2.2Метод nAST-k оценивания релевантности строки тексту сиспользованием нормированного АСДМетод nAST-k используется для оценивания релеватности строки (иликоллекции строк) тексту (коллекции текстов).

Метод nAST-k имеет несколькорадиикальных отличий от метода аннотированного суффиксного дерева, опи­санного в [5]. Во-первых, используется другой способ подготовки текстов: текстпредставляется набором строк нефиксированной длины, а не набором фрагмен­тов. Во-вторых, используется нормированная оценка релевантности.

В-третьих,метод nAST-k предусматривает параметризацию АСД, в том числе, процедуруочистки АСД от шума. В-четвертых, для АСД построения используется алго­ритм, имеющий линейную сложность по времени.2.2.1Структура методаМетод оценивания релевантности строки тексту с использованием норми­рованного АСД заключается в– подготовке текстов к обработке путем разбиения на последовательныефрагменты– определении и вычислении параметров АСД– вычислении нормированной оценки релевантности442.2.2Подготовка текстов к обработкеПодготовка текстов к обработке проводится согласно стандартной схеме,представленной в [6]: удаление xml- и html-разметки, если она присутствуетв тексте, токенизация, удаление знаков препинания и прочих символов, вклю­чая цифры и псевдографику, приведение всех слов к нижнему регистру.

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

В [65] экспериментально показано, что глубина дерева, построенногопо строкам из 2-4 слов, вполне достаточна для задач анализа текстов. Такимобразом, текст после обработки состоит из строк из 2-4 слов, соединенных че­рез пробел. Строки строятся следующим образом: первая строка начинается спервого слова в тексте и заканчивается 2-4 словом в тексте, вторая начинаетсясо второго и заканчивается соответственно на 3-5 слове. Например, если перваястрока обработанного текста такова: “слово1 слово2 слово3”, то вторая строкатекста будет такой: “слово2 слово3 слово4”. При этом учитываются границыпредложений: в одну строку не должны попадать слова из разных предложе­ний.2.2.3Параметризация АСДРассмотрим три параметра АСД: глубину, уровень очистки от шума иразмах.

Характеристики

Список файлов диссертации