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

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

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

Чащаразбора описывает синтактико-семантическую структуру абзаца.Определение1.16.Чащейразборатекстовогоабзацаназывается совокупность множества деревьев разбора предложенийабзацаисвязейнесколькихтипов,устанавливаемыхмеждувершинами деревьев. Каждая связь – это упорядоченная пара вершиндеревьев разбора, причем связаны между собой могут быть каквершины одного дерева, так и вершины разных деревьев.Со структурной точки зрения чаща представляет собойориентированный граф, который включает в себя деревья разбора, атакже дуги, соответствующие несинтаксическим связям.41Рисунок 1.3. Пример графического представления чащи разбора1.4.5 Семантико-коммуникативное представление текстаЧаща разбора представляет собой непосредственное развитиеидеи синтаксических деревьев разбора на случай абзаца.

При этомфактически чаща предполагает частично независимое построениесинтаксических и семантических связей. Более того, разные типысемантических связей также строятся независимо друг от друга.Крометого,еёприменениепредполагаетналичиеразвитыхинструментов, позволяющих автоматически конструировать деревья исвязи между ними. Это требование в полной мере выполняется дляанглийского языка, который и рассматривался в экспериментах.Возможной альтернативой чаще может служить представление,основанноеразработаннойнаИ.использованиитеорииМельчуком.Описанные«Смысл<->Текст»,имсемантико-42коммуникативные структуры предложений [75] обладают рядомважных свойств:1.

Применимы к языкам со свободным порядком слов, в том числе ик русскому языку.2. Описывают многие отношения и связи, известные из другихтеорий, такие как риторические отношения, анафора и т.д.3. Описывают текст с помощью системы 8 независимых парпротивоположных категорий: тематичность («темы» и «ремы»),наличие диалога и т.д.4.

Не требуют отдельного синтаксического анализа текста.5. Так же как и чаща разбора, позволяют получить графовоепредставление текста.Очевиднымнедостаткомтакогопредставленияявляетсяотсутствие полноценного математического описания данной теории ипрограммной реализации (выходящей за рамки построения деревьевзависимостей).Однако данное представление являетсявесьмаперспективным с точки зрения применения модели и методовсходства, описанных в нашей работе, для других языков, помимоанглийского. Тем не менее, в экспериментальных исследованияхпредпочтение было отдано чаще разбора.1.5 Ядра в задаче машинного обученияВ нашей работе мы будем исследовать применение ядер надеревьях в задаче классификации коротких текстов.

Предлагаемыйметод допускает использование различных видов ядерных функций надеревьях: неглубоких ядер, частичных ядер и т.д. В нашихэкспериментах мы применяли ядра простейшего вида. Такой выборбыл обусловлен рядом факторов. Во-первых, требовалась связность43порождаемыхподструктур,отсутствоваликорректирующиекоэффициенты («штрафы» за размер подструктур). Во-вторых,постановка задачи не предполагала использование предикатныхсемантических связей, для исследования которых, как правило,применяютсянеглубокие(shallow)ядра.В-третьих,важнойкомпонентой экспериментов было сравнение с существующимподходом к классификации предложений, использующим именно ядрас запретом на несвязность подструктур.1.5.1 Применение функции ядра в задачах машинного обученияОпределение 1.17.

Отображение K : X  X   называетсяядром или ядерной функцией [74], если оно обладает следующимисвойствами:1. Симметричность: x, y  X K ( x, y)  K ( y, x) .2. Неотрицательная определенность: N x1, , xN  X матрица K,задаваемаякакKij  K  xi , x j  ,являетсянеотрицательноопределенной.Ядерные функции применяются в сочетании с широким классомалгоритмов обучения, основанных на скалярном произведении ввекторныхпространствах.Ихприменениеобусловленотакназываемым трюком с ядрами (kernel trick) [59]. Пусть у нас имеетсяотображение  : X  V , где V ‒ пространство со скалярнымпроизведением, например, n .

Тогда ядро можно определить какскалярное произведение в этом пространстве: K  x, y     x     y  V .Этот прием в ряде случаев позволяет заменить трудоемкиевычисленияисходныхотображенийнаэлементахисходногомножества на подсчет скалярного произведения. Данный прием, вчастности, применяется в Методе Опорных Векторов (Support VectorMachine)[64].Основнаяидеяэтогометода‒нахождение44разделяющей гиперплоскости вида̿ )̿ ̿, где ̿ -вектор признаков, отвечающий классифицируемому объекту, а̿∈– параметры алгоритма, обучаемые согласно принципу∈минимизации риска.

Применение ядер позволяет использоватьданный метод для объектов, имеющих сложную структуру и оченьбольшое число свойств, не прибегая к явному выделению этихпризнаков. Пусть задано отображение (соответствующее выделениеобучающихпризнаковдляисходных : X  n .объектов)Перепишем выражение для разделяющей гиперплоскости следующимобразом:ll lH ( z )    yii zi   z  b   yii zi  z  b   yii ( xi )   ( x)  bi 1i 1 i 1гдевзависимостиоткласса,∈ ,;zi  i 1, l ‒ примеры из обучающей выборки.Как уже отмечалось выше, вместо применения функцииможно напрямую считатьоперироватьв ).

Ядерная функция позволяет неявнопространствахсогромнымчисломпризнаков(потенциально бесконечномерных).1.5.2 Некоторые виды ядерРассмотрим некоторые виды ядер, задаваемые для структур,представляющих текстовые строки и предложения.1.5.2.1 Ядра для строкНаиболеепростымпримером представляющейтекстовуюинформацию структуры, для которой можно определить функциюядра, являются строки. Строковые ядра [86] подсчитывают количествообщих для двух последовательностей подстрок, возможно, с45пропусками, например, могут быть опущены некоторые символыпервой строки. Пропуски учитываются в весе целевых подстрок.Пусть‒ конечный алфавит,∈строк. Для каждой строки– множество всехобозначает длину строки, самустроку можно записать в виде:, гдевыбор подстроки с i-го по j-й символ: i : j  обозначает∈ ,-.Определение 1.18.

u – подпоследовательность всуществуетпоследовательностьi u   , такая что 1  i1 индексов̿(, еслигде),или, для краткости записи,̿.Через)̿ обозначают расстояние между первым и последниминдексом подпоследовательности в оригинальной строке:( )̿. С помощью 1  2 обозначается конкатенация строк∈.Множествовсехподстрокданногопространство признаков, обозначаемоестрокув пространство⊂корпусаобразует. Чтобы отобразить, можно использовать следующий класс( ̿)для некоторого≤ . Такие функцииподсчитывают число вхождений u в строкуи назначают им весфункций:( )̿)∑̿̿, пропорциональный их длине.

Таким образом, скалярноепроизведение в пространстве признаков для двух строкивозвращает взвешенную по частоте встречаемости и длинам суммувсехобщихподпоследовательностей.Использующаявведенноеотображение функция ядра будет выглядеть следующим образом:46SK  1 , 2    u* u  1   u  1    u*  I :u   I  1  u*  I :u   I   I :u 11122I2 11d  I1 I 2 :u  2  I 2  dI  2d  I1  d  I 2 Данное ядро имеет следующие свойства:1. Длинные подпоследовательности получают меньший вес;2. Допускается пропуск символов исходной строки;3. Пропуски учитываются в весовой функции );4.

Символами можно считать слова, тогда мы получим ядро дляпоследовательностей слов.1.5.2.2 Ядро на синтаксических деревьяхОсновная идея ядер для деревьев [59], как и в случае состроками, заключается в том, чтобы подсчитывать количество общихподструктур для двух деревьевибез явного учета пространствавсех подструктур.Пусть– множество всех поддеревьев, а)‒ индикаторная функция, которая равна 1, если целевое поддеревои имеет корнем вершину n. Ядро для)вершин∑∑∈) где∈деревьев)∑Функцияи)определяется каки‒ множествасоответственно,а).определяетколичествообщихфрагментов,начинающихся в вершинах и , и зависит от типа фрагмента.В простейшем случае в качестве подструктур рассматриваютсямножества ребер и вершин из исходного дерева, которое такжеобразуют деревья с дополнительным ограничением: для любой47вершины должны учитываться или все, или ни одна из ее дочернихвершин.Дляподсчетаобщегоколичестватакихподструктур,начинающихся в вершинах и , используется следующий видфункции :1.

если продукции (вершина и её прямые потомки) в вершинах и не совпадают, то ).2. если продукции в вершинах одинаковы, и все дочерние вершины )являются листьями, то.‒ дополнительныйкоэффициент, позволяющий нормализовать вычисление ядер длябольших структур.3. если продукции в вершинах совпадают, и вершины не являютсяпредтерминальными (то есть имеющими только листья в качестведочерних)вершин),∏)(товводится(дочерних вершин для , рекурсивное)))) гдевыражение:) ‒ количество)‒ j-й ребенок вершины n.1.5.2.3 Неглубокое семантическое ядроДанный вид ядерной функции применяется для обучения надеревьях, представляющих семантическую структуру текста [62].Подструктуры в этом случае почти полностью совпадают со случаемядер на синтаксических деревьях, единственное различие – вкладспециального типа вершин, помеченных null, должен быть нулевым.Этонеобходимо,посколькуядроприменяетсядлядеревьевспециального вида, содержащих «слотовые» вершины, потомкикоторых могут быть помечены как null.48Алгоритм вычисления функциименяется следующимобразом:1.

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

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