Nonlinear Partial Differential Equations, Monotone Numerical Schemes, and Scaling Limits for Semi-Supervised Learning on Graphs

图半监督学习的非线性偏微分方程、单调数值方案和标度极限

基本信息

批准号：
1713691
负责人：
Jeffrey Calder
金额：
$ 16.31万
依托单位：
University of Minnesota-Twin Cities
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-08-15 至 2020-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1713691&HistoricalAwards=false
关键词：
Nonlinear Partial Differential Equations Monotone

项目摘要

Machine learning aims to harness the power of data to train algorithms to make predictions and perform complex tasks in science, engineering, medicine, and everyday life. Despite the wide success of machine learning, the growing size of typical data sets is creating serious computational challenges, partially due to our incomplete understanding of how algorithms work in the big data regime. The first goal of this project is to address these issues within a branch of machine learning called graph-based semi-supervised learning, which has found applications in problems such as protein sequencing, website classification, and speech recognition. The investigator analyzes some recently-proposed algorithms for semi-supervised learning. A deep mathematical understanding of these algorithms explains why they work and, more importantly, when they will fail. The investigator uses these insights to develop new, fast, and more efficient algorithms for semi-supervised learning. The second goal of this project is to develop and study new algorithms for curvature motions of curves and surfaces that are stable, efficient, and convergent. Curvature motion has found many applications in science and engineering, including materials science, computer vision, image processing, and recently in data science and machine learning. Curvature motion describes, for example, the motion of soap bubbles as well as the evolution of polycrystalline materials (such as metals and ceramic) during the manufacturing process. Because both machine learning and curvature motions have very broad applications across science and engineering, any improvement in algorithms and in our understanding of them could have broad societal impacts.The first objective of this project is to study rigorously a recently-proposed algorithm for graph-based semi-supervised learning based on Lp-Laplacian regularization. In particular, the investigator proves that the learning algorithms have continuum limits that correspond to solving a weighted p-Laplace equation in the viscosity sense. In the limit of small labeled data and infinite unlabeled data, it has recently been conjectured that Lp-Laplacian regularization is ill-posed when p is smaller than the intrinsic dimension of the data. The project aims to settle this conjecture rigorously. The investigator uses these continuum limits to study the relationship between the fraction of labeled data and the performance of the algorithms, and to develop new and more efficient computational algorithms based on these insights. The second objective of the project is to develop and analyze a new class of monotone finite difference schemes for curvature-driven motions of curves and surfaces, for which rigorous convergence proofs are available. The investigator has recently discovered a general technique for constructing monotone finite difference schemes for a wide class of curvature motions of curves and surfaces. He implements the new schemes for a variety of motions, experimentally tests convergence rates, and rigorously proves convergence to the viscosity solution using the Barles-Souganidis framework. Monotonicity of the new schemes allows for the development of fully implicit and unconditionally monotone time-stepping schemes, and guarantees the approximations are capturing the correct continuum dynamics.

机器学习旨在利用数据的力量来训练算法，以做出预测并执行科学、工程、医学和日常生活中的复杂任务。尽管机器学习取得了广泛的成功，但典型数据集规模的不断增长正在带来严峻的计算挑战，部分原因是我们对算法在大数据领域如何工作的不完全理解。该项目的首要目标是在称为基于图的半监督学习的机器学习分支中解决这些问题，该分支已在蛋白质测序、网站分类和语音识别等问题中得到应用。研究人员分析了一些最近提出的半监督学习算法。对这些算法的深入数学理解可以解释它们为何有效，更重要的是，它们何时会失败。研究人员利用这些见解来开发新的、快速的、更高效的半监督学习算法。该项目的第二个目标是开发和研究稳定、高效、收敛的曲线和曲面曲率运动的新算法。曲率运动在科学和工程领域有许多应用，包括材料科学、计算机视觉、图像处理，以及最近在数据科学和机器学习中的应用。例如，曲率运动描述了肥皂泡的运动以及制造过程中多晶材料（例如金属和陶瓷）的演变。由于机器学习和曲率运动在科学和工程领域都有非常广泛的应用，因此算法和我们对它们的理解的任何改进都可能产生广泛的社会影响。该项目的第一个目标是严格研究最近提出的图算法基于Lp-拉普拉斯正则化的半监督学习。特别是，研究人员证明了学习算法具有连续极限，该极限对应于求解粘度意义上的加权 p-拉普拉斯方程。在小标记数据和无限未标记数据的限制下，最近有人推测，当 p 小于数据的固有维度时，Lp-拉普拉斯正则化是不适定的。该项目旨在严格解决这一猜想。研究人员使用这些连续极限来研究标记数据的比例与算法性能之间的关系，并根据这些见解开发新的、更有效的计算算法。该项目的第二个目标是开发和分析一类新的单调有限差分格式，用于曲线和曲面的曲率驱动运动，并提供严格的收敛证明。研究人员最近发现了一种为各种曲线和曲面的曲率运动构建单调有限差分格式的通用技术。他针对各种运动实施了新方案，通过实验测试了收敛速度，并使用 Barles-Souganidis 框架严格证明了粘度解的收敛性。新方案的单调性允许开发完全隐式和无条件单调时间步长方案，并保证近似捕获正确的连续动态。