OpenRaiser/Intern-Atlas huggingface dataset:
External Memory Pipelining Made Easy With TPIE
Venue: arXiv cs.DS 2017
Year: 2017

When handling large datasets that exceed the capacity of the main memory, movement of data between main memory and external memory (disk), rather than actual (CPU) computation time, is often the bottleneck in the computation. Since data is moved between disk and main memory in large contiguous blocks, this has led to the development of a large number of I/O-efficient algorithms that minimize the number of such block movements. TPIE is one of two major libraries that have been developed to support I/O-efficient algorithm implementations. TPIE provides an interface where list stream processing and sorting can be implemented in a simple and modular way without having to worry about memory management or block movement. However, if care is not taken, such streaming-based implementations can lead to practically inefficient algorithms since lists of data items are typically written to (and read from) disk between components. In this paper we present a major extension of the TPIE library that includes a pipelining framework that allows for practically efficient streaming-based implementations while minimizing I/O-overhead between streaming components. The framework pipelines streaming components to avoid I/Os between components, that is, it processes several components simultaneously while passing output from one component directly to the input of the next component in main memory. TPIE automatically determines which components to pipeline and performs the required main memory management, and the extension also includes support for parallelization of internal memory computation and progress tracking across an entire application. The extended library has already been used to evaluate I/O-efficient algorithms in the research literature and is heavily used in I/O-efficient commercial terrain processing applications by the Danish startup SCALGO.
SceneFlowFields: Dense Interpolation of Sparse Scene Flow Correspondences
Venue: arXiv cs.CV 2017
Year: 2017

While most scene flow methods use either variational optimization or a strong rigid motion assumption, we show for the first time that scene flow can also be estimated by dense interpolation of sparse matches. To this end, we find sparse matches across two stereo image pairs that are detected without any prior regularization and perform dense interpolation preserving geometric and motion boundaries by using edge information. A few iterations of variational energy minimization are performed to refine our results, which are thoroughly evaluated on the KITTI benchmark and additionally compared to state-of-the-art on MPI Sintel. For application in an automotive context, we further show that an optional ego-motion model helps to boost performance and blends smoothly into our approach to produce a segmentation of the scene into static and dynamic parts.
Inverse Reinforcement Learning Under Noisy Observations
Venue: arXiv cs.RO 2017
Year: 2017

We consider the problem of performing inverse reinforcement learning when the trajectory of the expert is not perfectly observed by the learner. Instead, a noisy continuous-time observation of the trajectory is provided to the learner. This problem exhibits wide-ranging applications and the specific application we consider here is the scenario in which the learner seeks to penetrate a perimeter patrolled by a robot. The learner's field of view is limited due to which it cannot observe the patroller's complete trajectory. Instead, we allow the learner to listen to the expert's movement sound, which it can also use to estimate the expert's state and action using an observation model. We treat the expert's state and action as hidden data and present an algorithm based on expectation maximization and maximum entropy principle to solve the non-linear, non-convex problem. Related work considers discrete-time observations and an observation model that does not include actions. In contrast, our technique takes expectations over both state and action of the expert, enabling learning even in the presence of extreme noise and broader applications.
Enhanced Biologically Inspired Model for Image Recognition Based on a Novel Patch Selection Method with Moment
Venue: arXiv cs.CV 2017
Year: 2017

Biologically inspired model (BIM) for image recognition is a robust computational architecture, which has attracted widespread attention. BIM can be described as a four-layer structure based on the mechanisms of the visual cortex. Although the performance of BIM for image recognition is robust, it takes the randomly selected ways for the patch selection, which is sightless, and results in heavy computing burden. To address this issue, we propose a novel patch selection method with oriented Gaussian-Hermite moment (PSGHM), and we enhanced the BIM based on the proposed PSGHM, named as PBIM. In contrast to the conventional BIM which adopts the random method to select patches within the feature representation layers processed by multi-scale Gabor filter banks, the proposed PBIM takes the PSGHM way to extract a small number of representation features while offering promising distinctiveness. To show the effectiveness of the proposed PBIM, experimental studies on object categorization are conducted on the CalTech05, TU Darmstadt (TUD), and GRAZ01 databases. Experimental results demonstrate that the performance of PBIM is a significant improvement on that of the conventional BIM.
Fronthaul-Aware Software-Defined Wireless Networks: Resource Allocation and User Scheduling
Venue: arXiv cs.NI 2017
Year: 2017

Software-defined networking (SDN) provides an agile and programmable way to optimize radio access networks via a control-data plane separation. Nevertheless, reaping the benefits of wireless SDN hinges on making optimal use of the limited wireless fronthaul capacity. In this work, the problem of fronthaul-aware resource allocation and user scheduling is studied. To this end, a two-timescale fronthaul-aware SDN control mechanism is proposed in which the controller maximizes the time-averaged network throughput by enforcing a coarse correlated equilibrium in the long timescale. Subsequently, leveraging the controller's recommendations, each base station schedules its users using Lyapunov stochastic optimization in the short timescale, i.e., at each time slot. Simulation results show that significant network throughput enhancements and up to 40% latency reduction are achieved with the aid of the SDN controller. Moreover, the gains are more pronounced for denser network deployments.
Ranking Functions for Vector Addition Systems
Venue: arXiv cs.LO 2017
Year: 2017

Vector addition systems are an important model in theoretical computer science and have been used for the analysis of systems in a variety of areas. Termination is a crucial property of vector addition systems and has received considerable interest in the literature. In this paper we give a complete method for the construction of ranking functions for vector addition systems with states. The interest in ranking functions is motivated by the fact that ranking functions provide valuable additional information in case of termination: They provide an explanation for the progress of the vector addition system, which can be reported to the user of a verification tool, and can be used as certificates for termination. Moreover, we show how ranking functions can be used for the computational complexity analysis of vector addition systems (here complexity refers to the number of steps the vector addition system under analysis can take in terms of the given initial vector).
Power Modelling for Heterogeneous Cloud-Edge Data Centers
Venue: arXiv cs.PF 2017
Year: 2017

Existing power modelling research focuses not on the method used for developing models but rather on the model itself. This paper aims to develop a method for deploying power models on emerging processors that will be used, for example, in cloud-edge data centers. Our research first develops a hardware counter selection method that appropriately selects counters most correlated to power on ARM and Intel processors. Then, we propose a two stage power model that works across multiple architectures. The key results are: (i) the automated hardware performance counter selection method achieves comparable selection to the manual selection methods reported in literature, and (ii) the two stage power model can predict dynamic power more accurately on both ARM and Intel processors when compared to classic power models.
Multi-modal Aggregation for Video Classification
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we present a solution to Large-Scale Video Classification Challenge (LSVC2017) [1] that ranked the 1st place. We focused on a variety of modalities that cover visual, motion and audio. Also, we visualized the aggregation process to better understand how each modality takes effect. Among the extracted modalities, we found Temporal-Spatial features calculated by 3D convolution quite promising that greatly improved the performance. We attained the official metric mAP 0.8741 on the testing set with the ensemble model.
Label Embedding Network: Learning Label Representation for Soft Training of Deep Networks
Venue: arXiv cs.LG 2017
Year: 2017

We propose a method, called Label Embedding Network, which can learn label representation (label embedding) during the training process of deep networks. With the proposed method, the label embedding is adaptively and automatically learned through back propagation. The original one-hot represented loss function is converted into a new loss function with soft distributions, such that the originally unrelated labels have continuous interactions with each other during the training process. As a result, the trained model can achieve substantially higher accuracy and with faster convergence speed. Experimental results based on competitive tasks demonstrate the effectiveness of the proposed method, and the learned label embedding is reasonable and interpretable. The proposed method achieves comparable or even better results than the state-of-the-art systems. The source code is available at \url{https://github.com/lancopku/LabelEmb}.
Analytical Estimation of the Scalability of Iterative Numerical Algorithms on Distributed Memory Multiprocessors
Venue: arXiv cs.DC 2017
Year: 2017

This article presents a new high-level parallel computational model named BSF - Bulk Synchronous Farm. The BSF model extends the BSP model to deal with the compute-intensive iterative numerical methods executed on distributed-memory multiprocessor systems. The BSF model is based on the master-worker paradigm and the SPMD programming model. The BSF model makes it possible to predict the upper scalability bound of a BSF-program with great accuracy. The BSF model also provides equations for estimating the speedup and parallel efficiency of a BSF-program.
Personalized word representations Carrying Personalized Semantics Learned from Social Network Posts
Venue: arXiv cs.CL 2017
Year: 2017

Distributed word representations have been shown to be very useful in various natural language processing (NLP) application tasks. These word vectors learned from huge corpora very often carry both semantic and syntactic information of words. However, it is well known that each individual user has his own language patterns because of different factors such as interested topics, friend groups, social activities, wording habits, etc., which may imply some kind of personalized semantics. With such personalized semantics, the same word may imply slightly differently for different users. For example, the word "Cappuccino" may imply "Leisure", "Joy", "Excellent" for a user enjoying coffee, by only a kind of drink for someone else. Such personalized semantics of course cannot be carried by the standard universal word vectors trained with huge corpora produced by many people. In this paper, we propose a framework to train different personalized word vectors for different users based on the very successful continuous skip-gram model using the social network data posted by many individual users. In this framework, universal background word vectors are first learned from the background corpora, and then adapted by the personalized corpus for each individual user to learn the personalized word vectors. We use two application tasks to evaluate the quality of the personalized word vectors obtained in this way, the user prediction task and the sentence completion task. These personalized word vectors were shown to carry some personalized semantics and offer improved performance on these two evaluation tasks.
A Saak Transform Approach to Efficient, Scalable and Robust Handwritten Digits Recognition
Venue: arXiv cs.CV 2017
Year: 2017

An efficient, scalable and robust approach to the handwritten digits recognition problem based on the Saak transform is proposed in this work. First, multi-stage Saak transforms are used to extract a family of joint spatial-spectral representations of input images. Then, the Saak coefficients are used as features and fed into the SVM classifier for the classification task. In order to control the size of Saak coefficients, we adopt a lossy Saak transform that uses the principal component analysis (PCA) to select a smaller set of transform kernels. The handwritten digits recognition problem is well solved by the convolutional neural network (CNN) such as the LeNet-5. We conduct a comparative study on the performance of the LeNet-5 and the Saak-transform-based solutions in terms of scalability and robustness as well as the efficiency of lossless and lossy Saak transforms under a comparable accuracy level.
Simple and Effective Multi-Paragraph Reading Comprehension
Venue: arXiv cs.CL 2017
Year: 2017

We consider the problem of adapting neural paragraph-level question answering models to the case where entire documents are given as input. Our proposed solution trains models to produce well calibrated confidence scores for their results on individual paragraphs. We sample multiple paragraphs from the documents during training, and use a shared-normalization training objective that encourages the model to produce globally correct output. We combine this method with a state-of-the-art pipeline for training models on document QA data. Experiments demonstrate strong performance on several document QA datasets. Overall, we are able to achieve a score of 71.3 F1 on the web portion of TriviaQA, a large improvement from the 56.7 F1 of the previous best system.
Learning neural trans-dimensional random field language models with noise-contrastive estimation
Venue: arXiv cs.CL 2017
Year: 2017

Trans-dimensional random field language models (TRF LMs) where sentences are modeled as a collection of random fields, have shown close performance with LSTM LMs in speech recognition and are computationally more efficient in inference. However, the training efficiency of neural TRF LMs is not satisfactory, which limits the scalability of TRF LMs on large training corpus. In this paper, several techniques on both model formulation and parameter estimation are proposed to improve the training efficiency and the performance of neural TRF LMs. First, TRFs are reformulated in the form of exponential tilting of a reference distribution. Second, noise-contrastive estimation (NCE) is introduced to jointly estimate the model parameters and normalization constants. Third, we extend the neural TRF LMs by marrying the deep convolutional neural network (CNN) and the bidirectional LSTM into the potential function to extract the deep hierarchical features and bidirectionally sequential features. Utilizing all the above techniques enables the successful and efficient training of neural TRF LMs on a 40x larger training set with only 1/3 training time and further reduces the WER with relative reduction of 4.7% on top of a strong LSTM LM baseline.
Cascade Region Proposal and Global Context for Deep Object Detection
Venue: arXiv cs.CV 2017
Year: 2017

Deep region-based object detector consists of a region proposal step and a deep object recognition step. In this paper, we make significant improvements on both of the two steps. For region proposal we propose a novel lightweight cascade structure which can effectively improve RPN proposal quality. For object recognition we re-implement global context modeling with a few modications and obtain a performance boost (4.2% mAP gain on the ILSVRC 2016 validation set). Besides, we apply the idea of pre-training extensively and show its importance in both steps. Together with common training and testing tricks, we improve Faster R-CNN baseline by a large margin. In particular, we obtain 87.9% mAP on the PASCAL VOC 2012 test set, 65.3% on the ILSVRC 2016 test set and 36.8% on the COCO test-std set.
A Framework for Over-the-air Reciprocity Calibration for TDD Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

One of the biggest challenges in operating massive multiple-input multiple-output systems is the acquisition of accurate channel state information at the transmitter. To take up this challenge, time division duplex is more favorable thanks to its channel reciprocity between downlink and uplink. However, while the propagation channel over the air is reciprocal, the radio-frequency front-ends in the transceivers are not. Therefore, calibration is required to compensate the RF hardware asymmetry. Although various over-the-air calibration methods exist to address the above problem, this paper offers a unified representation of these algorithms, providing a higher level view on the calibration problem, and introduces innovations on calibration methods. We present a novel family of calibration methods, based on antenna grouping, which improve accuracy and speed up the calibration process compared to existing methods. We then provide the Cramér-Rao bound as the performance evaluation benchmark and compare maximum likelihood and least squares estimators. We also differentiate between coherent and non-coherent accumulation of calibration measurements, and point out that enabling non-coherent accumulation allows the training to be spread in time, minimizing impact to the data service. Overall, these results have special value in allowing to design reciprocity calibration techniques that are both accurate and resource-effective.
Learning to solve inverse problems using Wasserstein loss
Venue: arXiv cs.CV 2017
Year: 2017

We propose using the Wasserstein loss for training in inverse problems. In particular, we consider a learned primal-dual reconstruction scheme for ill-posed inverse problems using the Wasserstein distance as loss function in the learning. This is motivated by miss-alignments in training data, which when using standard mean squared error loss could severely degrade reconstruction quality. We prove that training with the Wasserstein loss gives a reconstruction operator that correctly compensates for miss-alignments in certain cases, whereas training with the mean squared error gives a smeared reconstruction. Moreover, we demonstrate these effects by training a reconstruction algorithm using both mean squared error and optimal transport loss for a problem in computerized tomography.
Finding Connected Secluded Subgraphs
Venue: arXiv cs.DS 2017
Year: 2017

Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough results and led to development of new techniques both within the traditional P vs NP dichotomy and within parameterized complexity. The Π-Subgraph problem asks whether an input graph contains an induced subgraph on at least k vertices satisfying graph property Π. For many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the Secluded Π-Subgraph problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Π, even when parameterized by k+t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Π. In particular, we show that the Connected Π-Secluded Subgraph problem is FPT when parameterized by just t for many important graph properties Π.
Social Network De-anonymization: More Adversarial Knowledge, More Users Re-Identified?
Venue: arXiv cs.SI 2017
Year: 2017

Following the trend of data trading and data publishing, many online social networks have enabled potentially sensitive data to be exchanged or shared on the web. As a result, users' privacy could be exposed to malicious third parties since they are extremely vulnerable to de-anonymization attacks, i.e., the attacker links the anonymous nodes in the social network to their real identities with the help of background knowledge. Previous work in social network de-anonymization mostly focuses on designing accurate and efficient de-anonymization methods. We study this topic from a different perspective and attempt to investigate the intrinsic relation between the attacker's knowledge and the expected de-anonymization gain. One common intuition is that the more auxiliary information the attacker has, the more accurate de-anonymization becomes. However, their relation is much more sophisticated than that. To simplify the problem, we attempt to quantify background knowledge and de-anonymization gain under several assumptions. Our theoretical analysis and simulations on synthetic and real network data show that more background knowledge may not necessarily lead to more de-anonymization gain in certain cases. Though our analysis is based on a few assumptions, the findings still leave intriguing implications for the attacker to make better use of the background knowledge when performing de-anonymization, and for the data owners to better measure the privacy risk when releasing their data to third parties.
A Comprehensive Survey on Fog Computing: State-of-the-art and Research Challenges
Venue: arXiv cs.DC 2017
Year: 2017

Cloud computing with its three key facets (i.e., IaaS, PaaS, and SaaS) and its inherent advantages (e.g., elasticity and scalability) still faces several challenges. The distance between the cloud and the end devices might be an issue for latency-sensitive applications such as disaster management and content delivery applications. Service Level Agreements (SLAs) may also impose processing at locations where the cloud provider does not have data centers. Fog computing is a novel paradigm to address such issues. It enables provisioning resources and services outside the cloud, at the edge of the network, closer to end devices or eventually, at locations stipulated by SLAs. Fog computing is not a substitute for cloud computing but a powerful complement. It enables processing at the edge while still offering the possibility to interact with the cloud. This article presents a comprehensive survey on fog computing. It critically reviews the state of the art in the light of a concise set of evaluation criteria. We cover both the architectures and the algorithms that make fog systems. Challenges and research directions are also introduced. In addition, the lessons learned are reviewed and the prospects are discussed in terms of the key role fog is likely to play in emerging technologies such as Tactile Internet.