OpenRaiser/Intern-Atlas huggingface dataset:
M3A: Model, MetaModel, and Anomaly Detection in Web Searches
Venue: arXiv cs.IR 2016
Year: 2016

'Alice' is submitting one web search per five minutes, for three hours in a row - is it normal? How to detect abnormal search behaviors, among Alice and other users? Is there any distinct pattern in Alice's (or other users') search behavior? We studied what is probably the largest, publicly available, query log that contains more than 30 million queries from 0.6 million users. In this paper, we present a novel, user-and group-level framework, M3A: Model, MetaModel and Anomaly detection. For each user, we discover and explain a surprising, bi-modal pattern of the inter-arrival time (IAT) of landed queries (queries with user click-through). Specifically, the model Camel-Log is proposed to describe such an IAT distribution; we then notice the correlations among its parameters at the group level. Thus, we further propose the metamodel Meta-Click, to capture and explain the two-dimensional, heavy-tail distribution of the parameters. Combining Camel-Log and Meta-Click, the proposed M3A has the following strong points: (1) the accurate modeling of marginal IAT distribution, (2) quantitative interpretations, and (3) anomaly detection.
Information Bounds and Flatness Factor Approximation for Fading Wiretap MIMO Channels
Venue: arXiv cs.IT 2016
Year: 2016

In this article, the design of secure lattice coset codes for general wireless channels with fading and Gaussian noise is studied. Recalling the eavesdropper's probability and information bounds, a variant of the latter is given from which it is explicitly seen that both quantities are upper bounded by (increasing functions of) the expected flatness factor of the faded lattice related to the eavesdropper. By making use of a recently developed approximation of the theta series of a lattice, it is further shown how the average flatness factor can be approximated numerically. In particular, based on the numerical computations, the average flatness factor not only bounds but also orders correctly the performance of different lattices.
Quantifying and Reducing Stereotypes in Word Embeddings
Venue: arXiv cs.CL 2016
Year: 2016

Machine learning algorithms are optimized to model statistical properties of the training data. If the input data reflects stereotypes and biases of the broader society, then the output of the learning algorithm also captures these stereotypes. In this paper, we initiate the study of gender stereotypes in {\em word embedding}, a popular framework to represent text data. As their use becomes increasingly common, applications can inadvertently amplify unwanted stereotypes. We show across multiple datasets that the embeddings contain significant gender stereotypes, especially with regard to professions. We created a novel gender analogy task and combined it with crowdsourcing to systematically quantify the gender bias in a given embedding. We developed an efficient algorithm that reduces gender stereotype using just a handful of training examples while preserving the useful geometric properties of the embedding. We evaluated our algorithm on several metrics. While we focus on male/female stereotypes, our framework may be applicable to other types of embedding biases.
A Boltzmann Machine Implementation for the D-Wave
Venue: arXiv cs.ET 2016
Year: 2016

The D-Wave is an adiabatic quantum computer. It is an understatement to say that it is not a traditional computer. It can be viewed as a computational accelerator or more precisely a computational oracle, where one asks it a relevant question and it returns a useful answer. The question is how do you ask a relevant question and how do you use the answer it returns. This paper addresses these issues in a way that is pertinent to machine learning. A Boltzmann machine is implemented with the D-Wave since the D-Wave is merely a hardware instantiation of a partially connected Boltzmann machine. This paper presents a prototype implementation of a 3-layered neural network where the D-Wave is used as the middle (hidden) layer of the neural network. This paper also explains how the D-Wave can be utilized in a multi-layer neural network (more than 3 layers) and one in which each layer may be multiple times the size of the D-Wave being used.
Polymetric Rhythmic Feel for a Cognitive Drum Computer
Venue: arXiv cs.SD 2016
Year: 2016

