OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Certification for Autonomous Systems
Venue: arXiv cs.RO 2023
Year: 2023

Autonomous systems are often deployed in complex sociotechnical environments, such as public roads, where they must behave safely and securely. Unlike many traditionally engineered systems, autonomous systems are expected to behave predictably in varying "open world" environmental contexts that cannot be fully specified formally. As a result, assurance about autonomous systems requires us to develop new certification methods and mathematical tools that can bound the uncertainty engendered by these diverse deployment scenarios, rather than relying on static tools.
AI based Log Analyser: A Practical Approach
Venue: arXiv cs.LG 2023
Year: 2023

The analysis of logs is a vital activity undertaken for fault or cyber incident detection, investigation and technical forensics analysis for system and cyber resilience. The potential application of AI algorithms for Log analysis could augment such complex and laborious tasks. However, such solution has its constraints the heterogeneity of log sources and limited to no labels for training a classifier. When such labels become available, the need for the classifier to be updated. This practice-based research seeks to address these challenges with the use of Transformer construct to train a new model with only normal log entries. Log augmentation through multiple forms of perturbation is applied as a form of self-supervised training for feature learning. The model is further finetuned using a form of reinforcement learning with a limited set of label samples to mimic real-world situation with the availability of labels. The experimental results of our model construct show promise with comparative evaluation measurements paving the way for future practical applications.
Teachable Reinforcement Learning via Advice Distillation
Venue: arXiv cs.LG 2023
Year: 2023

Training automated agents to complete complex tasks in interactive environments is challenging: reinforcement learning requires careful hand-engineering of reward functions, imitation learning requires specialized infrastructure and access to a human expert, and learning from intermediate forms of supervision (like binary preferences) is time-consuming and extracts little information from each human intervention. Can we overcome these challenges by building agents that learn from rich, interactive feedback instead? We propose a new supervision paradigm for interactive learning based on "teachable" decision-making systems that learn from structured advice provided by an external teacher. We begin by formalizing a class of human-in-the-loop decision making problems in which multiple forms of teacher-provided advice are available to a learner. We then describe a simple learning algorithm for these problems that first learns to interpret advice, then learns from advice to complete tasks even in the absence of human supervision. In puzzle-solving, navigation, and locomotion domains, we show that agents that learn from advice can acquire new skills with significantly less human supervision than standard reinforcement learning algorithms and often less than imitation learning.
Language modeling via stochastic processes
Venue: arXiv cs.CL 2023
Year: 2023

Modern language models can generate high-quality short texts. However, they often meander or are incoherent when generating longer texts. These issues arise from the next-token-only language modeling objective. Recent work in self-supervised learning suggests that models can learn good latent representations via contrastive learning, which can be effective for discriminative tasks. Our work analyzes the application of contrastive representations for generative tasks, like long text generation. We propose one approach for leveraging constrastive representations, which we call Time Control (TC). TC first learns a contrastive representation of the target text domain, then generates text by decoding from these representations. Compared to domain-specific methods and fine-tuning GPT2 across a variety of text domains, TC performs competitively to methods specific for learning sentence representations on discourse coherence. On long text generation settings, TC preserves the text structure both in terms of ordering (up to $+15\%$ better) and text length consistency (up to $+90\%$ better).
Quantum Cryptanalysis of Farfalle and (Generalised) Key-Alternating Feistel Networks
Venue: arXiv cs.IT 2023
Year: 2023

Farfalle is a permutation-based construction for building a pseudorandom function which has been proposed by G. Bertoni et al. in 2017. In this work, we show that by observing suitable inputs to Farfalle, one can derive various constructions of a periodic function with a period that involves a secret key. As this admits the application of Simon's algorithm in the so-called Q2 attack model, we further show that in the case when internal rolling function is linear, then the secret key can be extracted under feasible assumptions. Furthermore, using the provided constructions of periodic functions for Farfalle, we show that one can mount forgery attacks on the session-supporting mode for authenticated encryption (Farfalle-SAE) and the synthetic initial value AE mode (Farfalle-SIV). In addition, as the wide block cipher mode Farfalle-WBC is a 4-round Feistel scheme, a quantum distinguisher is constructed in the case when input branches are containing at last two blocks, where length of one block corresponds to the size of a permutation employed in Farfalle (a similar attack can be mounted to Farfalle-WBC-AE). And finally, we consider the problem of extracting a secret round key out of different periods obtained from a (Generalized) Feistel scheme (GFN), which has not been addressed in any of the previous works which consider the application of Simon's (or Simon-Grover) algorithm to round reduced versions of GFNs. By applying two different interpolation formulas, we show that one can extract the round key by utilizing amount of different periods which is closely related to the polynomial/algebraic degree of underlying inner function.
GriTS: Grid table similarity metric for table structure recognition
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we propose a new class of metric for table structure recognition (TSR) evaluation, called grid table similarity (GriTS). Unlike prior metrics, GriTS evaluates the correctness of a predicted table directly in its natural form as a matrix. To create a similarity measure between matrices, we generalize the two-dimensional largest common substructure (2D-LCS) problem, which is NP-hard, to the 2D most similar substructures (2D-MSS) problem and propose a polynomial-time heuristic for solving it. This algorithm produces both an upper and a lower bound on the true similarity between matrices. We show using evaluation on a large real-world dataset that in practice there is almost no difference between these bounds. We compare GriTS to other metrics and empirically validate that matrix similarity exhibits more desirable behavior than alternatives for TSR performance evaluation. Finally, GriTS unifies all three subtasks of cell topology recognition, cell location recognition, and cell content recognition within the same framework, which simplifies the evaluation and enables more meaningful comparisons across different types of TSR approaches. Code will be released at https://github.com/microsoft/table-transformer.
StructToken : Rethinking Semantic Segmentation with Structural Prior
Venue: arXiv cs.CV 2023
Year: 2023

