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

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

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


Результаты предыдущих курсов

Описание курса

Этот семестр посвящен постановке вычислительных экспериментов. Результатом эксперимента является анализ свойств математической модели, получаемой в результате решения поставленной задачи машинного обучения анализа данных. Построенная модель подготавливается к эксплуатации и представляется на языке, наиболее подходящем для эксплуатации. Cоздаются эксплуатационные интерфейсы. Результатами работы являются:

  1. эксплуатационная документация в формате systemdoics,
  2. код вычислительного эксперимента и тесты,
  3. версия кода для эксплуатаци[1],
  4. доклады и презентация.

Анализ свойств модели (алгоритма распознания, классификации, прогнозирования) включает следующие основные элементы:

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

Результат выполнения работ:

  • модуль для построения модели на языке Матлаб,
  • юнит-тесты модуля,
  • вычислительный эксперимент, системные тесты: анализ свойств модели (то же),
  • модуль эксплуатации модели, код на языке эксплуатации (С, ++, #, Python, Java, CUDA, Ruby, VHDL, ...),
  • юнит-тесты эксплуатируемой части,
  • конструкторская документация в формате Systemdocs, в частности:
    • мотивация проекта,
    • формальная постановка задачи,
    • IDEF модуля построения модели,
    • IDEF модуля эксплуатации модели (если требуется),
    • описание интерфейсов,
    • описание системных тестов и их результатов,
    • описание юнит-тестов,
    • анализ производительности.

Эксплуатация модели предполагается в одном из вариантов, доступных для широкого круга пользователей:

  • модуль на Google Play,
  • модуль на сервере mvr.jmlda.org.

Научная статья: написание научной статьи приветствуется, но не входит в расписание проекта. Это связано с повышением требования к качеству статей студентов четвертого курса. Так как на третьем курсе мы подали ряд статей в журналы ВАК, то имеет смысл для некоторых работ обсудить формат статьи в журнал WebOfKnowledge.

Требования к слушателям: слушатели знают базовый курс лекций К.В. Воронцова и программируют на Матлабе.

Технология работы: время работы человека гораздо ценнее времени работы компьютера. Поэтому мы работаем следующим образом: 1) ставим задачу в формальном наиболее детализированном варианте, формально описываем аалгоритм, 2) делаем вычислительные эксперименты на Матлабе, 3) полученные модели переписываем на том языке, на котором модели будут эксплуатироваться. Это может быть VHDL, в котором результатом компиляции является микросхема-процессор специального назначения увеличивающий скорость вычисления в миллионы раз, CUDA для видеопроцессоров, Java для телефонов, PL-SQL для систем коллективного пользования, Ruby on Rails для интернета.

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

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

Результаты

Автор Тема научной работы Ссылка Консультант Рецензент Доклады Буквы Сумма Оценка
Газизуллина Римма Вопросно-ответная система [2], pdf Кудинов Михаил Шинкевич Михаил BM GLAI>000
Гринчук Алексей Разработка метрик качества тематических моделей для библиотеки BigARTM [3], pdf Апишев Мурат Попова Мария B GLAI>>00
Гущин Александр Задача двухклассовой классификации изображений [4], pdf Лексин Василий GLAI-C+000
Костюк Анна Определение запрещенного товара на картинке Лексин Василий G>>>>000
Ефимова Ирина Формирование однородных обучающих выборок в информационном анализе ЭКГ-сигналов [5], pdf Целых Влада Газизуллина Римма BM GLAI+CU>0
Жуков Андрей Тематическое моделирование новостных потоков [6], pdf Дойков Никита BM GL+AICUTDP
Игнатов Андрей Полигон алгоритмов классификации для информационного анализа ЭКГ-сигналов [7], pdf Целых Влада BM GLA++ICU>0
Карасиков Михаил Прогнозирование третичных структур белков: оптимизация [8] С.В. Грудинин,

Ю.В. Максимов

B GL+>000>0
Кулунчаков Андрей Ранжирование документов с помощью структурно-простых моделей [9], pdf Мотренко Анастасия GLAIC+>>D
Липатова Анна Инструмент для эмпирического исследования переобучения линейных классификаторов и его приложение в задачах медицинской диагностики. [10], [11] Ишкина Шаура B GLAI0000
Макарова Анастасия Диагностика заболеваний на основе зависимости между знаками приращений амлитуд и интервалов в дискретизированной ЭКГ. [12], pdf К.В.Воронцов B 00000000
Плавин Александр Визуализация и частичная разметка тематической структуры текстовых коллекций [13], pdf Потапенко Анна G+LAIC++U>>
Попова Мария Последовательный выбор моделей распознавания физической активности человека [14], pdf В. В. Стрижов Швец Михаил BM GLA>IC000
Чинаев Николай Уточнение радужки в кольце [15] И. А. Матвеев B GLA0>0000
Швец Михаил Монотонные классификаторы с отбором признаков для задач медицинской диагностики [16], pdf Зухба Анастасия Гринчук Алексей BM GLAICUTDP
Шинкевич Михаил Офф-лайн оценка рекомендательной системы фильмов, основанной на трех популярных подходах. [17], pdf Петр Ромов Ефимова Ирина BM G+LAIC>>D
Абе Калан (Sk) 00000000
Иванов Николай (Sk) >0000000
Кищенко Ярослав (Sk) 00000000
Логинс Алвис (Sk) TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning. [18], [19] Мотренко Анастасия BM GLAIС>>D-
Мунхоева Марина (Sk) Learning influence probabilities in social networks (или 40) B GL0I-0000
Усман Бен (Sk) Уточнение прогноза железнодорожных грузоперевозок по биржевым данным Стенина Мария B GLA-00000
Червинский Федор (Sk) EEG Classification for Brain-Computer Interfaces Васильев Анатолий B 00000000
Юрченко Виктор (Sk) 00000000
Гурьев Георгий (Sk) 00000000
Широкова Елена(Sk) Жанровая классификация текстов Потапенко Анна B G>000000
Сухарева Анжелика Классификация научных текстов по отраслям знаний Царьков Сергей B GLAI>>00

