Scalable kernel methods, including kernel ridge regression, often rely on
low-rank matrix approximations using the Nystrom method, which involves
selecting landmark points from large data sets. The existing approaches to
selecting landmarks are typically computationally demanding as they require
manipulating and performing computations with large matrices in the input or
feature space. In this paper, our contribution is twofold. The first
contribution is to propose a novel landmark selection method that promotes
diversity using an efficient two-step approach. Our landmark selection
technique follows a coarse to fine strategy, where the first step computes
importance scores with a single pass over the whole data. The second step
performs K-means clustering on the constructed coreset to use the obtained
centroids as landmarks. Hence, the introduced method provides tunable
trade-offs between accuracy and efficiency. Our second contribution is to
investigate the performance of several landmark selection techniques using a
novel application of kernel methods for predicting structural responses due to
earthquake load and material uncertainties. Our experiments exhibit the merits
of our proposed landmark selection scheme against baselines.

本文研究基于核方法的可扩展建模，提出了一种新颖的选点方法，促进了多样性和算法效率的平衡，并应用在地震荷载预测中取得了良好的效果。

应用重要性抽样的核岭回归在地震响应预测中的应用

Kernel Ridge Regression Using Importance Sampling with Application to  Seismic Response Prediction

The Nystr\"om method has long been popular for scaling up kernel methods. Its
theoretical guarantees and empirical performance rely critically on the quality
of the landmarks selected. We study landmark selection for Nystr\"om using
Determinantal Point Processes (DPPs), discrete probability models that allow
tractable generation of diverse samples. We prove that landmarks selected via
DPPs guarantee bounds on approximation errors; subsequently, we analyze
implications for kernel ridge regression. Contrary to prior reservations due to
cubic complexity of DPPsampling, we show that (under certain conditions) Markov
chain DPP sampling requires only linear time in the size of the data. We
present several empirical results that support our theoretical analysis, and
demonstrate the superior performance of DPP-based landmark selection compared
with existing approaches.

本文通过使用 DPP 的方式选择 landmark 点来保证至少达到一定的误差边界并且减少了时间效率，在实验中它表现比现有的方法更好，特别是在 Nyström 方法和 kernel ridge regression 中有应用。

快速 DPP 采样在 Nystrom 法中的应用，用于核方法

Fast DPP Sampling for Nyström with Application to Kernel Methods

High computational costs of manifold learning prohibit its application for
large point sets. A common strategy to overcome this problem is to perform
dimensionality reduction on selected landmarks and to successively embed the
entire dataset with the Nystr\"om method. The two main challenges that arise
are: (i) the landmarks selected in non-Euclidean geometries must result in a
low reconstruction error, (ii) the graph constructed from sparsely sampled
landmarks must approximate the manifold well. We propose the sampling of
landmarks from determinantal distributions on non-Euclidean spaces. Since
current determinantal sampling algorithms have the same complexity as those for
manifold learning, we present an efficient approximation running in linear
time. Further, we recover the local geometry after the sparsification by
assigning each landmark a local covariance matrix, estimated from the original
point set. The resulting neighborhood selection based on the Bhattacharyya
distance improves the embedding of sparsely sampled manifolds. Our experiments
show a significant performance improvement compared to state-of-the-art
landmark selection techniques.

本文介绍了一种基于确定性分布采样的非欧几里得空间地标选择方法，能够解决大量点集的流形学习计算问题，并在原始数据集的基础上恢复局部几何，利用 Bhattacharyya 距离进行相似性计算和嵌入，与现有技术相比大幅提升了性能。