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

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

Версия 17:44, 14 мая 2008

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практика. Дана нелиненная регрессионная модель . Задана выборка. Требуется оценить параметры .

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

• Аппроксимация совместного распределения параметров и гиперпараметров модели.
• Аппроксимация функции ошибки рядом Тейлора.
• Вычисление нормирующей константы апостериорного распределения .
• Аппроксимация Лапласа: пример для одной и для нескольких переменных.
• Вывод гиперпараметров, плотность распределения в первом и втором уровне Байесовского вывода.
• Генетический алгоритм порождения и выбора регрессионных моделей.

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

Лекция 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 не позволяет использовать инлайн-функции в качестве аргументов.

Требуется:

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

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

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

Дано:

• Выборка с несколькими свободными переменными — файл.
• Набор порождающих функций свободных переменных (можно использовать список стандартных, требуется только задать этот список).
• Набор внешних критериев (три критерия).
• Список преобразований свободных переменных. Пользователь задает список преобразований свободных переменных.
• Пример линейной модели: [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.