pwc-archive/papers-with-abstracts huggingface dataset:
Budgeted Batch Bayesian Optimization With Unknown Batch Sizes
Authors: Vu Nguyen, Santu Rana, Sunil Gupta, Cheng Li, Svetha Venkatesh
Date: 2017-03-15 00:00:00
Tasks: Bayesian Optimization, BIG-bench Machine Learning, Experimental Design, global-optimization

Parameter settings profoundly impact the performance of machine learning
algorithms and laboratory experiments. The classical grid search or trial-error
methods are exponentially expensive in large parameter spaces, and Bayesian
optimization (BO) offers an elegant alternative for global optimization of
black box functions. In situations where the black box function can be
evaluated at multiple points simultaneously, batch Bayesian optimization is
used. Current batch BO approaches are restrictive in that they fix the number
of evaluations per batch, and this can be wasteful when the number of specified
evaluations is larger than the number of real maxima in the underlying
acquisition function. We present the Budgeted Batch Bayesian Optimization (B3O)
for hyper-parameter tuning and experimental design - we identify the
appropriate batch size for each iteration in an elegant way. To set the batch
size flexible, we use the infinite Gaussian mixture model (IGMM) for
automatically identifying the number of peaks in the underlying acquisition
functions. We solve the intractability of estimating the IGMM directly from the
acquisition function by formulating the batch generalized slice sampling to
efficiently draw samples from the acquisition function. We perform extensive
experiments for both synthetic functions and two real world applications -
machine learning hyper-parameter tuning and experimental design for alloy
hardening. We show empirically that the proposed B3O outperforms the existing
fixed batch BO approaches in finding the optimum whilst requiring a fewer
number of evaluations, thus saving cost and time.
Optimization for Large-Scale Machine Learning with Distributed Features and Observations
Authors: Alexandros Nathan, Diego Klabjan
Date: 2016-10-31 00:00:00
Tasks: BIG-bench Machine Learning, Distributed Computing, Distributed Optimization

As the size of modern data sets exceeds the disk and memory capacities of a
single computer, machine learning practitioners have resorted to parallel and
distributed computing. Given that optimization is one of the pillars of machine
learning and predictive modeling, distributed optimization methods have
recently garnered ample attention in the literature. Although previous research
has mostly focused on settings where either the observations, or features of
the problem at hand are stored in distributed fashion, the situation where both
are partitioned across the nodes of a computer cluster (doubly distributed) has
barely been studied. In this work we propose two doubly distributed
optimization algorithms. The first one falls under the umbrella of distributed
dual coordinate ascent methods, while the second one belongs to the class of
stochastic gradient/coordinate descent hybrid methods. We conduct numerical
experiments in Spark using real-world and simulated data sets and study the
scaling properties of our methods. Our empirical evaluation of the proposed
algorithms demonstrates the out-performance of a block distributed ADMM method,
which, to the best of our knowledge is the only other existing doubly
distributed optimization algorithm.
Founded Semantics and Constraint Semantics of Logic Rules
Authors: Yanhong A. Liu, Scott D. Stoller
Date: 2016-06-20 00:00:00
Tasks: Negation

Logic rules and inference are fundamental in computer science and have been studied extensively. However, prior semantics of logic languages can have subtle implications and can disagree significantly, on even very simple programs, including in attempting to solve the well-known Russell's paradox. These semantics are often non-intuitive and hard-to-understand when unrestricted negation is used in recursion. This paper describes a simple new semantics for logic rules, founded semantics, and its straightforward extension to another simple new semantics, constraint semantics, that unify the core of different prior semantics. The new semantics support unrestricted negation, as well as unrestricted existential and universal quantifications. They are uniquely expressive and intuitive by allowing assumptions about the predicates, rules, and reasoning to be specified explicitly, as simple and precise binary choices. They are completely declarative and relate cleanly to prior semantics. In addition, founded semantics can be computed in linear time in the size of the ground program.
An Analysis of Deep Neural Network Models for Practical Applications
Authors: Alfredo Canziani, Adam Paszke, Eugenio Culurciello
Date: 2016-05-24 00:00:00

