Викиконспекты - Вклад участника [ru]

EM-алгоритм

2019-04-09T09:49:00Z

176.59.23.40: /* Общий алгоритм */

== Определение ==

'''Алгоритм EM''' --- алгоритм поиска максимума правдоподобия параметров для решения задач, где некоторые переменные не являются наблюдаемыми.

Алгоритм ищет параметры модели итеративно, каждая итерация состоит из двух шагов:

'''E(Expectation''') шаг, в котором находится распределение скрытых переменных используя значение наблюдаемых переменных и текущего значения параметров.

'''M(Maximisation)''' шаг --- пересчет параметров, находя максимум правдоподобия исходя из распределения скрытых переменных, полученных на E-шаге.

== Задача разделения смеси распределений ==

=== Общий алгоритм ===

Необходимо описать плотность распределения функции на X как сумму k функций, которые можно рассматривать как элементы параметрического семейства функций <tex> p_j(x) = \phi(x;\theta_j)</tex>. Плотность распределения будет выглядеть как 
<tex>p(x) = \sum\limits_{i=1}^k \omega_j p_j(x); \sum\limits_{i=1}^k w_j = 1; w_j >= 0 </tex>
 где <tex>\omega_j</tex>- априорная вероятность j компоненты распределения.
Задача разделения смеси заключается в том, чтобы, имея выборку <tex>X^m</tex> случайных и независимых наблюдений из смеси <tex>p(x)</tex>, зная число <tex>k</tex> и функцию <tex>\phi</tex>, оценить вектор параметров <tex>\theta = (\omega_1,..,\omega_k,\theta_1,..,\theta_k)</tex>

E-шаг:

<tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex> 
Введем обозначение: <tex> g_{ij} = P(\theta_j | x_i) </tex> это и будут скрытые параметры данной задачи - апостериорная вероятность того, что обучающий объект <tex> x_i </tex> получен из <tex>j</tex>-й компоненты

По формуле Байеса справедливо равенство: 
<tex> g_{ij} = \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^k w_t p_t(x_i)}</tex> 
Таким образом при зная значение параметров легко найти скрытые переменные.

Перейдем к M-шагу.

Посчитаем для аддитивности логарифм правдоподобия: 
<tex> Q(\Theta) = ln \prod\limits_{i=1}^mp(x_i) = \sum\limits_{i=1}^m ln\sum\limits_{j=1}^k w_j p_j(x_i) \longrightarrow max</tex> 
при условии <tex>\sum\limits_{i=1}^k w_j = 1; w_j >= 0</tex> имеет смысл рассматривать лагранжиан задачи: 
<tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{p_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} - \lambda = 0.</tex> 

Умножим на <tex>\omega_j</tex> и просуммируем уравнения для всех <tex>j</tex> 

<tex>\sum\limits_{j=1}^k \sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = \lambda \sum\limits_{j=1}^kw_j</tex> 

Так как можно заменить порядок суммы и <tex>\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = 1</tex> и <tex>\sum\limits_{j=1}^kw_j = 1</tex>, из чего следует <tex>\lambda = m</tex> 

<tex>\omega_j = \frac{1}{m}\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = \frac{1}{m}\sum\limits_{i=1}^mg_{ij}</tex> 

Приравняв к нулю лагранжиан по <tex>\theta_j</tex> схожим способом найдем: 

<tex> \theta_j = \arg\max\limits{\theta}\sum\limits_{i=1}^mg_{ij}\ln(\phi(x_i;\theta)).</tex> 

Таким образом на M-шаге необходимо взять среднее значение <tex>g_{ij}</tex> и решить k независимых оптимизационных задач.

=== Разделение смеси гауссиан ===
[[Файл:Gaussians.png|right|250px| Несколько итераций алгоритма]]
Важным на практике примером является случай, когда параметрическое семейство - нормальные распределения. Параметрами функций будут являться матожидание и дисперсия. 
<tex>\theta = (w_1,..,w_k;\;\mu_1,..,\mu_k;\;\sigma_1,..,\sigma_k)</tex> — вектор параметров, 
<tex>p_j(x) = N(x;\mu_j, \sigma_j) = \frac1{\sqrt{2\pi}\sigma_j} \exp \biggl(-\frac{(x - \mu_j)^2}{2\sigma_j^2}\biggr) </tex>

