We consider a general inference setting for discrete probabilistic graphical models where we seek maximum a posteriori (MAP) estimates for a subset of the random variables (max nodes), marginalizing over the rest (sum...
详细信息
ISBN:
(纸本)9781618395993
We consider a general inference setting for discrete probabilistic graphical models where we seek maximum a posteriori (MAP) estimates for a subset of the random variables (max nodes), marginalizing over the rest (sum nodes). We present a hybrid message-passing algorithm to accomplish this. The hybrid algorithm passes a mix of sum and max messages depending on the type of source node (sum or max). We derive our algorithm by showing that it falls out as the solution of a particular relaxation of a variational framework. We further show that the expectation Maximization algorithm can be seen as an approximation to our algorithm. Experimental results on synthetic and real-world datasets, against several baselines, demonstrate the efficacy of our proposed algorithm.
We present new training methods that aim to mitigate local optima and slow convergence in unsupervised training by using additional imperfect objectives. In its simplest form, lateen EM alternates between the two obje...
详细信息
ISBN:
(纸本)9781937284114
We present new training methods that aim to mitigate local optima and slow convergence in unsupervised training by using additional imperfect objectives. In its simplest form, lateen EM alternates between the two objectives of ordinary "soft" and "hard" expectation maximization (EM) algorithms. Switching objectives when stuck can help escape local optima. We find that applying a single such alternation already yields state-of-the-art results for English dependency grammar induction. More elaborate lateen strategies track both objectives, with each validating the moves proposed by the other. Disagreements can signal earlier opportunities to switch or terminate, saving iterations. De-emphasizing fixed points in these ways eliminates some guesswork from tuning EM. An evaluation against a suite of unsupervised dependency parsing tasks, for a variety of languages, showed that lateen strategies significantly speed up training of both EM algorithms, and improve accuracy for hard EM.
Although the standard formulations of prediction problems involve fully-observed and noiseless data drawn in an i.i.d. manner, many applications involve noisy and/or missing data, possibly involving dependencies. We s...
详细信息
ISBN:
(纸本)9781618395993
Although the standard formulations of prediction problems involve fully-observed and noiseless data drawn in an i.i.d. manner, many applications involve noisy and/or missing data, possibly involving dependencies. We study these issues in the context of high-dimensional sparse linear regression, and propose novel estimators for the cases of noisy, missing, and/or dependent data. Many standard approaches to noisy or missing data, such as those using the EM algorithm, lead to optimization problems that are inherently non-convex, and it is difficult to establish theoretical guarantees on practical algorithms. While our approach also involves optimizing non-convex programs, we are able to both analyze the statistical error associated with any global optimum, and prove that a simple projected gradient descent algorithm will converge in polynomial time to a small neighborhood of the set of global minimizers. On the statistical side, we provide non-asymptotic bounds that hold with high probability for the cases of noisy, missing, and/or dependent data. On the computational side, we prove that under the same types of conditions required for statistical consistency, the projected gradient descent algorithm will converge at geometric rates to a near-global minimizer. We illustrate these theoretical predictions with simulations, showing agreement with the predicted scalings.
We propose a method for vector field learning with outliers, called vector field consensus (VFC). It could distinguish inliers from outliers and learn a vector field fitting for the inliers simultaneously. A prior is ...
详细信息
ISBN:
(纸本)9781457703942
We propose a method for vector field learning with outliers, called vector field consensus (VFC). It could distinguish inliers from outliers and learn a vector field fitting for the inliers simultaneously. A prior is taken to force the smoothness of the field, which is based on the Tiknonov regularization in vector-valued reproducing kernel Hilbert space. Under a Bayesian framework, we associate each sample with a latent variable which indicates whether it is an inlier, and then formulate the problem as maximum a posteriori problem and use expectation Maximization algorithm to solve it. The proposed method possesses two characteristics: 1) robust to outliers, and being able to tolerate 90% outliers and even more, 2) computationally efficient. As an application, we apply VFC to solve the problem of mismatch removing. The results demonstrate that our method outperforms many state-of-the-art methods, and it is very robust.
This study is concerned with the challenging and timely problem of channel equalisation and data detection for orthogonal frequency division multiplexing (OFDM) systems in the presence of frequency-selective and very ...
详细信息
This study is concerned with the challenging and timely problem of channel equalisation and data detection for orthogonal frequency division multiplexing (OFDM) systems in the presence of frequency-selective and very rapidly time-varying channels. The algorithm is based on the space alternating generalised expectation-maximisation (SAGE) technique which is particularly well suited to multicarrier signal formats and can be easily extended to multi-input multi-output-OFDM systems. In fast fading channels, the orthogonality between subcarriers is destroyed by the time variation of a fading channel over an OFDM symbol duration which causes severe inter-carrier interference (ICI) and, in conventional frequency-domain approaches, results in an irreducible error floor. The proposed joint data detection and equalisation algorithm updates the data sequences in series leading to a receiver structure that also incorporates ICI cancellation, enabling the system to operate at high vehicle speeds. A computational complexity investigation as well as detailed computer simulations indicate that this algorithm has significant performance and complexity advantages over existing suboptimal detection and equalisation algorithms proposed earlier in the literature.
This article investigates a new method of motion estimation based on block matching criterion through the modeling of image blocks by a mixture of two and three Gaussian distributions. Mixture parameters (weights, mea...
详细信息
This article investigates a new method of motion estimation based on block matching criterion through the modeling of image blocks by a mixture of two and three Gaussian distributions. Mixture parameters (weights, means vectors, and covariance matrices) are estimated by the expectation Maximization algorithm (EM) which maximizes the log-likelihood criterion. The similarity between a block in the current image and the more resembling one in a search window on the reference image is measured by the minimization of Extended Mahalanobis distance between the clusters of mixture. Performed experiments on sequences of real images have given good results, and PSNR reached 3 dB.
Methods: To test this hypothesis, the authors compared the accuracy and variation in accuracy of organ activity estimates obtained from planar and SPECT scans at various count levels. A simulated phantom population wi...
详细信息
Methods: To test this hypothesis, the authors compared the accuracy and variation in accuracy of organ activity estimates obtained from planar and SPECT scans at various count levels. A simulated phantom population with realistic variations in anatomy and biodistribution was used to model variability in a patient population. Planar and SPECT projections were simulated using previously validated Monte Carlo simulation tools. The authors simulated the projections at count levels approximately corresponding to 1.5-30 min of total acquisition time. The projections were processed using previously described quantitative SPECT (QSPECT) and planar (QPlanar) methods. The QSPECT method was based on the OS-EM algorithm with compensations for attenuation, scatter, and collimator-detector response. The QPlanar method is based on the ML-EM algorithm using the same model-based compensation for all the image degrading effects as the QSPECT method. The volumes of interests (VOIs) were defined based on the true organ configuration in the phantoms. The errors in organ activity estimates from different count levels and processing methods were compared in terms of mean and standard deviation over the simulated phantom population. Results: There was little degradation in quantitative reliability when the acquisition time was reduced by half for the QSPECT method (the mean error changed by < 1%, e.g., 0.9%-0.3%=0.6% for the spleen). The magnitude of the errors and variations in errors for large organ with high uptake were still acceptable for 1.5 min scans, even though the errors were slightly larger than those for the 30 min scans (i.e., < 2% for liver, < 3% for heart). The errors over the ranges of scan times studied for the QPlanar method were all within 0.3% for all organs. Conclusions: These data indicate that, for the purposes of organ activity estimation, acquisition times could be reduced at least by a factor of 2 for the QSPECT and QPlanar methods with little effect on the errors
The objective of this paper is to develop a robust maximum likelihood estimates (MLE) for the stochastic state space model via the expectation maximization (EM) algorithm to cope with observation outliers. Two types o...
详细信息
ISBN:
(纸本)9781612844879
The objective of this paper is to develop a robust maximum likelihood estimates (MLE) for the stochastic state space model via the expectation maximization (EM) algorithm to cope with observation outliers. Two types of outliers and their influence have been studied in this sequel namely the additive (AO) and innovative outliers (IO). Due to the sensitivity of the MLE to AO and IO we propose two techniques for robustifying the MLE: the weighted maximum likelihood estimate (WMLE) and the trimmed maximum likelihood estimate (TMLE). The WMLE is easy to implement, however it is still sensitive to IO. On the other hand, the TMLE is a combinatorial optimization problem and hard to implement but it is efficient to all types of outliers presented here. A Monte Carlo simulation result shows the efficiency of the TMLE and WMLE based on the EM algorithm.
Hidden semi-Markov models are a generalization of the well-known hidden Markov model. They allow for a greater flexibility of sojourn time distributions, which implicitly follow a geometric distribution in the case of...
详细信息
Hidden semi-Markov models are a generalization of the well-known hidden Markov model. They allow for a greater flexibility of sojourn time distributions, which implicitly follow a geometric distribution in the case of a hidden Markov chain. The aim of this paper is to describe hsmm, a new software package for the statistical computing environment R. This package allows for the simulation and maximum likelihood estimation of hidden semi-Markov models. The implemented expectation Maximization algorithm assumes that the time spent in the last visited state is subject to right-censoring. it is therefore not subject to the common limitation that the last visited state terminates at the last observation. Additionally, hsmm permits the user to make inferences about the underlying state sequence via the Viterbi algorithm and smoothing probabilities. (C) 2008 Elsevier B.V. All rights reserved.
Reinforcement learning models generally assume that a stimulus is presented that allows a learner to unambiguously identify the state of nature, and the reward received is drawn from a distribution that depends on tha...
详细信息
Reinforcement learning models generally assume that a stimulus is presented that allows a learner to unambiguously identify the state of nature, and the reward received is drawn from a distribution that depends on that state. However, in any natural environment, the stimulus is noisy. When there is state uncertainty, it is no longer immediately obvious how to perform reinforcement learning, since the observed reward cannot be unambiguously allocated to a state of the environment. This letter addresses the problem of incorporating state uncertainty in reinforcement learning models. We show that simply ignoring the uncertainty and allocating the reward to the most likely state of the environment results in incorrect value estimates. Furthermore, using only the information that is available before observing the reward also results in incorrect estimates. We therefore introduce a new technique, posterior weighted reinforcement learning, in which the estimates of state probabilities are updated according to the observed rewards ( e. g., if a learner observes a reward usually associated with a particular state, this state becomes more likely). We show analytically that this modified algorithm can converge to correct reward estimates and confirm this with numerical experiments. The algorithm is shown to be a variant of the expectation-maximization algorithm, allowing rigorous convergence analyses to be carried out. A possible neural implementation of the algorithm in the cortico-basal-ganglia-thalamic network is presented, and experimental predictions of our model are discussed.
暂无评论