Процессы управления и устойчивость

2. На 13 процессорах вычислим 13 различных разностей экспо-

нент и умножим их на другую экспоненту — β

mul

+ β

ad

так-

та. Умножим результат на константы α и β и, одновременно

с этим, вычислим произведение экспонент и констант: потре-

буется 3 процессора β

mul

такта. Обменяемся данными за β

tr

тактов.

3. На 5 процессорах сложим произведение экспонент на их раз-

ность (2β

ad

такта). На 3-х процессорах выполним умножение

экспонент на скобки, перед вычислением дроби в числителе по-

меняемся данными, т.е. еще 3β

mul

+ βtr такта.

4. Считаем дробь в числителе, отнимаем ее от оставшейся разно-

сти и заканчиваем вычисление делением числителя на знаме-

натель. Всего 2β

mul

+ β

ad

такта на одном процессоре.

Суммируем длительность действий 1–4 и получим искомые функци-

оналы длительности. Случаи 1 и 2 доказываются аналогично.

В данном случае вычисление вторым способом намного превос-

ходит вычисление первым, минимальный выигрыш 3β

mul

− 2β

ad

.

Литература

1. Демьянович Ю.К. Гладкость пространств сплайнов и всплеско-

вые разложения // Докл. АН, 2005. Т. 401, № 4. С. 1–4.

2. Демьянович Ю.К. Локальная аппроксимация на многообразии

минимальные сплайны. СПб.: Изд-во СПбГУ, 1994. 356 с.

3. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. Методы

сплайн-функций. М.: Наука, 1980. 352 с.

395

Пашкин М.В.

Санкт-Петербургский государственный университет

Применение нейронных сетей при разработке

алгоритма в игре "виртуальный футбол"

Рекомендовано к публикации ассистентом Антоновым С.А.

Введение. С развитием вычислительной техники появляются

всё новые и новые задачи. Причём такие, о которых первые кон-

структоры не могли и предполагать. Сначала это были программы

для обработки числовых массивов, которые использовались в науч-

ных центрах. Затем постепенно программы стали приобретать при-

кладной характер, появились "игрушки". Сегодня компьютеры име-

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

Появилась возможность решать задачи искусственного интеллекта.

Задачи стали комбинироваться. С одной из таких комбинаций мы и

будем работать: виртуальный футбол, в который играют мобильные

роботы.

Проект "Виртуальный футбол" родился в стенах МГУ и пред-

ставляет собой следующее. Есть программа-сервер, которая предо-

ставляет средства для управления игроками. К этой программе по-

средством плагинов подключаются две команды, оформленные в ви-

де DLL-модулей. Разработкой этих модулей участники проекта и за-

нимаются.

В данной работе предлагается принципиально новый метод раз-

работки программ управления игроками. Суть его в использовании

нейронных сетей (НС). НС – это самообучающаяся структура. На

этапе подготовки к соревнованиям теперь надо будет не придумы-

вать изощренный алгоритм, а соответствующим образом обучать

НС, которая и будет управлять игроками.

Введение в нейронные сети. Теория нейронных сетей вклю-

чает широкий круг вопросов из разных областей науки: биофизики,

математики, информатики, схемотехники и технологии. Поэтому по-

нятие "нейронные сети" детально определить сложно.

Искусственные нейронные сети (НС) – совокупность моделей био-

логических нейронных сетей. Представляют собой сеть элементов –

искусственных нейронов – связанных между собой синаптическими

396

соединениями. Сеть обрабатывает входную информацию и в процес-

се изменения своего состояния во времени формирует совокупность

выходных сигналов.

Работа сети состоит в преобразовании входных сигналов во вре-

мени, в результате чего меняется внутреннее состояние сети и фор-

мируются выходные воздействия.

Все модели НС требуют обучения. В общем случае, обучение – та-

кой выбор параметров сети, при котором сеть лучше всего справля-

ется с поставленной проблемой. Обучение – это задача многомерной

оптимизации, и для ее решения существует множество алгоритмов.

Искусственные нейронные сети – набор математических и алго-

ритмических методов для решения широкого круга задач. Выделим

