pwc-archive/papers-with-abstracts huggingface dataset:
Bounded Situation Calculus Action Theories
Authors: Giuseppe De Giacomo, Yves Lespérance, Fabio Patrizi
Date: 2015-09-07 00:00:00

In this paper, we investigate bounded action theories in the situation
calculus. A bounded action theory is one which entails that, in every
situation, the number of object tuples in the extension of fluents is bounded
by a given constant, although such extensions are in general different across
the infinitely many situations. We argue that such theories are common in
applications, either because facts do not persist indefinitely or because the
agent eventually forgets some facts, as new ones are learnt. We discuss various
classes of bounded action theories. Then we show that verification of a
powerful first-order variant of the mu-calculus is decidable for such theories.
Notably, this variant supports a controlled form of quantification across
situations. We also show that through verification, we can actually check
whether an arbitrary action theory maintains boundedness.
Distributed Machine Learning via Sufficient Factor Broadcasting
Authors: Pengtao Xie, Jin Kyu Kim, Yi Zhou, Qirong Ho, Abhimanu Kumar, Yao-Liang Yu, Eric Xing
Date: 2014-09-19 00:00:00
Tasks: BIG-bench Machine Learning

Matrix-parametrized models, including multiclass logistic regression and
sparse coding, are used in machine learning (ML) applications ranging from
computer vision to computational biology. When these models are applied to
large-scale ML problems starting at millions of samples and tens of thousands
of classes, their parameter matrix can grow at an unexpected rate, resulting in
high parameter synchronization costs that greatly slow down distributed
learning. To address this issue, we propose a Sufficient Factor Broadcasting
(SFB) computation model for efficient distributed learning of a large family of
matrix-parameterized models, which share the following property: the parameter
update computed on each data sample is a rank-1 matrix, i.e., the outer product
of two "sufficient factors" (SFs). By broadcasting the SFs among worker
machines and reconstructing the update matrices locally at each worker, SFB
improves communication efficiency --- communication costs are linear in the
parameter matrix's dimensions, rather than quadratic --- without affecting
computational correctness. We present a theoretical convergence analysis of
SFB, and empirically corroborate its efficiency on four different
matrix-parametrized ML models.
An Approach to the Analysis of the South Slavic Medieval Labels Using Image Texture
Authors: Darko Brodic, Alessia Amelio, Zoran N. Milivojevic
Date: 2015-09-07 00:00:00
Tasks: Classification, Clustering, Diversity, General Classification

The paper presents a new script classification method for the discrimination
of the South Slavic medieval labels. It consists in the textural analysis of
the script types. In the first step, each letter is coded by the equivalent
script type, which is defined by its typographical features. Obtained coded
text is subjected to the run-length statistical analysis and to the adjacent
local binary pattern analysis in order to extract the features. The result
shows a diversity between the extracted features of the scripts, which makes
the feature classification more effective. It is the basis for the
classification process of the script identification by using an extension of a
state-of-the-art approach for document clustering. The proposed method is
evaluated on an example of hand-engraved in stone and hand-printed in paper
labels in old Cyrillic, angular and round Glagolitic. Experiments demonstrate
very positive results, which prove the effectiveness of the proposed method.
Automated Analysis of Behavioural Variability and Filial Imprinting of Chicks (G. gallus), using Autonomous Robots
Authors: A. Gribovskiy, F. Mondada, J. L. Deneubourg, L. Cazenille, N. Bredeche, J. Halloy
Date: 2015-09-07 00:00:00

