OpenRaiser/Intern-Atlas huggingface dataset:
Reaching Distributed Equilibrium with Limited ID Space
Venue: arXiv cs.DC 2018
Year: 2018

We examine the relation between the size of the id space and the number of rational agents in a network under which equilibrium in distributed algorithms is possible. When the number of agents in the network is not a-priori known, a single agent may duplicate to gain an advantage, pretending to be more than one agent. However, when the id space is limited, each duplication involves a risk of being caught. By comparing the risk against the advantage, given an id space of size $L$, we provide a method of calculating the minimal threshold $t$, the required number of agents in the network, such that the algorithm is in equilibrium. That is, it is the minimal value of $t$ such that if agents a-priori know that $n \geq t$ then the algorithm is in equilibrium. We demonstrate this method by applying it to two problems, Leader Election and Knowledge Sharing, as well as providing a constant-time approximation $t \approx \frac{L}{5}$ of the minimal threshold for Leader Election.
An Efficient SIMD Implementation of Pseudo-Verlet Lists for Neighbour Interactions in Particle-Based Codes
Venue: arXiv cs.DC 2018
Year: 2018

In particle-based simulations, neighbour finding (i.e finding pairs of particles to interact within a given range) is the most time consuming part of the computation. One of the best such algorithms, which can be used for both Molecular Dynamics (MD) and Smoothed Particle Hydrodynamics (SPH) simulations, is the pseudo-Verlet list algorithm. This algorithm, however, does not vectorise trivially, and hence makes it difficult to exploit SIMD-parallel architectures. In this paper, we present several novel modifications as well as a vectorisation strategy for the algorithm which lead to overall speed-ups over the scalar version of the algorithm of 2.24x for the AVX instruction set (SIMD width of 8), 2.43x for AVX2, and 4.07x for AVX-512 (SIMD width of 16).
Weighted Low-Rank Approximation of Matrices and Background Modeling
Venue: arXiv cs.CV 2018
Year: 2018

We primarily study a special a weighted low-rank approximation of matrices and then apply it to solve the background modeling problem. We propose two algorithms for this purpose: one operates in the batch mode on the entire data and the other one operates in the batch-incremental mode on the data and naturally captures more background variations and computationally more effective. Moreover, we propose a robust technique that learns the background frame indices from the data and does not require any training frames. We demonstrate through extensive experiments that by inserting a simple weight in the Frobenius norm, it can be made robust to the outliers similar to the $\ell_1$ norm. Our methods match or outperform several state-of-the-art online and batch background modeling methods in virtually all quantitative and qualitative measures.
Fast Flux Service Network Detection via Data Mining on Passive DNS Traffic
Venue: arXiv cs.CR 2018
Year: 2018

In the last decade, the use of fast flux technique has become established as a common practice to organise botnets in Fast Flux Service Networks (FFSNs), which are platforms able to sustain illegal online services with very high availability. In this paper, we report on an effective fast flux detection algorithm based on the passive analysis of the Domain Name System (DNS) traffic of a corporate network. The proposed method is based on the near-real-time identification of different metrics that measure a wide range of fast flux key features; the metrics are combined via a simple but effective mathematical and data mining approach. The proposed solution has been evaluated in a one-month experiment over an enterprise network, with the injection of pcaps associated with different malware campaigns, that leverage FFSNs and cover a wide variety of attack scenarios. An in-depth analysis of a list of fast flux domains confirmed the reliability of the metrics used in the proposed algorithm and allowed for the identification of many IPs that turned out to be part of two notorious FFSNs, namely Dark Cloud and SandiFlux, to the description of which we therefore contribute. All the fast flux domains were detected with a very low false positive rate; a comparison of performance indicators with previous works show a remarkable improvement.
Are we on the same learning curve: Visualization of Semantic Similarity of Course Objectives
Venue: arXiv cs.HC 2018
Year: 2018

