OpenRaiser/Intern-Atlas huggingface dataset:
Robotic Swarm Control from Spatio-Temporal Specifications
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we study the problem of controlling a two-dimensional robotic swarm with the purpose of achieving high level and complex spatio-temporal patterns. We use a rich spatio-temporal logic that is capable of describing a wide range of time varying and complex spatial configurations, and develop a method to encode such formal specifications as a set of mixed integer linear constraints, which are incorporated into a mixed integer linear programming problem. We plan trajectories for each individual robot such that the whole swarm satisfies the spatio-temporal requirements, while optimizing total robot movement and/or a metric that shows how strongly the swarm trajectory resembles given spatio-temporal behaviors. An illustrative case study is included.
Near-Optimal (Euclidean) Metric Compression
Venue: arXiv cs.CG 2016
Year: 2016

The metric sketching problem is defined as follows. Given a metric on $n$ points, and $ε>0$, we wish to produce a small size data structure (sketch) that, given any pair of point indices, recovers the distance between the points up to a $1+ε$ distortion. In this paper we consider metrics induced by $\ell_2$ and $\ell_1$ norms whose spread (the ratio of the diameter to the closest pair distance) is bounded by $Φ>0$. A well-known dimensionality reduction theorem due to Johnson and Lindenstrauss yields a sketch of size $O(ε^{-2} \log (Φn) n\log n)$, i.e., $O(ε^{-2} \log (Φn) \log n)$ bits per point. We show that this bound is not optimal, and can be substantially improved to $O(ε^{-2}\log(1/ε) \cdot \log n + \log\log Φ)$ bits per point. Furthermore, we show that our bound is tight up to a factor of $\log(1/ε)$. We also consider sketching of general metrics and provide a sketch of size $O(n\log(1/ε)+ \log\log Φ)$ bits per point, which we show is optimal.
A Consumer BCI for Automated Music Evaluation Within a Popular On-Demand Music Streaming Service - Taking Listener's Brainwaves to Extremes
Venue: arXiv cs.AI 2016
Year: 2016

We investigated the possibility of using a machine-learning scheme in conjunction with commercial wearable EEG-devices for translating listener's subjective experience of music into scores that can be used for the automated annotation of music in popular on-demand streaming services. Based on the established -neuroscientifically sound- concepts of brainwave frequency bands, activation asymmetry index and cross-frequency-coupling (CFC), we introduce a Brain Computer Interface (BCI) system that automatically assigns a rating score to the listened song. Our research operated in two distinct stages: i) a generic feature engineering stage, in which features from signal-analytics were ranked and selected based on their ability to associate music induced perturbations in brainwaves with listener's appraisal of music. ii) a personalization stage, during which the efficiency of ex- treme learning machines (ELMs) is exploited so as to translate the derived pat- terns into a listener's score. Encouraging experimental results, from a pragmatic use of the system, are presented.
Linear-time string indexing and analysis in small space
Venue: arXiv cs.DS 2016
Year: 2016

The field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array (CSA) by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing. We report the following advances in string indexing and analysis. We show that the BWT of a string $T\in \{1,\ldots,σ\}^n$ can be built in deterministic $O(n)$ time using just $O(n\logσ)$ bits of space, where $σ\leq n$. Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of $T$. Many fundamental string analysis problems can be mapped to such enumeration, and can thus be solved in deterministic $O(n)$ time and in $O(n\logσ)$ bits of space from the input string. We also show how to build many of the existing indexes based on the BWT, such as the CSA, the compressed suffix tree (CST), and the bidirectional BWT index, in randomized $O(n)$ time and in $O(n\logσ)$ bits of space. The previously fastest construction algorithms for BWT, CSA and CST, which used $O(n\logσ)$ bits of space, took $O(n\log{\logσ})$ time for the first two structures, and $O(n\log^εn)$ time for the third, where $ε$ is any positive constant. Contrary to the state of the art, our bidirectional BWT index supports every operation in constant time per element in its output.
AMOS: An Automated Model Order Selection Algorithm for Spectral Graph Clustering
Venue: arXiv cs.SI 2016
Year: 2016

One of the longstanding problems in spectral graph clustering (SGC) is the so-called model order selection problem: automated selection of the correct number of clusters. This is equivalent to the problem of finding the number of connected components or communities in an undirected graph. In this paper, we propose AMOS, an automated model order selection algorithm for SGC. Based on a recent analysis of clustering reliability for SGC under the random interconnection model, AMOS works by incrementally increasing the number of clusters, estimating the quality of identified clusters, and providing a series of clustering reliability tests. Consequently, AMOS outputs clusters of minimal model order with statistical clustering reliability guarantees. Comparing to three other automated graph clustering methods on real-world datasets, AMOS shows superior performance in terms of multiple external and internal clustering metrics.
Chatbots' Greetings to Human-Computer Communication
Venue: arXiv cs.HC 2016
Year: 2016

Both dialogue systems and chatbots aim at putting into action communication between humans and computers. However, instead of focusing on sophisticated techniques to perform natural language understanding, as the former usually do, chatbots seek to mimic conversation. Since Eliza, the first chatbot ever, developed in 1966, there were many interesting ideas explored by the chatbots' community. Actually, more than just ideas, some chatbots' developers also provide free resources, including tools and large-scale corpora. It is our opinion that this know-how and materials should not be neglected, as they might be put to use in the human-computer communication field (and some authors already do it). Thus, in this paper we present a historical overview of the chatbots' developments, we review what we consider to be the main contributions of this community, and we point to some possible ways of coupling these with current work in the human-computer communication research line.
One Sentence One Model for Neural Machine Translation
Venue: arXiv cs.CL 2016
Year: 2016

Neural machine translation (NMT) becomes a new state-of-the-art and achieves promising translation results using a simple encoder-decoder neural network. This neural network is trained once on the parallel corpus and the fixed network is used to translate all the test sentences. We argue that the general fixed network cannot best fit the specific test sentences. In this paper, we propose the dynamic NMT which learns a general network as usual, and then fine-tunes the network for each test sentence. The fine-tune work is done on a small set of the bilingual training data that is obtained through similarity search according to the test sentence. Extensive experiments demonstrate that this method can significantly improve the translation performance, especially when highly similar sentences are available.
Computing Vertex-Disjoint Paths using MAOs
Venue: arXiv cs.DM 2016
Year: 2016

Let G be a graph with minimum degree $δ$. It is well-known that maximal adjacency orderings (MAOs) compute a vertex set S such that every pair of S is connected by at least $δ$ internally vertex-disjoint paths in G. We present an algorithm that, given any pair of S, computes these $δ$ paths in linear time O(n+m). This improves the previously best solutions for these special vertex pairs, which were flow-based. Our algorithm simplifies a proof about pendant pairs of Mader and makes a purely existential proof of Nagamochi algorithmic.
The Optional Prisoner's Dilemma in a Spatial Environment: Coevolving Game Strategy and Link Weights
Venue: arXiv cs.NE 2016
Year: 2016

In this paper, the Optional Prisoner's Dilemma game in a spatial environment, with coevolutionary rules for both the strategy and network links between agents, is studied. Using a Monte Carlo simulation approach, a number of experiments are performed to identify favourable configurations of the environment for the emergence of cooperation in adverse scenarios. Results show that abstainers play a key role in the protection of cooperators against exploitation from defectors. Scenarios of cyclic competition and of full dominance of cooperation are also observed. This work provides insights towards gaining an in-depth understanding of the emergence of cooperative behaviour in real-world systems.
Revealing Structure in Large Graphs: Szemerédi's Regularity Lemma and its Use in Pattern Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Introduced in the mid-1970's as an intermediate step in proving a long-standing conjecture on arithmetic progressions, Szemerédi's regularity lemma has emerged over time as a fundamental tool in different branches of graph theory, combinatorics and theoretical computer science. Roughly, it states that every graph can be approximated by the union of a small number of random-like bipartite graphs called regular pairs. In other words, the result provides us a way to obtain a good description of a large graph using a small amount of data, and can be regarded as a manifestation of the all-pervading dichotomy between structure and randomness. In this paper we will provide an overview of the regularity lemma and its algorithmic aspects, and will discuss its relevance in the context of pattern recognition research.
Multimedia Communication Quality Assessment Testbeds
Venue: arXiv cs.MM 2016
Year: 2016

We make an intensive use of multimedia frameworks in our research on modeling the perceived quality estimation in streaming services and real-time communications. In our preliminary work, we have used the VLC VOD software to generate reference audiovisual files with various degree of coding and network degradations. We have successfully built machine learning based models on the subjective quality dataset we have generated using these files. However, imperfections in the dataset introduced by the multimedia framework we have used prevented us from achieving the full potential of these models. In order to develop better models, we have re-created our end-to-end multimedia pipeline using the GStreamer framework for audio and video streaming. A GStreamer based pipeline proved to be significantly more robust to network degradations than the VLC VOD framework and allowed us to stream a video flow at a loss rate up to 5\% packet very easily. GStreamer has also enabled us to collect the relevant RTCP statistics that proved to be more accurate than network-deduced information. This dataset is free to the public. The accuracy of the statistics eventually helped us to generate better performing perceived quality estimation models. In this paper, we present the implementation of these VLC and GStreamer-based multimedia communication quality assessment testbeds with the references to their publicly available code bases.
No-hole $λ$-$L(k, k-1, \ldots, 2, 1)$-labeling for Square Grid
Venue: arXiv cs.DM 2016
Year: 2016

Given a fixed $k$ $\in$ $\mathbb{Z}^+$ and $λ$ $\in$ $\mathbb{Z}^+$, the objective of a $λ$-$L(k, k-1, \ldots, 2, 1)$-labeling of a graph $G$ is to assign non-negative integers (known as labels) from the set $\{0, \ldots, λ-1\}$ to the vertices of $G$ such that the adjacent vertices receive values which differ by at least $k$, vertices connected by a path of length two receive values which differ by at least $k-1$, and so on. The vertices which are at least $k+1$ distance apart can receive the same label. The smallest $λ$ for which there exists a $λ$-$L(k, k-1, \ldots, 2, 1)$-labeling of $G$ is known as the $L(k, k-1, \ldots, 2, 1)$-labeling number of $G$ and is denoted by $λ_k(G)$. The ratio between the upper bound and the lower bound of a $λ$-$L(k, k-1, \ldots, 2, 1)$-labeling is known as the approximation ratio. In this paper a lower bound on the value of the labeling number for square grid is computed and a formula is proposed which yields a $λ$-$L(k, k-1, \ldots, 2, 1)$-labeling of square grid, with approximation ratio at most $\frac{9}{8}$. The labeling presented is a no-hole one, i.e., it uses each label from $0$ to $λ-1$ at least once.
Minimally Supervised Written-to-Spoken Text Normalization
Venue: arXiv cs.CL 2016
Year: 2016

In speech-applications such as text-to-speech (TTS) or automatic speech recognition (ASR), \emph{text normalization} refers to the task of converting from a \emph{written} representation into a representation of how the text is to be \emph{spoken}. In all real-world speech applications, the text normalization engine is developed---in large part---by hand. For example, a hand-built grammar may be used to enumerate the possible ways of saying a given token in a given language, and a statistical model used to select the most appropriate pronunciation in context. In this study we examine the tradeoffs associated with using more or less language-specific domain knowledge in a text normalization engine. In the most data-rich scenario, we have access to a carefully constructed hand-built normalization grammar that for any given token will produce a set of all possible verbalizations for that token. We also assume a corpus of aligned written-spoken utterances, from which we can train a ranking model that selects the appropriate verbalization for the given context. As a substitute for the carefully constructed grammar, we also consider a scenario with a language-universal normalization \emph{covering grammar}, where the developer merely needs to provide a set of lexical items particular to the language. As a substitute for the aligned corpus, we also consider a scenario where one only has the spoken side, and the corresponding written side is "hallucinated" by composing the spoken side with the inverted normalization grammar. We investigate the accuracy of a text normalization engine under each of these scenarios. We report the results of experiments on English and Russian.
Character-level and Multi-channel Convolutional Neural Networks for Large-scale Authorship Attribution
Venue: arXiv cs.CL 2016
Year: 2016

Convolutional neural networks (CNNs) have demonstrated superior capability for extracting information from raw signals in computer vision. Recently, character-level and multi-channel CNNs have exhibited excellent performance for sentence classification tasks. We apply CNNs to large-scale authorship attribution, which aims to determine an unknown text's author among many candidate authors, motivated by their ability to process character-level signals and to differentiate between a large number of classes, while making fast predictions in comparison to state-of-the-art approaches. We extensively evaluate CNN-based approaches that leverage word and character channels and compare them against state-of-the-art methods for a large range of author numbers, shedding new light on traditional approaches. We show that character-level CNNs outperform the state-of-the-art on four out of five datasets in different domains. Additionally, we present the first application of authorship attribution to reddit.
SoftTarget Regularization: An Effective Technique to Reduce Over-Fitting in Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

Deep neural networks are learning models with a very high capacity and therefore prone to over-fitting. Many regularization techniques such as Dropout, DropConnect, and weight decay all attempt to solve the problem of over-fitting by reducing the capacity of their respective models (Srivastava et al., 2014), (Wan et al., 2013), (Krogh & Hertz, 1992). In this paper we introduce a new form of regularization that guides the learning problem in a way that reduces over-fitting without sacrificing the capacity of the model. The mistakes that models make in early stages of training carry information about the learning problem. By adjusting the labels of the current epoch of training through a weighted average of the real labels, and an exponential average of the past soft-targets we achieved a regularization scheme as powerful as Dropout without necessarily reducing the capacity of the model, and simplified the complexity of the learning problem. SoftTarget regularization proved to be an effective tool in various neural network architectures.
Twitter-Network Topic Model: A Full Bayesian Treatment for Social Network and Text Modeling
Venue: arXiv cs.CL 2016
Year: 2016

Twitter data is extremely noisy -- each tweet is short, unstructured and with informal language, a challenge for current topic modeling. On the other hand, tweets are accompanied by extra information such as authorship, hashtags and the user-follower network. Exploiting this additional information, we propose the Twitter-Network (TN) topic model to jointly model the text and the social network in a full Bayesian nonparametric way. The TN topic model employs the hierarchical Poisson-Dirichlet processes (PDP) for text modeling and a Gaussian process random function model for social network modeling. We show that the TN topic model significantly outperforms several existing nonparametric models due to its flexibility. Moreover, the TN topic model enables additional informative inference such as authors' interests, hashtag analysis, as well as leading to further applications such as author recommendation, automatic topic labeling and hashtag suggestion. Note our general inference framework can readily be applied to other topic models with embedded PDP nodes.
On the usability of deep networks for object-based image analysis
Venue: arXiv cs.NE 2016
Year: 2016

As computer vision before, remote sensing has been radically changed by the introduction of Convolution Neural Networks. Land cover use, object detection and scene understanding in aerial images rely more and more on deep learning to achieve new state-of-the-art results. Recent architectures such as Fully Convolutional Networks (Long et al., 2015) can even produce pixel level annotations for semantic mapping. In this work, we show how to use such deep networks to detect, segment and classify different varieties of wheeled vehicles in aerial images from the ISPRS Potsdam dataset. This allows us to tackle object detection and classification on a complex dataset made up of visually similar classes, and to demonstrate the relevance of such a subclass modeling approach. Especially, we want to show that deep learning is also suitable for object-oriented analysis of Earth Observation data. First, we train a FCN variant on the ISPRS Potsdam dataset and show how the learnt semantic maps can be used to extract precise segmentation of vehicles, which allow us studying the repartition of vehicles in the city. Second, we train a CNN to perform vehicle classification on the VEDAI (Razakarivony and Jurie, 2016) dataset, and transfer its knowledge to classify candidate segmented vehicles on the Potsdam dataset.
Leading Impulse Response Identification via the Weighted Elastic Net Criterion
Venue: arXiv cs.SY 2016
Year: 2016

This paper deals with the problem of finding a low-complexity estimate of the impulse response of a linear time-invariant discrete-time dynamic system from noise-corrupted input-output data. To this purpose, we introduce an identification criterion formed by the average (over the input perturbations) of a standard prediction error cost, plus a weighted l1 regularization term which promotes sparse solutions. While it is well known that such criteria do provide solutions with many zeros, a critical issue in our identification context is where these zeros are located, since sensible low-order models should be zero in the tail of the impulse response. The flavor of the key results in this paper is that, under quite standard assumptions (such as i.i.d. input and noise sequences and system stability), the estimate of the impulse response resulting from the proposed criterion is indeed identically zero from a certain time index (named the leading order) onwards, with arbitrarily high probability, for a sufficiently large data cardinality. Numerical experiments are reported that support the theoretical results, and comparisons are made with some other state-of-the-art methodologies.
Abstractive Meeting Summarization UsingDependency Graph Fusion
Venue: arXiv cs.CL 2016
Year: 2016

Automatic summarization techniques on meeting conversations developed so far have been primarily extractive, resulting in poor summaries. To improve this, we propose an approach to generate abstractive summaries by fusing important content from several utterances. Any meeting is generally comprised of several discussion topic segments. For each topic segment within a meeting conversation, we aim to generate a one sentence summary from the most important utterances using an integer linear programming-based sentence fusion approach. Experimental results show that our method can generate more informative summaries than the baselines.
Pose-Selective Max Pooling for Measuring Similarity
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we deal with two challenges for measuring the similarity of the subject identities in practical video-based face recognition - the variation of the head pose in uncontrolled environments and the computational expense of processing videos. Since the frame-wise feature mean is unable to characterize the pose diversity among frames, we define and preserve the overall pose diversity and closeness in a video. Then, identity will be the only source of variation across videos since the pose varies even within a single video. Instead of simply using all the frames, we select those faces whose pose point is closest to the centroid of the K-means cluster containing that pose point. Then, we represent a video as a bag of frame-wise deep face features while the number of features has been reduced from hundreds to K. Since the video representation can well represent the identity, now we measure the subject similarity between two videos as the max correlation among all possible pairs in the two bags of features. On the official 5,000 video-pairs of the YouTube Face dataset for face verification, our algorithm achieves a comparable performance with VGG-face that averages over deep features of all frames. Other vision tasks can also benefit from the generic idea of employing geometric cues to improve the descriptiveness of deep features.