pwc-archive/papers-with-abstracts huggingface dataset:
Group Recommendations: Axioms, Impossibilities, and Random Walks
Authors: Omer Lev, Moshe Tennenholtz
Date: 2017-07-27 00:00:00
Tasks: Recommendation Systems

We introduce an axiomatic approach to group recommendations, in line of
previous work on the axiomatic treatment of trust-based recommendation systems,
ranking systems, and other foundational work on the axiomatic approach to
internet mechanisms in social choice settings. In group recommendations we wish
to recommend to a group of agents, consisting of both opinionated and undecided
members, a joint choice that would be acceptable to them. Such a system has
many applications, such as choosing a movie or a restaurant to go to with a
group of friends, recommending games for online game players, & other communal
activities.
  Our method utilizes a given social graph to extract information on the
undecided, relying on the agents influencing them. We first show that a set of
fairly natural desired requirements (a.k.a axioms) leads to an impossibility,
rendering mutual satisfaction of them unreachable. However, we also show a
modified set of axioms that fully axiomatize a group variant of the random-walk
recommendation system, expanding a previous result from the individual
recommendation case.
An Epistemic Foundation for Authentication Logics (Extended Abstract)
Authors: Joseph Y. Halpern, Ron van der Meyden, Riccardo Pucella
Date: 2017-07-27 00:00:00
Tasks: Translation

While there have been many attempts, going back to BAN logic, to base
reasoning about security protocols on epistemic notions, they have not been all
that successful. Arguably, this has been due to the particular logics chosen.
We present a simple logic based on the well-understood modal operators of
knowledge, time, and probability, and show that it is able to handle issues
that have often been swept under the rug by other approaches, while being
flexible enough to capture all the higher- level security notions that appear
in BAN logic. Moreover, while still assuming that the knowledge operator allows
for unbounded computation, it can handle the fact that a computationally
bounded agent cannot decrypt messages in a natural way, by distinguishing
strings and message terms. We demonstrate that our logic can capture BAN logic
notions by providing a translation of the BAN operators into our logic,
capturing belief by a form of probabilistic knowledge.
The Topology of Statistical Verifiability
Authors: Konstantin Genin, Kevin T. Kelly
Date: 2017-07-27 00:00:00
Tasks: Learning Theory, Philosophy

Topological models of empirical and formal inquiry are increasingly
prevalent. They have emerged in such diverse fields as domain theory [1, 16],
formal learning theory [18], epistemology and philosophy of science [10, 15, 8,
9, 2], statistics [6, 7] and modal logic [17, 4]. In those applications, open
sets are typically interpreted as hypotheses deductively verifiable by true
propositional information that rules out relevant possibilities. However, in
statistical data analysis, one routinely receives random samples logically
compatible with every statistical hypothesis. We bridge the gap between
propositional and statistical data by solving for the unique topology on
probability measures in which the open sets are exactly the statistically
verifiable hypotheses. Furthermore, we extend that result to a topological
characterization of learnability in the limit from statistical data.
Binary Voting with Delegable Proxy: An Analysis of Liquid Democracy
Authors: Zoé Christoff, Davide Grossi
Date: 2017-07-27 00:00:00

The paper provides an analysis of the voting method known as delegable proxy
voting, or liquid democracy. The analysis first positions liquid democracy
within the theory of binary aggregation. It then focuses on two issues of the
system: the occurrence of delegation cycles; and the effect of delegations on
individual rationality when voting on logically interdependent propositions. It
finally points to proposals on how the system may be modified in order to
address the above issues.
Preservation of Semantic Properties during the Aggregation of Abstract Argumentation Frameworks
Authors: Weiwei Chen, Ulle Endriss
Date: 2017-07-27 00:00:00
Tasks: Abstract Argumentation

An abstract argumentation framework can be used to model the argumentative
stance of an agent at a high level of abstraction, by indicating for every pair
of arguments that is being considered in a debate whether the first attacks the
second. When modelling a group of agents engaged in a debate, we may wish to
aggregate their individual argumentation frameworks to obtain a single such
framework that reflects the consensus of the group. Even when agents disagree
on many details, there may well be high-level agreement on important semantic
properties, such as the acceptability of a given argument. Using techniques
from social choice theory, we analyse under what circumstances such semantic
properties agreed upon by the individual agents can be preserved under
aggregation.
Relaxing Exclusive Control in Boolean Games
Authors: Francesco Belardinelli, Umberto Grandi, Andreas Herzig, Dominique Longin, Emiliano Lorini, Arianna Novaro, Laurent Perrussel
Date: 2017-07-27 00:00:00

