Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “EM algorithm”

Search indexed PubMed citations on genomics, clinical trials, systematic reviews and public health. Explore titles, authors and supplied subject terms, then open the PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 recordsLinked to original sources
PubMed1993

The estimation of population pharmacokinetic parameters using an EM algorithm.

An EM algorithm was used to analyse data arising from non-linear mixed-effects models. The fixed parameters were determined by maximum likelihood using simplex minimization, and the random effects were estimated using the EM algorithm after linearization with respect to the random effects. Applications to a simple linear model and population pharmacokinetics are described. The use of posterior parameter estimates to investigate covariate relationships is briefly described. The implementation of the estimation-maximization (EM) algorithm described here has proved in practice to be robust but slow. We intend to use a Newton-Raphson minimization routine in place of the simplex method to hasten convergence. The alternative linearization of the non-linear mixed effects model suggested by Lindstrom and Bates (Biometrics 46 (1990) 673-687) is much more unstable than the usual linearization, especially during the initial iterations. In the case of indomethacin the two linearizations produced very similar results. The individual posterior parameter estimates provided by the program are very useful for the detection of covariate relationships in population pharmacokinetic studies. In addition, the posterior means can be used in the estimation of pharmacokinetic-pharmacodynamic relationships from sparse pharmacokinetic data where individual modelling is impossible.

Algorithms↗
PubMed1989

Trials, tribulations, and triumphs of the EM algorithm in pedigree analysis.

The EM algorithm is an iterative method for finding maximum-likelihood estimates. Its advantages often include numerical stability, simplicity of computer implementation, and natural incorporation of parameter constraints. However, the EM algorithm must be tailored to each specific problem. Smith (1957) and Ott (1977, 1979) have accomplished this for a variety of problems in human pedigree analysis. The present paper clarifies their theory by presenting it from a modern perspective. Five practical numerical examples are also given in an attempt to assess the value of the EM algorithm in realistic genetic modelling. These examples deal with racial admixture, linkage homogeneity, classical segregation analysis, a Mendelian latent trait model for schizophrenia, and a heterozygote detection assay for Ataxia-telangiectasia. Comparison with a quasi-Newton method of optimization reveals that the EM algorithm generally converges more slowly, but also more stably.

Algorithms↗
PubMedDate not supplied

Application of the EM algorithm to radiographic images.

The expectation maximization (EM) algorithm has received considerable attention in the area of positron emitted tomography (PET) as a restoration and reconstruction technique. In this paper, the restoration capabilities of the EM algorithm when applied to radiographic images is investigated. This application does not involve reconstruction. The performance of the EM algorithm is quantitatively evaluated using a "perceived" signal-to-noise ratio (SNR) as the image quality metric. This perceived SNR is based on statistical decision theory and includes both the observer's visual response function and a noise component internal to the eye-brain system. For a variety of processing parameters, the relative SNR (ratio of the processed SNR to the original SNR) is calculated and used as a metric to compare quantitatively the effects of the EM algorithm with two other image enhancement techniques: global contrast enhancement (windowing) and unsharp mask filtering. The results suggest that the EM algorithm's performance is superior when compared to unsharp mask filtering and global contrast enhancement for radiographic images which contain objects smaller than 4 mm.

Algorithms↗
PubMed2004

Using the EM algorithm to train neural networks: misconceptions and a new algorithm for multiclass classification.

The expectation-maximization (EM) algorithm has been of considerable interest in recent years as the basis for various algorithms in application areas of neural networks such as pattern recognition. However, there exists some misconceptions concerning its application to neural networks. In this paper, we clarify these misconceptions and consider how the EM algorithm can be adopted to train multilayer perceptron (MLP) and mixture of experts (ME) networks in applications to multiclass classification. We identify some situations where the application of the EM algorithm to train MLP networks may be of limited value and discuss some ways of handling the difficulties. For ME networks, it is reported in the literature that networks trained by the EM algorithm using iteratively reweighted least squares (IRLS) algorithm in the inner loop of the M-step, often performed poorly in multiclass classification. However, we found that the convergence of the IRLS algorithm is stable and that the log likelihood is monotonic increasing when a learning rate smaller than one is adopted. Also, we propose the use of an expectation-conditional maximization (ECM) algorithm to train ME networks. Its performance is demonstrated to be superior to the IRLS algorithm on some simulated and real data sets.

Algorithms↗
PubMed2004

A new algorithm for haplotype-based association analysis: the Stochastic-EM algorithm.

