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:
6 # http://www.apache.org/licenses/LICENSE-2.0
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.
14 """Module holding BitCountingMetadata class."""
18 from AvgStdevMetadata import AvgStdevMetadata
21 class BitCountingMetadata(AvgStdevMetadata):
22 """Class for metadata which includes information content of a group.
24 The information content is based on an assumption
25 that the data consists of independent random values
26 from a normal distribution.
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.
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.
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
55 :type prev_avg: float or None
57 super(BitCountingMetadata, self).__init__(size, avg, stdev)
58 self.max_value = max_value
59 self.prev_avg = prev_avg
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)
67 self.bits += math.log(size * (size + 1), 2)
69 # Avg is considered to be uniformly distributed
70 # from zero to max_value.
71 self.bits += math.log(max_value + 1.0, 2)
73 # Opposite triangle distribution with minimum.
74 self.bits += math.log(
75 max_value * (max_value + 1) / (abs(avg - prev_avg) + 1), 2)
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)
92 """Return string with human readable description of the group.
94 :returns: Readable description.
97 return "size={size} avg={avg} stdev={stdev} bits={bits}".format(
98 size=self.size, avg=self.avg, stdev=self.stdev, bits=self.bits)
101 """Return string executable as Python constructor call.
103 :returns: Executable constructor call.
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)