Целочисленный размер шага в scipy optimize минимизировать

Question

У меня есть алгоритм компьютерного зрения, который я хочу настроить с помощью scipy.optimize.minimize. Прямо сейчас я хочу настроить только два параметра, но число параметров может в конечном итоге увеличиться, поэтому я хотел бы использовать технику, которая может выполнять поиск в многомерном градиенте. Реализация Nelder-Mead в SciPy казалась подходящей.

Я установил весь код, но кажется, что функция минимизации действительно хочет использовать значения с плавающей запятой с размером шага меньше единицы. Текущий набор параметров является целым числом, и один имеет размер шага один, а другой имеет размер шага два (т.е. значение должно быть нечетным, если это не то, что я пытаюсь оптимизировать, преобразует его в нечетное число). Примерно один параметр - это размер окна в пикселях, а другой параметр - пороговое значение (значение от 0 до 255).

Для чего это стоит, я использую свежую сборку scipy из git repo. Кто-нибудь знает, как сказать scipy использовать определенный размер шага для каждого параметра? Есть ли способ, которым я могу свернуть свою собственную функцию градиента? Есть ли какой-нибудь скучный флаг, который может мне помочь? Я знаю, что это можно сделать с помощью простой развертки параметров, но в конечном итоге я хотел бы применить этот код к гораздо большим наборам параметров.

Сам код очень прост:

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

Вот как выглядит мой вывод. Как видите, мы повторяем много прогонов и нигде не минимизируем.

*+++++++++++++++++++++++++++++++++++++++++
[ 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

Предполагая, что функция минимизации является произвольно сложной (нелинейной), это в общем очень сложная проблема. Он не может быть гарантированно решен оптимально, если вы не попробуете все возможные варианты. Я не знаю, существует ли какой-либо нелинейный оптимизатор с целочисленными ограничениями (несколько сомневаюсь в этом), и я предполагаю, что вы знаете, что Nelder-Mead должен работать нормально, если это была смежная функция.

Редактировать: Учитывая комментарий от @Dougal, я просто добавлю сюда: Сначала настройте грубый + точный поиск по сетке, если затем вам захочется попробовать, если ваш Nelder-Mead работает (и сходится быстрее), приведенные ниже пункты могут помочь...

Но, возможно, некоторые моменты, которые помогают:

1. Учитывая, что целое целочисленное ограничение очень сложно, возможно, было бы целесообразно выполнить простую интерполяцию, чтобы помочь оптимизатору. Это все еще должно сходиться к целочисленному решению. Конечно, это требует подсчета дополнительных очков, но это может решить многие другие проблемы. (даже в линейном целочисленном программировании, как правило, сначала решается неограниченная система AFAIK)
2. Nelder-Mead начинается с N+1 очков, они жестко зашиты в scipy (по крайней мере, старые версии), чтобы (1+0.05) * x0[j] (за j во всех измерениях, если только x0[j] 0), что вы увидите на первых этапах оценки. Возможно, они могут быть предоставлены в более новых версиях, в противном случае вы можете просто изменить / скопировать код scipy (это чистый python) и установить его на что-то более разумное. Или, если вам кажется, что это проще, уменьшите все входные переменные так, чтобы (1+0,05)*x0 имело разумный размер.
3. Возможно, вам следует кэшировать все оценки функций, так как, если вы используете Nelder-Mead, я думаю, вы всегда можете столкнуться с оценкой дубликатов (по крайней мере, в конце).
4. Вы должны проверить, насколько вероятно, что Nelder-Mead просто сократится до одного значения и сдастся, потому что он всегда находит один и тот же результат.
5. Как правило, вы должны проверить, хорошо ли ведет себя ваша функция... Эта оптимизация обречена, если функция не изменяется плавно в пространстве параметров, и даже в этом случае она может легко столкнуться с локальными минимумами, если они у вас есть. (поскольку вы кэшировали все оценки - см. 2. - вы могли бы, по крайней мере, построить их и взглянуть на ландшафт ошибок, не выполняя никаких дополнительных проверок)

Answer 2

К сожалению, встроенные инструменты оптимизации Scipy не позволяют этого легко сделать. Но никогда не бойся; Похоже, у вас выпуклая проблема, и поэтому вы сможете найти уникальный оптимум, даже если он не будет математически красивым.

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

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

Более медленная, но потенциально более надежная альтернатива - реализовать деление пополам для каждого тестируемого параметра. Если вы знаете, что проблема совместно выпукла в двух ваших параметрах (или n параметрах), вы можете разделить ее на n одномерных задач оптимизации и написать алгоритм деления пополам, который рекурсивно оттачивает оптимальные параметры. Это может помочь справиться с некоторыми типами квазивыпуклости (например, если ваша функция потерь принимает значение фонового шума для части своей области и является выпуклой в другой области), но требует хорошего предположения относительно границ для начальной итерации.

Если вы просто нажмете запрошенный x значения в целочисленную сетку без фиксации xtol Чтобы отобразить этот размер сетки, вы рискуете, если решатель запросит две точки в ячейке сетки, получит одинаковое выходное значение и придет к выводу, что оно как минимум.

Нет простого ответа, к сожалению.

Answer 3

Привязать ваши поплавки x, y (он же winsize, threshold) к целочисленной сетке внутри вашей функции, например так:

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

Тогда Nelder-Mead увидит значения функции только в сетке и должен дать вам почти целое число x, y.

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

Answer 4

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

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

Answer 5

Проблема в том, что алгоритм застревает, пытаясь уменьшить свой (N+1) симплекс. Я настоятельно рекомендую всем, кто плохо знаком с этой концепцией, узнать больше о географической форме симплекса и выяснить, как входные параметры соотносятся с точками на симплексе. Как только вы поймете это, то, как предложил IP Freeley, проблема может быть решена путем определения сильных начальных точек для вашего симплекса. Обратите внимание, что это отличается от определения вашего x0 и входит в специальные параметры nelder-mead . Вот пример более высокой --4-- мерной задачи. Также обратите внимание, что исходный симплекс должен иметь N+1 точек, в данном случае 5, а в вашем случае 3.

      init_simplex = np.array([[1, .1, .3, .3], [.1, 1, .3, .3], [.1, .1, 5, .3],
                         [.1, .1, .3, 5], [1, 1, 5, 5]])
minimum = minimize(Optimize.simplex_objective, x0=np.array([.01, .01, .01, .01]),
                   method='Nelder-Mead',
                   options={'adaptive': True, 'xatol': 0.1, 'fatol': .00001,
                            'initial_simplex': init_simplex})

В этом примере x0 игнорируется определением initial_simplex. Другой полезной опцией в задачах большой размерности является «адаптивная» опция, которая учитывает количество параметров при попытке установить рабочие коэффициенты модели (т. е. α, γ, ρ и σ для отражения, расширения, сжатия и сжатия соответственно). . И если вы еще этого не сделали, я бы также рекомендовал ознакомиться с шагами алгоритма.

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