This work addresses a key challenge in the effective adoption of Recurrent Neural Networks (RNNs) by reducing inference time and expanding the scope of a prediction. It introduces compressed learning, a novel approach that integrates Context-Free Grammar (CFG) and online tokenization into the training and inference of RNNs for streaming inputs. Through a hierarchical compression algorithm, it compresses an input sequence to a CFG and makes predictions based on the compressed sequence. Its algorithm design employs a set of techniques to overcome the issues from the myopic nature of online tokenization, the tension between inference accuracy and compression rate, and other complexities in sequence compression and prediction. Its effectiveness is theoretically analyzed and empirically validated on 16 real-world sequences, including program function calls, memory traces, and system logs. Empirical results demonstrate that compressed learning can successfully recognize and leverage repetitive patterns in input sequences, and effectively translate them into dramatic (1–1,762 \(\times\) ) inference speedups as well as much (1–7,830 \(\times\) ) expanded prediction scope, while keeping the inference accuracy satisfactory.

Cross-domain recommendation (CDR) aims to leverage the rich information from the source domain to enhance recommendation performance in the target domain. However, the data imbalance problem inherent across different domains compromises the effectiveness of CDR approaches, posing a significant challenge to CDR. Most current CDR methodologies focus on creating better user embeddings for the target domain, yet usually neglect the inconsistency in user activities due to data imbalance. As a result, the process of creating user embeddings tends to prioritize users with more frequent interactions and leave less active users underserved, leading these CDR methods to struggle in making accurate recommendations for those with fewer interactions. Such bias in creating embeddings reveals the fact that ''not all embeddings are created equal'' in CDR, which serves as the primary motivation of this study. Inspired by the recent development of contrastive learning, this paper proposes User-aware Contrastive Learning for Robust cross-domain recommendation (UCLR), enhancing the robustness of cross-domain recommendation. Specifically, our proposed method consists of two sub-modules: (i) pretrained global embedding, where the global user embeddings are pretrained across all the domains; (ii) contrastive dual-stream collaborative autoencoder, where more equal user embeddings are generated by optimizing contrastive loss with individualized temperatures. To further improve the performance of our method in each domain, we finetune the whole framework of UCLR based on Low-Rank Adaptation (LoRA). Theoretically, our method is equipped with a provable convergence guarantee during the contrastive learning stage. Furthermore, we also conduct comprehensive experiments on real-world datasets to validate the effectiveness of our proposed method.

For years, machine learning has become the dominant approach to a variety of information retrieval tasks. The performance of machine learning algorithms heavily depends on their hyperparameters. It is hence critical to identity the optimal hyperparameter configuration when applying machine learning algorithms. Most of existing hyperparameter optimization methods assume a static relationship between hyperparameter configuration and algorithmic performance and are thus not suitable for many information retrieval applications with non-stationary environments such as e-commerce recommendation and online advertising. To address this limitation, we study online hyperparameter optimization, where the hyperparameter configuration is optimized on the fly. We formulate online hyperparameter optimization as a non-stationary continuum-armed bandits problem in which each arm corresponds to a hyperparameter configuration and the algorithmic performance is viewed as reward. For this problem, we develop principled methods with strong theoretical guarantees in terms of dynamic regret. The key idea is to adaptively discretize the continuous arm set and estimate the mean reward of each arm via weighted averaging. As a case application, we show how our methods can be applied to optimize the hyperparameter of vector-based candidate generation algorithm and empirically demonstrate the effectiveness and efficiency of our methods on public advertising dataset and online A/B testing. Furthermore, to the best of our knowledge, our methods are the first to achieve sub-linear dynamic regret bounds for continuum-armed bandits, which may be of independent interest.

The conventional solution to learning to rank problems ranks individual documents by prediction scores greedily. Recent emerged re-ranking models, which take as input initial lists, aim to capture document interdependencies and directly generate the optimal ordered lists. Typically, a re-ranking model is learned from a set of labeled data, which can achieve favorable performance on average. However, it can be suboptimal for individual queries because the available training data is usually highly imbalanced. This problem is challenging due to the absence of informative data for some queries and furthermore, the lack of a good data augmentation policy.

Recurrent Neural Networks (RNN) are widely used for various prediction tasks on sequences such as text, speed signals, program traces, and system logs. Due to RNNs’ inherently sequential behavior, one key challenge for the effective adoption of RNNs is to reduce the time spent on RNN inference and to increase the scope of a prediction. This work introduces CFG-guided compressed learning, an approach that creatively integrates Context-Free Grammar (CFG) and online tokenization into RNN learning and inference for streaming inputs. Through a hierarchical compression algorithm, it compresses an input sequence to a CFG and makes predictions based on the compressed sequence. Its algorithm design employs a set of techniques to overcome the issues from the myopic nature of online tokenization, the tension between inference accuracy and compression rate, and other complexities. Experiments on 16 real-world sequences of various types validate that the proposed compressed learning can successfully recognize and leverage repetitive patterns in input sequences, and effectively translate them into dramatic (1-1762×) inference speedups as well as much (1-7830×) expanded prediction scope, while keeping the inference accuracy satisfactory.

