pwc-archive/papers-with-abstracts huggingface dataset:
Asymptotic Behavior of Mean Partitions in Consensus Clustering
Authors: Brijnesh Jain
Date: 2015-12-18 00:00:00
Tasks: Clustering

Although consistency is a minimum requirement of any estimator, little is
known about consistency of the mean partition approach in consensus clustering.
This contribution studies the asymptotic behavior of mean partitions. We show
that under normal assumptions, the mean partition approach is consistent and
asymptotic normal. To derive both results, we represent partitions as points of
some geometric space, called orbit space. Then we draw on results from the
theory of Fr\'echet means and stochastic programming. The asymptotic properties
hold for continuous extensions of standard cluster criteria (indices). The
results justify consensus clustering using finite but sufficiently large sample
sizes. Furthermore, the orbit space framework provides a mathematical
foundation for studying further statistical, geometrical, and analytical
properties of sets of partitions.
Ontology-driven Information Extraction
Authors: Weronika T. Adrian, Nicola Leone, Marco Manna
Date: 2015-12-18 00:00:00
Tasks: Table Recognition, text annotation

Homogeneous unstructured data (HUD) are collections of unstructured documents
that share common properties, such as similar layout, common file format, or
common domain of values. Building on such properties, it would be desirable to
automatically process HUD to access the main information through a semantic
layer -- typically an ontology -- called semantic view. Hence, we propose an
ontology-based approach for extracting semantically rich information from HUD,
by integrating and extending recent technologies and results from the fields of
classical information extraction, table recognition, ontologies, text
annotation, and logic programming. Moreover, we design and implement a system,
named KnowRex, that has been successfully applied to curriculum vitae in the
Europass style to offer a semantic view of them, and be able, for example, to
select those which exhibit required skills.
High dimensional errors-in-variables models with dependent measurements
Authors: Mark Rudelson, Shuheng Zhou
Date: 2015-02-09 00:00:00
Tasks: Vocal Bursts Intensity Prediction

Suppose that we observe $y \in \mathbb{R}^f$ and $X \in \mathbb{R}^{f \times
m}$ in the following errors-in-variables model: \begin{eqnarray*} y & = & X_0
\beta^* + \epsilon \\ X & = & X_0 + W \end{eqnarray*} where $X_0$ is a $f
\times m$ design matrix with independent subgaussian row vectors, $\epsilon \in
\mathbb{R}^f$ is a noise vector and $W$ is a mean zero $f \times m$ random
noise matrix with independent subgaussian column vectors, independent of $X_0$
and $\epsilon$. This model is significantly different from those analyzed in
the literature in the sense that we allow the measurement error for each
covariate to be a dependent vector across its $f$ observations. Such error
structures appear in the science literature when modeling the trial-to-trial
fluctuations in response strength shared across a set of neurons.
  Under sparsity and restrictive eigenvalue type of conditions, we show that
one is able to recover a sparse vector $\beta^* \in \mathbb{R}^m$ from the
model given a single observation matrix $X$ and the response vector $y$. We
establish consistency in estimating $\beta^*$ and obtain the rates of
convergence in the $\ell_q$ norm, where $q = 1, 2$ for the Lasso-type
estimator, and for $q \in [1, 2]$ for a Dantzig-type conic programming
estimator. We show error bounds which approach that of the regular Lasso and
the Dantzig selector in case the errors in $W$ are tending to 0.
Face Hallucination using Linear Models of Coupled Sparse Support
Authors: Reuben Farrugia, Christine Guillemot
Date: 2015-12-18 00:00:00
Tasks: Face Hallucination, Hallucination, Super-Resolution

