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

НОВЫЙ ВЫЧИСЛИТЕЛЬНО ПРОСТОЙ МЕТОД ДЛЯ РЕАЛИЗАЦИИ НЕЙРОННЫХ СЕТЕЙ С ЖЕСТКИМИ ОГРАНИЧЕНИЯМИ НА ВЫХОДНЫЕ ДАННЫЕ

А. В. Константинов^1, *, Л. В. Уткин^1, **

¹ Высшая школа технологий искусственного интеллекта, Санкт-Петербургский политехнический университет Петра Великого
Санкт-Петербург, Россия

^* E-mail: andrue.konst@gmail.com
^** E-mail: lev.utkin@gmail.com

Поступила в редакцию 09.08.2023
После доработки 25.09.2023
Принята к публикации 15.10.2023

EDN: XPADWQ
DOI: 10.31857/S2686954323601094

Полный текст (PDF)

Аннотация

Предлагается новый вычислительно простой метод построения нейронных сетей, строго удовлетворяющих ограничениям на выход. Ключевая идея метода заключается в отображении скрытого вектора сети в точку, которая гарантированно находится внутри допустимого множества, определяемого набором выпуклых ограничений. Отображение реализуется дополнительным слоем нейронной сети. Предлагаемый метод обобщается на случай, когда совместные ограничения накладываются на входные и выходные вектора. В рамках предлагаемого метода также реализуется модель проецирования в ограниченное выпуклое множество. Реализованы различные типы ограничений, в том числе линейные и квадратичные ограничения, ограничения равенства и динамические ограничения, а также возможность отображения на границу выпуклого множества. Важной особенностью метода является его вычислительная простота. Сложность прямого прохода предлагаемого слоя нейронной сети с линейными и квадратичными ограничениями равна $O\left( {nm} \right)$ и $O({{n}^{2}}m)$, соответственно, где n – количество переменных, m – число ограничений. Численные эксперименты иллюстрируют метод путем решения задач оптимизации и классификации. Программный код, реализующий метод, находится в открытом доступе.

Ключевые слова: нейронные сети, жесткие ограничения, выпуклое множество, модель проекции, задача оптимизации, классификация

1. ВВЕДЕНИЕ

Нейронные сети можно рассматривать как важный и эффективный инструмент для решения различных задач машинного обучения. Ряд прикладных задач, реализация которых осуществляется с использованием нейронных сетей, требуют, чтобы выход сети был ограничен, т.е. предсказания удовлетворяли заданным ограничениям. Примерами задач, требующих ограничений на значения выхода сети, являются задачи оптимизации с ограничениями, модели, генерирующие изображения или части изображений в заданной области, задачи классификации с ограничениями на вероятности классов и т.д. Наиболее распространенный подход для учета таких ограничений состоит в том, чтобы добавить некоторые дополнительные штрафные слагаемые к функции потерь, чтобы штрафовать нарушения ограничений. Однако это не гарантирует, что ограничения будут выполняться для всех обучающих и новых примеров, так как в этом случае нарушение ограничений только штрафуется, но не устраняется. Поэтому такой подход приводит к так называемым мягким ограничениям [1]. Другой подход заключается в модификации нейронной сети так, чтобы она строго предсказывала в пределах ограниченного выходного пространства. В этом случае ограничения являются жесткими в том смысле, что они выполняются для любого входного примера во время обучения и использования [2].

Хотя многие прикладные задачи требуют жестких ограничений, в настоящее время существует не так много моделей, которые их реализуют. Большинство моделей основано на применении мягких ограничений из-за их простой реализации [3]. Метод, учитывающий жесткие конические ограничения вида $Ax \leqslant 0$, был предложен в работе [2]. Соответствующая модель “помещает” предсказания в допустимую область, используя определенный набор лучей. Серьезным ограничением этого метода является необходимость поиска соответствующих лучей. Если применять этот подход не только к коническим ограничениям, то нужно искать все вершины множества. Однако число вершин может быть чрезвычайно большим. Общий подход к решению задач оптимизации с ограничениями представлен в работе [4]. Он направлен на включение (потенциально невыпуклых) ограничений равенств и неравенств в алгоритмы оптимизации на основе глубокого обучения. Его производительность в значительной степени зависит от процесса обучения и выбранной архитектуры модели. Архитектура нейронной сети с жесткими ограничениями на выходные данные при помощи дополнительного выходного слоя предлагается в [5]. Однако метод рассматривает только линейные ограничения, но главное – это то, что для его реализации необходимо знать все вершины многогранника ограничений, число которых может быть огромным.

Интересный подход к решению задач квадратичной оптимизации с линейными ограничениями был предложен в [6]. Аналогичный подход, который встраивает слой оптимизации в нейронную сеть, предлагается в [7]. В отличие от [6], этот подход расширен на случай произвольной выпуклой функции потерь, включая ее параметры. Согласно [7], операция проекции выходной точки на ограниченную область может быть реализована с использованием дифференцируемого слоя оптимизации, который гарантирует, что выход нейронной сети удовлетворяет ограничениям. Однако эти подходы требуют решения задач выпуклой оптимизации для каждого прямого прохода нейронной сети, что значительно усложняет реализацию подходов. Еще один метод решения задачи оптимизации с линейными ограничениями представлен в [8]. Следует отметить, что метод может потребовать значительных вычислительных ресурсов и времени для решения сложных оптимизационных задач. Более того, он решает задачи оптимизации только с линейными ограничениями. Несколько подходов к решению задач условной оптимизации были предложены в работах [9–11]. Анализ этих подходов можно найти в обзорных статьях [12, 13].

