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

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

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

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

Со структурной точки зрения такаяпроекция – это максимальные по вложению поддеревья графа сдополнительными свойствами. Пример проекций для двух абзацевприведен в разделе 2.3.2.Операция пересечения двух групп определяется внутри каждоготипа групп [73]. Пересечение на проекциях заключается в попарномпересечении групп для каждого типа из двух множеств и выборенаибольших по вложению подгрупп. Работа с проекциями позволяетдобиться экономии по сложности (переход к работе с деревьями) беззначимого ущерба для качества результата (группы учитывают всенеобходимые лингвистические связи внутри абзаца).662.5.2 Построение множества расширенных группРассмотрим подробнее алгоритм нахождения заданной вышепроекции, т.е.

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

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

Полученные на уровне групп обобщения можно интерпретироватькак набор путей в результирующих общих поддеревьях [73].2.6 Эксперименты по поиску с использованием сходства междуабзацами2.6.1 Схема экспериментаПопробуем оценить, как обобщение чащ разбора можетулучшить поиск в ситуации, когда сформулированный в видепоискового запроса вопрос и потенциальный ответ на негопредставляют собой текстовые абзацы.

Количественным результатомоценки является точность в процентах, вычисленная как среднее по68100 поисковым запросам. В данной работе использовались параметрыпроведения эксперимента, описанные в [73].Оценка основана на повторном ранжировании поисковыхрезультатов, полученных с помощью API поисковой системы Bing,осуществляемом на базе меры сходства чащ разбора. Сходствоопределяется как общее число вершин в наибольшем общем подграфедля двух чащ. Приближенное значение этой оценки было полученопутем подсчета количества слов в наибольших общих подгруппах сучетом весов для частей речи [73].Полученные результаты приведены в таблице. Для оценки былисмоделированы следующие ситуации в трех прикладных областях: Выдача рекомендаций по товарам: агент рекомендательнойсистемы читает чаты о продуктах и находит в сети релевантнуюинформацию о каждом продукте. Выдачарекомендацийрекомендательнойсистемыпочитаетпутешествиям:чатысагентописаниемпутешествий и находит в сети релевантную информацию оботелях, курортах и т.д. Выдача рекомендаций в социальных cетях (на примереFacebook): агент рекомендательной системы читает чаты изаписи на «стене» пользователей социальной сети и отбираетинформацию, которая может быть интересна друзьям этихпользователей.В каждой из этих областей на основе Интернет-источниковвыбирался кусок текста, далее формировался запрос, а затем69осуществлялась фильтрация результатов поиска, полученных спомощью API поисковой системы Bing.2.6.2 Результаты экспериментовПоиск с использованиемобобщений для отдельныхпредложенийПоиск с помощью чащ,построенных нафрагментахПоиск с помощью чащ,построенных наоригинальных абзацахПоиск с использованиемобобщения чащ на графах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 составноепредложение2 предложения3 предложения4 предложения54.563.265.368.167.252.349.750.960.95758.362.161.762.063.763.064.663.961.962.758.1564.7568.7570.3369.25Тип запросаСложность запросаИсходный поиск в BingТаблица 2.1.

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

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

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

В таких чащах в среднем содержится10 синтаксических групп в каждом предложении и 10 дуг междупредложениями, которые дают нам до 40 расширенных групп.Поэтому для сопоставления таких чащ разбора необходимо попарнообобщить около 50 синтаксических групп и 40 расширенных групп изодной чащи с таким же множеством групп для другой. С учетомобобщения отдельных существительных и глагольных групп этосоставляет порядка 2 * 45 * 45 обобщений, сопровождаемыхпроверкой вхождения результатов друг в друга.

Каждое обобщениесостоит не более чем из 12 сравнений строк, если принять среднийразмер группы за 5 слов. Следовательно, в среднем обобщение двухчащ включает в себя 2 * 45 * 45 * 12 * 5 операций. Так как сравнениестрок занимает несколько микросекунд, обобщение занимает всреднем 100 миллисекунд без использования индекса. Однако впромышленной поисковой системе, где группы хранятся в обратноминдексе,операцияобобщенияможетбытьвыполненазафиксированное время, не зависящее от размера индекса [93].2.8 Кластеризация результатов поиска2.8.1 Решетка замкнутых описаний на чащахОбработка результатов поиска и их интерпретация ‒ одно изважнейших направлений в промышленном информационном поиске.Проблемаотображениярезультатовчастосводитсяких72ранжированию по одному числовому показателю ‒ релевантности. Вэтом случае результаты выводятся последовательно в соответствии сэтим значением.

Однако в реальных системах ранжированиепроизводится не только не только по релевантности, но и по месту,времени, ожидаемому доходу от результатов поиска и другимпараметрам.Также существуют и альтернативные варианты отображениярезультатов поиска, использующие различные виды кластеризации[137, 138].

На практике, как правило, используется комбинация двухподходов: сначала результаты ранжируются по релевантности и изних отбираются N лучших. А затем эти результаты тем или инымобразом группируются. Основное преимущество кластеризациизаключается в том, что похожие или дублирующие друг другарезультаты поиска объединяются, так что пользователь можетработать с кластерами результатов, а не с отдельными результатамипоиска.Одним из наиболее перспективных методов кластеризацииявляется концептуальная кластеризация, объединяющая объекты врешетку замкнутых множеств. Такая кластеризация удобна, например,когда поисковая выдача содержит результаты из разных источников:новости, документы, картинки.

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

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