[Метод наименьших квадратов]Приглашаю подумать

Мысль мне давно в голову засела. Что такое МНК? Метод, позволяющий провести кривую заданного типа рядом с экспериментальными точками. Чтобы получить коэффициенты, мы занимаемся минимизацией функционала  Sum_1_N (  ( y_i- f(x_i))^2 )
Но почему именно "квадратов"? Почему не 4 степеней, или 10х или 100ых?
Можно же написать Sum_1_N (  ( y_i- f(x_i))^(2*k) )
И совсем не очевидно, что при k>1 результат будет хуже, чем при k=1.
То есть, кривая может лежать "ближе" к заданным точкам .
Я попробовал на Excel'e подогнать к набору из 10 точек параболу по М4К и М6К
М4К по виду лучше легла, чем МНК.
(мининизировал Solver'ом)

Препы в Институте отмазывались, что МНК придумали потому, что коэффициенты для прямой хорошо им находятся. Это и понятно - мы их явно можем вытащить из частных производных от Sum
Но это имхо не ответ.

Еще в статистике есть теорема, что если точки от кривой раскиданы по Гауссу, то МНК доставляется наименьшая дисперсия для кривой. Тоже не удовлетворяет меня.

Кто-нибудь скажет, что-то ценное?
Понимаю, что тема скорее для математика, а не программерская, но может кто шарит.

Цитата kms, 12.05.02, 21:54:05

Понимаю, что тема скорее для математика, а не программерская, но может кто шарит.

вроде этот раздел форума как раз для этого и предназначен:))

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

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

Addon:
Выбирай и делай то, что тебе самому по душе и если позволяют возможности. 8)

Весь вопрос в том, какие данные мы собираемся апроксимировать, так если эксперементальные точки лежат практически на прямой, то лучше воспользоваться МНК (апроксимировать прямой), в других случаях лучшее приблежене будет если апроксимировать параболой.
Но чем больше степень полинома, тем больше вычислений  :(

Кто же знает где они лежат, на прямой или на окружности. ;D ;D ;D

Ты...
У тебя есть несколько точек полученых в ходе эксперемента. Ты смотришь как они лежат (

Цитата GrAnd, 18.05.02, 08:05:24

на прямой или на окружности. ;D ;D ;D

) и апроксимируешь

А если их около сотни ;D ;D ;D Дело в том, что начинать аппроксимацию  надо с самого лажового метода и при не получении необходимого приближения усложнять методику. И рассматривать где лежат точки не имеет никакого смысла.

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

Если я правильно помню идею МНК, то суть его в том, что мы минимизируем отклонение. Почему квадрат? Потому что степень небольшая, уравнение выводится просто. Можно было бы и модуль отклонения - но он не дифферинцируется . Сами вспомните, как метод получается - пишем [C0f0 + .. + CnFn]^2->min, дифференцируем по всем переменным, получаем систему - вот и все. Зачем усложнять - очень часто усложнение не оправдывается.

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

2WseslaW

ты чо, смеёшься?? посмотри на дату ;D

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

а ты чо, тот самый кмс 3 года спустя?? ;D

кстати не 3, а 1 ;D ;D

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

>а ты чо, тот самый кмс 3 года спустя??  
Типа того..
>кстати не 3, а 1  
Да, да

>и вобще, не следует путать метод наименьших квадратов и линейную регрессию. наименьшими квадратами можно приближать какой угодно функцией, хоть суммой логарифма с гиперболическим косинусом.
Я не путаю. Предполагается, что мы приближаем   набор точек (x_i, y_i)
какой-либо функцией Phi(x)? МНК дает нам необходимые коэффициенты этой фи.

>более того, мнк - ето вовсе даже не метод, а просто способ вычисления расстояния между двумя функциями.

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

>для линейной регрессии минимум находится аналитически, для других приближений его ищут различными _методами_ вроде градиентного спуска, сопряжённых градиентов, ньютона-рафсона, ....... .

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

Почему МНК(2)? Почему не МНК(3) 4... итд?

Я так понимаю, wormball знает ответ, но молчит пока. Написал на мыло.
Кстати, я найду где поискать и спросить, про все, что касается функана, но только что именно? Тока подзабыл я это все чуть-чуть...

Вел ли кто-нибудь исследования альтернативных функционалов для оптимального приближения кривой?

ето ты мне чтоли написал?? ;D

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

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

сопственно метод заводить собственный функционал расстояния тоже известен математике. тоесь ты можешь задать совершенно любую функцию и использовать её в качестве расстояния. но опять же не доказано, что сей метод имеет неоспоримые преимущества перед мнк, и в 99\% случаев используют мнк.

аещё я слышал про некий "метод максимального правдоподобия", только не знаю чо ето такое.

зы. проверил почту, ничего нового

Сообщение отредактировано: wormball - 22.09.03, 17:22

да еще не забывай чем больше степень тем больше осциляция поэтому большие степени полиномов не используют

2 Lucifer

Была в статистике теорема о том, что если ошибки по гауссу, то доставляется минимальная дисперсия.
Что такое робастность - непомню  >:( , видимо устойчивость к начальным данным..

Пусть мы строим функционал, который тем больше, чем больше совокупность всех |f_i  -  y_i| и тем ближе к 0, чем она меньше.
Я пока не говорю, как мы определяем меру для  совокупности |f_i  -  y_i|
Пока на интуитивном уровне...
МНК определяет это так:
Найти минимум функционала
SUM( |f_i (a, b, c...)  -  y_i|^2) -> min
a b c - искомые коэффициенты f()

Можно ли предложить что-то лучше?

Заодно задам еще один идиотский вопрос (на него можно не отвечать..):
Допустим, у нас есть набор простых функций. Можно ли хоть как-то подступиться к задаче - композицией этих функций собрать такую, которая бы наилучшим образом приближалась бы к нашим точкам? Скорее всего, это нереально.

Цитата Lucifer, 23.09.03, 16:23:26

Представь, что среди этой выборки был один кривой элемент, т.е. вся выборка из N(0,1), а один элемент попался равным 10000000(секретарша ошиблась когда цифры набивала, чубайс 380 вместо 220 вольт врубил).

ага, ты бы ещё захотел, чтобы она выдавала правильный ответ при половине кривых чисел в выборке. гнать надо в шею такую секретаршу!! в крайнем случае написать спец. программу, убирающую все нехорошие числа.

да и вобще насколько я помню математическое ожидание обладает какимито хорошими свойствами, которыми не обладает медиана.

кстати что такое метод максимального правдоподобия?? :

Сообщение отредактировано: wormball - 23.09.03, 13:32

Цитата wormball, 23.09.03, 17:30:18

ага, ты бы ещё захотел, чтобы она выдавала правильный ответ при половине кривых чисел в выборке. гнать надо в шею такую секретаршу!! в крайнем случае написать спец. программу, убирающую все нехорошие числа.

да и вобще насколько я помню математическое ожидание обладает какимито хорошими свойствами, которыми не обладает медиана.

кстати что такое метод максимального правдоподобия?? :

правильно помнишь м.о в отличии от медианы линейная операция -> легко считается и анализируется как ф-я чего про медиану сказать нельзя

ну а самое главное сумма мо=мо суммы в независимости от переменных

ТОВАРИЩ помни есть сл. величины без м.о и не попадись впросак   (Коши)

Цитата esperanto, 23.09.03, 17:58:56

ТОВАРИЩ помни есть сл. величины без м.о и не попадись впросак   (Коши)

0525!
уж сколько раз твердили миру, что у коши есь математичесоке ожидание! у него нет дисперсии

а уж тем более есь они у тех величин, с которыми люди имеют дело на практике.

Цитата wormball, 23.09.03, 18:07:02

0525!
уж сколько раз твердили миру, что у коши есь математичесоке ожидание! у него нет дисперсии

а уж тем более есь они у тех величин, с которыми люди имеют дело на практике.

судя по всему твердили те кто не знает тер вер!!!

f(x)=1/pi(1+x^2)

ex=integral(x/(1+x^2)dx,0,00)=бесконечность

и хватит спорить с преподавателями

сморя как интегрировать 8D

даже если не имеет, то всё равно насколько я понимаю ни один естественный процесс по нему не распределён, тоесь его можно рассматривать как математическую шутку ;D.

Цитата wormball, 23.09.03, 19:25:53

сморя как интегрировать 8D

даже если не имеет, то всё равно насколько я понимаю ни один естественный процесс по нему не распределён, тоесь его можно рассматривать как математическую шутку ;D.

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

кроме этого есьт дургие заокны в том числе дискретные без м.о


например

человек кидает монету до того как первый раз выпадет орел и получает приз
в размере равном два в степени количество попыток.

так вот м.о приза равно бесконечности поэтому елси ты будешь эмулировать эту игру и считать м.о

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

Цитата kms_, 23.09.03, 14:05:02

Заодно задам еще один идиотский вопрос (на него можно не отвечать..):
Допустим, у нас есть набор простых функций. Можно ли хоть как-то подступиться к задаче - композицией этих функций собрать такую, которая бы наилучшим образом приближалась бы к нашим точкам? Скорее всего, это нереально.

Вопрос совершенно не идиотский, очень даже актуальный. Первым кто дал на него правильный, исчепывающий и положительный ответ был Чебышев. см. полиномы Чебышева. Для практического применения лучше всего с вопросом ознакомиться по книге Анго "Математика для электро- и радиоинженеров".
Практическую реализацию метода см. www.netlib.org/chephes аппроксимация произвольной функции дробно - рациональными функциями по критерию минимума максимальной ошибки (критерий Чебышеба, минимакса).
Кстати, все что здесь написано о выборе степеней, есть ничто иное как выбор нормы в которой осуществляется аппрокимация.
Норма вектора (в Вашем случае это вектор разности аппроксимирующей функции и исходной) L=Sum^N_i=1|x_i|^p.
p=2 - евклидова норма, наименьшие квадраты
p=\infinity критерий минимакса.

Да исполнится же этой теме 5 лет!:)
Вопрос воистину вечный, я вот тоже как-то задумался над этим!
По-моему, всё намного проще! Не могу блеснуть очень глубокими знаниями, но на пальцах могу себе представить.
МНК имеет вид ∑(Yi - f(Xi))^2 = min. (рассмотрю задачу на плоскости)
Т.е. суммируются квадраты расстояний по оси Y между практическим (табличным) значением в i-той точке и функцией в этой точке. И аналитическим образом мы минимизируем эту сумму, т.е. принимаем, что все частные производние по неизвестным параметрам функции равны нулю.
Во-первых, почему там стоит квадрат? Ну уж точно, первую степень туда не влепишь, т.к. расстояния между Yi и f(Xi) будет получаться как положительным, так и отрицательным. Т.е., с нормальным случайным распределением, сумма всегда будет варьировать возле нуля, не накапливая тем самым общее отклонение. И так обстоит дело с любой нечётной степенью. Модуль туда, действительно, не воткнёшь, не дифференцируется, так нам однажды сказала учительница в школе и я принял это на веру:)
А теперь, если воткнуть туда 4 степень.... И что это получится... Очевидно, что сложные вычисления. А подумать глубже, будет просто всё так же суммироваться отклонение, только уже не в степени 2, а в степени 4. На мой взгляд, роль чётной степени - это просто перейти к абсолютному расстоянию, всегда положительному, дабы накапливать сумму. А четвёртая степень просто будет стремительнее накапливать сумму при больших Дельта Y. Следовательно, если и будет разница в минимизации суммы вторых и четвёртых степеней, то она будет заключаться в ооооочень маленьком приросте точности, на мой взгляд. А сужу, что ооочень маленьком потому что... вы видели вообще насколько чётко МНК апроксимирует??? И расстояние от точки до графика - воистину минимально, минимальней не придумаешь! А если не придумаешь, то и сумма 4 степеней будет там минимальна!!! А вообще, попробую как-нибудь сравнить на практике....

