pwc-archive/papers-with-abstracts huggingface dataset:
Convex Relaxations of SE(2) and SE(3) for Visual Pose Estimation
Authors: Matanya B. Horowitz, Nikolai Matni, Joel W. Burdick
Date: 2014-01-15 00:00:00
Tasks: Pose Estimation

This paper proposes a new method for rigid body pose estimation based on
spectrahedral representations of the tautological orbitopes of $SE(2)$ and
$SE(3)$. The approach can use dense point cloud data from stereo vision or an
RGB-D sensor (such as the Microsoft Kinect), as well as visual appearance data.
The method is a convex relaxation of the classical pose estimation problem, and
is based on explicit linear matrix inequality (LMI) representations for the
convex hulls of $SE(2)$ and $SE(3)$. Given these representations, the relaxed
pose estimation problem can be framed as a robust least squares problem with
the optimization variable constrained to these convex sets. Although this
formulation is a relaxation of the original problem, numerical experiments
indicate that it is indeed exact - i.e. its solution is a member of $SE(2)$ or
$SE(3)$ - in many interesting settings. We additionally show that this method
is guaranteed to be exact for a large class of pose estimation problems.
Causal Discovery with Continuous Additive Noise Models
Authors: Jonas Peters, Joris Mooij, Dominik Janzing, Bernhard Schölkopf
Date: 2013-09-26 00:00:00
Tasks: Causal Discovery, regression

We consider the problem of learning causal directed acyclic graphs from an
observational joint distribution. One can use these graphs to predict the
outcome of interventional experiments, from which data are often not available.
We show that if the observational distribution follows a structural equation
model with an additive noise structure, the directed acyclic graph becomes
identifiable from the distribution under mild conditions. This constitutes an
interesting alternative to traditional methods that assume faithfulness and
identify only the Markov equivalence class of the graph, thus leaving some
edges undirected. We provide practical algorithms for finitely many samples,
RESIT (Regression with Subsequent Independence Test) and two methods based on
an independence score. We prove that RESIT is correct in the population setting
and provide an empirical evaluation.
Sparse Coding: A Deep Learning using Unlabeled Data for High - Level Representation
Authors: R. Vidya, Dr. G. M. Nasira, R. P. Jaia Priyankka
Date: 2014-04-06 00:00:00
Tasks: Deep Learning

Sparse coding algorithm is an learning algorithm mainly for unsupervised
feature for finding succinct, a little above high - level Representation of
inputs, and it has successfully given a way for Deep learning. Our objective is
to use High - Level Representation data in form of unlabeled category to help
unsupervised learning task. when compared with labeled data, unlabeled data is
easier to acquire because, unlike labeled data it does not follow some
particular class labels. This really makes the Deep learning wider and
applicable to practical problems and learning. The main problem with sparse
coding is it uses Quadratic loss function and Gaussian noise mode. So, its
performs is very poor when binary or integer value or other Non- Gaussian type
data is applied. Thus first we propose an algorithm for solving the L1 -
regularized convex optimization algorithm for the problem to allow High - Level
Representation of unlabeled data. Through this we derive a optimal solution for
describing an approach to Deep learning algorithm by using sparse code.
Nearly Optimal Minimax Tree Search?
Authors: Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin
Date: 2014-04-05 00:00:00

Knuth and Moore presented a theoretical lower bound on the number of leaves
that any fixed-depth minimax tree-search algorithm traversing a uniform tree
must explore, the so-called minimal tree. Since real-life minimax trees are not
uniform, the exact size of this tree is not known for most applications.
Further, most games have transpositions, implying that there exists a minimal
graph which is smaller than the minimal tree. For three games (chess, Othello
and checkers) we compute the size of the minimal tree and the minimal graph.
Empirical evidence shows that in all three games, enhanced Alpha-Beta search is
capable of building a tree that is close in size to that of the minimal graph.
Hence, it appears game-playing programs build nearly optimal search trees.
However, the conventional definition of the minimal graph is wrong. There are
ways in which the size of the minimal graph can be reduced: by maximizing the
number of transpositions in the search, and generating cutoffs using branches
that lead to smaller search trees. The conventional definition of the minimal
graph is just a left-most approximation. Calculating the size of the real
minimal graph is too computationally intensive. However, upper bound
approximations show it to be significantly smaller than the left-most minimal
graph. Hence, it appears that game-playing programs are not searching as
efficiently as is widely believed. Understanding the left-most and real minimal
search graphs leads to some new ideas for enhancing Alpha-Beta search. One of
them, enhanced transposition cutoffs, is shown to significantly reduce search
tree size.
SSS* = Alpha-Beta + TT
Authors: Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin
Date: 2014-04-05 00:00:00

