OpenRaiser/Intern-Atlas huggingface dataset:
Weierstrass Pure Gaps From a Quotient of the Hermitian Curve
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, by employing the results over Kummer extensions, we give an arithmetic characterization of pure gaps at many totally ramified places over the quotients of Hermitian curves, including the well-studied Hermitian curves as special cases. The cardinality of these pure gaps is explicitly investigated. In particular, the numbers of gaps and pure gaps at a pair of distinct places are determined precisely, which can be regarded as an extension of the previous work by Matthews (2001) considered Hermitian curves. Additionally, some concrete examples are provided to illustrate our results.
Annotation of Car Trajectories based on Driving Patterns
Venue: arXiv cs.OH 2017
Year: 2017

Nowadays, the ubiquity of various sensors enables the collection of voluminous datasets of car trajectories. Such datasets enable analysts to make sense of driving patterns and behaviors: in order to understand the behavior of drivers, one approach is to break a trajectory into its underlying patterns and then analyze that trajectory in terms of derived patterns. The process of trajectory segmentation is a function of various resources including a set of ground truth trajectories with their driving patterns. To the best of our knowledge, no such ground-truth dataset exists in the literature. In this paper, we describe a trajectory annotation framework and report our results to annotate a dataset of personal car trajectories. Our annotation methodology consists of a crowd-sourcing task followed by a precise process of aggregation. Our annotation process consists of two granularity levels, one to specify the annotation (segment border) and the other one to describe the type of the segment (e.g. speed-up, turn, merge, etc.). The output of our project, Dataset of Annotated Car Trajectories (DACT), is available online at https://figshare.com/articles/dact_dataset_of_annotated_car_trajectories/5005289 .
Modeling of the Latent Embedding of Music using Deep Neural Network
Venue: arXiv cs.SD 2017
Year: 2017

While both the data volume and heterogeneity of the digital music content is huge, it has become increasingly important and convenient to build a recommendation or search system to facilitate surfacing these content to the user or consumer community. Most of the recommendation models fall into two primary species, collaborative filtering based and content based approaches. Variants of instantiations of collaborative filtering approach suffer from the common issues of so called "cold start" and "long tail" problems where there is not much user interaction data to reveal user opinions or affinities on the content and also the distortion towards the popular content. Content-based approaches are sometimes limited by the richness of the available content data resulting in a heavily biased and coarse recommendation result. In recent years, the deep neural network has enjoyed a great success in large-scale image and video recognitions. In this paper, we propose and experiment using deep convolutional neural network to imitate how human brain processes hierarchical structures in the auditory signals, such as music, speech, etc., at various timescales. This approach can be used to discover the latent factor models of the music based upon acoustic hyper-images that are extracted from the raw audio waves of music. These latent embeddings can be used either as features to feed to subsequent models, such as collaborative filtering, or to build similarity metrics between songs, or to classify music based on the labels for training such as genre, mood, sentiment, etc.
Monitoring Distributed Component-Based Systems
Venue: arXiv cs.SE 2017
Year: 2017

This paper addresses the online monitoring of distributed component-based systems with multi-party interactions against user-provided properties expressed in linear-temporal logic and referring to global states. We consider intrinsically independent components whose interactions are partitioned on distributed controllers. In this context, the problem that arises is that a global state of the system is not available to the monitor. Instead, we attach local controllers to schedulers to retrieve the concurrent local traces. Local traces are sent to a global observer which reconstructs the set of global traces that are compatible with the local ones, in a concurrency-preserving fashion. In this context, the reconstruction of the global traces is done on-the-fly using a lattice of partial states encoding the global traces compatible with the locally-observed traces. We implemented our monitoring approach in a prototype tool called RVDIST. RVDIST executes in parallel with the distributed model and takes as input the events generated from each scheduler and outputs the evaluated computation lattice. Our experiments show that, thanks to the optimisation applied in the online monitoring algorithm, i) the size of the constructed computation lattice is insensitive to the the number of received events, (ii) the lattice size is kept reasonable and (iii) the overhead of the monitoring process is cheap.
Joint Transmission with Limited Backhaul Connectivity
Venue: arXiv cs.IT 2017
Year: 2017

Downlink beamforming techniques with low signaling overhead are proposed for joint processing coordinated (JP) multi-point transmission. The objective is to maximize the weighted sum rate within joint transmission clusters. As the considered weighted sum rate maximization is a non-convex problem, successive convex approximation techniques, based on weighted mean-squared error minimization, are applied to devise algorithms with tractable computational complexity. Decentralized algorithms are proposed to enable JP even with limited backhaul connectivity. These algorithms rely provide a variety of alternatives for signaling overhead, computational complexity and convergence behavior. Time division duplexing is exploited to design transceiver training techniques for two scenarios: stream specific estimation and direct estimation. In the stream specific estimation, the base station and user equipment estimate all of the stream specific precoded pilots individually and construct the transmit/receive covariance matrices based on these pilot estimates. With the direct estimation, only the intended transmission is separately estimated and the covariance matrices constructed directly from the aggregate system-wide pilots. The impact of feedback/backhaul signaling quantization is considered, in order to further reduce the signaling overhead. Also, user admission is being considered for time-correlated channels. The enhanced transceiver convergence rate enables periodic beamformer reinitialization, which greatly improves the achieved system performance in dense networks.
A Novel Transmission Scheme for the $K$-user Broadcast Channel with Delayed CSIT
Venue: arXiv cs.IT 2017
Year: 2017

