pwc-archive/papers-with-abstracts huggingface dataset:
Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty for Separable Convex Programs in Machine Learning
Authors: Zhouchen Lin, Risheng Liu, Huan Li
Date: 2013-10-18 00:00:00
Tasks: Distributed Computing, parameter estimation

Many problems in machine learning and other fields can be (re)for-mulated as
linearly constrained separable convex programs. In most of the cases, there are
multiple blocks of variables. However, the traditional alternating direction
method (ADM) and its linearized version (LADM, obtained by linearizing the
quadratic penalty term) are for the two-block case and cannot be naively
generalized to solve the multi-block case. So there is great demand on
extending the ADM based methods for the multi-block case. In this paper, we
propose LADM with parallel splitting and adaptive penalty (LADMPSAP) to solve
multi-block separable convex programs efficiently. When all the component
objective functions have bounded subgradients, we obtain convergence results
that are stronger than those of ADM and LADM, e.g., allowing the penalty
parameter to be unbounded and proving the sufficient and necessary conditions}
for global convergence. We further propose a simple optimality measure and
reveal the convergence rate of LADMPSAP in an ergodic sense. For programs with
extra convex set constraints, with refined parameter estimation we devise a
practical version of LADMPSAP for faster convergence. Finally, we generalize
LADMPSAP to handle programs with more difficult objective functions by
linearizing part of the objective function as well. LADMPSAP is particularly
suitable for sparse representation and low-rank recovery problems because its
subproblems have closed form solutions and the sparsity and low-rankness of the
iterates can be preserved during the iteration. It is also highly
parallelizable and hence fits for parallel or distributed computing. Numerical
experiments testify to the advantages of LADMPSAP in speed and numerical
accuracy.
BayesOpt: A Bayesian Optimization Library for Nonlinear Optimization, Experimental Design and Bandits
Authors: Ruben Martinez-Cantin
Date: 2014-05-29 00:00:00
Tasks: Bayesian Optimization, Experimental Design, Hyperparameter Optimization

BayesOpt is a library with state-of-the-art Bayesian optimization methods to
solve nonlinear optimization, stochastic bandits or sequential experimental
design problems. Bayesian optimization is sample efficient by building a
posterior distribution to capture the evidence and prior knowledge for the
target function. Built in standard C++, the library is extremely efficient
while being portable and flexible. It includes a common interface for C, C++,
Python, Matlab and Octave.
A Comparison of Nature Inspired Algorithms for Multi-threshold Image Segmentation
Authors: Valentín Osuna-Enciso, Erik Cuevas, Humberto Sossa
Date: 2014-05-28 00:00:00
Tasks: Image Segmentation, Segmentation, Semantic Segmentation

In the field of image analysis, segmentation is one of the most important
preprocessing steps. One way to achieve segmentation is by mean of threshold
selection, where each pixel that belongs to a determined class islabeled
according to the selected threshold, giving as a result pixel groups that share
visual characteristics in the image. Several methods have been proposed in
order to solve threshold selectionproblems; in this work, it is used the method
based on the mixture of Gaussian functions to approximate the 1D histogram of a
gray level image and whose parameters are calculated using three nature
inspired algorithms (Particle Swarm Optimization, Artificial Bee Colony
Optimization and Differential Evolution). Each Gaussian function approximates
thehistogram, representing a pixel class and therefore a threshold point.
Experimental results are shown, comparing in quantitative and qualitative
fashion as well as the main advantages and drawbacks of each algorithm, applied
to multi-threshold problem.
An HMM Based Named Entity Recognition System for Indian Languages: The JU System at ICON 2013
Authors: Vivekananda Gayen, Kamal Sarkar
Date: 2014-05-28 00:00:00
Tasks: named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER)