Since the emergence of Deep Neural Networks (DNNs) as a prominent technique
in the field of computer vision, the ImageNet classification challenge has
played a major role in advancing the state-of-the-art. While accuracy figures
have steadily increased, the resource utilisation of winning models has not
been properly taken into account. In this work, we present a comprehensive
analysis of important metrics in practical applications: accuracy, memory
footprint, parameters, operations count, inference time and power consumption.
Key findings are: (1) power consumption is independent of batch size and
architecture; (2) accuracy and inference time are in a hyperbolic relationship;
(3) energy constraint is an upper bound on the maximum achievable accuracy and
model complexity; (4) the number of operations is a reliable estimate of the
inference time. We believe our analysis provides a compelling set of
information that helps design and engineer efficient DNNs.
On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
Authors: Max Simchowitz, Ahmed El Alaoui, Benjamin Recht
Date: 2017-04-14 00:00:00

We prove a \emph{query complexity} lower bound on rank-one principal
component analysis (PCA). We consider an oracle model where, given a symmetric
matrix $M \in \mathbb{R}^{d \times d}$, an algorithm is allowed to make $T$
\emph{exact} queries of the form $w^{(i)} = Mv^{(i)}$ for $i \in
\{1,\dots,T\}$, where $v^{(i)}$ is drawn from a distribution which depends
arbitrarily on the past queries and measurements $\{v^{(j)},w^{(j)}\}_{1 \le j
\le i-1}$. We show that for a small constant $\epsilon$, any adaptive,
randomized algorithm which can find a unit vector $\widehat{v}$ for which
$\widehat{v}^{\top}M\widehat{v} \ge (1-\epsilon)\|M\|$, with even small
probability, must make $T = \Omega(\log d)$ queries. In addition to settling a
widely-held folk conjecture, this bound demonstrates a fundamental gap between
convex optimization and "strict-saddle" non-convex optimization of which PCA is
a canonical example: in the former, first-order methods can have dimension-free
iteration complexity, whereas in PCA, the iteration complexity of
gradient-based methods must necessarily grow with the dimension. Our argument
proceeds via a reduction to estimating the rank-one spike in a deformed Wigner
model. We establish lower bounds for this model by developing a "truncated"
analogue of the $\chi^2$ Bayes-risk lower bound of Chen et al.
Hierarchic Kernel Recursive Least-Squares
Authors: Hossein Mohamadipanah, Mahdi Heydari, Girish Chowdhary
Date: 2017-04-14 00:00:00

We present a new kernel-based algorithm for modeling evenly distributed multidimensional datasets that does not rely on input space sparsification. The presented method reorganizes the typical single-layer kernel-based model into a deep hierarchical structure, such that the weights of a kernel model over each dimension are modeled over its adjacent dimension. We show that modeling weights in the suggested structure leads to significant computational speedup and improved modeling accuracy.
Translation of Patent Sentences with a Large Vocabulary of Technical Terms Using Neural Machine Translation
Authors: Zi Long, Takehito Utsuro, Tomoharu Mitsuhashi, Mikio Yamamoto
Date: 2017-04-14 00:00:00
Proceeding: WS 2016 12
Tasks: Decoder, Machine Translation, NMT, Translation

Neural machine translation (NMT), a new approach to machine translation, has
achieved promising results comparable to those of traditional approaches such
as statistical machine translation (SMT). Despite its recent success, NMT
cannot handle a larger vocabulary because training complexity and decoding
complexity proportionally increase with the number of target words. This
problem becomes even more serious when translating patent documents, which
contain many technical terms that are observed infrequently. In NMTs, words
that are out of vocabulary are represented by a single unknown token. In this
paper, we propose a method that enables NMT to translate patent sentences
comprising a large vocabulary of technical terms. We train an NMT system on
bilingual data wherein technical terms are replaced with technical term tokens;
this allows it to translate most of the source sentences except technical
terms. Further, we use it as a decoder to translate source sentences with
technical term tokens and replace the tokens with technical term translations
using SMT. We also use it to rerank the 1,000-best SMT translations on the
basis of the average of the SMT score and that of the NMT rescoring of the
translated sentences with technical term tokens. Our experiments on
Japanese-Chinese patent sentences show that the proposed NMT system achieves a
substantial improvement of up to 3.1 BLEU points and 2.3 RIBES points over
traditional SMT systems and an improvement of approximately 0.6 BLEU points and
0.8 RIBES points over an equivalent NMT system without our proposed technique.
Temporal Tessellation: A Unified Approach for Video Analysis
Authors: Dotan Kaufman, Gil Levi, Tal Hassner, Lior Wolf
Date: 2016-12-21 00:00:00
Proceeding: ICCV 2017 10
Tasks: Action Detection, Video Captioning, Video Summarization, Video Understanding

We present a general approach to video understanding, inspired by semantic
transfer techniques that have been successfully used for 2D image analysis. Our
method considers a video to be a 1D sequence of clips, each one associated with
its own semantics. The nature of these semantics -- natural language captions
or other labels -- depends on the task at hand. A test video is processed by
forming correspondences between its clips and the clips of reference videos
with known semantics, following which, reference semantics can be transferred
to the test video. We describe two matching methods, both designed to ensure
that (a) reference clips appear similar to test clips and (b), taken together,
the semantics of the selected reference clips is consistent and maintains
temporal coherence. We use our method for video captioning on the LSMDC'16
benchmark, video summarization on the SumMe and TVSum benchmarks, Temporal
Action Detection on the Thumos2014 benchmark, and sound prediction on the
Greatest Hits benchmark. Our method not only surpasses the state of the art, in
four out of five benchmarks, but importantly, it is the only single method we
know of that was successfully applied to such a diverse range of tasks.
ShapeWorld - A new test methodology for multimodal language understanding
Authors: Alexander Kuhnle, Ann Copestake
Date: 2017-04-14 00:00:00
Tasks: Multimodal Deep Learning, Visual Question Answering, Visual Question Answering (VQA)

We introduce a novel framework for evaluating multimodal deep learning models
with respect to their language understanding and generalization abilities. In
this approach, artificial data is automatically generated according to the
experimenter's specifications. The content of the data, both during training
and evaluation, can be controlled in detail, which enables tasks to be created
that require true generalization abilities, in particular the combination of
previously introduced concepts in novel ways. We demonstrate the potential of
our methodology by evaluating various visual question answering models on four
different tasks, and show how our framework gives us detailed insights into
their capabilities and limitations. By open-sourcing our framework, we hope to
stimulate progress in the field of multimodal language understanding.
Interpretable 3D Human Action Analysis with Temporal Convolutional Networks
Authors: Tae Soo Kim, Austin Reiter
Date: 2017-04-14 00:00:00
Tasks: 3D Action Recognition, Action Analysis, Action Recognition, Activity Recognition, Multimodal Activity Recognition, Skeleton Based Action Recognition, Temporal Action Localization

The discriminative power of modern deep learning models for 3D human action
recognition is growing ever so potent. In conjunction with the recent
resurgence of 3D human action representation with 3D skeletons, the quality and
the pace of recent progress have been significant. However, the inner workings
of state-of-the-art learning based methods in 3D human action recognition still
remain mostly black-box. In this work, we propose to use a new class of models
known as Temporal Convolutional Neural Networks (TCN) for 3D human action
recognition. Compared to popular LSTM-based Recurrent Neural Network models,
given interpretable input such as 3D skeletons, TCN provides us a way to
explicitly learn readily interpretable spatio-temporal representations for 3D
human action recognition. We provide our strategy in re-designing the TCN with
interpretability in mind and how such characteristics of the model is leveraged
to construct a powerful 3D activity recognition method. Through this work, we
wish to take a step towards a spatio-temporal model that is easier to
understand, explain and interpret. The resulting model, Res-TCN, achieves
state-of-the-art results on the largest 3D human action recognition dataset,
NTU-RGBD.
A Proof of Orthogonal Double Machine Learning with $Z$-Estimators
Authors: Vasilis Syrgkanis
Date: 2017-04-12 00:00:00
Tasks: BIG-bench Machine Learning

