Алгебра над алгоритмами и эвристический поиск закономерностей

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

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

Руководитель спецсеминара: д.ф.-м.н. Дьяконов Александр Геннадьевич

Содержание

Работа на спецсеминаре

В рамках работы на спецсеминаре есть два направления исследования:

  1. Теоретическое. Проводится в рамках алгебраического подхода к решению задач распознавания. Суть подхода: на алгоритмах, которые решают задачи обработки и анализа данных, специальным образом вводятся алгебраические операции. Например, можно складывать алгоритмы (получается опять алгоритм), умножать и т. д. Доказано (Ю. И. Журавлёвым), что среди получаемых алгебраических выражений над «естественными» алгоритмами есть высокоэффективные алгоритмы. На спецсеминаре рассматриваются вопросы: как их строить, анализировать, реализовывать на ЭВМ и т. д. и т. п. Данное направление представляет особую ценность студентам, которые хотят получить самостоятельные результаты в науке и продолжить обучение в аспирантуре.
  2. Прикладное. Решаются реальные прикладные задачи анализа данных (data mining). Например, классификация сигналов головного мозга, классификация сигналов-показаний работы механизмов, настройка спам-фильтров, автоматическая рубрикация текстов, прогнозирование финансовых временных рядов. От студентов требуется желание глубоко понять задачу (данные и скрытые в них закономерности), умение быстро осваивать новые методы (в незнакомой области), хорошо программировать, выдвигать гипотезы и фантазировать (последнее очень важно).

Заседания 2011-2012 уч. года (весенний семестр)

Лекция "Введение в анализ данных".

Просьба к участникам семинара - посмотреть, высказать свои замечания и предложения по улучшению. В ближайшие 2 дня надо её доделать... принимаю любые предложения, например, что добавить ещё в глоссарий. Спасибо. Дь-ов 16:45, 4 марта 2012 (MSK)


Число Докладчик Доклад
03.03.12 Дьяконов А.Г. Обзор использованных алгоритмов в конкурсе What Do You Know?
03.03.12 Нижибицкий Евгений (317) Доклад о применении теории нечетких множеств
03.03.12 Бобрик Ксения (417) Обзор использованных алгоритмов в конкурсе Algorithmic Trading Challenge
03.03.12 Ермушева Александра (417) Обзор использованных алгоритмов в конкурсе Algorithmic Trading Challenge
03.03.12 Фонарев Александр (317) Обзор алгоритмов поиска ближайших соседей по материалам http://simsearch.yury.name/tutorial.html

Наши успехи

Кто Что
Кириллов Александр, Фигурнов Михаил Второе место на конкурсе Интернет-математика «Relevance Prediction Challenge» (лучший результат среди российских участников). Статья с отчётом об используемых методах.

Научная работа - задания (весенний семестр 2012 года)

Участник Задание (каждый сам заполняет свою ячейку) Комментарий
Бобрик Ксения (417)
Ермушева Александра (417)
Кириллов Александр (417)
Фигурнов Михаил (417)
Кондрашкин Дмитрий (317) Метрические критерии представления функции двух переменных в виде суммы функций одного переменного
Нижибицкий Евгений (317) Обзор и анализ методов классификации текстов
Остапец Андрей (317) Курсовая работа на тему «Обзор методов линейного регрессионного анализа»
Фонарёв Александр (317) Обзор и анализ различных алгоритмов бустинга

Заседания 2011-2012 уч. года (осенний семестр)

Число Докладчик Доклад
10.12.11 Кириллов Александр (417) Обзор используемых алгоритмов в конкурсе Интернет-математика — 2011
10.12.11 Фигурнов Михаил (417) Обзор используемых алгоритмов в конкурсе Интернет-математика — 2011
10.12.11 Кондрашкин Дмитрий (317) Доклад по основам теории нечетких множеств
10.12.11 Остапец Андрей (317) Доклад о применении мультимножеств в анализе данных на основе статьи Metrics for Mining Multisets
26.11.11 Бобрик Ксения (417) Доклад по диссертации Dr. Jilles Vreeken "Making pattern mining useful"
26.11.11 Платонова Елена (517) Доклад по теме «Классический информационный поиск: реализация и методы» по книге "Введение в информационный поиск" К. Маннинга
26.11.11 Дьяконов А.Г. Доклад по теме «Пополнение линейного пространства нелинейными операциями». Часть доклада содержится в статье Нормировки и деление
12.11.11 Ермушева Александра (417) Доклад по диссертации Dr. Wenjun Zhou "Correlation analysis: from computational hardness to practical success"
29.10.11 Дьяконов А.Г. Доклад О двух алгоритмах рекомендательной системы
29.10.11 Кириллов Александр (417) Доклад по диссертации Dr. Tianyi Wu “A Framework for Promotion Analysis in Multi-Dimensional Space”
29.10.11 Фигурнов Михаил (417) Доклад по диссертации Dr. Michael Hay “Enabling Accurate Analysis of Private Network Data”
18.10.11 Нижибицкий Евгений (317) Доклад «Временные ряды из геометрии и топологии пространственных паттернов» по одноименной лекции
15.10.11 Остапец Андрей (317) Доклад «Фракталы, аттракторы, нейронные сети» по одноименной лекции
15.10.11 Фонарёв Александр (317) Доклад «Эмбедология и нейропрогноз» по одноименной лекции
15.10.11 Кондрашкин Дмитрий (317) Доклад «Стохастическая динамика, марковские модели и прогноз» по одноименной лекции

