pwc-archive/papers-with-abstracts huggingface dataset:
An efficient algorithm for learning with semi-bandit feedback
Authors: Gergely Neu, Gábor Bartók
Date: 2013-05-13 00:00:00
Tasks: Combinatorial Optimization

We consider the problem of online combinatorial optimization under
semi-bandit feedback. The goal of the learner is to sequentially select its
actions from a combinatorial decision set so as to minimize its cumulative
loss. We propose a learning algorithm for this problem based on combining the
Follow-the-Perturbed-Leader (FPL) prediction method with a novel loss
estimation procedure called Geometric Resampling (GR). Contrary to previous
solutions, the resulting algorithm can be efficiently implemented for any
decision set where efficient offline combinatorial optimization is possible at
all. Assuming that the elements of the decision set can be described with
d-dimensional binary vectors with at most m non-zero entries, we show that the
expected regret of our algorithm after T rounds is O(m sqrt(dT log d)). As a
side result, we also improve the best known regret bounds for FPL in the full
information setting to O(m^(3/2) sqrt(T log d)), gaining a factor of sqrt(d/m)
over previous bounds for this algorithm.
Generalized Neutrosophic Soft Set
Authors: Said Broumi
Date: 2013-05-13 00:00:00
Tasks: Decision Making

In this paper we present a new concept called generalized neutrosophic soft
set. This concept incorporates the beneficial properties of both generalized
neutrosophic set introduced by A.A. Salama [7]and soft set techniques proposed
by Molodtsov [4]. We also study some properties of this concept. Some
definitions and operations have been introduced on generalized neutrosophic
soft set. Finally we present an application of generalized neuutrosophic soft
set in decision making problem.
Automatic Parameter Adaptation for Multi-object Tracking
Authors: Duc Phu Chau, Monique Thonnat, François Bremond
Date: 2013-05-13 00:00:00
Tasks: General Classification, Multi-Object Tracking, Object, Object Tracking

Object tracking quality usually depends on video context (e.g. object
occlusion level, object density). In order to decrease this dependency, this
paper presents a learning approach to adapt the tracker parameters to the
context variations. In an offline phase, satisfactory tracking parameters are
learned for video context clusters. In the online control phase, once a context
change is detected, the tracking parameters are tuned using the learned values.
The experimental results show that the proposed approach outperforms the recent
trackers in state of the art. This paper brings two contributions: (1) a
classification method of video sequences to learn offline tracking parameters,
(2) a new method to tune online tracking parameters using tracking context.
A study for the effect of the Emphaticness and language and dialect for Voice Onset Time (VOT) in Modern Standard Arabic (MSA)
Authors: Sulaiman S. AlDahri
Date: 2013-05-13 00:00:00

The signal sound contains many different features, including Voice Onset Time
(VOT), which is a very important feature of stop sounds in many languages. The
only application of VOT values is stopping phoneme subsets. This subset of
consonant sounds is stop phonemes exist in the Arabic language, and in fact,
all languages. The pronunciation of these sounds is hard and unique especially
for less-educated Arabs and non-native Arabic speakers. VOT can be utilized by
the human auditory system to distinguish between voiced and unvoiced stops such
as /p/ and /b/ in English.This search focuses on computing and analyzing VOT of
Modern Standard Arabic (MSA), within the Arabic language, for all pairs of
non-emphatic (namely, /d/ and /t/) and emphatic pairs (namely, /d?/ and /t?/)
depending on carrier words. This research uses a database built by ourselves,
and uses the carrier words syllable structure: CV-CV-CV. One of the main
outcomes always found is the emphatic sounds (/d?/, /t?/) are less than 50% of
non-emphatic (counter-part) sounds ( /d/, /t/).Also, VOT can be used to
classify or detect for a dialect ina language.
Mean field variational Bayesian inference for support vector machine classification
Authors: Jan Luts, John T. Ormerod
Date: 2013-05-13 00:00:00
Tasks: Bayesian Inference, Classification, General Classification, Variable Selection

A mean field variational Bayes approach to support vector machines (SVMs)
using the latent variable representation on Polson & Scott (2012) is presented.
This representation allows circumvention of many of the shortcomings associated
with classical SVMs including automatic penalty parameter selection, the
ability to handle dependent samples, missing data and variable selection. We
demonstrate on simulated and real datasets that our approach is easily
extendable to non-standard situations and outperforms the classical SVM
approach whilst remaining computationally efficient.
Boosting with the Logistic Loss is Consistent
Authors: Matus Telgarsky
Date: 2013-05-13 00:00:00
Tasks: Generalization Bounds

This manuscript provides optimization guarantees, generalization bounds, and
statistical consistency results for AdaBoost variants which replace the
exponential loss with the logistic and similar losses (specifically, twice
differentiable convex losses which are Lipschitz and tend to zero on one side).
  The heart of the analysis is to show that, in lieu of explicit regularization
