The Twiddle Algorithm

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

Published


by

Category

Machine Learning

Tags

Contact