Автоматика и телемеханика, № 9, 2019

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

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

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

Департамент программной инженерии, ОРТ Брауде Колледж, Кармиель, Израиль;

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

Ханты-Мансийск;

Московский физико-технический институт)

ПРОЦЕДУРЫ РАНДОМИЗИРОВАННОГО МАШИННОГО ОБУЧЕНИЯ¹

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

компьютерной имитации энтропийно-оптимальных рандомизированных

моделей. Рассмотрены процедуры рандомизированного машинного обу-

чения (РМО) с “жесткой” и “мягкой” рандомизацией, которые сводят-

ся либо к точному воспроизведению эмпирических балансов в первом

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

симации. Сформулированы алгоритмы РМО в виде функциональных за-

дач энтропийно-линейного программирования. Приведены примеры при-

менения РМО в задачах классификации текстов и рандомизированного

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

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

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

лансы, классификация текстом, динамическая регрессия.

DOI: 10.1134/S0005231019090095

1. Введение

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

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

знаем или знаем не полностью. Другими словами, приходится исследовать,

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

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

Тем не менее, мы оперируем уровнем неопределенности, полагая, что его

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

необходимо как-то имитировать (моделировать) неопределенность. Наиболее

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

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

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

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

теориях — вероятности, статистики, оптимизации и др.

Стохастическая природа неопределенности мотивирует ее моделирование

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

мизированной средой. Разумеется эта среда не произвольная, а отражающая

предположительно существующие особенности неопределенности.

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

29-02115).

122

Одним из носителей этих особенностей неопределенности являются дан-

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

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

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

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

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

на эту тему, в виде концепции Data Mining появились в публикациях [1, 2].

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

ской статистики и теории вероятности, погруженные в дружественную для

пользователя информационно-технологическую среду. Журнал Nature посвя-

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

выпуск [3], в котором были сформулированы так называемые “5V” атрибут,

характеризующие данные, пригодные для указанной цели.

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

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

ром является компьютер, на котором обучается указанная модель с помо-

щью соответствующего информационного и алгоритмического обеспечения.

Поэтому процедуры и алгоритмы машинного обучения (МО) являются клю-

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

что МО имеет более чем 60-летнюю историю и опыт решения многочислен-

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

Ф. Розенблатт создал персептрон МАРК I [4]. Понятие эмпирического риска,

ключевое для МО-процедур, было введено в монографии Я.З. Цыпкина [5].

Метод потенциальных функций в задачах классификации и распознавания

был опубликован в 1970 г. в монографии М.А. Айзермана, Э.М. Бравермана,

Л.И. Розоноэра [6]. Основные идеи машинной классификации были опубли-

кованы в монографиях [7, 8], а реализованы они в методе SVM существен-

но позднее [9]. Современный референс-лист работ, посвященных машинно-

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

можно посвятить отдельную статью. Но все-таки, некоторые из них следует

упомянуть (исключительно по календарному принципу) [10-18].

Существующие представления о МО базируются на параметризованных

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

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

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

проблемам машинного обучения (РМО), особенность которого состоит в том,

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

данные используются для оценивания не их значений, а функций плотности

распределения вероятностей параметров. Смысл такого подхода состоит в

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

ры, как правило, погружены в некоторую неопределенную среду. Если речь

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

стью. Формирование моделей и их параметризация — процесс неформализуе-

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

Поэтому в массовом применении МО-процедур уровень неопределенности до-

статочно высок.

123

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

плотности распределения вероятностей параметров и шумов, в соответствии

с которыми генерируются ансамбли моделей “наилучших” в условиях макси-

мальной неопределенности. В статье рассмотрены два класса РМО-алгорит-

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

данными. В одном из них предполагается так называемая “жесткая” балан-

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

ными. В другом используется “мягкая” балансировка, когда выход приближен

к реальным данным оптимально в терминах принятого критерия.

В обоих классах РМО обученная модель генерирует ансамбли случайных

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

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

шумов. Эти ансамбли используются для решения задач “мягкой” (с вероятно-

стью) классификации и кластеризации, а также для задач рандомизирован-

ного прогнозирования с использованием моделей динамического регрессии.

2. РМО-процедура, структура и классификация

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

му обучению, направленным на повышение достоверности, надежности и

гибкости МО-процедур в условиях неопределенности и функционирова-

ния как при больших, так и при ограниченных объемах данных. Для до-

стижения этих декларируемых целей предлагается комплекс структурных,

информационно-технологических и алгоритмических модификаций стан-

дартных МО-процедур. При этом используется те же коллекции данных для

реализации РМО-процедур. Они состоят из двух массивов данных, которые

будем называть входными X и выходными Y .

Данные в указанных массивах измеряются в дискретные моменты вре-

мени j = 1, . . . , s. Поэтому входные данные характеризуются матрицей X =

= [x⁽¹⁾, . . . , x(s)], а выходные

— матрицей Y = [y⁽¹⁾, . . . , y(s)]. Векторы

x(j) ∈ Rⁿ, y(j) ∈ R^m. Предполагается, что массив входных данных содер-

жит точные данные, а массив выходных данных — с ошибками интер-

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

Ξ=

ξ⁽¹⁾,...

ξ(s)]. Случайные вектор

ξ(j) ∈ R^m, j = 1,s, - независимые и

компоненты их также независимые:

ξ(j)i ∈ E(j)i = [ξ^-i(j),ξ+i(j)], i = 1,m, j = 1,s;

⋃

(1)

ξ(j) ∈ Ξ_j =

E(j)i.

i=1

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

распределения вероятностей (ПРВ) Q_j

ξ(j)), j = 1,s. Предполагается, что

ПРВ — непрерывно дифференцируемые функции.

Структура РМО-процедуры представлена на рис. 1. Ее основными эле-

ментами являются рандомизированная параметризованная модель (РПМ) и

алгоритм рандомизированного машинного обучения (РМО-А).

124

Рис. 1. Структура РМО-процедуры.

1. РПМ преобразует массив входных данных X в модельный выход, ха-

рактеризуемый матрицей Z = [z⁽¹⁾, . . . , z(s)], где z(j) ∈ R^m. В общем случае

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

ской. Это означает, что модельный выход, наблюдаемый в момент време-

ни j, зависит от входа, наблюдаемого на некотором историческом интервале

j - ϱ,...,j, т.е. от матрицы X_ϱ(j) = [x(j-ϱ),...,x(j)]. Математическим обра-

зом этой связи является векторный функционалΩ(X_ϱ(j) | a, P (a)) со случай-

ными параметрами a интервального типа

(2)

a ∈ A = [a^-,a⁺

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

сти распределения вероятностей (ПРВ) P (a), которая предполагается

непрерывно-дифференцируемой.

Выход РПМ в j-й момент времени представляет собой ансамбл

Z(j | P (a))

случайных векторов

(3)

z(j | a) =Ω(X_ϱ

(j) | a, P (a)),

j = 1,s.

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

(4)

v(j | a

ξ(j)) = z(j |a)

ξ(j)

j = 1,s,

образующие ансамбль V(j | P (a), Q_j

ξ(j))). Вероятностные свойства этого ан-

самбля зависят от ПРВ P (a) и Q₁

ξ⁽¹⁾),... ,Q_s

ξ(s)). Смысл рандомизирован-

ного обучения состоит в определении таких функций ПРВ, в которых бы

учитывались условия балансирования ансамбля V(j | P (a), Q_j

ξ(j))) c выход-

ными обучающими данными Y (эмпирические балансы).

2. РМО-А представляет собой обучающий модуль, в котором формали-

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

125

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

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

пии [19, 20], определенный на функциях ПРВ P (a) случайных параметров

РПМ и функциях ПРВ Q₁

ξ⁽¹⁾),... ,Q_s

ξ(s)) шумов:

∫

P (a)

H[P (a), Q₁

ξ⁽¹⁾),... ,Q_s

ξ(s))] = - P(a) ln

da-

P⁰(a)

∫

∑

Q_j

ξ(j))

(5)

Q_j

ξ(j)) ln

ξ(j),

Q0j

ξ(j))

j=1

Ξ_j

где P⁰(a), Q0j

ξ(j)) — априорные ПРВ параметров и шумов.

Eго максимизация гарантирует получение наилучших решений при мак-

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

рована в [21] (см. также [22-25]). Информационная энтропия характеризует

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

шумами наблюдений. Поэтому максимум энтропии соответствует наилучшим

оценкам для максимально неопределенных (в единицах энтропии) шумов.

Алгоритмы РМО можно разделить на два класса, в одном из которых

реализуется принцип “жесткой” рандомизации, а в другом — “мягкой” рандо-

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

эмпирических балансов — точно или приближенно.

2.1. Под “жесткой” рандомизацией понимаются равенства между число-

выми характеристиками ансамбля V(j | P (a), Q_j

ξ(j))) и выходными обучаю-

щими данными Y :

[

]

(6)

m(k) j |P(a),Q_j

ξ(j))

= y(j),

j = 1,s.

Здесь m(k)[j | P (a), Q_j

ξ(j))] — вектор k-средних с компонентами следующего

вида:

[

]

[

]1/k

(7)

m(k)i j |P(a),Q_j

ξ(j)) = MP{zki ((j |a))} + MQj{ξki (j)}

где M_P , MQj — операторы математического ожидания по ПРВ P , Q_j соот-

ветственно. Здесь для характеризации эмпирических балансов при “жесткой”

рандомизации будет использоваться 1-средние, т.е.:

[

]

(8)

m⁽¹⁾ j |P(a),Q_j

ξ(j))

= y(j),

j = 1,s.

где

∫

m(1)i(j |P(a),Q_j

ξ(j))) =

P (a)z_i(j |a)da + Q_j

ξ(j))ξ(j)i

