Диссертация (1137241), страница 10

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

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

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

ПустьG1  (V1, E1,1, L1) и G2  (V2 , E2 ,21, L2 ) ‒ чащи с вершинами V иребрами E, где  :V  L ‒ функция, ставящая метки в соответствиеребрам, а L ‒ конечное непустое множество меток для вершин иребер. Модульное произведение чащ разбора He  G1 G2 включаетмножество вершин VH  E1 E2 , в котором все пары ребер (ei , e j ) ,1  i  E1и1  j  E2 ,должныиметьнепустоеобобщениесоответствующих им меток. Помимо этого, данные пары ребердолжны иметь непустое обобщение для меток вершин. Пустьei  (u1, v1, l1) и e j  (u2 , v2 , l2 ) . Условия выполнены, если l1  l2   ,1(v1)  2 (v2 )   и 1(u1) 2 (u2 )   .Между вершинами eH , f H VH , где eH  (e1, e2 ) и f H  ( f1, f 2 )может существовать ребро, если ребра для этой пары не совпадают:e1  f1ande2  f 2 . Также необходимо выполнениеодного изследующих условий: e1, f1 в G1 соединены посредством вершины c меткой, котораядает непустое обобщение с меткой вершины, общей для e2 , f 2 вG2 : vertices for e1, f1  vertices for e2 , f 2   . e1, f1 и e2 , f 2 не являются смежными в G1 и в G2 соответственно.Для того чтобы получить общий подграф для G1 и G2 , длякаждой пары ребер в G1 и G2 (пара вершин в H e ) из этого подграфадолжно существовать обобщение на метках со всеми остальными64парами ребер в G1 и G2 , которые формируют общий подграф.

Такимобразом, клика в H e соответствует общим подграфам в G1 и G2 .После нахождения всех наибольших клик для всех пар(например, представляющих вопрос и ответы) мы берем всерезультаты и ранжируем их в соответствии с размером клик. Притаком подходе, чем больше пар ребер содержит результат обобщения,тем более релевантным он является.2.5 Алгоритм вычисления приближенного обобщения чащразбора2.5.1 Проекции на чащахДля того чтобы оценить структурное сходство двух текстовыхабзацев, нам необходимо выполнить операцию обобщения насоответствующих им чащах разбора.

Воспользуемся приведеннымивыше определениями из теории решеток и узорных структур, для тогочтобы задать операцию обобщения.Если рассматривать абзацы как объекты, а чащи разбора как ихописания, то операция обобщения или сходства – это полурешеточнаяоперация пересечения. Далее, если представить чащу в виде графа, топересечение двух чащ наиболее естественным образом определяетсякак множество наибольших общих подграфов для соответствующихим графов. Выполнение данной операции является NP-труднойзадачей [68], поэтому для эффективного вычисления с сохранениемсвойств операции мы можем воспользоваться введенным вышемеханизмом проекций.Определениедопускаетсуществованиебольшогочисласпособов задания проекции.

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

Пример проекций для двух абзацевприведен в разделе 2.3.2.Операция пересечения двух групп определяется внутри каждоготипа групп [57]. Пересечение на проекциях заключается в попарномпересечении групп для каждого типа из двух множеств и выборенаибольших по вложению подгрупп. Работа с проекциями позволяетдобиться экономии по сложности (переход к работе с деревьями) беззначимого ущерба для качества результата (группы учитывают всенеобходимые лингвистические связи внутри абзаца).2.5.2 Построение множества расширенных группРассмотрим подробнее алгоритм нахождения заданной вышепроекции, т.е. множества расширенных групп, для чащи разбора.Для каждого предложения S в абзаце P:1.

Сформировать список предшествующих предложений в абзацеSprev2. Для каждого слова в текущем предложении:2.1Если это местоимение (pronoun): с помощью разрешенияанафоры найти все существительные и именные группы в Sprev,которые связаны с данным словом отношением «та жесущность».2.2Если это существительное (noun): найти все существительные иименные группы в Sprev, которые связаны с данным словом:отношением«тажеанафоры)отношением синонимиисущность»(черезразрешение66отношением «более общий случай»отношением «частный случай»имеют общую родительскую (связанную отношением«более общий случай») сущностьЕсли это глагол (verb):2.3Если2.3.1онвыражаетсобойкоммуникативноедействие(communicative action):2.3.1.1Сформировать группу VBCAphrase, включающую в себяглагольную группу данного слова VBphrase .2.3.1.2Найти предыдущее коммуникативное действие с егосубъектом VBCAphrase0 в Sprev.2.3.1.3Построить расширенную группу [VBCAphrase0 , VBCAphrase].Если он указывает на риторическое отношение (RST2.3.2relation):2.3.2.1Сформироватьизфраз–субъектовотношениярасширенную группу [VBRSTphrase1, VBRSTphrase2] ; фразаVBRSTphrase1 относится к Sprev.2.5.3 Обобщение чащ на проекцияхДля того чтобы вычислить сходство для двух абзацев сиспользованием проекций, необходимо:1.

Выполнить их фрагментацию и извлечь все синтаксическиегруппы из каждого предложения.2. Найти семантические связи внутри абзаца.3. Используясемантическиесвязи,построитьнаосновесинтаксических групп расширенные группы.4. Провести обобщение для каждого из четырех типов (см. раздел2.3.1) групп, заключающееся в поиске множества наибольшихобщих подгрупп для каждой пары групп одного и того же типа.675. Полученные на уровне групп обобщения можно интерпретироватькак набор путей в результирующих общих поддеревьях [57].2.6 Эксперименты по поиску с использованием сходства междуабзацами2.6.1 Схема экспериментаПопробуем оценить, как обобщение чащ разбора можетулучшить поиск в ситуации, когда сформулированный в видепоискового запроса вопрос и потенциальный ответ на негопредставляют собой текстовые абзацы.

Количественным результатомоценки является точность в процентах, вычисленная как среднее по100 поисковым запросам. В данной работе использовались параметрыпроведения эксперимента, описанные в [57].Оценка основана на повторном ранжировании поисковыхрезультатов, полученных с помощью API поисковой системы Bing,осуществляемом на базе меры сходства чащ разбора.

Сходствоопределяется как общее число вершин в наибольшем общем подграфедля двух чащ. Приближенное значение этой оценки было полученопутем подсчета количества слов в наибольших общих подгруппах сучетом весов для частей речи [57].Полученные результаты приведены в таблице. Для оценки былисмоделированы следующие ситуации в трех прикладных областях: Выдача рекомендаций по товарам: агент рекомендательнойсистемы читает чаты о продуктах и находит в сети релевантнуюинформацию о каждом продукте. Выдачарекомендацийрекомендательнойсистемыпочитаетпутешествиям:чатысагентописанием68путешествий и находит в сети релевантную информацию оботелях, курортах и т.д. Выдача рекомендаций в социальных cетях (на примереFacebook): агент рекомендательной системы читает чаты изаписи на «стене» пользователей социальной сети и отбираетинформацию, которая может быть интересна друзьям этихпользователей.В каждой из этих областей на основе Интернет-источниковвыбирался кусок текста, далее формировался запрос, а затемосуществлялась фильтрация результатов поиска, полученных спомощью API поисковой системы Bing.2.6.2 Результаты экспериментовРелевантность поиска спомощью чащ, построенныхна фрагментах, %,Релевантность поиска спомощью чащ, построенныхна оригинальных абзацах,%,Релевантность поиска сиспользованием обобщениячащ на графах, %ПоискрекомендацийРелевантность поиска сиспользованием обобщенийдля отдельныхпредложений, %,ПоискрекомендацийпопутешествиямРелевантность исходногопоиска в Bing, %,Поискрекомендацийпо товарам1 составноепредложение2 предложения3 предложения4 предложения1 составноепредложение2 предложения3 предложения4 предложения62.369.172.472.973.361.559.960.464.870.566.2666871.972.068.572.672.873.469.274.771.671.466.774.260.662.358.765.866.165.973.170.972.576.970.873.973.572.971.71 составноепредложение54.563.265.368.167.2Сложность запросаТип запросаТаблица 2.1.

Оценка релевантности поиска69контента наFacebook2 предложения3 предложения4 предложенияСредниепоказателиТочностьисходной52.349.750.960.95758.362.161.762.063.763.064.663.961.962.758.1564.7568.7570.3369.25поисковойвыдачисоставила58,2%,применение операции обобщения на уровне предложений далоулучшение в 6,5%. Использование проекций чащ для выдаваемыхпоисковой системой фрагментов (сниппетов) позволило увеличитьточность еще на 4%. Применение полного вычисления обобщения награфах для фрагментов дало прибавку в 0.5%.

Наконец, применениепроекций, но уже на чащах, построенных для абзацев, взятыхнепосредственно из оригинальных документов, дало прибавку еще в1,5% относительно вычислений на проекциях для фрагментов.Нетрудно видеть, что с ростом сложности запроса увеличивалсяэффект от применения технологии обобщения. Другим важнымвыводом является незначительная потеря качества при существенномвыигрыше в скорости за счет использования проекций.2.7 Оценка вычислительной сложностиОперация обобщения на деревьях разбора и чащах разбораопределяется как нахождение всех наибольших общих поддеревьев иподчащ соответственно. Хотя для деревьев эта проблема решается заO(N), для графа общего вида она является NP-трудной [68].Один из подходов к обучению на деревьях разбора основан натак называемых ядрах, определенных для дерева (tree kernel). Авторыэтого подхода предлагают технику, ориентированную специально надеревья разбора, уменьшая тем самым размерность пространства всехвозможныхподдеревьев.Существуетнесколькоспециальныхразновидностей ядер, направленных на более эффективную обработку70деревьев.

Частичные ядра (partial tree kernels) задают правилачастичного соответствия, игнорирующие некоторые дочерние узлы[59]. Ядра последовательностей на деревьях (tree sequence kernels)используют в качестве подструктуры не просто поддеревья, апоследовательности поддеревьев [69].Подход, основанный на сопоставлении синтаксических группдля предложений и расширенных групп для чащ разбора, свычислительнойточкизренияоказываетсягораздоболееэффективным, чем подходы, использующие ядра на графах разноговида,включаядеревья.Вместотогочтобырассматриватьпространство всех возможных подграфов, рассматриваются пути вдеревьях и графах, которые соответствуют синтаксическим ирасширенным группам.Для того чтобы оценить сложность обобщения двух чащразбора, рассмотрим абзац, состоящий из 5 предложений, каждое изкоторых имеет длину в 15 слов.

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

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