OpenRaiser/Intern-Atlas huggingface dataset:
A non-extensive entropy feature and its application to texture classification
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a new probabilistic non-extensive entropy feature for texture characterization, based on a Gaussian information measure. The highlights of the new entropy are that it is bounded by finite limits and that it is non additive in nature. The non additive property of the proposed entropy makes it useful for the representation of information content in the non-extensive systems containing some degree of regularity or correlation. The effectiveness of the proposed entropy in representing the correlated random variables is demonstrated by applying it for the texture classification problem since textures found in nature are random and at the same time contain some degree of correlation or regularity at some scale. The gray level co-occurrence probabilities (GLCP) are used for computing the entropy function. The experimental results indicate high degree of the classification accuracy. The performance of the new entropy function is found superior to other forms of entropy such as Shannon, Renyi, Tsallis and Pal and Pal entropies on comparison. Using the feature based polar interaction maps (FBIM) the proposed entropy is shown to be the best measure among the entropies compared for representing the correlated textures.
Anticipatory Radio Resource Management for Mobile Video Streaming with Linear Programming
Venue: arXiv cs.NI 2016
Year: 2016

In anticipatory networking, channel prediction is used to improve communication performance. This paper describes a new approach for allocating resources to video streaming traffic while accounting for quality of service. The proposed method is based on integrating a model of the user's local play-out buffer into the radio access network. The linearity of this model allows to formulate a Linear Programming problem that optimizes the trade-off between the allocated resources and the stalling time of the media stream. Our simulation results demonstrate the full power of anticipatory optimization in a simple, yet representative, scenario. Compared to instantaneous adaptation, our anticipatory solution shows impressive gains in spectral efficiency and stalling duration at feasible computation time while being robust against prediction errors.
An Introduction to Mechanized Reasoning
Venue: arXiv cs.LO 2016
Year: 2016

Mechanized reasoning uses computers to verify proofs and to help discover new theorems. Computer scientists have applied mechanized reasoning to economic problems but -- to date -- this work has not yet been properly presented in economics journals. We introduce mechanized reasoning to economists in three ways. First, we introduce mechanized reasoning in general, describing both the techniques and their successful applications. Second, we explain how mechanized reasoning has been applied to economic problems, concentrating on the two domains that have attracted the most attention: social choice theory and auction theory. Finally, we present a detailed example of mechanized reasoning in practice by means of a proof of Vickrey's familiar theorem on second-price auctions.
On the inconsistency of $\ell_1$-penalised sparse precision matrix estimation
Venue: arXiv cs.LG 2016
Year: 2016

Various $\ell_1$-penalised estimation methods such as graphical lasso and CLIME are widely used for sparse precision matrix estimation. Many of these methods have been shown to be consistent under various quantitative assumptions about the underlying true covariance matrix. Intuitively, these conditions are related to situations where the penalty term will dominate the optimisation. In this paper, we explore the consistency of $\ell_1$-based methods for a class of sparse latent variable -like models, which are strongly motivated by several types of applications. We show that all $\ell_1$-based methods fail dramatically for models with nearly linear dependencies between the variables. We also study the consistency on models derived from real gene expression data and note that the assumptions needed for consistency never hold even for modest sized gene networks and $\ell_1$-based methods also become unreliable in practice for larger networks.
Multidimensional factorization through helical mapping
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a new perspective on the problem of multidimensional spectral factorization, through helical mapping: $d$-dimensional ($d$D) data arrays are vectorized, processed by $1$D cepstral analysis and then remapped onto the original space. Partial differential equations (PDEs) are the basic framework to describe the evolution of physical phenomena. We observe that the minimum phase helical solution asymptotically converges to the $d$D semi-causal solution, and allows to decouple the two solutions arising from PDEs describing physical systems. We prove this equivalence in the theoretical framework of cepstral analysis, and we also illustrate the validity of helical factorization through a $2$D wave propagation example and a $3$D application to helioseismology.
Prediction of Infinite Words with Automata
Venue: arXiv cs.FL 2016
Year: 2016

In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters the emitter if there is a point after which all of the predictor's guesses are correct. In this paper we consider the case in which the predictor is an automaton and the emitted values are drawn from a finite set; i.e., the emitted sequence is an infinite word. We examine the predictive capabilities of finite automata, pushdown automata, stack automata (a generalization of pushdown automata), and multihead finite automata. We relate our predicting automata to purely periodic words, ultimately periodic words, and multilinear words, describing novel prediction algorithms for mastering these sequences.
Observing Trends in Automated Multilingual Media Analysis
Venue: arXiv cs.CL 2016
Year: 2016

Any large organisation, be it public or private, monitors the media for information to keep abreast of developments in their field of interest, and usually also to become aware of positive or negative opinions expressed towards them. At least for the written media, computer programs have become very efficient at helping the human analysts significantly in their monitoring task by gathering media reports, analysing them, detecting trends and - in some cases - even to issue early warnings or to make predictions of likely future developments. We present here trend recognition-related functionality of the Europe Media Monitor (EMM) system, which was developed by the European Commission's Joint Research Centre (JRC) for public administrations in the European Union (EU) and beyond. EMM performs large-scale media analysis in up to seventy languages and recognises various types of trends, some of them combining information from news articles written in different languages and from social media posts. EMM also lets users explore the huge amount of multilingual media data through interactive maps and graphs, allowing them to examine the data from various view points and according to multiple criteria. A lot of EMM's functionality is accessibly freely over the internet or via apps for hand-held devices.
DROW: Real-Time Deep Learning based Wheelchair Detection in 2D Range Data
Venue: arXiv cs.RO 2016
Year: 2016

We introduce the DROW detector, a deep learning based detector for 2D range data. Laser scanners are lighting invariant, provide accurate range data, and typically cover a large field of view, making them interesting sensors for robotics applications. So far, research on detection in laser range data has been dominated by hand-crafted features and boosted classifiers, potentially losing performance due to suboptimal design choices. We propose a Convolutional Neural Network (CNN) based detector for this task. We show how to effectively apply CNNs for detection in 2D range data, and propose a depth preprocessing step and voting scheme that significantly improve CNN performance. We demonstrate our approach on wheelchairs and walkers, obtaining state of the art detection results. Apart from the training data, none of our design choices limits the detector to these two classes, though. We provide a ROS node for our detector and release our dataset containing 464k laser scans, out of which 24k were annotated.
An MILP Approach for Real-time Optimal Controller Synthesis with Metric Temporal Logic Specifications
Venue: arXiv cs.SY 2016
Year: 2016

The fundamental idea of this work is to synthesize reactive controllers such that closed-loop execution trajectories of the system satisfy desired specifications that ensure correct system behaviors, while optimizing a desired performance criteria. In our approach, the correctness of a system's behavior can be defined according to the system's relation to the environment, for example, the output trajectories of the system terminate in a goal set without entering an unsafe set. Using Metric Temporal Logic (MTL) specifications we can further capture complex system behaviors and timing requirements, such as the output trajectories must pass through a number of way-points within a certain time frame before terminating in the goal set. Given a Mixed Logical Dynamical (MLD) system and system specifications in terms of MTL formula or simpler reach-avoid specifications, our goal is to find a closed-loop trajectory that satisfies the specifications, in non-deterministic environments. Using an MILP framework we search over the space of input signals to obtain such valid trajectories of the system, by adding constraints to satisfy the MTL formula only when necessary, to avoid the exponential complexity of solving MILP problems. We also present experimental results for planning a path for a mobile robot through a dynamically changing environment with a desired task specification.
Rank Aggregation for Course Sequence Discovery
Venue: arXiv cs.LG 2016
Year: 2016

In this work, we adapt the rank aggregation framework for the discovery of optimal course sequences at the university level. Each student provides a partial ranking of the courses taken throughout his or her undergraduate career. We compute pairwise rank comparisons between courses based on the order students typically take them, aggregate the results over the entire student population, and then obtain a proxy for the rank offset between pairs of courses. We extract a global ranking of the courses via several state-of-the art algorithms for ranking with pairwise noisy information, including SerialRank, Rank Centrality, and the recent SyncRank based on the group synchronization problem. We test this application of rank aggregation on 15 years of student data from the Department of Mathematics at the University of California, Los Angeles (UCLA). Furthermore, we experiment with the above approach on different subsets of the student population conditioned on final GPA, and highlight several differences in the obtained rankings that uncover hidden pre-requisites in the Mathematics curriculum.
Faster learning of deep stacked autoencoders on multi-core systems using synchronized layer-wise pre-training
Venue: arXiv cs.LG 2016
Year: 2016

Deep neural networks are capable of modelling highly non-linear functions by capturing different levels of abstraction of data hierarchically. While training deep networks, first the system is initialized near a good optimum by greedy layer-wise unsupervised pre-training. However, with burgeoning data and increasing dimensions of the architecture, the time complexity of this approach becomes enormous. Also, greedy pre-training of the layers often turns detrimental by over-training a layer causing it to lose harmony with the rest of the network. In this paper a synchronized parallel algorithm for pre-training deep networks on multi-core machines has been proposed. Different layers are trained by parallel threads running on different cores with regular synchronization. Thus the pre-training process becomes faster and chances of over-training are reduced. This is experimentally validated using a stacked autoencoder for dimensionality reduction of MNIST handwritten digit database. The proposed algorithm achieved 26\% speed-up compared to greedy layer-wise pre-training for achieving the same reconstruction accuracy substantiating its potential as an alternative.
Reasoning about Recursive Probabilistic Programs
Venue: arXiv cs.LO 2016
Year: 2016

