OpenRaiser/Intern-Atlas huggingface dataset:
Robust MIMO Beamforming for Cellular and Radar Coexistence
Venue: arXiv cs.IT 2017
Year: 2017

In this letter, we consider the coexistence and spectrum sharing between downlink multi-user multiple-input-multiple-output (MU-MIMO) communication and a MIMO radar. For a given performance requirement of the downlink communication system, we design the transmit beamforming such that the detection probability of the radar is maximized. While the original optimization problem is non-convex, we exploit the monotonically increasing relationship of the detection probability with the non-centrality parameter of the resulting probability distribution to obtain a convex lower-bound optimization. The proposed beamformer is designed to be robust to imperfect channel state information (CSI). Simulation results verify that the proposed approach facilitates the coexistence between radar and communication links, and illustrates a scalable trade-off between the two systems' performance.
Combined Tractability of Query Evaluation via Tree Automata and Cycluits (Extended Version)
Venue: arXiv cs.DB 2017
Year: 2017

We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We introduce a new Datalog fragment with stratified negation, intensional-clique-guarded Datalog (ICG-Datalog), with linear-time evaluation on structures of bounded treewidth for programs of bounded rule size. Such programs capture in particular conjunctive queries with simplicial decompositions of bounded width, guarded negation fragment queries of bounded CQ-rank, or two-way regular path queries. Our result proceeds via compilation to alternating two-way automata, whose semantics is defined via cyclic provenance circuits (cycluits) that can be tractably evaluated. Last, we prove that probabilistic query evaluation remains intractable in combined complexity under this parameterization.
LoPub: High-Dimensional Crowdsourced Data Publication with Local Differential Privacy
Venue: arXiv cs.CR 2017
Year: 2017

High-dimensional crowdsourced data collected from a large number of users produces rich knowledge for our society. However, it also brings unprecedented privacy threats to participants. Local privacy, a variant of differential privacy, is proposed as a means to eliminate the privacy concern. Unfortunately, achieving local privacy on high-dimensional crowdsourced data raises great challenges on both efficiency and effectiveness. Here, based on EM and Lasso regression, we propose efficient multi-dimensional joint distribution estimation algorithms with local privacy. Then, we develop a Locally privacy-preserving high-dimensional data Publication algorithm, LoPub, by taking advantage of our distribution estimation techniques. In particular, both correlations and joint distribution among multiple attributes can be identified to reduce the dimension of crowdsourced data, thus achieving both efficiency and effectiveness in locally private high-dimensional data publication. Extensive experiments on real-world datasets demonstrated that the efficiency of our multivariate distribution estimation scheme and confirm the effectiveness of our LoPub scheme in generating approximate datasets with local privacy.
Finding Tiny Faces
Venue: arXiv cs.CV 2017
Year: 2017

Though tremendous strides have been made in object recognition, one of the remaining open challenges is detecting small objects. We explore three aspects of the problem in the context of finding small faces: the role of scale invariance, image resolution, and contextual reasoning. While most recognition approaches aim to be scale-invariant, the cues for recognizing a 3px tall face are fundamentally different than those for recognizing a 300px tall face. We take a different approach and train separate detectors for different scales. To maintain efficiency, detectors are trained in a multi-task fashion: they make use of features extracted from multiple layers of single (deep) feature hierarchy. While training detectors for large objects is straightforward, the crucial challenge remains training detectors for small objects. We show that context is crucial, and define templates that make use of massively-large receptive fields (where 99% of the template extends beyond the object of interest). Finally, we explore the role of scale in pre-trained deep networks, providing ways to extrapolate networks tuned for limited scales to rather extreme ranges. We demonstrate state-of-the-art results on massively-benchmarked face datasets (FDDB and WIDER FACE). In particular, when compared to prior art on WIDER FACE, our results reduce error by a factor of 2 (our models produce an AP of 82% while prior art ranges from 29-64%).
MaMaDroid: Detecting Android Malware by Building Markov Chains of Behavioral Models
Venue: arXiv cs.CR 2017
Year: 2017

The rise in popularity of the Android platform has resulted in an explosion of malware threats targeting it. As both Android malware and the operating system itself constantly evolve, it is very challenging to design robust malware mitigation techniques that can operate for long periods of time without the need for modifications or costly re-training. In this paper, we present MaMaDroid, an Android malware detection system that relies on app behavior. MaMaDroid builds a behavioral model, in the form of a Markov chain, from the sequence of abstracted API calls performed by an app, and uses it to extract features and perform classification. By abstracting calls to their packages or families, MaMaDroid maintains resilience to API changes and keeps the feature set size manageable. We evaluate its accuracy on a dataset of 8.5K benign and 35.5K malicious apps collected over a period of six years, showing that it not only effectively detects malware (with up to 99% F-measure), but also that the model built by the system keeps its detection capabilities for long periods of time (on average, 86% and 75% F-measure, respectively, one and two years after training). Finally, we compare against DroidAPIMiner, a state-of-the-art system that relies on the frequency of API calls performed by apps, showing that MaMaDroid significantly outperforms it.
Attentive Explanations: Justifying Decisions and Pointing to the Evidence
Venue: arXiv cs.CV 2017
Year: 2017

Deep models are the defacto standard in visual decision models due to their impressive performance on a wide array of visual tasks. However, they are frequently seen as opaque and are unable to explain their decisions. In contrast, humans can justify their decisions with natural language and point to the evidence in the visual world which led to their decisions. We postulate that deep models can do this as well and propose our Pointing and Justification (PJ-X) model which can justify its decision with a sentence and point to the evidence by introspecting its decision and explanation process using an attention mechanism. Unfortunately there is no dataset available with reference explanations for visual decision making. We thus collect two datasets in two domains where it is interesting and challenging to explain decisions. First, we extend the visual question answering task to not only provide an answer but also a natural language explanation for the answer. Second, we focus on explaining human activities which is traditionally more challenging than object classification. We extensively evaluate our PJ-X model, both on the justification and pointing tasks, by comparing it to prior models and ablations using both automatic and human evaluations.
A 17/12-Approximation Algorithm for 2-Vertex-Connected Spanning Subgraphs on Graphs with Minimum Degree At Least 3
Venue: arXiv cs.DS 2017
Year: 2017

We obtain a polynomial-time 17/12-approximation algorithm for the minimum-cost 2-vertex-connected spanning subgraph problem, restricted to graphs of minimum degree at least 3. Our algorithm uses the framework of ear-decompositions for approximating connectivity problems, which was previously used in algorithms for finding the smallest 2-edge-connected spanning subgraph by Cheriyan, Sebő and Szigeti (SIAM J.Discrete Math. 2001) who gave a 17/12-approximation algorithm for this problem, and by Sebő and Vygen (Combinatorica 2014), who improved the approximation ratio to 4/3.
Separation of Concerns in Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we propose a framework for solving a single-agent task by using multiple agents, each focusing on different aspects of the task. This approach has two main advantages: 1) it allows for training specialized agents on different parts of the task, and 2) it provides a new way to transfer knowledge, by transferring trained agents. Our framework generalizes the traditional hierarchical decomposition, in which, at any moment in time, a single agent has control until it has solved its particular subtask. We illustrate our framework with empirical experiments on two domains.
Neural networks based EEG-Speech Models
Venue: arXiv cs.SD 2017
Year: 2017

In this paper, we propose an end-to-end neural network (NN) based EEG-speech (NES) modeling framework, in which three network structures are developed to map imagined EEG signals to phonemes. The proposed NES models incorporate a language model based EEG feature extraction layer, an acoustic feature mapping layer, and a restricted Boltzmann machine (RBM) based the feature learning layer. The NES models can jointly realize the representation of multichannel EEG signals and the projection of acoustic speech signals. Among three proposed NES models, two augmented networks utilize spoken EEG signals as either bias or gate information to strengthen the feature learning and translation of imagined EEG signals. Experimental results show that all three proposed NES models outperform the baseline support vector machine (SVM) method on EEG-speech classification. With respect to binary classification, our approach achieves comparable results relative to deep believe network approach.
Strong Federations: An Interoperable Blockchain Solution to Centralized Third-Party Risks
Venue: arXiv cs.CR 2017
Year: 2017

Bitcoin, the first peer-to-peer electronic cash system, opened the door to permissionless, private, and trustless transactions. Attempts to repurpose Bitcoin's underlying blockchain technology have run up against fundamental limitations to privacy, faithful execution, and transaction finality. We introduce \emph{Strong Federations}: publicly verifiable, Byzantine-robust transaction networks that facilitate movement of any asset between disparate markets, without requiring third-party trust. \emph{Strong Federations} enable commercial privacy, with support for transactions where asset types and amounts are opaque, while remaining publicly verifiable. As in Bitcoin, execution fidelity is cryptographically enforced; however, \emph{Strong Federations} significantly lower capital requirements for market participants by reducing transaction latency and improving interoperability. To show how this innovative solution can be applied today, we describe \emph{\liquid}: the first implementation of \emph{Strong Federations} deployed in a Financial Market.
Secure Estimation and Zero-Error Secrecy Capacity
Venue: arXiv cs.SY 2017
Year: 2017

We study the problem of securely estimating the states of an unstable dynamical system subject to nonstochastic disturbances. The estimator obtains all its information through an uncertain channel which is subject to nonstochastic disturbances as well, and an eavesdropper obtains a disturbed version of the channel inputs through a second uncertain channel. An encoder observes and block-encodes the states in such a way that, upon sending the generated codeword, the estimator's error is bounded and such that a security criterion is satisfied ensuring that the eavesdropper obtains as little state information as possible. Two security criteria are considered and discussed with the help of a numerical example. A sufficient condition on the uncertain wiretap channel, i.e., the pair formed by the uncertain channel from encoder to estimator and the uncertain channel from encoder to eavesdropper, is derived which ensures that a bounded estimation error and security are achieved. This condition is also shown to be necessary for a subclass of uncertain wiretap channels. To formulate the condition, the zero-error secrecy capacity of uncertain wiretap channels is introduced, i.e., the maximal rate at which data can be transmitted from the encoder to the estimator in such a way that the eavesdropper is unable to reconstruct the transmitted data. Lastly, the zero-error secrecy capacity of uncertain wiretap channels is studied.
Learning to predict where to look in interactive environments using deep recurrent q-learning
Venue: arXiv cs.CV 2017
Year: 2017

Bottom-Up (BU) saliency models do not perform well in complex interactive environments where humans are actively engaged in tasks (e.g., sandwich making and playing the video games). In this paper, we leverage Reinforcement Learning (RL) to highlight task-relevant locations of input frames. We propose a soft attention mechanism combined with the Deep Q-Network (DQN) model to teach an RL agent how to play a game and where to look by focusing on the most pertinent parts of its visual input. Our evaluations on several Atari 2600 games show that the soft attention based model could predict fixation locations significantly better than bottom-up models such as Itti-Kochs saliency and Graph-Based Visual Saliency (GBVS) models.
Adversarial Deep Structural Networks for Mammographic Mass Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Mass segmentation is an important task in mammogram analysis, providing effective morphological features and regions of interest (ROI) for mass detection and classification. Inspired by the success of using deep convolutional features for natural image analysis and conditional random fields (CRF) for structural learning, we propose an end-to-end network for mammographic mass segmentation. The network employs a fully convolutional network (FCN) to model potential function, followed by a CRF to perform structural learning. Because the mass distribution varies greatly with pixel position, the FCN is combined with position priori for the task. Due to the small size of mammogram datasets, we use adversarial training to control over-fitting. Four models with different convolutional kernels are further fused to improve the segmentation results. Experimental results on two public datasets, INbreast and DDSM-BCRP, show that our end-to-end network combined with adversarial training achieves the-state-of-the-art results.
Neural Multi-Source Morphological Reinflection
Venue: arXiv cs.CL 2017
Year: 2017

We explore the task of multi-source morphological reinflection, which generalizes the standard, single-source version. The input consists of (i) a target tag and (ii) multiple pairs of source form and source tag for a lemma. The motivation is that it is beneficial to have access to more than one source form since different source forms can provide complementary information, e.g., different stems. We further present a novel extension to the encoder- decoder recurrent neural architecture, consisting of multiple encoders, to better solve the task. We show that our new architecture outperforms single-source reinflection models and publish our dataset for multi-source morphological reinflection to facilitate future research.
ProxyTorrent: Untangling the Free HTTP(S) Proxy Ecosystem
Venue: arXiv cs.NI 2017
Year: 2017

Free web proxies promise anonymity and censorship circumvention at no cost. Several websites publish lists of free proxies organized by country, anonymity level, and performance. These lists index hundreds of thousand of hosts discovered via automated tools and crowd-sourcing. A complex free proxy ecosystem has been forming over the years, of which very little is known. In this paper we shed light on this ecosystem via ProxyTorrent, a distributed measurement platform that leverages both active and passive measurements. Active measurements discover free proxies, assess their performance, and detect potential malicious activities. Passive measurements relate to proxy performance and usage in the wild, and are collected by free proxies users via a Chrome plugin we developed. ProxyTorrent has been running since January 2017, monitoring up to 180,000 free proxies and totaling more than 1,500 users. Our analysis shows that less than 2% of the proxies announced on the web indeed proxy traffic on behalf of users; further, only half of these proxies have decent performance and can be used reliably. Around 10% of the working proxies exhibit malicious behaviors, e.g., ads injection and TLS interception, and these proxies are also the ones providing the best performance. Through the analysis of more than 2 Terabytes of proxied traffic, we show that web browsing is the primary user activity. Geo-blocking avoidance is not a prominent use-case, with the exception of countries hosting popular geo-blocked content.
Concurrency-Preserving and Sound Monitoring of Multi-Threaded Component-Based Systems
Venue: arXiv cs.SE 2017
Year: 2017

This paper addresses the monitoring of logic-independent linear-time user-provided properties in multi-threaded component-based systems. We consider intrinsically independent components that can be executed concurrently with a centralized coordination for multiparty interactions. In this context, the problem that arises is that a global state of the system is not available to the monitor. A naive solution to this problem would be to plug in a monitor which would force the system to synchronize in order to obtain the sequence of global states at runtime. Such a solution would defeat the whole purpose of having concurrent components. Instead, we reconstruct on-the-fly the global states by accumulating the partial states traversed by the system at runtime. We define transformations of components that preserve their semantics and concurrency and, at the same time, allow to monitor global-state properties. Moreover, we present RVMT-BIP, a prototype tool implementing the transformations for monitoring multi-threaded systems described in the BIP (Behavior, Interaction, Priority) framework, an expressive framework for the formal construction of heterogeneous systems. Our experiments on several multi-threaded BIP systems show that RVMT-BIP induces a cheap runtime overhead.
Efficient Optical flow and Stereo Vision for Velocity Estimation and Obstacle Avoidance on an Autonomous Pocket Drone
Venue: arXiv cs.RO 2017
Year: 2017

Miniature Micro Aerial Vehicles (MAV) are very suitable for flying in indoor environments, but autonomous navigation is challenging due to their strict hardware limitations. This paper presents a highly efficient computer vision algorithm called Edge-FS for the determination of velocity and depth. It runs at 20 Hz on a 4 g stereo camera with an embedded STM32F4 microprocessor (168 MHz, 192 kB) and uses feature histograms to calculate optical flow and stereo disparity. The stereo-based distance estimates are used to scale the optical flow in order to retrieve the drone's velocity. The velocity and depth measurements are used for fully autonomous flight of a 40 g pocket drone only relying on on-board sensors. The method allows the MAV to control its velocity and avoid obstacles.
EIP - Preventing DDoS with Ephemeral IP Identifiers Cryptographically Generated
Venue: arXiv cs.NI 2017
Year: 2017

Nowadays, denial of service (DoS) attacks represent a significant fraction of all attacks that take place in the Internet and their intensity is always growing. The main DoS attack methods consist of flooding their victims with bogus packets, queries or replies, so as to prevent them from fulfilling their roles. Preventing DoS attacks at network level would be simpler if end-to-end strong authentication in any packet exchange was mandatory. However, it is also likely that its mandatory adoption would introduce more harm than benefits. In this paper we present an end-point addressing scheme and a set of security procedures which satisfy most of network level DoS prevention requirements. Instead of being known by public stable IP addresses, hosts use ephemeral IP Identifiers cryptographically generated and bound to its usage context. Self-signed certificates and challenge-based protocols allow, without the need of any third parties, the implementation of defenses against DoS attacks. Communication in the open Internet while using these special IP addresses is supported by the so-called Map/Encap approaches, which in our point of view will be sooner or later required for the future Internet.
Efficient Action Detection in Untrimmed Videos via Multi-Task Learning
Venue: arXiv cs.CV 2017
Year: 2017

This paper studies the joint learning of action recognition and temporal localization in long, untrimmed videos. We employ a multi-task learning framework that performs the three highly related steps of action proposal, action recognition, and action localization refinement in parallel instead of the standard sequential pipeline that performs the steps in order. We develop a novel temporal actionness regression module that estimates what proportion of a clip contains action. We use it for temporal localization but it could have other applications like video retrieval, surveillance, summarization, etc. We also introduce random shear augmentation during training to simulate viewpoint change. We evaluate our framework on three popular video benchmarks. Results demonstrate that our joint model is efficient in terms of storage and computation in that we do not need to compute and cache dense trajectory features, and that it is several times faster than its sequential ConvNets counterpart. Yet, despite being more efficient, it outperforms state-of-the-art methods with respect to accuracy.
Symmetric Key Encryption for Arbitrary Block Sizes from Affine Spaces
Venue: arXiv cs.CR 2017
Year: 2017

A symmetric key encryption scheme is described for blocks of general size N that is a product of powers of many prime numbers. This is accomplished by realising each number (representing a message unit) as a point in a product of affine spaces over various finite fields. Then algebro-geometric transformations on those affine spaces is transported back to provide encryption. For a specific block size${}<2^{128}$ we get more than $2^{5478}$ keys.
Hardware for Machine Learning: Challenges and Opportunities
Venue: arXiv cs.CV 2017
Year: 2017

Machine learning plays a critical role in extracting meaningful information out of the zetabytes of sensor data collected every day. For some applications, the goal is to analyze and understand the data to identify trends (e.g., surveillance, portable/wearable electronics); in other applications, the goal is to take immediate action based the data (e.g., robotics/drones, self-driving cars, smart Internet of Things). For many of these applications, local embedded processing near the sensor is preferred over the cloud due to privacy or latency concerns, or limitations in the communication bandwidth. However, at the sensor there are often stringent constraints on energy consumption and cost in addition to throughput and accuracy requirements. Furthermore, flexibility is often required such that the processing can be adapted for different applications or environments (e.g., update the weights and model in the classifier). In many applications, machine learning often involves transforming the input data into a higher dimensional space, which, along with programmable weights, increases data movement and consequently energy consumption. In this paper, we will discuss how these challenges can be addressed at various levels of hardware design ranging from architecture, hardware-friendly algorithms, mixed-signal circuits, and advanced technologies (including memories and sensors).