OpenRaiser/Intern-Atlas huggingface dataset:
CrossMap Transformer: A Crossmodal Masked Path Transformer Using Double Back-Translation for Vision-and-Language Navigation
Venue: arXiv cs.RO 2023
Year: 2023

Navigation guided by natural language instructions is particularly suitable for Domestic Service Robots that interacts naturally with users. This task involves the prediction of a sequence of actions that leads to a specified destination given a natural language navigation instruction. The task thus requires the understanding of instructions, such as ``Walk out of the bathroom and wait on the stairs that are on the right''. The Visual and Language Navigation remains challenging, notably because it requires the exploration of the environment and at the accurate following of a path specified by the instructions to model the relationship between language and vision. To address this, we propose the CrossMap Transformer network, which encodes the linguistic and visual features to sequentially generate a path. The CrossMap transformer is tied to a Transformer-based speaker that generates navigation instructions. The two networks share common latent features, for mutual enhancement through a double back translation model: Generated paths are translated into instructions while generated instructions are translated into path The experimental results show the benefits of our approach in terms of instruction understanding and instruction generation.
An Empirical Study of Compound PCFGs
Venue: arXiv cs.CL 2023
Year: 2023

Compound probabilistic context-free grammars (C-PCFGs) have recently established a new state of the art for unsupervised phrase-structure grammar induction. However, due to the high space and time complexities of chart-based representation and inference, it is difficult to investigate C-PCFGs comprehensively. In this work, we rely on a fast implementation of C-PCFGs to conduct an evaluation complementary to that of~\citet{kim-etal-2019-compound}. We start by analyzing and ablating C-PCFGs on English treebanks. Our findings suggest that (1) C-PCFGs are data-efficient and can generalize to unseen sentence/constituent lengths; and (2) C-PCFGs make the best use of sentence-level information in generating preterminal rule probabilities. We further conduct a multilingual evaluation of C-PCFGs. The experimental results show that the best configurations of C-PCFGs, which are tuned on English, do not always generalize to morphology-rich languages.
Cyber Threat Intelligence Model: An Evaluation of Taxonomies, Sharing Standards, and Ontologies within Cyber Threat Intelligence
Venue: arXiv cs.CR 2023
Year: 2023

Cyber threat intelligence is the provision of evidence-based knowledge about existing or emerging threats. Benefits from threat intelligence include increased situational awareness, efficiency in security operations, and improved prevention, detection, and response capabilities. To process, correlate, and analyze vast amounts of threat information and data and derive intelligence that can be shared and consumed in meaningful times, it is required to utilize structured, machine-readable formats that incorporate the industry-required expressivity while at the same time being unambiguous. To a large extent, this is achieved with technologies like ontologies, schemas, and taxonomies. This research evaluates the coverage and high-level conceptual expressivity of cyber-threat-intelligence-relevant ontologies, sharing standards, and taxonomies pertaining to the who, what, why, where, when, and how elements of threats and attacks in addition to courses of action and technical indicators. The results confirm that little emphasis has been given to developing a comprehensive cyber threat intelligence ontology, with existing efforts being not thoroughly designed, non-interoperable, ambiguous, and lacking proper semantics and axioms for reasoning.
Reduction Free Normalisation for a proof irrelevant type of propositions
Venue: arXiv cs.LO 2023
Year: 2023

We show normalisation and decidability of convertibility for a type theory with a hierarchy of universes and a proof irrelevant type of propositions, close to the type system used in the proof assistant Lean. Contrary to previous arguments, the proof does not require explicitly to introduce a notion of neutral and normal forms.
Reverse Differentiation via Predictive Coding
Venue: arXiv cs.LG 2023
Year: 2023

Deep learning has redefined the field of artificial intelligence (AI) thanks to the rise of artificial neural networks, which are architectures inspired by their neurological counterpart in the brain. Through the years, this dualism between AI and neuroscience has brought immense benefits to both fields, allowing neural networks to be used in dozens of applications. These networks use an efficient implementation of reverse differentiation, called backpropagation (BP). This algorithm, however, is often criticized for its biological implausibility (e.g., lack of local update rules for the parameters). Therefore, biologically plausible learning methods that rely on predictive coding (PC), a framework for describing information processing in the brain, are increasingly studied. Recent works prove that these methods can approximate BP up to a certain margin on multilayer perceptrons (MLPs), and asymptotically on any other complex model, and that zero-divergence inference learning (Z-IL), a variant of PC, is able to exactly implement BP on MLPs. However, the recent literature shows also that there is no biologically plausible method yet that can exactly replicate the weight update of BP on complex models. To fill this gap, in this paper, we generalize (PC and) Z-IL by directly defining them on computational graphs, and show that it can perform exact reverse differentiation. What results is the first biologically plausible algorithm that is equivalent to BP in the way of updating parameters on any neural network, providing a bridge between the interdisciplinary research of neuroscience and deep learning.
TS-Net: OCR Trained to Switch Between Text Transcription Styles
Venue: arXiv cs.CV 2023
Year: 2023

