pwc-archive/papers-with-abstracts huggingface dataset:
Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
Authors: Prateek Jain, Sewoong Oh
Date: 2013-11-12 00:00:00
Tasks: Matrix Completion, Recommendation Systems

We study the problem of learning a distribution from samples, when the
underlying distribution is a mixture of product distributions over discrete
domains. This problem is motivated by several practical applications such as
crowd-sourcing, recommendation systems, and learning Boolean functions. The
existing solutions either heavily rely on the fact that the number of
components in the mixtures is finite or have sample/time complexity that is
exponential in the number of components. In this paper, we introduce a
polynomial time/sample complexity method for learning a mixture of $r$ discrete
product distributions over $\{1, 2, \dots, \ell\}^n$, for general $\ell$ and
$r$. We show that our approach is statistically consistent and further provide
finite sample guarantees.
  We use techniques from the recent work on tensor decompositions for
higher-order moment matching. A crucial step in these moment matching methods
is to construct a certain matrix and a certain tensor with low-rank spectral
decompositions. These tensors are typically estimated directly from the
samples. The main challenge in learning mixtures of discrete product
distributions is that these low-rank tensors cannot be obtained directly from
the sample moments. Instead, we reduce the tensor estimation problem to: $a$)
estimating a low-rank matrix using only off-diagonal block elements; and $b$)
estimating a tensor using a small number of linear measurements. Leveraging on
recent developments in matrix completion, we give an alternating minimization
based method to estimate the low-rank matrix, and formulate the tensor
completion problem as a least-squares problem.
A two-step learning approach for solving full and almost full cold start problems in dyadic prediction
Authors: Tapio Pahikkala, Michiel Stock, Antti Airola, Tero Aittokallio, Bernard De Baets, Willem Waegeman
Date: 2014-05-17 00:00:00

Dyadic prediction methods operate on pairs of objects (dyads), aiming to
infer labels for out-of-sample dyads. We consider the full and almost full cold
start problem in dyadic prediction, a setting that occurs when both objects in
an out-of-sample dyad have not been observed during training, or if one of them
has been observed, but very few times. A popular approach for addressing this
problem is to train a model that makes predictions based on a pairwise feature
representation of the dyads, or, in case of kernel methods, based on a tensor
product pairwise kernel. As an alternative to such a kernel approach, we
introduce a novel two-step learning algorithm that borrows ideas from the
fields of pairwise learning and spectral filtering. We show theoretically that
the two-step method is very closely related to the tensor product kernel
approach, and experimentally that it yields a slightly better predictive
performance. Moreover, unlike existing tensor product kernel methods, the
two-step method allows closed-form solutions for training and parameter
selection via cross-validation estimates both in the full and almost full cold
start settings, making the approach much more efficient and straightforward to
implement.
Identification of functionally related enzymes by learning-to-rank methods
Authors: Michiel Stock, Thomas Fober, Eyke Hüllermeier, Serghei Glinca, Gerhard Klebe, Tapio Pahikkala, Antti Airola, Bernard De Baets, Willem Waegeman
Date: 2014-05-17 00:00:00
Tasks: Learning-To-Rank

Enzyme sequences and structures are routinely used in the biological sciences
as queries to search for functionally related enzymes in online databases. To
this end, one usually departs from some notion of similarity, comparing two
enzymes by looking for correspondences in their sequences, structures or
surfaces. For a given query, the search operation results in a ranking of the
enzymes in the database, from very similar to dissimilar enzymes, while
information about the biological function of annotated database enzymes is
ignored.
  In this work we show that rankings of that kind can be substantially improved
by applying kernel-based learning algorithms. This approach enables the
detection of statistical dependencies between similarities of the active cleft
and the biological function of annotated enzymes. This is in contrast to
search-based approaches, which do not take annotated training data into
account. Similarity measures based on the active cleft are known to outperform
sequence-based or structure-based measures under certain conditions. We
consider the Enzyme Commission (EC) classification hierarchy for obtaining
annotated enzymes during the training phase. The results of a set of sizeable
experiments indicate a consistent and significant improvement for a set of
similarity measures that exploit information about small cavities in the
surface of enzymes.
That's sick dude!: Automatic identification of word sense change across different timescales
Authors: Sunny Mitra, Ritwik Mitra, Martin Riedl, Chris Biemann, Animesh Mukherjee, Pawan Goyal
Date: 2014-05-17 00:00:00
Proceeding: ACL 2014 6
Tasks: Word Sense Disambiguation

In this paper, we propose an unsupervised method to identify noun sense
changes based on rigorous analysis of time-varying text data available in the
form of millions of digitized books. We construct distributional thesauri based
networks from data at different time points and cluster each of them separately
to obtain word-centric sense clusters corresponding to the different time
points. Subsequently, we compare these sense clusters of two different time
points to find if (i) there is birth of a new sense or (ii) if an older sense
has got split into more than one sense or (iii) if a newer sense has been
formed from the joining of older senses or (iv) if a particular sense has died.
We conduct a thorough evaluation of the proposed methodology both manually as
well as through comparison with WordNet. Manual evaluation indicates that the
algorithm could correctly identify 60.4% birth cases from a set of 48 randomly
picked samples and 57% split/join cases from a set of 21 randomly picked
samples. Remarkably, in 44% cases the birth of a novel sense is attested by
WordNet, while in 46% cases and 43% cases split and join are respectively
confirmed by WordNet. Our approach can be applied for lexicography, as well as
for applications like word sense disambiguation or semantic search.
Real Time Object Tracking Based on Inter-frame Coding: A Review
Authors: Shraddha Mehta, Vaishali Kalariya
Date: 2014-05-17 00:00:00
Tasks: Object, Object Tracking, Position, Robot Navigation, Video Compression

Inter-frame Coding plays significant role for video Compression and Computer
Vision. Computer vision systems have been incorporated in many real life
applications (e.g. surveillance systems, medical imaging, robot navigation and
identity verification systems). Object tracking is a key computer vision topic,
which aims at detecting the position of a moving object from a video sequence.
The application of Inter-frame Coding for low frame rate video, as well as for
low resolution video. Various methods based on Top-down approach just like
kernel based or mean shift technique are used to track the object for video,
So, Inter-frame Coding algorithms are widely adopted by video coding standards,
mainly due to their simplicity and good distortion performance for object
tracking.
Efficient Tracking of a Moving Object using Inter-Frame Coding
Authors: Shraddha Mehta, Vaishali Kalariya
Date: 2014-05-17 00:00:00

Video surveillance has long been in use to monitor security sensitive areas
such as banks, department stores, highways, crowded public places and
borders.The advance in computing power, availability of large-capacity storage
devices and high speed network infrastructure paved the way for cheaper,
multi-sensor video surveillance systems.Traditionally, the video outputs are
processed online by human operators and are usually saved to tapes for later
use only after a forensic event.The increase in the number of cameras in
ordinary surveillance systems overloaded both the human operators and the
storage devices with high volumes of data and made it in-feasible to ensure
proper monitoring of sensitive areas for long times.
Thematically Reinforced Explicit Semantic Analysis
Authors: Yannis Haralambous, Vitaly Klyuev
Date: 2014-05-17 00:00:00
Tasks: text-classification, Text Classification

We present an extended, thematically reinforced version of Gabrilovich and
Markovitch's Explicit Semantic Analysis (ESA), where we obtain thematic
information through the category structure of Wikipedia. For this we first
define a notion of categorical tfidf which measures the relevance of terms in
categories. Using this measure as a weight we calculate a maximal spanning tree
of the Wikipedia corpus considered as a directed graph of pages and categories.
This tree provides us with a unique path of "most related categories" between
each page and the top of the hierarchy. We reinforce tfidf of words in a page
by aggregating it with categorical tfidfs of the nodes of these paths, and
define a thematically reinforced ESA semantic relatedness measure which is more
robust than standard ESA and less sensitive to noise caused by out-of-context
words. We apply our method to the French Wikipedia corpus, evaluate it through
a text classification on a 37.5 MB corpus of 20 French newsgroups and obtain a
precision increase of 9-10% compared with standard ESA.
Active Semi-Supervised Learning Using Sampling Theory for Graph Signals
Authors: Akshay Gadde, Aamir Anis, Antonio Ortega
Date: 2014-05-16 00:00:00
Tasks: Active Learning

We consider the problem of offline, pool-based active semi-supervised
learning on graphs. This problem is important when the labeled data is scarce
and expensive whereas unlabeled data is easily available. The data points are
represented by the vertices of an undirected graph with the similarity between
them captured by the edge weights. Given a target number of nodes to label, the
goal is to choose those nodes that are most informative and then predict the
unknown labels. We propose a novel framework for this problem based on our
recent results on sampling theory for graph signals. A graph signal is a
real-valued function defined on each node of the graph. A notion of frequency
for such signals can be defined using the spectrum of the graph Laplacian
matrix. The sampling theory for graph signals aims to extend the traditional
Nyquist-Shannon sampling theory by allowing us to identify the class of graph
signals that can be reconstructed from their values on a subset of vertices.
This approach allows us to define a criterion for active learning based on
sampling set selection which aims at maximizing the frequency of the signals
that can be reconstructed from their samples on the set. Experiments show the
effectiveness of our method.
Leveraging Evolutionary Search to Discover Self-Adaptive and Self-Organizing Cellular Automata
Authors: David B. Knoester, Heather J. Goldsby, Christoph Adami
Date: 2014-05-16 00:00:00
Tasks: Evolutionary Algorithms

Building self-adaptive and self-organizing (SASO) systems is a challenging
problem, in part because SASO principles are not yet well understood and few
platforms exist for exploring them. Cellular automata (CA) are a well-studied
approach to exploring the principles underlying self-organization. A CA
comprises a lattice of cells whose states change over time based on a discrete
update function. One challenge to developing CA is that the relationship of an
update function, which describes the local behavior of each cell, to the global
behavior of the entire CA is often unclear. As a result, many researchers have
used stochastic search techniques, such as evolutionary algorithms, to
automatically discover update functions that produce a desired global behavior.
However, these update functions are typically defined in a way that does not
provide for self-adaptation. Here we describe an approach to discovering CA
update functions that are both self-adaptive and self-organizing. Specifically,
we use a novel evolutionary algorithm-based approach to discover finite state
machines (FSMs) that implement update functions for CA. We show how this
approach is able to evolve FSM-based update functions that perform well on the
density classification task for 1-, 2-, and 3-dimensional CA. Moreover, we show
that these FSMs are self-adaptive, self-organizing, and highly scalable, often
performing well on CA that are orders of magnitude larger than those used to
evaluate performance during the evolutionary search. These results demonstrate
that CA are a viable platform for studying the integration of self-adaptation
and self-organization, and strengthen the case for using evolutionary
algorithms as a component of SASO systems.
Coarse-to-Fine Classification via Parametric and Nonparametric Models for Computer-Aided Diagnosis
Authors: Meizhu Liu, Le Lu, Xiaojing Ye, Shipeng Yu
Date: 2014-05-16 00:00:00
Tasks: Classification, General Classification, Graph Embedding, Lung Nodule Detection, Template Matching

Classification is one of the core problems in Computer-Aided Diagnosis (CAD),
targeting for early cancer detection using 3D medical imaging interpretation.
High detection sensitivity with desirably low false positive (FP) rate is
critical for a CAD system to be accepted as a valuable or even indispensable
tool in radiologists' workflow. Given various spurious imagery noises which
cause observation uncertainties, this remains a very challenging task. In this
paper, we propose a novel, two-tiered coarse-to-fine (CTF) classification
cascade framework to tackle this problem. We first obtain
classification-critical data samples (e.g., samples on the decision boundary)
extracted from the holistic data distributions using a robust parametric model
(e.g., \cite{Raykar08}); then we build a graph-embedding based nonparametric
classifier on sampled data, which can more accurately preserve or formulate the
complex classification boundary. These two steps can also be considered as
effective "sample pruning" and "feature pursuing + $k$NN/template matching",
respectively. Our approach is validated comprehensively in colorectal polyp
detection and lung nodule detection CAD systems, as the top two deadly cancers,
using hospital scale, multi-site clinical datasets. The results show that our
method achieves overall better classification/detection performance than
existing state-of-the-art algorithms using single-layer classifiers, such as
the support vector machine variants \cite{Wang08}, boosting \cite{Slabaugh10},
logistic regression \cite{Ravesteijn10}, relevance vector machine
\cite{Raykar08}, $k$-nearest neighbor \cite{Murphy09} or spectral projections
on graph \cite{Cai08}.
Compositional Morphology for Word Representations and Language Modelling
Authors: Jan A. Botha, Phil Blunsom
Date: 2014-05-16 00:00:00
Tasks: Decoder, Language Modeling, Language Modelling, Machine Translation, Translation, Word Similarity

This paper presents a scalable method for integrating compositional
morphological representations into a vector-based probabilistic language model.
Our approach is evaluated in the context of log-bilinear language models,
rendered suitably efficient for implementation inside a machine translation
decoder by factoring the vocabulary. We perform both intrinsic and extrinsic
evaluations, presenting results on a range of languages which demonstrate that
our model learns morphological representations that both perform well on word
similarity tasks and lead to substantial reductions in perplexity. When used
for translation into morphologically rich languages with large vocabularies,
our models obtain improvements of up to 1.2 BLEU points relative to a baseline
system using back-off n-gram models.
Les mathématiques de la langue : l'approche formelle de Montague
Authors: Yannis Haralambous
Date: 2014-05-16 00:00:00
Tasks: Math

We present a natural language modelization method which is strongely relying
on mathematics. This method, called "Formal Semantics," has been initiated by
the American linguist Richard M. Montague in the 1970's. It uses mathematical
tools such as formal languages and grammars, first-order logic, type theory and
$\lambda$-calculus. Our goal is to have the reader discover both Montagovian
formal semantics and the mathematical tools that he used in his method.
  -----
  Nous pr\'esentons une m\'ethode de mod\'elisation de la langue naturelle qui
est fortement bas\'ee sur les math\'ematiques. Cette m\'ethode, appel\'ee
{\guillemotleft}s\'emantique formelle{\guillemotright}, a \'et\'e initi\'ee par
le linguiste am\'ericain Richard M. Montague dans les ann\'ees 1970. Elle
utilise des outils math\'ematiques tels que les langages et grammaires formels,
la logique du 1er ordre, la th\'eorie de types et le $\lambda$-calcul. Nous
nous proposons de faire d\'ecouvrir au lecteur tant la s\'emantique formelle de
Montague que les outils math\'ematiques dont il s'est servi.
Model revision inference for extensions of first order logic
Authors: Joachim Jansen
Date: 2014-05-16 00:00:00

I am Joachim Jansen and this is my research summary, part of my application
to the Doctoral Consortium at ICLP'14. I am a PhD student in the Knowledge
Representation and Reasoning (KRR) research group, a subgroup of the
Declarative Languages and Artificial Intelligence (DTAI) group at the
department of Computer Science at KU Leuven. I started my PhD in September
2012. My promotor is prof. dr. ir. Gerda Janssens and my co-promotor is prof.
dr. Marc Denecker. I can be contacted at joachim.jansen@cs.kuleuven.be or at:
Room 01.167 Celestijnenlaan 200A 3001 Heverlee Belgium An extended abstract /
full version of a paper accepted to be presented at the Doctoral Consortium of
the 30th International Conference on Logic Programming (ICLP 2014), July 19-22,
Vienna, Austria
Algorithm for Adapting Cases Represented in a Tractable Description Logic
Authors: Liang Chang, Uli Sattler, Tianlong Gu
Date: 2014-05-16 00:00:00

Case-based reasoning (CBR) based on description logics (DLs) has gained a lot
of attention lately. Adaptation is a basic task in the CBR inference that can
be modeled as the knowledge base revision problem and solved in propositional
logic. However, in DLs, it is still a challenge problem since existing revision
operators only work well for strictly restricted DLs of the \emph{DL-Lite}
family, and it is difficult to design a revision algorithm which is
syntax-independent and fine-grained. In this paper, we present a new method for
adaptation based on the DL $\mathcal{EL_{\bot}}$. Following the idea of
adaptation as revision, we firstly extend the logical basis for describing
cases from propositional logic to the DL $\mathcal{EL_{\bot}}$, and present a
formalism for adaptation based on $\mathcal{EL_{\bot}}$. Then we present an
adaptation algorithm for this formalism and demonstrate that our algorithm is
syntax-independent and fine-grained. Our work provides a logical basis for
adaptation in CBR systems where cases and domain knowledge are described by the
tractable DL $\mathcal{EL_{\bot}}$.
Empirical Study of Artificial Fish Swarm Algorithm
Authors: Reza Azizi
Date: 2014-05-16 00:00:00

Artificial fish swarm algorithm (AFSA) is one of the swarm intelligence
optimization algorithms that works based on population and stochastic search.
In order to achieve acceptable result, there are many parameters needs to be
adjusted in AFSA. Among these parameters, visual and step are very significant
in view of the fact that artificial fish basically move based on these
parameters. In standard AFSA, these two parameters remain constant until the
algorithm termination. Large values of these parameters increase the capability
of algorithm in global search, while small values improve the local search
ability of the algorithm. In this paper, we empirically study the performance
of the AFSA and different approaches to balance between local and global
exploration have been tested based on the adaptive modification of visual and
step during algorithm execution. The proposed approaches have been evaluated
based on the four well-known benchmark functions. Experimental results show
considerable positive impact on the performance of AFSA.
FTVd is beyond Fast Total Variation regularized Deconvolution
Authors: Yi-Lun Wang
Date: 2014-02-17 00:00:00
Tasks: Image Deconvolution

In this paper, we revisit the "FTVd" algorithm for Fast Total Variation
Regularized Deconvolution, which has been widely used in the past few years.
Both its original version implemented in the MATLAB software FTVd 3.0 and its
related variant implemented in the latter version FTVd 4.0 are considered
\cite{Wang08FTVdsoftware}. We propose that the intermediate results during the
iterations are the solutions of a series of combined Tikhonov and total
variation regularized image deconvolution models and therefore some of them
often have even better image quality than the final solution, which is
corresponding to the pure total variation regularized model.
Optimized Cartesian $K$-Means
Authors: Jianfeng Wang, Jingdong Wang, Jingkuan Song, Xin-Shun Xu, Heng Tao Shen, Shipeng Li
Date: 2014-05-16 00:00:00
Tasks: Quantization

Product quantization-based approaches are effective to encode
high-dimensional data points for approximate nearest neighbor search. The space
is decomposed into a Cartesian product of low-dimensional subspaces, each of
which generates a sub codebook. Data points are encoded as compact binary codes
using these sub codebooks, and the distance between two data points can be
approximated efficiently from their codes by the precomputed lookup tables.
Traditionally, to encode a subvector of a data point in a subspace, only one
sub codeword in the corresponding sub codebook is selected, which may impose
strict restrictions on the search accuracy. In this paper, we propose a novel
approach, named Optimized Cartesian $K$-Means (OCKM), to better encode the data
points for more accurate approximate nearest neighbor search. In OCKM, multiple
sub codewords are used to encode the subvector of a data point in a subspace.
Each sub codeword stems from different sub codebooks in each subspace, which
are optimally generated with regards to the minimization of the distortion
errors. The high-dimensional data point is then encoded as the concatenation of
the indices of multiple sub codewords from all the subspaces. This can provide
more flexibility and lower distortion errors than traditional methods.
Experimental results on the standard real-life datasets demonstrate the
superiority over state-of-the-art approaches for approximate nearest neighbor
search.