This paper addresses a question about music cognition: how do we derive polymetric structures. A preference rule system is presented which is implemented into a drum computer. The preference rule system allows inferring local polymetric structures, like two-over-three and three-over-two. By analyzing the micro-timing of West African percussion music a timing pattern consisting of six pulses was discovered. It integrates binary and ternary rhythmic feels. The presented drum computer integrates the discovered superimposed polymetric swing (timing and velocity) appropriate to the rhythmic sequence the user inputs. For binary sequences, the amount of binary swing is increased and for ternary sequences, the ternary swing is increased.
Parallel Priority-Flood Depression Filling For Trillion Cell Digital Elevation Models On Desktops Or Clusters
Venue: arXiv cs.DC 2016
Year: 2016

Algorithms for extracting hydrologic features and properties from digital elevation models (DEMs) are challenged by large datasets, which often cannot fit within a computer's RAM. Depression filling is an important preconditioning step to many of these algorithms. Here, I present a new, linearly-scaling algorithm which parallelizes the Priority-Flood depression-filling algorithm by subdividing a DEM into tiles. Using a single-producer, multi-consumer design, the new algorithm works equally well on one core, multiple cores, or multiple machines and can take advantage of large memories or cope with small ones. Unlike previous algorithms, the new algorithm guarantees a fixed number of memory access and communication events per subdivision of the DEM. In comparison testing, this results in the new algorithm running generally faster while using fewer resources than previous algorithms. For moderately sized tiles, the algorithm exhibits ~60% strong and weak scaling efficiencies up to 48 cores, and linear time scaling across datasets ranging over three orders of magnitude. The largest dataset on which I run the algorithm has 2 trillion (2*10^12) cells. With 48 cores, processing required 4.8 hours wall-time (9.3 compute-days). This test is three orders of magnitude larger than any previously performed in the literature. Complete, well-commented source code and correctness tests are available for download from a repository.
Uncalibrated 3D Room Reconstruction from Sound
Venue: arXiv cs.SD 2016
Year: 2016

This paper presents a method to reconstruct the 3D structure of generic convex rooms from sound signals. Differently from most of the previous approaches, the method is fully uncalibrated in the sense that no knowledge about the microphones and sources position is needed. Moreover, we demonstrate that it is possible to bypass the well known echo labeling problem, allowing to reconstruct the room shape in a reasonable computation time without the need of additional hypotheses on the echoes order of arrival. Finally, the method is intrinsically robust to outliers and missing data in the echoes detection, allowing to work also in low SNR conditions. The proposed pipeline formalises the problem in different steps such as time of arrival estimation, microphones and sources localization and walls estimation. After providing a solution to these different problems we present a global optimization approach that links together all the problems in a single optimization function. The accuracy and robustness of the method is assessed on a wide set of simulated setups and in a challenging real scenario. Moreover we make freely available for a challenging dataset for 3D room reconstruction with accurate ground truth in a real scenario.
Enabling Effective FPGA Debug using Overlays: Opportunities and Challenges
Venue: arXiv cs.AR 2016
Year: 2016

FPGAs are going mainstream. Major companies that were not traditionally FPGA-focused are now seeking ways to exploit the benefits of reconfigurable technology and provide it to their customers. In order to do so, a debug ecosystem that provides for effective visibility into a working design and quick debug turn-around times is essential. Overlays have the opportunity to play a key role in this ecosystem. In this overview paper, we discuss how an overlay fabric that allows the user to rapidly add debug instrumentation to a design can be created and exploited. We discuss the requirements of such an overlay and some of the research challenges and opportunities that need to be addressed. To make our exposition concrete, we use two previously-published examples of overlays that have been developed to implement debug instrumentation.
A Cloud-Based and RESTful Internet of Things Platform to Foster Smart Grid Technologies Integration and Re-Usability
Venue: arXiv cs.NI 2016
Year: 2016

