Showing 1–50 of 59 results for author: Tong, J

Adaptive Perturbation Enhanced SCL Decoder for Polar Codes

Authors: Xianbin Wang, Huazi Zhang, Jiajie Tong, Jun Wang, Wen Tong

Abstract: For polar codes, successive cancellation list (SCL) decoding algorithm significantly improves finite-length performance compared to SC decoding. SCL-flip decoding can further enhance the performance but the gain diminishes as code length increases, due to the difficulty in locating the first error bit position. In this work, we introduce an SCL-perturbation decoding algorithm to address this issue… ▽ More For polar codes, successive cancellation list (SCL) decoding algorithm significantly improves finite-length performance compared to SC decoding. SCL-flip decoding can further enhance the performance but the gain diminishes as code length increases, due to the difficulty in locating the first error bit position. In this work, we introduce an SCL-perturbation decoding algorithm to address this issue. A basic version of the algorithm introduces small random perturbations to the received symbols before each SCL decoding attempt, and exhibits non-diminishing gain at large block lengths. Its enhanced version adaptively performs random perturbations or directional perturbation on each received symbol according to previous decoding results, and managed to correct more errors with fewer decoding attempts. Extensive simulation results demonstrate stable gains across various code rates, lengths and list sizes. To the best of our knowledge, this is the first SCL enhancement with non-diminishing gains as code length increases, and achieves unprecedented efficiency. With only one additional SCL-$L$ decoding attempt (in total two), the proposed algorithm achieves SCL-$2L$-equivalent performance. Since the gain is obtained without increasing list size, the algorithm is best suited for hardware implementation. △ Less

Submitted 3 July, 2024; originally announced July 2024.

LLaMA-MoE: Building Mixture-of-Experts from LLaMA with Continual Pre-training

Authors: Tong Zhu, Xiaoye Qu, Daize Dong, Jiacheng Ruan, Jingqi Tong, Conghui He, Yu Cheng

Abstract: Mixture-of-Experts (MoE) has gained increasing popularity as a promising framework for scaling up large language models (LLMs). However, training MoE from scratch in a large-scale setting still suffers from data-hungry and instability problems. Motivated by this limit, we investigate building MoE models from existing dense large language models. Specifically, based on the well-known LLaMA-2 7B mod… ▽ More Mixture-of-Experts (MoE) has gained increasing popularity as a promising framework for scaling up large language models (LLMs). However, training MoE from scratch in a large-scale setting still suffers from data-hungry and instability problems. Motivated by this limit, we investigate building MoE models from existing dense large language models. Specifically, based on the well-known LLaMA-2 7B model, we obtain an MoE model by: (1) Expert Construction, which partitions the parameters of original Feed-Forward Networks (FFNs) into multiple experts; (2) Continual Pre-training, which further trains the transformed MoE model and additional gate networks. In this paper, we comprehensively explore different methods for expert construction and various data sampling strategies for continual pre-training. After these stages, our LLaMA-MoE models could maintain language abilities and route the input tokens to specific experts with part of the parameters activated. Empirically, by training 200B tokens, LLaMA-MoE-3.5B models significantly outperform dense models that contain similar activation parameters. The source codes and models are available at https://github.com/pjlab-sys4nlp/llama-moe . △ Less

Submitted 24 June, 2024; originally announced June 2024.

A Federated Online Restless Bandit Framework for Cooperative Resource Allocation

Authors: Jingwen Tong, Xinran Li, Liqun Fu, Jun Zhang, Khaled B. Letaief

Abstract: Restless multi-armed bandits (RMABs) have been widely utilized to address resource allocation problems with Markov reward processes (MRPs). Existing works often assume that the dynamics of MRPs are known prior, which makes the RMAB problem solvable from an optimization perspective. Nevertheless, an efficient learning-based solution for RMABs with unknown system dynamics remains an open problem. In… ▽ More Restless multi-armed bandits (RMABs) have been widely utilized to address resource allocation problems with Markov reward processes (MRPs). Existing works often assume that the dynamics of MRPs are known prior, which makes the RMAB problem solvable from an optimization perspective. Nevertheless, an efficient learning-based solution for RMABs with unknown system dynamics remains an open problem. In this paper, we study the cooperative resource allocation problem with unknown system dynamics of MRPs. This problem can be modeled as a multi-agent online RMAB problem, where multiple agents collaboratively learn the system dynamics while maximizing their accumulated rewards. We devise a federated online RMAB framework to mitigate the communication overhead and data privacy issue by adopting the federated learning paradigm. Based on this framework, we put forth a Federated Thompson Sampling-enabled Whittle Index (FedTSWI) algorithm to solve this multi-agent online RMAB problem. The FedTSWI algorithm enjoys a high communication and computation efficiency, and a privacy guarantee. Moreover, we derive a regret upper bound for the FedTSWI algorithm. Finally, we demonstrate the effectiveness of the proposed algorithm on the case of online multi-user multi-channel access. Numerical results show that the proposed algorithm achieves a fast convergence rate of $\mathcal{O}(\sqrt{T\log(T)})$ and better performance compared with baselines. More importantly, its sample complexity decreases with the number of agents. △ Less

Submitted 12 June, 2024; originally announced June 2024.

WirelessLLM: Empowering Large Language Models Towards Wireless Intelligence

Authors: Jiawei Shao, Jingwen Tong, Qiong Wu, Wei Guo, Zijian Li, Zehong Lin, Jun Zhang

Abstract: The rapid evolution of wireless technologies and the growing complexity of network infrastructures necessitate a paradigm shift in how communication networks are designed, configured, and managed. Recent advancements in Large Language Models (LLMs) have sparked interest in their potential to revolutionize wireless communication systems. However, existing studies on LLMs for wireless systems are li… ▽ More The rapid evolution of wireless technologies and the growing complexity of network infrastructures necessitate a paradigm shift in how communication networks are designed, configured, and managed. Recent advancements in Large Language Models (LLMs) have sparked interest in their potential to revolutionize wireless communication systems. However, existing studies on LLMs for wireless systems are limited to a direct application for telecom language understanding. To empower LLMs with knowledge and expertise in the wireless domain, this paper proposes WirelessLLM, a comprehensive framework for adapting and enhancing LLMs to address the unique challenges and requirements of wireless communication networks. We first identify three foundational principles that underpin WirelessLLM: knowledge alignment, knowledge fusion, and knowledge evolution. Then, we investigate the enabling technologies to build WirelessLLM, including prompt engineering, retrieval augmented generation, tool usage, multi-modal pre-training, and domain-specific fine-tuning. Moreover, we present three case studies to demonstrate the practical applicability and benefits of WirelessLLM for solving typical problems in wireless networks. Finally, we conclude this paper by highlighting key challenges and outlining potential avenues for future research. △ Less

Submitted 15 June, 2024; v1 submitted 27 May, 2024; originally announced May 2024.

FEATHER: A Reconfigurable Accelerator with Data Reordering Support for Low-Cost On-Chip Dataflow Switching

Authors: Jianming Tong, Anirudh Itagi, Prasanth Chatarasi, Tushar Krishna

Abstract: The inference of ML models composed of diverse structures, types, and sizes boils down to the execution of different dataflows (i.e. different tiling, ordering, parallelism, and shapes). Using the optimal dataflow for every layer of workload can reduce latency by up to two orders of magnitude over a suboptimal dataflow. Unfortunately, reconfiguring hardware for different dataflows involves on-chip… ▽ More The inference of ML models composed of diverse structures, types, and sizes boils down to the execution of different dataflows (i.e. different tiling, ordering, parallelism, and shapes). Using the optimal dataflow for every layer of workload can reduce latency by up to two orders of magnitude over a suboptimal dataflow. Unfortunately, reconfiguring hardware for different dataflows involves on-chip data layout reordering and datapath reconfigurations, leading to non-trivial overhead that hinders ML accelerators from exploiting different dataflows, resulting in suboptimal performance. To address this challenge, we propose FEATHER, an innovative accelerator that leverages a novel spatial array termed Nest and a novel multi-stage reduction network called BIRRD for performing flexible data reduction with layout reordering under the hood, enabling seamless switching between optimal dataflows with negligible latency and resources overhead. For systematically evaluating the performance interaction between dataflows and layouts, we enhance Timeloop, a state-of-the-art dataflow cost modeling and search framework, with layout assessment capabilities, and term it as Layoutloop. We model FEATHER into Layoutloop and also deploy FEATHER end-to-end on the edge ZCU104 FPGA. FEATHER delivers 1.27~2.89x inference latency speedup and 1.3~6.43x energy efficiency improvement compared to various SoTAs like NVDLA, SIGMA and Eyeriss under ResNet-50 and MobiletNet-V3 in Layoutloop. On practical FPGA devices, FEATHER achieves 2.65/3.91x higher throughput than Xilinx DPU/Gemmini. Remarkably, such performance and energy efficiency enhancements come at only 6% area over a fixed-dataflow Eyeriss-like accelerator. Our code is released at https://github.com/maeri-project/FEATHER. △ Less

Submitted 21 May, 2024; originally announced May 2024.

Comments: 17 pages, 14 figures. International Symposium on Computer Architecture (ISCA), Jun 2024

EdgeLoc: A Communication-Adaptive Parallel System for Real-Time Localization in Infrastructure-Assisted Autonomous Driving

Authors: Boyi Liu, Jingwen Tong, Yufan Zhuang

Abstract: This paper presents EdgeLoc, an infrastructure-assisted, real-time localization system for autonomous driving that addresses the incompatibility between traditional localization methods and deep learning approaches. The system is built on top of the Robot Operating System (ROS) and combines the real-time performance of traditional methods with the high accuracy of deep learning approaches. The sys… ▽ More This paper presents EdgeLoc, an infrastructure-assisted, real-time localization system for autonomous driving that addresses the incompatibility between traditional localization methods and deep learning approaches. The system is built on top of the Robot Operating System (ROS) and combines the real-time performance of traditional methods with the high accuracy of deep learning approaches. The system leverages edge computing capabilities of roadside units (RSUs) for precise localization to enhance on-vehicle localization that is based on the real-time visual odometry. EdgeLoc is a parallel processing system, utilizing a proposed uncertainty-aware pose fusion solution. It achieves communication adaptivity through online learning and addresses fluctuations via window-based detection. Moreover, it achieves optimal latency and maximum improvement by utilizing auto-splitting vehicle-infrastructure collaborative inference, as well as online distribution learning for decision-making. Even with the most basic end-to-end deep neural network for localization estimation, EdgeLoc realizes a 67.75\% reduction in the localization error for real-time local visual odometry, a 29.95\% reduction for non-real-time collaborative inference, and a 30.26\% reduction compared to Kalman filtering. Finally, accuracy-to-latency conversion was experimentally validated, and an overall experiment was conducted on a practical cellular network. The system is open sourced at https://github.com/LoganCome/EdgeAssistedLocalization. △ Less

