Сложность вычисления функции и ее градиента
Подсчитаем теперь число операций, необходимых для вычисления всех двойственных переменных ?(?) для вершин и ?(?', ?) - для ребер.
Во-первых, нужно вычислить все частные производные
для всех вершин ? и всех k аргументов "простой" функции, соответствующей каждой вершине. Число таких производных равно сумме числа аргументов для всех функциональных символов, соответствующих вершинам графа, то есть следующей величине E:
Договоримся в этом разделе отображать ребра (?', ?), имеющие в своих метках P(?', ?) больше одного номера, как пучки ребер, идущих от вершины ?' к вершине ? - по одному такому ребру для каждого номера из P(?', ?). Число E просто равно числу ребер в графе. Число необходимых умножений и число сложений также не превосходят E.
Количество вычислений "простых" функций при вычислении сложной равно числу вершин графа. Обозначим его V. Отношение E/V дает представление об отношении вычислительных затрат на вычисление градиента к затратам на вычисление функции. Чтобы последовательно использовать эту оценку, а также искать те функции, для которых вычисление градиента еще проще, необходимо зафиксировать исходные предположения. Будем обозначать Tf затраты на вычисление f.
- Для каждой вершины графа, соответствующей ей функции f, и любого аргумента этой функции x справедлива оценка ;
- Для функций , соответствующих вершинам графа,
, то есть сумма переменных - простейшая функция;
- Умножение и сложение имеют примерно одинаковую сложность.
В предположениях 1-3 зафиксирован тот уровень точности, с которым будут делаться оценки. При формальном использовании отношения "a примерно равно b" неизбежны парадоксы типа "куча": один камень не куча, если n камней - не куча, то и n+1 - тоже, следовательно... . Чтобы избежать этого и сделать рассуждения более наглядными, поступим следующим образом. Сложность "простой" функции k переменных и любой ее частной производной оценим как ck, где c - некоторая константа,
Последнее вычитание единицы имеет смысл при рассмотрении большого числа сумм, содержащих мало слагаемых.
Пусть, как и выше, E- число ребер графа, V- число вершин, Vout - число выходных вершин (им не соответствует ни одной суммы в (6)). Сложность прямого прохождения графа (вычисления функций) оценивается как cE.
Обратное прохождение графа при вычислении градиентов складывается из трех слагаемых:
- Вычисление всех частных производных простых функций, соответствующих вершинам графа. Необходимо вычислить E таких производных. Сложность вычисления одной такой производной для вершины ?, имеющей |in(?)| входящих ребер, оценивается как c|in(?)|. Оценка сложности вычисления всех этих производных дается следующей суммой
- Вычисление всех произведений (7) на ребрах - E произведений (в связи с тем, что мы в данном разделе передачу сигнала на разные входы автомата, вычисляющего , обозначаем различными ребрами, уравнения (7), сохраняя прежнюю внешнюю форму, преобразуются так, что в суммах остается по одному слагаемому, остальное суммирование переносится к вершинам (6)).
- Вычисление всех сумм (6) - сложность равна E-(V-Vout).
Итого, полная сложность обратного прохождения сигналов оценивается как
Основную роль в последней сумме играет первое слагаемое - именно им определяется сложность обратного распространения по графу (если все |in(?)|=1, то TDif =cE, а уже в случае, когда |in(?)|=2, мы получаем TDif =2cE). Поэтому можно положить T ? TDif (строго говоря,
Если характерное число переменных у простых функций, соответствующих вершинам графа, равно m (то есть |in(?)|=m), то для вычисляемой по графу сложной функции F можно оценить отношение затрат на вычисление F и gradF следующим образом:
Эта оценка, конечно, лучше, чем полное число переменных n, но все же искомое отношение оценивается примерно как отношение числа ребер к числу вершин E/V (с точностью до менее значимых слагаемых). Если нас интересуют графы с большим числом связей, то для сохранения эффективности вычисления градиентов нужно ограничиваться специальными классами простых функций.
Из исходных предположений 1-3 наиболее существенно первое (
Ответ очевиден: общий вид таких функций
 | (12) |
В общем случае функции (12) билинейны. Их частный случай - линейные функции: если индексам из P2 в (12) соответствуют константы, то функция f - линейная.
И функции вида (12), и соответствующие им вершины будем называть квазилинейными.
Пусть интерпретация функциональных символов такова, что в графе вычислений присутствуют только вершины двух сортов: квазилинейные или с одной входной связью (соответствующие простым функциям одного переменного). Обозначим количества этих вершин Vq и V1 соответственно. Оценка сложности вычисления градиента для таких графов принципиально меняется. Обратное функционирование в этом случае требует следующих затрат:
- Поиск всех производных функций одного переменного, соответствующих вершинам графа (число таких производных равно V1), сложность поиска одной производной оценивается как c.
- Вычисление всех произведений (7) на ребрах - E произведений.
- Вычисление всех сумм (6) - сложность равна E-(V-Vout).
Итого, суммарная сложность обратного прохождения сигналов оценивается как
T gradF = cV 1+2E-(V- V out).
Оценим сложность вычислений при прямом распространении:
- Для любой квазилинейной вершины ? сложность вычисления функции оценивается как ,
- Для любой вершины с одной входной связью сложность оценивается как c.
Итак, для прямого распространения сложность оценивается как
T F =cV 1+(E- V 1- V q).
С ростом числа связей
Графы вычислений (с заданной интерпретацией функциональных символов), в которых присутствуют только вершины двух сортов: квазилинейные или с одной входной связью (соответствующие простым функциям одного переменного) играют особую роль. Будем называть их существенно квазилинейными. Для функций, вычисляемых с помощью таких графов, затраты на вычисление вектора градиента примерно вдвое больше, чем затраты на вычисление значения функции (всего!). При этом число связей и отношение
Таким образом, обратное прохождение адаптивного сумматора требует таких же затрат, как и прямое. Для других элементов стандартного нейрона обратное распространение строится столь же просто: точка ветвления при обратном процессе превращается в простой сумматор, а нелинейный преобразователь
Отличие общего случая от более привычных нейронных сетей состоит в том, что можно использовать билинейные комбинации (12) произвольных уже вычисленных функций, а не только линейные функции от них с постоянными коэффициентами-весами.
В определенном смысле квазилинейные функции (12) вычисляются линейными сумматорами с весами 1 и
Естественно возникает вопрос о вычислительных возможностях сетей, все вершины которых являются квазилинейными. Множество функций, вычисляемых такими сетями, содержит все координатные функции и замкнуто относительно сложения, умножения на константу и умножения функций. Следовательно оно содержит и все многочлены от любого количества переменных.Любая непрерывная функция на замкнутом ограниченном множестве в конечномерном пространстве может быть сколь угодно точно приближена с их помощью.
