Журнал вычислительной математики и математической физики, 2020, T. 60, № 3, стр. 369-378

2.1. Стохастическое матричное разложение

Определение 1. Будем называть матрицу $F$ неотрицательной, если ${{F}_{{ij}}} \geqslant 0\;{\kern 1pt} \forall i,j$.

Определение 2. Будем называть матрицу $F$ стохастической, если она является неотрицательной и $\sum\nolimits_i^{} {{{F}_{{ij}}}} = 1\;{\kern 1pt} \forall j.$

Определение 3. Неотрицательным (стохастическим) матричным разложением матрицы $F \in {{\mathbb{R}}^{{n \times m}}}$ называют представление $F$ в виде произведения двух неотрицательных (стохастичеcких) матриц $F = \Phi \Theta $.

Определение 4. Матричным разложением полного ранга матрицы $F \in {{\mathbb{R}}^{{n \times m}}},$ $\operatorname{rank} F = k$ называют представление $F$ в виде произведения двух матриц полного ранга $F = \Phi \Theta ,$ $\Phi \in {{\mathbb{R}}^{{n \times k}}}$, $\Theta \in {{\mathbb{R}}^{{k \times m}}}$.

Далее в этой работе для краткости разложением матрицы $F$ называется стохастическое матричное разложение полного ранга, кроме тех случаев, в которых явно сказано, что это стохастическое разложение или неотрицательное разложение. Также будем предполагать, что в матрице $F$, для которой ищется неотрицательное, стохастическое или стохастическое полноранговое разложение, нет нулевых столбцов.

Из определения разложения матрицы сразу следует, что матрицы $\Phi $ и $\Theta $ имеют ранг $k$. Также можно заметить, что если у матрицы есть хотя бы одно разложение, то она является стохастической.

Заметим, что если дано разложение $ \Leftrightarrow $ и у матрицы $\Phi $ есть хотя бы два различных столбца или у матрицы $\Theta $ есть хотя бы две различных строки, то можно найти новое разложение $F = \Phi S{{S}^{{ - 1}}}\Theta $, где $S$ – матрица перестановки. В связи с этим общепринятым является следующее определение единственности разложения.

Определение 5. Разложение $F = \Phi \Theta $ называется единственным, когда выполнено следующее условие: если нашлось некоторое другое разложение $F = \Phi {\text{'}}\Theta {\text{'}}$, то $\Phi {\text{'}} = \Phi S,$ $\Theta {\text{'}} = {{S}^{{ - 1}}}\Theta $ для некоторой матрицы перестановки $S$.

Введем следующие вспомогательные обозначения:

$\overline {{\text{supp}}(v)} $ – множество позиций, на которых стоят нулевые элементы вектора $v$;

${\text{supp}}(v)$ – множество позиций, на которых стоят ненулевые элементы вектора $v$;

${{X}_{j}}$ – есть $j$-й столбец матрицы $X$;

$X[[{{i}_{1}}, \ldots ,{{i}_{p}}],\;[{{j}_{1}}, \ldots ,{{j}_{q}}]]$ – подматрица, состоящая из строк ${{i}_{1}}, \ldots ,{{i}_{p}}$ и столбцов ${{j}_{1}}, \ldots ,{{j}_{q}}$.

2.2. Связь между неотрицательными и стохастическими матричными разложениями

Утверждение 1. Пусть $F \in {{\mathbb{R}}^{{n \times m}}}$ матрица без нулевых столбцов с неотрицательным разложением $F = \Phi \Theta $, $\Phi \in {{\mathbb{R}}^{{n \times k}}}$, $\Theta \in {{\mathbb{R}}^{{k \times m}}}$. Рассмотрим стохастическую матрицу $\tilde {F}$, ${{\tilde {F}}_{{ij}}} = \tfrac{{{{F}_{{ij}}}}}{{\sum\nolimits_i^{} {{{F}_{{ij}}}} }}$. Тогда $\tilde {F} = \tilde {\Phi }\tilde {\Theta }$ является стохастическим разложением матрицы $\tilde {F}$, где

