Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 196-211

1. ВВЕДЕНИЕ

Поиск минимумов функции потерь является основной стратегией для большинства алгоритмов машинного обучения. График функции потерь, который часто называется поверхностью потерь, обычно имеет сложную структуру [1–3]: невыпуклость, множество локальных минимумов, седловые точки, плоские области. Эти препятствия затрудняют исследование поверхности потерь.

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

Глобальные топологические характеристики множества траекторий градиентного потока описываются комплексом Морса через декомпозицию пространства параметров на ячейки, где поток однороден [4–6]. Бар-коды комплекса, Морса составляют основное резюме топологии потока градиентного векторного поля [7–9]. Бар-коды дают декомпозицию изменения топологии подуровневых множеств функции потерь на элементарные пары метаморфоз “рождение”–“исчезновение”.

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

Расчет бар-кодов для различных функций составляет суть топологического анализа данных. В настоящее время доступные программные пакеты для расчета бар-кодов функций, также называемых “подуровневой персистентностью”, включают GUDHI, Dionysus, PHAT. Они основаны на общем алгоритме, требующем построения симплициального комплекса и имеющем худшую временную сложность $O({{N}^{3}})$ по числу точек для вычисления бар-кода наименьшей степени. Эти пакеты в настоящее время могут обрабатывать расчеты бар-кодов для функций, определенных на сетке, до 10⁶ точек и в размерностях до шести. Таким образом, все существующие пакеты сталкиваются с проблемами масштабируемости.

Мы описываем алгоритм для вычисления бар-кодов наименьшей степени для функций в произвольных размерностях. В отличие от упомянутых методов на основе сетки, наш алгоритм работает с функциями, определенными на произвольно выбранных облаках точек. Известно, что методы на основе облаков точек работают лучше, чем методы на основе сетки, в задачах оптимизации [10]. Для вычисления бар-кодов наименьшей степени мы используем тот факт, что их определение можно переформулировать в геометрических терминах, см. определение 1 в разделе 2. Большинство в настоящее время доступных программных пакетов основаны на более алгебраическом подходе, как в определении 2 из раздела 2. Основная часть нашего алгоритма имеет худшую временную сложность $O(N\log N)$, наш алгоритм был протестирован в размерностях до 15 и с числом точек до 10⁹.

Предложенная методология описывает свойства поверхности потерь нейронных сетей через топологические признаки локальных минимумов. Мы хотели бы подчеркнуть, что значение функции потерь в минимуме составляет только половину его топологической характеристики из бар-кода. Другая половина может быть описана как значение функции потерь в 1-седловой точке, которая естественным образом связана с каждым локальным минимумом, см. раздел 2. 1-седловая точка q, связанная с минимумом p, является точкой, в которой связная компонента подуровневого множества ${{\Theta }_{{f \leqslant c}}} = \left\{ {\theta \in \Theta \,{\text{|}}\,f(\theta )\;\leqslant \;c} \right\}$, содержащая p, объединяется с другой связной компонентой подуровневого множества, содержащей более низкий минимум. Это соответствие между локальными минимумами и 1-седловыми точками, уничтожающими связные компоненты ${{\Theta }_{{f \leqslant c}}}$, является взаимно однозначным.

Сегмент $\left[ {f(p),f(q)} \right]$, где q – это 1-седловая точка, связанная с p, является инвариантом, который в бар-коде связывается с минимумом p. Разница $f(q) - f(p)$ является топологическим инвариантом минимума, количественно оценивающим его как препятствие для алгоритмов обучения на основе градиентных методов. Множество всех таких сегментов для всех минимумов – это бар-код наименьшей размерности функции f.

Основной вклад данной статьи заключаются в следующем:

1) Применение бар-кодов минимумов и соответствия между минимумами и 1-седловыми точками для исследования поверхностей потерь. Для каждого локального минимума p канонически определена 1-седловая точка $q$ (см. Раздел 2). Множество всех сегментов $\left[ {f(p),f(q)} \right]$, где p – локальный минимум, а $q$ – соответствующая 1-седловая точка f, является устойчивым топологическим инвариантом функции потерь. Это множество инвариантно, в частности, относительно действия гомеоморфизмов на $\Theta $. Это множество сегментов является частью полного бар-кода. Полный бар-код дает полное описание топологии функции потерь и глобальной структуры ее градиентного потока.

