Содержание к диссертации
Введение
1 СУЩЕСТВУЮЩИЕ МЕТОДЫ СИНТЕЗА НС 10
1.1 Обучение НС 10
1.1.1 Формулировка задачи 10
1.1.2 Обратное распространение ошибки 11
1.1.3 Эволюционные алгоритмы и алгоритмы случайного поиска 12
1.1.4 Гибридные методы 15
1.1.5 Сравнение методов обучения НС 15
1.2 Выбор архитектуры НС 16
1.2.1 Формулировка задачи 16
1.2.2 Классификация методов выбора архитектуры НС 16
1.2.3 Статистический подход 16
1.2.4 Конструктивные методы 18
1.2.5 Методы сокращения 21
1.2.6 Эволюционные алгоритмы и алгоритмы случайного поиска 23
1.2.7 Сравнение методов выбора архитектуры НС 26
1.3 Выводы 27
2 ВЫБОР КЛАССА НС 29
2.1 Задача выбора класса НС 29
2.2 Основания для построения класса КНС 30
2.3 Формальная модель КНС 32
2.4 Свойства КНС 35
2.5 Эффективность КНС в задачах аппроксимации непрерывных функций 42
3 ПОСТАНОВКА ЗАДАЧИ СИНТЕЗА КНС 43
3.1 Задача синтеза КНС 43
3.2 Анализ задачи 44
4 РЕШЕНИЕ ЗАДАЧИ СИНТЕЗА КНС 47
4.1 Декомпозиция задачи 47
4.2 Выбор архитектуры КНС 48
4.2.1 Алгоритм имитации отжига 48
4.2.2 Настройка алгоритма 50
4.3 Обучение КНС 54
4.3.1 Подход к решению задачи 54
4.3.2 Вычисление частных производных 54
4.3.3 Алгоритм Левенберга-Марквардта 57
4.4 Экспериментальное исследование алгоритма синтеза КНС 59
5 ПОВЫШЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ЭФФЕКТИВНОСТИ 65
5.1 Метод повышения вычислительной эффективности 65
5.2 Метрика в пространстве архитектур КНС 66
5.3 Оценка расстояния между архитектурами КНС 71
5.3.1 Постановка задачи 71
5.3.2 Редукция задачи 72
5.3.3 Алгоритм вычисления расстояния 76
5.3.4 Алгоритм сопоставления внутренних нейронов 77
5.3.5 Критерий выбора сопоставляемых нейронов 78
5.3.6 Настройка параметров 82
5.3.7 Сложность и оптимальная организация вычислений 84
5.3.8 Экспериментальное исследование алгоритма вычисления расстояния 87
5.3.9 Оценка пригодности алгоритма вычисления расстояния 89
5.4 Оценка аппроксимационной способности (АС) КНС 89
5.4.1 Постановка задачи 89
5.4.2 Модель зависимости АС схожих архитектур КНС 90
5.4.3 Решение задачи 91
5.4.4 Алгоритм оценки АС 93
5.4.5 Сложность алгоритма оценки АС 94
5.4.6 Экспериментальное исследование алгоритма оценки АС 94
5.5 Модификация алгоритма синтеза КНС 96
5.5.1 Структура алгоритма 96
5.5.2 Анализ свойств модифицированного алгоритма 99
5.5.3 Экспериментальное исследование модифицированного алгоритма 100
5.6 Выводы 101
ЗАКЛЮЧЕНИЕ 103
ЛИТЕРАТУРА
- Обучение НС
- Задача выбора класса НС
- Задача синтеза КНС
- Декомпозиция задачи
- Метод повышения вычислительной эффективности
Введение к работе
1 Задача синтеза НС под заданное приложение
Данная работа посвящена разработке метода решения задачи синтеза нейронной сети (НС) под заданное приложение. Суть задачи состоит в построении НС, предназначенной для решения определенной прикладной задачи, ставящейся в рамках заданного приложения; при этом требуется, чтобы синтезированная НС обеспечивала решение поставленной прикладной задачи с заданной эффективностью. Критерий оценки эффективности, с которой НС решает поставленную задачу, в общем случае определяется приложением, и может зависеть от таких характеристик, как, например, точность решения, сложность строения НС или степень пригодности НС для реализации на конкретной аппаратуре.
В задаче синтеза НС под заданное приложение требуется определить: архитектуру НС, которая задается: а) количеством и типами нейронов, из которых построена сеть, и б) топологией сети (т.е. структурой связей, соединяющих нейроны); значения весовых коэффициентов, приписываемых нейронам и связям, соединяющим нейроны; алгоритм функционирования НС, задающий правило, в соответствии с которым входному сигналу сети ставится в соответствие выходной сигнал.
В данной работе рассматриваются приложения, в которых возникает задача аппроксимации непрерывных функциональных зависимостей, и исследуются вопросы, связанные с применением для решения этой задачи НС прямого распространения [125]. Предполагается, что задача аппроксимации задается следующим образом: задан конечный набор пар вида "аргумент-значение" (выборка), представляющий собой измерения неизвестной функции F в некоторых точках области ее определения; априорно предполагается, что функция F непрерывна; требуется восстановить функцию J7 на всей области ее определения.
В такой постановке задача синтеза НС под заданное приложение сводится к задаче построения с помощью НС аппроксимации таблично заданной функции. Эффективность, с которой НС решает поставленную задачу аппроксимации, оценивается по двум критериям: точность аппроксимации должна быть максимальна; сложность самой НС должна быть минимальна.
Точность аппроксимации, обеспечиваемой НС, оценивается величиной среднеквадратической ошибки аппроксимации, вычисляемой по заданной выборке из аппроксимируемой функции F. Допускается использование различных схем кросс-проверки [54,99,119], подразумевающих подразделение заданной выборки на обучающую и проверочную выборки. Сложность НС является характеристикой архитектуры НС, и может измеряться количеством нейронов, из которых построена сеть, количеством настраиваемых весовых коэффициентов, или количеством элементарных математических операций, необходимых для вычисления выходного сигнала сети. Следует отметить, что приведенные выше критерии эффективности являются противоречивыми и не позволяют однозначно определить оптимальную НС: как правило, при увеличении сложности НС максимально достижимая для такой НС точность аппроксимации также увеличивается (и наоборот). Поэтому предполагается, что постановка задачи синтеза НС под заданное приложение содержит некоторые дополнительные условия, которые позволяют разрешить указанное противоречие. Рассматриваются варианты, когда заданы: максимально допустимая сложность НС - тогда оптимальной является НС, обеспечивающая наибольшую точность аппроксимации при соблюдении ограничения на сложность; требуемая точность аппроксимации - тогда оптимальной является НС минимальной сложности, обеспечивающая при этом заданную точность; относительные приоритеты обоих критериев эффективности - тогда имеется возможность сформировать единый непротиворечивый критерий оптимальности НС, учитывающий и точность аппроксимации, и сложность самой НС.
2 Актуальность темы
Традиционный подход к решению задачи синтеза НС под заданное приложение заключается в том, что исходная задача синтеза разбивается на несколько более простых подзадач, и решается в несколько этапов;
Выбирается класс, в котором будет производиться поиск оптимальной НС. Класс НС определяет алгоритм функционирования НС и правила, которым должна соответствовать архитектура НС. Эти правила ограничивают допустимую топологию сети и типы нейронов, которые разрешается использовать при построении сети.
В рамках выбранного класса НС строится архитектура НС. На этом этапе точно определяются количество нейронов в сети, тип каждого из них, а также наличие или отсутствие связи между каждой парой нейронов.
Производится обучение НС, архитектура которой была определена на предыдущем этапе. В процессе обучения определяются значения весовых коэффициентов сети,
Соответственно, возникают задачи:
Задача выбора класса НС, в которой требуется выбрать (или построить) класс НС, наиболее подходящий для заданного приложения. Под наиболее подходящим (оптимальным) классом НС здесь понимается такой класс, в котором возможно построить НС, способную обеспечить наиболее эффективное решение прикладной задачи (в рассматриваемом случае это задача аппроксимации таблично заданной функции).
Задача выбора архитектуры НС, в которой требуется в заданном классе НС выбрать оптимальную архитектуру. Под оптимальной здесь понимается архитектура, такая, что обученная НС с этой архитектурой решает поставленню задачу с наибольшей эффективностью среди всех НС выбранного класса.
Задача обучения НС, в которой требуется подобрать значения весовых коэффициентов НС с заданной архитектурой таким образом, чтобы максимально повысить эффективность, с которой НС решает поставленную задачу.
Для многих классов НС разработаны, хорошо изучены и с успехом применяются на практике различные алгоритмы обучения НС, такие, как алгоритм обратного распространения ошибки [88]. Наиболее сложными для решения являются задачи выбора класса и архитектуры НС. Для многих прикладных задач, решаемых с помощью НС, неизвестны формальные методы, позволяющие с достаточной точностью, и без проведения трудоемких экспериментальных исследований, оценить, насколько эффективное решение поставленной прикладной задачи может быть получено в заданном классе НС. Также неизвестны методы, позволяющие оценить, оптимальность заданной архитектуры НС, не решая при этом задачу обучения НС с такой архитектурой. Это приводит к необходимости использования для выбора оптимальной архитектуры НС вычислительно неэффективных методов переборного типа. Высокая вычислительная сложность переборных методов обусловлена, прежде всего, необходимостью многократного решения задачи обучения НС в процессе поиска оптимальной архитектуры.
Отсутствие вычислительно эффективных методов для точного решения задач выбора класса и архитектуры НС обуславливает использование для решения этих задач различных эмпирических методов. Например, на первом этапе выбирается один из "стандартных" классов НС, традиционно использующихся для решения прикладных задач того же рода, что ставится в заданном приложении. Примерами таких классов НС являются многослойные сети прямого распространения [125], сети функций радиального базиса [103], сети встречного распространения [43]. на втором этапе эмпирически [9,12], или на основании грубзых статистических оценок [5,6,108], выбирается размер НС. Если выбранный на предыдущем этапе класс НС таков, что размер НС однозначно не определяет ее архитектуру, то для доопределения архитектуры используются различные эвристические правила.
Для многих приложений такие методы позволяют быстро синтезировать НС, обеспечивающую приемлемую эффективность решения прикладной задачи, ставящейся в рамках приложения.
Однако существуют и приложения, отличительной чертой которых является наличие весьма жестких и принципиальных требований к эффективности решения, обеспечиваемого НС. Будем называть такие приложения "сложными" (здесь подразумевается в виду сложность решения задачи синтеза НС под такие приложения). В качестве примера "сложного" приложения можно привести приложение, в рамках которого ставится задача синтеза НС, предназначенной для решения узкоспециализированной прикладной задачи в условиях аппаратной реализации и функционирования в режиме реального времени. Для "сложных" приложений вероятность того, что использование эмпирических методов для выбора класса и архитектуры НС позволит получить приемлемый результат, может быть весьма малой. Поэтому возникает необходимость: для выбора класса НС - проводить тщательный теоретический и экспериментальный анализ прикладной задачи, решаемой с помощью НС. Целью такого анализа является определить, нейроструктуры какого класса наилучшим образом подходят для решения поставленной прикладной задачи. На этом этапе может возникать необходимость в построении нового, специфичного для решаемой задачи, класса НС, и в разработке алгоритмов обучения для НС такого "нестандартного" класса. для выбора архитектуры НС - использовать переборные методы, основанные на многократном повторении второго и третьего этапов синтеза НС (т.е. выбор архитектуры и обучение). Схема этих методов такова: выбирается начальная архитектура, НС обучается и оценивается эффективность, с которой обученная НС решает поставленную задачу; если полученный результат неудовлетворителен, то архитектура корректируется, и весь процесс повторяется снова, пока не будет достигнута заданная эффективность решения.
При таком подходе возникает ряд проблем, связанных с высокой трудоемкостью решения задачи синтеза НС. Процесс выбора класса НС не может быть полностью автоматизирован и может требовать значительных трудозатрат как со стороны экспертов в предметной области, так и со стороны специалистов в области использования НС. Переборный характер методов, используемых для выбора архитектуры, обуславливает их низкую вычислительную эффективность: на каждой итерации приходится решать задачу обучения НС, вычислительная сложность которой может быть весьма высокой, Кроме того, при использовании переборных методов для выбора архитектуры НС в заданном классе НС часто проявляется особенность, которая приводит к так называемой проблеме эквивалентных представлений (в оригинале - Permutation Problem или Competing Conventions Problem) [36,38,85,114,130]. Суть этой проблемы заключается в возможности существования, в рамках выбранного способа представления архитектуры НС, различных представлений одной и той же архитектуры НС. Например, два представления одной и той же архитектуры НС могут различаться порядком нумерации нейронов. Такие представления далее будут именоваться эквивалентными. Существование эквивалентных представлений архитектуры НС значительно увеличивает размер пространства, в котором производится поиск архитектуры НС, и, тем самым, снижает вычислительную эффективность переборных методов, осуществляющих поиск в этом пространстве.
Таким образом, можно выделить две наиболее существенные проблемы, возникающие при решении задачи синтеза НС для "сложных" приложений, в которых наивысший приоритет имеет эффективность решения поставленной задачи с помощью синтезируемой НС: трудоемкость и неформализуемость методов решения задачи выбора класса НС; низкая вычислительная эффективность существующих методов для решения задачи выбора архитектуры НС,
В работе будет показано, что эти проблемы актуальны и в рассматриваемом частном случае, когда НС применяется для построения аппроксимации непрерывной функции.
3 Цель работы
Целью данной работы является разработка метода, позволяющего автоматизировать и ускорить процесс решения задачи синтеза НС под заданное приложение. Рассматривается класс "сложных" приложений, в которых возникает задача аппроксимации таблично заданной функции. В рамках данной работы ставятся следующие задачи: предложить способ решения задачи синтеза НС под заданное приложение, не требующий применения неформализуемых эмпирических методов для выбора класса НС; разработать алгоритмы, позволяющие снизить вычислительную сложность решения задачи выбора архитектуры НС.
4 Методы решения
В данной работе предлагается метод решения задачи синтеза НС под заданное приложение, имеющий следующие особенности: задача выбора класса НС не решается заново для разных приложений, а вместо этого используется достаточно широкий, "универсальный" класс НС, и синтез искомой НС осуществляется в таком классе. Предлагаемый "универсальный" класс НС обладает тем свойством, что в нем с достаточно высокой вероятностью содержатся НС, обеспечивающие эффективное решение для широкого круга прикладных задач аппроксимации; при решении задачи выбора архитектуры НС используются алгоритмы, позволяющие минимизировать количество проводимых сессий обучения НС.
При построении метода синтеза НС под заданное приложение использовались недетерминированные поисковые методы, методы нелинейной локальной оптимизации, а также методы регрессионного анализа.
Использование предлагаемого метода позволяет достичь поставленных целей: отсутствие необходимости решения задачи выбора класса НС индивидуально для каждого нового приложения позволяет избежать применения неформализуемых эмпирических методов, и, тем самым, достичь полной автоматизации всего процесса решения задачи синтеза НС под заданное приложение; минимизация количества проводимых сессий обучения НС позволяет повысить вычислительную эффективность решения задачи выбора архитектуры НС, и, тем самым, существенно ускорить весь процесс решения задачи синтеза НС под заданное приложение.
Реализация предлагаемого метода содержит следующие компоненты:
В качестве "универсального" класса НС, который, как предполагается, хорошо подходит для многих приложений, вводится класс так называемых комбинированных нейронных сетей (КНС). КНС относятся к НС прямого распространения. Отличительной особенностью сетей из класса КНС является то, что топология сети не обязательно является регулярной, как в большинстве известных из литературы [119,125] классов НС, и может задаваться связным ациклическим графом достаточно произвольного вида. Также в КНС допускается использование, в пределах одной сети, различных (в том числе нетрадиционных для НС) типов нейронов. Предположение об эффективности использования КНС для решения задач аппроксимации непрерывных функций подтверждается результатами экспериментального исследования.
Предлагается алгоритм, позволяющий строить в классе КНС решения задачи синтеза НС под заданное приложение. Разработанный алгоритм синтеза КНС использует алгоритм имитации отжига [49,56] для выбора архитектуры КНС и алгоритм Левенберга-Марквардта [62,69,78] для обучения КНС.
Предлагается метод, позволяющий повысить вычислительную эффективность предложенного алгоритма синтеза КНС. Ускорение достигается за счет сокращения количества сессий обучения КНС, которые необходимо проводить в процессе работы предложенного алгоритма синтеза КНС. Разработанные в рамках предлагаемого метода алгоритмы позволяют: а) заменять, при выполнении определенных условий, проведение сессии обучения КНС значительно более быстрой процедурой вычисления приближенной оценки точности аппроксимации, которая достижима для обученной КНС с заданной архитектурой; б) избегать повторного обучения КНС с эквивалентными архитектурами. Этим достигается снижение негативного влияния проблемы эквивалентных представлений.
5 Структура работы
Обучение НС
Задача обучения НС состоит в отыскании набора весовых коэффициентов НС (весов), максимизирующих некоторую заданную меру эффективности, с которой НС решает поставленную прикладную задачу. В задаче обучения считается, что архитектура НС является заданной.
В данной работе предполагается, что НС используется для построения аппроксимации некоторой непрерывной функции F, заданной выборкой S, и рассматриваются два критерия эффективности решения задачи аппроксимации с помощью НС:
точность аппроксимации должна быть максимальна;
сложность самой НС должна быть минимальна.
Так как сложность НС является характеристикой архитектуры НС, и не зависит от ее весовых коэффициентов, то в задаче обучения НС в качестве меры эффективности решения задачи аппроксимации может рассматриваться только точность аппроксимации. Точность аппроксимации оценивается с помощью функции ошибки сети, которая может быть выбрана достаточно произвольно. Весьма часто в качестве функции ошибки сети используется среднеквадратическая оценка ошибки аппроксимации MSE (Mean Square -11 Error), которая задается формулой MSE(NET,S) = JlFNET(xi)-yi\\ , где Р 1=1 S - {(x y jj = \Г2,...,Р - набор измерений аппроксимируемой функции F (обучающая выборка), FNeT (х) - реализуемая сетью NET функция. При таком выборе функции ошибки сети задача обучения НС принимает следующий вид:
MSE(NET,S) mm, и может рассматриваться как задача множественной нелинейной регрессии, в которой искомыми параметрами являются веса сети NET. При этом искомые веса, минимизирующие функцию MSE, являются оценками максимального правдоподобия, максимизирующими функцию правдоподобия L выборки S [123]. В широких предположениях оценки максимального правдоподобия являются оптимальными [51]. Следует отметить, что иногда в задаче обучения НС рассматриваются функции ошибки сети, отличные от MSE: например, к MSE может добавляться дополнительный регуляризующий терм [123]. Однако в случае использования модифицированной функции ошибки сети, как правило, не требуется разработка принципиально новых алгоритмов обучения НС, и поэтому в предлагаемом обзоре таким случаям не будет уделяться отдельного внимания.
Задача выбора класса НС
Во введении была сформулирована задача выбора класса НС, возникающая в процессе синтеза НС под заданное приложение. Эта задача состоит в выборе (или построении) класса НС, наилучшим образом подходящего для приложения, т.е. такого класса, в котором можно построить НС, способную обеспечить наиболее эффективное решение поставленной прикладной задачи. Рассмотрим специфику задачи выбора класса НС применительно к рассматриваемому в данной работе частному случаю задачи синтеза НС под заданное приложение, когда НС применяется для построения аппроксимации непрерывной функции.
В данной работе предполагается, что эффективность, с которой некоторая НС х решает поставленную задачу аппроксимации, оценивается по двум критериям: точность аппроксимации MSE(x), обеспечиваемая НС х, и сложность С(х) самой НС х. Так как эти критерии противоречивы, в постановке задаче на основе этих двух критериев формируется некоторый единый непротиворечивый критерий H(MSE(x), С(х)). Без ограничения общности будем предполагать, что малые значения критерия Н соответствуют высокой эффективности решения прикладной задачи с помощью НС х. Тогда задача выбора класса НС приобретает следующий вид: найти класс НС X , для которого значение Q(X ) = minH(MSE(x\C(x)) минимально. Для решения этой задачи необходимо:
1) определить некоторый набор {X} классов НС, в который включаются классы, потенциально хорошо подходящие для заданного приложения (т.е. такие классы X, для которых имеются какие-либо основания рассчитывать на малые значения Q{X));
2) из набора {X} выбрать оптимальный класс X є {X} : X - arg min Q(X ) . В набор {X} могут включаться: - "стандартные" классы НС, для которых известно, что НС из этих классов хорошо подходят для задач аппроксимации непрерывных функций. Примерами таких классов являются многослойные сети прямого распространения [125], сети функций радиального базиса [103];
классы НС, построенные специально под конкретную решаемую задачу. В ряде случаев может оказаться возможным, используя некоторые априорные знания о структуре аппроксимируемой функции F, подобрать с некоторой степенью определенности типы нейронов и схему их соединения таким образом, чтобы функции, реализуемые НС, были в какой-то мере близки по структуре к функции F. Если удается определить класс, состоящий из таких НС, то можно надеяться на то, что для такого класса будет высока вероятность существования в нем НС, обеспечивающей эффективное решение поставленной задачи аппроксимации.
Следует отметить, что для "сложных" приложений, в которых выдвигаются жесткие требования к эффективности, с которой НС решает задачу аппроксимации, может возникнуть ситуация, когда ни один из "стандартных" классов НС не подходит для решения поставленной задачи аппроксимации. В такой ситуации возникает необходимость в построении одного или нескольких классов НС специально под решаемую задачу. При этом, если имеющихся знаний о структуре аппроксимируемой функции F недостаточно для построения таких классов, возникает необходимость в проведении дополнительных теоретических и экспериментальных исследований свойств задачи аппроксимации, решаемой с помощью НС.
Задача выбора, из набора {X}, оптимального класса X є {X} является весьма сложной. На настоящий момент неизвестны вычислительно эффективные формальные методы, которые позволяют оценить значение Q(X) для достаточно произвольных приложения, классаД и критерия Н. Для решения задачи выбора оптимального класса X может потребоваться как разработка методов, специфичных для данной конкретной задачи, так и проведение дополнительных вычислительных экспериментов.
Таким образом, можно сделать следующий вывод: для рассматриваемого в данной работе частного случая задачи синтеза НС под заданное приложение, когда НС применяется для построения аппроксимации непрерьгеной функции, задача выбора класса НС является весьма сложной. Основной проблемой, возникающей при решении задачи выбора класса НС, является необходимость разработки и применения методов, специфичных для заданного приложения, что затрудняет построение универсальных методов для решения рассматриваемой задачи, и не позволяет полностью автоматизировать процесс выбора оптимального класса НС.
Задача синтеза КНС
В рамках исследуемого в данной работе частного случая задачи синтеза НС под заданное приложение, когда НС применяется для построения аппроксимации таблично заданной непрерывной функции, рассматриваются следующие критерии эффективности, с которой НС решает задачу аппроксимации:
1) точность аппроксимации, которая обеспечивается НС;
2) сложность самой НС.
При решении задачи синтеза НС в классе КНС приведенные выше критерии оцениваются следующим образом. Точность аппроксимации, обеспечиваемая КНС NET = (G,T,W), измеряется величиной среднеквадратической ошибки аппроксимации MSE(NET,S), вычисляемой по заданной выборке S из аппроксимируемой функции. Сложность КНС измеряется количеством C{G,T) элементарных математических операций, необходимых для вычисления выходного сигнала сети.
Как было уже отмечено во введении, указанные критерии эффективности являются противоречивыми (улучшение решения по одному из этих критериев, как правило, ведет к ухудшению решения по другому критерию). Для разрешения этого противоречия предполагается, что определен некоторый интегральный критерий эффективности Н, зависящий от MSE и С, причем критерий Н может быть представлен в следующем виде: Н = U{MSE) + V(C), Здесь U, V - некоторые весовые функции, задающие относительные приоритеты критериев MSE, С. Предполагается, что конкретный вид весовых функций U.V определяется на этапе постановки задачи, исходя из требований приложения. В простейшем случае U,V- линейные функции: U(MSE) = a MSE V(C) = b C Здесь: a,b 0,a+b-l - относительные приоритеты критериев.
Также учитывается возможность директивных ограничений на максимально допустимые значения MSE и С (независимо от приоритетов U, V). Эти ограничения могут быть обусловлены спецификой прикладной задачи. Например, в системе реального времени может требоваться, чтобы на заданной аппаратуре время вычисления выходного сигнала сети не превосходило заданной величины; такое требование трансформируется в ограничение на максимально допустимую сложность сети С.
Учитывая вышесказанное, можно строго сформулировать задачу синтеза КНС.
Пусть заданы: корректная выборка S = {(x yjjj -1,2,..., Р;
максимально допустимая среднеквадратическая ошибка аппроксимации MSE (неотрицательное действительное число);
максимально допустимая сложность КНС Спнх (положительное целое число);
неубывающие, неотрицательные, непрерывные и дифференцируемые весовые функции U, V.
Требуется: построить такую КНС NET - (G, Т, W), для которой:
значение целевой функции U(MSE(NET,S)) + V(C(G,T)) минимально, при этом
среднеквадратическая ошибка аппроксимации MSE(NET,S) сети NET на выборке S не превосходит некоторого значения MSEnii 0;
сложность C(G,T) архитектуры сети NET ограничена максимально допустимым значением Ctnax 0;
Примечание: допускается постановка задачи, в которой одно или оба ограничения на максимальные значения MSE(NET,S) и C(G,T) отсутствуют. Кроме того, любая из функций U, V может быть тождественно равна нулю.
Декомпозиция задачи
Как было отмечено в предыдущем разделе, задачу (3.1) синтеза КНС может быть отнесена к задачам смешанной комбинаторно-непрерывной оптимизации с ограничениями. В настоящее время неизвестны эффективные методы для решения задач такого рода, особенно для случая, если количество оптимизируемых параметров достаточно велико. Однако в задаче синтеза КНС оказывается возможным разделить фазы решения задач комбинаторной и непрерывной оптимизации, что позволяет применять специализированные методы для решения каждой из возникающих подзадач. Действительно, запишем задачу (3.1) в виде задачи математического программирования: min U(MSE(G, Т, W, S)) + F(C(G, Т)) IG.T.W) (4.1) MSE(G,T,W,S) MSEm C(G,T) C№
Рассмотрим произвольную тройку {G,T,W), принадлежащую области допустимых решений задачи (4.1). Если существует такой набор весов W, что MSE(G,T,W ,S) MSE(GiT,W,S), то из того, что функция С монотонно неубывает, следует U(MSE(G, Т, W, S» + V(C(G, 7/)) U(MSE(G, Т, W, S)) + V(C(G, Г)). Поэтому возможно, не теряя оптимальных решений задачи, исключить из области Q допустимых решений все точки (G,f,W), для которых MSE(G,f,W,S) mmMSE(G,f,W,S) (т.е. все КНС с неоптимальными весами). При этом задача (4.1) принимает вид: min U(MSE(G, Т, W, S)) + V{C(G, Т)) (G,T,W) MSE(G,TtW,S) MSE C(GJ) C MSE(G, T, fV, S) = mmMSE(G,T, W, S)
Обозначим функциональным символом MSEbest аппроксимационную способность КНС-архитектуры (G,T) на выборке S: MSEbesl(G,T,S) = minMSE(G,T,W,S). Используя символ MSEbesf, можно представить задачу (3.1) синтеза КНС в следующем виде: mmU(MSEbest(G,T,S)) + V(C(G,T)) MSE (GJ,S) MSE , (4.2)
C{G,T) C -48 где MSEbest(G, Г, S) = mmMSE(G,T, W, S).
Представление (4.2) позволяет разделить задачу синтеза КНС на две подзадачи:
главную задачу выбора архитектуры КНС, т.е. задачу нахождения такой архитектуры (G,T), которая минимизировала бы целевую функцию Н = U(MSEbest(G,T,S)) + V(C(G,T)) и удовлетворяла бы при этом ограничениям задачи (4.2);
подчиненную задачу обучения КНС с заданной архитектурой, т.е. задачу нахождения оптимальных весов W и вычисления значения MSEbesl(G,T,S) = MSE(G,T,f S).
Отметим, что в главной задаче оптимизируемый параметр (архитектура) является структурой комбинаторного типа, а подчиненная задача представляет собой задачу минимизации гладкой невыпуклой функции. Декомпозиция (4.2) позволяет, вместо решения крайне сложной смешанной задачи (4.1), раздельно решать задачи комбинаторной и непрерывной оптимизации с помощью специализированных методов, каждый из которых эффективен в своем классе задач. Поэтому в дальнейшем при решении задачи (3.1) будет использоваться декомпозиция (4.2).
Для соблюдения строгости изложения следует сделать одно замечание относительно проведенной декомпозиции задачи синтеза КНС. В общем случае нет оснований всегда рассчитывать на возможность точного достижения минимума целевой функции как в задаче синтеза КНС, так и в подзадаче обучения КНС (наличие такой возможности неявно предполагалось при проведении декомпозиции). Однако можно гарантировать, для любого є О, существование є -оптимальных решений рассматриваемых оптимизационных задач (то есть решений, значения целевой функции для которых превосходят точную нижнюю грань для этих значений менее, чем на некоторую наперед заданную величину ; 0). Очевидно, что для прикладных задач необходимость подмены точных решений є -оптимальными не является существенной проблемой, так как величину є можно выбирать сколь угодно малой. Остается вопрос о том, всегда ли возможно при использовании декомпозиции (4.2) задать некоторую точность для решения подзадачи обучения КНС так, чтобы решение всей задачи синтеза КНС гарантированно было бы є -оптимальным (для любого є 0) Это оказывается возможным, так как функция U непрерывна, и для любого є 0 и для любых (G, Т) возможно выбрать такое S(,GiT) 0 чтобы отклонение найденного значения MSEbes!(G,T,S) от точной нижней грани inf MSE(G, Т, W, S) не более чем на 8 приводило бы к увеличению I) (MSEbesl(G,T\S)) не более чем на є.
Далее в данной главе будут отдельно рассмотрены методы для решения задач выбора архитектуры КНС и обучения КНС.
Метод повышения вычислительной эффективности
Основным недостатком предложенного алгоритма синтеза КНС является его высокая вычислительная сложность, что обусловсно необходимостью решения задачи обучения КНС на каждой итерации алгоритма. Целью обучения КНС является вычисление значения MSEbest{G,T,S) = mmMSE(G,T,WiS), которое, в свою очередь, используется для вычисления целевой функции Я задачи синтеза КНС (4.2). Несмотря на то, что для решения задачи обучения КНС используется достаточно эффективный, по сравнению с другими методами, алгоритм Левенберга-Марквардта, вычислительная сложность алгоритма синтеза КНС все же может быть весьма высока. Кроме того, для алгоритма синтеза КНС актуальна проблема эквивалентных представлений: достаточно высока вероятность возникновения ситуации, когда на некоторой итерации алгоритма синтеза генерируется архитектура КНС, функционально эквивалентная некоторой другой архитектуре, уже рассмотренной на предыдущих итерациях алгоритма. Если такая ситуация возникает, то фактически одну и ту же КНС приходится обучать многократно, что приводит к бесполезной трате вычислительных ресурсов и к еще большему снижению эффективности работы алгоритма синтеза КНС.
Одним из возможных методов повышения вычислительной эффективности алгоритма синтеза КНС является разработка и использование такого алгоритма обучения КНС, который всегда обеспечивал бы получение решений не худших, чем алгоритм Левенберга-Марквардта, и при этом обладал бы существенно меньшей вычислительной сложностью. Однако на настоящий момент возможность разработки такого алгоритма обучения КНС представляется маловероятной.
В данной работе предлагается использовать другой метод повышения вычислительной эффективности алгоритма синтеза КНС. Суть предлагаемого метода не в уменьшении времени, затрачиваемого на обучение КНС, а в сокращении количества сессий обучения, проводимых за определенное число итераций алгоритма синтеза КНС. Это сокращение предполагается достигать за счет модификаций алгоритма синтеза КНС, заключающихся в следующем: в процессе работы алгоритма синтеза КНС применяется быстрый алгоритм приближенной оценки аппроксимационной способности (AC) MSEbes архитектуры КНС. Использование алгоритма оценки АС позволяет, при выполнении определенных условий, заменить им проведение сессии обучения КНС;
на каждой итерации алгоритма синтеза, непосредственно перед обучением КНС, рассматривается архитектура обучаемой КНС. Выполняется проверка, проводилось ли на предыдущих шагах алгоритма синтеза обучение КНС с архитектурой, которая функционально эквивалентна рассматриваемой. Если такая ситуация имеет место, сессия обучения КНС не проводится.
Данная глава посвящена реализации предложенного выше метода повышения вычислительной эффективности алгоритма синтеза КНС. Описываемая реализация [128,129,131,132] была построена следующим образом.
Анализ результатов ряда проведенных экспериментов позволил сформировать гипотезу о наличии зависимости между АС для сетей со схожей архитектурой. На основе этой гипотезы был построен алгоритм оценки АС. Алгоритм позволяет оценить, для заданной выборки, величину АС произвольной архитектуры А, в том случае, если известны несколько других архитектур КНС, и для каждой из этих архитектур:
известна их АС;
известна степень их схожести друг с другом и с архитектурой А.
Алгоритм оценки АС используется в алгоритме синтеза КНС вместо алгоритма обучения, если выполняются сформулированные выше условия его применимости. В противном случае производится обучение КНС, Так как алгоритм оценки АС обладает существенно меньшей вычислительной сложностью, чем алгоритм обучения, его использование вместо алгоритма обучения КНС позволяет повысить вычислительную эффективность алгоритма синтеза КНС.
Необходимым условием для возможности применения алгоритма оценки АС является наличие критерия, позволяющего оценить схожесть двух архитектур КНС. В данной работе в качестве такого критерия предлагается специальным образом построенная метрика в пространстве архитектур КНС. Расстояние D между двумя архитектурами КНС определяется как длина минимальной последовательности элементарных операций модификации архитектуры КНС, переводящей одну из этих архитектур в другую, причем архитектуры рассматриваются равными с точностью до перенумерации внутренних нейронов. Будет показано, что введенная таким образом метрика обладает следующими свойствами:
расстояние между "похожими" (в интуитивном смысле) архитектурами КНС мало;
если расстояние между двумя архитектурами равно нулю, то они являются функционально эквивалентными (по следствию из утверждения 5), и их АС совпадают;
В данной главе также предлагается быстрый эвристический алгоритм вычисления расстояния D. Применение этого алгоритма позволяет, без существенных вычислительных затрат, решать следующие задачи:
проверять, на каждой итерации алгоритма синтеза КНС, возможность применения алгоритма оценки АС вместо алгоритма обучения КНС;
определять функциональную эквивалентность архитектур КНС, генерируемых алгоритмом синтеза КНС, и, тем самым, избегать многократного обучения КНС с одной и той же архитектурой.
Похожие диссертации на Синтез нейронной сети под заданное приложение
