We propose the Insertion-Deletion Transformer, a novel transformer-based neural architecture and training method for sequence generation. The model consists of two phases that are executed iteratively, 1) an insertion phase and 2) a deletion phase. The insertion phase parameterizes a distribution of insertions on the c…
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 “insertions and deletions”
ID-ExpO fine-tunes neural networks for more faithful explanations.
problem Improving the faithfulness of explanations for complex machine learning models.
method Differentiable insertion/deletion metric-aware regularizers for optimization.
result Fine-tuned predictors produce more faithful explanations.
New framework for consistent submodular maximization with insertions and deletions.
problem Maintaining near-optimal solutions in a dynamic setting with insertions and deletions.
method Developed a general framework for fully dynamic submodular maximization, instantiated for cardinality and rank-k matroid constraints.
result First constant-factor approximations with sublinear consistency for both cardinality and rank-k matroid constraints.
New formulas for feature importance tests in regression models.
problem Identifying important features in regression models.
method Established formulas for AUC criteria and proposed alternative metrics.
result Integrated Gradients (IG) performs nearly as well as Kernel SHAP (KS) but is faster.
A well-known problem in data science and machine learning is {\em linear regression}, which is recently extended to dynamic graphs. Existing exact algorithms for updating the solution of dynamic graph regression require at least a linear time (in terms of : the size of the graph). However, this time complexity might…
While neural sequence generation models achieve initial success for many NLP applications, the canonical decoding procedure with left-to-right generation order (i.e., autoregressive) in one-pass can not reflect the true nature of human revising a sentence to obtain a refined result. In this work, we propose XL-Editor, …
New algorithm for maximizing submodular functions in real-time data changes.
problem Maximizing submodular functions under dynamic constraints.
method Randomized algorithm with amortized update time.
result 4-approximate solution to submodular maximization problem.
RS-Del provides robustness for sequence classifiers against edit distance attacks.
problem Certifying robustness of discrete sequence classifiers against edit distance attacks.
method Randomized deletion (RS-Del) for discrete sequence classifiers, focusing on edit distance-bounded adversaries.
result Achieved a certified accuracy of 91% at an edit distance radius of 128 bytes on malware detection.
We consider the -means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space can be dynamically inserted to or deleted from the dataset. For this problem, we provide a one-pass coreset construction algorithm using space $\tilde{O}(k\cdot \mathrm{pol…
XGES improves GES by favoring early edge deletion, outperforming GES in finite data settings.
problem Learning directed acyclic graphs from finite data.
method Extremely Greedy Equivalent Search (XGES) improves GES by favoring early edge deletion.
result XGES consistently outperforms GES in recovering the correct graphs, and is 10 times faster.
With a sharp rise in fluency and users of "Hinglish" in linguistically diverse country, India, it has increasingly become important to analyze social content written in this language in platforms such as Twitter, Reddit, Facebook. This project focuses on using deep learning techniques to tackle a classification problem…
We use automatic speech recognition to assess spoken English learner pronunciation based on the authentic intelligibility of the learners' spoken responses determined from support vector machine (SVM) classifier or deep learning neural network model predictions of transcription correctness. Using numeric features produ…
Paper trains models to resist string transformations.
problem Vulnerability of NLP models to adversarial string transformations.
method Combines search and abstraction techniques for robust training.
result Trained models resist combinations of user-defined transformations.
Pair Hidden Markov Models (PHMMs) are probabilistic models used for pairwise sequence alignment, a quintessential problem in bioinformatics. PHMMs include three types of hidden states: match, insertion and deletion. Most previous studies have used one or two hidden states for each PHMM state type. However, few studies …
The study proves unique path lifting properties and their implications on quotient spaces and covering maps.
problem Understanding unique path lifting properties and their implications on quotient spaces and covering maps.
method The study uses group actions on -trees and path lifting properties to prove the main results.
result Every map of manifolds with the unique path lifting property is a covering map.
Deep Partition Aggregation defends against poisoning attacks with provable certificates.
problem Adversarial poisoning attacks corrupt classifier test-time behavior.
method Deep Partition Aggregation (DPA) is an ensemble method using hash partitions and base models trained on these partitions.
result DPA can certify >= 50% of test images against over 500 poison image insertions on MNIST, and nine insertions on CIFAR-10.
Many real datasets contain values missing not at random (MNAR). In this scenario, investigators often perform list-wise deletion, or delete samples with any missing values, before applying causal discovery algorithms. List-wise deletion is a sound and general strategy when paired with algorithms such as FCI and RFCI, b…
New approach protects privacy of deleted records in machine learning.
problem Privacy of deleted records in machine learning models.
method Sound deletion guarantee and noisy gradient descent algorithm.
result Privacy of existing records is necessary for deleted records' privacy.
Paper tackles adaptive deletion of data points from trained models.
problem Adaptive deletion of data points from trained models.
method Reduction from adaptive to non-adaptive deletion guarantees using differential privacy and max information.
result Strong provable deletion guarantees for adaptive deletion sequences.
We present the Insertion Transformer, an iterative, partially autoregressive model for sequence generation based on insertion operations. Unlike typical autoregressive models which rely on a fixed, often left-to-right ordering of the output, our approach accommodates arbitrary orderings by allowing for tokens to be ins…
This research tackles data deletion in linear regression with noisy SGD, finding perfect deleted points.
problem Finding points to delete from a dataset without significantly affecting the training result.
method Signal-to-noise ratio and an algorithm based on it.
result The perfect deleted point is crucial for maintaining model performance and privacy budget.
Efficient algorithms for deleting data from machine learning models without significantly affecting performance.
problem Deleting data from machine learning models while maintaining performance.
method Leveraging convex optimization and reservoir sampling, the paper introduces algorithms for handling long sequences of adversarial updates.
result First data deletion algorithms that promise steady-state error not growing with the length of the update sequence.
Most of real-world graphs are dynamic, i.e., they change over time by a sequence of update operations. While the regression problem has been studied for static graphs and temporal graphs, it is not investigated for general dynamic graphs. In this paper, we study regression over dynamic graphs. First, we present the not…
Paper proposes a fast method for approximate data deletion in generative models.
problem Efficient data deletion in unsupervised learning models is an open problem.
method Density-ratio-based framework for generative models, fast method for approximate data deletion, statistical test.
result Theoretical guarantees and empirical demonstrations of the proposed methods across various generative models.
New method for efficiently deleting data from ML models.
problem Efficiently removing data from trained ML models without retraining.
method Approximate deletion method for linear and logistic models.
result Significantly faster than existing methods, with linear time dependence on feature dimension.
Measuring the similarity of two files is an important task in malware analysis, with fuzzy hash functions being a popular approach. Traditional fuzzy hash functions are data agnostic: they do not learn from a particular dataset how to determine similarity; their behavior is fixed across all datasets. In this paper, we …
Study on deleting user data in linear regression models to maintain limited memory.
problem Deleting user data in a limited time frame for statistical models.
method Proposed FIFD-OLS and FIFD-Adaptive Ridge algorithms for low-dimensional and online settings.
result Demonstrated effectiveness of FIFD-Adaptive Ridge in maintaining statistical efficiency.
The paper develops algorithms to find a robust summary of data under deletion, achieving good approximation guarantees.
problem Finding a summary of data that remains valuable even after some elements are deleted.
method Constant-factor approximation algorithms for deletion robust submodular maximization under matroid constraints.
result The algorithms provide good approximation guarantees for both centralized and streaming settings.
New examples show deletion type admissible pairs can be rigid under rational saturation.
problem Rigidity of admissible pairs of rational homogeneous spaces of Picard number one.
method Application of Mok's general criterion for non-subdiagram type admissible pairs.
result Examples of deletion type admissible pairs are rigid under rational saturation.
The paper compares two methods for handling missing data in causal discovery.
problem Handling missing data in causal discovery algorithms.
method Test-wise deletion and multiple imputation.
result Multiple imputation is more challenging for causal discovery than for estimation.
In this work we explore the use of metric index structures, which accelerate nearest neighbor queries, in the scenario where we need to interleave insertions and queries during deployment. This use-case is inspired by a real-life need in malware analysis triage, and is surprisingly understudied. Existing literature ten…
We observe the effects of the three different events that cause spread changes in the order book, namely trades, deletions and placement of limit orders. By looking at the frequencies of the relative amounts of price changing events, we discover that deletions of orders open the bid-ask spread of a stock more often tha…
Deleting an edge of a 3-cycle in an intrinsically knotted graph gives an intrinsically linked graphmath.CO
We show that deleting an edge of a 3-cycle in an intrinsically knotted graph gives an intrinsically linked graph.
Intense recent discussions have focused on how to provide individuals with control over when their data can and cannot be used --- the EU's Right To Be Forgotten regulation is an example of this effort. In this paper we initiate a framework studying what to do when it is no longer permissible to deploy models derivativ…
Transposable Elements (TEs) or jumping genes are the DNA sequences that have an intrinsic capability to move within a host genome from one genomic location to another. Studies show that the presence of a TE within or adjacent to a functional gene may alter its expression. TEs can also cause an increase in the rate of m…
New attacks improve privacy audits by analyzing model updates.
problem Improving privacy audits of AI models through sequence analysis.
method Developed SeMI attacks to identify target insertions in model sequences.
result SeMI attacks achieve higher power and tighter privacy audits.
DaRE forests enable efficient data deletion from random forests.
problem Efficiently removing data from machine learning models.
method Random Forests with data deletion enabled (DaRE).
result Data deletion from DaRE models is orders of magnitude faster than retraining.
Tree Edit Distance Learning via Adaptive Symbol Embeddings: Supplementary Materials and Resultscs.LG
Metric learning has the aim to improve classification accuracy by learning a distance measure which brings data points from the same class closer together and pushes data points from different classes further apart. Recent research has demonstrated that metric learning approaches can also be applied to trees, such as m…
Metric learning has the aim to improve classification accuracy by learning a distance measure which brings data points from the same class closer together and pushes data points from different classes further apart. Recent research has demonstrated that metric learning approaches can also be applied to trees, such as m…
Ultra-fast search algorithm for trillion-scale corpora with semantic flexibility.
problem Efficiently searching over large natural language corpora with semantic variations.
method String matching based on suffix arrays, vector representation of words, dynamic corpus-aware pruning, fast exact lookup.
result Substantially lower search latency compared to existing methods on FineWeb-Edu corpus.
The paper tackles robust submodular maximization under matroid constraints, providing approximation algorithms for summary extraction.
problem Maximizing submodular functions while ensuring high value even after deletions.
method Constant-factor approximation algorithms for centralized and streaming settings, considering both non-monotone and monotone objectives.
result Approximation algorithms with space complexity depending on matroid rank and deleted elements, achieving improved factors in monotone cases.
Introduces TSI, a variance-based measure for persistence barcodes.
problem Capturing structural variability in persistence barcodes.
method Variance-based scalar measure, TSI, and complementary TSigI.
result TSI captures structural variability complementary to entropy.
Method detects if text is generated by a language model with watermarks.
problem Detecting if text is generated by a language model with watermarks.
method Randomization tests and change point detection techniques.
result Method ensures Type I and Type II error control and accurately identifies watermarked sub-strings.
We use a variation on the commutator collection process to characterize those pure braids which become trivial when any one strand is deleted, or, more generally, those pure braids which become trivial when all the strands in any one of a list of sets of strands is deleted.
An -coreset for a given set of points, is usually a small weighted set, such that querying the coreset \emph{provably} yields a -factor approximation to the original (full) dataset, for a given family of queries. Using existing techniques, coresets can be maintained for streaming, …
Graph pruning improves neural network performance by addressing squashing and smoothing issues.
problem Over-squashing and over-smoothing in Graph Neural Networks.
method Proposes edge deletions to simultaneously address over-squashing and over-smoothing, optimizing spectral gap.
result Edge deletions improve generalization and distinguishability of nodes of different classes.
Gordon and Litherland showed that all compact, unoriented, possibly non-orientable surfaces in bounded by a link are realted by attaching/deleting tubes and half twisted bands. In this note we give an elementary proof for this result.
The configuration space of ordered pairs of distinct points in a manifold , also known as the deleted square of , is not a homotopy invariant of : Longoni and Salvatore produced examples of homotopy equivalent lens spaces and of dimension three for which and are not homoto…