Hierarchical Dirichlet Processes

by Yee Whye Teh, Michael I. Jordan, Matthew J. Beal and David Blei

This paper is relevant to hierarchical modeling of MoE (hence related to HMoE). The DP extension for mixture model has been studied in this paper (with variational approximation methods) too. This paper only use Monte Carlo methods for inference (instead of approximation algorithms). They simply introduce one DP prior for parameters of the model that generates the data and another DP prior for the generation of groups. In one word,

G_0 \mid \gamma, H \sim \mathrm{DP}( \gamma, H ), G_j \mid \alpha_0, G_0 \sim \mathrm{DP}( \alpha_0, G_0), \theta_{ji} \sim G_j, x_{ji} \sim F(\theta_{ji}).

Their idea of DP is implemented with SBP (as in this paper). However, we can only observe x_i. For a learning problem we must find a proper settings for \gamma and \alpha_0. For inference, we must get the posterior distribution of two DPs. Please notice for a DP MoE, the base distribution of the DP is on the parameter space; now in HDP, the base distribution of the intermediate DP is a random measure, which is the top DP. Therefore the base distribution of the top DP is on the parameter space: the sampling from the top DP results in \sum_{k = 1}^K \frac{m_k}{m + \gamma}\delta_{\phi_k} + \frac{\gamma}{m + \gamma} H where m_k is the number of samples with \phi_k values and \phi_k are drawn from H, m=\sum_{k=1}^K m_k; the intermediate DP put these samples \theta_i in groups according to \sum_{t = 1}^T \frac{n_t}{i-1 + \alpha_0} \delta_{\psi_t} + \frac{\alpha_0}{i-1 + \alpha_0} G_0, where n_t is the number of samples in this group and T is the number of groups.

Now we come to the details:

• The SBP generates a set of v_i, \pi_i and \theta_i in the following way,

  v_i \sim \mathrm{Beta}(1, \alpha), \quad \pi_i = v_i \prod_{k = 1}^{i - 1}(1 - v_i), \quad \theta_i \sim G, \quad \Pr(\theta = \theta_i) = \pi_i

  This is equivalent to a DP whose parameter is \alpha and G. Then we may generate the data according to this.
• The HDP can be formulated as a variant of CRP, Chinese restaurant franchise: a customer chooses a dish (being served or not) and sits at a table (serving the dish or a new one). We can dormulate the generation as follows: a customer \theta_i comes into the restaurant and will sit at a table according to the intermediate DP and asks for a dish (if it is a new table) according to the top DP.
• For inference, we use SBP formulation and calculate the posterior of the hidden r.v.s. Ad we may see in the SBP formulation, we need an indicator (multinomial distribution) for one DP. The sampling is done with Gibbs sampler.
• It can be used for enhancing LDA (latent Dirichlet allocation) and HMM.
  

Random Projection for Manifold Learning

by Chinmay Hedge and Michael B. Wakin and Richard G. Baraniuk

This paper tells us that we may project the data from a higher dimensional space (n dimensions) into a random subspace (m dimensions) and we will not lose much information of the intrinsic structural information. Therefore we may apply one of the manifold learning algorithms to the randomly-projected data and still recover their structure in a proper space (d dimensions). And d < m << n and m = O(d log n).

The first theorem comes from RIP satisfaction, when

m \geq O\left( \frac{d \log (n V \tau^{-1}) \log(\rho^{-1})}{\epsilon^2}\right)

with probability no less than 1-ρ, for any x, z, we have

(1 - \epsilon) \sqrt{\frac{m}{n}} \leq \frac{d_i( \Phi x, \Phi z)}{d_i( x, z )} \leq (1 - \epsilon) \sqrt{\frac{m}{n}},

where Φ is the random orthogonal projection, V is the volume and 1/τ is the condition number of the latent manifold. To estimate the intrinsic dimensions, the author propose to employ Grassberger-Procaccia algorithm (based on correlation). They found bounds for the estimated dimensions: when

m \geq O\left( \frac{d \log( n V \tau^{-1}) \log (\rho^{-1})}{\beta^2 \delta^2} \right),

then the estmated correlation dimension satisfies

(1 - \delta) \hat{d} \leq \hat{d}_\Phi \leq (1 + \delta) \hat{d},

with probability exceeding 1-ρ. And the residual variance of the ISOMAP embedding is also bounded

R_\Phi \leq R + C \Gamma^2 \epsilon,

where Γ is the diameter of the point cloud.

Since in practice we are not sure about the intrinsic dimensionality, we usually try to add more orthogonal vectors and see whether the residual variance is small enough.

Well it is atypical way of applying CS in machine learning. Put all data in a random projection subspace and prove there are bounds for later learning algorithms. It is not the way I'd like to use CS.

Hierarchical Mixtures of Experts and the EM Algorithm

by Michael I. Jordan and Robert A. Jacobs

