OpenRaiser/Intern-Atlas huggingface dataset:
The 4-Adic Complexity of Interleaved Quaternary Sequences of Even Length with Optimal Autocorrelation
Venue: arXiv cs.IT 2022
Year: 2022

Su et al. proposed several new classes of quaternary sequences of even length with optimal autocorrelation interleaved by twin-prime sequences pairs, GMW sequences pairs or binary cyclotomic sequences of order four in \cite{S1}. In this paper, we determine the 4-adic complexity of these quaternary sequences with period $2n$ by using correlation function and the "Gauss periods" of order four and "quadratic Gauss sums" on finite field $\mathbb{F}_n$ and valued in $\mathbb{Z}^{*}_{4^{2n}-1}$. Our results show that they are safe enough to resist the attack of the rational approximation algorithm.
On the Existential Fragments of Local First-Order Logics with Data
Venue: arXiv cs.LO 2022
Year: 2022

We study first-order logic over unordered structures whose elements carry a finite number of data values from an infinite domain which can be compared wrt. equality. As the satisfiability problem for this logic is undecidable in general, in a previous work, we have introduced a family of local fragments that restrict quantification to neighbourhoods of a given reference point. We provide here the precise complexity characterisation of the satisfiability problem for the existential fragments of this local logic depending on the number of data values carried by each element and the radius of the considered neighbourhoods.
Parametric Interval Temporal Logic over Infinite Words
Venue: arXiv cs.LO 2022
Year: 2022

Model checking for Halpern and Shoham's interval temporal logic HS has been recently investigated in a systematic way, and it is known to be decidable under three distinct semantics. Here, we focus on the trace-based semantics, where the infinite execution paths (traces) of the given (finite) Kripke structure are the main semantic entities. In this setting, each finite infix of a trace is interpreted as an interval, and a proposition holds over an interval if and only if it holds over each component state (homogeneity assumption). In this paper, we introduce a quantitative extension of HS over traces, called parametric HS (PHS). The novel logic allows to express parametric timing constraints on the duration (length) of the intervals. We show that checking the existence of a parameter valuation for which a Kripke structure satisfies a PHS formula (model checking), or a PHS formula admits a trace as a model under the homogeneity assumption (satisfiability) is decidable. Moreover, we identify a fragment of PHS which subsumes parametric LTL and for which model checking and satisfiability are shown to be EXPSPACE-complete.
Android Private Compute Core Architecture
Venue: arXiv cs.CR 2022
Year: 2022

Android's Private Compute Core (PCC) is a secure, isolated environment within the operating system, that maintains separation from apps while enabling users and developers to maintain control over their data. It is backed by open-source code in the Android Framework introduced in Android 12. PCC allows features to communicate with a server to receive model updates and contribute to global model training through Private Compute Services (PCS), the core of which has been open sourced. PCC is part of the OS, and by virtue of being isolated, constrained, and trusted, it can host sophisticated ML features. The hosted features themselves, running inside PCC, can be closed source and updatable. In this way, PCC enables machine learning features to process ambient and OS-level data and improve over time, while restricting the availability of information about individual users to servers or apps.
Avoid One's Doom: Finding Cliff-Edge Configurations in Petri Nets
Venue: arXiv cs.FL 2022
Year: 2022

A crucial question in analyzing a concurrent system is to determine its long-run behaviour, and in particular, whether there are irreversible choices in its evolution, leading into parts of the reachability space from which there is no return to other parts. Casting this problem in the unifying framework of safe Petri nets, our previous work has provided techniques for identifying attractors, i.e. terminal strongly connected components of the reachability space, whose attraction basins we wish to determine. Here, we provide a solution for the case of safe Petri nets. Our algorithm uses net unfoldings and provides a map of all of the system's configurations (concurrent executions) that act as cliff-edges, i.e. any maximal extension for those configurations lies in some basin that is considered fatal. The computation turns out to require only a relatively small prefix of the unfolding, just twice the depth of Esparza's complete prefix.
Performance Impact of Channel Aging and Phase Noise on Intelligent Reflecting Surface
Venue: arXiv cs.IT 2022
Year: 2022

This letter aims to clarify the impact of channel aging and phase noise on the performance of intelligent reflecting surface-aided wireless systems. We first model mathematically the outdated channel state information (CSI) due to Doppler shifts and phase noise stemming from hardware impairment. Then, a closed-form expression of achievable spectral efficiency under noisy and aged CSI is theoretically derived. Some typical simulation results to numerically demonstrate the performance impact are illustrated.
MulBot: Unsupervised Bot Detection Based on Multivariate Time Series
Venue: arXiv cs.SI 2022
Year: 2022

