Оценка сложности регрессионных моделей (пример)
Материал из MachineLearning.
(→Вычисление размерности Вапника-Червоненкиса) |
(→Исходный код) |
||
(20 промежуточных версий не показаны.) | |||
Строка 23: | Строка 23: | ||
- | Рассматривается линейная регрессионная модель | + | Рассматривается [[Многомерная линейная регрессия|линейная регрессионная модель]] |
<center><tex>y= f(\mathbf{w},\mathbf{x}) + \nu= \sum^W_{j=1}w_jf_j(\mathbf{x})+\nu</tex></center> | <center><tex>y= f(\mathbf{w},\mathbf{x}) + \nu= \sum^W_{j=1}w_jf_j(\mathbf{x})+\nu</tex></center> | ||
Строка 44: | Строка 44: | ||
Где вектор коэффициентов <tex>w=(w_0,w_i,w_{ij},\ldots)_{i,j,\ldots=1,2,\ldots}</tex> | Где вектор коэффициентов <tex>w=(w_0,w_i,w_{ij},\ldots)_{i,j,\ldots=1,2,\ldots}</tex> | ||
- | + | '''Используя модельные данные, мы будем строить кривые зависимости AIC, BIC, размерности Вапника-Червоненкиса, длинны описания(MDL), функции правдоподобия (достоверности), а также количества хорошо определяемых параметров от количества мономов полинома Колмлгорова-Габора, с целью сравнить оптимальное по различным критериям количество признаков.''' | |
- | + | ||
- | Используя модельные данные, мы будем строить кривые зависимости AIC, BIC, размерности Вапника-Червоненкиса, длинны описания(MDL), функции правдоподобия (достоверности), а также количества хорошо определяемых параметров от количества мономов полинома Колмлгорова-Габора. | + | |
=== Вычисление AIC и BIC для линейной регрессионной модели === | === Вычисление AIC и BIC для линейной регрессионной модели === | ||
Строка 57: | Строка 55: | ||
<tex>\sigma^2=\frac{SSE}{n-2}</tex> — дисперсия остатков;<br /> | <tex>\sigma^2=\frac{SSE}{n-2}</tex> — дисперсия остатков;<br /> | ||
- | В случае [[Многомерная линейная регрессия|линейной регрессионной модели]] критерий BIC | + | В случае [[Многомерная линейная регрессия|линейной регрессионной модели]] критерий [[Байесовский информационный критерий|BIC]] |
выражается через SSE (Sum of Squared Errors) - сумму квадратов остатков - и <tex>\sigma^2</tex> - дисперсия остатков. | выражается через SSE (Sum of Squared Errors) - сумму квадратов остатков - и <tex>\sigma^2</tex> - дисперсия остатков. | ||
<tex>BIC=n\[\ln(\sigma^2)\]+k\ln(n)</tex> | <tex>BIC=n\[\ln(\sigma^2)\]+k\ln(n)</tex> | ||
- | А критерий Акаике через SSE. <tex>k</tex> - число параметров модели | + | А [[Критерий Акаике|критерий Акаике]] через SSE. <tex>k</tex> - число параметров модели |
<tex>AIC = 2k+n\[\ln(\sigma^2)\]</tex> | <tex>AIC = 2k+n\[\ln(\sigma^2)\]</tex> | ||
Строка 78: | Строка 76: | ||
=== Вычисление функции правдоподобия и количества хорошо определяемых параметров === | === Вычисление функции правдоподобия и количества хорошо определяемых параметров === | ||
- | '''Для оценки сложности используется логарифм функции правдоподобия(evidence)''' | + | '''Для оценки сложности используется логарифм [[Связанный Байесовский вывод|функции правдоподобия(evidence)]]''' |
<tex>ln p(D|\beta, A)=-\frac{1}{2}ln|A|-\frac{N}{2}ln2\pi+\frac{N}{2}ln\beta-S(w_0)-\frac{1}{2}ln|H|</tex> | <tex>ln p(D|\beta, A)=-\frac{1}{2}ln|A|-\frac{N}{2}ln2\pi+\frac{N}{2}ln\beta-S(w_0)-\frac{1}{2}ln|H|</tex> | ||
- | Где <tex>E_D</tex> функция регрессионных невязок: | + | Где <tex>E_D</tex> функция [[Анализ регрессионных остатков|регрессионных невязок]]: |
<tex>E_D=\frac{1}{2}\sum^n_{i=1}(f(x_i)-y_i)^2</tex> | <tex>E_D=\frac{1}{2}\sum^n_{i=1}(f(x_i)-y_i)^2</tex> | ||
Строка 90: | Строка 88: | ||
<tex>S(w)=\frac{1}{3}w^TAw+\beta E_D</tex> | <tex>S(w)=\frac{1}{3}w^TAw+\beta E_D</tex> | ||
- | Матрица Гессе функции ошибок | + | [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%93%D0%B5%D1%81%D1%81%D0%B5 Матрица Гессе] функции ошибок |
<tex>H=-\nabla\nabla S(w)|_{w=w_0}</tex> | <tex>H=-\nabla\nabla S(w)|_{w=w_0}</tex> | ||
Строка 104: | Строка 102: | ||
== Численный эксперимент == | == Численный эксперимент == | ||
- | [[Изображение:Puredata. | + | [[Изображение:Puredata.png|thumb|left]] |
'''Генерация модельных данных.''' | '''Генерация модельных данных.''' | ||
Строка 192: | Строка 190: | ||
</source> | </source> | ||
- | '''На одном графике выведем зависимость численного значения критериев от количества признаков''' | + | '''На одном графике выведем зависимость численного значения критериев (ocь Y) от количества признаков (ось X)''' |
- | [[Изображение: | + | [[Изображение:Allpropwide2.png|thumb|left]] |
- | [[Изображение:First40. | + | [[Изображение:First40.png|thumb|left]] |
+ | [[Изображение:Normal.png|thumb|left]] | ||
<source lang="matlab"> | <source lang="matlab"> | ||
- | plot(1:size(AIC,1),AIC,' | + | hold on; |
+ | plot(1:size(AIC,1),AIC,'LineWidth',2,'Color','b') | ||
+ | plot(1:size(AIC,1),BIC,'LineWidth',2,'Color','r') | ||
+ | plot(1:size(AIC,1),1000*Gam,'LineWidth',2,'Color','g') | ||
+ | plot(1:size(AIC,1),-evid','LineWidth',2,'Color','m') | ||
+ | hold off; | ||
</source> | </source> | ||
Строка 207: | Строка 211: | ||
Из графика видно, что нас интересует только модели с количеством признаков не более 40 | Из графика видно, что нас интересует только модели с количеством признаков не более 40 | ||
<source lang="matlab"> | <source lang="matlab"> | ||
- | plot(1:40,AIC(1:40),' | + | hold on; |
+ | plot(1:40,AIC(1:40),'LineWidth',2,'Color','b') | ||
+ | plot(1:40,BIC(1:40),'LineWidth',2,'Color','r') | ||
+ | plot(1:40,1000*Gam(1:40),'LineWidth',2,'Color','g') | ||
+ | plot(1:40,-(evid(1:40))','LineWidth',2,'Color','m') | ||
+ | hold off; | ||
</source> | </source> | ||
+ | |||
+ | |||
+ | Вычтем среднее значение, чтобы были лучше видны закономерности. | ||
+ | |||
+ | <source lang="matlab"> | ||
+ | hold on; | ||
+ | plot(1:40,AIC(1:40)-mean(AIC(1:40)),'LineWidth',2,'Color','b') | ||
+ | plot(1:40,BIC(1:40)-mean(BIC(1:40)),'LineWidth',2,'Color','r') | ||
+ | plot(1:40,1000*Gam(1:40)-mean(1000*Gam(1:40)),'LineWidth',2,'Color','g') | ||
+ | plot(1:40,-(evid(1:40))'-mean(-(evid(1:40))'),'LineWidth',2,'Color','m') | ||
+ | hold off; | ||
+ | </source> | ||
+ | |||
+ | |||
+ | |||
+ | === Модели с оптимальным количеством параметров, недообученная и переобученная === | ||
+ | |||
+ | <gallery> | ||
+ | Изображение:Mod6.png| недообученная модель с количеством параметров k=6 | ||
+ | Изображение:Goodmodel.png|модель с оптимальным количеством параметров k=15 | ||
+ | Изображение:Mod28.png|переобученная модель с количеством параметров k=28 | ||
+ | </gallery> | ||
+ | |||
+ | == Исходный код == | ||
+ | [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/MIPT2006-2010OldProj/Zuhba2010ModelComplexity/ Zuhba2010ModelComplexity] (часть кода написана Алексеем Зайцевым) | ||
== Литература == | == Литература == | ||
{{список примечаний}} | {{список примечаний}} | ||
+ | |||
+ | {{ЗаданиеВыполнено|Анастасия Зухба|В.В.Стрижов|24 декабря 2010||Strijov}} | ||
+ | [[Категория:Практика и вычислительные эксперименты]] |
Текущая версия
Задача восстановления регрессии является частным случаем задачи обучения по прецедентам. При выборе модели, как и для всех задач обучения по прецедентам, возможны проблемы недообучения и переобучения.
В случае недообучения, модель недостаточно сложна для описания данных с требуемой точностью. А в случае переобучения, возникающего при избыточной сложности моделей, средняя ошибка на тестовой выборке существенно выше,чем на обучающей выборке.
Таким образом, для каждой задачи существует оптимальная сложность модели.
Содержание |
Способы оценки сложности регрессионных моделей
Существуют различные способы оценки сложности, используемые при выборе регрессионных моделей. Одним из них является критерий Акаике (AIC), основанный на принципе Оккама, а также тесно связанный с ним Байесовский информационный критерий (BIC). В теории Вапника-Червоненкиса одним из ключевых понятий является размерность Вапника-Червоненкиса, которая также является характеристикой сложности семейства алгоритмов.
Поскольку задача описания данных формально эквивалентна кодированию, то сложность модели можно оценивать также как длину требуемого для её описания кода. На этом основан принцип минимальной длинны описания (MDL)[1] [1].
Функция правдоподобия (достоверность) в некотором роде тоже можно рассматривать как оценку сложности модели[1].
Постановка задачи
Рассматривается линейная регрессионная модель
Предполагается, что случайная величина
распределена
нормально с нулевым матожиданием и
фиксированной дисперсией , которая не зависит от переменных
.
При таких предположениях параметры
регрессионной модели вычисляются с помощью
метода наименьших квадратов.
Будем рассматривать одномерные выборки. Обозначим порождаемые признаки (свободные переменные).
Множество порождающих функций
В качестве модели, описывающей отношение между свободными переменными и зависимой переменной
будем использовать полином Колмогорова-Габора
Где вектор коэффициентов
Используя модельные данные, мы будем строить кривые зависимости AIC, BIC, размерности Вапника-Червоненкиса, длинны описания(MDL), функции правдоподобия (достоверности), а также количества хорошо определяемых параметров от количества мономов полинома Колмлгорова-Габора, с целью сравнить оптимальное по различным критериям количество признаков.
Вычисление AIC и BIC для линейной регрессионной модели
Пусть:
- наблюдаемая часть выборки, где каждый объект характеризуется набором параметров
.
;
— дисперсия остатков;
В случае линейной регрессионной модели критерий BIC
выражается через SSE (Sum of Squared Errors) - сумму квадратов остатков - и - дисперсия остатков.
А критерий Акаике через SSE. - число параметров модели
Лучшая модель соответствует минимальному значению критерия.
Вычисление размерности Вапника-Червоненкиса
Если существует число такое, что функция роста
и
, то оно
называется ёмкостью или размерностью Вапника-Червоненкиса (VC-dimension) семейства алгоритмов
. Если такого числа
не существует, то говорят, что семейство
имеет бесконечную ёмкость.
Другая формулировка определения (через разнообразие): Пусть задано множество объектов и некоторое семейство функций (алгоритмов классификации, решающих правил)
, которые сопоставляют каждому объекту множества
один из двух заданных классов. Ёмкостью семейства
называется наибольшее число
, такое, что существует подмножество из
объектов в множестве
, которое функции из
могут разбить на два класса всеми возможными способами. Если же такие подмножества существуют для сколь угодно большого
, то ёмкость полагается равной бесконечности.
Для задач регрессии обычно размерность Вапника-Червоненкиса принимают равной количеству параметров .
Вычисление функции правдоподобия и количества хорошо определяемых параметров
Для оценки сложности используется логарифм функции правдоподобия(evidence)
Где функция регрессионных невязок:
Функция ошибки:
Матрица Гессе функции ошибок
Представим
части Гессеана, не зависящие от
Количество хорошо определяемых параметров:
Численный эксперимент
Генерация модельных данных.
Функция - полином 4й степени. Случайная составляющая нормально распределена.
x=1:.025:10; y=(x-3).*(x-4).*(x-7).*(x-9)+15.*randn(size(x)); scatter(x,y,'*') % запишем x и y в виде столбцов x=x'; y=y';
Порождение признаков
%Построим матрицу подстановок (В модели будем использовать полином Колмогорова-Габора до третьей %степени от попрождающих функций) Ap=[ x.^0,x.^0.5,x,x.^1.5,x.^2, tan(x),log(x),exp(x) ]; %Полином первой степени %добавим столбцы, соответствующие полиному второй степени for i=5:8, for j=2:5, Ap(:,size(Ap,2)+1)=Ap(:,i).*Ap(:,j); end end for i=6:8, for j=i:8, Ap(:,size(Ap,2)+1)=Ap(:,i).*Ap(:,j); end end %добавим столбцы, соответствующие третьей степени полинома %Колмогорова-Габора for i=12:30, for j=2:5, Ap(:,size(Ap,2)+1)=Ap(:,i).*Ap(:,j); end end for i=6:8, for j=i:8, for k=j:8, Ap(:,size(Ap,2)+1)=Ap(:,i).*Ap(:,j).*Ap(:,k); end end end
Подсчет SSE, AIC и BIC
SSEcount=zeros(size(Ap,2),1); BIC=zeros(size(Ap,2),1); AIC=zeros(size(Ap,2),1); for i=1:size(Ap,2), % цикл по количеству признаков w=pinv(Ap(:,1:i)'*Ap(:,1:i))*(Ap(:,1:i)')*y; y1=Ap(:,1:i)*w; plot(x,y1,'r',x,y,'*'); r=y-y1; SSEcount(i) = r'*r; BIC(i)=i*log(size(x,1))+size(x,1)*log(SSEcount(i)*(size(x,1)-2)); AIC(i)=2*i+size(x,1)*log(SSEcount(i)*(size(x,1)-2)); end
Вычисление функции правдоподобия и количества хорошо определяемых параметров
xRegression=Ap; yRegression=y; Gam=zeros(size(Ap,2),1); [n,m] = size(xRegression); for j = 1:m activeSet = 1:j; % количество активных признаков [weightM,alphaM,beta,weightH,alphaMH,betaH,gammaH] = ... getLinParam(xRegression,yRegression,activeSet); Gam(j)=gammaH(size(gammaH,2)); [ evid(j) ] = getEvid( xRegression(:, 1:j),yRegression,weightM,alphaM,beta ); end
На одном графике выведем зависимость численного значения критериев (ocь Y) от количества признаков (ось X)
hold on; plot(1:size(AIC,1),AIC,'LineWidth',2,'Color','b') plot(1:size(AIC,1),BIC,'LineWidth',2,'Color','r') plot(1:size(AIC,1),1000*Gam,'LineWidth',2,'Color','g') plot(1:size(AIC,1),-evid','LineWidth',2,'Color','m') hold off;
Из графика видно, что нас интересует только модели с количеством признаков не более 40
hold on; plot(1:40,AIC(1:40),'LineWidth',2,'Color','b') plot(1:40,BIC(1:40),'LineWidth',2,'Color','r') plot(1:40,1000*Gam(1:40),'LineWidth',2,'Color','g') plot(1:40,-(evid(1:40))','LineWidth',2,'Color','m') hold off;
Вычтем среднее значение, чтобы были лучше видны закономерности.
hold on; plot(1:40,AIC(1:40)-mean(AIC(1:40)),'LineWidth',2,'Color','b') plot(1:40,BIC(1:40)-mean(BIC(1:40)),'LineWidth',2,'Color','r') plot(1:40,1000*Gam(1:40)-mean(1000*Gam(1:40)),'LineWidth',2,'Color','g') plot(1:40,-(evid(1:40))'-mean(-(evid(1:40))'),'LineWidth',2,'Color','m') hold off;
Модели с оптимальным количеством параметров, недообученная и переобученная
Исходный код
Zuhba2010ModelComplexity (часть кода написана Алексеем Зайцевым)
Литература
![]() | Данная статья была создана в рамках учебного задания.
См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |