OpenRaiser/Intern-Atlas huggingface dataset:
An Information-Theoretic Framework for Supervised Learning
Venue: arXiv cs.LG 2023
Year: 2023

Each year, deep learning demonstrates new and improved empirical results with deeper and wider neural networks. Meanwhile, with existing theoretical frameworks, it is difficult to analyze networks deeper than two layers without resorting to counting parameters or encountering sample complexity bounds that are exponential in depth. Perhaps it may be fruitful to try to analyze modern machine learning under a different lens. In this paper, we propose a novel information-theoretic framework with its own notions of regret and sample complexity for analyzing the data requirements of machine learning. With our framework, we first work through some classical examples such as scalar estimation and linear regression to build intuition and introduce general techniques. Then, we use the framework to study the sample complexity of learning from data generated by deep neural networks with ReLU activation units. For a particular prior distribution on weights, we establish sample complexity bounds that are simultaneously width independent and linear in depth. This prior distribution gives rise to high-dimensional latent representations that, with high probability, admit reasonably accurate low-dimensional approximations. We conclude by corroborating our theoretical results with experimental analysis of random single-hidden-layer neural networks.
Inverse problem for parameters identification in a modified SIRD epidemic model using ensemble neural networks
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we propose a parameter identification methodology of the SIRD model, an extension of the classical SIR model, that considers the deceased as a separate category. In addition, our model includes one parameter which is the ratio between the real total number of infected and the number of infected that were documented in the official statistics. Due to many factors, like governmental decisions, several variants circulating, opening and closing of schools, the typical assumption that the parameters of the model stay constant for long periods of time is not realistic. Thus our objective is to create a method which works for short periods of time. In this scope, we approach the estimation relying on the previous 7 days of data and then use the identified parameters to make predictions. To perform the estimation of the parameters we propose the average of an ensemble of neural networks. Each neural network is constructed based on a database built by solving the SIRD for 7 days, with random parameters. In this way, the networks learn the parameters from the solution of the SIRD model. Lastly we use the ensemble to get estimates of the parameters from the real data of Covid19 in Romania and then we illustrate the predictions for different periods of time, from 10 up to 45 days, for the number of deaths. The main goal was to apply this approach on the analysis of COVID-19 evolution in Romania, but this was also exemplified on other countries like Hungary, Czech Republic and Poland with similar results. The results are backed by a theorem which guarantees that we can recover the parameters of the model from the reported data. We believe this methodology can be used as a general tool for dealing with short term predictions of infectious diseases or in other compartmental models.
Discovering Opportunities in New York City's Discovery Program: Disadvantaged Students in Highly Competitive Markets
Venue: arXiv cs.GT 2023
Year: 2023

Discovery program (DISC) is a policy used by the New York City Department of Education (NYC DOE) to increase the number of admissions of students from low socio-economic background to specialized high schools. This policy has been instrumental in increasing the number of disadvantaged students attending these schools. However, assuming that students care more about the school they are assigned to rather than the type of seat they occupy (\emph{school-over-seat hypothesis}), our empirical analysis using data from 12 recent academic years shows that DISC creates about 950 in-group blocking pairs each year amongst disadvantaged students, impacting about 650 disadvantaged students every year. Moreover, we find that this program does not respect improvements, thus unintentionally creating an incentive to under-perform. These experimental results are confirmed by our theoretical analysis. In order to alleviate the concerns caused by DISC, we explore two alternative policies: the minority reserve (MR) and the joint-seat allocation (JSA) mechanisms. As our main theoretical contribution, we introduce a feature of markets, that we term high competitiveness, and we show that under this condition, JSA dominates MR for all disadvantaged students. We give sufficient conditions under which high competitiveness is verified. Data from NYC DOE satisfies the high competitiveness condition, and for this dataset our empirical results corroborate our theoretical predictions, showing the superiority of JSA. Given that JSA can be implemented by a simple modification of the classical deferred acceptance algorithm with responsive preference lists, we believe that, when the school-over-seat hypothesis holds, the discovery program can be changed for the better by implementing the JSA mechanism, leading in particular to aligned incentives for the top-performing disadvantaged students.
Adaptive Discriminative Regularization for Visual Classification
Venue: arXiv cs.LG 2023
Year: 2023

