pwc-archive/papers-with-abstracts huggingface dataset:
Clustering, Hamming Embedding, Generalized LSH and the Max Norm
Authors: Behnam Neyshabur, Yury Makarychev, Nathan Srebro
Date: 2014-05-13 00:00:00
Tasks: Clustering

We study the convex relaxation of clustering and hamming embedding, focusing
on the asymmetric case (co-clustering and asymmetric hamming embedding),
understanding their relationship to LSH as studied by (Charikar 2002) and to
the max-norm ball, and the differences between their symmetric and asymmetric
versions.
Sparse Matrix Factorization
Authors: Behnam Neyshabur, Rina Panigrahy
Date: 2013-11-13 00:00:00
Tasks: Deep Learning, Dictionary Learning

We investigate the problem of factorizing a matrix into several sparse
matrices and propose an algorithm for this under randomness and sparsity
assumptions. This problem can be viewed as a simplification of the deep
learning problem where finding a factorization corresponds to finding edges in
different layers and values of hidden units. We prove that under certain
assumptions for a sparse linear deep network with $n$ nodes in each layer, our
algorithm is able to recover the structure of the network and values of top
layer hidden units for depths up to $\tilde O(n^{1/6})$. We further discuss the
relation among sparse matrix factorization, deep learning, sparse recovery and
dictionary learning.
Circulant Binary Embedding
Authors: Felix X. Yu, Sanjiv Kumar, Yunchao Gong, Shih-Fu Chang
Date: 2014-05-13 00:00:00

Binary embedding of high-dimensional data requires long codes to preserve the
discriminative power of the input space. Traditional binary coding methods
often suffer from very high computation and storage costs in such a scenario.
To address this problem, we propose Circulant Binary Embedding (CBE) which
generates binary codes by projecting the data with a circulant matrix. The
circulant structure enables the use of Fast Fourier Transformation to speed up
the computation. Compared to methods that use unstructured matrices, the
proposed method improves the time complexity from $\mathcal{O}(d^2)$ to
$\mathcal{O}(d\log{d})$, and the space complexity from $\mathcal{O}(d^2)$ to
$\mathcal{O}(d)$ where $d$ is the input dimensionality. We also propose a novel
time-frequency alternating optimization to learn data-dependent circulant
projections, which alternatively minimizes the objective in original and
Fourier domains. We show by extensive experiments that the proposed approach
gives much better performance than the state-of-the-art approaches for fixed
time, and provides much faster computation with no performance degradation for
fixed number of bits.
Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling
Authors: Peilin Zhao, Tong Zhang
Date: 2014-05-13 00:00:00

Stochastic Gradient Descent (SGD) is a popular optimization method which has
been applied to many important machine learning tasks such as Support Vector
Machines and Deep Neural Networks. In order to parallelize SGD, minibatch
training is often employed. The standard approach is to uniformly sample a
minibatch at each step, which often leads to high variance. In this paper we
propose a stratified sampling strategy, which divides the whole dataset into
clusters with low within-cluster variance; we then take examples from these
clusters using a stratified sampling technique. It is shown that the
convergence rate can be significantly improved by the algorithm. Encouraging
experimental results confirm the effectiveness of the proposed method.
Dimensionality reduction for click-through rate prediction: Dense versus sparse representation
Authors: Bjarne Ørum Fruergaard, Toke Jansen Hansen, Lars Kai Hansen
Date: 2013-11-27 00:00:00
Tasks: Click-Through Rate Prediction, Dimensionality Reduction

In online advertising, display ads are increasingly being placed based on
real-time auctions where the advertiser who wins gets to serve the ad. This is
called real-time bidding (RTB). In RTB, auctions have very tight time
constraints on the order of 100ms. Therefore mechanisms for bidding
intelligently such as clickthrough rate prediction need to be sufficiently
fast. In this work, we propose to use dimensionality reduction of the
user-website interaction graph in order to produce simplified features of users
and websites that can be used as predictors of clickthrough rate. We
demonstrate that the Infinite Relational Model (IRM) as a dimensionality
reduction offers comparable predictive performance to conventional
dimensionality reduction schemes, while achieving the most economical usage of
features and fastest computations at run-time. For applications such as
real-time bidding, where fast database I/O and few computations are key to
success, we thus recommend using IRM based features as predictors to exploit
the recommender effects from bipartite graphs.
Phonetic based SoundEx & ShapeEx algorithm for Sindhi Spell Checker System
Authors: Zeeshan Bhatti, Ahmad Waqas, Imdad Ali Ismaili, Dil Nawaz Hakro, Waseem Javaid Soomro
Date: 2014-05-13 00:00:00

