Wednesday, May 29, 2013

Another very simple way of looking at Bayes theorem



In an earlier post (back in 2011) I mentioned that it would be interesting to visit Eliezer Yudkowsky's site and in particular his explanation of Bayes' theorem. It still is. In the post I posed the question that Eliezer uses on his site and gave the answer but I suggested you go and visit his site to find out how to calculate it. I didn't realise how common that question was back then. I was thinking about it recently and thought it might be nice to show another, more graphical way of getting to grips with the calculation.

Here is the question:

1% of women at age forty who participate in routine screening have breast cancer. 80% of women with breast cancer will get positive mammographies. 9.6% of women without breast cancer will also get positive mammographies. A woman in this age group had a positive mammography in a routine screening. What is the probability that she actually has breast cancer?

Remember that in tests, only 15% of doctors got the correct answer. The same is true in courts where probability of guilt is calculated. There are lots of examples and it's pretty serious. Bayes' Theorem really needs to be better understood.



Step 1

Right, we can draw the following tree.
1% of women (0.01) have cancer. 
Therefore, 99% do not (0.99). 
We mark the values on the branches as shown
            
                
        0.01    
      --------- C [cancer]
     |          
     |          
     |          
     |           
     |
     |
start
     |
     | 
     |           
     |          
     |          
     |  0.99    
      --------- NC [no cancer]
                 



Step 2


What else do we know?
80% (0.8) of women with breast cancer will get positive mammographies. 9.6% (0.096) of women without breast cancer will also get positive mammographies.


                     0.8
                 ---------- P [positive]
                | 
                |
        0.01    |
      --------- [cancer]
     |          |
     |          |
     |          |
     |           ---------- N [negative]
     |
     |
start
     |
     |              0.096
     |           ---------- P [positive]
     |          |
     |          |
     |  0.99    |
      --------- NC [no cancer]
                |
                |
                |
                 ---------- N  [negative]  


So the question is, given the above tree, a woman gets a positive mammography in a routine screening. What is the probability that she actually has breast cancer?

Step 3

I want to fill in the missing branches just to make it complete. So before we get into calculating our answer we'll tidy up.

                    0.8
                 ---------- P [positive]
                | 
                |
        0.01    |
      --------- [cancer]
     |          |
     |          |
     |          |   0.2 
     |           ---------- N [negative]
     |
     |
start
     |
     |              0.096
     |           ---------- P [positive]
     |          |
     |          |
     |  0.99    |
      --------- NC [no cancer]
                |
                |
                |   0.904
                 ---------- N  [negative]  


The thing to do here, is to make the related branches add up to 1.0. 
So 0.8 + 0.2 = 1.0
And from the other node, 0.096 + 0.904 = 1.0
That is the probability of going down one of those two routes at each node is 100% (1.0)


Step 4


We calculate the final nodes, (they are intersections actually but that terminology might be confusing in this diagram. The intersections between C and P, C and N etc)
But 

                    0.8
                 ---------- P  C ∩ P = 0.01x0.8 = 0.008 
                | 
                |
        0.01    |
      --------- [cancer]
     |          |
     |          |
     |          |   0.2 
     |           ---------- N  C ∩ N = 0.01x0.2 = 0.002
     |
     |
start
     |
     |              0.096
     |           ---------- P  NC ∩ P = 0.99x0.096 = 0.095 
     |          |
     |          |
     |  0.99    |
      --------- NC [no cancer]
                |
                |
                |   0.904
                 ---------- N  NC ∩ N = 0.99x0.904 = 0.895  



Step 5

Now answer the question.
A woman gets a positive mammography in a routine screening. What is the probability that she actually has breast cancer?

So we write this as,

P( P | C)   
      
which means Probability( Positive | Cancer), 
or, the probability of getting a Positive, given that the woman has Cancer.

This is conditional probability.
 P( P | C ) can be converted to:

 C ∩ P          Note that  C ∩ P = P ∩ C  
   P

So we plug in the numbers:



 C ∩ P     =      0.008             
   P          0.008 + 0.095   <--(all of the posibilities of being positive)

           =  0.008 
              0.103

           = 0.77 or 7.7%  

most of the doctors when tested, estimated the figure to be around 70%!

The equation


It doesn't look too much like Bayes' theorem though does it. It might be good to work toward the equation now though we don't need to know it to do conditional probablity.

P(A|B) 
is read as the probability of A given B. So we know B, or B has happened, so what is the probability of A.


    P(A|B) = P(A ∩ B)
               P(B)


we can rearranged this as

    P(A ∩ B) = P(A|B).P(B)

It can be noted that 
    P(A ∩ B) = P(B ∩ A)
   
Also,

    P(A ∩ B) = P(A|B).P(B)
    P(A ∩ B) = P(B|A).P(A)

So,
          P(A|B).P(B) = P(B|A).P(A)

which can be arranged to give us the usual equation:

    P(A|B) = P(B|A).P(A)
                P(B)

Tuesday, May 21, 2013

Richard Feynman on Youtube

The Character of Physical Law - Part 1 The Law of Gravitation
http://www.youtube.com/watch?v=j3mhkYbznBk

The Character of Physical Law - Part 2 The Relation of Mathematics and Physics
http://www.youtube.com/watch?v=kd0xTfdt6qw&feature=endscreen

The Character of Physical Law - Part 3 The Great Conservation Principles
http://www.youtube.com/watch?v=a6n0HSJ5jEE
This one has a problem with the sound

The Character of Physical Law - Part 4 Symmetry in Physical Law
http://www.youtube.com/watch?v=zQ6o1cDxV7o
I think these are all from 1964


Richard Feynman on Quantum Mechanics Part 1 - Photons Corpuscles of Light http://www.youtube.com/watch?v=xdZMXWmlp9g
University of Auckland New Zealand 1979


Richard Feynman Computer Heuristics Lecture
http://www.youtube.com/watch?v=EKWGGDXe5MA&feature=endscreen
1985


Friday, May 10, 2013

Greatest Common Divisor in Prolog

I am writing this because it's interesting and useful in seeing how Arithmetic can work in Prolog. It's from the Ivan Bratko book, Prolog Programming for Artificial Intelligence.
It's a great book.
Given two positive integers X and Y, their greatest common divisor, D, can be found according to three cases:
  1. If X and Y are equal then D is equal to X.
  2. If X < Y then D is equal to the greatest common divisor of X and the difference Y - X.
  3. If Y < X then do the same as (2.) with X and Y interchanged.


The rules can be expressed as a Prolog program by defining a three argument relation:
gcd( X, Y, D).
The three rules are then expressed as three clauses:

gcd( X,X,X).

gcd( X, Y, D) :-
   X < Y,
  Y1 is Y - X,
  gcd( X, Y1, D).

gcd( X, Y, D) :-
  Y < X,
  gcd( Y, X, D).

To me this was not immediatly apparent and I had not seen it before so I worked through Ivan Bratko's  example just to confirm it worked. Lo-and-behold it does.


scenario 1. X = 20 and Y = 25
So with this example, The greatest common divisor is 5.
We just subtract our way down, something like this:

[trace] 1 ?- gcd(20, 25, D).
   Call: (6) gcd(20, 25, _G1990) ? creep
   Call: (7) 20<25 ? creep
   Exit: (7) 20<25 ? creep
   Call: (7) _G2066 is 25-20 ? creep
   Exit: (7) 5 is 25-20 ? creep
   Call: (7) gcd(20, 5, _G1990) ? creep
   Call: (8) 20<5 ? creep
   Fail: (8) 20<5 ? creep
   Redo: (7) gcd(20, 5, _G1990) ? creep
   Call: (8) 5<20 ? creep
   Exit: (8) 5<20 ? creep
   Call: (8) gcd(5, 20, _G1990) ? creep
   Call: (9) 5<20 ? creep
   Exit: (9) 5<20 ? creep
   Call: (9) _G2069 is 20-5 ? creep
   Exit: (9) 15 is 20-5 ? creep
   Call: (9) gcd(5, 15, _G1990) ? creep
   Call: (10) 5<15 ? creep
   Exit: (10) 5<15 ? creep
   Call: (10) _G2072 is 15-5 ? creep
   Exit: (10) 10 is 15-5 ? creep
   Call: (10) gcd(5, 10, _G1990) ? creep
   Call: (11) 5<10 ? creep
   Exit: (11) 5<10 ? creep
   Call: (11) _G2075 is 10-5 ? creep
   Exit: (11) 5 is 10-5 ? creep
   Call: (11) gcd(5, 5, _G1990) ? creep
   Exit: (11) gcd(5, 5, 5) ? creep
   Exit: (10) gcd(5, 10, 5) ? creep
   Exit: (9) gcd(5, 15, 5) ? creep
   Exit: (8) gcd(5, 20, 5) ? creep
   Exit: (7) gcd(20, 5, 5) ? creep
   Exit: (6) gcd(20, 25, 5) ? creep
D = 5 .

The only maths bit is the
Y1 is Y - X 
but it shows how to use is It's a mathematical equals really.



Sunday, May 5, 2013

Prolog resources

Getting started

An introduction to logic programming through Prolog
An introduction to logic programming through Prolog was published by Prentice-Hall in 1996 but is now out of print. The author kindly provides a pdf of the text here:
http://spivey.oriel.ox.ac.uk/corner/Logic_Programming

Learn Prolog Now! website
Online
http://www.learnprolognow.org/lpnpage.php?pageid=online


Programming in Prolog: Using the ISO Standard 
by C.S. Mellish (Author), W.F. Clocksin



Logic

"Bob's book". Logic for Problem Solving
Logic for Problem Solving by Robert Kowalski is out of print but fortunatley the text can be viewed in pdf for at his web page at Imperial College.


Simply Logical, Intelligent Reasoning by Example
Simply Logical, Intelligent Reasoning by Example by Peter Flach is out of print but he kindly provides a pdf http://www.cs.bris.ac.uk/~flach/SimplyLogical.html

AI

Prolog Programming for Artificial Intelligence
by Ivan Bratko


Interesting Sites

Logic in Action
http://www.logicinaction.org

This is the new homepage of the Logic in Action Open Course Project. The project aims at the development of elementary and intermediate courses in logic in electronic form.

Wednesday, May 1, 2013

UML Sequence diagrams - TraceModeller, It's the business!

Sequence diagrams are such a useful model. I've always thought so, and often I've wanted to create them and my employer only had Visio to hand. Visio is big, it's clever, but it's too general trying to do all things for all people.

A colleguq has shown me his personal copy of Tracemodeller and it's so good. Yes it's a bit Java UI and sparten but that shouldn't matter. $109 I think.

http://www.tracemodeler.com/