Диссертация (1137218), страница 11
Текст из файла (страница 11)
Если речь идет о социальном поиске,то кластеризация позволяет группировать ответы и темы попользователям и сообществам. Кроме того, решетка автоматическиформирует иерархию и позволяет работать на нужном уровнесходства (например, с большими группами не очень похожихрезультатоврезультатов).илисмаленькимигруппамипочтиодинаковых73Простейшимвариантомконцептуальнойкластеризацииявляется использование решеток понятий [129,130,131,132,133,136].Недостаткомвданномслучаеявляетсянеобходимостьпредварительного задания множества признаков и проведенияшкалирования для получения формального контекста. При этомнеизбежна частичная потеря или огрубление информации.Более сложным случаем является построение решетки на основезамкнутых структурных описаний ‒ узорных структур.
В этом случаемы сможем полностью использовать краткое текстовое описаниерезультата ‒ поисковый сниппет [50,51].Весь необходимый аппарат уже был введен выше. Структурнымописанием каждого результата будет являться чаща разбора.Решеточная операция пересечения – это операция сходства чащразбора. Имея данную операцию, для построения самой решеткиможно использовать любой стандартный алгоритм, например,AddIntent [29].
Также в главах 1 и 2 были введены проекции узорныхструктур. Проекция предоставляет нам приближенное структурноеописание, а также способ пересечения этих описаний. Использованиепроекций для чащ позволяет улучшить временную и вычислительнуюсложность построения решетки: от операций на графах мы переходимк операциям на деревьях.Важный момент заключается в том, что используемое описаниеможно расширять.
Чаща разбора ‒ это первое «измерение» в описаниипоискового результата. Помимо этого, можно также добавлять другиеизмерения, например, временной интервал, для которого актуаленданный результат, целевую аудиторию (например, в виде множества)и т.д. С математической точки зрения, для добавления новогоизмерения необходимо определить коммутативную и ассоциативнуюоперацию сходства на таких описаниях, которая во многих случаях74вводится естественным образом.
Например, для множеств этопересечение, для интервалов ‒ объединение. Необходимо такжеотметить, что кластеризацию можно применять к произвольнымнаборам коротких текстов, а группировка результатов поисковойвыдачи является лишь одним из приложений данного подхода.Результатом применения описываемого подхода к произвольнойколлекциикороткихпредставлениетекстовэтойбудетколлекции,являтьсятаксономическоеучитывающеесинтактико-дискурсивное сходство входящих в неё текстов.2.8.2 Алгоритм кластеризации2.8.2.1 Кластеризация с использованием полного описанияАлгоритм кластеризации в случае использования обобщения наполном описании выглядит следующим образом:1.
Взять множество текстов (поисковую выдачу) T.2. Для каждого результата ti T построить чащу разбора pi P .3. Используяоперациюобобщениячащразборавкачестверешеточной операции пересечения , построить узорную решеткуT , P, , для всех текстов с помощью любого стандартногоалгоритма (например, AddIntent или Замыкай-По-Одному).4. Получить иерархические кластеры ‒ узорные понятия решетки.2.8.2.2 Кластеризация с использованием проекцийПри использовании приближенного представления абзацевалгоритм немного модифицируется:1.
Взять множество текстов (поисковую выдачу) T.2. Для каждого результата ti T построить проекцию чащи разбора pi P .753. Используя операцию обобщения проекций в качестве решеточнойоперации пересечения, построить проекцию узорной решетки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, securitysources said two rockets fired from Syria landed in a border area, andIsraeli war planes could be heard flying low over several parts of thecountry.76Нижнее понятие соответствует наиболее общему описанию ивсем объектам, имеющим это описание. В данном случае это пустоемножество объектов и все максимальные по вложению группы из трехновостей.На следующем уровне мы получаем понятия, каждое из которыхсодержит 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 ], …)Понятие верхнего уровня содержит группы, которые являютсяобщими для всех текстов.
В данном случае все 3 текста повествуют овзрывах машин возле столиц (car bombing near capitals), чтовыражается фрагментами [DT-a NN-car NN-bombing ], [DT-the NN-77capital ], [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 ВыводыВ работах [73, 94] было показано, как использование богатогонабора лингвистической информации – синтаксических связей междусловами – улучшает релевантность поиска. Для того чтобы, помимосинтаксической информации, воспользоваться и дискурсивной, былоиспользовано понятие чащи разбора и предложен способ вычислениясходствамеждутекстами,основанныйнаобобщениисоответствующих им чащ разбора.
Также была построена и применена78к задаче повторного ранжирования результатов поиска по ключевымсловам технология обобщения чащ разбора, представляемых в виденаборов групп.Для построения чащ использовались различные виды связеймеждусловамивпредложениях:кореферентныесвязи,таксономические отношения, такие как «быть частным случаем»,«быть обобщением» и т.д., а также дискурсивные связи, полученныена базе теории риторических структур и теории речевых актов.
Былопоказано, что если ответ содержится в нескольких предложениях, топрименение чащи позволяет повысить релевантность поиска.Также было показано, что операция сходства или обобщенияабзацев текста может быть естественным образом определена спомощью математического аппарата узорных структур. При этомобобщение с использованием общих подграфов точно описывается втерминах пересечения описаний объектов, а синтаксические ирасширенные группы соответствуют взятию проекций от исходныхописаний.Традиционное машинное обучение на языковых структурахограничено работой с формами и частотами ключевых слов.
В то жевремябольшинствосемантическихтеорийнеявляютсявычислительными, они моделируют определенный набор отношениймежду последовательными состояниями. В данной работе былапредпринята попытка совместить два подхода: использовать всюинформацию, полученную из дерева синтаксического разбора,дополнив ее сведениями из дискурсивных теорий, допускающихвычислительную обработку.793.
Применение ядер для классификации короткихтекстов3.1 ВведениеНесмотряназначительныеусилияпоформулированиюполноценной теории, описывающей связь между синтаксисом исемантикой, она все ещё не разработана. Однако конструированиесинтаксическихпризнаковдляавтоматическогообучениянасинтаксических структурах можно назвать мейнстримом.
Одно изрешений для работы с такими признаками – построение и вычислениеядер на деревьях синтаксического разбора. Функция ядра (convolutionkernel) на деревьях [76] задает пространство признаков, состоящее извозможных типов поддеревьев деревьев разбора, и подсчитываетколичество общих подструктур в качестве синтаксической близостимежду деревьями. Этот подход имеет несколько приложений вразличных задачах компьютерной лингвистики, в частности, ониспользуется для извлечения отношений [78, 79], распознаванияименованных сущностей [111] и выявления семантических ролей(Semantic Role Labeling) [112], разрешения анафоры на местоимениях[119], классификации вопросов [118] и машинного перевода [120].Свойство ядер генерировать большие объемы признаковявляется полезным для быстрого моделирования новых и не оченьхорошоизученныхлингвистическихявленийвобучающихалгоритмах.
Однако всегда возможно вручную смоделироватьпризнаки для линейных ядер, для того чтобы добиться высокойточности и хорошей скорости работы, несмотря на то что сложностьядер на деревьях может помешать их применению в реальныхприложениях.80Многие обучающие алгоритмы, такие как Метод ОпорныхВекторов (SVM) [81], могут работать напрямую с ядрами с помощьюзамены скалярного произведения на конкретную функцию ядра(«трюк с ядрами»). Это полезное свойство ядер делает ихэффективным решением для моделирования структурных объектов взадачах обработки текстов на естественном языке. Некоторые их этихзадачтребуютвычислениядискурсивныхсвойствабзацев,содержащих несколько предложений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
