OpenRaiser/Intern-Atlas huggingface dataset:
A Contextual Combinatorial Semi-Bandit Approach to Network Bottleneck Identification
Venue: arXiv cs.LG 2023
Year: 2023

Bottleneck identification is a challenging task in network analysis, especially when the network is not fully specified. To address this task, we develop a unified online learning framework based on combinatorial semi-bandits that performs bottleneck identification in parallel with learning the specifications of the underlying network. Within this framework, we adapt and study various combinatorial semi-bandit methods such as epsilon-greedy, LinUCB, BayesUCB, NeuralUCB, and Thompson Sampling. In addition, our framework is capable of using contextual information in the form of contextual bandits. Finally, we evaluate our framework on the real-world application of road networks and demonstrate its effectiveness in different settings.
Predicting Hate Intensity of Twitter Conversation Threads
Venue: arXiv cs.SI 2023
Year: 2023

Tweets are the most concise form of communication in online social media, wherein a single tweet has the potential to make or break the discourse of the conversation. Online hate speech is more accessible than ever, and stifling its propagation is of utmost importance for social media companies and users for congenial communication. Most of the research barring a recent few has focused on classifying an individual tweet regardless of the tweet thread/context leading up to that point. One of the classical approaches to curb hate speech is to adopt a reactive strategy after the hate speech postage. The ex-post facto strategy results in neglecting subtle posts that do not show the potential to instigate hate speech on their own but may portend in the subsequent discussion ensuing in the post's replies. In this paper, we propose DRAGNET++, which aims to predict the intensity of hatred that a tweet can bring in through its reply chain in the future. It uses the semantic and propagating structure of the tweet threads to maximize the contextual information leading up to and the fall of hate intensity at each subsequent tweet. We explore three publicly available Twitter datasets -- Anti-Racism contains the reply tweets of a collection of social media discourse on racist remarks during US political and Covid-19 background; Anti-Social presents a dataset of 40 million tweets amidst the COVID-19 pandemic on anti-social behaviours; and Anti-Asian presents Twitter datasets collated based on anti-Asian behaviours during COVID-19 pandemic. All the curated datasets consist of structural graph information of the Tweet threads. We show that DRAGNET++ outperforms all the state-of-the-art baselines significantly. It beats the best baseline by an 11% margin on the Person correlation coefficient and a decrease of 25% on RMSE for the Anti-Racism dataset with a similar performance on the other two datasets.
On the Number of Regions of Piecewise Linear Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Many feedforward neural networks (NNs) generate continuous and piecewise-linear (CPWL) mappings. Specifically, they partition the input domain into regions on which the mapping is affine. The number of these so-called linear regions offers a natural metric to characterize the expressiveness of CPWL NNs. The precise determination of this quantity is often out of reach in practice, and bounds have been proposed for specific architectures, including for ReLU and Maxout NNs. In this work, we generalize these bounds to NNs with arbitrary and possibly multivariate CPWL activation functions. We first provide upper and lower bounds on the maximal number of linear regions of a CPWL NN given its depth, width, and the number of linear regions of its activation functions. Our results rely on the combinatorial structure of convex partitions and confirm the distinctive role of depth which, on its own, is able to exponentially increase the number of regions. We then introduce a complementary stochastic framework to estimate the average number of linear regions produced by a CPWL NN. Under reasonable assumptions, the expected density of linear regions along any 1D path is bounded by the product of depth, width, and a measure of activation complexity (up to a scaling factor). This yields an identical role to the three sources of expressiveness: no exponential growth with depth is observed anymore.
Language with Vision: a Study on Grounded Word and Sentence Embeddings
Venue: arXiv cs.CL 2023
Year: 2023

