pwc-archive/papers-with-abstracts huggingface dataset:
Patterns in the English Language: Phonological Networks, Percolation and Assembly Models
Authors: Massimo Stella, Markus Brede
Date: 2014-10-16 00:00:00
Tasks: Clustering

In this paper we provide a quantitative framework for the study of
phonological networks (PNs) for the English language by carrying out principled
comparisons to null models, either based on site percolation, randomization
techniques, or network growth models. In contrast to previous work, we mainly
focus on null models that reproduce lower order characteristics of the
empirical data. We find that artificial networks matching connectivity
properties of the English PN are exceedingly rare: this leads to the hypothesis
that the word repertoire might have been assembled over time by preferentially
introducing new words which are small modifications of old words. Our null
models are able to explain the "power-law-like" part of the degree
distributions and generally retrieve qualitative features of the PN such as
high clustering, high assortativity coefficient, and small-world
characteristics. However, the detailed comparison to expectations from null
models also points out significant differences, suggesting the presence of
additional constraints in word assembly. Key constraints we identify are the
avoidance of large degrees, the avoidance of triadic closure, and the avoidance
of large non-percolating clusters.
A Machine Learning Approach to Predicting the Smoothed Complexity of Sorting Algorithms
Authors: Bichen Shi, Michel Schellekens, Georgiana Ifrim
Date: 2015-03-23 00:00:00
Tasks: BIG-bench Machine Learning

Smoothed analysis is a framework for analyzing the complexity of an
algorithm, acting as a bridge between average and worst-case behaviour. For
example, Quicksort and the Simplex algorithm are widely used in practical
applications, despite their heavy worst-case complexity. Smoothed complexity
aims to better characterize such algorithms. Existing theoretical bounds for
the smoothed complexity of sorting algorithms are still quite weak.
Furthermore, empirically computing the smoothed complexity via its original
definition is computationally infeasible, even for modest input sizes. In this
paper, we focus on accurately predicting the smoothed complexity of sorting
algorithms, using machine learning techniques. We propose two regression models
that take into account various properties of sorting algorithms and some of the
known theoretical results in smoothed analysis to improve prediction quality.
We show experimental results for predicting the smoothed complexity of
Quicksort, Mergesort, and optimized Bubblesort for large input sizes, therefore
filling the gap between known theoretical and empirical results.
A Comparative Analysis of Tensor Decomposition Models Using Hyper Spectral Image
Authors: Ankit Gupta, Ashish Oberoi
Date: 2015-03-23 00:00:00
Tasks: Tensor Decomposition

Hyper spectral imaging is a remote sensing technology, providing variety of
applications such as material identification, space object identification,
planetary exploitation etc. It deals with capturing continuum of images of the
earth surface from different angles. Due to the multidimensional nature of the
image, multi-way arrays are one of the possible solutions for analyzing hyper
spectral data. This multi-way array is called tensor. Our approach deals with
implementing three decomposition models LMLRA, BTD and CPD to the sample data
for choosing the best decomposition of the data set. The results have proved
that Block Term Decomposition (BTD) is the best tensor model for decomposing
the hyper spectral image in to resultant factor matrices.
Deep metric learning using Triplet network
Authors: Elad Hoffer, Nir Ailon
Date: 2014-12-20 00:00:00
Tasks: General Classification, Information Retrieval, Metric Learning, Retrieval, Triplet

Deep learning has proven itself as a successful set of models for learning
useful semantic representations of data. These, however, are mostly implicitly
learned as part of a classification task. In this paper we propose the triplet
network model, which aims to learn useful representations by distance
comparisons. A similar model was defined by Wang et al. (2014), tailor made for
learning a ranking for image information retrieval. Here we demonstrate using
various datasets that our model learns a better representation than that of its
immediate competitor, the Siamese network. We also discuss future possible
usage as a framework for unsupervised learning.
Optimum Reject Options for Prototype-based Classification
Authors: Lydia Fischer, Barbara Hammer, Heiko Wersing
Date: 2015-03-23 00:00:00
Tasks: Classification, General Classification

