pwc-archive/papers-with-abstracts huggingface dataset:
A theoretical contribution to the fast implementation of null linear discriminant analysis method using random matrix multiplication with scatter matrices
Authors: Ting-ting Feng, Gang Wu
Date: 2014-09-09 00:00:00
Tasks: Dimensionality Reduction

The null linear discriminant analysis method is a competitive approach for
dimensionality reduction. The implementation of this method, however, is
computationally expensive. Recently, a fast implementation of null linear
discriminant analysis method using random matrix multiplication with scatter
matrices was proposed. However, if the random matrix is chosen arbitrarily, the
orientation matrix may be rank deficient, and some useful discriminant
information will be lost. In this paper, we investigate how to choose the
random matrix properly, such that the two criteria of the null LDA method are
satisfied theoretically. We give a necessary and sufficient condition to
guarantee full column rank of the orientation matrix. Moreover, the geometric
characterization of the condition is also described.
Combining the analytical hierarchy process and the genetic algorithm to solve the timetable problem
Authors: Ihab Sbeity, Mohamed Dbouk, Habib Kobeissi
Date: 2014-09-09 00:00:00

The main problems of school course timetabling are time, curriculum, and
classrooms. In addition there are other problems that vary from one institution
to another. This paper is intended to solve the problem of satisfying the
teachers preferred schedule in a way that regards the importance of the teacher
to the supervising institute, i.e. his score according to some criteria.
Genetic algorithm (GA) has been presented as an elegant method in solving
timetable problem (TTP) in order to produce solutions with no conflict. In this
paper, we consider the analytic hierarchy process (AHP) to efficiently obtain a
score for each teacher, and consequently produce a GA-based TTP solution that
satisfies most of the teachers preferences.
Comparing Feature Detectors: A bias in the repeatability criteria, and how to correct it
Authors: Ives Rey-Otero, Mauricio Delbracio, Jean-Michel Morel
Date: 2014-09-08 00:00:00

Most computer vision application rely on algorithms finding local
correspondences between different images. These algorithms detect and compare
stable local invariant descriptors centered at scale-invariant keypoints.
Because of the importance of the problem, new keypoint detectors and
descriptors are constantly being proposed, each one claiming to perform better
(or to be complementary) to the preceding ones. This raises the question of a
fair comparison between very diverse methods. This evaluation has been mainly
based on a repeatability criterion of the keypoints under a series of image
perturbations (blur, illumination, noise, rotations, homotheties, homographies,
etc). In this paper, we argue that the classic repeatability criterion is
biased towards algorithms producing redundant overlapped detections. To
compensate this bias, we propose a variant of the repeatability rate taking
into account the descriptors overlap. We apply this variant to revisit the
popular benchmark by Mikolajczyk et al., on classic and new feature detectors.
Experimental evidence shows that the hierarchy of these feature detectors is
severely disrupted by the amended comparator.
Learning Machines Implemented on Non-Deterministic Hardware
Authors: Suyog Gupta, Vikas Sindhwani, Kailash Gopalakrishnan
Date: 2014-09-09 00:00:00
Tasks: BIG-bench Machine Learning

This paper highlights new opportunities for designing large-scale machine
learning systems as a consequence of blurring traditional boundaries that have
allowed algorithm designers and application-level practitioners to stay -- for
the most part -- oblivious to the details of the underlying hardware-level
implementations. The hardware/software co-design methodology advocated here
hinges on the deployment of compute-intensive machine learning kernels onto
compute platforms that trade-off determinism in the computation for improvement
in speed and/or energy efficiency. To achieve this, we revisit digital
stochastic circuits for approximating matrix computations that are ubiquitous
in machine learning algorithms. Theoretical and empirical evaluation is
undertaken to assess the impact of the hardware-induced computational noise on
algorithm performance. As a proof-of-concept, a stochastic hardware simulator
is employed for training deep neural networks for image recognition problems.
Multi-scale Orderless Pooling of Deep Convolutional Activation Features
Authors: Yunchao Gong, Li-Wei Wang, Ruiqi Guo, Svetlana Lazebnik
Date: 2014-03-07 00:00:00
Tasks: Classification, General Classification, image-classification, Image Classification, Retrieval

