Графические модели (курс лекций)/2012/Задание 4
Материал из MachineLearning.
(дополнение) |
(выдача) |
||
| (1 промежуточная версия не показана) | |||
| Строка 1: | Строка 1: | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
{{TOCright|300px}} | {{TOCright|300px}} | ||
| Строка 39: | Строка 34: | ||
=== Задача 4 === | === Задача 4 === | ||
| - | Рассмотрим двойственное разложение энергии <tex> E(x) = |x_1 - x_2| | + | Рассмотрим двойственное разложение энергии <tex> E(x) = -|x_1 - x_2| - |x_2 - x_3| - |x_3 - x_1|</tex> на две компоненты: |
| - | <tex> |x_1 - x_2| | + | <tex> -|x_1 - x_2| - |x_2 - x_3| </tex> и <tex> -|x_3 - x_1|</tex>. |
Здесь все переменные бинарны. | Здесь все переменные бинарны. | ||
| Строка 49: | Строка 44: | ||
=== Задача 5 === | === Задача 5 === | ||
| - | Рассмотрим двойственное разложение энергии <tex> E(x) = |x_1 - x_2| | + | Рассмотрим двойственное разложение энергии <tex> E(x) = -|x_1 - x_2| - |x_2 - x_3| - |x_3 - x_4| - |x_4 - x_1|</tex> на две компоненты: |
| - | <tex> |x_1 - x_2| | + | <tex> -|x_1 - x_2| - |x_2 - x_3| - |x_3 - x_4| </tex> и <tex> -|x_4 - x_1|</tex>. |
Здесь все переменные бинарны. | Здесь все переменные бинарны. | ||
Текущая версия
|
Начало выполнения задания: 9 апреля 2012
Срок сдачи: 18 апреля 2012, 18.00
Задача 1
Построить граф, минимальный разрез которого соответствует минимизации энергии .
Здесь
— бинарные переменные,
— скобка Айверсона.
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.
Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование?
Подсказка: .
Задача 2
Построить граф, минимальный разрез которого соответствует минимизации энергии .
Здесь
.
Здесь
— бинарные переменные,
— скобка Айверсона.
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.
Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование?
Задача 3
Как при помощи комбинации конструкций из задачи 2 построить конструкцию для минимизации энергии , где f — произвольная вогнутая, кусочно-линейная функция?
Задача 4
Рассмотрим двойственное разложение энергии на две компоненты:
и
.
Здесь все переменные бинарны.
Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.
Что изменится (не изменится), если изменить способ разложения энергии на компоненты?
Задача 5
Рассмотрим двойственное разложение энергии на две компоненты:
и
.
Здесь все переменные бинарны.
Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.
Что изменится (не изменится), если изменить способ разложения энергии на компоненты?
Оформление задания
Выполненный вариант задания необходимо сдать лектору в бумажном виде или прислать на bayesml@gmail.com в электронном виде. Для решения задания можно использовать собственноручно написанные программные средства. Если таковые используются, то их тоже необходимо прислать.
