=================================================================================

In Expectation-Maximization (EM) algorithm for estimating parameters in a mixture model using maximum likelihood, we mainly include:

          i) Soft assignment:

Instead of assigning a data point exclusively to the cluster with the maximum probability, EM assigns it to all clusters with some probability. The "softness" of the assignment is captured by these probabilities. Mathematically, the assignment is based on the responsibility w_j⁽ⁱ⁾:

          --------------------------------- [3696a]

where,

          L(ϕ, μ, ε) is a function representing the log-likelihood of the observed data given the parameters ϕ, μ, and ε.

          indicates that the operations in the EM algorithm are performed for each observation in the dataset (indexed by i).

          ii) Parameter updates:

The cluster parameters, such as the mixing coefficients (ϕ_j), means (μ_j), and covariances (ε_j), are updated using weighted averages. The weights are the responsibilities w_j⁽ⁱ⁾, indicating the likelihood of a data point belonging to a specific cluster:

          --------------------------------- [3696b]

          --------------------------------- [3696c]

where,

• p(x⁽ⁱ⁾, z⁽ⁱ⁾; ϕ, μ, ε) is the joint probability of observing x⁽ⁱ⁾ and its corresponding latent variable z⁽ⁱ⁾ given the parameters ϕ, μ, and ε.
• ϕ_j​ represents the probability that a randomly selected data point belongs to the j-th component of the mixture. It is estimated by counting the proportion of data points assigned to the j-th component.
• μ_j represents the mean of the distribution associated with the j-th component of the mixture. It is estimated by computing the weighted average of the observations assigned to the j-th component, where the weights are the probabilities of belonging to that component.
  

In a mixture model, we have a dataset with observations x⁽ⁱ⁾ that are assumed to be generated from a mixture of different distributions, each associated with a latent variable z⁽ⁱ⁾. The latent variable z⁽ⁱ⁾ indicates from which component of the mixture the observation x⁽ⁱ⁾ is generated. The goal is to estimate the parameters ϕ, μ, and ε that maximize the likelihood of the observed data. The likelihood function L(ϕ, μ, ε) is the probability of observing the entire dataset given the parameters.

The expressions in Equations 3696b and 3696c are the updates for the parameters ϕ_j​ and μ_j​ in the M-step of the EM algorithm for a mixture model. The 1{z⁽ⁱ⁾ = j} is an indicator function that equals 1 if z⁽ⁱ⁾ is equal to j and 0 otherwise. The sums in the denominators are normalization terms to ensure that ϕ represents a valid probability distribution and μ is properly weighted.

Equations 3696b and 3696c are exact Gaussian Discriminant Analysis (GDA), except difference of replacing y with z. That is, the main difference lies in the interpretation of the latent variable or label. In GDA, there's typically a categorical label variable y indicating the class to which an observation belongs. The likelihood and parameter estimation involve the class labels, and the focus is on modeling the class-conditional distributions. On the other hand, in Gaussian Mixture Model (GMM) with EM, there is a latent variable z that represents the component from which a data point is generated in the mixture. This latent variable z is associated with the different components of the mixture model, each modeled as a Gaussian distribution.

Based on evidence lower bound (ELBO) in variational inference, the EM algorithm gives,

                  ----------------- [3696ic]

This is the expression for the evidence lower bound, where Q is a distribution used in variational inference to approximate the posterior distribution p(z⁽ⁱ⁾|x⁽ⁱ⁾; θ). The goal is to maximize this lower bound during the optimization process.

For any θ and Q, its relationship to likelihood is given by,

          ---------------------------------- [3696icd]

This inequality holds due to the nature of the variational inference framework. The evidence lower bound J(θ, Q) is a lower bound on the log-likelihood L(θ). The goal of variational inference is to maximize the lower bound with respect to both the model parameters θ and the variational parameters Q. The inequality ensures that, at each step of the optimization, the lower bound is improved, and as a result, the log-likelihood is also improved. Maximizing the lower bound is a surrogate for maximizing the actual log-likelihood, which may be computationally challenging.

The EM algorithm alternates between the E-step (Expectation) and M-step (Maximization):

i) The E-step involves estimating the expected value of the latent variables (in this case, z⁽ⁱ⁾) given the observed data and the current parameter estimates. The expected value of the latent variables is computed given the current parameter estimates.

                    --------------------------------- [3696d]

                               ---------------------- [3696e]

where,

• p(z⁽ⁱ⁾ = j|x⁽ⁱ⁾; ϕ, μ, ε) is the posterior probability that the data point x⁽ⁱ⁾ belongs to the j-th component of the mixture, given the observed data and the current parameter estimates.

• p(x⁽ⁱ⁾|z⁽ⁱ⁾ = j) is the conditional probability of observing x⁽ⁱ⁾ given that it comes from the j-th component of the mixture. This is modeled as a univariate Gaussian distribution with parameters μ_j​ and ε_j:

            ----------------- [3696f]

  For the multivariate case, where x⁽ⁱ⁾ is a vector and μ_j​ is the mean vector of the j-th component, and Σ_j​ is the covariance matrix of the j-th component, the equation becomes:

          - [3696g]

Here, x⁽ⁱ⁾ is the observed data point, μ_j is the mean vector of the j-th component, Σ_j is the covariance matrix of the j-th component, and σ²_j is the variance of the j-th component (in the univariate case).

• p(z⁽ⁱ⁾ = j) is the prior probability of a data point belonging to the j-th component of the mixture, represented by the mixing coefficient ϕ_j. ϕ is a vector of numbers that sum to 1.

We can have,

        -------------------------- [3696gb]

        -------------------------- [3696gba]

Equation 3696gba represents the conditional probability of the latent variable z⁽ⁱ⁾ taking on a specific value j given the observed data x⁽ⁱ⁾ and the current parameter estimates ϕ, μ, and ε. z⁽ⁱ⁾ can be a multinomial variable denoted by ϕ or any other symbol. In probabilistic models, the term "multinomial" refers to a categorical distribution, which is a discrete probability distribution over a finite set of categories. The parameter ϕ would represent the probabilities associated with each category in the multinomial distribution.

       In summary, in the E-step, we set the distribution over latent variables z⁽ⁱ⁾ to be,

                    --------------------------------- [3696gc]

ii) During the M-step, you are optimizing the log-likelihood (ℓ(θ)) of the data with respect to the model parameters. In the M-step, the parameters are updated by maximizing the expected log-likelihood.

     The parameters μ_j​​ and Σ_j​​ are part of the parameters that are estimated in the EM algorithm for GMMs during the M-step.

                  ----------------- [3696h]

                  ----------------- [3696i]

The two equations above are used in the Maximization (M-step) to update the parameters ϕ_j​ and μ_j. In Equation 3696h, ϕ_j​ represents the mixing coefficient for the j-th component of the mixture. It is updated by taking the average of the responsibilities w_j⁽ⁱ⁾ over all data points. In Equation 3696i, μ_j​ is the mean vector of the j-th component, and it is updated by taking the weighted average of the data points x⁽ⁱ⁾ using the responsibilities w_j⁽ⁱ⁾ as weights. Equations 3696h and 3696i ensure that ϕ_j​ remains a valid probability distribution, and μ_j​ is updated based on the weighted average of the data points, where the weights are given by the responsibilities. These updates are performed iteratively in the EM algorithm until convergence, aiming to find the parameters that maximize the likelihood of the observed data in the presence of latent variables.

Inequality 3696icd tells that in E-step we maximize J with respect to Q, while in M-step, we maximize J with respect to θ::

• In the E-step, the goal is to compute or estimate the expected value of the log-likelihood, given the observed data and the current estimates of the parameters (θ).

This involves maximizing the evidence lower bound (J) with respect to the distribution of the latent variables (Q), treating the parameters (θ) as fixed.

             ----------------- [3696ica]

• In the M-step, the goal is to maximize the expected log-likelihood obtained from the E-step with respect to the parameters (θ).

This involves maximizing the evidence lower bound (J) with respect to the model parameters (θ), treating the distribution of the latent variables (Q) as fixed.

             ----------------- [3696icb]