We consider two stage estimation with a non-parametric first stage and a
generalized method of moments second stage, in a simpler setting than
(Chernozhukov et al. 2016). We give an alternative proof of the theorem given
in (Chernozhukov et al. 2016) that orthogonal second stage moments, sample
splitting and $n^{1/4}$-consistency of the first stage, imply
$\sqrt{n}$-consistency and asymptotic normality of second stage estimates. Our
proof is for a variant of their estimator, which is based on the empirical
version of the moment condition (Z-estimator), rather than a minimization of a
norm of the empirical vector of moments (M-estimator). This note is meant
primarily for expository purposes, rather than as a new technical contribution.
Towards Accurate Multi-person Pose Estimation in the Wild
Authors: George Papandreou, Tyler Zhu, Nori Kanazawa, Alexander Toshev, Jonathan Tompson, Chris Bregler, Kevin Murphy
Date: 2017-01-06 00:00:00
Proceeding: CVPR 2017 7
Tasks: Human Detection, Keypoint Detection, Multi-Person Pose Estimation, Pose Estimation

We propose a method for multi-person detection and 2-D pose estimation that
achieves state-of-art results on the challenging COCO keypoints task. It is a
simple, yet powerful, top-down approach consisting of two stages.
  In the first stage, we predict the location and scale of boxes which are
likely to contain people; for this we use the Faster RCNN detector. In the
second stage, we estimate the keypoints of the person potentially contained in
each proposed bounding box. For each keypoint type we predict dense heatmaps
and offsets using a fully convolutional ResNet. To combine these outputs we
introduce a novel aggregation procedure to obtain highly localized keypoint
predictions. We also use a novel form of keypoint-based Non-Maximum-Suppression
(NMS), instead of the cruder box-level NMS, and a novel form of keypoint-based
confidence score estimation, instead of box-level scoring.
  Trained on COCO data alone, our final system achieves average precision of
0.649 on the COCO test-dev set and the 0.643 test-standard sets, outperforming
the winner of the 2016 COCO keypoints challenge and other recent state-of-art.
Further, by using additional in-house labeled data we obtain an even higher
average precision of 0.685 on the test-dev set and 0.673 on the test-standard
set, more than 5% absolute improvement compared to the previous best performing
method on the same dataset.
Decision trees unearth return sign correlation in the S&P 500
Authors: Lucas Fievet, Didier Sornette
Date: 2016-10-12 00:00:00

Technical trading rules and linear regressive models are often used by
practitioners to find trends in financial data. However, these models are
unsuited to find non-linearly separable patterns. We propose a decision tree
forecasting model that has the flexibility to capture arbitrary patterns. To
illustrate, we construct a binary Markov process with a deterministic component
that cannot be predicted with an autoregressive process. A simulation study
confirms the robustness of the trees and limitation of the autoregressive
model. Finally, adjusting for multiple testing, we show that some tree based
strategies achieve trading performance significant at the 99% confidence level
on the S&P 500 over the past 20 years. The best strategy breaks even with the
buy-and-hold strategy at 21 bps in transaction costs per round trip. A
four-factor regression analysis shows significant intercept and correlation
with the market. The return anomalies are strongest during the bursts of the
dotcom bubble, financial crisis, and European debt crisis. The correlation of
the return signs during these periods confirms the theoretical model.
Deep Structured Learning for Facial Action Unit Intensity Estimation
Authors: Robert Walecki, Ognjen, Rudovic, Vladimir Pavlovic, Björn Schuller, Maja Pantic
Date: 2017-04-14 00:00:00
Proceeding: CVPR 2017 7

