OpenRaiser/Intern-Atlas huggingface dataset:
Co-saliency Detection for RGBD Images Based on Multi-constraint Feature Matching and Cross Label Propagation
Venue: arXiv cs.CV 2017
Year: 2017

Co-saliency detection aims at extracting the common salient regions from an image group containing two or more relevant images. It is a newly emerging topic in computer vision community. Different from the most existing co-saliency methods focusing on RGB images, this paper proposes a novel co-saliency detection model for RGBD images, which utilizes the depth information to enhance identification of co-saliency. First, the intra saliency map for each image is generated by the single image saliency model, while the inter saliency map is calculated based on the multi-constraint feature matching, which represents the constraint relationship among multiple images. Then, the optimization scheme, namely Cross Label Propagation (CLP), is used to refine the intra and inter saliency maps in a cross way. Finally, all the original and optimized saliency maps are integrated to generate the final co-saliency result. The proposed method introduces the depth information and multi-constraint feature matching to improve the performance of co-saliency detection. Moreover, the proposed method can effectively exploit any existing single image saliency model to work well in co-saliency scenarios. Experiments on two RGBD co-saliency datasets demonstrate the effectiveness of our proposed model.
Mental Sampling in Multimodal Representations
Venue: arXiv cs.LG 2017
Year: 2017

Both resources in the natural environment and concepts in a semantic space are distributed "patchily", with large gaps in between the patches. To describe people's internal and external foraging behavior, various random walk models have been proposed. In particular, internal foraging has been modeled as sampling: in order to gather relevant information for making a decision, people draw samples from a mental representation using random-walk algorithms such as Markov chain Monte Carlo (MCMC). However, two common empirical observations argue against simple sampling algorithms such as MCMC. First, the spatial structure is often best described by a Lévy flight distribution: the probability of the distance between two successive locations follows a power-law on the distances. Second, the temporal structure of the sampling that humans and other animals produce have long-range, slowly decaying serial correlations characterized as $1/f$-like fluctuations. We propose that mental sampling is not done by simple MCMC, but is instead adapted to multimodal representations and is implemented by Metropolis-coupled Markov chain Monte Carlo (MC$^3$), one of the first algorithms developed for sampling from multimodal distributions. MC$^3$ involves running multiple Markov chains in parallel but with target distributions of different temperatures, and it swaps the states of the chains whenever a better location is found. Heated chains more readily traverse valleys in the probability landscape to propose moves to far-away peaks, while the colder chains make the local steps that explore the current peak or patch. We show that MC$^3$ generates distances between successive samples that follow a Lévy flight distribution and $1/f$-like serial correlations, providing a single mechanistic account of these two puzzling empirical phenomena.
Sparse Message Passing Based Preamble Estimation for Crowded M2M Communications
Venue: arXiv cs.IT 2017
Year: 2017

Due to the massive number of devices in the M2M communication era, new challenges have been brought to the existing random-access (RA) mechanism, such as severe preamble collisions and resource block (RB) wastes. To address these problems, a novel sparse message passing (SMP) algorithm is proposed, based on a factor graph on which Bernoulli messages are updated. The SMP enables an accurate estimation on the activity of the devices and the identity of the preamble chosen by each active device. Aided by the estimation, the RB efficiency for the uplink data transmission can be improved, especially among the collided devices. In addition, an analytical tool is derived to analyze the iterative evolution and convergence of the SMP algorithm. Finally, numerical simulations are provided to verify the validity of our analytical results and the significant improvement of the proposed SMP on estimation error rate even when preamble collision occurs.
LookOut on Time-Evolving Graphs: Succinctly Explaining Anomalies from Any Detector
Venue: arXiv cs.SI 2017
Year: 2017

Why is a given node in a time-evolving graph ($t$-graph) marked as an anomaly by an off-the-shelf detection algorithm? Is it because of the number of its outgoing or incoming edges, or their timings? How can we best convince a human analyst that the node is anomalous? Our work aims to provide succinct, interpretable, and simple explanations of anomalous behavior in $t$-graphs (communications, IP-IP interactions, etc.) while respecting the limited attention of human analysts. Specifically, we extract key features from such graphs, and propose to output a few pair (scatter) plots from this feature space which "best" explain known anomalies. To this end, our work has four main contributions: (a) problem formulation: we introduce an "analyst-friendly" problem formulation for explaining anomalies via pair plots, (b) explanation algorithm: we propose a plot-selection objective and the LookOut algorithm to approximate it with optimality guarantees, (c) generality: our explanation algorithm is both domain- and detector-agnostic, and (d) scalability: we show that LookOut scales linearly on the number of edges of the input graph. Our experiments show that LookOut performs near-ideally in terms of maximizing explanation objective on several real datasets including Enron e-mail and DBLP coauthorship. Furthermore, LookOut produces fast, visually interpretable and intuitive results in explaining "ground-truth" anomalies from Enron, DBLP and LBNL (computer network) data.
A multi-branch convolutional neural network for detecting double JPEG compression
Venue: arXiv cs.CV 2017
Year: 2017

