OpenRaiser/Intern-Atlas huggingface dataset:
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
Venue: arXiv cs.DS 2022
Year: 2022

We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: * Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n OPT, n W, OPT^2, W^2\})$, where $n$ is the number of items, $W$ is the weight budget, and $OPT$ is the optimal profit. We present an algorithm running in time $\widetilde{O}(n + (W + OPT)^{1.5})$. This improves the running time in case $n,W,OPT$ are roughly equal. * Exact Algorithm for Unbounded Knapsack: Unbounded Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n \cdot p_{\max}, n \cdot w_{\max}, p_{\max}^2, w_{\max}^2\})$ [Axiotis, Tzamos '19, Jansen, Rohwedder '19, Chan, He '20], where $n$ is the number of items, $w_{\max}$ is the largest weight of any item, and $p_{\max}$ is the largest profit of any item. We present an algorithm running in time $\widetilde{O}(n + (p_{\max} + w_{\max})^{1.5})$, giving a similar improvement as for 0-1-Knapsack. * Approximating Unbounded Knapsack with Resource Augmentation: Unbounded Knapsack has a known FPTAS with running time $\widetilde{O}(\min\{n/\varepsilon, n + 1/\varepsilon^2\})$ [Jansen, Kraft '18]. We study weak approximation algorithms, which approximate the optimal profit but are allowed to overshoot the weight constraint. We present the first approximation scheme for Unbounded Knapsack in this setting, achieving running time $\widetilde{O}(n + 1/\varepsilon^{1.5})$. Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone sequences with bounded entries. These structured instances of Min-Plus-Convolution can be solved in time $O(n^{1.5})$ [Chi,Duan,Xie,Zhang '22] (in contrast to the conjectured $n^{2-o(1)}$ lower bound for the general case).
A CLIP-Hitchhiker's Guide to Long Video Retrieval
Venue: arXiv cs.CV 2022
Year: 2022

Our goal in this paper is the adaptation of image-text models for long video retrieval. Recent works have demonstrated state-of-the-art performance in video retrieval by adopting CLIP, effectively hitchhiking on the image-text representation for video tasks. However, there has been limited success in learning temporal aggregation that outperform mean-pooling the image-level representations extracted per frame by CLIP. We find that the simple yet effective baseline of weighted-mean of frame embeddings via query-scoring is a significant improvement above all prior temporal modelling attempts and mean-pooling. In doing so, we provide an improved baseline for others to compare to and demonstrate state-of-the-art performance of this simple baseline on a suite of long video retrieval benchmarks.
Quantum Transfer Learning for Wi-Fi Sensing
Venue: arXiv cs.LG 2022
Year: 2022

Beyond data communications, commercial-off-the-shelf Wi-Fi devices can be used to monitor human activities, track device locomotion, and sense the ambient environment. In particular, spatial beam attributes that are inherently available in the 60-GHz IEEE 802.11ad/ay standards have shown to be effective in terms of overhead and channel measurement granularity for these indoor sensing tasks. In this paper, we investigate transfer learning to mitigate domain shift in human monitoring tasks when Wi-Fi settings and environments change over time. As a proof-of-concept study, we consider quantum neural networks (QNN) as well as classical deep neural networks (DNN) for the future quantum-ready society. The effectiveness of both DNN and QNN is validated by an in-house experiment for human pose recognition, achieving greater than 90% accuracy with a limited data size.
Deploying self-supervised learning in the wild for hybrid automatic speech recognition
Venue: arXiv cs.SD 2022
Year: 2022

Self-supervised learning (SSL) methods have proven to be very successful in automatic speech recognition (ASR). These great improvements have been reported mostly based on highly curated datasets such as LibriSpeech for non-streaming End-to-End ASR models. However, the pivotal characteristics of SSL is to be utilized for any untranscribed audio data. In this paper, we provide a full exploration on how to utilize uncurated audio data in SSL from data pre-processing to deploying an streaming hybrid ASR model. More specifically, we present (1) the effect of Audio Event Detection (AED) model in data pre-processing pipeline (2) analysis on choosing optimizer and learning rate scheduling (3) comparison of recently developed contrastive losses, (4) comparison of various pre-training strategies such as utilization of in-domain versus out-domain pre-training data, monolingual versus multilingual pre-training data, multi-head multilingual SSL versus single-head multilingual SSL and supervised pre-training versus SSL. The experimental results show that SSL pre-training with in-domain uncurated data can achieve better performance in comparison to all the alternative out-domain pre-training strategies.
A General Measure of Collision Hazard in Traffic
Venue: arXiv cs.RO 2022
Year: 2022

A collision hazard measure that has the essential characteristics to provide a measurement of safety that will be useful to AV developers, traffic infrastructure developers and managers, regulators and the public is introduced here. The Streetscope Collision Hazard Measure (SHM) overcomes the limitations of existing measures, and provides an independent leading indication of safety. * Trailing indicators, such as collision statistics, incur pain and loss on society, and are not an ethically acceptable approach. * Near-misses have been shown to be effective predictors of incidents. * Time-to-Collision (TTC) provides ambiguous indication of collision hazards, and requires assumptions about vehicle behavior. * Responsibility-Sensitive Safety (RSS), because of its reliance on rules for individual circumstances, will not scale up to handle the complexities of traffic. * Instantaneous Safety Metric (ISM) relies on probabilistic predictions of behaviors to categorize events (possible, imminent, critical), and does not provide a quantitative measure of the severity of the hazard. * Inertial Measurement Unit (IMU) acceleration data is not correlated with hazard or risk. * A new measure, based on the concept of near-misses, that incorporates both proximity (separation distance) and motion (relative speed) is introduced. * Near-miss data has been shown to be predictive of the likelihood and severity of incidents. The new measure presented here gathers movement data about vehicles continuously and a quantitative score reflecting the hazard encountered or created (from which the riskiness or safeness of the behavior of vehicles can be estimated) is computed nearly continuously.
The Energy Complexity of Las Vegas Leader Election
Venue: arXiv cs.DS 2022
Year: 2022

We consider the time and energy complexities of randomized leader election in a multiple-access channel, where the number of devices $n\geq 2$ is unknown. It is well-known that for polynomial-time randomized leader election algorithms with success probability $1-1/poly(n)$, the optimal energy complexity is $Θ(\log\log^*n)$ if receivers can detect collisions, and $Θ(\log^*n)$ otherwise. Without collision detection, all existing randomized leader election algorithms using $o(\log\log n)$ energy are Monte Carlo in that they may fail with some small probability, and they may consume unbounded energy and never halt when they fail. Though the optimal energy complexity of leader election appears to be settled, it is still an open question to attain the optimal $O(\log^*n)$ energy complexity by an efficient Las Vegas algorithm that never fails. In this paper we address this fundamental question. $\textbf{Separation between Monte Carlo and Las Vegas:}$ Without collision detection, we prove that any Las Vegas leader election algorithm with finite expected time complexity must use $Ω(\log\log n)$ energy, establishing a large separation between Monte Carlo and Las Vegas algorithms. $\textbf{Exponential improvement with sender collision detection:}$ In the setting where senders can detect collisions, we design a new leader election algorithm that finishes in $O(\log^{1+ε}n)$ time and uses $O(ε^{-1}\log\log\log n)$ energy in expectation, showing that sender collision detection helps improve the energy complexity exponentially. $\textbf{Optimal deterministic leader election algorithm:}$ As a side result, via derandomization, we show a new deterministic algorithm that takes $O(n\log(N/n))$ time and $O(\log(N/n))$ energy to elect a leader from $n$ devices, where each device has a unique identifier in $[N]$. This algorithm is time-optimal and energy-optimal.
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
Venue: arXiv cs.DS 2022
Year: 2022

Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph $G=(I,J,E)$ between individuals $I$ and jobs $J$. The platform has a value of $v_j$ for matching job $j$ to an individual worker. In order to find a matching, the platform can consider the edges $(i j) \in E$ in any order and make a one-time take-it-or-leave-it offer of a price $π_{ij} = w$ of its choosing to $i$ for completing $j$. The worker accepts the offer with a known probability $ p_{ijw} $; in this case the job and the worker are irrevocably matched. What is the best way to make offers to maximize revenue and/or social welfare? The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new Random-Order Online Contention Resolution Scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of $\frac{1}{2}(1-e^{-2})\approx 0.432$ of [BGMS21], and improve on the best known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. As a consequence of our OCRS results, we obtain a $0.456$-approximate algorithm for the sequential pricing problem. We further extend our results to settings where workers can only be contacted a limited number of times, and show how to achieve improved results for this problem, via improved algorithms for the well-studied stochastic probing problem.
Learning Monocular Depth Estimation via Selective Distillation of Stereo Knowledge
Venue: arXiv cs.CV 2022
Year: 2022

Monocular depth estimation has been extensively explored based on deep learning, yet its accuracy and generalization ability still lag far behind the stereo-based methods. To tackle this, a few recent studies have proposed to supervise the monocular depth estimation network by distilling disparity maps as proxy ground-truths. However, these studies naively distill the stereo knowledge without considering the comparative advantages of stereo-based and monocular depth estimation methods. In this paper, we propose to selectively distill the disparity maps for more reliable proxy supervision. Specifically, we first design a decoder (MaskDecoder) that learns two binary masks which are trained to choose optimally between the proxy disparity maps and the estimated depth maps for each pixel. The learned masks are then fed to another decoder (DepthDecoder) to enforce the estimated depths to learn from only the masked area in the proxy disparity maps. Additionally, a Teacher-Student module is designed to transfer the geometric knowledge of the StereoNet to the MonoNet. Extensive experiments validate our methods achieve state-of-the-art performance for self- and proxy-supervised monocular depth estimation on the KITTI dataset, even surpassing some of the semi-supervised methods.
Addressing Resource and Privacy Constraints in Semantic Parsing Through Data Augmentation
Venue: arXiv cs.CL 2022
Year: 2022

We introduce a novel setup for low-resource task-oriented semantic parsing which incorporates several constraints that may arise in real-world scenarios: (1) lack of similar datasets/models from a related domain, (2) inability to sample useful logical forms directly from a grammar, and (3) privacy requirements for unlabeled natural utterances. Our goal is to improve a low-resource semantic parser using utterances collected through user interactions. In this highly challenging but realistic setting, we investigate data augmentation approaches involving generating a set of structured canonical utterances corresponding to logical forms, before simulating corresponding natural language and filtering the resulting pairs. We find that such approaches are effective despite our restrictive setup: in a low-resource setting on the complex SMCalFlow calendaring dataset (Andreas et al., 2020), we observe 33% relative improvement over a non-data-augmented baseline in top-1 match.
Terrain Analysis in StarCraft 1 and 2 as Combinatorial Optimization
Venue: arXiv cs.AI 2022
Year: 2022

Terrain analysis in Real-Time Strategy games is a necessary step to allow spacial reasoning. The goal of terrain analysis is to gather and process data about the map topology and properties to have a qualitative spatial representation. On StarCraft games, all previous works on terrain analysis propose a crisp analysis based on connected component detection, Voronoi diagram computation and pruning, and region merging. Those methods have been implemented as game-specific libraries, and they can only offer the same kind of analysis for all maps and all users. In this paper, we propose a way to consider terrain analysis as a combinatorial optimization problem. Our method allows different kinds of analysis by changing constraints or the objective function in the problem model. We also present a library, Taunt, implementing our method and able to handle both StarCraft 1 and StarCraft 2 maps. This makes our library a universal tool for StarCraft bots with different spatial representation needs. We believe our library unlocks the possibility to have real adaptive AIs playing StarCraft, and can be the starting point of a new wave of bots.
Policy Distillation with Selective Input Gradient Regularization for Efficient Interpretability
Venue: arXiv cs.LG 2022
Year: 2022

Although deep Reinforcement Learning (RL) has proven successful in a wide range of tasks, one challenge it faces is interpretability when applied to real-world problems. Saliency maps are frequently used to provide interpretability for deep neural networks. However, in the RL domain, existing saliency map approaches are either computationally expensive and thus cannot satisfy the real-time requirement of real-world scenarios or cannot produce interpretable saliency maps for RL policies. In this work, we propose an approach of Distillation with selective Input Gradient Regularization (DIGR) which uses policy distillation and input gradient regularization to produce new policies that achieve both high interpretability and computation efficiency in generating saliency maps. Our approach is also found to improve the robustness of RL policies to multiple adversarial attacks. We conduct experiments on three tasks, MiniGrid (Fetch Object), Atari (Breakout) and CARLA Autonomous Driving, to demonstrate the importance and effectiveness of our approach.
Extrinsic Calibration of LiDAR, IMU and Camera
Venue: arXiv cs.RO 2022
Year: 2022

In this work we present a novel method to jointly calibrate a sensor suite consisting a 3D-LiDAR, Inertial Measurement Unit (IMU) and Camera under an Extended Kalman Filter (EKF) framework. We exploit pairwise constraints between the 3 sensor pairs to perform EKF update and experimentally demonstrate the superior performance obtained with joint calibration as against individual sensor pair calibration.
A Regression Approach to Learning-Augmented Online Algorithms
Venue: arXiv cs.LG 2022
Year: 2022

The emerging field of learning-augmented online algorithms uses ML techniques to predict future input parameters and thereby improve the performance of online algorithms. Since these parameters are, in general, real-valued functions, a natural approach is to use regression techniques to make these predictions. We introduce this approach in this paper, and explore it in the context of a general online search framework that captures classic problems like (generalized) ski rental, bin packing, minimum makespan scheduling, etc. We show nearly tight bounds on the sample complexity of this regression problem, and extend our results to the agnostic setting. From a technical standpoint, we show that the key is to incorporate online optimization benchmarks in the design of the loss function for the regression problem, thereby diverging from the use of off-the-shelf regression tools with standard bounds on statistical error.
Data Augmentation to Address Out-of-Vocabulary Problem in Low-Resource Sinhala-English Neural Machine Translation
Venue: arXiv cs.CL 2022
Year: 2022

Out-of-Vocabulary (OOV) is a problem for Neural Machine Translation (NMT). OOV refers to words with a low occurrence in the training data, or to those that are absent from the training data. To alleviate this, word or phrase-based Data Augmentation (DA) techniques have been used. However, existing DA techniques have addressed only one of these OOV types and limit to considering either syntactic constraints or semantic constraints. We present a word and phrase replacement-based DA technique that consider both types of OOV, by augmenting (1) rare words in the existing parallel corpus, and (2) new words from a bilingual dictionary. During augmentation, we consider both syntactic and semantic properties of the words to guarantee fluency in the synthetic sentences. This technique was experimented with low resource Sinhala-English language pair. We observe with only semantic constraints in the DA, the results are comparable with the scores obtained considering syntactic constraints, and is favourable for low-resourced languages that lacks linguistic tool support. Additionally, results can be further improved by considering both syntactic and semantic constraints.
TTAPS: Test-Time Adaption by Aligning Prototypes using Self-Supervision
Venue: arXiv cs.LG 2022
Year: 2022

Nowadays, deep neural networks outperform humans in many tasks. However, if the input distribution drifts away from the one used in training, their performance drops significantly. Recently published research has shown that adapting the model parameters to the test sample can mitigate this performance degradation. In this paper, we therefore propose a novel modification of the self-supervised training algorithm SwAV that adds the ability to adapt to single test samples. Using the provided prototypes of SwAV and our derived test-time loss, we align the representation of unseen test samples with the self-supervised learned prototypes. We show the success of our method on the common benchmark dataset CIFAR10-C.
A reproducible experimental survey on biomedical sentence similarity: a string-based method sets the state of the art
Venue: arXiv cs.CL 2022
Year: 2022

This registered report introduces the largest, and for the first time, reproducible experimental survey on biomedical sentence similarity with the following aims: (1) to elucidate the state of the art of the problem; (2) to solve some reproducibility problems preventing the evaluation of most of current methods; (3) to evaluate several unexplored sentence similarity methods; (4) to evaluate an unexplored benchmark, called Corpus-Transcriptional-Regulation; (5) to carry out a study on the impact of the pre-processing stages and Named Entity Recognition (NER) tools on the performance of the sentence similarity methods; and finally, (6) to bridge the lack of reproducibility resources for methods and experiments in this line of research. Our experimental survey is based on a single software platform that is provided with a detailed reproducibility protocol and dataset as supplementary material to allow the exact replication of all our experiments. In addition, we introduce a new aggregated string-based sentence similarity method, called LiBlock, together with eight variants of current ontology-based methods and a new pre-trained word embedding model trained on the full-text articles in the PMC-BioC corpus. Our experiments show that our novel string-based measure sets the new state of the art on the sentence similarity task in the biomedical domain and significantly outperforms all the methods evaluated herein, except one ontology-based method. Likewise, our experiments confirm that the pre-processing stages, and the choice of the NER tool, have a significant impact on the performance of the sentence similarity methods. We also detail some drawbacks and limitations of current methods, and warn on the need of refining the current benchmarks. Finally, a noticeable finding is that our new string-based method significantly outperforms all state-of-the-art Machine Learning models evaluated herein.
Leapfrog: Certified Equivalence for Protocol Parsers
Venue: arXiv cs.PL 2022
Year: 2022

We present Leapfrog, a Coq-based framework for verifying equivalence of network protocol parsers. Our approach is based on an automata model of P4 parsers, and an algorithm for symbolically computing a compact representation of a bisimulation, using "leaps." Proofs are powered by a certified compilation chain from first-order entailments to low-level bitvector verification conditions, which are discharged using off-the-shelf SMT solvers. As a result, parser equivalence proofs in Leapfrog are fully automatic and push-button. We mechanically prove the core metatheory that underpins our approach, including the key transformations and several optimizations. We evaluate Leapfrog on a range of practical case studies, all of which require minimal configuration and no manual proof. Our largest case study uses Leapfrog to perform translation validation for a third-party compiler from automata to hardware pipelines. Overall, Leapfrog represents a step towards a world where all parsers for critical network infrastructure are verified. It also suggests directions for follow-on efforts, such as verifying relational properties involving security.
Global Type Inference for Featherweight Generic Java
Venue: arXiv cs.PL 2022
Year: 2022

Java's type system mostly relies on type checking augmented with local type inference to improve programmer convenience. We study global type inference for Featherweight Generic Java (FGJ), a functional Java core language. Given generic class headers and field specifications, our inference algorithm infers all method types if classes do not make use of polymorphic recursion. The algorithm is constraint-based and improves on prior work in several respects. Despite the restricted setting, global type inference for FGJ is NP-complete.
Anomaly detection using prediction error with Spatio-Temporal Convolutional LSTM
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we propose a novel method for video anomaly detection motivated by an existing architecture for sequence-to-sequence prediction and reconstruction using a spatio-temporal convolutional Long Short-Term Memory (convLSTM). As in previous work on anomaly detection, anomalies arise as spatially localised failures in reconstruction or prediction. In experiments with five benchmark datasets, we show that using prediction gives superior performance to using reconstruction. We also compare performance with different length input/output sequences. Overall, our results using prediction are comparable with the state of the art on the benchmark datasets.