Журнал вычислительной математики и математической физики, 2021, T. 61, № 5, стр. 691-695

1. МАЛОПАРАМЕТРИЧЕСКИЕ ПРЕДСТАВЛЕНИЯ И ПРИБЛИЖЕНИЯ

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

Анализ существующих приложений показывает, что малопараметрические приближения для матриц больших размеров основаны главным образом на том, что эти матрицы оказываются близкими к матрицам малого ранга. Недавний цикл работ (см. [1]–[3]) можно интерпретировать как попытку осмысления этого весьма общего явления.

Интерес к эффективным алгоритмам представления или приближения матриц матрицами малого ранга с использованием всех или лишь небольшого числа элементов не ослабевает вот уже более 30 лет. Среди разных подходов заметное место занимают крестовые приближения, которые строятся по небольшому числу столбцов и строк матрицы. Пусть $m \times n$-матрица

является суммой матрицы $R$ ранга $r$ и матрицы возмущения $F$, которое по спектральной норме не превосходит $\varepsilon $. В [4], [5] было показано, что если столбцы $m \times r$-матрицы $C$ и строки $r \times n$-матрицы $R$ выбраны из $A$ таким образом, что $r \times r$-подматрица $\hat {A}$ на их пересечении имеет наибольший объем (модуль определителя) среди всех подматриц порядка $r$, то выполняется неравенство где ${{\left\| {\, \cdot \,} \right\|}_{C}}$ – поэлементная (чебышёвская) норма, а ${{\sigma }_{{r + 1}}}(A)$ – сингулярное число матрицы $A$, которое при их упорядочивании по невозрастанию от старшего к младшему имеет номер $r + 1$. Приближения вида $CGR$ (иногда пишут $CUR$) принято называть крестовыми, так как они строятся по элементам некоторого креста, составленного из столбцов и строк заданной матрицы.

Крестовые методы для получения тензорных разложений в формате тензорного поезда впервые были предложены в [6]. В работе [7] данного номера получены новые оценки TT-рангов приближенных тензоризаций массивов значений некоторых гладких функций.

Достоинство крестовых приближений заключается в том, что для их построения нужно знать лишь малое число элементов матрицы. Но есть и недостаток, связанный непосредственно с оценкой (1): ее прямое использование в матричных нормах приводит к множителям, зависящим от размеров матрицы. Это обстоятельство несколько ограничивало область применения данного подхода в алгоритмах анализа данных. В то же время активно применялись вероятностные методы построения весьма эффективных алгоритмов приближений вида $CGR$ (см. [8]–[10]). Во многих интересных случаях рандомизированные алгоритмы обладали существенно лучшими оценками точности, но в них, однако, требовалось знать все элементы приближаемой матрицы.

Статья [11] в данном номере рассматривает оценки точности крестовых приближений на основе принципа обобщенного максимального объема в среднем. В ней рассматриваются наиболее употребительные матричные нормы, а полученные результаты подтверждают экспериментально наблюдаемый факт, что точность крестового метода сравнима с точностью рандомизированных алгоритмов. Это означает, что крестовый метод сохраняет свое главное преимущество – возможность строить высокоточные приближения на основе весьма лапидарной информации о матрице.

2. ЗАДАЧИ ВОСПОЛНЕНИЯ

Задача восполнения малоранговых матриц отличается от задачи приближения только в способе выбора элементов. Пусть матрица $A \in {{\mathbb{R}}^{{n \times n}}}$ (для упрощения обозначений рассмотрим случай квадратных матриц) допускает представление $A = R + F$ с матрицей $R$ “малого” ранга $r$ и “малым” по норме возмущением $F$. Допустим, что множество известных элементов $A$ мало и “равномерно” распределяется в $A.$ Можно ли восстановить матрицу $A$ по некоторому заданному набору ее элементов?

Первоначальной мотивацией для задачи восполнения матриц послужили приложения, связанные с анализом данных: рекомендательные системы, конкурсы типа “Netflix prize”, совместная фильтрация (сollabrative filtering) и др. К настоящему времени спектр приложений стал практически необозримым. Более того, восполнение матриц малого ранга является замечательным примером вычислительной задачи, решение которой опирается на глубокие теоретические результаты из разных областей математики.

В [12], [13] доказано, что для успешного восполнения число необходимых элементов не может быть меньше $\mathcal{O}\left( {nlogn} \right)$. Этими же авторами доказано, что при необременительных ограничениях $\mathcal{O}(nlo{{g}^{2}}(n))$ элементов достаточно для восполнения. Предложенная конструкция использует идеи релаксации задачи к выпуклой постановке с последующим применением известных методов оптимизации. Алгоритмическая сложность методов выпуклой оптимизации мотивировала дальнейшие исследования по поиску более быстрых вычислительных процедур. В результате появились итерационные алгоритмы SVT (Singular Value Thresholding) (см. [14]) и SVP (Singular Value Projection) (см. [15]). Каждая итерация этих алгоритмов состоит из двух шагов. На первом шаге применяется безусловный градиентный метод, а на втором новое приближение проектируется на многообразие матриц ранга $r$. Практическая применимость этих методов ограничивается только сложностью шага проектирования, который использует сингулярное разложение матриц.

В работе [16], представленной в данном номере, предлагается на каждом шаге проектирования заменить наилучшую проекцию на приближенную, сложность вычисления которой существенно меньше сложности сингулярного разложения. Для этого применяются крестовые приближения на основе принципа максимального объема. Важно заметить, что для SVP-алгоритма высокая точность приближений малого ранга во фробениусовой норме является критически важным свойством, определяющим сходимость метода. В теоретической части работы показано, что свойства сходимости методов изменятся незначительно. В качестве быстрых приближений использовались крестовое приближение на основе принципа обобщенного максимального объема (см. [17]) и вероятностные алгоритмы малоранговых приближений (см. [18]). В вычислительных экспериментах на матрицах порядка $1000$ достигалось ускорение в сотни раз. Особую ценность данной работе дает описание важных деталей программной реализации алгоритма, таких как адаптивный выбор шага в градиентном методе и адаптивная процедура набора ранга. Без них SVP-алгоритм существенно проигрывает как в скорости вычислений, так и в устойчивости.

В приложениях часто есть дополнительная информация о восполняемой малоранговой матрице (см. [19], [20]), которую было бы полезно учесть при разработке методов восполнения. Например, могут быть известны подпространства, в которых лежат линейные оболочки строк и столбцов. Такие задачи называют задачами восполнения со сторонней информацией (side information). Пусть ${{d}_{1}}$ и ${{d}_{2}}$ – размерности подпространств, которые содержат пространства строк и столбцов соответственно (очевидно, что $r \leqslant \min \{ {{d}_{1}},{{d}_{2}}\} $). Будем считать, что базисы пространств задаются матрицами $X \in {{\mathbb{R}}^{{m \times {{d}_{1}}}}}$ и $Y \in {{\mathbb{R}}^{{{{d}_{2}} \times n}}}.$ В этом случае число элементов, необходимое для восстановления, имеет вид $\mathcal{O}\left( {log(N)} \right)$ (см. [21]). Запишем задачу восполнения в виде $A = XWY,$ где $A$ – восполняемая матрица, а $W \in {{\mathbb{R}}^{{{{d}_{1}} \times {{d}_{2}}}}}$ – искомая матрица предсказательной модели. В работе [22] данного номера матрица $W$ представляется в факторизованном виде $W = UV$ с матрицами $U \in {{\mathbb{R}}^{{{{d}_{1}} \times r}}}$ и $V \in {{\mathbb{R}}^{{r \times {{d}_{2}}}}}$, разреженными по строкам и столбцам соответственно. Предложена модификация алгоритма восполнения, учитывающая разреженную структуру факторов. При определенных условиях новый алгоритм позволяет дополнительно снизить требования к числу известных элементов. Последнее является критически важным для приложений, где получение необходимой информации затруднено.

3. МАТРИЧНЫЕ И ТЕНЗОРНЫЕ МЕТОДЫ В МАШИННОМ ОБУЧЕНИИ

Подавляющее большинство современных моделей машинного обучения основано на глубинных искусственных нейросетях, которые представляют собой композицию линейных преобразований и поточечных нелинейных преобразований. Линейные преобразования параметризуются матрицами (“весами”), что дает прямую связь с матричным анализом. В частности, можно использовать методы малоранговой аппроксимации матриц и тензоров для сжатия моделей машинного обучения: по заданным весам строятся их аппроксимации, и возникает новая модель, которая содержит меньшее число параметров, но при этом приближает предыдущую. Даже если точности такой сжатой модели недостаточно, то ее можно дообучить, используя полученные с помощью матричных и/или тензорных разложений представления. Такой подход стал очень популярным. В данном выпуске тематике сжатия посвящена статья [23], в ней предложена идея использования аппроксимации не параметров модели, а промежуточных значений – активаций. Оказывается, что используя скелетное разложение матриц, составленноe из векторов активаций, можно существенно сжать различные модели машинного обучения. Следует отметить, что матричные и тензорные методы сжатия нейросетевых моделей (они называются “факторизационными”) стали отдельным направлением в построении быстрых и компактных моделей машинного обучения и уже используются в коммерческих программных пакетах.

Важным направлением развития матричных и тензорных методов является решение задач оптимизации, где неизвестные естественным образом представляются в виде двумерных или многомерных массивов. Такие оптимизационные задачи не всегда сводятся к классическим, но могут быть решены с использованием специальных оптимизационных методов, где на каждом шаге неободимо использовать эффективные и устойчивые матричные алгоритмы. В частности, подобные постановки возникают в рекомендательных системах, анализе социальных сетей и анализе естественных языков. Иногда даже возникает необходимость по-новому взглянуть на классические алгоритмы матричного анализа с точки зрения методов оптимизации. В данном выпуске этой тематике посвящена статья [22]. В [24] тензорные разложения используются для постановки модели о разделении смесей. Классических тензорных разложений в этом случае оказывается недостаточно, и вводится новое представление. В этом случае задача исследователя состоит в подборе правильного представления, или разработкe новой модели факторизации входного тензора, и решении возникающей задачи оптимизации.

Таким образом, матричные методы активно развиваются, применяются в машинном обучении как для создания новых моделей, так и для сжатия существующих. Устойчивые матричные алгоритмы дают основу для более устойчивых методов машинного обучения (в частности, использование ортогональных матриц позволяет в ряде случаев решить проблему “затухающего градиента”). При этом высокая надежность и скорость существующих матричных и тензорных разложений позволяют успешно использовать их для решения целого ряда многомерных задач. Интересным направлением видится также развитие новых оптимизационных методов для решения задач с ограничениями на свойства неизвестных матриц и тензоров, в том числе, с использованием методов стохастической оптимизации и теории игр.

4. ДРУГИЕ ПРИЛОЖЕНИЯ И ЗАКЛЮЧЕНИЕ

Традиционные применения матричных методов связаны с решением уравнений математической физики. Это могут быть как сложные многомерные уравнения, такие как уравнение Беллмана (тензорный метод для его решения рассмотрен в [31]), так и решение классических задач, например, электростатики многочастичных систем, с существенно более высокой скоростью (см. [32]). Статья [25] данного номера посвящена весьма актуальной проблеме численного решения объемных интегральных уравнений на неравномерных сетках. При дискретизации таких задач возникают плотные матрицы огромных размеров, которые, однако, обладают скрытой структурой – показано, что они допускают приближенную факторизацию в виде произведения разреженных матриц и многоуровневой тёплицевой матрицы. Этот факт позволяет эффективно выполнять умножение матрицы на вектор и применять итерационные методы. В [26] изучаются алгебры, появившиеся в результате исследования различных обобщений специфики тёплицевых матриц.

В целом ряде задач требуется вычисление матричной экспоненты. В статье [27] данного тематического номера рассматриваются некоторые вопросы, связанные с применением подпространств Крылова при вычислении эспоненты от несимметричной матрицы. В [28] предлагается новый алгоритм вычисления собственных векторов несимметричных трехдиагональных матриц. В [29] предлагаются и исследуются новые алгоритмы для решения нелинейной проблемы собственных значений. В [30] дается полезный обзор методов экстраполяции Шэнкса и их приложений к ускорению итерационных процессов.

Методы матричного анализа и прикладной линейной алгебры имеют огромное значение для развития наук и технологий. Они обсуждаются на многочисленных семинарах и являются основной темой некоторых серийных конференций. В России – это, прежде всего, регулярная международная конференция “Матричные методы в математике и приложениях”, которая обычно проводится в Москве на базе Института вычислительной математики им. Г.И. Марчука РАН и Сколковского университета науки и технологий. Часть результатов, представленных в данном тематическом выпуске, были анонсированы в докладах 5-й конференции этой серии, состоявшейся в августе 2019 г.

Авторы этого очерка и одновременно редакторы данного тематического выпуска выражают особую благодарность Сергею Александровичу Матвееву, взявшему на себя основную часть труда по его подготовке.