Michael R. Lyu

TMLR Journal 2026 Journal Article

Data Compressibility Quantifies LLM Memorization

• Yizhan Huang
• Zhe Yang
• Meifang Chen
• HUANG Nianchen
• Jianping Zhang
• Michael R. Lyu

Large Language Models (LLMs) are known to memorize portions of their training data, sometimes even reproduce content verbatim when prompted appropriately. Despite substantial interest, existing LLM memorization research has offered limited insight into how training data influences memorization and largely lacks quantitative characterization. In this work, we build upon the line of research that seeks to quantify memorization through data compressibility. We analyze why prior attempts fail to yield a reliable quantitative measure and show that a surprisingly simple shift from instance-level to set-level metrics uncovers a robust phenomenon, which we term the \textit{Entropy--Memorization (EM) Linearity}. This law states that a set-level data entropy estimator exhibits a linear correlation with memorization scores. We validate the EM Linearity through extensive experiments across a wide range of open-source models and experimental configurations. We further investigate the role of the token space—an implicit yet pivotal factor in our method—and identify an additional variant of the EM Law. Besides, we made a side observation that EM Linearity enables a simple application to distinguish between LLM train data and test data.

ICLR Conference 2025 Conference Paper

Competing Large Language Models in Multi-Agent Gaming Environments

• Jen-tse Huang 0001
• Eric John Li
• Man Ho Lam
• Tian Liang
• Wenxuan Wang 0001
• Youliang Yuan
• Wenxiang Jiao
• Xing Wang 0007

Decision-making is a complex process requiring diverse abilities, making it an excellent framework for evaluating Large Language Models (LLMs). Researchers have examined LLMs' decision-making through the lens of Game Theory. However, existing evaluation mainly focus on two-player scenarios where an LLM competes against another. Additionally, previous benchmarks suffer from test set leakage due to their static design. We introduce GAMA($\gamma$)-Bench, a new framework for evaluating LLMs' Gaming Ability in Multi-Agent environments. It includes eight classical game theory scenarios and a dynamic scoring scheme specially designed to quantitatively assess LLMs' performance. $\gamma$-Bench allows flexible game settings and adapts the scoring system to different game parameters, enabling comprehensive evaluation of robustness, generalizability, and strategies for improvement. Our results indicate that GPT-3.5 demonstrates strong robustness but limited generalizability, which can be enhanced using methods like Chain-of-Thought. We also evaluate 13 LLMs from 6 model families, including GPT-3.5, GPT-4, Gemini, LLaMA-3.1, Mixtral, and Qwen-2. Gemini-1.5-Pro outperforms others, scoring of $69.8$ out of $100$, followed by LLaMA-3.1-70B ($65.9$) and Mixtral-8x22B ($62.4$). Our code and experimental results are publicly available at https://github.com/CUHK-ARISE/GAMABench.

ICML Conference 2025 Conference Paper

On the Resilience of LLM-Based Multi-Agent Collaboration with Faulty Agents

• Jen-tse Huang 0001
• Jiaxu Zhou
• Tailin Jin
• Xuhui Zhou
• Zixi Chen
• Wenxuan Wang 0001
• Youliang Yuan
• Michael R. Lyu

Large language model-based multi-agent systems have shown great abilities across various tasks due to the collaboration of expert agents, each focusing on a specific domain. However, the impact of clumsy or even malicious agents—those who frequently make errors in their tasks—on the overall performance of the system remains underexplored. This paper investigates: (1) What is the resilience of various system structures (e. g. , A$\rightarrow$B$\rightarrow$C, A$\leftrightarrow$B$\leftrightarrow$C) under faulty agents, on different downstream tasks? (2) How can we increase system resilience to defend against these agents? To simulate faulty agents, we propose two approaches—AutoTransform and AutoInject—which introduce mistakes into the agents’ responses. Experiments on four downstream tasks using six systems show that the "hierarchical" structure, i. e. , A$\rightarrow$(B$\leftrightarrow$C), exhibits superior resilience with the lowest performance drop of 5. 5%, compared to 10. 5% and 23. 7% of other two structures. To further improve resilience, we introduce (1) Challenger, that introduces a mechanism for each agent to challenge others’ outputs, and (2) Inspector, an additional agent to review and correct messages, recovering up to 96. 4% errors made by faulty agents. Our code and data are available at https: //github. com/CUHK-ARISE/MAS-Resilience.

NeurIPS Conference 2024 Conference Paper

Apathetic or Empathetic? Evaluating LLMs' Emotional Alignments with Humans

• Jen-Tse Huang
• Man H. Lam
• Eric J. Li
• Shujie Ren
• Wenxuan Wang
• Wenxiang Jiao
• Zhaopeng Tu
• Michael R. Lyu

Evaluating Large Language Models’ (LLMs) anthropomorphic capabilities has become increasingly important in contemporary discourse. Utilizing the emotion appraisal theory from psychology, we propose to evaluate the empathy ability of LLMs, i. e. , how their feelings change when presented with specific situations. After a careful and comprehensive survey, we collect a dataset containing over 400 situations that have proven effective in eliciting the eight emotions central to our study. Categorizing the situations into 36 factors, we conduct a human evaluation involving more than 1, 200 subjects worldwide. With the human evaluation results as references, our evaluation includes seven LLMs, covering both commercial and open-source models, including variations in model sizes, featuring the latest iterations, such as GPT-4, Mixtral-8x22B, and LLaMA-3. 1. We find that, despite several misalignments, LLMs can generally respond appropriately to certain situations. Nevertheless, they fall short in alignment with the emotional behaviors of human beings and cannot establish connections between similar situations. Our collected dataset of situations, the human evaluation results, and the code of our testing framework, i. e. , EmotionBench, are publicly available at https: //github. com/CUHK-ARISE/EmotionBench.

AAAI Conference 2024 Conference Paper

Curvature-Invariant Adversarial Attacks for 3D Point Clouds

• Jianping Zhang
• Wenwei Gu
• Yizhan Huang
• Zhihan Jiang
• Weibin Wu
• Michael R. Lyu

Imperceptibility is one of the crucial requirements for adversarial examples. Previous adversarial attacks on 3D point cloud recognition suffer from noticeable outliers, resulting in low imperceptibility. We think that the drawbacks can be alleviated via taking the local curvature of the point cloud into consideration. Existing approaches introduce the local geometry distance into the attack objective function. However, their definition of the local geometry distance neglects different perceptibility of distortions along different directions. In this paper, we aim to enhance the imperceptibility of adversarial attacks on 3D point cloud recognition by better preserving the local curvature of the original 3D point clouds. To this end, we propose the Curvature-Invariant Method (CIM), which directly regularizes the back-propagated gradient during the generation of adversarial point clouds based on two assumptions. Specifically, we first decompose the back-propagated gradients into the tangent plane and the normal direction. Then we directly reduce the gradient along the large curvature direction on the tangent plane and only keep the gradient along the negative normal direction. Comprehensive experimental comparisons confirm the superiority of our approach. Notably, our strategy can achieve 7.2% and 14.5% improvements in Hausdorff distance and Gaussian curvature measurements of the imperceptibility.

AAAI Conference 2024 Conference Paper

Improving the Adversarial Transferability of Vision Transformers with Virtual Dense Connection

• Jianping Zhang
• Yizhan Huang
• Zhuoer Xu
• Weibin Wu
• Michael R. Lyu

With the great achievement of vision transformers (ViTs), transformer-based approaches have become the new paradigm for solving various computer vision tasks. However, recent research shows that similar to convolutional neural networks (CNNs), ViTs are still vulnerable to adversarial attacks. To explore the shared deficiency of models with different structures, researchers begin to analyze the cross-structure adversarial transferability, which is still under-explored. Therefore, in this work, we focus on the ViT attacks to improve the cross-structure transferability between the transformer-based and convolution-based models. Previous studies fail to thoroughly investigate the influence of the components inside the ViT models on adversarial transferability, leading to inferior performance. To overcome the drawback, we launch a motivating study by linearly down-scaling the gradients of components inside the ViT models to analyze their influence on adversarial transferability. Based on the motivating study, we find that the gradient of the skip connection most influences transferability and believe that back-propagating gradients from deeper blocks can enhance transferability. Therefore, we propose the Virtual Dense Connection method (VDC). Specifically, without changing the forward pass, we first recompose the original network to add virtual dense connections. Then we back-propagate gradients of deeper Attention maps and Multi-layer Perceptron (MLP) blocks via virtual dense connections when generating adversarial samples. Extensive experiments confirm the superiority of our proposed method over the state-of-the-art baselines, with an 8.2% improvement in transferability between ViT models and a 7.2% improvement in cross-structure transferability from ViTs to CNNs.

ICLR Conference 2024 Conference Paper

On the Humanity of Conversational AI: Evaluating the Psychological Portrayal of LLMs

• Jen-tse Huang 0001
• Wenxuan Wang 0001
• Eric John Li
• Man Ho Lam
• Shujie Ren
• Youliang Yuan
• Wenxiang Jiao
• Zhaopeng Tu

Large Language Models (LLMs) have recently showcased their remarkable capacities, not only in natural language processing tasks but also across diverse domains such as clinical medicine, legal consultation, and education. LLMs become more than mere applications, evolving into assistants capable of addressing diverse user requests. This narrows the distinction between human beings and artificial intelligence agents, raising intriguing questions regarding the potential manifestation of personalities, temperaments, and emotions within LLMs. In this paper, we propose a framework, PsychoBench, for evaluating diverse psychological aspects of LLMs. Comprising thirteen scales commonly used in clinical psychology, PsychoBench further classifies these scales into four distinct categories: personality traits, interpersonal relationships, motivational tests, and emotional abilities. Our study examines five popular models, namely text-davinci-003, ChatGPT, GPT-4, LLaMA-2-7b, and LLaMA-2-13b. Additionally, we employ a jailbreak approach to bypass the safety alignment protocols and test the intrinsic natures of LLMs. We have made PsychoBench openly accessible via https://github.com/CUHK-ARISE/PsychoBench.

AAAI Conference 2023 Conference Paper

CDTA: A Cross-Domain Transfer-Based Attack with Contrastive Learning

• Zihan Li
• Weibin Wu
• Yuxin Su
• Zibin Zheng
• Michael R. Lyu

Despite the excellent performance, deep neural networks (DNNs) have been shown to be vulnerable to adversarial examples. Besides, these examples are often transferable among different models. In other words, the same adversarial example can fool multiple models with different architectures at the same time. Based on this property, many black-box transfer-based attack techniques have been developed. However, current transfer-based attacks generally focus on the cross-architecture setting, where the attacker has access to the training data of the target model, which is not guaranteed in realistic situations. In this paper, we design a Cross-Domain Transfer-Based Attack (CDTA), which works in the cross-domain scenario. In this setting, attackers have no information about the target model, such as its architecture and training data. Specifically, we propose a contrastive spectral training method to train a feature extractor on a source domain (e.g., ImageNet) and use it to craft adversarial examples on target domains (e.g., Oxford 102 Flower). Our method corrupts the semantic information of the benign image by scrambling the outputs of both the intermediate feature layers and the final layer of the feature extractor. We evaluate CDTA with 16 target deep models on four datasets with widely varying styles. The results confirm that, in terms of the attack success rate, our approach can consistently outperform the state-of-the-art baselines by an average of 11.45% across all target models. Our code is available at https://github.com/LiulietLee/CDTA.

IJCAI Conference 2023 Conference Paper

Towards Semantics- and Domain-Aware Adversarial Attacks

• Jianping Zhang
• Yung-Chieh Huang
• Weibin Wu
• Michael R. Lyu

Language models are known to be vulnerable to textual adversarial attacks, which add human-imperceptible perturbations to the input to mislead DNNs. It is thus imperative to devise effective attack algorithms to identify the deficiencies of DNNs before real-world deployment. However, existing word-level attacks have two major deficiencies: (1) They may change the semantics of the original sentence. (2) The generated adversarial sample can appear unnatural to humans due to the introduction of out-of-domain substitute words. In this paper, to address such drawbacks, we propose a semantics- and domain-aware word-level attack method. Specifically, we greedily replace the important words in a sentence with the ones suggested by a language model. The language model is trained to be semantics- and domain-aware via contrastive learning and in-domain pre-training. Furthermore, to balance the quality of adversarial examples and the attack success rate, we propose an iterative updating framework to optimize the contrastive learning loss and the in-domain pre-training loss in circular order. Comprehensive experimental comparisons confirm the superiority of our approach. Notably, compared with state-of-the-art benchmarks, our strategy can achieve over 3\% improvement in attack success rates and 9. 8\% improvement in the quality of adversarial examples.

AAAI Conference 2022 Conference Paper

Text Revision By On-the-Fly Representation Optimization

• Jingjing Li
• Zichao Li
• Tao Ge
• Irwin King
• Michael R. Lyu

Text revision refers to a family of natural language generation tasks, where the source and target sequences share moderate resemblance in surface form but differentiate in attributes, such as text formality and simplicity. Current state-of-theart methods formulate these tasks as sequence-to-sequence learning problems, which rely on large-scale parallel training corpus. In this paper, we present an iterative in-place editing approach for text revision, which requires no parallel data. In this approach, we simply fine-tune a pre-trained Transformer with masked language modeling and attribute classification. During inference, the editing at each iteration is realized by two-step span replacement. At the first step, the distributed representation of the text optimizes on the fly towards an attribute function. At the second step, a text span is masked and another new one is proposed conditioned on the optimized representation. The empirical experiments on two typical and important text revision tasks, text formalization and text simplification, show the effectiveness of our approach. It achieves competitive and even better performance than state-of-the-art supervised methods on text simplification, and gains better performance than strong unsupervised methods on text formalization. Our code and model are released at https: //github. com/jingjingli01/OREO.

AAAI Conference 2020 Conference Paper

Neuron Interaction Based Representation Composition for Neural Machine Translation

• Jian Li
• Xing Wang
• Baosong Yang
• Shuming Shi
• Michael R. Lyu
• Zhaopeng Tu

Recent NLP studies reveal that substantial linguistic information can be attributed to single neurons, i. e. , individual dimensions of the representation vectors. We hypothesize that modeling strong interactions among neurons helps to better capture complex information by composing the linguistic properties embedded in individual neurons. Starting from this intuition, we propose a novel approach to compose representations learned by different components in neural machine translation (e. g. , multi-layer networks or multihead attention), based on modeling strong interactions among neurons in the representation vectors. Specifically, we leverage bilinear pooling to model pairwise multiplicative interactions among individual neurons, and a low-rank approximation to make the model computationally feasible. We further propose extended bilinear pooling to incorporate first-order representations. Experiments on WMT14 English⇒German and English⇒French translation tasks show that our model consistently improves performances over the SOTA TRANS- FORMER baseline. Further analyses demonstrate that our approach indeed captures more syntactic and semantic information as expected.

AAAI Conference 2019 Conference Paper

DDFlow: Learning Optical Flow with Unlabeled Data Distillation

• Pengpeng Liu
• Irwin King
• Michael R. Lyu
• Jia Xu

We present DDFlow, a data distillation approach to learning optical flow estimation from unlabeled data. The approach distills reliable predictions from a teacher network, and uses these predictions as annotations to guide a student network to learn optical flow. Unlike existing work relying on handcrafted energy terms to handle occlusion, our approach is data-driven, and learns optical flow for occluded pixels. This enables us to train our model with a much simpler loss function, and achieve a much higher accuracy. We conduct a rigorous evaluation on the challenging Flying Chairs, MPI Sintel, KITTI 2012 and 2015 benchmarks, and show that our approach significantly outperforms all existing unsupervised learning methods, while running at real time.

AAAI Conference 2019 Conference Paper

Generating Distractors for Reading Comprehension Questions from Real Examinations

• Yifan Gao
• Lidong Bing
• Piji Li
• Irwin King
• Michael R. Lyu

We investigate the task of distractor generation for multiple choice reading comprehension questions from examinations. In contrast to all previous works, we do not aim at preparing words or short phrases distractors, instead, we endeavor to generate longer and semantic-rich distractors which are closer to distractors in real reading comprehension from examinations. Taking a reading comprehension article, a pair of question and its correct option as input, our goal is to generate several distractors which are somehow related to the answer, consistent with the semantic context of the question and have some trace in the article. We propose a hierarchical encoderdecoder framework with static and dynamic attention mechanisms to tackle this task. Specifically, the dynamic attention can combine sentence-level and word-level attention varying at each recurrent time step to generate a more readable sequence. The static attention is to modulate the dynamic attention not to focus on question irrelevant sentences or sentences which contribute to the correct option. Our proposed framework outperforms several strong baselines on the first prepared distractor generation dataset of real reading comprehension questions. For human evaluation, compared with those distractors generated by baselines, our generated distractors are more functional to confuse the annotators.

AAAI Conference 2019 Conference Paper

Title-Guided Encoding for Keyphrase Generation

• Wang Chen
• Yifan Gao
• Jiani Zhang
• Irwin King
• Michael R. Lyu

Keyphrase generation (KG) aims to generate a set of keyphrases given a document, which is a fundamental task in natural language processing (NLP). Most previous methods solve this problem in an extractive manner, while recently, several attempts are made under the generative setting using deep neural networks. However, the state-of-the-art generative methods simply treat the document title and the document main body equally, ignoring the leading role of the title to the overall document. To solve this problem, we introduce a new model called Title-Guided Network (TG-Net) for automatic keyphrase generation task based on the encoderdecoder architecture with two new features: (i) the title is additionally employed as a query-like input, and (ii) a titleguided encoder gathers the relevant information from the title to each word in the document. Experiments on a range of KG datasets demonstrate that our model outperforms the state-ofthe-art models with a large margin, especially for documents with either very low or very high title length ratios.

IJCAI Conference 2018 Conference Paper

A Generic Approach for Accelerating Stochastic Zeroth-Order Convex Optimization

• XiaoTian Yu
• Irwin King
• Michael R. Lyu
• Tianbao Yang

In this paper, we propose a generic approach for accelerating the convergence of existing algorithms to solve the problem of stochastic zeroth-order convex optimization (SZCO). Standard techniques for accelerating the convergence of stochastic zeroth-order algorithms are by exploring multiple functional evaluations (e. g. , two-point evaluations), or by exploiting global conditions of the problem (e. g. , smoothness and strong convexity). Nevertheless, these classic acceleration techniques are necessarily restricting the applicability of newly developed algorithms. The key of our proposed generic approach is to explore a local growth condition (or called local error bound condition) of the objective function in SZCO. The benefits of the proposed acceleration technique are: (i) it is applicable to both settings with one-point evaluation and two-point evaluations; (ii) it does not necessarily require strong convexity or smoothness condition of the objective function; (iii) it yields an improvement on convergence for a broad family of problems. Empirical studies in various settings demonstrate the effectiveness of the proposed acceleration approach.

IJCAI Conference 2018 Conference Paper

Code Completion with Neural Attention and Pointer Networks

• Jian Li
• Yue Wang
• Michael R. Lyu
• Irwin King

Intelligent code completion has become an essential research task to accelerate modern software development. To facilitate effective code completion for dynamically-typed programming languages, we apply neural language models by learning from large codebases, and develop a tailored attention mechanism for code completion. However, standard neural language models even with attention mechanism cannot correctly predict the out-of-vocabulary (OoV) words that restrict the code completion performance. In this paper, inspired by the prevalence of locally repeated terms in program source code, and the recently proposed pointer copy mechanism, we propose a pointer mixture network for better predicting OoV words in code completion. Based on the context, the pointer mixture network learns to either generate a within-vocabulary word through an RNN component, or regenerate an OoV word from local context through a pointer component. Experiments on two benchmarked datasets demonstrate the effectiveness of our attention mechanism and pointer mixture network on the code completion task.

UAI Conference 2018 Conference Paper

Pure Exploration of Multi-Armed Bandits with Heavy-Tailed Payoffs

• Xiaotian Yu
• Han Shao
• Michael R. Lyu
• Irwin King

Inspired by heavy-tailed distributions in practical scenarios, we investigate the problem on pure exploration of Multi-Armed Bandits (MAB) with heavy-tailed payoffs by breaking the assumption of payoffs with sub-Gaussian noises in MAB, and assuming that stochastic payoffs from bandits are with finite p-th moments, where p ∈ (1, +∞). The main contributions in this paper are three-fold. First, we technically analyze tail probabilities of empirical average and truncated empirical average (TEA) for estimating expected payoffs in sequential decisions with heavy-tailed noises via martingales. Second, we propose two effective bandit algorithms based on different prior information (i. e. , fixed confidence or fixed budget) for pure exploration of MAB generating payoffs with finite p-th moments. Third, we derive theoretical guarantees for the proposed two bandit algorithms, and demonstrate the effectiveness of two algorithms in pure exploration of MAB with heavy-tailed payoffs in synthetic data and real-world financial data.

AAAI Conference 2017 Conference Paper

CBRAP: Contextual Bandits with RAndom Projection

• XiaoTian Yu
• Michael R. Lyu
• Irwin King

Contextual bandits with linear payoffs, which are also known as linear bandits, provide a powerful alternative for solving practical problems of sequential decisions, e. g. , online advertisements. In the era of big data, contextual data usually tend to be high-dimensional, which leads to new challenges for traditional linear bandits mostly designed for the setting of low-dimensional contextual data. Due to the curse of dimensionality, there are two challenges in most of the current bandit algorithms: the first is high time-complexity; and the second is extreme large upper regret bounds with highdimensional data. In this paper, in order to attack the above two challenges effectively, we develop an algorithm of Contextual Bandits via RAndom Projection (CBRAP) in the setting of linear payoffs, which works especially for high-dimensional contextual data. The proposed CBRAP algorithm is time-efficient and flexible, because it enables players to choose an arm in a low-dimensional space, and relaxes the sparsity assumption of constant number of non-zero components in previous work. Besides, we prove an upper regret bound for the proposed algorithm, which is associated with reduced dimensions. By comparing with three benchmark algorithms, we demonstrate improved performance on cumulative payoffs of CBRAP during its sequential decisions on both synthetic and real-world datasets, as well as its superior time-efficiency.

UAI Conference 2017 Conference Paper

FROSH: FasteR Online Sketching Hashing

• Xixian Chen
• Irwin King
• Michael R. Lyu

Many hashing methods, especially those that are in the data-dependent category with good learning accuracy, are still inefficient when dealing with three critical problems in modern data analysis. First, data usually come in a streaming fashion, but most of the existing hashing methods are batch-based models. Second, when data become huge, the extensive computational time, large space requirement, and multiple passes to load the data into memory will be prohibitive. Third, data often lack sufficient label information. Although the recently proposed Online Sketching Hashing (OSH) is promising to alleviate all three issues mentioned above, its training procedure still suffers from a high time complexity. In this paper, we propose a FasteR Online Sketching Hashing (FROSH) method to make the training process faster. Compared with OSH, we leverage fast transform to sketch data more compactly. Particularly, we derive independent transformations to guarantee the sketching accuracy, and design a novel implementation to make such transformations applicable to online data sketching without increasing the space cost. We rigorously prove that our method can yield a comparable learning accuracy with a lower time complexity and an equal space cost compared with OSH. Finally, extensive experiments on synthetic and realworld datasets demonstrate the excellent performance of our method.

ICML Conference 2017 Conference Paper

Toward Efficient and Accurate Covariance Matrix Estimation on Compressed Data

• Xixian Chen
• Michael R. Lyu
• Irwin King

Estimating covariance matrices is a fundamental technique in various domains, most notably in machine learning and signal processing. To tackle the challenges of extensive communication costs, large storage capacity requirements, and high processing time complexity when handling massive high-dimensional and distributed data, we propose an efficient and accurate covariance matrix estimation method via data compression. In contrast to previous data-oblivious compression schemes, we leverage a data-aware weighted sampling method to construct low-dimensional data for such estimation. We rigorously prove that our proposed estimator is unbiased and requires smaller data to achieve the same accuracy with specially designed sampling distributions. Besides, we depict that the computational procedures in our algorithm are efficient. All achievements imply an improved tradeoff between the estimation accuracy and computational costs. Finally, the extensive experiments on synthetic and real-world datasets validate the superior property of our method and illustrate that it significantly outperforms the state-of-the-art algorithms.

TIST Journal 2016 Journal Article

A Unified Point-of-Interest Recommendation Framework in Location-Based Social Networks

• Chen Cheng
• Haiqin Yang
• Irwin King
• Michael R. Lyu

Location-based social networks (LBSNs), such as Gowalla, Facebook, Foursquare, Brightkite, and so on, have attracted millions of users to share their social friendship and their locations via check-ins in the past few years. Plenty of valuable information is accumulated based on the check-in behaviors, which makes it possible to learn users’ moving patterns as well as their preferences. In LBSNs, point-of-interest (POI) recommendation is one of the most significant tasks because it can help targeted users explore their surroundings as well as help third-party developers provide personalized services. Matrix factorization is a promising method for this task because it can capture users’ preferences to locations and is widely adopted in traditional recommender systems such as movie recommendation. However, the sparsity of the check-in data makes it difficult to capture users’ preferences accurately. Geographical influence can help alleviate this problem and have a large impact on the final recommendation result. By studying users’ moving patterns, we find that users tend to check in around several centers and different users have different numbers of centers. Based on this, we propose a Multi-center Gaussian Model (MGM) to capture this pattern via modeling the probability of a user’s check-in on a location. Moreover, users are usually more interested in the top 20 or even top 10 recommended POIs, which makes personalized ranking important in this task. From previous work, directly optimizing for pairwise ranking like Bayesian Personalized Ranking (BPR) achieves better performance in the top- k recommendation than directly using matrix matrix factorization that aims to minimize the point-wise rating error. To consider users’ preferences, geographical influence and personalized ranking, we propose a unified POI recommendation framework, which unifies all of them together. Specifically, we first fuse MGM with matrix factorization methods and further with BPR using two different approaches. We conduct experiments on Gowalla and Foursquare datasets, which are two large-scale real-world LBSN datasets publicly available online. The results on both datasets show that our unified POI recommendation framework can produce better performance.

IJCAI Conference 2016 Conference Paper

Modeling the Homophily Effect between Links and Communities for Overlapping Community Detection

