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