resources/libraries/python/jumpavg/BitCountingStats.py

   1 # Copyright (c) 2022 Cisco and/or its affiliates.
   2 # Licensed under the Apache License, Version 2.0 (the "License");
   3 # you may not use this file except in compliance with the License.
   4 # You may obtain a copy of the License at:
   5 #
   6 #     http://www.apache.org/licenses/LICENSE-2.0
   7 #
   8 # Unless required by applicable law or agreed to in writing, software
   9 # distributed under the License is distributed on an "AS IS" BASIS,
  10 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  11 # See the License for the specific language governing permissions and
  12 # limitations under the License.
  13
  14 """Module holding BitCountingStats class."""
  15
  16 import dataclasses
  17 import math
  18 import typing
  19
  20 from .AvgStdevStats import AvgStdevStats
  21
  22
  23 @dataclasses.dataclass
  24 class BitCountingStats(AvgStdevStats):
  25     """Class for statistics which include information content of a group.
  26
  27     The information content is based on an assumption that the data
  28     consists of independent random values from a normal distribution.
  29
  30     Instances are only statistics, the data itself is stored elsewhere.
  31
  32     The coding needs to know the previous average, and a maximal value
  33     so both values are required as inputs.
  34
  35     This is a subclass of AvgStdevStats, even though all methods are overriden.
  36     Only for_runs method calls the parent implementation, without using super().
  37     """
  38
  39     max_value: float = None
  40     """Maximal sample value (real or estimated).
  41     Default value is there just for argument ordering reasons,
  42     leaving None leads to exceptions."""
  43     prev_avg: typing.Optional[float] = None
  44     """Population average of the previous group (if any)."""
  45     bits: float = None
  46     """The computed information content of the group.
  47     It is formally an argument to init function, just to keep repr string
  48     a valid call. ut the init value is ignored and always recomputed.
  49     """
  50
  51     def __post_init__(self):
  52         """Construct the stats object by computing from the values needed.
  53
  54         The None values are allowed for stats for zero size data,
  55         but such stats can report arbitrary avg and max_value.
  56         Stats for nonzero size data cannot contain None,
  57         else ValueError is raised.
  58
  59         The max_value needs to be numeric for nonzero size,
  60         but its relations to avg and prev_avg are not examined.
  61
  62         The bit count is not real, as that would depend on numeric precision
  63         (number of significant bits in values).
  64         The difference is assumed to be constant per value,
  65         which is consistent with Gauss distribution
  66         (but not with floating point mechanic).
  67         The hope is the difference will have
  68         no real impact on the classification procedure.
  69         """
  70         # Zero size should in principle have non-zero bits (coding zero size),
  71         # but zero allows users to add empty groups without affecting bits.
  72         self.bits = 0.0
  73         if self.size < 1:
  74             return
  75         if self.max_value <= 0.0:
  76             raise ValueError(f"Invalid max value: {self!r}")
  77         # Length of the sequence must be also counted in bits,
  78         # otherwise the message would not be decodable.
  79         # Model: probability of k samples is 1/k - 1/(k+1) == 1/k/(k+1)
  80         # This is compatible with zero size leading to zero bits.
  81         self.bits += math.log(self.size * (self.size + 1), 2)
  82         if self.prev_avg is None:
  83             # Avg is considered to be uniformly distributed
  84             # from zero to max_value.
  85             self.bits += math.log(self.max_value + 1.0, 2)
  86         else:
  87             # Opposite triangle distribution with minimum.
  88             self.bits += math.log(
  89                 (self.max_value * (self.max_value + 1))
  90                 / (abs(self.avg - self.prev_avg) + 1),
  91                 2,
  92             )
  93         if self.size < 2:
  94             return
  95         # Stdev is considered to be uniformly distributed
  96         # from zero to max_value. That is quite a bad expectation,
  97         # but resilient to negative samples etc.
  98         self.bits += math.log(self.max_value + 1.0, 2)
  99         # Now we know the samples lie on sphere in size-1 dimensions.
 100         # So it is (size-2)-sphere, with radius^2 == stdev^2 * size.
 101         # https://en.wikipedia.org/wiki/N-sphere
 102         sphere_area_ln = math.log(2)
 103         sphere_area_ln += math.log(math.pi) * ((self.size - 1) / 2.0)
 104         sphere_area_ln -= math.lgamma((self.size - 1) / 2.0)
 105         sphere_area_ln += math.log(self.stdev + 1.0) * (self.size - 2)
 106         sphere_area_ln += math.log(self.size) * ((self.size - 2) / 2.0)
 107         self.bits += sphere_area_ln / math.log(2)
 108
 109     # TODO: Rename, so pylint stops complaining about signature change.
 110     @classmethod
 111     def for_runs(
 112         cls,
 113         runs: typing.Iterable[typing.Union[float, AvgStdevStats]],
 114         max_value: float,
 115         prev_avg: typing.Optional[float] = None,
 116     ):
 117         """Return new stats instance describing the sequence of runs.
 118
 119         If you want to append data to existing stats object,
 120         you can simply use the stats object as the first run.
 121
 122         Instead of a verb, "for" is used to start this method name,
 123         to signify the result contains less information than the input data.
 124
 125         The two optional values can come from outside of the runs provided.
 126
 127         The max_value cannot be None for non-zero size data.
 128         The implementation does not check if no datapoint exceeds max_value.
 129
 130         TODO: Document the behavior for zero size result.
 131
 132         :param runs: Sequence of data to describe by the new metadata.
 133         :param max_value: Maximal expected value.
 134         :param prev_avg: Population average of the previous group, if any.
 135         :type runs: Iterable[Union[float, AvgStdevStats]]
 136         :type max_value: Union[float, NoneType]
 137         :type prev_avg: Union[float, NoneType]
 138         :returns: The new stats instance.
 139         :rtype: cls
 140         """
 141         asd = AvgStdevStats.for_runs(runs)
 142         ret_obj = cls(
 143             size=asd.size,
 144             avg=asd.avg,
 145             stdev=asd.stdev,
 146             max_value=max_value,
 147             prev_avg=prev_avg,
 148         )
 149         return ret_obj