Inter-individual variability has various impacts in animal social behaviour.
This implies that not only collective behaviours have to be studied but also
the behavioural variability of each member composing the groups. To understand
those effects on group behaviour, we develop a quantitative methodology based
on automated ethograms and autonomous robots to study the inter-individual
variability among social animals. We choose chicks of \textit{Gallus gallus
domesticus} as a classic social animal model system for their suitability in
laboratory and controlled experimentation. Moreover, even domesticated chicken
present social structures implying forms or leadership and filial imprinting.
We develop an imprinting methodology on autonomous robots to study individual
and social behaviour of free moving animals. This allows to quantify the
behaviours of large number of animals. We develop an automated experimental
methodology that allows to make relatively fast controlled experiments and
efficient data analysis. Our analysis are based on high-throughput data
allowing a fine quantification of individual behavioural traits. We quantify
the efficiency of various state-of-the-art algorithms to automate data analysis
and produce automated ethograms. We show that the use of robots allows to
provide controlled and quantified stimuli to the animals in absence of human
intervention. We quantify the individual behaviour of 205 chicks obtained from
hatching after synchronized fecundation. Our results show a high variability of
individual behaviours and of imprinting quality and success. Three classes of
chicks are observed with various level of imprinting. Our study shows that the
concomitant use of autonomous robots and automated ethograms allows detailed
and quantitative analysis of behavioural patterns of animals in controlled
laboratory experiments.
Hierarchical Deep Learning Architecture For 10K Objects Classification
Authors: Atul Laxman Katole, Krishna Prasad Yellapragada, Amish Kumar Bedi, Sehaj Singh Kalra, Mynepalli Siva Chaitanya
Date: 2015-09-07 00:00:00
Tasks: Classification, Deep Learning, General Classification, Object Recognition

Evolution of visual object recognition architectures based on Convolutional
Neural Networks & Convolutional Deep Belief Networks paradigms has
revolutionized artificial Vision Science. These architectures extract & learn
the real world hierarchical visual features utilizing supervised & unsupervised
learning approaches respectively. Both the approaches yet cannot scale up
realistically to provide recognition for a very large number of objects as high
as 10K. We propose a two level hierarchical deep learning architecture inspired
by divide & conquer principle that decomposes the large scale recognition
architecture into root & leaf level model architectures. Each of the root &
leaf level models is trained exclusively to provide superior results than
possible by any 1-level deep learning architecture prevalent today. The
proposed architecture classifies objects in two steps. In the first step the
root level model classifies the object in a high level category. In the second
step, the leaf level recognition model for the recognized high level category
is selected among all the leaf models. This leaf level model is presented with
the same input object image which classifies it in a specific category. Also we
propose a blend of leaf level models trained with either supervised or
unsupervised learning approaches. Unsupervised learning is suitable whenever
labelled data is scarce for the specific leaf level models. Currently the
training of leaf level models is in progress; where we have trained 25 out of
the total 47 leaf level models as of now. We have trained the leaf models with
the best case top-5 error rate of 3.2% on the validation data set for the
particular leaf models. Also we demonstrate that the validation error of the
leaf level models saturates towards the above mentioned accuracy as the number
of epochs are increased to more than sixty.
A Fast and Accurate Unconstrained Face Detector
Authors: Shengcai Liao, Anil K. Jain, Stan Z. Li
Date: 2014-08-06 00:00:00
Tasks: Face Detection, Robust Face Recognition

We propose a method to address challenges in unconstrained face detection, such as arbitrary pose variations and occlusions. First, a new image feature called Normalized Pixel Difference (NPD) is proposed. NPD feature is computed as the difference to sum ratio between two pixel values, inspired by the Weber Fraction in experimental psychology. The new feature is scale invariant, bounded, and is able to reconstruct the original image. Second, we propose a deep quadratic tree to learn the optimal subset of NPD features and their combinations, so that complex face manifolds can be partitioned by the learned rules. This way, only a single soft-cascade classifier is needed to handle unconstrained face detection. Furthermore, we show that the NPD features can be efficiently obtained from a look up table, and the detection template can be easily scaled, making the proposed face detector very fast. Experimental results on three public face datasets (FDDB, GENKI, and CMU-MIT) show that the proposed method achieves state-of-the-art performance in detecting unconstrained faces with arbitrary pose variations and occlusions in cluttered scenes.
Exploiting Out-of-Domain Data Sources for Dialectal Arabic Statistical Machine Translation
Authors: Katrin Kirchhoff, Bing Zhao, Wen Wang
Date: 2015-09-07 00:00:00
Tasks: Machine Translation, Translation

Statistical machine translation for dialectal Arabic is characterized by a
lack of data since data acquisition involves the transcription and translation
of spoken language. In this study we develop techniques for extracting parallel
data for one particular dialect of Arabic (Iraqi Arabic) from out-of-domain
corpora in different dialects of Arabic or in Modern Standard Arabic. We
compare two different data selection strategies (cross-entropy based and
submodular selection) and demonstrate that a very small but highly targeted
amount of found data can improve the performance of a baseline machine
translation system. We furthermore report on preliminary experiments on using
automatically translated speech data as additional training data.
Approval Voting and Incentives in Crowdsourcing
Authors: Nihar B. Shah, Dengyong Zhou, Yuval Peres
Date: 2015-02-19 00:00:00

The growing need for labeled training data has made crowdsourcing an
important part of machine learning. The quality of crowdsourced labels is,
however, adversely affected by three factors: (1) the workers are not experts;
(2) the incentives of the workers are not aligned with those of the requesters;
and (3) the interface does not allow workers to convey their knowledge
accurately, by forcing them to make a single choice among a set of options. In
this paper, we address these issues by introducing approval voting to utilize
the expertise of workers who have partial knowledge of the true answer, and
coupling it with a ("strictly proper") incentive-compatible compensation
mechanism. We show rigorous theoretical guarantees of optimality of our
mechanism together with a simple axiomatic characterization. We also conduct
preliminary empirical studies on Amazon Mechanical Turk which validate our
approach.
Fishing out Winners from Vote Streams
Authors: Arnab Bhattacharyya, Palash Dey
Date: 2015-08-19 00:00:00

We investigate the problem of winner determination from computational social
choice theory in the data stream model. Specifically, we consider the task of
summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a
small space data structure so as to be able to obtain the winner determined by
popular voting rules. As we show, finding the exact winner requires storing
essentially all the votes. So, we focus on the problem of finding an {\em
$\eps$-winner}, a candidate who could win by a change of at most $\eps$
fraction of the votes. We show non-trivial upper and lower bounds on the space
complexity of $\eps$-winner determination for several voting rules, including
$k$-approval, $k$-veto, scoring rules, approval, maximin, Bucklin, Copeland,
and plurality with run off.
A Hybrid Approach to Domain-Specific Entity Linking
Authors: Alex Olieman, Jaap Kamps, Maarten Marx, Arjan Nusselder
Date: 2015-09-06 00:00:00
Tasks: Entity Linking

The current state-of-the-art Entity Linking (EL) systems are geared towards
corpora that are as heterogeneous as the Web, and therefore perform
sub-optimally on domain-specific corpora. A key open problem is how to
construct effective EL systems for specific domains, as knowledge of the local
context should in principle increase, rather than decrease, effectiveness. In
this paper we propose the hybrid use of simple specialist linkers in
combination with an existing generalist system to address this problem. Our
main findings are the following. First, we construct a new reusable benchmark
for EL on a corpus of domain-specific conversations. Second, we test the
performance of a range of approaches under the same conditions, and show that
specialist linkers obtain high precision in isolation, and high recall when
combined with generalist linkers. Hence, we can effectively exploit local
context and get the best of both worlds.
Compressed Nonnegative Matrix Factorization is Fast and Accurate
Authors: Mariano Tepper, Guillermo Sapiro
Date: 2015-05-18 00:00:00

Nonnegative matrix factorization (NMF) has an established reputation as a
useful data analysis technique in numerous applications. However, its usage in
practical situations is undergoing challenges in recent years. The fundamental
factor to this is the increasingly growing size of the datasets available and
needed in the information sciences. To address this, in this work we propose to
use structured random compression, that is, random projections that exploit the
data structure, for two NMF variants: classical and separable. In separable NMF
(SNMF) the left factors are a subset of the columns of the input matrix. We
present suitable formulations for each problem, dealing with different
representative algorithms within each one. We show that the resulting
compressed techniques are faster than their uncompressed variants, vastly
reduce memory demands, and do not encompass any significant deterioration in
performance. The proposed structured random projections for SNMF allow to deal
with arbitrarily shaped large matrices, beyond the standard limit of
tall-and-skinny matrices, granting access to very efficient computations in
this general setting. We accompany the algorithmic presentation with
theoretical foundations and numerous and diverse examples, showing the
suitability of the proposed approaches.
Research: Analysis of Transport Model that Approximates Decision Taker's Preferences
Authors: Valery Vilisov
Date: 2015-09-06 00:00:00

Paper provides a method for solving the reverse Monge-Kantorovich transport
problem (TP). It allows to accumulate positive decision-taking experience made
by decision-taker in situations that can be presented in the form of TP. The
initial data for the solution of the inverse TP is the information on orders,
inventories and effective decisions take by decision-taker. The result of
solving the inverse TP contains evaluations of the TPs payoff matrix elements.
It can be used in new situations to select the solution corresponding to the
preferences of the decision-taker. The method allows to gain decision-taker
experience, so it can be used by others. The method allows to build the model
of decision-taker preferences in a specific application area. The model can be
updated regularly to ensure its relevance and adequacy to the decision-taker
system of preferences. This model is adaptive to the current preferences of the
decision taker.
A Total Fractional-Order Variation Model for Image Restoration with Non-homogeneous Boundary Conditions and its Numerical Solution
Authors: Jianping Zhang, Ke Chen
Date: 2015-09-06 00:00:00
Tasks: Image Restoration

To overcome the weakness of a total variation based model for image
restoration, various high order (typically second order) regularization models
have been proposed and studied recently. In this paper we analyze and test a
fractional-order derivative based total $\alpha$-order variation model, which
can outperform the currently popular high order regularization models. There
exist several previous works using total $\alpha$-order variations for image
restoration; however first no analysis is done yet and second all tested
formulations, differing from each other, utilize the zero Dirichlet boundary
conditions which are not realistic (while non-zero boundary conditions violate
definitions of fractional-order derivatives). This paper first reviews some
results of fractional-order derivatives and then analyzes the theoretical
properties of the proposed total $\alpha$-order variational model rigorously.
It then develops four algorithms for solving the variational problem, one based
on the variational Split-Bregman idea and three based on direct solution of the
discretise-optimization problem. Numerical experiments show that, in terms of
restoration quality and solution efficiency, the proposed model can produce
highly competitive results, for smooth images, to two established high order
models: the mean curvature and the total generalized variation.
Robust and highly performant ring detection algorithm for 3d particle tracking using 2d microscope imaging
Authors: Eldad Afik
Date: 2013-10-02 00:00:00

Three-dimensional particle tracking is an essential tool in studying dynamics
under the microscope, namely, fluid dynamics in microfluidic devices, bacteria
taxis, cellular trafficking. The 3d position can be determined using 2d imaging
alone by measuring the diffraction rings generated by an out-of-focus
fluorescent particle, imaged on a single camera. Here I present a ring
detection algorithm exhibiting a high detection rate, which is robust to the
challenges arising from ring occlusion, inclusions and overlaps, and allows
resolving particles even when near to each other. It is capable of real time
analysis thanks to its high performance and low memory footprint. The proposed
algorithm, an offspring of the circle Hough transform, addresses the need to
efficiently trace the trajectories of many particles concurrently, when their
number in not necessarily fixed, by solving a classification problem, and
overcomes the challenges of finding local maxima in the complex parameter space
which results from ring clusters and noise. Several algorithmic concepts
introduced here can be advantageous in other cases, particularly when dealing
with noisy and sparse data. The implementation is based on open-source and
cross-platform software packages only, making it easy to distribute and modify.
It is implemented in a microfluidic experiment allowing real-time
multi-particle tracking at 70 Hz, achieving a detection rate which exceeds 94%
and only 1% false-detection.
Simultaneous Clustering and Model Selection for Multinomial Distribution: A Comparative Study
Authors: Md. Abul Hasnat, Julien Velcin, Stéphane Bonnevay, Julien Jacques
Date: 2015-05-09 00:00:00
Tasks: Clustering, Model Selection

In this paper, we study different discrete data clustering methods, which use
the Model-Based Clustering (MBC) framework with the Multinomial distribution.
Our study comprises several relevant issues, such as initialization, model
estimation and model selection. Additionally, we propose a novel MBC method by
efficiently combining the partitional and hierarchical clustering techniques.
We conduct experiments on both synthetic and real data and evaluate the methods
using accuracy, stability and computation time. Our study identifies
appropriate strategies to be used for discrete data analysis with the MBC
methods. Moreover, our proposed method is very competitive w.r.t. clustering
accuracy and better w.r.t. stability and computation time.
Joint Color-Spatial-Directional clustering and Region Merging (JCSD-RM) for unsupervised RGB-D image segmentation
Authors: Md. Abul Hasnat, Olivier Alata, Alain Trémeau
Date: 2015-09-06 00:00:00
Tasks: Clustering, Image Generation, Image Segmentation, Segmentation, Semantic Segmentation

Recent advances in depth imaging sensors provide easy access to the
synchronized depth with color, called RGB-D image. In this paper, we propose an
unsupervised method for indoor RGB-D image segmentation and analysis. We
consider a statistical image generation model based on the color and geometry
of the scene. Our method consists of a joint color-spatial-directional
clustering method followed by a statistical planar region merging method. We
evaluate our method on the NYU depth database and compare it with existing
unsupervised RGB-D segmentation methods. Results show that, it is comparable
with the state of the art methods and it needs less computation time. Moreover,
it opens interesting perspectives to fuse color and geometry in an unsupervised
manner.
Theoretical and Experimental Analyses of Tensor-Based Regression and Classification
Authors: Kishan Wimalawarne, Ryota Tomioka, Masashi Sugiyama
Date: 2015-09-06 00:00:00
Tasks: Classification, General Classification, regression

We theoretically and experimentally investigate tensor-based regression and
classification. Our focus is regularization with various tensor norms,
including the overlapped trace norm, the latent trace norm, and the scaled
latent trace norm. We first give dual optimization methods using the
alternating direction method of multipliers, which is computationally efficient
when the number of training samples is moderate. We then theoretically derive
an excess risk bound for each tensor norm and clarify their behavior. Finally,
we perform extensive experiments using simulated and real data and demonstrate
the superiority of tensor-based learning methods over vector- and matrix-based
learning methods.
Unsupervised Cross-Domain Recognition by Identifying Compact Joint Subspaces
Authors: Yuewei Lin, Jing Chen, Yu Cao, Youjie Zhou, Lingfeng Zhang, Yuan Yan Tang, Song Wang
Date: 2015-09-05 00:00:00
Tasks: Domain Adaptation, Object Recognition, Sentiment Analysis, Sentiment Classification

This paper introduces a new method to solve the cross-domain recognition
problem. Different from the traditional domain adaption methods which rely on a
global domain shift for all classes between source and target domain, the
proposed method is more flexible to capture individual class variations across
domains. By adopting a natural and widely used assumption -- "the data samples
from the same class should lay on a low-dimensional subspace, even if they come
from different domains", the proposed method circumvents the limitation of the
global domain shift, and solves the cross-domain recognition by finding the
compact joint subspaces of source and target domain. Specifically, given
labeled samples in source domain, we construct subspaces for each of the
classes. Then we construct subspaces in the target domain, called anchor
subspaces, by collecting unlabeled samples that are close to each other and
highly likely all fall into the same class. The corresponding class label is
then assigned by minimizing a cost function which reflects the overlap and
topological structure consistency between subspaces across source and target
domains, and within anchor subspaces, respectively.We further combine the
anchor subspaces to corresponding source subspaces to construct the compact
joint subspaces. Subsequently, one-vs-rest SVM classifiers are trained in the
compact joint subspaces and applied to unlabeled data in the target domain. We
evaluate the proposed method on two widely used datasets: object recognition
dataset for computer vision tasks, and sentiment classification dataset for
natural language processing tasks. Comparison results demonstrate that the
proposed method outperforms the comparison methods on both datasets.