Grounding language in vision is an active field of research seeking to construct cognitively plausible word and sentence representations by incorporating perceptual knowledge from vision into text-based representations. Despite many attempts at language grounding, achieving an optimal equilibrium between textual representations of the language and our embodied experiences remains an open field. Some common concerns are the following. Is visual grounding advantageous for abstract words, or is its effectiveness restricted to concrete words? What is the optimal way of bridging the gap between text and vision? To what extent is perceptual knowledge from images advantageous for acquiring high-quality embeddings? Leveraging the current advances in machine learning and natural language processing, the present study addresses these questions by proposing a simple yet very effective computational grounding model for pre-trained word embeddings. Our model effectively balances the interplay between language and vision by aligning textual embeddings with visual information while simultaneously preserving the distributional statistics that characterize word usage in text corpora. By applying a learned alignment, we are able to indirectly ground unseen words including abstract words. A series of evaluations on a range of behavioural datasets shows that visual grounding is beneficial not only for concrete words but also for abstract words, lending support to the indirect theory of abstract concepts. Moreover, our approach offers advantages for contextualized embeddings, such as those generated by BERT, but only when trained on corpora of modest, cognitively plausible sizes. Code and grounded embeddings for English are available at https://github.com/Hazel1994/Visually_Grounded_Word_Embeddings_2.
Disentangling Model Multiplicity in Deep Learning
Venue: arXiv cs.LG 2023
Year: 2023

Model multiplicity is a well-known but poorly understood phenomenon that undermines the generalisation guarantees of machine learning models. It appears when two models with similar training-time performance differ in their predictions and real-world performance characteristics. This observed 'predictive' multiplicity (PM) also implies elusive differences in the internals of the models, their 'representational' multiplicity (RM). We introduce a conceptual and experimental setup for analysing RM by measuring activation similarity via singular vector canonical correlation analysis (SVCCA). We show that certain differences in training methods systematically result in larger RM than others and evaluate RM and PM over a finite sample as predictors for generalizability. We further correlate RM with PM measured by the variance in i.i.d. and out-of-distribution test predictions in four standard image data sets. Finally, instead of attempting to eliminate RM, we call for its systematic measurement and maximal exposure.
Actionable Guidance for High-Consequence AI Risk Management: Towards Standards Addressing AI Catastrophic Risks
Venue: arXiv cs.CY 2023
Year: 2023

Artificial intelligence (AI) systems can provide many beneficial capabilities but also risks of adverse events. Some AI systems could present risks of events with very high or catastrophic consequences at societal scale. The US National Institute of Standards and Technology (NIST) has been developing the NIST Artificial Intelligence Risk Management Framework (AI RMF) as voluntary guidance on AI risk assessment and management for AI developers and others. For addressing risks of events with catastrophic consequences, NIST indicated a need to translate from high level principles to actionable risk management guidance. In this document, we provide detailed actionable-guidance recommendations focused on identifying and managing risks of events with very high or catastrophic consequences, intended as a risk management practices resource for NIST for AI RMF version 1.0 (released in January 2023), or for AI RMF users, or for other AI risk management guidance and standards as appropriate. We also provide our methodology for our recommendations. We provide actionable-guidance recommendations for AI RMF 1.0 on: identifying risks from potential unintended uses and misuses of AI systems; including catastrophic-risk factors within the scope of risk assessments and impact assessments; identifying and mitigating human rights harms; and reporting information on AI risk factors including catastrophic-risk factors. In addition, we provide recommendations on additional issues for a roadmap for later versions of the AI RMF or supplementary publications. These include: providing an AI RMF Profile with supplementary guidance for cutting-edge increasingly multi-purpose or general-purpose AI. We aim for this work to be a concrete risk-management practices contribution, and to stimulate constructive dialogue on how to address catastrophic risks and associated issues in AI standards.
Gray Learning from Non-IID Data with Out-of-distribution Samples
Venue: arXiv cs.LG 2023
Year: 2023

