More Like this

1. Sampling Sparse Representations with Randomized Measurement Langevin Dynamics

   https://doi.org/10.1145/3427585  

   Wang, Kafeng; Xiong, Haoyi; Bian, Jiang; Zhu, Zhanxing; Gao, Qian; Guo, Zhishan; Xu, Cheng-Zhong; Huan, Jun; Dou, Dejing (April 2021, ACM Transactions on Knowledge Discovery from Data)

   null (Ed.)

   Stochastic Gradient Langevin Dynamics (SGLD) have been widely used for Bayesian sampling from certain probability distributions, incorporating derivatives of the log-posterior. With the derivative evaluation of the log-posterior distribution, SGLD methods generate samples from the distribution through performing as a thermostats dynamics that traverses over gradient flows of the log-posterior with certainly controllable perturbation. Even when the density is not known, existing solutions still can first learn the kernel density models from the given datasets, then produce new samples using the SGLD over the kernel density derivatives. In this work, instead of exploring new samples from kernel spaces, a novel SGLD sampler, namely, Randomized Measurement Langevin Dynamics (RMLD) is proposed to sample the high-dimensional sparse representations from the spectral domain of a given dataset. Specifically, given a random measurement matrix for sparse coding, RMLD first derives a novel likelihood evaluator of the probability distribution from the loss function of LASSO, then samples from the high-dimensional distribution using stochastic Langevin dynamics with derivatives of the logarithm likelihood and Metropolis–Hastings sampling. In addition, new samples in low-dimensional measuring spaces can be regenerated using the sampled high-dimensional vectors and the measurement matrix. The algorithm analysis shows that RMLD indeed projects a given dataset into a high-dimensional Gaussian distribution with Laplacian prior, then draw new sparse representation from the dataset through performing SGLD over the distribution. Extensive experiments have been conducted to evaluate the proposed algorithm using real-world datasets. The performance comparisons on three real-world applications demonstrate the superior performance of RMLD beyond baseline methods. 

   more » « less
2. Algorithm and Hardware Co-Design for FPGA Acceleration of Hamiltonian Monte Carlo Based No-U-Turn Sampler

   Wang, Y.; Li, P. (July 2021, The 32nd IEEE International Conference on Application-specific Systems, Architectures and Processors)

   null (Ed.)

   Monte Carlo (MC) methods are widely used in many research areas such as physical simulation, statistical analysis, and machine learning. Application of MC methods requires drawing fast mixing samples from a given probability distribution. Among existing sampling methods, the Hamiltonian Monte Carlo (HMC) utilizes gradient information during Hamiltonian simulation and can produce fast mixing samples at the highest efficiency. However, without carefully chosen simulation parameters for a specific problem, HMC generally suffers from simulation locality and computation waste. As a result, the No-U-Turn Sampler (NUTS) has been proposed to automatically tune these parameters during simulation and is the current state-of-the-art sampling algorithm. However, application of NUTS requires frequent gradient calculation of a given distribution and high-volume vector processing, especially for large-scale problems, leading to drawing an expensively large number of samples and a desire of hardware acceleration. While some hardware acceleration works have been proposed for traditional Markov Chain Monte Carlo (MCMC) and HMC methods, there is no existing work targeting hardware acceleration of the NUTS algorithm. In this paper, we present the first NUTS accelerator on FPGA while addressing the high complexity of this state-of-the-art algorithm. Our hardware and algorithm co-optimizations include an incremental resampling technique which leads to a more memory efficient architecture and pipeline optimization for multi-chain sampling to maximize the throughput. We also explore three levels of parallelism in the NUTS accelerator to further boost performance. Compared with optimized C++ NUTS package: RSTAN, our NUTS accelerator can reach a maximum speedup of 50.6X and an energy improvement of 189.7X. 

   more » « less
