авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
-- [ Страница 1 ] --

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ М.В. ЛОМОНОСОВА

Факультет

вычислительной математики

и кибернетики

Сборник статей

молодых ученых факультета

ВМК МГУ

Выпуск 10

МОСКВА – 2013

УДК 517.9+519.6+519.7

ББК 22

С23

Редакционный совет сборника:

С.А. ЛОЖКИН, А.В. ИЛЬИН, В.В. ФОМИЧЕВ,

И.Г. ШЕВЦОВА, А.А. ВОРОНЕНКО Составители:

А.И. МЕСЯЦ, И.Г. ШЕВЦОВА Сборник статей молодых ученых факультета ВМК МГУ/ Ред. со С23 вет: Ложкин С.А. и др. – М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова (лицензия ИД N 05899 от 24.09.2001 г.);

МАКС Пресс, 2013. – Выпуск 10. – 300 с.

ISBN 978-5-89407-508-2 ISBN В настоящий сборник вошли статьи, написанные молодыми учеными факуль тета вычислительной математики и кибернетики Московского государственно го университета имени М.В. Ломоносова в 2012–2013 гг.

УДК 517.9+519.6+519. ББК Составление и оформление. Месяц А.И., ISBN 978-5-89407-508- Шевцова И.Г., ISBN Совет молодых ученых факультета ВМК МГУ, Издательский отдел факультета ВМК МГУ, Данный выпуск посвящается 110-летию со дня рождения А. Н. Колмогорова выдающегося математика, одного из крупнейших учёных ХХ века СОДЕРЖАНИЕ О граничном управлении смещением на одном конце при за крепленном втором процесса вынужденных колебаний струны М. Ф. Абдукаримов........................................ О генерации правил для синтаксического анализа текстов на естественном языке П. В. Алейников.......................................... Задача управления портфелем пенсионного фонда при гарантированном исполнении обязательств в случае коррели рованной динамики цен активов Н. А. Андреев, А. В. Дружинина......................... Построение искусственных краевых условий для одномерной задачи распространения лазерного импульса в линейной среде с дисперсией третьего порядка А. Д. Денисов............................................ Разностная схема для расчета 2D генерации полупроводнико вой плазмы, индуцированной лазерным импульсом В. А. Егоренков........................................... Некоторые задачи восстановления бесповторных функций Д.

В. Кафтан............................................ Метод внутренней аппроксимации для поиска областей устой чивости аффинных полиномов А. В. Мальцева.......................................... Библиотечная реализация стековой вычислительной модели на примере языка Joy А. В. Мошкина.......................................... Задача оптимального управления в модели распространения вируса гриппа A(H1N1) С. М. Орлов............................................. Численное решение задачи о свободной конвекции в квад ратной области в двумерной постановке конечно-разностным методом В. О. Пиманов, И. С. Калачинская...................... 6 Содержание О различных типах граничных условий для одномерного уравнения колебаний А. М. Рогожников....................................... Внутренние оценки множеств достижимости билинейных систем В. В. Синяков........................................... Применение принципа доминирования по характерности в задаче совмещения формальных контекстов Д. Е. Стельмашенко.................................... Об одном способе организации библиотеки моделей программ Н. Н. Фастовец......................................... Анализ и применение признаков оценочных слов для форми рования словаря оценочной лексики И. И. Четвёркин........................................ Рефераты................................................. Сборник статей молодых ученых факультета ВМК МГУ, № 10, 2013 УДК 517.984. О граничном управлении смещением на одном конце при закрепленном втором процесса вынужденных колебаний струны © 2013 г. М. Ф. Абдукаримов mahmadsalim_86@mail.ru Кафедра общей математики 1 Введение В данной работе в терминах обобщенного решения неод нородного волнового уравнения utt (x, t) uxx (x, t) = f (x, t), 0 x l, 0 t T, c конечной энергией изучается за дача граничного управления смещением процесса вынужден ных колебаний струны на конце x = 0 при условии, что конец x = l закреплен. Работа состоит из трех разделов. В первом разделе приведены постановка задачи, необходимые определе ния и вспомогательные утверждения. Во втором для слу чая T 2l установлены необходимые и достаточные условия существования единственного граничного управления u(0, t) = = µ(t), переводящего процесс колебаний из начального состо яния {u(x, 0) = (x), ut (x, 0) = (x)} в финальное состояние {u(x, T ) = 1 (x), ut (x, T ) = 1 (x)} и это граничное управление представлено в явном аналитическом виде. Количество указан ных условий и вид искомого граничного управления зависят от того, какому множеству принадлежит промежуток времени T : интервалу (0, l) или полусегменту [l, 2l). И, наконец, тре тий раздел посвящен построению граничного управления, ко гда время T больше удвоенной длины струны l. Точнее, пока зано, что при T 2l (ради определенности и простоты будем считать, что 2l T 3l) искомое граничное управление су ществует, но определяется неоднозначно. Получен его общий 8 М. Ф. Абдукаримов вид, в который входят три совершенно произвольные первооб разные функций (x), 1 (x) и f (x, t) по первой переменной и две произвольные функции, определенные на сегментах длины T 2l, принадлежащие на них классу W2 и принимающие на концах этих сегментов заданные значения.

Отметим, что аналогичная задача для процесса свободных колебаний, т.е. колебаний, описываемых однородным волновым уравнением, была рассмотрена в [1]. Случай вынужденных ко лебаний, когда граничные управления действуют на двух кон цах, исследован в [2]– [4].

Для решения различных задач, связанных с граничными управлениями, В. А. Ильин, Е. И. Моисеев и их ученики опуб ликовали целый ряд работ (см., например, [5]– [12]). Из бо лее ранних работ, относящихся к данной тематике, приведем [13]– [20].

2 Постановка задачи, необходимые опре деления и вспомогательные утвержде ния В прямоугольнике QT = (0 x l) (0 t T ) рассмот рим в обобщенной трактовке следующие задачи.

Смешанная задача I:

Lu utt (x, t) uxx (x, t) = f (x, t) в QT, (1) u(l, t) 0 при (2) u(0, t) = µ(t), 0 t T, ut (x, 0) = (x) при (3) u(x, 0) = (x), 0 x l, 1 в которой µ(t) W2 [0, T ], (x) W2 [0, l], (x) L2 [0, l], f (x, t) L2 (QT ) и выполнены условия согласования (4) µ(0) = (0), (l) = 0.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении Задача граничного управления II: уравнение (1) с усло вием закрепления u(l, t) 0, при t [0, T ], начальными усло виями (3) и финальными условиями ut (x, T ) = 1 (x) при (5) u(x, T ) = 1 (x), 0 x l, в которой (x), 1 (x) W2 [0, l], (x), 1 (x) L2 [0, l], f (x, t) L2 (QT ).

Решение этих задач будем искать в классе W2 (QT ), впервые введенном в работе [5]. Приведем определение этого класса.

Определение 1. Будем говорить, что функция двух пере менных u(x, t) принадлежит классу W2 (QT ), если она непре рывна в замкнутом прямоугольнике QT и имеет в нем обоб щенные частные производные первого порядка, каждая из ко торых принадлежит классу L2 [0 l] при любом фикси x рованном t [0, T ] и принадлежит классу L2 [0 T ] при t любом фиксированном x [0, l].

Из принадлежности обобщенного решения u(x, t) задачи II классу W2 (QT ) вытекает, что это решение имеет след u(0, t) = = µ(t) W2 [0, T ], удовлетворяющий условиям согласования с функциями (x) и 1 (x), т.е. условиям (4) и µ(T ) = 1 (0), 1 (l) = 0.

Теперь дадим определения решений задач I–II.

Определение 2. Решением из класса W2 (QT ) смешанной за дачи I назовем такую функцию u(x, t) из этого класса, кото рая удовлетворяет тождеству T l l u(x, t)Ldxdt + [(x)t (x, 0) (x)(x, 0)]dx 0 0 T l T (6) µ(t)x (0, t)dt f (x, t)(x, t)dxdt = 0 0 Сборник статей молодых ученых факультета ВМК МГУ, № 10, 10 М. Ф. Абдукаримов для произвольной функции (x, t) из класса1 W2 (QT ), подчи ненной условиям (0, t) 0, (l, t) 0 при 0 t T и усло виям (x, T ) 0, t (x, T ) 0 при 0 l, граничным x условиям (2) и первому начальному условию (3) в классиче ском смысле, а второму начальному условию (3) в смысле равенства элементов L2 [0, l].

Определение 3. Решением из класса W2 (QT ) задачи гранич ного управления II назовем решение u(x, t) из этого класса сме шанной задачи I, которое обеспечивает выполненные первого равенства (5) в класcическом смысле, а второго равенства (5) в смысле совпадения элементов L2 [0, l].

Из тождества (6) и схемы рассуждений, изложенной в ра боте [21] вытекает следующее Утверждение 1. Для любого T 0 смешанная задача I может иметь только одно решение из класса W2 (QT ).

Рассмотрим теперь смешанную задачу I, у которой (x) на сегменте [0, l], (x) = 0 почти всюду на [0, l], а гранич ное значение µ(t) является произвольной функцией из клас са W2 [0, T ]. При этом в силу условия согласования (4) долж но выполниться равенство µ(0) = 0. Обозначим символом µ(t) функцию, совпадающую с µ(t) при 0 t T и продолженную нулем при t 0. Очевидно, что µ(t) W2 [, T ] 0.

2l. Тогда единственное ре Утверждение 2. Пусть T шение u(x, t) из класса W2 (QT ) смешанной задачи I, у кото рой (x) 0 на сегменте [0, l], (x) = 0 почти всюду на [0, l], f (x, t) L2 [QT ], а µ(t) - произвольная функция из класса W2 [0, T ], для которой µ(0) = 0 определяется равенством t x+t (7) u(x, t) = u(x, t) + f (, )dd, 0 xt+ Определение этого класса приведено в работе [1].

Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении в котором функция u(x, t) = µ(t x) µ(t x + 2l) явля ется решением смешанной задачи I для однородного волнового уравнения (см. [1]) и подынтегральная функция получена из функции f (x, t) нечетным продолжением относительно гра ниц x = 0 и x = l прямоугольника QT.

