Численные методы обучения по прецедентам (практика, В.В. Стрижов)

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

Перейти к: навигация, поиск
Статья предназначена прежде всего для студентов группы 774, она будет наполняться в течение этого семестра.


Список тем для студентов группы 674 находится здесь.



Содержание

Московский физико-технический институт, Факультет управления и прикладной математики

’’Численные методы обучения по прецедентам’’ — практические занятия, включающие прикладные аспекты создания алгоритмов машинного обучения. Семестровый курс содержит 32 часа практических занятий. В ходе занятий студент получает несколько заданий на исследование свойств алгоритмов. Результатом практики являются отчеты о выполнении заданий. Все задания нужно сдать по меньшей мере за неделю до экзамена, чтобы успеть получить рецензию и исправить недочеты.


Содержание отчета

Отчет состоит из следующих материалов:

  • статья на сайте machinelearning.ru,
  • отчет о вычислительном эксперименте,
  • исходный код алгоритма.

Статья на сайте machinelearning.ru

Статья должна иметь следующие разделы:

  1. Краткое введение в тему работы, содержащее определение алгоритма.
  2. Постановка задачи в математической нотации, содержащая обязательные слова «Дано» (задано), и «Найти» (требуется).
  3. Описание алгоритма в терминах поставленной задачи.
  4. Вычислительный эксперимент, поставленный для изучения свойств данного алгоритма. Раздел обязательно содержит описание графиков, иллюстрирующих работу алгоритма и слово «Результат» (вывод).
  5. Ссылка на программную реализацию. Например: DataGenerationExample.
  6. Ссылка на список статей сайта machinelearning.ru по данной тематике.
  7. Список литературы, откуда был взят алгоритм (с полным библиографическим описанием, см. Приложение А).

Рекомендуемые название разделов:

  1. (без названия)
  2. Постановка задачи
  3. Алгоритм (вариант — Описание алгоритма)
  4. Пример (вариант — Вычислительный эксперимент)
  5. Исходный код (ссылка, сам исходный код давать не нужно)
  6. Смотри также (список ссылок на machinelearning, или на wiki)
  7. Литература

Рекомендуемое название статьи: «Название вашего алгоритма (пример)».

Образец статьи: Логистическая регрессия (пример)

Вычислительный эксперимент

Вычислительный эксперимент состоит следующих шагов:

  1. Порождение модельных данных или загрузка реальных данных.
  2. Предобработка данных (если требуется).
  3. Визуализация данных (если требуется).
  4. Выполнение алгоритма, получение результатов.
  5. Исследование результатов работы алгоритма.
  6. Визуализация результатов.
  7. Выводы.

Образец отчета о вычислительном эксперименте и способ его автоматического получения см. здесь. Отчет должен содержать цель исследования (она может отличаться от постановки задачи), результаты визуализации, полученные результаты и выводы. Основные элементы отчета (перечисленные в предыдущем предложении), наиболее важные строки кода и графики должны попасть в раздел «Вычислительный эксперимент» статьи на сайте machinelearning.ru.

Написание исходного кода

Работа с репозиторием

Исходный код должен находится в репозитории https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms. О том, как работать с репозиторием, см. здесь. Права на добавление файлов в репозиторий можно получить у администратора вашей группы.

В репозитории находятся следующие папки общего пользования:

  • data – реальные данные для загрузки, общие для всех проектов (данные к конкретному заданию можно хранить в папке AlgorithmName или AlgorithmName\data),
  • common – функции общего пользования, относящиеся к алгоритмам,
  • utilities – вспомогательные функции общего пользования, относящиеся к вводу данных и рисованию графиков.

В репозитории нужно создать папку, название папки – название задания (алгоритма). В папке должен лежать основной файл demoAlgorithmName – файл отчета о вычислительном эксперименте (и, возможно, файл loadDataName – файл порождения модельных данных или загрузки реальных данных). Дополнительные файлы могут лежать в той же папке или в подпапках.

В процессе автоматической генерации отчета появляется папка html, которую, вместе с файлами .html и .gif, можно также загрузить в репозиторий.


Совет: не загружайте в репозиторий вспомогательный файл операционной системы Thumbs.db, он вам будет мешать.


Программирование

Рекомендации программистам и введение в Матлаб см. здесь. Настоятельно рекомендуется прочесть соглашение об именах в статье Документирование функций Matlab. Там же рассказано о создании отчетов о вычислительных экспериментах.

Процесс рецензирования

После написания текста статьи, кода алгоритмов и кода вычислительного эксперимента, студент должен написать рецензентам письмо о готовности к получению рецензии. После этого

Рецензент:

  • В статье на ML ставит пометки <ref>Замечание к статье</ref>.
  • В m-файлах ставит пометки % FIXIT Замечание к коду.

Студент:

  • В статье на ML вносит требуемые исправления и снимает пометки <ref>Замечание к статье</ref>. В дальнейшем рецензент сравнивает новую и старую версии статьи средствами ML (вкладка "история").
  • В m-файлах вносит требуемые исправления и исправляет пометки % FIXIT на FIXED.
Рецензент отвечает за качество работы, но должен быть благожелателен к исполнителю.


Полезные материалы, сводный список ссылок

Задачи

Для всех задач. Задана модельная выборка: n признаков, m=m_1+m_2 объектов, каждый из объектов принадлежит одному из 2-х классов. Распределение случайной величины, соответствующей признаку, описывающему класс, задано. Заданы параметры распределения. Для удобств визуализации примем n=2, но программировать алгоритмы нужно произвольного (натурального) числа признаков. При тестировании алгоритмов задается также разбиение выборки на обучающую и контрольную подвыборки.

Задача 1: Логистическая регрессия для решения задач классификации (пример) - выполняет Дорофеев Д.

Для заданной выборки требуется восстановить логистическую регрессию. При этом можно использовать библиотеку Матлаба или процедуру, описанную на сайте machinelearning.ru. Можно также или написать метод оптимизации параметров самостоятельно.

Построить графики для различных модельных выборок. На каждом графике показать разделяющую гиперплоскость, показать исходные и восстановленные метки класса для каждого объекта.

Задача 2: Метод ближайших соседей (пример)- выполняет Литвинов И., Метод k взвешенных ближайших соседей (пример) - выполняет Янович Ю.

Для заданной выборки требуется восстановить классификацию по K ближайшим соседям.

Построить графики для различных модельных выборок. На каждом графике показать исходные и восстановленные метки класса для каждого объекта. При различных значениях K показать принадлежность каждого узла сетки на плоскости, в которой лежат объекты, к одному из двух классов.

Задача 3: Функции радиального базиса (пример) — выполняет Островский А.

Для заданной выборки требуется восстановить классификацию с помощью функций радиального базиса.

Построить графики для различных модельных выборок. На каждом графике показать исходные и восстановленные метки класса для каждого объекта. Показать эквипотенциальные линии на графике.


Задача 4: Однослойный персептрон (пример) — выполняет Панов М.

Для заданной выборки требуется восстановить классификацию с помощью нейронных сетей с одним скрытым слоем.

Построить графики для различных модельных выборок. На каждом графике показать исходные и восстановленные метки класса для каждого объекта.


Задача 5: Решающие деревья (пример) - выполняет Скипор К.

Для заданной выборки требуется восстановить классификацию с помощью решающих деревьев.

Построить графики для различных модельных выборок. На каждом графике показать исходные и восстановленные метки класса для каждого объекта. Выполнить статистический анализ результатов классификации. Показать цветом на графике области определения для каждого класса.


Задача 6: Логические алгоритмы классификации (пример)

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

Построить графики для различных модельных выборок. На каждом графике показать исходные и восстановленные метки класса для каждого объекта. Выполнить статистический анализ результатов классификации. Показать цветом на графике области определения для каждого класса.


Задача 7: EM-алгоритм (пример) — выполняет Спирин Н., EM-алгоритм с последовательным добавлением компонент (пример) — выполняет Павлов К.

Для заданной выборки требуется восстановить классификацию (параметры смеси гауссовских распределений) с помощью EM-алгоритма.

Построить графики для различных модельных выборок. На каждом графике показать исходные и восстановленные метки класса для каждого объекта. Показать на графике функцию плотности распределения.


Задача 8: Метод Парзеновского окна (пример) - выполняет Зайцев А.

Для заданной выборки требуется восстановить классификацию методом Перзеновского окна с ядром из заданного набора.

Построить графики для различных модельных выборок. На каждом графике показать исходные и восстановленные метки класса для каждого объекта.


Задача 9* — со звездочкой (Регрессия и генетические алгоритмы)

Задана регрессионная выборка. Принята линейная модель. Требуется (с помощью генетического оптимизационного алгоритма) найти параметры модели, доставляющие оптимум критерию качества. Критерий качества задан Яндексом. На значения параметров наложены ограничения (см. описание алгоритма Lasso на machinelearning.ru).

Данная задача поставлена с учетом условий конкурса Яндекса «Интернет-математика 2009».

Задача 10* — со звездочкой (Регрессия и метод опорных векторов)

Задана регрессионная выборка. Принята линейная модель. Требуется (с помощью метода опорных векторов) найти параметры модели, доставляющие оптимум критерию качества. Критерий качества задан Яндексом. На значения параметров наложены ограничения типа неравенств. (Предлагается использовать пакет SVM-light, версия для Матлаба, см. документацию к конкурсу на Яндексе).

Данная задача поставлена с учетом условий конкурса Яндекса «Интернет-математика 2009».

Задача 11 (творческая, обсуждается отдельно)

Разработать язык описания порождаемых модельных данных и систему визуализации модельных данных.

Задача 12 (техническая, обсуждается отдельно)

Разработать, оттестировать и документировать интерфейс «Полигон-Матлаб», а также систему визуализации результатов, полученных в результате запуска Полигоном алгоритмов классификации, выполненных на Матлабе.

Примечания к задачам

  1. Данная версия задач будет уточняться, особенно в части деталей реализации алгоритмов.
  2. Строка «Выполнить статистический анализ результатов классификации» означает, что требуется использовать стандартные процедуры

системы Полигон для запуска алгоритмов, а также сбора и обработки результатов их работ (либо процедуры, написанные в Матлабе, в случае отсутствия интерфейса с Полигоном).

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

Что делать сейчас (2-9 апреля 2009)

Выбрать задачу (или несколько), найти и прочитать теорию, сделать краткий конспект, записать вопросы по реализации алгоритмов (например, даже для такой несложной концепции, как решающие деревья, предложено не менее десяти алгоритмов оптимизации).

9 апреля обсуждаем как делаются модельные данные, разбираем детали выполнения работ.

Комментарии (9-16 апреля 2009)

Приняты следующие комментарии, добавляемые в код при его проверке:

% FIXIT - желательно изменить код (улучшить структуру кода или устранить ошибку), 
% NOTE - комментарий для обмена мнениями,
% TODO - желательно выполнить работу.

Для совместимости с системой Полигон желательно оформлять интерфейсы основных модулей следующим образом: 1) алгоритм классификации, регрессионная модель с параметрами w и матрицей "объект-признак" X

y = namemdl(w, X)

2) процедура обучения (оптимизации параметров алгоритма или модели) c вектором ответов y и структурными параметрами PP

w = namelearn(X,y, PP)

3) необязательная процедура тестирования

y = nametest(w, X)

Параметры w могут быть вектором или структурой. Структурные параметры PP являются структурой.

% X [m,n] object-feature matrix
% y [m,1] vector of object lables
% w [p,1] vector of parameters, OR
% w [structure] structure of parameters
% PP [structure] parameters of the method

Заготовка для статьи на MachineLearning.ru (16-22 апреля 2009)

Скачать заготовку

Подготовка к зачету (7 мая 2009)

Зачет будет проходить в виде презентации выполненной работы. Продолжительность презентации семь минут и три дополнительные минуты на вопросы. Цель презентации: показать, что результаты работы понятны специалисту, и могут быть им использованы в дальнейшем. Под специалистами понимаются ваши одногруппники и преподаватели кафедры К.В. Воронцов, А.В. Лисица, В.В. Стрижов.

Во время презентации требуется:

  • Назвать основные свойства алгоритма
  • Поставить задачу
  • Осветить основные принципы работы алгоритма (кратко, без деталей)
  • Описать интерфейсы всех модулей алгоритма
  • Показать работу алгоритма на примерах

На презентации используется:

  • Страница из machinelearning.ru (обязательно)
  • Код из sourceforge.net (обязательно)
  • Для удобства можно подготовить текстовый документ с описанием интерфейсов модулей (по желанию)
  • Отчеты о вычислительных экспериментах в html-формате (по желанию)
  • Слайды готовить не нужно

Советы:

  1. Подготовьте доклад с секундомером в руках
  2. Расскажите его другу, ответьте на его вопросы
  3. При подготовке m-файлов к показу, наведите порядок в папке:
    • Файлы-скрипты желательно переименовать в demo_demoname.m
    • Графики желательно поместить в папку \fig
    • Имена и интерфейсы основных файлов должны соответствовать требованиям системы «Полигон»

Зачет состоится в аудитории 355, (21 мая 11:00)

Проектор, компьютер, интернет будут в аудитории.

Дополнительный зачет состоится в аудитории 355, (26 июня 15:00)

Условия проведения зачета см. выше.

На следующий год

Планы (май 2009) Состояние (октябрь 2009)
Дать UML, наиболее полезную для этих задач версию стандарта (одна лекция). Этим решаем проблему неудовлетворительного качества проектирования интерфейсов и порядка вызова модулей. Принят IDEF0
Требовать схему UML в ML-статье, в разделе "Исходный код". Предложен systemdocs
Написать соглашение об именах, версию для этого проекта. Используем Matlab Style-Guide
Если ML будет такой же медленной, отказаться от нее и сделать вариант отчета LaTeX->PDF, хранимый на SourceForge. ML работает быстро!
Принять стиль Гугл (возможно, упрощенную версию стилевых требований), опубликовать. Создать систему кросс-приемки и кросс-тестирования. Часть systemdocs
Принять стандарт каталогизации работ (возможно, каталогизировать ранние работы за три года - около 40 работ). Пока нет, требует времени
Отказаться от копирования материалов лекций в статью. Частично решено
Личные инструменты