algoritmo de mínimos cuadrados segmentados, no entiendo este concepto de programación dinámica en absoluto

Question

He estado tratando de implementar este algoritmo en Python durante unos días. Sigo volviendo a eso y simplemente me rindo y frustrado. No sé qué está pasando. No tengo a nadie a quien preguntar ni a ningún lado para pedir ayuda, así que he venido aquí.

PDF Advertencia: http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf

no creo que es un explicarse claramente, estoy seguro que no entiendo.

Mi comprensión de lo que sucede es lo siguiente:

Tenemos un conjunto de los puntos (x1, y1), (x2, y2) .. y queremos encontrar algunas líneas que mejor se adapten a estos datos. Podemos tener múltiples líneas rectas, y estas líneas provienen de los foros para a y b (y = ax + b).

Ahora el algoritmo comienza en el final (?) Y asume que un punto p (x_i, y_i) es parte del segmento de línea. Entonces las notas dicen que la solución óptima es 'es la solución óptima para {p1,. . . pi-1} más (mejor) línea a través de {pi,. . . pn} '. Lo cual solo significa para mí, que vayamos al punto p (x_i, y_i) y retrocedamos y busquemos otro segmento de línea a través del resto de los puntos. Ahora la solución óptima son estos dos segmentos de línea.

Luego toma un salto lógico que no puedo seguir y dice "Supongamos que el último punto pn es parte de un segmento que comienza en p_i. Si Opt (j) indica el costo de los primeros j puntos y e (j, k) el error de la mejor línea a través de los puntos j a k luego Opt (n) = e (i, n) + C + Opt (i - 1) "

Luego está el pseudocódigo para el algoritmo que no entiendo Entiendo que queremos iterar a través de la lista de puntos y encontrar los puntos que minimizan la fórmula OPT (n), pero simplemente no la sigo. Me está haciendo sentir estúpido.

Sé que esta pregunta es un dolor en el trasero y que no es fácil de responder, pero estoy buscando alguna guía para entender este algoritmo. Me disculpo por el PDF, pero no tengo una manera más clara de obtener la información crucial para el lector.

Gracias por su tiempo y leyendo esto, lo agradezco.

Answer 1

La premisa básica de la programación dinámica es optimizar (reducir el 'costo' o en este caso, el error) de un problema recursivamente mientras se almacena el costo de los subproblemas sobre la marcha para que no se vuelvan a calcular (esto se llama memoria) .

Es un poco tarde, así que no voy a ser demasiado detallado, pero parece que la parte con la que tienes más problemas es el núcleo DP en sí. DP es necesario aquí debido a la calidad 'segmeneted'. Como muestra su PDF, encontrar la línea que mejor se ajusta por mínimos cuadrados es simple y no requiere DP.

Opt (n) - e (i, n) + C + Opt (i-1) --- nuestra función de coste donde
C es el costo constante de un nuevo segmento de línea (sin la cual el problema es trivial y solo haríamos nuevos segmentos de línea por cada dos puntos)
e (i, n) es el error de los puntos i a n con UN segmento (no recursivo)
Opt (i-1) es el menos costo de forma recursiva desde el primer punto hasta el (i-1) -ésimo

Ahora el algoritmo

