\documentstyle[11pt]{article}
%\input{definitions}

\renewcommand{\baselinestretch}{1.2}
\setlength{\topmargin}{-0.25in}
\setlength{\oddsidemargin}{0.50in}
\setlength{\textwidth}{5.9in}
\setlength{\textheight}{8.5in}

\newcommand{\I}{{\bf I}}

%\input{psfig}

\begin{document}

\begin{center}
{\bf Computer Vision I: Low-Middle Level Vision  Homework Exercise \#2 }  \\ (total 10 points)   \\
Due: November 28th， 11:59 PM.
\end{center}

 
\noindent{\bf Problem 1} (Minimax entropy learning, 3 points). 

This question aims to refresh the proof process in minimax entropy learning.   Let $p(\I)$ be a FRAME model
with $K$ histograms matched to the underlying model $f(\I)$
\begin{equation}
    p(\I; \Theta) =\frac{1}{Z(\Theta)}
    \exp\{-\sum_{i=1}^K <\lambda_i, H_i(\I)>\}
\label{eq:FRAME}
\end{equation}
The parameter $\Theta=(\lambda_1, ..., \lambda_K)$ is learned so that
the following constraints are satisfied.
\begin{equation}
   E_{p}[H_i(\I)]=E_{f}[H_i(\I)]=h_i, \quad i=1,2,...,K.
\label{eq:FRAME_constraints}
\end{equation}

\begin{itemize}

\item \textbf{Q1:} Derive the following equation: 
\[  \frac{\partial \log Z}{\partial \lambda_i} = - E_p[H_i(\I)].\]

\item \textbf{Q2:} Let $\ell(\Theta)$ be the log-likelihood for one observed image $\I^{\rm obs}$,  
 prove that
\begin{eqnarray}
\frac{\partial^2 \ell(\Theta)}{\partial \lambda_i \partial \lambda_j} \
&=&  - \frac{\partial^2 \log Z}{\partial \lambda_i \partial \lambda_j} \\
&=& - E_p[(H_i(\I) - h_i)(H_j(\I) - h_j )], i,j \in \{1,2,...,K\}
\end{eqnarray}
{\em comment: Thus the second derivative of $\ell(\Theta)$ is a negative covariance matrix.  So $\ell(\Theta)$  has a single maximum solution.}

\end{itemize}


\noindent{}Now suppose we extract a new feature from the dictionary $F_+\in \Delta$, and augment the model to

\begin{equation}
    p_+(\I; \Theta_+) =\frac{1}{Z(\lambda_+)}
    \exp{-\sum_{\alpha=1}^K<\lambda_\alpha^\ast, H_\alpha(\I)> -
    <\lambda_+, H_+(\I)>}
\label{eq:FRAME_plus}
\end{equation}
The new parameter $\Theta_+=(\lambda_1^\ast, ..., \lambda_K^\ast,
\lambda_+)$ is  learned to not only satisfy the $K$ constraints specified
in equation~(\ref{eq:FRAME_constraints}), but also an extra condition:
\begin{equation}
   E_{p_+}[H_+(\I)]=E_{f}[H_+(\I)]=h_{+}.
\label{eq:Constraint_plus}
\end{equation}
Note: To match all the $K+1$ statistical constraints, the existing parameters  ($\lambda_\alpha \rightarrow \lambda_\alpha^\ast, i=1,2,..., K$) must be updated when we introduce new features (marginal) because all features are correlated. 

\begin{itemize}
\item  \textbf{Q3:} Derive the steps for proving the following theorem
\[
    KL(f||p)-KL(f||p_+) = KL(p_+ || p) .
\]
\end{itemize}


\noindent{\bf Problem 2}  (Learning by information projection, 2 points )

 Suppose that we are learning the underlying probability model $f(\I)$ of image $\I$. We start with an initial  probability model, denoted as $q(\I)$, and observe that $q(\I)$ has a different marginal probability over a macroscopic feature $H_i(\I)$:
\[
      E_q[H_i(\I)] \neq E_f[H_i(\I)] = h_i,
\] 
where $h_i$ is estimated from a set of examples sampled from $f(\I)$. To improve the current model, we learn a new probability model $p(\I)$
so that it reproduces this marginal statistics feature ($p(\I)$ may not necessarily replicate all the marginal probabilities that model $q(\I)$ has matched previously). We denote the set of models that satisfy this constraint equation by,
\[
  \Omega_i  = \{ p:   E_p[H_i(\I)] =  E_f[H_i(\I)] = h_i. \}
\] 
Now, among all the $p(\I)$  in $\Omega_i$, we choose one that is closest to $q(\I)$ so that it preserves the learning history. 
 \[
   p^\ast = \arg \min_{p\in \Omega_i} KL(p||q)  = \arg \min_{p\in \Omega_i}  \int p(\I) \log \frac{p(\I)}{q(\I)} d\I.
\]
\begin{enumerate}
\item Derive the formula of $p(\I)$ by leveraging the Euler-Lagrange equation (Tips: (I) constrained optimization).

\item Prove that $ KL(f|| q) - KL(f||p) = KL(p||q)$. (Remark: Since $D(p||q) >0$,  $p$ is closer to $f$ than $q$).

\item Show that this optimization satisfies the maximum entropy principle when $q(\I)$ is a uniform distribution.
\end{enumerate}


\vspace{5mm}
\noindent{\bf Problem 3}    (Information projection, 3 points)  


Considering the feature pursuit in a
family of models,
\[ p_0(x) \to p_1(x) \to \cdots \to p_K(x) \quad
\sim \; f(x). \]
where
\[
p_K(x; \Theta_K) = \frac{1}{Z_K}  \exp \{- \sum_{i=1}^K \lambda_i
h_i(x)\}.
\]
For simplicity, we treat $\lambda_i$ as a scalar rather than a
vector.

 In the minimax entropy process, when we add a new feature
statistics $h_{K}(x)$, we need to update all the parameters
$\lambda_i=1, ...,K$ in the new model $p_{K}(x;\Theta_{K})$
 by MLE, so that all the $K$ constraint equations are
 satisfied,
\[
 E_{p_{K}}[h_i(x)] = h_i^{\rm obs}, \quad i=1,2,...,K.
\]

In a different method, we can pursue a series of models in the
following way,
\[
    q_0(x) \to q_1(x) \to \cdots \to q_K(x) \quad
\sim \; f(x).
\]
with
\[ q_{K}(x) = \frac{1}{z_{K}} q_{K-1}(x)
\exp\{- \beta_{K} h_{K}(x)\}.
\]
In this model, $\beta_{K}$ is decided by the new constraint
\[
   E_{q_{K}}[h_{K}(x)] = E_{f}[h_{K}(x)] \approx  h_{K}^{\rm obs}.
\]
In comparison to the previous p-series, the q-series observes the
constraints one-by-one, and fixes the previous parameters $\beta_i,
i=1,2,...,K-1$ when we learn $\beta_{K}$, i.e.
\[
q_{K}(x; ) = \frac{1}{z_1 z_2\cdots z_K} q_o(x) \exp \{-
\sum_{i=1}^K\beta_i h_i(x)\}.
\]
\begin{enumerate}
\item  For the q-series, derive the formula for $\frac{\partial \log z_K}{\partial \beta_k}$.

\item  Suppose we denote by $Z_K = z_1 z_2\cdots z_{K-1}$ as the normalizing function for $q_K(x)$,
  derive $\frac{\partial^2 \log Z_K}{\partial \beta_i \partial
\beta_j}, \; \forall i,j \leq K$.

\item  Prove that  $KL(f|| q_K) - KL(f||q_{K+1}) =KL(q_{K+1} || q_K) \geq 0$, and prove the $q$-series  will converge to $f$
\end{enumerate}

\vspace{5mm}
\noindent{\bf Problem 4}    (Typical set, 2 points)  
 
 Suppose we toss a coin $N$ times and observe a $0/1$  sequence (for head and tail respectively),
\[
  S_N =( x_1, x_2, ..., x_N ), \quad x_i \in \{0, 1\}.
\]
$S_N$ is said to be of {\em  type $q$} (i.e. the frequency of $1$ is $q$
in the sequence) with $q = \frac{1}{N} \sum_{i=1}^N  x_i.$

 Let $\Omega(q)$ be the set of all sequences $S_N$ of type $q$. For simplicity, we discretize $q$ to finite precision.

\begin{enumerate}
\item What is the cardinality  of $\Omega(q)$ for $q=0.2$ and $q=0.5$
respectively? (Suppose we only care about the exponential order or
rate).

\item Suppose we know that the underlying probability is $x_i=1$ (or $x_i=0$) with probability $p$ (or $1-p$ respectively),  by sampling from this probability $N$ times, what is the probability  $p(S_N)$ that we observe a sequence $S_N \in \Omega(q)$?   What is the total probability mass $p(\Omega(q))$ for all the sequences in set $\Omega(q)$?

\item In the above question, show that as $N\rightarrow \infty$, only sequences from the type $p$, i.e. set $\Omega(p)$,  can be observed. 
\end{enumerate}

\end{document}


\vspace{5mm}
\noindent{\bf Question 4}   (And-Or graph, 3 points) 
 In a stochastic grammar, we have the following production rules
 (upper case for non-terminal nodes and lower case for terminal nodes, the numeric number are the branching
 probabilities, the probability is 1.0 when there is only 1 branch).
\begin{eqnarray*}
    S  & & \rightarrow AB    \\
    A  & & \rightarrow GH \, |\,  D ,  \quad  0.6 \, | \, 0.4 \\
    B & & \rightarrow E \, | \, F, \quad  0.3 \, | \, 0.7\\
    G  & & \rightarrow a, \quad  D  \rightarrow d, \quad E \rightarrow e, \quad F \rightarrow f \\
    H & &  \rightarrow b\, |\, c \quad 0.2   \, | \, 0.8
\end{eqnarray*}

\begin{enumerate}
\item  Transfer this context-free grammar in An And-Or tree (AoT) representation.

\item  How many valid sentences are in the language of this grammar ?  List all of them.

\item  What is the probability for a sentence $ace$?

\item  Suppose we write the probability of a parse tree as $p(tr)$, and we augment the AOT to an And-Or graph (AOG) by adding context information.  For example, it is observed that when $A$ is instantiated by $d$, then  $B$ is more likely to be instantiated by $e$ (or $f$) with frequency to be $0.45$ (or $0.55$ for $B$ to be instantiated by $f$) rather than $0.30$  in the AoT.  Derive a new probability for this AOG (following the information projection procedure) to account for this constraint. Note that this probability is defined on the parse graphs $pg$. 

\item State an algorithm for learning the augmented model above? 

\end{enumerate}

\end{document}











\vspace{1cm}
\noindent{\bf Question 3}.  Now suppose that someone tries to learn the parameters $\Theta$ in the probability
$p(\I; \Theta)$ above  from a set of independent  examples
\[
   D=\{ \I_1, \I_2, ..., \I_M \},
\]
by  maximum likelihood estimate (MLE). That is, we take the log-likelihood of the data as
\[
    \ell(\Theta) = \sum_{i=1}^M \log p(\I_i; \Theta)
\]
To find the best $\Theta$ that maximizes $\ell(\Theta)$, i.e.
\[
     \Theta^* = \arg\max \ell(\Theta).
\]
 One sets $\frac{\partial\ell(\Theta)}{\partial \lambda_i}=0$ for $i=1,2,...,K$.

\begin{enumerate}
\item Derive the $K$ equations $\frac{\partial\ell(\Theta)}{\partial \lambda_i}=0, \;\; i=1,2,...,K$.

\item Compare the $K$ equations with the $K$ constraints. Discuss the relation of the 2 sets of equations.
\end{enumerate}

\vspace{1cm}
\noindent{\bf Question 4}. Experiment. Let's revisit the probability model $p(\I)$ in HW 1 that observes the
$1/f$ law. Rewrite it in discrete form,
\[
     p(\I) = \frac{1}{Z} \exp\{- \frac{1}{2\sigma^2} \sum_{(x,y)\in \Lambda} (\nabla_x \I)^2 + (\nabla_y \I)^2 \}.
\]

\begin{enumerate}
\item What is the constraint equations in maximum entropy that lead to the above Gibbs model?

\item State verbally, what does the 1/f-law means afterall?

\item Derive the local characteristics $p(x_s|x_{\partial s})$, following question 1.

\item Design a code to simulate images from this model $\I \sim p(\I)$. To save computational time,
suppose we sample a small image of $128 \time 128$ pixels normalized to $8$ grey levels $\{0,1,...,7\}$
Suppose we assume a torus boundary condition, the algorithm iterates the following step:

 For $(x,y)\in \Lambda$ (you may visit the pixel $(x,y)$ in any order), we sample its intensity according to
 the local characteristics
 \[
    x_s \sim p(x_s|x_{\partial s}), \quad  s\in \Lambda, \quad {\rm set} \; \sigma^2=2.
 \]
 When you visit all pixels in $\Lambda$ once, it is called a "sweep". Try to run the algorithm
 100 sweeps, starting from $\I$ being a white noise image.  Save the intermediate results at
  0, 20, 40, 60, 80, 100 sweeps. Print it out. When you visualize it, you multiple $8$ for each pixel to $\{0, 32, 64, ..., 224\}$.  Compare this image with the $1/f$-law image that I got in the note.
Should they be almost the same?

\end{enumerate}

\end{document}

 \noindent{\bf Question 1}. (Hammersley-Clifford
theorem, 2 points )     

For a Gibbs field on a lattice $\Lambda$ with neighborhood system $\partial$.
\[   \pi(X) = \frac{1}{Z} \exp^{- H(X)}\]
$H(X)$ is a clique potential
\[
    H(X) = \sum_{c\in C} U_c(X_c).
\]
\begin{enumerate}
\item Derive the local characteristics (i.e. conditional probability) $\pi(X_A | X_{\bar{A}})$ and show that it is a
Markov random field model,
 \[ \pi(X_A | X_{\bar{A}}) = \pi(x_A |x_{\partial A}),  \quad  \forall A \subset
 \Lambda. \]


\item Derive the above local characteristics $\pi(X_s|X_{\partial s} )$ for a special example with $4$ nearest neighbor connection on a single site $s\in \Lambda$
 \[ H(X) = \sum_{s\in \Lambda} \phi(x_s) + \sum_{<s,t>} \psi(x_s, x_t)\]
\end{enumerate}

\noindent{\bf Problem 2}. This question studies the feature pursuit
process in minimax entropy distribution. Let $p(\I)$ be a Gibbs model
with $K$ histograms matched to the underlying frequency $f(\I)$
\begin{equation}
    p(\I; \Theta) =\frac{1}{Z(\Theta)}
    \exp\{-\sum_{i=1}^K\lambda_iH_i(\I)>\}
\label{eq:FRAME}
\end{equation}
The parameter $\Theta=(\lambda_1, ..., \lambda_K)$ is learned so that
the following constraints are satisfied.
\begin{equation}
   E_{p}[H_\alpha(\I)]=E_{f}[H_\alpha(\I)]=h_\alpha, \quad \alpha=1,2,...,K.
\label{eq:FRAME_constraints}
\end{equation}
Now suppose we add a new feature from a dictionary $F_+\in \Delta$, and augment the model to
\begin{equation}
    p_+(\I; \Theta_+) =\frac{1}{Z(\lambda_+)}
    \exp{-\sum_{\alpha=1}^K<\lambda_\alpha^\ast, H_\alpha(\I)> -
    <\lambda_+, H_+(\I)>}
\label{eq:FRAME_plus}
\end{equation}
The new parameter $\Theta_+=(\lambda_1^\ast, ..., \lambda_K^\ast,
\lambda_+)$ is  learned so that $p_+$ satisfies the $K$ constraints
in eqn~(\ref{eq:FRAME_constraints}) plus one extra condition,
\begin{equation}
   E_{p_+}[H_+(\I)]=E_{f}[H_+(\I)]=h_{+}.
\label{eq:Constraint_plus}
\end{equation}
Note that the previous parameters must be updated ($\lambda_\alpha \rightarrow \lambda_\alpha^\ast, i=1,2,...,K$) when we introduce new features (marginal) because all features are correlated. Therefore
 $\lambda_\alpha^\ast$ is a function of $h_+$.
It is desirable to choose $F_+$ (and thus $h_+$) so that $p_+$
approaches $f(\I)$ as fast as possible.
\[
    h_+^\ast = \arg\max_{F_+ \in \Delta} D(h_+), \quad D(h_+)= KL(f||p)-KL(f||p_+).
\]

\begin{enumerate}
\item  Derive the steps for the following conclusion.
\[
    KL(f||p)-KL(f||p_+) = KL(p_+ || p) = entopy(p) - entropy(p_+).
\]
What is your explanation of the above conclusion?


\item Suppose we expand the function $D(h_+)$ by Taylor expansion at
$h_o=E_p[H_+(\I)]$. For simplicity, we assume $\lambda_\alpha$ and $h_\alpha$ are scalars.
\[
    D(h_+) = D(h_o) + \frac{d D(h_o)}{dh_+}(h_+ -h_o)
    +\frac{1}{2}\frac{d^2 D(h_+)}{dh_+^2}(h_+ -h_o)^2 + O(\epsilon).
\]
 Calculate $\frac{d D(h_o)}{dh_+}$?

\end{enumerate}

\vspace{1cm}

\noindent{\bf Problem 3}. Consider an iid coin sequence with $N$
sufficiently large,
\[
  \pi_N =\{ x_1, x_2, ..., x_N \}, \quad x_i \in \{0, 1\}.
\]
$\pi_N$ is said to be of type $q$ (i.e. the frequency of $1$ is $q$ in the sequence) if
\[
      q = \frac{1}{N} \sum_{i=1}^N  x_i.
\]
 Let $\Omega(q)$ be the set of all sequences $\pi_N$ of type $q$.

\begin{enumerate}
\item What is the cardinality  of $\Omega(q)$ for $q=0.1$ and $q=0.5$
respectively? (we only care about the exponential order)

\item Suppose we know the underlying probability is $x_i=1$ (or $x_i=0$) with probability $p$ (or $1-p$
respectively),  what is the probability  $p(\pi_N)$ that we observe a sequence
$\pi_N \in \Omega(q)$?  What is the total probability mass $p(\Omega(q))$ for the
set $\Omega(q)$?

\item In the above question, show that as $N\rightarrow \infty$,
only sequences from the type $p$, i.e. set $\Omega(p)$,  can be observed.

\item Explain the intuitive meaning of this limit.
\end{enumerate}

\vspace{1cm}

\noindent{\bf Problem 4}.  Now let's combine the conclusions in 2-3
above. We know that the conclusion in problem 2 can be extended to
non-iid sequences, such as images $\I$.

  Suppose that by adding a new feature $F_+$ we have the difference
of histograms
\[
    D(h_+) \approx \frac{1}{2} |\Lambda| \cdot ||h_+ -h_o||=0.25 |\Lambda|.
\]
$\Lambda$ is the lattice, $|| \cdot ||$ is the absolute value. That is
the entropy is reduced by $0.25$ bits per pixel.

 If we denote by $\Omega_p$ the space that $p$ is focused on.
 What is the ratio of $\frac{|\Omega_p|}{|\Omega_{p_+}|}$?

\vspace{1cm}

\noindent{\bf Problem 5}. Pseudo-likelihood.

\begin{enumerate}
\item Consider a simple Ising model on a torus,
\[
     p(\I; \alpha, \beta) =\frac{1}{Z} \exp\{ -\alpha \sum_s \I_s - \beta \sum_{<s,t>} \I_s \cdot \I_t \},  \;\; \I_s \in \{-1, 1\}.
\]
Formulate the log-Pseudo-likelihood $\ell(\alpha,\beta)$.

\item Derive the equation for the maximum pseudo-likelihood estimate,
i.e.,
\[
     \frac{\partial \ell}{\partial \alpha}=0, \quad
     \frac{\partial \ell}{\partial \beta}=0.
\]

\end{enumerate}



\end{document}
