pwc-archive/papers-with-abstracts huggingface dataset:
Sparse Matrix Inversion with Scaled Lasso
Authors: Tingni Sun, Cun-Hui Zhang
Date: 2012-02-13 00:00:00

We propose a new method of learning a sparse nonnegative-definite target
matrix. Our primary example of the target matrix is the inverse of a population
covariance or correlation matrix. The algorithm first estimates each column of
the target matrix by the scaled Lasso and then adjusts the matrix estimator to
be symmetric. The penalty level of the scaled Lasso for each column is
completely determined by data via convex minimization, without using
cross-validation.
  We prove that this scaled Lasso method guarantees the fastest proven rate of
convergence in the spectrum norm under conditions of weaker form than those in
the existing analyses of other $\ell_1$ regularized algorithms, and has faster
guaranteed rate of convergence when the ratio of the $\ell_1$ and spectrum
norms of the target inverse matrix diverges to infinity. A simulation study
demonstrates the computational feasibility and superb performance of the
proposed method.
  Our analysis also provides new performance bounds for the Lasso and scaled
Lasso to guarantee higher concentration of the error at a smaller threshold
level than previous analyses, and to allow the use of the union bound in
column-by-column applications of the scaled Lasso without an adjustment of the
penalty level. In addition, the least squares estimation after the scaled Lasso
selection is considered and proven to guarantee performance bounds similar to
that of the scaled Lasso.
Green Heron Swarm Optimization Algorithm - State-of-the-Art of a New Nature Inspired Discrete Meta-Heuristics
Authors: Chiranjib Sur, Anupam Shukla
Date: 2013-10-14 00:00:00
Tasks: Combinatorial Optimization

Many real world problems are NP-Hard problems are a very large part of them
can be represented as graph based problems. This makes graph theory a very
important and prevalent field of study. In this work a new bio-inspired
meta-heuristics called Green Heron Swarm Optimization (GHOSA) Algorithm is
being introduced which is inspired by the fishing skills of the bird. The
algorithm basically suited for graph based problems like combinatorial
optimization etc. However introduction of an adaptive mathematical variation
operator called Location Based Neighbour Influenced Variation (LBNIV) makes it
suitable for high dimensional continuous domain problems. The new algorithm is
being operated on the traditional benchmark equations and the results are
compared with Genetic Algorithm and Particle Swarm Optimization. The algorithm
is also operated on Travelling Salesman Problem, Quadratic Assignment Problem,
Knapsack Problem dataset. The procedure to operate the algorithm on the
Resource Constraint Shortest Path and road network optimization is also
discussed. The results clearly demarcates the GHOSA algorithm as an efficient
algorithm specially considering that the number of algorithms for the discrete
optimization is very low and robust and more explorative algorithm is required
in this age of social networking and mostly graph based problem scenarios.
(Dual) Hoops Have Unique Halving
Authors: Rob Arthan, Paulo Oliva
Date: 2012-03-02 00:00:00

Continuous logic extends the multi-valued Lukasiewicz logic by adding a
halving operator on propositions. This extension is designed to give a more
satisfactory model theory for continuous structures. The semantics of these
logics can be given using specialisations of algebraic structures known as
hoops. As part of an investigation into the metatheory of propositional
continuous logic, we were indebted to Prover9 for finding a proof of an
important algebraic law.
An Agent-based Model of the Cognitive Mechanisms Underlying the Origins of Creative Cultural Evolution
Authors: Liane Gabora, Maryam Saberi
Date: 2013-10-14 00:00:00
Tasks: Cultural Vocal Bursts Intensity Prediction, Diversity

Human culture is uniquely cumulative and open-ended. Using a computational model of cultural evolution in which neural network based agents evolve ideas for actions through invention and imitation, we tested the hypothesis that this is due to the capacity for recursive recall. We compared runs in which agents were limited to single-step actions to runs in which they used recursive recall to chain simple actions into complex ones. Chaining resulted in higher cultural diversity, open-ended generation of novelty, and no ceiling on the mean fitness of actions. Both chaining and no-chaining runs exhibited convergence on optimal actions, but without chaining this set was static while with chaining it was ever-changing. Chaining increased the ability to capitalize on the capacity for learning. These findings show that the recursive recall hypothesis provides a computationally plausible explanation of why humans alone have evolved the cultural means to transform this planet.
Misfire Detection in IC Engine using Kstar Algorithm
Authors: Anish Bahri, V. Sugumaran, S Babu Devasenapati
Date: 2013-10-14 00:00:00
Tasks: General Classification

Misfire in an IC Engine continues to be a problem leading to reduced fuel
efficiency, increased power loss and emissions containing heavy concentration
of hydrocarbons. Misfiring creates a unique vibration pattern attributed to a
particular cylinder. Useful features can be extracted from these patterns and
can be analyzed to detect misfire. Statistical features from these vibration
signals were extracted. Out of these, useful features were identified using the
J48 decision tree algorithm and selected features were used for classification
using the Kstar algorithm. In this paper performance analysis of Kstar
algorithm is presented.
Online Ranking: Discrete Choice, Spearman Correlation and Other Feedback
Authors: Nir Ailon
Date: 2013-08-30 00:00:00

Given a set $V$ of $n$ objects, an online ranking system outputs at each time
step a full ranking of the set, observes a feedback of some form and suffers a
loss. We study the setting in which the (adversarial) feedback is an element in
$V$, and the loss is the position (0th, 1st, 2nd...) of the item in the
outputted ranking. More generally, we study a setting in which the feedback is
a subset $U$ of at most $k$ elements in $V$, and the loss is the sum of the
positions of those elements.
  We present an algorithm of expected regret $O(n^{3/2}\sqrt{Tk})$ over a time
horizon of $T$ steps with respect to the best single ranking in hindsight. This
improves previous algorithms and analyses either by a factor of either
$\Omega(\sqrt{k})$, a factor of $\Omega(\sqrt{\log n})$ or by improving running
time from quadratic to $O(n\log n)$ per round. We also prove a matching lower
bound. Our techniques also imply an improved regret bound for online rank
aggregation over the Spearman correlation measure, and to other more complex
ranking loss functions.
Variance Adjusted Actor Critic Algorithms
Authors: Aviv Tamar, Shie Mannor
Date: 2013-10-14 00:00:00

We present an actor-critic framework for MDPs where the objective is the
variance-adjusted expected return. Our critic uses linear function
approximation, and we extend the concept of compatible features to the
variance-adjusted setting. We present an episodic actor-critic algorithm and
show that it converges almost surely to a locally optimal point of the
objective function.
Changing the Environment based on Intrinsic Motivation
Authors: Christoph Salge, Daniel Polani
Date: 2013-10-14 00:00:00

One of the remarkable feats of intelligent life is that it restructures the
world it lives in for its own benefit. This extended abstract outlines how the
information-theoretic principle of empowerment, as an intrinsic motivation, can
be used to restructure the environment an agent lives in. We present a first
qualitative evaluation of how an agent in a 3d-gridworld builds a
staircase-like structure, which reflects the agent's embodiment.
Predicting college basketball match outcomes using machine learning techniques: some results and lessons learned
Authors: Albrecht Zimmermann, Sruthi Moorthy, Zifan Shi
Date: 2013-10-14 00:00:00
Tasks: BIG-bench Machine Learning, General Classification

Most existing work on predicting NCAAB matches has been developed in a
statistical context. Trusting the capabilities of ML techniques, particularly
classification learners, to uncover the importance of features and learn their
relationships, we evaluated a number of different paradigms on this task. In
this paper, we summarize our work, pointing out that attributes seem to be more
important than models, and that there seems to be an upper limit to predictive
quality.
Flow-Based Algorithms for Local Graph Clustering
Authors: Lorenzo Orecchia, Zeyuan Allen Zhu
Date: 2013-07-10 00:00:00
Tasks: Clustering, Graph Clustering, graph partitioning

