Прикладная регрессия и оптимизация (курс лекций, B.В.Стрижов)

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

Перейти к: навигация, поиск

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

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

Курс читается студентам 6-го курса кафедры «Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ с 2006 года. От студентов требуется знание линейной алгебры и математической статистики.

Содержание

Огранизация курса

Семестровый курс содержит 32 часа лекций и 32 часа практических занятий. Экзамен состоит из теоретической части и задач. До экзамена нужно сдать практические работы.

Лекция 1. Введение в регрессионный анализ

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

Практика. Методом наименьших квадратов найти для заданной линейной регрессионной модели (например, квадратичного полинома) параметры \mathbf{w}, приближающие выборку (первые N столбцов — свободная переменная, последний столбец — зависимая). Нарисовать график функции и данные.

Лекция 2. Вычислительные линейные методы

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

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

Лекция 3. Регуляризация в линейных методах

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

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

Лекция 4. Метод группового учета аргументов и скользящий контроль

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

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

Лекция 5. МГУА, алгоритмы поиска моделей

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

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

Лекция 6. Нелинейная регрессия

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

Практика. Для выборки и заданной модели одного параметра построить пару графиков. Первый график — данные и приближающая эти данные модель. Второй график — зависимость целевой функции p_1=-\log(\sum(y_i-f(w, x_i))^2) от единственного параметра w модели.

Даны три выборки (первый столбец — свободная переменная, второй, третий, четвертый — три реализации зависимой переменной). Задана модель. Даны три целевые функции

p_1=-\log\sum(y_i-f(w, x_i))^2,
p_2=-\log\sum|y_i-f(w, x_i)|,
p_3=-\log\max|y_i-f(w, x_i)|.

Сравнить полученные пары графиков.

Лекция 7. Гипотеза порождения данных и метод наибольшего правдоподобия

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

Практика. Задана регрессионная модель y=-3.14x^3+2.71x. Задана выборка. Требуется оценить дисперсию аддитивного Гауссова шума с нулевым средним, пользуясь введенным определением гиперпараметра и функционалом распределения. Подсказка: можно оценить ее методом перебора значений в заданном интервале, но есть и другие варианты.

Лекция 8. Связанный двухуровневый Байесовский вывод

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

Практика. Дана нелиненная регрессионная модель y=\sin(w_1\sin(x))+w_2x. Задана выборка. Требуется оценить параметры w_1,w_2.

Лекция 9. Аппроксимация Лапласа

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

Практика. Дана нелиненная регрессионная модель y=\sin(w_1x_1+w_2)\cos(w_3x_2+w_4). Задана выборка. Требуется оценить параметры w_1,\ldots, w_4. Нарисовать исходные данные и полученную модель. Дана нелиненная регрессионная модель двух свободных переменных y=\sin(w_1x_1+w_2)\cos(w_3x_2+w_4). Требуется оценить параметры w_1,\ldots,w_4. Нарисовать графики.

Лекция 10. Организация вычислительного эксперимента

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

Лекция 11. Однокритериальная и многокритериальная оптимизация в регрессии

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

Лекция 12. Построение оптимизационной системы

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

Лекция 13. Заключение

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

Практика, дополнительные задания

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

Дано:

  • Не менее трех выборок, с одной, двумя, тремя свободными переменными. Выборки не должны быть тривиальны.
  • Набор библиотечных функций, не менее 12 функций. Функция принимает вектор параметров, вектор или матрицу свободных переменных и возвращает значения зависимой переменной.
  • Пользователь строит из библиотечных функций модель, определяет для нее начальные параметры и область допустимых значений каждого параметра.
  • Пример модели fstr = 'w(1)*x(1)+w(2)*sin(w(3)*x(1)+w(4))+w(5)'; Внимание: Использовать конструкцию f = inline(fstr,'w','x'); лучше только для собрки модели, так как inline не позволяет использовать инлайн-функции в качестве аргументов.
Параметрыww(1)w(2)w(3)w(4)w(5)
ФиксированныеNaNNaNNaNNaN0.2NaN
Линейныеwlin110NaN1
Начальныеwini0.111NaN0
Максимумwmin-100NaN-100NaN-100
Минимумwmax100NaN100NaN100

Требуется:

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

Задание 2. Построение линейных регрессионных моделей методом группового учета аргументов

Внимание: дополнительная информация к заданию n содержится в заданиях от 1 до n-1.

Дано:

  • Выборка с несколькими свободными переменными — файл.
  • Набор порождающих функций свободных переменных (можно использовать список стандартных, требуется только задать этот список).
  • Набор внешних критериев (три критерия).
  • Список преобразований свободных переменных. Пользователь задает список преобразований свободных переменных.
  • Пример линейной модели: [x(:,1), sin(0.5*x(:,1)), log(x(:,1)), x(:,2), exp(x(:,2), log(x(:,2)), x(:,3), log(x(:,3))];

Требуется:

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

Задание 3. Построение набора нелинейных моделей путем индуктивного порождения

Дано:

  • Две выборки с одной и с двумя свободными переменными — файлы.
  • Библиотека порождающих функций. Можно взять из списка в статье.
  • Для каждой порождающей функции задан набор параметров — файл.
  • Набор моделей начального приближения.
  • Пример построения набора моделей начального приближения см. здесь.
  • Пример организации структуры суперпозиции в генетическом программировании см. здесь.

Требуется:

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

Задание 4. Вычисление Парето-оптимального фронта в пространстве критериев качества регрессионных моделей

Дано:

  • Две выборки с одной и с двумя свободными переменными — файлы.
  • Набор линейных моделей — файл, структура произвольная.
  • Набор критериев. (Три внешних критерия и три внутренних).

Требуется:

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

Задание 5. Генетическое программирование и метод группового учета аргументов

Дано:

  • См. Задание 2.

Требуется:

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

Выполнение практических заданий

Рекомендации по выполнению заданий

  • Создается папка «YourLastName», в которой будут находиться все файлы.
  • Стартовые файлы находятся в этой папке и имеют начало «run_problemX».
  • Файлы «*.m», которые относятся к данному заданию problemX с номером X, находятся в папке «code».
  • Файлы «*.m» c библиотечными моделями находятся в папке «func».
  • Файлы со входными данными, находятся в папке «data».
  • Файлы с графиками и отчеты находятся в папке «report».
  • Корневая папка архивируется в «YourLastName.zip» и отправляется по нижеуказанному адресу.
  • Скачать пример: [1]

Рекомендации для дополнительных заданий

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

Что такое краткое руководство пользователя?

Человек, знающий основы Матлаба должен в течение краткого времени разобраться в вашей системе. Для этого ему нужно объяснить следующее.

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

Литература

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