Currently, one of the hottest topics in the Internet of Things (IoT) research domain regards the issue to overcome the heterogeneity of proprietary technologies and systems so as to enable the integration of applications and devices developed for different environments in a single interoperable framework. Towards this objective, virtualization is widely used to foster integration and creation of new services and applications. Similar benefits are expected by its application in the smart grid arena. The use of a virtualization middleware is expected to enrich the capabilities and opportunities related to the use of smart grid devices. In this paper, we propose key features for an interoperable, re-usable, elastic and secure smart grid architecture which is cloud-based and relies on REST APIs. To highlight the benefits, a practical case study is presented, where outlined functionalities are implemented in a cloud-based IoT platform. The advantages brought by the proposed middleware in terms of interoperability, re-usability, privacy and elasticity of the underlying infrastructure are discussed.
Discretized Approaches to Schematization
Venue: arXiv cs.CG 2016
Year: 2016

To produce cartographic maps, simplification is typically used to reduce complexity of the map to a legible level. With schematic maps, however, this simplification is pushed far beyond the legibility threshold and is instead constrained by functional need and resemblance. Moreover, stylistic geometry is often used to convey the schematic nature of the map. In this paper we explore discretized approaches to computing a schematic shape $S$ for a simple polygon $P$. We do so by overlaying a plane graph $G$ on $P$ as the solution space for the schematic shape. Topological constraints imply that $S$ should describe a simple polygon. We investigate two approaches, simple map matching and connected face selection, based on commonly used similarity metrics. With the former, $S$ is a simple cycle $C$ in $G$ and we quantify resemblance via the Fréchet distance. We prove that it is NP-hard to compute a cycle that approximates the minimal Fréchet distance over all simple cycles in a plane graph $G$. This result holds even if $G$ is a partial grid graph, if area preservation is required and if we assume a given sequence of turns is specified. With the latter, $S$ is a connected face set in $G$, quantifying resemblance via the symmetric difference. Though the symmetric difference seems a less strict measure, we prove that it is NP-hard to compute the optimal face set. This result holds even if $G$ is full grid graph or a triangular or hexagonal tiling, and if area preservation is required. Moreover, it is independent of whether we allow the set of faces to have holes or not.
An empirical study on large scale text classification with skip-gram embeddings
Venue: arXiv cs.CL 2016
Year: 2016

We investigate the integration of word embeddings as classification features in the setting of large scale text classification. Such representations have been used in a plethora of tasks, however their application in classification scenarios with thousands of classes has not been extensively researched, partially due to hardware limitations. In this work, we examine efficient composition functions to obtain document-level from word-level embeddings and we subsequently investigate their combination with the traditional one-hot-encoding representations. By presenting empirical evidence on large, multi-class, multi-label classification problems, we demonstrate the efficiency and the performance benefits of this combination.
Tracking Time-Vertex Propagation using Dynamic Graph Wavelets
Venue: arXiv cs.LG 2016
Year: 2016

Graph Signal Processing generalizes classical signal processing to signal or data indexed by the vertices of a weighted graph. So far, the research efforts have been focused on static graph signals. However numerous applications involve graph signals evolving in time, such as spreading or propagation of waves on a network. The analysis of this type of data requires a new set of methods that fully takes into account the time and graph dimensions. We propose a novel class of wavelet frames named Dynamic Graph Wavelets, whose time-vertex evolution follows a dynamic process. We demonstrate that this set of functions can be combined with sparsity based approaches such as compressive sensing to reveal information on the dynamic processes occurring on a graph. Experiments on real seismological data show the efficiency of the technique, allowing to estimate the epicenter of earthquake events recorded by a seismic network.
Plug-and-Play Model Predictive Control for Load Shaping and Voltage Control in Smart Grids
Venue: arXiv cs.SY 2016
Year: 2016

This paper presents a predictive controller for handling plug-and-play (P&P) charging requests of flexible loads in a distribution system. We define two types of flexible loads: (i) deferrable loads that have a fixed power profile but can be deferred in time and (ii) shapeable loads that have flexible power profiles but fixed energy requests, such as Plug-in Electric Vehicles (PEVs). The proposed method uses a hierarchical control scheme based on a model predictive control (MPC) formulation for minimizing the global system cost. The first stage computes a reachable reference that trades off deviation from the nominal voltage with the required generation control. The second stage uses a price-based objective to aggregate flexible loads and provide load shaping services, while satisfying system constraints and users' preferences at all times. It is shown that the proposed controller is recursively feasible under specific conditions, i.e. the flexible load demands are satisfied and bus voltages remain within the desired limits. Finally, the proposed scheme is illustrated on a 55 bus radial distribution network.
Resilient Supervisory Control of Autonomous Intersections in the Presence of Sensor Attacks
Venue: arXiv cs.SY 2016
Year: 2016

Cyber-physical systems (CPS), such as autonomous vehicles crossing an intersection, are vulnerable to cyber-attacks and their safety-critical nature makes them a target for malicious adversaries. This paper studies the problem of supervisory control of autonomous intersections in the presence of sensor attacks. Sensor attacks are performed when an adversary gains access to the transmission channel and corrupts the measurements before they are received by the decision-making unit. We show that the supervisory control system is vulnerable to sensor attacks that can cause collision or deadlock among vehicles. To improve the system resilience, we introduce a detector in the control architecture and focus on stealthy attacks that cannot be detected but are capable of compromising safety. We then present a resilient supervisory control system that is safe, non-deadlocking, and maximally permissive, despite the presence of disturbances, uncontrolled vehicles, and sensor attacks. Finally, we demonstrate how the resilient supervisor works by considering illustrative examples.
A Delay-Optimal Packet Scheduler for M2M Uplink
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we present a delay-optimal packet scheduler for processing the M2M uplink traffic at the M2M application server (AS). Due to the delay-heterogeneity in uplink traffic, we classify it broadly into delay-tolerant and delay-sensitive traffic. We then map the diverse delay requirements of each class to sigmoidal functions of packet delay and formulate a utility-maximization problem that results in a proportionally fair delay-optimal scheduler. We note that solving this optimization problem is equivalent to solving for the optimal fraction of time each class is served with (preemptive) priority such that it maximizes the system utility. Using Monte-Carlo simulations for the queuing process at AS, we verify the correctness of the analytical result for optimal scheduler and show that it outperforms other state-of-the-art packet schedulers such as weighted round robin, max-weight scheduler, fair scheduler and priority scheduling. We also note that at higher traffic arrival rate, the proposed scheduler results in a near-minimal delay variance for the delay-sensitive traffic which is highly desirable. This comes at the expense of somewhat higher delay variance for delay-tolerant traffic which is usually acceptable due to its delay-tolerant nature.
A Curriculum Learning Method for Improved Noise Robustness in Automatic Speech Recognition
Venue: arXiv cs.CL 2016
Year: 2016

The performance of automatic speech recognition systems under noisy environments still leaves room for improvement. Speech enhancement or feature enhancement techniques for increasing noise robustness of these systems usually add components to the recognition system that need careful optimization. In this work, we propose the use of a relatively simple curriculum training strategy called accordion annealing (ACCAN). It uses a multi-stage training schedule where samples at signal-to-noise ratio (SNR) values as low as 0dB are first added and samples at increasing higher SNR values are gradually added up to an SNR value of 50dB. We also use a method called per-epoch noise mixing (PEM) that generates noisy training samples online during training and thus enables dynamically changing the SNR of our training data. Both the ACCAN and the PEM methods are evaluated on a end-to-end speech recognition pipeline on the Wall Street Journal corpus. ACCAN decreases the average word error rate (WER) on the 20dB to -10dB SNR range by up to 31.4% when compared to a conventional multi-condition training method.
Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions
Venue: arXiv cs.DS 2016
Year: 2016

