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

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

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


Моя первая научная статья

Участвуют эксперты, индивидуальные консультанты и студенты Кафедры анализа данных ФИВТ МФТИ.

  • Короткая ссылка на эту страницу: bit.ly/1yhhdTC


Выложен разбор задач по Матлабу (ДЗ-1), pdf


Результаты

Автор Задача пробного программирования Ссылка Консультант Рецензент ДЗ-1 ДЗ-2 (Номер задачи) Буквы Сумма Оценка
Бабанин Иван Simplification of the IR models structure code,

paper

Кузнецов М.П. 2.5 3 (22) AIL>BR>> 5 7
Давоян Геворг Автоматизация построения cut-based классификаторов для отбора "интересных" событий в физике частиц [1] (no code),

paper

Рогожников Алексей 3 0 AIL0S0B-RC--V 5.25
Елтышев Евгений Выявление тематической структуры сервиса Ответы@mail.ru code, paper Анна Потапенко 4 3 (1) AILSBRСV--T--D--E-- 9 8
Жигунов Андрей Поиск внешней и внутренней границ радужки на изображении глаза методом триангуляции. code, paper, slides Матвеев И.А. 1.5 2 (21) A-ILSBRCVTDES 11.75 8
Ивановский Дмитрий Построение интегрального индикатора по многоиндексной матрице оценок нескольких экспертов code, paper, slides Бахтеев Олег 1.5 3 (3) A-I--L-S-BR-C--V0TD--E0S 6.5 8
Липин Дмитрий Supervised rank aggregation with monotone feature transformation code,

paper, slides

Михаил Кузнецов 4.5 3 (8) AILSBRCVT+DEHS 13.25 8
Саитгалин Андрей Получение оценки разреженной ковариационной матрицы для нелинейных моделей (нейросетей) code, paper, slides Александр Адуенко 4 3 (4) AILSBR-C-V-TES 10.25 9
Талипов Камиль Определение области затенения радужки кластеризацией, основанной на локальных текстурных признаках code, paper, slides Матвеев И.А. 1.5 3 (14) AILSBRCVTDE 11 9
Янина Анастасия Рекомендация статей коллективного блога на основе тематической модели code, paper, slides Ромов Петр 0 3 (10) AILSBRCVTDES 12 10
Панин Александр Прунинг oblivious decision trees code, paper Алексей Рогожников, Андрей Устюжанин 0 0 AILS0BRCV 7
Гущин Михаил Устойчивость и другие свойства метрики AMS [2] (no code), paper Татьяна Лихоманенко, Андрей Устюжанин 0 0 AIL 3

Работа и консультации

  1. Работы сдаются в течение недели.
  2. Желательна итеративная сдача работ, начинать показ лучше в выходные.
  3. Дедлайн последней версии работы: среда 6:00am (проверка занимает всю среду).
  4. В отчет будет добавлен пункт об учете времени, затраченном на выполнение проекта по неделям.
  5. Каждый этап работ + 1 балл по системе (А--, А-, А, А+, А++). Несделанная работа — A0. Мотивированный перенос работы — знак «A>».

Расписание

Дата ДЗ Тема лекции Результат для обсуждения Код
Февраль 12 Вводная лекция. Задано ДЗ-1. --
19 1 Начало, демонстрация интерфейсов. Выбор задачи пробного программирования Регистрация в ML и SF, установлены все необходимые инструменты, прочитаны вводные тексты. --
Дата ДЗ Что делаем Результат для обсуждения Код
26 2 Решить пробную задачу, написать код. Выбор задачи Пробный код написан и загружен в репозиторий вместе с иллюстрирующими рисунками. Тема в ML и ссылка на работу в SF помещена напротив фамилии. Test
Март 5 3 Составить список публикаций по выбранной задаче, найти данные. Написать аннотацию и введение с обзором собранной литературы. Аннотация (600 знаков), введение (1-2 страницы), список литературы в bib-файле. Abstract, Introduction, Literature
12 4 Поставить задачу и базовый вычислительный эксперимент. Провести первичный анализ работы алгоритма. Постановка задачи (0.5-1 страница), код, отчет о работе базового алгоритма (кратко). Statement, Basic code, Report
19 5 Поставить вычислительный эксперимент на основе предлагаемого алгоритма с учетом предыдущих результатов. Код, визуализация полученных результатов, анализ ошибки, анализ качества. Code, Visualization
26 6 Описание алгоритма. Алгоритмическая часть статьи (второй / третий раздел). Theory
Апрель 2 7 Описание теоретической части и вычислительного эксперимента. Описание рисунков, выводы, заключение. Черновой вариант статьи с разделами «Вычислительный экперимент» и «Заключение». Document
9 8 Завершение вычислительного эксперимента. Описание эксперимента с анализом ошибок. Error
16 8 Контрольная точка — показ статьи в целом. Доработанная статья. сHeck
23 9 Доклады и обсуждение. Статья подана в журнал. Show, Journal, RevieW

Задачи

Нумерация задач может быть произвольной, но без повторения номеров.

