OpenRaiser/Intern-Atlas huggingface dataset:
A Survey and Taxonomy of Self-Aware and Self-Adaptive Cloud Autoscaling Systems
Venue: arXiv cs.SE 2018
Year: 2018

Autoscaling system can reconfigure cloud-based services and applications, through various configurations of cloud software and provisions of hardware resources, to adapt to the changing environment at runtime. Such a behavior offers the foundation for achieving elasticity in modern cloud computing paradigm. Given the dynamic and uncertain nature of the shared cloud infrastructure, cloud autoscaling system has been engineered as one of the most complex, sophisticated and intelligent artifacts created by human, aiming to achieve self-aware, self-adaptive and dependable runtime scaling. Yet, existing Self-aware and Self-adaptive Cloud Autoscaling System (SSCAS) is not mature to a state that it can be reliably exploited in the cloud. In this article, we survey the state-of-the-art research studies on SSCAS and provide a comprehensive taxonomy for this field. We present detailed analysis of the results and provide insights on open challenges, as well as the promising directions that are worth investigated in the future work of this area of research. Our survey and taxonomy contribute to the fundamentals of engineering more intelligent autoscaling systems in the cloud.
On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling
Venue: arXiv cs.CR 2018
Year: 2018

We consider the computational complexity of finding a legal black pebbling of a DAG $G=(V,E)$ with minimum cumulative cost. A black pebbling is a sequence $P_0,\ldots, P_t \subseteq V$ of sets of nodes which must satisfy the following properties: $P_0 = \emptyset$ (we start off with no pebbles on $G$), $\mathsf{sinks}(G) \subseteq \bigcup_{j \leq t} P_j$ (every sink node was pebbled at some point) and $\mathsf{parents}\big(P_{i+1}\backslash P_i\big) \subseteq P_i$ (we can only place a new pebble on a node $v$ if all of $v$'s parents had a pebble during the last round). The cumulative cost of a pebbling $P_0,P_1,\ldots, P_t \subseteq V$ is $\mathsf{cc}(P) = | P_1| + \ldots + | P_t|$. The cumulative pebbling cost is an especially important security metric for data-independent memory hard functions, an important primitive for password hashing. Thus, an efficient (approximation) algorithm would be an invaluable tool for the cryptanalysis of password hash functions as it would provide an automated tool to establish tight bounds on the amortized space-time cost of computing the function. We show that such a tool is unlikely to exist. In particular, we prove the following results. (1) It is $\texttt{NP}\mbox{-}\texttt{Hard}$ to find a pebbling minimizing cumulative cost. (2) The natural linear program relaxation for the problem has integrality gap $\tilde{O}(n)$, where $n$ is the number of nodes in $G$. We conjecture that the problem is hard to approximate. (3) We show that a related problem, find the minimum size subset $S\subseteq V$ such that $\textsf{depth}(G-S) \leq d$, is also $\texttt{NP}\mbox{-}\texttt{Hard}$. In fact, under the unique games conjecture there is no $(2-ε)$-approximation algorithm.
Deep Learning for Video Classification and Captioning
Venue: arXiv cs.CV 2018
Year: 2018

Accelerated by the tremendous increase in Internet bandwidth and storage space, video data has been generated, published and spread explosively, becoming an indispensable part of today's big data. In this paper, we focus on reviewing two lines of research aiming to stimulate the comprehension of videos with deep learning: video classification and video captioning. While video classification concentrates on automatically labeling video clips based on their semantic contents like human actions or complex events, video captioning attempts to generate a complete and natural sentence, enriching the single label as in video classification, to capture the most informative dynamics in videos. In addition, we also provide a review of popular benchmarks and competitions, which are critical for evaluating the technical progress of this vibrant field.
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
Venue: arXiv cs.DS 2018
Year: 2018

This paper makes two main contributions: The first is the construction of a near-minimum spanning tree with constant average distortion. The second is a general equivalence theorem relating two refined notions of distortion: scaling distortion and prioritized distortion. Minimum Spanning Trees of weighted graphs are fundamental objects in numerous applications. In particular in distributed networks, the minimum spanning tree of the network is often used to route messages between network nodes. Unfortunately, while being most efficient in the total cost of connecting all nodes, minimum spanning trees fail miserably in the desired property of approximately preserving distances between pairs. While known lower bounds exclude the possibility of the worst case distortion of a tree being small, it was shown in [ABN15] that there exists a spanning tree with constant average distortion. Yet, the weight of such a tree may be significantly larger than that of the MST. In this paper, we show that any weighted undirected graph admits a {\em spanning tree} whose weight is at most $(1+ρ)$ times that of the MST, providing {\em constant average distortion} $O(1/ρ)$. Our result exhibits the best possible tradeoff of this type. This result makes use of a general equivalence theorem relating two recently developed notions of distortion for metric embedding. The first is the notion of scaling distortion, which provides improved distortion for $1-ε$ fractions of the pairs, for all $ε$ simultaneously. A stronger version called coarse scaling distortion, has improved distortion guarantees for the furthest pairs. The second notion is that of prioritized distortion, a property allowing to prioritize the nodes whose associated distortions will be improved. We show that prioritized distortion is essentially equivalent to coarse scaling distortion via a general transformation.
A large scale study of SVM based methods for abstract screening in systematic reviews
Venue: arXiv cs.IR 2018
Year: 2018

A major task in systematic reviews is abstract screening, i.e., excluding, often hundreds or thousand of, irrelevant citations returned from a database search based on titles and abstracts. Thus, a systematic review platform that can automate the abstract screening process is of huge importance. Several methods have been proposed for this task. However, it is very hard to clearly understand the applicability of these methods in a systematic review platform because of the following challenges: (1) the use of non-overlapping metrics for the evaluation of the proposed methods, (2) usage of features that are very hard to collect, (3) using a small set of reviews for the evaluation, and (4) no solid statistical testing or equivalence grouping of the methods. In this paper, we use feature representation that can be extracted per citation. We evaluate SVM-based methods (commonly used) on a large set of reviews ($61$) and metrics ($11$) to provide equivalence grouping of methods based on a solid statistical test. Our analysis also includes a strong variability of the metrics using $500$x$2$ cross validation. While some methods shine for different metrics and for different datasets, there is no single method that dominates the pack. Furthermore, we observe that in some cases relevant (included) citations can be found after screening only 15-20% of them via a certainty based sampling. A few included citations present outlying characteristics and can only be found after a very large number of screening steps. Finally, we present an ensemble algorithm for producing a $5$-star rating of citations based on their relevance. Such algorithm combines the best methods from our evaluation and through its $5$-star rating outputs a more easy-to-consume prediction.
A Survey of Symbolic Execution Techniques
Venue: arXiv cs.SE 2018
Year: 2018

Many security and software testing applications require checking whether certain properties of a program hold for any possible usage scenario. For instance, a tool for identifying software vulnerabilities may need to rule out the existence of any backdoor to bypass a program's authentication. One approach would be to test the program using different, possibly random inputs. As the backdoor may only be hit for very specific program workloads, automated exploration of the space of possible inputs is of the essence. Symbolic execution provides an elegant solution to the problem, by systematically exploring many possible execution paths at the same time without necessarily requiring concrete inputs. Rather than taking on fully specified input values, the technique abstractly represents them as symbols, resorting to constraint solvers to construct actual instances that would cause property violations. Symbolic execution has been incubated in dozens of tools developed over the last four decades, leading to major practical breakthroughs in a number of prominent software reliability applications. The goal of this survey is to provide an overview of the main ideas, challenges, and solutions developed in the area, distilling them for a broad audience. The present survey has been accepted for publication at ACM Computing Surveys. If you are considering citing this survey, we would appreciate if you could use the following BibTeX entry: http://goo.gl/Hf5Fvc
A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

We consider the two related problems of detecting if an example is misclassified or out-of-distribution. We present a simple baseline that utilizes probabilities from softmax distributions. Correctly classified examples tend to have greater maximum softmax probabilities than erroneously classified and out-of-distribution examples, allowing for their detection. We assess performance by defining several tasks in computer vision, natural language processing, and automatic speech recognition, showing the effectiveness of this baseline across all. We then show the baseline can sometimes be surpassed, demonstrating the room for future research on these underexplored detection tasks.
ILGNet: Inception Modules with Connected Local and Global Features for Efficient Image Aesthetic Quality Classification using Domain Adaptation
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we address a challenging problem of aesthetic image classification, which is to label an input image as high or low aesthetic quality. We take both the local and global features of images into consideration. A novel deep convolutional neural network named ILGNet is proposed, which combines both the Inception modules and an connected layer of both Local and Global features. The ILGnet is based on GoogLeNet. Thus, it is easy to use a pre-trained GoogLeNet for large-scale image classification problem and fine tune our connected layers on an large scale database of aesthetic related images: AVA, i.e. \emph{domain adaptation}. The experiments reveal that our model achieves the state of the arts in AVA database. Both the training and testing speeds of our model are higher than those of the original GoogLeNet.
Location-Aided Pilot Contamination Avoidance for Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

Pilot contamination, defined as the interference during the channel estimation process due to reusing the same pilot sequences in neighboring cells, can severely degrade the performance of massive multiple-input multiple-output systems. In this paper, we propose a location-based approach to mitigating the pilot contamination problem for uplink multiple-input multiple-output systems. Our approach makes use of the approximate locations of mobile devices to provide good estimates of the channel statistics between the mobile devices and their corresponding base stations. Specifically, we aim at avoiding pilot contamination even when the number of base station antennas is not very large, and when multiple users from different cells, or even in the same cell, are assigned the same pilot sequence. First, we characterize a desired angular region of the target user at the serving base station based on the number of base station antennas and the location of the target user, and make the observation that in this region the interference is close to zero due to the spatial separability. Second, based on this observation, we propose pilot coordination methods for multi-user multi-cell scenarios to avoid pilot contamination. The numerical results indicate that the proposed pilot contamination avoidance schemes enhance the quality of the channel estimation and thereby improve the per-cell sum rate offered by target base stations.
Vector Approximate Message Passing
Venue: arXiv cs.IT 2018
Year: 2018

The standard linear regression (SLR) problem is to recover a vector $\mathbf{x}^0$ from noisy linear observations $\mathbf{y}=\mathbf{Ax}^0+\mathbf{w}$. The approximate message passing (AMP) algorithm recently proposed by Donoho, Maleki, and Montanari is a computationally efficient iterative approach to SLR that has a remarkable property: for large i.i.d.\ sub-Gaussian matrices $\mathbf{A}$, its per-iteration behavior is rigorously characterized by a scalar state-evolution whose fixed points, when unique, are Bayes optimal. The AMP algorithm, however, is fragile in that even small deviations from the i.i.d.\ sub-Gaussian model can cause the algorithm to diverge. This paper considers a "vector AMP" (VAMP) algorithm and shows that VAMP has a rigorous scalar state-evolution that holds under a much broader class of large random matrices $\mathbf{A}$: those that are right-orthogonally invariant. After performing an initial singular value decomposition (SVD) of $\mathbf{A}$, the per-iteration complexity of VAMP can be made similar to that of AMP. In addition, the fixed points of VAMP's state evolution are consistent with the replica prediction of the minimum mean-squared error recently derived by Tulino, Caire, Verdú, and Shamai. Numerical experiments are used to confirm the effectiveness of VAMP and its consistency with state-evolution predictions.
Network segregation in a model of misinformation and fact checking
Venue: arXiv cs.SI 2018
Year: 2018

Misinformation under the form of rumor, hoaxes, and conspiracy theories spreads on social media at alarming rates. One hypothesis is that, since social media are shaped by homophily, belief in misinformation may be more likely to thrive on those social circles that are segregated from the rest of the network. One possible antidote is fact checking which, in some cases, is known to stop rumors from spreading further. However, fact checking may also backfire and reinforce the belief in a hoax. Here we take into account the combination of network segregation, finite memory and attention, and fact-checking efforts. We consider a compartmental model of two interacting epidemic processes over a network that is segregated between gullible and skeptic users. Extensive simulation and mean-field analysis show that a more segregated network facilitates the spread of a hoax only at low forgetting rates, but has no effect when agents forget at faster rates. This finding may inform the development of mitigation techniques and overall inform on the risks of uncontrolled misinformation online.
To Frontalize or Not To Frontalize: Do We Really Need Elaborate Pre-processing To Improve Face Recognition?
Venue: arXiv cs.CV 2018
Year: 2018

Face recognition performance has improved remarkably in the last decade. Much of this success can be attributed to the development of deep learning techniques such as convolutional neural networks (CNNs). While CNNs have pushed the state-of-the-art forward, their training process requires a large amount of clean and correctly labelled training data. If a CNN is intended to tolerate facial pose, then we face an important question: should this training data be diverse in its pose distribution, or should face images be normalized to a single pose in a pre-processing step? To address this question, we evaluate a number of popular facial landmarking and pose correction algorithms to understand their effect on facial recognition performance. Additionally, we introduce a new, automatic, single-image frontalization scheme that exceeds the performance of current algorithms. CNNs trained using sets of different pre-processing methods are used to extract features from the Point and Shoot Challenge (PaSC) and CMU Multi-PIE datasets. We assert that the subsequent verification and recognition performance serves to quantify the effectiveness of each pose correction scheme.
Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent
Venue: arXiv cs.DS 2018
Year: 2018

In a barter exchange market, agents bring items and seek to exchange their items with one another. Agents may agree to a k-way exchange involving a cycle of k agents. A barter exchange market can be represented by a digraph where the vertices represent items and the edges out of a vertex indicate the items that an agent is willing to accept in exchange for that item. It is known that the problem of finding a set of vertex-disjoint cycles with the maximum total number of vertices (MAX-SIZE-EXCHANGE) can be solved in polynomial time. We consider a barter exchange where each agent may bring multiple items, and items of the same agent are represented by vertices with the same color. A set of cycles is said to be tropical if for every color there is a cycle that contains a vertex of that color. We show that the problem of determining whether there exists a tropical set of vertex-disjoint cycles in a digraph (TROPICAL-EXCHANGE) is NP-complete and APX-hard. This is equivalent to determining whether it is possible to arrange an exchange of items among agents such that every agent trades away at least one item. TROPICAL-MAX-SIZE-EXCHANGE is a similar problem, where the goal is to find a set of vertex-disjoint cycles that contains the maximum number of vertices and also contains all of the colors in the graph. We show that this problem is likewise NP-complete and APX-hard. For the restricted case where there are at most two vertices of each color (corresponding to a restriction that each agent may bring at most two items), both problems remain NP-hard but are in APX. Finally, we consider MAX-SIZE-TROPICAL-EXCHANGE, where the set of cycles must primarily include as many colors as possible and secondarily include as many vertices as possible. We show that this problem is NP-hard.
Better Streaming Algorithms for the Maximum Coverage Problem
Venue: arXiv cs.DS 2018
Year: 2018

We study the classic NP-Hard problem of finding the maximum $k$-set coverage in the data stream model: given a set system of $m$ sets that are subsets of a universe $\{1,\ldots,n \}$, find the $k$ sets that cover the most number of distinct elements. The problem can be approximated up to a factor $1-1/e$ in polynomial time. In the streaming-set model, the sets and their elements are revealed online. The main goal of our work is to design algorithms, with approximation guarantees as close as possible to $1-1/e$, that use sublinear space $o(mn)$. Our main results are: Two $(1-1/e-ε)$ approximation algorithms: One uses $O(ε^{-1})$ passes and $\tilde{O}(ε^{-2} k)$ space whereas the other uses only a single pass but $\tilde{O}(ε^{-2} m)$ space. We show that any approximation factor better than $(1-(1-1/k)^k)$ in constant passes requires $Ω(m)$ space for constant $k$ even if the algorithm is allowed unbounded processing time. We also demonstrate a single-pass, $(1-ε)$ approximation algorithm using $\tilde{O}(ε^{-2} m \cdot \min(k,ε^{-1}))$ space. We also study the maximum $k$-vertex coverage problem in the dynamic graph stream model. In this model, the stream consists of edge insertions and deletions of a graph on $N$ vertices. The goal is to find $k$ vertices that cover the most number of distinct edges. We show that any constant approximation in constant passes requires $Ω(N)$ space for constant $k$ whereas $\tilde{O}(ε^{-2}N)$ space is sufficient for a $(1-ε)$ approximation and arbitrary $k$ in a single pass. For regular graphs, we show that $\tilde{O}(ε^{-3}k)$ space is sufficient for a $(1-ε)$ approximation in a single pass. We generalize this to a $(κ-ε)$ approximation when the ratio between the minimum and maximum degree is bounded below by $κ$.
An Efficient Web Traffic Defence Against Timing-Analysis Attacks
Venue: arXiv cs.NI 2018
Year: 2018

We introduce a new class of lower overhead tunnel that is resistant to traffic analysis. The tunnel opportunistically reduces the number of dummy packets transmitted during busy times when many flows are simultaneously active while maintaining well-defined privacy properties. We find that the dummy packet overhead is typically less than 20% on lightly loaded links and falls to zero as the traffic load increases i.e. the tunnel is capacity-achieving. The additional latency incurred is less than 100ms. We build an experimental prototype of the tunnel and carry out an extensive performance evaluation that demonstrates its effectiveness under a range of network conditions and real web page fetches.
PhaseMax: Convex Phase Retrieval via Basis Pursuit
Venue: arXiv cs.IT 2018
Year: 2018

We consider the recovery of a (real- or complex-valued) signal from magnitude-only measurements, known as phase retrieval. We formulate phase retrieval as a convex optimization problem, which we call PhaseMax. Unlike other convex methods that use semidefinite relaxation and lift the phase retrieval problem to a higher dimension, PhaseMax is a "non-lifting" relaxation that operates in the original signal dimension. We show that the dual problem to PhaseMax is Basis Pursuit, which implies that phase retrieval can be performed using algorithms initially designed for sparse signal recovery. We develop sharp lower bounds on the success probability of PhaseMax for a broad range of random measurement ensembles, and we analyze the impact of measurement noise on the solution accuracy. We use numerical results to demonstrate the accuracy of our recovery guarantees, and we showcase the efficacy and limits of PhaseMax in practice.