pwc-archive/papers-with-abstracts huggingface dataset:
On the Feature Discovery for App Usage Prediction in Smartphones
Authors: Zhung-Xun Liao, Shou-Chung Li, Wen-Chih Peng, Philip S. Yu
Date: 2013-09-26 00:00:00
Tasks: feature selection, Management, Prediction

With the increasing number of mobile Apps developed, they are now closely
integrated into daily life. In this paper, we develop a framework to predict
mobile Apps that are most likely to be used regarding the current device status
of a smartphone. Such an Apps usage prediction framework is a crucial
prerequisite for fast App launching, intelligent user experience, and power
management of smartphones. By analyzing real App usage log data, we discover
two kinds of features: The Explicit Feature (EF) from sensing readings of
built-in sensors, and the Implicit Feature (IF) from App usage relations. The
IF feature is derived by constructing the proposed App Usage Graph (abbreviated
as AUG) that models App usage transitions. In light of AUG, we are able to
discover usage relations among Apps. Since users may have different usage
behaviors on their smartphones, we further propose one personalized feature
selection algorithm. We explore minimum description length (MDL) from the
training data and select those features which need less length to describe the
training data. The personalized feature selection can successfully reduce the
log size and the prediction time. Finally, we adopt the kNN classification
model to predict Apps usage. Note that through the features selected by the
proposed personalized feature selection algorithm, we only need to keep these
features, which in turn reduces the prediction time and avoids the curse of
dimensionality when using the kNN classifier. We conduct a comprehensive
experimental study based on a real mobile App usage dataset. The results
demonstrate the effectiveness of the proposed framework and show the predictive
capability for App usage prediction.
Bennett-type Generalization Bounds: Large-deviation Case and Faster Rate of Convergence
Authors: Chao Zhang
Date: 2013-09-26 00:00:00
Tasks: Generalization Bounds

In this paper, we present the Bennett-type generalization bounds of the
learning process for i.i.d. samples, and then show that the generalization
bounds have a faster rate of convergence than the traditional results. In
particular, we first develop two types of Bennett-type deviation inequality for
the i.i.d. learning process: one provides the generalization bounds based on
the uniform entropy number; the other leads to the bounds based on the
Rademacher complexity. We then adopt a new method to obtain the alternative
expressions of the Bennett-type generalization bounds, which imply that the
bounds have a faster rate o(N^{-1/2}) of convergence than the traditional
results O(N^{-1/2}). Additionally, we find that the rate of the bounds will
become faster in the large-deviation case, which refers to a situation where
the empirical risk is far away from (at least not close to) the expected risk.
Finally, we analyze the asymptotical convergence of the learning process and
compare our analysis with the existing results.
Active Learning with Expert Advice
Authors: Peilin Zhao, Steven Hoi, Jinfeng Zhuang
Date: 2013-09-26 00:00:00
Tasks: Active Learning

Conventional learning with expert advice methods assumes a learner is always
receiving the outcome (e.g., class labels) of every incoming training instance
at the end of each trial. In real applications, acquiring the outcome from
oracle can be costly or time consuming. In this paper, we address a new problem
of active learning with expert advice, where the outcome of an instance is
disclosed only when it is requested by the online learner. Our goal is to learn
an accurate prediction model by asking the oracle the number of questions as
small as possible. To address this challenge, we propose a framework of active
forecasters for online active learning with expert advice, which attempts to
extend two regular forecasters, i.e., Exponentially Weighted Average Forecaster
and Greedy Forecaster, to tackle the task of active learning with expert
advice. We prove that the proposed algorithms satisfy the Hannan consistency
under some proper assumptions, and validate the efficacy of our technique by an
extensive set of experiments.
Integrating Document Clustering and Topic Modeling
Authors: Pengtao Xie, Eric P. Xing
Date: 2013-09-26 00:00:00
Tasks: Clustering, Topic Models, Variational Inference

Document clustering and topic modeling are two closely related tasks which
can mutually benefit each other. Topic modeling can project documents into a
topic space which facilitates effective document clustering. Cluster labels
discovered by document clustering can be incorporated into topic models to
extract local topics specific to each cluster and global topics shared by all
clusters. In this paper, we propose a multi-grain clustering topic model
(MGCTM) which integrates document clustering and topic modeling into a unified
framework and jointly performs the two tasks to achieve the overall best
performance. Our model tightly couples two components: a mixture component used
for discovering latent groups in document collection and a topic model
component used for mining multi-grain topics including local topics specific to
each cluster and global topics shared across clusters.We employ variational
inference to approximate the posterior of hidden variables and learn model
parameters. Experiments on two datasets demonstrate the effectiveness of our
model.
On MAP Inference by MWSS on Perfect Graphs
Authors: Adrian Weller, Tony S. Jebara
Date: 2013-09-26 00:00:00