Расписание

Дата Что сделано Результат для обсуждения Буква
Сентябрь 3 Первая лекция. Представление нового курса, мотивация, организация работ. Две вводные лекции для новых студентов (по возможности).
10 Выбрана задача, рецензент. Доклад на 45 секунд о своем проекте. Запись в ML. Доклад B Go
17 Собрана литература. Собрана и описана выборка, сделано описание данных в текстовом виде или в IDEF0. Доклад 2й подгруппы. Список литературы. Описание данных. Literature
24 Поставлена задача. Написаны математическая постановка в формате TeX и описание базового алгоритма. постановка задачи и алгоритм. Algorithm
Октябрь 1 Разработана архитектура и интерфейс ядра системы. Описание архитектуры в IDEF0. Idef
15 Детализирован интерфейс, написан код. Код для реальных данных. Code
22 Написаны юнит-тесты и модуль, их запускающий. Подготовлен доклад с обоснованием интерфейсов и IDEF-описания. Юнит-тесты, доклад Unit
29 Собраны и подготовлены данные, необходимые для тестирования. Доработана схема IDEF0 в части подготовки данных. Написаны и запущены системные тесты. Тесты, данные, доработанная схема IDEF0. Tests, Data
Ноябрь 5 Код оптимизирован. Отчет профайлера до и после. Profiler
12 Сделан визуальный отчет. По результатам доработки кода написана рецензия на работу. Завершенный тех.отчет, рецензия. Report, Review
19 Сделан пользовательский интерфейс и неcколько примеров использования системы. Код на сайте. Web
26 Подготовлен доклад, приведены в порядок документация и код. Обсуждение результатов, доклад F первой группы. Slides
Декабрь 3 - Доклад F второй группы.

Доклады обозначаются буквами B, M, F.

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

10 сентября

  • Выбрать задачу и подготовить доклад о выбранной задаче на 45 секунд (первая часть группы). Содержание доклада включает:
  1. Существо и цели проекта.
  2. Важность и применимость задачи.
  3. Описание предполагаемых методов решения.
  • Создать описание проекта, заполнить разделы «Мотивация» (1.1.2) и «Литература» (1.1.3) в SystemDocs

Дополнительно для студентов Сколтеха:

  1. Получить доступ к проекту MLalgorithms на SourceForge через старосту группы, прочитать статью, загрузить MLalgorithms.
  2. Зарегистрироваться на сайте machinelearning.ru, послать логин старосте.
  3. В папке Group174 создать папку Surname2014PrijectName (См. Численные методы обучения по прецедентам (практика, В.В. Стрижов), раздел "Работа с репозиторием".)


17 сентября

  • Получить четкую постановку задачи, зафиксировать базовый алгоритм. При необходимости, расширить список литературы.
  • Собрать выборку и описать форматы и структуры данных в разделе 1.4 SystemDocs: состав выборки, основные статистики, гипотезу порождение данных. Создать описание процедуры порождения выборки в формате IDEF0.
    • Скачать и установить Ramus, разобраться с нотацией IDEF0
  • Заполнить раздел Выполнимость задачи/Feasibility. Уточнить границы применимости предлагаемых методов, прописать условия отказа от классификации.
  • Подготовить доклад о выбранной задаче на 45 секунд (вторая часть группы).


24 сентября

Создать отдельный файл LaTeX c постановкой задачи и базовым описанием алгоритма, включающими

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


1 октября

  • При необходимости, доработать постановку задачи. Сделать окончательное описание базового алгоритма.
  • Создать двухуровневую схему в IDEF0 (разделы 1.2.2 и 1.2.3), желательно, разделяя стадии обучения и использования модели.
  • Описать интерфейсы (раздел 2 SystemDocs).


15 октября

Написать код.


22 октября

  • Подготовить доклад, в котором обосновываются предлагаемые интерфейсы и IDEF-описания системы.
  • Написать юнит-тесты для каждого модуля.

29 октября

  • Доделать IDEF0: детализировать блок обработки пользовательских данных, сделать второй уровень детализации. Второй уровень посвящен проверке адекватности пользовательских данных на:
  1. наличие вирусов в теле загружаемых данных (воздерживаться от выполнения команд, находящихся в теле файлов, например, mpeg),
  2. тип загружаемого файла,
  3. величину загружаемого файла,
  4. допустимость времени расчетов, сложности алгоритма распознавания (не более 15 сек, в противном случае обсуждается вариант фонового выполнения алгоритма или отправка результатов по почте),
  5. допустимость объема памяти (желательно не более 200 МБ),
  6. адекватность структуры входных данных (алгоритм не должен возвращать неадекватные результаты получив неадекватные данные, желательно сообщать о таком случае).
  • В папке data собрать реальные данные, предназначенные для демонстрации работы алгоритма (и, возможно, для тестирования, если объем данных невелик). При большом объеме данных в эту папку записываются файлы со ссылками в интернет, где можно скачать большую выборку. Вариант: ссылка находится в загрузчике данных. Подготовить описание данных в systemdocs.
  • Подготовить модель загрузки и проверки пользовательских данных. Модуль должен загружать один пользовательский файл.
  • Создать системные тесты: протестировать входные данные и запускаемый модуль. Поместить ссылку на него в раздел 5.2 SystemDocs

5 ноября

  • Используя профайлер, оптимизировать узкие места в коде. Проделанную работу описать в секции 5.3 systemdocs, используя отчеты профайлера и вставляя комментарии о проделанной работе.

На заметку:

  • Узкие места - те фрагменты кода, которые занимают значительное время при выполнении вычислительного эксперимента. Требуется показать, что при достигнуты улучшения кода при замене циклов на матричные операции или показать, что код достаточно хорошо оптимизирован. При этом необходимо в отчет вставить наиболее значимые строки из отчета профайлера. Это как правило, первые 10-15 строк. Копировать можно из html-отчета профайлера или воспользоваться функцией profile. В ней есть пример, как сохранить отчет профайлера в удобном формате. При оптимизации кода можно вставить в отчет те измерения кода, которые вы считаете удачными.
  • Также при оптимизации рекомендуется пользоваться функцией parfor - параллельный for. См. документацию "doc parfor" и пример, где показано как включать параллельный режим. Совет: конструкции вида x = x+1 или x(end+1) = y и подобные конструкции не распараллеливаются. Чтобы избежать таких конструкций, надо заранее создавать структуры/матрицы требуемого размера. Параллельные вычисления работают в Матлабе начиная с версии 2012.

12 ноября

  • Написать рецензию, назвать файл YourSurname2014ReviewSurname. В рецензии отражается, насколько качественно сделана система; удобно ли пользоваться документацией.
  • Подготовить доклад на одну минуту о рецензируемой работе.
  • Используя результаты вычислительного эксперимента и системного тестирования, создать поясняющие графики и таблицы и поместить их в раздел 5.2. При оформления отчета желательно разделять текст по содержанию на адекватно поименованные параграфы. В отчет должны входить:
    • Визуализация процесса выбора модели и оптимизиции структурных параметров
    • Визуализации зависимости функции потерь от уровня шума или других факторов
    • ...

19 ноября

Создать папку «web», содержащую следующие файлы:

  1. File "config.json" (name and extension should be the same). Fill this file using example placed in folder "Group074/Kuznetsov2013SSAForecasting/web/"
  2. File "main.m" with one argument variable and one resulting variable:

html = main(filname), where filename is a text string containing file name, and html is text string containing visual "web" report in html format.

  1. File "test.csv" (you can use another extension), This file should contain test object (text, time series, image, sound, video, etc.) for forecasting.
  2. Other files, that are required for function "main" (in particular file with parameters and structural parameters of forecasting model/algorithm)

For testing purposes it is strongly recommended to launch function writeHTML. It calls function "main('test.csv')" and save results into "out.html". This file should contain either "web" report about results of forecasting or error massage about some trouble with forecasting (types of errors were considered in data loading section).

Задачи

Шаблон задачи[1]

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

Предлагаемые задачи, часть 1

8. Прогнозирование третичных структур белков: оптимизация

  • Консультант: С.В. Грудинин, Ю.В. Максимов
  • Задача: Поиск наилучшей упаковки боковых цепей белковой структуры в предположении известного жесткого остова при помощи выпуклой оптимизации.

Более полная задача включает в себя также перебор оснований в первичной последовательность при жестком остове и называется "обратный фолдинг". Предложить алгоритм оптимизации.

Входная матрица разряжена и имеет блочный вид,


E(\underline{x})=\left[\begin{array}{c}
x_{1}^{1}\\
x_{2}^{1}\\
\vdots\\
x_{1}^{i}\\
x_{2}^{i}\\
\vdots\\
x_{1}^{N}\\
x_{2}^{N}\\
x_{3}^{N}
\end{array}\right]^{T}\left[\begin{array}{ccccccccc}
0 & 0 & \cdots & e_{11}^{k1} & e_{21}^{k1} & \cdots & e_{11}^{N1} & e_{21}^{N1} & e_{31}^{N1}\\
0 & 0 & \cdots & e_{12}^{k1} & e_{22}^{k1} & \cdots & e_{12}^{N1} & e_{22}^{N1} & e_{32}^{N1}\\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
e_{11}^{1i} & e_{21}^{1i} & \cdots & e_{11}^{ki} & e_{21}^{ki} & \cdots & e_{11}^{Ni} & e_{21}^{Ni} & e_{31}^{Ni}\\
e_{12}^{1i} & e_{22}^{1i} & \cdots & e_{12}^{ki} & e_{22}^{ki} & \cdots & e_{12}^{Ni} & e_{22}^{Ni} & e_{32}^{Ni}\\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\
e_{11}^{1N} & e_{21}^{1N} & \cdots & e_{11}^{kN} & e_{21}^{kN} & \cdots & 0 & 0 & 0\\
e_{12}^{1N} & e_{22}^{1N} & \cdots & e_{12}^{kN} & e_{22}^{kN} & \cdots & 0 & 0 & 0\\
e_{13}^{1N} & e_{23}^{1N} & \cdots & e_{13}^{kN} & e_{23}^{kN} & \cdots & 0 & 0 & 0
\end{array}\right]\left[\begin{array}{c}
x_{1}^{1}\\
x_{2}^{1}\\
\vdots\\
x_{1}^{i}\\
x_{2}^{i}\\
\vdots\\
x_{1}^{N}\\
x_{2}^{N}\\
x_{3}^{N}
\end{array}\right]

Нужно решить и исследовать следующие задачи:

1) Minimization problem 1 (statistical physics)  :

\begin{align} E(\underline{x})	+bx & \rightarrow	& \textrm{min} \\
\textrm{w.r.t}.	&&	\left|| x^{k}\right||_{1}=1\;\forall k \\
	&&	x_{i}^{k}\geq0\;\forall i,k \end{align}

2) Minimization problem 2 :

\begin{align}E(\underline{x})	+bx &\rightarrow&	\textrm{min}\\
\textrm{w.r.t}.	&&	\left|| x^{k}\right||_{2}=1\;\forall k \\
		&&x_{i}^{k}\geq0\;\forall i,k \end{align}

3) Minimization problem 3 (structural biology) :