Доказательство. С помощью свойств функций µ(t) и f (x, t) тривиально проверяется, что при T 2l функция (7) удовлетворяет для любого t [0, T ] граничным условиям (2) и первому начальному условию u(x, 0) 0 при всех x [0, l], а второму начальному условию ut (x, 0) = 0 - почти всюду на [0, l].

Поэтому достаточно убедиться в том, что она удовлетворяет тождеству (6), в котором (x) 0 x [0, l], а (x) является нулевым элементом L2 [0, l], т.е. соотношению T l Lu,f, [u(x, t)L f (x, t)(x, t)] dxdt 0 T µ(t)x (0, t) dt = 0 (8) для любой функции (x, t) из определения 2. Так как справед ливость тождества (8) для функции u(x, t) установлена в [1].

Поэтому нам достаточно доказать его справедливость только для второго слагаемого (7).

С помощью интегрирования по частям придадим левой ча сти соотношения (8) следующий вид:

T l Lu,f, = ux (x, t)x (x, t) 0 ut (x, t)t (x, t) f (x, t)(x, t) dxdt. (9) Сборник статей молодых ученых факультета ВМК МГУ, № 10, 12 М. Ф. Абдукаримов Итак, нам надо доказать, что правая часть (9) равна ну лю. Обозначим через f (x, t) произвольную первообразную по x функции f (x, t). Найдя из (7) ux (x, t), ut (x, t) и подставляя их в правую часть (9), далее с помощью интегрирования по частям и с учетом свойств функции (x, t) получим:

l T t [f (x + t, ) f (x t +, )] d x (x, t)dtdx 0 0 Tl t [f (x + t, ) + f (x t +, )]d t (x, t)dxdt 0 0 l T f (x, t)(x, t)dxdt = 0 l T t 1 = [f (x + t, ) + f (x t +, )]d 0 0 T l t f (x, )d xt (x, t)dx xt (x, t)dxdt + dt+ 0 0 l T t 1 + [f (x + t, ) + f (x t +, )]d tx (x, t)dxdt 0 0 l T l T t f (x, )d f (x, t)(x, t)dxdt = 0 0 0 0 lT t (x, t) dtdx f (x, t)(x, t)dxdt = 0 Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении l T lT = f (x, t)(x, t)dxdt = 0.

0 0 0 Утверждение 2 доказано. Повторяя рассуждения, приве денные в [1], можно убедиться в справедливости следующего факта:

Утверждение 3. Пусть T 2l. Тогда может существо вать только одно решение из класса W2 (QT ) задачи гранич ного управления II.

3 Построение граничного управления в случае 0 T 2l В этом разделе рассмотрим задачу граничного управления II в случае, когда момент времени меняется в полусегменте 0 T 2l. Справедлива следующая Теорема 1. Для того чтобы при 0 T 2l для наперед заданных пяти функций (x), 1 (x) W2 [0, l], (x), 1 (x) L2 [0, l] и f (x, t) L2 (QT ) существовало единственное реше ние задачи граничного управления II из класса W2 (QT ), необ ходимо и достаточно, чтобы выполнялись 1) условия закрепления (l) = 0, 1 (l) = 0;

2) функции (x), (x), 1 (x), 1 (x) и f (x, t), дополнитель но удовлетворяли:

a) для случая 0 T l трем тождествам:

T 1 (t) + 1 (t) (t + T ) (t + T ) f (t + T, )d (10) при t t1, T 1 (t) + 1 (t) (t2 t) + (t2 t) f (t + T, )d Сборник статей молодых ученых факультета ВМК МГУ, № 10, 14 М. Ф. Абдукаримов (11) при t1 t l, T 1 (t) 1 (t) (t T ) + (t T ) f (t T +, )d (12) при T t l, в которых t1 = lT, t2 = 2lT и через (x), 1 (x) и f (x, t) обо значены соответственно первообразные функций (x), 1 (x) и f (x, t) по x, удовлетворяющие соотношениям T (13) 1 (0) + 1 (0) (T ) (T ) f (T, )d = 0, T f (l T +, )d = 0;

(14) 1 (l) 1 (l) (l T ) + (l T ) T 2l тождеству b) для случая l T 1 (t) + 1 (t) (t2 t) + (t2 t) f (t + T, )d (15) при t t2, в котором символами (x), 1 (x) и f (x, t) обозначены соот ветственно первообразные функций (x), 1 (x) и f (x, t) по x, удовлетворяющие соотношению T (16) 1 (0) + 1 (0) (t2 ) + (t2 ) f (T, )d = 0.

Для случая T = 2l необходимым и достаточным услови ям существования единственного решения из класса W2 (QT ) Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении задачи граничного управления II является только требова ние 1).

При выполнении этих требований решение указаной зада чи дается формулой t x+t f (, ) d d, (17) u(x, t) = F (t + x) F (t x + 2l) + 0 xt+ где функция F (t) определяется выражениями (18) [(t) + (t)] при t l, (19) [(2l t) (2l t)] 2l, при l t T 1 f (t, )d 1 (t T ) + 1 (t T ) (20) T + l, при T t T 1 [1 (2l + T t) 1 (2l + T t) f (2l t +, )d ] (21) при T + l t T + 2l, в которых2 символы (x), 1 (x) и f (x, t) обозначают соот ветственно первообразные функций (x), 1 (x) и f (x, t) по x, удовлетворяющие в случае 0 T l соотношениям (13) и (14), в случае l T 2l соотношению (16), а в случае T = 2l соотношению 2l (22) 1 (0) + 1 (0) (0) + (0) f (, )d = 0.

При T 2l однозначность определения функции F (t) гарантируется соотношениями (10)–(12) и (15).

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 16 М. Ф. Абдукаримов При этом искомое граничное управление u(0, t) = µ(t) W2 [0, T ], переводящее процесс колебаний из начального состо яния (3) в финальное состояние (5), имеет следующий вид:

a) в случае 0 T l T 1 µ(t) = (t) + (t) 1 (T t) + 1 (T t) + f (t, )d ;

b) в случае l T 2l 2 [(t) + (t) 1 (t2 + t) T (t + t) + f (t + 2l, )d ] при 0 t T l, [(t) + (t) (T t)+ µ(t) = T +1 (T t) + f (t, )d ] при T l t l, [(2l t) (2l t) (T t)+ T + (T t) + f (t, )d ] 1 T;

при l t c) в случае T = 2l 2 [(t) + (t) 1 (t) 1 (t)+ 2l + f (t + 2l, )d ] при 0 t l, µ(t) = 1 2 [(2l t) (2l t) 1 (2l t)+ 2l +1 (2l t) + f (t, )d ] 2l.

при l t Доказательство необходимости. Необходимость тре бования 1) вытекает из граничного условия u(l, t) 0 t [0, T ] и определения класса W2 (QT ). Перейдем к обоснова нию необходимости требования 2). Сначала рассмотрим част ный случай, когда в задаче II (x) 0 на сегменте [0, l], а (x) Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении является нулевым элементом L2 [0, l]. В этом случае решение u(x, t) из класса W2 (QT ) задачи II (если оно существует) яв ляется одновременно решением из того же класса смешанной задачи I, у которой (x) 0 на [0, l], а (x) = 0 почти всюду на [0, l]. Единственное решение последней задачи в силу утвер ждения 2 представляется в виде (7).

Сначала будем рассматривать подслучай 0 T l. Для него второй член в правой части равенства (7) является тож дественным нулем для всех x [0, l], t [0, T ]. Из получаемого соотношения имеем:

T [f (x+ T, )+ f (x T +, )] d, (23) 1 (x) = µ (T x)+ T (x) [f (x+T, )f (xT +, )] d, (24) = µ (T x)+ которые выполнены для почти всех x [0, l].

Из (23) и (24) вытекает справедливое в смысле равенства элементов L2 [0, l] соотношение T (x) (25) 1 (x) + = f (x + T, )d.

Интегрируя (25) по x в пределах от нуля до t, получим справедливое для всех t [0, l] соотношение T T 1 (t)+1 (t) f (t+T, )d = 1 (0)+1 (0) f (T, )d, 0 (26) 1 (x) и f (x, t) обозначены пока произ в котором символами вольные первообразные соответственно функций 1 (x) и f (x, t) Сборник статей молодых ученых факультета ВМК МГУ, № 10, 18 М. Ф. Абдукаримов по x. Если мы потребуем, чтобы эти первообразные удовлетво ряли условию T (27) 1 (0) + 1 (0) f (T, )d = 0, то получим справедливое для всех t [0, l] тождество T (28) 1 (t) + 1 (t) f (t + T, )d 0.

Теперь предположим, что x [T, l]. Вычитая из (23) равен ство (24), получим соотношение T (x) (29) 1 (x) = f (x T +, )d, понимаемое как равенство элементов L2 [T, l].

Интегрируя (29) по x в пределах от t до l, получим спра ведливое для всех t [T, l] соотношение T 1 (t) 1 (t) f (t T +, )d = T f (l T +, )d, (30) = 1 (l) 1 (l) в котором 1 (x) и f (x, t) - пока произвольные первообразные соответственно функций 1 (x) и f (x, t) по x. Если мы теперь потребуем, чтобы эти первообразные удовлетворяли условию T (31) 1 (l) 1 (l) f (l T +, )d = 0, Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении то получим справедливое для всех t [T, l] тождество T (32) 1 (t) 1 (t) f (t T +, )d 0.

Рассмотрение подслучая 0 T l завершено. Переходим к рассмотрению подслучая l T 2l. На этот раз из (7) мы получим соотношение 1 (x) = µ (T x) µ (T + x 2l)+ T (33) + [f (x + T, ) + f (x T +, )] d, справедливое для почти всех x [0, l].

Проинтегрировав (33) по x в пределах от нуля до t, мы по лучим, что для любого t [0, 2l T ] справедливо соотношение T 1 (t) 1 (0) = µ(T ) µ(T t) + f (t + T, )d + T T 1 (34) + f (t T +, )d f (T, )d, 0 в котором символы 1 (x) и f (x, t) обозначают пока произ вольные первообразные соответственно функций 1 (x) и f (x, t) по x.

Из равенства (7) при x = t, t = T и x = 0, t = T, вытекают соответственно следующие равенства:

T T 1 µ(T t) = 1 (t) f (t + T, )d + f (t T +, )d, 2 0 Сборник статей молодых ученых факультета ВМК МГУ, № 10, 20 М. Ф. Абдукаримов µ(T ) = 1 (0).

Подставляя эти значения соответственно в равенство (34), получим:

T 1 (t) + 1 (t) f (t + T, )d = T (35) = 1 (0) + 1 (0) f (T, )d.

Из (35) вытекает, что если через 1 (t), f (x, t) обозначить те первообразные функций 1 (x) и f (x, t) по первой переменной, которые удовлетворяют соотношению вида (27), то для всех t [0, 2l T ] будет справедливо тождество вида (28).

Тем самым, для частного случая, когда (x) 0 на [0, l], а (x) является нулевым элементом L2 [0, l], необходимость тре бования 2) доказана.

Рассмотрим теперь общий случай, когда (x) является про извольной функцией из класса W2 [0, l], удовлетворяющей усло вию (l) = 0, а (x) - произвольный элемент L2 [0, l].

Продолжим функции (x), (x) и f (x, t) по первой пере менной сначала на сегмент [l, 2l] нечетно относительно точки x = l, а затем на сегмент [l, 0] в подслучае 0 T l и на сегменты [2l, 0] и [2l, 3l] в подслучае l T 2l, так, что бы (x) W2 [l, 2l], (x) L2 [l, 2l], f (x, t) L2 [(l x 1 [2l, 3l], 2l) (0 t T )] в подслучае 0 T l и (x) W x 3l) (0 t T )] в (x) L2 [2l, 3l], f (x, t) L2 [(2l подслучае l T 2l и в этом последнем подслучае функции (x), (x) и f (x, t) по первой переменной оставались нечетны ми относительно точки x = l в пределах сегмента [l, 3l].

С так продолженными функциями (x), (x) и f (x, t) рас Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении смотрим функцию t [f (x + t, ) f (x t +, )]d, (36) v(x, t) = v(x, t) + в которой v(x, t) = 1 [(x + t) + (x t) + (x + t) (x t)], а (x) и f (x, t) обозначают пока произвольные первообразные соответственно функций (x) и f (x, t) по первой переменной.

Заметим, что эти первообразные будут четными относительно точки x = l функциями в пределах сегмента [0, 2l] в подслучае 0 T l и в пределах сегмента [l, 3l] в подслучае l T 2l.

Убедимся в том, что функция (36) в обоих случаях являет ся обобщенным решением из класса W2 (QT ) смешанной зада чи типа I, у которой v(x, 0) = (x) x [0, l], vt (x, 0) = (x) в смысле совпадения элементов L2 [0, l], v(l, t) 0 t [0, T ], а граничное значение v(0, t) берется из выражения (36). Нужно только доказать, что она удовлетворяет тождеству (6), в кото ром u(x, t) и µ(t) заменены соответственно на (x, t) и (0, t) для любой фигурирующей в определении 2 функции (x, t).

С помощью интегрирования по частям перепишем (6) в ви де l T [vx (x, t)x (x, t) vt (x, t)t (x, t)]dxdt 0 l T l (37) f (x, t)(x, t)]dxdt = t (x, 0)(x, 0)dx.

0 0 В [1] показано, что функция v(x, t) удовлетворяет соотно шению (37) в случае, когда в нем отсутствует T l f (x, t)(x, t) dxdt.

0 Сборник статей молодых ученых факультета ВМК МГУ, № 10, 22 М. Ф. Абдукаримов Поэтому нам достаточно доказать, что для интегрального сла гаемого, стоящего в правой части (36), справедливо (37), но это уже сделано при доказательстве утверждения 2.

Таким образом, функция (36) является обобщенным реше нием из класса W2 (QT ) смешанной задачи типа I. Отсюда сле дует, что разность [u(x, t)v(x, t)] удовлетворяет всем требова ниям рассмотренного выше частного случая. Поэтому для нее будут справедливы тождества вида (28) и (32) с условием (27) и (31) для определения первообразных в подслучае 0 T l и тождество вида (28) с условием для определения первооб разных (27) в подслучае l T 2l. Эти тождества имеют следующий вид:

a) в случае 0 T l:

[1 (t) vt (t, T )] + [1 (t) v(t, T )] 0 при 0 (38) t l, [1 (t) vt (t, T )] [1 (t) v(t, T )] 0 при T (39) t l со справедливыми соотношениями [1 (0) vt (0, T )] + [1 (0) v(0, T )] = 0 при 0 (40) t l, [1 (l) vt (l, T )] [1 (l) v(l, T )] = 0 при T (41) t l;

b) в случае l T 2l:

[1 (t) vt (t, T )] + [1 (t) v(t, T )] 0 при 0 2l T (42) t со справедливым соотношением (43) [1 (0) vt (0, T )] + [1 (0) v(0, T )] = 0, в которых символ vt (x, t) обозначает первообразную функции vt (x, t) по x и определяется равенством 1 vt (x, t) = [(x + t) (x t) + (x + t) + (x t)+ Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении t (44) + [f (x + t, ) + f (x t +, )]d ].

Равенства (36) и (44) позволяют переписать (38)–(43) в сле дующем виде:

1 (t) + 1 (t) (t + T ) (t + T ) T f (t + T, )d 0 при 0 (45) t l, 1 (t) 1 (t) + (t T ) (t T ) T f (t T +, )d 0 при T t l со справедливыми соотношениями T f (T, )d = 0 при 1 (0) + 1 (0) (T ) (T ) t l, 1 (l) 1 (l) + (l T ) (l T ) T при T f (l T +, )d = 0 t l;

1 (t) + 1 (t) (t + T ) (t + T ) T при 0 (46) f (t + T, )d 0 2l T t со справедливым соотношением T (47) 1 (0) + 1 (0) (T ) (T ) f (T, )d = 0.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 24 М. Ф. Абдукаримов Таким образом, для установления справедливости соотно шений (10)–(16) нам остается заметить, что так как относитель но точки x = l функция (x) является нечетной, а функция (x) четной, то всякий раз, когда аргумент t + T или T боль ше или равен l, справедливы равенства (t+T ) = (2lT t) и (t + T ) = (2l t T ). Отсюда следует, что тождество (45) должно быть переписано в виде двух тождеств (10) и (11), а тождество (46) и соотношение (47) должны быть переписаны в виде (15) и (16). Необходимость соотношений (10)–(12) и (15) полностью доказана.

Доказательство достаточности. Для того чтобы до казать, что функция u(x, t), определяемая равенством (17), принадлежит классу W2 (QT ), достаточно убедиться в том, что функция F (t), определяемая соотношениями (18)–(21), при надлежит классу W2 [0, T +2l]. Соотношения (18)–(21) позволя ют утверждать, что F (t) принадлежит классу W2 на каждом из сегментов [0, l], [l, 2l], [T, T + l] и [T + l, T + 2l].

Поэтому в случае 0 T l, т.е. когда 0 T l T + l 2l T + 2l, для доказательства принадлежности F (t) клас су W2 [0, T + 2l] достаточно убедиться в том, что: 1) значения F (t), определяемые равенствами (18) и (20), совпадают между собой при T l;

2) значения F (t), определяемые равен t ствами (19) и (20), совпадают между собой при l t T + l;

3) значения F (t), определяемые равенствами (19) и (21), сов падают между собой при T + l t 2l. Но это сразу вытекает из тождеств (10)–(12).

В случае l 2l, т.е. когда 0 l 2l T +l T T T + 2l, для доказательства принадлежности F (t) классу 3l W2 [0, T +2l] достаточно убедиться в том, что: 1) значения F (l), определяемые из равенств (18) и (19), совпадают между собой;

2) значения F (T + l), определяемые из равенств (20) и (21), совпадают между собой ;

3) в случае l T 2l значения F (t), определяемые из равенств (19) и (20), совпадают между собой при T 2l;

4) в случае T = 2l значение F (2l), определя t Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении емые из равенств (19) и (20), совпадают между собой. Но 1) и 2) проверяются непосредственно из соотношений (18)–(21), справедливость 3) сразу вытекает из тождества (15), а спра ведливость 4) - из соотношения (22).

Итак, F (t) принадлежит классу W2 [0, T + 2l] и поэтому функция u(x, t), определяемая равенством (17), принадлежит классу W2 (QT ).

С помощью соотношений (18)–(21) легко проверяется, что для всех x [0, l] справедливы равенства u(x, 0) = (x), u(x, T ) = 1 (x) и в смысле равенства элементов L2 [0, l] ut (x, 0) = (x), ut (x, T ) = 1 (x).

Остается доказать, что для функции u(x, t), определяемой равенством (17) и для граничного управления u(0, t) = µ(t), взятого как указано в условии теоремы, справедливо тожде ство (6) для произвольной функции (x, t) из определения 2.

В силу (37) достаточно доказать справедливость соотношения l T [ux (x, t)x (x, t) ut (x, t)t (x, t)]dxdt 0 l T l (48) f (x, t)(x, t)dxdt = (x)(x, 0)dx.

