Representations of sets are challenging to learn because operations on sets should be permutation-invariant. To this end, we propose a Permutation-Optimisation module that learns how to permute a set end-to-end. The permuted set can be further processed to learn a permutation-invariant representation of that set, avoid…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “permutation learning”
Regularizes RNNs to be invariant to input order.
problem Making RNNs invariant to input order.
method Stochastic regularization to enforce permutation invariance.
result Improves model performance on permutation invariant tasks.
A new method reduces memory requirements for sorting high-dimensional data.
problem Efficiently sorting and organizing high-dimensional data with low memory usage.
method Iteratively shuffles N indices and applies SoftSort optimization steps.
result Significantly improves sorting quality for multidimensional data.
New sampling methods improve Shapley value estimation for machine learning models.
problem Approximating Shapley values for non-trivial models is computationally challenging.
method Investigates new quadrature techniques and quasi-Monte Carlo methods for permutation sampling.
result Significant improvements in Shapley value estimates over existing methods.
Many problems at the intersection of combinatorics and computer science require solving for a permutation that optimally matches, ranks, or sorts some data. These problems usually have a task-specific, often non-differentiable objective function that data-driven algorithms can use as a learning signal. In this paper, w…
ShuffleNet is a state-of-the-art light weight convolutional neural network architecture. Its basic operations include group, channel-wise convolution and channel shuffling. However, channel shuffling is manually designed empirically. Mathematically, shuffling is a multiplication by a permutation matrix. In this paper, …
Derives formulae for general permutation equivariant layers and presents a second order graph variational encoder.
problem Tackles the limitation of previous equivariant neural networks by considering permutations of matrices.
method Derives formulae for general permutation equivariant layers, including matrix permutations. Presents a second order graph variational encoder.
result Latent distribution of equivariant generative models must be exchangeable.
Recently, the method of b-bit minwise hashing has been applied to large-scale linear learning and sublinear time near-neighbor search. The major drawback of minwise hashing is the expensive preprocessing cost, as the method requires applying (e.g.,) k=200 to 500 permutations on the data. The testing time can also be ex…
New algorithm learns permutations mixtures with optimal sample complexity.
problem Learning mixtures of permutations in high-dimensional settings.
method Combining groups of pairwise comparisons and combinatorial method of moments.
result Optimal sample complexity proportional to log(n) for high-dimensional data.
A new method learns graph distributions invariant to node ordering.
problem Graphs are hard to model due to node ordering invariance issues.
method Score-based generative modeling with permutation equivariant graph neural network.
result The method achieves better or comparable graph generation results.
We consider a simple and overarching representation for permutation-invariant functions of sequences (or multiset functions). Our approach, which we call Janossy pooling, expresses a permutation-invariant function as the average of a permutation-sensitive function applied to all reorderings of the input sequence. This …
A new tensor ring mixture model improves density estimation efficiency.
problem Efficient probability density estimation in statistical machine learning.
method Tensor ring decomposition with mixture model for adaptive weights.
result Enhanced expressive capability and flexibility in density estimation.
Permutation invariant network learns Wasserstein metrics.
problem Understanding the space of probability measures and comparing distributions.
method Permutation invariant network mapping samples to a low-dimensional space.
result Network can generalize to compute distances between unseen densities and learn moments.
Improves modeling of sets with permutation invariant densities.
problem Challenges in calculating trace limit practicality of current methods.
method Proposes an alternative approach to define permutation equivariant transformations with closed form trace.
result Improves both training and final performance.
We propose new positive definite kernels for permutations. First we introduce a weighted version of the Kendall kernel, which allows to weight unequally the contributions of different item pairs in the permutations depending on their ranks. Like the Kendall kernel, we show that the weighted version is invariant to rela…
Improves full conformal prediction for stochastic non-conformity measures.
problem Inability of existing conditions to guarantee full conformal prediction validity under stochastic settings.
method Introduces a new sufficient condition: Conditional Independence & Permutation Invariance in Distribution.
result Corrects the insufficient condition and provides a new sufficient condition for full conformal prediction validity.
Sample efficiency and scalability to a large number of agents are two important goals for multi-agent reinforcement learning systems. Recent works got us closer to those goals, addressing non-stationarity of the environment from a single agent's perspective by utilizing a deep net critic which depends on all observatio…
Novel neural GP kernels learn stable, flexible covariance structures.
problem Scalable and flexible covariance kernels for Gaussian processes.
method Directly learn kriging coefficients and conditional standard deviations using deep neural architectures exploiting permutation-equivariant structure.
result Improved training stability and data efficiency with expressive, non-stationary kernels.
New neural network architecture for auction design exploiting permutation symmetry.
problem Designing incentive-compatible auctions that maximize expected revenue.
method Constructed a permutation-equivariant neural network architecture.
result Permutation-equivariant architectures can perfectly recover optimal mechanisms.
CPI overcomes limitations of permutation importance by providing accurate variable selection.
problem Misidentification of unimportant variables in complex models due to covariate correlations.
method Developed a model agnostic and computationally lean Conditional Permutation Importance (CPI) approach.
result CPI provides accurate type-I error control and more parsimonious variable selection.
Permutation of any two hidden units yields invariant properties in typical deep generative neural networks. This permutation symmetry plays an important role in understanding the computation performance of a broad class of neural networks with two or more hidden units. However, a theoretical study of the permutation sy…
QWO speeds up causal discovery in LiGAMs by .
problem Scalability issues in permutation-based causal discovery methods for LiGAMs.
method Constructing a specific DAG for a permutation and searching over permutations to minimize edge count.
result QWO achieves a speed-up of compared to state-of-the-art methods.
Bayesian optimization method for permutations accelerates combinatorial search.
problem Optimizing expensive-to-evaluate objectives on permutation problems.
method LAW2ORDER, a batch Bayesian optimization method based on the acquisition weighted kernel.
result LAW2ORDER achieves sublinear batch cumulative regret, demonstrating accelerated search.
Permutation-equivariant neural networks improve auction mechanisms by reducing regret and sample complexity.
problem Designing optimal auction mechanisms that balance revenue and bidders' regret.
method Introduced permutation-equivariant neural networks to auction mechanisms.
result Permutation-equivariant neural networks decrease expected ex-post regret and improve model generalizability.
In this paper, we consider the problem of learning functions over sets, i.e., functions that are invariant to permutations of input set items. Recent approaches of pooling individual element embeddings can necessitate extremely large embedding sizes for challenging functions. We address this challenge by allowing stand…
We introduce a simple permutation equivariant layer for deep learning with set structure.This type of layer, obtained by parameter-sharing, has a simple implementation and linear-time complexity in the size of each set. We use deep permutation-invariant networks to perform point-could classification and MNIST-digit sum…
Efficiently discovers causal DAG permutations without additional assumptions.
problem Learning a DAG up to Markov equivalence.
method Utilizing DAG-specific problem structure, introduces an efficient algorithm for sparse permutations.
result Significant improvement in permutation discovery compared to existing algorithms.
C-MinHash reduces the number of permutations needed for MinHash from thousands to just two.
problem Approximating Jaccard similarity in large binary datasets using many permutations.
method Initial permutation followed by circulant shifting of a second permutation to generate hashes.
result C-MinHash achieves unbiased Jaccard similarity estimation with uniformly smaller variance.
A new method improves feature importance and model stress-testing reliability.
problem Estimating feature contributions in machine learning models for trust and transparency.
method Replacing multiple random permutations with a single, deterministic, and optimal permutation.
result Improved bias-variance tradeoffs and accuracy in challenging scenarios.
New method corrects correlation bias in feature importance.
problem Correlations between features in high-dimensional data bias statistical and machine learning models.
method Pairwise Permutation Algorithm (PPA)
result PPA corrects correlation bias, identifying biological relevant biomarkers.
Transformers tend to learn more symmetric functions in sequence data.
problem Understanding inductive bias in Transformers with infinitely over-parameterized models.
method Analyzing Transformers in the Gaussian process limit, using representation theory of the symmetric group.
result Transformers are biased towards more permutation symmetric functions, and this can be quantitatively predicted.
Cheap Permutation Testingmath.ST
Cheap permutation tests speed up distribution testing without sacrificing accuracy.
problem Efficiently testing distribution differences and independence.
method Group datapoints into bins and permute only these bins, using stored sufficient statistics.
result Cheap permutation tests maintain the accuracy and optimality of standard tests but are significantly faster.
Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passingcs.LG
SMP model preserves proximity and permutation in graph neural networks.
problem Challenges in graph mining, such as community and leader finding.
method Stochastic Message Passing (SMP) model that maintains proximity and permutation-equivariance.
result SMP model effectively preserves node proximities and permutation-equivariance.
C-OPH improves One Permutation Hashing by using a shorter circulant permutation.
problem Improving the accuracy of One Permutation Hashing (OPH) for Jaccard similarity estimation.
method Develops a new densification method using a shorter circulant permutation.
result Achieves the smallest estimation variance for Jaccard similarity.
Random permutations can offer faster convergence than with-replacement sampling for some functions.
problem Understanding when and how random permutations outperform with-replacement sampling in SGD convergence.
method Analyzing convergence rates for different function classes (1D strongly convex, general strongly convex, quadratic strongly convex).
result The optimal convergence gap between random and permutation-based SGD varies from exponential to nonexistent, depending on the function class.
New neural networks respect symmetries in symmetric tensors, improving efficiency and generalization.
problem Learning from symmetric tensors efficiently and respecting their inherent symmetries.
method Developed two characterizations of linear permutation equivariant functions between symmetric power spaces of R^n.
result These functions are highly data efficient compared to standard MLPs and generalize well to different sizes of symmetric tensors.
TRIP detects unreliable feature importance scores in random forests.
problem Unreliable feature importance scores in random forests due to model extrapolation.
method Develops TRIP (Test for Reliable Interpretation via Permutation) to detect unreliable permutation feature importance scores.
result TRIP reliably detects unreliable permutation feature importance scores in high-dimensional settings.
Unknotted cyclesmath.CO
Permutations linked to knots and links, with unknots counted by Schröder numbers.
problem Understanding permutations as knots and links.
method Using grid diagrams and Bennequin's inequality.
result Permutations corresponding to unknots and links are counted by Schröder numbers.
Proposes neuron alignment to optimize mode connectivity in neural networks.
problem Understanding and optimizing mode connectivity in deep neural networks.
method Introduces neuron alignment to approximate optimal weight permutations and improve mode connectivity.
result Neuron alignment significantly alleviates robust loss barriers and improves model robustness and accuracy.
LMC loss barrier decreases to zero with large network width.
problem Understanding the LMC phenomenon in neural networks.
method Fine-grained analysis of LMC for two-layer ReLU networks.
result LMC loss barrier decreases to zero at a rate of O(m^-1/2) for large network width.
New basis for permutation equivariant layers reduces computation costs.
problem Efficiently computing permutation equivariant layers in neural networks.
method Generalized partition algebra basis with low-rank tensors.
result Low-rank tensors enable faster computation compared to orbit basis.
We tackle permutation in linear regression with a new inference framework.
problem Statistical investigation of permutation in linear regression models.
method Localization step followed by conditional Monte Carlo test and coefficient inference.
result Valid statistical inference procedures for permutation and regression coefficients.
There has been a recent surge of interest in studying permutation-based models for ranking from pairwise comparison data. Despite being structurally richer and more robust than parametric ranking models, permutation-based models are less well understood statistically and generally lack efficient learning algorithms. In…
Permutability of surface transforms yields discrete analogs.
problem Discretization of smooth surfaces with specific properties.
method Permutability of transforms of smooth surfaces.
result Discrete surfaces with discrete analogs of original properties.
We shrink confidence sets for equivalent discrete distributions using permutation equivalence.
problem Building high-probability confidence sets for equivalent discrete distributions.
method Exploiting permutation-equivalence to refine confidence sets.
result Confidence sets shrink at asymptotic rates of and .
Deep neural networks have demonstrated cutting edge performance on various tasks including classification. However, it is well known that adversarially designed imperceptible perturbation of the input can mislead advanced classifiers. In this paper, Permutation Phase Defense (PPD), is proposed as a novel method to resi…
New method uses Multiple Choice Learning for speech separation.
problem Ambiguous task of assigning model predictions to ground truth signals.
method Uses Multiple Choice Learning (MCL) instead of Permutation Invariant Training (PIT).
result MCL matches PIT performance but is computationally advantageous.
The introduction of convolutional layers greatly advanced the performance of neural networks on image tasks due to innately capturing a way of encoding and learning translation-invariant operations, matching one of the underlying symmetries of the image domain. In comparison, there are a number of problems in which the…