OpenRaiser/Intern-Atlas huggingface dataset:
GPU LSM: A Dynamic Dictionary Data Structure for the GPU
Venue: arXiv cs.DC 2018
Year: 2018

We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU.
Performance Implications of NoCs on 3D-Stacked Memories: Insights from the Hybrid Memory Cube
Venue: arXiv cs.AR 2018
Year: 2018

Memories that exploit three-dimensional (3D)-stacking technology, which integrate memory and logic dies in a single stack, are becoming popular. These memories, such as Hybrid Memory Cube (HMC), utilize a network-on-chip (NoC) design for connecting their internal structural organizations. This novel usage of NoC, in addition to aiding processing-in-memory capabilities, enables numerous benefits such as high bandwidth and memory-level parallelism. However, the implications of NoCs on the characteristics of 3D-stacked memories in terms of memory access latency and bandwidth have not been fully explored. This paper addresses this knowledge gap by (i) characterizing an HMC prototype on the AC-510 accelerator board and revealing its access latency behaviors, and (ii) by investigating the implications of such behaviors on system and software designs.
Vision-based Real Estate Price Estimation
Venue: arXiv cs.CV 2018
Year: 2018

Since the advent of online real estate database companies like Zillow, Trulia and Redfin, the problem of automatic estimation of market values for houses has received considerable attention. Several real estate websites provide such estimates using a proprietary formula. Although these estimates are often close to the actual sale prices, in some cases they are highly inaccurate. One of the key factors that affects the value of a house is its interior and exterior appearance, which is not considered in calculating automatic value estimates. In this paper, we evaluate the impact of visual characteristics of a house on its market value. Using deep convolutional neural networks on a large dataset of photos of home interiors and exteriors, we develop a method for estimating the luxury level of real estate photos. We also develop a novel framework for automated value assessment using the above photos in addition to home characteristics including size, offered price and number of bedrooms. Finally, by applying our proposed method for price estimation to a new dataset of real estate photos and metadata, we show that it outperforms Zillow's estimates.
Robust Monocular SLAM for Egocentric Videos
Venue: arXiv cs.CV 2018
Year: 2018

Regardless of the tremendous progress, a truly general purpose pipeline for Simultaneous Localization and Mapping (SLAM) remains a challenge. We investigate the reported failure of state of the art (SOTA) SLAM techniques on egocentric videos. We find that the dominant 3D rotations, low parallax between successive frames, and primarily forward motion in egocentric videos are the most common causes of failures. The incremental nature of SOTA SLAM, in the presence of unreliable pose and 3D estimates in egocentric videos, with no opportunities for global loop closures, generates drifts and leads to the eventual failures of such techniques. Taking inspiration from batch mode Structure from Motion (SFM) techniques, we propose to solve SLAM as an SFM problem over the sliding temporal windows. This makes the problem well constrained. Further, we propose to initialize the camera poses using 2D rotation averaging, followed by translation averaging before structure estimation using bundle adjustment. This helps in stabilizing the camera poses when 3D estimates are not reliable. We show that the proposed SLAM technique, incorporating the two key ideas works successfully for long, shaky egocentric videos where other SOTA techniques have been reported to fail. Qualitative and quantitative comparisons on publicly available egocentric video datasets validate our results.
A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error
Venue: arXiv cs.DS 2018
Year: 2018

We consider one-sided error property testing of $\mathcal{F}$-minor freeness in bounded-degree graphs for any finite family of graphs $\mathcal{F}$ that contains a minor of $K_{2,k}$, the $k$-circus graph, or the $(k\times 2)$-grid for any $k\in\mathbb{N}$. This includes, for instance, testing whether a graph is outerplanar or a cactus graph. The query complexity of our algorithm in terms of the number of vertices in the graph, $n$, is $\tilde{O}(n^{2/3} / ε^5)$. Czumaj et~al.\ showed that cycle-freeness and $C_k$-minor freeness can be tested with query complexity $\tilde{O}(\sqrt{n})$ by using random walks, and that testing $H$-minor freeness for any $H$ that contains a cycles requires $Ω(\sqrt{n})$ queries. In contrast to these results, we analyze the structure of the graph and show that either we can find a subgraph of sublinear size that includes the forbidden minor $H$, or we can find a pair of disjoint subsets of vertices whose edge-cut is large, which induces an $H$-minor.
Imagination-Augmented Agents for Deep Reinforcement Learning
Venue: arXiv cs.LG 2018
Year: 2018

We introduce Imagination-Augmented Agents (I2As), a novel architecture for deep reinforcement learning combining model-free and model-based aspects. In contrast to most existing model-based reinforcement learning and planning methods, which prescribe how a model should be used to arrive at a policy, I2As learn to interpret predictions from a learned environment model to construct implicit plans in arbitrary ways, by using the predictions as additional context in deep policy networks. I2As show improved data efficiency, performance, and robustness to model misspecification compared to several baselines.
Reconfiguration on nowhere dense graph classes
Venue: arXiv cs.DM 2018
Year: 2018

Let $\mathcal{Q}$ be a vertex subset problem on graphs. In a reconfiguration variant of $\mathcal{Q}$ we are given a graph $G$ and two feasible solutions $S_s, S_t\subseteq V(G)$ of $\mathcal{Q}$ with $|S_s|=|S_t|=k$. The problem is to determine whether there exists a sequence $S_1,\ldots,S_n$ of feasible solutions, where $S_1=S_s$, $S_n=S_t$, $|S_i|\leq k\pm 1$, and each $S_{i+1}$ results from $S_i$, $1\leq i<n$, by the addition or removal of a single vertex. We prove that for every nowhere dense class of graphs and for every integer $r\geq 1$ there exists a polynomial $p_r$ such that the reconfiguration variants of the distance-$r$ independent set problem and the distance-$r$ dominating set problem admit kernels of size $p_r(k)$. If $k$ is equal to the size of a minimum distance-$r$ dominating set, then for any fixed $ε>0$ we even obtain a kernel of almost linear size $\mathcal{O}(k^{1+ε})$. We then prove that if a class $\mathcal{C}$ is somewhere dense and closed under taking subgraphs, then for some value of $r\geq 1$ the reconfiguration variants of the above problems on $\mathcal{C}$ are $\mathsf{W}[1]$-hard (and in particular we cannot expect the existence of kernelization algorithms). Hence our results show that the limit of tractability for the reconfiguration variants of the distance-$r$ independent set problem and distance-$r$ dominating set problem on subgraph closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.
Detecting random walks on graphs with heterogeneous sensors
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of detecting a random walk on a graph, based on observations of the graph nodes. When visited by the walk, each node of the graph observes a signal of elevated mean, which we assume can be different across different nodes. Outside of the path of the walk, and also in its absence, nodes measure only noise. Assuming the Neyman-Pearson setting, our goal then is to characterize detection performance by computing the error exponent for the probability of a miss, under a constraint on the probability of false alarm. Since exact computation of the error exponent is known to be difficult, equivalent to computation of the Lyapunov exponent, we approximate its value by finding a tractable lower bound. The bound reveals an interesting detectability condition: the walk is detectable whenever the entropy of the walk is smaller than one half of the expected signal-to-noise ratio. We derive the bound by extending the notion of Markov types to Gauss-Markov types. These are sequences of state-observation pairs with a given number of node-to-node transition counts and the same average signal values across nodes, computed from the measurements made during the times the random walk was visiting each node's respective location. The lower bound has an intuitive interpretation: among all Gauss-Markov types that are asymptotically feasible in the absence of the walk, the bound finds the most typical one under the presence of the walk. Finally, we show by a sequence of judicious problem reformulations that computing the bound reduces to solving a convex optimization problem, which is a result in its own right.
Continuous-Time Gaussian Process Motion Planning via Probabilistic Inference
Venue: arXiv cs.RO 2018
Year: 2018

We introduce a novel formulation of motion planning, for continuous-time trajectories, as probabilistic inference. We first show how smooth continuous-time trajectories can be represented by a small number of states using sparse Gaussian process (GP) models. We next develop an efficient gradient-based optimization algorithm that exploits this sparsity and GP interpolation. We call this algorithm the Gaussian Process Motion Planner (GPMP). We then detail how motion planning problems can be formulated as probabilistic inference on a factor graph. This forms the basis for GPMP2, a very efficient algorithm that combines GP representations of trajectories with fast, structure-exploiting inference via numerical optimization. Finally, we extend GPMP2 to an incremental algorithm, iGPMP2, that can efficiently replan when conditions change. We benchmark our algorithms against several sampling-based and trajectory optimization-based motion planning algorithms on planning problems in multiple environments. Our evaluation reveals that GPMP2 is several times faster than previous algorithms while retaining robustness. We also benchmark iGPMP2 on replanning problems, and show that it can find successful solutions in a fraction of the time required by GPMP2 to replan from scratch.
Towards Accurate Markerless Human Shape and Pose Estimation over Time
Venue: arXiv cs.CV 2018
Year: 2018

Existing marker-less motion capture methods often assume known backgrounds, static cameras, and sequence specific motion priors, which narrows its application scenarios. Here we propose a fully automatic method that given multi-view video, estimates 3D human motion and body shape. We take recent SMPLify \cite{bogo2016keep} as the base method, and extend it in several ways. First we fit the body to 2D features detected in multi-view images. Second, we use a CNN method to segment the person in each image and fit the 3D body model to the contours to further improves accuracy. Third we utilize a generic and robust DCT temporal prior to handle the left and right side swapping issue sometimes introduced by the 2D pose estimator. Validation on standard benchmarks shows our results are comparable to the state of the art and also provide a realistic 3D shape avatar. We also demonstrate accurate results on HumanEva and on challenging dance sequences from YouTube in monocular case.
Harnessing Natural Experiments to Quantify the Causal Effect of Badges
Venue: arXiv cs.SI 2018
Year: 2018

A wide variety of online platforms use digital badges to encourage users to take certain types of desirable actions. However, despite their growing popularity, their causal effect on users' behavior is not well understood. This is partly due to the lack of counterfactual data and the myriad of complex factors that influence users' behavior over time. As a consequence, their design and deployment lacks general principles. In this paper, we focus on first-time badges, which are awarded after a user takes a particular type of action for the first time, and study their causal effect by harnessing the delayed introduction of several badges in a popular Q&A website. In doing so, we introduce a novel causal inference framework for badges whose main technical innovations are a robust survival-based hypothesis testing procedure, which controls for the utility heterogeneity across users, and a bootstrap difference-in-differences method, which controls for the random fluctuations in users' behavior over time. We find that first-time badges steer users' behavior if the utility a user obtains from taking the corresponding action is sufficiently low, otherwise, the badge does not have a significant effect. Moreover, for badges that successfully steered user behavior, we perform a counterfactual analysis and show that they significantly improved the functioning of the site at a community level.
A framework for quantitative modeling and analysis of highly (re)configurable systems
Venue: arXiv cs.SE 2018
Year: 2018

