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

4. СОЕДИНЕНИЕ И НАСТРОЙКА ЭЛЕМЕНТОВ РАСПРЕЛДЕЛЕННЫХ СИСТЕМ СО СВОЙСТВАМИ РЕГУЛЯРИЗАЦИИ

4.1 Распределенные сети со свойствами регуляризации

Для реализации разложения регуляризованной функции аппроксимации , представленной в (2.22) в терминах функции Грина с центром в точке ,можно использовать нейросетевую структуру, показанную на рисунке 2.1 а. По очевидным причинам такие сети называются сетями регулировании (regularization network). Как и сеть, эта сеть имеет три слоя. Входной слой состоит из входных узлов, количество которых равно размерности вектора входного сигнала х (т. е. количеству независимых переменных в задаче). Второй слой является скрытым. Он состоит из нелинейных элементов, которые непосредственно связаны со всеми узлами входного слоя. Для каждой точки данных (i=1,2,…,N, где N—размер множества примеров обучения) существует свой скрытый узел. Функциями активации отдельных узлов скрытого слоя являются функции Грина. Следовательно, выходной сигнал i-го нейрона скрытого слоя определяется как x, ). Выходной слой состоит из единственного линейного нейрона, связанного со всеми узлами скрытого слоя. Под "линейностью" подразумевается то, что его выход является линейно-взвешенной суммой всех выходных сигналов скрытого слоя. Веса выходного слоя являются неизвестными коэффициентами разложения, определяемого в терминах функций Грина и параметра регуляризации На рисунке 4.1 а

Входной Скрытый слой Выходной
слой состоящий слой

из У функций

Грина

а)

Входной Скрытый слой, Выходной

слой состоящий слой

из т, радиальных

базисных функций

б)

Рисунок 4.1 - а) Сеть регуляризации; б) Сеть на основе радиальных базисных функций показана архитектура сети регуляризации с одним выходом. На рисунке видно, что такая архитектура может быть расширена для выходного сигнала любой размерности.

В сети регуляризации, показанной на рисунок 4.1 б, предполагается, что функция Грина является положительно-определенной для всех . При выполнении этого условия (например, если функция Грина имеет вид функции Гаусса (3.1)) решение, генерируемое сетью, будет являться оптимальной интерполяцией в смысле минимизации функционала E(F). Более того, сточки зрения теории аппроксимации сети регуляризации обладают следующими положительными свойствами.

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

2. Так как схема аппроксимации, вытекающая из теории регуляризации, является линейной относительно неизвестных коэффициентов, то сети регуляризации обладают свойством наилучшей аппроксимации (best-approximation property). Это значит, что для неизвестной линейной функции fвсегда существует такой набор коэффициентов, который аппроксимирует функцию fлучше любого другого набора.

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

4.2 Обобщенные сети на основе радиальных базисных функций

Однозначное соответствие между данными обучения и функциями Грина для i = 1, 2, ..., N явилось основой создания сети регуляризации, которая в вычислительном смысле при больших значениях N является очень ресурсоемкой. В частности, вычисление линейных весов сети (т. е. коэффициентов разложения в (2.22)) требует реализации операции обращения матрицы размерности вычислительная сложность которой возрастает пропорционально . Более того, для больших матриц ухудшается обусловленность, поскольку число обусловленности (condition number) матрицы определяется как отношение ее максимального собственного числа к минимальному. Для того чтобы обойти эти вычислительные трудности, необходимо уменьшить сложность сети, т. е. найти некоторую аппроксимацию регуляризированного решения.

Такой подход предполагает поиск субоптимального решения в пространстве меньшей размерности, аппроксимирующего регуляризированное решение (2.22). Для этого используется стандартный прием, получивший в вариационных задачах название метода Галеркина (Galerkin's method). Согласно этой технологии приближенное решение F*(x) находится как разложение по конечному базису, т. е.

, (4.1)

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

(т. е. ). Для радиальных базисных функций можно принять

(4.2)

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

корректное решение (2.25) будет полностью восстановлено. Таким образом, подставляя (2.25) в (2.34), можно переопределить F*(x) следующим образом:

(4.3)

Для данного разложения (4.3) функции аппроксимации F*(x) задача сводится к определению нового множества весов , которое минимизирует новый функционал стоимости E(F*), определяемый следующим образом:

(4.4)

Первое слагаемое в правой части (4.4) может быть выражено как квадратичная Евклидова норма , где

(4.5)

(4.6)

(4.7)

Вектор желаемого отклика остается, как и ранее, N-мерным. Однако размерности матрицы G функций Грина и вектора весов wизменяются. Матрица G теперь имеет размер и, таким образом, перестает быть симметричной. Вектор wимеет размерность . Из выражения (4.3) видно, что функция аппроксимации F* является линейной комбинацией функций Грина для стабилизатора D. Следовательно, второе слагаемое в правой части (4.4) можно выразить следующим образом:

(4.8)

где во-второй и в-третьей строках используется определение сопряженного оператора. Матрица G0 является симметричной матрицей размерности :

(4.9)

Таким образом, минимизация (4.4) по отношению к вектору w приводит к следующему результату:

(4.10)

Если параметр регуляризации , принимает значение, равное нулю, вектор w сходится к псевдообратному (по минимальной норме) решению сверхопределенной (over determined) задачи подбора кривой на основе метода наименьших квадратов (least-squares data-fittingproblem) для :

(4.11)

где - матрица, псевдо обратная матрице G, т. е.

(4.12)

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

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

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

(4.13)

(4.14)

(4.15)

Функционал переходит в квадратичную функцию . Таким образом, приходим к следующей задаче: построить минимизирующую последовательность для функционала Ф(z) на одном из множеств (4.

Пусть Y — одно из множеств или . Заметим, что любое ограничение (4.13) — (4.15) может быть записано в виде

(4.16)

где F — матрица размера — количество условий, определяющих множество, g — вектор ограничений длины . Неравенство понимается в смысле покомпонентных неравенств.

Если z находится на границе множества, то одно или несколько неравенств в (4.16) могут обращаться в равенства. Множеством активных ограничений I(z) (в точке z) будем называть множество индексов (быть может, не всех), для которых в точке z выполнены равенства

Через dimI будем обозначать число элементов в множестве I. Назовем матрицей активных элементов матрицу размера, строками которой являются строки матрицы F, номера которых принадлежат .

Квадратичную функцию представим в виде:

(4.17)

4.3 Алгоритм и взаимодействие элементов архитектуры распределенных систем с целью повышения свойств регуляризации

Метод проекции сопряженных градиентов для минимизации функции (4.17) при ограничениях (12) проще всего записывается в алгоритмическом виде.

Шаг 1. Минимизация начинается с произвольной допустимой точки и проводится в методом сопряженных градиентов. Положим число активных ограничений . Положим счетчик итераций метода проекции сопряженных градиентов без изменения матрицы активных ограничений .

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

Шаг 1.2. Вычисляется направление спуска , если , то

,

иначе

Шаг 1.3. Вычисляется — величина оптимального шага вдоль этого направления по формуле

Шаг 1.4. Вычисляется — величина максимально возможного шага вдоль этого направления , не выводящего за пределы множества Y.

Шаг 1.5. Если , то и переходим на шаг 1.1; иначе и переходим на шаг 2.

Шаг 2. Появились новые активные ограничения. Находим одно из новых активных ограничений и включаем его в множество активных ограничений . В соответствии с этим изменяем матрицу активных ограничений; m:=m+1.

Шаг 3. Вычисляем проектор на подпространство, определяемое условиями , по формуле

Шаг 4. Повторяем шаг 1, только в качестве начальной точки берется , а всюду вместо берутся их проекции Точный минимум на (n – m)-мерном линейном многообразии находится методом сопряженных градиентов за n-m-шагов. Поэтому выход из шага 4 проводится по сравнению

Если минимум на многообразии найден и , то переходим на шаг 6. Если минимум найден и , то переходим на шаг 5. Если минимум не найден (т. е. ), то переходим на шаг 2.

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

Шаг 5.1. Вычисляем набор из т теневых параметров по формуле

Шаг 5.2. Если все , то найдено решение задачи (ни одного ограничения нельзя выбросить из множества активных ограничений) . Переходим на шаг 6.

Шаг 5.3. Если для каждого i, то i-е активное ограничение исключаем из I(z) и переходим на шаг 3, положив т: =т—1.

Шаг 6. Конец.

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