The course description provided by instructors is an important piece of information as it defines what is expected from the instructor and what he/she is going to deliver during a particular course. One of the key components of a course description is the Learning Outcomes section. The contents of this section are used by program managers who are tasked to compare and match two different courses during the development of Transfer Agreements between different institutions. This research introduces the development of visual tools for understanding the two different courses and making comparisons. We designed methods to extract the text from a course description document, developed an algorithm to perform semantic analysis, and displayed the results in a web interface. We are able to achieve the intermediate results of the research which includes extracting, analyzing and visualizing the data.
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Venue: arXiv cs.DS 2018
Year: 2018

In this paper we study the adaptivity of submodular maximization. Adaptivity quantifies the number of sequential rounds that an algorithm makes when function evaluations can be executed in parallel. Adaptivity is a fundamental concept that is heavily studied across a variety of areas in computer science, largely due to the need for parallelizing computation. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, it is well known that a simple greedy algorithm achieves a $1-1/e$ approximation and that this approximation is optimal for polynomial-time algorithms. Somewhat surprisingly, despite extensive efforts on submodular optimization for large-scale datasets, until very recently there was no known algorithm that achieves a constant factor approximation for this problem whose adaptivity is sublinear in the size of the ground set $n$. Recent work by Balkanski and Singer describes an algorithm that obtains an approximation arbitrarily close to $1/3$ in $\mathcal{O}(\log n)$ adaptive rounds and shows that no algorithm can obtain a constant factor approximation in $\tilde{o}(\log n)$ adaptive rounds. This approach achieves an exponential speedup in adaptivity (and parallel running time) at the expense of approximation quality. In this paper we describe a novel approach that yields an algorithm whose approximation is arbitrarily close to the optimal $1-1/e$ guarantee in $\mathcal{O}(\log n)$ adaptive rounds. This algorithm therefore achieves an exponential speedup in parallel running time for submodular maximization at the expense of an arbitrarily small loss in approximation quality. This guarantee is optimal in both approximation and adaptivity, up to lower order terms.
Graph-based Selective Outlier Ensembles
Venue: arXiv cs.LG 2018
Year: 2018

An ensemble technique is characterized by the mechanism that generates the components and by the mechanism that combines them. A common way to achieve the consensus is to enable each component to equally participate in the aggregation process. A problem with this approach is that poor components are likely to negatively affect the quality of the consensus result. To address this issue, alternatives have been explored in the literature to build selective classifier and cluster ensembles, where only a subset of the components contributes to the computation of the consensus. Of the family of ensemble methods, outlier ensembles are the least studied. Only recently, the selection problem for outlier ensembles has been discussed. In this work we define a new graph-based class of ranking selection methods. A method in this class is characterized by two main steps: (1) Mapping the rankings onto a graph structure; and (2) Mining the resulting graph to identify a subset of rankings. We define a specific instance of the graph-based ranking selection class. Specifically, we map the problem of selecting ensemble components onto a mining problem in a graph. An extensive evaluation was conducted on a variety of heterogeneous data and methods. Our empirical results show that our approach outperforms state-of-the-art selective outlier ensemble techniques.
Are FPGAs Suitable for Edge Computing?
Venue: arXiv cs.DC 2018
Year: 2018

The rapid growth of Internet-of-things (IoT) and artificial intelligence applications have called forth a new computing paradigm--edge computing. In this paper, we study the suitability of deploying FPGAs for edge computing from the perspectives of throughput sensitivity to workload size, architectural adaptiveness to algorithm characteristics, and energy efficiency. This goal is accomplished by conducting comparison experiments on an Intel Arria 10 GX1150 FPGA and an Nvidia Tesla K40m GPU. The experiment results imply that the key advantages of adopting FPGAs for edge computing over GPUs are three-fold: 1) FPGAs can provide a consistent throughput invariant to the size of application workload, which is critical to aggregating individual service requests from various IoT sensors; (2) FPGAs offer both spatial and temporal parallelism at a fine granularity and a massive scale, which guarantees a consistently high performance for accelerating both high-concurrency and high-dependency algorithms; and (3) FPGAs feature 3-4 times lower power consumption and up to 30.7 times better energy efficiency, offering better thermal stability and lower energy cost per functionality.
Vision Based Dynamic Offside Line Marker for Soccer Games
Venue: arXiv cs.CV 2018
Year: 2018

Offside detection in soccer has emerged as one of the most important decisions with an average of 50 offside decisions every game. False detections and rash calls adversely affect game conditions and in many cases drastically change the outcome of the game. The human eye has finite precision and can only discern a limited amount of detail in a given instance. Current offside decisions are made manually by sideline referees and tend to remain controversial in many games. This calls for automated offside detection techniques in order to assist accurate refereeing. In this work, we have explicitly used computer vision and image processing techniques like Hough transform, color similarity (quantization), graph connected components, and vanishing point ideas to identify the probable offside regions. Keywords: Hough transform, connected components, KLT tracking, color similarity.
Detecting Linguistic Characteristics of Alzheimer's Dementia by Interpreting Neural Models
Venue: arXiv cs.CL 2018
Year: 2018

Alzheimer's disease (AD) is an irreversible and progressive brain disease that can be stopped or slowed down with medical treatment. Language changes serve as a sign that a patient's cognitive functions have been impacted, potentially leading to early diagnosis. In this work, we use NLP techniques to classify and analyze the linguistic characteristics of AD patients using the DementiaBank dataset. We apply three neural models based on CNNs, LSTM-RNNs, and their combination, to distinguish between language samples from AD and control patients. We achieve a new independent benchmark accuracy for the AD classification task. More importantly, we next interpret what these neural models have learned about the linguistic characteristics of AD patients, via analysis based on activation clustering and first-derivative saliency techniques. We then perform novel automatic pattern discovery inside activation clusters, and consolidate AD patients' distinctive grammar patterns. Additionally, we show that first derivative saliency can not only rediscover previous language patterns of AD patients, but also shed light on the limitations of neural models. Lastly, we also include analysis of gender-separated AD data.
Two-Player Games for Efficient Non-Convex Constrained Optimization
Venue: arXiv cs.LG 2018
Year: 2018

In recent years, constrained optimization has become increasingly relevant to the machine learning community, with applications including Neyman-Pearson classification, robust optimization, and fair machine learning. A natural approach to constrained optimization is to optimize the Lagrangian, but this is not guaranteed to work in the non-convex setting, and, if using a first-order method, cannot cope with non-differentiable constraints (e.g. constraints on rates or proportions). The Lagrangian can be interpreted as a two-player game played between a player who seeks to optimize over the model parameters, and a player who wishes to maximize over the Lagrange multipliers. We propose a non-zero-sum variant of the Lagrangian formulation that can cope with non-differentiable--even discontinuous--constraints, which we call the "proxy-Lagrangian". The first player minimizes external regret in terms of easy-to-optimize "proxy constraints", while the second player enforces the original constraints by minimizing swap regret. For this new formulation, as for the Lagrangian in the non-convex setting, the result is a stochastic classifier. For both the proxy-Lagrangian and Lagrangian formulations, however, we prove that this classifier, instead of having unbounded size, can be taken to be a distribution over no more than m+1 models (where m is the number of constraints). This is a significant improvement in practical terms.
Learning how to be robust: Deep polynomial regression
Venue: arXiv cs.CV 2018
Year: 2018

Polynomial regression is a recurrent problem with a large number of applications. In computer vision it often appears in motion analysis. Whatever the application, standard methods for regression of polynomial models tend to deliver biased results when the input data is heavily contaminated by outliers. Moreover, the problem is even harder when outliers have strong structure. Departing from problem-tailored heuristics for robust estimation of parametric models, we explore deep convolutional neural networks. Our work aims to find a generic approach for training deep regression models without the explicit need of supervised annotation. We bypass the need for a tailored loss function on the regression parameters by attaching to our model a differentiable hard-wired decoder corresponding to the polynomial operation at hand. We demonstrate the value of our findings by comparing with standard robust regression methods. Furthermore, we demonstrate how to use such models for a real computer vision problem, i.e., video stabilization. The qualitative and quantitative experiments show that neural networks are able to learn robustness for general polynomial regression, with results that well overpass scores of traditional robust estimation methods.
UCNN: Exploiting Computational Reuse in Deep Neural Networks via Weight Repetition
Venue: arXiv cs.NE 2018
Year: 2018

Convolutional Neural Networks (CNNs) have begun to permeate all corners of electronic society (from voice recognition to scene generation) due to their high accuracy and machine efficiency per operation. At their core, CNN computations are made up of multi-dimensional dot products between weight and input vectors. This paper studies how weight repetition ---when the same weight occurs multiple times in or across weight vectors--- can be exploited to save energy and improve performance during CNN inference. This generalizes a popular line of work to improve efficiency from CNN weight sparsity, as reducing computation due to repeated zero weights is a special case of reducing computation due to repeated weights. To exploit weight repetition, this paper proposes a new CNN accelerator called the Unique Weight CNN Accelerator (UCNN). UCNN uses weight repetition to reuse CNN sub-computations (e.g., dot products) and to reduce CNN model size when stored in off-chip DRAM ---both of which save energy. UCNN further improves performance by exploiting sparsity in weights. We evaluate UCNN with an accelerator-level cycle and energy model and with an RTL implementation of the UCNN processing element. On three contemporary CNNs, UCNN improves throughput-normalized energy consumption by 1.2x - 4x, relative to a similarly provisioned baseline accelerator that uses Eyeriss-style sparsity optimizations. At the same time, the UCNN processing element adds only 17-24% area overhead relative to the same baseline.
Fast Weight Long Short-Term Memory
Venue: arXiv cs.NE 2018
Year: 2018

Associative memory using fast weights is a short-term memory mechanism that substantially improves the memory capacity and time scale of recurrent neural networks (RNNs). As recent studies introduced fast weights only to regular RNNs, it is unknown whether fast weight memory is beneficial to gated RNNs. In this work, we report a significant synergy between long short-term memory (LSTM) networks and fast weight associative memories. We show that this combination, in learning associative retrieval tasks, results in much faster training and lower test error, a performance boost most prominent at high memory task difficulties.
The Reincarnation of Grille Cipher: A Generative Approach
Venue: arXiv cs.CR 2018
Year: 2018

In order to keep the data secret, various techniques have been implemented to encrypt and decrypt the secret data. Cryptography is committed to the security of content, i.e. it cannot be restored with a given ciphertext. Steganography is to hiding the existence of a communication channel within a stego. However, it has been difficult to construct a cipher (cypher) that simultaneously satisfy both channel and content security for secure communication. Inspired by the Cardan grille, this paper presents a new generative framework for grille cipher. A digital cardan grille is used for message encryption and decryption. The ciphertext is directly sampled by a powerful generator without an explicit cover. Message loss and prior loss are proposed for penalizing message extraction error and unrealistic ciphertext. Jensen-Shannon Divergence is introduced as new criteria for channel security. A simple practical data-driven grille cipher is proposed using semantic image inpainting and generative adversarial network. Experimental results demonstrate the promising of the proposed method.
Design, Simulation, and Testing of a Flexible Actuated Spine for Quadruped Robots
Venue: arXiv cs.RO 2018
Year: 2018