Шаблон описания задачи

  • Название: Название, под которым статья подается в журнал.
  • Задача: Описание или постановка задачи. Желательна постановка в виде задачи оптимизации (в формате argmin). Также возможна ссылка на классическую постановку задачи.
  • Данные: Краткое описание данных, используемых в вычислительном эксперименте, и ссылка на выборку.
  • Литература: Список научных работ, включающих 1) формулировку решаемой задачи, 2) ссылки на новые результаты, 3) основную информацию об исследуемой проблеме.
  • Базовой алгоритм: Ссылка на алгоритм, с которым проводится сравнение или на ближайшую по теме работу.
  • Решение: Предлагаемое решение задачи и способы проведения исследования. Способы представления и визуализации данных и проведения анализа ошибок, анализа качества алгоритма.
  • Новизна: Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала).
  • Консультант: Исследователь с опытом самостоятельного написания научных статей, желанием участвовать в работе еженедельно и возможностью оперативно отвечать на вопросы.


Список задач корректируется. Возможны существенные изменения. Заранее задачи выбирать не рекомендуется. В.В. Стрижов



Задача 1

  • Название: Использование методов визуализации графов для предсказания ссылок.
  • Задача: Предлагается решать задачу предсказания ссылок в графе (The Link Prediction Problem), максимизируя AUC на тестовой выборке.
  • Данные: Для начала предлагается использовать данные, взятые отсюда: http://snap.stanford.edu/data/ca-CondMat.html. Данный dataset описывает научное сотрудничество между авторами документов. Сеть содержит 23133 вершины и 93497 ребер. Скорее всего попробуем и другие данные.
  • Литература:
  • Базовой алгоритм: http://cseweb.ucsd.edu/~elkan/ECML2011LinkPrediction.pdf
  • Решение: На данный момент, очень хорошие результаты в этой области получают с помощью методов Matrix Factorization. Разложение матрицы смежности графа позволяет каждой вершине графа сопоставить набор скрытых признаков, на основании которых в последующем делается вывод о наличии или отсутствии ребра. С другой стороны, при визуализации графа в n-мерном евклидовом пространстве каждой вершине сопоставляется набор координат. На основании этих координат используя некоторые метрики можно судить о наличии или отсутствии ребра. В силу особенностей алгоритмов визуализации графов, вершины, относящиеся к разным компонентам, слабо связанным между собой, располагаются тем дальше друг от друга, чем меньше этих связей. Соответственно, при большом расстоянии вероятность возникновения ребра все меньше. Предлагается исследовать, насколько такой подход дает хороший результат в сравнении с результатами, полученными с помощью Matrix Factorization. Также, интересно проследить зависимость в качестве предсказания ссылок для алгоритмов визуализации графов и Matrix Factorization от размерности пространства скрытых признаков.
  • Новизна: Предлагается новый подход к задаче предсказания ссылок в графе, вероятно позволяющий получить сравнимое с Matrix Factorization качество при меньших размерностях пространства признаков, а также лучшее качество предсказания отсутствия ссылок.
  • Консультант: Самосват Егор

Задача 2

  • Название: Supervised rank aggregation with monotone feature transformation.
  • Задача: We address the problem of supervised rank aggregation, the task of combining the ranking results of individual rankers at meta-search [Yu-Ting Liu et al]. In supervised learning rank aggregation is formalized as optimization which minimizes disagreements between ranking results and the labeled data. In current research we propose to expand the Borda Fuse rule (linear combination of ranking vectors) by considering monotone transformations of the rankings.
  • Данные:
  • Литература
    • Problem statement
    • Yu-Ting Liu, Tie-Yan Liu, Tao Qin, Zhi-Ming Ma, and Hang Li. Supervised rank aggregation. In Proceedings of the 16th international conference on World Wide Web, pages 481–490. ACM, 2007.
  • Базовой алгоритм: Borda Fuse rule: linear combination of ranking vectors without monotone transformation.
  • Решение:
  • Новизна: The proposed class of monotone transformations allows to get any possible transformation of orders in Euclidean space. In the special case of the unit weight vector we get the vector of the Borda Count scores.
  • Консультант: Михаил Кузнецов

Задача 3

  • Название: Тематическая модель классификации
  • Задача: Дана коллекция документов, часть которых размечена по классам. Каждый документ может принадлежать многим классам. Требуется построить вероятностную тематическую модель и проверить гипотезу, что подбором стратегии инициализации и регуляризации в моделях ARTM возможно повысить качество классификации. Для реализации использовать библиотеку BigARTM.
  • Данные: Коллекции, использованные в [Rubin, 2012].
  • Литература:
    1. Rubin T. N., Chambers A., Smyth P., Steyvers M. Statistical topic models for multi-label document classification // Machine Learning. 2012, Vol.88, no.1-2., Pp.157–208.
    2. Vorontsov K. V., Potapenko A. A. Additive Regularization of Topic Models // Machine Learning. Special Issue “Data Analysis and Intelligent Optimization with Applications”. 2014. Русский перевод
  • Базовой алгоритм: Алгоритмы из [Rubin, 2012] или их аналоги в BigARTM, классические методы категоризации (Naϊve Bayes, SVM)
  • Решение: Комбинация регуляризаторов разреживания, сглаживания, декоррелирования, label regularization, и др. для мультимодальной тематической модели в библиотеке BigARTM. Подбор стратегий инициализации и регуляризации.
  • Новизна: Тематические модели с комбинированием большого числа регуляризаторов ранее не использовались для задач классификации.
  • Консультант: Пётр Ромов, Мурат Апишев, Константин Воронцов.

