OpenRaiser/Intern-Atlas huggingface dataset:
Imbalanced Deep Learning by Minority Class Incremental Rectification
Venue: arXiv cs.CV 2018
Year: 2018

Model learning from class imbalanced training data is a long-standing and significant challenge for machine learning. In particular, existing deep learning methods consider mostly either class balanced data or moderately imbalanced data in model training, and ignore the challenge of learning from significantly imbalanced training data. To address this problem, we formulate a class imbalanced deep learning model based on batch-wise incremental minority (sparsely sampled) class rectification by hard sample mining in majority (frequently sampled) classes during model training. This model is designed to minimise the dominant effect of majority classes by discovering sparsely sampled boundaries of minority classes in an iterative batch-wise learning process. To that end, we introduce a Class Rectification Loss (CRL) function that can be deployed readily in deep network architectures. Extensive experimental evaluations are conducted on three imbalanced person attribute benchmark datasets (CelebA, X-Domain, DeepFashion) and one balanced object category benchmark dataset (CIFAR-100). These experimental results demonstrate the performance advantages and model scalability of the proposed batch-wise incremental minority class rectification model over the existing state-of-the-art models for addressing the problem of imbalanced data learning.
A Tree Search Algorithm for Sequence Labeling
Venue: arXiv cs.CL 2018
Year: 2018

In this paper we propose a novel reinforcement learning based model for sequence tagging, referred to as MM-Tag. Inspired by the success and methodology of the AlphaGo Zero, MM-Tag formalizes the problem of sequence tagging with a Monte Carlo tree search (MCTS) enhanced Markov decision process (MDP) model, in which the time steps correspond to the positions of words in a sentence from left to right, and each action corresponds to assign a tag to a word. Two long short-term memory networks (LSTM) are used to summarize the past tag assignments and words in the sentence. Based on the outputs of LSTMs, the policy for guiding the tag assignment and the value for predicting the whole tagging accuracy of the whole sentence are produced. The policy and value are then strengthened with MCTS, which takes the produced raw policy and value as inputs, simulates and evaluates the possible tag assignments at the subsequent positions, and outputs a better search policy for assigning tags. A reinforcement learning algorithm is proposed to train the model parameters. Our work is the first to apply the MCTS enhanced MDP model to the sequence tagging task. We show that MM-Tag can accurately predict the tags thanks to the exploratory decision making mechanism introduced by MCTS. Experimental results show based on a chunking benchmark showed that MM-Tag outperformed the state-of-the-art sequence tagging baselines including CRF and CRF with LSTM.
A Spatial Basis Coverage Approach For Uplink Training And Scheduling In Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

Massive multiple-input multiple-output (massive MIMO) can provide large spectral and energy efficiency gains. Nevertheless, its potential is conditioned on acquiring accurate channel state information (CSI). In time division duplexing (TDD) systems, CSI is obtained through uplink training which is hindered by pilot contamination. The impact of this phenomenon can be relieved using spatial division multiplexing, which refers to partitioning users based on their spatial information and processing their signals accordingly. The performance of such schemes depend primarily on the implemented grouping method. In this paper, we propose a novel spatial grouping scheme that aims at managing pilot contamination while reducing the required training overhead in TDD massive MIMO. Herein, user specific decoding matrices are derived based on the columns of the discrete Fourier transform matrix (DFT), taken as a spatial basis. Copilot user groups are then formed in order to obtain the best coverage of the spatial basis with minimum overlapping between decoding matrices. We provide two algorithms that achieve the desired grouping and derive their respective performance guarantees. We also address inter-cell copilot interference through efficient pilot sequence allocation, leveraging the formed copilot groups. Various numerical results are provided to showcase the efficiency of the proposed algorithms.
Feedforward Architectures for Decentralized Precoding in Massive MU-MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