How to improve discriminative feature learning is central in classification. Existing works address this problem by explicitly increasing inter-class separability and intra-class similarity, whether by constructing positive and negative pairs for contrastive learning or posing tighter class separating margins. These methods do not exploit the similarity between different classes as they adhere to i.i.d. assumption in data. In this paper, we embrace the real-world data distribution setting that some classes share semantic overlaps due to their similar appearances or concepts. Regarding this hypothesis, we propose a novel regularization to improve discriminative learning. We first calibrate the estimated highest likelihood of one sample based on its semantically neighboring classes, then encourage the overall likelihood predictions to be deterministic by imposing an adaptive exponential penalty. As the gradient of the proposed method is roughly proportional to the uncertainty of the predicted likelihoods, we name it adaptive discriminative regularization (ADR), trained along with a standard cross entropy loss in classification. Extensive experiments demonstrate that it can yield consistent and non-trivial performance improvements in a variety of visual classification tasks (over 10 benchmarks). Furthermore, we find it is robust to long-tailed and noisy label data distribution. Its flexible design enables its compatibility with mainstream classification architectures and losses.
FastFold: Reducing AlphaFold Training Time from 11 Days to 67 Hours
Venue: arXiv cs.LG 2023
Year: 2023

Protein structure prediction helps to understand gene translation and protein function, which is of growing interest and importance in structural biology. The AlphaFold model, which used transformer architecture to achieve atomic-level accuracy in protein structure prediction, was a significant breakthrough. However, training and inference of the AlphaFold model are challenging due to its high computation and memory cost. In this work, we present FastFold, an efficient implementation of AlphaFold for both training and inference. We propose Dynamic Axial Parallelism and Duality Async Operations to improve the scaling efficiency of model parallelism. Besides, AutoChunk is proposed to reduce memory cost by over 80% during inference by automatically determining the chunk strategy. Experimental results show that FastFold reduces overall training time from 11 days to 67 hours and achieves 7.5X - 9.5X speedup for long-sequence inference. Furthermore, we scale FastFold to 512 GPUs and achieve an aggregate throughput of 6.02 PetaFLOP/s with 90.1% parallel efficiency.
Graph Rewriting and Relabeling with PBPO+: A Unifying Theory for Quasitoposes
Venue: arXiv cs.LO 2023
Year: 2023

We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called PBPO+, allows more control over the embedding of the pattern in the host graph, which is important for a large class of rewrite systems. We argue that PBPO+ can be considered a unifying theory in the general setting of quasitoposes, by demonstrating that PBPO+ can define a strict superset of the rewrite relations definable by PBPO, AGREE and DPO. Additionally, we show that PBPO+ is well suited for rewriting labeled graphs and some classes of attributed graphs, by introducing a lattice structure on the label set and requiring graph morphisms to be order-preserving.
STV+AGR: Towards Practical Verification of Strategic Ability Using Assume-Guarantee Reasoning
Venue: arXiv cs.MA 2023
Year: 2023

We present a substantially expanded version of our tool STV for strategy synthesis and verification of strategic abilities. The new version provides a web interface and support for assume-guarantee verification of multi-agent systems.
ReStore: In-Memory REplicated STORagE for Rapid Recovery in Fault-Tolerant Algorithms
Venue: arXiv cs.DC 2023
Year: 2023

Fault-tolerant distributed applications require mechanisms to recover data lost via a process failure. On modern cluster systems it is typically impractical to request replacement resources after such a failure. Therefore, applications have to continue working with the remaining resources. This requires redistributing the workload and that the non-failed processes reload data. We present an algorithmic framework and its C++ library implementation ReStore for MPI programs that enables recovery of data after process failures. By storing all required data in memory via an appropriate data distribution and replication, recovery is substantially faster than with standard checkpointing schemes that rely on a parallel file system. As the application developer can specify which data to load, we also support shrinking recovery instead of recovery using spare compute nodes. We evaluate ReStore in both controlled, isolated environments and real applications. Our experiments show loading times of lost input data in the range of milliseconds on up to 24 576 processors and a substantial speedup of the recovery time for the fault-tolerant version of a widely used bioinformatics application.
An Analysis of Ensemble Sampling
Venue: arXiv cs.LG 2023
Year: 2023

Ensemble sampling serves as a practical approximation to Thompson sampling when maintaining an exact posterior distribution over model parameters is computationally intractable. In this paper, we establish a regret bound that ensures desirable behavior when ensemble sampling is applied to the linear bandit problem. This represents the first rigorous regret analysis of ensemble sampling and is made possible by leveraging information-theoretic concepts and novel analytic techniques that may prove useful beyond the scope of this paper.
Rethinking Reconstruction Autoencoder-Based Out-of-Distribution Detection
Venue: arXiv cs.CV 2023
Year: 2023

In some scenarios, classifier requires detecting out-of-distribution samples far from its training data. With desirable characteristics, reconstruction autoencoder-based methods deal with this problem by using input reconstruction error as a metric of novelty vs. normality. We formulate the essence of such approach as a quadruplet domain translation with an intrinsic bias to only query for a proxy of conditional data uncertainty. Accordingly, an improvement direction is formalized as maximumly compressing the autoencoder's latent space while ensuring its reconstructive power for acting as a described domain translator. From it, strategies are introduced including semantic reconstruction, data certainty decomposition and normalized L2 distance to substantially improve original methods, which together establish state-of-the-art performance on various benchmarks, e.g., the FPR@95%TPR of CIFAR-100 vs. TinyImagenet-crop on Wide-ResNet is 0.2%. Importantly, our method works without any additional data, hard-to-implement structure, time-consuming pipeline, and even harming the classification accuracy of known classes.
Standardization of Extended Reality (XR) over 5G and 5G-Advanced 3GPP New Radio
Venue: arXiv cs.NI 2023
Year: 2023

Extended Reality (XR) is one of the major innovations to be introduced in 5G/5G-Advanced communication systems. A combination of augmented reality, virtual reality, and mixed reality, supplemented by cloud gaming, revisits the way how humans interact with computers, networks, and each other. However, efficient support of XR services imposes new challenges for existing and future wireless networks. This article presents a tutorial on integrating support for the XR into the 3GPP New Radio (NR), summarizing a range of activities handled within various 3GPP Service and Systems Aspects (SA) and Radio Access Networks (RAN) groups. The article also delivers a case study evaluating the performance of different XR services in state-of-the-art NR Release 17. The paper concludes with a vision of further enhancements to better support XR in future NR releases and outlines open problems in this area.
Rethinking Efficient Lane Detection via Curve Modeling
Venue: arXiv cs.CV 2023
Year: 2023

This paper presents a novel parametric curve-based method for lane detection in RGB images. Unlike state-of-the-art segmentation-based and point detection-based methods that typically require heuristics to either decode predictions or formulate a large sum of anchors, the curve-based methods can learn holistic lane representations naturally. To handle the optimization difficulties of existing polynomial curve methods, we propose to exploit the parametric Bézier curve due to its ease of computation, stability, and high freedom degrees of transformations. In addition, we propose the deformable convolution-based feature flip fusion, for exploiting the symmetry properties of lanes in driving scenes. The proposed method achieves a new state-of-the-art performance on the popular LLAMAS benchmark. It also achieves favorable accuracy on the TuSimple and CULane datasets, while retaining both low latency (> 150 FPS) and small model size (< 10M). Our method can serve as a new baseline, to shed the light on the parametric curves modeling for lane detection. Codes of our model and PytorchAutoDrive: a unified framework for self-driving perception, are available at: https://github.com/voldemortX/pytorch-auto-drive .
Learning from Label Proportions by Learning with Label Noise
Venue: arXiv cs.LG 2023
Year: 2023

