pwc-archive/papers-with-abstracts huggingface dataset:
Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons
Authors: Dohyung Park, Joe Neeman, Jin Zhang, Sujay Sanghavi, Inderjit S. Dhillon
Date: 2015-07-16 00:00:00
Tasks: Collaborative Filtering, Collaborative Ranking, Matrix Completion

In this paper we consider the collaborative ranking setting: a pool of users
each provides a small number of pairwise preferences between $d$ possible
items; from these we need to predict preferences of the users for items they
have not yet seen. We do so by fitting a rank $r$ score matrix to the pairwise
data, and provide two main contributions: (a) we show that an algorithm based
on convex optimization provides good generalization guarantees once each user
provides as few as $O(r\log^2 d)$ pairwise comparisons -- essentially matching
the sample complexity required in the related matrix completion setting (which
uses actual numerical as opposed to pairwise information), and (b) we develop a
large-scale non-convex implementation, which we call AltSVM, that trains a
factored form of the matrix via alternating minimization (which we show reduces
to alternating SVM problems), and scales and parallelizes very well to large
problem settings. It also outperforms common baselines on many moderately large
popular collaborative filtering datasets in both NDCG and in other measures of
ranking performance.
A Deep Hashing Learning Network
Authors: Guoqiang Zhong, Pan Yang, Sijiang Wang, Junyu Dong
Date: 2015-07-16 00:00:00
Tasks: Deep Hashing, Quantization

Hashing-based methods seek compact and efficient binary codes that preserve
the neighborhood structure in the original data space. For most existing
hashing methods, an image is first encoded as a vector of hand-crafted visual
feature, followed by a hash projection and quantization step to get the compact
binary vector. Most of the hand-crafted features just encode the low-level
information of the input, the feature may not preserve the semantic
similarities of images pairs. Meanwhile, the hashing function learning process
is independent with the feature representation, so the feature may not be
optimal for the hashing projection. In this paper, we propose a supervised
hashing method based on a well designed deep convolutional neural network,
which tries to learn hashing code and compact representations of data
simultaneously. The proposed model learn the binary codes by adding a compact
sigmoid layer before the loss layer. Experiments on several image data sets
show that the proposed model outperforms other state-of-the-art methods.
Joint Tensor Factorization and Outlying Slab Suppression with Applications
Authors: Xiao Fu, Kejun Huang, Wing-Kin Ma, Nicholas D. Sidiropoulos, Rasmus Bro
Date: 2015-07-16 00:00:00
Tasks: Speech Separation

We consider factoring low-rank tensors in the presence of outlying slabs.
This problem is important in practice, because data collected in many
real-world applications, such as speech, fluorescence, and some social network
data, fit this paradigm. Prior work tackles this problem by iteratively
selecting a fixed number of slabs and fitting, a procedure which may not
converge. We formulate this problem from a group-sparsity promoting point of
view, and propose an alternating optimization framework to handle the
corresponding $\ell_p$ ($0<p\leq 1$) minimization-based low-rank tensor
factorization problem. The proposed algorithm features a similar per-iteration
complexity as the plain trilinear alternating least squares (TALS) algorithm.
Convergence of the proposed algorithm is also easy to analyze under the
framework of alternating optimization and its variants. In addition,
regularization and constraints can be easily incorporated to make use of
\emph{a priori} information on the latent loading factors. Simulations and real
data experiments on blind speech separation, fluorescence data analysis, and
social network mining are used to showcase the effectiveness of the proposed
algorithm.
Certifying and removing disparate impact
Authors: Michael Feldman, Sorelle Friedler, John Moeller, Carlos Scheidegger, Suresh Venkatasubramanian
Date: 2014-12-11 00:00:00

What does it mean for an algorithm to be biased? In U.S. law, unintentional
bias is encoded via disparate impact, which occurs when a selection process has
widely different outcomes for different groups, even as it appears to be
neutral. This legal determination hinges on a definition of a protected class
(ethnicity, gender, religious practice) and an explicit description of the
process.
  When the process is implemented using computers, determining disparate impact
