О

О.H.Граничин, М.А.Красоперова

ПРИМЕHЕHИЕ АЛГОРИТМА СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ

С ОДHОВРЕМЕHHЫМ ВОЗМУЩЕHИЕМ HА ВХОДЕ

В РЕКОHСТРУКТИВHОМ МОДЕЛИРОВАHИИ СТИХОСЛОЖЕHИЯ

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

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

Обычно при классификации стохастических алгоритмов оптимизации их условно разделяют на две группы. Одна группа алгоритмов базируется на прямых измерениях (или вычислениях) значений градиента целевой функции при различных оптимизируемых параметрах, другая — на аппроксимациях градиента на основании измерений значений функции, вообще говоря, с помехами. В настоящее время налицо рост заинтересованности практиков в рекуррентных алгоритмах оптимизации, которые не требуют знания точной информации о градиенте функции потерь или о ее измерениях. Это мотивируется, например, проблемами, возникающими при конструировании систем, работающих в реальном времени и реагирующих на сложные последовательные запросы, при синтезе адаптивных систем управления, в задачах статистической идентификации сложных систем, оптимизации вычислительных процессов при больших объемах моделирования по методу Монте-Карло, обучения рекуррентных нейронных сетей, распознавания изображений (образов), получаемых с помехами от сенсорных датчиков. Главное преимущество такого типа алгоритмов заключается в том, что они не требуют детальных знаний функциональных отношений между настраиваемыми параметрами и значением целевой функции, которые требуется в алгоритмах первого типа, основанных на использовании точного значения величины градиента. Такие отношения при решении некоторых задач зачастую трудно получить, а в других задачах (таких, как оптимизация, основанная на моделировании) при более или менее известных свойствах этих отношений возникают большие трудности при вычислении градиента, связанные с необходимостью многократно вычислять значение функции потерь. Напротив, подходы, основанные на аппроксимации градиента, требуют только преобразования основных измерений выхода к значениям "скачка" целевой функции, что не требует полного знания отношений между входами и выходами системы.

Последнее соображение наводит на мысль о том, что такого типа алгоритмы можно попытаться использовать при анализе восприятия человеком стихотворного текста. В этой области знаний принято с большой осторожностью говорить о возможности точного математического описания тех или иных аспектов творческой деятельности и механизмов их восприятия, тем более о "дифференцировании" какой-то минимизируемой функции, точный вид которой мало кто отважится написать. Но сам факт наличия каких-то качественных зависимостей признается многими учеными. В лингвистических исследованиях стихотворный текст занимает важное место как особого рода речь. При этом подвергаются анализу не общеязыковые черты этой речи, а такие специфические, как метрика, ритмика, рифма и строфика. Четкая формальная выраженность этих явлений создает благоприятные условия для их изучения с помощью математических методов. Ниже рассматривается возможность применения нового типа алгоритмов стохастической аппроксимации с возмущением на входе (см. [1]) для решения некоторой оптимизационной задачи, возникающей при исследовании ритмической структуры стихотворного текста.

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

Ядром системы реконструктивного моделирования является модель порождения и восприятия ритмической структуры стихотворного текста. В основу модели положена гипотеза, согласно которой при создании и восприятии стихотворного текста его ритмическая структура отделяется от звукового наполнения и поступает в ведение находящегося в мозгу специализированного механизма. Модель является упрощенным гипотетическим описанием этого механизма и его функций. Она имеет семиотический характер и не претендует на нейрофизиологическое описание. Модель построена в применении к русскому стиху классического размера.

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

В настоящей работе для оптимизации выбора наиболее подходящего представления компонентов ритмической строки, поступающих на вход механизма рецепции модели М.А.Красноперовой, предлагается использовать алгоритм стохастической аппроксимации с возмущением на входе из [1,3].

