OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Generation of Geographically Accurate Transit Maps
Venue: arXiv cs.CG 2017
Year: 2017

We present LOOM (Line-Ordering Optimized Maps), a fully automatic generator of geographically accurate transit maps. The input to LOOM is data about the lines of a given transit network, namely for each line, the sequence of stations it serves and the geographical course the vehicles of this line take. We parse this data from GTFS, the prevailing standard for public transit data. LOOM proceeds in three stages: (1) construct a so-called line graph, where edges correspond to segments of the network with the same set of lines following the same course; (2) construct an ILP that yields a line ordering for each edge which minimizes the total number of line crossings and line separations; (3) based on the line graph and the ILP solution, draw the map. As a naive ILP formulation is too demanding, we derive a new custom-tailored formulation which requires significantly fewer constraints. Furthermore, we present engineering techniques which use structural properties of the line graph to further reduce the ILP size. For the subway network of New York, we can reduce the number of constraints from 229,000 in the naive ILP formulation to about 4,500 with our techniques, enabling solution times of less than a second. Since our maps respect the geography of the transit network, they can be used for tiles and overlays in typical map services. Previous research work either did not take the geographical course of the lines into account, or was concerned with schematic maps without optimizing line crossings or line separations.
Generating Nontrivial Melodies for Music as a Service
Venue: arXiv cs.SD 2017
Year: 2017

We present a hybrid neural network and rule-based system that generates pop music. Music produced by pure rule-based systems often sounds mechanical. Music produced by machine learning sounds better, but still lacks hierarchical temporal structure. We restore temporal hierarchy by augmenting machine learning with a temporal production grammar, which generates the music's overall structure and chord progressions. A compatible melody is then generated by a conditional variational recurrent autoencoder. The autoencoder is trained with eight-measure segments from a corpus of 10,000 MIDI files, each of which has had its melody track and chord progressions identified heuristically. The autoencoder maps melody into a multi-dimensional feature space, conditioned by the underlying chord progression. A melody is then generated by feeding a random sample from that space to the autoencoder's decoder, along with the chord progression generated by the grammar. The autoencoder can make musically plausible variations on an existing melody, suitable for recurring motifs. It can also reharmonize a melody to a new chord progression, keeping the rhythm and contour. The generated music compares favorably with that generated by other academic and commercial software designed for the music-as-a-service industry.
Asymptotic Performance of Coded Slotted ALOHA with Multi Packet Reception
Venue: arXiv cs.IT 2017
Year: 2017

In this letter, we develop a converse bound on the asymptotic load threshold of coded slotted ALOHA (CSA) schemes with K-multi packet reception capabilities at the receiver. Density evolution is used to track the average probability of packet segment loss and an area matching condition is applied to obtain the converse. For any given CSA rate, the converse normalized to K increases with K, which is in contrast with the results obtained so far for slotted ALOHA schemes based on successive interference cancellation. We show how the derived bound can be approached using spatially-coupled CSA.
Enumeration Problems for Regular Path Queries
Venue: arXiv cs.DB 2017
Year: 2017

Evaluation of regular path queries (RPQs) is a central problem in graph databases. We investigate the corresponding enumeration problem, that is, given a graph and an RPQ, enumerate all paths in the graph that match the RPQ. We consider several versions of this problem, corresponding to different semantics of RPQs that have recently been considered: arbitrary paths, shortest paths, simple paths, and trails. Whereas arbitrary and shortest paths can be enumerated in polynomial delay, the situation is much more intricate for simple paths and trails. For instance, already the question if a given graph contains a simple path or trail of a certain length has cases with highly non-trivial solutions and cases that are long-standing open problems. In this setting, we study RPQ evaluation from a parameterized complexity perspective. We define a class of simple transitive expressions that is prominent in practice and for which we can prove two dichotomy-like results: one for simple paths and one for trails paths. We observe that, even though simple path semantics and trail semantics are intractable for RPQs in general, they are feasible for the vast majority of the kinds of RPQs that users use in practice. At the heart of this study is a result of independent interest on the parameterized complexity of finding disjoint paths in graphs: the two disjoint paths problem is W[1]-hard if parameterized by the length of one of the two paths.
A Semantic Relevance Based Neural Network for Text Summarization and Text Simplification
Venue: arXiv cs.CL 2017
Year: 2017

Text summarization and text simplification are two major ways to simplify the text for poor readers, including children, non-native speakers, and the functionally illiterate. Text summarization is to produce a brief summary of the main ideas of the text, while text simplification aims to reduce the linguistic complexity of the text and retain the original meaning. Recently, most approaches for text summarization and text simplification are based on the sequence-to-sequence model, which achieves much success in many text generation tasks. However, although the generated simplified texts are similar to source texts literally, they have low semantic relevance. In this work, our goal is to improve semantic relevance between source texts and simplified texts for text summarization and text simplification. We introduce a Semantic Relevance Based neural model to encourage high semantic similarity between texts and summaries. In our model, the source text is represented by a gated attention encoder, while the summary representation is produced by a decoder. Besides, the similarity score between the representations is maximized during training. Our experiments show that the proposed model outperforms the state-of-the-art systems on two benchmark corpus.
Bilingual Words and Phrase Mappings for Marathi and Hindi SMT
Venue: arXiv cs.CL 2017
Year: 2017

Lack of proper linguistic resources is the major challenges faced by the Machine Translation system developments when dealing with the resource poor languages. In this paper, we describe effective ways to utilize the lexical resources to improve the quality of statistical machine translation. Our research on the usage of lexical resources mainly focused on two ways, such as; augmenting the parallel corpus with more vocabulary and to provide various word forms. We have augmented the training corpus with various lexical resources such as lexical words, function words, kridanta pairs and verb phrases. We have described the case studies, evaluations and detailed error analysis for both Marathi to Hindi and Hindi to Marathi machine translation systems. From the evaluations we observed that, there is an incremental growth in the quality of machine translation as the usage of various lexical resources increases. Moreover, usage of various lexical resources helps to improve the coverage and quality of machine translation where limited parallel corpus is available.
Exploring the Urban - Rural Incarceration Divide: Drivers of Local Jail Incarceration Rates in the U.S
Venue: arXiv cs.CY 2017
Year: 2017

As the rate of incarceration in the United States continues to grow, a large body of research has been primarily focused on understanding the determinants and drivers of federal and state prison growth. However, local jail systems, with 11 million admissions each year, have generated less research attention even though they have a far broader impact on communities. Preliminary time trend analysis conducted by the Vera Institute of Justice (Vera) uncovered disparities in county jail incarceration rates by geography. Contrary to assumptions that incarceration is an urban phenomenon, Vera discovered that during the past few decades, pretrial jail rates have declined in many urban areas whereas rates have grown or remained flat in rural counties. In an effort to uncover the factors contributing to continued jail growth in rural areas, Vera joined forces with Two Sigma's Data Clinic, a volunteer-based program that leverages employees' data science expertise. Using county jail data from 2000 - 2013 and county-specific demographic, political, socioeconomic, jail and prison population variables, a generalized estimating equations (GEE) model was specified to account for correlations within counties over time. The results revealed that county-level poverty, police expenditures, and spillover effects from other county and state authorities are all significant predictors of local jail rates. In addition, geographic investigation of model residuals revealed clusters of counties where observed rates were much higher (and much lower) than expected conditioned upon county variables.
Evaluation of the Performance of Adaptive HTTP Streaming Systems
Venue: arXiv cs.MM 2017
Year: 2017

Adaptive video streaming over HTTP is becoming omnipresent in our daily life. In the past, dozens of research papers have proposed novel approaches to address different aspects of adaptive streaming and a decent amount of player implementations (commercial and open source) are available. However, state of the art evaluations are sometimes superficial as many proposals only investigate a certain aspect of the problem or focus on a specific platform - player implementations used in actual services are rarely considered. HTML5 is now available on many platforms and foster the deployment of adaptive media streaming applications. We propose a common evaluation framework for adaptive HTML5 players and demonstrate its applicability by evaluating eight different players which are actually deployed in real-world services.
Performance Prediction and Optimization of Solar Water Heater via a Knowledge-Based Machine Learning Method
Venue: arXiv cs.AI 2017
Year: 2017

Measuring the performance of solar energy and heat transfer systems requires a lot of time, economic cost and manpower. Meanwhile, directly predicting their performance is challenging due to the complicated internal structures. Fortunately, a knowledge-based machine learning method can provide a promising prediction and optimization strategy for the performance of energy systems. In this Chapter, the authors will show how they utilize the machine learning models trained from a large experimental database to perform precise prediction and optimization on a solar water heater (SWH) system. A new energy system optimization strategy based on a high-throughput screening (HTS) process is proposed. This Chapter consists of: i) Comparative studies on varieties of machine learning models (artificial neural networks (ANNs), support vector machine (SVM) and extreme learning machine (ELM)) to predict the performances of SWHs; ii) Development of an ANN-based software to assist the quick prediction and iii) Introduction of a computational HTS method to design a high-performance SWH system.
Agile Calibration Process of Full-Stack Simulation Frameworks for V2X Communications
Venue: arXiv cs.PF 2017
Year: 2017

Computer simulations and real-world car trials are essential to investigate the performance of Vehicle-to-Everything (V2X) networks. However, simulations are imperfect models of the physical reality and can be trusted only when they indicate agreement with the real-world. On the other hand, trials lack reproducibility and are subject to uncertainties and errors. In this paper, we will illustrate a case study where the interrelationship between trials, simulation, and the reality-of-interest is presented. Results are then compared in a holistic fashion. Our study will describe the procedure followed to macroscopically calibrate a full-stack network simulator to conduct high-fidelity full-stack computer simulations.
The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis
Venue: arXiv cs.DS 2017
Year: 2017

The Paulsen problem is a basic open problem in operator theory: Given vectors $u_1, \ldots, u_n \in \mathbb R^d$ that are $ε$-nearly satisfying the Parseval's condition and the equal norm condition, is it close to a set of vectors $v_1, \ldots, v_n \in \mathbb R^d$ that exactly satisfy the Parseval's condition and the equal norm condition? Given $u_1, \ldots, u_n$, the squared distance (to the set of exact solutions) is defined as $\inf_{v} \sum_{i=1}^n \| u_i - v_i \|_2^2$ where the infimum is over the set of exact solutions. Previous results show that the squared distance of any $ε$-nearly solution is at most $O({\rm{poly}}(d,n,ε))$ and there are $ε$-nearly solutions with squared distance at least $Ω(dε)$. The fundamental open question is whether the squared distance can be independent of the number of vectors $n$. We answer this question affirmatively by proving that the squared distance of any $ε$-nearly solution is $O(d^{13/2} ε)$. Our approach is based on a continuous version of the operator scaling algorithm and consists of two parts. First, we define a dynamical system based on operator scaling and use it to prove that the squared distance of any $ε$-nearly solution is $O(d^2 n ε)$. Then, we show that by randomly perturbing the input vectors, the dynamical system will converge faster and the squared distance of an $ε$-nearly solution is $O(d^{5/2} ε)$ when $n$ is large enough and $ε$ is small enough. To analyze the convergence of the dynamical system, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyze the operator scaling algorithm.
Interference Model Similarity Index and Its Applications to mmWave Networks: Extended version
Venue: arXiv cs.IT 2017
Year: 2017

In wireless communication networks, interference models are routinely used for tasks such as performance analysis, optimization, and protocol design. These tasks are heavily affected by the accuracy and tractability of the interference models. Yet, quantifying the accuracy of these models remains a major challenge. In this paper, we propose a new index for assessing the accuracy of any interference model under any network scenario. Specifically, it is based on a new index that quantifies the ability of any interference model in correctly predicting harmful interference events, that is, link outages. We consider a specific wireless scenario of both conventional sub-6~GHz and millimeter-wave (mmWave) networks and demonstrate how our index yields insights into the possibility of simplifying the set of dominant interferers, replacing a Nakagami or Rayleigh random fading by an equivalent deterministic channel, and ignoring antenna sidelobes. Our analysis reveals that in highly directional antenna settings with obstructions, even simple interference models (such as the classical protocol model) are accurate, while with omnidirectional antennas, more sophisticated and complex interference models (such as the classical physical model) are necessary. We further use the proposed index to develop a simple interference model for mmWave networks that can significantly simplify design principles of the important procedures for wireless communication, such as beamforming, interference management, scheduling, and topology control. Our new approach makes it possible to adopt the simplest interference model of adequate accuracy for every wireless network.
On Mitigation of Side-Channel Attacks in 3D ICs: Decorrelating Thermal Patterns from Power and Activity
Venue: arXiv cs.CR 2017
Year: 2017

Various side-channel attacks (SCAs) on ICs have been successfully demonstrated and also mitigated to some degree. In the context of 3D ICs, however, prior art has mainly focused on efficient implementations of classical SCA countermeasures. That is, SCAs tailored for up-and-coming 3D ICs have been overlooked so far. In this paper, we conduct such a novel study and focus on one of the most accessible and critical side channels: thermal leakage of activity and power patterns. We address the thermal leakage in 3D ICs early on during floorplanning, along with tailored extensions for power and thermal management. Our key idea is to carefully exploit the specifics of material and structural properties in 3D ICs, thereby decorrelating the thermal behaviour from underlying power and activity patterns. Most importantly, we discuss powerful SCAs and demonstrate how our open-source tool helps to mitigate them.
Interactive Learning of State Representation through Natural Language Instruction and Explanation
Venue: arXiv cs.AI 2017
Year: 2017

One significant simplification in most previous work on robot learning is the closed-world assumption where the robot is assumed to know ahead of time a complete set of predicates describing the state of the physical world. However, robots are not likely to have a complete model of the world especially when learning a new task. To address this problem, this extended abstract gives a brief introduction to our on-going work that aims to enable the robot to acquire new state representations through language communication with humans.
Search-based Motion Planning for Aggressive Flight in SE(3)
Venue: arXiv cs.RO 2017
Year: 2017

Quadrotors with large thrust-to-weight ratios are able to track aggressive trajectories with sharp turns and high accelerations. In this work, we develop a search-based trajectory planning approach that exploits the quadrotor maneuverability to generate sequences of motion primitives in cluttered environments. We model the quadrotor body as an ellipsoid and compute its flight attitude along trajectories in order to check for collisions against obstacles. The ellipsoid model allows the quadrotor to pass through gaps that are smaller than its diameter with non-zero pitch or roll angles. Without any prior information about the location of gaps and associated attitude constraints, our algorithm is able to find a safe and optimal trajectory that guides the robot to its goal as fast as possible. To accelerate planning, we first perform a lower dimensional search and use it as a heuristic to guide the generation of a final dynamically feasible trajectory. We analyze critical discretization parameters of motion primitive planning and demonstrate the feasibility of the generated trajectories in various simulations and real-world experiments.
Texture Fuzzy Segmentation using Skew Divergence Adaptive Affinity Functions
Venue: arXiv cs.CV 2017
Year: 2017

Digital image segmentation is the process of assigning distinct labels to different objects in a digital image, and the fuzzy segmentation algorithm has been successfully used in the segmentation of images from a wide variety of sources. However, the traditional fuzzy segmentation algorithm fails to segment objects that are characterized by textures whose patterns cannot be successfully described by simple statistics computed over a very restricted area. In this paper, we propose an extension of the fuzzy segmentation algorithm that uses adaptive textural affinity functions to perform the segmentation of such objects on bidimensional images. The adaptive affinity functions compute their appropriate neighborhood size as they compute the texture descriptors surrounding the seed spels (spatial elements), according to the characteristics of the texture being processed. The algorithm then segments the image with an appropriate neighborhood for each object. We performed experiments on mosaic images that were composed using images from the Brodatz database, and compared our results with the ones produced by a recently published texture segmentation algorithm, showing the applicability of our method.
DEBIT: Distributed Energy Beamforming and Information Transfer for Multiway Relay Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a new distributed energy beamforming and information transfer (DEBIT) scheme for realizing simultaneous wireless information and power transfer (SWIPT) in multiway relay networks (MWRNs), where multiple single-antenna users exchange information via an energy-constrained single-antenna relay node. We investigate the optimal transceiver designs to maximize the achievable sum-rate or the harvested power. The resultant sum-rate maximization problem is non-convex and the global optimal solution can be obtained through a three-dimensional search in combination with conventional convex optimization. To reduce the computation complexity, a suboptimal DEBIT scheme is also proposed, for which the optimization problem becomes linear programming. The achievable sum-rate performance is analyzed and a closed-form lower bound is derived for the MWRN with a large number of users. Furthermore, we consider the harvested-power maximization problem under a target sum-rate constraint, and derive a lower bound of the average harvested power for MWRNs with a large number of users. Numerical results show that the DEBIT scheme significantly outperforms the conventional SWIPT and the derived lower bounds are tight.
Micro-Expression Spotting: A Benchmark
Venue: arXiv cs.CV 2017
Year: 2017

Micro-expressions are rapid and involuntary facial expressions, which indicate the suppressed or concealed emotions. Recently, the research on automatic micro-expression (ME) spotting obtains increasing attention. ME spotting is a crucial step prior to further ME analysis tasks. The spotting results can be used as important cues to assist many other human-oriented tasks and thus have many potential applications. In this paper, by investigating existing ME spotting methods, we recognize the immediacy of standardizing the performance evaluation of micro-expression spotting methods. To this end, we construct a micro-expression spotting benchmark (MESB). Firstly, we set up a sliding window based multi-scale evaluation framework. Secondly, we introduce a series of protocols. Thirdly, we also provide baseline results of popular methods. The MESB facilitates the research on ME spotting with fairer and more comprehensive evaluation and also enables to leverage the cutting-edge machine learning tools widely.
Countries' Survival in Networked International Environments
Venue: arXiv cs.SI 2017
Year: 2017

This paper applies a recently developed power allocation game in Li and Morse (2017) to study the countries' survival problem in networked international environments. In the game, countries strategically allocate their power to support the survival of themselves and their friends and to oppose that of their foes, where by a country's survival is meant when the country's total support equals or exceeds its total threats. This paper establishes conditions that characterize different types of networked international environments in which a country may survive, such as when all the antagonism among countries makes up a complete or bipartite graph.