Автоматика и телемеханика, № 3, 2021

Оптимизация, системный анализ

и исследование операций

(Федеральный исследовательский центр

“Информатика и управление” РАН, Москва;

Институт проблем управления им. В.А. Трапезникова РАН, Москва),

Ю.А. ДУБНОВ (yury.dubnov@phystech.edu)

(Федеральный исследовательский центр

“Информатика и управление” РАН, Москва;

Национальный исследовательский университет

“Высшая школа экономики”, Москва),

А.Ю. ПОПКОВ, канд. техн. наук (apopkov@isa.ru)

(Федеральный исследовательский центр

“Информатика и управление” РАН, Москва)

ЭНТРОПИЙНО-РАНДОМИЗИРОВАННОЕ ПРОЕКТИРОВАНИЕ¹

Предложен новый метод рандомизированного проектирования, ос-

нованный на энтропийной оптимизации случайных матриц-проекторов

(ERP-метод). Введено понятие индикатора компактности матрицы дан-

ных, который сохраняется в матрицах-проекциях. Сформулирован алго-

ритм ERP в виде задачи условной максимизации энтропийного функ-

ционала, заданного на функциях плотности распределения вероятностей

матриц-проекторов. Рассмотрен дискретный вариант этой задачи, полу-

чены условия существования и единственности ее положительного реше-

ния. Развиты процедуры реализации энтропийно-оптимальных матриц-

проекторов путем сэмплирования функций плотности распределения ве-

роятностей (ПРВ).

Ключевые слова: случайное проектирование, сжатие и растяжение мат-

рицы данных, матрицы-проекторы, индикатор компактности, сэмплиро-

вание функции плотности, дисперсионные множества, интерквартильные

множества.

DOI: 10.31857/S0005231021030090

1. Введение

Процедуры машинного обучения, ориентированные на задачи классифи-

кации, кластеризации и прогнозирования, оперируют данными, представлен-

ными в виде матриц “объекты-признаки”, из которых формируются обучаю-

щие и тестовые коллекции данных. В процессе формирования обучающей

¹ Работа выполнена при поддержке Российского фонда фундаментальных исследований

(проект № 20-07-00470).

149

коллекции и в особенности в результате ее применения для решения упо-

мянутых выше задач часто оказывается, что признаков недостаточно или

слишком много, так же как и объектов. Другими словами, возникает необ-

ходимость в преобразованиях имеющейся матрицы данных в обучающую и

тестовую коллекции.

Эти преобразования касаются как “сжатия”, так и “растяжения” матрицы

данных. В терминах “объекты-признаки” возникает семейство задач “сжа-

тия”: редукция количества признаков, редукция количества объектов и па-

раллельная редукция того и другого; и семейство задач “растяжения”: рас-

ширение пространства признаков, увеличение количества данных (условных

“объектов”) и параллельное увеличение того и другого. Если преобразова-

ния “сжатия” очень популярны в теории и практике машинного обучения, то

преобразованиям “растяжения” уделяется не столь широкое внимание. Хотя

исследователи, занимающиеся проблемами классификации и кластеризации,

часто сталкивались с тем, что в указанных проблемах в маломерных про-

странствах признаков они неразрешимы или дают низкую точность, тогда

как при увеличении размеров признакового пространства удается решить за-

дачу с хорошей точностью. Аналогичные эффекты наблюдаются и при недо-

статочном количестве данных.

Проблемам “сжатия” матрицы данных посвящена обширная литература,

некоторое представление о которой можно составить по обзорам [1-3] и мо-

нографиям [4-7].

Данная проблема вложена в более общую: приближение заданного на-

бора многомерных точек маломерным аффинным многообразием [8]. Здесь

следует отметить метод главных компонент (МГК) (Principal Component

Analysis (PCA)) [9-11] и его робастные версии [12]. Следует отметить,

что МГК применяется для матриц данных ограниченной размерности, так

как вычисление собственных чисел является весьма трудоемкой задачей.

Для многомерных задач применяют латентный семантический анализ ЛСА

(Latent Semantic Analysis (LSA)), основанный на сингулярном разложении

матрицы [13].

Редуцированные коллекции данных используются для решения различ-

ных задач машинного обучения. Поэтому было бы полезным в процедурах

редукции учитывать проблемную ориентацию их использования. Этот эф-

фект достигается в линейном дискриминационном анализе (ЛДА) (Linear

Discriminant Analysis (LDA)) [14, 15].

Учет в процедурах редукции последующих применений “сжатых” матриц -

тренд, который просматривается в задачах обработки больших объемов дан-

ных: распознавание по видеопотокам, классификация коллекций документов

и др. В этих случаях применяется метод случайных проекций (RP), базирую-

щийся на асимптотическом эффекте проецирования на пространство доста-

точно большой размерности, при котором в среднем сохраняется расстояние

между точками (лемма Джонсона-Линденштраусса [16]). Экспериментально

показано, что для генерации случайных матриц-проекторов может быть ис-

пользовано стандартное нормальное распределение, а в некоторых случаях

равномерное распределение [17-19].

150

Совсем иная ситуация, когда возникает необходимость в “растяжении”

матрицы данных. Наиболее часто такая необходимость имеет место в за-

дачах анализа таких данных, механизмы генерации которых неизвест-

ны. Одной из форм представления данных являются многомерные вре-

менные ряды. Примером таких объектов являются процессы, происходя-