Online social networks are actively involved in the removal of malicious social bots due to their role in the spread of low quality information. However, most of the existing bot detectors are supervised classifiers incapable of capturing the evolving behavior of sophisticated bots. Here we propose MulBot, an unsupervised bot detector based on multivariate time series (MTS). For the first time, we exploit multidimensional temporal features extracted from user timelines. We manage the multidimensionality with an LSTM autoencoder, which projects the MTS in a suitable latent space. Then, we perform a clustering step on this encoded representation to identify dense groups of very similar users -- a known sign of automation. Finally, we perform a binary classification task achieving f1-score $= 0.99$, outperforming state-of-the-art methods (f1-score $\le 0.97$). Not only does MulBot achieve excellent results in the binary classification task, but we also demonstrate its strengths in a novel and practically-relevant task: detecting and separating different botnets. In this multi-class classification task we achieve f1-score $= 0.96$. We conclude by estimating the importance of the different features used in our model and by evaluating MulBot's capability to generalize to new unseen bots, thus proposing a solution to the generalization deficiencies of supervised bot detectors.
The Objective Function: Science and Society in the Age of Machine Intelligence
Venue: arXiv cs.CY 2022
Year: 2022

Machine intelligence, or the use of complex computational and statistical practices to make predictions and classifications based on data representations of phenomena, has been applied to domains as disparate as criminal justice, commerce, medicine, media and the arts, mechanical engineering, among others. How has machine intelligence become able to glide so freely across, and to make such waves for, these domains? In this dissertation, I take up that question by ethnographically engaging with how the authority of machine learning has been constructed such that it can influence so many domains, and I investigate what the consequences are of it being able to do so. By examining the workplace practices of the applied machine learning researchers who produce machine intelligence, those they work with, and the artifacts they produce. The dissertation begins by arguing that machine intelligence proceeds from a naive form of empiricism with ties to positivist intellectual traditions of the 17th and 18th centuries. This naive empiricism eschews other forms of knowledge and theory formation in order for applied machine learning researchers to enact data performances that bring objects of analysis into existence as entities capable of being subjected to machine intelligence. By data performances, I mean generative enactments which bring into existence that which machine intelligence purports to analyze or describe. The enactment of data performances is analyzed as an agential cut into a representational field that produces both stable claims about the world and the interpretive frame in which those claims can hold true. The dissertation also examines how machine intelligence depends upon a range of accommodations from other institutions and organizations, from data collection and processing to organizational commitments to support the work of applied machine learning researchers.
Approximate sampling and estimation of partition functions using neural networks
Venue: arXiv cs.LG 2022
Year: 2022

We consider the closely related problems of sampling from a distribution known up to a normalizing constant, and estimating said normalizing constant. We show how variational autoencoders (VAEs) can be applied to this task. In their standard applications, VAEs are trained to fit data drawn from an intractable distribution. We invert the logic and train the VAE to fit a simple and tractable distribution, on the assumption of a complex and intractable latent distribution, specified up to normalization. This procedure constructs approximations without the use of training data or Markov chain Monte Carlo sampling. We illustrate our method on three examples: the Ising model, graph clustering, and ranking.
A Few Shot Multi-Representation Approach for N-gram Spotting in Historical Manuscripts
Venue: arXiv cs.CV 2022
Year: 2022

Despite recent advances in automatic text recognition, the performance remains moderate when it comes to historical manuscripts. This is mainly because of the scarcity of available labelled data to train the data-hungry Handwritten Text Recognition (HTR) models. The Keyword Spotting System (KWS) provides a valid alternative to HTR due to the reduction in error rate, but it is usually limited to a closed reference vocabulary. In this paper, we propose a few-shot learning paradigm for spotting sequences of a few characters (N-gram) that requires a small amount of labelled training data. We exhibit that recognition of important n-grams could reduce the system's dependency on vocabulary. In this case, an out-of-vocabulary (OOV) word in an input handwritten line image could be a sequence of n-grams that belong to the lexicon. An extensive experimental evaluation of our proposed multi-representation approach was carried out on a subset of Bentham's historical manuscript collections to obtain some really promising results in this direction.
Interactive Abstract Interpretation: Reanalyzing Whole Programs for Cheap
Venue: arXiv cs.PL 2022
Year: 2022

To put static program analysis at the fingertips of the software developer, we propose a framework for interactive abstract interpretation. While providing sound analysis results, abstract interpretation in general can be quite costly. To achieve quick response times, we incrementalize the analysis infrastructure, including postprocessing, without necessitating any modifications to the analysis specifications themselves. We rely on the local generic fixpoint engine TD, which dynamically tracks dependencies, while exploring the unknowns contributing to answering an initial query. Lazy invalidation is employed for analysis results affected by program change. Dedicated improvements support the incremental analysis of concurrency deficiencies such as data-races. The framework has been implemented for multithreaded C within the static analyzer Goblint, using MagpieBridge to relay findings to IDEs. We evaluate our implementation w.r.t. the yard sticks of response time and consistency: formerly proven invariants should be retained - when they are not affected by the change. The results indicate that with our approach, a reanalysis after small changes only takes a fraction of from-scratch analysis time, while most of the precision is retained. We also provide examples of program development highlighting the usability of the overall approach.
Learning from Mixed Datasets: A Monotonic Image Quality Assessment Model
Venue: arXiv cs.CV 2022
Year: 2022

