OpenRaiser/Intern-Atlas huggingface dataset:
Generalization and Expressivity for Deep Nets
Venue: arXiv cs.LG 2018
Year: 2018

Along with the rapid development of deep learning in practice, the theoretical explanations for its success become urgent. Generalization and expressivity are two widely used measurements to quantify theoretical behaviors of deep learning. The expressivity focuses on finding functions expressible by deep nets but cannot be approximated by shallow nets with the similar number of neurons. It usually implies the large capacity. The generalization aims at deriving fast learning rate for deep nets. It usually requires small capacity to reduce the variance. Different from previous studies on deep learning, pursuing either expressivity or generalization, we take both factors into account to explore the theoretical advantages of deep nets. For this purpose, we construct a deep net with two hidden layers possessing excellent expressivity in terms of localized and sparse approximation. Then, utilizing the well known covering number to measure the capacity, we find that deep nets possess excellent expressive power (measured by localized and sparse approximation) without enlarging the capacity of shallow nets. As a consequence, we derive near optimal learning rates for implementing empirical risk minimization (ERM) on the constructed deep nets. These results theoretically exhibit the advantage of deep nets from learning theory viewpoints.
Energy and Delay Optimization for Cache-Enabled Dense Small Cell Networks
Venue: arXiv cs.NI 2018
Year: 2018

Caching popular files in small base stations (SBSs) has been proved to be an effective way to reduce bandwidth pressure on the backhaul links of dense small cell networks (DSCNs). Many existing studies on cache-enabled DSCNs attempt to improve user experience by optimizing end-to-end file delivery delay. However, under practical scenarios where files (e.g., video files) have diverse quality of service requirements, energy consumption at SBSs should also be concerned from the network perspective. In this paper,we attempt to optimize these two critical metrics in cache-enabled DSCNs. Firstly, we formulate the energy-delay optimization problem as a Mixed Integer Programming (MIP) problem, where file placement, user association and power control are jointly considered. To model the tradeoff relationship between energy consumption and end-to-end file delivery delay, a utility function linearly combining these two metrics is used as an objective function of the optimization problem. Then, we solve the problem in two stages, i.e. caching stage and delivery stage, based on the observation that caching is performed during off-peak time. At the caching stage, a local popular file placement policy is proposed by estimating user preference at each SBS. At the delivery stage, with given caching status at SBSs, the MIP problem is further decomposed by Benders' decomposition method. An efficient algorithm is proposed to approach the optimal association and power solution by iteratively shrinking the gap of the upper and lower bounds. Finally, extension simulations are performed to validate our analytical and algorithmic work. The results demonstrate that the proposed algorithms can achieve the optimal tradeoff between energy consumption and end-to-end file delivery delay.
Learning and analyzing vector encoding of symbolic representations
Venue: arXiv cs.AI 2018
Year: 2018

We present a formal language with expressions denoting general symbol structures and queries which access information in those structures. A sequence-to-sequence network processing this language learns to encode symbol structures and query them. The learned representation (approximately) shares a simple linearity property with theoretical techniques for performing this task.
Sample-Relaxed Two-Dimensional Color Principal Component Analysis for Face Recognition and Image Reconstruction
Venue: arXiv cs.CV 2018
Year: 2018

A sample-relaxed two-dimensional color principal component analysis (SR-2DCPCA) approach is presented for face recognition and image reconstruction based on quaternion models. A relaxation vector is automatically generated according to the variances of training color face images with the same label. A sample-relaxed, low-dimensional covariance matrix is constructed based on all the training samples relaxed by a relaxation vector, and its eigenvectors corresponding to the $r$ largest eigenvalues are defined as the optimal projection. The SR-2DCPCA aims to enlarge the global variance rather than to maximize the variance of the projected training samples. The numerical results based on real face data sets validate that SR-2DCPCA has a higher recognition rate than state-of-the-art methods and is efficient in image reconstruction.
Efficient Enumeration of Bipartite Subgraphs in Graphs
Venue: arXiv cs.DS 2018
Year: 2018