Для данных полученных при реальных измерениях степень лучше не увеличивать, а уменьшать. А то получается, что чем больше отклонение ( шум ), тем больше у него вес, а по идее надо наоборот. Поэтому для борьбы с помехами лучше минимизаровать ∑|Yi - f(Xi)|. Это сложнее, чем сумму квадратов, но реально.

Цитата prografix @ 31.03.07, 08:38

А то получается, что чем больше отклонение ( шум ), тем больше у него вес, а по идее надо наоборот.

Не понял: так ведь чем больше вес, тем оно сильнее и минимизируется? (относительно других отклонений) Отклонение можно считать шумом только если есть уверенность, что эмпирическая функция p(x) близка к незашумлённому сигналу, а этого мы утверждать не можем на основе самих отклонений эмпирической функции с текущими коэффициентами от исходных данных, т.к. сама же эмпирическая функция и определяется этими отклонениями, при изменении её коэффициентов отклонения будут другими и "шум" будет совсем другой, т.к. незашумлённым будет считаться другой сигнал. Или нет? На практике, честно, не пробовал....

Добавлено 31.03.07, 09:55
Запутанно как-то.... Я имел в виду, что шум - это отклонение некоторой иделизированной функции f(x) незашумлённого сигнала, т.е. |f(x_i) - Y_i|, когда же мы проводим аппроксимацию, то на основе данных x_i, Y_i строется эмпирическая функция p(x), причём минимизируется Σ|p(x_i)-Y_i|ⁿ, n >= 1. Т.о. шум в данном случае просто невычисляем: величина |p(x_i) - Y_i| ничего не говорит о |f(x_i) - Y_i|.

Сообщение отредактировано: ors_archangel - 31.03.07, 09:58

Формулу ∑(Yi - f(Xi))^2 можно записать как ∑|Yi - f(Xi)|*|Yi - f(Xi)|, т.е. для каждого отклонения вес равен ему же. Получается, что у маленького отклонения маленький вес, а у большого - большой. Но большие отлонения имеют шумы, которые вообще надо выбросить.
В случае минимизации ∑|Yi - f(Xi)| у всех отклонений вес одинаковый.

Господа, что-то вы с шумами загнались!
Самое важное в МНК - это то, что есть функция суммарного отклонения от табличных точек некоторой кривой, форма и положение которой зависит от её коэффициентов. И при изменении некоторого коэффициента эта сумма уменьшается или увеличивается. А для просчёта оптимального коэффициента нужно просто искать частные производные. И я считаю, что 4-ая, что 2-ая степень - практически одна фигня, ну разве что мааалость поточнее будет 4-ая степень, я так думаю... Вобщем сейчас проверю, жуть как интересно!!!
Сунулся.... Жесть.... Выражение расписывается на 2 строчки.... Если, вобщем добью, то выложу следующим постом. Вообще, надо кому????

prografix
Сумма отклонений - это функция ошибки аппроксимации. Ни в коем случае её элементы не есть выявленный шум, я всё-таки на этом настаиваю. Это лишь оцнека ошибки приближения - расстояние между функциями, вообще-то. Евклидово расстояние способствует равноценному приближению ко всем точкам - без потери свойств "фильтрации" шума. Т.к., чтобы компенсировать, допустим отклонение в некоторой точке x_k, не достаточно ликвидировать просто суммарное отклонение в нескольких других точках, что позваляет линейная сумма модулей.
Т.е. квадрат направляет минимизацию в первую очередь на очень плохие точки, а не аппроксимирует функцию точне там, где отклонение больше, как ты говоришь, говоря о весе, равном отклонению, ведь когда отклонение станет меньше 1, то "вес" данной точки будет уже уменьшаться. Я хочу сказать, что "вес" не означает, что данная точка будет аппроксимирована точнее, он лишь указывает, насколька аппроксимация в данной точке далека от истины, и алгоритм улучшения аппроксимации - минимизации функции её ошибки - никак ведь на уровне отдельных точек вообще-то не работает: минимум глобален. И по старой же причине я не согласен, что если ∑|Yi - f(Xi)|*|Yi - f(Xi)| больше, то шум в данной точке больше. См. мой пост №28, пока не вижу ему опровержния.

fse

Цитата fse @ 31.03.07, 12:53

Если, вобщем добью, то выложу следующим постом. Вообще, надо кому????

Интересно было бы посмотреть

Вобщем вот.... Реализовал в одной проге МНК2 и МНК4.
Только функцию я взял для апроксимации прямой, но без её смещения, т.е. высчитывается только один коэффициент: тангенс угла наклона прямой, проходящей через т. (0, 0). С коэффициентом смещения сделать так вот быстренько нереально, т.к. при возведении в куб после дифференцирования получается очень большая и некрасивая формула.
Да, и что ещё нужно отметить! При МНК-4 при апроксимации самой элементарной прямой y = kx уже возможно несколько решений, 3, если не ошибаюсь, т.к. там необходимо в конце вывода коэффициента режить кубическое уравнение. Я не стал загоняться его решением, а вычислил самый первый корень дихотомией.
Точнее ли стала апроксимация? На мой взгляд ХЗ, оба оболденно ищут, но МНК-4 похоже что поправдоподобнее малость.
Выкладываю получившуюся прогу... Рассудите сами.
p.s. Исходники выкладывать не буду, т.к. нужно вместе с ними выкладывать компонент и математические библиотеки, некогда написанные.

p.p.s. ПОГОДИТЕ КА! А как тут вложить файл, можно ведь? В упор не вижу!!!:)

Добавлено 31.03.07, 14:43
Хе-хе:)
Держите так:)
http://slil.ru/24164551

Поясню свою мысль на простом примере. Пусть f - константа.
Делаем несколько измерений и получаем в n случаях значение а ( правильно ) и в одном случае значение b ( неправильно ).
Теперь будем получать оценку f при помощи минимизации ∑|Yi - f|^k.
Для k = 1 получим f = a ( медиана )
Для k = 2 получим f = (n*a+b)/(n+1) ( среднее арифметическое )
Для k = бесконечность получим f = (a+b)/2
Отсюда видно, что чем больше k, тем больше влияние помех.