Вычислительная сложность обучения

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

Пусть как всегда W - число синаптических весов сети (weights), а P - число обучающих примеров (patterns). Тогда для однократного вычисления градиента функции ошибки

$Вычислительная сложность обучения$

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

$Вычислительная сложность обучения$

. Здесь

$Вычислительная сложность обучения$

- матрица вторых производных в точке минимума

$Вычислительная сложность обучения$

. Оценив эту матрицу по локальной информации (для чего потребуется

$Вычислительная сложность обучения$

операций метода back-propagation), можно попасть из любой точки в минимум за один шаг. На этой стратегии построены методы вторго порядка (метод Ньютона). Альтернативная стратегия - найти требуемые

$Вычислительная сложность обучения$

параметров за

$Вычислительная сложность обучения$

шагов метода первого порядка, затратив на каждом шаге

$Вычислительная сложность обучения$

операций. Именно такую скорость сходимости (

$Вычислительная сложность обучения$

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

$Вычислительная сложность обучения$

операций.

Содержание раздела

Главная сайта