We analyse optimum reject strategies for prototype-based classifiers and
real-valued rejection measures, using the distance of a data point to the
closest prototype or probabilistic counterparts. We compare reject schemes with
global thresholds, and local thresholds for the Voronoi cells of the
classifier. For the latter, we develop a polynomial-time algorithm to compute
optimum thresholds based on a dynamic programming scheme, and we propose an
intuitive linear time, memory efficient approximation thereof with competitive
accuracy. Evaluating the performance in various benchmarks, we conclude that
local reject options are beneficial in particular for simple prototype-based
classifiers, while the improvement is less pronounced for advanced models. For
the latter, an accuracy-reject curve which is comparable to support vector
machine classifiers with state of the art reject options can be reached.
Fuzzy inequational logic
Authors: Vilem Vychodil
Date: 2014-08-08 00:00:00

We present a logic for reasoning about graded inequalities which generalizes
the ordinary inequational logic used in universal algebra. The logic deals with
atomic predicate formulas of the form of inequalities between terms and
formalizes their semantic entailment and provability in graded setting which
allows to draw partially true conclusions from partially true assumptions. We
follow the Pavelka approach and define general degrees of semantic entailment
and provability using complete residuated lattices as structures of truth
degrees. We prove the logic is Pavelka-style complete. Furthermore, we present
a logic for reasoning about graded if-then rules which is obtained as
particular case of the general result.
Training Binary Multilayer Neural Networks for Image Classification using Expectation Backpropagation
Authors: Zhiyong Cheng, Daniel Soudry, Zexi Mao, Zhenzhong Lan
Date: 2015-03-12 00:00:00
Tasks: Binary Classification, General Classification, image-classification, Image Classification

Compared to Multilayer Neural Networks with real weights, Binary Multilayer
Neural Networks (BMNNs) can be implemented more efficiently on dedicated
hardware. BMNNs have been demonstrated to be effective on binary classification
tasks with Expectation BackPropagation (EBP) algorithm on high dimensional text
datasets. In this paper, we investigate the capability of BMNNs using the EBP
algorithm on multiclass image classification tasks. The performances of binary
neural networks with multiple hidden layers and different numbers of hidden
units are examined on MNIST. We also explore the effectiveness of image spatial
filters and the dropout technique in BMNNs. Experimental results on MNIST
dataset show that EBP can obtain 2.12% test error with binary weights and 1.66%
test error with real weights, which is comparable to the results of standard
BackPropagation algorithm on fully connected MNNs.
Construction of FuzzyFind Dictionary using Golay Coding Transformation for Searching Applications
Authors: Kamran Kowsari, Maryam Yammahi, Nima Bari, Roman Vichr, Faisal Alsaby, Simon Y. Berkovich
Date: 2015-03-22 00:00:00

Searching through a large volume of data is very critical for companies,
scientists, and searching engines applications due to time complexity and
memory complexity. In this paper, a new technique of generating FuzzyFind
Dictionary for text mining was introduced. We simply mapped the 23 bits of the
English alphabet into a FuzzyFind Dictionary or more than 23 bits by using more
FuzzyFind Dictionary, and reflecting the presence or absence of particular
letters. This representation preserves closeness of word distortions in terms
of closeness of the created binary vectors within Hamming distance of 2
deviations. This paper talks about the Golay Coding Transformation Hash Table
and how it can be used on a FuzzyFind Dictionary as a new technology for using
in searching through big data. This method is introduced by linear time
complexity for generating the dictionary and constant time complexity to access
the data and update by new data sets, also updating for new data sets is linear
time depends on new data points. This technique is based on searching only for
letters of English that each segment has 23 bits, and also we have more than
23-bit and also it could work with more segments as reference table.
Machine Learning Methods for Attack Detection in the Smart Grid
Authors: Mete Ozay, Inaki Esnaola, Fatos T. Yarman Vural, Sanjeev R. Kulkarni, H. Vincent Poor
Date: 2015-03-22 00:00:00
Tasks: BIG-bench Machine Learning