Users of OCR systems, from different institutions and scientific disciplines, prefer and produce different transcription styles. This presents a problem for training of consistent text recognition neural networks on real-world data. We propose to extend existing text recognition networks with a Transcription Style Block (TSB) which can learn from data to switch between multiple transcription styles without any explicit knowledge of transcription rules. TSB is an adaptive instance normalization conditioned by identifiers representing consistently transcribed documents (e.g. single document, documents by a single transcriber, or an institution). We show that TSB is able to learn completely different transcription styles in controlled experiments on artificial data, it improves text recognition accuracy on large-scale real-world data, and it learns semantically meaningful transcription style embedding. We also show how TSB can efficiently adapt to transcription styles of new documents from transcriptions of only a few text lines.
Robust Sensing of Low-Rank Matrices with Non-Orthogonal Sparse Decomposition
Venue: arXiv cs.IT 2023
Year: 2023

We consider the problem of recovering an unknown low-rank matrix X with (possibly) non-orthogonal, effectively sparse rank-1 decomposition from measurements y gathered in a linear measurement process A. We propose a variational formulation that lends itself to alternating minimization and whose global minimizers provably approximate X up to noise level. Working with a variant of robust injectivity, we derive reconstruction guarantees for various choices of A including sub-gaussian, Gaussian rank-1, and heavy-tailed measurements. Numerical experiments support the validity of our theoretical considerations.
Challenges of 3D Surface Reconstruction in Capsule Endoscopy
Venue: arXiv cs.CV 2023
Year: 2023

Essential for improving the accuracy and reliability of bowel cancer screening, three-dimensional (3D) surface reconstruction using capsule endoscopy (CE) images remains challenging due to CE hardware and software limitations. This report generally focuses on challenges associated with 3D visualization and specifically investigates the impact of the indeterminate selection of the angle of the line of sight on 3D surfaces. Furthermore, it demonstrates that impact through 3D surfaces viewed at the same azimuth angles and different elevation angles of the line of sight. The report concludes that 3D printing of reconstructed 3D surfaces can potentially overcome line of sight indeterminate selection and 2D screen visual restriction-related errors.
The Low-Rank Simplicity Bias in Deep Networks
Venue: arXiv cs.LG 2023
Year: 2023

Modern deep neural networks are highly over-parameterized compared to the data on which they are trained, yet they often generalize remarkably well. A flurry of recent work has asked: why do deep networks not overfit to their training data? In this work, we make a series of empirical observations that investigate and extend the hypothesis that deeper networks are inductively biased to find solutions with lower effective rank embeddings. We conjecture that this bias exists because the volume of functions that maps to low effective rank embedding increases with depth. We show empirically that our claim holds true on finite width linear and non-linear models on practical learning paradigms and show that on natural data, these are often the solutions that generalize well. We then show that the simplicity bias exists at both initialization and after training and is resilient to hyper-parameters and learning methods. We further demonstrate how linear over-parameterization of deep non-linear models can be used to induce low-rank bias, improving generalization performance on CIFAR and ImageNet without changing the modeling capacity.
Alive publication
Venue: arXiv cs.DL 2023
Year: 2023

An alive publication is a new genre for presenting the results of scientific research, which means that scientific work is published online and then constantly developing and improving by its author. Serious errors and typos are no longer fatal, nor do they haunt the author for the rest of his or her life. The reader of an alive publication knows that the author is constantly monitoring changes occurring in this branch of science. Alive publication faces the inertia of scientific publishing traditions and, in particular, traditional bibliometrics. Unfortunately, at present, the author who supports an alive publication is dramatically losing out on many generally accepted bibliometric indicators. The alive publication encourages the development of the bibliography apparatus. Each bibliographic reference will soon have to contain such important for the reader updating on-the-fly attributes as attendance, number of external links, date of the last revision, etc. It is to be expected that as the alive publication spreads over to the scientific world, the author's concern for the publication's evolution will become like a parent's care for the development of a child. The Internet will be filled with scientific publications that do not lose their relevance over time.
Cluster Contrast for Unsupervised Person Re-Identification
Venue: arXiv cs.CV 2023
Year: 2023

