notes.lyx

#LyX 2.0 created this file. For more info see http://www.lyx.org/
\lyxformat 413
\begin_document
\begin_header
\textclass article
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\use_mhchem 1
\use_mathdots 1
\cite_engine basic
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\use_refstyle 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
\begin_inset FormulaMacro
\newcommand{\Var}{\text{Var}}
\end_inset


\begin_inset FormulaMacro
\newcommand{\E}{\text{E}}
\end_inset


\begin_inset FormulaMacro
\newcommand{\norm}[1]{\left\Vert #1\right\Vert }
\end_inset


\begin_inset FormulaMacro
\newcommand{\transpose}[1]{#1^{\text{T}}}
\end_inset


\begin_inset FormulaMacro
\newcommand{\Cov}{\text{Cov}}
\end_inset


\end_layout

\begin_layout Section
Identities, approximations, limits
\end_layout

\begin_layout Itemize
Identity: 
\begin_inset Formula $\lim_{x\rightarrow\infty}\left(1+\frac{a}{x}\right)^{x}=e^{a}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $e^{x}>1+x$
\end_inset

 for 
\begin_inset Formula $x>0$
\end_inset

 and 
\begin_inset Formula $e^{x}\approx1+x$
\end_inset

 for 
\begin_inset Formula $-.1<x<.1$
\end_inset


\end_layout

\begin_layout Itemize
Euler's identity: 
\begin_inset Formula $e^{i\pi}+1=0$
\end_inset

 (from 
\begin_inset Formula $e^{ix}=\cos x+i\sin x$
\end_inset

)
\end_layout

\begin_layout Section
General
\end_layout

\begin_layout Itemize
geometric mean 
\begin_inset Formula $\left(\prod_{i}x_{i}\right)^{\frac{1}{n}}$
\end_inset

 is exp of arith mean of logs, 
\begin_inset Formula $\exp\left(\frac{1}{n}\sum_{i}\log x_{i}\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
eg annualizing compounding: given annual growths 
\begin_inset Formula $a,b,c>1$
\end_inset

 and initial price 
\begin_inset Formula $p_{0}$
\end_inset

, 
\begin_inset Formula $p_{3}=abcp_{0}=\mu^{3}p_{0}$
\end_inset

 where geometric mean 
\begin_inset Formula $\mu=\sqrt[3]{abc}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
harmonic mean 
\begin_inset Formula $\left(\frac{1}{n}\sum_{i=1}^{n}x_{i}^{-1}\right)^{-1}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
if 
\begin_inset Formula $x_{i}$
\end_inset

 subject to (arithmetic-)mean-preserving spread, harmonic mean decreases
\end_layout

\begin_layout Itemize
preferable way to avg multiples, e.g.
 P/E ratio
\end_layout

\begin_layout Itemize
vs arith mean
\end_layout

\begin_deeper
\begin_layout Itemize
A travels 20mph for 1h then 30mph for 1h, avg speed is arith mean
\end_layout

\begin_layout Itemize
A travels 20mph for 1mi then 30mph for 1mi, avg speed is harmonic mean
\end_layout

\end_deeper
\begin_layout Itemize
F-1 score is harmonic mean of precision & recall
\end_layout

\end_deeper
\begin_layout Itemize
power mean 
\begin_inset Formula $M^{r}\left(\left\{ x_{i}\right\} \right)=\left(\frac{1}{n}\sum_{i}x_{i}^{r}\right)^{\frac{1}{r}}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $r=-1$
\end_inset

 harmonic, 
\begin_inset Formula $r=0$
\end_inset

 geom, 
\begin_inset Formula $r=1$
\end_inset

 arith, 
\begin_inset Formula $r=2$
\end_inset

 quadratic (root mean square), 
\begin_inset Formula $r=-\infty$
\end_inset

 min, 
\begin_inset Formula $r=\infty$
\end_inset

 max
\end_layout

\end_deeper
\begin_layout Itemize
Stirling's approx: 
\begin_inset Formula $\ln n!=n\ln n-n+O\left(\log n\right)$
\end_inset

 where last term is 
\begin_inset Formula $\frac{1}{2}\ln\left(2\pi n\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
Or, 
\begin_inset Formula $\lim_{n\rightarrow\infty}\frac{n!}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}=1$
\end_inset

 or 
\begin_inset Formula $n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}$
\end_inset


\end_layout

\end_deeper
\begin_layout Section
Information Theory
\end_layout

\begin_layout Itemize
surprisal: 
\begin_inset Formula $-\log P\left(x\right)=\log\frac{1}{P\left(x\right)}$
\end_inset

; in bits; additive; used in entropy, KLIC, etc.
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $P\left(x\right)=\frac{1}{n}\implies-\log P\left(x\right)=n$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
entropy 
\begin_inset Formula $H\left(X\right)=\E\left[I\left(X\right)\right]=-\sum_{x}p\left(x\right)\log p\left(x\right)\ge0$
\end_inset

 (expected 
\emph on
information content
\emph default
)
\end_layout

\begin_deeper
\begin_layout Itemize
lower prob events have higher information content
\end_layout

\begin_layout Itemize
measured in bits
\end_layout

\end_deeper
\begin_layout Itemize
mutual information 
\begin_inset Formula $I\left(X;Y\right)=\sum_{y}\sum_{x}p_{X,Y}\left(x,y\right)\log\frac{p_{X,Y}\left(x,y\right)}{p_{X}\left(x\right)p_{Y}\left(y\right)}\ge0$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
self-information is entropy: 
\begin_inset Formula $I\left(X;X\right)=H\left(X\right)$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $I\left(X;Y\right)=H\left(X\right)-H\left(X\mid Y\right)=H\left(Y\right)-H\left(Y\mid X\right)=H\left(X\right)+H\left(Y\right)-H\left(X,Y\right)=H\left(X,Y\right)-H\left(X\mid Y\right)-H\left(Y\mid X\right)$
\end_inset


\end_layout

\begin_layout Itemize
symmetric uncertainy 
\begin_inset Formula $U\left(X,Y\right)=2\frac{I\left(X;Y\right)}{H\left(X\right)+H\left(Y\right)}\in\left[0,1\right]$
\end_inset


\end_layout

\begin_layout Itemize
relationship to correlation
\end_layout

\begin_deeper
\begin_layout Itemize
MI measures general dependence, correlation measures linear dependence;
 MI is better for measuring dependence
\end_layout

\begin_layout Itemize
MI applicable to symbolic sequences; correlation applicable only to numerical
 sequences; but MI must estimate continuous distributions
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=D065413DAA29F4C500219B2822
1E904A?doi=10.1.1.15.672&rep=rep1&type=pdf
\end_layout

\end_inset


\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
Kullback–Leibler divergence aka KLIC: non-symmetric measure of difference
 btwn dists 
\begin_inset Formula $P,Q$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
expected # extra bits to code samples from 
\begin_inset Formula $P$
\end_inset

 when using code based on 
\begin_inset Formula $Q$
\end_inset

 rather than on 
\begin_inset Formula $P$
\end_inset


\end_layout

\begin_layout Itemize
alt intuition: avg likelihood of data distributed as 
\begin_inset Formula $P$
\end_inset

 given 
\begin_inset Formula $Q$
\end_inset

 as model: 
\begin_inset Formula $D_{\text{KL}}\left(P\|Q\right)=-\log\bar{L}$
\end_inset

 where 
\begin_inset Formula $L=\Pr\left[X\sim P\mid Q\right]$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $D_{\mbox{KL}}\left(P\parallel Q\right)=\sum_{i}P\left(i\right)\log\frac{P\left(i\right)}{Q\left(i\right)}=\sum_{i}P\left(i\right)\left(\log Q\left(i\right)-\log P\left(i\right)\right)$
\end_inset

; integral for continuous
\end_layout

\begin_layout Itemize
\begin_inset Formula $D_{\mbox{KL}}\ge0$
\end_inset

; 
\begin_inset Formula $D_{\mbox{KL}}=0$
\end_inset

 for 
\begin_inset Formula $P=Q$
\end_inset

; asymmetric
\end_layout

\begin_layout Itemize
mutual information 
\begin_inset Formula $I\left(X;Y\right)=D_{\text{KL}}\left(\Pr\left[X,Y\right]\|\Pr\left[X\right]\Pr\left[Y\right]\right)$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www.snl.salk.edu/~shlens/kl.pdf
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
normalized compression distance (NCD): 
\begin_inset Formula $NCD\left(x,y\right)=\frac{C\left(xy\right)-\min\left\{ C\left(x\right),C\left(y\right)\right\} }{\max\left\{ C\left(x\right),C\left(y\right)\right\} }$
\end_inset


\end_layout

\begin_layout Section
Finance
\end_layout

\begin_layout Itemize
rate of return (ROR) aka return on investment (ROI) aka return
\end_layout

\begin_deeper
\begin_layout Itemize
let 
\begin_inset Formula $V_{f}$
\end_inset

 be final value, 
\begin_inset Formula $V_{i}$
\end_inset

 be initial value
\end_layout

\begin_layout Itemize
ratio: 
\begin_inset Formula $r=\frac{V_{f}}{V_{i}}$
\end_inset


\end_layout

\begin_layout Itemize
arithmetic return aka yield: 
\begin_inset Formula $r_{\text{arith}}=\frac{V_{f}-V_{i}}{V_{i}}=r-1$
\end_inset


\end_layout

\begin_layout Itemize
logarithmic/continuous compound return: 
\begin_inset Formula $r_{\log}=\ln\frac{V_{f}}{V_{i}}=\ln\left(1+r\right)$
\end_inset


\end_layout

\begin_layout Itemize
compound annual growth rate (CAGR): 
\begin_inset Formula $\left(\frac{V_{f}}{V_{i}}\right)^{\frac{1}{n}}-1$
\end_inset

 where 
\begin_inset Formula $n$
\end_inset

 is # years
\end_layout

\begin_layout Itemize
annual percentage rate (APR)
\end_layout

\end_deeper
\begin_layout Section
Signal Processing
\end_layout

\begin_layout Itemize
DFT: 
\begin_inset Formula $X_{k}=\sum_{n=0}^{N-1}x_{n}\exp\left(-\frac{2\pi i}{N}kn\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
IDFT: 
\begin_inset Formula $X_{k}=\frac{1}{N}\sum_{n=0}^{N-1}x_{n}\exp\left(i2\pi k\frac{n}{N}\right)$
\end_inset

 (normalized, changed exp sign)
\end_layout

\begin_layout Itemize
interesting presentation: strength of freq 
\begin_inset Formula $k$
\end_inset

 is distance from origin of the midpoint of your signal's points as the
 signal are spun around a circle 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://altdevblogaday.org/2011/05/17/understanding-the-fourier-transform/
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
IIR, FIR: TODO
\end_layout

\begin_layout Section
Probability
\end_layout

\begin_layout Subsection
Distributions
\end_layout

\begin_layout Itemize
Binomial: # successes in 
\begin_inset Formula $n$
\end_inset

 Bernoulli trials each with success prob 
\begin_inset Formula $p$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\Pr\left[X=k\right]={n \choose k}p^{k}\left(1-p\right)^{n-k}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\E\left[X\right]=np$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X\right]=np\left(1-p\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Geometric: # trials until Bernoulli success with prob 
\begin_inset Formula $p$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\Pr\left[X=k\right]=\left(1-p\right)^{k-1}p$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\E\left[X\right]=\frac{1}{p}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X\right]=\frac{1-p}{p^{2}}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Hypergeom: # successes in 
\begin_inset Formula $n$
\end_inset

 draws from population of 
\begin_inset Formula $N$
\end_inset

 containing 
\begin_inset Formula $m$
\end_inset

 successes
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\Pr\left[X=k\right]=\frac{{m \choose k}{N-m \choose n-k}}{{N \choose m}}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\E\left[X\right]=n\frac{m}{N}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X\right]=n\frac{m}{N}\frac{\left(N-m\right)}{N}\frac{N-n}{N-1}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Negative binomial: # successes in 
\begin_inset Formula $n$
\end_inset

 Bernoulli trials before 
\begin_inset Formula $r$
\end_inset

 failures (generalization of geom)
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\Pr\left[X=k\right]={k+r-1 \choose k}\left(1-p\right)^{r}p^{k}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\E\left[X\right]=\frac{pr}{1-p}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X\right]=\frac{pr}{\left(1-p\right)^{2}}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Poisson: # arrivals in sliver of time (infinite-granularity binomial) assuming
 mean 
\begin_inset Formula $\lambda$
\end_inset

 arrival rate
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\Pr\left[X=k\right]=\frac{\lambda^{k}}{k!}e^{-\lambda}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\E\left[X\right]=\lambda$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X\right]=\lambda$
\end_inset


\end_layout

\begin_layout Itemize
Simple interesting proof from binomial
\end_layout

\end_deeper
\begin_layout Itemize
Normal: mean 
\begin_inset Formula $\mu$
\end_inset

, standard deviation 
\begin_inset Formula $\sigma$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $f\left(x\right)=\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp\left(-\frac{\left(x-\mu\right)^{2}}{2\sigma^{2}}\right)=\dots\exp\left(-\frac{Z^{2}}{2}\right)$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\E\left[X\right]=\mu$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X\right]=\sigma^{2}$
\end_inset


\end_layout

\begin_layout Itemize
Empirical rule: z-scores of 1/2/3 span 68%/95%/99.7%
\end_layout

\begin_layout Itemize
Is its own Fourier transform
\end_layout

\end_deeper
\begin_layout Itemize
Beta: density shape over 
\begin_inset Formula $\left(0,1\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
uniform dist is a beta dist
\end_layout

\begin_layout Itemize
params 
\begin_inset Formula $a,b$
\end_inset

 s.t.
 
\begin_inset Formula $\text{beta}\left[a,b\right]\left(\theta\right)=\alpha\theta^{a-1}\left(1-\theta\right)^{b-1}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $E\left[X\right]=\frac{a}{a+b}$
\end_inset

: higher 
\begin_inset Formula $a$
\end_inset

 suggests 
\begin_inset Formula $\Theta$
\end_inset

 closer to 1 than 0
\end_layout

\begin_layout Itemize
conjugate prior for Bernoulli/binomial dists
\end_layout

\end_deeper
\begin_layout Itemize
Exponential: time btwn Poisson process events
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $f\left(x\right)=\begin{cases}
\lambda e^{-\lambda x}, & x\ge0\\
0, & x<0
\end{cases}$
\end_inset

; 
\begin_inset Formula $\Pr\left[X<x\right]=\begin{cases}
1-e^{-\lambda x}, & x\ge0\\
0, & x<0
\end{cases}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\E\left[X\right]=\frac{1}{\lambda}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X\right]=\frac{1}{\lambda^{2}}$
\end_inset


\end_layout

\begin_layout Itemize
memoryless: 
\begin_inset Formula $\Pr\left[X>s\mid X>t\right]=\Pr\left[X>s-t\right]$
\end_inset

 / constant event rate 
\begin_inset Formula $\lambda$
\end_inset

 / constant hazard 
\begin_inset Formula $\lambda$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Gamma: scale 
\begin_inset Formula $\theta$
\end_inset

 and shape 
\begin_inset Formula $k$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
models waiting times: sum of 
\begin_inset Formula $k$
\end_inset

 indep exponentially distributed RVs, each with mean 
\begin_inset Formula $\theta$
\end_inset


\end_layout

\begin_layout Itemize
also the sample variance of normal data
\end_layout

\begin_layout Itemize
conjugate prior for many dists TODO
\end_layout

\end_deeper
\begin_layout Itemize
Student's t-distribution: a more spread-out normal distribution
\end_layout

\begin_deeper
\begin_layout Itemize
for when sample size is small, population SD unknown
\end_layout

\begin_layout Itemize
converges to normal as DF (corresponds to sample size) increases
\end_layout

\end_deeper
\begin_layout Itemize
Chi-square, chi distributions
\end_layout

\begin_deeper
\begin_layout Itemize
chi-square: sum of squares of 
\begin_inset Formula $k$
\end_inset

 normal RVs 
\begin_inset Formula $\sum_{i}\left(\frac{X_{i}-\mu_{i}}{\sigma_{i}}\right)^{2}$
\end_inset


\end_layout

\begin_layout Itemize
chi: length of vector of 
\begin_inset Formula $k$
\end_inset

 normal components 
\begin_inset Formula $\sqrt{\sum_{i}\left(\frac{X_{i}-\mu_{i}}{\sigma_{i}}\right)^{2}}$
\end_inset


\end_layout

\end_deeper
\begin_layout Subsection
Conjugate prior relationships
\end_layout

\begin_layout Itemize
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="3">
<features tabularvalignment="middle">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Likelihood 
\begin_inset Formula $\Pr\left[x\mid\theta\right]$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Conjugate prior 
\begin_inset Formula $\Pr\left[\theta\right]$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Posterior 
\begin_inset Formula $\Pr\left[\theta\mid x\right]$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Gaussian
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Gaussian
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Gaussian
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Binomial
\begin_inset Formula $\left(N,\theta\right)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Beta
\begin_inset Formula $\left(r,s\right)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Beta
\begin_inset Formula $\left(r+n,s+N-n\right)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Poisson
\begin_inset Formula $\left(\theta\right)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Gamma
\begin_inset Formula $\left(r,s\right)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Gamma
\begin_inset Formula $\left(r+n,s+1\right)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Multinomial
\begin_inset Formula $\left(\theta_{1},\dots,\theta_{k}\right)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Dirichlet
\begin_inset Formula $\left(\alpha_{1},\dots,\alpha_{k}\right)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Dirichlet
\begin_inset Formula $\left(\alpha_{1}+n_{1},\dots,\alpha_{k}+n_{k}\right)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Subsection
General definitions and properties
\end_layout

\begin_layout Itemize
Union bound aka Boole's inequality: 
\begin_inset Formula $\Pr\left[A\cup B\right]\le\Pr\left[A\right]+\Pr\left[B\right]$
\end_inset


\end_layout

\begin_layout Itemize
Bonferroni's inequality: 
\begin_inset Formula $\Pr\left[A\cap B\right]\ge\Pr\left[A\right]+\Pr\left[B\right]-1$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Pr\left[A\mid B\right]>\Pr\left[A\right]\iff\Pr\left[B\mid A\right]>\Pr\left[B\right]$
\end_inset


\end_layout

\begin_layout Itemize
Linearity: 
\begin_inset Formula $\E\left[aX+bY\right]=a\E\left[X\right]+b\E\left[Y\right]$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\E\left[X|Y=y\right]=\sum_{x}x\cdot\Pr\left[X=x|Y=y\right]$
\end_inset


\end_layout

\begin_layout Itemize
Iterated: 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $\E\left[E\left[X|Y\right]\right]=\E\left[X\right]$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X\right]=\E\left[\left(X-\mu\right)^{2}\right]=\E\left[X^{2}\right]-\left(\E\left[X\right]\right)^{2}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[aX+b\right]=\Var\left[aX\right]=a^{2}\Var\left[X\right]$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[aX+bY\right]=a^{2}\Var\left[X\right]+b^{2}\Var\left[Y\right]+2ab\Cov\left[X,Y\right]$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var\left[X+Y\right]=\Var\left[X\right]+\Var\left[Y\right]$
\end_inset

 if 
\begin_inset Formula $X,Y$
\end_inset

 indep/uncorrelated
\end_layout

\begin_layout Itemize
Pearson's product-moment coefficient is a 
\begin_inset Quotes eld
\end_inset

normalized
\begin_inset Quotes erd
\end_inset

 covariance: 
\begin_inset Formula $\rho_{X,Y}=\frac{\Cov\left[X,Y\right]}{\sigma_{X}\sigma_{Y}}\in\left[-1,1\right]$
\end_inset


\end_layout

\begin_layout Itemize
Law of total variance: 
\begin_inset Formula $\Var\left[X\right]=\E\left[\Var\left[X\mid Y\right]\right]+\Var\left[\E\left[X\mid Y\right]\right]$
\end_inset

 (unexplained and explained components)
\end_layout

\begin_layout Itemize

\emph on
coefficient of variation
\emph default
 aka 
\emph on
unitized risk
\emph default
 aka 
\emph on
variation coefficient
\emph default
: 
\begin_inset Formula $c=\frac{\sigma}{\left|\mu\right|}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
normalized measure of dispersion of a distribution
\end_layout

\end_deeper
\begin_layout Itemize
signal to noise ratio (SNR): 
\begin_inset Formula $\frac{\mu}{\sigma}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
reciprocal of coefficient of variation; only sensical for positive variables
\end_layout

\end_deeper
\begin_layout Itemize
Markov's inequality: 
\begin_inset Formula $\Pr\left[f\left(X\right)\ge t\right]\le\E\left[f\left(X\right)\right]/t$
\end_inset

, for any non-neg function 
\begin_inset Formula $f$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
corollary: Chebyshev's inequality, 
\begin_inset Formula $\Pr\left[\left|X-\E\left[X\right]\right|\ge a\right]\le\frac{\Var\left[X\right]}{a^{2}}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Hoeffding's inequality: upper bound on prob that sum of RVs deviates from
 expected value
\end_layout

\begin_deeper
\begin_layout Itemize
for Bernoullis (important special case): 
\begin_inset Formula $\Pr\left[\sum_{i}X_{i}\le\left(p-\epsilon\right)n\right]\le\E\left[-2\epsilon^{2}n\right]$
\end_inset

 where 
\begin_inset Formula $X_{i}\sim\mbox{Bernoulli}\left(p\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Section
Algorithms
\end_layout

\begin_layout Subsection
LSH
\end_layout

\begin_layout Itemize
usually use shingling
\end_layout

\begin_layout Itemize
minhash: for clustering sets by similarity
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $h_{\min}\left(x\right)=\min_{x\in X}h\left(x\right)$
\end_inset


\end_layout

\begin_layout Itemize
for two sets of numbers 
\begin_inset Formula $A,B$
\end_inset

, 
\begin_inset Formula $\Pr\left[\min\left(A\right)=\min\left(B\right)\right]=J\left(A,B\right)=\frac{\left|A\cap B\right|}{\left|A\cup B\right|}$
\end_inset


\end_layout

\begin_layout Itemize
with 
\begin_inset Formula $k$
\end_inset

 hash fns:
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\Pr\left[\bigwedge_{i=1}^{k}h_{\min}^{\left(i\right)}\left(A\right)=h_{\min}^{\left(i\right)}\left(B\right)\right]=\left(\frac{\left|A\cap B\right|}{\left|A\cup B\right|}\right)^{k}$
\end_inset

 (low false positives)
\end_layout

\begin_layout Itemize
\begin_inset Formula $\Pr\left[\bigvee_{i=1}^{k}h_{\min}^{\left(i\right)}\left(A\right)=h_{\min}^{\left(i\right)}\left(B\right)\right]=1-\left(1-\frac{\left|A\cap B\right|}{\left|A\cup B\right|}\right)^{k}$
\end_inset

 (low false negatives)
\end_layout

\begin_layout Itemize
estimate 
\begin_inset Formula $J\left(A,B\right)$
\end_inset

 as ratio of matching hash fns
\end_layout

\end_deeper
\begin_layout Itemize
with 
\begin_inset Formula $k$
\end_inset

 smallest hashes:
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\Pr\left[\mbox{all match}\right]=\frac{{\left|A\cap B\right| \choose n}}{{\left|A\cup B\right| \choose n}}\approx\left(\frac{\left|A\cap B\right|}{\left|A\cup B\right|}\right)^{n}$
\end_inset

 for 
\begin_inset Formula $n\ll\left|A\cap B\right|$
\end_inset


\end_layout

\begin_layout Itemize
estimate 
\begin_inset Formula $J\left(A,B\right)$
\end_inset

 as ratio of matching hashes
\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
simhash: similar documents have low Hamming distance between their simhashes
 (Moses Charikar, STOC02)
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $V=\left[0\right]\times64$
\end_inset

 for 64-bit simhash
\end_layout

\begin_layout Itemize
for each item, if bit 
\begin_inset Formula $i$
\end_inset

 of 
\begin_inset Formula $h\left(x\right)$
\end_inset

 set, increment 
\begin_inset Formula $V\left[i\right]$
\end_inset

, else decrement 
\begin_inset Formula $V\left[i\right]$
\end_inset


\end_layout

\begin_layout Itemize
bit 
\begin_inset Formula $i$
\end_inset

 of simhash is 1 if 
\begin_inset Formula $V\left[i\right]>0$
\end_inset

 else 0
\end_layout

\begin_layout Itemize
patented by Google
\end_layout

\end_deeper
\begin_layout Section
Statistics
\end_layout

\begin_layout Subsection
Basics
\end_layout

\begin_layout Itemize

\emph on
coefficient of variation (CV)
\emph default
 aka 
\emph on
unitized risk
\emph default
: 
\begin_inset Formula $\frac{\sigma}{\mu}$
\end_inset

 (to scale/normalize SDs)
\end_layout

\begin_layout Itemize

\emph on
(Pearson's) kurtosis
\emph default
: fourth standardized moment: 
\begin_inset Formula $\frac{\mu_{4}}{\sigma^{4}}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
measure of peakedness, but it's argued this really measures heavy tails
\end_layout

\end_deeper
\begin_layout Subsection
Fisherian tests TODO
\end_layout

\begin_layout Itemize
z-test/z-statistic: approximations are OK when 
\begin_inset Formula $n>30$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
one-sample: 
\begin_inset Formula $z=\frac{\bar{x}-\mu_{\bar{x}}}{\sigma_{\bar{x}}},\sigma_{\bar{x}}=\frac{\sigma}{\sqrt{n}}\approx\frac{S}{\sqrt{n}}$
\end_inset


\end_layout

\begin_layout Itemize
two-sample: 
\begin_inset Formula $z=\frac{\left(\bar{X}-\bar{Y}\right)-\left(\mu_{\bar{X}-\bar{Y}}=0\right)}{\sigma_{\bar{X}-\bar{Y}}=\sqrt{\frac{\sigma_{X}^{2}}{n}+\frac{\sigma_{Y}^{2}}{m}}\approx\sqrt{\frac{S_{X}^{2}}{n}+\frac{S_{Y}^{2}}{m}}}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
t-test/t-statistic: same as z-test but refer to student's t-distribution;
 use when 
\begin_inset Formula $n\le30$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
one-sample: 
\begin_inset Formula $t=\frac{\bar{x}-\mu_{\bar{x}}}{S/\sqrt{n}}$
\end_inset

 (same quantity as in z-test), DF is 
\begin_inset Formula $n-1$
\end_inset


\end_layout

\begin_layout Itemize
two-sample: 
\begin_inset Formula $t=\frac{\bar{X}-\bar{Y}-\left(\mu_{\bar{X}-\bar{Y}}=0\right)}{S_{\bar{X}-\bar{Y}}=\sqrt{\frac{S_{X}^{2}}{n}+\frac{S_{Y}^{2}}{m}}}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
chi-square test: 
\begin_inset Formula $X^{2}=\sum_{ij}\frac{\left(O_{ij}-E_{ij}\right)^{2}}{E_{ij}}=\sum_{i}\left(\frac{X_{i}-\mu_{i}}{\sigma_{i}}\right)^{2}$
\end_inset

, where 
\begin_inset Formula $ij$
\end_inset

 enumerate cells in contingency table
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $E_{ij}$
\end_inset

 are computed from marginal (global) frequencies of table
\end_layout

\begin_layout Itemize
dof is 
\begin_inset Formula $n-1$
\end_inset

 where 
\begin_inset Formula $n$
\end_inset

 is number of cells
\end_layout

\begin_layout Itemize
compare freqs of a sample against theoretical dist
\end_layout

\begin_layout Itemize
asymptotically approaches 
\begin_inset Formula $\chi^{2}$
\end_inset

 distribution
\end_layout

\begin_layout Itemize
uses normal approximation of multinomial distribution
\end_layout

\end_deeper
\begin_layout Itemize
multinomial test
\end_layout

\begin_layout Itemize
Fisher's exact test
\end_layout

\begin_layout Subsection
Neymann-Pearson tests
\end_layout

\begin_layout Itemize
Wald test: reject iff 
\begin_inset Formula $2\cdot\frac{\left|\hat{\theta}-\theta_{0}\right|}{\sigma}>z_{\alpha}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
depends on representation of 
\begin_inset Formula $\theta$
\end_inset

 (eg log-scaling); LR works with any monotonic transformation
\end_layout

\begin_layout Itemize
uses 2 approximations (know standard error, dist is 
\begin_inset Formula $\chi^{2}$
\end_inset

); LR only assumes dist is 
\begin_inset Formula $\chi^{2}$
\end_inset

 (if using that test)
\end_layout

\begin_layout Itemize
only deals with scalars; LR can deal with vector params
\end_layout

\end_deeper
\begin_layout Itemize
likelihood ratio test: for comparing fit of 2 models/hyps, where null is
 special case of the alternative
\end_layout

\begin_deeper
\begin_layout Itemize
model with more params will be better fit, but is it significantly better?
\end_layout

\begin_layout Itemize

\emph on
likelihood ratio test statistic
\emph default
 for simple hyps 
\begin_inset Formula $\theta_{0},\theta_{1}$
\end_inset

: 
\begin_inset Formula $\Lambda\left(x\right)=\frac{L\left(\theta_{0}\mid x\right)}{L\left(\theta_{1}\mid x\right)}$
\end_inset


\end_layout

\begin_layout Itemize

\emph on
log-likelihood ratio test statistic: 
\emph default

\begin_inset Formula $D=-2\ln\Lambda\left(x\right)=-2\ln\left(\frac{L\left(\theta_{0}\mid x\right)}{L\left(\theta_{1}\mid x\right)}\right)=-2\ln\left(L\left(\theta_{0}\mid x\right)\right)+2\ln\left(L\left(\theta_{1}\mid x\right)\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
approx.
 distributed as 
\begin_inset Formula $\chi^{2}$
\end_inset

 with dof 
\begin_inset Formula $df_{1}-df_{0}$
\end_inset


\end_layout

\begin_layout Itemize
G-test is more accurate than 
\begin_inset Formula $\chi^{2}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
for composite hyps: 
\begin_inset Formula $\Lambda\left(x\right)=\frac{\sup\left\{ L\left(\theta\mid x\right):\theta\in\Theta_{0}\right\} }{\sup\left\{ L\left(\theta\mid x\right):\theta\in\Theta\right\} }$
\end_inset

 (compare MLEs)
\end_layout

\begin_layout Itemize
Z-test, F-test, chi-square, G-test are tests for nested models and can be
 phrased as (approximations of) log-likelihood ratios
\end_layout

\end_deeper
\begin_layout Itemize
F-test: compare models; ANOVA; TODO
\end_layout

\begin_layout Itemize
G-test: for log-likelihood ratio tests; 
\begin_inset Formula $G=2\sum_{ij}O_{ij}\ln\left(\frac{O_{ij}}{E_{ij}}\right)$
\end_inset

 TODO
\end_layout

\begin_deeper
\begin_layout Itemize
chi-square tests are approximations; useful before computers
\end_layout

\begin_layout Itemize
G-test much better where for any contingency cell 
\begin_inset Formula $\left|O_{i}-E_{i}\right|>E_{i}$
\end_inset


\end_layout

\begin_layout Itemize
for small samples, use multinomial test, Fisher's exact test, or even Bayesian
 hyp selection
\end_layout

\end_deeper
\begin_layout Itemize
Bayes factors: vs likelihood ratio tests
\end_layout

\begin_layout Subsection
Hypothesis testing
\end_layout

\begin_layout Itemize
effect size: basically, how big a difference; fluffy notion/many formulations
\end_layout

\begin_deeper
\begin_layout Itemize
absolute: e.g., 
\begin_inset Quotes eld
\end_inset

difference between groups is 30lb
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
standardized difference of means: e.g., 
\begin_inset Formula $\frac{\bar{X}-\bar{Y}}{S}$
\end_inset

, where 
\begin_inset Formula $S$
\end_inset

 is SD of either or both groups
\end_layout

\end_deeper
\begin_layout Itemize
problem: can get significance (low 
\begin_inset Formula $p$
\end_inset

-value) with big effect and small sample or big sample and small effect
\end_layout

\begin_deeper
\begin_layout Itemize
hence, report effect/sample size with 
\begin_inset Formula $p$
\end_inset

-value
\end_layout

\end_deeper
\begin_layout Itemize
power analysis: prob of rejecting false 
\begin_inset Formula $H_{0}$
\end_inset

 (not making a type II error, false neg)
\end_layout

\begin_deeper
\begin_layout Itemize

\emph on
power
\emph default
 aka 
\emph on
sensitivity
\emph default
 is 
\begin_inset Formula $1-\beta$
\end_inset

 where 
\begin_inset Formula $\beta$
\end_inset

 is 
\emph on
false negative rate
\end_layout

\begin_layout Itemize
can use to find min sample size to likely detect given effect size, or min
 effect size likely detected by given sample size
\end_layout

\begin_layout Itemize
e.g., more powerful experiments may have more subjects
\end_layout

\end_deeper
\begin_layout Subsection
Unsorted
\end_layout

\begin_layout Itemize
kalman filter: TODO understand
\end_layout

\begin_deeper
\begin_layout Itemize
untrusted predictions, untrusted measurements; combine them
\end_layout

\begin_layout Itemize
optimal estimate 
\begin_inset Formula 
\[
\hat{y}=\text{prediction}+\left(\text{Kalman gain}\right)\left(\text{measurement}-\text{prediction}\right)
\]

\end_inset


\end_layout

\begin_layout Itemize
predict using previous data, measure, fuse/correct prediction and measurement
\end_layout

\begin_layout Itemize
usually no control signals 
\begin_inset Formula $\vec{u}_{k}$
\end_inset


\end_layout

\begin_layout Itemize
http://www.swarthmore.edu/NatSci/echeeve1/Ref/Kalman/ScalarKalman.html
\end_layout

\end_deeper
\begin_layout Itemize
Mahalanobis distance: similarity of a sample to a distribution
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $D_{M}=\sqrt{\transpose{\left(x-\mu\right)}S^{-1}\left(x-\mu\right)}$
\end_inset

 where 
\begin_inset Formula $x$
\end_inset

 is new sample, 
\begin_inset Formula $\mu$
\end_inset

 is dist mean, 
\begin_inset Formula $S$
\end_inset

 is covar matrix
\end_layout

\begin_layout Itemize
same as normalized Euclidian dist if 
\begin_inset Formula $S=I$
\end_inset

: 
\begin_inset Formula $D_{M}=\sqrt{\sum_{i}\frac{\left(x_{i}-\mu_{i}\right)^{2}}{s_{i}^{2}}}$
\end_inset


\end_layout

\end_deeper
\begin_layout Subsection
Smoothing
\end_layout

\begin_layout Itemize

\emph on
additive smoothing
\emph default
 aka 
\emph on
Laplace smoothing
\emph default
: 
\begin_inset Formula $\hat{\theta_{i}}=\frac{n_{i}+k}{n+dk}$
\end_inset

, 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $i=1,\dots,d$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
called 
\begin_inset Quotes eld
\end_inset

rule of succession
\begin_inset Quotes erd
\end_inset

 for 
\begin_inset Formula $k=1$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize

\emph on
Good-Turing estimation
\emph default
: complex
\end_layout

\begin_layout Subsection
Estimation
\end_layout

\begin_layout Itemize
90% confidence interval: in repeated samplings, the computed intervals 
\begin_inset Formula $I\left(X\right)$
\end_inset

 would contain the true param 90% of the time (0.1 miss rate); 
\begin_inset Formula $\Pr\left[\hat{\theta}\in I\left(X\right)\right]=.9$
\end_inset

 (
\begin_inset Formula $\theta$
\end_inset

 is const, 
\begin_inset Formula $I\left(X\right)$
\end_inset

 is RV)
\end_layout

\begin_layout Itemize
90% credible interval 
\begin_inset Formula $C\left(X\right)$
\end_inset

: 
\begin_inset Formula $\Pr\left[\theta\in C\left(X\right)\right]=.9$
\end_inset

 (
\begin_inset Formula $\theta,C\left(X\right)$
\end_inset

 are RV); 
\begin_inset Quotes eld
\end_inset

Bayesian confidence interval
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
statistic: any function of data 
\begin_inset Formula $\delta\left(X\right)$
\end_inset


\end_layout

\begin_layout Itemize
estimator: any statistic used to estimate an (unknown) param 
\begin_inset Formula $\theta$
\end_inset

; usu denoted 
\begin_inset Formula $\hat{\theta}=\delta\left(X\right)$
\end_inset


\end_layout

\begin_layout Itemize
bias: 
\begin_inset Formula $\E\left[\hat{\theta}-\theta\right]=\E\left[\hat{\theta}\right]-\theta$
\end_inset

 (
\emph on
unbiased 
\emph default
if 0 as 
\begin_inset Formula $n\rightarrow\infty$
\end_inset

)
\end_layout

\begin_layout Itemize
variance: 
\begin_inset Formula $\Var\left[\hat{\theta}-\theta\right]$
\end_inset


\end_layout

\begin_layout Itemize
unbiased estimator: converges to true param over repeatedly sampling
\end_layout

\begin_deeper
\begin_layout Itemize
e.g.: sample variance
\end_layout

\begin_deeper
\begin_layout Itemize
unbiased sample variance (
\begin_inset Formula $\E\left[s^{2}\right]=\sigma^{2}$
\end_inset

) is 
\begin_inset Formula $s^{2}=\frac{1}{n-1}\sum_{i}\left(X_{i}-\bar{X}\right)^{2}$
\end_inset

 (Bessel's correction)
\end_layout

\begin_layout Itemize
biased is 
\begin_inset Formula $s_{n}^{2}=\frac{1}{n}\sum_{i}\left(X_{i}-\bar{X}\right)^{2}$
\end_inset


\end_layout

\begin_layout Itemize
note: 
\begin_inset Formula $s$
\end_inset

 is 
\emph on
not
\emph default
 unbiased for SD
\end_layout

\end_deeper
\begin_layout Itemize
can be terrible; they may average to true value but individual estimates
 may be ridiculous
\end_layout

\begin_deeper
\begin_layout Itemize
e.g.
 for Poisson 
\begin_inset Formula $X$
\end_inset

, estimator 
\begin_inset Formula $\delta\left(X=x\right)$
\end_inset

 of statistic 
\begin_inset Formula $\Pr\left[X=0\right]^{2}=e^{-2\lambda}=\E\left[\delta\left(X\right)\right]$
\end_inset

 is 
\begin_inset Formula $\left(-1\right)^{x}$
\end_inset

, which is nonsense
\end_layout

\begin_layout Itemize
MLE is 
\begin_inset Formula $e^{-2x}$
\end_inset

, which is always positive and has smaller MSE
\end_layout

\begin_layout Itemize
besides bias, look also at 
\emph on
efficiency
\emph default
, the MSE of individual estimates
\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize

\emph on
consistent
\emph default
: 
\begin_inset Formula $\lim_{n\rightarrow\infty}\delta\left(X_{n}\right)=\theta$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
bias & variance must go to 0
\end_layout

\begin_layout Itemize
biased but consistent estimate of mean: 
\begin_inset Formula $\frac{1}{n}\sum_{i}x_{i}+\frac{1}{n}$
\end_inset


\end_layout

\begin_layout Itemize
unbiased but inconsistent estimate of mean: 
\begin_inset Formula $x_{1}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
maximum likelihood estimation (MLE): 
\begin_inset Formula $\arg\max_{\theta}\Pr\left[X\mid\theta\right]$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
find the peak in the likelihood function
\end_layout

\begin_layout Itemize
Fisher popularized this by showing that typically MLE is unbiased, consistent,
 & asymptotically the lowest variance estimator
\end_layout

\begin_layout Itemize
least squares: in OLS, if errors are normal, then least squares estimate
 is MLE
\end_layout

\begin_layout Itemize
now clear that MLE sometimes bad in practice, and finite sample behavior
 not samp esa asymptotic behavior, leading to Bayesian strategies
\end_layout

\begin_layout Itemize
disregards the uncertainty (
\begin_inset Quotes eld
\end_inset

spread
\begin_inset Quotes erd
\end_inset

 in the likelihood function, i.e.
 
\emph on
Fisher information
\emph default
)
\end_layout

\begin_layout Itemize
property: 
\begin_inset Formula $f\left(\hat{\theta}\right)$
\end_inset

 is MLE of 
\begin_inset Formula $f\left(\theta\right)$
\end_inset

 for any 
\begin_inset Formula $f$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
maximum a posteriori (MAP): 
\begin_inset Formula $\arg\max_{\theta}\left(\Pr\left[\theta\mid X\right]=\Pr\left[X\mid\theta\right]\Pr\left[\theta\right]\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
the Bayesian approach
\end_layout

\begin_layout Itemize
since we have a (posterior) prob dist over 
\begin_inset Formula $\theta$
\end_inset

, can extract whatever we want: mean, median, mode, intervals
\end_layout

\end_deeper
\begin_layout Itemize
Estimation: intervals, consistency, bias, MLE, MAP
\end_layout

\begin_deeper
\begin_layout Itemize
choose the single most probable 
\begin_inset Formula $\theta$
\end_inset

 given 
\begin_inset Formula $X$
\end_inset

 (mode of posterior)
\end_layout

\begin_layout Itemize
note: prediction using MAP is approx to Bayes prediction using all 
\begin_inset Formula $\theta$
\end_inset

 and their probabilities
\end_layout

\begin_layout Itemize
equiv: 
\begin_inset Formula $\arg\min_{\theta}\left(-\log\Pr\left[\theta\mid X\right]=-\log\Pr\left[X\mid\theta\right]-\log\Pr\left[\theta\right]\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $-\log\Pr\left[\theta\right]$
\end_inset

 is bits to describe 
\begin_inset Formula $\theta$
\end_inset

, 
\begin_inset Formula $-\log\Pr\left[X\mid\theta\right]$
\end_inset

 is add'l bits to describe data
\end_layout

\begin_layout Itemize
hence, MAP chooses 
\begin_inset Formula $\theta$
\end_inset

 that provides max compression, or MDL
\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
Bayes estimation: given loss 
\begin_inset Formula $L\left(\theta,\delta\right)$
\end_inset

 (eg sq err), minimize Bayes risk 
\begin_inset Formula $\E\left[L\left(\theta,\delta\right)\right]$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

https://github.com/johnmyleswhite/JAGSExamples/blob/master/slides/
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Exponential smoothing for time series analysis
\end_layout

\begin_layout Itemize

\emph on
exponential moving average (EMA)
\emph default
 aka 
\emph on
exponentially weighted moving average (EWMA)
\emph default
 aka 
\emph on
single exponential smoothing (SES)
\emph default

\begin_inset Formula 
\begin{eqnarray*}
S_{t} & = & \left(1-\alpha\right)\cdot S_{t-1}+\alpha\cdot y_{t-1}\\
S_{2} & = & 1
\end{eqnarray*}

\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
Does not spot trends
\end_layout

\end_deeper
\begin_layout Itemize

\emph on
double exponential moving average (DEMA)
\emph default
 aka 
\emph on
linear exponential smoothing (LES)
\emph default

\begin_inset Formula 
\begin{align*}
S_{t} & = & \alpha y_{t}+\left(1-\alpha\right)\left(S_{t-1}+b_{t-1}\right), & 0\le\alpha\le1\\
b_{t} & = & \gamma\left(S_{t}-S_{t-1}\right)+\left(1-\gamma\right)b_{t-1}, & 0\le\gamma\le1
\end{align*}

\end_inset


\end_layout

\begin_layout Itemize
triple exponential moving average (TEMA) aka 
\emph on
triple exponential smoothing (SES)
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status open

\begin_layout Plain Layout

http://www.itl.nist.gov/div898/handbook/pmc/section4/pmc4.htm
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Applied
\end_layout

\begin_layout Itemize

\emph on
recency, frequency, monetary value (RFM)
\emph default
: simple customer behavior analysis
\end_layout

\begin_deeper
\begin_layout Itemize
segment customers along these 3 axes into discrete bins
\end_layout

\begin_layout Itemize
identify highest-value intersections of bins
\end_layout

\end_deeper
\begin_layout Subsection
Time series
\end_layout

\begin_layout Itemize

\emph on
autoregressive
\emph default
 model: 
\begin_inset Formula $X_{t}=c+\sum_{i=1}^{p}\varphi_{i}X_{t-i}+\varepsilon_{t}$
\end_inset


\end_layout

\begin_layout Itemize
moving avg model: 
\begin_inset Formula $X_{t}=\mu+\varepsilon_{t}+\sum_{i=1}^{q}\theta_{i}\varepsilon_{t-i}$
\end_inset


\end_layout

\begin_layout Itemize

\emph on
autoregressive moving avg (ARMA)
\emph default
 aka 
\emph on
Box-Jenkins
\emph default
 model: 
\begin_inset Formula $X_{t}=\mu+a_{1}X_{t-1}+\dots+a_{k}X_{t-p}+\varepsilon_{t}+b_{1}\varepsilon_{t-1}+\dots+b_{q}\varepsilon_{t-q}$
\end_inset

 where 
\begin_inset Formula $E\left[\varepsilon_{t,}\varepsilon_{s}\right]=0\forall t\ne s$
\end_inset

 and 
\begin_inset Formula $\varepsilon_{t}\sim N\left(0,\sigma^{2}\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
one of most common univariate time series models
\end_layout

\begin_layout Itemize
Kalman filter can calculate exact log-likelihood, but 
\begin_inset Quotes eld
\end_inset

conditional
\begin_inset Quotes erd
\end_inset

 likelihood is easier/more commonly used
\end_layout

\end_deeper
\begin_layout Itemize

\emph on
vector autoregression (VAR)
\emph default
 model: 
\begin_inset Formula $X_{t}=A_{1}X_{t-1}+\dots+A_{p}X_{t-p}+\varepsilon_{t}$
\end_inset

 where each 
\begin_inset Formula $X_{i}$
\end_inset

 is a vector, 
\begin_inset Formula $A_{i}$
\end_inset

 is a matrix, and 
\begin_inset Formula $\varepsilon_{t}\sim N\left(0,\Sigma\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
multivariate time series generalization of univariate AR models
\end_layout

\begin_layout Itemize
widely used, esp.
 in macroecon
\end_layout

\end_deeper
\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www.slideshare.net/wesm/scipy-2011-time-series-analysis-in-python
\end_layout

\end_inset


\end_layout

\begin_layout Section
Time Series
\end_layout

\begin_layout Subsection
Processes
\end_layout

\begin_layout Itemize
second-order stationary process: 
\begin_inset Formula $\mu,\sigma^{2}$
\end_inset

 are time-indep
\end_layout

\begin_layout Itemize

\emph on
hazard rate
\emph default
 at time 
\begin_inset Formula $t$
\end_inset

 event rate at 
\begin_inset Formula $t$
\end_inset

 conditional on survival until 
\begin_inset Formula $t$
\end_inset

; eg bathtub curve; eg constant (in exponential dists)
\end_layout

\begin_layout Subsection
Autocorrelation
\end_layout

\begin_layout Itemize
autocorrelation function (ACF): for second-order stationary process, 
\begin_inset Formula $R\left(\tau\right)=\frac{\E\left[\left(X_{t}-\mu\right)\left(X_{t+\tau}-\mu\right)\right]}{\sigma^{2}}$
\end_inset

 (
\begin_inset Formula $\tau$
\end_inset

 is lag)
\end_layout

\begin_deeper
\begin_layout Itemize
when normalized by mean and variance, called 
\emph on
autocorrelation coefficient
\end_layout

\end_deeper
\begin_layout Itemize
partial ACF (PACF): TODO
\end_layout

\begin_layout Subsection
Models
\end_layout

\begin_layout Itemize
Order-
\begin_inset Formula $q$
\end_inset

 moving avg model MA(
\begin_inset Formula $q$
\end_inset

): 
\begin_inset Formula $X_{t}=\mu+\varepsilon_{t}+\sum_{i=1}^{q}\theta_{i}\varepsilon_{t-i}$
\end_inset


\end_layout

\begin_layout Itemize
Autoregressive model: 
\begin_inset Formula $X_{t}=c+\sum_{i=1}^{p}\varphi_{i}X_{t-i}+\varepsilon_{t}$
\end_inset


\end_layout

\begin_layout Itemize
Autoregressive moving avg (ARMA) aka Box-Jenkins model: 
\begin_inset Formula $X_{t}=c+\varepsilon_{t}+\sum_{i=1}^{p}\varphi_{i}X_{t-i}+\sum_{i=1}^{q}\theta_{i}\varepsilon_{t-i}$
\end_inset


\end_layout

\begin_layout Itemize
Autoregressive integrated moving avg (ARIMA): TODO
\end_layout

\begin_layout Section
Linear Algebra
\end_layout

\begin_layout Itemize

\emph on
Power method 
\emph default
or 
\emph on
power iteration
\emph default
: an eigenvalue algo
\end_layout

\begin_deeper
\begin_layout Itemize
Given matrix 
\begin_inset Formula $A$
\end_inset

, produce scalar 
\begin_inset Formula $\lambda$
\end_inset

 and non-0 vector 
\begin_inset Formula $v$
\end_inset

 (eigenvector) s.t.
 
\begin_inset Formula $Av=\lambda v$
\end_inset


\end_layout

\begin_layout Itemize
Doesn't compute matrix decomposition so suitable for large sparse 
\begin_inset Formula $A$
\end_inset


\end_layout

\begin_layout Itemize
But will only find one eigenvalue (with max val) and may converge slowly
\end_layout

\begin_layout Itemize
Start with random vector 
\begin_inset Formula $b_{0}$
\end_inset

 and iteratively multiple by 
\begin_inset Formula $A$
\end_inset

 and normalize: 
\begin_inset Formula $b_{k+1}=\frac{Ab_{k}}{\norm{Ab_{k}}}$
\end_inset


\end_layout

\begin_layout Itemize
TODO
\end_layout

\end_deeper
\begin_layout Itemize
\begin_inset Formula $a\cdot b=\norm a\norm b\cos\theta$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\norm{a\times b}=\norm a\norm b\sin\theta=\mbox{area of parallelogram with sides \ensuremath{a,b}}$
\end_inset

 (direction given by right hand rule)
\end_layout

\begin_layout Itemize
Cauchy-schwartz inequality: 
\begin_inset Formula $\left|a\cdot b\right|\le\norm a\norm b$
\end_inset


\end_layout

\begin_layout Itemize
triangle inequality: 
\begin_inset Formula $\norm{a+b}\le\norm a+\norm b$
\end_inset


\end_layout

\begin_layout Itemize
reduced row echelon form
\end_layout

\begin_deeper
\begin_layout Itemize
identity means unique solution
\end_layout

\begin_layout Itemize
\begin_inset Formula $\left[\begin{array}{cccc}
1 & 2 & 0 & 3\\
0 & 0 & 1 & -2\\
0 & 0 & 0 & 0
\end{array}\right]$
\end_inset

 with pivot variables 
\begin_inset Formula $x_{1},x_{3}$
\end_inset

 and free vars 
\begin_inset Formula $x_{2},x_{4}$
\end_inset

 has inf solutions
\end_layout

\begin_layout Itemize
\begin_inset Formula $\left[\begin{array}{cccc}
1 & 2 & 0 & 3\\
0 & 0 & 1 & -2\\
0 & 0 & 0 & -4
\end{array}\right]$
\end_inset

 has no solutions (
\begin_inset Formula $0=-4$
\end_inset

)
\end_layout

\end_deeper
\begin_layout Itemize
tensor product aka outer product 
\begin_inset Formula $\vec{a}\otimes\vec{b}=\vec{a}\transpose{\vec{b}}$
\end_inset

 is 
\begin_inset Formula $\left|\vec{a}\right|\times\left|\vec{b}\right|$
\end_inset

 matrix
\end_layout

\begin_layout Itemize
gradient 
\begin_inset Formula $\nabla f=\left[\begin{array}{c}
\frac{\partial f}{\partial x_{1}}\\
\frac{\partial f}{\partial x_{2}}\\
\vdots\\
\frac{\partial f}{\partial x_{n}}
\end{array}\right]$
\end_inset


\end_layout

\begin_layout Itemize
Hessian 
\begin_inset Formula $\nabla^{2}f=\left[\begin{array}{cccc}
\frac{\partial^{2}f}{\partial x_{1}^{2}} & \frac{\partial^{2}f}{\partial x_{1}\partial x_{2}} & \dots & \frac{\partial^{2}f}{\partial x_{1}\partial x_{n}}\\
\frac{\partial^{2}f}{\partial x_{2}\partial x_{1}} & \frac{\partial^{2}f}{\partial x_{2}^{2}} &  & \frac{\partial^{2}f}{\partial x_{2}\partial x_{n}}\\
\vdots &  & \ddots & \vdots\\
\frac{\partial^{2}f}{\partial x_{n}\partial x_{1}} & \frac{\partial^{2}f}{\partial x_{n}\partial x_{2}} & \dots & \frac{\partial^{2}f}{\partial x_{n}^{2}}
\end{array}\right]$
\end_inset

 is Jacobian of gradient
\end_layout

\begin_layout Itemize
Jacobian of function 
\begin_inset Formula $f:\Re^{n}\rightarrow\Re^{m}$
\end_inset

: 
\begin_inset Formula $Jf=\left[\begin{array}{cccc}
\frac{\partial f_{1}}{\partial x_{1}} & \frac{\partial f_{1}}{\partial x_{2}} & \dots & \frac{\partial f_{1}}{\partial x_{n}}\\
\frac{\partial f_{2}}{\partial x_{1}} & \frac{\partial f_{2}}{\partial x_{2}} &  & \frac{\partial f_{2}}{\partial x_{n}}\\
\vdots &  & \ddots & \vdots\\
\frac{\partial f_{m}}{\partial x_{1}} & \frac{\partial f_{m}}{\partial x_{2}} & \dots & \frac{\partial f_{m}}{\partial x_{n}}
\end{array}\right]$
\end_inset


\end_layout

\begin_layout Itemize
graph/Markov chain is 
\emph on
irreducible
\emph default
 iff strongly connected; matrix is 
\emph on
irreducible
\emph default
 iff it's transition matrix of irreducible graph/Markov chain
\end_layout

\begin_layout Subsection
Matrices
\end_layout

\begin_layout Itemize

\emph on
Elementary matrix
\emph default
: matrix that differs from 
\begin_inset Formula $I$
\end_inset

 by one elementary row op
\end_layout

\begin_layout Itemize
\begin_inset Formula $A$
\end_inset

 is 
\emph on
symmetric
\emph default
 iff 
\begin_inset Formula $\transpose A=A$
\end_inset


\end_layout

\begin_layout Itemize
Let 
\begin_inset Formula $A$
\end_inset

 be 
\begin_inset Formula $n\times n$
\end_inset

 over field 
\begin_inset Formula $K$
\end_inset

 (e.g.
 
\begin_inset Formula $\Re$
\end_inset

).
 Then these are equiv:
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $A$
\end_inset

 is invertible
\end_layout

\begin_layout Itemize
\begin_inset Formula $A$
\end_inset

 is nonsingular
\end_layout

\begin_layout Itemize
\begin_inset Formula $A$
\end_inset

 is nondegenerate
\end_layout

\begin_layout Itemize
\begin_inset Formula $A$
\end_inset

 is 
\emph on
row-equiv
\emph default
 to 
\begin_inset Formula $I$
\end_inset

 (can be changed to 
\begin_inset Formula $I$
\end_inset

 using elementary row ops)
\end_layout

\begin_layout Itemize
\begin_inset Formula $A$
\end_inset

 is 
\emph on
col-equiv 
\emph default
to 
\begin_inset Formula $I$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $A$
\end_inset

 has 
\begin_inset Formula $n$
\end_inset

 pivot positions
\end_layout

\begin_layout Itemize
\begin_inset Formula $\det A\ne0$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\text{rank}A=n$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $Ax=0$
\end_inset

 has only one trivial sol 
\begin_inset Formula $x=0$
\end_inset

 (i.e.
 
\begin_inset Formula $\text{Null}A=\left\{ 0\right\} $
\end_inset

)
\end_layout

\begin_layout Itemize
\begin_inset Formula $Ax=b$
\end_inset

 has exactly one sol for each 
\begin_inset Formula $b\in K^{n}$
\end_inset

 (
\begin_inset Formula $x\ne0$
\end_inset

)
\end_layout

\begin_layout Itemize
cols of 
\begin_inset Formula $A$
\end_inset

 are lin indep
\end_layout

\begin_layout Itemize
cols of 
\begin_inset Formula $A$
\end_inset

 span 
\begin_inset Formula $K^{n}$
\end_inset

 (i.e.
 
\begin_inset Formula $\text{Col}A=K^{n}$
\end_inset

)
\end_layout

\begin_layout Itemize
cols of 
\begin_inset Formula $A$
\end_inset

 form a 
\emph on
basis
\emph default
 of 
\begin_inset Formula $K^{n}$
\end_inset


\end_layout

\begin_layout Itemize
the linear transformation mapping 
\begin_inset Formula $x$
\end_inset

 to 
\begin_inset Formula $Ax$
\end_inset

 is a bijection from 
\begin_inset Formula $K^{n}$
\end_inset

 to 
\begin_inset Formula $K^{n}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\transpose A$
\end_inset

 is invertible
\end_layout

\begin_layout Itemize
0 is not an eval of 
\begin_inset Formula $A$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $A$
\end_inset

 can be expressed as product of finitely many 
\emph on
elementary matrices
\end_layout

\end_deeper
\begin_layout Itemize
For any invertible 
\begin_inset Formula $A$
\end_inset

, these hold:
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\left(AB\right)^{-1}=B^{-1}A^{-1}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\left(kA\right)^{-1}=k^{-1}A^{-1}$
\end_inset

 for 
\begin_inset Formula $k\ne0$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\left(\transpose A\right)^{-1}=\transpose{\left(A^{-1}\right)}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\det\left(A^{-1}\right)=\det\left(A\right)^{-1}$
\end_inset


\end_layout

\end_deeper
\begin_layout Subsection
Decomposition
\end_layout

\begin_layout Itemize
Gaussian elim: for solving system of equations
\end_layout

\begin_deeper
\begin_layout Itemize
phase 1, fwd elim: use elementary row ops to get 
\emph on
row echelon form
\emph default
 (pivots move to right as you move down)
\end_layout

\begin_layout Itemize
phase 2, back-subst: solve for unknowns using simplified row echelon form
\end_layout

\end_deeper
\begin_layout Itemize
Gaussian-Jordan elim: extension of Gaussian elim to get 
\emph on
reduced row echelon form
\emph default
 (
\begin_inset Formula $I$
\end_inset

 on left square)
\end_layout

\begin_deeper
\begin_layout Itemize
to invert 
\begin_inset Formula $A$
\end_inset

: 
\begin_inset Formula $\left[AI\right]\Rightarrow\left[IA^{-1}\right]$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
LU: matrix form of Gaussian elim's fwd elim phase
\end_layout

\begin_deeper
\begin_layout Itemize
a square matrix 
\begin_inset Formula $A=LU$
\end_inset

 where 
\begin_inset Formula $L,U$
\end_inset

 are lower/upper triangular matrices
\end_layout

\begin_layout Itemize
efficient; good for 
\begin_inset Quotes eld
\end_inset

good
\begin_inset Quotes erd
\end_inset

 matrices
\end_layout

\begin_layout Itemize
when solving 
\begin_inset Formula $Ax=b$
\end_inset

, faster to reuse 
\begin_inset Formula $LU$
\end_inset

: if know 
\begin_inset Formula $A=LU$
\end_inset

, then can solve 
\begin_inset Formula $LUx=b$
\end_inset

 by solving 
\begin_inset Formula $Ly=b$
\end_inset

 for 
\begin_inset Formula $y$
\end_inset

 then 
\begin_inset Formula $Ux=y$
\end_inset

 for 
\begin_inset Formula $x$
\end_inset

, with each of these done efficiently using fwd-/back-subst
\end_layout

\end_deeper
\begin_layout Itemize
QR: good balance btwn LU and SVD
\end_layout

\begin_deeper
\begin_layout Itemize
any real 
\begin_inset Formula $m\times n$
\end_inset

 matrix 
\begin_inset Formula $A=QR$
\end_inset

 where 
\begin_inset Formula $Q$
\end_inset

 is orthog 
\begin_inset Formula $m\times m$
\end_inset

, 
\begin_inset Formula $R$
\end_inset

 is upper triangular 
\begin_inset Formula $m\times n$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
SVD: very robust
\end_layout

\begin_layout Subsection
HITS
\end_layout

\begin_layout Itemize
\begin_inset Formula $\forall i,\forall k=1,2,3,\dots,$
\end_inset


\begin_inset Formula 
\begin{eqnarray*}
a_{i}^{\left(k\right)} & = & \sum_{j:e_{ji}\in E}h_{j}^{\left(k-1\right)}\\
h_{i}^{\left(k\right)} & = & \sum_{j:e_{ij}\in E}a_{j}^{\left(k\right)}
\end{eqnarray*}

\end_inset

 and 
\begin_inset Formula $a_{i}^{\left(1\right)}=h_{i}^{\left(1\right)}=\frac{1}{n}$
\end_inset

.
\end_layout

\begin_layout Itemize
if 
\begin_inset Formula $\vec{h},\vec{a}$
\end_inset

 are vectors of 
\begin_inset Formula $h_{i},a_{i}$
\end_inset

 and
\series bold
 
\series default

\begin_inset Formula $\vec{L}$
\end_inset

 is adj matrix (
\begin_inset Formula $L_{ij}=\begin{cases}
1 & \text{page \ensuremath{i}links to \ensuremath{j}}\\
0 & \text{otherwise}
\end{cases}$
\end_inset

) then 
\begin_inset Formula 
\begin{eqnarray*}
\vec{a}^{\left(k\right)} & = & \vec{L}^{T}\vec{h}^{\left(k-1\right)}\\
\vec{h}^{\left(k\right)} & = & \vec{L}\vec{a}^{\left(k\right)}
\end{eqnarray*}

\end_inset

 or 
\begin_inset Formula 
\begin{eqnarray*}
\vec{a}^{\left(k\right)} & = & \vec{L}^{T}\vec{L}\vec{a}^{\left(k-1\right)}\\
\vec{h}^{\left(k\right)} & = & \vec{L}\vec{L}^{T}\vec{h}^{\left(k-1\right)}
\end{eqnarray*}

\end_inset

 i.e., power method applied to positive semi-definite matrices 
\begin_inset Formula $\vec{L}\vec{L}^{T}$
\end_inset

 (auth matrix) and 
\begin_inset Formula $\vec{L}^{T}\vec{L}$
\end_inset

 (hub matrix).
\end_layout

\begin_layout Itemize
Thus, HITS amounts to solving for largest eigenvalue 
\begin_inset Formula $\lambda_{1}$
\end_inset

 in 
\begin_inset Formula $\vec{L}^{T}\vec{L}\vec{a}=\lambda_{1}\vec{a}$
\end_inset

 and 
\begin_inset Formula $\vec{L}\vec{L}^{T}\vec{h}=\lambda_{1}\vec{h}$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://meyer.math.ncsu.edu/Meyer/PS_Files/IMAGE.pdf
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
PageRank
\end_layout

\begin_layout Itemize
rank of page 
\begin_inset Formula $i$
\end_inset

 at iteration 
\begin_inset Formula $k$
\end_inset

: 
\begin_inset Formula $r_{i}^{\left(k+1\right)}=\sum_{j\in I_{i}}\frac{r_{j}^{\left(k\right)}}{\left|O_{j}\right|}$
\end_inset

, where 
\begin_inset Formula $I_{i}$
\end_inset

 is pages linking to 
\begin_inset Formula $i$
\end_inset

 and 
\begin_inset Formula $O_{j}$
\end_inset

 is pages 
\begin_inset Formula $j$
\end_inset

 links to
\end_layout

\begin_layout Itemize
start with uniform 
\begin_inset Formula $r_{i}^{\left(0\right)}=\frac{1}{n}\,\forall i$
\end_inset


\end_layout

\begin_layout Itemize
in matrix notation, 
\begin_inset Formula $\transpose{\pi^{\left(k+1\right)}}=\transpose{\pi^{\left(k\right)}}H$
\end_inset

, where 
\begin_inset Formula $H_{ij}=\frac{1}{\left|O_{i}\right|}$
\end_inset


\end_layout

\begin_layout Itemize
problems
\end_layout

\begin_deeper
\begin_layout Itemize
dangling nodes i.e.
 pages w no outlinks (rows of all 0s)
\end_layout

\begin_deeper
\begin_layout Itemize
replace rows with 
\begin_inset Formula $\vec{u}$
\end_inset

 of all 
\begin_inset Formula $\frac{1}{n}$
\end_inset

; call resulting matrix 
\begin_inset Formula $S$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
graph may not be strongly connected
\end_layout

\begin_deeper
\begin_layout Itemize
replace 
\begin_inset Formula $S$
\end_inset

 with 
\begin_inset Formula $G=\alpha S+\left(1-\alpha\right)E$
\end_inset

 where 
\begin_inset Formula $E$
\end_inset

 is 
\emph on
teleportation matrix
\emph default
 where all rows are 
\begin_inset Formula $\vec{u}$
\end_inset


\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
\begin_inset Formula $\pi=\pi G$
\end_inset

, usu.
 with normalization condition 
\begin_inset Formula $\sum_{i}\pi_{i}=1$
\end_inset


\end_layout

\begin_layout Itemize
properties
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $S,G$
\end_inset

 are 
\emph on
stochastic matrices
\emph default
 (Markov chain transition matrix; rows sum to 1), hence there's always a
 solution
\end_layout

\begin_layout Itemize
actually a unique solution (
\emph on
stationary distribution
\emph default
), either by Markov theory or Perron-Frobenius theorem
\end_layout

\end_deeper
\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://meyer.math.ncsu.edu/Meyer/PS_Files/IMAGE.pdf
\end_layout

\end_inset

 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://cacm.acm.org/magazines/2011/6/108660-pagerank-standing-on-the-shoulders-of-
giants/fulltext
\end_layout

\end_inset


\end_layout

\begin_layout Section
Optimization
\end_layout

\begin_layout Subsection
Convex optimization
\end_layout

\begin_layout Itemize
lin prog, quad prog
\end_layout

\begin_layout Subsection
Linear programming
\end_layout

\begin_layout Itemize
\begin_inset Formula $\arg\max_{\vec{x}}\transpose{\vec{c}}\vec{x}$
\end_inset

 subject to 
\begin_inset Formula $A\vec{x}\le\vec{b}$
\end_inset

 and 
\begin_inset Formula $\vec{x}\ge0$
\end_inset


\end_layout

\begin_layout Itemize
algo families: basis exchange (eg simplex), interior point (eg ellipsoid)
\end_layout

\begin_layout Subsection
Quadratic programming
\end_layout

\begin_layout Itemize
\begin_inset Formula $\arg\min_{\vec{x}}f\left(\vec{x}\right)=\frac{1}{2}\transpose{\vec{x}}Q\vec{x}+\transpose{\vec{c}}\vec{x}$
\end_inset

 subject to 
\begin_inset Formula $A\vec{x}\le\vec{b}$
\end_inset

 and 
\begin_inset Formula $E\vec{x}=\vec{d}$
\end_inset


\end_layout

\begin_layout Itemize
algos: interior point, active set, augmented Lagrangian, conjugate gradient,
 simplex extensions
\end_layout

\begin_layout Itemize
for pos-def 
\begin_inset Formula $Q$
\end_inset

, 
\emph on
ellipsoid method
\emph default
 solves in poly time
\end_layout

\begin_layout Itemize
for indef 
\begin_inset Formula $Q$
\end_inset

 or if 
\begin_inset Formula $Q$
\end_inset

 has only 1 negative eigenvalue, NP-hard
\end_layout

\begin_layout Section
Machine Learning
\end_layout

\begin_layout Subsection
Information criteria
\end_layout

\begin_layout Itemize
Akaike's information criterion (AIC): 
\begin_inset Formula $-2\log\mathcal{L}+2p=\mbox{deviance}+\mbox{params}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\mathcal{L}$
\end_inset

 is maximized likelihood using all avail data for estimation
\end_layout

\begin_layout Itemize
\begin_inset Formula $p$
\end_inset

 is # free params in model
\end_layout

\begin_layout Itemize
also seen (TODO resolve?)
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $-2\log\frac{\mbox{RSS}}{n}+\frac{2nk}{n-k-1}$
\end_inset

 where RSS is residual sum of squares and 
\begin_inset Formula $k$
\end_inset

 is # params
\end_layout

\begin_layout Itemize
\begin_inset Formula $-2\log\mathcal{L}+2p+\frac{2p\left(p+1\right)}{n-p-1}$
\end_inset

 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://scott.fortmann-roe.com/docs/MeasuringError.html
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
asymptotically, minimizing AIC equiv to minimizing CV value
\end_layout

\end_deeper
\begin_layout Itemize
Schwarz Bayesian information criterion (BIC): 
\begin_inset Formula $-2\log\mathcal{L}+p\log n$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $n$
\end_inset

 is # obs
\end_layout

\begin_layout Itemize
heavier penalty means model chosen by BIC is same or simpler (fewer params)
 than AIC
\end_layout

\begin_layout Itemize
asymptotically, minimizing BIC equiv to minimizing leave-
\begin_inset Formula $v$
\end_inset

-out CV where 
\begin_inset Formula $v=n\left(1-\frac{1}{\log n-1}\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Subsection
Bayesian learning
\end_layout

\begin_layout Itemize
hypothesis prior 
\begin_inset Formula $\Pr\left[\Theta\right]$
\end_inset

, where 
\begin_inset Formula $\Theta$
\end_inset

 is hyp RV
\end_layout

\begin_layout Itemize
likelihood 
\begin_inset Formula $L\left(\theta\right)=\Pr\left[\vec{x}\mid\theta\right]$
\end_inset

; log-likelihood 
\begin_inset Formula $\ell\left(\theta\right)=\log\Pr\left[\vec{x}\mid\theta\right]$
\end_inset


\end_layout

\begin_layout Itemize
posterior 
\begin_inset Formula $\Pr\left[\theta\mid\vec{x}\right]=\alpha\Pr\left[\vec{x}\mid\theta\right]\Pr\left[\theta\right]$
\end_inset


\end_layout

\begin_layout Itemize
Bayesian learning: predict 
\begin_inset Formula $\Pr\left[X'\mid\vec{x}\right]=\sum_{\theta}\Pr\left[X'\mid\vec{x},\theta\right]\Pr\left[\theta\mid\vec{x}\right]=\sum_{i}\Pr\left[X'\mid\theta\right]\Pr\left[\theta\mid\vec{x}\right]$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
calculate prob of each hyp and predict over all hyps
\end_layout

\end_deeper
\begin_layout Itemize
maximum a posteriori (MAP): predict 
\begin_inset Formula $\Pr\left[X'\mid\theta_{\text{MAP}}\right]$
\end_inset

 where 
\begin_inset Formula $\theta_{\text{MAP}}=\arg\max_{\theta}\Pr\left[\theta\mid\vec{x}\right]$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
predict from just the single hyp with greatest posterior (easier)
\end_layout

\begin_layout Itemize
usually 
\begin_inset Formula $\Pr\left[X'\mid\theta_{\text{MAP}}\right]\rightarrow\Pr\left[X'\mid\vec{x}\right]$
\end_inset

 as more data arrives; otherwise, may snap to incorrect hypothesis
\end_layout

\begin_layout Itemize
equiv to MDL: 
\begin_inset Formula $\theta_{\text{MAP}}=\arg\min_{\theta}-\log\Pr\left[\vec{x}\mid\theta\right]-\log\Pr\left[\theta\right]$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
maximum lilkelihood: assume uniform prior over hyps, then 
\begin_inset Formula $\theta_{\text{MAP}}=\arg\max_{\theta}\Pr\left[\vec{x}\mid\theta\right]$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
reasonable for more data, since data swamps priors
\end_layout

\end_deeper
\begin_layout Subsection
Complete data
\end_layout

\begin_layout Itemize
observations are commonly IID: 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $\Pr\left[\vec{x}\mid\theta\right]=\prod_{i=1}^{n}\Pr\left[\vec{x}_{i}\mid\theta\right]$
\end_inset


\end_layout

\begin_layout Itemize
maximum likelihood
\end_layout

\begin_deeper
\begin_layout Itemize
log likelihood easier to maximize because products become sums: 
\begin_inset Formula $\log\Pr\left[\vec{x}\mid\theta\right]=\sum_{i=1}^{n}\Pr\left[\vec{x}_{i}\mid\theta\right]$
\end_inset


\end_layout

\begin_layout Itemize
Naive Bayes: MLE on Bayesian network where (discrete) class is root, attrs
 are leaves, and 
\emph on
attrs are IID given class
\end_layout

\begin_deeper
\begin_layout Itemize

\emph on
generative model
\emph default
: either class is a component of 
\begin_inset Formula $\vec{x}$
\end_inset

 (
\begin_inset Formula $\vec{x}_{0}$
\end_inset

) or say 
\begin_inset Formula $\Pr\left[\vec{x},C\mid\theta\right]$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
same for both discrete and continuous models
\end_layout

\begin_layout Itemize
for network 
\begin_inset Formula $A\rightarrow B$
\end_inset

 where 
\begin_inset Formula $A,B$
\end_inset

 are continuous, MLE over 
\begin_inset Formula $\Pr\left[b\mid a\right]=\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{\left(b-\left(\theta_{1}a+\theta_{2}\right)\right)^{2}}{2\sigma^{2}}\right)$
\end_inset

 same as minimizing the exponent, the sum of squared errors 
\begin_inset Formula $E=\sum_{i=1}^{n}\left(b_{i}-\left(\theta_{1}a_{i}+\theta_{2}\right)\right)^{2}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Bayesian parameter learning (incorporating hyp probs)
\end_layout

\begin_deeper
\begin_layout Itemize
commonly use conjugate prior for hyp prior 
\begin_inset Formula $\Pr\left[\Theta\right]$
\end_inset

 to simplify math
\end_layout

\begin_layout Itemize
e.g.
 if 
\begin_inset Formula $\Theta=\Pr\left[X=\text{head}\right]$
\end_inset

 and 
\begin_inset Formula $\Pr\left[\theta\right]=\text{beta}\left[a,b\right]\left(\theta\right)=\alpha\theta^{a-1}\left(1-\theta\right)^{b-1}$
\end_inset

 and our data is 
\begin_inset Formula $x=\text{head}$
\end_inset

, then 
\begin_inset Formula 
\[
\Pr\left[\theta\mid x\right]=\alpha\Pr\left[x\mid\theta\right]\Pr\left[\theta\right]=\alpha'\theta\theta^{a-1}\left(1-\theta\right)^{b-1}=\text{beta}\left[a+1,b\right]\left(\theta\right)
\]

\end_inset


\end_layout

\begin_layout Itemize
usu.
 assume param independence so each param can have own beta dist
\end_layout

\begin_layout Itemize
incorporating param RVs into Bayesian network itself requires making copies
 of the variables describing each instance
\end_layout

\end_deeper
\begin_layout Subsection
Incomplete data: EM algo
\end_layout

\begin_layout Itemize
hidden/latent variables: indirection that dramatically reduces number of
 parameters in Bayesian network
\end_layout

\begin_layout Itemize
EM algo
\end_layout

\begin_deeper
\begin_layout Itemize
E-step: calculate expected likelihood given current param estimates: 
\begin_inset Formula $Q\left(\theta\mid\theta^{\left(t\right)}\right)=\E_{Z\mid X,\Theta^{\left(t\right)}}\left[\log L\left(\theta;X,Z\right)\right]$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
often, in reality, we don't actually have to calculate expected likelihood,
 just as we don't have to compute cost function in gradient descents
\end_layout

\begin_layout Itemize
this step usually just updates hidden value estimates, which will then be
 used in M-step
\end_layout

\end_deeper
\begin_layout Itemize
M-step: find params that maximize expected likelihood: 
\begin_inset Formula $\theta^{\left(t+1\right)}=\arg\max_{\theta}Q\left(\theta\mid\theta^{\left(t\right)}\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
EM algo examples (all have 
\begin_inset Formula $N$
\end_inset

 data points)
\end_layout

\begin_deeper
\begin_layout Itemize
unsupervised clustering: Gaussian mixture model
\end_layout

\begin_deeper
\begin_layout Itemize
single Gaussian: 
\begin_inset Formula $\mathcal{N}\left(x\mid\mu,\Sigma\right)=\frac{1}{\left(2\pi\right)^{d/2}\sqrt{\left|\Sigma\right|}}\exp\left(-\frac{1}{2}\transpose{\left(x-\mu\right)}\Sigma^{-1}\left(x-\mu\right)\right)$
\end_inset


\end_layout

\begin_layout Itemize
GMM: 
\begin_inset Formula $\Pr\left[x\right]=\sum_{i=1}^{N}\Pr\left[C=i\right]_{i}\cdot\mathcal{N}\left(x\mid\mu_{i},\Sigma_{i}\right)$
\end_inset

 where 
\begin_inset Formula $N$
\end_inset

 is # Gaussians
\end_layout

\begin_layout Itemize
while ANNs are universal approximators of functions, GMMs are universal
 approximators of densities
\end_layout

\begin_layout Itemize
even diagonal GMMs are universal approximators; full-rank are unwieldy,
 since # params is square of # dims
\end_layout

\begin_layout Itemize
like K-means with probabilistic assignments and Gaussians instead of means
 (K-means is a 
\emph on
hard EM
\emph default
 algo)
\end_layout

\begin_deeper
\begin_layout Itemize
very sensitive to initialization; may initialize with K-means
\end_layout

\end_deeper
\begin_layout Itemize
mixture model of 
\begin_inset Formula $k$
\end_inset

 components: 
\begin_inset Formula $\Pr\left[\vec{x}\right]=\sum_{i=1}^{k}\Pr\left[C=i\right]\Pr\left[\vec{x}\mid C=i\right]$
\end_inset


\end_layout

\begin_layout Itemize
Bayes net: 
\begin_inset Formula $C\rightarrow\vec{X}$
\end_inset

, 
\begin_inset Formula $C$
\end_inset

 hidden, 
\begin_inset Formula $C$
\end_inset

 discrete, 
\begin_inset Formula $\vec{X}$
\end_inset

 continuous
\end_layout

\begin_layout Itemize
E-step: calculate some quantities useful later (assignment probabilities,
 which are the hidden variables):
\begin_inset Formula 
\begin{eqnarray*}
p_{ij} & \leftarrow & \Pr\left[C_{j}=i\mid\vec{x}_{j}\right]=\alpha\Pr\left[\vec{x}_{j}\mid C_{j}=i\right]\Pr\left[C_{j}=i\right]\\
p_{i} & \leftarrow & \sum_{j}p_{ij}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
M-step: maximize expected likelihood of observed & hidden vars
\begin_inset Formula 
\begin{eqnarray*}
\vec{\mu}_{i} & \leftarrow & \sum_{j}p_{ij}\vec{x}_{j}/p_{i}\\
\vec{\Sigma}_{i} & \leftarrow & \sum_{j}p_{ij}\vec{x}_{j}\transpose{\vec{x}_{j}}/p_{i}\\
\Pr\left[C=i\right]=\theta_{i} & \leftarrow & p_{i}/N
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
to avoid local maxima (component shrinking to a single point, two components
 merging, etc.):
\end_layout

\begin_deeper
\begin_layout Itemize
use priors on params to apply MAP version of EM
\end_layout

\begin_layout Itemize
restart components with new random params if it gets too small/too close
 to another component
\end_layout

\begin_layout Itemize
initialize params with reasonable values
\end_layout

\end_deeper
\begin_layout Itemize
can also do MAP GMM
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://bengio.abracadoudou.com/lectures/gmm.pdf
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Naive Bayes with hidden class
\end_layout

\begin_deeper
\begin_layout Itemize
Bayes net: 
\begin_inset Formula $X\rightarrow\vec{Y}$
\end_inset

, 
\begin_inset Formula $X$
\end_inset

 hidden, 
\begin_inset Formula $X,Y$
\end_inset

 discrete
\end_layout

\begin_layout Itemize
E-step: 
\begin_inset Formula 
\begin{eqnarray*}
p_{ij} & \leftarrow & \Pr\left[X=i\mid\vec{Y}=\vec{y}_{j}\right]\\
p_{i} & \leftarrow & \sum_{j}p_{ij}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
M-step: 
\begin_inset Formula $\hat{N}$
\end_inset

 are expected counts: 
\begin_inset Formula 
\begin{eqnarray*}
\Pr\left[X=i\right]=\theta_{i} & \leftarrow & \frac{\hat{N}\left(X=i\right)}{N}=\frac{1}{N}\sum_{j=1}^{N}\Pr\left[X=i\right]=\frac{p_{i}}{N}\\
\Pr\left[\vec{Y}=\vec{y}\mid X=i\right]=\vec{\theta}_{i} & \leftarrow & \frac{\hat{N}\left(\vec{Y}=\vec{y},X=i\right)}{\hat{N}\left(X=i\right)}=\frac{\sum_{j:\vec{y}_{j}=\vec{y}}p_{ij}}{p_{i}}
\end{eqnarray*}

\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
HMMs: dynamic Bayes net with single discrete state var
\end_layout

\begin_deeper
\begin_layout Itemize
each data point is sequence of observations
\end_layout

\begin_layout Itemize
transition probs repeat across time: 
\begin_inset Formula $\forall t,\theta_{ijt}=\theta_{ij}$
\end_inset


\end_layout

\begin_layout Itemize
E-step: modify forward-backward algo to compute expected counts below
\end_layout

\begin_deeper
\begin_layout Itemize
obtained by smoothing rather than filtering: must pay attn to subsequent
 evidence in estimating prob of a particular transition (eg evidence is
 obtained after crime)
\end_layout

\end_deeper
\begin_layout Itemize
M-step: 
\begin_inset Formula $\theta_{ij}\leftarrow\frac{\sum_{t}\hat{N}\left(X_{t+1}=j,X_{t}=i\right)}{\sum_{t}\hat{N}\left(X_{t}=i\right)}$
\end_inset


\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
EM algo
\end_layout

\begin_deeper
\begin_layout Itemize
pretend we know params, then 
\begin_inset Quotes eld
\end_inset

complete
\begin_inset Quotes erd
\end_inset

 data infer prob dists over hidden vars, then find params that maximize
 likelihood of observed & hidden vars
\end_layout

\begin_layout Itemize
gist: 
\begin_inset Formula $\vec{\theta}^{\left(t+1\right)}=\arg\max_{\vec{\theta}}\sum_{\vec{z}}\Pr\left[\vec{Z}=\vec{z}\mid\vec{x},\vec{\theta}^{\left(t\right)}\right]\ell\left(\vec{x},\vec{Z}=\vec{z}\mid\theta\right)$
\end_inset


\end_layout

\begin_layout Itemize
E-step: compute 
\begin_inset Formula $Q\left(\vec{\theta}\mid\vec{\theta}^{\left(t\right)}\right)=\E_{\vec{Z}\mid\vec{x},\vec{\theta}^{\left(t\right)}}\left[\ell\left(\vec{x},\vec{Z}\mid\vec{\theta}\right)\right]$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
expected likelihood over 
\begin_inset Formula $\vec{Z}$
\end_inset

 under current 
\begin_inset Formula $\vec{\theta}^{\left(t\right)}$
\end_inset


\end_layout

\begin_layout Itemize
misnomer: what's calculated are fixed, data-dependent params of 
\begin_inset Formula $Q$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
M-step: compute 
\begin_inset Formula $\vec{\theta}^{\left(t+1\right)}=\arg\max_{\vec{\theta}}Q\left(\vec{\theta}\mid\vec{\theta}^{\left(t\right)}\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
new 
\begin_inset Formula $\vec{\theta}$
\end_inset

 that maximizes the expected likelihood
\end_layout

\end_deeper
\begin_layout Itemize
resembles gradient-based hill-climbing but no 
\begin_inset Quotes eld
\end_inset

step size
\begin_inset Quotes erd
\end_inset

 param
\end_layout

\begin_layout Itemize
monotonically increases likelihood
\end_layout

\end_deeper
\begin_layout Subsection
Kernel models
\end_layout

\begin_layout Itemize
aka Parzen-Rosenblatt window
\end_layout

\begin_layout Itemize
each instance contributes small density function 
\begin_inset Formula $K\left(\vec{x},\vec{x}_{i}\right)$
\end_inset


\end_layout

\begin_layout Itemize
density estimation: 
\begin_inset Formula $p\left(\vec{x}\right)=\frac{1}{N}\sum_{i=1}^{N}K\left(\vec{x},\vec{x}_{i}\right)$
\end_inset


\end_layout

\begin_layout Itemize
kernel normally depends only on distance 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $D\left(\vec{x},\vec{x}_{i}\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
eg 
\begin_inset Formula $d$
\end_inset

-dimensional Gaussian 
\begin_inset Formula $K\left(\vec{x},\vec{x}_{i}\right)=\frac{1}{\left(w^{2}\sqrt{2\pi}\right)^{d}}\exp\left(-\frac{D\left(\vec{x},\vec{x}_{i}\right)^{2}}{2w^{2}}\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
supervised learning: take weighted combination of all predictions
\end_layout

\begin_deeper
\begin_layout Itemize
vs kNN's unweighted combination of 
\begin_inset Formula $k$
\end_inset

 instances
\end_layout

\end_deeper
\begin_layout Subsection
Classification
\end_layout

\begin_layout Itemize
linear classifiers: simplest type of feedforward neural network
\end_layout

\begin_deeper
\begin_layout Itemize
TODO: single- vs multi-layer perceptron; feedforward vs backpropagation
\end_layout

\end_deeper
\begin_layout Itemize

\emph on
perceptron
\emph default
 learning algorithm: for each iteration, if 
\begin_inset Formula $y_{t}\left(\vec{\theta}\cdot\vec{x_{t}}\right)\le0$
\end_inset

 (mistake), then 
\begin_inset Formula $\vec{\theta}\leftarrow\vec{\theta}+y_{t}\vec{x_{t}}$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Itemize
makes at most 
\begin_inset Formula $\frac{R^{2}}{\gamma_{g}^{2}}$
\end_inset

 mistakes on training set, where 
\begin_inset Formula $\norm{\vec{x_{i}}}\le R$
\end_inset

 and 
\begin_inset Formula $\gamma_{g}\le\frac{y_{i}\left(\vec{\theta^{*}}\cdot\vec{x_{i}}\right)}{\norm{\vec{\theta^{*}}}}$
\end_inset

 is the margin
\end_layout

\end_deeper
\begin_layout Itemize

\emph on
support vector machine (SVM)
\emph default
: maximum margin classifier with some slack
\begin_inset Formula 
\begin{eqnarray*}
\text{minimize } &  & \frac{1}{2}\norm{\vec{\theta}}^{2}+C\sum_{t=1}^{n}\xi_{t}\\
\text{subject to } &  & y_{t}\left(\vec{\theta}^{T}\vec{x_{t}}+\theta_{0}\right)\ge1-\xi_{t}\\
\text{and } &  & \xi_{t}\ge0\,\forall t=1,\dots,n
\end{eqnarray*}

\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
equivalent formulation assuming 
\begin_inset Formula $y_{t}$
\end_inset

 are 1/0 instead of 
\begin_inset Formula $\pm1$
\end_inset

:
\begin_inset Formula 
\begin{eqnarray*}
\mbox{minimize} &  & C\sum_{t=1}^{n}\left[y_{t}\mbox{cost}_{1}\left(\transpose{\vec{\theta}}\vec{x}_{t}+\theta_{0}\right)+\left(1-y_{t}\right)\mbox{cost}_{0}\left(\transpose{\vec{\theta}}\vec{x}_{t}+\theta_{0}\right)\right]+\frac{1}{2}\norm{\vec{\theta}}^{2}\\
\mbox{where} &  & \mbox{cost}_{1}\left(z\right)=\max\left(0,1-z\right)\\
 &  & \mbox{cost}_{0}\left(z\right)=\max\left(0,1+z\right)
\end{eqnarray*}

\end_inset

since 
\begin_inset Formula 
\begin{eqnarray*}
y_{t}\left(\transpose{\vec{\theta}}\vec{x}_{t}+\theta_{0}\right) & \ge & 1-\xi_{t}\\
\xi_{t} & \ge & 0
\end{eqnarray*}

\end_inset

becomes (given that we're trying to minimize all the 
\begin_inset Formula $\xi_{t}$
\end_inset

)
\begin_inset Formula 
\begin{eqnarray*}
\xi_{t} & = & \max\left(0,1-y_{t}\left(\transpose{\vec{\theta}}\vec{x}_{t}+\theta_{0}\right)\right)\\
 & = & \mbox{cost}_{1}\left(\transpose{\vec{\theta}}\vec{x}_{t}+\theta_{0}\right)
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
LOOCV error 
\begin_inset Formula $\frac{1}{2}\sum_{i=1}^{n}\text{Loss}\left(y_{i},f\left(x_{i};\hat{\vec{\theta}}^{-i},\hat{\vec{\theta}}_{0}^{-i}\right)\right)$
\end_inset

 where Loss is the 0-1 loss.
 Upper bound is (# support vectors / 
\begin_inset Formula $n$
\end_inset

).
\end_layout

\begin_layout Itemize
quadratic programming optimization problem: single global maximum that can
 be found efficiently
\end_layout

\begin_layout Itemize
dual: 
\begin_inset Formula 
\begin{eqnarray*}
\mbox{maximize} &  & \sum_{i}\alpha_{i}-\frac{1}{2}\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}\left(\vec{x}_{i}\cdot\vec{x}_{j}\right)\\
\mbox{subject to} &  & \alpha_{i}\ge0\,\forall i\\
\mbox{and} &  & \sum_{i}\alpha_{i}y_{i}=0
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
kernel trick: substitute kernel function 
\begin_inset Formula $K\left(\vec{x}_{i},\vec{x}_{j}\right)=F\left(\vec{x}_{i}\right)\cdot F\left(\vec{x}_{j}\right)$
\end_inset

 where 
\begin_inset Formula $F$
\end_inset

 maps to high/infinite dimensions but 
\begin_inset Formula $K$
\end_inset

 can still be computed efficiently
\end_layout

\begin_layout Itemize

\emph on
Mercer's theorem
\emph default
: any 
\begin_inset Quotes eld
\end_inset

reasonable
\begin_inset Quotes erd
\end_inset

 (positive definite) kernel function corresponds to 
\emph on
some
\emph default
 feature space
\end_layout

\begin_layout Itemize
kernels
\end_layout

\begin_deeper
\begin_layout Itemize
quadratic: 
\begin_inset Formula $\left(\vec{x}_{i}\cdot\vec{x}_{j}\right)^{2}$
\end_inset

 (common illustration: slicing hyperparabola yields circular separator)
\end_layout

\begin_layout Itemize
polynomial: 
\begin_inset Formula $\left(1+\vec{x}_{i}\cdot\vec{x}_{j}\right)^{d}$
\end_inset


\end_layout

\begin_layout Itemize
radial basis function (RBF): often the best
\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize

\emph on
logistic regression
\emph default
: optimize using logit/logistic/sigmoid function 
\begin_inset Formula 
\[
\Pr\left[y=1\mid\vec{x};\vec{\theta}\right]=h_{\vec{\theta}}\left(\vec{x}\right)=g\left(z\right)=\frac{e^{z}}{e^{z}+1}=\frac{1}{1+e^{-z}},\, z=\theta_{0}+\vec{\theta}\cdot\vec{x}
\]

\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
loss function
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\mbox{Cost}\left(h_{\vec{\theta}}\left(\vec{x}\right),y\right)=\begin{cases}
-\log h_{\vec{\theta}}\left(\vec{x}\right), & \mbox{if \ensuremath{y=1}}\\
-\log\left(1-h_{\vec{\theta}}\left(\vec{x}\right)\right), & \mbox{if \ensuremath{y=0}}
\end{cases}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $J\left(\theta\right)=\frac{1}{m}\sum_{i=1}^{m}\mbox{Cost}\left(h_{\vec{\theta}}\left(\vec{x}^{\left(i\right)}\right),y^{\left(i\right)}\right)=-\frac{1}{m}\sum_{i=1}^{m}\left[y^{\left(i\right)}\log h_{\vec{\theta}}\left(\vec{x}^{\left(i\right)}\right)+\left(1-y^{\left(i\right)}\right)\log\left(1-h_{\vec{\theta}}\left(\vec{x^{\left(i\right)}}\right)\right)\right]$
\end_inset

 (a clever differentiable form)
\end_layout

\begin_layout Itemize
intuition: 0 when completely correct and 
\begin_inset Formula $\infty$
\end_inset

 when completely incorrect
\end_layout

\end_deeper
\begin_layout Itemize
gradient descent: identical (LMS) update rule & derivation as in linear
 regression but 
\begin_inset Formula $h$
\end_inset

 is non-linear (logit)
\end_layout

\begin_layout Itemize
for perfectly separable data, 
\begin_inset Formula $\theta\rightarrow\infty$
\end_inset

; need regularization
\end_layout

\begin_layout Itemize
another algo: Newton's method to find zero of 
\begin_inset Formula $\ell'\left(\theta\right)$
\end_inset


\end_layout

\begin_layout Itemize
coefficients & intercept have log-odds interpretation
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $z=\log\frac{p}{1-p}$
\end_inset

, where 
\begin_inset Formula $p=\Pr\left[y=1\mid\vec{x};\vec{\theta}\right]=g\left(z\right)$
\end_inset


\end_layout

\begin_layout Itemize
intercept: log-odds if 
\begin_inset Formula $\vec{x}=\vec{0}$
\end_inset


\end_layout

\begin_layout Itemize
coefficient for indicator: log-odds between 1 and 0 groups
\end_layout

\begin_layout Itemize
coefficient for continuous: log-odds between unit deltas in value
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status open

\begin_layout Plain Layout

http://www.ats.ucla.edu/stat/mult_pkg/faq/general/odds_ratio.htm
\end_layout

\end_inset


\end_layout

\end_deeper
\end_deeper
\begin_layout Subsection
Regression
\end_layout

\begin_layout Itemize
squared error 
\begin_inset Formula $\mbox{SE}=\sum_{i}\left(y_{i}-\hat{y}_{i}\right)^{2}$
\end_inset

, 
\begin_inset Formula $\mbox{MSE}=\frac{1}{n}\mbox{SE}$
\end_inset

, 
\begin_inset Formula $\mbox{RMSE}=\sqrt{\mbox{SE}}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize

\emph on
bias-variance tradeoff
\emph default
: 
\begin_inset Formula $\mbox{MSE}=\Var\left[\mbox{SE}\right]+\E\left[y_{i}-\hat{y}_{i}\right]^{2}=\Var\left[\mbox{SE}\right]+\mbox{Bias}^{2}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
relative sq err 
\begin_inset Formula $\mbox{RSE}=\frac{\sum_{i}\left(y_{i}-\hat{y}_{i}\right)^{2}}{\sum_{i}\left(y_{i}-\bar{y}\right)^{2}}$
\end_inset

, root rel sq err 
\begin_inset Formula $\mbox{RRSE}=\sqrt{\mbox{RSE}}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\mbox{MAE}=\frac{1}{n}\sum_{i}\left|y_{i}-\hat{y}_{i}\right|$
\end_inset

, rel abs err 
\begin_inset Formula $\mbox{RAE}=\frac{\sum_{i}\left|y_{i}-\hat{y}_{i}\right|}{\sum_{i}\left|y_{i}-\bar{y}\right|}$
\end_inset


\end_layout

\begin_layout Itemize
mean abs pct err 
\begin_inset Formula $\mbox{MAPE}=\frac{1}{n}\sum_{i}\left|\frac{y_{i}-\hat{y}_{i}}{y_{i}}\right|$
\end_inset

 (drawbacks: zeros, unbounded)
\end_layout

\begin_layout Itemize
relative errors can compare models of different units
\end_layout

\begin_layout Itemize

\emph on
coefficient of determination
\emph default
 
\begin_inset Formula $R^{2}=\frac{SS_{\mbox{reg}}}{SS_{\mbox{tot}}}=1-\frac{SS_{\mbox{err}}}{SS_{\mbox{tot}}}=1-\mbox{RSE}$
\end_inset

 where
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $SS_{\mbox{tot}}=\sum_{i}\left(y_{i}-\bar{y}\right)^{2}$
\end_inset

: total sum of squares (proportional to sample variance)
\end_layout

\begin_layout Itemize
\begin_inset Formula $SS_{\mbox{reg}}=\sum_{i}\left(f_{i}-\bar{y}\right)^{2}$
\end_inset

: regression/explained sum of squares
\end_layout

\begin_layout Itemize
\begin_inset Formula $SS_{\mbox{err}}=\sum_{i}\left(y_{i}-f_{i}\right)^{2}$
\end_inset

: residual sum of squares; sum of squared residuals
\end_layout

\begin_layout Itemize
\begin_inset Formula $R^{2}=1$
\end_inset

 is perfect; 
\begin_inset Formula $R^{2}<0$
\end_inset

 means 
\begin_inset Formula $\bar{y}$
\end_inset

 is better than the model
\end_layout

\end_deeper
\begin_layout Itemize
adjusted 
\begin_inset Formula $R^{2}$
\end_inset

 is 
\begin_inset Formula $1-\left(1-R^{2}\right)\frac{n-1}{n-p-1}=1-\frac{SS_{\mbox{err}}}{SS_{\mbox{tot}}}\cdot\frac{df_{t}}{df_{e}}=1-\frac{\Var_{\mbox{err}}}{\Var_{\mbox{tot}}}$
\end_inset

, where
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $p$
\end_inset

 is total number of regressors in linear model
\end_layout

\begin_layout Itemize
\begin_inset Formula $n$
\end_inset

 is sample size
\end_layout

\begin_layout Itemize
\begin_inset Formula $df_{t}$
\end_inset

 is dof 
\begin_inset Formula $n-1$
\end_inset

 of estimate of population variance of 
\begin_inset Formula $Y$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $df_{e}$
\end_inset

 is dof 
\begin_inset Formula $n-p-1$
\end_inset

 of estimate of underlying population error variance
\end_layout

\begin_layout Itemize
\begin_inset Formula $\Var_{\mbox{err}}=\frac{SS_{\mbox{err}}}{n-p-1}$
\end_inset

, 
\begin_inset Formula $\Var_{\mbox{tot}}=\frac{SS_{\mbox{tot}}}{n-1}$
\end_inset


\end_layout

\begin_layout Itemize
increases only if new regressor improves model more than would be expected
 by chance; penalizes too-many-regressors
\end_layout

\begin_layout Itemize
useful for feature selection, with small samples
\end_layout

\end_deeper
\begin_layout Itemize
intervals
\end_layout

\begin_deeper
\begin_layout Itemize
confidence interval: tells us about population params (mean/variance, or
 model params)
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Quotes eld
\end_inset

at confidence level 95%, 95% of samples (repeating this experiment) would
 generate CIs containing true params
\begin_inset Quotes erd
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
prediction interval: tells us about data values; always wider than CI
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Quotes eld
\end_inset

next value is in PI of 95% of samples (repeated experiments)
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
or: 
\begin_inset Quotes eld
\end_inset

95% of repeated experiments generate PI containing next random value
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
non-parametric assumes nothing about population; simply think of numbers
 of points/gaps
\end_layout

\end_deeper
\begin_layout Itemize
tolerance interval: tells us about percentage of all future values; usu.
 wider than PI
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Quotes eld
\end_inset

95% of all future values are in TI in 95% of samples/repeated experiments
\begin_inset Quotes erd
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
eg: in simple linear regression, 
\begin_inset Formula $\hat{y}=\hat{\alpha}+\hat{\beta}x=\E\left[y\mid x\right]$
\end_inset

 is the mean response, while 
\begin_inset Formula $y=\alpha+\beta x+\epsilon$
\end_inset

 is actual response
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\hat{y}$
\end_inset

 use CI, since 
\begin_inset Formula $\hat{\alpha},\hat{\beta}$
\end_inset

 use CI; draw confidence bands in plot for what the possible regression
 line is
\end_layout

\begin_layout Itemize
\begin_inset Formula $y$
\end_inset

 use PI; draw prediction bands in plot for what the possible values are
\end_layout

\end_deeper
\end_deeper
\begin_layout Subsection
Support vector regression (SVR)
\end_layout

\begin_layout Itemize
linear regression formulation with no slack: minimize 
\begin_inset Formula $\frac{1}{2}\norm{\vec{w}}^{2}$
\end_inset

 subject to 
\begin_inset Formula $y_{i}-\left\langle \vec{w},\vec{x}_{i}\right\rangle -b\le\varepsilon$
\end_inset

 and 
\begin_inset Formula $\left\langle \vec{w},\vec{x}_{i}\right\rangle +b-y_{i}\le\varepsilon$
\end_inset

 (require prediction 
\begin_inset Formula $\left\langle \vec{w},\vec{x}_{i}\right\rangle +b$
\end_inset

 to be within 
\begin_inset Formula $\pm\varepsilon$
\end_inset

 of 
\begin_inset Formula $y_{i}$
\end_inset

)
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.2073&rep=rep1&type=pdf
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Linear regression
\end_layout

\begin_layout Itemize

\emph on
ordinary least squares (OLS) regression
\emph default
: a linear regression
\end_layout

\begin_deeper
\begin_layout Itemize
minimize cost function 
\begin_inset Formula $J\left(\theta\right)=\frac{1}{2}\sum_{i=1}^{m}\left(y-h_{\vec{\theta}}\left(\vec{x}\right)\right)^{2},h_{\vec{\theta}}\left(\vec{x}\right)=\vec{\theta}\cdot\vec{x}$
\end_inset

 (sum of squared errors)
\end_layout

\begin_layout Itemize
gradient descent: repeatedly 
\begin_inset Formula $\theta_{j}\leftarrow\theta_{j}-\alpha\frac{\partial}{\partial\theta_{j}}J\left(\theta\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\alpha$
\end_inset

 is configurable learning rate
\end_layout

\begin_layout Itemize
batch: cost over all training instances
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\theta_{j}\leftarrow\theta_{j}+\alpha\sum_{i=1}^{m}\left(y^{\left(i\right)}-\vec{\theta}\cdot\vec{x}^{\left(i\right)}\right)\vec{x}_{j}^{\left(i\right)}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
stochastic aka incremental: converges faster
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\theta_{j}\leftarrow\theta_{j}+\alpha\left(y^{\left(i\right)}-\vec{\theta}\cdot\vec{x}^{\left(i\right)}\right)\vec{x}_{j}^{\left(i\right)}$
\end_inset


\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
update rule is called 
\emph on
least mean squares (LMS) rule
\emph default
 aka 
\emph on
Widrow-Hoff rule
\end_layout

\begin_deeper
\begin_layout Itemize
derivation for single training instance: 
\begin_inset Formula $\frac{\partial}{\partial\theta_{j}}J\left(\vec{\theta}\right)=\frac{\partial}{\partial\theta_{j}}\frac{1}{2}\left(y-\vec{\theta}\cdot\vec{x}\right)^{2}=-2\cdot\frac{1}{2}\left(y-\vec{\theta}\cdot\vec{x}\right)\frac{\partial}{\partial\theta_{j}}\left(y-\vec{\theta}\cdot\vec{x}\right)=-\left(y-\vec{\theta}\cdot\vec{x}\right)x_{j}$
\end_inset


\end_layout

\begin_layout Itemize
magnitude of update proportional to error term
\end_layout

\end_deeper
\begin_layout Itemize
can minimize in closed form without iterative algo (some matrix calculus):
 
\begin_inset Formula $\theta=\left(\transpose XX\right)^{-1}\transpose X\vec{y}$
\end_inset


\end_layout

\begin_layout Itemize
LOOCV can also be computed without training 
\begin_inset Formula $n$
\end_inset

 models: 
\begin_inset Formula $\frac{1}{n}\sum_{i=1}^{n}\left(\frac{e_{i}}{1-h_{i}}\right)^{2}$
\end_inset

 where 
\begin_inset Formula $e_{i}$
\end_inset

 is residual
\end_layout

\begin_layout Itemize
probabilistic interp: why linear regression/why 
\begin_inset Formula $J$
\end_inset

?
\end_layout

\begin_deeper
\begin_layout Itemize
assume 
\begin_inset Formula $y=\vec{\theta}\cdot\vec{x}+\epsilon$
\end_inset

 where 
\begin_inset Formula $\epsilon$
\end_inset

 is normally distributed
\end_layout

\begin_layout Itemize
in the following, 
\emph on
design matrix
\emph default
 
\begin_inset Formula $X$
\end_inset

 has training inputs as rows, and examples are indep
\end_layout

\begin_layout Itemize
to maximize likelihood 
\begin_inset Formula $L\left(\vec{\theta}\right)=p\left(\vec{y}\mid X;\vec{\theta}\right)=\prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{\left(y^{\left(i\right)}-\vec{\theta}\cdot\vec{x}^{\left(i\right)}\right)^{2}}{2\sigma^{2}}\right)$
\end_inset

, must minimize cost function in exponent
\end_layout

\begin_layout Itemize
can work it out by writing log likelihood
\end_layout

\end_deeper
\begin_layout Itemize
always passes through mean of 
\begin_inset Formula $x$
\end_inset

s and 
\begin_inset Formula $y$
\end_inset

s
\end_layout

\end_deeper
\begin_layout Subsection
Multi-layer feed-forward neural networks
\end_layout

\begin_layout Itemize
Assume 
\begin_inset Formula $m$
\end_inset

 examples, 
\begin_inset Formula $K$
\end_inset

 outputs, 
\begin_inset Formula $L$
\end_inset

 layers, 
\begin_inset Formula $s_{l}$
\end_inset

 nodes in layer 
\begin_inset Formula $l$
\end_inset


\end_layout

\begin_layout Itemize
Params 
\begin_inset Formula $\Theta^{\left(l\right)}$
\end_inset

 is 
\begin_inset Formula $s_{l+1}\times s_{l}$
\end_inset

 such that 
\begin_inset Formula $\Theta_{ij}^{\left(l\right)}$
\end_inset

 is weight from node 
\begin_inset Formula $j$
\end_inset

 in layer 
\begin_inset Formula $l$
\end_inset

 to node 
\begin_inset Formula $i$
\end_inset

 in layer 
\begin_inset Formula $l+1$
\end_inset

 (subscripts are 
\begin_inset Quotes eld
\end_inset

backward
\begin_inset Quotes erd
\end_inset

)
\end_layout

\begin_layout Itemize
Regularized cost 
\begin_inset Formula $J\left(\Theta\right)=-\frac{1}{m}\left[\sum_{i=1}^{m}\sum_{jk=1}^{K}y_{k}^{\left(i\right)}\log h_{\Theta}\left(x^{\left(i\right)}\right)+\left(1-y_{k}^{\left(i\right)}\right)\log\left(1-h_{\Theta}\left(x^{\left(i\right)}\right)\right)\right]+\frac{\lambda}{2m}\sum_{l=1}^{L}\sum_{i=1}^{s_{l}}\sum_{j=1}^{s_{l}+1}\left(\Theta_{ji}^{\left(l\right)}\right)^{2}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
Or squared error for regressions; these turn out to have the same derivations
\end_layout

\end_deeper
\begin_layout Itemize

\emph on
Backpropagation
\emph default
: algorithm used to compute gradients
\end_layout

\begin_deeper
\begin_layout Itemize
Need random initialization of 
\begin_inset Formula $\Theta$
\end_inset

 to break symmetry or all params will be equal
\end_layout

\begin_layout Itemize
\begin_inset Formula $\Delta_{ij}^{\left(l\right)}\leftarrow0\forall l,i,j$
\end_inset


\end_layout

\begin_layout Itemize
for 
\begin_inset Formula $i=1$
\end_inset

 to 
\begin_inset Formula $m$
\end_inset

:
\end_layout

\begin_deeper
\begin_layout Itemize
Forward-propagate activations 
\begin_inset Formula $\vec{a}^{\left(l\right)}=\Theta^{\left(l-1\right)}\vec{a}^{\left(l-1\right)}$
\end_inset

 for 
\begin_inset Formula $l=2,\dots,L$
\end_inset

 where 
\begin_inset Formula $\vec{a}^{\left(1\right)}=\vec{x}^{\left(i\right)}$
\end_inset


\end_layout

\begin_layout Itemize
Backpropagate errors 
\begin_inset Formula $\vec{\delta}^{\left(l\right)}=\transpose{\left(\Theta^{\left(l\right)}\right)}\vec{\delta}^{\left(l+1\right)}\odot g'\left(\vec{z}^{\left(l\right)}\right)$
\end_inset

 for 
\begin_inset Formula $l=L-1,\dots,2$
\end_inset

 where
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\vec{\delta}^{\left(L\right)}=\vec{a}^{\left(L\right)}-y^{\left(i\right)}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $g'\left(\vec{z}^{\left(l\right)}\right)=\vec{a}^{\left(l\right)}\odot\left(1-\vec{a}^{\left(l\right)}\right)$
\end_inset

 since 
\begin_inset Formula $g'\left(x\right)=g\left(x\right)\left(1-g\left(x\right)\right)$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $a\odot b$
\end_inset

 is element-wise multiplication (
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://math.stackexchange.com/questions/52578/symbol-for-elementwise-multiplicatio
n-of-vectors
\end_layout

\end_inset

)
\end_layout

\end_deeper
\begin_layout Itemize
\begin_inset Formula $\Delta_{ij}^{\left(l\right)}\leftarrow\Delta_{ij}^{\left(l\right)}+\delta_{i}^{\left(l+1\right)}a_{j}^{\left(l\right)}$
\end_inset

 for 
\begin_inset Formula $l=L-1,\dots,1$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Gradient 
\begin_inset Formula $\frac{\partial}{\partial\Theta_{ij}^{\left(l\right)}}J\left(\Theta\right)=\begin{cases}
\frac{1}{m}\Delta_{ij}^{\left(l\right)}+\lambda\Theta_{ij}^{\left(l\right)} & \mbox{if \ensuremath{j\ne0}}\\
\frac{1}{m}\Delta_{ij}^{\left(l\right)} & \mbox{if \ensuremath{j=0}}
\end{cases}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Excellent explanations of derivation at 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www.ml-class.org/course/qna/view?id=3740
\end_layout

\end_inset

, 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www.scribd.com/doc/72228829/Back-Propagation
\end_layout

\end_inset


\end_layout

\begin_layout Itemize
Derivation of gradient for layer 
\begin_inset Formula $L-1$
\end_inset

 focusing on a single example (
\begin_inset Formula $m=1$
\end_inset

)
\end_layout

\begin_deeper
\begin_layout Itemize
Define 
\begin_inset Formula $\delta_{i}^{\left(l\right)}=\frac{\partial J}{\partial z_{i}^{\left(l\right)}}$
\end_inset

: (how do we reduce the second factor?)
\begin_inset Formula 
\begin{eqnarray*}
\frac{\partial J}{\partial\Theta_{ij}^{\left(l-1\right)}} & = & \frac{\partial J}{\partial z_{i}^{\left(l\right)}}\frac{\partial z_{i}^{\left(l\right)}}{\partial\Theta_{ij}^{\left(l-1\right)}}=\delta_{i}^{\left(l\right)}\frac{\partial}{\partial\Theta_{ij}^{\left(L-1\right)}}\left(\sum_{k}\Theta_{kj}^{\left(l-1\right)}a_{j}^{\left(l-1\right)}\right)=\delta_{i}^{\left(l\right)}a_{j}^{\left(l-1\right)}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
For output layer:
\begin_inset Formula 
\begin{eqnarray*}
\delta_{i}^{\left(L\right)} & = & \frac{\partial J}{\partial z_{i}^{\left(L\right)}}\\
 & = & \frac{\partial}{\partial z_{i}^{\left(L\right)}}\left(-\sum_{k=1}^{K}y_{k}\log g\left(z_{k}^{\left(L\right)}\right)+\left(1-y_{k}\right)\log\left(1-g\left(z_{k}^{\left(L\right)}\right)\right)\right)\\
 & = & \frac{\partial}{\partial z_{i}^{\left(L\right)}}\left(-y_{i}\log g\left(z_{i}^{\left(L\right)}\right)+\left(1-y_{i}\right)\log\left(1-g\left(z_{i}^{\left(L\right)}\right)\right)\right)\\
 & = & -\left(y_{i}\frac{1}{g\left(z_{i}^{\left(L\right)}\right)}-\left(1-y_{i}\right)\frac{1}{1-g\left(z_{i}^{\left(L\right)}\right)}\right)g\left(z_{i}^{\left(L\right)}\right)\left(1-g\left(z_{i}^{\left(L\right)}\right)\right)\\
 & = & -\left(y_{i}\left(1-g\left(z_{i}^{\left(L\right)}\right)\right)-\left(1-y_{i}\right)g\left(z_{i}^{\left(L\right)}\right)\right)\\
 & = & -\left(y_{i}-g\left(z_{i}^{\left(L\right)}\right)\right)
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
Build on this to get previous layers
\end_layout

\begin_layout Itemize
For simpler squared error 
\begin_inset Formula $J\left(\Theta\right)=\frac{1}{2}\sum_{j=1}^{K}\left(y_{j}-a_{j}\right)^{2}$
\end_inset

, slightly different:
\begin_inset Formula 
\begin{eqnarray*}
\delta_{i} & = & \frac{\partial}{\partial z_{i}^{\left(L\right)}}\left(\frac{1}{2}\sum_{k=1}^{K}\left(y_{k}-g\left(z_{k}^{\left(L\right)}\right)\right)^{2}\right)\\
 & = & \left(y_{i}-g\left(z_{i}^{\left(L\right)}\right)\right)g'\left(z_{i}^{\left(L\right)}\right)\\
\end{eqnarray*}

\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Useful to test with 
\emph on
gradient checking
\emph default
 (numerical gradient)
\end_layout

\begin_layout Itemize
Generally if single hidden layer then choose more hidden units than inputs/outpu
ts, and choose same # hidden units in each layer if more than 1 hidden layer
\end_layout

\begin_layout Subsection
Local regression
\end_layout

\begin_layout Itemize

\emph on
locally weighted scatterplot smoothing (LOESS aka LOWESS) aka locally weighted
 regression (LWR)
\end_layout

\begin_deeper
\begin_layout Itemize
a type of 
\emph on
smoother
\end_layout

\begin_layout Itemize
typically LOESS is variable-bandwidth (fixed-span) smoother (like nearest-neighb
ors)
\end_layout

\begin_layout Itemize
typically LOESS is locally quadratic or linear
\end_layout

\begin_layout Itemize
weight functions/kernels: tricubic (traditional), Gaussian, ...
\end_layout

\end_deeper
\begin_layout Itemize
fixed-bandwidth example: to predict at 
\begin_inset Formula $x$
\end_inset

, fit 
\begin_inset Formula $\theta$
\end_inset

 to minimize 
\begin_inset Formula $\sum_{i}w^{\left(i\right)}\left(y^{\left(i\right)}-\vec{\theta}\cdot\vec{x}^{\left(i\right)}\right)^{2}$
\end_inset

 where typically 
\begin_inset Formula $w^{\left(i\right)}=\exp\left(-\frac{\left(x^{\left(i\right)}-x\right)^{2}}{2\tau^{2}}\right)$
\end_inset

 (some kernel) and 
\begin_inset Formula $\tau$
\end_inset

 is 
\emph on
bandwidth 
\emph default
param
\end_layout

\begin_layout Subsection
Regularization
\end_layout

\begin_layout Itemize
overfitting tends to occur when large weights found in 
\begin_inset Formula $\vec{\beta}$
\end_inset


\end_layout

\begin_layout Itemize
regularization pressures 
\begin_inset Formula $\vec{\beta}$
\end_inset

 to be small
\end_layout

\begin_layout Itemize
LASSO/L1: minimize 
\begin_inset Formula $\sum_{i}\left(\vec{\beta}\vec{x}_{i}-y_{i}\right)^{2}$
\end_inset

 where 
\begin_inset Formula $\norm{\vec{\beta}}_{1}\le s$
\end_inset

 and 
\begin_inset Formula $\norm{\vec{\beta}}_{1}=\sum_{j}\left|\vec{\beta}_{j}\right|$
\end_inset

 (
\begin_inset Formula $\ell_{1}$
\end_inset

 norm)
\end_layout

\begin_deeper
\begin_layout Itemize
equiv: minimize 
\begin_inset Formula $\sum_{i}\frac{1}{2n}\left(\vec{\beta}\vec{x}_{i}-y_{i}\right)^{2}+\lambda\norm{\vec{\beta}}_{1}$
\end_inset


\end_layout

\begin_layout Itemize
more notes in AI.page
\end_layout

\begin_layout Itemize
better than L2 when many features (vs examples)
\end_layout

\end_deeper
\begin_layout Itemize
ridge/Tikhonov: instead of 
\begin_inset Formula $\norm{X\vec{\beta}-\vec{y}}_{2}^{2}$
\end_inset

, minimize 
\begin_inset Formula $\norm{X\vec{\beta}-\vec{y}}_{2}^{2}+\norm{\Gamma\vec{\beta}}_{2}^{2}$
\end_inset

 for some suitable Tikhonov matrix 
\begin_inset Formula $\Gamma$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
L2 regularization: when 
\begin_inset Formula $\Gamma=I$
\end_inset


\end_layout

\begin_layout Itemize
effect aka 
\emph on
shrinkage
\end_layout

\begin_layout Itemize
\begin_inset Formula $\Gamma$
\end_inset

 can also be highpass to enforce smoothing
\end_layout

\begin_layout Itemize
explicit solution 
\begin_inset Formula $\hat{\beta}=\left(\transpose XX+\transpose{\Gamma}\Gamma\right)^{-1}\transpose X\vec{y}$
\end_inset

 (
\begin_inset Formula $O\left(n^{3}\right)$
\end_inset

 time)
\end_layout

\end_deeper
\begin_layout Itemize
elastic net: handles highly correlated vars; balance L1 & L2
\end_layout

\begin_deeper
\begin_layout Itemize
minimize 
\begin_inset Formula $\frac{1}{2n}\norm{X\vec{\beta}-\vec{y}}_{2}^{2}+\lambda\alpha\norm{\vec{\beta}}_{1}+\frac{\lambda\left(1-\alpha\right)}{2}\norm{\vec{\beta}}_{2}^{2}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www-stat.stanford.edu/~owen/courses/305/Rudyregularization.pdf
\end_layout

\end_inset

 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://scikit-learn.org/stable/modules/linear_model.html
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
GLM
\end_layout

\begin_layout Itemize
exponential family: 
\begin_inset Formula $p\left(y;\eta\right)=b\left(y\right)\exp\left(\transpose{\eta}T\left(y\right)-a\left(\eta\right)\right)$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\eta$
\end_inset

 is 
\emph on
natural param
\emph default
 aka 
\emph on
canonical param
\end_layout

\begin_layout Itemize
\begin_inset Formula $T\left(y\right)$
\end_inset

 is 
\emph on
sufficient statistic
\emph default
; often 
\begin_inset Formula $T\left(y\right)=y$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $a\left(\eta\right)$
\end_inset

 is 
\emph on
log partition function
\end_layout

\begin_layout Itemize
\begin_inset Formula $e^{-a\left(\eta\right)}$
\end_inset

 is normalizing const; ensures 
\begin_inset Formula $p$
\end_inset

 sums/integrates to 1 over 
\begin_inset Formula $y$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
fixed 
\begin_inset Formula $T,a,b$
\end_inset

 defines a 
\emph on
family
\emph default
 (set) of dists param'd by 
\begin_inset Formula $\eta$
\end_inset

 (vary 
\begin_inset Formula $\eta$
\end_inset

 for diff dists in fam)
\end_layout

\begin_layout Itemize
assumptions to derive GLM
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $y\mid x;\theta\sim\left(\mbox{some exponential family}\right)\left(\eta\right)$
\end_inset


\end_layout

\begin_layout Itemize
predicting 
\begin_inset Formula $h\left(x\right)=\E\left[T\left(y\right)\mid x\right]=\E\left[y\mid x\right]$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\eta=\vec{\theta}\cdot\vec{x}$
\end_inset

 (more of a 
\begin_inset Quotes eld
\end_inset

design choice
\begin_inset Quotes erd
\end_inset

 rather than an assumption)
\end_layout

\end_deeper
\begin_layout Subsection
PCA
\end_layout

\begin_layout Itemize
algorithm: normalize data, then find eigenvectors of covariance matrix
\end_layout

\begin_deeper
\begin_layout Itemize
can use SVD: 
\begin_inset Formula $U,S,V=\mbox{SVD}\left(\Cov\left(\frac{X-\mu}{\sigma}\right)\right)$
\end_inset

, where 
\begin_inset Formula $U$
\end_inset

 cols are eigenvectors in decreasing importance, 
\begin_inset Formula $S$
\end_inset

 is diagonal matrix of 
\emph on
singular values
\end_layout

\begin_layout Itemize
down-project: 
\begin_inset Formula $\vec{z}=U\vec{x}$
\end_inset


\end_layout

\begin_layout Itemize
recover: 
\begin_inset Formula $\vec{\hat{x}}=\transpose U\vec{z}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
use: viz (project to 2D/3D), compression, speeding up learning
\end_layout

\begin_layout Itemize
don't use to reduce dimensionality for learning since it doesn't consider
 labels; use regularization
\end_layout

\begin_layout Itemize
choose smallest 
\begin_inset Formula $k$
\end_inset

 where lost variance 
\begin_inset Formula $\frac{\frac{1}{m}\sum_{i=1}^{m}\norm{x^{\left(i\right)}-\hat{x}^{\left(i\right)}}^{2}}{\frac{1}{m}\sum_{i=1}^{m}\norm{x^{\left(i\right)}}^{2}}=\le.01$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
or (equivalently) retained variance 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $\frac{\sum_{i=1}^{k}S_{ii}}{\sum_{i=1}^{n}S_{ii}}\ge.99$
\end_inset


\family default
\series default
\shape default
\size default
\emph default
\bar default
\strikeout default
\uuline default
\uwave default
\noun default
\color inherit
 (
\begin_inset Quotes eld
\end_inset

99% variance retained
\begin_inset Quotes erd
\end_inset

)
\end_layout

\end_deeper
\begin_layout Itemize
PCA transpose trick 
\begin_inset Flex URL
status open

\begin_layout Plain Layout

http://blog.echen.me/2011/03/14/pca-transpose-trick/
\end_layout

\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
given 
\begin_inset Formula $m\times n$
\end_inset

 obs matrix 
\begin_inset Formula $A$
\end_inset

, often 
\begin_inset Formula $n\gg m$
\end_inset

 (dims 
\begin_inset Formula $\gg$
\end_inset

 obs)
\end_layout

\begin_layout Itemize
finding evecs of big 
\begin_inset Formula $n\times n$
\end_inset

 matrix 
\begin_inset Formula $\transpose AA$
\end_inset

 is expensive
\end_layout

\begin_layout Itemize
insight: if 
\begin_inset Formula $v$
\end_inset

 is evec of 
\begin_inset Formula $A\transpose A$
\end_inset

, then 
\begin_inset Formula $\transpose Av$
\end_inset

 is evec of 
\begin_inset Formula $\transpose AA$
\end_inset

 w same eval (short proof)
\end_layout

\begin_layout Itemize
so, find evecs of 
\begin_inset Formula $A\transpose A$
\end_inset

, then multiply by 
\begin_inset Formula $\transpose A$
\end_inset


\end_layout

\end_deeper
\begin_layout Subsection
SVD
\end_layout

\begin_layout Itemize
\begin_inset Formula $M=U\Sigma V^{\ast}$
\end_inset

, where
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $U$
\end_inset

 is 
\begin_inset Formula $m\times m$
\end_inset

 real/complex unitary matrix; cols (
\emph on
left singular vectors
\emph default
) are evecs of 
\begin_inset Formula $MM^{\ast}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\Sigma$
\end_inset

 is 
\begin_inset Formula $m\times n$
\end_inset

 non-neg real diag matrix
\end_layout

\begin_deeper
\begin_layout Itemize
entries are 
\emph on
singular values
\end_layout

\begin_layout Itemize
non-0 singular values are sqrts of non-0 evals of 
\begin_inset Formula $MM^{\ast}$
\end_inset

 or 
\begin_inset Formula $M^{\ast}M$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
\begin_inset Formula $V^{\ast}$
\end_inset

 is 
\begin_inset Formula $n\times n$
\end_inset

 real/complex unitary matrix; cols (
\emph on
right singular vectors
\emph default
) are evecs of 
\begin_inset Formula $M^{\ast}M$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
when all real, 
\begin_inset Formula $U,V$
\end_inset

 are rotations and 
\begin_inset Formula $\Sigma$
\end_inset

 is scaling
\end_layout

\begin_layout Itemize
eval decomp: similar concept but only for square matrices 
\begin_inset Formula $M$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $M^{\ast}M=V\Sigma^{\ast}U^{\ast}U\Sigma V^{\ast}=V\left(\Sigma^{\ast}\Sigma\right)V^{\ast}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $MM^{\ast}=U\Sigma V^{\ast}V\Sigma^{\ast}U^{\ast}=U\left(\Sigma\Sigma^{\ast}\right)U^{\ast}$
\end_inset


\end_layout

\begin_layout Itemize
RHSs are eval decomps of LHSs
\end_layout

\end_deeper
\begin_layout Itemize
use SVD to perform PCA
\end_layout

\begin_deeper
\begin_layout Itemize
let 
\begin_inset Formula $M$
\end_inset

 be deviations matrix; covar matrix is 
\begin_inset Formula $\frac{1}{n}M\transpose M=\frac{1}{n}U\Sigma^{2}\transpose U$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
low-rank approx to 
\begin_inset Formula $M$
\end_inset

: 
\begin_inset Formula $\tilde{M}=U\tilde{\Sigma}V^{\ast}$
\end_inset

, where 
\begin_inset Formula $\tilde{\Sigma}$
\end_inset

 is same as 
\begin_inset Formula $\Sigma$
\end_inset

 but with only 
\begin_inset Formula $r$
\end_inset

 largest singular values (rest replaced by 0)
\end_layout

\begin_layout Subsection
Matrix factorization
\end_layout

\begin_layout Itemize
\begin_inset Formula $R\approx MU$
\end_inset

 where 
\begin_inset Formula $M$
\end_inset

 is 
\begin_inset Formula $n_{M}\times d$
\end_inset

, 
\begin_inset Formula $U$
\end_inset

 is 
\begin_inset Formula $d\times n_{U}$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $d$
\end_inset

 latent features
\end_layout

\end_deeper
\begin_layout Itemize
EM-like algo (6.867 project)
\end_layout

\begin_deeper
\begin_layout Itemize
randomly init 
\begin_inset Formula $M$
\end_inset


\end_layout

\begin_layout Itemize
learn column 
\begin_inset Formula $i$
\end_inset

 of 
\begin_inset Formula $U$
\end_inset

 with OLS: 
\begin_inset Formula $\vec{u_{i}}=\left(\transpose MM\right)^{-1}\transpose M\vec{r_{i}}$
\end_inset

 where 
\begin_inset Formula $\vec{r_{i}}$
\end_inset

 has just known values from column 
\begin_inset Formula $i$
\end_inset

 of 
\begin_inset Formula $R$
\end_inset


\end_layout

\begin_layout Itemize
learn 
\begin_inset Formula $M$
\end_inset

 from 
\begin_inset Formula $U$
\end_inset

; iterate
\end_layout

\begin_layout Itemize
strongly overfits; can try introducing prior to prevent overfitting and
 to coerce values to be within 1 to 5
\end_layout

\begin_layout Itemize
can't run if too sparse because 
\begin_inset Formula $\left(\transpose MM\right)^{-1}$
\end_inset

 becomes singular
\end_layout

\end_deeper
\begin_layout Itemize
gradient descent 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www.quuxlabs.com/blog/2010/09/matrix-factorization-a-simple-tutorial-and-im
plementation-in-python/
\end_layout

\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $e_{ij}^{2}=\left(r_{ij}-\hat{r_{ij}}\right)^{2}=\left(r_{ij}-\sum_{k=1}^{K}p_{ik}q_{kj}\right)^{2}$
\end_inset


\end_layout

\begin_layout Itemize
gradient:
\begin_inset Formula 
\begin{eqnarray*}
\frac{\partial}{\partial p_{ik}}e_{ij}^{2} & = & -2\left(r_{ij}-\hat{r_{ij}}\right)^{2}q_{kj}=-2e_{ij}q_{kj}\\
\frac{\partial}{\partial q_{kj}}e_{ij}^{2} & = & -2\left(r_{ij}-\hat{r_{ij}}\right)^{2}p_{ik}=-2e_{ij}p_{ik}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
update rule (usu.
 
\begin_inset Formula $\alpha=.0002$
\end_inset

):
\begin_inset Formula 
\begin{eqnarray*}
p_{ik}' & = & p_{ik}+\alpha\frac{\partial}{\partial p_{ik}}e_{ij}^{2}=p_{ik}+2\alpha e_{ij}q_{kj}\\
q_{kj}' & = & q_{kj}+\alpha\frac{\partial}{\partial q_{kj}}e_{ij}^{2}=q_{kj}+2\alpha e_{ij}p_{ik}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
with regularization to avoid overfitting:
\begin_inset Formula 
\begin{eqnarray*}
e_{ij} & = & \left(r_{ij}-\sum_{k=1}^{K}p_{ik}q_{kj}\right)^{2}+\frac{\beta}{2}\sum_{k=1}^{K}\left(\norm P^{2}+\norm Q^{2}\right)\\
p_{ik}' & = & p_{ik}+\alpha\frac{\partial}{\partial p_{ik}}e_{ij}^{2}=p_{ik}+\alpha\left(2e_{ij}q_{kj}-\beta p_{ik}\right)\\
q_{kj}' & = & q_{kj}+\alpha\frac{\partial}{\partial q_{kj}}e_{ij}^{2}=q_{kj}+\alpha\left(2e_{ij}p_{ik}-\beta q_{kj}\right)
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Itemize
important extension: non-negative matrix factorization (NMF)
\end_layout

\begin_deeper
\begin_layout Itemize
require 
\begin_inset Formula $P,Q$
\end_inset

 to be non-negative
\end_layout

\end_deeper
\end_deeper
\begin_layout Subsection
Decision trees
\end_layout

\begin_layout Itemize
information gain or entropy discretization
\end_layout

\begin_deeper
\begin_layout Itemize
entropy 
\begin_inset Formula $H\left(.\right)$
\end_inset

 is information uncertainty
\end_layout

\begin_layout Itemize
in total, need 
\begin_inset Formula $H\left(Y\right)$
\end_inset

 bits to classify (e.g.
 1 bit for even 2-class distribution)
\end_layout

\begin_layout Itemize
each branch gives some information/removes uncertainty; want to move toward
 0 uncertainty
\end_layout

\begin_layout Itemize
after branching on an attr with value dist 
\begin_inset Formula $V$
\end_inset

, avg remaining uncertainty is 
\begin_inset Formula $\E_{V}\left[H\left(Y_{V}\right)\right]\le H\left(Y\right)$
\end_inset

, where 
\begin_inset Formula $Y_{v}$
\end_inset

 is class dist down branch for attr value 
\begin_inset Formula $v$
\end_inset


\end_layout

\begin_layout Itemize
choose attr w lowest remaining uncertainty, or greatest 
\emph on
information gain
\emph default
 
\begin_inset Formula $H\left(Y\right)-\E_{V}\left[H\left(Y_{V}\right)\right]$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
stopping criterion
\end_layout

\begin_deeper
\begin_layout Itemize
AIMA suggests building full tree then prune instead of early stop (eg consider
 learning xor), but this doesn't seem to be done elsewhere
\end_layout

\begin_layout Itemize
AIMA suggests chi-square test
\end_layout

\begin_layout Itemize
MDL suppose to be best-performing 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www.jair.org/media/279/live-279-1538-jair.pdf
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Subsection
Markov Chain Monte Carlo (MCMC)
\end_layout

\begin_layout Itemize
given multivariate dist, simpler to sample from conditional dists than the
 joint (hard to marginalize by integrating over joint dist)
\end_layout

\begin_layout Itemize
Gibbs sampling: initialize vars 
\begin_inset Formula $X_{i}^{\left(0\right)}\forall i$
\end_inset

, then iteratively sample 
\begin_inset Formula $X_{i}^{\left(t\right)}=P\left(X_{i}^{\left(t\right)}\mid\left\{ X_{j}^{\left(t-1\right)}\mid j\ne i\right\} \right)\forall i$
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
typically discard samples from initial 
\emph on
burn-in 
\emph default
period
\end_layout

\begin_layout Itemize
typically consider only every 
\begin_inset Formula $n$
\end_inset

 samples, since successive samples have some correlation
\end_layout

\begin_layout Itemize
useful when conditional distributions known, e.g.
 in Bayesian networks
\end_layout

\begin_layout Itemize
M-H special case where proposal dist is conditional dist; proposals accepted
 100% of time
\end_layout

\end_deeper
\begin_layout Itemize
Metropolis Hastings: (slower) generalization of Gibbs sampling for when
 conditional distributions unknown
\end_layout

\begin_deeper
\begin_layout Itemize
use 
\emph on
proposal conditional dist
\emph default
 
\begin_inset Formula $Q\left(X';X\right)$
\end_inset

, eg 
\begin_inset Formula $N\left(X,\sigma^{2}I\right)$
\end_inset

 (needn't be symmetric)
\end_layout

\begin_layout Itemize
\begin_inset Formula $a=a_{1}a_{2}=\frac{P\left(X'\right)Q\left(X^{\left(t\right)};X'\right)}{P\left(X^{\left(t\right)}\right)Q\left(X';X^{\left(t\right)}\right)}$
\end_inset

 where:
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $a_{1}=\frac{P\left(X'\right)}{P\left(X^{\left(t\right)}\right)}$
\end_inset

 is likelihood ratio btwn proposed sample 
\begin_inset Formula $X'$
\end_inset

 and prior sample 
\begin_inset Formula $X^{\left(t\right)}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $a_{2}=\frac{Q\left(X^{\left(t\right)};X'\right)}{Q\left(X';X^{\left(t\right)}\right)}$
\end_inset

 is ratio of proposal density in both directions
\end_layout

\end_deeper
\begin_layout Itemize
\begin_inset Formula $X^{\left(t+1\right)}=\begin{cases}
X' & \mbox{if \ensuremath{a\ge1}}\\
X' & \mbox{with prob \ensuremath{a}if \ensuremath{a<1}}\\
X^{\left(t\right)} & \mbox{with prob \ensuremath{1-a}if \ensuremath{a<1}}
\end{cases}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Burn-in commentary: 
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www.johndcook.com/blog/2011/08/10/markov-chains-dont-converge/
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Unsupervised learning
\end_layout

\begin_layout Itemize
K-means
\end_layout

\begin_deeper
\begin_layout Itemize
Algo: given inputs 
\begin_inset Formula $x^{\left(1\right)},\dots,x^{\left(m\right)}$
\end_inset

, repeatedly:
\end_layout

\begin_deeper
\begin_layout Itemize
update cluster assignments 
\begin_inset Formula $c^{\left(1\right)},\dots,c^{\left(m\right)}$
\end_inset

: assign each point to nearest cluster
\end_layout

\begin_layout Itemize
update cluster centroids 
\begin_inset Formula $\mu_{1},\dots,\mu_{K}$
\end_inset

 to mean of assigned points
\end_layout

\end_deeper
\begin_layout Itemize
Objective: minimize 
\emph on
distortion function
\emph default
 
\begin_inset Formula $J\left(c^{\left(1\right)},\dots,c^{\left(m\right)},\mu_{1},\dots,\mu_{K}\right)=\frac{1}{m}\sum_{i=1}^{m}\norm{x^{\left(i\right)}-\mu_{c^{\left(i\right)}}}^{2}$
\end_inset


\end_layout

\begin_layout Itemize
Use random initialization (good to initialize to 
\begin_inset Formula $K$
\end_inset

 random data points); run many times; choose clustering with min 
\begin_inset Formula $J$
\end_inset


\end_layout

\begin_layout Itemize
Choose 
\begin_inset Formula $K$
\end_inset

 at knee/elbow in curve of 
\begin_inset Formula $J$
\end_inset

 over 
\begin_inset Formula $K$
\end_inset

 (or choose based on the problem you're solving)
\end_layout

\end_deeper
\begin_layout Subsection
Infinite Mixture Models with Nonparametric Bayes and the Dirichlet Process
\end_layout

\begin_layout Itemize
nonparametric: params can change w data
\end_layout

\begin_layout Itemize
in the following
\end_layout

\begin_deeper
\begin_layout Itemize
\begin_inset Formula $n$
\end_inset

 is # diners, 
\begin_inset Formula $\alpha$
\end_inset

 is 
\emph on
dispersion param
\end_layout

\begin_layout Itemize
\begin_inset Formula $G_{0}$
\end_inset

 is base dist
\end_layout

\end_deeper
\begin_layout Itemize
Chinese restaurant process
\end_layout

\begin_deeper
\begin_layout Itemize
each new diner sits at new table w prob 
\begin_inset Formula $\frac{\alpha}{n+a}$
\end_inset

 or table 
\begin_inset Formula $k$
\end_inset

 w prob 
\begin_inset Formula $\frac{n_{k}}{n+\alpha}$
\end_inset

; call table assignments 
\begin_inset Formula $g_{i}$
\end_inset


\end_layout

\begin_layout Itemize
table 
\begin_inset Formula $k$
\end_inset

 serves some set of food parameterized by 
\begin_inset Formula $\phi_{k}\sim G_{0}$
\end_inset


\end_layout

\begin_layout Itemize
generate data points 
\begin_inset Formula $p_{i}\sim F\left(\phi_{g_{i}}\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Polya urn model
\end_layout

\begin_deeper
\begin_layout Itemize
start w urn containing 
\begin_inset Formula $\alpha G_{0}\left(\phi_{k}\right)$
\end_inset

 balls of 
\begin_inset Quotes eld
\end_inset

color
\begin_inset Quotes erd
\end_inset

 
\begin_inset Formula $\phi_{k}$
\end_inset

, for ea possible color 
\begin_inset Formula $\phi_{k}$
\end_inset


\end_layout

\begin_layout Itemize
draw ball, note color 
\begin_inset Formula $\phi_{i}$
\end_inset

, put back orig ball & new ball of same color
\end_layout

\begin_layout Itemize
generate data points 
\begin_inset Formula $p_{i}\sim F\left(\phi_{g_{i}}\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
stick-breaking process
\end_layout

\begin_deeper
\begin_layout Itemize
start w stick of length 1
\end_layout

\begin_layout Itemize
sample 
\begin_inset Formula $\beta_{1}\sim\text{Beta}\left(1,\alpha\right)$
\end_inset

; 
\begin_inset Formula $w_{1}=\beta_{1}$
\end_inset

 is the eventual proportion of customers at table 1
\end_layout

\begin_layout Itemize
sample 
\begin_inset Formula $\beta_{2}\sim\text{Beta}\left(1,\alpha\right)$
\end_inset

; 
\begin_inset Formula $w_{2}=\left(1-\beta_{1}\right)\beta_{2}$
\end_inset

 is eventual prop of customers at table 2
\end_layout

\begin_layout Itemize
generate group assignments 
\begin_inset Formula $g_{i}\sim\text{Multinomial}\left(w_{1},\dots,w_{\infty}\right)$
\end_inset


\end_layout

\begin_layout Itemize
generate data points 
\begin_inset Formula $p_{i}\sim F\left(\phi_{g_{i}}\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Dirichlet process
\end_layout

\begin_deeper
\begin_layout Itemize
generate a dist 
\begin_inset Formula $G\sim DP\left(G_{0},\alpha\right)$
\end_inset


\end_layout

\begin_layout Itemize
generate group-level params 
\begin_inset Formula $x_{i}\sim G$
\end_inset

, where 
\begin_inset Formula $x_{i}$
\end_inset

 is group param for 
\begin_inset Formula $i$
\end_inset

th data point
\end_layout

\begin_layout Itemize
generate each data point 
\begin_inset Formula $p_{i}\sim F\left(x_{i}\right)$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
inference: Gibbs sampling
\end_layout

\begin_deeper
\begin_layout Itemize
randomly init group assignments
\end_layout

\begin_layout Itemize
pick a point; fix assignments of other points; assign point to most likely
 group (existing or new)
\end_layout

\begin_layout Itemize
repeat till convergence
\end_layout

\end_deeper
\begin_layout Itemize
Indian buffet process: customers belong to multiple tables instead of just
 1
\end_layout

\begin_layout Itemize
CRP, Polya, sticks: sequential; DP: parallel
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://blog.echen.me/2012/03/20/infinite-mixture-models-with-nonparametric-bayes-a
nd-the-dirichlet-process/
\end_layout

\end_inset


\end_layout

\begin_layout Section
Natural language processing (NLP)
\end_layout

\begin_layout Subsection
Naive Bayes
\end_layout

\begin_layout Itemize
NB usu uses 
\emph on
multi-variate Bernoulli event model
\emph default
: 
\begin_inset Formula $X_{i}\sim\mbox{Bernoulli}_{c,i}$
\end_inset

 are whether dict word 
\begin_inset Formula $i$
\end_inset

 is present (for class 
\begin_inset Formula $c$
\end_inset

)
\end_layout

\begin_layout Itemize

\emph on
multinomial event model
\emph default
: better for text classif; 
\begin_inset Formula $X_{i}\sim\mbox{Multinomial}_{c}$
\end_inset

 is 
\begin_inset Formula $i$
\end_inset

th word in doc, sampled from dict (for class 
\begin_inset Formula $c$
\end_inset

)
\end_layout

\begin_deeper
\begin_layout Itemize
model: 
\begin_inset Formula $\Pr\left[D\mid\vec{\theta}_{c}\right]=\frac{\left(\sum_{i}f_{i}\right)!}{\prod_{i}f_{i}!}\prod\left(\theta_{c,i}\right)^{f_{i}}$
\end_inset

 where 
\begin_inset Formula $D$
\end_inset

 is document (this is just multinomial PMF)
\end_layout

\begin_layout Itemize
prediction: 
\begin_inset Formula $\arg\max_{c}\left[\log p\left(\vec{\theta}_{c}\right)+\sum_{i}f_{i}\log\theta_{c,i}\right]$
\end_inset


\end_layout

\begin_layout Itemize
estimation: 
\begin_inset Formula $\hat{\theta}_{c,i}=\frac{N_{c,i}+\alpha_{i}}{N_{c}+\alpha}$
\end_inset

 where 
\begin_inset Formula $\alpha=\sum_{i}\alpha_{i}$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
data skew bias: sensitive to training class dist
\end_layout

\begin_deeper
\begin_layout Itemize
fix with 
\emph on
complement NB
\emph default
: 
\begin_inset Formula $\hat{\theta}_{\tilde{c},i}=\frac{N_{\tilde{c},i}+\alpha_{i}}{N_{\tilde{c}}+\alpha}$
\end_inset

 and 
\begin_inset Formula $\arg\max_{c}\left[\log p\left(\vec{\theta}_{c}\right)-\sum_{i}f_{i}\log\theta_{\tilde{c},i}\right]$
\end_inset

 (notice the 
\begin_inset Formula $-$
\end_inset

)
\end_layout

\begin_layout Itemize
note: doesn't do anything for binary; need 3+ classes
\end_layout

\end_deeper
\begin_layout Itemize
weight magnitude errors: deal with deps like 
\begin_inset Quotes eld
\end_inset

San Francisco
\begin_inset Quotes erd
\end_inset

 vs.
 
\begin_inset Quotes eld
\end_inset

Boston
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_deeper
\begin_layout Itemize
use weight normalization 
\begin_inset Formula $\frac{\log\hat{\theta}_{c,i}}{\sum_{k}\left|\log\hat{\theta}_{c,k}\right|}$
\end_inset

 instead of 
\begin_inset Formula $\log\hat{\theta}_{c,i}$
\end_inset

 (given without much explanation)
\end_layout

\end_deeper
\begin_layout Itemize
transforms to model text more accurately based on empirical text dists
\end_layout

\begin_deeper
\begin_layout Itemize
term frequency: empirical dists were heavier-tailed than predicted by multinomia
l, more like power-law
\end_layout

\begin_deeper
\begin_layout Itemize
eg multinomial says 
\begin_inset Formula $\Pr\left[f_{i}=9\right]$
\end_inset

 (see a word 9 times) is tiny, but in reality pretty high (
\begin_inset Quotes eld
\end_inset

burstiness
\begin_inset Quotes erd
\end_inset

)
\end_layout

\begin_layout Itemize
use 
\begin_inset Formula $f_{i}'=\log\left(d+f_{i}\right)$
\end_inset

 where 
\begin_inset Formula $d=1$
\end_inset

 (or some optimized value)
\end_layout

\begin_layout Itemize
brings closer to the Bernoulli (0-1) model
\end_layout

\end_deeper
\begin_layout Itemize
document frequency
\end_layout

\begin_deeper
\begin_layout Itemize
common words unlikely to be predictive, but random variations can create
 fictitious correlations
\end_layout

\begin_layout Itemize
use 
\begin_inset Formula $f_{i}'=f_{i}\log\frac{\sum_{j}1}{\sum_{j}\delta_{i,j}}$
\end_inset

 to downweight common words where 
\begin_inset Formula $\delta_{i,j}=1$
\end_inset

 iff word 
\begin_inset Formula $i$
\end_inset

 in doc 
\begin_inset Formula $j$
\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
document length
\end_layout

\begin_deeper
\begin_layout Itemize
docs have strong inter-word deps; if word appears, likely to re-appear
\end_layout

\begin_layout Itemize
longer docs have disproportionately higher empirical term freqs/heavier
 tails; can have strong effect
\end_layout

\begin_layout Itemize
use 
\begin_inset Formula $f_{i}'=\frac{f_{i}}{\sqrt{\sum_{k}\left(f_{k}\right)^{2}}}$
\end_inset

; denom is doc length; discounts long docs; common in IR
\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://people.csail.mit.edu/jrennie/papers/icml03-nb.pdf
\end_layout

\end_inset


\end_layout

\begin_layout Section
Problems
\end_layout

\begin_layout Itemize
Solve for 
\begin_inset Formula $x$
\end_inset

 in 
\begin_inset Formula $x^{x^{x^{\dots}}}=2$
\end_inset

.
\end_layout

\begin_layout Itemize
Which is greater, 
\begin_inset Formula $e^{\pi}$
\end_inset

 or 
\begin_inset Formula $\pi^{e}$
\end_inset

? (Hint: 
\begin_inset Formula $e^{x}>1+x$
\end_inset

 for 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $x>0$
\end_inset


\family default
\series default
\shape default
\size default
\emph default
\bar default
\noun default
\color inherit
)
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status collapsed

\begin_layout Plain Layout

http://www.quantnet.com/forum/threads/quantitative-interview-questions-and-answers.
437/
\end_layout

\end_inset


\end_layout

\end_body
\end_document