We consider the task of automated estimation of facial expression intensity.
This involves estimation of multiple output variables (facial action units ---
AUs) that are structurally dependent. Their structure arises from statistically
induced co-occurrence patterns of AU intensity levels. Modeling this structure
is critical for improving the estimation performance; however, this performance
is bounded by the quality of the input features extracted from face images. The
goal of this paper is to model these structures and estimate complex feature
representations simultaneously by combining conditional random field (CRF)
encoded AU dependencies with deep learning. To this end, we propose a novel
Copula CNN deep learning approach for modeling multivariate ordinal variables.
Our model accounts for $ordinal$ structure in output variables and their
$non$-$linear$ dependencies via copula functions modeled as cliques of a CRF.
These are jointly optimized with deep CNN feature encoding layers using a newly
introduced balanced batch iterative training algorithm. We demonstrate the
effectiveness of our approach on the task of AU intensity estimation on two
benchmark datasets. We show that joint learning of the deep features and the
target output structure results in significant performance gains compared to
existing deep structured models for analysis of facial expressions.
iCaRL: Incremental Classifier and Representation Learning
Authors: Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, Christoph H. Lampert
Date: 2016-11-23 00:00:00
Proceeding: CVPR 2017 7
Tasks: class-incremental learning, Class Incremental Learning, Incremental Learning, Representation Learning

A major open problem on the road to artificial intelligence is the
development of incrementally learning systems that learn about more and more
concepts over time from a stream of data. In this work, we introduce a new
training strategy, iCaRL, that allows learning in such a class-incremental way:
only the training data for a small number of classes has to be present at the
same time and new classes can be added progressively. iCaRL learns strong
classifiers and a data representation simultaneously. This distinguishes it
from earlier works that were fundamentally limited to fixed data
representations and therefore incompatible with deep learning architectures. We
show by experiments on CIFAR-100 and ImageNet ILSVRC 2012 data that iCaRL can
learn many classes incrementally over a long period of time where other
strategies quickly fail.
Lean From Thy Neighbor: Stochastic & Adversarial Bandits in a Network
Authors: L. Elisa Celis, Farnood Salehi
Date: 2017-04-14 00:00:00
Tasks: Decision Making, Sociology

An individual's decisions are often guided by those of his or her peers,
i.e., neighbors in a social network. Presumably, being privy to the experiences
of others aids in learning and decision making, but how much advantage does an
individual gain by observing her neighbors? Such problems make appearances in
sociology and economics and, in this paper, we present a novel model to capture
such decision-making processes and appeal to the classical multi-armed bandit
framework to analyze it. Each individual, in addition to her own actions, can
observe the actions and rewards obtained by her neighbors, and can use all of
this information in order to minimize her own regret. We provide algorithms for
this setting, both for stochastic and adversarial bandits, and show that their
regret smoothly interpolates between the regret in the classical bandit setting
and that of the full-information setting as a function of the neighbors'
exploration. In the stochastic setting the additional information must simply
be incorporated into the usual estimation of the rewards, while in the
adversarial setting this is attained by constructing a new unbiased estimator
for the rewards and appropriately bounding the amount of additional information
provided by the neighbors. These algorithms are optimal up to log factors;
despite the fact that the agents act independently and selfishly, this implies
that it is an approximate Nash equilibria for all agents to use our algorithms.
Further, we show via empirical simulations that our algorithms, often
significantly, outperform existing algorithms that one could apply to this
setting.
On Generalized Bellman Equations and Temporal-Difference Learning
Authors: Huizhen Yu, A. Rupam Mahmood, Richard S. Sutton
Date: 2017-04-14 00:00:00

We consider off-policy temporal-difference (TD) learning in discounted Markov
decision processes, where the goal is to evaluate a policy in a model-free way
by using observations of a state process generated without executing the
policy. To curb the high variance issue in off-policy TD learning, we propose a
new scheme of setting the $\lambda$-parameters of TD, based on generalized
Bellman equations. Our scheme is to set $\lambda$ according to the eligibility
trace iterates calculated in TD, thereby easily keeping these traces in a
desired bounded range. Compared with prior work, this scheme is more direct and
flexible, and allows much larger $\lambda$ values for off-policy TD learning
with bounded traces. As to its soundness, using Markov chain theory, we prove
the ergodicity of the joint state-trace process under nonrestrictive
conditions, and we show that associated with our scheme is a generalized
Bellman equation (for the policy to be evaluated) that depends on both the
evolution of $\lambda$ and the unique invariant probability measure of the
state-trace process. These results not only lead immediately to a
characterization of the convergence behavior of least-squares based
implementation of our scheme, but also prepare the ground for further analysis
of gradient-based implementations.