pwc-archive/papers-with-abstracts huggingface dataset:
$\ell_0$ Sparsifying Transform Learning with Efficient Optimal Updates and Convergence Guarantees
Authors: Saiprasad Ravishankar, Yoram Bresler
Date: 2015-01-13 00:00:00
Tasks: Denoising, Image Denoising, Image Reconstruction

Many applications in signal processing benefit from the sparsity of signals
in a certain transform domain or dictionary. Synthesis sparsifying dictionaries
that are directly adapted to data have been popular in applications such as
image denoising, inpainting, and medical image reconstruction. In this work, we
focus instead on the sparsifying transform model, and study the learning of
well-conditioned square sparsifying transforms. The proposed algorithms
alternate between a $\ell_0$ "norm"-based sparse coding step, and a non-convex
transform update step. We derive the exact analytical solution for each of
these steps. The proposed solution for the transform update step achieves the
global minimum in that step, and also provides speedups over iterative
solutions involving conjugate gradients. We establish that our alternating
algorithms are globally convergent to the set of local minimizers of the
non-convex transform learning problems. In practice, the algorithms are
insensitive to initialization. We present results illustrating the promising
performance and significant speed-ups of transform learning over synthesis
K-SVD in image denoising.
SPRITE: A Response Model For Multiple Choice Testing
Authors: Ryan Ning, Andrew E. Waters, Christoph Studer, Richard G. Baraniuk
Date: 2015-01-12 00:00:00
Tasks: model, Multiple-choice

Item response theory (IRT) models for categorical response data are widely
used in the analysis of educational data, computerized adaptive testing, and
psychological surveys. However, most IRT models rely on both the assumption
that categories are strictly ordered and the assumption that this ordering is
known a priori. These assumptions are impractical in many real-world scenarios,
such as multiple-choice exams where the levels of incorrectness for the
distractor categories are often unknown. While a number of results exist on IRT
models for unordered categorical data, they tend to have restrictive modeling
assumptions that lead to poor data fitting performance in practice.
Furthermore, existing unordered categorical models have parameters that are
difficult to interpret. In this work, we propose a novel methodology for
unordered categorical IRT that we call SPRITE (short for stochastic polytomous
response item model) that: (i) analyzes both ordered and unordered categories,
(ii) offers interpretable outputs, and (iii) provides improved data fitting
compared to existing models. We compare SPRITE to existing item response models
and demonstrate its efficacy on both synthetic and real-world educational
datasets.
A Survey on Recent Advances of Computer Vision Algorithms for Egocentric Video
Authors: Sven Bambach
Date: 2015-01-12 00:00:00
Tasks: Action Detection, Activity Detection, Object Recognition, Video Summarization

Recent technological advances have made lightweight, head mounted cameras
both practical and affordable and products like Google Glass show first
approaches to introduce the idea of egocentric (first-person) video to the
mainstream. Interestingly, the computer vision community has only recently
started to explore this new domain of egocentric vision, where research can
roughly be categorized into three areas: Object recognition, activity
detection/recognition, video summarization. In this paper, we try to give a
broad overview about the different problems that have been addressed and
collect and compare evaluation results. Moreover, along with the emergence of
this new domain came the introduction of numerous new and versatile benchmark
datasets, which we summarize and compare as well.
Predicting Performance During Tutoring with Models of Recent Performance
Authors: April Galyardt, Ilya Goldin
Date: 2015-01-12 00:00:00

In educational technology and learning sciences, there are multiple uses for
a predictive model of whether a student will perform a task correctly or not.
For example, an intelligent tutoring system may use such a model to estimate
whether or not a student has mastered a skill. We analyze the significance of
data recency in making such predictions, i.e., asking whether relatively more
recent observations of a student's performance matter more than relatively
older observations. We develop a new Recent-Performance Factors Analysis model
that takes data recency into account. The new model significantly improves
predictive accuracy over both existing logistic-regression performance models
and over novel baseline models in evaluations on real-world and synthetic
datasets. As a secondary contribution, we demonstrate how the widely used
cross-validation with 0-1 loss is inferior to AIC and to cross-validation with
L1 prediction error loss as a measure of model performance.
Max-Cost Discrete Function Evaluation Problem under a Budget
Authors: Feng Nan, Joseph Wang, Venkatesh Saligrama
Date: 2015-01-12 00:00:00
Tasks: General Classification

