[Optimization] NormalIntegerHyperparameter `get_max_density` and `_compute_normalization`

[eddiebergman]

Reference PR #282

Both _compute_normalization and get_max_density will compute the pdf over the entire integer range of NormalIntegerHyperparameter and BetaIntegerHyperparameter. This is usually fine unless the ranges get massive, i.e. the entire int32 range.

Originally this destroyed memory and was quite slow but PR #282 changed this to operate on chunks of the range at a time, allowing memory to stay constant. However these computations still need to happen.

I'm not sure of an accurate fix to this problem.

import ConfigSpace.hyperparameters as CSH

# This will hang for incredibly long 
CSH.NormalIntegerHyperparameter('a', mu=10, sigma=500, lower=1, upper=2147483647)

[herilalaina]

To reduce the runtime, one solution is to limit the range of values considered. A possible approach would be to consider the confidence interval of the normalized distribution, which implicitly discards values outside this interval because their density would be negligible (~10^-277). I tested the idea on truncnorm, the backend of NormalIntegerHyperparameter for density computation, to compute the sum of densities as in _compute_normalization .

import time
from ConfigSpace.functional import arange_chunked

from scipy.stats import truncnorm

ARANGE_CHUNKSIZE = 10_000_000
lower = 1
upper = 2147483647
mu = 10
sigma = 500


def original():
    st = time.time()
    chunks = arange_chunked(lower, upper + 1, chunk_size=ARANGE_CHUNKSIZE)
    a = (lower - mu) / sigma
    b = (upper - mu) / sigma

    S = sum([truncnorm(a=a, b=b).pdf(chunk).sum() for chunk in chunks])
    return time.time() - st, S


def proposed():
    st = time.time()
    a = (lower - mu) / sigma
    b = (upper - mu) / sigma
    rv = truncnorm(a=a, b=b)
    u, v = rv.interval(confidence=0.9999999999999)
    chunks = arange_chunked(
        max(u, lower), min(v, upper + 1), chunk_size=ARANGE_CHUNKSIZE
    )

    S = sum([rv.pdf(chunk).sum() for chunk in chunks])
    return time.time() - st, S


print("Original: Runtime={} Sum={}".format(*original()))
print("Proposed: Runtime={} Sum={}".format(*proposed()))

Output:

Original: Runtime=13.534979104995728 Sum=0.5925480554639843
Proposed: Runtime=0.0007011890411376953 Sum=0.5925480554639743

For this example, both functions produce identical results, but the proposed one is considerably faster. Extensive test cases and benchmarking are still needed, though. What do you think ? @eddiebergman @mfeurer

[eddiebergman]

Wow, this is a great optimization! Very much on board for this!

[mfeurer]

I agree, this looks very promising and you should pursue this further.

[eddiebergman]

I think this can be closed, there was a PR that closed this before and it's present in 1.0.0, thanks for the great find @herilalaina!