# Дерево алгоритмов

Основным понятием, являющимся центром всей архитектуры модуля алгоритмов, является "дерево алгоритмов", показывающее то, как система выполняет пошаговый процесс оценки параметров: от предварительной настройки до выбора и выполнения одного из доступных семейств алгоритмов.


```{image} ./_static/Algo-tree.png
:alt: Select Parameters
:width: 500px
:align: center
```

<br>

Процесс можно разбить на следующие логические этапы:

1. **Начало и предварительная настройка:**
   - Процесс начинается с получения входных данных (выборка, для которой мы хотим оценить смесь).
   - Перед запуском основного алгоритма выполняются два ключевых подготовительных шага, которые предоставляют начальные условия:
     - **Estimate number of components (Оценка числа компонент):** Определение предполагаемого количества компонент в смеси.
     - **Initialize initial guess (Инициализация начального приближения):** Задание стартовых значений параметров для алгоритмов.
2. **Выбор семейства алгоритмов (Точка ветвления):**
   - На основе конфигурации или выбора пользователя, система переходит к одному из трех основных семейств алгоритмов (обозначено ромбом). Это ключевая точка, обеспечивающая гибкость системы.
3. **Исполнение алгоритма:**
   - **Ветвь EM-like (EM-подобные алгоритмы):**
     - Представляет итеративные алгоритмы, основанные на максимизации ожидания.
     - Классический цикл состоит из двух шагов: **E-step** (Expectation) и **M-step** (Maximization), которые повторяются до сходимости.
   - **Ветвь Monte Carlo (Методы Монте-Карло):**
     - Представляет алгоритмы, основанные на стохастическом сэмплировании (например, **MCMC**).
     - Внутренняя структура этих методов пока что не рассматривается и здесь обозначена многоточием (...)
   - **Ветвь Forward estimation (Прямое оценивание):**
     - Представляет неитеративные методы.
     - Примерами таких методов являются **MLE** и **Метод моментов**.

<br>

## EM-like

Как было показано в общей архитектуре "дерева алгоритмов", одной из ключевых стратегий оценки является EM-like. Данная диаграмма детализирует внутреннюю структуру этого итеративного процесса.



```{image} ./_static/EM-like.png
:alt: Select Parameters
:width: 700px
:align: center
```

<br>

Процесс состоит из двух фундаментальных шагов, выполняемых последовательно в цикле: **E-step** (шаг ожидания) и **M-step** (шаг максимизации):

1. **E-step (Шаг ожидания):**
   - **Вход:** На вход шага поступает текущее состояние модели смеси (Mixture).
   - **Задача:** Основная задача этого шага — вычислить "ответственность" (responsibilities) каждой компоненты смеси за каждую точку данных. По сути, это оценка скрытых (latent) переменных — вероятностей того, что $i$-ая точка данных принадлежит $k$-ой компоненте.
   - **Выход:** Результатом являются вычисленные "ответственности", которые вместе с исходными данными передаются на следующий шаг.
2. **M-step (Шаг максимизации):**
   - **Вход:** На вход поступают данные и вычисленные на E-шаге "ответственности".
   - **Задача:** Цель этого шага — обновить параметры $\Theta, \Omega$ модели смеси.
   - **Архитектурная особенность:** параметры компонент оцениваются независимо и параллельно. Для каждой компоненты можно указать собственные оценки стратегий а так же выбрать параметры, которые будут оценены. Таким образом можно для некоторых компонент оценить сначала один параметр, потом другой.
   - **Доступные стратегии**:
     - Q-function
     - Moments
     - L-moments
     - TL-moments
     - LQ-moments
3. **Завершение итерации:**
   - **Выход:** На выходе M-шага мы получаем обновленную модель смеси (Mixture).
   - Эта обновленная модель затем используется как входная для следующей итерации E-шага. Цикл "E-step -> M-step" повторяется до тех пор, пока не будет достигнут критерий останова. В конце каждой итерации происходит "pruning" смеси, отсекая ненужные компоненты (например те, которые вносят почти нулевой вклад в смесь).

<br>

## Monte Carlo

Пока что не рассматривались.

<br>

## Forward estimation



Эта ветвь объединяет неитеративные методы оценки параметров смеси. В отличие от EM-алгоритмов, которые уточняют параметры шаг за шагом, методы прямого оценивания вычисляют их напрямую на основе свойств выборки.

Основными представителями этого семейства являются **Метод Максимального Правдоподобия (MLE)** и **Метод Моментов (Method of Moments)**.

<br>

#### **Метод Максимального Правдоподобия (MLE)**

**Идея:** Метод заключается в поиске таких параметров модели ($\Theta$ и $\Omega$), при которых наблюдаемые данные являются наиболее "вероятными".

**Процесс:**

1. **Формирование функции правдоподобия:** Для смеси распределений функция правдоподобия $L(\Theta, \Omega~|~ x)$ строится на основе функции плотности $f(x ~|~ \Theta, \Omega)$.
2. **Максимизация:** Находится максимум логарифма этой функции.

<br>

#### **Метод Моментов (MoM)**

Пока что не рассматривался.