OpenRaiser/Intern-Atlas huggingface dataset:
New Upper Bounds on the Error Probability under ML Decoding for Spinal Codes and the Joint Transmission-Decoding System Design
Venue: arXiv cs.IT 2022
Year: 2022

Spinal codes are a type of capacity-achieving rateless codes that have been proved to approach the Shannon capacity over the additive white Gaussian noise (AWGN) channel and the binary symmetric channel (BSC). In this paper, we aim to analyze the bounds on the error probability of Spinal codes and design a joint transmission-decoding system. First, in the finite block-length regime, we derive new upper bounds on the Maximum Likelihood (ML) decoding error probability for Spinal codes over both the AWGN channel and the BSC. Then, based on the derived bounds, we formulate a rate maximization problem. As the solution exhibits an incremental-tail-transmission pattern, we propose an improved transmission scheme, referred to as the thresholded incremental tail transmission (TITT) scheme. Moreover, we also develop a dynamic TITT-matching decoding algorithm, called the bubble decoding with memory (BD-M) algorithm, to reduce the decoding time complexity. The TITT scheme at the transmitter and the BD-M algorithm at the receiver jointly constitute a dynamic transmission-decoding system for Spinal code, improving its rate performance and decoding throughput. Theoretical analysis and simulation results are provided to verify the superiority of the derived bounds and the proposed joint transmission-decoding system design.
A Survey on Ensemble Learning under the Era of Deep Learning
Venue: arXiv cs.LG 2022
Year: 2022

Due to the dominant position of deep learning (mostly deep neural networks) in various artificial intelligence applications, recently, ensemble learning based on deep neural networks (ensemble deep learning) has shown significant performances in improving the generalization of learning system. However, since modern deep neural networks usually have millions to billions of parameters, the time and space overheads for training multiple base deep learners and testing with the ensemble deep learner are far greater than that of traditional ensemble learning. Though several algorithms of fast ensemble deep learning have been proposed to promote the deployment of ensemble deep learning in some applications, further advances still need to be made for many applications in specific fields, where the developing time and computing resources are usually restricted or the data to be processed is of large dimensionality. An urgent problem needs to be solved is how to take the significant advantages of ensemble deep learning while reduce the required expenses so that many more applications in specific fields can benefit from it. For the alleviation of this problem, it is essential to know about how ensemble learning has developed under the era of deep learning. Thus, in this article, we present fundamental discussions focusing on data analyses of published works, methodologies, recent advances and unattainability of traditional ensemble learning and ensemble deep learning. We hope this article will be helpful to realize the intrinsic problems and technical challenges faced by future developments of ensemble learning under the era of deep learning.
Multi-sense embeddings through a word sense disambiguation process
Venue: arXiv cs.CL 2022
Year: 2022

Natural Language Understanding has seen an increasing number of publications in the last few years, especially after robust word embeddings models became prominent, when they proved themselves able to capture and represent semantic relationships from massive amounts of data. Nevertheless, traditional models often fall short in intrinsic issues of linguistics, such as polysemy and homonymy. Any expert system that makes use of natural language in its core, can be affected by a weak semantic representation of text, resulting in inaccurate outcomes based on poor decisions. To mitigate such issues, we propose a novel approach called Most Suitable Sense Annotation (MSSA), that disambiguates and annotates each word by its specific sense, considering the semantic effects of its context. Our approach brings three main contributions to the semantic representation scenario: (i) an unsupervised technique that disambiguates and annotates words by their senses, (ii) a multi-sense embeddings model that can be extended to any traditional word embeddings algorithm, and (iii) a recurrent methodology that allows our models to be re-used and their representations refined. We test our approach on six different benchmarks for the word similarity task, showing that our approach can produce state-of-the-art results and outperforms several more complex state-of-the-art systems.
Self-Adaptive Training: Bridging Supervised and Self-Supervised Learning
Venue: arXiv cs.LG 2022
Year: 2022

We propose self-adaptive training -- a unified training algorithm that dynamically calibrates and enhances training processes by model predictions without incurring an extra computational cost -- to advance both supervised and self-supervised learning of deep neural networks. We analyze the training dynamics of deep networks on training data that are corrupted by, e.g., random noise and adversarial examples. Our analysis shows that model predictions are able to magnify useful underlying information in data and this phenomenon occurs broadly even in the absence of any label information, highlighting that model predictions could substantially benefit the training processes: self-adaptive training improves the generalization of deep networks under noise and enhances the self-supervised representation learning. The analysis also sheds light on understanding deep learning, e.g., a potential explanation of the recently-discovered double-descent phenomenon in empirical risk minimization and the collapsing issue of the state-of-the-art self-supervised learning algorithms. Experiments on the CIFAR, STL, and ImageNet datasets verify the effectiveness of our approach in three applications: classification with label noise, selective classification, and linear evaluation. To facilitate future research, the code has been made publicly available at https://github.com/LayneH/self-adaptive-training.
The Gospel According to Q: Understanding the QAnon Conspiracy from the Perspective of Canonical Information
Venue: arXiv cs.CY 2022
Year: 2022

