OpenRaiser/Intern-Atlas huggingface dataset:
An Algebraic Method to Fidelity-based Model Checking over Quantum Markov Chains
Venue: arXiv cs.LO 2021
Year: 2021

Fidelity is one of the most widely used quantities in quantum information that measure the distance of quantum states through a noisy channel. In this paper, we introduce a quantum analogy of computation tree logic (CTL) called QCTL, which concerns fidelity instead of probability in probabilistic CTL, over quantum Markov chains (QMCs). Noisy channels are modelled by super-operators, which are specified by QCTL formulas; the initial quantum states are modelled by density operators, which are left parametric in the given QMC. The problem is to compute the minimumfidelity over all initial states for conservation. We achieve it by a reduction to quantifier elimination in the existential theory of the reals. The method is absolutely exact, so that QCTL formulas are proven to be decidable in exponential time. Finally, we implement the proposed method and demonstrate its effectiveness via a quantum IPv4 protocol.
Large scale deduplication based on fingerprints
Venue: arXiv cs.CV 2021
Year: 2021

In fingerprint-based systems, the size of databases increases considerably with population growth. In developing countries, because of the difficulty in using a central system when enlisting voters, it often happens that several regional voter databases are created and then merged to form a central database. A process is used to remove duplicates and ensure uniqueness by voter. Until now, companies specializing in biometrics use several costly computing servers with algorithms to perform large-scale deduplication based on fingerprints. These algorithms take a considerable time because of their complexity in O (n2), where n is the size of the database. This article presents an algorithm that can perform this operation in O (2n), with just a computer. It is based on the development of an index obtained using a 5 * 5 matrix performed on each fingerprint. This index makes it possible to build clusters of O (1) in size in order to compare fingerprints. This approach has been evaluated using close to 11 4000 fingerprints, and the results obtained show that this approach allows a penetration rate of less than 1%, an almost O (1) identification, and an O (n) deduplication. A base of 10 000 000 fingerprints can be deduplicated with a just computer in less than two hours, contrary to several days and servers for the usual tools. Keywords: fingerprint, cluster, index, deduplication.
Multi-Source Anomaly Detection in Distributed IT Systems
Venue: arXiv cs.LG 2021
Year: 2021

The multi-source data generated by distributed systems, provide a holistic description of the system. Harnessing the joint distribution of the different modalities by a learning model can be beneficial for critical applications for maintenance of the distributed systems. One such important task is the task of anomaly detection where we are interested in detecting the deviation of the current behaviour of the system from the theoretically expected. In this work, we utilize the joint representation from the distributed traces and system log data for the task of anomaly detection in distributed systems. We demonstrate that the joint utilization of traces and logs produced better results compared to the single modality anomaly detection methods. Furthermore, we formalize a learning task - next template prediction NTP, that is used as a generalization for anomaly detection for both logs and distributed trace. Finally, we demonstrate that this formalization allows for the learning of template embedding for both the traces and logs. The joint embeddings can be reused in other applications as good initialization for spans and logs.
Joint Learning of Hyperbolic Label Embeddings for Hierarchical Multi-label Classification
Venue: arXiv cs.LG 2021
Year: 2021

We consider the problem of multi-label classification where the labels lie in a hierarchy. However, unlike most existing works in hierarchical multi-label classification, we do not assume that the label-hierarchy is known. Encouraged by the recent success of hyperbolic embeddings in capturing hierarchical relations, we propose to jointly learn the classifier parameters as well as the label embeddings. Such a joint learning is expected to provide a twofold advantage: i) the classifier generalizes better as it leverages the prior knowledge of existence of a hierarchy over the labels, and ii) in addition to the label co-occurrence information, the label-embedding may benefit from the manifold structure of the input datapoints, leading to embeddings that are more faithful to the label hierarchy. We propose a novel formulation for the joint learning and empirically evaluate its efficacy. The results show that the joint learning improves over the baseline that employs label co-occurrence based pre-trained hyperbolic embeddings. Moreover, the proposed classifiers achieve state-of-the-art generalization on standard benchmarks. We also present evaluation of the hyperbolic embeddings obtained by joint learning and show that they represent the hierarchy more accurately than the other alternatives.
Coarse and Fine-Grained Hostility Detection in Hindi Posts using Fine Tuned Multilingual Embeddings
Venue: arXiv cs.CL 2021
Year: 2021