Learning with streaming data has attracted much attention during the past few years. Though most studies consider data stream with fixed features, in real practice the features may be evolvable. For example, features of data gathered by limited-lifespan sensors will change when these sensors are substituted by new ones. In this article, we propose a novel learning paradigm: Feature Evolvable Streaming Learning where old features would vanish and new features would occur. Rather than relying on only the current features, we attempt to recover the vanished features and exploit it to improve performance. Specifically, we learn a mapping from the overlapping period to recover old features and then we learn two models from the recovered features and the current features, respectively. To benefit from the recovered features, we develop two ensemble methods. In the first method, we combine the predictions from two models and theoretically show that with the assistance of old features, the performance on new features can be improved and we provide a tighter bound when the loss function is exponentially concave. In the second approach, we dynamically select the best single prediction and establish a better performance guarantee when the best model switches. Experiments on both synthetic and real data validate the effectiveness of our proposal.

Traditional Learning to Rank (LTR) models in E-commerce are usually trained on logged data from a single domain. However, data may come from multiple domains, such as hundreds of countries in international E-commerce platforms. Learning a single ranking function obscures domain differences, while learning multiple functions for each domain may also be inferior due to ignoring the correlations between domains. It can be formulated as a multi-task learning problem where multiple tasks share the same feature and label space. To solve the above problem, which we name Multi-Scenario Learning to Rank, we propose the Hybrid of implicit and explicit Mixture-of-Experts (HMoE) approach. Our proposed solution takes advantage of Multi-task Mixture-of-Experts to implicitly identify distinctions and commonalities between tasks in the feature space, and improves the performance with a stacked model learning task relationships in the label space explicitly. Furthermore, to enhance the flexibility, we propose an end-to-end optimization method with a task-constrained back-propagation strategy. We empirically verify that the optimization method is more effective than two-stage optimization required by the stacked approach. Experiments on real-world industrial datasets demonstrate that HMoE significantly outperforms the popular multi-task learning methods. HMoE is in-use in the search system of AliExpress and achieved 1.92% revenue gain in the period of one-week online A/B testing. We also release a sampled version of our dataset to facilitate future research.

In this paper, we propose a simple variant of the original SVRG, called variance reduced stochastic gradient descent (VR-SGD). Unlike the choices of snapshot and starting points in SVRG and its proximal variant, Prox-SVRG, the two vectors of VR-SGD are set to the average and last iterate of the previous epoch, respectively. The settings allow us to use much larger learning rates, and also make our convergence analysis more challenging. We also design two different update rules for smooth and nonsmooth objective functions, respectively, which means that VR-SGD can tackle non-smooth and/or non-strongly convex problems directly without any reduction techniques. Moreover, we analyze the convergence properties of VR-SGD for strongly convex problems, which show that VR-SGD attains linear convergence. Different from most algorithms that have no convergence guarantees for nonstrongly convex problems, we also provide the convergence guarantees of VR-SGD for this case, and empirically verify that VR-SGD with varying learning rates achieves similar performance to its momentum accelerated variant that has the optimal convergence rate O(1=T2). Finally, we apply VR-SGD to solve various machine learning problems, such as convex and non-convex empirical risk minimization, and leading eigenvalue computation. Experimental results show that VR-SGD converges significantly faster than SVRG and Prox-SVRG, and usually outperforms state-of-the-art accelerated methods, e.g., Katyusha.

Deep neural network (DNN) as a popular machine learning model is found to be vulnerable to adversarial attack. This attack constructs adversarial examples by adding small perturbations to the raw input, while appearing unmodified to human eyes but will be misclassified by a well-trained classifier. In this paper, we focus on the black-box attack setting where attackers have almost no access to the underlying models. To conduct black-box attack, a popular approach aims to train a substitute model based on the information queried from the target DNN. The substitute model can then be attacked using existing white-box attack approaches, and the generated adversarial examples will be used to attack the target DNN. Despite its encouraging results, this approach suffers from poor query efficiency, i.e., attackers usually needs to query a huge amount of times to collect enough information for training an accurate substitute model. To this end, we first utilize state-of-the-art white-box attack methods to generate samples for querying, and then introduce an active learning strategy to significantly reduce the number of queries needed. Besides, we also propose a diversity criterion to avoid the sampling bias. Our extensive experimental results on MNIST and CIFAR-10 show that the proposed method can reduce more than 90% of queries while preserve attacking success rates and obtain an accurate substitute model which is more than 85% similar with the target oracle.

Feature selection is a challenging problem for high dimensional data processing, which arises in many real applications such as data mining, information retrieval, and pattern recognition. In this paper, we study the problem of unsupervised feature selection. The problem is challenging due to the lack of label information to guide feature selection. We formulate the problem of unsupervised feature selection from the viewpoint of graph regularized data reconstruction. The underlying idea is that the selected features not only preserve the local structure of the original data space via graph regularization, but also approximately reconstruct each data point via linear combination. Therefore, the graph regularized data reconstruction error becomes a natural criterion for measuring the quality of the selected features. By minimizing the reconstruction error, we are able to select the features that best preserve both the similarity and discriminant information in the original data. We then develop an efficient gradient algorithm to solve the corresponding optimization problem. We evaluate the performance of our proposed algorithm on text clustering. The extensive experiments demonstrate the effectiveness of our proposed approach.

Semi-supervised clustering leverages side information such as pairwise constraints to guide clustering procedures. Despite promising progress, existing semi-supervised clustering approaches overlook the condition of side information being generated sequentially, which is a natural setting arising in numerous real-world applications such as social network and e-commerce system analysis. Given emerged new constraints, classical semi-supervised clustering algorithms need to re-optimize their objectives over all data samples and constraints in availability, which prevents them from efficiently updating the obtained data partitions. To address this challenge, we propose an efficient dynamic semi-supervised clustering framework that casts the clustering problem into a search problem over a feasible convex set, i.e., a convex hull with its extreme points being an ensemble of m data partitions. According to the principle of ensemble clustering, the optimal partition lies in the convex hull, and can thus be uniquely represented by an m-dimensional probability simplex vector. As such, the dynamic semi-supervised clustering problem is simplified to the problem of updating a probability simplex vector subject to the newly received pairwise constraints. We then develop a computationally efficient updating procedure to update the probability simplex vector in O(m2) time, irrespective of the data size n. Our empirical studies on several real-world benchmark datasets show that the proposed algorithm outperforms the state-of-the-art semi-supervised clustering algorithms with visible performance gain and significantly reduced running time.

Real-world datasets often involve multiple views of data items, e.g., a Web page can be described by both its content and anchor texts of hyperlinks leading to it; photos in Flickr could be characterized by visual features, as well as user contributed tags. Different views provide information complementary to each other. Synthesizing multi-view features can lead to a comprehensive description of the data items, which could benefit many data analytic applications. Unfortunately, the simple idea of concatenating different feature vectors ignores statistical properties of each view and usually incurs the “curse of dimensionality” problem. We propose Multi-view Concept Learning (MCL), a novel nonnegative latent representation learning algorithm for capturing conceptual factors from multi-view data. MCL exploits both multi-view information and label information. The key idea is to learn a common latent space across different views which (1) captures the semantic relationships between data items through graph embedding regularization on labeled items, and (2) allows each latent factor to be associated with a subset of views via sparseness constraints. In this way, MCL could capture flexible conceptual patterns hidden in multi-view features. Experiments on a toy problem and three real-world datasets show that MCL performs well and outperforms baseline methods.

Expert finding for question answering is a challenging problem in community-based question answering (CQA) systems, arising in many real applications such as question routing and identification of best answers. In order to provide high-quality experts, many existing approaches learn the user model from their past question-answering activities in CQA systems. However, the past activities of users in most CQA systems are rather few, and thus the user model may not be well inferred in practice. In this paper, we consider the problem of expert finding from the viewpoint of missing value estimation. We then employ users' social networks for inferring user model, and thus improve the performance of expert finding in CQA systems. In addition, we develop a novel graph-regularized matrix completion algorithm for inferring the user model. We further develop two efficient iterative procedures, GRMC-EGM and GRMC-AGM, to solve the optimization problem. GRMC-EGM utilizes the Extended Gradient Method (EGM), while GRMC-AGM applies the Accelerated proximal Gradient search Method (AGM), for the optimization. We evaluate our methods on the well-known question answering system Quora, and the popular social network Twitter. Our empirical study shows the effectiveness of the proposed algorithms in comparison to the state-of-the-art expert finding algorithms.

Different from traditional one-sided clustering techniques, coclustering makes use of the duality between samples and features to partition them simultaneously. Most of the existing co-clustering algorithms focus on modeling the relationship between samples and features, whereas the intersample and interfeature relationships are ignored. In this paper, we propose a novel coclustering algorithm named Locally Discriminative Coclustering (LDCC) to explore the relationship between samples and features as well as the intersample and interfeature relationships. Specifically, the sample-feature relationship is modeled by a bipartite graph between samples and features. And we apply local linear regression to discovering the intrinsic discriminative structures of both sample space and feature space. For each local patch in the sample and feature spaces, a local linear function is estimated to predict the labels of the points in this patch. The intersample and interfeature relationships are thus captured by minimizing the fitting errors of all the local linear functions. In this way, LDCC groups strongly associated samples and features together, while respecting the local structures of both sample and feature spaces. Our experimental results on several benchmark data sets have demonstrated the effectiveness of the proposed method.

The phenomenon of propagation is universal in our daily life. For example, infectious diseases can be transmitted from one person to another, hot news is disseminated widely on the Internet, and classic passages written by the popular users can be shared by many other users in online social network sites. With the emerging of online social network sites, such as Facebook, YouTube, and Flickr, many literatures try to analyse patterns of information propagation and design effective virtual marketing strategies in these sites. However, few metrics have been designed to measure the characteristic of information propagation. In this paper, we propose a novel metric for measuring members’ contribution to information propagation in online social network sites. As a case, we analyse large-scale traces of members’ contribution to photo dissemination in Flickr and find that the distribution of members’ contribution follows a power law distribution, which reveals that most of the information is created and propagated by a few members.