Машинное обучение 2012 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Домашние задания)
(Домашние задания)
 
(не показаны 3 промежуточные версии 1 участника)
Строка 4: Строка 4:
  
 
== Домашние задания ==
 
== Домашние задания ==
1. Крестики-нолики.
+
=== Крестики-нолики ===
Требуестся написать программу которая обучается играть за первого игрока (крестики) против фиксированной стратегии второго игрока. В случае ничейного результата партия считается проигранной крестиками.
+
 
В качестве стратегии второго использовать следующую: если нолики могут своим составить ряд из трех нолей, то они делают этот ход. Если такого хода нет, то ход выбирается случайно равновероятно из всех незанятых клеток.
+
Требуется написать программу, которая обучается играть за первого игрока (крестики) против фиксированной стратегии второго игрока (нолики). В случае ничейного результата партия считается проигранной крестиками.
Попробовать две стратегии обучения: TD (когда после хода ценность позиции сдвигается в сторону ценности новой позиции) и стратегию, которая премирует все позиции которые встретелись в партии если крестики победили и депримирует если проиграли.
+
В качестве стратегии второго использовать следующую: если нолики могут своим ходом составить ряд из трех нолей, то они делают этот ход. Если такого хода нет, то ход выбирается случайно равновероятно из всех незанятых клеток.
 +
Попробовать две стратегии обучения: TD (когда после хода ценность позиции сдвигается в сторону ценности новой позиции) и стратегию, которая премирует все позиции которые встретились в партии, если крестики победили и депремирует, если проиграли.
 
В качестве стратегии выбора хода крестиков реализовать \epsilon-жадную и температурную.  
 
В качестве стратегии выбора хода крестиков реализовать \epsilon-жадную и температурную.  
 
Программа должна, непрерывно обучаясь, провести 100 раз по 1000 партий и для каждой тысячи вывести число побед крестиков в консоль или в файл.
 
Программа должна, непрерывно обучаясь, провести 100 раз по 1000 партий и для каждой тысячи вывести число побед крестиков в консоль или в файл.
Задача зачитывается при наличии кода и четырех файлов (для всех сочетаний стратегии поведания и стратегии обучения) показывающих динамику числа побед.  
+
Задача зачитывается при наличии кода и четырёх файлов (для всех сочетаний стратегии поведения и стратегии обучения), показывающих динамику числа побед.
  
2. Про монетку.
+
=== Про монетку ===
Рассмотрим следующую игру: У вас есть сумма (от 1 до 99 монет), Вы делаете ставку и подбрасываете монетку. Если выпал "орел", то ставка удваивается, иначе теряется. Цель игры набрать ровно 100 монет.
+
 
Зафиксируем базовую стратегию: Если меньше или равно 50 монет, то ставим все иначе недостающую до 100 сумму. Пользуясь данной стратегие проэмулировать по 100 игр из каждого начального состояния.
+
Рассмотрим следующую игру: У вас есть сумма от 1 до 99 монет, вы делаете ставку и подбрасываете монетку. Если выпал "орёл", то ставка удваивается, иначе теряется. Цель игры набрать ровно 100 монет.
По результатам эмуляции для каждого положения вычислить "взвешенный успех" --- долю игр прошедших через это состояние, закончившиеся успехом.
+
Зафиксируем базовую стратегию: Если сумма меньше или равна 50 монетам, то ставим всё, иначе недостающую до 100 сумму. Пользуясь данной стратегией, проэмулировать по 100 игр из каждого начального состояния.
 +
По результатам эмуляции для каждого положения вычислить "взвешенный успех" --- долю игр, прошедших через это состояние, закончившихся успехом.
 
По результатам вычисления выбрать новую стратегию ставок --- жадную, по отношению к новым весам позиций.
 
По результатам вычисления выбрать новую стратегию ставок --- жадную, по отношению к новым весам позиций.
Повторить такую процедуру до схождения стратегии (до момента, когда ставки перестанут менятся).
+
Повторить такую процедуру до схождения стратегии (до момента, когда ставки перестанут меняться).
Провести такое моделирования для разной вероятности выпаденя орла --- 0.4, 0.5, 0.6. И вывести получившиеся оптимальные стратегии.
+
Провести такое моделирование для разной вероятности выпадения орла --- 0.4, 0.5, 0.6 и вывести получившиеся оптимальные стратегии.
Задача зачитывается при наличии кода и трех файлов (для трех вероятностей выпадения орла) содержащих полученную стратегию в виде пар чисел "состояние"--"ставка".
+
Задача зачитывается при наличии кода и трёх файлов (для трёх вероятностей выпадения орла), содержащих полученную стратегию в виде пар чисел "состояние"--"ставка".
 +
 
 +
=== Блекджек ===
 +
 
 +
