OpenRaiser/Intern-Atlas huggingface dataset:
Online Resource Allocation under Partially Predictable Demand
Venue: arXiv cs.DS 2018
Year: 2018

For online resource allocation problems, we propose a new demand arrival model where the sequence of arrivals contains both an adversarial component and a stochastic one. Our model requires no demand forecasting; however, due to the presence of the stochastic component, we can partially predict future demand as the sequence of arrivals unfolds. Under the proposed model, we study the problem of the online allocation of a single resource to two types of customers, and design online algorithms that outperform existing ones. Our algorithms are adjustable to the relative size of the stochastic component, and our analysis reveals that as the portion of the stochastic component grows, the loss due to making online decisions decreases. This highlights the value of (even partial) predictability in online resource allocation. We impose no conditions on how the resource capacity scales with the maximum number of customers. However, we show that using an adaptive algorithm---which makes online decisions based on observed data---is particularly beneficial when capacity scales linearly with the number of customers. Our work serves as a first step in bridging the long-standing gap between the two well-studied approaches to the design and analysis of online algorithms based on (1) adversarial models and (2) stochastic ones. Using novel algorithm design, we demonstrate that even if the arrival sequence contains an adversarial component, we can take advantage of the limited information that the data reveals to improve allocation decisions. We also study the classical secretary problem under our proposed arrival model, and we show that randomizing over multiple stopping rules may increase the probability of success.
anthem: Transforming gringo Programs into First-Order Theories (Preliminary Report)
Venue: arXiv cs.LO 2018
Year: 2018

In a recent paper by Harrison et al., the concept of program completion is extended to a large class of programs in the input language of the ASP grounder gringo. We would like to automate the process of generating and simplifying completion formulas for programs in that language, because examining the output produced by this kind of software may help programmers to see more clearly what their program does and to what degree its set of stable models conforms with their intentions. If a formal specification for the program is available, then it may be possible to use this software, in combination with automated reasoning tools, to verify that the program is correct. This note is a preliminary report on a project motivated by this idea.
Master of Web Puppets: Abusing Web Browsers for Persistent and Stealthy Computation
Venue: arXiv cs.CR 2018
Year: 2018

The proliferation of web applications has essentially transformed modern browsers into small but powerful operating systems. Upon visiting a website, user devices run implicitly trusted script code, the execution of which is confined within the browser to prevent any interference with the user's system. Recent JavaScript APIs, however, provide advanced capabilities that not only enable feature-rich web applications, but also allow attackers to perform malicious operations despite the confined nature of JavaScript code execution. In this paper, we demonstrate the powerful capabilities that modern browser APIs provide to attackers by presenting MarioNet: a framework that allows a remote malicious entity to control a visitor's browser and abuse its resources for unwanted computation or harmful operations, such as cryptocurrency mining, password-cracking, and DDoS. MarioNet relies solely on already available HTML5 APIs, without requiring the installation of any additional software. In contrast to previous browser-based botnets, the persistence and stealthiness characteristics of MarioNet allow the malicious computations to continue in the background of the browser even after the user closes the window or tab of the initial malicious website. We present the design, implementation, and evaluation of a prototype system, MarioNet, that is compatible with all major browsers, and discuss potential defense strategies to counter the threat of such persistent in-browser attacks. Our main goal is to raise awareness regarding this new class of attacks, and inform the design of future browser APIs so that they provide a more secure client-side environment for web applications.
Bayesian Transfer Reinforcement Learning with Prior Knowledge Rules
Venue: arXiv cs.LG 2018
Year: 2018

We propose a probabilistic framework to directly insert prior knowledge in reinforcement learning (RL) algorithms by defining the behaviour policy as a Bayesian posterior distribution. Such a posterior combines task specific information with prior knowledge, thus allowing to achieve transfer learning across tasks. The resulting method is flexible and it can be easily incorporated to any standard off-policy and on-policy algorithms, such as those based on temporal differences and policy gradients. We develop a specific instance of this Bayesian transfer RL framework by expressing prior knowledge as general deterministic rules that can be useful in a large variety of tasks, such as navigation tasks. Also, we elaborate more on recent probabilistic and entropy-regularised RL by developing a novel temporal learning algorithm and show how to combine it with Bayesian transfer RL. Finally, we demonstrate our method for solving mazes and show that significant speed ups can be obtained.
Optimization of Bit Mapping and Quantized Decoding for Off-the-Shelf Protograph LDPC Codes with Application to IEEE 802.3ca
Venue: arXiv cs.IT 2018
Year: 2018

Protograph-based, off-the-shelf low-density parity-check (LDPC) codes are optimized for higher-order modulation and quantized sum-product decoders. As an example, for the recently proposed LDPC code from the upcoming IEEE 802.3ca standard for passive optical networks (PONs), an optimized mapping of the bit channels originating from bit-metric decoding to the protograph variable nodes gains 0.4 dB and 0.3 dB at a bit-error rate of 1e-6 for shaped and uniform signaling, respectively. Furthermore, the clipping value for a quantized sum-product LDPC decoder is optimized via discretized density evolution.
Layer-compensated Pruning for Resource-constrained Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Resource-efficient convolution neural networks enable not only the intelligence on edge devices but also opportunities in system-level optimization such as scheduling. In this work, we aim to improve the performance of resource-constrained filter pruning by merging two sub-problems commonly considered, i.e., (i) how many filters to prune for each layer and (ii) which filters to prune given a per-layer pruning budget, into a global filter ranking problem. Our framework entails a novel algorithm, dubbed layer-compensated pruning, where meta-learning is involved to determine better solutions. We show empirically that the proposed algorithm is superior to prior art in both effectiveness and efficiency. Specifically, we reduce the accuracy gap between the pruned and original networks from 0.9% to 0.7% with 8x reduction in time needed for meta-learning, i.e., from 1 hour down to 7 minutes. To this end, we demonstrate the effectiveness of our algorithm using ResNet and MobileNetV2 networks under CIFAR-10, ImageNet, and Bird-200 datasets.
Direct optimization of F-measure for retrieval-based personal question answering
Venue: arXiv cs.IR 2018
Year: 2018

Recent advances in spoken language technologies and the introduction of many customer facing products, have given rise to a wide customer reliance on smart personal assistants for many of their daily tasks. In this paper, we present a system to reduce users' cognitive load by extending personal assistants with long-term personal memory where users can store and retrieve by voice, arbitrary pieces of information. The problem is framed as a neural retrieval based question answering system where answers are selected from previously stored user memories. We propose to directly optimize the end-to-end retrieval performance, measured by the F1-score, using reinforcement learning, leading to better performance on our experimental test set(s).
Adaptive Planar Point Location
Venue: arXiv cs.CG 2018
Year: 2018

We present self-adjusting data structures for answering point location queries in convex and connected subdivisions. Let $n$ be the number of vertices in a convex or connected subdivision. Our structures use $O(n)$ space. For any convex subdivision $S$, our method processes any online query sequence $σ$ in $O(\mathrm{OPT} + n)$ time, where $\mathrm{OPT}$ is the minimum time required by any linear decision tree for answering point location queries in $S$ to process $σ$. For connected subdivisions, the processing time is $O(\mathrm{OPT} + n + |σ|\log(\log^* n))$. In both cases, the time bound includes the $O(n)$ preprocessing time.
Throughput Optimizations for FPGA-based Deep Neural Network Inference
Venue: arXiv cs.DC 2018
Year: 2018

Deep neural networks are an extremely successful and widely used technique for various pattern recognition and machine learning tasks. Due to power and resource constraints, these computationally intensive networks are difficult to implement in embedded systems. Yet, the number of applications that can benefit from the mentioned possibilities is rapidly rising. In this paper, we propose novel architectures for the inference of previously learned and arbitrary deep neural networks on FPGA-based SoCs that are able to overcome these limitations. Our key contributions include the reuse of previously transferred weight matrices across multiple input samples, which we refer to as batch processing, and the usage of compressed weight matrices, also known as pruning. An extensive evaluation of these optimizations is presented. Both techniques allow a significant mitigation of data transfers and speed-up the network inference by one order of magnitude. At the same time, we surpass the data throughput of fully-featured x86-based systems while only using a fraction of their energy consumption.
Benchmark Analysis of Representative Deep Neural Network Architectures
Venue: arXiv cs.CV 2018
Year: 2018

This work presents an in-depth analysis of the majority of the deep neural networks (DNNs) proposed in the state of the art for image recognition. For each DNN multiple performance indices are observed, such as recognition accuracy, model complexity, computational complexity, memory usage, and inference time. The behavior of such performance indices and some combinations of them are analyzed and discussed. To measure the indices we experiment the use of DNNs on two different computer architectures, a workstation equipped with a NVIDIA Titan X Pascal and an embedded system based on a NVIDIA Jetson TX1 board. This experimentation allows a direct comparison between DNNs running on machines with very different computational capacity. This study is useful for researchers to have a complete view of what solutions have been explored so far and in which research directions are worth exploring in the future; and for practitioners to select the DNN architecture(s) that better fit the resource constraints of practical deployments and applications. To complete this work, all the DNNs, as well as the software used for the analysis, are available online.
Truly Concurrent Process Algebra Is Reversible
Venue: arXiv cs.LO 2018
Year: 2018

Based on our previous process algebra for concurrency APTC, we prove that it is reversible with a little modifications. The reversible algebra has four parts: Basic Algebra for Reversible True Concurrency (BARTC), Algebra for Parallelism in Reversible True Concurrency (APRTC), recursion and abstraction.
Visual Curiosity: Learning to Ask Questions to Learn Visual Recognition
Venue: arXiv cs.RO 2018
Year: 2018

In an open-world setting, it is inevitable that an intelligent agent (e.g., a robot) will encounter visual objects, attributes or relationships it does not recognize. In this work, we develop an agent empowered with visual curiosity, i.e. the ability to ask questions to an Oracle (e.g., human) about the contents in images (e.g., What is the object on the left side of the red cube?) and build visual recognition model based on the answers received (e.g., Cylinder). In order to do this, the agent must (1) understand what it recognizes and what it does not, (2) formulate a valid, unambiguous and informative language query (a question) to ask the Oracle, (3) derive the parameters of visual classifiers from the Oracle response and (4) leverage the updated visual classifiers to ask more clarified questions. Specifically, we propose a novel framework and formulate the learning of visual curiosity as a reinforcement learning problem. In this framework, all components of our agent, visual recognition module (to see), question generation policy (to ask), answer digestion module (to understand) and graph memory module (to memorize), are learned entirely end-to-end to maximize the reward derived from the scene graph obtained by the agent as a consequence of the dialog with the Oracle. Importantly, the question generation policy is disentangled from the visual recognition system and specifics of the environment. Consequently, we demonstrate a sort of double generalization. Our question generation policy generalizes to new environments and a new pair of eyes, i.e., new visual system. Trained on a synthetic dataset, our results show that our agent learns new visual concepts significantly faster than several heuristic baselines, even when tested on synthetic environments with novel objects, as well as in a realistic environment.
Learning Hash Codes via Hamming Distance Targets
Venue: arXiv cs.LG 2018
Year: 2018

We present a powerful new loss function and training scheme for learning binary hash codes with any differentiable model and similarity function. Our loss function improves over prior methods by using log likelihood loss on top of an accurate approximation for the probability that two inputs fall within a Hamming distance target. Our novel training scheme obtains a good estimate of the true gradient by better sampling inputs and evaluating loss terms between all pairs of inputs in each minibatch. To fully leverage the resulting hashes, we use multi-indexing. We demonstrate that these techniques provide large improvements to a similarity search tasks. We report the best results to date on competitive information retrieval tasks for ImageNet and SIFT 1M, improving MAP from 73% to 84% and reducing query cost by a factor of 2-8, respectively.
Fighting Against XSS Attacks: A Usability Evaluation of OWASP ESAPI Output Encoding
Venue: arXiv cs.CR 2018
Year: 2018

Cross Site Scripting (XSS) is one of the most critical vulnerabilities exist in web applications. XSS can be prevented by encoding untrusted data that are loaded into browser content of web applications. Security Application Programming Interfaces (APIs) such as OWASP ESAPI provide output encoding functionalities for programmers to use to protect their applications from XSS attacks. However, XSS still being ranked as one of the most critical vulnerabilities in web applications suggests that programmers are not effectively using those APIs to encode untrusted data. Therefore, we conducted an experimental study with 10 programmers where they attempted to fix XSS vulnerabilities of a web application using the output encoding functionality of OWASP ESAPI. Results revealed 3 types of mistakes that programmers made which resulted in them failing to fix the application by removing XSS vulnerabilities. We also identified 16 usability issues of OWASP ESAPI. We identified that some of these usability issues as the reason for mistakes that programmers made. Based on these results, we provided suggestions on how the usability of output encoding APIs should be improved to give a better experience to programmers.
NU-LiteNet: Mobile Landmark Recognition using Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

The growth of high-performance mobile devices has resulted in more research into on-device image recognition. The research problems are the latency and accuracy of automatic recognition, which remains obstacles to its real-world usage. Although the recently developed deep neural networks can achieve accuracy comparable to that of a human user, some of them still lack the necessary latency. This paper describes the development of the architecture of a new convolutional neural network model, NU-LiteNet. For this, SqueezeNet was developed to reduce the model size to a degree suitable for smartphones. The model size of NU-LiteNet is therefore 2.6 times smaller than that of SqueezeNet. The recognition accuracy of NU-LiteNet also compared favorably with other recently developed deep neural networks, when experiments were conducted on two standard landmark databases.
DATC RDF: An Open Design Flow from Logic Synthesis to Detailed Routing
Venue: arXiv cs.OH 2018
Year: 2018

In this paper, we present DATC Robust Design Flow (RDF) from logic synthesis to detailed routing. Our goals are 1) to provide an open-source academic design flow from logic synthesis to detailed routing based on existing contest results, 2) to construct a database for design benchmarks and point tool libraries, and 3) to interact with industrial designs by using industrial standard design input/output formats. We also demonstrate RDF in a scalable cloud infrastructure. Design methodology and cross-stage optimization research can be conducted via RDF.
Target Aware Network Adaptation for Efficient Representation Learning
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents an automatic network adaptation method that finds a ConvNet structure well-suited to a given target task, e.g., image classification, for efficiency as well as accuracy in transfer learning. We call the concept target-aware transfer learning. Given only small-scale labeled data, and starting from an ImageNet pre-trained network, we exploit a scheme of removing its potential redundancy for the target task through iterative operations of filter-wise pruning and network optimization. The basic motivation is that compact networks are on one hand more efficient and should also be more tolerant, being less complex, against the risk of overfitting which would hinder the generalization of learned representations in the context of transfer learning. Further, unlike existing methods involving network simplification, we also let the scheme identify redundant portions across the entire network, which automatically results in a network structure adapted to the task at hand. We achieve this with a few novel ideas: (i) cumulative sum of activation statistics for each layer, and (ii) a priority evaluation of pruning across multiple layers. Experimental results by the method on five datasets (Flower102, CUB200-2011, Dog120, MIT67, and Stanford40) show favorable accuracies over the related state-of-the-art techniques while enhancing the computational and storage efficiency of the transferred model.
AI Benchmark: Running Deep Neural Networks on Android Smartphones
Venue: arXiv cs.AI 2018
Year: 2018

Over the last years, the computational power of mobile devices such as smartphones and tablets has grown dramatically, reaching the level of desktop computers available not long ago. While standard smartphone apps are no longer a problem for them, there is still a group of tasks that can easily challenge even high-end devices, namely running artificial intelligence algorithms. In this paper, we present a study of the current state of deep learning in the Android ecosystem and describe available frameworks, programming models and the limitations of running AI on smartphones. We give an overview of the hardware acceleration resources available on four main mobile chipset platforms: Qualcomm, HiSilicon, MediaTek and Samsung. Additionally, we present the real-world performance results of different mobile SoCs collected with AI Benchmark that are covering all main existing hardware configurations.
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
Venue: arXiv cs.DS 2018
Year: 2018

We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs (FOCS 2014). It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem.
Learning Discriminators as Energy Networks in Adversarial Learning
Venue: arXiv cs.CV 2018
Year: 2018

We propose a novel framework for structured prediction via adversarial learning. Existing adversarial learning methods involve two separate networks, i.e., the structured prediction models and the discriminative models, in the training. The information captured by discriminative models complements that in the structured prediction models, but few existing researches have studied on utilizing such information to improve structured prediction models at the inference stage. In this work, we propose to refine the predictions of structured prediction models by effectively integrating discriminative models into the prediction. Discriminative models are treated as energy-based models. Similar to the adversarial learning, discriminative models are trained to estimate scores which measure the quality of predicted outputs, while structured prediction models are trained to predict contrastive outputs with maximal energy scores. In this way, the gradient vanishing problem is ameliorated, and thus we are able to perform inference by following the ascent gradient directions of discriminative models to refine structured prediction models. The proposed method is able to handle a range of tasks, e.g., multi-label classification and image segmentation. Empirical results on these two tasks validate the effectiveness of our learning method.
Disrupting the Coming Robot Stampedes: Designing Resilient Information Ecologies
Venue: arXiv cs.CY 2018
Year: 2018

Machines are designed to communicate widely and efficiently. Humans, less so. We evolved social structures that function best as small subgroups interacting within larger populations. Technology changes this dynamic, by allowing all individuals to be connected at the speed of light. A dense, tightly connected population can behave like a single agent. In animals, this happens in constrained areas where stampedes can easily form. Machines do not need these kinds of conditions. The very techniques used to design best-of-breed solutions may increase the risk of dangerous mass behaviors among homogeneous machines. In this paper we argue that ecologically-based design principles such as the presence of diversity are a broadly effective strategy to defend against unintended consequences at scale.