OpenRaiser/Intern-Atlas huggingface dataset:
Show Me the Whole World: Towards Entire Item Space Exploration for Interactive Personalized Recommendations
Authors: Yu Song, Shuai Sun, Jianxun Lian, Hong Huang, Yu Li, Hai Jin, Xing Xie
Venue: Conference WSDM 2022
Year: 2022

User interest exploration is an important and challenging topic in recommender systems, which alleviates the closed-loop effects between recommendation models and user-item interactions.Contextual bandit (CB) algorithms strive to make a good trade-off between exploration and exploitation so that users' potential interests have chances to expose. However, classical CB algorithms can only be applied to a small, sampled item set (usually hundreds), which forces the typical applications in recommender systems limited to candidate post-ranking, homepage top item ranking, ad creative selection, or online model selection (A/B test). In this paper, we introduce two simple but effective hierarchical CB algorithms to make a classical CB model (such as LinUCB and Thompson Sampling) capable to explore users' interest in the entire item space without limiting to a small item set. We first construct a hierarchy item tree via a bottom-up clustering algorithm to organize items in a coarse-to-fine manner. Then we propose ahierarchical CB (HCB) algorithm to explore users' interest on the hierarchy tree. HCB takes the exploration problem as a series of decision-making processes, where the goal is to find a path from the root to a leaf node, and the feedback will be back-propagated to all the nodes in the path. We further propose aprogressive hierarchical CB (pHCB) algorithm, which progressively extends visible nodes which reach a confidence level for exploration, to avoid misleading actions on upper-level nodes in the sequential decision-making process. Extensive experiments on two public recommendation datasets demonstrate the effectiveness and flexibility of our methods.
Learning to learn the future: Modeling concept drifts in time series prediction
Authors: Xiaoyu You, Mi Zhang, Daizong Ding, Fuli Feng, Yuanmin Huang
Venue: Conference CIKM 2021
Year: 2021

Time series prediction has great practical value in a wide range of real-world scenarios such as stock market and retail. Existing methods typically face model aging issue caused by the concept drift: the model performance degrades along time. Undoubtedly, the model aging issue can cause serious damage in practical usage, e.g. wrong predictions in stock price may cause catastrophic losses in the financial domain. Therefore, it is essential to address the model aging issue so as to promise the predictor's performance in the future. In this paper, we propose a novel solution to address the issue. First, we uncover the theoretical connection between the complex concept drift in time series data and the gradients of deep neural networks. Based on this, we propose a novel framework called learning to learn the future. Specifically, we develop a learning method to model the concept drift during the inference stage, which can help the model generalize well in the future. Furthermore, to mitigate the impact of noises and randomness of time series data, we propose to enhance the framework by leveraging similar series in concept drift modeling. To the best of our knowledge, our approach is the first general solution to model aging issue in time series prediction. We conduct extensive experiments on three real-world datasets, which validate the effectiveness of our framework. For instance, it achieves a relative improvement of 33% in stock price prediction over the state-of-the-art methods.
Scaling multinomial logistic regression via hybrid parallelism
Authors: Parameswaran Raman, Sriram Srinivasan, Shin Matsushima, Xinhua Zhang, Hyokun Yun, S. V. N. Vishwanathan
Venue: Conference KDD 2019
Year: 2019

We study the problem of scaling Multinomial Logistic Regression (MLR) to datasets with very large number of data points in the presence of large number of classes. At a scale where neither data nor the parameters are able to fit on a single machine, we argue that simultaneous data and model parallelism (Hybrid Parallelism) is inevitable. The key challenge in achieving such a form of parallelism in MLR is the log-partition function which needs to be computed across all K classes per data point, thus making model parallelism non-trivial. To overcome this problem, we propose a reformulation of the original objective that exploits double-separability, an attractive property that naturally leads to hybrid parallelism. Our algorithm (DS-MLR) is asynchronous and completely de-centralized, requiring minimal communication across workers while keeping both data and parameter workloads partitioned. Unlike standard data parallel approaches, DS-MLR avoids bulk-synchronization by maintaining local normalization terms on each worker and accumulating them incrementally using a token-ring topology. We demonstrate the versatility of DS-MLR under various scenarios in data and model parallelism, through an empirical study consisting of real-world datasets. In particular, to demonstrate scaling via hybrid parallelism, we created a new benchmark dataset (Reddit-Full) by pre-processing 1.7 billion reddit user comments spanning the period 2007-2015. We used DS-MLR to solve an extreme multi-class classification problem of classifying 211 million data points into their corresponding subreddits. Reddit-Full is a massive data set with data occupying 228 GB and 44 billion parameters occupying 358 GB. To the best of our knowledge, no other existing methods can handle MLR in this setting.
A hierarchical method for multi-class support vector machines
Authors: Volkan Vural, Jennifer G. Dy
Venue: Conference ICML 2004
Year: 2004

