pwc-archive/papers-with-abstracts huggingface dataset:
Evolving Complexity is Hard
Authors: Alden H. Wright, Cheyenne L. Laue
Date: 2022-09-16 00:00:00

Understanding the evolution of complexity is an important topic in a wide variety of academic fields. Implications of better understanding complexity include increased knowledge of major evolutionary transitions and the properties of living and technological systems. Genotype-phenotype (G-P) maps are fundamental to evolution, and biologically-oriented G-P maps have been shown to have interesting and often-universal properties that enable evolution by following phenotype-preserving walks in genotype space. Here we use a digital logic gate circuit G-P map where genotypes are represented by circuits and phenotypes by the functions that the circuits compute. We compare two mathematical definitions of circuit and phenotype complexity and show how these definitions relate to other well-known properties of evolution such as redundancy, robustness, and evolvability. Using both Cartesian and Linear genetic programming implementations, we demonstrate that the logic gate circuit shares many universal properties of biologically derived G-P maps, with the exception of the relationship between one method of computing phenotypic evolvability, robustness, and complexity. Due to the inherent structure of the G-P map, including the predominance of rare phenotypes, large interconnected neutral networks, and the high mutational load of low robustness, complex phenotypes are difficult to discover using evolution. We suggest, based on this evidence, that evolving complexity is hard and we discuss computational strategies for genetic-programming-based evolution to successfully find genotypes that map to complex phenotypes in the search space.
Pareto Driven Surrogate (ParDen-Sur) Assisted Optimisation of Multi-period Portfolio Backtest Simulations
Authors: Terence L. Van Zyl, Matthew Woolway, Andrew Paskaramoorthy
Date: 2022-09-13 00:00:00
Tasks: Management

Portfolio management is a multi-period multi-objective optimisation problem subject to a wide range of constraints. However, in practice, portfolio management is treated as a single-period problem partly due to the computationally burdensome hyper-parameter search procedure needed to construct a multi-period Pareto frontier. This study presents the \gls{ParDen-Sur} modelling framework to efficiently perform the required hyper-parameter search. \gls{ParDen-Sur} extends previous surrogate frameworks by including a reservoir sampling-based look-ahead mechanism for offspring generation in \glspl{EA} alongside the traditional acceptance sampling scheme. We evaluate this framework against, and in conjunction with, several seminal \gls{MO} \glspl{EA} on two datasets for both the single- and multi-period use cases. Our results show that \gls{ParDen-Sur} can speed up the exploration for optimal hyper-parameters by almost $2\times$ with a statistically significant improvement of the Pareto frontiers, across multiple \glspl{EA}, for both datasets and use cases.
Spiking GATs: Learning Graph Attentions via Spiking Neural Network
Authors: Beibei Wang, Bo Jiang
Date: 2022-09-05 00:00:00
Tasks: Graph Attention

Graph Attention Networks (GATs) have been intensively studied and widely used in graph data learning tasks. Existing GATs generally adopt the self-attention mechanism to conduct graph edge attention learning, requiring expensive computation. It is known that Spiking Neural Networks (SNNs) can perform inexpensive computation by transmitting the input signal data into discrete spike trains and can also return sparse outputs. Inspired by the merits of SNNs, in this work, we propose a novel Graph Spiking Attention Network (GSAT) for graph data representation and learning. In contrast to self-attention mechanism in existing GATs, the proposed GSAT adopts a SNN module architecture which is obvious energy-efficient. Moreover, GSAT can return sparse attention coefficients in natural and thus can perform feature aggregation on the selective neighbors which makes GSAT perform robustly w.r.t graph edge noises. Experimental results on several datasets demonstrate the effectiveness, energy efficiency and robustness of the proposed GSAT model.
The Curse of Unrolling: Rate of Differentiating Through Optimization
Authors: Damien Scieur, Quentin Bertrand, Gauthier Gidel, Fabian Pedregosa
Date: 2022-09-27 00:00:00
Tasks: Dataset Distillation, Hyperparameter Optimization, Meta-Learning, Rolling Shutter Correction

