forked from momo1106github/CNS_Final_Project
-
Notifications
You must be signed in to change notification settings - Fork 0
/
OUE.py
105 lines (78 loc) · 2.88 KB
/
OUE.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import random
from math import exp
class OUE():
"""
This class implement some methods for OUE.
"""
def __init__(self, d=10, epsilon=1.09):
"""
The constructor for OUE class.
Attributes:
d (int): How many category that want to be generated.
epsilon (double): Epsilon used to calculate probability q.
"""
self.d = d
self.epsilon = epsilon
self.p = 0.5
self.q = 1 / (exp(epsilon) + 1)
def encode(self, item):
"""
The function to encode items that want to be promoted.
Parameters:
item (int): Item that want to be promoted.
Returns:
Encoded items (list of int)
"""
encoded_item = [0] * self.d
encoded_item[item] = 1
return encoded_item
def perturb(self, encoded_item):
"""
The function to perturb encoded items.
For each bit of the encoded binary vector, if it is 1, then it remains 1 with a probability p.
Otherwise if the bit is 0, it is flipped to 1 with a probability q.
Parameters:
encoded_item (list of int): Encoded items that are going to be perturbed.
Returns:
Perturbed items (list of int)
"""
assert(self.d == len(encoded_item))
indices = [1, 0]
perturbed_item = list(encoded_item)
for i in range(len(perturbed_item)):
if perturbed_item[i] == 1:
perturbed_item[i] = random.choices(indices, weights = [self.p, 1 - self.p], k = 1)[0]
elif perturbed_item[i] == 0:
perturbed_item[i] = random.choices(indices, weights = [self.q, 1 - self.q], k = 1)[0]
else:
assert(False)
return perturbed_item
def aggregate(self, perturbed_items):
"""
The function to aggregate items.
Parameters:
perturbed_items (list of int): Perturbed items that are going to be check.
"""
n = len(perturbed_items)
estimated_f = []
for v in range(self.d):
p_ = 0
for i in range(n):
if perturbed_items[i] == v:
p_ += 1
p_ /= n
estimated_f.append((p_ - self.q) / (self.p - self.q))
return estimated_f
# if __name__ == "__main__":
# d = 10 # There are 10 category, including item0, item1, ..., item9
# item = 1 # Want to promote item1
# frequency = [0] * d # Frenquency of each item
# n = 100
# for i in range(n):
# OUE_instance = OUE(d)
# encoded_item = OUE_instance.encode(item)
# perturbed_item = OUE_instance.perturb(encoded_item)
# print (perturbed_item)
# for item_index in range(d):
# frequency[item_index] = ((frequency_estimator[item_index] / n) - q) / (p - q)
# print(frequency_estimator)