Walking quadruped robots face challenges in positioning their feet and lifting their legs during gait cycles over uneven terrain. The robot Laika is under development as a quadruped with a flexible, actuated spine designed to assist with foot movement and balance during these gaits. This paper presents the first set of hardware designs for the spine of Laika, a physical prototype of those designs, and tests in both hardware and simulations that show the prototype's capabilities. Laika's spine is a tensegrity structure, used for its advantages with weight and force distribution, and represents the first working prototype of a tensegrity spine for a quadruped robot. The spine bends by adjusting the lengths of the cables that separate its vertebrae, and twists using an actuated rotating vertebra at its center. The current prototype of Laika has stiff legs attached to the spine, and is used as a test setup for evaluation of the spine itself. This work shows the advantages of Laika's spine by demonstrating the spine lifting each of the robot's four feet, both as a form of balancing and as a precursor for a walking gait. These foot motions, using specific combinations of bending and rotation movements of the spine, are measured in both simulation and hardware experiments. Hardware data are used to calibrate the simulations, such that the simulations can be used for control of balancing or gait cycles in the future. Future work will attach actuated legs to Laika's spine, and examine balancing and gait cycles when combined with leg movements.
Fast Channel Estimation for Millimetre Wave Wireless Systems Using Overlapped Beam Patterns
Venue: arXiv cs.IT 2018
Year: 2018

This paper is concerned with the channel estimation problem in millimetre wave (MMW) wireless systems with large antenna arrays. By exploiting the sparse nature of the MMW channel, we present an efficient estimation algorithm based on a novel overlapped beam pattern design. The performance of the algorithm is analyzed and an upper bound on the probability of channel estimation failure is derived. Results show that the algorithm can significantly reduce the number of required measurements in channel estimation (e.g., by 225% when a single overlap is used) when compared to the existing channel estimation algorithm based on non-overlapped beam patterns.
Independent Distributions on a Multi-Branching AND-OR Tree of Height 2
Venue: arXiv cs.DS 2018
Year: 2018

We investigate an AND-OR tree T and a probability distribution d on the truth assignments to the leaves. Tarsi (1983) showed that if d is an independent and identical distribution (IID) such that probability of a leaf having value 0 is neither 0 nor 1 then, under a certain assumptions, there exists an optimal algorithm that is depth-first. We investigate the case where d is an independent distribution (ID) and probability depends on each leaf. It is known that in this general case, if height is greater than or equal to 3, Tarsi-type result does not hold. It is also known that for a complete binary tree of height 2, Tarsi-type result certainly holds. In this paper, we ask whether Tarsi-type result holds for an AND-OR tree of height 2. Here, a child node of the root is either an OR-gate or a leaf: The number of child nodes of an internal node is arbitrary, and depends on an internal node. We give an affirmative answer. Our strategy of the proof is to reduce the problem to the case of directional algorithms. We perform induction on the number of leaves, and modify Tarsi's method to suite height 2 trees. We discuss why our proof does not apply to height 3 trees.
Experiments with Universal CEFR Classification
Venue: arXiv cs.CL 2018
Year: 2018

The Common European Framework of Reference (CEFR) guidelines describe language proficiency of learners on a scale of 6 levels. While the description of CEFR guidelines is generic across languages, the development of automated proficiency classification systems for different languages follow different approaches. In this paper, we explore universal CEFR classification using domain-specific and domain-agnostic, theory-guided as well as data-driven features. We report the results of our preliminary experiments in monolingual, cross-lingual, and multilingual classification with three languages: German, Czech, and Italian. Our results show that both monolingual and multilingual models achieve similar performance, and cross-lingual classification yields lower, but comparable results to monolingual classification.
An Improved Reversible Data Hiding Scheme by Changing Modification Direction of Partial Coefficients in JPEG Images
Venue: arXiv cs.MM 2018
Year: 2018

This paper first reviews the reversible data hiding scheme, of Liu et al. in 2018, for JPEG images. After that, a novel reversible data hiding scheme, in which modification directions of partial nonzero quantized alternating current (AC) coefficients are utilized to decrease distortion and file size increase caused by data hiding, is proposed. Experimental results have shown that the proposed scheme has indeed advantages in visual quality and smaller increase in file size of marked JPEG images while compared to the state-of-the-art scheme with the same embedding payload so far.