характерные черты искусственных нейросетей как универсального

инструмента для решения задач:

1. НС дают возможность лучше понять организацию нервной си-

стемы человека и животных средних уровней: память, обработ-

ка сенсорной информации, моторика.

2. НС – средство обработки информации:

• гибкая модель для нелинейной аппроксимации многомер-

ных функций;

• средство прогнозирования во времени для процессов, за-

висящих от многих переменных;

• классификатор по многим признакам, дающий разбиение

входного пространства на области;

• средство распознавания образов;

• инструмент для поиска по ассоциациям;

• модель для поиска закономерностей в массивах данных.

3. НС свободны от ограничений обычных компьютеров благодаря

параллельной обработке и сильной связанности нейронов.

В перспективе НС должны помочь понять принципы, на кото-

рых построены высшие функции нервной системы: сознание, эмоции,

мышление. Основные положения теории нейронных сетей описаны в

[1, 2].

Многослойный персептрон. Алгоритм обратного распро-

странения ошибки. Таким образом, полный алгоритм обучения

НС с помощью процедуры обратного распространения строится так:

397

1. Подать на входы сети один из возможных образов и в режиме

обычного функционирования НС, когда сигналы распростра-

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

s

(n)

j

= Σ

M

i=0

y

(n−1)

i

ω

n

ij

,

где M – число нейронов в слое n − 1 с учетом нейрона с

постоянным выходным состоянием +1, задающего смещение;

y

n−1

i

= x

(n)

ij

– i-ый вход нейрона j слоя n. Кроме того,

y

(n)

j

= f (s

(n)

j

), y

q

(0) = I

q

. Здесь f () – сигмоид, I

q

– q-ая компо-

нента вектора входного образа.

2. Расcчитать для слоя N :

δ

(N )

j

= (y

(N )

i

− d

i

)

dy

i

ds

i

,

∆ω

(n)

ij

= −ηδ

(n)

j

y

(n−1)

i

,

∆ω

(n)

ij

(t) = −η µ∆ω

(n)

ij

(t − 1) + (1 − µ)δ

(n)

j

y

(n−1)

i

.

3. Рассчитать для всех остальных слоев, n = N − 1, . . . , 1,

δ

(n)

j

=

k

δ

(n+1)

k

ω

(n+1)

jk

dy

j

ds

j

,

∆ω

(n)

ij

= −ηδ

(n)

j

y

(n−1)

i

.

4. Скорректировать все веса в НС:

ω

i

j

(n)

(t) = ω

i

j

(n)

(t − 1) + δω

(n)

ij

(t).

5. Если ошибка сети существенна, перейти на шаг 1. В противном

случае – конец.

Сети на шаге 1 попеременно в случайном порядке предъявляются

все тренировочные образы, чтобы сеть, образно говоря, не забывала

одни по мере запоминания других.

Постановка задачи. Есть футбольное поле известных разме-

ров. Есть ворота известной ширины. На поле присутствуют две ко-

манды. Каждый игрок "видит все поле", т.е. что, куда движется.

Обычно подпрограммы управления игроками проектируются исхо-

дя из следующих соображений:

398

• у каждого игрока есть свои мысли;

• каждый игрок может читать мысли других игроков;

• игроки следят за противником, изучают его повадки;

• на основе выслеженных данных делать предположения, что бу-

дет делать противник и использовать это в своих интересах;

• нет разделения должностей (нападающий, защитник, вратарь).

Каждый игрок владеет всеми навыками в совершенстве. Тре-

буемое действие осуществляет игрок, который быстрее может

его исполнить и не занят.

Требуется разработать алгоритм управления игроками, отвечаю-

щий этим требованиям.

Для наблюдения за ходом игры и управления игроками сервер

предоставляет набор различных функций, с которыми можно озна-

комиться в SDK. Управление игроками осуществляется путём сооб-

щения серверу желаемых угловой скорости w и ускорения a. В нашем

случае проектирование программы управления сводится к обучению

НС, на входы которой подается текущая ситуация игры, а на выходе

снимаются a и w. Для этого потребуется реализовать следующее:

