pwc-archive/papers-with-abstracts huggingface dataset:
Generalized version of the support vector machine for binary classification problems: supporting hyperplane machine
Authors: E. G. Abramov, A. B. Komissarov, D. A. Kornyakov
Date: 2014-04-13 00:00:00
Tasks: Binary Classification, General Classification

In this paper there is proposed a generalized version of the SVM for binary
classification problems in the case of using an arbitrary transformation x ->
y. An approach similar to the classic SVM method is used. The problem is widely
explained. Various formulations of primal and dual problems are proposed. For
one of the most important cases the formulae are derived in detail. A simple
computational example is demonstrated. The algorithm and its implementation is
presented in Octave language.
Assessing the Quality of MT Systems for Hindi to English Translation
Authors: Aditi Kalyani, Hemant Kumud, Shashi Pal Singh, Ajai Kumar
Date: 2014-04-15 00:00:00
Tasks: Translation

Evaluation plays a vital role in checking the quality of MT output. It is
done either manually or automatically. Manual evaluation is very time consuming
and subjective, hence use of automatic metrics is done most of the times. This
paper evaluates the translation quality of different MT Engines for
Hindi-English (Hindi data is provided as input and English is obtained as
output) using various automatic metrics like BLEU, METEOR etc. Further the
comparison automatic evaluation results with Human ranking have also been
given.
Spiralet Sparse Representation
Authors: Reza Farrahi Moghaddam, Mohamed Cheriet
Date: 2014-04-15 00:00:00

This is the first report on Working Paper WP-RFM-14-01. The potential and
capability of sparse representations is well-known. However, their
(multivariate variable) vectorial form, which is completely fine in many fields
and disciplines, results in removal and filtering of important "spatial"
relations that are implicitly carried by two-dimensional [or multi-dimensional]
objects, such as images. In this paper, a new approach, called spiralet sparse
representation, is proposed in order to develop an augmented representation and
therefore a modified sparse representation and theory, which is capable to
preserve the data associated to the spatial relations.
Texture Based Image Segmentation of Chili Pepper X-Ray Images Using Gabor Filter
Authors: M. Rajalakshmi, Dr. P. Subashini
Date: 2014-04-15 00:00:00
Tasks: Image Segmentation, Segmentation, Semantic Segmentation, Texture Classification

Texture segmentation is the process of partitioning an image into regions
with different textures containing a similar group of pixels. Detecting the
discontinuity of the filter's output and their statistical properties help in
segmenting and classifying a given image with different texture regions. In
this proposed paper, chili x-ray image texture segmentation is performed by
using Gabor filter. The texture segmented result obtained from Gabor filter fed
into three texture filters, namely Entropy, Standard Deviation and Range
filter. After performing texture analysis, features can be extracted by using
Statistical methods. In this paper Gray Level Co-occurrence Matrices and First
order statistics are used as feature extraction methods. Features extracted
from statistical methods are given to Support Vector Machine (SVM) classifier.
Using this methodology, it is found that texture segmentation is followed by
the Gray Level Co-occurrence Matrix feature extraction method gives a higher
accuracy rate of 84% when compared with First order feature extraction method.
  Key Words: Texture segmentation, Texture filter, Gabor filter, Feature
extraction methods, SVM classifier.
Is it morally acceptable for a system to lie to persuade me?
Authors: Marco Guerini, Fabio Pianesi, Oliviero Stock
Date: 2014-04-15 00:00:00

