OpenRaiser/Intern-Atlas huggingface dataset:
Defect tolerance: fundamental limits and examples
Venue: arXiv cs.IT 2017
Year: 2017

This paper addresses the problem of adding redundancy to a collection of physical objects so that the overall system is more robust to failures. In contrast to its information counterpart, which can exploit parity to protect multiple information symbols from a single erasure, physical redundancy can only be realized through duplication and substitution of objects. We propose a bipartite graph model for designing defect-tolerant systems in which defective objects are replaced by judiciously connected redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size systems that approach these limits are constructed. Among other results, we show that simple modular redundancy is in general suboptimal. As we develop, this combinatorial problem of defect tolerant system design has a natural interpretation as one of graph coloring, and the analysis is significantly different from that traditionally used in information redundancy for error-control codes.
Notions of Anonymous Existence in Martin-Löf Type Theory
Venue: arXiv cs.LO 2017
Year: 2017

As the groupoid model of Hofmann and Streicher proves, identity proofs in intensional Martin-Löf type theory cannot generally be shown to be unique. Inspired by a theorem by Hedberg, we give some simple characterizations of types that do have unique identity proofs. A key ingredient in these constructions are weakly constant endofunctions on identity types. We study such endofunctions on arbitrary types and show that they always factor through a propositional type, the truncated or squashed domain. Such a factorization is impossible for weakly constant functions in general (a result by Shulman), but we present several non-trivial cases in which it can be done. Based on these results, we define a new notion of anonymous existence in type theory and compare different forms of existence carefully. In addition, we show possibly surprising consequences of the judgmental computation rule of the truncation, in particular in the context of homotopy type theory. All the results have been formalized and verified in the dependently typed programming language Agda.
Kek, Cucks, and God Emperor Trump: A Measurement Study of 4chan's Politically Incorrect Forum and Its Effects on the Web
Venue: arXiv cs.SI 2017
Year: 2017

The discussion-board site 4chan has been part of the Internet's dark underbelly since its inception, and recent political events have put it increasingly in the spotlight. In particular, /pol/, the "Politically Incorrect" board, has been a central figure in the outlandish 2016 US election season, as it has often been linked to the alt-right movement and its rhetoric of hate and racism. However, 4chan remains relatively unstudied by the scientific community: little is known about its user base, the content it generates, and how it affects other parts of the Web. In this paper, we start addressing this gap by analyzing /pol/ along several axes, using a dataset of over 8M posts we collected over two and a half months. First, we perform a general characterization, showing that /pol/ users are well distributed around the world and that 4chan's unique features encourage fresh discussions. We also analyze content, finding, for instance, that YouTube links and hate speech are predominant on /pol/. Overall, our analysis not only provides the first measurement study of /pol/, but also insight into online harassment and hate speech trends in social media.
Enhancing Secrecy with Multi-Antenna Transmission in Millimeter Wave Vehicular Communication Systems
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter wave (mmWave) vehicular communication systems will provide an abundance of bandwidth for the exchange of raw sensor data and support driver-assisted and safety-related functionalities. Lack of secure communication links, however, may lead to abuses and attacks that jeopardize the efficiency of transportation systems and the physical safety of drivers. In this paper, we propose two physical layer (PHY) security techniques for vehicular mmWave communication systems. The first technique uses multiple antennas with a single RF chain to transmit information symbols to a target receiver and noise-like signals in non-receiver directions. The second technique uses multiple antennas with a few RF chains to transmit information symbols to a target receiver and opportunistically inject artificial noise in controlled directions, thereby reducing interference in vehicular environments. Theoretical and numerical results show that the proposed techniques provide higher secrecy rate when compared to traditional PHY security techniques that require digital or more complex antenna architectures.
Cooperative Strategies for Wireless-Powered Communications: An Overview
Venue: arXiv cs.IT 2017
Year: 2017

Radio frequency (RF) energy transfer and harvesting has been intensively studied recently as a promising approach to significantly extend the lifetime of energy-constrained wireless networks. This technique has a great potential to provide relatively stable and continuous RF energy to devices wirelessly; it thus opened a new research paradigm, termed wireless-powered communication (WPC), which has raised many new research opportunities with wide applications. Among these, the design and analysis of cooperative schemes towards efficient WPC have attracted tremendous research interests nowadays. This article provides an overview of various cooperative strategies for WPC, with particular emphasis on relaying protocols for wireless-powered cooperative communications, cooperative spectrum sharing schemes for cognitive wireless-powered networks, and cooperative jamming strategies towards wireless-powered secure communications. We also identify several interesting research directions in this area before concluding this article.
An Inter-Node Interference Suppression Approach in Full-Duplex Wireless Communications
Venue: arXiv cs.IT 2017
Year: 2017

Considering that a full-duplex network is comprised of a full-duplex (FD) base station (BS) and two half-duplex (HD) users, one user transmits on the uplink channel and the other receives through the downlink channel on the same frequency. The uplink user will generate inter-user interference (IUI) on the downlink user through the interference channel. In this paper, we propose a novel IUI suppression approach when the BS knows the full channel station information. The main idea of the approach is to retransmit the weighted uplink signal as soon as it has been received at the BS. For the narrowband case, we first derive the closed-form expression of the optimum weighted coefficient when the SI is perfectly cancelled at the BS and then analyze the performance of the proposed IUI suppression approach in practical considerations. Furthermore, the proposed IUI suppression approach can be extended to the broadband case using a time-domain weighted filter. Simulation results shows the advantage over existing IUI suppression schemes.
Question Generation from a Knowledge Base with Web Exploration
Venue: arXiv cs.CL 2017
Year: 2017

Question generation from a knowledge base (KB) is the task of generating questions related to the domain of the input KB. We propose a system for generating fluent and natural questions from a KB, which significantly reduces the human effort by leveraging massive web resources. In more detail, a seed question set is first generated by applying a small number of hand-crafted templates on the input KB, then more questions are retrieved by iteratively forming already obtained questions as search queries into a standard search engine, before finally questions are selected by estimating their fluency and domain relevance. Evaluated by human graders on 500 random-selected triples from Freebase, questions generated by our system are judged to be more fluent than those of \newcite{serban-EtAl:2016:P16-1} by human graders.
A fuzzy expert system for earthquake prediction, case study: the Zagros range
Venue: arXiv cs.AI 2017
Year: 2017

A methodology for the development of a fuzzy expert system (FES) with application to earthquake prediction is presented. The idea is to reproduce the performance of a human expert in earthquake prediction. To do this, at the first step, rules provided by the human expert are used to generate a fuzzy rule base. These rules are then fed into an inference engine to produce a fuzzy inference system (FIS) and to infer the results. In this paper, we have used a Sugeno type fuzzy inference system to build the FES. At the next step, the adaptive network-based fuzzy inference system (ANFIS) is used to refine the FES parameters and improve its performance. The proposed framework is then employed to attain the performance of a human expert used to predict earthquakes in the Zagros area based on the idea of coupled earthquakes. While the prediction results are promising in parts of the testing set, the general performance indicates that prediction methodology based on coupled earthquakes needs more investigation and more complicated reasoning procedure to yield satisfactory predictions.
A guiding vector field algorithm for path following control of nonholonomic mobile robots
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we propose an algorithm for path following control of the nonholonomic mobile robot based on the idea of the guiding vector field (GVF). The desired path may be an arbitrary smooth curve in its implicit form, that is, a level set of a predefined smooth function. Using this function and the robot's kinematic model, we design a GVF, whose integral curves converge to the trajectory. A nonlinear motion controller is then proposed which steers the robot along such an integral curve, bringing it to the desired path. We establish global convergence conditions for our algorithm and demonstrate its applicability and performance by experiments with real wheeled robots.
Sound and Automated Synthesis of Digital Stabilizing Controllers for Continuous Plants
Venue: arXiv cs.SY 2017
Year: 2017

Modern control is implemented with digital microcontrollers, embedded within a dynamical plant that represents physical components. We present a new algorithm based on counter-example guided inductive synthesis that automates the design of digital controllers that are correct by construction. The synthesis result is sound with respect to the complete range of approximations, including time discretization, quantization effects, and finite-precision arithmetic and its rounding errors. We have implemented our new algorithm in a tool called DSSynth, and are able to automatically generate stable controllers for a set of intricate plant models taken from the literature within minutes.
Reachability Analysis of Innermost Rewriting
Venue: arXiv cs.LO 2017
Year: 2017

We consider the problem of inferring a grammar describing the output of a functional program given a grammar describing its input. Solutions to this problem are helpful for detecting bugs or proving safety properties of functional programs, and several rewriting tools exist for solving this problem. However, known grammar inference techniques are not able to take evaluation strategies of the program into account. This yields very imprecise results when the evaluation strategy matters. In this work, we adapt the Tree Automata Completion algorithm to approximate accurately the set of terms reachable by rewriting under the innermost strategy. We formally prove that the proposed technique is sound and precise w.r.t. innermost rewriting. We show that those results can be extended to the leftmost and rightmost innermost case. The algorithms for the general innermost case have been implemented in the Timbuk reachability tool. Experiments show that it noticeably improves the accuracy of static analysis for functional programs using the call-by-value evaluation strategy.
Decentralized Collaborative Learning of Personalized Models over Networks
Venue: arXiv cs.LG 2017
Year: 2017

We consider a set of learning agents in a collaborative peer-to-peer network, where each agent learns a personalized model according to its own learning objective. The question addressed in this paper is: how can agents improve upon their locally trained model by communicating with other agents that have similar objectives? We introduce and analyze two asynchronous gossip algorithms running in a fully decentralized manner. Our first approach, inspired from label propagation, aims to smooth pre-trained local models over the network while accounting for the confidence that each agent has in its initial model. In our second approach, agents jointly learn and propagate their model by making iterative updates based on both their local dataset and the behavior of their neighbors. To optimize this challenging objective, our decentralized algorithm is based on ADMM.
Conic Quadratic Formulations for Wireless Communications Design
Venue: arXiv cs.IT 2017
Year: 2017

As a wide class of resource management problems in wireless communications are nonconvex and even NP-hard in many cases, finding globally optimal solutions to these problems is of little practical interest. Towards more pragmatic approaches, there is a rich literature on iterative methods aiming at finding a solution satisfying necessary optimality conditions to these problems. These approaches have been derived under several similar mathematical frameworks such as inner approximation algorithm, concave-convex procedure, majorization-minimization algorithm, and successive convex approximation (SCA). However, a large portion of existing algorithms arrive at a relatively generic program at each iteration, which is less computationally efficient compared to a more standard convex formulation. This paper proposes \emph{numerically efficient} transformations and approximations for SCA-based methods to deal with nonconvexity in wireless communications design. More specifically, the central goal is to show that various nonconvex problems in wireless communications can be iteratively solved by conic quadratic optimization. We revisit various examples to demonstrate the advantages of the proposed approximations. Theoretical complexity analysis and numerical results show the superior efficiency in terms of computational cost of our proposed solutions compared to the existing ones.
Acoustic Reflector Localization: Novel Image Source Reversion and Direct Localization Methods
Venue: arXiv cs.SD 2017
Year: 2017

Acoustic reflector localization is an important issue in audio signal processing, with direct applications in spatial audio, scene reconstruction, and source separation. Several methods have recently been proposed to estimate the 3D positions of acoustic reflectors given room impulse responses (RIRs). In this article, we categorize these methods as "image-source reversion", which localizes the image source before finding the reflector position, and "direct localization", which localizes the reflector without intermediate steps. We present five new contributions. First, an onset detector, called the clustered dynamic programming projected phase-slope algorithm, is proposed to automatically extract the time of arrival for early reflections within the RIRs of a compact microphone array. Second, we propose an image-source reversion method that uses the RIRs from a single loudspeaker. It is constructed by combining an image source locator (the image source direction and range (ISDAR) algorithm), and a reflector locator (using the loudspeaker-image bisection (LIB) algorithm). Third, two variants of it, exploiting multiple loudspeakers, are proposed. Fourth, we present a direct localization method, the ellipsoid tangent sample consensus (ETSAC), exploiting ellipsoid properties to localize the reflector. Finally, systematic experiments on simulated and measured RIRs are presented, comparing the proposed methods with the state-of-the-art. ETSAC generates errors lower than the alternative methods compared through our datasets. Nevertheless, the ISDAR-LIB combination performs well and has a run time 200 times faster than ETSAC.
Stylometric Analysis of Early Modern Period English Plays
Venue: arXiv cs.CL 2017
Year: 2017

Function word adjacency networks (WANs) are used to study the authorship of plays from the Early Modern English period. In these networks, nodes are function words and directed edges between two nodes represent the relative frequency of directed co-appearance of the two words. For every analyzed play, a WAN is constructed and these are aggregated to generate author profile networks. We first study the similarity of writing styles between Early English playwrights by comparing the profile WANs. The accuracy of using WANs for authorship attribution is then demonstrated by attributing known plays among six popular playwrights. Moreover, the WAN method is shown to outperform other frequency-based methods on attributing Early English plays. In addition, WANs are shown to be reliable classifiers even when attributing collaborative plays. For several plays of disputed co-authorship, a deeper analysis is performed by attributing every act and scene separately, in which we both corroborate existing breakdowns and provide evidence of new assignments.
Lensless Imaging with Compressive Ultrafast Sensing
Venue: arXiv cs.CV 2017
Year: 2017

Lensless imaging is an important and challenging problem. One notable solution to lensless imaging is a single pixel camera which benefits from ideas central to compressive sampling. However, traditional single pixel cameras require many illumination patterns which result in a long acquisition process. Here we present a method for lensless imaging based on compressive ultrafast sensing. Each sensor acquisition is encoded with a different illumination pattern and produces a time series where time is a function of the photon's origin in the scene. Currently available hardware with picosecond time resolution enables time tagging photons as they arrive to an omnidirectional sensor. This allows lensless imaging with significantly fewer patterns compared to regular single pixel imaging. To that end, we develop a framework for designing lensless imaging systems that use ultrafast detectors. We provide an algorithm for ideal sensor placement and an algorithm for optimized active illumination patterns. We show that efficient lensless imaging is possible with ultrafast measurement and compressive sensing. This paves the way for novel imaging architectures and remote sensing in extreme situations where imaging with a lens is not possible.
On Sessions and Infinite Data
Venue: arXiv cs.LO 2017
Year: 2017

We define a novel calculus that combines a call-by-name functional core with session-based communication primitives. We develop a typing discipline that guarantees both normalisation of expressions and progress of processes and that uncovers an unexpected interplay between evaluation and communication.
ODIN: Obfuscation-based privacy preserving consensus algorithm for Decentralized Information fusion in smart device Networks
Venue: arXiv cs.CR 2017
Year: 2017

The large spread of sensors and smart devices in urban infrastructures are motivating research in the area of Internet of Thing (IoT), to develop new services and improve citizens' quality of life. Sensors and smart devices generate large amount of measurement data from sensing the environment, which is used to enable services, such as control power consumption or traffic density. To deal with such a large amount of information, and provide accurate measurements, service providers can adopt information fusion, which, given the decentralized nature of urban deployments, can be performed by means of consensus algorithms. These algorithms allow distributed agents to (iteratively) compute linear functions on the exchanged data, and take decisions based on the outcome, without the need for the support of a central entity. However, the use of consensus algorithms raises several security concerns, especially when private or security critical information are involved in the computation. This paper proposes ODIN, a novel algorithm that allows information fusion over encrypted data. ODIN is a privacy-preserving extension of the popular consensus gossip algorithm, that prevents distributed agents have direct access to the data while they iteratively reach consensus; agents cannot access even the final consensus value, but can only retrieve partial information, e.g., a binary decision. ODIN uses efficient additive obfuscation and proxy re-encryption during the update steps, and Garbled Circuits to take final decisions on the obfuscated consensus. We discuss the security of our proposal, and show its practicability and efficiency on real-world resource constrained devices, developing a prototype implementation for Raspberry Pi devices.
Deep image mining for diabetic retinopathy screening
Venue: arXiv cs.CV 2017
Year: 2017

Deep learning is quickly becoming the leading methodology for medical image analysis. Given a large medical archive, where each image is associated with a diagnosis, efficient pathology detectors or classifiers can be trained with virtually no expert knowledge about the target pathologies. However, deep learning algorithms, including the popular ConvNets, are black boxes: little is known about the local patterns analyzed by ConvNets to make a decision at the image level. A solution is proposed in this paper to create heatmaps showing which pixels in images play a role in the image-level predictions. In other words, a ConvNet trained for image-level classification can be used to detect lesions as well. A generalization of the backpropagation method is proposed in order to train ConvNets that produce high-quality heatmaps. The proposed solution is applied to diabetic retinopathy (DR) screening in a dataset of almost 90,000 fundus photographs from the 2015 Kaggle Diabetic Retinopathy competition and a private dataset of almost 110,000 photographs (e-ophtha). For the task of detecting referable DR, very good detection performance was achieved: $A_z = 0.954$ in Kaggle's dataset and $A_z = 0.949$ in e-ophtha. Performance was also evaluated at the image level and at the lesion level in the DiaretDB1 dataset, where four types of lesions are manually segmented: microaneurysms, hemorrhages, exudates and cotton-wool spots. The proposed detector outperforms recent algorithms trained to detect those lesions specifically, as well as competing heatmap generation algorithms for ConvNets. This detector is part of the Messidor system for mobile eye pathology screening. Because it does not rely on expert knowledge or manual segmentation for detecting relevant patterns, the proposed solution is a promising image mining tool, which has the potential to discover new biomarkers in images.
A Language-theoretic View on Network Protocols
Venue: arXiv cs.FL 2017
Year: 2017

Input validation is the first line of defense against malformed or malicious inputs. It is therefore critical that the validator (which is often part of the parser) is free of bugs. To build dependable input validators, we propose using parser generators for context-free languages. In the context of network protocols, various works have pointed at context-free languages as falling short to specify precisely or concisely common idioms found in protocols. We review those assessments and perform a rigorous, language-theoretic analysis of several common protocol idioms. We then demonstrate the practical value of our findings by developing a modular, robust, and efficient input validator for HTTP relying on context-free grammars and regular expressions.