Пробные задачи

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

(Различия между версиями)
Перейти к: навигация, поиск
(Задача 2)
Текущая версия (12:08, 29 декабря 2023) (править) (отменить)
м (Задача 58)
 
(137 промежуточных версий не показаны.)
Строка 1: Строка 1:
 +
__NOTOC__
{{Main|Численные методы обучения по прецедентам (практика, В.В. Стрижов)}}
{{Main|Численные методы обучения по прецедентам (практика, В.В. Стрижов)}}
-
* Короткая ссылка [http://bit.ly/1B4NKjZ bit.ly/1B4NKjZ]
+
{{Main|Интеллектуальные системы (кафедра МФТИ)/Прием студентов}}
-
* Решения задач, работы студентов, [http://sourceforge.net/p/mlalgorithms/code/HEAD/tree/GroupYAD/Example2015Code/ пример].
+
* Короткая ссылка на эту страницу [http://bit.ly/IS-prob bit.ly/IS-prob]
 +
'''Советы по решению задач''' (это просто советы, а не указания)
 +
* Теоретическое решение важнее практического.
 +
* Пишите теорию сами (не копируйте материал лекций).
 +
* Визуализируйте решение задач (рисунок от руки предпочтительнее его отсутствия).
 +
* Результаты эксперимента выносите на слайды (не показывайте pynb).
 +
* При обсуждении нейросетей учтите, что они для нас — не черные ящики, а прозрачные.
 +
* Берите эти, или прошлые, или свои задачи – что вам самим интересно.
-
=== Задача 1===
+
== Осень 2023 (можно использовать не только эти задачи, но и задачи прошлых лет) ==
-
Классифицировать [http://archive.ics.uci.edu/ml/datasets/Credit+Approval|заемщиков кредита] с помощью [[Логистическая регрессия|логистической регрессии]]. Для оптимизации параметров использовать алгоритм [[Логистическая регрессия (пример)|Ньютона-Рафсона]] или алгоритм [[Метод градиентного спуска|градиентного спуска]]. Построить ROC-кривые для фиксированного числа разбиений. Построить ряд графиков для различных мощностей подвыборок разбиений.
+
===Задачи 54-64===
-
Число итераций ограничить либо условием на сходимость – норма разности последовательных векторов весов не больше точности, либо числом шагов.
+
Скоро будут, пока используйте задачи прошлых лет или показывайте свои.
-
===Задача 2===
+
== Задача 54 ==
-
Нарисовать траекторию пошагового спуска к минимуму [|градиентного метода] и [[Алгоритм имитации отжига|имитации отжига]]. Сравнить их работу при поиске мимимума [[Media: SCHWEFEL.pdf|тестовой функции]].
+
Найти задачу из [https://arxiv.org/abs/2206.13446 Pen and Paper Exercises in Machine Learning by Michael U. Gutmann] и разобрать ее решение. (И даже проиллюстрировать графиком в коде.)
 +
== Задача 55 ==
 +
В задаче логистической регрессии найти оптимальные параметры модели (любая небольшая выборка под регрессию из UCI, пример из sklearn). Используюя случайные подвыбоки найти ковариацию параметров.
 +
== Задача 56 ==
 +
В задаче автогеррессионного прогнозирования оценить (теоретически), насколько отчетов времени вперед можно сделать прогноз с дисперсией, не превышающей заданную. Дисперсию ошибки и прогноза можно оценить. Нарисовать график с осями "время момента прогноза, дисперсия прогноза".
 +
== Задача 57 ==
 +
Проанализировать компромисс отклонение-дисперсия (bias-variance tradeoff) для случая разных типов распределений (желательно включая мультимодальные), нарисовать иллюстранцию на простых синтетических данных.
 +
== Весна 2022 ==
 +
=== Задача 43===
 +
Для акселерометров двух мобильных телефонов в руке или в кармане во время ходьбы: прогнозировать значения одного по другому (метод partial least squares, canonic correlation analysis). Насколько вырастет ошибка прогноза значений гироскопа по акселерометру? Или значения акселерометра в кармане по значению акселерометра в руке?
 +
=== Задача 44===
 +
Задана выборка для классификации и модель решающего дерева. На случайных подвыборках алгоритм построения дерева, например С 4.5, строит различные деревья. Как можно вычислить расстояние между двумя деревьями? Насколько разные деревья возвращает алгоритм построения дерева? Визуализировать значения функции парного расстояния? Насколько различные деревья возвращает алгоритм построения леса решающих деревьев?
 +
=== Задача 45===
 +
Задана выборка для классификации или для регрессии. На случайных подвыборках оценить матожидание и дисперсию функции ошибки (точность прогноза). Оценить матожидание и ковариации элементов вектора параметров. Как изменяются все эти оценки при 1) снижении объема выборки, 2) снижении сложности модели? Нарисовать графики. Модель – линейная или логистическая регрессия. Сложность – число параметров. (Вариант с нейросетью.)
 +
=== Задача 46===
 +
Задана выборка для метрической классификации (kNN). Как изменится точность классификации при увеличении числа ближайших соседей? На обучении, на контроле? Как найти оптимальное число соседей? Что изменится, если вместо евклидова расстояния использовать расстояние Махаланобиса x'Ax. Как получить оптимальный метрический тензор A?
-
Решение каждой задачи должно быть визуализировано, все рисунки необходимо кратко описать.
+
=== Задача 47===
 +
Показать, что движения конечностей человека адекватно аппроксимируются моделью маятника (если покажете, что системой маятников, вообще замечательно). Модель задана в виде ОДУ, решением ОДУ является интегральная кривая. Требуется снять показания акселерометра и гироскопа своего мобильного телефона, или двух телефонов, в руке, сумке, кармане (это маятник), или найти готовые.
 +
Нарисовать эти показания в фазовом пространстве "скорость-ускорение" или можно построить пространство по другому, на ваш вкус. Решить ОДУ – модель маятника, нарисовать решение ОДУ в том же пространстве. Запустить код Neural ODE, аппроксимировать показания, нарисовать решение в том же пространстве[http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%BF%D1%80%D0%BE%D0%B3%D0%BD%D0%BE%D0%B7%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%28%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B8%2C_%D0%90.%D0%92._%D0%93%D1%80%D0%B0%D0%B1%D0%BE%D0%B2%D0%BE%D0%B9%2C_%D0%92.%D0%92._%D0%A1%D1%82%D1%80%D0%B8%D0%B6%D0%BE%D0%B2%29/%D0%9E%D1%81%D0%B5%D0%BD%D1%8C_2021].
-
# С помощью логистической регрессии разделить два класса точек на плоскости. Результаты изобразить на графиках (см. пример [[Численные методы обучения по прецедентам (практика, В.В. Стрижов)/Примеры| Classification using logistic regression]]). Рассмотреть случаи линейно разделимой и неразделимой выборок.
+
=== Задача 48===
-
# Изобразить на рисунке Парето-расслоение множества точек на плоскости. (Парето-расслоение - набор последовательно вычисляемых Парето оптимальных фронтов. Первый фронт вычисляется для полной выборки и удаляется из нее. Для оставшихся данных вычисляется следующий слой и т.д)
+
Предыдущая задача на следующих даных: по видео маятника часов восстановить и нарисовать фазовое пространство и интегральную кривую решения уравнения маятника. Насколько решение математической модели маятника совпадает с координатами маятника на видео?
-
# Дана выборка [http://archive.ics.uci.edu/ml/datasets/Wine "Вина различных регионов"]. Требуется определить кластеры (регионы происхождения вин) и нарисовать результат: цветной точкой обозначен объект кластера; цветным кружком обозначен класс этого объекта, взятый из выборки. Вариант задания: определить число кластеров. Вариант задания: использовать два алгоритма, например <tex>k</tex>-means и EM, и показать сравнение результатов кластеризации на графике.
+
 
-
# Сгладить временной ряд [[Временной ряд (библиотека примеров)|Цены (объемы) на основные биржевые инструменты]] методом [[Экспоненциальное сглаживание| экспоненциального сглаживания]]. Нарисовать цветные графики сглаженных с различным <tex> \alpha </tex> рядов и исходного ряда.
+
=== Задача 49===
-
# Аппроксимация выборки замкнутой кривой [http://sourceforge.net/p/mlalgorithms/code/HEAD/tree/Group874/Group874Essay/Group874Essay.pdf?format=raw]: проверить, лежат ли точки на окружности? Сгенерировать данные самостоятельно. Построить графики для случая когда точки лежат на окружности и нет, на графиках изобразить выборку и аппроксимирующую окружность.
+
Обосновать и показать на примере почему повышать число слоев нейросети предпочтительнее, с точки зрения точности аппроксимации, чем повышать число нейронов скрытого слоя. Использовать теоремы Колмогорова, Цыбенкова, Ханина: [https://github.com/MarkPotanin/GeneticOpt/blob/master/Potanin2019NNStructure_APX.pdf], см. также [https://www.overleaf.com/read/gmkrtbmwsbsk 1], [https://drive.google.com/file/d/1Wn-CEhDKvjyZMvZdBHWUobxpizVF1G8l/view?usp=sharing 2], [https://drive.google.com/file/d/1_rDG98DlLaBcvlWr2oB_Mo8ksAfYtGL8/view?usp=sharing 3]
-
# Дан временной ряд с пропусками, например [http://archive.ics.uci.edu/ml/datasets/Gas+Sensor+Array+Drift+Dataset+at+Different+Concentrations]. Предложить способы заполнения пропусков в данных, заполнить пропуски. Для каждого способа построить гистограмму. Вариант: взять выборку без пропусков, удалить случайным образом часть данных, заполнить пропуски, сравнить гистограмму восстановленной выборки с гистограммой исходной выборки.
+
 
-
# Дана выборка [http://archive.ics.uci.edu/ml/datasets/Wine "Вина различных регионов"]. Выбрать два признака. Рассмотреть различные функции расстояния при классификации с помощью [[Метод ближайших соседей| метода ближайшего соседа]]. Для каждой изобразить результат классификации в пространстве выбранных признаков.
+
=== Задача 50===
-
# Для различных видов зависимости <tex> y = f(x) + \epsilon </tex> (линейная, квадратичная, логарифмическая) построить [[Линейная регрессия (пример)| линейную регрессию]] и нарисовать на графике SSE-отклонения (среднеквадратичные отклонения). Данные сгенерировать самостоятельно или взять данные "Цена на хлеб".
+
 
-
# Оценить площадь единичного круга методом Монте-Карло. Построить график зависимости результата от размера выборки.
+
Задана выборка и модель классификации или регрессии, несложная. Требуется оценить и визуализировать матрицу ковариации параметров. Для линейных моделей оценка получается [https://math.stackexchange.com/questions/4082033/deriving-the-variance-covariance-matrix-for-parameter-vector-of-a-linear-regress МНК]. Для линейных моделей и нейросетей оценка получается, например, с помощью процедуры бутстреп. Семплируем подвыборку, равномощную выборке (с повторениями). Оцениваем (оптимизируем) параметры на этой подвыборке, получая набор векторов параметров. Оцениваем ковариационную матрицу. Нарисовать полученную матрицу. Нарисовать зависимость ошибки от пары параметров, например, как [http://www.machinelearning.ru/wiki/index.php?title=%D0%98%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5:ModelBreadSw.png тут].
-
<!-- # Построить выпуклую оболочку точек на плоскости. Нарисовать график: точки и их выпуклая оболочка – замкнутая ломаная линия. -->
+
 
-
# Дана выборка: [http://archive.ics.uci.edu/ml/datasets/Iris ирисы Фишера]. Реализовать процедуру классификации методом решающего дерева. Проиллюстрировать результаты классификации на плоскости в пространстве двух признаков.
+
=== Задача 51===
-
# Задан временной ряд – [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/TSForecasting/TimeSeries/Sources/tsEnergyConsumption.csv объемы почасового потребления электроэнергии] (выбрать любые два дня). Аппроксимировать ряд полиномиальными моделями различных степеней (1-7). *Предложить метод определения оптимальной степени полинома.
+
Похожая задача в [[Media:is_problem_51.pdf|файле]].
-
# Задано два одномерных [[Временной ряд (библиотека примеров) | временных ряда]] различной длины. Вычислить расстояние между рядами методом динамического выравнивания. На графике изобразить путь наименьшей стоимости.
+
 
-
# Сгенерировать набор точек на плоскости. Выделить и визуализировать главные компоненты.
+
=== Задача 52===
-
# Аппроксимировать выборку [https://dmba.svn.sourceforge.net/svnroot/dmba/Data/WhiteBreadPrices.csv цены на хлеб] полиномиальной моделью. Нарисовать график. Выделить объекты, являющиеся выбросами, используя правило трех сигм, и отметить их на графике.
+
Даны работа [https://arxiv.org/abs/2012.00152 Pedro Domingos], лекция [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2%29 Воронцова про SVM]. Требуется визуализировать Figure 1 на простой выборке, которая аппроксимируется 1) линейной моделью, 2) нейросетью. Возможно размерность пространства независимой переменной $x$ равна один, размерность пространства параметров $w$ равна два. Доработать график так, чтобы показать на нем ось $x$ и ось $K$ и даже ось $L$ (надо думать, как, цветом или в несколько графиков). При этом ось $K$ это или само ядро или путь ядра по $t$. Формулы и рисунки в [[Media:is_problem_52.pdf|файле]].
-
# Разделить выборку [http://archive.ics.uci.edu/ml/datasets/Iris ирисы Фишера] на кластеры. Проиллюстрировать на графиках результаты кластеризации для различного числа кластеров, выделить кластеры разными цветами.
+
 
-
# Дана выборка из нескольких признаков, без целевого вектора Y. Например, эта https://dmba.svn.sourceforge.net/svnroot/dmba/Data/Diabets_LARS.csv Требуется указать тот признак, который хорошо описывается (в терминах линейной регрессии) остальными (такой признак обычно исключают из выборки). Предложить способ визуализации решения (например, с помощью ковариационной матрицы).
+
 
-
# Сгенерировать выборку случайным образом и воссстановить ее плотность [[Метод парзеновского окна| методом парзеновского окна]]. Взять несколько окон разной длины и изобразить результаты на одном рисунке. Рассмотреть различные способы порождения данных.
+
 
 +
=== Задача 53===
 +
Видео, например, мультфильм с шагающим персонажем – трехиндексная матрица. Требуется выполнить низкоранговое разложение (например HOSVD), и показать оптимальное число одноранговых трехиндексных матриц, необходимое для восстановления. Можно воспользоваться сингулярными числами (главными компонентами) и [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82#.D0.9E.D1.86.D0.B5.D0.BD.D0.BA.D0.B0_.D1.87.D0.B8.D1.81.D0.BB.D0.B0_.D0.B3.D0.BB.D0.B0.D0.B2.D0.BD.D1.8B.D1.85_.D0.BA.D0.BE.D0.BC.D0.BF.D0.BE.D0.BD.D0.B5.D0.BD.D1.82_.D0.BF.D0.BE_.D0.BF.D1.80.D0.B0.D0.B2.D0.B8.D0.BB.D1.83_.D1.81.D0.BB.D0.BE.D0.BC.D0.B0.D0.BD.D0.BD.D0.BE.D0.B9_.D1.82.D1.80.D0.BE.D1.81.D1.82.D0.B8 методом сломанной трости]. Каким образом можно снизить не только размерность пространства, но и число индексов матрицы? Например зная, что герой идет от одного края сцены к другому.
 +
 
 +
== Весна 2021 ==
<!--
<!--
-
# Показать разницу в скорости выполнения матричных операций и операций в цикле. Можно использовать в качестве примера [[Сингулярное разложение]] и другие методы линейной алгебры. Показать эффективность параллельных вычислений (parfor). Результаты представить в виде диаграммы (bar chart).
+
=== Задача 31===
-
# Разобраться как работает суперпозиция функций. С помощью функции @ породить все возможные полиномы от n переменных степени не более p. Вариант: приблизить полученными полиномами временной ряд цен на хлеб [[Линейная регрессия (пример)|(данные)]].
+
 
 +
=== Задача 32===
-->
-->
-
# Дан набор трехэлементных векторов. Первые два элемента нарисовать по осям абсцисс и ординат. Третий элемент отобразить как круг с пропорциональным радиусом. Пропорции подобрать исходя из чувства прекрасного. Сравнить полученный график с plot3. Что лучше?
+
=== Задача 33===
-
# Построить методом наименьших модулей уравнение регрессии 2ой степени по результатом опытов, данные [[Media:Опыт №7.3 21.10.14.txt.zip|прилагаются]] (x1,x2,x3 - переменные факторы, N - отклик). Вариант: сравнить с методом наименьших квадратов, построив на одном рисунке 2 графика (по оси абсцисс - истинные отклики, по оси ординат - результаты моделирования с помощью МНМ и МНК)
+
Сверточные нейросети CNN: как связана свертка, кросс-корреляция и преобразование Фурье? Пояснить на примере изображений.
-
# Разобраться как работает regexp в Матлабе. Сделать код, который выделяет все, что находится внутри скобок некоторого арифметического выражения. Визуализировать работу regexp.
+
-
# Дан временной ряд из m + 1 (случайных) точек. Приблизить m его первых точек полиномами степени от 1 до m. Вычислить среднюю ошибку в точках. Какая степень дает наибольшую ошибку?
+
-
# Аппроксимировать выборку [https://dmba.svn.sourceforge.net/svnroot/dmba/Data/WhiteBreadPrices.csv цены на хлеб] полиномиальными моделями различного порядка. Построить на одном рисунке два графика: качество аппроксимации на обучении и на контроле в зависимости от степени полинома.
+
-
# Предложить способы визуализации наборов четырехмерных векторов, например для [http://archive.ics.uci.edu/ml/datasets/Iris Fisher's iris data].
+
-
<!-- # Заданы две матрицы. Проверить, есть ли в них пересечение – подматрица? -->
+
-
# Дан временной [http://archive.ics.uci.edu/ml/datasets/Individual+household+electric+power+consumption ряд], описывающий потребление электричества. Приблизить ряд несколькими [[Линейная регрессия (пример)| криволинейными моделями]] и нарисовать спрогнозированные и исходный ряды на одном графике.
+
-
# Дана выборка, в которой есть несколько выбросов. Известно, что она может быть описана одномерной линейной регрессией. Требуется переборным путем найти выбросы. Показать их на графике.
+
-
# Дана выборка из двух классов на плоскости. Требуется разделить ее линейно и найти все объекты, которые залезли в чужой класс. Показать их на графике.
+
-
# Решается задача заполнения пропусков в социологических анкетах наиболее адекватными значениями. Основная идея: для фиксированной анкеты найти заполнить ее пропущенные поля с использованием значений соответствующих полей <tex>k</tex> ближайших соседей. Задана выборка <tex>X</tex>&nbsp;--- матрица, в которой элемент <tex>x_{ij}</tex> принадлежит конечному множеству <tex>\mathbb{L}_j=\{1,...,k_j,\text{NaN}\}</tex> допустимых значений <tex>j</tex>-го поля анкеты; отметка <tex>\text{NaN}</tex> означает пропуск в поле. На множестве <tex>\mathbb{L}_j</tex> задано отношение предпочтения <tex>\preceq</tex>. Например, "начальное образование" <tex>\preceq</tex> «среднее образование» <tex>\preceq</tex> «высшее образование»&nbsp;--- отношение линейного порядка. Требуется ввести такую функцию расстояния или метрику <tex>\rho(x_i,x_k)\rightarrow \mathbb{R}\cup\text{NaN}</tex>, которая бы обеспечивала наиболее полное восстановление пропусков, и описать процедуру восстановления. ''Дополнительно'': изменится ли ваше решение, в случае, когда каждая анкета имеет не менее одного пропуска. Вариант: каждое поле имеет не менее одного пропуска. Вариант: значительная часть элементов матрицы <tex>X</tex> пропущена.
+
 +
=== Задача 34===
 +
Следует ли метод аппроксимации Лапласа из теоремы Бернштейна-фон Мизеса?
-
<!-- # На вход подается матрица инцидентности дерева. Функция возвращает список (вектор) вершин в порядке их посещения. -->
+
=== Задача 35===
-
<!-- # Классифицировать цветы ириса произвольным алгоритмом, нарисовать на плоскости «самую наглядную» пару признаков, указать, что классифицировалось правильно, а что – нет. -->
+
Эксперты оценивают качество университетов путем 1) попарного сравнения, 2) по некоторой шкале (например, пятибалльной). Некоторые оценки отсутствуют. Требуется построить рейтинг университетов, который не меняется существенно в течение лет (конечно, при отсутствии изменений в политике университетов). Примеры решения 1) считаем попарную корреляцию между оценками и строим первую главную компоненту, 2) метод Кемени-Янга. Предлагается выписать и проанализировать эти решения или предложить свое.
-
<!-- # Дан временной ряд. По его вариационному ряду построить гистограмму из n перцентилей, нарисовать ее. Какое значение временного ряда встречается чаще всего? -->
+
 +
=== Задача 36===
 +
Метод Лассо выбирает признаки в линейной модели с помощью регуляризатора. При этом значения параметров модели зависят от назначенного значения регуляризатора. Вопрос: а как изменяются дисперсии параметров? Почему именно так? (Бонус: Что изменяется в распределениях параметров, если для выбора признаков используется метод Эластик-нет?)
 +
=== Задача 37===
 +
Глубокая нейронная сеть (композиция нескольких слоев) имеет меньшее число нейронов по сравнению с альтернативной ей сетью с одним скрытым слоем. При этом качество аппроксимации не падает. Почему это происходит? Визуализируйте траекторию вектора параметров в пространстве параметров в процессе оптимизации сети. Рекомендуется использовать для визуализации пространство низкой размерности, 2D или 3D.
-
[[Категория:Учебные курсы]]
+
=== Задача 38===
 +
Сейчас у каждого человека при себе один телефон, а то и несколько. Пусть один в кармане, другой в руке а третий в сумке. Возможно ли по значениям временного ряда акселерометров (или гироскопов) двух телефонов спрогнозировать значение временного ряда третьего? Нарисовать фазовые траектории временных рядов телефонов (для ходьбы или бега или подъема по лестнице) и проанализировать методы Partial least squares, либо Cross correlation analysis.
-
===Задача 2===
+
=== Задача 39===
-
Нарисовать траекторию пошагового спуска к минимуму [|градиентного метода] и [[Алгоритм имитации отжига|имитации отжига]]. Сравнить их работу при поиске мимимума [SCHWEFEL.pdf|тестовой функции].
+
В задаче восстановления регрессии предполагается, что распределение зависимой переменной унимодально. А точнее, нормально. А как решить задачу восстановления регрессии, когда это распределение мультимодально (привести такие случаи)? Например, рассмотрим восстановления зависимой переменной, для выборки <tex>(\mathbf{x}_i, y_i),\quad i\in\{1, \dots, N\}, </tex> где неслучайная величина <tex>\mathbf{x}\in\mathbb{C}</tex> — комплексное число, а зависимая переменная, случайная величина <tex> y\in\mathbb{R}</tex> — действительное число, измеренное с некоторой погрешностью. Объем <tex>N</tex> выборки достаточно велик. Требуется восстановить модель <tex>f=\ln(\mathbf{x})</tex> (вставьте оптимизируемые параметры по вашему усмотрению). Сама независимая переменная может быть представлена в полярной форме, например <tex>\mathbf{x} = r\exp(i\theta),\quad r>0,\quad \theta =\phi\pm 2\pi, 4\pi, \dots</tex>. Предложить параметрическую модель, оценить параметры (можно и их дисперсию), нарисовать трехмерный график и проанализировать случай, когда погрешность велика.
 +
=== Задача 40===
 +
Возможно ли сложную модель, например, глубокую нейросеть, обучить на выборке, которая содержит всего несколько элементов? Как определить оптимальный объем выборки? Как определить оптимальную сложность модели? Как согласовать эти две величины?
 +
=== Задача 41===
 +
Процедура обучения модели, иначе процедура оптимизации ее параметров, описывает пошаговое изменение вектора параметров. Так как вектор параметров – это точка в пространстве параметров, то процедура описывает пошаговое преобразование пространства параметров. Цель процедуры – получение оптимального значения вектора параметров. Эта процедура имеет различные варианты.
 +
# Детерминированная оптимизация – градиентный спуск, например, методом сопряженных градиентов.
 +
# Стохастический градиентный спуск. Градиент вычисляется по случайно взятой подвыборке.
 +
# Случайный поиск и варианты генетической оптимизации.
 +
# Теоретико-игровая оптимизация: процедура является реализацией игровой стратегии.
 +
# Дистилляция знаний: модель-ученик оптимизирует параметры с помощью фиксированной модели-учителя.
 +
# Гиперсети: одна модель прогнозирует значения параметров другой.
 +
Предлагается описать на выбор интересный, нетривиальный способ обучения модели и проиллюстрировать его графиками на синтетических данных.
 +
=== Задача 42===
 +
Алгоритм [https://en.wikipedia.org/wiki/Gerchberg%E2%80%93Saxton_algorithm Герхберга-Сакстона] восстанавливает мнимую часть изображения по его действительной части. Итеративно выполняем прямое и обратное преобразование Фурье. После первого же преобразования появляется мнимая часть. Продолжаем до тех пор, пока ошибка реконструкции изображения в комплексном пространстве не стабилизируется. Этот алгоритм используется для восстановления синхротронных изображений кристаллов по амплитуде плоского когерентного излучения. Вопрос: можно ли таким образом повысить качество изображения с обычного фотоаппарата? Дополнение. Так как этот алгоритм был предложен в 1972 году, существуют его модификации. Если вспомнить, что преобразование Фурье линейно, то в качестве альтернативы рассмотрим нелинейное преобразование, например, автоэнкодер. 
 +
== Весна 2020 ==
 +
Про задачу kNN уже больше не надо рассказывать, перебор...
 +
=== Задача 1 ===
 +
Задан полносвязный граф со взвешенными ребрами. Предложить алгоритм нахождения основного дерева, который отыскивал бы это дерево путем градиентного спуска. Для этого требуется ввести дифференцируемую штрафную функцию, которая штрафует полносвязный граф за то, что он не является деревом.
 +
=== Задача 2 ===
 +
Задана выборка измерений акселерометра [http://www.cis.fordham.edu/wisdm/dataset.php WISDM]. Модель движения из шести классов движений задается вектором средних значений сегментов нескольких повторов движений одного класса. Предложить способ классификации выборки.
 +
=== Задача 3 ===
 +
Заданы два временных ряда. Предложить алгоритм выравнивания (DTW, [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%B8_%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D1%88%D0%BA%D0%B0%D0%BB%D1%8B Rus], [https://en.wikipedia.org/wiki/Dynamic_time_warping En]), который ищет путь наименьшей стоимости не перебором, а методом градиентного спуска, приближая полиномом (третьей) степени.
 +
=== Задача 4 ===
 +
Задан текст (например, «Вот дом, который построил Джек»). Преложить алгоритм, который бы по нескольким предыдущим словам прогнозировал бы следующее слово. Проанализировать ошибку прогноза.
-
Решение каждой задачи должно быть визуализировано, все рисунки необходимо кратко описать.
+
=== Задача 5 ===
 +
Задан временной ряд с изменяющимся периодом. Предложить алгоритм, который отыскивает начало периода, пример: отсечение пика или как в [http://strijov.com/papers/MotrenkoStrijov2014RV2.pdf].
 +
=== Задача 6 ===
 +
Задано плоское черно-белое изображение односвязной фигуры (клякса). Предложить алгоритм, который бы указывал группу симметрии этой фигуры, если она имеется.
 +
 +
=== Задача 7 ===
 +
Задан фрагмент музыкального произведения. Предложить быстрый (например, хеширование изображения спектрограммы звука) алгоритм поиска в музыкальной базе Shazam.
 +
 +
=== Задача 8 ===
 +
В роман одного автора (Льва Толстого) поместили несколько абзацев другого (Михаила Зощенко). Предложить алгоритм, который бы находил бы смену стиля автора (кроме этого текста ничего нет, авторов мы не знаем). Можно представить текст как набор временных рядов или предложить другой способ представления текста для анализа.
 +
 +
=== Задача 9 ===
 +
Назовем двоичную, размера <tex>M,N,</tex> матрицу <tex>m</tex>-разреженной по строкам (<tex>n</tex>-разреженной по столбцам), если в каждой строке <tex>m</tex> пропущенных значений. Пропущенные значения в строке <tex>x</tex> восстанавливаются следующим образом. Находим ближайшую к ней строку <tex>y</tex> (расстояние Хемминга не превышает <tex>\rho</tex>), и заполняем пропущенные значения. Задана случайная матрица. Чему равняется максимальное значение <tex>n</tex> (или <tex>m</tex>), чтобы все пропущенные значения можно было бы восстановить?
 +
 +
=== Задача 10 ===
 +
Задана MIDI-партитура. Требуется спрогнозировать следующую ноту как (линейную) комбинацию предыдущих. Предложить алгоритм.
 +
 +
===Задача 11===
 +
Нарисовать траекторию пошагового спуска к минимуму [http://sebastianruder.com/optimizing-gradient-descent/ градиентного метода] и [[Алгоритм имитации отжига|имитации отжига]]. Сравнить их работу при поиске мимимума [[Media: SCHWEFEL.pdf|тестовой функции]].
 +
 +
===Задача 12===
 +
Предсказать сорт винограда из которого сделано вино, используя [https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data результаты химических анализов] ([http://archive.ics.uci.edu/ml/datasets/Wine описание] данных), c помощью [[Метод_k_ближайших_соседей_(пример)|KNN]] - метода k ближайших соседей с тремя различными метриками. Построить график зависимости величины ошибки от числа соседей k.
 +
 +
===Задача 13===
 +
Для выделения тем на коллекции документов используется матричное разложение. Предлагается определить к каким темам относится каждая из русских народных сказок. Для это следует построить словарь для коллекции документов. Построить матрицу строками в которой являются частоты слов из словаря, а число строк равняется числу сказок в коллекции. Сделать разложение матрицы "документ-слово" на матрицы "документ-тема" и "тема-слово" методом [[Сингулярное_разложение|SVD]]. В качестве коллекции документов предлагается взять: А. Барто "Мячик", "Бычок", "Зайка". Документом считать 2 строки произведения. В качестве словаря взять 10-20 слов.
 +
 +
===Задача 14===
 +
Используя данные о школьниках, выявить степень их алкогольной зависимости. В данных, взятых с UCI [https://github.com/amanchoudhary/student-alcohol-consumption-prediction 'Students'] (исходная выборка изъята из UCI, но осталась в других источниках), содержится информация о 30 признаках для каждого школьника, включая социальные и гендерные, а также указана материальная обеспеченность и количество свободного времени. Выбрать на свой взгляд наиболее весомые признаки и предсказать степень употребления алкоголя по выходным или будним по шкале от 0 до 5.
 +
 +
===Задача 15===
 +
Нарисовать путь наименьшей стоимости между временными рядами, найденный с помощью [https://sourceforge.net/p/mlalgorithms/code/HEAD/tree/Group274/Goncharov2015Centroids/code/DTW.zip?format=raw алгоритма DTW]. Ввести ограничения на вид пути в матрице с помощью техники [https://izbicki.me/img/uploads/2011/10/Sakoe-Chiba1.png "Sakoe-Chiba band"]. Показать, что при наименьшей величине отклонения пути от диагонали при этих ограничениях стоимость DTW перейдет в евклидово расстояние. Исследовать зависимость стоимости пути от величины ограничения. В качестве данных использовать синтетические временные ряды вида <tex>\sin ( x + c ) , \sin ( a |\sin ( x ) | ) + \sin ( b x )</tex> .
 +
 +
===Задача 16===
 +
По описанию [http://archive.ics.uci.edu/ml/datasets/Fertility условий посева] предсказать прорастут семена растений или нет. Провести бинарную классификацию семян с помощью метода Парзеновского окна. Построить график зависимости ошибки на контроле от ширины окна. Подобрать оптимальную ширину окна.
 +
 +
===Задача 17===
 +
Идентификация видов стекла.
 +
Часто на месте преступления остаются осколки разных видов стекол, которые можно использовать как улики, если определить тип стекла и от каких оно объектов. [https://archive.ics.uci.edu/ml/machine-learning-databases/glass/ Выборка] состоит из 9 признаков - химических параметров образцов и 214 объектов. Необходимо каждому образцу сопоставить один из 6 классов (например: стекло автомобиля, осколок посуды, окно здания) и сравнить качество работы решающего дерева и алгоритма [[Решающее дерево| решающего дерева]] и алгоритма [[Метод k ближайших соседей (пример)| k-ближайших соседей]]. В качестве функции ошибки использовать долю неправильных ответов классификатора. Дает ли масштабирование признаков значительное улучшение в качестве классификации?
 +
 +
===Задача 18===
 +
Распознавание [https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html британских гласных] (11 штук) по данным с динамиков, рекомендуется использовать нормированные признаки (файл .scaled). Решить задачу многоклассовой классификации с помощью решающего дерева. Реализовать метод решающего дерева, построить область разделения на классы в проекции на любые 2 признака.
 +
 +
===Задача 19 ===
 +
Классификация [http://archive.ics.uci.edu/ml/datasets/Mushroom ядовитости грибов] по основным признакам. Построить модель классификации на основе [[RBF| сети радиальных базисных функций]]. В качестве функции ошибки использовать метрику [https://www.jair.org/media/346/live-346-1610-jair.pdf HEOM].
 +
 +
===Задача 20===
 +
В крупную сеть гипермаркетов ежедневно выполняются поставки различных товаров. Требуется, использую временную историю спроса бананов за один год [https://sourceforge.net/p/mlalgorithms/code/HEAD/tree/Group274/Dvinskikh2016Essays/TestProgramming/Data_data.mat Goods], построить прогноз спроса товара на неделю. Для прогнозирования предлагается использовать алгоритм Гусеница, или SSA (Singular spectrum analysis).
 +
 +
===Задача 21===
 +
Предсказание площади лесных пожаров. На основе погодных измерений необходимо предсказать объем выгоревших лесных массивов на севере Португалии. [https://archive.ics.uci.edu/ml/machine-learning-databases/forest-fires/ Выборка] состоит из 13 признаков и 517 объектов. Для решения задачи предлагается использовать [[Метод наименьших квадратов| метод наименьших квадратов]] с регуляризацией. Нарисовать график весов признаков и общей ошибки на кросс-валидации при изменении параметра регуляризации. Какие признаки наиболее важны для нашей задачи? Что изменится, если предварительно все признаки стандартизовать?
 +
 +
==Весна 2019==
 +
===Задача 22 ===
 +
* Решить задачу: классификации
 +
* на выборке: синтетической и https://archive.ics.uci.edu/ml/datasets/Lung+Cancer
 +
* с использованием моделей: kNN, SVM, логистическая регрессия
 +
* со структурными параметрами: число и состав признаков,
 +
* критерии качества AUC, F1, число признаков
 +
 +
===Задача 23 ===
 +
* Решить задачу: регрессии
 +
* на выборке: синтетической и https://drive.google.com/file/d/157SPnufv1VkxazY3H58HHqYJYpZ76Ghw/view?usp=sharing
 +
* с использованием моделей: линейная регрессия, PCA + линейная регрессия, простая нейросеть
 +
* со структурными параметрами: число и состав признаков, размерность скрытого пространства, структура сети
 +
* критерии качества: квадратичная ошибка, число обусловленности
 +
 +
===Задача 24 ===
 +
* Решить задачу: выбора алгоритма оптимизации
 +
* на выборке: синтетической и MNIST
 +
* с использованием моделей: нейронных сетей простой структуры
 +
* Предлагаемые алгоритмы: SGD, Nesterov Momentum, Adam
 +
* со структурными параметрами: структура сети
 +
* критерии качества: скорость сходимости, значения оптимума, вид траектории
 +
 +
===Задача 25 ===
 +
* Решить задачу: классификации
 +
* на выборке: синтетической и https://archive.ics.uci.edu/ml/datasets/Breast+Cancer
 +
* с использованием моделей: логистической регрессии, нейронной сети, градиентного бустинга
 +
* со структурными параметрами: состав признаков, структура модели, количество параметров модели
 +
* критерии качества: ROC AUC, PR кривая, сложность модели (ввести опеределение)
 +
 +
===Задача 26 ===
 +
* Решить задачу: кластеризации
 +
* На выборке: предобученных векторов [https://github.com/facebookresearch/fastText/blob/master/pretrained-vectors.md fasttext], взять только слова из [https://github.com/first20hours/google-10000-english/blob/master/20k.txt 20k.txt]
 +
* С использованием модели: K-means
 +
* Со структурным параметром: K (число кластеров)
 +
* Критерии качества: внутрикластерное расстояние (евклидово расстояние и косинусная мера), межкластерное расстояние (евклидово расстояние и косинусная мера)
 +
 +
===Задача 27 ===
 +
* Решить задачу: классификации
 +
* На выборке: [http://mmlab.ie.cuhk.edu.hk/projects/CelebA.html celeb-a], рассматривать изображения как черно-белые. В качестве метки класса рассматривать пол изображенного человека.
 +
* С использованием моделей: SVM, нейронная сеть с одним скрытым слоем.
 +
* Со структурным параметром: количество нейронов на скрытом слое, количество итераций оптимизации нейронной сети.
 +
* критерии качества: ROC AUC
 +
 +
===Задача 28 ===
 +
* Решить задачу: кластеризации/классификации
 +
* На выборке: MNIST
 +
* С использованием моделей: PCA + K-means
 +
* Со структурным параметром: количество главных компонент в PCA
 +
* С критериями качества: однородность кластеров, Accuracy (за ответ классификатора принимать наиболее представимый в кластере класс)
 +
 +
===Задача 29 ===
 +
* Решить задачу: классификации
 +
* На выборке: SemEval 2015 (http://alt.qcri.org/semeval2015/task2/data/uploads/sts2015-en-post.zip).
 +
* С использованием моделей: логистическая регрессия на центроидах векторов предложений, SVM, KNN, Decision Tree.
 +
* Векторы предложений: https://github.com/facebookresearch/fastText/blob/master/pretrained-vectors.md
 +
* В качестве меток класса брать округление оценок схожести (принимает значения от 0 до 5)
 +
* Со структурным параметром: глубина и структура деревьев, параметры регуляризации логистической регрессии и SVM, количество соседей в KNN
 +
* С критериями качества: Precision-Recall-кривая
 +
 +
===Задача 30 ===
 +
* Решить задачу: классификации
 +
* На выборке: тональность твиттер-сообщений http://thinknook.com/wp-content/uploads/2012/09/Sentiment-Analysis-Dataset.zip
 +
* С использованием моделей: логистическая регрессия на центроидах векторов предложений, нейронная сеть с одним скрытым слоем.
 +
* Векторы предложений: https://github.com/facebookresearch/fastText/blob/master/pretrained-vectors.md
 +
* Со структурным параметром: количество итераций оптимизации нейронной сети, размер скрытого слоя.
 +
* С критериями качества: ROC AUC, precision-recall-кривая
 +
 +
{{tip|Тем, кто использует нейросети, важно понимать, что происходит внутри черного ящика.'''}}
 +
 +
=== Черновики простых задач по глубокому обучению ===
 +
 +
* Выборки: используются те, которые часто встречаются в статьях, легко скачать. Желательно, чтобы они выкачивались питоновскими пакетами автоматически.
 +
*# Boston: есть код загрузки в sklearn: http://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_boston.html
 +
*# MNIST: есть код загрузки в TensorFlow (https://www.tensorflow.org/versions/r1.2/get_started/mnist/pros#load_mnist_data), Keras (https://keras.io/datasets/#mnist-database-of-handwritten-digits)
 +
*# CIFAR-10: есть код в TensorFlow (https://github.com/tensorflow/models/tree/master/tutorials/image/cifar10/), Keras (https://keras.io/datasets/#cifar10-small-image-classification)
 +
*# Celeb-A: набор лиц знаменитостей с 40 булевыми атрибутами для каждого лица, выборка достаточно часто упоминается в работах по GAN http://mmlab.ie.cuhk.edu.hk/projects/CelebA.html
 +
*# Frey Faces: игрушечный датасет с лицом одного человека, часто используется в статьях по генеративным моделям https://cs.nyu.edu/~roweis/data.html
 +
*# Текстовые корпусы из nltk, выкачиваются в одну команду https://www.nltk.org/book/ch02.html
 +
* По задачам:
 +
*# В работе по GAN'ам (https://arxiv.org/pdf/1709.06548.pdf) был очень простой эксперимент на паре выборок <картинки из MNIST, транспонированные картинки из MNIST>, где сеть училась делать транспонирование, при этом задача рассматривалась как semi-supervised. Можно попробовать изучить, какое количество объектов потребуется простому автокодировщику, чтобы выучить операцию транспонирования.
 +
*# В статье (https://omoindrot.github.io/triplet-loss) рассматривались различные подходы к Metric Learning на основе триплетов. Можно провести сравнение стратегий Hard triplets, Easy triplets, Semi-hard triplets и случайных триплетов для какой-нибудь выборки. Результатом может быть визуализация, схожая с последним графиком из статьи.
 +
*# В работе (https://arxiv.org/pdf/1711.00464.pdf) рассматривается модификация функции потерь вариационного автокодировщика с разными коэффициентами на D_KL и ошибку реконструкции. Если коэффициент D_KL высокий - то модель хорошо работает как генеративная, если коэффициент D_KL низкий, то модель лучше восстанавливает исходную выборку. Можно повторить схожий эксперимент с лицами, получится наглядный график, как Figure 4 из статьи.
 +
*# Можно обучить модель перевода или что-то похожее на Seq2Seq: https://blog.keras.io/a-ten-minute-introduction-to-sequence-to-sequence-learning-in-keras.html Интересно было бы посмотреть как меняется перевод при снижении количества параметров.
 +
*# Есть простой пример посимвольной генерации текста на Keras: https://github.com/keras-team/keras/blob/master/examples/lstm_text_generation.py Здесь можно поэкспериментировать с температурой при генерации.
 +
 +
===Пожелания (но не указания)===
 +
Слайды желательно делать с комментариями, достаточными для передачи сообщения аудитории. Графики должны иметь подписанные оси и поясняющий текст с выводом - результатом анализа.
 +
# Цель вычислительного эксперимента, описание выборок, список моделей
 +
# Список функций ошибки, критериев качества
 +
# Способ разбиения выборки на обучение-контроль (выбрать)
 +
# Таблица модели/выборки/критерии качества на разбиении со ст. откл.
 +
# Анализ выбранной модели на разбиении обучение-контроль
 +
## График зависимости функции ошибки от значения структурного параметра со ст. откл.
 +
## График зависимости функции ошибки от объема выборки со ст. откл.
 +
## График скорости сходимости функции ошибки (зависимости функции ошибки от номера итерации оптимизационного алгоритма) со ст. откл.
 +
<!--{{tip|-->
 +
# Пожалуйста, называйте файлы со своими решениями '''Surname2019ProblemN''' для этих задач (или '''Surname2019ProblemOldN''' для задач прошлых лет внизу списка).<!--'''}}-->
 +
 +
== Весна 2018 и ранее ==
 +
Эти задачи тоже можно решать
 +
 +
# Восстановить регрессию используя формулу [[Формула Надарая-Ватсона|Надарая-Ватсона]]. Нарисовать восстановленную функцию с различными ядрами и шириной окна. В качестве данных использовать выборку [https://dmba.svn.sourceforge.net/svnroot/dmba/Data/WhiteBreadPrices.csv цены на хлеб] или [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/TSForecasting/TimeSeries/Sources/tsEnergyConsumption.csv| цены на электроэнергию].
 +
# 2D визуализация [https://drive.google.com/file/d/0B3vYNXYMNm_rMDFGc1B3OS0tRGs/view?usp=sharing N-мерных данных] с помощью [[Метод_главных_компонент|PCA]].
 +
Курс [https://www.coursera.org/learn/machine-learning/ "Machine Learning"] на Coursera: 7_pca.m script and 2.5 part of exercise 7 [https://drive.google.com/file/d/0B3vYNXYMNm_rNjJiaGJlSDc4X2M/view?usp=sharing].
 +
Визуализировать результаты на плоскости, оценить ошибку.
 +
# Заполнение пропусков в данных приложения [https://drive.google.com/open?id=0B3vYNXYMNm_rSWxDVWhLR0tHNEE Сardiomood]. Сравнить различные методы заполнения пропусков <ref>{{книга |автор = Загоруйко Н.Г. |заглавие = Прикладные методы анализа данных и знаний. - Новосибирск: Изд-во ин-та математики, 1999}}</ref>: 1) метод замены пропущенного значения средним из ближайших присутствующих элементов переменной, 2) метод восстановления пропущенного значения сплайн-интерполяцией по присутствующим элементам, 3) метод восстановления пропущенного значения на основе использования Zet-алгоритма <ref>{{книга |автор = Загоруйко Н.Г. |заглавие = Алгоритм заполнения пропусков в эмпирических таблицах. // Эмпирическое предсказание и распознавание образов. - Новосибирск, 1975. - Вып. 61: Вычислительные системы. - С. 3-27}}</ref>. Сравнение делать оценивая близость восстановленных пропусков с реальными данными.
 +
# Классифицировать [http://archive.ics.uci.edu/ml/datasets/Credit+Approval заемщиков кредита] с помощью [[Логистическая регрессия|логистической регрессии]]. Для оптимизации параметров использовать алгоритм [[Логистическая регрессия (пример)|Ньютона-Рафсона]] или алгоритм [[Метод градиентного спуска|градиентного спуска]]. Построить ROC-кривые для фиксированного числа разбиений. Построить ряд графиков для различных мощностей подвыборок разбиений.
 +
Число итераций ограничить либо условием на сходимость – норма разности последовательных векторов весов не больше точности, либо числом шагов.
 +
# Разметить [https://archive.ics.uci.edu/ml/machine-learning-databases/spambase/ коллекцию писем]. Предполагается, что некоторая часть коллекции является спамом, нужно отделить эти письма от всех остальных. Использовать [http://www.machinelearning.ru/wiki/images/2/28/Voron-ML-Clustering-slides.pdf| алгоритм кластеризации k-means]. Число кластеров установить равным двум. Попробовать различные стратегии инициализации. Сравнить результаты работы алгоритма с реальной разметкой коллекции на спам.
 +
# Оценить число главных компонент в [http://archive.ics.uci.edu/ml/datasets/Gas+sensor+array+under+flow+modulation данных] с помощью [[Метод главных компонент| метода сломанной трости]]. Для нахождения главных компонент применить МГК. Построить график зависимости величины ошибки описания объектов в базисе из главных компонент от числа главных компонент. По графику оценить собственную размерность пространства.
 +
# Построить прогноз [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/TSForecasting/TimeSeries/Sources/tsEnergyConsumption.csv энергопотребления] на 24 часа вперед методом [http://svn.code.sf.net/p/mlalgorithms/code/GroupYAD16/Akhtyamov2016FeatureSelectionVAR/doc/Akhtyamov2016FeatureSelectionVAR.pdf векторной авторегрессии] (см. постановку задачи, [[Media: Small var.m.rtf |пример реализации]]). Построить график, сравнить истинное поведение потребления и прогноз. Рассмотреть зависимость функции ошибки на прогнозе от длины использованной предыстории, имеет ли место переобучение?
 +
<!-------------- -->
 +
# Приближение элементов изображения линией или поверхностью.
 +
#* Требуется нарисовать приближающую прямую, окружность или другую линию или поверхность по вашему усмотрению на одном из следующих [[Media:Spring2015Problem.zip|изображений]] или на вашем изображении. Предобработка изображений (как и вообще, всё, что приводит к результату, разрешается). Обсуждаем постановку задачи и решение, а не техническую сторону (не то, как это было запрограммировано).
 +
#* Для справки. Как приблизить множество точек на плоскости прямой линией или полиномом, [[Линейная регрессия (пример)|написано здесь]]. Как найти центр и радиус окружности написано [[Линейная регрессия (пример)#Применение линейной постановки задачи для моделирования кривых второго порядка|здесь]]. Как найти фокусы приближаюшего эллипса, можно понять из п. 2 и Википедии [https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%B2%D0%B0%D1%8F_%D0%B2%D1%82%D0%BE%D1%80%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0], [https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%B2%D0%B0%D1%8F_%D0%B2%D1%82%D0%BE%D1%80%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0]. Алгоритм, приближающий множество точек в пространстве поверхностью, приведен здесь [http://sourceforge.net/p/mvr/code/HEAD/tree/examples/LinfitOptions/], смотрите также [[Численные методы обучения по прецедентам (практика, В.В. Стрижов)/Примеры|список примеров]].
 +
#* Развитие задачи: рассказать, как решить эту задачу 1) для произвольной размерности пространства 2) методом главных компонент.
 +
<!-------------- -->
# С помощью логистической регрессии разделить два класса точек на плоскости. Результаты изобразить на графиках (см. пример [[Численные методы обучения по прецедентам (практика, В.В. Стрижов)/Примеры| Classification using logistic regression]]). Рассмотреть случаи линейно разделимой и неразделимой выборок.
# С помощью логистической регрессии разделить два класса точек на плоскости. Результаты изобразить на графиках (см. пример [[Численные методы обучения по прецедентам (практика, В.В. Стрижов)/Примеры| Classification using logistic regression]]). Рассмотреть случаи линейно разделимой и неразделимой выборок.
# Изобразить на рисунке Парето-расслоение множества точек на плоскости. (Парето-расслоение - набор последовательно вычисляемых Парето оптимальных фронтов. Первый фронт вычисляется для полной выборки и удаляется из нее. Для оставшихся данных вычисляется следующий слой и т.д)
# Изобразить на рисунке Парето-расслоение множества точек на плоскости. (Парето-расслоение - набор последовательно вычисляемых Парето оптимальных фронтов. Первый фронт вычисляется для полной выборки и удаляется из нее. Для оставшихся данных вычисляется следующий слой и т.д)
Строка 88: Строка 306:
# Для различных видов зависимости <tex> y = f(x) + \epsilon </tex> (линейная, квадратичная, логарифмическая) построить [[Линейная регрессия (пример)| линейную регрессию]] и нарисовать на графике SSE-отклонения (среднеквадратичные отклонения). Данные сгенерировать самостоятельно или взять данные "Цена на хлеб".
# Для различных видов зависимости <tex> y = f(x) + \epsilon </tex> (линейная, квадратичная, логарифмическая) построить [[Линейная регрессия (пример)| линейную регрессию]] и нарисовать на графике SSE-отклонения (среднеквадратичные отклонения). Данные сгенерировать самостоятельно или взять данные "Цена на хлеб".
# Оценить площадь единичного круга методом Монте-Карло. Построить график зависимости результата от размера выборки.
# Оценить площадь единичного круга методом Монте-Карло. Построить график зависимости результата от размера выборки.
-
<!-- # Построить выпуклую оболочку точек на плоскости. Нарисовать график: точки и их выпуклая оболочка – замкнутая ломаная линия. -->
 
# Дана выборка: [http://archive.ics.uci.edu/ml/datasets/Iris ирисы Фишера]. Реализовать процедуру классификации методом решающего дерева. Проиллюстрировать результаты классификации на плоскости в пространстве двух признаков.
# Дана выборка: [http://archive.ics.uci.edu/ml/datasets/Iris ирисы Фишера]. Реализовать процедуру классификации методом решающего дерева. Проиллюстрировать результаты классификации на плоскости в пространстве двух признаков.
# Задан временной ряд – [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/TSForecasting/TimeSeries/Sources/tsEnergyConsumption.csv объемы почасового потребления электроэнергии] (выбрать любые два дня). Аппроксимировать ряд полиномиальными моделями различных степеней (1-7). *Предложить метод определения оптимальной степени полинома.
# Задан временной ряд – [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/TSForecasting/TimeSeries/Sources/tsEnergyConsumption.csv объемы почасового потребления электроэнергии] (выбрать любые два дня). Аппроксимировать ряд полиномиальными моделями различных степеней (1-7). *Предложить метод определения оптимальной степени полинома.
Строка 97: Строка 314:
# Дана выборка из нескольких признаков, без целевого вектора Y. Например, эта https://dmba.svn.sourceforge.net/svnroot/dmba/Data/Diabets_LARS.csv Требуется указать тот признак, который хорошо описывается (в терминах линейной регрессии) остальными (такой признак обычно исключают из выборки). Предложить способ визуализации решения (например, с помощью ковариационной матрицы).
# Дана выборка из нескольких признаков, без целевого вектора Y. Например, эта https://dmba.svn.sourceforge.net/svnroot/dmba/Data/Diabets_LARS.csv Требуется указать тот признак, который хорошо описывается (в терминах линейной регрессии) остальными (такой признак обычно исключают из выборки). Предложить способ визуализации решения (например, с помощью ковариационной матрицы).
# Сгенерировать выборку случайным образом и воссстановить ее плотность [[Метод парзеновского окна| методом парзеновского окна]]. Взять несколько окон разной длины и изобразить результаты на одном рисунке. Рассмотреть различные способы порождения данных.
# Сгенерировать выборку случайным образом и воссстановить ее плотность [[Метод парзеновского окна| методом парзеновского окна]]. Взять несколько окон разной длины и изобразить результаты на одном рисунке. Рассмотреть различные способы порождения данных.
-
<!--
 
# Показать разницу в скорости выполнения матричных операций и операций в цикле. Можно использовать в качестве примера [[Сингулярное разложение]] и другие методы линейной алгебры. Показать эффективность параллельных вычислений (parfor). Результаты представить в виде диаграммы (bar chart).
# Показать разницу в скорости выполнения матричных операций и операций в цикле. Можно использовать в качестве примера [[Сингулярное разложение]] и другие методы линейной алгебры. Показать эффективность параллельных вычислений (parfor). Результаты представить в виде диаграммы (bar chart).
# Разобраться как работает суперпозиция функций. С помощью функции @ породить все возможные полиномы от n переменных степени не более p. Вариант: приблизить полученными полиномами временной ряд цен на хлеб [[Линейная регрессия (пример)|(данные)]].
# Разобраться как работает суперпозиция функций. С помощью функции @ породить все возможные полиномы от n переменных степени не более p. Вариант: приблизить полученными полиномами временной ряд цен на хлеб [[Линейная регрессия (пример)|(данные)]].
-
-->
 
# Дан набор трехэлементных векторов. Первые два элемента нарисовать по осям абсцисс и ординат. Третий элемент отобразить как круг с пропорциональным радиусом. Пропорции подобрать исходя из чувства прекрасного. Сравнить полученный график с plot3. Что лучше?
# Дан набор трехэлементных векторов. Первые два элемента нарисовать по осям абсцисс и ординат. Третий элемент отобразить как круг с пропорциональным радиусом. Пропорции подобрать исходя из чувства прекрасного. Сравнить полученный график с plot3. Что лучше?
# Построить методом наименьших модулей уравнение регрессии 2ой степени по результатом опытов, данные [[Media:Опыт №7.3 21.10.14.txt.zip|прилагаются]] (x1,x2,x3 - переменные факторы, N - отклик). Вариант: сравнить с методом наименьших квадратов, построив на одном рисунке 2 графика (по оси абсцисс - истинные отклики, по оси ординат - результаты моделирования с помощью МНМ и МНК)
# Построить методом наименьших модулей уравнение регрессии 2ой степени по результатом опытов, данные [[Media:Опыт №7.3 21.10.14.txt.zip|прилагаются]] (x1,x2,x3 - переменные факторы, N - отклик). Вариант: сравнить с методом наименьших квадратов, построив на одном рисунке 2 графика (по оси абсцисс - истинные отклики, по оси ординат - результаты моделирования с помощью МНМ и МНК)
# Разобраться как работает regexp в Матлабе. Сделать код, который выделяет все, что находится внутри скобок некоторого арифметического выражения. Визуализировать работу regexp.
# Разобраться как работает regexp в Матлабе. Сделать код, который выделяет все, что находится внутри скобок некоторого арифметического выражения. Визуализировать работу regexp.
-
# Дан временной ряд из m + 1 (случайных) точек. Приблизить m его первых точек полиномами степени от 1 до m. Вычислить среднюю ошибку в точках. Какая степень дает наибольшую ошибку?
+
# Дан временной ряд из <tex>m + 1</tex> (случайных) точек. Приблизить m его первых точек полиномами степени от 1 до m. Вычислить среднюю ошибку в точках. Какая степень дает наибольшую ошибку?
# Аппроксимировать выборку [https://dmba.svn.sourceforge.net/svnroot/dmba/Data/WhiteBreadPrices.csv цены на хлеб] полиномиальными моделями различного порядка. Построить на одном рисунке два графика: качество аппроксимации на обучении и на контроле в зависимости от степени полинома.
# Аппроксимировать выборку [https://dmba.svn.sourceforge.net/svnroot/dmba/Data/WhiteBreadPrices.csv цены на хлеб] полиномиальными моделями различного порядка. Построить на одном рисунке два графика: качество аппроксимации на обучении и на контроле в зависимости от степени полинома.
# Предложить способы визуализации наборов четырехмерных векторов, например для [http://archive.ics.uci.edu/ml/datasets/Iris Fisher's iris data].
# Предложить способы визуализации наборов четырехмерных векторов, например для [http://archive.ics.uci.edu/ml/datasets/Iris Fisher's iris data].
Строка 112: Строка 327:
# Дана выборка из двух классов на плоскости. Требуется разделить ее линейно и найти все объекты, которые залезли в чужой класс. Показать их на графике.
# Дана выборка из двух классов на плоскости. Требуется разделить ее линейно и найти все объекты, которые залезли в чужой класс. Показать их на графике.
# Решается задача заполнения пропусков в социологических анкетах наиболее адекватными значениями. Основная идея: для фиксированной анкеты найти заполнить ее пропущенные поля с использованием значений соответствующих полей <tex>k</tex> ближайших соседей. Задана выборка <tex>X</tex>&nbsp;--- матрица, в которой элемент <tex>x_{ij}</tex> принадлежит конечному множеству <tex>\mathbb{L}_j=\{1,...,k_j,\text{NaN}\}</tex> допустимых значений <tex>j</tex>-го поля анкеты; отметка <tex>\text{NaN}</tex> означает пропуск в поле. На множестве <tex>\mathbb{L}_j</tex> задано отношение предпочтения <tex>\preceq</tex>. Например, "начальное образование" <tex>\preceq</tex> «среднее образование» <tex>\preceq</tex> «высшее образование»&nbsp;--- отношение линейного порядка. Требуется ввести такую функцию расстояния или метрику <tex>\rho(x_i,x_k)\rightarrow \mathbb{R}\cup\text{NaN}</tex>, которая бы обеспечивала наиболее полное восстановление пропусков, и описать процедуру восстановления. ''Дополнительно'': изменится ли ваше решение, в случае, когда каждая анкета имеет не менее одного пропуска. Вариант: каждое поле имеет не менее одного пропуска. Вариант: значительная часть элементов матрицы <tex>X</tex> пропущена.
# Решается задача заполнения пропусков в социологических анкетах наиболее адекватными значениями. Основная идея: для фиксированной анкеты найти заполнить ее пропущенные поля с использованием значений соответствующих полей <tex>k</tex> ближайших соседей. Задана выборка <tex>X</tex>&nbsp;--- матрица, в которой элемент <tex>x_{ij}</tex> принадлежит конечному множеству <tex>\mathbb{L}_j=\{1,...,k_j,\text{NaN}\}</tex> допустимых значений <tex>j</tex>-го поля анкеты; отметка <tex>\text{NaN}</tex> означает пропуск в поле. На множестве <tex>\mathbb{L}_j</tex> задано отношение предпочтения <tex>\preceq</tex>. Например, "начальное образование" <tex>\preceq</tex> «среднее образование» <tex>\preceq</tex> «высшее образование»&nbsp;--- отношение линейного порядка. Требуется ввести такую функцию расстояния или метрику <tex>\rho(x_i,x_k)\rightarrow \mathbb{R}\cup\text{NaN}</tex>, которая бы обеспечивала наиболее полное восстановление пропусков, и описать процедуру восстановления. ''Дополнительно'': изменится ли ваше решение, в случае, когда каждая анкета имеет не менее одного пропуска. Вариант: каждое поле имеет не менее одного пропуска. Вариант: значительная часть элементов матрицы <tex>X</tex> пропущена.
-
 
-
 
-
<!-- # На вход подается матрица инцидентности дерева. Функция возвращает список (вектор) вершин в порядке их посещения. -->
 
-
<!-- # Классифицировать цветы ириса произвольным алгоритмом, нарисовать на плоскости «самую наглядную» пару признаков, указать, что классифицировалось правильно, а что – нет. -->
 
-
<!-- # Дан временной ряд. По его вариационному ряду построить гистограмму из n перцентилей, нарисовать ее. Какое значение временного ряда встречается чаще всего? -->
 
-
 
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Текущая версия

  • Короткая ссылка на эту страницу bit.ly/IS-prob

Советы по решению задач (это просто советы, а не указания)

  • Теоретическое решение важнее практического.
  • Пишите теорию сами (не копируйте материал лекций).
  • Визуализируйте решение задач (рисунок от руки предпочтительнее его отсутствия).
  • Результаты эксперимента выносите на слайды (не показывайте pynb).
  • При обсуждении нейросетей учтите, что они для нас — не черные ящики, а прозрачные.
  • Берите эти, или прошлые, или свои задачи – что вам самим интересно.

Осень 2023 (можно использовать не только эти задачи, но и задачи прошлых лет)

Задачи 54-64

Скоро будут, пока используйте задачи прошлых лет или показывайте свои.

Задача 54

Найти задачу из Pen and Paper Exercises in Machine Learning by Michael U. Gutmann и разобрать ее решение. (И даже проиллюстрировать графиком в коде.)

Задача 55

В задаче логистической регрессии найти оптимальные параметры модели (любая небольшая выборка под регрессию из UCI, пример из sklearn). Используюя случайные подвыбоки найти ковариацию параметров.

Задача 56

В задаче автогеррессионного прогнозирования оценить (теоретически), насколько отчетов времени вперед можно сделать прогноз с дисперсией, не превышающей заданную. Дисперсию ошибки и прогноза можно оценить. Нарисовать график с осями "время момента прогноза, дисперсия прогноза".

Задача 57

Проанализировать компромисс отклонение-дисперсия (bias-variance tradeoff) для случая разных типов распределений (желательно включая мультимодальные), нарисовать иллюстранцию на простых синтетических данных.


Весна 2022

Задача 43

Для акселерометров двух мобильных телефонов в руке или в кармане во время ходьбы: прогнозировать значения одного по другому (метод partial least squares, canonic correlation analysis). Насколько вырастет ошибка прогноза значений гироскопа по акселерометру? Или значения акселерометра в кармане по значению акселерометра в руке?

Задача 44

Задана выборка для классификации и модель решающего дерева. На случайных подвыборках алгоритм построения дерева, например С 4.5, строит различные деревья. Как можно вычислить расстояние между двумя деревьями? Насколько разные деревья возвращает алгоритм построения дерева? Визуализировать значения функции парного расстояния? Насколько различные деревья возвращает алгоритм построения леса решающих деревьев?

Задача 45

Задана выборка для классификации или для регрессии. На случайных подвыборках оценить матожидание и дисперсию функции ошибки (точность прогноза). Оценить матожидание и ковариации элементов вектора параметров. Как изменяются все эти оценки при 1) снижении объема выборки, 2) снижении сложности модели? Нарисовать графики. Модель – линейная или логистическая регрессия. Сложность – число параметров. (Вариант с нейросетью.)

Задача 46

Задана выборка для метрической классификации (kNN). Как изменится точность классификации при увеличении числа ближайших соседей? На обучении, на контроле? Как найти оптимальное число соседей? Что изменится, если вместо евклидова расстояния использовать расстояние Махаланобиса x'Ax. Как получить оптимальный метрический тензор A?

Задача 47

Показать, что движения конечностей человека адекватно аппроксимируются моделью маятника (если покажете, что системой маятников, вообще замечательно). Модель задана в виде ОДУ, решением ОДУ является интегральная кривая. Требуется снять показания акселерометра и гироскопа своего мобильного телефона, или двух телефонов, в руке, сумке, кармане (это маятник), или найти готовые. Нарисовать эти показания в фазовом пространстве "скорость-ускорение" или можно построить пространство по другому, на ваш вкус. Решить ОДУ – модель маятника, нарисовать решение ОДУ в том же пространстве. Запустить код Neural ODE, аппроксимировать показания, нарисовать решение в том же пространстве[1].

Задача 48

Предыдущая задача на следующих даных: по видео маятника часов восстановить и нарисовать фазовое пространство и интегральную кривую решения уравнения маятника. Насколько решение математической модели маятника совпадает с координатами маятника на видео?

Задача 49

Обосновать и показать на примере почему повышать число слоев нейросети предпочтительнее, с точки зрения точности аппроксимации, чем повышать число нейронов скрытого слоя. Использовать теоремы Колмогорова, Цыбенкова, Ханина: [2], см. также 1, 2, 3

Задача 50

Задана выборка и модель классификации или регрессии, несложная. Требуется оценить и визуализировать матрицу ковариации параметров. Для линейных моделей оценка получается МНК. Для линейных моделей и нейросетей оценка получается, например, с помощью процедуры бутстреп. Семплируем подвыборку, равномощную выборке (с повторениями). Оцениваем (оптимизируем) параметры на этой подвыборке, получая набор векторов параметров. Оцениваем ковариационную матрицу. Нарисовать полученную матрицу. Нарисовать зависимость ошибки от пары параметров, например, как тут.

Задача 51

Похожая задача в файле.

Задача 52

Даны работа Pedro Domingos, лекция Воронцова про SVM. Требуется визуализировать Figure 1 на простой выборке, которая аппроксимируется 1) линейной моделью, 2) нейросетью. Возможно размерность пространства независимой переменной $x$ равна один, размерность пространства параметров $w$ равна два. Доработать график так, чтобы показать на нем ось $x$ и ось $K$ и даже ось $L$ (надо думать, как, цветом или в несколько графиков). При этом ось $K$ это или само ядро или путь ядра по $t$. Формулы и рисунки в файле.


Задача 53

Видео, например, мультфильм с шагающим персонажем – трехиндексная матрица. Требуется выполнить низкоранговое разложение (например HOSVD), и показать оптимальное число одноранговых трехиндексных матриц, необходимое для восстановления. Можно воспользоваться сингулярными числами (главными компонентами) и методом сломанной трости. Каким образом можно снизить не только размерность пространства, но и число индексов матрицы? Например зная, что герой идет от одного края сцены к другому.

Весна 2021

Задача 33

Сверточные нейросети CNN: как связана свертка, кросс-корреляция и преобразование Фурье? Пояснить на примере изображений.

Задача 34

Следует ли метод аппроксимации Лапласа из теоремы Бернштейна-фон Мизеса?

Задача 35

Эксперты оценивают качество университетов путем 1) попарного сравнения, 2) по некоторой шкале (например, пятибалльной). Некоторые оценки отсутствуют. Требуется построить рейтинг университетов, который не меняется существенно в течение лет (конечно, при отсутствии изменений в политике университетов). Примеры решения 1) считаем попарную корреляцию между оценками и строим первую главную компоненту, 2) метод Кемени-Янга. Предлагается выписать и проанализировать эти решения или предложить свое.

Задача 36

Метод Лассо выбирает признаки в линейной модели с помощью регуляризатора. При этом значения параметров модели зависят от назначенного значения регуляризатора. Вопрос: а как изменяются дисперсии параметров? Почему именно так? (Бонус: Что изменяется в распределениях параметров, если для выбора признаков используется метод Эластик-нет?)

Задача 37

Глубокая нейронная сеть (композиция нескольких слоев) имеет меньшее число нейронов по сравнению с альтернативной ей сетью с одним скрытым слоем. При этом качество аппроксимации не падает. Почему это происходит? Визуализируйте траекторию вектора параметров в пространстве параметров в процессе оптимизации сети. Рекомендуется использовать для визуализации пространство низкой размерности, 2D или 3D.

Задача 38

Сейчас у каждого человека при себе один телефон, а то и несколько. Пусть один в кармане, другой в руке а третий в сумке. Возможно ли по значениям временного ряда акселерометров (или гироскопов) двух телефонов спрогнозировать значение временного ряда третьего? Нарисовать фазовые траектории временных рядов телефонов (для ходьбы или бега или подъема по лестнице) и проанализировать методы Partial least squares, либо Cross correlation analysis.

Задача 39

В задаче восстановления регрессии предполагается, что распределение зависимой переменной унимодально. А точнее, нормально. А как решить задачу восстановления регрессии, когда это распределение мультимодально (привести такие случаи)? Например, рассмотрим восстановления зависимой переменной, для выборки (\mathbf{x}_i, y_i),\quad i\in\{1, \dots, N\}, где неслучайная величина \mathbf{x}\in\mathbb{C} — комплексное число, а зависимая переменная, случайная величина  y\in\mathbb{R} — действительное число, измеренное с некоторой погрешностью. Объем N выборки достаточно велик. Требуется восстановить модель f=\ln(\mathbf{x}) (вставьте оптимизируемые параметры по вашему усмотрению). Сама независимая переменная может быть представлена в полярной форме, например \mathbf{x} = r\exp(i\theta),\quad r>0,\quad \theta =\phi\pm 2\pi, 4\pi, \dots. Предложить параметрическую модель, оценить параметры (можно и их дисперсию), нарисовать трехмерный график и проанализировать случай, когда погрешность велика.

Задача 40

Возможно ли сложную модель, например, глубокую нейросеть, обучить на выборке, которая содержит всего несколько элементов? Как определить оптимальный объем выборки? Как определить оптимальную сложность модели? Как согласовать эти две величины?

Задача 41

Процедура обучения модели, иначе процедура оптимизации ее параметров, описывает пошаговое изменение вектора параметров. Так как вектор параметров – это точка в пространстве параметров, то процедура описывает пошаговое преобразование пространства параметров. Цель процедуры – получение оптимального значения вектора параметров. Эта процедура имеет различные варианты.

  1. Детерминированная оптимизация – градиентный спуск, например, методом сопряженных градиентов.
  2. Стохастический градиентный спуск. Градиент вычисляется по случайно взятой подвыборке.
  3. Случайный поиск и варианты генетической оптимизации.
  4. Теоретико-игровая оптимизация: процедура является реализацией игровой стратегии.
  5. Дистилляция знаний: модель-ученик оптимизирует параметры с помощью фиксированной модели-учителя.
  6. Гиперсети: одна модель прогнозирует значения параметров другой.

Предлагается описать на выбор интересный, нетривиальный способ обучения модели и проиллюстрировать его графиками на синтетических данных.

Задача 42

Алгоритм Герхберга-Сакстона восстанавливает мнимую часть изображения по его действительной части. Итеративно выполняем прямое и обратное преобразование Фурье. После первого же преобразования появляется мнимая часть. Продолжаем до тех пор, пока ошибка реконструкции изображения в комплексном пространстве не стабилизируется. Этот алгоритм используется для восстановления синхротронных изображений кристаллов по амплитуде плоского когерентного излучения. Вопрос: можно ли таким образом повысить качество изображения с обычного фотоаппарата? Дополнение. Так как этот алгоритм был предложен в 1972 году, существуют его модификации. Если вспомнить, что преобразование Фурье линейно, то в качестве альтернативы рассмотрим нелинейное преобразование, например, автоэнкодер. 

Весна 2020

Про задачу kNN уже больше не надо рассказывать, перебор...

Задача 1

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

Задача 2

Задана выборка измерений акселерометра WISDM. Модель движения из шести классов движений задается вектором средних значений сегментов нескольких повторов движений одного класса. Предложить способ классификации выборки.

Задача 3

Заданы два временных ряда. Предложить алгоритм выравнивания (DTW, Rus, En), который ищет путь наименьшей стоимости не перебором, а методом градиентного спуска, приближая полиномом (третьей) степени.

Задача 4

Задан текст (например, «Вот дом, который построил Джек»). Преложить алгоритм, который бы по нескольким предыдущим словам прогнозировал бы следующее слово. Проанализировать ошибку прогноза.

Задача 5

Задан временной ряд с изменяющимся периодом. Предложить алгоритм, который отыскивает начало периода, пример: отсечение пика или как в [3].

Задача 6

Задано плоское черно-белое изображение односвязной фигуры (клякса). Предложить алгоритм, который бы указывал группу симметрии этой фигуры, если она имеется.

Задача 7

Задан фрагмент музыкального произведения. Предложить быстрый (например, хеширование изображения спектрограммы звука) алгоритм поиска в музыкальной базе Shazam.

Задача 8

В роман одного автора (Льва Толстого) поместили несколько абзацев другого (Михаила Зощенко). Предложить алгоритм, который бы находил бы смену стиля автора (кроме этого текста ничего нет, авторов мы не знаем). Можно представить текст как набор временных рядов или предложить другой способ представления текста для анализа.

Задача 9

Назовем двоичную, размера M,N, матрицу m-разреженной по строкам (n-разреженной по столбцам), если в каждой строке m пропущенных значений. Пропущенные значения в строке x восстанавливаются следующим образом. Находим ближайшую к ней строку y (расстояние Хемминга не превышает \rho), и заполняем пропущенные значения. Задана случайная матрица. Чему равняется максимальное значение n (или m), чтобы все пропущенные значения можно было бы восстановить?

Задача 10

Задана MIDI-партитура. Требуется спрогнозировать следующую ноту как (линейную) комбинацию предыдущих. Предложить алгоритм.

Задача 11

Нарисовать траекторию пошагового спуска к минимуму градиентного метода и имитации отжига. Сравнить их работу при поиске мимимума тестовой функции.

Задача 12

Предсказать сорт винограда из которого сделано вино, используя результаты химических анализов (описание данных), c помощью KNN - метода k ближайших соседей с тремя различными метриками. Построить график зависимости величины ошибки от числа соседей k.

Задача 13

Для выделения тем на коллекции документов используется матричное разложение. Предлагается определить к каким темам относится каждая из русских народных сказок. Для это следует построить словарь для коллекции документов. Построить матрицу строками в которой являются частоты слов из словаря, а число строк равняется числу сказок в коллекции. Сделать разложение матрицы "документ-слово" на матрицы "документ-тема" и "тема-слово" методом SVD. В качестве коллекции документов предлагается взять: А. Барто "Мячик", "Бычок", "Зайка". Документом считать 2 строки произведения. В качестве словаря взять 10-20 слов.

Задача 14

Используя данные о школьниках, выявить степень их алкогольной зависимости. В данных, взятых с UCI 'Students' (исходная выборка изъята из UCI, но осталась в других источниках), содержится информация о 30 признаках для каждого школьника, включая социальные и гендерные, а также указана материальная обеспеченность и количество свободного времени. Выбрать на свой взгляд наиболее весомые признаки и предсказать степень употребления алкоголя по выходным или будним по шкале от 0 до 5.

Задача 15

Нарисовать путь наименьшей стоимости между временными рядами, найденный с помощью алгоритма DTW. Ввести ограничения на вид пути в матрице с помощью техники "Sakoe-Chiba band". Показать, что при наименьшей величине отклонения пути от диагонали при этих ограничениях стоимость DTW перейдет в евклидово расстояние. Исследовать зависимость стоимости пути от величины ограничения. В качестве данных использовать синтетические временные ряды вида \sin ( x + c ) , \sin ( a  |\sin ( x ) | ) + \sin ( b x ) .

Задача 16

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

Задача 17

Идентификация видов стекла. Часто на месте преступления остаются осколки разных видов стекол, которые можно использовать как улики, если определить тип стекла и от каких оно объектов. Выборка состоит из 9 признаков - химических параметров образцов и 214 объектов. Необходимо каждому образцу сопоставить один из 6 классов (например: стекло автомобиля, осколок посуды, окно здания) и сравнить качество работы решающего дерева и алгоритма решающего дерева и алгоритма k-ближайших соседей. В качестве функции ошибки использовать долю неправильных ответов классификатора. Дает ли масштабирование признаков значительное улучшение в качестве классификации?

Задача 18

Распознавание британских гласных (11 штук) по данным с динамиков, рекомендуется использовать нормированные признаки (файл .scaled). Решить задачу многоклассовой классификации с помощью решающего дерева. Реализовать метод решающего дерева, построить область разделения на классы в проекции на любые 2 признака.

Задача 19

Классификация ядовитости грибов по основным признакам. Построить модель классификации на основе сети радиальных базисных функций. В качестве функции ошибки использовать метрику HEOM.

Задача 20

В крупную сеть гипермаркетов ежедневно выполняются поставки различных товаров. Требуется, использую временную историю спроса бананов за один год Goods, построить прогноз спроса товара на неделю. Для прогнозирования предлагается использовать алгоритм Гусеница, или SSA (Singular spectrum analysis).

Задача 21

Предсказание площади лесных пожаров. На основе погодных измерений необходимо предсказать объем выгоревших лесных массивов на севере Португалии. Выборка состоит из 13 признаков и 517 объектов. Для решения задачи предлагается использовать метод наименьших квадратов с регуляризацией. Нарисовать график весов признаков и общей ошибки на кросс-валидации при изменении параметра регуляризации. Какие признаки наиболее важны для нашей задачи? Что изменится, если предварительно все признаки стандартизовать?

Весна 2019

Задача 22

  • Решить задачу: классификации
  • на выборке: синтетической и https://archive.ics.uci.edu/ml/datasets/Lung+Cancer
  • с использованием моделей: kNN, SVM, логистическая регрессия
  • со структурными параметрами: число и состав признаков,
  • критерии качества AUC, F1, число признаков

Задача 23

  • Решить задачу: регрессии
  • на выборке: синтетической и https://drive.google.com/file/d/157SPnufv1VkxazY3H58HHqYJYpZ76Ghw/view?usp=sharing
  • с использованием моделей: линейная регрессия, PCA + линейная регрессия, простая нейросеть
  • со структурными параметрами: число и состав признаков, размерность скрытого пространства, структура сети
  • критерии качества: квадратичная ошибка, число обусловленности

Задача 24

  • Решить задачу: выбора алгоритма оптимизации
  • на выборке: синтетической и MNIST
  • с использованием моделей: нейронных сетей простой структуры
  • Предлагаемые алгоритмы: SGD, Nesterov Momentum, Adam
  • со структурными параметрами: структура сети
  • критерии качества: скорость сходимости, значения оптимума, вид траектории

Задача 25

  • Решить задачу: классификации
  • на выборке: синтетической и https://archive.ics.uci.edu/ml/datasets/Breast+Cancer
  • с использованием моделей: логистической регрессии, нейронной сети, градиентного бустинга
  • со структурными параметрами: состав признаков, структура модели, количество параметров модели
  • критерии качества: ROC AUC, PR кривая, сложность модели (ввести опеределение)

Задача 26

  • Решить задачу: кластеризации
  • На выборке: предобученных векторов fasttext, взять только слова из 20k.txt
  • С использованием модели: K-means
  • Со структурным параметром: K (число кластеров)
  • Критерии качества: внутрикластерное расстояние (евклидово расстояние и косинусная мера), межкластерное расстояние (евклидово расстояние и косинусная мера)

Задача 27

  • Решить задачу: классификации
  • На выборке: celeb-a, рассматривать изображения как черно-белые. В качестве метки класса рассматривать пол изображенного человека.
  • С использованием моделей: SVM, нейронная сеть с одним скрытым слоем.
  • Со структурным параметром: количество нейронов на скрытом слое, количество итераций оптимизации нейронной сети.
  • критерии качества: ROC AUC

Задача 28

  • Решить задачу: кластеризации/классификации
  • На выборке: MNIST
  • С использованием моделей: PCA + K-means
  • Со структурным параметром: количество главных компонент в PCA
  • С критериями качества: однородность кластеров, Accuracy (за ответ классификатора принимать наиболее представимый в кластере класс)

Задача 29

  • Решить задачу: классификации
  • На выборке: SemEval 2015 (http://alt.qcri.org/semeval2015/task2/data/uploads/sts2015-en-post.zip).
  • С использованием моделей: логистическая регрессия на центроидах векторов предложений, SVM, KNN, Decision Tree.
  • Векторы предложений: https://github.com/facebookresearch/fastText/blob/master/pretrained-vectors.md
  • В качестве меток класса брать округление оценок схожести (принимает значения от 0 до 5)
  • Со структурным параметром: глубина и структура деревьев, параметры регуляризации логистической регрессии и SVM, количество соседей в KNN
  • С критериями качества: Precision-Recall-кривая

Задача 30

  • Решить задачу: классификации
  • На выборке: тональность твиттер-сообщений http://thinknook.com/wp-content/uploads/2012/09/Sentiment-Analysis-Dataset.zip
  • С использованием моделей: логистическая регрессия на центроидах векторов предложений, нейронная сеть с одним скрытым слоем.
  • Векторы предложений: https://github.com/facebookresearch/fastText/blob/master/pretrained-vectors.md
  • Со структурным параметром: количество итераций оптимизации нейронной сети, размер скрытого слоя.
  • С критериями качества: ROC AUC, precision-recall-кривая


Тем, кто использует нейросети, важно понимать, что происходит внутри черного ящика.


Черновики простых задач по глубокому обучению

  • Выборки: используются те, которые часто встречаются в статьях, легко скачать. Желательно, чтобы они выкачивались питоновскими пакетами автоматически.
    1. Boston: есть код загрузки в sklearn: http://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_boston.html
    2. MNIST: есть код загрузки в TensorFlow (https://www.tensorflow.org/versions/r1.2/get_started/mnist/pros#load_mnist_data), Keras (https://keras.io/datasets/#mnist-database-of-handwritten-digits)
    3. CIFAR-10: есть код в TensorFlow (https://github.com/tensorflow/models/tree/master/tutorials/image/cifar10/), Keras (https://keras.io/datasets/#cifar10-small-image-classification)
    4. Celeb-A: набор лиц знаменитостей с 40 булевыми атрибутами для каждого лица, выборка достаточно часто упоминается в работах по GAN http://mmlab.ie.cuhk.edu.hk/projects/CelebA.html
    5. Frey Faces: игрушечный датасет с лицом одного человека, часто используется в статьях по генеративным моделям https://cs.nyu.edu/~roweis/data.html
    6. Текстовые корпусы из nltk, выкачиваются в одну команду https://www.nltk.org/book/ch02.html
  • По задачам:
    1. В работе по GAN'ам (https://arxiv.org/pdf/1709.06548.pdf) был очень простой эксперимент на паре выборок <картинки из MNIST, транспонированные картинки из MNIST>, где сеть училась делать транспонирование, при этом задача рассматривалась как semi-supervised. Можно попробовать изучить, какое количество объектов потребуется простому автокодировщику, чтобы выучить операцию транспонирования.
    2. В статье (https://omoindrot.github.io/triplet-loss) рассматривались различные подходы к Metric Learning на основе триплетов. Можно провести сравнение стратегий Hard triplets, Easy triplets, Semi-hard triplets и случайных триплетов для какой-нибудь выборки. Результатом может быть визуализация, схожая с последним графиком из статьи.
    3. В работе (https://arxiv.org/pdf/1711.00464.pdf) рассматривается модификация функции потерь вариационного автокодировщика с разными коэффициентами на D_KL и ошибку реконструкции. Если коэффициент D_KL высокий - то модель хорошо работает как генеративная, если коэффициент D_KL низкий, то модель лучше восстанавливает исходную выборку. Можно повторить схожий эксперимент с лицами, получится наглядный график, как Figure 4 из статьи.
    4. Можно обучить модель перевода или что-то похожее на Seq2Seq: https://blog.keras.io/a-ten-minute-introduction-to-sequence-to-sequence-learning-in-keras.html Интересно было бы посмотреть как меняется перевод при снижении количества параметров.
    5. Есть простой пример посимвольной генерации текста на Keras: https://github.com/keras-team/keras/blob/master/examples/lstm_text_generation.py Здесь можно поэкспериментировать с температурой при генерации.

Пожелания (но не указания)

Слайды желательно делать с комментариями, достаточными для передачи сообщения аудитории. Графики должны иметь подписанные оси и поясняющий текст с выводом - результатом анализа.

  1. Цель вычислительного эксперимента, описание выборок, список моделей
  2. Список функций ошибки, критериев качества
  3. Способ разбиения выборки на обучение-контроль (выбрать)
  4. Таблица модели/выборки/критерии качества на разбиении со ст. откл.
  5. Анализ выбранной модели на разбиении обучение-контроль
    1. График зависимости функции ошибки от значения структурного параметра со ст. откл.
    2. График зависимости функции ошибки от объема выборки со ст. откл.
    3. График скорости сходимости функции ошибки (зависимости функции ошибки от номера итерации оптимизационного алгоритма) со ст. откл.
  6. Пожалуйста, называйте файлы со своими решениями Surname2019ProblemN для этих задач (или Surname2019ProblemOldN для задач прошлых лет внизу списка).

Весна 2018 и ранее

Эти задачи тоже можно решать

  1. Восстановить регрессию используя формулу Надарая-Ватсона. Нарисовать восстановленную функцию с различными ядрами и шириной окна. В качестве данных использовать выборку цены на хлеб или цены на электроэнергию.
  2. 2D визуализация N-мерных данных с помощью PCA.

Курс "Machine Learning" на Coursera: 7_pca.m script and 2.5 part of exercise 7 [4]. Визуализировать результаты на плоскости, оценить ошибку.

  1. Заполнение пропусков в данных приложения Сardiomood. Сравнить различные методы заполнения пропусков [1]: 1) метод замены пропущенного значения средним из ближайших присутствующих элементов переменной, 2) метод восстановления пропущенного значения сплайн-интерполяцией по присутствующим элементам, 3) метод восстановления пропущенного значения на основе использования Zet-алгоритма [1]. Сравнение делать оценивая близость восстановленных пропусков с реальными данными.
  2. Классифицировать заемщиков кредита с помощью логистической регрессии. Для оптимизации параметров использовать алгоритм Ньютона-Рафсона или алгоритм градиентного спуска. Построить ROC-кривые для фиксированного числа разбиений. Построить ряд графиков для различных мощностей подвыборок разбиений.

Число итераций ограничить либо условием на сходимость – норма разности последовательных векторов весов не больше точности, либо числом шагов.

  1. Разметить коллекцию писем. Предполагается, что некоторая часть коллекции является спамом, нужно отделить эти письма от всех остальных. Использовать алгоритм кластеризации k-means. Число кластеров установить равным двум. Попробовать различные стратегии инициализации. Сравнить результаты работы алгоритма с реальной разметкой коллекции на спам.
  2. Оценить число главных компонент в данных с помощью метода сломанной трости. Для нахождения главных компонент применить МГК. Построить график зависимости величины ошибки описания объектов в базисе из главных компонент от числа главных компонент. По графику оценить собственную размерность пространства.
  3. Построить прогноз энергопотребления на 24 часа вперед методом векторной авторегрессии (см. постановку задачи, пример реализации). Построить график, сравнить истинное поведение потребления и прогноз. Рассмотреть зависимость функции ошибки на прогнозе от длины использованной предыстории, имеет ли место переобучение?
  4. Приближение элементов изображения линией или поверхностью.
    • Требуется нарисовать приближающую прямую, окружность или другую линию или поверхность по вашему усмотрению на одном из следующих изображений или на вашем изображении. Предобработка изображений (как и вообще, всё, что приводит к результату, разрешается). Обсуждаем постановку задачи и решение, а не техническую сторону (не то, как это было запрограммировано).
    • Для справки. Как приблизить множество точек на плоскости прямой линией или полиномом, написано здесь. Как найти центр и радиус окружности написано здесь. Как найти фокусы приближаюшего эллипса, можно понять из п. 2 и Википедии [5], [6]. Алгоритм, приближающий множество точек в пространстве поверхностью, приведен здесь [7], смотрите также список примеров.
    • Развитие задачи: рассказать, как решить эту задачу 1) для произвольной размерности пространства 2) методом главных компонент.
  5. С помощью логистической регрессии разделить два класса точек на плоскости. Результаты изобразить на графиках (см. пример Classification using logistic regression). Рассмотреть случаи линейно разделимой и неразделимой выборок.
  6. Изобразить на рисунке Парето-расслоение множества точек на плоскости. (Парето-расслоение - набор последовательно вычисляемых Парето оптимальных фронтов. Первый фронт вычисляется для полной выборки и удаляется из нее. Для оставшихся данных вычисляется следующий слой и т.д)
  7. Дана выборка "Вина различных регионов". Требуется определить кластеры (регионы происхождения вин) и нарисовать результат: цветной точкой обозначен объект кластера; цветным кружком обозначен класс этого объекта, взятый из выборки. Вариант задания: определить число кластеров. Вариант задания: использовать два алгоритма, например k-means и EM, и показать сравнение результатов кластеризации на графике.
  8. Сгладить временной ряд Цены (объемы) на основные биржевые инструменты методом экспоненциального сглаживания. Нарисовать цветные графики сглаженных с различным  \alpha рядов и исходного ряда.
  9. Аппроксимация выборки замкнутой кривой [8]: проверить, лежат ли точки на окружности? Сгенерировать данные самостоятельно. Построить графики для случая когда точки лежат на окружности и нет, на графиках изобразить выборку и аппроксимирующую окружность.
  10. Дан временной ряд с пропусками, например [9]. Предложить способы заполнения пропусков в данных, заполнить пропуски. Для каждого способа построить гистограмму. Вариант: взять выборку без пропусков, удалить случайным образом часть данных, заполнить пропуски, сравнить гистограмму восстановленной выборки с гистограммой исходной выборки.
  11. Дана выборка "Вина различных регионов". Выбрать два признака. Рассмотреть различные функции расстояния при классификации с помощью метода ближайшего соседа. Для каждой изобразить результат классификации в пространстве выбранных признаков.
  12. Для различных видов зависимости  y = f(x) + \epsilon (линейная, квадратичная, логарифмическая) построить линейную регрессию и нарисовать на графике SSE-отклонения (среднеквадратичные отклонения). Данные сгенерировать самостоятельно или взять данные "Цена на хлеб".
  13. Оценить площадь единичного круга методом Монте-Карло. Построить график зависимости результата от размера выборки.
  14. Дана выборка: ирисы Фишера. Реализовать процедуру классификации методом решающего дерева. Проиллюстрировать результаты классификации на плоскости в пространстве двух признаков.
  15. Задан временной ряд – объемы почасового потребления электроэнергии (выбрать любые два дня). Аппроксимировать ряд полиномиальными моделями различных степеней (1-7). *Предложить метод определения оптимальной степени полинома.
  16. Задано два одномерных временных ряда различной длины. Вычислить расстояние между рядами методом динамического выравнивания. На графике изобразить путь наименьшей стоимости.
  17. Сгенерировать набор точек на плоскости. Выделить и визуализировать главные компоненты.
  18. Аппроксимировать выборку цены на хлеб полиномиальной моделью. Нарисовать график. Выделить объекты, являющиеся выбросами, используя правило трех сигм, и отметить их на графике.
  19. Разделить выборку ирисы Фишера на кластеры. Проиллюстрировать на графиках результаты кластеризации для различного числа кластеров, выделить кластеры разными цветами.
  20. Дана выборка из нескольких признаков, без целевого вектора Y. Например, эта https://dmba.svn.sourceforge.net/svnroot/dmba/Data/Diabets_LARS.csv Требуется указать тот признак, который хорошо описывается (в терминах линейной регрессии) остальными (такой признак обычно исключают из выборки). Предложить способ визуализации решения (например, с помощью ковариационной матрицы).
  21. Сгенерировать выборку случайным образом и воссстановить ее плотность методом парзеновского окна. Взять несколько окон разной длины и изобразить результаты на одном рисунке. Рассмотреть различные способы порождения данных.
  22. Показать разницу в скорости выполнения матричных операций и операций в цикле. Можно использовать в качестве примера Сингулярное разложение и другие методы линейной алгебры. Показать эффективность параллельных вычислений (parfor). Результаты представить в виде диаграммы (bar chart).
  23. Разобраться как работает суперпозиция функций. С помощью функции @ породить все возможные полиномы от n переменных степени не более p. Вариант: приблизить полученными полиномами временной ряд цен на хлеб (данные).
  24. Дан набор трехэлементных векторов. Первые два элемента нарисовать по осям абсцисс и ординат. Третий элемент отобразить как круг с пропорциональным радиусом. Пропорции подобрать исходя из чувства прекрасного. Сравнить полученный график с plot3. Что лучше?
  25. Построить методом наименьших модулей уравнение регрессии 2ой степени по результатом опытов, данные прилагаются (x1,x2,x3 - переменные факторы, N - отклик). Вариант: сравнить с методом наименьших квадратов, построив на одном рисунке 2 графика (по оси абсцисс - истинные отклики, по оси ординат - результаты моделирования с помощью МНМ и МНК)
  26. Разобраться как работает regexp в Матлабе. Сделать код, который выделяет все, что находится внутри скобок некоторого арифметического выражения. Визуализировать работу regexp.
  27. Дан временной ряд из m + 1 (случайных) точек. Приблизить m его первых точек полиномами степени от 1 до m. Вычислить среднюю ошибку в точках. Какая степень дает наибольшую ошибку?
  28. Аппроксимировать выборку цены на хлеб полиномиальными моделями различного порядка. Построить на одном рисунке два графика: качество аппроксимации на обучении и на контроле в зависимости от степени полинома.
  29. Предложить способы визуализации наборов четырехмерных векторов, например для Fisher's iris data.
  30. Дан временной ряд, описывающий потребление электричества. Приблизить ряд несколькими криволинейными моделями и нарисовать спрогнозированные и исходный ряды на одном графике.
  31. Дана выборка, в которой есть несколько выбросов. Известно, что она может быть описана одномерной линейной регрессией. Требуется переборным путем найти выбросы. Показать их на графике.
  32. Дана выборка из двух классов на плоскости. Требуется разделить ее линейно и найти все объекты, которые залезли в чужой класс. Показать их на графике.
  33. Решается задача заполнения пропусков в социологических анкетах наиболее адекватными значениями. Основная идея: для фиксированной анкеты найти заполнить ее пропущенные поля с использованием значений соответствующих полей k ближайших соседей. Задана выборка X --- матрица, в которой элемент x_{ij} принадлежит конечному множеству \mathbb{L}_j=\{1,...,k_j,\text{NaN}\} допустимых значений j-го поля анкеты; отметка \text{NaN} означает пропуск в поле. На множестве \mathbb{L}_j задано отношение предпочтения \preceq. Например, "начальное образование" \preceq «среднее образование» \preceq «высшее образование» --- отношение линейного порядка. Требуется ввести такую функцию расстояния или метрику \rho(x_i,x_k)\rightarrow \mathbb{R}\cup\text{NaN}, которая бы обеспечивала наиболее полное восстановление пропусков, и описать процедуру восстановления. Дополнительно: изменится ли ваше решение, в случае, когда каждая анкета имеет не менее одного пропуска. Вариант: каждое поле имеет не менее одного пропуска. Вариант: значительная часть элементов матрицы X пропущена.
Личные инструменты