Tamaño de paso entero en scipy optimize minimize

Question

Tengo un algoritmo de visión por computadora que quiero sintonizar usando scipy.optimize.minimize. En este momento, solo quiero ajustar dos parámetros, pero la cantidad de parámetros eventualmente podría aumentar, por lo que me gustaría utilizar una técnica que pueda realizar búsquedas graduales de gran dimensión. La implementación de Nelder-Mead en SciPy parecía una buena opción.

Tengo todo el código configurado, pero parece que la función de minimizar realmente quiere usar valores de punto flotante con un tamaño de paso inferior a uno. El conjunto actual de parámetros son ambos enteros y uno tiene un tamaño de paso de uno y otro tiene un tamaño de paso de dos (es decir, el valor debe ser impar, si no es lo que estoy tratando de optimizar, lo convertirá en un número impar). Aproximadamente un parámetro es un tamaño de ventana en píxeles y el otro parámetro es un umbral (un valor de 0-255).

Por lo que vale, estoy usando una compilación nueva de scipy del repositorio git. ¿Alguien sabe cómo decirle a scipy que use un tamaño de paso específico para cada parámetro? ¿Hay alguna manera de que pueda rodar mi propia función de gradiente? ¿Hay alguna bandera falsa que me pueda ayudar? Soy consciente de que esto podría hacerse con un simple barrido de parámetros, pero finalmente me gustaría aplicar este código a conjuntos de parámetros mucho más grandes.

El código en sí es muy simple:

import numpy as np 
from scipy.optimize import minimize 
from ScannerUtil import straightenImg 
import bson 

def doSingleIteration(parameters): 
    # do some machine vision magic 
    # return the difference between my value and the truth value 

parameters = np.array([11,10]) 
res = minimize(doSingleIteration, parameters, method='Nelder-Mead',options={'xtol': 1e-2, 'disp': True,'ftol':1.0,}) #not sure if these params do anything 
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" 
print res 

Esto es lo que mi salida se parece. Como puede ver, estamos repitiendo muchas carreras y no estamos llegando a ninguna parte en la minimización.

*+++++++++++++++++++++++++++++++++++++++++ 
[ 11. 10.] <-- Output from scipy minimize 
{'block_size': 11, 'degree': 10} <-- input to my algorithm rounded and made int 
+++++++++++++++++++++++++++++++++++++++++ 
120 <-- output of the function I am trying to minimize 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.55 10. ] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11. 10.5] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.55 9.5 ] 
{'block_size': 11, 'degree': 9} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.1375 10.25 ] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.275 10. ] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11. 10.25] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.275 9.75 ] 
{'block_size': 11, 'degree': 9} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
+++++++++++++++++++++++++++++++++++++++++ 
~~~ 
SNIP 
~~~ 
+++++++++++++++++++++++++++++++++++++++++ 
[ 11.   10.0078125] 
{'block_size': 11, 'degree': 10} 
+++++++++++++++++++++++++++++++++++++++++ 
120 
Optimization terminated successfully. 
     Current function value: 120.000000 
     Iterations: 7 
     Function evaluations: 27 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
    status: 0 
    nfev: 27 
success: True 
    fun: 120.0 
     x: array([ 11., 10.]) 
message: 'Optimization terminated successfully.' 
    nit: 7* 

Answer 1

Suponiendo que la función de minimizar es arbitrariamente compleja (no lineal), este es un problema muy difícil en general. No se puede garantizar que se resuelva de manera óptima a menos que pruebe todas las opciones posibles. Hago no sé si hay algún optimizador no lineal con números enteros (de alguna manera lo dudo) y asumiré que usted sabe que Nelder-Mead debería funcionar bien si fuera una función contigua.

Editar: Teniendo en cuenta el comentario de @Dougal lo voy a agregar aquí: Primero configure una grilla gruesa + fina, si le apetece probar si su Nelder-Mead funciona (y converge más rápido), los puntos a continuación pueden ... ayudar a

Pero tal vez algunos puntos que ayudan a:

1. teniendo en cuenta cómo toda la restricción de número entero es muy difícil, tal vez sería una opción para hacer un poco de interpolación simple para ayudar a que el optimizador. Aún debe converger a una solución entera. Por supuesto, esto requiere calcular puntos extra, pero podría resolver muchos otros problemas. (incluso en la programación lineal entera es común resolver el sistema no restringido primero AFAIK)
2. Nelder-Mead comienza con N + 1 puntos, estos están cableados en scipy (al menos versiones anteriores) a (1+0.05) * x0[j] (para j en todas las dimensiones, a menos que x0[j] sea 0), que verá en sus primeros pasos de evaluación. Tal vez estos pueden ser suministrados en versiones más nuevas, de lo contrario podría simplemente cambiar/copiar el código scipy (es python puro) y establecerlo en algo más razonable. O si cree que es más simple, escale todas las variables de entrada para que (1 + 0.05) * x0 sea de tamaño razonable.
3. Tal vez debería almacenar en caché todas las evaluaciones de funciones, ya que si usa Nelder-Mead supongo que siempre puede ejecutar la evaluación de duplicados (al menos al final).
4. Tienes que comprobar la probabilidad de que Nelder-Mead se reduzca a un solo valor y se dé por vencido, porque siempre encuentra el mismo resultado.
5. Por lo general, debe verificar si su función se comporta bien ... Esta optimización está condenada si la función no cambia sin problemas en el espacio de parámetros, y aun así puede ejecutarse fácilmente en mínimos locales si debe tener esos . (dado que guardó en caché todas las evaluaciones - vea 2. - al menos puede trazarlas y echar un vistazo al panorama de errores sin necesidad de hacer ningún cálculo adicional)

Answer 2

Ajustar sus flotadores x, y (aka winsize, umbral) a una red de número entero dentro de su función, así:

def func(x, y): 
    x = round(x) 
    y = round((y - 1)/2) * 2 + 1 # 1 3 5 ... 
    ... 

Entonces Nelder-Mead verá valores de la función única de la parrilla, y deben darle casi entero x, y.

(Si había cuidado para publicar su código en algún lugar, estoy en busca de casos de prueba para un Nelder-Mead con reinicios.)

Answer 3

Desafortunadamente, Scipy de herramientas integradas de optimización no permiten fácilmente para esto. Pero nunca temas; parece que tiene un problema convexo, por lo que debería poder encontrar un óptimo único, incluso si no fuera matemáticamente bonito.

Dos opciones que he implementado para diferentes problemas son la creación de un algoritmo personalizado de descenso de gradiente y el uso de bisección en una serie de problemas univariados. Si está haciendo una validación cruzada en su ajuste, desafortunadamente su función de pérdida no será uniforme (debido al ruido de la validación cruzada en diferentes conjuntos de datos), pero generalmente será convexa.

Para implementar el descenso de gradiente numéricamente (sin tener un método analítico para evaluar el degradado), elija un punto de prueba y un segundo punto que sea delta lejos de su punto de prueba en todas las dimensiones. Evaluar su función de pérdida en estos dos puntos puede permitirle calcular numéricamente un subgrado local. Es importante que delta sea lo suficientemente grande como para salir de los mínimos locales creados por el ruido de validación cruzada.

Una alternativa más lenta pero potencialmente más robusta es implementar la bisección para cada parámetro que está probando. Si sabe que el problema se expresa conjuntamente en sus dos parámetros (o n), puede separar esto en n problemas de optimización univariada y escriba un algoritmo de bisección que busque de forma recursiva los parámetros óptimos. Esto puede ayudar a manejar algunos tipos de cuasiconvexidad (por ejemplo, si su función de pérdida toma un valor de ruido de fondo para parte de su dominio, y es convexa en otra región), pero requiere una buena estimación de los límites de la iteración inicial.

Si simplemente ojear los solicitados x valores a una red de número entero sin fijar xtol para asignar a ese gridSize, te arriesgas a que la solicitud solucionador de dos puntos dentro de una celda de la cuadrícula, recibiendo el mismo valor de salida, y concluyendo que es en un mínimo.

No es una respuesta fácil, lamentablemente.

Answer 4

El método Minimizar de Nelder-Mead ahora le permite especificar los puntos vértice simples iniciales, por lo que debe poder separar los puntos símplex, y el símplex se desplazará y encontrará el mínimo y convergerá cuando el tamaño simple desciende por debajo de 1.

https://docs.scipy.org/doc/scipy/reference/optimize.minimize-neldermead.html#optimize-minimize-neldermead