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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (Результаты)
м (Результаты)
Строка 130: Строка 130:
|Ранжирование документов с помощью структурно-простых моделей
|Ранжирование документов с помощью структурно-простых моделей
|[http://svn.code.sf.net/p/mlalgorithms/code/Group174/Kulunchakov2014IsomorphicStructures/], [http://svn.code.sf.net/p/mlalgorithms/code/Group174/Kulunchakov2014IsomorphicStructures/doc/Kulunchakov2014IsomorphicStructures.pdf?format=raw pdf]
|[http://svn.code.sf.net/p/mlalgorithms/code/Group174/Kulunchakov2014IsomorphicStructures/], [http://svn.code.sf.net/p/mlalgorithms/code/Group174/Kulunchakov2014IsomorphicStructures/doc/Kulunchakov2014IsomorphicStructures.pdf?format=raw pdf]
-
|[Участник:Anastasiya|Мотренко Анастасия]
+
|[[Участник:Anastasiya|Мотренко Анастасия]]
|
|
|
|

Версия 14:53, 3 сентября 2014


Заметки и планы осеннего семестра. Материал будет убран на методическую страницу к концу августа. В сентябре тут будут опубликованы разделы Результаты, Расписание, Постановка задач. --Strijov 02:09, 15 мая 2014 (MSD)


Этот семестр посвящен постановке вычислительных экспериментов. Результатом эксперимента является анализ свойств математической модели, получаемой в результате решения поставленной задачи машинного обучения анализа данных. Построенная модель подготавливается к эксплуатации и представляется на языке, наиболее подходящем для эксплуатации. 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 для интернета.

Результаты

Автор Тема научной работы Ссылка Консультант Доклады Буквы Сумма Оценка
Газизуллина Римма Поставьте в это поле название работы [2], pdf
Гринчук Алексей [3], pdf
Гущин Александр [4], pdf
Ефимова Ирина Формирование однородных обучающих выборок в информационном анализе ЭКГ-сигналов [5], pdf Целых Влада
Жуков Андрей Тематическое моделирование новостных потоков [6], pdf ?
Игнатов Андрей Полигон алгоритмов классификации для информационного анализа ЭКГ-сигналов [7], pdf Целых Влада
Карасиков Михаил [8], pdf
Кулунчаков Андрей Ранжирование документов с помощью структурно-простых моделей [9], pdf Мотренко Анастасия
Липатова Анна [10], pdf
Макарова Анастасия [11], pdf
Плавин Александр Визуализация и частичная разметка тематической структуры текстовых коллекций [12], pdf Потапенко Анна
Попова Мария [13], pdf
Швец Михаил Монотонные классификаторы с отбором признаков для задач медицинской диагностики [14], pdf Зухба Анастасия
Шинкевич Михаил [15], pdf
Абе Калан (Sk) Что
Иванов Николай (Sk) Что
Кищенко Ярослав (Sk) Что
Логинс Алвис (Sk) Что
Мунхоева Марина (Sk) Что
Усман Бен (Sk) Что
Червинский Федор (Sk) Что
Юрченко Виктор (Sk) Что
Гурьев Георгий (Sk) Что
Павленко Виталий (Sk) Что

Расписание (до начала курса будет уточняться)

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

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

10 сентября

Выбрать задачу и подготовить доклад о выбранной задаче на 45 секунд (первая часть группы).

17 сентября

  • Заполнить разделы «Мотивация» (1.1.2) и «Литература» (1.1.3) в SystemDocs
  • Собрать выборку и описать форматы и структуры данных в разделе 1.4 SystemDocs
  • Подготовить доклад о выбранной задаче на 45 секунд (вторая часть группы).

24 сентября

Написать постановку задачи (используя LaTeX)


1 октября

  • Описать интерфейсы (раздел 2 SystemDocs)
  • Написать код.

8 октября

  • При необходимости, доработать постановку задачи.
  • Заполнить раздел 1.1.1 — описание проекта.
  • Создать двухуровневую схему в IDEF0 (разделы 1.2.2 и 1.2.3), желательно, разделяя стадии обучения и использования модели.

15 октября

Написать юнит-тесты для каждого модуля.

22 октября

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

29 октября

  • Написать отзыв, назвать файл YourSurname2014ReviewSurname
  • Подготовить доклад на одну минуту
  • Создать системные тесты: протестировать входные данные и запускаемый модуль. Поместить ссылку на него в раздел 5.2 SystemDocs

5 ноября

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

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

12 ноября

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

Задачи

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

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

Список проектов

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.

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

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

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

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

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

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.
    • Описание задачи.
  • Базовой алгоритм: Алгоритм полного перебора допустимых суперпозиций порождающих функций.

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

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

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}

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 неделю.
  • Литература:
  • Базовой алгоритм: Хочется попробовать выпуклые релаксации.

10. Прогнозирование объемов потребоения электроэнегргии

  • Консультант: Маркус Хильдман
  • Задача: Сделать элегантную систему прогнозирования.
  • Данные: Консультант.
  • Литература:
    • ...
  • Базовой алгоритм:

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

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

12. Про копулы

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

13. Про медицину

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

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

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

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

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

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

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

17. Интерпретация движений человека с помощью носимого акселерометра

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

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

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

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

  • Консультант: И.С. Гуз
  • Задача: Определение что на картинке есть телефонный номер, изображены таблетки и т.д.
  • Данные: В гуглдокс
  • Литература:
    • ...
  • Базовой алгоритм: Deep learning

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

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

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].

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

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

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

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

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

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

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

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

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

  • Поставщик: Samsung

28.T9

  • Задача: построить модель, предлагающую следующее слово во фразе по известным предыдущим.
  • Поставщик: Samsung

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

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

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

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

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, реализация метрик качества и средств мониторинга процесса обучения регуляризованных тематических моделей по текстовым коллекциям.
  • Данные: любые из доступных (примерно 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.

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.

Сделать

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


Примечания

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