Графические модели (курс лекций)/2012/Задание 4
Материал из MachineLearning.
|
Начало выполнения задания: 9 апреля 2012
Срок сдачи: 18 апреля 2012, 18.00
Задача 1
Построить граф, минимальный разрез которого соответствует минимизации энергии .
Здесь
— бинарные переменные,
— скобка Айверсона.
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.
Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование?
Подсказка: .
Задача 2
Построить граф, минимальный разрез которого соответствует минимизации энергии .
Здесь
.
Здесь
— бинарные переменные,
— скобка Айверсона.
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.
Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование?
Задача 3
Как при помощи комбинации конструкций из задачи 2 построить конструкцию для минимизации энергии , где f — произвольная вогнутая, кусочно-линейная функция?
Задача 4
Рассмотрим двойственное разложение энергии на две компоненты:
и
.
Здесь все переменные бинарны.
Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.
Что изменится (не изменится), если изменить способ разложения энергии на компоненты?
Задача 5
Рассмотрим двойственное разложение энергии на две компоненты:
и
.
Здесь все переменные бинарны.
Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.
Что изменится (не изменится), если изменить способ разложения энергии на компоненты?
Оформление задания
Выполненный вариант задания необходимо сдать лектору в бумажном виде или прислать на bayesml@gmail.com в электронном виде. Для решения задания можно использовать собственноручно написанные программные средства. Если таковые используются, то их тоже необходимо прислать.
