Диссертация (1137241), страница 11
Текст из файла (страница 11)
В таких чащах в среднем содержится10 синтаксических групп в каждом предложении и 10 дуг междупредложениями, которые дают нам до 40 расширенных групп.Поэтому для сопоставления таких чащ разбора необходимо попарнообобщить около 50 синтаксических групп и 40 расширенных групп изодной чащи с таким же множеством групп для другой.
С учетомобобщения отдельных существительных и глагольных групп этосоставляет порядка 2 * 45 * 45 обобщений, сопровождаемыхпроверкой вхождения результатов друг в друга. Каждое обобщениесостоит не более чем из 12 сравнений строк, если принять среднийразмер группы за 5 слов. Следовательно, в среднем обобщение двухчащ включает в себя 2 * 45 * 45 * 12 * 5 операций. Так как сравнениестрок занимает несколько микросекунд, обобщение занимает всреднем 100 миллисекунд без использования индекса. Однако в71промышленной поисковой системе, где группы хранятся в обратноминдексе,операцияобобщенияможетбытьвыполненазафиксированное время, не зависящее от размера индекса [70].2.8 Кластеризация результатов поиска2.8.1 Решетка замкнутых описаний на чащахОбработка результатов поиска и их интерпретация ‒ одно изважнейших направлений в промышленном информационном поиске.Проблемаотображениярезультатовчастосводитсякихранжированию по одному числовому показателю ‒ релевантности.
Вэтом случае результаты выводятся последовательно в соответствии сэтим значением. Однако в реальных системах ранжированиепроизводится не только не только по релевантности, но и по месту,времени, ожидаемому доходу от результатов поиска и другимпараметрам.Также существуют и альтернативные варианты отображениярезультатов поиска, использующие различные виды кластеризации[109, 110]. На практике, как правило, используется комбинация двухподходов: сначала результаты ранжируются по релевантности и изних отбираются N лучших.
А затем эти результаты тем или инымобразом группируются. Основное преимущество кластеризациизаключается в том, что похожие или дублирующие друг другарезультаты поиска объединяются, так что пользователь можетработать с кластерами результатов, а не с отдельными результатамипоиска.Одним из наиболее перспективных методов кластеризацииявляется концептуальная кластеризация, объединяющая объекты врешетку замкнутых множеств. Такая кластеризация удобна, например,когда поисковая выдача содержит результаты из разных источников:72новости, документы, картинки.
Если речь идет о социальном поиске,то кластеризация позволяет группировать ответы и темы попользователям и сообществам. Кроме того, решетка автоматическиформирует иерархию и позволяет работать на нужном уровнесходства (например, с большими группами не очень похожихрезультатовилисмаленькимигруппамипочтиодинаковыхрезультатов).ПростейшимявляетсявариантомиспользованиеНедостаткомвданномконцептуальнойрешетокслучаепонятийявляетсякластеризации[103,104,105,108].необходимостьпредварительного задания множества признаков и проведенияшкалирования для получения формального контекста. При этомнеизбежна частичная потеря или огрубление информации.Более сложным случаем является построение решетки на основезамкнутых структурных описаний ‒ узорных структур.
В этом случаемы сможем полностью использовать краткое текстовое описаниерезультата ‒ поисковый сниппет.Весь необходимый аппарат уже был введен выше. Структурнымописанием каждого результата будет являться чаща разбора.Решеточная операция пересечения – это операция сходства чащразбора. Имея данную операцию, для построения самой решеткиможно использовать любой стандартный алгоритм, например,AddIntent [19]. Также в главах 1 и 2 были введены проекции узорныхструктур. Проекция предоставляет нам приближенное структурноеописание, а также способ пересечения этих описаний.
Использованиепроекций для чащ позволяет улучшить временную и вычислительнуюсложность построения решетки: от операций на графах мы переходимк операциям на деревьях.73Важный момент заключается в том, что используемое описаниеможно расширять. Чаща разбора ‒ это первое «измерение» в описаниипоискового результата. Помимо этого, можно также добавлять другиеизмерения, например, временной интервал, для которого актуаленданный результат, целевую аудиторию (например, в виде множества)и т.д.
С математической точки зрения, для добавления новогоизмерения необходимо определить коммутативную и ассоциативнуюоперацию сходства на таких описаниях, которая во многих случаяхвводится естественным образом. Например, для множеств этопересечение, для интервалов ‒ объединение. Необходимо такжеотметить, что кластеризацию можно применять к произвольнымнаборам коротких текстов, а поисковая выдача просто является однимиз приложений данного подхода.2.8.2 Алгоритм кластеризации2.8.2.1 Кластеризация с использованием полного описанияТаким образом, алгоритм кластеризации в случае использованияобобщения на полном описании выглядит следующим образом:1. Взять множество текстов (поисковую выдачу) T.2. Для каждого результата ti T построить чащу разбора pi P .3.
Используяоперациюобобщениячащразборавкачестверешеточной операции пересечения , построить узорную решеткуT , P, , для всех текстов с помощью любого стандартногоалгоритма (например, AddIntent или Замыкай-По-Одному).4. Получить иерархические кластеры ‒ узорные понятия решетки.2.8.2.2 Кластеризация с использованием проекцийПри использовании приближенного представления абзацевалгоритм немного модифицируется:741. Взять множество текстов (поисковую выдачу) T.2.
Для каждого результата ti T построить проекцию чащи разбора pi P .3. Используя операцию обобщения проекций в качестве решеточнойоперации пересечения, построить проекцию узорной решеткиT , P , , длявсехтекстовспомощьюлюбогостандартного алгоритма (например, AddIntent или Замыкай-ПоОдному).4. Получить иерархические кластеры ‒ проекции узорных понятийрешетки.2.8.3 Пример кластеризации на проекцияхРассмотрим 3 новости и построим для них проекцию узорнойструктуры:1) At least 9 people were killed and 43 others wounded in shootings andbomb attacks, including four car bombings, in central and western Iraq onThursday, the police said.
A car bomb parked near the entrance of the localgovernment compound in Anbar's provincial capital of Ramadi, some 110km west of Baghdad, detonated in the morning near a convoy of vehiclescarrying the provincial governor Qassim al-Fahdawi, a provincial policesource told Xinhua on condition of anonymity.2) Officials say a car bomb in northeast Baghdad killed four people, whileanother bombing at a market in the central part of the capital killed at leasttwo and wounded many more.
Security officials also say at least twopolicemen were killed by a suicide car bomb attack in the northern city ofMosul. No group has claimed responsibility for the attacks, which occurredin both Sunni and Shi'ite neighborhoods.3) A car bombing in Damascus has killed at least nine security forces, withaid groups urging the evacuation of civilians trapped in the embattledSyrian town of Qusayr. The Syrian Observatory for Human Rights said onSunday the explosion, in the east of the capital, appeared to have beencarried out by the extremist Al-Nusra Front, which is allied to al-Qaeda,although there was no immediate confirmation.
In Lebanon, security75sources said two rockets fired from Syria landed in a border area, andIsraeli war planes could be heard flying low over several parts of thecountry.Нижнее понятие соответствует наиболее общему описанию ивсем объектам, имеющим это описание. В данном случае это пустоемножество объектов и все максимальные по вложению группы из трехновостей.На следующем уровне мы получаем понятия, каждое из которыхсодержит 1 объект и его описание.Узорное содержание для первой новости:[[NP [JJS-least CD-9 NNS-people ], NP [CD-43 NNS-others ], NP [NNSshootings CC-and NN-bomb NNS-attacks ], NP [NNS-shootings ], NP [NN-bomb NNSattacks ], NP [CD-four NN-car NNS-bombings ], NP [JJ-central CC-and JJ-westernNNP-Iraq ], NP [JJ-central ], NP [JJ-western NNP-Iraq ], NP [NNP-Thursday ], NP[DT-the NN-police ], NP [DT-A NN-car NN-bomb ], NP [DT-the NN-entrance IN-ofDT-the JJ-local NN-government NN-compound IN-in NNP-Anbar POS-'s JJ-provincialNN-capital IN-of NNP-Ramadi ,-, DT-some CD-110 NN-km NN-west IN-of NNPBaghdad ], NP [DT-the NN-entrance ]…, и т.д.Узорное содержание для второй новости:[[NP [NNS-Officials ], NP [DT-a NN-car NN-bomb IN-in JJ-northeast NNPBaghdad ], NP [DT-a NN-car NN-bomb ], NP [JJ-northeast NNP-Baghdad ], NP [CDfour NNS-people ], NP [DT-another NN-bombing IN-at DT-a NN-market IN-in DT-theJJ-central NN-part IN-of DT-the NN-capital ], NP [DT-another NN-bombing ], NP[DT-a NN-market IN-in DT-the JJ-central NN-part IN-of DT-the NN-capital],…и т.д.Узорное содержание для третьей новости:[[NP [DT-A NN-car NN-bombing IN-in NNP-Damascus ], NP [DT-A NN-carNN-bombing ], NP [NNP-Damascus ], NP [JJS-least CD-nine NN-security NNS-forces], NP [NN-aid NNS-groups VBG-urging DT-the NN-evacuation IN-of NNS-civiliansVBN-trapped IN-in DT-the JJ-embattled JJ-Syrian NN-town IN-of NNP-Qusayr ], NP[NN-aid NNS-groups ], …)76Понятие верхнего уровня содержит группы, которые являютсяобщими для всех текстов.
В данном случае все 3 текста повествуют овзрывах машин возле столиц (car bombing near capitals), чтовыражается фрагментами [DT-a NN-car NN-bombing ], [DT-the NNcapital ], [VBN-killed ], [JJS-least CD-* NN-* ]. Символ ‘*’ означает«произвольное слово, относящееся к данной части речи».Другие группы в данном узорном содержании соответствуютсинтаксическим шаблонам: [IN-of DT-the ], [NNS-* IN-* DT-* NN-* ].На уровне пересечения пар текстов наиболее интересным являетсяпонятие, содержащее тексты 1 и 2. Они описывают одно и то жесобытие, поэтому место происшествия совпадает: [NN-* NN-* IN-inNNP-baghdad]. В обоих текстах используются одинаковые термины:[NN-* NN-bomb NN-attack ], [NNS-attacks], и информация опострадавших: [VBD-wounded], [VBD-were VBN-killed ], [CD-* NNSpeople ], [CD-four NNS-* ].Рис 2.3.
Проекция узорной структуры для новостных текстов2.9 ВыводыВ работах [57, 71] было показано, как использование богатогонабора лингвистической информации – синтаксических связей междусловами – улучшает релевантность поиска. Для того чтобы, помимо77синтаксической информации, воспользоваться и семантической, былоиспользовано понятие чащи разбора и предложен способ вычислениясходствамеждутекстами,основанныйнаобобщениисоответствующих им чащ разбора. Также была построена и примененак задаче повторного ранжирования результатов поиска по ключевымсловам технология обобщения чащ разбора, представляемых в виденаборов групп.Для построения чащ использовались различные виды связеймеждусловамивпредложениях:кореферентныесвязи,таксономические отношения, такие как «быть частным случаем»,«быть обобщением», «та же сущность» и т.д., а также семантическиесвязи, полученные на базе теории риторических структур и теорииречевых актов. Было показано, что если ответ содержится внескольких предложениях, то применение чащи позволяет повыситьрелевантность поиска.Также было показано, что операция сходства или обобщенияабзацев текста может быть естественным образом определена спомощью математического аппарата узорных структур.
При этомобобщение с использованием общих подграфов точно описывается втерминах пересечения описаний объектов, а синтаксические ирасширенные группы соответствуют взятию проекций от исходныхописаний.Традиционное машинное обучение на языковых структурахограничено работой с формами и частотами ключевых слов. В то жевремябольшинствосемантическихтеорийнеявляютсявычислительными, они моделируют определенный набор отношениймежду последовательными состояниями. В данной работе былапредпринята попытка совместить два подхода: использовать всюинформацию, полученную из дерева синтаксического разбора,78дополнив ее сведениями из семантических теорий, допускающихвычислительную обработку.793.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
