OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid Tiled Convolutional Neural Networks for Text Sentiment Classification
Venue: arXiv cs.CL 2020
Year: 2020

The tiled convolutional neural network (tiled CNN) has been applied only to computer vision for learning invariances. We adjust its architecture to NLP to improve the extraction of the most salient features for sentiment analysis. Knowing that the major drawback of the tiled CNN in the NLP field is its inflexible filter structure, we propose a novel architecture called hybrid tiled CNN that applies a filter only on the words that appear in the similar contexts and on their neighbor words (a necessary step for preventing the loss of some n-grams). The experiments on the datasets of IMDB movie reviews and SemEval 2017 demonstrate the efficiency of the hybrid tiled CNN that performs better than both CNN and tiled CNN.
On the loss of learning capability inside an arrangement of neural networks
Venue: arXiv cs.OH 2020
Year: 2020

We analyze the loss of information and the loss of learning capability inside an arrangement of neural networks. Our method is new and based on the formulation of non-unitary Bogoliubov transformations in order to connect the information between different points of the arrangement. This can be done after expanding the activation function in a Fourier series and then assuming that its information is stored inside a Quantum scalar field.
On the Coverage Performance of Boolean-Poisson Cluster Models for Wireless Sensor Networks
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider wireless sensor networks (WSNs) with sensor nodes exhibiting clustering in their deployment. We model the coverage region of such WSNs by Boolean Poisson cluster models (BPCM) where sensors nodes' location is according to a Poisson cluster process (PCP) and each sensor has an independent sensing range around it. We consider two variants of PCP, in particular \matern and Thomas cluster process to form Boolean \matern and Thomas cluster models. We first derive the capacity functional of these models. Using the derived expressions, we compute the sensing probability of an event and compare it with sensing probability of a WSN modeled by a Boolean Poisson model where sensors are deployed according to a Poisson point process. We also derive the power required for each cluster to collect data from all of its sensors for the three considered WSNs. We show that a BPCM WSN has less power requirement in comparison to the Boolean Poisson WSN, but it suffers from lower coverage, leading to a trade-off between per-cluster power requirement and the sensing performance. A cluster process with desired clustering may provide better coverage while maintaining low power requirements.
Efficient Differentially Private $F_0$ Linear Sketching
Venue: arXiv cs.DS 2020
Year: 2020

A powerful feature of linear sketches is that from sketches of two data vectors, one can compute the sketch of the difference between the vectors. This allows us to answer fine-grained questions about the difference between two data sets. In this work, we consider how to construct sketches for weighted $F_0$, i.e., the summed weights of the elements in the data set, that are small, differentially private, and computationally efficient. Let a weight vector $w\in(0,1]^u$ be given. For $x\in\{0,1\}^u$ we are interested in estimating $\Vert x\circ w\Vert_1$ where $\circ$ is the Hadamard product (entrywise product). Building on a technique of Kushilevitz et al.~(STOC 1998), we introduce a sketch (depending on $w$) that is linear over GF(2), mapping a vector $x\in \{0,1\}^u$ to $Hx\in\{0,1\}^τ$ for a matrix $H$ sampled from a suitable distribution $\mathcal{H}$. Differential privacy is achieved by using randomized response, flipping each bit of $Hx$ with probability $p<1/2$. We show that for every choice of $0<β< 1$ and $\varepsilon=O(1)$ there exists $p<1/2$ and a distribution $\mathcal{H}$ of linear sketches of size $τ= O(\log^2(u)\varepsilon^{-2}β^{-2})$ such that: 1) For random $H\sim\mathcal{H}$ and noise vector $φ$, given $Hx + φ$ we can compute an estimate of $\Vert x\circ w\Vert_1$ that is accurate within a factor $1\pmβ$, plus additive error $O(\log(u)\varepsilon^{-2}β^{-2})$, with probability $1-1/u$, and 2) For every $H\sim\mathcal{H}$, $Hx + φ$ is $\varepsilon$-differentially private over the randomness in $φ$. The special case $w=(1,\dots,1)$ is unweighted $F_0$. Our results both improve the efficiency of existing methods for unweighted $F_0$ estimating and extend to a weighted generalization. We also give a distributed streaming implementation for estimating the size of the union between two input streams.
Essentially Optimal Sparse Polynomial Multiplication
Venue: arXiv cs.SC 2020
Year: 2020

We present a probabilistic algorithm to compute the product of two univariate sparse polynomials over a field with a number of bit operations that is quasi-linear in the size of the input and the output. Our algorithm works for any field of characteristic zero or larger than the degree. We mainly rely on sparse interpolation and on a new algorithm for verifying a sparse product that has also a quasi-linear time complexity. Using Kronecker substitution techniques we extend our result to the multivariate case.
Improving the Detection of Burnt Areas in Remote Sensing using Hyper-features Evolved by M3GP
Venue: arXiv cs.LG 2020
Year: 2020

One problem found when working with satellite images is the radiometric variations across the image and different images. Intending to improve remote sensing models for the classification of burnt areas, we set two objectives. The first is to understand the relationship between feature spaces and the predictive ability of the models, allowing us to explain the differences between learning and generalization when training and testing in different datasets. We find that training on datasets built from more than one image provides models that generalize better. These results are explained by visualizing the dispersion of values on the feature space. The second objective is to evolve hyper-features that improve the performance of different classifiers on a variety of test sets. We find the hyper-features to be beneficial, and obtain the best models with XGBoost, even if the hyper-features are optimized for a different method.
Exact and Robust Reconstructions of Integer Vectors Based on Multidimensional Chinese Remainder Theorem (MD-CRT)
Venue: arXiv cs.IT 2020
Year: 2020

The robust Chinese remainder theorem (CRT) has been recently proposed for robustly reconstructing a large nonnegative integer from erroneous remainders. It has found many applications in signal processing, including phase unwrapping and frequency estimation under sub-Nyquist sampling. Motivated by the applications in multidimensional (MD) signal processing, in this paper we propose the MD-CRT and robust MD-CRT for integer vectors. Specifically, by rephrasing the abstract CRT for rings in number-theoretic terms, we first derive the MD-CRT for integer vectors with respect to a general set of integer matrix moduli, which provides an algorithm to uniquely reconstruct an integer vector from its remainders, if it is in the fundamental parallelepiped of the lattice generated by a least common right multiple of all the moduli. For some special forms of moduli, we present explicit reconstruction formulae. Moreover, we derive the robust MD-CRT for integer vectors when the remaining integer matrices of all the moduli left divided by their greatest common left divisor (gcld) are pairwise commutative and coprime. Two different reconstruction algorithms are proposed, and accordingly, two different conditions on the remainder error bound for the reconstruction robustness are obtained, which are related to a quarter of the minimum distance of the lattice generated by the gcld of all the moduli or the Smith normal form of the gcld.
Towards Evaluating Gaussian Blurring in Perceptual Hashing as a Facial Image Filter
Venue: arXiv cs.CV 2020
Year: 2020

With the growth in social media, there is a huge amount of images of faces available on the internet. Often, people use other people's pictures on their own profile. Perceptual hashing is often used to detect whether two images are identical. Therefore, it can be used to detect whether people are misusing others' pictures. In perceptual hashing, a hash is calculated for a given image, and a new test image is mapped to one of the existing hashes if duplicate features are present. Therefore, it can be used as an image filter to flag banned image content or adversarial attacks --which are modifications that are made on purpose to deceive the filter-- even though the content might be changed to deceive the filters. For this reason, it is critical for perceptual hashing to be robust enough to take transformations such as resizing, cropping, and slight pixel modifications into account. In this paper, we would like to propose to experiment with effect of gaussian blurring in perceptual hashing for detecting misuse of personal images specifically for face images. We hypothesize that use of gaussian blurring on the image before calculating its hash will increase the accuracy of our filter that detects adversarial attacks which consist of image cropping, adding text annotation, and image rotation.
ResilientDB: Global Scale Resilient Blockchain Fabric
Venue: arXiv cs.DB 2020
Year: 2020

Recent developments in blockchain technology have inspired innovative new designs in resilient distributed and database systems. At their core, these blockchain applications typically use Byzantine fault-tolerant consensus protocols to maintain a common state across all replicas, even if some replicas are faulty or malicious. Unfortunately, existing consensus protocols are not designed to deal with geo-scale deployments in which many replicas spread across a geographically large area participate in consensus. To address this, we present the Geo-Scale Byzantine FaultTolerant consensus protocol (GeoBFT). GeoBFT is designed for excellent scalability by using a topological-aware grouping of replicas in local clusters, by introducing parallelization of consensus at the local level, and by minimizing communication between clusters. To validate our vision of high-performance geo-scale resilient distributed systems, we implement GeoBFT in our efficient ResilientDB permissioned blockchain fabric. We show that GeoBFT is not only sound and provides great scalability, but also outperforms state-of-the-art consensus protocols by a factor of six in geo-scale deployments.
Solving the Joint Order Batching and Picker Routing Problem for Large Instances
Venue: arXiv cs.DS 2020
Year: 2020

In this work, we investigate the problem of order batching and picker routing in warehouse storage areas. These problems are known to be capital and labour intensive, and often contribute to a sizable fraction of warehouse operating costs. Here, we consider the case of online grocery shopping where orders may consist of dozens of items. We present the problem introduced and tackle the issue of solving the problem heuristically with proposed methods of solving that utilize batching and routing heuristics. Instances with up to 50 orders were solved heuristically in large simulated warehouse instances consisting of 8 to 30 aisles, with 1 to 4 blocks. The proposed methods were shown to have relatively short computation times as compared to optimally solving the problem in. In particular, we showed that a proposed method which utilizes an optimal solver for routing yielded poorer results than methods that utilize routing heuristics.
Analysis and Optimization of an Intelligent Reflecting Surface-assisted System with Interference
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we study an intelligent reflecting surface (IRS)-assisted system where a multi-antenna base station (BS) serves a single-antenna user with the help of a multi-element IRS in the presence of interference generated by a multi-antenna BS serving its own single-antenna user. The signal and interference links via the IRS are modeled with Rician fading. To reduce phase adjustment cost, we adopt quasi-static phase shift design where the phase shifts do not change with the instantaneous channel state information (CSI). We investigate two cases of CSI at the BSs, namely, the instantaneous CSI case and the statistical CSI case, and apply Maximum Ratio Transmission (MRT) based on the complete CSI and the CSI of the Line-of-sight (LoS) components, respectively. Different costs on channel estimation and beamforming adjustment are incurred in the two CSI cases. First, we obtain a tractable expression of the average rate in the instantaneous CSI case and a tractable expression of the ergodic rate in the statistical CSI case. We also provide sufficient conditions for the average rate in the instantaneous CSI case to surpass the ergodic rate in the statistical CSI case, at any phase shifts. Then, we maximize the average rate and ergodic rate, both with respect to the phase shifts, leading to two non-convex optimization problems. For each problem, we obtain a globally optimal solution under certain system parameters, and propose an iterative algorithm based on parallel coordinate descent (PCD) to obtain a stationary point under arbitrary system parameters. Next, in each CSI case, we provide sufficient conditions under which the optimal quasi-static phase shift design is beneficial, compared to the system without IRS. Finally, we numerically verify the analytical results and demonstrate notable gains of the proposal solutions over existing ones.
Web Table Extraction, Retrieval and Augmentation: A Survey
Venue: arXiv cs.IR 2020
Year: 2020