Задача: научиться играть в блекджек против дилера с фиксированной стратегией.
 +
 
 +
Правила игры: игроку и дилеру сдаётся по две карты. Если у игрока 21 очко при сдаче, то дилер открывает свою руку и они сравниваются. Если этого не произошло, то игра продолжается по правилам, описанным далее. Игрок видит свои карты и одну карту дилера. Каждый ход игрок выбирает одну из двух возможностей: взять еще карту или остановиться. Ходы игрока продолжаются до тех пор, пока он не выберет "остановиться" или не наберёт больше 21 очка. Карты имеют следующую стоимость в очках: туз --- 1 или 11 по выбору игрока, остальные картинки 10, остальные карты по своему значению.
 +
Если игрок набрал больше 21, то он считается проигравшим. Если игрок остановился, то дилер начинает набирать карты.
 +
 
 +
Стратегия 1: Дилер набирает, пока у него не будет 17 или больше, и останавливается.
 +
 
 +
Стратегия 2: Дилер набирает, пока у него не будет столько же, сколько у игрока, и останавливается.
 +
 
 +
Предполагая, что каждая следующая карта достается из новой колоды, обучить стратегию поведения игрока. Начав со стратегии "останавливаться" на 20 и 21 проэмулировать ряд партий и построить вес успешности позиций, считая, что победа дает одно очко, поражение --- минус одно, ничья --- ноль.
 +
В качестве новой стратегии взять жадную стратегию при полученных весах. Повторять до сходимости. Позицией считать сумму карт в руке, открытую карту (ее стоимость) дилера и факт наличия в руке туза, которого вы считаете за 11.
 +
Задача зачитывается при наличии кода и описания полученных стратегий игрока, для двух стратегий дилера. Стратегия игрока описывается, как решения игрока ("взять" или "остановиться") при заданном числе очков в руке, открытой карты дилера и наличия в руке туза за 11 очков.
 +
 
 +
=== OCR ===
 +
 
 +
Цель задачи научиться распознавать печатный (или рукописный) текст на английском переводя его из картинки в последовательность символов.
 +
Для этого необходимо реализовать следующие компоненты:
 +
 
 +
1. Построить сеть (HMM или любую другую модель) для которой будет решаться задача MAP (поиск наиболее вероятного набора значений переменных при заданных свидетельствах).
 +
 
 +
2. Обучить распределения вероятностей соседних букв (возможно более сложных связей) на основе словаря.
 +
 
 +
3. Реализовать распознование отдельного символа (на основе нейронной сети или как вам будет угодно). Базу для обучения можно взять тут: http://www.ee.surrey.ac.uk/CVSSP/demos/chars74k/
 +
 
 +
4. Реализовать разбиение картинки на отдельные слова и символы.
  
3. Блек-Джек.
+
5. Объединить все вышеописанное.
Задача научиться играть в Блек-Джек против диллера с фиксированной стратегией.
+
Правила игры: игроку и диллеру сдается по две карты. Если у игрока 21 очко при сдаче, то диллер открывает свою руку и они сравниваются. Если этого не произошло, то игра продолжается по правилам описанным далее. Игрок видит свои карты и одну карту диллера. Каждый ход игрок выбирает одну из двух возможностей: взять еще карту или остановиться. Ходы игрока продолжаются до тех пор пока он не выберет "остановиться" или не наберет больше 21 очка.
+
Если игрок набрал больше 21, то он считается проигравшим. Если игрок остановился, то диллер начинает набирать карты. Стратегия 1: Диллер набирает пока у него не будет 17 или больше и останавливается. Стратегия 2: Диллер набирает пока у него не будет столько же сколько у игрока и останавливается.
+
Карты имеют следующую стоимость в очках: Туз --- 1 или 11 по выбору игрока, остальные картинки 10, остальные карты по своему значению.
+
Предполагая, что каждая следующая карта достается из новой колоды, обучить стратегию поведения игрока. Начав со стратегии останавливаться на 20 и 21 проэмулировать ряд партий и построить вес успешности позиций, считая, что победа дает одно очко, поражение --- минус одно, ничья --- ноль.
+
В качестве новой стратегии взять жадную стратегию при полученных весах. Повторять до сходимости. Позицией считать сумму карт в руке, открытую карту (ее стоимость) диллера и факт наличия в руке туза, которого вы считаете за 11.
+
Задача зачитывается при наличии кода и описания полученных стратегий игрока, для двух стратегий диллера. Стратегия игрока описывается, как решения игрока (взять или остановится) при заданном числе очков в руке, открытой карты диллера и наличия в руке туза за 11 очков.
+
  
 
== Список литературы ==
 
== Список литературы ==
  
 
== Полезные ссылки ==
 
== Полезные ссылки ==

Текущая версия на 14:45, 30 октября 2012

