| Теория вероятностей и ее применения |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Свойства мер устойчивости отбора признаков А. В. Булинский  Московский государственный университет имени М. В. Ломоносова, Москва, Россия
Английская версия:
Theory of Probability and its Applications, 2024, Volume 69, Issue 1, Pages DOI: https://doi.org/10.1137/S0040585X97T991726 
Реферативные базы данных:
   1. ВведениеПоследние 25 лет активно разрабатываются вероятностно-статистические методы выявления значимых факторов, оказывающих влияние на изучаемый случайный отклик. Можно считать, что исследуемая функция (отклик) $Y$ зависит от переменных (именуемых признаками или факторами) $X_1,\dots,X_d$. Требуется идентифицировать набор $(X_{j_1},\dots,X_{j_r})$, где $1\leqslant j_1<\dots <j_r\leqslant d$, от которого $Y$ зависит, в определенном смысле, существенным образом. Задачи такого рода представляют не только теоретический интерес, они важны и для разнообразных приложений, в том числе при анализе медико-биологических данных (см., например, [1]–[6]). Нахождение значимых факторов производится при различных предположениях. Часто рассматривается линейная модель с неизвестными коэффициентами, с которыми в представление функции $Y$ входят переменные $X_j$, $j=1,\dots,d$. При этом считается, что на наблюдения отклика налагаются случайные ошибки, а значимыми являются переменные, входящие в модель с коэффициентами, превышающими по модулю заданный порог. Достаточно упомянуть широко распространенный метод LASSO, получивший дальнейшее развитие (см., например, [7]). Среди нелинейных моделей большой популярностью пользуется логистическая регрессия, а также более общие смешанные модели (см., например, [8], [9]). Известно, что методы отбора значимых факторов делятся на четыре большие категории: фильтрующие, обертывающие, встроенные и гибридные. Кроме того, различают методы, предполагающие и не предполагающие обучение. Исследуются как параметрические, так и непараметрические модели. Чтобы дать представление об интенсивности рассматриваемой деятельности, укажем лишь на работу [10], где отмечено, что только развитию и приложениям одного MDR (multifactor dimensionality reduction) метода, введенного в статье [11] в 2001 г., к 2014 г. было посвящено более 800 работ. Естественно возникает вопрос, как данный алгоритм (или метод) будет работать, если он применяется к новому массиву данных. Другими словами, требуется понять, сколь хорошо тот или иной алгоритм проведет идентификацию значимых факторов, когда появятся новые наблюдения. Обычно устойчивость работы алгоритма отбора признаков (факторов) понимается как малое изменение выделяемого множества факторов при определенным образом контролируемом изменении обрабатываемых данных. По-видимому, впервые устойчивость отбора признаков была рассмотрена в работах [12] и [13]. В [12] изучалась устойчивость обертывающих методов, а авторы [13] исследовали более общую постановку. Они выясняли, как изменится набор выделяемых факторов, если алгоритм применяется к новой обучающей выборке, имеющей то же распределение, что и исходная. Отметим, что для отбора признаков применяются три основных подхода: ранжирование переменных, назначение им определенных весов, а также выделение подмножества в множестве индексов $\{1,\dots,d\}$ (и отбор признаков с этими индексами). Поскольку ранжирование и взвешивание обычно приводят к выбору набора признаков с помощью некоторого порога, мы не будем обсуждать, как именно произошло выделение упомянутого набора. Различные подходы к определению устойчивости процедур отбора признаков, а также обзор ряда результатов даны, например, в статьях [14]–[17]. Отметим работу [16], в которой авторы детально рассматривают и сопоставляют 15 известных мер устойчивости. Они также приводят ссылки на работы в области генетики, в которых анализ устойчивости отбора комбинаций генов играет принципиальную роль. Разумеется, упомянутое качественное определение устойчивости требует формализации. Целью нашей работы является рассмотрение меры устойчивости $\widehat{\Phi}$, введенной в [16]. Авторы упомянутой статьи утверждают, что только эта мера $\widehat{\Phi}$, в отличие от проанализированных ими 15 основных мер, известных в литературе, обладает пятью наиболее важными свойствами (определяемыми в следующем разделе), включая свойство монотонности. Однако мы демонстрируем, что упомянутое свойство монотонности меры $\widehat{\Phi}$ может не выполняться. Тем не менее эта мера устойчивости, несомненно, заслуживает внимания. Она имеет иное естественное свойство монотонности при фиксированном среднем значении числа выбираемых признаков. 2. Основные свойства мер устойчивостиКратко напомним два основных подхода к определению мер устойчивости отбора факторов. Первый использует сопоставление множеств, которые алгоритмом выделяются. Второй — построение некоторых функций, связанных с частотами отбора признаков или, более общим образом, зависящих от массива всех рассматриваемых данных. Пусть в $i$-м эксперименте факторы $X_1,\dots,X_d$ приняли соответственно значения $X_1^{(i)},\dots,X_d^{(i)}$, которые запишем в виде вектора $X^{(i)}$, а значение отклика $Y$ обозначим $Y^{(i)}$, $i=1,\dots,n$. Предположим, что для некоторого $n\in \mathbf{N}$ ($n>1$) даны наблюдения $(X^{(i)},Y^{(i)})$, $i=1,\dots,n$. Следуя [16], можно считать, что далее берутся $M$ бутстреповских выборок, построенных по имеющимся данным. Другой вариант — генерировать $M$ наборов данных отклика и факторов, задав их совместное распределение. Для нас будет существенно, что в результате применения некоторого алгоритма к $M$ наборам данных получены подмножества $S_1,\dots,S_M$ множества индексов $\{1,\dots,d\}$. Считается, что алгоритм находит множество индексов существенных (в определенном смысле) факторов. Требуется понять, насколько “близки” эти $M$ подмножеств, выделяемых алгоритмом. С этой целью вводится ряд функций $\Phi$ (“мер сходства”), которые сопоставляют между собой эти множества. Важная мера $\phi$ сравнения двух множеств была предложена в статье [18]. Она обобщает меру устойчивости, введенную в [19], на множества, вообще говоря, разной мощности. А именно,
$$
\begin{equation}
\phi(S_i,S_m):= \frac{|S_i\cap S_m| - |S_i|\,|S_m|/d}{\min\{|S_i|,|S_m|\} -\max\{0,|S_i|+|S_m|-d\}},
\end{equation}
\tag{1}
$$
где $|\,{\cdot}\,|$ обозначает число элементов конечного множества, $i,m\,{=}\,1,\dots,M$. Заметим, что функция $\phi$, фигурирующая в (1), принимает значения в множестве $[-1,1]$. Как правило, в качестве меры устойчивости набора множеств $S_1,\dots,S_M$, содержащихся в $\{1,\dots,d\}$, используют функцию, основанную на парных сравнениях:
$$
\begin{equation}
\Phi(S_1,\dots,S_M):= \frac{1}{M(M-1)}\sum_{i,m\in \{1,\dots,d\},\, i\neq m}\phi(S_i,S_m),
\end{equation}
\tag{2}
$$
где $\phi$ может задаваться и формулой, отличной от (1) (см., например, [16; табл. 6]). Подмножеству $S=\{j_1,\dots,j_r\}\subset \{1,\dots,d\}$ удобно поставить в соответствие вектор $z$ в $\mathbf{R}^d$, компоненты которого с номерами $j_1,\dots,j_r$ равны единице, а остальные — нулю. Очевидно, что такое соответствие взаимно однозначно. Тогда вместо набора $S_1,\dots,S_M$ можно рассмотреть $(M\times d)$-матрицу $Z=(z_{i,j})$, где $z_{i,j}\in \{0,1\}$, $i=1,\dots,M$, $j=1,\dots,d$, а вектор $z_i:=(z_{i,1},\dots,z_{i,d})$ отвечает множеству $S_i$ описанным образом. В [16; с. 13] введена мера устойчивости, основанная на матрице $Z$:
$$
\begin{equation}
\widehat{\Phi}(Z):= 1-\frac{(1/d)\sum_{j=1}^d s_j^2}{(\overline{k}/d)(1-\overline{k}/d)},
\end{equation}
\tag{3}
$$
где для $M>1$ и $d>1$
$$
\begin{equation}
s_j^2:=\frac{M}{M-1}\, \widehat{p}_j(1-\widehat{p}_j),\quad \overline{k}:=\sum_{j=1}^d \widehat{p}_j,\quad\widehat{p}_j:=\frac{1}{M}\sum_{i=1}^M z_{i,j}.
\end{equation}
\tag{4}
$$
Если $\overline{k}=0$ или $\overline{k}=d$ (т.е. $\widehat{p}_j$, $j=1,\dots,d$, или все равны нулю, или все равны единице), то полагаем $\widehat{\Phi}(Z):=1$. Когда надо подчеркнуть, что указанные величины зависят от матрицы $Z$, будем писать $s_j^2(Z)$, $\overline{k}(Z)$ и $\widehat{p}_j(Z)$. Заметим, что девять мер устойчивости, рассмотренных в [16; табл. 6] и вводимых с помощью (2), для заданной $\phi$ можно рассматривать как функции от матрицы $Z$. Например, формулу (1) легко переписать, учитывая, что $|S_i|=\sum_{j=1}^d z_{i,j}$, $|S_i \cap S_j|= (z_i,z_j)$, где $(\,{\cdot}\,,{\cdot}\,)$ — скалярное произведение в $\mathbf{R}^d$, порождающее евклидову метрику. Если строки матрицы $Z$ независимы и для каждого $i=1,\dots,M$ вектор $z_i=(z_{i,1},\dots,z_{i,d})$ таков, что $z_{i,j}$ есть реализация бернуллиевской величины с вероятностью успеха $p_j$, $j=1,\dots,d$ (независимость компонент вектора $z_i$ не предполагается), то согласно [16; теорема 7] меру устойчивости $\widehat{\Phi}$ можно рассматривать как асимптотически нормальную при $M\to \infty$ (с явно указанной нормировкой) статистическую оценку функции
$$
\begin{equation}
\Phi:= 1- \frac{(1/d)\sum_{j=1}^d p_j(1-p_j)}{\overline{p}(1-\overline{p})},
\end{equation}
\tag{5}
$$
где $\overline{p}:= (1/d)\sum_{j=1}^d p_j$. В такой схеме величина $\widehat{p}_j$ — статистическая оценка $p_j$, $j=1,\dots,d$. В [16] отмечено, что функция, введенная в (3), является частным случаем каппа-функции, изученной в [20]. По мнению авторов [16], желательно, чтобы мера устойчивости, построенная по матрице $Z$ (или по набору множеств $S_1,\dots,S_M$), обладала пятью основными свойствами, указанными в [16; табл. 1, с. 7]. Эти свойства следующие. $1^{\circ}$. Полная определенность: возможность использовать для нахождения $\widehat{\Phi}$ любую матрицу $Z$ с элементами, равными $0$ или $1$, тем самым позволяя варьировать мощности множеств $S_1,\dots,S_M$. $2^{\circ}$. Строгая монотонность: $\widehat{\Phi}$ является строго убывающей функцией от $s_j^2$, где $s_j^2$, $j=1,\dots,d$, введены в (4). $3^{\circ}$. Ограниченность: функция $\widehat{\Phi}$ должна быть ограничена сверху (или снизу) константой, которая не зависит ни от общего числа, ни от количеств выбираемых факторов. $4^{\circ}$. Максимальная устойчивость должна отвечать детерминированной схеме: $\widehat{\Phi}$ достигает своего максимального значения тогда и только тогда, когда все строки $z_i$ матрицы $Z$ совпадают. $5^{\circ}$. Поправка на случайность: величина $\mathbf{E}(\widehat{\Phi}\,|\,H_0)$ является константой, где $H_0$ означает, что результаты, указанные в каждой строке матрицы $Z$, имеют одну и ту же вероятность при любой перестановке ее элементов. Как отмечено выше в разделе 1, статья [16] содержит исследование 15 известных мер устойчивости с целью выяснить, какими из упомянутых пяти свойств обладает каждая их них. Результаты, представленные в [16; табл. 2, с. 11], показывают, что ни одна из этих 15 мер устойчивости не обладает всеми пятью основными свойствами. Поэтому в [16] главное внимание уделяется мере $\widehat{\Phi}$, определенной в (3), которая, как утверждают авторы, обладает всеми пятью требуемыми свойствами. В разделе 3 мы доказываем, что сформулированное выше свойство монотонности $2^{\circ}$ меры, введенной в (3), вообще говоря, не выполняется. Однако эта функция $\widehat{\Phi}(Z)$ заслуживает внимания, вместо $2^{\circ}$ она обладает иным естественным свойством монотонности, рассмотренным далее в замечании 3. 3. Свойство монотонностиНа с. 7 работы [16] авторы формулируют свойство строгой монотонности мер устойчивости (приведенное выше свойство $2^{\circ}$ в разделе 2), которое, по их мнению, желательно для каждой меры такого рода. Авторы утверждают, что с ростом величин $s_j^2$ функция $\widehat{\Phi}(Z)$ является строго убывающей. Разумеется, если в формуле (3) считать $s_1^2,\dots,s_d^2$ независимыми переменными, то функция $\widehat{\Phi}(Z)$ является убывающей по этим переменным. Однако если дана матрица $Z$, то однозначно определены величины $\widehat{p}_j$ и $s_j^2$, $j=1,\dots,d$. Следовательно, когда говорится об изменении $\widehat{\Phi}(Z)$ с ростом величин $s_j^2$, то это означает переход от одной матрицы к другой матрице, при котором происходит рост величин $s_j^2$, $j=1,\dots,d$. Заметим, что всегда можно менять компоненты столбцов матрицы $Z$ из нулей и единиц, чтобы получить любое наперед заданное значение $\widehat{p}_j$ из множества $\{0,1/M,\dots,M/M\}$, $j=1,\dots,d$, если алгоритм выдает некоторый набор из нулей и единиц без ограничений (например, нет ограничения, что алгоритм каждый раз находит одно и то же число $r$ факторов). Теорема 1. Для каждого натурального $d$, большего единицы, и всех достаточно больших $M$ $(M>10d+4)$ существуют $(M\times d)$-матрицы $Z_1$ и $Z_2$, элементы которых принадлежат множеству $\{0,1\}$, такие, что для некоторого $m\in \{1,\dots,d\}$ но при этом Доказательство. Для каждого $j=1,\dots,d$ переменная $\widehat{p}_j$ меняется от $0$ до $1$ с шагом $1/M$. Введем следующие функции от переменных $x_j\in [0,1]$, $j=1,\dots,d$:
$$
\begin{equation*}
\widetilde{\Phi}(x_1,\dots,x_d):=1- \frac{M}{M-1}f(x_1,\dots,x_d),
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
f(x_1,\dots,x_d):= \frac{\sum_{j=1}^d x_j(1-x_j)}{\sum_{i=1}^d x_i\bigl(1- (1/d)\sum_{i=1}^d x_i\bigr)}.
\end{equation*}
\notag
$$
Если имеется матрица $Z$, для которой найдены $\widehat{p}_j$, $j=1,\dots,d$, то
$$
\begin{equation*}
\widehat{\Phi}(Z)= \widetilde{\Phi}(\widehat{p}_1,\dots,\widehat{p}_d).
\end{equation*}
\notag
$$
При $m=1,\dots,d$ имеем
$$
\begin{equation*}
\frac{\partial}{\partial x_m}f(x_1,\dots,x_d) = \frac{g_m(x_1,\dots,x_d)}{\bigl(\sum_{j=1}^d x_j\bigl(1- (1/d)\sum_{j=1}^d x_j\bigr)\bigr)^2},
\end{equation*}
\notag
$$
где
$$
\begin{equation}
\begin{aligned} \, g_m(x_1,\dots,x_d) &=(1-2x_m)\biggl(\sum_{j=1}^d x_j - \frac1{d}\biggl(\sum_{j=1}^d x_j\biggr)^2\biggr) \nonumber \\ &\qquad -\biggl(\sum_{j=1}^d x_j - \sum_{j=1}^d x_j^2\biggr)\biggl(1- \frac2{d}\sum_{j=1}^d x_j\biggr). \end{aligned}
\end{equation}
\tag{8}
$$
Функция $\frac{\partial}{\partial x_m}f(x_1,\dots,x_d)$ принимает конечные значения, если $x_j\,{\in}\, (0,1)$, $j=1,\dots,d$. Точнее говоря, исключаются случаи, когда $\sum_{j=1}^d x_j=0$ или $\sum_{j=1}^d x_j=d$, т.е. все $x_j=0$ или все $x_j=1$ при $j=1,\dots,d$.
Зафиксируем $m\in \{1,\dots,d\}$ и положим
$$
\begin{equation*}
A:=\sum_{j\in\{1,\dots,d\},\, j\neq m}x_j,\quad B:=\sum_{j\in\{1,\dots,d\},\, j\neq m}x_j^2,
\end{equation*}
\notag
$$
где $A=A_m$ и $B=B_m$ зависят от $x_j$, $j\in\{1,\dots,d\}\setminus \{m\}$. Тогда
$$
\begin{equation*}
\begin{aligned} \, g_m(x_1,\dots,x_d) &= (1-2x_m)\biggl(x_m+A -\frac{(x_m+A)^2}{d}\biggr) \\ &\qquad- (x_m+A - x_m^2-B)\biggl(1-\frac{2(x_m+A)}{d}\biggr). \end{aligned}
\end{equation*}
\notag
$$
Имеем $t-t^2/d\leqslant d/4$ для $t\in \mathbf{R}$. Поэтому при $x_m\in [0,1/2]$ и $x_j\in [0,1]$, $j\in\{1,\dots,d\}\setminus \{m\}$, выполнено неравенство
$$
\begin{equation*}
(1-2x_m)\biggl(x_m+A -\frac{(x_m+A)^2}{d}\biggr)\leqslant (1-2x_m)\,\frac{d}{4}.
\end{equation*}
\notag
$$
Кроме того, $B\leqslant A$, так как $x_j\in [0,1]$, $j=1,\dots,d$. Очевидно, что Пусть $1- (2/d)\sum_{j=1}^dx_j\geqslant c$, где $c\in (0,1)$, т.е. $\sum_{j=1}^d x_j\leqslant (1-c)d/2$. Тогда
$$
\begin{equation*}
(x_m+A - x_m^2-B)\biggl(1-\frac{2(x_m+A)}{d}\biggr)\geqslant c(x_m-x_m^2).
\end{equation*}
\notag
$$
Для $c\in (0,1)$ и $d>1$ введем в $\mathbf{R}^d$ множество
$$
\begin{equation}
\begin{aligned} \, \Delta_{d,m}(c) &:=\biggl\{x=(x_1,\dots,x_d)\in \mathbf R^d\colon x_m\,{\in} \biggl[0,\frac{1}{2}\biggr], \nonumber \\ &\qquad\qquad x_j\,{\in}\, [0,1],\, j\,{\in}\,\{1,\dots,d\}\setminus \{m\},\, \sum_{j=1}^d x_j \,{\leqslant}\, \frac{(1-c)d}{2}\biggr\}. \end{aligned}
\end{equation}
\tag{9}
$$
Это множество не является пустым для $c\in (0,1-1/d]$. Действительно, пусть $x_j=v\in [0,1]$ для $j\in \{1,\dots,d\}\setminus \{m\}$. Тогда, поскольку $x_m \leqslant 1/2$, имеем
$$
\begin{equation*}
\sum_{j=1}^d x_j\leqslant \frac{1}{2}+(d-1)v \leqslant \frac{(1-c)d}{2},
\end{equation*}
\notag
$$
когда $v\leqslant (d(1-c)-1)/(2(d-1))=: v^*$. Очевидно, $0\leqslant v^*\leqslant 1/2$ при $d\geqslant 2$ и $c\in (0,1-1/d]$. Если $x=(x_1,\dots,x_d)\in \Delta_{d,m}(c)$, где $c\in (0,1-1/d]$, то
$$
\begin{equation*}
g_m(x_1,\dots,x_d)\leqslant (1-2x_m)\frac{d}{4} - c(x_m-x_m^2).
\end{equation*}
\notag
$$
Для $u \in [0,1/2]$ решение неравенства представляет собой промежуток
$$
\begin{equation*}
U(d,c):=\biggl(\frac{1}{2}\biggl(1+\frac{d}{2c}-\sqrt{1+\frac{d^2}{4c^2}}\,\biggr), \frac{1}{2}\biggr].
\end{equation*}
\notag
$$
Возьмем $c\in (0,1-1/d]$. Для $M\in \mathbf{N}$ выберем $x^{(0)}_m=r/M$, где $r\,{\in}\, \mathbf{N}$ таково, что $x^{(0)}_m$ и $x^{(0)}_m+1/M$ принадлежат множеству $U(d,c)$. Это возможно при $M>M_0(c,d)$, где $M_0(c,d):=4(d/(2c)+\sqrt{d^2/(4c^2)+1})$. Для $d>1$, $c\in (0,1-1/d)$ и $M>M_0(c,d)$ определим множество
$$
\begin{equation*}
\begin{aligned} \, T_{d,m}(M,c) &:= \biggl\{x=(x_1,\dots,x_d)\in [0,1]^d\colon \\ &\qquad\qquad x^{(0)}_m\leqslant x_m\leqslant x^{(0)}_m+\frac{1}{M},\, \sum_{j=1}^d x_j \leqslant \frac{(1-c)d}{2}\biggr\}. \end{aligned}
\end{equation*}
\notag
$$
Для этих $d$, $c$ и $M$ имеем $T_{d,m}(M,c)\subset \Delta_{d,m}(c)$.
Пусть $x^{(0)}_j\,{=}\,1/M$, $j\,{\in}\, \{1,\dots,d\}\setminus \{m\}$. Тогда для $d>1$, $M > M_1(c,d):=2(d-1)/((1-c)d-1)$ и $c\in (0,1-1/d)$ точки $x^{(0)}=(x^{(0)}_1,\dots,x^{(0)}_d)$ и $x^{(0)}+(1/M)e_m$ принадлежат множеству $T_{d,m}(M,c)$, где вектор $e_m$ в $\mathbf{R}^d$ имеет $m$-ю компоненту, равную единице, а остальные его компоненты равны нулю. Нетрудно видеть, что $M_0(c,d)>M_1(c,d)$ для $d>1$ при $c \in (0,2(d-1)/(2d+1))$. Для $x^{(0)}$ и любого $u\in [0,1/M]$ рассмотрим вектор
$$
\begin{equation*}
x(m,u):= \bigl(x^{(0)}_1,\dots,x^{(0)}_{m-1},x^{(0)}_m+u,x^{(0)}_{m+1},\dots,x^{(0)}_d\bigr).
\end{equation*}
\notag
$$
Имеем $x(m,u)\in \Delta_{d,m}(c)$. Функция $h$ убывает на $[0,1/2]$. Следовательно,
$$
\begin{equation*}
g_m(x(m,u))\leqslant h(x_m^{(0)}+u)\leqslant h(x_m^{(0)})<0.
\end{equation*}
\notag
$$
Для некоторого $w_m\in (0,1/M)$ по формуле Лагранжа имеем
$$
\begin{equation}
\begin{aligned} \, &f\biggl(x^{(0)}+\frac{1}{M}e_m\biggr) - f(x^{(0)}) \nonumber \\ &\qquad= \frac{g_m(x^{(0)}+w_m e_m)}{\bigl(\bigl(\sum_{j=1}^dx_j+ w_m\bigr)\bigl(1- (1/d)\bigl(\sum_{j=1}^d x_j+w_m\bigl)\bigr)\bigr)^2}\, \frac{1}{M}<0. \end{aligned}
\end{equation}
\tag{10}
$$
Здесь принято во внимание, что функция $f(x_1,\dots,x_m,\dots,x_d)$ непрерывна по $x_m$ на отрезке $[x_m,x_m+1/M]$ при фиксированных остальных аргументах.
Следовательно, для каждого $m\in \{1,\dots,d\}$ при $d>1$, $d\in \mathbf{N}$, $c \in (0,2(d-1)/(2d+1))$ и всех достаточно больших $M$ (а именно, для любого $M\in \mathbf{N}$ такого, что $M>M_0(c,d)$) найдутся $(M\times d)$-матрицы $Z_1$ и $Z_2$ с элементами из множества $\{0,1\}$, которые обладают следующими свойствами. Во-первых,
$$
\begin{equation*}
\begin{gathered} \, \widehat{p}_j(Z_1)=x_j^{(0)},\quad j\in \{1,\dots,d\}, \\ \widehat{p}_m(Z_2)=x_m^{(0)}+\frac{1}{M},\qquad\widehat{p}_j(Z_2)= x_j^{(0)},\quad j\in \{1,\dots,d\}\setminus \{m\}, \end{gathered}
\end{equation*}
\notag
$$
при этом, согласно (10), выполнено (7). Во-вторых,
$$
\begin{equation*}
s_m^2(Z_1) < s_m^2(Z_2),\qquad s_j^2(Z_1)=s_j^2(Z_2),\quad j\in \{1,\dots,d\}\setminus \{m\},
\end{equation*}
\notag
$$
где учтено, что $\widehat{p}_m(Z_1)<\widehat{p}_m(Z_2)\leqslant 1/2$, а функция $u-u^2$ возрастает на $[0,1/2]$ (и убывает на $[1/2,1]$).
Число $c\in (0,2(d-1)/(2d+1))$ можно выбрать сколь угодно близким к $2(d-1)/(2d+1)$. Поэтому утверждение теоремы 1 будет справедливо при всех натуральных $M$ таких, что
$$
\begin{equation*}
M > 2(a+\sqrt{a^2 +4}),\qquad a:=\frac{d(2d+1)}{2(d-1)}.
\end{equation*}
\notag
$$
Таким образом, теорема 1 будет заведомо верна при $M> 10d + 4$, где $d=2,3,\dots$. Доказательство теоремы завершено. Замечание 1. Интересно отметить, что не существует точки $x{\kern0.8pt}{\in}{\kern0.8pt}[0,1/2]^d$ такой, что $g_m(x)<0$ одновременно при всех $m=1,\dots,d$. Действительно, в противном случае мы имели бы Замечание 2. При каждых $d,M\in \mathbf{N}$ для $(M\times d)$-матрицы $Z$, имеющей $\widehat{p}_j= p$, $j=1,\dots,d$, функция $\widetilde{\Phi}(p,\dots,p)$ равна $-1/(M-1)$. Поэтому при любом $d\in \mathbf{N}$ и $M\geqslant 4$ легко построить $(M\times d)$-матрицы $Z_1$ и $Z_2$, для которых справедливо (6), но $\widehat{\Phi}(Z_1)= \widehat{\Phi}(Z_2)$. Теорема 1 показывает, что может произойти строгое возрастание $\widehat{\Phi}$, когда верно (6). Для $(M\times d)$-матрицы $Z$, состоящей из нулей и единиц, положим т.е. $q_j(Z)$ — число единиц в столбце с номером $j$ матрицы $Z$, $j=1,\dots,d$. Таким образом, $q_j(Z)= M\widehat{p}_j(Z)$, $j=1,\dots,d$. Введем множества
$$
\begin{equation*}
\begin{aligned} \, J_1(Z) &:=\biggl\{j\in \{1,\dots,d\}\colon q_j(Z)<\frac{M}{2}\biggr\}, \\ J_2(Z) &:=\biggl\{j\in \{1,\dots,d\}\colon q_j(Z)\geqslant \frac{M}{2}\biggr\}. \end{aligned}
\end{equation*}
\notag
$$
Следующий результат дает простой критерий того, когда для $(M\times d)$-матриц $Z_1$ и $Z_2$ с элементами из множества $\{0,1\}$ справедливо (6). Лемма 1. Пусть элементы $(M\times d)$-матриц $Z_1$, $Z_2$ равны нулю или единице. Тогда (6) верно в том и только том случае, когда выполнены неравенства Доказательство. Достаточно обратиться к формуле (4), учесть, что $\widehat{p}_j=q_j/M$, $j=1,\dots,d$, и рассмотреть поведение функции $x-x^2$ для $x\in [0,1]$. Утверждение леммы установлено. Следствие 1. В силу леммы 1 для $(M\times d)$-матрицы $Z_1$, состоящей из нулей и единиц, вообще говоря, может не существовать $(M\times d)$-матрица $Z_2$ также из нулей и единиц такая, что имеет место (6). Поясним это. Пусть натуральное число $d$ больше единицы, а $M=2k$, где $k\in \mathbf{N}$, и $q_j(Z_1)= k$, $j=1,\dots,d$. Таким образом, $J_2(Z)=\{1,\dots,d\}$. Тогда $M-q_j(Z_1)=k$, $j=1,\dots,d$. Видим, что выполнение (15) невозможно ни для какой $(M\times d)$-матрицы $Z_2$, содержащей нули и единицы. Рассмотрим теперь матрицу $Z$ такую, что каждый раз алгоритм выбирает ровно $r$ факторов из $\{1,\dots,d\}$, т.е. в каждой из $M$ строк матрицы $Z$ стоит ровно $r$ единиц, а остальные элементы строки равны нулю. Обозначим класс таких матриц $C_r(M,d)$. Тогда
$$
\begin{equation}
\overline{k}= \sum_{j=1}^d\widehat{p}_j= \sum_{j=1}^d \frac{1}{M}\sum_{i=1}^Mz_{i,j} =\frac{1}{M}\sum_{i=1}^M\sum_{j=1}^d z_{i,j}=\frac{1}{M}\sum_{i=1}^M r= r.
\end{equation}
\tag{18}
$$
Поэтому для матрицы $Z\in C_r(M,d)$
$$
\begin{equation}
\widehat{\Phi}(Z)=1- \frac{(1/d)\sum_{j=1}^d s_j^2}{(r/d)(1-r/d)}.
\end{equation}
\tag{19}
$$
Таким образом, для выяснения вопроса, как ведет себя $\widehat{\Phi}(Z)$ при переходе от одной матрицы класса $C_r(M,d)$ к другой матрице этого класса, надо лишь рассмотреть, как при этом изменяется величина $\sum_{j=1}^d s_j^2(Z)$. Заметим, что в силу (18) Следствие 2. Для каждого $r\in \mathbf{N}$ можно указать $M,d\in \mathbf{N}$ и матрицу $Z_1\in C_r(M,d)$ такую, что не найдется матрицы $Z_2\in C_r(M,d)$, для которой было бы справедливо (6). Для доказательства возьмем $M= pq$, $d=pr$, где $p,q,r\in \mathbf{N}$, $p\geqslant 3$. Рассмотрим матрицу $Z_1\in C_r(M,d)$, у которой
$$
\begin{equation*}
z_{i,j}=1, \quad\text{если }\ i\in\{vq+1,\dots,(v+1)q\},\ \ j\in \{vr+1,\dots,(v+1)r\}
\end{equation*}
\notag
$$
для $v\in \{0,\dots,p-1\}$, а остальные элементы матрицы $Z_1$ пусть равны нулю. Тогда $J_1(Z_1)=\{1,\dots,d\}$. Допустим, что нашлась матрица $Z_2\in C_r(M,d)$, для которой выполняется (6). Согласно лемме 1 получаем $q_m(Z_2)>q_m(Z_1)$ и $q_j(Z_2)\geqslant q_j(Z_1)$ для $j\in \{1,\dots,d\}\setminus \{m\}$, поэтому Пришли к противоречию, поскольку для любой матрицы из $C_r(M,d)$ должно выполняться (20). Замечание 3. Привлекательность меры устойчивости $\widehat{\Phi}(Z)$, заданной формулой (3), заключается в том, что она позволяет сравнивать матрицы даже разных размеров и без предположений о монотонных изменениях этой меры с ростом величин $s_j^2$, $j=1,\dots,d$. Следствие 2 показывает, что не всегда возможно найти матрицы, которые допускают сравнение в смысле выполнения (6). Поэтому вместо свойства $2^{\circ}$ монотонности, предложенного в [16] и приведенного в разделе 2, естественно требовать свойство монотонности меры устойчивости $\widehat{\Phi}(Z)$ относительно суммы $\sum_{j=1}^d s_j^2(Z)$ при условии фиксации средней величины $\overline{k}(Z)$. Функция $\widehat{\Phi}(Z)$, заданная формулой (3), обладает данным свойством. Пусть теперь матрица $Z_1\,{=}\,(z^{(1)}_{i,j})$, где $i=1,\dots,M$, $j=1,\dots,d$ ($M\,{\geqslant}\, 2$, $d\geqslant 2$), такова, что для некоторого $q\in \mathbf{N}$, $q<M$, имеем
$$
\begin{equation*}
z^{(1)}_{i,1}=1,\quad i=1,\dots, q,\qquad z_{i,2}^{(1)}=1,\quad i=q+1,\dots,M,
\end{equation*}
\notag
$$
а все остальные элементы $(M\times d)$-матрицы $Z_1$ равны нулю. Определим $(M\times d)$-матрицу $Z_2=(z^{(2)}_{i,j})$ такую, что
$$
\begin{equation*}
z^{(2)}_{i,1}=1,\quad i=q+1,\dots,M,\qquad z^{(2)}_{i,3}=1,\quad i=1,\dots,q,
\end{equation*}
\notag
$$
а все остальные элементы $(M\times d)$-матрицы $Z_2$ равны нулю. Тогда очевидно, что Матрицы $Z_1$ и $Z_2$ показывают, что первый и второй алгоритмы каждый раз выделяют один фактор. При этом применение (3) демонстрирует их одинаковую устойчивость. Первый алгоритм отдает предпочтение факторам с номерами $1$ и $2$ (частоты остальных равны нулю), а второй (согласно матрице $Z_2$) — факторам с номерами $1$ и $3$. Отметим также, что хотя $s_1^2(Z_1)=s_1^2(Z_2)$, тем не менее частоты $\widehat{p}_1(Z_1)$ и $\widehat{p}_1(Z_2)$ могут быть различны. Исходя из оценки устойчивости работы алгоритма с помощью $\widehat{\Phi}(Z)$, мы не можем сделать выбор в пользу первого или второго алгоритма. По-видимому, желательно сравнивать на устойчивость те алгоритмы, которые в результате обучения с большой вероятностью приводят к выявлению правильных (в определенном смысле) наборов факторов. В этой связи укажем на работы [14], [15], [21].
Цитирование в формате AMSBIB
\RBibitem{Bul24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|