OpenRaiser/Intern-Atlas huggingface dataset:
Learning Regular Languages over Large Ordered Alphabets
Venue: arXiv cs.LO 2015
Year: 2015

This work is concerned with regular languages defined over large alphabets, either infinite or just too large to be expressed enumeratively. We define a generic model where transitions are labeled by elements of a finite partition of the alphabet. We then extend Angluin's L* algorithm for learning regular languages from examples for such automata. We have implemented this algorithm and we demonstrate its behavior where the alphabet is a subset of the natural or real numbers. We sketch the extension of the algorithm to a class of languages over partially ordered alphabets.
Blocks and Fuel: Frameworks for deep learning
Venue: arXiv cs.LG 2015
Year: 2015

We introduce two Python frameworks to train neural networks on large datasets: Blocks and Fuel. Blocks is based on Theano, a linear algebra compiler with CUDA-support. It facilitates the training of complex neural network models by providing parametrized Theano operations, attaching metadata to Theano's symbolic computational graph, and providing an extensive set of utilities to assist training the networks, e.g. training algorithms, logging, monitoring, visualization, and serialization. Fuel provides a standard format for machine learning datasets. It allows the user to easily iterate over large datasets, performing many types of pre-processing on the fly.
Model-based reinforcement learning for infinite-horizon approximate optimal tracking
Venue: arXiv cs.SY 2015
Year: 2015

This paper provides an approximate online adaptive solution to the infinite-horizon optimal tracking problem for control-affine continuous-time nonlinear systems with unknown drift dynamics. Model-based reinforcement learning is used to relax the persistence of excitation condition. Model-based reinforcement learning is implemented using a concurrent learning-based system identifier to simulate experience by evaluating the Bellman error over unexplored areas of the state space. Tracking of the desired trajectory and convergence of the developed policy to a neighborhood of the optimal policy are established via Lyapunov-based stability analysis. Simulation results demonstrate the effectiveness of the developed technique.
Tackling Exascale Software Challenges in Molecular Dynamics Simulations with GROMACS
Venue: arXiv cs.CE 2015
Year: 2015

GROMACS is a widely used package for biomolecular simulation, and over the last two decades it has evolved from small-scale efficiency to advanced heterogeneous acceleration and multi-level parallelism targeting some of the largest supercomputers in the world. Here, we describe some of the ways we have been able to realize this through the use of parallelization on all levels, combined with a constant focus on absolute performance. Release 4.6 of GROMACS uses SIMD acceleration on a wide range of architectures, GPU offloading acceleration, and both OpenMP and MPI parallelism within and between nodes, respectively. The recent work on acceleration made it necessary to revisit the fundamental algorithms of molecular simulation, including the concept of neighborsearching, and we discuss the present and future challenges we see for exascale simulation - in particular a very fine-grained task parallelism. We also discuss the software management, code peer review and continuous integration testing required for a project of this complexity.
What Makes Kevin Spacey Look Like Kevin Spacey
Venue: arXiv cs.CV 2015
Year: 2015

We reconstruct a controllable model of a person from a large photo collection that captures his or her {\em persona}, i.e., physical appearance and behavior. The ability to operate on unstructured photo collections enables modeling a huge number of people, including celebrities and other well photographed people without requiring them to be scanned. Moreover, we show the ability to drive or {\em puppeteer} the captured person B using any other video of a different person A. In this scenario, B acts out the role of person A, but retains his/her own personality and character. Our system is based on a novel combination of 3D face reconstruction, tracking, alignment, and multi-texture modeling, applied to the puppeteering problem. We demonstrate convincing results on a large variety of celebrities derived from Internet imagery and video.
Where to Go on Your Next Trip? Optimizing Travel Destinations Based on User Preferences
Venue: arXiv cs.IR 2015
Year: 2015

Recommendation based on user preferences is a common task for e-commerce websites. New recommendation algorithms are often evaluated by offline comparison to baseline algorithms such as recommending random or the most popular items. Here, we investigate how these algorithms themselves perform and compare to the operational production system in large scale online experiments in a real-world application. Specifically, we focus on recommending travel destinations at Booking.com, a major online travel site, to users searching for their preferred vacation activities. To build ranking models we use multi-criteria rating data provided by previous users after their stay at a destination. We implement three methods and compare them to the current baseline in Booking.com: random, most popular, and Naive Bayes. Our general conclusion is that, in an online A/B test with live users, our Naive-Bayes based ranker increased user engagement significantly over the current online system.
Assessing Inconspicuous Smartphone Authentication for Blind People
Venue: arXiv cs.HC 2015
Year: 2015

As people store more personal data in their smartphones, the consequences of having it stolen or lost become an increasing concern. A typical counter-measure to avoid this risk is to set up a secret code that has to be entered to unlock the device after a period of inactivity. However, for blind users, PINs and passwords are inadequate, since entry 1) consumes a non-trivial amount of time, e.g. using screen readers, 2) is susceptible to observation, where nearby people can see or hear the secret code, and 3) might collide with social norms, e.g. disrupting personal interactions. Tap-based authentication methods have been presented and allow unlocking to be performed in a short time and support naturally occurring inconspicuous behavior (e.g. concealing the device inside a jacket) by being usable with a single hand. This paper presents a study with blind users (N = 16) where an authentication method based on tap phrases is evaluated. Results showed the method to be usable and to support the desired inconspicuity.
Data-Driven Diagnostics of Mechanism and Source of Sustained Oscillations
Venue: arXiv cs.SY 2015
Year: 2015

Sustained oscillations observed in power systems can damage equipment, degrade the power quality and increase the risks of cascading blackouts. There are several mechanisms that can give rise to oscillations, each requiring different countermeasure to suppress or eliminate the oscillation. This work develops mathematical framework for analysis of sustained oscillations and identifies statistical signatures of each mechanism, based on which a novel oscillation diagnosis method is developed via real-time processing of phasor measurement units (PMUs) data. Case studies show that the proposed method can accurately identify the exact mechanism for sustained oscillation, and meanwhile provide insightful information to locate the oscillation sources.
Game Theory for Signal Processing in Networks
Venue: arXiv cs.GT 2015
Year: 2015

In this tutorial, the basics of game theory are introduced along with an overview of its most recent and emerging applications in signal processing. One of the main features of this contribution is to gather in a single paper some fundamental game-theoretic notions and tools which, over the past few years, have become widely spread over a large number of papers. In particular, both strategic-form and coalition-form games are described in details while the key connections and differences between them are outlined. Moreover, a particular attention is also devoted to clarify the connections between strategic-form games and distributed optimization and learning algorithms. Beyond an introduction to the basic concepts and main solution approaches, several carefully designed examples are provided to allow a better understanding of how to apply the described tools.
Learning Agent for a Heat-Pump Thermostat With a Set-Back Strategy Using Model-Free Reinforcement Learning
Venue: arXiv cs.SY 2015
Year: 2015

The conventional control paradigm for a heat pump with a less efficient auxiliary heating element is to keep its temperature set point constant during the day. This constant temperature set point ensures that the heat pump operates in its more efficient heat-pump mode and minimizes the risk of activating the less efficient auxiliary heating element. As an alternative to a constant set-point strategy, this paper proposes a learning agent for a thermostat with a set-back strategy. This set-back strategy relaxes the set-point temperature during convenient moments, e.g. when the occupants are not at home. Finding an optimal set-back strategy requires solving a sequential decision-making process under uncertainty, which presents two challenges. A first challenge is that for most residential buildings a description of the thermal characteristics of the building is unavailable and challenging to obtain. A second challenge is that the relevant information on the state, i.e. the building envelope, cannot be measured by the learning agent. In order to overcome these two challenges, our paper proposes an auto-encoder coupled with a batch reinforcement learning technique. The proposed approach is validated for two building types with different thermal characteristics for heating in the winter and cooling in the summer. The simulation results indicate that the proposed learning agent can reduce the energy consumption by 4-9% during 100 winter days and by 9-11% during 80 summer days compared to the conventional constant set-point strategy
Global and Local Structure Preserving Sparse Subspace Learning: An Iterative Approach to Unsupervised Feature Selection
Venue: arXiv cs.LG 2015
Year: 2015

As we aim at alleviating the curse of high-dimensionality, subspace learning is becoming more popular. Existing approaches use either information about global or local structure of the data, and few studies simultaneously focus on global and local structures as the both of them contain important information. In this paper, we propose a global and local structure preserving sparse subspace learning (GLoSS) model for unsupervised feature selection. The model can simultaneously realize feature selection and subspace learning. In addition, we develop a greedy algorithm to establish a generic combinatorial model, and an iterative strategy based on an accelerated block coordinate descent is used to solve the GLoSS problem. We also provide whole iterate sequence convergence analysis of the proposed iterative algorithm. Extensive experiments are conducted on real-world datasets to show the superiority of the proposed approach over several state-of-the-art unsupervised feature selection approaches.
Fast Generation of Best Interval Patterns for Nonmonotonic Constraints
Venue: arXiv cs.AI 2015
Year: 2015

In pattern mining, the main challenge is the exponential explosion of the set of patterns. Typically, to solve this problem, a constraint for pattern selection is introduced. One of the first constraints proposed in pattern mining is support (frequency) of a pattern in a dataset. Frequency is an anti-monotonic function, i.e., given an infrequent pattern, all its superpatterns are not frequent. However, many other constraints for pattern selection are not (anti-)monotonic, which makes it difficult to generate patterns satisfying these constraints. In this paper we introduce the notion of projection-antimonotonicity and $θ$-$\Sigmaøϕια$ algorithm that allows efficient generation of the best patterns for some nonmonotonic constraints. In this paper we consider stability and $Δ$-measure, which are nonmonotonic constraints, and apply them to interval tuple datasets. In the experiments, we compute best interval tuple patterns w.r.t. these measures and show the advantage of our approach over postfiltering approaches. KEYWORDS: Pattern mining, nonmonotonic constraints, interval tuple data
On bicluster aggregation and its benefits for enumerative solutions
Venue: arXiv cs.LG 2015
Year: 2015

Biclustering involves the simultaneous clustering of objects and their attributes, thus defining local two-way clustering models. Recently, efficient algorithms were conceived to enumerate all biclusters in real-valued datasets. In this case, the solution composes a complete set of maximal and non-redundant biclusters. However, the ability to enumerate biclusters revealed a challenging scenario: in noisy datasets, each true bicluster may become highly fragmented and with a high degree of overlapping. It prevents a direct analysis of the obtained results. To revert the fragmentation, we propose here two approaches for properly aggregating the whole set of enumerated biclusters: one based on single linkage and the other directly exploring the rate of overlapping. Both proposals were compared with each other and with the actual state-of-the-art in several experiments, and they not only significantly reduced the number of biclusters but also consistently increased the quality of the solution.
An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication
Venue: arXiv cs.DS 2015
Year: 2015

The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et.al. in 1977. As any algorithm falling within the Reverse Search paradigm, it performs a DFS visit of a directed tree (the RS-tree) having the objects to be listed (i.e. maximal cliques) as its nodes. In a recursive implementation, the RS-tree corresponds to the recursion tree of the algorithm. The time delay is given by the cost of generating the next child of a node, and Tsukiyama showed it is $O(mn)$. In 2004, Makino and Uno sharpened the time delay to $O(n^ω)$ by generating all the children of a node in one single shot performed by computing a \emph{square} fast matrix multiplication. In this paper, we further improve the asymptotics for the exploration of the same RS-tree by grouping the offsprings' computation even further. Our idea is to rely on rectangular fast matrix multiplication in order to compute all children of $n^2$ nodes in one shot. According to the current upper bounds on fast matrix multiplication, with this the time delay improves from $O(n^{2.3728639})$ to $O(n^{2.093362})$.
Efficient Channel-Hopping Rendezvous Algorithm Based on Available Channel Set
Venue: arXiv cs.NI 2015
Year: 2015

In cognitive radio networks, rendezvous is a fundamental operation by which two cognitive users establish a communication link on a commonly-available channel for communications. Some existing rendezvous algorithms can guarantee that rendezvous can be completed within finite time and they generate channel-hopping (CH) sequences based on the whole channel set. However, some channels may not be available (e.g., they are being used by the licensed users) and these existing algorithms would randomly replace the unavailable channels in the CH sequence. This random replacement is not effective, especially when the number of unavailable channels is large. In this paper, we design a new rendezvous algorithm that attempts rendezvous on the available channels only for faster rendezvous. This new algorithm, called Interleaved Sequences based on Available Channel set (ISAC), constructs an odd sub-sequence and an even sub-sequence and interleaves these two sub-sequences to compose a CH sequence. We prove that ISAC provides guaranteed rendezvous (i.e., rendezvous can be achieved within finite time). We derive the upper bound on the maximum time-to-rendezvous (MTTR) to be O(m) (m is not greater than Q) under the symmetric model and O(mn) (n is not greater than Q) under the asymmetric model, where m and n are the number of available channels of two users and Q is the total number of channels (i.e., all potentially available channels). We conduct extensive computer simulation to demonstrate that ISAC gives significantly smaller MTTR than the existing algorithms.
Image Retrieval System Base on EMD Similarity Measure and S-Tree
Venue: arXiv cs.CV 2015
Year: 2015

The paper approaches the binary signature for each image based on the percentage of the pixels in each color images, at the same time the paper builds a similar measure between images based on EMD (Earth Mover's Distance). Besides, the paper proceeded to create the S-tree based on the similar measure EMD to store the image's binary signatures to quickly query image signature data. From there, the paper build an image retrieval algorithm and CBIR (Content-Based Image Retrieval) based on a similar measure EMD and S-tree. Based on this theory, the paper proceeded to build application and experimental assessment of the process of querying image on the database system which have over 10,000 images.
Modeling of through-reactors with allowance of Large-Scale Effect on Heat and Mass Efficiency of Chemical Apparatuses
Venue: arXiv cs.CE 2015
Year: 2015

This paper deals also with a problem of gas absorption accompanied by an instantaneous, irreversible reaction in the liquid layer. The well-known methods for calculating such processes are based usually on the certain amendments to solutions, which are obtained disregarding the chemical reaction. Unlike the known work (1. D. Baetens, R. Van Keer, L.H. Hosten. Gas-liquid reaction: absorption accompanied by an instantaneous, irreversible reaction// Moving Boundaries IV, Southampton, Boston, 1997) the approach we used takes into account the influence of reaction resulting product on the arising and velocity of a moving reaction plane. The known results in the theory of chemical apparatuses scaling are devoted to apparatuses with non-regular packings mainly. However how the phases distribution over the regular packings of chemical columns effects the heat and mass efficiency is studied lesser. This paper deals with the methods of simulation the scaling effects applying to chemical towers with regular packings of various types. The models for describing the influence of initial liquid and gas distribution in chemical columns with regular packing on the mass transfer efficiency have been submitted. The sufficiently simple methods for evaluating the influence of large-scale factor on the efficiency of mass transfer have been obtained. These methods are suitable for use in engineering calculation techniques.
ShapeFit: Exact location recovery from corrupted pairwise directions
Venue: arXiv cs.CV 2015
Year: 2015

Let $t_1,\ldots,t_n \in \mathbb{R}^d$ and consider the location recovery problem: given a subset of pairwise direction observations $\{(t_i - t_j) / \|t_i - t_j\|_2\}_{i<j \in [n] \times [n]}$, where a constant fraction of these observations are arbitrarily corrupted, find $\{t_i\}_{i=1}^n$ up to a global translation and scale. We propose a novel algorithm for the location recovery problem, which consists of a simple convex program over $dn$ real variables. We prove that this program recovers a set of $n$ i.i.d. Gaussian locations exactly and with high probability if the observations are given by an \erdosrenyi graph, $d$ is large enough, and provided that at most a constant fraction of observations involving any particular location are adversarially corrupted. We also prove that the program exactly recovers Gaussian locations for $d=3$ if the fraction of corrupted observations at each location is, up to poly-logarithmic factors, at most a constant. Both of these recovery theorems are based on a set of deterministic conditions that we prove are sufficient for exact recovery.
Taylor Polynomial Estimator for Estimating Frequency Moments
Venue: arXiv cs.DS 2015
Year: 2015

We present a randomized algorithm for estimating the $p$th moment $F_p$ of the frequency vector of a data stream in the general update (turnstile) model to within a multiplicative factor of $1 \pm ε$, for $p > 2$, with high constant confidence. For $0 < ε\le 1$, the algorithm uses space $O( n^{1-2/p} ε^{-2} + n^{1-2/p} ε^{-4/p} \log (n))$ words. This improves over the current bound of $O(n^{1-2/p} ε^{-2-4/p} \log (n))$ words by Andoni et. al. in \cite{ako:arxiv10}. Our space upper bound matches the lower bound of Li and Woodruff \cite{liwood:random13} for $ε= (\log (n))^{-Ω(1)}$ and the lower bound of Andoni et. al. \cite{anpw:icalp13} for $ε= Ω(1)$.
The implementation and optimization of Bitonic sort algorithm based on CUDA
Venue: arXiv cs.DC 2015
Year: 2015

This paper describes in detail the bitonic sort algorithm,and implements the bitonic sort algorithm based on cuda architecture.At the same time,we conduct two effective optimization of implementation details according to the characteristics of the GPU,which greatly improve the efficiency. Finally,we survey the optimized Bitonic sort algorithm on the GPU with the speedup of quick sort algorithm on the CPU.Since Quick Sort is not suitable to be implemented in parallel,but it is more efficient than other sorting algorithms on CPU to some extend.Hence,to see the speedup and performance,we compare bitonic sort on GPU with quick Sort on CPU. For a series of 32-bit random integer,the experimental results show that the acceleration of our work is nearly 20 times.When array size is about 216,the speedup ratio is even up to 30.
Link-Prediction Enhanced Consensus Clustering for Complex Networks
Venue: arXiv cs.SI 2015
Year: 2015

Many real networks that are inferred or collected from data are incomplete due to missing edges. Missing edges can be inherent to the dataset (Facebook friend links will never be complete) or the result of sampling (one may only have access to a portion of the data). The consequence is that downstream analyses that consume the network will often yield less accurate results than if the edges were complete. Community detection algorithms, in particular, often suffer when critical intra-community edges are missing. We propose a novel consensus clustering algorithm to enhance community detection on incomplete networks. Our framework utilizes existing community detection algorithms that process networks imputed by our link prediction based algorithm. The framework then merges their multiple outputs into a final consensus output. On average our method boosts performance of existing algorithms by 7% on artificial data and 17% on ego networks collected from Facebook.
Programs as Polypeptides
Venue: arXiv cs.NE 2015
Year: 2015

We describe a visual programming language for defining behaviors manifested by reified actors in a 2D virtual world that can be compiled into programs comprised of sequences of combinators that are themselves reified as actors. This makes it possible to build programs that build programs from components of a few fixed types delivered by diffusion using processes that resemble chemistry as much as computation.