Computational Modeling
Fall 2005

For today: HomeworkSeventeen (fft)

Today's outline:

0) fft wrap-up

1) Bayes' theorem

2) Bayesian inference


For next time, read:

http://en.wikipedia.org/wiki/Bayes'_theorem

http://en.wikipedia.org/wiki/Bayesian_inference

http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/457.466.pdf


For next Monday: HomeworkEighteen


(an) fft solution
-----------------

def fft(h):
    """compute the discrete Fourier transform of the sequence h.
    Assumes that len(h) is a power of two.
    """
    N = len(h)
 
    # the Fourier transform of a single value is itself
    if N == 1: return h
 
    # recursively compute the FFT of the even and odd values
    He = fft(h[0:N:2])
    Ho = fft(h[1:N:2])
 
    # merge the half-FFTs
    i = complex(0,1)
    W = exp(2*pi*i/N)
    ws = [pow(W,k) for k in range(N)]
    H = [e + w*o for w, e, o in zip(ws, He+He, Ho+Ho)]
    return H


Efficiency considerations:

1) order of growth, time and space

2) constant factors


Interpreting the results.

Aliasing.


Bayesianism in three steps
--------------------------

Bayes theorem

                  philosophy 101: interpretation of probability

Bayesian inference

                  philosophy 201: requirements of rationality

Bayesian epistemology




Bayes' theorem
--------------

First step is an uncontroversial law of probability:

P(A and B) = P(A) P(B|A)
           = P(B) P(A|B)

This implies

P(A|B)    =  P(B|A)    * P(A)  / P(B)

posterior = likelihood * prior / normalizing constant


Diachronic interpretation:

P(H|E)    =  P(E|H)    * P(H)  / P(E)

H = hypothesis
E = evidence



Some examples
-------------

Cookie example from Wikipedia #1.

False positives from Wikipedia #2.


Nothing controversial so far!

What does probability mean?

Whoomp...there it is.