In previous deep-learning-based methods, semantic segmentation has been regarded as a static or dynamic per-pixel classification task, \textit{i.e.,} classify each pixel representation to a specific category. However, these methods only focus on learning better pixel representations or classification kernels while ignoring the structural information of objects, which is critical to human decision-making mechanism. In this paper, we present a new paradigm for semantic segmentation, named structure-aware extraction. Specifically, it generates the segmentation results via the interactions between a set of learned structure tokens and the image feature, which aims to progressively extract the structural information of each category from the feature. Extensive experiments show that our StructToken outperforms the state-of-the-art on three widely-used benchmarks, including ADE20K, Cityscapes, and COCO-Stuff-10K.
Dealing with Sparse Rewards Using Graph Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Deep reinforcement learning in partially observable environments is a difficult task in itself, and can be further complicated by a sparse reward signal. Most tasks involving navigation in three-dimensional environments provide the agent with extremely limited information. Typically, the agent receives a visual observation input from the environment and is rewarded once at the end of the episode. A good reward function could substantially improve the convergence of reinforcement learning algorithms for such tasks. The classic approach to increase the density of the reward signal is to augment it with supplementary rewards. This technique is called the reward shaping. In this study, we propose two modifications of one of the recent reward shaping methods based on graph convolutional networks: the first involving advanced aggregation functions, and the second utilizing the attention mechanism. We empirically validate the effectiveness of our solutions for the task of navigation in a 3D environment with sparse rewards. For the solution featuring attention mechanism, we are also able to show that the learned attention is concentrated on edges corresponding to important transitions in 3D environment.
Joint Distribution of Distance and Angles in Finite Wireless Networks
Venue: arXiv cs.IT 2023
Year: 2023

Directional beamforming will play a paramount role in 5G and beyond networks in order to combat the higher path losses incurred at millimeter wave bands. Appropriate modeling and analysis of the angles and distances between transmitters and receivers in these networks are thus essential to understand performance and limiting factors. Most existing literature considers either infinite and uniform networks, where nodes are drawn according to a Poisson point process, or finite networks with the reference receiver placed at the origin of a disk. Under either of these assumptions, the distance and azimuth angle between transmitter and receiver are independent, and the angle follows a uniform distribution between $0$ and $2π$. Here, we consider a more realistic case of finite networks where the reference node is placed at any arbitrary location. We obtain the joint distribution between the distance and azimuth angle and demonstrate that these random variables do exhibit certain correlation, which depends on the shape of the region and the location of the reference node. To conduct the analysis, we present a general mathematical framework which is specialized to exemplify the case of a rectangular region. We then also derive the statistics for the 3D case where, considering antenna heights, the joint distribution of distance, azimuth and zenith angles is obtained. Finally, we describe some immediate applications of the present work, including the analysis of directional beamforming, the design of analog codebooks and wireless routing algorithms.
Flexible and Optimal Dependency Management via Max-SMT
Venue: arXiv cs.SE 2023
Year: 2023

Package managers such as NPM have become essential for software development. The NPM repository hosts over 2 million packages and serves over 43 billion downloads every week. Unfortunately, the NPM dependency solver has several shortcomings. 1) NPM is greedy and often fails to install the newest versions of dependencies; 2) NPM's algorithm leads to duplicated dependencies and bloated code, which is particularly bad for web applications that need to minimize code size; 3) NPM's vulnerability fixing algorithm is also greedy, and can even introduce new vulnerabilities; and 4) NPM's ability to duplicate dependencies can break stateful frameworks and requires a lot of care to workaround. Although existing tools try to address these problems they are either brittle, rely on post hoc changes to the dependency tree, do not guarantee optimality, or are not composable. We present PacSolve, a unifying framework and implementation for dependency solving which allows for customizable constraints and optimization goals. We use PacSolve to build MaxNPM, a complete, drop-in replacement for NPM, which empowers developers to combine multiple objectives when installing dependencies. We evaluate MaxNPM with a large sample of packages from the NPM ecosystem and show that it can: 1) reduce more vulnerabilities in dependencies than NPM's auditing tool in 33% of cases; 2) chooses newer dependencies than NPM in 14% of cases; and 3) chooses fewer dependencies than NPM in 21% of cases. All our code and data is open and available.
AutoML for Deep Recommender Systems: A Survey
Venue: arXiv cs.IR 2023
Year: 2023

Recommender systems play a significant role in information filtering and have been utilized in different scenarios, such as e-commerce and social media. With the prosperity of deep learning, deep recommender systems show superior performance by capturing non-linear information and item-user relationships. However, the design of deep recommender systems heavily relies on human experiences and expert knowledge. To tackle this problem, Automated Machine Learning (AutoML) is introduced to automatically search for the proper candidates for different parts of deep recommender systems. This survey performs a comprehensive review of the literature in this field. Firstly, we propose an abstract concept for AutoML for deep recommender systems (AutoRecSys) that describes its building blocks and distinguishes it from conventional AutoML techniques and recommender systems. Secondly, we present a taxonomy as a classification framework containing feature selection search, embedding dimension search, feature interaction search, model architecture search, and other components search. Furthermore, we put a particular emphasis on the search space and search strategy, as they are the common thread to connect all methods within each category and enable practitioners to analyze and compare various approaches. Finally, we propose four future promising research directions that will lead this line of research.
BARGAIN-MATCH: A Game Theoretical Approach for Resource Allocation and Task Offloading in Vehicular Edge Computing Networks
Venue: arXiv cs.GT 2023
Year: 2023

Vehicular edge computing (VEC) is emerging as a promising architecture of vehicular networks (VNs) by deploying the cloud computing resources at the edge of the VNs. This work aims to optimize resource allocation and task offloading in VEC networks. Specifically, we formulate a game theoretical resource allocation and task offloading problem (GTRATOP) that aims to maximize the system performance by jointly considering the incentive for cooperation, competition among vehicles, heterogeneity between VEC servers and vehicles, and inherent dynamic of VNs. Since the formulated GTRATOP is NP-hard, we propose an adaptive approach for resource allocation and task offloading in VEC networks by incorporating bargaining game and matching game, which is called BARGAIN-MATCH. First, for resource allocation, a bargaining game-based incentive is proposed to stimulate the vehicles and VEC servers to negotiate the optimal resource allocation and pricing decisions. Second, for task offloading, a many-to-one matching scheme is proposed to decide the optimal offloading strategies. Third, the dynamic and time-varying features are considered to adapt the strategies of BARGAIN-MATCH to the real-time VEC networks. Moreover, the BARGAIN-MATCH is proved to be stable and weak Pareto optimal. Simulation results demonstrate that the proposed BARGAIN-MATCH achieves superior system performance and efficiency compared to other methods, especially when the system workload is heavy.
Recent Few-Shot Object Detection Algorithms: A Survey with Performance Comparison
Venue: arXiv cs.CV 2023
Year: 2023

The generic object detection (GOD) task has been successfully tackled by recent deep neural networks, trained by an avalanche of annotated training samples from some common classes. However, it is still non-trivial to generalize these object detectors to the novel long-tailed object classes, which have only few labeled training samples. To this end, the Few-Shot Object Detection (FSOD) has been topical recently, as it mimics the humans' ability of learning to learn, and intelligently transfers the learned generic object knowledge from the common heavy-tailed, to the novel long-tailed object classes. Especially, the research in this emerging field has been flourishing in recent years with various benchmarks, backbones, and methodologies proposed. To review these FSOD works, there are several insightful FSOD survey articles [58, 59, 74, 78] that systematically study and compare them as the groups of fine-tuning/transfer learning, and meta-learning methods. In contrast, we review the existing FSOD algorithms from a new perspective under a new taxonomy based on their contributions, i.e., data-oriented, model-oriented, and algorithm-oriented. Thus, a comprehensive survey with performance comparison is conducted on recent achievements of FSOD. Furthermore, we also analyze the technical challenges, the merits and demerits of these methods, and envision the future directions of FSOD. Specifically, we give an overview of FSOD, including the problem definition, common datasets, and evaluation protocols. The taxonomy is then proposed that groups FSOD methods into three types. Following this taxonomy, we provide a systematic review of the advances in FSOD. Finally, further discussions on performance, challenges, and future directions are presented.
Example-based Hypernetworks for Out-of-Distribution Generalization
Venue: arXiv cs.CL 2023
Year: 2023

As Natural Language Processing (NLP) algorithms continually achieve new milestones, out-of-distribution generalization remains a significant challenge. This paper addresses the issue of multi-source adaptation for unfamiliar domains: We leverage labeled data from multiple source domains to generalize to unknown target domains at training. Our innovative framework employs example-based Hypernetwork adaptation: a T5 encoder-decoder initially generates a unique signature from an input example, embedding it within the source domains' semantic space. This signature is subsequently utilized by a Hypernetwork to generate the task classifier's weights. We evaluated our method across two tasks - sentiment classification and natural language inference - in 29 adaptation scenarios, where it outpaced established algorithms. In an advanced version, the signature also enriches the input example's representation. We also compare our finetuned architecture to few-shot GPT-3, demonstrating its effectiveness in essential use cases. To our knowledge, this marks the first application of Hypernetworks to the adaptation for unknown domains.
Temporal Transductive Inference for Few-Shot Video Object Segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Few-shot video object segmentation (FS-VOS) aims at segmenting video frames using a few labelled examples of classes not seen during initial training. In this paper, we present a simple but effective temporal transductive inference (TTI) approach that leverages temporal consistency in the unlabelled video frames during few-shot inference. Key to our approach is the use of both global and local temporal constraints. The objective of the global constraint is to learn consistent linear classifiers for novel classes across the image sequence, whereas the local constraint enforces the proportion of foreground/background regions in each frame to be coherent across a local temporal window. These constraints act as spatiotemporal regularizers during the transductive inference to increase temporal coherence and reduce overfitting on the few-shot support set. Empirically, our model outperforms state-of-the-art meta-learning approaches in terms of mean intersection over union on YouTube-VIS by 2.8%. In addition, we introduce improved benchmarks that are exhaustively labelled (i.e. all object occurrences are labelled, unlike the currently available), and present a more realistic evaluation paradigm that targets data distribution shift between training and testing sets. Our empirical results and in-depth analysis confirm the added benefits of the proposed spatiotemporal regularizers to improve temporal coherence and overcome certain overfitting scenarios.
Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard
Venue: arXiv cs.NE 2023
Year: 2023

In this paper we show how to use drift analysis in the case of two random variables $X_1, X_2$, when the drift is approximatively given by $A\cdot (X_1,X_2)^T$ for a matrix $A$. The non-trivial case is that $X_1$ and $X_2$ impede each other's progress, and we give a full characterization of this case. As application, we develop and analyze a minimal example TwoLinear of a dynamic environment that can be hard. The environment consists of two linear function $f_1$ and $f_2$ with positive weights $1$ and $n$, and in each generation selection is based on one of them at random. They only differ in the set of positions that have weight $1$ and $n$. We show that the $(1+1)$-EA with mutation rate $χ/n$ is efficient for small $χ$ on TwoLinear, but does not find the shared optimum in polynomial time for large $χ$.
Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures
Venue: arXiv cs.LG 2023
Year: 2023

We study the problem of learning nonparametric distributions in a finite mixture, and establish tight bounds on the sample complexity for learning the component distributions in such models. Namely, we are given i.i.d. samples from a pdf $f$ where $$ f=w_1f_1+w_2f_2, \quad w_1+w_2=1, \quad w_1,w_2>0 $$ and we are interested in learning each component $f_i$. Without any assumptions on $f_i$, this problem is ill-posed. In order to identify the components $f_i$, we assume that each $f_i$ can be written as a convolution of a Gaussian and a compactly supported density $ν_i$ with $\text{supp}(ν_1)\cap \text{supp}(ν_2)=\emptyset$. Our main result shows that $(\frac{1}{\varepsilon})^{Ω(\log\log \frac{1}{\varepsilon})}$ samples are required for estimating each $f_i$. The proof relies on a quantitative Tauberian theorem that yields a fast rate of approximation with Gaussians, which may be of independent interest. To show this is tight, we also propose an algorithm that uses $(\frac{1}{\varepsilon})^{O(\log\log \frac{1}{\varepsilon})}$ samples to estimate each $f_i$. Unlike existing approaches to learning latent variable models based on moment-matching and tensor methods, our proof instead involves a delicate analysis of an ill-conditioned linear system via orthogonal functions. Combining these bounds, we conclude that the optimal sample complexity of this problem properly lies in between polynomial and exponential, which is not common in learning theory.