Learning from label proportions (LLP) is a weakly supervised classification problem where data points are grouped into bags, and the label proportions within each bag are observed instead of the instance-level labels. The task is to learn a classifier to predict the individual labels of future individual instances. Prior work on LLP for multi-class data has yet to develop a theoretically grounded algorithm. In this work, we provide a theoretically grounded approach to LLP based on a reduction to learning with label noise, using the forward correction (FC) loss of \citet{Patrini2017MakingDN}. We establish an excess risk bound and generalization error analysis for our approach, while also extending the theory of the FC loss which may be of independent interest. Our approach demonstrates improved empirical performance in deep learning scenarios across multiple datasets and architectures, compared to the leading existing methods.
Computationally Efficient Worst-Case Analysis of Flow-Controlled Networks with Network Calculus
Venue: arXiv cs.NI 2023
Year: 2023

Networks with hop-by-hop flow control occur in several contexts, from data centers to systems architectures (e.g., wormhole-routing networks on chip). A worst-case end-to-end delay in such networks can be computed using Network Calculus (NC), an algebraic theory where traffic and service guarantees are represented as curves in a Cartesian plane. NC uses transformation operations, e.g., the min-plus convolution, to model how the traffic profile changes with the traversal of network nodes. NC allows one to model flow-controlled systems, hence one can compute the end-to-end service curve describing the minimum service guaranteed to a flow traversing a tandem of flow-controlled nodes. However, while the algebraic expression of such an end-to-end service curve is quite compact, its computation is often intractable from an algorithmic standpoint: data structures tend to grow quickly to unfeasibly large sizes, making operations intractable, even with as few as three hops. In this paper, we propose computational and algebraic techniques to mitigate the above problem. We show that existing techniques (such as reduction to compact domains) cannot be used in this case, and propose an arsenal of solutions, which include methods to mitigate the data representation space explosion as well as computationally efficient algorithms for the min-plus convolution operation. We show that our solutions allow a significant speedup, enable analysis of previously unfeasible case studies, and -- since they do not rely on any approximation -- still provide exact results.
Question-Answer Sentence Graph for Joint Modeling Answer Selection
Venue: arXiv cs.CL 2023
Year: 2023

This research studies graph-based approaches for Answer Sentence Selection (AS2), an essential component for retrieval-based Question Answering (QA) systems. During offline learning, our model constructs a small-scale relevant training graph per question in an unsupervised manner, and integrates with Graph Neural Networks. Graph nodes are question sentence to answer sentence pairs. We train and integrate state-of-the-art (SOTA) models for computing scores between question-question, question-answer, and answer-answer pairs, and use thresholding on relevance scores for creating graph edges. Online inference is then performed to solve the AS2 task on unseen queries. Experiments on two well-known academic benchmarks and a real-world dataset show that our approach consistently outperforms SOTA QA baseline models.
Object-centric and memory-guided normality reconstruction for video anomaly detection
Venue: arXiv cs.CV 2023
Year: 2023

This paper addresses video anomaly detection problem for videosurveillance. Due to the inherent rarity and heterogeneity of abnormal events, the problem is viewed as a normality modeling strategy, in which our model learns object-centric normal patterns without seeing anomalous samples during training. The main contributions consist in coupling pretrained object-level action features prototypes with a cosine distance-based anomaly estimation function, therefore extending previous methods by introducing additional constraints to the mainstream reconstruction-based strategy. Our framework leverages both appearance and motion information to learn object-level behavior and captures prototypical patterns within a memory module. Experiments on several well-known datasets demonstrate the effectiveness of our method as it outperforms current state-of-the-art on most relevant spatio-temporal evaluation metrics.
A Trainable Approach to Zero-delay Smoothing Spline Interpolation
Venue: arXiv cs.LG 2023
Year: 2023