The QAnon conspiracy theory claims that a cabal of (literally) blood-thirsty politicians and media personalities are engaged in a war to destroy society. By interpreting cryptic "drops" of information from an anonymous insider calling themself Q, adherents of the conspiracy theory believe that Donald Trump is leading them in an active fight against this cabal. QAnon has been covered extensively by the media, as its adherents have been involved in multiple violent acts, including the January 6th, 2021 seditious storming of the US Capitol building. Nevertheless, we still have relatively little understanding of how the theory evolved and spread on the Web, and the role played in that by multiple platforms. To address this gap, we study QAnon from the perspective of "Q" themself. We build a dataset of 4,949 canonical Q drops collected from six "aggregation sites," which curate and archive them from their original posting to anonymous and ephemeral image boards. We expose that these sites have a relatively low (overall) agreement, and thus at least some Q drops should probably be considered apocryphal. We then analyze the Q drops' contents to identify topics of discussion and find statistically significant indications that drops were not authored by a single individual. Finally, we look at how posts on Reddit are used to disseminate Q drops to wider audiences. We find that dissemination was (initially) limited to a few sub-communities and that, while heavy-handed moderation decisions have reduced the overall issue, the "gospel" of Q persists on the Web.
Time series compression: a survey
Venue: arXiv cs.DB 2022
Year: 2022

The presence of smart objects is increasingly widespread and their ecosystem, also known as Internet of Things, is relevant in many different application scenarios. The huge amount of temporally annotated data produced by these smart devices demand for efficient techniques for transfer and storage of time series data. Compression techniques play an important role toward this goal and, despite the fact that standard compression methods could be used with some benefit, there exist several ones that specifically address the case of time series by exploiting their peculiarities to achieve a more effective compression and a more accurate decompression in the case of lossy compression techniques. This paper provides a state-of-the-art survey of the principal time series compression techniques, proposing a taxonomy to classify them considering their overall approach and their characteristics. Furthermore, we analyze the performances of the selected algorithms by discussing and comparing the experimental results that where provided in the original articles. The goal of this paper is to provide a comprehensive and homogeneous reconstruction of the state-of-the-art which is currently fragmented across many papers that use different notations and where the proposed methods are not organized according to a classification.
Newcomer OSS-Candidates: Characterizing Contributions of Novice Developers to GitHub
Venue: arXiv cs.SE 2022
Year: 2022

The ability of an Open Source Software (OSS) project to attract, onboard, and retain any newcomer is vital to its livelihood. Although, evidence suggests an upsurge in novice developers joining social coding platforms (such as GitHub), the extent to which their activities result in a OSS contribution is unknown. Henceforth, we execute the protocols of a registered report to study activities of a "Newcomer OSS-Candidate", who is a novice developer that is new to that social coding platform, and has the intention to later onboard an OSS project. Using GitHub as a case platform, we analyze 171 identified Newcomer OSS-Candidates to characterize their contribution activities. Results show that Newcomer OSS-Candidates are likely to target software based repositories (i.e., 66%), and their first contributions are mainly associated with development (commits) and maintenance (PRs). Newcomer OSS-Candidates are less likely to practice social coding, but eventually end up onboarding (i.e., 30% quantitative, 70% follow-up survey) an OSS project. Furthermore, they cite finding a way to start as the most challenging barrier to contribute. Our work reveals insights on how newcomers to social coding platforms are potential sources of OSS contributions.
Enhanced word embeddings using multi-semantic representation through lexical chains
Venue: arXiv cs.CL 2022
Year: 2022

The relationship between words in a sentence often tells us more about the underlying semantic content of a document than its actual words, individually. In this work, we propose two novel algorithms, called Flexible Lexical Chain II and Fixed Lexical Chain II. These algorithms combine the semantic relations derived from lexical chains, prior knowledge from lexical databases, and the robustness of the distributional hypothesis in word embeddings as building blocks forming a single system. In short, our approach has three main contributions: (i) a set of techniques that fully integrate word embeddings and lexical chains; (ii) a more robust semantic representation that considers the latent relation between words in a document; and (iii) lightweight word embeddings models that can be extended to any natural language task. We intend to assess the knowledge of pre-trained models to evaluate their robustness in the document classification task. The proposed techniques are tested against seven word embeddings algorithms using five different machine learning classifiers over six scenarios in the document classification task. Our results show the integration between lexical chains and word embeddings representations sustain state-of-the-art results, even against more complex systems.
Learning Setup Policies: Reliable Transition Between Locomotion Behaviours
Venue: arXiv cs.RO 2022
Year: 2022