Given a subset S of vertices of an undirected graph G, the cut-improvement
problem asks us to find a subset S that is similar to A but has smaller
conductance. A very elegant algorithm for this problem has been given by
Andersen and Lang [AL08] and requires solving a small number of
single-commodity maximum flow computations over the whole graph G. In this
paper, we introduce LocalImprove, the first cut-improvement algorithm that is
local, i.e. that runs in time dependent on the size of the input set A rather
than on the size of the entire graph. Moreover, LocalImprove achieves this
local behaviour while essentially matching the same theoretical guarantee as
the global algorithm of Andersen and Lang.
  The main application of LocalImprove is to the design of better
local-graph-partitioning algorithms. All previously known local algorithms for
graph partitioning are random-walk based and can only guarantee an output
conductance of O(\sqrt{OPT}) when the target set has conductance OPT \in [0,1].
Very recently, Zhu, Lattanzi and Mirrokni [ZLM13] improved this to O(OPT /
\sqrt{CONN}) where the internal connectivity parameter CONN \in [0,1] is
defined as the reciprocal of the mixing time of the random walk over the graph
induced by the target set. In this work, we show how to use LocalImprove to
obtain a constant approximation O(OPT) as long as CONN/OPT = Omega(1). This
yields the first flow-based algorithm. Moreover, its performance strictly
outperforms the ones based on random walks and surprisingly matches that of the
best known global algorithm, which is SDP-based, in this parameter regime
[MMV12].
  Finally, our results show that spectral methods are not the only viable
approach to the construction of local graph partitioning algorithm and open
door to the study of algorithms with even better approximation and locality
guarantees.
Can Twitter Predict Royal Baby's Name ?
Authors: Bohdan Pavlyshenko
Date: 2013-10-13 00:00:00
Tasks: Decision Making

In this paper, we analyze the existence of possible correlation between
public opinion of twitter users and the decision-making of persons who are
influential in the society. We carry out this analysis on the example of the
discussion of probable name of the British crown baby, born in July, 2013. In
our study, we use the methods of quantitative processing of natural language,
the theory of frequent sets, the algorithms of visual displaying of users'
communities. We also analyzed the time dynamics of keyword frequencies. The
analysis showed that the main predictable name was dominating in the spectrum
of names before the official announcement. Using the theories of frequent sets,
we showed that the full name consisting of three component names was the part
of top 5 by the value of support. It was revealed that the structure of
dynamically formed users' communities participating in the discussion is
determined by only a few leaders who influence significantly the viewpoints of
other users.
Forecasting of Events by Tweet Data Mining
Authors: Bohdan Pavlyshenko
Date: 2013-10-13 00:00:00

This paper describes the analysis of quantitative characteristics of frequent
sets and association rules in the posts of Twitter microblogs related to
different event discussions. For the analysis, we used a theory of frequent
sets, association rules and a theory of formal concept analysis. We revealed
the frequent sets and association rules which characterize the semantic
relations between the concepts of analyzed subjects. The support of some
frequent sets reaches its global maximum before the expected event but with
some time delay. Such frequent sets may be considered as predictive markers
that characterize the significance of expected events for blogosphere users. We
showed that the time dynamics of confidence in some revealed association rules
can also have predictive characteristics. Exceeding a certain threshold may be
a signal for corresponding reaction in the society within the time interval
between the maximum and the probable coming of an event. In this paper, we
considered two types of events: the Olympic tennis tournament final in London,
2012 and the prediction of Eurovision 2013 winner.
Predicting Social Links for New Users across Aligned Heterogeneous Social Networks
Authors: Jiawei Zhang, Xiangnan Kong, Philip S. Yu
Date: 2013-10-13 00:00:00
Tasks: Link Prediction, Prediction, Transfer Learning

