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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Список проектов)
(Задача 6)
Строка 421: Строка 421:
* '''Желательные навыки''': готовность быстро разобраться в различных подходах к регрессии, знание или готовность к освоению С++ на среднем уровне (для более полного исследования нужно будет попробовать библиотеки на С++)
* '''Желательные навыки''': готовность быстро разобраться в различных подходах к регрессии, знание или готовность к освоению С++ на среднем уровне (для более полного исследования нужно будет попробовать библиотеки на С++)
 +
 +
=== Задача 7 ===
 +
* '''Название''': определение положения белков по электронной карте
 +
* '''Задача''': неформально --- есть наборы экспериментально определённых карт расположения белков в комплексах, часть из них известна в высоком разрешении, необходимо восстановить всю карту в высоком разрешении; формально --- есть матрицы и вектора энергий соответствующие каждой карте белкового комплекса, нужно определить какой набор белков минимизирует квадратичную форму, образованую матрицей и вектором.
 +
* '''Данные''': экспериментальные данные с сайта http://www.emdatabank.org/ будуь преобразованы в матрицы в вектора энергий. Понимание биофизической природы не обязательно.
 +
* '''Литература''': статьи по методам решения задач квадратичного программирования и различным релаксациям
 +
* '''Базовой алгоритм''': методы квадратичного программирования с различными релаксациями
 +
* '''Решение''': минимизация суммарной энергии белкового комплекса
 +
* '''Новизна''': применение методов квадратичного программирования и исследование их точности в задачах восстановления электронных карт
 +
* '''Консультант''': Александр Катруца, автор задачи: Сергей Грудинин.
 +
* '''Желательные навыки''': понимание и интерес к методам оптимизации, работа с пакетом CVX
=== Задача 10 ===
=== Задача 10 ===

Версия 08:13, 18 февраля 2016


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

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

Роли

Студент третьего курса очень хочет научиться ставить задачи формально, находить нужную литературу, порождать новые и актуальные идеи и решения задач.

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

Эксперт: поставщик задачи, владелец данных, либо тот, кто гарантирует новизну и актуальность работы.

Результаты

Автор Тема научной работы Ссылка Консультант Рецензент Доклад Буквы Сумма Оценка Журнал
Гончаров Алексей Метрическая классификация временных рядов code,

paper, slides

Мария Попова Задаянчук Андрей BMF AILSBRCVTDSW 12 10 ИИП
Баяндина Анастасия
Белозерова Анастасия
Владимирова Мария
Володин Сергей
Городницкий Олег
Иванычев Сергей
Ковалева Валерия
Макарчук Глеб
Малыгин Виталий
Молибог Игорь
Погодин Роман
Рязанов Андрей
Сафин Камиль
Федоряка Дмитрий
Цветкова Ольга
Чигринский Виктор

Расписание

Расписание будет изменено.


Дата ДЗ Тема лекции Результат для обсуждения Код
Февраль 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

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

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

Задачи

Шаблон описания научной статьи

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


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

Задача 5

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

Задача 6

  • Название: Sparse Regularized Regression on Protein Complex Data
  • Задача: найти лучшую модель регрессии на данных связывания белковых комплексов
  • Данные: признаковое описание белковых комплексов и константы связывания для них
  • Литература: статьи по регрессии и сравнению методов на схожих данных
  • Базовой алгоритм: регуляризованная линейная регрессия (Lasso, Ridge, ...), SVR, kernel methods, etc..
  • Решение: сравнение различных алгоритмов регрессии на данных, выбор оптимальной модели и оптимизация параметров
  • Новизна: получение лучшей модели регрессии для данных связывания белковых комплексов
  • Консультант: Александр Катруца, автор задачи: Сергей Грудинин.
  • Желательные навыки: готовность быстро разобраться в различных подходах к регрессии, знание или готовность к освоению С++ на среднем уровне (для более полного исследования нужно будет попробовать библиотеки на С++)


Задача 7

  • Название: определение положения белков по электронной карте
  • Задача: неформально --- есть наборы экспериментально определённых карт расположения белков в комплексах, часть из них известна в высоком разрешении, необходимо восстановить всю карту в высоком разрешении; формально --- есть матрицы и вектора энергий соответствующие каждой карте белкового комплекса, нужно определить какой набор белков минимизирует квадратичную форму, образованую матрицей и вектором.
  • Данные: экспериментальные данные с сайта http://www.emdatabank.org/ будуь преобразованы в матрицы в вектора энергий. Понимание биофизической природы не обязательно.
  • Литература: статьи по методам решения задач квадратичного программирования и различным релаксациям
  • Базовой алгоритм: методы квадратичного программирования с различными релаксациями
  • Решение: минимизация суммарной энергии белкового комплекса
  • Новизна: применение методов квадратичного программирования и исследование их точности в задачах восстановления электронных карт
  • Консультант: Александр Катруца, автор задачи: Сергей Грудинин.
  • Желательные навыки: понимание и интерес к методам оптимизации, работа с пакетом CVX