Detection of double JPEG compression is important to forensics analysis. A few methods were proposed based on convolutional neural networks (CNNs). These methods only accept inputs from pre-processed data, such as histogram features and/or decompressed images. In this paper, we present a CNN solution by using raw DCT (discrete cosine transformation) coefficients from JPEG images as input. Considering the DCT sub-band nature in JPEG, a multiple-branch CNN structure has been designed to reveal whether a JPEG format image has been doubly compressed. Comparing with previous methods, the proposed method provides end-to-end detection capability. Extensive experiments have been carried out to demonstrate the effectiveness of the proposed network.
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Venue: arXiv cs.CC 2017
Year: 2017

In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear. Formally, for each depth $Δ\leq \log d$, we show that any product-depth $Δ$ multilinear formula for $\mathrm{IMM}_d$ must have size $\exp(Ω(Δd^{1/Δ})).$ It also follows from this that any multilinear circuit of product-depth $Δ$ for the same polynomial of the above form must have a size of $\exp(Ω(d^{1/Δ})).$ In particular, any polynomial-sized multilinear formula for $\mathrm{IMM}_d$ must have depth $Ω(\log d)$, and any polynomial-sized multilinear circuit for $\mathrm{IMM}_d$ must have depth $Ω(\log d/\log \log d).$ Both these bounds are tight up to constant factors. 1. Depth-reduction: A well-known result of Brent (JACM 1974) implies that any formula of size $s$ can be converted to one of size $s^{O(1)}$ and depth $O(\log s)$; further, this reduction continues to hold for multilinear formulas. Our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to $o(\log s)$ without a superpolynomial blow-up in size. 2. Separations from general formulas: Our result, along with a non-trivial upper bound for $\mathrm{IMM}_{d}$ implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size $s$ and product-depth $Δ= o(\log s),$ general formulas of size $s$ and product-depth $Δ$ cannot be converted to multilinear formulas of size $s^{ω(1)}$ and product-depth $Δ,$ when the underlying field has characteristic zero.
Using Deep Learning and Satellite Imagery to Quantify the Impact of the Built Environment on Neighborhood Crime Rates
Venue: arXiv cs.CY 2017
Year: 2017

The built environment has been postulated to have an impact on neighborhood crime rates, however, measures of the built environment can be subjective and differ across studies leading to varying observations on its association with crime rates. Here, we illustrate an accurate and straightforward approach to quantify the impact of the built environment on neighborhood crime rates from high-resolution satellite imagery. Using geo-referenced crime reports and satellite images for three United States cities, we demonstrate how image features consistently identified using a convolutional neural network can explain up to 82% of the variation in neighborhood crime rates. Our results suggest the built environment is a strong predictor of crime rates, and this can lead to structural interventions shown to reduce crime incidence in urban settings.
A Geometric View of Optimal Transportation and Generative Model
Venue: arXiv cs.LG 2017
Year: 2017

In this work, we show the intrinsic relations between optimal transportation and convex geometry, especially the variational approach to solve Alexandrov problem: constructing a convex polytope with prescribed face normals and volumes. This leads to a geometric interpretation to generative models, and leads to a novel framework for generative models. By using the optimal transportation view of GAN model, we show that the discriminator computes the Kantorovich potential, the generator calculates the transportation map. For a large class of transportation costs, the Kantorovich potential can give the optimal transportation map by a close-form formula. Therefore, it is sufficient to solely optimize the discriminator. This shows the adversarial competition can be avoided, and the computational architecture can be simplified. Preliminary experimental results show the geometric method outperforms WGAN for approximating probability measures with multiple clusters in low dimensional space.
Balanced Judicious Partition is Fixed-Parameter Tractable
Venue: arXiv cs.DS 2017
Year: 2017

The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is "judicious" in the sense that neither side is burdened by too many edges, and Balanced JB also requires that the sizes of the sides themselves are "balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollobás and Scott, and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is FPT (which also proves that JB is FPT).
Collaboration Spheres: a Visual Metaphor to Share and Reuse Research Objects
Venue: arXiv cs.HC 2017
Year: 2017

Research Objects (ROs) are semantically enhanced aggregations of resources associated to scientific experiments, such as data, provenance of these data, the scientific workflow used to run the experiment, intermediate results, logs and the interpretation of the results. As the number of ROs increases, it is becoming difficult to find ROs to be used, reused or re-purposed. New search and retrieval techniques are required to find the most appropriate ROs for a given researcher, paying attention to provide an intuitive user interface. In this paper we show CollabSpheres, a user interface that provides a new visual metaphor to find ROs by means of a recommendation system that takes advantage of the social aspects of ROs. The experimental evaluation of this tool shows that users perceive high values of usability, user satisfaction, usefulness and ease of use. From the analysis of these results we argue that users perceive the simplicity, intuitiveness and cleanness of this tool, as well as this tool increases collaboration and reuse of research objects.
Dual Logic Concepts based on Mathematical Morphology in Stratified Institutions: Applications to Spatial Reasoning
Venue: arXiv cs.LO 2017
Year: 2017

Several logical operators are defined as dual pairs, in different types of logics. Such dual pairs of operators also occur in other algebraic theories, such as mathematical morphology. Based on this observation, this paper proposes to define, at the abstract level of institutions, a pair of abstract dual and logical operators as morphological erosion and dilation. Standard quantifiers and modalities are then derived from these two abstract logical operators. These operators are studied both on sets of states and sets of models. To cope with the lack of explicit set of states in institutions, the proposed abstract logical dual operators are defined in an extension of institutions, the stratified institutions, which take into account the notion of open sentences, the satisfaction of which is parametrized by sets of states. A hint on the potential interest of the proposed framework for spatial reasoning is also provided.
Evolution in Virtual Worlds
Venue: arXiv cs.NE 2017
Year: 2017

This chapter discusses the possibility of instilling a virtual world with mechanisms for evolution and natural selection in order to generate rich ecosystems of complex organisms in a process akin to biological evolution. Some previous work in the area is described, and successes and failures are discussed. The components of a more comprehensive framework for designing such worlds are mapped out, including the design of the individual organisms, the properties and dynamics of the environmental medium in which they are evolving, and the representational relationship between organism and environment. Some of the key issues discussed include how to allow organisms to evolve new structures and functions with few restrictions, and how to create an interconnectedness between organisms in order to generate drives for continuing evolutionary activity.
Cinnamons: A Computation Model Underlying Control Network Programming
Venue: arXiv cs.PL 2017
Year: 2017

We give the easily recognizable name "cinnamon" and "cinnamon programming" to a new computation model intended to form a theoretical foundation for Control Network Programming (CNP). CNP has established itself as a programming paradigm combining declarative and imperative features, built-in search engine, powerful tools for search control that allow easy, intuitive, visual development of heuristic, nondeterministic, and randomized solutions. We define rigorously the syntax and semantics of the new model of computation, at the same time trying to keep clear the intuition behind and to include enough examples. The purposely simplified theoretical model is then compared to both WHILE-programs (thus demonstrating its Turing-completeness), and the "real" CNP. Finally, future research possibilities are mentioned that would eventually extend the cinnamon programming into the directions of nondeterminism, randomness, and fuzziness.
Towards Linux Kernel Memory Safety
Venue: arXiv cs.CR 2017
Year: 2017

The security of billions of devices worldwide depends on the security and robustness of the mainline Linux kernel. However, the increasing number of kernel-specific vulnerabilities, especially memory safety vulnerabilities, shows that the kernel is a popular and practically exploitable target. Two major causes of memory safety vulnerabilities are reference counter overflows (temporal memory errors) and lack of pointer bounds checking (spatial memory errors). To succeed in practice, security mechanisms for critical systems like the Linux kernel must also consider performance and deployability as critical design objectives. We present and systematically analyze two such mechanisms for improving memory safety in the Linux kernel: (a) an overflow-resistant reference counter data structure designed to accommodate typical reference counter usage in kernel source code, and (b) runtime pointer bounds checking using Intel MPX in the kernel.
Computation of gray-level co-occurrence matrix based on CUDA and its optimization
Venue: arXiv cs.PF 2017
Year: 2017

As in various fields like scientific research and industrial application, the computation time optimization is becoming a task that is of increasing importance because of its highly parallel architecture. The graphics processing unit is regarded as a powerful engine for application programs that demand fairly high computation capabilities. Based on this, an algorithm was introduced in this paper to optimize the method used to compute the gray-level co-occurrence matrix (GLCM) of an image, and strategies (e.g., "copying", "image partitioning", etc.) were proposed to optimize the parallel algorithm. Results indicate that without losing the computational accuracy, the speed-up ratio of the GLCM computation of images with different resolutions by GPU by the use of CUDA was 50 times faster than that of the GLCM computation by CPU, which manifested significantly improved performance.
Analysis of feature detector and descriptor combinations with a localization experiment for various performance metrics
Venue: arXiv cs.CV 2017
Year: 2017

The purpose of this study is to provide a detailed performance comparison of feature detector/descriptor methods, particularly when their various combinations are used for image-matching. The localization experiments of a mobile robot in an indoor environment are presented as a case study. In these experiments, 3090 query images and 127 dataset images were used. This study includes five methods for feature detectors (features from accelerated segment test (FAST), oriented FAST and rotated binary robust independent elementary features (BRIEF) (ORB), speeded-up robust features (SURF), scale invariant feature transform (SIFT), and binary robust invariant scalable keypoints (BRISK)) and five other methods for feature descriptors (BRIEF, BRISK, SIFT, SURF, and ORB). These methods were used in 23 different combinations and it was possible to obtain meaningful and consistent comparison results using the performance criteria defined in this study. All of these methods were used independently and separately from each other as either feature detector or descriptor. The performance analysis shows the discriminative power of various combinations of detector and descriptor methods. The analysis is completed using five parameters: (i) accuracy, (ii) time, (iii) angle difference between keypoints, (iv) number of correct matches, and (v) distance between correctly matched keypoints. In a range of 60°, covering five rotational pose points for our system, the FAST-SURF combination had the lowest distance and angle difference values and the highest number of matched keypoints. SIFT-SURF was the most accurate combination with a 98.41% correct classification rate. The fastest algorithm was ORB-BRIEF, with a total running time of 21,303.30 s to match 560 images captured during motion with 127 dataset images.
Fishing for Clickbaits in Social Images and Texts with Linguistically-Infused Neural Network Models
Venue: arXiv cs.LG 2017
Year: 2017

This paper presents the results and conclusions of our participation in the Clickbait Challenge 2017 on automatic clickbait detection in social media. We first describe linguistically-infused neural network models and identify informative representations to predict the level of clickbaiting present in Twitter posts. Our models allow to answer the question not only whether a post is a clickbait or not, but to what extent it is a clickbait post e.g., not at all, slightly, considerably, or heavily clickbaity using a score ranging from 0 to 1. We evaluate the predictive power of models trained on varied text and image representations extracted from tweets. Our best performing model that relies on the tweet text and linguistic markers of biased language extracted from the tweet and the corresponding page yields mean squared error (MSE) of 0.04, mean absolute error (MAE) of 0.16 and R2 of 0.43 on the held-out test data. For the binary classification setup (clickbait vs. non-clickbait), our model achieved F1 score of 0.69. We have not found that image representations combined with text yield significant performance improvement yet. Nevertheless, this work is the first to present preliminary analysis of objects extracted using Google Tensorflow object detection API from images in clickbait vs. non-clickbait Twitter posts. Finally, we outline several steps to improve model performance as a part of the future work.
RETUYT in TASS 2017: Sentiment Analysis for Spanish Tweets using SVM and CNN
Venue: arXiv cs.CL 2017
Year: 2017

This article presents classifiers based on SVM and Convolutional Neural Networks (CNN) for the TASS 2017 challenge on tweets sentiment analysis. The classifier with the best performance in general uses a combination of SVM and CNN. The use of word embeddings was particularly useful for improving the classifiers performance.
Laying Down the Yellow Brick Road: Development of a Wizard-of-Oz Interface for Collecting Human-Robot Dialogue
Venue: arXiv cs.CL 2017
Year: 2017

We describe the adaptation and refinement of a graphical user interface designed to facilitate a Wizard-of-Oz (WoZ) approach to collecting human-robot dialogue data. The data collected will be used to develop a dialogue system for robot navigation. Building on an interface previously used in the development of dialogue systems for virtual agents and video playback, we add templates with open parameters which allow the wizard to quickly produce a wide variety of utterances. Our research demonstrates that this approach to data collection is viable as an intermediate step in developing a dialogue system for physical robots in remote locations from their users - a domain in which the human and robot need to regularly verify and update a shared understanding of the physical environment. We show that our WoZ interface and the fixed set of utterances and templates therein provide for a natural pace of dialogue with good coverage of the navigation domain.
Successive Four-Dimensional Stokes-Space Direct Detection
Venue: arXiv cs.IT 2017
Year: 2017

We present a successive detection scheme for the fourth dimension in a four-dimensional Stokes-space direct detection receiver. At the expense of a small number of electrical-domain computations, the additional information rate can be substantial.