pwc-archive/papers-with-abstracts huggingface dataset:
Local algorithms for interactive clustering
Authors: Pranjal Awasthi, Maria-Florina Balcan, Konstantin Voevodski
Date: 2013-12-24 00:00:00
Tasks: Clustering

We study the design of interactive clustering algorithms for data sets
satisfying natural stability assumptions. Our algorithms start with any initial
clustering and only make local changes in each step; both are desirable
features in many applications. We show that in this constrained setting one can
still design provably efficient algorithms that produce accurate clusterings.
We also show that our algorithms perform well on real-world data.
Rank Subspace Learning for Compact Hash Codes
Authors: Kai Li, Guo-Jun Qi, Jun Ye, Kien A. Hua
Date: 2015-03-19 00:00:00

The era of Big Data has spawned unprecedented interests in developing hashing
algorithms for efficient storage and fast nearest neighbor search. Most
existing work learn hash functions that are numeric quantizations of feature
values in projected feature space. In this work, we propose a novel hash
learning framework that encodes feature's rank orders instead of numeric values
in a number of optimal low-dimensional ranking subspaces. We formulate the
ranking subspace learning problem as the optimization of a piece-wise linear
convex-concave function and present two versions of our algorithm: one with
independent optimization of each hash bit and the other exploiting a sequential
learning framework. Our work is a generalization of the Winner-Take-All (WTA)
hash family and naturally enjoys all the numeric stability benefits of rank
correlation measures while being optimized to achieve high precision at very
short code length. We compare with several state-of-the-art hashing algorithms
in both supervised and unsupervised domain, showing superior performance in a
number of data sets.
Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming
Authors: Yuxin Chen, Yuejie Chi, Andrea Goldsmith
Date: 2013-10-02 00:00:00
Tasks: Retrieval

Statistical inference and information processing of high-dimensional data
often require efficient and accurate estimation of their second-order
statistics. With rapidly changing data, limited processing power and storage at
the acquisition devices, it is desirable to extract the covariance structure
from a single pass over the data and a small number of stored measurements. In
this paper, we explore a quadratic (or rank-one) measurement model which
imposes minimal memory requirements and low computational complexity during the
sampling process, and is shown to be optimal in preserving various
low-dimensional covariance structures. Specifically, four popular structural
assumptions of covariance matrices, namely low rank, Toeplitz low rank,
sparsity, jointly rank-one and sparse structure, are investigated, while
recovery is achieved via convex relaxation paradigms for the respective
structure.
  The proposed quadratic sampling framework has a variety of potential
applications including streaming data processing, high-frequency wireless
communication, phase space tomography and phase retrieval in optics, and
non-coherent subspace detection. Our method admits universally accurate
covariance estimation in the absence of noise, as soon as the number of
measurements exceeds the information theoretic limits. We also demonstrate the
robustness of this approach against noise and imperfect structural assumptions.
Our analysis is established upon a novel notion called the mixed-norm
restricted isometry property (RIP-$\ell_{2}/\ell_{1}$), as well as the
conventional RIP-$\ell_{2}/\ell_{2}$ for near-isotropic and bounded
measurements. In addition, our results improve upon the best-known phase
retrieval (including both dense and sparse signals) guarantees using PhaseLift
with a significantly simpler approach.
Reduced Basis Decomposition: a Certified and Fast Lossy Data Compression Algorithm
Authors: Yanlai Chen
Date: 2015-03-19 00:00:00
Tasks: Data Compression, Dimensionality Reduction

Dimension reduction is often needed in the area of data mining. The goal of
these methods is to map the given high-dimensional data into a low-dimensional
space preserving certain properties of the initial data. There are two kinds of
techniques for this purpose. The first, projective methods, builds an explicit
linear projection from the high-dimensional space to the low-dimensional one.
On the other hand, the nonlinear methods utilizes nonlinear and implicit
mapping between the two spaces. In both cases, the methods considered in
literature have usually relied on computationally very intensive matrix
factorizations, frequently the Singular Value Decomposition (SVD). The
computational burden of SVD quickly renders these dimension reduction methods
infeasible thanks to the ever-increasing sizes of the practical datasets.
  In this paper, we present a new decomposition strategy, Reduced Basis