• Hongyi Zhang
• Tong Zhao
• Irwin King
• Michael R. Lyu

Overlapping community detection has drawn much attention recently since it allows nodes in a network to have multiple community memberships. A standard framework to deal with overlapping community detection is Matrix Factorization (MF). Although all existing MF-based approaches use links as input to identify communities, the relationship between links and communities is still under-investigated. Most of the approaches only view links as consequences of communities (community-to-link) but fail to explore how nodes' community memberships can be represented by their linked neighbors (link-to-community). In this paper, we propose a Homophily-based Nonnegative Matrix Factorization (HNMF) to model both-sided relationships between links and communities. From the community-to-link perspective, we apply a preference-based pairwise function by assuming that nodes with common communities have a higher probability to build links than those without common communities. From the link-to-community perspective, we propose a new community representation learning with network embedding by assuming that linked nodes have similar community representations. We conduct experiments on several real-world networks and the results show that our HNMF model is able to find communities with better quality compared with state-of-the-art baselines.

IJCAI Conference 2015 Conference Paper

Exploiting k-Degree Locality to Improve Overlapping Community Detection

• Hongyi Zhang
• Michael R. Lyu
• Irwin King

Community detection is of crucial importance in understanding structures of complex networks. In many real-world networks, communities naturally overlap since a node usually has multiple community memberships. One popular technique to cope with overlapping community detection is Matrix Factorization (MF). However, existing MFbased models have ignored the fact that besides neighbors, “local non-neighbors” (e. g. , my friend’s friend but not my direct friend) are helpful when discovering communities. In this paper, we propose a Locality-based Non-negative Matrix Factorization (LNMF) model to refine a preference-based model by incorporating locality into learning objective. We define a subgraph called “k-degree local network” to set a boundary between local nonneighbors and other non-neighbors. By discriminately treating these two class of non-neighbors, our model is able to capture the process of community formation. We propose a fast sampling strategy within the stochastic gradient descent based learning algorithm. We compare our LNMF model with several baseline methods on various real-world networks, including large ones with ground-truth communities. Results show that our model outperforms state-of-the-art approaches.

JBHI Journal 2015 Journal Article

Extracting and Selecting Distinctive EEG Features for Efficient Epileptic Seizure Prediction

• Ning Wang
• Michael R. Lyu

This paper presents compact yet comprehensive feature representations for the electroencephalogram (EEG) signal to achieve efficient epileptic seizure prediction performance. The initial EEG feature vectors are formed by acquiring the dominant amplitude and frequency components on an epoch-by-epoch basis from the EEG signals. These extracted parameters can reveal the intrinsic EEG signal changes as well as the underlying stage transitions. To improve the efficacy of feature extraction, an elimination-based feature selection method has been applied on the initial feature vectors. This diminishes redundant and noisy points, providing each patient with a lower dimensional and independent final feature form. In this context, our study is distinguished from that of others currently prevailing. Usually, these latter approaches adopted feature extraction processes, which employed time-consuming high-dimensional parameter sets. Machine learning approaches that are considered as state of the art have been employed to build patient-specific binary classifiers that can divide the extracted feature parameters into preictal and interictal groups. Through out-of-sample evaluation on the intracranial EEG recordings provided by the publicly available Freiburg dataset, promising prediction performance has been attained. Specifically, we have achieved 98. 8% sensitivity results on the 19 patients included in our experiment, where only one of 83 seizures across all patients was not predicted. To make this investigation more comprehensive, we have conducted extensive comparative studies with other recently published competing approaches, in which the advantages of our method are highlighted.

UAI Conference 2015 Conference Paper

Fast Relative-Error Approximation Algorithm for Ridge Regression

• Shouyuan Chen
• Yang Liu 0003
• Michael R. Lyu
• Irwin King
• Shengyu Zhang 0002

Ridge regression is one of the most popular and effective regularized regression methods, and one case of particular interest is that the number of features p is much larger than the number of samples n, i. e. p n. In this case, the standard optimization algorithm for ridge regression computes the optimal solution x⇤ in O(n2 p + n3 ) time. In this paper, we propose a fast relativeerror approximation algorithm for ridge regression. More specifically, our algorithm outputs a solution x̃ satisfying kx̃ x⇤ k2  ✏kx⇤ k2 with high probability and runs in Õ(nnz(A) + n3 /✏2 ) time, where nnz(A) is the number of non-zero entries of matrix A. To the best of our knowledge, this is the first algorithm for ridge regression that runs in o(n2 p) time with provable relative-error approximation bound on the output vector. In addition, we analyze the risk inflation bound of our algorithm and apply our techniques to two generalizations of ridge regression, including multiple response ridge regression and a non-linear ridge regression problem. Finally, we show empirical results on both synthetic and real datasets.

IJCAI Conference 2015 Conference Paper

Training-Efficient Feature Map for Shift-Invariant Kernels

• Xixian Chen
• Haiqin Yang
• Irwin King
• Michael R. Lyu

Random feature map is popularly used to scale up kernel methods. However, employing a large number of mapped features to ensure an accurate approximation will still make the training time consuming. In this paper, we aim to improve the training efficiency of shift-invariant kernels by using fewer informative features without sacrificing precision. We propose a novel feature map method by extending Random Kitchen Sinks through fast datadependent subspace embedding to generate the desired features. More specifically, we describe two algorithms with different tradeoffs on the running speed and accuracy, and prove that O(l) features induced by them are able to perform as accurately as O(l2 ) features by other feature map methods. In addition, several experiments are conducted on the real-world datasets demonstrating the superiority of our proposed algorithms.