Due to the wide adoption of social media platforms like Facebook, Twitter, etc., there is an emerging need of detecting online posts that can go against the community acceptance standards. The hostility detection task has been well explored for resource-rich languages like English, but is unexplored for resource-constrained languages like Hindidue to the unavailability of large suitable data. We view this hostility detection as a multi-label multi-class classification problem. We propose an effective neural network-based technique for hostility detection in Hindi posts. We leverage pre-trained multilingual Bidirectional Encoder Representations of Transformer (mBERT) to obtain the contextual representations of Hindi posts. We have performed extensive experiments including different pre-processing techniques, pre-trained models, neural architectures, hybrid strategies, etc. Our best performing neural classifier model includes One-vs-the-Rest approach where we obtained 92.60%, 81.14%,69.59%, 75.29% and 73.01% F1 scores for hostile, fake, hate, offensive, and defamation labels respectively. The proposed model outperformed the existing baseline models and emerged as the state-of-the-art model for detecting hostility in the Hindi posts.
Estimating Conditional Mutual Information for Discrete-Continuous Mixtures using Multi-Dimensional Adaptive Histograms
Venue: arXiv cs.IT 2021
Year: 2021

Estimating conditional mutual information (CMI) is an essential yet challenging step in many machine learning and data mining tasks. Estimating CMI from data that contains both discrete and continuous variables, or even discrete-continuous mixture variables, is a particularly hard problem. In this paper, we show that CMI for such mixture variables, defined based on the Radon-Nikodym derivate, can be written as a sum of entropies, just like CMI for purely discrete or continuous data. Further, we show that CMI can be consistently estimated for discrete-continuous mixture variables by learning an adaptive histogram model. In practice, we estimate such a model by iteratively discretizing the continuous data points in the mixture variables. To evaluate the performance of our estimator, we benchmark it against state-of-the-art CMI estimators as well as evaluate it in a causal discovery setting.
A Multi-Perspective Study of Internet Performance during the COVID-19 Outbreak
Venue: arXiv cs.NI 2021
Year: 2021

The rapid spread of the novel corona virus, SARS-CoV-2, has prompted an unprecedented response from governments across the world. A third of the world population have been placed in varying degrees of lockdown, and the Internet has become the primary medium for conducting most businesses and schooling activities. This paper aims to provide a multi-prospective account of Internet performance during the first wave of the pandemic. We investigate the performance of the Internet control plane and data plane from a number of globally spread vantage points. We also look closer at two case studies. First, we look at growth in video traffic during the pandemic, using traffic logs from a global video conferencing provider. Second, we leverage a country-wide deployment of measurement probes to assess the performance of mobile networks during the outbreak. We find that the lockdown has visibly impacted almost all aspects of Internet performance. Access networks have experienced an increase in peak and off-peak end to end latency. Mobile networks exhibit significant changes in download speed, while certain types of video traffic has increased by an order of magnitude. Despite these changes, the Internet seems to have coped reasonably well with the lockdown traffic.
Top Program Construction and Reduction for polynomial time Meta-Interpretive Learning
Venue: arXiv cs.AI 2021
Year: 2021

Meta-Interpretive Learners, like most ILP systems, learn by searching for a correct hypothesis in the hypothesis space, the powerset of all constructible clauses. We show how this exponentially-growing search can be replaced by the construction of a Top program: the set of clauses in all correct hypotheses that is itself a correct hypothesis. We give an algorithm for Top program construction and show that it constructs a correct Top program in polynomial time and from a finite number of examples. We implement our algorithm in Prolog as the basis of a new MIL system, Louise, that constructs a Top program and then reduces it by removing redundant clauses. We compare Louise to the state-of-the-art search-based MIL system Metagol in experiments on grid world navigation, graph connectedness and grammar learning datasets and find that Louise improves on Metagol's predictive accuracy when the hypothesis space and the target theory are both large, or when the hypothesis space does not include a correct hypothesis because of "classification noise" in the form of mislabelled examples. When the hypothesis space or the target theory are small, Louise and Metagol perform equally well.
Image Steganography based on Iteratively Adversarial Samples of A Synchronized-directions Sub-image
Venue: arXiv cs.CV 2021
Year: 2021

Nowadays a steganography has to face challenges of both feature based staganalysis and convolutional neural network (CNN) based steganalysis. In this paper, we present a novel steganography scheme denoted as ITE-SYN (based on ITEratively adversarial perturbations onto a SYNchronized-directions sub-image), by which security data is embedded with synchronizing modification directions to enhance security and then iteratively increased perturbations are added onto a sub-image to reduce loss with cover class label of the target CNN classifier. Firstly an exist steganographic function is employed to compute initial costs. Then the cover image is decomposed into some non-overlapped sub-images. After each sub-image is embedded, costs will be adjusted following clustering modification directions profile. And then the next sub-image will be embedded with adjusted costs until all secret data has been embedded. If the target CNN classifier does not discriminate the stego image as a cover image, based on adjusted costs, we change costs with adversarial manners according to signs of gradients back-propagated from the CNN classifier. And then a sub-image is chosen to be re-embedded with changed costs. Adversarial intensity will be iteratively increased until the adversarial stego image can fool the target CNN classifier. Experiments demonstrate that the proposed method effectively enhances security to counter both conventional feature-based classifiers and CNN classifiers, even other non-target CNN classifiers.
Denoising Score Matching with Random Fourier Features
Venue: arXiv cs.LG 2021
Year: 2021