Decomposition (RBD), which is inspired by the Reduced Basis Method (RBM). Given
$X$ the high-dimensional data, the method approximates it by $Y \, T (\approx
X)$ with $Y$ being the low-dimensional surrogate and $T$ the transformation
matrix. $Y$ is obtained through a greedy algorithm thus extremely efficient. In
fact, it is significantly faster than SVD with comparable accuracy. $T$ can be
computed on the fly. Moreover, unlike many compression algorithms, it easily
finds the mapping for an arbitrary ``out-of-sample'' vector and it comes with
an ``error indicator'' certifying the accuracy of the compression. Numerical
results are shown validating these claims.
On Invariance and Selectivity in Representation Learning
Authors: Fabio Anselmi, Lorenzo Rosasco, Tomaso Poggio
Date: 2015-03-19 00:00:00
Tasks: Representation Learning

We discuss data representation which can be learned automatically from data,
are invariant to transformations, and at the same time selective, in the sense
that two points have the same representation only if they are one the
transformation of the other. The mathematical results here sharpen some of the
key claims of i-theory -- a recent theory of feedforward processing in sensory
cortex.
Syntagma Lexical Database
Authors: Daniel Christen
Date: 2015-03-19 00:00:00
Tasks: LEMMA, POS

This paper discusses the structure of Syntagma's Lexical Database (focused on
Italian). The basic database consists in four tables. Table Forms contains word
inflections, used by the POS-tagger for the identification of input-words.
Forms is related to Lemma. Table Lemma stores all kinds of grammatical features
of words, word-level semantic data and restrictions. In the table Meanings
meaning-related data are stored: definition, examples, domain, and semantic
information. Table Valency contains the argument structure of each meaning,
with syntactic and semantic features for each argument. The extended version of
SLD contains the links to Syntagma's Semantic Net and to the WordNet synsets of
other languages.
Deep Transform: Time-Domain Audio Error Correction via Probabilistic Re-Synthesis
Authors: Andrew J. R. Simpson
Date: 2015-03-19 00:00:00

In the process of recording, storage and transmission of time-domain audio
signals, errors may be introduced that are difficult to correct in an
unsupervised way. Here, we train a convolutional deep neural network to
re-synthesize input time-domain speech signals at its output layer. We then use
this abstract transformation, which we call a deep transform (DT), to perform
probabilistic re-synthesis on further speech (of the same speaker) which has
been degraded. Using the convolutive DT, we demonstrate the recovery of speech
audio that has been subject to extreme degradation. This approach may be useful
for correction of errors in communications devices.
Neural Network-Based Active Learning in Multivariate Calibration
Authors: A. Ukil, J. Bernasconi
Date: 2015-03-19 00:00:00
Tasks: Active Learning

In chemometrics, data from infrared or near-infrared (NIR) spectroscopy are
often used to identify a compound or to analyze the composition of amaterial.
This involves the calibration of models that predict the concentration
ofmaterial constituents from the measured NIR spectrum. An interesting aspect
of multivariate calibration is to achieve a particular accuracy level with a
minimum number of training samples, as this reduces the number of laboratory
tests and thus the cost of model building. In these chemometric models, the
input refers to a proper representation of the spectra and the output to the
concentrations of the sample constituents. The search for a most informative
new calibration sample thus has to be performed in the output space of the
model, rather than in the input space as in conventionalmodeling problems. In
this paper, we propose to solve the corresponding inversion problem by
utilizing the disagreements of an ensemble of neural networks to represent the
prediction error in the unexplored component space. The next calibration sample
is then chosen at a composition where the individual models of the ensemble
disagree most. The results obtained for a realistic chemometric calibration
example show that the proposed active learning can achieve a given calibration
accuracy with less training samples than random sampling.
Sign Language Fingerspelling Classification from Depth and Color Images using a Deep Belief Network
Authors: Lucas Rioux-Maldague, Philippe Giguère
Date: 2015-03-19 00:00:00
Tasks: General Classification, Sign Language Recognition

Automatic sign language recognition is an open problem that has received a
lot of attention recently, not only because of its usefulness to signers, but
also due to the numerous applications a sign classifier can have. In this
article, we present a new feature extraction technique for hand pose
recognition using depth and intensity images captured from a Microsoft Kinect
sensor. We applied our technique to American Sign Language fingerspelling
classification using a Deep Belief Network, for which our feature extraction
technique is tailored. We evaluated our results on a multi-user data set with
two scenarios: one with all known users and one with an unseen user. We
achieved 99% recall and precision on the first, and 77% recall and 79%
precision on the second. Our method is also capable of real-time sign
classification and is adaptive to any environment or lightning intensity.
Machine Learning in Wireless Sensor Networks: Algorithms, Strategies, and Applications
Authors: Mohammad Abu Alsheikh, Shaowei Lin, Dusit Niyato, Hwee-Pink Tan
Date: 2014-05-18 00:00:00
Tasks: BIG-bench Machine Learning

Wireless sensor networks monitor dynamic environments that change rapidly
over time. This dynamic behavior is either caused by external factors or
initiated by the system designers themselves. To adapt to such conditions,
sensor networks often adopt machine learning techniques to eliminate the need
for unnecessary redesign. Machine learning also inspires many practical
solutions that maximize resource utilization and prolong the lifespan of the
network. In this paper, we present an extensive literature review over the
period 2002-2013 of machine learning methods that were used to address common
issues in wireless sensor networks (WSNs). The advantages and disadvantages of
each proposed algorithm are evaluated against the corresponding problem. We
also provide a comparative guide to aid WSN designers in developing suitable
machine learning solutions for their specific application challenges.
A General Framework for Multi-focal Image Classification and Authentication: Application to Microscope Pollen Images
Authors: François Chung, Tomás Rodríguez
Date: 2015-03-19 00:00:00
Tasks: Classification, Clustering, General Classification, image-classification, Image Classification, Robust classification

In this article, we propose a general framework for multi-focal image
classification and authentication, the methodology being demonstrated on
microscope pollen images. The framework is meant to be generic and based on a
brute force-like approach aimed to be efficient not only on any kind, and any
number, of pollen images (regardless of the pollen type), but also on any kind
of multi-focal images. All stages of the framework's pipeline are designed to
be used in an automatic fashion. First, the optimal focus is selected using the
absolute gradient method. Then, pollen grains are extracted using a
coarse-to-fine approach involving both clustering and morphological techniques
(coarse stage), and a snake-based segmentation (fine stage). Finally, features
are extracted and selected using a generalized approach, and their
classification is tested with four classifiers: Weighted Neighbor Distance,
Neural Network, Decision Tree and Random Forest. The latter method, which has
shown the best and more robust classification accuracy results (above 97\% for
any number of pollen types), is finally used for the authentication stage.
Learning Hypergraph-regularized Attribute Predictors
Authors: Sheng Huang, Mohamed Elhoseiny, Ahmed Elgammal, Dan Yang
Date: 2015-03-19 00:00:00
Proceeding: CVPR 2015 6
Tasks: Attribute, hypergraph embedding

We present a novel attribute learning framework named Hypergraph-based
Attribute Predictor (HAP). In HAP, a hypergraph is leveraged to depict the
attribute relations in the data. Then the attribute prediction problem is
casted as a regularized hypergraph cut problem in which HAP jointly learns a
collection of attribute projections from the feature space to a hypergraph
embedding space aligned with the attribute space. The learned projections
directly act as attribute classifiers (linear and kernelized). This formulation
leads to a very efficient approach. By considering our model as a multi-graph
cut task, our framework can flexibly incorporate other available information,
in particular class label. We apply our approach to attribute prediction,
Zero-shot and $N$-shot learning tasks. The results on AWA, USAA and CUB
databases demonstrate the value of our methods in comparison with the
state-of-the-art approaches.
Automatic Pollen Grain and Exine Segmentation from Microscope Images
Authors: François Chung, Tomás Rodríguez
Date: 2015-03-19 00:00:00
Tasks: Clustering, Segmentation