Deep learning based image quality assessment (IQA) models usually learn to predict image quality from a single dataset, leading the model to overfit specific scenes. To account for this, mixed datasets training can be an effective way to enhance the generalization capability of the model. However, it is nontrivial to combine different IQA datasets, as their quality evaluation criteria, score ranges, view conditions, as well as subjects are usually not shared during the image quality annotation. In this paper, instead of aligning the annotations, we propose a monotonic neural network for IQA model learning with different datasets combined. In particular, our model consists of a dataset-shared quality regressor and several dataset-specific quality transformers. The quality regressor aims to obtain the perceptual qualities of each dataset while each quality transformer maps the perceptual qualities to the corresponding dataset annotations with their monotonicity maintained. The experimental results verify the effectiveness of the proposed learning strategy and our code is available at https://github.com/fzp0424/MonotonicIQA.
Change my Mind: Data Driven Estimate of Open-Mindedness from Political Discussions
Venue: arXiv cs.SI 2022
Year: 2022

One of the main dimensions characterizing the unfolding of opinion formation processes in social debates is the degree of open-mindedness of the involved population. Opinion dynamic modeling studies have tried to capture such a peculiar expression of individuals' personalities and relate it to emerging phenomena like polarization, radicalization, and ideology fragmentation. However, one of their major limitations lies in the strong assumptions they make on the initial distribution of such characteristics, often fixed so as to satisfy a normality hypothesis. Here we propose a data-driven methodology to estimate users' open-mindedness from online discussion data. Our analysis - focused on the political discussion taking place on Reddit during the first two years of the Trump presidency - unveils the existence of statistically diverse distributions of open-mindedness in annotated sub-populations (i.e., Republicans, Democrats, and Moderates/Neutrals). Moreover, such distributions appear to be stable across time and generated by individual users' behaviors that remain consistent and underdispersed.
Sample, Crop, Track: Self-Supervised Mobile 3D Object Detection for Urban Driving LiDAR
Venue: arXiv cs.CV 2022
Year: 2022

Deep learning has led to great progress in the detection of mobile (i.e. movement-capable) objects in urban driving scenes in recent years. Supervised approaches typically require the annotation of large training sets; there has thus been great interest in leveraging weakly, semi- or self-supervised methods to avoid this, with much success. Whilst weakly and semi-supervised methods require some annotation, self-supervised methods have used cues such as motion to relieve the need for annotation altogether. However, a complete absence of annotation typically degrades their performance, and ambiguities that arise during motion grouping can inhibit their ability to find accurate object boundaries. In this paper, we propose a new self-supervised mobile object detection approach called SCT. This uses both motion cues and expected object sizes to improve detection performance, and predicts a dense grid of 3D oriented bounding boxes to improve object discovery. We significantly outperform the state-of-the-art self-supervised mobile object detection method TCR on the KITTI tracking benchmark, and achieve performance that is within 30% of the fully supervised PV-RCNN++ method for IoUs <= 0.5.
Show, Interpret and Tell: Entity-aware Contextualised Image Captioning in Wikipedia
Venue: arXiv cs.CV 2022
Year: 2022

Humans exploit prior knowledge to describe images, and are able to adapt their explanation to specific contextual information, even to the extent of inventing plausible explanations when contextual information and images do not match. In this work, we propose the novel task of captioning Wikipedia images by integrating contextual knowledge. Specifically, we produce models that jointly reason over Wikipedia articles, Wikimedia images and their associated descriptions to produce contextualized captions. Particularly, a similar Wikimedia image can be used to illustrate different articles, and the produced caption needs to be adapted to a specific context, therefore allowing us to explore the limits of a model to adjust captions to different contextual information. A particular challenging task in this domain is dealing with out-of-dictionary words and Named Entities. To address this, we propose a pre-training objective, Masked Named Entity Modeling (MNEM), and show that this pretext task yields an improvement compared to baseline models. Furthermore, we verify that a model pre-trained with the MNEM objective in Wikipedia generalizes well to a News Captioning dataset. Additionally, we define two different test splits according to the difficulty of the captioning task. We offer insights on the role and the importance of each modality and highlight the limitations of our model. The code, models and data splits are publicly available at Upon acceptance.
SMTCE: A Social Media Text Classification Evaluation Benchmark and BERTology Models for Vietnamese
Venue: arXiv cs.CL 2022
Year: 2022

Text classification is a typical natural language processing or computational linguistics task with various interesting applications. As the number of users on social media platforms increases, data acceleration promotes emerging studies on Social Media Text Classification (SMTC) or social media text mining on these valuable resources. In contrast to English, Vietnamese, one of the low-resource languages, is still not concentrated on and exploited thoroughly. Inspired by the success of the GLUE, we introduce the Social Media Text Classification Evaluation (SMTCE) benchmark, as a collection of datasets and models across a diverse set of SMTC tasks. With the proposed benchmark, we implement and analyze the effectiveness of a variety of multilingual BERT-based models (mBERT, XLM-R, and DistilmBERT) and monolingual BERT-based models (PhoBERT, viBERT, vELECTRA, and viBERT4news) for tasks in the SMTCE benchmark. Monolingual models outperform multilingual models and achieve state-of-the-art results on all text classification tasks. It provides an objective assessment of multilingual and monolingual BERT-based models on the benchmark, which will benefit future studies about BERTology in the Vietnamese language.
Efficient Distribution Similarity Identification in Clustered Federated Learning via Principal Angles Between Client Data Subspaces
Venue: arXiv cs.LG 2022
Year: 2022

Clustered federated learning (FL) has been shown to produce promising results by grouping clients into clusters. This is especially effective in scenarios where separate groups of clients have significant differences in the distributions of their local data. Existing clustered FL algorithms are essentially trying to group together clients with similar distributions so that clients in the same cluster can leverage each other's data to better perform federated learning. However, prior clustered FL algorithms attempt to learn these distribution similarities indirectly during training, which can be quite time consuming as many rounds of federated learning may be required until the formation of clusters is stabilized. In this paper, we propose a new approach to federated learning that directly aims to efficiently identify distribution similarities among clients by analyzing the principal angles between the client data subspaces. Each client applies a truncated singular value decomposition (SVD) step on its local data in a single-shot manner to derive a small set of principal vectors, which provides a signature that succinctly captures the main characteristics of the underlying distribution. This small set of principal vectors is provided to the server so that the server can directly identify distribution similarities among the clients to form clusters. This is achieved by comparing the similarities of the principal angles between the client data subspaces spanned by those principal vectors. The approach provides a simple, yet effective clustered FL framework that addresses a broad range of data heterogeneity issues beyond simpler forms of Non-IIDness like label skews. Our clustered FL approach also enables convergence guarantees for non-convex objectives. Our code is available at https://github.com/MMorafah/PACFL.
Identification of Adaptive Driving Style Preference through Implicit Inputs in SAE L2 Vehicles
Venue: arXiv cs.HC 2022
Year: 2022

A key factor to optimal acceptance and comfort of automated vehicle features is the driving style. Mismatches between the automated and the driver preferred driving styles can make users take over more frequently or even disable the automation features. This work proposes identification of user driving style preference with multimodal signals, so the vehicle could match user preference in a continuous and automatic way. We conducted a driving simulator study with 36 participants and collected extensive multimodal data including behavioral, physiological, and situational data. This includes eye gaze, steering grip force, driving maneuvers, brake and throttle pedal inputs as well as foot distance from pedals, pupil diameter, galvanic skin response, heart rate, and situational drive context. Then, we built machine learning models to identify preferred driving styles, and confirmed that all modalities are important for the identification of user preference. This work paves the road for implicit adaptive driving styles on automated vehicles.
Algorithm-Agnostic Interpretations for Clustering
Venue: arXiv cs.LG 2022
Year: 2022

A clustering outcome for high-dimensional data is typically interpreted via post-processing, involving dimension reduction and subsequent visualization. This destroys the meaning of the data and obfuscates interpretations. We propose algorithm-agnostic interpretation methods to explain clustering outcomes in reduced dimensions while preserving the integrity of the data. The permutation feature importance for clustering represents a general framework based on shuffling feature values and measuring changes in cluster assignments through custom score functions. The individual conditional expectation for clustering indicates observation-wise changes in the cluster assignment due to changes in the data. The partial dependence for clustering evaluates average changes in cluster assignments for the entire feature space. All methods can be used with any clustering algorithm able to reassign instances through soft or hard labels. In contrast to common post-processing methods such as principal component analysis, the introduced methods maintain the original structure of the features.
Toy Models of Superposition
Venue: arXiv cs.LG 2022
Year: 2022

Neural networks often pack many unrelated concepts into a single neuron - a puzzling phenomenon known as 'polysemanticity' which makes interpretability much more challenging. This paper provides a toy model where polysemanticity can be fully understood, arising as a result of models storing additional sparse features in "superposition." We demonstrate the existence of a phase change, a surprising connection to the geometry of uniform polytopes, and evidence of a link to adversarial examples. We also discuss potential implications for mechanistic interpretability.