This paper formulates HMoE, which can be regarded as a soft decision tree. Each leaf node is an expert, which is usually a GLIM and whose parameters are to be estimated. The internal nodes are soft partitions (something like a multinomial regression, the number of classes equals the number of children). Therefore each internal node actually corresponds to a hidden r.v. whose parameters (the coefficients for inner product) are to be estimated. On a whole the model is a Bayesian belief network (a poly-tree?). The training of this kind of model can be done with EM algorithm and the posterior of the hidden variables must be calculated (via belief propagation, a typical inference problem). This is an old paper, which was wrongly picked out -,-b

Mixture-of-Parents Maximum Entropy Markov Models

by David S. Rosenberg, Dan Klein and Ben Taskar

Like skip-chain CRF, the mixture-of-parent MEMM also aims at utilizing the long-range interactions for NER problems. Skip-chain CRF, though, is beautiful in theory. The inference on it cannot be easily carried out (there are loops). This paper adds directed edges to the same r.v.s but with the assumption that Pr( y | pa(y) ) is a mixture of Pr( y | y') where y' in pa(y) (please note that x is omitted in this formulation and here we refer to a single element). With this, the conditional probability Pr(y | x) can still be calculated with dynamic programming (now we have to sum over all parents as well and here we refer to a sequence).

The tricky part they employed is the mixing proportion of the parent is assumed to be known as equal for one r.v. Then they can get a convex optimization problem which can be solved just as MEMM. By computing the gradient, L-BFGS can be applied. They actually have another objective (log conditional margins instead of log joint conditional) which is non-convex but it is well-behaved in practice.

Infinitely Imbalanced Logistic Regression

by Art B. Owen

This paper studies the case of binary classification when we have a fixed set of samples from positive class but infinite samples from negative class. Their main result is formulated in the following theorem:
Let n >= 1 and x_i in R^d be fixed and suppose that F₀ satisfies rhe tail condition

\int e^{x^\top \beta}( 1 + \| x\|) \,\mathrm{d} F_0(x) < \infty, \qquad \forall \beta \in \mathbb{R}^d

and surrounds

\bar{x} =\frac{1}{n} \sum_{i = 1}^n x_i.

Then the maximizer of the centered log-likelihood satisfies

\lim_{N \to\infty} \frac{\int e^{x^\top \beta} x \,\mathrm{d} F_0(x)}{\int e^{x^\top \beta}\,\mathrm{d} F_0(x)} = \bar{x}.

This theorem tells us several important things:

• There are two conditions we must satisfy if β does not diverge, either of which once violated will yield a counterexample (β will diverge).
• The convergent β only relates to the positive samples via their mean. Therefore it does NOT really matter how their are distributed.
• The author suggests this may be good for understanding the behavior of logistic regression and by removing the outlier or moving it towards the mean we can get a better model.
• If F₀(x) is a Gaussian or a mixture of Gaussians, β can be calculated as in LDA (the generative counterpart).
  

This is actually written by a stat guy and involves more derivations than other pure machine learning papers. This is quite interesting. I'd like to explore some theoretical properties of simple models but up to now I haven't found a proper point.

Compressive Sampling

by Emamnuel J. Candès

This is the first paper I read about compressive sampling (a.k.a. compressed sensing). The main idea of CS is that we have a measure matrix Φ and a different representation matrix Ψ and they are quite different. The traditional way of signal processing would use the same matrix for measurement and representation. The Nyquist-Shannon theorem says we need a bandwidth as large as the connected support in Φ-domain. But in practice our signal is usually sparse in Ψ-domain but the sparse weights are not in a connected subset of the whole space. Therefore to apply N-S thereom, we need a large bandwidth to transmit the data. But then we might think we might miss the sparsity point.

The new findings in CS say that if the measurement Φ satisfies a certain condition, we might recover the sparse encoding in Ψ-domain with a linear programming solver:

min | x |₁ subject to ΦΨx=y

where y is the measurement of the groundtruth (i.e. Φf, where f is the original signal).

The measurement matrix Φ must satisfy the UUP (uniform uncertainty principle) or RIP (restricted isometry principle). To put it simple, it means that any subset of coordinates (cardinality less than S) under the transform of the corresponding part of Φ will keep the norm in a certain bound. This bound implies when the exact decoding will be successful. Many stochastic matrix can be candidates for Φ, e.g. Gaussian, binary, Fourier (randomly selected rows of Fourier transform), incoherent measurement (randomly selected rows of random orthoganal matrix). Experts are busy proving how few rows we need for exact decoding. That is to prove a tight upper bound for S(sparsity of Ψ-domain) with N(length of the signal) and K(number of measurements, #rows of Φ).

It can be proved that the recovered x is optimal in a sense. This idea can still be extend to the case of signal with noise.

There are research of CS in machine learning, exploiting the sparsity part. Since as SVM or RVM suggests, the classifier in the dual representation should be sparse. Therefore it seems possible to train a model in a randomly projected space without losing information. There has been work in this part. I will explore more about it later. For now we just need their idea.

Exponential Family for Conditional Random Fields

by Yasemin Altun, Alex J. Smola and Thomas Hofmann

This paper is from UAI 2004, theoretical version of the ICML 2004 paper previously scanned here. The concepts of CRF, RKHS, exponential family and GP. But in a sense I don't think this paper is of much interest (lots of results are known in books I guess). The important section is the optimization. Come back later when I try GP (soon~).