pwc-archive/papers-with-abstracts huggingface dataset:
Local Graph Clustering Beyond Cheeger's Inequality
Authors: Zeyuan Allen Zhu, Silvio Lattanzi, Vahab Mirrokni
Date: 2013-04-30 00:00:00
Tasks: Clustering, Graph Clustering

Motivated by applications of large-scale graph clustering, we study
random-walk-based LOCAL algorithms whose running times depend only on the size
of the output cluster, rather than the entire graph. All previously known such
algorithms guarantee an output conductance of $\tilde{O}(\sqrt{\phi(A)})$ when
the target set $A$ has conductance $\phi(A)\in[0,1]$. In this paper, we improve
it to $$\tilde{O}\bigg( \min\Big\{\sqrt{\phi(A)},
\frac{\phi(A)}{\sqrt{\mathsf{Conn}(A)}} \Big\} \bigg)\enspace, $$ where the
internal connectivity parameter $\mathsf{Conn}(A) \in [0,1]$ is defined as the
reciprocal of the mixing time of the random walk over the induced subgraph on
$A$.
  For instance, using $\mathsf{Conn}(A) = \Omega(\lambda(A) / \log n)$ where
$\lambda$ is the second eigenvalue of the Laplacian of the induced subgraph on
$A$, our conductance guarantee can be as good as
$\tilde{O}(\phi(A)/\sqrt{\lambda(A)})$. This builds an interesting connection
to the recent advance of the so-called improved Cheeger's Inequality [KKL+13],
which says that global spectral algorithms can provide a conductance guarantee
of $O(\phi_{\mathsf{opt}}/\sqrt{\lambda_3})$ instead of
$O(\sqrt{\phi_{\mathsf{opt}}})$.
  In addition, we provide theoretical guarantee on the clustering accuracy (in
terms of precision and recall) of the output set. We also prove that our
analysis is tight, and perform empirical evaluation to support our theory on
both synthetic and real data.
  It is worth noting that, our analysis outperforms prior work when the cluster
is well-connected. In fact, the better it is well-connected inside, the more
significant improvement (both in terms of conductance and accuracy) we can
obtain. Our results shed light on why in practice some random-walk-based
algorithms perform better than its previous theory, and help guide future
research about local clustering.
Automatic ontology generation for data mining using fca and clustering
Authors: Amel Grissa Touzi, Hela Ben Massoud, Alaya Ayadi
Date: 2013-11-07 00:00:00
Tasks: Clustering, General Classification

Motivated by the increased need for formalized representations of the domain
of Data Mining, the success of using Formal Concept Analysis (FCA) and Ontology
in several Computer Science fields, we present in this paper a new approach for
automatic generation of Fuzzy Ontology of Data Mining (FODM), through the
fusion of conceptual clustering, fuzzy logic, and FCA. In our approach, we
propose to generate ontology taking in consideration another degree of
granularity into the process of generation. Indeed, we suggest to define an
ontology between classes resulting from a preliminary classification on the
data. We prove that this approach optimize the definition of the ontology,
offered a better interpretation of the data and optimized both the space memory
and the execution time for exploiting this data.
Exploring Deep and Recurrent Architectures for Optimal Control
Authors: Sergey Levine
Date: 2013-11-07 00:00:00
Tasks: Reinforcement Learning

Sophisticated multilayer neural networks have achieved state of the art
results on multiple supervised tasks. However, successful applications of such
multilayer networks to control have so far been limited largely to the
perception portion of the control pipeline. In this paper, we explore the
application of deep and recurrent neural networks to a continuous,
high-dimensional locomotion task, where the network is used to represent a
control policy that maps the state of the system (represented by joint angles)
directly to the torques at each joint. By using a recent reinforcement learning
algorithm called guided policy search, we can successfully train neural network
controllers with thousands of parameters, allowing us to compare a variety of
architectures. We discuss the differences between the locomotion control task
and previous supervised perception tasks, present experimental results
comparing various architectures, and discuss future directions in the
application of techniques from deep learning to the problem of optimal control.
Biometric Signature Processing & Recognition Using Radial Basis Function Network
Authors: Ankit Chadha, Neha Satam, Vibha Wali
Date: 2013-11-07 00:00:00
Tasks: Translation

Automatic recognition of signature is a challenging problem which has
received much attention during recent years due to its many applications in
different fields. Signature has been used for long time for verification and
authentication purpose. Earlier methods were manual but nowadays they are
getting digitized. This paper provides an efficient method to signature
recognition using Radial Basis Function Network. The network is trained with
sample images in database. Feature extraction is performed before using them
for training. For testing purpose, an image is made to undergo
rotation-translation-scaling correction and then given to network. The network
successfully identifies the original image and gives correct output for stored
database images also. The method provides recognition rate of approximately 80%
for 200 samples.
The Maximum Entropy Relaxation Path
Authors: Moshe Dubiner, Matan Gavish, Yoram Singer
Date: 2013-11-07 00:00:00

The relaxed maximum entropy problem is concerned with finding a probability
distribution on a finite set that minimizes the relative entropy to a given
prior distribution, while satisfying relaxed max-norm constraints with respect
to a third observed multinomial distribution. We study the entire relaxation
path for this problem in detail. We show existence and a geometric description
of the relaxation path. Specifically, we show that the maximum entropy
relaxation path admits a planar geometric description as an increasing,
piecewise linear function in the inverse relaxation parameter. We derive fast
algorithms for tracking the path. In various realistic settings, our algorithms
require $O(n\log(n))$ operations for probability distributions on $n$ points,
making it possible to handle large problems. Once the path has been recovered,
we show that given a validation set, the family of admissible models is reduced
from an infinite family to a small, discrete set. We demonstrate the merits of
our approach in experiments with synthetic data and discuss its potential for
the estimation of compact n-gram language models.
Category-Theoretic Quantitative Compositional Distributional Models of Natural Language Semantics
Authors: Edward Grefenstette
Date: 2013-11-06 00:00:00

This thesis is about the problem of compositionality in distributional
semantics. Distributional semantics presupposes that the meanings of words are
a function of their occurrences in textual contexts. It models words as
distributions over these contexts and represents them as vectors in high
dimensional spaces. The problem of compositionality for such models concerns
itself with how to produce representations for larger units of text by
composing the representations of smaller units of text.
  This thesis focuses on a particular approach to this compositionality
problem, namely using the categorical framework developed by Coecke, Sadrzadeh,
and Clark, which combines syntactic analysis formalisms with distributional
semantic representations of meaning to produce syntactically motivated
composition operations. This thesis shows how this approach can be
theoretically extended and practically implemented to produce concrete
compositional distributional models of natural language semantics. It
furthermore demonstrates that such models can perform on par with, or better
than, other competing approaches in the field of natural language processing.
  There are three principal contributions to computational linguistics in this
thesis. The first is to extend the DisCoCat framework on the syntactic front
and semantic front, incorporating a number of syntactic analysis formalisms and
providing learning procedures allowing for the generation of concrete
compositional distributional models. The second contribution is to evaluate the
models developed from the procedures presented here, showing that they
outperform other compositional distributional models present in the literature.
The third contribution is to show how using category theory to solve linguistic
problems forms a sound basis for research, illustrated by examples of work on
this topic, that also suggest directions for future research.
Adaptive Measurement-Based Policy-Driven QoS Management with Fuzzy-Rule-based Resource Allocation
Authors: Suleiman Y. Yerima, Gerard P. Parr, Sally I. McClean, Philip J. Morrow
Date: 2013-11-06 00:00:00
Tasks: Management

Fixed and wireless networks are increasingly converging towards common
connectivity with IP-based core networks. Providing effective end-to-end
resource and QoS management in such complex heterogeneous converged network
scenarios requires unified, adaptive and scalable solutions to integrate and
co-ordinate diverse QoS mechanisms of different access technologies with
IP-based QoS. Policy-Based Network Management (PBNM) is one approach that could
be employed to address this challenge. Hence, a policy-based framework for
end-to-end QoS management in converged networks, CNQF (Converged Networks QoS
Management Framework) has been proposed within our project. In this paper, the
CNQF architecture, a Java implementation of its prototype and experimental
validation of key elements are discussed. We then present a fuzzy-based CNQF
resource management approach and study the performance of our implementation
with real traffic flows on an experimental testbed. The results demonstrate the
efficacy of our resource-adaptive approach for practical PBNM systems.
Exploration in Interactive Personalized Music Recommendation: A Reinforcement Learning Approach
Authors: Xinxi Wang, Yi Wang, David Hsu, Ye Wang
Date: 2013-11-06 00:00:00
Tasks: Bayesian Inference, Music Recommendation, Recommendation Systems, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Variational Inference