• функцию управления игроками. Не важно как они будут дви-

гаться, главное чтобы это было более или менее случайно;

• протоколирование игры. Чтобы в дальнейшем на основе полу-

ченной

информации

сформировать

примеры

для

обучения НС;

• инструментарий для обучения;

• DLL-модуль, управляющий командой игроков, который будет

представлять собой интерфейс между сервером и НС.

Процесс решения задачи. Изначально использовался трех-

слойный персептрон со входным слоем. Входы – текущее состояние

игры, выходы – параметры управления своими игроками. Число вхо-

дов равняется числу изменяемых параметров процесса игры. Чис-

ло выходов – числу игроков, умноженному на два (два параметра

управления). Для обучения сети использовался алгоритм обратного

распространения ошибки. Данные на вход поступают в нормализо-

ванном виде, т.е. приведенными к промежутку [0,1]. На выходе дан-

ные также нормализованы. Для обучения сети необходимы приме-

ры, для их получения создана команда, в которой игроки хаотично

399

перемещаются по полю и запоминают все действия противников (в

бинарном файле). Затем этот бинарный файл преобразуется в обуча-

ющие пары вход/выход, с помощью которых и происходит обучение

сети. Из-за относительно простой структуры сети здесь возникла

проблема: большинству примеров сеть не смогла обучиться, так как

выходная ошибка сети была слишком большая.

После первой неудачи было принято решение использовать сеть

Хопфилда, которая часто применяется для реализации ассоциатив-

ной памяти. Этот вариант тоже не подошёл, так как для данной

задачи на её реализацию потребовалось много памяти, поскольку

для каждого возможного состояния нужно добавлять новую группу

нейронов. Попытки сократить число нейронов для одного состояния

не увенчались успехом.

Сейчас создана модель персептрона с регулируемым числом

скрытых слоёв и числом нейронов в них, что привело к хорошей

обучаемости.

Заключение. В результате работы был реализован принципи-

ально новый метод проектирования программы управления игрока-

ми в виртуальном футболе. В дальнейшем планируется наделить

игроков эмоциями, применяя нечеткую логику.

На основе наблюдений за игрой выявляются некоторые устой-

чивые комбинации, которые в дальнейшем сохраняются и для них

перечисляется набор действий. Далее через некоторые промежутки

времени программа пытается отнести текущее состояние к одной из

этих ситуаций и осуществить соответствующее действие. Для одной

ситуации может быть предусмотрено несколько действий. Для от-

ношений ситуация-действие ведется статистика (успех/неудача) и в

соответствие с этой статистикой при наступлении схожей ситуации

корректируется действие.

Литература

1. Короткий

С.

Нейронные

сети:

основные

положения.

http://neuronet.alo.ru/biblioteka.html

2. И.В. Заенцев. Нейронные сети: основные модели. Воронеж, 1999.

76 с.

400

Перминов П.А.

Санкт-Петербургский государственный университет

Представление флексий в прямой задаче

морфологического анализа.

Анализ составных слов

Рекомендовано к публикации профессором Тузовым В.А.

В данной статье рассматриваются прямая и обратная задачи мор-

фологического анализа для русского языка, вводится метод пред-

ставления флексий для решения прямой задачи и описывается мор-

фологический анализатор, реализованный с использованием этого

метода. Также рассматривается представление составных слов в

морфологическом словаре и их анализ.

Введение. При создании систем обработки информации на есте-

ственном языке (NLP-системы) для синтетических языков сущест-

венную роль играет качество морфологического анализа. В отноше-

нии русского языка построение системы, которая могла бы охватить

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

ние этой проблемы должно, в частности, допускать расширение ис-

ходного словаря и уточнение значений морфологических описате-

лей. На сегодняшний день в большинстве систем поиск морфоло-

гических описателей выполнен в виде подпрограмм. Такой подход,

безусловно, дает выигрыш в скорости, но не позволяет проводить

тонкую настройку анализатора без внесения изменений в исходный

код. Предлагаемый здесь метод представления флексий решает эту

проблему, что делает возможным использование ядра анализатора

