Прикладная регрессия и оптимизация, программа курса (осень 2006)

Московский физико-технический институт, Факультет управления и прикладной математики, 6-й курс

МФТИ, ФУПМ, группа 175б. Аудитория 355 ВЦ РАН, по средам 10:40.

Литература

  1. MacKay, D. Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003. Дальше...
  2. Nabney, Yan T., Netlab: Algorithms for pattern recognition. Springer, 2004.
  3. Malada, H. R. and Ivakhnenko, A. G. Inductive Learning Algorithms for Complex Systems Modeling, CRC Press, 1994.
  4. Friedman, J., Hastie, T. Tibshirani, R. The Elements of Statistical Learning. Springer, 2001.
  5. Брандт З. Анализ данных. М.: Мир, 2003.
  6. Голуб Дж., Ван-Лоун Ч. Матричные вычисления - М.: Мир, 1999.
  7. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. - М.: Мир, 1969.
  8. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. - М.: Финансы и статистика, 1989.

Практика

На каждую неделю назначаются задания. Выполненные задания нужно отправлять по адресу, указанному внизу этой страницы. Структура отправляемых файлов должна быть следующей (см. пример — maximov.zip).

  1. Создается папка "[LastName]", в которой будут находиться все файлы.
  2. Стартовые файлы находятся в этой папке и имеют начало "run_".
  3. Файлы "*.m", которые относятся к данному заданию, находятся в папке "code".
  4. Файлы "*.m" c библиотечными моделями находятся в папке "func".
  5. Файлы со входными данными, находятся в папке "data".
  6. Файлы с графиками и отчеты находятся в папке "report".
  7. Корневая папка архивируется в "[LastName].zip" и отправляется по нижеуказанному адресу.

Скачать пример: maximov.zip.

Лекция 1

Темы. План лекций, организация практических работ. Терминология: приближение функций, аппроксимация, интерполяция, регрессия. Обозначения. Постановка задач регрессии. Что такое модель регрессии. Метод наименьших квадратов. Приемы работы с Matlab.

Задание. Методом наименьших квадратов найти для регрессионной модели — квадратичного полинома — параметры w, приближающие выборку 'quaddata.csv'. Нарисовать график функции и данные. Данные находится в файле 'maximov.zip'.

Полезные материалы. Обзор приемов работы с Matlab: intro.m (вставлен пример с многомерной матрицей, улучшение кода этого примера приветствуется). Пример созданной функции: to01.m (поместить в папку 'code'). Метод наименьших квадратов run_mnk.m и данные к примеру mnk.csv. Иллюстрация к методу наименьших квадратов mnk.gif.

Следующая тема. Сингулярное разложение. Метод главных компонент. Подстановки в линейных моделях.

Лекция 2

Темы. Сингулярное разложение. Свойства сингулярного разложения. Примеры применения: поведение системы в экстремальных условиях, сегментация Фишера, кластеризация с ограничением размерности пространства. Метод главных компонент. Подстановки в линейных моделях.

Задание. Подбор нелинейных подстановок для решения задачи линейной регрессии. Требуется "угадать", какие подстановки требуется сделать, чтобы найди регрессионную модель для данных problem2.csv (также как и раньше, первый столбец — свободная переменная, а второй — зависимая). Для решения задачи необходимо нелинейные параметры подобрать вручную, а линейные — методом наименьших квадратов. Нарисовать график полученной модели и данных на графике с указанием найденной функции в заголовке. Для обращения матрицы следует использовать сингулярное разложение. Написанный к этому заданию код сохранить в файле run_problem2.m.
Внимание! Пожалуйста, переименуйте файл для предыдущего задания (Лекция 1) в run_problem1.m.

Полезные материалы. Примеры трех функций подстановки: m_gauss.m, m_sin.m и m_poly.m. Совет: в связи с тем, что производительность алгоритмов по поиску моделей существенно зависит от наполнения моделей, не следует вставлять проверки "data match" в эти функции. Проверки на соответствие размеров векторов лучше вставлять в вызывающие модули, а размеры тщательно документировать.

Следующая тема. Регуляризация.

Лекция 3

Темы. Библиотечные модели. Метод главных компонент (окончание). Пространства, порождаемые сингулярными векторами. Матричные нормы и обусловленность. Некорректно поставленные задачи. Регуляризация для МНК, SVD, PCA. Шкалы оценок и Расслоение Парето. Пример: интегральные индикаторы и экспертные оценки. Отыскание параметра регуляризации и согласование оценок — линейное и квадратичное.

Задание. Дана (7x2)-матрица A, файл problem3.csv. Требуется найти ее первую главную компоненту и нарисовать проекции векторов-строк матрицы A на первую главную компоненту. Пример рисунка: problem3.png.

Полезные материалы. Некоторые приемы работы с графикой: run_problem3.m. Метод главных компонент run_plot1PC.m. Проекции векторов на главные компоненты pca.gif.