Attack detection problems in the smart grid are posed as statistical learning
problems for different attack scenarios in which the measurements are observed
in batch or online settings. In this approach, machine learning algorithms are
used to classify measurements as being either secure or attacked. An attack
detection framework is provided to exploit any available prior knowledge about
the system and surmount constraints arising from the sparse structure of the
problem in the proposed approach. Well-known batch and online learning
algorithms (supervised and semi-supervised) are employed with decision and
feature level fusion to model the attack detection problem. The relationships
between statistical and geometric properties of attack vectors employed in the
attack scenarios and learning algorithms are analyzed to detect unobservable
attacks using statistical learning methods. The proposed algorithms are
examined on various IEEE test systems. Experimental analyses show that machine
learning algorithms can detect attacks with performances higher than the attack
detection algorithms which employ state vector estimation methods in the
proposed attack detection framework.
Unsupervised model compression for multilayer bootstrap networks
Authors: Xiao-Lei Zhang
Date: 2015-03-22 00:00:00
Tasks: Dimensionality Reduction, model, Model Compression

Recently, multilayer bootstrap network (MBN) has demonstrated promising
performance in unsupervised dimensionality reduction. It can learn compact
representations in standard data sets, i.e. MNIST and RCV1. However, as a
bootstrap method, the prediction complexity of MBN is high. In this paper, we
propose an unsupervised model compression framework for this general problem of
unsupervised bootstrap methods. The framework compresses a large unsupervised
bootstrap model into a small model by taking the bootstrap model and its
application together as a black box and learning a mapping function from the
input of the bootstrap model to the output of the application by a supervised
learner. To specialize the framework, we propose a new technique, named
compressive MBN. It takes MBN as the unsupervised bootstrap model and deep
neural network (DNN) as the supervised learner. Our initial result on MNIST
showed that compressive MBN not only maintains the high prediction accuracy of
MBN but also is over thousands of times faster than MBN at the prediction
stage. Our result suggests that the new technique integrates the effectiveness
of MBN on unsupervised learning and the effectiveness and efficiency of DNN on
supervised learning together for the effectiveness and efficiency of
compressive MBN on unsupervised learning.
Retrofitting Word Vectors to Semantic Lexicons
Authors: Manaal Faruqui, Jesse Dodge, Sujay K. Jauhar, Chris Dyer, Eduard Hovy, Noah A. Smith
Date: 2014-11-15 00:00:00
Proceeding: HLT 2015 5

Vector space word representations are learned from distributional information
of words in large corpora. Although such statistics are semantically
informative, they disregard the valuable information that is contained in
semantic lexicons such as WordNet, FrameNet, and the Paraphrase Database. This
paper proposes a method for refining vector space representations using
relational information from semantic lexicons by encouraging linked words to
have similar vector representations, and it makes no assumptions about how the
input vectors were constructed. Evaluated on a battery of standard lexical
semantic evaluation tasks in several languages, we obtain substantial
improvements starting with a variety of word vector models. Our refinement
method outperforms prior techniques for incorporating semantic lexicons into
the word vector training algorithms.
Cross-language Wikipedia Editing of Okinawa, Japan
Authors: Scott A. Hale
Date: 2015-01-04 00:00:00
Tasks: Articles

This article analyzes users who edit Wikipedia articles about Okinawa, Japan,
in English and Japanese. It finds these users are among the most active and
dedicated users in their primary languages, where they make many large,
high-quality edits. However, when these users edit in their non-primary
languages, they tend to make edits of a different type that are overall smaller
in size and more often restricted to the narrow set of articles that exist in
both languages. Design changes to motivate wider contributions from users in
their non-primary languages and to encourage multilingual users to transfer
more information across language divides are presented.
Indian Buffet process for model selection in convolved multiple-output Gaussian processes
Authors: Cristian Guarnizo, Mauricio A. Álvarez
Date: 2015-03-22 00:00:00
Tasks: Gaussian Processes, Model Selection, Variational Inference

Multi-output Gaussian processes have received increasing attention during the
last few years as a natural mechanism to extend the powerful flexibility of
Gaussian processes to the setup of multiple output variables. The key point
here is the ability to design kernel functions that allow exploiting the
correlations between the outputs while fulfilling the positive definiteness
requisite for the covariance function. Alternatives to construct these
covariance functions are the linear model of coregionalization and process
convolutions. Each of these methods demand the specification of the number of
latent Gaussian process used to build the covariance function for the outputs.
We propose in this paper, the use of an Indian Buffet process as a way to
perform model selection over the number of latent Gaussian processes. This type
of model is particularly important in the context of latent force models, where
the latent forces are associated to physical quantities like protein profiles
or latent forces in mechanical systems. We use variational inference to
estimate posterior distributions over the variables involved, and show examples
of the model performance over artificial data, a motion capture dataset, and a
gene expression dataset.
Asymmetric Distributions from Constrained Mixtures
Authors: Conrado S. Miranda, Fernando J. Von Zuben
Date: 2015-03-22 00:00:00
Tasks: Time Series, Time Series Analysis

This paper introduces constrained mixtures for continuous distributions,
characterized by a mixture of distributions where each distribution has a shape
similar to the base distribution and disjoint domains. This new concept is used
to create generalized asymmetric versions of the Laplace and normal
distributions, which are shown to define exponential families, with known
conjugate priors, and to have maximum likelihood estimates for the original
parameters, with known closed-form expressions. The asymmetric and symmetric
normal distributions are compared in a linear regression example, showing that
the asymmetric version performs at least as well as the symmetric one, and in a
real world time-series problem, where a hidden Markov model is used to fit a
stock index, indicating that the asymmetric version provides higher likelihood
and may learn distribution models over states and transition distributions with
considerably less entropy.
Modeling browser-based distributed evolutionary computation systems
Authors: Juan Julián Merelo-Guervós, Pablo García-Sánchez
Date: 2015-03-22 00:00:00
Tasks: Cloud Computing, Evolutionary Algorithms

From the era of big science we are back to the "do it yourself", where you do
not have any money to buy clusters or subscribe to grids but still have
algorithms that crave many computing nodes and need them to measure
scalability. Fortunately, this coincides with the era of big data, cloud
computing, and browsers that include JavaScript virtual machines. Those are the
reasons why this paper will focus on two different aspects of volunteer or
freeriding computing: first, the pragmatic: where to find those resources,
which ones can be used, what kind of support you have to give them; and then,
the theoretical: how evolutionary algorithms can be adapted to an environment
in which nodes come and go, have different computing capabilities and operate
in complete asynchrony of each other. We will examine the setup needed to
create a very simple distributed evolutionary algorithm using JavaScript and
then find a model of how users react to it by collecting data from several
experiments featuring different classical benchmark functions.
What the F-measure doesn't measure: Features, Flaws, Fallacies and Fixes
Authors: David M. W. Powers
Date: 2015-03-22 00:00:00
Tasks: BIG-bench Machine Learning, Information Retrieval, Retrieval

The F-measure or F-score is one of the most commonly used single number measures in Information Retrieval, Natural Language Processing and Machine Learning, but it is based on a mistake, and the flawed assumptions render it unsuitable for use in most contexts! Fortunately, there are better alternatives.
Large-scale Log-determinant Computation through Stochastic Chebyshev Expansions
Authors: Insu Han, Dmitry Malioutov, Jinwoo Shin
Date: 2015-03-22 00:00:00
Tasks: Metric Learning

Logarithms of determinants of large positive definite matrices appear
ubiquitously in machine learning applications including Gaussian graphical and
Gaussian process models, partition functions of discrete graphical models,
minimum-volume ellipsoids, metric learning and kernel learning. Log-determinant
computation involves the Cholesky decomposition at the cost cubic in the number
of variables, i.e., the matrix dimension, which makes it prohibitive for
large-scale applications. We propose a linear-time randomized algorithm to
approximate log-determinants for very large-scale positive definite and general
non-singular matrices using a stochastic trace approximation, called the
Hutchinson method, coupled with Chebyshev polynomial expansions that both rely
on efficient matrix-vector multiplications. We establish rigorous additive and
multiplicative approximation error bounds depending on the condition number of
the input matrix. In our experiments, the proposed algorithm can provide very
high accuracy solutions at orders of magnitude faster time than the Cholesky
decomposition and Schur completion, and enables us to compute log-determinants
of matrices involving tens of millions of variables.
Costing Generated Runtime Execution Plans for Large-Scale Machine Learning Programs
Authors: Matthias Boehm
Date: 2015-03-22 00:00:00
Tasks: BIG-bench Machine Learning

Declarative large-scale machine learning (ML) aims at the specification of ML
algorithms in a high-level language and automatic generation of hybrid runtime
execution plans ranging from single node, in-memory computations to distributed
computations on MapReduce (MR) or similar frameworks like Spark. The
compilation of large-scale ML programs exhibits many opportunities for
automatic optimization. Advanced cost-based optimization techniques
require---as a fundamental precondition---an accurate cost model for evaluating
the impact of optimization decisions. In this paper, we share insights into a
simple and robust yet accurate technique for costing alternative runtime
execution plans of ML programs. Our cost model relies on generating and costing
runtime plans in order to automatically reflect all successive optimization
phases. Costing runtime plans also captures control flow structures such as
loops and branches, and a variety of cost factors like IO, latency, and
computation costs. Finally, we linearize all these cost factors into a single
measure of expected execution time. Within SystemML, this cost model is
leveraged by several advanced optimizers like resource optimization and global
data flow optimization. We share our lessons learned in order to provide
foundations for the optimization of ML programs.
Real-time Dynamic MRI Reconstruction using Stacked Denoising Autoencoder
Authors: Angshul Majumdar
Date: 2015-03-22 00:00:00
Tasks: compressed sensing, Denoising, MRI Reconstruction

In this work we address the problem of real-time dynamic MRI reconstruction.
There are a handful of studies on this topic; these techniques are either based
on compressed sensing or employ Kalman Filtering. These techniques cannot
achieve the reconstruction speed necessary for real-time reconstruction. In
this work, we propose a new approach to MRI reconstruction. We learn a
non-linear mapping from the unstructured aliased images to the corresponding
clean images using a stacked denoising autoencoder (SDAE). The training for
SDAE is slow, but the reconstruction is very fast - only requiring a few matrix
vector multiplications. In this work, we have shown that using SDAE one can
reconstruct the MRI frame faster than the data acquisition rate, thereby
achieving real-time reconstruction. The quality of reconstruction is of the
same order as a previous compressed sensing based online reconstruction
technique.
Boosting Convolutional Features for Robust Object Proposals
Authors: Nikolaos Karianakis, Thomas J. Fuchs, Stefano Soatto
Date: 2015-03-21 00:00:00
Tasks: General Classification, image-classification, Image Classification, Object, object-detection, Object Detection, Superpixels

Deep Convolutional Neural Networks (CNNs) have demonstrated excellent
performance in image classification, but still show room for improvement in
object-detection tasks with many categories, in particular for cluttered scenes
and occlusion. Modern detection algorithms like Regions with CNNs (Girshick et
al., 2014) rely on Selective Search (Uijlings et al., 2013) to propose regions
which with high probability represent objects, where in turn CNNs are deployed
for classification. Selective Search represents a family of sophisticated
algorithms that are engineered with multiple segmentation, appearance and
saliency cues, typically coming with a significant run-time overhead.
Furthermore, (Hosang et al., 2014) have shown that most methods suffer from low
reproducibility due to unstable superpixels, even for slight image
perturbations. Although CNNs are subsequently used for classification in
top-performing object-detection pipelines, current proposal methods are
agnostic to how these models parse objects and their rich learned
representations. As a result they may propose regions which may not resemble
high-level objects or totally miss some of them. To overcome these drawbacks we
propose a boosting approach which directly takes advantage of hierarchical CNN
features for detecting regions of interest fast. We demonstrate its performance
on ImageNet 2013 detection benchmark and compare it with state-of-the-art
methods.