Most face super-resolution methods assume that low-resolution and
high-resolution manifolds have similar local geometrical structure, hence learn
local models on the lowresolution manifolds (e.g. sparse or locally linear
embedding models), which are then applied on the high-resolution manifold.
However, the low-resolution manifold is distorted by the oneto-many
relationship between low- and high- resolution patches. This paper presents a
method which learns linear models based on the local geometrical structure on
the high-resolution manifold rather than on the low-resolution manifold. For
this, in a first step, the low-resolution patch is used to derive a globally
optimal estimate of the high-resolution patch. The approximated solution is
shown to be close in Euclidean space to the ground-truth but is generally
smooth and lacks the texture details needed by state-ofthe-art face
recognizers. This first estimate allows us to find the support of the
high-resolution manifold using sparse coding (SC), which are then used as
support for learning a local projection (or upscaling) model between the
low-resolution and the highresolution manifolds using Multivariate Ridge
Regression (MRR). Experimental results show that the proposed method
outperforms six face super-resolution methods in terms of both recognition and
quality. These results also reveal that the recognition and quality are
significantly affected by the method used for stitching all super-resolved
patches together, where quilting was found to better preserve the texture
details which helps to achieve higher recognition rates.
Deformable Distributed Multiple Detector Fusion for Multi-Person Tracking
Authors: Andy J. Ma, Pong C. Yuen, Suchi Saria
Date: 2015-12-18 00:00:00

This paper addresses fully automated multi-person tracking in complex
environments with challenging occlusion and extensive pose variations. Our
solution combines multiple detectors for a set of different regions of interest
(e.g., full-body and head) for multi-person tracking. The use of multiple
detectors leads to fewer miss detections as it is able to exploit the
complementary strengths of the individual detectors. While the number of false
positives may increase with the increased number of bounding boxes detected
from multiple detectors, we propose to group the detection outputs by bounding
box location and depth information. For robustness to significant pose
variations, deformable spatial relationship between detectors are learnt in our
multi-person tracking system. On RGBD data from a live Intensive Care Unit
(ICU), we show that the proposed method significantly improves multi-person
tracking performance over state-of-the-art methods.
Can Pretrained Neural Networks Detect Anatomy?
Authors: Vlado Menkovski, Zharko Aleksovski, Axel Saalbach, Hannes Nickisch
Date: 2015-12-18 00:00:00
Tasks: Anatomy, speech-recognition, Speech Recognition

Convolutional neural networks demonstrated outstanding empirical results in
computer vision and speech recognition tasks where labeled training data is
abundant. In medical imaging, there is a huge variety of possible imaging
modalities and contrasts, where annotated data is usually very scarce. We
present two approaches to deal with this challenge. A network pretrained in a
different domain with abundant data is used as a feature extractor, while a
subsequent classifier is trained on a small target dataset; and a deep
architecture trained with heavy augmentation and equipped with sophisticated
regularization methods. We test the approaches on a corpus of X-ray images to
design an anatomy detection system.
Complexity and Approximation of the Fuzzy K-Means Problem
Authors: Johannes Blömer, Sascha Brauer, Kathrin Bujna
Date: 2015-12-18 00:00:00
Tasks: Clustering

The fuzzy $K$-means problem is a generalization of the classical $K$-means
problem to soft clusterings, i.e. clusterings where each points belongs to each
cluster to some degree. Although popular in practice, prior to this work the
fuzzy $K$-means problem has not been studied from a complexity theoretic or
algorithmic perspective. We show that optimal solutions for fuzzy $K$-means
cannot, in general, be expressed by radicals over the input points.
Surprisingly, this already holds for very simple inputs in one-dimensional
space. Hence, one cannot expect to compute optimal solutions exactly. We give
the first $(1+\epsilon)$-approximation algorithms for the fuzzy $K$-means
problem. First, we present a deterministic approximation algorithm whose
runtime is polynomial in $N$ and linear in the dimension $D$ of the input set,
given that $K$ is constant, i.e. a polynomial time approximation algorithm
given a fixed $K$. We achieve this result by showing that for each soft
clustering there exists a hard clustering with comparable properties. Second,
by using techniques known from coreset constructions for the $K$-means problem,
we develop a deterministic approximation algorithm that runs in time almost
linear in $N$ but exponential in the dimension $D$. We complement these results
with a randomized algorithm which imposes some natural restrictions on the
input set and whose runtime is comparable to some of the most efficient
approximation algorithms for $K$-means, i.e. linear in the number of points and
the dimension, but exponential in the number of clusters.
Decentralized Joint-Sparse Signal Recovery: A Sparse Bayesian Learning Approach
Authors: Saurabh Khanna, Chandra R. Murthy
Date: 2015-07-09 00:00:00