The \emph{Temp Secretary Problem} was recently introduced by Fiat et al. It is a generalization of the Secretary Problem, in which commitments are temporary for a fixed duration. We present a simple online algorithm with improved performance guarantees for cases already considered by Fiat et al.\ and give competitive ratios for new generalizations of the problem. In the classical setting, where candidates have identical contract durations $γ\ll 1$ and we are allowed to hire up to $B$ candidates simultaneously, our algorithm is $(\frac{1}{2} - O(\sqrtγ))$-competitive. For large $B$, the bound improves to $1 - O\left(\frac{1}{\sqrt{B}}\right) - O(\sqrtγ)$. Furthermore we generalize the problem from cardinality constraints towards general packing constraints. We achieve a competitive ratio of $1 - O\left(\sqrt{\frac{(1+\log d + \log B)}{B}}\right) -O(\sqrtγ)$, where $d$ is the sparsity of the constraint matrix and $B$ is generalized to the capacity ratio of linear constraints. Additionally we extend the problem towards arbitrary hiring durations. Our algorithmic approach is a relaxation that aggregates all temporal constraints into a non-temporal constraint. Then we apply a linear scaling algorithm that, on every arrival, computes a tentative solution on the input that is known up to this point. This tentative solution uses the non-temporal, relaxed constraints scaled down linearly by the amount of time that has already passed.
An Approach for Parallel Genetic Algorithms in the Cloud using Software Containers
Venue: arXiv cs.NE 2016
Year: 2016

Genetic Algorithms (GAs) are a powerful technique to address hard optimisation problems. However, scalability issues might prevent them from being applied to real-world problems. Exploiting parallel GAs in the cloud might be an affordable approach to get time efficient solutions that benefit of the appealing features of the cloud, such as scalability, reliability, fault-tolerance and cost-effectiveness. Nevertheless, distributed computation is very prone to cause considerable overhead for communication and making GAs distributed in an on-demand fashion is not trivial. Aiming to keep under control the communication overhead and support GAs developers in the construction and deployment of parallel GAs in the cloud, in this paper we propose an approach to distribute GAs using the global parallelisation model, exploiting software containers and their cloud orchestration. We also devised a conceptual workflow covering each cloud GAs distribution phase, from resources allocation to actual deployment and execution, in a DevOps fashion.
Towards stationary time-vertex signal processing
Venue: arXiv cs.LG 2016
Year: 2016

Graph-based methods for signal processing have shown promise for the analysis of data exhibiting irregular structure, such as those found in social, transportation, and sensor networks. Yet, though these systems are often dynamic, state-of-the-art methods for signal processing on graphs ignore the dimension of time, treating successive graph signals independently or taking a global average. To address this shortcoming, this paper considers the statistical analysis of time-varying graph signals. We introduce a novel definition of joint (time-vertex) stationarity, which generalizes the classical definition of time stationarity and the more recent definition appropriate for graphs. Joint stationarity gives rise to a scalable Wiener optimization framework for joint denoising, semi-supervised learning, or more generally inversing a linear operator, that is provably optimal. Experimental results on real weather data demonstrate that taking into account graph and time dimensions jointly can yield significant accuracy improvements in the reconstruction effort.
Some comments on the reliability of NOAA's Storm Events Database
Venue: arXiv cs.OH 2016
Year: 2016

Storms and other severe weather events can result in fatalities, injuries, and property damage. Therefore, preventing such outcomes to the extent possible is a key concern, and the scientific community faces an increasing demand for regularly updated appraisals of evolving climate conditions and extreme weather. NOAA's Storm Events Database is undoubtedly an invaluable resource to the general public, to the professional, and to the researcher. Due to such importance, the primary objective of this study was to explore this database and get clues about its reliability. A complete investigation of the damage estimates, injuries or fatalities figures is unfeasible due to the extension of the database. However, an exploratory data analysis with the resources of the R statistical data analysis language found that damage reports are missing in more than half of the records, that part of the damage values are incorrect, and that, despite all efforts of standardizations, non-standard event type names are still finding their way into the database. These few results are enough to demonstrate that the database suffers from incompleteness and inconsistencies and should not be used without taking reservations and appropriate precautions before advancing any inferences from the data.