An official website of the United States government
This article reports an experimental work that unveils some interesting yet unknown phenomena underneath all smooth nonlinear maps. The findings are based on the fact that, generalizing the conventional gradient dynamics, the right singular vectors of the Jacobian matrix of any differentiable map point in directions that are most pertinent to the infinitesimal deformation of the underlying function and that the singular values measure the rate of deformation in the corresponding directions. A continuous adaption of these singular vectors, therefore, constitutes a natural moving frame that carries indwelling information of the variation. This structure exists in any dimensional space, but the development of the fundamental theory and algorithm for surface exploration is an important first step for immediate application and further generalization. In this case, trajectories of these singular vectors, referred to as singular curves, unveil some intriguing patterns per the given function. At points where singular values coalesce, curious and complex behaviors occur, manifesting specific landmarks for the function. Upon analyzing the dynamics, it is discovered that there is a remarkably simple and universal structure underneath all smooth two-parameter maps. This work delineates graphs with this interesting dynamical system and the possible new discovery that, analogous to the double helix with two base parings in DNA, two strands of critical curves and eight base pairings could encode properties of a generic and arbitrary surface. This innate structure suggests that this approach could provide a unifying paradigm in functional genetics, where all smooth surfaces could be genome-sequenced and classified accordingly. Such a concept has sparked curiosity and warrants further investigation.
more »
« less
State aggregation learning from Markov transition data
State aggregation is a popular model reduction method rooted in optimal control. It reduces the complexity of engineering systems by mapping the system’s states into a small number of meta-states. The choice of aggregation map often depends on the data analysts’ knowledge and is largely ad hoc. In this paper, we propose a tractable algorithm that estimates the probabilistic aggregation map from the system’s trajectory. We adopt a soft-aggregation model, where each meta-state has a signature raw state, called an anchor state. This model includes several common state aggregation models as special cases. Our proposed method is a simple two- step algorithm: The first step is spectral decomposition of empirical transition matrix, and the second step conducts a linear transformation of singular vectors to find their approximate convex hull. It outputs the aggregation distributions and disaggregation distributions for each meta-state in explicit forms, which are not obtainable by classical spectral methods. On the theoretical side, we prove sharp error bounds for estimating the aggregation and disaggregation distributions and for identifying anchor states. The analysis relies on a new entry-wise deviation bound for singular vectors of the empirical transition matrix of a Markov process, which is of independent interest and cannot be deduced from existing literature. The application of our method to Manhattan traffic data successfully generates a data-driven state aggregation map with nice interpretations.
more »
« less
- Award ID(s):
- 1925845
- PAR ID:
- 10289814
- Date Published:
- Journal Name:
- Advances in neural information processing systems
- ISSN:
- 1049-5258
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper, we propose a novel representation learning framework, namely HIN2Vec, for heterogeneous information networks (HINs). The core of the proposed framework is a neural network model, also called HIN2Vec, designed to capture the rich semantics embedded in HINs by exploiting different types of relationships among nodes. Given a set of relationships specified in forms of meta-paths in an HIN, HIN2Vec carries out multiple prediction training tasks jointly based on a target set of relationships to learn latent vectors of nodes and meta-paths in the HIN. In addition to model design, several issues unique to HIN2Vec, including regularization of meta-path vectors, node type selection in negative sampling, and cycles in random walks, are examined. To validate our ideas, we learn latent vectors of nodes using four large-scale real HIN datasets, including Blogcatalog, Yelp, DBLP and U.S. Patents, and use them as features for multi-label node classification and link prediction applications on those networks. Empirical results show that HIN2Vec soundly outperforms the state-of-the-art representation learning models for network data, including DeepWalk, LINE, node2vec, PTE, HINE and ESim, by 6.6% to 23.8% ofmicro-f1 in multi-label node classification and 5% to 70.8% of MAP in link prediction.more » « less
-
We study a regularized interacting particle method for computing aggregation patterns and near singular solutions of a Keller–Segel (KS) chemotaxis system in two and three space dimensions, then further develop the DeepParticle method to learn and generate solutions under variations of physical parameters. The KS solutions are approximated as empirical measures of particles that self-adapt to the high gradient part of solutions. We utilize the expressiveness of deep neural networks (DNNs) to represent the transform of samples from a given initial (source) distribution to a target distribution at a finite time 𝑇 prior to blowup without assuming the invertibility of the transforms. In the training stage, we update the network weights by minimizing a discrete 2-Wasserstein distance between the input and target empirical measures. To reduce the computational cost, we develop an iterative divide-and-conquer algorithm to find the optimal transition matrix in the Wasserstein distance. We present numerical results of the DeepParticle framework for successful learning and generation of KS dynamics in the presence of laminar and chaotic flows. The physical parameter in this work is either the evolution time or the flow amplitude in the advection-dominated regime.more » « less
-
This paper considers a random component-wise variant of the unnormalized power method, which is similar to the regular power iteration except that only a random subset of indices is updated in each iteration. For the case of normal matrices, it was previously shown that random component-wise updates converge in the mean-squared sense to an eigenvector of eigenvalue 1 of the underlying matrix even in the case of the matrix having spectral radius larger than unity. In addition to the enlarged convergence regions, this study shows that the eigenvalue gap does not directly a ect the convergence rate of the randomized updates unlike the regular power method. In particular, it is shown that the rate of convergence is a ected by the phase of the eigenvalues in the case of random component-wise updates, and the randomized updates favor negative eigenvalues over positive ones. As an application, this study considers a reformulation of the component-wise updates revealing a randomized algorithm that is proven to converge to the dominant left and right singular vectors of a normalized data matrix. The algorithm is also extended to handle large-scale distributed data when computing an arbitrary rank approximation of an arbitrary data matrix. Numerical simulations verify the convergence of the proposed algorithms under di erent parameter settings.more » « less
-
Abstract We introduce an efficient stochastic interacting particle-field (SIPF) algorithm with no history dependence for computing aggregation patterns and near singular solutions of parabolic-parabolic Keller-Segel (KS) chemotaxis system in three-dimensional (3D) space. In our algorithm, the KS solutions are approximated as empirical measures of particles coupled with a smoother field (concentration of chemo-attractant) variable computed by a spectral method. Instead of using heat kernels that cause history dependence and high memory cost, we leverage the implicit Euler discretization to derive a one-step recursion in time for stochastic particle positions and the field variable based on the explicit Green’s function of an elliptic operator of the form Laplacian minus a positive constant. In numerical experiments, we observe that the resulting SIPF algorithm is convergent and self-adaptive to the high-gradient part of solutions. Despite the lack of analytical knowledge (such as a self-similar ansatz) of a blowup, the SIPF algorithm provides a low-cost approach to studying the emergence of finite-time blowup in 3D space using only dozens of Fourier modes and by varying the amount of initial mass and tracking the evolution of the field variable. Notably, the algorithm can handle multi-modal initial data and the subsequent complex evolution involving the merging of particle clusters and the formation of a finite time singularity with ease.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