Tables are a powerful and popular tool for organizing and manipulating data. A vast number of tables can be found on the Web, which represents a valuable knowledge resource. The objective of this survey is to synthesize and present two decades of research on web tables. In particular, we organize existing literature into six main categories of information access tasks: table extraction, table interpretation, table search, question answering, knowledge base augmentation, and table augmentation. For each of these tasks, we identify and describe seminal approaches, present relevant resources, and point out interdependencies among the different tasks.
Learning to Detect Malicious Clients for Robust Federated Learning
Venue: arXiv cs.LG 2020
Year: 2020

Federated learning systems are vulnerable to attacks from malicious clients. As the central server in the system cannot govern the behaviors of the clients, a rogue client may initiate an attack by sending malicious model updates to the server, so as to degrade the learning performance or enforce targeted model poisoning attacks (a.k.a. backdoor attacks). Therefore, timely detecting these malicious model updates and the underlying attackers becomes critically important. In this work, we propose a new framework for robust federated learning where the central server learns to detect and remove the malicious model updates using a powerful detection model, leading to targeted defense. We evaluate our solution in both image classification and sentiment analysis tasks with a variety of machine learning models. Experimental results show that our solution ensures robust federated learning that is resilient to both the Byzantine attacks and the targeted model poisoning attacks.
Variational Item Response Theory: Fast, Accurate, and Expressive
Venue: arXiv cs.LG 2020
Year: 2020

Item Response Theory (IRT) is a ubiquitous model for understanding humans based on their responses to questions, used in fields as diverse as education, medicine and psychology. Large modern datasets offer opportunities to capture more nuances in human behavior, potentially improving test scoring and better informing public policy. Yet larger datasets pose a difficult speed / accuracy challenge to contemporary algorithms for fitting IRT models. We introduce a variational Bayesian inference algorithm for IRT, and show that it is fast and scaleable without sacrificing accuracy. Using this inference approach we then extend classic IRT with expressive Bayesian models of responses. Applying this method to five large-scale item response datasets from cognitive science and education yields higher log likelihoods and improvements in imputing missing data. The algorithm implementation is open-source, and easily usable.
Fast 3D Indoor Scene Synthesis with Discrete and Exact Layout Pattern Extraction
Venue: arXiv cs.GR 2020
Year: 2020

We present a fast framework for indoor scene synthesis, given a room geometry and a list of objects with learnt priors. Unlike existing data-driven solutions, which often extract priors by co-occurrence analysis and statistical model fitting, our method measures the strengths of spatial relations by tests for complete spatial randomness (CSR), and extracts complex priors based on samples with the ability to accurately represent discrete layout patterns. With the extracted priors, our method achieves both acceleration and plausibility by partitioning input objects into disjoint groups, followed by layout optimization based on the Hausdorff metric. Extensive experiments show that our framework is capable of measuring more reasonable relations among objects and simultaneously generating varied arrangements in seconds.
An Experimental Study of Formula Embeddings for Automated Theorem Proving in First-Order Logic
Venue: arXiv cs.AI 2020
Year: 2020

Automated theorem proving in first-order logic is an active research area which is successfully supported by machine learning. While there have been various proposals for encoding logical formulas into numerical vectors -- from simple strings to more involved graph-based embeddings -- little is known about how these different encodings compare. In this paper, we study and experimentally compare pattern-based embeddings that are applied in current systems with popular graph-based encodings, most of which have not been considered in the theorem proving context before. Our experiments show that the advantages of simpler encoding schemes in terms of runtime are outdone by more complex graph-based embeddings, which yield more efficient search strategies and simpler proofs. To support this, we present a detailed analysis across several dimensions of theorem prover performance beyond just proof completion rate, thus providing empirical evidence to help guide future research on neural-guided theorem proving towards the most promising directions.
Don't Forget to Lock the Front Door! Inferring the Deployment of Source Address Validation of Inbound Traffic
Venue: arXiv cs.NI 2020
Year: 2020

