A new hierarchical clustering method selects representative points from sub-minimum-spanning-trees.
problem Selecting representative points for hierarchical clustering to improve robustness and reliability.
method Identify representative points using reciprocal nearest data points in sub-minimum-spanning-trees.
result The proposed algorithm outperforms other methods in accuracy and efficiency.
The study calculates the growth rate of reciprocal hyperbolic elements in Hecke groups.
problem Counting reciprocal hyperbolic elements in Hecke groups.
method Analyzes conjugacy classes of hyperbolic elements associated with reciprocal geodesics.
result Determines the asymptotic growth rate and limiting constant of primitive conjugacy classes of reciprocal hyperbolic elements.
Reciprocal learning unifies various machine learning algorithms.
problem Understanding the convergence of machine learning algorithms.
method Introducing reciprocal learning as a generalization of various algorithms using decision theory.
result Reciprocal learning algorithms converge at linear rates to an approximately optimal model under certain conditions.
The nearest neighbor problem is defined as follows: Given a set P of n points in some metric space (X,D), build a data structure that, given any point q, returns a point in P that is closest to q (its "nearest neighbor" in P). The data structure stores additional information about the set P, which is th…
We propose a novel class of network models for temporal dyadic interaction data. Our goal is to capture a number of important features often observed in social interactions: sparsity, degree heterogeneity, community structure and reciprocity. We propose a family of models based on self-exciting Hawkes point processes i…
Characterizes Lebesgue points using nearest neighbor methods.
problem Consistency of classification algorithms based on nearest neighbors.
method Characterization of Lebesgue points via 1-Nearest Neighbor regression.
result Proves convergence of 1-Nearest Neighbor classification algorithms in metric spaces.
The paper proves generalization bounds and stopping rules for self-selected data in reciprocal learning.
problem Generalization of learning algorithms using self-selected data.
method Proves universal generalization bounds using covering numbers and Wasserstein ambiguity sets.
result Provides stopping rules for reciprocal learning algorithms to ensure out-of-sample performance.
The paper models social networks with varying levels of reciprocity.
problem Understanding diverse reciprocal behavior in social networks.
method Developed a preferential attachment model with heterogeneous reciprocity.
result Captures the heavy-tailed nature of empirical degree distributions and identifies multiple user groups.
If we pick n random points uniformly in [0,1]d and connect each point to its k−nearest neighbors, then it is well known that there exists a giant connected component with high probability. We prove that in [0,1]d it suffices to connect every point to cd,1loglogn points chosen randomly among its $…
A new model predicts network events with improved accuracy and interpretability.
problem Predicting and understanding complex dynamic relational data in networks.
method Mutually Exciting Latent Space Hawkes (LSH) model for continuous-time networks.
result The LSH model outperforms existing models in prediction accuracy and interpretability.
Classifies reciprocal elements in Hecke groups, generalizing Sarnak's work.
problem Classifying reciprocal elements in Hecke groups.
method Classifying and parametrizing reciprocal classes in Hecke groups Γp for p≥3. result Generalizes Sarnak's result on reciprocal elements in the modular group.
In the machine learning field, dimensionality reduction is an important task. It mitigates the undesired properties of high-dimensional spaces to facilitate classification, compression, and visualization of high-dimensional data. During the last decade, researchers proposed many new (non-linear) techniques for dimensio…
The paper analyzes how much data points can be altered to change their rank in nearest neighbor searches.
problem Vulnerability of nearest neighbor search in high-dimensional data.
method Statistical analysis of perturbation needed to change neighbor rank.
result Derived statistical distribution of perturbation needed to modify neighbor rank.
VNNGP uses nearest neighbors to approximate GPs, improving scalability and performance.
problem Scalability issues in Gaussian process approximations.
method Sparse precision structure via nearest neighbors, variational framework.
result VNNGP outperforms low-rank methods and is less prone to overfitting.
The paper models reciprocity in interbank markets using a statistical null model.
problem Understanding the importance of individual banks in financial networks.
method Developed an exponential random graph model to account for reciprocal links on both topological and weighted levels.
result Weighted reciprocity in interbank markets is more significant than network size and volume before the financial crisis.
Reciprocal processes are acausal generalizations of Markov processes introduced by Bernstein in 1932. In the literature, a significant amount of attention has been focused on developing dynamical models for reciprocal processes. Recently, probabilistic graphical models for reciprocal processes have been provided. This …
Estimates growth of reciprocal classes in Hecke groups.
problem Estimating the growth of reciprocal conjugacy classes in Hecke groups.
method Using free product structure and word lengths of reciprocal elements, with tools from basic probability theory.
result Estimates the asymptotic growth of reciprocal conjugacy classes in Hecke groups.
The Nearest subspace classifier (NSS) finds an estimation of the underlying subspace within each class and assigns data points to the class that corresponds to its nearest subspace. This paper mainly studies how well NSS can be generalized to new samples. It is proved that NSS is strongly consistent under certain assum…
New method speeds up k-means clustering for large k by improving nearest-neighbor search.
problem Efficiently clustering large datasets with high-dimensional points.
method Seeded Approximate Nearest-Neighbor Search methods to improve Lloyd's algorithm.
result Significantly faster k-means clustering for large k values.
A new ensemble method improves kNN performance by extending the neighborhood rule.
problem Traditional kNN's limitations when test points are outside the spherical region and ensemble's high errors.
method Determines neighbors in k steps, using bootstrap samples and optimal models selection.
result The proposed ensemble method outperforms state-of-the-art methods on 17 benchmark datasets.
In many scientific disciplines structures in high-dimensional data have to be found, e.g., in stellar spectra, in genome data, or in face recognition tasks. In this work we present a novel approach to non-linear dimensionality reduction. It is based on fitting K-nearest neighbor regression to the unsupervised regressio…
This paper proposes a new hashing-based KNN technique for faster nearest neighbor selection.
problem Slowness of KNN in big datasets due to searching entire dataset.
method Divide data space into subcells, use hashing to map data points, and select nearest neighbors layer by layer.
result The proposed technique offers competitive performance with KNN and KDtree while significantly improving time efficiency.
Formulates Hilbert reciprocity law on 3-manifolds.
problem Developing arithmetic topology on 3-manifolds.
method Formulated an analogue of Hilbert reciprocity law using intersection forms and Kummer extensions.
result Cyclic covers of links are analogues of Kummer extensions.
New model accounts for scale variation and noise in pairwise comparisons.
problem Nonreciprocal pairwise comparisons in decision analysis.
method Additive model with structured matrix and random perturbation.
result Explicit estimators and probability assessments of admissible ranking regions.
We consider machine learning in a comparison-based setting where we are given a set of points in a metric space, but we have no access to the actual distances between the points. Instead, we can only ask an oracle whether the distance between two points i and j is smaller than the distance between the points i an…
A reciprocal recommendation problem is one where the goal of learning is not just to predict a user's preference towards a passive item (e.g., a book), but to recommend the targeted user on one side another user from the other side such that a mutual interest between the two exists. The problem thus is sharply differen…
Minimal spectral radii found for specific matrix types.
problem Finding smallest spectral radii for certain matrix classes.
method Analyzing skew-reciprocal integer matrices of fixed even dimensions.
result Most classes of matrices have smaller spectral radii than their reciprocal counterparts.
New topological methods for hypergraph data improve community detection and pattern recognition.
problem Community detection and pattern recognition in hypergraph data.
method Introducing a new topological space structure of hypergraph data, proposing modified nearest neighbors methods.
result Improved methods for community detection and pattern recognition in hypergraph data.
Algorithms often carry out equally many computations for "easy" and "hard" problem instances. In particular, algorithms for finding nearest neighbors typically have the same running time regardless of the particular problem instance. In this paper, we consider the approximate k-nearest-neighbor problem, which is the pr…
Study on geodesics and dihedral groups in lattices.
problem Growth and distribution of conjugacy classes of dihedral subgroups.
method Generalizing earlier work on reciprocal geodesics, proving equidistribution.
result Reciprocal geodesics are equidistributed in the unit tangent bundle.
We rigorously define the Liouville action functional for finitely generated, purely loxodromic quasi-Fuchsian group using homology and cohomology double complexes naturally associated with the group action. We prove that the classical action - the critical point of the Liouville action functional, considered as a funct…
A framework for flagging content with limited data.
problem Content flagging with scarce target-language data.
method Nearest-neighbor architecture using Transformer representations.
result Significant performance improvements over prior work.
Reciprocal processes are acausal generalizations of Markov processes introduced by Bernstein in 1932. In the literature, a significant amount of attention has been focused on developing dynamical models for reciprocal processes. In this paper, we provide a probabilistic graphical model for reciprocal processes. This le…
Both supervised and unsupervised machine learning algorithms have been used to learn partition-based index structures for approximate nearest neighbor (ANN) search. Existing supervised algorithms formulate the learning task as finding a partition in which the nearest neighbors of a training set point belong to the same…
Constructs harmonic maps near retractions in hyperbolic spaces.
problem Finding harmonic maps near retractions in hyperbolic spaces.
method Constructs harmonic maps to the hyperbolic plane from quasidisks, and to convex hulls from sets in the boundary at infinity of pinched Hadamard manifolds.
result Harmonic maps are bounded from nearest-point retractions in hyperbolic spaces.
We show that the nearest point retraction is a uniform quasi-isometry from the Thurston metric on a hyperbolic domain in the Riemann sphere to the boundary of the convex hull of its complement. As a corollary, one obtains explicit bounds on the quasi-isometry constant of the nearest point retraction with respect to the…
Algorithm identifies nearest mode in noisy data.
problem Identifying the point with the minimum k-th nearest neighbor distance in unknown multivariate probability density.
method Sequential learning algorithm using noisy oracle queries to adaptively decide which points to query.
result Upper bounds on query complexity show significant improvement over baselines.
Study geodesics entering a fixed cusp neighborhood multiple times.
problem Understanding geodesics entering a specific cusp neighborhood multiple times.
method Investigate reciprocal geodesics entering a fixed cusp neighborhood a fixed number of times.
result Characterized the class of reciprocal geodesics entering a fixed cusp neighborhood a fixed number of times.
New method reconstructs interbank networks enforcing reciprocity to improve stability and risk prediction.
problem Lack of public interbank network data and difficulty in replicating cycles.
method Proposes a new network reconstruction method enforcing sparsity and link reciprocity from aggregate data.
result Adding reciprocity improves prediction of network properties, including largest real eigenvalue and eccentricity of eigenvalues.
SPlit optimizes dataset splitting for better model performance.
problem Improving model performance through optimal dataset splitting.
method Adapting Support Points (SP) algorithm for subsampling and categorical variables in a sequential nearest neighbor approach.
result SPlit significantly improves worst-case testing performance compared to random splitting.
The condensed nearest neighbor (CNN) algorithm is a heuristic for reducing the number of prototypical points stored by a nearest neighbor classifier, while keeping the classification rule given by the reduced prototypical set consistent with the full set. I present an upper bound on the number of prototypical points ac…
We explore and expand the Soft Nearest Neighbor Loss to measure the entanglement of class manifolds in representation space: i.e., how close pairs of points from the same class are relative to pairs of points from different classes. We demonstrate several use cases of the loss. As an analytical to…
The paper studies empirical processes from nearest neighbors in regression.
problem Estimating conditional cumulative distribution functions and local linear regression.
method Uniform central limit theorem and non-asymptotic bound under local bracketing entropy and uniform entropy numbers.
result Gaussian limit of empirical process with simple covariance.
Growth rates of geodesics on modular orbifolds are studied.
problem Understanding growth rates of geodesics on modular orbifolds.
method Exhaustion of modular orbifold by compact subsurfaces, analysis of low lying geodesics and reciprocal geodesics.
result Growth rates of low lying geodesics and reciprocal geodesics converge to the full set's growth rate.
Proposes a boundary detection method inspired by LLE for high-dimensional data.
problem Identifying boundary points from data on an embedded manifold.
method Inspired by locally linear embedding, uses nearest neighbor search schemes and spectral properties of local covariance matrix.
result Enhanced boundary detection in noisy data.
Deep neural networks (DNNs) enable innovative applications of machine learning like image recognition, machine translation, or malware detection. However, deep learning is often criticized for its lack of robustness in adversarial settings (e.g., vulnerability to adversarial inputs) and general inability to rationalize…
Introduces Grassmann Distance Complexity to measure algebraic set nearest point problems.
problem Measuring complexity of finding nearest points in Grassmannian space.
method Uses Lipschitz critical point theory and o-minimal geometry.
result Establishes fundamental properties of GDC, including bounds and finiteness conditions.
A new ensemble method using random projections for kNN classification.
problem Improving kNN classification accuracy through ensemble methods.
method Random projection of bootstrap samples into lower dimensions, using extended neighbourhood rule for base learners.
result Enhanced classification accuracy compared to traditional kNN and other ensembles.