OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Scheduling Policy for Minimizing Age of Information with a Relay
Venue: arXiv cs.IT 2023
Year: 2023

We consider IoT sensor network where multiple sensors are connected to corresponding destination nodes via a relay. Thus, the relay schedules sensors to sample and destination nodes to update. The relay can select multiple sensors and destination nodes in each time. In order to minimize average weighted sum AoI, joint optimization of sampling and updating policy of the relay is investigated. For errorless and symmetric case where weights are equally given, necessary and sufficient conditions for optimality is found. Using this result, we obtain that the minimum average sum AoI in a closed-form expression which can be interpreted as fundamental limit of sum AoI in a single relay network. Also, for error-prone and symmetric case, we have proved that greedy policy achieves the minimum average sum AoI at the destination nodes. For general case, we have proposed scheduling policy obtained via reinforcement learning.
Implicit Multidimensional Projection of Local Subspaces
Venue: arXiv cs.LG 2023
Year: 2023

We propose a visualization method to understand the effect of multidimensional projection on local subspaces, using implicit function differentiation. Here, we understand the local subspace as the multidimensional local neighborhood of data points. Existing methods focus on the projection of multidimensional data points, and the neighborhood information is ignored. Our method is able to analyze the shape and directional information of the local subspace to gain more insights into the global structure of the data through the perception of local structures. Local subspaces are fitted by multidimensional ellipses that are spanned by basis vectors. An accurate and efficient vector transformation method is proposed based on analytical differentiation of multidimensional projections formulated as implicit functions. The results are visualized as glyphs and analyzed using a full set of specifically-designed interactions supported in our efficient web-based visualization tool. The usefulness of our method is demonstrated using various multi- and high-dimensional benchmark datasets. Our implicit differentiation vector transformation is evaluated through numerical comparisons; the overall method is evaluated through exploration examples and use cases.
SoK: Certified Robustness for Deep Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Great advances in deep neural networks (DNNs) have led to state-of-the-art performance on a wide range of tasks. However, recent studies have shown that DNNs are vulnerable to adversarial attacks, which have brought great concerns when deploying these models to safety-critical applications such as autonomous driving. Different defense approaches have been proposed against adversarial attacks, including: a) empirical defenses, which can usually be adaptively attacked again without providing robustness certification; and b) certifiably robust approaches, which consist of robustness verification providing the lower bound of robust accuracy against any attacks under certain conditions and corresponding robust training approaches. In this paper, we systematize certifiably robust approaches and related practical and theoretical implications and findings. We also provide the first comprehensive benchmark on existing robustness verification and training approaches on different datasets. In particular, we 1) provide a taxonomy for the robustness verification and training approaches, as well as summarize the methodologies for representative algorithms, 2) reveal the characteristics, strengths, limitations, and fundamental connections among these approaches, 3) discuss current research progresses, theoretical barriers, main challenges, and future directions for certifiably robust approaches for DNNs, and 4) provide an open-sourced unified platform to evaluate 20+ representative certifiably robust approaches.
Sequential composition of propositional logic programs
Venue: arXiv cs.LO 2023
Year: 2023

This paper introduces and studies the sequential composition and decomposition of propositional logic programs. We show that acyclic programs can be decomposed into single-rule programs and provide a general decomposition result for arbitrary programs. We show that the immediate consequence operator of a program can be represented via composition which allows us to compute its least model without any explicit reference to operators. This bridges the conceptual gap between the syntax and semantics of a propositional logic program in a mathematically satisfactory way.
Joint Demosaicking and Denoising Benefits from a Two-stage Training Strategy
Venue: arXiv cs.CV 2023
Year: 2023

Image demosaicking and denoising are the first two key steps of the color image production pipeline. The classical processing sequence has for a long time consisted of applying denoising first, and then demosaicking. Applying the operations in this order leads to oversmoothing and checkerboard effects. Yet, it was difficult to change this order, because once the image is demosaicked, the statistical properties of the noise are dramatically changed and hard to handle by traditional denoising models. In this paper, we address this problem by a hybrid machine learning method. We invert the traditional color filter array (CFA) processing pipeline by first demosaicking and then denoising. Our demosaicking algorithm, trained on noiseless images, combines a traditional method and a residual convolutional neural network (CNN). This first stage retains all known information, which is the key point to obtain faithful final results. The noisy demosaicked image is then passed through a second CNN restoring a noiseless full-color image. This pipeline order completely avoids checkerboard effects and restores fine image detail. Although CNNs can be trained to solve jointly demosaicking-denoising end-to-end, we find that this two-stage training performs better and is less prone to failure. It is shown experimentally to improve on the state of the art, both quantitatively and in terms of visual quality.
Question Directed Graph Attention Network for Numerical Reasoning over Text
Venue: arXiv cs.AI 2023
Year: 2023