\begin{align}E(\underline{x})	+bx &\rightarrow&	\textrm{min} \\
\textrm{w.r.t}.		&&\left|| x^{k}\right||_{\infty}=1\;\forall k \\
	&&	x_{i}^{k}\geq0\;\forall i,k \end{align}

7. Уточнение прогноза железнодорожных грузоперевозок по биржевым данным

  • Консультант: Стенина (Медведникова) Мария.
  • Задача: построить алгоритм уточнения прогноза грузоперевозок, включив в модель как исторические данные о загруженности, так и внешние данные: биржевые цены на основные инструменты и нормативные документы. Рассматривается проблема обнаружения причинно-следственных связей в разнородных временных рядах. Предлагается прогностическая модель, использующая выявленные связи. При построении модели используются экспертные высказывания относительно вида связей.
  • Данные: Исторические биржевые цены на основные инструменты и данные по железнодорожным грузоперевозкам.
  • Литература:
    • Вальков А.С., Кожанов Е.М., Медведникова М.М., Хусаинов Ф.И. Непараметрическое прогнозирование загруженности системы железнодорожных узлов по историческим данным. pdf
    • Вальков А.С., Кожанов Е.М., Мотренко А.П., Хусаинов Ф.И. Построение кросс-корреляционных зависимостей при прогнозе загруженности железнодорожного узла. pdf
  • Базовый алгоритм: Требуется найти.

5. Диагностика заболеваний по анализу пульсовой волны

  • Консультант: Кузнецова Рита.
  • Задача: Решается задача классификации состояния здоровья человека на основании анализа пульсовых волн. Требуется изучить набор базовых подходов и предложить новые варианты алгоритмов.
  • Данные: 1) [21]; 2) [22]
  • Литература:
    • Danbing Jia, Dongyu Zhang,Naimin Li Pulse Waveform Classification Using Support Vector Machine with Gaussian Time Warp Edit Distance Kernel, Computational and Mathematical Methods in Medicine Volume 2014 (2014)
    • Stephen R. Alty, Natalia Angarita-Jaimes, Sandrine C. Millasseau, Philip J. Chowienczy Predicting Arterial Stiffness From the Digital Volume Pulse Waveform, IEEE Trans Biomed Eng. 2007 Dec;54(12):2268-75.
    • C.C. Chiu, B.Y. Liau, S.J. Yeh, C.L. Hsu Artificial Neural Network Classification of Arterial Pulse Waveforms in Cardiovascular Diseases, Biomed 2008, Proceedings 21, pp. 129–132, 2008.
    • Almeida VG, Vieira J, Santos P, Pereira T, Pereira HC, Correia C, Pego M, Cardoso J. Machine Learning Techniques for Arterial Pressure Waveform Analysis, Journal of Personalized Medicine. 2013; 3(2):82-101.
  • Базовый алгоритм: SVM, алгоритмы кластеризации.

4. Рекомендация товаров для совместной продажи

  • Консультант: И.С. Гуз, А.А. Пимкова
  • Задача: Необходимо выделить группы товаров, продаваемых на Авито, которые являются дополняющими друг к другу (пример: автомобили и шины) и которые было бы интересно продавать совместно. При этом классический алгоритм выделения ассоциативных правил (пример - Apriori) не совсем эффективен, так как каждый товар описывается некоторой иерархией признаков (Пример: Авто -> Mazda -> 6 -> 2.0л) и эффективные правила могут содержать элементы различных иерархий (Вместе с "Авто -> Mazda -> 6" часто продаются "Шины -> Continental -> r16"). Необходимо формализовать и иметь возможность внедрить в алгоритм поиска подобных правил экспертные ограничения, запрещающие определенные классы правил, так как на их основе могут создаваться крайне не релевантные рекомендации.
  • Данные: История продаваемых совместно товаров, где каждый товар описывается набором атрибутов и принадлежит соответствующей товарной иерархии.
  • Литература:
    • Акобир Шахиди, Введение в анализ ассоциативных правил, 2002.
    • Акобир Шахиди, Apriori – масштабируемый алгоритм поиска ассоциативных правил, 2002 - http://www.basegroup.ru/library/analysis/association_rules/apriori/.
    • Сергей Ларин, Применение ассоциативных правил для стимулирования продаж>, 2003 - http://www.basegroup.ru/library/practice/salepromotion/.
    • R. Srikant, R. Agrawal, Mining Generalized Association Rules, In Proc. of the 21st International Conference on VLDB, Zurich, Switzerland, 1995.
    • J.S. Park, M.-S. Chen, and S.Y. Philip, An Effective HashBased Algorithm for Mining Association Rules, In Proc. ACM SIGMOD Int’l Conf. Management of Data, ACM Press, New York, 1995.
    • R. Agrawal, R. Srikant, Fast algorithms for mining association rules, In Proc. of the VLDB Conference, Santiago, Chile, September 1994

Базовый алгоритм: Алгоритм выделения обобщенных ассоциативных правил.

40. Определение что на картинке есть запрещенный товар

  • Консультант: В.А. Лексин
  • Задача: Двухклассовая классификация изображений
    • Часть 1: медикаменты
    • Часть 2: оружие
    • Часть 3: алкоголь и табак
  • Данные: На inclass.kaggle.com по приглашению.
  • Литература: Надо искать
  • Базовый алгоритм: Deep learning

21. Идентификация человека по изображению радужной оболочки глаза

  • Консультант: И.А. Матвеев
  • Задача: В проблеме идентификации человека по изображению радужной оболочки глаза (радужке) важнейшую роль играет выделение области радужки на исходном снимке (сегментация радужки). Однако, изображение радужки как правило частично закрыто (затенено) веками, ресницами, бликами, то есть часть радужки не может быть использована для распознавания и более того, использование данных с затенённых участков может порождать ложные признаки и снижать точность. Поэтому одним из важных этапов сегментации изображения радужки является