Deep convolutional neural networks (CNN) have shown their promise as a
universal representation for recognition. However, global CNN activations lack
geometric invariance, which limits their robustness for classification and
matching of highly variable scenes. To improve the invariance of CNN
activations without degrading their discriminative power, this paper presents a
simple but effective scheme called multi-scale orderless pooling (MOP-CNN).
This scheme extracts CNN activations for local patches at multiple scale
levels, performs orderless VLAD pooling of these activations at each level
separately, and concatenates the result. The resulting MOP-CNN representation
can be used as a generic feature for either supervised or unsupervised
recognition tasks, from image classification to instance-level retrieval; it
consistently outperforms global CNN activations without requiring any joint
training of prediction layers for a particular target dataset. In absolute
terms, it achieves state-of-the-art results on the challenging SUN397 and MIT
Indoor Scenes classification datasets, and competitive results on
ILSVRC2012/2013 classification and INRIA Holidays retrieval datasets.
Exploiting Social Network Structure for Person-to-Person Sentiment Analysis
Authors: Robert West, Hristo S. Paskov, Jure Leskovec, Christopher Potts
Date: 2014-09-08 00:00:00
Proceeding: TACL 2014 1
Tasks: Decision Making, Sentiment Analysis

Person-to-person evaluations are prevalent in all kinds of discourse and
important for establishing reputations, building social bonds, and shaping
public opinion. Such evaluations can be analyzed separately using signed social
networks and textual sentiment analysis, but this misses the rich interactions
between language and social context. To capture such interactions, we develop a
model that predicts individual A's opinion of individual B by synthesizing
information from the signed social network in which A and B are embedded with
sentiment analysis of the evaluative texts relating A to B. We prove that this
problem is NP-hard but can be relaxed to an efficiently solvable hinge-loss
Markov random field, and we show that this implementation outperforms text-only
and network-only versions in two very different datasets involving
community-level decision-making: the Wikipedia Requests for Adminship corpus
and the Convote U.S. Congressional speech corpus.
Approximating solution structure of the Weighted Sentence Alignment problem
Authors: Antonina Kolokolova, Renesa Nizamee
Date: 2014-09-08 00:00:00
Tasks: Sentence

We study the complexity of approximating solution structure of the bijective
weighted sentence alignment problem of DeNero and Klein (2008). In particular,
we consider the complexity of finding an alignment that has a significant
overlap with an optimal alignment. We discuss ways of representing the solution
for the general weighted sentence alignment as well as phrases-to-words
alignment problem, and show that computing a string which agrees with the
optimal sentence partition on more than half (plus an arbitrarily small
polynomial fraction) positions for the phrases-to-words alignment is NP-hard.
For the general weighted sentence alignment we obtain such bound from the
agreement on a little over 2/3 of the bits. Additionally, we generalize the
Hamming distance approximation of a solution structure to approximating it with
respect to the edit distance metric, obtaining similar lower bounds.
Bayesian Discovery of Threat Networks
Authors: Steven T. Smith, Edward K. Kao, Kenneth D. Senne, Garrett Bernstein, Scott Philips
Date: 2013-11-21 00:00:00

A novel unified Bayesian framework for network detection is developed, under
which a detection algorithm is derived based on random walks on graphs. The
algorithm detects threat networks using partial observations of their activity,
and is proved to be optimum in the Neyman-Pearson sense. The algorithm is
defined by a graph, at least one observation, and a diffusion model for threat.
A link to well-known spectral detection methods is provided, and the
equivalence of the random walk and harmonic solutions to the Bayesian
formulation is proven. A general diffusion model is introduced that utilizes
spatio-temporal relationships between vertices, and is used for a specific
space-time formulation that leads to significant performance improvements on
coordinated covert networks. This performance is demonstrated using a new
hybrid mixed-membership blockmodel introduced to simulate random covert
networks with realistic properties.
Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots
Authors: Michal Čáp, Peter Novák, Alexander Kleiner, Martin Selecký
Date: 2014-09-08 00:00:00
Tasks: Trajectory Planning