Massive multi-user multiple-input multiple-output (MU-MIMO) enables significant gains in spectral efficiency and link reliability compared to conventional small-scale MIMO technology. Furthermore, linear precoders, e.g., using zero forcing or Wiener filter (WF) precoding, are sufficient to achieve excellent error-rate performance in the massive MU-MIMO downlink. However, these methods necessitate centralized processing at the base-station (BS), which causes (i) excessively high interconnect and chip input/output data rates, and (ii) high implementation complexity. We propose two feedforward architectures and corresponding decentralized WF precoders that parallelize precoding across multiple computing fabrics, effectively mitigating the issues of centralized approaches. To demonstrate the efficacy of our decentralized precoders, we provide implementation results on a multi-GPU system, which show that our solutions achieve throughputs in the Gbit/s regime while achieving (near-)optimal error-rate performance in the massive MU-MIMO downlink.
Deep Co-attention based Comparators For Relative Representation Learning in Person Re-identification
Venue: arXiv cs.CV 2018
Year: 2018

Person re-identification (re-ID) requires rapid, flexible yet discriminant representations to quickly generalize to unseen observations on-the-fly and recognize the same identity across disjoint camera views. Recent effective methods are developed in a pair-wise similarity learning system to detect a fixed set of features from distinct regions which are mapped to their vector embeddings for the distance measuring. However, the most relevant and crucial parts of each image are detected independently without referring to the dependency conditioned on one and another. Also, these region based methods rely on spatial manipulation to position the local features in comparable similarity measuring. To combat these limitations, in this paper we introduce the Deep Co-attention based Comparators (DCCs) that fuse the co-dependent representations of the paired images so as to focus on the relevant parts of both images and produce their \textit{relative representations}. Given a pair of pedestrian images to be compared, the proposed model mimics the foveation of human eyes to detect distinct regions concurrent on both images, namely co-dependent features, and alternatively attend to relevant regions to fuse them into the similarity learning. Our comparator is capable of producing dynamic representations relative to a particular sample every time, and thus well-suited to the case of re-identifying pedestrians on-the-fly. We perform extensive experiments to provide the insights and demonstrate the effectiveness of the proposed DCCs in person re-ID. Moreover, our approach has achieved the state-of-the-art performance on three benchmark data sets: DukeMTMC-reID \cite{DukeMTMC}, CUHK03 \cite{FPNN}, and Market-1501 \cite{Market1501}.
High-Performance and Energy-Effcient Memory Scheduler Design for Heterogeneous Systems
Venue: arXiv cs.AR 2018
Year: 2018

When multiple processor cores (CPUs) and a GPU integrated together on the same chip share the off-chip DRAM, requests from the GPU can heavily interfere with requests from the CPUs, leading to low system performance and starvation of cores. Unfortunately, state-of-the-art memory scheduling algorithms are ineffective at solving this problem due to the very large amount of GPU memory traffic, unless a very large and costly request buffer is employed to provide these algorithms with enough visibility across the global request stream. Previously-proposed memory controller (MC) designs use a single monolithic structure to perform three main tasks. First, the MC attempts to schedule together requests to the same DRAM row to increase row buffer hit rates. Second, the MC arbitrates among the requesters (CPUs and GPU) to optimize for overall system throughput, average response time, fairness and quality of service. Third, the MC manages the low-level DRAM command scheduling to complete requests while ensuring compliance with all DRAM timing and power constraints. This paper proposes a fundamentally new approach, called the Staged Memory Scheduler (SMS), which decouples the three primary MC tasks into three significantly simpler structures that together improve system performance and fairness. Our evaluation shows that SMS provides 41.2% performance improvement and fairness improvement compared to the best previous state-of-the-art technique, while enabling a design that is significantly less complex and more power-efficient to implement.
A Subquadratic Algorithm for 3XOR
Venue: arXiv cs.DS 2018
Year: 2018

