Data Science PT 12: Integer Programming/NonConvex Optimization

An integer program is an optimization problem where some/all variables must be integers.

Here, we have slack variables S. Support set detection is where we set y=Ax+z, want support set. The algorithm is as follows: 

However integer linear programs are shown to be NP which indicates that they often can be abysmally slow. Another algorithmic approach is relaxation. First we ignore the integer constraints and solve the standard Linear Programming Problems. Next, we "round" to the nearby integer solution. Various application requires integer solutions, and we're just skipping the surface. 

Many functions are nonconvex, indicating that the local minimum doesn't need to be in global minimum. Various algorithms can be stuck in local minimums. And obviously, this is not good. 

The issue is local mimima doesn't necessarily have to be a global mimima. The issue is there can be tons of local minimums, especially as we approach higher dimensions. However, there can be tons of local minimums. Markov chain Monte Carlo (MCMC) can solve some non-convex problems. Simulated annealing as well. We use the form expression E(x) for energy (analogous to statistical physics).

The distribution for the signal is Pr(x)=Z⋅exp{-sE(x)}. S is the inverse temperature. At a higher temperature we have a low s which we have a weak pull towards lower energy. Lower temperature is analogous to a large s which has a strong pull to lower energy. It is here where we experience gradual cooling. If we cool down very slowly we significantly decrease the chance of approaching the global minima. The con to MCMC is that it can be very slow. 

In the expectation maximization algorithm, we iterate over estimation (E) & maximization (M). We create a function estimating the log of likelihood, based on the current parameters. In maximization, we update the parameters to maximize expected likelihood from estimation step. We define the likelihood function as L(θ;X,Z)=Pr(X,Z|θ) where θ is the parameter and Z represents the latent and missing values, where model generates the data X. 

The marginal likelihood is L(θ;X)=Pr(X|θ)=∫L(θ;X,Z)dZ which might be intractable due to many possible Z sequences. We want to compute the likelihood of the model L(θ;X), then optimize the parameter. Again, we computed expected value of log likelihood for parameter θ(t) in current iteration t. We can usually find sequence Z given parameter  θ(t). The following equations help to compute the expected value: 

The Gaussian mixture model is defined by this equation: 

And Component i has probability 𝛼i mean 𝜇i, and standard deviation 𝜎i. We also have covariance matrix ∑i. Many distributions well-approximated by Gaussian Mixture Models. We can use the Gaussian Mixture Models to model almost anything. Finally, there is a major tradeoff between the number of components and the model accuracy. The parameters (𝛼𝑖, 𝜇𝑖, 𝜎𝑖) are often unavailable, so we often need to estimate/approximate these from the data. The expectation step is to compute the sequence Z given parameters θ=(𝛼𝑖, 𝜇𝑖, 𝜎𝑖), and optimize this given the Z value. 

We have N scalar samples X∈ℝ^N, and Latent variable 𝑍 ∈ ℤ^N, with zn correspond to Gaussian components that xn belongs to.

Suppose I have a bunch of data points. We want to estimate from where each data point comes from. We can compute points and get the estimates from the 2 Gaussians as a result. 

If we are doing mixture models, we have a bunch of data points coming from K different Gaussians. If we happened to know the parameters of the Gaussian, we could figure out which point is likely from which Gaussian, computing the probabilities from the standard deviations from norm and choosing the maxima. We can use Bayes rule and the Gaussian formula. 

EM algorithm starts placing 2 random Gaussians and for each point calculate the probability that it either fits inside of the red or blue Gaussian. The probability is NEVER quantized, saying the probability that a point comes from X distribution, which is soft cluster. It finally uses these numbers (based on each point maximum probability) to re-estimate mean and variances. We compute the probability that a point is in a cluster to be xi.

The mean is going to be

and the standard deviation is 

Finally, it keeps iterating until it converges.