Аппроксимация по абсолютным разностям. Проще МНК.

[Tur]

Даны 4 точки

M1.X = 1; M1.Y = 3;
M2.X = 2; M2.Y = 4;
M3.X = 4; M3.Y = 4;
M4.X = 5; M4.Y = 5;



По МНК получается зеленая прямая ax + by + c = 0 после нормализации а = -0,3714 b = 0,9285 c = -2,5997
Все просто. А как найти прямую по абсолютным разностям? Т.е. представим искомую прямую так y = m*x + n, тогда абсолютные отклонения

e1 = |m*M1.X + n - M1.Y|
e2 = |m*M2.X + n - M2.Y|
e3 = |m*M3.X + n - M3.Y|
e4 = |m*M4.X + n - M4.Y|

При минимизации суммы min(e1+e2+e3+e4) как получить искомую прямую (m, n)? Какая здесь теория?

[ИСН]

Дык, развейте теорию, это просто.
Там, по-моему, выходит хрень какая-то с неоднозначностью.

[Tur]

ИСН, если бы я мог развить сам теорию, то не просил бы о помощи. Если Вам не трудно подскажите как конкретно получить m и n.

[Алексей К.]

И всё же я предлагаю Вам подступиться к теории самостоятельно. Для чего значительно упростить задачу. Сведём двумерную задачу подгонки прямой (два параметра надо найти) к задаче одномерной: найти некое $x=a$, ближайшее к $x_i,\;i=1\ldots n$. Найти и сравнить ближайшее по МНК, и ближайшее по абсолютным разностям. Совсем устное упрощение --- $n=2$.
Быть может, Вы откажетесь от этой затеи.

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

-- 20 июн 2010, 22:38 --

Пардон, давно этим не занимался, и, кажется приврал: в ГОСТах требовалось минимизировать максимальное отклонение, а не сумму этих разностей. Но свой одномерный совет оставляю в силе.

[Tur]

Алексей К., спасибо за отклик.

Рассмотрим числа
x1 = 2
x2 = 1
x3 = 4
x4 = 5
Найдем число 'a' разность квадратов отклонений от которого минимальна.
S(a) = (x1-a)^2+(x2-a)^2+(x3-a)^2+(x4-a)^2
dS/da = -x1-x2-x3-x4+4a = 0 -> a = sum(xi)/4 = 3 S(3) = 10

Запишем абсолютные разности, отсортировав х
Q(a) = |x2-a|+|x1-a|+|x3-a|+|x4-a|
Раскроем их на участках 1-5

Q1 = x2-a+x1-a+x3-a+x4-a = 12 - 4a. т.к. а <= x2, то 8 <= Q1
Q2 = a-x2+x1-a+x3-a+x4-a = 10 - 2a. т.к. x2 <= а <= x1, то 6 <= Q2 <= 8
Q3 = a-x2+a-x1+x3-a+x4-a = 6. Q3 = 6 для любых а из x1 <= а <= x3, т.е. 2 <= а <= 4
Q4 = a-x2+a-x1+a-x3+x4-a = -2 + 2a. т.к. x3 <= а <= x4, то 6 <= Q4 <= 8
Q5 = a-x2+a-x1+a-x3+a-x4 = -12 + 4a. т.к. x4 <= а, то 8 <= Q5

Другими словами x1 <= а <= x3, а где именно сказать нельзя. Т.е. задача в первом посту не имеет единственного решения? Это Вы хотели сказать?

Кстати если взять еще одну точку, например х5 = 6, то тогда будет решение. Число точек должно быть нечетным.
Так как решать мою задачу?

[Алексей К.]

Tur в сообщении #333345 писал(а):

Другими словами x1 <= а <= x3, а где именно сказать нельзя. Т.е. задача в первом посту не имеет единственного решения? Это Вы хотели сказать?

Это, и не только.
1. Но это главное.
2. Первый проснувшийся модератор Вас снесёт в карантин за такое написание формул. Это не по правилам. Ваши формулы очень просты: из $x_1 \le a \le x_3$: получается $x_1 \le a \le x_3$
3. Вы заголовком темы утверждаете, что нечто "проще МНК". Или это был вопрос? Или утверждение? Или гипотеза? Почему проще? Нет ничего проще МНК.
4. За МНКой имеются более глубокие обсонования, нежели простота. Что-то там из области максимального правдоподобия.
5. Как решать Вашу задачу --- я не знаю. Установить разумные пределы и шаг для перебора? Ну и чтобы задуматься об этом, кому-то надо как-то вдохновиться. Может там и катят какие-то методы типа линейного программирования... но вряд ли. Никто так не делает, делать так, на мой взгляд незачем. Такие идеи могут приходить от малоопытности, для того, чтобы потом быть отвергнутыми. Мне так кажется. По-моему, сам когда-то давно пережил.

[Tur]

Алексей К., эту тему я поднял потому что мне показалось что решать некоторые задачи т.о. было бы проще. "проще МНК" - это утверждение, т.к. модуль разности проще квадрата разности. Наверное я ошибся.

Сейчас я должен решить такую задачу. Требуется найти сферу по касательным к ней. Даны N прямых близких к касательным к сфере. Каждая прямая задана точкой и вектором. Требуется найти центр сферы и ее радиус.
Расстояние от прямой $M_1 (x_1, y_1, z_1)$ с направляющим нормализованным вектором $(m_1, n_1, p_1)$ до точки $M_0(x_0, y_0, z_0)$ определяется так
$r_1 = \sqrt{[(x_0-x_1)n_1-(y_0-y_1)m_1]^2+[(y_0-y_1)p_1-(z_0-z_1)n_1]^2+[(z_0-z_1)m_1-(x_0-x_1)p_1]^2}$

квадрат разностей отклонения $e_1 = (r_1 - R)^2$
частные производные приравненные к нулю могут быть представлены так

$de_1/dx_0 = A_1x_0+B_1y_0+C_1z_0+D_1=0$
$de_1/dy_0 = B_1x_0+B_2y_0+C_2z_0+D_2=0$
$de_1/dz_0 = C_1x_0+C_2y_0+C_3z_0+D_3=0$

где $A_1, B_1, C_1, D_1, B_2, C_2, D_2, C_3, D_3$ выражаются через $x_1, y_1, z_1$ и $m_1, n_1, p_1$

Каждая прямая (шесть чисел) дает три таких уравнения. Если всего четыре прямых, то получается 12 уравнений с тремя неизвестными, которые решаются по http://ru.wikipedia.org/wiki/Метод_наименьших_квадратов

Но пока все это не дает верного результата. Может быть сама идея такого решения ошибочна? Или она верна и просто следует искать ошибку в вычислениях?

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


Конечно неправильно, т.к. надо же сумму отклонений дифференцировать, т.е. $A_1, B_1, C_1, D_1, B_2, C_2, D_2, C_3, D_3$ будут другими и вообще производные будут иными. Не вижу пока решения.

[VoloCh]

По поводу "теории".

Теория оптимизации по модулям - это дифференциальное счисление липшецевых функций. Развита Кларком (Экланом, Г.Смирновым, ...) Гуглите "производную Кларка". Но практического эффекта в вашей задаче не будет, так как вообще говоря, решение - это отрезок. Подобно тому как $|x|'=[-1;1]$. Тут "штрих" - это производная Кларка, оно (тут) совпадает с "производной" выпуклой функции.

[Алексей К.]

Tur в сообщении #333979 писал(а):

Требуется найти центр сферы и ее радиус... Это 4 неизвестных (А.К.)
Каждая прямая (шесть чисел) дает три таких уравнения. Если всего четыре прямых, то получается 12 уравнений с тремя неизвестными, (а куда делась четвёртая? А.К.)
которые решаются по http://ru.wikipedia.org/wiki/Метод_наименьших_квадратов

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

Цитата:

Но пока все это не дает верного результата. Может быть сама идея такого решения ошибочна? Или она верна и просто следует искать ошибку в вычислениях?

Идея, на мой взгляд, правильная. Скорее всего, задачка решается не в лоб, а линеаризация потребуется.
Я, может, после работы, попробую всё записать, и отвечу посодержательнее.
Задачка забавная (стала), народ, наверное, подключится.

Про МНК-окружность на плоскости я разглагольствовал здесь. Но я там обоснованно схитрил --- подменил сумму квадратов честных расстояний суммой квадратов других величин, благораря чему уравнения остались линейными.
Вам точно всё понятно с этой более простой задачкой? Основы МНК ясны? Меня чисто смутила фраза о 12-ти уравнениях...

[ewert]

Tur в сообщении #333979 писал(а):

мне показалось что решать некоторые задачи т.о. было бы проще. "проще МНК" - это утверждение, т.к. модуль разности проще квадрата разности. Наверное я ошибся.

Наверное.

Фактически Вы имеете дело с переопределённой системой линейных уравнений для двух неизвестных $(a_0,a_1)$, а именно: $a_0+a_1x_k=y_k,\ \ k=1,2,\ldots n$ или, в матричной записи, $H\vec a=\vec y$, где $h_{k1}=1$ и $h_{k2}=x_k$. Проведение "оптимальной" прямой $\{y=a_0+a_1x\}$ сводится к нахождению псевдорешения этой системы, т.е. к минимизации нормы невязки: $\|H\vec a-\vec y\|=\min$. Выбор критерия оптимизации -- это ровно выбор какой-то конкретной нормы. Методу наименьших квадратов соответствует конкретно выбор квадратичной нормы: $\|\vec u\|=\|\vec u\|_2=\sqrt{\sum\limits_{k=1}^nu_k^2}$. И это -- самый простой вариант постановки задачи, поскольку квадратичная норма -- в некотором смысле единственная, порождённая скалярным произведением. Минимизация же просто суммы расстояний означает выбор "линейной" нормы: $\|\vec u\|=\|\vec u\|_1=\sum\limits_{k=1}^n|u_k|$. Вариант -- в определённом смысле наихудший (наряду с минимизацией наибольшего расстояния, т.е. с выбором равномерной нормы), причём по двум причинам. Во-первых, обе эти нормы -- негладкие, что не есть хорошо при прочих равных условиях. Во-вторых, обе они не являются строго выпуклыми, поэтому решение может оказаться не единственным (тогда их бесконечно много).

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

[Алексей К.]

Алексей К. в сообщении #334020 писал(а):

Скорее всего, задачка решается не в лоб, а линеаризация потребуется.

По первым прикидкам, задача решается в лоб, и вполне аналогична вышеупомянутой плоской задачке. Только более громоздкие формулы. Минимизируем не $\sum\limits_i^n (r_i-R)^2$, а $\sum\limits_i^n (r_i^2-R^2)^2$. Обоснование --- $\ldots =\sum\limits_i^n (r_i-R)^2 (r_i+R)^2\approx \mathrm{const}\cdot\sum\limits_i^n (r_i-R)^2 $. Ну и комбинацию квадратичных членов заменяем линейной буковкой Ку, как в том плоском примере.

[Tur]

Первую задачу я сделал сегодня через симплекс и вот что получил

Белая линия это результат m = 0.4378 n = 2.8111
Сумма абсолютных отклонений |0.2488| + |-0.3134| + |0.5622| = 1.1245 (1245 - значения Х у исходных точек - случайное совпадение). По МНК (нулевое приближение) m = 0.4 n = 2.8 сумма абсолютных отклонений |0.2| + |-0.4| + |0.4| + |-0.2| = 1.2 (числа почти "целые" - а исходные точки я выбирал не раздумывая долго).
VoloCh, спасибо за "теорию", правда пока я ничего читабельного не нашел. Все это требует много времени, а я все делаю для того чтобы решить задачу со сферой. Там симплекс не годится, все должно решаться быстро (~20 ms), а касательных более двухсот.

Цитата:

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

ewert, как видите это не совсем так, правда возможно если симплексу дать другое начальное приближение или шаг изменения m и n (я его взял 0.001), то можно получить другую линию. А за разъяснения спасибо.

Цитата:

И это -- самый простой вариант постановки задачи

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

Цитата:

В МНК сколько уравнений --- столько и неизвестных.

Сегодня линию МНК я нашел иначе, не через функцию матлаба, а решением преопределенной системы
m*M1.X + n - M1.Y = 0
m*M2.X + n - M2.Y = 0
m*M3.X + n - M3.Y = 0
m*M4.X + n - M4.Y = 0
Результаты совпали, но почему - до конца неясно. Все это я делаю для поиска решения второй задачи со сферой. Переопределенные системы вероятно будут состоять из более простых уравнений, их, линейные, только надо получить, а решить не сложно.

Цитата:

Это 4 неизвестных (А.К.) ... Меня чисто смутила фраза о 12-ти уравнениях...

Конечно, просто я не пишу все мысли, только некоторые.

Цитата:

Минимизируем не $\sum\limits_i^n (r_i-R)^2$, а $\sum\limits_i^n (r_i^2-R^2)^2$.

В этом случае тоже получаются сложные уравнения $d((r_1^2-R^2)^2)/dx_0 = 2(r_1^2-R^2)*2r_1*r_1'$

А почему не $\sum\limits_i^n |r_i^2-R^2| ?$ Ведь о чем речь? Чтобы сделать систему уравнений решаемой и соблюсти близость к истине $\sum\limits_i^n (r_i-R)^2.$ Так?

Цитата:

Скорее всего, задачка решается не в лоб, а линеаризация потребуется.

Какая линеаризация? чего?

Цитата:

комбинацию квадратичных членов заменяем линейной буковкой Ку

Тоже неясно. Завтра я распишу производные, посмотрим.

[ewert]

Tur в сообщении #334368 писал(а):

ewert[/b], как видите это не совсем так, правда возможно если симплексу дать другое начальное приближение или шаг изменения m и n (я его взял 0.001), то можно получить другую линию.

Не знаю, что у Вас за симплекс был, но белая линия -- увы, неверна. Она проходит через точку $(5;5)$, т.е. задаётся уравнением $y=k(x-5)+5$. Сумма расстояний по вертикали до остальных точек -- это

$$F(k)=|k(1-5)+5-3|+|k(2-5)+5-4|+|k(4-5)+5-4|=|2-4k|+|1-3k|+|1-k|.$$

Вот и покачайте эту линию вокруг правой точки. При $k={1\over3}$ сумма расстояний равна ${4\over3}$, при $k={1\over2}$ получается $1$ и при $k=1$ -- $4$. А между этими значениями функция $F(k)$ зависит от $k$ линейно. Следовательно, оптимальным наклоном будет $k={1\over2}$, т.е. оптимальна -- прямая, проходящая через две крайние точки, и (в данном случае) только она.

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

[Tur]

ewert, спасибо, согласен, белая линия неверна, а верно $k={1\over2}$, т.е. m = 0.5 n = 2.5, при этом сумма расстояний 1. Все это видно невооруженным глазом. Той же функции симплекс я дал начальное приближение m = 0.5 n = 2.5 и она его подтвердила

Ошибку пока не нашел, а может ее и нет, а есть два горба у функции $S = F(m, n)$, где S - сумма расстояний. Код симплекса уже обсуждался на этом форуме?

[Алексей К.]

Алексей К. в сообщении #334117 писал(а):

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

Не. Лопухнулся.

Tur в сообщении #334368 писал(а):

Какая линеаризация? чего?

Функционал нелинеен. Я бы искал первое приближение, линеаризовал бы ф-л, (типа $F(X_0,\ldots)=F(X_0^{(0)},\ldots)+F'_{X_0}\Delta X_0+\ldots$) итерациями итерировал бы эти $\Delta X_0$, $\Delta Y_0$, $\Delta Z_0$, $\Delta R$, но делал бы по МНК и только по МНК. Возможно, от узости кругозора.
Фрмулы не сложные, просто малость громоздкие. Вообще-то и без них можно обойтись, написав простой минимайзер, который сам будет оценивать производные в окрестности очередного приближения. Их можно и в сети отыскать, наверное. Что-нибудь вроде знаменитого ЦЕРНовского MINUITа.

А разности минимизировать... Лично меня не тянет. Да ну, МНК проще.