отбраковка затенённых участков.

  • Данные: растровое монохромное изображение, типичный размер 640*480 пикселей (однако, возможны и другие размеры) и координаты центров и радиусы двух окружностей, аппроксимирующих зрачок и радужку.
  • Литература:
    • Описание задачи и предлагаемые пути решения
    • Monro D. University of Bath Iris Image Database // http:// www.bath.ac.uk/ elec-eng/ research/ sipg/ irisweb/
    • Chinese academy of sciences institute of automation (CASIA) CASIA Iris image database // http://www.cb-sr.ia.ac.cn/IrisDatabase.htm, 2005.
    • MMU Iris Image Database: Multimedia University // http:// pesonna.mmu.edu.my/ ccteo/
    • Phillips P.J., Scruggs W.T., O’Toole A.J. et al. Frvt2006 and ice2006 large–scale experimental results // IEEE PAMI. 2010. V. 32. № 5. P. 831–846.
    • G.Xu, Z.Zhang, Y.Ma Improving the performance of iris recogniton system using eyelids and eyelashes detection and iris image enhancement // Proc. 5Th Int. Conf. Cognitive Informatics. 2006. P.871-876.
  • Базовый алгоритм: метод, использующий скользящее окно и текстурные признаки [2006: Xu, Zhang, Ma].

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

  • Консультант: И.А. Рейер, А.А. Адуенко
  • Задача:
  • Данные:
  • Литература:
  • Базовый алгоритм:

40. Определение точной границы зрачка

  • Консультант: И.А. Матвеев
  • Задача: Требуется разработать метод построения устойчивых точной границы и эквивалентной окружности (см. подробное описание задачи). Критерием качества алгоритма служит устойчивость найденных решений к малым вариациям исходных данных.
  • Данные: растровое монохромное изображение, типичный размер 640*480 пикселей (однако, возможны и другие размеры) и координаты центров и радиусы двух приближённых окружностей, аппроксимирующих зрачок и радужку. Тестовая выборка включает в себя несколько тысяч изображений баз BATH[1], CASIA [2], MMU[3], NDIRIS [4] с прилагающейся разметкой. Изображения в формате BMP.
  • Литература:
    • [1] Monro D. University of Bath Iris Image Database // http:// www.bath.ac.uk/ elec-eng/ research/ sipg/ irisweb/
    • [2] Chinese academy of sciences institute of automation (CASIA) CASIA Iris image database // http://www.cb-sr.ia.ac.cn/IrisDatabase.htm, 2005.
    • [3] MMU Iris Image Database: Multimedia University // http:// pesonna.mmu.edu.my/ ccteo/
    • [4] Phillips P.J., Scruggs W.T., O’Toole A.J. et al. Frvt2006 and ice2006 large–scale experimental results // IEEE PAMI. 2010. V. 32. № 5. P. 831–846.
    • Описание задачи
  • Базовый алгоритм: Один из перспективных вариантов решения — использование метода оптимального кругового пути; возможный альтернативный метод — непосредственный поиск округлого тёмного объекта в расширенном окне, заданном окружностью зрачка.

Часть 2

9. Прогнозирование четвертичных структур белков: нивелирование

  • Консультант: Ю.В. Максимов
  • Задача: Задача заключается в предсказании упаковки белковых молекул в мультимерный комплекс в приближении жестких тел. Одна из формклировок задачи записывается как невыпуклая оптимизация.

Нужно исследовать эту формулировку и предложить алгоритм решения.

Suppose we have N proteins in an assembly, such that each protein i can be located in one of P positions x_{p}^{i}. N is ~ 10, P ~ 100. To each two vectors x_{i}^{p} and x_{j}^{q}, we can assign an energy function q_{0}, which is the overlap integral in the simplest approximation. Each protein position also has an associated score b_{0}. Thus, the optimal packing problem can be formulated as


\begin{align}
x^{T}Q_{0}x+b_{0}^{T}x	&\rightarrow&	\textrm{min}\\
\textrm{w.r.t}.		&&\left\Vert x^{k}\right\Vert _{\infty}=1\;\forall k \\
	&&	x_{i}^{k}\geq0\;\forall i,k
\end{align}

  • Данные: Собираются при помощи одного из стандартных комплексов решенных при помощи электронной микроскопии. Значения энергий и интегралов перекрытия вычисляются при помощи модификации одного из стандартных пакетов, например, HermiteFit. Данные генерируются за ~ 1 минуту, модификация кода и подготовка данных займет ~ 1 неделю.
  • Литература: Ю.Е. Нестеров Введение в выпуклую оптимизацию (доступна на сайте PreMoLab)
  • Замечания по коду: Замечания по программной реализации
  • Базовый алгоритм: Хочется попробовать выпуклые релаксации.

1. Формирование однородных обучающих выборок в информационном анализе электрокардиосигналов

  • Консультант: Целых Влада
  • Задача:
    Дано: две размеченные выборки объектов двух классов. Первая выборка эталонная, вторая содержит неизвестную долю выбросов — объектов с неверной классификацией.
    Найти: вычислительно эффективный способ очистки второй выборки от выбросов.
    Критерий: возрастание 10-fold CV AUC при пополнении первой обучающей выборки отфильтрованной второй выборкой.
  • Данные: выборки электрокардиограмм с диагнозами по 14 заболеваниям, для каждого из которых есть два типа выборок: эталонные прецеденты (прошедшие всестороннее обследование с применением современных клинических, лабораторных и инструментальных методов исследования) и случаи, когда диагнозы устанавливались терапевтом.
  • Базовый алгоритм: пополнение обучающей выборки всеми объектами второй выборки с отступами не менее заданного порога.
  • Литература:
    1. Воронцов К. В. Изображение:Voron-ML-Metric-slides.pdf. Лекции по машинному обучению. — 2014.
    2. Успенский В. М. Информационная функция сердца // Клиническая медицина, 2008. — Т. 86, № 5. — С. 4–13.
    3. Успенский В. М. Информационная функция сердца. Теория и практика диагностики заболеваний внутренних органов методом информационного анализа электрокардиосигналов. — М.: «Экономика и информация», 2008. — 116 с.
    4. Обзоры по outlier detection, anomaly detection, novelty detection, semisupervised learning.

2. Полигон алгоритмов классификации для информационного анализа электрокардиосигналов

  • Консультант: Целых Влада
  • Задача: разработка инструментальной среды для поддержки совместной работы в исследовательской группе по информационному анализу ЭКГ-сигналов.
  • Данные: выборки электрокардиограмм с диагнозами по 14 заболеваниям. Объекты-электрокардиограммы задаются несколькими представлениями, полученными после различных этапов предобработки (демодуляции, дискретизации, векторизации).
  • Литература:
    1. Успенский В. М. Информационная функция сердца. Теория и практика диагностики заболеваний внутренних органов методом информационного анализа электрокардиосигналов. — М.: «Экономика и информация», 2008. — 116 с.

Базовый алгоритм: наивный байесовский классификатор над векторизованным представлением электрокардиограмм.

3. Монотонные классификаторы с отбором признаков для задач медицинской диагностики

  • Консультант: Зухба Анастасия
  • Задача: реализация и исследование алгоритма обучения монотонного классификатора ближайшего соседа с отбором признаков и эталонных объектов.
  • Данные: выборки электрокардиограмм (в векторном представлении) с диагнозами по 14 заболеваниям.
  • Литература:
    1. Махина Г.А. О восстановлении монотонных булевых функций методом ближайшего соседа. ИОИ-9. 2012.

Базовый алгоритм: наивный байесовский классификатор над векторизованным представлением электрокардиограмм.

6. Ранжирование документов с помощью структурно-простых моделей

  • Консультант: А.П. Мотренко
  • Задача: Решается задача поиска ранжирующей функции в задачах информационного поиска. Цель: развить или улучшить результаты работы [Goswami et al, 2014]. В работе [Goswami et al, 2014] поиск осуществляется полным перебором суперпозиций, порожденных заданной грамматикой и удовлетворяющих ограничениям, определяемым спецификой задачи. Предложенные ограничения позволяют провести перебор суперпозиций сложности (длины) до восьми включительно и обнаружить ранжирующие функции, статистически не менее точные, чем некоторые из традиционно используемых ранжирующих функций большей сложности (например, BM25 сложности 25). Возможные пути развития:
    • предложить алгоритм направленного поиска суперпозиций большей сложности на основе полученных результатов.
    • модифицировать базовый алгоритм и найти более оптимальную ранжирующую функцию.
  • Данные: Данные по текстовым коллекциям LIG. Объектами выборки являются пары документ-запрос (d, q), документы коллекции отранжированы экспертно для каждого запроса. Для каждого слова w из запроса q вычисляются значение ранжирующей функции f(x, y, k), зависящей от трех переменных:
  1. x — нормализованная частота встречаемости слова w в документе d:  x = t_d^{w}\log(1 + c\cdot l_{avg}/l_d), где t_d^{w} — частота встречаемости слова w в документе d (вычисляется для каждого слова из q), l_{d} длина документа в коллекции, l_{avg} — средняя длина документа в коллекции, c\in{\mathbb{R}} — некий параметр.
  2. y — нормализованная частота встречаемости слова w в коллекции:  y = \frac{N_w}{N}, где N_w — количество документов в коллекции, содержащих слово w, N — общее число документов в коллекции.
  3. k — действительнозначный параметр.
  • Литература:
    • Goswami P., Moura1 S., Gaussier E., Amini M.R. Exploring the Space of IR Functions //Advances in Information Retrieval. Lecture Notes in Computer Science. 8416:372-384, 2014.
    • Описание задачи.
  • Базовый алгоритм: Алгоритм полного перебора допустимых суперпозиций порождающих функций.


38. Разработка выпуклого обучаещего алгоритма Gibbs-SVM

  • Консультант: Ю. Максимов
  • Задача: Найти и исследовать устойчивое решение для следующей задачи, которая является продолжением метода опорных векторов.

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

Maximize (in w):


\frac{C}{p}||w||_{p}^{p}+\sum_{(x,y)\in D}\left(\epsilon\ln\sum_{x}e^{-\frac{w^{T}\phi(x)+loss(x)}{\epsilon}}-\epsilon\ln\sum_{y}e^{-\frac{w^{T}\phi(y)+loss(y)}{\epsilon}}\right)

Эта задача похожа на latent-variable SVM.

11. Про интегральные индикаторы

  • Консультант: М.П. Кузнецов
  • Задача:
  • Данные: Интернет
  • Литература:
    • ...
  • Базовый алгоритм:

16. Последовательный выбор моделей распознавания физической активности чесловека

  • Консультант: А.П. Мотренко
  • Задача: На основе существующих алгоритмов [Кузнецов: 2014; Попова, Стрижов: 2014] создать алгоритм онлайн классификации типа движения пользователя, который бы определял текущий тип активности, учитывая исторические данные и пользовательские отзывы (правильно или неправильно алгоритм распознал тип движения).
  • Данные: показания акселерометра, трехмерные временные ряды.
  • Литература:
  • Базовый алгоритм:


31. Визуализация и частичная разметка тематической структуры текстовых коллекций

  • Консультант: Потапенко Анна
  • Задача: Разработать среду визуализации, отображающую темы, документы и термины в вероятностной тематической модели. При отображении текста документа должны отображаться принадлежности слов к темам. Предусмотреть возможность ручной разметки принадлежности слов к темам для оценивания качества модели или частичного обучения.
  • Данные: Коллекция статей конференций ММРО-ИОИ за несколько лет.
  • Литература:
    1. Описание задачи и предлагаемые пути решения
    2. Vorontsov K. V., Potapenko A. A. Tutorial on Probabilistic Topic Modeling: Additive Regularization for Stochastic Matrix Factorization. // Analysis of Images, Social Networks, and Texts AIST-2014.— CCIS 436, Springer.