and constraints, the structure of the problem is fairly rigidly controlled by
the source distribution itself. The first control of this type is in the
separable case, where a distribution-dependent relaxed weak learning rate
induces speedy convergence with high probability over any sample. Otherwise, in
the nonseparable case, the convex surrogate risk itself exhibits
distribution-dependent levels of curvature, and consequently the algorithm's
output has small norm with high probability.
Identifying Pairs in Simulated Bio-Medical Time-Series
Authors: Uri Kartoun
Date: 2013-05-12 00:00:00
Tasks: Classification, General Classification, Time Series, Time Series Analysis

The paper presents a time-series-based classification approach to identify
similarities in pairs of simulated human-generated patterns. An example for a
pattern is a time-series representing a heart rate during a specific
time-range, wherein the time-series is a sequence of data points that represent
the changes in the heart rate values. A bio-medical simulator system was
developed to acquire a collection of 7,871 price patterns of financial
instruments. The financial instruments traded in real-time on three American
stock exchanges, NASDAQ, NYSE, and AMEX, simulate bio-medical measurements. The
system simulates a human in which each price pattern represents one bio-medical
sensor. Data provided during trading hours from the stock exchanges allowed
real-time classification. Classification is based on new machine learning
techniques: self-labeling, which allows the application of supervised learning
methods on unlabeled time-series and similarity ranking, which applied on a
decision tree learning algorithm to classify time-series regardless of type and
quantity.
Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
Authors: Shai Shalev-Shwartz, Tong Zhang
Date: 2013-05-12 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: BIG-bench Machine Learning

Stochastic dual coordinate ascent (SDCA) is an effective technique for
solving regularized loss minimization problems in machine learning. This paper
considers an extension of SDCA under the mini-batch setting that is often used
in practice. Our main contribution is to introduce an accelerated mini-batch
version of SDCA and prove a fast convergence rate for this method. We discuss
an implementation of our method over a parallel computing system, and compare
the results to both the vanilla stochastic dual coordinate ascent and to the
accelerated deterministic gradient descent method of
\cite{nesterov2007gradient}.
Strategic Planning for Network Data Analysis
Authors: Kartik Talamadupula, Octavian Udrea, Anton Riabov, Anand Ranganathan
Date: 2013-05-12 00:00:00
Tasks: Malware Detection

As network traffic monitoring software for cybersecurity, malware detection,
and other critical tasks becomes increasingly automated, the rate of alerts and
supporting data gathered, as well as the complexity of the underlying model,
regularly exceed human processing capabilities. Many of these applications
require complex models and constituent rules in order to come up with decisions
that influence the operation of entire systems. In this paper, we motivate the
novel "strategic planning" problem -- one of gathering data from the world and
applying the underlying model of the domain in order to come up with decisions
that will monitor the system in an automated manner. We describe our use of
automated planning methods to this problem, including the technique that we
used to solve it in a manner that would scale to the demands of a real-time,
real world scenario. We then present a PDDL model of one such application
scenario related to network administration and monitoring, followed by a
description of a novel integrated system that was built to accept generated
plans and to continue the execution process. Finally, we present evaluations of
two different automated planners and their different capabilities with our
integrated system, both on a six-month window of network data, and using a
simulator.
Learning Policies for Contextual Submodular Prediction
Authors: Stephane Ross, Jiaji Zhou, Yisong Yue, Debadeepta Dey, J. Andrew Bagnell
Date: 2013-05-11 00:00:00
Tasks: Diversity, Document Summarization, News Recommendation, Prediction, Trajectory Prediction

Many prediction domains, such as ad placement, recommendation, trajectory
prediction, and document summarization, require predicting a set or list of
options. Such lists are often evaluated using submodular reward functions that
measure both quality and diversity. We propose a simple, efficient, and
provably near-optimal approach to optimizing such prediction problems based on
no-regret learning. Our method leverages a surprising result from online
submodular optimization: a single no-regret online learner can compete with an
optimal sequence of predictions. Compared to previous work, which either learn
a sequence of classifiers or rely on stronger assumptions such as
realizability, we ensure both data-efficiency as well as performance guarantees
in the fully agnostic setting. Experiments validate the efficiency and
applicability of the approach on a wide range of problems including manipulator
trajectory optimization, news recommendation and document summarization.
On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions
Authors: Purushottam Kar, Bharath K. Sriperumbudur, Prateek Jain, Harish C Karnick
Date: 2013-05-11 00:00:00
Tasks: Generalization Bounds, Metric Learning

In this paper, we study the generalization properties of online learning
based stochastic methods for supervised learning problems where the loss
function is dependent on more than one training sample (e.g., metric learning,
ranking). We present a generic decoupling technique that enables us to provide
Rademacher complexity-based generalization error bounds. Our bounds are in
general tighter than those obtained by Wang et al (COLT 2012) for the same
problem. Using our decoupling technique, we are further able to obtain fast
convergence rates for strongly convex pairwise loss functions. We are also able
to analyze a class of memory efficient online learning algorithms for pairwise
learning problems that use only a bounded subset of past training samples to
update the hypothesis at each step. Finally, in order to complement our
generalization bounds, we propose a novel memory efficient online learning
algorithm for higher order learning problems with bounded regret guarantees.
Geiringer Theorems: From Population Genetics to Computational Intelligence, Memory Evolutive Systems and Hebbian Learning
Authors: Boris Mitavskiy, Elio Tuci, Chris Cannings, Jonathan Rowe, Jun He
Date: 2013-05-11 00:00:00
Tasks: Evolutionary Algorithms, Reinforcement Learning

The classical Geiringer theorem addresses the limiting frequency of
occurrence of various alleles after repeated application of crossover. It has
been adopted to the setting of evolutionary algorithms and, a lot more
recently, reinforcement learning and Monte-Carlo tree search methodology to
cope with a rather challenging question of action evaluation at the chance
nodes. The theorem motivates novel dynamic parallel algorithms that are
explicitly described in the current paper for the first time. The algorithms
involve independent agents traversing a dynamically constructed directed graph
that possibly has loops. A rather elegant and profound category-theoretic model
of cognition in biological neural networks developed by a well-known French
mathematician, professor Andree Ehresmann jointly with a neurosurgeon, Jan Paul
Vanbremeersch over the last thirty years provides a hint at the connection
between such algorithms and Hebbian learning.
Two SVDs produce more focal deep learning representations
Authors: Hinrich Schuetze, Christian Scheible
Date: 2013-01-16 00:00:00
Tasks: Deep Learning, Domain Adaptation, Vocal Bursts Valence Prediction

A key characteristic of work on deep learning and neural networks in general
is that it relies on representations of the input that support generalization,
robust inference, domain adaptation and other desirable functionalities. Much
recent progress in the field has focused on efficient and effective methods for
computing representations. In this paper, we propose an alternative method that
is more efficient than prior work and produces representations that have a
property we call focality -- a property we hypothesize to be important for
neural network representations. The method consists of a simple application of
two consecutive SVDs and is inspired by Anandkumar (2012).
A Further Generalization of the Finite-Population Geiringer-like Theorem for POMDPs to Allow Recombination Over Arbitrary Set Covers
Authors: Boris Mitavskiy, Jun He
Date: 2013-05-11 00:00:00
Tasks: Relation

A popular current research trend deals with expanding the Monte-Carlo tree
search sampling methodologies to the environments with uncertainty and
incomplete information. Recently a finite population version of Geiringer
theorem with nonhomologous recombination has been adopted to the setting of
Monte-Carlo tree search to cope with randomness and incomplete information by
exploiting the entrinsic similarities within the state space of the problem.
The only limitation of the new theorem is that the similarity relation was
assumed to be an equivalence relation on the set of states. In the current
paper we lift this "curtain of limitation" by allowing the similarity relation
to be modeled in terms of an arbitrary set cover of the set of state-action
pairs.
Affine Invariant Divergences associated with Composite Scores and its Applications
Authors: Takafumi Kanamori, Hironori Fujisawa
Date: 2013-05-11 00:00:00
Tasks: parameter estimation

In statistical analysis, measuring a score of predictive performance is an
important task. In many scientific fields, appropriate scores were tailored to
tackle the problems at hand. A proper score is a popular tool to obtain
statistically consistent forecasts. Furthermore, a mathematical
characterization of the proper score was studied. As a result, it was revealed
that the proper score corresponds to a Bregman divergence, which is an
extension of the squared distance over the set of probability distributions. In
the present paper, we introduce composite scores as an extension of the typical
scores in order to obtain a wider class of probabilistic forecasting. Then, we
propose a class of composite scores, named Holder scores, that induce
equivariant estimators. The equivariant estimators have a favorable property,
implying that the estimator is transformed in a consistent way, when the data
is transformed. In particular, we deal with the affine transformation of the
data. By using the equivariant estimators under the affine transformation, one
can obtain estimators that do no essentially depend on the choice of the system
of units in the measurement. Conversely, we prove that the Holder score is
characterized by the invariance property under the affine transformations.
Furthermore, we investigate statistical properties of the estimators using
Holder scores for the statistical problems including estimation of regression
functions and robust parameter estimation, and illustrate the usefulness of the
newly introduced scores for statistical forecasting.
Stochastic Collapsed Variational Bayesian Inference for Latent Dirichlet Allocation
Authors: James Foulds, Levi Boyles, Christopher DuBois, Padhraic Smyth, Max Welling
Date: 2013-05-10 00:00:00
Tasks: Bayesian Inference, Topic Models, Variational Inference

In the internet era there has been an explosion in the amount of digital text
information available, leading to difficulties of scale for traditional
inference algorithms for topic models. Recent advances in stochastic
variational inference algorithms for latent Dirichlet allocation (LDA) have
made it feasible to learn topic models on large-scale corpora, but these
methods do not currently take full advantage of the collapsed representation of
the model. We propose a stochastic algorithm for collapsed variational Bayesian
inference for LDA, which is simpler and more efficient than the state of the
art method. We show connections between collapsed variational Bayesian
inference and MAP estimation for LDA, and leverage these connections to prove
convergence properties of the proposed algorithm. In experiments on large-scale
text corpora, the algorithm was found to converge faster and often to a better
solution than the previous method. Human-subject experiments also demonstrated
that the method can learn coherent topics in seconds on small corpora,
facilitating the use of topic models in interactive document analysis software.
MARFCAT: Transitioning to Binary and Larger Data Sets of SATE IV
Authors: Serguei A. Mokhov, Joey Paquet, Mourad Debbabi, Yankui Sun
Date: 2012-07-16 00:00:00
Tasks: BIG-bench Machine Learning

We present a second iteration of a machine learning approach to static code
analysis and fingerprinting for weaknesses related to security, software
engineering, and others using the open-source MARF framework and the MARFCAT
application based on it for the NIST's SATE IV static analysis tool exposition
workshop's data sets that include additional test cases, including new large
synthetic cases. To aid detection of weak or vulnerable code, including source
or binary on different platforms the machine learning approach proved to be
fast and accurate to for such tasks where other tools are either much slower or
have much smaller recall of known vulnerabilities. We use signal and NLP
processing techniques in our approach to accomplish the identification and
classification tasks. MARFCAT's design from the beginning in 2010 made is
independent of the language being analyzed, source code, bytecode, or binary.
In this follow up work with explore some preliminary results in this area. We
evaluated also additional algorithms that were used to process the data.
Towards a theory of good SAT representations
Authors: Matthew Gwynne, Oliver Kullmann
Date: 2013-02-18 00:00:00
Tasks: ARC

We aim at providing a foundation of a theory of "good" SAT representations F
of boolean functions f. We argue that the hierarchy UC_k of unit-refutation
complete clause-sets of level k, introduced by the authors, provides the most
basic target classes, that is, F in UC_k is to be achieved for k as small as
feasible. If F does not contain new variables, i.e., F is equivalent (as a CNF)
to f, then F in UC_1 is similar to "achieving (generalised) arc consistency"
known from the literature (it is somewhat weaker, but theoretically much nicer
to handle). We show that for polysize representations of boolean functions in
this sense, the hierarchy UC_k is strict. The boolean functions for these
separations are "doped" minimally unsatisfiable clause-sets of deficiency 1;
these functions have been introduced in [Sloan, Soerenyi, Turan, 2007], and we
generalise their construction and show a correspondence to a strengthened
notion of irredundant sub-clause-sets. Turning from lower bounds to upper
bounds, we believe that many common CNF representations fit into the UC_k
scheme, and we give some basic tools to construct representations in UC_1 with
new variables, based on the Tseitin translation. Note that regarding new
variables the UC_1-representations are stronger than mere "arc consistency",
since the new variables are not excluded from consideration.
Shape Reconstruction and Recognition with Isolated Non-directional Cues
Authors: Toshiro Kubota, Jessica Ranck, Briley Acker, Herman De Haan
Date: 2013-05-10 00:00:00

The paper investigates a hypothesis that our visual system groups visual cues
based on how they form a surface, or more specifically triangulation derived
from the visual cues. To test our hypothesis, we compare shape recognition with
three different representations of visual cues: a set of isolated dots
delineating the outline of the shape, a set of triangles obtained from Delaunay
triangulation of the set of dots, and a subset of Delaunay triangles excluding
those outside of the shape. Each participant was assigned to one particular
representation type and increased the number of dots (and consequentially
triangles) until the underlying shape could be identified. We compare the
average number of dots needed for identification among three types of
representations. Our hypothesis predicts that the results from the three
representations will be similar. However, they show statistically significant
differences. The paper also presents triangulation based algorithms for
reconstruction and recognition of a shape from a set of isolated dots.
Experiments showed that the algorithms were more effective and perceptually
agreeable than similar contour based ones. From these experiments, we conclude
that triangulation does affect our shape recognition. However, the surface
based approach presents a number of computational advantages over the contour
based one and should be studied further.