Online social networks have gained great success in recent years and many of
them involve multiple kinds of nodes and complex relationships. Among these
relationships, social links among users are of great importance. Many existing
link prediction methods focus on predicting social links that will appear in
the future among all users based upon a snapshot of the social network. In
real-world social networks, many new users are joining in the service every
day. Predicting links for new users are more important. Different from
conventional link prediction problems, link prediction for new users are more
challenging due to the following reasons: (1) differences in information
distributions between new users and the existing active users (i.e., old
users); (2) lack of information from the new users in the network. We propose a
link prediction method called SCAN-PS (Supervised Cross Aligned Networks link
prediction with Personalized Sampling), to solve the link prediction problem
for new users with information transferred from both the existing active users
in the target network and other source networks through aligned accounts. We
proposed a within-target-network personalized sampling method to process the
existing active users' information in order to accommodate the differences in
information distributions before the intra-network knowledge transfer. SCAN-PS
can also exploit information in other source networks, where the user accounts
are aligned with the target network. In this way, SCAN-PS could solve the cold
start problem when information of these new users is total absent in the target
network.
A Novel Frank-Wolfe Algorithm. Analysis and Applications to Large-Scale SVM Training
Authors: Hector Allende, Emanuele Frandi, Ricardo Nanculef, Claudio Sartori
Date: 2013-04-03 00:00:00

Recently, there has been a renewed interest in the machine learning community
for variants of a sparse greedy approximation procedure for concave
optimization known as {the Frank-Wolfe (FW) method}. In particular, this
procedure has been successfully applied to train large-scale instances of
non-linear Support Vector Machines (SVMs). Specializing FW to SVM training has
allowed to obtain efficient algorithms but also important theoretical results,
including convergence analysis of training algorithms and new characterizations
of model sparsity.
  In this paper, we present and analyze a novel variant of the FW method based
on a new way to perform away steps, a classic strategy used to accelerate the
convergence of the basic FW procedure. Our formulation and analysis is focused
on a general concave maximization problem on the simplex. However, the
specialization of our algorithm to quadratic forms is strongly related to some
classic methods in computational geometry, namely the Gilbert and MDM
algorithms.
  On the theoretical side, we demonstrate that the method matches the
guarantees in terms of convergence rate and number of iterations obtained by
using classic away steps. In particular, the method enjoys a linear rate of
convergence, a result that has been recently proved for MDM on quadratic forms.
  On the practical side, we provide experiments on several classification
datasets, and evaluate the results using statistical tests. Experiments show
that our method is faster than the FW method with classic away steps, and works
well even in the cases in which classic away steps slow down the algorithm.
Furthermore, these improvements are obtained without sacrificing the predictive
accuracy of the obtained SVM model.
Dense Scattering Layer Removal
Authors: Qiong Yan, Li Xu, Jiaya Jia
Date: 2013-10-13 00:00:00

We propose a new model, together with advanced optimization, to separate a
thick scattering media layer from a single natural image. It is able to handle
challenging underwater scenes and images taken in fog and sandstorm, both of
which are with significantly reduced visibility. Our method addresses the
critical issue -- this is, originally unnoticeable impurities will be greatly
magnified after removing the scattering media layer -- with transmission-aware
optimization. We introduce non-local structure-aware regularization to properly
constrain transmission estimation without introducing the halo artifacts. A
selective-neighbor criterion is presented to convert the unconventional
constrained optimization problem to an unconstrained one where the latter can
be efficiently solved.
Cross-moments computation for stochastic context-free grammars
Authors: Velimir M. Ilic, Miroslav D. Ciric, Miomir S. Stankovic
Date: 2011-08-01 00:00:00

In this paper we consider the problem of efficient computation of
cross-moments of a vector random variable represented by a stochastic
context-free grammar. Two types of cross-moments are discussed. The sample
space for the first one is the set of all derivations of the context-free
grammar, and the sample space for the second one is the set of all derivations
which generate a string belonging to the language of the grammar. In the past,
this problem was widely studied, but mainly for the cross-moments of scalar
variables and up to the second order. This paper presents new algorithms for
computing the cross-moments of an arbitrary order, and the previously developed
ones are derived as special cases.
Spectral Classification Using Restricted Boltzmann Machine
Authors: Fu-qiang Chen, Yan Wu, Yude Bu, Guo-dong Zhao
Date: 2013-05-03 00:00:00
Tasks: Astronomy, Classification, General Classification

In this study, a novel machine learning algorithm, restricted Boltzmann
machine (RBM), is introduced. The algorithm is applied for the spectral
classification in astronomy. RBM is a bipartite generative graphical model with
two separate layers (one visible layer and one hidden layer), which can extract
higher level features to represent the original data. Despite generative, RBM
can be used for classification when modified with a free energy and a soft-max
function. Before spectral classification, the original data is binarized
according to some rule. Then we resort to the binary RBM to classify
cataclysmic variables (CVs) and non-CVs (one half of all the given data for
training and the other half for testing). The experiment result shows
state-of-the-art accuracy of 100%, which indicates the efficiency of the binary
RBM algorithm.
Negative Binomial Process Count and Mixture Modeling
Authors: Mingyuan Zhou, Lawrence Carin
Date: 2012-09-15 00:00:00
Tasks: Bayesian Inference

The seemingly disjoint problems of count and mixture modeling are united
under the negative binomial (NB) process. A gamma process is employed to model
the rate measure of a Poisson process, whose normalization provides a random
probability measure for mixture modeling and whose marginalization leads to an
NB process for count modeling. A draw from the NB process consists of a Poisson
distributed finite number of distinct atoms, each of which is associated with a
logarithmic distributed number of data samples. We reveal relationships between
various count- and mixture-modeling distributions and construct a
Poisson-logarithmic bivariate distribution that connects the NB and Chinese
restaurant table distributions. Fundamental properties of the models are
developed, and we derive efficient Bayesian inference. It is shown that with
augmentation and normalization, the NB process and gamma-NB process can be
reduced to the Dirichlet process and hierarchical Dirichlet process,
respectively. These relationships highlight theoretical, structural and
computational advantages of the NB process. A variety of NB processes,
including the beta-geometric, beta-NB, marked-beta-NB, marked-gamma-NB and
zero-inflated-NB processes, with distinct sharing mechanisms, are also
constructed. These models are applied to topic modeling, with connections made
to existing algorithms under Poisson factor analysis. Example results show the
importance of inferring both the NB dispersion and probability parameters.
On Optimal Probabilities in Stochastic Coordinate Descent Methods
Authors: Peter Richtárik, Martin Takáč
Date: 2013-10-13 00:00:00

We propose and analyze a new parallel coordinate descent method---`NSync---in
which at each iteration a random subset of coordinates is updated, in parallel,
allowing for the subsets to be chosen non-uniformly. We derive convergence
rates under a strong convexity assumption, and comment on how to assign
probabilities to the sets to optimize the bound. The complexity and practical
performance of the method can outperform its uniform variant by an order of
magnitude. Surprisingly, the strategy of updating a single randomly selected
coordinate per iteration---with optimal probabilities---may require less
iterations, both in theory and practice, than the strategy of updating all
coordinates at every iteration.
Joint Indoor Localization and Radio Map Construction with Limited Deployment Load
Authors: Sameh Sorour, Yves Lostanlen, Shahrokh Valaee
Date: 2013-10-12 00:00:00
Tasks: Indoor Localization

One major bottleneck in the practical implementation of received signal
strength (RSS) based indoor localization systems is the extensive deployment
efforts required to construct the radio maps through fingerprinting. In this
paper, we aim to design an indoor localization scheme that can be directly
employed without building a full fingerprinted radio map of the indoor
environment. By accumulating the information of localized RSSs, this scheme can
also simultaneously construct the radio map with limited calibration. To design
this scheme, we employ a source data set that possesses the same spatial
correlation of the RSSs in the indoor environment under study. The knowledge of
this data set is then transferred to a limited number of calibration
fingerprints and one or several RSS observations with unknown locations, in
order to perform direct localization of these observations using manifold
alignment. We test two different source data sets, namely a simulated radio
propagation map and the environments plan coordinates. For moving users, we
exploit the correlation of their observations to improve the localization
accuracy. The online testing in two indoor environments shows that the plan
coordinates achieve better results than the simulated radio maps, and a
negligible degradation with 70-85% reduction in calibration load.