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

1. ВВЕДЕНИЕ

Методы пополнения или восстановления матриц, matrix completion, находят широкое примение в рекомендательных системах [1], [2], задачах кластеризации [3], классификации с многими метками [4], [5], обработки сигналов [6], компьютерного зрения [7] и подобных. В традиционной постановке частично наблюдаемая низкоранговая матрица восстанавливается напрямую через скалярное произведение выученных строчных и колоночных факторов, или неявно с использованием ядерных методов (kernel trick). При этом каждый фактор является численным отражением признаков некоей сущности, связанной с той или иной строкой или столбцом. Теоретические основания, определяющие возможность восстановления низкоранговых матриц, рассмотрены в работах [8] и [9]. Например, в условиях независимого случайного наблюдения достаточно иметь доступ к $O(Nlo{{g}^{2}}N)$ элементам матрицы низкого ранга ${{n}_{1}} \times {{n}_{2}}$ для полного точного ее восстановления ($N = max{\text{\{ }}{{n}_{1}},{{n}_{2}}{\text{\} }}$). Оценка, не зависящая от распределения, приведенная в [10], позволяет достичь полного восстановления матриц, имея $O({{N}^{{3/2}}})$ наблюдения.

Зачастую в дополнение к элементам самой частично наблюдаемой матрицы доступны вспомогательные экзогенные характеристики сущностей, стоящих за ее строками и столбцами. Например, в [11] показано, что побочные признаки строк и столбцов в виде профилей пользователей или описания жанров кино, side-channel information, полезны в задаче рекомендательной системы. Подобная вспомогательная информация играет особо важную роль при решении проблемы “холодного старта” рекомендательной системы, так как в ситуации, когда необходимо предсказать “взаимодействие” наблюдавшихся ранее сущностей с новой доселе ненаблюдавшейся сущностью, единственной возможностью остается только делать выводы на основе побочных характеристик.

Подходы, тем или иными способом учитывающие побочные признаки при пополнении матрицы, носят название индуктивного восстановления матриц, inductive matrix completion (IMC), см. в том числе [12]–[18]. Ключевой теоретический результат, полученный на момент написания настоящей работы, заключается в том, что достаточный объем наблюдений для восстановления снижается до $O(logN)$ при условии, что побочные признаки имеют “хорошую” предсказательную силу. При этом вполне естественна ситуация, когда не все признаки релевантны или имеют хорошую предсказательную силу. Таким образом, становится очевидной необходимость разработки алгоритмов IMC, работающих в условиях избыточности побочных признаков и при этом сохраняющих гарантии по асимптотике достаточного объема наблюдений для восстановления. Немногие исследования обращаются к теме развития методов индуктивного восстановления матриц с отбором побочных признаков (прореживания), [16], [19] при том, что потенциал модификаций и улучшений существующих алгоритмов восстановления матриц в этом направлений велик.

Систематическое исследование проблемы индуктивного восстановления матриц началось с работы [12], в которой показано, что для полного восстановления достаточно наблюдать $O(logN)$ случайных элементов при условии использования нормы ${{\left\| M \right\|}_{ * }} = \sum\nolimits_i {{{\sigma }_{i}}} (M)$ сингулярных чисел ${{\sigma }_{i}}(M)$ матрицы $M$ в качестве регуляризатора, также известной как ядерная норма. В [20] рассмотрено представление матрицы в виде низкорангового произведения факторов и побочных признаков и изучена итеративная покоординатная процедура, возникающая в данной параметризации задачи. Предложенная параметризация нивелирует необходимость сингулярного разложения матрицы на каждой итерации, заменяя ее попеременным решением квадратичной задачи для каждого фактора. В [18] рассмотрены невыпуклый регуляризатор на факторы и 3-х фазная итеративная процедура восстановления, завершающаяся фазой проективного градиентного спуска, которая гарантирует, что вычисленные факторы находятся в окрестности оптимального решения задачи с высокой вероятностью по наблюдаемым выборкам.

В [14] рассматривается ситуация с несовершенными побочными признаками, которые не имеют достаточной предсказательной силы для полного восстановления матрицы, и, совместив индуктивный и классический подходы к восстановлению матриц, добиваются состоятельного восстановления матриц также и в случае “совершенных” побочных признаков. В [16] рассматривается аналогичная ситуация, где используется разреживающий регуляризатор на основе нормы сингулярных чисел целевой матрицы, приводя также оценки достаточного числа наблюдаемых элементов для восстановления. Однако в работе не исследуется эффект отбора признаков на получаемое решение, и предложенная процедура имеет высокую сложность по памяти и арифметическую сложность. В [19] рассматривается комбинаторная постановка задачи индуктивного восстановления матриц с отбором признаков, и приводится оценка ускоренной асимптотики достаточного объема наблюдений при наличии шума. В аналогичной постановке индуктивного восстановления ребер в графах в [21] получены минимакс оптимальные оценки достаточного объема наблюдений в режимах низкоранговой матрицы связности и избыточности побочных признаков, а также исследован баланс между вероятностью точного восстановления и вычислительной сложностью.

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

Мы также предлагаем итеративную процедуру для численного решения предложенной невыпуклой оптимизационной задачи разреженного IMC, основанную на алгоритме ADMM [22], [23]. Приводимые нами экспериментальные свидетельства, демонстрируют, что предложенная процедура восстанавливает матрицу одновременно с отбором малоинформативных побочных признаков как на синтетических примерах, так и в наборах данных из практических приложений, при этом достигая показателей качества, сравнимых с алгоритмическими аналогами без прореживания. Реализация процедуры (https://github.com/premolab/SGIMC) позволяет индуктивно восстанавливать частично наблюдаемые матрицы больших размеров.

Изложение результатов начинается с постановки оптимизационной задачи для восстановления матриц с прореживающим регуляризатором в разд. 2. В разд. 3 приводятся оценки обобщающей способности предложенного метода и достаточного объема наблюдений для восстановления, а в разд. 4 приведена предложенная нами итеративная процедура. Затем в разд. 5 приводятся и обсуждаются полученные экспериментальные свидетельства. Изложение завершается разд. 6.

2. ПОСТАНОВКА ЗАДАЧИ ВОССТАНОВЛЕНИЯ МАТРИЦ С ПРОРЕЖИВАНИЕМ

Рассмотрим целевую матрицу $M \in {{\mathbb{R}}^{{{{n}_{1}} \times {{n}_{2}}}}}$, в которой наблюдаемы только значения ${{M}_{{ij}}}$ и некоторого множества $(i,j) \in \Omega \subset {\text{\{ }}1,\; \ldots ,\;{{n}_{1}}{\text{\} }} \times {\text{\{ }}1,\; \ldots ,\;{{n}_{2}}{\text{\} }}$. Предположим, что побочные признаки полностью наблюдаемы и представлены в виде матриц $X \in {{\mathbb{R}}^{{{{n}_{1}} \times {{d}_{1}}}}}$ и $Y \in {{\mathbb{R}}^{{{{n}_{2}} \times {{d}_{2}}}}}$ для строк и столбцов $M$ соответственно. Также допустим, что побочная информация имеет предсказательную силу применительно к значениям в $M$ через билинейную модель

для некоторой матрицы весов $W \in {{\mathbb{R}}^{{{{d}_{1}} \times {{d}_{2}}}}}$. Целью задачи индуктивного восстановления матрицы является оценка ненаблюдаемых элементов $M$ на основе наблюдаемых ${{M}_{\Omega }}$ и побочной строчных $X$ и столбцовых $Y$ характеристик.

Главенствующим допущением в подходах к решению задачи IMC является предположение о том, что матрица $W$ имеет низкий ранг $k < min({{d}_{1}},{{d}_{2}})$, см. [12], [14]. При этом существуют два подхода к учету данного ограничения в итоговой оптимизационной задаче.

Подход 1. Использование ${{\ell }_{1}}$ нормы сингулярных чисел матрицы $W$, ядерная норма ${{\left\| W \right\|}_{ * }}$, в качестве разреживающего регуляризатора, приводящего к низкоранговым решениям ${{\left\| W \right\|}_{ * }}$, см. [12], [14], [16].

Подход 2. Явная параметризация $W$ в виде низкорангового произведения $U{{V}^{{\text{т}}}}$, где $U \in {{\mathbb{R}}^{{{{d}_{1}} \times k}}}$ и $V \in {{\mathbb{R}}^{{{{d}_{2}} \times k}}}$, см. [18], [20].

Мы сосредотачиваемся на втором подходе, поскольку он позволяет работать с матрицей весов $W$ неявно через ее факторы, что упрощает отбор признаков в задачах с большими объемами данных (${{d}_{1}},{{d}_{2}} \gg 1$).

Предположим, что $\mathcal{L}:\mathbb{R} \times \mathbb{R} \to \mathbb{R}$ является гладкой выпуклой функцией потерь в задаче машинного обучения, и рассмотрим следующую регуляризованную задачу минимизации:

где $R({\kern 1pt} \cdot {\kern 1pt} )$ – регуляризатор, и ${{\lambda }_{U}},{{\lambda }_{V}} \geqslant 0$. Обычно в задачах восстановления матриц роль $R$ играет квадрат нормы Фробениуса [14], которая имеет вид для некоторой матрицы $Z \in {{\mathbb{R}}^{{d \times k}}}$. В задаче линейной регрессии данная $R$ эквивалентна регуляризации Тихонова. В настоящей работе мы предлагаем использовать прореживающий регуляризатор $R(Z)$ вида где через ${{e}_{i}}$ обозначается $i$-й единичный базисный вектор, чья размерность однозначна определяется контекстом выражения, в котором он участвует. Матричная функция $R(Z)$ вычисляет ${{\ell }_{1}}$ норму вектора ${{\ell }_{2}}$ норм строк $Z$. Подобный составной регуляризатор позволяет построчно прореживать матрицы $U$ и $V$, т.е. наводит так называемую групповую разреженность, что в общем итоге создает эффект отбора побочных признаков в $X$ и $Y$ соответственно. Таким образом, задача индуктивного восстановления матриц с отбором признаков через групповую регуляризацию, Sparse-Group penalty Inductive Matrix Completion (SGIMC), имеет вид Заметим, что численная процедура, приведенная в разд. 6, позволяет работать с комбинацией регуляризаторов. В частности, мы рассматриваем квадрат нормы Фробениуса $R(Z) = \left\| Z \right\|_{{\text{F}}}^{2}$, а также поэлементную матричную ${{L}_{1}}$-норму $R(Z) = {{\left\| Z \right\|}_{{1,1}}} = \sum\nolimits_{i = 1}^n {\sum\nolimits_{j = 1}^d {\left| {{{z}_{{ij}}}} \right|} } $ для большего контроля над разреженностью итогового решения.

3. АНАЛИЗ АСИМПТОТИКИ ОШИБКИ ВОССТАНОВЛЕНИЯ

В данном разделе приводится анализ влияния отбора признаков на точность восстановления матриц.

Задачу индуктивного восстановления матрицы можно рассмотреть через призму машинного обучения с учителем. Действительно, наблюдаемые значения в разреженной матрице ${{M}_{\Omega }}$ можно рассматривать как случайную выборку значений неизвестной ненаблюдаемой матрицы $W{\text{*}}$, полученной с использованием линейных измерений, построенных на побочных признаках $X$ и $Y$. Таким образом, набор данных $(X,Y,{{M}_{\Omega }})$ представляется в виде выборки $S = ({{x}_{t}},{{y}_{t}},{{b}_{t}})_{{t = 1}}^{m}$ размера $m = \left| \Omega \right|$ при фиксированном обходе индексов из $\Omega $. Каждое значение ${{b}_{t}}$ в $S$ является результатом применения измерительного оператора ${{A}_{t}}$ к $W{\text{*}}$, который задан одноранговой матрицей ${{A}_{t}} = {{x}_{t}}y_{t}^{{\text{т}}}$ размера ${{d}_{1}} \times {{d}_{2}}$: ${{b}_{t}} = \left\langle {{{A}_{t}},W{\text{*}}} \right\rangle = x_{t}^{{\text{т}}}W{\text{*}}{{y}_{t}}$. С этого ракурса задача (2) эквивалентна оценке истинной $W{\text{*}}$ матрицей ранга $k$, заданной произведением $U$ и $V$, поскольку

Для понимания того, возможно ли в постановке (2) оценить истинную матрицу $W{\text{*}}$ и тем самым восстановить целевую матрицу $M$, рассмотрим задачу (2) с дополнительными ограничениями:

для некоторых неотрицательных ${{C}_{U}}$ и ${{C}_{V}}$. Решение (3) в данной задаче эквивалентно отысканию функции, минимизирующей функционал определенный на параметрическом классе функций $\mathcal{F}$, заданным где $\Theta $ означает допустимое множество параметров, заданное прямым произведением замкнутых шаров по норме ${{\left\| {\, \cdot \,} \right\|}_{{2,1}}}$ с радиусами ${{C}_{U}}$ и ${{C}_{V}}$ соответственно для $U$ и $V$:

Для того, чтобы определить, может ли класс $\mathcal{F}$ обобщить конечный набор наблюдаемых значений $M$ на всю матрицу, необходимо оценить асимптотику ошибки восстановления этим классом. Для этого рассмотрим распределение $\mathcal{D}$ на $\mathcal{Z} \times \mathcal{T}$, где $\mathcal{Z} \subset {{\mathbb{R}}^{{{{d}_{1}} \times {{d}_{2}}}}}$ – множество матриц ${{d}_{1}} \times {{d}_{2}}$, а $\mathcal{T}$ является множеством допустимых значений в матрице $M$. Поскольку в задаче индуктивного восстановления множество $\mathcal{Z}$ задано набором ограниченных по норме матриц ранга $1$ вида $A = x{{y}^{{\text{т}}}}$, рассмотрим такие распределения $\mathcal{D}$ над $\mathcal{X} \times \mathcal{Y} \times \mathcal{T}$, для которых справедливо, что пространства побочных признаков $\mathcal{X} \subset {{\mathbb{R}}^{{{{d}_{1}}}}}$ и $\mathcal{Y} \subset {{\mathbb{R}}^{{{{d}_{2}}}}}$ являются ограниченными множествами. Отображение $\mathcal{X} \times \mathcal{Y}$ в $\mathcal{Z}$ имеет вид $(x,y) \mapsto x{{y}^{{\text{т}}}}$.

Оценка асимптотики ошибки восстановления также требует ограниченности функции потерь $\ell :\mathbb{R} \times \mathcal{T} \to \mathbb{R}$, относительно которой определяются понятия теоретического (ожидаемого) и эмпирического риска. В задаче восстановления бинарной матрицы $M$ множество $\mathcal{T}$ равно ${\text{\{ }}{\kern 1pt} - {\kern 1pt} 1,\; + {\kern 1pt} 1{\text{\} }}$ и используется бинарная функция потерь ($0{\kern 1pt} - {\kern 1pt} 1$ loss): $\ell (p,b) = {{1}_{{p \ne b}}}$. Однако для анализа асимптотики ошибки в задаче восстановления вещественной матрицы $\mathcal{T} = [ - B, + B]$ для некоторого $B > 0$ и функция потерь $\ell (p,b)$ равна ${{\left| {p - b} \right|}^{d}}$ при $d \geqslant 1$.

Определение 1 (Риск). Рассмотрим гипотезу, решающее правило или регрессионную функцию $f:\mathcal{Z} \to \mathbb{R}$. При заданном распределении $\mathcal{D}$, теоретический риск $f$ задан выражением

Для заданной выборки $S = ({{z}_{i}},{{b}_{i}})_{{i = 1}}^{m} \sim \mathcal{D}$, эмпирический риск $f$ вычисляется в виде

где ${{\hat {\mathbb{E}}}_{{(z,b) \sim S}}}$ означает (условное) математическое ожидание над эмпирическим распределением, порожденным выборкой $S$.

Для того чтобы получить оценку асимптотики верхней границы теоретического риска $R(\hat {f})$ минимизирующей гипотезы $\hat {f} = arg\;mi{{n}_{{f \in \mathcal{F}}}}\hat {R}(f)$, также известной как оценка обобщающей способности класса $\mathcal{F}$, в задаче (3), которая является эквивалентным представлением задачи SGIMC, рассмотрим более простой класс линейных гипотез на некотором $\mathcal{K} \subset {{\mathbb{R}}^{q}}$:

и оценим асимптотику теоретического риска для (5).

Заметим, что в силу того, что пространства ${{\mathbb{R}}^{{{{d}_{1}} \times {{d}_{2}}}}}$ и ${{\mathbb{R}}^{q}}$ изоморфны для $q = {{d}_{1}}{{d}_{2}}$, класс гипотез $\mathcal{H}$ тождественен классу ${{\mathcal{F}}_{1}}$, более удобному для анализа в задаче оценки значений матриц:

где ${{\left\| {\, \cdot \,} \right\|}_{{1,1}}}$ означает поэлементную ${{L}_{1}}$-норму матрицы $W$. Таким образом, поскольку для $C = {{C}_{U}}{{C}_{V}}$ справедливо, что $\mathcal{F} \subset {{\mathcal{F}}_{1}}$, из оценки асимптотики верхней границы теоретического риска для класса $\mathcal{H}$ в (5) следует оценка асимптотики ошибки восстановления для класса $\mathcal{F}$ в (4). Вложение классов следует из следующего наблюдения: если $W$ параметризована произведением $W = U{{V}^{{\text{т}}}}$ ранга $k$, тогда норму ${{\left\| W \right\|}_{{1,1}}}$ можно ограничить сверху произведением норм ${{\left\| U \right\|}_{{2,1}}}$ и ${{\left\| V \right\|}_{{2,1}}}$. Действительно,

Основной результат работы [24] дает равномерную оценку верхней границы теоретического риска с использованием понятия радемахеровской сложности (Rademacher complexity) класса гипотез [25]. Радемахеровская сложность класса $\mathcal{H} \subset {{\mathbb{R}}^{\mathcal{K}}}$ в условиях распределения ${{\mathcal{D}}_{\mathcal{K}}}$ на множестве $\mathcal{K}$ задается в виде

где математическое ожидание берется по всем выборкам $S$ размера $m$ независимых одинаково распределенных случайных величин из ${{\mathcal{D}}_{\mathcal{K}}}$. При этом эмпирическая радемахеровская сложность класса $\mathcal{H}$ при условии заданной выборки $S = ({{z}_{i}})_{{i = 1}}^{m} \subset \mathcal{K}$ определяется в виде где математическое ожидание обусловлено по выборке $S$ и берется по случайным векторам $\varepsilon = ({{\varepsilon }_{i}})_{{i = 1}}^{m}$ независимых равномерных случайных величин из ${\text{\{ }} - {\kern 1pt} 1,\; + 1{\text{\} }}$. В настоящем анализе мы рассматриваем классы измеримых функций, для которых супремум в (7) измерим, что выполняется для линейных гипотез над конечномерными пространствами ${{\mathbb{R}}^{m}}$. Заметим, что используемое в настоящей работе определение радемахеровской сложности совпадает с определением в [26], которое отличается от определения из [24] и [25] отсутствием множителя $2$.

Основная теорема об оценке обобщающей способности класса функций через радемахеровскую сложность из работ [25] и [26, теорема 3.1, стр. 35] предлагает оценку верхней границы теоретического риска, равномерную по гипотезам из $\mathcal{H}$.

Теорема 1 (переформулировка). Рассмотрим $\rho $-липшицеву функцию потерь $\ell :\mathbb{R} \times \mathcal{T} \to [0,1]$, или бинарную функцию потерь $\ell $ с $\rho = 1{\text{/}}2$. Пусть $\mathcal{H}$ является классом функций из $\mathcal{K}$ в $\mathbb{R}$ и пусть $S = ({{z}_{i}},{{b}_{i}})_{{i = 1}}^{m}$ задает выборку независимых одинаково распределенных случайных величин из $\mathcal{D}$ в пространстве $\mathcal{K} \times \mathcal{T}$. Тогда для любой $\delta \in (0,1)$ с вероятностью не ниже $1 - \delta $ по выборкам $S \sim {{\mathcal{D}}^{m}}$ следующие неравенства выполняются одновременно (равномерно) для всех $h \in \mathcal{H}$

Таким образом, для того чтобы ограничить сверху теоретический риск, достаточно найти верхнюю границу эмпирической радемахеровской сложности ${{\hat {\mathcal{R}}}_{S}}(\mathcal{H})$. Для этого мы воспользуемся теоремой 2 из [24], которая приводит оценку сложности для класса линейных гипотез H, ограниченных шаром ${{L}_{1}}$-нормы (LASSO hypothesis).

Теорема 2 (LASSO). Пусть задана фиксированная выборка $S = ({{z}_{i}})_{{i = 1}}^{m}$ из $\mathcal{K} \subset {{\mathbb{R}}^{q}}$ размера $m$. Тогда справедлива следующая оценка сверху для ${{\hat {\mathcal{R}}}_{S}}(\mathcal{H})$ из (7):

Таким образом, для любой выборки $S = ({{x}_{t}},{{y}_{t}},{{b}_{t}})_{{t = 1}}^{m}$ размера $m = \left| \Omega \right|$ независимых одинаково распределенных элементов $\mathcal{X} \times \mathcal{Y} \times \mathcal{T}$ согласно распределению $\mathcal{D}$ с ограниченным носителем, из анализа выше и оценки (8) следует, что эмпирическая радемахеровская сложность класса гипотез $\mathcal{F}$ задачи SGIMC ограничена сверху выражением

где ${{\left\| {{{A}_{t}}} \right\|}_{{max}}}$ равна ${{L}_{\infty }}$ норме элементов матрицы ${{A}_{t}}$, а ${{S}_{\mathcal{Z}}} = ({{A}_{t}})_{{t = 1}}^{m}$ является проекцией выборки $S$ на компоненту $\mathcal{Z}$, в которой ${{A}_{t}} = {{x}_{t}}y_{t}^{{\text{т}}}$ преобразует точки в $\mathcal{X} \times \mathcal{Y}$ в выборку матриц из $\mathcal{Z}$. Для любого $t$ значение нормы ${{\left\| {{{A}_{t}}} \right\|}_{{max}}}$ матрицы ранга $1$ ограниченно сверху произведением ${{\left\| {{{x}_{t}}} \right\|}_{\infty }}{{\left\| {{{y}_{t}}} \right\|}_{\infty }}$.

Для оценки асимптотики ошибки восстановления в задаче SGIMC воспользуемся оценкой (9) и теоремой 1 и, сделав некотoрое допущение относительно гипотезы $f{\text{*}}$, минимизирующей теоретический риск $R(f)$ по всем $f:A \mapsto \left\langle {A,W} \right\rangle $ и для всевозможных матриц $W \in {{\mathbb{R}}^{{{{d}_{1}} \times {{d}_{2}}}}}$ ранга $k$. Допущение заключается в следующем: рассмотрим задачу минимизации теоретического риска с требованием низкорангового решения для распределения $\mathcal{D}$ с ограничением на носитель ${{\left\| x \right\|}_{\infty }} \leqslant 1$ и ${{\left\| y \right\|}_{\infty }} \leqslant 1$, но без ограничений на нормы факторов $U$ и $V$:

с $U \in {{\mathbb{R}}^{{{{d}_{1}} \times k}}}$, $V \in {{\mathbb{R}}^{{{{d}_{2}} \times k}}}$, где $k$ равен рангу матрицы $M$, – и обозначим парой ${{U}_{ * }}$, ${{V}_{ * }}$ решение задачи (10). Если задача восстановления матрицы реализуема, т.е. минимизирующая пара $({{U}_{ * }},{{V}_{ * }})$ задачи (10) достигает нулевого теоретического риска (с бинарной функцией потерь, или ${{L}_{d}}$), тогда для любой выборки независимых одинаково распределенных случайных величин из $\mathcal{D}$ пара $(\hat {U},\hat {V})$, минимизирующая эмпирический риск, также его обнуляет. Действительно, если пара $(\hat {U},\hat {V})$, зависящая от $S$, является решением задачи (3) с эмпирическим риском вместо теоретического, тогда имеем Однако, поскольку $\ell $ является ограниченной сверху неотрицательной функцией потерь, то для любой пары $(U,V)$ можно получить откуда следует, что в реализуемом случае оптимальный эмпирический риск также обнуляется.

Если рассматривается бинарная функция потерь $\ell $, или липшицева функция потерь с показателем $\rho $, тогда в реализуемом случае задачи индуктивного восстановления матриц с отбором признаков через групповую регуляризацию оценка верхней границы теоретического риска

является результатом следующей теоремы, являющейся основным результатом данного раздела.

Теорема 3 (Основной результат). Рассмотрим задачу (3), в которой коэффициенты ${{C}_{U}} = {{\left\| {{{U}_{ * }}} \right\|}_{{2,1}}}$ и ${{C}_{V}} = {{\left\| {{{V}_{ * }}} \right\|}_{{2,1}}}$ определяются решением $({{U}_{ * }},{{V}_{ * }}) \in {{\mathbb{R}}^{{{{d}_{2}} \times k}}} \times {{\mathbb{R}}^{{{{d}_{2}} \times k}}}$ задачи (10). Тогда для любого $\delta > 0$ с вероятностью не ниже $1 - \delta $ справедлива следующая оценка верхней границы теоретического риска для пары $(\hat {U},\hat {V})$, минимизирующей эмпирический риск:

где $\left| \Omega \right|$ равно количеству наблюдаемых значений в целевой матрице $M$.

Если предположить, что теоретический риск минимизируется разреженным решением, т.е. некоторые строки матриц ${{U}_{ * }}$ и ${{V}_{ * }}$ полностью нулевые строки, тогда их ${{L}_{{2,1}}}$ нормы можно ограничить

причем ${{s}_{1}}$ и ${{s}_{2}}$ определяются верхней оценкой количества ненулевых строк, а ${{u}_{\infty }}$ и ${{{v}}_{\infty }}$ равны максимальным по модулю значениям в ${{U}_{ * }}$ и, соответственно, в ${{V}_{ * }}$. В условиях данного предположения выполняется следующее следствие теоремы 3.

Следствие 1. Если в дополнение к предпосылкам теоремы 3 предположить, что теоретический риск минимизируется разреженным решением (${{U}_{ * }}$ и ${{V}_{ * }}$ имеют не более чем ${{s}_{1}}$ и ${{s}_{2}}$ ненулевых строки), тогда с вероятностью не ниже $1 - \delta $ справедлива следующая оценка верхней границы:

${{u}_{\infty }}$ и ${{{v}}_{\infty }}$ равны максимальным по модулю значениями в матрицах ${{U}_{ * }}$ и, соответственно, в ${{V}_{ * }}$. Более того, если распределение $\mathcal{D}$ таково, что сами побочныe признаки $x$ и $y$ почти наверное разрежены, тогда с вероятностью не ниже $1 - \delta $: где ${{r}_{1}}$ и ${{r}_{2}}$ ограничивают сверху число ненулевых значений для каждого $x$ и $y$.

Из асимптотики верхних оценок ошибок восстановления, выведенных выше, можно получить процедуру для решения задачи SGIMC с ограничениями (3), если сформулировать ее как задачу регуляризованной минимизации эмпирического риска для некоторых заданных радиусов ${{C}_{U}}$ и ${{C}_{V}}$. Действительно, если предположить, что пара $(\hat {U},\hat {V})$ решает

где $\mathcal{L}$ является либо ${{L}_{q}}$ функцией потерь, либо выпуклой мажорантой бинарной функции потерь в задаче классификации. Регуляризаторы вида ${{\left\| {\, \cdot \,} \right\|}_{{2,1}}}$ обеспечивают малость ${{C}_{U}}$ и ${{C}_{V}}$ в оценке верхней границы (0.3), что, в свою очередь, с высокой вероятностью приводит к низкому теоретическому риску оцененных матриц $U$ и $V$ ранга $k$.

Заметим, что в случае разреженных матриц истинных факторов $U$ и $V$ регуляризация с помощью нормы Фробениуса приводит к асимптотике ошибки восстановления вида

в то время когда предложенная выше оценка с высокой вероятностью дает асимптотику что приводит к меньшему числу достаточных наблюдений в ${{M}_{\Omega }}$ в режиме высокого $d$ и низкого $s$. Вдобавок, если побочные признаки сами по себе разрежены, то регуляризация нормой Фробениуса дает оценку в то время как анализ, приведенный в данном разделе, дает асимптотику В сравнении это означает, что различия в оценке количества достаточного числа наблюдаемых значений в $M$ определяются соотношениями значений ${{s}_{1}}$, ${{s}_{2}}$, ${{r}_{1}}$ и ${{r}_{2}}$.

4. ПРОЦЕДУРА ВОССТАНОВЛЕНИЯ С ПРОРЕЖИВАНИЕМ

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

Задача индуктивного восстановления матриц с отбором признаков через групповую регуляризацию (SGIMC) для набора данных $({{M}_{\Omega }},X,Y)$ может быть сформулирована в виде следующей оптимизационной задачи: для заданного ранга $k \geqslant 1$ найти такие $U \in {{\mathbb{R}}^{{{{d}_{1}} \times k}}}$ и $V \in {{\mathbb{R}}^{{{{d}_{2}} \times k}}}$, которые доставляют минимум

где $\mathcal{L}(y,p)$ является гладкой выпуклой функцией потерь. Для восстановления вещественной матрицы $M$ функция потерь $\mathcal{L}(y,p)$ равна $\frac{1}{2}{{(y - p)}^{2}}$, а для восстановления бинарной матрицы со значениями $ \pm 1$ функция имеет вид $\mathcal{L}(y,p) = log(1 + {{e}^{{ - yp}}})$.

Норма ${{\left\| U \right\|}_{{2,1}}}$ является групповым регуляризатором матрицы $U$, “мягко” отсекая строки $U$ с низкой ${{L}_{2}}$, тем самым производя отбор побочных признаков, поскольку восстановлениe матрицы $M$ происходит при помощи $XU = \sum\nolimits_{p = 1}^{{{d}_{1}}} {(X{{e}_{p}})} {\kern 1pt} {{({{U}^{{\text{т}}}}{{e}_{p}})}^{{\text{т}}}}$ в (11). Заметим, что приводимая ниже итеративная процедура также позволяет регуляризовать матрицы факторов с помощью нормы Фробениуса и поэлементной ${{L}_{1}}$ нормы для поэлементного разрежения.

Задача (11) является би-выпуклой задачей, т.е. функция $J(U,V)$ выпукла по каждому аргументу в отдельности, но не в совокупности. Естественным методом в данном случае является покоординатный спуск [20] – попеременная циклическая минимизация сначала по $U$ при фиксированной $V$, затем наоборот:

покуда относительное изменение ${{U}_{t}}V_{t}^{{\text{т}}}$ между последовательными шагами итерации не станет ниже заранее установленного порога. В силу того, что по каждому аргументу по отдельности целевая функция строго выпуклая из-за регуляризации, решение каждой подзадачи (12) единственно, что означает сходимость итераций процедуры к стационарной точке [22].

Структура функции потерь и регуляризации (11) означаeт, что целевая функция $J$ для набора данных $({{M}_{\Omega }},X,Y)$ совпадает с целевой функцией ${{J}^{{\text{т}}}}$ для $(M_{\Omega }^{{\text{т}}},Y,X)$, в которой роли аргументов $U$ и $V$ поменяны местами (транспонированная задача). Таким образом, частная целевая функция $V \mapsto J(U,V)$ при фиксированном $U$ тождественна $U \mapsto {{J}^{{\text{т}}}}(V,U)$ для транспонированной задачи, что приводит к тому, что достаточно разработать итеративную процедуру для решения $mi{{n}_{U}}J(U,V)$ для данных $({{M}_{\Omega }},X,Y)$ и фиксированного $V$, чтобы получить полную процедуру для покоординатного спуска (12).

Частная задача (11) по $U$ при фиксированном $V$ имеет вид

где ${{p}_{{ij}}} = e_{i}^{{\text{т}}}(XU{{Q}^{{\text{т}}}}){{e}_{j}}$, а $Q = YV$ является матрицей ${{n}_{2}} \times k$. Мы предлагаем численно решать задачу (13) с помощью Метода переменных множителей (Alternating Direction Method of Multipliers, ADMM), предложенного в [27] и [28], с гарантиями сходимости, исследованными в [29] и [30]. Применительно к (13) итерации метода принимают вид где $\eta > 0$, двойственная переменная $\Phi $ является матрицей ${{d}_{1}} \times k$ и $\tfrac{{{{\lambda }_{R}}}}{2}\left\| U \right\|_{F}^{2}$ является вспомогательным регуляризатором, обеспечивающим сильную выпуклость целевой функции на каждой итерации.

5. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ

В данном разделе приводится экспериментальное сравнение предложенного метода индуктивного восстановления матриц с групповым регуляризатором (SGIMC) с методом IMC, предложенным в [31], а также со стандартным методом восстановления матриц (MF), основанного на факторном разложения матриц, при помощи стохастического градиентного спуска. Раздел начинается с численного эксперимента на искусственных данных, нацеленного на изучение эффектов гиперпараметров задачи и ее размерности на качество восстановления матриц. Затем алгоритмы индуктивного восстановления матриц сравниваются в задаче кластеризации и восстановления матриц на реальных наборах данных. Мы не сравниваемся с процедурой IMC из работы [16], по причине того, что существующая реализация этого алгоритма не была работоспособной даже на задачах самой низкой размерности из рассматриваемых.

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

В данной работе предлагается новый подход к индуктивному восстановлению матриц, который использует прореживающие регуляризаторы для отбора побочных признаков SGIMC. Эксперименты демонстрируют, что с помощью нового метода можно достичь высокого качествa восстановления матриц как на искусственных наборах данных, так и на данных из прикладных задач. Более того, в условиях наличия большого числа малоинформативных побочных признаков метод и предложенная вычислительная процедура работают лучше, чем аналоги. Теоретический анализ показывает, что регуляризатор ${{L}_{{1,2}}}$, наводящий групповое прореживание, позволяет улучшить асимптотическую верхнюю оценку ошибки восстановления матрицы.

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