для морфологического анализа других языков.

1. Прямая и обратная задачи морфологического анализа.

Основные задачи, решаемые при морфологическом анализе – прямая

и обратная. Прямой задачей называется генерация по исходной фор-

ме слова (единственное число, именительный падеж – для склоняе-

мых частей речи, инфинитив – для глаголов) всей парадигмы это-

го слова. Обратная задача – восстановление по произвольной фор-

ме слова его основной формы и поиск морфологического описателя.

Обратная задача более трудоёмка, но в конечном итоге сводится в

данной реализации к прямой задаче.

1.1. Прямая задача. Прямая задача делится на два этапа: на

первом этапе строятся всевозможные формы исходной лексемы, на

401

втором этапе – их морфологические описатели. При реализации пря-

мой задачи для первого этапа применяется словарь, построенный по

словарю А. А. Зализняка [1], в котором приводятся лексемы с их со-

кращенной парадигмой. Этот словарь используется для построения

всех словоформ искомой лексемы. Общее количество словоформ, ко-

торое может быть построено по такому словарю, составляет около

двух миллионов. Словарная статья в данном словаре в БНФ-нота-

ции

1

имеет следующий вид:

<статья лексемы> ::= <лексема> <морфологическая помета>

[<окончания>][<модификатор основы> <окончания>]*

<окончания> ::= {<окончание>}*

Так для лексемы ЛЮБИТЬ словарная статья выглядит так:

ЛЮБИТЬ г4н л ло в вши вшY 1Л еннY ю

1 ишь ит им ите ят и ите я ящJ имY

Здесь г4н – это морфологическая помета, указывающая на то,

что лексема ЛЮБИТЬ является глаголом неопределенного вида

4-го класса спряжения; 1Л, 1 – модификаторы основ; л ло в вши

вшJ, еннY ю, ишь ит им ите ят и ите я ящJ имY – окончания сокра-

щенной парадигмы. По данной статье могут быть построены основы

с соответствующими окончаниями:

ЛЮБИ л ло в вши вшJ

ЛЮБЛ еннY ю

ЛЮБ ишь ит им ите ят и ите я ящJ имY

Первая основа строится из исходной лексемы по следующему ал-

горитму:

1. Если лексема принадлежит к глаголам, или прилагательным,

или существительным 12-го класса склонения, то

a) если лексема оканчивается на -СЬ или -СЯ, то оторвать от

неё 2 последние буквы;

b) если лексема оканчивается на гласную или -Й или -Ь, ото-

рвать от неё 2 последние буквы;

с) выход.

2. Если лексема оканчивается на гласную или -Й или -Ь, ото-

рвать от неё последнюю букву.

1

{}* –  повторяется 1 и более раз; []* –  повторяется

0 и более раз.

402

Вторая основа строится из первой при помощи первого модифи-

катора основы, третья – из второй при помощи второго модифика-

тора основы и т.д. по алгоритму:

1. Если модификатор основы начинается с цифры, то оторвать от

основы количество букв, равное этой цифре. Удалить цифру у

модификатора;

2. Добавить к основе модификатор.

По лексеме и полученным основам, путём прибавления к ним со-

ответствующих окончаний, строятся словоформы для сокращенной

парадигмы:

ЛЮБИТЬ= ЛЮБИл ЛЮБИло ЛЮБИв ЛЮБИвши ЛЮБИвшJ

ЛЮБЛеннY ЛЮБЛю ЛЮБишь ЛЮБит ЛЮБим ЛЮБите

ЛЮБят ЛЮБи ЛЮБите ЛЮБя ЛЮБящJ ЛЮБимY

Следующим шагом словоформы сокращённой парадигмы расши-

ряются до словоформ полной парадигмы. Для глаголов добавляют-

ся окончания действительных и страдательных причастий, а также

краткие формы страдательных причастий:

ЛЮБИТЬ ЛЮБИЛ

ЛЮБИЛО ЛЮБИВ

ЛЮБИВШИ

ЛЮБИВШИЙ