Заседания 2010-2011 уч. года (весенний семестр)

Дата Докладчик Доклад
11.05.11 Бобрик Ксения (317) Доклад по теме «Прогнозирование временных рядов»
04.05.11 Платонова Елена (317) Доклад по теме «Задачи и методы информационного поиска»
20.04.11 Ермушева Александра (317) Доклад по теме «Задачи и методы коллаборативной фильтрации»
13.04.11 Кириллов Александр (317) Доклад по теме «Предсказание связности графов»

Участники спецсеминара

Год выпускаУчастники:
2014

Кондрашкин Дмитрий

  • Тема работы «».

Нижибицкий Евгений

  • Тема работы «».

Остапец Андрей

  • Тема работы «».

Фонарев Александр

  • Тема работы «».
2013

Бобрик Ксения

  • Тема работы «Прогнозирование временных рядов».

Ермушева Александра

  • Тема работы «Коллаборативная фильтрация».

Кириллов Александр

  • Тема работы «Прогнозирование связности графа».

Фигурнов Михаил

  • Тема работы «».
2012

Платонова Елена

Выпускники спецсеминара

Год выпускаВыпускники:
Аспирант, 2010

Карпович Павел

  • Карпович П. А. k-сингулярные системы точек в пространстве l1 // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009», секция «Вычислительная математика и кибернетика», М: МАКС Пресс, 2009. — C.34.
  • Карпович П. А. Эффективная реализация алгоритмов распознавания образов // Журнал вычислительной математики и математической физики, 2009, Т. 49, № 8. C.1510-1516
  • Карпович П. А. О задаче разделения системы точек в пространсте l1 на подсистемы с невырождеными матрицами попарных расстояний // Тезисы конференции МФТИ, Секция проблем интеллектуального анализа данных, распознавания и прогнозирования. — М.: ГОУ ВПО «Московский физико-технический институт (государственный университет)», 2009. — С. 52.
  • Карпович П. А., Дьяконов А. Г. Критерий k-сингулярности систем точек в алгебраическом подходе к распознаванию // 14-я Всероссийская конференция «Математические методы распознавания образов» Владимирская обл., г. Суздаль, 21-26 сентября 2009 г.: Сборник докладов. — М. МАКС Пресс, 2009. С. 41-44.
  • Карпович П.А. Разделение системы точек на подмножества с невырожденными матрицами попарных расстояний // Материалы XVII Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2010». – М.: Изд. отдел ВМиК МГУ, МАКС Пресс, 2010. – С. 87-88.
  • Карпович П.А. Критерии k-сингулярности и разделение 1-сингулянрных систем // Вестник Московского университета. Секция 15. “Вычислительная математика и кибернетика” – 2010. № 4.
  • Карпович П.А. Дьяконов А.Г. K-сингулярные системы точек, приложения в алгебраическом подходе к распознаванию // Тезисы докладов Международной научной конференции ИОИ-8 Кипр, Пафос - 2010

Диссертация: «K-сингулярные системы точек в алгебраическом подходе к распознаванию образов» (2010, успешно защищена 18.02.2011 по специальности 01.01.09)

2010

Ахламченкова Ольга

  • Дипломная работа «Машинное обучение для ранжирования документов»

Токарева (Одинокова) Евгения

2009