An important capability of autonomous multi-robot systems is to prevent
collision among the individual robots. One approach to this problem is to plan
conflict-free trajectories and let each of the robots follow its pre-planned
trajectory. A widely used practical method for multi-robot trajectory planning
is prioritized planning, which has been shown to be effective in practice, but
is in general incomplete. Formal analysis of instances that are provably
solvable by prioritized planning is still missing. Moreover, prioritized
planning is a centralized algorithm, which may be in many situations
undesirable.
  In this paper we a) propose a revised version of prioritized planning and
characterize the class of instances that are provably solvable by the algorithm
and b) propose an asynchronous decentralized variant of prioritized planning,
which maintains the desirable properties of the centralized version and in the
same time exploits the distributed computational power of the individual
robots, which in most situations allows to find the joint trajectories faster.
  The experimental evaluation performed on real-world indoor maps shows that a)
the revised version of prioritized planning reliably solves a wide class of
instances on which both classical prioritized planning and popular reactive
technique ORCA fail and b) the asynchronous decentralized algorithm provides
solution faster than the previously proposed synchronized decentralized
algorithm.
Symbolic regression of generative network models
Authors: Telmo Menezes, Camille Roth
Date: 2014-09-08 00:00:00
Tasks: regression, Symbolic Regression

Networks are a powerful abstraction with applicability to a variety of
scientific fields. Models explaining their morphology and growth processes
permit a wide range of phenomena to be more systematically analysed and
understood. At the same time, creating such models is often challenging and
requires insights that may be counter-intuitive. Yet there currently exists no
general method to arrive at better models. We have developed an approach to
automatically detect realistic decentralised network growth models from
empirical data, employing a machine learning technique inspired by natural
selection and defining a unified formalism to describe such models as computer
programs. As the proposed method is completely general and does not assume any
pre-existing models, it can be applied "out of the box" to any given network.
To validate our approach empirically, we systematically rediscover pre-defined
growth laws underlying several canonical network generation models and credible
laws for diverse real-world networks. We were able to find programs that are
simple enough to lead to an actual understanding of the mechanisms proposed,
namely for a simple brain and a social network.
Variational Inference for Uncertainty on the Inputs of Gaussian Process Models
Authors: Andreas C. Damianou, Michalis K. Titsias, Neil D. Lawrence
Date: 2014-09-08 00:00:00
Tasks: Dimensionality Reduction, Gaussian Processes, Variational Inference

The Gaussian process latent variable model (GP-LVM) provides a flexible
approach for non-linear dimensionality reduction that has been widely applied.
However, the current approach for training GP-LVMs is based on maximum
likelihood, where the latent projection variables are maximized over rather
than integrated out. In this paper we present a Bayesian method for training
GP-LVMs by introducing a non-standard variational inference framework that
allows to approximately integrate out the latent variables and subsequently
train a GP-LVM by maximizing an analytic lower bound on the exact marginal
likelihood. We apply this method for learning a GP-LVM from iid observations
and for learning non-linear dynamical systems where the observations are
temporally correlated. We show that a benefit of the variational Bayesian
procedure is its robustness to overfitting and its ability to automatically
select the dimensionality of the nonlinear latent space. The resulting
framework is generic, flexible and easy to extend for other purposes, such as
Gaussian process regression with uncertain inputs and semi-supervised Gaussian
processes. We demonstrate our method on synthetic data and standard machine
learning benchmarks, as well as challenging real world datasets, including high
resolution video data.
Spectral Clustering of Graphs with the Bethe Hessian
Authors: Alaa Saade, Florent Krzakala, Lenka Zdeborová
Date: 2014-06-07 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Clustering, Stochastic Block Model

