Repository: facebookresearch/NeuralCompression (language: python)

Issue:
upper_tail op
Approximates upper tail quantile for range coding.

```Python
upper_tail(distribution: torch.distributions.Distribution, tail_mass: float) -> float
```

For range coding of random variables, the distribution tails need special handling, because range coding can only handle alphabets with a finite number of symbols. This method returns a cut-off location for the upper tail, such that approximately `tail_mass` probability mass is contained in the tails (together). The tails are then handled by using the `overflow` functionality of the range coder implementation (using a Golomb-like universal code).

Prerequisites: 

- [x] #77 


Discussion / hints:

Fix patch:
diff --git a/docs/source/functional.rst b/docs/source/functional.rst
index bda7f303..373dcfe9 100644
--- a/docs/source/functional.rst
+++ b/docs/source/functional.rst
@@ -17,3 +17,4 @@ neuralcompression.functional
 .. autofunction:: log_survival_function
 .. autofunction:: log_cdf
 .. autofunction:: lower_bound
+.. autofunction:: upper_bound
diff --git a/neuralcompression/functional/__init__.py b/neuralcompression/functional/__init__.py
index 6b885ef1..1bfd95d1 100644
--- a/neuralcompression/functional/__init__.py
+++ b/neuralcompression/functional/__init__.py
@@ -18,6 +18,7 @@
     soft_round_inverse,
 )
 from ._survival_function import survival_function
+from ._upper_tail import upper_tail
 from .complexity import count_flops
 from .distortion import (
     learned_perceptual_image_patch_similarity,
diff --git a/neuralcompression/functional/_upper_tail.py b/neuralcompression/functional/_upper_tail.py
new file mode 100644
index 00000000..ac0e146a
--- /dev/null
+++ b/neuralcompression/functional/_upper_tail.py
@@ -0,0 +1,53 @@
+"""
+Copyright (c) Facebook, Inc. and its affiliates.
+
+This source code is licensed under the MIT license found in the
+LICENSE file in the root directory of this source tree.
+"""
+
+import math
+
+import torch
+from torch import Tensor
+from torch.distributions import Distribution
+
+from ._estimate_tails import estimate_tails
+from ._log_survival_function import log_survival_function
+
+
+def upper_tail(distribution: Distribution, tail_mass: float) -> Tensor:
+    """Approximates upper tail quantile for range coding.
+
+    For range coding of random variables, the distribution tails need special
+    handling, because range coding can only handle alphabets with a finite
+    number of symbols. This method returns a cut-off location for the upper
+    tail, such that approximately ``tail_mass`` probability mass is contained
+    in the tails (together). The tails are then handled by using the
+    ``overflow`` functionality of the range coder implementation (using a
+    Golomb-like universal code).
+
+    Args:
+        distribution: an object representing a continuous-valued random
+            variable.
+        tail_mass: desired probability mass for the tails.
+
+    Returns:
+        the approximate upper tail quantiles for each scalar distribution.
+    """
+    try:
+        x = distribution.icdf(torch.tensor([1 - tail_mass / 2]))
+    except (AttributeError, NotImplementedError):
+        try:
+            x = estimate_tails(
+                lambda _x: log_survival_function(_x, distribution),
+                math.log(tail_mass / 2),
+                distribution.batch_shape,
+            )
+        except NotImplementedError:
+            error = """
+            `distribution` must implement either `cdf` or `icdf`
+            """
+
+            raise NotImplementedError(error)
+
+    return x.detach()


Test patch:
diff --git a/tests/functional/test_upper_tail.py b/tests/functional/test_upper_tail.py
new file mode 100644
index 00000000..239fdef5
--- /dev/null
+++ b/tests/functional/test_upper_tail.py
@@ -0,0 +1,30 @@
+"""
+Copyright (c) Facebook, Inc. and its affiliates.
+
+This source code is licensed under the MIT license found in the
+LICENSE file in the root directory of this source tree.
+"""
+
+import torch
+import torch.testing
+from torch.distributions import Normal, Uniform
+
+from neuralcompression.functional import upper_tail
+
+
+def test_upper_tail():
+    torch.testing.assert_close(
+        upper_tail(
+            Normal(0.0, 1.0),
+            0.5,
+        ),
+        torch.tensor([0.6745]),
+    )
+
+    torch.testing.assert_close(
+        upper_tail(
+            Uniform(0.0, 1.0),
+            0.5,
+        ),
+        torch.tensor([0.75]),
+    )