OpenRaiser/Intern-Atlas huggingface dataset:
Toward Transparent AI: A Survey on Interpreting the Inner Structures of Deep Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

The last decade of machine learning has seen drastic increases in scale and capabilities. Deep neural networks (DNNs) are increasingly being deployed in the real world. However, they are difficult to analyze, raising concerns about using them without a rigorous understanding of how they function. Effective tools for interpreting them will be important for building more trustworthy AI by helping to identify problems, fix bugs, and improve basic understanding. In particular, "inner" interpretability techniques, which focus on explaining the internal components of DNNs, are well-suited for developing a mechanistic understanding, guiding manual modifications, and reverse engineering solutions. Much recent work has focused on DNN interpretability, and rapid progress has thus far made a thorough systematization of methods difficult. In this survey, we review over 300 works with a focus on inner interpretability tools. We introduce a taxonomy that classifies methods by what part of the network they help to explain (weights, neurons, subnetworks, or latent representations) and whether they are implemented during (intrinsic) or after (post hoc) training. To our knowledge, we are also the first to survey a number of connections between interpretability research and work in adversarial robustness, continual learning, modularity, network compression, and studying the human visual system. We discuss key challenges and argue that the status quo in interpretability research is largely unproductive. Finally, we highlight the importance of future work that emphasizes diagnostics, debugging, adversaries, and benchmarking in order to make interpretability tools more useful to engineers in practical applications.
Searching for Regularity in Bounded Functions
Venue: arXiv cs.CC 2023
Year: 2023

Given a function $f$ on $\mathbb{F}_2^n$, we study the following problem. What is the largest affine subspace $\mathcal{U}$ such that when restricted to $\mathcal{U}$, all the non-trivial Fourier coefficients of $f$ are very small? For the natural class of bounded Fourier degree $d$ functions $f:\mathbb{F}_2^n \to [-1,1]$, we show that there exists an affine subspace of dimension at least $ \tildeΩ(n^{1/d!}k^{-2})$, wherein all of $f$'s nontrivial Fourier coefficients become smaller than $ 2^{-k}$. To complement this result, we show the existence of degree $d$ functions with coefficients larger than $2^{-d\log n}$ when restricted to any affine subspace of dimension larger than $Ω(dn^{1/(d-1)})$. In addition, we give explicit examples of functions with analogous but weaker properties. Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of $\mathbb{F}_2^n$ that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers.
Network polarization, filter bubbles, and echo chambers: An annotated review of measures and reduction methods
Venue: arXiv cs.SI 2023
Year: 2023

Polarization arises when the underlying network connecting the members of a community or society becomes characterized by highly connected groups with weak inter-group connectivity. The increasing polarization, the strengthening of echo chambers, and the isolation caused by information filters in social networks are increasingly attracting the attention of researchers from different areas of knowledge such as computer science, economics, social and political sciences. This work presents an annotated review of network polarization measures and models used to handle the polarization. Several approaches for measuring polarization in graphs and networks were identified, including those based on homophily, modularity, random walks, and balance theory. The strategies used for reducing polarization include methods that propose edge or node editions (including insertions or deletions, as well as edge weight modifications), changes in social network design, or changes in the recommendation systems embedded in these networks.
Information Retention in the Multi-platform Sharing of Science
Venue: arXiv cs.CY 2023
Year: 2023

The public interest in accurate scientific communication, underscored by recent public health crises, highlights how content often loses critical pieces of information as it spreads online. However, multi-platform analyses of this phenomenon remain limited due to challenges in data collection. Collecting mentions of research tracked by Altmetric LLC, we examine information retention in the over 4 million online posts referencing 9,765 of the most-mentioned scientific articles across blog sites, Facebook, news sites, Twitter, and Wikipedia. To do so, we present a burst-based framework for examining online discussions about science over time and across different platforms. To measure information retention we develop a keyword-based computational measure comparing an online post to the scientific article's abstract. We evaluate our measure using ground truth data labeled by within field experts. We highlight three main findings: first, we find a strong tendency towards low levels of information retention, following a distinct trajectory of loss except when bursts of attention begin in social media. Second, platforms show significant differences in information retention. Third, sequences involving more platforms tend to be associated with higher information retention. These findings highlight a strong tendency towards information loss over time - posing a critical concern for researchers, policymakers, and citizens alike - but suggest that multi-platform discussions may improve information retention overall.
Toward Supporting Perceptual Complementarity in Human-AI Collaboration via Reflection on Unobservables
Venue: arXiv cs.HC 2023
Year: 2023