0 0 Отметим, что справедливость соотношения (48) для функ ции (17) без интегрального слагаемого, стоящего в ее правой части, установлена в [1]. Поэтому нам достаточно доказать, что для указанного интегрального слагаемого справедливо со отношение (48), в котором правая часть отсутствует, а это уже показано в процессе доказательства утверждения 2. Теорема полностью доказана.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 26 М. Ф. Абдукаримов 4 Построение граничного управления в случае 2l T 3l Наконец, в этом последнем разделе рассмотрим задачу гра ничного управления II в случае T 2l. Ради определенности будем считать, что 2l T 3l. Имеет место следующая Теорема 2. Если 2l T 3l, то для произвольных 1 [0, l], (x), (x) L [0, l] пяти функций (x), 1 (x) W2 1 и f (x, t) L2 (QT ), удовлетворяющих условиям закрепления (l) = 1 (l) = 0, существует решение u(x, t) задачи гранично го управления II из класса W2 (QT ). Это решение и соответ ствующее граничное управление определяются неоднозначно и имеют следующий вид:

u(x, t) = u(x, t) + u(x, t), µ(t) = µ(t) + µ(t), где u(x, t) = µ(t + x) µ(t x + 2l)+ T x+t (49) +µ(t + x + 2l) f (, ) d d, t xt+ (50) u(x, t) = µ(t x) µ(t + x 2l) + µ(t x 2l), 1 T 2 (t) + (t) + f (t, )d (t + 2l) при 0 t T 2l, T (t) + (t) + f (t, )d 2 при T 2l t l, µ(t) = 1 [(2l t) (2l t)+ T + f (2l t +, )d ] 2l, при l t (t) при 2l t T, 0 при t T, (51) Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении 0 при t 0, (t) при 0 t T 2l, [1 (t T + 2l)+ µ(t) = +1 (t T + 2l)] при T 2l t T l, [1 (T t) 1 (T t)] 2 при T l t 2l, [1 (T t) 1 (T t)] (t 2l)] при 2l t T, (52) 1 и f (x, t) обозначают совершенно произволь символы (x), ные первообразные соответственно функций (x), 1 (x) и f (x, t) по первой переменной, (t) - произвольная функция из класса W2 [2l, T ], удовлетворяющая условиям (2l) = 1 [(0) T (0) + 0 f (, )d ], (T ) = 0, (t) - произвольная функция из класса W2 [0, T 2l], удовлетворяющая условиям (0) = 0, (T 2l) = 2 [1 (0) + 1 (0)].

Доказательство. Отдельно докажем, что функция (49) с µ(t), определяемым соотношением (51), является решением из класса W2 (QT ) задачи граничного управления II с про извольной функцией (x) W2 [0, l], удовлетворяющей усло вию (l) = 0, с произвольными функциями (x) L2 [0, l], f (x, t) L2 (QT ), и с функциями 1 (x) 0 на [0, l] и 1 (x), яв ляющейся нулевым элементом L2 [0, l], т.е. является решением задачи о полном успокоении колебательного процесса, а функ ция (50) с µ(t), определяемым соотношением (52), является ре шением из класса W2 (QT ) задачи граничного управления II с функциями (x) 0 на [0, l], f (x, t) = 0 почти всюду на [0, l] [0, T ] и (x), являющейся нулевым элементом L2 [0, l], и с произвольными функциями 1 (x) W2 [0, l], удовлетворяю щей условию 1 (l) = 0 и 1 (x) L2 [0, l], т.е. является решени ем задачи о приведении первоначально покоящейся системы в произвольное наперед заданное состояние.

Начнем с рассмотрения функции (49). Из соотношения (51) следует, что функция µ(t) принадлежит классу W2 на каждом Сборник статей молодых ученых факультета ВМК МГУ, № 10, 28 М. Ф. Абдукаримов из сегментов [0, T 2l], [T 2l, l] (при T = 3l этот сегмент нужно выбросить), [l, 2l] и [2l, T ] и обращается в нуль при всех t T.

Кроме того, легко проверяется, что µ(T 2l + 0) = µ(T 2l 0), µ(l + 0) = µ(l 0), µ(2l + 0) = µ(2l 0), µ(T 0) = 0.

Отсюда получим, что функция µ(t) принадлежит классу 1 [0, T + 3l] и поэтому функция (49) принадлежит классу W W2 (QT ).

Далее, из (51) вытекает, что x [0, l] T 1 (x) + (x) + f (x, )d (x + 2l), µ(x) = T 1 µ(2l x) = (x) (x) + f (x +, )d, µ(x + 2l) = (x + 2l) и потому в силу (49) x [0, l] T x u(x, 0) = µ(x)µ(2lx)+µ(x+2l) f (, )dd = (x).

0 x+ Аналогично из справедливых в смысле равенства элементов L2 [0, l] соотношений T f (x, )d (x + 2l), µ (x) = (x) + (x) + T µ (2l x) = [(x) + (x) f (x +, )d ], µ (x + 2l) = (x + 2l), Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении вытекает справедливое в том же смысле соотношение ut (x, 0) = µ (x) µ (2l x) + µ (x + 2l) T [f (x +, ) + f (x, )]d = (x).

Поэтому нам остается доказать, что для произвольной функции (x, t) из определения 2 справедливо тождество (6), в котором u(x, t) = u(x, t) и µ(t) = µ(t). В силу (48) достаточно доказать соотношение l T [ux (x, t)x (x, t) ut (x, t)t (x, t)]dxdt 0 l T l (53) f (x, t)(x, t)dxdt = (x)(x, 0)dx.

0 0 Рассмотрим функцию U (x, t) = µ(t + x) + µ(t x + 2l) + µ(t + x + 2l) T 1 [f (x + t, ) + f (x t +, )]d, t в которой f (x, t) - произвольная по x первообразная функции f (x, t).

Нетрудно заметить, что для почти всех x [0, l] и t [0, T ] справедливы Ux (x, t) = ut (x, t), Ut (x, t) f (x, t) = ux (x, t).

Учитывая эти соотношения, с помощью интегрирования по ча стям получим:

T l l T Ut (x, t)x (x, t)dt dx f (x, t)x (x, t)dx dt 0 0 0 Сборник статей молодых ученых факультета ВМК МГУ, № 10, 30 М. Ф. Абдукаримов T l lT Ux (x, t)t (x, t)dx dt f (x, t)(x, t)dxdt = 0 0 0 l l = U (x, T )x (x, T )dx U (x, 0)x (x, 0)dx 0 l T T U (x, t)xt (x, t)dxdt U (l, t)t (l, t)dt+ 0 0 T l T + U (0, t)t (0, t)dt + U (x, t)tx (x, t)dxdt 0 0 T T l T f (l, t)(l, t)dt + f (0, t)(0, t)dt + f (x, t)(x, t)dxdt 0 0 0 l T l f (x, t)(x, t)dxdt = U (x, 0)x (x, 0)dx = 0 0 l l = ut (x, 0)(x, 0)dx = (x)(x, 0)dx.

0 Тем самым, соотношение (53) установлено и доказательство теоремы 2 для функции (49) завершено, а ее доказательство для u(x, t) приведено в [1]. Теорема 2 доказана.

Автор выражает глубокую благодарность своему научному руководителю доценту Крицкову Л. В. за постоянное внимание и полезные обсуждения при выполнении этой работы.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении Список литературы [1] Ильин В. А. Граничное управление процессом колебаний на одном конце при закрепленном втором конце в тер минах обобщенного решения волнового уравнения с конеч ной энергией // Дифференц. уравнения, 2000, т. 36, № 12, с. 1670 – 1686.

[2] Абдукаримов М. Ф. Граничное управление процессом коле баний, описываемым неоднородным волновым уравнением, за минимальный промежуток времени // Сборник статей молодых учёных факультета ВМК МГУ, 2011, №8, с. 5–18.

[3] Abdukarimov M. F. On a boundary control problem for forced string oscillations // Azerbaijan journal of mathematics, 2012, vol.2, №2, p. 105–116.

[4] Абдукаримов М. Ф. О граничном управлении на двух кон цах вынужденными колебаниями струны // Докл. АН РТ, 2012, т.55, №4, с. 291–299.

[5] Ильин В. А. Граничное управление процессом колебаний на двух концах в терминах обобщенного решения волнового уравнения с конечной энергией // Дифференц. уравнения, 2000, т. 36, №11, с. 1513 – 1528.

[6] Ильин В. А., Моисеев Е. И. Оптимальное граничное управление процессом колебаний струны на одном конце при свободном другом конце // Нелинейная динамика и управление, 2004, вып. 4, М.: Физматлит, с. 25 – 38.

[7] Ильин В. А., Моисеев Е. И. Минимизация интеграла от модуля производной граничного управления, возведенного 1. // Вестник МГУ, сер.15, в произвольную степень p вычисл.матем. и киберн., 2006, №3, с.6–18.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 32 М. Ф. Абдукаримов [8] Ильин В. А., Моисеев Е. И. Оптимальное граничное управление смещением на одном конце струны при сво бодном втором ее конце за любой достаточно большой промежуток времени // Дифференц. уравнения, 2007, т.

43, №10, с. 1369 – 1381.

[9] Моисеев Е. И., Холомеева А. А. Оптимальное граничное управление смещением колебаниями струны с нелокаль ным условием нечетности первого рода // Дифференц.

уравнения, 2010, т. 46, №11, с. 1623 – 1630.

[10] Моисеев Е. И., Холомеева А. А. Оптимальное гранич ное управление смещением колебаниями струны с нело кальным условием четности второго рода // Дифференц.

уравнения, 2011, т. 47, №1, с. 127 – 134.

[11] Никитин А. А. Граничное управление упругой силой на од ном конце струны // Докл. РАН, 2006, т. 406, №4, с. 458– 461.

[12] Никитин А. А., Кулешов А. А. Оптимизация гранично го управления, производимого третьим краевым условием // Дифференц. уравнения, 2008, т. 44, №5, с 681–690.