Насколько нам известно, на данный момент нет подхода, позволяющего реализовывать и обучать нейронные сети, выход которых удовлетворяет линейным и квадратичным ограничениям, без решения задачи оптимизации при прямом проходе нейронной сети. Поэтому мы представляем новый вычислительно простой метод, который накладывает жесткие линейные и квадратичные ограничения на выходные значения нейронной сети. Основная идея метода состоит в том, чтобы отобразить вектор латентных параметров нейронной сети в точку, которая гарантированно находится внутри допустимого множества, определяемого набором ограничений. Отображение реализуется специальным дополнительным слоем нейронной сети. Предлагаемый метод просто обобщается на случай, когда ограничения накладываются не только на выходные данные сети, но и на входных данных. Еще одна особенность подхода заключается в том, что метод проекции точки на допустимое множество просто реализуется в рамках предложенного подхода. Важной особенностью предлагаемого метода является его вычислительная простота. Например, вычислительная сложность прямого прохода слоя нейронной сети, реализующего метод, в случае линейных ограничений составляет $O\left( {nm} \right)$, а в случае квадратичных ограничений – $O({{n}^{2}}m)$, где n – количество переменных, m – количество ограничений.

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

Вклад работы можно резюмировать следующим образом:

1. Предложен новый вычислительно простой метод, который накладывает жесткие линейные и квадратичные ограничения на выходные значения нейронной сети.

2. Рассмотрена реализация метода с различными типами ограничений, в том числе линейными и квадратичными ограничениями, ограничениями равенствами, ограничениями, накладываемыми на входные и выходные данные.

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

4. Приведены численные эксперименты, иллюстрирующие предложенный метод. В частности, рассматриваются различные задачи оптимизации и задачи классификации.

Программное обеспечение, реализующее метод может быть найдено на сайте: https:// github.com/andruekonst/ConstraiNet/.

2. ПОСТАНОВКА ЗАДАЧИ И ПРЕДЛАГАЕМЫЙ МЕТОД

Пусть $z \in {{\mathbb{R}}^{d}}$ – входной вектор нейронной сети, а $x \in {{\mathbb{R}}^{n}}$ – выходной вектор (предсказание) сети. Нейронная сеть рассматривается как функция ${{f}_{\theta }}:{{\mathbb{R}}^{d}} \to {{\mathbb{R}}^{n}}$ такая, что $x = {{f}_{\theta }}\left( z \right)$, где $\theta \in \Theta $ – вектор обучаемых параметров.

Пусть $\Omega \subset {{\mathbb{R}}^{n}}$ – выпуклое допустимое множество выходных данных, образованное множеством ограничений в виде $m$ неравенств:

(1)

$\Omega = \left\{ {x\,{\text{|}}\,{{h}_{i}}\left( x \right) \leqslant 0,\;i = 1,...,m} \right\},$

где каждое ограничение ${{h}_{i}}\left( x \right) \leqslant 0$ является выпуклым.

Наша цель – построить нейронную сеть с ограничениями на выходные данные. Другими словами, необходимо построить модель x = ${{f}_{\theta }}(z):{{\mathbb{R}}^{d}} \to \Omega $ и наложить ограничения на $x$ так, что $x \in \Omega $ для любого $z \in {{\mathbb{R}}^{d}}$, т.е.

$\forall z \in {{\mathbb{R}}^{d}}\left( {{{f}_{\theta }}\left( z \right) \in \Omega } \right).$

2.1. Слой нейронной сети с ограничениями для выходных данных

Пусть задана фиксированная точка p внутри выпуклой области $\Omega $, т.е. $p \in \Omega $. Любая точка x из множества $\Omega $ может быть представлена в виде:

$x = p + \alpha \cdot r,$

где $\alpha \geqslant 0$ – параметр масштаба; $r \in {{\mathbb{R}}^{n}}$ – вектор (луч из точки p).

С другой стороны, для любых p, r, существует верхняя граница ${{\bar {\alpha }}_{{p,r}}}$ параметра α, определяемая как

${{\bar {\alpha }}_{{p,r}}} = {\text{max}}\left\{ {\alpha \geqslant 0\,{\text{|}}\,p + \alpha \cdot r \in \Omega } \right\}.$

Причем отрезок $\left[ {p;p + {{{\bar {\alpha }}}_{{p,r}}} \cdot r} \right]$ принадлежит $\Omega $, так как $\Omega $ – выпуклое множество. Смысл определения границы ${{\bar {\alpha }}_{{p,r}}}$ в том, чтобы определить точку пересечения луча $r$ с одним из ограничений.

Зададим слой нейронной сети, отображающий луч $r$ и масштаб $s$ в виде:

${{g}_{p}}\left( {r,s} \right) = p + {{\alpha }_{{p,r}}}\left( s \right) \cdot r,$

где ${{\alpha }_{{p,r}}}\left( s \right)$ – функция параметра слоя s и ${{\bar {\alpha }}_{{p,r}}}$, определяемая как

${{\alpha }_{{p,r}}}\left( s \right) = \sigma \left( s \right) \cdot {{\bar {\alpha }}_{{p,r}}},$

$\sigma \left( s \right):\mathbb{R} \to \left[ {0,1} \right]$ – сигмоидальная функция, т.е. гладкая монотонная функция.

Такой слой гарантированно выполняет ограничения:

$\forall r \in {{\mathbb{R}}^{n}},\quad s \in \mathbb{R}\left( {{{g}_{p}}\left( {r,s} \right) \in \Omega } \right),$

так как отрезок $\left[ {p,p + {{{\bar {\alpha }}}_{{p,r}}} \cdot r} \right]$ принадлежит $\Omega $.

Схема отображения луча r и скаляра $s$ в точку внутри области $\Omega $ представлена на рис. 1. По лучу r, выходящему из точки $p$, находится пересечение с границей области $p + {{\bar {\alpha }}_{{p,r}}} \cdot r$, и затем в результате масштабирования получается точка g.

Рис. 1.

Схема отображения ${{g}_{p}}\left( {r,s} \right)$.

Для системы ограничений достаточно находить верхнюю границу ${{\bar {\alpha }}_{{p,r}}}$, удовлетворяющую каждому из ограничений. Пусть $\bar {\alpha }_{{p,r}}^{{\left( i \right)}}$ – верхняя граница параметра $\alpha $, соответствующая i-му ограничению $\left( {{{h}_{i}}\left( x \right) \leqslant 0} \right)$ системы (1). Тогда верхняя граница всей системы задается так, чтобы $[p,p + {{\bar {\alpha }}_{{p,r}}} \cdot r]$ $ \subseteq $ $ \subseteq $ $[p,p + \bar {\alpha }_{{p,r}}^{{\left( i \right)}} \cdot r]$, т.е.

(2)

${{\bar {\alpha }}_{{p,r}}} = {\text{min}}\{ \bar {\alpha }_{{p,r}}^{{\left( i \right)}}\} _{{i = 1}}^{m}.$

Схема поиска верхней границы ${{\bar {\alpha }}_{{p,r}}}$ при линейных ограничениях изображена на рис. 2.

Рис. 2.

Схема поиска верхней границы ${{\bar {\alpha }}_{{p,r}}}$ пересечения ограничений.

Вычислительная сложность прямого прохода описанного слоя нейронной сети прямо пропорциональна числу ограничений и вычислительной сложности пересечения с одним ограничением.

Утверждение 1. С помощью слоя ${{g}_{p}}\left( {r,s} \right)$ может быть представлен любой вектор $x \in \Omega $. Для любого входа $\left( {r,s} \right)$ выход слоя ${{g}_{p}}\left( {r,s} \right)$ принадлежит множеству $\Omega $.

Доказательство:

1. Любой выходной вектор ${{g}_{p}}\left( {r,s} \right)$ удовлетворяет ограничениям, т.е. $\forall r \in {{\mathbb{R}}^{n}}$, $s \in \mathbb{R}$ выполняется условие ${{g}_{p}}\left( {r,s} \right) \in \Omega $, так как ${{\alpha }_{{p,r}}}\left( s \right) \leqslant \bar {\alpha }_{{p,r}}^{{\left( i \right)}}$, и $[p,p + \bar {\alpha }_{{p,r}}^{{\left( i \right)}} \cdot r] \subset \Omega $. Следовательно, g_p(r, s) ∈ [p, $p + {{\alpha }_{{p,r}}}(s)] \subset \Omega $.

2. Любая точка $x \in \Omega $ может быть представлена с помощью слоя ${{g}_{p}}\left( {r,s} \right)$. Действительно, пусть $r\, = \,x\, - \,p$, $s \to + \infty $. Тогда x = g_p(x – p, $ + \infty )\, = \,p\, + \,1$ · (x – – p) = x, что требовалось доказать.

Чтобы получить модель ${{f}_{\theta }}\left( z \right):{{\mathbb{R}}^{d}} \to \Omega $, требуется подать на вход слоя ${{g}_{p}}\left( {r,s} \right)$ выход основной нейронной сети ${{r}_{\theta }}\left( z \right)$ и ${{s}_{\theta }}\left( z \right)$:

${{f}_{\theta }}\left( z \right) = g\left( {{{r}_{\theta }}\left( z \right),{{s}_{\theta }}\left( z \right)} \right).$

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

2.2. Линейные ограничения

В случае линейных ограничений ${{\bar {\alpha }}_{{p,r}}}$ определяется пересечением луча из точки p в направлении r с набором ограничений. Рассмотрим пересечение с одним линейным ограничением вида $a_{i}^{T}x \leqslant {{b}_{i}}.$ Верхняя граница параметра $\alpha $ определяется решением системы:

(3)

