метод наибольших квадратов :)

Тема в разделе "WASM.A&O", создана пользователем persicum, 30 ноя 2010.

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Есть N точек.
    Нужно провести полином степени К<N, который бы точно проходил через максимальное число точек. На отклонения выпадающих точек начхать =)))
     
  2. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    persicum
    Этот полином в большинстве случаев будет проходить через K точек, и если повезёт на него могут попасть еще какие-то точки, решение в лоб - перебирать все подмножества из К точек.
     
  3. Ravager

    Ravager New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2008
    Сообщения:
    34
    Если начальные данные случайны, вероятность того, что полином пройдёт через более, чем K точек, равна 0, так что можно просто взять K произвольных точек и построить полином по ним.
     
  4. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    не-не, задачка не имеет ничего общего с ошибками астрономических измерений или NP-полным перебором! Она относится к кодированию, хочу построить свой шифр и декодировать его таким образом. Вроде достаточно методом евклида найти НОД пары полиномов (длинного и покороче), но как их постороить ума не приложу =(((
     
  5. _sheva740

    _sheva740 New Member

    Публикаций:
    0
    Регистрация:
    31 авг 2005
    Сообщения:
    1.539
    Адрес:
    Poland
    Я конечно могу ошибиться,
    но если точек n , а полином
    степени k<n, то он пройдет через все точки.

    Ну по аналогии
    прямая y=x^1 - 2 точки
    парабола y=x^2 - 3 точки
    ...
    ... y=x^k - n точек, где n>k

    Или я не в теме?
     
  6. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Все праильна, интерполяционный полином степени N-1 проходит через N точек и единственен. Но я имел в виду K<<N =))) Иначе задача решается неоднозначно (декодирование невозможно)
     
  7. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Как выглядит хи-квадрат как функция от K переменных (коэффициентов полинома) при изменении любого (нескольких) из них? Есть ли локальные минимумы и "основной" минимум?

    Точки заданы целыми числами?
     
  8. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    PSR1257
    Квадратичная форма имеет только один глобальный минимум?
    Ошибок округления нет, ну и плюс надо не минимизировать расстояния (как в МНК), а максимизировать число точек, через которые полином проходит точно.
     
  9. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Не знаю, но если Хи даже с несколькими (число их кратно K?) экстремумами - их можно искать быстрее чем полным перебором.

    Это понятно. Не уверен, но возможно можно аналитически показать что для некоторого K0 и N0 или какой-то f(K0,N0) невозможно для N случайно заданных точек провести полином через них точно (те оклонение точно 0.000..).

    Может быть вы имеете в виду что при "шифровании" задаются N точек заданных ЦЕЛЫМИ числами которые заведомо принадлежат некоему ЗАДАННОМУ полиному K-степени, т.е. задача заведомо имеет точное решение просто нужно найти его?
     
  10. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Разумеется, так оно и есть!
    Вместо полинома степени K-1 удобнее говорить о наборе из К коэффициентов.
    Имея К коэффициентов, можно настругать сколько угодно, т.е. N точек. Это будет кодовым представлением этих К коэффициентов-символов с внесенной избыточностью.

    Если известно, что некоторые любые K из N точек заведомо верны, то сообщение можно декодировать решив систему уравнений с матрицей вандермонда K x K (интерполяция).

    А если не известно, какие именно символы из N полученных точек верны, то задача декодирования усложняется.

    Разумеется, на смежные темы имеется множество литературы вроде спектрального регрессионного анализа Берлекампа-Месси и тому подобное, но для меня все это бесполезно.

    Как известно, мамаша Коала вскармливает своих медвежат собственным калом, поскольку листья эвкалипта очень тверды и малосъедобны. Тожасть самое относительно специальной литературы - она мне не по зубам. Мне нужно все разжевать и показать на простом примере, как провести полином К через N точек чтобы максимизировать число точек, через которые полином проходит точно. Тогда я смогу это запрогать.
     
  11. baldr

    baldr New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    327
    persicum,

    Тогда критерий этой самой «максимальности» нужно чётко определить. Для десяти точек полином степени 5, проходящий через 8 точек, лучше полинома степени 6, проходящего через 9 точек?
     
  12. Ravager

    Ravager New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2008
    Сообщения:
    34
    K задано в условии, как я понимаю.
     
  13. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    persicum

    Опишите схему шифрования и обмена шифроданными - ?

    Пока как я понял у Фокса и Дейны есть общий никому неизвестный полином степени K. Фокс выбирает случайным образом N точек - все принадлежат полиному - и засылает их Дейне. Плохо понятно где здесь обмен данными?

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

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Откель растет такая уважуха? =)))

    Оставим злоумышленников в стороне пока вместе с Бобом и Алисой.
    Рассмотрим просто помехоустойчивый код без ключей.

    Классический Рид-Соломон работает так:
    Информационный полином К умножаем на генераторный полином G и получаем кодовое слово избыточной длины по сравнению с К. Передаем абракадабру по каналу с ошибками. Декодируем.

    Неклассические коды Рида-Соломона работают так:
    Информационный полином К эвалюционируем для некоторых известных принимающей стороне X1..XN и получаем то что я называю N точек - Y1..YN. Передаем вектор Y по каналу с помехами. Вопрос: как декодировать?
     
  15. baldr

    baldr New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    327
    persicum,

    По выборке фактов можно построить любую гипотезу. "Эвалюционируем" -- вычисляем, что ли?
     
  16. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Нужна максимально правдоподобная гипотеза. Перебор очевидно не годится.
     
  17. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Предположим, K = N/2.
    Тогда можно построить 2 полинома степени (K-1) - один для истинных точек, второй - для мусорных. Как определить какой из них нужный? Очевидно, никак. Далее предположим, что K = N/2 + 1. Где гарантия, что оставшиеся (N/2 - 1) мусорных точек не образуют более "длинный" полином степени (K - 1) с некоторыми точками из истинных? И так далее.
    Да что тут разглагольствовать, вот пример:
    Берём 2 полинома: x+(x^4-4*x^2+1) и x-(x^4-4*x^2+1).
    Пусть N = 5, K = N - 1 = 4, и все истинные точки соответствуют пересечениям полиномов (на рисунке отмечены фиолетовым). Разбавим истинные значения всего лишь одним мусорным (на рисунке обозначено синей точкой).
    Как видим, по заданным точкам можно провести 2 полинома, оба степени K - 1. Один из которых, истинный, будет проходить через 4 точки, а второй, мусорный, через 5 точек.
    Это конечно редкий случай, и, возможно, его можно обойти, но вряд ли есть другой способ кроме как перебор всех возможных полиномов степени K - 1 с проверкой - не будет ли существовать полином "длиннее", если добавить очередную мусорную точку.
    [​IMG]

    Uploaded with ImageShack.us
     
  18. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    KeSqueer
    Спасибо за красочный рассказ в картинках!
    Вот только опасения напрасны - вы демонстрируете невозможность исправления ошибок при отсутствии избыточности. Кто бы сомневался! Все правильно, если число коэффициентов K (так удобнее, чтобы не вычитать единицу) равно N, то исправить ничего нельзя, поскольку даже одна ошибка переведет интерполяционный полином в другой K'.
    В общем, N=K+2T должен исправлять T ошибок однозначно.

    Для вашего случая надо рассмотреть не 5, а семь N. При выпадании одной точки все неправильные полиномы K'=5 будут покрывать только 5 точек, а правильный полином K=5 будет покрывать уже шесть точек, и может быть ущучен!
     
  19. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Алгоритм с числом операций K! или exp(K) очевидно не имеет практической ценности для не очень малых K. Интересует что-то типа ln(K) как в алгоритме Евклида получения Наибольшего Общего Делителя. Смущает только, что матерые лбы Рид и Соломон в своих там 60-х пошли другим путем, оставив этот более простой и быстрый в вычислительном плане вариант для кодирования. Видать, в самом общем виде, когда места ошибок неизвестны, неклассический алгоритм может требовать слишком много вычислений на декодирование. =(((
     
  20. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    persicum
    Осознал. Не учёл того факта, что не все "наструганные" точки обязаны быть избыточными.

    Хорошо. Давайте упростим задачу до "не могу".
    Раскидаем по плоскости пару сотен точек, с условием, что их координаты должны быть целыми числами (чтобы ещё проще). Как провести прямую через максимальное количество точек? Очевидно, перебором. Других мыслей пока нет.