pwc-archive/papers-with-abstracts huggingface dataset:
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
Authors: Samuel B. Hopkins, Gautam Kamath, Mahbod Majid
Date: 2021-11-25 00:00:00

We give the first polynomial-time algorithm to estimate the mean of a $d$-variate probability distribution with bounded covariance from $\tilde{O}(d)$ independent samples subject to pure differential privacy. Prior algorithms for this problem either incur exponential running time, require $\Omega(d^{1.5})$ samples, or satisfy only the weaker concentrated or approximate differential privacy conditions. In particular, all prior polynomial-time algorithms require $d^{1+\Omega(1)}$ samples to guarantee small privacy loss with "cryptographically" high probability, $1-2^{-d^{\Omega(1)}}$, while our algorithm retains $\tilde{O}(d)$ sample complexity even in this stringent setting. Our main technique is a new approach to use the powerful Sum of Squares method (SoS) to design differentially private algorithms. SoS proofs to algorithms is a key theme in numerous recent works in high-dimensional algorithmic statistics -- estimators which apparently require exponential running time but whose analysis can be captured by low-degree Sum of Squares proofs can be automatically turned into polynomial-time algorithms with the same provable guarantees. We demonstrate a similar proofs to private algorithms phenomenon: instances of the workhorse exponential mechanism which apparently require exponential time but which can be analyzed with low-degree SoS proofs can be automatically turned into polynomial-time differentially private algorithms. We prove a meta-theorem capturing this phenomenon, which we expect to be of broad use in private algorithm design. Our techniques also draw new connections between differentially private and robust statistics in high dimensions. In particular, viewed through our proofs-to-private-algorithms lens, several well-studied SoS proofs from recent works in algorithmic robust statistics directly yield key components of our differentially private mean estimation algorithm.
An Optimal Algorithm for Finding Champions in Tournament Graphs
Authors: Lorenzo Beretta, Franco Maria Nardini, Roberto Trani, Rossano Venturini
Date: 2021-11-26 00:00:00
Tasks: Conversational Search, Information Retrieval, Machine Translation, Question Answering, Recommendation Systems, Retrieval

A tournament graph is a complete directed graph, which can be used to model a round-robin tournament between $n$ players. In this paper, we address the problem of finding a champion of the tournament, also known as Copeland winner, which is a player that wins the highest number of matches. In detail, we aim to investigate algorithms that find the champion by playing a low number of matches. Solving this problem allows us to speed up several Information Retrieval and Recommender System applications, including question answering, conversational search, etc. Indeed, these applications often search for the champion inducing a round-robin tournament among the players by employing a machine learning model to estimate who wins each pairwise comparison. Our contribution, thus, allows finding the champion by performing a low number of model inferences. We prove that any deterministic or randomized algorithm finding a champion with constant success probability requires $\Omega(\ell n)$ comparisons, where $\ell$ is the number of matches lost by the champion. We then present an asymptotically-optimal deterministic algorithm matching this lower bound without knowing $\ell$, and we extend our analysis to three variants of the problem. Lastly, we conduct a comprehensive experimental assessment of the proposed algorithms on a question answering task on public data. Results show that our proposed algorithms speed up the retrieval of the champion up to $13\times$ with respect to the state-of-the-art algorithm that perform the full tournament.
Job Recommender Systems: A Review
Authors: Corné de Ruijt, Sandjai Bhulai
Date: 2021-11-26 00:00:00
Tasks: Fairness, Recommendation Systems

This paper provides a review of the job recommender system (JRS) literature published in the past decade (2011-2021). Compared to previous literature reviews, we put more emphasis on contributions that incorporate the temporal and reciprocal nature of job recommendations. Previous studies on JRS suggest that taking such views into account in the design of the JRS can lead to improved model performance. Also, it may lead to a more uniform distribution of candidates over a set of similar jobs. We also consider the literature from the perspective of algorithm fairness. Here we find that this is rarely discussed in the literature, and if it is discussed, many authors wrongly assume that removing the discriminatory feature would be sufficient. With respect to the type of models used in JRS, authors frequently label their method as `hybrid'. Unfortunately, they thereby obscure what these methods entail. Using existing recommender taxonomies, we split this large class of hybrids into subcategories that are easier to analyse. We further find that data availability, and in particular the availability of click data, has a large impact on the choice of method and validation. Last, although the generalizability of JRS across different datasets is infrequently considered, results suggest that error scores may vary across these datasets.
Emotion Embedding Spaces for Matching Music to Stories
Authors: Minz Won, Justin Salamon, Nicholas J. Bryan, Gautham J. Mysore, Xavier Serra
Date: 2021-11-26 00:00:00
Tasks: Cross-Modal Retrieval, Metric Learning, Retrieval

Content creators often use music to enhance their stories, as it can be a powerful tool to convey emotion. In this paper, our goal is to help creators find music to match the emotion of their story. We focus on text-based stories that can be auralized (e.g., books), use multiple sentences as input queries, and automatically retrieve matching music. We formalize this task as a cross-modal text-to-music retrieval problem. Both the music and text domains have existing datasets with emotion labels, but mismatched emotion vocabularies prevent us from using mood or emotion annotations directly for matching. To address this challenge, we propose and investigate several emotion embedding spaces, both manually defined (e.g., valence/arousal) and data-driven (e.g., Word2Vec and metric learning) to bridge this gap. Our experiments show that by leveraging these embedding spaces, we are able to successfully bridge the gap between modalities to facilitate cross modal retrieval. We show that our method can leverage the well established valence-arousal space, but that it can also achieve our goal via data-driven embedding spaces. By leveraging data-driven embeddings, our approach has the potential of being generalized to other retrieval tasks that require broader or completely different vocabularies.
Streamlining Evaluation with ir-measures
Authors: Sean MacAvaney, Craig Macdonald, Iadh Ounis
Date: 2021-11-26 00:00:00
Tasks: Information Retrieval, Retrieval

We present ir-measures, a new tool that makes it convenient to calculate a diverse set of evaluation measures used in information retrieval. Rather than implementing its own measure calculations, ir-measures provides a common interface to a handful of evaluation tools. The necessary tools are automatically invoked (potentially multiple times) to calculate all the desired metrics, simplifying the evaluation process for the user. The tool also makes it easier for researchers to use recently-proposed measures (such as those from the C/W/L framework) alongside traditional measures, potentially encouraging their adoption.
Evaluating the Robustness of Retrieval Pipelines with Query Variation Generators
Authors: Gustavo Penha, Arthur Câmara, Claudia Hauff
Date: 2021-11-25 00:00:00
Tasks: Information Retrieval, Language Modelling, Retrieval

Heavily pre-trained transformers for language modelling, such as BERT, have shown to be remarkably effective for Information Retrieval (IR) tasks, typically applied to re-rank the results of a first-stage retrieval model. IR benchmarks evaluate the effectiveness of retrieval pipelines based on the premise that a single query is used to instantiate the underlying information need. However, previous research has shown that (I) queries generated by users for a fixed information need are extremely variable and, in particular, (II) neural models are brittle and often make mistakes when tested with modified inputs. Motivated by those observations we aim to answer the following question: how robust are retrieval pipelines with respect to different variations in queries that do not change the queries' semantics? In order to obtain queries that are representative of users' querying variability, we first created a taxonomy based on the manual annotation of transformations occurring in a dataset (UQV100) of user-created query variations. For each syntax-changing category of our taxonomy, we employed different automatic methods that when applied to a query generate a query variation. Our experimental results across two datasets for two IR tasks reveal that retrieval pipelines are not robust to these query variations, with effectiveness drops of $\approx20\%$ on average. The code and datasets are available at https://github.com/Guzpenha/query_variation_generators.
ProLiVis: Protein-Protein Interaction Literature Visualization System
Authors: Melih Sozdinler
Date: 2021-11-24 00:00:00

We provide a visualization model that targets the visualization of Protein-Protein Interactions(PPI) and combines it with a super view based on publications and methods to extract interactions. Although there are several existing tools, our model considers the existing literature and is capable to demonstrate all interactions for the selected organisms. In our model, we propose a three-level visualization concept for the PPI networks with the current state-of-the-art studies based on several organisms. And, we abstract of overall network based on two perspectives; "experimental method types of each interaction" and "ownership with the publication". We claim that it is more efficient to work on our proposed layout rather than parsing text files or databases. For that way, we plan to support the existing visuals with complementary outsourced information from the existing knowledge base.
On the quartet distance given partial information
Authors: Sagi Snir, Osnat Weissberg, Raphael Yuster
Date: 2021-11-25 00:00:00

Let $T$ be an arbitrary phylogenetic tree with $n$ leaves. It is well-known that the average quartet distance between two assignments of taxa to the leaves of $T$ is $\frac 23 \binom{n}{4}$. However, a longstanding conjecture of Bandelt and Dress asserts that $(\frac 23 +o(1))\binom{n}{4}$ is also the {\em maximum} quartet distance between two assignments. While Alon, Naves, and Sudakov have shown this indeed holds for caterpillar trees, the general case of the conjecture is still unresolved. A natural extension is when partial information is given: the two assignments are known to coincide on a given subset of taxa. The partial information setting is biologically relevant as the location of some taxa (species) in the phylogenetic tree may be known, and for other taxa it might not be known. What can we then say about the average and maximum quartet distance in this more general setting? Surprisingly, even determining the {\em average} quartet distance becomes a nontrivial task in the partial information setting and determining the maximum quartet distance is even more challenging, as these turn out to be dependent of the structure of $T$. In this paper we prove nontrivial asymptotic bounds that are sometimes tight for the average quartet distance in the partial information setting. We also show that the Bandelt and Dress conjecture does not generally hold under the partial information setting. Specifically, we prove that there are cases where the average and maximum quartet distance substantially differ.
Hidden Markov Modeling over Graphs
Authors: Mert Kayaalp, Virginia Bordignon, Stefan Vlaski, Ali H. Sayed
Date: 2021-11-26 00:00:00
Tasks: State Estimation

This work proposes a multi-agent filtering algorithm over graphs for finite-state hidden Markov models (HMMs), which can be used for sequential state estimation or for tracking opinion formation over dynamic social networks. We show that the difference from the optimal centralized Bayesian solution is asymptotically bounded for geometrically ergodic transition models. Experiments illustrate the theoretical findings and in particular, demonstrate the superior performance of the proposed algorithm compared to a state-of-the-art social learning algorithm.
Engineering and Implementation of SimAEN
Authors: Gwendolyn Gettliffe, Adam Norige, Ted Londner, Jonathan Saunders, Dieter Schuldt, William Streilein
Date: 2021-11-24 00:00:00
Tasks: Sensitivity

This paper presents SimAEN, an agent-based simulation whose purpose is to assist public health in understanding and controlling AEN. SimAEN models a population of interacting individuals, or 'agents', in which COVID-19 is spreading. These individuals interact with a public health system that includes Automated Exposure Notifiation (AEN) and Manual Contact Tracing (MCT). These interactions influence when individuals enter and leave quarantine, affecting the spread of the simulated disease. Over 70 user-configurable parameters influence the outcome of SimAEN's simulations. These parameters allow the user to tailor SimAEN to a specific public health jurisdiction and to test the effects of various interventions, including different sensitivity settings of AEN.
Model Reduction of Linear Dynamical Systems via Balancing for Bayesian Inference
Authors: Elizabeth Qian, Jemima M. Tabeart, Christopher Beattie, Serkan Gugercin, Jiahua Jiang, Peter R. Kramer, Akil Narayan
Date: 2021-11-25 00:00:00
Tasks: Bayesian Inference, Dimensionality Reduction

We consider the Bayesian approach to the linear Gaussian inference problem of inferring the initial condition of a linear dynamical system from noisy output measurements taken after the initial time. In practical applications, the large dimension of the dynamical system state poses a computational obstacle to computing the exact posterior distribution. Model reduction offers a variety of computational tools that seek to reduce this computational burden. In particular, balanced truncation is a system-theoretic approach to model reduction which obtains an efficient reduced-dimension dynamical system by projecting the system operators onto state directions which trade off the reachability and observability of state directions as expressed through the associated Gramians. We introduce Gramian definitions relevant to the inference setting and propose a balanced truncation approach based on these inference Gramians that yield a reduced dynamical system that can be used to cheaply approximate the posterior mean and covariance. Our definitions exploit natural connections between (i) the reachability Gramian and the prior covariance and (ii) the observability Gramian and the Fisher information. The resulting reduced model then inherits stability properties and error bounds from system theoretic considerations, and in some settings yields an optimal posterior covariance approximation. Numerical demonstrations on two benchmark problems in model reduction show that our method can yield near-optimal posterior covariance approximations with order-of-magnitude state dimension reduction.
Teaching Undergraduate Students to Think Like Real-World Systems Engineers: A Technology-Based Hybrid Learning Approach
Authors: Rami Ghannam, Cecilia Chan
Date: 2021-11-26 00:00:00
Tasks: Decision Making

A hybrid teaching approach that relied on combining Project Based Learning with Team Based Learning was trialled in an engineering module during the past five years. Our motivation was to expose students to real-world authentic engineering problems and to steer them away from the classical 'banking' approach, with a view to developing their systems engineering skills via deeper and more collaborative learning. Our third year module was called Team Design and Project Skills and was concerned with 320 students dividing themselves in teams to develop a smart electronic system. We reveal module design details and discuss the effectiveness of our teaching approach via analysis of student grades during the past five years, as well as data from surveys that were completed by 68 students. 64% of surveyed students agreed that the module helped broaden their perspective in electronic systems design. Moreover, 84% recognised that this module was a valuable component in their degree programme. Adopting this approach in an engineering curriculum enabled students to integrate knowledge in areas that included control systems, image processing, embedded systems, sensors, as well as team working, decision making, trouble shooting and project planning.
Network regression and supervised centrality estimation
Authors: Junhui Cai, Dan Yang, Ran Chen, Wu Zhu, Haipeng Shen, Linda Zhao
Date: 2021-11-25 00:00:00
Tasks: regression, valid

The centrality in a network is often used to measure nodes' importance and model network effects on a certain outcome. Empirical studies widely adopt a two-stage procedure, which first estimates the centrality from the observed noisy network and then infers the network effect from the estimated centrality, even though it lacks theoretical understanding. We propose a unified modeling framework to study the properties of centrality estimation and inference and the subsequent network regression analysis with noisy network observations. Furthermore, we propose a supervised centrality estimation methodology, which aims to simultaneously estimate both centrality and network effect. We showcase the advantages of our method compared with the two-stage method both theoretically and numerically via extensive simulations and a case study in predicting currency risk premiums from the global trade network.
On a Stochastic Fundamental Lemma and Its Use for Data-Driven Optimal Control
Authors: Guanru Pan, Ruchuan Ou, Timm Faulwasser
Date: 2021-11-26 00:00:00
Tasks: Data Driven Optimal Control, LEMMA

Data-driven control based on the fundamental lemma by Willems et al. is frequently considered for deterministic LTI systems subject to measurement noise. However, besides measurement noise, stochastic disturbances might also directly affect the dynamics. In this paper, we leverage Polynomial Chaos Expansions (PCE) to extend the deterministic fundamental lemma towards stochastic systems. This extension allows to predict future statistical distributions of the inputs and outputs for stochastic LTI systems in data-driven fashion, i.e., based on the knowledge of previously recorded input-output-disturbance data and of the disturbance distribution we perform data-driven uncertainty propagation. Finally, we analyze data-driven stochastic optimal control problems and we propose a conceptual framework for data-driven stochastic predictive control. Numerical examples illustrate the efficacy of the proposed concepts.
Intermittent Sampling in Repetitive Control: Exploiting Time-Varying Measurements
Authors: Johan Kon, Nard Strijbosch, Sjirk Koekebakker, Tom Oomen
Date: 2021-11-25 00:00:00

The performance increase up to the sensor resolution in repetitive control (RC) invalidates the standard assumption in RC that data is available at equidistant time instances, e.g., in systems with package loss or when exploiting timestamped data from optical encoders. The aim of this paper is to develop an intermittent sampling RC framework for non-equidistant measurements. Sufficient stability conditions are derived that can be verified using non-parametric frequency response function data. This results in a frequency domain design procedure to explicitly address uncertainty. The RC framework is validated on an industrial printbelt setup for which exact non-equidistant measurement data is available.
Hidden Order of Boolean Networks
Authors: Xiao Zhang, Zhengping Ji, Daizhan Cheng
Date: 2021-11-25 00:00:00

It is a common belief that the order of a Boolean network is mainly determined by its attractors, including fixed points and cycles. Using semi-tensor product (STP) of matrices and the algebraic state-space representation (ASSR) of Boolean networks, this paper reveals that in addition to this explicit order, there is certain implicit or hidden order, which is determined by the fixed points and limit cycles of their dual networks. The structure and certain properties of dual networks are investigated. Instead of a trajectory, which describes the evolution of a state, hidden order provides a global picture to describe the evolution of the overall network. It is our conjecture that the order of networks is mainly determined by the dual attractors via their corresponding hidden orders. The previously obtained results about Boolean networks are further extended to the k-valued case.
Optimal Energy Scheduling and Sensitivity Analysis for Integrated Power-Water-Heat Systems
Authors: Sidun Fang, Chenxu Wang, Yashen Lin, Changhong Zhao
Date: 2021-02-01 00:00:00
Tasks: Scheduling, Sensitivity

The conventionally independent power, water, and heating networks are becoming more tightly connected, which motivates their joint optimal energy scheduling to improve the overall efficiency of an integrated energy system. However, such a joint optimization is known as a challenging problem with complex network constraints and couplings of electric, hydraulic, and thermal models that are nonlinear and nonconvex. We formulate an optimal power-water-heat flow (OPWHF) problem and develop a computationally efficient heuristic to solve it. The proposed heuristic decomposes OPWHF into subproblems, which are iteratively solved via convex relaxation and convex-concave procedure. Simulation results validate that the proposed framework can improve operational flexibility and social welfare of the integrated system, wherein the water and heating networks respond as virtual energy storage to time-varying energy prices and solar photovoltaic generation. Moreover, we perform sensitivity analysis to compare two modes of heating network control: by flow rate and by temperature. Our results reveal that the latter is more effective for heating networks with a wider space of pipeline parameters.
A Preliminary Study on the Role of Energy Storage and Load Rationing in Mitigating the Impact of the 2021 Texas Power Outage
Authors: Ali Menati, Le Xie
Date: 2021-11-25 00:00:00

In February 2021, an unprecedented winter storm swept across the U.S., severely affecting the Texas power grid, leading to more than 4.5 million customers' electricity service interruption. This paper assesses the load shedding experienced by customers under realistic scenarios in the actual power grid. It also conducts a preliminary study on using energy storage and load rationing to mitigate rotating blackout's adverse impact on the grid. It is estimated that utility-scale battery storage systems with a total installed capacity of 920 GWh would be required to fully offset the load shedding during the Texas power outage if energy storage were the only technical option. Our simulation result suggests that implementing 20 percent load rationing on the system could potentially reduce this estimated energy storage capacity by 85 percent. This estimate is obtained using the predicted capacity and demand profile from February 15 to February 18, 2021. Recognizing the fact that it would be very challenging to practically deploy energy storage of this size, approaches to provide more granular demand reduction are studied as a means of leveraging the energy storage to maximize the survivability of consumers. Preliminary case study suggests the potential of combining load rationing and proper sizing of energy storage would potentially provide much reliability improvement for the grid under such extreme weather conditions.