COSI 123A Statistical Machine Learning

Introduction

1. Introduction

Background Concepts

1. Random variables
2. Probability
   • Bayes' theorem
   • Chain rule
   • Independent
   • Conditional independent
3. Probability distribution
   • Gaussian
   • Bernoulli
   • Binomial
4. Descriptive statistics
   • Expectation
   • Variance
   • Covariance
5. Entropy
   • Definition $H[x]=-\sum _{x}p(x)lo{g}_{x}p(x)$
   • Important in coding theory, statistical physics, machine learning
   • Conditional entropy:
     • Definition: $H[Y|X]=-\sum _x\sum _{y}p(x,y)lo{g}_2(p(y|x))$, or $H[Y|X]=-\underset{x}{\int }\underset{y}{\int }p(x,y)lo{g}_2(p(y|x))dxdy$
     • Property: $H[X,Y]=H[x]+H[Y|X]=H[Y]+H[X|Y]$
   • Mutual information
     • Definition: $I[X,Y]=-\sum _x\sum _{y}p(x,y)lo{g}_2(\frac{p(x)p(y)}{p(x,y)}))$, or $U[X,Y]=-\underset{x}{\int }\underset{y}{\int }p(x,y)lo{g}_2(\frac{p(x)p(y)}{p(x,y)}))dxdy$
     • Property: $I[X,Y]=H[X]-H[X|Y]=H[Y]-H[Y|X]$
6. Kullback-Leibler Divergence
   • Definition: $KL(p(x)||q(x))=\underset{x}{\int }p(x)log(\frac{p(x)}{q(x)})=-\underset{x}{\int }p(x)log(\frac{q(x)}{p(x)})$
   • Property: $KL(p(x)||q(x))\ne KL(q(x)||p(x))$
   • Property: $I[X,Y]=KL(p(x,y)||p(x)p(y))$
7. Convex and concave functions
8. Vector, vector operations, matrix, matrix multiplication
9. Matrix calculus
   • $\frac{\partial (a\overrightarrow{x}+b)}{\partial \overrightarrow{x}}=a$
   • $\frac{\partial ({\overrightarrow{a}}^T\overrightarrow{x})}{\partial \overrightarrow{x}}={\overrightarrow{a}}^T$
   • $\frac{\partial ({\overrightarrow{x}}^T\overrightarrow{a})}{\partial \overrightarrow{x}}={\overrightarrow{a}}^T$
   • $\frac{\partial ({\overrightarrow{x}}^T\overrightarrow{x})}{\partial \overrightarrow{x}}=2{\overrightarrow{x}}^T$
   • $\frac{\partial A\overrightarrow{x}}{\overrightarrow{x}}=A$
   • $\frac{\partial {\overrightarrow{x}}^{T}A}{\overrightarrow{x}}=A^T$
10. Function approximation
    • $y=f(x;\overrightarrow{w})=\sum _{i=0}^M{w}_i{x}^i=\overrightarrow{w}x$
    • Sum of square error(SSE) = $E_{ss}(\overrightarrow{w})=\frac{1}{2}\sum _{n=1}^N[f(x_n;\overrightarrow{w})-y_n{]}^2$
    • Root-mean-square error(RMSE) = $\sqrt{\frac{\sum _{n=1}^N[f(x_n;\overrightarrow{w})-y_n{]}^2}{N}}$
11. Model selection
    • Select a model that fits data well and is as simple as possible

Linear Regression and Logistic Regression

1. Regression models
   • Answer what is the relationship between dependent variable and the independent variables
   • Given a dataset $\{<\overrightarrow{x_n,y_n}>\}$, where $\overrightarrow{x_n}\in {\mathbb{R}}^n$, and $y_n\in \mathbb{R}$, build a function $f(\overrightarrow{x};\overrightarrow{w})$ to predict the output of a new sample $\overrightarrow{x}$
2. Linear model
   • Estimate parameters
     • $f(\overrightarrow{x},\overrightarrow{w})={\overrightarrow{w}}^T\overrightarrow{x}$
     • Err = $\sum _{n=1}^N(y-f({\overrightarrow{x}}_n,\overrightarrow{w}){)}^2=(\overrightarrow{y}-X\overrightarrow{w}{)}^T(\overrightarrow{y}-X\overrightarrow{w})$
     • Solution: if X is full rank, then $\overrightarrow{w}=(X^{T}X{)}^{-1}{X}^T\overrightarrow{y}$
     • If $(X^{T}X)$ is singular, then there are features that are linear combinations of other features, so we need to reduce the amount of features to make $(X^{T}X)$ full rank
3. Linear basis function model
   • Replace $f(\overrightarrow{x};\overrightarrow{w})=w_0+...+w_d{x}_d$ with $f(\overrightarrow{x};\overrightarrow{w})=w_0+...+w_m{h}_m(\overrightarrow{x})$
   • $\{h_i(\overrightarrow{x})\}$ is a set of non-linear basis functions/kernel functions
4. Logistic regression & classification
   • $f(\overrightarrow{x};\overrightarrow{w})=\frac{1}{1+e^{{\overrightarrow{w}}^T\overrightarrow{x}}}$
   • Let $P(1|\overrightarrow{x};\overrightarrow{w})=f(\overrightarrow{x},\overrightarrow{w})$, $P(0|\overrightarrow{x};\overrightarrow{w})=1-f(\overrightarrow{x},\overrightarrow{w})$,
   • Classification rule: assign $\overrightarrow{x}$ to class 1 if $P(1|\overrightarrow{x};\overrightarrow{w})>P(0|\overrightarrow{x};\overrightarrow{w})$, otherwise assign $\overrightarrow{x}$ to class 0
   • $logit(\overrightarrow{x};\overrightarrow{w})=log(\frac{P(1|\overrightarrow{x};\overrightarrow{w})}{P(0|\overrightarrow{x};\overrightarrow{w})})={\overrightarrow{w}}^T\overrightarrow{x}$

Principal Component Analysis

Linear Discriminant Analysis

Bayesian Decision Theory

1. Formula
   • Given state $S\in \{s_1,...,s_M\}$.
   • Let decision $A\in \{a_1,...,a_N\}$.
   • Cost function $C(a_i|s_k)$ is the loss incurred for taking $A=a_i$ when $S=s_k$.
   • $P(s_k)$ is the prior probability of $S=s_k$.
   • Let observation be represented as a feature vector $\overrightarrow{x}$.
   • $P(\overrightarrow{x}|s_k)$ is the probability for $\overrightarrow{x}$ conditioned on $s_k$ being the true state
   • Expected loss before observing $\overrightarrow{x}$: $R(a_i)=\sum _{k=1}^{M}C(a_i|s_k)P(s_k)$.
   • Expected loss after observing $\overrightarrow{x}$: $R(a_i|\overrightarrow{x})=\sum _{k=1}^{M}C(a_i|s_k)P(s_k|\overrightarrow{x})$.
2. Bayesian risk
   • A decision function $D(x)$ maps from an observation $\overrightarrow{x}$ to a decision/action.
   • The total risk of a decision function is given by
     • Discrete: $E_{P(\overrightarrow{x})}=[R(D(\overrightarrow{x})|\overrightarrow{x})]=E_{\overrightarrow{x}}[R(D(\overrightarrow{x})|\overrightarrow{x})]P(\overrightarrow{x})$
     • Discrete: $E_{P(\overrightarrow{x})}=[R(D(\overrightarrow{x})|\overrightarrow{x})]={\int }_{\overrightarrow{x}}[R(D(\overrightarrow{x})|\overrightarrow{x})]P(\overrightarrow{x})$
   • A decision function is optimal if it minimizes the total risk. This optimal total risk is called Bayes risk.
3. Two-class Bayes Classifier
   • Let $M=2$, and compare $R(a_1|\overrightarrow{x})$ with $R(a_2|\overrightarrow{x})$
   • We can derive $R(a_1|\overrightarrow{x})<R(a_2|\overrightarrow{x})⟺\frac{P(\overrightarrow{x}|s_1)}{P(\overrightarrow{x}|s_2)}>\frac{P(s_2)[C(a_1|s_2)-C(a_2|s_2)]}{P(s_1)[C(a_2|s_1)-C(a_1|s_1)]}$, which is likelihood ration > constant threshold
   • Also we notice that $\frac{P(\overrightarrow{x}|s_1)}{P(\overrightarrow{x}|s_2)}\propto \frac{P(s_1|\overrightarrow{x})}{P(s_2|\overrightarrow{x})}$, which is likelihood ratio is proportional to posterior ratio
4. Minimum-error-rate classification
   • Consider the following cost function: $D_{it}=\{\begin{array}{ll}0,& i=j\\ 1& i\ne j\end{array}$
   • To minimize the average probability of error, we should select $s_i$ with the maximal posterior probability $P(s_i|\overrightarrow{x})$
   • Classify $\overrightarrow{x}$ as $s_i$ if $P(s_i|\overrightarrow{x})>P(s_j|\overrightarrow{x})$ for $\mathrm{\forall }j\ne i$
5. Classifiers and discriminant functions
   • A pattern classifier can be represented by a set of discriminant functions $\{g_i(\overrightarrow{x})\}$
   • The classifier assigns a sample $\overrightarrow{x}$ to $s_j$ if $g_i(\overrightarrow{x})<g_j(\overrightarrow{x})$ for $\mathrm{\forall }j\ne i$
   • If we replace every $g_i(\overrightarrow{x})$ by $f(g_i(\overrightarrow{x}))$, where f is a monotonically increasing function, the resulting classification is unchanged
   • A classifier that uses linear discriminant functions is called a linear classifier

Maximum Likelihood Estimation (MLE) and the Expectation and Maximization (EM) Algorithm