The state-dependent $K$-user memoryless Broadcast Channel~(BC) with state feedback is investigated. We propose a novel transmission scheme and derive its corresponding achievable rate region, which, compared to some general schemes that deal with feedback, has the advantage of being relatively simple and thus is easy to evaluate. In particular, it is shown that the capacity region of the symmetric erasure BC with an arbitrary input alphabet size is achievable with the proposed scheme. For the fading Gaussian BC, we derive a symmetric achievable rate as a function of the signal-to-noise ratio~(SNR) and a small set of parameters. Besides achieving the optimal degrees of freedom at high SNR, the proposed scheme is shown, through numerical results, to outperform existing schemes from the literature in the finite SNR regime.
Exploiting the Pruning Power of Strong Local Consistencies Through Parallelization
Venue: arXiv cs.AI 2017
Year: 2017

Local consistencies stronger than arc consistency have received a lot of attention since the early days of CSP research. %because of the strong pruning they can achieve. However, they have not been widely adopted by CSP solvers. This is because applying such consistencies can sometimes result in considerably smaller search tree sizes and therefore in important speed-ups, but in other cases the search space reduction may be small, causing severe run time penalties. Taking advantage of recent advances in parallelization, we propose a novel approach for the application of strong local consistencies (SLCs) that can improve their performance by largely preserving the speed-ups they offer in cases where they are successful, and eliminating the run time penalties in cases where they are unsuccessful. This approach is presented in the form of two search algorithms. Both algorithms consist of a master search process, which is a typical CSP solver, and a number of slave processes, with each one implementing a SLC method. The first algorithm runs the different SLCs synchronously at each node of the search tree explored in the master process, while the second one can run them asynchronously at different nodes of the search tree. Experimental results demonstrate the benefits of the proposed method.
Understanding MIDI: A Painless Tutorial on Midi Format
Venue: arXiv cs.SD 2017
Year: 2017

A short overview demystifying the midi audio format is presented. The goal is to explain the file structure and how the instructions are used to produce a music signal, both in the case of monophonic signals as for polyphonic signals.
Constrained Bayesian Networks: Theory, Optimization, and Applications
Venue: arXiv cs.AI 2017
Year: 2017

We develop the theory and practice of an approach to modelling and probabilistic inference in causal networks that is suitable when application-specific or analysis-specific constraints should inform such inference or when little or no data for the learning of causal network structure or probability values at nodes are available. Constrained Bayesian Networks generalize a Bayesian Network such that probabilities can be symbolic, arithmetic expressions and where the meaning of the network is constrained by finitely many formulas from the theory of the reals. A formal semantics for constrained Bayesian Networks over first-order logic of the reals is given, which enables non-linear and non-convex optimisation algorithms that rely on decision procedures for this logic, and supports the composition of several constrained Bayesian Networks. A non-trivial case study in arms control, where few or no data are available to assess the effectiveness of an arms inspection process, evaluates our approach. An open-access prototype implementation of these foundations and their algorithms uses the SMT solver Z3 as decision procedure, leverages an open-source package for Bayesian inference to symbolic computation, and is evaluated experimentally.
A Non-Rigid Map Fusion-Based RGB-Depth SLAM Method for Endoscopic Capsule Robots
Venue: arXiv cs.CV 2017
Year: 2017

In the gastrointestinal (GI) tract endoscopy field, ingestible wireless capsule endoscopy is considered as a minimally invasive novel diagnostic technology to inspect the entire GI tract and to diagnose various diseases and pathologies. Since the development of this technology, medical device companies and many groups have made significant progress to turn such passive capsule endoscopes into robotic active capsule endoscopes to achieve almost all functions of current active flexible endoscopes. However, the use of robotic capsule endoscopy still has some challenges. One such challenge is the precise localization of such active devices in 3D world, which is essential for a precise three-dimensional (3D) mapping of the inner organ. A reliable 3D map of the explored inner organ could assist the doctors to make more intuitive and correct diagnosis. In this paper, we propose to our knowledge for the first time in literature a visual simultaneous localization and mapping (SLAM) method specifically developed for endoscopic capsule robots. The proposed RGB-Depth SLAM method is capable of capturing comprehensive dense globally consistent surfel-based maps of the inner organs explored by an endoscopic capsule robot in real time. This is achieved by using dense frame-to-model camera tracking and windowed surfelbased fusion coupled with frequent model refinement through non-rigid surface deformations.
Sparse Coding by Spiking Neural Networks: Convergence Theory and Computational Results
Venue: arXiv cs.LG 2017
Year: 2017

In a spiking neural network (SNN), individual neurons operate autonomously and only communicate with other neurons sparingly and asynchronously via spike signals. These characteristics render a massively parallel hardware implementation of SNN a potentially powerful computer, albeit a non von Neumann one. But can one guarantee that a SNN computer solves some important problems reliably? In this paper, we formulate a mathematical model of one SNN that can be configured for a sparse coding problem for feature extraction. With a moderate but well-defined assumption, we prove that the SNN indeed solves sparse coding. To the best of our knowledge, this is the first rigorous result of this kind.
Learning Hard Alignments with Variational Inference
Venue: arXiv cs.AI 2017
Year: 2017

There has recently been significant interest in hard attention models for tasks such as object recognition, visual captioning and speech recognition. Hard attention can offer benefits over soft attention such as decreased computational cost, but training hard attention models can be difficult because of the discrete latent variables they introduce. Previous work used REINFORCE and Q-learning to approach these issues, but those methods can provide high-variance gradient estimates and be slow to train. In this paper, we tackle the problem of learning hard attention for a sequential task using variational inference methods, specifically the recently introduced VIMCO and NVIL. Furthermore, we propose a novel baseline that adapts VIMCO to this setting. We demonstrate our method on a phoneme recognition task in clean and noisy environments and show that our method outperforms REINFORCE, with the difference being greater for a more complicated task.
Intel RealSense Stereoscopic Depth Cameras
Venue: arXiv cs.CV 2017
Year: 2017

We present a comprehensive overview of the stereoscopic Intel RealSense RGBD imaging systems. We discuss these systems' mode-of-operation, functional behavior and include models of their expected performance, shortcomings, and limitations. We provide information about the systems' optical characteristics, their correlation algorithms, and how these properties can affect different applications, including 3D reconstruction and gesture recognition. Our discussion covers the Intel RealSense R200 and the Intel RealSense D400 (formally RS400).
Opportunistic Communication in Extreme Wireless Sensor Networks
Venue: arXiv cs.NI 2017
Year: 2017

Sensor networks can nowadays deliver 99.9% of their data with duty cycles below 1%. This remarkable performance is, however, dependent on some important underlying assumptions: low traffic rates, medium size densities and static nodes. In this thesis, we investigate the performance of these same resource-constrained devices, but under scenarios that present extreme conditions: high traffic rates, high densities and mobility: the so-called Extreme Wireless Sensor Networks (EWSNs).
Tight Analysis for the 3-Majority Consensus Dynamics
Venue: arXiv cs.DC 2017
Year: 2017