It is now widely accepted that haplotypic information can be of great interest for investigating the role of a candidate gene in the etiology of complex diseases. In the absence of family data, haplotypes cannot be deduced from genotypes, except for individuals who are homozygous at all loci or heterozygous at only one site. Statistical methodologies are therefore required for inferring haplotypes from genotypic data and testing their association with a phenotype of interest. Two maximum likelihood algorithms are often used in the context of haplotype-based association studies, the Newton-Raphson (NR) and the Expectation-Maximisation (EM) algorithms. In order to circumvent the limitations of both algorithms, including convergence to local minima and saddle points, we here described how a stochastic version of the EM algorithm, referred to as SEM, could be used for testing haplotype-phenotype association. Statistical properties of the SEM algorithm were investigated through a simulation study for a large range of practical situations, including small/large samples and rare/frequent haplotypes, and results were compared to those obtained by use of the standard NR algorithm. Our simulation study indicated that the SEM algorithm provides results similar to those of the NR algorithm, making the SEM algorithm of great interest for haplotype-based association analysis, especially when the number of polymorphisms is quite large.

Algorithms↗
PubMed2005

Genetic-based EM algorithm for learning Gaussian mixture models.

We propose a genetic-based expectation-maximization (GA-EM) algorithm for learning Gaussian mixture models from multivariate data. This algorithm is capable of selecting the number of components of the model using the minimum description length (MDL) criterion. Our approach benefits from the properties of Genetic algorithms (GA) and the EM algorithm by combination of both into a single procedure. The population-based stochastic search of the GA explores the search space more thoroughly than the EM method. Therefore, our algorithm enables escaping from local optimal solutions since the algorithm becomes less sensitive to its initialization. The GA-EM algorithm is elitist which maintains the monotonic convergence property of the EM algorithm. The experiments on simulated and real data show that the GA-EM outperforms the EM method since: 1) We have obtained a better MDL score while using exactly the same termination condition for both algorithms. 2) Our approach identifies the number of components which were used to generate the underlying data more often than the EM algorithm.

Algorithms↗
PubMed1996

A modified EM algorithm for estimation in generalized mixed models.

Application of the EM algorithm for estimation in the generalized mixed model has been largely unsuccessful because the E-step cannot be determined in most instances. The E-step computes the conditional expectation of the complete data log-likelihood and when the random effect distribution is normal, this expectation remains an intractable integral. The problem can be approached by numerical or analytic approximations; however, the computational burden imposed by numerical integration methods and the absence of an accurate analytic approximation have limited the use of the EM algorithm. In this paper, Laplace's method is adapted for analytic approximation within the E-step. The proposed algorithm is computationally straightforward and retains much of the conceptual simplicity of the conventional EM algorithm, although the usual convergence properties are not guaranteed. The proposed algorithm accommodates multiple random factors and random effect distributions besides the normal, e.g., the log-gamma distribution. Parameter estimates obtained for several data sets and through simulation show that this modified EM algorithm compares favorably with other generalized mixed model methods.

Algorithms↗
PubMed2002

[The use of the expectation-maximization (EM) algorithm for maximum likelihood estimation of gametic frequencies of multilocus polymorphic codominant systems based on sampled population data].

