pwc-archive/papers-with-abstracts huggingface dataset:
Efficient Learning of Linear Separators under Bounded Noise
Authors: Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Ruth Urner
Date: 2015-03-12 00:00:00
Tasks: Active Learning, Learning Theory

We study the learnability of linear separators in $\Re^d$ in the presence of
bounded (a.k.a Massart) noise. This is a realistic generalization of the random
classification noise model, where the adversary can flip each example $x$ with
probability $\eta(x) \leq \eta$. We provide the first polynomial time algorithm
that can learn linear separators to arbitrarily small excess error in this
noise model under the uniform distribution over the unit ball in $\Re^d$, for
some constant value of $\eta$. While widely studied in the statistical learning
theory community in the context of getting faster convergence rates,
computationally efficient algorithms in this model had remained elusive. Our
work provides the first evidence that one can indeed design algorithms
achieving arbitrarily small excess error in polynomial time under this
realistic noise model and thus opens up a new and exciting line of research.
  We additionally provide lower bounds showing that popular algorithms such as
hinge loss minimization and averaging cannot lead to arbitrarily small excess
error under Massart noise, even under the uniform distribution. Our work
instead, makes use of a margin based technique developed in the context of
active learning. As a result, our algorithm is also an active learning
algorithm with label complexity that is only a logarithmic the desired excess
error $\epsilon$.
LINE: Large-scale Information Network Embedding
Authors: Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, Qiaozhu Mei
Date: 2015-03-12 00:00:00
Tasks: Graph Embedding, Link Prediction, Network Embedding, Node Classification

This paper studies the problem of embedding very large information networks
into low-dimensional vector spaces, which is useful in many tasks such as
visualization, node classification, and link prediction. Most existing graph
embedding methods do not scale for real world information networks which
usually contain millions of nodes. In this paper, we propose a novel network
embedding method called the "LINE," which is suitable for arbitrary types of
information networks: undirected, directed, and/or weighted. The method
optimizes a carefully designed objective function that preserves both the local
and global network structures. An edge-sampling algorithm is proposed that
addresses the limitation of the classical stochastic gradient descent and
improves both the effectiveness and the efficiency of the inference. Empirical
experiments prove the effectiveness of the LINE on a variety of real-world
information networks, including language networks, social networks, and
citation networks. The algorithm is very efficient, which is able to learn the
embedding of a network with millions of vertices and billions of edges in a few
hours on a typical single machine. The source code of the LINE is available
online.
Classification and its applications for drug-target interaction identification
Authors: Jian-Ping Mei, Chee-Keong Kwoh, Peng Yang, Xiao-Li Li
Date: 2015-02-16 00:00:00
Tasks: Classification, Clustering, Drug Discovery, General Classification

Classification is one of the most popular and widely used supervised learning
tasks, which categorizes objects into predefined classes based on known
knowledge. Classification has been an important research topic in machine
learning and data mining. Different classification methods have been proposed
and applied to deal with various real-world problems. Unlike unsupervised
learning such as clustering, a classifier is typically trained with labeled
data before being used to make prediction, and usually achieves higher accuracy
than unsupervised one.
  In this paper, we first define classification and then review several
representative methods. After that, we study in details the application of
classification to a critical problem in drug discovery, i.e., drug-target
prediction, due to the challenges in predicting possible interactions between
drugs and targets.
Background Modelling using Octree Color Quantization
Authors: Aditya A. V. Sastry
Date: 2014-12-05 00:00:00
Tasks: Quantization