Finding the most likely (MAP) configuration of a Markov random field (MRF) is
NP-hard in general. A promising, recent technique is to reduce the problem to
finding a maximum weight stable set (MWSS) on a derived weighted graph, which
if perfect, allows inference in polynomial time. We derive new results for this
approach, including a general decomposition theorem for MRFs of any order and
number of labels, extensions of results for binary pairwise models with
submodular cost functions to higher order, and an exact characterization of
which binary pairwise MRFs can be efficiently solved with this method. This
defines the power of the approach on this class of models, improves our toolbox
and expands the range of tractable models.
Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs
Authors: Luis Gustavo Vianna, Scott Sanner, Leliane Nunes de Barros
Date: 2013-09-26 00:00:00

Recent advances in symbolic dynamic programming (SDP) combined with the
extended algebraic decision diagram (XADD) data structure have provided exact
solutions for mixed discrete and continuous (hybrid) MDPs with piecewise linear
dynamics and continuous actions. Since XADD-based exact solutions may grow
intractably large for many problems, we propose a bounded error compression
technique for XADDs that involves the solution of a constrained bilinear saddle
point problem. Fortuitously, we show that given the special structure of this
problem, it can be expressed as a bilevel linear programming problem and solved
to optimality in finite time via constraint generation, despite having an
infinite set of constraints. This solution permits the use of efficient linear
program solvers for XADD compression and enables a novel class of bounded
approximate SDP algorithms for hybrid MDPs that empirically offers
order-of-magnitude speedups over the exact solution in exchange for a small
approximation error.
Dynamic Blocking and Collapsing for Gibbs Sampling
Authors: Deepak Venugopal, Vibhav Gogate
Date: 2013-09-26 00:00:00
Tasks: Blocking

In this paper, we investigate combining blocking and collapsing -- two widely
used strategies for improving the accuracy of Gibbs sampling -- in the context
of probabilistic graphical models (PGMs). We show that combining them is not
straight-forward because collapsing (or eliminating variables) introduces new
dependencies in the PGM and in computation-limited settings, this may adversely
affect blocking. We therefore propose a principled approach for tackling this
problem. Specifically, we develop two scoring functions, one each for blocking
and collapsing, and formulate the problem of partitioning the variables in the
PGM into blocked and collapsed subsets as simultaneously maximizing both
scoring functions (i.e., a multi-objective optimization problem). We propose a
dynamic, greedy algorithm for approximately solving this intractable
optimization problem. Our dynamic algorithm periodically updates the
partitioning into blocked and collapsed variables by leveraging correlation
statistics gathered from the generated samples and enables rapid mixing by
blocking together and collapsing highly correlated variables. We demonstrate
experimentally the clear benefit of our dynamic approach: as more samples are
drawn, our dynamic approach significantly outperforms static graph-based
approaches by an order of magnitude in terms of accuracy.
Finite-Time Analysis of Kernelised Contextual Bandits
Authors: Michal Valko, Nathaniel Korda, Remi Munos, Ilias Flaounas, Nelo Cristianini
Date: 2013-09-26 00:00:00
Tasks: Multi-Armed Bandits

We tackle the problem of online reward maximisation over a large finite set
of actions described by their contexts. We focus on the case when the number of
actions is too big to sample all of them even once. However we assume that we
have access to the similarities between actions' contexts and that the expected
reward is an arbitrary linear function of the contexts' images in the related
reproducing kernel Hilbert space (RKHS). We propose KernelUCB, a kernelised UCB
algorithm, and give a cumulative regret bound through a frequentist analysis.
For contextual bandits, the related algorithm GP-UCB turns out to be a special
case of our algorithm, and our finite-time analysis improves the regret bound
of GP-UCB for the agnostic case, both in the terms of the kernel-dependent
quantity and the RKHS norm of the reward function. Moreover, for the linear
kernel, our regret bound matches the lower bound for contextual linear bandits.
Approximate Kalman Filter Q-Learning for Continuous State-Space MDPs
Authors: Charles Tripp, Ross D. Shachter
Date: 2013-09-26 00:00:00
Tasks: Q-Learning

We seek to learn an effective policy for a Markov Decision Process (MDP) with
continuous states via Q-Learning. Given a set of basis functions over state
action pairs we search for a corresponding set of linear weights that minimizes
the mean Bellman residual. Our algorithm uses a Kalman filter model to estimate
those weights and we have developed a simpler approximate Kalman filter model
that outperforms the current state of the art projected TD-Learning methods on
several standard benchmark problems.
Speedy Model Selection (SMS) for Copula Models
Authors: Yaniv Tenzer, Gal Elidan
Date: 2013-09-26 00:00:00
Tasks: model, Model Selection

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.
Modeling Documents with Deep Boltzmann Machines
Authors: Nitish Srivastava, Ruslan R. Salakhutdinov, Geoffrey E. Hinton
Date: 2013-09-26 00:00:00
Tasks: Document Classification, General Classification, Retrieval

We introduce a Deep Boltzmann Machine model suitable for modeling and
extracting latent semantic representations from a large unstructured collection
of documents. We overcome the apparent difficulty of training a DBM with
judicious parameter tying. This parameter tying enables an efficient
pretraining algorithm and a state initialization scheme that aids inference.
The model can be trained just as efficiently as a standard Restricted Boltzmann
Machine. Our experiments show that the model assigns better log probability to
unseen data than the Replicated Softmax model. Features extracted from our
model outperform LDA, Replicated Softmax, and DocNADE models on document
retrieval and document classification tasks.
Preference Elicitation For General Random Utility Models
Authors: Hossein Azari Soufiani, David C. Parkes, Lirong Xia
Date: 2013-09-26 00:00:00
Tasks: Experimental Design

This paper discusses {General Random Utility Models (GRUMs)}. These are a
class of parametric models that generate partial ranks over alternatives given
attributes of agents and alternatives. We propose two preference elicitation
scheme for GRUMs developed from principles in Bayesian experimental design, one
for social choice and the other for personalized choice. We couple this with a
general Monte-Carlo-Expectation-Maximization (MC-EM) based algorithm for MAP
inference under GRUMs. We also prove uni-modality of the likelihood functions
for a class of GRUMs. We examine the performance of various criteria by
experimental studies, which show that the proposed elicitation scheme increases
the precision of estimation.
Sparse Nested Markov models with Log-linear Parameters
Authors: Ilya Shpitser, Robin J. Evans, Thomas S. Richardson, James M. Robins
Date: 2013-09-26 00:00:00
Tasks: Causal Inference

Hidden variables are ubiquitous in practical data analysis, and therefore
modeling marginal densities and doing inference with the resulting models is an
important problem in statistics, machine learning, and causal inference.
Recently, a new type of graphical model, called the nested Markov model, was
developed which captures equality constraints found in marginals of directed
acyclic graph (DAG) models. Some of these constraints, such as the so called
`Verma constraint', strictly generalize conditional independence. To make
modeling and inference with nested Markov models practical, it is necessary to
limit the number of parameters in the model, while still correctly capturing
the constraints in the marginal of a DAG model. Placing such limits is similar
in spirit to sparsity methods for undirected graphical models, and regression
models. In this paper, we give a log-linear parameterization which allows
sparse modeling with nested Markov models. We illustrate the advantages of this
parameterization with a simulation study.
Determinantal Clustering Processes - A Nonparametric Bayesian Approach to Kernel Based Semi-Supervised Clustering
Authors: Amar Shah, Zoubin Ghahramani
Date: 2013-09-26 00:00:00
Tasks: Clustering

Semi-supervised clustering is the task of clustering data points into
clusters where only a fraction of the points are labelled. The true number of
clusters in the data is often unknown and most models require this parameter as
an input. Dirichlet process mixture models are appealing as they can infer the
number of clusters from the data. However, these models do not deal with high
dimensional data well and can encounter difficulties in inference. We present a
novel nonparameteric Bayesian kernel based method to cluster data points
without the need to prespecify the number of clusters or to model complicated
densities from which data points are assumed to be generated from. The key
insight is to use determinants of submatrices of a kernel matrix as a measure
of how close together a set of points are. We explore some theoretical
properties of the model and derive a natural Gibbs based algorithm with MCMC
hyperparameter learning. The model is implemented on a variety of synthetic and
real world data sets.
Identifying Finite Mixtures of Nonparametric Product Distributions and Causal Inference of Confounders
Authors: Eleni Sgouritsa, Dominik Janzing, Jonas Peters, Bernhard Schoelkopf
Date: 2013-09-26 00:00:00
Tasks: Causal Inference

We propose a kernel method to identify finite mixtures of nonparametric
product distributions. It is based on a Hilbert space embedding of the joint
distribution. The rank of the constructed tensor is equal to the number of
mixture components. We present an algorithm to recover the components by
partitioning the data points into clusters such that the variables are jointly
conditionally independent given the cluster. This method can be used to
identify finite confounders.
The Supervised IBP: Neighbourhood Preserving Infinite Latent Feature Models
Authors: Novi Quadrianto, Viktoriia Sharmanska, David A. Knowles, Zoubin Ghahramani
Date: 2013-09-26 00:00:00
Tasks: Retrieval

We propose a probabilistic model to infer supervised latent variables in the
Hamming space from observed data. Our model allows simultaneous inference of
the number of binary latent variables, and their values. The latent variables
preserve neighbourhood structure of the data in a sense that objects in the
same semantic concept have similar latent values, and objects in different
concepts have dissimilar latent values. We formulate the supervised infinite
latent variable problem based on an intuitive principle of pulling objects
together if they are of the same type, and pushing them apart if they are not.
We then combine this principle with a flexible Indian Buffet Process prior on
the latent variables. We show that the inferred supervised latent variables can
be directly used to perform a nearest neighbour search for the purpose of
retrieval. We introduce a new application of dynamically extending hash codes,
and show how to effectively couple the structure of the hash codes with
continuously growing structure of the neighbourhood preserving infinite latent
feature space.
Solution Methods for Constrained Markov Decision Process with Continuous Probability Modulation
Authors: Marek Petrik, Dharmashankar Subramanian, Janusz Marecki
Date: 2013-09-26 00:00:00

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.
Approximation of Lorenz-Optimal Solutions in Multiobjective Markov Decision Processes
Authors: Patrice Perny, Paul Weng, Judy Goldsmith, Josiah Hanna
Date: 2013-09-26 00:00:00

This paper is devoted to fair optimization in Multiobjective Markov Decision
Processes (MOMDPs). A MOMDP is an extension of the MDP model for planning under
uncertainty while trying to optimize several reward functions simultaneously.
This applies to multiagent problems when rewards define individual utility
functions, or in multicriteria problems when rewards refer to different
features. In this setting, we study the determination of policies leading to
Lorenz-non-dominated tradeoffs. Lorenz dominance is a refinement of Pareto
dominance that was introduced in Social Choice for the measurement of
inequalities. In this paper, we introduce methods to efficiently approximate
the sets of Lorenz-non-dominated solutions of infinite-horizon, discounted
MOMDPs. The approximations are polynomial-sized subsets of those solutions.
Evaluating computational models of explanation using human judgments
Authors: Michael Pacer, Joseph Williams, Xi Chen, Tania Lombrozo, Thomas Griffiths
Date: 2013-09-26 00:00:00

We evaluate four computational models of explanation in Bayesian networks by
comparing model predictions to human judgments. In two experiments, we present
human participants with causal structures for which the models make divergent
predictions and either solicit the best explanation for an observed event
(Experiment 1) or have participants rate provided explanations for an observed
event (Experiment 2). Across two versions of two causal structures and across
both experiments, we find that the Causal Explanation Tree and Most Relevant
Explanation models provide better fits to human data than either Most Probable
Explanation or Explanation Tree models. We identify strengths and shortcomings
of these models and what they can reveal about human explanation. We conclude
by suggesting the value of pursuing computational and psychological
investigations of explanation in parallel.
Stochastic Rank Aggregation
Authors: Shuzi Niu, Yanyan Lan, Jiafeng Guo, Xue-Qi Cheng
Date: 2013-09-26 00:00:00

This paper addresses the problem of rank aggregation, which aims to find a
consensus ranking among multiple ranking inputs. Traditional rank aggregation
methods are deterministic, and can be categorized into explicit and implicit
methods depending on whether rank information is explicitly or implicitly
utilized. Surprisingly, experimental results on real data sets show that
explicit rank aggregation methods would not work as well as implicit methods,
although rank information is critical for the task. Our analysis indicates that
the major reason might be the unreliable rank information from incomplete
ranking inputs. To solve this problem, we propose to incorporate uncertainty
into rank aggregation and tackle the problem in both unsupervised and
supervised scenario. We call this novel framework {stochastic rank aggregation}
(St.Agg for short). Specifically, we introduce a prior distribution on ranks,
and transform the ranking functions or objectives in traditional explicit
methods to their expectations over this distribution. Our experiments on
benchmark data sets show that the proposed St.Agg outperforms the baselines in
both unsupervised and supervised scenarios.
Treedy: A Heuristic for Counting and Sampling Subsets
Authors: Teppo Niinimaki, Mikko Koivisto
Date: 2013-09-26 00:00:00

Consider a collection of weighted subsets of a ground set N. Given a query
subset Q of N, how fast can one (1) find the weighted sum over all subsets of
Q, and (2) sample a subset of Q proportionally to the weights? We present a
tree-based greedy heuristic, Treedy, that for a given positive tolerance d
answers such counting and sampling queries to within a guaranteed relative
error d and total variation distance d, respectively. Experimental results on
artificial instances and in application to Bayesian structure discovery in
Bayesian networks show that approximations yield dramatic savings in running
time compared to exact computation, and that Treedy typically outperforms a
previously proposed sorting-based heuristic.
Structured Convex Optimization under Submodular Constraints
Authors: Kiyohito Nagano, Yoshinobu Kawahara
Date: 2013-09-26 00:00:00
Tasks: BIG-bench Machine Learning

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.