Numerical reasoning over texts, such as addition, subtraction, sorting and counting, is a challenging machine reading comprehension task, since it requires both natural language understanding and arithmetic computation. To address this challenge, we propose a heterogeneous graph representation for the context of the passage and question needed for such reasoning, and design a question directed graph attention network to drive multi-step numerical reasoning over this context graph. The code link is at: https://github.com/emnlp2020qdgat/QDGAT
Unsupervised Summarization by Jointly Extracting Sentences and Keywords
Venue: arXiv cs.CL 2023
Year: 2023

We present RepRank, an unsupervised graph-based ranking model for extractive multi-document summarization in which the similarity between words, sentences, and word-to-sentence can be estimated by the distances between their vector representations in a unified vector space. In order to obtain desirable representations, we propose a self-attention based learning method that represent a sentence by the weighted sum of its word embeddings, and the weights are concentrated to those words hopefully better reflecting the content of a document. We show that salient sentences and keywords can be extracted in a joint and mutual reinforcement process using our learned representations, and prove that this process always converges to a unique solution leading to improvement in performance. A variant of absorbing random walk and the corresponding sampling-based algorithm are also described to avoid redundancy and increase diversity in the summaries. Experiment results with multiple benchmark datasets show that RepRank achieved the best or comparable performance in ROUGE.
Symbolic Relational Deep Reinforcement Learning based on Graph Neural Networks and Autoregressive Policy Decomposition
Venue: arXiv cs.LG 2023
Year: 2023

We focus on reinforcement learning (RL) in relational problems that are naturally defined in terms of objects, their relations, and object-centric actions. These problems are characterized by variable state and action spaces, and finding a fixed-length representation, required by most existing RL methods, is difficult, if not impossible. We present a deep RL framework based on graph neural networks and auto-regressive policy decomposition that naturally works with these problems and is completely domain-independent. We demonstrate the framework's broad applicability in three distinct domains and show impressive zero-shot generalization over different problem sizes.
Data-Driven Certification of Neural Networks with Random Input Noise
Venue: arXiv cs.LG 2023
Year: 2023

Methods to certify the robustness of neural networks in the presence of input uncertainty are vital in safety-critical settings. Most certification methods in the literature are designed for adversarial or worst-case inputs, but researchers have recently shown a need for methods that consider random input noise. In this paper, we examine the setting where inputs are subject to random noise coming from an arbitrary probability distribution. We propose a robustness certification method that lower-bounds the probability that network outputs are safe. This bound is cast as a chance-constrained optimization problem, which is then reformulated using input-output samples to make the optimization constraints tractable. We develop sufficient conditions for the resulting optimization to be convex, as well as on the number of samples needed to make the robustness bound hold with overwhelming probability. We show for a special case that the proposed optimization reduces to an intuitive closed-form solution. Case studies on synthetic, MNIST, and CIFAR-10 networks experimentally demonstrate that this method is able to certify robustness against various input noise regimes over larger uncertainty regions than prior state-of-the-art techniques.
Learning Diverse Options via InfoMax Termination Critic
Venue: arXiv cs.LG 2023
Year: 2023

We consider the problem of autonomously learning reusable temporally extended actions, or options, in reinforcement learning. While options can speed up transfer learning by serving as reusable building blocks, learning reusable options for unknown task distribution remains challenging. Motivated by the recent success of mutual information (MI) based skill learning, we hypothesize that more diverse options are more reusable. To this end, we propose a method for learning termination conditions of options by maximizing MI between options and corresponding state transitions. We derive a scalable approximation of this MI maximization via gradient ascent, yielding the InfoMax Termination Critic (IMTC) algorithm. Our experiments demonstrate that IMTC significantly improves the diversity of learned options without extrinsic rewards combined with an intrinsic option learning method. Moreover, we test the reusability of learned options by transferring options into various tasks, confirming that IMTC helps quick adaptation, especially in complex domains where an agent needs to manipulate objects.
Revisiting Deep Neural Network Test Coverage from the Test Effectiveness Perspective
Venue: arXiv cs.SE 2023
Year: 2023

Many test coverage metrics have been proposed to measure the Deep Neural Network (DNN) testing effectiveness, including structural coverage and non-structural coverage. These test coverage metrics are proposed based on the fundamental assumption: they are correlated with test effectiveness. However, the fundamental assumption is still not validated sufficiently and reasonably, which brings question on the usefulness of DNN test coverage. This paper conducted a revisiting study on the existing DNN test coverage from the test effectiveness perspective, to effectively validate the fundamental assumption. Here, we carefully considered the diversity of subjects, three test effectiveness criteria, and both typical and state-of-the-art test coverage metrics. Different from all the existing studies that deliver negative conclusions on the usefulness of existing DNN test coverage, we identified some positive conclusions on their usefulness from the test effectiveness perspective. In particular, we found the complementary relationship between structural and non-structural coverage and identified the practical usage scenarios and promising research directions for these existing test coverage metrics.
Achilles Heels for AGI/ASI via Decision Theoretic Adversaries
Venue: arXiv cs.AI 2023
Year: 2023

As progress in AI continues to advance, it is important to know how advanced systems will make choices and in what ways they may fail. Machines can already outsmart humans in some domains, and understanding how to safely build ones which may have capabilities at or above the human level is of particular concern. One might suspect that artificially generally intelligent (AGI) and artificially superintelligent (ASI) will be systems that humans cannot reliably outsmart. As a challenge to this assumption, this paper presents the Achilles Heel hypothesis which states that even a potentially superintelligent system may nonetheless have stable decision-theoretic delusions which cause them to make irrational decisions in adversarial settings. In a survey of key dilemmas and paradoxes from the decision theory literature, a number of these potential Achilles Heels are discussed in context of this hypothesis. Several novel contributions are made toward understanding the ways in which these weaknesses might be implanted into a system.
Exploring Flip Flop memories and beyond: training recurrent neural networks with key insights
Venue: arXiv cs.LG 2023
Year: 2023

Training neural networks to perform different tasks is relevant across various disciplines. In particular, Recurrent Neural Networks (RNNs) are of great interest in Computational Neuroscience. Open-source frameworks dedicated to Machine Learning, such as Tensorflow and Keras have produced significant changes in the development of technologies that we currently use. This work aims to make a significant contribution by comprehensively investigating and describing the implementation of a temporal processing task, specifically a 3-bit Flip Flop memory. We delve into the entire modelling process, encompassing equations, task parametrization, and software development. The obtained networks are meticulously analyzed to elucidate dynamics, aided by an array of visualization and analysis tools. Moreover, the provided code is versatile enough to facilitate the modelling of diverse tasks and systems. Furthermore, we present how memory states can be efficiently stored in the vertices of a cube in the dimensionally reduced space, supplementing previous results with a distinct approach.
Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
Venue: arXiv cs.DM 2023
Year: 2023

The greedy Prefer-same de Bruijn sequence construction was first presented by Eldert et al.[AIEE Transactions 77 (1958)]. As a greedy algorithm, it has one major downside: it requires an exponential amount of space to store the length $2^n$ de Bruijn sequence. Though de Bruijn sequences have been heavily studied over the last 60 years, finding an efficient construction for the Prefer-same de Bruijn sequence has remained a tantalizing open problem. In this paper, we unveil the underlying structure of the Prefer-same de Bruijn sequence and solve the open problem by presenting an efficient algorithm to construct it using $O(n)$ time per bit and only $O(n)$ space. Following a similar approach, we also present an efficient algorithm to construct the Prefer-opposite de Bruijn sequence.
MimicNorm: Weight Mean and Last BN Layer Mimic the Dynamic of Batch Normalization
Venue: arXiv cs.LG 2023
Year: 2023

Substantial experiments have validated the success of Batch Normalization (BN) Layer in benefiting convergence and generalization. However, BN requires extra memory and float-point calculation. Moreover, BN would be inaccurate on micro-batch, as it depends on batch statistics. In this paper, we address these problems by simplifying BN regularization while keeping two fundamental impacts of BN layers, i.e., data decorrelation and adaptive learning rate. We propose a novel normalization method, named MimicNorm, to improve the convergence and efficiency in network training. MimicNorm consists of only two light operations, including modified weight mean operations (subtract mean values from weight parameter tensor) and one BN layer before loss function (last BN layer). We leverage the neural tangent kernel (NTK) theory to prove that our weight mean operation whitens activations and transits network into the chaotic regime like BN layer, and consequently, leads to an enhanced convergence. The last BN layer provides autotuned learning rates and also improves accuracy. Experimental results show that MimicNorm achieves similar accuracy for various network structures, including ResNets and lightweight networks like ShuffleNet, with a reduction of about 20% memory consumption. The code is publicly available at https://github.com/Kid-key/MimicNorm.
Investigating Membership Inference Attacks under Data Dependencies
Venue: arXiv cs.CR 2023
Year: 2023

Training machine learning models on privacy-sensitive data has become a popular practice, driving innovation in ever-expanding fields. This has opened the door to new attacks that can have serious privacy implications. One such attack, the Membership Inference Attack (MIA), exposes whether or not a particular data point was used to train a model. A growing body of literature uses Differentially Private (DP) training algorithms as a defence against such attacks. However, these works evaluate the defence under the restrictive assumption that all members of the training set, as well as non-members, are independent and identically distributed. This assumption does not hold for many real-world use cases in the literature. Motivated by this, we evaluate membership inference with statistical dependencies among samples and explain why DP does not provide meaningful protection (the privacy parameter $ε$ scales with the training set size $n$) in this more general case. We conduct a series of empirical evaluations with off-the-shelf MIAs using training sets built from real-world data showing different types of dependencies among samples. Our results reveal that training set dependencies can severely increase the performance of MIAs, and therefore assuming that data samples are statistically independent can significantly underestimate the performance of MIAs.
Out-of-distribution detection for regression tasks: parameter versus predictor entropy
Venue: arXiv cs.LG 2023
Year: 2023

It is crucial to detect when an instance lies downright too far from the training samples for the machine learning model to be trusted, a challenge known as out-of-distribution (OOD) detection. For neural networks, one approach to this task consists of learning a diversity of predictors that all can explain the training data. This information can be used to estimate the epistemic uncertainty at a given newly observed instance in terms of a measure of the disagreement of the predictions. Evaluation and certification of the ability of a method to detect OOD require specifying instances which are likely to occur in deployment yet on which no prediction is available. Focusing on regression tasks, we choose a simple yet insightful model for this OOD distribution and conduct an empirical evaluation of the ability of various methods to discriminate OOD samples from the data. Moreover, we exhibit evidence that a diversity of parameters may fail to translate to a diversity of predictors. Based on the choice of an OOD distribution, we propose a new way of estimating the entropy of a distribution on predictors based on nearest neighbors in function space. This leads to a variational objective which, combined with the family of distributions given by a generative neural network, systematically produces a diversity of predictors that provides a robust way to detect OOD samples.
MSO Undecidability for Hereditary Classes of Unbounded Clique-Width
Venue: arXiv cs.LO 2023
Year: 2023

Seese's conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them.
Self-Supervised Learning for Biological Sample Localization in 3D Tomographic Images
Venue: arXiv cs.CV 2023
Year: 2023

In synchrotron-based Computed Tomography (CT) there is a trade-off between spatial resolution, field of view and speed of positioning and alignment of samples. The problem is even more prominent for high-throughput tomography--an automated setup, capable of scanning large batches of samples without human interaction. As a result, in many applications, only 20-30% of the reconstructed volume contains the actual sample. Such data redundancy clutters the storage and increases processing time. Hence, an automated sample localization becomes an important practical problem. In this work, we describe two self-supervised losses designed for biological CT. We further demonstrate how to employ the uncertainty estimation for sample localization. This approach shows the ability to localize a sample with less than 1.5\% relative error and reduce the used storage by a factor of four. We also show that one of the proposed losses works reasonably well as a pre-training task for the semantic segmentation.
Sharp Thresholds in Random Simple Temporal Graphs
Venue: arXiv cs.DM 2023
Year: 2023

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdős-Rényi random graph $G~G_{n,p}$ by considering a random permutation $π$ of the edges and interpreting the ranks in $π$ as presence times. Temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at $p=\log n/n$ any fixed pair of vertices can a.a.s. reach each other; at $2\log n/n$ at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at $3\log n/n$ all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size $2n+o(n)$ as soon as it becomes temporally connected, which is nearly optimal as $2n-4$ is a lower bound. This result is significant because temporal graphs do not admit spanners of size $O(n)$ in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size $o(n^2)$ (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all non-negligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners -- i.e., spanners of size $2n-2$ made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently) -- exist a.a.s. at $4\log n/n$, this threshold being also sharp. Finally, we show that optimal spanners (of size $2n-4$) also exist a.a.s. at $p = 4\log n/n$.