OpenRaiser/Intern-Atlas huggingface dataset:
Tight sensitivity bounds for smaller coresets
Authors: Alaa Maalouf, Adiel Statman, Dan Feldman
Venue: Conference KDD 2020
Year: 2020

An ε-coreset to the dimensionality reduction problem for a (possibly very large) matrix A ∈ Rn x d is a small scaled subset of its n rows that approximates their sum of squared distances to every affine k-dimensional subspace of Rd, up to a factor of 1±ε. Such a coreset is useful for boosting the running time of computing a low-rank approximation (k-SVD/k-PCA) while using small memory. Coresets are also useful for handling streaming, dynamic and distributed data in parallel. With high probability, non-uniform sampling based on the so called leverage score or sensitivity of each row in A yields a coreset. The size of the (sampled) coreset is then near-linear in the total sum of these sensitivity bounds. We provide algorithms that compute provably tight bounds for the sensitivity of each input row. It is based on two ingredients: (i) iterative algorithm that computes the exact sensitivity of each row up to arbitrary small precision for (non-affine) k-subspaces, and (ii) a general reduction for computing a coreset for affine subspaces, given a coreset for (non-affine) subspaces in Rd. Experimental results on real-world datasets, including the English Wikipedia documents-term matrix, show that our bounds provide significantly smaller and data-dependent coresets also in practice. Full open source code is also provided.
FairGAN: GANs-based fairness-aware learning for recommendations with implicit feedback
Authors: Jie Li, Yongli Ren, Ke Deng
Venue: Conference WWW 2022
Year: 2022

Ranking algorithms in recommender systems influence people to make decisions. Conventional ranking algorithms based on implicit feedback data aim to maximize the utility to users by capturing users’ preferences over items. However, these utility-focused algorithms tend to cause fairness issues that require careful consideration in online platforms. Existing fairness-focused studies does not explicitly consider the problem of lacking negative feedback in implicit feedback data, while previous utility-focused methods ignore the importance of fairness in recommendations. To fill this gap, we propose a Generative Adversarial Networks (GANs) based learning algorithm FairGAN mapping the exposure fairness issue to the problem of negative preferences in implicit feedback data. FairGAN does not explicitly treat unobserved interactions as negative, but instead, adopts a novel fairness-aware learning strategy to dynamically generate fairness signals. This optimizes the search direction to make FairGAN capable of searching the space of the optimal ranking that can fairly allocate exposure to individual items while preserving users’ utilities as high as possible.
Deep modeling of the evolution of user preferences and item attributes in dynamic social networks
Authors: Peizhi Wu, Yi Tu, Zhenglu Yang, Adam Jatowt, Masato Odagaki
Venue: Conference WWW 2018
Year: 2018

Modeling the evolution of user preferences and item attributes in a dynamic social network is important because it is the basis for many applications, including recommendation systems and user behavior analysis. This study introduces a comprehensive general neural framework with several optimal strategies to jointly model the evolution of user preferences and item attributes in dynamic social networks. Preliminary experimental results conducted on real-world datasets demonstrate that our model performs better than the state-of-the-art methods.
Automl: From methodology to application
Authors: Yaliang Li, Zhen Wang, Yuexiang Xie, Bolin Ding, Kai Zeng, Ce Zhang
Venue: Conference CIKM 2021
Year: 2021

