\documentclass[landscape,letterpaper,final]{article}
% squeeze vertical space technique at
% http://www.terminally-incoherent.com/blog/2007/09/19/latex-squeezing-the-vertical-white-space/

\usepackage[scale={0.95,0.95},centering,includeall,noheadfoot,nomarginpar,dvips]{geometry}
\usepackage{palatino}
\usepackage{amsmath,amsthm,amssymb}
\usepackage[dvips]{hyperref}
\usepackage{url}
\usepackage{graphicx}
\DeclareGraphicsExtensions{.eps}
\usepackage{mdwlist} % use enumerate* and itemize* instead

\usepackage{multicol}
\setlength{\columnseprule}{1pt}
\setlength{\columnsep}{4ex}

\usepackage[compact]{titlesec}
\titlespacing{\section}{0pt}{*0}{*0}
\titlespacing{\subsection}{0pt}{*0}{*0}
\titlespacing{\subsubsection}{0pt}{*0}{*0}

\pagestyle{empty}
%\setlength{\parindent}{0pt}
\setlength{\parskip}{0pt}
\setlength{\parsep}{0pt}
\setlength{\partopsep}{0pt}
\linespread{0.5}

\title{CS590 Pattern Recognition\\cheatsheat}
\author{Wei Peng}
\date{}