Доказательство. Заметим, что матрицы $S$ и $\Theta {\text{'}}$ определены корректно, т.е. деления на ноль произойти не может, благодаря предположению о том, что в матрице $F$ нет нулевых столбцов.

Докажем, что $\tilde {F} = \tilde {\Phi }\tilde {\Theta }$ является стохастическим разложением матрицы $\tilde {F}$. Разделив $j$-й столбец левой и правой части равенства $F = \Phi S{{S}^{{ - 1}}}\Theta $ на $\sum\nolimits_i^{} {{{F}_{{ij}}}} $, мы получаем, что $\tilde {F} = \tilde {\Phi }\tilde {\Theta }$ является верным равенством. Матрица $S$ подобрана таким образом, чтобы матрица $\tilde {\Phi }$ была стохастической, следовательно, верно равенство $e_{n}^{{\text{T}}}\tilde {\Phi } = e_{k}^{{\text{T}}}$, где ${{e}_{p}} \in {{\mathbb{R}}^{p}}$ – вектор-столбец из единиц. Воспользовавшись стохастичностью матрицы $\tilde {F}$, получаем

Значит, матрица $\tilde {\Theta }$ тоже стохастическая.

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

2.3. Обзор результатов

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

В работе [18] вводится геометрическая интерпретация стохастического матричного разложения. Для матрицы $X$ обозначим ${{C}_{X}} = \left\{ {x\,{\text{|}}\,x = \sum\nolimits_i^{} {{{a}_{i}}{{X}_{i}}} ,\;{{a}_{i}} \geqslant 0} \right\}$ симплициальный конус, порожденный векторами ${{X}_{i}}$. Геометрическая интерпретация заключается в сопоставлении каждому стохастическому разложению матрицы $F = \Phi \Theta $ симплициального конуса ${{G}_{\Phi }} \supset {{G}_{F}}$. Также в работе получены достаточные условия на матрицы-факторы (Lemma 4), гарантирующие единственность разложения, при этом достаточные условия выражаются в терминах симплициальных конусов ${{G}_{\Phi }}$ и ${{G}_{F}}$. Аналог этой геометрической интерпретации в терминах выпуклых многогранников активно используется в нашей работе (см. лемму 1).

В работе [19] получены необходимые условия единственности (Theorem 5) и достаточные условия единственности для неотрицательных матричных разложений. На примерах демонстрируется выполнение условий теорем и их ограничения. В экспериментах показывается, что в случае единственности разложения $F = \Phi \Theta $ добавление небольшого шума к исходным данным F влечет сходимость к тому же единственному решению $(\Phi ,\Theta )$ c небольшим шумом.

В работе [20] используется геометрическая интерпретация, введенная в работе [18], и доказывается достаточный критерий единственности (Theorem 6), при этом условия даются в терминах матрицы $F$. Описывается техника предобработки данных, приводящая к устойчивости и разреженности получаемой тематической модели. Демонстрируется эффективность техники на нескольких наборах изображений.

3.1. Условия основной теоремы

Теорема 1. Пусть дано разложение $F = \Phi \Theta $, $F \in {{\mathbb{R}}^{{n \times m}}}$, $\operatorname{rank} F = k$, $\Phi \in {{\mathbb{R}}^{{n \times k}}}$, $\Theta \in {{\mathbb{R}}^{{k \times m}}}$. Пусть выполнены следующие условия.

Условие 1. $\forall i \in \{ 1, \ldots ,k\} $ $\exists j:{{\Theta }_{{ij}}} = 1,$ $\forall i{\text{'}} \ne j{{\Theta }_{{i{\text{'}}j}}} = 0.$

Условие 2. $\forall j\;\operatorname{rank} (\Phi [\overline {{\text{supp}}({{\Phi }_{j}})} ,\;[1, \ldots ,k]{\backslash }[j]]) = k - 1.$

Тогда разложение $F = \Phi \Theta $ единственно.

Первое условие требует наличия в матрице $\Theta $ $k$ столбцов, из которых можно составить единичную матрицу $k \times k$.

Второе условие требует, чтобы для каждого столбца ${{\Phi }_{j}}$ матрицы $\Phi $ подматрица, соответствующая множеству строк, на которых в ${{\Phi }_{j}}$ стоят нули, имела ранг $k - 1$. Тривиальным примером матрицы $\Phi $, которая удовлетворяет этому условию, является матрица, из $k$ строк которой можно составить единичную матрицу размера $k \times k$.

Простым следствием из этой теоремы является достаточное условие для единственности разложения стохастической матрицы $F$.

Следствие 1. Пусть у стохастической матрицы $F \in {{\mathbb{R}}^{{n \times m}}}$ ранга $k$ нашлось $k$ таких столбцов с номерами $\{ {{j}_{1}}, \ldots ,{{j}_{k}}\} : = J$, что

(I) $\forall j \in J\;\operatorname{rank} (F[\overline {{\text{supp}}({{F}_{j}})} ,\;J{\backslash }[j]]) = k - 1,$

(II) для любого $j \in J,$ $p = 1, \ldots ,m,$ найдутся коэффициенты ${{a}_{{jp}}} \geqslant 0$ т.ч. $\sum\nolimits_{j \in J}^{} {{{a}_{{jp}}}} = 1,$ ${{F}_{p}} = \sum\nolimits_{j \in J}^{} {{{a}_{{jp}}}{{F}_{j}}} ,\;\,\forall p.$

Тогда у $F$ существует единственное разложение $F = \Phi \Theta $, где

Доказательство. Действительно, если выполнено условие 1, то $k$ столбцов ${{F}_{{{{j}_{1}}}}}, \ldots ,{{F}_{{{{j}_{k}}}}}$ можно взять в качестве матрицы $\Phi $, подходящей под условия теоремы 1. Матрица $\Theta $, дающая разложение $F = \Phi \Theta $, найдется благодаря условию $2$.

Сравним это следствие с теоремой единственности, сформулированной в работе [20]. Паттерном разреженности (англ. sparsity pattern) вектора $v$ называется множество $\{ i{\kern 1pt} {\text{|}}{\kern 1pt} {{v}_{i}} = 0\} $. Например, паттерн разреженности вектора $(4,0,0,2,0)$ есть $\{ 1,2,4\} $. Неотрицательным рангом матрицы $F$ назовем такое минимальное $r$, что существует неотрицательное разложение матрицы $F = \Phi \Theta ,$ $\Phi \in {{\mathbb{R}}^{{n \times r}}}$, $\Theta \in {{\mathbb{R}}^{{r \times m}}}$.

Теорема 2 ([20, теорема 6]). Пусть дана стохастическая матрица $F$ с рангом, совпадающим с неотрицательным рангом и равным $k$. Если у матрицы $F$ есть $k$ ненулевых столбцов, каждый из которых имеет $k - 1$ нулей таких, что в соответствующих этим нулям строкам паттерны разреженности различны, то матрица $F$ имеет единственное разложение.

Ниже приведен пример матрицы $F$, которая имеет единственное разложение, удовлетворяет условиям следствия теоремы 1, описанного выше, но не удовлетворяет условиям теоремы 6 статьи [20].

Пример 1.

У этой матрицы $F$ есть единственное разложение $F = FE$, но условия теоремы [20, Theorem 6] не выполнены, потому что для каждого столбца у множества строк, в которых этот столбец зануляется, одинаковые паттерны разреженности. При этом легко понять, что условия следствия теоремы 1 выполнены.

Определение 6. Стандартным $(n - 1)$-мерным симплексом называется множество

Далее линейной оболочкой матрицы $X$ будем называть линейную оболочку множества ее столбцов $\{ {{X}_{i}}\} $ и обозначать ${\text{span}}(X)$. Аналогично выпуклой оболочкой матрицы $X$ будем называть выпуклую оболочку ее столбцов и обозначать $\operatorname{conv} (X)$.

Определение 7. Точку $v$ выпуклого многогранника $M$ называют вершиной $M$, если не существует такого отрезка $[{{u}_{1}},{{u}_{2}}] \subset M$, что $v$ является внутренней точкой отрезка $[{{u}_{1}},{{u}_{2}}]$.

Лемма 1. Пусть дана стохастическая матрица $F \in {{\mathbb{R}}^{{n \times m}}}$, $\operatorname{rank} F = k$. Каждый выпуклый многогранник $M \subset {{\Delta }_{{n - 1}}}$ с $k$ вершинами, т.ч. $\operatorname{conv} (F) \subset M$, биективно соответствует некоторому семейству разложений $F = \Phi \Theta $, которое определяется условием $\operatorname{conv} (\Phi ) = M$.

Доказательство аналогичного утверждения можно найти в [18, лемма 4]. В этой работе доказательство проводится в терминах симплициальных конусов. Каждый симплициальный конус в формулировке работы [18] соответствует некоторому многограннику в приведенной выше формулировке. Соответствие ‘многогранник’ $ \to $ ‘конус’ восстанавливается путем взятия всех возможных положительных линейных комбинаций точек из многогранника. Соответствие ‘конус’ $ \to $ ‘многогранник’ получается путем пересечения конуса со стандартным симплексом.

Следствие 2. Пусть разложение $F = \Phi \Theta $ таково, что $\operatorname{conv} (F) = \operatorname{conv} (\Phi )$. Тогда, если каждая вершина $\operatorname{conv} (\Phi )$ является вершиной $\operatorname{span} (\Phi ) \cap {{\Delta }_{{n - 1}}}$, то разложение $F = \Phi \Theta $ единственно.