Submitted 8 June, 2024; v1 submitted 20 May, 2024; originally announced May 2024.

Exploring the Compositional Deficiency of Large Language Models in Mathematical Reasoning

Authors: Jun Zhao, Jingqi Tong, Yurong Mou, Ming Zhang, Qi Zhang, Xuanjing Huang

Abstract: Human cognition exhibits systematic compositionality, the algebraic ability to generate infinite novel combinations from finite learned components, which is the key to understanding and reasoning about complex logic. In this work, we investigate the compositionality of large language models (LLMs) in mathematical reasoning. Specifically, we construct a new dataset \textsc{MathTrap}\footnotemark[3]… ▽ More Human cognition exhibits systematic compositionality, the algebraic ability to generate infinite novel combinations from finite learned components, which is the key to understanding and reasoning about complex logic. In this work, we investigate the compositionality of large language models (LLMs) in mathematical reasoning. Specifically, we construct a new dataset \textsc{MathTrap}\footnotemark[3] by introducing carefully designed logical traps into the problem descriptions of MATH and GSM8k. Since problems with logical flaws are quite rare in the real world, these represent ``unseen'' cases to LLMs. Solving these requires the models to systematically compose (1) the mathematical knowledge involved in the original problems with (2) knowledge related to the introduced traps. Our experiments show that while LLMs possess both components of requisite knowledge, they do not \textbf{spontaneously} combine them to handle these novel cases. We explore several methods to mitigate this deficiency, such as natural language prompts, few-shot demonstrations, and fine-tuning. We find that LLMs' performance can be \textbf{passively} improved through the above external intervention. Overall, systematic compositionality remains an open challenge for large language models. △ Less

Submitted 11 July, 2024; v1 submitted 5 May, 2024; originally announced May 2024.

Accurate Low-Degree Polynomial Approximation of Non-polynomial Operators for Fast Private Inference in Homomorphic Encryption

Authors: Jianming Tong, Jingtian Dang, Anupam Golder, Callie Hao, Arijit Raychowdhury, Tushar Krishna

Abstract: As machine learning (ML) permeates fields like healthcare, facial recognition, and blockchain, the need to protect sensitive data intensifies. Fully Homomorphic Encryption (FHE) allows inference on encrypted data, preserving the privacy of both data and the ML model. However, it slows down non-secure inference by up to five magnitudes, with a root cause of replacing non-polynomial operators (ReLU… ▽ More As machine learning (ML) permeates fields like healthcare, facial recognition, and blockchain, the need to protect sensitive data intensifies. Fully Homomorphic Encryption (FHE) allows inference on encrypted data, preserving the privacy of both data and the ML model. However, it slows down non-secure inference by up to five magnitudes, with a root cause of replacing non-polynomial operators (ReLU and MaxPooling) with high-degree Polynomial Approximated Function (PAF). We propose SmartPAF, a framework to replace non-polynomial operators with low-degree PAF and then recover the accuracy of PAF-approximated model through four techniques: (1) Coefficient Tuning (CT) -- adjust PAF coefficients based on the input distributions before training, (2) Progressive Approximation (PA) -- progressively replace one non-polynomial operator at a time followed by a fine-tuning, (3) Alternate Training (AT) -- alternate the training between PAFs and other linear operators in the decoupled manner, and (4) Dynamic Scale (DS) / Static Scale (SS) -- dynamically scale PAF input value within (-1, 1) in training, and fix the scale as the running max value in FHE deployment. The synergistic effect of CT, PA, AT, and DS/SS enables SmartPAF to enhance the accuracy of the various models approximated by PAFs with various low degrees under multiple datasets. For ResNet-18 under ImageNet-1k, the Pareto-frontier spotted by SmartPAF in latency-accuracy tradeoff space achieves 1.42x ~ 13.64x accuracy improvement and 6.79x ~ 14.9x speedup than prior works. Further, SmartPAF enables a 14-degree PAF (f1^2 g_1^2) to achieve 7.81x speedup compared to the 27-degree PAF obtained by minimax approximation with the same 69.4% post-replacement accuracy. Our code is available at https://github.com/EfficientFHE/SmartPAF. △ Less

Submitted 7 May, 2024; v1 submitted 4 April, 2024; originally announced April 2024.

Comments: Proceedings of the 5th MLSys Conference, Santa Clara, CA, USA, 2024. Copyright 2024 by the author(s)

EMONA: Event-level Moral Opinions in News Articles

Authors: Yuanyuan Lei, Md Messal Monem Miah, Ayesha Qamar, Sai Ramana Reddy, Jonathan Tong, Haotian Xu, Ruihong Huang

Abstract: Most previous research on moral frames has focused on social media short texts, little work has explored moral sentiment within news articles. In news articles, authors often express their opinions or political stance through moral judgment towards events, specifically whether the event is right or wrong according to social moral rules. This paper initiates a new task to understand moral opinions… ▽ More Most previous research on moral frames has focused on social media short texts, little work has explored moral sentiment within news articles. In news articles, authors often express their opinions or political stance through moral judgment towards events, specifically whether the event is right or wrong according to social moral rules. This paper initiates a new task to understand moral opinions towards events in news articles. We have created a new dataset, EMONA, and annotated event-level moral opinions in news articles. This dataset consists of 400 news articles containing over 10k sentences and 45k events, among which 9,613 events received moral foundation labels. Extracting event morality is a challenging task, as moral judgment towards events can be very implicit. Baseline models were built for event moral identification and classification. In addition, we also conduct extrinsic evaluations to integrate event-level moral opinions into three downstream tasks. The statistical analysis and experiments show that moral opinions of events can serve as informative features for identifying ideological bias or subjective events. △ Less

Submitted 2 April, 2024; originally announced April 2024.

Comments: Accepted to NAACL 2024

From Learning to Analytics: Improving Model Efficacy with Goal-Directed Client Selection

Authors: Jingwen Tong, Zhenzhen Chen, Liqun Fu, Jun Zhang, Zhu Han

Abstract: Federated learning (FL) is an appealing paradigm for learning a global model among distributed clients while preserving data privacy. Driven by the demand for high-quality user experiences, evaluating the well-trained global model after the FL process is crucial. In this paper, we propose a closed-loop model analytics framework that allows for effective evaluation of the trained global model using… ▽ More Federated learning (FL) is an appealing paradigm for learning a global model among distributed clients while preserving data privacy. Driven by the demand for high-quality user experiences, evaluating the well-trained global model after the FL process is crucial. In this paper, we propose a closed-loop model analytics framework that allows for effective evaluation of the trained global model using clients' local data. To address the challenges posed by system and data heterogeneities in the FL process, we study a goal-directed client selection problem based on the model analytics framework by selecting a subset of clients for the model training. This problem is formulated as a stochastic multi-armed bandit (SMAB) problem. We first put forth a quick initial upper confidence bound (Quick-Init UCB) algorithm to solve this SMAB problem under the federated analytics (FA) framework. Then, we further propose a belief propagation-based UCB (BP-UCB) algorithm under the democratized analytics (DA) framework. Moreover, we derive two regret upper bounds for the proposed algorithms, which increase logarithmically over the time horizon. The numerical results demonstrate that the proposed algorithms achieve nearly optimal performance, with a gap of less than 1.44% and 3.12% under the FA and DA frameworks, respectively. △ Less

Submitted 30 March, 2024; originally announced April 2024.

Comments: This work was partly presented at IEEE ICC 2022

MSC Class: 14J60 ACM Class: I.2.7

Optimization Over Trained Neural Networks: Taking a Relaxing Walk

Authors: Jiatai Tong, Junyang Cai, Thiago Serra

Abstract: Besides training, mathematical optimization is also used in deep learning to model and solve formulations over trained neural networks for purposes such as verification, compression, and optimization with learned constraints. However, solving these formulations soon becomes difficult as the network size grows due to the weak linear relaxation and dense constraint matrix. We have seen improvements… ▽ More Besides training, mathematical optimization is also used in deep learning to model and solve formulations over trained neural networks for purposes such as verification, compression, and optimization with learned constraints. However, solving these formulations soon becomes difficult as the network size grows due to the weak linear relaxation and dense constraint matrix. We have seen improvements in recent years with cutting plane algorithms, reformulations, and an heuristic based on Mixed-Integer Linear Programming (MILP). In this work, we propose a more scalable heuristic based on exploring global and local linear relaxations of the neural network model. Our heuristic is competitive with a state-of-the-art MILP solver and the prior heuristic while producing better solutions with increases in input, depth, and number of neurons. △ Less

Submitted 28 January, 2024; v1 submitted 7 January, 2024; originally announced January 2024.

Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming

Authors: Hongcheng Liu, Jindong Tong

Abstract: This paper studies sample average approximation (SAA) in solving convex or strongly convex stochastic programming problems. Under some common regularity conditions, we show -- perhaps for the first time -- that SAA's sample complexity can be completely free from any quantification of metric entropy (such as the logarithm of the covering number), leading to a significantly more efficient rate with… ▽ More This paper studies sample average approximation (SAA) in solving convex or strongly convex stochastic programming problems. Under some common regularity conditions, we show -- perhaps for the first time -- that SAA's sample complexity can be completely free from any quantification of metric entropy (such as the logarithm of the covering number), leading to a significantly more efficient rate with dimensionality $d$ than most existing results. From the newly established complexity bounds, an important revelation is that SAA and the canonical stochastic mirror descent (SMD) method, two mainstream solution approaches to SP, entail almost identical rates of sample efficiency, rectifying a persistent theoretical discrepancy of SAA from SMD by the order of $O(d)$. Furthermore, this paper explores non-Lipschitzian scenarios where SAA maintains provable efficacy but the corresponding results for SMD remain mostly unexplored, indicating the potential of SAA's better applicability in some irregular settings. △ Less

Submitted 13 June, 2024; v1 submitted 31 December, 2023; originally announced January 2024.

MSC Class: 90C15; 90C25; 60-08

Collaborative Camouflaged Object Detection: A Large-Scale Dataset and Benchmark

Authors: Cong Zhang, Hongbo Bi, Tian-Zhu Xiang, Ranwan Wu, Jinghui Tong, Xiufang Wang

Abstract: In this paper, we provide a comprehensive study on a new task called collaborative camouflaged object detection (CoCOD), which aims to simultaneously detect camouflaged objects with the same properties from a group of relevant images. To this end, we meticulously construct the first large-scale dataset, termed CoCOD8K, which consists of 8,528 high-quality and elaborately selected images with objec… ▽ More In this paper, we provide a comprehensive study on a new task called collaborative camouflaged object detection (CoCOD), which aims to simultaneously detect camouflaged objects with the same properties from a group of relevant images. To this end, we meticulously construct the first large-scale dataset, termed CoCOD8K, which consists of 8,528 high-quality and elaborately selected images with object mask annotations, covering 5 superclasses and 70 subclasses. The dataset spans a wide range of natural and artificial camouflage scenes with diverse object appearances and backgrounds, making it a very challenging dataset for CoCOD. Besides, we propose the first baseline model for CoCOD, named bilateral-branch network (BBNet), which explores and aggregates co-camouflaged cues within a single image and between images within a group, respectively, for accurate camouflaged object detection in given images. This is implemented by an inter-image collaborative feature exploration (CFE) module, an intra-image object feature search (OFS) module, and a local-global refinement (LGR) module. We benchmark 18 state-of-the-art models, including 12 COD algorithms and 6 CoSOD algorithms, on the proposed CoCOD8K dataset under 5 widely used evaluation metrics. Extensive experiments demonstrate the effectiveness of the proposed method and the significantly superior performance compared to other competitors. We hope that our proposed dataset and model will boost growth in the COD community. The dataset, model, and results will be available at: https://github.com/zc199823/BBNet--CoCOD. △ Less

Submitted 6 October, 2023; originally announced October 2023.

Comments: Accepted by IEEE Transactions on Neural Networks and Learning Systems (TNNLS)

Simulation-to-reality UAV Fault Diagnosis in windy environments

Authors: Wei Zhang, Junjie Tong, Fang Liao, Yunfeng Zhang

Abstract: Monitoring propeller failures is vital to maintain the safe and reliable operation of quadrotor UAVs. The simulation-to-reality UAV fault diagnosis technique offer a secure and economical approach to identify faults in propellers. However, classifiers trained with simulated data perform poorly in real flights due to the wind disturbance in outdoor scenarios. In this work, we propose an uncertainty… ▽ More Monitoring propeller failures is vital to maintain the safe and reliable operation of quadrotor UAVs. The simulation-to-reality UAV fault diagnosis technique offer a secure and economical approach to identify faults in propellers. However, classifiers trained with simulated data perform poorly in real flights due to the wind disturbance in outdoor scenarios. In this work, we propose an uncertainty-based fault classifier (UFC) to address the challenge of sim-to-real UAV fault diagnosis in windy scenarios. It uses the ensemble of difference-based deep convolutional neural networks (EDDCNN) to reduce model variance and bias. Moreover, it employs an uncertainty-based decision framework to filter out uncertain predictions. Experimental results demonstrate that the UFC can achieve 100% fault-diagnosis accuracy with a data usage rate of 33.6% in the windy outdoor scenario. △ Less

Submitted 21 September, 2023; originally announced September 2023.

Comments: 8 pages, 8 figures

Conformal Temporal Logic Planning using Large Language Models

Authors: Jun Wang, Jiaming Tong, Kaiyuan Tan, Yevgeniy Vorobeychik, Yiannis Kantaros

Abstract: This paper addresses a new motion planning problem for mobile robots tasked with accomplishing multiple high-level sub-tasks, expressed using natural language (NL). These sub-tasks should be accomplished in a temporal and logical order. To formally define the overarching mission, we leverage Linear Temporal Logic (LTL) defined over atomic predicates modeling these NL-based sub-tasks. This is in co… ▽ More This paper addresses a new motion planning problem for mobile robots tasked with accomplishing multiple high-level sub-tasks, expressed using natural language (NL). These sub-tasks should be accomplished in a temporal and logical order. To formally define the overarching mission, we leverage Linear Temporal Logic (LTL) defined over atomic predicates modeling these NL-based sub-tasks. This is in contrast to related planning approaches that define LTL tasks over atomic predicates capturing desired low-level system configurations. Our goal is to design robot plans that satisfy LTL tasks defined over NL-based atomic propositions. A novel technical challenge arising in this setup lies in reasoning about correctness of a robot plan with respect to such LTL-encoded tasks. To address this problem, we propose HERACLEs, a hierarchical conformal natural language planner, that relies on (i) automata theory to determine what NL-specified sub-tasks should be accomplished next to make mission progress; (ii) Large Language Models to design robot plans satisfying these sub-tasks; and (iii) conformal prediction to reason probabilistically about correctness of the designed plans and to determine if external assistance is required. We provide theoretical probabilistic mission satisfaction guarantees as well as extensive comparative experiments on mobile manipulation tasks. △ Less

Submitted 22 February, 2024; v1 submitted 18 September, 2023; originally announced September 2023.

Incorprating Prompt tuning for Commit classification with prior Knowledge

Authors: Jiajun Tong, Xiaobin Rui

Abstract: Commit Classification(CC) is an important task in software maintenance since it helps software developers classify code changes into different types according to their nature and purpose. This allows them to better understand how their development efforts are progressing, identify areas where they need improvement. However, existing methods are all discriminative models, usually with complex archi… ▽ More Commit Classification(CC) is an important task in software maintenance since it helps software developers classify code changes into different types according to their nature and purpose. This allows them to better understand how their development efforts are progressing, identify areas where they need improvement. However, existing methods are all discriminative models, usually with complex architectures that require additional output layers to produce class label probabilities. Moreover, they require a large amount of labeled data for fine-tuning, and it is difficult to learn effective classification boundaries in the case of limited labeled data. To solve above problems, we propose a generative framework that Incorporating prompt-tuning for commit classification with prior knowledge (IPCK) https://github.com/AppleMax1992/IPCK, which simplifies the model structure and learns features across different tasks. It can still reach the SOTA performance with only limited samples. Firstly, we proposed a generative framework based on T5. This encoder-decoder construction method unifies different CC task into a text2text problem, which simplifies the structure of the model by not requiring an extra output layer. Second, instead of fine-tuning, we design an prompt-tuning solution which can be adopted in few-shot scenarios with only limit samples. Furthermore, we incorporate prior knowledge via an external knowledge graph to map the probabilities of words into the final labels in the speech machine step to improve performance in few-shot scenarios. Extensive experiments on two open available datasets show that our framework can solve the CC problem simply but effectively in few-shot and zeroshot scenarios, while improving the adaptability of the model without requiring a large amount of training samples for fine-tuning. △ Less

Submitted 26 October, 2023; v1 submitted 21 August, 2023; originally announced August 2023.

Boosting Commit Classification with Contrastive Learning

Authors: Jiajun Tong, Zhixiao Wang, Xiaobin Rui

Abstract: Commit Classification (CC) is an important task in software maintenance, which helps software developers classify code changes into different types according to their nature and purpose. It allows developers to understand better how their development efforts are progressing, identify areas where they need improvement, and make informed decisions about when and how to release new software versions.… ▽ More Commit Classification (CC) is an important task in software maintenance, which helps software developers classify code changes into different types according to their nature and purpose. It allows developers to understand better how their development efforts are progressing, identify areas where they need improvement, and make informed decisions about when and how to release new software versions. However, existing models need lots of manually labeled data for fine-tuning processes, and ignore sentence-level semantic information, which is often essential for discovering the difference between diverse commits. Therefore, it is still challenging to solve CC in fewshot scenario. To solve the above problems, we propose a contrastive learning-based commit classification framework. Firstly, we generate $K$ sentences and pseudo-labels according to the labels of the dataset, which aims to enhance the dataset. Secondly, we randomly group the augmented data $N$ times to compare their similarity with the positive $T_p^{|C|}$ and negative $T_n^{|C|}$ samples. We utilize individual pretrained sentence transformers (ST)s to efficiently obtain the sentence-level embeddings from different features respectively. Finally, we adopt the cosine similarity function to limit the distribution of vectors, similar vectors are more adjacent. The light fine-tuned model is then applied to the label prediction of incoming commits. Extensive experiments on two open available datasets demonstrate that our framework can solve the CC problem simply but effectively in fewshot scenarios, while achieving state-of-the-art(SOTA) performance and improving the adaptability of the model without requiring a large number of training samples for fine-tuning. The code, data, and trained models are available at https://github.com/AppleMax1992/CommitFit. △ Less

Submitted 16 August, 2023; originally announced August 2023.

NEOLAF, an LLM-powered neural-symbolic cognitive architecture

Authors: Richard Jiarui Tong, Cassie Chen Cao, Timothy Xueqian Lee, Guodong Zhao, Ray Wan, Feiyue Wang, Xiangen Hu, Robin Schmucker, Jinsheng Pan, Julian Quevedo, Yu Lu

Abstract: This paper presents the Never Ending Open Learning Adaptive Framework (NEOLAF), an integrated neural-symbolic cognitive architecture that models and constructs intelligent agents. The NEOLAF framework is a superior approach to constructing intelligent agents than both the pure connectionist and pure symbolic approaches due to its explainability, incremental learning, efficiency, collaborative and… ▽ More This paper presents the Never Ending Open Learning Adaptive Framework (NEOLAF), an integrated neural-symbolic cognitive architecture that models and constructs intelligent agents. The NEOLAF framework is a superior approach to constructing intelligent agents than both the pure connectionist and pure symbolic approaches due to its explainability, incremental learning, efficiency, collaborative and distributed learning, human-in-the-loop enablement, and self-improvement. The paper further presents a compelling experiment where a NEOLAF agent, built as a problem-solving agent, is fed with complex math problems from the open-source MATH dataset. The results demonstrate NEOLAF's superior learning capability and its potential to revolutionize the field of cognitive architectures and self-improving adaptive instructional systems. △ Less

Submitted 7 August, 2023; originally announced August 2023.

Subgraph Stationary Hardware-Software Inference Co-Design

Authors: Payman Behnam, Jianming Tong, Alind Khare, Yangyu Chen, Yue Pan, Pranav Gadikar, Abhimanyu Rajeshkumar Bambhaniya, Tushar Krishna, Alexey Tumanov

Abstract: A growing number of applications depend on Machine Learning (ML) functionality and benefits from both higher quality ML predictions and better timeliness (latency) at the same time. A growing body of research in computer architecture, ML, and systems software literature focuses on reaching better latency-accuracy tradeoffs for ML models. Efforts include compression, quantization, pruning, early-ex… ▽ More A growing number of applications depend on Machine Learning (ML) functionality and benefits from both higher quality ML predictions and better timeliness (latency) at the same time. A growing body of research in computer architecture, ML, and systems software literature focuses on reaching better latency-accuracy tradeoffs for ML models. Efforts include compression, quantization, pruning, early-exit models, mixed DNN precision, as well as ML inference accelerator designs that minimize latency and energy, while preserving delivered accuracy. All of them, however, yield improvements for a single static point in the latency-accuracy tradeoff space. We make a case for applications that operate in dynamically changing deployment scenarios, where no single static point is optimal. We draw on a recently proposed weight-shared SuperNet mechanism to enable serving a stream of queries that uses (activates) different SubNets within this weight-shared construct. This creates an opportunity to exploit the inherent temporal locality with our proposed SubGraph Stationary (SGS) optimization. We take a hardware-software co-design approach with a real implementation of SGS in SushiAccel and the implementation of a software scheduler SushiSched controlling which SubNets to serve and what to cache in real-time. Combined, they are vertically integrated into SUSHI-an inference serving stack. For the stream of queries, SUSHI yields up to 25% improvement in latency, 0.98% increase in served accuracy. SUSHI can achieve up to 78.7% off-chip energy savings. △ Less

Submitted 21 June, 2023; originally announced June 2023.

Comments: 16 pages; MLSYS 2023

Improving speech translation by fusing speech and text

Authors: Wenbiao Yin, Zhicheng Liu, Chengqi Zhao, Tao Wang, Jian Tong, Rong Ye

Abstract: In speech translation, leveraging multimodal data to improve model performance and address limitations of individual modalities has shown significant effectiveness. In this paper, we harness the complementary strengths of speech and text, which are disparate modalities. We observe three levels of modality gap between them, denoted by Modal input representation, Modal semantic, and Modal hidden sta… ▽ More In speech translation, leveraging multimodal data to improve model performance and address limitations of individual modalities has shown significant effectiveness. In this paper, we harness the complementary strengths of speech and text, which are disparate modalities. We observe three levels of modality gap between them, denoted by Modal input representation, Modal semantic, and Modal hidden states. To tackle these gaps, we propose \textbf{F}use-\textbf{S}peech-\textbf{T}ext (\textbf{FST}), a cross-modal model which supports three distinct input modalities for translation: speech, text, and fused speech-text. We leverage multiple techniques for cross-modal alignment and conduct a comprehensive analysis to assess its impact on speech translation, machine translation, and fused speech-text translation. We evaluate FST on MuST-C, GigaST, and newstest benchmark. Experiments show that the proposed FST achieves an average 34.0 BLEU on MuST-C En$\rightarrow$De/Es/Fr (vs SOTA +1.1 BLEU). Further experiments demonstrate that FST does not degrade on MT task, as observed in prior works. Instead, it yields an average improvement of 3.2 BLEU over the pre-trained MT model. △ Less

Submitted 23 May, 2023; originally announced May 2023.

Seeing Through the Glass: Neural 3D Reconstruction of Object Inside a Transparent Container

Authors: Jinguang Tong, Sundaram Muthu, Fahira Afzal Maken, Chuong Nguyen, Hongdong Li

Abstract: In this paper, we define a new problem of recovering the 3D geometry of an object confined in a transparent enclosure. We also propose a novel method for solving this challenging problem. Transparent enclosures pose challenges of multiple light reflections and refractions at the interface between different propagation media e.g. air or glass. These multiple reflections and refractions cause seriou… ▽ More In this paper, we define a new problem of recovering the 3D geometry of an object confined in a transparent enclosure. We also propose a novel method for solving this challenging problem. Transparent enclosures pose challenges of multiple light reflections and refractions at the interface between different propagation media e.g. air or glass. These multiple reflections and refractions cause serious image distortions which invalidate the single viewpoint assumption. Hence the 3D geometry of such objects cannot be reliably reconstructed using existing methods, such as traditional structure from motion or modern neural reconstruction methods. We solve this problem by explicitly modeling the scene as two distinct sub-spaces, inside and outside the transparent enclosure. We use an existing neural reconstruction method (NeuS) that implicitly represents the geometry and appearance of the inner subspace. In order to account for complex light interactions, we develop a hybrid rendering strategy that combines volume rendering with ray tracing. We then recover the underlying geometry and appearance of the model by minimizing the difference between the real and hybrid rendered images. We evaluate our method on both synthetic and real data. Experiment results show that our method outperforms the state-of-the-art (SOTA) methods. Codes and data will be available at https://github.com/hirotong/ReNeuS △ Less

Submitted 24 March, 2023; originally announced March 2023.

Comments: Accepted to CVPR2023

DDCNN: A Promising Tool for Simulation-To-Reality UAV Fault Diagnosis

Authors: Wei Zhang, Shanze Wang, Junjie Tong, Fang Liao, Yunfeng Zhang, Xiaoyu Shen

Abstract: Identifying the fault in propellers is important to keep quadrotors operating safely and efficiently. The simulation-to-reality (sim-to-real) UAV fault diagnosis methods provide a cost-effective and safe approach to detecting propeller faults. However, due to the gap between simulation and reality, classifiers trained with simulated data usually underperform in real flights. In this work, a novel… ▽ More Identifying the fault in propellers is important to keep quadrotors operating safely and efficiently. The simulation-to-reality (sim-to-real) UAV fault diagnosis methods provide a cost-effective and safe approach to detecting propeller faults. However, due to the gap between simulation and reality, classifiers trained with simulated data usually underperform in real flights. In this work, a novel difference-based deep convolutional neural network (DDCNN) model is presented to address the above issue. It uses the difference features extracted by deep convolutional neural networks to reduce the sim-to-real gap. Moreover, a new domain adaptation (DA) method is presented to further bring the distribution of the real-flight data closer to that of the simulation data. The experimental results demonstrate that the DDCNN+DA model can increase the accuracy from 52.9% to 99.1% in real-world UAV fault detection. △ Less

Submitted 23 June, 2024; v1 submitted 16 February, 2023; originally announced February 2023.

Comments: 20xx IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, including reprinting/republishing this material for advertising or promotional purposes, collecting new collected works for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works

Simulation-to-reality UAV Fault Diagnosis with Deep Learning

Authors: Wei Zhang, Junjie Tong, Fang Liao, Yunfeng Zhang

Abstract: Accurate diagnosis of propeller faults is crucial for ensuring the safe and efficient operation of quadrotors. Training a fault classifier using simulated data and deploying it on a real quadrotor is a cost-effective and safe approach. However, the simulation-to-reality gap often leads to poor performance of the classifier when applied in real flight. In this work, we propose a deep learning model… ▽ More Accurate diagnosis of propeller faults is crucial for ensuring the safe and efficient operation of quadrotors. Training a fault classifier using simulated data and deploying it on a real quadrotor is a cost-effective and safe approach. However, the simulation-to-reality gap often leads to poor performance of the classifier when applied in real flight. In this work, we propose a deep learning model that addresses this issue by utilizing newly identified features (NIF) as input and utilizing domain adaptation techniques to reduce the simulation-to-reality gap. In addition, we introduce an adjusted simulation model that generates training data that more accurately reflects the behavior of real quadrotors. The experimental results demonstrate that our proposed approach achieves an accuracy of 96\% in detecting propeller faults. To the best of our knowledge, this is the first reliable and efficient method for simulation-to-reality fault diagnosis of quadrotor propellers. △ Less

Submitted 8 February, 2023; originally announced February 2023.

Comments: 7 pages, 9 figures

Machine Learning for UAV Propeller Fault Detection based on a Hybrid Data Generation Model

Authors: J. J. Tong, W. Zhang, F. Liao, C. F. Li, Y. F. Zhang

Abstract: This paper describes the development of an on-board data-driven system that can monitor and localize the fault in a quadrotor unmanned aerial vehicle (UAV) and at the same time, evaluate the degree of damage of the fault under real scenarios. To achieve offline training data generation, a hybrid approach is proposed for the development of a virtual data-generative model using a combination of data… ▽ More This paper describes the development of an on-board data-driven system that can monitor and localize the fault in a quadrotor unmanned aerial vehicle (UAV) and at the same time, evaluate the degree of damage of the fault under real scenarios. To achieve offline training data generation, a hybrid approach is proposed for the development of a virtual data-generative model using a combination of data-driven models as well as well-established dynamic models that describe the kinematics of the UAV. To effectively represent the drop in performance of a faulty propeller, a variation of the deep neural network, a LSTM network is proposed. With the RPM of the propeller as input and based on the fault condition of the propeller, the proposed propeller model estimates the resultant torque and thrust. Then, flight datasets of the UAV under various fault scenarios are generated via simulation using the developed data-generative model. Lastly, a fault classifier using a CNN model is proposed to identify as well as evaluate the degree of damage to the damaged propeller. The scope of this paper focuses on the identification of faulty propellers and classification of the fault level for quadrotor UAVs using RPM as well as flight data. Doing so allows for early minor fault detection to prevent serious faults from occurring if the fault is left unrepaired. To further validate the workability of this approach outside of simulation, a real-flight test is conducted indoors. The real flight data is collected and a simulation to real sim-real test is conducted. Due to the imperfections in the build of our experimental UAV, a slight calibration approach to our simulation model is further proposed and the experimental results obtained show that our trained model can identify the location of propeller fault as well as the degree/type of damage. Currently, the diagnosis accuracy on the testing set is over 80%. △ Less

Submitted 3 February, 2023; originally announced February 2023.

Expanding Knowledge Graphs with Humans in the Loop

Authors: Emaad Manzoor, Jordan Tong, Sriniketh Vijayaraghavan, Rui Li

Abstract: Curated knowledge graphs encode domain expertise and improve the performance of recommendation, segmentation, ad targeting, and other machine learning systems in several domains. As new concepts emerge in a domain, knowledge graphs must be expanded to preserve machine learning performance. Manually expanding knowledge graphs, however, is infeasible at scale. In this work, we propose a method for k… ▽ More Curated knowledge graphs encode domain expertise and improve the performance of recommendation, segmentation, ad targeting, and other machine learning systems in several domains. As new concepts emerge in a domain, knowledge graphs must be expanded to preserve machine learning performance. Manually expanding knowledge graphs, however, is infeasible at scale. In this work, we propose a method for knowledge graph expansion with humans-in-the-loop. Concretely, given a knowledge graph, our method predicts the "parents" of new concepts to be added to this graph for further verification by human experts. We show that our method is both accurate and provably "human-friendly". Specifically, we prove that our method predicts parents that are "near" concepts' true parents in the knowledge graph, even when the predictions are incorrect. We then show, with a controlled experiment, that satisfying this property increases both the speed and the accuracy of the human-algorithm collaboration. We further evaluate our method on a knowledge graph from Pinterest and show that it outperforms competing methods on both accuracy and human-friendliness. Upon deployment in production at Pinterest, our method reduced the time needed for knowledge graph expansion by ~400% (compared to manual expansion), and contributed to a subsequent increase in ad revenue of 20%. △ Less

Submitted 26 March, 2023; v1 submitted 9 December, 2022; originally announced December 2022.

Hyperbolic Cosine Transformer for LiDAR 3D Object Detection

Authors: Jigang Tong, Fanhang Yang, Sen Yang, Enzeng Dong, Shengzhi Du, Xing Wang, Xianlin Yi

Abstract: Recently, Transformer has achieved great success in computer vision. However, it is constrained because the spatial and temporal complexity grows quadratically with the number of large points in 3D object detection applications. Previous point-wise methods are suffering from time consumption and limited receptive fields to capture information among points. In this paper, we propose a two-stage hyp… ▽ More Recently, Transformer has achieved great success in computer vision. However, it is constrained because the spatial and temporal complexity grows quadratically with the number of large points in 3D object detection applications. Previous point-wise methods are suffering from time consumption and limited receptive fields to capture information among points. In this paper, we propose a two-stage hyperbolic cosine transformer (ChTR3D) for 3D object detection from LiDAR point clouds. The proposed ChTR3D refines proposals by applying cosh-attention in linear computation complexity to encode rich contextual relationships among points. The cosh-attention module reduces the space and time complexity of the attention operation. The traditional softmax operation is replaced by non-negative ReLU activation and hyperbolic-cosine-based operator with re-weighting mechanism. Extensive experiments on the widely used KITTI dataset demonstrate that, compared with vanilla attention, the cosh-attention significantly improves the inference speed with competitive performance. Experiment results show that, among two-stage state-of-the-art methods using point-level features, the proposed ChTR3D is the fastest one. △ Less

Submitted 10 November, 2022; originally announced November 2022.

Comments: 8 pages, 5 figures and 3 tables. This paper possibly publicated on the IEEE Robotics and Automation Letters

ACM Class: I.4.8

Probabilistic Decomposition Transformer for Time Series Forecasting

Authors: Junlong Tong, Liping Xie, Wankou Yang, Kanjian Zhang

Abstract: Time series forecasting is crucial for many fields, such as disaster warning, weather prediction, and energy consumption. The Transformer-based models are considered to have revolutionized the field of sequence modeling. However, the complex temporal patterns of the time series hinder the model from mining reliable temporal dependencies. Furthermore, the autoregressive form of the Transformer intr… ▽ More Time series forecasting is crucial for many fields, such as disaster warning, weather prediction, and energy consumption. The Transformer-based models are considered to have revolutionized the field of sequence modeling. However, the complex temporal patterns of the time series hinder the model from mining reliable temporal dependencies. Furthermore, the autoregressive form of the Transformer introduces cumulative errors in the inference step. In this paper, we propose the probabilistic decomposition Transformer model that combines the Transformer with a conditional generative model, which provides hierarchical and interpretable probabilistic forecasts for intricate time series. The Transformer is employed to learn temporal patterns and implement primary probabilistic forecasts, while the conditional generative model is used to achieve non-autoregressive hierarchical probabilistic forecasts by introducing latent space feature representations. In addition, the conditional generative model reconstructs typical features of the series, such as seasonality and trend terms, from probability distributions in the latent space to enable complex pattern separation and provide interpretable forecasts. Extensive experiments on several datasets demonstrate the effectiveness and robustness of the proposed model, indicating that it compares favorably with the state of the art. △ Less

Submitted 31 October, 2022; originally announced October 2022.

A topic-aware graph neural network model for knowledge base updating

Authors: Jiajun Tong, Zhixiao Wang, Xiaobin Rui

Abstract: The open domain knowledge base is very important. It is usually extracted from encyclopedia websites and is widely used in knowledge retrieval systems, question answering systems, or recommendation systems. In practice, the key challenge is to maintain an up-to-date knowledge base. Different from Unwieldy fetching all of the data from the encyclopedia dumps, to enlarge the freshness of the knowled… ▽ More The open domain knowledge base is very important. It is usually extracted from encyclopedia websites and is widely used in knowledge retrieval systems, question answering systems, or recommendation systems. In practice, the key challenge is to maintain an up-to-date knowledge base. Different from Unwieldy fetching all of the data from the encyclopedia dumps, to enlarge the freshness of the knowledge base as big as possible while avoiding invalid fetching, the current knowledge base updating methods usually determine whether entities need to be updated by building a prediction model. However, these methods can only be defined in some specific fields and the result turns out to be obvious bias, due to the problem of data source and data structure. The users' query intentions are often diverse as to the open domain knowledge, so we construct a topic-aware graph network for knowledge updating based on the user query log. Our methods can be summarized as follow: 1. Extract entities through the user's log and select them as seeds 2. Scrape the attributes of seed entities in the encyclopedia website, and self-supervised construct the entity attribute graph for each entity. 3. Use the entity attribute graph to train the GNN entity update model to determine whether the entity needs to be synchronized. 4.Use the encyclopedia knowledge to match and update the filtered entity with the entity in the knowledge base according to the minimum edit times algorithm. △ Less

Submitted 1 September, 2022; v1 submitted 30 August, 2022; originally announced August 2022.

A multi-model-based deep learning framework for short text multiclass classification with the imbalanced and extremely small data set

Authors: Jiajun Tong, Zhixiao Wang, Xiaobin Rui

Abstract: Text classification plays an important role in many practical applications. In the real world, there are extremely small datasets. Most existing methods adopt pre-trained neural network models to handle this kind of dataset. However, these methods are either difficult to deploy on mobile devices because of their large output size or cannot fully extract the deep semantic information between phrase… ▽ More Text classification plays an important role in many practical applications. In the real world, there are extremely small datasets. Most existing methods adopt pre-trained neural network models to handle this kind of dataset. However, these methods are either difficult to deploy on mobile devices because of their large output size or cannot fully extract the deep semantic information between phrases and clauses. This paper proposes a multimodel-based deep learning framework for short-text multiclass classification with an imbalanced and extremely small data set. Our framework mainly includes five layers: The encoder layer uses DISTILBERT to obtain context-sensitive dynamic word vectors that are difficult to represent in traditional feature engineering methods. Since the transformer part of this layer is distilled, our framework is compressed. Then, we use the next two layers to extract deep semantic information. The output of the encoder layer is sent to a bidirectional LSTM network, and the feature matrix is extracted hierarchically through the LSTM at the word and sentence level to obtain the fine-grained semantic representation. After that, the max-pooling layer converts the feature matrix into a lower-dimensional matrix, preserving only the obvious features. Finally, the feature matrix is taken as the input of a fully connected softmax layer, which contains a function that can convert the predicted linear vector into the output value as the probability of the text in each classification. Extensive experiments on two public benchmarks demonstrate the effectiveness of our proposed approach on an extremely small data set. It retains the state-of-the-art baseline performance in terms of precision, recall, accuracy, and F1 score, and through the model size, training time, and convergence epoch, we can conclude that our method can be deployed faster and lighter on mobile devices. △ Less

Submitted 23 June, 2022; originally announced June 2022.

On the Message Passing Efficiency of Polar and Low-Density Parity-Check Decoders

Authors: Dawei Yin, Yuan Li, Xianbin Wang, Jiajie Tong, Huazi Zhang, Jun Wang, Guanghui Wang, Jun Chen, Guiying Yan, Zhiming Ma, Wen Tong

Abstract: This study focuses on the efficiency of message-passing-based decoding algorithms for polar and low-density parity-check (LDPC) codes. Both successive cancellation (SC) and belief propagation (BP) decoding algorithms are studied {in} the message-passing framework. Counter-intuitively, SC decoding demonstrates the highest decoding efficiency, although it was considered a weak decoder {in terms of}… ▽ More This study focuses on the efficiency of message-passing-based decoding algorithms for polar and low-density parity-check (LDPC) codes. Both successive cancellation (SC) and belief propagation (BP) decoding algorithms are studied {in} the message-passing framework. Counter-intuitively, SC decoding demonstrates the highest decoding efficiency, although it was considered a weak decoder {in terms of} error-correction performance. We analyze the complexity-performance tradeoff to dynamically track the decoding efficiency, where the complexity is measured by the number of messages passed (NMP), and the performance is measured by the statistical distance to the maximum a posteriori (MAP) estimate. This study offers a new insight into the contribution of each message passed in decoding, and compares various decoding algorithms on a message-by-message level. The analysis corroborates recent results on terabits-per-second polar SC decoders, and might shed light on better scheduling strategies. △ Less

Submitted 20 April, 2023; v1 submitted 14 June, 2022; originally announced June 2022.

A Performance-Consistent and Computation-Efficient CNN System for High-Quality Automated Brain Tumor Segmentation

Authors: Juncheng Tong, Chunyan Wang

Abstract: The research on developing CNN-based fully-automated Brain-Tumor-Segmentation systems has been progressed rapidly. For the systems to be applicable in practice, a good The research on developing CNN-based fully-automated Brain-Tumor-Segmentation systems has been progressed rapidly. For the systems to be applicable in practice, a good processing quality and reliability are the must. Moreover, for w… ▽ More The research on developing CNN-based fully-automated Brain-Tumor-Segmentation systems has been progressed rapidly. For the systems to be applicable in practice, a good The research on developing CNN-based fully-automated Brain-Tumor-Segmentation systems has been progressed rapidly. For the systems to be applicable in practice, a good processing quality and reliability are the must. Moreover, for wide applications of such systems, a minimization of computation complexity is desirable, which can also result in a minimization of randomness in computation and, consequently, a better performance consistency. To this end, the CNN in the proposed system has a unique structure with 2 distinguished characters. Firstly, the three paths of its feature extraction block are designed to extract, from the multi-modality input, comprehensive feature information of mono-modality, paired-modality and cross-modality data, respectively. Also, it has a particular three-branch classification block to identify the pixels of 4 classes. Each branch is trained separately so that the parameters are updated specifically with the corresponding ground truth data of a target tumor areas. The convolution layers of the system are custom-designed with specific purposes, resulting in a very simple config of 61,843 parameters in total. The proposed system is tested extensively with BraTS2018 and BraTS2019 datasets. The mean Dice scores, obtained from the ten experiments on BraTS2018 validation samples, are 0.787+0.003, 0.886+0.002, 0.801+0.007, for enhancing tumor, whole tumor and tumor core, respectively, and 0.751+0.007, 0.885+0.002, 0.776+0.004 on BraTS2019. The test results demonstrate that the proposed system is able to perform high-quality segmentation in a consistent manner. Furthermore, its extremely low computation complexity will facilitate its implementation/application in various environments. △ Less

Submitted 2 May, 2022; originally announced May 2022.

Comments: 10 pages, 4 figures, currently under review of IEEE transactions on medical imaging

CMMD: Cross-Metric Multi-Dimensional Root Cause Analysis

Authors: Shifu Yan, Caihua Shan, Wenyi Yang, Bixiong Xu, Dongsheng Li, Lili Qiu, Jie Tong, Qi Zhang

Abstract: In large-scale online services, crucial metrics, a.k.a., key performance indicators (KPIs), are monitored periodically to check their running statuses. Generally, KPIs are aggregated along multiple dimensions and derived by complex calculations among fundamental metrics from the raw data. Once abnormal KPI values are observed, root cause analysis (RCA) can be applied to identify the reasons for an… ▽ More In large-scale online services, crucial metrics, a.k.a., key performance indicators (KPIs), are monitored periodically to check their running statuses. Generally, KPIs are aggregated along multiple dimensions and derived by complex calculations among fundamental metrics from the raw data. Once abnormal KPI values are observed, root cause analysis (RCA) can be applied to identify the reasons for anomalies, so that we can troubleshoot quickly. Recently, several automatic RCA techniques were proposed to localize the related dimensions (or a combination of dimensions) to explain the anomalies. However, their analyses are limited to the data on the abnormal metric and ignore the data of other metrics which may be also related to the anomalies, leading to imprecise or even incorrect root causes. To this end, we propose a cross-metric multi-dimensional root cause analysis method, named CMMD, which consists of two key components: 1) relationship modeling, which utilizes graph neural network (GNN) to model the unknown complex calculation among metrics and aggregation function among dimensions from historical data; 2) root cause localization, which adopts the genetic algorithm to efficiently and effectively dive into the raw data and localize the abnormal dimension(s) once the KPI anomalies are detected. Experiments on synthetic datasets, public datasets and online production environment demonstrate the superiority of our proposed CMMD method compared with baselines. Currently, CMMD is running as an online service in Microsoft Azure. △ Less

Submitted 30 March, 2022; originally announced March 2022.

Voxelized 3D Feature Aggregation for Multiview Detection

Authors: Jiahao Ma, Jinguang Tong, Shan Wang, Wei Zhao, Zicheng Duan, Chuong Nguyen

Abstract: Multi-view detection incorporates multiple camera views to alleviate occlusion in crowded scenes, where the state-of-the-art approaches adopt homography transformations to project multi-view features to the ground plane. However, we find that these 2D transformations do not take into account the object's height, and with this neglection features along the vertical direction of same object are like… ▽ More Multi-view detection incorporates multiple camera views to alleviate occlusion in crowded scenes, where the state-of-the-art approaches adopt homography transformations to project multi-view features to the ground plane. However, we find that these 2D transformations do not take into account the object's height, and with this neglection features along the vertical direction of same object are likely not projected onto the same ground plane point, leading to impure ground-plane features. To solve this problem, we propose VFA, voxelized 3D feature aggregation, for feature transformation and aggregation in multi-view detection. Specifically, we voxelize the 3D space, project the voxels onto each camera view, and associate 2D features with these projected voxels. This allows us to identify and then aggregate 2D features along the same vertical line, alleviating projection distortions to a large extent. Additionally, because different kinds of objects (human vs. cattle) have different shapes on the ground plane, we introduce the oriented Gaussian encoding to match such shapes, leading to increased accuracy and efficiency. We perform experiments on multiview 2D detection and multiview 3D detection problems. Results on four datasets (including a newly introduced MultiviewC dataset) show that our system is very competitive compared with the state-of-the-art approaches. %Our code and data will be open-sourced.Code and MultiviewC are released at https://github.com/Robert-Mar/VFA. △ Less

Submitted 4 January, 2023; v1 submitted 6 December, 2021; originally announced December 2021.

Federated Learning Algorithms for Generalized Mixed-effects Model (GLMM) on Horizontally Partitioned Data from Distributed Sources

Authors: Wentao Li, Jiayi Tong, Md. Monowar Anjum, Noman Mohammed, Yong Chen, Xiaoqian Jiang

Abstract: Objectives: This paper develops two algorithms to achieve federated generalized linear mixed effect models (GLMM), and compares the developed model's outcomes with each other, as well as that from the standard R package (`lme4'). Methods: The log-likelihood function of GLMM is approximated by two numerical methods (Laplace approximation and Gaussian Hermite approximation), which supports federat… ▽ More Objectives: This paper develops two algorithms to achieve federated generalized linear mixed effect models (GLMM), and compares the developed model's outcomes with each other, as well as that from the standard R package (`lme4'). Methods: The log-likelihood function of GLMM is approximated by two numerical methods (Laplace approximation and Gaussian Hermite approximation), which supports federated decomposition of GLMM to bring computation to data. Results: Our developed method can handle GLMM to accommodate hierarchical data with multiple non-independent levels of observations in a federated setting. The experiment results demonstrate comparable (Laplace) and superior (Gaussian-Hermite) performances with simulated and real-world data. Conclusion: We developed and compared federated GLMMs with different approximations, which can support researchers in analyzing biomedical data to accommodate mixed effects and address non-independence due to hierarchical structures (i.e., institutes, region, country, etc.). △ Less

Submitted 7 June, 2022; v1 submitted 28 September, 2021; originally announced September 2021.

Comments: 19 pages, 5 figures, submitted to Journal of Biomedical Informatics

Theoretical Analysis and Evaluation of NoCs with Weighted Round-Robin Arbitration

Authors: Sumit K. Mandal, Jie Tong, Raid Ayoub, Michael Kishinevsky, Ahmed Abousamra, Umit Y. Ogras

Abstract: Fast and accurate performance analysis techniques are essential in early design space exploration and pre-silicon evaluations, including software eco-system development. In particular, on-chip communication continues to play an increasingly important role as the many-core processors scale up. This paper presents the first performance analysis technique that targets networks-on-chip (NoCs) that emp… ▽ More Fast and accurate performance analysis techniques are essential in early design space exploration and pre-silicon evaluations, including software eco-system development. In particular, on-chip communication continues to play an increasingly important role as the many-core processors scale up. This paper presents the first performance analysis technique that targets networks-on-chip (NoCs) that employ weighted round-robin (WRR) arbitration. Besides fairness, WRR arbitration provides flexibility in allocating bandwidth proportionally to the importance of the traffic classes, unlike basic round-robin and priority-based arbitration. The proposed approach first estimates the effective service time of the packets in the queue due to WRR arbitration. Then, it uses the effective service time to compute the average waiting time of the packets. Next, we incorporate a decomposition technique to extend the analytical model to handle NoC of any size. The proposed approach achieves less than 5% error while executing real applications and 10% error under challenging synthetic traffic with different burstiness levels. △ Less

Submitted 11 August, 2023; v1 submitted 21 August, 2021; originally announced August 2021.

Comments: This paper is accepted in International Conference on Computer Aided Design (ICCAD), 2021

A unified polar decoder platform for low-power and low-cost devices

Authors: Jiajie Tong, Qifan Zhang, Huazi Zhang, Rong Li, Jun Wang, Wen Tong

Abstract: In this paper, we design a polar decoding platform for diverse application scenarios that require low-cost and low-power communications. Specifically, prevalent polar decoders such as successive cancellation (SC), SC-list (SCL) and Fano decoders are all supported under the same architecture. Unlike high-throughput or low-latency decoders that promote parallelism, this architecture promotes seriali… ▽ More In this paper, we design a polar decoding platform for diverse application scenarios that require low-cost and low-power communications. Specifically, prevalent polar decoders such as successive cancellation (SC), SC-list (SCL) and Fano decoders are all supported under the same architecture. Unlike high-throughput or low-latency decoders that promote parallelism, this architecture promotes serialization by repeatedly calling a ``sub-process'' that is executed by a core module. The resulting serial SCL-8 decoder is only 3 times as big as an SC decoder. Cost and power are minimized through resource sharing and adaptive decoding techniques, etc. We carried out performance simulation and hardware implementation to evaluate the actual chip area and energy consumption. △ Less

Submitted 18 July, 2021; originally announced July 2021.

Comments: 6 pages, 8 figures. Part of this paper was presented in an invited talk at the 2021 International Symposium on Information Theory (ISIT)

Fast polar codes for terabits-per-second throughput communications

Authors: Jiajie Tong, Xianbin Wang, Qifan Zhang, Huazi Zhang, Rong Li, Jun Wang, Wen Tong

Abstract: Targeting high-throughput and low-power communications, we implement two successive cancellation (SC) decoders for polar codes. With $16nm$ ASIC technology, the area efficiency and energy efficiency are $4Tbps/mm^2$ and $0.63pJ/bit$, respectively, for the unrolled decoder, and $561Gbps/mm^2$ and $1.21pJ/bit$, respectively, for the recursive decoder. To achieve such a high throughput, a novel code… ▽ More Targeting high-throughput and low-power communications, we implement two successive cancellation (SC) decoders for polar codes. With $16nm$ ASIC technology, the area efficiency and energy efficiency are $4Tbps/mm^2$ and $0.63pJ/bit$, respectively, for the unrolled decoder, and $561Gbps/mm^2$ and $1.21pJ/bit$, respectively, for the recursive decoder. To achieve such a high throughput, a novel code construction, coined as fast polar codes, is proposed and jointly optimized with a highly-parallel SC decoding architecture. First, we reuse existing modules to fast decode more outer code blocks, and then modify code construction to facilitate faster decoding for all outer code blocks up to a degree of parallelism of $16$. Furthermore, parallel comparison circuits and bit quantization schemes are customized for hardware implementation. Collectively, they contribute to an $2.66\times$ area efficiency improvement and $33\%$ energy saving over the state of the art. △ Less

