Arrow Research search

Author name cluster

Ping Li

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

111 papers
2 author rows

Possible papers

111

JBHI Journal 2026 Journal Article

Bond-Aware Molecular Graph Learning With Multi-Graph Interleaved Message Passing

  • Honghao Wang
  • Hongrui Zhang
  • Acong Zhang
  • Junlei Tang
  • Ping Li

Graph neural networks (GNNs) have demonstrated remarkable capabilities in molecular property prediction. Existing approaches adopt GNNs by modeling molecules as homogeneous graphs. However, the bonds between atoms can be heterogeneous, whose characterization and role in molecular graph representation learning remain unexplored. To address the heterogeneity issue inherent in molecular graphs, in this work, we build the bond-centric graphs and propose a novel multi-graph learning model, which captures the bond heterogeneity via augmented bond graph view and bond coding for atom features. Different from conventional multi-view learning that focus on late-stage view fusion, our method integrates cross-graph information during the node representation learning phase. Towards this end, we introduce the interleaved message passing graph neural network ( IMPGNN ), allowing the messages passing across three views of the molecular graph. Moreover, we introduce a novel structure-aware pooling mechanims for graph representation, which yields up to 45. 7% gains over simple sum pooling. Comparative experiments on two standard molecular property prediction tasks reveal that our method surpasses all competing approaches (including multimodal models) on 75% of the evaluated benchmark datasets.

AAAI Conference 2026 Conference Paper

Discovering Decoupled Functional Modules in Large Language Models

  • Yanke Yu
  • Jin Li
  • Ying Sun
  • Ping Li
  • Zhefeng Wang
  • Yi Zheng

Understanding the internal functional organization of Large Language Models (LLMs) is crucial for improving their trustworthiness and performance. However, how LLMs organize different functions into modules remains highly unexplored. To bridge this gap, we formulate a function module discovery problem and propose an Unsupervised LLM Cross-layer MOdule Discovery (ULCMOD) framework that simultaneously disentangles the large set of neurons in the entire LLM into modules while discovering the topics of input samples related to these modules. Our framework introduces a novel objective function and an efficient Iterative Decoupling (IterD) algorithm. Extensive experiments show that our method discovers high-quality, disentangled modules that capture more meaningful semantic information and achieve superior performance in various downstream tasks. Moreover, our qualitative analysis reveals that the discovered modules show function comprehensiveness, function hierarchy, and clear function spatial arrangement within LLMs. Our work provides a novel tool for interpreting LLMs' function modules, filling a critical gap in LLMs' interpretability research.

EAAI Journal 2026 Journal Article

Elastic net twin support vector machine with Universum data and its safe screening rule

  • Hongmei Wang
  • Ping Li
  • Kun Jiang
  • Yitian Xu

Twin support vector machine with Universum data (UTSVM) is a powerful classification technique. It not only inherits the sophisticated structure of twin support vector machine but also incorporates prior information from Universum data. However, the adoption of l 1 penalty for slack variables in UTSVM suffers a geometric irrationality, impairing its ability to precisely represent the location of violated samples and thus partially degrading model performance. Therefore, we propose a novel elastic net twin support vector machine with Universum data (ENUTSVM) in this paper, which refines the geometric formulation by imposing elastic net penalty for slack variables. Furthermore, we theoretically derive a violation tolerance upper bound (VTUB) that quantitatively characterizes the relationship between the distances of violated samples and their corresponding slack variable differences. Additionally, to enhance the computational efficiency of ENUTSVM, we develop a safe screening rule (SSR-ENUTSVM) by combining variational inequalities and optimization conditions. We compare the proposed method with seven other competitive algorithms on four synthetic datasets and ten benchmark datasets. The experimental results and statistical tests confirm the superiority of our methods. Finally, we apply our method to an epileptic electroencephalogram (EEG) signal classification problem, which verifies its effectiveness in practical applications.

EAAI Journal 2026 Journal Article

Slimmable neural architecture design based on cross architecture and token distillation

  • Guhao Qiu
  • Zhihua Chen
  • Lei Dai
  • Ping Li
  • Bin Sheng

The manually designed neural networks have the drawbacks of requiring a large amount of training data and high computational costs. In this paper, we propose the masked autoencoder based lightweight network search algorithm which leverages the efficient channel search algorithm and specific distillation strategy to obtain the optimal architecture. During SuperNet training process, we design the cross-token distillation and cross-architecture strategy. Token distillation strategy is used to enforce the similar representation obtained from different masks in one image. Architecture distillation strategy is used to fully utilize the representation from the sampled subnetwork and use the feature maps from one image but the same token. In the subnetwork searching process, we further pretrain the selected network considering the component dependency. Comprehensive experiments verify that our proposed method is efficient and flexible than baseline self-supervised learning algorithm and structured pruning algorithms. For example, our method obtains 4. 4% improvement in TOP-1 metrics compared with the classic Masked Autoencoder algorithm designed for lightweight Transformer architecture with less than 10M parameter.

AAAI Conference 2026 Conference Paper

Toward Real-World High-Precision Image Matting and Segmentation

  • Haipeng Zhou
  • Zhaohu Xing
  • Hongqiu Wang
  • Jun Ma
  • Ping Li
  • Lei Zhu

High-precision scene parsing tasks, including image matting and dichotomous segmentation, aim to accurately predict masks with extremely fine details (such as hair). Most existing methods focus on salient, single foreground objects. While interactive methods allow for target adjustment, their class-agnostic design restricts generalization across different categories. Furthermore, the scarcity of high-quality annotation has led to a reliance on inharmonious synthetic data, resulting in poor generalization to real-world scenarios. To this end, we propose a Foreground Consistent Learning model, dubbed as FCLM, to address the aforementioned issues. Specifically, we first introduce a Depth-Aware Distillation strategy where we transfer the depth-related knowledge for better foreground representation. Considering the data dilemma, we term the processing of synthetic data as domain adaptation problem where we propose a domain-invariant learning strategy to focus on foreground learning. To support interactive prediction, we contribute an Object-Oriented Decoder that can receive both visual and language prompts to predict the referring target. Experimental results show that our method quantitatively and qualitatively outperforms state-of-the-art methods.

EAAI Journal 2025 Journal Article

Adaptive human in the loop system for identifying non-optimal states in natural product manufacturing process

  • Qilong Xue
  • Yang Yu
  • Shixin Cen
  • Yequan Yan
  • Jiping Pang
  • Ping Li
  • Yehan Hou
  • Lei Wang

In the extraction of natural products, the identification of non-optimal production states is pivotal for ensuring consistent product quality. Currently, there is a deficiency in online, automated detection methods. This study introduces an online machine vision strategy in a real industrial setting to maintain optimal production state. Specifically, the strategy incorporates an adaptive human in the loop deep learning approach to select high-value samples. This method achieves over 90 % accuracy with fewer training samples, effectively addressing the challenges posed by the low-value density characteristic of industrial data. Additionally, a convolutional neural networks-transformer framework is employed as a classifier for video data to meet the demands of time-series data. To enhance the efficiency of processing multiple video streams, we have implemented a knowledge distillation technique to lighten the model. Finally, this model has been deployed in an actual industrial environment for online monitoring of three extraction devices. The system encapsulates the expertise of engineers to standardize the criteria for assessing production states. This integration of innovative technologies ensures a more reliable and efficient extraction process, meeting the industry's need for consistent product quality.

NeurIPS Conference 2025 Conference Paper

Comparator-Adaptive $\Phi$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games

  • Soumita Hait
  • Ping Li
  • Haipeng Luo
  • Mengxiao Zhang

In the classic expert problem, $\Phi$-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation $\phi \in \Phi$. A recent work by Lu et al. , [2025] introduced an adaptive algorithm whose regret against a comparator $\phi$ depends on a certain sparsity-based complexity measure of $\phi$, recovering and interpolating optimal bounds for standard regret notions such as external, internal, and swap regret. In this work, we propose a general idea to achieve an even better comparator-adaptive $\Phi$-regret bound via much simpler algorithms compared to Lu et al. , [2025]. Specifically, we discover a prior distribution over all possible binary transformations and show that it suffices to achieve prior-dependent regret against these transformations. Then, we propose two concrete and efficient algorithms to achieve so, where the first one combines multiple copies of the kernelized Hedge algorithm of Farina et al. , [2022], and the second one combines multiple copies of a variant of the BM-reduction [Blum and Mansour, 2007]. To further showcase the power of our methods and the advantages over Lu et al. , [2025] besides the simplicity and better regret bounds, we also show that our second approach can be extended to the game setting to achieve accelerated and adaptive convergence rate to $\Phi$-equilibria for a class of general-sum games. When specified to the special case of correlated equilibria, our bound improves over the existing ones from Anagnostides et al. , [2022a, b].

TCS Journal 2025 Journal Article

Conflict-free chromatic index of trees

  • Shanshan Guo
  • Ethan Y.H. Li
  • Luyi Li
  • Ping Li

A graph G is called conflict-free k -edge-colorable if there exists an assignment of k colors to E ( G ) such that for every edge e ∈ E ( G ), there is a color that is assigned to exactly one edge among the closed neighborhood of e. The smallest k such that G is conflict-free k -edge-colorable is called the conflict-free chromatic index of G, denoted χ C F ′ ( G ). Dȩbski and Przybyło showed that 2 ≤ χ C F ′ ( T ) ≤ 3 for every tree T of size at least two. In this paper, we present an algorithm to determine the conflict-free chromatic index of a tree without vertices of degree 2, in time O ( | V ( T ) | ). This partially answers a question raised by Kamyczura, Meszka and Przybyło.

TIST Journal 2025 Journal Article

Denoising Structure against Adversarial Attacks on Graph Representation Learning

  • Na Chen
  • Ping Li
  • Jincheng Huang
  • Kai Zhang

Despite their excellent performance in graph representation learning, graph convolutional networks have been proved to be vulnerable to adversarial perturbations on the connectivity between nodes in an unnoticed manner. In this work, by looking into the impacts of adversarial attacks on graph data, we empirically find that the dominant edge-addition attacks generally increase the heterophily between connected nodes, which will fool the transductive inference models on node classification task. To defend against such attacks, we develop a Two-Stage Denoising (TSD) method that aims at removing possible malicious edges so as to mitigate the heterophily issue introduced by attacks. In particular, after a rough removal of the links that have quite low feature similarity, our method further spots the potentially heterophilous links by predicting node labels with a multi-view labeling consensus. This design is based on assumption that if the label predictions for the same node from two different views of a graph data are consistent, then we have a high chance to acquire the reliable labeling. The experiments demonstrate that by denoising a graph this way, the robustness of graph convolutional networks on node classification task is remarkably improved, compared to several strong competitive robust graph neural network models.

EAAI Journal 2025 Journal Article

Enhanced Cross-Dimensional Transformer for long-term wellhead pressure forecasting during hydraulic fracturing

  • Tao Zhang
  • Yuan Zhong
  • Jing Zhou
  • Ping Li
  • Jie Gong

Observational analysis of wellhead pressure variations is crucial for detecting fracturing fluid leakage and assessing wellbore integrity during fracturing operations. Accurately predicting multi-time step pressure changes is essential for enhancing oil and gas extraction efficiency while ensuring wellhead safety. This paper proposes the Enhanced Cross-Dimensional Transformer (ECformer), a time series model that predicts long-term wellhead pressure by capturing time-variable dependencies, the cross-dimensional information, in fracturing operation data. ECformer employs Patch Generation to segment local data regions, enabling the Cross-Dimensional Enhancement Structure to capture latent time-variable relationships. Patch Shuffle and Multi-Scale Fusion further refine temporal extraction and feature-level analysis at the patch scale, thereby enhancing prediction accuracy. Experimental results show that ECformer outperforms the newer Near Time Transformer (NTformer) and Patch Time Series Transformer (PatchTST) in long-term wellhead pressure prediction, reducing the Mean Squared Error (MSE) by 3. 5% and 33. 4% within 90 s and by 6. 6% and 38. 5% within 120 s about the average of multiple data sets. ECformer shows higher accuracy in long-step predictions, providing greater potential for future proactive risk prevention.

JBHI Journal 2025 Journal Article

Federated Pseudo Modality Generation for Incomplete Multi-Modal MRI Reconstruction

  • Yunlu Yan
  • Chun-Mei Feng
  • Yuexiang Li
  • Ping Li
  • Rick Siow Mong Goh
  • Baiying Lei
  • Weiming Wang
  • David Dagan Feng

While multi-modal learning has been widely used for MRI reconstruction, it relies on paired multi-modal data, which is difficult to acquire in real clinical scenarios. Especially in the federated setting, there is a common issue that several medical institutions suffer from missing modalities or even only have single-modal data. Therefore, it is infeasible to deploy a standard federated learning framework in such conditions. In this paper, we propose a novel communication-efficient federated learning framework (namely Fed-PMG) to address the missing modality challenge in federated multi-modal MRI reconstruction. Specifically, we utilize a pseudo modality generation mechanism to recover the missing modality for each single-modal client by sharing the distribution information of the amplitude spectrum in frequency space. However, the step of sharing the original amplitude spectrum leads to heavy communication costs. To reduce the communication cost, we introduce a clustering scheme to project the set of amplitude spectrum into a finite number of cluster centroids and share them among the clients. With such an elaborate design, our approach can effectively complete the missing modality within an acceptable communication cost. Extensive experimental results demonstrate that our proposed method can outperform state-of-the-art methods and reach a performance similar to the ideal scenario (i. e. , all clients have the full set of modalities).

ICLR Conference 2025 Conference Paper

GPromptShield: Elevating Resilience in Graph Prompt Tuning Against Adversarial Attacks

  • Shuhan Song
  • Ping Li
  • Ming Dun
  • Maolei Huang
  • Huawei Cao
  • Xiaochun Ye

The paradigm of ``pre-training and prompt-tuning", with its effectiveness and lightweight characteristics, has rapidly spread from the language field to the graph field. Several pioneering studies have designed specialized prompt functions for diverse downstream graph tasks based on various graph pre-training strategies. These prompts concentrate on the compatibility between the pre-training pretext and downstream graph tasks, aiming to bridge the gap between them. However, designing prompts blindly to adapt to downstream tasks based on this concept neglects crucial security issues. By conducting covert attacks on downstream graph data, we find that even when the downstream task data closely matches that of the pre-training tasks, it is still feasible to generate highly misleading prompts using simple deceptive techniques. In this paper, we shift the primary focus of graph prompts from compatibility to vulnerability issues in adversarial attack scenarios. We design a highly extensible shield defense system for the prompts, which enhances their robustness from two perspectives:Direct Handling and Indirect Amplification. When downstream graph data contains unreliable biases, the former directly combats invalid information by incorporating hybrid multi-defense prompts to the input graph's feature space, while the latter adopts a training strategy to bypass the invalid components and amplifies valid part. We provide a theoretical derivation that proves their feasibility, indicating that unbiased prompts exist under certain conditions on unreliable data. Extensive experiments across various scenarios of adversarial attacks (including adaptive and non-adaptive attacks) indicate that the prompts within our defense system exhibit enhanced resilience and superiority. This paper explores a new perspective in graph prompt learning, offering a novel option for robust prompt tuning in downstream tasks.

EAAI Journal 2025 Journal Article

Model-free output feedback optimal tracking control for two-dimensional batch processes

  • Huiyuan Shi
  • Jiayue Ma
  • Qiang Liu
  • Jinna Li
  • Xueying Jiang
  • Ping Li