In 1979 Stockman introduced the SSS* minimax search algorithm that domi-
nates Alpha-Beta in the number of leaf nodes expanded. Further investigation of
the algorithm showed that it had three serious drawbacks, which prevented its
use by practitioners: it is difficult to understand, it has large memory
requirements, and it is slow. This paper presents an alternate formulation of
SSS*, in which it is implemented as a series of Alpha-Beta calls that use a
transposition table (AB- SSS*). The reformulation solves all three perceived
drawbacks of SSS*, making it a practical algorithm. Further, because the search
is now based on Alpha-Beta, the extensive research on minimax search
enhancements can be easily integrated into AB-SSS*. To test AB-SSS* in
practise, it has been implemented in three state-of-the- art programs: for
checkers, Othello and chess. AB-SSS* is comparable in performance to Alpha-Beta
on leaf node count in all three games, making it a viable alternative to
Alpha-Beta in practise. Whereas SSS* has usually been regarded as being
entirely different from Alpha-Beta, it turns out to be just an Alpha-Beta
enhancement, like null-window searching. This runs counter to published
simulation results. Our research leads to the surprising result that iterative
deepening versions of Alpha-Beta can expand fewer leaf nodes than iterative
deepening versions of SSS* due to dynamic move re-ordering.
A New Paradigm for Minimax Search
Authors: Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin
Date: 2014-04-05 00:00:00

This paper introduces a new paradigm for minimax game-tree search algo-
rithms. MT is a memory-enhanced version of Pearls Test procedure. By changing
the way MT is called, a number of best-first game-tree search algorithms can be
simply and elegantly constructed (including SSS*). Most of the assessments of
minimax search algorithms have been based on simulations. However, these
simulations generally do not address two of the key ingredients of high
performance game-playing programs: iterative deepening and memory usage. This
paper presents experimental data from three game-playing programs (checkers,
Othello and chess), covering the range from low to high branching factor. The
improved move ordering due to iterative deepening and memory usage results in
significantly different results from those portrayed in the literature. Whereas
some simulations show Alpha-Beta expanding almost 100% more leaf nodes than
other algorithms [12], our results showed variations of less than 20%. One new
instance of our framework (MTD-f) out-performs our best alpha- beta searcher
(aspiration NegaScout) on leaf nodes, total nodes and execution time. To our
knowledge, these are the first reported results that compare both depth-first
and best-first algorithms given the same amount of memory
Text Based Approach For Indexing And Retrieval Of Image And Video: A Review
Authors: Avinash N Bhute, B. B. Meshram
Date: 2014-04-05 00:00:00
Tasks: Retrieval

Text data present in multimedia contain useful information for automatic
annotation, indexing. Extracted information used for recognition of the overlay
or scene text from a given video or image. The Extracted text can be used for
retrieving the videos and images. In this paper, firstly, we are discussed the
different techniques for text extraction from images and videos. Secondly, we
are reviewed the techniques for indexing and retrieval of image and videos by
using extracted text.
MTD(f), A Minimax Algorithm Faster Than NegaScout
Authors: Aske Plaat
Date: 2014-04-05 00:00:00

MTD(f) is a new minimax search algorithm, simpler and more efficient than
previous algorithms. In tests with a number of tournament game playing programs
for chess, checkers and Othello it performed better, on average, than
NegaScout/PVS (the AlphaBeta variant used in practically all good chess,
checkers, and Othello programs). One of the strongest chess programs of the
moment, MIT's parallel chess program Cilkchess uses MTD(f) as its search
algorithm, replacing NegaScout, which was used in StarSocrates, the previous
version of the program.
A Compression Technique for Analyzing Disagreement-Based Active Learning
Authors: Yair Wiener, Steve Hanneke, Ran El-Yaniv
Date: 2014-04-05 00:00:00
Tasks: Active Learning

We introduce a new and improved characterization of the label complexity of
disagreement-based active learning, in which the leading quantity is the
version space compression set size. This quantity is defined as the size of the
smallest subset of the training data that induces the same version space. We
show various applications of the new characterization, including a tight
analysis of CAL and refined label complexity bounds for linear separators under
mixtures of Gaussians and axis-aligned rectangles under product densities. The
version space compression set size, as well as the new characterization of the
label complexity, can be naturally extended to agnostic learning problems, for
which we show new speedup results for two well known active learning
algorithms.
Ensemble Committees for Stock Return Classification and Prediction
Authors: James Brofos
Date: 2014-04-05 00:00:00
Tasks: Binary Classification, Classification, General Classification, Prediction, Time Series, Time Series Analysis

This paper considers a portfolio trading strategy formulated by algorithms in
the field of machine learning. The profitability of the strategy is measured by
the algorithm's capability to consistently and accurately identify stock
indices with positive or negative returns, and to generate a preferred
portfolio allocation on the basis of a learned model. Stocks are characterized
by time series data sets consisting of technical variables that reflect market
conditions in a previous time interval, which are utilized produce binary
classification decisions in subsequent intervals. The learned model is
constructed as a committee of random forest classifiers, a non-linear support
vector machine classifier, a relevance vector machine classifier, and a
constituent ensemble of k-nearest neighbors classifiers. The Global Industry
Classification Standard (GICS) is used to explore the ensemble model's efficacy
within the context of various fields of investment including Energy, Materials,
Financials, and Information Technology. Data from 2006 to 2012, inclusive, are
considered, which are chosen for providing a range of market circumstances for
evaluating the model. The model is observed to achieve an accuracy of
approximately 70% when predicting stock price returns three months in advance.
Sharpened Error Bounds for Random Sampling Based $\ell_2$ Regression
Authors: Shusen Wang
Date: 2014-03-30 00:00:00
Tasks: regression

Given a data matrix $X \in R^{n\times d}$ and a response vector $y \in
R^{n}$, suppose $n>d$, it costs $O(n d^2)$ time and $O(n d)$ space to solve the
least squares regression (LSR) problem. When $n$ and $d$ are both large,
exactly solving the LSR problem is very expensive. When $n \gg d$, one feasible
approach to speeding up LSR is to randomly embed $y$ and all columns of $X$
into a smaller subspace $R^c$; the induced LSR problem has the same number of
columns but much fewer number of rows, and it can be solved in $O(c d^2)$ time
and $O(c d)$ space.
  We discuss in this paper two random sampling based methods for solving LSR
more efficiently. Previous work showed that the leverage scores based sampling
based LSR achieves $1+\epsilon$ accuracy when $c \geq O(d \epsilon^{-2} \log
d)$. In this paper we sharpen this error bound, showing that $c = O(d \log d +
d \epsilon^{-1})$ is enough for achieving $1+\epsilon$ accuracy. We also show
that when $c \geq O(\mu d \epsilon^{-2} \log d)$, the uniform sampling based
LSR attains a $2+\epsilon$ bound with positive probability.
The Fast Cauchy Transform and Faster Robust Linear Regression
Authors: Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff
Date: 2012-07-19 00:00:00
Tasks: regression

We provide fast algorithms for overconstrained $\ell_p$ regression and
related problems: for an $n\times d$ input matrix $A$ and vector
$b\in\mathbb{R}^n$, in $O(nd\log n)$ time we reduce the problem
$\min_{x\in\mathbb{R}^d} \|Ax-b\|_p$ to the same problem with input matrix
$\tilde A$ of dimension $s \times d$ and corresponding $\tilde b$ of dimension
$s\times 1$. Here, $\tilde A$ and $\tilde b$ are a coreset for the problem,
consisting of sampled and rescaled rows of $A$ and $b$; and $s$ is independent
of $n$ and polynomial in $d$. Our results improve on the best previous
algorithms when $n\gg d$, for all $p\in[1,\infty)$ except $p=2$. We also
provide a suite of improved results for finding well-conditioned bases via
ellipsoidal rounding, illustrating tradeoffs between running time and
conditioning quality, including a one-pass conditioning algorithm for general
$\ell_p$ problems.
  We also provide an empirical evaluation of implementations of our algorithms
for $p=1$, comparing them with related algorithms. Our empirical results show
that, in the asymptotic regime, the theory is a very good guide to the
practical performance of these algorithms. Our algorithms use our faster
constructions of well-conditioned bases for $\ell_p$ spaces and, for $p=1$, a
fast subspace embedding of independent interest that we call the Fast Cauchy
Transform: a distribution over matrices $\Pi:\mathbb{R}^n\mapsto
\mathbb{R}^{O(d\log d)}$, found obliviously to $A$, that approximately
preserves the $\ell_1$ norms: that is, with large probability, simultaneously
for all $x$, $\|Ax\|_1 \approx \|\Pi Ax\|_1$, with distortion $O(d^{2+\eta})$,
for an arbitrarily small constant $\eta>0$; and, moreover, $\Pi A$ can be
computed in $O(nd\log d)$ time. The techniques underlying our Fast Cauchy
Transform include fast Johnson-Lindenstrauss transforms, low-coherence
matrices, and rescaling by Cauchy random variables.
Beyond the quantum formalism: consequences of a neural-oscillator model to quantum cognition
Authors: J. Acacio de Barros
Date: 2013-09-15 00:00:00

In this paper we present a neural oscillator model of stimulus response
theory that exhibits quantum-like behavior. We then show that without adding
any additional assumptions, a quantum model constructed to fit observable
pairwise correlations has no predictive power over the unknown triple moment,
obtainable through the activation of multiple oscillators. We compare this with
the results obtained in de Barros (2013), where a criteria of rationality gives
optimal ranges for the triple moment.
Implementing Anti-Unification Modulo Equational Theory
Authors: Jochen Burghardt, Birgit Heinz
Date: 2014-04-01 00:00:00
Tasks: LEMMA

We present an implementation of E-anti-unification as defined in Heinz
(1995), where tree-grammar descriptions of equivalence classes of terms are
used to compute generalizations modulo equational theories. We discuss several
improvements, including an efficient implementation of variable-restricted
E-anti-unification from Heinz (1995), and give some runtime figures about them.
We present applications in various areas, including lemma generation in
equational inductive proofs, intelligence tests, diverging Knuth-Bendix
completion, strengthening of induction hypotheses, and theory formation about
finite algebras.
TACT: A Transfer Actor-Critic Learning Framework for Energy Saving in Cellular Radio Access Networks
Authors: Rongpeng Li, Zhifeng Zhao, Xianfu Chen, Jacques Palicot, Honggang Zhang
Date: 2012-11-28 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Recent works have validated the possibility of improving energy efficiency in
radio access networks (RANs), achieved by dynamically turning on/off some base
stations (BSs). In this paper, we extend the research over BS switching
operations, which should match up with traffic load variations. Instead of
depending on the dynamic traffic loads which are still quite challenging to
precisely forecast, we firstly formulate the traffic variations as a Markov
decision process. Afterwards, in order to foresightedly minimize the energy
consumption of RANs, we design a reinforcement learning framework based BS
switching operation scheme. Furthermore, to avoid the underlying curse of
dimensionality in reinforcement learning, a transfer actor-critic algorithm
(TACT), which utilizes the transferred learning expertise in historical periods
or neighboring regions, is proposed and provably converges. In the end, we
evaluate our proposed scheme by extensive simulations under various practical
configurations and show that the proposed TACT algorithm contributes to a
performance jumpstart and demonstrates the feasibility of significant energy
efficiency improvement at the expense of tolerable delay performance.
AIS-MACA- Z: MACA based Clonal Classifier for Splicing Site, Protein Coding and Promoter Region Identification in Eukaryotes
Authors: Pokkuluri Kiran Sree, Inampudi Ramesh Babu, SSSN Usha Devi N
Date: 2014-04-04 00:00:00

Bioinformatics incorporates information regarding biological data storage,
accessing mechanisms and presentation of characteristics within this data. Most
of the problems in bioinformatics and be addressed efficiently by computer
techniques. This paper aims at building a classifier based on Multiple
Attractor Cellular Automata (MACA) which uses fuzzy logic with version Z to
predict splicing site, protein coding and promoter region identification in
eukaryotes. It is strengthened with an artificial immune system technique
(AIS), Clonal algorithm for choosing rules of best fitness. The proposed
classifier can handle DNA sequences of lengths 54,108,162,252,354. This
classifier gives the exact boundaries of both protein and promoter regions with
an average accuracy of 90.6%. This classifier can predict the splicing site
with 97% accuracy. This classifier was tested with 1, 97,000 data components
which were taken from Fickett & Toung , EPDnew, and other sequences from a
renowned medical university.
Resolving Multi-path Interference in Time-of-Flight Imaging via Modulation Frequency Diversity and Sparse Regularization
Authors: Ayush Bhandari, Achuta Kadambi, Refael Whyte, Christopher Barsi, Micha Feigin, Adrian Dorrington, Ramesh Raskar
Date: 2014-04-03 00:00:00
Tasks: Diversity, Transparent objects