In the typical framework for boolean games (BG) each player can change the
truth value of some propositional atoms, while attempting to make her goal
true. In standard BG goals are propositional formulas, whereas in iterated BG
goals are formulas of Linear Temporal Logic. Both notions of BG are
characterised by the fact that agents have exclusive control over their set of
atoms, meaning that no two agents can control the same atom. In the present
contribution we drop the exclusivity assumption and explore structures where an
atom can be controlled by multiple agents. We introduce Concurrent Game
Structures with Shared Propositional Control (CGS-SPC) and show that they ac-
count for several classes of repeated games, including iterated boolean games,
influence games, and aggregation games. Our main result shows that, as far as
verification is concerned, CGS-SPC can be reduced to concurrent game structures
with exclusive control. This result provides a polynomial reduction for the
model checking problem of specifications in Alternating-time Temporal Logic on
CGS-SPC.
A Logic for Global and Local Announcements
Authors: Francesco Belardinelli, Hans van Ditmarsch, Wiebe van der Hoek
Date: 2017-07-27 00:00:00

In this paper we introduce {\em global and local announcement logic} (GLAL),
a dynamic epistemic logic with two distinct announcement operators --
$[\phi]^+_A$ and $[\phi]^-_A$ indexed to a subset $A$ of the set $Ag$ of all
agents -- for global and local announcements respectively. The boundary case
$[\phi]^+_{Ag}$ corresponds to the public announcement of $\phi$, as known from
the literature. Unlike standard public announcements, which are {\em model
transformers}, the global and local announcements are {\em pointed model
transformers}. In particular, the update induced by the announcement may be
different in different states of the model. Therefore, the resulting
computations are trees of models, rather than the typical sequences. A
consequence of our semantics is that modally bisimilar states may be
distinguished in our logic. Then, we provide a stronger notion of bisimilarity
and we show that it preserves modal equivalence in GLAL. Additionally, we show
that GLAL is strictly more expressive than public announcement logic with
common knowledge. We prove a wide range of validities for GLAL involving the
interaction between dynamics and knowledge, and show that the satisfiability
problem for GLAL is decidable. We illustrate the formal machinery by means of
detailed epistemic scenarios.
Common Knowledge in a Logic of Gossips
Authors: Krzysztof R. Apt, Dominik Wojtczak
Date: 2017-07-27 00:00:00

Gossip protocols aim at arriving, by means of point-to-point or group
communications, at a situation in which all the agents know each other secrets.
Recently a number of authors studied distributed epistemic gossip protocols.
These protocols use as guards formulas from a simple epistemic logic, which
makes their analysis and verification substantially easier.
  We study here common knowledge in the context of such a logic. First, we
analyze when it can be reduced to iterated knowledge. Then we show that the
semantics and truth for formulas without nested common knowledge operator are
decidable. This implies that implementability, partial correctness and
termination of distributed epistemic gossip protocols that use non-nested
common knowledge operator is decidable, as well. Given that common knowledge is
equivalent to an infinite conjunction of nested knowledge, these results are
non-trivial generalizations of the corresponding decidability results for the
original epistemic logic, established in (Apt & Wojtczak, 2016).
  K. R. Apt & D. Wojtczak (2016): On Decidability of a Logic of Gossips. In
Proc. of JELIA 2016, pp. 18-33, doi:10.1007/ 978-3-319-48758-8_2.
Cheryl's Birthday
Authors: Hans van Ditmarsch, Michael Ian Hartley, Barteld Kooi, Jonathan Welton, Joseph B. W. Yeo
Date: 2017-07-27 00:00:00

We present four logic puzzles and after that their solutions. Joseph Yeo designed 'Cheryl's Birthday'. Mike Hartley came up with a novel solution for 'One Hundred Prisoners and a Light Bulb'. Jonathan Welton designed 'A Blind Guess' and 'Abby's Birthday'. Hans van Ditmarsch and Barteld Kooi authored the puzzlebook 'One Hundred Prisoners and a Light Bulb' that contains other knowledge puzzles, and that can also be found on the webpage http://personal.us.es/hvd/lightbulb.html dedicated to the book.
Learning audio sequence representations for acoustic event classification
Authors: Zixing Zhang, Ding Liu, Jing Han, Kun Qian, Björn Schuller
Date: 2017-07-27 00:00:00
Tasks: Classification, Decoder, General Classification

Acoustic Event Classification (AEC) has become a significant task for machines to perceive the surrounding auditory scene. However, extracting effective representations that capture the underlying characteristics of the acoustic events is still challenging. Previous methods mainly focused on designing the audio features in a `hand-crafted' manner. Interestingly, data-learnt features have been recently reported to show better performance. Up to now, these were only considered on the frame level. In this article, we propose an unsupervised learning framework to learn a vector representation of an audio sequence for AEC. This framework consists of a Recurrent Neural Network (RNN) encoder and an RNN decoder, which respectively transforms the variable-length audio sequence into a fixed-length vector and reconstructs the input sequence on the generated vector. After training the encoder-decoder, we feed the audio sequences to the encoder and then take the learnt vectors as the audio sequence representations. Compared with previous methods, the proposed method can not only deal with the problem of arbitrary-lengths of audio streams, but also learn the salient information of the sequence. Extensive evaluation on a large-size acoustic event database is performed, and the empirical results demonstrate that the learnt audio sequence representation yields a significant performance improvement by a large margin compared with other state-of-the-art hand-crafted sequence features for AEC.
Large-scale, Fast and Accurate Shot Boundary Detection through Spatio-temporal Convolutional Neural Networks
Authors: Ahmed Hassanien, Mohamed Elgharib, Ahmed Selim, Sung-Ho Bae, Mohamed Hefeeda, Wojciech Matusik
Date: 2017-05-09 00:00:00
Tasks: Boundary Detection, Camera shot boundary detection, Optical Flow Estimation

Shot boundary detection (SBD) is an important pre-processing step for video
manipulation. Here, each segment of frames is classified as either sharp,
gradual or no transition. Current SBD techniques analyze hand-crafted features
and attempt to optimize both detection accuracy and processing speed. However,
the heavy computations of optical flow prevents this. To achieve this aim, we
present an SBD technique based on spatio-temporal Convolutional Neural Networks
(CNN). Since current datasets are not large enough to train an accurate SBD
CNN, we present a new dataset containing more than 3.5 million frames of sharp
and gradual transitions. The transitions are generated synthetically using
image compositing models. Our dataset contain additional 70,000 frames of
important hard-negative no transitions. We perform the largest evaluation to
date for one SBD algorithm, on real and synthetic data, containing more than
4.85 million frames. In comparison to the state of the art, we outperform
dissolve gradual detection, generate competitive performance for sharp
detections and produce significant improvement in wipes. In addition, we are up
to 11 times faster than the state of the art.
Algebraic Relations and Triangulation of Unlabeled Image Points
Authors: André Wagner
Date: 2017-07-27 00:00:00

In multiview geometry when correspondences among multiple views are unknown
the image points can be understood as being unlabeled. This is a common problem
in computer vision. We give a novel approach to handle such a situation by
regarding unlabeled point configurations as points on the Chow variety
$\text{Sym}_m(\mathbb{P}^2)$. For two unlabeled points we design an algorithm
that solves the triangulation problem with unknown correspondences. Further the
unlabeled multiview variety $\text{Sym}_m(V_A)$ is studied.
Ultra-low-power Wireless Streaming Cameras
Authors: Saman Naderiparizi, Mehrdad Hessar, Vamsi Talla, Shyamnath Gollakota, Joshua R. Smith
Date: 2017-07-27 00:00:00
Tasks: Face Detection

Wireless video streaming has traditionally been considered an extremely
power-hungry operation. Existing approaches optimize the camera and
communication modules individually to minimize their power consumption.
However, the joint redesign and optimization of wireless communication as well
as the camera is what that provides more power saving. We present an
ultra-low-power wireless video streaming camera. To achieve this, we present a
novel "analog" video backscatter technique that feeds analog pixels from the
photo-diodes directly to the backscatter hardware, thereby eliminating power
consuming hardware components such as ADCs and amplifiers. We prototype our
wireless camera using off-the-shelf hardware and show that our design can
stream video at up to 13 FPS and can operate up to a distance of 150 feet from
the access point. Our COTS prototype consumes 2.36mW. Finally, to demonstrate
the potential of our design, we built two proof-of-concept applications: video
streaming for micro-robots and security cameras for face detection.
Linear Convergence of SVRG in Statistical Estimation
Authors: Chao Qu, Yan Li, Huan Xu
Date: 2016-11-07 00:00:00

SVRG and its variants are among the state of art optimization algorithms for
large scale machine learning problems. It is well known that SVRG converges
linearly when the objective function is strongly convex. However this setup can
be restrictive, and does not include several important formulations such as
Lasso, group Lasso, logistic regression, and some non-convex models including
corrected Lasso and SCAD. In this paper, we prove that, for a class of
statistical M-estimators covering examples mentioned above, SVRG solves the
formulation with {\em a linear convergence rate} without strong convexity or
even convexity. Our analysis makes use of {\em restricted strong convexity},
under which we show that SVRG converges linearly to the fundamental statistical
precision of the model, i.e., the difference between true unknown parameter
$\theta^*$ and the optimal solution $\hat{\theta}$ of the model.
Simultaneous Estimation of Non-Gaussian Components and their Correlation Structure
Authors: Hiroaki Sasaki, Michael U. Gutmann, Hayaru Shouno, Aapo Hyvärinen
Date: 2015-06-18 00:00:00

The statistical dependencies which independent component analysis (ICA)
cannot remove often provide rich information beyond the linear independent
components. It would thus be very useful to estimate the dependency structure
from data. While such models have been proposed, they usually concentrated on
higher-order correlations such as energy (square) correlations. Yet, linear
correlations are a most fundamental and informative form of dependency in many
real data sets. Linear correlations are usually completely removed by ICA and
related methods, so they can only be analyzed by developing new methods which
explicitly allow for linearly correlated components. In this paper, we propose
a probabilistic model of linear non-Gaussian components which are allowed to
have both linear and energy correlations. The precision matrix of the linear
components is assumed to be randomly generated by a higher-order process and
explicitly parametrized by a parameter matrix. The estimation of the parameter
matrix is shown to be particularly simple because using score matching, the
objective function is a quadratic form. Using simulations with artificial data,
we demonstrate that the proposed method improves identifiability of
non-Gaussian components by simultaneously learning their correlation structure.
Applications on simulated complex cells with natural image input, as well as
spectrograms of natural audio data show that the method finds new kinds of
dependencies between the components.
Determining Semantic Textual Similarity using Natural Deduction Proofs
Authors: Hitomi Yanaka, Koji Mineshima, Pascual Martinez-Gomez, Daisuke Bekki
Date: 2017-07-27 00:00:00
Proceeding: EMNLP 2017 9
Tasks: Semantic Textual Similarity, Sentence

Determining semantic textual similarity is a core research subject in natural
language processing. Since vector-based models for sentence representation
often use shallow information, capturing accurate semantics is difficult. By
contrast, logical semantic representations capture deeper levels of sentence
semantics, but their symbolic nature does not offer graded notions of textual
similarity. We propose a method for determining semantic textual similarity by
combining shallow features with features extracted from natural deduction
proofs of bidirectional entailment relations between sentence pairs. For the
natural deduction proofs, we use ccg2lambda, a higher-order automatic inference
system, which converts Combinatory Categorial Grammar (CCG) derivation trees
into semantic representations and conducts natural deduction proofs.
Experiments show that our system was able to outperform other logic-based
systems and that features derived from the proofs are effective for learning
textual similarity.
Signal and Noise Statistics Oblivious Sparse Reconstruction using OMP/OLS
Authors: Sreejith Kallummil, Sheetal Kalyani
Date: 2017-07-27 00:00:00
Tasks: compressed sensing

Orthogonal matching pursuit (OMP) and orthogonal least squares (OLS) are
widely used for sparse signal reconstruction in under-determined linear
regression problems. The performance of these compressed sensing (CS)
algorithms depends crucially on the \textit{a priori} knowledge of either the
sparsity of the signal ($k_0$) or noise variance ($\sigma^2$). Both $k_0$ and
$\sigma^2$ are unknown in general and extremely difficult to estimate in under
determined models. This limits the application of OMP and OLS in many practical
situations. In this article, we develop two computationally efficient
frameworks namely TF-IGP and RRT-IGP for using OMP and OLS even when $k_0$ and
$\sigma^2$ are unavailable. Both TF-IGP and RRT-IGP are analytically shown to
accomplish successful sparse recovery under the same set of restricted isometry
conditions on the design matrix required for OMP/OLS with \textit{a priori}
knowledge of $k_0$ and $\sigma^2$. Numerical simulations also indicate a highly
competitive performance of TF-IGP and RRT-IGP in comparison to OMP/OLS with
\textit{a priori} knowledge of $k_0$ and $\sigma^2$.
Smart Mining for Deep Metric Learning
Authors: Ben Harwood, Vijay Kumar B G, Gustavo Carneiro, Ian Reid, Tom Drummond
Date: 2017-04-05 00:00:00
Proceeding: ICCV 2017 10
Tasks: Metric Learning, Triplet

To solve deep metric learning problems and producing feature embeddings,
current methodologies will commonly use a triplet model to minimise the
relative distance between samples from the same class and maximise the relative
distance between samples from different classes. Though successful, the
training convergence of this triplet model can be compromised by the fact that
the vast majority of the training samples will produce gradients with
magnitudes that are close to zero. This issue has motivated the development of
methods that explore the global structure of the embedding and other methods
that explore hard negative/positive mining. The effectiveness of such mining
methods is often associated with intractable computational requirements. In
this paper, we propose a novel deep metric learning method that combines the
triplet model and the global structure of the embedding space. We rely on a
smart mining procedure that produces effective training samples for a low
computational cost. In addition, we propose an adaptive controller that
automatically adjusts the smart mining hyper-parameters and speeds up the
convergence of the training process. We show empirically that our proposed
method allows for fast and more accurate training of triplet ConvNets than
other competing mining methods. Additionally, we show that our method achieves
new state-of-the-art embedding results for CUB-200-2011 and Cars196 datasets.
A Jointly Learned Deep Architecture for Facial Attribute Analysis and Face Detection in the Wild
Authors: Keke He, Yanwei Fu, xiangyang xue
Date: 2017-07-27 00:00:00
Tasks: Attribute, Face Detection

Facial attribute analysis in the real world scenario is very challenging
mainly because of complex face variations. Existing works of analyzing face
attributes are mostly based on the cropped and aligned face images. However,
this result in the capability of attribute prediction heavily relies on the
preprocessing of face detector. To address this problem, we present a novel
jointly learned deep architecture for both facial attribute analysis and face
detection. Our framework can process the natural images in the wild and our
experiments on CelebA and LFWA datasets clearly show that the state-of-the-art
performance is obtained.
Anytime Exact Belief Propagation
Authors: Gabriel Azevedo Ferreira, Quentin Bertrand, Charles Maussion, Rodrigo de Salvo Braz
Date: 2017-07-27 00:00:00
Tasks: Probabilistic Programming

Statistical Relational Models and, more recently, Probabilistic Programming,
have been making strides towards an integration of logic and probabilistic
reasoning. A natural expectation for this project is that a probabilistic logic
reasoning algorithm reduces to a logic reasoning algorithm when provided a
model that only involves 0-1 probabilities, exhibiting all the advantages of
logic reasoning such as short-circuiting, intelligibility, and the ability to
provide proof trees for a query answer. In fact, we can take this further and
require that these characteristics be present even for probabilistic models
with probabilities \emph{near} 0 and 1, with graceful degradation as the model
becomes more uncertain. We also seek inference that has amortized constant time
complexity on a model's size (even if still exponential in the induced width of
a more directly relevant portion of it) so that it can be applied to huge
knowledge bases of which only a relatively small portion is relevant to typical
queries. We believe that, among the probabilistic reasoning algorithms, Belief
Propagation is the most similar to logic reasoning: messages are propagated
among neighboring variables, and the paths of message-passing are similar to
proof trees. However, Belief Propagation is either only applicable to tree
models, or approximate (and without guarantees) for precision and convergence.
In this paper we present work in progress on an Anytime Exact Belief
Propagation algorithm that is very similar to Belief Propagation but is exact
even for graphical models with cycles, while exhibiting soft short-circuiting,
amortized constant time complexity in the model size, and which can provide
probabilistic proof trees.