By assuming that the most frequently occuring color in a video or a region of
a video I propose a new algorithm for detecting foreground objects in a video.
The process of detecting the foreground objects is complicated because of the
fact that there may be swaying trees, objects of the background being moved
around or lighting changes in the video. To deal with such complexities many
have come up with solutions which heavily rely on expensive floating point
operations. In this paper I used a data structure called Octree which is
implemented only using binary operations. Traditionally octrees were used for
color quantization but here in this paper I used it as a data structure to
store the most frequently occuring colors in a video as well. For each of the
starting few video frames, I constructed a Octree using all the colors of that
frame. Next I pruned all the trees by removing nodes below a certain height and
gave the leaf nodes a color which is dependant on the topological path from
that node to its parent. Hence any two leaf nodes in two different octrees with
the same topological path from themselves to the root will represent the same
color. Next I merged all these individual trees into a single tree retaining
only those nodes whose topological path to itself from the root is most common
among all the trees. The colors represented by the leaf nodes in the resultant
tree will be the most frequently occuring colors in the starting video frames
of the video. Hence any color of an incomming frame that is not close to any of
the colors represented by the leaf node of the merged tree can be regarded as
belonging to a foreground object.
  As an Octree is constructed using only binary operations, it is very fast
compared to other leading algorithms.
A model-based approach to recovering the structure of a plant from images
Authors: Ben Ward, John Bastian, Anton Van Den Hengel, Daniel Pooley, Rajendra Bari, Bettina Berger, Mark Tester
Date: 2015-03-11 00:00:00

We present a method for recovering the structure of a plant directly from a
small set of widely-spaced images. Structure recovery is more complex than
shape estimation, but the resulting structure estimate is more closely related
to phenotype than is a 3D geometric model. The method we propose is applicable
to a wide variety of plants, but is demonstrated on wheat. Wheat is made up of
thin elements with few identifiable features, making it difficult to analyse
using standard feature matching techniques. Our method instead analyses the
structure of plants using only their silhouettes. We employ a generate-and-test
method, using a database of manually modelled leaves and a model for their
composition to synthesise plausible plant structures which are evaluated
against the images. The method is capable of efficiently recovering accurate
estimates of plant structure in a wide variety of imaging scenarios, with no
manual intervention.
Describing and Understanding Neighborhood Characteristics through Online Social Media
Authors: Mohamed Kafsi, Henriette Cramer, Bart Thomee, David A. Shamma
Date: 2015-03-11 00:00:00
Tasks: Descriptive

Geotagged data can be used to describe regions in the world and discover
local themes. However, not all data produced within a region is necessarily
specifically descriptive of that area. To surface the content that is
characteristic for a region, we present the geographical hierarchy model (GHM),
a probabilistic model based on the assumption that data observed in a region is
a random mixture of content that pertains to different levels of a hierarchy.
We apply the GHM to a dataset of 8 million Flickr photos in order to
discriminate between content (i.e., tags) that specifically characterizes a
region (e.g., neighborhood) and content that characterizes surrounding areas or
more general themes. Knowledge of the discriminative and non-discriminative
terms used throughout the hierarchy enables us to quantify the uniqueness of a
given region and to compare similar but distant regions. Our evaluation
demonstrates that our model improves upon traditional Naive Bayes
classification by 47% and hierarchical TF-IDF by 27%. We further highlight the
differences and commonalities with human reasoning about what is locally
characteristic for a neighborhood, distilled from ten interviews and a survey
that covered themes such as time, events, and prior regional knowledge
Switching to Learn
Authors: Shahin Shahrampour, Mohammad Amin Rahimian, Ali Jadbabaie
Date: 2015-03-11 00:00:00

A network of agents attempt to learn some unknown state of the world drawn by
nature from a finite set. Agents observe private signals conditioned on the
true state, and form beliefs about the unknown state accordingly. Each agent
may face an identification problem in the sense that she cannot distinguish the
truth in isolation. However, by communicating with each other, agents are able
to benefit from side observations to learn the truth collectively. Unlike many
distributed algorithms which rely on all-time communication protocols, we
propose an efficient method by switching between Bayesian and non-Bayesian
regimes. In this model, agents exchange information only when their private
signals are not informative enough; thence, by switching between the two
regimes, agents efficiently learn the truth using only a few rounds of
communications. The proposed algorithm preserves learnability while incurring a
lower communication cost. We also verify our theoretical findings by simulation
examples.
Directed Information Graphs
Authors: Christopher J. Quinn, Negar Kiyavash, Todd P. Coleman
Date: 2012-04-09 00:00:00

We propose a graphical model for representing networks of stochastic
processes, the minimal generative model graph. It is based on reduced
factorizations of the joint distribution over time. We show that under
appropriate conditions, it is unique and consistent with another type of
graphical model, the directed information graph, which is based on a
generalization of Granger causality. We demonstrate how directed information
quantifies Granger causality in a particular sequential prediction setting. We
also develop efficient methods to estimate the topological structure from data
that obviate estimating the joint statistics. One algorithm assumes
upper-bounds on the degrees and uses the minimal dimension statistics
necessary. In the event that the upper-bounds are not valid, the resulting
graph is nonetheless an optimal approximation. Another algorithm uses
near-minimal dimension statistics when no bounds are known but the distribution
satisfies a certain criterion. Analogous to how structure learning algorithms
for undirected graphical models use mutual information estimates, these
algorithms use directed information estimates. We characterize the
sample-complexity of two plug-in directed information estimators and obtain
confidence intervals. For the setting when point estimates are unreliable, we
propose an algorithm that uses confidence intervals to identify the best
approximation that is robust to estimation error. Lastly, we demonstrate the
effectiveness of the proposed algorithms through analysis of both synthetic
data and real data from the Twitter network. In the latter case, we identify
which news sources influence users in the network by merely analyzing tweet
times.
Appearance-based indoor localization: A comparison of patch descriptor performance
Authors: Jose Rivera-Rubio, Ioannis Alexiou, Anil A. Bharath
Date: 2015-03-11 00:00:00
Tasks: Indoor Localization, Position, Simultaneous Localization and Mapping

Vision is one of the most important of the senses, and humans use it
extensively during navigation. We evaluated different types of image and video
frame descriptors that could be used to determine distinctive visual landmarks
for localizing a person based on what is seen by a camera that they carry. To
do this, we created a database containing over 3 km of video-sequences with
ground-truth in the form of distance travelled along different corridors. Using
this database, the accuracy of localization - both in terms of knowing which
route a user is on - and in terms of position along a certain route, can be
evaluated. For each type of descriptor, we also tested different techniques to
encode visual structure and to search between journeys to estimate a user's
position. The techniques include single-frame descriptors, those using
sequences of frames, and both colour and achromatic descriptors. We found that
single-frame indexing worked better within this particular dataset. This might
be because the motion of the person holding the camera makes the video too
dependent on individual steps and motions of one particular journey. Our
results suggest that appearance-based information could be an additional source
of navigational data indoors, augmenting that provided by, say, radio signal
strength indicators (RSSIs). Such visual information could be collected by
crowdsourcing low-resolution video feeds, allowing journeys made by different
users to be associated with each other, and location to be inferred without
requiring explicit mapping. This offers a complementary approach to methods
based on simultaneous localization and mapping (SLAM) algorithms.
Diverse Landmark Sampling from Determinantal Point Processes for Scalable Manifold Learning
Authors: Christian Wachinger, Polina Golland
Date: 2015-03-11 00:00:00
Tasks: Dimensionality Reduction, Point Processes

High computational costs of manifold learning prohibit its application for
large point sets. A common strategy to overcome this problem is to perform
dimensionality reduction on selected landmarks and to successively embed the
entire dataset with the Nystr\"om method. The two main challenges that arise
are: (i) the landmarks selected in non-Euclidean geometries must result in a
low reconstruction error, (ii) the graph constructed from sparsely sampled
landmarks must approximate the manifold well. We propose the sampling of
landmarks from determinantal distributions on non-Euclidean spaces. Since
current determinantal sampling algorithms have the same complexity as those for
manifold learning, we present an efficient approximation running in linear
time. Further, we recover the local geometry after the sparsification by
assigning each landmark a local covariance matrix, estimated from the original
point set. The resulting neighborhood selection based on the Bhattacharyya
distance improves the embedding of sparsely sampled manifolds. Our experiments
show a significant performance improvement compared to state-of-the-art
landmark selection techniques.
Computational Lower Bounds for Community Detection on Random Graphs
Authors: Bruce Hajek, Yihong Wu, Jiaming Xu
Date: 2014-06-25 00:00:00
Tasks: Community Detection