Time-of-flight (ToF) cameras calculate depth maps by reconstructing phase
shifts of amplitude-modulated signals. For broad illumination or transparent
objects, reflections from multiple scene points can illuminate a given pixel,
giving rise to an erroneous depth map. We report here a sparsity regularized
solution that separates K-interfering components using multiple modulation
frequency measurements. The method maps ToF imaging to the general framework of
spectral estimation theory and has applications in improving depth profiles and
exploiting multiple scattering.
Attribute-Efficient Evolvability of Linear Functions
Authors: Elaine Angelino, Varun Kanade
Date: 2013-09-16 00:00:00
Tasks: Attribute, Evolutionary Algorithms

In a seminal paper, Valiant (2006) introduced a computational model for
evolution to address the question of complexity that can arise through
Darwinian mechanisms. Valiant views evolution as a restricted form of
computational learning, where the goal is to evolve a hypothesis that is close
to the ideal function. Feldman (2008) showed that (correlational) statistical
query learning algorithms could be framed as evolutionary mechanisms in
Valiant's model. P. Valiant (2012) considered evolvability of real-valued
functions and also showed that weak-optimization algorithms that use
weak-evaluation oracles could be converted to evolutionary mechanisms.
  In this work, we focus on the complexity of representations of evolutionary
mechanisms. In general, the reductions of Feldman and P. Valiant may result in
intermediate representations that are arbitrarily complex (polynomial-sized
circuits). We argue that biological constraints often dictate that the
representations have low complexity, such as constant depth and fan-in
circuits. We give mechanisms for evolving sparse linear functions under a large
class of smooth distributions. These evolutionary algorithms are
attribute-efficient in the sense that the size of the representations and the
number of generations required depend only on the sparsity of the target
function and the accuracy parameter, but have no dependence on the total number
of attributes.
A Tutorial on Principal Component Analysis
Authors: Jonathon Shlens
Date: 2014-04-03 00:00:00

Principal component analysis (PCA) is a mainstay of modern data analysis - a
black box that is widely used but (sometimes) poorly understood. The goal of
this paper is to dispel the magic behind this black box. This manuscript
focuses on building a solid intuition for how and why principal component
analysis works. This manuscript crystallizes this knowledge by deriving from
simple intuitions, the mathematics behind PCA. This tutorial does not shy away
from explaining the ideas informally, nor does it shy away from the
mathematics. The hope is that by addressing both aspects, readers of all levels
will be able to gain a better understanding of PCA as well as the when, the how
and the why of applying this technique.
Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation
Authors: Dong Xia
Date: 2014-03-25 00:00:00

In this paper, we consider low rank matrix estimation using either
matrix-version Dantzig Selector $\hat{A}_{\lambda}^d$ or matrix-version LASSO
estimator $\hat{A}_{\lambda}^L$. We consider sub-Gaussian measurements, $i.e.$,
the measurements $X_1,\ldots,X_n\in\mathbb{R}^{m\times m}$ have $i.i.d.$
sub-Gaussian entries. Suppose $\textrm{rank}(A_0)=r$. We proved that, when
$n\geq Cm[r^2\vee r\log(m)\log(n)]$ for some $C>0$, both $\hat{A}_{\lambda}^d$
and $\hat{A}_{\lambda}^L$ can obtain optimal upper bounds(except some
logarithmic terms) for estimation accuracy under spectral norm. By applying
metric entropy of Grassmann manifolds, we construct (near) matching minimax
lower bound for estimation accuracy under spectral norm. We also give upper
bounds and matching minimax lower bound(except some logarithmic terms) for
estimation accuracy under Schatten-q norm for every $1\leq q\leq\infty$. As a
direct corollary, we show both upper bounds and minimax lower bounds of
estimation accuracy under Ky-Fan-k norms for every $1\leq k\leq m$.