pwc-archive/papers-with-abstracts huggingface dataset:
Leveraging user profile attributes for improving pedagogical accuracy of learning pathways
Authors: Tanmay Sinha, Ankit Banka, Dae Ki Kang
Date: 2014-07-27 00:00:00
Tasks: TAG

In recent years, with the enormous explosion of web based learning resources,
personalization has become a critical factor for the success of services that
wish to leverage the power of Web 2.0. However, the relevance, significance and
impact of tailored content delivery in the learning domain is still
questionable. Apart from considering only interaction based features like
ratings and inferring learner preferences from them, if these services were to
incorporate innate user profile attributes which affect learning activities,
the quality of recommendations produced could be vastly improved. Recognizing
the crucial role of effective guidance in informal educational settings, we
provide a principled way of utilizing multiple sources of information from the
user profile itself for the recommendation task. We explore factors that affect
the choice of learning resources and explain in what way are they helpful to
improve the pedagogical accuracy of learning objects recommended. Through a
systematical application of machine learning techniques, we further provide a
technological solution to convert these indirectly mapped learner specific
attributes into a direct mapping with the learning resources. This mapping has
a distinct advantage of tagging learning resources to make their metadata more
informative. The results of our empirical study depict the similarity of
nominal learning attributes with respect to each other. We further succeed in
capturing the learner subset, whose preferences are most likely to be an
indication of learning resource usage. Our novel system filters learner profile
attributes to discover a tag that links them with learning resources.
Fast Distributed Coordinate Descent for Non-Strongly Convex Losses
Authors: Olivier Fercoq, Zheng Qu, Peter Richtárik, Martin Takáč
Date: 2014-05-21 00:00:00

We propose an efficient distributed randomized coordinate descent method for
minimizing regularized non-strongly convex loss functions. The method attains
the optimal $O(1/k^2)$ convergence rate, where $k$ is the iteration counter.
The core of the work is the theoretical study of stepsize parameters. We have
implemented the method on Archer - the largest supercomputer in the UK - and
show that the method is capable of solving a (synthetic) LASSO optimization
problem with 50 billion variables.
An evolutionary solver for linear integer programming
Authors: João Pedro Pedroso
Date: 2014-07-27 00:00:00

In this paper we introduce an evolutionary algorithm for the solution of
linear integer programs. The strategy is based on the separation of the
variables into the integer subset and the continuous subset; the integer
variables are fixed by the evolutionary system, and the continuous ones are
determined in function of them, by a linear program solver.
  We report results obtained for some standard benchmark problems, and compare
them with those obtained by branch-and-bound. The performance of the
evolutionary algorithm is promising. Good feasible solutions were generally
obtained, and in some of the difficult benchmark tests it outperformed
branch-and-bound.
MDPs with Unawareness
Authors: Joseph Y. Halpern, Nan Rong, Ashutosh Saxena
Date: 2014-07-27 00:00:00
Tasks: Decision Making

Markov decision processes (MDPs) are widely used for modeling decision-making
problems in robotics, automated control, and economics. Traditional MDPs assume
that the decision maker (DM) knows all states and actions. However, this may
not be true in many situations of interest. We define a new framework, MDPs
with unawareness (MDPUs) to deal with the possibilities that a DM may not be
aware of all possible actions. We provide a complete characterization of when a
DM can learn to play near-optimally in an MDPU, and give an algorithm that
learns to play near-optimally when it is possible to do so, as efficiently as
possible. In particular, we characterize when a near-optimal solution can be
found in polynomial time.
A Game-Theoretic Analysis of Updating Sets of Probabilities
Authors: Peter D. Grunwald, Joseph Y. Halpern
Date: 2014-07-27 00:00:00

We consider how an agent should update her uncertainty when it is represented
by a set P of probability distributions and the agent observes that a random
variable X takes on value x, given that the agent makes decisions using the
minimax criterion, perhaps the best-studied and most commonly-used criterion in
the literature. We adopt a game-theoretic framework, where the agent plays
against a bookie, who chooses some distribution from P. We consider two
reasonable games that differ in what the bookie knows when he makes his choice.
Anomalies that have been observed before, like time inconsistency, can be
understood as arising because different games are being played, against bookies
with different information. We characterize the important special cases in
which the optimal decision rules according to the minimax criterion amount to
either conditioning or simply ignoring the information. Finally, we consider
the relationship between conditioning and calibration when uncertainty is
described by sets of probabilities.
Evidence with Uncertain Likelihoods
Authors: Joseph Y. Halpern, Riccardo Pucella
Date: 2014-07-27 00:00:00

An agent often has a number of hypotheses, and must choose among them based
on observations, or outcomes of experiments. Each of these observations can be
viewed as providing evidence for or against various hypotheses. All the
attempts to formalize this intuition up to now have assumed that associated
with each hypothesis h there is a likelihood function {\mu}h, which is a
probability measure that intuitively describes how likely each observation is,
conditional on h being the correct hypothesis. We consider an extension of this
framework where there is uncertainty as to which of a number of likelihood
functions is appropriate, and discuss how one formal approach to defining
evidence, which views evidence as a function from priors to posteriors, can be
generalized to accommodate this uncertainty.
When Ignorance is Bliss
Authors: Peter D. Grunwald, Joseph Y. Halpern
Date: 2014-07-27 00:00:00

It is commonly-accepted wisdom that more information is better, and that
information should never be ignored. Here we argue, using both a Bayesian and a
non-Bayesian analysis, that in some situations you are better off ignoring
information if your uncertainty is represented by a set of probability
measures. These include situations in which the information is relevant for the
prediction task at hand. In the non-Bayesian analysis, we show how ignoring
information avoids dilation, the phenomenon that additional pieces of
information sometimes lead to an increase in uncertainty. In the Bayesian
analysis, we show that for small sample sizes and certain prediction tasks, the
Bayesian posterior based on a noninformative prior yields worse predictions
than simply ignoring the given information.
A Logic for Reasoning about Evidence
Authors: Joseph Y. Halpern, Riccardo Pucella
Date: 2014-07-27 00:00:00

We introduce a logic for reasoning about evidence, that essentially views
evidence as a function from prior beliefs (before making an observation) to
posterior beliefs (after making the observation). We provide a sound and
complete axiomatization for the logic, and consider the complexity of the
decision problem. Although the reasoning in the logic is mainly propositional,
we allow variables representing numbers and quantification over them. This
expressive power seems necessary to capture important properties of evidence
Reasoning about Expectation
Authors: Joseph Y. Halpern, Riccardo Pucella
Date: 2014-07-27 00:00:00

Expectation is a central notion in probability theory. The notion of
expectation also makes sense for other notions of uncertainty. We introduce a
propositional logic for reasoning about expectation, where the semantics
depends on the underlying representation of uncertainty. We give sound and
complete axiomatizations for the logic in the case that the underlying
representation is (a) probability, (b) sets of probability measures, (c) belief
functions, and (d) possibility measures. We show that this logic is more
expressive than the corresponding logic for reasoning about likelihood in the
case of sets of probability measures, but equi-expressive in the case of
probability, belief, and possibility. Finally, we show that satisfiability for
these logics is NP-complete, no harder than satisfiability for propositional
logic.
Updating Probabilities
Authors: Peter D. Grunwald, Joseph Y. Halpern
Date: 2014-07-27 00:00:00

As examples such as the Monty Hall puzzle show, applying conditioning to
update a probability distribution on a ``naive space', which does not take into
account the protocol used, can often lead to counterintuitive results. Here we
examine why. A criterion known as CAR (coarsening at random) in the statistical
literature characterizes when ``naive' conditioning in a naive space works. We
show that the CAR condition holds rather infrequently. We then consider more
generalized notions of update such as Jeffrey conditioning and minimizing
relative entropy (MRE). We give a generalization of the CAR condition that
characterizes when Jeffrey conditioning leads to appropriate answers, but show
that there are no such conditions for MRE. This generalizes and interconnects
previous results obtained in the literature on CAR and MRE.
Conditional Plausibility Measures and Bayesian Networks
Authors: Joseph Y. Halpern
Date: 2014-07-27 00:00:00

A general notion of algebraic conditional plausibility measures is defined.
Probability measures, ranking functions, possibility measures, and (under the
appropriate definitions) sets of probability measures can all be viewed as
defining algebraic conditional plausibility measures. It is shown that the
technology of Bayesian networks can be applied to algebraic conditional
plausibility measures.
Defining Relative Likelihood in Partially-Ordered Preferential Structures
Authors: Joseph Y. Halpern
Date: 2014-07-27 00:00:00

Starting with a likelihood or preference order on worlds, we extend it to a
likelihood ordering on sets of worlds in a natural way, and examine the
resulting logic. Lewis (1973) earlier considered such a notion of relative
likelihood in the context of studying counterfactuals, but he assumed a total
preference order on worlds. Complications arise when examining partial orders
that are not present for total orders. There are subtleties involving the exact
approach to lifting the order on worlds to an order on sets of worlds. In
addition, the axiomatization of the logic of relative likelihood in the case of
partial orders gives insight into the connection between relative likelihood
and default reasoning.
Principles and Parameters: a coding theory perspective
Authors: Matilde Marcolli
Date: 2014-07-26 00:00:00

We propose an approach to Longobardi's parametric comparison method (PCM) via
the theory of error-correcting codes. One associates to a collection of
languages to be analyzed with the PCM a binary (or ternary) code with one code
words for each language in the family and each word consisting of the binary
values of the syntactic parameters of the language, with the ternary case
allowing for an additional parameter state that takes into account phenomena of
entailment of parameters. The code parameters of the resulting code can be
compared with some classical bounds in coding theory: the asymptotic bound, the
Gilbert-Varshamov bound, etc. The position of the code parameters with respect
to some of these bounds provides quantitative information on the variability of
syntactic parameters within and across historical-linguistic families. While
computations carried out for languages belonging to the same family yield codes
below the GV curve, comparisons across different historical families can give
examples of isolated codes lying above the asymptotic bound.
Mixture Model Averaging for Clustering
Authors: Yuhong Wei, Paul D. McNicholas
Date: 2012-12-23 00:00:00
Tasks: Clustering, model, Model Selection

In mixture model-based clustering applications, it is common to fit several
models from a family and report clustering results from only the `best' one. In
such circumstances, selection of this best model is achieved using a model
selection criterion, most often the Bayesian information criterion. Rather than
throw away all but the best model, we average multiple models that are in some
sense close to the best one, thereby producing a weighted average of clustering
results. Two (weighted) averaging approaches are considered: averaging the
component membership probabilities and averaging models. In both cases, Occam's
window is used to determine closeness to the best model and weights are
computed within a Bayesian model averaging paradigm. In some cases, we need to
merge components before averaging; we introduce a method for merging mixture
components based on the adjusted Rand index. The effectiveness of our
model-based clustering averaging approaches is illustrated using a family of
Gaussian mixture models on real and simulated data.
Pairwise Correlations in Layered Close-Packed Structures
Authors: P. M. Riechers, D. P. Varn, J. P. Crutchfield
Date: 2014-07-26 00:00:00

Given a description of the stacking statistics of layered close-packed
structures in the form of a hidden Markov model, we develop analytical
expressions for the pairwise correlation functions between the layers. These
may be calculated analytically as explicit functions of model parameters or the
expressions may be used as a fast, accurate, and efficient way to obtain
numerical values. We present several examples, finding agreement with previous
work as well as deriving new relations.
Randomized Block Coordinate Descent for Online and Stochastic Optimization
Authors: Huahua Wang, Arindam Banerjee
Date: 2014-07-01 00:00:00
Tasks: Stochastic Optimization

Two types of low cost-per-iteration gradient descent methods have been
extensively studied in parallel. One is online or stochastic gradient descent
(OGD/SGD), and the other is randomzied coordinate descent (RBCD). In this
paper, we combine the two types of methods together and propose online
randomized block coordinate descent (ORBCD). At each iteration, ORBCD only
computes the partial gradient of one block coordinate of one mini-batch
samples. ORBCD is well suited for the composite minimization problem where one
function is the average of the losses of a large number of samples and the
other is a simple regularizer defined on high dimensional variables. We show
that the iteration complexity of ORBCD has the same order as OGD or SGD. For
strongly convex functions, by reducing the variance of stochastic gradients, we
show that ORBCD can converge at a geometric rate in expectation, matching the
convergence rate of SGD with variance reduction and RBCD.
Decision Trees for Function Evaluation - Simultaneous Optimization of Worst and Expected Cost
Authors: Ferdinando Cicalese, Eduardo Laber, Aline Medeiros Saettler
Date: 2013-09-11 00:00:00
Tasks: Active Learning

In several applications of automatic diagnosis and active learning a central
problem is the evaluation of a discrete function by adaptively querying the
values of its variables until the values read uniquely determine the value of
the function. In general, the process of reading the value of a variable might
involve some cost, computational or even a fee to be paid for the experiment
required for obtaining the value. This cost should be taken into account when
deciding the next variable to read. The goal is to design a strategy for
evaluating the function incurring little cost (in the worst case or in
expectation according to a prior distribution on the possible variables'
assignments). Our algorithm builds a strategy (decision tree) which attains a
logarithmic approxima- tion simultaneously for the expected and worst cost
spent. This is best possible under the assumption that $P \neq NP.$
Bayesian Nonparametric Dictionary Learning for Compressed Sensing MRI
Authors: Yue Huang, John Paisley, Qin Lin, Xinghao Ding, Xueyang Fu, Xiao-Ping Zhang
Date: 2013-02-12 00:00:00
Tasks: compressed sensing, Denoising, Dictionary Learning, Image Reconstruction, Stochastic Optimization

We develop a Bayesian nonparametric model for reconstructing magnetic
resonance images (MRI) from highly undersampled k-space data. We perform
dictionary learning as part of the image reconstruction process. To this end,
we use the beta process as a nonparametric dictionary learning prior for
representing an image patch as a sparse combination of dictionary elements. The
size of the dictionary and the patch-specific sparsity pattern are inferred
from the data, in addition to other dictionary learning variables. Dictionary
learning is performed directly on the compressed image, and so is tailored to
the MRI being considered. In addition, we investigate a total variation penalty
term in combination with the dictionary learning model, and show how the
denoising property of dictionary learning removes dependence on regularization
parameters in the noisy setting. We derive a stochastic optimization algorithm
based on Markov Chain Monte Carlo (MCMC) for the Bayesian model, and use the
alternating direction method of multipliers (ADMM) for efficiently performing
total variation minimization. We present empirical results on several MRI,
which show that the proposed regularization framework can improve
reconstruction accuracy over other methods.
Crowdsourcing Dialect Characterization through Twitter
Authors: Bruno Gonçalves, David Sánchez
Date: 2014-07-26 00:00:00

We perform a large-scale analysis of language diatopic variation using
geotagged microblogging datasets. By collecting all Twitter messages written in
Spanish over more than two years, we build a corpus from which a carefully
selected list of concepts allows us to characterize Spanish varieties on a
global scale. A cluster analysis proves the existence of well defined
macroregions sharing common lexical properties. Remarkably enough, we find that
Spanish language is split into two superdialects, namely, an urban speech used
across major American and Spanish citites and a diverse form that encompasses
rural areas and small towns. The latter can be further clustered into smaller
varieties with a stronger regional character.
Pushbroom Stereo for High-Speed Navigation in Cluttered Environments
Authors: Andrew J. Barry, Russ Tedrake
Date: 2014-07-26 00:00:00
Tasks: CPU, Position, Vocal Bursts Intensity Prediction

We present a novel stereo vision algorithm that is capable of obstacle
detection on a mobile-CPU processor at 120 frames per second. Our system
performs a subset of standard block-matching stereo processing, searching only
for obstacles at a single depth. By using an onboard IMU and state-estimator,
we can recover the position of obstacles at all other depths, building and
updating a full depth-map at framerate.
  Here, we describe both the algorithm and our implementation on a high-speed,
small UAV, flying at over 20 MPH (9 m/s) close to obstacles. The system
requires no external sensing or computation and is, to the best of our
knowledge, the first high-framerate stereo detection system running onboard a
small UAV.
Efficient Bayesian Nonparametric Modelling of Structured Point Processes
Authors: Tom Gunter, Chris Lloyd, Michael A. Osborne, Stephen J. Roberts
Date: 2014-07-25 00:00:00
Tasks: Point Processes

This paper presents a Bayesian generative model for dependent Cox point
processes, alongside an efficient inference scheme which scales as if the point
processes were modelled independently. We can handle missing data naturally,
infer latent structure, and cope with large numbers of observed processes. A
further novel contribution enables the model to work effectively in higher
dimensional spaces. Using this method, we achieve vastly improved predictive
performance on both 2D and 1D real data, validating our structured approach.
An Efficient Two-Stage Sparse Representation Method
Authors: Chengyu Peng, Hong Cheng, Manchor Ko
Date: 2014-04-04 00:00:00
Tasks: Vocal Bursts Valence Prediction

There are a large number of methods for solving under-determined linear
inverse problem. Many of them have very high time complexity for large
datasets. We propose a new method called Two-Stage Sparse Representation (TSSR)
to tackle this problem. We decompose the representing space of signals into two
parts, the measurement dictionary and the sparsifying basis. The dictionary is
designed to approximate a sub-Gaussian distribution to exploit its
concentration property. We apply sparse coding to the signals on the dictionary
in the first stage, and obtain the training and testing coefficients
respectively. Then we design the basis to approach an identity matrix in the
second stage, to acquire the Restricted Isometry Property (RIP) and
universality property. The testing coefficients are encoded over the basis and
the final representing coefficients are obtained. We verify that the projection
of testing coefficients onto the basis is a good approximation of the signal
onto the representing space. Since the projection is conducted on a much
sparser space, the runtime is greatly reduced. For concrete realization, we
provide an instance for the proposed TSSR. Experiments on four biometrics
databases show that TSSR is effective and efficient, comparing with several
classical methods for solving linear inverse problem.
Extending Acyclicity Notions for Existential Rules (\emph{long version})
Authors: Jean-Francois Baget, Fabien Garreau, Marie-Laure Mugnier, Swan Rocher
Date: 2014-07-25 00:00:00
Tasks: Negation

Existential rules have been proposed for representing ontological knowledge,
specifically in the context of Ontology-Based Query Answering. Entailment with
existential rules is undecidable. We focus in this paper on conditions that
ensure the termination of a breadth-first forward chaining algorithm known as
the chase. First, we propose a new tool that allows to extend existing
acyclicity conditions ensuring chase termination, while keeping good complexity
properties. Second, we consider the extension to existential rules with
nonmonotonic negation under stable model semantics and further extend
acyclicity results obtained in the positive case.
Revisiting Chase Termination for Existential Rules and their Extension to Nonmonotonic Negation
Authors: Jean-François Baget, Fabien Garreau, Marie-Laure Mugnier, Swan Rocher
Date: 2014-05-05 00:00:00
Tasks: Negation

Existential rules have been proposed for representing ontological knowledge,
specifically in the context of Ontology- Based Data Access. Entailment with
existential rules is undecidable. We focus in this paper on conditions that
ensure the termination of a breadth-first forward chaining algorithm known as
the chase. Several variants of the chase have been proposed. In the first part
of this paper, we propose a new tool that allows to extend existing acyclicity
conditions ensuring chase termination, while keeping good complexity
properties. In the second part, we study the extension to existential rules
with nonmonotonic negation under stable model semantics, discuss the relevancy
of the chase variants for these rules and further extend acyclicity results
obtained in the positive case.