This paper concerns the problem of the absence of ingress filtering at the network edge, one of the main causes of important network security issues. Numerous network operators do not deploy the best current practice - Source Address Validation (SAV) that aims at mitigating these issues. We perform the first Internet-wide active measurement study to enumerate networks not filtering incoming packets by their source address. The measurement method consists of identifying closed and open DNS resolvers handling requests coming from the outside of the network with the source address from the range assigned inside the network under the test. The proposed method provides the most complete picture of the inbound SAV deployment state at network providers. We reveal that 32 673 Autonomous Systems (ASes) and 197 641 Border Gateway Protocol (BGP) prefixes are vulnerable to spoofing of inbound traffic. Finally, using the data from the Spoofer project and performing an open resolver scan, we compare the filtering policies in both directions.
Permissioned Blockchain-Based Security for SDN in IoT Cloud Networks
Venue: arXiv cs.CR 2020
Year: 2020

The advancement in cloud networks has enabled connectivity of both traditional networked elements and new devices from all walks of life, thereby forming the Internet of Things (IoT). In an IoT setting, improving and scaling network components as well as reducing cost is essential to sustain exponential growth. In this domain, software-defined networking (SDN) is revolutionizing the network infrastructure with a new paradigm. SDN splits the control/routing logic from the data transfer/forwarding. This splitting causes many issues in SDN, such as vulnerabilities of DDoS attacks. Many solutions (including blockchain based) have been proposed to overcome these problems. In this work, we offer a blockchain-based solution that is provided in redundant SDN (load-balanced) to service millions of IoT devices. Blockchain is considered as tamper-proof and impossible to corrupt due to the replication of the ledger and consensus for verification and addition to the ledger. Therefore, it is a perfect fit for SDN in IoT Networks. Blockchain technology provides everyone with a working proof of decentralized trust. The experimental results show gain and efficiency with respect to the accuracy, update process, and bandwidth utilization.
Safe Exploration for Optimizing Contextual Bandits
Venue: arXiv cs.IR 2020
Year: 2020

Contextual bandit problems are a natural fit for many information retrieval tasks, such as learning to rank, text classification, recommendation, etc. However, existing learning methods for contextual bandit problems have one of two drawbacks: they either do not explore the space of all possible document rankings (i.e., actions) and, thus, may miss the optimal ranking, or they present suboptimal rankings to a user and, thus, may harm the user experience. We introduce a new learning method for contextual bandit problems, Safe Exploration Algorithm (SEA), which overcomes the above drawbacks. SEA starts by using a baseline (or production) ranking system (i.e., policy), which does not harm the user experience and, thus, is safe to execute, but has suboptimal performance and, thus, needs to be improved. Then SEA uses counterfactual learning to learn a new policy based on the behavior of the baseline policy. SEA also uses high-confidence off-policy evaluation to estimate the performance of the newly learned policy. Once the performance of the newly learned policy is at least as good as the performance of the baseline policy, SEA starts using the new policy to execute new actions, allowing it to actively explore favorable regions of the action space. This way, SEA never performs worse than the baseline policy and, thus, does not harm the user experience, while still exploring the action space and, thus, being able to find an optimal policy. Our experiments using text classification and document retrieval confirm the above by comparing SEA (and a boundless variant called BSEA) to online and offline learning methods for contextual bandit problems.
Active Learning for Identification of Linear Dynamical Systems
Venue: arXiv cs.LG 2020
Year: 2020

We propose an algorithm to actively estimate the parameters of a linear dynamical system. Given complete control over the system's input, our algorithm adaptively chooses the inputs to accelerate estimation. We show a finite time bound quantifying the estimation rate our algorithm attains and prove matching upper and lower bounds which guarantee its asymptotic optimality, up to constants. In addition, we show that this optimal rate is unattainable when using Gaussian noise to excite the system, even with optimally tuned covariance, and analyze several examples where our algorithm provably improves over rates obtained by playing noise. Our analysis critically relies on a novel result quantifying the error in estimating the parameters of a dynamical system when arbitrary periodic inputs are being played. We conclude with numerical examples that illustrate the effectiveness of our algorithm in practice.