The paper develops mixed-integer formulations for neural networks using partitioning.
problem Optimizing trained ReLU neural networks with balanced model size and tightness.
method Partitioning node inputs into groups, forming the convex hull via disjunctive programming.
result The proposed formulations outperform existing ones, especially with fewer partitions.
Deep networks partition input space into regions with complex affine mappings.
problem Understanding the geometry and complexity of deep neural networks.
method Analyzed deep networks as max-affine spline operators and power diagrams.
result Composition of deep networks results in a progressively subdivided power diagram.
New technique reduces verification time for neural networks.
problem Verifying neural networks for safety-critical applications.
method Shadow prices for more efficient input partitioning.
result Significant reduction in computation times for verification.
We introduce a novel approach to feed-forward neural network interpretation based on partitioning the space of sequences of neuron activations. In line with this approach, we propose a model-specific interpretation method, called YASENN. Our method inherits many advantages of model-agnostic distillation, such as an abi…
A new method for semi-supervised text classification using layer partitioning.
problem Adapting neural semi-supervised learning to discrete text inputs.
method Decompose neural network into feature extractor F and update layer U for training. Use dropout for systematic noise. result Improves text classification especially on short texts compared to state-of-the-art methods.
In this article, the logic rule ensembles approach to supervised learning is applied to the unsupervised or semi-supervised clustering. Logic rules which were obtained by combining simple conjunctive rules are used to partition the input space and an ensemble of these rules is used to define a similarity matrix. Simila…
Extensions to given-data Sobol' index estimators for large models.
problem Efficiently compute Sobol' indices for models with many inputs.
method General definition, streaming algorithm, heuristic filtering.
result Comparable accuracy and lower memory usage for large models.
This paper presents a new approach for Gaussian process (GP) regression for large datasets. The approach involves partitioning the regression input domain into multiple local regions with a different local GP model fitted in each region. Unlike existing local partitioned GP approaches, we introduce a technique for patc…
A hierarchical routing mixture of experts model for complex regression tasks.
problem Complex data distribution in regression tasks.
method Binary tree-structured hierarchical routing mixture of experts (HRME) model with classifiers and simple regression models.
result Effective prediction with simple leaf experts in multimodal data.
In this paper, we investigate a divide and conquer approach to Kernel Ridge Regression (KRR). Given n samples, the division step involves separating the points based on some underlying disjoint partition of the input space (possibly via clustering), and then computing a KRR estimate for each partition. The conquering s…
Enhances random forests by smoothing predictions for better performance.
problem Suboptimal performance due to piecewise constant predictions in random forests.
method Kernel-based smoothing mechanism to introduce local regularity.
result Smoothed random forest model consistently improves predictive performance.
Improved neural network robustness certification through tighter convex relaxations.
problem Certifying neural network robustness to perturbed and adversarial inputs.
method Exploiting ReLU network structure, novel partition-based certification procedure.
result Tightens existing linear programming relaxations to achieve zero relaxation error asymptotically.
Graphs can model interactions between vertices, but how well depends on graph structure.
problem Lack of formal characterization of GNNs' ability to model interactions between vertices.
method Formalized interaction strength using separation rank and quantified it for different partitions of vertices.
result GNNs' ability to model interactions is primarily determined by the partition's walk index.
ParK efficiently solves kernel ridge regression for large datasets.
problem Large-scale kernel ridge regression efficiency and accuracy.
method Partitioning feature space with random projections and iterative optimization.
result Provably maintains statistical accuracy with reduced space and time complexity.
Develops an MS-inspired algorithm for regression mode finding and space partitioning.
problem Finding local modes of regression functions and partitioning input space.
method Mean-shift-inspired algorithm for iterative gradient ascent.
result Proves convergence and rates of convergence for estimated local modes.
A new procedure aggregates models to predict data from multiple clusters.
problem Predicting data from multiple clusters with different underlying models.
method Three-step procedure: clustering, model fitting, and aggregation.
result The method outperforms existing models in various prediction problems.
Unsupervised space partitioning improves ANNS performance without pre-processing.
problem Efficient nearest neighbor search in high-dimensional spaces.
method Custom unsupervised learning framework for space partitioning and learning-to-search.
result Our method outperforms state-of-the-art approaches on ANNS benchmarks.
Proposes a partitioned least squares model for feature grouping.
problem Modeling with feature groups to assess variable importance.
method Two methods: alternating least squares and exact reformulation.
result Exact method provides better results in less time.
Origami uses SGX enclaves and blinding to protect deep neural network inference privacy.
problem Protecting deep neural network inference privacy in machine learning services.
method Combines enclave execution, cryptographic blinding, and accelerator-based computation.
result Demonstrates improved privacy-preserving inference performance compared to prior work.
Proposes a stratified sampling method for high-dimensional models using neural active manifolds.
problem Uncertainty propagation in computationally expensive models with many inputs.
method Neural active manifolds for nonlinear dimensionality reduction, followed by stratification in the reduced space.
result Effective variance reduction in high-dimensional models using stratified sampling.
MD-split+ creates locally valid prediction regions for complex data.
problem Localized prediction regions for complex data.
method Localized model performance-based partitioning of feature space X.
result MD-split+ creates valid prediction regions that scale to high dimensions.
In this work, we propose a simple but effective method to interpret black-box machine learning models globally. That is, we use a compact binary tree, the interpretation tree, to explicitly represent the most important decision rules that are implicitly contained in the black-box machine learning models. This tree is l…
InfoCNF improves conditional image generation by optimizing latent code partitioning and solver error tolerances.
problem Efficiently conditioning CNFs on high-dimensional latent codes for conditional image generation.
method InfoCNF partitions latent space into class-specific and shared codes, and uses gating networks to optimize ODE solver error tolerances.
result InfoCNF improves test accuracy on CIFAR10 while reducing NFEs and maintaining comparable likelihood scores.
Novel PairNet speeds up ANN training with fast hyperparameter optimization.
problem Slow training of traditional ANNs with many hyperparameters.
method Partition inputs into subspaces, optimize hyperparameters via linear equations, train local PairNets in subspaces.
result PairNet achieves higher speeds and lower MSEs than traditional ANNs.
Paper improves classification rates for private data.
problem Classifying data with privacy constraints and relaxed assumptions.
method Introduced a novel approach for classification under privacy constraints, relaxing the strong density assumption.
result Achieved minimax optimal convergence rates without strong density assumption.
Adaptive region-based active learning seeks labels for complex data.
problem Efficiently label complex datasets with minimal human effort.
method Adaptive region partitioning and active learning for distinct predictors.
result Substantial empirical benefits over existing methods.
We study large-scale spatial systems that contain exogenous variables, e.g. environmental factors that are significant predictors in spatial processes. Building predictive models for such processes is challenging because the large numbers of observations present makes it inefficient to apply full Kriging. In order to r…
Single-head attention approximates any function under various norms.
problem Universal approximation of functions using attention mechanisms.
method Interpreting attention as partitioning and summing linear transformations.
result Single-head attention can approximate any continuous function under L∞-norm and Lebesgue integrable functions under Lp-norm. The study predicts Kronecker coefficients using interpretable machine learning models.
problem Predicting Kronecker coefficients of the symmetric group.
method Employed interpretable machine learning models with input features of triples of partitions and b-loadings.
result Achieved an accuracy of approximately 83% and over 99% with transformer-based models.
Algorithm detects free products in disk mapping class groups.
problem Detecting free products in mapping class groups of punctured disks.
method Algorithm based on Dynnikov coordinates to verify completeness and reveal free product structure.
result Algorithm determines exact structure of free products generated by Dehn twists.
RIPE is a novel deterministic and easily understandable prediction algorithm developed for continuous and discrete ordered data. It infers a model, from a sample, to predict and to explain a real variable Y given an input variable X∈X (features). The algorithm extracts a sparse set of hyperrectangles $…
Sparse codes improve optimal control tasks with correlated inputs.
problem Optimal control tasks with correlated feature inputs.
method Used a sparse code to represent natural images in an optimal control task solved with neuro-dynamic programming.
result An over-complete sparse code increases memory capacity and learning speed beyond a complete code.
Spectral method for detecting communities in time-varying networks from noisy signals.
problem Detect communities in time-varying networks from noisy signals.
method Spectral algorithm based on latent stochastic blockmodel.
result Consistent recovery of community structure in time-varying networks.
Paper improves neural network robustness analysis for safety-critical systems.
problem Uncertainty in neural network outputs for safety-critical systems.
method Unified propagation and partition approaches to provide tighter bounds.
result Proposed algorithms give tighter bounds than existing methods for the same computation time.
The paper deals with regression problems, in which the nonsmooth target is assumed to switch between different operating modes. Specifically, piecewise smooth (PWS) regression considers target functions switching deterministically via a partition of the input space, while switching regression considers arbitrary switch…
PASCO speeds up graph clustering for large graphs.
problem Efficiently clustering large graphs with many communities.
method Overlay method combining coarsening and parallel clustering.
result PASCO accelerates clustering with improved efficiency and quality.
For many large undirected models that arise in real-world applications, exact maximumlikelihood training is intractable, because it requires computing marginal distributions of the model. Conditional training is even more difficult, because the partition function depends not only on the parameters, but also on the obse…
PSimGNN partitions graphs into subgraphs for efficient graph similarity computation.
problem Efficiently compute graph similarity scores for large graphs.
method Graph partitioning followed by subgraph-level and node-level comparisons using a graph neural network.
result PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks.
Bonsai learns fast, deep trees for XMC with fast training and high accuracy.
problem Efficiently learning multi-label classification models with millions of labels.
method Develops Bonsai suite of algorithms that generalize label representation and learn shallow trees.
result Bonsai achieves best of fast training and high accuracy on XMC tasks.
A new method for creating simpler models from complex ones.
problem Creating accurate approximations of complex models at reduced costs.
method Sequential adaptive surrogate modeling based on locally spectral expansions.
result Stochastic spectral embedding (SSE) shows good approximation capabilities and scalability.
In this paper, we investigate the significance of choosing an appropriate tessellation strategy for a spatio-temporal taxi demand-supply modeling framework. Our study compares (i) the variable-sized polygon based Voronoi tessellation, and (ii) the fixed-sized grid based Geohash tessellation, using taxi demand-supply GP…
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.
Enhances POU-Nets with probabilistic noise model for efficient spatial data clustering.
problem Improving the efficiency and accuracy of deep learning models for spatial data.
method Integrates Gaussian noise model into POU-Nets to enable gradient-based optimization and hierarchical refinement.
result Achieves sharp spatial partitions and higher-order polynomial approximation without regularizers.
A new method estimates rare failure events in complex systems.
problem Estimating the probability of rare failure events in non-linear systems.
method Stochastic Spectral Embedding (SSE) combined with modifications for efficient rare event estimation.
result Rare failure probability decomposed into conditional probabilities for easier computation.
Secure Multiparty Computation protects data privacy in Symbolic Regression.
problem Data privacy in Symbolic Regression models.
method Secure Multiparty Computation for vertical partitioning.
result Comparable performance to centralized model while preserving privacy.
A new model for Gaussian process experts tackles scalability and uncertainty issues.
problem Scalability and excessive number of experts degrade predictive performance and increase uncertainty.
method Nested partitioning scheme infers the number of components, a generalised GP framework accommodates multiple response types, and a factorised exponential family structure handles multiple input types.
result Effectiveness demonstrated on synthetic data and an Alzheimer's challenge dataset.
Undirected graphical models encode in a graph G the dependency structure of a random vector Y. In many applications, it is of interest to model Y given another random vector X as input. We refer to the problem of estimating the graph G(x) of Y conditioned on X=x as ``graph-valued regression.'' In this pap…
Batch normalization improves deep networks by aligning their decision boundaries with data.
problem Improving the performance and generalization of deep networks.
method Theoretical analysis of batch normalization as a function approximation technique for continuous piecewise affine splines.
result Batch normalization adapts the geometry of a deep network's partition to match the data, improving learning and generalization.