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

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

Версия от 17:44, 14 мая 2008; Yury Chekhovich (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

Курс лекций состоит теоретической и прикладной частей. Теоретическая часть рассматривает обоснование применимости методов для решения определенных задач. Прикладная часть включает ряд заданий по написанию алгоритмов регрессионного анализа на языке системы 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))²)$ от единственного параметра $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 не позволяет использовать инлайн-функции в качестве аргументов.

Параметры	w	w(1)	w(2)	w(3)	w(4)	w(5)
Фиксированные	NaN	NaN	NaN	NaN	0.2	NaN
Линейные	wlin	1	1	0	NaN	1
Начальные	wini	0.1	1	1	NaN	0
Максимум	wmin	-100	NaN	-100	NaN	-100
Минимум	wmax	100	NaN	100	NaN	100

Требуется:

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

Задание 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.

Требуется:

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

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

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

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

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

Литература

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.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BA%D0%BB%D0%B0%D0%B4%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F_%D0%B8_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_B.%D0%92.%D0%A1%D1%82%D1%80%D0%B8%D0%B6%D0%BE%D0%B2%29»

Категории: Учебные курсы | Регрессионный анализ

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты