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

Question

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

PDF Предупреждение: http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf

Я не думаю, что это ясно объяснено, я точно не понимаю.

Мое понимание того, что происходит, таково:

У нас есть набор точек (x1, y1), (x2, y2) .. и мы хотим найти несколько линий, которые лучше всего соответствуют этим данным.У нас может быть несколько прямых линий, и эти линии взяты из заданных форумов для a и b (y = ax + b).

Теперь алгоритм начинается в конце (?) И предполагает, что точка p (x_i, y_i) является частью отрезка.Тогда в заметках говорится, что оптимальным решением является «оптимальное решение для {p1,.,,pi − 1} плюс (лучшая) строка через {pi,.,,рп}».Для меня это просто означает, что мы идем к точке p (x_i, y_i) и возвращаемся назад и находим другой отрезок прямой через оставшиеся точки.Теперь оптимальным решением являются оба этих отрезка.

Затем выполняется логический переход, за которым я не могу следовать, и он говорит: «Предположим, что последняя точка pn является частью сегмента, начинающегося с p_i. Если Opt (j) обозначает стоимость первых j точек иe (j, k) ошибка наилучшей линии через точки j к k, тогда Opt (n) = e (i, n) + C + Opt (i - 1) "

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

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

Спасибо за ваше время и за чтение, я ценю это.

Answer 1

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

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

Теперь предположим, что мы пытаемся найти набор сегментов, который наилучшим образом соответствует n заданным точкам. Если бы мы знали лучшие решения для n-1 подзадач: наилучшее соответствие для первой точки, наилучшее соответствие для первых 2 точек, ..., наилучшее соответствие для первых n-1 точек, то мы могли бы рассчитать наилучшее решение для исходной задачи с n пунктов следующим образом:

n-я точка лежит на одном сегменте, и этот сегмент начинается в некоторой более ранней точке i, для некоторого i = 1, 2, ..., n. Мы уже решили все более мелкие подзадачи, то есть, имеющие менее n точек, чтобы мы могли найти наилучшее соответствие для n точек, которое минимизирует:

стоимость наилучшего соответствия для первых i-1 баллов (уже рассчитано) + стоимость одной линии, которая лучше всего подходит для точек от i до n (с использованием задачи наименьших квадратов) + стоимость использования нового сегмента

Значение i, которое минимизирует указанное выше количество, дает нам решение: используйте наилучшее соответствие для подзадачи i-1 и отрезка от точки i до n.

Если вам нужна дополнительная помощь, я написал объяснение алгоритма и предоставил реализацию C ++ здесь: http://kartikkukreja.wordpress.com/2013/10/21/segmented-least-squares-problem/

Answer 2

Сложная часть, часть динамического программирования - это часть

for j = 1 to n
    M[j] = min_(1=<i=<j) ( e(i,j) + C + M[i-1])

, где M[0] = 0 выполняется раньше, а n - общее количество точек данных. Кроме того, подчеркивание означает, что раздел в скобках впоследствии должен быть подписан. Профессор вполне мог бы использовать OPT вместо M, и это делается в лекциях других университетов об этом, которые вы можете найти в Интернете (и которые выглядят почти одинаково). Теперь, если вы посмотрите на мой блок кода выше и на лекции, вы заметите разницу. Я использовал M[i-1], а ваш профессор использовал M[j-1]. Это опечатка в псевдокоде вашего профессора. Вы даже можете посмотреть назад на слайд и убедиться, что он исправил его в функции ошибок.

По сути, для каждого j вы находите точку i, чтобы нарисовать линию к j так, чтобы ее ошибка, плюс стоимость добавления этой дополнительной линии (C) плюс стоимость создания всех отрезков линии к i (который уже был выбран оптимально) минимизируется.

Кроме того, помните, что e(i,i) = 0, а также e(i,i+1), потому что при подгонке линии к точке нет ошибки, равно как и к двум точкам.

Answer 3

Начиная с точки 1, наилучшее решение вплоть до точки j, должно включать новую конечную точку j в последнем отрезке линии, поэтому возникает проблема, где мне нужно разместить последнее разбиение, чтобы минимизировать стоимость этого последний отрезок?

К счастью, стоимость рассчитывается в терминах подзадач той же проблемы, которую вы пытаетесь решить, и, к счастью, вы уже решили эти меньшие подзадачи к тому времени, как перешли к следующей точке j. Таким образом, в новой точке j вы пытаетесь найти оптимальную точку i между точками 1 и j, чтобы отделить новый отрезок линии, который включает в себя j, и минимизирует стоимость: optim_cost_up_to (i) + cost_of_split + cost_of_lsq_fit (i + 1 , к). Теперь запутанная часть заключается в том, что в любой момент может показаться, что вы просто находите один сплит, но на самом деле все предыдущие сплиты определяются с помощью optim_cost_up_to (i), и поскольку вы уже рассчитали оптимальную стоимость для всех этих точек если перейти к j, то вам просто нужно запомнить ответы, чтобы алгоритму не приходилось пересчитывать эти затраты каждый раз, когда он увеличивает точку.

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

в любом случае ...

    def optimalSolution(points,split_cost)
        solutions = {0:{'cost':0,'splits':[]}}
        for j in range(1,len(points)):
            best_split = None
            best_cost = lsqFitCost(points,0,j)
            for i in range(0,j):
                cost = solutions[i]['cost'] + split_cost + lsqFitCost(points,i+1,j)
                if cost < best_cost:
                   best_cost = cost
                   best_split = i
            if best_split != None:
                solution[j] = {'cost':best_cost,'splits':solution[best_split]['splits']+[best_split]}
            else:
                solution[j] = {'cost':best_cost,'splits':[]}
        return solutions

это не красиво, и я не проверял это (может быть ошибка, связанная со случаем, когда нет разделения - лучшая цена), но, надеюсь, это поможет вам выбрать правильный путь? Обратите внимание, что lsqFitCost должен выполнять большую работу на каждой итерации, но для подгонки линии наименьших квадратов вы можете сделать эту стоимость намного меньше, поддерживая текущие суммы, используемые в вычислениях ... вам следует подгонять линию наименьших квадратов Google для больше информации. Это может сделать lsqFitCost постоянным, поэтому общее время будет равно O (N ^ 2).

Answer 4

Основная предпосылка динамического программирования состоит в том, чтобы рекурсивно оптимизировать (снизить «стоимость» или, в этом случае, ошибку) проблемы, сохраняя при этом стоимость подзадач, чтобы они не пересчитывались (это называется запоминанием).

Уже немного поздно, поэтому я не буду вдаваться в подробности, но, похоже, часть, с которой у вас больше всего проблем, это само ядро ​​DP. DP необходим здесь из-за «сегментированного» качества. Как показывает ваш PDF, поиск линии наилучшего соответствия по методу наименьших квадратов прост и не требует DP.

Opt (n) - e (i, n) + C + Opt (i-1) --- наша функция стоимости, где
C - это постоянная стоимость нового отрезка (без которой проблема тривиальна, и мы просто сделаем новые отрезки для каждых двух точек)
e (i, n) - ошибка точек от i до n с ОДНЫМ сегментом (не рекурсивная)
Опция (i-1) - это рекурсивная наименьшая стоимость от первой точки до (i-1) -го

Теперь алгоритм

Убедитесь, что список точек отсортирован по значениям x
M [0] = 0 --- говорит само за себя
Для всех пар (i, j) с i Для (j = 1..n): M [j] = min ([opt (j) для i в диапазоне (1, j)]

Итак, в общем, найдите стоимость в одну строку между любыми двумя возможными точками, сохраните в e
Найдите наименьшую стоимость до j, для j от 1 до n. Значения по пути помогут в дальнейшем вычислении, так что сохраните их! Обратите внимание, что я также являюсь параметром для выбора. M [n] - общая оптимизированная стоимость.

Вопрос к вам - Как вы можете определить, где происходит сегментация? Как вы можете использовать это и M, чтобы определить набор отрезков, когда все закончится?

Надеюсь, это поможет!