In this article, we propose an automatic method for the segmentation of
pollen grains from microscope images, followed by the automatic segmentation of
their exine. The objective of exine segmentation is to separate the pollen
grain in two regions of interest: exine and inner part. A coarse-to-fine
approach ensures a smooth and accurate segmentation of both structures. As a
rough stage, grain segmentation is performed by a procedure involving
clustering and morphological operations, while the exine is approximated by an
iterative procedure consisting in consecutive cropping steps of the pollen
grain. A snake-based segmentation is performed to refine the segmentation of
both structures. Results have shown that our segmentation method is able to
deal with different pollen types, as well as with different types of exine and
inner part appearance. The proposed segmentation method aims to be generic and
has been designed as one of the core steps of an automatic pollen
classification framework.
Implementation of a Practical Distributed Calculation System with Browsers and JavaScript, and Application to Distributed Deep Learning
Authors: Ken Miura, Tatsuya Harada
Date: 2015-03-19 00:00:00
Tasks: Deep Learning

Deep learning can achieve outstanding results in various fields. However, it
requires so significant computational power that graphics processing units
(GPUs) and/or numerous computers are often required for the practical
application. We have developed a new distributed calculation framework called
"Sashimi" that allows any computer to be used as a distribution node only by
accessing a website. We have also developed a new JavaScript neural network
framework called "Sukiyaki" that uses general purpose GPUs with web browsers.
Sukiyaki performs 30 times faster than a conventional JavaScript library for
deep convolutional neural networks (deep CNNs) learning. The combination of
Sashimi and Sukiyaki, as well as new distribution algorithms, demonstrates the
distributed deep learning of deep CNNs only with web browsers on various
devices. The libraries that comprise the proposed methods are available under
MIT license at http://mil-tokyo.github.io/.
An approach to improving edge detection for facial and remotely sensed images using vector order statistics
Authors: B O. Sadiq, S. M. Sani, S. Garba
Date: 2015-03-19 00:00:00
Tasks: Edge Detection

This paper presents an improved edge detection algorithm for facial and
remotely sensed images using vector order statistics. The developed algorithm
processes colored images directly without been converted to gray scale. A
number of the existing algorithms converts the colored images into gray scale
before detection of edges. But this process leads to inaccurate precision of
recognized edges, thus producing false and broken edges in the output edge map.
Facial and remotely sensed images consist of curved edge lines which have to be
detected continuously to prevent broken edges. In order to deal with this, a
collection of pixel approach is introduced with a view to minimizing the false
and broken edges that exists in the generated output edge map of facial and
remotely sensed images.
Edge Detection: A Collection of Pixel based Approach for Colored Images
Authors: B O. Sadiq, S. M. Sani, S. Garba
Date: 2015-03-19 00:00:00
Tasks: Edge Detection

The existing traditional edge detection algorithms process a single pixel on
an image at a time, thereby calculating a value which shows the edge magnitude
of the pixel and the edge orientation. Most of these existing algorithms
convert the coloured images into gray scale before detection of edges. However,
this process leads to inaccurate precision of recognized edges, thus producing
false and broken edges in the image. This paper presents a profile modelling
scheme for collection of pixels based on the step and ramp edges, with a view
to reducing the false and broken edges present in the image. The collection of
pixel scheme generated is used with the Vector Order Statistics to reduce the
imprecision of recognized edges when converting from coloured to gray scale
images. The Pratt Figure of Merit (PFOM) is used as a quantitative comparison
between the existing traditional edge detection algorithm and the developed
algorithm as a means of validation. The PFOM value obtained for the developed
algorithm is 0.8480, which showed an improvement over the existing traditional
edge detection algorithms.
Non-parametric Bayesian Models of Response Function in Dynamic Image Sequences
Authors: Ondřej Tichý, Václav Šmídl
Date: 2015-03-19 00:00:00
Tasks: blind source separation

Estimation of response functions is an important task in dynamic medical
imaging. This task arises for example in dynamic renal scintigraphy, where
impulse response or retention functions are estimated, or in functional
magnetic resonance imaging where hemodynamic response functions are required.
These functions can not be observed directly and their estimation is
complicated because the recorded images are subject to superposition of
underlying signals. Therefore, the response functions are estimated via blind
source separation and deconvolution. Performance of this algorithm heavily
depends on the used models of the response functions. Response functions in
real image sequences are rather complicated and finding a suitable parametric
form is problematic. In this paper, we study estimation of the response
functions using non-parametric Bayesian priors. These priors were designed to
favor desirable properties of the functions, such as sparsity or smoothness.
These assumptions are used within hierarchical priors of the blind source
separation and deconvolution algorithm. Comparison of the resulting algorithms
with these priors is performed on synthetic dataset as well as on real datasets
from dynamic renal scintigraphy. It is shown that flexible non-parametric
priors improve estimation of response functions in both cases. MATLAB
implementation of the resulting algorithms is freely available for download.
BitSim: An Algebraic Similarity Measure for Description Logics Concepts
Authors: Sourish Dasgupta, Gaurav Maheshwari, Priyansh Trivedi
Date: 2015-03-19 00:00:00
Tasks: Semantic correspondence, Semantic Similarity, Semantic Textual Similarity

In this paper, we propose an algebraic similarity measure {\sigma}BS (BS
stands for BitSim) for assigning semantic similarity score to concept
definitions in ALCH+ an expressive fragment of Description Logics (DL). We
define an algebraic interpretation function, I_B, that maps a concept
definition to a unique string ({\omega}_B) called bit-code) over an alphabet
{\Sigma}_B of 11 symbols belonging to L_B - the language over P B. IB has
semantic correspondence with conventional model-theoretic interpretation of DL.
We then define {\sigma}_BS on L_B. A detailed analysis of I_B and {\sigma}_BS
has been given.
MIST: L0 Sparse Linear Regression with Momentum
Authors: Goran Marjanovic, Magnus O. Ulfarsson, Alfred O. Hero III
Date: 2014-09-25 00:00:00
Tasks: regression

Significant attention has been given to minimizing a penalized least squares
criterion for estimating sparse solutions to large linear systems of equations.
The penalty is responsible for inducing sparsity and the natural choice is the
so-called $l_0$ norm. In this paper we develop a Momentumized Iterative
Shrinkage Thresholding (MIST) algorithm for minimizing the resulting non-convex
criterion and prove its convergence to a local minimizer. Simulations on large
data sets show superior performance of the proposed method to other methods.
L0 Sparse Inverse Covariance Estimation
Authors: Goran Marjanovic, Alfred O. Hero III
Date: 2014-08-05 00:00:00

Recently, there has been focus on penalized log-likelihood covariance
estimation for sparse inverse covariance (precision) matrices. The penalty is
responsible for inducing sparsity, and a very common choice is the convex $l_1$
norm. However, the best estimator performance is not always achieved with this
penalty. The most natural sparsity promoting "norm" is the non-convex $l_0$
penalty but its lack of convexity has deterred its use in sparse maximum
likelihood estimation. In this paper we consider non-convex $l_0$ penalized
log-likelihood inverse covariance estimation and present a novel cyclic descent
algorithm for its optimization. Convergence to a local minimizer is proved,
which is highly non-trivial, and we demonstrate via simulations the reduced
bias and superior quality of the $l_0$ penalty as compared to the $l_1$
penalty.
Phrase database Approach to structural and semantic disambiguation in English-Korean Machine Translation
Authors: Myong-Chol Pak
Date: 2015-03-19 00:00:00
Tasks: Machine Translation, Translation

In machine translation it is common phenomenon that machine-readable
dictionaries and standard parsing rules are not enough to ensure accuracy in
parsing and translating English phrases into Korean language, which is revealed
in misleading translation results due to consequent structural and semantic
ambiguities. This paper aims to suggest a solution to structural and semantic
ambiguities due to the idiomaticity and non-grammaticalness of phrases commonly
used in English language by applying bilingual phrase database in
English-Korean Machine Translation (EKMT). This paper firstly clarifies what
the phrase unit in EKMT is based on the definition of the English phrase,
secondly clarifies what kind of language unit can be the target of the phrase
database for EKMT, thirdly suggests a way to build the phrase database by
presenting the format of the phrase database with examples, and finally
discusses briefly the method to apply this bilingual phrase database to the
EKMT for structural and semantic disambiguation.