[13] Lions J. L. Exact Controllability, Stabilization and Perturba tions for Distributed Systems // SIAM Review, 1988, vol. 30, No. 1, p. 1–68.

[14] Zuazua E. Exact Controllability for the Semilinear Wave Equation // J. Math. pures et appl., 69, 1990, p. 1–31.

[15] Бутковский А. Г. Теория оптимального управления систе мами с распределенными параметрами. М.: Наука, 1965.

[16] Егоров А.И. Управление упругими колебаниями // ДАН УССР, серия физ-мат. и техн. наук, 1986, №5, с. 60–63.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, О граничном управлении [17] Васильев Ф. П. О двойственности в линейных задчах управления и наблюдения // Дифференц. уравнения, 1995, т. 31, №11, с. 1893 – 1900.

[18] Васильев Ф. П., Куржанский М. А., Потапов М. М., Раз гулин А. В. Приближенное решение двойственных задач управления и наблюдения. М.: Макс пресс, 2010.

[19] Васильев Ф. П., Куржанский М. А., Потапов М. М. Ме тод прямых в задачах граничного управления и наблюде ния для уравнений колебаний струны // Вестник МГУ, сер. 15, вычисл. матем. и киб., 1993, № 3, с. 8–15.

[20] Васильев Ф. П., Куржанский М. А., Разгулин А. В. О ме тоде Фурье для решения одной задачи управления колеба нием струны // Вестник МГУ, сер. 15, вычисл. матем. и киб., 1993, № 2, c. 3–8.

[21] Ильин В. А. О разрешимости смешанных задач для гипер болического и параболического уравнений // Успехи матем.

наук, 1960, т.15, вып.2(92), с.97–154.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 34 Сборник статей молодых ученых факультета ВМК МГУ, № 10, УДК 004.421. О генерации правил для синтаксического анализа текстов на естественном языке © 2013 г. П. В. Алейников iamrdzim@gmail.com Кафедра алгоритмических языков ВМК МГУ 1 Введение На настоящий момент не создана достаточно полная и фор мальная модель для синтаксического анализа текстов на есте ственном языке, которая позволила бы автоматически опре делять, какие слова в предложении и каким именно образом связаны между собой. В различных учебниках и словарях да ны некоторые правила синтаксического анализа, однако они записаны на естественном языке и предназначены для исполь зования людьми, а не компьютером, так что они не формали зованы, плохо поддаются автоматизации и часто имеют неод нозначные, интуитивно понятные трактовки. Для того, чтобы перевести их в компьютеризованный формат, потребуется дол говременный труд команды экспертов-лингвистов. Однако, по чему бы не попробовать поручить составление таких правил программе? Ведь в таком случае, если только удастся разрабо тать достаточно эффективный алгоритм, результат получится быстрее, и он будет более точным и формальным. Работа над решением задач подобного рода ведётся уже полвека, и в по следнее время интерес к ним не ослабевает. Например, в рабо те [1] описан алгоритм автоматизированной генерации правил для действующего по методу рекурсивного спуска синтаксиче ского анализатора. Однако, этот алгоритм требует постоянного контроля со стороны эксперта-лингвиста, и, кроме того, пра вила генерируются на основании лишь одного предложения, Генерация правил для синтаксического анализа и то, насколько оно показательно, не учитывается. Сейчас, с появлением мощных вычислительных средств, а также боль ших корпусов текстов на компьютерных носителях возникла возможность использовать для создания этой системы правил статистические методы. Их применение для исследования тек стов позволяет подойти к проблеме с другой стороны не про бовать формализовать и автоматизировать известные прави ла или привлекать к работе экспертов, а генерировать систе му правил автоматически, исследуя структуру большого ко личества предложений. В настоящей работе предлагается рас смотреть синтаксический анализатор, использующий модель грамматики зависимостей [2] (то есть, структура предложения представляется в виде иерархии компонентов, между которы ми установлено отношение зависимости). Предлагаемый алго ритм может работать полностью автоматически, и он основан на статистическом анализе, то есть, он создаёт правила на ос нове большого корпуса текстов.

Для того, чтобы создать алгоритм составления системы правил для синтаксического анализа в рамках модели грам матики зависимостей, можно воспользоваться технологией ма шинного обучения с учителем [3] (способ настройки параметров некоторой системы, в ходе которого испытуемая система обу чается с помощью примеров). Для этого нужен текст, содер жащий синтаксическую разметку то есть, кроме собственно текста, в файле должны содержаться сведения о синтаксиче ской структуре, например, для каждого слова может быть ука зано, как оно связано с другими словами предложения. Един ственным достаточно большим корпусом таких текстов явля ется СинТагРус [4], именно поэтому его файлы данных исполь зуются для обучения предлагаемого алгоритма.

Таким образом, на вход алгоритму подаётся корпус текстов, содержащий лексическую и синтаксическую разметку (каж дому слову приписаны его морфологические признаки и син таксическая функция в предложении). Алгоритм должен со Сборник статей молодых ученых факультета ВМК МГУ, № 10, 36 П. В. Алейников ставить по корпусу формальную грамматику используемого в корпусе естественного языка, которая состоит из определений типов синтаксических связей между словами в предложении.

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

Поясним термины. Синтаксическая связь [5] это связь слов, служащая для выражения взаимозависимости элементов словосочетания и предложения. Выделяют разные типы син таксических связей, например, определительная связь, преди кативная, сравнительная и другие. Тип связи, существующей между словами, определяет большинство их морфологических признаков. Морфологические признаки это характеристики грамматической природы слов. Одни морфологические при знаки являются общими для нескольких частей речи, напри мер падеж, другие свойственны только одному классу слов, на пример время у глаголов. Один и тот же признак может быть неизменяемым, постоянным для какого-либо класса слов и из меняемым у других, как, например, род у существительных и прилагательных. У каждой части речи свой набор морфологи ческих признаков. В предложении Мама мыла Милу можно выделить 2 связи мама мыла и мыла Милу. Это связи разного типа, поэтому слова мама и Милу стоят в разных падежах.

Корпус СинТагРус это множество текстов художествен ной, публицистической и исторической литературы, размечен ных лексически и синтаксически то есть, с указанием всех синтаксических связей. Все слова приведены в корпусе вместе с Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа их морфологическими признаками и начальной формой. Опи саны связи между словами: в каждом предложении выделено главное слово, от которого начинаются все цепочки связей, и для всех остальных слов указывается связь, в которую это сло во входит как подчинённое.

В предлагаемом алгоритме используется система типов син таксических связей из корпуса СинТагРус. Эта система ти пов несколько отличается от общепринятой рассматривают ся только связи между двумя словами, а не произвольным их количеством. Помимо этого, среди связанных слов выделяет ся главное, хозяин связи, которое называется её субъектом.

Другое связанное слово подчинено ему, оно называется объек том связи. Несмотря на введение этих ограничений, все слова в предложении можно связать такими связями. Для приме ра покажем, какие связи выделяются в корпусе СинТагРус во фрагменте предложения книги по истории, агрономии, меди цине.... В этом фрагменте пять слов, поэтому он должен со держать четыре связи, чтобы можно было связать все слова друг с другом как известно, число дуг в дереве на едини цу меньше, чем число вершин в этом дереве. Например, в этом предложении могут быть связи книги по, по истории, по агрономии и по медицине.

Кроме того, лингвисты выделяют только сочинительный и подчинительный типы синтаксических связей, а также шесть способов синтаксических связей [6]. Создатели же корпуса СинТагРус подошли к задаче выделения типов серьёзнее и вы делили больше, а именно 70 типов синтаксических связей. Эти типы связей, выделяемые в корпусе СинТагРус, чётче форма лизованы, а их отличия друг от друга точнее определены по сравнению с типами связей, используемыми лингвистами. Бла годаря этому типы связей из корпуса СинТагРус легче преоб разовать в правила формальной грамматики.

Итак, чтобы решить проблему определения типа синтак сических связей, разработан алгоритм создания системы фор Сборник статей молодых ученых факультета ВМК МГУ, № 10, 38 П. В. Алейников мальных правил. Эта система содержит 70 элементов, опре деляющих разные синтаксические связи. В правилах указы вается, какими характеристиками обладают связываемые сло ва. В модельном случае правило для каждой связи представ ляет собой характеристическую функцию с двумя аргумента ми словами одного предложения. Функция принимает дей ствительные значения в диапазоне от 0 до 1 и характери зует вероятность существования связи данного типа между своими аргументами-словами. Чтобы использовать построен ную систему для синтаксической разметки текста, необходимо проверить, удовлетворяют ли слова данного текста построен ным правилам. Если некоторое правило выполняется для пары слов, можно считать, что между этими словами есть связь со ответствующего правилу типа.

2 Структура генерируемых правил Описываемый алгоритм генерации системы правил осно ван на методе машинного обучения с учителем [3], называ емом decision rule, или решающее правило [7]. Задача ма шинного обучения состоит в определении того, по каким при знакам можно судить о том, что некий объект принадлежит некоторому классу. Алгоритм анализирует признаки всех объ ектов, относящихся к данному классу, и выявляет, какие из признаков являются определяющими для вхождения объекта в класс. При обучении с учителем для этого анализа использу ется обучающая выборка, содержащая признаки всех объектов (или предоставляющая возможность их вычислить), а также указание для каждого объекта, к какому классу он принадле жит. Алгоритм по размеченной таким образом обучающей вы борке строит систему правил. Когда она построена, анализатор способен распознать принадлежность произвольного объекта к одному из классов по набору признаков этого объекта.

Разные методы машинного обучения отличаются способом Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа описания условий отнесения объекта к некоторому классу. На пример, в методе опорных векторов [7] требуется, чтобы объект располагался по определённую сторону от заданной гиперплос кости в пространстве признаков. А в методе решающих дере вьев [7] класс объекта определяется путём последовательных проверок на значения признаков. Метод решающих правил от личается тем, что для отнесения объекта к некоторому клас су требуется, чтобы он удовлетворял составленной программой логической формуле. Этот метод был выбран для реализации в алгоритме потому, что логические формулы являются есте ственной формой записи для описания типов синтаксических связей в лингвистике.

В предлагаемом алгоритме в качестве правил используются булевы формулы следующего вида:

(1) formula ::= conjunction conjunction... conjunction;

conjunction ::= disjunction disjunction... disjunction;

(2) (3) disjunction ::= (plus... plus) \ (minus... minus).

Обозначим как НЭД (Не-Элементарная Дизъюнкция) такую дизъюнкцию (disjunction), состоящую из двух частей, разде лённых знаком логического вычитания \. В первой части пе речислены так называемые положительные литералы (plus), а во второй части отрицательные (minus). Положительные литералы содержат условия, которые должны выполняться на объектах, удовлетворяющих правилу. Отрицательные литера лы, наоборот, содержат условия, которые не должны выпол няться на этих объектах. И те, и другие литералы имеют оди наковую структуру, а вместе называются просто литералами (literal):

z. (4) literal ::= oi = x | sj = y | ok = sk | ol = sl | os В литерале (literal) определяется либо один из признаков объ екта или субъекта связи, либо равенство или неравенство неко торого признака у объекта и субъекта связи, либо расстояние Сборник статей молодых ученых факультета ВМК МГУ, № 10, 40 П. В. Алейников между объектом и субъектом (число слов между ними +1).

Здесь o обозначает объект, а s субъект. Оба они представ лены в виде вектора из своих признаков, множество которых обозначается как F : o = {oi } |iF, s = {si } |iF. x и y некото рые значения признаков i и j соответственно;

z и границы диапазона расстояния между объектом и субъектом. Напри мер, так выглядит одно из построенных по алгоритму правил:

(sshortness = FULL) {(spos = ADJECTIVE)\ [(opos = CONJUNCTION) (opos = ADJECTIVE)]} [(sdegree = POSITIVE) \ (10 os 10)] (scase = ocase ) (sgender = ogender ) Это правило говорит о том, что связь типа определительная может выделяться между двумя словами, если одно из них полное прилагательное в позитивной форме, а другое не при лагательное и не союз, и при этом их падежи и рода совпадают, и они находятся на расстоянии менее 10 слов друг от друга. На пример, субъект своего и объект отца из предложения И ничего из бесстрашия своего отца она, похоже, не унаследова ла подходят под это правило.

3 Литералы (literal): используемые при знаки Как уже говорилось ранее, машинное обучение основано на анализе некоторых признаков объектов, входящих в целевой класс. В данном случае классы состоят из пар слов субъ ект связи объект связи. Используемые признаки это, в первую очередь, морфологические признаки объекта и субъек та. Они используются в условиях, обозначенных в формуле (4) как oi = x, sj = y, ok = sk и ol = sl. Условие первого вида го ворит об определённом значении морфологического признака i Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа у объекта связи, условие второго вида об определённом зна чении признака j у субъекта связи, условие третьего вида о равенстве значений признака k у объекта и субъекта, а усло вие четвёртого вида о несовпадении значений признака l у объекта и субъекта. При этом используется список морфологи ческих признаков, взятый из корпуса СинТагРус. В него вхо дят как стандартные морфологические признаки слова, такие как часть речи, лицо или падеж, так и некоторые другие, на пример, возможность использования в словообразовании. Все го признаков 19.

Некоторые признаки, выделяемые в корпусе, не использу ются в описываемом алгоритме, так как почти для всех слов из корпуса они принимают одно и тоже стандартное значение, и при этом не влияют на наличие и тип синтаксических связей между словами. Кроме того, не все признаки имеют смысл для каждой части речи. Например, для глаголов не имеет смысла падеж, а форма прилагательного имеет смысл только для при лагательных. Поэтому в алгоритм заложена таблица, содер жащая информацию о значимости каждого морфологического признака для каждой части речи, и незначительные признаки не рассматриваются при построении правил.


Условие z (последний вид из перечисленных os в формуле (4)) говорит о том, что расстояние между объек том и субъектом связи находится в пределах от до z. Этот вид условий был введён для того, чтобы можно было учесть, что обычно объект и субъект связи расположены достаточно близко друг к другу.

Приведём пример разобранного фрагмента предложения с несколькими выделенными признаками: как мне грустно.

Здесь между субъектом мне и объектом грустно есть связь, обозначенная в разметке как дательный субъект. Эта связь имеет, в том числе, такие признаки:

spos = PRONOUN часть речи субъекта ( мне ) местоимение;

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 42 П. В. Алейников падеж субъекта ( мне ) дательный;

scase = DATIVE форма объекта ( грустно ) краткая;

oshortness = SHORT onumber = SINGLE число объекта ( грустно ) единственное.

Конечно, самый показательный признак среди них это scase = DATIVE, падеж субъекта ( мне ) дательный.

4 НЭД: Не-Элементарные Дизъюнкции (disjunction), объединение литералов В формуле (3) показано, что НЭД состоит из нескольких элементарных условий, объединённых знаком дизъюнкции, и, возможно, отрицания нескольких других элементарных усло вий, также объединённых знаком дизъюнкции. Описываемый алгоритм составляет НЭД таким образом, что все положитель ные элементарные условия в каждой отдельной НЭД определя ют значение либо одного и того же морфологического призна ка объекта связи, либо одного признака субъекта связи, либо дизъюнкция содержит только одно условие. Таким образом, условие на равенство или неравенство некоторого признака у объекта или субъекта связи, а также условие, ограничивающее диапазон допустимых расстояний между объектом и субъек том связи, может входить только в НЭД, состоящую из одного этого условия. Точно так же ограничены и отрицательные эле ментарные условия каждой НЭД.

Алгоритм просматривает текст обучающей выборки только один раз, и во время этого просмотра для каждого типа син таксических связей строится набор НЭД. В набор для каждого типа связей входят НЭД нескольких видов:

• по одной НЭД для каждого морфологического признака объекта связи;

• по одной НЭД для каждого признака субъекта связи;

Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа • по одной НЭД, состоящей из условия на равенство или неравенство значений каждого морфологического при знака у объекта и субъекта связи;

• одна отдельная НЭД для диапазона расстояний между словами в связи.

При этом в дизъюнкцию добавляются только элементарные условия, соответствующие значениям, которые действительно встречаются в примерах на связь рассматриваемого типа. На пример, если у связи некоторого типа могут быть объекты существительные, то в дизъюнкцию, соответствующую части речи объекта связи данного типа, можно добавить условие opos = NOUN.

Строя каждую НЭД, алгоритм всякий раз добавляет в неё то положительное условие, которому удовлетворяет наиболь шее число примеров на связь рассматриваемого типа. То есть, если связью данного типа связаны пары слов, в которых у субъектов чаще всего встречается именительный падеж, и ме нее часто родительный, то в дизъюнкцию, соответствующую падежу субъекта связи данного типа, сначала будет добавлено условие scase = NOMINATIVE (ИМЕНИТЕЛЬНЫЙ), а затем может быть добавлено условие scase = GENITIVE (РОДИ ТЕЛЬНЫЙ).

Необходимо теперь заметить, что у алгоритма есть два па раметра это задаваемые пользователем точность и полнота правил. Точность (precision) и полнота (recall) [8] это две основных независимых оценки результатов работы алгоритма машинного обучения. Чтобы определить их, вначале опреде лим понятие целевого класса. Рассмотрим частный случай за дачи машинного обучения: пусть достаточно определить, при надлежит ли объект некоторому классу или нет, и не требуется классифицировать объект по нескольким классам. Например, в нашем случае это будет вопрос о том, связана ли пара слов или нет, или связаны ли слова из этой пары связью заранее определённого типа. В таком случае класс, на принадлежность Сборник статей молодых ученых факультета ВМК МГУ, № 10, 44 П. В. Алейников которому проверяется объект, называется целевым классом, а дополнение этого класса до глобального множества значений объекта называется нецелевым классом.

При такой постановке задачи при работе алгоритма могут возникнуть ошибки двух видов:

• алгоритм относит объект из нецелевого класса к целевому классу (в нашем случае, алгоритм считает несвязанные слова связанными некоторой связью);

• алгоритм относит объект из целевого класса к нецелево му классу (наоборот, алгоритм считает связанные слова несвязанными).

В [9] указаны формулы для оценки точности и полноты на при мере задачи информационного поиска. В данном случае, если обозначить T • NP число объектов целевого класса, отнесённых алго ритмом к целевому классу;

F • NP число объектов нецелевого класса, отнесённых ал горитмом к целевому классу;

F • NN число объектов целевого класса, отнесённых алго ритмом к нецелевому классу;

T • NN число объектов нецелевого класса, отнесённых ал горитмом к нецелевому классу;

то эти формулы принимают следующий вид:

T NT NP ;

R= T P F. (5) P= T F + NP NP + NN NP Здесь P обозначает точность, а R полноту. Из этих формул следует, что ошибки первого вида понижают точность, а ошиб ки второго вида полноту результатов работы алгоритма.

Требуемые точность и полнота принимают действительные значения в диапозоне от 0 до 1. Итак, положительные элемен тарные условия будут добавляться в дизъюнкцию до тех пор, пока доля покрытых ими примеров на связь рассматриваемо го типа среди всех примеров на связь этого типа не превы Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа сит требуемого значения полноты правил. Таким образом, ред ко встречающиеся значения соответствующего признака будут опущены. Это понижает зависимость системы правил от влия ния конкретного корпуса, причём полнота правил должна оста ваться не ниже установленного значения.

Например, пусть в 68 примерах на связь предикат субъ ект связи находится в именительном падеже, а в 4 примерах в родительном падеже, и ещё в 4 примерах падеж не опреде лён, так как часть речи субъекта связи глагол или союз.

Пусть также требуемая полнота 0.8, то есть 80 %. Тогда в дизъюнкцию, соответствующую падежу субъекта связи пре дикат, сначала будет добавлено условие scase = NOMINATIVE (именительный падеж субъекта). Затем будет подсчитано, что добавленное условие покрывает более 89 % примеров на эту связь, и процесс остановится, условие scase = GENITIVE (ро дительный падеж субъекта) добавлено не будет.

В результате описанного выше построения НЭД для каж дого типа связей будут составлены наборы из 58 этих элемен тов 19 для различных признаков объекта связи, 19 для раз ных признаков субъекта связи, 19 для равенства всевозмож ных признаков у объекта и субъекта связи и 1 для диапазона расстояния между объектом и субъектом связи. Всего будет создано 70 58 = 4060 НЭД для 70 типов связей. После это го из них можно составлять конъюнкции, а из конъюнкций формулы.

5 Конъюнкции (conjunction) и формулы (formula): условия остановки алгоритма После построения наборов дизъюнкций перед нами откры ваются большие возможности выбора элементов, из которых можно составить формулы. Но если построить правила из всех условий, которые можно получить из обучающей выборки, то в результатах проявится так называемый эффект переобуче Сборник статей молодых ученых факультета ВМК МГУ, № 10, 46 П. В. Алейников ния. То есть, система правил будет точно отображать обуча ющую выборку, но при этом, возможно, будет часто ошибать ся на текстах, не входящих в неё. Чтобы избежать этого эф фекта, необходимо ограничить количество элементов, которые могут входить в каждую конъюнкцию (это число отвечает за точность формулы) и количество конъюнкций, которые могут входить в каждую формулу (это число отвечает за её полно ту). Алгоритм уменьшает эти числа, добавляя новые элемен ты в систему формул лишь до тех пор, пока не будут достиг нуты требуемые пользователем значения точности и полноты результатов работы алгоритма.

В [10] рассматривается алгоритм, реализующий метод ре шающих правил, классифицирующий состояния пациентов в больнице, со структурой правил, похожей на выбранную для данного алгоритма:

A = K1 K2... Kq причём Ki является конъюнкцией pi элементов множества ат рибутов Tm. В этой работе предлагается метод последователь ного добавления в правило лучших атрибутов и утверждается, что данный метод приводит к максимизации эффективности правила. В описываемом нами алгоритме также используется такая техника: чтобы повысить точность алгоритма, дизъюнк ции в формуле (2) объединяются в конъюнкции, а чтобы полу чить достаточную полноту, конъюнкции в формуле (1) снова объединяются в глобальную дизъюнкцию. В самом деле, до бавляя в формулу новые элементы через знак дизъюнкции, мы расширяем множество объектов, относимых алгоритмом к целевому классу. Если добавляются правильные элементы, действительно описывающие целевой класс, то среди объектов, добавленных в множество относимых алгоритмом к целевому классу, будет большая доля классифицированных правильно.


T MF MP T F F T N MP · NN MN · NP T F NP NN Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа T T T F T T T F NP · NP + NP · NN + MP · NP + MP · NN T T T F T T F T NP · NP + NP · NN + MP · NP + MN · NP T T T F T T F T F (NP + MP ) · (NP + NN ) NP · (NP + NN + MP + MN ) T T NT NP + MP T P F R R.

T T F F NP + MP + NN + MN NP + NN T Здесь увеличение NP после добавления нового элемента обо T, а увеличение N F F значено как MP как MN. Таким образом, N T будет больше, чем у N F, полнота если относительный рост NP N формулы повысится.

Наоборот, добавляя в формулу новые элементы через знак конъюнкции, мы сужаем множество объектов, относимых алго ритмом к целевому классу. При этом среди удалённых из этого множества объектов должна быть большая доля классифици рованных неправильно. Точнее, если относительное снижение F T NP будет больше, чем у NP, точность формулы повысится:

T пусть после добавления нового элемента NP уменьшилось на T, а N F уменьшилось на LF, тогда LP P P LT LF P LT · NP LF · NP LT · NP LF · NP F T F T P P P P P T F NP NP NP · NP NP · LT + NP · NP LT · NP T T T F T F P P NP · NP NP · LT + NP · NP LF · NP T T T F T T P P (NP + NP ) · (NP LT ) NP · (NP LT + NP LF ) T F T T T F P P P NP LT T NT P T P F P P.

NP L T + NP L F T F NP + NP P P Таким образом, алгоритм добавляет в конъюнкцию дизъюнк ции до достижения требуемого значения точности, а в форму лу добавляет элементы до достижения необходимого значения полноты.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 48 П. В. Алейников 6 Структура процесса работы программ ной системы Построение системы правил происходит итеративно. А именно, процесс работы программы состоит из повторяющихся одинаковых циклов, каждый из которых состоит из повторяю щихся одинаковых шагов. Перед началом первого цикла своей работы программа строит необходимые наборы НЭД для всех типов связей так, как описано выше. Все правила изначально считаются пустыми, они не содержат никаких конъюнкций. В начале каждого цикла ко всем правилам, построение которых ещё не завершено, добавляется так называемая строящаяся конъюнкция, построение которой начнётся с этого момента.

Изначально строящаяся конъюнкция пустая она не содер жит ни одной дизъюнкции. Если во время цикла работы по строение какой-то из строящихся конъюнкций завершается по описанному выше условию остановки, она теряет свой статус строящейся, становясь обыкновенной, и в соответствующее ей правило добавляется новая строящаяся конъюнкция, также изначально пустая. Каждый шаг работы состоит из несколь ких этапов: сначала выбираются наилучшие дизъюнкции, за тем выбирается текущий тип связей, и наконец происходит переход к следующему шагу работы. На каждом шаге своей ра боты программная система пытается добавить в систему пра вил одну очередную НЭД из построенных наборов.

6.1 Выбор наилучших дизъюнкций В начале каждого шага своей работы программная система выбирает наилучшие дизъюнкции в наборах для каждого типа связей. При этом дизъюнкции сравниваются по особой мере, учитывающей и их точность, и их полноту. Выбор этой меры был сделан опытным путем. Сначала в качестве этой меры те стировались просто полнота и точность. Однако, если взять только одну из этих оценок, у генерируемых правил понижа Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа ется противоположная оценка точность и полнота соответ ственно. Кроме самих полноты и точности, тестировались сме шанные меры в виде их суммы и произведения:

E1 = P + R;

E2 = P R.

Однако, наилучший результат был достигнут при использова нии сбалансированной F1 -меры [9], которая оценивает с одина ковым весом и полноту, и точность дизъюнкции:

2·P ·R F1 =.

P +R Здесь, как и раньше, P обозначает точность, а R полноту.

Добавим, что искать наилучшую дизъюнкцию во всех наборах для разных типов связей на каждом шаге работы не обязатель но. Поскольку на каждом шаге в систему правил добавляется только одна дизъюнкция, достаточно после окончания шага пе ресчитать наилучшую дизъюнкцию для типа связей, дизъюнк ция от которого была добавлена на этом шаге, а остальные наилучшие дизъюнкции оставить прежними.

Заметим, что в общем случае один объект может подходить под несколько различных правил. Из-за такой конкуренции в алгоритме решено было использовать гибкие правила, то есть правила, ставящие в соответствие паре слов не чёткий ответ, существует ли между этими словами связь соответствующего типа, а значение характеристической функции существования связи данного типа между её аргументами-словами, как было описано выше. А именно, каждому правилу при его построе нии придаётся вес, который оно ставит в соответствие каждой паре слов, удовлетворяющей его условию. Парам слов, не удо влетворяющим условию правила, ставится в соответствие 0. В качестве веса правила предлагается использовать его точность.

Таким образом, пара слов считается связанной тем типом свя зей, который соответствует правилу с наибольшей точностью среди тех, условиям которых удовлетворяет данная пара слов.

Сборник статей молодых ученых факультета ВМК МГУ, № 10, 50 П. В. Алейников Однако, при подсчёте точности как раз требуется определить, к какому типу связей система правил относит пару слов по лучается замкнутый круг. Поэтому на каждом этапе построе ния системы правил при подсчёте весов правил используется точность, подсчитанная на предыдущем шаге.

В результате описанных действий для всех типов связей из соответствующих им наборов дизъюнкций выбраны наилуч шие. Они являются потенциальными кандидатами на добавле ние в строящиеся конъюнкции. На данном шаге работы остаёт ся только определить так называемый текущий тип связей, наилучшая дизъюнкция из набора которого и будет добавлена в соответствующее ей правило.

6.2 Выбор текущего типа связей Этот выбор происходит с использованием другого крите рия в данном случае используется просто точность. Эта ме ра выбрана потому, что нам важно, чтобы в первую очередь в систему правил попали конъюнкции с наибольшей точностью, и вот почему. Данный алгоритм достигает требуемой точности генерируемых правил благодаря последовательному добавле нию в систему правил конъюнкций, гарантированно обладаю щих этой требуемой точностью. Если это условие выполнено, в любой момент в системе правил содержатся только достаточно точные конъюнкции. Если выбрать одну из этих конъюнкций, можно подсчитать число примеров, на которых она допуска ет ошибки первого вида: алгоритм считает несвязанные сло ва связанными некоторой связью, или, в данном случае, конъ юнкция выигрывает в конкуренции за примеры, которые не относятся к соответствующему этой конъюнкции типу связей.

Тогда, если конъюнкция обладает требуемой точностью, коли чество таких примеров будет достаточно незначительным. В этом случае каждая конъюнкция, уже добавленная в систему правил, будет выигрывать в конкуренции за некоторые приме ры, относящиеся к соответствующему этой конъюнкции типу Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа связи. Благодаря этому во время последующих этапов работы алгоритма эти примеры уже не смогут войти в число примеров, которые по ошибке относятся системой к другому типу связей.

В результате другие типы связей получат преимущество в точ ности своих дизъюнкций, раз число их ошибок первого вида сократится.

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

T Здесь NP число примеров, в которых слова относятся к связи рассматриваемого типа, и на которых в конкуренции победило F именно правило для этого типа связей. Также NP число при меров, в которых слова относятся к связи другого типа или не относятся ни к одному из типов связей, но на которых тем не менее в конкуренции победило именно правило для рассматри ваемого типа связей. Текущим типом связей выбирается тот, у которого наилучшая дизъюнкция получила наибольшее значе ние точности. Подсчитанное значение точности для текущего типа связей записывается и может использоваться на следую щем шаге работы алгоритма в конкуренции правил за примеры как вес правила для типа связей, на данном шаге объявленного текущим.

Когда правила конкурируют за примеры, кроме связан ных пар слов из обучающей выборки они обрабатывают также несвязанные пары слов из предложений текста. Эти примеры с несвязанными парами слов названы отрицательными, так Сборник статей молодых ученых факультета ВМК МГУ, № 10, 52 П. В. Алейников как они принадлежат нецелевому классу в задаче определения, связана ли синтаксически пара слов. Отрицательные примеры введены в алгоритм для того, чтобы учесть, что системе пра вил предстоит не только определять, какого типа связь меж ду парой слов, но и, в общем случае, связаны ли некоторые слова или нет. Такие примеры генерируются алгоритмом са мостоятельно по обучающей выборке. Их количество в некото рое заданное пользователем число раз больше числа положи тельных примеров то есть, примеров связанных пар слов, которые берутся из обучающей выборки. Алгоритм для каж дого положительного примера выбирает заданное число слов в том же предложении, не связанных синтаксически с субъек том связи из рассматриваемого положительного примера. Если число слов в предложении делает невозможным выбор требуе мого числа отрицательных примеров, выбирается столько слов, сколько возможно. Каждое найденное слово алгоритм объеди няет в пару с субъектом связи из рассматриваемого положи тельного примера и записывает созданные пары в набор отри цательных примеров.

Когда текущий тип связей выбран, алгоритм пытается до бавить наилучшую дизъюнкцию этого типа связей к соответ ствующей строящейся конъюнкции. При этом алгоритм прохо дит через серию проверок, чтобы определить, какой результат достигнут на данном шаге его работы.

6.3 Переход к следующему шагу и завершение ра боты Когда алгоритм выбрал текущий тип связей, он проверя ет, повышается ли точность у его строящейся конъюнкции при добавлении в неё наилучшей дизъюнкции из набора того же текущего типа связей. Если точность понижается, добавление отменяется, и эту дизъюнкцию больше не пытаются добавить в правило и в дальнейшем. В противном случае дизъюнкция вставляется на своё место, и алгоритм проверяет, достигла ли Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа строящаяся конъюнкция текущего типа связей требуемого зна чения точности. Если необходимое значение ещё не достигнуто, алгоритм пытается добавить к только что вставленной дизъ юнкции отрицательные элементы.

Пока НЭД не добавлена в формулу, она не имеет отрица тельных условий. Когда необходимо добавить в НЭД отрица тельные условия, алгоритм собирает статистику по всем при мерам из обучающей выборки, не относящимся к рассматри ваемому типу связей, которые построенное правило классифи цирует ошибочно. После чего точно так же, как для положи тельных условий, строится набор дизъюнкций, описывающих собранные примеры. Из набора построенных дизъюнкций вы бирается одна тем же образом, которым выбирается наилуч шая дизъюнкция в наборе некоторого типа связей. Выбранная дизъюнкция отрицательных условий становится отрицатель ной частью НЭД, добавленной в формулу. При этом алгоритм следит за тем, чтобы отрицательные условия не вступали в противоречие с положительными.

После добавления отрицательных условий в НЭД алгоритм снова производит проверку точности конъюнкции. Если на мо мент второй проверки требуемое значение все ещё не достиг нуто, алгоритм переходит на следующий шаг и построение си стемы правил продолжается. Если же в какой-то момент необ ходимое значение достигнуто, построенная конъюнкция добав ляется к правилу для текущего типа связей, и алгоритм про веряет, не достигла ли построенная часть правила требуемого значения полноты. В том случае, если необходимое значение достигнуто, создание правила для текущего типа связей пре кращается. Иначе множество примеров, причисленных к связи текущего типа, сокращается: из этого множества удаляются примеры, удовлетворяющие построенной конъюнкции. Остав шиеся примеры пока не удовлетворяют построенной части пра вила, и их можно использовать для построения последующих конъюнкций в этом правиле. Кроме того, алгоритм обновля Сборник статей молодых ученых факультета ВМК МГУ, № 10, 54 П. В. Алейников ет набор дизъюнкций для текущего типа связей, так как его элементы теряют актуальность.

Цикл работы завершается, когда для всех типов связей нет возможности или необходимости добавлять новые конъюнк ции в формулы. Для конкретного типа связей это может быть вызвано либо тем, что построено достаточно конъюнкций и достигнута требуемая полнота, либо тем, что все возможные дизъюнкции были выбраны и набор для данного типа связей пуст. Во втором случае последняя конъюнкция для данного типа связей оказывается недостроенной. Если её точность не меньше требуемой, она добавляется в формулу, в противном случае от неё отказываются. После завершения цикла алго ритм в первую очередь проверяет, были ли добавлены в систе му правил новые элементы во время этого цикла. Если нет, то цикл не принёс изменений и алгоритм переходит в состояние завершения. В ином случае проверяется, есть ли типы связей, правила для которых не достроены то есть, для которых не достигнуто требуемое значение полноты. Если таких правил нет, то алгоритм успешно завершается. В противном случае та ким типам связей даётся второй шанс запускается новый цикл работы, на котором эти правила могут заново попытаться построить несколько конъюнкций.

Наконец, находясь в состоянии завершения, алгоритм про веряет, достигнута ли требуемая полнота на всех типах свя зей. Для тех из них, для которых заданное значение полноты не достигнуто, алгоритм особо выделяет соответствующие им правила как недоработанные.

7 Реализация. Оценка эффективности ал горитма Описанный алгоритм был реализован в виде программ ной системы STAR AGES Syntax Texts Analysis of Russian Automated Generator of rulEs Systems. В ходе тестирования Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа программы было обнаружено, что для некоторых типов связей требуемые значения оценок достигаются уже после небольшого числа шагов работы, сделанных программной системой. Одна ко также были обнаружены типы связей, для которых требу емые значения оценок не достигаются даже при вовлечении в правило всех доступных дизъюнкций.

Результаты работы программной системы отличаются при обработке разных текстов в качестве обучающей выборки. Кро ме того, в программе используются генерируемые случайным образом отрицательные примеры, и благодаря этому резуль таты работы отличаются даже при последовательных запус ках программы на одном и том же корпусе текстов. Также, поскольку алгоритм статистический, он требует длительного времени для тестирования и оптимизации.

Для того, чтобы упростить тестирование программы и оценку результатов её работы, было предложено использовать для управления работой программной системы графический пользовательский интерфейс. Интерфейс предоставит пользо вателю удобную визуализацию начальных данных, процесса построения системы правил и результатов работы алгоритма, а также возможность экспериментировать с порядком добавле ния элементов в правила. Благодаря этому интерфейсу можно будет эффективно составлять системы правил для корпусов специализированных текстов, а также улучшать оценки авто матически генерируемой системы правил. Удобства для тести рования, предоставляемые интерфейсом, позволят обработать корпуса текстов большего объема, сделать более точные выво ды о работе программы и помогут откорректировать алгоритм.

Оценить правильность сгенерированной системы правил может только эксперт-лингвист. Однако, не имея в своём распо ряжении профессионального лингвиста, пользователь описан ной программной системы всё же может проверить полученную систему правил. Для этого можно воспользоваться, например, методом кросс-валидации [11]. Суть этого метода заключает Сборник статей молодых ученых факультета ВМК МГУ, № 10, 56 П. В. Алейников Таблица 1. Зависимость точности результатов от параметров Требуемая Требуемая полнота точность 80 50 80 64.26 67.00 63. 50 50.26 47.43 51. 20 25.69 24.57 23. Таблица 2. Зависимость полноты результатов от параметров Требуемая Требуемая полнота точность 80 50 80 33.93 27.71 22. 50 47.07 40.57 36. 20 60.19 55.00 52. ся в том, что исходная выборка делится несколькими способа ми на две части: обучающую и контрольную выборки. Затем для каждого варианта разбиения исходной выборки алгоритм генерирует систему правил по обучающей выборке. На осно ве сгенерированных правил делается синтаксическая размет ка контрольной выборки, которая сравнивается с имеющейся разметкой. Затем подсчитывается количество несовпадений и вычисляется средняя ошибка на элементах контрольной вы борки. Оценкой скользящего контроля называется средняя по всем разбиениям величина ошибки на контрольных выборках.

Таблица 3. Зависимость F-меры результатов от параметров Требуемая Требуемая полнота точность 80 50 80 44.41 39.21 33. 50 48.61 43.73 42. 20 36.01 33.97 32. Сборник статей молодых ученых факультета ВМК МГУ, № 10, Генерация правил для синтаксического анализа Из таблицы 1 можно заметить, что точность результатов работы практически не зависит от требуемого значения пол ноты. Зависимость точности результатов от требуемого значе ния точности прямая. Но при этом, если для требуемых зна чений точности 20% и 50% точность результатов превышает требуемое значение, то для требуемого значения точности 80% точность результатов колеблется около 65%. Кроме того, при проведении экспериментов было отмечено, что с повышением требуемого значения точности увеличивается разброс значений точности результатов для разных обучающих выборок. В неко торых случаях точность результатов составляла более требуе мого значения 80%, а в некоторых случаях падала ниже 20%.

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



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.