Задача 4

  • Название: Получение оценки разреженной ковариационной матрицы для нелинейных моделей (нейросетей).
  • Задача: Один из возможных подходов к решению задачи выбора регрессионной модели из заданного параметрического семейства регрессионных моделей заключается во введении предположений о распределении параметров модели [1]. В этом случае предполагается, что функция регрессии задана оценкой вектора параметров, который считается нормально распределённой многомерной случайной величиной. Предлагается регулировать структуру нейронной сети, используя ковариационную матрицу ее модели. Требуется оценить ковариационную матрицу параметров в отсутствии предположений о независимости параметров модели.
  • Данные: Синтетические данные и тесты.
  • Литература:
  • Базовой алгоритм: Оценка диагональной матрицы, см. папку MLAlgorithms/HyperOptimization.
  • Решение: Предлагается рассмотреть разреженные матрицы, отвечающие предположению о том, что большая часть узлов нейронных сетей не связана друг с другом.
  • Новизна: Предложен быстрый алгоритм получения оценок ковариационной матрицы общего вида для нелинейных моделей, исследованы свойства разреженных матриц.
  • Консультант: Александр Адуенко.

Задача 5

  • Название: Рекомендация статей коллективного блога на основе тематической модели
  • Задача: Дана коллекция статей коллективного блога Хабрахабр.ру. Требуется построить тематическую модель коллективного блога Хабрахабр.ру, учитывающую социальные связи, рубрики, ссылки. Проверить гипотезу о том что учет социальных связей, комментариев и рубрик улучшает качество рекомендательного ранжирования статей.
  • Данные: Корпус из порядка 130 тыс. статей с комментариями и разметкой (теги, хабы), информация о пользователях (избранные страницы, сообщества).
  • Литература:
    1. Vorontsov K. V., Potapenko A. A. Additive Regularization of Topic Models // Machine Learning. Special Issue “Data Analysis and Intelligent Optimization with Applications”. 2014. Русский перевод
    2. Chong Wang, David M. Blei Topic Modeling for Recommending Scientific Articles
  • Базовой алгоритм: Обычная тематическая модель PLSA или LDA.
  • Решение: Тематическая модель на основе подхода ARTM с комбинацией регуляризаторов для учета специфики коллективного блога.
  • Новизна: Комбинирование большого числа регуляризаторов в тематических моделях ранее не использовалось для построения рекомендательных моделей. Существующие тематические модели для рекомендации, учитывающие социальные связи, основанные на вероятностном выводе (модификации LDA) приводят к вычислительно трудным задачам, что ограничивает их применимость.
  • Консультант: Петр Ромов, Константин Воронцов

Задача 6

  • Название: Simplification of the IR models structure
  • Задача: To achieve the acceptable quality of the information retrieval models, modern search engines use models of very complex structure. In current research we propose to simplify the model structure and make it interpretable without decreasing the model accuracy. To do this, we follow the idea from (Goswami et al., 2014) of constructing the set of nonlinear IR functions of simple structure and admissible accuracy. However, each of this functions is expected to have lower accuracy while comparing with the best IR model of complex structure. Thus, we propose to approximate this complex model with the linear combination of simple nonlinear functions and expect to obtain the comparable quality of solution.
  • Данные: TREC collections.
  • Литература
    • P. Goswami et Al. Exploring the Space of IR Functions // Advances in Information Retrieval. Lecture Notes in Computer Science. 8416:372-384, 2014.
    • Problem statement
  • Базовой алгоритм: Gradient boosting machine for constructing a model of high complexity. Exaustive search of superpositions from a set of elementary functions for approximation and simplification.
  • Решение: The optimal functions for the linear combination can be found by the greedy algorithm.
  • Новизна: A new ranking function of simple structure competitive with traditional ones.
  • Консультант: Mikhail Kuznetsov.

Задача 7

  • Название: Выявление тематической структуры сервиса Ответы@mail.ru.
  • Задача: Построить проблемно-ориентированную тематическую модель коллекции вопросов и ответов.
  • Данные:
    1. Большая коллекция вопросов и ответов (около 11 млн. вопросов, в среднем 3-5 ответов на вопрос).
    2. Привязки к авторам и времени.
    3. Привязки к двухуровневой иерархии категорий (27 верхний уровень, 189 нижний).
  • Литература:
    1. Rubin T. N., Chambers A., Smyth P., Steyvers M. Statistical topic models for multi-label document classification // Machine Learning. 2012, Vol.88, no.1-2., Pp.157–208.
    2. Vorontsov K. V., Potapenko A. A. Additive Regularization of Topic Models // Machine Learning. Special Issue “Data Analysis and Intelligent Optimization with Applications”. 2014. Русский перевод
  • Базовой алгоритм: Обычная тематическая модель PLSA или LDA без проблемно-ориентированных регуляризаторов.
  • Решение: Комбинация регуляризаторов разреживания, сглаживания, декоррелирования, классификации по авторам и категориям, сглаживания по времени, label regularization, и др. для мультимодальной динамической тематической модели в библиотеке BigARTM. Подбор стратегий инициализации и регуляризации.
  • Новизна: Тематические модели с комбинированием большого числа регуляризаторов ранее не использовались. Тематическая модель сервиса Ответы@mail.ru позволит анализировать динамику различных тем в социальной среде.
  • Консультант: Анна Потапенко, Константин Воронцов, Павел Браславский.

Задача 8

  • Название: Устойчивость и другие свойства метрики AMS.
  • Задача: необходимо построить методы машинного обучения, при которых получается сравнимое качество AMS, устойчивое к выбору оптимального порога (на тестовом датасете данный порог близок к оптимальному)

Задача 9

  • Название: Разделение смеси распадов с известным распределением массы.
  • Задача: Обучение без учителя. Есть набор событий (реальные данные), описываемый N признаками, в котором содержатся представители 2 классов (сигнал и фон). Распределение этого набора данных по массе показано на рисунке. Метки событий неизвестны. Формы распределений для сигнала и фона по массе известны (гауссиан и экспонента). Изучить изменение распределений событий, отобранных классификатором как "сигнал" при различных катах на классификатор.
  • Данные: Данные описываются набором физических признаков (момент, импульс, время жизни, качество трэка), метки не даны, но заданы формы распределений. Алгоритм проверяется на Монте-Карло симуляции (в которой метки известны).
  • Литература: Splot technique
  • Базовый алгоритм:
    1. Для случая, когда остальные признаки не имеют корреляции с массой, работает следующий простой прием: фитируем распределения по массе, получаем вероятности каждого событи быть сигналом или шумом, далее запускаем классификатор (причем каждое событие добавляется с разными весами и в качестве сигнала, и в качестве шума)
    2. Ещё более простой вариант - если пик виден явно, можно обучить классификатор на данных из sideband (2000-4000) с меткой шума и данных в пике с меткой сигнала (450-500). Проверить качество на тестовом множестве:
  • Решение: Исследование разделение смеси при нескоррелированном признаковом описании с массой и при скоррелированном:
    1. baseline - RandomForest, в котором каждое событие входит в обучающую выборку два раза: один раз как сигнал, один раз как шум. Веса равны соответственно вероятностям, что событие сигнал или шум.
    2. sPlot позволяет реконструировать распределение остальных фичей - возможно, наивный байес или что-то похитрее
    3. модификации бустинга
  • Новизна: На данный момент используется splot, но масса обычно всегда имеет корреляцию, так что построение методов разделения смесей, учитывающих корреляцию, нет.
  • Консультант: Татьяна Лихоманенко, Андрей Устюжанин

Задача 10

  • Название: Автоматизация построения cut-based классификаторов для отбора "интересных" событий в физике частиц.
  • Задача: Есть набор признаков, часто в физических приложениях требуется выкинуть 90% шума и почти не потерять сигнал. Для этого физики долго подбирают пороги на признаки распада, но можно заставить машину делать то же самое. Единственное преимущество таких классификаторов над 'традиционными': очень высокая скорость и человекопонятность (что люди из прикладных областей очень ценят). Также можно это преобразовать в запрос к некоторой базе данных (что при наличии индексов будет работать сильно быстрее, чем просто поэлементное применение).
  • Данные: Данные без преселектов конкретных распадов (преселекты известны из статей, с ними необходимо сравнивать качество построенной модели)
  • Литература:
    1. TMVA,
    2. A* algorithm
  • Базовый алгоритм: Пакет TMVA содержит метод Rectangular cut optimization, который решает именно данную задачу, но использует при этом только простые правила: (10 < x1 < 50) & (20 < x2 < 40)
  • Решение:
    1. умное использование TMVA Rectangular cut optimization (построить в виде запросов к базе данных)
    2. A-star как метод выбора
    3. Методы стохастической оптимизации
    4. перебор фичей (+-*/, что-то такое, если удастся использовать размерность переменных - было бы совсем здорово)
  • Новизна: На данный момент в каждом распаде физики сами подбирают каты на фичи вручную, необходимо получить алгоритм, который можно встроить в систему анализа, как триггеры
  • Консультант: Алексей Рогожников, Андрей Устюжанин

Задача 11

  • Название: Прунинг oblivious decision trees.
  • Задача: Трудоемкая задача при обучении ODT является выбор признаков и порогов, используемых в каждом дереве. Когда это уже сделано на сервере (например, матрикснетом), на локальном компьютере деревья можно модифицировать путем изменения значений в листах. Требуется научиться эффективно сжимать модель - из 5000 деревьев оставлять 100, получая сравнимое качество классификации.
    1. Это ускорит применение и сделает возможным применять в частности матрикснет крайне быстро
    2. Это позволит изменять функцию потерь для уже натренированной модели (вопрос, правда, насколько это будет оправдано)
    3. Это сделает возможным 'переобучать' модель - то есть обучили на одних данных, потом оказалось, что учиться надо на сильно бОльшей выборке (или наоборот - только на каком-то подмножестве). Операция переобучения требует меньше ресурсов.
    4. Построение сложных моделей с дальнейшим сжатием позволит использовать их в триггерных системах
  • Данные: Обученные деревья. Тестировать предлагается на наборе данных higgs [3]
  • Литература:
    1. Friedman, Treeboost
    2. sklearn использует шаг по методу Ньютона для значений в листьях
    3. YetiRank
  • Базовый алгоритм: Изменение значений в листьях у деревьев - возможно, даже стоит делать не одну итерацию метода второго порядка, а больше.
  • Решение:
    1. жадный итеративный отбор деревьев (жадная минимизация loss-функции).
    2. Предложить возможные алгоритмы модификации листьев (сравнение качества работы)
    3. Возможно, ввести регуляризацию, чтобы не переобучиться.
    4. Посмотреть поведение алгоритма при изменении loss-функции для уже натренированной модели
  • Новизна: Быстрый алгоритм получения эффективной (с вычислительной точки зрения) модели классификации.
  • Консультант: Алексей Рогожников, Андрей Устюжанин

Задача 12

  • Название: Определение области затенения радужки классификатором локальных текстурных признаков
  • Задача: Дано изображение радужки глаза человека и окружности, аппроксимирующие границы зрачок-радужка и радужка-склера. Кольцо, заключённое между этими окружностями, - радужка. Область радужки часто перекрыта (затенена) различными объектами: блики, веки, ресницы, тени от век и ресниц. Известен некоторый сегмент S кольца, не содержащий затенений. Требуется выделить точки затенения в области радужки. Качество решения определяется как минимум суммы относительных ошибок первого и второго рода по тестовому набору изображений, для которых известны области затенения.
  • Данные:
    1. База изображений радужки CASIA-Iris-Thousand http://biometrics.idealtest.org/dbDetailForUser.do?id=4
    2. База изображений радужки MMU
    3. База изображений радужки IIT Delhi http://www4.comp.polyu.edu.hk/~csajaykr/IITD/Database_Iris.htm
    4. NIST ICE DB и др.
  • Литература:
    1. Y. H. Li, M. Savvides. A pixel-wise, learning-based approach for occlusion estimation of iris images in polar domain. In ICASSP, pages 1357–1360. IEEE, 2009.
    2. Guangzhu Xu, Zaifeng Zhang, and Yide Ma. Improving the performance of iris recogniton system using eyelids and eyelashes detection and iris image enhancement. In Cognitive Informatics, 2006. ICCI 2006. 5th IEEE International Conference on, volume 2, pages 871–876, July 2006.
    3. Zhaofeng He, Tieniu Tan, Zhenan Sun, and Xianchao Qiu. Robust eyelid, eyelash and shadow localization for iris recognition. In ICIP, pages 265–268. IEEE, 2008.
    4. Zhaofeng He, Tieniu Tan, Zhenan Sun, and Xianchao Qiu. Toward accurate and fast iris segmentation for iris biometrics. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(9):1670–1684, 2009.
    5. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М., Техносфера, 2005 – 1072 с.
    6. Шапиро Л, Стокман Дж. Компьютерное зрение. М., БИНОМ. Лаборатория знаний, 2006 – 752 с.
    7. Форсайт Д, Понс Ж. Компьютерное зрение. Современный подход. М., Издательский дом «Вильямс», 2004 – 928 с.
  • Базовой алгоритм: См. [1]. Каждая точка области радужки относится к одному из двух классов: радужка/затенение, с использованием классификатора, основанного на смесях гауссианов. Вектор признаков точки пятимерный, состоит из её координат, яркости, средней яркости окрестности и дисперсии яркости в окрестности. Для обучения классификатора используются изображения, размеченные вручную.
  • Решение: В [1] используется ручная разметка некоторых изображений для тренировки классификатора. Это является недостатком. С использованием сегмента S, не содержащего затенений, можно построить полностью автоматический метод. Таким образом содержание работы — реализация метода [1], но с использованием сегмента S (содержащего лишь часть истинной радужки) вместо разметки, где выделена вся незатенённая радужка. Также рекомендуется рассмотреть различные характеристики окрестности точки в дополнение к пяти признакам, используемым в [1].
  • Новизна: Метод выделения всей незатенённой области радужки на основании анализа её малой части, применимый для широкого класса изображений.
  • Консультант: Матвеев И.А.

Задача 13

  • Название: Повышение качества прогнозирования спроса с помощью анализа взаимозаменяемости товаров
  • Задача:

Дано:

    1. Временные ряды продаж нескольких группам товаров в одном гипермаркете. Также для каждого товара известны периоды дефицита, периоды воздействия на спрос календарных праздников и периоды проведения. маркетинговых акций. Также известен товарный классификатор: дерево групп товаров, где сами товары являются листьями.
    2. Алгоритм прогнозирования, который используется для построения прогнозов спроса по этим товарам: самоадаптивное экспоненциальное сглаживание (модель Тригга-Лича, см. [1])
    3. Функция потерь, по которой измеряется качество прогнозов: MAPE.
    4. Требования к построению прогнозов: прогнозы требуется строить понедельно (в начале текущей недели требуется построить прогноз суммарного спроса на следующую неделю).


Гипотеза: в продажах наблюдается взаимозаменямость товаров, проявляющаяся в виде:

    1. Эффекта «каннибализации» - при появлении на рынке нового товара продажи аналогичных товаров (по группе, по цене) начинают падать.
    2. Снижения продаж аналогичных товаров при проведении промо-акции по данному товару;
    3. Повышения продаж аналогичных товаров при появлении дефицита по данному товару;


Задача заключается в повышении качества прогнозирования в рамках поставленной задачи путём рассмотрения сезонности для групп товаров. Результат можно считать достигнутым, если показано статистически значимое повышение качества при построении серии прогнозов (не менее 20) по каждому временному ряду скользящим контролем.

  • Данные:
    1. Данные о продажах нескольких товарных групп в гипермаркете крупной торговой сети: https://drive.google.com/file/d/0B5YjPespcL83X3pHaE1aRzBUaDg/view?usp=sharing
  • Литература:
    1. Лукашин Ю. П. Адаптивные методы краткосрочного прогнозирования временных рядов. — М.: Финансы и статистика, 2003.
    2. http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C_%D0%A2%D1%80%D0%B8%D0%B3%D0%B3%D0%B0-%D0%9B%D0%B8%D1%87%D0%B0
    3. P. Syrovátka; L. Grega. Analysis of methodological approaches to evaluation of complementary and substitution relationship in consumer demand for food. Agricultural economics.- ISSN 0139-570X, ZDB-ID 20432719. - Vol. 48.2002, 10, p. 456-462
    4. Kumar M., Error-based Clustering and Its Application to Sales Forecasting in Retail Merchandising. PhD Thesis. http://books.google.ru/books/about/Error_based_Clustering_and_Its_Applicati.html?id=6252NwAACAAJ&redir_esc=y
  • Базовой алгоритм: См. модель Тригга-Лича в [1] и [2]. Допускается использование других алгоритмов в качестве базового, при наличии аргументации.
  • Решение: В литературе очень мало описан учёт взаимозаменямости товаров при прогнозировании спроса. Общие эконометрические подходы к учёту взаимозаменяемости/дополняемости базируются на корреляционном анализе [3], который, возможно, подходит для макроэкономических исследований, но оказывается малоэффективен при прогнозировании спроса на уровне детализации отдельного товара в отдельном магазине. Предлагается рассмотреть альтернативный подход, при котором проявление эффектов взаимозаменяемости анализируется только при краткосрочных, но сильных воздействиях на спрос: а именно, в периоды дефицита и проведения маркетинговых акций. В рамках исследования предполагается три шага:
    1. Определение групп взаимозаменяемых товаров. В начале работы предлагается взять в качестве таковых группу нижнего уровня классификатора. В дальнейшем возможно уточнение на основе информации по ценовой категории, а также методами кластеризации (см. [4]).
    2. Оценка эффекта взаимозаменяемости, в периоды дефицита и проведения маркетинговых акций. Для этого предлагается сравнивать фактический спрос на товар с прогнозируемым в периоды проведения акций либо наличия дефицита по аналогам, оценивать "эффект взаимозаменяемости" в процентах и далее агрегировать показатели по группе аналогов.
    3. Использование полученных оценок для повышения качества прогнозирования. Проверка обобщающей способности найденных эффектов при прогнозировании на будущие периоды. Допускается предположение, что на будущее известны периоды дефицита
  • Новизна: Оригинальный алгоритм учёта эффекта взаимозаменяемости товаров при прогнозировании.
  • Консультант: Каневский Д.Ю.


Задача 14

  • Название: Построение интегрального индикатора по многоиндексной матрице оценок нескольких экспертов
  • Задача: Дана многомерная матрица экспертных оценок (эксперт-критерий-объект), выполненная в ранговых шкалах. В матрице допускается существенное количество пропущенных значений. Эксперты упорядочены по уровню значимости. Каждый эксперт также может указать его мнение о важности каждого критерия. Требуется построить интегральный индикатор по данной матрице. Алгоритм должен быть устойчив к большому количеству пропущенных данных. Добавление: требуется решить задачу выбора признаков, признаки принимают значения из разномощных шкал.
  • Данные: таблица с оценками экспертов компаний, предлагающих платежные сервисы
  • Литература:
  • Базовой алгоритм: Парето-оптимальный фронт (см. последний пункт литературы)
  • Решение: Предлагается сравнивать медиану кемени (требуется модифицировать для поставленной задачи) с базовым алгоритмом
  • Новизна: Задача предполагает сильную вариативность исходных данных для алгоритма и является обобщением многих классических задач Preference Learning и Decision Making.
  • Консультант: Олег Бахтеев.

Задача 15

  • Название: Поиск внешней и внутренней границ радужки на изображении глаза методом парных градиентов
  • Задача: Дано изображение радужки глаза человека. Также может быть дано приблизительное положение центра глаза — некоторой точки внутри зрачка, желательно рассмотреть оба случая: с заданным центром и без него. Требуется найти окружность, аппроксимирующую зрачок (её центр и радиус) и окружность, аппроксимирующую внешнюю границу радужки.
  • Данные:
    1. База изображений радужки CASIA-Iris-Thousand http://biometrics.idealtest.org/dbDetailForUser.do?id=4
    2. База изображений радужки MMU
    3. База изображений радужки IIT Delhi http://www4.comp.polyu.edu.hk/~csajaykr/IITD/Database_Iris.htm
    4. NIST ICE DB и др.
  • Литература:
    1. Pan L., Chu W.S., Saragih J.M., de la Torre F. Fast and Robust Circular Object Detection with Probabilistic Pairwise Voting (PPV) // Signal Processing Letters. 2011. V.18. N.11. P.639–642. http://www.humansensing.cs.cmu.edu/projects/ppv/ppv.pdf
    2. https://ru.wikipedia.org/wiki/Преобразование_Хафа
    3. W. Gander, G. H. Golub, and R. Strebel, “Least-squares fitting of circles and ellipses,” BIT Numerical Mathematics, vol. 34, no. 4, pp. 558–578, 1994. http://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf
    4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М., Техносфера, 2005 – 1072 с.
    5. Шапиро Л, Стокман Дж. Компьютерное зрение. М., БИНОМ. Лаборатория знаний, 2006 – 752 с.
    6. Форсайт Д, Понс Ж. Компьютерное зрение. Современный подход. М., Издательский дом «Вильямс», 2004 – 928 с.
  • Базовой алгоритм: См. [1]. Представляет собой разновидность преобразования Хафа [2]. В каждой точке изображения рассчитывается градиент яркости. Производится поиск пар точек удовлетворяющих условиям: (1) большой модуль градиента; (2) вектора градиента имеют противоположное направление; (3) вектора градиента лежат приблизительно на прямой, соединяющей эти точки. Центры отрезков, соединяющих такие точки — это центры гипотетических окружностей. На изображении-аккумуляторе отмечаются центры для всех найденных пар точек. Наибольшая плотность соответствует наиболее выразительной окружности на изображении.
  • Решение: Предлагается реализовать метод, близкий к [1], с адаптациями для изображений глаза (например, возможностью выделить два округлых концентрических контура — внутреннюю и внешнюю границы радужки; также следует отрабатывать случай частичного затенения искомой окружности). Решением задачи для каждого из изображений является окружность (координаты центра и радиус), соответствующая зрачку (или две окружности — зрачок и радужка). Для каждого изображения известны “истинные” окружности такого рода — размеченные человеком-экспертом границы. Качество решения определяется гистограммой величины ошибки определения. Численный критерий качества решения — доля изображений, на которых ошибка превышает 10% истинного радиуса зрачка/радужки. Ошибка рассчитывается как сумма абсолютных значений отклонений вычисленных абсциссы и ординаты центра и радиуса зрачка от истинных значений.
  • Новизна: Поиск внешней и внутренней границ радужки на изображении глаза методом парных градиентов.
  • Консультант: Матвеев И.А.

Задача 16

  • Название: Поиск внешней и внутренней границ радужки на изображении глаза методом триангуляции
  • Задача: Дано изображение радужки глаза человека. Также может быть дано приблизительное положение центра глаза — некоторой точки внутри зрачка, желательно рассмотреть оба случая: с заданным центром и без него. Требуется найти окружность, аппроксимирующую зрачок (её центр и радиус) и, факультативно, окружность, аппроксимирующую внешнюю границу радужки.
  • Данные:
    1. База изображений радужки CASIA-Iris-Thousand http://biometrics.idealtest.org/dbDetailForUser.do?id=4
    2. База изображений радужки MMU
    3. База изображений радужки IIT Delhi http://www4.comp.polyu.edu.hk/~csajaykr/IITD/Database_Iris.htm
    4. NIST ICE DB и др.
  • Литература:
    1. Erik Cuevas, Noé Ortega-Sánchez, Daniel Zaldivar and Marco Pérez-Cisneros. Journal of Intelligent & Robotic Systems. Vol. 66, No. 3, pp. 359-376, 2012. http://arxiv.org/ftp/arxiv/papers/1405/1405.7242.pdf
    2. https://ru.wikipedia.org/wiki/Преобразование_Хафа
    3. W. Gander, G. H. Golub, and R. Strebel, “Least-squares fitting of circles and ellipses,” BIT Numerical Mathematics, vol. 34, no. 4, pp. 558–578, 1994. http://www.emis.de/journals/BBMS/Bulletin/sup962/gander.pdf
    4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М., Техносфера, 2005 – 1072 с.
    5. Шапиро Л, Стокман Дж. Компьютерное зрение. М., БИНОМ. Лаборатория знаний, 2006 – 752 с.
    6. Форсайт Д, Понс Ж. Компьютерное зрение. Современный подход. М., Издательский дом «Вильямс», 2004 – 928 с.
  • Базовой алгоритм: См. [1]. Представляет собой разновидность преобразования Хафа [2]. В каждой точке изображения рассчитывается градиент яркости. Производится поиск троек точек удовлетворяющих условиям: (1) большой модуль градиента; (2) вектора градиента направлены в сторону, противоположную центру тройки. Центры окружностей, проведённых через эти точки — это центры гипотетических окружностей зрачка (радужки). На изображении-аккумуляторе отмечаются центры описанных окружностей для всех найденных пар точек. Наибольшая плотность соответствует наиболее выразительной окружности на изображении.
  • Решение: Предлагается реализовать метод, близкий к [1], с адаптациями для изображений глаза (например, возможностью выделить два округлых концентрических контура — внутреннюю и внешнюю границы радужки; также следует отрабатывать случай частичного затенения искомой окружности). Решением задачи для каждого из изображений является окружность (координаты центра и радиус), соответствующая зрачку (или две окружности — зрачок и радужка). Для каждого изображения известны “истинные” окружности такого рода — размеченные человеком-экспертом границы. Качество решения определяется гистограммой величины ошибки определения. Численный критерий качества решения — доля изображений, на которых ошибка превышает 10% истинного радиуса зрачка/радужки. Ошибка рассчитывается как сумма абсолютных значений отклонений вычисленных абсциссы и ординаты центра и радиуса зрачка от истинных значений.
  • Новизна: Поиск внешней и внутренней границ радужки на изображении глаза методом триангуляции.
  • Консультант: Матвеев И.А.

Задача 17

  • Название: Определение области затенения радужки кластеризацией, основанной на локальных текстурных признаках
  • Задача: Дано изображение радужки глаза человека и окружности, аппроксимирующие границы зрачок-радужка и радужка-склера. Кольцо, заключённое между этими окружностями, - радужка. Область радужки часто перекрыта (затенена) различными объектами: блики, веки, ресницы, тени от век и ресниц. Требуется выделить точки затенения в области радужки.
  • Данные:
    1. База изображений радужки CASIA-Iris-Thousand http://biometrics.idealtest.org/dbDetailForUser.do?id=4
    2. База изображений радужки MMU
    3. База изображений радужки IIT Delhi http://www4.comp.polyu.edu.hk/~csajaykr/IITD/Database_Iris.htm
    4. NIST ICE DB и др.
  • Литература:
    1. H. Proenca and L.A. Alexandre. Iris segmentation methodology for non-cooperative recognition. Vision, Image and Signal Processing, IEE Proceedings, 153(2):199–205, April 2006. http://www.di.ubi.pt/~hugomcp/doc/ProencaAlexandreIrisSegmentationIEE.pdf
    2. Guangzhu Xu, Zaifeng Zhang, and Yide Ma. Improving the performance of iris recogniton system using eyelids and eyelashes detection and iris image enhancement. In Cognitive Informatics, 2006. ICCI 2006. 5th IEEE International Conference on, volume 2, pages 871–876, July 2006.
    3. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М., Техносфера, 2005 – 1072 с.
    4. Шапиро Л, Стокман Дж. Компьютерное зрение. М., БИНОМ. Лаборатория знаний, 2006 – 752 с.
    5. Форсайт Д, Понс Ж. Компьютерное зрение. Современный подход. М., Издательский дом «Вильямс», 2004 – 928 с.
  • Базовой алгоритм: См. [1]. В каждом пикселе области радужки рассчитывается набор локальных текстурных признаков, которые (возможно, вместе с координатами) составляют вектор признаков. На полученных объектах выполняется процедура кластеризации (например, методом k-средних или иерархическая аггломеративная). Класс, содержащий максимальное число элементов считается классом пикселей радужки, остальные — различного рода помехами.
  • Решение: Качество решения определяется как минимум суммы относительных ошибок первого и второго рода по тестовому набору изображений, для которых известны области затенения.
  • Новизна: Исследование возможности сегментации затенений радужки без априорно заданной модели её текстуры.
  • Консультант: Матвеев И.А.

Задача 18

  • Название: Улучшение обученного OBDT
  • Задача: 0. Научиться складывать пару ODT (строить суперпозицию ODT). 1. Коррекция порогов в уже построенном дереве. Можно минимизировать gini-подобную метрику. 2. Строительство глубоких решающих деревьев.

Построить глубокое ODT трудно, ибо распределение событий в листьях будет неравномерное - выбирать пороги становится тяжело. Искусственный способ получения глубоких деревьев - складывать два-три неглубоких дерева, потом прунить получившееся дерево, выкидывая признаки. При правильной готовке это ускорит применение формулы (что иногда у нас критично), но в первую очередь хотелось бы получить прирост в качестве. Вопрос выбора значений в листьях глубокого дерева особенно интересный, ибо часто в листе мало событий. Однако структура ODT позволяет решать подобные трудности.

См. также

Личные инструменты