pwc-archive/papers-with-abstracts huggingface dataset:
Regret-Aware Black-Box Optimization with Natural Gradients, Trust-Regions and Entropy Control
Authors: Maximilian Hüttenrauch, Gerhard Neumann
Date: 2022-05-24 00:00:00
Tasks: Scheduling

Most successful stochastic black-box optimizers, such as CMA-ES, use rankings of the individual samples to obtain a new search distribution. Yet, the use of rankings also introduces several issues such as the underlying optimization objective is often unclear, i.e., we do not optimize the expected fitness. Further, while these algorithms typically produce a high-quality mean estimate of the search distribution, the produced samples can have poor quality as these algorithms are ignorant of the regret. Lastly, noisy fitness function evaluations may result in solutions that are highly sub-optimal on expectation. In contrast, stochastic optimizers that are motivated by policy gradients, such as the Model-based Relative Entropy Stochastic Search (MORE) algorithm, directly optimize the expected fitness function without the use of rankings. MORE can be derived by applying natural policy gradients and compatible function approximation, and is using information theoretic constraints to ensure the stability of the policy update. While MORE does not suffer from the listed limitations, it often cannot achieve state of the art performance in comparison to ranking based methods. We improve MORE by decoupling the update of the mean and covariance of the search distribution allowing for more aggressive updates on the mean while keeping the update on the covariance conservative, an improved entropy scheduling technique based on an evolution path which results in faster convergence and a simplified and more effective model learning approach in comparison to the original paper. We compare our algorithm to state of the art black-box optimization algorithms on standard optimization tasks as well as on episodic RL tasks in robotics where it is also crucial to have small regret. We obtain competitive results on benchmark functions and clearly outperform ranking-based methods in terms of regret on the RL tasks.
Sparse-group boosting -- Unbiased group and variable selection
Authors: Fabian Obster, Christian Heumann
Date: 2022-06-13 00:00:00
Tasks: Variable Selection

In the presence of grouped covariates, we propose a framework for boosting that allows to enforce sparsity within and between groups. By using component-wise and group-wise gradient boosting at the same time with adjusted degrees of freedom, a model with similar properties as the sparse group lasso can be fitted through boosting. We show that within-group and between-group sparsity can be controlled by a mixing parameter and discuss similarities and differences to the mixing parameter in the sparse group lasso. With simulations, gene data as well as agricultural data we show the effectiveness and predictive competitiveness of this estimator. The data and simulations suggest, that in the presence of grouped variables the use of sparse group boosting is associated with less biased variable selection and higher predictability compared to component-wise boosting. Additionally, we propose a way of reducing bias in component-wise boosting through the degrees of freedom.
A non-graphical representation of conditional independence via the neighbourhood lattice
Authors: Arash A. Amini, Bryon Aragam, Qing Zhou
Date: 2022-06-12 00:00:00
Tasks: valid

We introduce and study the neighbourhood lattice decomposition of a distribution, which is a compact, non-graphical representation of conditional independence that is valid in the absence of a faithful graphical representation. The idea is to view the set of neighbourhoods of a variable as a subset lattice, and partition this lattice into convex sublattices, each of which directly encodes a collection of conditional independence relations. We show that this decomposition exists in any compositional graphoid and can be computed efficiently and consistently in high-dimensions. {In particular, this gives a way to encode all of independence relations implied by a distribution that satisfies the composition axiom, which is strictly weaker than the faithfulness assumption that is typically assumed by graphical approaches.} We also discuss various special cases such as graphical models and projection lattices, each of which has intuitive interpretations. Along the way, we see how this problem is closely related to neighbourhood regression, which has been extensively studied in the context of graphical models and structural equations.
Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering
Authors: Peng Wang, Huikang Liu, Anthony Man-Cho So, Laura Balzano
Date: 2022-06-11 00:00:00
Tasks: Clustering

The K-subspaces (KSS) method is a generalization of the K-means method for subspace clustering. In this work, we present local convergence analysis and a recovery guarantee for KSS, assuming data are generated by the semi-random union of subspaces model, where $N$ points are randomly sampled from $K \ge 2$ overlapping subspaces. We show that if the initial assignment of the KSS method lies within a neighborhood of a true clustering, it converges at a superlinear rate and finds the correct clustering within $\Theta(\log\log N)$ iterations with high probability. Moreover, we propose a thresholding inner-product based spectral method for initialization and prove that it produces a point in this neighborhood. We also present numerical results of the studied method to support our theoretical developments.
TransRec: Learning Transferable Recommendation from Mixture-of-Modality Feedback
Authors: Jie Wang, Fajie Yuan, Mingyue Cheng, Joemon M. Jose, Chenyun Yu, Beibei Kong, Xiangnan He, Zhijin Wang, Bo Hu, Zang Li
Date: 2022-06-13 00:00:00
Tasks: Recommendation Systems, Transfer Learning

Learning large-scale pre-trained models on broad-ranging data and then transfer to a wide range of target tasks has become the de facto paradigm in many machine learning (ML) communities. Such big models are not only strong performers in practice but also offer a promising way to break out of the task-specific modeling restrictions, thereby enabling task-agnostic and unified ML systems. However, such a popular paradigm is mainly unexplored by the recommender systems (RS) community. A critical issue is that standard recommendation models are primarily built on categorical identity features. That is, the users and the interacted items are represented by their unique IDs, which are generally not shareable across different systems or platforms. To pursue the transferable recommendations, we propose studying pre-trained RS models in a novel scenario where a user's interaction feedback involves a mixture-of-modality (MoM) items, e.g., text and images. We then present TransRec, a very simple modification made on the popular ID-based RS framework. TransRec learns directly from the raw features of the MoM items in an end-to-end training manner and thus enables effective transfer learning under various scenarios without relying on overlapped users or items. We empirically study the transferring ability of TransRec across four different real-world recommendation settings. Besides, we look at its effects by scaling source and target data size. Our results suggest that learning neural recommendation models from MoM feedback provides a promising way to realize universal RS.
Deconfounding Duration Bias in Watch-time Prediction for Video Recommendation
Authors: Ruohan Zhan, Changhua Pei, Qiang Su, Jianfeng Wen, Xueliang Wang, Guanyu Mu, Dong Zheng, Peng Jiang
Date: 2022-06-13 00:00:00
Tasks: Prediction

Watch-time prediction remains to be a key factor in reinforcing user engagement via video recommendations. It has become increasingly important given the ever-growing popularity of online videos. However, prediction of watch time not only depends on the match between the user and the video but is often mislead by the duration of the video itself. With the goal of improving watch time, recommendation is always biased towards videos with long duration. Models trained on this imbalanced data face the risk of bias amplification, which misguides platforms to over-recommend videos with long duration but overlook the underlying user interests. This paper presents the first work to study duration bias in watch-time prediction for video recommendation. We employ a causal graph illuminating that duration is a confounding factor that concurrently affects video exposure and watch-time prediction -- the first effect on video causes the bias issue and should be eliminated, while the second effect on watch time originates from video intrinsic characteristics and should be preserved. To remove the undesired bias but leverage the natural effect, we propose a Duration Deconfounded Quantile-based (D2Q) watch-time prediction framework, which allows for scalability to perform on industry production systems. Through extensive offline evaluation and live experiments, we showcase the effectiveness of this duration-deconfounding framework by significantly outperforming the state-of-the-art baselines. We have fully launched our approach on Kuaishou App, which has substantially improved real-time video consumption due to more accurate watch-time predictions.
Scalable Exploration for Neural Online Learning to Rank with Perturbed Feedback
Authors: Yiling Jia, Hongning Wang
Date: 2022-06-13 00:00:00
Tasks: Computational Efficiency, Efficient Exploration, Learning-To-Rank, Retrieval

Deep neural networks (DNNs) demonstrate significant advantages in improving ranking performance in retrieval tasks. Driven by the recent technical developments in optimization and generalization of DNNs, learning a neural ranking model online from its interactions with users becomes possible. However, the required exploration for model learning has to be performed in the entire neural network parameter space, which is prohibitively expensive and limits the application of such online solutions in practice. In this work, we propose an efficient exploration strategy for online interactive neural ranker learning based on the idea of bootstrapping. Our solution employs an ensemble of ranking models trained with perturbed user click feedback. The proposed method eliminates explicit confidence set construction and the associated computational overhead, which enables the online neural rankers' training to be efficiently executed in practice with theoretical guarantees. Extensive comparisons with an array of state-of-the-art OL2R algorithms on two public learning to rank benchmark datasets demonstrate the effectiveness and computational efficiency of our proposed neural OL2R solution.
Pliable Private Information Retrieval
Authors: Sarah A. Obead, Jörg Kliewer
Date: 2022-06-12 00:00:00
Tasks: Information Retrieval, Retrieval

We formulate a new variant of the private information retrieval (PIR) problem where the user is pliable, i.e., interested in any message from a desired subset of the available dataset, denoted as pliable private information retrieval (PPIR). We consider a setup where a dataset consisting of $f$ messages is replicated in $n$ noncolluding databases and classified into $\Gamma$ classes. For this setup, the user wishes to retrieve any $\lambda\geq 1$ messages from multiple desired classes, i.e., $\eta\geq 1$, while revealing no information about the identity of the desired classes to the databases. We term this problem multi-message PPIR (M-PPIR) and introduce the single-message PPIR (PPIR) problem as an elementary special case of M-PPIR. We first derive converse bounds on the M-PPIR rate, which is defined as the ratio of the desired amount of information and the total amount of downloaded information, followed by the corresponding achievable schemes. As a result, we show that the PPIR capacity, i.e., the maximum achievable PPIR rate, for $n$ noncolluding databases matches the capacity of PIR with $n$ databases and $\Gamma$ messages. Thus, enabling flexibility, i.e., pliability, where privacy is only guaranteed for classes, but not for messages as in classical PIR, allows to trade-off privacy versus download rate. A similar insight is shown to hold for the general case of M-PPIR.
A Matrix Decomposition Model Based on Feature Factors in Movie Recommendation System
Authors: Dan Liu, Hou-Biao Li
Date: 2022-06-12 00:00:00
Tasks: Attribute, Collaborative Filtering, Movie Recommendation, Recommendation Systems

Currently, matrix decomposition is one of the most widely used collaborative filtering algorithms by using factor decomposition to effectively deal with large-scale rating matrix. It mainly uses the interaction records between users and items to predict ratings. Based on the characteristic attributes of items and users, this paper proposes a new UISVD++ model that fuses the type attributes of movies and the age attributes of users into SVD++ framework. By projecting the age attribute into the user's implicit space and the type attribute into the item's implicit space, the model enriches the side information of the users and items. At last, we conduct comparative experiments on two public data sets, Movielens-100K and Movielens-1M. Experiment results express that the prediction accuracy of this model is better than other baselines in the task of predicting scores. In addition, these results also show that UISVD++ can effectively alleviate the cold start situation.
Incremental Information Gain Mining Of Temporal Relational Streams
Authors: Ken Pu, Limin Ma
Date: 2022-06-11 00:00:00

This paper studies the problem of mining for data values with high information gain in relational tables. High information gain can help data analysts and secondary data mining algorithms gain insights into strong statistical dependencies and causality relationship between key metrics. In this paper, we will study the problem of high information gain identification for scenarios involving temporal relations where new records are added continuously to the relations. We show that information gain can be efficiently maintained in an incremental fashion, making it possible to monitor continuously high information gain values.
Learning to Rank Rationales for Explainable Recommendation
Authors: Zhichao Xu, Yi Han, Tao Yang, Anh Tran, Qingyao Ai
Date: 2022-06-10 00:00:00
Tasks: Explainable Recommendation, Learning-To-Rank, Open-Ended Question Answering, Persuasiveness, Recommendation Systems

State-of-the-art recommender system (RS) mostly rely on complex deep neural network (DNN) model structure, which makes it difficult to provide explanations along with RS decisions. Previous researchers have proved that providing explanations along with recommended items can help users make informed decisions and improve their trust towards the uninterpretable blackbox system. In model-agnostic explainable recommendation, system designers deploy a separate explanation model to take as input from the decision model, and generate explanations to meet the goal of persuasiveness. In this work, we explore the task of ranking textual rationales (supporting evidences) for model-agnostic explainable recommendation. Most of existing rationales ranking algorithms only utilize the rationale IDs and interaction matrices to build latent factor representations; and the semantic information within the textual rationales are not learned effectively. We argue that such design is suboptimal as the important semantic information within the textual rationales may be used to better profile user preferences and item features. Seeing this gap, we propose a model named Semantic-Enhanced Bayesian Personalized Explanation Ranking (SE-BPER) to effectively combine the interaction information and semantic information. SE-BPER first initializes the latent factor representations with contextualized embeddings generated by transformer model, then optimizes them with the interaction data. Extensive experiments show that such methodology improves the rationales ranking performance while simplifying the model training process (fewer hyperparameters and faster convergence). We conclude that the optimal way to combine semantic and interaction information remains an open question in the task of rationales ranking.
A Constructive GAN-based Approach to Exact Estimate Treatment Effect without Matching
Authors: Boyang You, Kerry Papps
Date: 2022-06-13 00:00:00
Tasks: counterfactual, Counterfactual Inference, Generative Adversarial Network, Selection bias

Matching has become the mainstream in counterfactual inference, with which selection bias between sample groups can be significantly eliminated. However in practice, when estimating average treatment effect on the treated (ATT) via matching, no matter which method, the trade-off between estimation accuracy and information loss constantly exist. Attempting to completely replace the matching process, this paper proposes the GAN-ATT estimator that integrates generative adversarial network (GAN) into counterfactual inference framework. Through GAN machine learning, the probability density functions (PDFs) of samples in both treatment group and control group can be approximated. By differentiating conditional PDFs of the two groups with identical input condition, the conditional average treatment effect (CATE) can be estimated, and the ensemble average of corresponding CATEs over all treatment group samples is the estimate of ATT. Utilizing GAN-based infinite sample augmentations, problems in the case of insufficient samples or lack of common support domains can be easily solved. Theoretically, when GAN could perfectly learn the PDFs, our estimators can provide exact estimate of ATT. To check the performance of the GAN-ATT estimator, three sets of data are used for ATT estimations: Two toy data sets with 1/2 dimensional covariate inputs and constant/covariate-dependent treatment effect are tested. The estimates of GAN-ATT are proved close to the ground truth and are better than traditional matching approaches; A real firm-level data set with high-dimensional input is tested and the applicability towards real data sets is evaluated by comparing matching approaches. Through the evidences obtained from the three tests, we believe that the GAN-ATT estimator has significant advantages over traditional matching methods in estimating ATT.
MLPD: Multi-Label Pedestrian Detector in Multispectral Domain
Authors: Jiwon Kim, Hyeongjun Kim, Taejoo Kim, Namil Kim, Yukyung Choi
Date: 2021-07-26 00:00:00
Proceeding: IEEE ROBOTICS AND AUTOMATION LETTERS 2021 7
Tasks: Multi-Label Learning, Multispectral Object Detection, Pedestrian Detection

Multispectral pedestrian detection has been actively studied as a promising multi-modality solution to handle illumination and weather changes. Most multi-modality approaches carry the assumption that all inputs are fully-overlapped. However, these kinds of data pairs are not common in practical applications due to the complexity of the existing sensor configuration. In this letter, we tackle multispectral pedestrian detection, where all input data are not paired. To this end, we propose a novel single-stage detection framework that leverages multi-label learning to learn input state-aware features by assigning a separate label according to the given state of the input image pair. We also present a novel augmentation strategy by applying geometric transformations to synthesize the unpaired multispectral images. In extensive experiments, we demonstrate the efficacy of the proposed method under various real-world conditions, such as fully-overlapped images and partially-overlapped images, in stereo-vision. Code and a demonstration video are available at https://github.com/sejong-rcv/MLPD-Multi-Label-Pedestrian-Detection.
D2Conv3D: Dynamic Dilated Convolutions for Object Segmentation in Videos
Authors: Christian Schmidt, Ali Athar, Sabarinath Mahadevan, Bastian Leibe
Date: 2021-11-15 00:00:00
Proceeding: WACV 2021 11
Tasks: Multi-Object Tracking and Segmentation, Segmentation, Semantic Segmentation, Unsupervised Video Object Segmentation, Video Instance Segmentation, Video Object Segmentation, Video Segmentation, Video Semantic Segmentation

Despite receiving significant attention from the research community, the task of segmenting and tracking objects in monocular videos still has much room for improvement. Existing works have simultaneously justified the efficacy of dilated and deformable convolutions for various image-level segmentation tasks. This gives reason to believe that 3D extensions of such convolutions should also yield performance improvements for video-level segmentation tasks. However, this aspect has not yet been explored thoroughly in existing literature. In this paper, we propose Dynamic Dilated Convolutions (D2Conv3D): a novel type of convolution which draws inspiration from dilated and deformable convolutions and extends them to the 3D (spatio-temporal) domain. We experimentally show that D2Conv3D can be used to improve the performance of multiple 3D CNN architectures across multiple video segmentation related benchmarks by simply employing D2Conv3D as a drop-in replacement for standard convolutions. We further show that D2Conv3D out-performs trivial extensions of existing dilated and deformable convolutions to 3D. Lastly, we set a new state-of-the-art on the DAVIS 2016 Unsupervised Video Object Segmentation benchmark. Code is made publicly available at https://github.com/Schmiddo/d2conv3d.
Algorithms for determining transposons in gene sequences
Authors: Yue Wang
Date: 2015-06-08 00:00:00

Some genes can change their relative locations in a genome. Thus for different individuals of the same species, the orders of genes might be different. Such jumping genes are called transposons. A practical problem is to determine transposons in given gene sequences. Through an intuitive rule, we transform the biological problem of determining transposons into a rigorous mathematical problem of determining the longest common subsequence. Depending on whether the gene sequence is linear (each sequence has a fixed head and tail) or circular (we can choose any gene as the head, and the previous one is the tail), and whether genes have multiple copies, we classify the problem of determining transposons into four scenarios: (1) linear sequences without duplicated genes; (2) circular sequences without duplicated genes; (3) linear sequences with duplicated genes; (4) circular sequences with duplicated genes. With the help of graph theory, we design fast algorithms for different scenarios. We also derive some results that might be of theoretical interests in combinatorics.