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

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

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

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

Содержание

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

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

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


Задание студентам: продолжить оформление этой странички
  • внести себя в участники (317)
  • написать тему текущей работы (417-517)
  • выложить курсовые (517, частично 417)

Дь-ов


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

Расписание заседаний пока не составлено.

Основная работа начнётся с октября 2012 года. Дь-ов


См. архив:

Наши успехи

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

Научная работа - задания

Участник Задание (каждый сам заполняет свою ячейку) Комментарий
Бобрик Ксения (517)
Ермушева Александра (517)
Кириллов Александр (517)
Фигурнов Михаил (517) Обобщение метрического критерия k-сингулярности на метрики из разрезного конуса \operatorname{CUT}_q
Кондрашкин Дмитрий (417)
Нижибицкий Евгений (417)
Остапец Андрей (417)
Фонарёв Александр (417)

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

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

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

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

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

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

2013

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

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

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

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

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

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

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

  • Курсовая работа «Метрические критерии k-сингулярности».
  • Второе место на конкурсе Интернет-математика «Relevance Prediction Challenge» (лучший результат среди российских участников).
  • Figurnov M., Kirillov A. Linear combination of random forests for the Relevance Prediction Challenge - 2012
  • Фигурнов М.В. Линейная комбинация случайных лесов в задаче предсказания релевантности документов. // Сборник тезисов XIX Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2012». Секция «Вычислительная математика и кибернетика». М.: МАКС Пресс, 2012, с. 107-109.

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

Год выпускаВыпускники:
Аспирант, 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)

2012

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

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-координат съёмки и т.п.
  • Задача кредитного скоринга Прогнозирование надёжности клиента банка по обязательствам выплаты процентов кредита.