resources/tools/presentation/new/jumpavg/BitCountingMetadata.py

   1 # Copyright (c) 2018 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 BitCountingMetadata class."""
  15
  16 import math
  17
  18 from AvgStdevMetadata import AvgStdevMetadata
  19
  20
  21 class BitCountingMetadata(AvgStdevMetadata):
  22     """Class for metadata which includes information content of a group.
  23
  24     The information content is based on an assumption
  25     that the data consists of independent random values
  26     from a normal distribution.
  27     """
  28
  29     def __init__(self, max_value, size=0, avg=0.0, stdev=0.0, prev_avg=None):
  30         """Construct the metadata by computing from the values needed.
  31
  32         The bit count is not real, as that would depend on numeric precision
  33         (number of significant bits in values).
  34         The difference is assumed to be constant per value,
  35         which is consistent with Gauss distribution
  36         (but not with floating point mechanic).
  37         The hope is the difference will have
  38         no real impact on the classification procedure.
  39
  40         :param max_value: Maximal expected value.
  41             TODO: This might be more optimal,
  42             but max-invariant algorithm will be nicer.
  43         :param size: Number of values participating in this group.
  44         :param avg: Population average of the participating sample values.
  45         :param stdev: Population standard deviation of the sample values.
  46         :param prev_avg: Population average of the previous group.
  47             If None, no previous average is taken into account.
  48             If not None, the given previous average is used to discourage
  49             consecutive groups with similar averages
  50             (opposite triangle distribution is assumed).
  51         :type max_value: float
  52         :type size: int
  53         :type avg: float
  54         :type stdev: float
  55         :type prev_avg: float or None
  56         """
  57         super(BitCountingMetadata, self).__init__(size, avg, stdev)
  58         self.max_value = max_value
  59         self.prev_avg = prev_avg
  60         self.bits = 0.0
  61         if self.size < 1:
  62             return
  63         # Length of the sequence must be also counted in bits,
  64         # otherwise the message would not be decodable.
  65         # Model: probability of k samples is 1/k - 1/(k+1)
  66         # == 1/k/(k+1)
  67         self.bits += math.log(size * (size + 1), 2)
  68         if prev_avg is None:
  69             # Avg is considered to be uniformly distributed
  70             # from zero to max_value.
  71             self.bits += math.log(max_value + 1.0, 2)
  72         else:
  73             # Opposite triangle distribution with minimum.
  74             self.bits += math.log(
  75                 max_value * (max_value + 1) / (abs(avg - prev_avg) + 1), 2)
  76         if self.size < 2:
  77             return
  78         # Stdev is considered to be uniformly distributed
  79         # from zero to max_value. That is quite a bad expectation,
  80         # but resilient to negative samples etc.
  81         self.bits += math.log(max_value + 1.0, 2)
  82         # Now we know the samples lie on sphere in size-1 dimensions.
  83         # So it is (size-2)-sphere, with radius^2 == stdev^2 * size.
  84         # https://en.wikipedia.org/wiki/N-sphere
  85         sphere_area_ln = math.log(2) + math.log(math.pi) * ((size - 1) / 2.0)
  86         sphere_area_ln -= math.lgamma((size - 1) / 2.0)
  87         sphere_area_ln += math.log(stdev + 1.0) * (size - 2)
  88         sphere_area_ln += math.log(size) * ((size - 2) / 2.0)
  89         self.bits += sphere_area_ln / math.log(2)
  90
  91     def __str__(self):
  92         """Return string with human readable description of the group.
  93
  94         :returns: Readable description.
  95         :rtype: str
  96         """
  97         return "size={size} avg={avg} stdev={stdev} bits={bits}".format(
  98             size=self.size, avg=self.avg, stdev=self.stdev, bits=self.bits)
  99
 100     def __repr__(self):
 101         """Return string executable as Python constructor call.
 102
 103         :returns: Executable constructor call.
 104         :rtype: str
 105         """
 106         return ("BitCountingMetadata(max_value={max_value},size={size}," +
 107                 "avg={avg},stdev={stdev},prev_avg={prev_avg})").format(
 108                     max_value=self.max_value, size=self.size, avg=self.avg,
 109                     stdev=self.stdev, prev_avg=self.prev_avg)