In many real world contexts, successful human-AI collaboration requires humans to productively integrate complementary sources of information into AI-informed decisions. However, in practice human decision-makers often lack understanding of what information an AI model has access to in relation to themselves. There are few available guidelines regarding how to effectively communicate about unobservables: features that may influence the outcome, but which are unavailable to the model. In this work, we conducted an online experiment to understand whether and how explicitly communicating potentially relevant unobservables influences how people integrate model outputs and unobservables when making predictions. Our findings indicate that presenting prompts about unobservables can change how humans integrate model outputs and unobservables, but do not necessarily lead to improved performance. Furthermore, the impacts of these prompts can vary depending on decision-makers' prior domain expertise. We conclude by discussing implications for future research and design of AI-based decision support tools.
Gotham Testbed: a Reproducible IoT Testbed for Security Experiments and Dataset Generation
Venue: arXiv cs.CR 2023
Year: 2023

The growing adoption of the Internet of Things (IoT) has brought a significant increase in attacks targeting those devices. Machine learning (ML) methods have shown promising results for intrusion detection; however, the scarcity of IoT datasets remains a limiting factor in developing ML-based security systems for IoT scenarios. Static datasets get outdated due to evolving IoT architectures and threat landscape; meanwhile, the testbeds used to generate them are rarely published. This paper presents the Gotham testbed, a reproducible and flexible security testbed extendable to accommodate new emulated devices, services or attackers. Gotham is used to build an IoT scenario composed of 100 emulated devices communicating via MQTT, CoAP and RTSP protocols, among others, in a topology composed of 30 switches and 10 routers. The scenario presents three threat actors, including the entire Mirai botnet lifecycle and additional red-teaming tools performing DoS, scanning, and attacks targeting IoT protocols. The testbed has many purposes, including a cyber range, testing security solutions, and capturing network and application data to generate datasets. We hope that researchers can leverage and adapt Gotham to include other devices, state-of-the-art attacks and topologies to share scenarios and datasets that reflect the current IoT settings and threat landscape.
Short Synchronizing Words for Random Automata
Venue: arXiv cs.FL 2023
Year: 2023

We prove that a uniformly random automaton with $n$ states on a 2-letter alphabet has a synchronizing word of length $O(n^{1/2}\log n)$ with high probability (w.h.p.). That is to say, w.h.p. there exists a word $ω$ of such length, and a state $v_0$, such that $ω$ sends all states to $v_0$. Prior to this work, the best upper bound was the quasilinear bound $O(n\log^3n)$ due to Nicaud (2016). The correct scaling exponent had been subject to various estimates by other authors between $0.5$ and $0.56$ based on numerical simulations, and our result confirms that the smallest one indeed gives a valid upper bound (with a log factor). Our proof introduces the concept of $w$-trees, for a word $w$, that is, automata in which the $w$-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on $n$ states is a $w$-tree for some word $w$ of length at most $(1+ε)\log_2(n)$, for any $ε>0$. The existence of the (random) word $w$ is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.
Measuring Causal Effects of Data Statistics on Language Model's `Factual' Predictions
Venue: arXiv cs.CL 2023
Year: 2023

Large amounts of training data are one of the major reasons for the high performance of state-of-the-art NLP models. But what exactly in the training data causes a model to make a certain prediction? We seek to answer this question by providing a language for describing how training data influences predictions, through a causal framework. Importantly, our framework bypasses the need to retrain expensive models and allows us to estimate causal effects based on observational data alone. Addressing the problem of extracting factual knowledge from pretrained language models (PLMs), we focus on simple data statistics such as co-occurrence counts and show that these statistics do influence the predictions of PLMs, suggesting that such models rely on shallow heuristics. Our causal framework and our results demonstrate the importance of studying datasets and the benefits of causality for understanding NLP models.
Self-organized Polygon Formation Control based on Distributed Estimation
Venue: arXiv cs.RO 2023
Year: 2023

This paper studies the problem of controlling a multi-robot system to achieve a polygon formation in a self-organized manner. Different from the typical formation control strategies where robots are steered to satisfy the predefined control variables, such as pairwise distances, relative positions and bearings, the foremost idea of this paper is to achieve polygon formations by injecting control inputs randomly to a few robots (say, vertex robots) of the group, and the rest follow the simple principles of moving towards the midpoint of their two nearest neighbors in the ring graph without any external inputs. In our problem, a fleet of robots is initially distributed in the plane. The socalled vertex robots take the responsibility of determining the geometric shape of the entire formation and its overall size, while the others move so as to minimize the differences with two direct neighbors. In the first step, each vertex robot estimates the number of robots in its associated chain. Two types of control inputs that serve for the estimation are designed using the measurements from the latest and the last two time instants respectively. In the second step, the self-organized formation control law is proposed where only vertex robots receive external information. Comparisons between the two estimation strategies are carried out in terms of the convergence speed and robustness. The effectiveness of the whole control framework is further validated in both simulation and physical experiments.
Enhanced Methods for the Weight Constrained Shortest Path Problem
Venue: arXiv cs.AI 2023
Year: 2023

The classic problem of constrained pathfinding is a well-studied, yet challenging, topic in AI with a broad range of applications in various areas such as communication and transportation. The Weight Constrained Shortest Path Problem (WCSPP), the base form of constrained pathfinding with only one side constraint, aims to plan a cost-optimum path with limited weight/resource usage. Given the bi-criteria nature of the problem (i.e., dealing with the cost and weight of paths), methods addressing the WCSPP have some common properties with bi-objective search. This paper leverages the recent state-of-the-art techniques in both constrained pathfinding and bi-objective search and presents two new solution approaches to the WCSPP on the basis of A* search, both capable of solving hard WCSPP instances on very large graphs. We empirically evaluate the performance of our algorithms on a set of large and realistic problem instances and show their advantages over the state-of-the-art algorithms in both time and space metrics. This paper also investigates the importance of priority queues in constrained search with A*. We show with extensive experiments on both realistic and randomised graphs how bucket-based queues without tie-breaking can effectively improve the algorithmic performance of exhaustive A*-based bi-criteria searches.
Smoothing Entailment Graphs with Language Models
Venue: arXiv cs.CL 2023
Year: 2023

The diversity and Zipfian frequency distribution of natural language predicates in corpora leads to sparsity in Entailment Graphs (EGs) built by Open Relation Extraction (ORE). EGs are computationally efficient and explainable models of natural language inference, but as symbolic models, they fail if a novel premise or hypothesis vertex is missing at test-time. We present theory and methodology for overcoming such sparsity in symbolic models. First, we introduce a theory of optimal smoothing of EGs by constructing transitive chains. We then demonstrate an efficient, open-domain, and unsupervised smoothing method using an off-the-shelf Language Model to find approximations of missing premise predicates. This improves recall by 25.1 and 16.3 percentage points on two difficult directional entailment datasets, while raising average precision and maintaining model explainability. Further, in a QA task we show that EG smoothing is most useful for answering questions with lesser supporting text, where missing premise predicates are more costly. Finally, controlled experiments with WordNet confirm our theory and show that hypothesis smoothing is difficult, but possible in principle.
One Object at a Time: Accurate and Robust Structure From Motion for Robots
Venue: arXiv cs.RO 2023
Year: 2023

A gaze-fixating robot perceives distance to the fixated object and relative positions of surrounding objects immediately, accurately, and robustly. We show how fixation, which is the act of looking at one object while moving, exploits regularities in the geometry of 3D space to obtain this information. These regularities introduce rotation-translation couplings that are not commonly used in structure from motion. To validate, we use a Franka Emika Robot with an RGB camera. We a) find that error in distance estimate is less than 5 mm at a distance of 15 cm, and b) show how relative position can be used to find obstacles under challenging scenarios. We combine accurate distance estimates and obstacle information into a reactive robot behavior that is able to pick up objects of unknown size, while impeded by unforeseen obstacles. Project page: https://oxidification.com/p/one-object-at-a-time/ .
Interacting with next-phrase suggestions: How suggestion systems aid and influence the cognitive processes of writing
Venue: arXiv cs.HC 2023
Year: 2023

Writing with next-phrase suggestions powered by large language models is becoming more pervasive by the day. However, research to understand writers' interaction and decision-making processes while engaging with such systems is still emerging. We conducted a qualitative study to shed light on writers' cognitive processes while writing with next-phrase suggestion systems. To do so, we recruited 14 amateur writers to write two reviews each, one without suggestions and one with suggestions. Additionally, we also positively and negatively biased the suggestion system to get a diverse range of instances where writers' opinions and the bias in the language model align or misalign to varying degrees. We found that writers interact with next-phrase suggestions in various complex ways: Writers abstracted and extracted multiple parts of the suggestions and incorporated them within their writing, even when they disagreed with the suggestion as a whole; along with evaluating the suggestions on various criteria. The suggestion system also had various effects on the writing process, such as altering the writer's usual writing plans, leading to higher levels of distraction etc. Based on our qualitative analysis using the cognitive process model of writing by Hayes as a lens, we propose a theoretical model of 'writer-suggestion interaction' for writing with GPT-2 (and causal language models in general) for a movie review writing task, followed by directions for future research and design.
Joint Active and Passive Beamforming for RIS-aided MIMO Communications with Low-Resolution Phase Shifts
Venue: arXiv cs.IT 2023
Year: 2023

Practical hardware limitations often impose a reduced number of available phase shifts at the elements of a reconfigurable intelligent surface (RIS). Most works often assume continuous phase-shits at the RIS elements for the transmit and passive beamforming optimization, which can lead to substantial performance loss. Therefore, to harvest the gains of RIS-assisted multi-stream multiple-input multiple-output (MIMO) communications under realistic phase shifts, this letter proposes a problem formulation for the maximization of the achievable rate over the transmit precoder and RIS elements, which avoids an explicit discrete constraint while still incorporating its effect. To efficiently tackle the resulting problem when considering large arrays and RIS panels, an iterative algorithm is derived which comprises a sequence of simple projections. Simulation results demonstrate that the proposed design can be very effective, especially with low-resolution phase-shifts.
See What the Robot Can't See: Learning Cooperative Perception for Visual Navigation
Venue: arXiv cs.RO 2023
Year: 2023

We consider the problem of navigating a mobile robot towards a target in an unknown environment that is endowed with visual sensors, where neither the robot nor the sensors have access to global positioning information and only use first-person-view images. In order to overcome the need for positioning, we train the sensors to encode and communicate relevant viewpoint information to the mobile robot, whose objective it is to use this information to navigate to the target along the shortest path. We overcome the challenge of enabling all the sensors (even those that cannot directly see the target) to predict the direction along the shortest path to the target by implementing a neighborhood-based feature aggregation module using a Graph Neural Network (GNN) architecture. In our experiments, we first demonstrate generalizability to previously unseen environments with various sensor layouts. Our results show that by using communication between the sensors and the robot, we achieve up to 2.0x improvement in SPL (Success weighted by Path Length) when compared to a communication-free baseline. This is done without requiring a global map, positioning data, nor pre-calibration of the sensor network. Second, we perform a zero-shot transfer of our model from simulation to the real world. Laboratory experiments demonstrate the feasibility of our approach in various cluttered environments. Finally, we showcase examples of successful navigation to the target while both the sensor network layout as well as obstacles are dynamically reconfigured as the robot navigates. We provide a video demo, the dataset, trained models, and source code. https://www.youtube.com/watch?v=kcmr6RUgucw https://github.com/proroklab/sensor-guided-visual-nav
BERT4Loc: BERT for Location -- POI Recommender System
Venue: arXiv cs.IR 2023
Year: 2023

Recommending points of interest (POIs) is a challenging task that requires extracting comprehensive location data from location-based social media platforms. To provide effective location-based recommendations, it's important to analyze users' historical behavior and preferences. In this study, we present a sophisticated location-aware recommendation system that uses Bidirectional Encoder Representations from Transformers (BERT) to offer personalized location-based suggestions. Our model combines location information and user preferences to provide more relevant recommendations compared to models that predict the next POI in a sequence. Our experiments on two benchmark dataset show that our BERT-based model outperforms various state-of-the-art sequential models. Moreover, we see the effectiveness of the proposed model for quality through additional experiments.
Mitigating Smart Jammers in Multi-User MIMO
Venue: arXiv cs.IT 2023
Year: 2023

Wireless systems must be resilient to jamming attacks. Existing mitigation methods based on multi-antenna processing require knowledge of the jammer's transmit characteristics that may be difficult to acquire, especially for smart jammers that evade mitigation by transmitting only at specific instants. We propose a novel method to mitigate smart jamming attacks on the massive multi-user multiple-input multiple-output (MU-MIMO) uplink which does not require the jammer to be active at any specific instant. By formulating an optimization problem that unifies jammer estimation and mitigation, channel estimation, and data detection, we exploit that a jammer cannot change its subspace within a coherence interval. Theoretical results for our problem formulation show that its solution is guaranteed to recover the users' data symbols under certain conditions. We develop two efficient iterative algorithms for approximately solving the proposed problem formulation: MAED, a parameter-free algorithm which uses forward-backward splitting with a box symbol prior, and SO-MAED, which replaces the prior of MAED with soft-output symbol estimates that exploit the discrete transmit constellation and which uses deep unfolding to optimize algorithm parameters. We use simulations to demonstrate that the proposed algorithms effectively mitigate a wide range of smart jammers without a priori knowledge about the attack type.
Extremal numbers of disjoint triangles in $r$-partite graphs
Venue: arXiv cs.DM 2023
Year: 2023

For two graphs $G$ and $F$, the extremal number of $F$ in $G$, denoted by {ex}$(G,F)$, is the maximum number of edges in a spanning subgraph of $G$ not containing $F$ as a subgraph. Determining {ex}$(K_n,F)$ for a given graph $F$ is a classical extremal problem in graph theory. In 1962, Erdős determined {ex}$(K_n,kK_3)$, which generalized Mantel's Theorem. On the other hand, in 1974, {Bollobás}, Erdős, and Straus determined {ex}$(K_{n_1,n_2,\dots,n_r},K_t)$, which extended Turán's Theorem to complete multipartite graphs. { In this paper,} we determine {ex}$(K_{n_1,n_2,\dots,n_r},kK_3)$ for $r\ge 4$ and $10k-4\le n_1+4k\le n_2\le n_3\le \cdots \le n_r$.