Industries

Product

Technology

Team

Careers

Press

Sign In

Try Developer Platform

Using the Signaloid UxHw TTR Bit-Level Distribution Representation for Parametric Distributions

General

General

One of the distribution representations provided by the Signaloid's UxHw technology is the Telescoping Torques Representation (TTR), a weighted mixture of Dirac deltas placed non-uniformly across the support of the distribution. The fidelity of TTR in representing probability distributions can be scaled by changing the number of these Dirac deltas and we refer to their number as the representation size. Similarly, the positions and masses of the Dirac deltas can be represented with fewer or more bits (e.g., 32-bit IEEE-754 float versus 64-bit IEEE-754 double values). The Signaloid UxHw technology uses representations such as TTR for representing both analytic/parametric distributions (e.g., Gaussian, log-normal, etc.) as well as for representing arbitrarily-complex mixtures of parametric distributions and empirical distributions. Because representations such as TTR used by UxHw use a limited number of bits to represent a potentially-real-valued and potentially-continuous probability distributions, they are inherently approximations in the same way that floating-point representations like IEEE-754 are approximations of real numbers. Finding the optimal discrete approximation for a distribution with respect to the Wasserstein metric is a convex optimization problem with an objective function that is expensive to evaluate and has a non-explicit gradient. For such problems, convex optimization algorithms typically do not scale well as the dimension (or in this case the representation size) grows [1]. This poor scaling complicates the use of standard convex optimization algorithms and it forces systems that require discrete representation approximations to continuous distributions to take an alternate route in finding accurate representations. This technology explainer presents a recursive algorithm for finding the discretized approximation to a distribution. The algorithm presented keeps improving the approximation of the continuous probability distribution (in a precise mathematical sense) as the representation size increases.

Figure 1: Graphic illustration of the TTR algorithm applied to the unit Gaussian distribution. The sketch on the left shows how, through three recursion iterations, the TTR algorithm splits the domains across the mean value (i.e., the value that balances the probability torque of that domain). The sketch on the right shows the subsequent placement of Dirac deltas and their associated weights.

Why It Matters

Accurately approximating continuous distributions is indispensable. Any computation on a digital computer involving continuous distributions requires the quantization of the distribution into a discrete approximation. As an example application, a reliability engineer might create a computer simulation model for estimating when a device might fail, and if they are unable to accurately describe the tails of the distribution, they would not be able to use the output of the simulation in applications such as reliability engineering and survival analysis.

The Technical Details

The Challenge

The conventional method to find a discrete representation of a continuous distribution is via the so-called Monte Carlo method. This method works as follows. Given an integer N, the algorithm generates N random samples from the given distribution and then builds an approximation from this sample, typically via the empirical cumulative distribution function (CDF). One of the challenges with this method is that it is random and thus depending on the outcome of the sampling procedure, the Wasserstein-1 distance between the known distribution and the sampled distribution will vary. Another challenge is that the Wasserstein-1 error is (on average) of order O(N^(−1/2)) which is far from the optimal rate of O(N^(−1)) [2, Chapter II]. The recursive algorithm presented in this technology explainer improves this approach by making the error deterministic, performant, and of optimal order O(N^(−1)).

The TTR Algorithm

The Telescoping Torques Representation (TTR) algorithm is a domain-splitting, divide-and-conquer, recursive algorithm that takes a probability distribution and a number n≥0 (which we refer to as the TTR order) as input. The algorithm outputs a discrete probability distribution of 2^n Dirac deltas. Once the domain has been split into smaller subdomains, for a given random variable X with a known distribution, TTR represents the distribution of X in each subdomain Ω by a single Dirac delta that sits at the mean value of X when restricted to Ω and has a mass equal to the total mass of the distribution of X in Ω. The recursive domain splitting follows a simple rule: Split each subdomain obtained at the previous recursion step into two, at the Dirac delta position which TTR uses for that subdomain, i.e., at the mean value of the distribution of X restricted to that subdomain. Figure 1 shows an illustration that depicts the TTR algorithm for three recursion steps and the Code Example shows a naive python implementation of the algorithm. We refer to a TTR by the number of Dirac deltas it has and not the order: The representation in Figure 1 has eight Dirac deltas and we will refer to it using the shorthand "TTR-8".

Obtaining TTRs for Parametric Distributions

There are multiple ways for calculating the TTR of known parametric distributions. Next, we discuss these.

Sample-Based Approaches:

The sample-based approach is simple: It uses a dedicated random number generator (RNG) to collect samples for a given parametric distribution and applies the TTR algorithm to the distribution described by the samples. The downsides of this approach are multiple: It is slow, inaccurate, and the obtained representations show variation due to variation in samples obtained from RNGs.

Analytic Approaches:

Despite their name, analytic approaches still provide a discrete digital TTR representation, but they rely on analytic properties of distributions to achieve their results. Analytic approaches provide the only way to find the exact (up to floating point precision) TTR for a specified parametric distribution. There are four distinct methods to the analytic approach that we list and clarify below. These methods differ in their efficiency and in the types of parametric distributions we can apply them to. We list the methods below in decreasing order of efficiency:

i) Using analytic expressions for TTR Dirac deltas: This method requires the knowledge of the analytic expressions for all the Dirac deltas (i.e., their positions and probability masses) of the TTR. This information is only available for the Uniform distribution, and thus, this method only applies to the uniform distribution.

ii) The "mother TTR" method: This method is applicable to all distributions from the location-scale family of distributions (e.g., the Gaussian, Laplace, Logistic, and Gumbel Type-1 distributions), as well as the scale-only family of distributions (e.g., the Exponential distribution). For these families of distributions, once one knows the TTR for the "mother" distribution (i.e., the unit distribution) for which the scale parameter equals 1 and the location parameter equals 0, one can find the TTR for a distribution with any pair of scale and location parameters by scaling the Dirac delta positions by the scale parameter and translating them by the translation parameter. Thus, to find the TTR for any such distribution one only needs to calculate the TTRs of the mother distribution. The unit Gaussian distribution in Figure 2 is an example of a mother distribution. in We may determine the mother TTR of a distribution using one of the methods described in iii) and iv) below.

iii) Using analytic integration: To apply this method to a given type of parametric distribution, one needs to know the analytic expressions for the CDF given by

and the first moment function (MF) given by

where f is the PDF of the distribution. Once one knows these analytical expressions, a simple recursive algorithm utilizing these expressions suffices to quickly calculate the TTR of a distribution for any set of parameters.

iv) Using numerical integration: This is by far the most expensive method and involves calculating the CDF and MF mentioned in iii) by means of numerical integration. One would only use this method if one wished to obtain an almost exact TTR (limited only by errors induced by numerical integration) for a given distribution and none of the analytical methods above are applicable for the type of parametric distribution of interest.

Figure 2: Plot of the unit Gaussian distribution represented using TTR-256.

Uniform distribution on [0,1] with TTR size 256:
image
Gaussian distribution (mother) with TTR size 256:
image
Laplace distribution (mother) with TTR size 256:
image

Supported Parametric Distributions

Distributions that currently are supported are:

  • Bounded Pareto

  • Exponential Distribution

  • Gaussian Distribution

  • Gumbel-1 Distribution

  • Laplace Distribution

  • Logistic Distribution

  • Log-normal Distribution

  • Uniform Distribution

  • Weibull Distribution

  • Gamma Distribution

  • χ2 Distribution

  • Student's-t Distribution

  • F Distribution

  • Beta Distribution

  • Generalized Extreme Value Distribution

Relevant Code Example
import numpy as np

def ttr_split(positions, masses, n_dirac_deltas, remaining_dirac_deltas, ttr_positions, ttr_masses):

    # Split the array based on their split position
    split_position = np.dot(positions, masses) / np.sum(masses)
    positions_below = positions[positions < split_position]
    positions_above = positions[positions >= split_position]

    # Split masses based on the positions
    split_index = np.searchsorted(positions, split_position)
    masses_below = masses[:split_index]
    masses_above = masses[split_index:]

    remaining_dirac_deltas /= 2

    if remaining_dirac_deltas >= 1:
        ttr_split(positions_below, masses_below, n_dirac_deltas, remaining_dirac_deltas, ttr_positions, ttr_masses)
        ttr_split(positions_above, masses_above, n_dirac_deltas, remaining_dirac_deltas, ttr_positions, ttr_masses)
    else:
        ttr_positions.append(split_position)
        ttr_masses.append(np.sum(masses))
        
    return ttr_positions, ttr_masses
The Takeaway

Obtaining accurate discrete representations of continuous distributions is computationally challenging. This technology explainer highlighted a discrete representation for continuous probability distributions, the telescoping torques representation (TTR). TTR is based on a simple and general algorithm which converges to the true distribution with an optimal rate. When applications require discrete representations of continuous distributions for parametric distributions, the TTR algorithm and related discrete representation can provide representations that are accurate and performant.

References

  1. Sébastien Bubeck (2015), "Convex Optimization: Algorithms and Complexity", Foundations and Trends® in Machine Learning: Vol. 8: No. 3-4, pp 231-357. http://dx.doi.org/10.1561/2200000050

  2. Siegfried Graf and Harald Luschgy, Foundations of Quantization for Probability Distributions.

Schedule a Demo Call

Schedule a Call

Request Whitepaper
Schedule a Demo Call

Schedule a Call

Request Whitepaper
Schedule a Demo Call

Schedule a Call

Request Whitepaper