Estimation of gametic frequencies in multilocus polymorphic systems based on the numerical distribution of multilocus genotypes in a population sample ("analysis without pedigrees") is difficult because some gametes are not recognized in the data obtained. Even in the case of codominant systems, where all alleles can be recognized by genotypes, so that direct estimation of the frequencies of genes (alleles) is possible ("complete data"), estimation of the frequencies of multilocus gametes based on the data on multilocus genotypes is sometimes impossible, whether population data or even family data are used for studying genotypic segregation or analysis of linkage ("incomplete data"). Such "incomplete data" are analyzed based on the corresponding genetic models using the expectation-maximization (EM) algorithm. In this study, the EM algorithm based on the random-marriage model for a nonsubdivided population was used to estimate gametic frequencies. The EM algorithm used in the study does not set any limitations on the number of loci and the number of alleles of each locus. Locus and alleles are identified by numeration making possible to arrange loops. In each combination of alleles for a given combination of m out of L loci (L is the total number of loci studied), all alleles are assigned value 1, and the remaining alleles are assigned value 0. The sum of zeros and unities for each gamete is its gametic value (h), and the sum of the gametic values of the gametes that form a given genotype is the genotypic value (g) of this genotype. Then, gametes with the same h are united into a single class, which reduces the number of the estimated parameters. In a general case of m loci, this procedure yields m + 1 classes of gametes and 2m + 1 classes of genotypes with genotypic values g = 0, 1, 2, ..., 2m. The unknown frequencies of the m + 1 classes of gametes can be represented as functions of the gametic frequencies whose maximum likelihood estimations (MLEs) have been obtained in all previous EM procedures and the only unknown frequency (Pm(m)) that is to be estimated in the given EM procedure. At the expectation step, the expected frequencies (Fm(g) of the genotypes with genotypic values g are expressed in terms of the products of the frequencies of m + 1 classes of gametes. The data on genotypes are the numbers (ng) of individuals with genotypic values g = 0, 1, 2, 3, ..., 2m. The maximization step is the maximization of the logarithm of the likelihood function (LLF) for ng values. Thus, the EM algorithm is reduced, in each case, to solution of only one equation with one unknown parameter with the use of the ng values, i.e., the numbers of individuals after the corresponding regrouping of the data on the individuals' genotypes. Treatment of the data obtained by Kurbatova on the MNSs and Rhesus systems with alleles C, Cw, c, D, d, E, e with the use of Weir's EM algorithm and the EM algorithm suggested in this study yielded similar results. However, the MLEs of the parameters obtained with the use of either algorithm often converged to a wrong solution: the sum of the frequencies of all gametes (4 and 12 gametes for MNSs and Rhesus, respectively) was not equal to 1.0 even if the global maximum of LLF was reached for each of them (as it was for MNSs with the use of Weir's EM algorithm), with each parameter falling within admissible limits (e.g., [0, min(PN,Ps)] for PNs). The chi 2 function is suggested to be used as a goodness-of-fit function for the distribution of genotypes in a sample in order to select acceptable solutions. However, the minimum of this function only guarantee the acceptability of solutions if all limitations on the parameters are met: the sum of estimations of gametic frequencies is 1.0, each frequency falls within the admissible limits, and the "gametic algebra" is complied with (none of the frequencies is negative).

Algorithms↗
PubMed2005

Convergence study of an accelerated ML-EM algorithm using bigger step size.

In SPECT/PET, the maximum-likelihood expectation-maximization (ML-EM) algorithm is getting more attention as the speed of computers increases. This is because it can incorporate various physical aspects into the reconstruction process leading to a more accurate reconstruction than other analytical methods such as filtered-backprojection algorithms. However, the convergence rate of the ML-EM algorithm is very slow. Several methods have been developed to speed it up, such as the ordered-subset expectation-maximization (OS-EM) algorithm. Even though OS-type algorithms can bring about significant acceleration in the iterative reconstruction, it is generally believed that ML-EM produces better images, in terms of statistical noise in the reconstruction. In this paper, we present an accelerated ML-EM algorithm with bigger step size and show its convergence characteristics in terms of variance noise and log-likelihood values. We also show some advantages of our method over other accelerating methods using additive forms.

Algorithms↗
PubMed2004

Segmentation of 4D cardiac MR images using a probabilistic atlas and the EM algorithm.

In this paper an automatic atlas-based segmentation algorithm for 4D cardiac MR images is proposed. The algorithm is based on the 4D extension of the expectation maximisation (EM) algorithm. The EM algorithm uses a 4D probabilistic cardiac atlas to estimate the initial model parameters and to integrate a priori information into the classification process. The probabilistic cardiac atlas has been constructed from the manual segmentations of 3D cardiac image sequences of 14 healthy volunteers. It provides space and time-varying probability maps for the left and right ventricles, the myocardium, and background structures such as the liver, stomach, lungs and skin. In addition to using the probabilistic cardiac atlas as a priori information, the segmentation algorithm incorporates spatial and temporal contextual information by using 4D Markov Random Fields. After the classification, the largest connected component of each structure is extracted using a global connectivity filter which improves the results significantly, especially for the myocardium. Validation against manual segmentations and computation of the correlation between manual and automatic segmentation on 249 3D volumes were calculated. We used the 'leave one out' test where the image set to be segmented was not used in the construction of its corresponding atlas. Results show that the procedure can successfully segment the left ventricle (LV) (r = 0.96), myocardium (r = 0.92) and right ventricle (r = 0.92). In addition, 4D images from 10 patients with hypertrophic cardiomyopathy were also manually and automatically segmented yielding a good correlation in the volumes of the LV (r = 0.93) and myocardium (0.94) when the atlas constructed with volunteers is blurred.

Algorithms↗
PubMed1997

The EM algorithm in medical imaging.

This article outlines the statistical developments that have taken place in the use of the EM algorithm in emission and transmission tomography during the past decade or so. We discuss the statistical aspects of the modelling of the projection data for both the emission and transmission cases and define the relevant probability models. This leads to the use of the method of maximum likelihood as a means of estimating the relevant unknown parameters within a given region of a patient's body and to the use of the EM algorithm to compute the reconstruction. Various different types of EM algorithm are discussed, including the SAGE algorithms of Fessler and Hero. The limitations of the EM algorithm, per se, are covered and the need for regularization is stressed. A number of different methods for penalizing the likelihood are described and a number of algorithms for the computation of the penalized EM reconstruction are discussed.

Algorithms↗
PubMed2003

[A multicenter evaluation of seven commercial ML-EM algorithms for SPECT image reconstruction using simulation data].

The maximum likelihood expectation maximization (ML-EM) algorithm has become available as an alternative to filtered back projection in SPECT. The actual physical performance may be different depending on the manufacturer and model, because of differences in computational details. The purpose of this study was to investigate the characteristics of seven different types of ML-EM algorithms using simple simulation data. Seven ML-EM algorithm programs were used: Genie (GE), esoft (Siemens), HARP-III (Hitachi), GMS-5500UI (Toshiba), Pegasys (ADAC), ODYSSEY-FX (Marconi), and Windows-PC (original software). Projection data of a 2-pixel-wide line source in the center of the field of view were simulated without attenuation or scatter. Images were reconstructed with ML-EM by changing the number of iterations from 1 to 45 for each algorithm. Image quality was evaluated after a reconstruction using full width at half maximum (FWHM), full width at tenth maximum (FWTM), and the total counts of the reconstructed images. In the maximum number of iterations, the difference in the FWHM value was up to 1.5 pixels, and that of FWTM, no less than 2.0 pixels. The total counts of the reconstructed images in the initial few iterations were larger or smaller than the converged value depending on the initial values. Our results for the simplest simulation data suggest that each ML-EM algorithm itself provides a simulation image. We should keep in mind which algorithm is being used and its computational details, when physical and clinical usefulness are compared.

Algorithms↗
PubMed1994

Noise properties of the EM algorithm: I. Theory.

The expectation-maximization (EM) algorithm is an important tool for maximum-likelihood (ML) estimation and image reconstruction, especially in medical imaging. It is a non-linear iterative algorithm that attempts to find the ML estimate of the object that produced a data set. The convergence of the algorithm and other deterministic properties are well established, but relatively little is known about how noise in the data influences noise in the final reconstructed image. In this paper we present a detailed treatment of these statistical properties. The specific application we have in mind is image reconstruction in emission tomography, but the results are valid for any application of the EM algorithm in which the data set can be described by Poisson statistics. We show that the probability density function for the grey level at a pixel in the image is well approximated by a log-normal law. An expression is derived for the variance of the grey level and for pixel-to-pixel covariance. The variance increases rapidly with iteration number at first, but eventually saturates as the ML estimate is approached. Moreover, the variance at any iteration number has a factor proportional to the square of the mean image (though other factors may also depend on the mean image), so a map of the standard deviation resembles the object itself. Thus low-intensity regions of the image tend to have low noise. By contrast, linear reconstruction methods, such as filtered back-projection in tomography, show a much more global noise pattern, with high-intensity regions of the object contributing to noise at rather distant low-intensity regions. The theoretical results of this paper depend on two approximations, but in the second paper in this series we demonstrate through Monte Carlo simulation that the approximations are justified over a wide range of conditions in emission tomography. The theory can, therefore, be used as a basis for calculation of objective figures of merit for image quality.

Algorithms↗
PubMed1998

Deterministic annealing EM algorithm.

This paper presents a deterministic annealing EM (DAEM) algorithm for maximum likelihood estimation problems to overcome a local maxima problem associated with the conventional EM algorithm. In our approach, a new posterior parameterized by `temperature' is derived by using the principle of maximum entropy and is used for controlling the annealing process. In the DAEM algorithm, the EM process is reformulated as the problem of minimizing the thermodynamic free energy by using a statistical mechanics analogy. Since this minimization is deterministically performed at each temperature, the total search is executed far more efficiently than in the simulated annealing. Moreover, the derived DAEM algorithm, unlike the conventional EM algorithm, can obtain better estimates free of the initial parameter values. We also apply the DAEM algorithm to the training of probabilistic neural networks using mixture models to estimate the probability density and demonstrate the performance of the DAEM algorithm.

Journal Article↗
PubMed1997

Uses of the EM algorithm in the analysis of data on HIV/AIDS and other infectious diseases.

The analysis of data on infectious diseases is a natural setting for applications of the EM algorithm, because the infection process is only partially observable. Difficulties in determining the expectation at the E step have been side-stepped by adopting pragmatic models which reflect only part of the mechanism that generates the data. In the HIV/AIDS context the EM algorithm has helped in the reconstruction of the unobserved HIV infection curve, the so-called backprojection problem, as well as in the estimation of the distribution for the incubation period until AIDS, in estimating the infectivity of HIV in partnerships and in estimating parameters describing the decline in the immune system. There is a need for smooth estimates of functions in these applications, suggesting the use of the EMS algorithm or use of the EM algorithm to maximize a penalized likelihood. For data on other infectious diseases the application of the EM algorithm has so far been restricted to analyses of data on the size of outbreaks in a sample of households.

Acquired Immunodeficiency Syndrome↗
PubMed2005

An EM algorithm for the block mixture model.

Although many clustering procedures aim to construct an optimal partition of objects or, sometimes, of variables, there are other methods, called block clustering methods, which consider simultaneously the two sets and organize the data into homogeneous blocks. Recently, we have proposed a new mixture model called block mixture model which takes into account this situation. This model allows one to embed simultaneous clustering of objects and variables in a mixture approach. We have studied this probabilistic model under the classification likelihood approach and developed a new algorithm for simultaneous partitioning based on the Classification EM algorithm. In this paper, we consider the block clustering problem under the maximum likelihood approach and the goal of our contribution is to estimate the parameters of this model. Unfortunately, the application of the EM algorithm for the block mixture model cannot be made directly; difficulties arise due to the dependence structure in the model and approximations are required. Using a variational approximation, we propose a generalized EM algorithm to estimate the parameters of the block mixture model and, to illustrate our approach, we study the case of binary data by using a Bernoulli block mixture.

Algorithms↗
PubMed2003

An EM algorithm for mapping binary disease loci: application to fibrosarcoma in a four-way cross mouse family.

Many diseases show dichotomous phenotypic variation but do not follow a simple Mendelian pattern of inheritance. Variances of these binary diseases are presumably controlled by multiple loci and environmental variants. A least-squares method has been developed for mapping such complex disease loci by treating the binary phenotypes (0 and 1) as if they were continuous. However, the least-squares method is not recommended because of its ad hoc nature. Maximum Likelihood (ML) and Bayesian methods have also been developed for binary disease mapping by incorporating the discrete nature of the phenotypic distribution. In the ML analysis, the likelihood function is usually maximized using some complicated maximization algorithms (e.g. the Newton-Raphson or the simplex algorithm). Under the threshold model of binary disease, we develop an Expectation Maximization (EM) algorithm to solve for the maximum likelihood estimates (MLEs). The new EM algorithm is developed by treating both the unobserved genotype and the disease liability as missing values. As a result, the EM iteration equations have the same form as the normal equation system in linear regression. The EM algorithm is further modified to take into account sexual dimorphism in the linkage maps. Applying the EM-implemented ML method to a four-way-cross mouse family, we detected two regions on the fourth chromosome that have evidence of QTLs controlling the segregation of fibrosarcoma, a form of connective tissue cancer. The two QTLs explain 50-60% of the variance in the disease liability. We also applied a Bayesian method previously developed (modified to take into account sex-specific maps) to this data set and detected one additional QTL on chromosome 13 that explains another 26% of the variance of the disease liability. All the QTLs detected primarily show dominance effects.

Algorithms↗
PubMed2000

On-line EM algorithm for the normalized gaussian network.

A normalized gaussian network (NGnet) (Moody & Darken, 1989) is a network of local linear regression units. The model softly partitions the input space by normalized gaussian functions, and each local unit linearly approximates the output within the partition. In this article, we propose a new on-line EMalgorithm for the NGnet, which is derived from the batch EMalgorithm (Xu, Jordan, &Hinton 1995), by introducing a discount factor. We show that the on-line EM algorithm is equivalent to the batch EM algorithm if a specific scheduling of the discount factor is employed. In addition, we show that the on-line EM algorithm can be considered as a stochastic approximation method to find the maximum likelihood estimator. A new regularization method is proposed in order to deal with a singular input distribution. In order to manage dynamic environments, where the input-output distribution of data changes over time, unit manipulation mechanisms such as unit production, unit deletion, and unit division are also introduced based on probabilistic interpretation. Experimental results show that our approach is suitable for function approximation problems in dynamic environments. We also apply our on-line EM algorithm to robot dynamics problems and compare our algorithm with the mixtures-of-experts family.

Algorithms↗