Given the fast rise of increasingly autonomous artificial agents and robots,
a key acceptability criterion will be the possible moral implications of their
actions. In particular, intelligent persuasive systems (systems designed to
influence humans via communication) constitute a highly sensitive topic because
of their intrinsically social nature. Still, ethical studies in this area are
rare and tend to focus on the output of the required action. Instead, this work
focuses on the persuasive acts themselves (e.g. "is it morally acceptable that
a machine lies or appeals to the emotions of a person to persuade her, even if
for a good end?"). Exploiting a behavioral approach, based on human assessment
of moral dilemmas -- i.e. without any prior assumption of underlying ethical
theories -- this paper reports on a set of experiments. These experiments
address the type of persuader (human or machine), the strategies adopted
(purely argumentative, appeal to positive emotions, appeal to negative
emotions, lie) and the circumstances. Findings display no differences due to
the agent, mild acceptability for persuasion and reveal that truth-conditional
reasoning (i.e. argument validity) is a significant dimension affecting
subjects' judgment. Some implications for the design of intelligent persuasive
systems are discussed.
Scalable Matting: A Sub-linear Approach
Authors: Philip G. Lee, Ying Wu
Date: 2014-04-15 00:00:00
Tasks: Image Matting

Natural image matting, which separates foreground from background, is a very
important intermediate step in recent computer vision algorithms. However, it
is severely underconstrained and difficult to solve. State-of-the-art
approaches include matting by graph Laplacian, which significantly improves the
underconstrained nature by reducing the solution space. However, matting by
graph Laplacian is still very difficult to solve and gets much harder as the
image size grows: current iterative methods slow down as $\mathcal{O}\left(n^2
\right)$ in the resolution $n$. This creates uncomfortable practical limits on
the resolution of images that we can matte. Current literature mitigates the
problem, but they all remain super-linear in complexity. We expose properties
of the problem that remain heretofore unexploited, demonstrating that an
optimization technique originally intended to solve PDEs can be adapted to take
advantage of this knowledge to solve the matting problem, not heuristically,
but exactly and with sub-linear complexity. This makes ours the most efficient
matting solver currently known by a very wide margin and allows matting finally
to be practical and scalable in the future as consumer photos exceed many
dozens of megapixels, and also relieves matting from being a bottleneck for
vision algorithms that depend on it.
Exploring the power of GPU's for training Polyglot language models
Authors: Vivek Kulkarni, Rami Al-Rfou', Bryan Perozzi, Steven Skiena
Date: 2014-04-05 00:00:00
Tasks: CPU, GPU

One of the major research trends currently is the evolution of heterogeneous
parallel computing. GP-GPU computing is being widely used and several
applications have been designed to exploit the massive parallelism that
GP-GPU's have to offer. While GPU's have always been widely used in areas of
computer vision for image processing, little has been done to investigate
whether the massive parallelism provided by GP-GPU's can be utilized
effectively for Natural Language Processing(NLP) tasks. In this work, we
investigate and explore the power of GP-GPU's in the task of learning language
models. More specifically, we investigate the performance of training Polyglot
language models using deep belief neural networks. We evaluate the performance
of training the model on the GPU and present optimizations that boost the
performance on the GPU.One of the key optimizations, we propose increases the
performance of a function involved in calculating and updating the gradient by
approximately 50 times on the GPU for sufficiently large batch sizes. We show
that with the above optimizations, the GP-GPU's performance on the task
increases by factor of approximately 3-4. The optimizations we made are generic
Theano optimizations and hence potentially boost the performance of other
models which rely on these operations.We also show that these optimizations
result in the GPU's performance at this task being now comparable to that on
the CPU. We conclude by presenting a thorough evaluation of the applicability
of GP-GPU's for this task and highlight the factors limiting the performance of
training a Polyglot model on the GPU.
Learning optimization models in the presence of unknown relations
Authors: Sicco Verwer, Yingqian Zhang, Qing Chuan Ye
Date: 2014-01-06 00:00:00
Tasks: regression

In a sequential auction with multiple bidding agents, it is highly
challenging to determine the ordering of the items to sell in order to maximize
the revenue due to the fact that the autonomy and private information of the
agents heavily influence the outcome of the auction.
  The main contribution of this paper is two-fold. First, we demonstrate how to
apply machine learning techniques to solve the optimal ordering problem in
sequential auctions. We learn regression models from historical auctions, which
are subsequently used to predict the expected value of orderings for new
auctions. Given the learned models, we propose two types of optimization
methods: a black-box best-first search approach, and a novel white-box approach
that maps learned models to integer linear programs (ILP) which can then be
solved by any ILP-solver. Although the studied auction design problem is hard,
our proposed optimization methods obtain good orderings with high revenues.
  Our second main contribution is the insight that the internal structure of
regression models can be efficiently evaluated inside an ILP solver for
optimization purposes. To this end, we provide efficient encodings of
regression trees and linear regression models as ILP constraints. This new way
of using learned models for optimization is promising. As the experimental
results show, it significantly outperforms the black-box best-first search in
nearly all settings.
Combining Drift Analysis and Generalized Schema Theory to Design Efficient Hybrid and/or Mixed Strategy EAs
Authors: Boris Mitavskiy, Jun He
Date: 2013-05-11 00:00:00
Tasks: Scheduling

Hybrid and mixed strategy EAs have become rather popular for tackling various
complex and NP-hard optimization problems. While empirical evidence suggests
that such algorithms are successful in practice, rather little theoretical
support for their success is available, not mentioning a solid mathematical
foundation that would provide guidance towards an efficient design of this type
of EAs. In the current paper we develop a rigorous mathematical framework that
suggests such designs based on generalized schema theory, fitness levels and
drift analysis. An example-application for tackling one of the classical
NP-hard problems, the "single-machine scheduling problem" is presented.
Meta-evaluation of comparability metrics using parallel corpora
Authors: Bogdan Babych, Anthony Hartley
Date: 2014-04-14 00:00:00

Metrics for measuring the comparability of corpora or texts need to be
developed and evaluated systematically. Applications based on a corpus, such as
training Statistical MT systems in specialised narrow domains, require finding
a reasonable balance between the size of the corpus and its consistency, with
controlled and benchmarked levels of comparability for any newly added
sections. In this article we propose a method that can meta-evaluate
comparability metrics by calculating monolingual comparability scores
separately on the 'source' and 'target' sides of parallel corpora. The range of
scores on the source side is then correlated (using Pearson's r coefficient)
with the range of 'target' scores; the higher the correlation - the more
reliable is the metric. The intuition is that a good metric should yield the
same distance between different domains in different languages. Our method
gives consistent results for the same metrics on different data sets, which
indicates that it is reliable and can be used for metric comparison or for
optimising settings of parametrised metrics.
Pure Strategy or Mixed Strategy?
Authors: Jun He, Feidun He, Hongbin Dong
Date: 2011-12-07 00:00:00

Mixed strategy EAs aim to integrate several mutation operators into a single
algorithm. However few theoretical analysis has been made to answer the
question whether and when the performance of mixed strategy EAs is better than
that of pure strategy EAs. In theory, the performance of EAs can be measured by
asymptotic convergence rate and asymptotic hitting time. In this paper, it is
proven that given a mixed strategy (1+1) EAs consisting of several mutation
operators, its performance (asymptotic convergence rate and asymptotic hitting
time)is not worse than that of the worst pure strategy (1+1) EA using one
mutation operator; if these mutation operators are mutually complementary, then
it is possible to design a mixed strategy (1+1) EA whose performance is better
than that of any pure strategy (1+1) EA using one mutation operator.
Deep Convolutional Ranking for Multilabel Image Annotation
Authors: Yunchao Gong, Yangqing Jia, Thomas Leung, Alexander Toshev, Sergey Ioffe
Date: 2013-12-17 00:00:00

Multilabel image annotation is one of the most important challenges in
computer vision with many real-world applications. While existing work usually
use conventional visual features for multilabel annotation, features based on
Deep Neural Networks have shown potential to significantly boost performance.
In this work, we propose to leverage the advantage of such features and analyze
key components that lead to better performances. Specifically, we show that a
significant performance gain could be obtained by combining convolutional
architectures with approximate top-$k$ ranking objectives, as thye naturally
fit the multilabel tagging problem. Our experiments on the NUS-WIDE dataset
outperforms the conventional visual features by about 10%, obtaining the best
reported performance in the literature.
Methods for Ordinal Peer Grading
Authors: Karthik Raman, Thorsten Joachims
Date: 2014-04-14 00:00:00

MOOCs have the potential to revolutionize higher education with their wide
outreach and accessibility, but they require instructors to come up with
scalable alternates to traditional student evaluation. Peer grading -- having
students assess each other -- is a promising approach to tackling the problem
of evaluation at scale, since the number of "graders" naturally scales with the
number of students. However, students are not trained in grading, which means
that one cannot expect the same level of grading skills as in traditional
settings. Drawing on broad evidence that ordinal feedback is easier to provide
and more reliable than cardinal feedback, it is therefore desirable to allow
peer graders to make ordinal statements (e.g. "project X is better than project
Y") and not require them to make cardinal statements (e.g. "project X is a
B-"). Thus, in this paper we study the problem of automatically inferring
student grades from ordinal peer feedback, as opposed to existing methods that
require cardinal peer feedback. We formulate the ordinal peer grading problem
as a type of rank aggregation problem, and explore several probabilistic models
under which to estimate student grades and grader reliability. We study the
applicability of these methods using peer grading data collected from a real
class -- with instructor and TA grades as a baseline -- and demonstrate the
efficacy of ordinal feedback techniques in comparison to existing cardinal peer
grading methods. Finally, we compare these peer-grading techniques to
traditional evaluation techniques.
Composite Self-Concordant Minimization
Authors: Quoc Tran-Dinh, Anastasios Kyrillidis, Volkan Cevher
Date: 2013-08-13 00:00:00

We propose a variable metric framework for minimizing the sum of a
self-concordant function and a possibly non-smooth convex function, endowed
with an easily computable proximal operator. We theoretically establish the
convergence of our framework without relying on the usual Lipschitz gradient
assumption on the smooth part. An important highlight of our work is a new set
of analytic step-size selection and correction procedures based on the
structure of the problem. We describe concrete algorithmic instances of our
framework for several interesting applications and demonstrate them numerically
on both synthetic and real data.
A Theoretical Assessment of Solution Quality in Evolutionary Algorithms for the Knapsack Problem
Authors: Jun He, Boris Mitavskiy, Yuren Zhou
Date: 2014-04-14 00:00:00
Tasks: Evolutionary Algorithms

Evolutionary algorithms are well suited for solving the knapsack problem.
Some empirical studies claim that evolutionary algorithms can produce good
solutions to the 0-1 knapsack problem. Nonetheless, few rigorous investigations
address the quality of solutions that evolutionary algorithms may produce for
the knapsack problem. The current paper focuses on a theoretical investigation
of three types of (N+1) evolutionary algorithms that exploit bitwise mutation,
truncation selection, plus different repair methods for the 0-1 knapsack
problem. It assesses the solution quality in terms of the approximation ratio.
Our work indicates that the solution produced by pure strategy and mixed
strategy evolutionary algorithms is arbitrarily bad. Nevertheless, the
evolutionary algorithm using helper objectives may produce 1/2-approximation
solutions to the 0-1 knapsack problem.
A Study on Stroke Rehabilitation through Task-Oriented Control of a Haptic Device via Near-Infrared Spectroscopy-Based BCI
Authors: Berdakh Abibullaev, Jinung An, Seung-Hyun Lee, Jeon-Il Moon
Date: 2013-08-19 00:00:00
Tasks: Brain Computer Interface, Classification, General Classification, Motor Imagery

This paper presents a study in task-oriented approach to stroke
rehabilitation by controlling a haptic device via near-infrared
spectroscopy-based brain-computer interface (BCI). The task is to command the
haptic device to move in opposing directions of leftward and rightward
movement. Our study consists of data acquisition, signal preprocessing, and
classification. In data acquisition, we conduct experiments based on two
different mental tasks: one on pure motor imagery, and another on combined
motor imagery and action observation. The experiments were conducted in both
offline and online modes. In the signal preprocessing, we use localization
method to eliminate channels that are irrelevant to the mental task, as well as
perform feature extraction for subsequent classification. We propose multiple
support vector machine classifiers with a majority-voting scheme for improved
classification results. And lastly, we present test results to demonstrate the
efficacy of our proposed approach to possible stroke rehabilitation practice.
Fast nonparametric clustering of structured time-series
Authors: James Hensman, Magnus Rattray, Neil D. Lawrence
Date: 2014-01-08 00:00:00
Tasks: Clustering, Nonparametric Clustering, Time Series, Time Series Analysis, Variational Inference

In this publication, we combine two Bayesian non-parametric models: the
Gaussian Process (GP) and the Dirichlet Process (DP). Our innovation in the GP
model is to introduce a variation on the GP prior which enables us to model
structured time-series data, i.e. data containing groups where we wish to model
inter- and intra-group variability. Our innovation in the DP model is an
implementation of a new fast collapsed variational inference procedure which
enables us to optimize our variationala pproximation significantly faster than
standard VB approaches. In a biological time series application we show how our
model better captures salient features of the data, leading to better
consistency with existing biological classifications, while the associated
inference algorithm provides a twofold speed-up over EM-based variational
inference.
Multi-digit Number Recognition from Street View Imagery using Deep Convolutional Neural Networks
Authors: Ian J. Goodfellow, Yaroslav Bulatov, Julian Ibarz, Sacha Arnoud, Vinay Shet
Date: 2013-12-20 00:00:00
Tasks: Image Classification

Recognizing arbitrary multi-character text in unconstrained natural
photographs is a hard problem. In this paper, we address an equally hard
sub-problem in this domain viz. recognizing arbitrary multi-digit numbers from
Street View imagery. Traditional approaches to solve this problem typically
separate out the localization, segmentation, and recognition steps. In this
paper we propose a unified approach that integrates these three steps via the
use of a deep convolutional neural network that operates directly on the image
pixels. We employ the DistBelief implementation of deep neural networks in
order to train large, distributed neural networks on high quality images. We
find that the performance of this approach increases with the depth of the
convolutional network, with the best performance occurring in the deepest
architecture we trained, with eleven hidden layers. We evaluate this approach
on the publicly available SVHN dataset and achieve over $96\%$ accuracy in
recognizing complete street numbers. We show that on a per-digit recognition
task, we improve upon the state-of-the-art, achieving $97.84\%$ accuracy. We
also evaluate this approach on an even more challenging dataset generated from
Street View imagery containing several tens of millions of street number
annotations and achieve over $90\%$ accuracy. To further explore the
applicability of the proposed system to broader text recognition tasks, we
apply it to synthetic distorted text from reCAPTCHA. reCAPTCHA is one of the
most secure reverse turing tests that uses distorted text to distinguish humans
from bots. We report a $99.8\%$ accuracy on the hardest category of reCAPTCHA.
Our evaluations on both tasks indicate that at specific operating thresholds,
the performance of the proposed system is comparable to, and in some cases
exceeds, that of human operators.
Anytime Hierarchical Clustering
Authors: Omur Arslan, Daniel E. Koditschek
Date: 2014-04-13 00:00:00
Tasks: Anomaly Detection, Clustering

We propose a new anytime hierarchical clustering method that iteratively
transforms an arbitrary initial hierarchy on the configuration of measurements
along a sequence of trees we prove for a fixed data set must terminate in a
chain of nested partitions that satisfies a natural homogeneity requirement.
Each recursive step re-edits the tree so as to improve a local measure of
cluster homogeneity that is compatible with a number of commonly used (e.g.,
single, average, complete) linkage functions. As an alternative to the standard
batch algorithms, we present numerical evidence to suggest that appropriate
adaptations of this method can yield decentralized, scalable algorithms
suitable for distributed/parallel computation of clustering hierarchies and
online tracking of clustering trees applicable to large, dynamically changing
databases and anomaly detection.
Active Learning for Undirected Graphical Model Selection
Authors: Divyanshu Vats, Robert D. Nowak, Richard G. Baraniuk
Date: 2014-04-13 00:00:00
Tasks: Active Learning, model, Model Selection

This paper studies graphical model selection, i.e., the problem of estimating
a graph of statistical relationships among a collection of random variables.
Conventional graphical model selection algorithms are passive, i.e., they
require all the measurements to have been collected before processing begins.
We propose an active learning algorithm that uses junction tree representations
to adapt future measurements based on the information gathered from prior
measurements. We prove that, under certain conditions, our active learning
algorithm requires fewer scalar measurements than any passive algorithm to
reliably estimate a graph. A range of numerical results validate our theory and
demonstrates the benefits of active learning.