\newcommand{\mathd}{\,\mathrm{d}}
\newcommand{\erf}{\,\mathrm{erf}}
\newcommand{\oops}[1]{\textbf{#1}}

%% End of preamble

%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\setlength{\abovedisplayshortskip}{0pt}
\setlength{\belowdisplayshortskip}{0pt}
\setlength{\abovedisplayskip}{0ex}
\setlength{\belowdisplayskip}{0ex}

\begin{multicols*}{3}
  \begin{center}
    {\LARGE \oops{CS590 Pattern Recognition\\cheatsheet}\vspace{.5ex}}

    {\large Wei Peng\vspace{.5ex}}
  \end{center}
  \section{Bayesian Decision Theory}
  \subsection{Preliminaries}
  \[
  P(\omega_i|x) = \frac{p(x|\omega_i)P(\omega)}{p(x)}
  \]
  \[
  P(\mbox{posterior})=\frac{\mbox{likelihood}\times \mbox{prior}}{\mbox{evidence}}
  \]
 \(p(X=x|\omega)\) is \emph{class-conditional function}.

  Risk function
  \[
  \begin{split}
  R(\omega, \delta) &= R_\delta = E_\omega[L(\omega, \delta(x))] \\
  &= \int_x\,L(\omega, \delta(x))p(x|\omega)\mathd x
  \end{split}
  \]

  Bayesian risk function
  \[
  R(\omega_i|x) = \sum_{j=1}^c\lambda_{ij}P(\omega_j|x)
  \]

  Two-category classification
  \[
  \begin{split}
    R(\alpha_1|x) &= \lambda_{11}P(\omega_1|x) + \lambda_{12} P(\omega_2|x)\\
    R(\alpha_2|x) &= \lambda_{21}P(\omega_1|x) + \lambda_{22} P(\omega_2|x).
  \end{split}
  \]
  Choose $\alpha_1$ if $R(\alpha_1|x)<R(\alpha_2|x)$, i.e.
  \[
  \frac{p(x|\omega_1)}{p(x|\omega_2)}>\frac{\lambda_{12}-\lambda_{22}}{\lambda_{21}-\lambda_{11}}\times\frac{P(\omega_2)}{\omega_1}.
  \]

  \subsection{Minimax Criterion}
  Minimax criterion implies \emph{worst case analysis}.
  \[
  \begin{split}
    R &= \int_{R_1}[\lambda_{11}P(\omega_1)p(x|\omega_1)+\lambda_{12}P(\omega_2)p(x|\omega_2)]\mathd x\\
      &\quad+\int_{R_2}[\lambda_{21}P(\omega_1)p(x|\omega_1)+\lambda_{22}P(\omega_2)p(x|\omega_2)]\mathd x\\
 \end{split}
  \]
  Use the facts $P(\omega_2)=1-P(\omega_1)$ and $\int_{R_1}p(x|\omega_1)\mathd x=1-\int_{R_2}p(x|\omega_1)$
  \[
  \begin{split}
    R(P(\omega_1)) &= \overbrace{\lambda_{22}+(\lambda_{12}-\lambda_{22})\int_{R_1}p(x|\omega_2)\mathd x}^{\mbox{the minimax risk}}\\
    &\quad
    +P(\omega_1)[
    (\lambda_{11}-\lambda_{22})\\
    &\qquad
    +
    (\lambda_{21}-\lambda_{11})\int_{R_2}p(x|\omega_1)\mathd x\\
    &\qquad
    -
    (\lambda_{12}-\lambda_{22})\int_{R_1}p(x|\omega_1)\mathd x
    ]
  \end{split}
  \]
  The coefficient of $P(\omega_1)$ is $0$.

  \subsection{Neyman-Pearson}
  For hypothesis test, among the tests with size $\alpha$ (given type \romannumeral 1{} error---false positive)
  \[
  \alpha = \int_{\Omega_2}p(x|\omega_1)\mathd x,
  \] 
  the \emph{likelihood test} is the most \emph{powerful} (minimal Type \romannumeral 2{} error---false negative) one with power $1-\beta$, in which $\beta$ is given by
  \[
  \beta = \int_{\Omega_1}p(x|\omega_2)\mathd x.
  \]

  The likelihood test is to favors $\omega_1$ if
  in which $T$ is some threshold; otherwise, favors $\omega_2$.

  Thus, Neyman-Pearson rule states that the decision region $\Omega_1$ for $\omega_1$ is
  \[
  C_\alpha=\{x|\Lambda(x)\geq T_\alpha\}
  \]
  in which
  \[
  \Lambda(x)\doteq \frac{p(x|\omega_1)}{p(x|\omega_2)}
  \]
  is the \emph{likelihood} and $T_\alpha$ satisfying
  \[
  \alpha = \int_{\Omega_2} p(x|\omega_1)\mathd x=\int_{-\infty}^{T_\alpha} p(\Lambda|\omega_1)\mathd\Lambda.
  \]

  Then the power of the test is
  \[
  1-\beta = \int_{\Omega_2} p(x|\omega_2)\mathd x=\int_{T_\alpha}^{\infty} p(\Lambda|\omega_2)\mathd\Lambda.
  \]

  Example
  \[
  \begin{split}
    p(x|\omega_1)&\sim N(\mu_1, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x-\mu_1)^2}{2\sigma^2}\right)\\
    p(x|\omega_2)&\sim N(\mu_2, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp\left(-\frac{(x-\mu_2)^2}{2\sigma^2}\right)
  \end{split}
  \]
  Let the decision region $C_\alpha=\{x|x\geq x_1\}$, we have
  \[
  \alpha = \frac{1}{2} - \frac{1}{2}\erf(\frac{x_1-\mu_1}{\sqrt{2}\sigma}),
  \]
  or equivalently
  \[
  x_1 = \mu_1 + \sqrt{2}\sigma\erf^{-1}(1-\alpha).
  \]
  The power is
  \[
  1 - \beta = \frac{1}{2} - \frac{1}{2}\erf(\frac{x_1-\mu_2}{\sqrt{2}\sigma}).
  \]

  \subsection{Bayesian Classifier: Gaussian Density}
  \subsubsection{Background}
  Use discriminant function, e.g., posterior probabilities (with or without normalization factor), log-posterior\(g_i(x) = \ln p(x|\omega_i) + \ln P(\omega_i)\).

  Univariate and multivariate Gaussian
  \[
    p(x) = \frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)
  \]
  \[
    p(x) = \frac{1}{(2\pi)^{\frac{d}{2}}|\Sigma|^{\frac{1}{2}}}\exp\left(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\right).
  \]
  We have
  \[
  \mu = \mathcal{E}[x]=\int xp(x)\mathd x,
  \]
  \[
  \Sigma = \mathcal{E}[(x-\mu)(x-\mu)^T] = \int(x-\mu)(x-\mu)^Tp(x)\mathd x,
  \] and
  \[
  \mbox{cdf} = \frac{1}{2}\left[1+\erf(\frac{x-\mu}{\sqrt{2}\sigma})\right].
  \]
  in which
  \[
  \erf(x) = \frac{2}{\sqrt{\pi}} \int_{0}^x e^{-t^2}\mathd t.
  \] is the \emph{error function}, defined for $x\geq 0$.

  \emph{Mahalanobis} distance is \(\sqrt{(x-\mu)^T\Sigma^{-1}(x-\mu)}\).
  
  Let $\Lambda=\mbox{diag}(\lambda_1, \ldots, \lambda_d)$ and $A^T=[e_1, \ldots, e_d]$, then
  \[
  \Sigma = A^T\Lambda A.
  \]
  \subsubsection{Bayesian Decision Boundary}
  Take log-posterior as the discriminant function
  \[
  \begin{split}
    g_i(x) &=\ln p(x|\omega_i) + \ln P(\omega_i)\\
    &= -\frac{1}{2}(x-\mu_i)^T\Sigma_i^{-1}(x-\mu_i) - \frac{d}{2}\ln 2\pi \\
    &\quad - \frac{1}{2}\ln|\Sigma_i| + \ln P(\omega_i).
  \end{split}
  \]

    The decision boundary is
  \begin{itemize*}
    \item \textbf{$\mathbf{\Sigma_i=\sigma^2 I}$\quad}
      \[
      w^T(x-x_0) = 0
      \]
      in which $w=\mu_i-\mu_j$ and
      \[
      x_0 = \frac{1}{2}(\mu_i+\mu_j) - \frac{\sigma^2}{\Vert\mu_i-\mu_j\Vert}\ln[\frac{P(\omega_i)}{P(\omega_j)}](\mu_i-\mu_j).
      \]

    \item \textbf{$\mathbf{\Sigma_i=\Sigma}$\quad}
      \[
      w^T(x-x_0) = 0
      \]
      in which $w=\Sigma^{-1}(\mu_i-\mu_j)$ and
      \[
      x_0 = \frac{1}{2}(\mu_i+\mu_j) - \frac{\ln[P(\omega_i)/P(\omega_j)]}{(\mu_i-\mu_j)^T\Sigma^{-1}(\mu_i-\mu_j)}(\mu_i-\mu_j).
      \]

    \item \textbf{$\mathbf{\Sigma_i}$ is arbitrary\quad}
      \[
      g_i(x) = x^TW_ix + w_i^Tx + w_{i0}      
      \]
      in which $W_i=-\frac{1}{2}\Sigma_i^{-1}$, $w_i=\Sigma^{-1}\mu_i$, and
      \[
      w_{i0}=-\frac{1}{2}\mu_i^T\Sigma_i^{-1}\mu_i - \frac{1}{2}\ln|\Sigma_i| + \ln P(\omega_i).
      \]
  \end{itemize*}

  \subsection{Two-class Error Boundary}
  \subsubsection{Chernoff Bound}
  \[
  P(error) = \int_{-\infty}^{\infty}P(error|x)p(x)\mathd x
  \]
and by Bayesian decision rule
  \[
  P(error|x) = \min[P(\omega_1|x), P(\omega_2|x)]\doteq \min[a, b].
  \]
  By the inequality $\min[a, b]\leq a^\beta b^{1-\beta}$ for $a, b\geq 0$ and $0\leq\beta\leq 1$ and the Bayes rule $P(\omega_i|x)p(x)=p(x|\omega_i)P(\omega_i)$, we have
  \[
  P(error)\leq P(\omega_1)^\beta P(\omega_2)^{1-\beta} \int p(x|\omega_1)^\beta p(x|\omega_2)^{1-\beta}\mathd x
  \] for some $0\leq\beta\leq 1$.

  For the case that $p(x|\omega_i)\sim N(\mu_i, \Sigma_i)$, we get
  \[
  \int p(x|\omega_1)^\beta p(x|\omega_2)^{1-\beta}\mathd x = \exp[-k(\beta)]
  \]
  where
  \[
  \begin{split}
    k(\beta) &= \frac{\beta(1-\beta)}{2}(\mu_2-\mu_1)^T\\
    &\quad \times[\beta\Sigma_1+(1-\beta)\Sigma_2]^{-1}(\mu_2-\mu_1)\\
    &\quad + \frac{1}{2}\ln\frac{|\beta\Sigma_1+(1-\beta)\Sigma_2|}{|\Sigma_1|^\beta|\Sigma_2|^{1-\beta}}.
  \end{split}
  \]

  Find the $\beta=\beta^*$ which minimizes $k(\beta)$. The \emph{Chernoff bound} is found by substitutes $\beta^*$ into $P(error)$.

  \subsubsection{Bhattacharya Bound}
  The \emph{Bhattacharya bound} is found by substitutes $\beta=\frac{1}{2}$ into $P(error)$.

  \subsection{Noisy Feature}
  Deal with \emph{bad} (noisy) features by marginalization
  \[
  P(\omega_i|x_g) = \frac{\int P(\omega_i|x_g, x_b)p(x_g, x_b)\mathd x_b}{\int p(x_g, x_b)\mathd x_b}.
  \]
  
  Choose $\omega_i$ if $P(\omega_i|x_g)>P(\omega_j|x_g)$, $\forall j\neq i$.

  \section{Parameter Estimation/Learning}
  \subsection{Maximum Likelihood Estimation}
  \subsubsection{Background}
  $p(\mathcal{D}|\theta)$ is the \emph{likelihood of $\theta$ with respect to the sample $\mathcal{D}$}. By the independent-sample assumption,
  \[
  p(\mathcal{D}|\theta) = \prod_{k=1}^n p(x_k|\theta).
  \]

  Log-likelihoood maths tractable.

  \subsubsection{Plug-in Rule}
  Substitute the estimated parameter $\hat{\theta}$ for the true ones in the class-conditional densities. Then use $p(x|\omega_i, \hat{\theta})$ as if they were true densities in constructing the decision rule.
  
  \subsubsection{Example: Gaussian}
  Conclusion: use \emph{sample} mean and covariance.
  \[
  \hat{\mu} = \frac{1}{n}\sum_{i=1}^n x_i = \mbox{sample mean}
  \]
  \[
  \hat{\Sigma} = \frac{1}{n}(x_i-\hat{\mu})(x_i-\hat{\mu})^T=\mbox{sample covariance}.
  \]


  \subsection{Bayesian Learning}
  \subsubsection{Idea}
  \begin{itemize*}
    \item Allows treating the parameters as random variables themselves and estimates the density for the parameters.
    \item Can be formulated as a recursive estimation, thus allowing one to incorporate new evidence one at a time as they come along.
  \end{itemize*}

  \subsubsection{Formulation}
  \[
  p(\omega_i|x, \mathcal{D}_i)=\frac{p(x|\omega_i, \mathcal{D}_i)P(\omega)}{\Sigma_{j=1}^c p(x|\omega_j, \mathcal{D}_j)P(\omega_j)}
  \]
  \[
  p(x|D) = \int p(x|\theta)p(\theta|\mathcal{D})\mathd \theta
  \]
  The key lies in estimating $p(\theta|\mathcal{D})$.

  \subsubsection{Example: Univariate Gaussian}
  If $p(x_k|\mu)\sim N(\mu, \sigma^2)$ and $p(\mu)\sim N(\mu_0, \sigma_0^2)$, we have
  \[
  \mu_n = \left(\frac{n\sigma_0^2}{n\sigma_0^2+\sigma^2}\right)\hat{\mu}_n+\frac{\sigma^2}{n\sigma_0^2+\sigma^2}\mu_0
  \]
  \[
  \sigma_n^2 = \frac{\sigma_0^2\sigma^2}{n\sigma_0^2+\sigma^2}.
  \]
  $\sigma^2/\sigma_0^2$ is called \emph{dogmatism}.

  We get 
  \[
  p(\theta|\mathcal{D})\sim N(\mu_n, \sigma^2+\sigma_n^2).
  \]

  \subsubsection{Example: Multivariate Gaussian}
  Similar results:
  \[
  p(x|\mathcal{D}) \sim N(\mu_n, \Sigma+\Sigma_n)
  \]
  \[
  \mu_n = \Sigma_0\left(\Sigma_0 + \frac{1}{n}\Sigma\right)^{-1}\hat{\mu}_n + \frac{1}{n}\Sigma\left(\Sigma_0+\frac{1}{n}\Sigma\right)^{-1}\mu_0
  \]
  \[
  \Sigma_n = \Sigma_0\left(\Sigma_0 + \frac{1}{n}\Sigma\right)^{-1}\frac{1}{n}\Sigma.
  \]

\end{multicols*}
\end{document}
