OpenRaiser/Intern-Atlas huggingface dataset:
Auction Mechanisms in Cloud/Fog Computing Resource Allocation for Public Blockchain Networks
Venue: arXiv cs.GT 2020
Year: 2020

As an emerging decentralized secure data management platform, blockchain has gained much popularity recently. To maintain a canonical state of blockchain data record, proof-of-work based consensus protocols provide the nodes, referred to as miners, in the network with incentives for confirming new block of transactions through a process of "block mining" by solving a cryptographic puzzle. Under the circumstance of limited local computing resources, e.g., mobile devices, it is natural for rational miners, i.e., consensus nodes, to offload computational tasks for proof of work to the cloud/fog computing servers. Therefore, we focus on the trading between the cloud/fog computing service provider and miners, and propose an auction-based market model for efficient computing resource allocation. In particular, we consider a proof-of-work based blockchain network. Due to the competition among miners in the blockchain network, the allocative externalities are particularly taken into account when designing the auction mechanisms. Specifically, we consider two bidding schemes: the constant-demand scheme where each miner bids for a fixed quantity of resources, and the multi-demand scheme where the miners can submit their preferable demands and bids. For the constant-demand bidding scheme, we propose an auction mechanism that achieves optimal social welfare. In the multi-demand bidding scheme, the social welfare maximization problem is NP-hard. Therefore, we design an approximate algorithm which guarantees the truthfulness, individual rationality and computational efficiency. Through extensive simulations, we show that our proposed auction mechanisms with the two bidding schemes can efficiently maximize the social welfare of the blockchain network and provide effective strategies for the cloud/fog computing service provider.
Local Learning with Deep and Handcrafted Features for Facial Expression Recognition
Venue: arXiv cs.CV 2020
Year: 2020

We present an approach that combines automatic features learned by convolutional neural networks (CNN) and handcrafted features computed by the bag-of-visual-words (BOVW) model in order to achieve state-of-the-art results in facial expression recognition. To obtain automatic features, we experiment with multiple CNN architectures, pre-trained models and training procedures, e.g. Dense-Sparse-Dense. After fusing the two types of features, we employ a local learning framework to predict the class label for each test image. The local learning framework is based on three steps. First, a k-nearest neighbors model is applied in order to select the nearest training samples for an input test image. Second, a one-versus-all Support Vector Machines (SVM) classifier is trained on the selected training samples. Finally, the SVM classifier is used to predict the class label only for the test image it was trained for. Although we have used local learning in combination with handcrafted features in our previous work, to the best of our knowledge, local learning has never been employed in combination with deep features. The experiments on the 2013 Facial Expression Recognition (FER) Challenge data set, the FER+ data set and the AffectNet data set demonstrate that our approach achieves state-of-the-art results. With a top accuracy of 75.42% on FER 2013, 87.76% on the FER+, 59.58% on AffectNet 8-way classification and 63.31% on AffectNet 7-way classification, we surpass the state-of-the-art methods by more than 1% on all data sets.
Comparative Analysis and Framework Evaluating Web Single Sign-On Systems
Venue: arXiv cs.CR 2020
Year: 2020

We perform a comprehensive analysis and comparison of 14 web single sign-on (SSO) systems proposed and/or deployed over the last decade, including federated identity and credential/password management schemes. We identify common design properties and use them to develop a taxonomy for SSO schemes, highlighting the associated trade-offs in benefits (positive attributes) offered. We develop a framework to evaluate the schemes, in which we identify 14 security, usability, deployability, and privacy benefits. We also discuss how differences in priorities between users, service providers (SPs), and identity providers (IdPs) impact the design and deployment of SSO schemes.
PSGAN: A Generative Adversarial Network for Remote Sensing Image Pan-Sharpening
Venue: arXiv cs.CV 2020
Year: 2020

This paper addresses the problem of remote sensing image pan-sharpening from the perspective of generative adversarial learning. We propose a novel deep neural network based method named PSGAN. To the best of our knowledge, this is one of the first attempts at producing high-quality pan-sharpened images with GANs. The PSGAN consists of two components: a generative network (i.e., generator) and a discriminative network (i.e., discriminator). The generator is designed to accept panchromatic (PAN) and multispectral (MS) images as inputs and maps them to the desired high-resolution (HR) MS images and the discriminator implements the adversarial training strategy for generating higher fidelity pan-sharpened images. In this paper, we evaluate several architectures and designs, namely two-stream input, stacking input, batch normalization layer, and attention mechanism to find the optimal solution for pan-sharpening. Extensive experiments on QuickBird, GaoFen-2, and WorldView-2 satellite images demonstrate that the proposed PSGANs not only are effective in generating high-quality HR MS images and superior to state-of-the-art methods and also generalize well to full-scale images.
Necessary and Sufficient Budgets in Information Source Finding with Querying: Adaptivity Gap
Venue: arXiv cs.SI 2020
Year: 2020

In this paper, we study a problem of detecting the source of diffused information by querying individuals, given a sample snapshot of the information diffusion graph, where two queries are asked: {\em (i)} whether the respondent is the source or not, and {\em (ii)} if not, which neighbor spreads the information to the respondent. We consider the case when respondents may not always be truthful and some cost is taken for each query. Our goal is to quantify the necessary and sufficient budgets to achieve the detection probability $1-δ$ for any given $0<δ<1.$ To this end, we study two types of algorithms: adaptive and non-adaptive ones, each of which corresponds to whether we adaptively select the next respondents based on the answers of the previous respondents or not. We first provide the information theoretic lower bounds for the necessary budgets in both algorithm types. In terms of the sufficient budgets, we propose two practical estimation algorithms, each of non-adaptive and adaptive types, and for each algorithm, we quantitatively analyze the budget which ensures $1-δ$ detection accuracy. This theoretical analysis not only quantifies the budgets needed by practical estimation algorithms achieving a given target detection accuracy in finding the diffusion source, but also enables us to quantitatively characterize the amount of extra budget required in non-adaptive type of estimation, refereed to as {\em adaptivity gap}. We validate our theoretical findings over synthetic and real-world social network topologies.
Convex Programming Based Spectral Clustering
Venue: arXiv cs.LG 2020
Year: 2020

Clustering is a fundamental task in data analysis, and spectral clustering has been recognized as a promising approach to it. Given a graph describing the relationship between data, spectral clustering explores the underlying cluster structure in two stages. The first stage embeds the nodes of the graph in real space, and the second stage groups the embedded nodes into several clusters. The use of the $k$-means method in the grouping stage is currently standard practice. We present a spectral clustering algorithm that uses convex programming in the grouping stage and study how well it works. This algorithm is designed based on the following observation. If a graph is well-clustered, then the nodes with the largest degree in each cluster can be found by computing an enclosing ellipsoid of the nodes embedded in real space, and the clusters can be identified by using those nodes. We show that, for well-clustered graphs, the algorithm can find clusters of nodes with minimal conductance. We also give an experimental assessment of the algorithm's performance.
On the List Decodability of Insertions and Deletions
Venue: arXiv cs.IT 2020
Year: 2020

In this work, we study the problem of list decoding of insertions and deletions. We present a Johnson-type upper bound on the maximum list size. The bound is meaningful only when insertions occur. Our bound implies that there are binary codes of rate $Ω(1)$ that are list-decodable from a $0.707$-fraction of insertions. For any $τ_\mathsf{I} \geq 0$ and $τ_\mathsf{D} \in [0,1)$, there exist $q$-ary codes of rate $Ω(1)$ that are list-decodable from a $τ_\mathsf{I}$-fraction of insertions and $τ_\mathsf{D}$-fraction of deletions, where $q$ depends only on $τ_\mathsf{I}$ and $τ_\mathsf{D}$. We also provide efficient encoding and decoding algorithms for list-decoding from $τ_\mathsf{I}$-fraction of insertions and $τ_\mathsf{D}$-fraction of deletions for any $τ_\mathsf{I} \geq 0$ and $τ_\mathsf{D} \in [0,1)$. Based on the Johnson-type bound, we derive a Plotkin-type upper bound on the code size in the Levenshtein metric.
NEWMA: a new method for scalable model-free online change-point detection
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of detecting abrupt changes in the distribution of a multi-dimensional time series, with limited computing power and memory. In this paper, we propose a new, simple method for model-free online change-point detection that relies only on fast and light recursive statistics, inspired by the classical Exponential Weighted Moving Average algorithm (EWMA). The proposed idea is to compute two EWMA statistics on the stream of data with different forgetting factors, and to compare them. By doing so, we show that we implicitly compare recent samples with older ones, without the need to explicitly store them. Additionally, we leverage Random Features (RFs) to efficiently use the Maximum Mean Discrepancy as a distance between distributions, furthermore exploiting recent optical hardware to compute high-dimensional RFs in near constant time. We show that our method is significantly faster than usual non-parametric methods for a given accuracy.
Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning
Venue: arXiv cs.LG 2020
Year: 2020

Understanding the convergence performance of asynchronous stochastic gradient descent method (Async-SGD) has received increasing attention in recent years due to their foundational role in machine learning. To date, however, most of the existing works are restricted to either bounded gradient delays or convex settings. In this paper, we focus on Async-SGD and its variant Async-SGDI (which uses increasing batch size) for non-convex optimization problems with unbounded gradient delays. We prove $o(1/\sqrt{k})$ convergence rate for Async-SGD and $o(1/k)$ for Async-SGDI. Also, a unifying sufficient condition for Async-SGD's convergence is established, which includes two major gradient delay models in the literature as special cases and yields a new delay model not considered thus far.
Stable Super-Resolution of Images: A Theoretical Study
Venue: arXiv cs.IT 2020
Year: 2020

We study the ubiquitous super-resolution problem, in which one aims at localizing positive point sources in an image, blurred by the point spread function of the imaging device. To recover the point sources, we propose to solve a convex feasibility program, which simply finds a nonnegative Borel measure that agrees with the observations collected by the imaging device. In the absence of imaging noise, we show that solving this convex program uniquely retrieves the point sources, provided that the imaging device collects enough observations. This result holds true if the point spread function of the imaging device can be decomposed into horizontal and vertical components, and if the translations of these components form a Chebyshev system, i.e., a system of continuous functions that loosely behave like algebraic polynomials. Building upon recent results for one-dimensional signals [1], we prove that this super-resolution algorithm is stable, in the generalized Wasserstein metric, to model mismatch (i.e., when the image is not sparse) and to additive imaging noise. In particular, the recovery error depends on the noise level and how well the image can be approximated with well-separated point sources. As an example, we verify these claims for the important case of a Gaussian point spread function. The proofs rely on the construction of novel interpolating polynomials---which are the main technical contribution of this paper---and partially resolve the question raised in [2] about the extension of the standard machinery to higher dimensions.
Combining Modified Weibull Distribution Models for Power System Reliability Forecast
Venue: arXiv cs.CE 2020
Year: 2020

In recent years, under deregulated environment, electric utility companies have been encouraged to ensure maximum system reliability through the employment of cost-effective long-term asset management strategies. To help achieve this goal, this research proposes a novel statistical approach to forecast power system asset population reliability. It uniquely combines a few modified Weibull distribution models to build a robust joint forecast model. At first, the classic age based Weibull distribution model is reviewed. In comparison, this paper proposes a few modified Weibull distribution models to incorporate special considerations for power system applications. Furthermore, this paper proposes a novel method to effectively measure the forecast accuracy and evaluate different Weibull distribution models. As a result, for a specific asset population, the suitable model(s) can be selected. More importantly, if more than one suitable model exists, these models can be mathematically combined as a joint forecast model to forecast future asset reliability. Finally, the proposed methods were applied to a Canadian utility company for the reliability forecast of electromechanical relays and the results are discussed in detail to demonstrate the practicality and usefulness of this research.
A note on belief structures and S-approximation spaces
Venue: arXiv cs.AI 2020
Year: 2020

We study relations between evidence theory and S-approximation spaces. Both theories have their roots in the analysis of Dempster's multivalued mappings and lower and upper probabilities and have close relations to rough sets. We show that an S-approximation space, satisfying a monotonicity condition, can induce a natural belief structure which is a fundamental block in evidence theory. We also demonstrate that one can induce a natural belief structure on one set, given a belief structure on another set if those sets are related by a partial monotone S-approximation space.
Discriminator Feature-based Inference by Recycling the Discriminator of GANs
Venue: arXiv cs.CV 2020
Year: 2020

Generative adversarial networks (GANs)successfully generate high quality data by learning amapping from a latent vector to the data. Various studies assert that the latent space of a GAN is semanticallymeaningful and can be utilized for advanced data analysis and manipulation. To analyze the real data in thelatent space of a GAN, it is necessary to build an inference mapping from the data to the latent vector. Thispaper proposes an effective algorithm to accurately infer the latent vector by utilizing GAN discriminator features. Our primary goal is to increase inference mappingaccuracy with minimal training overhead. Furthermore,using the proposed algorithm, we suggest a conditionalimage generation algorithm, namely a spatially conditioned GAN. Extensive evaluations confirmed that theproposed inference algorithm achieved more semantically accurate inference mapping than existing methodsand can be successfully applied to advanced conditionalimage generation tasks.
AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Recent studies have shown that adversarial examples in state-of-the-art image classifiers trained by deep neural networks (DNN) can be easily generated when the target model is transparent to an attacker, known as the white-box setting. However, when attacking a deployed machine learning service, one can only acquire the input-output correspondences of the target model; this is the so-called black-box attack setting. The major drawback of existing black-box attacks is the need for excessive model queries, which may give a false sense of model robustness due to inefficient query designs. To bridge this gap, we propose a generic framework for query-efficient black-box attacks. Our framework, AutoZOOM, which is short for Autoencoder-based Zeroth Order Optimization Method, has two novel building blocks towards efficient black-box attacks: (i) an adaptive random gradient estimation strategy to balance query counts and distortion, and (ii) an autoencoder that is either trained offline with unlabeled data or a bilinear resizing operation for attack acceleration. Experimental results suggest that, by applying AutoZOOM to a state-of-the-art black-box attack (ZOO), a significant reduction in model queries can be achieved without sacrificing the attack success rate and the visual quality of the resulting adversarial examples. In particular, when compared to the standard ZOO method, AutoZOOM can consistently reduce the mean query counts in finding successful adversarial examples (or reaching the same distortion level) by at least 93% on MNIST, CIFAR-10 and ImageNet datasets, leading to novel insights on adversarial robustness.
NLP-assisted software testing: A systematic mapping of the literature
Venue: arXiv cs.SE 2020
Year: 2020

