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