pwc-archive/papers-with-abstracts huggingface dataset:
Learning Nash Equilibria in Congestion Games
Authors: Walid Krichene, Benjamin Drighès, Alexandre M. Bayen
Date: 2014-07-31 00:00:00

We study the repeated congestion game, in which multiple populations of
players share resources, and make, at each iteration, a decentralized decision
on which resources to utilize. We investigate the following question: given a
model of how individual players update their strategies, does the resulting
dynamics of strategy profiles converge to the set of Nash equilibria of the
one-shot game? We consider in particular a model in which players update their
strategies using algorithms with sublinear discounted regret. We show that the
resulting sequence of strategy profiles converges to the set of Nash equilibria
in the sense of Ces\`aro means. However, strong convergence is not guaranteed
in general. We show that strong convergence can be guaranteed for a class of
algorithms with a vanishing upper bound on discounted regret, and which satisfy
an additional condition. We call such algorithms AREP algorithms, for
Approximate REPlicator, as they can be interpreted as a discrete-time
approximation of the replicator equation, which models the continuous-time
evolution of population strategies, and which is known to converge for the
class of congestion games. In particular, we show that the discounted Hedge
algorithm belongs to the AREP class, which guarantees its strong convergence.
A Bottom-Up Approach for Automatic Pancreas Segmentation in Abdominal CT Scans
Authors: Amal Farag, Le Lu, Evrim Turkbey, Jiamin Liu, Ronald M. Summers
Date: 2014-07-31 00:00:00
Tasks: Clustering, Computed Tomography (CT), Organ Segmentation, Pancreas Segmentation, Segmentation, Superpixels

Organ segmentation is a prerequisite for a computer-aided diagnosis (CAD)
system to detect pathologies and perform quantitative analysis. For
anatomically high-variability abdominal organs such as the pancreas, previous
segmentation works report low accuracies when comparing to organs like the
heart or liver. In this paper, a fully-automated bottom-up method is presented
for pancreas segmentation, using abdominal computed tomography (CT) scans. The
method is based on a hierarchical two-tiered information propagation by
classifying image patches. It labels superpixels as pancreas or not via pooling
patch-level confidences on 2D CT slices over-segmented by the Simple Linear
Iterative Clustering approach. A supervised random forest (RF) classifier is
trained on the patch level and a two-level cascade of RFs is applied at the
superpixel level, coupled with multi-channel feature extraction, respectively.
On six-fold cross-validation using 80 patient CT volumes, we achieved 68.8%
Dice coefficient and 57.2% Jaccard Index, comparable to or slightly better than
published state-of-the-art methods.
Constrained Parametric Proposals and Pooling Methods for Semantic Segmentation in RGB-D Images
Authors: Dan Banica, Cristian Sminchisescu
Date: 2013-12-30 00:00:00
Tasks: Scene Classification, Segmentation, Semantic Segmentation

We focus on the problem of semantic segmentation based on RGB-D data, with
emphasis on analyzing cluttered indoor scenes containing many instances from
many visual categories. Our approach is based on a parametric figure-ground
intensity and depth-constrained proposal process that generates spatial layout
hypotheses at multiple locations and scales in the image followed by a
sequential inference algorithm that integrates the proposals into a complete
scene estimate. Our contributions can be summarized as proposing the following:
(1) a generalization of parametric max flow figure-ground proposal methodology
to take advantage of intensity and depth information, in order to
systematically and efficiently generate the breakpoints of an underlying
spatial model in polynomial time, (2) new region description methods based on
second-order pooling over multiple features constructed using both intensity
and depth channels, (3) an inference procedure that can resolve conflicts in
overlapping spatial partitions, and handles scenes with a large number of
objects category instances, of very different scales, (4) extensive evaluation
of the impact of depth, as well as the effectiveness of a large number of
descriptors, both pre-designed and automatically obtained using deep learning,
in a difficult RGB-D semantic segmentation problem with 92 classes. We report
state of the art results in the challenging NYU Depth v2 dataset, extended for
RMRC 2013 Indoor Segmentation Challenge, where currently the proposed model
ranks first, with an average score of 24.61% and a number of 39 classes won.
Moreover, we show that by combining second-order and deep learning features,
over 15% relative accuracy improvements can be additionally achieved. In a
scene classification benchmark, our methodology further improves the state of
the art by 24%.
MONEYBaRL: Exploiting pitcher decision-making using Reinforcement Learning
Authors: Gagan Sidhu, Brian Caffo
Date: 2014-07-31 00:00:00
Tasks: BIG-bench Machine Learning, Decision Making, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

This manuscript uses machine learning techniques to exploit baseball
pitchers' decision making, so-called "Baseball IQ," by modeling the at-bat
information, pitch selection and counts, as a Markov Decision Process (MDP).
Each state of the MDP models the pitcher's current pitch selection in a
Markovian fashion, conditional on the information immediately prior to making
the current pitch. This includes the count prior to the previous pitch, his
ensuing pitch selection, the batter's ensuing action and the result of the
pitch.
A New Model of Array Grammar for generating Connected Patterns on an Image Neighborhood
Authors: G. Vishnu Murthy, Pavan Kumar C., Vakulabharanam Vijaya Kumar
Date: 2014-07-31 00:00:00
Tasks: General Classification

Study of patterns on images is recognized as an important step in
characterization and classification of image. The ability to efficiently
analyze and describe image patterns is thus of fundamental importance. The
study of syntactic methods of describing pictures has been of interest for
researchers. Array Grammars can be used to represent and recognize connected
patterns. In any image the patterns are recognized using connected patterns. It
is very difficult to represent all connected patterns (CP) even on a small 3 x
3 neighborhood in a pictorial way. The present paper proposes the model of
array grammar capable of generating any kind of simple or complex pattern and
derivation of connected pattern in an image neighborhood using the proposed
grammar is discussed.
Learning Mixtures of Linear Classifiers
Authors: Yuekai Sun, Stratis Ioannidis, Andrea Montanari
Date: 2013-11-11 00:00:00
Tasks: regression

We consider a discriminative learning (regression) problem, whereby the
regression function is a convex combination of k linear classifiers. Existing
approaches are based on the EM algorithm, or similar techniques, without
provable guarantees. We develop a simple method based on spectral techniques
and a `mirroring' trick, that discovers the subspace spanned by the
classifiers' parameter vectors. Under a probabilistic assumption on the feature
vector distribution, we prove that this approach has nearly optimal statistical
efficiency.
Recommending with an Agenda: Active Learning of Private Attributes using Matrix Factorization
Authors: Smriti Bhagat, Udi Weinsberg, Stratis Ioannidis, Nina Taft
Date: 2013-11-26 00:00:00
Tasks: Active Learning, Recommendation Systems

Recommender systems leverage user demographic information, such as age,
gender, etc., to personalize recommendations and better place their targeted
ads. Oftentimes, users do not volunteer this information due to privacy
concerns, or due to a lack of initiative in filling out their online profiles.
We illustrate a new threat in which a recommender learns private attributes of
users who do not voluntarily disclose them. We design both passive and active
attacks that solicit ratings for strategically selected items, and could thus
be used by a recommender system to pursue this hidden agenda. Our methods are
based on a novel usage of Bayesian matrix factorization in an active learning
setting. Evaluations on multiple datasets illustrate that such attacks are
indeed feasible and use significantly fewer rated items than static inference
methods. Importantly, they succeed without sacrificing the quality of
recommendations to users.
Two-pass Discourse Segmentation with Pairing and Global Features
Authors: Vanessa Wei Feng, Graeme Hirst
Date: 2014-07-30 00:00:00
Tasks: Discourse Segmentation, Segmentation, Sentence, Vocal Bursts Valence Prediction

Previous attempts at RST-style discourse segmentation typically adopt
features centered on a single token to predict whether to insert a boundary
before that token. In contrast, we develop a discourse segmenter utilizing a
set of pairing features, which are centered on a pair of adjacent tokens in the
sentence, by equally taking into account the information from both tokens.
Moreover, we propose a novel set of global features, which encode
characteristics of the segmentation as a whole, once we have an initial
segmentation. We show that both the pairing and global features are useful on
their own, and their combination achieved an $F_1$ of 92.6% of identifying
in-sentence discourse boundaries, which is a 17.8% error-rate reduction over
the state-of-the-art performance, approaching 95% of human performance. In
addition, similar improvement is observed across different classification
frameworks.
Fast Bayesian Feature Selection for High Dimensional Linear Regression in Genomics via the Ising Approximation
Authors: Charles K. Fisher, Pankaj Mehta
Date: 2014-07-30 00:00:00
Tasks: feature selection, regression

Feature selection, identifying a subset of variables that are relevant for
predicting a response, is an important and challenging component of many
methods in statistics and machine learning. Feature selection is especially
difficult and computationally intensive when the number of variables approaches
or exceeds the number of samples, as is often the case for many genomic
datasets. Here, we introduce a new approach -- the Bayesian Ising Approximation
(BIA) -- to rapidly calculate posterior probabilities for feature relevance in
L2 penalized linear regression. In the regime where the regression problem is
strongly regularized by the prior, we show that computing the marginal
posterior probabilities for features is equivalent to computing the
magnetizations of an Ising model. Using a mean field approximation, we show it
is possible to rapidly compute the feature selection path described by the
posterior probabilities as a function of the L2 penalty. We present simulations
and analytical results illustrating the accuracy of the BIA on some simple
regression problems. Finally, we demonstrate the applicability of the BIA to
high dimensional regression by analyzing a gene expression dataset with nearly
30,000 features.
Market Making with Decreasing Utility for Information
Authors: Miroslav Dudík, Rafael Frongillo, Jennifer Wortman Vaughan
Date: 2014-07-30 00:00:00

We study information elicitation in cost-function-based combinatorial
prediction markets when the market maker's utility for information decreases
over time. In the sudden revelation setting, it is known that some piece of
information will be revealed to traders, and the market maker wishes to prevent
guaranteed profits for trading on the sure information. In the gradual decrease
setting, the market maker's utility for (partial) information decreases
continuously over time. We design adaptive cost functions for both settings
which: (1) preserve the information previously gathered in the market; (2)
eliminate (or diminish) rewards to traders for the publicly revealed
information; (3) leave the reward structure unaffected for other information;
and (4) maintain the market maker's worst-case loss. Our constructions utilize
mixed Bregman divergence, which matches our notion of utility for information.
Consistent transformations of belief functions
Authors: Fabio Cuzzolin
Date: 2014-07-30 00:00:00

Consistent belief functions represent collections of coherent or
non-contradictory pieces of evidence, but most of all they are the counterparts
of consistent knowledge bases in belief calculus. The use of consistent
transformations cs[.] in a reasoning process to guarantee coherence can
therefore be desirable, and generalizes similar techniques in classical logic.
Transformations can be obtained by minimizing an appropriate distance measure
between the original belief function and the collection of consistent ones. We
focus here on the case in which distances are measured using classical Lp
norms, in both the "mass space" and the "belief space" representation of belief
functions. While mass consistent approximations reassign the mass not focussed
on a chosen element of the frame either to the whole frame or to all supersets
of the element on an equal basis, approximations in the belief space do
distinguish these focal elements according to the "focussed consistent
transformation" principle. The different approximations are interpreted and
compared, with the help of examples.
People are Strange when you're a Stranger: Impact and Influence of Bots on Social Networks
Authors: Luca Maria Aiello, Martina Deplano, Rossano Schifanella, Giancarlo Ruffo
Date: 2014-07-30 00:00:00

Bots are, for many Web and social media users, the source of many dangerous
attacks or the carrier of unwanted messages, such as spam. Nevertheless,
crawlers and software agents are a precious tool for analysts, and they are
continuously executed to collect data or to test distributed applications.
However, no one knows which is the real potential of a bot whose purpose is to
control a community, to manipulate consensus, or to influence user behavior. It
is commonly believed that the better an agent simulates human behavior in a
social network, the more it can succeed to generate an impact in that
community. We contribute to shed light on this issue through an online social
experiment aimed to study to what extent a bot with no trust, no profile, and
no aims to reproduce human behavior, can become popular and influential in a
social media. Results show that a basic social probing activity can be used to
acquire social relevance on the network and that the so-acquired popularity can
be effectively leveraged to drive users in their social connectivity choices.
We also register that our bot activity unveiled hidden social polarization
patterns in the community and triggered an emotional response of individuals
that brings to light subtle privacy hazards perceived by the user base.
Merging and Shifting of Images with Prominence Coefficient for Predictive Analysis using Combined Image
Authors: T. R. Gopalakrishnan Nair, Richa Sharma
Date: 2014-07-30 00:00:00

Shifting of objects in an image and merging many images after appropriate
shifting is being used in several engineering and scientific applications which
require complex perception development. A method has been presented here which
could be used in precision engineering and biological applications where more
precise prediction is required of a combined phenomenon with varying prominence
of each phenomenon. Accurate merging of intended pixels can be achieved in high
quality using frequency domain techniques even though initial properties of the
original pixels are lost in this process. This paper introduces a technique to
shift and merge various images with varying prominence of each image. A
coefficient named prominence coefficient has been introduced which is capable
of making some of the images transparent and highlighting the rest as per
requirement of merging process which can be used as a simple but effective
technique for overlapped view of a set of images.
Clustering Approach Towards Image Segmentation: An Analytical Study
Authors: Dibya Jyoti Bora, Anil Kumar Gupta
Date: 2014-07-30 00:00:00
Tasks: Clustering, Image Segmentation, Segmentation, Semantic Segmentation

Image processing is an important research area in computer vision. Image
segmentation plays the vital rule in image processing research. There exist so
many methods for image segmentation. Clustering is an unsupervised study.
Clustering can also be used for image segmentation. In this paper, an in-depth
study is done on different clustering techniques that can be used for image
segmentation with their pros and cons. An experiment for color image
segmentation based on clustering with K-Means algorithm is performed to observe
the accuracy of clustering technique for the segmentation purpose.
The Grow-Shrink strategy for learning Markov network structures constrained by context-specific independences
Authors: Alejandro Edera, Yanela Strappa, Facundo Bromberg
Date: 2014-07-30 00:00:00

Markov networks are models for compactly representing complex probability
distributions. They are composed by a structure and a set of numerical weights.
The structure qualitatively describes independences in the distribution, which
can be exploited to factorize the distribution into a set of compact functions.
A key application for learning structures from data is to automatically
discover knowledge. In practice, structure learning algorithms focused on
"knowledge discovery" present a limitation: they use a coarse-grained
representation of the structure. As a result, this representation cannot
describe context-specific independences. Very recently, an algorithm called
CSPC was designed to overcome this limitation, but it has a high computational
complexity. This work tries to mitigate this downside presenting CSGS, an
algorithm that uses the Grow-Shrink strategy for reducing unnecessary
computations. On an empirical evaluation, the structures learned by CSGS
achieve competitive accuracies and lower computational complexity with respect
to those obtained by CSPC.
Differentially-Private Logistic Regression for Detecting Multiple-SNP Association in GWAS Databases
Authors: Fei Yu, Michal Rybar, Caroline Uhler, Stephen E. Fienberg
Date: 2014-07-30 00:00:00
Tasks: Privacy Preserving, regression

Following the publication of an attack on genome-wide association studies
(GWAS) data proposed by Homer et al., considerable attention has been given to
developing methods for releasing GWAS data in a privacy-preserving way. Here,
we develop an end-to-end differentially private method for solving regression
problems with convex penalty functions and selecting the penalty parameters by
cross-validation. In particular, we focus on penalized logistic regression with
elastic-net regularization, a method widely used to in GWAS analyses to
identify disease-causing genes. We show how a differentially private procedure
for penalized logistic regression with elastic-net regularization can be
applied to the analysis of GWAS data and evaluate our method's performance.
Targeting Optimal Active Learning via Example Quality
Authors: Lewis P. G. Evans, Niall M. Adams, Christoforos Anagnostopoulos
Date: 2014-07-30 00:00:00
Tasks: Active Learning, General Classification

In many classification problems unlabelled data is abundant and a subset can
be chosen for labelling. This defines the context of active learning (AL),
where methods systematically select that subset, to improve a classifier by
retraining. Given a classification problem, and a classifier trained on a small
number of labelled examples, consider the selection of a single further
example. This example will be labelled by the oracle and then used to retrain
the classifier. This example selection raises a central question: given a fully
specified stochastic description of the classification problem, which example
is the optimal selection? If optimality is defined in terms of loss, this
definition directly produces expected loss reduction (ELR), a central quantity
whose maximum yields the optimal example selection. This work presents a new
theoretical approach to AL, example quality, which defines optimal AL behaviour
in terms of ELR. Once optimal AL behaviour is defined mathematically, reasoning
about this abstraction provides insights into AL. In a theoretical context the
optimal selection is compared to existing AL methods, showing that heuristics
can make sub-optimal selections. Algorithms are constructed to estimate example
quality directly. A large-scale experimental study shows these algorithms to be
competitive with standard AL methods.
Associative embeddings for large-scale knowledge transfer with self-assessment
Authors: Alexander Vezhnevets, Vittorio Ferrari
Date: 2013-12-11 00:00:00
Proceeding: CVPR 2014 6
Tasks: Gaussian Processes, Object Localization, Transfer Learning

We propose a method for knowledge transfer between semantically related
classes in ImageNet. By transferring knowledge from the images that have
bounding-box annotations to the others, our method is capable of automatically
populating ImageNet with many more bounding-boxes and even pixel-level
segmentations. The underlying assumption that objects from semantically related
classes look alike is formalized in our novel Associative Embedding (AE)
representation. AE recovers the latent low-dimensional space of appearance
variations among image windows. The dimensions of AE space tend to correspond
to aspects of window appearance (e.g. side view, close up, background). We
model the overlap of a window with an object using Gaussian Processes (GP)
regression, which spreads annotation smoothly through AE space. The
probabilistic nature of GP allows our method to perform self-assessment, i.e.
assigning a quality estimate to its own output. It enables trading off the
amount of returned annotations for their quality. A large scale experiment on
219 classes and 0.5 million images demonstrates that our method outperforms
state-of-the-art methods and baselines for both object localization and
segmentation. Using self-assessment we can automatically return bounding-box
annotations for 30% of all images with high localization accuracy (i.e.~73%
average overlap with ground-truth).
Automated Machine Learning on Big Data using Stochastic Algorithm Tuning
Authors: Thomas Nickson, Michael A. Osborne, Steven Reece, Stephen J. Roberts
Date: 2014-07-30 00:00:00
Tasks: Bayesian Optimisation, Benchmarking, BIG-bench Machine Learning, Time Series, Time Series Analysis, Time Series Prediction

We introduce a means of automating machine learning (ML) for big data tasks,
by performing scalable stochastic Bayesian optimisation of ML algorithm
parameters and hyper-parameters. More often than not, the critical tuning of ML
algorithm parameters has relied on domain expertise from experts, along with
laborious hand-tuning, brute search or lengthy sampling runs. Against this
background, Bayesian optimisation is finding increasing use in automating
parameter tuning, making ML algorithms accessible even to non-experts. However,
the state of the art in Bayesian optimisation is incapable of scaling to the
large number of evaluations of algorithm performance required to fit realistic
models to complex, big data. We here describe a stochastic, sparse, Bayesian
optimisation strategy to solve this problem, using many thousands of noisy
evaluations of algorithm performance on subsets of data in order to effectively
train algorithms for big data. We provide a comprehensive benchmarking of
possible sparsification strategies for Bayesian optimisation, concluding that a
Nystrom approximation offers the best scaling and performance for real tasks.
Our proposed algorithm demonstrates substantial improvement over the state of
the art in tuning the parameters of a Gaussian Process time series prediction
task on real, big data.