We present a tight analysis for the well-studied randomized 3-majority dynamics of stabilizing consensus, hence answering the main open question of Becchetti et al. [SODA'16]. Consider a distributed system of n nodes, each initially holding an opinion in {1, 2, ..., k}. The system should converge to a setting where all (non-corrupted) nodes hold the same opinion. This consensus opinion should be \emph{valid}, meaning that it should be among the initially supported opinions, and the (fast) convergence should happen even in the presence of a malicious adversary who can corrupt a bounded number of nodes per round and in particular modify their opinions. A well-studied distributed algorithm for this problem is the 3-majority dynamics, which works as follows: per round, each node gathers three opinions --- say by taking its own and two of other nodes sampled at random --- and then it sets its opinion equal to the majority of this set; ties are broken arbitrarily, e.g., towards the node's own opinion. Becchetti et al. [SODA'16] showed that the 3-majority dynamics converges to consensus in O((k^2\sqrt{\log n} + k\log n)(k+\log n)) rounds, even in the presence of a limited adversary. We prove that, even with a stronger adversary, the convergence happens within O(k\log n) rounds. This bound is known to be optimal.
Learning Convex Regularizers for Optimal Bayesian Denoising
Venue: arXiv cs.LG 2017
Year: 2017

We propose a data-driven algorithm for the maximum a posteriori (MAP) estimation of stochastic processes from noisy observations. The primary statistical properties of the sought signal is specified by the penalty function (i.e., negative logarithm of the prior probability density function). Our alternating direction method of multipliers (ADMM)-based approach translates the estimation task into successive applications of the proximal mapping of the penalty function. Capitalizing on this direct link, we define the proximal operator as a parametric spline curve and optimize the spline coefficients by minimizing the average reconstruction error for a given training set. The key aspects of our learning method are that the associated penalty function is constrained to be convex and the convergence of the ADMM iterations is proven. As a result of these theoretical guarantees, adaptation of the proposed framework to different levels of measurement noise is extremely simple and does not require any retraining. We apply our method to estimation of both sparse and non-sparse models of Lévy processes for which the minimum mean square error (MMSE) estimators are available. We carry out a single training session and perform comparisons at various signal-to-noise ratio (SNR) values. Simulations illustrate that the performance of our algorithm is practically identical to the one of the MMSE estimator irrespective of the noise power.
GraphH: High Performance Big Graph Analytics in Small Clusters
Venue: arXiv cs.DC 2017
Year: 2017

It is common for real-world applications to analyze big graphs using distributed graph processing systems. Popular in-memory systems require an enormous amount of resources to handle big graphs. While several out-of-core approaches have been proposed for processing big graphs on disk, the high disk I/O overhead could significantly reduce performance. In this paper, we propose GraphH to enable high-performance big graph analytics in small clusters. Specifically, we design a two-stage graph partition scheme to evenly divide the input graph into partitions, and propose a GAB (Gather-Apply-Broadcast) computation model to make each worker process a partition in memory at a time. We use an edge cache mechanism to reduce the disk I/O overhead, and design a hybrid strategy to improve the communication performance. GraphH can efficiently process big graphs in small clusters or even a single commodity server. Extensive evaluations have shown that GraphH could be up to 7.8x faster compared to popular in-memory systems, such as Pregel+ and PowerGraph when processing generic graphs, and more than 100x faster than recently proposed out-of-core systems, such as GraphD and Chaos when processing big graphs.
The Impact of Alternation
Venue: arXiv cs.FL 2017
Year: 2017

Alternating automata have been widely used to model and verify systems that handle data from finite domains, such as communication protocols or hardware. The main advantage of the alternating model of computation is that complementation is possible in linear time, thus allowing to concisely encode trace inclusion problems that occur often in verification. In this paper we consider alternating automata over infinite alphabets, whose transition rules are formulae in a combined theory of booleans and some infinite data domain, that relate past and current values of the data variables. The data theory is not fixed, but rather it is a parameter of the class. We show that union, intersection and complementation are possible in linear time in this model and, though the emptiness problem is undecidable, we provide two efficient semi-algorithms, inspired by two state-of-the-art abstraction refinement model checking methods: lazy predicate abstraction \cite{HJMS02} and the \impact~ semi-algorithm \cite{mcmillan06}. We have implemented both methods and report the results of an experimental comparison.
Learning Edge Representations via Low-Rank Asymmetric Projections
Venue: arXiv cs.LG 2017
Year: 2017

We propose a new method for embedding graphs while preserving directed edge information. Learning such continuous-space vector representations (or embeddings) of nodes in a graph is an important first step for using network information (from social networks, user-item graphs, knowledge bases, etc.) in many machine learning tasks. Unlike previous work, we (1) explicitly model an edge as a function of node embeddings, and we (2) propose a novel objective, the "graph likelihood", which contrasts information from sampled random walks with non-existent edges. Individually, both of these contributions improve the learned representations, especially when there are memory constraints on the total size of the embeddings. When combined, our contributions enable us to significantly improve the state-of-the-art by learning more concise representations that better preserve the graph structure. We evaluate our method on a variety of link-prediction task including social networks, collaboration networks, and protein interactions, showing that our proposed method learn representations with error reductions of up to 76% and 55%, on directed and undirected graphs. In addition, we show that the representations learned by our method are quite space efficient, producing embeddings which have higher structure-preserving accuracy but are 10 times smaller.
Research on Bi-mode Biometrics Based on Deep Learning
Venue: arXiv cs.CV 2017
Year: 2017

In view of the fact that biological characteristics have excellent independent distinguishing characteristics,biometric identification technology involves almost all the relevant areas of human distinction. Fingerprints, iris, face, voice-print and other biological features have been widely used in the public security departments to detect detection, mobile equipment unlock, target tracking and other fields. With the use of electronic devices more and more widely and the frequency is getting higher and higher. Only the Biometrics identification technology with excellent recognition rate can guarantee the long-term development of these fields.
Text-based Adventures of the Golovin AI Agent
Venue: arXiv cs.AI 2017
Year: 2017

The domain of text-based adventure games has been recently established as a new challenge of creating the agent that is both able to understand natural language, and acts intelligently in text-described environments. In this paper, we present our approach to tackle the problem. Our agent, named Golovin, takes advantage of the limited game domain. We use genre-related corpora (including fantasy books and decompiled games) to create language models suitable to this domain. Moreover, we embed mechanisms that allow us to specify, and separately handle, important tasks as fighting opponents, managing inventory, and navigating on the game map. We validated usefulness of these mechanisms, measuring agent's performance on the set of 50 interactive fiction games. Finally, we show that our agent plays on a level comparable to the winner of the last year Text-Based Adventure AI Competition.