OpenRaiser/Intern-Atlas huggingface dataset:
Competitive Routing in Hybrid Communication Networks
Venue: arXiv cs.DC 2018
Year: 2018

Routing is a challenging problem for wireless ad hoc networks, especially when the nodes are mobile and spread so widely that in most cases multiple hops are needed to route a message from one node to another. In fact, it is known that any online routing protocol has a poor performance in the worst case, in a sense that there is a distribution of nodes resulting in bad routing paths for that protocol, even if the nodes know their geographic positions and the geographic position of the destination of a message is known. The reason for that is that radio holes in the ad hoc network may require messages to take long detours in order to get to a destination, which are hard to find in an online fashion. In this paper, we assume that the wireless ad hoc network can make limited use of long-range links provided by a global communication infrastructure like a cellular infrastructure or a satellite in order to compute an abstraction of the wireless ad hoc network that allows the messages to be sent along near-shortest paths in the ad hoc network. We present distributed algorithms that compute an abstraction of the ad hoc network in $\mathcal{O}\left(\log ^2 n\right)$ time using long-range links, which results in $c$-competitive routing paths between any two nodes of the ad hoc network for some constant $c$ if the convex hulls of the radio holes do not intersect. We also show that the storage needed for the abstraction just depends on the number and size of the radio holes in the wireless ad hoc network and is independent on the total number of nodes, and this information just has to be known to a few nodes for the routing to work.
On the Long-Term Memory of Deep Recurrent Networks
Venue: arXiv cs.LG 2018
Year: 2018

A key attribute that drives the unprecedented success of modern Recurrent Neural Networks (RNNs) on learning tasks which involve sequential data, is their ability to model intricate long-term temporal dependencies. However, a well established measure of RNNs long-term memory capacity is lacking, and thus formal understanding of the effect of depth on their ability to correlate data throughout time is limited. Specifically, existing depth efficiency results on convolutional networks do not suffice in order to account for the success of deep RNNs on data of varying lengths. In order to address this, we introduce a measure of the network's ability to support information flow across time, referred to as the Start-End separation rank, which reflects the distance of the function realized by the recurrent network from modeling no dependency between the beginning and end of the input sequence. We prove that deep recurrent networks support Start-End separation ranks which are combinatorially higher than those supported by their shallow counterparts. Thus, we establish that depth brings forth an overwhelming advantage in the ability of recurrent networks to model long-term dependencies, and provide an exemplar of quantifying this key attribute which may be readily extended to other RNN architectures of interest, e.g. variants of LSTM networks. We obtain our results by considering a class of recurrent networks referred to as Recurrent Arithmetic Circuits, which merge the hidden state with the input via the Multiplicative Integration operation, and empirically demonstrate the discussed phenomena on common RNNs. Finally, we employ the tool of quantum Tensor Networks to gain additional graphic insight regarding the complexity brought forth by depth in recurrent networks.
Logical relations for coherence of effect subtyping
Venue: arXiv cs.PL 2018
Year: 2018

A coercion semantics of a programming language with subtyping is typically defined on typing derivations rather than on typing judgments. To avoid semantic ambiguity, such a semantics is expected to be coherent, i.e., independent of the typing derivation for a given typing judgment. In this article we present heterogeneous, biorthogonal, step-indexed logical relations for establishing the coherence of coercion semantics of programming languages with subtyping. To illustrate the effectiveness of the proof method, we develop a proof of coherence of a type-directed, selective CPS translation from a typed call-by-value lambda calculus with delimited continuations and control-effect subtyping. The article is accompanied by a Coq formalization that relies on a novel shallow embedding of a logic for reasoning about step-indexing.
Complete 3D Scene Parsing from an RGBD Image
Venue: arXiv cs.CV 2018
Year: 2018

One major goal of vision is to infer physical models of objects, surfaces, and their layout from sensors. In this paper, we aim to interpret indoor scenes from one RGBD image. Our representation encodes the layout of orthogonal walls and the extent of objects, modeled with CAD-like 3D shapes. We parse both the visible and occluded portions of the scene and all observable objects, producing a complete 3D parse. Such a scene interpretation is useful for robotics and visual reasoning, but difficult to produce due to the well-known challenge of segmentation, the high degree of occlusion, and the diversity of objects in indoor scenes. We take a data-driven approach, generating sets of potential object regions, matching to regions in training images, and transferring and aligning associated 3D models while encouraging fit to observations and spatial consistency. We use support inference to aid interpretation and propose a retrieval scheme that uses convolutional neural networks (CNNs) to classify regions and retrieve objects with similar shapes. We demonstrate the performance of our method on our newly annotated NYUd v2 dataset with detailed 3D shapes.
A Deep Learning Approach to the Citywide Traffic Accident Risk Prediction
Venue: arXiv cs.CY 2018
Year: 2018