To address the challenge of linear quadratic tracking for batch processes without taking into account the specifics regarding the system dynamics and the state observer, a two-dimensional off-policy model-free output feedback control method is proposed. Previous solutions have mostly failed to fully explore the historical input and output information of the system along time and batch dimensions, thereby constraining the flexibility and efficiency of the controller. However, the method proposed aims to reconstruct the state space by delving into these historical input and output data of the system. The correlation between the two-dimensional value function and the two-dimensional Q-function with output feedback characteristics is found, thereby revealing the corresponding two-dimensional Bellman equation. This method, through the use of reinforcement learning algorithms, can effectively learn the optimal control strategy without the need for prior knowledge of system dynamics. To this end, the proposed method not only converges faster but also has smaller errors, making it more suitable for complex and ever-changing industrial production processes in reality. This innovative research provides new ideas and methods for the design and optimization of control systems, which is expected to bring higher efficiency and more stable performance to industrial production. At last, simulation outcomes for the injection velocity process validate the suggested method's effectiveness.

IJCAI Conference 2025 Conference Paper

Temporal Consistency Constrained Transferable Adversarial Attacks with Background Mixup for Action Recognition

  • Ping Li
  • Jianan Ni
  • Bo Pang

Action recognition models using deep learning are vulnerable to adversarial examples, which are transferable across other models trained on the same data modality. Existing transferable attack methods face two major challenges: 1) they heavily rely on the assumption that the decision boundaries of the surrogate (a. k. a. , source) model and the target model are similar, which limits the adversarial transferability; and 2) their decision boundary difference makes the attack direction uncertain, which may result in the gradient oscillation, weakening the adversarial attack. This motivates us to propose a Background Mixup-induced Temporal Consistency (BMTC) attack method for action recognition. From the input transformation perspective, we design a model-agnostic background adversarial mixup module to reduce the surrogate-target model dependency. In particular, we randomly sample one video from each category and make its background frame, while selecting the background frame with the top attack ability for mixup with the clean frame by reinforcement learning. Moreover, to ensure an explicit attack direction, we leverage the background category as guidance for updating the gradient of adversarial example, and design a temporal gradient consistency loss, which strengthens the stability of the attack direction on subsequent frames. Empirical studies on two video datasets, i. e. , UCF101 and Kinetics-400, and one image dataset, i. e. , ImageNet, demonstrate that our method significantly boosts the transferability of adversarial examples across several action/image recognition models.

EAAI Journal 2025 Journal Article

The three-party evolutionary game of preannouncement strategies for platform's AI updates considering users' loyalties

  • Ping Li
  • Bin Wu
  • Na Wu

The platform adopts the preannouncement strategy to announce information related to AI updates in advance, the preannounce information may reshape the market expectations, thus affecting the supply and demand balance for two-sided users. To analyze the dynamic progress of different preannouncement strategy and explore the equilibrium outcomes, this paper considers three preannouncement strategies regarding AI updates: full, partial and no-preannouncement under consideration of users' loyalty or disloyalty, then building Hotelling game model to explore the optimal results of three players. We construct three-party evolutionary game model to describe the multi-period gaming behaviors, and obtain the possible ESS (evolutionary stable strategy) and related equilibrium conditions. The results show that the full preannouncement is not optimal stable strategy for platform, there exists ESS only when two-sided users are no-loyal with capability of switching platform. When the preannouncement investment is lower than two-sided users' expectations, platform should partially preannounce AI updates, but when the preannouncement investment is higher than bilateral users’ expectations, platform should avoid preannouncing AI updates.

ICLR Conference 2025 Conference Paper

Toward Generalizing Visual Brain Decoding to Unseen Subjects

  • Xiangtao Kong
  • Kexin Huang
  • Ping Li
  • Lei Zhang 0006

Visual brain decoding aims to decode visual information from human brain activities. Despite the great progress, one critical limitation of current brain decoding research lies in the lack of generalization capability to unseen subjects. Prior work typically focuses on decoding brain activity of individuals based on the observation that different subjects exhibit different brain activities, while it remains unclear whether brain decoding can be generalized to unseen subjects. This study aims to answer this question. We first consolidate an image-fMRI dataset consisting of stimulus-image and fMRI-response pairs, involving 177 subjects in the movie-viewing task of the Human Connectome Project (HCP). This dataset allows us to investigate the brain decoding performance with the increase of participants. We then present a learning paradigm that applies uniform processing across all subjects, instead of employing different network heads or tokenizers for individuals as in previous methods, so that we can accommodate a large number of subjects to explore the generalization capability across different subjects. A series of experiments are conducted and we have the following findings. First, the network exhibits clear generalization capabilities with the increase of training subjects. Second, the generalization capability is common to popular network architectures (MLP, CNN and Transformer). Third, the generalization performance is affected by the similarity between subjects. Our findings reveal the inherent similarities in brain activities across individuals. With the emergence of larger and more comprehensive datasets, it is possible to train a brain decoding foundation model in the future. Codes and models can be found at https://github.com/Xiangtaokong/TGBD}{https://github.com/Xiangtaokong/TGBD.

JMLR Journal 2024 Journal Article

Cluster-Adaptive Network A/B Testing: From Randomization to Estimation

  • Yang Liu
  • Yifan Zhou
  • Ping Li
  • Feifang Hu

The performance of A/B testing in both online and offline experimental settings hinges on mitigating network interference and achieving covariate balancing. These experiments often involve an observable network with identifiable clusters, and measurable cluster-level and individual-level attributes. Exploiting these inherent characteristics holds potential for refining experimental design and subsequent statistical analyses. In this article, we propose a novel cluster-adaptive network A/B testing procedure, which contains a cluster-adaptive randomization (CLAR) and a cluster-adjusted estimator (CAE) to facilitate the design of the experiment and enhance the performance of ATE estimation. The CLAR sequentially assigns clusters to minimize the Mahalanobis distance, which further leads to the balance of the cluster-level covariates and the within-cluster-averaged individual-level covariates. The cluster-adjusted estimator (CAE) is tailored to offset biases caused by network interference. The proposed procedure has the following two folds of the desirable properties. First, we show that the Malanobis distance calculated for the two levels of covariates is $O_p(m^{-1})$, where $m$ represents the number of clusters. This result justifies the simultaneous balance of the cluster-level and individual-level covariates. Under mild conditions, we derive the asymptotic normality of CAE and demonstrate the benefit of covariate balancing on improving the precision for estimating ATE. The proposed A/B testing procedure is easy to calculate, consistent, and achieves higher accuracy. Extensive numerical studies are conducted to demonstrate the finite sample property of the proposed network A/B testing procedure. [abs] [ pdf ][ bib ] &copy JMLR 2024. ( edit, beta )

ICML Conference 2024 Conference Paper

High-Order Contrastive Learning with Fine-grained Comparative Levels for Sparse Ordinal Tensor Completion

  • Yu Dai
  • Junchen Shen
  • Zijie Zhai
  • Danlin Liu
  • Jingyang Chen
  • Yu Sun
  • Ping Li
  • Jie Zhang

Contrastive learning is a powerful paradigm for representation learning with prominent success in computer vision and NLP, but how to extend its success to high-dimensional tensors remains a challenge. This is because tensor data often exhibit high-order mode-interactions that are hard to profile and with negative samples growing combinatorially faster than second-order contrastive learning; furthermore, many real-world tensors have ordinal entries that necessitate more delicate comparative levels. To solve the challenge, we propose High-Order Contrastive Tensor Completion (HOCTC), an innovative network to extend contrastive learning to sparse ordinal tensor data. HOCTC employs a novel attention-based strategy with query-expansion to capture high-order mode interactions even in case of very limited tokens, which transcends beyond second-order learning scenarios. Besides, it extends two-level comparisons (positive-vs-negative) to fine-grained contrast-levels using ordinal tensor entries as a natural guidance. Efficient sampling scheme is proposed to enforce such delicate comparative structures, generating comprehensive self-supervised signals for high-order representation learning. Extensive experiments show that HOCTC has promising results in sparse tensor completion in traffic/recommender applications.

UAI Conference 2024 Conference Paper

Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games

  • Yi Feng
  • Ping Li
  • Ioannis Panageas
  • Xiao Wang 0036

Last-iterate behaviors of learning algorithms in repeated two-player zero-sum games have been extensively studied due to their wide applications in machine learning and related tasks. Typical algorithms that exhibit the last-iterate convergence property include optimistic and extra-gradient methods. However, most existing results establish these properties under the assumption that the game is time-independent. Recently, (Feng et al. , 2023) studied the last-iterate behaviors of optimistic and extra-gradient methods in games with a time-varying payoff matrix, and proved that in an unconstrained periodic game, extra-gradient method converges to the equilibrium while optimistic method diverges. This finding challenges the conventional wisdom that these two methods are expected to behave similarly as they do in time-independent games. However, compared to unconstrained games, games with constrains are more common both in practical and theoretical studies. In this paper, we investigate the last-iterate behaviors of optimistic and extra-gradient methods in the constrained periodic games, demonstrating that similar separation results for last-iterate convergence also hold in this setting.

EAAI Journal 2024 Journal Article

Optimal tracking control of batch processes with time-invariant state delay: Adaptive Q-learning with two-dimensional state and control policy

  • Huiyuan Shi
  • Mengdi Lv
  • Xueying Jiang
  • Chengli Su
  • Ping Li

Given that conventional model-based control methods have some limitations for dynamic systems with unknown model parameters and existing reinforcement learning methods do not take batch and time delay information into account, a novel data-based adaptive Q-learning approach with two-dimensional (2D) state and control policy is proposed to address the optimal tracking control issue for batch processes with time-invariant state delay. The extended delay state space equation, value function, Q function and optimal performance index are initially presented along the time and batch directions. By examining the correlation between the 2D value function and the 2D Q function, a delay-dependent 2D Bellman equation is designed independent of the process model, which is solved to obtain the expression of the control law. Without requiring prior knowledge of the system, the optimal gain matrices of the control law are further learned by using the current and historical state, output error values and time delay information of the timewise and batchwise. It is feasible to achieve accelerated convergence and reduced errors between the optimal control gain matrices and the learning gain matrices, hence enhancing the tracking capabilities of the systems. At the same time, the unbiasedness and convergence of the given adaptive Q-learning approach are strictly proved. The effectiveness of the proposed algorithm is ultimately validated by simulation comparisons of injection molding, specifically regarding the convergence of control gains and the tracking of output.

EAAI Journal 2024 Journal Article

Robust asynchronous fuzzy predictive fault-tolerant tracking control for nonlinear multi-phase batch processes with time-varying reference trajectories

  • Hui Li
  • Shiqi Wang
  • Huiyuan Shi
  • Limin Wang
  • Chengli Su
  • Ping Li

For nonlinear multi-phase batch processes with time-varying reference trajectories, actuator faults and nonlinear characteristics, a robust asynchronous fuzzy predictive fault-tolerant tracking control method is proposed. First, considering an asynchronous switching situation between a state and a controller when switching occurs, an extended Takagi-Sugeno fuzzy switching model, including the matched and mismatched cases, is established. Then, a robust asynchronous fuzzy predictive fault-tolerant tracking controller is constructed based on the switching model by taking into account whether the model rules match the controller rules. Second, in order to ensure the stability of the system, the conditions for system stability indicated by the linear matrix inequality are provided using the relevant theories and methodologies. Next, the stability conditions are solved online, which can obtain the gains of control law in each phase, the minimum running time in the matched case, and the maximum running time in the mismatched case. By utilizing the maximum running duration allows the switching signal to be sent out in advance, preventing asynchronous switching situations and ensuring stable system operation. The simulation results finally demonstrate the viability and effectiveness of the developed controller.

ECAI Conference 2024 Conference Paper

TED: Accelerate Model Training by Internal Generalization

  • Jinying Xiao
  • Ping Li
  • Jie Nie

Large language models have demonstrated strong performance in recent years, but the high cost of training drives the need for efficient methods to compress dataset sizes. We propose TED pruning, a method that addresses the challenge of overfitting under high pruning ratios by quantifying the model’s ability to improve performance on pruned data while fitting retained data, known as Internal Generalization (IG). TED uses an optimization objective based on Internal Generalization Distance (IGD), measuring changes in IG before and after pruning to align with true generalization performance and achieve implicit regularization. The IGD optimization objective was verified to allow the model to achieve the smallest upper bound on generalization error. The impact of small mask fluctuations on IG is studied through masks and Taylor approximation, and fast estimation of IGD is enabled. In analyzing continuous training dynamics, the prior effect of IGD is validated, and a progressive pruning strategy is proposed. Experiments on image classification, natural language understanding, and large language model fine-tuning show TED achieves lossless performance with 60-70% of the data. Upon acceptance, our code will be made publicly available.

NeurIPS Conference 2024 Conference Paper

Voxel Proposal Network via Multi-Frame Knowledge Distillation for Semantic Scene Completion

  • Lubo Wang
  • Di Lin
  • Kairui Yang
  • Ruonan Liu
  • Qing Guo
  • Wuyuan Xie
  • Miaohui Wang
  • Lingyu Liang

Semantic scene completion is a difficult task that involves completing the geometry and semantics of a scene from point clouds in a large-scale environment. Many current methods use 3D/2D convolutions or attention mechanisms, but these have limitations in directly constructing geometry and accurately propagating features from related voxels, the completion likely fails while propagating features in a single pass without considering multiple potential pathways. And they are generally only suitable for static scenes and struggle to handle dynamic aspects. This paper introduces Voxel Proposal Network (VPNet) that completes scenes from 3D and Bird's-Eye-View (BEV) perspectives. It includes Confident Voxel Proposal based on voxel-wise coordinates to propose confident voxels with high reliability for completion. This method reconstructs the scene geometry and implicitly models the uncertainty of voxel-wise semantic labels by presenting multiple possibilities for voxels. VPNet employs Multi-Frame Knowledge Distillation based on the point clouds of multiple adjacent frames to accurately predict the voxel-wise labels by condensing various possibilities of voxel relationships. VPNet has shown superior performance and achieved state-of-the-art results on the SemanticKITTI and SemanticPOSS datasets.

NeurIPS Conference 2023 Conference Paper

$L_2$-Uniform Stability of Randomized Learning Algorithms: Sharper Generalization Bounds and Confidence Boosting

  • Xiaotong Yuan
  • Ping Li

Exponential generalization bounds with near-optimal rates have recently been established for uniformly stable algorithms~\citep{feldman2019high, bousquet2020sharper}. We seek to extend these best known high probability bounds from deterministic learning algorithms to the regime of randomized learning. One simple approach for achieving this goal is to define the stability for the expectation over the algorithm's randomness, which may result in sharper parameter but only leads to guarantees regarding the on-average generalization error. Another natural option is to consider the stability conditioned on the algorithm's randomness, which is way more stringent but may lead to generalization with high probability jointly over the randomness of sample and algorithm. The present paper addresses such a tension between these two alternatives and makes progress towards relaxing it inside a classic framework of confidence-boosting. To this end, we first introduce a novel concept of $L_2$-uniform stability that holds uniformly over data but in second-moment over the algorithm's randomness. Then as a core contribution of this work, we prove a strong exponential bound on the first-moment of generalization error under the notion of $L_2$-uniform stability. As an interesting consequence of the bound, we show that a bagging-based meta algorithm leads to near-optimal generalization with high probability jointly over the randomness of data and algorithm. We further substantialize these generic results to stochastic gradient descent (SGD) to derive sharper exponential bounds for convex or non-convex optimization with natural time-decaying learning rates, which have not been possible to prove with the existing stability-based generalization guarantees.

EAAI Journal 2023 Journal Article

A solar radiation intelligent forecasting framework based on feature selection and multivariable fuzzy time series

  • Yuyang Gao
  • Ping Li
  • Hufang Yang
  • Jianzhou Wang

Accurate solar radiation forecasting can effectively improve solar energy utilization efficiency and decrease the operational cost of solar photovoltaic power plants. However, some common forecasting methods have certain limitations, such as neglecting data fuzziness, meteorological factors, feature selection, and seasonal adjustment. Therefore, a solar radiation intelligent forecasting framework based on feature selection and multivariable fuzzy time series is proposed. Specifically, a combined fuzzy strategy is used to fuzzy the data, and an improved multi-objective optimization algorithm is proposed to search for the optimal parameters. A seasonal multivariable fuzzy time series is proposed to achieve multivariable inputs and seasonal adjustments. The experimental analysis, statistical test, and robustness analysis all verify the superiority of the proposed forecasting framework compared with competitive models. The MAPE values of the proposed forecasting framework for two regions are about 6% and 4%, respectively, which outperform some common basic models such as BPNN(about 11% and 9%), ELM(about 12% and 10%), LSTM(about 9% and 7%). The comparison analysis further indicates that the vital parts of the forecasting framework containing feature selection, seasonal adjustment, multi-objective optimization, and multivariable inputs can all have a positive influence on forecasting performance.

AAAI Conference 2023 Conference Paper

A Tale of Two Latent Flows: Learning Latent Space Normalizing Flow with Short-Run Langevin Flow for Approximate Inference

  • Jianwen Xie
  • Yaxuan Zhu
  • Yifei Xu
  • Dingcheng Li
  • Ping Li

We study a normalizing flow in the latent space of a top-down generator model, in which the normalizing flow model plays the role of the informative prior model of the generator. We propose to jointly learn the latent space normalizing flow prior model and the top-down generator model by a Markov chain Monte Carlo (MCMC)-based maximum likelihood algorithm, where a short-run Langevin sampling from the intractable posterior distribution is performed to infer the latent variables for each observed example, so that the parameters of the normalizing flow prior and the generator can be updated with the inferred latent variables. We show that, under the scenario of non-convergent short-run MCMC, the finite step Langevin dynamics is a flow-like approximate inference model and the learning objective actually follows the perturbation of the maximum likelihood estimation (MLE). We further point out that the learning framework seeks to (i) match the latent space normalizing flow and the aggregated posterior produced by the short-run Langevin flow, and (ii) bias the model from MLE such that the short-run Langevin flow inference is close to the true posterior. Empirical results of extensive experiments validate the effectiveness of the proposed latent space normalizing flow model in the tasks of image generation, image reconstruction, anomaly detection, supervised image inpainting and unsupervised image recovery.

TCS Journal 2023 Journal Article

An LP-based approximation algorithm for the generalized traveling salesman path problem

  • Jian Sun
  • Gregory Gutin
  • Ping Li
  • Peihao Shi
  • Xiaoyan Zhang

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = ( V, E, c ) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E, i. e. , c: E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure.

AAAI Conference 2023 Conference Paper

CoopInit: Initializing Generative Adversarial Networks via Cooperative Learning

  • Yang Zhao
  • Jianwen Xie
  • Ping Li

Numerous research efforts have been made to stabilize the training of the Generative Adversarial Networks (GANs), such as through regularization and architecture design. However, we identify the instability can also arise from the fragile balance at the early stage of adversarial learning. This paper proposes the CoopInit, a simple yet effective cooperative learning-based initialization strategy that can quickly learn a good starting point for GANs, with a very small computation overhead during training. The proposed algorithm consists of two learning stages: (i) Cooperative initialization stage: The discriminator of GAN is treated as an energy-based model (EBM) and is optimized via maximum likelihood estimation (MLE), with the help of the GAN's generator to provide synthetic data to approximate the learning gradients. The EBM also guides the MLE learning of the generator via MCMC teaching; (ii) Adversarial finalization stage: After a few iterations of initialization, the algorithm seamlessly transits to the regular mini-max adversarial training until convergence. The motivation is that the MLE-based initialization stage drives the model towards mode coverage, which is helpful in alleviating the issue of mode dropping during the adversarial learning stage. We demonstrate the effectiveness of the proposed approach on image generation and one-sided unpaired image-to-image translation tasks through extensive experiments.

AAAI Conference 2023 Conference Paper

Defending Backdoor Attacks on Vision Transformer via Patch Processing

  • Khoa D. Doan
  • Yingjie Lao
  • Peng Yang
  • Ping Li

Vision Transformers (ViTs) have a radically different architecture with significantly less inductive bias than Convolutional Neural Networks. Along with the improvement in performance, security and robustness of ViTs are also of great importance to study. In contrast to many recent works that exploit the robustness of ViTs against adversarial examples, this paper investigates a representative causative attack, i.e., backdoor. We first examine the vulnerability of ViTs against various backdoor attacks and find that ViTs are also quite vulnerable to existing attacks. However, we observe that the clean-data accuracy and backdoor attack success rate of ViTs respond distinctively to patch transformations before the positional encoding. Then, based on this finding, we propose an effective method for ViTs to defend both patch-based and blending-based trigger backdoor attacks via patch processing. The performances are evaluated on several benchmark datasets, including CIFAR10, GTSRB, and TinyImageNet, which show the proposedds defense is very successful in mitigating backdoor attacks for ViTs. To the best of our knowledge, this paper presents the first defensive strategy that utilizes a unique characteristic of ViTs against backdoor attacks.

IJCAI Conference 2023 Conference Paper

Detecting Adversarial Faces Using Only Real Face Self-Perturbations

  • Qian Wang
  • Yongqin Xian
  • Hefei Ling
  • Jinyuan Zhang
  • Xiaorui Lin
  • Ping Li
  • Jiazhong Chen
  • Ning Yu

Adversarial attacks aim to disturb the functionality of a target system by adding specific noise to the input samples, bringing potential threats to security and robustness when applied to facial recognition systems. Although existing defense techniques achieve high accuracy in detecting some specific adversarial faces (adv-faces), new attack methods especially GAN-based attacks with completely different noise patterns circumvent them and reach a higher attack success rate. Even worse, existing techniques require attack data before implementing the defense, making it impractical to defend newly emerging attacks that are unseen to defenders. In this paper, we investigate the intrinsic generality of adv-faces and propose to generate pseudo adv-faces by perturbing real faces with three heuristically designed noise patterns. We are the first to train an adv-face detector using only real faces and their self-perturbations, agnostic to victim facial recognition systems, and agnostic to unseen attacks. By regarding adv-faces as out-of-distribution data, we then naturally introduce a novel cascaded system for adv-face detection, which consists of training data self-perturbations, decision boundary regularization, and a max-pooling-based binary classifier focusing on abnormal local color aberrations. Experiments conducted on LFW and CelebA-HQ datasets with eight gradient-based and two GAN-based attacks validate that our method generalizes to a variety of unseen adversarial attacks.

IROS Conference 2023 Conference Paper

DMCL: Robot Autonomous Navigation via Depth Image Masked Contrastive Learning

  • Jiahao Jiang
  • Ping Li
  • Xudong Lv
  • Yuxiang Yang

Achieving high performance in deep reinforcement learning relies heavily on the ability to obtain good state representations from pixel inputs. However, learning an observation-space-to-action-space mapping from high-dimensional inputs is challenging in reinforcement learning, particularly when dealing with consecutive depth images as input states. In addition, we observe that the consecutive inputs of depth images are highly correlated for the autonomous navigation of a mobile robot, which inspires us to capture temporal correlations between consecutive inputs and infer scene change relationships. To this end, we propose a novel end-to-end robot vision navigation method dubbed DMCL, which obtains good spatial-temporal state representation via Depth image Masked Contrastive Learning. It reconstructs the latent representation from consecutive depth images masked in both spatial and temporal dimensions, resulting in a complete environment state representation. To obtain the optimal navigation policy, we leverage the Soft Actor-Critic reinforcement learning in conjunction with the above representation learning. Extensive experiments demonstrate that the proposed DMCL outperforms representative state-of-the-art methods. The source code will be made publicly available.

NeurIPS Conference 2023 Conference Paper

k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy

  • Chenglin Fan
  • Ping Li
  • Xiaoyun Li

In clustering algorithms, the choice of initial centers is crucial for the quality of the learned clusters. We propose a new initialization scheme for the $k$-median problem in the general metric space (e. g. , discrete space induced by graphs), based on the construction of metric embedding tree structure of the data. We propose a novel and efficient search algorithm, for good initial centers that can be used subsequently for the local search algorithm. The so-called HST initialization method can produce initial centers achieving lower error than those from another popular method $k$-median++, also with higher efficiency when $k$ is not too small. Our HST initialization can also be easily extended to the setting of differential privacy (DP) to generate private initial centers. We show that the error of applying DP local search followed by our private HST initialization improves previous results on the approximation error, and approaches the lower bound within a small factor. Experiments demonstrate the effectiveness of our proposed methods.

NeurIPS Conference 2023 Conference Paper

On the Last-iterate Convergence in Time-varying Zero-sum Games: Extra Gradient Succeeds where Optimism Fails

  • Yi Feng
  • Hu Fu
  • Qun Hu
  • Ping Li
  • Ioannis Panageas
  • Bo Peng
  • Xiao Wang

Last-iterate convergence has received extensive study in two player zero-sum games starting from bilinear, convex-concave up to settings that satisfy the MVI condition. Typical methods that exhibit last-iterate convergence for the aforementioned games include extra-gradient (EG) and optimistic gradient descent ascent (OGDA). However, all the established last-iterate convergence results hold for the restrictive setting where the underlying repeated game does not change over time. Recently, a line of research has focused on regret analysis of OGDA in time-varying games, i. e. , games where payoffs evolve with time; the last-iterate behavior of OGDA and EG in time-varying environments remains unclear though. In this paper, we study the last-iterate behavior of various algorithms in two types of unconstrained, time-varying, bilinear zero-sum games: periodic and convergent perturbed games. These models expand upon the usual repeated game formulation and incorporate external environmental factors, such as the seasonal effects on species competition and vanishing external noise. In periodic games, we prove that EG will converge while OGDA and momentum method will diverge. This is quite surprising, as to the best of our knowledge, it is the first result that indicates EG and OGDA have qualitatively different last-iterate behaviors and do not exhibit similar behavior. In convergent perturbed games, we prove all these algorithms converge as long as the game itself stabilizes with a faster rate than $1/t$.

NeurIPS Conference 2023 Conference Paper

On the Overlooked Structure of Stochastic Gradients

  • Zeke Xie
  • Qian-Yuan Tang
  • Mingming Sun
  • Ping Li

Stochastic gradients closely relate to both optimization and generalization of deep neural networks (DNNs). Some works attempted to explain the success of stochastic optimization for deep learning by the arguably heavy-tail properties of gradient noise, while other works presented theoretical and empirical evidence against the heavy-tail hypothesis on gradient noise. Unfortunately, formal statistical tests for analyzing the structure and heavy tails of stochastic gradients in deep learning are still under-explored. In this paper, we mainly make two contributions. First, we conduct formal statistical tests on the distribution of stochastic gradients and gradient noise across both parameters and iterations. Our statistical tests reveal that dimension-wise gradients usually exhibit power-law heavy tails, while iteration-wise gradients and stochastic gradient noise caused by minibatch training usually do not exhibit power-law heavy tails. Second, we further discover that the covariance spectra of stochastic gradients have the power-law structures overlooked by previous studies and present its theoretical implications for training of DNNs. While previous studies believed that the anisotropic structure of stochastic gradients matters to deep learning, they did not expect the gradient covariance can have such an elegant mathematical structure. Our work challenges the existing belief and provides novel insights on the structure of stochastic gradients in deep learning.

JMLR Journal 2023 Journal Article

Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation

  • Xiao-Tong Yuan
  • Ping Li

The stochastic proximal point (SPP) methods have gained recent attention for stochastic optimization, with strong convergence guarantees and superior robustness to the classic stochastic gradient descent (SGD) methods showcased at little to no cost of computational overhead added. In this article, we study a minibatch variant of SPP, namely M-SPP, for solving convex composite risk minimization problems. The core contribution is a set of novel excess risk bounds of M-SPP derived through the lens of algorithmic stability theory. Particularly under smoothness and quadratic growth conditions, we show that M-SPP with minibatch-size $n$ and iteration count $T$ enjoys an in-expectation fast rate of convergence consisting of an $\mathcal{O}\left(\frac{1}{T^2}\right)$ bias decaying term and an $\mathcal{O}\left(\frac{1}{nT}\right)$ variance decaying term. In the small-$n$-large-$T$ setting, this result substantially improves the best known results of SPP-type approaches by revealing the impact of noise level of model on convergence rate. In the complementary small-$T$-large-$n$ regime, we propose a two-phase extension of M-SPP to achieve comparable convergence rates. Additionally, we establish a deviation bound on the parameter estimation error of a sampling-without-replacement variant of M-SPP, which holds with high probability over the randomness of data while in expectation over the randomness of algorithm. Numerical evidences are provided to support our theoretical predictions when substantialized to Lasso and logistic regression models. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

NeurIPS Conference 2023 Conference Paper

Smooth Flipping Probability for Differential Private Sign Random Projection Methods

  • Ping Li
  • Xiaoyun Li

We develop a series of differential privacy (DP) algorithms from a family of random projection (RP) and sign random projection (SignRP) methods. We first show how to improve the previous DP-RP approach using the ``optimal Gaussian mechanism''. Then, we propose a series of DP-SignRP algorithms that leverage the robustness of the ``sign flipping probability'' of random projections. That is, given $x = \sum_{i=1}^p u_i w_{i}$ where $u$ is a $p$-dimensional data vector and $w$ is a symmetric random vector, $sign(x)$ only has a fairly small probability to be flipped if there is a small modification on data $u$, depending on the specific distribution of $w$. This robustness leads to our novel design of ``smooth flipping probability'' for SignRP-type algorithms with better utility than using the standard randomized response mechanism. Retrieval and classification experiments demonstrate that, among the presented DP-RP algorithms, \textbf{DP-SignOPORP} (where OPORP is an improvement over the celebrated count-sketch algorithms), performs the best in general. In the industrial practice, DP methods were not very popular for machine learning or search, largely because the performance typically would drop substantially if DP is applied. Since our proposed new DP algorithms have significantly improved the performance, it is anticipated that our work will motivate a wide adoption of DP in practice. Finally, we stress that, since our methods are applied to the original data (i. e. , feature vectors), the privacy of downstream tasks is naturally protected.

TCS Journal 2023 Journal Article

Structural diagnosability of hypercubes under the PMC and MM* models

  • Ping Li
  • Shurong Zhang
  • Xiaomin Hu
  • Weihua Yang

The fault diagnosability has played an important role in the reliability of the interconnection network. In a network, the states of any two adjacent vertices can usually affect each other, and the neighbor of a faulty vertex is more likely to become faulty. These motivate our study of fault diagnosability from the perspective of some structures instead of basing on individual faulty vertices. Therefore, we introduce a novel measure of diagnosability, called structural diagnosability. Given a specific structure H, the H-structure diagnosability of a network G, denoted by t s ( G; H ), is the maximum number of pairwise disjoint subnetworks H 1, H 2, …, H m in G, such that, for i = 1, 2, …, m, H i is isomorphic to H and when all vertices in H i are faulty, these vertices can be diagnosed correctly. In this paper, we will establish t s ( Q n; H ) for the n-dimensional hypercube Q n under the PMC model and MM* model, respectively, where H ∈ { K 1, 1, K 1, 2, K 1, 3, C 4 }.

TCS Journal 2023 Journal Article

Two-stage non-submodular maximization

  • Hong Chang
  • Jing Jin
  • Zhicheng Liu
  • Ping Li
  • Xiaoyan Zhang

The sheer size of modern datasets has led to an urgent need for summarization techniques that can identify representative elements of the data set. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which allows us to find nearly-optimal solutions in linear time. However, for many applications in practice, including experimental design and sparse Gaussian processes, the objective is in general not submodular. To solve these optimization problems, an important research method is to describe the characteristics of the non-submodular functions. The non-submodular function is a hot research topic in the study of nonlinear combinatorial optimizations. In this paper, we combine and generalize the curvature and the generic submodularity ratio to design an approximation algorithm for two-stage non-submodular maximization under a matroid constraint.

AAAI Conference 2022 Conference Paper

DeepAuth: A DNN Authentication Framework by Model-Unique and Fragile Signature Embedding

  • Yingjie Lao
  • Weijie Zhao
  • Peng Yang
  • Ping Li

Along with the evolution of deep neural networks (DNNs) in many real-world applications, the complexity of model building has also dramatically increased. It is thus vital to protect the intellectual property (IP) of the model builder and ensure the trustworthiness of the deployed models. Meanwhile, adversarial attacks on DNNs (e. g. , backdoor and poisoning attacks) that seek to inject malicious behaviors have been investigated recently, demanding a means for verifying the integrity of the deployed model to protect the users. In this paper, we present a novel DNN authentication framework Deep- Auth which embeds a unique and fragile signature to each protected DNN model. Our approach exploits sensitive key samples that are well crafted from the input space to latent space and then to logit space for producing signatures. After embedding, each model will respond distinctively to these key samples, which creates a model-unique signature as a strong tool for authentication and user identity. The signature embedding process is also designed to ensure the fragility of the signature, which can be used to detect malicious modifications such that an illegitimate user or an altered model should not have the intact signature. Extensive evaluations on various models over a wide range of datasets demonstrate the effectiveness and efficiency of the proposed DeepAuth.

AAAI Conference 2022 Conference Paper

Efficient Compact Bilinear Pooling via Kronecker Product

  • Tan Yu
  • Yunfeng Cai
  • Ping Li

Bilinear pooling has achieved excellent performance in finegrained recognition tasks. Nevertheless, high-dimensional bilinear features suffer from over-fitting and inefficiency. To alleviate these issues, compact bilinear pooling (CBP) methods were developed to generate low-dimensional features. Although the low-dimensional features from existing CBP methods enable high efficiency in subsequent classification, CBP methods themselves are inefficient. Thus, the inefficiency issue of the bilinear pooling is still unsolved. In this work, we propose an efficient compact bilinear pooling method to solve the inefficiency problem inherited in bilinear pooling thoroughly. It decomposes the huge-scale projection matrix into a two-level Kronecker product of several smallscale matrices. By exploiting the “vec trick” and the tensor modal product, we can obtain the compact bilinear feature through the decomposed projection matrices in a speedy manner. Systematic experiments on four public benchmarks using two backbones demonstrate the efficiency and effectiveness of the proposed method in fine-grained recognition.

NeurIPS Conference 2022 Conference Paper

Generative Status Estimation and Information Decoupling for Image Rain Removal

  • Di Lin
  • Xin Wang
  • Jia Shen
  • Renjie Zhang
  • Ruonan Liu
  • Miaohui Wang
  • Wuyuan Xie
  • Qing Guo

Image rain removal requires the accurate separation between the pixels of the rain streaks and object textures. But the confusing appearances of rains and objects lead to the misunderstanding of pixels, thus remaining the rain streaks or missing the object details in the result. In this paper, we propose SEIDNet equipped with the generative Status Estimation and Information Decoupling for rain removal. In the status estimation, we embed the pixel-wise statuses into the status space, where each status indicates a pixel of the rain or object. The status space allows sampling multiple statuses for a pixel, thus capturing the confusing rain or object. In the information decoupling, we respect the pixel-wise statuses, decoupling the appearance information of rain and object from the pixel. Based on the decoupled information, we construct the kernel space, where multiple kernels are sampled for the pixel to remove the rain and recover the object appearance. We evaluate SEIDNet on the public datasets, achieving state-of-the-art performances of image rain removal. The experimental results also demonstrate the generalization of SEIDNet, which can be easily extended to achieve state-of-the-art performances on other image restoration tasks (e. g. , snow, haze, and shadow removal).

AAAI Conference 2022 Conference Paper

Input-Specific Robustness Certification for Randomized Smoothing

  • Ruoxin Chen
  • Jie Li
  • Junchi Yan
  • Ping Li
  • Bin Sheng

Although randomized smoothing has demonstrated high certified robustness and superior scalability to other certified defenses, the high computational overhead of the robustness certification bottlenecks the practical applicability, as it depends heavily on the large sample approximation for estimating the confidence interval. In existing works, the sample size for the confidence interval is universally set and agnostic to the input for prediction. This Input-Agnostic Sampling (IAS) scheme may yield a poor Average Certified Radius (ACR)-runtime trade-off which calls for improvement. In this paper, we propose Input-Specific Sampling (ISS) acceleration to achieve the cost-effectiveness for robustness certification, in an adaptive way of reducing the sampling size based on the input characteristic. Furthermore, our method universally controls the certified radius decline from the ISS sample size reduction. The empirical results on CIFAR-10 and ImageNet show that ISS can speed up the certification by more than three times at a limited cost of 0. 05 certified radius. Meanwhile, ISS surpasses IAS on the average certified radius across the extensive hyperparameter settings. Specifically, ISS achieves ACR=0. 958 on ImageNet in 250 minutes, compared to ACR=0. 917 by IAS under the same condition. We release our code in https: //github. com/roy-ch/Input-Specific-Certification.

IJCAI Conference 2022 Conference Paper

Learning Cluster Causal Diagrams: An Information-Theoretic Approach

  • Xueyan Niu
  • Xiaoyun Li
  • Ping Li

Many real-world phenomena arise from causal relationships among a set of variables. As a powerful tool, Bayesian Network (BN) has been successful in describing high-dimensional distributions. However, the faithfulness condition, enforced in most BN learning algorithms, is violated in the settings where multiple variables synergistically affect the outcome (i. e. , with polyadic dependencies). Building upon recent development in cluster causal diagrams (C-DAGs), we initiate the formal study of learning C-DAGs from observational data to relax the faithfulness condition. We propose a new scoring function, the Clustering Information Criterion (CIC), based on information-theoretic measures that represent various complex interactions among variables. The CIC score also contains a penalization of the model complexity under the minimum description length principle. We further provide a searching strategy to learn structures of high scores. Experiments on both synthetic and real data support the effectiveness of the proposed method.

NeurIPS Conference 2022 Conference Paper

Marksman Backdoor: Backdoor Attacks with Arbitrary Target Class

  • Khoa D Doan
  • Yingjie Lao
  • Ping Li

In recent years, machine learning models have been shown to be vulnerable to backdoor attacks. Under such attacks, an adversary embeds a stealthy backdoor into the trained model such that the compromised models will behave normally on clean inputs but will misclassify according to the adversary's control on maliciously constructed input with a trigger. While these existing attacks are very effective, the adversary's capability is limited: given an input, these attacks can only cause the model to misclassify toward a single pre-defined or target class. In contrast, this paper exploits a novel backdoor attack with a much more powerful payload, denoted as Marksman, where the adversary can arbitrarily choose which target class the model will misclassify given any input during inference. To achieve this goal, we propose to represent the trigger function as a class-conditional generative model and to inject the backdoor in a constrained optimization framework, where the trigger function learns to generate an optimal trigger pattern to attack any target class at will while simultaneously embedding this generative backdoor into the trained model. Given the learned trigger-generation function, during inference, the adversary can specify an arbitrary backdoor attack target class, and an appropriate trigger causing the model to classify toward this target class is created accordingly. We show empirically that the proposed framework achieves high attack performance (e. g. , 100% attack success rates in several experiments) while preserving the clean-data performance in several benchmark datasets, including MNIST, CIFAR10, GTSRB, and TinyImageNet. The proposed Marksman backdoor attack can also easily bypass existing backdoor defenses that were originally designed against backdoor attacks with a single target class. Our work takes another significant step toward understanding the extensive risks of backdoor attacks in practice.

NeurIPS Conference 2022 Conference Paper

On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond

  • Xiaotong Yuan
  • Ping Li

The \FedProx~algorithm is a simple yet powerful distributed proximal point optimization method widely used for federated learning (FL) over heterogeneous data. Despite its popularity and remarkable success witnessed in practice, the theoretical understanding of FedProx is largely underinvestigated: the appealing convergence behavior of \FedProx~is so far characterized under certain non-standard and unrealistic dissimilarity assumptions of local functions, and the results are limited to smooth optimization problems. In order to remedy these deficiencies, we develop a novel local dissimilarity invariant convergence theory for \FedProx~and its minibatch stochastic extension through the lens of algorithmic stability. As a result, we contribute to derive several new and deeper insights into \FedProx~for non-convex federated optimization including: 1) convergence guarantees invariant to certain stringent local dissimilarity conditions; 2) convergence guarantees for non-smooth FL problems; and 3) linear speedup with respect to size of minibatch and number of sampled devices. Our theory for the first time reveals that local dissimilarity and smoothness are not must-have for \FedProx~to get favorable complexity bounds.

NeurIPS Conference 2022 Conference Paper

Private Graph All-Pairwise-Shortest-Path Distance Release with Improved Error Rate

  • Chenglin Fan
  • Ping Li
  • Xiaoyun Li

Releasing all pairwise shortest path (APSP) distances between vertices on general graphs under weight Differential Privacy (DP) is known as a challenging task. In previous work, to achieve DP with some fixed budget, with high probability the maximal absolute error among all published pairwise distances is roughly O(n) where n is the number of nodes. It was shown that this error could be reduced for some special graphs, which, however, is hard for general graphs. Therefore, whether the approximation error can be reduced to sublinear is posted as an interesting open problem. In this paper, we break the linear barrier on the distance approximation error of previous result, by proposing an algorithm that releases a constructed synthetic graph privately. Computing all pairwise distances on the constructed graph only introduces O(n^{1/2}) error in answering all pairwise shortest path distances for fixed privacy parameter. Our method is based on a novel graph diameter (link length) augmentation via constructing ``shortcuts'' for the paths. By adding a set of shortcut edges to the original graph, we show that any node pair has a shortest path with link length O(n^{1/2}). Then by adding noises with some positive mean to the edge weights, the new graph is differentially private and can be published to answer all pairwise shortest path distances with O(n^{1/2}) approximation error using standard APSP computation. Numerical examples are also provided. Additionally, we also consider the graph with small feedback vertex set number. A feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles, and the feedback vertex set number of a graph, k, is the size of a smallest feedback vertex set. We propose a DP algorithm with error rate O(k), which improves the error of general graphs provided k=o(n^{1/2}).

NeurIPS Conference 2022 Conference Paper

SignRFF: Sign Random Fourier Features

  • Xiaoyun Li
  • Ping Li

The industry practice has been moving to embedding based retrieval (EBR). For example, in many applications, the embedding vectors are trained by some form of two-tower models. During serving phase, candidates (embedding vectors) are retrieved according to the rankings of cosine similarities either exhaustively or by approximate near neighbor (ANN) search algorithms. For those applications, it is natural to apply ``sign random projections'' (SignRP) or variants, on the trained embedding vectors to facilitate efficient data storage and cosine distance computations. SignRP is also one of the standard indexing schemes for conducting approximate near neighbor search. In the literature, SignRP has been popular and, to an extent, becomes the default method for ``locality sensitive hashing'' (LSH). In this paper, we propose ``sign random Fourier features'' (SignRFF) as an alternative to SignRP. The original method of random Fourier features (RFF) is a standard technique for approximating the Gaussian kernel (as opposed to the linear cosine kernel), in the literature of large-scale machine learning. Basically, RFF applies a simple nonlinear transformation on the samples generated by random projections (RP). Thus, in the pipeline of EBR, it is straightforward to replace SignRP by SignRFF. This paper explains, in a principled manner, why it makes sense to do so. In this paper, a new analytical measure called \textbf{Ranking Efficiency (RE)} is developed, which in retrospect is closely related to the ``two-sample mean'' $t$-test statistic for binomial variables. RE provides a systematic and unified framework for comparing different LSH methods. We compare our proposed SignRP with SignRP, KLSH (kernel LSH), as well SQ-RFF (which is another 1-bit coding scheme for RFF). According to the RE expression, SignRFF consistently outperforms KLSH (for Gaussian kernel) and SQ-RFF. SignRFF also outperforms SignRP in the relatively high similarity region. The theoretical comparison results are consistent with our empirical findings. In addition, experiments are conducted to compare SignRFF with a wide range of data-dependent and deep learning based hashing methods and show the advantage of SignRFF with a sufficient number of hash bits.

AAAI Conference 2021 Conference Paper

A Blind Block Term Decomposition of High Order Tensors

  • Yunfeng Cai
  • Ping Li

Tensor decompositions have found many applications in signal processing, data mining, machine learning, etc. In particular, the block term decomposition (BTD), which is a generalization of CP decomposition and Tucker decomposition/HOSVD, has been successfully used for the compression and acceleration of neural networks. However, computing BTD is NP-hard, and optimization based methods usually suffer from slow convergence or even fail to converge, which limits the applications of BTD. This paper considers a “blind” block term decomposition (BBTD) of high order tensors, in which the block diagonal structure of the core tensor is unknown. Our contributions include: 1) We establish the necessary and sufficient conditions for the existence of BTD, characterize the condition when a BTD solves the BBTD problem, and show that the BBTD is unique under a “low rank” assumption. 2) We propose an algebraic method to compute the BBTD. This method transforms the problem of determining the block diagonal structure of the core tensor into a clustering problem of complex numbers, in polynomial time. And once the clustering problem is solved, the BBTD can be obtained via computing several matrix decompositions. Numerical results show that our method is able to compute the BBTD, even in the presence of noise to some extent, whereas optimization based methods (e. g. , MINF and NLS in TENSORLAB) may fail to converge.

NeurIPS Conference 2021 Conference Paper

A Comprehensively Tight Analysis of Gradient Descent for PCA

  • Zhiqiang Xu
  • Ping Li

We study the Riemannian gradient method for PCA on which a crucial fact is that despite the simplicity of the considered setting, i. e. , deterministic version of Krasulina's method, the convergence rate has not been well-understood yet. In this work, we provide a general tight analysis for the gap-dependent rate at $O(\frac{1}{\Delta}\log\frac{1}{\epsilon})$ that holds for any real symmetric matrix. More importantly, when the gap $\Delta$ is significantly smaller than the target accuracy $\epsilon$ on the objective sub-optimality of the final solution, the rate of this type is actually not tight any more, which calls for a worst-case rate. We further give the first worst-case analysis that achieves a rate of convergence at $O(\frac{1}{\epsilon}\log\frac{1}{\epsilon})$. The two analyses naturally roll out a comprehensively tight convergence rate at $O(\frac{1}{\max\{\Delta, \epsilon\}}\hskip-. 3em\log\frac{1}{\epsilon})$. Particularly, our gap-dependent analysis suggests a new promising learning rate for stochastic variance reduced PCA algorithms. Experiments are conducted to confirm our findings as well.

NeurIPS Conference 2021 Conference Paper

A Note on Sparse Generalized Eigenvalue Problem

  • Yunfeng Cai
  • Guanhua Fang
  • Ping Li

The sparse generalized eigenvalue problem (SGEP) aims to find the leading eigenvector with sparsity structure. SGEP plays an important role in statistical learning and has wide applications including, but not limited to, sparse principal component analysis, sparse canonical correlation analysis and sparse Fisher discriminant analysis, etc. Due to the sparsity constraint, the solution of SGEP entails interesting properties from both numerical and statistical perspectives. In this paper, we provide a detailed sensitivity analysis for SGEP and establish the rate-optimal perturbation bound under the sparse setting. Specifically, we show that the bound is related to the perturbation/noise level and the recovery of the true support of the leading eigenvector as well. We also investigate the estimator of SGEP via imposing a non-convex regularization. Such estimator can achieve the optimal error rate and can recover the sparsity structure as well. Extensive numerical experiments corroborate our theoretical findings via using alternating direction method of multipliers (ADMM)-based computational method.

NeurIPS Conference 2021 Conference Paper

Backdoor Attack with Imperceptible Input and Latent Modification

  • Khoa Doan
  • Yingjie Lao
  • Ping Li

Recent studies have shown that deep neural networks (DNN) are vulnerable to various adversarial attacks. In particular, an adversary can inject a stealthy backdoor into a model such that the compromised model will behave normally without the presence of the trigger. Techniques for generating backdoor images that are visually imperceptible from clean images have also been developed recently, which further enhance the stealthiness of the backdoor attacks from the input space. Along with the development of attacks, defense against backdoor attacks is also evolving. Many existing countermeasures found that backdoor tends to leave tangible footprints in the latent or feature space, which can be utilized to mitigate backdoor attacks. In this paper, we extend the concept of imperceptible backdoor from the input space to the latent representation, which significantly improves the effectiveness against the existing defense mechanisms, especially those relying on the distinguishability between clean inputs and backdoor inputs in latent space. In the proposed framework, the trigger function will learn to manipulate the input by injecting imperceptible input noise while matching the latent representations of the clean and manipulated inputs via a Wasserstein-based regularization of the corresponding empirical distributions. We formulate such an objective as a non-convex and constrained optimization problem and solve the problem with an efficient stochastic alternating optimization procedure. We name the proposed backdoor attack as Wasserstein Backdoor (WB), which achieves a high attack success rate while being stealthy from both the input and latent spaces, as tested in several benchmark datasets, including MNIST, CIFAR10, GTSRB, and TinyImagenet.

AAAI Conference 2021 Conference Paper

Fast and Compact Bilinear Pooling by Shifted Random Maclaurin

  • Tan Yu
  • Xiaoyun Li
  • Ping Li

Bilinear pooling has achieved an excellent performance in many computer vision tasks. However, the high-dimension features from bilinear pooling can sometimes be inefficient and prone to over-fitting. Random Maclaurin (RM) is a widely used GPU-friendly approximation method to reduce the dimensionality of bilinear features. However, to achieve good performance, huge projection matrices are usually required in practice, making it extremely costly in computation and memory. In this paper, we propose a Shifted Random Maclaurin (SRM) strategy for fast and compact bilinear pooling. With merely negligible extra computational cost, the proposed SRM provides an estimator with a provably smaller variance than RM, which benefits accurate kernel approximation and thus the learning performance. Using a small projection matrix, the proposed SRM achieves a comparable estimation performance as RM based on a large projection matrix, and thus considerably boosts the efficiency. Furthermore, we upgrade the proposed SRM to SRM+ to further improve the efficiency and make the compact bilinear pooling compatible with fast matrix normalization. Fast and Compact Bilinear Network (FCBN) built upon the proposed SRM+ is devised, achieving an end-to-end training. Systematic experiments conducted on four public datasets demonstrate the effectiveness and efficiency of the proposed FCBN.

AAAI Conference 2021 Conference Paper

Learning Energy-Based Model with Variational Auto-Encoder as Amortized Sampler

  • Jianwen Xie
  • Zilong Zheng
  • Ping Li

Due to the intractable partition function, training energybased models (EBMs) by maximum likelihood requires Markov chain Monte Carlo (MCMC) sampling to approximate the gradient of the Kullback-Leibler divergence between data and model distributions. However, it is non-trivial to sample from an EBM because of the difficulty of mixing between modes. In this paper, we propose to learn a variational auto-encoder (VAE) to initialize the finite-step MCMC, such as Langevin dynamics that is derived from the energy function, for efficient amortized sampling of the EBM. With these amortized MCMC samples, the EBM can be trained by maximum likelihood, which follows an “analysis by synthesis” scheme; while the VAE learns from these MCMC samples via variational Bayes. We call this joint training algorithm the variational MCMC teaching, in which the VAE chases the EBM toward data distribution. We interpret the learning algorithm as a dynamic alternating projection in the context of information geometry. Our proposed models can generate samples comparable to GANs and EBMs. Additionally, we demonstrate that our model can learn effective probabilistic distribution toward supervised conditional learning tasks.

NeurIPS Conference 2021 Conference Paper

Learning Generative Vision Transformer with Energy-Based Latent Space for Saliency Prediction

  • Jing Zhang
  • Jianwen Xie
  • Nick Barnes
  • Ping Li

Vision transformer networks have shown superiority in many computer vision tasks. In this paper, we take a step further by proposing a novel generative vision transformer with latent variables following an informative energy-based prior for salient object detection. Both the vision transformer network and the energy-based prior model are jointly trained via Markov chain Monte Carlo-based maximum likelihood estimation, in which the sampling from the intractable posterior and prior distributions of the latent variables are performed by Langevin dynamics. Further, with the generative vision transformer, we can easily obtain a pixel-wise uncertainty map from an image, which indicates the model confidence in predicting saliency from the image. Different from the existing generative models which define the prior distribution of the latent variables as a simple isotropic Gaussian distribution, our model uses an energy-based informative prior which can be more expressive to capture the latent space of the data. We apply the proposed framework to both RGB and RGB-D salient object detection tasks. Extensive experimental results show that our framework can achieve not only accurate saliency predictions but also meaningful uncertainty maps that are consistent with the human perception.

NeurIPS Conference 2021 Conference Paper

Mitigating Forgetting in Online Continual Learning with Neuron Calibration

  • Haiyan Yin
  • Peng Yang
  • Ping Li

Inspired by human intelligence, the research on online continual learning aims to push the limits of the machine learning models to constantly learn from sequentially encountered tasks, with the data from each task being observed in an online fashion. Though recent studies have achieved remarkable progress in improving the online continual learning performance empowered by the deep neural networks-based models, many of today's approaches still suffer a lot from catastrophic forgetting, a persistent challenge for continual learning. In this paper, we present a novel method which attempts to mitigate catastrophic forgetting in online continual learning from a new perspective, i. e. , neuron calibration. In particular, we model the neurons in the deep neural networks-based models as calibrated units under a general formulation. Then we formalize a learning framework to effectively train the calibrated model, where neuron calibration could give ubiquitous benefit to balance the stability and plasticity of online continual learning algorithms through influencing both their forward inference path and backward optimization path. Our proposed formulation for neuron calibration is lightweight and applicable to general feed-forward neural networks-based models. We perform extensive experiments to evaluate our method on four benchmark continual learning datasets. The results show that neuron calibration plays a vital role in improving online continual learning performance and our method could substantially improve the state-of-the-art performance on all~the~evaluated~datasets.

JMLR Journal 2021 Journal Article

On the Riemannian Search for Eigenvector Computation

  • Zhiqiang Xu
  • Ping Li

Eigenvector computation is central to numerical algebra and often critical to many data analysis tasks nowadays. Most research on this problem has been focusing on projection methods like power iterations, such that this category of algorithms can achieve both optimal convergence rates and cheap per-iteration costs. In contrast, search methods belonging to another main category are less understood in this respect. In this work, we consider the leading eigenvector computation as a non-convex optimization problem on the (generalized) Stiefel manifold and covers the cases for both standard and generalized eigenvectors. It is shown that the inexact Riemannian gradient method induced by the shift-and-invert preconditioning is guaranteed to converge to one of the ground-truth eigenvectors at an optimal rate, e.g., $O(\sqrt{\kappa_{\mathbf{B}}\frac{\lambda_{1}}{\lambda_{1}-\lambda_{p+1}}}\log\frac{1}{\epsilon})$ for a pair of real symmetric matrices $(\mathbf{A},\mathbf{B})$ with $\mathbf{B}$ being positive definite, where $\lambda_{i}$ represents the $i$-th largest generalized eigenvalue of the matrix pair, $p$ is the multiplicity of $\lambda_{1}$, and $\kappa_{\mathbf{B}}$ stands for the condition number of $\mathbf{B}$. The standard eigenvector computation is recovered by setting $\mathbf{B}$ to an identity matrix. Our analysis reduces the dependence on the eigengap, making it the first Riemannian eigensolver that achieves the optimal rate. Experiments demonstrate that the proposed search method is able to deliver significantly better performance than projection methods by taking advantages of step-size schemes. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

ICRA Conference 2021 Conference Paper

Point Cloud Segmentation via Edge-fused Local Graph Learning

  • Mengtao Han
  • Yaochen Li
  • Liangyu Zuo
  • Qiao Li
  • Chi Zhang 0020
  • Yuanqi Su
  • Ping Li

Traditional convolution for capturing local structures and relationships remains a key technical limit in 3D semantic segmentation, which neglects the certain influence of the adjacent points on the central point in the disordered local point clouds. In this paper, we propose a novel joint-edge graph convolution neural network (JEGCN), which can extract the dynamic features of each local area and transfer the edge information between the vertex pairs to the adjacent vertices. In the proposed graph convolution module, the adjacent vertices are selected with high classification confidence which can guide the central vertex, and then reweight these vertices. Considering the lack of texture features in 3D point clouds, we incorporate 2D image features to adjacent feature propagation to effectively extract the local and global features of point clouds. The experimental results based on ScanNet and S3DIS datasets demonstrate the effectiveness of the proposed method.

NeurIPS Conference 2021 Conference Paper

Rate-Optimal Subspace Estimation on Random Graphs

  • Zhixin Zhou
  • Fan Zhou
  • Ping Li
  • Cun-Hui Zhang

We study the theory of random bipartite graph whose adjacency matrix is generated according to a connectivity matrix $M$. We consider the bipartite graph to be sparse, i. e. , the entries of $M$ are upper bounded by certain sparsity parameter. We show that the performance of estimating the connectivity matrix $M$ depends on the sparsity of the graph. We focus on two measurement of performance of estimation: the error of estimating $M$ and the error of estimating the column space of $M$. In the first case, we consider the operator norm and Frobenius norm of the difference between the estimation and the true connectivity matrix. In the second case, the performance will be measured by the difference between the estimated projection matrix and the true projection matrix in operator norm and Frobenius norm. We will show that the estimators we propose achieve the minimax optimal rate.

AAAI Conference 2021 Conference Paper

Rejection Sampling for Weighted Jaccard Similarity Revisited

  • Xiaoyun Li
  • Ping Li

Efficiently1 computing the weighted Jaccard similarity has become an active research topic in machine learning and theory. For sparse data, the standard technique is based on the consistent weighed sampling (CWS). For dense data, however, methods based on rejection sampling (RS) can be much more efficient. Nevertheless, existing RS methods are still slow for practical purposes. In this paper, we propose to improve RS by a strategy, which we call efficient rejection sampling (ERS), based on “early stopping + densification”. We analyze the statistical property of ERS and provide experimental results to compare ERS with RS and other algorithms for hashing weighted Jaccard. The results demonstrate that ERS significantly improves the existing methods for estimating the weighted Jaccard similarity in relatively dense data.

AAAI Conference 2020 Conference Paper

Distributed Primal-Dual Optimization for Online Multi-Task Learning

  • Peng Yang
  • Ping Li

Conventional online multi-task learning algorithms suffer from two critical limitations: 1) Heavy communication caused by delivering high velocity of sequential data to a central machine; 2) Expensive runtime complexity for building task relatedness. To address these issues, in this paper we consider a setting where multiple tasks are geographically located in different places, where one task can synchronize data with others to leverage knowledge of related tasks. Specifically, we propose an adaptive primal-dual algorithm, which not only captures task-specific noise in adversarial learning but also carries out a projection-free update with runtime efficiency. Moreover, our model is well-suited to decentralized periodic-connected tasks as it allows the energy-starved or bandwidth-constraint tasks to postpone the update. Theoretical results demonstrate the convergence guarantee of our distributed algorithm with an optimal regret. Empirical results confirm that the proposed model is highly effective on various real-world datasets.

AAAI Conference 2020 Conference Paper

IVFS: Simple and Efficient Feature Selection for High Dimensional Topology Preservation

  • Xiaoyun Li
  • Chenxi Wu
  • Ping Li

Feature selection is an important tool to deal with high dimensional data. In unsupervised case, many popular algorithms aim at maintaining the structure of the original data. In this paper, we propose a simple and effective feature selection algorithm to enhance sample similarity preservation through a new perspective, topology preservation, which is represented by persistent diagrams from the context of computational topology. This method is designed upon a unified feature selection framework called IVFS, which is inspired by random subset method. The scheme is flexible and can handle cases where the problem is analytically intractable. The proposed algorithm is able to well preserve the pairwise distances, as well as topological patterns, of the full data. We demonstrate that our algorithm can provide satisfactory performance under a sharp sub-sampling rate, which supports ef- ficient implementation of our proposed method to large scale datasets. Extensive experiments validate the effectiveness of the proposed feature selection scheme.

AAAI Conference 2020 Conference Paper

Meta-CoTGAN: A Meta Cooperative Training Paradigm for Improving Adversarial Text Generation

  • Haiyan Yin
  • Dingcheng Li
  • Xu Li
  • Ping Li

Training generative models that can generate high-quality text with sufficient diversity is an important open problem for Natural Language Generation (NLG) community. Recently, generative adversarial models have been applied extensively on text generation tasks, where the adversarially trained generators alleviate the exposure bias experienced by conventional maximum likelihood approaches and result in promising generation quality. However, due to the notorious defect of mode collapse for adversarial training, the adversarially trained generators face a quality-diversity trade-off, i. e. , the generator models tend to sacrifice generation diversity severely for increasing generation quality. In this paper, we propose a novel approach which aims to improve the performance of adversarial text generation via efficiently decelerating mode collapse of the adversarial training. To this end, we introduce a cooperative training paradigm, where a language model is cooperatively trained with the generator and we utilize the language model to efficiently shape the data distribution of the generator against mode collapse. Moreover, instead of engaging the cooperative update for the generator in a principled way, we formulate a meta learning mechanism, where the cooperative update to the generator serves as a high level meta task, with an intuition of ensuring the parameters of the generator after the adversarial update would stay resistant against mode collapse. In the experiment, we demonstrate our proposed approach can efficiently slow down the pace of mode collapse for the adversarial text generators. Overall, our proposed method is able to outperform the baseline approaches with significant margins in terms of both generation quality and diversity in the testified domains.

JMLR Journal 2020 Journal Article

On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond

  • Xiao-Tong Yuan
  • Ping Li

The DANE algorithm is an approximate Newton method popularly used for communication-efficient distributed machine learning. Reasons for the interest in DANE include scalability and efficiency. Convergence of DANE, however, can be tricky; its appealing convergence rate is only rigorous for quadratic objective function, and for more general convex functions the known results are no stronger than those of the classic first-order methods. To remedy these drawbacks, we propose in this article some new alternatives of DANE which are more suitable for analysis. We first introduce a simple variant of DANE equipped with backtracking line search, for which global asymptotic convergence and sharper local non-asymptotic convergence guarantees can be proved for both quadratic and non-quadratic strongly convex functions. Then we propose a heavy-ball method to accelerate the convergence of DANE, showing that the near-tight local rate of convergence can be established for strongly convex functions, and with proper modification of the algorithm about the same result applies globally to linear prediction models. Numerical evidence is provided to confirm the theoretical and practical advantages of our methods. [abs] [ pdf ][ bib ] &copy JMLR 2020. ( edit, beta )

NeurIPS Conference 2020 Conference Paper

Optimal Prediction of the Number of Unseen Species with Multiplicity

  • Yi Hao
  • Ping Li

Based on a sample of size $n$, we consider estimating the number of symbols that appear at least $\mu$ times in an independent sample of size $a \cdot n$, where $a$ is a given parameter. This formulation includes, as a special case, the well-known problem of inferring the number of unseen species introduced by [Fisher et al. ] in 1943 and considered by many others. Of considerable interest in this line of works is the largest $a$ for which the quantity can be accurately predicted. We completely resolve this problem by determining the limit of estimation to be $a \approx (\log n)/\mu$, with both lower and upper bounds matching up to constant factors. For the particular case of $\mu = 1$, this implies the recent result by [Orlitsky et al. ] on the unseen species problem. Experimental evaluations show that the proposed estimator performs exceptionally well in practice. Furthermore, the estimator is a simple linear combination of symbols' empirical counts, and hence linear-time computable.

NeurIPS Conference 2020 Conference Paper

RANet: Region Attention Network for Semantic Segmentation

  • Dingguo Shen
  • Yuanfeng Ji
  • Ping Li
  • Yi Wang
  • Di Lin

Recent semantic segmentation methods model the relationship between pixels to construct the contextual representations. In this paper, we introduce the \emph{Region Attention Network} (RANet), a novel attention network for modeling the relationship between object regions. RANet divides the image into object regions, where we select representative information. In contrast to the previous methods, RANet configures the information pathways between the pixels in different regions, enabling the region interaction to exchange the regional context for enhancing all of the pixels in the image. We train the construction of object regions, the selection of the representative regional contents, the configuration of information pathways and the context exchange between pixels, jointly, to improve the segmentation accuracy. We extensively evaluate our method on the challenging segmentation benchmarks, demonstrating that RANet effectively helps to achieve the state-of-the-art results.

NeurIPS Conference 2020 Conference Paper

Ratio Trace Formulation of Wasserstein Discriminant Analysis

  • Hexuan Liu
  • Yunfeng Cai
  • You-Lin Chen
  • Ping Li

We reformulate the Wasserstein Discriminant Analysis (WDA) as a ratio trace problem and present an eigensolver-based algorithm to compute the discriminative subspace of WDA. This new formulation, along with the proposed algorithm, can be served as an efficient and more stable alternative to the original trace ratio formulation and its gradient-based algorithm. We provide a rigorous convergence analysis for the proposed algorithm under the self-consistent field framework, which is crucial but missing in the literature. As an application, we combine WDA with low-dimensional clustering techniques, such as K-means, to perform subspace clustering. Numerical experiments on real datasets show promising results of the ratio trace formulation of WDA in both classification and clustering tasks.

NeurIPS Conference 2020 Conference Paper

Thunder: a Fast Coordinate Selection Solver for Sparse Learning

  • Shaogang Ren
  • Weijie Zhao
  • Ping Li

L1 regularization has been broadly employed to pursue model sparsity. Despite the non-smoothness, people have developed efficient algorithms by leveraging the sparsity and convexity of the problems. In this paper, we propose a novel active incremental approach to further improve the efficiency of the solvers. We show that our method performs well even when the existing methods fail due to the low sparseness or high solution accuracy request. Theoretical analysis and experimental results on synthetic and real-world data sets validate the advantages of the method.

NeurIPS Conference 2020 Conference Paper

Towards Better Generalization of Adaptive Gradient Methods

  • Yingxue Zhou
  • Belhal Karimi
  • Jinxing Yu
  • Zhiqiang Xu
  • Ping Li

Adaptive gradient methods such as AdaGrad, RMSprop and Adam have been optimizers of choice for deep learning due to their fast training speed. However, it was recently observed that their generalization performance is often worse than that of SGD for over-parameterized neural networks. While new algorithms such as AdaBound, SWAT, and Padam were proposed to improve the situation, the provided analyses are only committed to optimization bounds for the training objective, leaving critical generalization capacity unexplored. To close this gap, we propose \textit{\textbf{S}table \textbf{A}daptive \textbf{G}radient \textbf{D}escent} (\textsc{SAGD}) for nonconvex optimization which leverages differential privacy to boost the generalization performance of adaptive gradient methods. Theoretical analyses show that \textsc{SAGD} has high-probability convergence to a population stationary point. We further conduct experiments on various popular deep learning tasks and models. Experimental results illustrate that \textsc{SAGD} is empirically competitive and often better than baselines.

JMLR Journal 2020 Journal Article

Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data

  • Martin Slawski
  • Emanuel Ben-David
  • Ping Li

A tacit assumption in linear regression is that (response, predictor)-pairs correspond to identical observational units. A series of recent works have studied scenarios in which this assumption is violated under terms such as “Unlabeled Sensing and “Regression with Unknown Permutation”. In this paper, we study the setup of multiple response variables and a notion of mismatches that generalizes permutations in order to allow for missing matches as well as for one-to-many matches. A two-stage method is proposed under the assumption that most pairs are correctly matched. In the first stage, the regression parameter is estimated by handling mismatches as contaminations, and subsequently the generalized permutation is estimated by a basic variant of matching. The approach is both computationally convenient and equipped with favorable statistical guarantees. Specifically, it is shown that the conditions for permutation recovery become considerably less stringent as the number of responses $m$ per observation increase. Particularly, for $m = \Omega(\log n)$, the required signal-to-noise ratio no longer depends on the sample size $n$. Numerical results on synthetic and real data are presented to support the main findings of our analysis. [abs] [ pdf ][ bib ] &copy JMLR 2020. ( edit, beta )

IJCAI Conference 2019 Conference Paper

Coreference Aware Representation Learning for Neural Named Entity Recognition

  • Zeyu Dai
  • Hongliang Fei
  • Ping Li

Recent neural network models have achieved state-of-the-art performance on the task of named entity recognition (NER). However, previous neural network models typically treat the input sentences as a linear sequence of words but ignore rich structural information, such as the coreference relations among non-adjacent words, phrases or entities. In this paper, we propose a novel approach to learn coreference-aware word representations for the NER task at the document level. In particular, we enrich the well-known neural architecture ``CNN-BiLSTM-CRF'' with a coreference layer on top of the BiLSTM layer to incorporate coreferential relations. Furthermore, we introduce the coreference regularization to ensure the coreferential entities to share similar representations and consistent predictions within the same coreference cluster. Our proposed model achieves new state-of-the-art performance on two NER benchmarks: CoNLL-2003 and OntoNotes v5. 0. More importantly, we demonstrate that our framework does not rely on gold coreference knowledge, and can still work well even when the coreferential relations are generated by a third-party toolkit.

AAAI Conference 2019 Conference Paper

Cycle-SUM: Cycle-Consistent Adversarial LSTM Networks for Unsupervised Video Summarization

  • Li Yuan
  • Francis EH Tay
  • Ping Li
  • Li Zhou
  • Jiashi Feng

In this paper, we present a novel unsupervised video summarization model that requires no manual annotation. The proposed model termed Cycle-SUM adopts a new cycleconsistent adversarial LSTM architecture that can effectively maximize the information preserving and compactness of the summary video. It consists of a frame selector and a cycle-consistent learning based evaluator. The selector is a bi-direction LSTM network that learns video representations that embed the long-range relationships among video frames. The evaluator defines a learnable information preserving metric between original video and summary video and “supervises” the selector to identify the most informative frames to form the summary video. In particular, the evaluator is composed of two generative adversarial networks (GANs), in which the forward GAN is learned to reconstruct original video from summary video while the backward GAN learns to invert the processing. The consistency between the output of such cycle learning is adopted as the information preserving metric for video summarization. We demonstrate the close relation between mutual information maximization and such cycle learning procedure. Experiments on two video summarization benchmark datasets validate the state-of-theart performance and superiority of the Cycle-SUM model over previous baselines.

NeurIPS Conference 2019 Conference Paper

Generalization Error Analysis of Quantized Compressive Learning

  • Xiaoyun Li
  • Ping Li

Compressive learning is an effective method to deal with very high dimensional datasets by applying learning algorithms in a randomly projected lower dimensional space. In this paper, we consider the learning problem where the projected data is further compressed by scalar quantization, which is called quantized compressive learning. Generalization error bounds are derived for three models: nearest neighbor (NN) classifier, linear classifier and least squares regression. Besides studying finite sample setting, our asymptotic analysis shows that the inner product estimators have deep connection with NN and linear classification problem through the variance of their debiased counterparts. By analyzing the extra error term brought by quantization, our results provide useful implications to the choice of quantizers in applications involving different learning tasks. Empirical study is also conducted to validate our theoretical findings.

AAAI Conference 2019 Conference Paper

Multi-Agent Discussion Mechanism for Natural Language Generation

  • Xu Li
  • Mingming Sun
  • Ping Li

We introduce the discussion mechanism into the multiagent communicating encoder-decoder architecture for Natural Language Generation (NLG) tasks and prove that by applying the discussion mechanism, the communication between agents becomes more effective. Generally speaking, an encoder-decoder architecture predicts target-sequence word by word in several time steps. At each time step of prediction, agents with the discussion mechanism predict the target word after several discussion steps. In the first step of discussion, agents make their choice independently and express their decision to other agents. In the next discussion step, agents collect other agents’ decision to update their own decisions, then express the updated decisions to others again. After several iterations, the agents make their final decision based on a well-communicated situation. The benefit of the discussion mechanism is that multiple encoders can be designed as different structures to fit the specified input or to fetch different representations of inputs. We train and evaluate the discussion mechanism on Table to Text Generation, Text Summarization and Image Caption tasks, respectively. Our empirical results demonstrate that the proposed multi-agent discussion mechanism is helpful for maximizing the utility of the communication between agents.

NeurIPS Conference 2019 Conference Paper

Möbius Transformation for Fast Inner Product Search on Graph

  • Zhixin Zhou
  • Shulong Tan
  • Zhaozhuo Xu
  • Ping Li

We present a fast search on graph algorithm for Maximum Inner Product Search (MIPS). This optimization problem is challenging since traditional Approximate Nearest Neighbor (ANN) search methods may not perform efficiently in the non-metric similarity measure. Our proposed method is based on the property that Möbius transformation introduces an isomorphism between a subgraph of l^2-Delaunay graph and Delaunay graph for inner product. Under this observation, we propose a simple but novel graph indexing and searching algorithm to find the optimal solution with the largest inner product with the query. Experiments show our approach leads to significant improvements compared to existing methods.

NeurIPS Conference 2019 Conference Paper

Outlier Detection and Robust PCA Using a Convex Measure of Innovation

  • Mostafa Rahmani
  • Ping Li

This paper presents a provable and strong algorithm, termed Innovation Search (iSearch), to robust Principal Component Analysis (PCA) and outlier detection. An outlier by definition is a data point which does not participate in forming a low dimensional structure with a large number of data points in the data. In other word, an outlier carries some innovation with respect to most of the other data points. iSearch ranks the data points based on their values of innovation. A convex optimization problem is proposed whose optimal value is used as our measure of innovation. We derive analytical performance guarantees for the proposed robust PCA method under different models for the distribution of the outliers including randomly distributed outliers, clustered outliers, and linearly dependent outliers. Moreover, it is shown that iSearch provably recovers the span of the inliers when the inliers lie in a union of subspaces. In the challenging scenarios in which the outliers are close to each other or they are close to the span of the inliers, iSearch is shown to outperform most of the existing methods.

NeurIPS Conference 2019 Conference Paper

Random Projections with Asymmetric Quantization

  • Xiaoyun Li
  • Ping Li

The method of random projection has been a popular tool for data compression, similarity search, and machine learning. In many practical scenarios, applying quantization on randomly projected data could be very helpful to further reduce storage cost and facilitate more efficient retrievals, while only suffering from little loss in accuracy. In real-world applications, however, data collected from different sources may be quantized under different schemes, which calls for a need to study the asymmetric quantization problem. In this paper, we investigate the cosine similarity estimators derived in such setting under the Lloyd-Max (LM) quantization scheme. We thoroughly analyze the biases and variances of a series of estimators including the basic simple estimators, their normalized versions, and their debiased versions. Furthermore, by studying the monotonicity, we show that the expectation of proposed estimators increases with the true cosine similarity, on a broader family of stair-shaped quantizers. Experiments on nearest neighbor search justify the theory and illustrate the effectiveness of our proposed estimators.

NeurIPS Conference 2019 Conference Paper

Re-randomized Densification for One Permutation Hashing and Bin-wise Consistent Weighted Sampling

  • Ping Li
  • Xiaoyun Li
  • Cun-Hui Zhang

Jaccard similarity is widely used as a distance measure in many machine learning and search applications. Typically, hashing methods are essential for the use of Jaccard similarity to be practical in large-scale settings. For hashing binary (0/1) data, the idea of one permutation hashing (OPH) with densification significantly accelerates traditional minwise hashing algorithms while providing unbiased and accurate estimates. In this paper, we propose a strategy named “re-randomization” in the process of densification that could achieve the smallest variance among all densification schemes. The success of this idea naturally inspires us to generalize one permutation hashing to weighted (non-binary) data, which results in the socalled “bin-wise consistent weighted sampling (BCWS)” algorithm. We analyze the behavior of BCWS and compare it with a recent alternative. Extensive experiments on various datasets illustrates the effectiveness of our proposed methods.

AAAI Conference 2019 Conference Paper

Sign-Full Random Projections

  • Ping Li

The method of 1-bit (“sign-sign”) random projections has been a popular tool for efficient search and machine learning on large datasets. Given two D-dim data vectors u, v ∈ RD, one can generate x = PD i=1 uiri, and y = PD i=1 viri, where ri ∼ N(0, 1) iid. Then one can estimate the cosine similarity ρ from sgn(x) and sgn(y). In this paper, we study a series of estimators for “sign-full” random projections. First we prove E(sgn(x)y) = q 2 π ρ, which provides an estimator for ρ. Interestingly this estimator can be substantially improved by normalizing y. Then we study estimators based on E (y−1x≥0 + y+1x<0) and its normalized version. We analyze the theoretical limit (using the MLE) and conclude that, among the proposed estimators, no single estimator can achieve (close to) the theoretical optimal asymptotic variance, for the entire range of ρ. On the other hand, the estimators can be combined to achieve the variance close to that of the MLE. In applications such as near neighbor search, duplicate detection, knn-classification, etc, the training data are first transformed via random projections and then only the signs of the projected data points are stored (i. e. , the sgn(x)). The original training data are discarded. When a new data point arrives, we apply random projections but we do not necessarily need to quantize the projected data (i. e. , the y) to 1-bit. Therefore, sign-full random projections can be practically useful. This gain essentially comes at no additional cost.

NeurIPS Conference 2019 Conference Paper

Towards Practical Alternating Least-Squares for CCA

  • Zhiqiang Xu
  • Ping Li

Alternating least-squares (ALS) is a simple yet effective solver for canonical correlation analysis (CCA). In terms of ease of use, ALS is arguably practitioners' first choice. Despite recent provably guaranteed variants, the empirical performance often remains unsatisfactory. To promote the practical use of ALS for CCA, we propose truly alternating least-squares. Instead of approximately solving two independent linear systems, in each iteration, it simply solves two coupled linear systems of half the size. It turns out that this coupling procedure is able to bring significant performance improvements in practice. Inspired by accelerated power method, we further propose faster alternating least-squares, where momentum terms are introduced into the update equations. Both algorithms enjoy linear convergence. To make faster ALS even more practical, we put forward adaptive alternating least-squares to avoid tuning the momentum parameter, which is as easy to use as the plain ALS while retaining advantages of the fast version. Experiments on several datasets empirically demonstrate the superiority of the proposed algorithms to recent variants.

JMLR Journal 2018 Journal Article

A Tight Bound of Hard Thresholding

  • Jie Shen
  • Ping Li