Власова Юлия

  • Дипломная работа «Генерация признаков в задаче классификации сигналов» (PDF, 929 КБ).
  • Власова Ю. В. Применение генетических алгоритмов в задаче классификации сигналов (приложение в BCI) // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009», секция «Вычислительная математика и кибернетика», М: МАКС Пресс, 2009. — C.17.
  • Власова Ю. В. Применение генетических алгоритмов в задаче классификации сигналов (приложение в BCI) // Доклады 14-й Всероссийской конференции «Математические методы распознавания образов», М.: МАКС Пресс, 2009, С. 96-99.

Логинов Вячеслав

  • Дипломная работа «Прогнозирование временных рядов с помощью рекуррентных нейросетей с откликом»

Фёдорова Валентина

  • Дипломная работа «Локальные методы прогнозирования временных рядов»
  • Федорова В. П. Локальные методы прогнозирования временных рядов // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009», секция «Вычислительная математика и кибернетика», М: МАКС Пресс, 2009. — C.87.

Чучвара Алексндра (бакалавр)

2008

Ломова Дарья

  • Дипломная работа «Выделение закономерностей во временных рядах методом анализа главных компонент»

Вершкова Ирина

  • Дипломная работа «Локальная и глобальная согласованность в интеллектуальном анализе данных»
2007

Кнорре Анна

  • Дипломная работа «Надежность алгоритмов распознавания, основанных на синтезе дизъюнктивных нормальных форм»

Карпович Павел

  • Дипломная работа «Эффективная реализация алгоритмов распознавания образов»

Сиваченко Евгений

  • Дипломная работа «Нейросетевой поиск логических закономерностей»
2006

Ховратович (Курятникова) Татьяна

  • Дипломная работа «Критерии корректности в задачах распознавания образов с малым числом признаков»
  • Курятникова Т. С. Критерии корректности алгебраического и линейного замыкания АВО для малых размерностей // Материалы XII Международной конференции студентов, аспирантов и молодых учёных «Ломоносов», секция «Вычислительная математика и кибернетика». М.: Изд. отд. ВМиК МГУ, 2006. — c. 32-33.

Мошин Николай

  • Дипломная работа «Эффективная реализация алгоритмов решения задачи выполнимости»
2005

Каменева Наталия

  • Дипломная работа «Эффективные логические алгоритмы распознавания, основанные на синтезе ДНФ»

Силкин Леонид

  • Дипломная работа «Оценка разделяющей способности признаков при кодировании информации в задачах распознавания»

Некоторые решаемые прикладные задачи

  • Прогнозирование временных рядов По характеристикам процесса в прошлом предсказать поведение в будущем. Знание о прошлом может быть неполным или ошибочным. Типичный пример: прогнозирование денежных сумм, которые будут сниматься с банкомата в течение следующей недели.
  • Классификация технических сигналов и сигналов головного мозга По описанию изменения некоторой характеристики процесса необходимо определить её класс. Например, по электрокортикограмме определить ментальное состояние человека. При этом обучающая выборка (данные, которые у нас есть) была собрана достаточно давно, а тестирование алгоритма будет проводиться потом (при изменённых внешних условиях, а следовательно, при изменённых характеристиках данных).
  • Фильтрация спама Настроить спам-фильтр на некотором универсальном обучающем множестве (данных спам-ловушек) так, чтобы он хорошо работал на компьютере конкретного пользователя (без дополнительной донастройки).
  • Иерархическая классификация текстов Написать алгоритм автоматической категоризации документов. Например, новостные рассылки необходимо распределить по каталогам «спорт/футбол», «спорт/биатлон», «музыка/концерты», «музыка/рок/исполнители» и т. д.
  • Ранжирование документов на основе обучающего множества Написать алгоритм, который оценивает релевантность документа поисковому запросу. Для фиксированного запроса упорядочить документы (используя их признаковые описания) так, чтобы порядок отражал «адекватность» запроса.
  • Прогноз связности графа социальной сети Предсказать изменения динамического графа социальной сети, в частности, появление новых рёбер.
  • Прогнозирование успешности грантов и проектов По описанию заявки оценить перспективность выполнения данного проекта.
  • Разработка рекомендательного алгоритма, который делает актуальные предложения купить какой-то товар, воспользоваться услугой или прочитать материал.
  • Предсказывание визитов покупателей и сумм покупок для сети супермаркетов Разработка алгоритма, который предсказывает дату первого визита и сумму покупки каждого клиента.
  • Оценка фотографий по метаданным Прогноз «интересности» фото-материалов на основе анализа названия, описания, GPS-координат съёмки и т.п.
  • Задача кредитного скоринга Прогнозирование надёжности клиента банка по обязательствам выплаты процентов кредита.