OpenRaiser/Intern-Atlas huggingface dataset:
Localizing Adverts in Outdoor Scenes
Venue: arXiv cs.CV 2019
Year: 2019

Online videos have witnessed an unprecedented growth over the last decade, owing to wide range of content creation. This provides the advertisement and marketing agencies plethora of opportunities for targeted advertisements. Such techniques involve replacing an existing advertisement in a video frame, with a new advertisement. However, such post-processing of online videos is mostly done manually by video editors. This is cumbersome and time-consuming. In this paper, we propose DeepAds -- a deep neural network, based on the simple encoder-decoder architecture, that can accurately localize the position of an advert in a video frame. Our approach of localizing billboards in outdoor scenes using neural nets, is the first of its kind, and achieves the best performance. We benchmark our proposed method with other semantic segmentation algorithms, on a public dataset of outdoor scenes with manually annotated billboard binary maps.
BlockLite: A Lightweight Emulator for Public Blockchains
Venue: arXiv cs.DB 2019
Year: 2019

Blockchain is an enabler of many emerging decentralized applications in areas of cryptocurrency, Internet of Things, smart healthcare, among many others. Although various open-source blockchain frameworks are available, the infrastructure is complex enough and difficult for many users to modify or test out new research ideas. To make it worse, many advantages of blockchain systems can be demonstrated only at large scales, e.g., thousands of nodes, which are not always available to researchers. This demo paper presents a lightweight single-node emulator of blockchain systems, namely \mbox{BlockLite}, designed to be executing real proof-of-work workload along with peer-to-peer network communications and hash-based immutability. BlockLite employs a preprocessing approach to avoid the per-node computation overhead at runtime and thus scales to thousands of nodes. Moreover, BlockLite offers an easy-to-use programming interface allowing for a Lego-like customization to the system, e.g. new ad-hoc consensus protocols.
Interactive Semi-automated Specification Mining for Debugging: An Experience Report
Venue: arXiv cs.SE 2019
Year: 2019

Context: Specification mining techniques are typically used to extract the specification of a software in the absence of (up-to-date) specification documents. This is useful for program comprehension, testing, and anomaly detection. However, specification mining can also potentially be used for debugging, where a faulty behavior is abstracted to give developers a context about the bug and help them locating it. Objective: In this project, we investigate this idea in an industrial setting. We propose a very basic semi-automated specification mining approach for debugging and apply that on real reported issues from an AutoPilot software system from our industry partner, MicroPilot Inc. The objective is to assess the feasibility and usefulness of the approach in a real-world setting. Method: The approach is developed as a prototype tool, working on C code, which accept a set of relevant state fields and functions, per issue, and generates an extended finite state machine that represents the faulty behavior, abstracted with respect to the relevant context (the selected fields and functions). Results: We qualitatively evaluate the approach by a set of interviews (including observational studies) with the company's developers on their real-world reported bugs. The results show that a) our approach is feasible, b) it can be automated to some extent, and c) brings advantages over only using their code-level debugging tools. We also compared this approach with traditional fully automated state-merging algorithms and reported several issues when applying those techniques on a real-world debugging context. Conclusion: The main conclusion of this study is that the idea of an "interactive" specification mining rather than a fully automated mining tool is NOT impractical and indeed is useful for the debugging use case.
DeepRMSA: A Deep Reinforcement Learning Framework for Routing, Modulation and Spectrum Assignment in Elastic Optical Networks
Venue: arXiv cs.NI 2019
Year: 2019

This paper proposes DeepRMSA, a deep reinforcement learning framework for routing, modulation and spectrum assignment (RMSA) in elastic optical networks (EONs). DeepRMSA learns the correct online RMSA policies by parameterizing the policies with deep neural networks (DNNs) that can sense complex EON states. The DNNs are trained with experiences of dynamic lightpath provisioning. We first modify the asynchronous advantage actor-critic algorithm and present an episode-based training mechanism for DeepRMSA, namely, DeepRMSA-EP. DeepRMSA-EP divides the dynamic provisioning process into multiple episodes (each containing the servicing of a fixed number of lightpath requests) and performs training by the end of each episode. The optimization target of DeepRMSA-EP at each step of servicing a request is to maximize the cumulative reward within the rest of the episode. Thus, we obviate the need for estimating the rewards related to unknown future states. To overcome the instability issue in the training of DeepRMSA-EP due to the oscillations of cumulative rewards, we further propose a window-based flexible training mechanism, i.e., DeepRMSA-FLX. DeepRMSA-FLX attempts to smooth out the oscillations by defining the optimization scope at each step as a sliding window, and ensuring that the cumulative rewards always include rewards from a fixed number of requests. Evaluations with the two sample topologies show that DeepRMSA-FLX can effectively stabilize the training while achieving blocking probability reductions of more than 20.3% and 14.3%, when compared with the baselines.
Hiding Data in Plain Sight: Undetectable Wireless Communications Through Pseudo-Noise Asymmetric Shift Keying
Venue: arXiv cs.CR 2019
Year: 2019

Undetectable wireless transmissions are fundamental to avoid eavesdroppers. To address this issue, wireless steganography hides covert information inside primary information by slightly modifying the transmitted waveform such that primary information will still be decodable, while covert information will be seen as noise by agnostic receivers. Since the addition of covert information inevitably decreases the SNR of the primary transmission, key challenges in wireless steganography are: i) to assess the impact of the covert channel on the primary channel as a function of different channel conditions; and ii) to make sure that the covert channel is undetectable. Existing approaches are protocol-specific, also we notice that existing wireless technologies rely on phase-keying modulations that in most cases do not use the channel up to its Shannon capacity. Therefore, the residual capacity can be leveraged to implement a wireless system based on a pseudo-noise asymmetric shift keying (PN-ASK) modulation, where covert symbols are mapped by shifting the amplitude of primary symbols. This way, covert information will be undetectable, since a receiver expecting phase-modulated symbols will see their shift in amplitude as an effect of channel/path loss degradation. We first investigate the SER of PN-ASK as a function of the channel; then, we find the optimal PN-ASK parameters that optimize primary and covert throughput under different channel condition. We evaluate the throughput performance and undetectability of PN-ASK through extensive simulations and on an experimental testbed based on USRP N210 software-defined radios. We show that PN-ASK improves the throughput by more than 8x with respect to prior art. Finally, we demonstrate through experiments that PN-ASK is able to transmit covert data on top of IEEE 802.11g frames, which are correctly decoded by an off-the-shelf laptop WiFi.
Comment on "If it's pinched it's a memristor" by L. Chua [Semicond. Sci. Technol. 29, 104001 (2014)]
Venue: arXiv cs.ET 2019
Year: 2019

In his paper "If it's pinched it's a memristor" [Semicond. Sci. Technol. 29, 104001 (2014)] L. Chua claims to extend the notion of memristor to all two-terminal resistive devices that show a hysteresis loop pinched at the origin. He also states that memcapacitors and meminductors can be defined by a trivial replacement of symbols in the memristor relations, and, therefore, there should be a correspondence between the hysteresis curves of different types of memory elements. This leads the author to the erroneous conclusion that charge-voltage curves of any memcapacitive devices should be pinched at the origin. The purpose of this Comment is to correct the wrong statements in Chua's paper, as well as to highlight some other inconsistencies in his reasoning. We also provide experimental evidence of a memcapacitive device showing non-pinched hysteresis.
Learning Algebraic Structures: Preliminary Investigations
Venue: arXiv cs.LG 2019
Year: 2019

We employ techniques of machine-learning, exemplified by support vector machines and neural classifiers, to initiate the study of whether AI can "learn" algebraic structures. Using finite groups and finite rings as a concrete playground, we find that questions such as identification of simple groups by "looking" at the Cayley table or correctly matching addition and multiplication tables for finite rings can, at least for structures of small size, be performed by the AI, even after having been trained only on small number of cases. These results are in tandem with recent investigations on whether AI can solve certain classes of problems in algebraic geometry.
CrossTrainer: Practical Domain Adaptation with Loss Reweighting
Venue: arXiv cs.LG 2019
Year: 2019

Domain adaptation provides a powerful set of model training techniques given domain-specific training data and supplemental data with unknown relevance. The techniques are useful when users need to develop models with data from varying sources, of varying quality, or from different time ranges. We build CrossTrainer, a system for practical domain adaptation. CrossTrainer utilizes loss reweighting, which provides consistently high model accuracy across a variety of datasets in our empirical analysis. However, loss reweighting is sensitive to the choice of a weight hyperparameter that is expensive to tune. We develop optimizations leveraging unique properties of loss reweighting that allow CrossTrainer to output accurate models while improving training time compared to naive hyperparameter search.
Parallel Cut Pursuit For Minimization of the Graph Total Variation
Venue: arXiv cs.DS 2019
Year: 2019

We present a parallel version of the cut-pursuit algorithm for minimizing functionals involving the graph total variation. We show that the decomposition of the iterate into constant connected components, which is at the center of this method, allows for the seamless parallelization of the otherwise costly graph-cut based refinement stage. We demonstrate experimentally the efficiency of our method in a wide variety of settings, from simple denoising on huge graphs to more complex inverse problems with nondifferentiable penalties. We argue that our approach combines the efficiency of graph-cuts based optimizers with the versatility and ease of parallelization of traditional proximal
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles
Venue: arXiv cs.DS 2019
Year: 2019

In this paper we study two geometric data structure problems in the special case when input objects or queries are fat rectangles. We show that in this case a significant improvement compared to the general case can be achieved. We describe data structures that answer two- and three-dimensional orthogonal range reporting queries in the case when the query range is a \emph{fat} rectangle. Our two-dimensional data structure uses $O(n)$ words and supports queries in $O(\log\log U +k)$ time, where $n$ is the number of points in the data structure, $U$ is the size of the universe and $k$ is the number of points in the query range. Our three-dimensional data structure needs $O(n\log^{\varepsilon}U)$ words of space and answers queries in $O(\log \log U + k)$ time. We also consider the rectangle stabbing problem on a set of three-dimensional fat rectangles. Our data structure uses $O(n)$ space and answers stabbing queries in $O(\log U\log\log U +k)$ time.
Internet Speed Measurement: Current Challenges and Future Recommendations
Venue: arXiv cs.NI 2019
Year: 2019

Government organizations, regulators, consumers, Internet service providers, and application providers alike all have an interest in measuring user Internet "speed". Access speeds have increased by an order of magnitude in past years, with gigabit speeds available to tens of millions of homes. Approaches must evolve to accurately reflect the changing user experience and network speeds. This paper offers historical and technical background on current speed testing methods, highlights their limitations as access network speeds continue to increase, and offers recommendations for the next generation of Internet "speed" measurement.
PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs
Venue: arXiv cs.DS 2019
Year: 2019

{\it SimRank} is a classic measure of the similarities of nodes in a graph. Given a node $u$ in graph $G =(V, E)$, a {\em single-source SimRank query} returns the SimRank similarities $s(u, v)$ between node $u$ and each node $v \in V$. This type of queries has numerous applications in web search and social networks analysis, such as link prediction, web mining, and spam detection. Existing methods for single-source SimRank queries, however, incur query cost at least linear to the number of nodes $n$, which renders them inapplicable for real-time and interactive analysis. { This paper proposes \prsim, an algorithm that exploits the structure of graphs to efficiently answer single-source SimRank queries. \prsim uses an index of size $O(m)$, where $m$ is the number of edges in the graph, and guarantees a query time that depends on the {\em reverse PageRank} distribution of the input graph. In particular, we prove that \prsim runs in sub-linear time if the degree distribution of the input graph follows the power-law distribution, a property possessed by many real-world graphs. Based on the theoretical analysis, we show that the empirical query time of all existing SimRank algorithms also depends on the reverse PageRank distribution of the graph.} Finally, we present the first experimental study that evaluates the absolute errors of various SimRank algorithms on large graphs, and we show that \prsim outperforms the state of the art in terms of query time, accuracy, index size, and scalability.
Adversarial Variational Embedding for Robust Semi-supervised Learning
Venue: arXiv cs.LG 2019
Year: 2019

Semi-supervised learning is sought for leveraging the unlabelled data when labelled data is difficult or expensive to acquire. Deep generative models (e.g., Variational Autoencoder (VAE)) and semisupervised Generative Adversarial Networks (GANs) have recently shown promising performance in semi-supervised classification for the excellent discriminative representing ability. However, the latent code learned by the traditional VAE is not exclusive (repeatable) for a specific input sample, which prevents it from excellent classification performance. In particular, the learned latent representation depends on a non-exclusive component which is stochastically sampled from the prior distribution. Moreover, the semi-supervised GAN models generate data from pre-defined distribution (e.g., Gaussian noises) which is independent of the input data distribution and may obstruct the convergence and is difficult to control the distribution of the generated data. To address the aforementioned issues, we propose a novel Adversarial Variational Embedding (AVAE) framework for robust and effective semi-supervised learning to leverage both the advantage of GAN as a high quality generative model and VAE as a posterior distribution learner. The proposed approach first produces an exclusive latent code by the model which we call VAE++, and meanwhile, provides a meaningful prior distribution for the generator of GAN. The proposed approach is evaluated over four different real-world applications and we show that our method outperforms the state-of-the-art models, which confirms that the combination of VAE++ and GAN can provide significant improvements in semisupervised classification.
Time-Varying Massive MIMO Channel Estimation: Capturing, Reconstruction and Restoration
Venue: arXiv cs.IT 2019
Year: 2019

On the time-varying channel estimation, the traditional downlink (DL) channel restoration schemes usually require the reconstruction for the covariance of downlink process noise vector, which is dependent on DL channel covariance matrix (CCM). However, the acquisition of the CCM leads to unacceptable overhead in massive MIMO systems. To tackle this problem, in this paper, we propose a novel scheme for the DL channel tracking. First, with the help of virtual channel representation (VCR), we build a dynamic uplink (UL) massive MIMO channel model with the consideration of off-grid refinement. Then, a coordinate-wise maximization based expectation maximization (EM) algorithm is adopted for capturing the model parameters, including the spatial signatures, the time-correlation factors, the off-grid bias, the channel power, and the noise power. Thanks to the angle reciprocity, the spatial signatures, timecorrelation factors and off-grid bias of the DL channel model can be reconstructed with the knowledge of UL ones. However, the other two kinds of model parameters are closely related with the carrier frequency, which cannot be perfectly inferred from the UL ones. Instead of relearning the DL model parameters with dedicated training, we resort to the optimal Bayesian Kalman filter (OBKF) method to accurately track the DL channel with the partially prior knowledge. At the same time, the model parameters will be gradually restored. Specially, the factor-graph and the Metropolis Hastings MCMC are utilized within the OBKF framework. Finally, numerical results are provided to demonstrate the efficiency of our proposed scheme.
Equal-Subset-Sum Faster Than the Meet-in-the-Middle
Venue: arXiv cs.DS 2019
Year: 2019

In the Equal-Subset-Sum problem, we are given a set $S$ of $n$ integers and the problem is to decide if there exist two disjoint nonempty subsets $A,B \subseteq S$, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in $O^{*}(3^{n/2}) \le O^{*}(1.7321^n)$ time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give $O^{*}(1.7088^n)$ worst case Monte Carlo algorithm. This answers the open problem from Woeginger's inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in $O^{*}(3^n)$ time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in $O^{*}(2.6817^n)$ time and polynomial space.
Greedy Signal Space Recovery Algorithm with Overcomplete Dictionaries in Compressive Sensing
Venue: arXiv cs.IT 2019
Year: 2019

Compressive Sensing (CS) is a new paradigm for the efficient acquisition of signals that have sparse representation in a certain domain. Traditionally, CS has provided numerous methods for signal recovery over an orthonormal basis. However, modern applications have sparked the emergence of related methods for signals not sparse in an orthonormal basis but in some arbitrary, perhaps highly overcomplete, dictionary, particularly due to their potential to generate different kinds of sparse representation of signals. To this end, we apply a signal space greedy method, which relies on the ability to optimally project a signal onto a small number of dictionary atoms, to address signal recovery in this setting. We describe a generalized variant of the iterative recovery algorithm called Signal space Subspace Pursuit (SSSP) for this more challenging setting. Here, using the Dictionary-Restricted Isometry Property (D-RIP) rather than classical RIP, we derive a low bound on the number of measurements required and then provide the proof of convergence for the algorithm. The algorithm in noisy and noise-free measurements has low computational complexity and provides high recovery accuracy. Simulation results show that the algorithm outperforms best compared with the existing recovery algorithms.
Self-Adjusting Linear Networks
Venue: arXiv cs.DS 2019
Year: 2019

Emerging networked systems become increasingly flexible and reconfigurable. This introduces an opportunity to adjust networked systems in a demand-aware manner, leveraging spatial and temporal locality in the workload for online optimizations. However, it also introduces a trade-off: while more frequent adjustments can improve performance, they also entail higher reconfiguration costs. This paper initiates the formal study of linear networks which self-adjust to the demand in an online manner, striking a balance between the benefits and costs of reconfigurations. We show that the underlying algorithmic problem can be seen as a distributed generalization of the classic dynamic list update problem known from self-adjusting datastructures: in a network, requests can occur between node pairs. This distributed version turns out to be significantly harder than the classical problem in generalizes. Our main results are a $Ω(\log{n})$ lower bound on the competitive ratio, and a (distributed) online algorithm that is $O(\log{n})$-competitive if the communication requests are issued according to a linear order.
Two classes of linear codes and their generalized Hamming weights
Venue: arXiv cs.IT 2019
Year: 2019

The generalized Hamming weights (GHWs) are fundamental parameters of linear codes. In this paper, we investigate the generalized Hamming weights of two classes of linear codes constructed from defining sets and determine them completely employing a number-theoretic approach.
Locality and Structure Regularized Low Rank Representation for Hyperspectral Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

Hyperspectral image (HSI) classification, which aims to assign an accurate label for hyperspectral pixels, has drawn great interest in recent years. Although low rank representation (LRR) has been used to classify HSI, its ability to segment each class from the whole HSI data has not been exploited fully yet. LRR has a good capacity to capture the underlying lowdimensional subspaces embedded in original data. However, there are still two drawbacks for LRR. First, LRR does not consider the local geometric structure within data, which makes the local correlation among neighboring data easily ignored. Second, the representation obtained by solving LRR is not discriminative enough to separate different data. In this paper, a novel locality and structure regularized low rank representation (LSLRR) model is proposed for HSI classification. To overcome the above limitations, we present locality constraint criterion (LCC) and structure preserving strategy (SPS) to improve the classical LRR. Specifically, we introduce a new distance metric, which combines both spatial and spectral features, to explore the local similarity of pixels. Thus, the global and local structures of HSI data can be exploited sufficiently. Besides, we propose a structure constraint to make the representation have a near block-diagonal structure. This helps to determine the final classification labels directly. Extensive experiments have been conducted on three popular HSI datasets. And the experimental results demonstrate that the proposed LSLRR outperforms other state-of-the-art methods.