OpenRaiser/Intern-Atlas huggingface dataset:
Parallel Range, Segment and Rectangle Queries with Augmented Maps
Venue: arXiv cs.CG 2018
Year: 2018

The range, segment and rectangle query problems are fundamental problems in computational geometry, and have extensive applications in many domains. Despite the significant theoretical work on these problems, efficient implementations can be complicated. We know of very few practical implementations of the algorithms in parallel, and most implementations do not have tight theoretical bounds. We focus on simple and efficient parallel algorithms and implementations for these queries, which have tight worst-case bound in theory and good parallel performance in practice. We propose to use a simple framework (the augmented map) to model the problem. Based on the augmented map interface, we develop both multi-level tree structures and sweepline algorithms supporting range, segment and rectangle queries in two dimensions. For the sweepline algorithms, we propose a parallel paradigm and show corresponding cost bounds. All of our data structures are work-efficient to build in theory and achieve a low parallel depth. The query time is almost linear to the output size. We have implemented all the data structures described in the paper using a parallel augmented map library. Based on the library each data structure only requires about 100 lines of C++ code. We test their performance on large data sets (up to $10^8$ elements) and a machine with 72-cores (144 hyperthreads). The parallel construction achieves 32-68x speedup. Speedup numbers on queries are up to 126-fold. Our sequential implementation outperforms the CGAL library by at least 2x in both construction and queries. Our sequential implementation can be slightly slower than the R-tree in the Boost library in some cases (0.6-2.5x), but has significantly better query performance (1.6-1400x) than Boost.
SEGEN: Sample-Ensemble Genetic Evolutional Network Model
Venue: arXiv cs.NE 2018
Year: 2018

Deep learning, a rebranding of deep neural network research works, has achieved a remarkable success in recent years. With multiple hidden layers, deep learning models aim at computing the hierarchical feature representations of the observational data. Meanwhile, due to its severe disadvantages in data consumption, computational resources, parameter tuning costs and the lack of result explainability, deep learning has also suffered from lots of criticism. In this paper, we will introduce a new representation learning model, namely "Sample-Ensemble Genetic Evolutionary Network" (SEGEN), which can serve as an alternative approach to deep learning models. Instead of building one single deep model, based on a set of sampled sub-instances, SEGEN adopts a genetic-evolutionary learning strategy to build a group of unit models generations by generations. The unit models incorporated in SEGEN can be either traditional machine learning models or the recent deep learning models with a much "narrower" and "shallower" architecture. The learning results of each instance at the final generation will be effectively combined from each unit model via diffusive propagation and ensemble learning strategies. From the computational perspective, SEGEN requires far less data, fewer computational resources and parameter tuning efforts, but has sound theoretic interpretability of the learning process and results. Extensive experiments have been done on several different real-world benchmark datasets, and the experimental results obtained by SEGEN have demonstrated its advantages over the state-of-the-art representation learning models.
Hardware based Spatio-Temporal Neural Processing Backend for Imaging Sensors: Towards a Smart Camera
Venue: arXiv cs.CV 2018
Year: 2018

In this work we show how we can build a technology platform for cognitive imaging sensors using recent advances in recurrent neural network architectures and training methods inspired from biology. We demonstrate learning and processing tasks specific to imaging sensors, including enhancement of sensitivity and signal-to-noise ratio (SNR) purely through neural filtering beyond the fundamental limits sensor materials, and inferencing and spatio-temporal pattern recognition capabilities of these networks with applications in object detection, motion tracking and prediction. We then show designs of unit hardware cells built using complementary metal-oxide semiconductor (CMOS) and emerging materials technologies for ultra-compact and energy-efficient embedded neural processors for smart cameras.
PDNet: Prior-model Guided Depth-enhanced Network for Salient Object Detection
Venue: arXiv cs.CV 2018
Year: 2018

Fully convolutional neural networks (FCNs) have shown outstanding performance in many computer vision tasks including salient object detection. However, there still remains two issues needed to be addressed in deep learning based saliency detection. One is the lack of tremendous amount of annotated data to train a network. The other is the lack of robustness for extracting salient objects in images containing complex scenes. In this paper, we present a new architecture$ - $PDNet, a robust prior-model guided depth-enhanced network for RGB-D salient object detection. In contrast to existing works, in which RGB-D values of image pixels are fed directly to a network, the proposed architecture is composed of a master network for processing RGB values, and a sub-network making full use of depth cues and incorporate depth-based features into the master network. To overcome the limited size of the labeled RGB-D dataset for training, we employ a large conventional RGB dataset to pre-train the master network, which proves to contribute largely to the final accuracy. Extensive evaluations over five benchmark datasets demonstrate that our proposed method performs favorably against the state-of-the-art approaches.
Studio Ousia's Quiz Bowl Question Answering System
Venue: arXiv cs.CL 2018
Year: 2018

