OpenRaiser/Intern-Atlas huggingface dataset:
A Fine-Grained Perspective on Approximating Subset Sum and Partition
Venue: arXiv cs.DS 2020
Year: 2020

Approximating Subset Sum is a classic and fundamental problem in computer science and mathematical optimization. The state-of-the-art approximation scheme for Subset Sum computes a $(1-\varepsilon)$-approximation in time $\tilde{O}(\min\{n/\varepsilon, n+1/\varepsilon^2\})$ [Gens, Levner'78, Kellerer et al.'97]. In particular, a $(1-1/n)$-approximation can be computed in time $O(n^2)$. We establish a connection to Min-Plus-Convolution, a problem that is of particular interest in fine-grained complexity theory and can be solved naively in time $O(n^2)$. Our main result is that computing a $(1-1/n)$-approximation for Subset Sum is subquadratically equivalent to Min-Plus-Convolution. Thus, assuming the Min-Plus-Convolution conjecture from fine-grained complexity theory, there is no approximation scheme for Subset Sum with strongly subquadratic dependence on $n$ and $1/\varepsilon$. In the other direction, our reduction allows us to transfer known lower order improvements from Min-Plus-Convolution to Subset Sum, which yields a mildly subquadratic randomized approximation scheme. This adds the first approximation problem to the list of problems that are equivalent to Min-Plus-Convolution. For the related Partition problem, an important special case of Subset Sum, the state of the art is a randomized approximation scheme running in time $\tilde{O}(n+1/\varepsilon^{5/3})$ [Mucha~et~al.'19]. We adapt our reduction from Subset Sum to Min-Plus-Convolution to obtain a related reduction from Partition to Min-Plus-Convolution. This yields an improved approximation scheme for Partition running in time $\tilde{O}(n + 1/\varepsilon^{3/2})$. Our algorithm is the first deterministic approximation scheme for Partition that breaks the quadratic barrier.
Active Learning in Video Tracking
Venue: arXiv cs.LG 2020
Year: 2020

Active learning methods, like uncertainty sampling, combined with probabilistic prediction techniques have achieved success in various problems like image classification and text classification. For more complex multivariate prediction tasks, the relationships between labels play an important role in designing structured classifiers with better performance. However, computational time complexity limits prevalent probabilistic methods from effectively supporting active learning. Specifically, while non-probabilistic methods based on structured support vector machines can be tractably applied to predicting bipartite matchings, conditional random fields are intractable for these structures. We propose an adversarial approach for active learning with structured prediction domains that is tractable for matching. We evaluate this approach algorithmically in an important structured prediction problems: object tracking in videos. We demonstrate better accuracy and computational efficiency for our proposed method.
Scalable Online Vetting of Android Apps for Measuring Declared SDK Versions and Their Consistency with API Calls
Venue: arXiv cs.SE 2020
Year: 2020

Android has been the most popular smartphone system with multiple platform versions active in the market. To manage the application's compatibility with one or more platform versions, Android allows apps to declare the supported platform SDK versions in their manifest files. In this paper, we conduct a systematic study of this modern software mechanism. Our objective is to measure the current practice of declared SDK versions (which we term as DSDK versions afterwards) in real apps, and the (in)consistency between DSDK versions and their host apps' API calls. To successfully analyze a modern dataset of 22,687 popular apps (with an average app size of 25MB), we design a scalable approach that operates on the Android bytecode level and employs a lightweight bytecode search for app analysis. This approach achieves a good performance suitable for online vetting in app markets, requiring only around 5 seconds to process an app on average. Besides shedding light on the characteristics of DSDK in the wild, our study quantitatively measures two side effects of inappropriate DSDK versions: (i) around 35% apps under-set the minimum DSDK versions and could incur runtime crashes, but fortunately, only 11.3% apps could crash on Android 6.0 and above; (ii) around 2% apps, due to under-claiming the targeted DSDK versions, are potentially exploitable by remote code execution, and half of them invoke the vulnerable API via embedded third-party libraries. These results indicate the importance and difficulty of declaring correct DSDK, and our work can help developers fulfill this goal.
Hiding Information in Big Data based on Deep Learning
Venue: arXiv cs.CR 2020
Year: 2020

The current approach of information hiding based on deep learning model can not directly use the original data as carriers, which means the approach can not make use of the existing data in big data to hiding information. We proposed a novel method of information hiding in big data based on deep learning. Our method uses the existing data in big data as carriers and uses deep learning models to hide and extract secret messages in big data. The data amount of big data is unlimited and thus the data amount of secret messages hided in big data can also be unlimited. Before opponents want to extract secret messages from carriers, they need to find the carriers, however finding out the carriers from big data is just like finding out a box from the sea. Deep learning models are well known as deep black boxes in which the process from the input to the output is very complex, and thus the deep learning model for information hiding is almost impossible for opponents to reconstruct. The results also show that our method can hide secret messages safely, conveniently, quickly and with no limitation on the data amount.
Scalable NAS with Factorizable Architectural Parameters
Venue: arXiv cs.LG 2020
Year: 2020

Neural Architecture Search (NAS) is an emerging topic in machine learning and computer vision. The fundamental ideology of NAS is using an automatic mechanism to replace manual designs for exploring powerful network architectures. One of the key factors of NAS is to scale-up the search space, e.g., increasing the number of operators, so that more possibilities are covered, but existing search algorithms often get lost in a large number of operators. For avoiding huge computing and competition among similar operators in the same pool, this paper presents a scalable algorithm by factorizing a large set of candidate operators into smaller subspaces. As a practical example, this allows us to search for effective activation functions along with the regular operators including convolution, pooling, skip-connect, etc. With a small increase in search costs and no extra costs in re-training, we find interesting architectures that were not explored before, and achieve state-of-the-art performance on CIFAR10 and ImageNet, two standard image classification benchmarks.
Age of Information for Updates with Distortion: Constant and Age-Dependent Distortion Constraints
Venue: arXiv cs.IT 2020
Year: 2020

We consider an information update system where an information receiver requests updates from an information provider in order to minimize its age of information. The updates are generated at the information provider (transmitter) as a result of completing a set of tasks such as collecting data and performing computations. We refer to this as the update generation process. We model the $quality$ of an update as an increasing function of the processing time spent while generating the update at the transmitter. In particular, we use $distortion$ as a proxy for $quality$, and model distortion as a decreasing function of processing time. Processing longer at the transmitter results in a better quality (lower distortion) update, but it causes the update to age. We determine the age-optimal policies for the update request times at the receiver and the update processing times at the transmitter subject to a minimum required quality (maximum allowed distortion) constraint on the updates. For the required quality constraint, we consider the cases of constant maximum allowed distortion constraints, as well as age-dependent maximum allowed distortion constraints.
privGAN: Protecting GANs from membership inference attacks at low cost
Venue: arXiv cs.LG 2020
Year: 2020

Generative Adversarial Networks (GANs) have made releasing of synthetic images a viable approach to share data without releasing the original dataset. It has been shown that such synthetic data can be used for a variety of downstream tasks such as training classifiers that would otherwise require the original dataset to be shared. However, recent work has shown that the GAN models and their synthetically generated data can be used to infer the training set membership by an adversary who has access to the entire dataset and some auxiliary information. Current approaches to mitigate this problem (such as DPGAN) lead to dramatically poorer generated sample quality than the original non--private GANs. Here we develop a new GAN architecture (privGAN), where the generator is trained not only to cheat the discriminator but also to defend membership inference attacks. The new mechanism provides protection against this mode of attack while leading to negligible loss in downstream performances. In addition, our algorithm has been shown to explicitly prevent overfitting to the training set, which explains why our protection is so effective. The main contributions of this paper are: i) we propose a novel GAN architecture that can generate synthetic data in a privacy preserving manner without additional hyperparameter tuning and architecture selection, ii) we provide a theoretical understanding of the optimal solution of the privGAN loss function, iii) we demonstrate the effectiveness of our model against several white and black--box attacks on several benchmark datasets, iv) we demonstrate on three common benchmark datasets that synthetic images generated by privGAN lead to negligible loss in downstream performance when compared against non--private GANs.
Exploiting the Sensitivity of $L_2$ Adversarial Examples to Erase-and-Restore
Venue: arXiv cs.CV 2020
Year: 2020

By adding carefully crafted perturbations to input images, adversarial examples (AEs) can be generated to mislead neural-network-based image classifiers. $L_2$ adversarial perturbations by Carlini and Wagner (CW) are among the most effective but difficult-to-detect attacks. While many countermeasures against AEs have been proposed, detection of adaptive CW-$L_2$ AEs is still an open question. We find that, by randomly erasing some pixels in an $L_2$ AE and then restoring it with an inpainting technique, the AE, before and after the steps, tends to have different classification results, while a benign sample does not show this symptom. We thus propose a novel AE detection technique, Erase-and-Restore (E&R), that exploits the intriguing sensitivity of $L_2$ attacks. Experiments conducted on two popular image datasets, CIFAR-10 and ImageNet, show that the proposed technique is able to detect over 98% of $L_2$ AEs and has a very low false positive rate on benign images. The detection technique exhibits high transferability: a detection system trained using CW-$L_2$ AEs can accurately detect AEs generated using another $L_2$ attack method. More importantly, our approach demonstrates strong resilience to adaptive $L_2$ attacks, filling a critical gap in AE detection. Finally, we interpret the detection technique through both visualization and quantification.
Reinforcement Learning with Goal-Distance Gradient
Venue: arXiv cs.LG 2020
Year: 2020

Reinforcement learning usually uses the feedback rewards of environmental to train agents. But the rewards in the actual environment are sparse, and even some environments will not rewards. Most of the current methods are difficult to get good performance in sparse reward or non-reward environments. Although using shaped rewards is effective when solving sparse reward tasks, it is limited to specific problems and learning is also susceptible to local optima. We propose a model-free method that does not rely on environmental rewards to solve the problem of sparse rewards in the general environment. Our method use the minimum number of transitions between states as the distance to replace the rewards of environmental, and proposes a goal-distance gradient to achieve policy improvement. We also introduce a bridge point planning method based on the characteristics of our method to improve exploration efficiency, thereby solving more complex tasks. Experiments show that our method performs better on sparse reward and local optimal problems in complex environments than previous work.
An infinite family of linear codes supporting 4-designs
Venue: arXiv cs.IT 2020
Year: 2020

The first linear code supporting a $4$-design was the $[11, 6, 5]$ ternary Golay code discovered in 1949 by Golay. In the past 71 years, sporadic linear codes holding $4$-designs or $5$-designs were discovered and many infinite families of linear codes supporting $3$-designs were constructed. However, the question as to whether there is an infinite family of linear codes holding an infinite family of $t$-designs for $t\geq 4$ remains open for 71 years. This paper settles this long-standing problem by presenting an infinite family of BCH codes of length $2^{2m+1}+1$ over $\mathrm{GF}(2^{2m+1})$ holding an infinite family of $4$-$(2^{2m+1}+1, 6, 2^{2m}-4)$ designs. Moreover, an infinite family of linear codes holding the spherical design $S(3, 5, 4^m+1)$ is presented.
Ensemble emotion recognizing with multiple modal physiological signals
Venue: arXiv cs.LG 2020
Year: 2020

Physiological signals that provide the objective repression of human affective states are attracted increasing attention in the emotion recognition field. However, the single signal is difficult to obtain completely and accurately description for emotion. Multiple physiological signals fusing models, building the uniform classification model by means of consistent and complementary information from different emotions to improve recognition performance. Original fusing models usually choose the particular classification method to recognition, which is ignoring different distribution of multiple signals. Aiming above problems, in this work, we propose an emotion classification model through multiple modal physiological signals for different emotions. Features are extracted from EEG, EMG, EOG signals for characterizing emotional state on valence and arousal levels. For characterization, four bands filtering theta, beta, alpha, gamma for signal preprocessing are adopted and three Hjorth parameters are computing as features. To improve classification performance, an ensemble classifier is built. Experiments are conducted on the benchmark DEAP datasets. For the two-class task, the best result on arousal is 94.42\%, the best result on valence is 94.02\%, respectively. For the four-class task, the highest average classification accuracy is 90.74, and it shows good stability. The influence of different peripheral physiological signals for results is also analyzed in this paper.
Spectrum Intelligent Radio: Technology, Development, and Future Trends
Venue: arXiv cs.IT 2020
Year: 2020

The advent of Industry 4.0 with massive connectivity places significant strains on the current spectrum resources, and challenges the industry and regulators to respond promptly with new disruptive spectrum management strategies. The current radio development, with certain elements of intelligence, is nowhere near showing an agile response to the complex radio environments. Following the line of intelligence, we propose to classify spectrum intelligent radio into three streams: classical signal processing, machine learning (ML), and contextual adaptation. We focus on the ML approach, and propose a new intelligent radio architecture with three hierarchical forms: perception, understanding, and reasoning. The proposed perception method achieves fully blind multi-level spectrum sensing. The understanding method accurately predicts the primary users' coverage across a large area, and the reasoning method performs a near-optimal idle channel selection. Opportunities, challenges, and future visions are also discussed for the realization of a fully intelligent radio.
Approximating Text-to-Pattern Hamming Distances
Venue: arXiv cs.DS 2020
Year: 2020

We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n, both over an alphabet of size $σ$, compute the Hamming distance between the pattern and the text at every location. Several $(1+ε)$-approximation algorithms have been proposed in the literature, with running time of the form $O(ε^{-O(1)}n\log n\log m)$, all using fast Fourier transform (FFT). We describe a simple $(1+ε)$-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results: - We obtain the first linear-time approximation algorithm; the running time is $O(ε^{-2}n)$. - We obtain a faster exact algorithm computing all Hamming distances up to a given threshold k; its running time improves previous results by logarithmic factors and is linear if $k\le\sqrt m$. - We obtain approximation algorithms with better $ε$-dependence using rectangular matrix multiplication. The time-bound is $Õ(n)$ when the pattern is sufficiently long: $m\ge ε^{-28}$. Previous algorithms require $Õ(ε^{-1}n)$ time. - When k is not too small, we obtain a truly sublinear-time algorithm to find all locations with Hamming distance approximately (up to a constant factor) less than k, in $O((n/k^{Ω(1)}+occ)n^{o(1)})$ time, where occ is the output size. The algorithm leads to a property tester, returning true if an exact match exists and false if the Hamming distance is more than $δm$ at every location, running in $Õ(δ^{-1/3}n^{2/3}+δ^{-1}n/m)$ time. - We obtain a streaming algorithm to report all locations with Hamming distance approximately less than k, using $Õ(ε^{-2}\sqrt k)$ space. Previously, streaming algorithms were known for the exact problem with Õ(k) space or for the approximate problem with $Õ(ε^{-O(1)}\sqrt m)$ space.
Lossless Compression of Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks have been successful in many predictive modeling tasks, such as image and language recognition, where large neural networks are often used to obtain good accuracy. Consequently, it is challenging to deploy these networks under limited computational resources, such as in mobile devices. In this work, we introduce an algorithm that removes units and layers of a neural network while not changing the output that is produced, which thus implies a lossless compression. This algorithm, which we denote as LEO (Lossless Expressiveness Optimization), relies on Mixed-Integer Linear Programming (MILP) to identify Rectified Linear Units (ReLUs) with linear behavior over the input domain. By using L1 regularization to induce such behavior, we can benefit from training over a larger architecture than we would later use in the environment where the trained neural network is deployed.
Integrating Low-Power Wide-Area Networks for Enhanced Scalability and Extended Coverage
Venue: arXiv cs.NI 2020
Year: 2020

Low-Power Wide-Area Networks (LPWANs) are evolving as an enabling technology for Internet-of-Things (IoT) due to their capability of communicating over long distances at very low transmission power. Existing LPWAN technologies, however, face limitations in meeting scalability and covering very wide areas which make their adoption challenging for future IoT applications, especially in infrastructure-limited rural areas. To address this limitation, in this paper, we consider achieving scal-ability and extended coverage by integrating multiple LPWANs. SNOW (Sensor Network Over White Spaces), a recently proposed LPWAN architecture over the TV white spaces, has demonstrated its advantages over existing LPWANs in performance and energy-efficiency. In this paper, we propose to scale up LPWANs through a seamless integration of multiple SNOWs which enables concurrent inter-SNOW and intra-SNOW communications. We then formulate the tradeoff between scalability and inter-SNOW interference as a constrained optimization problem whose objective is to maximize scalability by managing white space spectrum sharing across multiple SNOWs. We also prove the NP-hardness of this problem. To this extent, We propose an intuitive polynomial-time heuristic algorithm for solving the scalability optimization problem which is highly efficient in practice. For the sake of theoretical bound, we also propose a simple polynomial-time 1/2-approximation algorithm for the scalability optimization problem. Hardware experiments through deployment in an area of (25x15)sq. km as well as large scale simulations demonstrate the effectiveness of our algorithms and feasibility of achieving scalability through seamless integration of SNOWs with high reliability, low latency, and energy efficiency.
Fast Estimation of Information Theoretic Learning Descriptors using Explicit Inner Product Spaces
Venue: arXiv cs.LG 2020
Year: 2020

Kernel methods form a theoretically-grounded, powerful and versatile framework to solve nonlinear problems in signal processing and machine learning. The standard approach relies on the \emph{kernel trick} to perform pairwise evaluations of a kernel function, leading to scalability issues for large datasets due to its linear and superlinear growth with respect to the training data. Recently, we proposed \emph{no-trick} (NT) kernel adaptive filtering (KAF) that leverages explicit feature space mappings using data-independent basis with constant complexity. The inner product defined by the feature mapping corresponds to a positive-definite finite-rank kernel that induces a finite-dimensional reproducing kernel Hilbert space (RKHS). Information theoretic learning (ITL) is a framework where information theory descriptors based on non-parametric estimator of Renyi entropy replace conventional second-order statistics for the design of adaptive systems. An RKHS for ITL defined on a space of probability density functions simplifies statistical inference for supervised or unsupervised learning. ITL criteria take into account the higher-order statistical behavior of the systems and signals as desired. However, this comes at a cost of increased computational complexity. In this paper, we extend the NT kernel concept to ITL for improved information extraction from the signal without compromising scalability. Specifically, we focus on a family of fast, scalable, and accurate estimators for ITL using explicit inner product space (EIPS) kernels. We demonstrate the superior performance of EIPS-ITL estimators and combined NT-KAF using EIPS-ITL cost functions through experiments.