• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

The Twiddle Algorithm

Contents

  • The algorithm
  • See also

Twiddle is an algorithm that tries to find a good choice of parameters $p$ for an algorithm $\mathcal{A}$ that returns an error.

The algorithm is quite simple to implement. I guess gradient descent might be better for most cases, but Twiddle does not require any knowledge about the algorithm $\mathcal{A}$ which might be a big advantage. And you don't have to calculate the gradient of high dimensional functions, which is nice, too.

The algorithm

Here is some pythonic pseudo code. A is an algorithm that returns an error.

# Choose an initialization parameter vector
p = [0, 0, 0]
# Define potential changes
dp = [1, 1, 1]
# Calculate the error
best_err = A(p)

threshold = 0.001

while sum(dp) > threshold:
    for i in range(len(p)):
        p[i] += dp[i]
        err = A(p)

        if err < best_err:  # There was some improvement
            best_err = err
            dp[i] *= 1.1
        else:  # There was no improvement
            p[i] -= 2 * dp[i]  # Go into the other direction
            err = A(p)

            if err < best_err:  # There was an improvement
                best_err = err
                dp[i] *= 1.05
            else:  # There was no improvement
                p[i] += dp[i]
                # As there was no improvement, the step size in either
                # direction, the step size might simply be too big.
                dp[i] *= 0.95

See also

  • Twiddle - CS373 Unit 5 - Udacity: Explanation of Twiddle by Sebastian Thrun
  • Numerische Optimierung in Matlab mit Twiddle-Algorithmus (German)

Published

Sep 6, 2014
by Martin Thoma

Category

Machine Learning

Tags

  • AI 13
  • Machine Learning 81
  • Python 141

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor