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

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

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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p_1=-\log\sum(y_i-f(w, x_i))²,
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³+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.
Личные инструменты