OpenRaiser/Intern-Atlas huggingface dataset:
Image scaling by de la Vallée-Poussin filtered interpolation
Venue: arXiv cs.CV 2022
Year: 2022

We present a new image scaling method both for downscaling and upscaling, running with any scale factor or desired size. The resized image is achieved by sampling a bivariate polynomial which globally interpolates the data at the new scale. The method's particularities lay in both the sampling model and the interpolation polynomial we use. Rather than classical uniform grids, we consider an unusual sampling system based on Chebyshev zeros of the first kind. Such optimal distribution of nodes permits to consider near--best interpolation polynomials defined by a filter of de la Vallée Poussin type. The action ray of this filter provides an additional parameter that can be suitably regulated to improve the approximation. The method has been tested on a significant number of different image datasets. The results are evaluated in qualitative and quantitative terms and compared with other available competitive methods. The perceived quality of the resulting scaled images is such that important details are preserved, and the appearance of artifacts is low. Competitive quality measurement values, good visual quality, limited computational effort, and moderate memory demand make the method suitable for real-world applications.
Learning Perceptual Locomotion on Uneven Terrains using Sparse Visual Observations
Venue: arXiv cs.RO 2022
Year: 2022

To proactively navigate and traverse various terrains, active use of visual perception becomes indispensable. We aim to investigate the feasibility and performance of using sparse visual observations to achieve perceptual locomotion over a range of common terrains (steps, ramps, gaps, and stairs) in human-centered environments. We formulate a selection of sparse visual inputs suitable for locomotion over the terrains of interest, and propose a learning framework to integrate exteroceptive and proprioceptive states. We specifically design the state observations and a training curriculum to learn feedback control policies effectively over a range of different terrains. We extensively validate and benchmark the learned policy in various tasks: omnidirectional walking on flat ground, and forward locomotion over various obstacles, showing high success rate of traversability. Furthermore, we study exteroceptive ablations and evaluate policy generalization by adding various levels of noise and testing on new unseen terrains. We demonstrate the capabilities of autonomous perceptual locomotion that can be achieved by only using sparse visual observations from direct depth measurements, which are easily available from a Lidar or RGB-D sensor, showing robust ascent and descent over high stairs of 20 cm height, i.e., 50% leg length, and robustness against noise and unseen terrains.
On the Provable Generalization of Recurrent Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Recurrent Neural Network (RNN) is a fundamental structure in deep learning. Recently, some works study the training process of over-parameterized neural networks, and show that over-parameterized networks can learn functions in some notable concept classes with a provable generalization error bound. In this paper, we analyze the training and generalization for RNNs with random initialization, and provide the following improvements over recent works: 1) For a RNN with input sequence $x=(X_1,X_2,...,X_L)$, previous works study to learn functions that are summation of $f(β^T_lX_l)$ and require normalized conditions that $||X_l||\leqε$ with some very small $ε$ depending on the complexity of $f$. In this paper, using detailed analysis about the neural tangent kernel matrix, we prove a generalization error bound to learn such functions without normalized conditions and show that some notable concept classes are learnable with the numbers of iterations and samples scaling almost-polynomially in the input length $L$. 2) Moreover, we prove a novel result to learn N-variables functions of input sequence with the form $f(β^T[X_{l_1},...,X_{l_N}])$, which do not belong to the "additive" concept class, i,e., the summation of function $f(X_l)$. And we show that when either $N$ or $l_0=\max(l_1,..,l_N)-\min(l_1,..,l_N)$ is small, $f(β^T[X_{l_1},...,X_{l_N}])$ will be learnable with the number iterations and samples scaling almost-polynomially in the input length $L$.
Adaptive-Resolution Field Mapping Using Gaussian Process Fusion with Integral Kernels
Venue: arXiv cs.RO 2022
Year: 2022

Unmanned aerial vehicles are rapidly gaining popularity in a variety of environmental monitoring tasks. A key requirement for their autonomous operation is the ability to perform efficient environmental mapping online, given limited onboard resources constraining operation time, travel distance, and computational capacity. To address this, we present an online adaptive-resolution approach for mapping terrain based on Gaussian Process fusion. A key aspect of our approach is an integral kernel encoding spatial correlation over the areas of grid cells, which enables modifying map resolution while maintaining correlations in a theoretically sound fashion. This way, we can retain details in areas of interest at higher map resolutions while compressing information in uninteresting areas at coarser resolutions to achieve a compact map representation of the environment. We evaluate the performance of our approach on both synthetic and real-world data. Results show that our method is more efficient in terms of mapping time and memory consumption without compromising on map quality. Finally, we integrate our mapping strategy into an adaptive path planning framework to show that it facilitates information gathering efficiency in online settings.
Relational Memory: Native In-Memory Accesses on Rows and Columns
Venue: arXiv cs.DB 2022
Year: 2022

Analytical database systems are typically designed to use a column-first data layout to access only the desired fields. On the other hand, storing data row-first works great for accessing, inserting, or updating entire rows. Transforming rows to columns at runtime is expensive, hence, many analytical systems ingest data in row-first form and transform it in the background to columns to facilitate future analytical queries. How will this design change if we can always efficiently access only the desired set of columns? To address this question, we present a radically new approach to data transformation from rows to columns. We build upon recent advancements in embedded platforms with re-programmable logic to design native in-memory access on rows and columns. Our approach, termed Relational Memory, relies on an FPGA- based accelerator that sits between the CPU and main memory and transparently transforms base data to any group of columns with minimal overhead at runtime. This design allows accessing any group of columns as if it already exists in memory. We implement and deploy Relational Memory in real hardware, and we show that we can access the desired columns up to 1.63x faster than accessing them from their row-wise counterpart, while matching the performance of a pure columnar access for low projectivity, and outperforming it by up to 1.87x as projectivity (and tuple re-construction cost) increases. Moreover, our approach can be easily extended to support offloading of a number of operations to hardware, e.g., selection, group by, aggregation, and joins, having the potential to vastly simplify the software logic and accelerate the query execution.
Ruler Wrapping
Venue: arXiv cs.DS 2022
Year: 2022

In 1985 Hopcroft, Joseph and Whitesides showed it is NP-complete to decide whether a carpenter's ruler with segments of given positive lengths can be folded into a line of at most a given length, such that the folded hinges alternate between 180 degrees clockwise and 180 degrees counter-clockwise. At the open-problem session of 33rd Canadian Conference on Computational Geometry (CCCG '21), O'Rourke proposed a natural variation of this problem called {\em ruler wrapping}, in which all folded hinges must be folded the same way. In this paper we show O'Rourke's variation has an linear-time solution. We also show how, given a sequence of positive numbers, in linear time we can partition it into the maximum number of substrings whose totals are non-decreasing.
Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators
Venue: arXiv cs.AI 2022
Year: 2022

Recent advances in reinforcement learning (RL) have led to a growing interest in applying RL to classical planning domains or applying classical planning methods to some complex RL domains. However, the long-horizon goal-based problems found in classical planning lead to sparse rewards for RL, making direct application inefficient. In this paper, we propose to leverage domain-independent heuristic functions commonly used in the classical planning literature to improve the sample efficiency of RL. These classical heuristics act as dense reward generators to alleviate the sparse-rewards issue and enable our RL agent to learn domain-specific value functions as residuals on these heuristics, making learning easier. Correct application of this technique requires consolidating the discounted metric used in RL and the non-discounted metric used in heuristics. We implement the value functions using Neural Logic Machines, a neural network architecture designed for grounded first-order logic inputs. We demonstrate on several classical planning domains that using classical heuristics for RL allows for good sample efficiency compared to sparse-reward RL. We further show that our learned value functions generalize to novel problem instances in the same domain.
Efficient Decoding of Folded Linearized Reed-Solomon Codes in the Sum-Rank Metric
Venue: arXiv cs.IT 2022
Year: 2022

Recently, codes in the sum-rank metric attracted attention due to several applications in e.g. multishot network coding, distributed storage and quantum-resistant cryptography. The sum-rank analogs of Reed-Solomon and Gabidulin codes are linearized Reed-Solomon codes. We show how to construct $h$-folded linearized Reed-Solomon (FLRS) codes and derive an interpolation-based decoding scheme that is capable of correcting sum-rank errors beyond the unique decoding radius. The presented decoder can be used for either list or probabilistic unique decoding and requires at most $\mathcal{O}(sn^2)$ operations in $\mathbb{F}_{q^m}$, where $s \leq h$ is an interpolation parameter and $n$ denotes the length of the unfolded code. We derive a heuristic upper bound on the failure probability of the probabilistic unique decoder and verify the results via Monte Carlo simulations.
Structural Persistence in Language Models: Priming as a Window into Abstract Language Representations
Venue: arXiv cs.CL 2022
Year: 2022

We investigate the extent to which modern, neural language models are susceptible to structural priming, the phenomenon whereby the structure of a sentence makes the same structure more probable in a follow-up sentence. We explore how priming can be used to study the potential of these models to learn abstract structural information, which is a prerequisite for good performance on tasks that require natural language understanding skills. We introduce a novel metric and release Prime-LM, a large corpus where we control for various linguistic factors which interact with priming strength. We find that Transformer models indeed show evidence of structural priming, but also that the generalisations they learned are to some extent modulated by semantic information. Our experiments also show that the representations acquired by the models may not only encode abstract sequential structure but involve certain level of hierarchical syntactic information. More generally, our study shows that the priming paradigm is a useful, additional tool for gaining insights into the capacities of language models and opens the door to future priming-based investigations that probe the model's internal states.
An Efficient Probe-based Routing for Content-Centric Networking
Venue: arXiv cs.NI 2022
Year: 2022

With the development of new technologies and applications, such as the Internet of Things, smart cities, 5G, and edge computing, traditional Internet Protocol-based (IP-based) networks have been exposed as having many problems. Information-Centric Networking (ICN), Named Data Networking (NDN), and Content-Centric Networking (CCN) are therefore proposed as an alternative for future networks. However, unlike IP-based networks, CCN routing is nondeterministic and difficult to optimize due to frequent in-network caching replacement. This paper presents a novel probe-based routing algorithm that explores real-time in-network caching to ensure the routing table storing the optimal paths to the nearest content provider is up-to-date. Effective probe-selections, Pending Interest Table (PIT) probe, and Forwarding Information Base (FIB) probe are discussed and analyzed by simulation with different performance measurements. Compared with the basic CCN, in terms of qualitative analysis, the additional computational overhead of our approach is O(*) and O(*) on processing interest packets and data packets, respectively. However, in terms of quantitative analysis, our approach reduces the number of timeout interests by 6% and the average response time by 0.6 s. Furthermore, although basic CCN and our approach belong to the same Quality of Service category, our approach outperforms basic CCN in terms of real values. Additionally, our probe-based approach performs better than * and *. Owing to speedup FIB updating by probes, our approach provides more reliable interest packet routing when accounting for router failures. In summary, the results demonstrate that compared to basic CCN, our probe-based routing approach raises FIB accuracy and reduces network congestion and response time, resulting in efficient routing.
A Sufficient Condition for Convex Hull Property in General Convex Spatio-Temporal Corridors
Venue: arXiv cs.RO 2022
Year: 2022