This paper reports about our work in the ICON 2013 NLP TOOLS CONTEST on Named
Entity Recognition. We submitted runs for Bengali, English, Hindi, Marathi,
Punjabi, Tamil and Telugu. A statistical HMM (Hidden Markov Models) based model
has been used to implement our system. The system has been trained and tested
on the NLP TOOLS CONTEST: ICON 2013 datasets. Our system obtains F-measures of
0.8599, 0.7704, 0.7520, 0.4289, 0.5455, 0.4466, and 0.4003 for Bengali,
English, Hindi, Marathi, Punjabi, Tamil and Telugu respectively.
Seeing What You're Told: Sentence-Guided Activity Recognition In Video
Authors: N. Siddharth, Andrei Barbu, Jeffrey Mark Siskind
Date: 2013-08-19 00:00:00
Proceeding: CVPR 2014 6
Tasks: Action Recognition, Activity Recognition, Sentence, Temporal Action Localization

We present a system that demonstrates how the compositional structure of
events, in concert with the compositional structure of language, can interplay
with the underlying focusing mechanisms in video action recognition, thereby
providing a medium, not only for top-down and bottom-up integration, but also
for multi-modal integration between vision and language. We show how the roles
played by participants (nouns), their characteristics (adjectives), the actions
performed (verbs), the manner of such actions (adverbs), and changing spatial
relations between participants (prepositions) in the form of whole sentential
descriptions mediated by a grammar, guides the activity-recognition process.
Further, the utility and expressiveness of our framework is demonstrated by
performing three separate tasks in the domain of multi-activity videos:
sentence-guided focus of attention, generation of sentential descriptions of
video, and query-based video search, simply by leveraging the framework in
different manners.
Circle detection using Discrete Differential Evolution Optimization
Authors: Erik Cuevas, Daniel Zaldivar, Marco Perez, Marte Ramirez
Date: 2014-05-28 00:00:00

This paper introduces a circle detection method based on Differential
Evolution (DE) optimization. Just as circle detection has been lately
considered as a fundamental component for many computer vision algorithms, DE
has evolved as a successful heuristic method for solving complex optimization
problems, still keeping a simple structure and an easy implementation. It has
also shown advantageous convergence properties and remarkable robustness. The
detection process is considered similar to a combinational optimization
problem. The algorithm uses the combination of three edge points as parameters
to determine circles candidates in the scene yielding a reduction of the search
space. The objective function determines if some circle candidates are actually
present in the image. This paper focuses particularly on one DE-based algorithm
known as the Discrete Differential Evolution (DDE), which eventually has shown
better results than the original DE in particular for solving combinatorial
problems. In the DDE, suitable conversion routines are incorporated into the
DE, aiming to operate from integer values to real values and then getting
integer values back, following the crossover operation. The final algorithm is
a fast circle detector that locates circles with sub-pixel accuracy even
considering complicated conditions and noisy images. Experimental results on
several synthetic and natural images with varying range of complexity validate
the efficiency of the proposed technique considering accuracy, speed, and
robustness.
Adaptive Feature Ranking for Unsupervised Transfer Learning
Authors: Son N. Tran, Artur d'Avila Garcez
Date: 2013-12-21 00:00:00
Tasks: Transfer Learning

Transfer Learning is concerned with the application of knowledge gained from
solving a problem to a different but related problem domain. In this paper, we
propose a method and efficient algorithm for ranking and selecting
representations from a Restricted Boltzmann Machine trained on a source domain
to be transferred onto a target domain. Experiments carried out using the
MNIST, ICDAR and TiCC image datasets show that the proposed adaptive feature
ranking and transfer learning method offers statistically significant
improvements on the training of RBMs. Our method is general in that the
knowledge chosen by the ranking function does not depend on its relation to any
specific target domain, and it works with unsupervised learning and
knowledge-based transfer.
Reconstructing Native Language Typology from Foreign Language Usage
Authors: Yevgeni Berzak, Roi Reichart, Boris Katz
Date: 2014-04-25 00:00:00
Proceeding: WS 2014 6