Given a set $X$ of $n$ binary words of equal length $w$, the 3XOR problem asks for three elements $a, b, c \in X$ such that $a \oplus b=c$, where $ \oplus$ denotes the bitwise XOR operation. The problem can be easily solved on a word RAM with word length $w$ in time $O(n^2 \log{n})$. Using Han's fast integer sorting algorithm (2002/2004) this can be reduced to $O(n^2 \log{\log{n}})$. With randomization or a sophisticated deterministic dictionary construction, creating a hash table for $X$ with constant lookup time leads to an algorithm with (expected) running time $O(n^2)$. At present, seemingly no faster algorithms are known. We present a surprisingly simple deterministic, quadratic time algorithm for 3XOR. Its core is a version of the Patricia trie for $X$, which makes it possible to traverse the set $a \oplus X$ in ascending order for arbitrary $a\in \{0, 1\}^{w}$ in linear time. Furthermore, we describe a randomized algorithm for 3XOR with expected running time $O(n^2\cdot\min\{\log^3{w}/w, (\log\log{n})^2/\log^2 n\})$. The algorithm transfers techniques to our setting that were used by Baran, Demaine, and Pătraşcu (2005/2008) for solving the related int3SUM problem (the same problem with integer addition in place of binary XOR) in expected time $o(n^2)$. As suggested by Jafargholi and Viola (2016), linear hash functions are employed. The latter authors also showed that assuming 3XOR needs expected running time $n^{2-o(1)}$ one can prove conditional lower bounds for triangle enumeration just as with 3SUM. We demonstrate that 3XOR can be reduced to other problems as well, treating the examples offline SetDisjointness and offline SetIntersection, which were studied for 3SUM by Kopelowitz, Pettie, and Porat (2016).
FIRST: A Framework for Optimizing Information Quality in Mobile Crowdsensing Systems
Venue: arXiv cs.NI 2018
Year: 2018

Mobile crowdsensing allows data collection at a scale and pace that was once impossible. One of the biggest challenges in mobile crowdsensing is that participants may exhibit malicious or unreliable behavior. Therefore, it becomes imperative to design algorithms to accurately classify between reliable and unreliable sensing reports. To this end, we propose a novel Framework for optimizing Information Reliability in Smartphone-based participaTory sensing (FIRST), that leverages mobile trusted participants (MTPs) to securely assess the reliability of sensing reports. FIRST models and solves the challenging problem of determining before deployment the minimum number of MTPs to be used in order to achieve desired classification accuracy. We extensively evaluate FIRST through an implementation in iOS and Android of a room occupancy monitoring system, and through simulations with real-world mobility traces. Experimental results demonstrate that FIRST reduces significantly the impact of three security attacks (i.e., corruption, on/off, and collusion), by achieving a classification accuracy of almost 80% in the considered scenarios. Finally, we discuss our ongoing research efforts to test the performance of FIRST as part of the National Map Corps project.
Structured Weight Matrices-Based Hardware Accelerators in Deep Neural Networks: FPGAs and ASICs
Venue: arXiv cs.DC 2018
Year: 2018

Both industry and academia have extensively investigated hardware accelerations. In this work, to address the increasing demands in computational capability and memory requirement, we propose structured weight matrices (SWM)-based compression techniques for both \emph{field programmable gate array} (FPGA) and \emph{application-specific integrated circuit} (ASIC) implementations. In algorithm part, SWM-based framework adopts block-circulant matrices to achieve a fine-grained tradeoff between accuracy and compression ratio. The SWM-based technique can reduce computational complexity from O($n^2$) to O($n\log n$) and storage complexity from O($n^2$) to O($n$) for each layer and both training and inference phases. For FPGA implementations on deep convolutional neural networks (DCNNs), we achieve at least 152X and 72X improvement in performance and energy efficiency, respectively using the SWM-based framework, compared with the baseline of IBM TrueNorth processor under same accuracy constraints using the data set of MNIST, SVHN, and CIFAR-10. For FPGA implementations on long short term memory (LSTM) networks, the proposed SWM-based LSTM can achieve up to 21X enhancement in performance and 33.5X gains in energy efficiency compared with the baseline accelerator. For ASIC implementations, the SWM-based ASIC design exhibits impressive advantages in terms of power, throughput, and energy efficiency. Experimental results indicate that this method is greatly suitable for applying DNNs onto both FPGAs and mobile/IoT devices.
On the Feasibility of Real-Time 3D Hand Tracking using Edge GPGPU Acceleration
Venue: arXiv cs.DC 2018
Year: 2018