This paper presents a novel combinational phonetic algorithm for Sindhi
Language, to be used in developing Sindhi Spell Checker which has yet not been
developed prior to this work. The compound textual forms and glyphs of Sindhi
language presents a substantial challenge for developing Sindhi spell checker
system and generating similar suggestion list for misspelled words. In order to
implement such a system, phonetic based Sindhi language rules and patterns must
be considered into account for increasing the accuracy and efficiency. The
proposed system is developed with a blend between Phonetic based SoundEx
algorithm and ShapeEx algorithm for pattern or glyph matching, generating
accurate and efficient suggestion list for incorrect or misspelled Sindhi
words. A table of phonetically similar sounding Sindhi characters for SoundEx
algorithm is also generated along with another table containing similar glyph
or shape based character groups for ShapeEx algorithm. Both these are first
ever attempt of any such type of categorization and representation for Sindhi
Language.
A Novel Method for Developing Robotics via Artificial Intelligence and Internet of Things
Authors: Aadhityan A
Date: 2014-05-12 00:00:00

This paper describe about a new methodology for developing and improving the
robotics field via artificial intelligence and internet of things. Now a day,
we can say Artificial Intelligence take the world into robotics. Almost all
industries use robots for lot of works. They are use co-operative robots to
make different kind of works. But there was some problem to make robot for
multi tasks. So there was a necessary new methodology to made multi tasking
robots. It will be done only by artificial intelligence and internet of things.
A Neuron as a Signal Processing Device
Authors: Tao Hu, Zaid J. Towfic, Cengiz Pehlevan, Alex Genkin, Dmitri B. Chklovskii
Date: 2014-05-12 00:00:00

A neuron is a basic physiological and computational unit of the brain. While
much is known about the physiological properties of a neuron, its computational
role is poorly understood. Here we propose to view a neuron as a signal
processing device that represents the incoming streaming data matrix as a
sparse vector of synaptic weights scaled by an outgoing sparse activity vector.
Formally, a neuron minimizes a cost function comprising a cumulative squared
representation error and regularization terms. We derive an online algorithm
that minimizes such cost function by alternating between the minimization with
respect to activity and with respect to synaptic weights. The steps of this
algorithm reproduce well-known physiological properties of a neuron, such as
weighted summation and leaky integration of synaptic inputs, as well as an
Oja-like, but parameter-free, synaptic learning rule. Our theoretical framework
makes several predictions, some of which can be verified by the existing data,
others require further experiments. Such framework should allow modeling the
function of neuronal circuits without necessarily measuring all the microscopic
biophysical parameters, as well as facilitate the design of neuromorphic
electronics.
Cross-view Action Modeling, Learning and Recognition
Authors: Jiang wang, Xiaohan Nie, Yin Xia, Ying Wu, Song-Chun Zhu
Date: 2014-05-12 00:00:00
Proceeding: CVPR 2014 6
Tasks: Action Recognition, Temporal Action Localization

Existing methods on video-based action recognition are generally
view-dependent, i.e., performing recognition from the same views seen in the
training data. We present a novel multiview spatio-temporal AND-OR graph
(MST-AOG) representation for cross-view action recognition, i.e., the
recognition is performed on the video from an unknown and unseen view. As a
compositional model, MST-AOG compactly represents the hierarchical
combinatorial structures of cross-view actions by explicitly modeling the
geometry, appearance and motion variations. This paper proposes effective
methods to learn the structure and parameters of MST-AOG. The inference based
on MST-AOG enables action recognition from novel views. The training of MST-AOG
takes advantage of the 3D human skeleton data obtained from Kinect cameras to
avoid annotating enormous multi-view video frames, which is error-prone and
time-consuming, but the recognition does not need 3D information and is based
on 2D video input. A new Multiview Action3D dataset has been created and will
be released. Extensive experiments have demonstrated that this new action
representation significantly improves the accuracy and robustness for
cross-view action recognition on 2D videos.
Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm
Authors: Hadi Daneshmand, Manuel Gomez-Rodriguez, Le Song, Bernhard Schoelkopf
Date: 2014-05-12 00:00:00

Information spreads across social and technological networks, but often the
network structures are hidden from us and we only observe the traces left by
the diffusion processes, called cascades. Can we recover the hidden network
structures from these observed cascades? What kind of cascades and how many
cascades do we need? Are there some network structures which are more difficult
than others to recover? Can we design efficient inference algorithms with
provable guarantees?
  Despite the increasing availability of cascade data and methods for inferring
networks from these data, a thorough theoretical understanding of the above
questions remains largely unexplored in the literature. In this paper, we
investigate the network structure inference problem for a general family of
continuous-time diffusion models using an $l_1$-regularized likelihood
maximization framework. We show that, as long as the cascade sampling process
satisfies a natural incoherence condition, our framework can recover the
correct network structure with high probability if we observe $O(d^3 \log N)$
cascades, where $d$ is the maximum number of parents of a node and $N$ is the
total number of nodes. Moreover, we develop a simple and efficient
soft-thresholding inference algorithm, which we use to illustrate the
consequences of our theoretical results, and show that our framework
outperforms other alternatives in practice.
Safe Screening With Variational Inequalities and Its Application to LASSO
Authors: Jun Liu, Zheng Zhao, Jie Wang, Jieping Ye
Date: 2013-07-29 00:00:00
Tasks: Computational Efficiency, feature selection, Sparse Learning

Sparse learning techniques have been routinely used for feature selection as
the resulting model usually has a small number of non-zero entries. Safe
screening, which eliminates the features that are guaranteed to have zero
coefficients for a certain value of the regularization parameter, is a
technique for improving the computational efficiency. Safe screening is gaining
increasing attention since 1) solving sparse learning formulations usually has
a high computational cost especially when the number of features is large and
2) one needs to try several regularization parameters to select a suitable
model. In this paper, we propose an approach called "Sasvi" (Safe screening
with variational inequalities). Sasvi makes use of the variational inequality
that provides the sufficient and necessary optimality condition for the dual
problem. Several existing approaches for Lasso screening can be casted as
relaxed versions of the proposed Sasvi, thus Sasvi provides a stronger safe
screening rule. We further study the monotone properties of Sasvi for Lasso,
based on which a sure removal regularization parameter can be identified for
each feature. Experimental results on both synthetic and real data sets are
reported to demonstrate the effectiveness of the proposed Sasvi for Lasso
screening.
A Note on Improved Loss Bounds for Multiple Kernel Learning
Authors: Zakria Hussain, John Shawe-Taylor, Mario Marchand
Date: 2011-06-30 00:00:00

In this paper, we correct an upper bound, presented in~\cite{hs-11}, on the
generalisation error of classifiers learned through multiple kernel learning.
The bound in~\cite{hs-11} uses Rademacher complexity and has an\emph{additive}
dependence on the logarithm of the number of kernels and the margin achieved by
the classifier. However, there are some errors in parts of the proof which are
corrected in this paper. Unfortunately, the final result turns out to be a risk
bound which has a \emph{multiplicative} dependence on the logarithm of the
number of kernels and the margin achieved by the classifier.
The Metrics Matter! On the Incompatibility of Different Flavors of Replanning
Authors: Kartik Talamadupula, David E. Smith, Subbarao Kambhampati
Date: 2014-05-12 00:00:00
Tasks: Open-Ended Question Answering

When autonomous agents are executing in the real world, the state of the
world as well as the objectives of the agent may change from the agent's
original model. In such cases, the agent's planning process must modify the
plan under execution to make it amenable to the new conditions, and to resume
execution. This brings up the replanning problem, and the various techniques
that have been proposed to solve it. In all, three main techniques -- based on
three different metrics -- have been proposed in prior automated planning work.
An open question is whether these metrics are interchangeable; answering this
requires a normalized comparison of the various replanning quality metrics. In
this paper, we show that it is possible to support such a comparison by
compiling all the respective techniques into a single substrate. Using this
novel compilation, we demonstrate that these different metrics are not
interchangeable, and that they are not good surrogates for each other. Thus we
focus attention on the incompatibility of the various replanning flavors with
each other, founded in the differences between the metrics that they
respectively seek to optimize.
Approximate Policy Iteration Schemes: A Comparison
Authors: Bruno Scherrer
Date: 2014-05-12 00:00:00

We consider the infinite-horizon discounted optimal control problem
formalized by Markov Decision Processes. We focus on several approximate
variations of the Policy Iteration algorithm: Approximate Policy Iteration,
Conservative Policy Iteration (CPI), a natural adaptation of the Policy Search
by Dynamic Programming algorithm to the infinite-horizon case (PSDP$_\infty$),
and the recently proposed Non-Stationary Policy iteration (NSPI(m)). For all
algorithms, we describe performance bounds, and make a comparison by paying a
particular attention to the concentrability constants involved, the number of
iterations and the memory required. Our analysis highlights the following
points: 1) The performance guarantee of CPI can be arbitrarily better than that
of API/API($\alpha$), but this comes at the cost of a relative---exponential in
$\frac{1}{\epsilon}$---increase of the number of iterations. 2) PSDP$_\infty$
enjoys the best of both worlds: its performance guarantee is similar to that of
CPI, but within a number of iterations similar to that of API. 3) Contrary to
API that requires a constant memory, the memory needed by CPI and PSDP$_\infty$
is proportional to their number of iterations, which may be problematic when
the discount factor $\gamma$ is close to 1 or the approximation error
$\epsilon$ is close to $0$; we show that the NSPI(m) algorithm allows to make
an overall trade-off between memory and performance. Simulations with these
schemes confirm our analysis.
Dynamic Rate and Channel Selection in Cognitive Radio Systems
Authors: Richard Combes, Alexandre Proutiere
Date: 2014-02-23 00:00:00
Tasks: channel selection

In this paper, we investigate dynamic channel and rate selection in cognitive
radio systems which exploit a large number of channels free from primary users.
In such systems, transmitters may rapidly change the selected (channel, rate)
pair to opportunistically learn and track the pair offering the highest
throughput. We formulate the problem of sequential channel and rate selection
as an online optimization problem, and show its equivalence to a {\it
structured} Multi-Armed Bandit problem. The structure stems from inherent
properties of the achieved throughput as a function of the selected channel and
rate. We derive fundamental performance limits satisfied by {\it any} channel
and rate adaptation algorithm, and propose algorithms that achieve (or
approach) these limits. In turn, the proposed algorithms optimally exploit the
inherent structure of the throughput. We illustrate the efficiency of our
algorithms using both test-bed and simulation experiments, in both stationary
and non-stationary radio environments. In stationary environments, the packet
successful transmission probabilities at the various channel and rate pairs do
not evolve over time, whereas in non-stationary environments, they may evolve.
In practical scenarios, the proposed algorithms are able to track the best
channel and rate quite accurately without the need of any explicit measurement
and feedback of the quality of the various channels.
Resource-Aware Programming for Robotic Vision
Authors: Johny Paul, Walter Stechele, Manfred Kröhnert, Tamim Asfour
Date: 2014-05-12 00:00:00

Humanoid robots are designed to operate in human centered environments. They
face changing, dynamic environments in which they need to fulfill a multitude
of challenging tasks. Such tasks differ in complexity, resource requirements,
and execution time. Latest computer architectures of humanoid robots consist of
several industrial PCs containing single- or dual-core processors. According to
the SIA roadmap for semiconductors, many-core chips with hundreds to thousands
of cores are expected to be available in the next decade. Utilizing the full
power of a chip with huge amounts of resources requires new computing paradigms
and methodologies.
  In this paper, we analyze a resource-aware computing methodology named