Linguists and psychologists have long been studying cross-linguistic
transfer, the influence of native language properties on linguistic performance
in a foreign language. In this work we provide empirical evidence for this
process in the form of a strong correlation between language similarities
derived from structural features in English as Second Language (ESL) texts and
equivalent similarities obtained from the typological features of the native
languages. We leverage this finding to recover native language typological
similarity structure directly from ESL text, and perform prediction of
typological features in an unsupervised fashion with respect to the target
languages. Our method achieves 72.2% accuracy on the typology prediction task,
a result that is highly competitive with equivalent methods that rely on
typological resources.
On the cost-complexity of multi-context systems
Authors: Peter Novák, Cees Witteveen
Date: 2014-05-28 00:00:00

Multi-context systems provide a powerful framework for modelling
information-aggregation systems featuring heterogeneous reasoning components.
Their execution can, however, incur non-negligible cost. Here, we focus on
cost-complexity of such systems. To that end, we introduce cost-aware
multi-context systems, an extension of non-monotonic multi-context systems
framework taking into account costs incurred by execution of semantic operators
of the individual contexts. We formulate the notion of cost-complexity for
consistency and reasoning problems in MCSs. Subsequently, we provide a series
of results related to gradually more and more constrained classes of MCSs and
finally introduce an incremental cost-reducing algorithm solving the reasoning
problem for definite MCSs.
Seeking multi-thresholds for image segmentation with Learning Automata
Authors: Erik Cuevas, Daniel Zaldivar, Marco Perez
Date: 2014-05-28 00:00:00
Tasks: Image Segmentation, parameter estimation, Semantic Segmentation

This paper explores the use of the Learning Automata (LA) algorithm to
compute threshold selection for image segmentation as it is a critical
preprocessing step for image analysis, pattern recognition and computer vision.
LA is a heuristic method which is able to solve complex optimization problems
with interesting results in parameter estimation. Despite other techniques
commonly seek through the parameter map, LA explores in the probability space
providing appropriate convergence properties and robustness. The segmentation
task is therefore considered as an optimization problem and the LA is used to
generate the image multi-threshold separation. In this approach, one 1D
histogram of a given image is approximated through a Gaussian mixture model
whose parameters are calculated using the LA algorithm. Each Gaussian function
approximating the histogram represents a pixel class and therefore a threshold
point. The method shows fast convergence avoiding the typical sensitivity to
initial conditions such as the Expectation Maximization (EM) algorithm or the
complex time-consuming computations commonly found in gradient methods.
Experimental results demonstrate the algorithm ability to perform automatic
multi-threshold selection and show interesting advantages as it is compared to
other algorithms solving the same task.
Circle detection by Harmony Search Optimization
Authors: Erik Cuevas, Noe Ortega, Daniel Zaldivar, Marco Perez
Date: 2014-05-28 00:00:00

Automatic circle detection in digital images has received considerable
attention over the last years in computer vision as several efforts have aimed
for an optimal circle detector. This paper presents an algorithm for automatic
detection of circular shapes that considers the overall process as an
optimization problem. The approach is based on the Harmony Search Algorithm
(HSA), a derivative free meta-heuristic optimization algorithm inspired by
musicians while improvising new harmonies. The algorithm uses the encoding of
three points as candidate circles (harmonies) over the edge-only image. An
objective function evaluates (harmony quality) if such candidate circles are
actually present in the edge image. Guided by the values of this objective
function, the set of encoded candidate circles are evolved using the HSA so
that they can fit to the actual circles on the edge map of the image (optimal
harmony). Experimental results from several tests on synthetic and natural
images with a varying complexity range have been included to validate the
efficiency of the proposed technique regarding accuracy, speed and robustness.
Machine Learner for Automated Reasoning 0.4 and 0.5
Authors: Cezary Kaliszyk, Josef Urban, Jiří Vyskočil
Date: 2014-02-11 00:00:00
Tasks: Automated Theorem Proving

Machine Learner for Automated Reasoning (MaLARea) is a learning and reasoning
system for proving in large formal libraries where thousands of theorems are
available when attacking a new conjecture, and a large number of related
problems and proofs can be used to learn specific theorem-proving knowledge.
The last version of the system has by a large margin won the 2013 CASC LTB
competition. This paper describes the motivation behind the methods used in
MaLARea, discusses the general approach and the issues arising in evaluation of
such system, and describes the Mizar@Turing100 and CASC'24 versions of MaLARea.
A Multi-threshold Segmentation Approach Based on Artificial Bee Colony Optimization
Authors: Erik Cuevas, Felipe Sencion, Daniel Zaldivar, Marco Perez, Humberto Sossa
Date: 2014-05-28 00:00:00
Tasks: Image Segmentation, Semantic Segmentation

