Сложность вычисления функции и ее градиента
Подсчитаем теперь число операций, необходимых для вычисления всех двойственных переменных ?(?) для вершин и ?(?', ?) - для ребер.
Во-первых, нужно вычислить все частные производные
![](../../../../img/tex/6/d/a/6da42d39aba428277b4b009d882a9cca.png)
для всех вершин ? и всех k аргументов "простой" функции, соответствующей каждой вершине. Число таких производных равно сумме числа аргументов для всех функциональных символов, соответствующих вершинам графа, то есть следующей величине E:
![](../../../../img/tex/5/7/2/572bed8719d3a81167b96b7cea5df540.png)
Договоримся в этом разделе отображать ребра (?', ?), имеющие в своих метках P(?', ?) больше одного номера, как пучки ребер, идущих от вершины ?' к вершине ? - по одному такому ребру для каждого номера из P(?', ?). Число E просто равно числу ребер в графе. Число необходимых умножений и число сложений также не превосходят E.
Количество вычислений "простых" функций при вычислении сложной равно числу вершин графа. Обозначим его V. Отношение E/V дает представление об отношении вычислительных затрат на вычисление градиента к затратам на вычисление функции. Чтобы последовательно использовать эту оценку, а также искать те функции, для которых вычисление градиента еще проще, необходимо зафиксировать исходные предположения. Будем обозначать Tf затраты на вычисление f.
- Для каждой вершины графа, соответствующей ей функции f, и любого аргумента этой функции x справедлива оценка ;
- Для функций , соответствующих вершинам графа,, то есть сумма переменных - простейшая функция;
- Умножение и сложение имеют примерно одинаковую сложность.
В предположениях 1-3 зафиксирован тот уровень точности, с которым будут делаться оценки. При формальном использовании отношения "a примерно равно b" неизбежны парадоксы типа "куча": один камень не куча, если n камней - не куча, то и n+1 - тоже, следовательно... . Чтобы избежать этого и сделать рассуждения более наглядными, поступим следующим образом. Сложность "простой" функции k переменных и любой ее частной производной оценим как ck, где c - некоторая константа,
![](../../../../img/tex/a/7/6/a76f18a9e60d7c10060259d500d6cb33.png)
Последнее вычитание единицы имеет смысл при рассмотрении большого числа сумм, содержащих мало слагаемых.
Пусть, как и выше, E- число ребер графа, V- число вершин, Vout - число выходных вершин (им не соответствует ни одной суммы в (6)). Сложность прямого прохождения графа (вычисления функций) оценивается как cE.
Обратное прохождение графа при вычислении градиентов складывается из трех слагаемых:
- Вычисление всех частных производных простых функций, соответствующих вершинам графа. Необходимо вычислить E таких производных. Сложность вычисления одной такой производной для вершины ?, имеющей |in(?)| входящих ребер, оценивается как c|in(?)|. Оценка сложности вычисления всех этих производных дается следующей суммой
- Вычисление всех произведений (7) на ребрах - E произведений (в связи с тем, что мы в данном разделе передачу сигнала на разные входы автомата, вычисляющего , обозначаем различными ребрами, уравнения (7), сохраняя прежнюю внешнюю форму, преобразуются так, что в суммах остается по одному слагаемому, остальное суммирование переносится к вершинам (6)).
- Вычисление всех сумм (6) - сложность равна E-(V-Vout).
Итого, полная сложность обратного прохождения сигналов оценивается как
![](../../../../img/tex/9/0/e/90e4ac3dc9c6d51042ababc959e8ec27.png)
Основную роль в последней сумме играет первое слагаемое - именно им определяется сложность обратного распространения по графу (если все |in(?)|=1, то TDif =cE, а уже в случае, когда |in(?)|=2, мы получаем TDif =2cE). Поэтому можно положить T ? TDif (строго говоря,
![](../../../../img/tex/5/a/e/5ae6f3abda83b5840c20e6effc07fb22.png)
Если характерное число переменных у простых функций, соответствующих вершинам графа, равно m (то есть |in(?)|=m), то для вычисляемой по графу сложной функции F можно оценить отношение затрат на вычисление F и gradF следующим образом:
![](../../../../img/tex/0/4/8/048d80da481f5dca517e6a0a55996da4.png)
Эта оценка, конечно, лучше, чем полное число переменных n, но все же искомое отношение оценивается примерно как отношение числа ребер к числу вершин E/V (с точностью до менее значимых слагаемых). Если нас интересуют графы с большим числом связей, то для сохранения эффективности вычисления градиентов нужно ограничиваться специальными классами простых функций.
Из исходных предположений 1-3 наиболее существенно первое (
![](../../../../img/tex/5/5/2/552e0fb012c0dad77ec85f8cf13f52fa.png)
Ответ очевиден: общий вид таких функций
![]() | (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).
С ростом числа связей
![](../../../../img/tex/f/0/f/f0f262dae02569197befd329e8e83336.png)
Графы вычислений (с заданной интерпретацией функциональных символов), в которых присутствуют только вершины двух сортов: квазилинейные или с одной входной связью (соответствующие простым функциям одного переменного) играют особую роль. Будем называть их существенно квазилинейными. Для функций, вычисляемых с помощью таких графов, затраты на вычисление вектора градиента примерно вдвое больше, чем затраты на вычисление значения функции (всего!). При этом число связей и отношение
![](../../../../img/tex/8/f/c/8fc8cc1c9c7d25d073a428283a007030.png)
Таким образом, обратное прохождение адаптивного сумматора требует таких же затрат, как и прямое. Для других элементов стандартного нейрона обратное распространение строится столь же просто: точка ветвления при обратном процессе превращается в простой сумматор, а нелинейный преобразователь
![](../../../../img/tex/d/9/c/d9c6b344dd066b56f9ded571fc35ee90.png)
![](../../../../img/tex/7/0/a/70a520133ac30259e1edad863a7b0775.png)
![](../../../../img/tex/a/f/4/af42e1a931ce3ac0e0fe2f5eef525d7b.png)
Отличие общего случая от более привычных нейронных сетей состоит в том, что можно использовать билинейные комбинации (12) произвольных уже вычисленных функций, а не только линейные функции от них с постоянными коэффициентами-весами.
В определенном смысле квазилинейные функции (12) вычисляются линейными сумматорами с весами 1 и
![](../../../../img/tex/c/7/d/c7de7d8db9920066ccd844fa2b0fc2b0.png)
![](../../../../img/tex/5/6/c/56c1efdcd7cdac451615aee9fd6908da.png)
![](../../../../img/tex/e/4/e/e4e34a65c27f657754abedcf38f6cb4c.png)
Естественно возникает вопрос о вычислительных возможностях сетей, все вершины которых являются квазилинейными. Множество функций, вычисляемых такими сетями, содержит все координатные функции и замкнуто относительно сложения, умножения на константу и умножения функций. Следовательно оно содержит и все многочлены от любого количества переменных.Любая непрерывная функция на замкнутом ограниченном множестве в конечномерном пространстве может быть сколь угодно точно приближена с их помощью.