OpenRaiser/Intern-Atlas huggingface dataset:
Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time
Venue: arXiv cs.DS 2021
Year: 2021

We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. The input to the problem is an $n$-vertex $m$-edge graph $G$ with non-negative edge lengths, that undergoes a sequence of edge deletions. The goal is to support approximate shortest-path queries: given a pair $x,y$ of vertices of $G$, return a path $P$ connecting $x$ to $y$, whose length is within factor $α$ of the length of the shortest $x$-$y$ path, in time $\tilde O(|E(P)|)$, where $α$ is the approximation factor of the algorithm. APSP is one of the most basic and extensively studied dynamic graph problems. A long line of work culminated in the algorithm of [Chechik, FOCS 2018] with near optimal guarantees for the oblivious-adversary setting. Unfortunately, adaptive-adversary setting is still poorly understood. For unweighted graphs, the algorithm of [Henzinger, Krinninger and Nanongkai, FOCS '13, SICOMP '16] achieves a $(1+ε)$-approximation with total update time $\tilde O(mn/ε)$; the best current total update time of $n^{2.5+O(ε)}$ is achieved by the deterministic algorithm of [Chuzhoy, Saranurak, SODA'21], with $2^{O(1/ε)}$-multiplicative and $2^{O(\log^{3/4}n/ε)}$-additive approximation. To the best of our knowledge, for arbitrary non-negative edge weights, the fastest current adaptive-update algorithm has total update time $O(n^{3}\log L/ε)$, achieving a $(1+ε)$-approximation. Here, L is the ratio of longest to shortest edge lengths. Our main result is a deterministic algorithm for decremental APSP in undirected edge-weighted graphs, that, for any $Ω(1/\log\log m)\leq ε< 1$, achieves approximation factor $(\log m)^{2^{O(1/ε)}}$, with total update time $O\left (m^{1+O(ε)}\cdot (\log m)^{O(1/ε^2)}\cdot \log L\right )$.
Batched Data-Driven Evolutionary Multi-Objective Optimization Based on Manifold Interpolation
Venue: arXiv cs.NE 2021
Year: 2021

Multi-objective optimization problems are ubiquitous in real-world science, engineering and design optimization problems. It is not uncommon that the objective functions are as a black box, the evaluation of which usually involve time-consuming and/or costly physical experiments. Data-driven evolutionary optimization can be used to search for a set of non-dominated trade-off solutions, where the expensive objective functions are approximated as a surrogate model. In this paper, we propose a framework for implementing batched data-driven evolutionary multi-objective optimization. It is so general that any off-the-shelf evolutionary multi-objective optimization algorithms can be applied in a plug-in manner. In particular, it has two unique components: 1) based on the Karush-Kuhn-Tucker conditions, a manifold interpolation approach that explores more diversified solutions with a convergence guarantee along the manifold of the approximated Pareto-optimal set; and 2) a batch recommendation approach that reduces the computational time of the optimization process by evaluating multiple samples at a time in parallel. Experiments on 136 benchmark test problem instances with irregular Pareto-optimal front shapes against six state-of-the-art surrogate-assisted EMO algorithms fully demonstrate the effectiveness and superiority of our proposed framework. In particular, our proposed framework is featured with a faster convergence and a stronger resilience to various PF shapes.
SCORE-IT: A Machine Learning-based Tool for Automatic Standardization of EEG Reports
Venue: arXiv cs.CL 2021
Year: 2021

Machine learning (ML)-based analysis of electroencephalograms (EEGs) is playing an important role in advancing neurological care. However, the difficulties in automatically extracting useful metadata from clinical records hinder the development of large-scale EEG-based ML models. EEG reports, which are the primary sources of metadata for EEG studies, suffer from lack of standardization. Here we propose a machine learning-based system that automatically extracts components from the SCORE specification from unstructured, natural-language EEG reports. Specifically, our system identifies (1) the type of seizure that was observed in the recording, per physician impression; (2) whether the session recording was normal or abnormal according to physician impression; (3) whether the patient was diagnosed with epilepsy or not. We performed an evaluation of our system using the publicly available TUH EEG corpus and report F1 scores of 0.92, 0.82, and 0.97 for the respective tasks.
Exploiting Heterogeneity in Robust Federated Best-Arm Identification
Venue: arXiv cs.LG 2021
Year: 2021

We study a federated variant of the best-arm identification problem in stochastic multi-armed bandits: a set of clients, each of whom can sample only a subset of the arms, collaborate via a server to identify the best arm (i.e., the arm with the highest mean reward) with prescribed confidence. For this problem, we propose Fed-SEL, a simple communication-efficient algorithm that builds on successive elimination techniques and involves local sampling steps at the clients. To study the performance of Fed-SEL, we introduce a notion of arm-heterogeneity that captures the level of dissimilarity between distributions of arms corresponding to different clients. Interestingly, our analysis reveals the benefits of arm-heterogeneity in reducing both the sample- and communication-complexity of Fed-SEL. As a special case of our analysis, we show that for certain heterogeneous problem instances, Fed-SEL outputs the best-arm after just one round of communication. Our findings have the following key implication: unlike federated supervised learning where recent work has shown that statistical heterogeneity can lead to poor performance, one can provably reap the benefits of both local computation and heterogeneity for federated best-arm identification. As our final contribution, we develop variants of Fed-SEL, both for federated and peer-to-peer settings, that are robust to the presence of Byzantine clients, and hence suitable for deployment in harsh, adversarial environments.
CEM: Commonsense-aware Empathetic Response Generation
Venue: arXiv cs.CL 2021
Year: 2021

A key trait of daily conversations between individuals is the ability to express empathy towards others, and exploring ways to implement empathy is a crucial step towards human-like dialogue systems. Previous approaches on this topic mainly focus on detecting and utilizing the user's emotion for generating empathetic responses. However, since empathy includes both aspects of affection and cognition, we argue that in addition to identifying the user's emotion, cognitive understanding of the user's situation should also be considered. To this end, we propose a novel approach for empathetic response generation, which leverages commonsense to draw more information about the user's situation and uses this additional information to further enhance the empathy expression in generated responses. We evaluate our approach on EmpatheticDialogues, which is a widely-used benchmark dataset for empathetic response generation. Empirical results demonstrate that our approach outperforms the baseline models in both automatic and human evaluations and can generate more informative and empathetic responses.
ChangeChip: A Reference-Based Unsupervised Change Detection for PCB Defect Detection
Venue: arXiv cs.CV 2021
Year: 2021

The usage of electronic devices increases, and becomes predominant in most aspects of life. Surface Mount Technology (SMT) is the most common industrial method for manufacturing electric devices in which electrical components are mounted directly onto the surface of a Printed Circuit Board (PCB). Although the expansion of electronic devices affects our lives in a productive way, failures or defects in the manufacturing procedure of those devices might also be counterproductive and even harmful in some cases. It is therefore desired and sometimes crucial to ensure zero-defect quality in electronic devices and their production. While traditional Image Processing (IP) techniques are not sufficient to produce a complete solution, other promising methods like Deep Learning (DL) might also be challenging for PCB inspection, mainly because such methods require big adequate datasets which are missing, not available or not updated in the rapidly growing field of PCBs. Thus, PCB inspection is conventionally performed manually by human experts. Unsupervised Learning (UL) methods may potentially be suitable for PCB inspection, having learning capabilities on the one hand, while not relying on large datasets on the other. In this paper, we introduce ChangeChip, an automated and integrated change detection system for defect detection in PCBs, from soldering defects to missing or misaligned electronic elements, based on Computer Vision (CV) and UL. We achieve good quality defect detection by applying an unsupervised change detection between images of a golden PCB (reference) and the inspected PCB under various setting. In this work, we also present CD-PCB, a synthesized labeled dataset of 20 pairs of PCB images for evaluation of defect detection algorithms.
Rectangle-based Approximation for Rendering Glossy Interreflections
Venue: arXiv cs.GR 2021
Year: 2021

This study introduces an approximation for rendering one bounce glossy interreflection in real time. The solution is based on the most representative point (MRP) and extends to a sampling disk near the MRP. Our algorithm represents geometry as rectangle proxies and specular reflections using a spherical Gaussian. The reflected radiance from the disk was efficiently approximated by selecting a representative attenuation axis in the sampling disk. We provide an efficient approximation of the glossy interreflection and can efficiently perform the approximation at runtime. Our method uses forward rendering (without using GBuffer), which is more suitable for platforms that favor forward rendering, such as mobile applications and virtual reality.
Leveraging Clinical Characteristics for Improved Deep Learning-Based Kidney Tumor Segmentation on CT
Venue: arXiv cs.CV 2021
Year: 2021

This paper assesses whether using clinical characteristics in addition to imaging can improve automated segmentation of kidney cancer on contrast-enhanced computed tomography (CT). A total of 300 kidney cancer patients with contrast-enhanced CT scans and clinical characteristics were included. A baseline segmentation of the kidney cancer was performed using a 3D U-Net. Input to the U-Net were the contrast-enhanced CT images, output were segmentations of kidney, kidney tumors, and kidney cysts. A cognizant sampling strategy was used to leverage clinical characteristics for improved segmentation. To this end, a Least Absolute Shrinkage and Selection Operator (LASSO) was used. Segmentations were evaluated using Dice and Surface Dice. Improvement in segmentation was assessed using Wilcoxon signed rank test. The baseline 3D U-Net showed a segmentation performance of 0.90 for kidney and kidney masses, i.e., kidney, tumor, and cyst, 0.29 for kidney masses, and 0.28 for kidney tumor, while the 3D U-Net trained with cognizant sampling enhanced the segmentation performance and reached Dice scores of 0.90, 0.39, and 0.38 respectively. To conclude, the cognizant sampling strategy leveraging the clinical characteristics significantly improved kidney cancer segmentation.
Conditional MoCoGAN for Zero-Shot Video Generation
Venue: arXiv cs.CV 2021
Year: 2021

We propose a conditional generative adversarial network (GAN) model for zero-shot video generation. In this study, we have explored zero-shot conditional generation setting. In other words, we generate unseen videos from training samples with missing classes. The task is an extension of conditional data generation. The key idea is to learn disentangled representations in the latent space of a GAN. To realize this objective, we base our model on the motion and content decomposed GAN and conditional GAN for image generation. We build the model to find better-disentangled representations and to generate good-quality videos. We demonstrate the effectiveness of our proposed model through experiments on the Weizmann action database and the MUG facial expression database.
Whittle Index Based Scheduling Policy for Minimizing the Cost of Age of Information
Venue: arXiv cs.IT 2021
Year: 2021

We design a new scheduling policy to minimize the general non-decreasing cost function of age of information (AoI) in a multiuser system. In this system, the base station stochastically generates time-sensitive packets and transmits them to corresponding user equipments via an unreliable channel. We first formulate the transmission scheduling problem as an average cost constrained Markov decision process problem. Through introducing the service charge, we derive the closed-form expression for the Whittle index, based on which we design the scheduling policy. Using numerical results, we demonstrate the performance gain of our designed scheduling policy compared to the existing policies, such as the optimal policy, the on-demand Whittle index policy, and the age greedy policy.
Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation
Venue: arXiv cs.DB 2021
Year: 2021

Cardinality estimation (CardEst) plays a significant role in generating high-quality query plans for a query optimizer in DBMS. In the last decade, an increasing number of advanced CardEst methods (especially ML-based) have been proposed with outstanding estimation accuracy and inference latency. However, there exists no study that systematically evaluates the quality of these methods and answer the fundamental problem: to what extent can these methods improve the performance of query optimizer in real-world settings, which is the ultimate goal of a CardEst method. In this paper, we comprehensively and systematically compare the effectiveness of CardEst methods in a real DBMS. We establish a new benchmark for CardEst, which contains a new complex real-world dataset STATS and a diverse query workload STATS-CEB. We integrate multiple most representative CardEst methods into an open-source database system PostgreSQL, and comprehensively evaluate their true effectiveness in improving query plan quality, and other important aspects affecting their applicability, ranging from inference latency, model size, and training time, to update efficiency and accuracy. We obtain a number of key findings for the CardEst methods, under different data and query settings. Furthermore, we find that the widely used estimation accuracy metric(Q-Error) cannot distinguish the importance of different sub-plan queries during query optimization and thus cannot truly reflect the query plan quality generated by CardEst methods. Therefore, we propose a new metric P-Error to evaluate the performance of CardEst methods, which overcomes the limitation of Q-Error and is able to reflect the overall end-to-end performance of CardEst methods. We have made all of the benchmark data and evaluation code publicly available at https://github.com/Nathaniel-Han/End-to-End-CardEst-Benchmark.
Data-Centric and Data-Aware Frameworks for Fundamentally Efficient Data Handling in Modern Computing Systems
Venue: arXiv cs.AR 2021
Year: 2021

There is an explosive growth in the size of the input and/or intermediate data used and generated by modern and emerging applications. Unfortunately, modern computing systems are not capable of handling large amounts of data efficiently. Major concepts and components (e.g., the virtual memory system) and predominant execution models (e.g., the processor-centric execution model) used in almost all computing systems are designed without having modern applications' overwhelming data demand in mind. As a result, accessing, moving, and processing large amounts of data faces important challenges in today's systems, making data a first-class concern and a prime performance and energy bottleneck in such systems. This thesis studies the root cause of inefficiency in modern computing systems when handling modern applications' data demand, and aims to fundamentally address such inefficiencies, with a focus on two directions. First, we design SIMDRAM, an end-to-end processing-using-DRAM framework that aids the widespread adoption of processing-using-DRAM, a data-centric computation paradigm that improves the overall performance and efficiency of the system when computing large amounts of data by minimizing the cost of data movement and enabling computation where the data resides. Second, we introduce the Virtual Block Interface (VBI), a novel virtual memory framework that 1) eliminates the inefficiencies of the conventional virtual memory frameworks when handling the high memory demand in modern applications, and 2) is built from the ground up to understand, convey, and exploit data properties, to create opportunities for performance and efficiency improvements.
Online Learning of Optimally Diverse Rankings
Venue: arXiv cs.LG 2021
Year: 2021

Search engines answer users' queries by listing relevant items (e.g. documents, songs, products, web pages, ...). These engines rely on algorithms that learn to rank items so as to present an ordered list maximizing the probability that it contains relevant item. The main challenge in the design of learning-to-rank algorithms stems from the fact that queries often have different meanings for different users. In absence of any contextual information about the query, one often has to adhere to the {\it diversity} principle, i.e., to return a list covering the various possible topics or meanings of the query. To formalize this learning-to-rank problem, we propose a natural model where (i) items are categorized into topics, (ii) users find items relevant only if they match the topic of their query, and (iii) the engine is not aware of the topic of an arriving query, nor of the frequency at which queries related to various topics arrive, nor of the topic-dependent click-through-rates of the items. For this problem, we devise LDR (Learning Diverse Rankings), an algorithm that efficiently learns the optimal list based on users' feedback only. We show that after $T$ queries, the regret of LDR scales as $O((N-L)\log(T))$ where $N$ is the number of all items. We further establish that this scaling cannot be improved, i.e., LDR is order optimal. Finally, using numerical experiments on both artificial and real-world data, we illustrate the superiority of LDR compared to existing learning-to-rank algorithms.
Single-Target Real-Time Passive WiFi Tracking
Venue: arXiv cs.NI 2021
Year: 2021