Asegúrese de que la lista de puntos se ordena por los valores x
M [0] = 0 --- explica por sí mismo
para todos los pares (i, j) con i < j: encontrar e (i, j) - --- (Esto requerirá anidados para/foreach loops, o un tipo de estructura de comprensión. Almacenar estos valores en matriz 2D)
Para (j = 1..n): M [j] = min (! [Opt (j) para i en el rango de (1, j)]

Así básicamente, encuentre el costo de una línea entre dos posibles puntos, almacene en e
Encuentre el menor costo hasta j, para j entre 1 y n. Los valores a lo largo del camino le ayudarán con el cálculo posterior, así que guárdelos! i es un parámetro para Optar también. M [n] es el costo total optimizado

Pregunta para usted - ¿Cómo puede determinar dónde se produce la segmentación? ¿Cómo puede usar esto, y M, para determinar el conjunto de segmentos de línea una vez que ts todo?

Espero que esto ayude!

Answer 2

La parte difícil, la parte de programación dinámica, es la sección

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

donde M[0] = 0 se hace antes y n es el número total de puntos de datos. Además, el guión bajo significa que la sección entre paréntesis después debe estar suscrita. El profesor bien podría haber usado OPT en lugar de M, y esto se hace en otras conferencias de otras universidades sobre esto que se pueden encontrar en la web (y que se ven casi idénticas). Ahora, si miras mi bloque de códigos de arriba y eso en la conferencia, notarás una diferencia. Usé M[i-1] y su profesor usó M[j-1]. Es un error tipográfico en el pseudocódigo de tu profesor. Incluso puede mirar hacia atrás a la diapositiva anterior y ver que la tenía correcta en la función de error allí.

Básicamente, para cada j, está encontrando el punto i para trazar una línea a j de tal que el error de la misma, más el costo de agregar esta línea adicional (C), más el costo de hacer todos los segmentos de línea hasta i (que ya se ha elegido de manera óptima) se minimiza.

Además, recuerde que e(i,i) = 0 así como e(i,i+1) porque el ajuste de una línea a un punto no ofrece ningún error además de solo dos puntos.

Answer 3

A partir del punto 1, la mejor solución hasta un punto j, debe incluir el nuevo punto final j en el último segmento de línea, por lo que el problema es dónde tengo que colocar la última división para minimizar el costo de este último segmento de línea?

Afortunadamente el costo se calcula en términos de subproblemas del mismo problema que está tratando de resolver, y afortunadamente ya ha resuelto estos subproblemas más pequeños para cuando se haya movido al siguiente punto j. Entonces en el nuevo punto j estás tratando de encontrar un punto óptimo i, entre los puntos 1 y j, para dividir un nuevo segmento de línea que incluya j, y minimiza el costo: optimum_cost_up_to (i) + cost_of_split + cost_of_lsq_fit (i + 1 , j). Ahora la parte confusa es que en cualquier punto podría parecer que estás encontrando una sola división, pero en realidad todas las divisiones anteriores están determinadas por optimum_cost_up_to (i), y como ya has calculado el costo óptimo para todos estos puntos conduciendo a j, entonces solo necesita memorizar las respuestas para que el algoritmo no tenga que volver a calcular estos costos cada vez que avance un punto.

en Python probablemente me usar un diccionario para almacenar los resultados, aunque para este algoritmo de programación dinámica una matriz podría ser mejor ...

de todos modos ...

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 

no es bastante , y no lo he comprobado (puede haber un error que involucre el caso en que ninguna división es el mejor costo), pero con suerte lo ayudará a estar en el camino correcto. Tenga en cuenta que lsqFitCost tiene que trabajar mucho en cada iteración, pero para una línea de mínimos cuadrados que se ajuste de esta manera, puede hacer que este costo sea mucho menor manteniendo las sumas utilizadas en el cálculo ... debe hacer un ajuste de línea de mínimos cuadrados para Google más información. Esto podría hacer que lsqFitCost sea constante, por lo que el tiempo total sería O (N^2).

Answer 4

El problema de mínimos cuadrados pide encontrar una sola línea de mejor ajuste para los puntos dados y tiene una buena solución de formulario cerrado. Esta solución se usa como una primitiva para resolver el problema de mínimos cuadrados segmentados.

En el problema de mínimos cuadrados segmentados, podemos tener cualquier número de segmentos para ajustarse a los puntos dados y tenemos que pagar un costo por cada nuevo segmento utilizado. Si el costo de usar un nuevo segmento era 0, podríamos ajustar todos los puntos al pasar una línea separada a través de cada punto.

Supongamos ahora que estamos tratando de encontrar el conjunto de segmentos que mejor se ajusta a los n puntos dados. Si conociéramos las mejores soluciones para los subproblemas n-1: la mejor opción para el primer punto, la mejor opción para los primeros 2 puntos, ..., la mejor opción para los primeros n-1 puntos, entonces podríamos calcular la mejor solución para el problema original con n puntos de la siguiente manera:

El enésimo punto se encuentra en un solo segmento y este segmento comienza en algún punto anterior i, para algunos i = 1, 2, ..., n. Ya hemos resuelto todos los subproblemas más pequeños, es decir, que tiene menos de n puntos para que podamos encontrar el mejor ajuste para n puntos que minimiza:

coste de mejor ajuste para la primera i-1 puntos (ya computarizada) + coste de un solo línea que se ajusta mejor a los puntos i a n (usando el problema de mínimos cuadrados) + costo de usar un nuevo segmento

El valor de i que minimiza la cantidad anterior nos da la solución: use el mejor ajuste para el subproblema i- 1 y el segmento a través del punto i a n.

Si necesita más ayuda, he escrito una explicación del algoritmo y con tal implementación en C++ aquí: http://kartikkukreja.wordpress.com/2013/10/21/segmented-least-squares-problem/