Участник:Anton/Песочница
Материал из MachineLearning.
| Строка 11: | Строка 11: | ||
'''Срок сдачи''': {{ins| 18 апреля 2012, 18.00}} | '''Срок сдачи''': {{ins| 18 апреля 2012, 18.00}} | ||
| - | |||
=== Задача 1 === | === Задача 1 === | ||
| - | [[Изображение: | + | Построить граф, минимальный разрез которого соответствует минимизации энергии <tex> 1 - x_1 \dots x_n = [x_1 + \dots x_n \neq n] </tex>. |
| + | Здесь <tex>x_1,\dots, x_n</tex> — бинарные переменные, <tex>[\cdot]</tex> — [http://en.wikipedia.org/wiki/Iverson_bracket скобка Айверсона]. | ||
| + | |||
| + | Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных. | ||
| + | |||
| + | Подсказка: <tex> -x_1\dots x_n = \min_z \left( (n-1)z - zx_1 - \dots - zx_n \right) </tex>. | ||
| + | |||
| + | === Задача 2 === | ||
| + | [[Изображение:GM2012_hw4_image1.png|250px|thumb|Функция f из задачи 2]] | ||
| + | |||
| + | Построить граф, минимальный разрез которого соответствует минимизации энергии <tex> f(x_1 + \dots + x_n) </tex>. | ||
| + | Здесь <tex> f(k) = (n - k) / \ell [k > n - \ell] + [k \leq n - \ell] </tex>. | ||
| + | Здесь <tex>x_1,\dots, x_n</tex> — бинарные переменные, <tex>[\cdot]</tex> — [http://en.wikipedia.org/wiki/Iverson_bracket скобка Айверсона]. | ||
| + | |||
| + | Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных. | ||
| + | |||
| + | === Задача 3 === | ||
| + | |||
| + | Как при помощи комбинации конструкций из задачи 2 построить конструкцию для минимизации энергии <tex> f(x_1 + \dots + x_n) </tex>, где f — произвольная вогнутая, кусочно-линейная функция? | ||
| + | |||
| + | === Задача 4 === | ||
| + | |||
| + | Рассмотрим двойственное разложение энергии <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>. | ||
| + | Здесь все переменные бинарны. | ||
| + | Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать. | ||
| + | === Задача 5 === | ||
| + | Рассмотрим двойственное разложение энергии <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>. Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать. | ||
| - | |||
=== Оформление задания === | === Оформление задания === | ||
Версия 13:23, 7 апреля 2012
| Задание находится в разработке. Не приступайте к выполнению задания до его официальной выдачи. |
|
Начало выполнения задания: 9 апреля 2012
Срок сдачи: 18 апреля 2012, 18.00
Задача 1
Построить граф, минимальный разрез которого соответствует минимизации энергии .
Здесь
— бинарные переменные,
— скобка Айверсона.
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.
Подсказка: .
Задача 2
Построить граф, минимальный разрез которого соответствует минимизации энергии .
Здесь
.
Здесь
— бинарные переменные,
— скобка Айверсона.
Доказать, что каждый возможный разрез этой конструкции соответствует определенной разметке переменных.
Задача 3
Как при помощи комбинации конструкций из задачи 2 построить конструкцию для минимизации энергии , где f — произвольная вогнутая, кусочно-линейная функция?
Задача 4
Рассмотрим двойственное разложение энергии на две компоненты:
и
.
Здесь все переменные бинарны.
Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.
Задача 5
Рассмотрим двойственное разложение энергии на две компоненты:
и
. Построить график двойственной функции. Есть ли зазор между прямой и двойственной задачами? Ответ обосновать.
Оформление задания
Выполненный вариант задания необходимо сдать лектору в бумажном виде или прислать на bayesml@gmail.com в электронном виде. Для решения задания можно использовать собственноручно написанные программные средства. Если таковые используются, то их тоже необходимо прислать.