This paper is concerned with the hard thresholding operator which sets all but the $k$ largest absolute elements of a vector to zero. We establish a tight bound to quantitatively characterize the deviation of the thresholded solution from a given signal. Our theoretical result is universal in the sense that it holds for all choices of parameters, and the underlying analysis depends only on fundamental arguments in mathematical optimization. We discuss the implications for two domains: Compressed Sensing. On account of the crucial estimate, we bridge the connection between the restricted isometry property (RIP) and the sparsity parameter for a vast volume of hard thresholding based algorithms, which renders an improvement on the RIP condition especially when the true sparsity is unknown. This suggests that in essence, many more kinds of sensing matrices or fewer measurements are admissible for the data acquisition procedure. Machine Learning. In terms of large-scale machine learning, a significant yet challenging problem is learning accurate sparse models in an efficient manner. In stark contrast to prior work that attempted the $\ell_1$-relaxation for promoting sparsity, we present a novel stochastic algorithm which performs hard thresholding in each iteration, hence ensuring such parsimonious solutions. Equipped with the developed bound, we prove the {\em global linear convergence} for a number of prevalent statistical models under mild assumptions, even though the problem turns out to be non-convex. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

JMLR Journal 2018 Journal Article

Gradient Hard Thresholding Pursuit

  • Xiao-Tong Yuan
  • Ping Li
  • Tong Zhang

Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure for finding sparse solutions of underdetermined linear systems. This method has been shown to have strong theoretical guarantee and impressive numerical performance. In this article, we generalize HTP from compressed sensing to a generic problem setup of sparsity-constrained convex optimization. The proposed algorithm iterates between a standard gradient descent step and a hard-thresholding step with or without debiasing. We analyze the parameter estimation and sparsity recovery performance of the proposed method. Extensive numerical results confirm our theoretical predictions and demonstrate the superiority of our method to the state-of-the-art greedy selection methods in sparse linear regression, sparse logistic regression and sparse precision matrix estimation problems.\footnote{A conference version of this work appeared in ICML 2014 \citep{Yuan- ICML-2014}.} [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

TIST Journal 2017 Journal Article

Adult Image and Video Recognition by a Deep Multicontext Network and Fine-to-Coarse Strategy

  • Xinyu Ou
  • Hefei Ling
  • Han Yu
  • Ping Li
  • Fuhao Zou
  • Si Liu

Adult image and video recognition is an important and challenging problem in the real world. Low-level feature cues do not produce good enough information, especially when the dataset is very large and has various data distributions. This issue raises a serious problem for conventional approaches. In this article, we tackle this problem by proposing a deep multicontext network with fine-to-coarse strategy for adult image and video recognition. We employ a deep convolution networks to model fusion features of sensitive objects in images. Global contexts and local contexts are both taken into consideration and are jointly modeled in a unified multicontext deep learning framework. To make the model more discriminative for diverse target objects, we investigate a novel hierarchical method, and a task-specific fine-to-coarse strategy is designed to make the multicontext modeling more suitable for adult object recognition. Furthermore, some recently proposed deep models are investigated. Our approach is extensively evaluated on four different datasets. One dataset is used for ablation experiments, whereas others are used for generalization experiments. Results show significant and consistent improvements over the state-of-the-art methods.

IJCAI Conference 2017 Conference Paper

Online Robust Low-Rank Tensor Learning

  • Ping Li
  • Jiashi Feng
  • Xiaojie Jin
  • Luming Zhang
  • Xianghua Xu
  • Shuicheng Yan

The rapid increase of multidimensional data (a. k. a. tensor) like videos brings new challenges for low-rank data modeling approaches such as dynamic data size, complex high-order relations, and multiplicity of low-rank structures. Resolving these challenges require a new tensor analysis method that can perform tensor data analysis online, which however is still absent. In this paper, we propose an Online Robust Low-rank Tensor Modeling (ORLTM) approach to address these challenges. ORLTM dynamically explores the high-order correlations across all tensor modes for low-rank structure modeling. To analyze mixture data from multiple subspaces, ORLTM introduces a new dictionary learning component. ORLTM processes data streamingly and thus requires quite low memory cost that is independent of data size. This makes ORLTM quite suitable for processing large-scale tensor data. Empirical studies have validated the effectiveness of the proposed method on both synthetic data and one practical task, i. e. , video background subtraction. In addition, we provide theoretical analysis regarding computational complexity and memory cost, demonstrating the efficiency of ORLTM rigorously.

NeurIPS Conference 2017 Conference Paper

Partial Hard Thresholding: Towards A Principled Analysis of Support Recovery

  • Jie Shen
  • Ping Li

In machine learning and compressed sensing, it is of central importance to understand when a tractable algorithm recovers the support of a sparse signal from its compressed measurements. In this paper, we present a principled analysis on the support recovery performance for a family of hard thresholding algorithms. To this end, we appeal to the partial hard thresholding (PHT) operator proposed recently by Jain et al. [IEEE Trans. Information Theory, 2017]. We show that under proper conditions, PHT recovers an arbitrary "s"-sparse signal within O(s kappa log kappa) iterations where "kappa" is an appropriate condition number. Specifying the PHT operator, we obtain the best known result for hard thresholding pursuit and orthogonal matching pursuit with replacement. Experiments on the simulated data complement our theoretical findings and also illustrate the effectiveness of PHT compared to other popular recovery methods.

NeurIPS Conference 2017 Conference Paper

Simple strategies for recovering inner products from coarsely quantized random projections

  • Ping Li
  • Martin Slawski

Random projections have been increasingly adopted for a diverse set of tasks in machine learning involving dimensionality reduction. One specific line of research on this topic has investigated the use of quantization subsequent to projection with the aim of additional data compression. Motivated by applications in nearest neighbor search and linear learning, we revisit the problem of recovering inner products (respectively cosine similarities) in such setting. We show that even under coarse scalar quantization with 3 to 5 bits per projection, the loss in accuracy tends to range from negligible'' to moderate''. One implication is that in most scenarios of practical interest, there is no need for a sophisticated recovery approach like maximum likelihood estimation as considered in previous work on the subject. What we propose herein also yields considerable improvements in terms of accuracy over the Hamming distance-based approach in Li et al. (ICML 2014) which is comparable in terms of simplicity

NeurIPS Conference 2016 Conference Paper

Exact Recovery of Hard Thresholding Pursuit

  • Xiaotong Yuan
  • Ping Li
  • Tong Zhang

The Hard Thresholding Pursuit (HTP) is a class of truncated gradient descent methods for finding sparse solutions of $\ell_0$-constrained loss minimization problems. The HTP-style methods have been shown to have strong approximation guarantee and impressive numerical performance in high dimensional statistical learning applications. However, the current theoretical treatment of these methods has traditionally been restricted to the analysis of parameter estimation consistency. It remains an open problem to analyze the support recovery performance (a. k. a. , sparsistency) of this type of methods for recovering the global minimizer of the original NP-hard problem. In this paper, we bridge this gap by showing, for the first time, that exact recovery of the global sparse minimizer is possible for HTP-style methods under restricted strong condition number bounding conditions. We further show that HTP-style methods are able to recover the support of certain relaxed sparse solutions without assuming bounded restricted strong condition number. Numerical results on simulated data confirms our theoretical predictions.

NeurIPS Conference 2016 Conference Paper

Learning Additive Exponential Family Graphical Models via $\ell_{2,1}$-norm Regularized M-Estimation

  • Xiaotong Yuan
  • Ping Li
  • Tong Zhang
  • Qingshan Liu
  • Guangcan Liu

We investigate a subclass of exponential family graphical models of which the sufficient statistics are defined by arbitrary additive forms. We propose two $\ell_{2, 1}$-norm regularized maximum likelihood estimators to learn the model parameters from i. i. d. samples. The first one is a joint MLE estimator which estimates all the parameters simultaneously. The second one is a node-wise conditional MLE estimator which estimates the parameters for each node individually. For both estimators, statistical analysis shows that under mild conditions the extra flexibility gained by the additive exponential family models comes at almost no cost of statistical efficiency. A Monte-Carlo approximation method is developed to efficiently optimize the proposed estimators. The advantages of our estimators over Gaussian graphical models and Nonparanormal estimators are demonstrated on synthetic and real data sets.

NeurIPS Conference 2016 Conference Paper

Quantized Random Projections and Non-Linear Estimation of Cosine Similarity

  • Ping Li
  • Michael Mitzenmacher
  • Martin Slawski

Random projections constitute a simple, yet effective technique for dimensionality reduction with applications in learning and search problems. In the present paper, we consider the problem of estimating cosine similarities when the projected data undergo scalar quantization to $b$ bits. We here argue that the maximum likelihood estimator (MLE) is a principled approach to deal with the non-linearity resulting from quantization, and subsequently study its computational and statistical properties. A specific focus is on the on the trade-off between bit depth and the number of projections given a fixed budget of bits for storage or transmission. Along the way, we also touch upon the existence of a qualitative counterpart to the Johnson-Lindenstrauss lemma in the presence of quantization.

NeurIPS Conference 2015 Conference Paper

b-bit Marginal Regression

  • Martin Slawski
  • Ping Li

We consider the problem of sparse signal recovery from $m$ linear measurements quantized to $b$ bits. $b$-bit Marginal Regression is proposed as recovery algorithm. We study the question of choosing $b$ in the setting of a given budget of bits $B = m \cdot b$ and derive a single easy-to-compute expression characterizing the trade-off between $m$ and $b$. The choice $b = 1$ turns out to be optimal for estimating the unit vector corresponding to the signal for any level of additive Gaussian noise before quantization as well as for adversarial noise. For $b \geq 2$, we show that Lloyd-Max quantization constitutes an optimal quantization scheme and that the norm of the signal canbe estimated consistently by maximum likelihood.

NeurIPS Conference 2015 Conference Paper

Regularization-Free Estimation in Trace Regression with Symmetric Positive Semidefinite Matrices

  • Martin Slawski
  • Ping Li
  • Matthias Hein

Trace regression models have received considerable attention in the context of matrix completion, quantum state tomography, and compressed sensing. Estimation of the underlying matrix from regularization-based approaches promoting low-rankedness, notably nuclear norm regularization, have enjoyed great popularity. In this paper, we argue that such regularization may no longer be necessary if the underlying matrix is symmetric positive semidefinite (spd) and the design satisfies certain conditions. In this situation, simple least squares estimation subject to an spd constraint may perform as well as regularization-based approaches with a proper choice of regularization parameter, which entails knowledge of the noise level and/or tuning. By contrast, constrained least squaresestimation comes without any tuning parameter and may hence be preferred due to its simplicity.

AAAI Conference 2015 Conference Paper

Tensor-Based Learning for Predicting Stock Movements

  • Qing Li
  • LiLing Jiang
  • Ping Li
  • Hsinchun Chen

Stock movements are essentially driven by new information. Market data, financial news, and social sentiment are believed to have impacts on stock markets. To study the correlation between information and stock movements, previous works typically concatenate the features of different information sources into one super feature vector. However, such concatenated vector approaches treat each information source separately and ignore their interactions. In this article, we model the multi-faceted investors’ information and their intrinsic links with tensors. To identify the nonlinear patterns between stock movements and new information, we propose a supervised tensor regression learning approach to investigate the joint impact of different information sources on stock markets. Experiments on CSI 100 stocks in the year 2011 show that our approach outperforms the state-of-the-art trading strategies.

NeurIPS Conference 2014 Conference Paper

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

  • Anshumali Shrivastava
  • Ping Li

We present the first provably sublinear time hashing algorithm for approximate \emph{Maximum Inner Product Search} (MIPS). Searching with (un-normalized) inner product as the underlying similarity measure is a known difficult problem and finding hashing schemes for MIPS was considered hard. While the existing Locality Sensitive Hashing (LSH) framework is insufficient for solving MIPS, in this paper we extend the LSH framework to allow asymmetric hashing schemes. Our proposal is based on a key observation that the problem of finding maximum inner products, after independent asymmetric transformations, can be converted into the problem of approximate near neighbor search in classical settings. This key observation makes efficient sublinear hashing scheme for MIPS possible. Under the extended asymmetric LSH (ALSH) framework, this paper provides an example of explicit construction of provably fast hashing scheme for MIPS. Our proposed algorithm is simple and easy to implement. The proposed hashing scheme leads to significant computational savings over the two popular conventional LSH schemes: (i) Sign Random Projection (SRP) and (ii) hashing based on $p$-stable distributions for $L_2$ norm (L2LSH), in the collaborative filtering task of item recommendations on Netflix and Movielens (10M) datasets.

EAAI Journal 2014 Journal Article

Evaluating the risk of failure modes with extended MULTIMOORA method under fuzzy environment

  • Hu-Chen Liu
  • Xiao-Jun Fan
  • Ping Li
  • Yi-Zeng Chen

Failure mode and effects analysis (FMEA) is a prospective risk assessment tool which has been widely used within various industries, particularly the aerospace, automotive and healthcare industries. However, the conventional risk priority number (RPN) method has been criticized much for its deficiencies in risk factor weights, computation of RPN, evaluation of failure modes and so on. Therefore ranking of failure modes based on their related risk factors is necessary seeking to overcome the shortcomings and enhance the assessment capability of the traditional FMEA. In this paper, we treat the risk factors and their weights as fuzzy variables and evaluate them using fuzzy linguistic terms. As a result, a new risk priority model is proposed for evaluating the risk of failure modes based on fuzzy set theory and MULTIMOORA method. An empirical case of preventing infant abduction is provided to illustrate the potential applications and benefits of the proposed fuzzy FMEA. The main findings of this article are related with the proposed technique for failure modes assessment and ranking, and application of this technique for the prevention of infant abduction, which is a devastating problem for a healthcare facility.

NeurIPS Conference 2014 Conference Paper

Online Optimization for Max-Norm Regularization

  • Jie Shen
  • Huan Xu
  • Ping Li

Max-norm regularizer has been extensively studied in the last decade as it promotes an effective low rank estimation of the underlying data. However, max-norm regularized problems are typically formulated and solved in a batch manner, which prevents it from processing big data due to possible memory bottleneck. In this paper, we propose an online algorithm for solving max-norm regularized problems that is scalable to large problems. Particularly, we consider the matrix decomposition problem as an example, although our analysis can also be applied in other problems such as matrix completion. The key technique in our algorithm is to reformulate the max-norm into a matrix factorization form, consisting of a basis component and a coefficients one. In this way, we can solve the optimal basis and coefficients alternatively. We prove that the basis produced by our algorithm converges to a stationary point asymptotically. Experiments demonstrate encouraging results for the effectiveness and robustness of our algorithm. See the full paper at arXiv: 1406. 3190.

NeurIPS Conference 2014 Conference Paper

Recovery of Coherent Data via Low-Rank Dictionary Pursuit

  • Guangcan Liu
  • Ping Li

The recently established RPCA method provides a convenient way to restore low-rank matrices from grossly corrupted observations. While elegant in theory and powerful in reality, RPCA is not an ultimate solution to the low-rank matrix recovery problem. Indeed, its performance may not be perfect even when data are strictly low-rank. This is because RPCA ignores clustering structures of the data which are ubiquitous in applications. As the number of cluster grows, the coherence of data keeps increasing, and accordingly, the recovery performance of RPCA degrades. We show that the challenges raised by coherent data (i. e. , data with high coherence) could be alleviated by Low-Rank Representation (LRR)~\cite{tpami 2013 lrr}, provided that the dictionary in LRR is configured appropriately. More precisely, we mathematically prove that if the dictionary itself is low-rank then LRR is immune to the coherence parameter which increases with the underlying cluster number. This provides an elementary principle for dealing with coherent data and naturally leads to a practical algorithm for obtaining proper dictionaries in unsupervised environments. Experiments on randomly generated matrices and real motion sequences verify our claims. See the full paper at arXiv: 1404. 4032.

NeurIPS Conference 2013 Conference Paper

Beyond Pairwise: Provably Fast Algorithms for Approximate $k$-Way Similarity Search

  • Anshumali Shrivastava
  • Ping Li

We go beyond the notion of pairwise similarity and look into search problems with $k$-way similarity functions. In this paper, we focus on problems related to \emph{3-way Jaccard} similarity: $\mathcal{R}^{3way}= \frac{|S_1 \cap S_2 \cap S_3|}{|S_1 \cup S_2 \cup S_3|}$, $S_1, S_2, S_3 \in \mathcal{C}$, where $\mathcal{C}$ is a size $n$ collection of sets (or binary vectors). We show that approximate $\mathcal{R}^{3way}$ similarity search problems admit fast algorithms with provable guarantees, analogous to the pairwise case. Our analysis and speedup guarantees naturally extend to $k$-way resemblance. In the process, we extend traditional framework of \emph{locality sensitive hashing (LSH)} to handle higher order similarities, which could be of independent theoretical interest. The applicability of $\mathcal{R}^{3way}$ search is shown on the Google sets" application. In addition, we demonstrate the advantage of $\mathcal{R}^{3way}$ resemblance over the pairwise case in improving retrieval quality. "

NeurIPS Conference 2013 Conference Paper

Sign Cauchy Projections and Chi-Square Kernel

  • Ping Li
  • Gennady Samorodnitsk
  • John Hopcroft

The method of Cauchy random projections is popular for computing the $l_1$ distance in high dimension. In this paper, we propose to use only the signs of the projected data and show that the probability of collision (i. e. , when the two signs differ) can be accurately approximated as a function of the chi-square ($\chi^2$) similarity, which is a popular measure for nonnegative data (e. g. , when features are generated from histograms as common in text and vision applications). Our experiments confirm that this method of sign Cauchy random projections is promising for large-scale learning applications. Furthermore, we extend the idea to sign $\alpha$-stable random projections and derive a bound of the collision probability.

NeurIPS Conference 2012 Conference Paper

Entropy Estimations Using Correlated Symmetric Stable Random Projections

  • Ping Li
  • Cun-Hui Zhang

Methods for efficiently estimating the Shannon entropy of data streams have important applications in learning, data mining, and network anomaly detections (e. g. , the DDoS attacks). For nonnegative data streams, the method of Compressed Counting (CC) based on maximally-skewed stable random projections can provide accurate estimates of the Shannon entropy using small storage. However, CC is no longer applicable when entries of data streams can be below zero, which is a common scenario when comparing two streams. In this paper, we propose an algorithm for entropy estimation in general data streams which allow negative entries. In our method, the Shannon entropy is approximated by the finite difference of two correlated frequency moments estimated from correlated samples of symmetric stable random variables. Our experiments confirm that this method is able to substantially better approximate the Shannon entropy compared to the prior state-of-the-art.

NeurIPS Conference 2012 Conference Paper

One Permutation Hashing

  • Ping Li
  • Art Owen
  • Cun-Hui Zhang

While minwise hashing is promising for large-scale learning in massive binary data, the preprocessing cost is prohibitive as it requires applying (e. g. ,) $k=500$ permutations on the data. The testing time is also expensive if a new data point (e. g. , a new document or a new image) has not been processed. In this paper, we develop a simple \textbf{one permutation hashing} scheme to address this important issue. While it is true that the preprocessing step can be parallelized, it comes at the cost of additional hardware and implementation. Also, reducing $k$ permutations to just one would be much more \textbf{energy-efficient}, which might be an important perspective as minwise hashing is commonly deployed in the search industry. While the theoretical probability analysis is interesting, our experiments on similarity estimation and SVM \& logistic regression also confirm the theoretical results.

NeurIPS Conference 2011 Conference Paper

Hashing Algorithms for Large-Scale Learning

  • Ping Li
  • Anshumali Shrivastava
  • Joshua Moore
  • Arnd König

Minwise hashing is a standard technique in the context of search for efficiently computing set similarities. The recent development of b-bit minwise hashing provides a substantial improvement by storing only the lowest b bits of each hashed value. In this paper, we demonstrate that b-bit minwise hashing can be naturally integrated with linear learning algorithms such as linear SVM and logistic regression, to solve large-scale and high-dimensional statistical learning tasks, especially when the data do not fit in memory. We compare $b$-bit minwise hashing with the Count-Min (CM) and Vowpal Wabbit (VW) algorithms, which have essentially the same variances as random projections. Our theoretical and empirical comparisons illustrate that b-bit minwise hashing is significantly more accurate (at the same storage cost) than VW (and random projections) for binary data.

NeurIPS Conference 2010 Conference Paper

b-Bit Minwise Hashing for Estimating Three-Way Similarities

  • Ping Li
  • Arnd Konig
  • Wenhao Gui

Computing two-way and multi-way set similarities is a fundamental problem. This study focuses on estimating 3-way resemblance (Jaccard similarity) using b-bit minwise hashing. While traditional minwise hashing methods store each hashed value using 64 bits, b-bit minwise hashing only stores the lowest b bits (where b>= 2 for 3-way). The extension to 3-way similarity from the prior work on 2-way similarity is technically non-trivial. We develop the precise estimator which is accurate and very complicated; and we recommend a much simplified estimator suitable for sparse data. Our analysis shows that $b$-bit minwise hashing can normally achieve a 10 to 25-fold improvement in the storage space required for a given estimator accuracy of the 3-way resemblance.

AIIM Journal 2010 Journal Article

Development of traditional Chinese medicine clinical data warehouse for medical knowledge discovery and decision support

  • Xuezhong Zhou
  • Shibo Chen
  • Baoyan Liu
  • Runsun Zhang
  • Yinghui Wang
  • Ping Li
  • Yufeng Guo
  • Hua Zhang

Objective Traditional Chinese medicine (TCM) is a scientific discipline, which develops the related theories from the long-term clinical practices. The large-scale clinical data are the core empirical knowledge source for TCM research. This paper introduces a clinical data warehouse (CDW) system, which incorporates the structured electronic medical record (SEMR) data for medical knowledge discovery and TCM clinical decision support (CDS). Materials and methods We have developed the clinical reference information model (RIM) and physical data model to manage the various information entities and their relationships in TCM clinical data. An extraction-transformation-loading (ETL) tool is implemented to integrate and normalize the clinical data from different operational data sources. The CDW includes online analytical processing (OLAP) and complex network analysis (CNA) components to explore the various clinical relationships. Furthermore, the data mining and CNA methods are used to discover the valuable clinical knowledge from the data. Results The CDW has integrated 20, 000 TCM inpatient data and 20, 000 outpatient data, which contains manifestations (e. g. symptoms, physical examinations and laboratory test results), diagnoses and prescriptions as the main information components. We propose a practical solution to accomplish the large-scale clinical data integration and preprocessing tasks. Meanwhile, we have developed over 400 OLAP reports to enable the multidimensional analysis of clinical data and the case-based CDS. We have successfully conducted several interesting data mining applications. Particularly, we use various classification methods, namely support vector machine, decision tree and Bayesian network, to discover the knowledge of syndrome differentiation. Furthermore, we have applied association rule and CNA to extract the useful acupuncture point and herb combination patterns from the clinical prescriptions. Conclusion A CDW system consisting of TCM clinical RIM, ETL, OLAP and data mining as the core components has been developed to facilitate the tasks of TCM knowledge discovery and CDS. We have conducted several OLAP and data mining tasks to explore the empirical knowledge from the TCM clinical data. The CDW platform would be a promising infrastructure to make full use of the TCM clinical data for scientific hypothesis generation, and promote the development of TCM from individualized empirical knowledge to large-scale evidence-based medicine.

YNIMG Journal 2008 Journal Article

Cortical competition during language discrimination

  • Jingjing Zhao
  • Hua Shu
  • Linjun Zhang
  • Xiaoyi Wang
  • Qiyong Gong
  • Ping Li

How do human listeners differentiate one language from another? In this study we examine the contributions of acoustic and linguistic cues to successful language discrimination. In particular, we report findings that reveal patterns of cortical competition as a function of the competition between prosodic, phonological, and lexical semantic information during language discrimination. We manipulated four types of stimuli in the listening environment: synthesized speech with rhythmic information, synthesized speech with rhythmic plus intonational information, natural speech from Japanese and Italian, and natural speech from Chinese and English. Our study shows that, depending on the amount and the kind of cues available, the listener recruits different areas of the brain for the same language task. Furthermore, brain activations do not monotonically multiply as a function of the complexity of the cues available, but are the outcomes of cue competition as a function of cue validity for the discrimination task. These findings show how acoustic and linguistic cues lead to cortical competition and how cortical activities adapt to the task demand for successful information processing.

NeurIPS Conference 2008 Conference Paper

One sketch for all: Theory and Application of Conditional Random Sampling

  • Ping Li
  • Kenneth Church
  • Trevor Hastie

Conditional Random Sampling (CRS) was originally proposed for efficiently computing pairwise ($l_2$, $l_1$) distances, in static, large-scale, and sparse data sets such as text and Web data. It was previously presented using a heuristic argument. This study extends CRS to handle dynamic or streaming data, which much better reflect the real-world situation than assuming static data. Compared with other known sketching algorithms for dimension reductions such as stable random projections, CRS exhibits a significant advantage in that it is ``one-sketch-for-all. '' In particular, we demonstrate that CRS can be applied to efficiently compute the $l_p$ distance and the Hilbertian metrics, both are popular in machine learning. Although a fully rigorous analysis of CRS is difficult, we prove that, with a simple modification, CRS is rigorous at least for an important application of computing Hamming norms. A generic estimator and an approximate variance formula are provided and tested on various applications, for computing Hamming norms, Hamming distances, and $\chi^2$ distances.

TCS Journal 2008 Journal Article

Paths in circuit graphs of matroids

  • Guizhen Liu
  • Ping Li

Let G be the circuit graph of any connected matroid. It is proved that for any two vertices of G, there is a path of length k joining them for any integer k satisfying 2 ≤ k ≤ | V ( G ) | − 1.

TCS Journal 2007 Journal Article

A new algorithm based on copulas for VaR valuation with empirical calculations

  • Gang Cheng
  • Ping Li
  • Peng Shi

This paper concerns the application of copula functions in VaR valuation. The copula function is used to model the dependence structure of multivariate assets. After the introduction of the traditional Monte Carlo simulation method and the pure copula method we present a new algorithm based on mixture copula functions and the dependence measure, Spearman’s rho. This new method is used to simulate daily returns of two stock market indices in China, Shanghai Stock Composite Index and Shenzhen Stock Composite Index, and then empirically calculate six risk measures including VaR and conditional VaR. The results are compared with those derived from the traditional Monte Carlo method and the pure copula method. From the comparison we show that the dependence structure between asset returns plays a more important role in valuating risk measures comparing with the form of marginal distributions.

NeurIPS Conference 2007 Conference Paper

A Unified Near-Optimal Estimator For Dimension Reduction in $l_\alpha$ ($0<\alpha\leq 2$) Using Stable Random Projections

  • Ping Li
  • Trevor Hastie

Many tasks (e. g. , clustering) in machine learning only require the lα distances in- stead of the original data. For dimension reductions in the lα norm (0 < α ≤ 2), the method of stable random projections can efficiently compute the lα distances in massive datasets (e. g. , the Web or massive data streams) in one pass of the data. The estimation task for stable random projections has been an interesting topic. We propose a simple estimator based on the fractional power of the samples (pro- jected data), which is surprisingly near-optimal in terms of the asymptotic vari- ance. In fact, it achieves the Cram´er-Rao bound when α = 2 and α = 0+. This new result will be useful when applying stable random projections to distance- based clustering, classifications, kernels, massive data streams etc.

NeurIPS Conference 2007 Conference Paper

McRank: Learning to Rank Using Multiple Classification and Gradient Boosting

  • Ping Li
  • Qiang Wu
  • Christopher Burges

We cast the ranking problem as (1) multiple classification (“Mc”) (2) multiple or- dinal classification, which lead to computationally tractable learning algorithms for relevance ranking in Web search. We consider the DCG criterion (discounted cumulative gain), a standard quality measure in information retrieval. Our ap- proach is motivated by the fact that perfect classifications result in perfect DCG scores and the DCG errors are bounded by classification errors. We propose us- ing the Expected Relevance to convert class probabilities into ranking scores. The class probabilities are learned using a gradient boosting tree algorithm. Evalua- tions on large-scale datasets show that our approach can improve LambdaRank [5] and the regressions-based ranker [6], in terms of the (normalized) DCG scores. An efficient implementation of the boosting tree algorithm is also presented.

JMLR Journal 2007 Journal Article

Nonlinear Estimators and Tail Bounds for Dimension Reduction in l1 Using Cauchy Random Projections

  • Ping Li
  • Trevor J. Hastie
  • Kenneth W. Church

For dimension reduction in the l 1 norm, the method of Cauchy random projections multiplies the original data matrix A ∈ ℝ n×D with a random matrix R ∈ ℝ D×k ( k ≪ D ) whose entries are i.i.d. samples of the standard Cauchy C (0,1). Because of the impossibility result, one can not hope to recover the pairwise l 1 distances in A from B = A × R ∈ ℝ n×k, using linear estimators without incurring large errors. However, nonlinear estimators are still useful for certain applications in data stream computations, information retrieval, learning, and data mining. We study three types of nonlinear estimators: the sample median estimators, the geometric mean estimators, and the maximum likelihood estimators (MLE). We derive tail bounds for the geometric mean estimators and establish that k = O (log n / ε 2 ) suffices with the constants explicitly given. Asymptotically (as k →∞), both the sample median and the geometric mean estimators are about 80% efficient compared to the MLE. We analyze the moments of the MLE and propose approximating its distribution of by an inverse Gaussian. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

NeurIPS Conference 2006 Conference Paper

Conditional Random Sampling: A Sketch-based Sampling Technique for Sparse Data

  • Ping Li
  • Kenneth Church
  • Trevor Hastie

We1 develop Conditional Random Sampling (CRS), a technique particularly suit- able for sparse data. In large-scale applications, the data are often highly sparse. CRS combines sketching and sampling in that it converts sketches of the data into conditional random samples online in the estimation stage, with the sample size determined retrospectively. This paper focuses on approximating pairwise l2 and l1 distances and comparing CRS with random projections. For boolean (0/1) data, CRS is provably better than random projections. We show using real-world data that CRS often outperforms random projections. This technique can be applied in learning, data mining, information retrieval, and database query optimizations.

YNIMG Journal 2004 Journal Article

Neural representations of nouns and verbs in Chinese: an fMRI study

  • Ping Li
  • Zhen Jin
  • Li Hai Tan

The neural representation of nouns and verbs has been a focus of many recent neuroimaging and neuropsychological studies. These studies have in general found that in English and other Indo-European languages, verbs are represented in the frontal region (e. g. , the left prefrontal cortex) while nouns in the posterior regions (the temporal–occipital regions). There is accumulating evidence, however, that the picture may have been overly simplified. In the present study, we examine the representations of nouns and verbs in Chinese, a language that has unique properties in its grammar and particularly in the structure of nouns and verbs. In an fMRI experiment, subjects viewed a list of disyllabic nouns, verbs, and class-ambiguous words and performed a lexical decision on the target. Results from the experiment indicate that nouns and verbs in Chinese activate a wide range of overlapping brain areas in distributed networks, in both the left and the right hemispheres. The results provide support for the prediction regarding the impact of linguistic typology and language-specific influences on the neural representation of grammatical categories. They are consistent with recent proposals that specific linguistic experience shapes neural systems of reading and speaking and that the language-specific properties of the Chinese grammar affect the representation, processing, and acquisition in this language.

v2026.09.13