OpenRaiser/Intern-Atlas huggingface dataset:
Cross-View Cross-Scene Multi-View Crowd Counting
Venue: arXiv cs.CV 2022
Year: 2022

Multi-view crowd counting has been previously proposed to utilize multi-cameras to extend the field-of-view of a single camera, capturing more people in the scene, and improve counting performance for occluded people or those in low resolution. However, the current multi-view paradigm trains and tests on the same single scene and camera-views, which limits its practical application. In this paper, we propose a cross-view cross-scene (CVCS) multi-view crowd counting paradigm, where the training and testing occur on different scenes with arbitrary camera layouts. To dynamically handle the challenge of optimal view fusion under scene and camera layout change and non-correspondence noise due to camera calibration errors or erroneous features, we propose a CVCS model that attentively selects and fuses multiple views together using camera layout geometry, and a noise view regularization method to train the model to handle non-correspondence errors. We also generate a large synthetic multi-camera crowd counting dataset with a large number of scenes and camera views to capture many possible variations, which avoids the difficulty of collecting and annotating such a large real dataset. We then test our trained CVCS model on real multi-view counting datasets, by using unsupervised domain transfer. The proposed CVCS model trained on synthetic data outperforms the same model trained only on real data, and achieves promising performance compared to fully supervised methods that train and test on the same single scene.
Computing Maximal Unique Matches with the r-index
Venue: arXiv cs.DS 2022
Year: 2022

In recent years, pangenomes received increasing attention from the scientific community for their ability to incorporate population variation information and alleviate reference genome bias. Maximal Exact Matches (MEMs) and Maximal Unique Matches (MUMs) have proven themselves to be useful in multiple bioinformatic contexts, for example short-read alignment and multiple-genome alignment. However, standard techniques using suffix trees and FM-indexes do not scale to a pangenomic level. Recently, Gagie et al. [JACM 20] introduced the $r$-index that is a Burrows-Wheeler Transform (BWT)-based index able to handle hundreds of human genomes. Later, Rossi et al. [JCB 22] enabled the computation of MEMs using the $r$-index, and Boucher et al. [DCC 21] showed how to compute them in a streaming fashion. In this paper, we show how to augment Boucher et al.'s approach to enable the computation of MUMs on the $r$-index, while preserving the space and time bounds. We add additional $O(r)$ samples of the longest common prefix (LCP) array, where $r$ is the number of equal-letter runs of the BWT, that permits the computation of the second longest match of the pattern suffix with respect to the input text, which in turn allows the computation of candidate MUMs. We implemented a proof-of-concept of our approach, that we call mum-phinder, and tested on real-world datasets. We compared our approach with competing methods that are able to compute MUMs. We observe that our method is up to 8 times smaller, while up to 19 times slower when the dataset is not highly repetitive, while on highly repetitive data, our method is up to 6.5 times slower and uses up to 25 times less memory.
Simpler is Better: off-the-shelf Continual Learning Through Pretrained Backbones
Venue: arXiv cs.CV 2022
Year: 2022

In this short paper, we propose a baseline (off-the-shelf) for Continual Learning of Computer Vision problems, by leveraging the power of pretrained models. By doing so, we devise a simple approach achieving strong performance for most of the common benchmarks. Our approach is fast since requires no parameters updates and has minimal memory requirements (order of KBytes). In particular, the "training" phase reorders data and exploit the power of pretrained models to compute a class prototype and fill a memory bank. At inference time we match the closest prototype through a knn-like approach, providing us the prediction. We will see how this naive solution can act as an off-the-shelf continual learning system. In order to better consolidate our results, we compare the devised pipeline with common CNN models and show the superiority of Vision Transformers, suggesting that such architectures have the ability to produce features of higher quality. Moreover, this simple pipeline, raises the same questions raised by previous works \cite{gdumb} on the effective progresses made by the CL community especially in the dataset considered and the usage of pretrained models. Code is live at https://github.com/francesco-p/off-the-shelf-cl
A New Approach to Compute Information Theoretic Outer Bounds and Its Application to Regenerating Codes
Venue: arXiv cs.IT 2022
Year: 2022