IJCAI Conference 2013 Conference Paper

A Unified Framework for Reputation Estimation in Online Rating Systems

• Guang Ling
• Irwin King
• Michael R. Lyu

Online rating systems are now ubiquitous due to the success of recommender systems. In such systems, users are allowed to rate the items (movies, songs, commodities) in a predefined range of values. The ratings collected can be used to infer users’ preferences as well as items’ intrinsic features, which are then matched to perform personalized recommendation. Most previous work focuses on improving the prediction accuracy or ranking capability. Little attention has been paid to the problem of spammers or low-reputed users in such systems. Spammers contaminate the rating system by assigning unreasonable scores to items, which may affect the accuracy of a recommender system. There are evidences supporting the existence of spammers in online rating systems. Reputation estimation methods can be employed to keep track of users’ reputation and detect spammers in such systems. In this paper, we propose a unified framework for computing the reputation score of a user, given only users’ ratings on items. We show that previously proposed reputation estimation methods can be captured as special cases of our framework. We propose a new low-rank matrix factorization based reputation estimation method and demonstrate its superior discrimination ability.

IJCAI Conference 2013 Conference Paper

Where You Like to Go Next: Successive Point-of-Interest Recommendation

• Chen Cheng
• Haiqin Yang
• Michael R. Lyu
• Irwin King

Personalized point-of-interest (POI) recommendation is a significant task in location-based social networks (LBSNs) as it can help provide better user experience as well as enable third-party services, e. g. , launching advertisements. To provide a good recommendation, various research has been conducted in the literature. However, pervious efforts mainly consider the “check-ins” in a whole and omit their temporal relation. They can only recommend POI globally and cannot know where a user would like to go tomorrow or in the next few days. In this paper, we consider the task of successive personalized POI recommendation in LB- SNs, which is a much harder task than standard personalized POI recommendation or prediction. To solve this task, we observe two prominent properties in the check-in sequence: personalized Markov chain and region localization. Hence, we propose a novel matrix factorization method, namely FPMC- LR, to embed the personalized Markov chains and the localized regions. Our proposed FPMC-LR not only exploits the personalized Markov chain in the check-in sequence, but also takes into account users’ movement constraint, i. e. , moving around a localized region. More importantly, utilizing the information of localized regions, we not only reduce the computation cost largely, but also discard the noisy information to boost recommendation. Results on two real-world LBSNs datasets demonstrate the merits of our proposed FPMC-LR.

AAAI Conference 2012 Conference Paper

A Data-Driven Approach to Question Subjectivity Identification in Community Question Answering

• Tom Chao Zhou
• Xiance Si
• Edward Y. Chang
• Irwin King
• Michael R. Lyu

Automatic Subjective Question Answering (ASQA), which aims at answering users’ subjective questions using summaries of multiple opinions, becomes increasingly important. One challenge of ASQA is that expected answers for subjective questions may not readily exist in the Web. The rising and popularity of Community Question Answering (CQA) sites, which provide platforms for people to post and answer questions, provides an alternative to ASQA. One important task of ASQA is question subjectivity identification, which identifies whether a user is asking a subjective question. Unfortunately, there has been little labeled training data available for this task. In this paper, we propose an approach to collect training data automatically by utilizing social signals in CQA sites without involving any manual labeling. Experimental results show that our data-driven approach achieves 9. 37% relative improvement over the supervised approach using manually labeled data, and achieves 5. 15% relative gain over a stateof-the-art semi-supervised approach. In addition, we propose several heuristic features for question subjectivity identification. By adding these features, we achieve 11. 23% relative improvement over word n-gram feature under the same experimental setting.

UAI Conference 2012 Conference Paper

Response Aware Model-Based Collaborative Filtering

• Guang Ling
• Haiqin Yang
• Michael R. Lyu
• Irwin King

Previous work on recommender systems mainly focus on fitting the ratings provided by users. However, the response patterns, i.e., some items are rated while others not, are generally ignored. We argue that failing to observe such response patterns can lead to biased parameter estimation and sub-optimal model performance. Although several pieces of work have tried to model users’ response patterns, they miss the effectiveness and interpretability of the successful matrix factorization collaborative filtering approaches. To bridge the gap, in this paper, we unify explicit response models and PMF to establish the Response Aware Probabilistic Matrix Factorization (RAPMF) framework. We show that RAPMF subsumes PMF as a special case. Empirically we demonstrate the merits of RAPMF from various aspects.

TIST Journal 2011 Journal Article

Learning to recommend with explicit and implicit social relations

• Hao Ma
• Irwin King
• Michael R. Lyu

Recommender systems have been well studied and developed, both in academia and in industry recently. However, traditional recommender systems assume that all the users are independent and identically distributed; this assumption ignores the connections among users, which is not consistent with the real-world observations where we always turn to our trusted friends for recommendations. Aiming at modeling recommender systems more accurately and realistically, we propose a novel probabilistic factor analysis framework which naturally fuses the users' tastes and their trusted friends' favors together. The proposed framework is quite general, and it can also be applied to pure user-item rating matrix even if we do not have explicit social trust information among users. In this framework, we coin the term social trust ensemble to represent the formulation of the social trust restrictions on the recommender systems. The complexity analysis indicates that our approach can be applied to very large datasets since it scales linearly with the number of observations, while the experimental results show that our method outperforms state-of-the-art approaches.

