OpenRaiser/Intern-Atlas huggingface dataset:
Gaussian Processes for Big Data
Venue: arXiv cs.LG 2013
Year: 2013

We introduce stochastic variational inference for Gaussian process models. This enables the application of Gaussian process (GP) models to data sets containing millions of data points. We show how GPs can be vari- ationally decomposed to depend on a set of globally relevant inducing variables which factorize the model in the necessary manner to perform variational inference. Our ap- proach is readily extended to models with non-Gaussian likelihoods and latent variable models based around Gaussian processes. We demonstrate the approach on a simple toy problem and two real world data sets.
Learning Periodic Human Behaviour Models from Sparse Data for Crowdsourcing Aid Delivery in Developing Countries
Venue: arXiv cs.AI 2013
Year: 2013

In many developing countries, half the population lives in rural locations, where access to essentials such as school materials, mosquito nets, and medical supplies is restricted. We propose an alternative method of distribution (to standard road delivery) in which the existing mobility habits of a local population are leveraged to deliver aid, which raises two technical challenges in the areas optimisation and learning. For optimisation, a standard Markov decision process applied to this problem is intractable, so we provide an exact formulation that takes advantage of the periodicities in human location behaviour. To learn such behaviour models from sparse data (i.e., cell tower observations), we develop a Bayesian model of human mobility. Using real cell tower data of the mobility behaviour of 50,000 individuals in Ivory Coast, we find that our model outperforms the state of the art approaches in mobility prediction by at least 25% (in held-out data likelihood). Furthermore, when incorporating mobility prediction with our MDP approach, we find a 81.3% reduction in total delivery time versus routine planning that minimises just the number of participants in the solution path.
Learning Max-Margin Tree Predictors
Venue: arXiv cs.LG 2013
Year: 2013

Structured prediction is a powerful framework for coping with joint prediction of interacting outputs. A central difficulty in using this framework is that often the correct label dependence structure is unknown. At the same time, we would like to avoid an overly complex structure that will lead to intractable prediction. In this work we address the challenge of learning tree structured predictive models that achieve high accuracy while at the same time facilitate efficient (linear time) inference. We start by proving that this task is in general NP-hard, and then suggest an approximate alternative. Briefly, our CRANK approach relies on a novel Circuit-RANK regularizer that penalizes non-tree structures and that can be optimized using a CCCP procedure. We demonstrate the effectiveness of our approach on several domains and show that, despite the relative simplicity of the structure, prediction accuracy is competitive with a fully connected model that is computationally costly at prediction time.
Tighter Linear Program Relaxations for High Order Graphical Models
Venue: arXiv cs.AI 2013
Year: 2013

Graphical models with High Order Potentials (HOPs) have received considerable interest in recent years. While there are a variety of approaches to inference in these models, nearly all of them amount to solving a linear program (LP) relaxation with unary consistency constraints between the HOP and the individual variables. In many cases, the resulting relaxations are loose, and in these cases the results of inference can be poor. It is thus desirable to look for more accurate ways of performing inference in these models. In this work, we study the LP relaxations that result from enforcing additional consistency constraints between the HOP and the rest of the model. We address theoretical questions about the strength of the resulting relaxations compared to the relaxations that arise in standard approaches, and we develop practical and efficient message passing algorithms for optimizing the LPs. Empirically, we show that the LPs with additional consistency constraints lead to more accurate inference on some challenging problems that include a combination of low order and high order terms.
Structured Convex Optimization under Submodular Constraints
Venue: arXiv cs.LG 2013
Year: 2013

A number of discrete and continuous optimization problems in machine learning are related to convex minimization problems under submodular constraints. In this paper, we deal with a submodular function with a directed graph structure, and we show that a wide range of convex optimization problems under submodular constraints can be solved much more efficiently than general submodular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse optimization methods, in which the proposed methods are effective. Additionally, we evaluate the performance of the proposed method through computational experiments.
Solution Methods for Constrained Markov Decision Process with Continuous Probability Modulation
Venue: arXiv cs.AI 2013
Year: 2013

We propose solution methods for previously-unsolved constrained MDPs in which actions can continuously modify the transition probabilities within some acceptable sets. While many methods have been proposed to solve regular MDPs with large state sets, there are few practical approaches for solving constrained MDPs with large action sets. In particular, we show that the continuous action sets can be replaced by their extreme points when the rewards are linear in the modulation. We also develop a tractable optimization formulation for concave reward functions and, surprisingly, also extend it to non- concave reward functions by using their concave envelopes. We evaluate the effectiveness of the approach on the problem of managing delinquencies in a portfolio of loans.
Speedy Model Selection (SMS) for Copula Models
Venue: arXiv cs.LG 2013
Year: 2013