The integrity of training data, even when annotated by experts, is far from guaranteed, especially for non-IID datasets comprising both in- and out-of-distribution samples. In an ideal scenario, the majority of samples would be in-distribution, while samples that deviate semantically would be identified as out-of-distribution and excluded during the annotation process. However, experts may erroneously classify these out-of-distribution samples as in-distribution, assigning them labels that are inherently unreliable. This mixture of unreliable labels and varied data types makes the task of learning robust neural networks notably challenging. We observe that both in- and out-of-distribution samples can almost invariably be ruled out from belonging to certain classes, aside from those corresponding to unreliable ground-truth labels. This opens the possibility of utilizing reliable complementary labels that indicate the classes to which a sample does not belong. Guided by this insight, we introduce a novel approach, termed \textit{Gray Learning} (GL), which leverages both ground-truth and complementary labels. Crucially, GL adaptively adjusts the loss weights for these two label types based on prediction confidence levels. By grounding our approach in statistical learning theory, we derive bounds for the generalization error, demonstrating that GL achieves tight constraints even in non-IID settings. Extensive experimental evaluations reveal that our method significantly outperforms alternative approaches grounded in robust statistics.
Dual Representation Learning for Out-of-Distribution Detection
Venue: arXiv cs.LG 2023
Year: 2023

To classify in-distribution samples, deep neural networks explore strongly label-related information and discard weakly label-related information according to the information bottleneck. Out-of-distribution samples drawn from distributions differing from that of in-distribution samples could be assigned with unexpected high-confidence predictions because they could obtain minimum strongly label-related information. To distinguish in- and out-of-distribution samples, Dual Representation Learning (DRL) makes out-of-distribution samples harder to have high-confidence predictions by exploring both strongly and weakly label-related information from in-distribution samples. For a pretrained network exploring strongly label-related information to learn label-discriminative representations, DRL trains its auxiliary network exploring the remaining weakly label-related information to learn distribution-discriminative representations. Specifically, for a label-discriminative representation, DRL constructs its complementary distribution-discriminative representation by integrating diverse representations less similar to the label-discriminative representation. Accordingly, DRL combines label- and distribution-discriminative representations to detect out-of-distribution samples. Experiments show that DRL outperforms the state-of-the-art methods for out-of-distribution detection.
QuDASH: Quantum-inspired rate adaptation approach for DASH video streaming
Venue: arXiv cs.NI 2023
Year: 2023

Internet traffic is dramatically increasing with the development of network technologies and video streaming traffic accounts for large amount within the total traffic, which reveals the importance to guarantee the quality of content delivery service. Based on the network conditions, adaptive bitrate (ABR) control is utilized as a common technique which can choose the proper bitrate to ensure the video streaming quality. In this paper, new bitrate control method, QuDASH is proposed by taking advantage of the emerging quantum technology. In QuDASH, the adaptive control model is developed using the quadratic unconstrained binary optimization (QUBO), which aims at increasing the average bitrate and decreasing the video rebuffering events to maximize the user quality of experience (QoE). In order to formulate the video control model, first the QUBO terms of different factors are defined regarding video quality, bitrate change, and buffer condition. Then, all the individual QUBO terms are merged to generate an objective function. By minimizing the QUBO objective function, the bitrate choice is determined from the solution. The control model is solved by Digital Annealer, which is a quantum-inspired computing technology. The evaluation of the proposed method is carried out by simulation with the throughput traces obtained in real world under different scenarios and the comparison with other methods is conducted. Experiment results demonstrated that the proposed QuDASH method has better performance in terms of QoE compared with other advanced ABR methods. In 68.2% of the examined cases, QuDASH achieves the highest QoE results, which shows the superiority of the QuDASH over conventional methods.
An Input-Queueing TSN Switching Architecture to Achieve Zero Packet Loss for Timely Traffic
Venue: arXiv cs.NI 2023
Year: 2023