Context: To reduce manual effort of extracting test cases from natural-language requirements, many approaches based on Natural Language Processing (NLP) have been proposed in the literature. Given the large amount of approaches in this area, and since many practitioners are eager to utilize such techniques, it is important to synthesize and provide an overview of the state-of-the-art in this area. Objective: Our objective is to summarize the state-of-the-art in NLP-assisted software testing which could benefit practitioners to potentially utilize those NLP-based techniques. Moreover, this can benefit researchers in providing an overview of the research landscape. Method: To address the above need, we conducted a survey in the form of a systematic literature mapping (classification). After compiling an initial pool of 95 papers, we conducted a systematic voting, and our final pool included 67 technical papers. Results: This review paper provides an overview of the contribution types presented in the papers, types of NLP approaches used to assist software testing, types of required input requirements, and a review of tool support in this area. Some key results we have detected are: (1) only four of the 38 tools (11%) presented in the papers are available for download; (2) a larger ratio of the papers (30 of 67) provided a shallow exposure to the NLP aspects (almost no details). Conclusion: This paper would benefit both practitioners and researchers by serving as an "index" to the body of knowledge in this area. The results could help practitioners utilizing the existing NLP-based techniques; this in turn reduces the cost of test-case design and decreases the amount of human resources spent on test activities. After sharing this review with some of our industrial collaborators, initial insights show that this review can indeed be useful and beneficial to practitioners.
Efficient Full-Matrix Adaptive Regularization
Venue: arXiv cs.LG 2020
Year: 2020

Adaptive regularization methods pre-multiply a descent direction by a preconditioning matrix. Due to the large number of parameters of machine learning problems, full-matrix preconditioning methods are prohibitively expensive. We show how to modify full-matrix adaptive regularization in order to make it practical and effective. We also provide a novel theoretical analysis for adaptive regularization in non-convex optimization settings. The core of our algorithm, termed GGT, consists of the efficient computation of the inverse square root of a low-rank matrix. Our preliminary experiments show improved iteration-wise convergence rates across synthetic tasks and standard deep learning benchmarks, and that the more carefully-preconditioned steps sometimes lead to a better solution.
The Age of Information in Networks: Moments, Distributions, and Sampling
Venue: arXiv cs.IT 2020
Year: 2020

A source provides status updates to monitors through a network with state defined by a continuous-time finite Markov chain. An age of information (AoI) metric is used to characterize timeliness by the vector of ages tracked by the monitors. Based on a stochastic hybrid systems (SHS) approach, first order linear differential equations are derived for the temporal evolution of both the moments and the moment generating function (MGF) of the age vector components. It is shown that the existence of a non-negative fixed point for the first moment is sufficient to guarantee convergence of all higher order moments as well as a region of convergence for the stationary MGF vector of the age. The stationary MGF vector is then found for the age on a line network of preemptive memoryless servers. From this MGF, it is found that the age at a node is identical in distribution to the sum of independent exponential service times. This observation is then generalized to linear status sampling networks in which each node receives samples of the update process at each preceding node according to a renewal point process. For each node in the line, the age is shown to be identical in distribution to a sum of independent renewal process age random variables.
Are All Languages Equally Hard to Language-Model?
Venue: arXiv cs.CL 2020
Year: 2020

For general modeling methods applied to diverse languages, a natural question is: how well should we expect our models to work on languages with differing typological profiles? In this work, we develop an evaluation framework for fair cross-linguistic comparison of language models, using translated text so that all models are asked to predict approximately the same information. We then conduct a study on 21 languages, demonstrating that in some languages, the textual expression of the information is harder to predict with both $n$-gram and LSTM language models. We show complex inflectional morphology to be a cause of performance differences among languages.
A Structured Variational Autoencoder for Contextual Morphological Inflection
Venue: arXiv cs.CL 2020
Year: 2020

Statistical morphological inflectors are typically trained on fully supervised, type-level data. One remaining open research question is the following: How can we effectively exploit raw, token-level data to improve their performance? To this end, we introduce a novel generative latent-variable model for the semi-supervised learning of inflection generation. To enable posterior inference over the latent variables, we derive an efficient variational inference procedure based on the wake-sleep algorithm. We experiment on 23 languages, using the Universal Dependencies corpora in a simulated low-resource setting, and find improvements of over 10% absolute accuracy in some cases.