pwc-archive/papers-with-abstracts huggingface dataset:
Adaptation Algorithm and Theory Based on Generalized Discrepancy
Authors: Corinna Cortes, Mehryar Mohri, Andres Muñoz Medina
Date: 2014-05-07 00:00:00
Tasks: Domain Adaptation

We present a new algorithm for domain adaptation improving upon a discrepancy
minimization algorithm previously shown to outperform a number of algorithms
for this task. Unlike many previous algorithms for domain adaptation, our
algorithm does not consist of a fixed reweighting of the losses over the
training sample. We show that our algorithm benefits from a solid theoretical
foundation and more favorable learning bounds than discrepancy minimization. We
present a detailed description of our algorithm and give several efficient
solutions for solving its optimization problem. We also report the results of
several experiments showing that it outperforms discrepancy minimization.
Microsoft COCO: Common Objects in Context
Authors: Tsung-Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, Piotr Dollár
Date: 2014-05-01 00:00:00
Tasks: Instance Segmentation, Object, Object Localization, Object Recognition, Scene Understanding, Segmentation, Semantic Segmentation

We present a new dataset with the goal of advancing the state-of-the-art in
object recognition by placing the question of object recognition in the context
of the broader question of scene understanding. This is achieved by gathering
images of complex everyday scenes containing common objects in their natural
context. Objects are labeled using per-instance segmentations to aid in precise
object localization. Our dataset contains photos of 91 objects types that would
be easily recognizable by a 4 year old. With a total of 2.5 million labeled
instances in 328k images, the creation of our dataset drew upon extensive crowd
worker involvement via novel user interfaces for category detection, instance
spotting and instance segmentation. We present a detailed statistical analysis
of the dataset in comparison to PASCAL, ImageNet, and SUN. Finally, we provide
baseline performance analysis for bounding box and segmentation detection
results using a Deformable Parts Model.
Decentralized Control of Partially Observable Markov Decision Processes using Belief Space Macro-actions
Authors: Shayegan Omidshafiei, Ali-akbar Agha-mohammadi, Christopher Amato, Jonathan P. How
Date: 2015-02-20 00:00:00
Tasks: Decision Making

The focus of this paper is on solving multi-robot planning problems in
continuous spaces with partial observability. Decentralized partially
observable Markov decision processes (Dec-POMDPs) are general models for
multi-robot coordination problems, but representing and solving Dec-POMDPs is
often intractable for large problems. To allow for a high-level representation
that is natural for multi-robot problems and scalable to large discrete and
continuous problems, this paper extends the Dec-POMDP model to the
decentralized partially observable semi-Markov decision process (Dec-POSMDP).
The Dec-POSMDP formulation allows asynchronous decision-making by the robots,
which is crucial in multi-robot domains. We also present an algorithm for
solving this Dec-POSMDP which is much more scalable than previous methods since
it can incorporate closed-loop belief space macro-actions in planning. These
macro-actions are automatically constructed to produce robust solutions. The
proposed method's performance is evaluated on a complex multi-robot package
delivery problem under uncertainty, showing that our approach can naturally
represent multi-robot problems and provide high-quality solutions for
large-scale problems.
OntoLoki: an automatic, instance-based method for the evaluation of biological ontologies on the Semantic Web
Authors: Benjamin M. Good, Gavin Ha, Chi K. Ho, Mark D. Wilkinson
Date: 2015-02-20 00:00:00

The delineation of logical definitions for each class in an ontology and the
consistent application of these definitions to the assignment of instances to
classes are important criteria for ontology evaluation. If ontologies are
specified with property-based restrictions on class membership, then such
consistency can be checked automatically. If no such logical restrictions are
applied, as is the case with many biological ontologies, there are currently no
automated methods for measuring the semantic consistency of instance assignment
on an ontology-wide scale, nor for inferring the patterns of properties that
might define a particular class. We constructed a program that takes as its
input an OWL/RDF knowledge base containing an ontology, instances associated
with each of the classes in the ontology, and properties of those instances.
For each class, it outputs: 1) a rule for determining class membership based on
the properties of the instances and 2) a quantitative score for the class that
reflects the ability of the identified rule to correctly predict class
membership for the instances in the knowledge base. We evaluated this program
using both artificial knowledge bases of known quality and real, widely used
ontologies. The results indicate that the suggested method can be used to
conduct objective, automatic, data-driven evaluations of biological ontologies
without formal class definitions in regards to the property-based consistency
of instance-assignment. This inductive method complements existing, purely
deductive approaches to automatic consistency checking, offering not just the
potential to help in the ontology engineering process but also in the knowledge
discovery process.
Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
Authors: Thomas Steinke, Jonathan Ullman
Date: 2014-10-05 00:00:00
Tasks: valid

We show an essentially tight bound on the number of adaptively chosen
statistical queries that a computationally efficient algorithm can answer
accurately given $n$ samples from an unknown distribution. A statistical query
asks for the expectation of a predicate over the underlying distribution, and
an answer to a statistical query is accurate if it is "close" to the correct
expectation over the distribution. This question was recently studied by Dwork
et al., who showed how to answer $\tilde{\Omega}(n^2)$ queries efficiently, and
also by Hardt and Ullman, who showed that answering $\tilde{O}(n^3)$ queries is
hard. We close the gap between the two bounds and show that, under a standard
hardness assumption, there is no computationally efficient algorithm that,
given $n$ samples from an unknown distribution, can give valid answers to
$O(n^2)$ adaptively chosen statistical queries. An implication of our results
is that computationally efficient algorithms for answering arbitrary,
adaptively chosen statistical queries may as well be differentially private.
  We obtain our results using a new connection between the problem of answering
adaptively chosen statistical queries and a combinatorial object called an
interactive fingerprinting code. In order to optimize our hardness result, we
give a new Fourier-analytic approach to analyzing fingerprinting codes that is
simpler, more flexible, and yields better parameters than previous
constructions.
Development of a VO Registry Subject Ontology using Automated Methods
Authors: Brian Thomas
Date: 2015-02-20 00:00:00

We report on our initial work to automate the generation of a domain ontology
using subject fields of resources held in the Virtual Observatory registry.
Preliminary results are comparable to more generalized ontology learning
software currently in use. We expect to be able to refine our solution to
improve both the depth and breadth of the generated ontology.
Web Similarity in Sets of Search Terms using Database Queries
Authors: Andrew R. Cohen, Paul M. B. Vitanyi
Date: 2015-02-20 00:00:00

Normalized web distance (NWD) is a similarity or normalized semantic distance based on the World Wide Web or another large electronic database, for instance Wikipedia, and a search engine that returns reliable aggregate page counts. For sets of search terms the NWD gives a common similarity (common semantics) on a scale from 0 (identical) to 1 (completely different). The NWD approximates the similarity of members of a set according to all (upper semi)computable properties. We develop the theory and give applications of classifying using Amazon, Wikipedia, and the NCBI website from the National Institutes of Health. The last gives new correlations between health hazards. A restriction of the NWD to a set of two yields the earlier normalized google distance (NGD) but no combination of the NGD's of pairs in a set can extract the information the NWD extracts from the set. The NWD enables a new contextual (different databases) learning approachbased on Kolmogorov complexity theory that incorporates knowledge from these databases.
Refining Adverse Drug Reactions using Association Rule Mining for Electronic Healthcare Data
Authors: Jenna M. Reps, Uwe Aickelin, Jiangang Ma, Yanchun Zhang
Date: 2015-02-20 00:00:00

Side effects of prescribed medications are a common occurrence. Electronic
healthcare databases present the opportunity to identify new side effects
efficiently but currently the methods are limited due to confounding (i.e. when
an association between two variables is identified due to them both being
associated to a third variable).
  In this paper we propose a proof of concept method that learns common
associations and uses this knowledge to automatically refine side effect
signals (i.e. exposure-outcome associations) by removing instances of the
exposure-outcome associations that are caused by confounding. This leaves the
signal instances that are most likely to correspond to true side effect
occurrences. We then calculate a novel measure termed the confounding-adjusted
risk value, a more accurate absolute risk value of a patient experiencing the
outcome within 60 days of the exposure.
  Tentative results suggest that the method works. For the four signals (i.e.
exposure-outcome associations) investigated we are able to correctly filter the
majority of exposure-outcome instances that were unlikely to correspond to true
side effects. The method is likely to improve when tuning the association rule
mining parameters for specific health outcomes.
  This paper shows that it may be possible to filter signals at a patient level
based on association rules learned from considering patients' medical
histories. However, additional work is required to develop a way to automate
the tuning of the method's parameters.
The Complexity of Reasoning with FODD and GFODD
Authors: Benjamin J. Hescott, Roni Khardon
Date: 2014-07-05 00:00:00

Recent work introduced Generalized First Order Decision Diagrams (GFODD) as a
knowledge representation that is useful in mechanizing decision theoretic
planning in relational domains. GFODDs generalize function-free first order
logic and include numerical values and numerical generalizations of existential
and universal quantification. Previous work presented heuristic inference
algorithms for GFODDs and implemented these heuristics in systems for decision
theoretic planning. In this paper, we study the complexity of the computational
problems addressed by such implementations. In particular, we study the
evaluation problem, the satisfiability problem, and the equivalence problem for
GFODDs under the assumption that the size of the intended model is given with
the problem, a restriction that guarantees decidability. Our results provide a
complete characterization placing these problems within the polynomial
hierarchy. The same characterization applies to the corresponding restriction
of problems in first order logic, giving an interesting new avenue for
efficient inference when the number of objects is bounded. Our results show
that for $\Sigma_k$ formulas, and for corresponding GFODDs, evaluation and
satisfiability are $\Sigma_k^p$ complete, and equivalence is $\Pi_{k+1}^p$
complete. For $\Pi_k$ formulas evaluation is $\Pi_k^p$ complete, satisfiability
is one level higher and is $\Sigma_{k+1}^p$ complete, and equivalence is
$\Pi_{k+1}^p$ complete.
Achieving All with No Parameters: Adaptive NormalHedge
Authors: Haipeng Luo, Robert E. Schapire
Date: 2015-02-20 00:00:00
Tasks: All

We study the classic online learning problem of predicting with expert
advice, and propose a truly parameter-free and adaptive algorithm that achieves
several objectives simultaneously without using any prior information. The main
component of this work is an improved version of the NormalHedge.DT algorithm
(Luo and Schapire, 2014), called AdaNormalHedge. On one hand, this new
algorithm ensures small regret when the competitor has small loss and almost
constant regret when the losses are stochastic. On the other hand, the
algorithm is able to compete with any convex combination of the experts
simultaneously, with a regret in terms of the relative entropy of the prior and
the competitor. This resolves an open problem proposed by Chaudhuri et al.
(2009) and Chernov and Vovk (2010). Moreover, we extend the results to the
sleeping expert setting and provide two applications to illustrate the power of
AdaNormalHedge: 1) competing with time-varying unknown competitors and 2)
predicting almost as well as the best pruning tree. Our results on these
applications significantly improve previous work from different aspects, and a
special case of the first application resolves another open problem proposed by
Warmuth and Koolen (2014) on whether one can simultaneously achieve optimal
shifting regret for both adversarial and stochastic losses.
Supervised Dictionary Learning and Sparse Representation-A Review
Authors: Mehrdad J. Gangeh, Ahmed K. Farahat, Ali Ghodsi, Mohamed S. Kamel
Date: 2015-02-20 00:00:00
Tasks: Denoising, Dictionary Learning, General Classification

Dictionary learning and sparse representation (DLSR) is a recent and
successful mathematical model for data representation that achieves
state-of-the-art performance in various fields such as pattern recognition,
machine learning, computer vision, and medical imaging. The original
formulation for DLSR is based on the minimization of the reconstruction error
between the original signal and its sparse representation in the space of the
learned dictionary. Although this formulation is optimal for solving problems
such as denoising, inpainting, and coding, it may not lead to optimal solution
in classification tasks, where the ultimate goal is to make the learned
dictionary and corresponding sparse representation as discriminative as
possible. This motivated the emergence of a new category of techniques, which
is appropriately called supervised dictionary learning and sparse
representation (S-DLSR), leading to more optimal dictionary and sparse
representation in classification tasks. Despite many research efforts for
S-DLSR, the literature lacks a comprehensive view of these techniques, their
connections, advantages and shortcomings. In this paper, we address this gap
and provide a review of the recently proposed algorithms for S-DLSR. We first
present a taxonomy of these algorithms into six categories based on the
approach taken to include label information into the learning of the dictionary
and/or sparse representation. For each category, we draw connections between
the algorithms in this category and present a unified framework for them. We
then provide guidelines for applied researchers on how to represent and learn
the building blocks of an S-DLSR solution based on the problem at hand. This
review provides a broad, yet deep, view of the state-of-the-art methods for
S-DLSR and allows for the advancement of research and development in this
emerging area of research.
Feature-Budgeted Random Forest
Authors: Feng Nan, Joseph Wang, Venkatesh Saligrama
Date: 2015-02-20 00:00:00
Tasks: Prediction

We seek decision rules for prediction-time cost reduction, where complete
data is available for training, but during prediction-time, each feature can
only be acquired for an additional cost. We propose a novel random forest
algorithm to minimize prediction error for a user-specified {\it average}
feature acquisition budget. While random forests yield strong generalization
performance, they do not explicitly account for feature costs and furthermore
require low correlation among trees, which amplifies costs. Our random forest
grows trees with low acquisition cost and high strength based on greedy minimax
cost-weighted-impurity splits. Theoretically, we establish near-optimal
acquisition cost guarantees for our algorithm. Empirically, on a number of
benchmark datasets we demonstrate superior accuracy-cost curves against
state-of-the-art prediction-time algorithms.
Building pattern recognition applications with the SPARE library
Authors: Lorenzo Livi, Guido Del Vescovo, Antonello Rizzi, Fabio Massimo Frattale Mascioli
Date: 2014-10-20 00:00:00
Tasks: Clustering, General Classification

This paper presents the SPARE C++ library, an open source software tool
conceived to build pattern recognition and soft computing systems. The library
follows the requirement of the generality: most of the implemented algorithms
are able to process user-defined input data types transparently, such as
labeled graphs and sequences of objects, as well as standard numeric vectors.
Here we present a high-level picture of the SPARE library characteristics,
focusing instead on the specific practical possibility of constructing pattern
recognition systems for different input data types. In particular, as a proof
of concept, we discuss two application instances involving clustering of
real-valued multidimensional sequences and classification of labeled graphs.
A Data Mining framework to model Consumer Indebtedness with Psychological Factors
Authors: Alexandros Ladas, Eamonn Ferguson, Uwe Aickelin, Jon Garibaldi
Date: 2015-02-20 00:00:00

Modelling Consumer Indebtedness has proven to be a problem of complex nature.
In this work we utilise Data Mining techniques and methods to explore the
multifaceted aspect of Consumer Indebtedness by examining the contribution of
Psychological Factors, like Impulsivity to the analysis of Consumer Debt. Our
results confirm the beneficial impact of Psychological Factors in modelling
Consumer Indebtedness and suggest a new approach in analysing Consumer Debt,
that would take into consideration more Psychological characteristics of
consumers and adopt techniques and practices from Data Mining.
On predictability of rare events leveraging social media: a machine learning perspective
Authors: Lei Le, Emilio Ferrara, Alessandro Flammini
Date: 2015-02-20 00:00:00
Tasks: BIG-bench Machine Learning, Sentiment Analysis

Information extracted from social media streams has been leveraged to
forecast the outcome of a large number of real-world events, from political
elections to stock market fluctuations. An increasing amount of studies
demonstrates how the analysis of social media conversations provides cheap
access to the wisdom of the crowd. However, extents and contexts in which such
forecasting power can be effectively leveraged are still unverified at least in
a systematic way. It is also unclear how social-media-based predictions compare
to those based on alternative information sources. To address these issues,
here we develop a machine learning framework that leverages social media
streams to automatically identify and predict the outcomes of soccer matches.
We focus in particular on matches in which at least one of the possible
outcomes is deemed as highly unlikely by professional bookmakers. We argue that
sport events offer a systematic approach for testing the predictive power of
social media, and allow to compare such power against the rigorous baselines
set by external sources. Despite such strict baselines, our framework yields
above 8% marginal profit when used to inform simple betting strategies. The
system is based on real-time sentiment analysis and exploits data collected
immediately before the games, allowing for informed bets. We discuss the
rationale behind our approach, describe the learning framework, its prediction
performance and the return it provides as compared to a set of betting
strategies. To test our framework we use both historical Twitter data from the
2014 FIFA World Cup games, and real-time Twitter data collected by monitoring
the conversations about all soccer matches of four major European tournaments
(FA Premier League, Serie A, La Liga, and Bundesliga), and the 2014 UEFA
Champions League, during the period between Oct. 25th 2014 and Nov. 26th 2014.
Pseudo Fuzzy Set
Authors: Sukanta Nayak, Snehashish Chakraverty
Date: 2015-02-20 00:00:00
Tasks: Triplet

Here a novel idea to handle imprecise or vague set viz. Pseudo fuzzy set has
been proposed. Pseudo fuzzy set is a triplet of element and its two membership
functions. Both the membership functions may or may not be dependent. The
hypothesis is that every positive sense has some negative sense. So, one
membership function has been considered as positive and another as negative.
Considering this concept, here the development of Pseudo fuzzy set and its
property along with Pseudo fuzzy numbers has been discussed.
NP-Hardness and Inapproximability of Sparse PCA
Authors: Malik Magdon-Ismail
Date: 2015-02-19 00:00:00

We give a reduction from {\sc clique} to establish that sparse PCA is
NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse
PCA (unless P=NP). Under weaker complexity assumptions, we also exclude
polynomial constant-factor approximation algorithms.
An Approach For Transforming of Relational Databases to OWL Ontology
Authors: Mona Dadjoo, Esmaeil Kheirkhah
Date: 2015-02-20 00:00:00
Tasks: Management, Retrieval

Rapid growth of documents, web pages, and other types of text content is a
huge challenge for the modern content management systems. One of the problems
in the areas of information storage and retrieval is the lacking of semantic
data. Ontologies can present knowledge in sharable and repeatedly usable manner
and provide an effective way to reduce the data volume overhead by encoding the
structure of a particular domain. Metadata in relational databases can be used
to extract ontology from database in a special domain. According to solve the
problem of sharing and reusing of data, approaches based on transforming
relational database to ontology are proposed. In this paper we propose a method
for automatic ontology construction based on relational database. Mining and
obtaining further components from relational database leads to obtain knowledge
with high semantic power and more expressiveness. Triggers are one of the
database components which could be transformed to the ontology model and
increase the amount of power and expressiveness of knowledge by presenting part
of the knowledge dynamically