Arrow Research search

Author name cluster

Tao Jiang

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.

51 papers
2 author rows

Possible papers

51

AAAI Conference 2026 Conference Paper

FedSkeleton: Secure Multi-Party Graph Skeleton Construction for Privacy-Preserving Federated Time-Series Forecasting

  • Henggang Deng
  • Yuchao Tang
  • Wenjie Fu
  • Huandong Wang
  • Kun Chen
  • Tao Jiang

In real-world time-series modelling, graph structures are widely adopted because they explicitly encode node topology and capture complex network dynamics. In practice, however, a complete graph is often partitioned across multiple parties; each party can access only its local sub-graph and, owing to privacy regulations, cannot share topology or data, creating pervasive data silos. Federated Graph Learning (FGL) offers a privacy-preserving collaborative-learning paradigm, yet current methods still face two key challenges: (1) the graph topology itself contains sensitive structural information, which can lead to privacy leakage if directly shared during FGL; (2) cross-party edges are crucial for accurate modeling, yet exploiting them without compromising privacy remains a significant challenge. To overcome these obstacles, we propose FedSkeleton, a privacy-preserving framework for time-series prediction that comprises a Skeleton Construction Module and a Dual-stream Forecasting Module, enabling global dependency capture without revealing the topology. Extensive experiments show that FedSkeleton consistently outperforms existing baselines and even surpasses models trained in a centralized setting with full-graph access in certain cases. In addition, we conduct comprehensive security analysis, communication-cost evaluation and scalability experiments, demonstrating that FedSkeleton effectively resists common attacks, keeps communication overhead manageable, and remains robust with respect to key hyper-parameters and the number of participating parties.

PDF Details DOI

YNICL Journal 2026 Journal Article

Functional gradient analysis reveals potential therapeutic mechanisms of nrTMS for postoperative motor deficits in glioma patients: A randomized controlled trial

  • Yuzhe Li
  • Jiangwei Wang
  • Zhong Zhang
  • Xing Fan
  • Yinyan Wang
  • Wenbin Ma
  • Tao Jiang
  • Shengyu Fang

OBJECTIVE: This study aimed to investigate the therapeutic effects and neural mechanisms of high-frequency neuro-navigated repetitive transcranial magnetic stimulation (nrTMS) targeting the hand knob in glioma patients with postoperative motor deficits, using functional gradient analysis to characterize cortical reorganization. METHODS: Thirty patients with postoperative motor deficits were randomized to receive nrTMS or sham stimulation targeting the ipsilateral hand knob. Motor function was assessed using Fugl-Meyer Assessment (FMA) and muscle strength. Resting-state fMRI was acquired to compute principal functional gradients. Control/tumor, nrTMS/sham, and Pre-TMS/Post-TMS gradient changes were analyzed. Correlation and regression analyses related to motor recovery were performed. RESULTS: The nrTMS group showed significantly greater improvement in muscle strength (Post-treatment: nrTMS: 3.533 ± 0.720, Sham: 2.067 ± 0.572, p = 0.019, d = 1.082; 3-month follow-up: nrTMS: 4.600 ± 0.408, Sham: 3.733 ± 0.609, p = 0.035, d = 1.012). Gradient analysis revealed increased sensorimotor network (SMN) gradient scores following nrTMS (Pre-TMS: -0.707 ± 0.108; Post-TMS: -0.636 ± 0.077; p = 0.016), and HH_SomMot_22 within upper limb motor cortex is most strongly correlated with motor recovery. CONCLUSIONS: High-frequency nrTMS targeting the hand knob accelerated the motor recovery. Gradient analysis findings provide novel insights into therapeutic mechanisms of nrTMS and underscore the value of the hand knob as a stimulation target.

Details DOI

AAAI Conference 2026 Conference Paper

Multi-agent In-context Coordination via Decentralized Memory Retrieval

  • Tao Jiang
  • Zichuan Lin
  • Lihe Li
  • Yi-Chen Li
  • Cong Guan
  • Lei Yuan
  • Zongzhang Zhang
  • Yang Yu

Large transformer models, trained on diverse datasets, have demonstrated impressive few-shot performance on previously unseen tasks without requiring parameter updates. This capability has also been explored in Reinforcement Learning (RL), where agents interact with the environment to retrieve context and maximize cumulative rewards, showcasing strong adaptability in complex settings. However, in cooperative Multi-Agent Reinforcement Learning (MARL), where agents must coordinate toward a shared goal, decentralized policy deployment can lead to mismatches in task alignment and reward assignment, limiting the efficiency of policy adaptation. To address this challenge, we introduce Multi-agent In-context Coordination via Decentralized Memory Retrieval (MAICC), a novel approach designed to enhance coordination by fast adaptation. Our method involves training a centralized embedding model to capture fine-grained trajectory representations, followed by decentralized models that approximate the centralized one to obtain team-level task information. Based on the learned embeddings, relevant trajectories are retrieved as context, which, combined with the agents' current sub-trajectories, inform decision-making. During decentralized execution, we introduce a novel memory mechanism that effectively balances test-time online data with offline memory. Based on the constructed memory, we propose a hybrid utility score that incorporates both individual- and team-level returns, ensuring credit assignment across agents. Extensive experiments on cooperative MARL benchmarks, including Level-Based Foraging (LBF) and SMAC (v1/v2), show that MAICC enables faster adaptation to unseen tasks compared to existing methods.

PDF Details DOI

AAAI Conference 2026 Conference Paper

UQ-ViT: Harmonizing Extreme Activations with Hardware-Friendly Uniform Quantization in Vision Transformers

  • Tao Jiang
  • Yucheng Jiang
  • Xiwen Yao
  • Gong Cheng
  • Junwei Han

Post-Training Quantization enables efficient Vision Transformer (ViTs) deployment with a small calibration data, and its prevalent use of uniform quantization harnesses AI accelerator matrix cores for high-speed inference. However, the application of uniform quantization is fundamentally challenged by the extreme non-uniformity of activation distributions.Specifically, the power-law nature of post-Softmax attention scores and the significant inter-channel variance in post-GELU activations create a dilemma for conventional quantization, as it struggles to preserve critical high-magnitude values without sacrificing overall precision. To resolve this core conflict, we introduce UQ-ViT (Uniform Quantization for Vision Transformers), a novel uniform quantization framework designed to reconcile high precision with hardware efficiency. Central to UQ-ViT are two operators: Dynamic Elimination of Maximum (DeMax) and Normalization Quantization (NormQuant). DeMax is a quantization operator for post-Softmax attention scores that utilizes uniform quantization. It dynamically eliminates and preserves dominant values, effectively mitigating quantization loss from the extreme values in the power-law distribution. NormQuant utilizes a per-channel quantization strategy during quantization and reverts to a per-tensor format for dequantization, achieving both high accuracy and computational efficiency. Crucially, it is applicable to any linear layer, enabling effective quantization of post-GELU activations in ViTs. Through extensive experiments on various ViTs and vision tasks, including image classification, object detection, and instance segmentation, we demonstrate that our proposed approach outperforms existing methods, achieving superior accuracy while ensuring hardware friendliness.

PDF Details DOI

EAAI Journal 2025 Journal Article

A prior segmentation knowledge enhanced deep learning system for the classification of tumors in ultrasound image

  • Tao Jiang
  • Jun Guo
  • Wenyu Xing
  • Ming Yu
  • Yifang Li
  • Bo Zhang
  • Yi Dong
  • Dean Ta

Breast and thyroid cancers are prevalent among women worldwide. Ultrasound (US) examination is widely used for the early detection of breast and thyroid cancers. However, due to the blurred tumor boundaries and irregular shapes, the computer-aided diagnosis (CAD) of tumors based on US is challenging. Numerous studies have introduced deep learning-based multi-task learning approaches to address this issue, but these methods may result in feature redundancy and misinformation. Tumor segmentation is a prerequisite step for US CAD, and a higher Dice coefficient is associated with more accurate classification outcomes. Therefore, this paper introduces a novel deep-learning system that fully utilizes segmentation knowledge to boost classification performance. The system starts with a hybrid convolutional neural network (CNN)-Transformer for tumor localization and coarse segmentation, then uses a lightweight CNN-based U-Net to refine segmentation results. Subsequently, segmentation knowledge is harnessed to augment the network input and enhance multimodal feature extraction, resulting in improved classification performance. Our proposed method yielded a Dice coefficient of 83. 62% and 77. 20% for breast and thyroid tumor segmentation and area under curve (AUC) values of 0. 9536 and 0. 9475 for their respective classifications. Compared to non-segmentation knowledge-based classification models, our method obtained an increase in AUC of 0. 1054 and 0. 0566 on the breast and thyroid datasets, respectively. It outperformed the performance of the State-Of-The-Art (SOTA) methods across various datasets. In summary, our proposed system shows promise for application in US tumor analysis and holds potential to be extended to additional diseases and modalities.

Details DOI

IROS Conference 2025 Conference Paper

Design, Manufacturing, and Experiments of an Origami-based Parallel-Legged Structure for Insect-scale Robots

  • Qunwei Zhu
  • Minghai Xia
  • Tao Jiang
  • Zhongyue Lu
  • Yiming Zhu
  • Zirong Luo

Aiming to address the challenges associated with complex manufacturing processes and the difficulties in batch production of insect-scale robots. A mechatronic origami mechanism applied to an insect-scale parallel-legged structure is designed, manufactured, and tested. The origami mechanism is constructed using a multilayer composite laminate, which allows for the integrated fabrication of robotic hinges, linkages, and actuators. Utilizing the origami mechanism, it becomes feasible to fold and create the insect-scale parallel-legged structure. This enables the rapid assembly of various types of insect-scale robots, including monopods, bipedal robots, quadrupeds, and hexapods. We built the experimental prototype and test environments to validate the kinematic performance of the insect-scale parallel-legged structure. The monopod robot, weighing 200 mg and featuring the parallel leg, possesses the ability to rotate around the center of an adaptive rotating platform at a speed of 5 cm/s. The bipedal robot demonstrates the ability to navigate the rotating platform by performing alternating leg swings. The quadrupedal robot, designed with four parallel-legged structures, exhibited a movement speed of 1. 9 cm/s when actuated at a frequency of 20 Hz. In contrast, the hexapod robot achieved a superior speed of 3. 25 cm/s under the same actuation frequency of 20 Hz. The origami mechanism and the insect-scale parallel-legged structure provide a new method for the design and fabrication of insect-scale robots.

Details

ICRA Conference 2025 Conference Paper

Efficient 7-DoF Grasp for Target-Driven Object in Dense Cluttered Scenes

  • Tianjiao Lei
  • Yizhuo Sun
  • Yi Huang
  • Jiangshuai Huang
  • Tao Jiang

Achieving a real-time precise grasp of a specified target object in densely cluttered environments is an essential capability for autonomous robot operation. Recently, considerable investigations on planar and spatial grasp have been carried out, and significant results have been obtained. However, these point cloud-based grasp prediction methods often fail to ensure that the generated grasp configurations meet the precise requirements of the task. Additionally, some of the existing grasp pipelines are too time-consuming to meet the demand for real-time robot response. In more challenging cluttered scenes, the quality of pose and gripper jaw opening estimation in highdimensional space requires further improvement. Therefore, this paper introduces a data- and model-independent and efficient method to generate 7-DoF grasp configurations for arbitrary target objects from single-view point cloud data in dense cluttered scenes. In addition, this paper proposes a grasp framework that generates the grasp configuration for the target object while reducing the time consumed during the grasp process, to enable robots to efficiently grasp target objects for designated tasks. The grasp pipeline focuses on guided regions via target detection and rapidly adjusts grasp configurations through multi-region point cloud distribution perception. Extensive real-world robot experiments have demonstrated the effectiveness of the proposed method in grasping target objects in cluttered scenes, achieving higher success rates and reduced runtime compared to baseline methods. The realized code and video are available at https://github.com/L-tj/7DGCG.

Details

IROS Conference 2025 Conference Paper

Heteroscedastic Bayesian Optimization-Based Dynamic PID Tuning for Accurate and Robust UAV Trajectory Tracking

  • Fuqiang Gu
  • Jiangshan Ai
  • Xu Lu
  • Xianlei Long
  • Yan Li 0037
  • Tao Jiang
  • Chao Chen 0004
  • Huidong Liu

Unmanned Aerial Vehicles (UAVs) play an important role in various applications, where precise trajectory tracking is crucial. However, conventional control algorithms for trajectory tracking often exhibit limited performance due to the underactuated, nonlinear, and highly coupled dynamics of quadrotor systems. To address these challenges, we propose HBO-PID, a novel control algorithm that integrates the Heteroscedastic Bayesian Optimization (HBO) framework with the classical PID controller to achieve accurate and robust trajectory tracking. By explicitly modeling input-dependent noise variance, the proposed method can better adapt to dynamic and complex environments, and therefore improve the accuracy and robustness of trajectory tracking. To accelerate the convergence of optimization, we adopt a two-stage optimization strategy that allow us to more efficiently find the optimal controller parameters. Through experiments in both simulation and real-world scenarios, we demonstrate that the proposed method significantly outperforms state-of-the-art (SOTA) methods. Compared to SOTA methods, it improves the position accuracy by 24. 7% to 42. 9%, and the angular accuracy by 40. 9% to 78. 4%.

Details

IROS Conference 2025 Conference Paper

Hierarchical Trajectory Planning Method for Piano-Playing Robot

  • Zirui Wang
  • Jiayu Zhang
  • Wei Jiang
  • Tao Jiang
  • Jingdong Zhao
  • Liangliang Zhao
  • Baoshi Cao
  • Le Qi

Piano-playing tasks, which effectively demonstrate bimanual coordination capabilities in humanoid robots, are increasingly becoming a research focus. However, prior research has predominantly focused on Cartesian space trajectory planning without adequately addressing real-world obstacle avoidance constraints and manipulator acceleration limits. This paper proposes a hierarchical trajectory planning framework that systematically incorporates both obstacle avoidance and acceleration constraints. Firstly, discrete Cartesian path points are generated using a dynamic programming approach; secondly, joint space path points are derived considering obstacle avoidance and joint limit constraints through dynamic programming; thirdly, the joint space trajectory is interpolated using a Jacobian inverse-based method; finally, the trajectory is refined using Model Predictive Control (MPC). Experimental results demonstrate that the proposed method produces trajectories satisfying both obstacle avoidance and acceleration constraints, enabling fluent piano piece execution in real-world environments.

Details

ICML Conference 2025 Conference Paper

LLM-Assisted Semantically Diverse Teammate Generation for Efficient Multi-agent Coordination

  • Lihe Li
  • Lei Yuan 0005
  • Pengsen Liu
  • Tao Jiang
  • Yang Yu 0001

Training with diverse teammates is the key for learning generalizable agents. Typical approaches aim to generate diverse teammates by utilizing techniques like randomization, designing regularization terms, or reducing policy compatibility, etc. However, such teammates lack semantic information, resulting in inefficient teammate generation and poor adaptability of the agents. To tackle these challenges, we propose Semantically Diverse Teammate Generation (SemDiv), a novel framework leveraging the capabilities of large language models (LLMs) to discover and learn diverse coordination behaviors at the semantic level. In each iteration, SemDiv first generates a novel coordination behavior described in natural language, then translates it into a reward function to train a teammate policy. Once the policy is verified to be meaningful, novel, and aligned with the behavior, the agents train a policy for coordination. Through this iterative process, SemDiv efficiently generates a diverse set of semantically grounded teammates, enabling agents to develop specialized policies, and select the most suitable ones through language-based reasoning to adapt to unseen teammates. Experiments show that SemDiv generates teammates covering a wide range of coordination behaviors, including those unreachable by baseline methods. Evaluation across four MARL environments, each with five unseen representative teammates, demonstrates SemDiv’s superior coordination and adaptability. Our code is available at https: //github. com/lilh76/SemDiv.

Details

AAAI Conference 2025 Conference Paper

MIA-Tuner: Adapting Large Language Models as Pre-training Text Detector

  • Wenjie Fu
  • Huandong Wang
  • Chen Gao
  • Guanghua Liu
  • Yong Li
  • Tao Jiang

The increasing parameters and expansive dataset of large lan- guage models (LLMs) highlight the urgent demand for a technical solution to audit the underlying privacy risks and copyright issues associated with LLMs. Existing studies have partially addressed this need through an exploration of the pre-training data detection problem, which is an instance of a membership inference attack (MIA). This problem involves determining whether a given piece of text has been used during the pre-training phase of the target LLM. Although existing methods have designed various sophisticated MIA score functions to achieve considerable detection performance in pre-trained LLMs, how to achieve high-confidence detection and how to perform MIA on aligned LLMs remain challenging. In this paper, we propose MIA-Tuner, a novel instruction-based MIA method, which instructs LLMs themselves to serve as a more precise pre-training data detector internally, rather than design an external MIA score function. Furthermore, we design two instruction-based safeguards to respectively mitigate the privacy risks brought by the existing methods and MIA-Tuner. To comprehensively evaluate the most recent state-of-the-art LLMs, we collect a more up-to-date MIA benchmark dataset, named WIKIMIA-24, to replace the widely adopted benchmark WIKIMIA. We conduct extensive experiments across various aligned and unaligned LLMs over the two benchmark datasets. The results demonstrate that MIA-Tuner increases the AUC of MIAs from 0.7 to a significantly high level of 0.9.

PDF Details DOI

NeurIPS Conference 2025 Conference Paper

MoBA: Mixture of Block Attention for Long-Context LLMs

  • Enzhe Lu
  • Zhejun Jiang
  • Jingyuan Liu
  • Yulun Du
  • Tao Jiang
  • Chao Hong
  • Shaowei Liu
  • Weiran He

Scaling the effective context length is essential for advancing large language models (LLMs) toward artificial general intelligence (AGI). However, the quadratic increase in computational complexity inherent in traditional attention mechanisms presents a prohibitive overhead. Existing approaches either impose strongly biased structures, such as sink or window attention which are task-specific, or radically modify the attention mechanism into linear approximations, whose performance in complex reasoning tasks remains inadequately explored. In this work, we propose a solution that adheres to the ``less structure'' principle, allowing the model to determine where to attend autonomously, rather than introducing predefined biases. We introduce Mixture of Block Attention (MoBA), an innovative approach that applies the principles of Mixture of Experts (MoE) to the attention mechanism. This novel architecture demonstrates superior performance on long-context tasks while offering a key advantage: the ability to seamlessly transition between full and sparse attention, enhancing efficiency without the risk of compromising performance. MoBA has already been deployed to handle actual production workloads with long-context requirements, demonstrating significant advancements in efficient attention computation for LLMs. Our code is available at https: //github. com/MoonshotAI/MoBA.

PDF Details

TIST Journal 2025 Journal Article

Mobility Data-Driven Privacy-Preserving Model for Detecting High-Risk Infection Cases

  • Wenjie Fu
  • Huandong Wang
  • Chen Gao
  • Guanghua Liu
  • Yong Li
  • Tao Jiang

In the past few years, infectious diseases like COVID-19 have caused serious distress to the global society and the economy. To prevent its spread, the early detection and assessment of infectious diseases based on molecular tests or antigen testing of bodily have led to countless labor and material costs. Fortunately, with the rapid development of mobile localization and web techniques, the collected massive mobile trajectory data provide a promising solution for detecting positive cases. However, existing mobility data-driven infection case detection methods are limited in terms of modeling the complicated epidemic spreading processes and preserving user privacy of the mobility data. In this article, we propose a novel graph convolutional networks (GCN) model for detecting high-risk infection cases, where we incorporate a spatio-temporal hypergraph to model the complex interaction of individuals. Then, we elaborately design a privacy-preserving framework tightly coupled with the structure of the spatio-temporal hypergraph, which includes a mobility data obfuscation module to protect privacy and an accompanying confidence-aware mechanism to mitigate the consequent performance decline. Moreover, we introduce a causal propagation mechanism to further guarantee the temporal dependency and causal effect of the feature propagation in our spatio-temporal hypergraph, which introduces both the causal transform of node features and the causal gathering of edge features. Finally, extensive experiments on a large mobility dataset collected from location-based services (LBS) show that the proposed model improves the performance of infection case detection by at least 12.47% when compared with several widely adopted baselines. Besides, our code and datasets are available at the link ( https://github.com/wjfu99/EPI-HGNN ).

Details DOI

NeurIPS Conference 2025 Conference Paper

Multi-Agent Imitation by Learning and Sampling from Factorized Soft Q-Function

  • Yi-Chen Li
  • Zhongxiang Ling
  • Tao Jiang
  • Fuxiang Zhang
  • Pengyuan Wang
  • Lei Yuan
  • Zongzhang Zhang
  • Yang Yu

Learning from multi-agent expert demonstrations, known as Multi-Agent Imitation Learning (MAIL), provides a promising approach to sequential decision-making. However, existing MAIL methods including Behavior Cloning (BC) and Adversarial Imitation Learning (AIL) face significant challenges: BC suffers from the compounding error issue, while the very nature of adversarial optimization makes AIL prone to instability. In this work, we propose \textbf{M}ulti-\textbf{A}gent imitation by learning and sampling from \textbf{F}actor\textbf{I}zed \textbf{S}oft Q-function (MAFIS), a novel method that addresses these limitations for both online and offline MAIL settings. Built upon the single-agent IQ-Learn framework, MAFIS introduces the value decomposition network to factorize the imitation objective at agent level, thus enabling scalable training for multi-agent systems. Moreover, we observe that the soft Q-function implicitly defines the optimal policy as an energy-based model, from which we can sample actions via stochastic gradient Langevin dynamics. This allows us to estimate the gradient of the factorized optimization objective for continuous control tasks, avoiding the adversarial optimization between the soft Q-function and the policy required by prior work. By doing so, we obtain a tractable and \emph{non-adversarial} objective for both discrete and continuous multi-agent control. Experiments on common benchmarks including the discrete control tasks StarCraft Multi-Agent Challenge v2 (SMACv2), Gold Miner, and Multi Particle Environments (MPE), as well as the continuous control task Multi-Agent MuJoCo (MaMuJoCo), demonstrate that MAFIS achieves superior performance compared with baselines. Our code is available at https: //github. com/LAMDA-RL/MAFIS.

PDF Details

AAAI Conference 2025 Conference Paper

Prompt-SID: Learning Structural Representation Prompt via Latent Diffusion for Single Image Denoising

  • Huaqiu Li
  • Wang Zhang
  • Xiaowan Hu
  • Tao Jiang
  • Zikang Chen
  • Haoqian Wang

Many studies have concentrated on constructing supervised models utilizing paired datasets for image denoising, which proves to be expensive and time-consuming. Current self-supervised and unsupervised approaches typically rely on blind-spot networks or sub-image pairs sampling, resulting in pixel information loss and destruction of detailed structural information, thereby significantly constraining the efficacy of such methods. In this paper, we introduce Prompt-SID, a prompt-learning-based single image denoising framework that emphasizes the preservation of structural details. This approach is trained in a self-supervised manner using downsampled image pairs. It captures original-scale image information through structural encoding and integrates this prompt into the denoiser. To achieve this, we propose a structural representation generation model based on the latent diffusion process and design a structural attention module within the transformer-based denoiser architecture to decode the prompt. Additionally, we introduce a scale replay training mechanism, which effectively mitigates the scale gap from images of different resolutions. We conduct comprehensive experiments on synthetic, real-world, and fluorescence imaging datasets, showcasing the remarkable effectiveness of Prompt-SID.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Spatiotemporal Blind-Spot Network with Calibrated Flow Alignment for Self-Supervised Video Denoising

  • Zikang Chen
  • Tao Jiang
  • Xiaowan Hu
  • Wang Zhang
  • Huaqiu Li
  • Haoqian Wang

Self-supervised video denoising aims to remove noise from videos without relying on ground truth data, leveraging the video itself to recover clean frames. Existing methods often rely on simplistic feature stacking or apply optical flow without thorough analysis. This results in suboptimal utilization of both inter-frame and intra-frame information, and it also neglects the potential of optical flow alignment under self-supervised conditions, leading to biased and insufficient denoising outcomes. To this end, we first explore the practicality of optical flow in the self-supervised setting and introduce a SpatioTemporal Blind-spot Network (STBN) for global frame feature utilization. In the temporal domain, we utilize bidirectional blind-spot feature propagation through the proposed blind-spot alignment block to ensure accurate temporal alignment and effectively capture long-range dependencies. In the spatial domain, we introduce the spatial receptive field expansion module, which enhances the receptive field and improves global perception capabilities. Additionally, to reduce the sensitivity of optical flow estimation to noise, we propose an unsupervised optical flow distillation mechanism that refines fine-grained inter-frame interactions during optical flow alignment. Our method demonstrates superior performance across both synthetic and real-world video denoising datasets.

PDF Details DOI

ICRA Conference 2025 Conference Paper

TrackOcc: Camera-Based 4D Panoptic Occupancy Tracking

  • Zhuoguang Chen
  • Kenan Li
  • Xiuyu Yang
  • Tao Jiang
  • Yiming Li 0003
  • Hang Zhao 0021

Comprehensive and consistent dynamic scene understanding from camera input is essential for advanced autonomous systems. Traditional camera-based perception tasks like 3D object tracking and semantic occupancy prediction lack either spatial comprehensiveness or temporal consistency. In this work, we introduce a brand-new task, Camera-based 4D Panoptic Occupancy Tracking, which simultaneously addresses panoptic occupancy segmentation and object tracking from camera-only input. Furthermore, we propose TrackOcc, a cutting-edge approach that processes image inputs in a streaming, end-to-end manner with 4D panoptic queries to address the proposed task. Leveraging the localization-aware loss, TrackOcc enhances the accuracy of 4D panoptic occupancy tracking without bells and whistles. Experimental results demonstrate that our method achieves state-of-the-art performance on the Waymo dataset. The source code will be released at https://github.com/Tsinghua-MARS-Lab/TrackOcc.

Details

NeurIPS Conference 2024 Conference Paper

Membership Inference Attacks against Fine-tuned Large Language Models via Self-prompt Calibration

  • Wenjie Fu
  • Huandong Wang
  • Chen Gao
  • Guanghua Liu
  • Yong Li
  • Tao Jiang

Membership Inference Attacks (MIA) aim to infer whether a target data record has been utilized for model training or not. Existing MIAs designed for large language models (LLMs) can be bifurcated into two types: reference-free and reference-based attacks. Although reference-based attacks appear promising performance by calibrating the probability measured on the target model with reference models, this illusion of privacy risk heavily depends on a reference dataset that closely resembles the training set. Both two types of attacks are predicated on the hypothesis that training records consistently maintain a higher probability of being sampled. However, this hypothesis heavily relies on the overfitting of target models, which will be mitigated by multiple regularization methods and the generalization of LLMs. Thus, these reasons lead to high false-positive rates of MIAs in practical scenarios. We propose a Membership Inference Attack based on Self-calibrated Probabilistic Variation (SPV-MIA). Specifically, we introduce a self-prompt approach, which constructs the dataset to fine-tune the reference model by prompting the target LLM itself. In this manner, the adversary can collect a dataset with a similar distribution from public APIs. Furthermore, we introduce probabilistic variation, a more reliable membership signal based on LLM memorization rather than overfitting, from which we rediscover the neighbour attack with theoretical grounding. Comprehensive evaluation conducted on three datasets and four exemplary LLMs shows that SPV-MIA raises the AUC of MIAs from 0. 7 to a significantly high level of 0. 9. Our code and dataset are available at: https: //github. com/tsinghua-fib-lab/NeurIPS2024_SPV-MIA

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Multi-Agent Domain Calibration with a Handful of Offline Data

  • Tao Jiang
  • Lei Yuan
  • Lihe Li
  • Cong Guan
  • Zongzhang Zhang
  • Yang Yu

The shift in dynamics results in significant performance degradation of policies trained in the source domain when deployed in a different target domain, posing a challenge for the practical application of reinforcement learning (RL) in real-world scenarios. Domain transfer methods aim to bridge this dynamics gap through techniques such as domain adaptation or domain calibration. While domain adaptation involves refining the policy through extensive interactions in the target domain, it may not be feasible for sensitive fields like healthcare and autonomous driving. On the other hand, offline domain calibration utilizes only static data from the target domain to adjust the physics parameters of the source domain (e. g. , a simulator) to align with the target dynamics, enabling the direct deployment of the trained policy without sacrificing performance, which emerges as the most promising for policy deployment. However, existing techniques primarily rely on evolution algorithms for calibration, resulting in low sample efficiency. To tackle this issue, we propose a novel framework Madoc (\textbf{M}ulti-\textbf{a}gent \textbf{do}main \textbf{c}alibration). Firstly, we formulate a bandit RL objective to match the target trajectory distribution by learning a couple of classifiers. We then address the challenge of a large domain parameter space by modeling domain calibration as a cooperative multi-agent reinforcement learning (MARL) problem. Specifically, we utilize a Variational Autoencoder (VAE) to automatically cluster physics parameters with similar effects on the dynamics, grouping them into distinct agents. These grouped agents train calibration policies coordinately to adjust multiple parameters using MARL. Our empirical evaluation on 21 offline locomotion tasks in D4RL and NeoRL benchmarks showcases the superior performance of our method compared to strong existing offline model-based RL, offline domain calibration, and hybrid offline-and-online RL baselines.

PDF Details DOI

IROS Conference 2024 Conference Paper

SSCBench: A Large-Scale 3D Semantic Scene Completion Benchmark for Autonomous Driving

  • Yiming Li 0003
  • Sihang Li 0001
  • Xinhao Liu 0003
  • Moonjun Gong
  • Kenan Li
  • Nuo Chen 0003
  • Zijun Wang
  • Zhiheng Li

Monocular scene understanding is a foundational component of autonomous systems. Within the spectrum of monocular perception topics, one crucial and useful task for holistic 3D scene understanding is semantic scene completion (SSC), which jointly completes semantic information and geometric details from RGB input. However, progress in SSC, particularly in large-scale street views, is hindered by the scarcity of high-quality datasets. To address this issue, we introduce SSCBench, a comprehensive benchmark that integrates scenes from widely used automotive datasets (e. g. , KITTI-360, nuScenes, and Waymo). SSCBench follows an established setup and format in the community, facilitating the easy exploration of SSC methods in various street views. We benchmark models using monocular, trinocular, and point cloud input to assess the performance gap resulting from sensor coverage and modality. Moreover, we have unified semantic labels across diverse datasets to simplify cross-domain generalization testing. We commit to including more datasets and SSC models to drive further advancements in this field. Our data and code are available at https://github.com/ai4ce/SSCBench.

Details

NeurIPS Conference 2023 Conference Paper

Occ3D: A Large-Scale 3D Occupancy Prediction Benchmark for Autonomous Driving

  • Xiaoyu Tian
  • Tao Jiang
  • Longfei Yun
  • Yucheng Mao
  • Huitong Yang
  • Yue Wang
  • Yilun Wang
  • Hang Zhao

Robotic perception requires the modeling of both 3D geometry and semantics. Existing methods typically focus on estimating 3D bounding boxes, neglecting finer geometric details and struggling to handle general, out-of-vocabulary objects. 3D occupancy prediction, which estimates the detailed occupancy states and semantics of a scene, is an emerging task to overcome these limitations. To support 3D occupancy prediction, we develop a label generation pipeline that produces dense, visibility-aware labels for any given scene. This pipeline comprises three stages: voxel densification, occlusion reasoning, and image-guided voxel refinement. We establish two benchmarks, derived from the Waymo Open Dataset and the nuScenes Dataset, namely Occ3D-Waymo and Occ3D-nuScenes benchmarks. Furthermore, we provide an extensive analysis of the proposed dataset with various baseline models. Lastly, we propose a new model, dubbed Coarse-to-Fine Occupancy (CTF-Occ) network, which demonstrates superior performance on the Occ3D benchmarks. The code, data, and benchmarks are released at \url{https: //tsinghua-mars-lab. github. io/Occ3D/}.

PDF Details

IJCAI Conference 2022 Conference Paper

PRNet: Point-Range Fusion Network for Real-Time LiDAR Semantic Segmentation

  • Xiaoyan Li
  • Gang Zhang
  • Tao Jiang
  • Xufen Cai
  • Zhenhua Wang

Accurate and real-time LiDAR semantic segmentation is necessary for advanced autonomous driving systems. To guarantee a fast inference speed, previous methods utilize the highly optimized 2D convolutions to extract features on the range view (RV), which is the most compact representation of the LiDAR point clouds. However, these methods often suffer from lower accuracy for two reasons: 1) the information loss during the projection from 3D points to the RV, 2) the semantic ambiguity when 3D points labels are assigned according to the RV predictions. In this work, we introduce an end-to-end point-range fusion network (PRNet) that extracts semantic features mainly on the RV and iteratively fuses the RV features back to the 3D points for the final prediction. Besides, a novel range view projection (RVP) operation is designed to alleviate the information loss during the projection to the RV, and a point-range convolution (PRConv) is proposed to automatically mitigate the semantic ambiguity during transmitting features from the RV back to 3D points. Experiments on the SemanticKITTI and nuScenes benchmarks demonstrate that the PRNet pushes the range-based methods to a new state-of-the-art, and achieves a better speed-accuracy trade-off.

PDF Details DOI

IROS Conference 2021 Conference Paper

Look Before You Act: Boosting Pseudo-LiDAR with Online Semantic Embedding

  • Liangjun Zhang
  • Tao Song
  • Tao Jiang
  • Di Xie
  • Shiliang Pu

Vision-based 3D object detection is a research focus in the field of autonomous driving system. While recently proposed pseudo-LiDAR is a promising solution, its performance is severely restricted by the image-based depth estimator, leading to a considerable performance gap against the LiDAR-based counterparts. In this paper, substantial advances are developed along an orthogonal direction to the previous efforts in the pseudo-LiDAR pipeline. Concretely, we propose a plug- and-play module, called Online Semantic Embedding (OSE), aligning image semantics with the pseudo-LiDAR detection in an end-to-end manner. On the KITTI object detection benchmark, existing stereo-based baselines integrated with our approach show impressive improvements without bells and whistles. Furthermore, we emphasize that OSE works in retrieving the performance under geometric imperfection conditions.

Details

AAAI Conference 2021 Conference Paper

LREN: Low-Rank Embedded Network for Sample-Free Hyperspectral Anomaly Detection

  • Kai Jiang
  • Weiying Xie
  • Jie Lei
  • Tao Jiang
  • Yunsong Li

Hyperspectral anomaly detection (HAD) is a challenging task because it explores the intrinsic structure of complex highdimensional signals without any samples at training time. Deep neural networks (DNNs) can dig out the underlying distribution of hyperspectral data but are limited by the labeling of large-scale hyperspectral datasets, especially the low spatial resolution of hyperspectral data, which makes labeling more difficult. To tackle this problem while ensuring the detection performance, we present an unsupervised lowrank embedded network (LREN) in this paper. LREN is a joint learning network in which the latent representation is specifically designed for HAD, rather than merely as a feature input for the detector. And it searches the lowest rank representation based on a representative and discriminative dictionary in the deep latent space to estimate the residual efficiently. Considering the physically mixing properties in hyperspectral imaging, we develop a trainable density estimation module based on Gaussian mixture model (GMM) in the deep latent space to construct a dictionary that can better characterize the complex hyperspectral images (HSIs). The closed-form solution of the proposed low-rank learner surpasses existing approaches on four real hyperspectral datasets with different anomalies. We argue that this unified framework paves a novel way to combine feature extraction and anomaly estimation-based methods for HAD, which intends to learn the underlying representation tailored for HAD without the prerequisite of manually labeled data. Code available at https: //github. com/xdjiangkai/LREN.

PDF Details

AAAI Conference 2020 Conference Paper

End-to-End Unpaired Image Denoising with Conditional Adversarial Networks

  • Zhiwei Hong
  • Xiaocheng Fan
  • Tao Jiang
  • Jianxing Feng

Image denoising is a classic low level vision problem that attempts to recover a noise-free image from a noisy observation. Recent advances in deep neural networks have outperformed traditional prior based methods for image denoising. However, the existing methods either require paired noisy and clean images for training or impose certain assumptions on the noise distribution and data types. In this paper, we present an end-to-end unpaired image denoising framework (UID- Net) that denoises images with only unpaired clean and noisy training images. The critical component of our model is a noise learning module based on a conditional Generative Adversarial Network (cGAN). The model learns the noise distribution from the input noisy images and uses it to transform the input clean images to noisy ones without any assumption on the noise distribution and data types. This process results in pairs of clean and pseudo-noisy images. Such pairs are then used to train another denoising network similar to the existing denoising methods based on paired images. The noise learning and denoising components are integrated together so that they can be trained end-to-end. Extensive experimental evaluation has been performed on both synthetic and real data including real photographs and computer tomography (CT) images. The results demonstrate that our model outperforms the previous models trained on unpaired images as well as the state-of-the-art methods based on paired training data when proper training pairs are unavailable.

PDF Details

JMLR Journal 2020 Journal Article

Recovery of a Mixture of Gaussians by Sum-of-Norms Clustering

  • Tao Jiang
  • Stephen Vavasis
  • Chen Wen Zhai

Sum-of-norms clustering is a method for assigning $n$ points in $\mathbf{R}^d$ to $K$ clusters, $1\le K\le n$, using convex optimization. Recently, Panahi (2017) proved that sum-of-norms clustering is guaranteed to recover a mixture of Gaussians under the restriction that the number of samples is not too large. The purpose of this note is to lift this restriction, that is, show that sum-of-norms clustering can recover a mixture of Gaussians even as the number of samples tends to infinity. Our proof relies on an interesting characterization of clusters computed by sum-of-norms clustering that was developed inside a proof of the agglomeration conjecture by Chiquet et al. (2017). Because we believe this theorem has independent interest, we restate and reprove the Chiquet et al. (2017) result herein. [abs] [ pdf ][ bib ] &copy JMLR 2020. ( edit, beta )

PDF Details

NeurIPS Conference 2020 Conference Paper

Reinforced Molecular Optimization with Neighborhood-Controlled Grammars

  • Chencheng Xu
  • Qiao Liu
  • Minlie Huang
  • Tao Jiang

A major challenge in the pharmaceutical industry is to design novel molecules with specific desired properties, especially when the property evaluation is costly. Here, we propose MNCE-RL, a graph convolutional policy network for molecular optimization with molecular neighborhood-controlled embedding grammars through reinforcement learning. We extend the original neighborhood-controlled embedding grammars to make them applicable to molecular graph generation and design an efficient algorithm to infer grammatical production rules from given molecules. The use of grammars guarantees the validity of the generated molecular structures. By transforming molecular graphs to parse trees with the inferred grammars, the molecular structure generation task is modeled as a Markov decision process where a policy gradient strategy is utilized. In a series of experiments, we demonstrate that our approach achieves state-of-the-art performance in a diverse range of molecular optimization tasks and exhibits significant superiority in optimizing molecular properties with a limited number of property evaluations.

PDF Details

YNICL Journal 2019 Journal Article

A quantitative SVM approach potentially improves the accuracy of magnetic resonance spectroscopy in the preoperative evaluation of the grades of diffuse gliomas

  • Chong Qi
  • Yiming Li
  • Xing Fan
  • Yin Jiang
  • Rui Wang
  • Song Yang
  • Lanxi Meng
  • Tao Jiang

OBJECTIVES: H-MRS) metabolic features and the grade of gliomas, and to establish a machine-learning model to predict the glioma grade. METHODS: H-MRS image. The Student's t-test was conducted to screen for differentially expressed features between low- and high-grade gliomas (WHO grades II and III/IV, respectively). Next, the minimum Redundancy Maximum Relevance (mRMR) algorithm was performed to further select features for a support vector machine (SVM) classifier building. Performance of the predictive model was evaluated both in the training and validation sets using ROC curve analysis. RESULTS: H-MRS metabolic features, thirteen features were differentially expressed. Four features were further selected as grade-predictive imaging signatures using the mRMR algorithm. The predictive performance of the machine-learning model measured by the AUC was 0.825 and 0.820 in the training and validation sets, respectively. This was better than the predictive performances of individual metabolic features, the best of which was 0.812. CONCLUSIONS: H-MRS metabolic features could help in predicting the grade of gliomas. The machine-learning model achieved a better prediction performance in grading gliomas than individual features, indicating that it could complement the traditionally used metabolic features.

Details DOI

YNICL Journal 2018 Journal Article

A radiomic signature as a non-invasive predictor of progression-free survival in patients with lower-grade gliomas

  • Xing Liu
  • Yiming Li
  • Zenghui Qian
  • Zhiyan Sun
  • Kaibin Xu
  • Kai Wang
  • Shuai Liu
  • Xing Fan

OBJECTIVE: The aim of this study was to develop a radiomics signature for prediction of progression-free survival (PFS) in lower-grade gliomas and to investigate the genetic background behind the radiomics signature. METHODS: In this retrospective study, training (n = 216) and validation (n = 84) cohorts were collected from the Chinese Glioma Genome Atlas and the Cancer Genome Atlas, respectively. For each patient, a total of 431 radiomics features were extracted from preoperative T2-weighted magnetic resonance images. A radiomics signature was generated in the training cohort, and its prognostic value was evaluated in both the training and validation cohorts. The genetic characteristics of the group with high-risk scores were identified by radiogenomic analysis, and a nomogram was established for prediction of PFS. RESULTS: There was a significant association between the radiomics signature (including 9 screened radiomics features) and PFS, which was independent of other clinicopathologic factors in both the training (P < 0.001, multivariable Cox regression) and validation (P = 0.045, multivariable Cox regression) cohorts. Radiogenomic analysis revealed that the radiomics signature was associated with the immune response, programmed cell death, cell proliferation, and vasculature development. A nomogram established using the radiomics signature and clinicopathologic risk factors demonstrated high accuracy and good calibration for prediction of PFS in both the training (C-index, 0.684) and validation (C-index, 0.823) cohorts. CONCLUSIONS: PFS can be predicted non-invasively in patients with LGGs by a group of radiomics features that could reflect the biological processes of these tumors.

Details DOI

YNICL Journal 2018 Journal Article

MRI features predict p53 status in lower-grade gliomas via a machine-learning approach

  • Yiming Li
  • Zenghui Qian
  • Kaibin Xu
  • Kai Wang
  • Xing Fan
  • Shaowu Li
  • Tao Jiang
  • Xing Liu

Background: P53 mutation status is a pivotal biomarker for gliomas. Here, we developed a machine-learning model to predict p53 status in lower-grade gliomas based on radiomic features extracted from conventional magnetic resonance (MR) images. Methods: = 92) set. A total of 431 radiomic features were extracted from each patient. The lest absolute shrinkage and selection operator (LASSO) method was used for feature selection and radiomic signature construction. Subsequently, a machine-learning model to predict p53 status was established using the selected features and a Support Vector Machine classifier. The predictive performance of all individual features and the model was calculated using receiver operating characteristic curves in both the training and validation sets. Results: The p53-related radiomic signature was built using the LASSO algorithm; this procedure consisted of four first-order statistics or related wavelet features (including Maximum, Median, Minimum, and Uniformity), a shape and size-based feature (Spherical Disproportion), and ten textural features or related wavelet features (including Correlation, Run Percentage, and Sum Entropy). The prediction accuracies based on the area under the curve were 89.6% in the training set and 76.3% in the validation set, which were better than individual features. Conclusions: These results demonstrate that MR image texture features are predictive of p53 mutation status in lower-grade gliomas. Thus, our procedure can be conveniently used to facilitate presurgical molecular pathological diagnosis.

Details DOI

YNICL Journal 2018 Journal Article

Radiomics analysis allows for precise prediction of epilepsy in patients with low-grade gliomas

  • Zhenyu Liu
  • Yinyan Wang
  • Xing Liu
  • Yang Du
  • Zhenchao Tang
  • Kai Wang
  • Jingwei Wei
  • Di Dong

Purpose To investigate the association between imaging features and low-grade gliomas (LGG) related epilepsy, and to propose a radiomics-based model for the prediction of LGG-associated epilepsy. Methods This retrospective study consecutively enrolled 286 patients with LGGs (194 in the primary cohort and 92 in the validation cohort). T2-weighted MR images (T2WI) were used to characterize risk factors for LGG-related epilepsy: Tumor location features and 3-D imaging features were determined, following which the interactions between these two kinds of features were analyzed. Elastic net was applied to generate a radiomics signature combining key imaging features associated with the LGG-related epilepsy with the primary cohort, and then a nomogram incorporating radiomics signature and clinical characteristics was developed. The radiomics signature and nomogram were validated in the validation cohort. Results A total of 475 features associated with LGG-related epilepsy were obtained for each patient. A radiomics signature with eleven selected features allowed for discriminating patients with epilepsy or not was detected, which performed better than location and 3-D imaging features. The nomogram incorporating radiomics signature and clinical characteristics achieved a high degree of discrimination with area under receiver operating characteristic (ROC) curve (AUC) at 0. 8769 in the primary cohort and 0. 8152 in the validation cohort. The nomogram also allowed for good calibration in the primary cohort. Conclusion We developed and validated an effective prediction model for LGG-related epilepsy. Our results suggested that radiomics analysis may enable more precise and individualized prediction of LGG-related epilepsy.

Details DOI

YNIMG Journal 2014 Journal Article

3D BrainCV: Simultaneous visualization and analysis of cells and capillaries in a whole mouse brain with one-micron voxel resolution

  • Jingpeng Wu
  • Yong He
  • Zhongqin Yang
  • Congdi Guo
  • Qingming Luo
  • Wei Zhou
  • Shangbin Chen
  • Anan LI

Systematic cellular and vascular configurations are essential for understanding fundamental brain anatomy and metabolism. We demonstrated a 3D brainwide cellular and vascular (called 3D BrainCV) visualization and quantitative protocol for a whole mouse brain. We developed a modified Nissl staining method that quickly labeled the cells and blood vessels simultaneously in an entire mouse brain. Terabytes 3D datasets of the whole mouse brains, with unprecedented details of both individual cells and blood vessels, including capillaries, were simultaneously imaged at 1-μm voxel resolution using micro-optical sectioning tomography (MOST). For quantitative analysis, we proposed an automatic image-processing pipeline to perform brainwide vectorization and analysis of cells and blood vessels. Six representative brain regions from the cortex to the deep, including FrA, M1, PMBSF, V1, striatum, and amygdala, and six parameters, including cell number density, vascular length density, fractional vascular volume, distance from the cells to the nearest microvessel, microvascular length density, and fractional microvascular volume, had been quantitatively analyzed. The results showed that the proximity of cells to blood vessels was linearly correlated with vascular length density, rather than the cell number density. The 3D BrainCV made overall snapshots of the detailed picture of the whole brain architecture, which could be beneficial for the state comparison of the developing and diseased brain.

Details DOI

TCS Journal 2009 Journal Article

Separation numbers of trees

  • Tao Jiang
  • Zevi Miller
  • Dan Pritikin

Let G be a graph on n vertices. Given a bijection f: V ( G ) → { 1, 2, …, n }, let | f | = min { | f ( u ) − f ( v ) |: u v ∈ E ( G ) }. The separation number s ( G ) (also known as antibandwidth [T. Calamoneri, A. Massini, L. Török, I. Vrt’o, Antibandwidth of Complete k -ary trees, Electronic Notes in Discrete Mathematics 24 (2006), 259–266; A. Raspaud, H. Schroder, O. Sykora, L. Török, I. Vrt’o, Antibandwidth and cyclic antibandwidth of meshes and hypercubes, Discrete Mathematics 309 (2009) 3541–3552] of G is then max { | f | } over all such bijections f of G. We study the case when G is a forest, obtaining the following results. 1. Let F be a forest in which each component is a star. Then s ( F ) = n − μ 2, where μ is the minimum value of ‖ X | − | Y ‖ over all bipartitions ( X, Y ) of F. 2. Let d be the maximum degree of a tree T on n vertices. Then (a) s ( T ) ≥ n 2 − c 1 n d, and (b) s ( T ) ≥ n 2 − c 2 d 2 log d n, where c 1 and c 2 are absolute constants. We give constructions showing that the bound (a) is asymptotically tight when d is in the range n 1 3 < d ≤ n 12, while (b) is asymptotically tight when d is in the range n q ≤ d ≤ n 1 3, where 0 < q < 1 3 is any fixed constant, and when d ≥ 4 is an absolute constant. We also show that for h ≥ 3 and odd d ≥ 3, we have s ( T h d ) = n 2 − Θ ( d 2 + d h ), where T h d is the symmetric d -ary tree of height h, improving the estimates obtained in the first of the above-mentioned references.

Details DOI

TCS Journal 2007 Journal Article

Complexity and approximation of the minimum recombinant haplotype configuration problem

  • Lan Liu
  • Chen Xi
  • Jing Xiao
  • Tao Jiang

We study the complexity and approximation of the problem of reconstructing haplotypes from genotypes on pedigrees under the Mendelian Law of Inheritance and the minimum recombinant principle (MRHC). First, we show that the MRHC for simple pedigrees where each member has at most one mate and at most one child (i. e. binary-tree pedigrees) is NP-hard. Second, we present some approximation results for the MRHC problem, which are the first approximation results in the literature to the best of our knowledge. We prove that the MRHC on two-locus pedigrees or binary-tree pedigrees with missing data cannot be approximated unless P=NP. Next we show that the MRHC on two-locus pedigrees without missing data cannot be approximated within any constant ratio under the Unique Games Conjecture and can be approximated within the ratio O ( log ( n ) ). Our L-reduction for the approximation hardness gives a simple alternative proof that the MRHC on two-locus pedigrees is NP-hard, which is much easier to understand than the original proof. We also show that the MRHC for tree pedigrees without missing data cannot be approximated within any constant ratio under the Unique Games Conjecture, too. Finally, we explore the hardness and approximation of the MRHC on pedigrees where each member has a bounded number of children and mates mirroring real pedigrees.

Details DOI

TCS Journal 2006 Journal Article

A network flow approach to the Minimum Common Integer Partition Problem

  • Wenbo Zhao
  • Peng Zhang
  • Tao Jiang

In the k-Minimum Common Integer Partition Problem, abbreviated as k-MCIP, we are given k multisets X 1, …, X k of positive integers, the goal is to find an integer multiset T of the minimum size such that for every i, we can partition each of the integers in X i so that the disjoint (multiset) union of their partitions equals T. This problem has applications in computational molecular biology, in particular, ortholog assignment and DNA hybridization fingerprint assembly. The problem is known to be NP-hard for any k ⩾ 2. In this article, we improve the approximation ratio for k-MCIP by viewing this problem as a flow decomposition problem in some flow network. We show an efficient 0. 5625 k -approximation algorithm, improving upon the previously best known 0. 6139 k -approximation algorithm for this problem.

Details DOI

TCS Journal 2006 Journal Article

Approximating the minimum weight weak vertex cover

  • Yong Zhang
  • Qi Ge
  • Rudolf Fleischer
  • Tao Jiang
  • Hong Zhu

Accurate network flow measurement is important for a variety of network applications, where the “flow” over an edge in the network is intuitively the rate of data traffic. The problem of efficiently monitoring the network flow can be regarded as finding the minimum weight weak vertex cover for a given graph. In this paper, we present a ( 2 - 2 ν ( G ) ) -approximation algorithm solving for this problem, which improves previous results, where ν ( G ) is the cyclomatic number of G.

Details DOI

TCS Journal 2003 Journal Article

Approximation algorithms for NMR spectral peak assignment

  • Zhi-Zhong Chen
  • Tao Jiang
  • Guohui Lin
  • Jianjun Wen
  • Dong Xu
  • Jinbo Xu
  • Ying Xu

We study a constrained bipartite matching problem where the input is a weighted bipartite graph G=(U, V, E), U is a set of vertices following a sequential order, V is another set of vertices partitioned into a collection of disjoint subsets, each following a sequential order, and E is a set of edges between U and V with non-negative weights. The objective is to find a matching in G with the maximum weight that satisfies the given sequential orders on both U and V, i. e. if u i+1 follows u i in U and if v j+1 follows v j in V, then u i is matched with v j if and only if u i+1 is matched with v j+1. The problem has recently been formulated as a crucial step in an algorithmic approach for interpreting NMR spectral data (IEEE Comput. Sci. Eng. 4 (2002) 50–62). The interpretation of NMR spectral data is known as a key problem in protein structure determination via NMR spectroscopy. Unfortunately, the constrained bipartite matching problem is NP-hard (IEEE Comput. Sci. Eng. 4 (2002) 50–62). We first propose a 2-approximation algorithm for the problem, which follows directly from the recent result of Bar-Noy et al. (Proc. 32nd ACM Symp. on Theory of Computing (STOC’00), 2000, pp. 735–744) on interval scheduling. However, our extensive experimental results on real NMR spectral data illustrate that the algorithm performs poorly in terms of recovering target-matching edges. We then propose another approximation algorithm that tries to take advantage of the “density” of the sequential order information in V. Although we are only able to prove an approximation ratio of 3 log 2 D for this algorithm, where D is the length of a longest string in V, the experimental results demonstrate that this new algorithm performs much better on real data, i. e. it is able to recover a large fraction of target-matching edges and the weight of its output matching is often in fact close to the maximum. We also prove that the problem is MAX SNP-hard, even if the input bipartite graph is unweighted. We further present an approximation algorithm for a nontrivial special case that breaks the ratio 2 barrier.

Details DOI

NeurIPS Conference 2003 Conference Paper

Efficient and Robust Feature Extraction by Maximum Margin Criterion

  • Haifeng Li
  • Tao Jiang
  • Keshu Zhang

A new feature extraction criterion, maximum margin criterion (MMC), is proposed in this paper. This new criterion is general in the sense that, when combined with a suitable constraint, it can actually give rise to the most popular feature extractor in the literature, linear discriminate analysis (LDA). We derive a new feature extractor based on MMC using a different constraint that does not depend on the nonsingularity of the within-class scatter matrix Sw. Such a dependence is a major drawback of LDA especially when the sample size is small. The kernelized (nonlin- ear) counterpart of this linear feature extractor is also established in this paper. Our preliminary experimental results on face images demonstrate that the new feature extractors are efficient and stable.

PDF Details

TCS Journal 2000 Journal Article

New applications of the incompressibility method: Part II

  • Harry Buhrman
  • Tao Jiang
  • Ming Li
  • Paul Vitányi

The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas (Li and Vitányi, An Introduction to Kolmogorov Complexity and its Applications, Springer, New york, 1997). To further demonstrate its power and elegance we exhibit new simple proofs using the incompressibility method.

Details DOI

I&C Journal 1996 Journal Article

Lower Bounds on Learning Decision Lists and Trees

  • Thomas Hancock
  • Tao Jiang
  • Ming Li
  • John Tromp

k-Decision lists and decision trees play important roles in learning theory as well as in practical learning systems. k-Decision lists generalize classes such as monomials, k-DNF, andk-CNF, and like these subclasses they are polynomially PAC-learnable [R. Rivest, Mach. Learning 2(1987), 229–246]. This leaves open the question of whetherk-decision lists can be learned as efficiently ask-DNF. We answer this question negatively in a certain sense, thus disproving a claim in a popular textbook [M. Anthony and N. Biggs, “Computational Learning Theory, ” Cambridge Univ. Press, Cambridge, UK, 1992]. Decision trees, on the other hand, are not even known to be polynomially PAC-learnable, despite their widespread practical application. We will show that decision trees are not likely to be efficiently PAC-learnable. We summarize our specific results. The following problems cannot be approximated in polynomial time within a factor of 2log δ n for anyδ<1, unlessNP⊂DTIME[2 polylogn ]: a generalized set cover, k-decision lists, k-decision lists by monotone decision lists, and decision trees. Decision lists cannot be approximated in polynomial time within a factor ofnδ, for some constantδ>0, unlessNP=P. Also, k-decision lists withl0–1 alternations cannot be approximated within a factor log l nunlessNP⊂DTIME[n O(loglog n)] (providing an interesting comparison to the upper bound obtained by A. Dhagat and L. Hellerstein [in“FOCS '94, ” pp. 64–74]).

Details DOI

TCS Journal 1995 Journal Article

Alignment of trees — an alternative to tree edit

  • Tao Jiang
  • Lusheng Wang
  • Kaizhong Zhang

In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time complexity of this algorithm is O(|T 1|·|T 2·(deg(T 1) + deg(T 2))2), where |T 1| is the number of nodes in T 1 and deg(T 1) is the degree of T 1, i = 1. 2. The algorithm is faster than the best known algorithm for tree edit when deg(T 1) and deg(T 2) are smaller than the depths of T 1 and T 2. For unordered trees, we show that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes MAX SNP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is MAX SNP-hard even if both trees have a bounded degree (Zhang and Jiang, 1994). Finally, multiple alignment of trees is discussed.

Details DOI

TCS Journal 1995 Journal Article

Shortest consistent superstrings computable in polynomial time

  • Tao Jiang
  • Vadim G. Timkovsky

The shortest consistent superstring problem is, given a set of positive strings and a set of negative strings, finding a shortest string including every positive string and no negative string as a substring. This problem is NP-hard and arises in DNA sequencing by hybridization. It is also an extension of the well-known shortest common superstring problem which corresponds to the case when the set of negative strings is empty. In this paper we show that a shortest consistent superstring can be found in polynomial time if (i) a longest common nonsuperstring for the set of negative strings exists or (ii) the number of positive strings is bounded and every symbol of the alphabet appears at the end of some negative string. In the case (i) a longest consistent superstring can also be found in polynomial time.

Details DOI

TCS Journal 1994 Journal Article

Approximating shortest superstrings with constraints

  • Tao Jiang
  • Ming Li

Various versions of the shortest common superstring problem play important roles in data compression and DNA sequencing. Only recently, the open problem of how to approximate a shortest superstring given a set of strings was solved in (Blum, 1991; Li, 1990). Blum (1991) shows that several greedy algorithms produce a superstring of length O(n), where n is the optimal length. However, a major problem remains open: can we still linearly approximate a superstring in polynomial time when the superstring is required to be consistent with some given negative strings, i. e. , it must not contain any negative string? The best previous algorithm, Group-Merge given in (Jiang and Li, 1993; Li, 1990), produces a consistent superstring of length θ(n log n). The negative strings make the problem much more difficult and, as we will show, a greedy-style algorithm cannot achieve linear approximation for this problem. We present polynomial-time approximation algorithms that produce consistent superstrings of length O(n), for two important special cases: (a) when no negative strings contain positive strings as substrings; (b) when there are only a constant number of negative strings. The algorithms are obtained by making an essential use of the Hungarian algorithm, which can find an optimal cycle cover on weighted graphs. The other main objective of this paper is to analyze the performance of some greedy-style algorithms for this problem. Due to their time efficiency and simplicity, greedy algorithms are of practical importance. We introduce a new analysis showing that when no negative strings contain positive strings, a greedy algorithm achieves O(n 4 3 ) and O(n) if the number of negative examples is further bounded by some constant.

Details DOI

TCS Journal 1994 Journal Article

Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata

  • Tao Jiang
  • Oscar H. Ibarra
  • Hui Wang

A two-dimensional nondeterministic on-line tessellation acceptor (2-NOTA) is a special type of real-time two-dimensional nondeterministic cellular automaton in which data flows from the upper-left corner to the lower-right corner. A two-dimensional alternating finite automaton (2-AFA) is an alternating finite automaton with a two-dimensional rectangular input whose input head can move in all four directions on the input. In this paper, we show that 2-NOTAs and 2-AFAs are incomparable. This answers in the negative an open question posed by Ito (this journal, 1989). Closure properties of the classes of languages (i. e. , sets of two-dimensional patterns) accepted by two-way, three-way, and four-way two-dimensional alternating finite automata and two-dimensional alternating finite automata with only universal states (2-UFAs) are also obtained which answer several open questions posed by Inoue and Takanami (1988).

Details DOI

TCS Journal 1992 Journal Article

A characterization of exponential-time languages by alternating context-free grammars

  • Oscar H. Ibarra
  • Tao Jiang
  • Hui Wang

We show that the class of exponential-time languages or, equivalently, the class of languages accepted by alternating pushdown automata (APDAs), is exactly the class of languages generated by linear-erasing alternating context-free grammars (ACFGs). An ACFG is generalization of an ordinary context-free grammar in which we allow the use of universal nonterminals in much the same way as universal states are used in APDAs. It was recently claimed in [9] that APDAs are equivalent to ACFGs. However, the proofs in both directions have major flaws which do not seem to be correctable. As it turns out, the proof of the claim does not follow from a simple extension of the well-known constructions for the nonalternating case. Our proof is, in fact, for a modified claim: APDAs are equivalent to linear-erasing ACFGs, where linear-erasing means that there is a constant c such that every string of length n in the language generated by the ACFG has a derivation in which all intermediate sentential forms are at most cn long.

Details DOI

I&C Journal 1992 Journal Article

The synchronization of nonuniform networks of finite automata

  • Tao Jiang

The generalized firing squad synchronization problem (gfssp) is the well-known firing squad synchronization problem (fssp) extended to arbitrarily connected networks of finite automata. Here, the transmission delays associated with the links of a network are assumed to be 0; i. e. , a signal can get through a link in no time. When the delays are allowed to be arbitrary nonnegative integers, the problem is called gfssp-nud (i. e. , gfssp with nonuniform delays). We give for the first time a solution of gfssp-nud. The solution is independent of the structure of the network and the actual delays of the links. The firing time of the solution is bounded by O(Δ 3+τ max), where τ max is the maximum transmission delay of any single link and Δ is the maximum transmission delay between the general and any other node of a given network. This answers an open question in Mazoyer (in “Automata Networks” (C. Choffrut, Ed.), pp. 82–93, Springer-Verlag, Berlin/New York, 1986). Our result is based on a strategy different from the one of Balzer and Waksman, which is used in almost all existing solutions of fssp and gfssp. The extension of gfssp and gfssp-nud to networks with more than one general is also considered. We show that (1) for any fixed k≥2, gfssp with at most k generals has a solution whose firing time is bounded by O(D), where D is the maximum distance between any two nodes of a given network, and gfssp-nud with at most k generals has a solution whose firing time is bounded by O((Φ+τ max)3), where Φ is the maximum transmission delay between any two nodes of a given network; (2) there are no solutions for gfssp and gfssp-nud with an arbitrary number of generals.

Details DOI

TCS Journal 1991 Journal Article

Parallel parsing on a one-way linear array of finite-state machines

  • Oscar H. Ibarra
  • Tao Jiang
  • Hui Wang

Efficient parallel algorithms for some parsing problems are presented. These problems include the parsing of linear context-free languages, languages accepted by nondeterministic one-counter automata, and transductions defined by a special class of two-tape nondeterministic finite-state transducers. The model of parallel computation is a one-way linear array of identical finite-state machines. The data movement in the array is one-way, from left to right. For inputs of length n, the array uses n nodes. Our algorithms can actually produce a parse, i. e. a sequence of rules (moves) that generates (accepts) an input, in linear time. When only a no/yes answer is required, the parsing problem becomes a recognition problem. The best serial (RAM) algorithms for the corresponding recognition problems take O(n 2/log2 n) time and space. Previous parallel algorithms for the recognition problems run in linear time on a one-way linear array of finite-state machines.

Details DOI

I&C Journal 1991 Journal Article

Some classes of languages in NC1

  • Oscar H. Ibarra
  • Tao Jiang
  • Jik H. Chang
  • Bala Ravikumar

We show the containment of several classes of languages in NC1. These include the binary encodings of semilinear sets and some subclasses of context-free languages. We also investigate the closure properties of NC1.

Details DOI

TCS Journal 1990 Journal Article

On the complexity of 1–tape ATMs and off-line 1-tape ATMs running in constant reversals

  • Tao Jiang

Yamamoto and Noguchi raised the question of whether every recursively enumerable set can be accepted by a 1-tape or off-line 1-tape alternating Turing machine (ATM) whose (work)tape head makes only a constant number of reversals. In this paper, we answer the open question in the negative. We show that (1) constant-reversal 1-tape ATMs accept only regular languages and (2) there exists a recursive function h(k, r, n) such that for every k-state off-line 1-tape ATM, M, running in r reversals, the language accepted by M is in ASPACE(h(k, r, n)).

Details DOI

TCS Journal 1988 Journal Article

Relating the power of cellular arrays to their closure properties

  • Oscar H. Ibarra
  • Tao Jiang

There are many fundamental open problems concerning cellular arrays (CA's). For example: (1) Is the class of real-time CA languages closed under reversal (concatenation)? (2) (2) Are linear-time CA's more powerful than real-time CA's? (3) (3) Are nonlinear-time CA's more powerful than linear-time CA's? 4 (4) Does one-way communication reduce the computing power of a CA? Although some of these problems appear to be easier to resolve than the others, e. g. , problem (1) seems easier than (2), no solution to any of these problems is forthcoming. In this paper, we investigate the relationships among these problems as well as prove some positive results concerning CA's. We show: a (a) the class of real-time CA languages is closed under reversal if and only if linear-time CA's are equivalent to real-time CA's; b if CA's are more powerful than CA's restricted to one-way data communication (i. e. , one-way CA's), then nonlinear-time CA's are more powerful than linear-time CA's; c (c) if the class of real-time CA languages is closed under reversal, then it is also closed under concatenation. In the case of unary CA languages, we show that the class is closed under concatenation. We also show that the languageL={0 n 1 m |m, n>0, mdividesn}is a real-time CA language, disproving a conjecture of Bucher and Culik.

Details DOI
v2026.09.13