Subgraph enumeration problems ask to output all subgraphs of an input graph that belongs to the specified graph class or satisfy the given constraint. These problems have been widely studied in theoretical computer science. As far, many efficient enumeration algorithms for the fundamental substructures such as spanning trees, cycles, and paths, have been developed. This paper addresses the enumeration problem of bipartite subgraphs. Even though bipartite graphs are quite fundamental and have numerous applications in both theory and application, its enumeration algorithms have not been intensively studied, to the best of our knowledge. We propose the first non-trivial algorithms for enumerating all bipartite subgraphs in a given graph. As the main results, we develop two efficient algorithms: the one enumerates all bipartite induced subgraphs of a graph with degeneracy $k$ in $O(k)$ time per solution. The other enumerates all bipartite subgraphs in $O(1)$ time per solution.
A Deep Learning Approach for Pose Estimation from Volumetric OCT Data
Venue: arXiv cs.CV 2018
Year: 2018

Tracking the pose of instruments is a central problem in image-guided surgery. For microscopic scenarios, optical coherence tomography (OCT) is increasingly used as an imaging modality. OCT is suitable for accurate pose estimation due to its micrometer range resolution and volumetric field of view. However, OCT image processing is challenging due to speckle noise and reflection artifacts in addition to the images' 3D nature. We address pose estimation from OCT volume data with a new deep learning-based tracking framework. For this purpose, we design a new 3D convolutional neural network (CNN) architecture to directly predict the 6D pose of a small marker geometry from OCT volumes. We use a hexapod robot to automatically acquire labeled data points which we use to train 3D CNN architectures for multi-output regression. We use this setup to provide an in-depth analysis on deep learning-based pose estimation from volumes. Specifically, we demonstrate that exploiting volume information for pose estimation yields higher accuracy than relying on 2D representations with depth information. Supporting this observation, we provide quantitative and qualitative results that 3D CNNs effectively exploit the depth structure of marker objects. Regarding the deep learning aspect, we present efficient design principles for 3D CNNs, making use of insights from the 2D deep learning community. In particular, we present Inception3D as a new architecture which performs best for our application. We show that our deep learning approach reaches errors at our ground-truth label's resolution. We achieve a mean average error of $\SI{14.89 \pm 9.3}{\micro\metre}$ and $\SI{0.096 \pm 0.072}{\degree}$ for position and orientation learning, respectively.
Deep reinforcement learning for time series: playing idealized trading games
Venue: arXiv cs.LG 2018
Year: 2018

Deep Q-learning is investigated as an end-to-end solution to estimate the optimal strategies for acting on time series input. Experiments are conducted on two idealized trading games. 1) Univariate: the only input is a wave-like price time series, and 2) Bivariate: the input includes a random stepwise price time series and a noisy signal time series, which is positively correlated with future price changes. The Univariate game tests whether the agent can capture the underlying dynamics, and the Bivariate game tests whether the agent can utilize the hidden relation among the inputs. Stacked Gated Recurrent Unit (GRU), Long Short-Term Memory (LSTM) units, Convolutional Neural Network (CNN), and multi-layer perceptron (MLP) are used to model Q values. For both games, all agents successfully find a profitable strategy. The GRU-based agents show best overall performance in the Univariate game, while the MLP-based agents outperform others in the Bivariate game.
Scalable Breadth-First Search on a GPU Cluster
Venue: arXiv cs.DC 2018
Year: 2018

On a GPU cluster, the ratio of high computing power to communication bandwidth makes scaling breadth-first search (BFS) on a scale-free graph extremely challenging. By separating high and low out-degree vertices, we present an implementation with scalable computation and a model for scalable communication for BFS and direction-optimized BFS. Our communication model uses global reduction for high-degree vertices, and point-to-point transmission for low-degree vertices. Leveraging the characteristics of degree separation, we reduce the graph size to one third of the conventional edge list representation. With several other optimizations, we observe linear weak scaling as we increase the number of GPUs, and achieve 259.8 GTEPS on a scale-33 Graph500 RMAT graph with 124 GPUs on the latest CORAL early access system.
BEBP: An Poisoning Method Against Machine Learning Based IDSs
Venue: arXiv cs.LG 2018
Year: 2018

In big data era, machine learning is one of fundamental techniques in intrusion detection systems (IDSs). However, practical IDSs generally update their decision module by feeding new data then retraining learning models in a periodical way. Hence, some attacks that comprise the data for training or testing classifiers significantly challenge the detecting capability of machine learning-based IDSs. Poisoning attack, which is one of the most recognized security threats towards machine learning-based IDSs, injects some adversarial samples into the training phase, inducing data drifting of training data and a significant performance decrease of target IDSs over testing data. In this paper, we adopt the Edge Pattern Detection (EPD) algorithm to design a novel poisoning method that attack against several machine learning algorithms used in IDSs. Specifically, we propose a boundary pattern detection algorithm to efficiently generate the points that are near to abnormal data but considered to be normal ones by current classifiers. Then, we introduce a Batch-EPD Boundary Pattern (BEBP) detection algorithm to overcome the limitation of the number of edge pattern points generated by EPD and to obtain more useful adversarial samples. Based on BEBP, we further present a moderate but effective poisoning method called chronic poisoning attack. Extensive experiments on synthetic and three real network data sets demonstrate the performance of the proposed poisoning method against several well-known machine learning algorithms and a practical intrusion detection method named FMIFS-LSSVM-IDS.
Combinatorial Multi-Objective Multi-Armed Bandit Problem
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we introduce the COmbinatorial Multi-Objective Multi-Armed Bandit (COMO-MAB) problem that captures the challenges of combinatorial and multi-objective online learning simultaneously. In this setting, the goal of the learner is to choose an action at each time, whose reward vector is a linear combination of the reward vectors of the arms in the action, to learn the set of super Pareto optimal actions, which includes the Pareto optimal actions and actions that become Pareto optimal after adding an arbitrary small positive number to their expected reward vectors. We define the Pareto regret performance metric and propose a fair learning algorithm whose Pareto regret is $O(N L^3 \log T)$, where $T$ is the time horizon, $N$ is the number of arms and $L$ is the maximum number of arms in an action. We show that COMO-MAB has a wide range of applications, including recommending bundles of items to users and network routing, and focus on a resource-allocation application for multi-user communication in the presence of multidimensional performance metrics, where we show that our algorithm outperforms existing MAB algorithms.
Two-Stage Convolutional Neural Network for Breast Cancer Histology Image Classification
Venue: arXiv cs.CV 2018
Year: 2018

This paper explores the problem of breast tissue classification of microscopy images. Based on the predominant cancer type the goal is to classify images into four categories of normal, benign, in situ carcinoma, and invasive carcinoma. Given a suitable training dataset, we utilize deep learning techniques to address the classification problem. Due to the large size of each image in the training dataset, we propose a patch-based technique which consists of two consecutive convolutional neural networks. The first "patch-wise" network acts as an auto-encoder that extracts the most salient features of image patches while the second "image-wise" network performs classification of the whole image. The first network is pre-trained and aimed at extracting local information while the second network obtains global information of an input image. We trained the networks using the ICIAR 2018 grand challenge on BreAst Cancer Histology (BACH) dataset. The proposed method yields 95 % accuracy on the validation set compared to previously reported 77 % accuracy rates in the literature. Our code is publicly available at https://github.com/ImagingLab/ICIAR2018
Development of a culturally-oriented website usability evaluation
Venue: arXiv cs.HC 2018
Year: 2018

As the uni-cultural studies of website usability have matured, the paucity of cross-cultural studies of usability become increasingly apparent. Moving toward these cross-cultural studies will require the development of a new tool to assess website usability in the context of cultural dimensions. This paper introduces the preliminary results from the first phase of this project and then presents the proposed method for the research in progress that specifically is directed to the development and quantitative evaluation of a measurement scale of a culture sensitive measurement of website usability. The recognition of the need to develop this scale resulted from the identification of culture-related shortcomings of previous measurement tools that have been used widely within the Management of Information Systems (MIS) literature.
A Modular Design for Geo-Distributed Querying
Venue: arXiv cs.DC 2018
Year: 2018

Most distributed storage systems provide limited abilities for querying data by attributes other than their primary keys. Supporting efficient search on secondary attributes is challenging as applications pose varying requirements to query processing systems, and no single system design can be suitable for all needs. In this paper, we show how to overcome these challenges in order to extend distributed data stores to support queries on secondary attributes. We propose a modular architecture that is flexible and allows query processing systems to make trade-offs according to different use case requirements. We describe adap-tive mechanisms that make use of this flexibility to enable query processing systems to dynamically adjust to query and write operation workloads.
Entanglement-assisted quantum MDS codes from constacyclic codes with large minimum distance
Venue: arXiv cs.IT 2018
Year: 2018

The entanglement-assisted (EA) formalism allows arbitrary classical linear codes to transform into entanglement-assisted quantum error correcting codes (EAQECCs) by using pre-shared entanglement between the sender and the receiver. In this work, we propose a decomposition of the defining set of constacyclic codes. Using this method, we construct four classes of $q$-ary entanglement-assisted quantum MDS (EAQMDS) codes based on classical constacyclic MDS codes by exploiting less pre-shared maximally entangled states. We show that a class of $q$-ary EAQMDS have minimum distance upper limit greater than $3q-1$. Some of them have much larger minimum distance than the known quantum MDS (QMDS) codes of the same length. Most of these $q$-ary EAQMDS codes are new in the sense that their parameters are not covered by the codes available in the literature.
High Throughput Synchronous Distributed Stochastic Gradient Descent
Venue: arXiv cs.DC 2018
Year: 2018

We introduce a new, high-throughput, synchronous, distributed, data-parallel, stochastic-gradient-descent learning algorithm. This algorithm uses amortized inference in a compute-cluster-specific, deep, generative, dynamical model to perform joint posterior predictive inference of the mini-batch gradient computation times of all worker-nodes in a parallel computing cluster. We show that a synchronous parameter server can, by utilizing such a model, choose an optimal cutoff time beyond which mini-batch gradient messages from slow workers are ignored that maximizes overall mini-batch gradient computations per second. In keeping with earlier findings we observe that, under realistic conditions, eagerly discarding the mini-batch gradient computations of stragglers not only increases throughput but actually increases the overall rate of convergence as a function of wall-clock time by virtue of eliminating idleness. The principal novel contribution and finding of this work goes beyond this by demonstrating that using the predicted run-times from a generative model of cluster worker performance to dynamically adjust the cutoff improves substantially over the static-cutoff prior art, leading to, among other things, significantly reduced deep neural net training times on large computer clusters.
FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees
Venue: arXiv cs.LG 2018
Year: 2018

Recent DNN pruning algorithms have succeeded in reducing the number of parameters in fully connected layers, often with little or no drop in classification accuracy. However, most of the existing pruning schemes either have to be applied during training or require a costly retraining procedure after pruning to regain classification accuracy. We start by proposing a cheap pruning algorithm for fully connected DNN layers based on difference of convex functions (DC) optimisation, that requires little or no retraining. We then provide a theoretical analysis for the growth in the Generalization Error (GE) of a DNN for the case of bounded perturbations to the hidden layers, of which weight pruning is a special case. Our pruning method is orders of magnitude faster than competing approaches, while our theoretical analysis sheds light to previously observed problems in DNN pruning. Experiments on commnon feedforward neural networks validate our results.
Comparison of Limited Feedback Schemes for NOMA Transmission in mmWave Drone Networks
Venue: arXiv cs.IT 2018
Year: 2018

Introducing non-orthogonal multiple access (NOMA) transmission to an unmanned aerial vehicle (UAV) based communication network is a promising solution to enhance its spectral efficiency. However, for realistic deployment of such a network, identifying a practical user feedback scheme for NOMA is essential. In this paper, considering two practical feedback schemes we introduce NOMA transmission to UAVs acting as aerial base stations (BS) to provide coverage at a large stadium. In particular, a UAV-BS generates directional beams, and multiple users are served simultaneously within the same beam employing NOMA transmission. Each user is considered to have a target rate based on its quality of service (QoS) requirements. In order to relieve the burden of tracking and feeding back full channel state information, we consider two limited feedback schemes as practical alternatives: 1) user distance, and 2) user angle with respect to beamforming direction under different user region geometries. Our evaluation results show that NOMA with limited feedback can provide better sum rates compared to its orthogonal counterpart. Further, based on the geometry of user region we identify that there is an optimal feedback scheme and user ordering criteria for NOMA transmission which can maximize sum rates.
SDPMN: Privacy Preserving MapReduce Network Using SDN
Venue: arXiv cs.DC 2018
Year: 2018

MapReduce is a popular programming model and an associated implementation for parallel processing big data in the distributed environment. Since large scaled MapReduce data centers usually provide services to many users, it is an essential problem to preserve the privacy between different applications in the same network. In this paper, we propose SDPMN, a framework that using \textit{software defined network} (SDN) to distinguish the network between each application, which is a manageable and scalable method. We design this framework based on the existing SDN structure and Hadoop networks. Since the rule space of each SDN device is limited, we also propose the rule placement optimization for this framework to maximize the hardware supported isolated application networks. We state this problem in a general MapReduce network and design a heuristic algorithm to find the solution. From the simulation based evaluation, with our algorithm, the given network can support more privacy preserving application networks with SDN switches.
Geodabs: Trajectory Indexing Meets Fingerprinting at Scale
Venue: arXiv cs.DS 2018
Year: 2018

Finding trajectories and discovering motifs that are similar in large datasets is a central problem for a wide range of applications. Solutions addressing this problem usually rely on spatial indexing and on the computation of a similarity measure in polynomial time. Although effective in the context of sparse trajectory datasets, this approach is too expensive in the context of dense datasets, where many trajectories potentially match with a given query. In this paper, we apply fingerprinting, a copy-detection mechanism used in the context of textual data, to trajectories. To this end, we fingerprint trajectories with geodabs, a construction based on geohash aimed at trajectory fingerprinting. We demonstrate that by relying on the properties of a space filling curve geodabs can be used to build sharded inverted indexes. We show how normalization affects precision and recall, two key measures in information retrieval. We then demonstrate that the probabilistic nature of fingerprinting has a marginal effect on the quality of the results. Finally, we evaluate our method in terms of performances and show that, in contrast with existing methods, it is not affected by the density of the trajectory dataset and that it can be efficiently distributed.
Light Transport Simulation via Generalized Multiple Importance Sampling
Venue: arXiv cs.GR 2018
Year: 2018

Multiple importance sampling (MIS) is employed to reduce variance of estimators, but when sampling and weighting are not suitable to the integrand, the estimators would have extra variance. Therefore, robust light transport simulation algorithms based on Monte Carlo sampling for different types of scenes are still uncompleted. In this paper, we address this problem by present a general method, named generalized multiple importance sampling (GMIS), to enhance the robustness of light transport simulation based on MIS. GMIS combines different sampling techniques and weighting functions, extending MIS to a more generalized framework. Meanwhile, we implement the GMIS in common renderers and illustrate how it increase the robustness of light transport simulation. Experiments show that, by applying GMIS, we obtain better convergence performance and lower variance, and increase the rendering of ambient light and specular shadow effects apparently.