The EM algorithm iteratively alternates between these two steps until convergence. The E-step computes the expected value of the latent variables, and the M-step updates the parameters of the model based on this expectation. The algorithm aims to find a set of parameters that maximizes the observed data log-likelihood, taking into account the presence of latent variables. Therefore, the EM algorithm is often referred as a coordinate ascent algorithm.

In summary, in the M-step, we update θ by,

                  ----------------- [3696id]

The right-hand side of the optimization problem is constructed as a lower bound for the log-likelihood. This is a key concept in variational inference and the derivation of the evidence lower bound (ELBO). The given optimization problem is often associated with the maximization of the ELBO. The goal is to find the parameters θ that maximize the ELBO. The ELBO is a lower bound for the log-likelihood because of Jensen's inequality. Specifically, for any distribution Q_i(z⁽ⁱ⁾), Jensen's inequality implies that:

                  --------------- [3696ie]

Maximizing the sum over i in the optimization problem is equivalent to maximizing a lower bound on the log-likelihood. This approach is commonly used in variational inference to approximate intractable posterior distributions by optimizing a tractable lower bound. The optimization process seeks to find both the model parameters θ and the variational parameters that define the distribution Q_i(z⁽ⁱ⁾).

A probabilistic model which is often used in the EM algorithm, particularly for mixture models such as Gaussian Mixture Models (GMMs) is given by the expressions, which represent the probability distribution assumptions for the model, below.

                  --------------------------------- [3696ida]

                  --------- [3696idb]

                  ----------------------------------------- [3696idc]

                  ----------------------------------------- [3696idd]

Equation 3696ida represents the assignment of observation i to the j-th component of the mixture model. In GMMs, each component is associated with a Gaussian distribution. Equation 3696idb is the probability density function (PDF) of the observed data x⁽ⁱ⁾ given the assignment z⁽ⁱ⁾ = j and the model parameters θ. In the case of a Gaussian mixture model, this PDF is represented by a multivariate Gaussian distribution with mean μ_j​ and covariance matrix ε_j​ for the j-th component. Equation 3696idc represents the prior probability of assignment to the j-th component. In GMMs, ϕ_j​ ​is often interpreted as the weight or mixing coefficient associated with the j-th component. Equation 3696idd is the estimated probability (or responsibility) that observation i belongs to the j-th component during the E-step of the EM algorithm. It is often computed as part of the EM algorithm and is proportional to the likelihood of the data given the current parameters.

The process, of finding the maximum likelihood estimates for the mean parameter μ_j​ by taking the derivative of the log-likelihood function with respect to μ_j​ and setting it equal to 0, is given by,

                  ----------------------------------- [3696idea]

The process involves taking the derivative of the log-likelihood function with respect to the mean parameter μ_j and setting it equal to 0 to find the values of μ_j​ that maximize the likelihood of the observed data.

The parameter update step in the M-step of the EM algorithm, particularly for Gaussian Mixture Models (GMMs), can be given by,

                  ----------------------------------- [3696ide]

where,

            μ_j is the means.

            ε_j is the covariances​.

            ϕ_j is the mixing coefficients.

Equation 3696ide is the update rule for the mean μ_j​ of the j-th component during the M-step. This update is based on the responsibilities ω_j⁽ⁱ⁾ assigned to the j-th component during the E-step when we are optimizing the log-likelihood of the data.

Similarly, update equations for the other parameters can be obtained. For instance, the covariance matrix ε_j update is typically obtained by setting the derivative of the log-likelihood with respect to ε_j​ to 0. The update equation often involves the weighted sum of the outer products of the data points with the responsibilities ω_j⁽ⁱ⁾​ . Therefore, update for ε_j can be given by,

                  ----------------------------------- [3696idf]

                  ----------------------------------- [3696idg]

This update ensures that ε_j​ maximizes the likelihood of the data under the assumption of a Gaussian distribution.

Update for ϕ_j​ (mixing coefficient) can be given by,

                  ----------------------------------- [3696idh]

                  ----------------------------------- [3696idi]

where,

            N is the total number of data points. This update ensures that ϕ_j​​ reflects the proportion of data points assigned to the j-th component.

