OpenRaiser/Intern-Atlas huggingface dataset:
Reallocation Problems with Minimum Completion Time
Venue: arXiv cs.DS 2021
Year: 2021

Reallocation scheduling is one of the most fundamental problems in various areas such as supply chain management, logistics, and transportation science. In this paper, we introduce the reallocation problem that models the scheduling in which products are with fixed cost, non-fungible, and reallocated in parallel, and comprehensively study the complexity of the problem under various settings of the transition time, product size, and capacities. We show that the problem can be solved in polynomial time for a fundamental setting where the product size and transition time are both uniform. We also show that the feasibility of the problem is NP-complete even for little more general settings, which implies that no polynomial-time algorithm constructs a feasible schedule of the problem unless P$=$NP. We then consider the relaxation of the problem, which we call the capacity augmentation, and derive a reallocation schedule feasible with the augmentation such that the completion time is at most the optimal of the original problem. When the warehouse capacity is sufficiently large, we design constant-factor approximation algorithms under all the settings. We also show the relationship between the reallocation problem and the bin packing problem when the warehouse and carry-in capacities are sufficiently large.
Building Damage Mapping with Self-PositiveUnlabeled Learning
Venue: arXiv cs.CV 2021
Year: 2021

Humanitarian organizations must have fast and reliable data to respond to disasters. Deep learning approaches are difficult to implement in real-world disasters because it might be challenging to collect ground truth data of the damage situation (training data) soon after the event. The implementation of recent self-paced positive-unlabeled learning (PU) is demonstrated in this work by successfully applying to building damage assessment with very limited labeled data and a large amount of unlabeled data. Self-PU learning is compared with the supervised baselines and traditional PU learning using different datasets collected from the 2011 Tohoku earthquake, the 2018 Palu tsunami, and the 2018 Hurricane Michael. By utilizing only a portion of labeled damaged samples, we show how models trained with self-PU techniques may achieve comparable performance as supervised learning.
Auto Tuning of Hadoop and Spark parameters
Venue: arXiv cs.DC 2021
Year: 2021

Data of the order of terabytes, petabytes, or beyond is known as Big Data. This data cannot be processed using the traditional database software, and hence there comes the need for Big Data Platforms. By combining the capabilities and features of various big data applications and utilities, Big Data Platforms form a single solution. It is a platform that helps to develop, deploy and manage the big data environment. Hadoop and Spark are the two open-source Big Data Platforms provided by Apache. Both these platforms have many configurational parameters, which can have unforeseen effects on the execution time, accuracy, etc. Manual tuning of these parameters can be tiresome, and hence automatic ways should be needed to tune them. After studying and analyzing various previous works in automating the tuning of these parameters, this paper proposes two algorithms - Grid Search with Finer Tuning and Controlled Random Search. The performance indicator studied in this paper is Execution Time. These algorithms help to tune the parameters automatically. Experimental results have shown a reduction in execution time of about 70% and 50% for Hadoop and 81.19% and 77.77% for Spark by Grid Search with Finer Tuning and Controlled Random Search, respectively.
Finding All Leftmost Separators of Size $\leq k$
Venue: arXiv cs.DS 2021
Year: 2021

We define a notion called leftmost separator of size at most $k$. A leftmost separator of size $k$ is a minimal separator $S$ that separates two given sets of vertices $X$ and $Y$ such that we "cannot move $S$ more towards $X$" such that $|S|$ remains smaller than the threshold. One of the incentives is that by using leftmost separators we can improve the time complexity of treewidth approximation. Treewidth approximation is a problem which is known to have a linear time FPT algorithm in terms of input size, and only single exponential in terms of the parameter, treewidth. It is not known whether this result can be improved theoretically. However, the coefficient of the parameter $k$ (the treewidth) in the exponent is large. Hence, our goal is to decrease the coefficient of $k$ in the exponent, in order to achieve a more practical algorithm. Hereby, we trade a linear-time algorithm for an $\mathcal{O}(n \log n)$-time algorithm. The previous known $\mathcal{O}(f(k) n \log n)$-time algorithms have dependences of $2^{24k}k!$, $2^{8.766k}k^2$ (a better analysis shows that it is $2^{7.671k}k^2$), and higher. In this paper, we present an algorithm for treewidth approximation which runs in time $\mathcal{O}(2^{6.755k}\ n \log n)$, Furthermore, we count the number of leftmost separators and give a tight upper bound for them. We show that the number of leftmost separators of size $\leq k$ is at most $C_{k-1}$ (Catalan number). Then, we present an algorithm which outputs all leftmost separators in time $\mathcal{O}(\frac{4^k}{\sqrt{k}}n)$.
Characterizing Human Explanation Strategies to Inform the Design of Explainable AI for Building Damage Assessment
Venue: arXiv cs.HC 2021
Year: 2021