2) Алгоритм для расчета бар-кодов минимумов. Мы описываем и анализируем алгоритм для расчета бар-кодов минимумов. Алгоритм принимает на вход случайно или специальным образом выбранный набор точек и значения функции потерь на этом наборе. Затем алгоритм использует процедуру HNSW для расчета графа соседей. Следующим шагом является вычисление бар-кода минимумов для функции, определенной на графе. Локальные минимумы порождают кластеры точек в подуровневых множествах. Затем алгоритм работает, рассматривая соседей каждой выбранной точки с более низкими значениями функции и решая, принадлежит ли эта точка существующему кластеру, порождает новый кластер (минимум) или объединяет два или более кластера (1‑седловая точка). Вторая часть алгоритма, работающего с функцией на графе, аналогична частному 0-мерному случаю общего алгоритма, описанного в [7].

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

Наш код доступен в репозитории https://github.com/grag90/BarcodeCalc.

Полезность нашего подхода и алгоритмов не ограничивается задачами оптимизации. Наш алгоритм позволяет быстро вычислять персисентные бар-коды многих функций, которые до сих пор были недоступны. Эти подуровневые персистентные бар-коды успешно применялись в различных дисциплинах: например в когнитивных науках [11], космологии [12], см. также ссылки в [13].

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

Статья содержит следующие разделы. Мы начинаем с двух определений бар-кодов локальных минимумов в разделе 2. Наш алгоритм для расчета бар-кодов описан в разделе 3. В разделе 4 мы применяем наш алгоритм для расчета бар-кодов бенчмарк функций. Мы доказываем сходимость алгоритма и демонстрируем ее эмпирически в подразделе 4. В разделе 5 мы вычисляем бар-коды функций потерь малых нейронных сетей и описываем наши основные наблюдения.

2. ОПИСАНИЕ ТОПОЛОГИЯ ПОВЕРХНОСТЕЙ ПОТЕРЬ ЧЕРЕЗ БАР-КОДЫ

Бар-коды описывают топологические признаки функций представляя изменение топологии подуровневых множеств функции как сумму пар элементарных метаморфоз “рождение”–“исчезновение”. Мы предлагаем применить эти инварианты как инструмент для изучения топологии поверхностей потерь.

В этом разделе мы описываем два определения бар-кодов минимумов для кусочно-гладких непрерывных функций. В этой работе мы сосредотачиваемся на части бар-кодов, описывающих явления “рождения”–“исчезновения” связных компонент подуровневых множеств функции потерь. Подход из этого раздела аналогично работает в контексте “почти минимумов”, т.е. для критических точек (многообразий) малых ненулевых индексов. Такие точки часто также могут являться конечными точками алгоритмов оптимизации в высокомерных пространствах параметров глубоких нейронных сетей [2].

Первое определение: объединение со связной компонентой более низкого минимума

Пусть f является кусочно-гладкой непрерывной функцией. Значения параметра c, при которых топология подуровневых множеств

меняется, являются критическими значениями f.

Пусть p является одним из минимумов f. Когда c увеличивается от $f(p) - \epsilon $ до $f(p) + \epsilon $, рождается новая связная компонента множества ${{\Theta }_{{f\leqslant c}}}$. Для иллюстрации этого процесса мы приводим пример на рис. 1, где связные компоненты S₁, ${{S}_{2}},{{S}_{3}},{{S}_{4}}$ подуровневого множества рождаются в минимумах ${{p}_{1}},\;{{p}_{2}},\;{{p}_{3}},\;{{p}_{4}}$ соответственно.

Связные компоненты подуровневых множеств объединяются в 1-седловых критических точках.

Точка $q$ является 1-седловой критической точкой, если пересечение множества ${{\Theta }_{{f < f(q)}}}$ с любой малой окрестностью $q$ имеет более одной связной компоненты. Без потери общности в этом разделе мы можем предположить, что 1-седловые точки  f являются особенностями общего положения, так что эти пересечения имеют не более двух связных компонент. В противном случае можно всегда добавить небольшое возмущение к f или рассмотреть 1-седловые точки с кратностью, заданной числом этих компонент минус один.

Пусть $p$ – это минимум, не являющийся глобальным. С увеличением $c$, связная компонент ${{\Theta }_{{f\leqslant c}}}$, рожденная в $p$, объединяется с другой связной компонентой. Затем эта объединенная связная компонента может снова объединиться с другой. После каждого объединения минимум ограничения f на объединенной связной компоненте является наименьшим из двух минимумов ограничения f на каждую из двух связных компонент перед объединением. Другими словами, связная компонента с более низким минимумом “поглощает” в точке объединения связную компоненту с более высоким минимумом, см. рис. 1. Пусть $q$ является точкой объединения, где связная компонента с минимумом $p$ поглощается связной компонентой, чей минимум ниже. Заметим, что пересечение множества ${{\Theta }_{{f < f(q)}}}$ с любой малой окрестностью $q$ имеет по крайней мере две связных компоненты.

