Автореферат (1137275), страница 2
Текст из файла (страница 2)
Методика апробирована в задачах пополнения таксономий чистой и прикладной математики с использованием русскоязычной Википедии;4. Показана эффективность использование критерия релевантностиСУВСС в классе задач поиска по однословному ключу, в которомполнота важнее, чем точность;5. Разработаны комплексы программ, реализующие предложеннуютеоретико-множественную модель совокупности «строка – текст» сиспользованием критерия релевантности СУВСС, применительно крешению задач в пунктах 2, 3 и 4.Теоретическая значимость работы заключается в разработке принципиально новых моделей и методов: теоретико-множественной модели совокупности «строка – текст», модели нормированного аннотированного суффиксного дерева с критерием релевантности СУВСС, а также метода построения таблиц релевантности «строка – текст» (РСТ) для применения в конкретных задачах.5Практическая ценность подтверждена экспериментами по сравнительной оценке использования мер релевантности для рубрикации научных статей,результатами расчетов по пополнению таксономий с использованием материалов интернета и результатами решения задач поиска, ориентированных на егополноту.
Все разработанные методы реализованы в виде программных комплексов, предназначенных для решения исследовательских и прикладных задач. Разработанные методы и алгоритмы были успешно применены в реальных проектахкомпании ООО «ФОРС-Центр разработки» (метод фильтрации обсценной лексики использован для анализа и определения тональности текстов в социальныхсетях в системе FORSMedia) и «ЕС-Лизинг» (метод рубрикации использован длякатегоризации проектной документации) и проектах, выполнявшихся по грантам ВШЭ в 2010 – 2015 гг., а также в преподавательской деятельности Департамента анализа данных и искусственного интеллекта Факультета компьютерныхнаук НИУ ВШЭ.Достоверность полученных результатов подтверждена строгостью использованных математических моделей и методов, экспериментами по сравнению результатов применения разработанных традиционных методов на конкретных задачах, а также алгоритмической эффективностью программных реализаций.Апробация результатов работы.
Основные результаты работы обсуждались и докладывались на следующих научных конференциях и семинарах:– 1-ой, 2-ой всероссийских научных конференция “Анализ изображений,сетей и текстов” (АИСТ-2012, АИСТ-2013), Екатеринбург, Россия; темыдокладов – “Автоматизация использования таксономий для аннотирования текстовых документов”, “Использование ресурсов интернета дляпостроения таксономии”– 1-ом семинаре по кластерам, деревьям и порядкам (COT-2013), Москва,Россия; тема доклада – “An AST method for scoring string-to-textsimiliarity in semantic text analysis”– 8-ой международной конференции “Диалог” (Диалог-2013), Бекасово, Россия; тема доклада – “Computational refining of Russian-languagetaxonomy using Wikipedia”– 3-ей международной научной конференции “Анализ изображений, сетей и текстов” (АИСТ-2014), Екатеринбург, Россия; тема доклада –“Conceptual maps: construction over a text collection and analysis”– 2-ой международной конференции “Информационные технологии и количественный менеджмент” (ITQM-2014), Москва, Россия; тема доклада – “A method for refining a taxonomy by using annotated suffix trees andWikipedia recourses”– 3-ей всероссийской конференции “Искусственный интеллект и естественный язык” (AINL-2014), Москва, Россия; тема доклада – “Созданиеи визуализация газетного интернет-корпуса”6– 8-ой международной конференции “Веб-поиск и майнинг данных”(WSDM-2015), Шанхай, КНР тема доклада – “An approach to the problemof annotation of research publication”;– 2-ом международном семинаре по майнингу данных и автоматическойобработке текстов (DMNLP-2015) тема доклада – “Some thoughts onusing annotated suffix trees for NLP tasks”.Публикация результатов.
Основные результаты работы изложены в 13научных статьях. 7 статей опубликованы в рецензируемых сборниках трудовмеждународных и всероссийских конференций, 3 статьи опубликованы в журналах из списка ВАК.Структура диссертации. Диссертация состоит из введения, 6 глав, заключения, и списка литературы, состоящего из 105 наименований.Во введении раскрывается актуальность темы диссертации, формулируются проблемы и задачи исследования, предмет исследования, определяются цели работы, описываются методы исследования, излагаются основные научныерезультаты, обосновывается теоретическая и практическая значимость работы,даётся общая характеристика исследования.В первой главе приводится обзор основных видов формализации коллекций текстовых документов: векторная модель, языковая модель, модель скрытых тем, модель суффиксного дерева.
Вводится теоретико-множественная модель представления коллекции текстовых документов: каждый документ представлен набором всех возможных символьных подпоследовательностей фиксированной длины и короче. Вводится понятие нормированного аннотированного суффиксного дерева, используемого для вычисления частот всех символьныхподпоследовательностей текстовых документов в теоретико-множественной модели.Cуффиксное дерево для m-символьной строки S представляет собой ориентированное дерево с корнем, имеющее ровно m листьев, занумерованных от1 до m.
Каждая внутренняя вершина, отличная от корня, имеет не меньше двухдетей, а каждая строка помечена непустой подстрой строки S. Никакие две дуги,выходящие из одной и той же вершины, не могут иметь пометок, начинающихсяс одного и того же символа. Главная особенность суффиксного дерева заключается в том, что для каждого листа i конкатенация меток дуг на пути от корняк листу i составляет / произносит / кодирует / прочитывает суффикс строки S,который начинается в позиции i, то есть, S[i : m] [Гасфилд, 2003]Аннотированное суффиксное дерево определяется в [Pampapathi и др.,2006] как суффискное дерево, в котором:– Символы стоят не на ребрах, а в узлах;– Каждому узлу соответствует один символ;– Каждый узел помечен частотой фрагмента, который прочитывает путьот корня до этого узла;– Опущены терминальные символы и метки листьев, представляющие номер суффикса и входной строки.7Рис.
1 — Суффиксное дерево для строки S = xabxacРис. 2 — Аннотированное суффиксное дерево для строки S = ``xabxac''Свойство 1. Частота любого узла равна сумме частот его узлов-детей, таккак родительский узел соответствует префиксу нескольких суффиксов и его частота складывается из частот этих суффиксов. Отсюда же следует другое свойство АСД.Свойство 2. Частота родительского узла равна сумме частот листьев, которые он покрывает.В первой главе описывается наивный алгоритм построения АСД для входной строки, являющийся адаптацией классического наивного алгоритма построения суффиксных деревьев [Гасфилд, 2003].
Сначала инициализируется пустаяструктура, к которой итерационно добавляются суффиксы входной строки. Придобавлении каждого суффикса проверяется, совпадает ли префикс текущего суффикса с каким-либо путем от корня в АСД (назовем такой путь совпадением).Если да, то частоты в совпадении увеличиваются на 1, а не совпавший фрагментсуффикса добавляется к последнему узлу в совпадении в качестве потомка с частотами, равными 1. Если совпадения нет, то суффикс добавляется в АСД какцепочка узлов с частотами 1.Во второй главе рассматривается задача вычисления релевантности«строка – текст», являющаяся базовым этапом любой практической задачиобработки и анализа коллекций текстовых документов.
Приводится обзор существующих мер релевантности в векторной, вероятностной и языковой моделях,а также их модификации с учетом снижения размерности модели. Общий подход к вычислению релевантности строки тексту заключается в вычислении тех8или иных частотных характеристик коллекции документов и числа совпадений– совпадающих элементов строки и текста. В качестве элемента текста могутвыступать слова в неизменном виде, их (псведо)основы, леммы или символьныефрагменты. Утверждается, что все рассмотренные меры релевантности обладают общими недостатками: они не учитывают вложенность совпадений друг вдруга и не учитывают возможные нечеткие совпадения. Предлагается использовать в качестве оценок релевантности в теоретико-множественной моделиоценки сходства, получаемые по методу нормированного аннотированного суффиксного дерева.
Утверждается и демонстрируется, что только такой метод вычисления релевантности позволяет преодолеть сформулированные недостаткидругих мер релевантности. Вводится понятие нормированного аннотированногосуффиксного дерева и связанной с ним естественно интерпретируемой функциирелевантности СУВСС (средняя условная вероятность символа в совпадении).Оценка релевантности строки тексту вычисляется в два этапа: сначала –оценки каждого суффикса входной строки 1, затем – нормированное среднееоценок всех суффиксов входной строки 2. Обозначим f (node) – частота узлаnode, а f (nodeparent ) – частота родительского узла. Оценка одного суффикса входной строки складывается из условных вероятностей узлов , входящих вf (node)совпадение match префикса данного суффикса с АСД – f (node), преобраparent )зованных при помощи шкалирующей функции и нормированных длинной совпадения |match|.∑score(match(suf f ix,ast)) =node∈matchf (node))ϕ( f (nodeparent )|suf f ix|,(1)Оценка всей входной строки 2 – это сумма всех нормированных оценок еесуффиксов suf f ix, усредненное длиной строки match.∑relevance(string,text) =suf f ixscore(match(suf f ix,ast))|string|(2)Шкалирующая функция ϕ(x) может иметь следующий вид:– ϕ(x) = 1 – константа (обозначение – constant);– ϕ(x) = x – линейная (обозначение – linear);x– ϕ(x) = log 1−x– логистическая (обозначение – logit);√– ϕ(x) = x – корень квадратный (обозначение – root);– ϕ(x) = x2 – квадратичная функция (обозначение – square);– ϕ(x) = log(x) – логарифмическая функция (обозначение – log);– ϕ(x) = 1+e1−x – сигмоида (обозначение – sigmoid).Предлагается адаптация алгоритма Укконена [Ukkonen, 1995] для построения АСД за линейное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
