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

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

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

Применима к языкам со свободным порядком слов, в том числе и крусскому языку.2. Описывает многие отношения и связи, известные из другихтеорий, такие как синтаксические связи, анафора, семантикокоммуникативные связи [97] и т.д.3. Комбинирует синтаксический и семантический уровни анализа.4.

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

В нашихэкспериментах мы применяли ядра простейшего вида. Такой выборбыл обусловлен рядом факторов. Во-первых, требовалась связностьпорождаемыхподструктур,отсутствоваликорректирующиекоэффициенты («штрафы» за размер подструктур). Во-вторых,43постановка задачи не предполагала использование предикатныхсемантических связей, для исследования которых, как правило,применяютсянеглубокие(shallow)ядра.В-третьих,важнойкомпонентой экспериментов было сравнение с существующимподходом к классификации предложений, использующим именно ядрас запретом на несвязность подструктур.1.5.1 Применение ядерных функций в задачах машинногообученияОпределение 1.17. Отображение K : X  X   называетсяядром или ядерной функцией [96], если оно обладает следующимисвойствами:1. Симметричность: x, y  X K ( x, y)  K ( y, x) .2.

Неотрицательная определенность: N x1,задаваемаякакKij  K  xi , x j  ,, xN  X матрица K,являетсянеотрицательноопределенной.Ядерные функции применяются в сочетании с широким классомалгоритмов обучения, основанных на скалярном произведении ввекторныхпространствах.Ихприменениеобусловленотакназываемым трюком с ядрами (kernel trick) [76]. Пусть у нас имеетсяотображение  : X  V , где V ‒ пространство со скалярнымпроизведением, например, n . Тогда ядро можно определить какскалярное произведение в этом пространстве: K  x, y     x     y  .VЭтот прием в ряде случаев позволяет заменить трудоемкиевычисленияисходныхотображенийнаэлементахисходногомножества на подсчет скалярного произведения. Данный прием, вчастности, применяется в Методе Опорных Векторов (Support VectorMachine)[81].Основнаяидеяэтогометода‒нахождениеразделяющей гиперплоскости вида (̿ ) = ̿ ∙ ̿ + = 0, где ̿ -44вектор признаков, отвечающий классифицируемому объекту, аw̿ ∈ Rn , b ∈ Rn – параметры алгоритма, обучаемые согласно принципуминимизации риска.

Применение ядер позволяет использоватьданный метод для объектов, имеющих сложную структуру и оченьбольшое число свойств, не прибегая к явному выделению этихпризнаков. Пусть задано отображение (соответствующее выделениеобучающихпризнаковдляисходныхобъектов) : 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где = ±1взависимостиоткласса,αi ∈ R,αi ≥ 0;zi  i 1, l ‒ примеры из обучающей выборки.Как уже отмечалось выше, вместо применения функции ϕможно напрямую считать ( , ). Ядерная функция позволяет неявнооперироватьвпространствахсогромнымчисломпризнаков(потенциально бесконечномерных).1.5.2 Некоторые виды ядерРассмотрим некоторые виды ядер, задаваемые для структур,представляющих текстовые строки и предложения.1.5.2.1 Ядра для строкНаиболеепростымпримером представляющейтекстовуюинформацию структуры, для которой можно определить функциюядра,являютсястроки.Строковыеядра[110]подсчитываютколичество общих для двух последовательностей подстрок, возможно,с пропусками, например, могут быть опущены некоторые символыпервой строки.

Пропуски учитываются в весе целевых подстрок.45nПусть Σ ‒ конечный алфавит, Σ * =∪∞n=0 Σ – множество всехстрок. Для каждой строки σ ∈ Σ * , |σ| обозначает длину строки, самустроку можно записать в виде: s1 . . s|σ| , где si ∈ Σ,  i : j  обозначаетвыбор подстроки с i-го по j-й символ: si si+1 . . sj-1 sj .Определение 1.18. u – подпоследовательность в σ, еслисуществует1  i1 последовательностьI̿ = (i1 , … , i|u| ),,индексовгдеi u   , такая что = 1 . . || или, для краткости записи, = []̿ .Через d(I)̿ обозначают расстояние между первым и последниминдексом подпоследовательности в оригинальной строке: d(I)̿ =i|u| -i1 + 1.

С помощью 1  2 обозначается конкатенация строкσ1 , σ2 ∈ Σ * .Множествовсехподстрокданногокорпусаобразуетпространство признаков, обозначаемое ℱ ⊂ ∗ . Чтобы отобразитьстроку в пространство ℝ∞ , можно использовать следующий классфункций: ϕu (σ) = ∑I̿:u=s[I̿] λd(I̿) для некоторого ≤ 1. Такие функцииподсчитывают число вхождений u в строку и назначают им вес()̿ , пропорциональный их длине. Таким образом, скалярноепроизведение в пространстве признаков для двух строк 1 и 2возвращает взвешенную по частоте встречаемости и длинам суммувсехобщихподпоследовательностей.Использующаявведенноеотображение функция ядра будет выглядеть следующим образом:SK  1 , 2    u* u  1   u  1    u*  I :u   I  1  u*  I :u   I   I :u 11122I2  d  I  d  I1211d  I1 I 2 :u  2  I 2  dI  246Данное ядро имеет следующие свойства:1.

Длинные подпоследовательности получают меньший вес;2. Допускается пропуск символов исходной строки;3. Пропуски учитываются в весовой функции (. );4. Символами можно считать слова, тогда мы получим ядро дляпоследовательностей слов.1.5.2.2 Ядро на синтаксических деревьяхОсновная идея ядер для деревьев [76], как и в случае состроками, заключается в том, чтобы подсчитывать количество общихподструктур для двух деревьев T1 и T2 без явного учета пространствавсех подструктур.Пусть ℱ = {1 , 2 , … , |ℱ| } – множество всех поддеревьев, а ()‒ индикаторная функция, которая равна 1, если целевое поддеревоимеет корнем вершину n.

Ядро для T1 и 2 определяется какTK(T1 , T2 ) = ∑n1∈NT1 ∑n2∈NT2 ∆(n1 , n2 ), где NT1 и NT2 ‒ множествавершиндеревьевT1иT2соответственно,а|F|∆(n1 , n2 ) = ∑i=1 χi (n1 )χi (n2 ).Функцияопределяетколичествообщихфрагментов,начинающихся в вершинах 1 и 2 , и зависит от типа фрагмента.В простейшем случае в качестве подструктур рассматриваютсямножества ребер и вершин из исходного дерева, которое такжеобразуют деревья с дополнительным ограничением: для любойвершины должны учитываться или все, или ни одна из ее дочернихвершин.47Дляподсчетаобщегоколичестватакихподструктур,начинающихся в вершинах 1 и 2 , используется следующий видфункции ∆:1.

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

если 1 (или n2 ) ‒ предтерминальная вершина, и метка ее потомка– null, то ∆(n1 , n2 ) = 0.2. если продукции в вершинах n1 и n2 не совпадают, то ∆(n1 , n2 ) = 03. если продукции в вершинах одинаковы, и дочерние вершинытолько терминальные, то ∆(1 , 2 ) = .4. еслипродукциивпредтерминальные,вершинахтосовпадают,вводитсяивершинырекурсивноеневыражение:l(n )∆(n1 , n2 ) = ∏j=11 (1 + ∆ (cn1 (j), cn2 (j))) -1.1.5.2.4 Ядро частичных поддеревьевЕсли ослабить требование касательно продукций, то получатсяподструктуры более общего вида, а функция ∆ упростится [113].

Длядвух вершин n1 и n2 ядро на синтаксических деревьях применяетсядля всех возможных подпоследовательностей потомков этих вершин.Алгоритм подсчета функции  выглядит следующим образом:1. Если метки вершин n1 и n2 разные, то ∆(1 , 2 ) = 0.2. В противном случае  n1 , n2   1   I ,I12 ,l I1 l  I 2 l  I1 j 1     cn1 I1 j , cn2 I 2 j , ∆(n1 , n2 ) = 1 +̿l(I )̿ ), cn (I2j̿ )), где I1̿ =< h1 , h2 , h3 , … > и∑I̿1,I̿2,l(I̿1)=l(I̿2) ∏j=11 ∆(cn1 (I1j22 =< 1 , 2 , 3 , … > ‒ последовательности индексов, отвечающиеупорядоченной последовательности потомков cn1 для n1 и cn1 для n2соответственно, I1 j и I 2 j указывают на j-ого потомка всоответствующей последовательности, а (.

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

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