Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (4 results)

  • Thesis
  • Peer Reviewed
UCLA Electronic Theses and Dissertations (2018)

In recent years, the need for pattern recognition and data analysis has grown exponentially in various fields of scientific research. My research is centered around graph Laplacian based techniques for image processing and machine learning. Three papers pertaining to this theme will be presented in this thesis.The first work is an application of graph Laplacian regularization to the problem of convolutional sparse coding. The additional regularization improves the robustness of the sparse representation with respect to noise, and has empirically shown to improve the performance of denoising on several well-known images. Efficient algorithms for computing the eigen-decomposition of the graph Laplacian were also incorporated to the solver for fast implementations of the method.The second piece of work studies the convergence of the graph Allen-Cahn scheme. A technique inspired by the maximum principle for the heat equation is used to show stability of the convex-splitting numeric scheme. This coupled with techniques from convex optimization allows for a proof of convergence under an a-posteriori condition. The analysis is then generalized to handle spectral trunction, a common method to save computational cost, and also to the case of multi-class classification. In particular, the results for spectral trunction are drastically different from that of the original scheme in the worst case, but does not present itself in practical applications.The third piece of work combines two fields of research, uncertainty quantification, and

semi-supervised learning on graphs. The work presents a unified Bayesian framework thatincorporates most previous methods for graph-based semi-supervised learning. A Bayesianframework allows for the computation of uncertainty for certain quantities under the pos-terior distribution. We show via solid numerical evidence that for a few carefully designedquantities, the expectations computed under the posterior yields meaningful notions of un-certainty for the classification problem. Efficient numerical methods were also devised tomake possible the evaluation of these quantities for large scale graphs.

    Cover page: Analysis and Application of Graph-Based Semi-Supervised Learning Methods
    • Article
    • Peer Reviewed
    UCLA Previously Published Works (2017)
    The graph Laplacian and the graph cut problem are closely related to Markov random fields, and have many applications in clustering and image segmentation. The diffuse interface model is widely used for modeling in material science, and can also be used as a proxy to total variation minimization. In Bertozzi and Flenner (Multiscale Model Simul 10(3):1090–1118, 2012), an algorithm was developed to generalize the diffuse interface model to graphs to solve the graph cut problem. This work analyzes the conditions for the graph diffuse interface algorithm to converge. Using techniques from numerical PDE and convex optimization, monotonicity in function value and convergence under an a posteriori condition are shown for a class of schemes under a graph-independent stepsize condition. We also generalize our results to incorporate spectral truncation, a common technique used to save computation cost, and also to the case of multiclass classification. Various numerical experiments are done to compare theoretical results with practical performance.
      Cover page: Convergence of the Graph Allen–Cahn Scheme
      • Article
      • Peer Reviewed
      UCLA Previously Published Works (2018)
      Classification of high dimensional data finds wide-ranging applications. In many of these applications equipping the resulting classification with a measure of uncertainty may be as important as the classification itself. In this paper we introduce, develop algorithms for, and investigate the properties of, a variety of Bayesian models for the task of binary classification; via the posterior distribution on the classification labels, these methods automatically give measures of uncertainty. The methods are all based around the graph formulation of semi-supervised learning. We provide a unified framework which brings together a variety of methods which have been introduced in different communities within the mathematical sciences. We study probit classification in the graph-based setting, generalize the level-set method for Bayesian inverse problems to the classification setting, and generalize the Ginzburg-Landau optimization-based classifier to a Bayesian setting; we also show that the probit and level set approaches are natural relaxations of the harmonic function approach introduced in [Zhu et al 2003]. We introduce efficient numerical methods, suited to large data-sets, for both MCMC-based sampling as well as gradient-based MAP estimation. Through numerical experiments we study classification accuracy and uncertainty quantification for our models; these experiments showcase a suite of datasets commonly used to evaluate graph-based semi-supervised learning algorithms.
        Cover page: Uncertainty Quantification in Graph-Based Classification of High Dimensional Data
        • Article
        • Peer Reviewed
        UCLA Previously Published Works (2020)
          Cover page: Uncertainty quantification for semi-supervised multi-class classification in image processing and ego-motion analysis of body-worn videos
          Top