$\left\{ {\begin{array}{*{20}{l}} {x = p + \alpha \cdot r,} \\ {a_{i}^{T}x = {{b}_{i}},} \\ {\alpha \geqslant 0.} \end{array}} \right.$

Следовательно, если решение существует, то верно:

$a_{i}^{T}p + \alpha \cdot a_{i}^{T}r = {{b}_{i}},$

$\bar {\alpha }_{{p,r}}^{{\left( i \right)}} = \frac{{{{b}_{i}} - a_{i}^{T}p}}{{a_{i}^{T}r}}.$

Если $a_{i}^{T}r = 0$ или ${{\bar {\alpha }}_{i}}\left( {p,r} \right) < 0$, то (3) не имеет решения и $\bar {\alpha }_{{p,r}}^{{\left( i \right)}}$ можно положить $ + \infty $. Если задана система неравенств, то верхняя граница определяется с помощью (2).

В случае линейных ограничений вычислительная сложность прямого прохода слоя нейронной̆ сети равна $O\left( {nm} \right)$.

2.3. Квадратичные ограничения

Пусть i-е квадратичное ограничение задано в виде:

$\frac{1}{2}{{x}^{T}}{{P}^{{\left( i \right)}}}x + q_{i}^{T}x \leqslant {{b}_{i}},$

где матрица ${{P}^{{\left( i \right)}}}$ – положительно полуопределенная. Тогда пересечение луча с ограничением задается уравнением:

$\frac{1}{2}{{\left( {p + \alpha \cdot r} \right)}^{T}}{{P}^{{\left( i \right)}}}\left( {p + \alpha \cdot r} \right) + q_{i}^{T}\left( {p + \alpha \cdot r} \right) = {{b}_{i}}.$

В зависимости от коэффициента при α², возможны два случая:

1. Если ${{r}^{T}}{{P}^{{\left( i \right)}}}r = 0$, то уравнение линейное и имеет решение:

$\alpha = - \frac{{q_{i}^{T}p + \frac{1}{2}{{p}^{T}}{{P}^{{\left( i \right)}}}p - {{b}_{i}}}}{{{{p}^{T}}{{P}^{{\left( i \right)}}}r + q_{i}^{T}r}}.$

2. Если ${{r}^{T}}{{P}^{{\left( i \right)}}}r > 0$, то решений два, но рассматриваем только большее положительное, соответствующее движению по направлению луча. Таким решением является:

$\alpha = - \frac{{ - ({{p}^{T}}{{P}^{{\left( i \right)}}}r + q_{i}^{T}r) + \sqrt {D{\text{/}}4} }}{{{{r}^{T}}{{P}^{{\left( i \right)}}}r}},$

$\begin{gathered} \frac{D}{4} = {{({{p}^{T}}{{P}^{{\left( i \right)}}}r + q_{i}^{T}r)}^{2}} - \\ \, - ({{r}^{T}}{{P}^{{\left( i \right)}}}r) \cdot (2q_{i}^{T}p + {{p}^{T}}{{P}^{{\left( i \right)}}}p - 2{{b}_{i}}), \\ \end{gathered} $

так как знаменатель положительный.

Случай ${{r}^{T}}{{P}^{{\left( i \right)}}}r < 0$ невозможен, так как матрица положительно полуопределенная. В противном случае ограничение задавало бы невыпуклое множество.

Если $\alpha \geqslant 0$, то $\bar {\alpha }_{{p,r}}^{{\left( i \right)}} = \alpha $. В противном случае, если луч не пересекает ограничение, то $\bar {\alpha }_{{p,r}}^{{\left( i \right)}} = + \infty $. Для системы квадратичных ограничений верхняя граница имеет вид (2).

В случае квадратичных ограничений вычислительная сложность прямого прохода слоя нейронной сети равна $O({{n}^{2}}m)$.

2.4. Ограничения типа равенств

Рассмотрим случай, когда область $\Omega $ задается системой линейных равенств и неравенств вида:

(4)

$x \in \Omega \Leftrightarrow \left\{ {\begin{array}{*{20}{l}} {Ax \leqslant b,} \\ {Qx = p.} \end{array}} \right.$

В этом случае задача может быть сведена к (1), т.е. к системе неравенств. Для этого найдем и зафиксируем вектор u, удовлетворяющий системе $Qu = p$. Если система не имеет решений, то $\Omega $ пустая. Если существует только одно решение, то $\Omega $ состоит из одной точки. В противном случае решений бесконечное множество и достаточно выбрать любое из них, например, решая задачу наименьших квадратов:

${\text{||}}Qu - p{\text{|}}{{{\text{|}}}^{2}} \to {\text{min}}.$

Затем можно найти матрицу $R$, которая является базисом ядра Q, т.е. $R$ удовлетворяет условию:

$\forall w\left( {QRw = 0} \right).$

Матрица $R$ может быть получена при помощи SVD-разложения матрицы $Q \in {{\mathbb{R}}^{{\mu \times n}}}$:

$USV = Q,$

где $U \in {{\mathbb{R}}^{{\mu \times \mu }}}$ и $V \in {{\mathbb{R}}^{{n \times n}}}$ – ортогональные матрицы, $S \in {{\mathbb{R}}^{{\mu \times n}}}$ – матрица с ненулевыми значениями только на диагонали, отсортированными по убыванию.

Тогда матрица $R$ задается как

$R = \left( {{{v}_{1}}, \ldots ,{{v}_{\delta }}} \right),$

где $\delta $ – число ненулевых диагональных элементов матрицы S, ${{v}_{1}}, \ldots ,{{v}_{\delta }}$ – столбцы матрицы $V$.

Отсюда

$\forall w \in {{\mathbb{R}}^{\delta }}\left( {Q\left( {Rw + u} \right) = p} \right).$

Новая система ограничений на вектор $w$ определяется как

$A\left( {Rw + u} \right) \leqslant b,$

или в канонической форме

(5)

$Bw \leqslant t,$

где $B = AR$, $t = b - Au$.

Таким образом, w – вектор переменных для новой системы (4). Для любого w, вектор x, удовлетворяющий исходной системе, может быть восстановлен в виде $x = Rw + u$. В итоге модель решения будет задаваться как:

(6)

${{f}_{\theta }}\left( z \right) = R{{\tilde {f}}_{\theta }}\left( z \right) + u,$

где ${{\tilde {f}}_{\theta }}\left( z \right)$ – модель для ограничений (5).

В более общем случае, если задано произвольное выпуклое множество $\Omega $, как пересечение выпуклых ограничений типа неравенств (1), и одно дополнительное ограничение равенство:

$x \in \Omega \Leftrightarrow \left\{ {\begin{array}{*{20}{l}} {{{h}_{i}}\left( x \right) \leqslant 0,} \\ {Qx = p,} \end{array}} \right.$

то можно применить замену переменных для получения новых (возможно нелинейных) ограничений:

$x \in \Omega \Leftrightarrow \left\{ {\begin{array}{*{20}{l}} {{{h}_{i}}\left( {Rw + u} \right) \leqslant 0,} \\ {x = Rw + u,} \end{array}} \right. \Leftrightarrow \left\{ {\begin{array}{*{20}{l}} {\tilde {h}_{i}^{{\left( {R,u} \right)}}\left( w \right) \leqslant 0,} \\ {x = Rw + u.} \end{array}} \right.$

Таким образом, модель может использоваться для генерации решений ${{\tilde {f}}_{\theta }}\left( z \right)$, удовлетворяющих нелинейным ограничениям $\tilde {h}_{i}^{{\left( {R,u} \right)}}\left( {{{{\tilde {f}}}_{\theta }}\left( z \right)} \right)$, и затем решения для x получаются через (6).

2.5. Ограничения на входные и выходные данные

На практике может потребоваться задавать ограничения не только на выходной вектор ${{f}_{\theta }}\left( z \right)$, но и совместные ограничения, зависящие от некоторых входных векторов. Пусть задана выпуклая область ограничений на входной вектор z и выходной вектор ${{f}_{\theta }}\left( z \right)$:

$\Lambda \subset {{\mathbb{R}}^{k}} \times {{\mathbb{R}}^{n}},$

т.е. для любого z, модель ${{f}_{\theta }}\left( z \right)$ должна удовлетворять условию:

$y = \left[ {\begin{array}{*{20}{c}} {{{f}_{\theta }}\left( z \right)} \\ z \end{array}} \right] \in \Lambda .$

Здесь y – конкатенация векторов ${{f}_{\theta }}\left( z \right)$ и $z$. Если область задана в виде пересечения выпуклых ограничений:

$\Lambda = \left\{ {y\,{\text{|}}\,{{\Gamma }_{i}}\left( y \right) \leqslant 0,\;i = 1, \ldots ,m} \right\},$

то для фиксированного z путем подстановки может быть построена новая система ограничений исключительно на выходной вектор ${{f}_{\theta }}\left( z \right)$:

$G\left( z \right) = \left\{ {z\,{\text{|}}\,{{\gamma }_{i}}\left( {x;z} \right) \leqslant 0,\;i = 1,...,m} \right\},$

где ${{\gamma }_{i}}\left( {x;z} \right)$ получены путем подстановки z в ${{\Gamma }_{i}}$.

Здесь ${{\gamma }_{i}}$ зависит от z как от фиксированных параметров, а переменной является только $x$. Например, если ${{\Gamma }_{i}}$ – линейная функция, то после подстановки параметров ${{\gamma }_{i}}\left( {x;z} \right) \leqslant 0$ будет новым линейным ограничением на x, либо автоматически выполняться. Если ${{\Gamma }_{i}}$ – квадратичная функция, то ограничение на $x$ будет либо квадратичным, либо линейным, либо автоматически выполняться.

Новые динамические ограничения на выходные данные, зависящие от входного вектора $z$, удовлетворяют условию

${{f}_{\theta }}\left( z \right) \in G\left( z \right),$

при условии, что входной вектор $z$ из допустимого множества:

$z \in \left\{ {z\,{\text{|}}\,\exists x:\left[ {\begin{array}{*{20}{c}} x \\ z \end{array}} \right] \in \Lambda } \right\}.$

Такие ограничения могут изменяться с изменением $z$, и могут быть реализованы в нейронной сети при условии существования фиксированной точки $p$.

2.6. Модель проекции

Заметим, что с помощью предложенного слоя нейронной сети с ограничениями на выходные данные может быть построена модель проекции, отображающая точки в $\Omega $ и обладающая свойством идемпотентности, т.е.

$\forall x \in {{\mathbb{R}}^{n}}\left( {{{f}_{\theta }}\left( {{{f}_{\theta }}\left( x \right)} \right) = {{f}_{\theta }}\left( x \right)} \right).$

Такая модель может быть реализована двумя способами:

1. Первый способ – обучение модели f_θ(z) = = $g({{r}_{\theta }}(z),{{s}_{\theta }}(s))$ тождественному преобразованию с помощью минимизации функционала, штрафующего расстояние между образом и прообразом, например, для ортогональной проекции в L_p-норме

(7)

$\mathcal{L} = \frac{1}{N}\mathop \sum \limits_{i = 1}^N {\text{||}}{{f}_{\theta }}\left( {{{x}_{i}}} \right) - {{x}_{i}}{\text{|}}{{{\text{|}}}_{p}}.$

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

2. Второй способ – центральная проекция, которая может быть получена без оптимизации модели, за счет задания луча ${{r}_{\theta }}\left( z \right): = z - p$. В этом случае масштаб должен быть задан без сигмоиды в явном виде, как: ${{\alpha }_{{p,r}}}\left( s \right) = {\text{min}}\left\{ {1,{{{\bar {\alpha }}}_{{p,r}}}} \right\}$. Тогда

$\begin{gathered} {{{\tilde {g}}}_{p}}\left( {r\left( x \right)} \right) = p + {\text{min}}\left\{ {1,{{{\bar {\alpha }}}_{{p,\left( {x - p} \right)}}}} \right\} \cdot \left( {x - p} \right) = \\ \, = \left\{ \begin{gathered} x,\quad {{{\bar {\alpha }}}_{{p,\left( {x - p} \right)}}} \geqslant 1, \hfill \\ \left( {1 - {{{\bar {\alpha }}}_{{p,\left( {x - p} \right)}}}} \right)p + {{{\bar {\alpha }}}_{{p,\left( {x - p} \right)}}}x,\quad {\text{иначе}}{\text{.}} \hfill \\ \end{gathered} \right. \\ \end{gathered} $

Примеры реализации модели проекции для квадратичных ограничений приведены на рис. 3. Для каждого из вариантов приведено векторное поле, где начало каждой стрелки соответствует прообразу, а конец – его проекции в множество из 5 ограничений. Слева приведен результат нейронной сети, параметры которой минимизируют (7), где в $\Omega $ имеются артефакты, соответствующие областям с большими ошибками аппроксимации. Справа приведен результат нейронной сети без обучаемых параметров, реализующей центральную проекцию, где нет ошибок.

Рис. 3.

Примеры моделей проекции для квадратичных ограничений.

2.7. Построение решений на границе

Разработанный метод может быть также применен для построения решений в невыпуклом граничном множестве, обозначенном $\partial \Omega $. Для этого положим $\sigma \left( s \right) = 1$. Тогда

$g\left( r \right) = p + \bar {\alpha }\left( {p,r} \right) \cdot r \in \partial \Omega .$

Отсюда следует, что g(r) находится на границе при $r \ne 0$.

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

(8)

$\begin{array}{*{20}{c}} {{\text{min||}}z - {{f}_{\theta }}\left( z \right){\text{|}}{{{\text{|}}}_{p}}} \\ {{\text{при}}\;{\text{ограничениях}}\;{{f}_{\theta }}\left( z \right) \in \partial \Omega .} \end{array}$

Примеры проецирования на область, заданную набором линейных ограничений, для L₁- и L₂-норм приведены на рис. 4. Для решения каждой из задач обучена нейронная сеть, содержащая 5 слоев размера 100, минимизирующая (8), множество значений которой задано как $\partial \Omega $. Из рис. 6 видно, что генерируемые точки находятся на границе ограничений.

Рис. 4.

Примеры аппроксимации проекции на границу с использованием L₁- и L₂-norm.

Рис. 5.

Сравнение времени работы предлагаемой нейронной сети и проецирования с помощью CVXPYLayers.

Рис. 6.

Траектории оптимизации для функций Розенброка [15] и Bird [16].

3. ЭКСПЕРИМЕНТЫ

3.1. Задачи оптимизации

Одно из применений предлагаемого подхода – решение задач оптимизации с ограничениями. Для каждой частной задачи оптимизируется вектор входных параметров $~{{z}_{i}}$ так, чтобы минимизировать функцию потерь $~{{l}_{i}}\left( {{{f}_{\theta }}\left( {{{z}_{i}}} \right)} \right)$. Для тестирования были сгенерированы по 50 наборов задач и ограничений для выходной размерности 2, 5 и 10, с 50, 100 и 200 ограничениями отдельно для случаев линейных и квадратичных ограничений, так, чтобы область $\Omega $ была ограничена.

Для линейных ограничений генерировались $m$ векторов ${{a}_{1}}, \ldots ,{{a}_{m}} \sim \mathcal{N}\left( {0,I} \right)$, задающих точки, принадлежащие гиперплоскостям, и нормали к этим гиперплоскостям. Тогда ${{b}_{i}} = a_{i}^{T}{{a}_{i}},$ и Ω = = $\{ x\,{\text{|}}\,a_{i}^{T}x \leqslant {{b}_{i}},\;i = 1,...,m\} $. Для квадратичных ограничений генерировались положительно полуопределенные матрицы ${{P}^{{\left( i \right)}}}$ и векторы ${{q}_{i}}\, \sim \,\mathcal{N}(0,I)$, $i = 1, \ldots ,m$. Затем ограничения смещались так, чтобы удовлетворять ограничениям с зазором ${{b}_{i}} > 0$. В итоге получаем систему квадратичных ограничений Ω = $\{ x\,{\text{|}}\,{{x}^{T}}{{P}^{{\left( i \right)}}}x + q_{i}^{T}x \leqslant {{b}_{i}},\;i = 1, \ldots ,m\} .$

Относительная ошибка для сравнения моделей вычисляется по значению функции потерь полученного решения ${{l}_{i}}\left( {{{f}_{\theta }}\left( {{{x}_{i}}} \right)} \right)$ относительно функции потерь эталонного решения ${{l}_{i}}(x_{i}^{{\text{*}}})$:

$RE = \frac{{{\text{max\{ }}0,{{l}_{i}}\left( {{{f}_{\theta }}\left( {{{x}_{i}}} \right)} \right) - {{l}_{i}}(x_{i}^{*}){\text{\} }}}}{{{\text{|}}{{l}_{i}}(x_{i}^{*}){\text{|}}}} \cdot 100{\text{\% }}.$

Эталонные решения были получены с помощью алгоритма OSQP [14], предназначенного исключительно для решения линейных и квадратичных задач.

В табл. 1 приведены средние относительные ошибки для задач оптимизации с линейными (LL) и квадратичными (QL) функциями потерь, а также линейными (LC) и квадратичными (QС) ограничениями. Из таблицы видно, что метод позволяет оптимизировать входные параметры r и $s$s для предлагаемого слоя. Видно, что этот слой не ухудшает градиент для всей нейронной сети.

Таблица 1.

RE для задач с различными функциями потерь и ограничениями

m	n	LL–LC	LL–QC	QL–LC	QL–QC
	2	3.6 × 10^–5	1.3 × 10^–4	3.9 × 10^–5	7.1 × 10^–6
50	5	2.4 × 10^–3	7.7 × 10^–5	1.2 × 10^–3	4.9 × 10^–4
	10	1.4 × 10^–2	4.3 × 10^–6	6.9 × 10^–3	3.5 × 10^–3
	2	2.6 × 10^–5	1.6 × 10^–4	5.4 × 10^–5	6.0 × 10^–6
100	5	2.1 × 10^–3	8.1 × 10^–4	1.6 × 10^–3	8.9 × 10^–4
	10	1.1 × 10^–2	1.3 × 10^–5	8.0 × 10^–3	4.3 × 10^–3
	2	1.5 × 10^–5	3.1 × 10^–4	5.0 × 10^–5	1.2 × 10^–5
200	5	2.6 × 10^–3	1.1 × 10^–3	1.3 × 10^–3	5.9 × 10^–4
	10	1.2 × 10^–2	2.8 × 10^–4	7.7 × 10^–3	4.9 × 10^–3

Для сравнения с нейронной сетью была выбрана библиотека CVXPYLayers [7], позволяющая задавать дифференцируемые слои оптимизации внутри нейронной сети. На рис. 5 приведено сравнение времени выполнения оптимизации при одинаковых гиперпараметрах, при условии, что после 5 мин с начала оптимизации, алгоритм CVXPYLayers останавливался, даже если оптимизация не была завершена. Как видно из рисунка, предложенный алгоритм требует значительно меньших затрат с точки зрения производительности.

Структура нейронной сети позволяет реализовать алгоритмы решения произвольных задач как выпуклой, так и невыпуклой оптимизации. На рис. 6 представлены траектории оптимизации для функции Розенброка [15] с квадратичными ограничениями:

${{\mathcal{L}}_{{Ros}}}\left( x \right) = (1 - x_{1}^{2}) + 100{{({{x}_{2}} - x_{1}^{2})}^{2}},$

${{\Omega }_{{Ros}}} = \left\{ {x\,{\text{|}}\,x_{1}^{2} + x_{2}^{2} \leqslant 2} \right\},$

и функции Bird [16], которая имеет 4 локальных минимума в ${{\Omega }_{{Bird}}}$, два из которых лежат на границе ${{\Omega }_{{Bird}}}$:

$\begin{gathered} {{\mathcal{L}}_{{Bird}}}\left( x \right) = \sin \left( {{{x}_{2}}} \right){{e}^{{{{{\left( {1 - \cos \left( {{{x}_{1}}} \right)} \right)}}^{2}}}}} + \\ \, + \cos \left( {{{x}_{1}}} \right){{e}^{{{{{\left( {1 - \sin \left( {{{x}_{2}}} \right)} \right)}}^{2}}}}} + {{\left( {{{x}_{1}} - {{x}_{2}}} \right)}^{2}}, \\ \end{gathered} $

${{\Omega }_{{Bird}}} = \{ x\,{\text{|}}\,{{\left( {{{x}_{1}} + 5} \right)}^{2}} + {{\left( {{{x}_{2}} + 5} \right)}^{2}} < 25\} .$

Функция ${{\mathcal{L}}_{{Ros}}}\left( x \right)$ имеет глобальный минимум в точке (1, 1). Границы для ${{\Omega }_{{Ros}}}$ и ${{\Omega }_{{Bird}}}~$показаны большими черными окружностями. Использовались 2000 итераций алгоритма Adam со скоростью обучения 0.1. 9 точек на равномерной сетке от –0.75 до 0.75 выбраны как начальные точки, для которых траектории оптимизации показаны на рис. 6, где конечная точка обозначена белой звездой.

3.2. Пример классификации

Для иллюстрации возможности предлагаемого метода рассмотрена задача классификации на примере простейшего набора данных “Iris” с ограничениями на верхние границы ${{\bar {p}}_{i}}$ для каждой вероятности класса ${{x}_{i}}$:

${{f}_{\theta }}\left( z \right) \in \left\{ {x\,{\text{|}}\,0 \leqslant {{x}_{i}} \leqslant {{{\bar {p}}}_{i}},{{{\mathbf{1}}}^{T}}x = 1} \right\}.$

Эти ограничения могут играть уравновешивающую роль в обучении, уменьшая влияние уже правильно классифицированных точек на функцию потерь. Чтобы проиллюстрировать, как нейронная сеть обучается с этими ограничениями, и упростить визуализацию результатов, выбран именно этот классический набор данных, содержащий 3 класса и 150 примеров. Три класса позволяют визуализировать результаты с помощью единичного симплекса вероятностей. В этом примере мы устанавливаем верхние границы ${{\bar {p}}_{i}}$ = 0.75 для i = 1, 2, 3. На рис. 7 показаны единичные симплексы и точки, которые являются выходными данными нейронной сети, обученной на 100, 500 и 1000 эпохах. Нейронная сеть состоит из 5 слоев размером 64. Цвета точек обозначают соответствующие классы (Setosa, Versicolor, Virginica). Из рис. 7 видно, что ограничения влияют не только при очень близком расположении выходных точек к ним, но и на всем протяжении обучения сети.

Рис. 7.

Вероятности классов при различном числе (100, 500, 1000) эпох обучения.

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

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

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

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

Список литературы

Marquez-Neila P., Salzmann M., Fua P. Imposing Hard Constraints on Deep Networks: Promises and Limitations. CVPR Workshop on Negative Results in Computer Vision. 2017. P. 1–9.
Frerix T., Niessner M., Cremers D. Homogeneous Linear Inequality Constraints for Neural Network Activations. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. 2020. P. 748–49.
Lee J.Y., Mehta S.V., Wick M., Tristan J.-B., Carbonell J. Gradient-Based Inference for Networks with Output Constraints. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI-19). 2019. V. 33. P. 4147–54.
Donti P.L., Rolnick D., Kolter J.Z. DC3: A Learning Method for Optimization with Hard Constraints. International Conference on Learning Representations (ICLR 2021). 2021. P. 1–17.
Brosowsky M., Keck F., Dunkel O., Zollner M. Sample-Specific Output Constraints for Neural Networks. The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21). 2021. P. 6812–21.
Amos B., Kolter J.Z. Optnet: Differentiable Optimization as a Layer in Neural Networks. International Conference on Machine Learning. PMLR, 2017. P. 136–145.
Agrawal A., Amos B., Barratt S., Boyd S., Diamond S., Kolter J.Z. Differentiable Convex Optimization Layers. Advances in Neural Information Processing Systems. 2019. V. 32. P. 1–13.
Li M., Kolouri S., Mohammadi J. Learning to Solve Optimization Problems with Hard Linear Constraints. IEEE Access. 2023. V. 11. P. 59995–60004.
Balestriero R., LeCun Y. Police: Provably Optimal Linear Constraint Enforcement for Deep Neural Networks. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE. 2023. P. 1–5.
Chen Y., Huang D., Zhang D., Zeng J., Wang N., Zhang H., Yan J. Theory-Guided Hard Constraint Projection (HCP): A Knowledge-Based Data-Driven Scientific Machine Learning Method. Journal of Computational Physics. 2021. V. 445 (110624).
Negiar G., Mahoney M.W., Krishnapriyan A. Learning Differentiable Solvers for Systems with Hard Constraints. The Eleventh International Conference on Learning Representations (ICLR 2023). 2023. P. 1–19.
Kotary J., Fioretto F., Van Hentenryck P. Learning Hard Optimization Problems: A Data Generation Perspective. 35th Conference on Neural Information Processing Systems (NeurIPS 2021). 2021. V. 34. P. 24981–24992.
Kotary J., Fioretto F., Van Hentenryck P., Wilder B. End-to-End Constrained Optimization Learning: A Survey. Proceedings of the Thirtieth International Joint Con-ference on Artificial Intelligence (IJCAI-21). 2021. P. 4475–82.
Stellato B., Banjac G., Goulart P., Bemporad A., Boyd S. OSQP: An Operator Splitting Solver for Quadratic Programs. Mathematical Programming Computation. 2020. V. 12. № 4. P. 637–72.
Rosenbrock H.H. An Automatic Method for Finding the Greatest or Least Value of a Function. The Computer Journal. 1960. V. 3. № 3. P. 175–84.
Mishra S.K. Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method. Available at SSRN 926132. 2006. P. 1–24.
Raissi M., Perdikaris P., Karniadakis G.E. Physics-Informed Neural Networks: A Deep Learning Framework for Solving Forward and Inverse Problems Involving Nonlinear Partial Differential Equations. Journal of Computational Physics 2019. V. 378. P. 686–707.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал