Notebook

Hoeffding Inequality¶

Run a computer simulation for flipping 1,000 virtual fair coins. Flip each coin independently 10 times. Focus on 3 coins as follows:

$c_1$ is the first coin flipped,
$c_{rand}$ is a coin chosen randomly from the 1,000,
$c_{min}$ is the coin which had the minimum frequency of heads (pick the earlier one in case of a tie).

Let $\nu_1$ , $\nu_{rand}$ , and $\nu_{min}$ be the fraction of heads obtained for the 3 respective coins out of the 10 tosses. Run the experiment 100,000 times in order to reduce variability in your results (note that $c_{rand}$ and $c_{min}$ will change from run to run) and compute average values for the $\nu$ 's.

1. $\nu_{min}$ is closed to:

[a] 0
[b] 0.01
[c] 0.1
[d] 0.5
[e] 0.67

In [28]:

import numpy as np

def experiment(times, coins=1000, flip_count=10):
    nu = np.zeros(3, dtype=float)
    for i in xrange(times):
        flips = np.random.binomial(flip_count, 0.5, coins)
        nu += [flips[0], np.min(flips), np.random.choice(flips)]
    return nu / times / flip_count

In [31]:

np.abs(experiment(100000)[1] - [0, 0.01, 0.1, 0.5, 0.67])

Out[31]:

array([ 0.037523,  0.027523,  0.062477,  0.462477,  0.632477])

Answer: [b] second difference is the smallest

2. Which coin or coins satisfy Hoeffding's Inequality?

[a] $c_1$ only
[b] $c_{rand}$ only
[c] $c_{min}$ only
[d] $c_1$ and $c_{rand}$
[e] $c_{min}$ and $c_{rand}$

Hoeffding's Inequality:

$P[|\nu - \mu| > \epsilon] \leq 2e^{-2\epsilon^2 N}$

Answer: [d] c_min is not a random draw from a single "bin" and as such is bounded by the union rule and not Hoeffding

Error and Noise¶

Consider the bin model for a hypothesis $h$ that makes an error with probability $\mu$ in approximating a deterministic target function $f$ (both $h$ and $f$ are binary functions). if we use same $h$ to approximate a noisy version of f given by:

$P(y|x) = \left\{ \begin{array}{11} \lambda & y = f(x) \\ 1-\lambda & y \neq f(x) \end{array} \right.$

3. What is the probability of error that $h$ makes in approximating $y$ ? Hint: Two wrongs can make a right!

[a] $\mu$
[b] $\lambda$
[c] $1-\mu$
[d] $(1-\lambda) * \mu + \lambda * (1-\mu)$
[e] $(1-\lambda) (1-\mu) + \lambda * \mu$

4. At what value of $\lambda$ will the performance of $h$ be independent of $\mu$ ?

[a] $0$
[b] $0.5$
[c] $1/\sqrt{2}$
[d] $1$
[e] no values of $\lambda$

Linear Regression¶

Nonlinear Transformation¶

In [ ]: