pwc-archive/papers-with-abstracts huggingface dataset:
Learning to Mine Chinese Coordinate Terms Using the Web
Authors: Xiaojiang Huang, Xiaojun Wan, Jianguo Xiao
Date: 2015-07-08 00:00:00
Tasks: Relation

Coordinate relation refers to the relation between instances of a concept and
the relation between the directly hyponyms of a concept. In this paper, we
focus on the task of extracting terms which are coordinate with a user given
seed term in Chinese, and grouping the terms which belong to different concepts
if the seed term has several meanings. We propose a semi-supervised method that
integrates manually defined linguistic patterns and automatically learned
semi-structural patterns to extract coordinate terms in Chinese from web search
results. In addition, terms are grouped into different concepts based on their
co-occurring terms and contexts. We further calculate the saliency scores of
extracted terms and rank them accordingly. Experimental results demonstrate
that our proposed method generates results with high quality and wide coverage.
Scatter Matrix Concordance: A Diagnostic for Regressions on Subsets of Data
Authors: Michael J. Kane, Bryan Lewis, Sekhar Tatikonda, Simon Urbanek
Date: 2015-07-12 00:00:00
Tasks: Computational Efficiency, Diagnostic, regression

Linear regression models depend directly on the design matrix and its
properties. Techniques that efficiently estimate model coefficients by
partitioning rows of the design matrix are increasingly popular for large-scale
problems because they fit well with modern parallel computing architectures. We
propose a simple measure of {\em concordance} between a design matrix and a
subset of its rows that estimates how well a subset captures the
variance-covariance structure of a larger data set. We illustrate the use of
this measure in a heuristic method for selecting row partition sizes that
balance statistical and computational efficiency goals in real-world problems.
Tensor principal component analysis via sum-of-squares proofs
Authors: Samuel B. Hopkins, Jonathan Shi, David Steurer
Date: 2015-07-12 00:00:00

We study a statistical model for the tensor principal component analysis
problem introduced by Montanari and Richard: Given a order-$3$ tensor $T$ of
the form $T = \tau \cdot v_0^{\otimes 3} + A$, where $\tau \geq 0$ is a
signal-to-noise ratio, $v_0$ is a unit vector, and $A$ is a random noise
tensor, the goal is to recover the planted vector $v_0$. For the case that $A$
has iid standard Gaussian entries, we give an efficient algorithm to recover
$v_0$ whenever $\tau \geq \omega(n^{3/4} \log(n)^{1/4})$, and certify that the
recovered vector is close to a maximum likelihood estimator, all with high
probability over the random choice of $A$. The previous best algorithms with
provable guarantees required $\tau \geq \Omega(n)$.
  In the regime $\tau \leq o(n)$, natural tensor-unfolding-based spectral
relaxations for the underlying optimization problem break down (in the sense
that their integrality gap is large). To go beyond this barrier, we use convex
relaxations based on the sum-of-squares method. Our recovery algorithm proceeds
by rounding a degree-$4$ sum-of-squares relaxations of the
maximum-likelihood-estimation problem for the statistical model. To complement
our algorithmic results, we show that degree-$4$ sum-of-squares relaxations
break down for $\tau \leq O(n^{3/4}/\log(n)^{1/4})$, which demonstrates that
improving our current guarantees (by more than logarithmic factors) would
require new techniques or might even be intractable.
  Finally, we show how to exploit additional problem structure in order to
solve our sum-of-squares relaxations, up to some approximation, very
efficiently. Our fastest algorithm runs in nearly-linear time using shifted
(matrix) power iteration and has similar guarantees as above. The analysis of
this algorithm also confirms a variant of a conjecture of Montanari and Richard
about singular vectors of tensor unfoldings.
Homotopy Continuation Approaches for Robust SV Classification and Regression
Authors: Shinya Suzumura, Kohei Ogawa, Masashi Sugiyama, Masayuki Karasuyama, Ichiro Takeuchi
Date: 2015-07-12 00:00:00
Tasks: Classification, General Classification, Model Selection, regression, Robust classification

In support vector machine (SVM) applications with unreliable data that
contains a portion of outliers, non-robustness of SVMs often causes
considerable performance deterioration. Although many approaches for improving
the robustness of SVMs have been studied, two major challenges remain in robust
SVM learning. First, robust learning algorithms are essentially formulated as
non-convex optimization problems. It is thus important to develop a non-convex
optimization method for robust SVM that can find a good local optimal solution.
The second practical issue is how one can tune the hyperparameter that controls
the balance between robustness and efficiency. Unfortunately, due to the
non-convexity, robust SVM solutions with slightly different hyper-parameter
values can be significantly different, which makes model selection highly
unstable. In this paper, we address these two issues simultaneously by
introducing a novel homotopy approach to non-convex robust SVM learning. Our
basic idea is to introduce parametrized formulations of robust SVM which bridge
the standard SVM and fully robust SVM via the parameter that represents the
influence of outliers. We characterize the necessary and sufficient conditions
of the local optimal solutions of robust SVM, and develop an algorithm that can
trace a path of local optimal solutions when the influence of outliers is
gradually decreased. An advantage of our homotopy approach is that it can be
interpreted as simulated annealing, a common approach for finding a good local
optimal solution in non-convex optimization problems. In addition, our homotopy
method allows stable and efficient model selection based on the path of local
optimal solutions. Empirical performances of the proposed approach are
demonstrated through intensive numerical experiments both on robust
classification and regression problems.
Scalable Bayesian Inference for Excitatory Point Process Networks
Authors: Scott W. Linderman, Ryan P. Adams
Date: 2015-07-12 00:00:00
Tasks: Bayesian Inference, Variational Inference

Networks capture our intuition about relationships in the world. They
describe the friendships between Facebook users, interactions in financial
markets, and synapses connecting neurons in the brain. These networks are
richly structured with cliques of friends, sectors of stocks, and a smorgasbord
of cell types that govern how neurons connect. Some networks, like social
network friendships, can be directly observed, but in many cases we only have
an indirect view of the network through the actions of its constituents and an
understanding of how the network mediates that activity. In this work, we focus
on the problem of latent network discovery in the case where the observable
activity takes the form of a mutually-excitatory point process known as a
Hawkes process. We build on previous work that has taken a Bayesian approach to
this problem, specifying prior distributions over the latent network structure
and a likelihood of observed activity given this network. We extend this work
by proposing a discrete-time formulation and developing a computationally
efficient stochastic variational inference (SVI) algorithm that allows us to
scale the approach to long sequences of observations. We demonstrate our
algorithm on the calcium imaging data used in the Chalearn neural connectomics
challenge.
Classifier-Based Text Simplification for Improved Machine Translation
Authors: Shruti Tyagi, Deepti Chopra, Iti Mathur, Nisheeth Joshi
Date: 2015-07-12 00:00:00
Tasks: Machine Translation, Text Simplification, Translation

Machine Translation is one of the research fields of Computational
Linguistics. The objective of many MT Researchers is to develop an MT System
that produce good quality and high accuracy output translations and which also
covers maximum language pairs. As internet and Globalization is increasing day
by day, we need a way that improves the quality of translation. For this
reason, we have developed a Classifier based Text Simplification Model for
English-Hindi Machine Translation Systems. We have used support vector machines
and Na\"ive Bayes Classifier to develop this model. We have also evaluated the
performance of these classifiers.
Auditing: Active Learning with Outcome-Dependent Query Costs
Authors: Sivan Sabato, Anand D. Sarwate, Nathan Srebro
Date: 2013-06-10 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Active Learning, Binary Classification, Fraud Detection, General Classification