State-of-the-art unsupervised re-ID methods train the neural networks using a memory-based non-parametric softmax loss. Instance feature vectors stored in memory are assigned pseudo-labels by clustering and updated at instance level. However, the varying cluster sizes leads to inconsistency in the updating progress of each cluster. To solve this problem, we present Cluster Contrast which stores feature vectors and computes contrast loss at the cluster level. Our approach employs a unique cluster representation to describe each cluster, resulting in a cluster-level memory dictionary. In this way, the consistency of clustering can be effectively maintained throughout the pipline and the GPU memory consumption can be significantly reduced. Thus, our method can solve the problem of cluster inconsistency and be applicable to larger data sets. In addition, we adopt different clustering algorithms to demonstrate the robustness and generalization of our framework. The application of Cluster Contrast to a standard unsupervised re-ID pipeline achieves considerable improvements of 9.9%, 8.3%, 12.1% compared to state-of-the-art purely unsupervised re-ID methods and 5.5%, 4.8%, 4.4% mAP compared to the state-of-the-art unsupervised domain adaptation re-ID methods on the Market, Duke, and MSMT17 datasets. Code is available at https://github.com/alibaba/cluster-contrast.
Continuous mean distance of a weighted graph
Venue: arXiv cs.CG 2023
Year: 2023

We study the concept of the continuous mean distance of a weighted graph. For connected unweighted graphs, the mean distance can be defined as the arithmetic mean of the distances between all pairs of vertices. This parameter provides a natural measure of the compactness of the graph, and has been intensively studied, together with several variants, including its version for weighted graphs. The continuous analog of the (discrete) mean distance is the mean of the distances between all pairs of points on the edges of the graph. Despite being a very natural generalization, to the best of our knowledge this concept has been barely studied, since the jump from discrete to continuous implies having to deal with an infinite number of distances, something that increases the difficulty of the parameter. In this paper we show that the continuous mean distance of a weighted graph can be computed in time quadratic in the number of edges, by two different methods that apply fundamental concepts in discrete algorithms and computational geometry. We also present structural results that allow a faster computation of this continuous parameter for several classes of weighted graphs. Finally, we study the relation between the (discrete) mean distance and its continuous counterpart, mainly focusing on the relevant question of the convergence when iteratively subdividing the edges of the weighted graph.
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism
Venue: arXiv cs.LG 2023
Year: 2023

Offline (or batch) reinforcement learning (RL) algorithms seek to learn an optimal policy from a fixed dataset without active data collection. Based on the composition of the offline dataset, two main categories of methods are used: imitation learning which is suitable for expert datasets and vanilla offline RL which often requires uniform coverage datasets. From a practical standpoint, datasets often deviate from these two extremes and the exact data composition is usually unknown a priori. To bridge this gap, we present a new offline RL framework that smoothly interpolates between the two extremes of data composition, hence unifying imitation learning and vanilla offline RL. The new framework is centered around a weak version of the concentrability coefficient that measures the deviation from the behavior policy to the expert policy alone. Under this new framework, we further investigate the question on algorithm design: can one develop an algorithm that achieves a minimax optimal rate and also adapts to unknown data composition? To address this question, we consider a lower confidence bound (LCB) algorithm developed based on pessimism in the face of uncertainty in offline RL. We study finite-sample properties of LCB as well as information-theoretic limits in multi-armed bandits, contextual bandits, and Markov decision processes (MDPs). Our analysis reveals surprising facts about optimality rates. In particular, in all three settings, LCB achieves a faster rate of $1/N$ for nearly-expert datasets compared to the usual rate of $1/\sqrt{N}$ in offline RL, where $N$ is the number of samples in the batch dataset. In the case of contextual bandits with at least two contexts, we prove that LCB is adaptively optimal for the entire data composition range, achieving a smooth transition from imitation learning to offline RL. We further show that LCB is almost adaptively optimal in MDPs.
The Complexity of Pacing for Second-Price Auctions
Venue: arXiv cs.GT 2023
Year: 2023

Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in this game is known as a pacing equilibrium. In this work, we show that the problem of finding an approximate pacing equilibrium is PPAD-complete for second-price auctions. This resolves an open question of Conitzer et al. [2021]. As a consequence of our hardness result, we show that the tatonnement-style budget-management dynamics introduced by Borgs et al. [2007] are unlikely to converge efficiently for repeated second-price auctions. This disproves a conjecture by Borgs et al. [2007], under the assumption that the complexity class PPAD is not equal to P. Our hardness result also implies the existence of a refinement of supply-aware market equilibria which is hard to compute with simple linear utilities.
Active RIS vs. Passive RIS: Which Will Prevail in 6G?
Venue: arXiv cs.IT 2023
Year: 2023

As a revolutionary paradigm for controlling wireless channels, reconfigurable intelligent surfaces (RISs) have emerged as a candidate technology for future 6G networks. However, due to the "multiplicative fading" effect, the existing passive RISs only achieve limited capacity gains in many scenarios with strong direct links. In this paper, the concept of active RISs is proposed to overcome this fundamental limitation. Unlike passive RISs that reflect signals without amplification, active RISs can amplify the reflected signals via amplifiers integrated into their elements. To characterize the signal amplification and incorporate the noise introduced by the active components, we develop and verify the signal model of active RISs through the experimental measurements based on a fabricated active RIS element. Based on the verified signal model, we further analyze the asymptotic performance of active RISs to reveal the substantial capacity gain they provide for wireless communications. Finally, we formulate the sum-rate maximization problem for an active RIS aided multi-user multiple-input single-output (MU-MISO) system and a joint transmit beamforming and reflect precoding scheme is proposed to solve this problem. Simulation results show that, in a typical wireless system, passive RISs can realize only a limited sum-rate gain of 22%, while active RISs can achieve a significant sum-rate gain of 130%, thus overcoming the "multiplicative fading" effect.
Set-Valued Rigid Body Dynamics for Simultaneous, Inelastic, Frictional Impacts
Venue: arXiv cs.RO 2023
Year: 2023

Robotic manipulation and locomotion often entail nearly-simultaneous collisions -- such as heel and toe strikes during a foot step -- with outcomes that are extremely sensitive to the order in which impacts occur. Robotic simulators commonly lack the accuracy to predict this ordering, and instead pick one with a heuristic. This discrepancy degrades performance when model-based controllers and policies learned in simulation are placed on a real robot. We reconcile this issue with a set-valued rigid-body model which generates a broad set of physically reasonable outcomes of simultaneous frictional impacts. We first extend Routh's impact model to multiple impacts by reformulating it as a differential inclusion (DI), and show that any solution will resolve all impacts in finite time. By considering time as a state, we embed this model into another DI which captures the continuous-time evolution of rigid body dynamics, and guarantee existence of solutions. We finally cast simulation of simultaneous impacts as a linear complementarity problem (LCP), and develop an algorithm for tight approximation of the post-impact velocity set with probabilistic guarantees. We demonstrate our approach on several examples drawn from manipulation and legged locomotion.
SMORES-EP, a Modular Robot with Parallel Self-assembly
Venue: arXiv cs.RO 2023
Year: 2023

Self-assembly of modular robotic systems enables the construction of complex robotic configurations to adapt to different tasks. This paper presents a framework for SMORES types of modular robots to efficiently self-assemble into tree topologies. These modular robots form kinematic chains that have been shown to be capable of a large variety of manipulation and locomotion tasks, yet they can reconfigure using a mobile reconfiguration. A desired kinematic topology can be mapped onto a planar pattern with optimal module assignment based on the modules' locations, then the mobile reconfiguration assembly process can be executed in parallel. A docking controller is developed to guarantee the success of docking processes. A hybrid control architecture is designed to handle a large number of modules and complex behaviors of each individual, and achieve efficient and robust self-assembly actions. The framework is demonstrated in both hardware and simulation on the SMORES-EP platform.
Ideology-driven polarisation in online ratings: the review bombing of The Last of Us Part II
Venue: arXiv cs.CY 2023
Year: 2023

A review bomb is a large and quick surge in online reviews about a product, service, or business, coordinated by a group of people willing to manipulate public opinion about that entity. This study challenges the assumption that review bombing is solely a phenomenon of misinformation and connects motivations and substantial content of online reviews with the broader theory of judgement of facts and of value. These theories are verified in a quantitative analysis of the most prominent case of review bombing, which involves the video game The Last of Us Part II. It is discovered that ideology-driven ratings are followed by a grassroots counter-bombing, aimed at mitigating the effects of the negative ratings. The two factions of bombers, despite being politically polar opposites, are very similar in terms of other metrics. Evidence suggests the theoretical framework of political disinformation is insufficient to explain this case of review bombing. In light of the need to re-frame review bombing, recommendations are proposed for the preventive management of future cases.
Improving the Gilbert-Varshamov Bound by Graph Spectral Method
Venue: arXiv cs.IT 2023
Year: 2023

We improve Gilbert-Varshamov bound by graph spectral method. Gilbert graph $G_{q,n,d}$ is a graph with all vectors in $\mathbb{F}_q^n$ as vertices where two vertices are adjacent if their Hamming distance is less than $d$. In this paper, we calculate the eigenvalues and eigenvectors of $G_{q,n,d}$ using the properties of Cayley graph. The improved bound is associated with the minimum eigenvalue of the graph. Finally we give an algorithm to calculate the bound and linear codes which satisfy the bound.