pwc-archive/papers-with-abstracts huggingface dataset:
Web image annotation by diffusion maps manifold learning algorithm
Authors: Neda Pourali
Date: 2014-12-08 00:00:00
Tasks: Dimensionality Reduction

Automatic image annotation is one of the most challenging problems in machine
vision areas. The goal of this task is to predict number of keywords
automatically for images captured in real data. Many methods are based on
visual features in order to calculate similarities between image samples. But
the computation cost of these approaches is very high. These methods require
many training samples to be stored in memory. To lessen this burden, a number
of techniques have been developed to reduce the number of features in a
dataset. Manifold learning is a popular approach to nonlinear dimensionality
reduction. In this paper, we investigate Diffusion maps manifold learning
method for web image auto-annotation task. Diffusion maps manifold learning
method is used to reduce the dimension of some visual features. Extensive
experiments and analysis on NUS-WIDE-LITE web image dataset with different
visual features show how this manifold learning dimensionality reduction method
can be applied effectively to image annotation.
Accurate Streaming Support Vector Machines
Authors: Vikram Nathan, Sharath Raghvendra
Date: 2014-12-08 00:00:00
Tasks: Binary Classification

A widely-used tool for binary classification is the Support Vector Machine
(SVM), a supervised learning technique that finds the "maximum margin" linear
separator between the two classes. While SVMs have been well studied in the
batch (offline) setting, there is considerably less work on the streaming
(online) setting, which requires only a single pass over the data using
sub-linear space. Existing streaming algorithms are not yet competitive with
the batch implementation. In this paper, we use the formulation of the SVM as a
minimum enclosing ball (MEB) problem to provide a streaming SVM algorithm based
off of the blurred ball cover originally proposed by Agarwal and Sharathkumar.
Our implementation consistently outperforms existing streaming SVM approaches
and provides higher accuracies than libSVM on several datasets, thus making it
competitive with the standard SVM batch implementation.
Double Ramp Loss Based Reject Option Classifier
Authors: Naresh Manwani, Kalpit Desai, Sanand Sasidharan, Ramasubramanian Sundararajan
Date: 2013-11-26 00:00:00
Tasks: General Classification

We consider the problem of learning reject option classifiers. The goodness
of a reject option classifier is quantified using $0-d-1$ loss function wherein
a loss $d \in (0,.5)$ is assigned for rejection. In this paper, we propose {\em
double ramp loss} function which gives a continuous upper bound for $(0-d-1)$
loss. Our approach is based on minimizing regularized risk under the double
ramp loss using {\em difference of convex (DC) programming}. We show the
effectiveness of our approach through experiments on synthetic and benchmark
datasets. Our approach performs better than the state of the art reject option
classification approaches.
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness
Authors: Mark Bun, Thomas Steinke
Date: 2014-12-08 00:00:00
Tasks: Math

Polynomial approximations to boolean functions have led to many positive
results in computer science. In particular, polynomial approximations to the
sign function underly algorithms for agnostically learning halfspaces, as well
as pseudorandom generators for halfspaces. In this work, we investigate the
limits of these techniques by proving inapproximability results for the sign
function.
  Firstly, the polynomial regression algorithm of Kalai et al. (SIAM J. Comput.
2008) shows that halfspaces can be learned with respect to log-concave
distributions on $\mathbb{R}^n$ in the challenging agnostic learning model. The
power of this algorithm relies on the fact that under log-concave
distributions, halfspaces can be approximated arbitrarily well by low-degree
polynomials. We ask whether this technique can be extended beyond log-concave
distributions, and establish a negative result. We show that polynomials of any
degree cannot approximate the sign function to within arbitrarily low error for
a large class of non-log-concave distributions on the real line, including
those with densities proportional to $\exp(-|x|^{0.99})$.
  Secondly, we investigate the derandomization of Chernoff-type concentration
inequalities. Chernoff-type tail bounds on sums of independent random variables
have pervasive applications in theoretical computer science. Schmidt et al.
(SIAM J. Discrete Math. 1995) showed that these inequalities can be established
for sums of random variables with only $O(\log(1/\delta))$-wise independence,
for a tail probability of $\delta$. We show that their results are tight up to
constant factors.
  These results rely on techniques from weighted approximation theory, which
studies how well functions on the real line can be approximated by polynomials
under various distributions. We believe that these techniques will have further
applications in other areas of computer science.
Rediscovering the Alphabet - On the Innate Universal Grammar
Authors: M. Yahia Kaadan, Asaad Kaadan
Date: 2014-12-08 00:00:00
Tasks: Transfer Learning

Universal Grammar (UG) theory has been one of the most important research
topics in linguistics since introduced five decades ago. UG specifies the
restricted set of languages learnable by human brain, and thus, many
researchers believe in its biological roots. Numerous empirical studies of
neurobiological and cognitive functions of the human brain, and of many natural
languages, have been conducted to unveil some aspects of UG. This, however,
resulted in different and sometimes contradicting theories that do not indicate
a universally unique grammar. In this research, we tackle the UG problem from
an entirely different perspective. We search for the Unique Universal Grammar
(UUG) that facilitates communication and knowledge transfer, the sole purpose
of a language. We formulate this UG and show that it is unique, intrinsic, and
cosmic, rather than humanistic. Initial analysis on a widespread natural
language already showed some positive results.
Learning Word Representations from Relational Graphs
Authors: Danushka Bollegala, Takanori Maehara, Yuichi Yoshida, Ken-ichi Kawarabayashi
Date: 2014-12-07 00:00:00
Tasks: Representation Learning

Attributes of words and relations between two words are central to numerous
tasks in Artificial Intelligence such as knowledge representation, similarity
measurement, and analogy detection. Often when two words share one or more
attributes in common, they are connected by some semantic relations. On the
other hand, if there are numerous semantic relations between two words, we can
expect some of the attributes of one of the words to be inherited by the other.
Motivated by this close connection between attributes and relations, given a
relational graph in which words are inter- connected via numerous semantic
relations, we propose a method to learn a latent representation for the
individual words. The proposed method considers not only the co-occurrences of
words as done by existing approaches for word representation learning, but also
the semantic relations in which two words co-occur. To evaluate the accuracy of
the word representations learnt using the proposed method, we use the learnt
word representations to solve semantic word analogy problems. Our experimental
results show that it is possible to learn better word representations by using
semantic semantics between words.
SimNets: A Generalization of Convolutional Networks
Authors: Nadav Cohen, Amnon Shashua
Date: 2014-10-03 00:00:00

We present a deep layered architecture that generalizes classical
convolutional neural networks (ConvNets). The architecture, called SimNets, is
driven by two operators, one being a similarity function whose family contains
the convolution operator used in ConvNets, and the other is a new soft
max-min-mean operator called MEX that realizes classical operators like ReLU
and max pooling, but has additional capabilities that make SimNets a powerful
generalization of ConvNets. Three interesting properties emerge from the
architecture: (i) the basic input to hidden layer to output machinery contains
as special cases kernel machines with the Exponential and Generalized Gaussian
kernels, the output units being "neurons in feature space" (ii) in its general
form, the basic machinery has a higher abstraction level than kernel machines,
and (iii) initializing networks using unsupervised learning is natural.
Experiments demonstrate the capability of achieving state of the art accuracy
with networks that are an order of magnitude smaller than comparable ConvNets.
Bayesian Image Restoration for Poisson Corrupted Image using a Latent Variational Method with Gaussian MRF
Authors: Hayaru Shouno
Date: 2014-12-07 00:00:00
Tasks: Image Restoration

We treat an image restoration problem with a Poisson noise chan- nel using a
Bayesian framework. The Poisson randomness might be appeared in observation of
low contrast object in the field of imaging. The noise observation is often
hard to treat in a theo- retical analysis. In our formulation, we interpret the
observation through the Poisson noise channel as a likelihood, and evaluate the
bound of it with a Gaussian function using a latent variable method. We then
introduce a Gaussian Markov random field (GMRF) as the prior for the Bayesian
approach, and derive the posterior as a Gaussian distribution. The latent
parameters in the likelihood and the hyperparameter in the GMRF prior could be
treated as hid- den parameters, so that, we propose an algorithm to infer them
in the expectation maximization (EM) framework using loopy belief
propagation(LBP). We confirm the ability of our algorithm in the computer
simulation, and compare it with the results of other im- age restoration
frameworks.
On the Behavioural Formalization of the Cognitive Middleware AWDRAT
Authors: Muhammad Taimoor Khan, Dimitrios Serpanos, Howard Shrobe
Date: 2014-12-07 00:00:00

We present our ongoing work and initial results towards the (behavioral)
correctness analysis of the cognitive middleware AWDRAT. Since, the (provable)
behavioral correctness of a software system is a fundamental pre-requisite of
the system's security. Therefore, the goal of the work is to first formalize
the behavioral semantics of the middleware as a pre-requisite for our proof of
the behavioral correctness. However, in this paper, we focus only on the core
and critical component of the middleware, i.e. Execution Monitor which is a
part of the module "Architectural Differencer" of AWDRAT. The role of the
execution monitor is to identify inconsistencies between runtime observations
of the target system and predictions of the specification System Architectural
Model of the system. As a starting point we have defined the formal
(denotational) semantics of the observations (runtime events) and predictions
(executable specifications as of System Architectural Model); then based on the
aforementioned formal semantices, we have formalized the behavior of the
"Execution Monitor" of the middleware.
Dictionary Learning over Distributed Models
Authors: Jianshu Chen, Zaid J. Towfic, Ali H. Sayed
Date: 2014-02-06 00:00:00
Tasks: Collaborative Inference, Dictionary Learning

In this paper, we consider learning dictionary models over a network of
agents, where each agent is only in charge of a portion of the dictionary
elements. This formulation is relevant in Big Data scenarios where large
dictionary models may be spread over different spatial locations and it is not
feasible to aggregate all dictionaries in one location due to communication and
privacy considerations. We first show that the dual function of the inference
problem is an aggregation of individual cost functions associated with
different agents, which can then be minimized efficiently by means of diffusion
strategies. The collaborative inference step generates dual variables that are
used by the agents to update their dictionaries without the need to share these
dictionaries or even the coefficient models for the training data. This is a
powerful property that leads to an effective distributed procedure for learning
dictionaries over large networks (e.g., hundreds of agents in our experiments).
Furthermore, the proposed learning strategy operates in an online manner and is
able to respond to streaming data, where each data sample is presented to the
network once.
Iterative Bayesian Reconstruction of Non-IID Block-Sparse Signals
Authors: Mehdi Korki, Jingxin Zhang, Cishen Zhang, Hadi Zayyani
Date: 2014-12-07 00:00:00

This paper presents a novel Block Iterative Bayesian Algorithm (Block-IBA)
for reconstructing block-sparse signals with unknown block structures. Unlike
the existing algorithms for block sparse signal recovery which assume the
cluster structure of the nonzero elements of the unknown signal to be
independent and identically distributed (i.i.d.), we use a more realistic
Bernoulli-Gaussian hidden Markov model (BGHMM) to characterize the non-i.i.d.
block-sparse signals commonly encountered in practice. The Block-IBA
iteratively estimates the amplitudes and positions of the block-sparse signal
using the steepest-ascent based Expectation-Maximization (EM), and optimally
selects the nonzero elements of the block-sparse signal by adaptive
thresholding. The global convergence of Block-IBA is analyzed and proved, and
the effectiveness of Block-IBA is demonstrated by numerical experiments and
simulations on synthetic and real-life data.
Sparse Modeling for Image and Vision Processing
Authors: Julien Mairal, Francis Bach, Jean Ponce
Date: 2014-11-12 00:00:00
Tasks: Model Selection

In recent years, a large amount of multi-disciplinary research has been
conducted on sparse models and their applications. In statistics and machine
learning, the sparsity principle is used to perform model selection---that is,
automatically selecting a simple model among a large collection of them. In
signal processing, sparse coding consists of representing data with linear
combinations of a few dictionary elements. Subsequently, the corresponding
tools have been widely adopted by several scientific communities such as
neuroscience, bioinformatics, or computer vision. The goal of this monograph is
to offer a self-contained view of sparse modeling for visual recognition and
image processing. More specifically, we focus on applications where the
dictionary is learned and adapted to data, yielding a compact representation
that has been successful in various contexts.
Smoothed Low Rank and Sparse Matrix Recovery by Iteratively Reweighted Least Squares Minimization
Authors: Canyi Lu, Zhouchen Lin, Shuicheng Yan
Date: 2014-01-29 00:00:00

This work presents a general framework for solving the low rank and/or sparse
matrix minimization problems, which may involve multiple non-smooth terms. The
Iteratively Reweighted Least Squares (IRLS) method is a fast solver, which
smooths the objective function and minimizes it by alternately updating the
variables and their weights. However, the traditional IRLS can only solve a
sparse only or low rank only minimization problem with squared loss or an
affine constraint. This work generalizes IRLS to solve joint/mixed low rank and
sparse minimization problems, which are essential formulations for many tasks.
As a concrete example, we solve the Schatten-$p$ norm and $\ell_{2,q}$-norm
regularized Low-Rank Representation (LRR) problem by IRLS, and theoretically
prove that the derived solution is a stationary point (globally optimal if
$p,q\geq1$). Our convergence proof of IRLS is more general than previous one
which depends on the special properties of the Schatten-$p$ norm and
$\ell_{2,q}$-norm. Extensive experiments on both synthetic and real data sets
demonstrate that our IRLS is much more efficient.
Possible and Necessary Allocations via Sequential Mechanisms
Authors: Haris Aziz, Toby Walsh, Lirong Xia
Date: 2014-12-06 00:00:00

A simple mechanism for allocating indivisible resources is sequential
allocation in which agents take turns to pick items. We focus on possible and
necessary allocation problems, checking whether allocations of a given form
occur in some or all mechanisms for several commonly used classes of sequential
allocation mechanisms. In particular, we consider whether a given agent
receives a given item, a set of items, or a subset of items for five natural
classes of sequential allocation mechanisms: balanced, recursively balanced,
balanced alternating, strictly alternating and all policies. We identify
characterizations of allocations produced balanced, recursively balanced,
balanced alternating policies and strictly alternating policies respectively,
which extend the well-known characterization by Brams and King [2005] for
policies without restrictions. In addition, we examine the computational
complexity of possible and necessary allocation problems for these classes.
Markov Chain Analysis of Evolution Strategies on a Linear Constraint Optimization Problem
Authors: Alexandre Chotard, Anne Auger, Nikolaus Hansen
Date: 2014-04-11 00:00:00

This paper analyses a $(1,\lambda)$-Evolution Strategy, a randomised
comparison-based adaptive search algorithm, on a simple constraint optimisation
problem. The algorithm uses resampling to handle the constraint and optimizes a
linear function with a linear constraint. Two cases are investigated: first the
case where the step-size is constant, and second the case where the step-size
is adapted using path length control. We exhibit for each case a Markov chain
whose stability analysis would allow us to deduce the divergence of the
algorithm depending on its internal parameters. We show divergence at a
constant rate when the step-size is constant. We sketch that with step-size
adaptation geometric divergence takes place. Our results complement previous
studies where stability was assumed.
Relations among Some Low Rank Subspace Recovery Models
Authors: Hongyang Zhang, Zhouchen Lin, Chao Zhang, Junbin Gao
Date: 2014-12-06 00:00:00

Recovering intrinsic low dimensional subspaces from data distributed on them
is a key preprocessing step to many applications. In recent years, there has
been a lot of work that models subspace recovery as low rank minimization
problems. We find that some representative models, such as Robust Principal
Component Analysis (R-PCA), Robust Low Rank Representation (R-LRR), and Robust
Latent Low Rank Representation (R-LatLRR), are actually deeply connected. More
specifically, we discover that once a solution to one of the models is
obtained, we can obtain the solutions to other models in closed-form
formulations. Since R-PCA is the simplest, our discovery makes it the center of
low rank subspace recovery models. Our work has two important implications.
First, R-PCA has a solid theoretical foundation. Under certain conditions, we
could find better solutions to these low rank models at overwhelming
probabilities, although these models are non-convex. Second, we can obtain
significantly faster algorithms for these models by solving R-PCA first. The
computation cost can be further cut by applying low complexity randomized
algorithms, e.g., our novel $\ell_{2,1}$ filtering algorithm, to R-PCA.
Experiments verify the advantages of our algorithms over other state-of-the-art
ones that are based on the alternating direction method.
Using Artificial Neural Network Techniques for Prediction of Electric Energy Consumption
Authors: Hasan M. H. Owda, Babatunji Omoniwa, Ahmad R. Shahid, Sheikh Ziauddin
Date: 2014-12-06 00:00:00

Due to imprecision and uncertainties in predicting real world problems,
artificial neural network (ANN) techniques have become increasingly useful for
modeling and optimization. This paper presents an artificial neural network
approach for forecasting electric energy consumption. For effective planning
and operation of power systems, optimal forecasting tools are needed for energy
operators to maximize profit and also to provide maximum satisfaction to energy
consumers. Monthly data for electric energy consumed in the Gaza strip was
collected from year 1994 to 2013. Data was trained and the proposed model was
validated using 2-Fold and K-Fold cross validation techniques. The model has
been tested with actual energy consumption data and yields satisfactory
performance.
Iterative Neural Autoregressive Distribution Estimator (NADE-k)
Authors: Tapani Raiko, Li Yao, Kyunghyun Cho, Yoshua Bengio
Date: 2014-06-05 00:00:00
Tasks: Density Estimation, Image Generation, Missing Values, Variational Inference

Training of the neural autoregressive density estimator (NADE) can be viewed
as doing one step of probabilistic inference on missing values in data. We
propose a new model that extends this inference scheme to multiple steps,
arguing that it is easier to learn to improve a reconstruction in $k$ steps
rather than to learn to reconstruct in a single inference step. The proposed
model is an unsupervised building block for deep learning that combines the
desirable properties of NADE and multi-predictive training: (1) Its test
likelihood can be computed analytically, (2) it is easy to generate independent
samples from it, and (3) it uses an inference engine that is a superset of
variational inference for Boltzmann machines. The proposed NADE-k is
competitive with the state-of-the-art in density estimation on the two datasets
tested.
On the Information Theoretic Limits of Learning Ising Models
Authors: Karthikeyan Shanmugam, Rashish Tandon, Alexandros G. Dimakis, Pradeep Ravikumar
Date: 2014-11-05 00:00:00
Proceeding: NeurIPS 2014 12

We provide a general framework for computing lower-bounds on the sample
complexity of recovering the underlying graphs of Ising models, given i.i.d
samples. While there have been recent results for specific graph classes, these
involve fairly extensive technical arguments that are specialized to each
specific graph class. In contrast, we isolate two key graph-structural
ingredients that can then be used to specify sample complexity lower-bounds.
Presence of these structural properties makes the graph class hard to learn. We
derive corollaries of our main result that not only recover existing recent
results, but also provide lower bounds for novel graph classes not considered
previously. We also extend our framework to the random graph setting and derive
corollaries for Erd\H{o}s-R\'{e}nyi graphs in a certain dense setting.
Rule reasoning for legal norm validation of FSTP facts
Authors: Naouel Karam, Shashishekar Ramakrishna, Adrian Paschke
Date: 2014-12-05 00:00:00

Non-obviousness or inventive step is a general requirement for patentability
in most patent law systems. An invention should be at an adequate distance
beyond its prior art in order to be patented. This short paper provides an
overview on a methodology proposed for legal norm validation of FSTP facts
using rule reasoning approach.
Consistent optimization of AMS by logistic loss minimization
Authors: Wojciech Kotłowski
Date: 2014-12-05 00:00:00
Tasks: Binary Classification, General Classification

In this paper, we theoretically justify an approach popular among
participants of the Higgs Boson Machine Learning Challenge to optimize
approximate median significance (AMS). The approach is based on the following
two-stage procedure. First, a real-valued function is learned by minimizing a
surrogate loss for binary classification, such as logistic loss, on the
training sample. Then, a threshold is tuned on a separate validation sample, by
direct optimization of AMS. We show that the regret of the resulting
(thresholded) classifier measured with respect to the squared AMS, is
upperbounded by the regret of the underlying real-valued function measured with
respect to the logistic loss. Hence, we prove that minimizing logistic
surrogate is a consistent method of optimizing AMS.