Motion planning is one of the key modules in autonomous driving systems to generate trajectories for self-driving vehicles to follow. A common motion planning approach is to generate trajectories within semantic safe corridors. The trajectories are generated by optimizing parametric curves (e.g. Bezier curves) according to an objective function. To guarantee safety, the curves are required to satisfy the convex hull property, and be contained within the safety corridors. The convex hull property however does not necessary hold for time-dependent corridors, and depends on the shape of corridors. The existing approaches only support simple shape corridors, which is restrictive in real-world, complex scenarios. In this paper, we provide a sufficient condition for general convex, spatio-temporal corridors with theoretical proof of guaranteed convex hull property. The theorem allows for using more complicated shapes to generate spatio-temporal corridors and minimizing the uncovered search space to $O(\frac{1}{n^2})$ compared to $O(1)$ of trapezoidal corridors, which can improve the optimality of the solution. Simulation results show that using general convex corridors yields less harsh brakes, hence improving the overall smoothness of the resulting trajectories.
BlackLivesMatter 2020: An Analysis of Deleted and Suspended Users in Twitter
Venue: arXiv cs.SI 2022
Year: 2022

After George Floyd's death in May 2020, the volume of discussion in social media increased dramatically. A series of protests followed this tragic event, called as the 2020 BlackLivesMatter movement. Eventually, many user accounts are deleted by their owners or suspended due to violating the rules of social media platforms. In this study, we analyze what happened in Twitter before and after the event triggers with respect to deleted and suspended users. We create a novel dataset that includes approximately 500k users sharing 20m tweets, half of whom actively participated in the 2020 BlackLivesMatter discussion, but some of them were deleted or suspended later. We particularly examine the factors for undesirable behavior in terms of spamming, negative language, hate speech, and misinformation spread. We find that the users who participated to the 2020 BlackLivesMatter discussion have more negative and undesirable tweets, compared to the users who did not. Furthermore, the number of new accounts in Twitter increased significantly after the trigger event occurred, yet new users are more oriented to have undesirable tweets, compared to old ones.
Discovering Boundary Values of Feature-based Machine Learning Classifiers through Exploratory Datamorphic Testing
Venue: arXiv cs.LG 2022
Year: 2022

Testing has been widely recognised as difficult for AI applications. This paper proposes a set of testing strategies for testing machine learning applications in the framework of the datamorphism testing methodology. In these strategies, testing aims at exploring the data space of a classification or clustering application to discover the boundaries between classes that the machine learning application defines. This enables the tester to understand precisely the behaviour and function of the software under test. In the paper, three variants of exploratory strategies are presented with the algorithms implemented in the automated datamorphic testing tool Morphy. The correctness of these algorithms are formally proved. Their capability and cost of discovering borders between classes are evaluated via a set of controlled experiments with manually designed subjects and a set of case studies with real machine learning models.
Towards Protecting Face Embeddings in Mobile Face Verification Scenarios
Venue: arXiv cs.CV 2022
Year: 2022

This paper proposes PolyProtect, a method for protecting the sensitive face embeddings that are used to represent people's faces in neural-network-based face verification systems. PolyProtect transforms a face embedding to a more secure template, using a mapping based on multivariate polynomials parameterised by user-specific coefficients and exponents. In this work, PolyProtect is evaluated on two open-source face recognition systems in a cooperative-user mobile face verification context, under the toughest threat model that assumes a fully-informed attacker with complete knowledge of the system and all its parameters. Results indicate that PolyProtect can be tuned to achieve a satisfactory trade-off between the recognition accuracy of the PolyProtected face verification system and the irreversibility of the PolyProtected templates. Furthermore, PolyProtected templates are shown to be effectively unlinkable, especially if the user-specific parameters employed in the PolyProtect mapping are selected in a non-naive manner. The evaluation is conducted using practical methodologies with tangible results, to present realistic insight into the method's robustness as a face embedding protection scheme in practice. This work is fully reproducible using the publicly available code at: https://gitlab.idiap.ch/bob/bob.paper.polyprotect_2021.
Uniform Bounds for Scheduling with Job Size Estimates
Venue: arXiv cs.PF 2022
Year: 2022

We consider the problem of scheduling to minimize mean response time in M/G/1 queues where only estimated job sizes (processing times) are known to the scheduler, where a job of true size $s$ has estimated size in the interval $[βs, αs]$ for some $α\geq β> 0$. We evaluate each scheduling policy by its approximation ratio, which we define to be the ratio between its mean response time and that of Shortest Remaining Processing Time (SRPT), the optimal policy when true sizes are known. Our question: is there a scheduling policy that (a) has approximation ratio near 1 when $α$ and $β$ are near 1, (b) has approximation ratio bounded by some function of $α$ and $β$ even when they are far from 1, and (c) can be implemented without knowledge of $α$ and $β$? We first show that naively running SRPT using estimated sizes in place of true sizes is not such a policy: its approximation ratio can be arbitrarily large for any fixed $β< 1$. We then provide a simple variant of SRPT for estimated sizes that satisfies criteria (a), (b), and (c). In particular, we prove its approximation ratio approaches 1 uniformly as $α$ and $β$ approach 1. This is the first result showing this type of convergence for M/G/1 scheduling. We also study the Preemptive Shortest Job First (PSJF) policy, a cousin of SRPT. We show that, unlike SRPT, naively running PSJF using estimated sizes in place of true sizes satisfies criteria (b) and (c), as well as a weaker version of (a).
Domain-Specific Bias Filtering for Single Labeled Domain Generalization
Venue: arXiv cs.CV 2022
Year: 2022

Conventional Domain Generalization (CDG) utilizes multiple labeled source datasets to train a generalizable model for unseen target domains. However, due to expensive annotation costs, the requirements of labeling all the source data are hard to be met in real-world applications. In this paper, we investigate a Single Labeled Domain Generalization (SLDG) task with only one source domain being labeled, which is more practical and challenging than the CDG task. A major obstacle in the SLDG task is the discriminability-generalization bias: the discriminative information in the labeled source dataset may contain domain-specific bias, constraining the generalization of the trained model. To tackle this challenging task, we propose a novel framework called Domain-Specific Bias Filtering (DSBF), which initializes a discriminative model with the labeled source data and then filters out its domain-specific bias with the unlabeled source data for generalization improvement. We divide the filtering process into (1) feature extractor debiasing via k-means clustering-based semantic feature re-extraction and (2) classifier rectification through attention-guided semantic feature projection. DSBF unifies the exploration of the labeled and the unlabeled source data to enhance the discriminability and generalization of the trained model, resulting in a highly generalizable model. We further provide theoretical analysis to verify the proposed domain-specific bias filtering process. Extensive experiments on multiple datasets show the superior performance of DSBF in tackling both the challenging SLDG task and the CDG task.
TopiOCQA: Open-domain Conversational Question Answering with Topic Switching
Venue: arXiv cs.CL 2022
Year: 2022

In a conversational question answering scenario, a questioner seeks to extract information about a topic through a series of interdependent questions and answers. As the conversation progresses, they may switch to related topics, a phenomenon commonly observed in information-seeking search sessions. However, current datasets for conversational question answering are limiting in two ways: 1) they do not contain topic switches; and 2) they assume the reference text for the conversation is given, i.e., the setting is not open-domain. We introduce TopiOCQA (pronounced Tapioca), an open-domain conversational dataset with topic switches on Wikipedia. TopiOCQA contains 3,920 conversations with information-seeking questions and free-form answers. On average, a conversation in our dataset spans 13 question-answer turns and involves four topics (documents). TopiOCQA poses a challenging test-bed for models, where efficient retrieval is required on multiple turns of the same conversation, in conjunction with constructing valid responses using conversational history. We evaluate several baselines, by combining state-of-the-art document retrieval methods with neural reader models. Our best model achieves F1 of 55.8, falling short of human performance by 14.2 points, indicating the difficulty of our dataset. Our dataset and code is available at https://mcgill-nlp.github.io/topiocqa