Zero packet loss with bounded latency is necessary for many applications, such as industrial control networks, automotive Ethernet, and aircraft communication systems. Traditional networks cannot meet the such strict requirement, and thus Time-Sensitive Networking (TSN) emerges. TSN is a set of standards proposed by IEEE 802 for providing deterministic connectivity in terms of low packet loss, low packet delay variation, and guaranteed packet transport. However, to our knowledge, few existing TSN solutions can deterministically achieve zero packet loss with bounded latency. This paper fills in this blank by proposing a novel input-queueing TSN switching architecture, under which we design a TDMA-like scheduling policy (called M-TDMA) along with a sufficient condition and an EDF-like scheduling policy (called M-EDF) along with a different sufficient condition to achieve zero packet loss with bounded latency.
Contextual Squeeze-and-Excitation for Efficient Few-Shot Image Classification
Venue: arXiv cs.CV 2023
Year: 2023

Recent years have seen a growth in user-centric applications that require effective knowledge transfer across tasks in the low-data regime. An example is personalization, where a pretrained system is adapted by learning on small amounts of labeled data belonging to a specific user. This setting requires high accuracy under low computational complexity, therefore the Pareto frontier of accuracy vs. adaptation cost plays a crucial role. In this paper we push this Pareto frontier in the few-shot image classification setting with a key contribution: a new adaptive block called Contextual Squeeze-and-Excitation (CaSE) that adjusts a pretrained neural network on a new task to significantly improve performance with a single forward pass of the user data (context). We use meta-trained CaSE blocks to conditionally adapt the body of a network and a fine-tuning routine to adapt a linear head, defining a method called UpperCaSE. UpperCaSE achieves a new state-of-the-art accuracy relative to meta-learners on the 26 datasets of VTAB+MD and on a challenging real-world personalization benchmark (ORBIT), narrowing the gap with leading fine-tuning methods with the benefit of orders of magnitude lower adaptation cost.
Quaternion variational integration for inertial maneuvering in a biomimetic UAV
Venue: arXiv cs.RO 2023
Year: 2023

Biological flying, gliding, and falling creatures are capable of extraordinary forms of inertial maneuvering: free-space maneuvering based on fine control of their multibody dynamics, as typified by the self-righting reflexes of cats. However, designing inertial maneuvering capability into biomimetic robots, such as biomimetic unmanned aerial vehicles (UAVs) is challenging. Accurately simulating this maneuvering requires numerical integrators that can ensure both singularity-free integration, and momentum and energy conservation, in a strongly coupled system - properties unavailable in existing conventional integrators. In this work, we develop a pair of novel quaternion variational integrators (QVIs) showing these properties, and demonstrate their capability for simulating inertial maneuvering in a biomimetic UAV showing complex multibody-dynamics coupling. Being quaternion-valued, these QVIs are innately singularity-free; and being variational, they can show excellent energy and momentum conservation properties. We explore the effect of variational integration order (left-rectangle vs. midpoint) on the conservation properties of integrator, and conclude that, in complex coupled systems in which canonical momenta may be time-varying, the midpoint integrator is required. The resulting midpoint QVI is well-suited to the analysis of inertial maneuvering in a biomimetic UAV - a feature that we demonstrate in simulation - and of other complex dynamical systems.
Two-sided Robustly Testable Codes
Venue: arXiv cs.IT 2023
Year: 2023

We show that the tensor product of two random linear codes is robustly testable with high probability. This implies that one can obtain pairs of linear codes such that their product and the product of their dual codes are simultaneously robustly testable. Such two-sided robustly testable codes (with a much weaker form of robustness) were the key ingredient in the recent constructions of asymptotically good quantum LDPC codes, which ensured their linear minimum distance. We hope that the existence of such codes with a stronger form of robustness, shown here, can be used to simplify the proofs and provide better distance bounds in these constructions. We also give new very simple examples of non-robustly testable codes. We show that if the parity-checks of two codes are mutually orthogonal, then their product is not robustly testable. In particular, this implies that the product of a code with its dual can never be robustly testable. We also study a property of a collection of linear codes called product-expansion, which can be viewed as a coboundary expansion of the cochain complex naturally associated with the product of these codes. We show that this property is related with the robust testability and the agreement testability of the products of codes.
Bridging the Gap Between Indexing and Retrieval for Differentiable Search Index with Query Generation
Venue: arXiv cs.IR 2023
Year: 2023

The Differentiable Search Index (DSI) is an emerging paradigm for information retrieval. Unlike traditional retrieval architectures where index and retrieval are two different and separate components, DSI uses a single transformer model to perform both indexing and retrieval. In this paper, we identify and tackle an important issue of current DSI models: the data distribution mismatch that occurs between the DSI indexing and retrieval processes. Specifically, we argue that, at indexing, current DSI methods learn to build connections between the text of long documents and the identifier of the documents, but then retrieval of document identifiers is based on queries that are commonly much shorter than the indexed documents. This problem is further exacerbated when using DSI for cross-lingual retrieval, where document text and query text are in different languages. To address this fundamental problem of current DSI models, we propose a simple yet effective indexing framework for DSI, called DSI-QG. When indexing, DSI-QG represents documents with a number of potentially relevant queries generated by a query generation model and re-ranked and filtered by a cross-encoder ranker. The presence of these queries at indexing allows the DSI models to connect a document identifier to a set of queries, hence mitigating data distribution mismatches present between the indexing and the retrieval phases. Empirical results on popular mono-lingual and cross-lingual passage retrieval datasets show that DSI-QG significantly outperforms the original DSI model.
Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs
Venue: arXiv cs.LG 2023
Year: 2023

Algorithmic Gaussianization is a phenomenon that can arise when using randomized sketching or sampling methods to produce smaller representations of large datasets: For certain tasks, these sketched representations have been observed to exhibit many robust performance characteristics that are known to occur when a data sample comes from a sub-gaussian random design, which is a powerful statistical model of data distributions. However, this phenomenon has only been studied for specific tasks and metrics, or by relying on computationally expensive methods. We address this by providing an algorithmic framework for gaussianizing data distributions via averaging, proving that it is possible to efficiently construct data sketches that are nearly indistinguishable (in terms of total variation distance) from sub-gaussian random designs. In particular, relying on a recently introduced sketching technique called Leverage Score Sparsified (LESS) embeddings, we show that one can construct an $n\times d$ sketch of an $N\times d$ matrix $A$, where $n\ll N$, that is nearly indistinguishable from a sub-gaussian design, in time $O(\text{nnz}(A)\log N + nd^2)$, where $\text{nnz}(A)$ is the number of non-zero entries in $A$. As a consequence, strong statistical guarantees and precise asymptotics available for the estimators produced from sub-gaussian designs (e.g., for least squares and Lasso regression, covariance estimation, low-rank approximation, etc.) can be straightforwardly adapted to our sketching framework. We illustrate this with a new approximation guarantee for sketched least squares, among other examples.
Optimal rate-limited secret key generation from Gaussian sources using lattices
Venue: arXiv cs.IT 2023
Year: 2023

We propose a lattice-based scheme for secret key generation from Gaussian sources in the presence of an eavesdropper, and show that it achieves the strong secret key capacity in the case of degraded source models, as well as the optimal secret key / public communication rate trade-off. The key ingredients of our scheme are the use of the modulo lattice operation to extract the channel intrinsic randomness, based on the notion of flatness factor, together with a randomized lattice quantization technique to quantize the continuous source. Compared to previous works, we introduce two new notions of flatness factor based on $L^1$ distance and KL divergence, respectively, which might be of independent interest. We prove the existence of secrecy-good lattices under $L^1$ distance and KL divergence, whose $L^1$ and KL flatness factors vanish for volume-to-noise ratios up to $2πe$. This improves upon the volume-to-noise ratio threshold $2π$ of the $L^{\infty}$ flatness factor.