Machine Learning methods have been adopted for a wide range of real-world applications, ranging from social networks, online image/video-sharing platforms, and e-commerce to education, healthcare, etc. However, in practice, a large amount of effort is required to tune several components of machine learning methods, including data representation, hyperparameter, and model architecture, in order to achieve a good performance. To alleviate the required tunning efforts, Automated Machine Learning (AutoML), which can automate the process of applying machine learning methods, has been studied in both academy and industry recently. In this tutorial, we will introduce the main research topics of AutoML, including Hyperparameter Optimization, Neural Architecture Search, and Meta-Learning. Two emerging topics of AutoML, Automatic Feature Generation and Machine Learning Guided Database, will also be discussed since they are important components for real-world applications. For each topic, we will motivate it with application examples from industry, illustrate the state-of-the-art methodologies, and discuss some future research directions based on our experience from industry and the trends in academy.
MOOCCubeX: a large knowledge-centered repository for adaptive learning in MOOCs //
Authors: Jifan Yu, Yuquan Wang, Qingyang Zhong, Gan Luo, Yiming Mao, Kai Sun, Wenzheng Feng, Wei Xu, Shulin Cao, Kaisheng Zeng, Zijun Yao, Lei Hou, Yankai Lin, Peng Li, Jie Zhou, Bin Xu, Juanzi Li, Jie Tang, Maosong Sun
Venue: Conference CIKM 2021
Year: 2021

The prosperity of massive open online courses provides fodder for plentiful research efforts on adaptive learning. However, current open-access educational datasets are still far from sufficient to meet the need for various topics of adaptive learning. Existing released datasets often cover only small-scale data, lack fine-grained knowledge concepts. They are even difficult to curate and supplement due to platform limitations. In this work, we construct MOOCCubeX, a large, knowledge-centered repository consisting of 4,216 courses, 230,263 videos, 358,265 exercises, 637,572 fine-grained concepts and over 296 million behavioral data of 3,330,294 students, for supporting the research topics on adaptive learning in MOOCs. Licensed by XuetangX, one of the largest MOOC websites in China, we obtain abundant and diverse course resources and student behavioral data and are permitted to make subsequent periodic updates. We propose a framework to accomplish data processing, weakly supervised fine-grained concept graph mining, and data curation to improve usability and richness. Based on the fine-grained concepts, we re-organize the data from the knowledge perspective and acquire more external learning resources from the web. Our repository is now available at https://github.com/THU-KEG/MOOCCubeX.
Imitation learning to outperform demonstrators by directly extrapolating demonstrations
Authors: Yuanying Cai, Chuheng Zhang, Wei Shen, Xiaonan He, Xuyun Zhang, Longbo Huang
Venue: Conference CIKM 2022
Year: 2022

We consider the problem of imitation learning from suboptimal demonstrations that aims to learn a better policy than demonstrators. Previous methods usually learn a reward function to encode the underlying intention of the demonstrators and use standard reinforcement learning to learn a policy based on this reward function. Such methods can fail to control the distribution shift between demonstrations and the learned policy since the learned reward function may not generalize well on out-of-distribution samples and can mislead the agent to highly uncertain states, resulting in degenerated performance. To address this limitation, we propose a novel algorithm called Outperforming demonstrators by Directly Extrapolating Demonstrations(ODED). Instead of learning a reward function, ODED trains an ensemble of extrapolation networks that generate extrapolated demonstrations, i.e., demonstrations that may be induced by a good agent, based on provided demonstrations. With these extrapolated demonstrations, we can use an off-the-shelf imitation learning algorithm to learn a good policy. Guided by extrapolated demonstrations, the learned policy avoids visiting highly uncertain states and therefore controls the distribution shift. Empirically, we show that ODED outperforms suboptimal demonstrators and achieves better performance than state-of-the-art imitation learning algorithms on the MuJoCo and DeepMind Control Suite tasks.
Fairness in model-sharing games
Authors: Kate Donahue, Jon M. Kleinberg
Venue: Conference WWW 2023
Year: 2023

In many real-world situations, data is distributed across multiple self-interested agents. These agents can collaborate to build a machine learning model based on data from multiple agents, potentially reducing the error each experiences. However, sharing models in this way raises questions of fairness: to what extent can the error experienced by one agent be significantly lower than the error experienced by another agent in the same coalition? In this work, we consider two notions of fairness that each may be appropriate in different circumstances: egalitarian fairness (which aims to bound how dissimilar error rates can be) and proportional fairness (which aims to reward players for contributing more data). We similarly consider two common methods of model aggregation, one where a single model is created for all agents (uniform), and one where an individualized model is created for each agent. For egalitarian fairness, we obtain a tight multiplicative bound on how widely error rates can diverge between agents collaborating (which holds for both aggregation methods). For proportional fairness, we show that the individualized aggregation method always gives a small player error that is upper bounded by proportionality. For uniform aggregation, we show that this upper bound is guaranteed for any individually rational coalition (where no player wishes to leave to do local learning).
Investor- Imitator: A Framework for Trading Knowledge Extraction
Authors: Yi Ding, Weiqing Liu, Jiang Bian, Daoqiang Zhang, Tie-Yan Liu
Venue: Conference KDD 2018
Year: 2018

Stock trading is a popular investment approach in real world. However, since lacking enough domain knowledge and experience, it is very difficult for common investors to analyze thousands of stocks manually. Algorithmic investment provides another rational way to formulate human knowledge as a trading agent. However, it still requires well-built knowledge and experience to design effective trading algorithms in such a volatile market. Fortunately, various kinds of historical trading records are easy to obtain in this big-data era, it is invaluable of us to extract the trading knowledge hidden in the data to help people make better decisions. In this paper, we propose a reinforcement learning driven Investor-Imitator framework to formalize the trading knowledge, by imitating an investor's behavior with a set of logic descriptors. In particular, to instantiate specific logic descriptors, we introduce the Rank-Invest model that can keep the diversity of logic descriptors by learning to optimize different evaluation metrics. In the experiment, we first simulate three types of investors, representing different degrees of information disclosure we may meet in real market. By learning towards these investors, we can tell the inherent trading logic of the target investor with the Investor-Imitator empirically, and the extracted interpretable knowledge can help us better understand and construct trading portfolios. Experimental results in this paper sufficiently demonstrate the designed purpose of Investor-Imitator, it makes the Investor-Imitator an applicable and meaningful intelligent trading framework in financial investment research.
State dependent parallel neural hawkes process for limit order book event stream prediction and simulation
Authors: Zijian Shi, John Cartlidge
Venue: Conference KDD 2022
Year: 2022

The majority of trading in financial markets is executed through a limit order book (LOB). The LOB is an event-based continuously-updating system that records contemporaneous demand (`bids' to buy) and supply (`asks' to sell) for a financial asset. Following recent successes in the literature that combine stochastic point processes with neural networks to model event stream patterns, we propose a novel state-dependent parallel neural Hawkes process to predict LOB events and simulate realistic LOB data. The model is characterized by: (1) separate intensity rate modelling for each event type through a parallel structure of continuous time LSTM units; and (2) an event-state interaction mechanism that improves prediction accuracy and enables efficient sampling of the event-state stream. We first demonstrate the superiority of the proposed model over traditional stochastic or deep learning models for predicting event type and time of a real world LOB dataset. Using stochastic point sampling from a well trained model, we then develop a realistic deep learning-based LOB simulator that exhibits multiple stylized facts found in real LOB data.
No cost likelihood manipulation at test time for making better mistakes in deep networks
Authors: Shyamgopal Karthik, Ameya Prabhu, Puneet K. Dokania, Vineet Gandhi
Venue: Conference ICLR 2021
Year: 2021

There has been increasing interest in building deep hierarchy-aware classifiers that aim to quantify and reduce the severity of mistakes, and not just reduce the number of errors. The idea is to exploit the label hierarchy (e.g., the WordNet ontology) and consider graph distances as a proxy for mistake severity. Surprisingly, on examining mistake-severity distributions of the top-1 prediction, we find that current state-of-the-art hierarchy-aware deep classifiers do not always show practical improvement over the standard cross-entropy baseline in making better mistakes. The reason for the reduction in average mistake-severity can be attributed to the increase in low-severity mistakes, which may also explain the noticeable drop in their accuracy. To this end, we use the classical Conditional Risk Minimization (CRM) framework for hierarchy-aware classification. Given a cost matrix and a reliable estimate of likelihoods (obtained from a trained network), CRM simply amends mistakes at inference time; it needs no extra hyperparameters and requires adding just a few lines of code to the standard cross-entropy baseline. It significantly outperforms the state-of-the-art and consistently obtains large reductions in the average hierarchical distance of top-$k$ predictions across datasets, with very little loss in accuracy. CRM, because of its simplicity, can be used with any off-the-shelf trained model that provides reliable likelihood estimates.
Object retrieval and localization with spatially-constrained similarity measure and k-nn re-ranking
Authors: Xiaohui Shen, Zhe Lin 0001, Jonathan Brandt, Shai Avidan, Ying Wu 0001
Venue: Conference CVPR 2012
Year: 2012

One fundamental problem in object retrieval with the bag-of-visual words (BoW) model is its lack of spatial information. Although various approaches are proposed to incorporate spatial constraints into the BoW model, most of them are either too strict or too loose so that they are only effective in limited cases. We propose a new spatially-constrained similarity measure (SCSM) to handle object rotation, scaling, view point change and appearance deformation. The similarity measure can be efficiently calculated by a voting-based method using inverted files. Object retrieval and localization are then simultaneously achieved without post-processing. Furthermore, we introduce a novel and robust re-ranking method with the k-nearest neighbors of the query for automatically refining the initial search results. Extensive performance evaluations on six public datasets show that SCSM significantly outperforms other spatial models, while k-NN re-ranking outperforms most state-of-the-art approaches using query expansion.
Possibility before utility: Learning and using hierarchical affordances
Authors: Robby Costales, Shariq Iqbal, Fei Sha
Venue: Conference ICLR 2022
Year: 2022

Reinforcement learning algorithms struggle on tasks with complex hierarchical dependency structures. Humans and other intelligent agents do not waste time assessing the utility of every high-level action in existence, but instead only consider ones they deem possible in the first place. By focusing only on what is feasible, or "afforded", at the present moment, an agent can spend more time both evaluating the utility of and acting on what matters. To this end, we present Hierarchical Affordance Learning (HAL), a method that learns a model of hierarchical affordances in order to prune impossible subtasks for more effective learning. Existing works in hierarchical reinforcement learning provide agents with structural representations of subtasks but are not affordance-aware, and by grounding our definition of hierarchical affordances in the present state, our approach is more flexible than the multitude of approaches that ground their subtask dependencies in a symbolic history. While these logic-based methods often require complete knowledge of the subtask hierarchy, our approach is able to utilize incomplete and varying symbolic specifications. Furthermore, we demonstrate that relative to non-affordance-aware methods, HAL agents are better able to efficiently learn complex tasks, navigate environment stochasticity, and acquire diverse skills in the absence of extrinsic supervision -- all of which are hallmarks of human learning.
Practical counterfactual policy learning for top-k recommendations
Authors: Yaxu Liu, Jui-Nan Yen, Bo-Wen Yuan, Rundong Shi, Peng Yan, Chih-Jen Lin
Venue: Conference KDD 2022
Year: 2022

For building recommender systems, a critical task is to learn a policy with collected feedback (e.g., ratings, clicks) to decide which items to be recommended to users. However, it has been shown that the selection bias in the collected feedback leads to biased learning and thus a sub-optimal policy. To deal with this issue, counterfactual learning has received much attention, where existing approaches can be categorized as either value learning or policy learning approaches. This work studies policy learning approaches for top-K recommendations with a large item space and points out several difficulties related to importance weight explosion, observation insufficiency, and training efficiency. A practical framework for policy learning is then proposed to overcome these difficulties. Our experiments confirm the effectiveness and efficiency of the proposed framework.
Learning to hash robustly, guaranteed
Authors: Alexandr Andoni, Daniel Beaglehole
Venue: Conference ICML 2022
Year: 2022

The indexing algorithms for the high-dimensional nearest neighbor search (NNS) with the best worst-case guarantees are based on the randomized Locality Sensitive Hashing (LSH), and its derivatives. In practice, many heuristic approaches exist to "learn" the best indexing method in order to speed-up NNS, crucially adapting to the structure of the given dataset. Oftentimes, these heuristics outperform the LSH-based algorithms on real datasets, but, almost always, come at the cost of losing the guarantees of either correctness or robust performance on adversarial queries, or apply to datasets with an assumed extra structure/model. In this paper, we design an NNS algorithm for the Hamming space that has worst-case guarantees essentially matching that of theoretical algorithms, while optimizing the hashing to the structure of the dataset (think instance-optimal algorithms) for performance on the minimum-performing query. We evaluate the algorithm's ability to optimize for a given dataset both theoretically and practically. On the theoretical side, we exhibit a natural setting (dataset model) where our algorithm is much better than the standard theoretical one. On the practical side, we run experiments that show that our algorithm has a 1.8x and 2.1x better recall on the worst-performing queries to the MNIST and ImageNet datasets.
SQR: Balancing speed, quality and risk in online experiments
Authors: Ya Xu, Weitao Duan, Shaochen Huang
Venue: Conference KDD 2018
Year: 2018

Controlled experimentation, also called A/B testing, is widely adopted to accelerate product innovations in the online world. However, how fast we innovate can be limited by how we run experiments. Most experiments go through a "ramp up" process where we gradually increase the traffic to the new treatment to 100%. We have seen huge inefficiency and risk in how experiments are ramped, and it is getting in the way of innovation. This can go both ways: we ramp too slowly and much time and resource is wasted; or we ramp too fast and suboptimal decisions are made. In this paper, we build up a ramping framework that can effectively balance among Speed, Quality and Risk (SQR). We start out by identifying the top common mistakes experimenters make, and then introduce the four SQR principles corresponding to the four ramp phases of an experiment. To truly scale SQR to all experiments, we develop a statistical algorithm that is embedded into the process of running every experiment to automatically recommend ramp decisions. Finally, to complete the whole picture, we briefly cover the auto-ramp engineering infrastructure that can collect inputs and execute on the recommendations timely and reliably.
Rectifying pseudo labels: Iterative feature clustering for graph representation learning
Authors: Zhihui Hu, Guang Kou, Haoyu Zhang, Na Li, Ke Yang, Lin Liu
Venue: Conference CIKM 2021
Year: 2021

Graph Convolutional Networks (GCNs) are powerful representation learning methods for non-Euclidean data. Compared with the Euclidean data, labeling the non-Euclidean data is more expensive. Meanwhile, most existing GCNs only utilize few labeled data but ignore most of the unlabeled data. To address this issue, we design a novel end-to-end Iterative Feature Clustering Graph Convolutional Networks (IFC-GCN) that enhances the standard GCN with an Iterative Feature Clustering (IFC) module. The proposed IFC module constrains node features iteratively based on the predicted pseudo labels and feature clustering. Further, we design an EM-like framework for IFC-GCN training, which improves the network performance by rectifying the pseudo labels and the node features alternately. Theoretical analysis and experimental results show that our proposed IFC module can effectively modify the node features. Experimental results on public datasets demonstrate that IFC-GCN outperforms state-of-the-art methods on the semi-supervised node classification task.
Identifiability of cause and effect using regularized regression
Authors: Alexander Marx, Jilles Vreeken
Venue: Conference KDD 2019
Year: 2019

We consider the problem of telling apart cause from effect between two univariate continuous-valued random variables X and Y. In general, it is impossible to make definite statements about causality without making assumptions on the underlying model; one of the most important aspects of causal inference is hence to determine under which assumptions are we able to do so. In this paper we show under which general conditions we can identify cause from effect by simply choosing the direction with the best regression score. We define a general framework of identifiable regression-based scoring functions, and show how to instantiate it in practice using regression splines. Compared to existing methods that either give strong guarantees, but are hardly applicable in practice, or provide no guarantees, but do work well in practice, our instantiation combines the best of both worlds; it gives guarantees, while empirical evaluation on synthetic and real-world data shows that it performs at least as well as the state of the art.