OpenRaiser/Intern-Atlas huggingface dataset:
9.6 Million Links in Source Code Comments: Purpose, Evolution, and Decay
Venue: arXiv cs.SE 2019
Year: 2019

Links are an essential feature of the World Wide Web, and source code repositories are no exception. However, despite their many undisputed benefits, links can suffer from decay, insufficient versioning, and lack of bidirectional traceability. In this paper, we investigate the role of links contained in source code comments from these perspectives. We conducted a large-scale study of around 9.6 million links to establish their prevalence, and we used a mixed-methods approach to identify the links' targets, purposes, decay, and evolutionary aspects. We found that links are prevalent in source code repositories, that licenses, software homepages, and specifications are common types of link targets, and that links are often included to provide metadata or attribution. Links are rarely updated, but many link targets evolve. Almost 10% of the links included in source code comments are dead. We then submitted a batch of link-fixing pull requests to open source software repositories, resulting in most of our fixes being merged successfully. Our findings indicate that links in source code comments can indeed be fragile, and our work opens up avenues for future work to address these problems.
Probabilistic Forwarding of Coded Packets on Networks
Venue: arXiv cs.IT 2019
Year: 2019

We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has $k$ data packets to broadcast, and it suffices that a large fraction of the network nodes receives the broadcast. The source encodes the $k$ data packets into $n \ge k$ coded packets using a maximum distance separable (MDS) code, and transmits them to its one-hop neighbours. Every other node in the network follows a probabilistic forwarding protocol, in which it forwards a previously unreceived packet to all its neighbours with a certain probability $p$. A "near-broadcast" is when the expected fraction of nodes that receive at least $k$ of the $n$ coded packets is close to $1$. The forwarding probability $p$ is chosen so as to minimize the expected total number of transmissions needed for a near-broadcast. In this paper, we analyze the probabilistic forwarding of coded packets on two specific network topologies: binary trees and square grids. For trees, our analysis shows that for fixed $k$, the expected total number of transmissions increases with $n$. On the other hand, on grids, we use ideas from percolation theory to show that a judicious choice of $n$ will significantly reduce the expected total number of transmissions needed for a near-broadcast.
Learning Continuous Face Age Progression: A Pyramid of GANs
Venue: arXiv cs.CV 2019
Year: 2019

The two underlying requirements of face age progression, i.e. aging accuracy and identity permanence, are not well studied in the literature. This paper presents a novel generative adversarial network based approach to address the issues in a coupled manner. It separately models the constraints for the intrinsic subject-specific characteristics and the age-specific facial changes with respect to the elapsed time, ensuring that the generated faces present desired aging effects while simultaneously keeping personalized properties stable. To ensure photo-realistic facial details, high-level age-specific features conveyed by the synthesized face are estimated by a pyramidal adversarial discriminator at multiple scales, which simulates the aging effects with finer details. Further, an adversarial learning scheme is introduced to simultaneously train a single generator and multiple parallel discriminators, resulting in smooth continuous face aging sequences. The proposed method is applicable even in the presence of variations in pose, expression, makeup, etc., achieving remarkably vivid aging effects. Quantitative evaluations by a COTS face recognition system demonstrate that the target age distributions are accurately recovered, and 99.88% and 99.98% age progressed faces can be correctly verified at 0.001% FAR after age transformations of approximately 28 and 23 years elapsed time on the MORPH and CACD databases, respectively. Both visual and quantitative assessments show that the approach advances the state-of-the-art.
Unsupervised Learning of Neural Networks to Explain Neural Networks (extended abstract)
Venue: arXiv cs.LG 2019
Year: 2019

This paper presents an unsupervised method to learn a neural network, namely an explainer, to interpret a pre-trained convolutional neural network (CNN), i.e., the explainer uses interpretable visual concepts to explain features in middle conv-layers of a CNN. Given feature maps of a conv-layer of the CNN, the explainer performs like an auto-encoder, which decomposes the feature maps into object-part features. The object-part features are learned to reconstruct CNN features without much loss of information. We can consider the disentangled representations of object parts a paraphrase of CNN features, which help people understand the knowledge encoded by the CNN. More crucially, we learn the explainer via knowledge distillation without using any annotations of object parts or textures for supervision. In experiments, our method was widely used to interpret features of different benchmark CNNs, and explainers significantly boosted the feature interpretability without hurting the discrimination power of the CNNs.
Managing Popularity Bias in Recommender Systems with Personalized Re-ranking
Venue: arXiv cs.IR 2019
Year: 2019

Many recommender systems suffer from popularity bias: popular items are recommended frequently while less popular, niche products, are recommended rarely or not at all. However, recommending the ignored products in the `long tail' is critical for businesses as they are less likely to be discovered. In this paper, we introduce a personalized diversification re-ranking approach to increase the representation of less popular items in recommendations while maintaining acceptable recommendation accuracy. Our approach is a post-processing step that can be applied to the output of any recommender system. We show that our approach is capable of managing popularity bias more effectively, compared with an existing method based on regularization. We also examine both new and existing metrics to measure the coverage of long-tail items in the recommendation.
Faster parameterized algorithm for Cluster Vertex Deletion
Venue: arXiv cs.DS 2019
Year: 2019

In the Cluster Vertex Deletion problem the input is a graph $G$ and an integer $k$. The goal is to decide whether there is a set of vertices $S$ of size at most $k$ such that the deletion of the vertices of $S$ from $G$ results a graph in which every connected component is a clique. We give an algorithm for Cluster Vertex Deletion whose running time is $O^*(1.811^k)$.
A Concentration of Measure Approach to Database De-anonymization
Venue: arXiv cs.DB 2019
Year: 2019

In this paper, matching of correlated high-dimensional databases is investigated. A stochastic database model is considered where the correlation among the database entries is governed by an arbitrary joint distribution. Concentration of measure theorems such as typicality and laws of large numbers are used to develop a database matching scheme and derive necessary conditions for successful matching. Furthermore, it is shown that these conditions are tight through a converse result which characterizes a set of distributions on the database entries for which reliable matching is not possible. The necessary and sufficient conditions for reliable matching are evaluated in the cases when the database entries are independent and identically distributed as well as under Markovian database models.
Cascaded Coded Distributed Computing on Heterogeneous Networks
Venue: arXiv cs.IT 2019
Year: 2019

Coded distributed computing (CDC) introduced by Li et al. in 2015 offers an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce. For the more general cascaded CDC, Map computations are repeated at $r$ nodes to significantly reduce the communication load among nodes tasked with computing $Q$ Reduce functions $s$ times. While an achievable cascaded CDC scheme was proposed, it only operates on homogeneous networks, where the storage, computation load and communication load of each computing node is the same. In this paper, we address this limitation by proposing a novel combinatorial design which operates on heterogeneous networks where nodes have varying storage and computing capabilities. We provide an analytical characterization of the computation-communication trade-off and show that it is optimal within a constant factor and could outperform the state-of-the-art homogeneous schemes.
Enhancing MapReduce Fault Recovery Through Binocular Speculation
Venue: arXiv cs.DC 2019
Year: 2019

MapReduce speculation plays an important role in finding potential task stragglers and failures. But a tacit dichotomy exists in MapReduce due to its inherent two-phase (map and reduce) management scheme in which map tasks and reduce tasks have distinctly different execution behaviors, yet reduce tasks are dependent on the results of map tasks. We reveal that speculation policies for fault handling in MapReduce do not recognize this dichotomy between map and reduce tasks, which leads to an issue of speculation myopia for MapReduce fault recovery. These issues cause significant performance degradation upon network and node failures. To address the speculation myopia caused by MapReduce dichotomy, we introduce a new scheme called binocular speculation to help MapReduce increase its assessment scope for speculation. As part of the scheme, we also design three component techniques including neighborhood glance, collective speculation and speculative rollback. Our evaluation shows that, with these techniques, binocular speculation can increase the coordination of map and reduce phases, and enhance the efficiency of MapReduce fault recovery.
On the Fundamental Limits of Multi-user Scheduling under Short-term Fairness Constraints
Venue: arXiv cs.IT 2019
Year: 2019

In the conventional information theoretic analysis of multiterminal communication scenarios, it is often assumed that all of the distributed terminals use the communication channel simultaneously. However, in practical wireless communication systems - due to restricted computation complexity at network terminals - a limited number of users can be activated either in uplink or downlink simultaneously. This necessitates the design of a scheduler which determines the set of active users at each time-slot. A well designed scheduler maximizes the average system utility subject to a set of fairness criteria, which must be met in a limited window-length to avoid long starvation periods. In this work, scheduling under short-term temporal fairness constraints is considered. The objective is to maximize the average system utility such that the fraction of the time-slots that each user is activated is within desired upper and lower bounds in the fairness window-length. The set of feasible window-lengths is characterized as a function of system parameters. It is shown that the optimal system utility is non-monotonic and super-additive in window-length. Furthermore, a scheduling strategy is proposed which satisfies short-term fairness constraints for arbitrary window-lengths, and achieves optimal average system utility as the window-length is increased asymptotically. Numerical simulations are provided to verify the results.
PINPOINT: Efficient and Effective Resource Isolation for Mobile Security and Privacy
Venue: arXiv cs.OS 2019
Year: 2019

Virtualization is frequently used to isolate untrusted processes and control their access to sensitive resources. However, isolation usually carries a price in terms of less resource sharing and reduced inter-process communication. In an open architecture such as Android, this price and its impact on performance, usability, and transparency must be carefully considered. Although previous efforts in developing general-purpose isolation solutions have shown that some of these negative side effects can be mitigated, doing so involves overcoming significant design challenges by incorporating numerous additional platform complexities not directly related to improved security. Thus, the general purpose solutions become inefficient and burdensome if the end-user has only specific security goals. In this paper, we present PINPOINT, a resource isolation strategy that forgoes general-purpose solutions in favor of a "building block" approach that addresses specific end-user security goals. PINPOINT embodies the concept of Linux Namespace lightweight isolation, but does so in the Android Framework by guiding the security designer towards isolation points that are contextually close to the resource(s) that need to be isolated. This strategy allows the rest of the Framework to function fully as intended, transparently. We demonstrate our strategy with a case study on Android System Services, and show four applications of PINPOINTed system services functioning with unmodified market apps. Our evaluation results show that practical security and privacy advantages can be gained using our approach, without inducing the problematic side-effects that other general-purpose designs must address.
Thompson Sampling for a Fatigue-aware Online Recommendation System
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we consider an online recommendation setting, where a platform recommends a sequence of items to its users at every time period. The users respond by selecting one of the items recommended or abandon the platform due to fatigue from seeing less useful items. Assuming a parametric stochastic model of user behavior, which captures positional effects of these items as well as the abandoning behavior of users, the platform's goal is to recommend sequences of items that are competitive to the single best sequence of items in hindsight, without knowing the true user model a priori. Naively applying a stochastic bandit algorithm in this setting leads to an exponential dependence on the number of items. We propose a new Thompson sampling based algorithm with expected regret that is polynomial in the number of items in this combinatorial setting, and performs extremely well in practice.
Interacting with the Internet of Things using Smart Contracts and Blockchain Technologies
Venue: arXiv cs.CR 2019
Year: 2019

Despite technological advances, most smart objects in the Internet of Things (IoT) cannot be accessed using technologies designed and developed for interacting with powerful Internet servers. IoT use cases involve devices that not only have limited resources, but also they are not always connected to the Internet and are physically exposed to tampering. In this paper, we describe the design, development, and evaluation of a smart contract-based solution that allows end-users to securely interact with smart devices. Our approach enables access control, Thing authentication, and payments in a fully decentralized setting, taking at the same time into consideration the limitations and constraints imposed by both blockchain technologies and the IoT paradigm. Our prototype implementation is based on existing technologies, i.e., Ethereum smart contracts, which makes it realistic and fundamentally secure.
Predicting Parkinson's Disease using Latent Information extracted from Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

This paper presents a new method for medical diagnosis of neurodegenerative diseases, such as Parkinson's, by extracting and using latent information from trained Deep convolutional, or convolutional-recurrent Neural Networks (DNNs). In particular, our approach adopts a combination of transfer learning, k-means clustering and k-Nearest Neighbour classification of deep neural network learned representations to provide enriched prediction of the disease based on MRI and/or DaT Scan data. A new loss function is introduced and used in the training of the DNNs, so as to perform adaptation of the generated learned representations between data from different medical environments. Results are presented using a recently published database of Parkinson's related information, which was generated and evaluated in a hospital environment.
AStERISK: Auction-based Shared Economy ResolutIon System for blocKchain
Venue: arXiv cs.CR 2019
Year: 2019

Recent developments in blockchains and edge computing allows to deploy decentralized shared economy with utility tokens, where altcoins secure and reward useful work. However, the majority of the systems being developed, does not provide mechanisms to pair workers and clients, or rely on manual and insecure resolution. AStERISK bridges this gap allowing to perform sealed-bid auctions on blockchains, automatically determine the most optimal price for services, and assign clients to the most suitable workers. AStERISK allows workers to specify a minimal price for their work, and hide submitted bids as well the identity of the bidders without relying on any centralized party at any point. We provide a smart contract implementation of AStERISK and show how to deploy it within the Filecoin network, and perform an initial benchmark on Chainspace.
Toward Joint Image Generation and Compression using Generative Adversarial Networks
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we present a generative adversarial network framework that generates compressed images instead of synthesizing raw RGB images and compressing them separately. In the real world, most images and videos are stored and transferred in a compressed format to save storage capacity and data transfer bandwidth. However, since typical generative adversarial networks generate raw RGB images, those generated images need to be compressed by a post-processing stage to reduce the data size. Among image compression methods, JPEG has been one of the most commonly used lossy compression methods for still images. Hence, we propose a novel framework that generates JPEG compressed images using generative adversarial networks. The novel generator consists of the proposed locally connected layers, chroma subsampling layers, quantization layers, residual blocks, and convolution layers. The locally connected layer is proposed to enable block-based operations. We also discuss training strategies for the proposed architecture including the loss function and the transformation between its generator and its discriminator. The proposed method is evaluated using the publicly available CIFAR-10 dataset and LSUN bedroom dataset. The results demonstrate that the proposed method is able to generate compressed data with competitive qualities. The proposed method is a promising baseline method for joint image generation and compression using generative adversarial networks.
Computer Vision and Metrics Learning for Hypothesis Testing: An Application of Q-Q Plot for Normality Test
Venue: arXiv cs.CV 2019
Year: 2019

This paper proposes a new deep-learning method to construct test statistics by computer vision and metrics learning. The application highlighted in this paper is applying computer vision on Q-Q plot to construct a new test statistic for normality test. To the best of our knowledge, there is no similar application documented in the literature. Traditionally, there are two families of approaches for verifying the probability distribution of a random variable. Researchers either subjectively assess the Q-Q plot or objectively use a mathematical formula, such as Kolmogorov-Smirnov test, to formally conduct a normality test. Graphical assessment by human beings is not rigorous whereas normality test statistics may not be accurate enough when the uniformly most powerful test does not exist. It may take tens of years for statistician to develop a new test statistic that is more powerful statistically. Our proposed method integrates four components based on deep learning: an image representation learning component of a Q-Q plot, a dimension reduction component, a metrics learning component that best quantifies the differences between two Q-Q plots for normality test, and a new normality hypothesis testing process. Our experimentation results show that the machine-learning-based test statistics can outperform several widely-used traditional normality tests. This study provides convincing evidence that the proposed method could objectively create a powerful test statistic based on Q-Q plots and this method could be modified to construct many more powerful test statistics for other applications in the future.
Trust Region Value Optimization using Kalman Filtering
Venue: arXiv cs.LG 2019
Year: 2019

Policy evaluation is a key process in reinforcement learning. It assesses a given policy using estimation of the corresponding value function. When using a parameterized function to approximate the value, it is common to optimize the set of parameters by minimizing the sum of squared Bellman Temporal Differences errors. However, this approach ignores certain distributional properties of both the errors and value parameters. Taking these distributions into account in the optimization process can provide useful information on the amount of confidence in value estimation. In this work we propose to optimize the value by minimizing a regularized objective function which forms a trust region over its parameters. We present a novel optimization method, the Kalman Optimization for Value Approximation (KOVA), based on the Extended Kalman Filter. KOVA minimizes the regularized objective function by adopting a Bayesian perspective over both the value parameters and noisy observed returns. This distributional property provides information on parameter uncertainty in addition to value estimates. We provide theoretical results of our approach and analyze the performance of our proposed optimizer on domains with large state and action spaces.
Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation
Venue: arXiv cs.DS 2019
Year: 2019

We propose a solution approach for the problem (P) of minimizing an unconstrained binary polynomial optimization problem. We call this method PQCR (Polynomial Quadratic Convex Reformulation). The resolution is based on a 3-phase method. The first phase consists in reformulating (P) into a quadratic program (QP). For this, we recursively reduce the degree of (P) to two, by use of the standard substitution of the product of two variables by a new one. We then obtain a linearly constrained binary program. In the second phase, we rewrite the quadratic objective function into an equivalent and parametrized quadratic function using the equality x 2 i = x i and new valid quadratic equalities. Then, we focus on finding the best parameters to get a quadratic convex program which continuous relaxation's optimal value is maximized. For this, we build a semidefinite relaxation (SDP) of (QP). Then, we prove that the standard linearization inequalities, used for the quadratization step, are redundant in (SDP) in presence of the new quadratic equalities. Next, we deduce our optimal parameters from the dual optimal solution of (SDP). The third phase consists in solving (QP *), the optimal reformulated problem, with a standard solver. In particular, at each node of the branch-and-bound, the solver computes the optimal value of a continuous quadratic convex program. We present computational results on instances of the image restoration problem and of the low autocorrelation binary sequence problem. We compare PQCR with other convexification methods, and with the general solver Baron 17.4.1 [39]. We observe that most of the considered instances can be solved with our approach combined with the use of Cplex [24].