Следующая тема. Метод группового учета аргументов — внешние критерии.

Лекция 4

Темы. История и особенности МГУА. Принцип МГУА. Внешние и внутренние критерии. Разделение выборки на две части. Принятые обозначения. Критерий регулярности, критерий минимального смещения, критерий предсказательной способности. Комбинированные критерии — линейная комбинация. Оптимальность в пространстве внешних критериев и Парето-оптимальный фронт. Базовая модель МГУА. Подстановки в базовой модели.

Задание. Дана выборка, файл problem4.csv. Первые 10 точек являются обучающими, остальные — контрольными. Требуется вычислить внешний критерий (критерий регулярности) для линейной модели.

Полезные материалы. Заготовка функции критерия регулярности: met_regularity.m.

Следующая тема. МГУА, однорядные и многорядные алгоритмы поиска моделей. Генетические оптимизационные алгоритмы.

Лекция 5

Темы. Базовая модель МГУА: модель Колмогорова-Габора. Последовательность шагов и критерии остановки алгоритма. Многорядный алгоритм: линейная комбинация заданного числа нелинейных подстановок. Комбинаторный алгоритм. Матрица вхождения мономов в базовую модель. Генетический алгоритм: последовательность шагов. Представление. Селекция: алгоритм рулетки. Скрещивание. Мутация. Параметры алгоритма. Сравнение алгоритмов глобальной и локальной оптимизации. Метаоптимизация — оптимизация параметров оптимизирующего алгоритма. Регрессия в метаоптимизации.

Задание. Дана выборка, файл problem5.csv. Первые 30 точек являются обучающими, остальные — контрольными. Первый и второй столбец — свободные переменные, последний — зависимая. Требуется написать комбинаторный алгоритм и с помощью критерия регулярности отыскать оптимальную полиномиальную модель. Совет: для отладки можно использовать файл problem4.csv.

Полезные материалы. Очень полезные счетчики: cntabover.m и cntabappend.m. Функция показа трехмерных моделей surfplot.m

Следующая тема. Обозначения для базовой модели нескольких переменных с подстановками (обобщение). Четыре типа алгоритмов порождения моделей. Гипотезы порождения данных.

Лекция 6

Темы. Постановка задачи для многомерной регрессионной модели и множества подстановок безпараметрических гладких нелинейных функций одного аргумента. Подстановки для мономов в базовой модели. Теорема Колмогорова о представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного. О том, как эксперты строят модели — сильные и слабые стороны (линейная регрессия, полиномиальные модели, нейронные сети, МГУА, МГУА с подстановками, произвольная суперпозиция). Интерпретируемость моделей. Четыре способа порождения моделей. Гипотеза порождения данных. Функция распределения и плотность распределения. Наивный метод оценки параметров распределения.

Задание.

Полезные материалы. О том, как рисовать несколько графиков в одном окне, часть кода txt_subplotexample.m. Комментарий: через переменную y1 обозначены значения, которые принимает модель на элементах выборки свободных переменных.

Следующая тема. Метод наибольшего правдоподобия.

Лекция 7

Темы. Два отображения в задачах регрессии: f : X → Y и f : X x W → Y. Представление элементов одной выборки как независимых случайных величин с заданной плотностью распределения. Совместная плотность распределения. Определение функции наибольшего правдоподобия L. Фиксация одного из двух аргументов функции  L. Пример вычисления L для 1) дискретного и 2) непрерывного множества значений оцениваемых параметров. Вычисление оценок параметров одномерного Гауссова распределения. Примеры построения целевой функции в пространстве параметров W. Примеры обнаружения инвариантов с использованием целевой функции, определенной на W. Примеры вычисления устойчивости моделей с помощью интеграла целевой функции для заданной области в W. Гипотеза аддитивного Гауссова шума с нулевым средним. Гиперпараметры. Гипотеза о штрафе больших весов в линейных моделях. Константа Липшица и гипотеза о шуме. Ошибка в пространстве данных и ошибка в пространстве весов.

Задание.Задана регрессионная модель y = - 3.14 x3 + 2.71 x. Данные, по которым была построена эта модель , находятся в файле problem7.csv. Требуется оценить дисперсию аддитивного Гауссова шума с нулевым средним, пользуясь введенным определением гиперпараметра и функционалом распределения (memento).

Полезные материалы. Подсказка: можно оценить ее методом перебора значений в заданном интервале, но есть и другие варианты. Функция плптности met_pDwb.m и самый простой пример.

Следующая тема. Совместный двухуровневый Байесовский вывод.

Лекция 8

Темы. Первый уровень Байесовского вывода. Функция распределения в пространстве параметров. Правдоподобие моделей. Байесовский критерий сравнения моделей. Пример сравнения моделей с параметрами, принимающими значения в конечном множестве. Механизм двухуровневого Байесовского вывода, схема проведения вычислительного эксперимента. Достоверность. Множитель Оккама, определение. Сравнение моделей. Изменение апостериорного распределения параметров после получения данных. Пример сравнения трех моделей с различным априорным и апостериорным распределением параметров.

Задание. Дана нелиненная регрессионная модель y = sin(w1sin(x))+w2x. Данные, по которым была построена эта модель находятся в файле problem8.csv. Требуется оценить параметры w1, w2, график problem8.png.

Полезные материалы. Читай doc nlinfit. Очень полезный инструмент.

Следующая тема. Применение гиперпараметров.

Лекция 9

Темы. Постановка задачи с точки зрения эксперта в предметной области. Схема работы аналитика при поиске модели. Ограничения, накладываемые при моделировании. Модель как произвольная суперпозиция. Пример автоматического построения модели давления в камере сгорания дизельного двигателя. Роль гиперпараметров при оценке информативности свободных переменных. Функция распределения случайной переменной в пространстве данных, функция распределения параметров в пространстве параметров. Связь гиперпараметров и дисперсий в обоих пространствах. Выбор наиболее информативных элементов модели.

Задание. Дана нелиненная регрессионная модель y = sin(w1x1+w2) cos(w3x2+w4). Данные, по которым была построена эта модель находятся в файле problem9.csv. Требуется оценить параметры w1,…, w4, график problem9.png. Нарисовать исходные данные и полученную модель. Дана нелиненная регрессионная модель двух свободных переменных y = sin(w1x1+w2) cos(w3x2+w4). Данные, по которым была построена эта модель находятся в файле problem9.csv. Требуется оценить параметры w1,...,w4, график problem9.png.

Полезные материалы. Функция построения графика зависимости зависимой переменной от двух свободных, surfplot.m. Совет. Если параметры начального приближения выбраны недостаночно точно, результаты оптимизации будут некорректными. Также см. статью о выводе гиперпараметров, strijov06poisk_jct.pdf

Следующая тема. Вывод гиперпараметров.

Лекция 10

Темы. Аппроксимация совместного распределения параметров и гиперпараметров модели. Аппроксимация функции ошибки S(w) рядом Тейлора. Вычисление нормирующей константы ZS апостериорного распределения p(w|D,alpha,beta). Аппроксимация Лапласа: пример для одной переменной. Вывод гиперпараметров, плотность распределения p(D|alpha,beta) в первом и втором уровне Байесовского вывода. Генетический алгоритм порождения и выбора регрессионных моделей.

Задание. Больше заданий в семестре не предполагается.

Следующая тема. Однокритериальная и многокритериальная оптимизация.

Лекция 11

Темы. Постановка задачи однокритериальной оптимизации. Алгоритмы локальной и глобальной оптимизации. Мультистарт локальной оптимизации. Алгоритм Нельдера-Мида. Алгоритм моделируемого отжига и задача коммивояжера. Тестовые задачи однокритериальной оптимизации. Постановка задачи многокритериальной оптимизации. Пространство аргументов и целевое пространство. Парето-оптимальный фронт. Проблема постановки задачи оптимизации — один критерий или много критериев? Задачи регуляризации и многокритериальная оптимизация: регуляризация в двухуровневом Байесовском выводе, в методе наименьших квадратов, регуляризация ковариационной матрицы; выбор модели пространстве внешних критериев МГУА. Тестовые задачи многокритериальной оптимизации. Отображение пространства аргументов в целевое пространство: использование стохастических алгоритмов или алгоритмов полного перебора.

Следующая тема. Построение оптимизационной системы.

Лекция 12

Темы. Методы многокритериальной оптимизации. Линейная комбинация целевых функций. Целевое программирование (goal programming). Стремление к цели (goal attainment) — целевое программирование со скалярным параметром. Лексикографическое упорядочивание  — оптимизация целевых функций по отдельности. Особые точки ПОФ  — утопия, антиутопия, надир. Направленный поиск (direct-based search). Архитектура системы многокритериальной оптимизации. Работа оптимизационного алгоритма с модулями системы.

Следующая тема. Заключение.

Лекция 13

Темы. Регрессия и классификация. Использование методов регрессии при решении задач классификации. Сравнение непараметрических и параметрических методов. Адекватность полученных результатов и гипотеза перемешивания. Основные математические объекты, обсуждаемые в рамках курса «Прикладная регрессия и оптимизация», их взаимосвязь. Архитектура системы поиска оптимальных регрессионных моделей.

Экзамен 19 декабря 2006 г., аудитория 355

Теория. Требуется ответить на основной вопрос, указанный в билете (номер билета есть номер лекции) и на два дополнительных вопроса.

Практика. Принести с собой USB flash memory со всеми заданиями. Задания должны быть выполнены в ранее указанном формате.

Благодарности

Хочу отметить Андрея Ивахненко, Дмитрия Житлухина и Галину Иофину за вопросы, которые они задавали в ходе лекций, за то, что разобрались в теме и за ответственность при выполнении практических заданий.

В. В. Стрижов