The task of reconstructing smooth signals from streamed data in the form of signal samples arises in various applications. This work addresses such a task subject to a zero-delay response; that is, the smooth signal must be reconstructed sequentially as soon as a data sample is available and without having access to subsequent data. State-of-the-art approaches solve this problem by interpolating consecutive data samples using splines. Here, each interpolation step yields a piece that ensures a smooth signal reconstruction while minimizing a cost metric, typically a weighted sum between the squared residual and a derivative-based measure of smoothness. As a result, a zero-delay interpolation is achieved in exchange for an almost certainly higher cumulative cost as compared to interpolating all data samples together. This paper presents a novel approach to further reduce this cumulative cost on average. First, we formulate a zero-delay smoothing spline interpolation problem from a sequential decision-making perspective, allowing us to model the future impact of each interpolated piece on the average cumulative cost. Then, an interpolation method is proposed to exploit the temporal dependencies between the streamed data samples. Our method is assisted by a recurrent neural network and accordingly trained to reduce the accumulated cost on average over a set of example data samples collected from the same signal source generating the signal to be reconstructed. Finally, we present extensive experimental results for synthetic and real data showing how our approach outperforms the abovementioned state-of-the-art.
Universal Prototype Transport for Zero-Shot Action Recognition and Localization
Venue: arXiv cs.CV 2023
Year: 2023

This work addresses the problem of recognizing action categories in videos when no training examples are available. The current state-of-the-art enables such a zero-shot recognition by learning universal mappings from videos to a semantic space, either trained on large-scale seen actions or on objects. While effective, we find that universal action and object mappings are biased to specific regions in the semantic space. These biases lead to a fundamental problem: many unseen action categories are simply never inferred during testing. For example on UCF-101, a quarter of the unseen actions are out of reach with a state-of-the-art universal action model. To that end, this paper introduces universal prototype transport for zero-shot action recognition. The main idea is to re-position the semantic prototypes of unseen actions by matching them to the distribution of all test videos. For universal action models, we propose to match distributions through a hyperspherical optimal transport from unseen action prototypes to the set of all projected test videos. The resulting transport couplings in turn determine the target prototype for each unseen action. Rather than directly using the target prototype as final result, we re-position unseen action prototypes along the geodesic spanned by the original and target prototypes as a form of semantic regularization. For universal object models, we outline a variant that defines target prototypes based on an optimal transport between unseen action prototypes and object prototypes. Empirically, we show that universal prototype transport diminishes the biased selection of unseen action prototypes and boosts both universal action and object models for zero-shot classification and spatio-temporal localization.
DeltaCNN: End-to-End CNN Inference of Sparse Frame Differences in Videos
Venue: arXiv cs.CV 2023
Year: 2023

Convolutional neural network inference on video data requires powerful hardware for real-time processing. Given the inherent coherence across consecutive frames, large parts of a video typically change little. By skipping identical image regions and truncating insignificant pixel updates, computational redundancy can in theory be reduced significantly. However, these theoretical savings have been difficult to translate into practice, as sparse updates hamper computational consistency and memory access coherence; which are key for efficiency on real hardware. With DeltaCNN, we present a sparse convolutional neural network framework that enables sparse frame-by-frame updates to accelerate video inference in practice. We provide sparse implementations for all typical CNN layers and propagate sparse feature updates end-to-end - without accumulating errors over time. DeltaCNN is applicable to all convolutional neural networks without retraining. To the best of our knowledge, we are the first to significantly outperform the dense reference, cuDNN, in practical settings, achieving speedups of up to 7x with only marginal differences in accuracy.