Invasive Computing, to address these challenges. The benefits and limitations
of the new programming model is analyzed using two widely used computer vision
algorithms, the Harris Corner detector and SIFT (Scale Invariant Feature
Transform) feature matching. The result indicate that the new programming model
together with the extensions within the application layer, makes them highly
adaptable; leading to better quality in the results obtained.
D numbers theory: a generalization of Dempster-Shafer theory
Authors: Xinyang Deng, Yong Deng
Date: 2014-02-14 00:00:00

Dempster-Shafer theory is widely applied to uncertainty modelling and
knowledge reasoning due to its ability of expressing uncertain information.
However, some conditions, such as exclusiveness hypothesis and completeness
constraint, limit its development and application to a large extend. To
overcome these shortcomings in Dempster-Shafer theory and enhance its
capability of representing uncertain information, a novel theory called D
numbers theory is systematically proposed in this paper. Within the proposed
theory, uncertain information is expressed by D numbers, reasoning and
synthesization of information are implemented by D numbers combination rule.
The proposed D numbers theory is an generalization of Dempster-Shafer theory,
which inherits the advantage of Dempster-Shafer theory and strengthens its
capability of uncertainty modelling.
Conservative collision prediction and avoidance for stochastic trajectories in continuous time and space
Authors: Jan-Peter Calliess, Michael Osborne, Stephen Roberts
Date: 2014-02-17 00:00:00
Tasks: Collision Avoidance

Existing work in multi-agent collision prediction and avoidance typically
assumes discrete-time trajectories with Gaussian uncertainty or that are
completely deterministic. We propose an approach that allows detection of
collisions even between continuous, stochastic trajectories with the only
restriction that means and variances can be computed. To this end, we employ
probabilistic bounds to derive criterion functions whose negative sign provably
is indicative of probable collisions. For criterion functions that are
Lipschitz, an algorithm is provided to rapidly find negative values or prove
their absence. We propose an iterative policy-search approach that avoids prior
discretisations and yields collision-free trajectories with adjustably high
certainty. We test our method with both fixed-priority and auction-based
protocols for coordinating the iterative planning process. Results are provided
in collision-avoidance simulations of feedback controlled plants.
Two-Stage Metric Learning
Authors: Jun Wang, Ke Sun, Fei Sha, Stephane Marchand-Maillet, Alexandros Kalousis
Date: 2014-05-12 00:00:00
Tasks: Metric Learning, Vocal Bursts Valence Prediction

In this paper, we present a novel two-stage metric learning algorithm. We
first map each learning instance to a probability distribution by computing its
similarities to a set of fixed anchor points. Then, we define the distance in
the input data space as the Fisher information distance on the associated
statistical manifold. This induces in the input data space a new family of
distance metric with unique properties. Unlike kernelized metric learning, we
do not require the similarity measure to be positive semi-definite. Moreover,
it can also be interpreted as a local metric learning algorithm with well
defined distance approximation. We evaluate its performance on a number of
datasets. It outperforms significantly other metric learning methods and SVM.
Gender identity and lexical variation in social media
Authors: David Bamman, Jacob Eisenstein, Tyler Schnoebelen
Date: 2012-10-16 00:00:00
Tasks: Clustering

We present a study of the relationship between gender, linguistic style, and
social networks, using a novel corpus of 14,000 Twitter users. Prior
quantitative work on gender often treats this social variable as a female/male
binary; we argue for a more nuanced approach. By clustering Twitter users, we
find a natural decomposition of the dataset into various styles and topical
interests. Many clusters have strong gender orientations, but their use of
linguistic resources sometimes directly conflicts with the population-level
language statistics. We view these clusters as a more accurate reflection of
the multifaceted nature of gendered language styles. Previous corpus-based work
has also had little to say about individuals whose linguistic styles defy
population-level gender patterns. To identify such individuals, we train a
statistical classifier, and measure the classifier confidence for each
individual in the dataset. Examining individuals whose language does not match
the classifier's model for their gender, we find that they have social networks
that include significantly fewer same-gender social connections and that, in
general, social network homophily is correlated with the use of same-gender
language markers. Pairing computational methods and social theory thus offers a
new perspective on how gender emerges as individuals position themselves
relative to audiences, topics, and mainstream gender norms.