OpenRaiser/Intern-Atlas huggingface dataset:
Binary Stochastic Filtering: a Method for Neural Network Size Minimization and Supervised Feature Selection
Venue: arXiv cs.LG 2019
Year: 2019

Binary Stochastic Filtering (BSF), the algorithm for feature selection and neuron pruning is proposed in this work. The method defines filtering layer which penalizes amount of the information involved in the training process. This information could be the input data or output of the previous layer, which directly leads to the feature selection or neuron pruning respectively, producing \textit{ad hoc} subset of features or selecting optimal number of neurons in each layer. Filtering layer stochastically passes or drops features based on individual weights, which are tuned with standard backpropagation algorithm during the training process. Multifold decrease of neural network size has been achieved in the experiments. Besides, the method was able to select minimal number of features, surpassing literature references by the accuracy/dimensionality ratio.
Throughput-Outage Analysis and Evaluation of Cache-Aided D2D Networks with Measured Popularity Distributions
Venue: arXiv cs.IT 2019
Year: 2019

Caching of video files on user devices, combined with file exchange through device-to-device (D2D) communications is a promising method for increasing the throughput of wireless networks. Previous theoretical investigations showed that throughput can be increased by orders of magnitude, but assumed a Zipf distribution for modeling the popularity distribution, which was based on observations in {\em wired} networks. Thus the question whether cache-aided D2D video distribution can provide in practice the benefits promised by existing theoretical literature remains open. To answer this question, we provide new results specifically for popularity distributions of video requests of mobile users. Based on an extensive real-world dataset, we adopt a generalized distribution, known as Mandelbrot-Zipf (MZipf) distribution. We first show that this popularity distribution can fit the practical data well. Using this distribution, we analyze the throughput--outage tradeoff of the cache-aided D2D network and show that the scaling law is identical to the case of Zipf popularity distribution when the MZipf distribution is sufficiently skewed, implying that the benefits previously promised in the literature could indeed be realized in practice. To support the theory, practical evaluations using numerical experiments are provided, and show that the cache-aided D2D can outperform the conventional unicasting from base stations.
Spectra of networks containing short loops
Venue: arXiv cs.SI 2019
Year: 2019

The spectrum of the adjacency matrix plays several important roles in the mathematical theory of networks and in network data analysis, for example in percolation theory, community detection, centrality measures, and the theory of dynamical systems on networks. A number of methods have been developed for the analytic computation of network spectra, but they typically assume that networks are locally tree-like, meaning that the local neighborhood of any node takes the form of a tree, free of short loops. Empirically observed networks, by contrast, often have many short loops. Here we develop an approach for calculating the spectra of networks with short loops using a message passing method. We give example applications to some previously studied classes of networks.
Inequalities and Approximations for Fisher Information in the Presence of Nuisance Parameters
Venue: arXiv cs.IT 2019
Year: 2019

Many imaging systems are used to estimate a vector of parameters associated with the object being imaged. In many cases there are other parameters in the model for the imaging data that are not of interest for the task at hand. We refer to these as nuisance parameters and use them to form the components of the nuisance parameter vector. If we have a prior probability distribution function (PDF) for the nuisance parameter vector, then we may mariginalize over the nuisance parameters to produce a conditional PDF for the data that only depends on the parameters of interest. We will examine this approach to develop inequalities and approximations for the FIM when the data is affected by nuisance parameters.
Salus: Fine-Grained GPU Sharing Primitives for Deep Learning Applications
Venue: arXiv cs.DC 2019
Year: 2019

GPU computing is becoming increasingly more popular with the proliferation of deep learning (DL) applications. However, unlike traditional resources such as CPU or the network, modern GPUs do not natively support fine-grained sharing primitives. Consequently, implementing common policies such as time sharing and preemption are expensive. Worse, when a DL application cannot completely use a GPU's resources, the GPU cannot be efficiently shared between multiple applications, leading to GPU underutilization. We present Salus to enable two GPU sharing primitives: fast job switching and memory sharing, in order to achieve fine-grained GPU sharing among multiple DL applications. Salus implements an efficient, consolidated execution service that exposes the GPU to different DL applications, and enforces fine-grained sharing by performing iteration scheduling and addressing associated memory management issues. We show that these primitives can then be used to implement flexible sharing policies such as fairness, prioritization, and packing for various use cases. Our integration of Salus with TensorFlow and evaluation on popular DL jobs show that Salus can improve the average completion time of DL training jobs by $3.19\times$, GPU utilization for hyper-parameter tuning by $2.38\times$, and GPU utilization of DL inference applications by $42\times$ over not sharing the GPU and $7\times$ over NVIDIA MPS with small overhead.
Learning Theory and Support Vector Machines - a primer
Venue: arXiv cs.LG 2019
Year: 2019

The main goal of statistical learning theory is to provide a fundamental framework for the problem of decision making and model construction based on sets of data. Here, we present a brief introduction to the fundamentals of statistical learning theory, in particular the difference between empirical and structural risk minimization, including one of its most prominent implementations, i.e. the Support Vector Machine.
Crowdsourced PAC Learning under Classification Noise
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we analyze PAC learnability from labels produced by crowdsourcing. In our setting, unlabeled examples are drawn from a distribution and labels are crowdsourced from workers who operate under classification noise, each with their own noise parameter. We develop an end-to-end crowdsourced PAC learning algorithm that takes unlabeled data points as input and outputs a trained classifier. Our three-step algorithm incorporates majority voting, pure-exploration bandits, and noisy-PAC learning. We prove several guarantees on the number of tasks labeled by workers for PAC learning in this setting and show that our algorithm improves upon the baseline by reducing the total number of tasks given to workers. We demonstrate the robustness of our algorithm by exploring its application to additional realistic crowdsourcing settings.
A Case for Superconducting Accelerators
Venue: arXiv cs.AR 2019
Year: 2019

As the scaling of conventional CMOS-based technologies slows down, there is growing interest in alternative technologies that can improve performance or energy-efficiency. Superconducting circuits based on Josephson Junction (JJ) is an emerging technology that can provide devices which can be switched with pico-second latencies and consuming two orders of magnitude lower switching energy compared to CMOS. While JJ-based circuits can provide high operating frequency and energy-efficiency, this technology faces three critical challenges: limited device density and lack of area-efficient technology for memory structures, reduced gate fanout compared to CMOS, and new failure modes of Flux-Traps that occurs due to the operating environment. The lack of dense memory technology restricts the use of superconducting technology in the near term to application domains that have high compute intensity but require negligible amount of memory. In this paper, we study the use of superconducting technology to build an accelerator for SHA-256 engines commonly used in Bitcoin mining applications. We show that merely porting existing CMOS-based accelerator to superconducting technology provides 10.6X improvement in energy efficiency. Redesigning the accelerator to suit the unique constraints of superconducting technology (such as low fanout) improves the energy efficiency to 12.2X. We also investigate solutions to make the accelerator tolerant of new fault modes and show how this fault-tolerant design can be leveraged to reduce the operating current, thereby increasing the overall energy-efficiency to 46X compared to CMOS. Our paper also develops a workflow for evaluating area, performance, and power for accelerators built in superconducting technology, and this workflow can help other researchers explore designs using this technology.
Seamless Rate Adaptation at Receiver Side for Indoor Visible Light Communications by Using Raptor Codes
Venue: arXiv cs.IT 2019
Year: 2019

Visible light communication (VLC), which uses LEDs for both illumination and communication purposes, has recently emerged as either an alternative or a support system for radio frequency (RF) communication. VLC channel inside a room is highly variable since it is pretty much depends on optical line of sight (LOS) and field of view (FOV) and it causes the received signal to vary dramatically. Therefore, to achieve spectral efficient communication, using rate adaptation methods are essential. In this study, we propose a rateless codes based rate adaptation method which adjusts transmission rate at receiver side and does not require channel state information (CSI) at the transmitter side. Spectral efficiency of proposed method is analyzed and compared with adaptive modulation and coding (AMC) rate adaptation method widely used in literature. For simulation work, we consider a realistic communication system model by using commercially available LEDs and also fulfilling illumination requirements. To overcome multi-path effects, optical orthogonal frequency-division multiplexing (OFDM) is used. Simulation results indicate that proposed rate adaptive method can achieve seamless rate adaptation and has higher spectral efficiency compared to AMC in presence of significant signal quality variations caused by mobility in a model room.
A Privacy-Preserving Traffic Monitoring Scheme via Vehicular Crowdsourcing
Venue: arXiv cs.CR 2019
Year: 2019

The explosive growth of vehicle amount has given rise to a series of traffic problems, such as traffic congestion, road safety, and fuel waste. Collecting vehicles' speed information is an effective way to monitor the traffic condition and avoid vehicles being congested, which however may bring threats to vehicles' location and trajectory privacy. Motivated by the fact that traffic monitoring does not need to know each individual vehicle's speed and the average speed would be sufficient, we propose a privacy-preserving traffic monitoring (PPTM) scheme to aggregate vehicles' speeds at different locations. In PPTM, the roadside unit (RSU) collects vehicles' speed information at multiple road segments, and further cooperates with a service provider to calculate the average speed information for every road segment. To preserve vehicles' privacy, both homomorphic Paillier cryptosystem and super-increasing sequence are adopted. A comprehensive security analysis indicates that the proposed PPTM can preserve vehicles' identities, speeds, locations, and trajectories privacy from being disclosed. In addition, extensive simulations are conducted to validate the effectiveness and efficiency of the proposed PPTM scheme.
Evaluating Reputation Management Schemes of Internet of Vehicles based on Evolutionary Game Theory
Venue: arXiv cs.GT 2019
Year: 2019

Conducting reputation management is very important for Internet of vehicles. However, most of the existing researches evaluate the effectiveness of their schemes with settled attacking behaviors in their simulation which cannot represent the scenarios in reality. In this paper, we propose to consider dynamical and diversity attacking strategies in the simulation of reputation management scheme evaluation. To that end, we apply evolutionary game theory to model the evolution process of malicious users' attacking strategies, and discuss the methodology of the evaluation simulations. We further apply our evaluation method to a reputation management scheme with multiple utility functions, and discuss the evaluation results. The results indicate that our evaluation method is able to depict the evolving process of the dynamic attacking strategies in a vehicular network, and the final state of the simulation could be used to quantify the protection effectiveness of the reputation management scheme.
Analysis of Baseline Evolutionary Algorithms for the Packing While Travelling Problem
Venue: arXiv cs.NE 2019
Year: 2019

The performance of base-line Evolutionary Algorithms (EAs) on combinatorial problems has been studied rigorously. From the theoretical viewpoint, the literature extensively investigates the linear problems, while the theoretical analysis of the non-linear problems is still far behind. In this paper, variations of the Packing While Travelling (PWT) -- also known as the non-linear knapsack problem -- are studied as an attempt to analyse the behaviour of EAs on non-linear problems from theoretical perspective. We investigate PWT for two cities and $n$ items with correlated weights and profits, using single-objective and multi-objective algorithms. Our results show that RLS\_swap, which differs from the classical RLS by having the ability to swap two bits in one iteration, finds the optimal solution in $O(n^3)$ expected time. We also study an enhanced version of GSEMO, which a specific selection operator to deal with exponential population size, and prove that it finds the Pareto front in the same asymptotic expected time. In the case of uniform weights, (1+1)~EA is able to find the optimal solution in expected time $O(n^2\log{(\max\{n,p_{\max}\})})$, where $p_{\max}$ is the largest profit of the given items. We also perform an experimental analysis to complement our theoretical investigations and provide additional insights into the runtime behavior.
Assessing Solution Quality of 3SAT on a Quantum Annealing Platform
Venue: arXiv cs.ET 2019
Year: 2019

When solving propositional logic satisfiability (specifically 3SAT) using quantum annealing, we analyze the effect the difficulty of different instances of the problem has on the quality of the answer returned by the quantum annealer. A high-quality response from the annealer in this case is defined by a high percentage of correct solutions among the returned answers. We show that the phase transition regarding the computational complexity of the problem, which is well-known to occur for 3SAT on classical machines (where it causes a detrimental increase in runtime), persists in some form (but possibly to a lesser extent) for quantum annealing.
Learning Ising Models with Independent Failures
Venue: arXiv cs.DS 2019
Year: 2019

We give the first efficient algorithm for learning the structure of an Ising model that tolerates independent failures; that is, each entry of the observed sample is missing with some unknown probability p. Our algorithm matches the essentially optimal runtime and sample complexity bounds of recent work for learning Ising models due to Klivans and Meka (2017). We devise a novel unbiased estimator for the gradient of the Interaction Screening Objective (ISO) due to Vuffray et al. (2016) and apply a stochastic multiplicative gradient descent algorithm to minimize this objective. Solutions to this minimization recover the neighborhood information of the underlying Ising model on a node by node basis.
Efficient Cross-Validation for Semi-Supervised Learning
Venue: arXiv cs.LG 2019
Year: 2019

Manifold regularization, such as laplacian regularized least squares (LapRLS) and laplacian support vector machine (LapSVM), has been widely used in semi-supervised learning, and its performance greatly depends on the choice of some hyper-parameters. Cross-validation (CV) is the most popular approach for selecting the optimal hyper-parameters, but it has high complexity due to multiple times of learner training. In this paper, we provide a method to approximate the CV for manifold regularization based on a notion of robust statistics, called Bouligand influence function (BIF). We first provide a strategy for approximating the CV via the Taylor expansion of BIF. Then, we show how to calculate the BIF for general loss function,and further give the approximate CV criteria for model selection in manifold regularization. The proposed approximate CV for manifold regularization requires training only once, hence can significantly improve the efficiency of traditional CV. Experimental results show that our approximate CV has no statistical discrepancy with the original one, but much smaller time cost.
On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
Venue: arXiv cs.LG 2019
Year: 2019

Gradient descent (GD) and stochastic gradient descent (SGD) are the workhorses of large-scale machine learning. While classical theory focused on analyzing the performance of these methods in convex optimization problems, the most notable successes in machine learning have involved nonconvex optimization, and a gap has arisen between theory and practice. Indeed, traditional analyses of GD and SGD show that both algorithms converge to stationary points efficiently. But these analyses do not take into account the possibility of converging to saddle points. More recent theory has shown that GD and SGD can avoid saddle points, but the dependence on dimension in these analyses is polynomial. For modern machine learning, where the dimension can be in the millions, such dependence would be catastrophic. We analyze perturbed versions of GD and SGD and show that they are truly efficient---their dimension dependence is only polylogarithmic. Indeed, these algorithms converge to second-order stationary points in essentially the same time as they take to converge to classical first-order stationary points.
Classifying Signals on Irregular Domains via Convolutional Cluster Pooling
Venue: arXiv cs.LG 2019
Year: 2019

We present a novel and hierarchical approach for supervised classification of signals spanning over a fixed graph, reflecting shared properties of the dataset. To this end, we introduce a Convolutional Cluster Pooling layer exploiting a multi-scale clustering in order to highlight, at different resolutions, locally connected regions on the input graph. Our proposal generalises well-established neural models such as Convolutional Neural Networks (CNNs) on irregular and complex domains, by means of the exploitation of the weight sharing property in a graph-oriented architecture. In this work, such property is based on the centrality of each vertex within its soft-assigned cluster. Extensive experiments on NTU RGB+D, CIFAR-10 and 20NEWS demonstrate the effectiveness of the proposed technique in capturing both local and global patterns in graph-structured data out of different domains.
Person Re-identification in Videos by Analyzing Spatio-Temporal Tubes
Venue: arXiv cs.CV 2019
Year: 2019

Typical person re-identification frameworks search for k best matches in a gallery of images that are often collected in varying conditions. The gallery may contain image sequences when re-identification is done on videos. However, such a process is time consuming as re-identification has to be carried out multiple times. In this paper, we extract spatio-temporal sequences of frames (referred to as tubes) of moving persons and apply a multi-stage processing to match a given query tube with a gallery of stored tubes recorded through other cameras. Initially, we apply a binary classifier to remove noisy images from the input query tube. In the next step, we use a key-pose detection-based query minimization. This reduces the length of the query tube by removing redundant frames. Finally, a 3-stage hierarchical re-identification framework is used to rank the output tubes as per the matching scores. Experiments with publicly available video re-identification datasets reveal that our framework is better than state-of-the-art methods. It ranks the tubes with an increased CMC accuracy of 6-8% across multiple datasets. Also, our method significantly reduces the number of false positives. A new video re-identification dataset, named Tube-based Reidentification Video Dataset (TRiViD), has been prepared with an aim to help the re-identification research community
Development of Video Frame Enhancement Technique Using Pixel Intensity Analysis
Venue: arXiv cs.MM 2019
Year: 2019

This paper developed a brightness enhancement technique for video frame pixel intensity improvement. Frames extracted from the six sample video data used in this work were stored in the form of images in a buffer. Noise was added to the extracted image frames to vary the intensity of their pixels so that the pixel values of the noisy images differ from their true values in order to determine the efficiency of the developed technique. Simulation results showed that, the developed technique was efficient with an improved pixel intensity and histogram distribution. The Peak to Signal Noise Ratio evaluation showed that the efficiency of the developed technique for both grayscale and coloured video frames were improved by PSNR of 12.45%, 16.32%, 27.57% and 19.83% over the grey level colour (black and white) for the NAELS1.avi, NAELS2.avi, NTA1.avi and NTA2.avi respectively. Also, a percentage improvement of 28.93% and 31.68% were obtained for the coloured image over the grey level image for Akiyo.avi and Forman.avi benchmark video frame, respectively.
3D Robot Pose Estimation from 2D Images
Venue: arXiv cs.CV 2019
Year: 2019

This paper considers the task of locating articulated poses of multiple robots in images. Our approach simultaneously infers the number of robots in a scene, identifies joint locations and estimates sparse depth maps around joint locations. The proposed method applies staged convolutional feature detectors to 2D image inputs and computes robot instance masks using a recurrent network architecture. In addition, regression maps of most likely joint locations in pixel coordinates together with depth information are computed. Compositing 3D robot joint kinematics is accomplished by applying masks to joint readout maps. Our end-to-end formulation is in contrast to previous work in which the composition of robot joints into kinematics is performed in a separate post-processing step. Despite the fact that our models are trained on artificial data, we demonstrate generalizability to real world images.