Определение 1. Точка объединения $q$, где связная компонента с минимумом $p$ поглощается связной компонентой с более низким минимумом, является 1-седлом, естественно связанным с минимумом $p$. Сегмент $\left[ {f(p),f(q)} \right]$ естественно ассоциируется в бар-коде с минимумом $p$.

Обратите внимание, что две связные компоненты пересечения малой окрестности такой $q$ с ${{\Theta }_{{f < f(q)}}}$ принадлежат двум разным связным компонентам всего множества ${{\Theta }_{{f < f(q)}}}$. 1-седловые этого типа называются “плюс” или типом “исчезновения”. Заметим, что

Утверждение 1. Описанное соответствие между локальными минимумами и 1-седлами такого типа является взаимно однозначным.

Доказательство. Соответствие в обратном направлении можно описать следующим образом. Пусть $q$ является 1-седловой точкой такого типа, что две ветви множества ${{\Theta }_{{f < f(q)}}}$ рядом с $q$ не связаны во всем множестве ${{\Theta }_{{f < f(q)}}}$. Одна из связных компонент подуровневого множества ${{\Theta }_{{f \leqslant c}}}$ разделяется на две, когда $c$ уменьшается от $f(q) + \epsilon $ до $f(q) - \epsilon $. Пусть ${{p}_{1}}$ и ${{p}_{2}}$ являются двумя минимумами ограничения f на каждую из этих двух связных компонент. Пусть ${{p}_{1}} > {{p}_{2}}$ является наибольшим из двух минимумов. 1-седло $q$ связано по определению 1 с локальным минимумом ${{p}_{1}}$, так как две связных компоненты объединяются в $q$. Заметим что

т.е. ${{p}_{1}}$ не появляется среди минимумов f на одной из связных компонент ${{\Theta }_{{f\leqslant f(q) + \epsilon }}}$. Другими словами, минимум ${{p}_{1}}$, который соответствует $q$ по определению 1, является новым минимумом, появляющимся в множестве минимумов f на связных компонентах ${{\Theta }_{{f\leqslant c}}}$, когда $c$ уменьшается от $f(q) + \epsilon $ до $f(q) - \epsilon $.              $\square $

Для применения в разделе 6 важно, чтобы 1‑седла, связанные с минимумами, описывались следующим образом.

Утверждение 2. Рассмотрим различные пути $\gamma $, начинающиеся от локального минимума $p$ и идущие к более низкому минимуму. Пусть ${{m}_{\gamma }} \in \Theta $ является максимумом ограничения f на таком пути $\gamma $. Тогда 1-седло $q$, соответствующее локальному минимуму $p$ в бар-коде, является минимумом по множеству всех таких путей $\gamma $ максимумов ${{m}_{\gamma }}$:

Доказательство. Пусть связная компонента локального минимума $p$ объединяется со связной компонентой более низкого минимума в точке $q$. Тогда существует путь в подуровневом множестве ${{\Theta }_{{f\leqslant f(q)}}}$, проходящий через $q$ и соединяющий $p$ с более низким минимумом. Точка $q$ является максимумом ограничения f на этом пути. И пути в подуровневых множествах ${{\Theta }_{{f\leqslant c}}}$, $c < f(q)$, который соединял бы $p$ с более низким минимумом, нет. Следовательно, не существует пути с $f({{m}_{\gamma }})\, < \,f(q)$ и $q$ удовлетворяет уравнению (1).                               $\square $

Второе определение: инварианты фильтрованных комплексов

Мы напоминаем здесь определение для полного бар-кода [7]. Хотя наш алгоритм из раздела 3 основан на определении 1, нам нужно определение 2 ниже, чтобы вставить вещи в общую рамку, в которой эти инварианты составляют полное описание топологии функции потерь и глобального поведения градиентного потока.

Семейства траекторий градиентного потока, исходящие из одной и той же особой точки, разлагают область $\Theta $ на ячейки, на которых градиентный поток ведет себя равномерно [6].

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

Напомним, что цепной комплекс $({{C}_{*}},{{\partial }_{*}})$ представляет собой последовательность конечномерных векторных пространств ${{C}_{j}}$ (пространства “$j$-цепей”) и линейных операторов (“дифференциалов”)

которые удовлетворяют ${{\partial }_{j}}\, \circ \,{{\partial }_{{j + 1}}}\, = \,0$. $j$-я гомология цепного комплекса $({{C}_{*}},{{\partial }_{*}})$ является частным векторных пространств H_j = $\ker \left( {{{\partial }_{j}}} \right){\text{/im}}\left( {{{\partial }_{{j + 1}}}} \right)$.

Разложение сложного геометрического объекта на простые части делается часто в определенном последовательном порядке, в этом случае алгебраический аналог такого разложения представляет собой $\mathbb{R}$-фильтрованный цепной комплекс. Напомним что подкомплекс $(C_{*}^{'},\partial _{*}^{'})\, \subseteq \,({{C}_{*}},{{\partial }_{*}})$ представляет собой последовательность подпространств $C_{j}^{'} \subseteq {{C}_{j}}$, вместе с согласованными дифференциалами $\partial _{j}^{'} = {{\partial }_{j}}{{{\text{|}}}_{{C_{j}^{'}}}}$. Цепной комплекс ${{C}_{*}}$ называется $\mathbb{R}$-фильтрованным, если в ${{C}_{*}}$ имеется возрастающая последовательность подкомплексов ($\mathbb{R}$-фильтрация): ${{F}_{{{{s}_{1}}}}}{{C}_{*}}\, \subset \,{{F}_{{{{s}_{2}}}}}{{C}_{*}}\, \subset \, \ldots \, \subset \,{{F}_{{{{s}_{{\max }}}}}}{{C}_{*}}\, = \,{{C}_{*}}$, индексированная конечным множеством вещественных чисел ${{s}_{1}} < {{s}_{2}} < \ldots < {{s}_{{{\text{max}}}}}$.

Теорема 3 ([7], Секция 2). Любой $\mathbb{R}$-фильтрованный цепной комплекс ${{C}_{*}}$ может быть приведен к канонической форме, т.е. к канонически определенной прямой сумме $\mathbb{R}$-фильтрованных комплексов двух типов: одномерные комплексы с тривиальным дифференциальном ${{\partial }_{j}}({{e}_{i}}) = 0$ и двумерные комплексы с тривиальными гомологиями ${{\partial }_{j}}({{e}_{{{{i}_{2}}}}})\, = \,{{e}_{{{{i}_{1}}}}}$, с помощью линейного преобразования, сохраняющего $\mathbb{R}$-фильтрацию. Получившаяся прямая сумма таких простых $\mathbb{R}$-фильтрованных комплексов единственна.

Определение 2. Полный бар-код представляет собой визуализацию разложения $\mathbb{R}$-фильтрованного комплекса в соответствии с теоремой 3. Каждый фильтрованный 2-мерный комплекс с тривиальными гомологиями ${{\partial }_{j}}({{e}_{{{{i}_{2}}}}})\, = \,{{e}_{{{{i}_{1}}}}}$, $\left\langle {{{e}_{{{{i}_{1}}}}}} \right\rangle \, = \,{{F}_{{\leqslant {{s}_{1}}}}}$, $\left\langle {{{e}_{{{{i}_{1}}}}},{{e}_{{{{i}_{2}}}}}} \right\rangle \, = \,{{F}_{{\leqslant {{s}_{2}}}}}$ описывает один топологический признак в размерности $j$, который “рождается” в ${{s}_{1}}$ и “исчезает” в ${{s}_{2}}$. Он представлен сегментом $[{{s}_{1}},{{s}_{2}}]$ в бар-коде степени $j$. А каждый фильтрованный одномерный комплекс с тривиальным дифференциалом, ${{\partial }_{j}}{{e}_{i}} = 0$, $\left\langle {{{e}_{i}}} \right\rangle = {{F}_{{ \leqslant r}}}$ описывает топологический признак размерности $j$, который “рождается” в $r$ и никогда не “исчезает”. Он представлен полупрямой $[r, + \infty [$ в бар-коде степени $j$.

Доказательство Теоремы 3 приведено в [7], Секция 2, см. также [8, 9]. Мы описываем его в Приложении 9 для удобства читателя. По сути, можно привести $\mathbb{R}$-фильтрованный комплекс к требуемой прямой сумме простых $\mathbb{R}$-фильтрованных комплексов по индукции, начиная с наименьших базисных элементов степени один, таким образом, что манипуляции с базисными элементами степени $j$ не разрушают полученное разложение на простые $\mathbb{R}$-фильтрованные комплексы в степени $j - 1$ и в более низких частях фильтрации в степени $j$.

Пусть $f:\Theta \to \mathbb{R}$ – это гладкая, или, в более общем случае, кусочно-гладкая непрерывная функция, такая что подуровневые множества ${{\Theta }_{{f \leqslant c}}} = \left\{ {\theta \in \Theta \,{\text{|}}\,f(\theta )\;\leqslant \;c} \right\}$ компактны.

Существуют разные фильтрованные цепные комплексы, вычисляющие гомологии топологических пространств ${{\Theta }_{{f\leqslant c}}}$, например, Čech комплексы, симплициальные комплексы или CW-комплексы. Без потери общности можно предположить, что кусочно-гладкая функция f является гладкой, в противном случае всегда можно заменить f на гладкое приближение. Добавив небольшое возмущение, можно также предположить, что критические точки f являются невырожденными, а критические значения различными.

Один фильтрованный цепной комплекс, естественно связанный с такой функцией f, с подкомплексами ${{F}_{s}}{{C}_{*}}$, вычисляющими гомологии подуровневых множеств ${{\Theta }_{{f\leqslant s}}}$, – это комплекс Морса, см. приложение A и [4, 5] для дополнительной информации. Комплекс Морса определяется следующим образом. Базисные элементы в $k$-векторных пространствах ${{C}_{j}}$ соответствуют критическим точкам f индекса $j$ с выбором ориентации. Ориентация здесь – это выбор ориентации $j$-мерного подпространства касательного пространства в критической точке, на котором гессиан отрицательно определен. Матрица ${{\partial }_{j}}$ состоит из числа траекторий градиента, учитываемых со знаками, между критическими точками индекса $j$ и индекса $(j - 1)$. Естественная фильтрация на комплексе Морса задается значениями критических точек. Базисные элементы в ${{F}_{s}}{{C}_{*}}$ соответствуют критическим точкам с критическим значением $s$ и ниже.

Утверждение 4. Пусть $p$ – минимум, который не является глобальным. Тогда $p$ представляет тривиальный класс гомологий в комплексе Морса, вычисляющем гомологии ${{\Theta }_{{f\leqslant c}}}$ для достаточно большого $c$, т.е. $p$ является нижним базисным элементом одного из двумерных комплексов с тривиальными гомологиями в канонической форме. Таким образом, $p$ ассоциировано с 1-седлом $q$. Это 1-седло из определения 1, т.е. $q$ – это 1-седло, возле которой связная компонента подуровневого множества, соответствующая $p$, поглощается связной компонентой с более низким минимумом. Сегмент $\left[ {f(p),f(q)} \right]$, следовательно, соответствует минимуму $p$ по определению 1.

Доказательство. Пусть $q$ – это 1-седловая точка, возле которой связная компонента, соответствующая $p$, поглощается связной компонентой с более низким минимумом $r$. Гомологии ${{H}_{0}}({{\Theta }_{{f\leqslant f(q) - \epsilon }}})$ линейно порождаются классами связных компонент ${{\Theta }_{{f\leqslant f(q) - \epsilon }}}$. Они соответствуют генераторам комплекса Морса, заданным минимумами ограничения f на каждую связную компоненту. В комплексе Морса, вычисляющем гомологии ${{\Theta }_{{f\leqslant f(q) + \epsilon }}}$, генератор, соответствующий локальному минимуму $p$, после приведения к канонической форме, равен границе генератора, соответствующего 1-седлу $q$, так как класс гомологий соответствующий генератору $p$ исчезает в $f(q)$. Следовательно, $q$ ассоциирован с $p$ в канонической форме.        $\square $

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

Общее количество различных топологических признаков в подуровневых множествах ${{\Theta }_{{f\leqslant c}}}$ функции потерь можно непосредственно получить из бар-кода. А именно, количество пересечений горизонтальной линии на уровне $c$ с сегментами в бар-коде индекса $j$ дает количество независимых топологических признаков размерности $j$ в ${{\Theta }_{{f\leqslant c}}}$, см. примеры в разделе 4.

3. АЛГОРИТМ ДЛЯ ВЫЧИСЛЕНИЯ БАР-КОДОВ МИНИМУМОВ

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

Для анализа поверхности заданной функции $f:\Theta \to \mathbb{R}$ мы сначала строим ее приближение на основе конечного графа. Для этого мы рассматриваем случайно выбранное подмножество точек $\{ {{\theta }_{1}}, \ldots ,{{\theta }_{N}}\} \in \Theta $ и строим граф с этими точками в качестве вершин. Мы соединяем вершины ребром, если точки близки. Таким образом, для каждой вершины ${{\theta }_{n}}$, сравнивая $f({{\theta }_{n}})$ с $f({{\theta }_{{n{\kern 1pt} '}}})$ для соседей ${{\theta }_{{n{\kern 1pt} '}}}$ вершины ${{\theta }_{n}}$, мы можем описать локальную топологию возле точки ${{\theta }_{n}}$. В то же время связные компоненты подуровневых множеств ${{\Theta }_{{f\leqslant c}}}$ соответствуют, см. Утверждение 5 ниже, связным компонентам подграфа ${{\Xi }_{{f\leqslant c}}}$ точек ${{\theta }_{n}}$, таких что $f({{\theta }_{n}})\;\leqslant \;c$.

Два технических момента здесь – это выбор точек ${{\theta }_{n}}$ и определение близости, т.е. когда точки соединяются ребром. В наших экспериментах мы выбираем точки равномерно из некоторого куба. Чтобы добавить ребра, мы вычисляем ориентированный граф $k$-ближайших соседей на заданных точках, затем отбрасываем ориентацию ребер и проверяем, что расстояние между соседями не превышает $c(D){{N}^{{ - \frac{1}{D}}}}$, где $D$ – размерность входных данных функции f. В наших экспериментах мы используем k = 2D.

Теперь мы описываем часть алгоритма, который вычисляет бар-коды функции по ее приближению на основе графа, описанного выше. Основная идея заключается в том, чтобы отслеживать эволюцию связных компонент подуровневых подмножеств графа ${{\Xi }_{{f\leqslant c}}}\, = \,\{ {{\theta }_{n}}\,{\text{|}}\,f({{\theta }_{n}})\;\leqslant \;c\} $ при увеличении $c$.

Для простоты предположим, что точки $\theta $ упорядочены по значению функции f, т.е. для $n < n{\kern 1pt} '$ у нас есть $f({{\theta }_{n}}) < f({{\theta }_{{n'}}})$. В этом случае нас интересует эволюция связных компонент в процессе последовательного добавления вершин ${{\theta }_{1}},{{\theta }_{2}}, \ldots ,{{\theta }_{N}}$ в граф, начиная с пустого графа. Обозначим подграф на вершинах ${{\theta }_{1}}, \ldots ,{{\theta }_{n}}$ как ${{\Xi }_{n}}$. Когда мы добавляем новую вершину ${{\theta }_{{n + 1}}}$ к ${{\Xi }_{n}}$, есть три возможности эволюции связных компонент:

1. Вершина ${{\theta }_{{n + 1}}}$ имеет нулевую степень в ${{\Xi }_{{n + 1}}}$. Это означает, что ${{\theta }_{{n + 1}}}$ является локальным минимумом f и образует новую связную компоненту в подуровневом множестве.

2. Все соседи ${{\theta }_{{n + 1}}}$ в ${{\Xi }_{{n + 1}}}$ принадлежат одной связной компоненте в ${{\Xi }_{n}}$.

3. Все соседи ${{\theta }_{{n + 1}}}$ в ${{\Xi }_{{n + 1}}}$ принадлежат $K\; \geqslant \;2$ связным компонентам ${{s}_{1}},{{s}_{2}}, \ldots ,{{s}_{K}}$ в ${{\Xi }_{n}}$. Таким образом, все эти компоненты объединяться в одну связную компоненту в ${{\Xi }_{{n + 1}}}$.

В третьем случае, согласно определению 1 раздела 2, точка ${{\theta }_{{n + 1}}}$ является дискретной 1-седловой точкой. Таким образом, одна из компонент ${{s}_{k}}$ поглощает все остальные. Эта компонента, которая имеет наименьшее минимальное значение. Для оставшихся компонент это задает их бар-коды: для ${{s}_{i}},i \ne k$ пара рождение-исчезновение равна $[\mathop {\min }\limits_{\theta \in {{s}_{i}}} f(\theta );f({{\theta }_{{n + 1}}})]$. Мы резюмируем эту процедуру в алгоритме 1.

4. БАР-КОДЫ БЕНЧМАРК ФУНКЦИЙ И СХОДИМОСТЬ АЛГОРИТМА

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

Мы применяем наш алгоритм к нескольким функциям $f:{{\mathbb{R}}^{D}} \to \mathbb{R}$ из Global Optimization Benchmark (см., например, [17]). Эти функции предназначены для обмана алгоритмов глобальной оптимизации, они очень сложные, имеют много локальных минимумов и седловых точек даже для малых размерностей. Таким образом, вычисление бар-кодов и соответствия минимум-седло для этих функций также представляет собой достаточно трудную задачу.

Бар-коды 2D бенчмарк функций

Для начала мы вычисляем бар-коды нескольких двумерных бенчмарк функций. Мы визуализируем полученные бар-коды и соответствие минимум-седло. Затем мы проводим эксперименты, чтобы оценить, как количество точек, используемых для вычисления бар-кодов, влияет на качество ответа. Мы рассматриваем следующие тестовые целевые функции:

1. HumpCamel6 функция f : [–2, 2] × [–1.5, $1.5] \to \mathbb{R}$ с 6 локальными минимумами (рис. 2):

2. Langermann целевая функция $f{{:[0,10]}^{2}} \to \mathbb{R}$ (рис. 3):

Чтобы сохранить графики простыми, мы отображали соответствие минимум-седло только для верхних 30 сегментов в бар-коде, отсортированных по размеру кластера (количество точек в момент поглощения кластера). Как мы видим на рис. 2, соответствие между минимумом и седлом не тривиально. Для многих минимумов соответствующие седла находятся довольно далеко. В частности, это наблюдение иллюстрирует замечание, обсуждаемое на рис. 1: соответствующее минимуму 1-седло часто не является ближайшим седлом.

3. Wavy тестовая целевая функция $f\,:\,{{[ - \pi ,\pi ]}^{2}}\, \to \,\mathbb{R}$ (рис. 4):

Функция Wavy симметрична относительно диэдральной группы D₄ порядка 8. Таким образом, ее пары критических значений минимум-седло образуют мультиплеты, формируя простые представления группы D₄.

4. HolderTable тестовая целевая функция f : [–10, ${{10]}^{2}} \to \mathbb{R}$ (рис. 5):

Сходимость Алгоритма

В этом подразделе мы доказываем и эмпирически проверяем сходимость нашего алгоритма, когда количество точек $N$, используемых для построения бар-кодов, стремится к бесконечности. Для сравнения двух бар-кодов мы принимаем расстояние Bottleneck [9, 18], также известное как расстояние Вассерштейн-$\infty $, ${{\mathbb{W}}_{\infty }}$, на диаграммах персистентности (двумерные облака точек пар рождение-исчезновение):

Здесь $\Delta $ обозначает “диагональ” (пары с “рождением” равным “исчезновению”), а $\Gamma (\mathcal{D},\mathcal{D}{\kern 1pt} ')$ обозначает набор частичных соответствий между $\mathcal{D}$ и $\mathcal{D}{\kern 1pt} '$, определенных как биекции между $\mathcal{D} \cup \Delta $ и $\mathcal{D}{\kern 1pt} '\; \cup \Delta $.

Для функции $f:\Theta \to \mathbb{R}$ пусть $\mathcal{D}_{f}^{*}$ обозначает ее бар-код. Наш алгоритм использует конечное число N случайно выбранных точек ${{\Theta }_{N}}\, = \,\{ {{\theta }_{1}}, \ldots ,{{\theta }_{N}}\} $ для вычисления приближения ${{\hat {\mathcal{D}}}_{f}}({{\Theta }_{N}})$ истинного бар-кода $\mathcal{D}_{f}^{*}$. Пусть C обозначает константу Липшица для f.

Утверждение 5. Пусть для любого $\theta \in \Theta $ существует ${{\theta }_{i}} \in {{\Theta }_{N}}$ такое, что ${\text{|}}\theta - {{\theta }_{i}}{\text{|}} < \varepsilon $. Тогда

Доказательство. Это следует, например, из ([16], Лемма 1).                  $\square $

Отметим, что для типичной выборки ${{\Theta }_{N}}$ максимальное расстояние от $\theta \in \Theta $ до ${{\Theta }_{N}}$ составляет $ \sim {\kern 1pt} {{N}^{{ - \frac{1}{D}}}}$. Из этого следует, что ${{\hat {\mathcal{D}}}_{f}}({{\Theta }_{N}})$ сходится к $\mathcal{D}_{f}^{*}$ при $N \to \infty $ для любой типичной последовательности выборок $\{ {{\Theta }_{N}}\} $. И в частности,

при $N \to \infty $ для любой типичной пары последовательностей $\{ {{\Theta }_{N}}\} ,\;\{ \Theta _{N}^{'}\} $.

Мы проверили условие (3) на нескольких тестовых функциях из набора для глобальной оптимизации. Каждая из тестовых функций представляет собой серию функций произвольной размерности. Даже для небольших размерностей они чрезвычайно сложны (содержат экспоненциальное количество локальных минимумов и седловых точек). Для каждой функции а и размерности $D = 3,4,5,6$ мы рассматриваем различные размеры выборок $\mathop {\log }\nolimits_{10} N \in [3,3.5,4, \ldots ,7]$. Для каждой тройки $(f,D,N)$ мы случайно выбираем $R$ пар $(({{\Theta }_{N}}{{)}_{r}},(\Theta _{N}^{'}{{)}_{r}})$ облаков точек размера N. Затем для каждого из $2R$ облаков точек мы вычисляем бар-код нашим алгоритмом и в каждой паре измеряем расстояние ${{\mathbb{W}}_{\infty }}$ между бар-кодами. Наконец, мы берем среднее значение

Рассматриваемые функции:

1. Alpine01 функция $f:[ - {{10,10]}^{D}} \to \mathbb{R}$ определена как

2. Schwefel26 функция $f:[ - {{500,500]}^{D}} \to \mathbb{R}$ определена как:

3. XinSheYang04 функция $f:[ - {{10,10]}^{D}} \to \mathbb{R}$ определена как:

Для каждой пары $(f,D)$ мы резюмируем зависимость от размера облака N в виде графика в десятичной логарифмической шкале. Мы эмпирически наблюдаем, что для достаточно больших N

как и ожидалось на основе Предложения 5.

Результаты представлены на рис. 6.

В табл. 1 время выполнения Алгоритма 1, включая поиск HNSW NN, на случайных выборках из 106 точек, сравнивается со временем выполнения для платформы GUDHI на сетке из 106 точек для функций Alpine01 и Schwefel26 в размерностях $D \in \{ 3,4,5,6,7\} $.

5. ТОПОЛОГИЯ ФУНКЦИЙ ПОТЕРЬ НЕЙРОННЫХ СЕТЕЙ

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

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

Для нескольких архитектур нейронных сетей известно множество результатов о поверхности потерь (см., например, [19, 20] и ссылки в них). Различные геометрические и топологические свойства поверхностей потерь были изучены в [21–24].

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

Для каждой анализируемой нейронной сети функция потерь представляет собой среднеквадратичную ошибку при прогнозировании (случайно выбранной) функции $g:[ - \pi ,\pi ] \to \mathbb{R}$, заданной как

плюс ${{l}_{2}}$-регуляризация. Ошибка вычисляется для прогноза на равномерно распределенных входах $x \in \left\{ { - \pi + \frac{{2\pi }}{{100}}k\,{\text{|}}\,k = 0,1, \ldots ,100} \right\}$.

6. ТОПОЛОГИЯ ФУНКЦИЙ ПОТЕРЬ НЕЙРОННЫХ СЕТЕЙ

Мы рассмотрели полносвязные нейронные сети с одним скрытым слоем из 2 и 3 нейронов, двумя скрытыми слоями с 2 × 2, 3 × 2 и 3 × 3 нейронами, и тремя скрытыми слоями с 2 × 2 × 2 и 3 × × 2 × 2 нейронами с активацией $ReLU$. Мы вычислили бар-коды функций потерь на гиперкубических множествах $\Theta $, которые были выбраны на основе типичного диапазона параметров минимумов. Результаты представлены на рис. 8.

Наши результаты дают следующие два наблюдения:

1. Бар-коды расположены в очень малой нижней части диапазона значений; обычно максимальное значение функции было около 200 и выше, и седла, соединенные с минимумами, лежат гораздо ниже 1.

2. С увеличением глубины и ширины нейронной сети бар-коды опускаются ниже.

Например, верхние границы бар-кодов однослойной сети (2) находятся в диапазоне [0.55, 0.65], двухслойной сети (2 × 2) – в диапазоне [0.35, 0.45], и трехслойной сети (2 × 2 × 2) – в диапазоне [0.1, 0.3].

Следствия для обучения

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

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

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

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

Стратегия вычисления бар-кодов для глубоких нейронных сетей

Исследование поверхности потерь с использованием методов топологического анализа данных может быть расширено на глубокие нейронные сети. Стратегия для глубоких нейронных сетей основана на предложении 2 выше. Идея заключается в том, чтобы действовать методом градиентного спуска по пути, начиная с данного минимума и идущего к точке с более низким минимумом. Деформация пути под действием градиентного потока задается действием компонента градиента, который ортогонален касательному направлению пути. Компонент градиента, который параллелен направлению касания пути, поглощается перепараметризацией пути. Затем формула (1) дает оценку значения 1-седла, соответствующего этому минимуму в бар-коде.

Следствия для обобщения

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

7. ЗАКЛЮЧЕНИЕ

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

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

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

Разработанный нами метод имеет несколько направлений для дальнейших исследований. Хотя мы тестировали метод на небольших нейронных сетях, его можно применить к современным нейронным сетям, таким как сверточные сети (например, ResNet, VGG, AlexNet, U-Net, см. [25]) для задач обработки изображений. Однако в этом случае графовая аппроксимация, которую мы используем, требует разумного выбора представителей вершин графа, так как плотное заполнение области точками вычислительно неприемлемо. Очевидно, существуют также связи, заслуживающие дальнейшего исследования, между бар-кодами локальных минимумов и оптимальными значениями коэффициентов скорости обучения, или скоростями сходимости во время обучения.