skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: IAN: Iterated Adaptive Neighborhoods for Manifold Learning and Dimensionality Estimation
Abstract Invoking the manifold assumption in machine learning requires knowledge of the manifold's geometry and dimension, and theory dictates how many samples are required. However, in most applications, the data are limited, sampling may not be uniform, and the manifold's properties are unknown; this implies that neighborhoods must adapt to the local structure. We introduce an algorithm for inferring adaptive neighborhoods for data given by a similarity kernel. Starting with a locally conservative neighborhood (Gabriel) graph, we sparsify it iteratively according to a weighted counterpart. In each step, a linear program yields minimal neighborhoods globally, and a volumetric statistic reveals neighbor outliers likely to violate manifold geometry. We apply our adaptive neighborhoods to nonlinear dimensionality reduction, geodesic computation, and dimension estimation. A comparison against standard algorithms using, for example, k-nearest neighbors, demonstrates the usefulness of our approach.  more » « less
Award ID(s):
1822650
PAR ID:
10462084
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Neural Computation
Volume:
35
Issue:
3
ISSN:
0899-7667
Page Range / eLocation ID:
453 to 524
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))
    Modern machine learning systems are increasingly trained on large amounts of data embedded in high-dimensional spaces. Often this is done without analyzing the structure of the dataset. In this work, we propose a framework to study the geometric structure of the data. We make use of our recently introduced non-negative kernel (NNK) regression graphs to estimate the point density, intrinsic dimension, and linearity of the data manifold (curvature). We further generalize the graph construction and geometric estimation to multiple scales by iteratively merging neighborhoods in the input data. Our experiments demonstrate the effectiveness of our proposed approach over other baselines in estimating the local geometry of the data manifolds on synthetic and real datasets. 
    more » « less
  2. ; (, The Journal of Geometric Analysis)
    We construct an injective map from the set of holomorphic equivalence classes of neighborhoods M of a compact complex manifold C into a finite dimension complex Euclidean space when the normal bundle of C in M is fixed and is either weakly negative or 2-positive. 
    more » « less
  3. ; ; ; ; ; ; (, MODVIS Workshop on Computational Models in Vision)
    Understanding circuit properties from physiological data presents two challenges: (i) recordings do not reveal connectivity, and (ii) stimuli only exercise circuits to a limited extent. We address these challenges for the mouse visual system with a novel neural manifold obtained using unsupervised algorithms. Each point in our manifold is a neuron; nearby neurons respond similarly in time to similar parts of a stimulus ensemble. This ensemble includes drifting gratings and flows, i.e., patterns resembling what a mouse would “see” running through fields. Regarding (i), our manifold differs from the standard practice in computational neuroscience: embedding trials in neural coordinates. Topology matters: we infer that, if the circuit consists of separate components, the manifold is discontinuous (illustrated with retinal data). If there is significant overlap between circuits, the manifold is nearly-continuous (cortical data). Regarding (ii), most of the cortical manifold is not activated with conventional gratings, despite their prominence in laboratory settings. Our manifold suggests organizing cortical circuitry by a few specialized circuits for specific members of the stimulus ensemble, together with circuits involving ‘multi-stimuli’-responding neurons. To approach real circuits, local neighborhoods in the manifold are identified with actual circuit components. For retinal data, we show these components correspond to distinct ganglion cell types by their mosaic-like receptive field organization, while for cortical data, neighborhoods organize neurons by type (excitatory/inhibitory) and anatomical layer. In summary: the topology of neural organization reflects well the underlying anatomy and physiology of the retina and the visual cortex. 
    more » « less
  4. ; ; ; (, Conference on Neural Information Processing Systems)
    Deep neural networks have revolutionized many real world applications, due to their flexibility in data fitting and accurate predictions for unseen data. A line of research reveals that neural networks can approximate certain classes of functions with an arbitrary accuracy, while the size of the network scales exponentially with respect to the data dimension. Empirical results, however, suggest that networks of moderate size already yield appealing performance. To explain such a gap, a common belief is that many data sets exhibit low dimensional structures, and can be modeled as samples near a low dimensional manifold. In this paper, we prove that neural networks can efficiently approximate functions supported on low dimensional manifolds. The network size scales exponentially in the approximation error, with an exponent depending on the intrinsic dimension of the data and the smoothness of the function. Our result shows that exploiting low dimensional data structures can greatly enhance the efficiency in function approximation by neural networks. We also implement a sub-network that assigns input data to their corresponding local neighborhoods, which may be of independent interest. 
    more » « less
  5. ; ; ; (, Advances in Neural Information Processing Systems)
    Deep neural networks have revolutionized many real world applications, due to their flexibility in data fitting and accurate predictions for unseen data. A line of research reveals that neural networks can approximate certain classes of functions with an arbitrary accuracy, while the size of the network scales exponentially with respect to the data dimension. Empirical results, however, suggest that networks of moderate size already yield appealing performance. To explain such a gap, a common belief is that many data sets exhibit low dimensional structures, and can be modeled as samples near a low dimensional manifold. In this paper, we prove that neural networks can efficiently approximate functions supported on low dimensional manifolds. The network size scales exponentially in the approximation error, with an exponent depending on the intrinsic dimension of the data and the smoothness of the function. Our result shows that exploiting low dimensional data structures can greatly enhance the efficiency in function approximation by neural networks. We also implement a sub-network that assigns input data to their corresponding local neighborhoods, which may be of independent interest. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email