Участник:Anton/Песочница

Материал из MachineLearning.

(Различия между версиями)

Версия 18:09, 11 апреля 2011

Статья в настоящий момент дорабатывается.
Формулировка задания находится в стадии формирования. Просьба не приступать к выполнению задания, пока это предупреждение не будет удалено. Anton 18:11, 7 апреля 2011 (MSD)

Содержание

1 Марковское случайное поле
- 1.1 MRF для интерактивной сегментации изображений
2 Вариант 1 : TRW
3 Вариант 2 : α-expansion

Перейти к основной странице курса

Задание состоит из двух вариантов.

Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.

Марковское случайное поле

Марковское случайное поле (MRF) — графическая модель, энергия (отрицательный логарифм правдоподобия) которой записывается в виде:
$E(X) = \sum_{p \in P} D_p(x_p) + \sum_{(p, q) \in E} V_{pq}(x_p, x_q),$
где P — множество индексов переменных, E — система соседства, D — унарные потенциалы, V — бинарные потенциалы.

Рассмотрим модель со следующими ограничения:

переменные $x_p$ дискретны и принимают значения из множества {1,…,K}, K ≥ 2,
система соседства E - прямоугольная решетка,
бинарные потенциалы V являются обобщенными потенциалами Поттса: $V_{pq} = \alpha_{pq} [x_p \neq x_q]$ .

В рамках этого задания требуется:

реализовать алгоритм поиска конфигурации MRF, обладающей минимальной энергией (TRW или α-expansion),
протестировать реализованный алгоритм на модельных задачах,
применить реализованный алгоритм для задачи интерактивной сегментации изображений,
сравнить алгоритмы TRW и α-expansion на задаче сегментации изображений.

MRF для интерактивной сегментации изображений

Задача сегментации изображения состоит в отнесении каждого пикселя изображения к одному из K классов. В интерактивном варианте пользователь отмечает часть пикселей, принадлежащих каждому классу. После этого требуется автоматически разметить оставшуюся часть изображения.

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

Каждая переменная $x_p$ соответствует пикселю изображения.
Используется стандартная 4-х связная система соседства.
Если пиксель p отнесен пользователем к классу k, то унарные потенциалы „разрешают“ переменной $x_p$ принимать только значение k:
$D_p(k) = 0, D_p(l) = \infty, l \neq k$ .
Если пиксель p не отнесен пользователем ни к одному из классов, то унарные потенциалы принимают значения равные минус логарифму правдоподобия принадлежности пикселя цвета $I_p$ соответствующему классу: $D_p(k) = -\log P_k(I_p)$ .
Цветовые модели объектов можно восстановить по пикселям, размеченным пользователем, при помощи EM-алгоритма восстановления смеси нормальных распределений в пространстве Luv.
В качестве парных потенциалов выбираются обобщенные потенциалы Поттса с коэффициентами α, делающими разрез более энергетически-выгодным, там где цвет изображения сильно меняется: $\alpha_{pq} = A + B\:\exp\left(-\frac{|| I_p - I_q ||^2}{2\sigma^2}\right)$ , A ≥ 0, B ≥ 0, σ — параметры.

Вариант 1 : TRW

Задание

Реализовать метод
Реализовать EM-алгоритм обучения СММ при заданном числе состояний K.
Реализовать алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ
Протестировать реализованные алгоритмы на модельных сигналах
Рассчитать набор признаков для описания поведения мыши и на их основе найти 3 осмысленных поведенческих акта с помощью ЕМ-алгоритма обучения СММ, проинтерпретировать полученные поведенческие акты
Наложить полученные поведенческие акты на видео с поведением
Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен, в частности, включать в себя графики сегментации модельных сигналов.

Спецификация реализуемых функций

Генерация выборки

[X, T] = HMM_GENERATE(N, w, A, Mu, Sigmas)

ВХОД

N — количество точек в генерируемой последовательности, uint32;

w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;

A — матрица перехода, матрица типа double размера K x K;

Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;

Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;

ВЫХОД

X — сгенерированная последовательность, матрица типа double размера N x d

T — последовательность скрытых состояний, матрица типа double размера 1 x N

Рекомендации по выполнению задания

1. При разбиении MRF-решетки на вертикальные и горизонтальные цепочки формулировка несколько упрощается:

Каждое ребро графа принадлежит только одному подграфу, а значит не нужно вводить двойственные переменные, соответствующие ребрам.
Каждое вершина принадлежит только двум деревьям, а значит можно ввести |P|K двойственных переменных, соответствующих условиям $y_{pk}^{hor} = y_{pk}^{vert}, \;\; p \in P, \;\; k = 1\dots K$ , где hor и vert, обозначают горизонтальную и вертикальную цепочку, проходящую через p-ю вершину.

2. Поскольку двойственная функция вогнута и кусочно-линейна, оптимизировать ее можно при помощи алгоритма субградиентного подъема. Каждый шаг метода субградиентного подъема состоит в пересчете значений двойственных переменных λ по следующему правилу:
$\lambda_{new} = \lambda_{old} + \alpha_t g_t,$ где $g_t$ — субградиент в текущей точке, $\alpha_t$ — параметр, отвечающий за длину сдвига. В рамках данного практического задания рекомендуется использовать адаптивный метод выбора длины шага:
$\alpha_t = \frac{\text{Approx}_t - \text{Dual}_t}{|| \nabla g_t|| ^ 2},$
где $\text{Dual}_t$ — текущее значение двойственной функции, </tex>\text{Approx}_t</tex> — оценка оптимума двойственной функции, которую можно определять следующим способом:
$\text{Approx}_t = \text{BestDual}_t + \delta_t,$ где $\text{BestDual}_t$ — лучшее на данный момент значение двойственной функции,
$\delta_{t+1} = \begin{cases} c^* \delta_t, \;\; \text{Dual}_t > \text{Dual}_{t-1}, \\ \max(c_* \delta_t, \; \varepsilon ), \;\; \text{Dual}_t \leq \text{Dual}_{t-1}. \end{cases}$
$c^*, \; c_*, \; \varepsilon$ — параметры метода. Обычно $c^* > 1, \; 1 > c_* > 0, \; \varepsilon \to 0+$ .

Данные для выполнения задания

Оформление задания