AAAI Conference 2011 Conference Paper

Learning to Suggest Questions in Online Forums

• Tom Zhou
• Chin-Yew Lin
• Irwin King
• Michael R. Lyu
• Young-In Song
• Yunbo Cao

Online forums contain interactive and semantically related discussions on various questions. Extracted question-answer archive is invaluable knowledge, which can be used to improve Question Answering services. In this paper, we address the problem of Question Suggestion, which targets at suggesting questions that are semantically related to a queried question. Existing bag-of-words approaches suffer from the shortcoming that they could not bridge the lexical chasm between semantically related questions. Therefore, we present a new framework to suggest questions, and propose the Topicenhanced Translation-based Language Model (TopicTRLM) which fuses both the lexical and latent semantic knowledge. Extensive experiments have been conducted with a large real world data set. Experimental results indicate our approach is very effective and outperforms other popular methods in several metrics.

ICML Conference 2010 Conference Paper

Online Learning for Group Lasso

• Haiqin Yang
• Zenglin Xu
• Irwin King
• Michael R. Lyu

ICML Conference 2010 Conference Paper

Simple and Efficient Multiple Kernel Learning by Group Lasso

• Zenglin Xu
• Rong Jin 0001
• Haiqin Yang
• Irwin King
• Michael R. Lyu

IJCAI Conference 2009 Conference Paper

• Zenglin Xu
• Rong Jin
• Michael R. Lyu
• Irwin King

We consider the problem of semi-supervised feature selection, where we are given a small amount of labeled examples and a large amount of unlabeled examples. Since a small number of labeled samples are usually insufficient for identifying the relevant features, the critical problem arising from semi-supervised feature selection is how to take advantage of the information underneath the unlabeled data. To address this problem, we propose a novel discriminative semi-supervised feature selection method based on the idea of manifold regularization. The proposed method selects features through maximizing the classification margin between different classes and simultaneously exploiting the geometry of the probability distribution that generates both labeled and unlabeled data. We formulate the proposed feature selection method into a convex-concave optimization problem, where the saddle point corresponds to the optimal solution. To find the optimal solution, the level method, a fairly recent optimization method, is employed. We also present a theoretic proof of the convergence rate for the application of the level method to our problem. Empirical evaluation on several benchmark data sets demonstrates the effectiveness of the proposed semi-supervised feature selection method.

ICML Conference 2009 Conference Paper

Non-monotonic feature selection

• Zenglin Xu
• Rong Jin 0001
• Jieping Ye
• Michael R. Lyu
• Irwin King

ICML Conference 2007 Conference Paper

Learning nonparametric kernel matrices from pairwise constraints

• Steven C. H. Hoi
• Rong Jin 0001
• Michael R. Lyu

Many kernel learning methods have to assume parametric forms for the target kernel functions, which significantly limits the capability of kernels in fitting diverse patterns. Some kernel learning methods assume the target kernel matrix to be a linear combination of parametric kernel matrices. This assumption again importantly limits the flexibility of the target kernel matrices. The key challenge with nonparametric kernel learning arises from the difficulty in linking the nonparametric kernels to the input patterns. In this paper, we resolve this problem by introducing the graph Laplacian of the observed data as a regularizer when optimizing the kernel matrix with respect to the pairwise constraints. We formulate the problem into Semi-Definite Programs (SDP), and propose an efficient algorithm to solve the SDP problem. The extensive evaluation on clustering with pairwise constraints shows that the proposed nonparametric kernel learning method is more effective than other state-of-the-art kernel learning techniques.

ICML Conference 2006 Conference Paper

Batch mode active learning and its application to medical image classification

• Steven C. H. Hoi
• Rong Jin 0001
• Jianke Zhu
• Michael R. Lyu

ICML Conference 2004 Conference Paper

Learning large margin classifiers locally and globally

• Kaizhu Huang
• Haiqin Yang
• Irwin King
• Michael R. Lyu

JMLR Journal 2004 Journal Article

The Minimum Error Minimax Probability Machine

• Kaizhu Huang
• Haiqin Yang
• Irwin King
• Michael R. Lyu
• Laiwan Chan

We construct a distribution-free Bayes optimal classifier called the Minimum Error Minimax Probability Machine (MEMPM) in a worst-case setting, i.e., under all possible choices of class-conditional densities with a given mean and covariance matrix. By assuming no specific distributions for the data, our model is thus distinguished from traditional Bayes optimal approaches, where an assumption on the data distribution is a must. This model is extended from the Minimax Probability Machine (MPM), a recently-proposed novel classifier, and is demonstrated to be the general case of MPM. Moreover, it includes another special case named the Biased Minimax Probability Machine, which is appropriate for handling biased classification. One appealing feature of MEMPM is that it contains an explicit performance indicator, i.e., a lower bound on the worst-case accuracy, which is shown to be tighter than that of MPM. We provide conditions under which the worst-case Bayes optimal classifier converges to the Bayes optimal classifier. We demonstrate how to apply a more general statistical framework to estimate model input parameters robustly. We also show how to extend our model to nonlinear classification by exploiting kernelization techniques. A series of experiments on both synthetic data sets and real world benchmark data sets validates our proposition and demonstrates the effectiveness of our model. [abs] [ pdf ]