OpenRaiser/Intern-Atlas huggingface dataset:
Faster batched range minimum queries
Venue: arXiv cs.DS 2017
Year: 2017

Range Minimum Query (RMQ) is an important building brick of many compressed data structures and string matching algorithms. Although this problem is essentially solved in theory, with sophisticated data structures allowing for constant time queries, there are scenarios in which the number of queries, $q$, is rather small and given beforehand, which encourages to use a simpler approach. A recent work by Alzamel et al. starts with contracting the input array to a much shorter one, with its size proportional to $q$. In this work, we build upon their solution, speeding up handling small batches of queries by a factor of 3.8--7.8 (the gap grows with $q$). The key idea that helped us achieve this advantage is adapting the well-known Sparse Table technique to work on blocks, with speculative block minima comparisons. We also propose an even much faster (but possibly using more space) variant without the array contraction.
Ensemble Framework for Real-time Decision Making
Venue: arXiv cs.AI 2017
Year: 2017

This paper introduces a new framework for real-time decision making in video games. An Ensemble agent is a compound agent composed of multiple agents, each with its own tasks or goals to achieve. Usually when dealing with real-time decision making, reactive agents are used; that is agents that return a decision based on the current state. While reactive agents are very fast, most games require more than just a rule-based agent to achieve good results. Deliberative agents---agents that use a forward model to search future states---are very useful in games with no hard time limit, such as Go or Backgammon, but generally take too long for real-time games. The Ensemble framework addresses this issue by allowing the agent to be both deliberative and reactive at the same time. This is achieved by breaking up the game-play into logical roles and having highly focused components for each role, with each component disregarding anything outwith its own role. Reactive agents can be used where a reactive agent is suited to the role, and where a deliberative approach is required, branching is kept to a minimum by the removal of all extraneous factors, enabling an informed decision to be made within a much smaller time-frame. An Arbiter is used to combine the component results, allowing high performing agents to be created from simple, efficient components.
Web-STAR: Towards a Visual Web-Based IDE for a Story Comprehension System
Venue: arXiv cs.HC 2017
Year: 2017

In this work, we present Web-STAR, an online platform for story understanding built on top of the STAR (STory comprehension through ARgumentation) reasoning engine. This platform includes a web-based IDE, integration with the STAR system and a web service infrastructure to support integration with other systems that rely on story understanding functionality to complete their tasks. The platform also delivers a number of "social" features like public story sharing with a built-in commenting system, a public repository for sharing stories with the community and collaboration tools that can be used from both project team members for development and educators for teaching. Moreover, we discuss the ongoing work on adding new features and functionality to this platform.
Scalable Online Convolutional Sparse Coding
Venue: arXiv cs.CV 2017
Year: 2017

Convolutional sparse coding (CSC) improves sparse coding by learning a shift-invariant dictionary from the data. However, existing CSC algorithms operate in the batch mode and are expensive, in terms of both space and time, on large datasets. In this paper, we alleviate these problems by using online learning. The key is a reformulation of the CSC objective so that convolution can be handled easily in the frequency domain and much smaller history matrices are needed. We use the alternating direction method of multipliers (ADMM) to solve the resulting optimization problem and the ADMM subproblems have efficient closed-form solutions. Theoretical analysis shows that the learned dictionary converges to a stationary point of the optimization problem. Extensive experiments show that convergence of the proposed method is much faster and its reconstruction performance is also better. Moreover, while existing CSC algorithms can only run on a small number of images, the proposed method can handle at least ten times more images.
On the enumeration of sentences by compactness
Venue: arXiv cs.AI 2017
Year: 2017

Presented is a Julia meta-program that discovers compact theories from data if they exist. It writes candidate theories in Julia and then validates: tossing the bad theories and keeping the good theories. Compactness is measured by a metric: such as the number of space-time derivatives. The underlying algorithm is applicable to a wide variety of combinatorics problems and compactness serves to cut down the search space.
The Capacity of Cache Aided Private Information Retrieval
Venue: arXiv cs.IT 2017
Year: 2017

The problem of cache enabled private information retrieval (PIR) is considered in which a user wishes to privately retrieve one out of $K$ messages, each of size $L$ bits from $N$ distributed databases. The user has a local cache of storage $SL$ bits which can be used to store any function of the $K$ messages. The main contribution of this work is the exact characterization of the capacity of cache aided PIR as a function of the storage parameter $S$. In particular, for a given cache storage parameter $S$, the information-theoretically optimal download cost $D^{*}(S)/L$ (or the inverse of capacity) is shown to be equal to $(1- \frac{S}{K})\left(1+ \frac{1}{N}+ \ldots + \frac{1}{N^{K-1}}\right)$. Special cases of this result correspond to the settings when $S=0$, for which the optimal download cost was shown by Sun and Jafar to be $\left(1+ \frac{1}{N}+ \ldots + \frac{1}{N^{K-1}}\right)$, and the case when $S=K$, i.e., cache size is large enough to store all messages locally, for which the optimal download cost is $0$. The intermediate points $S\in (0, K)$ can be readily achieved through a simple memory-sharing based PIR scheme. The key technical contribution of this work is the converse, i.e., a lower bound on the download cost as a function of storage $S$ which shows that memory sharing is information-theoretically optimal.
Curvature-aware Manifold Learning
Venue: arXiv cs.LG 2017
Year: 2017

Traditional manifold learning algorithms assumed that the embedded manifold is globally or locally isometric to Euclidean space. Under this assumption, they divided manifold into a set of overlapping local patches which are locally isometric to linear subsets of Euclidean space. By analyzing the global or local isometry assumptions it can be shown that the learnt manifold is a flat manifold with zero Riemannian curvature tensor. In general, manifolds may not satisfy these hypotheses. One major limitation of traditional manifold learning is that it does not consider the curvature information of manifold. In order to remove these limitations, we present our curvature-aware manifold learning algorithm called CAML. The purpose of our algorithm is to break the local isometry assumption and to reduce the dimension of the general manifold which is not isometric to Euclidean space. Thus, our method adds the curvature information to the process of manifold learning. The experiments have shown that our method CAML is more stable than other manifold learning algorithms by comparing the neighborhood preserving ratios.
The Principal Fiber Bundle Structure of the Gimbal-Spacecraft System
Venue: arXiv cs.SY 2017
Year: 2017

The gimbal-spacecraft system, that consists of a variable speed control moment gyro (VSCMG) mounted inside a spacecraft, has been employed as an actuator for the attitude control of a spacecraft and has been much studied in the aerospace control community. Employing a Newtonian approach, the equations of motion are derived, and further study focusses on singularity issues and control law synthesis. While the geometric mechanics community has studied many mechanical systems of engineering interest, including spinning rotors (or momentum wheels) that are used as actuators, there has not been a particular effort to model and control the gimbal-spacecraft system in a geometric framework. This article serves two purposes: it presents the gimbal-spacecraft system in a geometric mechanics framework, and in particular, highlights the connection form, that could form the basis for future control design, and secondly, the exposition is of a tutorial nature whereby the willing reader, with minimal prerequisites, is introduced to the tools of differential geometry in this context.
A Community's Perspective on the Status and Future of Peer Review in Software Engineering
Venue: arXiv cs.SE 2017
Year: 2017

Context: Pre-publication peer review of scientific articles is considered a key element of the research process in software engineering, yet it is often perceived as not to work fully well. Objective: We aim at understanding the perceptions of and attitudes towards peer review of authors and reviewers at one of software engineering's most prestigious venues, the International Conference on Software Engineering (ICSE). Method: We invited 932 ICSE 2014/15/16 authors and reviewers to participate in a survey with 10 closed and 9 open questions. Results: We present a multitude of results, such as: Respondents perceive only one third of all reviews to be good, yet one third as useless or misleading; they propose double-blind or zero-blind reviewing regimes for improvement; they would like to see showable proofs of (good) reviewing work be introduced; attitude change trends are weak. Conclusion: The perception of the current state of software engineering peer review is fairly negative. Also, we found hardly any trend that suggests reviewing will improve by itself over time; the community will have to make explicit efforts. Fortunately, our (mostly senior) respondents appear more open for trying different peer reviewing regimes than we had expected.
Living Labs - An Ethical Challenge for Researchers and Platform Providers
Venue: arXiv cs.CY 2017
Year: 2017

The infamous Facebook emotion contagion experiment is one of the most prominent and best-known online experiments based on the concept of what we here call "living labs". In these kinds of experiments, real-world applications such as social web platforms trigger experimental switches inside their system to present experimental changes to their users - most of the time without the users being aware of their role as virtual guinea pigs. In the Facebook example the researches changed the way users' personal timeline was compiled to test the influence on the users' moods and feelings. The reactions to these experiments showed the inherent ethical issues such living labs settings bring up, mainly the study's lack of informed consent procedures, as well as a more general critique of the flaws in the experimental design. In this chapter, we describe additional use cases: The so-called living labs that focus on experimentation with information systems such as search engines and wikis and especially on their real-world usage. The living labs paradigm allows researchers to conduct research in real-world environments or systems. In the field of information science and especially information retrieval - which is the scientific discipline that is concerned with the research of search engines, information systems, and search related algorithms and techniques - it is still common practice to perform in vitro or offline evaluations using static test collections. Living labs are widely unknown or unavailable to academic researchers in these fields. A main benefit of living labs is their potential to offer new ways and possibilities to experiment with information systems and especially their users, but on the other hand they introduce a whole set of ethical issues that we would like to address in this chapter.
New Cardinality Estimation Methods for HyperLogLog Sketches
Venue: arXiv cs.DS 2017
Year: 2017

This work presents new cardinality estimation methods for data sets recorded by HyperLogLog sketches. A simple derivation of the original estimator was found, that also gives insight how to correct its deficiencies. The result is an improved estimator that is unbiased over the full cardinality range, is easy computable, and does not rely on empirically determined data as previous approaches. Based on the maximum likelihood principle a second unbiased estimation method is presented which can also be extended to estimate cardinalities of union, intersection, or relative complements of two sets that are both represented as HyperLogLog sketches. Experimental results show that this approach is more precise than the conventional technique using the inclusion-exclusion principle.
An approach to reachability analysis for feed-forward ReLU neural networks
Venue: arXiv cs.AI 2017
Year: 2017

We study the reachability problem for systems implemented as feed-forward neural networks whose activation function is implemented via ReLU functions. We draw a correspondence between establishing whether some arbitrary output can ever be outputed by a neural system and linear problems characterising a neural system of interest. We present a methodology to solve cases of practical interest by means of a state-of-the-art linear programs solver. We evaluate the technique presented by discussing the experimental results obtained by analysing reachability properties for a number of benchmarks in the literature.
Reconstructing the Forest of Lineage Trees of Diverse Bacterial Communities Using Bio-inspired Image Analysis
Venue: arXiv cs.CV 2017
Year: 2017

Cell segmentation and tracking allow us to extract a plethora of cell attributes from bacterial time-lapse cell movies, thus promoting computational modeling and simulation of biological processes down to the single-cell level. However, to analyze successfully complex cell movies, imaging multiple interacting bacterial clones as they grow and merge to generate overcrowded bacterial communities with thousands of cells in the field of view, segmentation results should be near perfect to warrant good tracking results. We introduce here a fully automated closed-loop bio-inspired computational strategy that exploits prior knowledge about the expected structure of a colony's lineage tree to locate and correct segmentation errors in analyzed movie frames. We show that this correction strategy is effective, resulting in improved cell tracking and consequently trustworthy deep colony lineage trees. Our image analysis approach has the unique capability to keep tracking cells even after clonal subpopulations merge in the movie. This enables the reconstruction of the complete Forest of Lineage Trees (FLT) representation of evolving multi-clonal bacterial communities. Moreover, the percentage of valid cell trajectories extracted from the image analysis almost doubles after segmentation correction. This plethora of trustworthy data extracted from a complex cell movie analysis enables single-cell analytics as a tool for addressing compelling questions for human health, such as understanding the role of single-cell stochasticity in antibiotics resistance without losing site of the inter-cellular interactions and microenvironment effects that may shape it.
Improved Approximate Rips Filtrations with Shifted Integer Lattices
Venue: arXiv cs.CG 2017
Year: 2017

Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes constitutes an expensive task because of a combinatorial explosion in the complex size. For $n$ points in $\mathbb{R}^d$, we present a scheme to construct a $3\sqrt{2}$-approximation of the multi-scale filtration of the $L_\infty$-Rips complex, which extends to a $O(d^{0.25})$-approximation of the Rips filtration for the Euclidean case. The $k$-skeleton of the resulting approximation has a total size of $n2^{O(d\log k)}$. The scheme is based on the integer lattice and on the barycentric subdivision of the $d$-cube.
Inter-Session Modeling for Session-Based Recommendation
Venue: arXiv cs.IR 2017
Year: 2017

In recent years, research has been done on applying Recurrent Neural Networks (RNNs) as recommender systems. Results have been promising, especially in the session-based setting where RNNs have been shown to outperform state-of-the-art models. In many of these experiments, the RNN could potentially improve the recommendations by utilizing information about the user's past sessions, in addition to its own interactions in the current session. A problem for session-based recommendation, is how to produce accurate recommendations at the start of a session, before the system has learned much about the user's current interests. We propose a novel approach that extends a RNN recommender to be able to process the user's recent sessions, in order to improve recommendations. This is done by using a second RNN to learn from recent sessions, and predict the user's interest in the current session. By feeding this information to the original RNN, it is able to improve its recommendations. Our experiments on two different datasets show that the proposed approach can significantly improve recommendations throughout the sessions, compared to a single RNN working only on the current session. The proposed model especially improves recommendations at the start of sessions, and is therefore able to deal with the cold start problem within sessions.
Model Selection with Nonlinear Embedding for Unsupervised Domain Adaptation
Venue: arXiv cs.AI 2017
Year: 2017

Domain adaptation deals with adapting classifiers trained on data from a source distribution, to work effectively on data from a target distribution. In this paper, we introduce the Nonlinear Embedding Transform (NET) for unsupervised domain adaptation. The NET reduces cross-domain disparity through nonlinear domain alignment. It also embeds the domain-aligned data such that similar data points are clustered together. This results in enhanced classification. To determine the parameters in the NET model (and in other unsupervised domain adaptation models), we introduce a validation procedure by sampling source data points that are similar in distribution to the target data. We test the NET and the validation procedure using popular image datasets and compare the classification results across competitive procedures for unsupervised domain adaptation.
Multiresolution Match Kernels for Gesture Video Classification
Venue: arXiv cs.CV 2017
Year: 2017

The emergence of depth imaging technologies like the Microsoft Kinect has renewed interest in computational methods for gesture classification based on videos. For several years now, researchers have used the Bag-of-Features (BoF) as a primary method for generation of feature vectors from video data for recognition of gestures. However, the BoF method is a coarse representation of the information in a video, which often leads to poor similarity measures between videos. Besides, when features extracted from different spatio-temporal locations in the video are pooled to create histogram vectors in the BoF method, there is an intrinsic loss of their original locations in space and time. In this paper, we propose a new Multiresolution Match Kernel (MMK) for video classification, which can be considered as a generalization of the BoF method. We apply this procedure to hand gesture classification based on RGB-D videos of the American Sign Language(ASL) hand gestures and our results show promise and usefulness of this new method.
Fundamental Limits of Universal Variable-to-Fixed Length Coding of Parametric Sources
Venue: arXiv cs.IT 2017
Year: 2017

Universal variable-to-fixed (V-F) length coding of $d$-dimensional exponential family of distributions is considered. We propose an achievable scheme consisting of a dictionary, used to parse the source output stream, making use of the previously-introduced notion of quantized types. The quantized type class of a sequence is based on partitioning the space of minimal sufficient statistics into cuboids. Our proposed dictionary consists of sequences in the boundaries of transition from low to high quantized type class size. We derive the asymptotics of the $ε$-coding rate of our coding scheme for large enough dictionaries. In particular, we show that the third-order coding rate of our scheme is $H\frac{d}{2}\frac{\log\log M}{\log M}$, where $H$ is the entropy of the source and $M$ is the dictionary size. We further provide a converse, showing that this rate is optimal up to the third-order term.
Toward Faultless Content-Based Playlists Generation for Instrumentals
Venue: arXiv cs.SD 2017
Year: 2017

This study deals with content-based musical playlists generation focused on Songs and Instrumentals. Automatic playlist generation relies on collaborative filtering and autotagging algorithms. Autotagging can solve the cold start issue and popularity bias that are critical in music recommender systems. However, autotagging remains to be improved and cannot generate satisfying music playlists. In this paper, we suggest improvements toward better autotagging-generated playlists compared to state-of-the-art. To assess our method, we focus on the Song and Instrumental tags. Song and Instrumental are two objective and opposite tags that are under-studied compared to genres or moods, which are subjective and multi-modal tags. In this paper, we consider an industrial real-world musical database that is unevenly distributed between Songs and Instrumentals and bigger than databases used in previous studies. We set up three incremental experiments to enhance automatic playlist generation. Our suggested approach generates an Instrumental playlist with up to three times less false positives than cutting edge methods. Moreover, we provide a design of experiment framework to foster research on Songs and Instrumentals. We give insight on how to improve further the quality of generated playlists and to extend our methods to other musical tags. Furthermore, we provide the source code to guarantee reproducible research.
Computational Controversy
Venue: arXiv cs.CY 2017
Year: 2017

Climate change, vaccination, abortion, Trump: Many topics are surrounded by fierce controversies. The nature of such heated debates and their elements have been studied extensively in the social science literature. More recently, various computational approaches to controversy analysis have appeared, using new data sources such as Wikipedia, which help us now better understand these phenomena. However, compared to what social sciences have discovered about such debates, the existing computational approaches mostly focus on just a few of the many important aspects around the concept of controversies. In order to link the two strands, we provide and evaluate here a controversy model that is both, rooted in the findings of the social science literature and at the same time strongly linked to computational methods. We show how this model can lead to computational controversy analytics that have full coverage over all the crucial aspects that make up a controversy.