Численные методы обучения по прецедентам (практика, В.В. Стрижов)/Группа 074, весна 2014
Материал из MachineLearning.
(Различия между версиями)
Строка 203: | Строка 203: | ||
|} | |} | ||
- | |||
- | + | == Домашние задания == | |
+ | === Задание 1, к 25 февраля === | ||
+ | # Посоветоваться с научным руководителем и заполнить шаблон — план научной раборы (работа в течение семестра, дипломная работа или статья — вам решать). | ||
+ | # Поместить полученный план на эту страницу. | ||
+ | # Пользуясь материалами лекций ([http://sourceforge.net/p/mvr/code/HEAD/tree/lectures/Strijov2014ModelSelection1ch.pdf текст], [слайды http://sourceforge.net/p/mvr/code/HEAD/tree/lectures/Part1%60DataGeneration.pdf?format=raw], [http://sourceforge.net/p/mvr/code/HEAD/tree/lectures/Part3%60ProblemStatement.pdf?format=raw слайды]) и материалами курса [[Теория обучения машин]], написать постановку вашей задачи в формате эссе. Ожидаемый размер эссе — полстраницы. Постановка задачи должна содержать строку <tex>\arg\min</tex>. | ||
+ | # Использовать [http://sourceforge.net/p/mlalgorithms/code/HEAD/tree/Group074/Kuznetsov2013SSAForecasting/doc/Surname2013Essay1.tex?format=raw шаблон] вместе со [http://sourceforge.net/p/mlalgorithms/code/HEAD/tree/Group074/Kuznetsov2013SSAForecasting/doc/jmlda.sty?format=raw стилевым файлом]. См. результат [http://sourceforge.net/p/mlalgorithms/code/HEAD/tree/Group074/Kuznetsov2013SSAForecasting/doc/Surname2013Essay1.pdf?format=raw PDF]. | ||
+ | # Загрузить полученный текст на сайт SourceForge: MLAlgorithms/Group074, создав папку Surname2014Title (где Title -- ключевое слово в названии научной работы), в файлы Surname2014Essay1.tex и pdf. | ||
+ | * '''Примечание.''' Те, кто пишут статью, могут держать в течение семестра один файл с именем статьи. Сихронизация ДЗ будет происходить с третьим курсом. | ||
+ | * '''Важно!''' Те, кто не нашли научных руководителей, напишите предполагаемым/желаемым руководителям или напишите представителям Сколково/Кафедры. | ||
- | |||
- | * Данные: Краткое описание данных, используемых в вычислительном эксперименте, и ссылка на выборку. | + | == Шаблон научной статьи == |
+ | * '''Название:''' Название, под которым статья подается в журнал. | ||
+ | * '''Задача:''' Описание или постановка задачи. Желательна постановка в виде задачи оптимизации (в формате argmin). Также возможна ссылка на классическую постановку задачи. | ||
+ | * '''Данные:''' Краткое описание данных, используемых в вычислительном эксперименте, и ссылка на выборку. | ||
+ | * '''Литература:''' Список научных работ, дополненный 1) формулировкой решаемой задачи, 2) ссылками на новые результаты, 3) основной информацией об исследуемой проблеме. | ||
+ | * '''Базовой алгоритм:''' Ссылка на алгоритм, с которым проводится сравнение или на ближайшую по теме работу. | ||
+ | * '''Решение:''' Предлагаемое решение задачи и способы проведения исследования. Способы представления и визуализации данных и проведения анализа ошибок, анализа качества алгоритма. | ||
+ | * '''Новизна:''' Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала). | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
+ | === Автор: Пушняков Алексей === | ||
* Название: О комбинаторных оценках максимальных <tex>\varepsilon</tex>-разбиений метрических конфигураций. | * Название: О комбинаторных оценках максимальных <tex>\varepsilon</tex>-разбиений метрических конфигураций. | ||
- | |||
* Задача: Дано метрическое пространство <tex>(X,\rho),\; |X| < \infty</tex>. Пусть выбран некоторый порог <tex>\varepsilon</tex>, известно, что из всех <tex>{|X| \choose 2}</tex> попарных расстоянии таких, которые больше <tex>\eps</tex>, ''мало''. Формально, | * Задача: Дано метрическое пространство <tex>(X,\rho),\; |X| < \infty</tex>. Пусть выбран некоторый порог <tex>\varepsilon</tex>, известно, что из всех <tex>{|X| \choose 2}</tex> попарных расстоянии таких, которые больше <tex>\eps</tex>, ''мало''. Формально, | ||
: <tex>|\Lambda_{\eps}| = |\left\{(x,y):\; \rho(x,y) > \eps \right\}| \leq \frac{\delta |X|^2}{2},</tex> | : <tex>|\Lambda_{\eps}| = |\left\{(x,y):\; \rho(x,y) > \eps \right\}| \leq \frac{\delta |X|^2}{2},</tex> | ||
Строка 229: | Строка 232: | ||
Требуется определить некоторый новый порог <tex>\eps'</tex> такой, чтобы ''значительная'' часть точек пространства попала в некоторое множество диаметра не более <tex>\eps'</tex>. | Требуется определить некоторый новый порог <tex>\eps'</tex> такой, чтобы ''значительная'' часть точек пространства попала в некоторое множество диаметра не более <tex>\eps'</tex>. | ||
Иначе говоря, требуется найти гарантированную оценку снизу на мощность максимального множества диаметра не более <tex>\eps'</tex>. | Иначе говоря, требуется найти гарантированную оценку снизу на мощность максимального множества диаметра не более <tex>\eps'</tex>. | ||
- | |||
* Решение: Вначале показывается, что в случае <tex>\varepsilon' < 2\varepsilon</tex> нельзя гарантировать какую-либо линейную по мощности пространства оценку. Поэтому останавливаемся на случае <tex>\varepsilon' \geq 2\varepsilon</tex>. Далее жадным образом строится разбиение пространства на подмножества диаметра не более <tex>\varepsilon'</tex>, и рассматриваются некоторые свойства этого разбиения (здесь существенно применяется лемма Холла). Особый интерес представляет первое подмножество разбиения <tex> X_0 </tex>, так его мощность и требуется оценить. Вместо непосредственно мощности <tex> X_0 </tex> предлагается оценить число ''длинных'' ребер (их длина больше <tex>\varepsilon</tex>). Центральным утверждением является факт, что таких ребер не менее <tex> |X_0|\cdot|X\setminus X_0| </tex>. Доказательство основано на рассмотрении максимального паросочетания в некотором двудольном подграфе с долями <tex>X_0</tex> и <tex>X\setminus X_0</tex>. | * Решение: Вначале показывается, что в случае <tex>\varepsilon' < 2\varepsilon</tex> нельзя гарантировать какую-либо линейную по мощности пространства оценку. Поэтому останавливаемся на случае <tex>\varepsilon' \geq 2\varepsilon</tex>. Далее жадным образом строится разбиение пространства на подмножества диаметра не более <tex>\varepsilon'</tex>, и рассматриваются некоторые свойства этого разбиения (здесь существенно применяется лемма Холла). Особый интерес представляет первое подмножество разбиения <tex> X_0 </tex>, так его мощность и требуется оценить. Вместо непосредственно мощности <tex> X_0 </tex> предлагается оценить число ''длинных'' ребер (их длина больше <tex>\varepsilon</tex>). Центральным утверждением является факт, что таких ребер не менее <tex> |X_0|\cdot|X\setminus X_0| </tex>. Доказательство основано на рассмотрении максимального паросочетания в некотором двудольном подграфе с долями <tex>X_0</tex> и <tex>X\setminus X_0</tex>. |
Версия 13:51, 22 февраля 2014
Результаты
Автор | Тема научной работы | Руководитель | Лекции | Буквы | Оценка |
---|---|---|---|---|---|
Бунаков Василий… | 0 | ||||
Вдовина Евгения | 0 | ||||
Воронов Сергей | Фильтрация и тематическое моделирование коллекции научных документов | Воронцов К.В. | 8(8) | ||
Гринчук Олег | 0 | ||||
Дубовик Анна | 0 | ||||
Желавская Ирина | 3(4) | ||||
Жуйков Владимир | 3(7) | ||||
Иванов Александр | Коалиционная манипулируемость правил коллективного выбора | 5(6) | |||
Касаткин Сергей | 2(4) | ||||
Катруца Александр | Тестирование алгоритмов выбора признаков | 8(8) | |||
Костин Александр | Эффективный алгоритм построения триангуляции Делоне коллекции бициклов | Местецкий Л.М. | 0 | ||
Котенко Ленгольд Екатерина | 0 | ||||
Кудряшова Александра | 4(5) | ||||
Левдик Павел | 0 | ||||
Матросов Михаил | Short-term forecasting of musical compositions using chord sequences | 5(6) | |||
Митяшов Андрей | 0 | ||||
Неклюдов Кирилл | 0 | ||||
Перекрестенко Дмитрий | 0 | ||||
Прилепский Роман | 0 | ||||
Пушняков Алексей | Комбинаторные оценки -разбиений метрических пространств | Рудаков К.В. | 8(8) | ||
Рыскина Мария | Регуляризация вероятностных тематических моделей для повышения устойчивости и интерпретируемости | Воронцов К.В. | 0 | ||
Уржумцев Олег | 0 | ||||
Фейзханов Рустем | Обработка видео и распознавание текста для видеоконференций | 2(6) | |||
Шуйский Николай | 5(6) | ||||
Яшков Даниил | 0 | ||||
Иванов Сергей | 0 | ||||
Колчанов Андрей | 0 |
Домашние задания
Задание 1, к 25 февраля
- Посоветоваться с научным руководителем и заполнить шаблон — план научной раборы (работа в течение семестра, дипломная работа или статья — вам решать).
- Поместить полученный план на эту страницу.
- Пользуясь материалами лекций (текст, [слайды http://sourceforge.net/p/mvr/code/HEAD/tree/lectures/Part1%60DataGeneration.pdf?format=raw], слайды) и материалами курса Теория обучения машин, написать постановку вашей задачи в формате эссе. Ожидаемый размер эссе — полстраницы. Постановка задачи должна содержать строку .
- Использовать шаблон вместе со стилевым файлом. См. результат PDF.
- Загрузить полученный текст на сайт SourceForge: MLAlgorithms/Group074, создав папку Surname2014Title (где Title -- ключевое слово в названии научной работы), в файлы Surname2014Essay1.tex и pdf.
- Примечание. Те, кто пишут статью, могут держать в течение семестра один файл с именем статьи. Сихронизация ДЗ будет происходить с третьим курсом.
- Важно! Те, кто не нашли научных руководителей, напишите предполагаемым/желаемым руководителям или напишите представителям Сколково/Кафедры.
Шаблон научной статьи
- Название: Название, под которым статья подается в журнал.
- Задача: Описание или постановка задачи. Желательна постановка в виде задачи оптимизации (в формате argmin). Также возможна ссылка на классическую постановку задачи.
- Данные: Краткое описание данных, используемых в вычислительном эксперименте, и ссылка на выборку.
- Литература: Список научных работ, дополненный 1) формулировкой решаемой задачи, 2) ссылками на новые результаты, 3) основной информацией об исследуемой проблеме.
- Базовой алгоритм: Ссылка на алгоритм, с которым проводится сравнение или на ближайшую по теме работу.
- Решение: Предлагаемое решение задачи и способы проведения исследования. Способы представления и визуализации данных и проведения анализа ошибок, анализа качества алгоритма.
- Новизна: Обоснование новизны и значимости идей (для редколлегии и рецензентов журнала).
Автор: Пушняков Алексей
- Название: О комбинаторных оценках максимальных -разбиений метрических конфигураций.
- Задача: Дано метрическое пространство . Пусть выбран некоторый порог , известно, что из всех попарных расстоянии таких, которые больше , мало. Формально,
где - некоторое число, а пары мы считаем неупорядоченными. Требуется определить некоторый новый порог такой, чтобы значительная часть точек пространства попала в некоторое множество диаметра не более . Иначе говоря, требуется найти гарантированную оценку снизу на мощность максимального множества диаметра не более .
- Решение: Вначале показывается, что в случае нельзя гарантировать какую-либо линейную по мощности пространства оценку. Поэтому останавливаемся на случае . Далее жадным образом строится разбиение пространства на подмножества диаметра не более , и рассматриваются некоторые свойства этого разбиения (здесь существенно применяется лемма Холла). Особый интерес представляет первое подмножество разбиения , так его мощность и требуется оценить. Вместо непосредственно мощности предлагается оценить число длинных ребер (их длина больше ). Центральным утверждением является факт, что таких ребер не менее . Доказательство основано на рассмотрении максимального паросочетания в некотором двудольном подграфе с долями и .