This paper presents the case study of a non-intrusive porting of a monolithic C++ library for real-time 3D hand tracking, to the domain of edge-based computation. Towards a proof of concept, the case study considers a pair of workstations, a computationally powerful and a computationally weak one. By wrapping the C++ library in Java container and by capitalizing on a Java-based offloading infrastructure that supports both CPU and GPGPU computations, we are able to establish automatically the required server-client workflow that best addresses the resource allocation problem in the effort to execute from the weak workstation. As a result, the weak workstation can perform well at the task, despite lacking the sufficient hardware to do the required computations locally. This is achieved by offloading computations which rely on GPGPU, to the powerful workstation, across the network that connects them. We show the edge-based computation challenges associated with the information flow of the ported algorithm, demonstrate how we cope with them, and identify what needs to be improved for achieving even better performance.
4D Temporally Coherent Light-field Video
Venue: arXiv cs.CV 2018
Year: 2018

Light-field video has recently been used in virtual and augmented reality applications to increase realism and immersion. However, existing light-field methods are generally limited to static scenes due to the requirement to acquire a dense scene representation. The large amount of data and the absence of methods to infer temporal coherence pose major challenges in storage, compression and editing compared to conventional video. In this paper, we propose the first method to extract a spatio-temporally coherent light-field video representation. A novel method to obtain Epipolar Plane Images (EPIs) from a spare light-field camera array is proposed. EPIs are used to constrain scene flow estimation to obtain 4D temporally coherent representations of dynamic light-fields. Temporal coherence is achieved on a variety of light-field datasets. Evaluation of the proposed light-field scene flow against existing multi-view dense correspondence approaches demonstrates a significant improvement in accuracy of temporal coherence.
Stack-U-Net: Refinement Network for Image Segmentation on the Example of Optic Disc and Cup
Venue: arXiv cs.CV 2018
Year: 2018

In this work, we propose a special cascade network for image segmentation, which is based on the U-Net networks as building blocks and the idea of the iterative refinement. The model was mainly applied to achieve higher recognition quality for the task of finding borders of the optic disc and cup, which are relevant to the presence of glaucoma. Compared to a single U-Net and the state-of-the-art methods for the investigated tasks, very high segmentation quality has been achieved without a need for increasing the volume of datasets. Our experiments include comparison with the best-known methods on publicly available databases DRIONS-DB, RIM-ONE v.3, DRISHTI-GS, and evaluation on a private data set collected in collaboration with University of California San Francisco Medical School. The analysis of the architecture details is presented, and it is argued that the model can be employed for a broad scope of image segmentation problems of similar nature.
Algorithms for Deciding Membership in Polytopes of General Dimension
Venue: arXiv cs.CG 2018
Year: 2018

We study the fundamental problem of polytope membership aiming at large convex polytopes, i.e. in high dimension and with many facets, given as an intersection of halfspaces. Standard data-structures as well as brute force methods cannot scale, due to the curse of dimen- sionality. We design an efficient algorithm, by reduction to the approx- imate Nearest Neighbor (ANN) problem based on the construction of a Voronoi diagram with the polytope being one bounded cell. We thus trade exactness for efficiency so as to obtain complexity bounds polyno- mial in the dimension, by exploiting recent progress in the complexity of ANN search. We employ this algorithm to present a novel boundary data structure based on a Newton-like iterative intersection procedure. We implement our algorithms and compare with brute-force approaches to show that they scale very well as the dimension and number of facets grow larger.
A Hybrid Recommendation Method Based on Feature for Offline Book Personalization
Venue: arXiv cs.IR 2018
Year: 2018

Recommendation system has been widely used in different areas. Collaborative filtering focuses on rating, ignoring the features of items itself. In order to effectively evaluate customers preferences on books, taking into consideration of the characteristics of offline book retail, we use LDA model to calculate customers preference on book topics and use word2vec to calculate customers preference on book types. When forecasting rating on books, we take two factors into consideration: similarity of customers and correlation between customers and books. The experiment shows that our hybrid recommendation method based on features performances better than single recommendation method in offline book retail data.
Maximum Likelihood Coordinate Systems for Wireless Sensor Networks: from physical coordinates to topology coordinates
Venue: arXiv cs.NI 2018
Year: 2018

Many WSN protocols require the location coordinates of the sensor nodes, as it is useful to consider the data collected by the sensors in the context of the location from which they were collected. Thus, one of the major challenges in WSNs is to determine the coordinates of sensors while minimizing the hardware cost. To address this, numerous localization algorithms have been proposed in the literature. However, outcomes of these algorithms are affected by noise, fading, and interference. As a result, their levels of accuracy may become unacceptable in complex environments that contain obstacles and reflecting surfaces. The alternative is to use topological maps based only on connectivity information. Since they do not contain information about physical distances, however, they are not faithful representatives of the physical layout. Thus, the primary goal of this research is to discover a topology map that provides more accurate information about physical layouts. In doing so, this research has resulted in four main contributions. First, a novel concept Maximum-Likelihood Topology Map for RF WSNs is presented. This topology map provides a more accurate physical representation, by using the probability of packet reception. The second contribution is Millimetre wave Topology Map calculation, which is a novel topology mapping algorithm based on maximum likelihood estimation for millimetre wave WSNs. The third contribution is a distributed algorithm being proposed to calculate the topology coordinates of sensors by themselves as two algorithms above calculate centrally, which requires time. Since a topology map contains significant non-linear distortions, two WSN applications i.e. target searching and extremum seeking, which use a proposed topology map to localize the sensors and perform its specified task are presented as the final contribution of this dissertation.
On improving the approximation ratio of the r-shortest common superstring problem
Venue: arXiv cs.DS 2018
Year: 2018

The Shortest Common Superstring problem (SCS) consists, for a set of strings S = {s_1,...,s_n}, in finding a minimum length string that contains all s_i, 1<= i <= n, as substrings. While a 2+11/30 approximation ratio algorithm has recently been published, the general objective is now to break the conceptual lower bound barrier of 2. This paper is a step ahead in this direction. Here we focus on a particular instance of the SCS problem, meaning the r-SCS problem, which requires all input strings to be of the same length, r. Golonev et al. proved an approximation ratio which is better than the general one for r<= 6. Here we extend their approach and improve their approximation ratio, which is now better than the general one for r<= 7, and less than or equal to 2 up to r = 6.
Live Functional Programming with Typed Holes
Venue: arXiv cs.PL 2018
Year: 2018

This paper develops a dynamic semantics for incomplete functional programs, starting from the static semantics developed in recent work on Hazelnut. We model incomplete functional programs as expressions with holes, with empty holes standing for missing expressions or types, and non-empty holes operating as membranes around static and dynamic type inconsistencies. Rather than aborting when evaluation encounters any of these holes as in some existing systems, evaluation proceeds around holes, tracking the closure around each hole instance as it flows through the remainder of the program. Editor services can use the information in these hole closures to help the programmer develop and confirm their mental model of the behavior of the complete portions of the program as they decide how to fill the remaining holes. Hole closures also enable a fill-and-resume operation that avoids the need to restart evaluation after edits that amount to hole filling. Formally, the semantics borrows machinery from both gradual type theory (which supplies the basis for handling unfilled type holes) and contextual modal type theory (which supplies a logical basis for hole closures), combining these and developing additional machinery necessary to continue evaluation past holes while maintaining type safety. We have mechanized the metatheory of the core calculus, called Hazelnut Live, using the Agda proof assistant. We have also implemented these ideas into the Hazel programming environment. The implementation inserts holes automatically, following the Hazelnut edit action calculus, to guarantee that every editor state has some (possibly incomplete) type. Taken together with this paper's type safety property, the result is a proof-of-concept live programming environment where rich dynamic feedback is truly available without gaps, i.e. for every reachable editor state.