Computing the Jacobian of the solution of an optimization problem is a central problem in machine learning, with applications in hyperparameter optimization, meta-learning, optimization as a layer, and dataset distillation, to name a few. Unrolled differentiation is a popular heuristic that approximates the solution using an iterative solver and differentiates it through the computational path. This work provides a non-asymptotic convergence-rate analysis of this approach on quadratic objectives for gradient descent and the Chebyshev method. We show that to ensure convergence of the Jacobian, we can either 1) choose a large learning rate leading to a fast asymptotic convergence but accept that the algorithm may have an arbitrarily long burn-in phase or 2) choose a smaller learning rate leading to an immediate but slower convergence. We refer to this phenomenon as the curse of unrolling. Finally, we discuss open problems relative to this approach, such as deriving a practical update rule for the optimal unrolling strategy and making novel connections with the field of Sobolev orthogonal polynomials.
Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency
Authors: Wenlong Mou, Martin J. Wainwright, Peter L. Bartlett
Date: 2022-09-26 00:00:00
Tasks: Causal Inference

The problem of estimating a linear functional based on observational data is canonical in both the causal inference and bandit literatures. We analyze a broad class of two-stage procedures that first estimate the treatment effect function, and then use this quantity to estimate the linear functional. We prove non-asymptotic upper bounds on the mean-squared error of such procedures: these bounds reveal that in order to obtain non-asymptotically optimal procedures, the error in estimating the treatment effect should be minimized in a certain weighted $L^2$-norm. We analyze a two-stage procedure based on constrained regression in this weighted norm, and establish its instance-dependent optimality in finite samples via matching non-asymptotic local minimax lower bounds. These results show that the optimal non-asymptotic risk, in addition to depending on the asymptotically efficient variance, depends on the weighted norm distance between the true outcome function and its approximation by the richest function class supported by the sample size.
LitCovid in 2022: an information resource for the COVID-19 literature
Authors: Qingyu Chen, Alexis Allot, Robert Leaman, Chih-Hsuan Wei, Elaheh Aghaarabi, John J. Guerrerio, Lilly Xu, Zhiyong Lu
Date: 2022-09-27 00:00:00
Tasks: Articles

LitCovid (https://www.ncbi.nlm.nih.gov/research/coronavirus/), first launched in February 2020, is a first-of-its-kind literature hub for tracking up-to-date published research on COVID-19. The number of articles in LitCovid has increased from 55,000 to ~300,000 over the past two and half years, with a consistent growth rate of ~10,000 articles per month. In addition to the rapid literature growth, the COVID-19 pandemic has evolved dramatically. For instance, the Omicron variant has now accounted for over 98% of new infections in the U.S. In response to the continuing evolution of the COVID-19 pandemic, this article describes significant updates to LitCovid over the last two years. First, we introduced the Long Covid collection consisting of the articles on COVID-19 survivors experiencing ongoing multisystemic symptoms, including respiratory issues, cardiovascular disease, cognitive impairment, and profound fatigue. Second, we provided new annotations on the latest COVID-19 strains and vaccines mentioned in the literature. Third, we improved several existing features with more accurate machine learning algorithms for annotating topics and classifying articles relevant to COVID-19. LitCovid has been widely used with millions of accesses by users worldwide on various information needs and continues to play a critical role in collecting, curating, and standardizing the latest knowledge on the COVID-19 literature.
From Ranked Lists to Carousels: A Carousel Click Model
Authors: Behnam Rahdari, Branislav Kveton, Peter Brusilovsky
Date: 2022-09-27 00:00:00

Carousel-based recommendation interfaces allow users to explore recommended items in a structured, efficient, and visually-appealing way. This made them a de-facto standard approach to recommending items to end users in many real-life recommenders. In this work, we try to explain the efficiency of carousel recommenders using a \emph{carousel click model}, a generative model of user interaction with carousel-based recommender interfaces. We study this model both analytically and empirically. Our analytical results show that the user can examine more items in the carousel click model than in a single ranked list, due to the structured way of browsing. These results are supported by a series of experiments, where we integrate the carousel click model with a recommender based on matrix factorization. We show that the combined recommender performs well on held-out test data, and leads to higher engagement with recommendations than a traditional single ranked list.
Efficient On-Device Session-Based Recommendation
Authors: Xin Xia, Junliang Yu, Qinyong Wang, Chaoqun Yang, Quoc Viet Hung Nguyen, Hongzhi Yin
Date: 2022-09-27 00:00:00
Tasks: Knowledge Distillation, Model Compression, Recommendation Systems, Session-Based Recommendations

On-device session-based recommendation systems have been achieving increasing attention on account of the low energy/resource consumption and privacy protection while providing promising recommendation performance. To fit the powerful neural session-based recommendation models in resource-constrained mobile devices, tensor-train decomposition and its variants have been widely applied to reduce memory footprint by decomposing the embedding table into smaller tensors, showing great potential in compressing recommendation models. However, these model compression techniques significantly increase the local inference time due to the complex process of generating index lists and a series of tensor multiplications to form item embeddings, and the resultant on-device recommender fails to provide real-time response and recommendation. To improve the online recommendation efficiency, we propose to learn compositional encoding-based compact item representations. Specifically, each item is represented by a compositional code that consists of several codewords, and we learn embedding vectors to represent each codeword instead of each item. Then the composition of the codeword embedding vectors from different embedding matrices (i.e., codebooks) forms the item embedding. Since the size of codebooks can be extremely small, the recommender model is thus able to fit in resource-constrained devices and meanwhile can save the codebooks for fast local inference.Besides, to prevent the loss of model capacity caused by compression, we propose a bidirectional self-supervised knowledge distillation framework. Extensive experimental results on two benchmark datasets demonstrate that compared with existing methods, the proposed on-device recommender not only achieves an 8x inference speedup with a large compression ratio but also shows superior recommendation performance.
Privacy-Preserving Synthetic Data Generation for Recommendation Systems
Authors: Fan Liu, Zhiyong Cheng, Huilin Chen, Yinwei Wei, Liqiang Nie, Mohan Kankanhalli
Date: 2022-09-27 00:00:00
Tasks: Privacy Preserving, Recommendation Systems, Synthetic Data Generation

Recommendation systems make predictions chiefly based on users' historical interaction data (e.g., items previously clicked or purchased). There is a risk of privacy leakage when collecting the users' behavior data for building the recommendation model. However, existing privacy-preserving solutions are designed for tackling the privacy issue only during the model training and results collection phases. The problem of privacy leakage still exists when directly sharing the private user interaction data with organizations or releasing them to the public. To address this problem, in this paper, we present a User Privacy Controllable Synthetic Data Generation model (short for UPC-SDG), which generates synthetic interaction data for users based on their privacy preferences. The generation model aims to provide certain privacy guarantees while maximizing the utility of the generated synthetic data at both data level and item level. Specifically, at the data level, we design a selection module that selects those items that contribute less to a user's preferences from the user's interaction data. At the item level, a synthetic data generation module is proposed to generate a synthetic item corresponding to the selected item based on the user's preferences. Furthermore, we also present a privacy-utility trade-off strategy to balance the privacy and utility of the synthetic data. Extensive experiments and ablation studies have been conducted on three publicly accessible datasets to justify our method, demonstrating its effectiveness in generating synthetic data under users' privacy preferences.
RADio -- Rank-Aware Divergence Metrics to Measure Normative Diversity in News Recommendations
Authors: Sanne Vrijenhoek, Gabriel Bénédict, Mateo Gutierrez Granada, Daan Odijk, Maarten de Rijke
Date: 2022-09-17 00:00:00
Tasks: Diversity, Recommendation Systems

In traditional recommender system literature, diversity is often seen as the opposite of similarity, and typically defined as the distance between identified topics, categories or word models. However, this is not expressive of the social science's interpretation of diversity, which accounts for a news organization's norms and values and which we here refer to as normative diversity. We introduce RADio, a versatile metrics framework to evaluate recommendations according to these normative goals. RADio introduces a rank-aware Jensen Shannon (JS) divergence. This combination accounts for (i) a user's decreasing propensity to observe items further down a list and (ii) full distributional shifts as opposed to point estimates. We evaluate RADio's ability to reflect five normative concepts in news recommendations on the Microsoft News Dataset and six (neural) recommendation algorithms, with the help of our metadata enrichment pipeline. We find that RADio provides insightful estimates that can potentially be used to inform news recommender system design.
Hierarchical Interdisciplinary Topic Detection Model for Research Proposal Classification
Authors: Meng Xiao, Ziyue Qiao, Yanjie Fu, Hao Dong, Yi Du, Pengyang Wang, Hui Xiong, Yuanchun Zhou
Date: 2022-09-16 00:00:00
Tasks: Classification

The peer merit review of research proposals has been the major mechanism for deciding grant awards. However, research proposals have become increasingly interdisciplinary. It has been a longstanding challenge to assign interdisciplinary proposals to appropriate reviewers, so proposals are fairly evaluated. One of the critical steps in reviewer assignment is to generate accurate interdisciplinary topic labels for proposal-reviewer matching. Existing systems mainly collect topic labels manually generated by principal investigators. However, such human-reported labels can be non-accurate, incomplete, labor intensive, and time costly. What role can AI play in developing a fair and precise proposal reviewer assignment system? In this study, we collaborate with the National Science Foundation of China to address the task of automated interdisciplinary topic path detection. For this purpose, we develop a deep Hierarchical Interdisciplinary Research Proposal Classification Network (HIRPCN). Specifically, we first propose a hierarchical transformer to extract the textual semantic information of proposals. We then design an interdisciplinary graph and leverage GNNs for learning representations of each discipline in order to extract interdisciplinary knowledge. After extracting the semantic and interdisciplinary knowledge, we design a level-wise prediction component to fuse the two types of knowledge representations and detect interdisciplinary topic paths for each proposal. We conduct extensive experiments and expert evaluations on three real-world datasets to demonstrate the effectiveness of our proposed model.
The effectiveness of factorization and similarity blending
Authors: Andrea Pinto, Giacomo Camposampiero, Loïc Houmard, Marc Lundwall
Date: 2022-09-16 00:00:00
Tasks: Collaborative Filtering

Collaborative Filtering (CF) is a widely used technique which allows to leverage past users' preferences data to identify behavioural patterns and exploit them to predict custom recommendations. In this work, we illustrate our review of different CF techniques in the context of the Computational Intelligence Lab (CIL) CF project at ETH Z\"urich. After evaluating the performances of the individual models, we show that blending factorization-based and similarity-based approaches can lead to a significant error decrease (-9.4%) on the best-performing stand-alone model. Moreover, we propose a novel stochastic extension of a similarity model, SCSR, which consistently reduce the asymptotic complexity of the original algorithm.
PARSRec: Explainable Personalized Attention-fused Recurrent Sequential Recommendation Using Session Partial Actions
Authors: Ehsan Gholami, Mohammad Motamedi, Ashwin Aravindakshan
Date: 2022-09-16 00:00:00
Tasks: Recommendation Systems, Sequential Recommendation

The emerging meta- and multi-verse landscape is yet another step towards the more prevalent use of already ubiquitous online markets. In such markets, recommender systems play critical roles by offering items of interest to the users, thereby narrowing down a vast search space that comprises hundreds of thousands of products. Recommender systems are usually designed to learn common user behaviors and rely on them for inference. This approach, while effective, is oblivious to subtle idiosyncrasies that differentiate humans from each other. Focusing on this observation, we propose an architecture that relies on common patterns as well as individual behaviors to tailor its recommendations for each person. Simulations under a controlled environment show that our proposed model learns interpretable personalized user behaviors. Our empirical results on Nielsen Consumer Panel dataset indicate that the proposed approach achieves up to 27.9% performance improvement compared to the state-of-the-art.
Inclusive Ethical Design for Recommender Systems
Authors: Susan Leavy
Date: 2022-09-13 00:00:00
Tasks: Recommendation Systems

Recommender systems are becoming increasingly central as mediators of information with the potential to profoundly influence societal opinion. While approaches are being developed to ensure these systems are designed in a responsible way, adolescents in particular, represent a potentially vulnerable user group requiring explicit consideration. This is especially important given the nature of their access and use of recommender systems but also their role as providers of content. This paper proposes core principles for the ethical design of recommender systems and evaluates whether current approaches to ensuring adherence to these principles are sufficiently inclusive of the particular needs and potential vulnerabilities of adolescent users.
Fast online ranking with fairness of exposure
Authors: Nicolas Usunier, Virginie Do, Elvis Dohmatob
Date: 2022-09-13 00:00:00
Tasks: Fairness, global-optimization, Recommendation Systems

As recommender systems become increasingly central for sorting and prioritizing the content available online, they have a growing impact on the opportunities or revenue of their items producers. For instance, they influence which recruiter a resume is recommended to, or to whom and how much a music track, video or news article is being exposed. This calls for recommendation approaches that not only maximize (a proxy of) user satisfaction, but also consider some notion of fairness in the exposure of items or groups of items. Formally, such recommendations are usually obtained by maximizing a concave objective function in the space of randomized rankings. When the total exposure of an item is defined as the sum of its exposure over users, the optimal rankings of every users become coupled, which makes the optimization process challenging. Existing approaches to find these rankings either solve the global optimization problem in a batch setting, i.e., for all users at once, which makes them inapplicable at scale, or are based on heuristics that have weak theoretical guarantees. In this paper, we propose the first efficient online algorithm to optimize concave objective functions in the space of rankings which applies to every concave and smooth objective function, such as the ones found for fairness of exposure. Based on online variants of the Frank-Wolfe algorithm, we show that our algorithm is computationally fast, generating rankings on-the-fly with computation cost dominated by the sort operation, memory efficient, and has strong theoretical guarantees. Compared to baseline policies that only maximize user-side performance, our algorithm allows to incorporate complex fairness of exposure criteria in the recommendations with negligible computational overhead.
Strategyproofness-Exposing Mechanism Descriptions
Authors: Yannai A. Gonczarowski, Ori Heffetz, Clayton Thomas
Date: 2022-09-27 00:00:00

A menu description presents a mechanism to player $i$ in two steps. Step (1) uses the reports of other players to describe $i$'s menu: the set of $i$'s potential outcomes. Step (2) uses $i$'s report to select $i$'s favorite outcome from her menu. Can menu descriptions better expose strategyproofness, without sacrificing simplicity? We propose a new, simple menu description of Deferred Acceptance. We prove that -- in contrast with other common matching mechanisms -- this menu description must differ substantially from the corresponding traditional description. We demonstrate, with a lab experiment on two elementary mechanisms, the promise and challenges of menu descriptions.
Towards Real Time Thermal Simulations for Design Optimization using Graph Neural Networks
Authors: Helios Sanchis-Alepuz, Monika Stipsitz
Date: 2022-09-21 00:00:00
Tasks: Graph Neural Network

This paper presents a method to simulate the thermal behavior of 3D systems using a graph neural network. The method discussed achieves a significant speed-up with respect to a traditional finite-element simulation. The graph neural network is trained on a diverse dataset of 3D CAD designs and the corresponding finite-element simulations, representative of the different geometries, material properties and losses that appear in the design of electronic systems. We present for the transient thermal behavior of a test system. The accuracy of the network result for one-step predictions is remarkable (\SI{0.003}{\%} error). After 400 time steps, the accumulated error reaches \SI{0.78}{\%}. The computing time of each time step is \SI{50}{ms}. Reducing the accumulated error is the current focus of our work. In the future, a tool such as the one we are presenting could provide nearly instantaneous approximations of the thermal behavior of a system that can be used for design optimization.