OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of Coupled Scalar Systems by Displacement Convexity
Venue: arXiv cs.IT 2017
Year: 2017

Potential functionals have been introduced recently as an important tool for the analysis of coupled scalar systems (e.g. density evolution equations). In this contribution, we investigate interesting properties of this potential. Using the tool of displacement convexity, we show that, under mild assumptions on the system, the potential functional is displacement convex. Furthermore, we give the conditions on the system such that the potential is strictly displacement convex, in which case the minimizer is unique.
Complexity of regular bifix-free languages
Venue: arXiv cs.FL 2017
Year: 2017

We study descriptive complexity properties of the class of regular bifix-free languages, which is the intersection of prefix-free and suffix-free regular languages. We show that there exist a single ternary universal (stream of) bifix-free languages that meet all the bounds for the state complexity basic operations (Boolean operations, product, star, and reversal). This is in contrast with suffix-free languages, where it is known that there does not exist such a stream. Then we present a stream of bifix-free languages that is most complex in terms of all basic operations, syntactic complexity, and the number of atoms and their complexities, which requires a superexponential alphabet. We also complete the previous results by characterizing state complexity of product, star, and reversal, and establishing tight upper bounds for atom complexities of bifix-free languages. We show that to meet the bound for reversal we require at least 3 letters and to meet the bound for atom complexities $n+1$ letters are sufficient and necessary. For the cases of product, star, and reversal we show that there are no gaps (magic numbers) in the interval of possible state complexities of the languages resulted from an operation; in particular, the state complexity of the product $L_m L_n$ is always $m+n-2$, while of the star is either $n-1$ or $n-2$.
Delay-Optimal Scheduling for Queueing Systems with Switching Overhead
Venue: arXiv cs.PF 2017
Year: 2017

We study the scheduling polices for asymptotically optimal delay in queueing systems with switching overhead. Such systems consist of a single server that serves multiple queues, and some capacity is lost whenever the server switches to serve a different set of queues. The capacity loss due to this switching overhead can be significant in many emerging applications, and needs to be explicitly addressed in the design of scheduling policies. For example, in 60GHz wireless networks with directional antennas, base stations need to train and reconfigure their beam patterns whenever they switch from one client to another. Considerable switching overhead can also be observed in many other queueing systems such as transportation networks and manufacturing systems. While the celebrated Max-Weight policy achieves asymptotically optimal average delay for systems without switching overhead, it fails to preserve throughput-optimality, let alone delay-optimality, when switching overhead is taken into account. We propose a class of Biased Max-Weight scheduling policies that explicitly takes switching overhead into account. The Biased Max-Weight policy can use either queue length or head-of-line waiting time as an indicator of the system status. We prove that our policies not only are throughput-optimal, but also can be made arbitrarily close to the asymptotic lower bound on average delay. To validate the performance of the proposed policies, we provide extensive simulation with various system topologies and different traffic patterns. We show that the proposed policies indeed achieve much better delay performance than that of the state-of-the-art policy.
PRSP: A Plugin-based Framework for RDF Stream Processing
Venue: arXiv cs.DB 2017
Year: 2017

In this paper, we propose a plugin-based framework for RDF stream processing named PRSP. Within this framework, we can employ SPARQL query engines to process C-SPARQL queries with maintaining the high performance of those engines in a simple way. Taking advantage of PRSP, we can process large-scale RDF streams in a distributed context via distributed SPARQL engines. Besides, we can evaluate the performance and correctness of existing SPARQL query engines in handling RDF streams in a united way, which amends the evaluation of them ranging from static RDF (i.e., RDF graph) to dynamic RDF (i.e., RDF stream). Finally, within PRSP, we experimently evaluate the correctness and the performance on YABench. The experiments show that PRSP can still maintain the high performance of those engines in RDF stream processing although there are some slight differences among them.
A General Sequential Delay-Doppler Estimation Scheme for Sub-Nyquist Pulse-Doppler Radar
Venue: arXiv cs.IT 2017
Year: 2017

Sequential estimation of the delay and Doppler parameters for sub-Nyquist radars by analog-to-information conversion (AIC) systems has received wide attention recently. However, the estimation methods reported are AIC-dependent and have poor performance for off-grid targets. This paper develops a general estimation scheme in the sense that it is applicable to all AICs regardless whether the targets are on or off the grids. The proposed scheme estimates the delay and Doppler parameters sequentially, in which the delay estimation is formulated into a beamspace direction-of- arrival problem and the Doppler estimation is translated into a line spectrum estimation problem. Then the well-known spatial and temporal spectrum estimation techniques are used to provide efficient and high-resolution estimates of the delay and Doppler parameters. In addition, sufficient conditions on the AIC to guarantee the successful estimation of off-grid targets are provided, while the existing conditions are mostly related to the on-grid targets. Theoretical analyses and numerical experiments show the effectiveness and the correctness of the proposed scheme.
An Arrow-Hurwicz-Uzawa Type Flow as Least Squares Solver for Network Linear Equations
Venue: arXiv cs.SY 2017
Year: 2017

We study the approach to obtaining least squares solutions to systems of linear algebraic equations over networks by using distributed algorithms. Each node has access to one of the linear equations and holds a dynamic state. The aim for the node states is to reach a consensus as a least squares solution of the linear equations by exchanging their states with neighbors over an underlying interaction graph. A continuous-time distributed least squares solver over networks is developed in the form of the famous Arrow-Hurwicz-Uzawa flow. A necessary and sufficient condition is established on the graph Laplacian for the continuous-time distributed algorithm to give the least squares solution in the limit, with an exponentially fast convergence rate. The feasibility of different fundamental graphs is discussed including path graph, star graph, etc. Moreover, a discrete-time distributed algorithm is developed by Euler's method, converging exponentially to the least squares solution at the node states with suitable step size and graph conditions. The exponential convergence rate for both the continuous-time and discrete-time algorithms under the established conditions is confirmed by numerical examples. Finally, we investigate the performance of the proposed flow under switching networks, and surprisingly, switching networks at high switching frequencies can lead to approximate least square solvers even if all graphs in the switching signal fail to do so in the absence of structure switching.
Securing the Assets of Decentralized Applications using Financial Derivatives (DRAFT)
Venue: arXiv cs.CR 2017
Year: 2017

Ethereum contracts can be designed to function as fully decentralized applications called DAPPs. Many DAPPs have already been fielded, including an online marketplace, a role playing game, a prediction market, and an Internet service provider. Unfortunately, DAPPs can be hacked, and the assets they control can be stolen. A recent attack on an Ethereum decentralized application called The DAO demonstrated that smart contract bugs are more than an academic concern. Ether worth tens of millions of US dollars was extracted by an attacker from The DAO, sending the value of its tokens and the overall exchange price of ether tumbling. We present a market-based technique for insuring the ether holdings of a DAPP using futures contracts indexed by the trade price of ether for DAPP tokens. Under fairly general circumstances, our technique is capable of recovering the majority of ether lost from theft with high probability even when all of the ether holdings are stolen; and the only cost to DAPP token holders is an adjustable ether withdrawal fee. If the probability of a margin call in $d$ days is $p$ for a futures contract with 20 times leverage, then our approach will allow for the recovery of half the stolen ether with probability $p$ and a withdrawal fee of 5%. A higher withdrawal fee of 25% allows for more than 80% of the ether to be recovered with probability $p$.
Balancing Novelty and Salience: Adaptive Learning to Rank Entities for Timeline Summarization of High-impact Events
Venue: arXiv cs.IR 2017
Year: 2017

Long-running, high-impact events such as the Boston Marathon bombing often develop through many stages and involve a large number of entities in their unfolding. Timeline summarization of an event by key sentences eases story digestion, but does not distinguish between what a user remembers and what she might want to re-check. In this work, we present a novel approach for timeline summarization of high-impact events, which uses entities instead of sentences for summarizing the event at each individual point in time. Such entity summaries can serve as both (1) important memory cues in a retrospective event consideration and (2) pointers for personalized event exploration. In order to automatically create such summaries, it is crucial to identify the "right" entities for inclusion. We propose to learn a ranking function for entities, with a dynamically adapted trade-off between the in-document salience of entities and the informativeness of entities across documents, i.e., the level of new information associated with an entity for a time point under consideration. Furthermore, for capturing collective attention for an entity we use an innovative soft labeling approach based on Wikipedia. Our experiments on a real large news datasets confirm the effectiveness of the proposed methods.
Multiple Access Wiretap Channel with Noiseless Feedback
Venue: arXiv cs.IT 2017
Year: 2017

The physical layer security in the up-link of the wireless communication systems is often modeled as the multiple access wiretap channel (MAC-WT), and recently it has received a lot attention. In this paper, the MAC-WT has been re-visited by considering the situation that the legitimate receiver feeds his received channel output back to the transmitters via two noiseless channels, respectively. This model is called the MAC-WT with noiseless feedback. Inner and outer bounds on the secrecy capacity region of this feedback model are provided. To be specific, we first present a decode-and-forward (DF) inner bound on the secrecy capacity region of this feedback model, and this bound is constructed by allowing each transmitter to decode the other one's transmitted message from the feedback, and then each transmitter uses the decoded message to re-encode his own messages, i.e., this DF inner bound allows the independent transmitters to co-operate with each other. Then, we provide a hybrid inner bound which is strictly larger than the DF inner bound, and it is constructed by using the feedback as a tool not only to allow the independent transmitters to co-operate with each other, but also to generate two secret keys respectively shared between the legitimate receiver and the two transmitters. Finally, we give a sato-type outer bound on the secrecy capacity region of this feedback model. The results of this paper are further explained via a Gaussian example.
Agent-Agnostic Human-in-the-Loop Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

Providing Reinforcement Learning agents with expert advice can dramatically improve various aspects of learning. Prior work has developed teaching protocols that enable agents to learn efficiently in complex environments; many of these methods tailor the teacher's guidance to agents with a particular representation or underlying learning scheme, offering effective but specialized teaching procedures. In this work, we explore protocol programs, an agent-agnostic schema for Human-in-the-Loop Reinforcement Learning. Our goal is to incorporate the beneficial properties of a human teacher into Reinforcement Learning without making strong assumptions about the inner workings of the agent. We show how to represent existing approaches such as action pruning, reward shaping, and training in simulation as special cases of our schema and conduct preliminary experiments on simple domains.
Near Optimal Behavior via Approximate State Abstraction
Venue: arXiv cs.LG 2017
Year: 2017

The combinatorial explosion that plagues planning and reinforcement learning (RL) algorithms can be moderated using state abstraction. Prohibitively large task representations can be condensed such that essential information is preserved, and consequently, solutions are tractably computable. However, exact abstractions, which treat only fully-identical situations as equivalent, fail to present opportunities for abstraction in environments where no two situations are exactly alike. In this work, we investigate approximate state abstractions, which treat nearly-identical situations as equivalent. We present theoretical guarantees of the quality of behaviors derived from four types of approximate abstractions. Additionally, we empirically demonstrate that approximate abstractions lead to reduction in task complexity and bounded loss of optimality of behavior in a variety of environments.
Understanding the Effective Receptive Field in Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

We study characteristics of receptive fields of units in deep convolutional networks. The receptive field size is a crucial issue in many visual tasks, as the output must respond to large enough areas in the image to capture information about large objects. We introduce the notion of an effective receptive field, and show that it both has a Gaussian distribution and only occupies a fraction of the full theoretical receptive field. We analyze the effective receptive field in several architecture designs, and the effect of nonlinear activations, dropout, sub-sampling and skip connections on it. This leads to suggestions for ways to address its tendency to be too small.
Deep Memory Networks for Attitude Identification
Venue: arXiv cs.CL 2017
Year: 2017

We consider the task of identifying attitudes towards a given set of entities from text. Conventionally, this task is decomposed into two separate subtasks: target detection that identifies whether each entity is mentioned in the text, either explicitly or implicitly, and polarity classification that classifies the exact sentiment towards an identified entity (the target) into positive, negative, or neutral. Instead, we show that attitude identification can be solved with an end-to-end machine learning architecture, in which the two subtasks are interleaved by a deep memory network. In this way, signals produced in target detection provide clues for polarity classification, and reversely, the predicted polarity provides feedback to the identification of targets. Moreover, the treatments for the set of targets also influence each other -- the learned representations may share the same semantics for some targets but vary for others. The proposed deep memory network, the AttNet, outperforms methods that do not consider the interactions between the subtasks or those among the targets, including conventional machine learning methods and the state-of-the-art deep learning models.
The Quantified City: Sensing Dynamics in Urban Setting
Venue: arXiv cs.SI 2017
Year: 2017

The world is witnessing a period of extreme growth and urbanization; cities in the 21st century became nerve centers creating economic opportunities and cultural values which make cities grow exponentially. With this rapid urban population growth, city infrastructure is facing major problems, from the need to scale urban systems to sustaining the quality of services for citizen at scale. Understanding the dynamics of cities is critical towards informed strategic urban planning. This paper showcases QuantifiedCity, a system aimed at understanding the complex dynamics taking place in cities. Often, these dynamics involve humans, services, and infrastructures and are observed in different spaces: physical (IoT-based) sensing and human (social-based) sensing. The main challenges the system strives to address are related to data integration and fusion to enable an effective and semantically relevant data grouping. This is achieved by considering the spatio-temporal space as a blocking function for any data generated in the city. Our system consists of three layer for data acquisition, data analysis, and data visualization; each of which embeds a variety of modules to better achieve its purpose (e.g., data crawling, data cleaning, topic modeling, sentiment analysis, named entity recognition, event detection, time series analysis, etc.) End users can browse the dynamics through three main dimensions: location, time, and event. For each dimension, the system renders a set of map-centric widgets that summarize the underlying related dynamics. This paper highlights the need for such a holistic platform, identifies the strengths of the "Quantified City" concept, and showcases a working demo through a real-life scenario.
Leveraging SDN to Monitor Critical Infrastricture Networks in a Smarter Way
Venue: arXiv cs.NI 2017
Year: 2017

In critical infrastructures, communication networks are used to exchange vital data among elements of Industrial Control Systems (ICSes). Due to the criticality of such systems and the increase of the cybersecurity risks in these contexts, best practices recommend the adoption of Intrusion Detection Systems (IDSes) as monitoring facilities. The choice of the positions of IDSes is crucial to monitor as many streams of data traffic as possible. This is especially true for the traffic patterns of ICS networks, mostly confined in many subnetworks, which are geographically distributed and largely autonomous. We introduce a methodology and a software architecture that allow an ICS operator to use the spare bandwidth that might be available in over-provisioned networks to forward replicas of traffic streams towards a single IDS placed at an arbitrary location. We leverage certain characteristics of ICS networks, like stability of topology and bandwidth needs predictability, and make use of the Software-Defined Networking (SDN) paradigm. We fulfill strict requirements about packet loss, for both functional and security aspects. Finally, we evaluate our approach on network topologies derived from real networks.
Classification of MRI data using Deep Learning and Gaussian Process-based Model Selection
Venue: arXiv cs.LG 2017
Year: 2017

The classification of MRI images according to the anatomical field of view is a necessary task to solve when faced with the increasing quantity of medical images. In parallel, advances in deep learning makes it a suitable tool for computer vision problems. Using a common architecture (such as AlexNet) provides quite good results, but not sufficient for clinical use. Improving the model is not an easy task, due to the large number of hyper-parameters governing both the architecture and the training of the network, and to the limited understanding of their relevance. Since an exhaustive search is not tractable, we propose to optimize the network first by random search, and then by an adaptive search based on Gaussian Processes and Probability of Improvement. Applying this method on a large and varied MRI dataset, we show a substantial improvement between the baseline network and the final one (up to 20\% for the most difficult classes).
On the Achievable Secrecy Diversity of Cooperative Networks with Untrusted Relays
Venue: arXiv cs.CR 2017
Year: 2017

Cooperative relaying is often deployed to enhance the communication reliability (i.e., diversity order) and consequently the end-to-end achievable rate. However, this raises several security concerns when the relays are untrusted since they may have access to the relayed message. In this paper, we study the achievable secrecy diversity order of cooperative networks with untrusted relays. In particular, we consider a network with an N-antenna transmitter (Alice), K single-antenna relays, and a single-antenna destination (Bob). We consider the general scenario where there is no relation between N and K, and therefore K can be larger than N. Alice and Bob are assumed to be far away from each other, and all communication is done through the relays, i.e., there is no direct link. Providing secure communication while enhancing the diversity order has been shown to be very challenging. In fact, it has been shown in the literature that the maximum achievable secrecy diversity order for the adopted system model is one (while using artificial noise jamming). In this paper, we adopt a nonlinear interference alignment scheme that we have proposed recently to transmit the signals from Alice to Bob. We analyze the proposed scheme in terms of the achievable secrecy rate and secrecy diversity order. Assuming Gaussian inputs, we derive an explicit expression for the achievable secrecy rate and show analytically that a secrecy diversity order of up to min(N,K)-1 can be achieved using the proposed technique. We provide several numerical examples to validate the obtained analytical results and demonstrate the superiority of the proposed technique to its counterparts that exist in the literature.
NIC-Planar Graphs
Venue: arXiv cs.DM 2017
Year: 2017

A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. NIC-planarity generalizes IC-planarity, which allows a vertex to be incident to at most one crossing edge, and specializes 1-planarity, which only requires at most one crossing per edge. We characterize embeddings of maximal NIC-planar graphs in terms of generalized planar dual graphs. The characterization is used to derive tight bounds on the density of maximal NIC-planar graphs which ranges between 3.2(n-2) and 3.6(n-2). Further, we prove that optimal NIC-planar graphs with 3.6(n-2) edges have a unique embedding and can be recognized in linear time, whereas the general recognition problem of NIC-planar graphs is NP-complete. In addition, we show that there are NIC-planar graphs that do not admit right angle crossing drawings, which distinguishes NIC-planar from IC-planar graphs.