Explainable AI (XAI) is a promising means of supporting human-AI collaborations for high-stakes visual detection tasks, such as damage detection tasks from satellite imageries, as fully-automated approaches are unlikely to be perfectly safe and reliable. However, most existing XAI techniques are not informed by the understandings of task-specific needs of humans for explanations. Thus, we took a first step toward understanding what forms of XAI humans require in damage detection tasks. We conducted an online crowdsourced study to understand how people explain their own assessments, when evaluating the severity of building damage based on satellite imagery. Through the study with 60 crowdworkers, we surfaced six major strategies that humans utilize to explain their visual damage assessments. We present implications of our findings for the design of XAI methods for such visual detection contexts, and discuss opportunities for future research.
On the Secrecy Design of STAR-RIS assisted Uplink NOMA Networks
Venue: arXiv cs.IT 2021
Year: 2021

This paper investigates the secure transmission in a simultaneously transmitting and reflecting reconfigurable intelligent surface (STAR-RIS) assisted uplink non-orthogonal multiple access system, where the legitimate users send confidential signals to the base station by exploiting STAR-RIS to reconfigure the electromagnetic propagation environment proactively. Depending on the availability of the eavesdropping channel state information (CSI), both the full CSI and statistical CSI of the eavesdropper are considered. For the full eavesdropping CSI scenario, we adopt the adaptive-rate wiretap code scheme with the aim of maximizing minimum secrecy capacity subject to the successive interference cancellation decoding order constraints. To proceed, we propose an alternating hybrid beamforming (AHB) algorithm to jointly optimize the receive beamforming, transmit power, and reflection/transmission coefficients. While for the statistical eavesdropping CSI scenario, the constant-rate wiretap code scheme is employed to minimize the maximum secrecy outage probability (SOP) subject to the quality-of-service requirements of legitimate users. Then, we derive the exact SOP expression under the constant-rate coding strategy and develop an extended AHB algorithm for the joint secrecy beamforming design. Simulation results demonstrate the effectiveness of the proposed scheme. Moreover, some useful guidance about the quantification of phase shift/amplitude and the deployment of STAR-RIS is provided.
Speech recognition for air traffic control via feature learning and end-to-end training
Venue: arXiv cs.SD 2021
Year: 2021

In this work, we propose a new automatic speech recognition (ASR) system based on feature learning and an end-to-end training procedure for air traffic control (ATC) systems. The proposed model integrates the feature learning block, recurrent neural network (RNN), and connectionist temporal classification loss to build an end-to-end ASR model. Facing the complex environments of ATC speech, instead of the handcrafted features, a learning block is designed to extract informative features from raw waveforms for acoustic modeling. Both the SincNet and 1D convolution blocks are applied to process the raw waveforms, whose outputs are concatenated to the RNN layers for the temporal modeling. Thanks to the ability to learn representations from raw waveforms, the proposed model can be optimized in a complete end-to-end manner, i.e., from waveform to text. Finally, the multilingual issue in the ATC domain is also considered to achieve the ASR task by constructing a combined vocabulary of Chinese characters and English letters. The proposed approach is validated on a multilingual real-world corpus (ATCSpeech), and the experimental results demonstrate that the proposed approach outperforms other baselines, achieving a 6.9\% character error rate.
Speed Maps: An Application to Guide Robots in Human Environments
Venue: arXiv cs.RO 2021
Year: 2021