The density estimation is one of the core problems in statistics. Despite this, existing techniques like maximum likelihood estimation are computationally inefficient due to the intractability of the normalizing constant. For this reason an interest to score matching has increased being independent on the normalizing constant. However, such estimator is consistent only for distributions with the full space support. One of the approaches to make it consistent is to add noise to the input data which is called Denoising Score Matching. In this work we derive analytical expression for the Denoising Score matching using the Kernel Exponential Family as a model distribution. The usage of the kernel exponential family is motivated by the richness of this class of densities. To tackle the computational complexity we use Random Fourier Features based approximation of the kernel function. The analytical expression allows to drop additional regularization terms based on the higher-order derivatives as they are already implicitly included. Moreover, the obtained expression explicitly depends on the noise variance, so the validation loss can be straightforwardly used to tune the noise level. Along with benchmark experiments, the model was tested on various synthetic distributions to study the behaviour of the model in different cases. The empirical study shows comparable quality to the competing approaches, while the proposed method being computationally faster. The latter one enables scaling up to complex high-dimensional data.
Irrationality and Transcendence Criteria for Infinite Series in Isabelle/HOL
Venue: arXiv cs.LO 2021
Year: 2021

We give an overview of our formalizations in the proof assistant Isabelle/HOL of certain irrationality and transcendence criteria for infinite series from three different research papers: by Erdős and Straus (1974), Hančl (2002), and Hančl and Rucki (2005). Our formalizations in Isabelle/HOL can be found on the Archive of Formal Proofs. Here we describe selected aspects of the formalization and discuss what this reveals about the use and potential of Isabelle/HOL in formalizing modern mathematical research, particularly in these parts of number theory and analysis.
Random Shadows and Highlights: A new data augmentation method for extreme lighting conditions
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we propose a new data augmentation method, Random Shadows and Highlights (RSH) to acquire robustness against lighting perturbations. Our method creates random shadows and highlights on images, thus challenging the neural network during the learning process such that it acquires immunity against such input corruptions in real world applications. It is a parameter-learning free method which can be integrated into most vision related learning applications effortlessly. With extensive experimentation, we demonstrate that RSH not only increases the robustness of the models against lighting perturbations, but also reduces over-fitting significantly. Thus RSH should be considered essential for all vision related learning systems. Code is available at: https://github.com/OsamaMazhar/Random-Shadows-Highlights.
Should Ensemble Members Be Calibrated?
Venue: arXiv cs.LG 2021
Year: 2021

Underlying the use of statistical approaches for a wide range of applications is the assumption that the probabilities obtained from a statistical model are representative of the "true" probability that event, or outcome, will occur. Unfortunately, for modern deep neural networks this is not the case, they are often observed to be poorly calibrated. Additionally, these deep learning approaches make use of large numbers of model parameters, motivating the use of Bayesian, or ensemble approximation, approaches to handle issues with parameter estimation. This paper explores the application of calibration schemes to deep ensembles from both a theoretical perspective and empirically on a standard image classification task, CIFAR-100. The underlying theoretical requirements for calibration, and associated calibration criteria, are first described. It is shown that well calibrated ensemble members will not necessarily yield a well calibrated ensemble prediction, and if the ensemble prediction is well calibrated its performance cannot exceed that of the average performance of the calibrated ensemble members. On CIFAR-100 the impact of calibration for ensemble prediction, and associated calibration is evaluated. Additionally the situation where multiple different topologies are combined together is discussed.
Analysis of E-commerce Ranking Signals via Signal Temporal Logic
Venue: arXiv cs.LO 2021
Year: 2021

The timed position of documents retrieved by learning to rank models can be seen as signals. Signals carry useful information such as drop or rise of documents over time or user behaviors. In this work, we propose to use the logic formalism called Signal Temporal Logic (STL) to characterize document behaviors in ranking accordingly to the specified formulas. Our analysis shows that interesting document behaviors can be easily formalized and detected thanks to STL formulas. We validate our idea on a dataset of 100K product signals. Through the presented framework, we uncover interesting patterns, such as cold start, warm start, spikes, and inspect how they affect our learning to ranks models.
A Perspective-Based Understanding of Project Success
Venue: arXiv cs.SE 2021
Year: 2021