Device-free human tracking is an essential ingredient for ubiquitous wireless sensing. Recent passive WiFi tracking systems face the challenges of inaccurate separation of dynamic human components and time-consuming estimation of multi-dimensional signal parameters. In this work, we present a scheme named WiFi Doppler Frequency Shift (WiDFS), which can achieve single-target real-time passive tracking using channel state information (CSI) collected from commercial-off-the-shelf (COTS) WiFi devices. We consider the typical system setup including a transmitter with a single antenna and a receiver with three antennas; while our scheme can be readily extended to another setup. To remove the impact of transceiver asynchronization, we first apply CSI cross-correlation between each RX antenna pair. We then combine them to estimate a Doppler frequency shift (DFS) in a short-time window. After that, we leverage the DFS estimate to separate dynamic human components from CSI self-correlation terms of each antenna, thereby separately calculating angle-of-arrival (AoA) and human reflection distance for tracking. In addition, a hardware calibration algorithm is presented to refine the spacing between RX antennas and eliminate the hardware-related phase differences between them. A prototype demonstrates that WiDFS can achieve real-time tracking with a median position error of 72.32 cm in multipath-rich environments.
Coded Relaying in LoRa Sensor Networks
Venue: arXiv cs.NI 2021
Year: 2021

To enhance the reliability of LoRa sensor networks, we propose two opportunistic forwarding protocols in which relays overhear sensor-to-gateway messages and periodically forward them to a gateway. To reduce the number of transmissions, the relays forward XOR sums of the overheard messages. One protocol employs a single relay node, while two relays cooperate in the other. With a single relay, our proposed protocol requires fewer relay transmissions to achieve similar loss rates as conventional uncoded forwarding in which every received message is immediately forwarded. We demonstrate up to 55% reduction in relay transmission time relative to uncoded forwarding. The cooperative protocol provides better loss and delay performance than the single-relay protocol, and we demonstrate up to 16% reduction in the message-loss rate along with 33% reduction in relay transmission times compared to conventional forwarding.
Graph-based Retrieval for Claim Verification over Cross-Document Evidence
Venue: arXiv cs.IR 2021
Year: 2021

Verifying the veracity of claims requires reasoning over a large knowledge base, often in the form of corpora of trustworthy sources. A common approach consists in retrieving short portions of relevant text from the reference documents and giving them as input to a natural language inference module that determines whether the claim can be inferred or contradicted from them. This approach, however, struggles when multiple pieces of evidence need to be collected and combined from different documents, since the single documents are often barely related to the target claim and hence they are left out by the retrieval module. We conjecture that a graph-based approach can be beneficial to identify fragmented evidence. We tested this hypothesis by building, over the whole corpus, a large graph that interconnects text portions by means of mentioned entities and exploiting such a graph for identifying candidate sets of evidence from multiple sources. Our experiments show that leveraging on a graph structure is beneficial in identifying a reasonably small portion of passages related to a claim.
Semantics-Guided Contrastive Network for Zero-Shot Object detection
Venue: arXiv cs.CV 2021
Year: 2021

Zero-shot object detection (ZSD), the task that extends conventional detection models to detecting objects from unseen categories, has emerged as a new challenge in computer vision. Most existing approaches tackle the ZSD task with a strict mapping-transfer strategy, which may lead to suboptimal ZSD results: 1) the learning process of those models ignores the available unseen class information, and thus can be easily biased towards the seen categories; 2) the original visual feature space is not well-structured and lack of discriminative information. To address these issues, we develop a novel Semantics-Guided Contrastive Network for ZSD, named ContrastZSD, a detection framework that first brings contrastive learning mechanism into the realm of zero-shot detection. Particularly, ContrastZSD incorporates two semantics-guided contrastive learning subnets that contrast between region-category and region-region pairs respectively. The pairwise contrastive tasks take advantage of additional supervision signals derived from both ground truth label and pre-defined class similarity distribution. Under the guidance of those explicit semantic supervision, the model can learn more knowledge about unseen categories to avoid the bias problem to seen concepts, while optimizing the data structure of visual features to be more discriminative for better visual-semantic alignment. Extensive experiments are conducted on two popular benchmarks for ZSD, i.e., PASCAL VOC and MS COCO. Results show that our method outperforms the previous state-of-the-art on both ZSD and generalized ZSD tasks.