We tackle the challenge of efficiently learning the structure of expressive multivariate real-valued densities of copula graphical models. We start by theoretically substantiating the conjecture that for many copula families the magnitude of Spearman's rank correlation coefficient is monotone in the expected contribution of an edge in network, namely the negative copula entropy. We then build on this theory and suggest a novel Bayesian approach that makes use of a prior over values of Spearman's rho for learning copula-based models that involve a mix of copula families. We demonstrate the generalization effectiveness of our highly efficient approach on sizable and varied real-life datasets.
Partial Model Checking using Networks of Labelled Transition Systems and Boole an Equation Systems
Venue: arXiv cs.LO 2013
Year: 2013

Partial model checking was proposed by Andersen in 1995 to verify a temporal logic formula compositionally on a composition of processes. It consists in incrementally incorporating into the formula the behavioural information taken from one process - an operation called quotienting - to obtain a new formula that can be verified on a smaller composition from which the incorporated process has been removed. Simplifications of the formula must be applied at each step, so as to maintain the formula at a tractable size. In this paper, we revisit partial model checking. First, we extend quotienting to the network of labelled transition systems model, which subsumes most parallel composition operators, including m-among-n synchronisation and parallel composition using synchronisation interfaces, available in the ELOTOS standard. Second, we reformulate quotienting in terms of a simple synchronous product between a graph representation of the formula (called formula graph) and a process, thus enabling quotienting to be implemented efficiently and easily, by reusing existing tools dedicated to graph compositions. Third, we propose simplifications of the formula as a combination of bisimulations and reductions using Boolean equation systems applied directly to the formula graph, thus enabling formula simplifications also to be implemented efficiently. Finally, we describe an implementation in the CADP (Construction and Analysis of Distributed Processes) toolbox and present some experimental results in which partial model checking uses hundreds of times less memory than on-the-fly model checking.
Design Elements that Promote the use of Fake Website Detection Tools
Venue: arXiv cs.CY 2013
Year: 2013

Fake websites have emerged as a major source of online fraud, accounting for billions of dollars of loss by Internet users. We explore the process by which salient design elements could increase the use of protective tools, thus reducing the success rate of fake websites. Using the protection motivation theory, we conceptualize a model to investigate how salient design elements of detection tools could influence user perceptions of the tools, efficacy in dealing with threats, and use of such tools. The research method was a controlled lab experiment with a novel and extensive experimental design and protocol. We found that trust in the detector is the pivotal coping mechanism in dealing with security threats and is a major conduit for transforming salient design elements into increased use. We also found that design elements have profound and unexpected impacts on self-efficacy. The significant theoretical and empirical implications of findings are discussed.
Face Verification Using Boosted Cross-Image Features
Venue: arXiv cs.CV 2013
Year: 2013

This paper proposes a new approach for face verification, where a pair of images needs to be classified as belonging to the same person or not. This problem is relatively new and not well-explored in the literature. Current methods mostly adopt techniques borrowed from face recognition, and process each of the images in the pair independently, which is counter intuitive. In contrast, we propose to extract cross-image features, i.e. features across the pair of images, which, as we demonstrate, is more discriminative to the similarity and the dissimilarity of faces. Our features are derived from the popular Haar-like features, however, extended to handle the face verification problem instead of face detection. We collect a large bank of cross-image features using filters of different sizes, locations, and orientations. Consequently, we use AdaBoost to select and weight the most discriminative features. We carried out extensive experiments on the proposed ideas using three standard face verification datasets, and obtained promising results outperforming state-of-the-art.
Optimal Hybrid Channel Allocation:Based On Machine Learning Algorithms
Venue: arXiv cs.NI 2013
Year: 2013

Recent advances in cellular communication systems resulted in a huge increase in spectrum demand. To meet the requirements of the ever-growing need for spectrum, efficient utilization of the existing resources is of utmost importance. Channel Allocation, has thus become an inevitable research topic in wireless communications. In this paper, we propose an optimal channel allocation scheme, Optimal Hybrid Channel Allocation (OHCA) for an effective allocation of channels. We improvise upon the existing Fixed Channel Allocation (FCA) technique by imparting intelligence to the existing system by employing the multilayer perceptron technique.
CSIFT Based Locality-constrained Linear Coding for Image Classification
Venue: arXiv cs.CV 2013
Year: 2013

In the past decade, SIFT descriptor has been witnessed as one of the most robust local invariant feature descriptors and widely used in various vision tasks. Most traditional image classification systems depend on the luminance-based SIFT descriptors, which only analyze the gray level variations of the images. Misclassification may happen since their color contents are ignored. In this article, we concentrate on improving the performance of existing image classification algorithms by adding color information. To achieve this purpose, different kinds of colored SIFT descriptors are introduced and implemented. Locality-constrained Linear Coding (LLC), a state-of-the-art sparse coding technology, is employed to construct the image classification system for the evaluation. The real experiments are carried out on several benchmarks. With the enhancements of color SIFT, the proposed image classification system obtains approximate 3% improvement of classification accuracy on the Caltech-101 dataset and approximate 4% improvement of classification accuracy on the Caltech-256 dataset.
Context-aware recommendations from implicit data via scalable tensor factorization
Venue: arXiv cs.LG 2013
Year: 2013

Albeit the implicit feedback based recommendation problem - when only the user history is available but there are no ratings - is the most typical setting in real-world applications, it is much less researched than the explicit feedback case. State-of-the-art algorithms that are efficient on the explicit case cannot be automatically transformed to the implicit case if scalability should be maintained. There are few implicit feedback benchmark data sets, therefore new ideas are usually experimented on explicit benchmarks. In this paper, we propose a generic context-aware implicit feedback recommender algorithm, coined iTALS. iTALS applies a fast, ALS-based tensor factorization learning method that scales linearly with the number of non-zero elements in the tensor. We also present two approximate and faster variants of iTALS using coordinate descent and conjugate gradient methods at learning. The method also allows us to incorporate various contextual information into the model while maintaining its computational efficiency. We present two context-aware variants of iTALS incorporating seasonality and item purchase sequentiality into the model to distinguish user behavior at different time intervals, and product types with different repetitiveness. Experiments run on six data sets shows that iTALS clearly outperforms context-unaware models and context aware baselines, while it is on par with factorization machines (beats 7 times out of 12 cases) both in terms of recall and MAP.
Correcting Multi-focus Images via Simple Standard Deviation for Image Fusion
Venue: arXiv cs.CV 2013
Year: 2013

Image fusion is one of the recent trends in image registration which is an essential field of image processing. The basic principle of this paper is to fuse multi-focus images using simple statistical standard deviation. Firstly, the simple standard deviation for the k-by-k window inside each of the multi-focus images was computed. The contribution in this paper came from the idea that the focused part inside an image had high details rather than the unfocused part. Hence, the dispersion between pixels inside the focused part is higher than the dispersion inside the unfocused part. Secondly, a simple comparison between the standard deviation for each k-by-k window in the multi-focus images could be computed. The highest standard deviation between all the computed standard deviations for the multi-focus images could be treated as the optimal that is to be placed in the fused image. The experimental visual results show that the proposed method produces very satisfactory results in spite of its simplicity.
Group-theoretic structure of linear phase multirate filter banks
Venue: arXiv cs.IT 2013
Year: 2013

Unique lifting factorization results for group lifting structures are used to characterize the group-theoretic structure of two-channel linear phase FIR perfect reconstruction filter bank groups. For D-invariant, order-increasing group lifting structures, it is shown that the associated lifting cascade group C is isomorphic to the free product of the upper and lower triangular lifting matrix groups. Under the same hypotheses, the associated scaled lifting group S is the semidirect product of C by the diagonal gain scaling matrix group D. These results apply to the group lifting structures for the two principal classes of linear phase perfect reconstruction filter banks, the whole- and half-sample symmetric classes. Since the unimodular whole-sample symmetric class forms a group, W, that is in fact equal to its own scaled lifting group, W=S_W, the results of this paper characterize the group-theoretic structure of W up to isomorphism. Although the half-sample symmetric class H does not form a group, it can be partitioned into cosets of its lifting cascade group, C_H, or, alternatively, into cosets of its scaled lifting group, S_H. Homomorphic comparisons reveal that scaled lifting groups covered by the results in this paper have a structure analogous to a "noncommutative vector space."
Retargeting GCC: Do We Reinvent the Wheel Every Time?
Venue: arXiv cs.PL 2013
Year: 2013

Porting GCC to new architecture requires writing a Machine Description (MD) file that contains mapping from GCC's intermediate form to the target assembly code. Constructing an MD file is a difficult task because it requires the user to understand both (a) the internals of GCC, and (b) the intricacies of the target architecture. Instruction sets of different architectures exhibit significant amount of semantic similarities across a large class (for example, the instruction sets for RISC architectures) and differ only in syntax. Therefore, it is expected that MD files of machines with similar architectures should also have similarities. To confirm our hypothesis, we created "mdcompare", a tool to (a) extract RTL patterns (machine independent abstraction of RTL templates) from MD files of well known architectures and (b) compare the similarity of patterns across architectures. The results are encouraging; we found that 28% -- 70% RTL expressions are similar across pairs of MD files, the similarity percentage being on the higher side for pairs of similar architectures.
Evolution and development of complex computational systems using the paradigm of metabolic computing in Epigenetic Tracking
Venue: arXiv cs.CE 2013
Year: 2013

Epigenetic Tracking (ET) is an Artificial Embryology system which allows for the evolution and development of large complex structures built from artificial cells. In terms of the number of cells, the complexity of the bodies generated with ET is comparable with the complexity of biological organisms. We have previously used ET to simulate the growth of multicellular bodies with arbitrary 3-dimensional shapes which perform computation using the paradigm of "metabolic computing". In this paper we investigate the memory capacity of such computational structures and analyse the trade-off between shape and computation. We now plan to build on these foundations to create a biologically-inspired model in which the encoding of the phenotype is efficient (in terms of the compactness of the genome) and evolvable in tasks involving non-trivial computation, robust to damage and capable of self-maintenance and self-repair.
Analysis of the spatial and dynamical properties of a multiscale model of intestinal crypts
Venue: arXiv cs.CE 2013
Year: 2013

The preliminary analyses on a multiscale model of intestinal crypt dynamics are here presented. The model combines a morphological model, based on the Cellular Potts Model (CPM), and a gene regulatory network model, based on Noisy Random Boolean Networks (NRBNs). Simulations suggest that the stochastic differentiation process is itself sufficient to ensure the general homeostasis in the asymptotic states, as proven by several measures.
On the Effect of Data Contamination on Track Purity
Venue: arXiv cs.IT 2013
Year: 2013

This paper is concerned with performance analysis for data association, in a target tracking environment. Effects of misassociation are considered in a simple (linear) multiscan framework so as to provide closed-form expressions of the probability of correct association. In this paper, we focus on the development of explicit approximations of this probability. Via rigorous calculations the effect of dimensioning parameters (number of scans, false measurement positions or densities) is analyzed, for various modelings of the false measurements. Remarkably, it is possible to derive very simple expressions of the probability of correct association which are independent of the scenario kinematic parameters.
Prefactor Reduction of the Guruswami-Sudan Interpolation Step
Venue: arXiv cs.IT 2013
Year: 2013

The concept of prefactors is considered in order to decrease the complexity of the Guruswami-Sudan interpolation step for generalized Reed-Solomon codes. It is shown that the well-known re-encoding projection due to Koetter et al. leads to one type of such prefactors. The new type of Sierpinski prefactors is introduced. The latter are based on the fact that many binomial coefficients in the Hasse derivative associated with the Guruswami-Sudan interpolation step are zero modulo the base field characteristic. It is shown that both types of prefactors can be combined and how arbitrary prefactors can be used to derive a reduced Guruswami-Sudan interpolation step.
Approximation Algorithms for the Max-Buying Problem with Limited Supply
Venue: arXiv cs.GT 2013
Year: 2013

We consider the Max-Buying Problem with Limited Supply, in which there are $n$ items, with $C_i$ copies of each item $i$, and $m$ bidders such that every bidder $b$ has valuation $v_{ib}$ for item $i$. The goal is to find a pricing $p$ and an allocation of items to bidders that maximizes the profit, where every item is allocated to at most $C_i$ bidders, every bidder receives at most one item and if a bidder $b$ receives item $i$ then $p_i \leq v_{ib}$. Briest and Krysta presented a 2-approximation for this problem and Aggarwal et al. presented a 4-approximation for the Price Ladder variant where the pricing must be non-increasing (that is, $p_1 \geq p_2 \geq \cdots \geq p_n$). We present an $e/(e-1)$-approximation for the Max-Buying Problem with Limited Supply and, for every $\varepsilon > 0$, a $(2+\varepsilon)$-approximation for the Price Ladder variant.
Personal Identification from Lip-Print Features using a Statistical Model
Venue: arXiv cs.CV 2013
Year: 2013

This paper presents a novel approach towards identification of human beings from the statistical analysis of their lip prints. Lip features are extracted by studying the spatial orientations of the grooves present in lip prints of individuals using standard edge detection techniques. Horizontal, vertical and diagonal groove features are analysed using connected-component analysis to generate the region-specific edge datasets. Comparison between test and reference sample datasets against a threshold value to define a match yield satisfactory results. FAR, FRR and ROC metrics have been used to gauge the performance of the algorithm for real-world deployment in unimodal and multimodal biometric verification systems.
Online Approximate Optimal Path-Following for a Kinematic Unicycle
Venue: arXiv cs.SY 2013
Year: 2013

Online approximation of an infinite horizon optimal path-following strategy for a kinematic unicycle is considered. The solution to the optimal control problem is approximated using an approximate dynamic programming technique that uses concurrent-learning-based adaptive update laws to estimate the unknown value function. The developed controller overcomes challenges with the approximation of the infinite horizon value function using an auxiliary function that describes the motion of a virtual target on the desired path. The developed controller guarantees uniformly ultimately bounded (UUB) convergence of the vehicle to a desired path while maintaining a desired speed profile and UUB convergence of the approximate policy to the optimal policy. Simulation results are included to demonstrate the controller's performance.