MM Algorithm[unfinished]

By -
MM algorithm

1. Overview of MM algorithm


    • The MM algorithm is not an algorithm, but a prescription for constructing optimization algorithms. 
    • The EM algorithm from statistics is a special case.
    • An MM algorithm operates by creating a surrogate function that minorizes or majorizes the objective function. When the surrogate function is optimized, the objective function is driven uphill or downhill as needed.
    • In minimization MM stands for majorize/minimize, and in maximization MM stands for minorize/maximize.

2. Rationale for the MM principle


    • It can generate an algorithm that avoids matrix inversion. 
    • It can separate the parameters of a problem. 
    • It can linearize an optimization problem. 
    • It can deal gracefully with equality and inequality constraints. 
    • It can turn a non-differentiable problem into a smooth problem.

3. Majorization and definition of algorithms


    • A function $g(θ | θ^n)$ is said to majorize the function f(θ) at θn provided: 

 $f(θ^n) = g(θ^n | θ^n); $

$f(θ) ≤ g(θ | θ^n)$ for all θ. 
    • The majorization relation between functions is closed under the formation of sums, nonnegative products, limits,and composition with an increasing function.
    • A function $g(θ | θ^n)$ is said to minorize the function $f(θ)$ at $θ^n$ provided $−g(θ | θ^n)$ majorizes $−f(θ)$. 
    • In minimization, we choose a majorizing function $g(θ | θ^n)$ and minimize it. This produces the next point $θ^{n+1}$ in the algorithm.

 4. Descent Property 


  • An MM minimization algorithm satisfies the descent property $f(θ^{n+1}) ≤ f(θ^n)$ with strict inequality unless both 
 $g(θ^{n+1} | θ^n) = g(θ^n | θ^n)$
 $f(θ^{n+1}) = g(θ^{n+1} | θ^n).$ 
  • The descent property follows from the definitions and 
     $f(θ^{n+1}) = g(θ^{n+1} | θ^n) + f(θ^{n+1}) − g(θ^{n+1} | θ^n) $
     $ ≤ g(θ^n | θ^n) + f(θ^n) − g(θ^n | θ^n) = f(θ^n). $
(Because $f(θ^{n+1}) − g(θ^{n+1} | θ^n) \leq 0 = f(θ^n) − g(θ^n | θ^n) $)
  • The descent property makes the MM algorithm very stable.


5. Constructing majorization (minorization) function

  • Jensen's inequality: for any convex function $f(x)$ and any random variable $X$, we have:
$f(E(X)) \leq E(f(X))$.
      Since $- ln(x)$ is a convex function, we conclude for probability densities $a(x), b(x)$ that
                                 
          $-\ln {E(\frac{a(X)}{b(X)})} \leq - E[\ln(\frac{a(X)}{b(X)})]$.

      If $X$ has density function $b(x)$, then  $E(\frac{a(X)}{b(X)}) = 1$. The above inequality implies:  $E( \ln (a(X))) \leq E( \ln (b(X)))$. 

       Discussion: Why EM algorithm is a special case of MM algorithm?   
       Answer: here

  •  Minorization via Supporting Hyperplanes


     Any linear function tangent to the graph of a convex function is a minorizer at the point of tangency. Hence, if $f(x)$ is convex and differentiable, then:



$f(\theta) \geq f(\theta^{n}) + \triangledown f(\theta^n)^t(\theta - \theta^n)$


     with equality when $\theta = \theta^n$.
  • Majorization via the Definition of Convexity

      A function $f(x)$ is a convex function if and only if:
   $f(\sum\limits_{i}\alpha_it_i) \leq \sum\limits_{i} \alpha_if(t_i)$, 
    for any finite collection of points $t_i$ and corresponding multipliers $\alpha_i \geq 0$ and                  $\sum\limits_{i}\alpha_i = 1$.

  • The Arithmetic-Geometric Mean Inequality
      
  •  The Cauchy-Schwartz Inequality    
The function $f(\theta) = ||\theta||$ is convex because it satisfies the triangle inequality and the           homogeneity condition $||\alpha \theta|| = |\alpha|||\theta||$.
From the inequality in section minorization via Supporting hyperplanes, we have:

      $||\theta|| \geq ||\theta^{n}||  + \frac{(\theta - \theta^n)^t\theta^n}{||\theta^m||} = \frac{\theta^t\theta^m}{||\theta^m||}.$ 

6. Reference


Comments

Post a Comment

Popular posts from this blog

Manifold Learning [unfinished]

By -
Image
I. What is manifold learning Dimensionality Reduction The accuracy of the training algorithms is directly proportional to the amount of data we have. However, managing a large number of features is usually a burden to our algorithm.  Some of these features may be irrelevant, so it's important to make sure that the final model doesn't get affected by this.  What is Dimensionality?  Dimensionality refers to the minimum number of coordinates needed to specify any point within a space or an object. Why do we need Dimensionality Reduction? If you keep the dimensionality high, it will be nice and unique but it may not be easy to analyse because of complexity involved. Apart from simplifying data, visualization is also an interesting and challenging application. Linear Dimensionality Reduction Fig 1 : PCA illustration (source: http://evelinag.com/blog ) Principle Component Analysis  Given a data set, PCA finds the directions along which the data has max
Read more

Feature scaling

By -
Image
1. What is feature scaling?  Feature scaling is a method used to normalize all independent values of our data. We also call it as data normalization and is generally performed before running machine learning algorithms. 2. Why do we need to use feature scaling?  In practice the range of raw data is very wide and hence the object functions will not work properly (means that it will stuck at local optimum), or they are time-consuming without normalization. For example:  K-Means, might give you totally different solutions depending on the preprocessing methods that you used. This is because an affine transformation implies a change in the metric space: the Euclidean distance between two samples will be different after that transformation. When we apply gradient descent, feature scaling also helps it to converge much faster that without normalized data.  With and without feature scaling in gradient descent 3. Methods in feature scaling? Rescaling The simplest method is resc
Read more

Find all pairs in array of integers whose sum is equal to a given number ?

By -
Problem: Write a program to find all pairs of integers whose sum is equal to a given number. For example if input integer array is {1, 2, 3, 4, 5}, and the given sum is 5, the code should return two pairs {1, 4} and {2, 3}. This is a common interview question related to array structure. A quick search on Google can return several pages discussing the problem, to list but a few [1,2, 3, 4]. Those pages only discuss the solutions at the conceptual level, without supporting comparing numbers, although they also provide the code. In this note I would re-implement all these approaches and compare their efficiency in practice. Common approaches There are four approaches which are often mentioned together: Brute-force, HashSet, sorting with search and sorting with binary search. Each has its own pros and cons. Interested readers can find the details in the list of sources below. Here is a summary of the storage complexity and computational complexity. Approach Storage co
Read more