Spectral clustering is a standard approach to label nodes on a graph by
studying the (largest or lowest) eigenvalues of a symmetric real matrix such as
e.g. the adjacency or the Laplacian. Recently, it has been argued that using
instead a more complicated, non-symmetric and higher dimensional operator,
related to the non-backtracking walk on the graph, leads to improved
performance in detecting clusters, and even to optimal performance for the
stochastic block model. Here, we propose to use instead a simpler object, a
symmetric real matrix known as the Bethe Hessian operator, or deformed
Laplacian. We show that this approach combines the performances of the
non-backtracking operator, thus detecting clusters all the way down to the
theoretical limit in the stochastic block model, with the computational,
theoretical and memory advantages of real symmetric matrices.
Real Time Fabric Defect Detection System on an Embedded DSP Platform
Authors: J. L. Raheja, B. Ajay, Ankit Chaudhary
Date: 2014-09-08 00:00:00
Tasks: Defect Detection

In industrial fabric productions, automated real time systems are needed to
find out the minor defects. It will save the cost by not transporting defected
products and also would help in making compmay image of quality fabrics by
sending out only undefected products. A real time fabric defect detection
system (FDDS), implementd on an embedded DSP platform is presented here.
Textural features of fabric image are extracted based on gray level
co-occurrence matrix (GLCM). A sliding window technique is used for defect
detection where window moves over the whole image computing a textural energy
from the GLCM of the fabric image. The energy values are compared to a
reference and the deviations beyond a threshold are reported as defects and
also visually represented by a window. The implementation is carried out on a
TI TMS320DM642 platform and programmed using code composer studio software. The
real time output of this implementation was shown on a monitor.
Accurate, fully-automated NMR spectral profiling for metabolomics
Authors: Siamak Ravanbakhsh, Philip Liu, Trent Bjorndahl, Rupasri Mandal, Jason R. Grant, Michael Wilson, Roman Eisner, Igor Sinelnikov, Xiaoyu Hu, Claudio Luchinat, Russell Greiner, David S. Wishart
Date: 2014-09-04 00:00:00
Tasks: CPU

Many diseases cause significant changes to the concentrations of small
molecules (aka metabolites) that appear in a person's biofluids, which means
such diseases can often be readily detected from a person's "metabolic
profile". This information can be extracted from a biofluid's NMR spectrum.
Today, this is often done manually by trained human experts, which means this
process is relatively slow, expensive and error-prone. This paper presents a
tool, Bayesil, that can quickly, accurately and autonomously produce a complex
biofluid's (e.g., serum or CSF) metabolic profile from a 1D1H NMR spectrum.
This requires first performing several spectral processing steps then matching
the resulting spectrum against a reference compound library, which contains the
"signatures" of each relevant metabolite. Many of these steps are novel
algorithms and our matching step views spectral matching as an inference
problem within a probabilistic graphical model that rapidly approximates the
most probable metabolic profile. Our extensive studies on a diverse set of
complex mixtures, show that Bayesil can autonomously find the concentration of
all NMR-detectable metabolites accurately (~90% correct identification and ~10%
quantification error), in <5minutes on a single CPU. These results demonstrate
that Bayesil is the first fully-automatic publicly-accessible system that
provides quantitative NMR spectral profiling effectively -- with an accuracy
that meets or exceeds the performance of trained experts. We anticipate this
tool will usher in high-throughput metabolomics and enable a wealth of new
applications of NMR in clinical settings. Available at http://www.bayesil.ca.
The Large Margin Mechanism for Differentially Private Maximization
Authors: Kamalika Chaudhuri, Daniel Hsu, Shuang Song
Date: 2014-09-07 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: BIG-bench Machine Learning, Privacy Preserving

A basic problem in the design of privacy-preserving algorithms is the private
maximization problem: the goal is to pick an item from a universe that
(approximately) maximizes a data-dependent function, all under the constraint
of differential privacy. This problem has been used as a sub-routine in many
privacy-preserving algorithms for statistics and machine-learning.
  Previous algorithms for this problem are either range-dependent---i.e., their
utility diminishes with the size of the universe---or only apply to very
restricted function classes. This work provides the first general-purpose,
range-independent algorithm for private maximization that guarantees
approximate differential privacy. Its applicability is demonstrated on two
fundamental tasks in data mining and machine learning.
A Computational Model of the Short-Cut Rule for 2D Shape Decomposition
Authors: Lei Luo, Chunhua Shen, Xinwang Liu, Chunyuan Zhang
Date: 2014-09-07 00:00:00

We propose a new 2D shape decomposition method based on the short-cut rule.
The short-cut rule originates from cognition research, and states that the
human visual system prefers to partition an object into parts using the
shortest possible cuts. We propose and implement a computational model for the
short-cut rule and apply it to the problem of shape decomposition. The model we
proposed generates a set of cut hypotheses passing through the points on the
silhouette which represent the negative minima of curvature. We then show that
most part-cut hypotheses can be eliminated by analysis of local properties of
each. Finally, the remaining hypotheses are evaluated in ascending length
order, which guarantees that of any pair of conflicting cuts only the shortest
will be accepted. We demonstrate that, compared with state-of-the-art shape
decomposition methods, the proposed approach achieves decomposition results
which better correspond to human intuition as revealed in psychological
experiments.
An NLP Assistant for Clide
Authors: Tobias Kortkamp
Date: 2014-09-07 00:00:00
Tasks: Sentence

This report describes an NLP assistant for the collaborative development
environment Clide, that supports the development of NLP applications by
providing easy access to some common NLP data structures. The assistant
visualizes text fragments and their dependencies by displaying the semantic
graph of a sentence, the coreference chain of a paragraph and mined triples
that are extracted from a paragraph's semantic graphs and linked using its
coreference chain. Using this information and a logic programming library, we
create an NLP database which is used by a series of queries to mine the
triples. The algorithm is tested by translating a natural language text
describing a graph to an actual graph that is shown as an annotation in the
text editor.
Depth image hand tracking from an overhead perspective using partially labeled, unbalanced data: Development and real-world testing
Authors: Stephen Czarnuch, Alex Mihailidis
Date: 2014-09-06 00:00:00

We present the development and evaluation of a hand tracking algorithm based
on single depth images captured from an overhead perspective for use in the
COACH prompting system. We train a random decision forest body part classifier
using approximately 5,000 manually labeled, unbalanced, partially labeled
training images. The classifier represents a random subset of pixels in each
depth image with a learned probability density function across all trained body
parts. A local mode-find approach is used to search for clusters present in the
underlying feature space sampled by the classified pixels. In each frame, body
part positions are chosen as the mode with the highest confidence. User hand
positions are translated into hand washing task actions based on proximity to
environmental objects. We validate the performance of the classifier and task
action proposals on a large set of approximately 24,000 manually labeled
images.
Global Convergence of Online Limited Memory BFGS
Authors: Aryan Mokhtari, Alejandro Ribeiro
Date: 2014-09-06 00:00:00

Global convergence of an online (stochastic) limited memory version of the
Broyden-Fletcher- Goldfarb-Shanno (BFGS) quasi-Newton method for solving
optimization problems with stochastic objectives that arise in large scale
machine learning is established. Lower and upper bounds on the Hessian
eigenvalues of the sample functions are shown to suffice to guarantee that the
curvature approximation matrices have bounded determinants and traces, which,
in turn, permits establishing convergence to optimal arguments with probability
1. Numerical experiments on support vector machines with synthetic data
showcase reductions in convergence time relative to stochastic gradient descent
algorithms as well as reductions in storage and computation relative to other
online quasi-Newton methods. Experimental evaluation on a search engine
advertising problem corroborates that these advantages also manifest in
practical applications.