ξ(j),

(9)

Ξ_j

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

126

2.2.

При

“ мягкой” рандомизации балансы между ансамблем

V(j | P (a), Q_j

ξ(j))), состоящим из случайных векторов

v(j | a

ξ(j)) (4), и

выходными обучающими данными — (s × m)-матрицей Y = {y⁽¹⁾, . . . , y(s)}

выполняются приближенно в терминах принятого критерия.

Для формирования подходящего критерия обратимся к равенству (4),

определяющему случайные j-векторы, входящие в ансамбль V. Близость век-

торв v(j | a) и y(j) будем оценивать какой-либо гельдеровской векторной нор-

мой [26]:

(10)

N(j)(a

ξ(j),y(j)) = ∥z(j |a) - y(j)

ξ(j)∥_H ≤ N(j)z,y(a,y(j)) + N_Ξ

ξ(j)

где

(11)

N(j)z,y(a,y(j)) = ∥z(j |a) - y(j)∥_H,

(12)

N(j)ξ

ξ(j)) =

ξ(j)∥_H.

Норма (11) характеризует различие между вектором выхода модели и векто-

ром обучающих данных, а норма (12) — “мощность” шумов.

Заметим, что нормы (11) и (12) являются функциями случайных аргумен-

тов: параметров a и шумо

ξ(j). Определим их математические ожидания:

∫

N (j)

z,y

[P (a)] = P (a)N(j)z,y(a, y(j))da,

∫

N(j)

(13)

[Q_j

ξ(j))] =

Q_j

ξ(j))N_ξ

ξ(j))

ξ(j).

Ξ_j

Качество приближения эмпирических балансов и оценивания “мощности”

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

ми (13).

3. РМО-алгоритмы с “жесткой” рандомизацией

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

ских балансов. Поэтому соответствующий ей РМО-А формулируется в сле-

дующем виде:

∫

P (a)

H[P (a), Q

ξ)] = - P (a) ln

da-

P⁰(a)

∫

∑

Q_j

ξ(j))

(14)

Q_j

ξ(j)) ln

ξ(j)

⇒ max

Q0j

ξ(j))

j=1

Ξ_j

при условиях:

— нормировки функций ПРВ

∫

(15)

P (a)da = 1,

Q_j

ξ(j))

ξ(j)

= 1, j = 1, s;

Ξ_j

127

— эмпирические балансы с использованием 1-средних

(16)

m⁽¹⁾(j |P(a),Q_j

ξ(j)

)) = y(j),

j = 1,s.

Здесь P⁰(a), Q0j

ξ(j)) — априорные ПРВ параметров и шумов; вектор m(k)

имеет компоненты (9). Задача (14) и (16) является функциональной зада-

чей энтропийно-линейного программирования ляпуновского типа [27-31] (все

компоненты задачи описываются интегральными функционалами). Для за-

дач этого типа условия оптимальности могут быть получены с использо-

ванием функционала и множителей Лагранжа. Поскольку функции ПРВ

в РМО-А — непрерывно-дифференцируемые, то вариация функционала

Лагранжа может быть определена с использованием производных Гато [32].

Введем следующие обозначения:

• переменная

∫

(17)

w(P (a)) = 1 -

P (a) da;

• вектор q(Q

ξ)) с компонентами

∫

(18)

q_j(Q_j

ξ(j))) = 1 - Q_j

ξ(j))

ξ(j)

j = 1,s;

Ξ_j

• векторы

(19)

e(j)(P(a),Q

ξ)) = y(j) - m⁽¹⁾(j | P (a), Q_j

ξ(j)

)).

• множители Лагранжа μ; ν₁, . . . , ν_s; θ(1), . . . , θ(s).

Здесь Q

ξ) = [Q₁

ξ⁽¹⁾),... ,Q_s

ξ(s))]. Используя введенные обозначения, опре-

делим функционал Лагранжа

L[P (A), Q

ξ)] = H[P (a), Q

ξ)] + μw(P (a)) + 〈ν, q(Q

ξ))〉+

∑

(20)

〈θ(j),e(j)(P(a),Q(ξ

))〉.

j=1

В этом равенстве 〈•, •〉 — скалярное произведение.

Условия стационарности функционала (20) в терминах производных Гато

имеют вид:

∑

P^∗(a)

+1+μ+

〈θ(j),ê(j)〉 = 0,

P⁰(a)

j=1

Q^∗j

ξ(j))

(21)

+1+ν_j +〈θ(j)

ξ(j)

〉 = 0,

Q0j

ξ(j))

j = 1,s.

128

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

раметров РПМ и шумов измерений:

⎡

⎤

∑

P^∗(a) = P⁰(a)exp ⎣-1 - μ -

〈θ(j),z(j)〉⎦ ,

j=1

[

]

(22)

Q^∗j

ξ(j)) = Q0j

ξ(j))exp

-1 - ν_j - 〈θ(j)

ξ(j)〉 ,

j = 1,s.

Используя условия нормировки (17) и (18), можно исключить множители

Лагранжа μ и ν. Тогда выражения для энтропийно-оптимальных и нормиро-

ванных функций ПРВ примут вид:

[

]

∑

P⁰(a)exp -

〈θ(j),z(j)〉

j=1

P^∗(a) =

P(^θ)

[

]

Q0j

ξ(j))exp

-〈θ(j)

ξ(j)〉

(23)

Q^∗j

ξ(j)) =

Q_j(θ(j))

j = 1,s.

В этих равенствах

⎡

⎤

∫

∑

P(^θ) = P⁰(a) exp ⎣-

〈θ(j),z(j)〉⎦ da,

j=1

∫

[

]

(24)

Q_j(θ(j)) = Q0j

ξ(j))exp

-〈θ(j)

ξ(j)〉

ξ(j)

j = 1,s.

Ξ_j

Здесь^θ = {θ(1), . . . ,θ(s)}. Из (23) и (24) следует, что энтропийно-оптимальные

функции ПРВ принадлежат экспоненциальному семейству, параметризован-

ному множителями Лагранжа.

Значения указанных множителей Лагранжа определяются следующими

уравнениями, возникающими из эмпирических балансов (16) при подстановке

в них функций ПРВ из (23) и (24):

⎡

⎤

∫

∑

P-1(^θ) P⁰(a) exp ⎣-

〈θ(j),z(j)〉⎦ da +

j=1

∫

[

]

(25)

+Q-1j(^θ) Q0j

ξ(j))exp

-〈θ(j)

ξ(j)〉

ξ(j) = y(j),

Ξ_j

j = 1,s.

129

Уравнения (25) образуют особый класс нелинейных уравнений, в которые

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

мости левых частей этих уравнений от множителей Лагранжа^θ.

4. РМО-алгоритмы с “мягкой” рандомизацией

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

ближенно в рамках условной минимизации синтетического функционала (5)

и (13):

∑

N (j)

J [P (a), Q

ξ)] = H[P (a), Q

ξ)] -

(P (a)) -

z,y

j=1

(26)

∑

N(j)

(Q_j

ξ(j))) ⇒ max,

j=1

при условиях нормировки ПРВ

∫

(27)

P (a)da = 1,

Q_j

ξ(j))

ξ(j)

= 1, j = 1, s.

Ξ_j

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

условий оптимальности в терминах производных Гато [32].

Будем иметь:

[

]

(

)

∑

P⁰(a)exp -

z,y (a,y(j)) + N(j)ξ

ξ(j))

j=1

P^∗(a) =

[

]

(j)

exp -Nξ

ξ(j))

(28)

Q^∗j

ξ(j)) =

j = 1,s,

Q_j

где

∫

P = P^∗(a)da,

^A∫

(29)

Q_j = Q^∗j

ξ(j))

ξ(j)

j = 1,s.

Ξ_j

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

ные ресурсы только на вычисление многомерных интегралов (29).

130

5. Некоторые приложения рандомизированного машинного обучения

5.1. РМО с “жесткой” рандомизацией для бинарной вероятностной

классификации текстов

Бинарная вероятностная классификация предполагает определение при-

надлежности объекта соответствующему классу с вероятностью, вычисляе-

мой с учетом имеющейся обучающей коллекции.

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

классификатор. Пусть имеются две коллекции текстовых документов: обу-

чающая E = {e₁, . . . , e_m} и тестовая T = {t₁, . . . , t_s}. В обучающей коллекции

документы помечены принадлежностью либо к классу 1, либо к классу 2.

В тестовой коллекции документы никак не помечены.

Документы в обеих коллекциях представлены векторами, компонентами

которых являются веса ключевых слов (термов), встречающихся в докумен-

те. Тем самым формируются наборы векторов, размерность которых равна

количеству n ключевых слов:

E = {e⁽¹⁾,...,e(m)},

e(j) ∈ Rⁿ, j = 1,m,

(30)

T = {t⁽¹⁾,...,t(s)},

t(k) ∈ Rⁿ

k = 1,s.

Здесь Rⁿ — пространство признаков, в данном случае — весов ключевых слов.

1. Э т а п о б у ч е н и я. Документы в обучающей коллекции помечены, т.е.

она состоит из пар “номер документа, класс”: O = {(1, 1), (2, 1), . . . , (m, 1)}

длины m. Трансформируем ее в последовательность чисел из интервала [0, 1],

где номеру элемента в коллекции могут соответствовать числа из интервала

[1/2, 1], если документ принадлежит первому классу, и числа из интервала

[0, 1/2), если документ принадлежит второму классу. Таким образом, получа-

ем “обучающий” вектор y с компонентами, значения которых лежат в интер-

вале [0, 1], и размерностью, равной количеству m документов в коллекции,

т.е.

{

}

(31)

y= y⁽¹⁾,...,y(m)

Рандомизированная модель (решающее правило) представляется случайным

вектором z(e(j), a), зависящим от случайных параметров a однослойной ней-

ронной сети

(

)

(32)

z(j)(a) = sigm

〈e(j), a〉

j = 1,m.

Здесь

(33)

sigm(x) =

1 + exp[-α(x - Δ)]

где параметры α и Δ фиксированы. Аргумент этой функции случайный, так

как параметры a рандомизированной модели случайные. Значения функции

131

sigm(x) на интервале [1/2, 1] соответствуют первому классу, и значения в

открытом интервале [0, 1/2) — второму классу.

В рандомизированной модели (32) параметры a = {a₁, . . . , a_n} — незави-

симые, интервального типа:

a_k ∈ A_k = [a^-k,a+k],

k = 1,n,

⊗

(34)

A= A_k.

k=1

На этих интервальных множествах существует функция ПРВ P (a). Поэтому

для каждого документа с номером j имеет место ансамбл

Z(j) случайных чи-

сел из интервала (0, 1) (32) и (53). Средние значения компонент будут иметь

следующий вид

∫

(

)

(35)

M{z^j(a)} = P (a)sigm

〈e(j), a〉

da.

Итак, РМО-А классификации с “жесткой” рандомизацией представляются

в следующем виде

∫

(36)

H[P (a)] = -

P (a) ln P (a)da ⇒ max

при условиях:

- нормировки

∫

(37)

P (a)da = 1,

- эмпирических балансов

∫

(

)

(38)

P (a)sigm

〈e(j), a〉 da = y(j)

j = 1,m.

Введем множители Лагранжа^θ = {θ₁, . . . , θ_m} для ограничений (38). Тогда

решение этой задачи, согласно (22) и адаптированное к модели (53), с точно-

стью до множителей Лагранжа θ₁, . . . , θ_m имеет вид

W^∗(a)

(39)

P^∗(a) =

P(^θ)^,

где

(

)

(40)

W^∗(a) = exp

-〈θ, z(a)〉

∫

[

]

(41)

P(^θ) = exp

-〈θ, z(a)〉

da.

132

Таблица 1

e(j)1

e(j)2

e(j)3

e(j)4

0,11

0,75

0,08

0,21

0,91

0,65

0,11

0,81

0,57

0,17

0,31

0,91

Множители Лагранжа^θ определяются системой балансовых уравнений (38)

следующего вида

∫

[

]

(42)

P-1(^θ) exp

-〈θ, z(a)〉

z(j)(a)da = y(j)

j = 1,m.

Заметим, что размерность этой системы равна количеству документов в

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

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

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

два примера, которые демонстрируют основную идею РМО-А с “жесткой”

рандомизацией для бинарной классификации текстов.

Пример

1 — Обучение. Размерность алгоритма равна 4, обучающая

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

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

Рандомизированная модель (32) и (53) имеет параметры: α = 1,0 и Δ = 0.

Ответы y = {0,18; 0,81; 0,43} (y_i < 0,5 соответствует классу 2, y_i ≥ 0,5 со-

ответствует классу 1). Множители Лагранжа для энтропийно-оптимальной

ПРВ (39) и (40) имеют следующие значения:^θ = {0,2524; 1,7678; 1,6563}. Па-

раметры a_i ∈ [-10, 10], i = 1, 4. Энтропийно-оптимальная для данной обуча-

ющей коллекции функция W^∗(a) (39) имеет вид

(

)

∑

W^∗(a) = exp

- θ_iz_i(a)

i=1

(

))(-1)

∑

(43)

z_i(a) =

1 + exp

- e(j)_k, a_k

k=1

На рис. 2 показано двумерное сечение функции (39) при a₃ = 0,5; a₄ = 0,5.

2. Э т а п т е с т и р о в а н и я. На этом этапе используется коллекция T =

= {t₁, . . . , t_s}, где каждый элемент коллекции характеризуется вектором

t(j) ∈ Rⁿ. Рассмотрим процедуру классификации для произвольного доку-

мента t(j).

Шаг 1. Генерируется ансамбль

Z(i) выхода рандомизированной модели

(решающих правил) (32) и (53) с функцией P^∗(a) (39). Ансамбль содержит

N случайных чисел из интервала [0, 1].

Шаг 2. Если случайное число из этого ансамбля больше 1/2, то доку-

мент t(i) относится к классу 1. Если — меньше 1/2, то — к классу 2.

Шаг 3. Пусть N₁ чисел оказались в классе 1 и N₂ — в классе 2. Посколь-

ку число испытаний N достаточно велико, то можно считать, что величины

133

W(a)

Рис. 2. Двумерное сечение функции

ПРВ для a₃ = 0,5, a₄ = 0,5,

θ = {3,2807,-3,5127,1,6373}.

p(i)

Класс 1

p(i)

Класс 2

0,8

0,7

0,6

0,5

0,4

0,3

0,2

0,1

100 150 200 250 300 350 400 450 500 0

100 150 200 250 300 350 400

450 500

Тестовые документы

Рис. 3. Эмпирические вероятности принадлежности классам.

p(i)1

= N₁/N и p(i)2 = N₂/N есть эмпирические вероятности попадания доку-

мента t(i) в соответствующий класс. Повторяя операции шагов 2, 3 для всей

коллекции T, получим распределения вероятностей попадания документов в

класс 1 или 2.

Пример

1 — Тестирование. Генерируется массив (500 × 4) четырех-

мерных случайных векторов t(i), i = 1, 500, с независимыми компонентами,

равномерно распределенными в интервалах [0, 1]. Для каждого элемента этой

выборки генерируются случайные параметры модели (32) и (53) в соответ-

ствии с ПРВ (39) и (40) (N = 1000) методом исключения [33] и вычисляется

ее выход. Выполняются шаги 2, 3.

На рис. 3a-3б показаны эмпирические вероятности p(i)1, p(i)2 принадлежно-

сти t_i-документа классу 1 и 2.

134

5.2. РМО с “мягкой” рандомизацией для прогнозирования миграционного

взаимдействия региональных систем

Взаимовлияние миграционных процессов в региональных системах —

проблема, актуальность которой возрастает в современном мире. Неоднород-

ность социально-экономического статуса регионов возрастает вместе с ростом

политической и военной напряженности. Все это приводит к резкому пере-

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

ности регионального населения и росту затрат на его обеспечение. Поэтому

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

алгоритмы, программное обеспечение), позволяющие в режиме адаптации к

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

обеспечивающих ресурсов.

Рассмотрим динамическую модель миграционного взаимодействия с огра-

ничением на общий ресурс и дискретным временем, изложенную в [34]. Она

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

ри системы S₁ и описывается уравнением динамической регрессии:

(44)

K[(s + 1)h] = (A - E)K[sh] + F(z[sh]),

(K, F) ∈ R^N

, s = 0,K - 1,

где A — матрица пространственных передвижек, E — диагональная матрица

мобильности, K[sh] — распределение населения в региональной системе S₁ в

момент времени sh.

Локально-стационарное распределение в момент времени sh иммиграци-

онных потоков из региональной системы S₂ в систему S₁, характеризуемое

энтропийным оператором, моделирует второй блок, допускающий описание

вектор-функцией F(z[sh]) с компонентами

∑

(45)

f_n[sh] = h

b_jn(z[sh])cjn

n = 1,N, s = 0,K - 1.

j=1

Переменная z — экспоненциальный множитель Лагранжа в задаче энтро-

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

решением уравнения

∑

(46)

c_knb_kn(z[sh])ckn

= T[sh],

k=1 n=1

где T [sh] — объем общего для регионов системы S₁ ресурса, который исполь-

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

Входными данными для модели являются объемы T [0], T [h],

...,T[(K - 1)h] и выходными

— распределения регионального населе-

ния K[0], K[h], . . . , K[(K - 1)h] в системе S₁.

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

зирования иммиграционных потоков из Сирии (1) и Ливии (2) (система S₂)

в Германию (1), Францию (2) и Италию (3) (система S₁).

135

Таблица 2

m_n

0,43

0,50

0,40

h1n

0,3

h2n

0,3

h3n

0,5

0,4

b1n

0,4

0,3

b2n

0,3

0,1

0,4

c1n

0,4

0,3

c2n

0,4

0,3

1. Рандомизированная модель, параметры, ошибки измерений, временные

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

ной математической моделью (44)-(46), применив в ней нормализованные

переменные

K_n[sh]

(47)

p_n[sh] =

n = 1,3.

K_max

Получим:

∑

p_n[(s + 1)h] = (1 - b₁m_n)p_n[sh] + hb₁b₂

m_ih_inp_i[sh] + hf_n[sh],

i=1,i=n

∑

(48)

f_n[sh] =

n = 1,3,

b_inbcin3

i=1

∑∑

T [sh] =

c_inb_inbcin3.

n=1 i=1

В этих уравнениях переменные состояния системы S₁ и иммиграционнные

потоки из системы S₂ нормализованы, т.е.

(49)

0 ≤ p_n[sh] ≤ 1,

0≤f_n

[sh] ≤ 1,

n = 1,N.

Переменная z^∗ есть характеристика энтропийного оператора иммиграцион-

ного процесса, которая определяется решением последнего уравнения в (48).

Значения параметров m_i, h_in, b_in и c_in указаны в табл. 2.

Согласно этой таблице m_max = 0,5; h_max = 0,5; b_min = 0,3; b_max = 0,4;

c_max = c_min = c = 0,5. Ошибки измерений численности (в нормализованных

единицах

ξ[sh] ∈ R³ интервального типа

(50)

ξ[sh] ∈ Ξ =

ξ_-

ξ₊],

ξ^±n

= 0,01,

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

мени sh.

Нормализованный наблюдаемый выход модели имеет вид

(51)