This paper explores the use of the Artificial Bee Colony (ABC) algorithm to
compute threshold selection for image segmentation. ABC is a heuristic
algorithm motivated by the intelligent behavior of honey-bees which has been
successfully employed to solve complex optimization problems. In this approach,
an image 1D histogram is approximated through a Gaussian mixture model whose
parameters are calculated by the ABC algorithm. For the approximation scheme,
each Gaussian function represents a pixel class and therefore a threshold.
Unlike the Expectation Maximization (EM) algorithm, the ABC based method shows
fast convergence and low sensitivity to initial conditions. Remarkably, it also
improves complex time consuming computations commonly required by
gradient-based methods. Experimental results demonstrate the algorithms ability
to perform automatic multi threshold selection yet showing interesting
advantages by comparison to other well known algorithms.
BliStr: The Blind Strategymaker
Authors: Josef Urban
Date: 2013-01-12 00:00:00

BliStr is a system that automatically develops strategies for E prover on a
large set of problems. The main idea is to interleave (i) iterated
low-timelimit local search for new strategies on small sets of similar easy
problems with (ii) higher-timelimit evaluation of the new strategies on all
problems. The accumulated results of the global higher-timelimit runs are used
to define and evolve the notion of "similar easy problems", and to control the
selection of the next strategy to be improved. The technique was used to
significantly strengthen the set of E strategies used by the MaLARea, PS-E,
E-MaLeS, and E systems in the CASC@Turing 2012 competition, particularly in the
Mizar division. Similar improvement was obtained on the problems created from
the Flyspeck corpus.
The Computational Impact of Partial Votes on Strategic Voting
Authors: Nina Narodytska, Toby Walsh
Date: 2014-05-28 00:00:00

In many real world elections, agents are not required to rank all candidates.
We study three of the most common methods used to modify voting rules to deal
with such partial votes. These methods modify scoring rules (like the Borda
count), elimination style rules (like single transferable vote) and rules based
on the tournament graph (like Copeland) respectively. We argue that with an
elimination style voting rule like single transferable vote, partial voting
does not change the situations where strategic voting is possible. However,
with scoring rules and rules based on the tournament graph, partial voting can
increase the situations where strategic voting is possible. As a consequence,
the computational complexity of computing a strategic vote can change. For
example, with Borda count, the complexity of computing a strategic vote can
decrease or stay the same depending on how we score partial votes.
The PeerRank Method for Peer Assessment
Authors: Toby Walsh
Date: 2014-05-28 00:00:00

We propose the PeerRank method for peer assessment. This constructs a grade
for an agent based on the grades proposed by the agents evaluating the agent.
Since the grade of an agent is a measure of their ability to grade correctly,
the PeerRank method weights grades by the grades of the grading agent. The
PeerRank method also provides an incentive for agents to grade correctly. As
the grades of an agent depend on the grades of the grading agents, and as these
grades themselves depend on the grades of other agents, we define the PeerRank
method by a fixed point equation similar to the PageRank method for ranking
web-pages. We identify some formal properties of the PeerRank method (for
example, it satisfies axioms of unanimity, no dummy, no discrimination and
symmetry), discuss some examples, compare with related work and evaluate the
performance on some synthetic data. Our results show considerable promise,
reducing the error in grade predictions by a factor of 2 or more in many cases
over the natural baseline of averaging peer grades.
On the saddle point problem for non-convex optimization
Authors: Razvan Pascanu, Yann N. Dauphin, Surya Ganguli, Yoshua Bengio
Date: 2014-05-19 00:00:00

A central challenge to many fields of science and engineering involves
minimizing non-convex error functions over continuous, high dimensional spaces.
Gradient descent or quasi-Newton methods are almost ubiquitously used to
perform such minimizations, and it is often thought that a main source of
difficulty for the ability of these local methods to find the global minimum is
the proliferation of local minima with much higher error than the global
minimum. Here we argue, based on results from statistical physics, random
matrix theory, and neural network theory, that a deeper and more profound
difficulty originates from the proliferation of saddle points, not local
minima, especially in high dimensional problems of practical interest. Such
saddle points are surrounded by high error plateaus that can dramatically slow
down learning, and give the illusory impression of the existence of a local
minimum. Motivated by these arguments, we propose a new algorithm, the
saddle-free Newton method, that can rapidly escape high dimensional saddle
points, unlike gradient descent and quasi-Newton methods. We apply this
algorithm to deep neural network training, and provide preliminary numerical
evidence for its superior performance.
Layered Logic Classifiers: Exploring the `And' and `Or' Relations
Authors: Zhuowen Tu, Piotr Dollar, Ying-Nian Wu
Date: 2014-05-27 00:00:00
Tasks: Pedestrian Detection, Semantic Segmentation

Designing effective and efficient classifier for pattern analysis is a key
problem in machine learning and computer vision. Many the solutions to the
problem require to perform logic operations such as `and', `or', and `not'.
Classification and regression tree (CART) include these operations explicitly.
Other methods such as neural networks, SVM, and boosting learn/compute a
weighted sum on features (weak classifiers), which weakly perform the 'and' and
'or' operations. However, it is hard for these classifiers to deal with the
'xor' pattern directly. In this paper, we propose layered logic classifiers for
patterns of complicated distributions by combining the `and', `or', and `not'
operations. The proposed algorithm is very general and easy to implement. We
test the classifiers on several typical datasets from the Irvine repository and
two challenging vision applications, object segmentation and pedestrian
detection. We observe significant improvements on all the datasets over the
widely used decision stump based AdaBoost algorithm. The resulting classifiers
have much less training complexity than decision tree based AdaBoost, and can
be applied in a wide range of domains.
Learning Coverage Functions and Private Release of Marginals
Authors: Vitaly Feldman, Pravesh Kothari
Date: 2013-04-08 00:00:00

We study the problem of approximating and learning coverage functions. A
function $c: 2^{[n]} \rightarrow \mathbf{R}^{+}$ is a coverage function, if
there exists a universe $U$ with non-negative weights $w(u)$ for each $u \in U$
and subsets $A_1, A_2, \ldots, A_n$ of $U$ such that $c(S) = \sum_{u \in
\cup_{i \in S} A_i} w(u)$. Alternatively, coverage functions can be described
as non-negative linear combinations of monotone disjunctions. They are a
natural subclass of submodular functions and arise in a number of applications.
  We give an algorithm that for any $\gamma,\delta>0$, given random and uniform
examples of an unknown coverage function $c$, finds a function $h$ that
approximates $c$ within factor $1+\gamma$ on all but $\delta$-fraction of the
points in time $poly(n,1/\gamma,1/\delta)$. This is the first fully-polynomial
algorithm for learning an interesting class of functions in the demanding PMAC
model of Balcan and Harvey (2011). Our algorithms are based on several new
structural properties of coverage functions. Using the results in (Feldman and
Kothari, 2014), we also show that coverage functions are learnable agnostically
with excess $\ell_1$-error $\epsilon$ over all product and symmetric
distributions in time $n^{\log(1/\epsilon)}$. In contrast, we show that,
without assumptions on the distribution, learning coverage functions is at
least as hard as learning polynomial-size disjoint DNF formulas, a class of
functions for which the best known algorithm runs in time
$2^{\tilde{O}(n^{1/3})}$ (Klivans and Servedio, 2004).
  As an application of our learning results, we give simple
differentially-private algorithms for releasing monotone conjunction counting
queries with low average error. In particular, for any $k \leq n$, we obtain
private release of $k$-way marginals with average error $\bar{\alpha}$ in time
$n^{O(\log(1/\bar{\alpha}))}$.