Графические модели (курс лекций)/2012/Задание 4
Материал из MachineLearning.
(Новая: {{stop| '''Задание находится в разработке.'''<br/> Не приступайте к выполнению задания до его официальной выд...) |
(дополнение) |
||
Строка 1: | Строка 1: | ||
{{stop| | {{stop| | ||
'''Задание находится в разработке.'''<br/> | '''Задание находится в разработке.'''<br/> | ||
- | Не приступайте к выполнению задания | + | Не приступайте к выполнению задания пока это объявление не убрано. |
}} | }} | ||
Строка 17: | Строка 17: | ||
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных. | Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных. | ||
+ | |||
+ | Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование? | ||
Подсказка: <tex> -x_1\dots x_n = \min_z \left( (n-1)z - zx_1 - \dots - zx_n \right) </tex>. | Подсказка: <tex> -x_1\dots x_n = \min_z \left( (n-1)z - zx_1 - \dots - zx_n \right) </tex>. | ||
Строка 28: | Строка 30: | ||
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных. | Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных. | ||
+ | |||
+ | Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование? | ||
=== Задача 3 === | === Задача 3 === | ||
Строка 36: | Строка 40: | ||
Рассмотрим двойственное разложение энергии <tex> E(x) = |x_1 - x_2| + |x_2 - x_3| + |x_3 - x_1|</tex> на две компоненты: | Рассмотрим двойственное разложение энергии <tex> E(x) = |x_1 - x_2| + |x_2 - x_3| + |x_3 - x_1|</tex> на две компоненты: | ||
- | <tex> |x_1 - x_2| + |x_2 - x_3| </tex> и <tex> |x_3 - x_1|</tex>. | + | <tex> |x_1 - x_2| + |x_2 - x_3| </tex> и <tex> |x_3 - x_1|</tex>. |
Здесь все переменные бинарны. | Здесь все переменные бинарны. | ||
+ | |||
Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать. | Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать. | ||
+ | |||
+ | Что изменится (не изменится), если изменить способ разложения энергии на компоненты? | ||
=== Задача 5 === | === Задача 5 === | ||
Рассмотрим двойственное разложение энергии <tex> E(x) = |x_1 - x_2| + |x_2 - x_3| + |x_3 - x_4| + |x_4 - x_1|</tex> на две компоненты: | Рассмотрим двойственное разложение энергии <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| + |x_2 - x_3| + |x_3 - x_4| </tex> и <tex> |x_4 - x_1|</tex>. Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать. | + | <tex> |x_1 - x_2| + |x_2 - x_3| + |x_3 - x_4| </tex> и <tex> |x_4 - x_1|</tex>. |
+ | Здесь все переменные бинарны. | ||
+ | |||
+ | Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать. | ||
+ | Что изменится (не изменится), если изменить способ разложения энергии на компоненты? | ||
=== Оформление задания === | === Оформление задания === |
Версия 11:55, 8 апреля 2012
Задание находится в разработке. Не приступайте к выполнению задания пока это объявление не убрано. |
|
Начало выполнения задания: 9 апреля 2012
Срок сдачи: 18 апреля 2012, 18.00
Задача 1
Построить граф, минимальный разрез которого соответствует минимизации энергии . Здесь — бинарные переменные, — скобка Айверсона.
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.
Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование?
Подсказка: .
Задача 2
Построить граф, минимальный разрез которого соответствует минимизации энергии . Здесь . Здесь — бинарные переменные, — скобка Айверсона.
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.
Привести пример прикладной задачи, где такая энергия может возникнуть. К каким эффектам приведет ее использование?
Задача 3
Как при помощи комбинации конструкций из задачи 2 построить конструкцию для минимизации энергии , где f — произвольная вогнутая, кусочно-линейная функция?
Задача 4
Рассмотрим двойственное разложение энергии на две компоненты: и . Здесь все переменные бинарны.
Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.
Что изменится (не изменится), если изменить способ разложения энергии на компоненты?
Задача 5
Рассмотрим двойственное разложение энергии на две компоненты: и . Здесь все переменные бинарны.
Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.
Что изменится (не изменится), если изменить способ разложения энергии на компоненты?
Оформление задания
Выполненный вариант задания необходимо сдать лектору в бумажном виде или прислать на bayesml@gmail.com в электронном виде. Для решения задания можно использовать собственноручно написанные программные средства. Если таковые используются, то их тоже необходимо прислать.