== k-means как EM алгоритм ==
[[Файл:kmeans.jpg|right|250px|K-means]]
Скрытыми переменными в данной задаче являются классы, к которым относятся объекты для кластеризации. Сами же параметры это центры масс классов. На шаге E - распределяются все объекты по классам исходя из расстояния от центра, на шаге M находится оптимальное месторасположение центра.

Аналогично рассматривается и алгоритм c-means. Скрытые переменные здесь будут вероятности принадлежности к классам, которые находятся на E-шаге по расстоянию от центра. Центр так же рассчитывается на M-шаге исходя из скрытых переменных.

== Реализация на python ==

'''import''' numpy as np
'''import''' matplotlib.pyplot as plt
'''from''' sklearn '''import''' cluster, datasets, mixture
'''from''' sklearn.preprocessing '''import''' StandardScaler
'''from''' itertools '''import''' cycle, islice
np.random.seed(12)

# Создаем datasets с использованием стандартных sklearn.datasets
n_samples = 2000
random_state = 170
noisy_circles = datasets.make_circles(n_samples=n_samples, factor=.5, noise=.05)
noisy_moons = datasets.make_moons(n_samples=n_samples, noise=.05)
blobs = datasets.make_blobs(n_samples=n_samples, random_state=8)
varied = datasets.make_blobs(n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=random_state)

# Создаем анизатропно разделенные данные
X, y = datasets.make_blobs(n_samples=n_samples, random_state=random_state)
transformation = [[0.6, -0.6], [-0.4, 0.8]]
X_aniso = np.dot(X, transformation)
aniso = (X_aniso, y)

# Выставляем параметры для matplotlib.pyplot
plt.figure(figsize=(9 * 2 + 3, 12.5))
plt.subplots_adjust(left=.02, right=.98, bottom=.001, top=.96, wspace=.05, hspace=.01)
plot_num = 1
defaul_n = 3

# Варьируем значение количества классов в зависимости от данных, ведь для нас это гиперпараметр
datasets = [
(varied, defaul_n),
(aniso, defaul_n),
(blobs, defaul_n),
(noisy_circles, 2)]
for i_dataset, (dataset, n_cluster) in enumerate(datasets):
X, y = dataset

# Нормализация данных
X = StandardScaler().fit_transform(X)

# Непосредственно наш алгоритм - Gaussian Mixture
gmm = mixture.GaussianMixture(n_components=n_cluster, covariance_type='full')

# Для сравнения берем алгоритм - K-means
two_means = cluster.KMeans(n_clusters=n_cluster)
clustering_algorithms = (
('GaussianMixture', gmm),
('KMeans', two_means)
)
for name, algorithm in clustering_algorithms:

# Этап обучения
algorithm.fit(X)

# Применяем алгоритм
y_pred = algorithm.predict(X)

# Рисуем результаты
plt.subplot(len(datasets), len(clustering_algorithms), plot_num)
if i_dataset == 0:
plt.title(name, size=18)
colors = np.array(list(islice(cycle(['#377eb8', '#ff7f00', '#4daf4a']), int(max(y_pred) + 1))))
plt.scatter(X[:, 0], X[:, 1], s=10, color=colors[y_pred])
plt.xlim(-2.5, 2.5)
plt.ylim(-2.5, 2.5)
plt.xticks(())
plt.yticks(())
plot_num += 1
plt.show()

[[Файл:Prog.png|thumb|250px|Результат программы]]

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

== См. также ==
*[[Кластеризация]]

== Источники информации ==

# [http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Математические методы обучения по прецедентам К. В. Воронцов]
# [http://dendroid.sk/2011/05/09/k-means-clustering/ k-means]

[[Категория:Машинное обучение]]

EM-алгоритм

2019-04-09T09:46:54Z

176.59.23.40: /* Определение */

== Определение ==