The study of the fundamental limits of information systems is a central theme in information theory. Both the traditional analytical approach and the recently proposed computational approach have significant limitations, where the former is mainly due to its reliance on human ingenuity, and the latter due to its exponential memory and computational complexity. In this work, we propose a new computational approach to tackle the problem with much lower memory and computational requirements, which can naturally utilize certain intuitions, but also can maintain the strong computational advantage of the existing computational approach. A reformulation of the underlying optimization problem is first proposed, which converts the large linear program to a maximin problem. This leads to an iterative solving procedure, which uses the LP dual to carry over learned evidence between iterations. The key in the reformulated problem is the selection of good information inequalities, with which a relaxed LP can be formed. A particularly powerful intuition is a potentially optimal code construction, and we provide a method that directly utilizes it in the new algorithm. As an application, we derive a tighter outer bound for the storage-repair tradeoff for the $(6,5,5)$ regenerating code problem, which involves at least 30 random variables and is impossible to compute with the previously known computational approach.
Towards URLLC with Proactive HARQ Adaptation
Venue: arXiv cs.NI 2022
Year: 2022

In this work, we propose a dynamic decision maker algorithm to improve the proactive HARQ protocol for beyond 5G networks. Based on Lyapunov stochastic optimization, our adaptation control framework dynamically selects the number of proactive retransmissions for intermittent URLLC traffic scenarios under time-varying channel conditions without requiring any prior knowledge associated with this stochastic process. It then better exploits the trade-off between Radio Access Network (RAN) latency, reliability and resource efficiency, which is still limited in its realization on current HARQ designs. We then evaluate the performance of several HARQ strategies and show that our proposal further improves latency over the reactive regime without affecting the resource efficiency such as fixed proactive retransmission while maintaining target reliability.
Deep Sequence Modeling for Anomalous ISP Traffic Prediction
Venue: arXiv cs.LG 2022
Year: 2022

Internet traffic in the real world is susceptible to various external and internal factors which may abruptly change the normal traffic flow. Those unexpected changes are considered outliers in traffic. However, deep sequence models have been used to predict complex IP traffic, but their comparative performance for anomalous traffic has not been studied extensively. In this paper, we investigated and evaluated the performance of different deep sequence models for anomalous traffic prediction. Several deep sequences models were implemented to predict real traffic without and with outliers and show the significance of outlier detection in real-world traffic prediction. First, two different outlier detection techniques, such as the Three-Sigma rule and Isolation Forest, were applied to identify the anomaly. Second, we adjusted those abnormal data points using the Backward Filling technique before training the model. Finally, the performance of different models was compared for abnormal and adjusted traffic. LSTM_Encoder_Decoder (LSTM_En_De) is the best prediction model in our experiment, reducing the deviation between actual and predicted traffic by more than 11\% after adjusting the outliers. All other models, including Recurrent Neural Network (RNN), Long Short-Term Memory (LSTM), LSTM_En_De with Attention layer (LSTM_En_De_Atn), Gated Recurrent Unit (GRU), show better prediction after replacing the outliers and decreasing prediction error by more than 29%, 24%, 19%, and 10% respectively. Our experimental results indicate that the outliers in the data can significantly impact the quality of the prediction. Thus, outlier detection and mitigation assist the deep sequence model in learning the general trend and making better predictions.
Smart City Intersections: Intelligence Nodes for Future Metropolises
Venue: arXiv cs.CV 2022
Year: 2022