3. Smoothed Estimators for Markov Chains with Sparse Spatial Observations

   https://doi.org/10.1111/gean.12222  

   Kang, Wei; Rey, Sergio J. (October 2019, Geographical Analysis)

   Empirical applications of the Markov chain model and its spatial extensions suffer from issues induced by the sparse transition probability matrix, which usually results from adopting maximum likelihood estimators (MLEs). Two discrete kernel estimators with cross‐validated parameters are proposed for reducing the sparsity in the estimated transition probability matrix. Monte Carlo experiments suggest that these estimators are not only quite effective in producing a much less sparse matrix, alleviating issues related to sparsity, but also superior to MLEs in terms of lowering the mean squared error for individual and total transition probability, giving rise to the better recovery of the underlying dynamics. 

   more » « less
4. Scaling Up Sparse Support Vector Machine by Simultaneous Feature and Sample Reduction

   Zhang, W; Hong, B; Ye, J; Cai, D; He, X; Wang, J. (January 2017, Proceedings of the 34th International Conference on Machine Learning)

   Sparse support vector machine (SVM) is a popular classification technique that can simultaneously learn a small set of the most interpretable features and identify the support vectors. It has achieved great successes in many real-world applications. However, for large-scale problems involving a huge number of samples and extremely high-dimensional features, solving sparse SVMs remains challenging. By noting that sparse SVMs induce sparsities in both feature and sample spaces, we propose a novel approach, which is based on accurate estimations of the primal and dual optima of sparse SVMs, to simultaneously identify the features and samples that are guaranteed to be irrelevant to the outputs. Thus, we can remove the identified inactive samples and features from the training phase, leading to substantial savings in both the memory usage and computational cost without sacrificing accuracy. To the best of our knowledge, the proposed method is the first static feature and sample reduction method for sparse SVMs. Experiments on both synthetic and real datasets (e.g., the kddb dataset with about 20 million samples and 30 million features) demonstrate that our approach significantly outperforms state-of-the-art methods and the speedup gained by our approach can be orders of magnitude. 

   more » « less
5. Likelihood level adapted estimation of marginal likelihood for Bayesian model selection

   https://doi.org/10.1016/j.cma.2025.118141  

   De, Subhayan; Farzad, Reza; Brewick, Patrick T; Johnson, Erik A; Wojtkiewicz, Steven F (October 2025, Computer Methods in Applied Mechanics and Engineering)

   In computational mechanics, multiple models are often present to describe a physical system. While Bayesian model selection is a helpful tool to compare these models using measurement data, it requires the computationally expensive estimation of a multidimensional integral — known as the marginal likelihood or as the model evidence (i.e., the probability of observing the measured data given the model) — over the multidimensional parameter domain. This study presents efficient approaches for estimating this marginal likelihood by transforming it into a one-dimensional integral that is subsequently evaluated using a quadrature rule at multiple adaptively-chosen iso-likelihood contour levels. Three different algorithms are proposed to estimate the probability mass at each adapted likelihood level using samples from importance sampling, stratified sampling, and Markov chain Monte Carlo (MCMC) sampling, respectively. The proposed approach is illustrated — with comparisons to Monte Carlo, nested, and MultiNest sampling — through four numerical examples. The first, an elementary example, shows the accuracies of the three proposed algorithms when the exact value of the marginal likelihood is known. The second example uses an 11-story building subjected to an earthquake excitation with an uncertain hysteretic base isolation layer with two models to describe the isolation layer behavior. The third example considers flow past a cylinder when the inlet velocity is uncertain. Based on the these examples, the method with stratified sampling is by far the most accurate and efficient method for complex model behavior in low dimension, particularly considering that this method can be implemented to exploit parallel computation. In the fourth example, the proposed approach is applied to heat conduction in an inhomogeneous plate with uncertain thermal conductivity modeled through a 100 degree-of-freedom Karhunen–Loève expansion. The results indicate that MultiNest cannot efficiently handle the high-dimensional parameter space, whereas the proposed MCMC-based method more accurately and efficiently explores the parameter space. The marginal likelihood results for the last three examples — when compared with the results obtained from standard Monte Carlo sampling, nested sampling, and MultiNest algorithm — show good agreement. 

   more » « less