OpenRaiser/Intern-Atlas huggingface dataset:
Enablers and Inhibitors in Causal Justifications of Logic Programs
Venue: arXiv cs.LO 2016
Year: 2016

To appear in Theory and Practice of Logic Programming (TPLP). In this paper we propose an extension of logic programming (LP) where each default literal derived from the well-founded model is associated to a justification represented as an algebraic expression. This expression contains both causal explanations (in the form of proof graphs built with rule labels) and terms under the scope of negation that stand for conditions that enable or disable the application of causal rules. Using some examples, we discuss how these new conditions, we respectively call "enablers" and "inhibitors", are intimately related to default negation and have an essentially different nature from regular cause-effect relations. The most important result is a formal comparison to the recent algebraic approaches for justifications in LP: "Why-not Provenance" (WnP) and "Causal Graphs" (CG). We show that the current approach extends both WnP and CG justifications under the Well-Founded Semantics and, as a byproduct, we also establish a formal relation between these two approaches.
Robust AN-Aided Beamforming and Power Splitting Design for Secure MISO Cognitive Radio With SWIPT
Venue: arXiv cs.IT 2016
Year: 2016

A multiple-input single-output cognitive radio downlink network is studied with simultaneous wireless information and power transfer. In this network, a secondary user coexists with multiple primary users and multiple energy harvesting receivers. In order to guarantee secure communication and energy harvesting, the problem of robust secure artificial noise-aided beamforming and power splitting design is investigated under imperfect channel state information (CSI). Specifically, the transmit power minimization problem and the max-min fairness energy harvesting problem are formulated for both the bounded CSI error model and the probabilistic CSI error model. These problems are non-convex and challenging to solve. A one-dimensional search algorithm is proposed to solve these problems based on ${\cal S}\text{-Procedure} $ under the bounded CSI error model and based on Bernstein-type inequalities under the probabilistic CSI error model. It is shown that the optimal robust secure beamforming can be achieved under the bounded CSI error model, whereas a suboptimal beamforming solution can be obtained under the probabilistic CSI error model. A tradeoff is elucidated between the secrecy rate of the secondary user receiver and the energy harvested by the energy harvesting receivers under a max-min fairness criterion.
Latent Skill Embedding for Personalized Lesson Sequence Recommendation
Venue: arXiv cs.LG 2016
Year: 2016

Students in online courses generate large amounts of data that can be used to personalize the learning process and improve quality of education. In this paper, we present the Latent Skill Embedding (LSE), a probabilistic model of students and educational content that can be used to recommend personalized sequences of lessons with the goal of helping students prepare for specific assessments. Akin to collaborative filtering for recommender systems, the algorithm does not require students or content to be described by features, but it learns a representation using access traces. We formulate this problem as a regularized maximum-likelihood embedding of students, lessons, and assessments from historical student-content interactions. An empirical evaluation on large-scale data from Knewton, an adaptive learning technology company, shows that this approach predicts assessment results competitively with benchmark models and is able to discriminate between lesson sequences that lead to mastery and failure.
Mobile Big Data Analytics Using Deep Learning and Apache Spark
Venue: arXiv cs.DC 2016
Year: 2016

The proliferation of mobile devices, such as smartphones and Internet of Things (IoT) gadgets, results in the recent mobile big data (MBD) era. Collecting MBD is unprofitable unless suitable analytics and learning methods are utilized for extracting meaningful information and hidden patterns from data. This article presents an overview and brief tutorial of deep learning in MBD analytics and discusses a scalable learning framework over Apache Spark. Specifically, a distributed deep learning is executed as an iterative MapReduce computing on many Spark workers. Each Spark worker learns a partial deep model on a partition of the overall MBD, and a master deep model is then built by averaging the parameters of all partial models. This Spark-based framework speeds up the learning of deep models consisting of many hidden layers and millions of parameters. We use a context-aware activity recognition application with a real-world dataset containing millions of samples to validate our framework and assess its speedup effectiveness.
Clustering Optimisation Techniques in Mobile Networks
Venue: arXiv cs.NI 2016
Year: 2016

The use of mobile phones has exploded over the past years,abundantly through the introduction of smartphones and the rapidly expanding use of mobile data. This has resulted in a spiraling problem of ensuring quality of service for users of mobile networks. Hence, mobile carriers and service providers need to determine how to prioritise expansion decisions and optimise network faults to ensure customer satisfaction and optimal network performance. To assist in that decision-making process, this research employs data mining classification of different Key Performance Indicator datasets to develop a monitoring scheme for mobile networks as a means of identifying the causes of network malfunctions. Then, the data are clustered to observe the characteristics of the technical areas with the use of k-means clustering. The data output is further trained with decision tree classification algorithms. The end result was that this method of network optimisation allowed for significantly improved fault detection performance
Finding Needle in a Million Metrics: Anomaly Detection in a Large-scale Computational Advertising Platform
Venue: arXiv cs.AI 2016
Year: 2016

Online media offers opportunities to marketers to deliver brand messages to a large audience. Advertising technology platforms enables the advertisers to find the proper group of audiences and deliver ad impressions to them in real time. The recent growth of the real time bidding has posed a significant challenge on monitoring such a complicated system. With so many components we need a reliable system that detects the possible changes in the system and alerts the engineering team. In this paper we describe the mechanism that we invented for recovering the representative metrics and detecting the change in their behavior. We show that this mechanism is able to detect the possible problems in time by describing some incident cases.
Measuring Object-Oriented Design Principles
Venue: arXiv cs.SE 2016
Year: 2016

The idea of automatizing the assessment of objectoriented design is not new. Different approaches define and apply their own quality models, which are composed of single metrics or combinations thereof, to operationalize software design. However, single metrics are too fine-grained to identify core design flaws and they cannot provide hints for making design improvements. In order to deal with these weaknesses of metric-based models, rules-based approaches have proven successful in the realm of source-code quality. Moreover, for developing a well-designed software system, design principles play a key role, as they define fundamental guidelines and help to avoid pitfalls. Therefore, this thesis will enhance and complete a rule-based quality reference model for operationalizing design principles and will provide a measuring tool that implements these rules. The validation of the design quality model and the measurement tool will be based on various industrial projects. Additionally, quantitative and qualitative surveys will be conducted in order to get validated results on the value of object-oriented design principles for software development
On the Power of Advice and Randomization for Online Bipartite Matching
Venue: arXiv cs.DS 2016
Year: 2016

While randomized online algorithms have access to a sequence of uniform random bits, deterministic online algorithms with advice have access to a sequence of advice bits, i.e., bits that are set by an all powerful oracle prior to the processing of the request sequence. Advice bits are at least as helpful as random bits, but how helpful are they? In this work, we investigate the power of advice bits and random bits for online maximum bipartite matching (MBM). The well-known Karp-Vazirani-Vazirani algorithm is an optimal randomized $(1-\frac{1}{e})$-competitive algorithm for \textsc{MBM} that requires access to $Θ(n \log n)$ uniform random bits. We show that $Ω(\log(\frac{1}ε) n)$ advice bits are necessary and $O(\frac{1}{ε^5} n)$ sufficient in order to obtain a $(1-ε)$-competitive deterministic advice algorithm. Furthermore, for a large natural class of deterministic advice algorithms, we prove that $Ω(\log \log \log n)$ advice bits are required in order to improve on the $\frac{1}{2}$-competitiveness of the best deterministic online algorithm, while it is known that $O(\log n)$ bits are sufficient. Last, we give a randomized online algorithm that uses $c n$ random bits, for integers $c \ge 1$, and a competitive ratio that approaches $1-\frac{1}{e}$ very quickly as $c$ is increasing. For example if $c = 10$, then the difference between $1-\frac{1}{e}$ and the achieved competitive ratio is less than $0.0002$.
Faster Algorithms for the Maximum Common Subtree Isomorphism Problem
Venue: arXiv cs.DS 2016
Year: 2016

The maximum common subtree isomorphism problem asks for the largest possible isomorphism between subtrees of two given input trees. This problem is a natural restriction of the maximum common subgraph problem, which is ${\sf NP}$-hard in general graphs. Confining to trees renders polynomial time algorithms possible and is of fundamental importance for approaches on more general graph classes. Various variants of this problem in trees have been intensively studied. We consider the general case, where trees are neither rooted nor ordered and the isomorphism is maximum w.r.t. a weight function on the mapped vertices and edges. For trees of order $n$ and maximum degree $Δ$ our algorithm achieves a running time of $\mathcal{O}(n^2Δ)$ by exploiting the structure of the matching instances arising as subproblems. Thus our algorithm outperforms the best previously known approaches. No faster algorithm is possible for trees of bounded degree and for trees of unbounded degree we show that a further reduction of the running time would directly improve the best known approach to the assignment problem. Combining a polynomial-delay algorithm for the enumeration of all maximum common subtree isomorphisms with central ideas of our new algorithm leads to an improvement of its running time from $\mathcal{O}(n^6+Tn^2)$ to $\mathcal{O}(n^3+TnΔ)$, where $n$ is the order of the larger tree, $T$ is the number of different solutions, and $Δ$ is the minimum of the maximum degrees of the input trees. Our theoretical results are supplemented by an experimental evaluation on synthetic and real-world instances.
The IBM 2016 Speaker Recognition System
Venue: arXiv cs.SD 2016
Year: 2016

In this paper we describe the recent advancements made in the IBM i-vector speaker recognition system for conversational speech. In particular, we identify key techniques that contribute to significant improvements in performance of our system, and quantify their contributions. The techniques include: 1) a nearest-neighbor discriminant analysis (NDA) approach that is formulated to alleviate some of the limitations associated with the conventional linear discriminant analysis (LDA) that assumes Gaussian class-conditional distributions, 2) the application of speaker- and channel-adapted features, which are derived from an automatic speech recognition (ASR) system, for speaker recognition, and 3) the use of a deep neural network (DNN) acoustic model with a large number of output units (~10k senones) to compute the frame-level soft alignments required in the i-vector estimation process. We evaluate these techniques on the NIST 2010 speaker recognition evaluation (SRE) extended core conditions involving telephone and microphone trials. Experimental results indicate that: 1) the NDA is more effective (up to 35% relative improvement in terms of EER) than the traditional parametric LDA for speaker recognition, 2) when compared to raw acoustic features (e.g., MFCCs), the ASR speaker-adapted features provide gains in speaker recognition performance, and 3) increasing the number of output units in the DNN acoustic model (i.e., increasing the senone set size from 2k to 10k) provides consistent improvements in performance (for example from 37% to 57% relative EER gains over our baseline GMM i-vector system). To our knowledge, results reported in this paper represent the best performances published to date on the NIST SRE 2010 extended core tasks.
Parsimonious modeling with Information Filtering Networks
Venue: arXiv cs.IT 2016
Year: 2016

We introduce a methodology to construct parsimonious probabilistic models. This method makes use of Information Filtering Networks to produce a robust estimate of the global sparse inverse covariance from a simple sum of local inverse covariances computed on small sub-parts of the network. Being based on local and low-dimensional inversions, this method is computationally very efficient and statistically robust even for the estimation of inverse covariance of high-dimensional, noisy and short time-series. Applied to financial data our method results computationally more efficient than state-of-the-art methodologies such as Glasso producing, in a fraction of the computation time, models that can have equivalent or better performances but with a sparser inference structure. We also discuss performances with sparse factor models where we notice that relative performances decrease with the number of factors. The local nature of this approach allows us to perform computations in parallel and provides a tool for dynamical adaptation by partial updating when the properties of some variables change without the need of recomputing the whole model. This makes this approach particularly suitable to handle big datasets with large numbers of variables. Examples of practical application for forecasting, stress testing and risk allocation in financial systems are also provided.
The Possibilities and Limitations of Private Prediction Markets
Venue: arXiv cs.GT 2016
Year: 2016

We consider the design of private prediction markets, financial markets designed to elicit predictions about uncertain events without revealing too much information about market participants' actions or beliefs. Our goal is to design market mechanisms in which participants' trades or wagers influence the market's behavior in a way that leads to accurate predictions, yet no single participant has too much influence over what others are able to observe. We study the possibilities and limitations of such mechanisms using tools from differential privacy. We begin by designing a private one-shot wagering mechanism in which bettors specify a belief about the likelihood of a future event and a corresponding monetary wager. Wagers are redistributed among bettors in a way that more highly rewards those with accurate predictions. We provide a class of wagering mechanisms that are guaranteed to satisfy truthfulness, budget balance in expectation, and other desirable properties while additionally guaranteeing epsilon-joint differential privacy in the bettors' reported beliefs, and analyze the trade-off between the achievable level of privacy and the sensitivity of a bettor's payment to her own report. We then ask whether it is possible to obtain privacy in dynamic prediction markets, focusing our attention on the popular cost-function framework in which securities with payments linked to future events are bought and sold by an automated market maker. We show that under general conditions, it is impossible for such a market maker to simultaneously achieve bounded worst-case loss and epsilon-differential privacy without allowing the privacy guarantee to degrade extremely quickly as the number of trades grows, making such markets impractical in settings in which privacy is valued. We conclude by suggesting several avenues for potentially circumventing this lower bound.
Max-Margin Nonparametric Latent Feature Models for Link Prediction
Venue: arXiv cs.LG 2016
Year: 2016

Link prediction is a fundamental task in statistical network analysis. Recent advances have been made on learning flexible nonparametric Bayesian latent feature models for link prediction. In this paper, we present a max-margin learning method for such nonparametric latent feature relational models. Our approach attempts to unite the ideas of max-margin learning and Bayesian nonparametrics to discover discriminative latent features for link prediction. It inherits the advances of nonparametric Bayesian methods to infer the unknown latent social dimension, while for discriminative link prediction, it adopts the max-margin learning principle by minimizing a hinge-loss using the linear expectation operator, without dealing with a highly nonlinear link likelihood function. For posterior inference, we develop an efficient stochastic variational inference algorithm under a truncated mean-field assumption. Our methods can scale up to large-scale real networks with millions of entities and tens of millions of positive links. We also provide a full Bayesian formulation, which can avoid tuning regularization hyper-parameters. Experimental results on a diverse range of real datasets demonstrate the benefits inherited from max-margin learning and Bayesian nonparametric inference.
Asymptotic consistency and order specification for logistic classifier chains in multi-label learning
Venue: arXiv cs.LG 2016
Year: 2016

Classifier chains are popular and effective method to tackle a multi-label classification problem. The aim of this paper is to study the asymptotic properties of the chain model in which the conditional probabilities are of the logistic form. In particular we find conditions on the number of labels and the distribution of feature vector under which the estimated mode of the joint distribution of labels converges to the true mode. Best of our knowledge, this important issue has not yet been studied in the context of multi-label learning. We also investigate how the order of model building in a chain influences the estimation of the joint distribution of labels. We establish the link between the problem of incorrect ordering in the chain and incorrect model specification. We propose a procedure of determining the optimal ordering of labels in the chain, which is based on using measures of correct specification and allows to find the ordering such that the consecutive logistic models are best possibly specified. The other important question raised in this paper is how accurately can we estimate the joint posterior probability when the ordering of labels is wrong or the logistic models in the chain are incorrectly specified. The numerical experiments illustrate the theoretical results.
Active Learning from Positive and Unlabeled Data
Venue: arXiv cs.LG 2016
Year: 2016

During recent years, active learning has evolved into a popular paradigm for utilizing user's feedback to improve accuracy of learning algorithms. Active learning works by selecting the most informative sample among unlabeled data and querying the label of that point from user. Many different methods such as uncertainty sampling and minimum risk sampling have been utilized to select the most informative sample in active learning. Although many active learning algorithms have been proposed so far, most of them work with binary or multi-class classification problems and therefore can not be applied to problems in which only samples from one class as well as a set of unlabeled data are available. Such problems arise in many real-world situations and are known as the problem of learning from positive and unlabeled data. In this paper we propose an active learning algorithm that can work when only samples of one class as well as a set of unlabelled data are available. Our method works by separately estimating probability desnity of positive and unlabeled points and then computing expected value of informativeness to get rid of a hyper-parameter and have a better measure of informativeness./ Experiments and empirical analysis show promising results compared to other similar methods.
Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
Venue: arXiv cs.DS 2016
Year: 2016

Connected Vertex Cover is one of the classical problems of computer science, already mentioned in the monograph of Garey and Johnson. Although the optimization and decision variants of finding connected vertex covers of minimum size or weight are well studied, surprisingly there is no work on the enumeration or maximum number of minimal connected vertex covers of a graph. In this paper we show that the maximum number of minimal connected vertex covers of a graph is at most 1.8668^n, and these can be enumerated in time O(1.8668^n). For graphs of chordality at most 5, we are able to give a better upper bound, and for chordal graphs and distance-hereditary graphs we are able to give tight bounds on the maximum number of minimal connected vertex covers.
On the Accuracy of Point Localisation in a Circular Camera-Array
Venue: arXiv cs.CV 2016
Year: 2016

Although many advances have been made in light-field and camera-array image processing, there is still a lack of thorough analysis of the localisation accuracy of different multi-camera systems. By considering the problem from a frame-quantisation perspective, we are able to quantify the point localisation error of circular camera configurations. Specifically, we obtain closed form expressions bounding the localisation error in terms of the parameters describing the acquisition setup. These theoretical results are independent of the localisation algorithm and thus provide fundamental limits on performance. Furthermore, the new frame-quantisation perspective is general enough to be extended to more complex camera configurations.
Stochastic Shortest Path with Energy Constraints in POMDPs
Venue: arXiv cs.AI 2016
Year: 2016

We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels.