pwc-archive/papers-with-abstracts huggingface dataset:
What Players do with the Ball: A Physically Constrained Interaction Modeling
Authors: Andrii Maksai, Xinchao Wang, Pascal Fua
Date: 2015-11-19 00:00:00
Proceeding: CVPR 2016 6

Tracking the ball is critical for video-based analysis of team sports.
However, it is difficult, especially in low-resolution images, due to the small
size of the ball, its speed that creates motion blur, and its often being
occluded by players. In this paper, we propose a generic and principled
approach to modeling the interaction between the ball and the players while
also imposing appropriate physical constraints on the ball's trajectory. We
show that our approach, formulated in terms of a Mixed Integer Program, is more
robust and more accurate than several state-of-the-art approaches on real-life
volleyball, basketball, and soccer sequences.
Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization
Authors: Adish Singla, Sebastian Tschiatschek, Andreas Krause
Date: 2015-11-23 00:00:00
Tasks: Diversity

We address the problem of maximizing an unknown submodular function that can
only be accessed via noisy evaluations. Our work is motivated by the task of
summarizing content, e.g., image collections, by leveraging users' feedback in
form of clicks or ratings. For summarization tasks with the goal of maximizing
coverage and diversity, submodular set functions are a natural choice. When the
underlying submodular function is unknown, users' feedback can provide noisy
evaluations of the function that we seek to maximize. We provide a generic
algorithm -- \submM{} -- for maximizing an unknown submodular function under
cardinality constraints. This algorithm makes use of a novel exploration module
-- \blbox{} -- that proposes good elements based on adaptively sampling noisy
function evaluations. \blbox{} is able to accommodate different kinds of
observation models such as value queries and pairwise comparisons. We provide
PAC-style guarantees on the quality and sampling cost of the solution obtained
by \submM{}. We demonstrate the effectiveness of our approach in an
interactive, crowdsourced image collection summarization application.
Positive Neural Networks in Discrete Time Implement Monotone-Regular Behaviors
Authors: Tom J. Ameloot, Jan Van den Bussche
Date: 2015-02-21 00:00:00

We study the expressive power of positive neural networks. The model uses
positive connection weights and multiple input neurons. Different behaviors can
be expressed by varying the connection weights. We show that in discrete time,
and in absence of noise, the class of positive neural networks captures the
so-called monotone-regular behaviors, that are based on regular languages. A
finer picture emerges if one takes into account the delay by which a
monotone-regular behavior is implemented. Each monotone-regular behavior can be
implemented by a positive neural network with a delay of one time unit. Some
monotone-regular behaviors can be implemented with zero delay. And,
interestingly, some simple monotone-regular behaviors can not be implemented
with zero delay.
Analyzing Classifiers: Fisher Vectors and Deep Neural Networks
Authors: Sebastian Bach, Alexander Binder, Grégoire Montavon, Klaus-Robert Müller, Wojciech Samek
Date: 2015-12-01 00:00:00
Proceeding: CVPR 2016 6
Tasks: Classification, General Classification, image-classification, Image Classification

Fisher Vector classifiers and Deep Neural Networks (DNNs) are popular and
successful algorithms for solving image classification problems. However, both
are generally considered `black box' predictors as the non-linear
transformations involved have so far prevented transparent and interpretable
reasoning. Recently, a principled technique, Layer-wise Relevance Propagation
(LRP), has been developed in order to better comprehend the inherent structured
reasoning of complex nonlinear classification models such as Bag of Feature
models or DNNs. In this paper we (1) extend the LRP framework also for Fisher
Vector classifiers and then use it as analysis tool to (2) quantify the
importance of context for classification, (3) qualitatively compare DNNs
against FV classifiers in terms of important image regions and (4) detect
potential flaws and biases in data. All experiments are performed on the PASCAL
VOC 2007 data set.
Augmenting Phrase Table by Employing Lexicons for Pivot-based SMT
Authors: Yiming Cui, Conghui Zhu, Xiaoning Zhu, Tiejun Zhao
Date: 2015-12-01 00:00:00
Tasks: Machine Translation, Translation

Pivot language is employed as a way to solve the data sparseness problem in
machine translation, especially when the data for a particular language pair
does not exist. The combination of source-to-pivot and pivot-to-target
translation models can induce a new translation model through the pivot
language. However, the errors in two models may compound as noise, and still,
the combined model may suffer from a serious phrase sparsity problem. In this
paper, we directly employ the word lexical model in IBM models as an additional
resource to augment pivot phrase table. In addition, we also propose a phrase
table pruning method which takes into account both of the source and target
phrasal coverage. Experimental result shows that our pruning method
significantly outperforms the conventional one, which only considers source
side phrasal coverage. Furthermore, by including the entries in the lexicon
model, the phrase coverage increased, and we achieved improved results in
Chinese-to-Japanese translation using English as pivot language.
Learning Using 1-Local Membership Queries
Authors: Galit Bary
Date: 2015-12-01 00:00:00
Tasks: Machine Translation, Sentence, Sentiment Analysis, Translation

Classic machine learning algorithms learn from labelled examples. For
example, to design a machine translation system, a typical training set will
consist of English sentences and their translation. There is a stronger model,
in which the algorithm can also query for labels of new examples it creates.
E.g, in the translation task, the algorithm can create a new English sentence,
and request its translation from the user during training. This combination of
examples and queries has been widely studied. Yet, despite many theoretical
results, query algorithms are almost never used. One of the main causes for
this is a report (Baum and Lang, 1992) on very disappointing empirical
performance of a query algorithm. These poor results were mainly attributed to
the fact that the algorithm queried for labels of examples that are artificial,
and impossible to interpret by humans.
  In this work we study a new model of local membership queries (Awasthi et
al., 2012), which tries to resolve the problem of artificial queries. In this
model, the algorithm is only allowed to query the labels of examples which are
close to examples from the training set. E.g., in translation, the algorithm
can change individual words in a sentence it has already seen, and then ask for
the translation. In this model, the examples queried by the algorithm will be
close to natural examples and hence, hopefully, will not appear as artificial
or random. We focus on 1-local queries (i.e., queries of distance 1 from an
example in the training sample). We show that 1-local membership queries are
already stronger than the standard learning model. We also present an
experiment on a well known NLP task of sentiment analysis. In this experiment,
the users were asked to provide more information than merely indicating the
label. We present results that illustrate that this extra information is
beneficial in practice.
Optimal Estimation and Completion of Matrices with Biclustering Structures
Authors: Chao Gao, Yu Lu, Zongming Ma, Harrison H. Zhou
Date: 2015-12-01 00:00:00

Biclustering structures in data matrices were first formalized in a seminal
paper by John Hartigan (1972) where one seeks to cluster cases and variables
simultaneously. Such structures are also prevalent in block modeling of
networks. In this paper, we develop a unified theory for the estimation and
completion of matrices with biclustering structures, where the data is a
partially observed and noise contaminated data matrix with a certain
biclustering structure. In particular, we show that a constrained least squares
estimator achieves minimax rate-optimal performance in several of the most
important scenarios. To this end, we derive unified high probability upper
bounds for all sub-Gaussian data and also provide matching minimax lower bounds
in both Gaussian and binary cases. Due to the close connection of graphon to
stochastic block models, an immediate consequence of our general results is a
minimax rate-optimal estimator for sparse graphons.
Implicit Sparse Code Hashing
Authors: Tsung-Yu Lin, Tsung-Wei Ke, Tyng-Luh Liu
Date: 2015-12-01 00:00:00
Tasks: Dimensionality Reduction

We address the problem of converting large-scale high-dimensional image data
into binary codes so that approximate nearest-neighbor search over them can be
efficiently performed. Different from most of the existing unsupervised
approaches for yielding binary codes, our method is based on a
dimensionality-reduction criterion that its resulting mapping is designed to
preserve the image relationships entailed by the inner products of sparse
codes, rather than those implied by the Euclidean distances in the ambient
space. While the proposed formulation does not require computing any sparse
codes, the underlying computation model still inevitably involves solving an
unmanageable eigenproblem when extremely high-dimensional descriptors are used.
To overcome the difficulty, we consider the column-sampling technique and
presume a special form of rotation matrix to facilitate subproblem
decomposition. We test our method on several challenging image datasets and
demonstrate its effectiveness by comparing with state-of-the-art binary coding
techniques.
A Bennett Inequality for the Missing Mass
Authors: Bahman Yari Saeed Khanloo
Date: 2015-03-20 00:00:00
Tasks: Learning Theory

Novel concentration inequalities are obtained for the missing mass, i.e. the
total probability mass of the outcomes not observed in the sample. We derive
distribution-free deviation bounds with sublinear exponents in deviation size
for missing mass and improve the results of Berend and Kontorovich (2013) and
Yari Saeed Khanloo and Haffari (2015) for small deviations which is the most
important case in learning theory.
Inferring Interpersonal Relations in Narrative Summaries
Authors: Shashank Srivastava, Snigdha Chaturvedi, Tom Mitchell
Date: 2015-12-01 00:00:00
Tasks: Clustering, Structured Prediction

Characterizing relationships between people is fundamental for the
understanding of narratives. In this work, we address the problem of inferring
the polarity of relationships between people in narrative summaries. We
formulate the problem as a joint structured prediction for each narrative, and
present a model that combines evidence from linguistic and semantic features,
as well as features based on the structure of the social community in the text.
We also provide a clustering-based approach that can exploit regularities in
narrative types. e.g., learn an affinity for love-triangles in romantic
stories. On a dataset of movie summaries from Wikipedia, our structured models
provide more than a 30% error-reduction over a competitive baseline that
considers pairs of characters in isolation.
Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times
Authors: Anand Subramanian, Katyanne Farias
Date: 2015-01-23 00:00:00
Tasks: CPU, Scheduling

This paper concerns the single machine total weighted tardiness scheduling
with sequence-dependent setup times, usually referred as $1|s_{ij}|\sum
w_jT_j$. In this $\mathcal{NP}$-hard problem, each job has an associated
processing time, due date and a weight. For each pair of jobs $i$ and $j$,
there may be a setup time before starting to process $j$ in case this job is
scheduled immediately after $i$. The objective is to determine a schedule that
minimizes the total weighted tardiness, where the tardiness of a job is equal
to its completion time minus its due date, in case the job is completely
processed only after its due date, and is equal to zero otherwise. Due to its
complexity, this problem is most commonly solved by heuristics. The aim of this
work is to develop a simple yet effective limitation strategy that speeds up
the local search procedure without a significant loss in the solution quality.
Such strategy consists of a filtering mechanism that prevents unpromising moves
to be evaluated. The proposed strategy has been embedded in a local search
based metaheuristic from the literature and tested in classical benchmark
instances. Computational experiments revealed that the limitation strategy
enabled the metaheuristic to be extremely competitive when compared to other
algorithms from the literature, since it allowed the use of a large number of
neighborhood structures without a significant increase in the CPU time and,
consequently, high quality solutions could be achieved in a matter of seconds.
In addition, we analyzed the effectiveness of the proposed strategy in two
other well-known metaheuristics. Further experiments were also carried out on
benchmark instances of problem $1|s_{ij}|\sum T_j$.
Optimization theory of Hebbian/anti-Hebbian networks for PCA and whitening
Authors: Cengiz Pehlevan, Dmitri B. Chklovskii
Date: 2015-11-30 00:00:00

In analyzing information streamed by sensory organs, our brains face
challenges similar to those solved in statistical signal processing. This
suggests that biologically plausible implementations of online signal
processing algorithms may model neural computation. Here, we focus on such
workhorses of signal processing as Principal Component Analysis (PCA) and
whitening which maximize information transmission in the presence of noise. We
adopt the similarity matching framework, recently developed for principal
subspace extraction, but modify the existing objective functions by adding a
decorrelating term. From the modified objective functions, we derive online PCA
and whitening algorithms which are implementable by neural networks with local
learning rules, i.e. synaptic weight updates that depend on the activity of
only pre- and postsynaptic neurons. Our theory offers a principled model of
neural computations and makes testable predictions such as the dropout of
underutilized neurons.
Estimation with Norm Regularization
Authors: Arindam Banerjee, Sheng Chen, Farideh Fazayeli, Vidyashankar Sivakumar
Date: 2015-05-09 00:00:00
Proceeding: NeurIPS 2014 12

Analysis of non-asymptotic estimation error and structured statistical
recovery based on norm regularized regression, such as Lasso, needs to consider
four aspects: the norm, the loss function, the design matrix, and the noise
model. This paper presents generalizations of such estimation error analysis on
all four aspects compared to the existing literature. We characterize the
restricted error set where the estimation error vector lies, establish
relations between error sets for the constrained and regularized problems, and
present an estimation error bound applicable to any norm. Precise
characterizations of the bound is presented for isotropic as well as
anisotropic subGaussian design matrices, subGaussian noise models, and convex
loss functions, including least squares and generalized linear models. Generic
chaining and associated results play an important role in the analysis. A key
result from the analysis is that the sample complexity of all such estimators
depends on the Gaussian width of a spherical cap corresponding to the
restricted error set. Further, once the number of samples $n$ crosses the
required sample complexity, the estimation error decreases as
$\frac{c}{\sqrt{n}}$, where $c$ depends on the Gaussian width of the unit norm
ball.
Ask, and shall you receive?: Understanding Desire Fulfillment in Natural Language Text
Authors: Snigdha Chaturvedi, Dan Goldwasser, Hal Daume III
Date: 2015-11-30 00:00:00
Tasks: Natural Language Understanding

The ability to comprehend wishes or desires and their fulfillment is
important to Natural Language Understanding. This paper introduces the task of
identifying if a desire expressed by a subject in a given short piece of text
was fulfilled. We propose various unstructured and structured models that
capture fulfillment cues such as the subject's emotional state and actions. Our
experiments with two different datasets demonstrate the importance of
understanding the narrative and discourse structure to address this task.
A Hebbian/Anti-Hebbian Network for Online Sparse Dictionary Learning Derived from Symmetric Matrix Factorization
Authors: Tao Hu, Cengiz Pehlevan, Dmitri B. Chklovskii
Date: 2015-03-02 00:00:00
Tasks: Dictionary Learning

Olshausen and Field (OF) proposed that neural computations in the primary
visual cortex (V1) can be partially modeled by sparse dictionary learning. By
minimizing the regularized representation error they derived an online
algorithm, which learns Gabor-filter receptive fields from a natural image
ensemble in agreement with physiological experiments. Whereas the OF algorithm
can be mapped onto the dynamics and synaptic plasticity in a single-layer
neural network, the derived learning rule is nonlocal - the synaptic weight
update depends on the activity of neurons other than just pre- and postsynaptic
ones - and hence biologically implausible. Here, to overcome this problem, we
derive sparse dictionary learning from a novel cost-function - a regularized
error of the symmetric factorization of the input's similarity matrix. Our
algorithm maps onto a neural network of the same architecture as OF but using
only biologically plausible local learning rules. When trained on natural
images our network learns Gabor-filter receptive fields and reproduces the
correlation among synaptic weights hard-wired in the OF network. Therefore,
online symmetric matrix factorization may serve as an algorithmic theory of
neural computation.
Circulant temporal encoding for video retrieval and temporal alignment
Authors: Matthijs Douze, Jérôme Revaud, Jakob Verbeek, Hervé Jégou, Cordelia Schmid
Date: 2015-06-08 00:00:00
Tasks: Retrieval, Video Retrieval

We address the problem of specific video event retrieval. Given a query video
of a specific event, e.g., a concert of Madonna, the goal is to retrieve other
videos of the same event that temporally overlap with the query. Our approach
encodes the frame descriptors of a video to jointly represent their appearance
and temporal order. It exploits the properties of circulant matrices to
efficiently compare the videos in the frequency domain. This offers a
significant gain in complexity and accurately localizes the matching parts of
videos. The descriptors can be compressed in the frequency domain with a
product quantizer adapted to complex numbers. In this case, video retrieval is
performed without decompressing the descriptors. We also consider the temporal
alignment of a set of videos. We exploit the matching confidence and an
estimate of the temporal offset computed for all pairs of videos by our
retrieval approach. Our robust algorithm aligns the videos on a global timeline
by maximizing the set of temporally consistent matches. The global temporal
alignment enables synchronous playback of the videos of a given scene.
Modeling Dynamic Relationships Between Characters in Literary Novels
Authors: Snigdha Chaturvedi, Shashank Srivastava, Hal Daume III, Chris Dyer
Date: 2015-11-30 00:00:00
Tasks: Structured Prediction, World Knowledge

Studying characters plays a vital role in computationally representing and
interpreting narratives. Unlike previous work, which has focused on inferring
character roles, we focus on the problem of modeling their relationships.
Rather than assuming a fixed relationship for a character pair, we hypothesize
that relationships are dynamic and temporally evolve with the progress of the
narrative, and formulate the problem of relationship modeling as a structured
prediction problem. We propose a semi-supervised framework to learn
relationship sequences from fully as well as partially labeled data. We present
a Markovian model capable of accumulating historical beliefs about the
relationship and status changes. We use a set of rich linguistic and
semantically motivated features that incorporate world knowledge to investigate
the textual content of narrative. We empirically demonstrate that such a
framework outperforms competitive baselines.
Formalizing Preference Utilitarianism in Physical World Models
Authors: Caspar Oesterheld
Date: 2015-04-21 00:00:00
Tasks: Bayesian Inference, Ethics

Most ethical work is done at a low level of formality. This makes practical
moral questions inaccessible to formal and natural sciences and can lead to
misunderstandings in ethical discussion. In this paper, we use Bayesian
inference to introduce a formalization of preference utilitarianism in physical
world models, specifically cellular automata. Even though our formalization is
not immediately applicable, it is a first step in providing ethics and
ultimately the question of how to "make the world better" with a formal basis.
Pattern Recognition of Bearing Faults using Smoother Statistical Features
Authors: Muhammad Masood Tahir, Ayyaz Hussain
Date: 2015-03-15 00:00:00
Tasks: Diagnostic

A pattern recognition (PR) based diagnostic scheme is presented to identify
bearing faults, using time domain features. Vibration data is acquired from
faulty bearings using a test rig. The features are extracted from the data, and
processed prior to utilize in the PR process. The processing involves smoothing
of feature distributions. This reduces the undesired impact of vibration
randomness on the PR process, and thus enhances the diagnostic accuracy of the
model.
Influence diagrams for the optimization of a vehicle speed profile
Authors: Václav Kratochvíl, Jiří Vomlel
Date: 2015-11-30 00:00:00

Influence diagrams are decision theoretic extensions of Bayesian networks.
They are applied to diverse decision problems. In this paper we apply influence
diagrams to the optimization of a vehicle speed profile. We present results of
computational experiments in which an influence diagram was used to optimize
the speed profile of a Formula 1 race car at the Silverstone F1 circuit. The
computed lap time and speed profiles correspond well to those achieved by test
pilots. An extended version of our model that considers a more complex
optimization function and diverse traffic constraints is currently being tested
onboard a testing car by a major car manufacturer. This paper opens doors for
new applications of influence diagrams.