We present the concept of speed maps: speed limits for mobile robots in human environments. Static speed maps allow for faster navigation on corridors while limiting the speed around corners and in rooms. Dynamic speed maps put limits on speed around humans. We demonstrate the concept for a mobile robot that guides people to annotated landmarks on the map. The robot keeps a metric map for navigation and a semantic map to hold planar surfaces for tasking. The system supports automatic initialization upon the detection of a specially designed QR code. We show that speed maps not only can reduce the impact of a potential collision but can also reduce navigation time.
LVIS Challenge Track Technical Report 1st Place Solution: Distribution Balanced and Boundary Refinement for Large Vocabulary Instance Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

This report introduces the technical details of the team FuXi-Fresher for LVIS Challenge 2021. Our method focuses on the problem in following two aspects: the long-tail distribution and the segmentation quality of mask and boundary. Based on the advanced HTC instance segmentation algorithm, we connect transformer backbone(Swin-L) through composite connections inspired by CBNetv2 to enhance the baseline results. To alleviate the problem of long-tail distribution, we design a Distribution Balanced method which includes dataset balanced and loss function balaced modules. Further, we use a Mask and Boundary Refinement method composed with mask scoring and refine-mask algorithms to improve the segmentation quality. In addition, we are pleasantly surprised to find that early stopping combined with EMA method can achieve a great improvement. Finally, by using multi-scale testing and increasing the upper limit of the number of objects detected per image, we achieved more than 45.4% boundary AP on the val set of LVIS Challenge 2021. On the test data of LVIS Challenge 2021, we rank 1st and achieve 48.1% AP. Notably, our APr 47.5% is very closed to the APf 48.0%.
MixSiam: A Mixture-based Approach to Self-supervised Representation Learning
Venue: arXiv cs.CV 2021
Year: 2021

Recently contrastive learning has shown significant progress in learning visual representations from unlabeled data. The core idea is training the backbone to be invariant to different augmentations of an instance. While most methods only maximize the feature similarity between two augmented data, we further generate more challenging training samples and force the model to keep predicting discriminative representation on these hard samples. In this paper, we propose MixSiam, a mixture-based approach upon the traditional siamese network. On the one hand, we input two augmented images of an instance to the backbone and obtain the discriminative representation by performing an element-wise maximum of two features. On the other hand, we take the mixture of these augmented images as input, and expect the model prediction to be close to the discriminative representation. In this way, the model could access more variant data samples of an instance and keep predicting invariant discriminative representations for them. Thus the learned model is more robust compared to previous contrastive learning methods. Extensive experiments on large-scale datasets show that MixSiam steadily improves the baseline and achieves competitive results with state-of-the-art methods. Our code will be released soon.
CoreLM: Coreference-aware Language Model Fine-Tuning
Venue: arXiv cs.CL 2021
Year: 2021

Language Models are the underpin of all modern Natural Language Processing (NLP) tasks. The introduction of the Transformers architecture has contributed significantly into making Language Modeling very effective across many NLP task, leading to significant advancements in the field. However, Transformers come with a big computational cost, which grows quadratically with respect to the input length. This presents a challenge as to understand long texts requires a lot of context. In this paper, we propose a Fine-Tuning framework, named CoreLM, that extends the architecture of current Pretrained Language Models so that they incorporate explicit entity information. By introducing entity representations, we make available information outside the contextual space of the model, which results in a better Language Model for a fraction of the computational cost. We implement our approach using GPT2 and compare the fine-tuned model to the original. Our proposed model achieves a lower Perplexity in GUMBY and LAMBDADA datasets when compared to GPT2 and a fine-tuned version of GPT2 without any changes. We also compare the models' performance in terms of Accuracy in LAMBADA and Children's Book Test, with and without the use of model-created coreference annotations.
Deep Learning Methods for Daily Wildfire Danger Forecasting
Venue: arXiv cs.LG 2021
Year: 2021

