OpenRaiser/Intern-Atlas huggingface dataset:
Global-Local Airborne Mapping (GLAM): Reconstructing a City from Aerial Videos
Venue: arXiv cs.CV 2018
Year: 2018

Monocular visual SLAM has become an attractive practical approach for robot localization and 3D environment mapping, since cameras are small, lightweight, inexpensive, and produce high-rate, high-resolution data streams. Although numerous robust tools have been developed, most existing systems are designed to operate in terrestrial environments and at relatively small scale (a few thousand frames) due to constraints on computation and storage. In this paper, we present a feature-based visual SLAM system for aerial video whose simple design permits near real-time operation, and whose scalability permits large-area mapping using tens of thousands of frames, all on a single conventional computer. Our approach consists of two parallel threads: the first incrementally creates small locally consistent submaps and estimates camera poses at video rate; the second aligns these submaps with one another to produce a single globally consistent map via factor graph optimization over both poses and landmarks. Scale drift is minimized through the use of 7-degree-of-freedom similarity transformations during submap alignment. We quantify our system's performance on both simulated and real data sets, and demonstrate city-scale map reconstruction accurate to within 2 meters using nearly 90,000 aerial video frames - to our knowledge, the largest and fastest such reconstruction to date.
Automatic Emphysema Detection using Weakly Labeled HRCT Lung Images
Venue: arXiv cs.CV 2018
Year: 2018

A method for automatically quantifying emphysema regions using High-Resolution Computed Tomography (HRCT) scans of patients with chronic obstructive pulmonary disease (COPD) that does not require manually annotated scans for training is presented. HRCT scans of controls and of COPD patients with diverse disease severity are acquired at two different centers. Textural features from co-occurrence matrices and Gaussian filter banks are used to characterize the lung parenchyma in the scans. Two robust versions of multiple instance learning (MIL) classifiers, miSVM and MILES, are investigated. The classifiers are trained with the weak labels extracted from the forced expiratory volume in one minute (FEV$_1$) and diffusing capacity of the lungs for carbon monoxide (DLCO). At test time, the classifiers output a patient label indicating overall COPD diagnosis and local labels indicating the presence of emphysema. The classifier performance is compared with manual annotations by two radiologists, a classical density based method, and pulmonary function tests (PFTs). The miSVM classifier performed better than MILES on both patient and emphysema classification. The classifier has a stronger correlation with PFT than the density based method, the percentage of emphysema in the intersection of annotations from both radiologists, and the percentage of emphysema annotated by one of the radiologists. The correlation between the classifier and the PFT is only outperformed by the second radiologist. The method is therefore promising for facilitating assessment of emphysema and reducing inter-observer variability.
Inductive Representation Learning on Large Graphs
Venue: arXiv cs.SI 2018
Year: 2018

Low-dimensional embeddings of nodes in large graphs have proved extremely useful in a variety of prediction tasks, from content recommendation to identifying protein functions. However, most existing approaches require that all nodes in the graph are present during training of the embeddings; these previous approaches are inherently transductive and do not naturally generalize to unseen nodes. Here we present GraphSAGE, a general, inductive framework that leverages node feature information (e.g., text attributes) to efficiently generate node embeddings for previously unseen data. Instead of training individual embeddings for each node, we learn a function that generates embeddings by sampling and aggregating features from a node's local neighborhood. Our algorithm outperforms strong baselines on three inductive node-classification benchmarks: we classify the category of unseen nodes in evolving information graphs based on citation and Reddit post data, and we show that our algorithm generalizes to completely unseen graphs using a multi-graph dataset of protein-protein interactions.
Meta-Learning for Resampling Recommendation Systems
Venue: arXiv cs.LG 2018
Year: 2018

One possible approach to tackle the class imbalance in classification tasks is to resample a training dataset, i.e., to drop some of its elements or to synthesize new ones. There exist several widely-used resampling methods. Recent research showed that the choice of resampling method significantly affects the quality of classification, which raises resampling selection problem. Exhaustive search for optimal resampling is time-consuming and hence it is of limited use. In this paper, we describe an alternative approach to the resampling selection. We follow the meta-learning concept to build resampling recommendation systems, i.e., algorithms recommending resampling for datasets on the basis of their properties.
Evaluating (and improving) the correspondence between deep neural networks and human representations
Venue: arXiv cs.CV 2018
Year: 2018

Decades of psychological research have been aimed at modeling how people learn features and categories. The empirical validation of these theories is often based on artificial stimuli with simple representations. Recently, deep neural networks have reached or surpassed human accuracy on tasks such as identifying objects in natural images. These networks learn representations of real-world stimuli that can potentially be leveraged to capture psychological representations. We find that state-of-the-art object classification networks provide surprisingly accurate predictions of human similarity judgments for natural images, but fail to capture some of the structure represented by people. We show that a simple transformation that corrects these discrepancies can be obtained through convex optimization. We use the resulting representations to predict the difficulty of learning novel categories of natural images. Our results extend the scope of psychological experiments and computational modeling by enabling tractable use of large natural stimulus sets.
SliceType: Fast Gaze Typing with a Merging Keyboard
Venue: arXiv cs.HC 2018
Year: 2018

Jitter is an inevitable by-product of gaze detection. Because of this, gaze typing tends to be a slow and frustrating process. In this paper, we propose SliceType, a soft keyboard that is optimized for gaze input. Our main design objective is to use the screen area more efficiently by allocating a larger area to the target keys. We achieve this by determining the keys that will not be used for the next input, and allocating their space to the adjacent keys with a merging animation. Larger keys are faster to navigate towards, and easy to dwell on in the presence of eye tracking jitter. As a result, the user types faster and more comfortably. In addition, we employ a word completion scheme that complements gaze typing mechanics. A character and a related prediction is displayed at each key. Dwelling at a key enters the character, and double-dwelling enters the prediction. While dwelling on a key to enter a character, the user reads the related prediction effortlessly. The improvements provided by these features are quantified using the Fitts' law. The performance of the proposed keyboard is compared with two other soft keyboards designed for gaze typing, Dasher and GazeTalk. 37 novice users gaze-typed a piece of text using all three keyboards. The results of the experiment show that the proposed keyboard allows faster typing, and is more preferred by the users.
Dynamic Integration of Background Knowledge in Neural NLU Systems
Venue: arXiv cs.CL 2018
Year: 2018

Common-sense and background knowledge is required to understand natural language, but in most neural natural language understanding (NLU) systems, this knowledge must be acquired from training corpora during learning, and then it is static at test time. We introduce a new architecture for the dynamic integration of explicit background knowledge in NLU models. A general-purpose reading module reads background knowledge in the form of free-text statements (together with task-specific text inputs) and yields refined word representations to a task-specific NLU architecture that reprocesses the task inputs with these representations. Experiments on document question answering (DQA) and recognizing textual entailment (RTE) demonstrate the effectiveness and flexibility of the approach. Analysis shows that our model learns to exploit knowledge in a semantically appropriate way.
Multistatic Scatter Radio Sensor Networks for Extended Coverage
Venue: arXiv cs.IT 2018
Year: 2018

Scatter radio, i.e., communication by means of reflection, has been recently proposed as a viable ultra-low power solution for wireless sensor networks (WSNs). This work offers a detailed comparison between monostatic and multistatic scatter radio architectures. In monostatic architecture, the reader consists of both the illuminating transmitter and the receiver of signals scattered back from the sensors. The multistatic architecture includes several ultra-low cost illuminating carrier emitters and a single reader. Maximum-likelihood coherent and noncoherent bit error rate (BER), diversity order, average information and energy outage probability comparison is performed, under dyadic Nakagami fading, filling a gap in the literature. It is found that: (i) diversity order, BER, and tag location-independent performance bounds of multistatic architecture outperform monostatic, (ii) energy outage due to radio frequency (RF) harvesting for passive tags, is less frequent in multistatic than monostatic architecture, and (iii) multistatic coverage is higher than monostatic. Furthermore, a proof-of-concept {digital} multistatic, scatter radio WSN with a single receiver, four low-cost emitters and multiple ambiently-powered, low-bitrate tags, perhaps the first of its kind, is experimentally demonstrated (at $13$ dBm transmission power), covering an area of $3500$ m$^2$. Research findings are applicable in the industries of WSNs, radio frequency identification (RFID), and emerging Internet-of-Things.
On some interesting ternary formulas
Venue: arXiv cs.DM 2018
Year: 2018

We obtain the following results about the avoidance of ternary formulas. Up to renaming of the letters, the only infinite ternary words avoiding the formula $ABCAB.ABCBA.ACB.BAC$ (resp. $ABCA.BCAB.BCB.CBA$) have the same set of recurrent factors as the fixed point of $\texttt{0}\mapsto\texttt{012}$, $\texttt{1}\mapsto\texttt{02}$, $\texttt{2}\mapsto\texttt{1}$. The formula $ABAC.BACA.ABCA$ is avoided by polynomially many binary words and there exist arbitrarily many infinite binary words with different sets of recurrent factors that avoid it. If every variable of a ternary formula appears at least twice in the same fragment, then the formula is $3$-avoidable. The pattern $ABACADABCA$ is unavoidable for the class of $C_4$-minor-free graphs with maximum degree~$3$. This disproves a conjecture of Grytczuk. The formula $ABCA.ACBA$, or equivalently the palindromic pattern $ABCADACBA$, has avoidability index $4$.
Recovering 6D Object Pose: A Review and Multi-modal Analysis
Venue: arXiv cs.CV 2018
Year: 2018

A large number of studies analyse object detection and pose estimation at visual level in 2D, discussing the effects of challenges such as occlusion, clutter, texture, etc., on the performances of the methods, which work in the context of RGB modality. Interpreting the depth data, the study in this paper presents thorough multi-modal analyses. It discusses the above-mentioned challenges for full 6D object pose estimation in RGB-D images comparing the performances of several 6D detectors in order to answer the following questions: What is the current position of the computer vision community for maintaining "automation" in robotic manipulation? What next steps should the community take for improving "autonomy" in robotics while handling objects? Our findings include: (i) reasonably accurate results are obtained on textured-objects at varying viewpoints with cluttered backgrounds. (ii) Heavy existence of occlusion and clutter severely affects the detectors, and similar-looking distractors is the biggest challenge in recovering instances' 6D. (iii) Template-based methods and random forest-based learning algorithms underlie object detection and 6D pose estimation. Recent paradigm is to learn deep discriminative feature representations and to adopt CNNs taking RGB images as input. (iv) Depending on the availability of large-scale 6D annotated depth datasets, feature representations can be learnt on these datasets, and then the learnt representations can be customized for the 6D problem.
Accurate Monocular Visual-inertial SLAM using a Map-assisted EKF Approach
Venue: arXiv cs.RO 2018
Year: 2018

This paper presents a novel tightly-coupled monocular visual-inertial Simultaneous Localization and Mapping algorithm, which provides accurate and robust localization within the globally consistent map in real time on a standard CPU. This is achieved by firstly performing the visual-inertial extended kalman filter(EKF) to provide motion estimate at a high rate. However the filter becomes inconsistent due to the well known linearization issues. So we perform a keyframe-based visual-inertial bundle adjustment to improve the consistency and accuracy of the system. In addition, a loop closure detection and correction module is also added to eliminate the accumulated drift when revisiting an area. Finally, the optimized motion estimates and map are fed back to the EKF-based visual-inertial odometry module, thus the inconsistency and estimation error of the EKF estimator are reduced. In this way, the system can continuously provide reliable motion estimates for the long-term operation. The performance of the algorithm is validated on public datasets and real-world experiments, which proves the superiority of the proposed algorithm.
On complexity of propositional Linear-time Temporal Logic with finitely many variables
Venue: arXiv cs.LO 2018
Year: 2018

It is known [DemriSchnoebelen02] that both satisfiability and model-checking problems for propositional Linear-time Temporal Logic, LTL, with only a single propositional variable in the language are PSPACE-complete, which coincides with the complexity of these problems for LTL with an arbitrary number of propositional variables [SislaClarke85]. In the present paper, we show that the same result can be obtained by modifying the original proof of SPACE-hardness for LTL from [SislaClarke85]; i.e., we show how to modify the construction from [SislaClarke85] to model the computations of polynomially-space bound Turing machines using only formulas of one variable. We believe that our alternative proof of the results from [DemriSchnoebelen02] gives additional insight into the semantic and computational properties of LTL.
Reinforcement Learning with Budget-Constrained Nonparametric Function Approximation for Opportunistic Spectrum Access
Venue: arXiv cs.IT 2018
Year: 2018

Opportunistic spectrum access is one of the emerging techniques for maximizing throughput in congested bands and is enabled by predicting idle slots in spectrum. We propose a kernel-based reinforcement learning approach coupled with a novel budget-constrained sparsification technique that efficiently captures the environment to find the best channel access actions. This approach allows learning and planning over the intrinsic state-action space and extends well to large state spaces. We apply our methods to evaluate coexistence of a reinforcement learning-based radio with a multi-channel adversarial radio and a single-channel CSMA-CA radio. Numerical experiments show the performance gains over carrier-sense systems.
On Counting Triangles through Edge Sampling in Large Dynamic Graphs
Venue: arXiv cs.SI 2018
Year: 2018

Traditional frameworks for dynamic graphs have relied on processing only the stream of edges added into or deleted from an evolving graph, but not any additional related information such as the degrees or neighbor lists of nodes incident to the edges. In this paper, we propose a new edge sampling framework for big-graph analytics in dynamic graphs which enhances the traditional model by enabling the use of additional related information. To demonstrate the advantages of this framework, we present a new sampling algorithm, called Edge Sample and Discard (ESD). It generates an unbiased estimate of the total number of triangles, which can be continuously updated in response to both edge additions and deletions. We provide a comparative analysis of the performance of ESD against two current state-of-the-art algorithms in terms of accuracy and complexity. The results of the experiments performed on real graphs show that, with the help of the neighborhood information of the sampled edges, the accuracy achieved by our algorithm is substantially better. We also characterize the impact of properties of the graph on the performance of our algorithm by testing on several Barabasi-Albert graphs.
Approximate Best-Response Dynamics in Random Interference Games
Venue: arXiv cs.GT 2018
Year: 2018