The mixing coefficient ϕ_j​ represents the prior probability of selecting the j-th component. The update for ϕ_j​ is obtained by setting the derivative of the log-likelihood with respect to ϕ_j​ to 0.

As an example of EM algorithm, assuming we want to maximize the L(θ) of the blue curve, in Figure 3696a, with the steps below:

i) In the first E-step, we can randomly initiate θ as at θ₀ = 2.25, we can construct a lower bound shown in green for a log-likelihood with the properties below:

          i.a) Everywhere on the lower bound (green) curve is lower than the blue curve.

          i.b) The blue curve and the green curve have a common point, which is the initiated point on the blue curve.

ii) In the first M-step, we find the maximum of the green curve, which is the point at Max₁.

iii) In the second E-step, we use the θ value of the point at Max₁ as θ₁to repeat the steps i) and ii).

iv) Those steps will repeated until the local maximum is found.

Equation 3696a can be modified to,

          --------------------------------- [3696j]

where,

          Q_i(z⁽ⁱ⁾) represents a probability distribution Q_i​ over the latent variable z⁽ⁱ⁾ for the i-th observation.

          is the sum over all possible values of the latent variable z⁽ⁱ⁾ according to the distribution Q_i. The sum is equal to 1.

          is the ratio of the joint probability p(x⁽ⁱ⁾, z⁽ⁱ⁾; θ) to the distribution Q_i(z⁽ⁱ⁾). It's essentially the responsibility of the latent variable according to the current model.

Because we have expectation of a function given by ,

          --------------------------------- [3696jb]

Here, E[g(z)] represents the expected value of the function g(z) with respect to the probability distribution p(z). The sum is taken over all possible values of the random variable z.

And, expectation of a random variable is given by,

          --------------------------------- [3696jc]

Here, similarly, E[z] represents the expected value of the random variable z itself. Again, the sum is taken over all possible values of z according to the probability distribution p(z).

In the EM algorithm, these formulas in Equations 3696jb and 3696jc are often used in the E-step to compute the expected values of certain functions or random variables with respect to a given probability distribution.

Then, another way to represent the log-likelihood function in the EM algorithm is,

          --------------------------------- [3696k]

The right-hand side of Equation 3696k represents the log of the expected value of the ratio with respect to the distribution Q_i​ over the latent variable z⁽ⁱ⁾.

Based on Jensen's inequality, for log function, which is a concave function, then we have,

          -------------- [3696l]

Then, we have,

          ------------ [3696m]

The right-hand side in Inequality 3696m represents the lower bounds as shown in Figure 3696a.

The EM algorithm involves iteratively updating parameters ϕ, μ, and ε to maximize this log-likelihood function. The E-step computes the expected value of the log-likelihood with respect to the current estimates of the parameters, and the M-step maximizes this expected log-likelihood to update the parameters. The process repeats until convergence. The distribution Q_i(z⁽ⁱ⁾) plays a crucial role in this iterative process.

On a given iteration at EM, we want ,

          ---- [3696n]

To enable Equation 3696n, which is related to the evidence lower bound (ELBO), to be true, we need to have a specific relationship between the distributions involved. This equation involves an expectation with respect to the distribution Q. The equality holds under the condition that the distributions Q_i(z⁽ⁱ⁾) are chosen such that the logarithm can be taken inside the expectation. This typically happens when the logarithm is a convex function, and the Jensen's inequality becomes an equality. Therefore, the condition for equality is that the logarithm function applied to the ratio is a concave function, or equivalently, the reciprocal of the logarithm (exponential function) is convex. Then, the needs to be a constant with respect to the distribution Q_i(z⁽ⁱ⁾). In other words, the ratio should not depend on the specific values of z⁽ⁱ⁾ drawn from the distribution Q_i.

In practical terms, this often occurs when dealing with exponential families of distributions, where the ratio of two probability density functions is a well-behaved function, and the logarithm of this ratio satisfies the conditions for Jensen's inequality to become an equality.

Let's set,

          ----------------- [3696o]

We know,

          ----------------- [3696p]

============================================