{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Probability Theory Review" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Preliminaries\n", "\n", "- Goal \n", " - Review of probability theory from a logical reasoning viewpoint (i.e., a Bayesian interpretation)\n", "- Materials \n", " - Mandatory\n", " - These lecture notes\n", " - Optional\n", " - Bishop pp. 12-20 \n", " - [Bruininkx - 2002 - Bayesian Probability](./files/Bruyninkx-2002-Bayesian-probability.pdf)\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Example Problem: Disease Diagnosis\n", "\n", "- **[Question]** Given a disease with prevalence of 1% and a test procedure with sensitivity ('true positive' rate) of 95% and specificity ('true negative' rate) of 85% , what is the chance that somebody who tests positive actually has the disease?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- **[Solution]** Use probabilistic inference, to be discussed in this lecture. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Why Probability Theory?\n", "\n", "- Probability theory (PT) is the **theory of optimal processing of incomplete information** (see [Cox theorem](https://en.wikipedia.org/wiki/Cox%27s_theorem)), and as such provides a quantitative framework for drawing conclusions from a finite (read: incomplete) data set. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Machine learning concerns drawing conclusions from (a finite set of) data and therefore PT is the _optimal calculus for machine learning_. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- In general, nearly all interesting questions in machine learning can be stated in the following form (a conditional probability):\n", "$$p(\\text{whatever-we-want-to-know}\\, | \\,\\text{whatever-we-do-know})$$\n", " - For example:\n", " - Predictions\n", " $$p(\\,\\text{future-observations}\\,|\\,\\text{past-observations}\\,)$$\n", " - Classify a received data point \n", " $$p(\\,x\\text{-belongs-to-class-}k \\,|\\,x\\,)$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ " \n", "- **Information theory** (\"theory of log-probability\") provides a source coding view on machine learning that is consistent with probability theory (more in part-2). " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Probability Theory Notation\n", "\n", "- Define an **event** $A$ as a statement, whose truth is contemplated by a person, e.g.,\n", "\n", "$$A = \\text{'it will rain tomorrow'}$$\n", " " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- We write the denial of $A$, i.e. the event **not**-A, as $\\bar{A}$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "##### probabilities\n", "\n", "- For any event $A$, with background knowledge $I$, the **conditional probability of $A$ given $I$**, is written as \n", "$$p(A|I)$$" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true, "slideshow": { "slide_type": "fragment" } }, "source": [ " \n", "- The value of a probability is limited to $0 \\le p(A|I) \\le 1$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- All probabilities are in principle conditional probabilities of the type $p(A|I)$, since there is always some background knowledge. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ " - Still, we often write $p(A)$ rather than $p(A|I)$ if the background knowledge $I$ is assumed to be obviously present. E.g., $p(A)$ rather than $p(\\,A\\,|\\,\\text{the-sun-comes-up-tomorrow}\\,)$.\n", " " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "##### probabilities for random variable assignments\n", "\n", "- Note that, if $X$ is a random variable, then the assignment $X=x$ (with $x$ a value) can be interpreted as an event. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- We often write $p(x)$ rather than $p(X=x)$ (hoping that the reader understands the context ;-) " ] }, { "cell_type": "markdown", "metadata": { "collapsed": true, "slideshow": { "slide_type": "fragment" } }, "source": [ "- In an apparent effort to further abuse notational conventions, $p(X)$ often denotes the full distribution over random variable $X$, i.e., the distribution for all assignments for $X$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "##### compound events\n", "\n", "- The **joint** probability that both $A$ and $B$ are true, given $I$ (a.k.a. **conjunction**) is written as\n", "$$p(A,B|I)$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- $A$ and $B$ are said to be **independent**, given $I$, if (and only if) $$p(A,B|I) = p(A|I)\\,p(B|I)$$ " ] }, { "cell_type": "markdown", "metadata": { "collapsed": true, "slideshow": { "slide_type": "fragment" } }, "source": [ "- The probability that either $A$ or $B$, or both $A$ and $B$, are true, given $I$ (a.k.a. **disjunction**) is written as \n", "$$p(A+B|I)$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Probability Theory Calculus\n", " \n", "- **Normalization**. If you know that event $A$ given $I$ is true, then $p(A|I)=1$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- **Product rule**. The conjuction of two events $A$ and $B$ with given background $I$ is given by \n", "$$ p(A,B|I) = p(A|B,I)\\,p(B|I) \\,.$$\n", " - If $A$ and $B$ are independent given $I$, then $p(A|B,I) = p(A|I)$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- **Sum rule**. The disjunction for two events $A$ and $B$ given background $I$ is given by\n", "$$ p(A+B|I) = p(A|I) + p(B|I) - p(A,B|I)\\,.$$\n", " - As a special case, it follows from the sum rule that $ p(A|I) + p(\\bar{A}|I) = 1$\n", " - Note that the background information may not change, e.g., if $I^\\prime \\neq I$, then \n", "$$ p(A+B|I^\\prime) \\neq p(A|I) + p(B|I) - p(A,B|I)\\,.$$ " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- **All legitimate probabilistic relations can be derived from the sum and product rules!**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- The product and sum rules are also known as the **axioms of probability theory**, but in fact, under some mild conditions, they can be derived as the unique rules for rational reasoning under uncertainty ([Cox theorem, 1946](https://en.wikipedia.org/wiki/Cox%27s_theorem))." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Frequentist vs. Bayesian Interpretation of Probabilities\n", "\n", "- In the **frequentist** interpretation, $p(A)$ relates to the relative frequency that $A$ would occur under repeated execution of an experiment. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ " - For instance, if the experiment is tossing a coin, then $p(\\texttt{tail}) = 0.4$ means that in the limit of a large number of coin tosses, 40% of outcomes turn up as $\\texttt{tail}$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- In the **Bayesian** interpretation, $p(A)$ reflects the **degree of belief** that event $A$ is true. I.o.w., the probability is associated with a **state-of-knowledge** (usually held by a person). \n", " - For instance, for the coin tossing experiment, $p(\\texttt{tail}) = 0.4$ should be interpreted as the belief that there is a 40% chance that $\\texttt{tail}$ comes up if the coin were tossed.\n", " - Under the Bayesian interpretation, PT calculus (sum and product rules) **extends boolean logic to rational reasoning with uncertainty**. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- The Bayesian viewpoint is more generally applicable than the frequentist viewpoint, e.g., it is hard to apply the frequentist viewpoint to the event '$\\texttt{it will rain tomorrow}$'. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- The Bayesian viewpoint is clearly favored in the machine learning community. (In this class, we also strongly favor the Bayesian interpretation). " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### The Sum Rule and Marginalization\n", "\n", "- We discussed that every inference problem in PT can be evaluated through the sum and product rules. Next, we present two useful corollaries: (1) Marginalization and (2) Bayes rule " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- If $X$ and $Y$ are random variables over finite domains, than it follows from the sum rule that \n", "$$\n", "p(X) = \\sum_Y p(X,Y) = \\sum_Y p(X|Y) p(Y) \\,.\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Note that this is just a **generalized sum rule**. In fact, Bishop (p.14) (and some other authors as well) calls this the sum rule.\n", " - EXERCISE: Proof the generalized sum rule." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Of course, in the continuous domain, the (generalized) sum rule becomes\n", "$$p(X)=\\int p(X,Y) \\,\\mathrm{d}Y$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Integrating $Y$ out of a joint distribution is called **marginalization** and the result $p(X)$ is sometimes referred to as the **marginal probability**. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### The Product Rule and Bayes Rule\n", "\n", "- Consider 2 variables $D$ and $\\theta$; it follows symmetry arguments that \n", "$$p(D,\\theta)=p(D|\\theta)p(\\theta)=p(\\theta|D)p(D)$$ \n", "and hence that\n", "$$ p(\\theta|D) = \\frac{p(D|\\theta) p(\\theta)}{p(D)}\\,.$$ " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- This formula is called **Bayes rule** (or Bayes theorem). While Bayes rule is always true, a particularly useful application occurs when $D$ refers to an observed data set and $\\theta$ is set of model parameters that relates to the data. In that case,\n", "\n", " - the **prior** probability $p(\\theta)$ represents our **state-of-knowledge** about proper values for $\\theta$, before seeing the data $D$.\n", " - the **posterior** probability $p(\\theta|D)$ represents our state-of-knowledge about $\\theta$ after we have seen the data." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "$\\Rightarrow$ Bayes rule tells us how to update our knowledge about model parameters when facing new data. Hence, \n", "\n", "