pwc-archive/papers-with-abstracts huggingface dataset:
PAWL-Forced Simulated Tempering
Authors: Luke Bornn
Date: 2013-05-22 00:00:00

In this short note, we show how the parallel adaptive Wang-Landau (PAWL)
algorithm of Bornn et al. (2013) can be used to automate and improve simulated
tempering algorithms. While Wang-Landau and other stochastic approximation
methods have frequently been applied within the simulated tempering framework,
this note demonstrates through a simple example the additional improvements
brought about by parallelization, adaptive proposals and automated bin
splitting.
Improving NSGA-II with an Adaptive Mutation Operator
Authors: Arthur Carvalho, Aluizio F. R. Araujo
Date: 2013-05-21 00:00:00
Tasks: Diversity

The performance of a Multiobjective Evolutionary Algorithm (MOEA) is
crucially dependent on the parameter setting of the operators. The most desired
control of such parameters presents the characteristic of adaptiveness, i.e.,
the capacity of changing the value of the parameter, in distinct stages of the
evolutionary process, using feedbacks from the search for determining the
direction and/or magnitude of changing. Given the great popularity of the
algorithm NSGA-II, the objective of this research is to create adaptive
controls for each parameter existing in this MOEA. With these controls, we
expect to improve even more the performance of the algorithm.
  In this work, we propose an adaptive mutation operator that has an adaptive
control which uses information about the diversity of candidate solutions for
controlling the magnitude of the mutation. A number of experiments considering
different problems suggest that this mutation operator improves the ability of
the NSGA-II for reaching the Pareto optimal Front and for getting a better
diversity among the final solutions.
Note on Evaluation of Hierarchical Modular Systems
Authors: Mark Sh. Levin
Date: 2013-05-21 00:00:00

This survey note describes a brief systemic view to approaches for evaluation
of hierarchical composite (modular) systems. The list of considered issues
involves the following: (i) basic assessment scales (quantitative scale,
ordinal scale, multicriteria description, two kinds of poset-like scales), (ii)
basic types of scale transformations problems, (iii) basic types of scale
integration methods. Evaluation of the modular systems is considered as
assessment of system components (and their compatibility) and integration of
the obtained local estimates into the total system estimate(s). This process is
based on the above-mentioned problems (i.e., scale transformation and
integration). Illustrations of the assessment problems and evaluation
approaches are presented (including numerical examples).
Out-of-sample Extension for Latent Position Graphs
Authors: Minh Tang, Youngser Park, Carey E. Priebe
Date: 2013-05-21 00:00:00
Tasks: General Classification, Graph Embedding, Position

We consider the problem of vertex classification for graphs constructed from
the latent position model. It was shown previously that the approach of
embedding the graphs into some Euclidean space followed by classification in
that space can yields a universally consistent vertex classifier. However, a
major technical difficulty of the approach arises when classifying unlabeled
out-of-sample vertices without including them in the embedding stage. In this
paper, we studied the out-of-sample extension for the graph embedding step and
its impact on the subsequent inference tasks. We show that, under the latent
position graph model and for sufficiently large $n$, the mapping of the
out-of-sample vertices is close to its true latent position. We then
demonstrate that successful inference for the out-of-sample vertices is
possible.
Optical Flow on Evolving Surfaces with an Application to the Analysis of 4D Microscopy Data
Authors: Clemens Kirisits, Lukas F. Lang, Otmar Scherzer
Date: 2013-01-08 00:00:00
Tasks: Motion Estimation, Optical Flow Estimation

We extend the concept of optical flow to a dynamic non-Euclidean setting.
Optical flow is traditionally computed from a sequence of flat images. It is
the purpose of this paper to introduce variational motion estimation for images
that are defined on an evolving surface. Volumetric microscopy images depicting
a live zebrafish embryo serve as both biological motivation and test data.
Power to the Points: Validating Data Memberships in Clusterings
Authors: Parasaran Raman, Suresh Venkatasubramanian
Date: 2013-05-21 00:00:00
Tasks: Clustering

A clustering is an implicit assignment of labels of points, based on
proximity to other points. It is these labels that are then used for downstream
analysis (either focusing on individual clusters, or identifying
representatives of clusters and so on). Thus, in order to trust a clustering as
a first step in exploratory data analysis, we must trust the labels assigned to
individual data. Without supervision, how can we validate this assignment? In
this paper, we present a method to attach affinity scores to the implicit
labels of individual points in a clustering. The affinity scores capture the
confidence level of the cluster that claims to "own" the point. This method is
very general: it can be used with clusterings derived from Euclidean data,
kernelized data, or even data derived from information spaces. It smoothly
incorporates importance functions on clusters, allowing us to eight different
clusters differently. It is also efficient: assigning an affinity score to a
point depends only polynomially on the number of clusters and is independent of
the number of points in the data. The dimensionality of the underlying space
only appears in preprocessing. We demonstrate the value of our approach with an
experimental study that illustrates the use of these scores in different data
analysis tasks, as well as the efficiency and flexibility of the method. We
also demonstrate useful visualizations of these scores; these might prove
useful within an interactive analytics framework.
The Doxastic Interpretation of Team Semantics
Authors: Pietro Galliani
Date: 2013-05-21 00:00:00

We advance a doxastic interpretation for many of the logical connectives
considered in Dependence Logic and in its extensions, and we argue that Team
Semantics is a natural framework for reasoning about beliefs and belief
updates.
On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
Authors: Zhaosong Lu, Lin Xiao
Date: 2013-05-21 00:00:00

In this paper we analyze the randomized block-coordinate descent (RBCD)
methods proposed in [8,11] for minimizing the sum of a smooth convex function
and a block-separable convex function. In particular, we extend Nesterov's
technique developed in [8] for analyzing the RBCD method for minimizing a
smooth convex function over a block-separable closed convex set to the
aforementioned more general problem and obtain a sharper expected-value type of
convergence rate than the one implied in [11]. Also, we obtain a better
high-probability type of iteration complexity, which improves upon the one in
[11] by at least the amount $O(n/\epsilon)$, where $\epsilon$ is the target
solution accuracy and $n$ is the number of problem blocks. In addition, for
unconstrained smooth convex minimization, we develop a new technique called
{\it randomized estimate sequence} to analyze the accelerated RBCD method
proposed by Nesterov [11] and establish a sharper expected-value type of
convergence rate than the one given in [11].
Nonparametric Unsupervised Classification
Authors: Yingzhen Yang, Thomas S. Huang
Date: 2012-10-02 00:00:00
Tasks: Classification, Clustering, General Classification

Unsupervised classification methods learn a discriminative classifier from
unlabeled data, which has been proven to be an effective way of simultaneously
clustering the data and training a classifier from the data. Various
unsupervised classification methods obtain appealing results by the classifiers
learned in an unsupervised manner. However, existing methods do not consider
the misclassification error of the unsupervised classifiers except unsupervised
SVM, so the performance of the unsupervised classifiers is not fully evaluated.
In this work, we study the misclassification error of two popular classifiers,
i.e. the nearest neighbor classifier (NN) and the plug-in classifier, in the
setting of unsupervised classification.
Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem
Authors: Ittai Abraham, Omar Alonso, Vasilis Kandylas, Aleksandrs Slivkins
Date: 2013-02-13 00:00:00
Tasks: Information Retrieval, Multiple-choice, Retrieval, Survey

Very recently crowdsourcing has become the de facto platform for distributing
and collecting human computation for a wide range of tasks and applications
such as information retrieval, natural language processing and machine
learning. Current crowdsourcing platforms have some limitations in the area of
quality control. Most of the effort to ensure good quality has to be done by
the experimenter who has to manage the number of workers needed to reach good
results.
  We propose a simple model for adaptive quality control in crowdsourced
multiple-choice tasks which we call the \emph{bandit survey problem}. This
model is related to, but technically different from the well-known multi-armed
bandit problem. We present several algorithms for this problem, and support
them with analysis and simulations. Our approach is based in our experience
conducting relevance evaluation for a large commercial search engine.
Efficient Image Retargeting for High Dynamic Range Scenes
Authors: Govind Salvi, Puneet Sharma, Shanmuganathan Raman
Date: 2013-05-20 00:00:00
Tasks: Image Retargeting, Vocal Bursts Intensity Prediction

Most of the real world scenes have a very high dynamic range (HDR). The
mobile phone cameras and the digital cameras available in markets are limited
in their capability in both the range and spatial resolution. Same argument can
be posed about the limited dynamic range display devices which also differ in
the spatial resolution and aspect ratios.
  In this paper, we address the problem of displaying the high contrast low
dynamic range (LDR) image of a HDR scene in a display device which has
different spatial resolution compared to that of the capturing digital camera.
The optimal solution proposed in this work can be employed with any camera
which has the ability to shoot multiple differently exposed images of a scene.
Further, the proposed solutions provide the flexibility in the depiction of
entire contrast of the HDR scene as a LDR image with an user specified spatial
resolution. This task is achieved through an optimized content aware
retargeting framework which preserves salient features along with the algorithm
to combine multi-exposure images. We show the proposed approach performs
exceedingly well in the generation of high contrast LDR image of varying
spatial resolution compared to an alternate approach.
SHARE: A Web Service Based Framework for Distributed Querying and Reasoning on the Semantic Web
Authors: Ben P Vandervalk, E Luke McCarthy, Mark D. Wilkinson
Date: 2013-05-20 00:00:00
Tasks: Retrieval

Here we describe the SHARE system, a web service based framework for
distributed querying and reasoning on the semantic web. The main innovations of
SHARE are: (1) the extension of a SPARQL query engine to perform on-demand data
retrieval from web services, and (2) the extension of an OWL reasoner to test
property restrictions by means of web service invocations. In addition to
enabling queries across distributed datasets, the system allows for a target
dataset that is significantly larger than is possible under current,
centralized approaches. Although the architecture is equally applicable to all
types of data, the SHARE system targets bioinformatics, due to the large number
of interoperable web services that are already available in this area. SHARE is
built entirely on semantic web standards, and is the successor of the BioMOBY
project.
Infinite Shift-invariant Grouped Multi-task Learning for Gaussian Processes
Authors: Yuyang Wang, Roni Khardon, Pavlos Protopapas
Date: 2012-03-05 00:00:00
Tasks: Gaussian Processes, Model Selection, Multi-Task Learning, Time Series, Time Series Analysis

Multi-task learning leverages shared information among data sets to improve
the learning performance of individual tasks. The paper applies this framework
for data where each task is a phase-shifted periodic time series. In
particular, we develop a novel Bayesian nonparametric model capturing a mixture
of Gaussian processes where each task is a sum of a group-specific function and
a component capturing individual variation, in addition to each task being
phase shifted. We develop an efficient \textsc{em} algorithm to learn the
parameters of the model. As a special case we obtain the Gaussian mixture model
and \textsc{em} algorithm for phased-shifted periodic time series. Furthermore,
we extend the proposed model by using a Dirichlet Process prior and thereby
leading to an infinite mixture model that is capable of doing automatic model
selection. A Variational Bayesian approach is developed for inference in this
model. Experiments in regression, classification and class discovery
demonstrate the performance of the proposed models using both synthetic data
and real-world time series data from astrophysics. Our methods are particularly
useful when the time series are sparsely and non-synchronously sampled.
Meta Path-Based Collective Classification in Heterogeneous Information Networks
Authors: Xiangnan Kong, Bokai Cao, Philip S. Yu, Ying Ding, David J. Wild
Date: 2013-05-20 00:00:00
Tasks: Classification, General Classification

Collective classification has been intensively studied due to its impact in
many important applications, such as web mining, bioinformatics and citation
analysis. Collective classification approaches exploit the dependencies of a
group of linked objects whose class labels are correlated and need to be
predicted simultaneously. In this paper, we focus on studying the collective
classification problem in heterogeneous networks, which involves multiple types
of data objects interconnected by multiple types of links. Intuitively, two
objects are correlated if they are linked by many paths in the network.
However, most existing approaches measure the dependencies among objects
through directly links or indirect links without considering the different
semantic meanings behind different paths. In this paper, we study the
collective classification problem taht is defined among the same type of
objects in heterogenous networks. Moreover, by considering different linkage
paths in the network, one can capture the subtlety of different types of
dependencies among objects. We introduce the concept of meta-path based
dependencies among objects, where a meta path is a path consisting a certain
sequence of linke types. We show that the quality of collective classification
results strongly depends upon the meta paths used. To accommodate the large
network size, a novel solution, called HCC (meta-path based Heterogenous
Collective Classification), is developed to effectively assign labels to a
group of instances that are interconnected through different meta-paths. The
proposed HCC model can capture different types of dependencies among objects
with respect to different meta paths. Empirical studies on real-world networks
demonstrate that effectiveness of the proposed meta path-based collective
classification approach.
Quantum and Concept Combination, Entangled Measurements and Prototype Theory
Authors: Diederik Aerts
Date: 2013-03-11 00:00:00

We analyze the meaning of the violation of the marginal probability law for
situations of correlation measurements where entanglement is identified. We
show that for quantum theory applied to the cognitive realm such a violation
does not lead to the type of problems commonly believed to occur in situations
of quantum theory applied to the physical realm. We briefly situate our quantum
approach for modeling concepts and their combinations with respect to the
notions of 'extension' and 'intension' in theories of meaning, and in existing
concept theories.
Online Portfolio Selection: A Survey
Authors: Bin Li, Steven C. H. Hoi
Date: 2012-12-10 00:00:00
Tasks: BIG-bench Machine Learning, Meta-Learning, Survey

Online portfolio selection is a fundamental problem in computational finance,
which has been extensively studied across several research communities,
including finance, statistics, artificial intelligence, machine learning, and
data mining, etc. This article aims to provide a comprehensive survey and a
structural understanding of published online portfolio selection techniques.
From an online machine learning perspective, we first formulate online
portfolio selection as a sequential decision problem, and then survey a variety
of state-of-the-art approaches, which are grouped into several major
categories, including benchmarks, "Follow-the-Winner" approaches,
"Follow-the-Loser" approaches, "Pattern-Matching" based approaches, and
"Meta-Learning Algorithms". In addition to the problem formulation and related
algorithms, we also discuss the relationship of these algorithms with the
Capital Growth theory in order to better understand the similarities and
differences of their underlying trading ideas. This article aims to provide a
timely and comprehensive survey for both machine learning and data mining
researchers in academia and quantitative portfolio managers in the financial
industry to help them understand the state-of-the-art and facilitate their
research and practical applications. We also discuss some open issues and
evaluate some emerging new trends for future research directions.
Ensembles of Classifiers based on Dimensionality Reduction
Authors: Alon Schclar, Lior Rokach, Amir Amit
Date: 2013-05-19 00:00:00
Tasks: Dimensionality Reduction

We present a novel approach for the construction of ensemble classifiers
based on dimensionality reduction. Dimensionality reduction methods represent
datasets using a small number of attributes while preserving the information
conveyed by the original dataset. The ensemble members are trained based on
dimension-reduced versions of the training set. These versions are obtained by
applying dimensionality reduction to the original training set using different
values of the input parameters. This construction meets both the diversity and
accuracy criteria which are required to construct an ensemble classifier where
the former criterion is obtained by the various input parameter values and the
latter is achieved due to the decorrelation and noise reduction properties of
dimensionality reduction. In order to classify a test sample, it is first
embedded into the dimension reduced space of each individual classifier by
using an out-of-sample extension algorithm. Each classifier is then applied to
the embedded sample and the classification is obtained via a voting scheme. We
present three variations of the proposed approach based on the Random
Projections, the Diffusion Maps and the Random Subspaces dimensionality
reduction algorithms. We also present a multi-strategy ensemble which combines
AdaBoost and Diffusion Maps. A comparison is made with the Bagging, AdaBoost,
Rotation Forest ensemble classifiers and also with the base classifier which
does not incorporate dimensionality reduction. Our experiments used seventeen
benchmark datasets from the UCI repository. The results obtained by the
proposed algorithms were superior in many cases to other algorithms.
Generalized Centroid Estimators in Bioinformatics
Authors: Michiaki Hamada, Hisanori Kiryu, Wataru Iwasaki, Kiyoshi Asai
Date: 2013-05-19 00:00:00

In a number of estimation problems in bioinformatics, accuracy measures of
the target problem are usually given, and it is important to design estimators
that are suitable to those accuracy measures. However, there is often a
discrepancy between an employed estimator and a given accuracy measure of the
problem. In this study, we introduce a general class of efficient estimators
for estimation problems on high-dimensional binary spaces, which representmany
fundamental problems in bioinformatics. Theoretical analysis reveals that the
proposed estimators generally fit with commonly-used accuracy measures (e.g.
sensitivity, PPV, MCC and F-score) as well as it can be computed efficiently in
many cases, and cover a wide range of problems in bioinformatics from the
viewpoint of the principle of maximum expected accuracy (MEA). It is also shown
that some important algorithms in bioinformatics can be interpreted in a
unified manner. Not only the concept presented in this paper gives a useful
framework to design MEA-based estimators but also it is highly extendable and
sheds new light on many problems in bioinformatics.
Quantum Annealing for Dirichlet Process Mixture Models with Applications to Network Clustering
Authors: Issei Sato, Shu Tanaka, Kenichi Kurihara, Seiji Miyashita, Hiroshi Nakagawa
Date: 2013-05-19 00:00:00
Tasks: Clustering, Stochastic Optimization

We developed a new quantum annealing (QA) algorithm for Dirichlet process
mixture (DPM) models based on the Chinese restaurant process (CRP). QA is a
parallelized extension of simulated annealing (SA), i.e., it is a parallel
stochastic optimization technique. Existing approaches [Kurihara et al.
UAI2009, Sato et al. UAI2009] and cannot be applied to the CRP because their QA
framework is formulated using a fixed number of mixture components. The
proposed QA algorithm can handle an unfixed number of classes in mixture
models. We applied QA to a DPM model for clustering vertices in a network where
a CRP seating arrangement indicates a network partition. A multi core processor
was used for running QA in experiments, the results of which show that QA is
better than SA, Markov chain Monte Carlo inference, and beam search at finding
a maximum a posteriori estimation of a seating arrangement in the CRP. Since
our QA algorithm is as easy as to implement the SA algorithm, it is suitable
for a wide range of applications.
Horizon-Independent Optimal Prediction with Log-Loss in Exponential Families
Authors: Peter Bartlett, Peter Grunwald, Peter Harremoes, Fares Hedayati, Wojciech Kotlowski
Date: 2013-05-19 00:00:00

We study online learning under logarithmic loss with regular parametric
models. Hedayati and Bartlett (2012b) showed that a Bayesian prediction
strategy with Jeffreys prior and sequential normalized maximum likelihood
(SNML) coincide and are optimal if and only if the latter is exchangeable, and
if and only if the optimal strategy can be calculated without knowing the time
horizon in advance. They put forward the question what families have
exchangeable SNML strategies. This paper fully answers this open problem for
one-dimensional exponential families. The exchangeability can happen only for
three classes of natural exponential family distributions, namely the Gaussian,
Gamma, and the Tweedie exponential family of order 3/2. Keywords: SNML
Exchangeability, Exponential Family, Online Learning, Logarithmic Loss,
Bayesian Strategy, Jeffreys Prior, Fisher Information1
Passive Learning with Target Risk
Authors: Mehrdad Mahdavi, Rong Jin
Date: 2013-02-08 00:00:00
Tasks: Generalization Bounds, Learning Theory, Stochastic Optimization

In this paper we consider learning in passive setting but with a slight
modification. We assume that the target expected loss, also referred to as
target risk, is provided in advance for learner as prior knowledge. Unlike most
studies in the learning theory that only incorporate the prior knowledge into
the generalization bounds, we are able to explicitly utilize the target risk in
the learning process. Our analysis reveals a surprising result on the sample
complexity of learning: by exploiting the target risk in the learning
algorithm, we show that when the loss function is both strongly convex and
smooth, the sample complexity reduces to $\O(\log (\frac{1}{\epsilon}))$, an
exponential improvement compared to the sample complexity
$\O(\frac{1}{\epsilon})$ for learning with strongly convex loss functions.
Furthermore, our proof is constructive and is based on a computationally
efficient stochastic optimization algorithm for such settings which demonstrate
that the proposed algorithm is practically useful.