32. Тематическое моделирование новостных потоков

  • Консультант: Дойков Никита
  • Задача: Веб-интерфейс для визуального анализа качества динамической тематической модели. Для каждой темы, найденной моделью, должна генерироваться страница. На ней должны находиться: график темы во времени; ранжированный список сообщений, в которых была эта тема; ранжированный список терминов этой темы. Должны быть сформированы страницы сообщений, на которых можно прочитать их исходный текст, тематические слова должны быть покрашены цветами, соответствующими темам.
  • Данные: коллекция пресс-релизов органов государственной власти и внешнеполитических ведомств ряда стран за 10 лет, на английском языке.
  • Литература:
    1. Xuerui Wang and Andrew McCallum. Topics Over Time: a non-Markov continuous-time model of topical trends. 12th ACM SIGKDD.
  • Базовый алгоритм: описанные в литературе динамические тематические модели (ТОТ и др.)

33. Иерархическая тематическая модель научных конференций ММРО и ИОИ

  • Консультант: Стенин Сергей, Чиркова Надежда
  • Задача: реализация и исследование нисходящего алгоритма построения тематической иерархии с учётом авторства; визуализация тематической иерархии в виде web-сайта с возможностью навигации по тематическому дереву и по коллекции исходных документов в PDF-формате.
  • Данные: коллекция статей научных конференций ММРО и ИОИ за 7 лет, на русском языке.
  • Литература:
  • Базовый алгоритм: описанные в литературе иерархические тематические модели.

34. Мультиязычная тематическая модель для автоматического формирования словарей профессиональной терминологии

  • Консультант: Виктор Кантор (ABBYY), Марина Дударенко
  • Задача: реализация и исследование нисходящего алгоритма построения тематической иерархии с учётом авторства; визуализация тематической иерархии в виде web-сайта с возможностью навигации по тематическому дереву и по коллекции исходных документов в PDF-формате.
  • Данные: коллекция параллельных текстов (русский+английский) по математике и физике, предоставленная ABBYY.
  • Литература:
  • Базовый алгоритм: описанные в литературе методы выравнивания параллельных текстов, выделения терминов, формирования словарей.

35. Жанровая классификация текстов

  • Консультант: Романенко Александр, Потапенко Анна
  • Задача: кластеризация больших текстовых интернет-коллекций по жанрам.
  • Данные: коллекция текстов, размеченная экспертами по функциональным категориям (предоставлена Сергеем Шаровым).
  • Литература:
  • Базовый алгоритм: описанные в литературе методы выравнивания параллельных текстов, выделения терминов, формирования словарей.

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

  • Консультант: Соколов Евгений (Яндекс), Александр Фрей
  • Задача: построение мультимодальной тематической модели, учитывающей клики пользователей по рекламным объявлениям для повышения точности предсказания CTR объявлений.
  • Данные: под NDA Яндекс, возможна отладка модели на синтетических данных.
  • Литература:
  • Базовый алгоритм: описанные в литературе тематические модели классификации (Dependency LDA И др.).

37. Разработка метрик качества тематических моделей для библиотеки BigARTM

  • Консультант: Апишев Мурат
  • Задача: Сравнение онлайновых алгоритмов тематического моделирования текстовых коллекций, реализованных в библиотеках BigARTM и Vowpal Wabbit по производительности и качеству модели. Реализация метрик качества и средств мониторинга процесса обучения регуляризованных тематических моделей в BigARTM.
  • Данные: любые из доступных (примерно 10) текстовых коллекций.
  • Литература:
    1. Vorontsov K. V., Potapenko A. A. Tutorial on Probabilistic Topic Modeling: Additive Regularization for Stochastic Matrix Factorization. // Analysis of Images, Social Networks, and Texts AIST-2014.— CCIS 436, Springer.
  • Базовый алгоритм: PLSA, LDA.

41. Классификация научных текстов по отраслям знаний

  • Консультант: Царьков Сергей
  • Задача: повышение качества классификации научных текстов по отраслям науки при автоматическом выделении терминов.
  • Данные: коллекция авторефератов диссертаций на русском языке.
  • Литература: статьи по term extraction.
  • Базовый алгоритм: наивный байесовский классификатор с отбором признаков над униграммной моделью.

Часть 3

5. Алгоритм авторизации пользователя на основе акселерометрического описания жестов

  • Консультант: А.П. Мотренко
  • Задача: Задача состоит в разработке алгоритма анализа акселерометрических временных рядов с целью распознавания движений и идентификации личности пользователя. В случае, когда жест, совершаемый пользователем, фиксирован и известен, существующие алгоритмы [Пример 1] позволяют с высокой точностью определить, выполняет ли жест авторизированный пользователь (хозяин устройства) или кто-то другой. Необходимо разработать алгоритм, на основе исторических данных определяющий пользователя, выполняющего произвольные движения, по характерным биометрическим показателям.
  • Данные: показания акселерометра, трехмерные временные ряды.
  • Литература:

14. Выделение фундаментального периода при сегментировании акселерометрических временных рядов

  • Консультант: А.А. Кузьмин
  • Задача: Решается задача сегментирования временных рядов в рамках задачи распознавания активности человека по сенсорным временным рядам. Предполагается наличие фундаментальной периодики, рассматриваемой как элементарная единица движения. Исходя из природы исследуемых данных и соображений интерпретируемости, на выделяемые сегменты накладывается следующее требование: каждый сегмент должен соответствовать фундаментальному периоду. Проблемы:
  1. временные ряды не строго периодические\квазипериодические.
  2. временные ряды состоят из множества «периодик». Необходимо выбрать из них фундаментальную.
  • Данные: Есть, консультант.
  • Литература:
    • Мотренко, 2014. Extracting fundamental periods to segment human motion time series. pdf
  • Базовый алгоритм: Выбирается пара главных компонент тракторной матрицы исследуемого временного ряда, и траектория выбранных компонент рассекается осью симметрии. Таким образом ряд разбивается на полупериоды, которые затем объединяются в период.

