OpenRaiser/Intern-Atlas huggingface dataset:
Beyond Brightness Constancy: Learning Noise Models for Optical Flow
Venue: arXiv cs.CV 2016
Year: 2016

Optical flow is typically estimated by minimizing a "data cost" and an optional regularizer. While there has been much work on different regularizers many modern algorithms still use a data cost that is not very different from the ones used over 30 years ago: a robust version of brightness constancy or gradient constancy. In this paper we leverage the recent availability of ground-truth optical flow databases in order to learn a data cost. Specifically we take a generative approach in which the data cost models the distribution of noise after warping an image according to the flow and we measure the "goodness" of a data cost by how well it matches the true distribution of flow warp error. Consistent with current practice, we find that robust versions of gradient constancy are better models than simple brightness constancy but a learned GMM that models the density of patches of warp error gives a much better fit than any existing assumption of constancy. This significant advantage of the GMM is due to an explicit modeling of the spatial structure of warp errors, a feature which is missing from almost all existing data costs in optical flow. Finally, we show how a good density model of warp error patches can be used for optical flow estimation on whole images. We replace the data cost by the expected patch log-likelihood (EPLL), and show how this cost can be optimized iteratively using an additional step of denoising the warp error image. The results of our experiments are promising and show that patch models with higher likelihood lead to better optical flow estimation.
Full-Duplex Cellular Networks: It Works!
Venue: arXiv cs.IT 2016
Year: 2016

Full-duplex (FD) communications with bidirectional transmitting and receiving at the same time and frequency radio resource have long been deemed a promising way to boost spectrum efficiency, but hindered by the techniques for self-interference cancellation (SIC). Recent breakthroughs in analog and digital signal processing yield the feasibility of beyond $100$ dB SIC capability and make it possible for FD communications to demonstrate nearly doubled spectrum efficiency for point-to-point links. Now it is time to shift at least partial of our focus to full duplex networking, such as in cellular networks, since it is not straightforward but demanding novel and more complicated interference management techniques. Before putting FD networking into practice, we need to understand that what scenarios FD communications should be applied in under the current technology maturity, how bad the performance will be if we do nothing to deal with the newly introduced interference, and most importantly, how much improvement could be achieved after applying advanced solutions. This article will shed light on these questions.
Modeling and predicting measured response time of cloud-based web services using long-memory time series
Venue: arXiv cs.NI 2016
Year: 2016

Predicting cloud performance from user's perspective is a complex task, because of several factors involved in providing the service to the consumer. In this work, the response time of 10 real-world services is analyzed. We have observed long memory in terms of the measured response time of the CPU-intensive services and statistically verified this observation using estimators of the Hurst exponent. Then, naïve, mean, autoregressive integrated moving average (ARIMA) and autoregressive fractionally integrated moving average (ARFIMA) methods are used to forecast the future values of quality of service (QoS) at runtime. Results of the cross-validation over the 10 datasets show that the long-memory ARFIMA model provides the mean of 37.5 % and the maximum of 57.8 % reduction in the forecast error when compared to the short-memory ARIMA model according to the standard error measure of mean absolute percentage error. Our work implies that consideration of the long-range dependence in QoS data can help to improve the selection of services according to their possible future QoS values.
Achieving Energy Efficiency in Cloud Brokering
Venue: arXiv cs.NI 2016
Year: 2016

The proliferation of cloud providers has brought substantial interoperability complexity to the public cloud market, in which cloud brokering has been playing an important role. However, energy-related issues for public clouds have not been well addressed in the literature. In this paper, we claim that the broker is also situated in a perfect position where necessary actions can be taken to achieve energy efficiency for public cloud systems, particularly through job assignment and scheduling. We formulate the problem by a mixed integer program and prove its NP-hardness. Based on the complexity analysis, we simplify the problem by introducing admission control on jobs. In the sequel, optimal job assignment can be done straightforwardly and the problem is transformed into improving job admission rate by scheduling on two coupled phases: data transfer and job execution. The two scheduling phases are further decoupled and we develop efficient scheduling algorithm for each of them. Experimental results show that the proposed solution can achieve significant reduction on energy consumption with admission rates improved as well, even in large-scale public cloud systems.
Semi-supervised learning of local structured output predictors
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we study the problem of semi-supervised structured output prediction, which aims to learn predictors for structured outputs, such as sequences, tree nodes, vectors, etc., from a set of data points of both input-output pairs and single inputs without outputs. The traditional methods to solve this problem usually learns one single predictor for all the data points, and ignores the variety of the different data points. Different parts of the data set may have different local distributions, and requires different optimal local predictors. To overcome this disadvantage of existing methods, we propose to learn different local predictors for neighborhoods of different data points, and the missing structured outputs simultaneously. In the neighborhood of each data point, we proposed to learn a linear predictor by minimizing both the complexity of the predictor and the upper bound of the structured prediction loss. The minimization is conducted by gradient descent algorithms. Experiments over four benchmark data sets, including DDSM mammography medical images, SUN natural image data set, Cora research paper data set, and Spanish news wire article sentence data set, show the advantages of the proposed method.
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication
Venue: arXiv cs.DS 2016
Year: 2016

This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic data structure problems. We introduce a new randomized nondeterministic four-party communication model that enables "accelerated", error-preserving simulations of dynamic data structures. We use this technique to prove an $Ω(n(\log n/\log\log n)^2)$ cell-probe lower bound for the dynamic 2D weighted orthogonal range counting problem (2D-ORC) with $n/\mathrm{poly}\log n$ updates and $n$ queries, that holds even for data structures with $\exp(-\tildeΩ(n))$ success probability. This result not only proves the highest amortized lower bound to date, but is also tight in the strongest possible sense, as a matching upper bound can be obtained by a deterministic data structure with worst-case operational time. This is the first demonstration of a "sharp threshold" phenomenon for dynamic data structures. Our broader motivation is that cell-probe lower bounds for exponentially small success facilitate reductions from dynamic to static data structures. As a proof-of-concept, we show that a slightly strengthened version of our lower bound would imply an $Ω((\log n /\log\log n)^2)$ lower bound for the static 3D-ORC problem with $O(n\log^{O(1)}n)$ space. Such result would give a near quadratic improvement over the highest known static cell-probe lower bound, and break the long standing $Ω(\log n)$ barrier for static data structures.
Optimal Binary Coding for $q^+$ -state Data Embedding
Venue: arXiv cs.IT 2016
Year: 2016

In steganography, we always hope to maximize the embedding payload subject to an upper-bounded distortion. We need suitable distortion measurement to evaluate the embedding impact. However, different distortion functions exposes different levels of distortion evaluation, implying that we have different optimization distributions by applying different distortion functions. In applications, the embedding distortion is caused by a certain number of embedding operations. Instead of a predefined distortion, we actually utilize a number of modifications to embed as many message bits as possible as long as the modifications are acceptable. This paper focuses on the design of optimal binary codewords for data embedding with a limited number of modification candidates. We have proved the optimality of the designed codewords, and proposed the way to construct the optimal binary codewords. It is pointed out that the optimal binary code is not unique, and an optimal code can be computed within a low computational cost.
Using Deep Learning for Image-Based Plant Disease Detection
Venue: arXiv cs.CV 2016
Year: 2016

Crop diseases are a major threat to food security, but their rapid identification remains difficult in many parts of the world due to the lack of the necessary infrastructure. The combination of increasing global smartphone penetration and recent advances in computer vision made possible by deep learning has paved the way for smartphone-assisted disease diagnosis. Using a public dataset of 54,306 images of diseased and healthy plant leaves collected under controlled conditions, we train a deep convolutional neural network to identify 14 crop species and 26 diseases (or absence thereof). The trained model achieves an accuracy of 99.35% on a held-out test set, demonstrating the feasibility of this approach. When testing the model on a set of images collected from trusted online sources - i.e. taken under conditions different from the images used for training - the model still achieves an accuracy of 31.4%. While this accuracy is much higher than the one based on random selection (2.6%), a more diverse set of training data is needed to improve the general accuracy. Overall, the approach of training deep learning models on increasingly large and publicly available image datasets presents a clear path towards smartphone-assisted crop disease diagnosis on a massive global scale.
A Primer on Cellular Network Analysis Using Stochastic Geometry
Venue: arXiv cs.IT 2016
Year: 2016

This tutorial is intended as an accessible but rigorous first reference for someone interested in learning how to model and analyze cellular network performance using stochastic geometry. In particular, we focus on computing the signal-to-interference-plus-noise ratio (SINR) distribution, which can be characterized by the coverage probability (the SINR CCDF) or the outage probability (its CDF). We model base stations (BSs) in the network as a realization of a homogeneous Poisson point process of density $λ$, and compute the SINR for three main cases: the downlink, uplink, and finally the multi-tier downlink, which is characterized by having $k$ tiers of BSs each with a unique density $λ_i$ and transmit power $p_i$. These three baseline results have been extensively extended to many different scenarios, and we conclude with a brief summary of some of those extensions.
PSNR and Jitter Analysis of Routing Protocols for Video Streaming in Sparse MANET Networks, using NS2 and the Evalvid Framework
Venue: arXiv cs.NI 2016
Year: 2016

Advances in multimedia and ad-hoc networking have urged a wealth of research in multimedia delivery over ad-hoc networks. This comes as no surprise, as those networks are versatile and beneficial to a plethora of applications where the use of fully wired network has proved intricate if not impossible, such as prompt formation of networks during conferences, disaster relief in case of flood and earthquake, and also in war activities. It this paper, we aim to investigate the combined impact of network sparsity and network node density on the Peak Signal Noise to Ratio (PSNR) and jitter performance of proactive and reactive routing protocols in ad-hoc networks. We also shed light onto the combined effect of mobility and sparsity on the performance of these protocols. We validate our results through the use of an integrated Simulator-Evaluator environment consisting of the Network Simulator NS2, and the Video Evaluation Framework Evalvid.
Disease dynamics on a network game: a little empathy goes a long way
Venue: arXiv cs.SI 2016
Year: 2016

Individuals change their behavior during an epidemic in response to whether they and/or those they interact with are healthy or sick. Healthy individuals are concerned about contracting a disease from their sick contacts and may utilize protective measures. Sick individuals may be concerned with spreading the disease to their healthy contacts and adopt preemptive measures. Yet, in practice both protective and preemptive changes in behavior come with costs. This paper proposes a stochastic network disease game model that captures the self-interests of individuals during the spread of a susceptible-infected-susceptible (SIS) disease where individuals react to current risk of disease spread, and their reactions together with the current state of the disease stochastically determine the next stage of the disease. We show that there is a critical level of concern, i.e., empathy, by the sick individuals above which disease is eradicated fast. Furthermore, we find that if the network and disease parameters are above the epidemic threshold, the risk averse behavior by the healthy individuals cannot eradicate the disease without the preemptive measures of the sick individuals. This imbalance in the role played by the response of the infected versus the susceptible individuals in disease eradication affords critical policy insights.
Radio Resource Allocation for Device-to-Device Underlay Communication Using Hypergraph Theory
Venue: arXiv cs.NI 2016
Year: 2016

Device-to-Device (D2D) communication has been recognized as a promising technique to offload the traffic for the evolved Node B (eNB). However, the D2D transmission as an underlay causes severe interference to both the cellular and other D2D links, which imposes a great technical challenge to radio resource allocation. Conventional graph based resource allocation methods typically consider the interference between two user equipments (UEs), but they cannot model the interference from multiple UEs to completely characterize the interference. In this paper, we study channel allocation using hypergraph theory to coordinate the interference between D2D pairs and cellular UEs, where an arbitrary number of D2D pairs are allowed to share the uplink channels with the cellular UEs. Hypergraph coloring is used to model the cumulative interference from multiple D2D pairs, and thus, eliminate the mutual interference. Simulation results show that the system capacity is significantly improved using the proposed hypergraph method in comparison to the conventional graph based one.
The Univariate Flagging Algorithm (UFA): a Fully-Automated Approach for Identifying Optimal Thresholds in Data
Venue: arXiv cs.LG 2016
Year: 2016

In many data classification problems, there is no linear relationship between an explanatory and the dependent variables. Instead, there may be ranges of the input variable for which the observed outcome is signficantly more or less likely. This paper describes an algorithm for automatic detection of such thresholds, called the Univariate Flagging Algorithm (UFA). The algorithm searches for a separation that optimizes the difference between separated areas while providing the maximum support. We evaluate its performance using three examples and demonstrate that thresholds identified by the algorithm align well with visual inspection and subject matter expertise. We also introduce two classification approaches that use UFA and show that the performance attained on unseen test data is equal to or better than that of more traditional classifiers. We demonstrate that the proposed algorithm is robust against missing data and noise, is scalable, and is easy to interpret and visualize. It is also well suited for problems where incidence of the target is low.
Connected reversible Mealy automata of prime size cannot generate infinite Burnside groups
Venue: arXiv cs.FL 2016
Year: 2016

The simplest example of an infinite Burnside group arises in the class of automaton groups. However there is no known example of such a group generated by a reversible Mealy automaton. It has been proved that, for a connected automaton of size at most~3, or when the automaton is not bireversible, the generated group cannot be Burnside infinite. In this paper, we extend these results to automata with bigger stateset, proving that, if a connected reversible automaton has a prime number of states, it cannot generate an infinite Burnside group.
Noise Robust Speech Recognition Using Multi-Channel Based Channel Selection And ChannelWeighting
Venue: arXiv cs.SD 2016
Year: 2016

In this paper, we study several microphone channel selection and weighting methods for robust automatic speech recognition (ASR) in noisy conditions. For channel selection, we investigate two methods based on the maximum likelihood (ML) criterion and minimum autoencoder reconstruction criterion, respectively. For channel weighting, we produce enhanced log Mel filterbank coefficients as a weighted sum of the coefficients of all channels. The weights of the channels are estimated by using the ML criterion with constraints. We evaluate the proposed methods on the CHiME-3 noisy ASR task. Experiments show that channel weighting significantly outperforms channel selection due to its higher flexibility. Furthermore, on real test data in which different channels have different gains of the target signal, the channel weighting method performs equally well or better than the MVDR beamforming, despite the fact that the channel weighting does not make use of the phase delay information which is normally used in beamforming.
Vector Network Coding Based on Subspace Codes Outperforms Scalar Linear Network Coding
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers vector network coding based on rank-metric codes and subspace codes. Our main result is that vector network coding can significantly reduce the required field size compared to scalar linear network coding in the same multicast network. The achieved gap between the field size of scalar and vector network coding is in the order of $q^{(\ell-1)t^2/\ell}-q^t$, for any $q \geq 2$, where $t$ denotes the dimension of the vector solution, and the number of messages is $2 \ell$, ${\ell \geq 2}$. Previously, only a gap of constant size had been shown. This implies also the same gap between the field size in linear and non-linear scalar network coding for multicast networks. Similar results are given for any number of odd messages greater than two. The results are obtained by considering several multicast networks which are variations of the well-known combination network.
Attacks on Fitness Trackers Revisited: A Case-Study of Unfit Firmware Security
Venue: arXiv cs.CR 2016
Year: 2016

Fitness trackers - wearables that continuously record a wearer's step count and related activity data - are quickly gaining in popularity. Apart from being useful for individuals seeking a more healthy lifestyle, their data is also being used in court and by insurance companies to adjust premiums. For these use cases, it is essential to ensure authenticity and integrity of data. Here we demonstrate a flaw in the way firmware for Withings' Activité is verified, allowing an adversary to compromise the tracker itself. This type of attack has so far not been applied to fitness trackers. Vendors have started mitigating previous attacks, which manipulated data by interfering with wireless channels, or by physically moving the tracker to fool sensors. Hardware similarities amongst different trackers suggest findings can be transferred to other tracker as well.
Performance Evaluation of LOS MIMO Systems under the Influence of Phase Noise
Venue: arXiv cs.IT 2016
Year: 2016

To deal with the ever increasing data rate demand in wireless systems, suitable backhaul solutions have to be found. One option is to use LOS MIMO systems at mmWave frequencies, as high bandwidths and spectral efficiencies will be able to fulfill this requirement. Several investigations have shown, that phase noise can decimate the efficiency of such systems immensely and needs to be adequately dealt with. In this work we investigate the system level performance of LOS MIMO systems subject to this impairment and examine the influence for various practical phase noise values. Furthermore, it is shown how a simple phase noise compensation algorithm can be used to enhance the performance of these systems in different scenarios.
Synchronization of linearly coupled reaction-diffusion neural networks with hybrid coupling and time-varying delays via aperiodically intermittent pinning control
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, the complete synchronization problem of linearly coupled neural networks with reaction-diffusion terms and time-varying delays via aperiodically intermittent pinning control is investigated. The coupling matrix for the network can be asymmetric. Compared with state coupling in the synchronization literature, we design a novel distributed coupling protocol by using the reaction-diffusion coupling-spatial coupling, which can accelerate the synchronization process. This can be regarded as the main difference between this paper and previous works. Using the Lyapunov function and theories in the aperiodically intermittent control, we present some criteria for the complete synchronization with a static coupling strength. In this case, there is no constraint on the bound of time-varying delays, so it can be larger than the length of control span. On the other hand, for the network with an adaptive coupling strength, we propose a simple adaptive rule for the coupling strength and prove its effectiveness rigorously. In this case, the bound of time-varying delay is required to be less than the infimum of the control time span. Finally, numerical simulations are given to verify the theoretical results.
High-level GPU programming in Julia
Venue: arXiv cs.DC 2016
Year: 2016

GPUs are popular devices for accelerating scientific calculations. However, as GPU code is usually written in low-level languages, it breaks the abstractions of high-level languages popular with scientific programmers. To overcome this, we present a framework for CUDA GPU programming in the high-level Julia programming language. This framework compiles Julia source code for GPU execution, and takes care of the necessary low-level interactions using modern code generation techniques to avoid run-time overhead. Evaluating the framework and its APIs on a case study comprising the trace transform from the field of image processing, we find that the impact on performance is minimal, while greatly increasing programmer productivity. The metaprogramming capabilities of the Julia language proved invaluable for enabling this. Our framework significantly improves usability of GPUs, making them accessible for a wide range of programmers. It is available as free and open-source software licensed under the MIT License.