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

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

Версия 14:11, 18 февраля 2015 (править) Romazepa (Обсуждение | вклад) (→Сколтех) ← К предыдущему изменению		Версия 14:16, 18 февраля 2015 (править) (отменить) Romazepa (Обсуждение | вклад) (→Сколтех) К следующему изменению →
Строка 169:		Строка 169:
	|Роман Прилепский (Ск)		|Роман Прилепский (Ск)
	|Автоматическое построение оптимальной структуры сети глубокого обучения для задач классификации временных рядов		|Автоматическое построение оптимальной структуры сети глубокого обучения для задач классификации временных рядов
-	|	+	|[http://sourceforge.net/p/mlalgorithms/code/HEAD/tree/Group174/Prilepskiy2014AutotuneDeepLearning]
	|В. В. Стрижов		|В. В. Стрижов
	|		|

---

Версия 14:16, 18 февраля 2015

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

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

• Группа 174, весна 2014: первая научная статья
• Группа 174, осень 2014: вычислительный эксперимент

Планирование научных исследований

Участвуют эксперты, индивидуальные консультанты и студенты кафедры.

• Описание курса
• Методика преподавания
• Результаты предыдущего курса
• Короткая ссылка на эту страницу: bit.ly/1BW1Sy8

Результаты

Физтех

Автор	Тема научной работы	Ссылка	Консультант	Рецензенты	Буквы
Газизуллина Римма	Исследование взаимосвязанности временных рядов	[1], pdf	Консультант		N
Гринчук Алексей	Использование контекстной документной кластеризации для улучшения качества построения тематичсеких моделей	[2], pdf	Апишев Мурат, Ромов Пётр		N-
Гущин Александр	Тема				N0
Ефимова Ирина	Формирование однородных обучающих выборок в задачах классификации	[3], pdf	Целых Влада		N
Жуков Андрей	Тема				N0
Игнатов Андрей	Применение Deep Learning в задаче информационного анализа ЭКГ-сигналов	[4], pdf	Ишкина Шаура		N
Карасиков Михаил	Тема				N0
Кулунчаков Андрей	Порождение структурно простых ранжирующих функций для задач информационного поиска	[5], pdf	Мотренко Анастасия		N
Липатова Анна	Улучшение качества классификации наивного байесовского классификатора путем добавления регуляризации.	[6], pdf	К. В. Воронцов		N-
Макарова Анастасия	Тема				N0
Плавин Александр	Тема				N0
Попова Мария	Классификация временных рядов с использованием методов Deep Learning	[7] [8]	В. В. Стрижов		N
Швец Михаил	Монотонные классификаторы для задач медицинской диагностики	[9], pdf			N
Шинкевич Михаил	Применение коллаборативной фильтрации, активного обучения и навигационной корреляции в задаче выделения селекторов				N
Авдюхов Дмитрий	Тема				N0
Гиззатуллин Анвар	Тема				N0
Костюк Анна	Тема				N0
Сухарева Анжелика	Классификация научных текстов по отраслям знаний				N-

Сколтех

Автор	Тема научной работы	Ссылка	Консультант	Рецензенты	Буквы
Роман Прилепский (Ск)	Автоматическое построение оптимальной структуры сети глубокого обучения для задач классификации временных рядов	[10]	В. В. Стрижов		N-
Михаил Матросов (Ск)	Прогнозирование сложноорганизованных наборов временных рядов				N-
Владимир Жуйков	Тема				N0
АВ	Тема				N0
Антон Киселев	Тема				N0
Александра Кудряшова	Detection of emotions using video record				N0
Алвис Логинс	EVERGREEN: Spatial join-oriented data structure				N

Расписание

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

ДЗ-1 (к 18.02)

1. Заполнить на странице курса bit.ly/1BW1Sy8 шаблон описания задачи,
2. Подготовить короткий доклад на 45 сек. с описанием задачи.

ДЗ-2 (к 25.02)

1. Собрать список литературы по выбранной теме. Список литературы должен содержать около двадцати позиций. Позиции из списка можно условно разделить на секции
   • Ссылки на работы, содержащие идею исследования. Желательно, чтобы работы были написаны различными авторами.
   • Ссылки на работы, в которых предлагаемые в работе методы применяются для решения различных прикладных задач.
   • Ссылки на данные, их описание, описание прикладной задачи связанной с исследуемыми данными.
   • Дополнительная информация: ссылки на описание инструментов (если используются специальные библиотеки или программное обеспечение); работы, формирующие теоретическую базу исследования, обзоры работ по исследуемой теме.
2. Сделать презентацию, состоящую из двух слайдов:
   1. На первом слайде кратко сформулировать цели исследования, решаемую задача (в чем она заключается и где актуальна), методы решения.
   2. На втором привести список основных источников.
3. Создать шаблон статьи и заполнить в нем раздел «Related work», содержащий обзор собранной литературы.

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

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

Задачи

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

• Название: Название, под которым статья подается в журнал.

• Задача: Описание или постановка задачи. Желательна постановка в виде задачи оптимизации (в формате argmin). Также возможна ссылка на классическую постановку задачи.

• Данные: Краткое описание данных, используемых в вычислительном эксперименте, и ссылка на выборку.

• Литература: Список научных работ, дополненный 1) формулировкой решаемой задачи, 2) ссылками на новые результаты, 3) основной информацией об исследуемой проблеме.

• Базовой алгоритм: Ссылка на алгоритм, с которым проводится сравнение или на ближайшую по теме работу.

• Решение: Предлагаемое решение задачи и способы проведения исследования. Способы представления и визуализации данных и проведения анализа ошибок, анализа качества алгоритма.

• Новизна: Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала).

1. Порождение структурно простых ранжирующих функций для задач информационного поиска

• Задача: Решается проблема порождения ранжирующих функций в задачах информационного поиска. Ранжирующая функция ищется в виде суперпозиции некоторых заданных порождающих функций. Предлагается генетический алгоритм порождения структурно-простых суперпозиций, который затем сравнивается с алгоритмом полного перебора. Функционалами качества при этом являются MAP и P@10. Оптимальность полученных функций предлагается исследовать с помощью метрик на моделях и данных. Ссылка на подробную постановку задачи.

• Данные: Выборка состоит из нескольких коллекций документов. Каждой коллекции экспертом приписано множество запросов и для некоторых из ее документов заданы оценки релевантности данным запросам. Ссылка на данные и ссылка на запросы и экcпертные оценки.

• Литература:

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

• • P. Goswami, S. Moura, E. Gaussier et al. / Exploring the space of ir functions // ECIR'14. - 2014. - Pp. 372-384.

Постановка задачи для генетического алгоритма на моделях любой сложности.

• • Fan W., Gordon M. D., Pathak P. / A generic ranking function discovery framework by genetic programming for information retrieval // Inf. Process. Manage. - 2004. Vol. 40, no. 4. Pp. 587-602.

Алгоритм порождения суперпозиций.

• • Рудой Г.И., Стрижов В.В. / Алгоритмы индуктивного порождения суперпозиций для аппроксимации измеряемых данных // Информатика и её применения, 2013, 7(1) — 17-26

• Базовой алгоритм: В данный момент используется генетический алгоритм MVR порождения моделей с простым удалением всех моделей, имеющих избыточную сложность.

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

• Новизна: На данный момент известно два наиболее продуктивных подхода к поиску ранжирующей функции: переборный и генетический алгоритм. Переборный алгоритм [Goswami et al., 2014] находит структурно-простую ранжирующую функцию и гарантирует ее оптимальность в небольшом множестве функций (на данный момент просмотрены функции структурной сложности не более 8). Генетический алгоритм [Fan et. al., 2004] работает заметно быстрее, но находимые им функции неинтерпретируемы и заметно переусложнены. В настоящей работе предлагается использовать регуляризатор для контроля структурной сложности модели и метрику для ускорения сходимости. Цель: ускорить алгоритм в работе [Goswami et al., 2014], получить те же результаты на структурно простых моделях, показать их устойчивость относительно начального приближения и исследовать структурно более сложные функции.

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

• Задача:

  Дано: две размеченные выборки объектов двух классов. Первая выборка эталонная, вторая содержит неизвестную долю выбросов — объектов с неверной классификацией.

  Найти: вычислительно эффективный способ очистки второй выборки от выбросов.

  Критерий: возрастание 10-fold CV AUC при пополнении первой обучающей выборки отфильтрованной второй выборкой.

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

• Литература:
  1. Успенский В. М. Информационная функция сердца // Клиническая медицина, 2008. — Т. 86, № 5. — С. 4–13.
  2. Успенский В. М. Информационная функция сердца. Теория и практика диагностики заболеваний внутренних органов методом информационного анализа электрокардиосигналов. — М.: «Экономика и информация», 2008. — 116 с.
  3. Chandola V. [at al.] Outlier detection: A Survey // ACM Computing Surveys. – July 2009. – V. 41(3), N 15.
  4. Singh K. [at al.] Outlier Detection: Applications And Techniques // International Journal of Computer Science Issues. – January 2012. – V. 9(1), N 3

• Базовый алгоритм: Пополнение обучающей выборки всеми объектами второй выборки с отступами не менее заданного порога. Ссылка.

• Решение: Для пополнения первой выборки объектами второй выборки предлагается метод сближения ROC-кривых — жадный алгоритм, исключающий объекты второй выборки так, чтобы минимизировать расстояние между ROC-кривой обучающей подвыборки первой выборки и ROC-кривой второй выборки. Также предлагается рассмотреть различные модификации данного метода.

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

3. Применение Deep Learning в задаче информационного анализа ЭКГ-сигналов

• Задача: Решается задача диагностики заболеваний внутренних органов человека по его электрокардиограмме. Задача состоит из двух последовательных этапов: обработки исходных сигналов, включающей в себя построение признакового описания кардиограмм, и их классификации по полученным векторам признаков. В роли функционалов качества в данной задаче выступают AUC, FPR и FNR.

• Данные: Выборка представляет собой множество электрокардиограмм с диагнозами по 14 заболеваниям. Каждая кардиограмма задается вектором, элементами которого являются пары интервал-амплитуда.

• Литература:
  • Успенский В. М. Информационная функция сердца. Теория и практика диагностики заболеваний внутренних органов методом информационного анализа электрокардиосигналов. — М.: «Экономика и информация», 2008. — 116 с.
  • Uspenskiy V.M., Vorontsov K. V., Tselykh V. R., Bunakov V.A. Information Function of the Heart: Discrete and Fuzzy Encoding of the ECG-Signal for Multidisease Diagnostic System. In: Advanced Mathematical and Computational Tools in Metrology – AMCTM 2014
  • Bengio Y., Courville A., Vincent P. Representation Learning: A Review and New Perspectives. In: IEEE Transactions on Pattern Analysis & Machine Intelligence, vol.35, no. 8, pp. 1798-1828, 2013
  • Geoffrey E. Hinton. A Practical Guide to Training Restricted Boltzmann Machines. In: Neural Networks: Tricks of the Trade, рp. 599-619, 2012

• Базовой алгоритм: Ручное выделение признаков с последующим применением наивного байесовского классификатора.

• Решение: Предлагается использовать Deep Learning для выделения признаков из исходных электрокардиограмм. В качестве базовых алгоритмов рассматриваются автоэнкодеры, ограниченные машины больцмана и сверточные нейронные сети. Для решения поставленной задачи используется суперпозиция данных алгоритмов. Для улучшения качества обучения предлагается ряд эвристик.

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

4. Применение коллаборативный фильтрации и активного обучения в задаче выделения селекторов

• Задача:

Дано: Результат A/B-тестирования каждого пользователя Найти: Множество селекторов минимальной мощности, при котором результат голосования принадлежит доверительному интервалу Критерий: Фактор мощности множества селекторов

• Данные: Результат A/B-тестирования и навигационная корреляция

• Литература:
  1. Benjamin Marlin, Collaborative filtering: a machine learning perspective. // Thesis for the degree of Master of Science Graduate Department of Computer Science University of Toronto
  2. Subhagata Chattopadhyay, Similarity based clustering // Computing and Informatics, Vol. 30, 2011, 701–720
  3. Ilham Esslimani, Armelle Brun, Anne Boyer. A collaborative filtering approach combining clustering and navigational based correlation // Universite ́ Nancy2, LORIA, 2008

• Базовой алгоритм: Косинус угла между векторами объектов / пользователей. FLAME-кластеризация.

• Решение: Сначала определяются параметры суперпозиции, экспертно заданных признаков близости пользователей. Далее пользователи разбиваются на кластеры при помощи FLAME кластеризации.

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

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

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

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

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

6. Обнаружение взаимосвязанности временных рядов

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

• Данные: Синтетические данные, исторические биржевые цены на основные инструменты и данные по железнодорожным грузоперевозкам.

• Литература:

Описание алгоритма ССМ

• • G. Sugihara, R.M. May. Nonlinear forecasting as a way of distinguishing chaos from measurement error in time series
  • George Sugihara et al. Detecting Causality in Complex Ecosystems. Science 338, 496 (2012)

Рассмотрение различных алгоритмов для обнаружения связаности рядов

• • Вальков А.С., Кожанов Е.М., Мотренко А.П., Хусаинов Ф.И. Построение кросс-корреляционных зависимостей при прогнозе загруженности железнодорожного узла // Машинное обучение и анализ данных. 2013. T. 1, № 5. C. 505-518.

• Базовой алгоритм: Алгоритм сходящегося перекрестного отображения (Convergent Cross Mapping, CCM)

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

• Новизна: Предложены различные структуры связей между временными рядами и метод проверки наличия связей

7. EVERGREEN: Spatial join-oriented data structure

• Задача: Given a dataset with objects from 3D space that belong to two classes. Find a list of pairs of objects, where each pair contains objects from both classes and the distance between objects in one pair is less then epsilon.
• Данные: Generated dataset with different sizes, shapes and distances of objects and a dataset from BlueGene project of spatial destination of axons and dendrites of mouse's brain.
• Литература:
  1. Sadegh Nobari, Panagiotis Karras et al., TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning, ACM SIGMOD’13 – main article, the description of base algorithm for parallelization
  2. Thoinus Brinkhoff et al., Efficient Processing of Spatial Joins Using R-trees, SIGMOD’93 – some basic principles of R-trees
  3. Ibrahim Kamel, Parallel R-trees, SIGMOD’92 – the implementation of parallel R-trees
  4. Scott T. Leutenegger, STR: A SIMPLE AND EFFICIENT ALGORITHM FOR R-TREE PACKING, ICASE report 97-14 – description of R-tree boosting, fast creating of tree from known set of data (building from the bottom)
  5. CUDA C BEST PRACTICES GUIDE – manual for GPU API
• Базовый алгоритм: EVERGREEN dTree, reTree, cTree.
• Решение New algorithm for spatial join was developed with 3 different modifications. Each of them outperforms all others best solutions for mentioned problem.
• Новизна The problem is well developed for disk-based approached. We develop state-of-the-art in-memory approach that is based of the assumption that whole built data structure can be placed in fast RAM memory.

Примечания