We propose a learning setting in which unlabeled data is free, and the cost
of a label depends on its value, which is not known in advance. We study binary
classification in an extreme case, where the algorithm only pays for negative
labels. Our motivation are applications such as fraud detection, in which
investigating an honest transaction should be avoided if possible. We term the
setting auditing, and consider the auditing complexity of an algorithm: the
number of negative labels the algorithm requires in order to learn a hypothesis
with low relative error. We design auditing algorithms for simple hypothesis
classes (thresholds and rectangles), and show that with these algorithms, the
auditing complexity can be significantly lower than the active label
complexity. We also discuss a general competitive approach for auditing and
possible modifications to the framework.
DeepFont: Identify Your Font from An Image
Authors: Zhangyang Wang, Jianchao Yang, Hailin Jin, Eli Shechtman, Aseem Agarwala, Jonathan Brandt, Thomas S. Huang
Date: 2015-07-12 00:00:00
Tasks: Domain Adaptation, Font Recognition, Model Compression

As font is one of the core design concepts, automatic font identification and
similar font suggestion from an image or photo has been on the wish list of
many designers. We study the Visual Font Recognition (VFR) problem, and advance
the state-of-the-art remarkably by developing the DeepFont system. First of
all, we build up the first available large-scale VFR dataset, named AdobeVFR,
consisting of both labeled synthetic data and partially labeled real-world
data. Next, to combat the domain mismatch between available training and
testing data, we introduce a Convolutional Neural Network (CNN) decomposition
approach, using a domain adaptation technique based on a Stacked Convolutional
Auto-Encoder (SCAE) that exploits a large corpus of unlabeled real-world text
images combined with synthetic data preprocessed in a specific way. Moreover,
we study a novel learning-based model compression approach, in order to reduce
the DeepFont model size without sacrificing its performance. The DeepFont
system achieves an accuracy of higher than 80% (top-5) on our collected
dataset, and also produces a good font similarity measure for font selection
and suggestion. We also achieve around 6 times compression of the model without
any visible loss of recognition accuracy.
A Probabilistic Approach to Knowledge Translation
Authors: Shangpu Jiang, Daniel Lowd, Dejing Dou
Date: 2015-07-12 00:00:00
Tasks: Transfer Learning, Translation

In this paper, we focus on a novel knowledge reuse scenario where the
knowledge in the source schema needs to be translated to a semantically
heterogeneous target schema. We refer to this task as "knowledge translation"
(KT). Unlike data translation and transfer learning, KT does not require any
data from the source or target schema. We adopt a probabilistic approach to KT
by representing the knowledge in the source schema, the mapping between the
source and target schemas, and the resulting knowledge in the target schema all
as probability distributions, specially using Markov random fields and Markov
logic networks. Given the source knowledge and mappings, we use standard
learning and inference algorithms for probabilistic graphical models to find an
explicit probability distribution in the target schema that minimizes the
Kullback-Leibler divergence from the implicit distribution. This gives us a
compact probabilistic model that represents knowledge from the source schema as
well as possible, respecting the uncertainty in both the source knowledge and
the mapping. In experiments on both propositional and relational domains, we
find that the knowledge obtained by KT is comparable to other approaches that
require data, demonstrating that knowledge can be reused without data.
Dependent Indian Buffet Process-based Sparse Nonparametric Nonnegative Matrix Factorization
Authors: Junyu Xuan, Jie Lu, Guangquan Zhang, Richard Yi Da Xu, Xiangfeng Luo
Date: 2015-07-12 00:00:00
Tasks: Clustering, Recommendation Systems

Nonnegative Matrix Factorization (NMF) aims to factorize a matrix into two
optimized nonnegative matrices appropriate for the intended applications. The
method has been widely used for unsupervised learning tasks, including
recommender systems (rating matrix of users by items) and document clustering
(weighting matrix of papers by keywords). However, traditional NMF methods
typically assume the number of latent factors (i.e., dimensionality of the
loading matrices) to be fixed. This assumption makes them inflexible for many
applications. In this paper, we propose a nonparametric NMF framework to
mitigate this issue by using dependent Indian Buffet Processes (dIBP). In a
nutshell, we apply a correlation function for the generation of two stick
weights associated with each pair of columns of loading matrices, while still
maintaining their respective marginal distribution specified by IBP. As a
consequence, the generation of two loading matrices will be column-wise
(indirectly) correlated. Under this same framework, two classes of correlation
function are proposed (1) using Bivariate beta distribution and (2) using
Copula function. Both methods allow us to adopt our work for various
applications by flexibly choosing an appropriate parameter settings. Compared
with the other state-of-the art approaches in this area, such as using Gaussian
Process (GP)-based dIBP, our work is seen to be much more flexible in terms of
allowing the two corresponding binary matrix columns to have greater variations
in their non-zero entries. Our experiments on the real-world and synthetic
datasets show that three proposed models perform well on the document
clustering task comparing standard NMF without predefining the dimension for
the factor matrices, and the Bivariate beta distribution-based and Copula-based
models have better flexibility than the GP-based model.
Using Bayesian Network Representations for Effective Sampling from Generative Network Models
Authors: Pablo Robles-Granda, Sebastian Moreno, Jennifer Neville
Date: 2015-07-11 00:00:00

Bayesian networks (BNs) are used for inference and sampling by exploiting
conditional independence among random variables. Context specific independence
(CSI) is a property of graphical models where additional independence relations
arise in the context of particular values of random variables (RVs).
Identifying and exploiting CSI properties can simplify inference. Some
generative network models (models that generate social/information network
samples from a network distribution P(G)), with complex interactions among a
set of RVs, can be represented with probabilistic graphical models, in
particular with BNs. In the present work we show one such a case. We discuss
how a mixed Kronecker Product Graph Model can be represented as a BN, and study
its BN properties that can be used for efficient sampling. Specifically, we
show that instead of exhibiting CSI properties, the model has deterministic
context-specific dependence (DCSD). Exploiting this property focuses the
sampling method on a subset of the sampling space that improves efficiency.
A model building framework for Answer Set Programming with external computations
Authors: Thomas Eiter, Michael Fink, Giovambattista Ianni, Thomas Krennwallner, Christoph Redl, Peter Schüller
Date: 2015-07-06 00:00:00

As software systems are getting increasingly connected, there is a need for
equipping nonmonotonic logic programs with access to external sources that are
possibly remote and may contain information in heterogeneous formats. To cater
for this need, HEX programs were designed as a generalization of answer set
programs with an API style interface that allows to access arbitrary external
sources, providing great flexibility. Efficient evaluation of such programs
however is challenging, and it requires to interleave external computation and
model building; to decide when to switch between these tasks is difficult, and
existing approaches have limited scalability in many real-world application
scenarios. We present a new approach for the evaluation of logic programs with
external source access, which is based on a configurable framework for dividing
the non-ground program into possibly overlapping smaller parts called
evaluation units. The latter will be processed by interleaving external
evaluation and model building using an evaluation graph and a model graph,
respectively, and by combining intermediate results. Experiments with our
prototype implementation show a significant improvement compared to previous
approaches. While designed for HEX-programs, the new evaluation approach may be
deployed to related rule-based formalisms as well.
Best Subset Selection via a Modern Optimization Lens
Authors: Dimitris Bertsimas, Angela King, Rahul Mazumder
Date: 2015-07-11 00:00:00
Tasks: regression, Sparse Learning

In the last twenty-five years (1990-2014), algorithmic advances in integer
optimization combined with hardware improvements have resulted in an
astonishing 200 billion factor speedup in solving Mixed Integer Optimization
(MIO) problems. We present a MIO approach for solving the classical best subset
selection problem of choosing $k$ out of $p$ features in linear regression
given $n$ observations. We develop a discrete extension of modern first order
continuous optimization methods to find high quality feasible solutions that we
use as warm starts to a MIO solver that finds provably optimal solutions. The
resulting algorithm (a) provides a solution with a guarantee on its
suboptimality even if we terminate the algorithm early, (b) can accommodate
side constraints on the coefficients of the linear regression and (c) extends
to finding best subset solutions for the least absolute deviation loss
function. Using a wide variety of synthetic and real datasets, we demonstrate
that our approach solves problems with $n$ in the 1000s and $p$ in the 100s in
minutes to provable optimality, and finds near optimal solutions for $n$ in the
100s and $p$ in the 1000s in minutes. We also establish via numerical
experiments that the MIO approach performs better than {\texttt {Lasso}} and
other popularly used sparse learning procedures, in terms of achieving sparse
solutions with good predictive power.
Joint estimation of quantile planes over arbitrary predictor spaces
Authors: Yun Yang, Surya Tokdar
Date: 2015-07-11 00:00:00
Tasks: Econometrics, parameter estimation, quantile regression

In spite of the recent surge of interest in quantile regression, joint
estimation of linear quantile planes remains a great challenge in statistics
and econometrics. We propose a novel parametrization that characterizes any
collection of non-crossing quantile planes over arbitrarily shaped convex
predictor domains in any dimension by means of unconstrained scalar, vector and
function valued parameters. Statistical models based on this parametrization
inherit a fast computation of the likelihood function, enabling penalized
likelihood or Bayesian approaches to model fitting. We introduce a complete
Bayesian methodology by using Gaussian process prior distributions on the
function valued parameters and develop a robust and efficient Markov chain
Monte Carlo parameter estimation. The resulting method is shown to offer
posterior consistency under mild tail and regularity conditions. We present
several illustrative examples where the new method is compared against existing
approaches and is found to offer better accuracy, coverage and model fit.
A new boosting algorithm based on dual averaging scheme
Authors: Nan Wang
Date: 2015-07-11 00:00:00
Tasks: BIG-bench Machine Learning

The fields of machine learning and mathematical optimization increasingly
intertwined. The special topic on supervised learning and convex optimization
examines this interplay. The training part of most supervised learning
algorithms can usually be reduced to an optimization problem that minimizes a
loss between model predictions and training data. While most optimization
techniques focus on accuracy and speed of convergence, the qualities of good
optimization algorithm from the machine learning perspective can be quite
different since machine learning is more than fitting the data. Better
optimization algorithms that minimize the training loss can possibly give very
poor generalization performance. In this paper, we examine a particular kind of
machine learning algorithm, boosting, whose training process can be viewed as
functional coordinate descent on the exponential loss. We study the relation
between optimization techniques and machine learning by implementing a new
boosting algorithm. DABoost, based on dual-averaging scheme and study its
generalization performance. We show that DABoost, although slower in reducing
the training error, in general enjoys a better generalization error than
AdaBoost.
Ontology Matching with Knowledge Rules
Authors: Shangpu Jiang, Daniel Lowd, Dejing Dou
Date: 2015-07-11 00:00:00
Tasks: Ontology Matching

Ontology matching is the process of automatically determining the semantic
equivalences between the concepts of two ontologies. Most ontology matching
algorithms are based on two types of strategies: terminology-based strategies,
which align concepts based on their names or descriptions, and structure-based
strategies, which exploit concept hierarchies to find the alignment. In many
domains, there is additional information about the relationships of concepts
represented in various ways, such as Bayesian networks, decision trees, and
association rules. We propose to use the similarities between these
relationships to find more accurate alignments. We accomplish this by defining
soft constraints that prefer alignments where corresponding concepts have the
same local relationships encoded as knowledge rules. We use a probabilistic
framework to integrate this new knowledge-based strategy with standard
terminology-based and structure-based strategies. Furthermore, our method is
particularly effective in identifying correspondences between complex concepts.
Our method achieves substantially better F-score than the previous
state-of-the-art on three ontology matching domains.