This work proposes a decentralized, iterative, Bayesian algorithm called
CB-DSBL for in-network estimation of multiple jointly sparse vectors by a
network of nodes, using noisy and underdetermined linear measurements. The
proposed algorithm exploits the network wide joint sparsity of the un- known
sparse vectors to recover them from significantly fewer number of local
measurements compared to standalone sparse signal recovery schemes. To reduce
the amount of inter-node communication and the associated overheads, the nodes
exchange messages with only a small subset of their single hop neighbors. Under
this communication scheme, we separately analyze the convergence of the
underlying Alternating Directions Method of Multipliers (ADMM) iterations used
in our proposed algorithm and establish its linear convergence rate. The
findings from the convergence analysis of decentralized ADMM are used to
accelerate the convergence of the proposed CB-DSBL algorithm. Using Monte Carlo
simulations, we demonstrate the superior signal reconstruction as well as
support recovery performance of our proposed algorithm compared to existing
decentralized algorithms: DRL-1, DCOMP and DCSP.
Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls
Authors: Konstantin Avrachenkov, Bruno Ribeiro, Jithin K. Sreedharan
Date: 2015-10-19 00:00:00
Tasks: Bayesian Inference

Online social networks (OSN) contain extensive amount of information about
the underlying society that is yet to be explored. One of the most feasible
technique to fetch information from OSN, crawling through Application
Programming Interface (API) requests, poses serious concerns over the the
guarantees of the estimates. In this work, we focus on making reliable
statistical inference with limited API crawls. Based on regenerative properties
of the random walks, we propose an unbiased estimator for the aggregated sum of
functions over edges and proved the connection between variance of the
estimator and spectral gap. In order to facilitate Bayesian inference on the
true value of the estimator, we derive the approximate posterior distribution
of the estimate. Later the proposed ideas are validated with numerical
experiments on inference problems in real-world networks.
On Voting and Facility Location
Authors: Michal Feldman, Amos Fiat, Iddan Golomb
Date: 2015-12-18 00:00:00

We study mechanisms for candidate selection that seek to minimize the social
cost, where voters and candidates are associated with points in some underlying
metric space. The social cost of a candidate is the sum of its distances to
each voter. Some of our work assumes that these points can be modeled on a real
line, but other results of ours are more general.
  A question closely related to candidate selection is that of minimizing the
sum of distances for facility location. The difference is that in our setting
there is a fixed set of candidates, whereas the large body of work on facility
location seems to consider every point in the metric space to be a possible
candidate. This gives rise to three types of mechanisms which differ in the
granularity of their input space (voting, ranking and location mechanisms). We
study the relationships between these three classes of mechanisms.
  While it may seem that Black's 1948 median algorithm is optimal for candidate
selection on the line, this is not the case. We give matching upper and lower
bounds for a variety of settings. In particular, when candidates and voters are
on the line, our universally truthful spike mechanism gives a [tight]
approximation of two. When assessing candidate selection mechanisms, we seek
several desirable properties: (a) efficiency (minimizing the social cost) (b)
truthfulness (dominant strategy incentive compatibility) and (c) simplicity (a
smaller input space). We quantify the effect that truthfulness and simplicity
impose on the efficiency.
Experimental robustness of Fourier Ptychography phase retrieval algorithms
Authors: Li-Hao Yeh, Jonathan Dong, Jingshan Zhong, Lei Tian, Michael Chen, Gongguo Tang, Mahdi Soltanolkotabi, Laura Waller
Date: 2015-11-10 00:00:00
Tasks: Retrieval

Fourier ptychography is a new computational microscopy technique that
provides gigapixel-scale intensity and phase images with both wide
field-of-view and high resolution. By capturing a stack of low-resolution
images under different illumination angles, a nonlinear inverse algorithm can
be used to computationally reconstruct the high-resolution complex field. Here,
we compare and classify multiple proposed inverse algorithms in terms of
experimental robustness. We find that the main sources of error are noise,
aberrations and mis-calibration (i.e. model mis-match). Using simulations and
experiments, we demonstrate that the choice of cost function plays a critical
role, with amplitude-based cost functions performing better than
intensity-based ones. The reason for this is that Fourier ptychography datasets
consist of images from both brightfield and darkfield illumination,
representing a large range of measured intensities. Both noise (e.g. Poisson
noise) and model mis-match errors are shown to scale with intensity. Hence,
algorithms that use an appropriate cost function will be more tolerant to both
noise and model mis-match. Given these insights, we propose a global Newton's
method algorithm which is robust and computationally efficient. Finally, we
discuss the impact of procedures for algorithmic correction of aberrations and
mis-calibration.
Necessary and Sufficient Conditions for Surrogate Functions of Pareto Frontiers and Their Synthesis Using Gaussian Processes
Authors: Conrado Silva Miranda, Fernando José Von Zuben
Date: 2015-05-19 00:00:00
Tasks: Gaussian Processes, valid

This paper introduces the necessary and sufficient conditions that surrogate
functions must satisfy to properly define frontiers of non-dominated solutions
in multi-objective optimization problems. These new conditions work directly on
the objective space, thus being agnostic about how the solutions are evaluated.
Therefore, real objectives or user-designed objectives' surrogates are allowed,
opening the possibility of linking independent objective surrogates. To
illustrate the practical consequences of adopting the proposed conditions, we
use Gaussian processes as surrogates endowed with monotonicity soft constraints
and with an adjustable degree of flexibility, and compare them to regular
Gaussian processes and to a frontier surrogate method in the literature that is
the closest to the method proposed in this paper. Results show that the
necessary and sufficient conditions proposed here are finely managed by the
constrained Gaussian process, guiding to high-quality surrogates capable of
suitably synthesizing an approximation to the Pareto frontier in challenging
instances of multi-objective optimization, while an existing approach that does
not take the theory proposed in consideration defines surrogates which greatly
violate the conditions to describe a valid frontier.
Modeling Progress in AI
Authors: Miles Brundage
Date: 2015-12-18 00:00:00

Participants in recent discussions of AI-related issues ranging from
intelligence explosion to technological unemployment have made diverse claims
about the nature, pace, and drivers of progress in AI. However, these theories
are rarely specified in enough detail to enable systematic evaluation of their
assumptions or to extrapolate progress quantitatively, as is often done with
some success in other technological domains. After reviewing relevant
literatures and justifying the need for more rigorous modeling of AI progress,
this paper contributes to that research program by suggesting ways to account
for the relationship between hardware speed increases and algorithmic
improvements in AI, the role of human inputs in enabling AI capabilities, and
the relationships between different sub-fields of AI. It then outlines ways of
tailoring AI progress models to generate insights on the specific issue of
technological unemployment, and outlines future directions for research on AI
progress.
Domain Adaptation and Transfer Learning in StochasticNets
Authors: Mohammad Javad Shafiee, Parthipan Siva, Paul Fieguth, Alexander Wong
Date: 2015-12-18 00:00:00
Tasks: BIG-bench Machine Learning, Domain Adaptation, Transfer Learning

Transfer learning is a recent field of machine learning research that aims to
resolve the challenge of dealing with insufficient training data in the domain
of interest. This is a particular issue with traditional deep neural networks
where a large amount of training data is needed. Recently, StochasticNets was
proposed to take advantage of sparse connectivity in order to decrease the
number of parameters that needs to be learned, which in turn may relax training
data size requirements. In this paper, we study the efficacy of transfer
learning on StochasticNet frameworks. Experimental results show ~7% improvement
on StochasticNet performance when the transfer learning is applied in training
step.
Scene-adaptive Coded Apertures Imaging
Authors: Xuehui Wang, Jinli Suo, Jingyi Yu, Yongdong Zhang, Qionghai Dai
Date: 2015-06-19 00:00:00

Coded aperture imaging systems have recently shown great success in
recovering scene depth and extending the depth-of-field. The ideal pattern,
however, would have to serve two conflicting purposes: 1) be broadband to
ensure robust deconvolution and 2) has sufficient zero-crossings for a high
depth discrepancy. This paper presents a simple but effective scene-adaptive
coded aperture solution to bridge this gap. We observe that the geometric
structures in a natural scene often exhibit only a few edge directions, and the
successive frames are closely correlated. Therefore we adopt a spatial
partitioning and temporal propagation scheme. In each frame, we address one
principal direction by applying depth-discriminative codes along it and
broadband codes along its orthogonal direction. Since within a frame only the
regions with edge direction corresponding to its aperture code behaves well, we
utilize the close among-frame correlation to propagate the high quality single
frame results temporally to obtain high performance over the whole image
lattice. To physically implement this scheme, we use a Liquid Crystal on
Silicon (LCoS) microdisplay that permits fast changing pattern codes. Firstly,
we capture the scene with a pinhole and analyze the scene content to determine
primary edge orientations. Secondly, we sequentially apply the proposed coding
scheme with these orientations in the following frames. Experiments on both
synthetic and real scenes show that our technique is able to combine advantages
of the state-of-the-art patterns for recovering better quality depth map and
all-focus images.
Monocular Object Instance Segmentation and Depth Ordering with CNNs
Authors: Ziyu Zhang, Alexander G. Schwing, Sanja Fidler, Raquel Urtasun
Date: 2015-05-12 00:00:00
Proceeding: ICCV 2015 12
Tasks: Instance Segmentation, Object, Segmentation, Semantic Segmentation

In this paper we tackle the problem of instance-level segmentation and depth
ordering from a single monocular image. Towards this goal, we take advantage of
convolutional neural nets and train them to directly predict instance-level
segmentations where the instance ID encodes the depth ordering within image
patches. To provide a coherent single explanation of an image we develop a
Markov random field which takes as input the predictions of convolutional
neural nets applied at overlapping patches of different resolutions, as well as
the output of a connected component algorithm. It aims to predict accurate
instance-level segmentation and depth ordering. We demonstrate the
effectiveness of our approach on the challenging KITTI benchmark and show good
performance on both tasks.
Learning the Preferences of Ignorant, Inconsistent Agents
Authors: Owain Evans, Andreas Stuhlmueller, Noah D. Goodman
Date: 2015-12-18 00:00:00
Tasks: Decision Making

An important use of machine learning is to learn what people value. What
posts or photos should a user be shown? Which jobs or activities would a person
find rewarding? In each case, observations of people's past choices can inform
our inferences about their likes and preferences. If we assume that choices are
approximately optimal according to some utility function, we can treat
preference inference as Bayesian inverse planning. That is, given a prior on
utility functions and some observed choices, we invert an optimal
decision-making process to infer a posterior distribution on utility functions.
However, people often deviate from approximate optimality. They have false
beliefs, their planning is sub-optimal, and their choices may be temporally
inconsistent due to hyperbolic discounting and other biases. We demonstrate how
to incorporate these deviations into algorithms for preference inference by
constructing generative models of planning for agents who are subject to false
beliefs and time inconsistency. We explore the inferences these models make
about preferences, beliefs, and biases. We present a behavioral experiment in
which human subjects perform preference inference given the same observations
of choices as our model. Results show that human subjects (like our model)
explain choices in terms of systematic deviations from optimal behavior and
suggest that they take such deviations into account when inferring preferences.