Регрессия квадратичного полинома

[sergey zhukov]

мат-ламер
Да вопросов-то в общем и не было. Был один - почему квадраты? - и это вроде прояснилось.

С приведенной гребенкой решение МНМ однозначно. Но можно слегка модифицировать гребенку - тогда решение МНМ не однозначно.

Слабый минимум у МНМ - это в сравнении с минимумом у МНК на тех же данных.

[мат-ламер]

sergey zhukov в сообщении #1646129 писал(а):

Был один - почему квадраты? - и это вроде прояснилось.

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

[sergey zhukov]

Missir в сообщении #1646060 писал(а):

Последний проще всего реализуется, но эффективен он только в случае нормального распределения регрессионных остатков.

Интересно. Возьмем какую-нибудь модельную задачу. Скажем, прямую с нанесенным на нее шумом (случайная величина с заданным распределением). Один из методов удаления этого шума: это так провести прямую, чтобы регрессионные остатки были распределены согласно тому самому распределению шума. Если этот шум гауссовый и независимый от точки к точке, то мы по сути и решаем эту задачу, применяя метод МНК. Но вообще можно решить эту задачу для любого шума, если мы только знаем его распределение. Скажем, можно решить ее для равномерного шума, если подобрать кривую так, чтобы регрессионные остатки был распределены равномерно. Получится некоторая другая задача на экстремум суммы какой-то функции от отклонений.

[B@R5uk]

sergey zhukov в сообщении #1646048 писал(а):

Я вообще заметил, что МНМ почему-то "приклеивается" к точкам, и мне это показалось странным. Вот 14 точек типа "0,1,0,1...", через которые я провел многочлен четвертой степени методом МНМ:
Изображение

Он проходит через четыре точки данных. Сразу видно, что МНК сдеал бы это совершенно иначе (примерно провел бы горизонтальную прямую по центру картинки) Т.е. по сути регрессионные полиномы МНМ - это плиномы Лагранжа. Осталось только понять, через какие же точки данных они должны пройти, и тогда найти их совсем легко.

А можно глянуть код, которым вы считали? Сдаётся мне, что на картинке не есть оптимальная кривая. График симметричен относительно поворота на 180° вокруг центра, выбранный вами полином тоже способен иметь ту же симметрию. По идее, оптимальная кривая должна иметь эту самую симметрию. Не говоря уже про точку НАД максимальным значением исходного набора.

[ozheredov]

sergey zhukov в сообщении #1646196 писал(а):

Скажем, прямую с нанесенным на нее шумом (случайная величина с заданным распределением). Один из методов удаления этого шума: это так провести прямую, чтобы регрессионные остатки были распределены согласно тому самому распределению шума.

Как оценивать распределение остатков $x_i - \hat{x_i}$, чтобы сравнивать его с эталонным распределением шума?

[sergey zhukov]

B@R5uk
Вы правы. Глобальный минимум выглядит так:

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

ozheredov
Это же наверное стандартная задача. Дан ряд реализаций случайной величины, подобрать параметры плотности вероятности известного вида для этого ряда. Скажем, подобрать такие параметры плотности вероятности, чтобы произведение вероятностей всех реализаций стало максимальным. Точнее, произведение соответствующих значений кривой плотности вероятности для этих реализаций. И наоборот: дана плотность вероятности известного вида, "подобрать под нее" параметры случайного ряда (в данном случае это параметры регрессионной кривой). Считается, что шум во всех точках данных подчиняется одному и тому же распределению, независимому от данных, которое нам известно.

А иногда о нем даже не все нужно знать. Скажем, для нормального распределения не нужно знать дисперсию. Достаточно того, что она постоянна. А вот с равномерным распределением я поторопился, наверное. Максимум, что там можно сделать, это прибавть к регрессионной кривой сверху и снизу полосы пределов этого распределения и следить за тем, чтобы все точки данных вошли в эти полосы. Вычислять там нечего.

[ozheredov]

sergey zhukov в сообщении #1646229 писал(а):

Дан ряд реализаций случайной величины, подобрать параметры плотности вероятности известного вида для этого ряда.

Это, видимо, метод максимального правдоподобия.

sergey zhukov в сообщении #1646229 писал(а):

произведение соответствующих значений кривой плотности вероятности для этих реализаций

Или какое-то расстояние между распределениями, например Кульбака-Лейблера. Вопрос - при каком размере выборки преимущества описанной Вами процедуры не утонут в неточности МП-оценивания

[sergey zhukov]

Евгений Машеров в сообщении #1646100 писал(а):

МНК предлагает нам среднее арифметическое

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

-- 14.07.2024, 20:29 --

Можно тогда говорить, что практика усреднения результатов измерений методом среднего арифметического связана с тем, что распределение ошибок предполагается нормальным. Отсюда следует, что наиболее вероятный результат - среднее арифметическое. Если бы распределение ошибок имело в показателе экспоненты, скажем, четвертую степень отклонения, а не вторую, то для нахождения среднего пришлось бы искать минимум суммы четвертых степеней отклонений. Т.е. вместо среднего арифметического нужно было бы решать кубическое уравнение.

[мат-ламер]

sergey zhukov в сообщении #1646196 писал(а):

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

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

-- Пн июл 15, 2024 17:31:31 --

sergey zhukov в сообщении #1646303 писал(а):

Можно тогда говорить, что практика усреднения результатов измерений методом среднего арифметического связана с тем, что распределение ошибок предполагается нормальным.

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

[B@R5uk]