This paper presents a wp-style calculus for obtaining expectations on the outcomes of (mutually) recursive probabilistic programs. We provide several proof rules to derive one-- and two--sided bounds for such expectations, and show the soundness of our wp-calculus with respect to a probabilistic pushdown automaton semantics. We also give a wp-style calculus for obtaining bounds on the expected runtime of recursive programs that can be used to determine the (possibly infinite) time until termination of such programs.
Robot Dream
Venue: arXiv cs.RO 2016
Year: 2016

In this position paper we present a novel approach to neurobiologically plausible implementation of emotional reactions and behaviors for real-time autonomous robotic systems. The working metaphor we use is the "day" and "night" phases of mammalian life. During the "day" phase a robotic system stores the inbound information and is controlled by a light-weight rule-based system in real time. In contrast to that, during the "night" phase the stored information is been transferred to the supercomputing system to update the realistic neural network: emotional and behavioral strategies.
Reducing the generalised Sudoku problem to the Hamiltonian cycle problem
Venue: arXiv cs.DS 2016
Year: 2016

The generalised Sudoku problem with $N$ symbols is known to be NP-complete, and hence is equivalent to any other NP-complete problem, even for the standard restricted version where $N$ is a perfect square. In particular, generalised Sudoku is equivalent to the, classical, Hamiltonian cycle problem. A constructive algorithm is given that reduces generalised Sudoku to the Hamiltonian cycle problem, where the resultant instance of Hamiltonian cycle problem is sparse, and has $O(N^3)$ vertices. The Hamiltonian cycle problem instance so constructed is a directed graph, and so a (known) conversion to undirected Hamiltonian cycle problem is also provided so that it can be submitted to the best heuristics. A simple algorithm for obtaining the valid Sudoku solution from the Hamiltonian cycle is provided. Techniques to reduce the size of the resultant graph are also discussed.
Online Matching: Haste makes Waste!
Venue: arXiv cs.DS 2016
Year: 2016

This paper studies a new online problem, referred to as \emph{min-cost perfect matching with delays (MPMD)}, defined over a finite metric space (i.e., a complete graph with positive edge weights obeying the triangle inequality) $\mathcal{M}$ that is known to the algorithm in advance. Requests arrive in a continuous time online fashion at the points of $\mathcal{M}$ and should be served by matching them to each other. The algorithm is allowed to delay its request matching commitments, but this does not come for free: the total cost of the algorithm is the sum of metric distances between matched requests \emph{plus} the sum of times each request waited since it arrived until it was matched. A randomized online MPMD algorithm is presented whose competitive ratio is $O (\log^{2} n + \log Δ)$, where $n$ is the number of points in $\mathcal{M}$ and $Δ$ is its aspect ratio. The analysis is based on a machinery developed in the context of a new stochastic process that can be viewed as two interleaved Poisson processes; surprisingly, this new process captures precisely the behavior of our algorithm. A related problem in which the algorithm is allowed to clear any unmatched request at a fixed penalty is also addressed. It is suggested that the MPMD problem is merely the tip of the iceberg for a general framework of online problems with delayed service that captures many more natural problems.
Informed Truthfulness in Multi-Task Peer Prediction
Venue: arXiv cs.GT 2016
Year: 2016