With the rapid development of urbanization, the boom of vehicle numbers has resulted in serious traffic accidents, which led to casualties and huge economic losses. The ability to predict the risk of traffic accident is important in the prevention of the occurrence of accidents and to reduce the damages caused by accidents in a proactive way. However, traffic accident risk prediction with high spatiotemporal resolution is difficult, mainly due to the complex traffic environment, human behavior, and lack of real-time traffic-related data. In this study, we collected big traffic accident data. By analyzing the spatial and temporal patterns of traffic accident frequency, we presented the spatiotemporal correlation of traffic accidents. Based on the patterns we found in analysis, we proposed a high accurate deep learning model based on recurrent neural network toward the prediction of traffic accident risk. The predictive accident risk can be potential applied to the traffic accident warning system. The proposed method can be integrated into an intelligent traffic control system toward a more reasonable traffic prediction and command organization.
Deterministic Approximate Methods for Maximum Consensus Robust Fitting
Venue: arXiv cs.CV 2018
Year: 2018

Maximum consensus estimation plays a critically important role in robust fitting problems in computer vision. Currently, the most prevalent algorithms for consensus maximization draw from the class of randomized hypothesize-and-verify algorithms, which are cheap but can usually deliver only rough approximate solutions. On the other extreme, there are exact algorithms which are exhaustive search in nature and can be costly for practical-sized inputs. This paper fills the gap between the two extremes by proposing deterministic algorithms to approximately optimize the maximum consensus criterion. Our work begins by reformulating consensus maximization with linear complementarity constraints. Then, we develop two novel algorithms: one based on non-smooth penalty method with a Frank-Wolfe style optimization scheme, the other based on the Alternating Direction Method of Multipliers (ADMM). Both algorithms solve convex subproblems to efficiently perform the optimization. We demonstrate the capability of our algorithms to greatly improve a rough initial estimate, such as those obtained using least squares or a randomized algorithm. Compared to the exact algorithms, our approach is much more practical on realistic input sizes. Further, our approach is naturally applicable to estimation problems with geometric residuals
Direction of arrival estimation for multiple sound sources using convolutional recurrent neural network
Venue: arXiv cs.SD 2018
Year: 2018

This paper proposes a deep neural network for estimating the directions of arrival (DOA) of multiple sound sources. The proposed stacked convolutional and recurrent neural network (DOAnet) generates a spatial pseudo-spectrum (SPS) along with the DOA estimates in both azimuth and elevation. We avoid any explicit feature extraction step by using the magnitudes and phases of the spectrograms of all the channels as input to the network. The proposed DOAnet is evaluated by estimating the DOAs of multiple concurrently present sources in anechoic, matched and unmatched reverberant conditions. The results show that the proposed DOAnet is capable of estimating the number of sources and their respective DOAs with good precision and generate SPS with high signal-to-noise ratio.
High-Quality Facial Photo-Sketch Synthesis Using Multi-Adversarial Networks
Venue: arXiv cs.CV 2018
Year: 2018

Synthesizing face sketches from real photos and its inverse have many applications. However, photo/sketch synthesis remains a challenging problem due to the fact that photo and sketch have different characteristics. In this work, we consider this task as an image-to-image translation problem and explore the recently popular generative models (GANs) to generate high-quality realistic photos from sketches and sketches from photos. Recent GAN-based methods have shown promising results on image-to-image translation problems and photo-to-sketch synthesis in particular, however, they are known to have limited abilities in generating high-resolution realistic images. To this end, we propose a novel synthesis framework called Photo-Sketch Synthesis using Multi-Adversarial Networks, (PS2-MAN) that iteratively generates low resolution to high resolution images in an adversarial way. The hidden layers of the generator are supervised to first generate lower resolution images followed by implicit refinement in the network to generate higher resolution images. Furthermore, since photo-sketch synthesis is a coupled/paired translation problem, we leverage the pair information using CycleGAN framework. Both Image Quality Assessment (IQA) and Photo-Sketch Matching experiments are conducted to demonstrate the superior performance of our framework in comparison to existing state-of-the-art solutions. Code available at: https://github.com/lidan1/PhotoSketchMAN.
Minimal Reachability is Hard To Approximate
Venue: arXiv cs.SY 2018
Year: 2018

In this note, we consider the problem of choosing which nodes of a linear dynamical system should be actuated so that the state transfer from the system's initial condition to a given final state is possible. Assuming a standard complexity hypothesis, we show that this problem cannot be efficiently solved or approximated in polynomial, or even quasi-polynomial, time.
Convolutional Neural Networks Via Node-Varying Graph Filters
Venue: arXiv cs.LG 2018
Year: 2018

Convolutional neural networks (CNNs) are being applied to an increasing number of problems and fields due to their superior performance in classification and regression tasks. Since two of the key operations that CNNs implement are convolution and pooling, this type of networks is implicitly designed to act on data described by regular structures such as images. Motivated by the recent interest in processing signals defined in irregular domains, we advocate a CNN architecture that operates on signals supported on graphs. The proposed design replaces the classical convolution not with a node-invariant graph filter (GF), which is the natural generalization of convolution to graph domains, but with a node-varying GF. This filter extracts different local features without increasing the output dimension of each layer and, as a result, bypasses the need for a pooling stage while involving only local operations. A second contribution is to replace the node-varying GF with a hybrid node-varying GF, which is a new type of GF introduced in this paper. While the alternative architecture can still be run locally without requiring a pooling stage, the number of trainable parameters is smaller and can be rendered independent of the data dimension. Tests are run on a synthetic source localization problem and on the 20NEWS dataset.
JESC: Japanese-English Subtitle Corpus
Venue: arXiv cs.CL 2018
Year: 2018

In this paper we describe the Japanese-English Subtitle Corpus (JESC). JESC is a large Japanese-English parallel corpus covering the underrepresented domain of conversational dialogue. It consists of more than 3.2 million examples, making it the largest freely available dataset of its kind. The corpus was assembled by crawling and aligning subtitles found on the web. The assembly process incorporates a number of novel preprocessing elements to ensure high monolingual fluency and accurate bilingual alignments. We summarize its contents and evaluate its quality using human experts and baseline machine translation (MT) systems.
Tensorizing Generative Adversarial Nets
Venue: arXiv cs.LG 2018
Year: 2018

Generative Adversarial Network (GAN) and its variants exhibit state-of-the-art performance in the class of generative models. To capture higher-dimensional distributions, the common learning procedure requires high computational complexity and a large number of parameters. The problem of employing such massive framework arises when deploying it on a platform with limited computational power such as mobile phones. In this paper, we present a new generative adversarial framework by representing each layer as a tensor structure connected by multilinear operations, aiming to reduce the number of model parameters by a large factor while preserving the generative performance and sample quality. To learn the model, we employ an efficient algorithm which alternatively optimizes both discriminator and generator. Experimental outcomes demonstrate that our model can achieve high compression rate for model parameters up to $35$ times when compared to the original GAN for MNIST dataset.
Synergy in the Knowledge Base of U.S. Innovation Systems at National, State, and Regional Levels: The Contributions of High-Tech Manufacturing and Knowledge-Intensive Services
Venue: arXiv cs.DL 2018
Year: 2018

Using information theory, we measure innovation systemness as synergy among size-classes, zip-codes, and technological classes (NACE-codes) for 8.5 million American companies. The synergy at the national level is decomposed at the level of states, Core-Based Statistical Areas (CBSA), and Combined Statistical Areas (CSA). We zoom in to the state of California and in more detail to Silicon Valley. Our results do not support the assumption of a national system of innovations in the U.S.A. Innovation systems appear to operate at the level of the states; the CBSA are too small, so that systemness spills across their borders. Decomposition of the sample in terms of high-tech manufacturing (HTM), medium-high-tech manufacturing (MHTM), knowledge-intensive services (KIS), and high-tech services (HTKIS) does not change this pattern, but refines it. The East Coast -- New Jersey, Boston, and New York -- and California are the major players, with Texas a third one in the case of HTKIS. Chicago and industrial centers in the Midwest also contribute synergy. Within California, Los Angeles contributes synergy in the sectors of manufacturing, the San Francisco area in KIS. Knowledge-intensive services in Silicon Valley and the Bay area -- a CSA composed of seven CBSA -- spill over to other regions and even globally.
Statistical Significance and Effect Sizes of Differences among Research Universities at the Level of Nations and Worldwide based on the Leiden Rankings
Venue: arXiv cs.DL 2018
Year: 2018

The Leiden Rankings can be used for grouping research universities by considering universities which are not statistically significantly different as homogeneous sets. The groups and intergroup relations can be analyzed and visualized using tools from network analysis. Using the so-called "excellence indicator" PPtop-10%--the proportion of the top-10% most-highly-cited papers assigned to a university--we pursue a classification using (i) overlapping stability intervals, (ii) statistical-significance tests, and (iii) effect sizes of differences among 902 universities in 54 countries; we focus on the UK, Germany, Brazil, and the USA as national examples. Although the groupings remain largely the same using different statistical significance levels or overlapping stability intervals, these classifications are uncorrelated with those based on effect sizes. Effect sizes for the differences between universities are small (w <.2). The more detailed analysis of universities at the country level suggests that distinctions beyond three or perhaps four groups of universities (high, middle, low) may not be meaningful. Given similar institutional incentives, isomorphism within each eco-system of universities should not be underestimated. Our results suggest that networks based on overlapping stability intervals can provide a first impression of the relevant groupings among universities. However, the clusters are not well-defined divisions between groups of universities.
A Dynamic Hash Table for the GPU
Venue: arXiv cs.DC 2018
Year: 2018

