权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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-Laplacian正则化的基于图的半监督学习算法。特别是，研究人员证明，学习算法具有连续的限制，对应于解决加权p-Laplace方程的粘性意义。在小标记数据和无限未标记数据的限制下，当p小于数据的本征维数时，Lp-Laplacian正则化是不适定的. 该项目旨在严格解决这一猜想。研究人员使用这些连续极限来研究标记数据的分数与算法性能之间的关系，并基于这些见解开发新的更有效的计算算法。该项目的第二个目标是开发和分析一类新的单调有限差分格式的曲线和曲面的曲率驱动的运动，严格的收敛性证明。研究者最近发现了一种构造曲线曲面一类曲率运动的单调有限差分格式的一般方法。他实现了各种运动的新计划，实验测试收敛速度，并严格证明收敛到粘度的解决方案使用巴尔斯-Souganwestern框架。新方案的单调性允许开发完全隐式和无条件单调的时间步长方案，并保证近似捕获正确的连续动态。