OpenRaiser/Intern-Atlas huggingface dataset:
Interactive Coding for Markovian Protocols
Venue: arXiv cs.IT 2017
Year: 2017

We address the problem of simulating an arbitrary Markovian interactive protocol over binary symmetric channels with crossover probability $\varepsilon$. We are interested in the achievable rates of reliable simulation, i.e., in characterizing the smallest possible blowup in communications such that a vanishing error probability (in the protocol length) can be attained. Whereas for general interactive protocols the output of each party may depend on all previous outputs of its counterpart, in a (first order) Markovian protocol this dependence is limited to the last observed output only. In the special case where there is no dependence on previous outputs (no interaction), the maximal achievable rate is given by the (one-way) Shannon capacity $1-h(\varepsilon)$. For Markovian protocols, we first show that a rate of $\frac{2}{3}(1-h(\varepsilon))$ can be trivially achieved. We then describe a more involved coding scheme and provide a closed-form lower bound for its rate at any noise level $\varepsilon$. Specifically, we show that this scheme outperforms the trivial one for any $\varepsilon<0.044$, and achieves a rate higher than $\frac{1-h(\varepsilon)}{1+h(\varepsilon)+h\left(<\varepsilon(2-\varepsilon)>\right)}=1-Θ(h(\varepsilon))$ as $\varepsilon\to 0$, which is order-wise the best possible. This should be juxtaposed with a result of Kol and Raz that shows the capacity for interactive protocols with alternating rounds is lower bounded by $1-O(\sqrt{h(\varepsilon)})$.
Emotion-Recognition Using Smart Watch Accelerometer Data: Preliminary Findings
Venue: arXiv cs.HC 2017
Year: 2017

This study investigates the use of accelerometer data from a smart watch to infer an individual's emotional state. We present our preliminary findings on a user study with 50 participants. Participants were primed either with audio-visual (movie clips) or audio (classical music) to elicit emotional responses. Participants then walked while wearing a smart watch on one wrist and a heart rate strap on their chest. Our hypothesis is that the accelerometer signal will exhibit different patterns for participants in response to different emotion priming. We divided the accelerometer data using sliding windows, extracted features from each window, and used the features to train supervised machine learning algorithms to infer an individual's emotion from their walking pattern. Our discussion includes a description of the methodology, data collected, and early results.
Lexical Disambiguation in Natural Language Questions (NLQs)
Venue: arXiv cs.CL 2017
Year: 2017

Question processing is a fundamental step in a question answering (QA) application, and its quality impacts the performance of QA application. The major challenging issue in processing question is how to extract semantic of natural language questions (NLQs). A human language is ambiguous. Ambiguity may occur at two levels; lexical and syntactic. In this paper, we propose a new approach for resolving lexical ambiguity problem by integrating context knowledge and concepts knowledge of a domain, into shallow natural language processing (SNLP) techniques. Concepts knowledge is modeled using ontology, while context knowledge is obtained from WordNet, and it is determined based on neighborhood words in a question. The approach will be applied to a university QA system.
SURGE: Continuous Detection of Bursty Regions Over a Stream of Spatial Objects
Venue: arXiv cs.DB 2017
Year: 2017

With the proliferation of mobile devices and location-based services, continuous generation of massive volume of streaming spatial objects (i.e., geo-tagged data) opens up new opportunities to address real-world problems by analyzing them. In this paper, we present a novel continuous bursty region detection problem that aims to continuously detect a bursty region of a given size in a specified geographical area from a stream of spatial objects. Specifically, a bursty region shows maximum spike in the number of spatial objects in a given time window. The problem is useful in addressing several real-world challenges such as surge pricing problem in online transportation and disease outbreak detection. To solve the problem, we propose an exact solution and two approximate solutions, and the approximation ratio is $\frac{1-α}{4}$ in terms of the burst score, where $α$ is a parameter to control the burst score. We further extend these solutions to support detection of top-$k$ bursty regions. Extensive experiments with real-world data are conducted to demonstrate the efficiency and effectiveness of our solutions.
Symbolic Computation of the Worst-Case Execution Time of a Program
Venue: arXiv cs.PL 2017
Year: 2017

Parametric Worst-case execution time (WCET) analysis of a sequential program produces a formula that represents the worst-case execution time of the program, where parameters of the formula are user-defined parameters of the program (as loop bounds, values of inputs or internal variables, etc). In this paper we propose a novel methodology to compute the parametric WCET of a program. Unlike other algorithms in the literature, our method is not based on Integer Linear Programming (ILP). Instead, we follow an approach based on the notion of symbolic computation of WCET formulae. After explaining our methodology and proving its correctness, we present a set of experiments to compare our method against the state of the art. We show that our approach dominates other parametric analyses, and produces results that are very close to those produced by non-parametric ILP-based approaches, while keeping very good computing time.
Low-Complexity Iterative Detection for Orthogonal Time Frequency Space Modulation
Venue: arXiv cs.IT 2017
Year: 2017

