Графические модели (курс лекций)/2012/Задание 4

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

Перейти к: навигация, поиск

Содержание

Начало выполнения задания: 9 апреля 2012

Срок сдачи: 18 апреля 2012, 18.00

Задача 1

Построить граф, минимальный разрез которого соответствует минимизации энергии  1 - x_1 \dots x_n = [x_1 + \dots x_n \neq n] . Здесь x_1,\dots, x_n — бинарные переменные, [\cdot]скобка Айверсона.

Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.

Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование?

Подсказка:  -x_1\dots x_n = \min_z \left( (n-1)z - zx_1 - \dots - zx_n \right) .

Задача 2

Функция f из задачи 2
Функция f из задачи 2

Построить граф, минимальный разрез которого соответствует минимизации энергии  f(x_1 + \dots + x_n) . Здесь  f(k) = (n - k) / \ell [k > n - \ell] + [k \leq n - \ell] . Здесь x_1,\dots, x_n — бинарные переменные, [\cdot]скобка Айверсона.

Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.

Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование?

Задача 3

Как при помощи комбинации конструкций из задачи 2 построить конструкцию для минимизации энергии  f(x_1 + \dots + x_n) , где f — произвольная вогнутая, кусочно-линейная функция?

Задача 4

Рассмотрим двойственное разложение энергии  E(x) = -|x_1 - x_2| - |x_2 - x_3| - |x_3 - x_1| на две компоненты:  -|x_1 - x_2| - |x_2 - x_3| и  -|x_3 - x_1|. Здесь все переменные бинарны.

Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.

Что изменится (не изменится), если изменить способ разложения энергии на компоненты?

Задача 5

Рассмотрим двойственное разложение энергии  E(x) = -|x_1 - x_2| - |x_2 - x_3| - |x_3 - x_4| - |x_4 - x_1| на две компоненты:  -|x_1 - x_2| - |x_2 - x_3| - |x_3 - x_4| и  -|x_4 - x_1|. Здесь все переменные бинарны.

Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.

Что изменится (не изменится), если изменить способ разложения энергии на компоненты?

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

Выполненный вариант задания необходимо сдать лектору в бумажном виде или прислать на bayesml@gmail.com в электронном виде. Для решения задания можно использовать собственноручно написанные программные средства. Если таковые используются, то их тоже необходимо прислать.

Личные инструменты