We propose novel methods for max-cost Discrete Function Evaluation Problem
(DFEP) under budget constraints. We are motivated by applications such as
clinical diagnosis where a patient is subjected to a sequence of (possibly
expensive) tests before a decision is made. Our goal is to develop strategies
for minimizing max-costs. The problem is known to be NP hard and greedy methods
based on specialized impurity functions have been proposed. We develop a broad
class of \emph{admissible} impurity functions that admit monomials, classes of
polynomials, and hinge-loss functions that allow for flexible impurity design
with provably optimal approximation bounds. This flexibility is important for
datasets when max-cost can be overly sensitive to "outliers." Outliers bias
max-cost to a few examples that require a large number of tests for
classification. We design admissible functions that allow for accuracy-cost
trade-off and result in $O(\log n)$ guarantees of the optimal cost among trees
with corresponding classification accuracy levels.
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning
Authors: Aurélien Bellet, YIngyu Liang, Alireza Bagheri Garakani, Maria-Florina Balcan, Fei Sha
Date: 2014-04-09 00:00:00
Tasks: Sparse Learning

Learning sparse combinations is a frequent theme in machine learning. In this
paper, we study its associated optimization problem in the distributed setting
where the elements to be combined are not centrally located but spread over a
network. We address the key challenges of balancing communication costs and
optimization errors. To this end, we propose a distributed Frank-Wolfe (dFW)
algorithm. We obtain theoretical guarantees on the optimization error
$\epsilon$ and communication cost that do not depend on the total number of
combining elements. We further show that the communication cost of dFW is
optimal by deriving a lower-bound on the communication cost required to
construct an $\epsilon$-approximate solution. We validate our theoretical
analysis with empirical studies on synthetic and real-world data, which
demonstrate that dFW outperforms both baselines and competing methods. We also
study the performance of dFW when the conditions of our analysis are relaxed,
and show that dFW is fairly robust.
Navigating the Semantic Horizon using Relative Neighborhood Graphs
Authors: Amaru Cuba Gyllensten, Magnus Sahlgren
Date: 2015-01-12 00:00:00
Proceeding: EMNLP 2015 9
Tasks: Word Sense Induction

This paper is concerned with nearest neighbor search in distributional
semantic models. A normal nearest neighbor search only returns a ranked list of
neighbors, with no information about the structure or topology of the local
neighborhood. This is a potentially serious shortcoming of the mode of querying
a distributional semantic model, since a ranked list of neighbors may conflate
several different senses. We argue that the topology of neighborhoods in
semantic space provides important information about the different senses of
terms, and that such topological structures can be used for word-sense
induction. We also argue that the topology of the neighborhoods in semantic
space can be used to determine the semantic horizon of a point, which we define
as the set of neighbors that have a direct connection to the point. We
introduce relative neighborhood graphs as method to uncover the topological
properties of neighborhoods in semantic models. We also provide examples of
relative neighborhood graphs for three well-known semantic models; the PMI
model, the GloVe model, and the skipgram model.
Efficient Online Relative Comparison Kernel Learning
Authors: Eric Heim, Matthew Berger, Lee M. Seversky, Milos Hauskrecht
Date: 2015-01-06 00:00:00
Tasks: Collaborative Filtering, Retrieval

