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.
16 from AvgStdevMetadata import AvgStdevMetadata
19 class BitCountingMetadata(AvgStdevMetadata):
20 """Class for metadata which includes information content."""
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.
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.
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
48 :type prev_avg: float or None
50 super(BitCountingMetadata, self).__init__(size, avg, stdev)
51 self.max_value = max_value
52 self.prev_avg = prev_avg
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)
60 self.bits += math.log(size * (size + 1), 2)
62 # Avg is considered to be uniformly distributed
63 # from zero to max_value.
64 self.bits += math.log(max_value + 1.0, 2)
66 # Opposite triangle distribution with minimum.
67 self.bits += math.log(
68 max_value * (max_value + 1) / (abs(avg - prev_avg) + 1), 2)
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)
85 """Return string with human readable description of the group.
87 :returns: Readable description.
90 return "size={size} avg={avg} stdev={stdev} bits={bits}".format(
91 size=self.size, avg=self.avg, stdev=self.stdev, bits=self.bits)
94 """Return string executable as Python constructor call.
96 :returns: Executable constructor call.
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)