We elaborate on the recently proposed orthogonal time frequency space (OTFS) modulation technique, which provides significant advantages over orthogonal frequency division multiplexing (OFDM) in Doppler channels. We first derive the input--output relation describing OTFS modulation and demodulation (mod/demod) for delay--Doppler channels with arbitrary number of paths, with given delay and Doppler values. We then propose a low-complexity message passing (MP) detection algorithm, which is suitable for large-scale OTFS taking advantage of the inherent channel sparsity. Since the fractional Doppler paths (i.e., not exactly aligned with the Doppler taps) produce the inter Doppler interference (IDI), we adapt the MP detection algorithm to compensate for the effect of IDI in order to further improve performance. Simulations results illustrate the superior performance gains of OTFS over OFDM under various channel conditions.
Leveraging Weakly Annotated Data for Fashion Image Retrieval and Label Prediction
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we present a method to learn a visual representation adapted for e-commerce products. Based on weakly supervised learning, our model learns from noisy datasets crawled on e-commerce website catalogs and does not require any manual labeling. We show that our representation can be used for downward classification tasks over clothing categories with different levels of granularity. We also demonstrate that the learnt representation is suitable for image retrieval. We achieve nearly state-of-art results on the DeepFashion In-Shop Clothes Retrieval and Categories Attributes Prediction tasks, without using the provided training set.
Prosodic Features from Large Corpora of Child-Directed Speech as Predictors of the Age of Acquisition of Words
Venue: arXiv cs.CL 2017
Year: 2017

The impressive ability of children to acquire language is a widely studied phenomenon, and the factors influencing the pace and patterns of word learning remains a subject of active research. Although many models predicting the age of acquisition of words have been proposed, little emphasis has been directed to the raw input children achieve. In this work we present a comparatively large-scale multi-modal corpus of prosody-text aligned child directed speech. Our corpus contains automatically extracted word-level prosodic features, and we investigate the utility of this information as predictors of age of acquisition. We show that prosody features boost predictive power in a regularized regression, and demonstrate their utility in the context of a multi-modal factorized language models trained and tested on child-directed speech.
Routing Games over Time with FIFO policy
Venue: arXiv cs.GT 2017
Year: 2017

We study atomic routing games where every agent travels both along its decided edges and through time. The agents arriving on an edge are first lined up in a \emph{first-in-first-out} queue and may wait: an edge is associated with a capacity, which defines how many agents-per-time-step can pop from the queue's head and enter the edge, to transit for a fixed delay. We show that the best-response optimization problem is not approximable, and that deciding the existence of a Nash equilibrium is complete for the second level of the polynomial hierarchy. Then, we drop the rationality assumption, introduce a behavioral concept based on GPS navigation, and study its worst-case efficiency ratio to coordination.
Surjective H-Colouring over Reflexive Digraphs
Venue: arXiv cs.CC 2017
Year: 2017

The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, the property of a structure that all of its endomorphisms that do not have range of size 1 are automorphisms, as a means to obtain complexity-theoretic classifications of Surjective H-Colouring in the case of reflexive digraphs. Chen [2014] proved, in the setting of constraint satisfaction problems, that Surjective H-Colouring is NP-complete if H has the property that all of its polymorphisms are essentially unary. We give the first concrete application of his result by showing that every endo-trivial reflexive digraph H has this property. We then use the concept of endo-triviality to prove, as our main result, a dichotomy for Surjective H-Colouring when H is a reflexive tournament: if H is transitive, then Surjective H-Colouring is in NL, otherwise it is NP-complete. By combining this result with some known and new results we obtain a complexity classification for Surjective H-Colouring when H is a partially reflexive digraph of size at most 3.
Compositional Construction of Finite State Abstractions for Stochastic Control Systems
Venue: arXiv cs.SY 2017
Year: 2017

Controller synthesis techniques for continuous systems with respect to temporal logic specifications typically use a finite-state symbolic abstraction of the system. Constructing this abstraction for the entire system is computationally expensive, and does not exploit natural decompositions of many systems into interacting components. We have recently introduced a new relation, called (approximate) disturbance bisimulation for compositional symbolic abstraction to help scale controller synthesis for temporal logic to larger systems. In this paper, we extend the results to stochastic control systems modeled by stochastic differential equations. Given any stochastic control system satisfying a stochastic version of the incremental input-to-state stability property and a positive error bound, we show how to construct a finite-state transition system (if there exists one) which is disturbance bisimilar to the given stochastic control system. Given a network of stochastic control systems, we give conditions on the simultaneous existence of disturbance bisimilar abstractions to every component allowing for compositional abstraction of the network system.
Scale Adaptive Clustering of Multiple Structures
Venue: arXiv cs.CV 2017
Year: 2017

We propose the segmentation of noisy datasets into Multiple Inlier Structures with a new Robust Estimator (MISRE). The scale of each individual structure is estimated adaptively from the input data and refined by mean shift, without tuning any parameter in the process, or manually specifying thresholds for different estimation problems. Once all the data points were classified into separate structures, these structures are sorted by their densities with the strongest inlier structures coming out first. Several 2D and 3D synthetic and real examples are presented to illustrate the efficiency, robustness and the limitations of the MISRE algorithm.
An Assessment of Data Transfer Performance for Large-Scale Climate Data Analysis and Recommendations for the Data Infrastructure for CMIP6
Venue: arXiv cs.DC 2017
Year: 2017

We document the data transfer workflow, data transfer performance, and other aspects of staging approximately 56 terabytes of climate model output data from the distributed Coupled Model Intercomparison Project (CMIP5) archive to the National Energy Research Supercomputing Center (NERSC) at the Lawrence Berkeley National Laboratory required for tracking and characterizing extratropical storms, a phenomena of importance in the mid-latitudes. We present this analysis to illustrate the current challenges in assembling multi-model data sets at major computing facilities for large-scale studies of CMIP5 data. Because of the larger archive size of the upcoming CMIP6 phase of model intercomparison, we expect such data transfers to become of increasing importance, and perhaps of routine necessity. We find that data transfer rates using the ESGF are often slower than what is typically available to US residences and that there is significant room for improvement in the data transfer capabilities of the ESGF portal and data centers both in terms of workflow mechanics and in data transfer performance. We believe performance improvements of at least an order of magnitude are within technical reach using current best practices, as illustrated by the performance we achieved in transferring the complete raw data set between two high performance computing facilities. To achieve these performance improvements, we recommend: that current best practices (such as the Science DMZ model) be applied to the data servers and networks at ESGF data centers; that sufficient financial and human resources be devoted at the ESGF data centers for systems and network engineering tasks to support high performance data movement; and that performance metrics for data transfer between ESGF data centers and major computing facilities used for climate data analysis be established, regularly tested, and published.
A Policy Search Method For Temporal Logic Specified Reinforcement Learning Tasks
Venue: arXiv cs.AI 2017
Year: 2017

Reward engineering is an important aspect of reinforcement learning. Whether or not the user's intentions can be correctly encapsulated in the reward function can significantly impact the learning outcome. Current methods rely on manually crafted reward functions that often require parameter tuning to obtain the desired behavior. This operation can be expensive when exploration requires systems to interact with the physical world. In this paper, we explore the use of temporal logic (TL) to specify tasks in reinforcement learning. TL formula can be translated to a real-valued function that measures its level of satisfaction against a trajectory. We take advantage of this function and propose temporal logic policy search (TLPS), a model-free learning technique that finds a policy that satisfies the TL specification. A set of simulated experiments are conducted to evaluate the proposed approach.
Real time text localization for Indoor Mobile Robot Navigation
Venue: arXiv cs.RO 2017
Year: 2017

Scene text is an important feature to be extracted, especially in vision-based mobile robot navigation as many potential landmarks such as nameplates and information signs contain text. In this paper, a novel two-step text localization method for Indoor Mobile Robot Navigation is introduced. This method is based on morphological operators and machine learning techniques and can be used in real time environments. The proposed method has two steps. At First, a new set of morphological operators is applied with a particular sequence to extract high contrast areas that have high probability of text existence. Using of morphological operators has many advantages such as: high computation speed, being invariant to several geometrical transformations like translation, rotations, and scaling, and being able to extract all areas containing text. After extracting text candidate regions, a set of nine features are extracted for accurate detection and deletion of the regions that don't have text. These features are descriptors for texture properties and are computed in real time. Then, we use a SVM classifier to detect the existence of text in the region. Performance of the proposed algorithm is compared against a number of widely used text localization algorithms and the results show that this method can quickly and effectively localize and extract text regions from real scenes and can be used in mobile robot navigation under an indoor environment to detect text based landmarks.
KeyVec: Key-semantics Preserving Document Representations
Venue: arXiv cs.CL 2017
Year: 2017

Previous studies have demonstrated the empirical success of word embeddings in various applications. In this paper, we investigate the problem of learning distributed representations for text documents which many machine learning algorithms take as input for a number of NLP tasks. We propose a neural network model, KeyVec, which learns document representations with the goal of preserving key semantics of the input text. It enables the learned low-dimensional vectors to retain the topics and important information from the documents that will flow to downstream tasks. Our empirical evaluations show the superior quality of KeyVec representations in two different document understanding tasks.
Edina: Building an Open Domain Socialbot with Self-dialogues
Venue: arXiv cs.CL 2017
Year: 2017

We present Edina, the University of Edinburgh's social bot for the Amazon Alexa Prize competition. Edina is a conversational agent whose responses utilize data harvested from Amazon Mechanical Turk (AMT) through an innovative new technique we call self-dialogues. These are conversations in which a single AMT Worker plays both participants in a dialogue. Such dialogues are surprisingly natural, efficient to collect and reflective of relevant and/or trending topics. These self-dialogues provide training data for a generative neural network as well as a basis for soft rules used by a matching score component. Each match of a soft rule against a user utterance is associated with a confidence score which we show is strongly indicative of reply quality, allowing this component to self-censor and be effectively integrated with other components. Edina's full architecture features a rule-based system backing off to a matching score, backing off to a generative neural network. Our hybrid data-driven methodology thus addresses both coverage limitations of a strictly rule-based approach and the lack of guarantees of a strictly machine-learning approach.
Photorealistic Style Transfer with Screened Poisson Equation
Venue: arXiv cs.CV 2017
Year: 2017

Recent work has shown impressive success in transferring painterly style to images. These approaches, however, fall short of photorealistic style transfer. Even when both the input and reference images are photographs, the output still exhibits distortions reminiscent of a painting. In this paper we propose an approach that takes as input a stylized image and makes it more photorealistic. It relies on the Screened Poisson Equation, maintaining the fidelity of the stylized image while constraining the gradients to those of the original input image. Our method is fast, simple, fully automatic and shows positive progress in making a stylized image photorealistic. Our results exhibit finer details and are less prone to artifacts than the state-of-the-art.
Poor Peering: a reflexion about a RIXP
Venue: arXiv cs.NI 2017
Year: 2017

Since more than twenty years, Internet evolves as well as users' needs. and the users' needs too. The need of bandwidth growths every day with the new usages. In this context, with megabit per second count. There is a real business behind our free access to web site. From a group of island, the economy of bandwidth can be a major challenge. Installing a Regional Internet eXchange Point (RIXP) can be a solution to keep regional Internet traffic. This paper brings a reflexion about where to install a RIXP in the Indian Ocean Area (IOA). As there is a lot of different countries and stakes, we (stay) only on an scientist approach.
SCARF: A Biomedical Association Rule Finding Webserver
Venue: arXiv cs.DB 2017
Year: 2017

The analysis of enormous datasets with missing data entries is a standard task in biological and medical data processing. Large-scale, multi-institution clinical studies are the typical examples of such datasets. These sets make possible the search for multi-parametric relations since from the plenty of the data one is likely to find a satisfying number of subjects with the required parameter ensembles. Specifically, finding combinatorial biomarkers for some given condition also needs a very large dataset to analyze. For this goal, statistical regression analysis is not the preferred tool of choice, since (i) the {\em a priori} knowledge of the parameter-sets to analyze is missing, and (ii) typically relatively few subjects have the interesting parameter-value ensembles for the analysis. For fast and automatic multi-parametric relation discovery association-rule finding tools are used for more than two decades in the data-mining community. Here we present the SCARF webserver for {\em generalized} association rule mining. Association rules are of the form: $a$ AND $b$ AND ... AND $x \rightarrow y$, meaning that the presence of properties $a$ AND $b$ AND ... AND $x$ implies property $y$; our algorithm finds generalized association rules, since it also finds logical disjunctions (i.e., ORs) at the left-hand side, allowing the discovery of more complex rules in a more compressed form in the database. This feature also helps reducing the typically very large result-tables of such studies, since allowing ORs in the left-hand side of a single rule could include dozens of classical rules. The capabilities of the SCARF algorithm were demonstrated in mining the Alzheimer's database of the Coalition Against Major Diseases (CAMD) in our recent publication (Archives of Gerontology and Geriatrics Vol. 73, pp. 300-307, 2017). Here we describe the webserver implementation of the algorithm.