Wildfire forecasting is of paramount importance for disaster risk reduction and environmental sustainability. We approach daily fire danger prediction as a machine learning task, using historical Earth observation data from the last decade to predict next-day's fire danger. To that end, we collect, pre-process and harmonize an open-access datacube, featuring a set of covariates that jointly affect the fire occurrence and spread, such as weather conditions, satellite-derived products, topography features and variables related to human activity. We implement a variety of Deep Learning (DL) models to capture the spatial, temporal or spatio-temporal context and compare them against a Random Forest (RF) baseline. We find that either spatial or temporal context is enough to surpass the RF, while a ConvLSTM that exploits the spatio-temporal context performs best with a test Area Under the Receiver Operating Characteristic of 0.926. Our DL-based proof-of-concept provides national-scale daily fire danger maps at a much higher spatial resolution than existing operational solutions.
Multi-scale 2D Representation Learning for weakly-supervised moment retrieval
Venue: arXiv cs.CV 2021
Year: 2021

Video moment retrieval aims to search the moment most relevant to a given language query. However, most existing methods in this community often require temporal boundary annotations which are expensive and time-consuming to label. Hence weakly supervised methods have been put forward recently by only using coarse video-level label. Despite effectiveness, these methods usually process moment candidates independently, while ignoring a critical issue that the natural temporal dependencies between candidates in different temporal scales. To cope with this issue, we propose a Multi-scale 2D Representation Learning method for weakly supervised video moment retrieval. Specifically, we first construct a two-dimensional map for each temporal scale to capture the temporal dependencies between candidates. Two dimensions in this map indicate the start and end time points of these candidates. Then, we select top-K candidates from each scale-varied map with a learnable convolutional neural network. With a newly designed Moments Evaluation Module, we obtain the alignment scores of the selected candidates. At last, the similarity between captions and language query is served as supervision for further training the candidates' selector. Experiments on two benchmark datasets Charades-STA and ActivityNet Captions demonstrate that our approach achieves superior performance to state-of-the-art results.
Rapid wildfire response system based on drones
Venue: arXiv cs.RO 2021
Year: 2021

The wildfires in Australia make people suffer the losses caused by the devastating disasters. To protect people's security and the country's development in vulnerable situations, we are expected to establish a set of efficient and sustainable fire-rescuing response mechanisms and tackle the problems faced, including optimization of loadings and quantity of drones, time adaptability of the model, and the locations of radio-repeater drones. We determined the location of mobile emergency operation centers (EOC), which conduct drone launches and deploy rescue personnel. After figuring out where the EOCs are located, we can establish the Drones Planning-programming Budgeting Model to detect the configuration of drones, including optimal numbers and mix of SSA drones and Radio Repeater drones. To estimate the adaptability of our model in the next ten decades, we build a Holt-Winters seasonal model. We utilize the Drones Deployment Optimization model to optimize the locations of hovering VHF/UHF radio-repeater drones. In addition, sensitivity analysis of the model is tested.
A Dynamic Programming Method to Construct Polar Codes with Improved Performance
Venue: arXiv cs.IT 2021
Year: 2021

In the standard polar code construction, the message vector $(U_0,U_1,\dots,U_{n-1})$ is divided into information bits and frozen bits according to the reliability of each $U_i$ given $(U_0,U_1,\dots,U_{i-1})$ and all the channel outputs. While this reliability function is the most suitable measure to choose information bits under the Successive Cancellation (SC) decoder, there is a mismatch between this reliability function and the Successive Cancellation List (SCL) decoder because the SCL decoder also makes use of the information from the future frozen bits. We propose a Dynamic Programming (DP) construction of polar codes to resolve this mismatch. Our DP construction chooses different sets of information bits for different list sizes in order to optimize the performance of the constructed code under the SCL decoder. Simulation results show that our DP-polar codes consistently demonstrate $0.3$--$1$dB improvement over the standard polar codes under the SCL decoder with list size $32$ for various choices of code lengths and code rates.
Using Graph-Theoretic Machine Learning to Predict Human Driver Behavior
Venue: arXiv cs.RO 2021
Year: 2021

Studies have shown that autonomous vehicles (AVs) behave conservatively in a traffic environment composed of human drivers and do not adapt to local conditions and socio-cultural norms. It is known that socially aware AVs can be designed if there exists a mechanism to understand the behaviors of human drivers. We present an approach that leverages machine learning to predict, the behaviors of human drivers. This is similar to how humans implicitly interpret the behaviors of drivers on the road, by only observing the trajectories of their vehicles. We use graph-theoretic tools to extract driver behavior features from the trajectories and machine learning to obtain a computational mapping between the extracted trajectory of a vehicle in traffic and the driver behaviors. Compared to prior approaches in this domain, we prove that our method is robust, general, and extendable to broad-ranging applications such as autonomous navigation. We evaluate our approach on real-world traffic datasets captured in the U.S., India, China, and Singapore, as well as in simulation.
Small model property reflects in games and automata
Venue: arXiv cs.LO 2021
Year: 2021

Small model property is an important property that implies decidability. We show that the small model size is directly related to some important resources in games and automata for checking provability.
Nyx-Net: Network Fuzzing with Incremental Snapshots
Venue: arXiv cs.CR 2021
Year: 2021

Coverage-guided fuzz testing ("fuzzing") has become mainstream and we have observed lots of progress in this research area recently. However, it is still challenging to efficiently test network services with existing coverage-guided fuzzing methods. In this paper, we introduce the design and implementation of Nyx-Net, a novel snapshot-based fuzzing approach that can successfully fuzz a wide range of targets spanning servers, clients, games, and even Firefox's Inter-Process Communication (IPC) interface. Compared to state-of-the-art methods, Nyx-Net improves test throughput by up to 300x and coverage found by up to 70%. Additionally, Nyx-Net is able to find crashes in two of ProFuzzBench's targets that no other fuzzer found previously. When using Nyx-Net to play the game Super Mario, Nyx-Net shows speedups of 10-30x compared to existing work. Under some circumstances, Nyx-Net is even able play "faster than light": solving the level takes less wall-clock time than playing the level perfectly even once. Nyx-Net is able to find previously unknown bugs in servers such as Lighttpd, clients such as MySQL client, and even Firefox's IPC mechanism - demonstrating the strength and versatility of the proposed approach. Lastly, our prototype implementation was awarded a $20.000 bug bounty for enabling fuzzing on previously unfuzzable code in Firefox and solving a long-standing problem at Mozilla.
A System for General In-Hand Object Re-Orientation
Venue: arXiv cs.RO 2021
Year: 2021

In-hand object reorientation has been a challenging problem in robotics due to high dimensional actuation space and the frequent change in contact state between the fingers and the objects. We present a simple model-free framework that can learn to reorient objects with both the hand facing upwards and downwards. We demonstrate the capability of reorienting over 2000 geometrically different objects in both cases. The learned policies show strong zero-shot transfer performance on new objects. We provide evidence that these policies are amenable to real-world operation by distilling them to use observations easily available in the real world. The videos of the learned policies are available at: https://taochenshh.github.io/projects/in-hand-reorientation.
Generalization in Dexterous Manipulation via Geometry-Aware Multi-Task Learning
Venue: arXiv cs.RO 2021
Year: 2021

Dexterous manipulation of arbitrary objects, a fundamental daily task for humans, has been a grand challenge for autonomous robotic systems. Although data-driven approaches using reinforcement learning can develop specialist policies that discover behaviors to control a single object, they often exhibit poor generalization to unseen ones. In this work, we show that policies learned by existing reinforcement learning algorithms can in fact be generalist when combined with multi-task learning and a well-chosen object representation. We show that a single generalist policy can perform in-hand manipulation of over 100 geometrically-diverse real-world objects and generalize to new objects with unseen shape or size. Interestingly, we find that multi-task learning with object point cloud representations not only generalizes better but even outperforms the single-object specialist policies on both training as well as held-out test objects. Video results at https://huangwl18.github.io/geometry-dex