'''Алгоритм EM''' --- алгоритм поиска максимума правдоподобия параметров для решения задач, где некоторые переменные не являются наблюдаемыми.

Алгоритм ищет параметры модели итеративно, каждая итерация состоит из двух шагов:

'''E(Expectation''') шаг, в котором находится распределение скрытых переменных используя значение наблюдаемых переменных и текущего значения параметров.

'''M(Maximisation)''' шаг --- пересчет параметров, находя максимум правдоподобия исходя из распределения скрытых переменных, полученных на E-шаге.

== Задача разделения смеси распределений ==

=== Общий алгоритм ===

Необходимо описать плотность распределения функции на X как сумму k функций, которые можно рассматривать как элементы параметрического семейства функций <tex> p_j(x) = \phi(x;\theta_j)</tex>. Плотность распределения будет выглядеть как 
<tex>p(x) = \sum\limits_{i=1}^k \omega_j p_j(x); \sum\limits_{i=1}^k w_j = 1; w_j >= 0 </tex>
 где <tex>\omega_j</tex>- априорная вероятность j компоненты распределения.
Задача разделения смеси заключается в том, чтобы, имея выборку <tex>X^m</tex> случайных и независимых наблюдений из смеси <tex>p(x)</tex>, зная число <tex>k</tex> и функцию <tex>\phi</tex>, оценить вектор параметров <tex>\theta = (\omega_1,..,\omega_k,\theta_1,..,\theta_k)</tex>

E-шаг:

<tex>p(x,\theta_j) = p(x)P(\theta_j | x) = w_jp_j(x)</tex> 
Введем обозначение: <tex> g_{ij} = P(\theta_j | x_i) </tex> это и будут скрытые параметры данной задачи - апостериорная вероятность того, что обучающий объект <tex> x_i </tex> получен из <tex>j</tex>-й компоненты

По формуле Байеса справедливо равенство: 
<tex> g_{ij} = \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^k w_t p_t(x_i)}</tex> 
Таким образом при зная значение параметров легко найти скрытые переменные.

Перейдем к M-шагу:

Посчитаем для аддитивности логарифм правдоподобия: 
<tex> Q(\Theta) = ln \prod\limits_{i=1}^mp(x_i) = \sum\limits_{i=1}^m ln\sum\limits_{j=1}^k w_j p_j(x_i) \longrightarrow max</tex> 
при условии <tex>\sum\limits_{i=1}^k w_j = 1; w_j >= 0</tex> имеет смысл рассматривать лагранжиан задачи: 
<tex>\frac{\partial L} {\partial w_j} = \sum\limits_{i=1}^m \frac{p_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} - \lambda = 0</tex> 

Умножим на <tex>\omega_j</tex> и просумируем уравнения для всех <tex>j</tex> 

<tex>\sum\limits_{j=1}^k \sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = \lambda \sum\limits_{j=1}^kw_j</tex> 

Так как можно заменить порядок суммы и <tex>\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = 1</tex> и <tex>\sum\limits_{j=1}^kw_j = 1</tex> из чего следует <tex>\lambda = m</tex> 

<tex>\omega_j = \frac{1}{m}\sum\limits_{i=1}^m \frac{w_jp_j(x_i)}{\sum\limits_{t=1}^kw_tp_t(x_i)} = \frac{1}{m}\sum\limits_{i=1}^mg_{ij}</tex> 

Приравняв к нулю лагранжиан по <tex>\theta_j</tex> схожим способом найдем: 

<tex> \theta_j = arg \max\limits{\theta}\sum\limits_{i=1}^mg_{ij}ln(\phi(x_i;\theta)) </tex> 

Таким образом на M-шаге необходимо взять среднее значение <tex>g_{ij}</tex> и решить k независимых оптимизационных задач.

=== Разделение смеси гауссиан ===
[[Файл:Gaussians.png|right|250px| Несколько итераций алгоритма]]
Важным на практике примером является случай, когда параметрическое семейство - нормальные распределения. Параметрами функций будут являться матожидание и дисперсия. 
<tex>\theta = (w_1,..,w_k;\;\mu_1,..,\mu_k;\;\sigma_1,..,\sigma_k)</tex> — вектор параметров, 
<tex>p_j(x) = N(x;\mu_j, \sigma_j) = \frac1{\sqrt{2\pi}\sigma_j} \exp \biggl(-\frac{(x - \mu_j)^2}{2\sigma_j^2}\biggr) </tex>

== k-means как EM алгоритм ==
[[Файл:kmeans.jpg|right|250px|K-means]]
Скрытыми переменными в данной задаче являются классы, к которым относятся объекты для кластеризации. Сами же параметры это центры масс классов. На шаге E - распределяются все объекты по классам исходя из расстояния от центра, на шаге M находится оптимальное месторасположение центра.

Аналогично рассматривается и алгоритм c-means. Скрытые переменные здесь будут вероятности принадлежности к классам, которые находятся на E-шаге по расстоянию от центра. Центр так же рассчитывается на M-шаге исходя из скрытых переменных.

== Реализация на python ==

'''import''' numpy as np
'''import''' matplotlib.pyplot as plt
'''from''' sklearn '''import''' cluster, datasets, mixture
'''from''' sklearn.preprocessing '''import''' StandardScaler
'''from''' itertools '''import''' cycle, islice
np.random.seed(12)

# Создаем datasets с использованием стандартных sklearn.datasets
n_samples = 2000
random_state = 170
noisy_circles = datasets.make_circles(n_samples=n_samples, factor=.5, noise=.05)
noisy_moons = datasets.make_moons(n_samples=n_samples, noise=.05)
blobs = datasets.make_blobs(n_samples=n_samples, random_state=8)
varied = datasets.make_blobs(n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=random_state)

# Создаем анизатропно разделенные данные
X, y = datasets.make_blobs(n_samples=n_samples, random_state=random_state)
transformation = [[0.6, -0.6], [-0.4, 0.8]]
X_aniso = np.dot(X, transformation)
aniso = (X_aniso, y)

# Выставляем параметры для matplotlib.pyplot
plt.figure(figsize=(9 * 2 + 3, 12.5))
plt.subplots_adjust(left=.02, right=.98, bottom=.001, top=.96, wspace=.05, hspace=.01)
plot_num = 1
defaul_n = 3

# Варьируем значение количества классов в зависимости от данных, ведь для нас это гиперпараметр
datasets = [
(varied, defaul_n),
(aniso, defaul_n),
(blobs, defaul_n),
(noisy_circles, 2)]
for i_dataset, (dataset, n_cluster) in enumerate(datasets):
X, y = dataset

# Нормализация данных
X = StandardScaler().fit_transform(X)

# Непосредственно наш алгоритм - Gaussian Mixture
gmm = mixture.GaussianMixture(n_components=n_cluster, covariance_type='full')

# Для сравнения берем алгоритм - K-means
two_means = cluster.KMeans(n_clusters=n_cluster)
clustering_algorithms = (
('GaussianMixture', gmm),
('KMeans', two_means)
)
for name, algorithm in clustering_algorithms:

# Этап обучения
algorithm.fit(X)

# Применяем алгоритм
y_pred = algorithm.predict(X)

# Рисуем результаты
plt.subplot(len(datasets), len(clustering_algorithms), plot_num)
if i_dataset == 0:
plt.title(name, size=18)
colors = np.array(list(islice(cycle(['#377eb8', '#ff7f00', '#4daf4a']), int(max(y_pred) + 1))))
plt.scatter(X[:, 0], X[:, 1], s=10, color=colors[y_pred])
plt.xlim(-2.5, 2.5)
plt.ylim(-2.5, 2.5)
plt.xticks(())
plt.yticks(())
plot_num += 1
plt.show()

[[Файл:Prog.png|thumb|250px|Результат программы]]

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

== См. также ==
*[[Кластеризация]]

== Источники информации ==

# [http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf Математические методы обучения по прецедентам К. В. Воронцов]
# [http://dendroid.sk/2011/05/09/k-means-clustering/ k-means]

[[Категория:Машинное обучение]]