Answering the call for alternative approaches to researching project management, we explore the evaluation of project success from a subjectivist perspective. An in-depth, longitudinal case study of information systems development in a large manufacturing company was used to investigate how various project stakeholders subjectively perceived the project outcome and what evaluation criteria they drew on in doing so. A conceptual framework is developed for understanding and analyzing evaluations of project success, both formal and informal. The framework highlights how different stakeholder perspectives influence the perceived outcome(s) of a project, and how project evaluations may differ between stakeholders and across time.
Noise Is Useful: Exploiting Data Diversity for Edge Intelligence
Venue: arXiv cs.IT 2021
Year: 2021

Edge intelligence requires to fast access distributed data samples generated by edge devices. The challenge is using limited radio resource to acquire massive data samples for training machine learning models at edge server. In this article, we propose a new communication-efficient edge intelligence scheme where the most useful data samples are selected to train the model. Here the usefulness or values of data samples is measured by data diversity which is defined as the difference between data samples. We derive a close-form expression of data diversity that combines data informativeness and channel quality. Then a joint data-and-channel diversity aware multiuser scheduling algorithm is proposed. We find that noise is useful for enhancing data diversity under some conditions.
WER-BERT: Automatic WER Estimation with BERT in a Balanced Ordinal Classification Paradigm
Venue: arXiv cs.CL 2021
Year: 2021

Automatic Speech Recognition (ASR) systems are evaluated using Word Error Rate (WER), which is calculated by comparing the number of errors between the ground truth and the transcription of the ASR system. This calculation, however, requires manual transcription of the speech signal to obtain the ground truth. Since transcribing audio signals is a costly process, Automatic WER Evaluation (e-WER) methods have been developed to automatically predict the WER of a speech system by only relying on the transcription and the speech signal features. While WER is a continuous variable, previous works have shown that positing e-WER as a classification problem is more effective than regression. However, while converting to a classification setting, these approaches suffer from heavy class imbalance. In this paper, we propose a new balanced paradigm for e-WER in a classification setting. Within this paradigm, we also propose WER-BERT, a BERT based architecture with speech features for e-WER. Furthermore, we introduce a distance loss function to tackle the ordinal nature of e-WER classification. The proposed approach and paradigm are evaluated on the Librispeech dataset and a commercial (black box) ASR system, Google Cloud's Speech-to-Text API. The results and experiments demonstrate that WER-BERT establishes a new state-of-the-art in automatic WER estimation.
Neural networks behave as hash encoders: An empirical study
Venue: arXiv cs.LG 2021
Year: 2021

The input space of a neural network with ReLU-like activations is partitioned into multiple linear regions, each corresponding to a specific activation pattern of the included ReLU-like activations. We demonstrate that this partition exhibits the following encoding properties across a variety of deep learning models: (1) {\it determinism}: almost every linear region contains at most one training example. We can therefore represent almost every training example by a unique activation pattern, which is parameterized by a {\it neural code}; and (2) {\it categorization}: according to the neural code, simple algorithms, such as $K$-Means, $K$-NN, and logistic regression, can achieve fairly good performance on both training and test data. These encoding properties surprisingly suggest that {\it normal neural networks well-trained for classification behave as hash encoders without any extra efforts.} In addition, the encoding properties exhibit variability in different scenarios. {Further experiments demonstrate that {\it model size}, {\it training time}, {\it training sample size}, {\it regularization}, and {\it label noise} contribute in shaping the encoding properties, while the impacts of the first three are dominant.} We then define an {\it activation hash phase chart} to represent the space expanded by {model size}, training time, training sample size, and the encoding properties, which is divided into three canonical regions: {\it under-expressive regime}, {\it critically-expressive regime}, and {\it sufficiently-expressive regime}. The source code package is available at \url{https://github.com/LeavesLei/activation-code}.
Selective Deletion in a Blockchain
Venue: arXiv cs.CR 2021
Year: 2021

The constantly growing size of blockchains becomes a challenge with the increasing usage. Especially the storage of unwanted data in a blockchain is an issue, because it cannot be removed naturally. In order to counteract this problem, we present the first concept for the selective deletion of single entries in a blockchain. For this purpose, the general consensus algorithm is extended by the functionality of regularly creating summary blocks. Previous data of the chain are summarized and stored again in a new block, leaving out unwanted information. With a shifting marker of the Genesis Block, data can be deleted from the beginning of a blockchain. In this way, the technology of the blockchain becomes fully transactional. The concept is independent of a specific block structure, network structure, or consensus algorithm. Moreover, this functionality can be adapted to current blockchains to solve multiple problems related to scalability. This approach enables the transfer of blockchain technology to further fields of application, among others in the area of Industry 4.0 and Product Life-cycle Management.