We design and implement a fully concurrent dynamic hash table for GPUs with comparable performance to the state of the art static hash tables. We propose a warp-cooperative work sharing strategy that reduces branch divergence and provides an efficient alternative to the traditional way of per-thread (or per-warp) work assignment and processing. By using this strategy, we build a dynamic non-blocking concurrent linked list, the slab list, that supports asynchronous, concurrent updates (insertions and deletions) as well as search queries. We use the slab list to implement a dynamic hash table with chaining (the slab hash). On an NVIDIA Tesla K40c GPU, the slab hash performs updates with up to 512 M updates/s and processes search queries with up to 937 M queries/s. We also design a warp-synchronous dynamic memory allocator, SlabAlloc, that suits the high performance needs of the slab hash. SlabAlloc dynamically allocates memory at a rate of 600 M allocations/s, which is up to 37x faster than alternative methods in similar scenarios.
Forgetting the Forgotten with Letheia, Concealing Content Deletion from Persistent Observers
Venue: arXiv cs.CR 2018
Year: 2018

Most social platforms offer mechanisms allowing users to delete their posts, and a significant fraction of users exercise this right to be forgotten. However, ironically, users' attempt to reduce attention to sensitive posts via deletion, in practice, attracts unwanted attention from stalkers specifically to those posts. Thus, deletions may leave users more vulnerable to attacks on their privacy in general. Users hoping to make their posts forgotten face a "damned if I do, damned if I don't" dilemma. Many are shifting towards ephemeral social platform like Snapchat, which will deprive us of important user-data archival. In the form of intermittent withdrawals, we present, Lethe, a novel solution to this problem of forgetting the forgotten. If the next-generation social platforms are willing to give up the uninterrupted availability of non-deleted posts by a very small fraction, Lethe provides privacy to the deleted posts over long durations. In presence of Lethe, an adversarial observer becomes unsure if some posts are permanently deleted or just temporarily withdrawn by Lethe; at the same time, the adversarial observer is overwhelmed by a large number of falsely flagged undeleted posts. To demonstrate the feasibility and performance of Lethe, we analyze large-scale real data about users' deletion over Twitter and thoroughly investigate how to choose time duration distributions for alternating between temporary withdrawals and resurrections of non-deleted posts. We find a favorable trade-off between privacy, availability and adversarial overhead in different settings for users exercising their right to delete. We show that, even against an ultimate adversary with an uninterrupted access to the entire platform, Lethe offers deletion privacy for up to 3 months from the time of deletion, while maintaining content availability as high as 95% and keeping the adversarial precision to 20%.
Flexible Prior Distributions for Deep Generative Models
Venue: arXiv cs.LG 2018
Year: 2018

We consider the problem of training generative models with deep neural networks as generators, i.e. to map latent codes to data points. Whereas the dominant paradigm combines simple priors over codes with complex deterministic models, we argue that it might be advantageous to use more flexible code distributions. We demonstrate how these distributions can be induced directly from the data. The benefits include: more powerful generative models, better modeling of latent structure and explicit control of the degree of generalization.
A Model-Based Approach to Security Analysis for Cyber-Physical Systems
Venue: arXiv cs.CR 2018
Year: 2018

Evaluating the security of cyber-physical systems throughout their life cycle is necessary to assure that they can be deployed and operated in safety-critical applications, such as infrastructure, military, and transportation. Most safety and security decisions that can have major effects on mitigation strategy options after deployment are made early in the system's life cycle. To allow for a vulnerability analysis before deployment, a sufficient well-formed model has to be constructed. To construct such a model we produce a taxonomy of attributes; that is, a generalized schema for system attributes. This schema captures the necessary specificity that characterizes a possible real system and can also map to the attack vector space associated with the model's attributes. In this way, we can match possible attack vectors and provide architectural mitigation at the design phase. We present a model of a flight control system encoded in the Systems Modeling Language, commonly known as SysML, but also show agnosticism with respect to the modeling language or tool used.
Finding all Maximal Area Parallelograms in a Convex Polygon
Venue: arXiv cs.CG 2018
Year: 2018

Polygon inclusion problems have been studied extensively in geometric optimization. In this paper, we consider the variant of computing the maximum area parallelograms (MAPs) and all the locally maximal area parallelograms (LMAPs) in a given convex polygon. By proving and utilizing several structural properties of the LMAPs, we compute all of them (including all the MAPs) in $O(n^2)$ time, where $n$ denotes the number of edges of the given polygon. In addition, we prove that the LMAPs interleave each other and thus the number of LMAPs is $O(n)$. We discuss applications of our result to, among others, the problem of computing the maximum area centrally-symmetric convex body inside a convex polygon, and the simplest case of the Heilbronn triangle problem.