<jupyter_start><jupyter_text>Learning from Data of Variable Quality- Authors: <NAME>, <NAME>, <NAME>- This Jupyter Notebook made by <NAME>  Estimating the Bias from Corrupted CoinsWe should know the epsilon lower and upper bounds of each bias, and these should be sorted from smaller (or equal) to bigger.<jupyter_code>from numpy.random import choice

epsilon = numpy.array([0.01, 0.1, 0.4, 0.5])
n_outcomes = numpy.array([50, 100, 500, 600])
# Example from paper
epsilon = numpy.array([0.001, 0.01, 0.02, 0.03, 0.04, 0.2, 0.3, 0.5])
n_outcomes = numpy.array([10, 50, 100, 500, 1500, 2000, 3000, 10000])
bias = numpy.array([0.5 + e*choice([-1,1]) for e in epsilon])
print(bias)
K = len(bias)
samples = [numpy.random.binomial(1, bias[k], n_outcomes[k]) for k in range(K)]

pyplot.hist(samples)
print("Real bias is")
print(bias)
estimated_bias = [numpy.concatenate(samples[:(k+1)]).mean() for k in range(K)]
print("The estimated bias is")
print(estimated_bias)
expected_bias = [numpy.inner(bias[:(k+1)], n_outcomes[:(k+1)])/sum(n_outcomes[:(k+1)]) for k in range(K)]
print("The expected bias is")
print(expected_bias)<jupyter_output>Real bias is
[0.501 0.49  0.52  0.47  0.46  0.7   0.2   0.   ]
The estimated bias is
[0.4, 0.5, 0.58125, 0.4984848484848485, 0.4648148148148148, 0.5762019230769231, 0.4185754189944134, 0.17465034965034965]
The expected bias is
[0.501, 0.4918333333333333, 0.5094375, 0.479560606060606, 0.46597685185185184, 0.5784879807692308, 0.41990363128491626, 0.17520454545454547]<jupyter_text>Real deviation$$ | \beta - \hat\beta_k | $$ Upper bound with triangle inequality and the authors' assumptions$$\begin{align}| \beta - \hat\beta_k | =& | \beta - \bar\beta_k + \bar\beta_k - \hat\beta_k | \\ \le& \sum_{i=1}^k \frac{n_i}{n_{i,k}}\epsilon_i + | \bar\beta_k - \hat\beta_k |\end{align}$$<jupyter_code>real_deviation = [abs(bias[k] - estimated_bias[k]) for k in range(K)]
print('Real deviation')
print(real_deviation)

upper_bound = []
for k in range(K):
    b = 0
    for i in range(k):
        b += (n_outcomes[i]/sum(n_outcomes[:(i+1)]))*epsilon[i]
    b += abs(expected_bias[k] - estimated_bias[k])
    upper_bound.append(b)
    
print('Upper bound of the deviation')
print(upper_bound)
# FIXME Shouldn't the upper bound be always bigger than its corresponding real_deviation?

pyplot.plot(real_deviation, label='Real deviation')
pyplot.plot(upper_bound, label='Upper bound')
pyplot.ylabel('Error')
pyplot.xlabel('Number of piles k')
pyplot.legend()<jupyter_output>Real deviation
[0.10099999999999998, 0.010000000000000009, 0.06125000000000003, 0.028484848484848502, 0.004814814814814772, 0.12379807692307687, 0.2185754189944134, 0.17465034965034965]
Upper bound of the deviation
[0.10099999999999998, 0.009166666666666712, 0.08114583333333339, 0.040757575757575784, 0.04572264309764311, 0.07462444153069156, 0.16982044228273285, 0.2947447498187722]<jupyter_text>FIXME The upper bound should be always bigger, but it is not the case here  Bounding the second term with Hoeffding inequalityWith high probability and an appropiate choice of $\delta$$$| \beta - \hat\beta_k | \le \sum_{i=1}^k \frac{n_i}{n_{i,k}}\epsilon_i + \sqrt{\frac{\log(2K/\delta)}{2n_{1,k}}}$$<jupyter_code>from numpy import sqrt, log

delta = 0.001
print('Previous upperbound')
print(upper_bound)
estimated_deviation = []
for k in range(K):
    b = 0
    for i in range(k):
        b += (n_outcomes[i]/sum(n_outcomes[:(i+1)]))*epsilon[i]
    b += sqrt(log(2.0*K/delta)/(2*sum(n_outcomes[:(k+1)])))
    estimated_deviation.append(b)
    
print('Upperbound with delta probability')
print(estimated_deviation)

pyplot.plot(real_deviation, label='Real deviation')
pyplot.plot(upper_bound, label='Upper bound')
pyplot.plot(estimated_deviation, label='Estimated deviation')
pyplot.ylabel('Error')
pyplot.xlabel('Number of piles k')
pyplot.legend()<jupyter_output>Previous upperbound
[0.10099999999999998, 0.009166666666666712, 0.08114583333333339, 0.040757575757575784, 0.04572264309764311, 0.07462444153069156, 0.16982044228273285, 0.2947447498187722]
Upperbound with delta probability
[0.6957134468019832, 0.28502382530963133, 0.18326169503382914, 0.10746973879456012, 0.09189791027887795, 0.10644854192600123, 0.19449226222419047, 0.3109852348807587]<jupyter_text>FIXME the papers' example do not show the delta value Optimal number of piles$$k^* = \underset{k \in \{1, \dots, K\}}{\operatorname{argmin}} \left\{ \sum_{i=1}^k \frac{n_i}{n_{i,k}}\epsilon_i + \sqrt{\frac{\log(2K/\delta)}{2n_{1,k}}} \right\}$$<jupyter_code>k_star = numpy.argmin(estimated_deviation)
print('Optimum number of piles K* = {}'.format(k_star+1))<jupyter_output>Optimum number of piles K* = 5
{'fraction_non_alphanumeric': 0.15079365079365079, 'fraction_numerical': 0.19583869583869584, 'mean_word_length': 5.719020172910663, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 10, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '632080', 'license': 'MIT', 'n_tokens_mistral': 2394, 'n_tokens_neox': 1810, 'n_words': 396, 'path': 'notebooks/learning_data_variable_quality.ipynb', 'repo_name': 'perellonieto/RecyclingLabels', 'size': '4700'}