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

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

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

Версия 16:35, 11 апреля 2011

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


Содержание

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

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

Среда реализации для всех вариантов – 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] .

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

  1. реализовать алгоритм поиска конфигурации MRF, обладающей минимальной энергией (TRW или α-expansion),
  2. протестировать реализованный алгоритм на модельных задачах,
  3. применить реализованный алгоритм для задачи интерактивной сегментации изображений,
  4. сравнить алгоритмы 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, σ — параметры.

Метод субградиентного подъема для алгоритма TRW

Каждый шаг метода субградиентного подъема состоит в пересчете значений двойственных переменных λ по следующему правилу:
\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, где
\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+/tex> </p><p>== Вариант 1 : TRW== </p><p>=== Задание === </p><p>=== Спецификация реализуемых функций === </p><p>=== Рекомендации по выполнению задания === </p><p>=== Данные для выполнения задания === </p><p>=== Оформление задания === </p><p>== Вариант 2 : α-expansion == </p><p>=== Задание === </p><p>=== Спецификация реализуемых функций === </p><p>=== Рекомендации по выполнению задания === </p><p>=== Данные для выполнения задания === </p><p>=== Оформление задания === </p><p>[[Категория:Учебные курсы]] [[Категория:Байесовские методы]]

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Anton/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»
Личные инструменты