Documentation

Documentation

Functions

KullbackLeibler.klBern — Method.
function klBern(x, y)

Kullback-Leibler divergence for Bernoulli distributions. https://en.wikipedia.org/wiki/Bernoulli_distribution#Kullback.E2.80.93Leibler_divergence

\[\mathrm{KL}(\mathcal{B}(x), \mathcal{B}(y)) = x \log(\frac{x}{y}) + (1-x) \log(\frac{1-x}{1-y}).\]
    julia> klBern(0.5, 0.5)
    0.0
    julia> klBern(0.1, 0.9)
    1.757779...
    julia> klBern(0.9, 0.1)  # And this KL is symmetric
    1.757779...
    julia> klBern(0.4, 0.5)
    0.020135...
    julia> klBern(0.01, 0.99)
    4.503217...

  • Special values:

    julia> klBern(0, 1)  # Should be +Inf, but 0 --> eps, 1 --> 1 - eps
    34.539575...
source
KullbackLeibler.klBin — Method.
function klBin(x, y, n)

Kullback-Leibler divergence for Binomial distributions. https://math.stackexchange.com/questions/320399/kullback-leibner-divergence-of-binomial-distributions

  • It is simply the n times klBern on x and y.

\[\mathrm{KL}(\mathrm{Bin}(x, n), \mathrm{Bin}(y, n)) = n \times \left(x \log(\frac{x}{y}) + (1-x) \log(\frac{1-x}{1-y}) \right).\]

  • Warning: The two distributions must have the same parameter n, and x, y are p, q in (0, 1).

    julia> klBin(0.5, 0.5, 10)
    0.0
    julia> klBin(0.1, 0.9, 10)
    17.57779...
    julia> klBin(0.9, 0.1, 10)  # And this KL is symmetric
    17.57779...
    julia> klBin(0.4, 0.5, 10)
    0.20135...
    julia> klBin(0.01, 0.99, 10)
    45.03217...

  • Special values:

    julia> klBin(0, 1, 10)  # Should be +Inf, but 0 --> eps, 1 --> 1 - eps
    345.39575...
source
KullbackLeibler.klPoisson — Method.
function klPoisson(x, y)

Kullback-Leibler divergence for Poison distributions. https://en.wikipedia.org/wiki/Poisson_distribution#Kullback.E2.80.93Leibler_divergence

\[\mathrm{KL}(\mathrm{Poisson}(x), \mathrm{Poisson}(y)) = y - x + x \times \log(\frac{x}{y}).\]
    julia> klPoisson(3, 3)
    0.0
    julia> klPoisson(2, 1)
    0.386294...
    julia> klPoisson(1, 2)  # And this KL is non-symmetric
    0.306852...
    julia> klPoisson(3, 6)
    0.920558...
    julia> klPoisson(6, 8)
    0.273907...

  • Special values:

    julia> klPoisson(1, 0)  # Should be +Inf, but 0 --> eps, 1 --> 1 - eps
    33.538776...
    julia> klPoisson(0, 0)
    0.0
source
KullbackLeibler.klExp — Method.
function klExp(x, y)

Kullback-Leibler divergence for exponential distributions. https://en.wikipedia.org/wiki/Exponential_distribution#Kullback.E2.80.93Leibler_divergence

.. math::

\mathrm{KL}(\mathrm{Exp}(x), \mathrm{Exp}(y)) = \begin{cases}
\frac{x}{y} - 1 - \log(\frac{x}{y}) & \text{if} x > 0, y > 0\\
+\infty & \text{otherwise}
\end{cases}
    julia> klExp(3, 3)
    0.0
    julia> klExp(3, 6)
    0.193147...
    julia> klExp(1, 2)  # Only the proportion between x and y is used
    0.193147...
    julia> klExp(2, 1)  # And this KL is non-symmetric
    0.306852...
    julia> klExp(4, 2)  # Only the proportion between x and y is used
    0.306852...
    julia> klExp(6, 8)
    0.037682...

  • x, y have to be positive:

    julia> klExp(-3, 2)
    Inf
    julia> klExp(3, -2)
    Inf
    julia> klExp(-3, -2)
    Inf
source
KullbackLeibler.klGamma — Method.
function klGamma(x, y, a=1)

Kullback-Leibler divergence for gamma distributions. https://en.wikipedia.org/wiki/Gamma_distribution#Kullback.E2.80.93Leibler_divergence

  • It is simply the a times klExp on x and y.

.. math::

\mathrm{KL}(\Gamma(x, a), \Gamma(y, a)) = \begin{cases}
a \times \left( \frac{x}{y} - 1 - \log(\frac{x}{y}) \right) & \text{if} x > 0, y > 0\\
+\infty & \text{otherwise}
\end{cases}

  • Warning: The two distributions must have the same parameter a.

    julia> klGamma(3, 3)
    0.0
    julia> klGamma(3, 6)
    0.193147...
    julia> klGamma(1, 2)  # Only the proportion between x and y is used
    0.193147...
    julia> klGamma(2, 1)  # And this KL is non-symmetric
    0.306852...
    julia> klGamma(4, 2)  # Only the proportion between x and y is used
    0.306852...
    julia> klGamma(6, 8)
    0.037682...

  • x, y have to be positive:

    julia> klGamma(-3, 2)
    Inf
    julia> klGamma(3, -2)
    Inf
    julia> klGamma(-3, -2)
    Inf
source
KullbackLeibler.klNegBin — Method.
function klNegBin(x, y, r=1)

Kullback-Leibler divergence for negative binomial distributions. https://en.wikipedia.org/wiki/Negative_binomial_distribution

\[\mathrm{KL}(\mathrm{NegBin}(x, r), \mathrm{NegBin}(y, r)) = r \times \log((r + x) / (r + y)) - x \times \log(y \times (r + x) / (x \times (r + y))).\]

  • Warning: The two distributions must have the same parameter r.

    julia> klNegBin(0.5, 0.5)
    0.0
    julia> klNegBin(0.1, 0.9)
    -0.711611...
    julia> klNegBin(0.9, 0.1)  # And this KL is non-symmetric
    2.0321564...
    julia> klNegBin(0.4, 0.5)
    -0.130653...
    julia> klNegBin(0.01, 0.99)
    -0.717353...

  • Special values:

    julia> klBern(0, 1)  # Should be +Inf, but 0 --> eps, 1 --> 1 - eps
    34.539575...

  • With other values for r:

    julia> klNegBin(0.5, 0.5, r=2)
    0.0
    julia> klNegBin(0.1, 0.9, r=2)
    -0.832991...
    julia> klNegBin(0.1, 0.9, r=4)
    -0.914890...
    julia> klNegBin(0.9, 0.1, r=2)  # And this KL is non-symmetric
    2.3325528...
    julia> klNegBin(0.4, 0.5, r=2)
    -0.154572...
    julia> klNegBin(0.01, 0.99, r=2)
    -0.836257...
source
KullbackLeibler.klGauss — Method.
function klGauss(x, y, sig2x=0.25, sig2y=0.25)

Kullback-Leibler divergence for Gaussian distributions of means $x$ and $y$ and variances $sig2x$ and $sig2y$, $\nu_1 = \mathcal{N}(x, \sigma_x^2)$ and $\nu_2 = \mathcal{N}(y, \sigma_x^2)$:

\[\mathrm{KL}(\nu_1, \nu_2) = \frac{(x - y)^2}{2 \sigma_y^2} + \frac{1}{2}\left( \frac{\sigma_x^2}{\sigma_y^2} - 1 \log\left(\frac{\sigma_x^2}{\sigma_y^2}\right) \right).\]

See https://en.wikipedia.org/wiki/Normal_distribution#Other_properties

  • By default, sig2y is assumed to be sig2x (same variance).

    julia> klGauss(3, 3)
    0.0
    julia> klGauss(3, 6)
    18.0
    julia> klGauss(1, 2)
    2.0
    julia> klGauss(2, 1)  # And this KL is symmetric
    2.0
    julia> klGauss(4, 2)
    8.0
    julia> klGauss(6, 8)
    8.0

  • x, y can be negative:

    julia> klGauss(-3, 2)
    50.0
    julia> klGauss(3, -2)
    50.0
    julia> klGauss(-3, -2)
    2.0
    julia> klGauss(3, 2)
    2.0

  • With other values for sig2x:

    julia> klGauss(3, 3, sig2x=10)
    0.0
    julia> klGauss(3, 6, sig2x=10)
    0.45
    julia> klGauss(1, 2, sig2x=10)
    0.05
    julia> klGauss(2, 1, sig2x=10)  # And this KL is symmetric
    0.05
    julia> klGauss(4, 2, sig2x=10)
    0.2
    julia> klGauss(6, 8, sig2x=10)
    0.2

  • With different values for sig2x and sig2y:

    julia> klGauss(0, 0, sig2x=0.25, sig2y=0.5)
    -0.0284...
    julia> klGauss(0, 0, sig2x=0.25, sig2y=1.0)
    0.2243...
    julia> klGauss(0, 0, sig2x=0.5, sig2y=0.25)  # not symmetric here!
    1.1534...

    julia> klGauss(0, 1, sig2x=0.25, sig2y=0.5)
    0.9715...
    julia> klGauss(0, 1, sig2x=0.25, sig2y=1.0)
    0.7243...
    julia> klGauss(0, 1, sig2x=0.5, sig2y=0.25)  # not symmetric here!
    3.1534...

    julia> klGauss(1, 0, sig2x=0.25, sig2y=0.5)
    0.9715...
    julia> klGauss(1, 0, sig2x=0.25, sig2y=1.0)
    0.7243...
    julia> klGauss(1, 0, sig2x=0.5, sig2y=0.25)  # not symmetric here!
    3.1534...

  • Warning: Using :class:Policies.klUCB (and variants) with klGauss is equivalent to use :class:Policies.UCB, so prefer the simpler version.

source
KullbackLeibler.klucb — Method.
function klucb(x, d, kl, upperbound, lowerbound=-Inf, precision=1e-6, max_iterations=50)

The generic KL-UCB index computation.

  • x: value of the cum reward,

  • d: upper bound on the divergence,

  • kl: the KL divergence to be used (klBern, klGauss, etc),

  • upperbound, lowerbound=-Inf: the known bound of the values x,

  • precision=1e-6: the threshold from where to stop the research,

  • max_iterations: max number of iterations of the loop (safer to bound it to reduce time complexity).

  • Note: It uses a bisection search, and one call to $kl$ for each step of the bisection search.

For example, for klucbBern, the two steps are to first compute an upperbound (as precise as possible) and the compute the kl-UCB index:

    julia> x, d = 0.9, 0.2   # mean x, exploration term d
    julia> upperbound = min(1.0, klucbGauss(x, d, sig2x=0.25))  # variance 1/4 for [0,1] bounded distributions
    julia> upperbound
    1.0
    julia> klucb(x, d, klBern, upperbound, lowerbound=0, precision=1e-3, max_iterations=10)
    0.9941...
    julia> klucb(x, d, klBern, upperbound, lowerbound=0, precision=1e-6, max_iterations=10)
    0.994482...
    julia> klucb(x, d, klBern, upperbound, lowerbound=0, precision=1e-3, max_iterations=50)
    0.9941...
    julia> klucb(x, d, klBern, upperbound, lowerbound=0, precision=1e-6, max_iterations=100)  # more and more precise!
    0.994489...

  • Note: See below for more examples for different KL divergence functions.

source
KullbackLeibler.klucbBern — Method.
function klucbBern(x, d, precision=1e-6)

KL-UCB index computation for Bernoulli distributions, using klucb.

  • Influence of x:

    julia> klucbBern(0.1, 0.2)
    0.378391...
    julia> klucbBern(0.5, 0.2)
    0.787088...
    julia> klucbBern(0.9, 0.2)
    0.994489...

  • Influence of d:

    julia> klucbBern(0.1, 0.4)
    0.519475...
    julia> klucbBern(0.1, 0.9)
    0.734714...

    julia> klucbBern(0.5, 0.4)
    0.871035...
    julia> klucbBern(0.5, 0.9)
    0.956809...

    julia> klucbBern(0.9, 0.4)
    0.999285...
    julia> klucbBern(0.9, 0.9)
    0.999995...
source
KullbackLeibler.klucbGauss — Method.
function klucbGauss(x, d, sig2x=0.25, precision=0.0)

KL-UCB index computation for Gaussian distributions.

  • Note: it does not require any search.

  • Warning: it works only if the good variance constant is given.

  • Influence of x:

    julia> klucbGauss(0.1, 0.2)
    0.416227...
    julia> klucbGauss(0.5, 0.2)
    0.816227...
    julia> klucbGauss(0.9, 0.2)
    1.216227...

- Influence of d:

julia julia> klucbGauss(0.1, 0.4) 0.547213... julia> klucbGauss(0.1, 0.9) 0.770820...

julia> klucbGauss(0.5, 0.4)
0.947213...
julia> klucbGauss(0.5, 0.9)
1.170820...

julia> klucbGauss(0.9, 0.4)
1.347213...
julia> klucbGauss(0.9, 0.9)
1.570820...

```

  • Warning: Using :class:Policies.klUCB (and variants) with klucbGauss is equivalent to use :class:Policies.UCB, so prefer the simpler version.

source
KullbackLeibler.klucbPoisson — Method.
function klucbPoisson(x, d, precision=1e-6)

KL-UCB index computation for Poisson distributions, using klucb.

  • Influence of x:

    julia> klucbPoisson(0.1, 0.2)
    0.450523...
    julia> klucbPoisson(0.5, 0.2)
    1.089376...
    julia> klucbPoisson(0.9, 0.2)
    1.640112...

  • Influence of d:

    julia> klucbPoisson(0.1, 0.4)
    0.693684...
    julia> klucbPoisson(0.1, 0.9)
    1.252796...

    julia> klucbPoisson(0.5, 0.4)
    1.422933...
    julia> klucbPoisson(0.5, 0.9)
    2.122985...

    julia> klucbPoisson(0.9, 0.4)
    2.033691...
    julia> klucbPoisson(0.9, 0.9)
    2.831573...
source
KullbackLeibler.klucbExp — Method.
function klucbExp(x, d, precision=1e-6)

KL-UCB index computation for exponential distributions, using klucb.

  • Influence of x:

    julia> klucbExp(0.1, 0.2)
    0.202741...
    julia> klucbExp(0.5, 0.2)
    1.013706...
    julia> klucbExp(0.9, 0.2)
    1.824671...

  • Influence of d:

    julia> klucbExp(0.1, 0.4)
    0.285792...
    julia> klucbExp(0.1, 0.9)
    0.559088...

    julia> klucbExp(0.5, 0.4)
    1.428962...
    julia> klucbExp(0.5, 0.9)
    2.795442...

    julia> klucbExp(0.9, 0.4)
    2.572132...
    julia> klucbExp(0.9, 0.9)
    5.031795...
source
KullbackLeibler.klucbGamma — Method.
function klucbGamma(x, d, precision=1e-6)

KL-UCB index computation for Gamma distributions, using klucb.

  • Influence of x:

    julia> klucbGamma(0.1, 0.2)
    0.202...
    julia> klucbGamma(0.5, 0.2)
    1.013...
    julia> klucbGamma(0.9, 0.2)
    1.824...

  • Influence of d:

    julia> klucbGamma(0.1, 0.4)
    0.285...
    julia> klucbGamma(0.1, 0.9)
    0.559...

    julia> klucbGamma(0.5, 0.4)
    1.428...
    julia> klucbGamma(0.5, 0.9)
    2.795...

    julia> klucbGamma(0.9, 0.4)
    2.572...
    julia> klucbGamma(0.9, 0.9)
    5.031...
source

Index