Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Category:

Автоподбор параметров

Пилим тут https://github.com/streamcode9/node-discrete-spsa

An implementation of the Discrete Simultaneous Perturbation Stochastic Aproximation algorithm.

See Stacy D. Hill, "Discrete Stochastic Approximation with Application to Resource Allocation", 2005 http://www.jhuapl.edu/SPSA/PDF-SPSA/Hill_TechDig05.pdf

Cам алгоритм на 5-й странице step1-5, прост как палка.

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

Это всё равно бесконечная игра с подбором learning rate, но наверное получше будет, чем наивный подход "просемплировать всё пространство состояний с заданным шагом, используя статистически значимые бенчмарки".

Трюк в том, что вместо рассчёта градиента через частные производные, которые приближаем конечными разностями, используем 1-мерную конечную разность в случайном направлении. Которая, о чудо, оказывается (несмещённой статистической) оценкой градиента. И при этом требует вычислить целевую функцию всего 2 раза на итерацию, вместо стольки раз, сколько у нас частных производных + 1.

Вдобавок, оно работает нормально для зашумлённых целевых функций. Т.е. рандомность бенчмарков устранять не надо. И даже в случае целочисленных параметров и пространства разрешённых состояний произвольной формы (ну может почти произвольной, я в детали не вникал).
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments