OpenRaiser/Intern-Atlas huggingface dataset:
A Survey of Anticipatory Mobile Networking: Context-Based Classification, Prediction Methodologies, and Optimization Techniques
Venue: arXiv cs.NI 2017
Year: 2017

A growing trend for information technology is to not just react to changes, but anticipate them as much as possible. This paradigm made modern solutions, such as recommendation systems, a ubiquitous presence in today's digital transactions. Anticipatory networking extends the idea to communication technologies by studying patterns and periodicity in human behavior and network dynamics to optimize network performance. This survey collects and analyzes recent papers leveraging context information to forecast the evolution of network conditions and, in turn, to improve network performance. In particular, we identify the main prediction and optimization tools adopted in this body of work and link them with objectives and constraints of the typical applications and scenarios. Finally, we consider open challenges and research directions to make anticipatory networking part of next generation networks.
RankSign: an efficient signature algorithm based on the rank metric
Venue: arXiv cs.CR 2017
Year: 2017

In this paper we propose a new approach to code-based signatures that makes use in particular of rank metric codes. When the classical approach consists in finding the unique preimage of a syndrome through a decoding algorithm, we propose to introduce the notion of mixed decoding of erasures and errors for building signature schemes. In that case the difficult problem becomes, as is the case in lattice-based cryptography, finding a preimage of weight above the Gilbert-Varshamov bound (case where many solutions occur) rather than finding a unique preimage of weight below the Gilbert-Varshamov bound. The paper describes RankSign: a new signature algorithm for the rank metric based on a new mixed algorithm for decoding erasures and errors for the recently introduced Low Rank Parity Check (LRPC) codes. We explain how it is possible (depending on choices of parameters) to obtain a full decoding algorithm which is able to find a preimage of reasonable rank weight for any random syndrome with a very strong probability. We study the semantic security of our signature algorithm and show how it is possible to reduce the unforgeability to direct attacks on the public matrix, so that no information leaks through signatures. Finally, we give several examples of parameters for our scheme, some of which with public key of size $11,520$ bits and signature of size $1728$ bits. Moreover the scheme can be very fast for small base fields.
DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs
Venue: arXiv cs.CV 2017
Year: 2017

In this work we address the task of semantic image segmentation with Deep Learning and make three main contributions that are experimentally shown to have substantial practical merit. First, we highlight convolution with upsampled filters, or 'atrous convolution', as a powerful tool in dense prediction tasks. Atrous convolution allows us to explicitly control the resolution at which feature responses are computed within Deep Convolutional Neural Networks. It also allows us to effectively enlarge the field of view of filters to incorporate larger context without increasing the number of parameters or the amount of computation. Second, we propose atrous spatial pyramid pooling (ASPP) to robustly segment objects at multiple scales. ASPP probes an incoming convolutional feature layer with filters at multiple sampling rates and effective fields-of-views, thus capturing objects as well as image context at multiple scales. Third, we improve the localization of object boundaries by combining methods from DCNNs and probabilistic graphical models. The commonly deployed combination of max-pooling and downsampling in DCNNs achieves invariance but has a toll on localization accuracy. We overcome this by combining the responses at the final DCNN layer with a fully connected Conditional Random Field (CRF), which is shown both qualitatively and quantitatively to improve localization performance. Our proposed "DeepLab" system sets the new state-of-art at the PASCAL VOC-2012 semantic image segmentation task, reaching 79.7% mIOU in the test set, and advances the results on three other datasets: PASCAL-Context, PASCAL-Person-Part, and Cityscapes. All of our code is made publicly available online.
Refined Composite Multiscale Dispersion Entropy and its Application to Biomedical Signals
Venue: arXiv cs.IT 2017
Year: 2017

Multiscale entropy (MSE) is a widely-used tool to analyze biomedical signals. It was proposed to overcome the deficiencies of conventional entropy methods when quantifying the complexity of time series. However, MSE is undefined for very short signals and slow for real-time applications because of the use of sample entropy (SampEn). To overcome these shortcomings, we introduce multiscale dispersion entropy (DisEn - MDE) as a very fast and powerful method to quantify the complexity of signals. MDE is based on our recently developed DisEn, which has a computation cost of O(N), compared with O(N2) for SampEn. We also propose the refined composite MDE (RCMDE) to improve the stability of MDE. We evaluate MDE, RCMDE, and refined composite MSE (RCMSE) on synthetic signals and find that these methods have similar behaviors but the MDE and RCMDE are significantly faster than MSE and RCMSE, respectively. The results also illustrate that RCMDE is more stable than MDE for short and noisy signals, which are common in biomedical applications. To evaluate the proposed methods on real signals, we employ three biomedical datasets, including focal and non-focal electroencephalograms (EEGs), blood pressure recordings in Fantasia database, and resting-state EEGs activity in Alzheimer's disease (AD). The results again demonstrate a similar behavior of RCMSE, MDE and RCMDE, although the RCMDE and MDE are significantly faster and lead to larger differences between physiological conditions known to alter the complexity of the physiological recordings. To sum up, MDE and RCMDE are expected to be useful for the analysis of physiological signals thanks to their ability to distinguish different types of dynamics.
Neural Net Models for Open-Domain Discourse Coherence
Venue: arXiv cs.CL 2017
Year: 2017

Discourse coherence is strongly associated with text quality, making it important to natural language generation and understanding. Yet existing models of coherence focus on measuring individual aspects of coherence (lexical overlap, rhetorical structure, entity centering) in narrow domains. In this paper, we describe domain-independent neural models of discourse coherence that are capable of measuring multiple aspects of coherence in existing sentences and can maintain coherence while generating new sentences. We study both discriminative models that learn to distinguish coherent from incoherent discourse, and generative models that produce coherent text, including a novel neural latent-variable Markovian generative model that captures the latent discourse dependencies between sentences in a text. Our work achieves state-of-the-art performance on multiple coherence evaluations, and marks an initial step in generating coherent texts given discourse contexts.
Proof of tightness of Varshamov - Gilbert bound for binary codes
Venue: arXiv cs.IT 2017
Year: 2017

We prove tightness of right logarithmic asymptotic of Varshamov- Gilbert bound for linear binary codes We find general asymptotic coding bound for linear codes
Using Game Theory to Study the Evolution of Cultural Norms
Venue: arXiv cs.CY 2017
Year: 2017

We discuss how to use evolutionary game theory (EGT) as a framework for studying how cultural dynamics and structural properties can influence the evolution of norms and behaviors within a society. We provide a brief tutorial on how EGT works, and discuss what kinds of insights it can provide. We then describe three published studies in which we have developed EGT models that help explain how structural and external conditions in a society affect the emergence of social norms.
Shortest Trajectories and Reversibility in Boolean Automata Networks
Venue: arXiv cs.DM 2017
Year: 2017

The question this research report explores is the following: when does a shortest trajectory between two configurations, or between one configuration and an attractor need to change several times the state of one automaton?
The Mythos of Model Interpretability
Venue: arXiv cs.LG 2017
Year: 2017

Supervised machine learning models boast remarkable predictive capabilities. But can you trust your model? Will it work in deployment? What else can it tell you about the world? We want models to be not only good, but interpretable. And yet the task of interpretation appears underspecified. Papers provide diverse and sometimes non-overlapping motivations for interpretability, and offer myriad notions of what attributes render models interpretable. Despite this ambiguity, many papers proclaim interpretability axiomatically, absent further explanation. In this paper, we seek to refine the discourse on interpretability. First, we examine the motivations underlying interest in interpretability, finding them to be diverse and occasionally discordant. Then, we address model properties and techniques thought to confer interpretability, identifying transparency to humans and post-hoc explanations as competing notions. Throughout, we discuss the feasibility and desirability of different notions, and question the oft-made assertions that linear models are interpretable and that deep neural networks are not.
On Matching and Thickness in Heterogeneous Dynamic Markets
Venue: arXiv cs.DS 2017
Year: 2017

We study dynamic matching in an infinite-horizon stochastic market. While all agents are potentially compatible with each other, some are hard-to-match and others are easy-to-match. Agents prefer to be matched as soon as possible and matches are formed either bilaterally or indirectly through chains. We adopt an asymptotic approach and compute tight bounds on the limit of waiting time of agents under myopic policies that differ in matching technology and prioritization. We find that the market composition is a key factor in the desired matching technology and prioritization level. When hard-to-match agents arrive less frequently than easy-to-match ones (i) bilateral matching is almost as efficient as chains (waiting times scale similarly under both, though chains always outperform bilateral matching by a constant factor), and (ii) assigning priorities to hard-to-match agents improves their waiting times. When hard-to-match agents arrive more frequently, chains are much more efficient than bilateral matching and prioritization has no impact. We further conduct comparative statics on arrival rates. Somewhat surprisingly, we find that in a heterogeneous market and under bilateral matching, increasing arrival rate has a non-monotone effect on waiting times, due to the fact that, under some market compositions, there is an adverse effect of competition. Our comparative statics shed light on the impact of merging markets and attracting altruistic agents (that initiate chains) or easy-to-match agents. This work uncovers fundamental differences between heterogeneous and homogeneous dynamic markets, and potentially helps policy makers to generate insights on the operations of matching markets such as kidney exchange programs.
Why Nominal-Typing Matters in OOP
Venue: arXiv cs.PL 2017
Year: 2017

The statements `inheritance is not subtyping' and `mainstream OO languages unnecessarily place restrictions over inheritance' have rippled as mantras through the PL research community for years. Many mainstream OO developers and OO language designers however do not accept these statements. In \emph{nominally-typed} OO languages that these developers and language designers are dearly familiar with, inheritance simply is subtyping; and they believe OO type inheritance is an inherently nominal notion not a structural one. Nominally-typed OO languages are among the most used programming languages today. However, the value of nominal typing to mainstream OO developers, as a means for designing robust OO software, seems to be in wait for full appreciation among PL researchers--thereby perpetuating an unnecessary schism between many OO developers and language designers and many OO PL researchers, with each side discounting, if not even disregarding, the views of the other. In this essay we strengthen earlier efforts to demonstrate the semantic value of nominal typing by presenting a technical comparison between nominal OO type systems and structural OO type systems. Recently, a domain-theoretic model of nominally-typed OOP was compared to well-known models of structurally-typed OOP. Combined, these comparisons provide a clear and deep account for the relation between nominal and structural OO type systems that has not been presented before, and they help demonstrate the key value of nominal typing and nominal subtyping to OO developers and language designers. We believe a clearer understanding of the key semantic advantage of pure nominal OO typing over pure structural OO typing can help remedy the existing schism. We believe future foundational OO PL research, to further its relevance to mainstream OOP, should be based less on structural models of OOP and more on nominal ones instead.
Randomized Ternary Search Tries
Venue: arXiv cs.DS 2017
Year: 2017

This paper presents a new kind of self-balancing ternary search trie that uses a randomized balancing strategy adapted from Aragon and Seidel's randomized binary search trees ("treaps"). After any sequence of insertions and deletions of strings, the tree looks like a ternary search trie built by inserting strings in random order. As a result, the time cost of searching, inserting, or deleting a string of length k in a tree with n strings is at most O(k + log n) with high probability.
Deep Learning with Darwin: Evolutionary Synthesis of Deep Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Taking inspiration from biological evolution, we explore the idea of "Can deep neural networks evolve naturally over successive generations into highly efficient deep neural networks?" by introducing the notion of synthesizing new highly efficient, yet powerful deep neural networks over successive generations via an evolutionary process from ancestor deep neural networks. The architectural traits of ancestor deep neural networks are encoded using synaptic probability models, which can be viewed as the `DNA' of these networks. New descendant networks with differing network architectures are synthesized based on these synaptic probability models from the ancestor networks and computational environmental factor models, in a random manner to mimic heredity, natural selection, and random mutation. These offspring networks are then trained into fully functional networks, like one would train a newborn, and have more efficient, more diverse network architectures than their ancestor networks, while achieving powerful modeling capabilities. Experimental results for the task of visual saliency demonstrated that the synthesized `evolved' offspring networks can achieve state-of-the-art performance while having network architectures that are significantly more efficient (with a staggering $\sim$48-fold decrease in synapses by the fourth generation) compared to the original ancestor network.
Decentralized Simultaneous Information and Energy Transmission in K-User Multiple Access Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, the fundamental limits of decentralized simultaneous information and energy transmission in the $K$-user Gaussian multiple access channel (G-MAC), with an arbitrary $K \geqslant 2$ and one non-colocated energy harvester (EH), are fully characterized. The objective of the transmitters is twofold. First, they aim to reliably communicate their message indices to the receiver; and second, to harvest energy at the EH at a rate not less than a minimum rate requirement $b$. The information rates $R_1,\dots,R_K$, in bits per channel use, are measured at the receiver and the energy rate $B$ is measured at an EH. Stability is considered in the sense of an $η$-Nash equilibrium ($η$-NE), with $η> 0$. The main result is a full characterization of the $η$-NE information-energy region, i.e., the set of information-energy rate tuples $(R_1,\dots,R_K,B)$ that are achievable and stable in the G-MAC when: $(a)$ all the transmitters autonomously and independently tune their own transmit configurations seeking to maximize their own information transmission rates $R_1,\dots, R_K$; and $(b)$ all the transmitters jointly guarantee an energy transmission rate $B$ at the EH, such that $B \geqslant b$. Therefore, any rate tuple outside the $η$-NE region is not stable as there always exists at least one transmitter able to increase by at least $η$ bits per channel use its own information transmission rate by updating its own transmit configuration.
Sequential geophysical and flow inversion to characterize fracture networks in subsurface systems
Venue: arXiv cs.CE 2017
Year: 2017

Subsurface applications including geothermal, geological carbon sequestration, oil and gas, etc., typically involve maximizing either the extraction of energy or the storage of fluids. Characterizing the subsurface is extremely complex due to heterogeneity and anisotropy. Due to this complexity, there are uncertainties in the subsurface parameters, which need to be estimated from multiple diverse as well as fragmented data streams. In this paper, we present a non-intrusive sequential inversion framework, for integrating data from geophysical and flow sources to constraint subsurface Discrete Fracture Networks (DFN). In this approach, we first estimate bounds on the statistics for the DFN fracture orientations using microseismic data. These bounds are estimated through a combination of a focal mechanism (physics-based approach) and clustering analysis (statistical approach) of seismic data. Then, the fracture lengths are constrained based on the flow data. The efficacy of this multi-physics based sequential inversion is demonstrated through a representative synthetic example.
Ego-Surfing: Person Localization in First-Person Videos Using Ego-Motion Signatures
Venue: arXiv cs.CV 2017
Year: 2017

We envision a future time when wearable cameras are worn by the masses and recording first-person point-of-view videos of everyday life. While these cameras can enable new assistive technologies and novel research challenges, they also raise serious privacy concerns. For example, first-person videos passively recorded by wearable cameras will necessarily include anyone who comes into the view of a camera -- with or without consent. Motivated by these benefits and risks, we developed a self-search technique tailored to first-person videos. The key observation of our work is that the egocentric head motion of a target person (ie, the self) is observed both in the point-of-view video of the target and observer. The motion correlation between the target person's video and the observer's video can then be used to identify instances of the self uniquely. We incorporate this feature into the proposed approach that computes the motion correlation over densely-sampled trajectories to search for a target individual in observer videos. Our approach significantly improves self-search performance over several well-known face detectors and recognizers. Furthermore, we show how our approach can enable several practical applications such as privacy filtering, target video retrieval, and social group clustering.
Fair Simulation for Nondeterministic and Probabilistic Buechi Automata: a Coalgebraic Perspective
Venue: arXiv cs.LO 2017
Year: 2017

Notions of simulation, among other uses, provide a computationally tractable and sound (but not necessarily complete) proof method for language inclusion. They have been comprehensively studied by Lynch and Vaandrager for nondeterministic and timed systems; for Büchi automata the notion of fair simulation has been introduced by Henzinger, Kupferman and Rajamani. We contribute to a generalization of fair simulation in two different directions: one for nondeterministic tree automata previously studied by Bomhard; and the other for probabilistic word automata with finite state spaces, both under the Büchi acceptance condition. The former nondeterministic definition is formulated in terms of systems of fixed-point equations, hence is readily translated to parity games and is then amenable to Jurdziński's algorithm; the latter probabilistic definition bears a strong ranking-function flavor. These two different-looking definitions are derived from one source, namely our coalgebraic modeling of Büchi automata. Based on these coalgebraic observations, we also prove their soundness: a simulation indeed witnesses language inclusion.
Network Densification in 5G: From the Short-Range Communications Perspective
Venue: arXiv cs.IT 2017
Year: 2017

Besides advanced telecommunications techniques, the most prominent evolution of wireless networks is the densification of network deployment. In particular, the increasing access points/users density and reduced cell size significantly enhance spatial reuse, thereby improving network capacity. Nevertheless, does network ultra-densification and over-deployment always boost the performance of wireless networks? Since the distance from transmitters to receivers is greatly reduced in dense networks, signal is more likely to be propagated from long- to short-range region. Without considering short-range propagation features, conventional understanding of the impact of network densification becomes doubtful. With this regard, it is imperative to reconsider the pros and cons brought by network densification. In this article, we first discuss the short-range propagation features in densely deployed network and verify through experimental results the validity of the proposed short-range propagation model. Considering short-range propagation, we further explore the fundamental impact of network densification on network capacity, aided by which a concrete interpretation of ultra-densification is presented from the network capacity perspective. Meanwhile, as short-range propagation makes interference more complicated and difficult to handle, we discuss possible approaches to further enhance network capacity in ultra-dense wireless networks. Moreover, key challenges are presented to suggest future directions.
Improving Variational Inference with Inverse Autoregressive Flow
Venue: arXiv cs.LG 2017
Year: 2017

The framework of normalizing flows provides a general strategy for flexible variational inference of posteriors over latent variables. We propose a new type of normalizing flow, inverse autoregressive flow (IAF), that, in contrast to earlier published flows, scales well to high-dimensional latent spaces. The proposed flow consists of a chain of invertible transformations, where each transformation is based on an autoregressive neural network. In experiments, we show that IAF significantly improves upon diagonal Gaussian approximate posteriors. In addition, we demonstrate that a novel type of variational autoencoder, coupled with IAF, is competitive with neural autoregressive models in terms of attained log-likelihood on natural images, while allowing significantly faster synthesis.