OpenRaiser/Intern-Atlas huggingface dataset:
Scale-aware Fast R-CNN for Pedestrian Detection
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we consider the problem of pedestrian detection in natural scenes. Intuitively, instances of pedestrians with different spatial scales may exhibit dramatically different features. Thus, large variance in instance scales, which results in undesirable large intra-category variance in features, may severely hurt the performance of modern object instance detection methods. We argue that this issue can be substantially alleviated by the divide-and-conquer philosophy. Taking pedestrian detection as an example, we illustrate how we can leverage this philosophy to develop a Scale-Aware Fast R-CNN (SAF R-CNN) framework. The model introduces multiple built-in sub-networks which detect pedestrians with scales from disjoint ranges. Outputs from all the sub-networks are then adaptively combined to generate the final detection results that are shown to be robust to large variance in instance scales, via a gate function defined over the sizes of object proposals. Extensive evaluations on several challenging pedestrian detection datasets well demonstrate the effectiveness of the proposed SAF R-CNN. Particularly, our method achieves state-of-the-art performance on Caltech, INRIA, and ETH, and obtains competitive results on KITTI.
Wireless Physical-Layer Identification: Modeling and Validation
Venue: arXiv cs.CR 2016
Year: 2016

The wireless physical-layer identification (WPLI) techniques utilize the unique features of the physical waveforms of wireless signals to identify and classify authorized devices. As the inherent physical layer features are difficult to forge, WPLI is deemed as a promising technique for wireless security solutions. However, as of today it still remains unclear whether existing WPLI techniques can be applied under real-world requirements and constraints. In this paper, through both theoretical modeling and experiment validation, the reliability and differentiability of WPLI techniques are rigorously evaluated, especially under the constraints of state-of-art wireless devices, real operation environments, as well as wireless protocols and regulations. Specifically, a theoretical model is first established to systematically describe the complete procedure of WPLI. More importantly, the proposed model is then implemented to thoroughly characterize various WPLI techniques that utilize the spectrum features coming from the non-linear RF-front-end, under the influences from different transmitters, receivers, and wireless channels. Subsequently, the limitations of existing WPLI techniques are revealed and evaluated in details using both the developed theoretical model and in-lab experiments. The real-world requirements and constraints are characterized along each step in WPLI, including i) the signal processing at the transmitter (device to be identified), ii) the various physical layer features that originate from circuits, antenna, and environments, iii) the signal propagation in various wireless channels, iv) the signal reception and processing at the receiver (the identifier), and v) the fingerprint extraction and classification at the receiver.
Why Johnny Still, Still Can't Encrypt: Evaluating the Usability of a Modern PGP Client
Venue: arXiv cs.CR 2016
Year: 2016

This paper presents the results of a laboratory study involving Mailvelope, a modern PGP client that integrates tightly with existing webmail providers. In our study, we brought in pairs of participants and had them attempt to use Mailvelope to communicate with each other. Our results shown that more than a decade and a half after \textit{Why Johnny Can't Encrypt}, modern PGP tools are still unusable for the masses. We finish with a discussion of pain points encountered using Mailvelope, and discuss what might be done to address them in future PGP systems.
Subsequence Automata with Default Transitions
Venue: arXiv cs.FL 2016
Year: 2016

Let $S$ be a string of length $n$ with characters from an alphabet of size $σ$. The \emph{subsequence automaton} of $S$ (often called the \emph{directed acyclic subsequence graph}) is the minimal deterministic finite automaton accepting all subsequences of $S$. A straightforward construction shows that the size (number of states and transitions) of the subsequence automaton is $O(nσ)$ and that this bound is asymptotically optimal. In this paper, we consider subsequence automata with \emph{default transitions}, that is, special transitions to be taken only if none of the regular transitions match the current character, and which do not consume the current character. We show that with default transitions, much smaller subsequence automata are possible, and provide a full trade-off between the size of the automaton and the \emph{delay}, i.e., the maximum number of consecutive default transitions followed before consuming a character. Specifically, given any integer parameter $k$, $1 < k \leq σ$, we present a subsequence automaton with default transitions of size $O(nk\log_{k}σ)$ and delay $O(\log_k σ)$. Hence, with $k = 2$ we obtain an automaton of size $O(n \log σ)$ and delay $O(\log σ)$. On the other extreme, with $k = σ$, we obtain an automaton of size $O(n σ)$ and delay $O(1)$, thus matching the bound for the standard subsequence automaton construction. Finally, we generalize the result to multiple strings. The key component of our result is a novel hierarchical automata construction of independent interest.
Quad-LED and Dual-LED Complex Modulation for Visible Light Communication
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose simple and novel complex modulation techniques that exploit the spatial domain to transmit complex-valued modulation symbols in visible light wireless communication. The idea is to use multiple light emitting diodes (LEDs) to convey the real and imaginary parts of a complex modulation symbol and their sign information, or, alternately, to convey the magnitude and phase of a complex symbol. The proposed techniques are termed as {\em quad-LED complex modulation (QCM)} and {\em dual-LED complex modulation (DCM)}. The proposed QCM scheme uses four LEDs (hence the name `quad-LED'); while the magnitudes of the real and imaginary parts are conveyed through intensity modulation of LEDs, the sign information is conveyed through spatial indexing of LEDs. The proposed DCM scheme, on the other hand, exploits the polar representation of a complex symbol; it uses only two LEDs (hence the name `dual-LED'), one LED to map the magnitude and another LED to map the phase of a complex modulation symbol. These techniques do not need Hermitian symmetry operation to generate LED compatible positive real transmit signals. We present zero-forcing and minimum distance detectors and their performance for QCM-OFDM and DCM-OFDM. We further propose another modulation scheme, termed as SM-DCM {\em (spatial modulation-DCM)} scheme, which brings in the advantage of spatial modulation (SM) to DCM. The proposed SM-DCM scheme uses two DCM BLOCKs with two LEDs in each BLOCK, and an index bit decides which among the two BLOCKs will be used in a given channel use. We study the bit error rate (BER) performance of the proposed schemes through analysis and simulations. Using tight analytical BER upper bounds and spatial distribution of the received signal-to-noise ratios, we compute and plot the achievable rate contours for a given target BER in QCM, DCM, and SM-DCM.
From Byzantine Failures to Crash Failures in Message-Passing Systems: a BG Simulation-based approach
Venue: arXiv cs.DC 2016
Year: 2016

The BG-simulation is a powerful reduction algorithm designed for asynchronous read/write crash-prone systems. It allows a set of $(t+1)$ asynchronous sequential processes to wait-free simulate (i.e., despite the crash of up to $t$ of them) an arbitrary number $n$ of processes under the assumption that at most $t$ of them may crash. The BG simulation shows that, in read/write systems, the crucial parameter is not the number $n$ of processes, but the upper bound $t$ on the number of process crashes. The paper extends the concept of BG simulation to asynchronous message-passing systems prone to Byzantine failures. Byzantine failures are the most general type of failure: a faulty process can exhibit any arbitrary behavior. Because of this, they are also the most difficult to analyze and to handle algorithmically. The main contribution of the paper is a signature-free reduction of Byzantine failures to crash failures. Assuming $t<\min(n',n/3)$, the paper presents an algorithm that simulates a system of $n'$ processes where up to $t$ may crash, on top of a basic system of $n$ processes where up to $t$ may be Byzantine. While topological techniques have been used to relate the computability of Byzantine failure-prone systems to that of crash failure-prone ones, this simulation is the first, to our knowledge, that establishes this relation directly, in an algorithmic way. In addition to extending the basic BG simulation to message-passing systems and failures more severe than process crashes, being modular and direct, this simulation provides us with a deeper insight in the nature and understanding of crash and Byzantine failures in the context of asynchronous message-passing systems. Moreover, it also allows crash-tolerant algorithms, designed for asynchronous read/write systems, to be executed on top of asynchronous message-passing systems prone to Byzantine failures.
Harvesting Full-Duplex Rate Gains in Cellular Networks with Half-Duplex User Terminals
Venue: arXiv cs.IT 2016
Year: 2016

Full-Duplex (FD) transceivers may be expensive in terms of complexity, power consumption, and price to be implemented in all user terminals. Therefore, techniques to exploit in-band full-duplex communication with FD base stations (BSs) and half-duplex (HD) users' equipment (UEs) are required. In this context, 3-node topology (3NT) has been recently proposed for FD BSs to reuse the uplink (UL) and downlink (DL) channels with HD terminals within the same cell. In this paper, we present a tractable mathematical framework, based on stochastic geometry, for 3NT in cellular networks. To this end, we propose a design paradigm via pulse-shaping and partial overlap between UL and DL channels to maximize the harvested rate gains in 3NT. The results show that 3NT achieves a close performance to networks with FD BSs and FD UEs, denoted by 2-node topology (2NT) networks. A maximum of 5$\%$ rate loss is reported when 3NT is compared to 2NT with efficient self-interference cancellation (SIC). If the SIC in 2NT is not efficient, 3NT highly outperforms 2NT. Consequently, we conclude that, irrespective to the UE duplexing scheme, it is sufficient to have FD BSs to harvest FD rate gains.
Lattice-Theoretic Progress Measures and Coalgebraic Model Checking (with Appendices)
Venue: arXiv cs.LO 2016
Year: 2016

In the context of formal verification in general and model checking in particular, parity games serve as a mighty vehicle: many problems are encoded as parity games, which are then solved by the seminal algorithm by Jurdzinski. In this paper we identify the essence of this workflow to be the notion of progress measure, and formalize it in general, possibly infinitary, lattice-theoretic terms. Our view on progress measures is that they are to nested/alternating fixed points what invariants are to safety/greatest fixed points, and what ranking functions are to liveness/least fixed points. That is, progress measures are combination of the latter two notions (invariant and ranking function) that have been extensively studied in the context of (program) verification. We then apply our theory of progress measures to a general model-checking framework, where systems are categorically presented as coalgebras. The framework's theoretical robustness is witnessed by a smooth transfer from the branching-time setting to the linear-time one. Although the framework can be used to derive some decision procedures for finite settings, we also expect the proposed framework to form a basis for sound proof methods for some undecidable/infinitary problems.
BinaryConnect: Training Deep Neural Networks with binary weights during propagations
Venue: arXiv cs.LG 2016
Year: 2016

Deep Neural Networks (DNN) have achieved state-of-the-art results in a wide range of tasks, with the best results obtained with large training sets and large models. In the past, GPUs enabled these breakthroughs because of their greater computational speed. In the future, faster computation at both training and test time is likely to be crucial for further progress and for consumer applications on low-power devices. As a result, there is much interest in research and development of dedicated hardware for Deep Learning (DL). Binary weights, i.e., weights which are constrained to only two possible values (e.g. -1 or 1), would bring great benefits to specialized DL hardware by replacing many multiply-accumulate operations by simple accumulations, as multipliers are the most space and power-hungry components of the digital implementation of neural networks. We introduce BinaryConnect, a method which consists in training a DNN with binary weights during the forward and backward propagations, while retaining precision of the stored weights in which gradients are accumulated. Like other dropout schemes, we show that BinaryConnect acts as regularizer and we obtain near state-of-the-art results with BinaryConnect on the permutation-invariant MNIST, CIFAR-10 and SVHN.
Algorithmic information, plane Kakeya sets, and conditional dimension
Venue: arXiv cs.CC 2016
Year: 2016

We formulate the conditional Kolmogorov complexity of x given y at precision r, where x and y are points in Euclidean spaces and r is a natural number. We demonstrate the utility of this notion in two ways. 1. We prove a point-to-set principle that enables one to use the (relativized, constructive) dimension of a single point in a set E in a Euclidean space to establish a lower bound on the (classical) Hausdorff dimension of E. We then use this principle, together with conditional Kolmogorov complexity in Euclidean spaces, to give a new proof of the known, two-dimensional case of the Kakeya conjecture. This theorem of geometric measure theory, proved by Davies in 1971, says that every plane set containing a unit line segment in every direction has Hausdorff dimension 2. 2. We use conditional Kolmogorov complexity in Euclidean spaces to develop the lower and upper conditional dimensions dim(x|y) and Dim(x|y) of x given y, where x and y are points in Euclidean spaces. Intuitively these are the lower and upper asymptotic algorithmic information densities of x conditioned on the information in y. We prove that these conditional dimensions are robust and that they have the correct information-theoretic relationships with the well-studied dimensions dim(x) and Dim(x) and the mutual dimensions mdim(x:y) and Mdim(x:y).
SegNet: A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

We present a novel and practical deep fully convolutional neural network architecture for semantic pixel-wise segmentation termed SegNet. This core trainable segmentation engine consists of an encoder network, a corresponding decoder network followed by a pixel-wise classification layer. The architecture of the encoder network is topologically identical to the 13 convolutional layers in the VGG16 network. The role of the decoder network is to map the low resolution encoder feature maps to full input resolution feature maps for pixel-wise classification. The novelty of SegNet lies is in the manner in which the decoder upsamples its lower resolution input feature map(s). Specifically, the decoder uses pooling indices computed in the max-pooling step of the corresponding encoder to perform non-linear upsampling. This eliminates the need for learning to upsample. The upsampled maps are sparse and are then convolved with trainable filters to produce dense feature maps. We compare our proposed architecture with the widely adopted FCN and also with the well known DeepLab-LargeFOV, DeconvNet architectures. This comparison reveals the memory versus accuracy trade-off involved in achieving good segmentation performance. SegNet was primarily motivated by scene understanding applications. Hence, it is designed to be efficient both in terms of memory and computational time during inference. It is also significantly smaller in the number of trainable parameters than other competing architectures. We also performed a controlled benchmark of SegNet and other architectures on both road scenes and SUN RGB-D indoor scene segmentation tasks. We show that SegNet provides good performance with competitive inference time and more efficient inference memory-wise as compared to other architectures. We also provide a Caffe implementation of SegNet and a web demo at http://mi.eng.cam.ac.uk/projects/segnet/.
ProtNN: Fast and Accurate Nearest Neighbor Protein Function Prediction based on Graph Embedding in Structural and Topological Space
Venue: arXiv cs.LG 2016
Year: 2016

Studying the function of proteins is important for understanding the molecular mechanisms of life. The number of publicly available protein structures has increasingly become extremely large. Still, the determination of the function of a protein structure remains a difficult, costly, and time consuming task. The difficulties are often due to the essential role of spatial and topological structures in the determination of protein functions in living cells. In this paper, we propose ProtNN, a novel approach for protein function prediction. Given an unannotated protein structure and a set of annotated proteins, ProtNN finds the nearest neighbor annotated structures based on protein-graph pairwise similarities. Given a query protein, ProtNN finds the nearest neighbor reference proteins based on a graph representation model and a pairwise similarity between vector embedding of both query and reference protein-graphs in structural and topological spaces. ProtNN assigns to the query protein the function with the highest number of votes across the set of k nearest neighbor reference proteins, where k is a user-defined parameter. Experimental evaluation demonstrates that ProtNN is able to accurately classify several datasets in an extremely fast runtime compared to state-of-the-art approaches. We further show that ProtNN is able to scale up to a whole PDB dataset in a single-process mode with no parallelization, with a gain of thousands order of magnitude of runtime compared to state-of-the-art approaches.
Impact of Underlaid Multi-antenna D2D on Cellular Downlink in Massive MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider a massive multiple-input multiple-output (MIMO) downlink system underlaid with a network of multi-antenna D2D user equipments (UEs). Each D2D transmitter (Tx) uses all its antennas to beamform information towards its desired D2D receiver, which uses only a single antenna for reception. While beamforming at the D2D Tx reduces D2D interference to the neighbouring cellular UEs (CUEs), the cellular-to-D2D interference is also negligible due to highly directional beamforming at the massive MIMO base station. For the above proposed system, we analyze the average per-user spectral efficiency (SE) of CUEs ($R^{c,d}$) as a function of the D2D area spectral efficiency (ASE). Our analysis reveals that for a fixed D2D ASE ($R_0^{(d)}$) and fixed number of D2D antennas ($N$), with increasing density of D2D Txs ($λ$), $R^{c,d}$ increases (for sufficiently large $λ$) and approaches a fundamental limit $R_{\infty}^{c,d}$ as $λ\to \infty$. Also, $R_{\infty}^{c,d}$ depends on $R_{0}^{(d)}$ and $N$, only through the ratio $\frac{R_{0}^{(d)}}{N-1}$, i.e, for a given fundamental limit $R_{\infty}^{c,d}$, the D2D ASE can be approximately doubled with every doubling in $N$.
Fast Collaborative Filtering from Implicit Feedback with Provable Guarantees
Venue: arXiv cs.LG 2016
Year: 2016

Building recommendation algorithms is one of the most challenging tasks in Machine Learning. Although most of the recommendation systems are built on explicit feedback available from the users in terms of rating or text, a majority of the applications do not receive such feedback. Here we consider the recommendation task where the only available data is the records of user-item interaction over web applications over time, in terms of subscription or purchase of items; this is known as implicit feedback recommendation. There is usually a massive amount of such user-item interaction available for any web applications. Algorithms like PLSI or Matrix Factorization runs several iterations through the dataset, and may prove very expensive for large datasets. Here we propose a recommendation algorithm based on Method of Moment, which involves factorization of second and third order moments of the dataset. Our algorithm can be proven to be globally convergent using PAC learning theory. Further, we show how to extract the parameters using only three passes through the entire dataset. This results in a highly scalable algorithm that scales up to million of users even on a machine with a single-core processor and 8 GB RAM and produces competitive performance in comparison with existing algorithms.
Is It Possible to Simultaneously Achieve Zero Handover Failure Rate and Ping-Pong Rate?
Venue: arXiv cs.NI 2016
Year: 2016

Network densification through the deployment of large number of small cells has been considered as the dominant driver for wireless evolution into 5G. However, it has increased the complexity of mobility management, and operators have been facing the technical challenges in handover (HO) parameter optimization. The trade-off between the HO failure (HOF) rate and the ping-pong (PP) rate has further complicated the challenges. In this article, we proposed ZEro handover failure with Unforced and automatic time-to-execute Scaling (ZEUS) HO. ZEUS HO assures HO signaling when a user equipment (UE) is in a good radio link condition and executes the HO at an optimal time. We analyzed the HO performance of Long-Term Evolution (LTE) and ZEUS theoretically using a geometry-based model, considering the most important HO parameter, i.e., HO margin (HOM). We derived the probabilities of HOF and PP from the analysis. The numerical results demonstrated that ZEUS HO can achieve zero HOF rate without increasing the PP rate, solving the trade-off. Furthermore, we showed that the ZEUS HO can accomplish zero HOF rate and zero PP rate simultaneously with an extension of keeping fast moving users out of small cells.
Burrows-Wheeler transform for terabases
Venue: arXiv cs.DS 2016
Year: 2016

In order to avoid the reference bias introduced by mapping reads to a reference genome, bioinformaticians are investigating reference-free methods for analyzing sequenced genomes. With large projects sequencing thousands of individuals, this raises the need for tools capable of handling terabases of sequence data. A key method is the Burrows-Wheeler transform (BWT), which is widely used for compressing and indexing reads. We propose a practical algorithm for building the BWT of a large read collection by merging the BWTs of subcollections. With our 2.4 Tbp datasets, the algorithm can merge 600 Gbp/day on a single system, using 30 gigabytes of memory overhead on top of the run-length encoded BWTs.