Лектор - Николенко С. И.

Лекции

Домашние задания

Крестики-нолики

Требуется написать программу, которая обучается играть за первого игрока (крестики) против фиксированной стратегии второго игрока (нолики). В случае ничейного результата партия считается проигранной крестиками. В качестве стратегии второго использовать следующую: если нолики могут своим ходом составить ряд из трех нолей, то они делают этот ход. Если такого хода нет, то ход выбирается случайно равновероятно из всех незанятых клеток. Попробовать две стратегии обучения: TD (когда после хода ценность позиции сдвигается в сторону ценности новой позиции) и стратегию, которая премирует все позиции которые встретились в партии, если крестики победили и депремирует, если проиграли. В качестве стратегии выбора хода крестиков реализовать \epsilon-жадную и температурную. Программа должна, непрерывно обучаясь, провести 100 раз по 1000 партий и для каждой тысячи вывести число побед крестиков в консоль или в файл. Задача зачитывается при наличии кода и четырёх файлов (для всех сочетаний стратегии поведения и стратегии обучения), показывающих динамику числа побед.

Про монетку

Рассмотрим следующую игру: У вас есть сумма от 1 до 99 монет, вы делаете ставку и подбрасываете монетку. Если выпал "орёл", то ставка удваивается, иначе теряется. Цель игры набрать ровно 100 монет. Зафиксируем базовую стратегию: Если сумма меньше или равна 50 монетам, то ставим всё, иначе недостающую до 100 сумму. Пользуясь данной стратегией, проэмулировать по 100 игр из каждого начального состояния. По результатам эмуляции для каждого положения вычислить "взвешенный успех" --- долю игр, прошедших через это состояние, закончившихся успехом. По результатам вычисления выбрать новую стратегию ставок --- жадную, по отношению к новым весам позиций. Повторить такую процедуру до схождения стратегии (до момента, когда ставки перестанут меняться). Провести такое моделирование для разной вероятности выпадения орла --- 0.4, 0.5, 0.6 и вывести получившиеся оптимальные стратегии. Задача зачитывается при наличии кода и трёх файлов (для трёх вероятностей выпадения орла), содержащих полученную стратегию в виде пар чисел "состояние"--"ставка".

Блекджек

Задача: научиться играть в блекджек против дилера с фиксированной стратегией.

Правила игры: игроку и дилеру сдаётся по две карты. Если у игрока 21 очко при сдаче, то дилер открывает свою руку и они сравниваются. Если этого не произошло, то игра продолжается по правилам, описанным далее. Игрок видит свои карты и одну карту дилера. Каждый ход игрок выбирает одну из двух возможностей: взять еще карту или остановиться. Ходы игрока продолжаются до тех пор, пока он не выберет "остановиться" или не наберёт больше 21 очка. Карты имеют следующую стоимость в очках: туз --- 1 или 11 по выбору игрока, остальные картинки 10, остальные карты по своему значению. Если игрок набрал больше 21, то он считается проигравшим. Если игрок остановился, то дилер начинает набирать карты.

Стратегия 1: Дилер набирает, пока у него не будет 17 или больше, и останавливается.

Стратегия 2: Дилер набирает, пока у него не будет столько же, сколько у игрока, и останавливается.

Предполагая, что каждая следующая карта достается из новой колоды, обучить стратегию поведения игрока. Начав со стратегии "останавливаться" на 20 и 21 проэмулировать ряд партий и построить вес успешности позиций, считая, что победа дает одно очко, поражение --- минус одно, ничья --- ноль. В качестве новой стратегии взять жадную стратегию при полученных весах. Повторять до сходимости. Позицией считать сумму карт в руке, открытую карту (ее стоимость) дилера и факт наличия в руке туза, которого вы считаете за 11. Задача зачитывается при наличии кода и описания полученных стратегий игрока, для двух стратегий дилера. Стратегия игрока описывается, как решения игрока ("взять" или "остановиться") при заданном числе очков в руке, открытой карты дилера и наличия в руке туза за 11 очков.

OCR

Цель задачи научиться распознавать печатный (или рукописный) текст на английском переводя его из картинки в последовательность символов. Для этого необходимо реализовать следующие компоненты:

1. Построить сеть (HMM или любую другую модель) для которой будет решаться задача MAP (поиск наиболее вероятного набора значений переменных при заданных свидетельствах).

2. Обучить распределения вероятностей соседних букв (возможно более сложных связей) на основе словаря.

3. Реализовать распознование отдельного символа (на основе нейронной сети или как вам будет угодно). Базу для обучения можно взять тут: http://www.ee.surrey.ac.uk/CVSSP/demos/chars74k/

4. Реализовать разбиение картинки на отдельные слова и символы.

5. Объединить все вышеописанное.

Список литературы

Полезные ссылки