Motivation:
we have huge data sets (i.e. google index) that are themselves
approximations. Why do we have determinstic / exect methods to operate
on approximate data?
Example:
List l;
populate l;
# sum l for number 7
def sum:
s = 0
foreach i in l:
if i == 7: s += 1
return s
If l has 1 billion elements, we will be waiting a long time. Would
like to use probability to approximate result and save on computation
i.e. cut computation in half, be correct 50% of the time
We introduce a new iterator that subsamples the list l based on p
# specify that we want a bound of 50%
def sum:
s = 0
foreachp(.5) i in l:
if i == 7: s += 1
return s
# specify that we want a bound of 95%
def sum:
s = 0
foreachp(.95) i in l:
if i == 7: s += 1
return s
However, if we know something about the way data are distributed in l,
we can do much better. i.e. imagine we know that 7 is more likely to
be in the first 100 elements of l than anywhere else. In effect, we
have specified a prior over the distribution of the value 7 over l.
Our foreach(0.95) now really only has to sample 95 elements from the
first 100 (95/100 = 0.95) to satisify this condition.
# specify that we want a bound of 95% and how 7 is likely distributed in l
def sum:
s = 0
foreachp(.9) i in l where p(7 | Index < 100) = 0.8:
if i == 7: s += 1
return s
Questions:
(i) come up with language constructs that allow us to talk about
this stuff succinctly?
(ii) statically come up with priors over data?
(iii) propagate probabalities?
sum() + sum() = ?
sum() * sum() = ?
Notes:
p(7 | Index < 20) = p(Index < 20 | 7) * p(7) / p(Index < 20)
where
p(7) = uniform?
p(Index < 20) = 20 / length(l)
p(Index < 20 | 7) = ?
N trials. For each trial success if sample = 7.
Draw $N$ trials from a multinomial distribution with each trial
resulting in exactly one of $K$ possible outcomes.
Bowl #1: 10 chocolate chip, 30 plain
Bowl #2: 20 chocolate chip, 20 plain
draw at random: cookie is plain. H = picked from bowl #1?
H = bowl #1, H2 = bowl #2
P(H_1) = P(H_2) = 1.0
P(E|H_1) = 30 / 40 = 0.75
P(E|H_2) = 20 / 40 = 0.50
P(H_1|E) = P(E|H_1) * P(H_1) / {P(E|H_1)*P(H_1) + P(E|H_2)*P(H_2)}
= 0.6