(and hence bias) is harder. It might not be possible to disclose the process.
In addition, even if the process is open, it might be hard to elucidate in a
legal setting how the algorithm makes its decisions. Instead of requiring
access to the algorithm, we propose making inferences based on the data the
algorithm uses.
  We make four contributions to this problem. First, we link the legal notion
of disparate impact to a measure of classification accuracy that while known,
has received relatively little attention. Second, we propose a test for
disparate impact based on analyzing the information leakage of the protected
class from the other data attributes. Third, we describe methods by which data
might be made unbiased. Finally, we present empirical evidence supporting the
effectiveness of our test for disparate impact and our approach for both
masking bias and preserving relevant information in the data. Interestingly,
our approach resembles some actual selection practices that have recently
received legal scrutiny.
Bias and population structure in the actuation of sound change
Authors: James Kirby, Morgan Sonderegger
Date: 2015-07-16 00:00:00
Tasks: Inductive Bias

Why do human languages change at some times, and not others? We address this
longstanding question from a computational perspective, focusing on the case of
sound change. Sound change arises from the pronunciation variability ubiquitous
in every speech community, but most such variability does not lead to change.
Hence, an adequate model must allow for stability as well as change. Existing
theories of sound change tend to emphasize factors at the level of individual
learners promoting one outcome or the other, such as channel bias (which favors
change) or inductive bias (which favors stability). Here, we consider how the
interaction of these biases can lead to both stability and change in a
population setting. We find that population structure itself can act as a
source of stability, but that both stability and change are possible only when
both types of bias are active, suggesting that it is possible to understand why
sound change occurs at some times and not others as the population-level result
of the interplay between forces promoting each outcome in individual speakers.
In addition, if it is assumed that learners learn from two or more teachers,
the transition from stability to change is marked by a phase transition,
consistent with the abrupt transitions seen in many empirical cases of sound
change. The predictions of multiple-teacher models thus match empirical cases
of sound change better than the predictions of single-teacher models,
underscoring the importance of modeling language change in a population
setting.
Parallel MMF: a Multiresolution Approach to Matrix Computation
Authors: Risi Kondor, Nedelina Teneva, Pramod K. Mudrakarta
Date: 2015-07-15 00:00:00

Multiresolution Matrix Factorization (MMF) was recently introduced as a
method for finding multiscale structure and defining wavelets on
graphs/matrices. In this paper we derive pMMF, a parallel algorithm for
computing the MMF factorization. Empirically, the running time of pMMF scales
linearly in the dimension for sparse matrices. We argue that this makes pMMF a
valuable new computational primitive in its own right, and present experiments
on using pMMF for two distinct purposes: compressing matrices and
preconditioning large sparse linear systems.
A Generalized Kernel Approach to Structured Output Learning
Authors: Hachem Kadri, Mohammad Ghavamzadeh, Philippe Preux
Date: 2012-05-10 00:00:00
Tasks: regression

We study the problem of structured output learning from a regression
perspective. We first provide a general formulation of the kernel dependency
estimation (KDE) problem using operator-valued kernels. We show that some of
the existing formulations of this problem are special cases of our framework.
We then propose a covariance-based operator-valued kernel that allows us to
take into account the structure of the kernel feature space. This kernel
operates on the output space and encodes the interactions between the outputs
without any reference to the input space. To address this issue, we introduce a
variant of our KDE method based on the conditional covariance operator that in
addition to the correlation between the outputs takes into account the effects
of the input variables. Finally, we evaluate the performance of our KDE
approach using both covariance and conditional covariance kernels on two
structured output problems, and compare it to the state-of-the-art kernel-based
structured output regression methods.
Learning Boolean functions with concentrated spectra
Authors: Dustin G. Mixon, Jesse Peterson
Date: 2015-07-15 00:00:00
Tasks: General Classification

This paper discusses the theory and application of learning Boolean functions
that are concentrated in the Fourier domain. We first estimate the VC dimension
of this function class in order to establish a small sample complexity of
learning in this case. Next, we propose a computationally efficient method of
empirical risk minimization, and we apply this method to the MNIST database of
handwritten digits. These results demonstrate the effectiveness of our model
for modern classification tasks. We conclude with a list of open problems for
future investigation.
Learning Action Models: Qualitative Approach
Authors: Thomas Bolander, Nina Gierasimczuk
Date: 2015-07-15 00:00:00

In dynamic epistemic logic, actions are described using action models. In
this paper we introduce a framework for studying learnability of action models
from observations. We present first results concerning propositional action
models. First we check two basic learnability criteria: finite identifiability
(conclusively inferring the appropriate action model in finite time) and
identifiability in the limit (inconclusive convergence to the right action
model). We show that deterministic actions are finitely identifiable, while
non-deterministic actions require more learning power-they are identifiable in
the limit. We then move on to a particular learning method, which proceeds via
restriction of a space of events within a learning-specific action model. This
way of learning closely resembles the well-known update method from dynamic
epistemic logic. We introduce several different learning methods suited for
finite identifiability of particular types of deterministic actions.
The Role of Principal Angles in Subspace Classification
Authors: Jiaji Huang, Qiang Qiu, Robert Calderbank
Date: 2015-07-15 00:00:00
Tasks: Classification, General Classification

Subspace models play an important role in a wide range of signal processing
tasks, and this paper explores how the pairwise geometry of subspaces
influences the probability of misclassification. When the mismatch between the
signal and the model is vanishingly small, the probability of misclassification
is determined by the product of the sines of the principal angles between
subspaces. When the mismatch is more significant, the probability of
misclassification is determined by the sum of the squares of the sines of the
principal angles. Reliability of classification is derived in terms of the
distribution of signal energy across principal vectors. Larger principal angles
lead to smaller classification error, motivating a linear transform that
optimizes principal angles. The transform presented here (TRAIT) preserves some
specific characteristic of each individual class, and this approach is shown to
be complementary to a previously developed transform (LRT) that enlarges
inter-class distance while suppressing intra-class dispersion. Theoretical
results are supported by demonstration of superior classification accuracy on
synthetic and measured data even in the presence of significant model mismatch.
Associative Measures and Multi-word Unit Extraction in Turkish
Authors: Umit Mersinli
Date: 2015-07-15 00:00:00
Tasks: Sentence

Associative measures are "mathematical formulas determining the strength of
association between two or more words based on their occurrences and
cooccurrences in a text corpus" (Pecina, 2010, p. 138). The purpose of this
paper is to test the 12 associative measures that Text-NSP (Banerjee &
Pedersen, 2003) contains on a 10-million-word subcorpus of Turkish National
Corpus (TNC) (Aksan et.al., 2012). A statistical comparison of those measures
is out of the scope of the study, and the measures will be evaluated according
to the linguistic relevance of the rankings they provide. The focus of the
study is basically on optimizing the corpus data, before applying the measures
and then, evaluating the rankings produced by these measures as a whole, not on
the linguistic relevance of individual n-grams. The findings include
intra-linguistically relevant associative measures for a comma delimited,
sentence splitted, lower-cased, well-balanced, representative, 10-million-word
corpus of Turkish.
Bayesian Modeling with Gaussian Processes using the GPstuff Toolbox
Authors: Jarno Vanhatalo, Jaakko Riihimäki, Jouni Hartikainen, Pasi Jylänki, Ville Tolvanen, Aki Vehtari
Date: 2012-06-25 00:00:00
Tasks: Gaussian Processes

Gaussian processes (GP) are powerful tools for probabilistic modeling
purposes. They can be used to define prior distributions over latent functions
in hierarchical Bayesian models. The prior over functions is defined implicitly
by the mean and covariance function, which determine the smoothness and
variability of the function. The inference can then be conducted directly in
the function space by evaluating or approximating the posterior process.
Despite their attractive theoretical properties GPs provide practical
challenges in their implementation. GPstuff is a versatile collection of
computational tools for GP models compatible with Linux and Windows MATLAB and
Octave. It includes, among others, various inference methods, sparse
approximations and tools for model assessment. In this work, we review these
tools and demonstrate the use of GPstuff in several models.
Predictive Entropy Search for Bayesian Optimization with Unknown Constraints
Authors: José Miguel Hernández-Lobato, Michael A. Gelbart, Matthew W. Hoffman, Ryan P. Adams, Zoubin Ghahramani
Date: 2015-02-18 00:00:00
Tasks: Bayesian Optimization

Unknown constraints arise in many types of expensive black-box optimization
problems. Several methods have been proposed recently for performing Bayesian
optimization with constraints, based on the expected improvement (EI)
heuristic. However, EI can lead to pathologies when used with constraints. For
example, in the case of decoupled constraints---i.e., when one can
independently evaluate the objective or the constraints---EI can encounter a
pathology that prevents exploration. Additionally, computing EI requires a
current best solution, which may not exist if none of the data collected so far
satisfy the constraints. By contrast, information-based approaches do not
suffer from these failure modes. In this paper, we present a new
information-based method called Predictive Entropy Search with Constraints
(PESC). We analyze the performance of PESC and show that it compares favorably
to EI-based approaches on synthetic and benchmark problems, as well as several
real-world examples. We demonstrate that PESC is an effective algorithm that
provides a promising direction towards a unified solution for constrained
Bayesian optimization.
ALEVS: Active Learning by Statistical Leverage Sampling
Authors: Cem Orhan, Öznur Taştan
Date: 2015-07-15 00:00:00
Tasks: Active Learning, Binary Classification, Informativeness

Active learning aims to obtain a classifier of high accuracy by using fewer
label requests in comparison to passive learning by selecting effective
queries. Many active learning methods have been developed in the past two
decades, which sample queries based on informativeness or representativeness of
unlabeled data points. In this work, we explore a novel querying criterion
based on statistical leverage scores. The statistical leverage scores of a row
in a matrix are the squared row-norms of the matrix containing its (top) left
singular vectors and is a measure of influence of the row on the matrix.
Leverage scores have been used for detecting high influential points in
regression diagnostics and have been recently shown to be useful for data
analysis and randomized low-rank matrix approximation algorithms. We explore
how sampling data instances with high statistical leverage scores perform in
active learning. Our empirical comparison on several binary classification
datasets indicate that querying high leverage points is an effective strategy.
Probabilistic Backpropagation for Scalable Learning of Bayesian Neural Networks
Authors: José Miguel Hernández-Lobato, Ryan P. Adams
Date: 2015-02-18 00:00:00

Large multilayer neural networks trained with backpropagation have recently
achieved state-of-the-art results in a wide range of problems. However, using
backprop for neural net learning still has some disadvantages, e.g., having to
tune a large number of hyperparameters to the data, lack of calibrated
probabilistic predictions, and a tendency to overfit the training data. In
principle, the Bayesian approach to learning neural networks does not have
these problems. However, existing Bayesian techniques lack scalability to large
dataset and network sizes. In this work we present a novel scalable method for
learning Bayesian neural networks, called probabilistic backpropagation (PBP).
Similar to classical backpropagation, PBP works by computing a forward
propagation of probabilities through the network and then doing a backward
computation of gradients. A series of experiments on ten real-world datasets
show that PBP is significantly faster than other techniques, while offering
competitive predictive abilities. Our experiments also show that PBP provides
accurate estimates of the posterior variance on the network weights.
Factors of Transferability for a Generic ConvNet Representation
Authors: Hossein Azizpour, Ali Sharif Razavian, Josephine Sullivan, Atsuto Maki, Stefan Carlsson
Date: 2014-06-22 00:00:00
Tasks: Dimensionality Reduction, Representation Learning

Evidence is mounting that Convolutional Networks (ConvNets) are the most
effective representation learning method for visual recognition tasks. In the
common scenario, a ConvNet is trained on a large labeled dataset (source) and
the feed-forward units activation of the trained network, at a certain layer of
the network, is used as a generic representation of an input image for a task
with relatively smaller training set (target). Recent studies have shown this
form of representation transfer to be suitable for a wide range of target
visual recognition tasks. This paper introduces and investigates several
factors affecting the transferability of such representations. It includes
parameters for training of the source ConvNet such as its architecture,
distribution of the training data, etc. and also the parameters of feature
extraction such as layer of the trained ConvNet, dimensionality reduction, etc.
Then, by optimizing these factors, we show that significant improvements can be
achieved on various (17) visual recognition tasks. We further show that these
visual recognition tasks can be categorically ordered based on their distance
from the source task such that a correlation between the performance of tasks
and their distance from the source task w.r.t. the proposed factors is
observed.
On the Computability of Solomonoff Induction and Knowledge-Seeking
Authors: Jan Leike, Marcus Hutter
Date: 2015-07-15 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Solomonoff induction is held as a gold standard for learning, but it is known
to be incomputable. We quantify its incomputability by placing various flavors
of Solomonoff's prior M in the arithmetical hierarchy. We also derive
computability bounds for knowledge-seeking agents, and give a limit-computable
weakly asymptotically optimal reinforcement learning agent.
Solomonoff Induction Violates Nicod's Criterion
Authors: Jan Leike, Marcus Hutter
Date: 2015-07-15 00:00:00

Nicod's criterion states that observing a black raven is evidence for the
hypothesis H that all ravens are black. We show that Solomonoff induction does
not satisfy Nicod's criterion: there are time steps in which observing black
ravens decreases the belief in H. Moreover, while observing any computable
infinite string compatible with H, the belief in H decreases infinitely often
when using the unnormalized Solomonoff prior, but only finitely often when
using the normalized Solomonoff prior. We argue that the fault is not with
Solomonoff induction; instead we should reject Nicod's criterion.
Towards Log-Linear Logics with Concrete Domains
Authors: Melisachew Wudage Chekol, Jakob Huber, Heiner Stuckenschmidt
Date: 2015-07-09 00:00:00

We present $\mathcal{MEL}^{++}$ (M denotes Markov logic networks) an
extension of the log-linear description logics $\mathcal{EL}^{++}$-LL with
concrete domains, nominals, and instances. We use Markov logic networks (MLNs)
in order to find the most probable, classified and coherent $\mathcal{EL}^{++}$
ontology from an $\mathcal{MEL}^{++}$ knowledge base. In particular, we develop
a novel way to deal with concrete domains (also known as datatypes) by
extending MLN's cutting plane inference (CPI) algorithm.
Language discrimination and clustering via a neural network approach
Authors: Angelo Mariano, Giorgio Parisi, Saverio Pascazio
Date: 2015-07-15 00:00:00
Tasks: Clustering

We classify twenty-one Indo-European languages starting from written text. We
use neural networks in order to define a distance among different languages,
construct a dendrogram and analyze the ultrametric structure that emerges. Four
or five subgroups of languages are identified, according to the "cut" of the
dendrogram, drawn with an entropic criterion. The results and the method are
discussed.
Evidential relational clustering using medoids
Authors: Kuang Zhou, Arnaud Martin, Quan Pan, Zhun-Ga Liu
Date: 2015-07-15 00:00:00
Tasks: Clustering

In real clustering applications, proximity data, in which only pairwise
similarities or dissimilarities are known, is more general than object data, in
which each pattern is described explicitly by a list of attributes.
Medoid-based clustering algorithms, which assume the prototypes of classes are
objects, are of great value for partitioning relational data sets. In this
paper a new prototype-based clustering method, named Evidential C-Medoids
(ECMdd), which is an extension of Fuzzy C-Medoids (FCMdd) on the theoretical
framework of belief functions is proposed. In ECMdd, medoids are utilized as
the prototypes to represent the detected classes, including specific classes
and imprecise classes. Specific classes are for the data which are distinctly
far from the prototypes of other classes, while imprecise classes accept the
objects that may be close to the prototypes of more than one class. This soft
decision mechanism could make the clustering results more cautious and reduce
the misclassification rates. Experiments in synthetic and real data sets are
used to illustrate the performance of ECMdd. The results show that ECMdd could
capture well the uncertainty in the internal data structure. Moreover, it is
more robust to the initializations compared with FCMdd.