Dynamic platforms that operate over many unique terrain conditions typically require many behaviours. To transition safely, there must be an overlap of states between adjacent controllers. We develop a novel method for training setup policies that bridge the trajectories between pre-trained Deep Reinforcement Learning (DRL) policies. We demonstrate our method with a simulated biped traversing a difficult jump terrain, where a single policy fails to learn the task, and switching between pre-trained policies without setup policies also fails. We perform an ablation of key components of our system, and show that our method outperforms others that learn transition policies. We demonstrate our method with several difficult and diverse terrain types, and show that we can use setup policies as part of a modular control suite to successfully traverse a sequence of complex terrains. We show that using setup policies improves the success rate for traversing a single difficult jump terrain (from 51.3% success rate with the best comparative method to 82.2%), and traversing a random sequence of difficult obstacles (from 1.9% without setup policies to 71.2%).
A Comprehensive Evaluation Framework for Deep Model Robustness
Venue: arXiv cs.CV 2022
Year: 2022

Deep neural networks (DNNs) have achieved remarkable performance across a wide range of applications, while they are vulnerable to adversarial examples, which motivates the evaluation and benchmark of model robustness. However, current evaluations usually use simple metrics to study the performance of defenses, which are far from understanding the limitation and weaknesses of these defense methods. Thus, most proposed defenses are quickly shown to be attacked successfully, which results in the ``arm race'' phenomenon between attack and defense. To mitigate this problem, we establish a model robustness evaluation framework containing 23 comprehensive and rigorous metrics, which consider two key perspectives of adversarial learning (i.e., data and model). Through neuron coverage and data imperceptibility, we use data-oriented metrics to measure the integrity of test examples; by delving into model structure and behavior, we exploit model-oriented metrics to further evaluate robustness in the adversarial setting. To fully demonstrate the effectiveness of our framework, we conduct large-scale experiments on multiple datasets including CIFAR-10, SVHN, and ImageNet using different models and defenses with our open-source platform. Overall, our paper provides a comprehensive evaluation framework, where researchers could conduct comprehensive and fast evaluations using the open-source toolkit, and the analytical results could inspire deeper understanding and further improvement to the model robustness.
Towards glass-box CNNs
Venue: arXiv cs.CV 2022
Year: 2022

With the substantial performance of neural networks in sensitive fields increases the need for interpretable deep learning models. Major challenge is to uncover the multiscale and distributed representation hidden inside the basket mappings of the deep neural networks. Researchers have been trying to comprehend it through visual analysis of features, mathematical structures, or other data-driven approaches. Here, we work on implementation invariances of CNN-based representations and present an analytical binary prototype that provides useful insights for large scale real-life applications. We begin by unfolding conventional CNN and then repack it with a more transparent representation. Inspired by the attainment of neural networks, we choose to present our findings as a three-layer model. First is a representation layer that encompasses both the class information (group invariant) and symmetric transformations (group equivariant) of input images. Through these transformations, we decrease intra-class distance and increase the inter-class distance. It is then passed through a dimension reduction layer followed by a classifier. The proposed representation is compared with the equivariance of AlexNet (CNN) internal representation for better dissemination of simulation results. We foresee following immediate advantages of this toy version: i) contributes pre-processing of data to increase the feature or class separability in large scale problems, ii) helps designing neural architecture to improve the classification performance in multi-class problems, and iii) helps building interpretable CNN through scalable functional blocks.
Visual explanation of black-box model: Similarity Difference and Uniqueness (SIDU) method
Venue: arXiv cs.CV 2022
Year: 2022

Explainable Artificial Intelligence (XAI) has in recent years become a well-suited framework to generate human understandable explanations of "black-box" models. In this paper, a novel XAI visual explanation algorithm known as the Similarity Difference and Uniqueness (SIDU) method that can effectively localize entire object regions responsible for prediction is presented in full detail. The SIDU algorithm robustness and effectiveness is analyzed through various computational and human subject experiments. In particular, the SIDU algorithm is assessed using three different types of evaluations (Application, Human and Functionally-Grounded) to demonstrate its superior performance. The robustness of SIDU is further studied in the presence of adversarial attack on "black-box" models to better understand its performance. Our code is available at: https://github.com/satyamahesh84/SIDU_XAI_CODE.
HANA: A HAndwritten NAme Database for Offline Handwritten Text Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Methods for linking individuals across historical data sets, typically in combination with AI based transcription models, are developing rapidly. Probably the single most important identifier for linking is personal names. However, personal names are prone to enumeration and transcription errors and although modern linking methods are designed to handle such challenges, these sources of errors are critical and should be minimized. For this purpose, improved transcription methods and large-scale databases are crucial components. This paper describes and provides documentation for HANA, a newly constructed large-scale database which consists of more than 3.3 million names. The database contain more than 105 thousand unique names with a total of more than 1.1 million images of personal names, which proves useful for transfer learning to other settings. We provide three examples hereof, obtaining significantly improved transcription accuracy on both Danish and US census data. In addition, we present benchmark results for deep learning models automatically transcribing the personal names from the scanned documents. Through making more challenging large-scale databases publicly available we hope to foster more sophisticated, accurate, and robust models for handwritten text recognition.
Non-Asymptotic Converse Bounds Via Auxiliary Channels
Venue: arXiv cs.IT 2022
Year: 2022

This paper presents a new derivation method of converse bounds on the non-asymptotic achievable rate of discrete weakly symmetric memoryless channels. It is based on the finite blocklength statistics of the channel, where with the use of an auxiliary channel the converse bound is produced. This method is general and initially is presented for an arbitrary weakly symmetric channel. Afterwards, the main result is specialized for the $q$-ary erasure channel (QEC), binary symmetric channel (BSC), and QEC with stop feedback. Numerical evaluations show identical or comparable bounds to the state-of-the-art in the cases of QEC and BSC, and a tighter bound for the QEC with stop feedback.
A Deterministic Algorithm for the Discrete Logarithm Problem in a Semigroup
Venue: arXiv cs.CC 2022
Year: 2022

The discrete logarithm problem in a finite group is the basis for many protocols in cryptography. The best general algorithms which solve this problem have time complexity of $\mathcal{O}(\sqrt{N}\log N)$, and a space complexity of $\mathcal{O}(\sqrt{N})$ where $N$ is the order of the group. (If $N$ is unknown, a simple modification would achieve a time complexity of $\mathcal{O}(\sqrt{N}(\log N)^2)$.) These algorithms require the inversion of some group elements or rely on finding collisions and the existence of inverses, and thus do not adapt to work in the general semigroup setting. For semigroups, probabilistic algorithms with similar time complexity have been proposed. The main result of this paper is a deterministic algorithm for solving the discrete logarithm problem in a semigroup. Specifically, let $x$ be an element in a semigroup having finite order $N_x$. The paper provides an algorithm, which, given any element $y\in \langle x \rangle $, provides all natural numbers $m$ with $x^m=y$, and has time complexity $O(\sqrt{N_x}(\log N_x)^2)$ steps. The paper also gives an analysis of the success rates of the existing probabilistic algorithms, which were so far only conjectured or stated loosely.
Generalising via Meta-Examples for Continual Learning in the Wild
Venue: arXiv cs.LG 2022
Year: 2022

Future deep learning systems call for techniques that can deal with the evolving nature of temporal data and scarcity of annotations when new problems occur. As a step towards this goal, we present FUSION (Few-shot UnSupervIsed cONtinual learning), a learning strategy that enables a neural network to learn quickly and continually on streams of unlabelled data and unbalanced tasks. The objective is to maximise the knowledge extracted from the unlabelled data stream (unsupervised), favor the forward transfer of previously learnt tasks and features (continual) and exploit as much as possible the supervised information when available (few-shot). The core of FUSION is MEML - Meta-Example Meta-Learning - that consolidates a meta-representation through the use of a self-attention mechanism during a single inner loop in the meta-optimisation stage. To further enhance the capability of MEML to generalise from few data, we extend it by creating various augmented surrogate tasks and by optimising over the hardest. An extensive experimental evaluation on public computer vision benchmarks shows that FUSION outperforms existing state-of-the-art solutions both in the few-shot and continual learning experimental settings.
Increasing the Confidence of Deep Neural Networks by Coverage Analysis
Venue: arXiv cs.LG 2022
Year: 2022

The great performance of machine learning algorithms and deep neural networks in several perception and control tasks is pushing the industry to adopt such technologies in safety-critical applications, as autonomous robots and self-driving vehicles. At present, however, several issues need to be solved to make deep learning methods more trustworthy, predictable, safe, and secure against adversarial attacks. Although several methods have been proposed to improve the trustworthiness of deep neural networks, most of them are tailored for specific classes of adversarial examples, hence failing to detect other corner cases or unsafe inputs that heavily deviate from the training samples. This paper presents a lightweight monitoring architecture based on coverage paradigms to enhance the model robustness against different unsafe inputs. In particular, four coverage analysis methods are proposed and tested in the architecture for evaluating multiple detection logics. Experimental results show that the proposed approach is effective in detecting both powerful adversarial examples and out-of-distribution inputs, introducing limited extra-execution time and memory requirements.