Traffic intersections are the most suitable locations for the deployment of computing, communications, and intelligence services for smart cities of the future. The abundance of data to be collected and processed, in combination with privacy and security concerns, motivates the use of the edge-computing paradigm which aligns well with physical intersections in metropolises. This paper focuses on high-bandwidth, low-latency applications, and in that context it describes: (i) system design considerations for smart city intersection intelligence nodes; (ii) key technological components including sensors, networking, edge computing, low latency design, and AI-based intelligence; and (iii) applications such as privacy preservation, cloud-connected vehicles, a real-time "radar-screen", traffic management, and monitoring of pedestrian behavior during pandemics. The results of the experimental studies performed on the COSMOS testbed located in New York City are illustrated. Future challenges in designing human-centered smart city intersections are summarized.
Experiments with Unit Disk Cover Algorithms for Covering Massive Pointsets
Venue: arXiv cs.CG 2022
Year: 2022

Given a set of $n$ points in the plane, the Unit Disk Cover (UDC) problem asks to compute the minimum number of unit disks required to cover the points, along with a placement of the disks. The problem is NP-hard and several approximation algorithms have been designed over the last three decades. In this paper, we have engineered and experimentally compared practical performances of some of these algorithms on massive pointsets. The goal is to investigate which algorithms run fast and give good approximation in practice. We present a simple $7$-approximation algorithm for UDC that runs in $O(n)$ expected time and uses $O(s)$ extra space, where $s$ denotes the size of the generated cover. In our experiments, it turned out to be the speediest of all. We also present two heuristics to reduce the sizes of covers generated by it without slowing it down by much. To our knowledge, this is the first work that experimentally compares geometric covering algorithms. Experiments with them using massive pointsets (in the order of millions) throw light on their practical uses. We share the engineered algorithms via GitHub - https://github.com/ghoshanirban/UnitDiskCoverAlgorithms for broader uses and future research in the domain of geometric optimization.
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
Venue: arXiv cs.DS 2022
Year: 2022

The \emph{$ p$-processor cup game} is a classic and widely studied scheduling problem that captures the setting in which a $p$-processor machine must assign tasks to processors over time in order to ensure that no individual task ever falls too far behind. The problem is formalized as a multi-round game in which two players, a filler (who assigns work to tasks) and an emptier (who schedules tasks) compete. The emptier's goal is to minimize backlog, which is the maximum amount of outstanding work for any task. Recently, Kuszmaul and Westover (ITCS, 2021) proposed the \emph{variable-processor cup game}, which considers the same problem, except that the amount of resources available to the players (i.e., the number $p$ of processors) fluctuates between rounds of the game. They showed that this seemingly small modification fundamentally changes the dynamics of the game: whereas the optimal backlog in the fixed $p$-processor game is $Θ(\log n)$, independent of $p$, the optimal backlog in the variable-processor game is $Θ(n)$. The latter result was only known to apply to games with \emph{exponentially many} rounds, however, and it has remained an open question what the optimal tradeoff between time and backlog is for shorter games. This paper establishes a tight trade-off curve between time and backlog in the variable-processor cup game. Importantly, we prove that for a game consisting of $t$ rounds, the optimal backlog is $Θ(n)$ if and only if $t \ge Ω(n^3)$. Our techniques also allow for us to resolve several other open questions concerning how the variable-processor cup game behaves in beyond-worst-case-analysis settings.
A Secure File Sharing System Based on IPFS and Blockchain
Venue: arXiv cs.CR 2022
Year: 2022

There is a great interest in many approaches towards blockchain in providing a solution to record transactions in a decentralized way. However, there are some limitations when storing large files or documents on the blockchain. In order to meet the requirements of storing relatively large data, a decentralized storage medium is produced. IPFS is a distributed file system which is content-addressable. It works very similar to the blockchain network. There are some attempts which take advantage of the blockchain concept and IPFS to design new approaches. Unfortunately, there are some inefficiencies in sharing data using the combination of IPFS and blockchain. In this paper, we proposed a secure file sharing system that brings a distributed access control and group key management by the adoption of the IPFS proxy. The IPFS proxy which plays an important role in the design is adopted to take responsibility for the control policies. The combination of the IPFS server and the blockchain network with the adoption of the IPFS proxy make a secure file sharing system which the members on the system can create new groups or join different groups by their own choice. Although there is no access control mechanism in IPFS server and blockchain network, the secure file sharing system manages the access control policies. The members access files only belong to the group they authorized.
Differentiable Simulation of Soft Multi-body Systems
Venue: arXiv cs.LG 2022
Year: 2022

We present a method for differentiable simulation of soft articulated bodies. Our work enables the integration of differentiable physical dynamics into gradient-based pipelines. We develop a top-down matrix assembly algorithm within Projective Dynamics and derive a generalized dry friction model for soft continuum using a new matrix splitting strategy. We derive a differentiable control framework for soft articulated bodies driven by muscles, joint torques, or pneumatic tubes. The experiments demonstrate that our designs make soft body simulation more stable and realistic compared to other frameworks. Our method accelerates the solution of system identification problems by more than an order of magnitude, and enables efficient gradient-based learning of motion control with soft robots.
Explain and Conquer: Personalised Text-based Reviews to Achieve Transparency
Venue: arXiv cs.LG 2022
Year: 2022

There are many contexts in which dyadic data are present. Social networks are a well-known example. In these contexts, pairs of elements are linked building a network that reflects interactions. Explaining why these relationships are established is essential to obtain transparency, an increasingly important notion. These explanations are often presented using text, thanks to the spread of the natural language understanding tasks. Our aim is to represent and explain pairs established by any agent (e.g., a recommender system or a paid promotion mechanism), so that text-based personalisation is taken into account. We have focused on the TripAdvisor platform, considering the applicability to other dyadic data contexts. The items are a subset of users and restaurants and the interactions the reviews posted by these users. We propose the PTER (Personalised TExt-based Reviews) model. We predict, from the available reviews for a given restaurant, those that fit to the specific user interactions. PTER leverages the BERT (Bidirectional Encoders Representations from Transformers) transformer-encoder model. We customised a deep neural network following the feature-based approach, presenting a LTR (Learning To Rank) downstream task. We carried out several comparisons of our proposal with a random baseline and other models of the state of the art, following the EXTRA (EXplanaTion RAnking) benchmark. Our method outperforms other collaborative filtering proposals.
DEAR: A Novel Deep Learning-based Approach for Automated Program Repair
Venue: arXiv cs.SE 2022
Year: 2022

The existing deep learning (DL)-based automated program repair (APR) models are limited in fixing general software defects. % We present {\tool}, a DL-based approach that supports fixing for the general bugs that require dependent changes at once to one or multiple consecutive statements in one or multiple hunks of code. % We first design a novel fault localization (FL) technique for multi-hunk, multi-statement fixes that combines traditional spectrum-based (SB) FL with deep learning and data-flow analysis. It takes the buggy statements returned by the SBFL model, detects the buggy hunks to be fixed at once, and expands a buggy statement $s$ in a hunk to include other suspicious statements around $s$. We design a two-tier, tree-based LSTM model that incorporates cycle training and uses a divide-and-conquer strategy to learn proper code transformations for fixing multiple statements in the suitable fixing context consisting of surrounding subtrees. We conducted several experiments to evaluate {\tool} on three datasets: Defects4J (395 bugs), BigFix (+26k bugs), and CPatMiner (+44k bugs). On Defects4J dataset, {\tool} outperforms the baselines from 42\%--683\% in terms of the number of auto-fixed bugs with only the top-1 patches. On BigFix dataset, it fixes 31--145 more bugs than existing DL-based APR models with the top-1 patches. On CPatMiner dataset, among 667 fixed bugs, there are 169 (25.3\%) multi-hunk/multi-statement bugs. {\tool} fixes 71 and 164 more bugs, including 52 and 61 more multi-hunk/multi-statement bugs, than the state-of-the-art, DL-based APR models.
P^3 Ranker: Mitigating the Gaps between Pre-training and Ranking Fine-tuning with Prompt-based Learning and Pre-finetuning
Venue: arXiv cs.IR 2022
Year: 2022

Compared to other language tasks, applying pre-trained language models (PLMs) for search ranking often requires more nuances and training signals. In this paper, we identify and study the two mismatches between pre-training and ranking fine-tuning: the training schema gap regarding the differences in training objectives and model architectures, and the task knowledge gap considering the discrepancy between the knowledge needed in ranking and that learned during pre-training. To mitigate these gaps, we propose Pre-trained, Prompt-learned and Pre-finetuned Neural Ranker (P^3 Ranker). P^3 Ranker leverages prompt-based learning to convert the ranking task into a pre-training like schema and uses pre-finetuning to initialize the model on intermediate supervised tasks. Experiments on MS MARCO and Robust04 show the superior performances of P^3 Ranker in few-shot ranking. Analyses reveal that P^3 Ranker is able to better accustom to the ranking task through prompt-based learning and retrieve necessary ranking-oriented knowledge gleaned in pre-finetuning, resulting in data-efficient PLM adaptation. Our code is available at https://github.com/NEUIR/P3Ranker.
Pik-Fix: Restoring and Colorizing Old Photos
Venue: arXiv cs.CV 2022
Year: 2022

Restoring and inpainting the visual memories that are present, but often impaired, in old photos remains an intriguing but unsolved research topic. Decades-old photos often suffer from severe and commingled degradation such as cracks, defocus, and color-fading, which are difficult to treat individually and harder to repair when they interact. Deep learning presents a plausible avenue, but the lack of large-scale datasets of old photos makes addressing this restoration task very challenging. Here we present a novel reference-based end-to-end learning framework that is able to both repair and colorize old, degraded pictures. Our proposed framework consists of three modules: a restoration sub-network that conducts restoration from degradations, a similarity network that performs color histogram matching and color transfer, and a colorization subnet that learns to predict the chroma elements of images conditioned on chromatic reference signals. The overall system makes uses of color histogram priors from reference images, which greatly reduces the need for large-scale training data. We have also created a first-of-a-kind public dataset of real old photos that are paired with ground truth ''pristine'' photos that have been manually restored by PhotoShop experts. We conducted extensive experiments on this dataset and synthetic datasets, and found that our method significantly outperforms previous state-of-the-art models using both qualitative comparisons and quantitative measurements. The code is available at https://github.com/DerrickXuNu/Pik-Fix.
ImAiR: Airwriting Recognition framework using Image Representation of IMU Signals
Venue: arXiv cs.HC 2022
Year: 2022

The problem of Airwriting Recognition is focused on identifying letters written by movement of finger in free space. It is a type of gesture recognition where the dictionary corresponds to letters in a specific language. In particular, airwriting recognition using sensor data from wrist-worn devices can be used as a medium of user input for applications in Human-Computer Interaction (HCI). Recognition of in-air trajectories using such wrist-worn devices is limited in literature and forms the basis of the current work. In this paper, we propose an airwriting recognition framework by first encoding the time-series data obtained from a wearable Inertial Measurement Unit (IMU) on the wrist as images and then utilizing deep learning-based models for identifying the written alphabets. The signals recorded from 3-axis accelerometer and gyroscope in IMU are encoded as images using different techniques such as Self Similarity Matrix (SSM), Gramian Angular Field (GAF) and Markov Transition Field (MTF) to form two sets of 3-channel images. These are then fed to two separate classification models and letter prediction is made based on an average of the class conditional probabilities obtained from the two models. Several standard model architectures for image classification such as variants of ResNet, DenseNet, VGGNet, AlexNet and GoogleNet have been utilized. Experiments performed on two publicly available datasets demonstrate the efficacy of the proposed strategy. The code for our implementation will be made available at https://github.com/ayushayt/ImAiR.