This paper presents our approach to the quantitative modeling and analysis of highly (re)configurable systems, such as software product lines. Different combinations of the optional features of such a system give rise to combinatorially many individual system variants. We use a formal modeling language that allows us to model systems with probabilistic behavior, possibly subject to quantitative feature constraints, and able to dynamically install, remove or replace features. More precisely, our models are defined in the probabilistic feature-oriented language QFLAN, a rich domain specific language (DSL) for systems with variability defined in terms of features. QFLAN specifications are automatically encoded in terms of a process algebra whose operational behavior interacts with a store of constraints, and hence allows to separate system configuration from system behavior. The resulting probabilistic configurations and behavior converge seamlessly in a semantics based on discrete-time Markov chains, thus enabling quantitative analysis. Our analysis is based on statistical model checking techniques, which allow us to scale to larger models with respect to precise probabilistic analysis techniques. The analyses we can conduct range from the likelihood of specific behavior to the expected average cost, in terms of feature attributes, of specific system variants. Our approach is supported by a novel Eclipse-based tool which includes state-of-the-art DSL utilities for QFLAN based on the Xtext framework as well as analysis plug-ins to seamlessly run statistical model checking analyses. We provide a number of case studies that have driven and validated the development of our framework.
Adaptive and Resilient Revenue Maximizing Dynamic Resource Allocation and Pricing for Cloud-Enabled IoT Systems
Venue: arXiv cs.DC 2018
Year: 2018

Cloud computing is becoming an essential component of modern computer and communication systems. The available resources at the cloud such as computing nodes, storage, databases, etc. are often packaged in the form of virtual machines (VMs) to be used by remotely located client applications for computational tasks. However, the cloud has a limited number of VMs available, which have to be efficiently utilized to generate higher productivity and subsequently generate maximum revenue. Client applications generate requests with computational tasks at random times with random complexity to be processed by the cloud. The cloud service provider (CSP) has to decide whether to allocate a VM to a task at hand or to wait for a higher complexity task in the future. We propose a threshold-based mechanism to optimally decide the allocation and pricing of VMs to sequentially arriving requests in order to maximize the revenue of the CSP over a finite time horizon. Moreover, we develop an adaptive and resilient framework based that can counter the effect of realtime changes in the number of available VMs at the cloud server, the frequency and nature of arriving tasks on the revenue of the CSP.
Robust Physical-World Attacks on Deep Learning Models
Venue: arXiv cs.CR 2018
Year: 2018

Recent studies show that the state-of-the-art deep neural networks (DNNs) are vulnerable to adversarial examples, resulting from small-magnitude perturbations added to the input. Given that that emerging physical systems are using DNNs in safety-critical situations, adversarial examples could mislead these systems and cause dangerous situations.Therefore, understanding adversarial examples in the physical world is an important step towards developing resilient learning algorithms. We propose a general attack algorithm,Robust Physical Perturbations (RP2), to generate robust visual adversarial perturbations under different physical conditions. Using the real-world case of road sign classification, we show that adversarial examples generated using RP2 achieve high targeted misclassification rates against standard-architecture road sign classifiers in the physical world under various environmental conditions, including viewpoints. Due to the current lack of a standardized testing method, we propose a two-stage evaluation methodology for robust physical adversarial examples consisting of lab and field tests. Using this methodology, we evaluate the efficacy of physical adversarial manipulations on real objects. Witha perturbation in the form of only black and white stickers,we attack a real stop sign, causing targeted misclassification in 100% of the images obtained in lab settings, and in 84.8%of the captured video frames obtained on a moving vehicle(field test) for the target classifier.
Evolution of Human-like Social Grooming Strategies regarding Richness and Group Size
Venue: arXiv cs.SI 2018
Year: 2018

Human beings tend to cooperate with close friends, therefore they have to construct strong social relationships to recieve cooperation from others. Therefore they should have acquired their strategies of social relationship construction through an evolutionary process. The behavior of social relationship construction is know as "social grooming." In this paper, we show that there are four classes including a human-like strategy in evolutionary dynamics of social grooming strategies based on an evolutionary game simulation. Social relationship strengths (as measured by frequency of social grooming) often show a much skewed distribution (a power law distribution). It may be due to time costs constraints on social grooming, because the costs are too large to ignore for having many strong social relationships. Evolution of humans' strategies of construction of social relationships may explain the origin of human intelligence based on a social brain hypothesis. We constructed an individual-based model to explore the evolutionary dynamics of social grooming strategies. The model is based on behavior to win over others by strengthening social relationships with cooperators. The results of evolutionary simulations show the four classes of evolutionary dynamics. The results depend on total resources and the ratio of each cooperator's resource to the number of cooperators. One of the four classes is similar to a human strategy, i.e. the strategies based on the Yule--Simon process of power law.
Large-Scale Low-Rank Matrix Learning with Nonconvex Regularizers
Venue: arXiv cs.LG 2018
Year: 2018

Low-rank modeling has many important applications in computer vision and machine learning. While the matrix rank is often approximated by the convex nuclear norm, the use of nonconvex low-rank regularizers has demonstrated better empirical performance. However, the resulting optimization problem is much more challenging. Recent state-of-the-art requires an expensive full SVD in each iteration. In this paper, we show that for many commonly-used nonconvex low-rank regularizers, a cutoff can be derived to automatically threshold the singular values obtained from the proximal operator. This allows such operator being efficiently approximated by power method. Based on it, we develop a proximal gradient algorithm (and its accelerated variant) with inexact proximal splitting and prove that a convergence rate of O(1/T) where T is the number of iterations is guaranteed. Furthermore, we show the proposed algorithm can be well parallelized, which achieves nearly linear speedup w.r.t the number of threads. Extensive experiments are performed on matrix completion and robust principal component analysis, which shows a significant speedup over the state-of-the-art. Moreover, the matrix solution obtained is more accurate and has a lower rank than that of the nuclear norm regularizer.
Latent Parameter Estimation in Fusion Networks Using Separable Likelihoods
Venue: arXiv cs.SY 2018
Year: 2018

Multi-sensor state space models underpin fusion applications in networks of sensors. Estimation of latent parameters in these models has the potential to provide highly desirable capabilities such as network self-calibration. Conventional solutions to the problem pose difficulties in scaling with the number of sensors due to the joint multi-sensor filtering involved when evaluating the parameter likelihood. In this article, we propose a separable pseudo-likelihood which is a more accurate approximation compared to a previously proposed alternative under typical operating conditions. In addition, we consider using separable likelihoods in the presence of many objects and ambiguity in associating measurements with objects that originated them. To this end, we use a state space model with a hypothesis based parameterisation, and, develop an empirical Bayesian perspective in order to evaluate separable likelihoods on this model using local filtering. Bayesian inference with this likelihood is carried out using belief propagation on the associated pairwise Markov random field. We specify a particle algorithm for latent parameter estimation in a linear Gaussian state space model and demonstrate its efficacy for network self-calibration using measurements from non-cooperative targets in comparison with alternatives.
Optimal Throughput Fairness Trade-offs for Downlink Non-Orthogonal Multiple Access over Fading Channels
Venue: arXiv cs.IT 2018
Year: 2018

Recently, non-orthogonal multiple access (NOMA) has attracted considerable interest as one of the 5G-enabling techniques. However, users with better channel conditions in downlink communications intrinsically benefits from NOMA thanks to successive decoding, judicious designs are required to guarantee user fairness. In this paper, a two-user downlink NOMA system over fading channels is considered. For delay-tolerant transmission, the average sum-rate is maximized subject to both average and peak power constraints as well as a minimum average user rate constraint. The optimal resource allocation is obtained using Lagrangian dual decomposition under full channel state information at the transmitter (CSIT), while an effective power allocation policy under partial CSIT is also developed based on analytical results. In parallel, for delay-limited transmission, the sum of delay-limited throughput (DLT) is maximized subject to a maximum allowable user outage constraint under full CSIT, and the analysis for the sum of DLT is also performed under partial CSIT. Furthermore, an optimal orthogonal multiple access (OMA) scheme is also studied as a benchmark to prove the superiority of NOMA over OMA under full CSIT. Finally, the theoretical analysis is verified by simulations via different trade-offs for the average sum-rate (sum-DLT) versus the minimum (maximum) average user rate (outage) requirement.