We introduce a framework, which we call Divide-by-2 (DB2), for extending support vector machines (SVM) to multi-class prob-lems. DB2 offers an alternative to the stan-dard one-against-one and one-against-rest al-gorithms. For an N class problem, DB2 pro-duces an N − 1 node binary decision tree where nodes represent decision boundaries formed by N−1 SVM binary classifiers. This tree structure allows us to present a gener-alization and a time complexity analysis of DB2. Our analysis and related experiments show that, DB2 is faster than one-against-one and one-against-rest algorithms in terms of testing time, significantly faster than one-against-rest in terms of training time, and that the cross-validation accuracy of DB2 is comparable to these two methods. 1.
Towards Theoretical Analysis of Transformation Complexity of ReLU DNNs
Authors: Jie Ren 0018, Mingjie Li, Meng Zhou, Shih-Han Chan, Quanshi Zhang
Venue: Conference ICML 2022
Year: 2022

This paper aims to theoretically analyze the complexity of feature transformations encoded in piecewise linear DNNs with ReLU layers. We propose metrics to measure three types of complexities of transformations based on the information theory. We further discover and prove the strong correlation between the complexity and the disentanglement of transformations. Based on the proposed metrics, we analyze two typical phenomena of the change of the transformation complexity during the training process, and explore the ceiling of a DNN's complexity. The proposed metrics can also be used as a loss to learn a DNN with the minimum complexity, which also controls the over-fitting level of the DNN and influences adversarial robustness, adversarial transferability, and knowledge consistency. Comprehensive comparative studies have provided new perspectives to understand the DNN.
Embedding Global and Local Influences for Dynamic Graphs
Authors: Meng Liu, Jiaming Wu, Yong Liu
Venue: Conference CIKM 2022
Year: 2022

Graph embedding is becoming increasingly popular due to its ability of representing large-scale graph data by mapping nodes to low-dimensional space. Current research usually focuses on transductive learning, which aims to generates fixed node embeddings by training the whole graph. However, dynamic graph changes constantly with new node additions and interactions. Unlike transductive learning, inductive learning attempts to dynamically generate node embeddings over time even for unseen nodes, which is more suitable for real-world applications. Therefore, we propose an inductive dynamic graph embedding method called AGLI by aggregating global and local influences. We propose an aggregator function that integrates global influence with local influence to generate node embeddings at any time. We conduct extensive experiments on several real-world datasets and compare AGLI with several state-of-the-art baseline methods on various tasks. The experimental results show that AGLI achieves better performance than the state-of-the-art baseline methods.
New event detection based on indexing-tree and named entity
Authors: Kuo Zhang, Juan Zi, Li Gang Wu
Venue: Conference SIGIR 2007
Year: 2007

New Event Detection (NED) aims at detecting from one or multiple streams of news stories that which one is reported on a new event (i.e. not reported previously). With the overwhelming volume of news available today, there is an increasing need for a NED system which is able to detect new events more efficiently and accurately. In this paper we propose a new NED model to speed up the NED task by using news indexing-tree dynamically. Moreover, based on the observation that terms of different types have different effects for NED task, two term reweighting approaches are proposed to improve NED accuracy. In the first approach, we propose to adjust term weights dynamically based on previous story clusters and in the second approach, we propose to employ statistics on training data to learn the named entity reweighting model for each class of stories. Experimental results on two Linguistic Data Consortium (LDC) datasets TDT2 and TDT3 show that the proposed model can improve both efficiency and accuracy of NED task significantly, compared to the baseline system and other existing systems.
When recommender systems meet fleet management: Practical study in online driver repositioning system
Authors: Zhe Xu, Chang Men, Peng Li, Bicheng Jin, Ge Li, Yue Yang, Chunyang Liu, Ben Wang, Xiaohu Qie
Venue: Conference WWW 2020
Year: 2020

E-hailing platforms have become an important component of public transportation in recent years. The supply (online drivers) and demand (passenger requests) are intrinsically imbalanced because of the pattern of human behavior, especially in time and locations such as peak hours and train stations. Hence, how to balance supply and demand is one of the key problems to satisfy passengers and drivers and increase social welfare. As an intuitive and effective approach to address this problem, driver repositioning has been employed by some real-world e-hailing platforms. In this paper, we describe a novel framework of driver repositioning system, which meets various requirements in practical situations, including robust driver experience satisfaction and multi-driver collaboration. We introduce an effective and user-friendly driver interaction design called “driver repositioning task”. A novel modularized algorithm is developed to generate the repositioning tasks in real time. To our knowledge, this is the first industry-level application of driver repositioning. We evaluate the proposed method in real-world experiments, achieving a 2% improvement of driver income. Our framework has been fully deployed in the online system of DiDi Chuxing and serves millions of drivers on a daily basis.
Fairness-aware Guaranteed Display Advertising Allocation under Traffic Cost Constraint
Authors: Liang Dai, Zhonglin Zu, Hao Wu, Liang Wang, Bo Zheng
Venue: Conference WWW 2023
Year: 2023

Real-time Bidding (RTB) and Guaranteed Display (GD) advertising are two primary ways to sell impressions for publishers in online display advertising. Although GD contract serves less efficiently compared to RTB ads, it helps advertisers reach numerous target audiences at a lower cost and allows publishers to increase overall advertising revenue. However, with billion-scale requests online per day, it’s a challenging problem for publishers to decide whether and which GD ad to display for each impression. In this paper, we propose an optimal allocation model for GD contracts considering optimizing three objectives: maximizing guaranteed delivery and impressions’ quality and minimizing the extra traffic cost of GD contracts to increase overall revenue. The traffic cost of GD contracts is defined as the potential expected revenue if the impression is allocated to RTB ads. Our model dynamically adjusts the weights for each GD contract between impressions’ quality and traffic cost based on real-time performance, which produces fairness-aware allocation results. A parallel training framework based on Parameter-Server (PS) architecture is utilized to efficiently and periodically update the model. Deriving from the allocation model, we also propose a simple and adaptive online bidding strategy for GD contracts, which can be updated quickly by feedback-based algorithms to achieve optimal impression allocation even in complex and dynamic environments. We demonstrate the effectiveness of our proposed method by using both offline evaluation and online A/B testing.
CONFLUX: A Request-level Fusion Framework for Impression Allocation via Cascade Distillation
Authors: XiaoYu Wang 0014, Bin Tan, Yonghui Guo, Tao Yang, Dongbo Huang, Lan Xu 0001, Nikolaos M. Freris, Hao Zhou 0001, Xiangyang Li 0001
Venue: Conference KDD 2022
Year: 2022

Guaranteed delivery (GD) and real-time bidding (RTB) constitute two parallel profit streams for the publisher. The diverse advertiser demands (brand or instant effect) result in different selling (in bulk or via auction) and pricing (fixed unit price or various bids) patterns, which naturally raises the fusion allocation issue of breaking the two markets' barrier and selling out at the global highest price boosting the total revenue. The fusion process complicates the competition between GD and RTB, and GD contracts with overlapping targeting. The non-stationary user traffic and bid landscape further worsen the situation, making the assignment unsupervised and hard to evaluate. Thus, a static policy or coarse-grained modeling from existing work is inferior to facing the above challenges.
Uncertainty Quantification for Fairness in Two-Stage Recommender Systems
Authors: Lequn Wang, Thorsten Joachims
Venue: Conference WSDM 2023
Year: 2023

Many large-scale recommender systems consist of two stages. The first stage efficiently screens the complete pool of items for a small subset of promising candidates, from which the second-stage model curates the final recommendations. In this paper, we investigate how to ensure group fairness to the items in this two-stage architecture. In particular, we find that existing first-stage recommenders might select an irrecoverably unfair set of candidates such that there is no hope for the second-stage recommender to deliver fair recommendations. To this end, motivated by recent advances in uncertainty quantification, we propose two threshold-policy selection rules that can provide distribution-free and finite-sample guarantees on fairness in first-stage recommenders. More concretely, given any relevance model of queries and items and a point-wise lower confidence bound on the expected number of relevant items for each threshold-policy, the two rules find near-optimal sets of candidates that contain enough relevant items in expectation from each group of items. To instantiate the rules, we demonstrate how to derive such confidence bounds from potentially partial and biased user feedback data, which are abundant in many large-scale recommender systems. In addition, we provide both finite-sample and asymptotic analyses of how close the two threshold selection rules are to the optimal thresholds. Beyond this theoretical analysis, we show empirically that these two rules can consistently select enough relevant items from each group while minimizing the size of the candidate sets for a wide range of settings.
Outguard: Detecting in-browser covert cryptocurrency mining in the wild
Authors: Amin Kharraz, Zane Ma, Paul Murley, Charles Lever, Joshua Mason, Andrew Miller, Nikita Borisov, Manos Antonakakis, Michael D. Bailey
Venue: Conference WWW 2019
Year: 2019

In-browser cryptojacking is a form of resource abuse that leverages end-users' machines to mine cryptocurrency without obtaining the users' consent. In this paper, we design, implement, and evaluate Outguard, an automated cryptojacking detection system. We construct a large ground-truth dataset, extract several features using an instrumented web browser, and ultimately select seven distinctive features that are used to build an SVM classification model. Outguardachieves a 97.9% TPR and 1.1% FPR and is reasonably tolerant to adversarial evasions. We utilized Outguardin the wild by deploying it across the Alexa Top 1M websites and found 6,302 cryptojacking sites, of which 3,600 are new detections that were absent from the training data. These cryptojacking sites paint a broad picture of the cryptojacking ecosystem, with particular emphasis on the prevalence of cryptojacking websites and the shared infrastructure that provides clues to the operators behind the cryptojacking phenomenon.
Hierarchical classification: combining Bayes with SVM
Authors: Nicolò Cesa-Bianchi, Claudio Gentile, Luca Zaniboni
Venue: Conference ICML 2006
Year: 2006

We study hierarchical classification in the general case when an instance could belong to more than one class node in the underlying taxonomy. Experiments done in previous work showed that a simple hierarchy of Support Vectors Machines (SVM) with a top-down evaluation scheme has a surprisingly good performance on this kind of task. In this paper, we introduce a refined evaluation scheme which turns the hierarchical SVM classifier into an approximator of the Bayes optimal classifier with respect to a simple stochastic model for the labels. Experiments on synthetic datasets, generated according to this stochastic model, show that our refined algorithm outperforms the simple hierarchical SVM. On real-world data, however, the advantage brought by our approach is a bit less clear. We conjecture this is due to a higher noise rate for the training labels in the low levels of the taxonomy.
Games, algorithms, and the Internet
Authors: Christos H. Papadimitriou
Venue: Conference WWW 2011
Year: 2011

The advent of the Internet brought parallel paradigm shifts to both Economics and Computer Science. Computer scientists realized that large-scale performing systems can emerge from the interaction of selfish agents and that incentives are a quintessential part of a good system design. And economists saw that the default platforms of economic transactions are computational and interconnected. Algorithmic Game Theory is a subdiscipline that emerged from this turmoil, revisiting some of the most important problems in Economics and Game Theory from a computational and network perspective. This talk will survey some of the major themes, results and challenges in this field.
Joint segmentation and classification of human actions in video
Authors: Minh Hoai Nguyen, Zhen-Zhong Lan, Fernando De la Torre
Venue: Conference CVPR 2011
Year: 2011

Automatic video segmentation and action recognition has been a long-standing problem in computer vision. Much work in the literature treats video segmentation and action recognition as two independent problems; while segmentation is often done without a temporal model of the activity, action recognition is usually performed on pre-segmented clips. In this paper we propose a novel method that avoids the limitations of the above approaches by jointly performing video segmentation and action recognition. Unlike standard approaches based on extensions of dynamic Bayesian networks, our method is based on a discriminative temporal extension of the spatial bag-of-words model that has been very popular in object recognition. The classification is performed robustly within a multi-class SVM framework whereas the inference over the segments is done efficiently with dynamic programming. Experimental results on honeybee, Weizmann, and Hollywood datasets illustrate the benefits of our approach compared to state-of-the-art methods.
Challenges of computational verification in social multimedia
Authors: Christina Boididou, Symeon Papadopoulos, Yiannis Kompatsiaris, Steve Schifferes, Nic Newman
Venue: Conference WWW 2014
Year: 2014

Fake or misleading multimedia content and its distribution through social networks such as Twitter constitutes an increasingly important and challenging problem, especially in the context of emergencies and critical situations. In this paper, the aim is to explore the challenges involved in applying a computational verification framework to automatically classify tweets with unreliable media content as fake or real. We created a data corpus of tweets around big events focusing on the ones linking to images (fake or real) of which the reliability could be verified by independent online sources. Extracting content and user features for each tweet, we explored the fake prediction accuracy performance using each set of features separately and in combination. We considered three approaches for evaluating the performance of the classifier, ranging from the use of standard cross-validation, to independent groups of tweets and to cross-event training. The obtained results included a 81% for tweet features and 75% for user ones in the case of cross-validation. When using different events for training and testing, the accuracy is much lower (up to %58) demonstrating that the generalization of the predictor is a very challenging issue.
Robust fitting of multiple structures: The statistical learning approach
Authors: Tat-Jun Chin, Hanzi Wang, David Suter
Venue: Conference ICCV 2009
Year: 2009

We propose an unconventional but highly effective approach to robust fitting of multiple structures by using statistical learning concepts. We design a novel Mercer kernel for the robust estimation problem which elicits the potential of two points to have emerged from the same underlying structure. The Mercer kernel permits the application of well-grounded statistical learning methods, among which nonlinear dimensionality reduction, principal component analysis and spectral clustering are applied for robust fitting. Our method can remove gross outliers and in parallel discover the multiple structures present. It functions well under severe outliers (more than 90% of the data) and considerable inlier noise without requiring elaborate manual tuning or unrealistic prior information. Experiments on synthetic and real problems illustrate the superiority of the proposed idea over previous methods.