In this chapter, we describe our question answering system, which was the winning system at the Human-Computer Question Answering (HCQA) Competition at the Thirty-first Annual Conference on Neural Information Processing Systems (NIPS). The competition requires participants to address a factoid question answering task referred to as quiz bowl. To address this task, we use two novel neural network models and combine these models with conventional information retrieval models using a supervised machine learning model. Our system achieved the best performance among the systems submitted in the competition and won a match against six top human quiz experts by a wide margin.
Revisiting Single Image Depth Estimation: Toward Higher Resolution Maps with Accurate Object Boundaries
Venue: arXiv cs.CV 2018
Year: 2018

This paper considers the problem of single image depth estimation. The employment of convolutional neural networks (CNNs) has recently brought about significant advancements in the research of this problem. However, most existing methods suffer from loss of spatial resolution in the estimated depth maps; a typical symptom is distorted and blurry reconstruction of object boundaries. In this paper, toward more accurate estimation with a focus on depth maps with higher spatial resolution, we propose two improvements to existing approaches. One is about the strategy of fusing features extracted at different scales, for which we propose an improved network architecture consisting of four modules: an encoder, decoder, multi-scale feature fusion module, and refinement module. The other is about loss functions for measuring inference errors used in training. We show that three loss terms, which measure errors in depth, gradients and surface normals, respectively, contribute to improvement of accuracy in an complementary fashion. Experimental results show that these two improvements enable to attain higher accuracy than the current state-of-the-arts, which is given by finer resolution reconstruction, for example, with small objects and object boundaries.
Deep learning and its application to medical image segmentation
Venue: arXiv cs.CV 2018
Year: 2018

One of the most common tasks in medical imaging is semantic segmentation. Achieving this segmentation automatically has been an active area of research, but the task has been proven very challenging due to the large variation of anatomy across different patients. However, recent advances in deep learning have made it possible to significantly improve the performance of image recognition and semantic segmentation methods in the field of computer vision. Due to the data driven approaches of hierarchical feature learning in deep learning frameworks, these advances can be translated to medical images without much difficulty. Several variations of deep convolutional neural networks have been successfully applied to medical images. Especially fully convolutional architectures have been proven efficient for segmentation of 3D medical images. In this article, we describe how to build a 3D fully convolutional network (FCN) that can process 3D images in order to produce automatic semantic segmentations. The model is trained and evaluated on a clinical computed tomography (CT) dataset and shows state-of-the-art performance in multi-organ segmentation.
An Incremental Boolean Tensor Factorization approach to model Change Patterns of Objects in Images
Venue: arXiv cs.CV 2018
Year: 2018

Change detection process has recently progressed from a post-classification method to an expert knowledge interpretation process of the time-series data. The technique finds applications mainly in remote sensing images and can be utilized to analyze urbanization and monitor forest regions. In this paper, a framework to perform a knowledge based interpretation of the changes/no changes observed in a spatiotemporal domain using tensor based approaches is presented. An incremental approach to Boolean Tensor Factorization method is proposed in this work, which is adopted to model the change patterns of objects/classes as well as their associated features. The framework is evaluated under different datasets to visualize the performance for the dependency factors. The algorithm is also validated in comparison with the tradition Boolean Tensor Factorization method and the results are substantial.
$\mathcal{O}(k)$-robust spanners in one dimension
Venue: arXiv cs.CG 2018
Year: 2018

A geometric $t$-spanner on a set of points in Euclidean space is a graph containing for every pair of points a path of length at most $t$ times the Euclidean distance between the points. Informally, a spanner is $\mathcal{O}(k)$-robust if deleting $k$ vertices only harms $\mathcal{O}(k)$ other vertices. We show that on any one-dimensional set of $n$ points, for any $\varepsilon>0$, there exists an $\mathcal{O}(k)$-robust $1$-spanner with $\mathcal{O}(n^{1+\varepsilon})$ edges. Previously it was only known that $\mathcal{O}(k)$-robust spanners with $\mathcal{O}(n^2)$ edges exists and that there are point sets on which any $\mathcal{O}(k)$-robust spanner has $Ω(n\log{n})$ edges.
Data Streams with Bounded Deletions
Venue: arXiv cs.DS 2018
Year: 2018

Two prevalent models in the data stream literature are the insertion-only and turnstile models. Unfortunately, many important streaming problems require a $Θ(\log(n))$ multiplicative factor more space for turnstile streams than for insertion-only streams. This complexity gap often arises because the underlying frequency vector $f$ is very close to $0$, after accounting for all insertions and deletions to items. Signal detection in such streams is difficult, given the large number of deletions. In this work, we propose an intermediate model which, given a parameter $α\geq 1$, lower bounds the norm $\|f\|_p$ by a $1/α$-fraction of the $L_p$ mass of the stream had all updates been positive. Here, for a vector $f$, $\|f\|_p = \left (\sum_{i=1}^n |f_i|^p \right )^{1/p}$, and the value of $p$ we choose depends on the application. This gives a fluid medium between insertion only streams (with $α= 1$), and turnstile streams (with $α= \text{poly}(n)$), and allows for analysis in terms of $α$. We show that for streams with this $α$-property, for many fundamental streaming problems we can replace a $O(\log(n))$ factor in the space usage for algorithms in the turnstile model with a $O(\log(α))$ factor. This is true for identifying heavy hitters, inner product estimation, $L_0$ estimation, $L_1$ estimation, $L_1$ sampling, and support sampling. For each problem, we give matching or nearly matching lower bounds for $α$-property streams. We note that in practice, many important turnstile data streams are in fact $α$-property streams for small values of $α$. For such applications, our results represent significant improvements in efficiency for all the aforementioned problems.
Sentiment Analysis of Comments on Rohingya Movement with Support Vector Machine
Venue: arXiv cs.IR 2018
Year: 2018

The Rohingya Movement and Crisis caused a huge uproar in the political and economic state of Bangladesh. Refugee movement is a recurring event and a large amount of data in the form of opinions remains on social media such as Facebook, with very little analysis done on them.To analyse the comments based on all Rohingya related posts, we had to create and modify a classifier based on the Support Vector Machine algorithm. The code is implemented in python and uses scikit-learn library. A dataset on Rohingya analysis is not currently available so we had to use our own data set of 2500 positive and 2500 negative comments. We specifically used a support vector machine with linear kernel. A previous experiment was performed by us on the same dataset using the naive bayes algorithm, but that did not yield impressive results.
Modelling and controllability of the motion of a slender, flexible micro-swimmer
Venue: arXiv cs.SY 2018
Year: 2018

The mechanism of swimming at very low Reynolds number conditions is a topic of interest to biologists and engineering community. We develop a novel kinematic model of a slender flexible swimmer which locomotes in a low Reynolds number regime. In contrast to existing techniques that model such systems as a connected set of straight, rigid links, the novelty of our technique stems from the fact that we model the swimmer with two components - one is a straight, rigid body (the head) and the other is a flexible member (the tail). Using Cox theory we model the gradient of the forces as a function of the instantaneous shape of the swimmer and its velocity. By virtue of the low inertia conditions, an expression for the translational and rotational velocity of the head is obtained for the planar motion in the form of a Lie algebra of the Special Euclidean group. We explain the principal fiber bundle structure of the configuration space of the swimmer and use that to show a weak controllability result for a type of slender flexible swimmer where the shape space is the space of all continuous curves of a given length. A set of simulation results is presented showing the variation of the swimmer head velocity for a bump function moving along the swimmer length.
2CoBel : An Efficient Belief Function Extension for Two-dimensional Continuous Spaces
Venue: arXiv cs.AI 2018
Year: 2018

This paper introduces an innovative approach for handling 2D compound hypotheses within the Belief Function Theory framework. We propose a polygon-based generic rep- resentation which relies on polygon clipping operators. This approach allows us to account in the computational cost for the precision of the representation independently of the cardinality of the discernment frame. For the BBA combination and decision making, we propose efficient algorithms which rely on hashes for fast lookup, and on a topological ordering of the focal elements within a directed acyclic graph encoding their interconnections. Additionally, an implementation of the functionalities proposed in this paper is provided as an open source library. Experimental results on a pedestrian localization problem are reported. The experiments show that the solution is accurate and that it fully benefits from the scalability of the 2D search space granularity provided by our representation.
State measurement error-to-state stability results based on approximate discrete-time models
Venue: arXiv cs.SY 2018
Year: 2018

Digital controller design for nonlinear systems may be complicated by the fact that an exact discrete-time plant model is not known. One existing approach employs approximate discrete-time models for stability analysis and control design, and ensures different types of closedloop stability properties based on the approximate model and on specific bounds on the mismatch between the exact and approximate models. Although existing conditions for practical stability exist, some of which consider the presence of process disturbances, input-to-state stability with respect to state-measurement errors and based on approximate discretetime models has not been addressed. In this paper, we thus extend existing results in two main directions: (a) we provide input-to-state stability (ISS)-related results where the input is the state measurement error and (b) our results allow for some specific varying-sampling-rate scenarios. We provide conditions to ensure semiglobal practical ISS, even under some specific forms of varying sampling rate. These conditions employ Lyapunov-like functions. We illustrate the application of our results on numerical examples, where we show that a bounded state-measurement error can cause a semiglobal practically stable system to diverge.
DeepMood: Modeling Mobile Phone Typing Dynamics for Mood Detection
Venue: arXiv cs.HC 2018
Year: 2018

The increasing use of electronic forms of communication presents new opportunities in the study of mental health, including the ability to investigate the manifestations of psychiatric diseases unobtrusively and in the setting of patients' daily lives. A pilot study to explore the possible connections between bipolar affective disorder and mobile phone usage was conducted. In this study, participants were provided a mobile phone to use as their primary phone. This phone was loaded with a custom keyboard that collected metadata consisting of keypress entry time and accelerometer movement. Individual character data with the exceptions of the backspace key and space bar were not collected due to privacy concerns. We propose an end-to-end deep architecture based on late fusion, named DeepMood, to model the multi-view metadata for the prediction of mood scores. Experimental results show that 90.31% prediction accuracy on the depression score can be achieved based on session-level mobile phone typing dynamics which is typically less than one minute. It demonstrates the feasibility of using mobile phone metadata to infer mood disturbance and severity.
Pattern Analysis with Layered Self-Organizing Maps
Venue: arXiv cs.CV 2018
Year: 2018

This paper defines a new learning architecture, Layered Self-Organizing Maps (LSOMs), that uses the SOM and supervised-SOM learning algorithms. The architecture is validated with the MNIST database of hand-written digit images. LSOMs are similar to convolutional neural nets (covnets) in the way they sample data, but different in the way they represent features and learn. LSOMs analyze (or generate) image patches with maps of exemplars determined by the SOM learning algorithm rather than feature maps from filter-banks learned via backprop. LSOMs provide an alternative to features derived from covnets. Multi-layer LSOMs are trained bottom-up, without the use of backprop and therefore may be of interest as a model of the visual cortex. The results show organization at multiple levels. The algorithm appears to be resource efficient in learning, classifying and generating images. Although LSOMs can be used for classification, their validation accuracy for these exploratory runs was well below the state of the art. The goal of this article is to define the architecture and display the structures resulting from its application to the MNIST images.
Socio-spatial Self-organizing Maps: Using Social Media to Assess Relevant Geographies for Exposure to Social Processes
Venue: arXiv cs.SI 2018
Year: 2018

Social media offers a unique window into attitudes like racism and homophobia, exposure to which are important, hard to measure and understudied social determinants of health. However, individual geo-located observations from social media are noisy and geographically inconsistent. Existing areas by which exposures are measured, like Zip codes, average over irrelevant administratively-defined boundaries. Hence, in order to enable studies of online social environmental measures like attitudes on social media and their possible relationship to health outcomes, first there is a need for a method to define the collective, underlying degree of social media attitudes by region. To address this, we create the Socio-spatial-Self organizing map, "SS-SOM" pipeline to best identify regions by their latent social attitude from Twitter posts. SS-SOMs use neural embedding for text-classification, and augment traditional SOMs to generate a controlled number of non-overlapping, topologically-constrained and topically-similar clusters. We find that not only are SS-SOMs robust to missing data, the exposure of a cohort of men who are susceptible to multiple racism and homophobia-linked health outcomes, changes by up to 42% using SS-SOM measures as compared to using Zip code-based measures.
Message passing-based joint CFO and channel estimation in millimeter wave systems with one-bit ADCs
Venue: arXiv cs.IT 2018
Year: 2018

Channel estimation at millimeter wave (mmWave) is challenging when large antenna arrays are used. Prior work has leveraged the sparse nature of mmWave channels via compressed sensing based algorithms for channel estimation. Most of these algorithms, though, assume perfect synchronization and are vulnerable to phase errors that arise due to carrier frequency offset (CFO) and phase noise. Recently sparsity-aware, non-coherent beamforming algorithms that are robust to phase errors were proposed for narrowband phased array systems with full resolution analog-to-digital converters (ADCs). Such energy based algorithms, however, are not robust to heavy quantization at the receiver. In this paper, we develop a joint CFO and wideband channel estimation algorithm that is scalable across different mmWave architectures. Our method exploits the sparsity of mmWave MIMO channel in the angle-delay domain, in addition to compressibility of the phase error vector. We formulate the joint estimation as a sparse bilinear optimization problem and then use message passing for recovery. We also give an efficient implementation of a generalized bilinear message passing algorithm for the joint estimation in mmWave systems with one-bit ADCs. Simulation results show that our method is able to recover the CFO and the channel compressively, even in the presence of phase noise.