Задача 10

  • Название: Multi-task learning подход для задачи предсказания биологической активности ядерных рецепторов
  • Задача: В задаче необходимо построить multi-task модель, предсказывающую взаимодействие двух типов молекул: рецепторов и протеинов. Решение этой задачи необходимо для разработки новых лекарств (drug design).
  • Данные: описание 8500+ протеинов и метки для 12 рецепторов
  • Литература: будет отправлена студенту
  • Базовой алгоритм: multi-task lasso регрессия из библиотеки python scikit-learn
  • Решение: обобщение линейной регрересси на случай multi-task в вероятностной интерпретации
  • Новизна: Multi-task learning подход является новаторским в области drug design
  • Консультант: Мария Попова
  • Желательные навыки: понимание и интерес к теории вероятности, готовность быстро разобраться в различных подходах к регрессии, знание или готовность к освоению Python


Задача 12

  • Название: Смеси моделей в векторной авторегрессии в задаче прогнозирования (больших) временных рядов.
  • Задача: Имеется набор временных рядов длины T, содержащих показания различных датчиков, отражающих состояние устройства. Необходимо предсказать следующие t показаний датчиков. Практическая значимость: перед поломкой состояние устройства меняется, предсказание "аномального" поведения поможет своевременно принять меры и избежать поломки или минимизировать потери.
  • Данные: Многомерные временные ряды с показаниями различных датчиков серверов (загрузка ЦП, памяти, температура)
  • Литература: Ключевые слова: mixture models, boosting, Adaboost, векторная авторегрессия.
    • Александр Цыплаков. Введение в прогнозирование в классических моделях временных рядов. [1]
    • Нейчев Р.Г., Катруца А.М., Стрижов В.В. Выбор оптимального набора признаков из мультикоррелирующего множества в задаче прогнозирования[2]
    • Christopher M. Bishop. Pattern Recognition and Machine Learning. Страница 667
  • Базовый алгоритм: Бустинг, алгоритм Adaboost.
  • Решение: Использовать для построения проноза смесь нескольких линейных моделей вместо одной сложной.
  • Новизна: Доработано пространство параметров для смеси моделей в векторной авторегрессии.
  • Консультант: Радослав Нейчев

Задача 14

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


Задача 16

  • Название: Адаптивный нелинейный метод восстановления матрицы по частичным наблюдениям
  • Задача: Пусть есть неизвестная (возможно многомерная) матрица A, позиция элемента в ней описывается целочисленным вектором p. Известны значения матрицы на некотором подмножестве ее элементов. Требуется найти параметризацию и параметры такие, что на некотором некотором подмножестве элементов минимизируется квадратичное отклонение. Более подробное описание по ссылке [4]
  • Данные: модельные данные, Netflix Prize Data Set, MovieLens 20M Dataset, Criteo Display Advertising Challenge Dataset
  • Литература:
    • "ACCAMS: Additive Co-Clustering to Approximate Matrices Succinctly" (Beutel, Amr Ahmed, Smola)
    • "Non-linear Matrix Factorization with Gaussian Processes" (Neil D. Lawrence)
    • "Low-rank matrix completion using alternating minimization" (Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi)
  • Базовый алгоритм: Низкоранговое приближение
  • Решение: И параметры, и параметризацию искать из данных.
  • Новизна: Обобщение работ в данной области; предложена новая модель, эфективность которой предлагается проверить
  • Консультант: Михаил Трофимов
  • Желательные навыки: python

Задача 17

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

Задача 18

  • Название: Аппроксимация границ радужки глаза.
  • Задача: По изображению человеческого глаза определить окружности, аппроксимирующие внутреннюю и внешнюю границу радужки.
  • Данные: Растровые монохромные изображения, типичный размер 640*480 пикселей (однако, возможны и другие размеры)

[7], [8].

  • Литература:
    • К.А.Ганькин, А.Н.Гнеушев, И.А.Матвеев Сегментация изображения радужки глаза, основанная на приближенных методах с последующими уточнениями // Известия РАН. Теория и системы управления, 2014, № 2, с. 78–92.
    • Duda, R. O. Use of the Hough transformation to detect lines and curves in pictures / R. O. Duda, P. E. Hart // Communications of the ACM. 1972. Vol. 15, no. 1. Pp.
  • Базовый алгоритм: Ефимов Юрий. Поиск внешней и внутренней границ радужки на изображении глаза методом парных градиентов, 2015.
  • Решение: См. Iris_circle_problem.pdf
  • Новизна: Предложен быстрый беспереборный алгоритм аппроксимации границ с помощью линейных мультимоделей.
  • Консультант: Юрий Ефимов (автор Стрижов, эксперт Матвеев)

Задача 19

  • Название: Аппроксимация комбинаторных оценок переобучения для отбора признаков в задаче медицинской диагностики.
  • Задача: Технология информационного анализа электрокардиосигналов по В. М. Успенскому применяется для диагностики заболеваний внутренних органов по электрокардиограмме. Линейный наивный байесовский классификатор с отбором признаков хорошо зарекомендовал себя в этой задаче. Однако для отбора признаков до сих пор использовались только очень простые жадные стратегии. Предлагается использовать более интенсивные переборные стратегии, чтобы найти лучшие и более короткие диагностические наборы признаков. Однако чем интенсивнее перебор, тем выше вероятность переобучения. Для сокращения переобучения предлагается использовать комбинаторные оценки переобучения пороговых решающих правил. Для эффективного вычисления этих оценок предлагается использовать суррогатное моделирование.
  • Данные: Выборки векторов признаковых описаний ЭКГ, полученные с помощью системы скрининговой диагностики «Скринфакс». Будут выданы.
  • Литература:
  • Базовой алгоритм: линейный наивный байесовский классификатор с отбором признаков.
  • Решение: Для оценивания переобучения используются точные комбинаторные формулы. Для аппроксимации (суррогатного моделирования) этих формул используется MVR Composer. Для отбора признаков используются эвристические полужадные алгоритмы комбинаторной оптимизации.
  • Новизна: Ранее для отбора признаков комбинаторные оценки переобучения не применялись. Данный метод позволяет сокращать диагностические наборы признаков и улучшать качество классификации.
  • Консультант: Ишкина Шаура, Кулунчаков Андрей (MVR Composer), автор задачи: К.В.Воронцов

Задача 20

  • Название: Модель порождения объектов в задаче прогнозирования временных рядов
  • Задача: Построить модель порождения объектов для задачи прогнозирования, которая будет создавать качественную выборку для последующего решения задачи прогнозирования.
  • Данные: Временные ряды потребления электроэнергии, временные ряды акселерометра мобильного телефона
  • Литература:
    • Keogh E. J., Pazzani M. J. Scaling up dynamic time warping to massive datasets
    • Salvador S., Chan P. Fastdtw: Toward accurate dynamic time warping in linear time and space
    • Кузнецов М.П., Ивкин Н.П. Алгоритм классификации временных рядов акселерометра по комбинированному признаковому описанию
    • Карасиков М. Е. Классификация временных рядов в пространстве параметров порождающих моделей [9]
  • Базовой алгоритм: Различные эвристики
  • Постановка задачи: Формулировка и подробное описание задачи приведено по ссылке [10]
  • Новизна: рассмотрение модели порождения данных в подобной задаче
  • Консультант: Гончаров Алексей

Задача 21

  • Название: Алгоритм прогнозирования структуры локально-оптимальных моделей
  • Задача: Требуется спрогнозировать временной ряд с помощью некоторой параметрической суперпозицией алгебраических функций. Предлагается не стоить прогностическую модель, а спрогнозировать ее, то есть предсказать структуру аппроксимирующей суперпозиции. Вводится класс рассматриваемых суперпозиций, и на множестве таких структурных описаний проводится поиск локально-оптимальной модели для рассматриваемой задачи. Задача состоит в 1) поиске подходящего структурного описания модели 2) описания алгоритма поиска той структуры, которая будет соответствовать оптимальной модели 3) описания алгоритма обратного построения модели по ее структурному описанию. В качестве уже имеющегося примера ответа на вопросы 1-3, смотри работы А. А. Варфоломеевой.
  • Данные: Набор временных рядов, который подразумевает восстановление функциональных зависимостей. Предлагается сначала использовать синтетические данные или сразу применить алгоритм к прогнозированию временных рядов 1) потребления электроэнергии 2) физической активности с последующим анализом получающихся структур.
  • Литература:
    • А. А. Варфоломеева Выбор признаков при разметке библиографических списков методами структурного обучения, 2013, [11]
    • Bin Cao, Ying Li and Jianwei Yin Measuring Similarity between Graphs Based on the Levenshtein Distance, 2012, [12]
  • Базовой алгоритм: Конкретно к предлагаемой проблеме базового алгоритма нет. Предлагается попробовать повторить эксперимент А. А. Варфоломеевой для другого структурного описания, чтобы понять, что происходит.
  • Решение: Суперпозиция алгебраических функций задает ордерево, на вершинах которого заданы метки соответствующих алгебраических функций или переменных. Поэтому структурным описанием такой суперпозиции может являться ее DFS-code. Это строка, состоящая из меток вершин, записанных в порядке обхода дерева поиском в глубину. Зная арности соответствующих алгебраических функций, можем любой такой DFS-code восстановить за O(n) и получить обратно суперпозицию функций. На множестве подобных строковых описаний предлагается искать то строковое описание, которое будет соответствовать оптимальной модели.
  • Консультант: Кулунчаков Андрей

Задача 22

  • Название: Определение заимствований в тексте без указания источника
  • Задача: Решается задача выявления внутренних заимствований в тексте. Требуется проверить гипотезу о том, что заданный текст написан единственным автором, и в случае ее невыполнения выделить заимствованные части текста. Заимствованием считается часть текста, предположительно написанная другим автором и содержащая характерные отличия от стиля основного автора. Требуется разработать такую стилевую функцию, которая позволяет с высокой степенью достоверности отличить стиль основного автора текста от заимствований.
  • Данные: Коллекция конкурса PAN-2011.
  • Литература:
    1. Oberreuter, G., L’Huillier, G., Rıos, S. A., & Velásquez, J. D. (2011). Approaches for intrinsic and external plagiarism detection. Proceedings of the PAN.
  • Базовый алгоритм, решение: На текущий момент реализован базовый метод выявления зависимостей, основанный на анализе частотностей слов и символьных n-грамм в предложении. Для каждого текста формируется словарь, в котором каждому слову (n-грамме) поставлено в соответствие значение его встречаемости в тексте. На основе значений встречаемости формируется признаковое описание каждого сегмента-предложения. Выполняется классификация сегментов текста на основе экспертной разметки заимствований. Качество базового алгоритма составляет 0.29 по F1-мере (Pladget 0.21) на коллекции PAN-2011, в то время как качество лучшего алгоритма, принимавшего участие в соревновании 2011 года [Oberreuter], составляет 0.32 по F1-мере (Pladget 0.32). Предлагается реализовать этот алгоритм и сравнить его с базовым методом.
  • Консультант: Михаил Кузнецов

Задача 23

  • Название: Использование методов снижения размерности при построении признакового пространства в задаче обнаружения внутреннего плагиата
  • Задача: Для более эффективного решения задачи обнаружения внутреннего плагиата использовать методы снижения размерности, сохраняющие расстояние между объектами. Требуется доработать метод tSNE [2], включив в модель информацию о разметке данных и возможность добавления ранее не рассмотренных объектов в пространство сниженной размерности. Подробнее см. [1]
  • Данные: Коллекция конкурса PAN-2011.
  • Литература:
    1. Problem_statement_dim_reduce.pdf‎
    2. Laurens van der Maaten. Visualizing Data using t-SNE Journal of Machine Learning Research, 9 (2008) 2579-2605.
    3. Julian Brooke and Graeme Hirst. Paragraph Clustering for Intrinsic Plagiarism Detection using a Stylistic Vector-Space Model with Extrinsic Features, 2012.
  • Базовой алгоритм, решение: См. [1]
  • Консультант: Мотренко Анастасия

Задача 24

  • Название: Анализ клиентских сред и задача непрерывного аукциона: экстремальная многоклассовая классификация
  • Задача: Ранжирующая модель выбирается из класса случайных решающих деревьев. Исследуются свойства процедуры случайного построения моделей.
  • Данные:
    1. Yahoo!,
    2. Microsoft.
  • Литература:
    1. ICML'13 (tutorial),
    2. Slides,
    3. ECML'15 workshop,
    4. Manik Varma presentation on multi-label multi-class classification.
  • Базовой алгоритм: FastXML
  • Новизна: Построение универсальной модели для решения широкого класса задач, в которых над множеством меток классов определена алгебраическая структура.
  • Консультант: В.В. Стрижов


Задача 28

  • Название: Склейка белковых комплексов
  • Консультант: Нечаев, Максимов
Личные инструменты