Механизм рецепции в реконструктивном моделировании стихосложения. Механизм рецепции состоит из оперативной памяти и механизма реализации ритмических строк. Оперативная память состоит из двух слоев — верхнего и нижнего. Каждый слой представляет собой последовательность разрядов. Каждый разряд может находиться в той или иной степени возбуждения, которая называется его значением. Механизм реализации ритмических строк в типичном случае обеспечивает определенные изменения значений разрядов оперативной памяти в процессе восприятия (порождения) очередной ритмической строки. Смысл этих изменений состоит в том, чтобы достичь подходящего компромиссного состояния между коррелятом предшествующих строк, накопившимся в оперативной памяти, и текущей ритмической строкой, поступающей на вход механизма рецепции. [1]

На вход механизма рецепции поступают ритмические строки, числовое представление которых определяется большим набором подстраиваемых параметров (начальное, конечное, максимальное значение каждого реализуемого слога ритмической строки, длины их участков подъема и спуска и др.). При переходе к описанию математической модели механизма рецепции необходимо предположить, что существует определенная программа представления ритмических строк в виде наборов числовых значений, упорядоченных слева направо в соответствии с текстом строки. Количественное представление последовательности слогов очередной ритмической строки зависит от многих факторов и обычно не может быть произведено однозначно. Более или менее строгому математическому описанию поддаются качественные соотношения между параметрами различных слогов в пределах одной ритмической строки. При "плохом" выборе параметров результаты функционирования механизма рецепции могут оказаться не только неадекватными языковым реалиям, но и неустойчивыми в математическом смысле, и соответственно ценность получаемых с его помощью характеристик “внутренней” системы ритмики стиха становится невысокой.

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

Будем считать, что каждый из слоев оперативной памяти имеет по l разрядов. Обозначим M1 и M2 наборы чисел, векторы, соответствующие состояниям верхнего и нижнего слоев,

Mi=(Mi[1],Mi[2],…,Mi[l]), i=1,2,

где Mi[j] — значение j-го разряда i-го слоя.

До начала работы механизма рецепции значения всех разрядов оперативной памяти могут быть равны нулю. Если строка является не первой, то в типичном случае к моменту ее реализации здесь остается след предшествующих строк. В [2] описан процесс изменения значений при реализации очередной ритмической строки. Способ реализации определяется, в частности, выбором некоторых параметров, связанных с процессом обмена значениями между верхним и нижним слоями оперативной памяти. Предположим, что к началу реализации в оперативной памяти остался “след” от предшествующих ритмических строк. Пусть очередная ритмическая строка задана также в виде набора из l чисел

S=(S[1],S[2],…,S[l])

с неотрицательными компонентами S[j], j=1,…,l.

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

На втором этапе для каждого ритмического слова сначала производится поразрядное сравнение последовательности его ожидаемых значений с теми значениями, которые имеются на соответствующем участке верхнего слоя оперативной памяти: S[j] сравнивается с M[j] для каждого j, такого что j=k[i],…, k[i]+w[i]-1, где k[i] — номер разряда с которого по первоначальной разметке начинается реализация i-го ритмического слова в оперативной памяти, а w[i] — количество отведенных для него разрядов В результате сравнения определяется одна из двух ситуаций:

1) S[j]≥M1[j] для любого j в указанной области изменений,

2) существуют j, для которых S[j]<M1[j].

Обе ситуации подробно описаны в работе [2]. Нас будет интересовать сейчас только вторая из них. В этой ситуации реализация ритмического слова происходит по более сложному алгоритму, чем в первой, так как процесс сталкивается с “сопротивлением” накопленной ранее основы ритмической структуры предшествующего текста. Так как количественное представление ритмического слова неоднозначно, одним из способов разрешения возникающего конфликта является корректировка формы его представления: изменение соответствующей ритмическому слову последовательности числовых значений. Характер корректировки определяется при предварительном рассмотрении реализации очередного слова в строке. После того, как подходящий вид ритмического слова определен, осуществляется поразрядное слева направо отображение в оперативную память каждого из его значений. Далее будет формализован процесс предварительного подбора "оптимального" вида очередного ритмического слова.

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

W=(S[k[i]],S[k[i]+1],…,S[k[i]+w[i]-1])

задано с точностью до некоторого набора из r параметров

θ =(θ [1],θ [2],…,θ [r]),

принадлежащих некоторому ограниченному и замкнутому множеству Θ. Параметрами ритмического слова могут быть позиция (номер разряда в оперативной памяти) и относительная характеристика начального значения его первого слога; относительная длина (в разрядах) каждого из слогов; относительная разность между максимальным и минимальным значениями в пределах одного слога; относительная величина конечного значения слога; отношение длин участков подъема и спуска при представлении каждого из слогов слова в сравнении с другими и т.п.

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

Обозначим M(θ) значения всех разрядов того участка верхнего слоя оперативной памяти, где было реализовано ритмическое слово W(θ ) с набором параметров θ. Для характеристики качества выбора слова W(θ ) при заданном начальном представлении W можно ввести целевую функцию

f(θ)=Σ (W(θ )[j]-W[j])^2+(M(θ )[j]-M1[k[i]+j-1])^2,

где суммирование Σ выполняется по всем индексам j=1,2,…,w[i]-1 и набор чисел M1 представляет значения соответствующего участка верхнего слоя оперативной памяти перед началом процесса реализации слова[2] W(θ ).

Для нахождения оптимального набора параметров θ можно просто постараться перебрать все возможные значения из заданного множества Θ. Но при исследовании крупных текстов этот способ практически не применим из-за большой размерности вектора настраиваемых параметров. Воспользоваться при оптимизации классическими математическими методами также не представляется возможным, так как зависимость значений функции потерь от параметра θ не задана аналитически. В такой ситуации можно попытаться воспользоваться алгоритмом стохастической аппроксимации с пробным одновременным возмущением на входе [1,3], который позволяет при минимальном количестве измерений функции f(θ) (попыток предварительной реализации ритмического слова) сгенерировать последовательность оценок {θ (n)}, n=1,2,…, сходящуюся во многих практических случаях к оптимальному значению θ. Представляется обоснованным тот факт, что в практическом отношении применение этого алгоритма при автоматизированном анализе ритмики стиха позволит существенно сократить объем необходимой работы и время ее выполнения, а также упростит способы ее осуществления. В теоретическом отношении опыт применения этого алгоритма может быть полезен при изучении принципов анализа ритмического текста и, возможно, более общих принципов восприятия семиотической информации человеком. В реальном восприятии также можно предположить существование предварительного подбора, который основан не на точном переборе всех возможностей, а на прикидке по ограниченной совокупности признаков с учетом в том или ином приближении предыдущего опыта. Кажется оправданной также и сама идея минимизации как идея приближения к текущему ритмическому тексту и контексту.

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

Алгоритм стохастической аппроксимации с возмущением на входе. Многие последовательные (итеративные) алгоритмы минимизации какой-либо целевой функции f(θ) можно записать в виде

θ(n)= θ(n-1)-α(n)g(θ(n-1)),

где {θ(n)} — последовательность оценок неизвестного вектора, минимизирующего функцию f(θ); {α(n)} — заданная числовая последовательность; g(θ) — оценка градиента g(θ)=f’(θ) целевой функции f(θ), вычисляющаяся по предыдущим наблюдениям значений функции f(θ) (может быть и не точным). В классическом алгоритме процедуры стохастической аппроксимации Кифера-Вольфовица оценка градиента строится как конечно-разностная аппроксимация. Если размерность вектора оцениваемых параметров θ равна r, то для аппроксимации каждой из r компонент вектора-градиента берется два измерения. При этом общее количество измерений на каждой итерации равно 2r, что при большой размерности вектора оцениваемых параметров требует привлечения значительных вычислительных ресурсов. Основная особенность рассматриваемого ниже алгоритма стохастической аппроксимации с возмущением на входе состоит в том, что вне зависимости от размерности вектора оцениваемых параметров неизвестная минимизируемая целевая функция f(θ) на каждой итерации измеряется только в двух точках, соответствующих позиции предыдущей оценки, возбужденной по всем координатам.

Пусть в каждый момент времени n мы можем задать вектор Δ(n) — пробного возмущения, составленный из минус и плюс единиц, выбираемых с одинаковой вероятностью. Рассмотрим алгоритм оптимизации, в котором оценка градиента функции f(θ) вычисляется по формуле

g(θ(n-1))= Δ(n)(Y(θ(n-1)+β(n)Δ(n))- Y(θ(n-1)-β(n)Δ(n)))/(2 β(n))

где {β(n)} — заданная числовая последовательность, а {Y(θ)} — измеренное в точке θ значение. Дж.Спал в работе [3] показал, что несмотря на существенное сокращение затрат на вычисление оценки градиента общее количество итераций для минимизации неизвестной функции, измеряемой с ошибками (помехами), не увеличивается по сравнению со стандартными конечно-разностными алгоритмами. Кроме того, в [1] обосновывается разумность применения этого алгоритма в тех ситуациях, когда нельзя достаточно точно описать неизвестную минимизируемую функцию потерь f(θ), а измерению доступны только опосредованно связанные с ней значения вместе с некоторой систематической погрешностью.

Следующее пошаговое резюме показывает, как последовательно по итерациям формировать оценки {θ(n)}.

Шаг 1: Инициализация и выбор коэффициентов.

Установите счетчик алгоритма n = 1. Выберите начальное приближение θ(0) и значения для неотрицательных коэффициентов α, β, γ, μ и ν. В алгоритме используются последовательности α(n) = α / (γ +n)^μ и β(n) = β /n^ ν. Выбор последовательностей {α(n)} и {β(n)} играет критическую роль в работе алгоритма. В ситуации, когда компоненты вектора θ существенно отличаются по величине, желательно использовать матричное масштабирование α(n), если предварительно доступна информация об их относительных величинах.

Шаг 2: Генерация вектора пробного возмущения.

Сгенерируйте r-мерный случайный вектор возмущения Δ(n), в котором все r компонент независимо смоделированы по вероятностному распределению Бернулли (равны минус или плюс единице в равной вероятностью).

Шаг 3: Измерение значений функции.

Получите два измерения Y1(n) и Y2(n) функции f(θ), в "возмущенных" относительно текущей оценки θ(n-1) точках θ(n-1)+β(n)Δ(n) и θ(n-1)-β(n)Δ(n) с β(n) и Δ(n), сформированными на шагах 1 и 2 соответственно.

Шаг 4: Аппроксимация градиента.

Сгенерируйте вектор аппроксимации градиента по правилу

g(θ(n-1))= Δ(n)( Y1(n)-Y2(n))/(2 β(n)).

Шаг 5: Обновление оценки θ.

Используйте стандартную форму алгоритма стохастической аппроксимации

θ(n)= θ(n-1)-α(n)g(θ(n-1))

для перехода от θ(n-1) к новому значению θ(n).

Шаг 6: Итерация или завершение.

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

Литература

1. Граничин О.Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика, 2002, № 2 (в печати).
2. Красноперова М.А.Основы реконструктивного моделирования стихосложения.-Изд-во С.-Петерб. университета, 2000. 237с.

3. Spall J.C. Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation // IEEE Trans. on Automat. Control, 1992, vol.37, pp.332-341.

[1] Более подробноое описание механизма рецепции , лежащих в его основе идей и принципов функционирования см. в работе [2]

[2] Начало процесса реализации ритмического слова будем соотносить с тем моментом, с которого начинается поразрядное сравнение его значений со значениями отмеченного для него участка оперативной памяти.