Learning a kernel matrix from relative comparison human feedback is an
important problem with applications in collaborative filtering, object
retrieval, and search. For learning a kernel over a large number of objects,
existing methods face significant scalability issues inhibiting the application
of these methods to settings where a kernel is learned in an online and timely
fashion. In this paper we propose a novel framework called Efficient online
Relative comparison Kernel LEarning (ERKLE), for efficiently learning the
similarity of a large set of objects in an online manner. We learn a kernel
from relative comparisons via stochastic gradient descent, one query response
at a time, by taking advantage of the sparse and low-rank properties of the
gradient to efficiently restrict the kernel to lie in the space of positive
semidefinite matrices. In addition, we derive a passive-aggressive online
update for minimally satisfying new relative comparisons as to not disrupt the
influence of previously obtained comparisons. Experimentally, we demonstrate a
considerable improvement in speed while obtaining improved or comparable
accuracy compared to current methods in the online learning setting.
Photonic Delay Systems as Machine Learning Implementations
Authors: Michiel Hermans, Miguel Soriano, Joni Dambre, Peter Bienstman, Ingo Fischer
Date: 2015-01-12 00:00:00
Tasks: BIG-bench Machine Learning

Nonlinear photonic delay systems present interesting implementation platforms
for machine learning models. They can be extremely fast, offer great degrees of
parallelism and potentially consume far less power than digital processors. So
far they have been successfully employed for signal processing using the
Reservoir Computing paradigm. In this paper we show that their range of
applicability can be greatly extended if we use gradient descent with
backpropagation through time on a model of the system to optimize the input
encoding of such systems. We perform physical experiments that demonstrate that
the obtained input encodings work well in reality, and we show that optimized
systems perform significantly better than the common Reservoir Computing
approach. The results presented here demonstrate that common gradient descent
techniques from machine learning may well be applicable on physical
neuro-inspired analog computers.
Combined modeling of sparse and dense noise for improvement of Relevance Vector Machine
Authors: Martin Sundin, Saikat Chatterjee, Magnus Jansson
Date: 2015-01-12 00:00:00
Tasks: Denoising, Image Denoising

Using a Bayesian approach, we consider the problem of recovering sparse
signals under additive sparse and dense noise. Typically, sparse noise models
outliers, impulse bursts or data loss. To handle sparse noise, existing methods
simultaneously estimate the sparse signal of interest and the sparse noise of
no interest. For estimating the sparse signal, without the need of estimating
the sparse noise, we construct a robust Relevance Vector Machine (RVM). In the
RVM, sparse noise and ever present dense noise are treated through a combined
noise model. The precision of combined noise is modeled by a diagonal matrix.
We show that the new RVM update equations correspond to a non-symmetric
sparsity inducing cost function. Further, the combined modeling is found to be
computationally more efficient. We also extend the method to block-sparse
signals and noise with known and unknown block structures. Through simulations,
we show the performance and computation efficiency of the new RVM in several
applications: recovery of sparse and block sparse signals, housing price
prediction and image denoising.
Belief Hierarchical Clustering
Authors: Wiem Maalel, Kuang Zhou, Arnaud Martin, Zied Elouedi
Date: 2015-01-12 00:00:00
Tasks: Clustering

In the data mining field many clustering methods have been proposed, yet
standard versions do not take into account uncertain databases. This paper
deals with a new approach to cluster uncertain data by using a hierarchical
clustering defined within the belief function framework. The main objective of
the belief hierarchical clustering is to allow an object to belong to one or
several clusters. To each belonging, a degree of belief is associated, and
clusters are combined based on the pignistic properties. Experiments with real
uncertain data show that our proposed method can be considered as a propitious
tool.
Learning Deep Temporal Representations for Brain Decoding
Authors: Orhan Firat, Emre Aksan, Ilke Oztekin, Fatos T. Yarman Vural
Date: 2014-12-23 00:00:00
Tasks: Brain Decoding, General Classification

Functional magnetic resonance imaging produces high dimensional data, with a
less then ideal number of labelled samples for brain decoding tasks (predicting
brain states). In this study, we propose a new deep temporal convolutional
neural network architecture with spatial pooling for brain decoding which aims
to reduce dimensionality of feature space along with improved classification
performance. Temporal representations (filters) for each layer of the
convolutional model are learned by leveraging unlabelled fMRI data in an
unsupervised fashion with regularized autoencoders. Learned temporal
representations in multiple levels capture the regularities in the temporal
domain and are observed to be a rich bank of activation patterns which also
exhibit similarities to the actual hemodynamic responses. Further, spatial
pooling layers in the convolutional architecture reduce the dimensionality
without losing excessive information. By employing the proposed temporal
convolutional architecture with spatial pooling, raw input fMRI data is mapped
to a non-linear, highly-expressive and low-dimensional feature space where the
final classification is conducted. In addition, we propose a simple heuristic
approach for hyper-parameter tuning when no validation data is available.
Proposed method is tested on a ten class recognition memory experiment with
nine subjects. The results support the efficiency and potential of the proposed
model, compared to the baseline multi-voxel pattern analysis techniques.
A Dataset for Movie Description
Authors: Anna Rohrbach, Marcus Rohrbach, Niket Tandon, Bernt Schiele
Date: 2015-01-12 00:00:00
Proceeding: CVPR 2015 6
Tasks: Benchmarking, Descriptive

Descriptive video service (DVS) provides linguistic descriptions of movies
and allows visually impaired people to follow a movie along with their peers.
Such descriptions are by design mainly visual and thus naturally form an
interesting data source for computer vision and computational linguistics. In
this work we propose a novel dataset which contains transcribed DVS, which is
temporally aligned to full length HD movies. In addition we also collected the
aligned movie scripts which have been used in prior work and compare the two
different sources of descriptions. In total the Movie Description dataset
contains a parallel corpus of over 54,000 sentences and video snippets from 72
HD movies. We characterize the dataset by benchmarking different approaches for
generating video descriptions. Comparing DVS to scripts, we find that DVS is
far more visual and describes precisely what is shown rather than what should
happen according to the scripts created prior to movie production.
Autodetection and Classification of Hidden Cultural City Districts from Yelp Reviews
Authors: Harini Suresh, Nicholas Locascio
Date: 2015-01-12 00:00:00
Tasks: Clustering, General Classification, Topic Models

Topic models are a way to discover underlying themes in an otherwise
unstructured collection of documents. In this study, we specifically used the
Latent Dirichlet Allocation (LDA) topic model on a dataset of Yelp reviews to
classify restaurants based off of their reviews. Furthermore, we hypothesize
that within a city, restaurants can be grouped into similar "clusters" based on
both location and similarity. We used several different clustering methods,
including K-means Clustering and a Probabilistic Mixture Model, in order to
uncover and classify districts, both well-known and hidden (i.e. cultural areas
like Chinatown or hearsay like "the best street for Italian restaurants")
within a city. We use these models to display and label different clusters on a
map. We also introduce a topic similarity heatmap that displays the similarity
distribution in a city to a new restaurant.
Learning the Conditional Independence Structure of Stationary Time Series: A Multitask Learning Approach
Authors: Alexander Jung
Date: 2014-04-04 00:00:00
Tasks: Time Series, Time Series Analysis

We propose a method for inferring the conditional independence graph (CIG) of
a high-dimensional Gaussian vector time series (discrete-time process) from a
finite-length observation. By contrast to existing approaches, we do not rely
on a parametric process model (such as, e.g., an autoregressive model) for the
observed random process. Instead, we only require certain smoothness properties
(in the Fourier domain) of the process. The proposed inference scheme works
even for sample sizes much smaller than the number of scalar process components
if the true underlying CIG is sufficiently sparse. A theoretical performance
analysis provides conditions which guarantee that the probability of the
proposed inference method to deliver a wrong CIG is below a prescribed value.
These conditions imply lower bounds on the sample size such that the new method
is consistent asymptotically. Some numerical experiments validate our
theoretical performance analysis and demonstrate superior performance of our
scheme compared to an existing (parametric) approach in case of model mismatch.
Identifiability and optimal rates of convergence for parameters of multiple types in finite mixtures
Authors: Nhat Ho, XuanLong Nguyen
Date: 2015-01-11 00:00:00
Tasks: parameter estimation

This paper studies identifiability and convergence behaviors for parameters
of multiple types in finite mixtures, and the effects of model fitting with
extra mixing components. First, we present a general theory for strong
identifiability, which extends from the previous work of Nguyen [2013] and Chen
[1995] to address a broad range of mixture models and to handle matrix-variate
parameters. These models are shown to share the same Wasserstein distance based
optimal rates of convergence for the space of mixing distributions ---
$n^{-1/2}$ under $W_1$ for the exact-fitted and $n^{-1/4}$ under $W_2$ for the
over-fitted setting, where $n$ is the sample size. This theory, however, is not
applicable to several important model classes, including location-scale
multivariate Gaussian mixtures, shape-scale Gamma mixtures and
location-scale-shape skew-normal mixtures. The second part of this work is
devoted to demonstrating that for these "weakly identifiable" classes,
algebraic structures of the density family play a fundamental role in
determining convergence rates of the model parameters, which display a very
rich spectrum of behaviors. For instance, the optimal rate of parameter
estimation in an over-fitted location-covariance Gaussian mixture is precisely
determined by the order of a solvable system of polynomial equations --- these
rates deteriorate rapidly as more extra components are added to the model. The
established rates for a variety of settings are illustrated by a simulation
study.
Crowd-ML: A Privacy-Preserving Learning Framework for a Crowd of Smart Devices
Authors: Jihun Hamm, Adam Champion, Guoxing Chen, Mikhail Belkin, Dong Xuan
Date: 2015-01-11 00:00:00
Tasks: Privacy Preserving

Smart devices with built-in sensors, computational capabilities, and network
connectivity have become increasingly pervasive. The crowds of smart devices
offer opportunities to collectively sense and perform computing tasks in an
unprecedented scale. This paper presents Crowd-ML, a privacy-preserving machine
learning framework for a crowd of smart devices, which can solve a wide range
of learning problems for crowdsensing data with differential privacy
guarantees. Crowd-ML endows a crowdsensing system with an ability to learn
classifiers or predictors online from crowdsensing data privately with minimal
computational overheads on devices and servers, suitable for a practical and
large-scale employment of the framework. We analyze the performance and the
scalability of Crowd-ML, and implement the system with off-the-shelf
smartphones as a proof of concept. We demonstrate the advantages of Crowd-ML
with real and simulated experiments under various conditions.
Semi-supervised Feature Analysis by Mining Correlations among Multiple Tasks
Authors: Xiaojun Chang, Yi Yang
Date: 2014-11-23 00:00:00
Tasks: feature selection

In this paper, we propose a novel semi-supervised feature selection framework
by mining correlations among multiple tasks and apply it to different
multimedia applications. Instead of independently computing the importance of
features for each task, our algorithm leverages shared knowledge from multiple
related tasks, thus, improving the performance of feature selection. Note that
we build our algorithm on assumption that different tasks share common
structures. The proposed algorithm selects features in a batch mode, by which
the correlations between different features are taken into consideration.
Besides, considering the fact that labeling a large amount of training data in
real world is both time-consuming and tedious, we adopt manifold learning which
exploits both labeled and unlabeled training data for feature space analysis.
Since the objective function is non-smooth and difficult to solve, we propose
an iterative algorithm with fast convergence. Extensive experiments on
different applications demonstrate that our algorithm outperforms other
state-of-the-art feature selection algorithms.
Online Handwritten Devanagari Stroke Recognition Using Extended Directional Features
Authors: Lajish VL, Sunil Kumar Kopparapu
Date: 2015-01-11 00:00:00
Tasks: Phoneme Recognition

This paper describes a new feature set, called the extended directional
features (EDF) for use in the recognition of online handwritten strokes. We use
EDF specifically to recognize strokes that form a basis for producing
Devanagari script, which is the most widely used Indian language script. It
should be noted that stroke recognition in handwritten script is equivalent to
phoneme recognition in speech signals and is generally very poor and of the
order of 20% for singing voice. Experiments are conducted for the automatic
recognition of isolated handwritten strokes. Initially we describe the proposed
feature set, namely EDF and then show how this feature can be effectively
utilized for writer independent script recognition through stroke recognition.
Experimental results show that the extended directional feature set performs
well with about 65+% stroke level recognition accuracy for writer independent
data set.