25. Сравнение эффективности логических методов в задачах анализа данных

  • Консультант: Ю.В. Максимов
  • Задача: состоит в сравнительном исследовании качества комбинаторно-логических методов при решении задач анализа данных. В частности, сравнении методов, основанных на построении ДНФ разделяющих классы(редукционный; последовательное перемножение (Дьяконов)) и др.
  • Данные: Базы libsvm, uci и imagenet(файл с дип фичерсами для некоторых коллекций будет выдан консультантом).
  • Литература: приведена в файле
  • Замечания к коду: Замечания по программной реализации
  • Базовый алгоритм: Базовый алгоритм: Решающие деревья(ID3, ID4.5, CART), построение ДНФ последовательным перемножением(Дьяконов, 2003) и другие приведенные в файлах-описаниях.

24. Автоматическое построение программы научных конференций

  • Консультант: А.А. Кузьмин
  • Задача:
  • Данные:
  • Литература:
  • Базовый алгоритм: В работе [Пример 1] траектории вектора ускорения сравниваются с помощью углового расстояния между ними. Предлагается сравнивать не сами сигналы, но их фазовые траектории.

22. Сегментация визуальных сцен: группирование суперпикселей

  • Консультант: И.А. Рейер
  • Задача: В процессе подготовки
  • Данные:
  • Литература:
  • Базовый алгоритм:

19. Задача двухклассовой классификации изображений

  • Консультант: В.А.Лексин
  • Задача: Определение что на картинке есть контакты: телефонный номер, email, ссылка и т.д.
  • Данные: Планируется конкурс на machinelearning.ru
  • Литература:
    • Надо искать
  • Базовый алгоритм: Deep learning

18. Прогнозрование вероятности клика по покупательским поисковым запросам

  • Консультант: М.П. Кузнецов
  • Задача:
  • Данные: Есть
  • Литература:
    • ...
  • Базовый алгоритм:

15. Навигация в отсутствии сигнала GPS

  • Консультант:
  • Задача 1: Задано пространство (B) допустимых положений субъекта. Требуется по представленному "профилю" движения субъекта m определить его положение в пространстве B. Профиль движения может включать (не обязательно все) данные датчиков носимых приборов (смартфоны, "умные" браслеты и т.п.) — направление, ускорение, сердечный ритм, уровень сигнала и т.п.
  • Задача 2: Построение пространства (B) допустимых положений субъектов по профилям движения.
  • Данные: Консультант.
  • Литература:
    • ...
  • Базовый алгоритм:


20. Метапрогнозирование временных рядов

  • Консультант: А.С. Инякин
  • Задача: Задан набор алгоритмов прогнозирования временных рядов. По предъявленному временному ряду требуется указать алгоритм, который доставляет наиболее точный прогноз. При этом сам алгоритм выполнять не предполагается. Для решения этой задачи предлагается построить набор признаков, описывающих временной ряд Экспертно создается набор порождающих функций, которые 1) преобразуют временной ряд (например, сглаживают, раскладывают по главным компонентам), 2) извлекают из временного ряда его агрегированные описания (например, среднее, дисперсию, число экстремумов). Возможно порождение значительного количества признаков путем построения суперпозиций порождающих функций.
  • Данные: Библиотека квазипериодических и апериодических временных рядов
  • Литература:
    • Кузнецов М.П., Мафусалов А.А., Животовский Н.К., Зайцев Е., Сунгуров Д.С. Сглаживающие алгоритмы прогнозирования // Машинное обучение и анализ данных, 2011. T.1, №1. C.104-112.
    • Фадеев И.В., Ивкин Н.П., Савинов Н.А., Корниенко А.И., Кононенко Д.С., Джамтырова Р.Б. Авторегрессионные алгоритмы прогнозирования // Машинное обучение и анализ данных, 2011. T.1, №1. C.92-103.
    • Найти дополнительную обзорную литературу по автоматическому прогнозированию.

27. Исправление опечаток

  • Задача: Samsung, подробная информация по требованию

28.T9

  • Задача: построить модель, предлагающую следующее слово во фразе по известным предыдущим. (подробная информация по требованию)
  • Данные: Samsung

29. Классификация в естественных языках

  • Задача: определение языка; определение кодировки (угадать правильную кодировку, если текст отображается в нечитаемом виде); классификация по темам, жанрам и т. д.(подробная информация по требованию)
  • Данные: Samsung

30. Вопросно-ответная система

  • Задача: извлечение информации (какие-нибудь простые типы вопросов, подробная информация по требованию)
  • Данные: Samsung

39. Обучение метрик в задачах полного и частичного обучения

  • Консультант: Ю.В. Максимов
  • Задача: состоит в программной реализации комплекса методов выпуклой и DC-оптимизации для задачи выбора оптимальной метрики в задачах распознавания. Иными словами, в построении метрики такой, что классификация методом ближайших соседей дает высокую точность.
  • Данные: Birds и Fungus коллекции ImageNet с извлеченными Deep features(предоставляется консультантом).
  • Литература: Список литературы и описание подробное задачи приведены в файле
  • Замечания к коду: Замечания по программной реализации
  • Базовый алгоритм: выпуклая релаксация задачи решаемая внутренней точкой через CVX.

Сделать

Написать методические рекомендации для руководителей по планированию и проверке результатов работ.


Примечания

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