Доказательство этого следствия можно найти в [20, лемма 4].

3.2. Доказательство теоремы 3

Целью этого подраздела является доказательство теоремы 3. Основой доказательства является лемма 3 о необходимых и достаточных условиях на то, чтобы точка ${{\Phi }_{i}}$ являлась вершиной многогранника $\operatorname{span} (\Phi ) \cap {{\Delta }_{{n - 1}}}$.

Для начала докажем несколько вспомогательных лемм.

Лемма 2. Пусть многогранник $M$ задан системой

где ${{\pi }_{i}}$ являются линейными функциями. Точка $v$ является вершиной $M$ тогда и только тогда, когда системаимеет единственное решение, где

Доказательство. Единственность решения системы (3.1) $ \Rightarrow $ $v$ – вершина.

Предположим, что $v$ не вершина, тогда, т.к. она удовлетворяет набору условий ${{\pi }_{i}}(x) \geqslant 0,$ $i = 1, \ldots ,m$, значит, точка $v$ лежит в многограннике $M$, и следовательно, она является серединой некоторого отрезка $L$ с концами ${{u}_{1}}$ и ${{u}_{2}}$. Заметим, что в силу симметрии ${{u}_{1}}$ и ${{u}_{2}}$ относительно $v$ выполнено $\forall i \in I$ ${{\pi }_{i}}({{u}_{1}}) = - {{\pi }_{i}}({{u}_{2}})$. При этом $\forall x \in M\;{{\pi }_{i}}(x) \geqslant 0$ и $\sum\nolimits_s^{} {{{x}^{s}}} = 1$. Значит, $\forall i \in I\;{{\pi }_{i}}({{u}_{1}})\, = \,{{\pi }_{i}}({{u}_{2}})\, = \,0$. Но тогда $\forall x \in L$ $x$ является решением системы (3.1), получаем противоречие c тем фактом, что $v$ является единственным решением системы (3.1).

Таким образом, $v$ – вершина $ \Rightarrow $ единственность решения системы (3.1).

Предположим, что нашлось еще одно решение системы (3.1). Значит, система ${{\pi }_{i}}(x) = 0,\;i \in I$ имеет пространство решений размерности больше $0$, а пересечение этого пространства решений с системой

является многогранником $M{\kern 1pt} {\text{'}}$ размерности больше 0. Отметим, что точка $v$ обязана по определению $I$ быть внутренней для $M{\kern 1pt} {\text{'}}$, в противном случае на ней бы затуплялась некоторая линейная функция ${{\pi }_{i}}$ для некоторого индекса $i \notin I$. Поэтому точка $v$ представляется как средняя точка некоторого отрезка $[{{u}_{1}},{{u}_{2}}] \subset M{\kern 1pt} ' \subset M$, а значит, не является вершиной $M$.

Лемма 3. Пусть дано разложение $F = \Phi \Theta $, $F \in {{\mathbb{R}}^{{n \times m}}}$. Тогда вершина ${{\Phi }_{j}}$ многогранника ${\text{conv}}(\Phi )$ является вершиной ${\text{span}}(\Phi ) \cap {{\Delta }_{{n - 1}}}$ тогда и только тогда, когда

Доказательство. Без ограничения общности будем считать, что $j = k$.

Далее будет доказано, что следующие утверждения являются эквивалентными:

(I) ${{\Phi }_{k}}$ является вершиной многогранника ${\text{span}}(\Phi ) \cap {{\Delta }_{{n - 1}}};$

(II) $\exists !$ решение системы

(III) $\exists !$ решение системы уравнений

(IV) $\operatorname{rank} (\Phi [\overline {{\text{supp}}({{\Phi }_{k}})} ,\;[1, \ldots ,k]{\backslash }[k]]) = k - 1;$

(III) $ \Leftrightarrow $ (IV)

Система (3.3) всегда имеет нулевое решение. То, что это решение единственно, равносильно тому, что ядро отображения, задаваемого матрицей $\Phi [\overline {{\text{supp}}({{\Phi }_{k}})} ,\;[1, \ldots ,k]{\backslash }[k]]$, нулевое, что равносильно (IV).

$({\text{III}}) \Rightarrow ({\text{II}})$

Заметим, что при $i \in \overline {{\text{supp}}({{\Phi }_{k}})} {{\Phi }_{{ik}}} = 0$, поэтому

Пусть система (3.3) имеет единственное решение, тогда система (3.2) имеет не более одного решения, потому что в ней больше условий. При этом система (3.2) всегда имеет решение ${{e}_{k}} = (0, \ldots ,0,1)$, которое соответствует точке ${{\Phi }_{k}}$, ${{\Phi }_{k}} = \Phi {{e}_{k}}$. Значит, и система (3.2) имеет единственное решение.