sergey zhukov в сообщении #1646229 писал(а):

А градиентный спуск как-то все проезжает мимо этого минимума. Приводит к нему, но едет дальше. Видимо, там очень мелкая ямка.

Градиентный спуск абсолютно не пригодный для решения этой задачи метод (когда считаете МНМ, а не МНК). Взгляните на вашу целевую функцию под углом следующим образом. Будем считать оптимальные коэффициенты полинома в два этапа. Сначала зафиксируем коэффициенты при 4-ой, 3-ей и 2-ой степенях и подгоним первую и нулевую (возможно даже аналитически, но это не важно для понимания проблемы). Потом, имея оптимальное решение для линейной задачи (просто перенесли старшие степени по другую сторону равенства и решили задачу), находим коэффициенты старших степеней. Казалось бы, ничего нового? Ан, нет! При решении линейной задачи может возникнуть ситуация (для каких-то фиксированных значений коэффициентов старших степеней), когда прямую можно провести множеством способов, каждый из них даст одно и то же значение целевой функции. Для такой ситуации вариация коэффициентов старших степеней при подгонке должна сужать область "болтания" прямой. Метод градиентного спуска этого в принципе видеть не может. У него частные производные нулевые, он и рад.

[мат-ламер]

sergey zhukov в сообщении #1646229 писал(а):

А градиентный спуск как-то все проезжает мимо этого минимума. Приводит к нему, но едет дальше.

B@R5uk в сообщении #1646379 писал(а):

Градиентный спуск абсолютно не пригодный для решения этой задачи метод (когда считаете МНМ, а не МНК).

Классический градиентный спуск предназначен для гладких функций. А у нас функция кусочно-линейная. Но есть модификация этого метода, называемая субградиентным методом. Его можно использовать, но метод довольно медленный.

[sergey zhukov]

B@R5uk
Не очень понял это объяснение, но зато понял, что поскольку целевая функция у МНМ кусочно-линейная, то на ребрах и вершинах она не дифференциируема. И градиентный спуск, который тут "любит" как раз по ребрам передвигаться, легко может застрять на ребре, на котором частные производные целевой функции по всем направлениям положительны, хотя это вовсе не точка минимума. А если задать правило "если вперед частная производная положительна, то делай шаг назад", то градиентный спуск может вместо спуска иногда заняться подьемом.

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

[Alex Krylov]

Вообще, вот это $\min\limits_{x} \left\lVert Ax-b\right\rVert_1$ и вот это $\min\limits_{x} \left\lVert Ax-b\right\rVert_\infty$ переформулируются как соотв. задачи линейного программирования. Для фигурировавшего в данной дискуссионной ветке примера (с полиномом 4-й степени и данными типа (0,1)) ниже приведен соотв. код Matlab с использованием парсера Yalmip. Для 1-нормы решение совпадает с приведенным выше, а для inf-нормы решением является константный полином $0.5$.

Используется синтаксис Matlab M

%1-norm minimization min ||A*x-b||_1

a = (0:0.1:1.3)';
A = [ones(14,1),a,a.^2,a.^3,a.^4];
b = zeros(14,1);
for i = 2:2:14 
b(i) = 1;
end
x = sdpvar(5,1);
t = sdpvar(14,1);
constr = [A*x-t <= b, -A*x-t <= -b];
obj = ones(1,14)*t;
optimize(constr,obj);
value(obj)
norm(A*value(x),Inf)%Check Inf-norm of solution

plot(a,b);
zoom xon;
hold on;
plot(a,A*value(x));
hold on;

%inf-norm minimization min ||A*x-b||_inf

clear x t;
x = sdpvar(5,1);
t = sdpvar;
constr = [A*x-b+t*ones(14,1) >= 0, A*x-b-t*ones(14,1) <= 0];
obj = t;
optimize(constr,obj);
value(obj)
norm(A*value(x),1)%Check 1-norm of solution

plot(a,A*value(x));
 

Вообще говоря, парсер Yalmip абсолютно не нуждается в том, чтобы задачи минимизации линейных норм в явном виде переформулировались для него в виде соотв. задач линейного программирования (он делает это сам). Можно было просто написать:

Используется синтаксис Matlab M

optimize([],norm(A*x-b, 1))

или

Используется синтаксис Matlab M

optimize([],norm(A*x-b, inf))

Явная переформулировка в виде соотв. задач линейного программирования была сделана чисто из педагогических соображений.

[Missir]

Так то оно так, но вот зачем здесь нужна весьма сомнительная Yalmip понятно не совсем.
Вот решение в matlab:

Используется синтаксис Matlab M

x=((0:13)/10)'; y=zeros(14,1); for j=2:2:14; y(j)=1; end
X=[ones(14,1) x x.^2 x.^3 x.^4];
vars=linprog([zeros(1,5) ones(1,14)], [[X -eye(14)]; [-X -eye(14)]], [y; -y]);
b=vars(1:5);
F=sum(vars(6:end));

yo=X*b;
plot(x,y); hold on; plot(x,yo,'r');
 

кстати, решение у этой задачи не единственное, так как $b_0=0$.

[Евгений Машеров]

мат-ламер в сообщении #1646377 писал(а):

Этот метод можно применять не только для нормальных распределений. Вот, скажем, теорема Гаусса-Маркова не предполагает нормальности ошибок. Но она предполагает, что будут использоваться линейные методы получения оценок, которые просто реализуются на практике.

Есть глубокая связь линейности и нормальности. Линейные преобразования сохраняют нормальность.