\( % groupings of objects. \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\seq}[1]{\left(#1\right)} \newcommand{\ang}[1]{\langle#1\rangle} \newcommand{\tuple}[1]{\left(#1\right)} \newcommand{\size}[1]{\left| #1\right|} \newcommand{\comp}{\circ} % numerical shortcuts. \newcommand{\abs}[1]{\left| #1\right|} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} % linear algebra shortcuts. \newcommand{\change}{\Delta} \newcommand{\norm}[1]{\left\| #1\right\|} \newcommand{\dprod}[1]{\langle#1\rangle} \newcommand{\linspan}[1]{\langle#1\rangle} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\der}[1]{\frac{d#1}{dx}} \newcommand{\lap}{\Delta} \newcommand{\kron}{\otimes} \newcommand{\nperp}{\nvdash} \newcommand{\mat}[1]{\left[ \begin{smallmatrix}#1 \end{smallmatrix} \right]} % derivatives and limits \newcommand{\partder}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\partdern}[3]{\frac{\partial^{#3 #1}}{\partial #2^{#3}}} \newcommand{\gradient}{\nabla} \newcommand{\subdifferential}{\partial} % Arrows \newcommand{\diverge}{\nearrow} \newcommand{\notto}{\nrightarrow} \newcommand{\up}{\uparrow} \newcommand{\down}{\downarrow} % gets and gives are defined! % ordering operators \newcommand{\oleq}{\preceq} \newcommand{\ogeq}{\succeq} % programming and logic operators \newcommand{\dfn}{:=} \newcommand{\assign}{:=} \newcommand{\co}{\ co\ } \newcommand{\en}{\ en\ } % logic operators \newcommand{\xor}{\oplus} \newcommand{\Land}{\bigwedge} \newcommand{\Lor}{\bigvee} \newcommand{\finish}{\Box} \newcommand{\contra}{\Rightarrow \Leftarrow} \newcommand{\iseq}{\stackrel{_?{=}}} % Set theory \newcommand{\symdiff}{\Delta} \newcommand{\setdiff}{\backslash} \newcommand{\union}{\cup} \newcommand{\inters}{\cap} \newcommand{\Union}{\bigcup} \newcommand{\Inters}{\bigcap} \newcommand{\nullSet}{\phi} % graph theory \newcommand{\nbd}{\Gamma} % Script alphabets % For reals, use \Re % greek letters \newcommand{\eps}{\epsilon} \newcommand{\del}{\delta} \newcommand{\ga}{\alpha} \newcommand{\gb}{\beta} \newcommand{\gd}{\del} \newcommand{\gp}{\pi} \newcommand{\gf}{\phi} \newcommand{\gh}{\eta} \newcommand{\gF}{\Phi} \newcommand{\gl}{\lambda} \newcommand{\gm}{\mu} \newcommand{\gn}{\nu} \newcommand{\gr}{\rho} \newcommand{\gs}{\sigma} \newcommand{\gth}{\theta} \newcommand{\gx}{\xi} \newcommand{\gw}{\omega} \newcommand{\sw}{\sigma} \newcommand{\SW}{\Sigma} \newcommand{\ew}{\lambda} \newcommand{\EW}{\Lambda} \newcommand{\Del}{\Delta} \newcommand{\gD}{\Delta} \newcommand{\gG}{\Gamma} \newcommand{\gW}{\Omega} \newcommand{\gS}{\Sigma} \newcommand{\gTh}{\Theta} % Bold english letters. \newcommand{\bA}{\mathbf{A}} \newcommand{\bB}{\mathbf{B}} \newcommand{\bC}{\mathbf{C}} \newcommand{\bD}{\mathbf{D}} \newcommand{\bE}{\mathbf{E}} \newcommand{\bF}{\mathbf{F}} \newcommand{\bG}{\mathbf{G}} \newcommand{\bH}{\mathbf{H}} \newcommand{\bI}{\mathbf{I}} \newcommand{\bJ}{\mathbf{J}} \newcommand{\bK}{\mathbf{K}} \newcommand{\bL}{\mathbf{L}} \newcommand{\bM}{\mathbf{M}} \newcommand{\bN}{\mathbf{N}} \newcommand{\bO}{\mathbf{O}} \newcommand{\bP}{\mathbf{P}} \newcommand{\bQ}{\mathbf{Q}} \newcommand{\bR}{\mathbf{R}} \newcommand{\bS}{\mathbf{S}} \newcommand{\bT}{\mathbf{T}} \newcommand{\bU}{\mathbf{U}} \newcommand{\bV}{\mathbf{V}} \newcommand{\bW}{\mathbf{W}} \newcommand{\bX}{\mathbf{X}} \newcommand{\bY}{\mathbf{Y}} \newcommand{\bZ}{\mathbf{Z}} \newcommand{\bba}{\mathbf{a}} \newcommand{\bbb}{\mathbf{b}} \newcommand{\bbc}{\mathbf{c}} \newcommand{\bbd}{\mathbf{d}} \newcommand{\bbe}{\mathbf{e}} \newcommand{\bbf}{\mathbf{f}} \newcommand{\bbg}{\mathbf{g}} \newcommand{\bbh}{\mathbf{h}} \newcommand{\bbk}{\mathbf{k}} \newcommand{\bbl}{\mathbf{l}} \newcommand{\bbm}{\mathbf{m}} \newcommand{\bbn}{\mathbf{n}} \newcommand{\bbp}{\mathbf{p}} \newcommand{\bbq}{\mathbf{q}} \newcommand{\bbr}{\mathbf{r}} \newcommand{\bbs}{\mathbf{s}} \newcommand{\bbt}{\mathbf{t}} \newcommand{\bbu}{\mathbf{u}} \newcommand{\bbv}{\mathbf{v}} \newcommand{\bbw}{\mathbf{w}} \newcommand{\bbx}{\mathbf{x}} \newcommand{\bby}{\mathbf{y}} \newcommand{\bbz}{\mathbf{z}} \newcommand{\0}{\mathbf{0}} \newcommand{\1}{\mathbf{1}} % Caligraphic english alphabet \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cT}{\mathcal{T}} \newcommand{\cU}{\mathcal{U}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cW}{\mathcal{W}} \newcommand{\cX}{\mathcal{X}} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} % Formatting shortcuts \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\blue}[1]{\textcolor{blue}{#1}} \newcommand{\htext}[2]{\texorpdfstring{#1}{#2}} % Statistics \newcommand{\distr}{\sim} \newcommand{\stddev}{\sigma} \newcommand{\covmatrix}{\Sigma} \newcommand{\mean}{\mu} \newcommand{\param}{\theta} \newcommand{\gthEst}{\hat{\theta}} \newcommand{\ftr}{\phi} \newcommand{\est}[1]{\hat{#1}} % General utility \newcommand{\todo}[1]{\textbf{[TODO]}] \footnote{TODO: #1}} \newcommand{\tbc}{[\textbf{Incomplete}]} \newcommand{\chk}{[\textbf{Check}]} \newcommand{\why}{[\textbf{Find proof}]} \newcommand{\opt}[1]{\textit{#1}} \newcommand{\experience}[1]{[\textbf{Personal Experience}]: #1 \blacktriangle} \newcommand{\pf}[1]{[\textbf{Proof}]: #1 \Box} \newcommand{\core}[1]{\textbf{Core Idea}: #1 \Arrowvert} \newcommand{\example}[1]{\textbf{Example}: #1 \blacktriangle} \newcommand{\error}[1]{\textbf{Error alert}: #1 \triangle} \newcommand{\oprob}{[\textbf{OP}]: } \renewcommand{\~}{\htext{$\sim$}{~}} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max} \)

Inference

Here we only consider inference by sampling. Inference techniques particular to various model classes are considered elsewhere.

Inference problems

Find Pr(X=x) or \(Pr(X=x|Y=y)\). Inference algorithms may be exact or approximate.

Or find E[X] or \(E[X|Y=y]\).

Or find the mode of \(Pr(X=x|Y=y)\): as done in case of Maximum likelihood estimation.

Difficulty in calculating Pr(X=x)

Pr(X=x) can be difficult to calculate analytically. One could specify \(Pr(X=x) = Z^{-1}f(x)\) by leaving the normalization constant Z unspecified, and describing only \(f(x)\).

Similarly, \(Pr(X=x|Y=y)\) can involve solving the ‘summation problem’.

Can be difficult due to not knowing the normalization constant.

Often probability of an event T cannot be estimated analytically, even when probability of an atomic event is known. Eg: Consider uniform density over a bounded space in \(R^{d}\), consider an irregular shape in it representing event T; now find Pr(T). Ye can throw darts/ sample to find the area (Monte carlo!). Or construct a grid to calculate the volume of the irregular shape: but here the computation will be \(N^{d}\), where N is number of grid points in each dimension.

Inference by sampling

Rejection sampling

To find \(E[f(X)|E_1]\), Sample from distribution of X, reject samples for which \(\lnot E_1\), then use remaining points to find avg f(X).

Set counting techniques

Design sample space, sample m times to estimate event probability.

Maybe iteratively constrict sample space and multiply probabilities, derive number of events: Thus, one finds \\(Pr(E_{1}), Pr(E_{2}| E_{1}) ..\) finally finding \(Pr(Y|E_{1} .. )\); thence finding Pr(Y).

Inference quality

FPRAS for (eps, d) approx.

RAS: Randomized approximation scheme. Suppose \(Pr(|m^{-1}\sum^{m}_{i=1} (X-\mu)|\geq \epsilon \mu) \leq d\). If \(m\) is FP (Fully Polynomial) in \(\ln(\frac{2}{d}), \epsilon^{-2}, |x|\), we have a FPRAS. From Chernoff bound : \(m \geq \frac{3\ln(\frac{2}{d})}{\epsilon^{2}\mu}\).

Fully poly almost uniform samplers (FPAUS)

\tbc