Submitted 18 July, 2021; originally announced July 2021.

Comments: 8 pages, 5 figures. Part of this paper was presented in an invited talk at the 2021 International Symposium on Information Theory (ISIT)

The Volctrans Neural Speech Translation System for IWSLT 2021

Authors: Chengqi Zhao, Zhicheng Liu, Jian Tong, Tao Wang, Mingxuan Wang, Rong Ye, Qianqian Dong, Jun Cao, Lei Li

Abstract: This paper describes the systems submitted to IWSLT 2021 by the Volctrans team. We participate in the offline speech translation and text-to-text simultaneous translation tracks. For offline speech translation, our best end-to-end model achieves 8.1 BLEU improvements over the benchmark on the MuST-C test set and is even approaching the results of a strong cascade solution. For text-to-text simulta… ▽ More This paper describes the systems submitted to IWSLT 2021 by the Volctrans team. We participate in the offline speech translation and text-to-text simultaneous translation tracks. For offline speech translation, our best end-to-end model achieves 8.1 BLEU improvements over the benchmark on the MuST-C test set and is even approaching the results of a strong cascade solution. For text-to-text simultaneous translation, we explore the best practice to optimize the wait-k model. As a result, our final submitted systems exceed the benchmark at around 7 BLEU on the same latency regime. We will publish our code and model to facilitate both future research works and industrial applications. This paper describes the systems submitted to IWSLT 2021 by the Volctrans team. We participate in the offline speech translation and text-to-text simultaneous translation tracks. For offline speech translation, our best end-to-end model achieves 7.9 BLEU improvements over the benchmark on the MuST-C test set and is even approaching the results of a strong cascade solution. For text-to-text simultaneous translation, we explore the best practice to optimize the wait-k model. As a result, our final submitted systems exceed the benchmark at around 7 BLEU on the same latency regime. We release our code and model at \url{https://github.com/bytedance/neurst/tree/master/examples/iwslt21} to facilitate both future research works and industrial applications. △ Less

Submitted 30 June, 2021; v1 submitted 15 May, 2021; originally announced May 2021.

Comments: IWSLT 2021

Spectral Temporal Graph Neural Network for Multivariate Time-series Forecasting

Authors: Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Conguri Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, Qi Zhang

Abstract: Multivariate time-series forecasting plays a crucial role in many real-world applications. It is a challenging problem as one needs to consider both intra-series temporal correlations and inter-series correlations simultaneously. Recently, there have been multiple works trying to capture both correlations, but most, if not all of them only capture temporal correlations in the time domain and resor… ▽ More Multivariate time-series forecasting plays a crucial role in many real-world applications. It is a challenging problem as one needs to consider both intra-series temporal correlations and inter-series correlations simultaneously. Recently, there have been multiple works trying to capture both correlations, but most, if not all of them only capture temporal correlations in the time domain and resort to pre-defined priors as inter-series relationships. In this paper, we propose Spectral Temporal Graph Neural Network (StemGNN) to further improve the accuracy of multivariate time-series forecasting. StemGNN captures inter-series correlations and temporal dependencies \textit{jointly} in the \textit{spectral domain}. It combines Graph Fourier Transform (GFT) which models inter-series correlations and Discrete Fourier Transform (DFT) which models temporal dependencies in an end-to-end framework. After passing through GFT and DFT, the spectral representations hold clear patterns and can be predicted effectively by convolution and sequential learning modules. Moreover, StemGNN learns inter-series correlations automatically from the data without using pre-defined priors. We conduct extensive experiments on ten real-world datasets to demonstrate the effectiveness of StemGNN. Code is available at https://github.com/microsoft/StemGNN/ △ Less

Submitted 13 March, 2021; originally announced March 2021.

Comments: Accepted by NeurIPS 2020. 20 pages, 7 figures

Multivariate Time-series Anomaly Detection via Graph Attention Network

Authors: Hang Zhao, Yujing Wang, Juanyong Duan, Congrui Huang, Defu Cao, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, Qi Zhang

Abstract: Anomaly detection on multivariate time-series is of great importance in both data mining research and industrial applications. Recent approaches have achieved significant progress in this topic, but there is remaining limitations. One major limitation is that they do not capture the relationships between different time-series explicitly, resulting in inevitable false alarms. In this paper, we prop… ▽ More Anomaly detection on multivariate time-series is of great importance in both data mining research and industrial applications. Recent approaches have achieved significant progress in this topic, but there is remaining limitations. One major limitation is that they do not capture the relationships between different time-series explicitly, resulting in inevitable false alarms. In this paper, we propose a novel self-supervised framework for multivariate time-series anomaly detection to address this issue. Our framework considers each univariate time-series as an individual feature and includes two graph attention layers in parallel to learn the complex dependencies of multivariate time-series in both temporal and feature dimensions. In addition, our approach jointly optimizes a forecasting-based model and are construction-based model, obtaining better time-series representations through a combination of single-timestamp prediction and reconstruction of the entire time-series. We demonstrate the efficacy of our model through extensive experiments. The proposed method outperforms other state-of-the-art models on three real-world datasets. Further analysis shows that our method has good interpretability and is useful for anomaly diagnosis. △ Less

Submitted 4 September, 2020; originally announced September 2020.

Comments: Accepted by ICDM 2020. 10 pages

Toward Terabits-per-second Communications: Low-Complexity Parallel Decoding of $G_N$-Coset Codes

Authors: Xianbin Wang, Jiajie Tong, Huazi Zhang, Shengchen Dai, Rong Li, Jun Wang

Abstract: Recently, a parallel decoding framework of $G_N$-coset codes was proposed. High throughput is achieved by decoding the independent component polar codes in parallel. Various algorithms can be employed to decode these component codes, enabling a flexible throughput-performance tradeoff. In this work, we adopt SC as the component decoders to achieve the highest-throughput end of the tradeoff. The be… ▽ More Recently, a parallel decoding framework of $G_N$-coset codes was proposed. High throughput is achieved by decoding the independent component polar codes in parallel. Various algorithms can be employed to decode these component codes, enabling a flexible throughput-performance tradeoff. In this work, we adopt SC as the component decoders to achieve the highest-throughput end of the tradeoff. The benefits over soft-output component decoders are reduced complexity and simpler (binary) interconnections among component decoders. To reduce performance degradation, we integrate an error detector and a log-likelihood ratio (LLR) generator into each component decoder. The LLR generator, specifically the damping factors therein, is designed by a genetic algorithm. This low-complexity design can achieve an area efficiency of $533Gbps/mm^2$ under 7nm technology. △ Less

Submitted 21 April, 2020; originally announced April 2020.

Comments: 5 pages, 6 figures

Toward Terabits-per-second Communications: A High-Throughput Hardware Implementation of $G_N$-Coset Codes

Authors: Jiajie Tong, Xianbin Wang, Qifan Zhang, Huazi Zhang, Shengchen Dai, Rong Li, Jun Wang

Abstract: Recently, a parallel decoding algorithm of $G_N$-coset codes was proposed.The algorithm exploits two equivalent decoding graphs.For each graph, the inner code part, which consists of independent component codes, is decoded in parallel. The extrinsic information of the code bits is obtained and iteratively exchanged between the graphs until convergence. This algorithm enjoys a higher decoding paral… ▽ More Recently, a parallel decoding algorithm of $G_N$-coset codes was proposed.The algorithm exploits two equivalent decoding graphs.For each graph, the inner code part, which consists of independent component codes, is decoded in parallel. The extrinsic information of the code bits is obtained and iteratively exchanged between the graphs until convergence. This algorithm enjoys a higher decoding parallelism than the previous successive cancellation algorithms, due to the avoidance of serial outer code processing. In this work, we present a hardware implementation of the parallel decoding algorithm, it can support maximum $N=16384$. We complete the decoder's physical layout in TSMC $16nm$ process and the size is $999.936μm\times 999.936μm, \,\approx 1.00mm^2$. The decoder's area efficiency and power consumption are evaluated for the cases of $N=16384,K=13225$ and $N=16384, K=14161$. Scaled to $7nm$ process, the decoder's throughput is higher than $477Gbps/mm^2$ and $533Gbps/mm^2$ with five iterations. △ Less

Submitted 21 April, 2020; originally announced April 2020.

Comments: 5 pages, 6 figures

A Soft Cancellation Decoder for Parity-Check Polar Codes

Authors: Jiajie Tong, Huazi Zhang, Xianbin Wang, Shengchen Dai, Rong Li, Jun Wang

Abstract: Polar codes has been selected as the channel coding scheme for 5G new radio (NR) control channel. Specifically, a special type of parity-check polar (PC-Polar) codes was adopted in uplink control information (UCI). In this paper, we propose a parity-check soft-cancellation (PC-SCAN) algorithm and its simplified version to decode PC-Polar codes. The potential benefits are two-fold. First, PC-SCAN c… ▽ More Polar codes has been selected as the channel coding scheme for 5G new radio (NR) control channel. Specifically, a special type of parity-check polar (PC-Polar) codes was adopted in uplink control information (UCI). In this paper, we propose a parity-check soft-cancellation (PC-SCAN) algorithm and its simplified version to decode PC-Polar codes. The potential benefits are two-fold. First, PC-SCAN can provide soft output for PC-Polar codes, which is essential for advanced turbo receivers. Second, the decoding performance is better than that of successive cancellation (SC). This is due to the fact that parity-check constraints can be exploited by PC-SCAN to enhance the reliability of other information bits over the iterations. Moreover, we describe a cyclic-shift-register (CSR) based implementation "CSR-SCAN" to reduce both hardware cost and latency with minimum performance loss. △ Less

Submitted 2 July, 2020; v1 submitted 19 March, 2020; originally announced March 2020.

Comments: 8 pages, 14 figures, short version accepted by IEEE PIMRC 2020

On the Performance of Massive MIMO Systems With Low-Resolution ADCs Over Rician Fading Channels

Authors: Tianle Liu, Jun Tong, Qinghua Guo, Jiangtao Xi, Yanguang Yu, Zhitao Xiao

Abstract: This paper considers uplink massive multiple-input multiple-output (MIMO) systems with lowresolution analog-to-digital converters (ADCs) over Rician fading channels. Maximum-ratio-combining (MRC) and zero-forcing (ZF) receivers are considered under the assumption of perfect and imperfect channel state information (CSI). Low-resolution ADCs are considered for both data detection and channel estimat… ▽ More This paper considers uplink massive multiple-input multiple-output (MIMO) systems with lowresolution analog-to-digital converters (ADCs) over Rician fading channels. Maximum-ratio-combining (MRC) and zero-forcing (ZF) receivers are considered under the assumption of perfect and imperfect channel state information (CSI). Low-resolution ADCs are considered for both data detection and channel estimation, and the resulting performance is analyzed. Asymptotic approximations of the spectrum efficiency (SE) for large systems are derived based on random matrix theory. With these results, we can provide insights into the trade-offs between the SE and the ADC resolution and study the influence of the Rician K-factors on the performance. It is shown that a large value of K-factors may lead to better performance and alleviate the influence of quantization noise on channel estimation. Moreover, we investigate the power scaling laws for both receivers under imperfect CSI and it shows that when the number of base station (BS) antennas is very large, without loss of SE performance, the transmission power can be scaled by the number of BS antennas for both receivers while the overall performance is limited by the resolution of ADCs. The asymptotic analysis is validated by numerical results. Besides, it is also shown that the SE gap between the two receivers is narrowed down when the K-factor is increased. We also show that ADCs with moderate resolutions lead to better energy efficiency (EE) than that with high-resolution or extremely low-resolution ADCs and using ZF receivers achieve higher EE as compared with the MRC receivers. △ Less

Submitted 24 June, 2019; originally announced June 2019.

Comments: 12 pages, 7 figures

Time-Series Anomaly Detection Service at Microsoft

Authors: Hansheng Ren, Bixiong Xu, Yujing Wang, Chao Yi, Congrui Huang, Xiaoyu Kou, Tony Xing, Mao Yang, Jie Tong, Qi Zhang

Abstract: Large companies need to monitor various metrics (for example, Page Views and Revenue) of their applications and services in real time. At Microsoft, we develop a time-series anomaly detection service which helps customers to monitor the time-series continuously and alert for potential incidents on time. In this paper, we introduce the pipeline and algorithm of our anomaly detection service, which… ▽ More Large companies need to monitor various metrics (for example, Page Views and Revenue) of their applications and services in real time. At Microsoft, we develop a time-series anomaly detection service which helps customers to monitor the time-series continuously and alert for potential incidents on time. In this paper, we introduce the pipeline and algorithm of our anomaly detection service, which is designed to be accurate, efficient and general. The pipeline consists of three major modules, including data ingestion, experimentation platform and online compute. To tackle the problem of time-series anomaly detection, we propose a novel algorithm based on Spectral Residual (SR) and Convolutional Neural Network (CNN). Our work is the first attempt to borrow the SR model from visual saliency detection domain to time-series anomaly detection. Moreover, we innovatively combine SR and CNN together to improve the performance of SR model. Our approach achieves superior experimental results compared with state-of-the-art baselines on both public datasets and Microsoft production data. △ Less

Submitted 10 June, 2019; originally announced June 2019.

Comments: KDD 2019

Recovering Dropped Pronouns in Chinese Conversations via Modeling Their Referents

Authors: Jingxuan Yang, Jianzhuo Tong, Si Li, Sheng Gao, Jun Guo, Nianwen Xue

Abstract: Pronouns are often dropped in Chinese sentences, and this happens more frequently in conversational genres as their referents can be easily understood from context. Recovering dropped pronouns is essential to applications such as Information Extraction where the referents of these dropped pronouns need to be resolved, or Machine Translation when Chinese is the source language. In this work, we pre… ▽ More Pronouns are often dropped in Chinese sentences, and this happens more frequently in conversational genres as their referents can be easily understood from context. Recovering dropped pronouns is essential to applications such as Information Extraction where the referents of these dropped pronouns need to be resolved, or Machine Translation when Chinese is the source language. In this work, we present a novel end-to-end neural network model to recover dropped pronouns in conversational data. Our model is based on a structured attention mechanism that models the referents of dropped pronouns utilizing both sentence-level and word-level information. Results on three different conversational genres show that our approach achieves a significant improvement over the current state of the art. △ Less

Submitted 17 May, 2019; originally announced June 2019.

Comments: accepted by NAACL 2019

Gridless Variational Bayesian Channel Estimation for Antenna Array Systems with Low Resolution ADCs

Authors: Jiang Zhu, Chao-kai Wen, Jun Tong, Chongbin Xu, Shi Jin

Abstract: Employing low-resolution analog-to-digital converters (ADCs) coupled with large antenna arrays at the receivers has drawn considerable interests in the millimeter wave (mm-wave) system. Since mm-wave channels are sparse in angular dimensions, exploiting the structure could reduce the number of measurements while achieve acceptable performance at the same time. Motivated by the variational Bayesian… ▽ More Employing low-resolution analog-to-digital converters (ADCs) coupled with large antenna arrays at the receivers has drawn considerable interests in the millimeter wave (mm-wave) system. Since mm-wave channels are sparse in angular dimensions, exploiting the structure could reduce the number of measurements while achieve acceptable performance at the same time. Motivated by the variational Bayesian line spectral estimation (VALSE) algorithm which treats the angles as random parameters, in contrast with previous works which confine the estimate to the set of grid angle points and induce grid mismatch, this paper proposes the grid-less quantized variational Bayesian channel estimation (GL-QVBCE) algorithm for antenna array systems with low resolution ADCs. Compared to the traditional least squares (LS) approach, numerical results show that GL-QVBCE performs significantly better and asymptotically approaches the Cramèr Rao bound (CRB). △ Less

Submitted 3 June, 2019; originally announced June 2019.

Comments: 25 pages in a single column

On the Construction of $G_N$-coset Codes for Parallel Decoding

Authors: Xianbin Wang, Huazi Zhang, Rong Li, Jiajie Tong, Yiqun Ge, Jun Wang

Abstract: In this paper, we propose a type of $G_N$-coset codes for a highly parallel stage-permuted turbo-like decoder. The decoder exploits the equivalence between two stage-permuted factor graphs of $G_N$-coset codes. Specifically, the inner codes of a $G_N$-coset code consist of independent component codes, thus are decoded in parallel. The extrinsic information of the code bits is obtained and iterativ… ▽ More In this paper, we propose a type of $G_N$-coset codes for a highly parallel stage-permuted turbo-like decoder. The decoder exploits the equivalence between two stage-permuted factor graphs of $G_N$-coset codes. Specifically, the inner codes of a $G_N$-coset code consist of independent component codes, thus are decoded in parallel. The extrinsic information of the code bits is obtained and iteratively exchanged between the two graphs until convergence. Accordingly, we explore a heuristic and flexible code construction method (information set selection) for various information lengths and coding rates. Simulations show that the proposed $G_N$-coset codes could achieve a coding performance comparable with polar codes but enjoy higher decoding parallelism. △ Less

Submitted 29 October, 2019; v1 submitted 30 April, 2019; originally announced April 2019.

Comments: 6 pages, 6 figures

Pre-training of Context-aware Item Representation for Next Basket Recommendation

Authors: Jingxuan Yang, Jun Xu, Jianzhuo Tong, Sheng Gao, Jun Guo, Jirong Wen

Abstract: Next basket recommendation, which aims to predict the next a few items that a user most probably purchases given his historical transactions, plays a vital role in market basket analysis. From the viewpoint of item, an item could be purchased by different users together with different items, for different reasons. Therefore, an ideal recommender system should represent an item considering its tran… ▽ More Next basket recommendation, which aims to predict the next a few items that a user most probably purchases given his historical transactions, plays a vital role in market basket analysis. From the viewpoint of item, an item could be purchased by different users together with different items, for different reasons. Therefore, an ideal recommender system should represent an item considering its transaction contexts. Existing state-of-the-art deep learning methods usually adopt the static item representations, which are invariant among all of the transactions and thus cannot achieve the full potentials of deep learning. Inspired by the pre-trained representations of BERT in natural language processing, we propose to conduct context-aware item representation for next basket recommendation, called Item Encoder Representations from Transformers (IERT). In the offline phase, IERT pre-trains deep item representations conditioning on their transaction contexts. In the online recommendation phase, the pre-trained model is further fine-tuned with an additional output layer. The output contextualized item embeddings are used to capture users' sequential behaviors and general tastes to conduct recommendation. Experimental results on the Ta-Feng data set show that IERT outperforms the state-of-the-art baseline methods, which demonstrated the effectiveness of IERT in next basket representation. △ Less

Submitted 14 April, 2019; originally announced April 2019.

An Asymmetric Adaptive SCL Decoder Hardware for Ultra-Low-Error-Rate Polar Codes

Authors: Jiajie Tong, Huazi Zhang, Lingchen Huang, Xiaocheng Liu, Jun Wang

Abstract: In theory, Polar codes do not exhibit an error floor under successive-cancellation (SC) decoding. In practice, frame error rate (FER) down to $10^{-12}$ has not been reported with a real SC list (SCL) decoder hardware. This paper presents an asymmetric adaptive SCL (A2SCL) decoder, implemented in real hardware, for high-throughput and ultra-reliable communications. We propose to concatenate multip… ▽ More In theory, Polar codes do not exhibit an error floor under successive-cancellation (SC) decoding. In practice, frame error rate (FER) down to $10^{-12}$ has not been reported with a real SC list (SCL) decoder hardware. This paper presents an asymmetric adaptive SCL (A2SCL) decoder, implemented in real hardware, for high-throughput and ultra-reliable communications. We propose to concatenate multiple SC decoders with an SCL decoder, in which the numbers of SC/SCL decoders are balanced with respect to their area and latency. In addition, a novel unequal-quantization technique is adopted. The two optimizations are crucial for improving SCL throughput within limited chip area. As an application, we build a link-level FPGA emulation platform to measure ultra-low FERs of 3GPP NR Polar codes (with parity-check and CRC bits). It is flexible to support all list sizes up to $8$, code lengths up to $1024$ and arbitrary code rates. With the proposed hardware, decoding speed is 7000 times faster than a CPU core. For the first time, FER as low as $10^{-12}$ is measured and quantization effect is analyzed. △ Less

Submitted 3 April, 2019; originally announced April 2019.