v[sh] = p[sh] +ξ

[sh].

136

Таблица 3. Входные и выходные коллекции данных

год

2009

2010

2011

2012

2013

Y₁[s]

81,90

81,77

80,27

80,42

80,64

y₁[s]

1,00

0,998

0,980

0,982

0,985

Y₂[s]

62,47

62,80

63,11

63,41

63,70

y₂[s]

0,762

0,767

0,771

0,774

0,778

Y₃[s]

59,39

59,53

59,63

59,71

59,75

y₃[s]

0,725

0,727

0,728

0,729

0,726

T [s] (млрд)

0,093

0,094

0,095

0,096

0,097

Модель (48) со случайными параметрами будет использоваться для оце-

нивания их характеристик и тестирования на соответствующих временных

интервалах с шагом h = 1 год:

• интервал оценивания T_est = 2009 - 2013 годы;

• интервал тестирования T_tst = 2014 - 2018 годы.

2. Энтропийное оценивание ПРВ параметров и шумов (интервал T_est).

Для решения этой задачи используются данные о распределении населения

в Германии n = 1, Франции n = 2 и Италии n = 3 и об общих затратах на

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

табл. 3, (UNDATA a world information, data.un.org).

В этой модели параметры b₁, b₂, b₃ — случайные со значениями из интер-

валов:

(52)

b₁ ∈ B₁ = [1,0;2,5]; b₂ ∈ B₂ = [0,5;1,8], b₃ ∈ B₃

= [0,3; 1,5].

Cогласно (4)

(53)

U₁ = 0,5; U₂ = 00,5; U₃ = 1,2, U₄

= 0,986.

Тогда метод “мягкого” РМО дает следующие оптимальные ПРВ парамет-

ров и шумов:

(

)

0,5

exp

-0,5b₁ - 0,5b₁b₂ - 1,2b

- 0,986

W^∗(b) =

(

)

∑

exp

n=1

(54)

Q^∗

ξ) =

где

∫

(

)

W =

exp

-0,5b₁ - 0,5b₁b₂ - 1,2b0,53 - 0,986 db₁db₂db₃,

B₁ B₂ B₃

∫

∏

(55)

exp(-ξ²

)dξ.

n=1-0,01

137

10⁵

1,25000

1,24995

1,24990

1,24985

1,24980

1,24975

0,010

0,005

0,010

0,005

0,010

Рис. 5. Двумерное сечение функции ПРВ шума Q^∗(ξ₁, ξ₂, ξ₃), ξ₃ = 0,01, I =

= 7,9992E - 06.

На рис. 4,a-4,в приведены графики двумерных сечений 3-мерных функции

ПРВ параметров, и на рис. 5 — функции ПРВ шума.

3. Тестирование модели. Для тестироваия рандомизированной модели (50)

с оптимальными ПРВ (54) и (55) используются тестовые данные о числен-

ности населения в исследуемых странах из UNDATA a world information

(data.un.org), приведенные в табл. 4. Там же приведены результаты тести-

рования в терминах средних по ансамблю траекторий p₁[sh], p₂[sh], p₃[sh].

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

ванных интервальных параметров, имеющих функции ПРВ (54) и (55),

и построения соответствующих траекторий согласно уравнениям (50). На

рис. 6,a-6,в показаны ансамбли таких траекторий v₁[sh], v₂[sh], v[sh]. На этих

же рисунках нанесены средние v₁[sh], v₂[sh], v₃[sh] по ансамблям траектории

(штриховая линия) и траектории y₁[sh], y₂[sh], y₃[sh] реальных изменений ре-

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

персионных трубок p∗1[sh] ± σ₁, p∗2[sh] ± σ₂, p∗3[sh] ± σ₃ (пунктирная линия).

Таблица 4. Входные и выходные коллекции данных

год

2014

2015

2016

2017

2018

Y₁[s]

81,489

81,707

82,063

82,386

82,674

y₁[s]

0,985

0,988

0,993

0,996

1,000

p₁[sh]

0,986

0,615

0,743

0,639

0,999

Y₂[s]

64,190

64,457

64,791

65,134

65,484

y₂[s]

0,721

0,472

0,564

0,529

0,708

p₂[sh]

0,722

0,695

0,707

0,691

0,715

Y₃[s]

59,585

59,504

59,509

59,516

y₃[s]

0,775

0,609

0,562

0,699

0,650

p₃[sh]

0,776

0,617

0,607

0,705

0,628

T [s] (млрд)

0,097

0,098

139

Погрешность при тестировании оценивалась относительной среднеквадра-

тичной ошибкой

√

(p_n[sh] - y_n[sh])²

s=0

(56)

δ_n

√

∑

(p_n[sh])² +

(y_n[sh])²

s=0

В данном примере она составила: по региону 1 — 4,6 %, по региону 2 — 3,5 %,

по региону 3 — 2,6 %.

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

Рандомизированное машинное обучение является эффективным инстру-

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

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

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

