pwc-archive/papers-with-abstracts huggingface dataset:
Scaling SVM and Least Absolute Deviations via Exact Data Reduction
Authors: Jie Wang, Peter Wonka, Jieping Ye
Date: 2013-10-25 00:00:00

The support vector machine (SVM) is a widely used method for classification.
Although many efforts have been devoted to develop efficient solvers, it
remains challenging to apply SVM to large-scale problems. A nice property of
SVM is that the non-support vectors have no effect on the resulting classifier.
Motivated by this observation, we present fast and efficient screening rules to
discard non-support vectors by analyzing the dual problem of SVM via
variational inequalities (DVI). As a result, the number of data instances to be
entered into the optimization can be substantially reduced. Some appealing
features of our screening method are: (1) DVI is safe in the sense that the
vectors discarded by DVI are guaranteed to be non-support vectors; (2) the data
set needs to be scanned only once to run the screening, whose computational
cost is negligible compared to that of solving the SVM problem; (3) DVI is
independent of the solvers and can be integrated with any existing efficient
solvers. We also show that the DVI technique can be extended to detect
non-support vectors in the least absolute deviations regression (LAD). To the
best of our knowledge, there are currently no screening methods for LAD. We
have evaluated DVI on both synthetic and real data sets. Experiments indicate
that DVI significantly outperforms the existing state-of-the-art screening
rules for SVM, and is very effective in discarding non-support vectors for LAD.
The speedup gained by DVI rules can be up to two orders of magnitude.
MLI: An API for Distributed Machine Learning
Authors: Evan R. Sparks, Ameet Talwalkar, Virginia Smith, Jey Kottalam, Xinghao Pan, Joseph Gonzalez, Michael J. Franklin, Michael. I. Jordan, Tim Kraska
Date: 2013-10-21 00:00:00
Tasks: BIG-bench Machine Learning

MLI is an Application Programming Interface designed to address the
challenges of building Machine Learn- ing algorithms in a distributed setting
based on data-centric computing. Its primary goal is to simplify the
development of high-performance, scalable, distributed algorithms. Our initial
results show that, relative to existing systems, this interface can be used to
build distributed implementations of a wide variety of common Machine Learning
algorithms with minimal complexity and highly competitive performance and
scalability.
A feasible roadmap for unsupervised deconvolution of two-source mixed gene expressions
Authors: Niya Wang, Eric P. Hoffman, Robert Clarke, Zhen Zhang, David M. Herrington, Ie-Ming Shih, Douglas A. Levine, Guoqiang Yu, Jianhua Xuan, Yue Wang
Date: 2013-10-25 00:00:00

Tissue heterogeneity is a major confounding factor in studying individual
populations that cannot be resolved directly by global profiling. Experimental
solutions to mitigate tissue heterogeneity are expensive, time consuming,
inapplicable to existing data, and may alter the original gene expression
patterns. Here we ask whether it is possible to deconvolute two-source mixed
expressions (estimating both proportions and cell-specific profiles) from two
or more heterogeneous samples without requiring any prior knowledge. Supported
by a well-grounded mathematical framework, we argue that both constituent
proportions and cell-specific expressions can be estimated in a completely
unsupervised mode when cell-specific marker genes exist, which do not have to
be known a priori, for each of constituent cell types. We demonstrate the
performance of unsupervised deconvolution on both simulation and real gene
expression data, together with perspective discussions.
Predicting the NFL using Twitter
Authors: Shiladitya Sinha, Chris Dyer, Kevin Gimpel, Noah A. Smith
Date: 2013-10-25 00:00:00

We study the relationship between social media output and National Football
League (NFL) games, using a dataset containing messages from Twitter and NFL
game statistics. Specifically, we consider tweets pertaining to specific teams
and games in the NFL season and use them alongside statistical game data to
build predictive models for future game outcomes (which team will win?) and
sports betting outcomes (which team will win with the point spread? will the
total points be over/under the line?). We experiment with several feature sets
and find that simple features using large volumes of tweets can match or exceed
the performance of more traditional features that use game statistics.
Perturbative Corrections for Approximate Inference in Gaussian Latent Variable Models
Authors: Manfred Opper, Ulrich Paquet, Ole Winther
Date: 2013-01-12 00:00:00

Expectation Propagation (EP) provides a framework for approximate inference.
When the model under consideration is over a latent Gaussian field, with the
approximation being Gaussian, we show how these approximations can
systematically be corrected. A perturbative expansion is made of the exact but
intractable correction, and can be applied to the model's partition function
and other moments of interest. The correction is expressed over the
higher-order cumulants which are neglected by EP's local matching of moments.
Through the expansion, we see that EP is correct to first order. By considering
higher orders, corrections of increasing polynomial complexity can be applied
to the approximation. The second order provides a correction in quadratic time,
which we apply to an array of Gaussian process and Ising models. The
corrections generalize to arbitrarily complex approximating families, which we
illustrate on tree-structured Ising model approximations. Furthermore, they
provide a polynomial-time assessment of the approximation error. We also
provide both theoretical and practical insights on the exactness of the EP
solution.
Boosting the concordance index for survival data - a unified framework to derive and evaluate biomarker combinations
Authors: Andreas Mayr, Matthias Schmid
Date: 2013-07-24 00:00:00
Tasks: feature selection

The development of molecular signatures for the prediction of time-to-event
outcomes is a methodologically challenging task in bioinformatics and
biostatistics. Although there are numerous approaches for the derivation of
marker combinations and their evaluation, the underlying methodology often
suffers from the problem that different optimization criteria are mixed during
the feature selection, estimation and evaluation steps. This might result in
marker combinations that are only suboptimal regarding the evaluation criterion
of interest. To address this issue, we propose a unified framework to derive
and evaluate biomarker combinations. Our approach is based on the concordance
index for time-to-event data, which is a non-parametric measure to quantify the
discrimatory power of a prediction rule. Specifically, we propose a
component-wise boosting algorithm that results in linear biomarker combinations
that are optimal with respect to a smoothed version of the concordance index.
We investigate the performance of our algorithm in a large-scale simulation
study and in two molecular data sets for the prediction of survival in breast
cancer patients. Our numerical results show that the new approach is not only
methodologically sound but can also lead to a higher discriminatory power than
traditional approaches for the derivation of gene signatures.
Gender Classification Using Gradient Direction Pattern
Authors: Mohammad shahidul Islam
Date: 2013-10-25 00:00:00
Tasks: Classification, Gender Classification, General Classification

A novel methodology for gender classification is presented in this paper. It
extracts feature from local region of a face using gray color intensity
difference. The facial area is divided into sub-regions and GDP histogram
extracted from those regions are concatenated into a single vector to represent
the face. The classification accuracy obtained by using support vector machine
has outperformed all traditional feature descriptors for gender classification.
It is evaluated on the images collected from FERET database and obtained very
high accuracy.
A Tensor Approach to Learning Mixed Membership Community Models
Authors: Anima Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade
Date: 2013-02-12 00:00:00
Tasks: Community Detection, Stochastic Block Model

Community detection is the task of detecting hidden communities from observed
interactions. Guaranteed community detection has so far been mostly limited to
models with non-overlapping communities such as the stochastic block model. In
this paper, we remove this restriction, and provide guaranteed community
detection for a family of probabilistic network models with overlapping
communities, termed as the mixed membership Dirichlet model, first introduced
by Airoldi et al. This model allows for nodes to have fractional memberships in
multiple communities and assumes that the community memberships are drawn from
a Dirichlet distribution. Moreover, it contains the stochastic block model as a
special case. We propose a unified approach to learning these models via a
tensor spectral decomposition method. Our estimator is based on low-order
moment tensor of the observed network, consisting of 3-star counts. Our
learning method is fast and is based on simple linear algebraic operations,
e.g. singular value decomposition and tensor power iterations. We provide
guaranteed recovery of community memberships and model parameters and present a
careful finite sample analysis of our learning method. As an important special
case, our results match the best known scaling requirements for the
(homogeneous) stochastic block model.
Durkheim Project Data Analysis Report
Authors: Linas Vepstas
Date: 2013-10-24 00:00:00
Tasks: General Classification

This report describes the suicidality prediction models created under the
DARPA DCAPS program in association with the Durkheim Project
[http://durkheimproject.org/]. The models were built primarily from
unstructured text (free-format clinician notes) for several hundred patient
records obtained from the Veterans Health Administration (VHA). The models were
constructed using a genetic programming algorithm applied to bag-of-words and
bag-of-phrases datasets. The influence of additional structured data was
explored but was found to be minor. Given the small dataset size,
classification between cohorts was high fidelity (98%). Cross-validation
suggests these models are reasonably predictive, with an accuracy of 50% to 69%
on five rotating folds, with ensemble averages of 58% to 67%. One particularly
noteworthy result is that word-pairs can dramatically improve classification
accuracy; but this is the case only when one of the words in the pair is
already known to have a high predictive value. By contrast, the set of all
possible word-pairs does not improve on a simple bag-of-words model.
Sockpuppet Detection in Wikipedia: A Corpus of Real-World Deceptive Writing for Linking Identities
Authors: Thamar Solorio, Ragib Hasan, Mainul Mizan
Date: 2013-10-24 00:00:00
Proceeding: LREC 2014 5
Tasks: Benchmarking

This paper describes the corpus of sockpuppet cases we gathered from
Wikipedia. A sockpuppet is an online user account created with a fake identity
for the purpose of covering abusive behavior and/or subverting the editing
regulation process. We used a semi-automated method for crawling and curating a
dataset of real sockpuppet investigation cases. To the best of our knowledge,
this is the first corpus available on real-world deceptive writing. We describe
the process for crawling the data and some preliminary results that can be used
as baseline for benchmarking research. The dataset will be released under a
Creative Commons license from our project website: http://docsig.cis.uab.edu.
Combining Structured and Unstructured Randomness in Large Scale PCA
Authors: Nikos Karampatziakis, Paul Mineiro
Date: 2013-10-23 00:00:00
Tasks: BIG-bench Machine Learning, Outlier Detection

Principal Component Analysis (PCA) is a ubiquitous tool with many
applications in machine learning including feature construction, subspace
embedding, and outlier detection. In this paper, we present an algorithm for
computing the top principal components of a dataset with a large number of rows
(examples) and columns (features). Our algorithm leverages both structured and
unstructured random projections to retain good accuracy while being
computationally efficient. We demonstrate the technique on the winning
submission the KDD 2010 Cup.
Pseudo vs. True Defect Classification in Printed Circuits Boards using Wavelet Features
Authors: Sahil Sikka, Karan Sikka, M. K. Bhuyan, Yuji Iwahori
Date: 2013-10-24 00:00:00
Tasks: General Classification

In recent years, Printed Circuit Boards (PCB) have become the backbone of a
large number of consumer electronic devices leading to a surge in their
production. This has made it imperative to employ automatic inspection systems
to identify manufacturing defects in PCB before they are installed in the
respective systems. An important task in this regard is the classification of
defects as either true or pseudo defects, which decides if the PCB is to be
re-manufactured or not. This work proposes a novel approach to detect most
common defects in the PCBs. The problem has been approached by employing highly
discriminative features based on multi-scale wavelet transform, which are
further boosted by using a kernalized version of the support vector machines
(SVM). A real world printed circuit board dataset has been used for
quantitative analysis. Experimental results demonstrated the efficacy of the
proposed method.
Active Learning of Linear Embeddings for Gaussian Processes
Authors: Roman Garnett, Michael A. Osborne, Philipp Hennig
Date: 2013-10-24 00:00:00
Tasks: Active Learning, Bayesian Optimization, Gaussian Processes, regression

We propose an active learning method for discovering low-dimensional
structure in high-dimensional Gaussian process (GP) tasks. Such problems are
increasingly frequent and important, but have hitherto presented severe
practical difficulties. We further introduce a novel technique for
approximately marginalizing GP hyperparameters, yielding marginal predictions
robust to hyperparameter mis-specification. Our method offers an efficient
means of performing GP regression, quadrature, or Bayesian optimization in
high-dimensional spaces.
Mean Field Bayes Backpropagation: scalable training of multilayer neural networks with binary weights
Authors: Daniel Soudry, Ron Meir
Date: 2013-10-07 00:00:00
Tasks: General Classification

Significant success has been reported recently using deep neural networks for
classification. Such large networks can be computationally intensive, even
after training is over. Implementing these trained networks in hardware chips
with a limited precision of synaptic weights may improve their speed and energy
efficiency by several orders of magnitude, thus enabling their integration into
small and low-power electronic devices. With this motivation, we develop a
computationally efficient learning algorithm for multilayer neural networks
with binary weights, assuming all the hidden neurons have a fan-out of one.
This algorithm, derived within a Bayesian probabilistic online setting, is
shown to work well for both synthetic and real-world problems, performing
comparably to algorithms with real-valued weights, while retaining
computational tractability.
Sparse Predictive Structure of Deconvolved Functional Brain Networks
Authors: Tommaso Furlanello, Marco Cristoforetti, Cesare Furlanello, Giuseppe Jurman
Date: 2013-10-24 00:00:00
Tasks: Classification, Functional Connectivity, General Classification

The functional and structural representation of the brain as a complex
network is marked by the fact that the comparison of noisy and intrinsically
correlated high-dimensional structures between experimental conditions or
groups shuns typical mass univariate methods. Furthermore most network
estimation methods cannot distinguish between real and spurious correlation
arising from the convolution due to nodes' interaction, which thus introduces
additional noise in the data. We propose a machine learning pipeline aimed at
identifying multivariate differences between brain networks associated to
different experimental conditions. The pipeline (1) leverages the deconvolved
individual contribution of each edge and (2) maps the task into a sparse
classification problem in order to construct the associated "sparse deconvolved
predictive network", i.e., a graph with the same nodes of those compared but
whose edge weights are defined by their relevance for out of sample predictions
in classification. We present an application of the proposed method by decoding
the covert attention direction (left or right) based on the single-trial
functional connectivity matrix extracted from high-frequency
magnetoencephalography (MEG) data. Our results demonstrate how network
deconvolution matched with sparse classification methods outperforms typical
approaches for MEG decoding.
Randomized co-training: from cortical neurons to machine learning and back again
Authors: David Balduzzi
Date: 2013-10-24 00:00:00
Tasks: BIG-bench Machine Learning

Despite its size and complexity, the human cortex exhibits striking
anatomical regularities, suggesting there may simple meta-algorithms underlying
cortical learning and computation. We expect such meta-algorithms to be of
interest since they need to operate quickly, scalably and effectively with
little-to-no specialized assumptions.
  This note focuses on a specific question: How can neurons use vast quantities
of unlabeled data to speed up learning from the comparatively rare labels
provided by reward systems? As a partial answer, we propose randomized
co-training as a biologically plausible meta-algorithm satisfying the above
requirements. As evidence, we describe a biologically-inspired algorithm,
Correlated Nystrom Views (XNV) that achieves state-of-the-art performance in
semi-supervised learning, and sketch work in progress on a neuronal
implementation.
Universalities of Reproducing Kernels Revisited
Authors: Benxun Wang, Haizhang Zhang
Date: 2013-10-21 00:00:00
Tasks: Translation

Kernel methods have been widely applied to machine learning and other
questions of approximating an unknown function from its finite sample data. To
ensure arbitrary accuracy of such approximation, various denseness conditions
are imposed on the selected kernel. This note contributes to the study of
universal, characteristic, and $C_0$-universal kernels. We first give simple
and direct description of the difference and relation among these three kinds
of universalities of kernels. We then focus on translation-invariant and
weighted polynomial kernels. A simple and shorter proof of the known
characterization of characteristic translation-invariant kernels will be
presented. The main purpose of the note is to give a delicate discussion on the
universalities of weighted polynomial kernels.
Fast 3D Salient Region Detection in Medical Images using GPUs
Authors: Rahul Thota, Sharan Vaswani, Amit Kale, Nagavijayalakshmi Vydyanathan
Date: 2013-10-24 00:00:00

Automated detection of visually salient regions is an active area of research
in computer vision. Salient regions can serve as inputs for object detectors as
well as inputs for region based registration algorithms. In this paper we
consider the problem of speeding up computationally intensive bottom-up salient
region detection in 3D medical volumes.The method uses the Kadir Brady
formulation of saliency. We show that in the vicinity of a salient region,
entropy is a monotonically increasing function of the degree of overlap of a
candidate window with the salient region. This allows us to initialize a sparse
seed-point grid as the set of tentative salient region centers and iteratively
converge to the local entropy maxima, thereby reducing the computation
complexity compared to the Kadir Brady approach of performing this computation
at every point in the image. We propose two different approaches for achieving
this. The first approach involves evaluating entropy in the four quadrants
around the seed point and iteratively moving in the direction that increases
entropy. The second approach we propose makes use of mean shift tracking
framework to affect entropy maximizing moves. Specifically, we propose the use
of uniform pmf as the target distribution to seek high entropy regions. We
demonstrate the use of our algorithm on medical volumes for left ventricle
detection in PET images and tumor localization in brain MR sequences.
When is an Example a Counterexample?
Authors: Eric Pacuit, Arthur Paul Pedersen, Jan-Willem Romeijn
Date: 2013-10-23 00:00:00

In this extended abstract, we carefully examine a purported counterexample to
a postulate of iterated belief revision. We suggest that the example is better
seen as a failure to apply the theory of belief revision in sufficient detail.
The main contribution is conceptual aiming at the literature on the
philosophical foundations of the AGM theory of belief revision [1]. Our
discussion is centered around the observation that it is often unclear whether
a specific example is a "genuine" counterexample to an abstract theory or a
misapplication of that theory to a concrete case.
Knowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existence
Authors: Jerome Lang, Bruno Zanuttini
Date: 2013-10-23 00:00:00

Knowledge-based programs (KBPs) are high-level protocols describing the
course of action an agent should perform as a function of its knowledge. The
use of KBPs for expressing action policies in AI planning has been surprisingly
overlooked. Given that to each KBP corresponds an equivalent plan and vice
versa, KBPs are typically more succinct than standard plans, but imply more
on-line computation time. Here we make this argument formal, and prove that
there exists an exponential succinctness gap between knowledge-based programs
and standard plans. Then we address the complexity of plan existence. Some
results trivially follow from results already known from the literature on
planning under incomplete knowledge, but many were unknown so far.
Can Facial Uniqueness be Inferred from Impostor Scores?
Authors: Abhishek Dutta, Raymond Veldhuis, Luuk Spreeuwers
Date: 2013-10-23 00:00:00

In Biometrics, facial uniqueness is commonly inferred from impostor
similarity scores. In this paper, we show that such uniqueness measures are
highly unstable in the presence of image quality variations like pose, noise
and blur. We also experimentally demonstrate the instability of a recently
introduced impostor-based uniqueness measure of [Klare and Jain 2013] when
subject to poor quality facial images.
Provable Bounds for Learning Some Deep Representations
Authors: Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma
Date: 2013-10-23 00:00:00

We give algorithms with provable guarantees that learn a class of deep nets
in the generative model view popularized by Hinton and others. Our generative
model is an $n$ node multilayer neural net that has degree at most $n^{\gamma}$
for some $\gamma <1$ and each edge has a random edge weight in $[-1,1]$. Our
algorithm learns {\em almost all} networks in this class with polynomial
running time. The sample complexity is quadratic or cubic depending upon the
details of the model.
  The algorithm uses layerwise learning. It is based upon a novel idea of
observing correlations among features and using these to infer the underlying
edge structure via a global graph recovery procedure. The analysis of the
algorithm reveals interesting structure of neural networks with random edge
weights.