OpenRaiser/Intern-Atlas huggingface dataset:
Programming Requests/Responses with GreatFree in the Cloud Environment
Venue: arXiv cs.PL 2018
Year: 2018

Programming request with GreatFree is an efficient programming technique to implement distributed polling in the cloud computing environment. GreatFree is a distributed programming environment through which diverse distributed systems can be established through programming rather than configuring or scripting. GreatFree emphasizes the importance of programming since it offers developers the opportunities to leverage their distributed knowledge and programming skills. Additionally, programming is the unique way to construct creative, adaptive and flexible systems to accommodate various distributed computing environments. With the support of GreatFree code-level Distributed Infrastructure Patterns, Distributed Operation Patterns and APIs, the difficult procedure is accomplished in a programmable, rapid and highly-patterned manner, i.e., the programming behaviors are simplified as the repeatable operation of Copy-Paste-Replace. Since distributed polling is one of the fundamental techniques to construct distributed systems, GreatFree provides developers with relevant APIs and patterns to program requests/responses in the novel programming environment.
A generalized matrix Krylov subspace method for TV regularization
Venue: arXiv cs.NA 2018
Year: 2018

This paper presents an efficient algorithm to solve total variation (TV) regularizations of images contaminated by a both blur and noise. The unconstrained structure of the problem suggests that one can solve a constrained optimization problem by transforming the original unconstrained minimization problem to an equivalent constrained minimization one. An augmented Lagrangian method is developed to handle the constraints when the model is given with matrix variables, and an alternating direction method (ADM) is used to iteratively find solutions. The solutions of some sub-problems are belonging to subspaces generated by application of successive orthogonal projections onto a class of generalized matrix Krylov subspaces of increasing dimension.
Bayesian Optimization Using Monotonicity Information and Its Application in Machine Learning Hyperparameter
Venue: arXiv cs.LG 2018
Year: 2018

We propose an algorithm for a family of optimization problems where the objective can be decomposed as a sum of functions with monotonicity properties. The motivating problem is optimization of hyperparameters of machine learning algorithms, where we argue that the objective, validation error, can be decomposed as monotonic functions of the hyperparameters. Our proposed algorithm adapts Bayesian optimization methods to incorporate the monotonicity constraints. We illustrate the advantages of exploiting monotonicity using illustrative examples and demonstrate the improvements in optimization efficiency for some machine learning hyperparameter tuning applications.
From acquaintance to best friend forever: robust and fine-grained inference of social tie strengths
Venue: arXiv cs.SI 2018
Year: 2018

Social networks often provide only a binary perspective on social ties: two individuals are either connected or not. While sometimes external information can be used to infer the strength of social ties, access to such information may be restricted or impractical. Sintos and Tsaparas (KDD 2014) first suggested to infer the strength of social ties from the topology of the network alone, by leveraging the Strong Triadic Closure (STC) property. The STC property states that if person A has strong social ties with persons B and C, B and C must be connected to each other as well (whether with a weak or strong tie). Sintos and Tsaparas exploited this to formulate the inference of the strength of social ties as NP-hard optimization problem, and proposed two approximation algorithms. We refine and improve upon this landmark paper, by developing a sequence of linear relaxations of this problem that can be solved exactly in polynomial time. Usefully, these relaxations infer more fine-grained levels of tie strength (beyond strong and weak), which also allows to avoid making arbitrary strong/weak strength assignments when the network topology provides inconclusive evidence. One of the relaxations simultaneously infers the presence of a limited number of STC violations. An extensive theoretical analysis leads to two efficient algorithmic approaches. Finally, our experimental results elucidate the strengths of the proposed approach, and sheds new light on the validity of the STC property in practice.
About being the Tortoise or the Hare? - A Position Paper on Making Cloud Applications too Fast and Furious for Attackers
Venue: arXiv cs.CR 2018
Year: 2018

Cloud applications expose - beside service endpoints - also potential or actual vulnerabilities. And attackers have several advantages on their side. They can select the weapons, the point of time and the point of attack. Very often cloud application security engineering efforts focus to harden the fortress walls but seldom assume that attacks may be successful. So, cloud applications rely on their defensive walls but seldom attack intruders actively. Biological systems are different. They accept that defensive "walls" can be breached at several layers and therefore make use of an active and adaptive defense system to attack potential intruders - an immune system. This position paper proposes such an immune system inspired approach to ensure that even undetected intruders can be purged out of cloud applications. This makes it much harder for intruders to maintain a presence on victim systems. Evaluation experiments with popular cloud service infrastructures (Amazon Web Services, Google Compute Engine, Azure and OpenStack) showed that this could minimize the undetected acting period of intruders down to minutes.
Distributed Log Analysis on the Cloud Using MapReduce
Venue: arXiv cs.DC 2018
Year: 2018

In this paper we describe our work on designing a web based, distributed data analysis system based on the popular MapReduce framework deployed on a small cloud; developed specifically for analyzing web server logs. The log analysis system consists of several cluster nodes, it splits the large log files on a distributed file system and quickly processes them using MapReduce programming model. The cluster is created using an open source cloud infrastructure, which allows us to easily expand the computational power by adding new nodes. This gives us the ability to automatically resize the cluster according to the data analysis requirements. We implemented MapReduce programs for basic log analysis needs like frequency analysis, error detection, busy hour detection etc. as well as more complex analyses which require running several jobs. The system can automatically identify and analyze several web server log types such as Apache, IIS, Squid etc. We use open source projects for creating the cloud infrastructure and running MapReduce jobs.
Deep Visual Domain Adaptation: A Survey
Venue: arXiv cs.CV 2018
Year: 2018

Deep domain adaption has emerged as a new learning technique to address the lack of massive amounts of labeled data. Compared to conventional methods, which learn shared feature subspaces or reuse important source instances with shallow representations, deep domain adaption methods leverage deep networks to learn more transferable representations by embedding domain adaptation in the pipeline of deep learning. There have been comprehensive surveys for shallow domain adaption, but few timely reviews the emerging deep learning based methods. In this paper, we provide a comprehensive survey of deep domain adaptation methods for computer vision applications with four major contributions. First, we present a taxonomy of different deep domain adaption scenarios according to the properties of data that define how two domains are diverged. Second, we summarize deep domain adaption approaches into several categories based on training loss, and analyze and compare briefly the state-of-the-art methods under these categories. Third, we overview the computer vision applications that go beyond image classification, such as face recognition, semantic segmentation and object detection. Fourth, some potential deficiencies of current methods and several future directions are highlighted.
Graph Planning with Expected Finite Horizon
Venue: arXiv cs.AI 2018
Year: 2018

Graph planning gives rise to fundamental algorithmic questions such as shortest path, traveling salesman problem, etc. A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon $T$. However, in many scenarios, the time horizon is not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is $T$. If the stopping time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary, to represent the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping-time distribution with expected stopping time $T$, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping-time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans.
TextZoo, a New Benchmark for Reconsidering Text Classification
Venue: arXiv cs.CL 2018
Year: 2018

Text representation is a fundamental concern in Natural Language Processing, especially in text classification. Recently, many neural network approaches with delicate representation model (e.g. FASTTEXT, CNN, RNN and many hybrid models with attention mechanisms) claimed that they achieved state-of-art in specific text classification datasets. However, it lacks an unified benchmark to compare these models and reveals the advantage of each sub-components for various settings. We re-implement more than 20 popular text representation models for classification in more than 10 datasets. In this paper, we reconsider the text classification task in the perspective of neural network and get serval effects with analysis of the above results.
Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers
Venue: arXiv cs.IT 2018
Year: 2018

A private information retrieval (PIR) scheme on coded storage systems with colluding, byzantine, and non-responsive servers is presented. Furthermore, the scheme can also be used for symmetric PIR in the same setting. An explicit scheme using an $[n,k]$ generalized Reed-Solomon storage code is designed, protecting against $t$-collusion and handling up to $b$ byzantine and $r$ non-responsive servers, when $n\geq n'= (ν+1) k+t+2b+r-1$, for some integer $ν\geq 1$. This scheme achieves a PIR rate of $1-\frac{k+2b+t+r-1}{n'}$. In the case where the capacity is known, namely when $k=1$, it is asymptotically capacity achieving as the number of files grows.
Sample Efficient Deep Reinforcement Learning for Dialogue Systems with Large Action Spaces
Venue: arXiv cs.CL 2018
Year: 2018

In spoken dialogue systems, we aim to deploy artificial intelligence to build automated dialogue agents that can converse with humans. A part of this effort is the policy optimisation task, which attempts to find a policy describing how to respond to humans, in the form of a function taking the current state of the dialogue and returning the response of the system. In this paper, we investigate deep reinforcement learning approaches to solve this problem. Particular attention is given to actor-critic methods, off-policy reinforcement learning with experience replay, and various methods aimed at reducing the bias and variance of estimators. When combined, these methods result in the previously proposed ACER algorithm that gave competitive results in gaming environments. These environments however are fully observable and have a relatively small action set so in this paper we examine the application of ACER to dialogue policy optimisation. We show that this method beats the current state-of-the-art in deep learning approaches for spoken dialogue systems. This not only leads to a more sample efficient algorithm that can train faster, but also allows us to apply the algorithm in more difficult environments than before. We thus experiment with learning in a very large action space, which has two orders of magnitude more actions than previously considered. We find that ACER trains significantly faster than the current state-of-the-art.
Convex Formulations for Fair Principal Component Analysis
Venue: arXiv cs.LG 2018
Year: 2018

Though there is a growing body of literature on fairness for supervised learning, the problem of incorporating fairness into unsupervised learning has been less well-studied. This paper studies fairness in the context of principal component analysis (PCA). We first present a definition of fairness for dimensionality reduction, and our definition can be interpreted as saying that a reduction is fair if information about a protected class (e.g., race or gender) cannot be inferred from the dimensionality-reduced data points. Next, we develop convex optimization formulations that can improve the fairness (with respect to our definition) of PCA and kernel PCA. These formulations are semidefinite programs (SDP's), and we demonstrate the effectiveness of our formulations using several datasets. We conclude by showing how our approach can be used to perform a fair (with respect to age) clustering of health data that may be used to set health insurance rates.
Learning Deep Convolutional Networks for Demosaicing
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a comprehensive study of applying the convolutional neural network (CNN) to solving the demosaicing problem. The paper presents two CNN models that learn end-to-end mappings between the mosaic samples and the original image patches with full information. In the case the Bayer color filter array (CFA) is used, an evaluation with ten competitive methods on popular benchmarks confirms that the data-driven, automatically learned features by the CNN models are very effective. Experiments show that the proposed CNN models can perform equally well in both the sRGB space and the linear space. It is also demonstrated that the CNN model can perform joint denoising and demosaicing. The CNN model is very flexible and can be easily adopted for demosaicing with any CFA design. We train CNN models for demosaicing with three different CFAs and obtain better results than existing methods. With the great flexibility to be coupled with any CFA, we present the first data-driven joint optimization of the CFA design and the demosaicing method using CNN. Experiments show that the combination of the automatically discovered CFA pattern and the automatically devised demosaicing method significantly outperforms the current best demosaicing results. Visual comparisons confirm that the proposed methods reduce more visual artifacts than existing methods. Finally, we show that the CNN model is also effective for the more general demosaicing problem with spatially varying exposure and color and can be used for taking images of higher dynamic ranges with a single shot. The proposed models and the thorough experiments together demonstrate that CNN is an effective and versatile tool for solving the demosaicing problem.
ThUnderVolt: Enabling Aggressive Voltage Underscaling and Timing Error Resilience for Energy Efficient Deep Neural Network Accelerators
Venue: arXiv cs.NE 2018
Year: 2018

Hardware accelerators are being increasingly deployed to boost the performance and energy efficiency of deep neural network (DNN) inference. In this paper we propose Thundervolt, a new framework that enables aggressive voltage underscaling of high-performance DNN accelerators without compromising classification accuracy even in the presence of high timing error rates. Using post-synthesis timing simulations of a DNN accelerator modeled on the Google TPU, we show that Thundervolt enables between 34%-57% energy savings on state-of-the-art speech and image recognition benchmarks with less than 1% loss in classification accuracy and no performance loss. Further, we show that Thundervolt is synergistic with and can further increase the energy efficiency of commonly used run-time DNN pruning techniques like Zero-Skip.
A Systems Theory Approach to the Synthesis of Minimum Noise Phase-Insensitive Quantum Amplifiers
Venue: arXiv cs.SY 2018
Year: 2018

We present a systems theory approach to the proof of a result bounding the required level of added quantum noise in a phase-insensitive quantum amplifier. We also present a synthesis procedure for constructing a quantum optical phase-insensitive quantum amplifier which adds the minimum level of quantum noise and achieves a required gain and bandwidth. This synthesis procedure is based on a singularly perturbed quantum system and leads to an amplifier involving two squeezers and two beamsplitters.
How to Match when All Vertices Arrive Online
Venue: arXiv cs.DS 2018
Year: 2018

We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors' arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc. We show that the Ranking algorithm by Karp et al. (STOC 1990) is $0.5211$-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats $0.5$ on general graphs in an online matching problem, a first step towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between $0.5541$ and $0.5671$. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be $0.6317 < 1-\frac{1}{e}$-competitive in our model even for bipartite graphs.
Deep feature compression for collaborative object detection
Venue: arXiv cs.CV 2018
Year: 2018

Recent studies have shown that the efficiency of deep neural networks in mobile applications can be significantly improved by distributing the computational workload between the mobile device and the cloud. This paradigm, termed collaborative intelligence, involves communicating feature data between the mobile and the cloud. The efficiency of such approach can be further improved by lossy compression of feature data, which has not been examined to date. In this work we focus on collaborative object detection and study the impact of both near-lossless and lossy compression of feature data on its accuracy. We also propose a strategy for improving the accuracy under lossy feature compression. Experiments indicate that using this strategy, the communication overhead can be reduced by up to 70% without sacrificing accuracy.
Dynamic monopolies for interval graphs with bounded thresholds
Venue: arXiv cs.DM 2018
Year: 2018

For a graph $G$ and an integer-valued threshold function $τ$ on its vertex set, a dynamic monopoly is a set of vertices of $G$ such that iteratively adding to it vertices $u$ of $G$ that have at least $τ(u)$ neighbors in it eventually yields the vertex set of $G$. We show that the problem of finding a dynamic monopoly of minimum order can be solved in polynomial time for interval graphs with bounded threshold functions, but is NP-hard for chordal graphs allowing unbounded threshold functions.
Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Case
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we study the Empirical Risk Minimization problem in the non-interactive local model of differential privacy. In the case of constant or low dimensionality ($p\ll n$), we first show that if the ERM loss function is $(\infty, T)$-smooth, then we can avoid a dependence of the sample complexity, to achieve error $α$, on the exponential of the dimensionality $p$ with base $1/α$ (i.e., $α^{-p}$), which answers a question in [smith 2017 interaction]. Our approach is based on polynomial approximation. Then, we propose player-efficient algorithms with $1$-bit communication complexity and $O(1)$ computation cost for each player. The error bound is asymptotically the same as the original one. Also with additional assumptions we show a server efficient algorithm. Next we consider the high dimensional case ($n\ll p$), we show that if the loss function is Generalized Linear function and convex, then we could get an error bound which is dependent on the Gaussian width of the underlying constrained set instead of $p$, which is lower than that in [smith 2017 interaction].
Urban vs. rural divide in HTTPS implementation for hospital websites in Illinois
Venue: arXiv cs.CY 2018
Year: 2018

The Hypertext Transfer Protocol Secure (HTTPS) communications protocol is used to secure traffic between a web browser and server. This technology can significantly reduce the risk of interception and manipulation of web information for nefarious purposes such as identity theft. Deployment of HTTPS has reached about 50% of all webs sites. Little is known about HTTPS implantation for hospital websites. To investigate the prevalence of HTTPS implementation, we analyzed the websites of the 210 public hospitals in the state of Illinois, USA. HTTPS was implemented to industry standards for 54% of all hospital websites in Illinois. Geographical analysis showed an urban vs. rural digital divide with 60% of urban hospitals and 40% of rural hospitals implementing HTTPS.