The problem of peer prediction is to elicit information from agents in settings without any objective ground truth against which to score reports. Peer prediction mechanisms seek to exploit correlations between signals to align incentives with truthful reports. A long-standing concern has been the possibility of uninformative equilibria. For binary signals, a multi-task mechanism [Dasgupta-Ghosh '13] achieves strong truthfulness, so that the truthful equilibrium strictly maximizes payoff. We characterize conditions on the signal distribution for which this mechanism remains strongly-truthful with non-binary signals, also providing a greatly simplified proof. We introduce the Correlated Agreement (CA) mechanism, which handles multiple signals and provides informed truthfulness: no strategy profile provides more payoff in equilibrium than truthful reporting, and the truthful equilibrium is strictly better than any uninformed strategy (where an agent avoids the effort of obtaining a signal). The CA mechanism is maximally strongly truthful, in that no mechanism in a broad class of mechanisms is strongly truthful on a larger family of signal distributions. We also give a detail-free version of the mechanism that removes any knowledge requirements on the part of the designer, using reports on many tasks to learn statistics while retaining epsilon-informed truthfulness.
Inferring Fine-grained Details on User Activities and Home Location from Social Media: Detecting Drinking-While-Tweeting Patterns in Communities
Venue: arXiv cs.AI 2016
Year: 2016

Nearly all previous work on geo-locating latent states and activities from social media confounds general discussions about activities, self-reports of users participating in those activities at times in the past or future, and self-reports made at the immediate time and place the activity occurs. Activities, such as alcohol consumption, may occur at different places and types of places, and it is important not only to detect the local regions where these activities occur, but also to analyze the degree of participation in them by local residents. In this paper, we develop new machine learning based methods for fine-grained localization of activities and home locations from Twitter data. We apply these methods to discover and compare alcohol consumption patterns in a large urban area, New York City, and a more suburban and rural area, Monroe County. We find positive correlations between the rate of alcohol consumption reported among a community's Twitter users and the density of alcohol outlets, demonstrating that the degree of correlation varies significantly between urban and suburban areas. While our experiments are focused on alcohol use, our methods for locating homes and distinguishing temporally-specific self-reports are applicable to a broad range of behaviors and latent states.
Microphone array post-filter for separation of simultaneous non-stationary sources
Venue: arXiv cs.SD 2016
Year: 2016

Microphone array post-filters have demonstrated their ability to greatly reduce noise at the output of a beamformer. However, current techniques only consider a single source of interest, most of the time assuming stationary background noise. We propose a microphone array post-filter that enhances the signals produced by the separation of simultaneous sources using common source separation algorithms. Our method is based on a loudness-domain optimal spectral estimator and on the assumption that the noise can be described as the sum of a stationary component and of a transient component that is due to leakage between the channels of the initial source separation algorithm. The system is evaluated in the context of mobile robotics and is shown to produce better results than current post-filtering techniques, greatly reducing interference while causing little distortion to the signal of interest, even at very low SNR.
UTSig: A Persian Offline Signature Dataset
Venue: arXiv cs.CV 2016
Year: 2016

The pivotal role of datasets in signature verification systems motivates researchers to collect signature samples. Distinct characteristics of Persian signature demands for richer and culture-dependent offline signature datasets. This paper introduces a new and public Persian offline signature dataset, UTSig, that consists of 8280 images from 115 classes. Each class has 27 genuine signatures, 3 opposite-hand signatures, and 42 skilled forgeries made by 6 forgers. Compared with the other public datasets, UTSig has more samples, more classes, and more forgers. We considered various variables including signing period, writing instrument, signature box size, and number of observable samples for forgers in the data collection procedure. By careful examination of main characteristics of offline signature datasets, we observe that Persian signatures have fewer numbers of branch points and end points. We propose and evaluate four different training and test setups for UTSig. Results of our experiments show that training genuine samples along with opposite-hand samples and random forgeries can improve the performance in terms of equal error rate and minimum cost of log likelihood ratio.
A Markovian-based Approach for Daily Living Activities Recognition
Venue: arXiv cs.HC 2016
Year: 2016

Recognizing the activities of daily living plays an important role in healthcare. It is necessary to use an adapted model to simulate the human behavior in a domestic space to monitor the patient harmonically and to intervene in the necessary time. In this paper, we tackle this problem using the hierarchical hidden Markov model for representing and recognizing complex indoor activities. We propose a new grammar, called "Home By Room Activities Language", to facilitate the complexity of human scenarios and consider the abnormal activities.
Comparing Properties of Massively Multiplayer Online Worlds and the Internet of Things
Venue: arXiv cs.NI 2016
Year: 2016

With the rise of the Internet of Things (IoT), this means recognizing the need for architectures to handle billions of devices and their interactions. A virtual world engine at the massively multiplayer scale is a massively multiplayer online world (MMOW); one thing virtual world engines realized when going into the scale of MMOs, is the cost of maintaining a potentially quadratic number of interactions between a massive number of objects, laid out in a spatial dimension. Research into IoT was fueled by research in wireless sensor networks, but rather than start from a device perspective, this article looks at how architectures deal with interacting entities at large scale. The domain of MMOWs is examined for properties that are affected by scale. Thereafter the domain of IoT is evaluated to see if each of those properties are found and how each is handled. By comparing the current state of the art of MMOWs and IoT, with respect to scalability, the problem of scaling IoT is explicated, as well as the problem of incorporating an MMOW with IoT into a pervasive platform. Three case studies of a MMOW interfacing with IoT are presented in closing.
The Status Gradient of Trends in Social Media
Venue: arXiv cs.SI 2016
Year: 2016

An active line of research has studied the detection and representation of trends in social media content. There is still relatively little understanding, however, of methods to characterize the early adopters of these trends: who picks up on these trends at different points in time, and what is their role in the system? We develop a framework for analyzing the population of users who participate in trending topics over the course of these topics' lifecycles. Central to our analysis is the notion of a "status gradient", describing how users of different activity levels adopt a trend at different points in time. Across multiple datasets, we find that this methodology reveals key differences in the nature of the early adopters in different domains.