Current music recommender systems typically act in a greedy fashion by
recommending songs with the highest user ratings. Greedy recommendation,
however, is suboptimal over the long term: it does not actively gather
information on user preferences and fails to recommend novel songs that are
potentially interesting. A successful recommender system must balance the needs
to explore user preferences and to exploit this information for recommendation.
This paper presents a new approach to music recommendation by formulating this
exploration-exploitation trade-off as a reinforcement learning task called the
multi-armed bandit. To learn user preferences, it uses a Bayesian model, which
accounts for both audio content and the novelty of recommendations. A
piecewise-linear approximation to the model and a variational inference
algorithm are employed to speed up Bayesian inference. One additional benefit
of our approach is a single unified model for both music recommendation and
playlist generation. Both simulation results and a user study indicate strong
potential for the new approach.
The Squared-Error of Generalized LASSO: A Precise Analysis
Authors: Samet Oymak, Christos Thrampoulidis, Babak Hassibi
Date: 2013-11-04 00:00:00

We consider the problem of estimating an unknown signal $x_0$ from noisy
linear observations $y = Ax_0 + z\in R^m$. In many practical instances, $x_0$
has a certain structure that can be captured by a structure inducing convex
function $f(\cdot)$. For example, $\ell_1$ norm can be used to encourage a
sparse solution. To estimate $x_0$ with the aid of $f(\cdot)$, we consider the
well-known LASSO method and provide sharp characterization of its performance.
We assume the entries of the measurement matrix $A$ and the noise vector $z$
have zero-mean normal distributions with variances $1$ and $\sigma^2$
respectively. For the LASSO estimator $x^*$, we attempt to calculate the
Normalized Square Error (NSE) defined as $\frac{\|x^*-x_0\|_2^2}{\sigma^2}$ as
a function of the noise level $\sigma$, the number of observations $m$ and the
structure of the signal. We show that, the structure of the signal $x_0$ and
choice of the function $f(\cdot)$ enter the error formulae through the summary
parameters $D(cone)$ and $D(\lambda)$, which are defined as the Gaussian
squared-distances to the subdifferential cone and to the $\lambda$-scaled
subdifferential, respectively. The first LASSO estimator assumes a-priori
knowledge of $f(x_0)$ and is given by $\arg\min_{x}\{{\|y-Ax\|_2}~\text{subject
to}~f(x)\leq f(x_0)\}$. We prove that its worst case NSE is achieved when
$\sigma\rightarrow 0$ and concentrates around $\frac{D(cone)}{m-D(cone)}$.
Secondly, we consider $\arg\min_{x}\{\|y-Ax\|_2+\lambda f(x)\}$, for some
$\lambda\geq 0$. This time the NSE formula depends on the choice of $\lambda$
and is given by $\frac{D(\lambda)}{m-D(\lambda)}$. We then establish a mapping
between this and the third estimator $\arg\min_{x}\{\frac{1}{2}\|y-Ax\|_2^2+
\lambda f(x)\}$. Finally, for a number of important structured signal classes,
we translate our abstract formulae to closed-form upper bounds on the NSE.
Face Recognition via Globality-Locality Preserving Projections
Authors: Sheng Huang, Dan Yang, Fei Yang, Yongxin Ge, Xiaohong Zhang, Jiwen Lu
Date: 2013-11-06 00:00:00
Tasks: Face Recognition

We present an improved Locality Preserving Projections (LPP) method, named Gloablity-Locality Preserving Projections (GLPP), to preserve both the global and local geometric structures of data. In our approach, an additional constraint of the geometry of classes is imposed to the objective function of conventional LPP for respecting some more global manifold structures. Moreover, we formulate a two-dimensional extension of GLPP (2D-GLPP) as an example to show how to extend GLPP with some other statistical techniques. We apply our works to face recognition on four popular face databases, namely ORL, Yale, FERET and LFW-A databases, and extensive experimental results demonstrate that the considered global manifold information can significantly improve the performance of LPP and the proposed face recognition methods outperform the state-of-the-arts.
Randomized Dimension Reduction on Massive Data
Authors: Stoyan Georgiev, Sayan Mukherjee
Date: 2012-11-07 00:00:00
Tasks: Dimensionality Reduction, regression

Scalability of statistical estimators is of increasing importance in modern
applications and dimension reduction is often used to extract relevant
information from data. A variety of popular dimension reduction approaches can
be framed as symmetric generalized eigendecomposition problems. In this paper
we outline how taking into account the low rank structure assumption implicit
in these dimension reduction approaches provides both computational and
statistical advantages. We adapt recent randomized low-rank approximation
algorithms to provide efficient solutions to three dimension reduction methods:
Principal Component Analysis (PCA), Sliced Inverse Regression (SIR), and
Localized Sliced Inverse Regression (LSIR). A key observation in this paper is
that randomization serves a dual role, improving both computational and
statistical performance. This point is highlighted in our experiments on real
and simulated data.
Quality Assessment of Pixel-Level ImageFusion Using Fuzzy Logic
Authors: Srinivasa Rao Dammavalam, Seetha Maddala, M. H. M. Krishna Prasad
Date: 2013-11-05 00:00:00
Tasks: Weather Forecasting

Image fusion is to reduce uncertainty and minimize redundancy in the output
while maximizing relevant information from two or more images of a scene into a
single composite image that is more informative and is more suitable for visual
perception or processing tasks like medical imaging, remote sensing, concealed
weapon detection, weather forecasting, biometrics etc. Image fusion combines
registered images to produce a high quality fused image with spatial and
spectral information. The fused image with more information will improve the
performance of image analysis algorithms used in different applications. In
this paper, we proposed a fuzzy logic method to fuse images from different
sensors, in order to enhance the quality and compared proposed method with two
other methods i.e. image fusion using wavelet transform and weighted average
discrete wavelet transform based image fusion using genetic algorithm (here
onwards abbreviated as GA) along with quality evaluation parameters image
quality index (IQI), mutual information measure (MIM), root mean square error
(RMSE), peak signal to noise ratio (PSNR), fusion factor (FF), fusion symmetry
(FS) and fusion index (FI) and entropy. The results obtained from proposed
fuzzy based image fusion approach improves quality of fused image as compared
to earlier reported methods, wavelet transform based image fusion and weighted
average discrete wavelet transform based image fusion using genetic algorithm.
A Big Data Approach to Computational Creativity
Authors: Lav R. Varshney, Florian Pinel, Kush R. Varshney, Debarun Bhattacharjya, Angela Schoergendorfer, Yi-Min Chee
Date: 2013-11-05 00:00:00
Tasks: valid

Computational creativity is an emerging branch of artificial intelligence
that places computers in the center of the creative process. Broadly,
creativity involves a generative step to produce many ideas and a selective
step to determine the ones that are the best. Many previous attempts at
computational creativity, however, have not been able to achieve a valid
selective step. This work shows how bringing data sources from the creative
domain and from hedonic psychophysics together with big data analytics
techniques can overcome this shortcoming to yield a system that can produce
novel and high-quality creative artifacts. Our data-driven approach is
demonstrated through a computational creativity system for culinary recipes and
menus we developed and deployed, which can operate either autonomously or
semi-autonomously with human interaction. We also comment on the volume,
velocity, variety, and veracity of data in computational creativity.
Identifying Purpose Behind Electoral Tweets
Authors: Saif M. Mohammad, Svetlana Kiritchenko, Joel Martin
Date: 2013-11-05 00:00:00
Tasks: Question Answering

Tweets pertaining to a single event, such as a national election, can number
in the hundreds of millions. Automatically analyzing them is beneficial in many
downstream natural language applications such as question answering and
summarization. In this paper, we propose a new task: identifying the purpose
behind electoral tweets--why do people post election-oriented tweets? We show
that identifying purpose is correlated with the related phenomenon of sentiment
and emotion detection, but yet significantly different. Detecting purpose has a
number of applications including detecting the mood of the electorate,
estimating the popularity of policies, identifying key issues of contention,
and predicting the course of events. We create a large dataset of electoral
tweets and annotate a few thousand tweets for purpose. We develop a system that
automatically classifies electoral tweets as per their purpose, obtaining an
accuracy of 43.56% on an 11-class task and an accuracy of 73.91% on a 3-class
task (both accuracies well above the most-frequent-class baseline). Finally, we
show that resources developed for emotion detection are also helpful for
detecting purpose.
Statistical Inference in Hidden Markov Models using $k$-segment Constraints
Authors: Michalis K. Titsias, Christopher Yau, Christopher C. Holmes
Date: 2013-11-05 00:00:00

Hidden Markov models (HMMs) are one of the most widely used statistical
methods for analyzing sequence data. However, the reporting of output from HMMs
has largely been restricted to the presentation of the most-probable (MAP)
hidden state sequence, found via the Viterbi algorithm, or the sequence of most
probable marginals using the forward-backward (F-B) algorithm. In this article,
we expand the amount of information we could obtain from the posterior
distribution of an HMM by introducing linear-time dynamic programming
algorithms that, we collectively call $k$-segment algorithms, that allow us to
i) find MAP sequences, ii) compute posterior probabilities and iii) simulate
sample paths conditional on a user specified number of segments, i.e.
contiguous runs in a hidden state, possibly of a particular type. We illustrate
the utility of these methods using simulated and real examples and highlight
the application of prospective and retrospective use of these methods for
fitting HMMs or exploring existing model fits.
Using Robust PCA to estimate regional characteristics of language use from geo-tagged Twitter messages
Authors: Dániel Kondor, István Csabai, László Dobos, János Szüle, Norbert Barankai, Tamás Hanyecz, Tamás Sebők, Zsófia Kallus, Gábor Vattay
Date: 2013-11-05 00:00:00

Principal component analysis (PCA) and related techniques have been
successfully employed in natural language processing. Text mining applications
in the age of the online social media (OSM) face new challenges due to
properties specific to these use cases (e.g. spelling issues specific to texts
posted by users, the presence of spammers and bots, service announcements,
etc.). In this paper, we employ a Robust PCA technique to separate typical
outliers and highly localized topics from the low-dimensional structure present
in language use in online social networks. Our focus is on identifying
geospatial features among the messages posted by the users of the Twitter
microblogging service. Using a dataset which consists of over 200 million
geolocated tweets collected over the course of a year, we investigate whether
the information present in word usage frequencies can be used to identify
regional features of language use and topics of interest. Using the PCA pursuit
method, we are able to identify important low-dimensional features, which
constitute smoothly varying functions of the geographic location.
Learning Trajectory Preferences for Manipulators via Iterative Improvement
Authors: Ashesh Jain, Brian Wojcik, Thorsten Joachims, Ashutosh Saxena
Date: 2013-06-26 00:00:00
Proceeding: NeurIPS 2013 12

We consider the problem of learning good trajectories for manipulation tasks.
This is challenging because the criterion defining a good trajectory varies
with users, tasks and environments. In this paper, we propose a co-active
online learning framework for teaching robots the preferences of its users for
object manipulation tasks. The key novelty of our approach lies in the type of
feedback expected from the user: the human user does not need to demonstrate
optimal trajectories as training data, but merely needs to iteratively provide
trajectories that slightly improve over the trajectory currently proposed by
the system. We argue that this co-active preference feedback can be more easily
elicited from the user than demonstrations of optimal trajectories, which are
often challenging and non-intuitive to provide on high degrees of freedom
manipulators. Nevertheless, theoretical regret bounds of our algorithm match
the asymptotic rates of optimal trajectory algorithms. We demonstrate the
generalizability of our algorithm on a variety of grocery checkout tasks, for
whom, the preferences were not only influenced by the object being manipulated
but also by the surrounding environment.\footnote{For more details and a
demonstration video, visit: \url{http://pr.cs.cornell.edu/coactive}}