This paper studies the problem of detecting the presence of a small dense
community planted in a large Erd\H{o}s-R\'enyi random graph $\mathcal{G}(N,q)$,
where the edge probability within the community exceeds $q$ by a constant
factor. Assuming the hardness of the planted clique detection problem, we show
that the computational complexity of detecting the community exhibits the
following phase transition phenomenon: As the graph size $N$ grows and the
graph becomes sparser according to $q=N^{-\alpha}$, there exists a critical
value of $\alpha = \frac{2}{3}$, below which there exists a computationally
intensive procedure that can detect far smaller communities than any
computationally efficient procedure, and above which a linear-time procedure is
statistically optimal. The results also lead to the average-case hardness
results for recovering the dense community and approximating the densest
$K$-subgraph.
Properties of simple sets in digital spaces. Contractions of simple sets preserving the homotopy type of a digital space
Authors: Alexander V. Evako
Date: 2015-03-11 00:00:00

A point of a digital space is called simple if it can be deleted from the
space without altering topology. This paper introduces the notion simple set of
points of a digital space. The definition is based on contractible spaces and
contractible transformations. A set of points in a digital space is called
simple if it can be contracted to a point without changing topology of the
space. It is shown that contracting a simple set of points does not change the
homotopy type of a digital space, and the number of points in a digital space
without simple points can be reduces by contracting simple sets. Using the
process of contracting, we can substantially compress a digital space while
preserving the topology. The paper proposes a method for thinning a digital
space which shows that this approach can contribute to computer science such as
medical imaging, computer graphics and pattern analysis.
Principal Sensitivity Analysis
Authors: Sotetsu Koyamada, Masanori Koyama, Ken Nakae, Shin Ishii
Date: 2014-12-21 00:00:00
Tasks: BIG-bench Machine Learning, Sensitivity

We present a novel algorithm (Principal Sensitivity Analysis; PSA) to analyze
the knowledge of the classifier obtained from supervised machine learning
techniques. In particular, we define principal sensitivity map (PSM) as the
direction on the input space to which the trained classifier is most sensitive,
and use analogously defined k-th PSM to define a basis for the input space. We
train neural networks with artificial data and real data, and apply the
algorithm to the obtained supervised classifiers. We then visualize the PSMs to
demonstrate the PSA's ability to decompose the knowledge acquired by the
trained classifiers.
Automatic Unsupervised Tensor Mining with Quality Assessment
Authors: Evangelos E. Papalexakis
Date: 2015-03-11 00:00:00
Tasks: Tensor Decomposition

A popular tool for unsupervised modelling and mining multi-aspect data is
tensor decomposition. In an exploratory setting, where and no labels or ground
truth are available how can we automatically decide how many components to
extract? How can we assess the quality of our results, so that a domain expert
can factor this quality measure in the interpretation of our results? In this
paper, we introduce AutoTen, a novel automatic unsupervised tensor mining
algorithm with minimal user intervention, which leverages and improves upon
heuristics that assess the result quality. We extensively evaluate AutoTen's
performance on synthetic data, outperforming existing baselines on this very
hard problem. Finally, we apply AutoTen on a variety of real datasets,
providing insights and discoveries. We view this work as a step towards a fully
automated, unsupervised tensor mining tool that can be easily adopted by
practitioners in academia and industry.
Representative Selection for Big Data via Sparse Graph and Geodesic Grassmann Manifold Distance
Authors: Chinh Dang, Hayder Radha
Date: 2014-05-07 00:00:00
Tasks: Clustering, Video Summarization

This paper addresses the problem of identifying a very small subset of data
points that belong to a significantly larger massive dataset (i.e., Big Data).
The small number of selected data points must adequately represent and
faithfully characterize the massive Big Data. Such identification process is
known as representative selection [19]. We propose a novel representative
selection framework by generating an l1 norm sparse graph for a given Big-Data
dataset. The Big Data is partitioned recursively into clusters using a spectral
clustering algorithm on the generated sparse graph. We consider each cluster as
one point in a Grassmann manifold, and measure the geodesic distance among
these points. The distances are further analyzed using a min-max algorithm [1]
to extract an optimal subset of clusters. Finally, by considering a sparse
subgraph of each selected cluster, we detect a representative using principal
component centrality [11]. We refer to the proposed representative selection
framework as a Sparse Graph and Grassmann Manifold (SGGM) based approach. To
validate the proposed SGGM framework, we apply it onto the problem of video
summarization where only few video frames, known as key frames, are selected
among a much longer video sequence. A comparison of the results obtained by the
proposed algorithm with the ground truth, which is agreed by multiple human
judges, and with some state-of-the-art methods clearly indicates the viability
of the SGGM framework.
A Novel Hybrid CNN-AIS Visual Pattern Recognition Engine
Authors: Vandna Bhalla, Santanu Chaudhury, Arihant Jain
Date: 2015-03-11 00:00:00
Tasks: Small Data Image Classification

Machine learning methods are used today for most recognition problems.
Convolutional Neural Networks (CNN) have time and again proved successful for
many image processing tasks primarily for their architecture. In this paper we
propose to apply CNN to small data sets like for example, personal albums or
other similar environs where the size of training dataset is a limitation,
within the framework of a proposed hybrid CNN-AIS model. We use Artificial
Immune System Principles to enhance small size of training data set. A layer of
Clonal Selection is added to the local filtering and max pooling of CNN
Architecture. The proposed Architecture is evaluated using the standard MNIST
dataset by limiting the data size and also with a small personal data sample
belonging to two different classes. Experimental results show that the proposed
hybrid CNN-AIS based recognition engine works well when the size of training
data is limited in size
Convolutional Neural Network Architectures for Matching Natural Language Sentences
Authors: Baotian Hu, Zhengdong Lu, Hang Li, Qingcai Chen
Date: 2015-03-11 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Question Answering

Semantic matching is of central importance to many natural language tasks
\cite{bordes2014semantic,RetrievalQA}. A successful matching algorithm needs to
adequately model the internal structures of language objects and the
interaction between them. As a step toward this goal, we propose convolutional
neural network models for matching two sentences, by adapting the convolutional
strategy in vision and speech. The proposed models not only nicely represent
the hierarchical structures of sentences with their layer-by-layer composition
and pooling, but also capture the rich matching patterns at different levels.
Our models are rather generic, requiring no prior knowledge on language, and
can hence be applied to matching tasks of different nature and in different
languages. The empirical study on a variety of matching tasks demonstrates the
efficacy of the proposed model on a variety of matching tasks and its
superiority to competitor models.
Scalable Discovery of Time-Series Shapelets
Authors: Josif Grabocka, Martin Wistuba, Lars Schmidt-Thieme
Date: 2015-03-11 00:00:00
Tasks: Clustering, General Classification, Online Clustering, Prediction, Time Series, Time Series Analysis, Time Series Classification

Time-series classification is an important problem for the data mining
community due to the wide range of application domains involving time-series
data. A recent paradigm, called shapelets, represents patterns that are highly
predictive for the target variable. Shapelets are discovered by measuring the
prediction accuracy of a set of potential (shapelet) candidates. The candidates
typically consist of all the segments of a dataset, therefore, the discovery of
shapelets is computationally expensive. This paper proposes a novel method that
avoids measuring the prediction accuracy of similar candidates in Euclidean
distance space, through an online clustering pruning technique. In addition,
our algorithm incorporates a supervised shapelet selection that filters out
only those candidates that improve classification accuracy. Empirical evidence
on 45 datasets from the UCR collection demonstrate that our method is 3-4
orders of magnitudes faster than the fastest existing shapelet-discovery
method, while providing better prediction accuracy.