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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Шаблон научной статьи)
Строка 300: Строка 300:
* '''Решение:''' Модифицировать алгоритм, описанный в статье [2], используя алгоритм построения триангуляции для многоугольников, описанный в [1].
* '''Решение:''' Модифицировать алгоритм, описанный в статье [2], используя алгоритм построения триангуляции для многоугольников, описанный в [1].
* '''Новизна:''' На данный момент являются известными понятия коллекция бициклов и триангуляция Делоне, однако алгоритмы построения триангуляций Делоне для коллекций бициклов имеют квадратичную сложность (в рассматриваемом худшем случае). Целью работы является предложить алгоритм, сложность которого можно оценить как <tex>O(n \log n)</tex>
* '''Новизна:''' На данный момент являются известными понятия коллекция бициклов и триангуляция Делоне, однако алгоритмы построения триангуляций Делоне для коллекций бициклов имеют квадратичную сложность (в рассматриваемом худшем случае). Целью работы является предложить алгоритм, сложность которого можно оценить как <tex>O(n \log n)</tex>
 +
 +
=== Автор: Яшков Даниил ===
 +
* '''Название:''' Прогнозирование сильно разреженных временных рядов.
 +
* '''Задача:''' В работе решается задача прогнозирования группы разреженных временных рядов.
 +
* '''Данные:''' Используются реальные данные по продажам запчастей самолетов.
 +
* '''Литература: '''
 +
1. Downing, M., Chipulu, M., Ojiako, U and Kaparis, D (2011),
 +
―Forecasting in airforce supply chains‖, The International Journal of
 +
Logistics Management, Vol. 22, No. 1, pp 127-144.
 +
 +
 +
2. C Hiemstra, JD Jones - The Journal of Finance, 1994 - Wiley Online Library.
 +
* '''Решение:''' Поскольку из-за сильной разреженности рядов их невозможно прогнозировать отдельно, предлагается следующий подход: выделить группы рядов, которые зависимы между собой по Грейнджеру. Далее прогноз делать в каждой группе отдельно: прогнозируем агрегированный временной ряд в каждой группе(например сумму всех рядов). Получаем прогнозы каждого из временных рядов, дизагрегируя его с учетом найденных связей.

Версия 21:18, 24 февраля 2014


Результаты

Автор Тема научной работы Руководитель Лекции Буквы Оценка
Бунаков Василий 0,0
Вдовина Евгения 0,2(3)
Воронов Сергей Фильтрация и тематическое моделирование коллекции научных документов Воронцов К.В. 8(8),3(3)
Гринчук Олег 0,3(3)
Дубовик Анна 0,0
Желавская Ирина 3(4),2(3)
Жуйков Владимир 3(7),2(2)
Иванов Александр Коалиционная манипулируемость правил коллективного выбора 5(6),3(3)
Касаткин Сергей 2(4),0
Катруца Александр Тестирование алгоритмов выбора признаков Стрижов В.В. 8(8),3(3)
Костин Александр Эффективный алгоритм построения триангуляции Делоне коллекции бициклов Местецкий Л.М. 0,2(2)
Котенко Ленгольд Екатерина 0,02
Кудряшова Александра 4(5),0
Левдик Павел 0,0
Матросов Михаил Short-term forecasting of musical compositions using chord sequences 5(6),1(2)
Митяшов Андрей 0,0
Неклюдов Кирилл 0,2(2)
Перекрестенко Дмитрий 0,0
Прилепский Роман 0,1(2)
Пушняков Алексей Комбинаторные оценки \varepsilon-разбиений метрических пространств Рудаков К.В. 8(8),2(3)
Рыскина Мария Регуляризация вероятностных тематических моделей для повышения устойчивости и интерпретируемости Воронцов К.В. 0,3(3)
Уржумцев Олег 0,0
Фейзханов Рустем Обработка видео и распознавание текста для видеоконференций 2(6),3(3)
Шуйский Николай 5(6),2(3)
Яшков Даниил 0,0
Иванов Сергей 0,0
Колчанов Андрей 0,0


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

Задание 1, к 25 февраля

  1. Посоветоваться с научным руководителем и заполнить шаблон — план научной раборы (работа в течение семестра, дипломная работа или статья — вам решать).
  2. Поместить полученный план на эту страницу.
  3. Пользуясь материалами лекций (текст, слайды, слайды) и материалами курса Теория обучения машин, написать постановку вашей задачи в формате эссе. Ожидаемый размер эссе — полстраницы. Постановка задачи должна содержать строку \arg\min.
  4. Использовать шаблон вместе со стилевым файлом. См. результат PDF.
  5. Загрузить полученный текст на сайт SourceForge: MLAlgorithms/Group074/, создав папку Surname2014Title/ (где Title — ключевое слово в названии научной работы), в файлы Surname2014Essay1.tex и pdf.
  • Примечание. Те, кто пишут статью, могут держать в течение семестра один файл с именем статьи. Сихронизация ДЗ будет происходить с третьим курсом.
  • Важно! Те, кто не нашли научных руководителей, напишите предполагаемым/желаемым руководителям или напишите представителям Сколково/Кафедры.

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

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


Автор: Пушняков Алексей

  • Название: О комбинаторных оценках максимальных \varepsilon-разбиений метрических конфигураций.
  • Задача: Дано метрическое пространство (X,\rho),\; |X| < \infty. Пусть выбран некоторый порог \varepsilon, известно, что из всех {|X| \choose 2} попарных расстоянии таких, которые больше \eps, мало. Формально,
|\Lambda_{\eps}| =  |\left\{(x,y):\; \rho(x,y) > \eps \right\}| \leq \frac{\delta |X|^2}{2},

где \delta > 0 - некоторое число, а пары (x,y) мы считаем неупорядоченными. Требуется определить некоторый новый порог \eps' такой, чтобы значительная часть точек пространства попала в некоторое множество диаметра не более \eps'. Иначе говоря, требуется найти гарантированную оценку снизу на мощность максимального множества диаметра не более \eps'.

  • Решение: Вначале показывается, что в случае \varepsilon' < 2\varepsilon нельзя гарантировать какую-либо линейную по мощности пространства оценку. Поэтому останавливаемся на случае \varepsilon' \geq 2\varepsilon. Далее жадным образом строится разбиение пространства на подмножества диаметра не более \varepsilon', и рассматриваются некоторые свойства этого разбиения (здесь существенно применяется лемма Холла). Особый интерес представляет первое подмножество разбиения  X_0 , так его мощность и требуется оценить. Вместо непосредственно мощности  X_0 предлагается оценить число длинных ребер (их длина больше \varepsilon). Центральным утверждением является факт, что таких ребер не менее  |X_0|\cdot|X\setminus X_0| . Доказательство основано на рассмотрении максимального паросочетания в некотором двудольном подграфе с долями X_0 и X\setminus X_0.
  • Литература:

1. Hall P. On representatives of subsets //J. London Math. Soc. – 1935. – Т. 10. – №. 1. – С. 26-30.

2. А. С. Вальков, “О быстром алгоритме восстановления иерархической ε-кластерной структуры”, Ж. вычисл. матем. и матем. физ., 45:1 (2005), 170–179.

Автор: Катруца Александр

  • Название: Проблема мультиколлинеарности при выборе признаков в регрессионных задачах
  • Задача: Исследовать свойства алгоритмов выбора признаков на предмет их адекватности при работе с выборками, содержащими мультиколлинеарные признаки.
  • Данные: набор синтетических выборок, сгенерированных в соответствии с введёнными параметрами мультиколлинеарности и количества признаков каждого типа.
  • Литература:

1. Il-Gyo Chong and Chi-Hyuck Jun. Performance of some variable selection methods when multicollinearity is present. Chemometrics and Intelligent Laboratory Systems, 78(1–2):103 – 112, 2005.

2. Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58:267–288, 1994.

3. Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. Least angle regression. Ann. Statist, pages 407–499, 2004.

4. Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society, Series B, 67:301–320, 2005.

  • Базовые алгоритмы: LARS, Lasso, Elastic Net, Stepwise regression.
  • Решение: генерировать целевые векторы и выборки с заранее определённым взаимным расположением признаков (ортогональность, коллинеарность, случайность и т.д.) и запускать на них алгоритмы выбора признаков. Оценивать качество предлагается несколькими функионалами: VIF, adjusted R^2, C_p и др. Также предлагается исследовать зависимость качества от параметра мультиколлинеарности.

Автор: Рыскина Мария

  • Название: Регуляризация вероятностных тематических моделей для повышения устойчивости и интерпретируемости
  • Задача: Исследовать влияние регуляризации на устойчивость и интерпретируемость моделей для модельных и реальных данных (см. эссе). Проверить гипотезу: регуляризация делает модель более интерпретируемой.
  • Данные: Модельные данные; коллекция тезисов конференции ММРО/IOI.
  • Литература:

1. Воронцов К. В., Потапенко А. А. Регуляризация, робастность и разреженность вероятностных тематических моделей //Компьютерные исследования и моделирование. – 2012. – Т. 4. – №. 4. – С. 693-706.

2. Chang J. et al. Reading Tea Leaves: How Humans Interpret Topic Models //NIPS. – 2009. – Т. 22. – С. 288-296.

  • Базовый алгоритм: PLSA-EM
  • Решение:

1. Для модельных данных: генерируются разреженные выходные матрицы, по ним восстанавливается входная и строится модель (стандартная и регуляризованная). Между темами в полученных моделях и в исходной матрице находятся взаимно-однозначные соответствия (венгерский алгоритм). Вычисляется значение введённого критерия качества интерпретируемости (см. эссе).

2. Для реальных данных: тот же эксперимент, но по-другому ищутся соответствия: строятся модели для разных начальных приближений и на всех полученных темах производится иерархическая кластеризация. Предполагается измерять интерпретируемость с помощью асессоров.

Автор: Уржумцев Олег

  • Название: Исследование поведения аддитивной регуляризованной тематической модели при добавлении темпоральных признаков
  • Задача: Максимизация когеретности тематик путём настройки параметров аддитивной регуляризованной тематической модели с включёнными темпоральными признаками.

Модель отличается от стандартной pLSA наличием дополнительных матриц $\Psi$ и $\Xi$:  \ln \prod_{d\in D}\prod_{w\in d} p(w,c,y | d)^{n_{dw}} &= \sum_{d,w} n_{dw} \ln \sum_t \phi_{wt} \theta_{td} + {}\\&+ \tau_C \sum_{d} n_{d} \ln \sum_t \psi_{c_d t} \theta_{td} + {}\\&+ \tau_Y \sum_{d} n_{d} \ln \sum_t \xi_{y_d t} \theta_{td} \;\to\; \max_{\Phi,\Theta,\Psi,\Xi}

Для оценки качества применяется мера когерентности тематик, вернее, логарифм условной вероятности (log conditional probability, LCP) - метрика, оценивающая вероятность появления менее частого слова в тематике при условии появления более частого: \[    \mathrm{LCP} (t)    =    \sum_{i=1}^{k-1} \sum_{j=i}^k        \log \frac{N(w_i,w_j)}{N(w_i)},\]

  • Решение: Вначале показывается, что в случае \varepsilon' < 2\varepsilon нельзя гарантировать какую-либо линейную по мощности пространства оценку. Поэтому останавливаемся на случае \varepsilon' \geq 2\varepsilon. Далее жадным образом строится разбиение пространства на подмножества диаметра не более \varepsilon', и рассматриваются некоторые свойства этого разбиения (здесь существенно применяется лемма Холла). Особый интерес представляет первое подмножество разбиения  X_0 , так его мощность и требуется оценить. Вместо непосредственно мощности  X_0 предлагается оценить число длинных ребер (их длина больше \varepsilon). Центральным утверждением является факт, что таких ребер не менее  |X_0|\cdot|X\setminus X_0| . Доказательство основано на рассмотрении максимального паросочетания в некотором двудольном подграфе с долями X_0 и X\setminus X_0.

Автор: Неклюдов Кирилл

  • Название: Facial keypoints detection.
  • Задача: В работе решается задача нахождения ключевых точек лица человека на изображении. Координаты ключевых точек представляются в виде дерева. Для построения дерева используется минимизация "энергии". "Энергия" вершин и рёбер дерева находятся из распределения вероятностей, параметры которого в свою очередь обучаются из принципа максимального правдоподобия. Координаты точек находятся как аргументы плотностей распределения, на которых функция принимает максимальное значение.
  • Данные: Обучающая выборка с отмеченными ключевыми точками сожержит 7000 чёрно-белых фотографий лиц разрешением 96х96.
  • Литература:

1. P.F. Felzenszwalb and D.P. Huttenlocher. Pictorial structures for object recognition. International Journal of computer vision, 61(1):55-79, January 2005.

2. Rajesh P.N. Rao and Dana H. Ballard. An active vision architecture based on iconic representations. Elsevier Science, March 1995.

  • Базовый алгоритм: Алгоритм минимизации энергии описанный в статье P.F. Felzenszwalb and D.P. Huttenlocher. Pictorial structures for object recognition.
  • Решение: Помимо реализации базового алгоритма предлагается предварительная обработка фотографий с помощью Гауссовского фильтра. Оптимальный размер фильтра выбирается исходя из минимизации функционала: \textrm{RMSE} = \sqrt{\frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2}.

Автор: Костин Александр

  • Название: Эффективный алгоритм построения триангуляции Делоне коллекции бициклов.
  • Задача: Рассматривается задача построения триангуляции Делоне коллекции бициклов. Для проверки условия Делоне предлагается использовать геометрию Лагерра.
  • Данные: Модельные данные: коллекции бициклов.
  • Литература:

1. Л.М. Местецкий, Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. // Москва, Физматлит, 2009.

2. Матвеева Д.С., Триангуляции Делоне коллекции бициклов (дипломная работа)// Москва, ВМК МГУ, 2013

  • Базовый алгоритм: Решение основано на алгоритме построения триангуляции, описанное в [2].
  • Решение: Модифицировать алгоритм, описанный в статье [2], используя алгоритм построения триангуляции для многоугольников, описанный в [1].
  • Новизна: На данный момент являются известными понятия коллекция бициклов и триангуляция Делоне, однако алгоритмы построения триангуляций Делоне для коллекций бициклов имеют квадратичную сложность (в рассматриваемом худшем случае). Целью работы является предложить алгоритм, сложность которого можно оценить как O(n \log n)

Автор: Яшков Даниил

  • Название: Прогнозирование сильно разреженных временных рядов.
  • Задача: В работе решается задача прогнозирования группы разреженных временных рядов.
  • Данные: Используются реальные данные по продажам запчастей самолетов.
  • Литература:

1. Downing, M., Chipulu, M., Ojiako, U and Kaparis, D (2011), ―Forecasting in airforce supply chains‖, The International Journal of Logistics Management, Vol. 22, No. 1, pp 127-144.


2. C Hiemstra, JD Jones - The Journal of Finance, 1994 - Wiley Online Library.

  • Решение: Поскольку из-за сильной разреженности рядов их невозможно прогнозировать отдельно, предлагается следующий подход: выделить группы рядов, которые зависимы между собой по Грейнджеру. Далее прогноз делать в каждой группе отдельно: прогнозируем агрегированный временной ряд в каждой группе(например сумму всех рядов). Получаем прогнозы каждого из временных рядов, дизагрегируя его с учетом найденных связей.
Личные инструменты