In this paper we develop a novel approach to the convergence of Best-Response Dynamics for the family of interference games. Interference games represent the fundamental resource allocation conflict between users of the radio spectrum. In contrast to congestion games, interference games are generally not potential games. Therefore, proving the convergence of the best-response dynamics to a Nash equilibrium in these games requires new techniques. We suggest a model for random interference games, based on the long term fading governed by the players' geometry. Our goal is to prove convergence of the approximate best-response dynamics with high probability with respect to the randomized game. We embrace the asynchronous model in which the acting player is chosen at each stage at random. In our approximate best-response dynamics, the action of a deviating player is chosen at random among all the approximately best ones. We show that with high probability, with respect to the players' geometry and asymptotically with the number of players, each action increases the expected social-welfare (sum of achievable rates). Hence, the induced sum-rate process is a submartingale. Based on the Martingale Convergence Theorem, we prove convergence of the strategy profile to an approximate Nash equilibrium with good performance for asymptotically almost all interference games. We use the Markovity of the induced sum-rate process to provide probabilistic bounds on the convergence time. Finally, we demonstrate our results in simulated examples.
Modeling Biological Problems in Computer Science: A Case Study in Genome Assembly
Venue: arXiv cs.DS 2018
Year: 2018

As computer scientists working in bioinformatics/computational biology, we often face the challenge of coming up with an algorithm to answer a biological question. This occurs in many areas, such as variant calling, alignment, and assembly. In this tutorial, we use the example of the genome assembly problem to demonstrate how to go from a question in the biological realm to a solution in the computer science realm. We show the modeling process step-by-step, including all the intermediate failed attempts.
Closed-Form Mathematical Representations of Interval Type-2 Fuzzy Logic Systems
Venue: arXiv cs.SY 2018
Year: 2018

Interval type-2 fuzzy logic systems (IT2 FLSs) have a wide range of applications due to their abilities to handle uncertainties compared to their type-1 counterparts. This paper discusses the representation of IT2 FLSs in closed mathematical form. Two novel inference mechanisms are introduced, each of them represents a whole IT2 FLS. The two forms are based on approximating Coupland and John's geometric method and the Nie-Tan method. Having closed-form representations is preferred in the design of control systems, especially when stability analysis is studied. Additionally, the simplicity of the proposed mechanisms, offers an easy way for implementation. Simulation results show that the proposed method perform very closely to other methods. Simulation results are provided.
Gradient Diversity: a Key Ingredient for Scalable Distributed Learning
Venue: arXiv cs.LG 2018
Year: 2018

It has been experimentally observed that distributed implementations of mini-batch stochastic gradient descent (SGD) algorithms exhibit speedup saturation and decaying generalization ability beyond a particular batch-size. In this work, we present an analysis hinting that high similarity between concurrently processed gradients may be a cause of this performance degradation. We introduce the notion of gradient diversity that measures the dissimilarity between concurrent gradient updates, and show its key role in the performance of mini-batch SGD. We prove that on problems with high gradient diversity, mini-batch SGD is amenable to better speedups, while maintaining the generalization performance of serial (one sample) SGD. We further establish lower bounds on convergence where mini-batch SGD slows down beyond a particular batch-size, solely due to the lack of gradient diversity. We provide experimental evidence indicating the key role of gradient diversity in distributed learning, and discuss how heuristics like dropout, Langevin dynamics, and quantization can improve it.
Numerically Stable Variants of the Communication-hiding Pipelined Conjugate Gradients Algorithm for the Parallel Solution of Large Scale Symmetric Linear Systems
Venue: arXiv cs.NA 2018
Year: 2018

By reducing the number of global synchronization bottlenecks per iteration and hiding communication behind useful computational work, pipelined Krylov subspace methods achieve significantly improved parallel scalability on present-day HPC hardware. However, this typically comes at the cost of a reduced maximal attainable accuracy. This paper presents and compares several stabilized versions of the communication-hiding pipelined Conjugate Gradients method. The main novel contribution of this work is the reformulation of the multi-term recurrence pipelined CG algorithm by introducing shifts in the recursions for specific auxiliary variables. These shifts reduce the amplification of local rounding errors on the residual. The stability analysis presented in this work provides a rigorous method for selection of the optimal shift value in practice. It is shown that, given a proper choice for the shift parameter, the resulting shifted pipelined CG algorithm restores the attainable accuracy and displays nearly identical robustness to local rounding error propagation compared to classical CG. Numerical results on a variety of SPD benchmark problems compare different stabilization techniques for the pipelined CG algorithm, showing that the shifted pipelined CG algorithm is able to attain a high accuracy while displaying excellent parallel performance.