щие в мозгу живых существ и, прежде всего, человека, макро-проявления

которых фиксируются в виде электрических сигналов ЭЭГ [20]. Анало-

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

в виде временных рядов котировок акций, валют, товаров и финансо-

вых инструментов [21]. В последнее время весьма популярными становят-

ся исследования электорального поведения населения во время выборов,

предсказание которого осуществляется путем анализа ретроспективной ди-

намики процессов выборов, отображенной в соответствующих временных

рядах [22].

В этих работах применялись так называемые модельные конструкции

временных рядов, а формирование признакового пространства осуществля-

лось последовательным отбором признаков с привлечением методов фильтра-

ции [23], условной энтропии [24], взаимной информации “признак-класс” [25],

кросс-энтропии Кульбака-Ляйблера [26].

Однако в некоторых задачах, частично упомянутых выше, использовать

модель временного ряда трудно или невозможно из-за отсутствия знания о

механизмах его происхождения. Поэтому важными являются попытки отоб-

ражения компонент временного ряда в конечный набор чисел признаков

многомерного временного ряда. Полагая, что многомерный временной ряд

кодирует свойства объекта, последнее означает, что формируется признако-

вое пространство объекта.

В [27] была предложена процедура безмодельного отображения временно-

го ряда в конечную совокупность характеризующих его чисел, основанную на

теории ε-сложности. В дальнейшем [28, 29] эта процедура была тестирована

на задачах бинарной классификации одного класса ЭЭГ-сигналов в области

психиатрии. Результаты этих исследований показали, с одной стороны, что

технология ε-сложности может служить основой для безмодельной класси-

фикации временных рядов, а с другой что для достижения удовлетво-

рительной точности классификации возникает необходимость в увеличении

размерности признакового пространства.

В данной работе развивается новый метод “сжатия” и “растяжения” мат-

рицы c не вполне достоверными данными, основанный на построении ран-

домизированных матриц-проекторов (ERP-метод). Развит алгоритм опти-

мизации функции плотности распределения вероятностей (ПРВ) матриц-

проекторов с учетом сохранения индикатора компактности матрицы дан-

ных. Алгоритм сформулирован в терминах условной максимизации энтро-

пийного функционала, определенного на функциях ПРВ матриц-проекторов.

При этом оптимальные оценки функций ПРВ соответствуют условиям макси-

мальной неопределенности. Реализация рандомизированных матриц-проек-

торов осуществляется путем сэмплирования оптимальных ПРВ с исполь-

зованием bootstrap-процедуры и метода Монте-Карло [30, 31]. Рассмотре-

ны задачи рандомизированного проектирования с фиксированными эле-

151

ментами множества матриц-проекторов, на котором определена дискретная

функция распределения вероятностей. Сформулирован алгоритм ее оптими-

зации и выбора полезных числовых характеристик множества случайных

матриц-проекторов.

2. Формулировки задач энтропийно-рандомизированного

проектирования

1. Точечно-множественное представление матрицы данных: индикатор

компактности

Рассмотрим матрицу данных “объекты-признаки”:





u⁽¹⁾

{

}

(2.1)

U_(m×s) = ···

,

u⁽ⁱ⁾ = u⁽ⁱ⁾¹,... ,u⁽ⁱ⁾

∈R^s

i = 1,m.

u^(m)

Здесь m количество объектов, s количество признаков, R^s признаковое

пространство. Будем полагать, что элементы матрицы данных стандартизо-

ваны, т.е. u_ij ∈ [0, 1], i = 1, m, j = 1, s.

Точечно-множественным отображением матрицы U_(m×s) в признаковом

{

}

пространстве R^s(m) будем называть множество U^sm точек

u⁽¹⁾,... ,u^(m)

В качестве характеристики разброса точек в множестве U^sm определим ин-

дикатор компактности ρ_U как среднее арифметическое расстояний между

точками²:

∑

(

)

(2.2)

ρ_U =

̺ u^(α),u^(β)

m(m - 1)

(α,β)=1, α<β

(

)

где ̺

u^(α),u^(β)

расстояние между точками u^(α), u^(β). Если элементы мат-

рицы данных стандартизованы и выбрано евклидово расстояние, то

(

)

√

0≤̺ u^(α),u^(β)

≤

для всех (α, β) = 1, m,

(2.3)

0≤ρ_U

≤ 1.

Определим следующие классы трансформаций матрицы данных:

• (mr)-класс: U_(m×s) → Y_(m×r), множество Y^rm в пространстве R^r(m);

• (ns)-класс: U_(m×s) → B_(n×s), множество B^sn в пространстве R^s(n);

• (nr)-класс: U_(m×s) → Z_(n×r), множество Z^rn в пространстве R^r(n).

² Могут быть выбраны и другие индикаторы, например максимальное расстояние меж-

ду точками и др.

152

2. Случайные матрицы-проекторы и их вероятностные характеристики

1. Проектирование на пространство R^r(m) (генерация множества Y^rm).

Эту операцию будем осуществлять с помощью матрицы-проектора Q_(s×r):





y⁽¹⁾

Y_(m×r) = ···

=U(m×s)Q_(s×r);

y^(m)

(2.4)

∑

y^(i)j =

u_ikq_kj, i = 1,m; j = 1,r.

k=1

Матрица-проектор Q_(s×r) случайная интервального типа, т.е.

(2.5)

Q_(s×r) ∈ Q = [Q^-,Q⁺

Вероятностные свойства матрицы-проектора характеризуются непрерывно-

дифференцируемой функцией плотности распределений вероятностей (ПРВ)

P (Q), определенной на Q.

Векторы y⁽ⁱ⁾ образуют множество Y^rm из m r-мерных точек. Определим

расстояние между ними ̺(y^(α), y^(β) | Q_(s×r)) и индикатор компактности

∑

(

)

(2.6)

ρ_Y (Q) =

̺ y^(α),y^(β)

|Q_(s×r)

m(m - 1)

(α,β)=1, α<β

Поскольку значения элементов матрицы-проектора случайные числа, то

среднее расстояние (2.6) принимает случайные значения.

Определим математическое ожидание индикатора компактности:

∫

(2.7)

ρY = P (Q)ρY

(Q)dQ.

2. Проектирование на пространство R^(n×s) (генерация множества B^sn).

Эту операцию осуществим с помощью матрицы-проектора T_(n×m) со слу-

чайными элементами:





b⁽¹⁾

B_(n×s) = ···

=T(n×m)U_(m×s);

b⁽ⁿ⁾

(2.8)

∑

b^(i)j =

t_ik u_kj, i = 1,n; j = 1,s.

k=1

Матрица-проектор T_(n×m) случайная интервального типа, т.е.

(2.9)

T_(n×m) ∈ T = [T^-,T⁺

153

Ее вероятностные свойства характеризуются функцией ПРВ W (T ), опреде-

ленной на T .

Векторы b⁽ⁱ⁾ образуют множество B^sn из s-мерных точек в количестве

n < m. Определим индикатор компактности в виде

∑

(2.10)

ρ_B(T) =

̺(b^(α), b^(β)

|T)

n(n - 1)

(α,β), α<β

и его математическое ожидание:

∫

(2.11)

ρB = W (T )ρB(T )dT.

3. Проектирование на пространство R^r(n) (генерация множества Z^rn).

Эту операцию будем осуществлять с помощью случайных матриц-проек-

торов T_n×m и Q_(s×r):





z⁽¹⁾

(2.12)

Z_(n×r) = ···

=T(n×m)U_(m×s)Q_(s×r);

z⁽ⁿ⁾

∑

z⁽ⁱ⁾

= t_ip u_pkq_kj,

i = 1,n; j = 1,r.

p=1

k=1

Указанные матрицы-проекторы интервального типа:

T_(n×m) ∈ T = [T^-,T⁺],

(2.13)

Q_(s×r) ∈ Q = [Q^-,Q⁺

Вероятностные свойства матриц-проекторов характеризуются функцией сов-

местного ПРВ F (T, Q), определенной на множестве

⊗

(2.14)

F =T

Векторы z⁽ⁱ⁾ образуют множество Z^rn из r-мерных точек. Индикатор компакт-

ности этого множества:

∑

(2.15)

ρ_Z(T,Q) =

̺(z^α, z^β

|T,Q).

n(n - 1)

(α,β), α<β

Математическое ожидание индикатора компактности имеет вид

∫

(2.16)

ρZ = F (T, Q)ρZ(T, Q)dT dQ.

Соотношения между размерами (m, s) матрицы данных и размерами

(m, r), (n, s), (n, r) матриц-проекций характеризуют ее “сжатие” или “растя-

жение”: если r < s, n < m, то “сжатие”; если r > s, n > m, то “растяжение”.

154

3. Алгоритмы энтропийно-рандомизированного проектирования

Рассмотрим проектирование на пространство R^r(n), которое осуществляет

трансформацию матрицы данных одновременно по двум ее параметрам.

Алгоритм энтропийно-рандомизированного проектирования (ERP-алго-

ритм) представляет собой MEE-оценку функции ПРВ F(T,Q) с включен-

ным в нее условием балансирования (равенства) индексов компактности мат-

риц данных U_(m×s) и проекции Z_(n×r).

MEE-оценка [32] функции F(B,Q) определяется следующим алгоритмом:

∫

(3.1)

H[F (T, Q)] = -

F (T, Q) ln F (T, Q) dT dQ ⇒ max,

∫

F (T, Q)dT dQ = 1,

∫

F (T, Q)ρ_Z (T, Q)dT dQ = ρ_U .

Задача (3.1) является функциональной задачей на условный экстремум ля-

пуновского типа: все их компоненты являются интегральными функциона-

лами [33].

Интегральная форма этой задачи позволяет использовать для формули-

ровки условий оптимальности функционал Лагранжа со скалярными множи-

телями Лагранжа:





∫

L[F (T, Q)] = H[F (T, Q)] + µ1 - F (T, Q)dT dQ +





∫

(3.2)

+ λρ_U - F(T,Q)ρ_Z(T,Q)dTdQ .

В терминах производных Гато [33] (G_F ) условия стационарности функциона-

ла Лагранжа приобретают следующий вид:

(3.3)

G_F

L[F (T, Q)] = 0.

Энтропийно-оптимальная функция ПРВ матриц-проекторов имеет вид [32]

exp (-λ ρ_Z (T, Q))

(3.4)

F^∗(T,Q|λ) =

F(λ)

∫

F(λ) = exp (-λ ρ_Z (T, Q)) dT dQ.

155

Из выражений (3.4) видно, что структура функции ПРВ зависит от вы-

бранной функции расстояний (2.15) и не зависит от параметра λ, определяе-

мого из уравнения баланса индикаторов компактности:

∫

(3.5)

Φ(λ) = exp (-λ ρ_Z (T, Q)) (ρ_Z (T, Q) - ρ_U

) dT dQ = 0.

Поскольку параметр λ является масштабным, можно использовать его при-

ближенное значение, получаемое из линеаризованного уравнения (3.5):

∫

(ρ_Z (T, Q) - ρ_U ) dT dQ

λ=

∫

(3.6)

ρ_Z(T,Q)(ρ_Z(T,Q) - ρ_U )dTdQ

Пример 1. Пусть матрица данных и индикаторы компактности, постро-

енные на евклидовом и манхэттенском расстояниях, имеет вид





0,1

0,8

;

U_(3×2) = 0,5 0,4

ρ^EU = 0,506, ρ^MU = 0,933.

0,9

0,2

Рассмотрим проектирование на пространство R²⁽¹⁾:

Z_(2×1) = z⁽²⁾ = T_(2×3)U_(3×2)q(2),

где

(

)

(

)

T = [T^-,T⁺], T^- =

;

T⁺ =

;

(

)

(

)

-1

Q = [q^-,q⁺], q^- =

q+ =

-1

Вектор z⁽²⁾ имеет следующие компоненты:

∑

z₁ = q₁

t_1ju_j1 + q₂

t_1ju_j2, z₂ = q₁

t_2ju_j1 + q₂

t_2ju_j2.

j=1

Рассмотрим два вида расстояний между элементами вектора z:

евклидово



₂

∑

ρ^EZ(T,q) = (z₁ - z₂)²

=q₁

u_j1(t_1j - t_2j) - q₂

u_j2(t_1j - t_2j)

;

j=1

манхэттенское



∑



ρ^MZ (T,q) = |z₁ - z₂| =

q₁

u_j1(t_1j - t_2j) - q₂

u_j2(t_1j - t_2j).



 j=1

j=1

156

Энтропийно-оптимальные ПРВ случайных матриц-проекторов (3.4) имеют

вид:

для евклидового расстояния

(

)

exp

-λ ρ^EZ(T,q)

(3.7)

F^∗E(T,q |λ) =

F(λ)

∫

(

)

F_E(λ) = exp

-λρ^EZ(T,q)

dT dq;

для манхэттенского расстояния

(

)

exp

-λ ρ^MZ (T,q)

(3.8)

F^∗M (T,q |λ) =

F(λ)

∫

(

)

F_M (λ) = exp

-λρ^MZ (T,q)

dB dq.

Параметр λ определяется из следующих уравнений для евклидова и манхэт-

тенского расстояний соответственно:

∫

(

)(

)

(3.9)

exp

-λρ^EZ(T,q)

ρ^EZ(T,q) - δ ρ^EU

dT dq = 0,

∫

(

)(

)

exp

-λρ^MZ (T,q)

ρ^MZ (T,q) - δ ρ^MU

dT dq = 0.

В равенствах (3.7)-(3.9)

⊗

F =T

Качественное представление о морфологии многомерных функций ПРВ (3.7),

(3.8) дают некоторые их сечения.

a) матрица-проектор T задана:

(

)

T^∗ =

Соответствующие сечения ненормированных функций (3.7), (3.8) имеют вид:

[

)

F^∗E(T^∗,q) ∼ exp

-λ(0,41q₁ - 0,28q₂)²

(q₁, q₂) ∈ [-1, 1],

F^∗M (T^∗,q) ∼ exp [-λ|0,41q₁ - 0,28q₂|) , (q₁,q₂) ∈ [-1,1].

б) матрица-проектор T и вектор-проектор q⁽²⁾ имеют вид:

(

)

(

)

q₁

T =

q(2) =

t₂₁

-1

157

Соответствующие сечения ненормированных функций (3.7), (3.8) имеют вид:

[

)

F^∗E(T^∗,q) ∼ exp

-λ(-0,1q₁t₂₁ - 0,4q₁ + 0,8t₂₁ + 0,2)²

q₁ ∈ [-1,1], t₂₁ ∈ [0,1],

F^∗M (B^∗,q) ∼ exp [-λ| - 0,1q₁t₂₁ - 0,4q₁ + 0,8t₂₁ + 0,2|) ,

q₁ ∈ [-1,1], t₂₁ ∈ [0,1].

Заметим, что полученные ПРВ случайных проекторов энтропийно-опти-

мальны для соответствующей матрицы данных и существенно отличаются от

нормального распределения, рекомендуемого для применения при случайном

проектировании (см., например [19]).

4. Реализация случайных проекторов и их числовых характеристик

Стандартный способ реализации случайных проекторов состоит в сэм-

плировании энтропийно-оптимальных ПРВ P (Q), W (T ), F (T, Q), при кото-

рых сохраняется межвекторное расстояние матрицы данных в ее матрицах-

проекциях. В результате сэмплирования ПРВ трансформируются в последо-

вательность случайных матриц-проекторов:

(

)

(

)

(4.1)

F^∗(T,Q) ⇒ T⁽¹⁾,Q⁽¹⁾

,..., T^(N),Q^(N)

,...

Общий метод генерации случайных последовательностей с заданной функ-

цией ПРВ изложен в [34]. Свойство сохранения указанного выше баланса

может не выполняться для каждого в отдельности элемента этой последова-

тельности, но “в среднем” оно выполняется. Поэтому в качестве реализуемого

эмпирического проектора можно принять матрицы

∑

(4.2)

T ≈

T⁽ⁱ⁾,

Q≈1

Q⁽ⁱ⁾.

i=1

Точные значения “средних” матриц-проекторов определяются следующими

равенствами:

∫

(4.3)

T = T F(T,Q)dTdQ,

QF(T,Q)dTdQ.

Хотя интегралы в этих равенствах многомерные, но подынтегральные функ-

ции представляют собой экспоненты от полиномов. Это часто позволяет по-

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

Кроме того проблему вычисления многомерных интегралов можно решить

приближенными методами: методом Монте-Карло и методами полиномиаль-

ной аппроксимации подынтегральных функций.

Функция ПРВ F^∗(T, Q) определена на ограниченном множестве F (2.14).

Поэтому в качестве реализуемого проектора может быть использована пара

матриц

(4.4)

(T^∗, Q^∗) = arg max

F (T, Q).

158

5. Cлучайные матрицы-проекторы с заданными значениями элементов

1. Множество (0, 1)-матриц-проекторов и его упорядочение

Рассмотрим процедуру проектирования на пространство R^r(m), осуществ-

ляемого матрицей-проектором Q_(s×r) со случайными элементами, принима-

ющими значения 0 или 1.

Представим матрицу вектором-строкой длины sr. Количество различных

последовательностей из 0 и 1, т.е. количество различных векторов-строк рав-

но N = 2^rs. В качестве примера для s = 3, r = 1 таких векторов будет 8:

000, 100, 010, 001, 110, 011, 101, 111;

для s = 4, r = 1 их будет 16:

0000, 1000, 0100, 0010, 0001, 1100, 0110, 0011,

1001, 0101, 1010, 1111, 1110, 0111, 1011, 1101.

Для матрицы-проектора Q_(s×r) существует конечное множество Q ее (0, 1)-

реализаций:

(5.1)

Q = {Q⁽¹⁾,...,Q^(N)},

N =2^sr.

Полагая, что реализации случайные, их вероятностные свойства будем харак-

теризовать функцией дискретного распределения вероятностей (ДРВ) W (α)

с дискретным носителем α ∈ A = [1, N], где

(5.2)

W (α) = w = {w_α

α = 1,N}.

Матрица-проекция





y^(α)(1)





Y(α)(m×r) =





U_(m×s)Q^(α)(s×r);



=

(5.3)

y^(α)

(m)

∑

y^(α,i)j =

u_ikq^(α)kj, i = 1,m; j = 1,r.

k=1

Индикатор компактности множества Y^(α):

∑

(

)

(5.4)

ρ^(α)Y(Q) =

̺^(α) y^(κ),y^(β) |Q^(α)

(s×r)

m(m - 1)

(κ,β)=1, κ<β

Упорядочим последовательность (5.1) в соответствии со следующей последо-

вательностью неравенств:

(5.5)

0 < ρ^(1)Y(Q) < ρ^(2)Y(Q) < ··· < ρ^(N)Y

(Q).

159

2. MEE-оценка функций ДРВ

MEE-оценка функции ДРВ W (α) определяется следующим алгоритмом:

∑

(5.6)

H(w) = - w_α ln w_α

⇒ max

α=1

при ограничениях:

нормировка

∑

(5.7)

w_α

= 1,

α=1

баланс индикаторов компактности

∑

(5.8)

w_α ρ^(α)Y(Q) = ρ_U .

α=1

Задача (5.6)-(5.8) является конечномерной задачей на условный экстре-

мум с вогнутой целевой функцией (информационной энтропией) и линейны-

ми ограничениями-равенствами.

Рассмотрим функцию Лагранжа

(

) (

)

∑

(5.9)

L(w, λ) = H(w) + µ

w_α

+ λ ρ_U - w_αρ^(α)Y(Q)

α=1

Из условий стационарности этой функции получаем, что энтропийно-опти-

мальное распределение вероятностей имеет вид

(

)

(α)

exp

-λρ

(Q)

(5.10)

w^∗α =

α = 1,N,

(

)

∑

exp

-λρ^(α)Y(Q)

α=1

где параметр λ определяется из следующего уравнения:

∑

(

)(

)

(5.11)

exp

-λρ^(α)Y(Q) ρ^(α)(Q) - ρU

= 0,

-∞ < λ < ∞.

α=1

Воспользуемся заменой z = exp(-λ). Тогда уравнение (5.11) примет вид

∑

(5.12)

ϕ(z) =

zhα c_α = 0, z ≥ 0; c_α = (h_α - ρ_U ), h_α = ρ^(α)Y.

α=1

160

Теорема 1. Пусть существует α = l такое, что

c_α < 0

для α = 1, . . . , l,

(5.13)

c_α

≥0

для α = l + 1, . . . , N,

и согласно (5.5)

(5.14)

0<h₁ <h₂ <···<h_l <h_l+1 <···<h_N.

Тогда уравнение (5.12) имеет единственное положительное решение z^∗ > 0.

Доказательство приведено в Приложении.

3. Стратегии выбора “подходящей” матрицы-проекции из Q (5.1)

Энтропийно-оптимальная ДРВ W^∗(α) = w^∗α, α = 1, N (5.12) характери-

зует вероятности реализации элементов (матриц-проекторов) из множе-

ства Q (5.1). Но для формирования конкретной матрицы-проекции Y_(m×r)

необходима конкретная матрица-проектор из множества Q. Можно предло-

жить следующие стратегии для осуществления указанного выбора.

1. Матрица-проекция с максимальной вероятностью. Пусть в (5.5) раз-

ность Δ_ρ = ρ^(N)Y - ρ^(1)Y достаточно велика. Это означает, что в ДРВ (5.12)

максимальное значение вероятности существенно больше минимального. То-

гда реализуемая матрица-проектор имеет номер

(5.15)

α^∗ = arg max

w^∗α.

1≤α≤N

2. Средняя матрица-проектор. В случае, когда Δ_ρ = ρ^(N)Y - ρ^(1)Y мала, воз-

растание последовательности {ρ^(α)} происходит с небольшой скоростью. По-

этому целесообразнее использовать осреднение для определения реализуемой

матрицы-проектора:

∑

(5.16)

α = αw^∗α,

α^∗

= ⌊α⌋,

α=1

где ⌊•⌋ целая часть числа •.

3. Медианная матрица-проектор определяется следующим равенством:

∑

(5.17)

w^∗α =

w^∗α.

α=1

α=α^∗+1

4. Осреднение матриц-проекций. Данная стратегия состоит из следую-

щих этапов. На первом этапе выделяются подмножества матриц-проекторов,

обладающие определенными свойствами. На втором формируется подмно-

жество соответствующих им матриц-проекций. Затем вычисляется средняя

матрица-проекция.

Если второй и третий этапы связаны со стандартными для математической

статистики вычислениями, то первый требует дополнительных комментари-

ев. Выделение подмножеств матриц-проекторов основано на правилах, ко-

торые отображают желаемые свойства этих подмножеств. В зависимости от

161

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

персионные и интерквартильные подмножества.

Рассмотрим дисперсионные подмножества, для чего вычислим средне-

квадратичное значение (с.к.з.) переменной α:

√

∑

(5.18)

σ^∗α = ⌊σ⌋,

σ=

D_α, D_α = (α^∗ - α)²w_α.

α=1

Определим дисперсионный интервал

[

]

(5.19)

I_α = α^∗ - σ^∗α,α^∗ + σ^∗

Дисперсионное подмножество:

{

}

Q=Q(α^∗-σ^α)_,...,Q(α^∗+σ^α)

(5.20)

Для каждого элемента этого подмножества вычисляются соответствующие

матрицы-проекции:

{

}

(5.21)

Y = Y(α∗-σα)(m×r),...,Y(α∗+σα)

(m×r)

На последнем этапе вычисляется средняя по дисперсионному множеству

матрица-проекция:

α^∗+σ^∗α∑

(5.22)

Y^D(m×r) =

Y(α)(m×r).

2σ^∗α

α=α^∗-σ^∗α

Рассмотрим процедуру формирования интерквартильных подмножеств.

Энтропийно-оптимальная функция распределения вероятностей, согласно

(5.10), имеет вид

∑

(5.23)

F^∗(β) =

w^∗α

β ∈ [0,N].

α=1

Напомним, что κ^∗-квартилью случайной переменной α является множе-

ство A(κ∗) ее значений [1, β^∗], где β^∗ есть целая часть решения уравнения

F^∗(β) = κ^∗.

Рассмотрим два квартильных множества: A(κ1) и A(κ2), причем κ^∗1 > κ^∗2.

Каждому из этих множеств соответствуют подмножества матриц-проекто-

ров:

{

}

Q(κ^∗1

)= Q⁽¹⁾,...,Q(α(κ1))

{

}

(5.24)

Q(κ^∗2

)= Q⁽¹⁾,...,Q(α(κ2))

162

где α(κ) - количество элементов в подмножестве Q(κ). Образуем подмноже-

ство матриц-проекторов

{

}

(5.25)

Q(κ^∗1 - κ^∗2)= Q(α(κ2)),...,Q(α(κ1))

которое является (κ^∗1 - κ^∗2)-интерквантильным подмножеством I(κ1-κ2)

энтропийно-оптимальных матриц-проекторов. Количество элементов в этом

подмножестве равно M_(κ∗-κ∗2) = α(κ1) - α(κ2).

Для каждого элемента подмножества Q(κ^∗1 - κ^∗2) (5.25) вычисляются соот-

ветствующие матрицы-проекции

{

}

(5.26)

Y(κ^∗1 - κ^∗2) = Yα(κ2),...,Yα(κ1)

(m×r)

Средняя по подмножеству I(κ1-κ2) матрица-проекция:

α(κ^∗1)∑

(5.27)

Y^K(m×r) =

Y^α(m×r).

M_(κ∗-κ∗)

α=α(κ^∗2)

6. Алгоритм энтропийно-рандомизированного проектирования

с заданными значениями элементов матриц-проекторов

dERP -алгоритм состоит из двух последовательных этапов. На первом вы-

числяется энтропийно-оптимальная ДРВ на множестве заданных матриц-

проекторов, сохраняющая индикатор компактности матрицы данных. Второй

этап состоит в реализации “подходящей” матрицы-проектора из заданного

множества с учетом энтропийно-оптимальной ДРВ.

Алгоритм 1 (dERP-алгоритм).

Шаг 0. Нормировка матрицы-данных

u_ij - u_min

u_ij :=

i = 1,m; j = 1,s.

u_max - u_min

Шаг 1. Вычисление индикатора компактности матрицы данных

∑

2!(m - 2)!

ρ_U :=

̺(u^(β), u^(γ)).

β,γ=1, γ<β

Шаг 2. Генерация множества Q матриц-проекторов с элементами 0,1

Q^(α),

α = 1,N, N = 2^rs.

Шаг 3. Формирование множества Y матриц-проекций с элементами

∑

y^(α)i,k :=

u_i,νq^(α)ν,k,

i = 1,m, k = 1,r,

ν=1

163

и векторами-строками

{

}

y^αν := y^(α)ν,1,... ,y^(α)

ν = 1,m.

ν,r

Шаг 4. Вычисление индикаторов компактности матриц-проекций

∑

ρ^(α)Y :=2!(m-2)!

̺(y^(ν), y^(µ)),

α = 1,N.

ν,µ=1, ν<µ

Шаг 5. Определение значения множителя Лагранжа λ^∗ из уравнения

∑

(

)(

)

exp

-λρ^(α)Y(Q) ρ^(α)(Q) - ρU

= 0,

-∞ < λ < ∞,

α=1

и определение энтропийно-оптимальной ДРВ

(

)

(α)

exp

-λρ

(Q)

w^∗α =

α = 1,N.

(

∑

exp

-λρ^(α)Y(Q)

α=1

Шаг 6. Формирование и выбор стратегий реализации энтропийно-опти-

мальных матриц-проекторов:

матрица-проекция с максимальной вероятностью

Q(α∗) : α^∗ = arg maxw(α |λ^∗);

средняя матрица-проекция

∑

Q^(α) : α =

αw^∗α;

α=1

медианная матрица-проектор

∑ N∑

Q^(α) :

w^∗α;

α=1

α=α+1

средняя по дисперсионному подмножеству матрица-проекция

α^∗+σ^∗α∑

Y^D(m×r) =

Y(α)(m×r),

2σ^∗α

α=α^∗-σ^∗α

средняя по (κ^∗1 - κ^∗2)-интерквартильному подмножеству матрица-

проекция

α(κ^∗1)∑

Y^K(m×r) =

Y^α(m×r).

M_(κ∗-κ∗)

α=α(κ^∗2)

Матрицы-проекции, вычисляемые на 6-м шаге алгоритма, могут исполь-

зоваться как исходные матрицы данных для решения задач машинного обу-

чения.

164

7. Заключение

Предлагается новый метод “сжатия” и “растяжения” матрицы данных, ос-

нованный на энтропийно-рандомизированном проектировани (ERP). Сфор-

мулирован алгоритм ERP в виде задачи условной максимизации функциона-

ла энтропии, определенного на функциях ПРВ матриц-проекторов. Получе-

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

занной задаче. Рассмотрен случай конечных множеств матриц-проекторов,

на которых существуют дискретные функции распределения вероятностей

(ДРВ) и сформулирован алгоритм их энтропийной оптимизации. Реализа-

ция энтропийно-рандимизированных проекций осуществляется сэмплирова-

нием оптимальных ПРВ (ДРВ), генерацией множеств матриц-проекторов и

использованием их числовых характеристик: средних, медианных, средних

по дисперсионному или интерквартильному множеству.

ПРИЛОЖЕНИЕ

Доказательство теоремы 1. Воспользуемся условиями (5.13), (5.14),

и уравнение (5.12) представим в виде

^N z^hαc_α

(Π.1)

φ(z) =^α=l+1

= 1.

∑

z^hαc_α

α=1

Согласно (5.5) h_l+1 - h₁ > 0, и

^N z^hαc_α + c_l+1

(Π.2)

φ(z) = z(hl+1-h1)α=l+2

∑

zhαc_α + c₁

α=2

Отсюда следует, что

φ(0) = 0.

Представим теперь функцию φ(z) в виде

∑

zhα-hN c_α + c_N

(Π.3)

φ(z) = z(hN -hl)α=l+1

∑

z^hα^-hlc_α + c_l

α=1

Нетрудно увидеть, что

φ(∞) = +∞.

165

Рассмотрим производную

∑

c_β c_α(h_α - h_β)z(hβ-hα)

(Π.4)

φ^′(z) =^β=1α=l+1(

)₂

> 0.

∑

c_α zhα

α=1

Следовательно, функция φ(z) монотонно-возрастающая, и уравнения (Π.1),

(Π.2) имеют единственное положительное решение z^∗ > 0.

СПИСОК ЛИТЕРАТУРЫ

Carreira-Perpinan M.A. A review of dimension reduction techniques. Tachnical

report CS-96-09, Department of Computer Science, University of Sheffield, 1997.

Imola K. A survey of dimension reduction techniques. Center for Applied Scientific

Computing, Lawrence Livermore National Laboratory, 2002.

Cunningham P. Dimension Reduction. Technical Report UCD-CSI-2007-7, Univer-

sity College Dublin, 2007.

Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная

статистика. Классификация и снижение размерности. М.: Финансы и стати-

стика, 1989.

Friedman J., Hastie T., Tibshirani R. Element of Statistical Learning: Prediction,

Inference and Data Mining. Springer, 2001.

Bishop C. Pattern Recognition and Machine Learning, ser. Information Science and

Statistics, Springer, 2006.

Comon P., Jutten C. Handbook of Blind Source Separation. Independent Compo-

nent Analysis and Applications. Academic Press, Oxford UK, 2010.

Bruckstein A.M., Donoho D.L., Elad M. From Sparse Solutions of Systems of Equa-

tions to Sparse Modeling of Signals and Images. SIAM Rev. 2009. V. 51. No. 1.

P. 34-81.

Pirson K. On lines and planes of closest fit to systems of points in space // Philo-

sophical Magazine. 1901. V. 2. P. 559-572.

10.

Кендал М.Дж., Стюарт А. Статистические выводы и связи / Пер. с англ. М.:

Наука, 1973.

11.

Jolliffe I.T. Principal Component Analysis. N.Y. Springer-Verlag, 2002.

12.

Поляк Б.Т., Хлебников М.В. Метод главных компонент: робастные версии //

АиТ. 2017. № 3. C. 130-148.

Polyak B.T., Khlebnikov M.V. Principle component analysis: Robust versions //

Autom Remote Control 2017. V. 78. P. 490-506.

https://doi.org/10.1134/S0005117917030092.

13.

Deerwester S.C., Dumias S.T., Landaurer T.K., Furnas G.W., Harshman R.A.

Indexing by latent semantic analysis // J. American Society of Information Sciences.

1990. V. 41. No. 6. P. 391-407.

14.

Fisher R.A. The Use of Multiple Measurements in Taxonomic Problems // Annals

of Eugenics. 1936. V. 7. P. 179-188.

15.

McLachlan G.J. Discriminant Analysis and Statistical Pattern Recognition. Wiley

Interscience, 2004.

166

16.

Johnson W.B., Lindenstrauss J. Extension Of Lipshitz mapping into Hilbert

space // In: Conference in modern analysis and probability. American Mathematical

Society. 1984. V. 26. P. 189-206.

17.

Achlioptas D. Database-friendly random projections // Proceedings of the twentieth

ACM Symposium on Principles of database systems. P. 274-281.

18.

Bingham E., Mannila H. Random projection in dimensionality reduction: applica-

tions to image and text data // Proceedings of the seventh ACM SIGKDD inter-

national conference on Knowledge discovery and data mining. P. 245-250.

19.

Vempala S.S. The random projection method. American Mathematical Society,

2005. V. 65.

20.

Ганин И.П., Косиченко Е.А., Каплан А.Я. Особенности ЭЭГ-реакций на эмоци-

онально значимые стимулы в тезнологии интерфейса мозг-компьютер на волне

Р300 // Журн. высш. нерв. деятельности им. И.П. Павлова. 2017. Т. 67. № 4.

С. 453-463.

21.

Huber F., Zorner T.O. Threshold cointegrationin international exchange rates:

A Bayesian approach // International Journal of Forecasting. 2019. V.

35.

P. 458-473.

22.

Kosinskia M., Stillwella D., Groepelb T. Private traits and attributtes are pre-

dictable from digital records of human behaviour // Proceedings of the National

Agademy of Sciences of the USA. 2013. 110(15). P. 5802-5805.

23.

Blum A., Langly P. Selection of relevant feature and examples in machine learn-

ing // Artificial Intelligence. 1997. V. 97. Nos. 1-2. P. 245-271.

24.

Cover T.M., Thomas J.A. Elements of Information Theory. N.Y.: John Wiley and

Sons, 1991.

25.

Peng H.C., Long F., Ding C. Feature selection based on mutual information: criteria

of max-dependency, max-relevance, and min-redudancy // IEEE Transaction on

Pattern Analysis and Machine Intelligence. 2005. V. 27. No. 8. P. 1226-1238.

26.

Zhang Y., Li S., Wang T., Zhang Z. Divergence-based feature selection for separate

classes // Neurocomputing. 2013. V. 101. P. 32-42.

27.

Дарховский Б.С., Каплан А.Я., Шишкин С.Л. О подходе к оценке сложности

кривых (на примере электроэнцефалограммы человека) // АиТ. 2002. № 3.

С. 134-140.

Darhovsky B.S., Kaplan A.Ya., Shishkin S.L. On an Approach to the Estimation

of the Complexity of Curves (Using as an Example an Electroencephalogram of a

Human Being) // Autom. Remote Control. 2002. V. 63. No. 3. P. 468-474.

28.

Дарховский Б.С., Пирятинская А. Новый подход к проблеме сегментации вре-

менных рядов произвольной структуры // Труды МИАН им. В.А. Стеклова.

2014. Т. 287. С. 61-74.

29.

Darhovsky B., Piryatinska A. Quickest detection of changes in the generating mech-

anism of a time series via the ε-complexity of continuous functions // Sequantial

Analysis. 2014. V. 33. P. 231-250.

30.

Efron B. Bootstrap Methods: Another Look at the Jackknife // Annals of Statistics.

1979. V. 7. No. 1. P.1-26.

31.

Bach F.R. Bolasso: model consistent Lasso estimation through the bootstrap //

Proceedings of the 25-th International Conference on Machine Learning. 2008.

P. 33-40.

32.

Попков Ю.С. Асимптотическая эффективность оценок максимальной энтро-

пии // Доклады Российской Академии Наук. Математика, Информатика, Про-

цессы Управления. 2020. Т. 493. С. 104-107.

https://doi.org/10.31857/S2686954320040165.

167