Рассмотрены задачи с “жесткой” и “мягкой” рандомизацией и получены соот-

ветствующие алгоритмы их решения. Приведены примеры задач классифика-

ции текстов и оценивания (тестирования) моделей динамической регрессии.

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

Piatetsky-Shapiro G., Frawley W. Knowledge Discovery in Databases. AAAI/MIT

Press, 1991.

Witten I.H., Frank E. Data Mining: Practical Learning Tools and Techniques (2nd

Ed.). Morgan Kaufmann, 2005.

Editorial Community cleverness required // Nature. 2008. V. 455. No. 1.

Rosenblatt M. The Perceptron — perceiving and recognizing automaton. Report 85-

460-1, 1957.

Цыпкин Я.З. Основы теории обучающихся систем. М.: Наука, 1970.

Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций

в теории обучения машан. М.: Наука, 1970.

Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974.

Вапник В.Н., Червоненкис А.Я. Восстановление зависимостей по эмпиричеким

данным. М.: Наука, 1979.

Bishop C.M. Pattern Recognition and Machine Learning. Serise: Information Theory

and Statistics. Springer. 2006.

10.

Dempster A.P., Laird N.M., Rubin D.B. Maximum Likelihood from incomplete data

via the EM algorithm // J. Royal Statistical Society. Ser. B. 1977. No. 34. P. 1-38.

11.

Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск:

Наука, 1998.

12.

Jain A., Murty M., Flunn P. Data clastering: A review. ASM Computing Surveys,

1999. V. 31. No. 3. P. 264-323.

13.

Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer,

2001. http://www-stat.stanford.edu/ tibs/ElemStatLearn

14.

Воронцов К.В. Математические методы обучения по прецендентам. Курс лекций

МФТИ, 2006.

141

15.

Мерков А.Б. Распознавание образов. Введение в методы статистического обуче-

ния. М.: Едиториал УРСС, 2010.

16.

Золотых Н.Ю. Машинное обучение и анализ данных. 2013.

http://www.uic.unn.ru/ zny/ml

17.

Флах П. Машинное обучение. М.: ДМК Пресс, 2015.

18.

Abellan J., Castellano J.G. Improving the Naive Bayes Classifier via a Quick Variable

Selection Method Using Maximumu of Entropy // Entropy. 2017. V. 19. No. 6.

P. 246-254.

19.

Kullback S., Leibler R.A. On Information and Sufficiency // Ann. Math. Stat. 1951.

V. 22 (1). P. 79-86.

20.

Kapur J.N. Maximum entropy models in science and engineering. John Wiley &

Sons, Inc., 1989.

21.

Jaynes E.T. Information Theory and Statistical Mechanics // Physics Review Notes.

1957. V. 106. P. 620-630.

22.

The maximum entropy formalism / Eds. R.D. Levin, M. Tribus. MIT Press, 1979.

23.

Jaynes E.T. Papers on Probability, Statistics and Statistical Physics. Dordrecht:

Kluwer Acad. Publisher, 1989.

24.

Jaynes E.T. Probability Theory. The logic and science. Cambrige Univ. Press, 2003.

25.

Racine J., Maasoumi E. A Versatile and Robust Metric Entropy Test of Time-

Reversibility, and Other Hypotheses // J. Econometrics. 2007. V. 138. P. 547-567.

26.

Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.

27.

Kaashoek M.A., Seatzu S., van der Mee C. Recent Advances in Operator Theory

and its Applications. Springer, 2006.

28.

Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.: Наука, 1974.

29.

Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управление. М.: Нау-

ка, 1979.

30.

Darkhovskii B.S., Popkov Y.S., Popkov A.Y. Monte Carlo Method of Batch

Iterations: Probabilistic Characteristics // Autom. Remote Control. 2015. V. 76.

No. 5. P. 776-785.

Дарховский Б.С., Попков Ю.С., Попков А.Ю. Метод пакетных итераций Монте-

Карло: вероятностные характеристики // АиТ. 2015. № 5. С. 60-71.

31.

Попков Ю.С., Попков А.Ю., Дарховский Б.С. Параллельный Монте-Карло для

построения энтропийно-робастных оценок // Метематическое моделирование.

2015. Т. 27. № 6. С. 14-32.

32.

Kolmogorov F.N., Fomin S.V. Elements of the Theory of Functions and Functional

Analysis. Duver Books of Mathematics, 1999.

33.

Rubinstein R.Y., Kroese D.P. Simulation and the Monte Carlo Method, John Wiley

& Sons, 2008.

34.

Попков Ю.С. Динамическая модель миграционного взаимодействия региональ-

ных систем с энтропийным оператором // Тр. ИСА РАН. 2018. Т. 68. № 3.

С. 3-11. https://doi.org/10.14357/20790279180301

Статья представлена к публикации членом редколлегии А.В. Назиным.

Поступила в редакцию 06.06.2018

После доработки 13.09.2018

Принята к публикации 08.11.2018

142