(II) $ \Rightarrow $ (III)

Пусть у системы (3.2) существует единственное решение. Тогда оно равно ${{e}_{k}}$ (вектор размера $k$), потому что такое решение всегда существует. Также $0$ (только в данном случае это уже вектор размера $k - 1$) является решением системы (3.3). Предположим, что у системы (3.3) нашлось еще одно решение $u \ne 0$. Тогда мы можем определить новое решение $\bar {u}$ системы (3.2), подобрав константу $c$ в векторе $\tilde {u} = ({{u}^{{(1)}}}, \ldots ,{{u}^{{(k - 1)}}},c)$ и отнормировав его:

где

(I) $ \Leftrightarrow $ (II)

Следует из леммы 2. Заметим, что система

задает в точности многогранник $\operatorname{span} (\Phi ) \cap {{\Delta }_{n}}$ в пространстве $\operatorname{span} (\Phi )$ в координатах ${{\Phi }_{i}}$, который соответствует многограннику M из леммы 2. Множеству $I$ из леммы 2 соответствует $\overline {{\text{supp}}({{\Phi }_{k}})} $.

Теперь есть все необходимое, чтобы доказать теорему 1.

Доказательство. Из условия

следует, что $k$ точек $F$ совпадают с вершинами $\operatorname{conv} (\Phi )$, а значит, $\operatorname{conv} (F) = \operatorname{conv} (\Phi )$.

Условие же на ранги

по лемме 3 равносильно тому, что каждая вершина $\operatorname{conv} (\Phi )$ является вершиной многогранника $\operatorname{span} (\Phi ) \cap {{\Delta }_{{n - 1}}}$. Значит, теорема 1 следует из следствия 2.

4.1. Интерпретация условий теоремы

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

Условие 1, заключающееся в наличии в матрице темы-документы $\Theta $ столбцов, из которых можно составить единичную матрицу $k \times k$, говорит о наличии $k$ унитематических документов, то есть таких, в которых вероятности встретить любую тему, кроме одной, нулевые. Выполнение этого условия можно гарантировать, добавив в коллекцию $k$ искусственно созданных унитематических документов, слова для которых подбираются, например, экспертами.

Условие 2 говорит о том, что для любого $j$ матрицы

задают неотрицательное разложение полного ранга матрицы $F[\overline {{\text{supp}}({{\Phi }_{j}})} ,:]$. Это означает, что матрица $\Phi $, из которой убрали $j$-ю тему-столбец и все слова, вероятность которых ненулевая в этой теме, и матрица $\Theta $, из которой убрали $j$-ю тему-строку, задают тематическую модель для матрицы слова-документы $F$, из которой убрали все слова, встречающиеся в $j$-й теме.

Для проверки выполнения второго условия на реальной текстовой коллеции был проведен эксперимент.

4.2. Описание эксперимента

Эксперимент проводился на лемматизированной коллекции 20newsgroups [21]. Тематическая модель строилась алгоритмом оптимизации ARTM (см. [3], [4]) с регуляризатором разреживания $R(\Phi ) = \alpha \sum\nolimits_t {\sum\nolimits_w {ln{{\phi }_{{wt}}}} } $ с коэффициентом регуляризации $\alpha $. В использованной реализации алгоритма ARTM по умолчанию матрица $\Phi $ не может содержать нулей. Регуляризатор разреживания позволяет добиться зануления малых значений в этой матрице и контролировать количество нулей.

Для проверки второго условия теоремы требовалось для каждой темы $t$ проверять полноту ранга матрицы $\Phi [\overline {\operatorname{supp} ({{\Phi }_{t}})} ,[1, \ldots ,T]{\backslash }[t]]$. Эффективный вычислительный способ сделать это – нахождение минимального сингулярного значения матрицы $\Phi [\overline {{\text{supp}}({{\Phi }_{t}})} ,[1, \ldots ,T]{\backslash }[t]]$ и сравнение его с нулем. Далее будем обозначать это минимальное сингулярное значение ${{\sigma }_{t}}$ для темы $t$.

4.3. Результаты

Как показывает фиг. 1, даже незначительного разреживания ($\alpha = - {{10}^{{ - 25}}}$) достаточно, чтобы обеспечить единственность разложения. Однако, если запустить исходный алгоритм PLSA без какого либо разреживания, то условия теоремы не будут выполняться из-за отсутствия нулей в матрице $\Phi $.