ЛЮБИВШЕГО ЛЮБИВШЕМУ ЛЮБИВШИМ ЛЮБИВШЕМ ЛЮБИВШАЯ

ЛЮБИВШЕЙ

ЛЮБИВШЕЮ

ЛЮБИВШУЮ

ЛЮБИВШЕЕ ЛЮБИВШИЕ

ЛЮБИВШИХ ЛЮБИВШИМИ ЛЮБЛЕННЫЙ ЛЮБЛЕННОГО ЛЮБЛЕННОМУ

ЛЮБЛЕННЫМ ЛЮБЛЕННОМ ЛЮБЛЕННАЯ

ЛЮБЛЕННОЙ ЛЮБЛЕННОЮ

ЛЮБЛЕННУЮ ЛЮБЛЕННОЕ ЛЮБЛЕННЫЕ ЛЮБЛЕННЫХ ЛЮБЛЕННЫМИ

ЛЮБЛЕН

ЛЮБЛЕНА ЛЮБЛЕНО

ЛЮБЛЕНЫ. . .

На втором этапе прямой задачи строится собственно полная пара-

дигма искомой лексемы, т.е. для каждой словоформы полной пара-

дигмы ищется соответствующий морфологический описатель. С этой

целью был введен метод представления флексий. Решение о присво-

ении того или иного морфологического описателя принимается на

основе морфологической пометы лексемы, окончания словоформы

сокращенной парадигмы, словоформе сокращённой парадигмы, сло-

воформе полной парадигмы и лексеме. Критерии, по которым про-

исходит отбор тех или иных морфологических описателей, равно как

и сами описатели, были представлены в виде следующей структуры:

БНФ:

<представление флексий> ::= {<морфологический блок>}*

<морфологический блок> ::= "{" [<маска морф. пометы>]*

<тело блока> "}"

<маска морф. пометы> ::= <маска И ИЛИ>

403

<тело блока> ::= { [<морфологический описатель>

[<флексия>]*] [<морфологический блок>] }*

<морфологический описатель> ::= "@Сущ.>" | "@Прил.>" |

"@Гл.>" | ... | "@Муж.Вин.Неодуш." | ...

<флексия> ::= <маска флексии> [<морфологическая помета>]*

<маска флексии> ::= <маска И>

<морфологическая помета> ::= "М0" | "М0о"| "Ж0" | "ж0" | ...

<маска И ИЛИ> ::=

{<маска И>}*

<маска И> ::= <маска> ["_" <маска>]*

<маска> ::= ["~"] ["*"] {<стринг> ["*"]}*

<стринг> ::= {<символ> | "?"}*

<символ> ::= "а" | ... | "я" | "А" | ... | "Я" | "+" | ...

Фрагмент данной структуры для глаголов выглядит следующим об-

разом:

{

г*

@Гл.>

{

~*Н*

@Перех.>

}

{

*Н*

@Неперех.>

}

{

~*н*

@Совер.>

}

{

*н*_~*с*

@Несовер.>

}

{

*н*_*с*

@Совер.@Несовер.>

}

{

*Б*

@Безл.>

...

}

{

~*Б*

@Инфин.>

=

{

~*с*

@Наст.1л.Ед.

*ю

*юсь

м

мся

у

усь

@Наст.2л.Ед.

*шь

*шься

...

}

{ *с*

@Буд.1л.Ед.

*ю

*юсь

м

мся

у

404

усь

@Буд.2л.Ед.

*шь

{

~г8с’1 ~г8сН’1

*шься

...

@Прош.Ед.Муж.

л

лся

-

}

{

@Прош.Ед.Муж.

-_~*ЯГ- г8с’1 г8сН’1

ся_*ЯГ- г8с’1 г8сН’1

}

@Прош.Ед.Жен.

ла

лась

...

@Прич.Дейст.Наст.>

*щJ

*щJся

@Прич.Страд.Наст.>

*мY

...

@Муж.Им.

*J_*ИЙ

*J*_*ИЙСЯ

*Y_*ЫЙ

@Муж.Род.

*J_*ЕГО

*J*_*ЕГОСЯ

*Y_*ОГО

...

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: