OpenRaiser/Intern-Atlas huggingface dataset:
The Influence of the Other-Race Effect on Susceptibility to Face Morphing Attacks
Venue: arXiv cs.CV 2022
Year: 2022

Facial morphs created between two identities resemble both of the faces used to create the morph. Consequently, humans and machines are prone to mistake morphs made from two identities for either of the faces used to create the morph. This vulnerability has been exploited in "morph attacks" in security scenarios. Here, we asked whether the "other-race effect" (ORE) -- the human advantage for identifying own- vs. other-race faces -- exacerbates morph attack susceptibility for humans. We also asked whether face-identification performance in a deep convolutional neural network (DCNN) is affected by the race of morphed faces. Caucasian (CA) and East-Asian (EA) participants performed a face-identity matching task on pairs of CA and EA face images in two conditions. In the morph condition, different-identity pairs consisted of an image of identity "A" and a 50/50 morph between images of identity "A" and "B". In the baseline condition, morphs of different identities never appeared. As expected, morphs were identified mistakenly more often than original face images. Moreover, CA participants showed an advantage for CA faces in comparison to EA faces (a partial ORE). Of primary interest, morph identification was substantially worse for cross-race faces than for own-race faces. Similar to humans, the DCNN performed more accurately for original face images than for morphed image pairs. Notably, the deep network proved substantially more accurate than humans in both cases. The results point to the possibility that DCNNs might be useful for improving face identification accuracy when morphed faces are presented. They also indicate the significance of the ORE in morph attack susceptibility in applied settings.
MaxSAT with Absolute Value Functions: A Parameterized Perspective
Venue: arXiv cs.CC 2022
Year: 2022

The natural generalization of the Boolean satisfiability problem to optimization problems is the task of determining the maximum number of clauses that can simultaneously be satisfied in a propositional formula in conjunctive normal form. In the weighted maximum satisfiability problem each clause has a positive weight and one seeks an assignment of maximum weight. The literature almost solely considers the case of positive weights. While the general case of the problem is only restricted slightly by this constraint, many special cases become trivial in the absence of negative weights. In this work we study the problem with negative weights and observe that the problem becomes computationally harder - which we formalize from a parameterized perspective in the sense that various variations of the problem become W[1]-hard if negative weights are present. Allowing negative weights also introduces new variants of the problem: Instead of maximizing the sum of weights of satisfied clauses, we can maximize the absolute value of that sum. This turns out to be surprisingly expressive even restricted to monotone formulas in disjunctive normal form with at most two literals per clause. In contrast to the versions without the absolute value, however, we prove that these variants are fixed-parameter tractable. As technical contribution we present a kernelization for an auxiliary problem on hypergraphs in which we seek, given an edge-weighted hypergraph, an induced subgraph that maximizes the absolute value of the sum of edge-weights.
Optimal Closeness Testing of Discrete Distributions Made (Complex) Simple
Venue: arXiv cs.DS 2022
Year: 2022

In this note, we revisit the recent work of Diakonikolas, Gouleakis, Kane, Peebles, and Price (2021), and provide an alternative proof of their main result. Our argument does not rely on any specific property of Poisson random variables (such as stability and divisibility) nor on any "clever trick," but instead on an identity relating the expectation of the absolute value of any random variable to the integral of its characteristic function: \[ \mathbb{E}[|X|] = \frac{2}π\int_0^\infty \frac{1-\Re(\mathbb{E}[e^{i tX}])}{t^2}\, dt \] Our argument, while not devoid of technical aspects, is arguably conceptually simpler and more general; and we hope this technique can find additional applications in distribution testing.
Advantages of maintaining a multi-task project-specific bot: an experience report
Venue: arXiv cs.SE 2022
Year: 2022

Bots are becoming a popular method for automating basic everyday tasks in many software projects. This is true in particular because of the availability of many off-the-shelf task-specific bots that teams can quickly adopt (which are sometimes completed with additional task-specific custom bots). Based on our experience in the Coq project, where we have developed and maintained a multi-task project-specific bot, we argue that this alternative approach to project automation should receive more attention because it strikes a good balance between productivity and adaptibility. In this article, we describe the kind of automation that our bot implements, what advantages we have gained by maintaining a project-specific bot, and the technology and architecture choices that have made it possible. We draw conclusions that should generalize to other medium-sized software teams willing to invest in project automation without disrupting their workflows.
Plug-and-Play Adaptation for Continuously-updated QA
Venue: arXiv cs.CL 2022
Year: 2022

Language models (LMs) have shown great potential as implicit knowledge bases (KBs). And for their practical use, knowledge in LMs need to be updated periodically. However, existing tasks to assess LMs' efficacy as KBs do not adequately consider multiple large-scale updates. To this end, we first propose a novel task--Continuously-updated QA (CuQA)--in which multiple large-scale updates are made to LMs, and the performance is measured with respect to the success in adding and updating knowledge while retaining existing knowledge. We then present LMs with plug-in modules that effectively handle the updates. Experiments conducted on zsRE QA and NQ datasets show that our method outperforms existing approaches. We find that our method is 4x more effective in terms of updates/forgets ratio, compared to a fine-tuning baseline.
Machines of finite depth: towards a formalization of neural networks
Venue: arXiv cs.LG 2022
Year: 2022

We provide a unifying framework where artificial neural networks and their architectures can be formally described as particular cases of a general mathematical construction--machines of finite depth. Unlike neural networks, machines have a precise definition, from which several properties follow naturally. Machines of finite depth are modular (they can be combined), efficiently computable and differentiable. The backward pass of a machine is again a machine and can be computed without overhead using the same procedure as the forward pass. We prove this statement theoretically and practically, via a unified implementation that generalizes several classical architectures--dense, convolutional, and recurrent neural networks with a rich shortcut structure--and their respective backpropagation rules.
Supervised Contrastive CSI Representation Learning for Massive MIMO Positioning
Venue: arXiv cs.IT 2022
Year: 2022

Similarity metric is crucial for massive MIMO positioning utilizing channel state information~(CSI). In this letter, we propose a novel massive MIMO CSI similarity learning method via deep convolutional neural network~(DCNN) and contrastive learning. A contrastive loss function is designed considering multiple positive and negative CSI samples drawn from a training dataset. The DCNN encoder is trained using the loss so that positive samples are mapped to points close to the anchor's encoding, while encodings of negative samples are kept away from the anchor's in the representation space. Evaluation results of fingerprint-based positioning on a real-world CSI dataset show that the learned similarity metric improves positioning accuracy significantly compared with other known state-of-the-art methods.
Affine Frequency Division Multiplexing for Next Generation Wireless Communications
Venue: arXiv cs.IT 2022
Year: 2022

Affine Frequency Division Multiplexing (AFDM), a new chirp-based multicarrier waveform for high mobility communications, is introduced here. AFDM is based on discrete affine Fourier transform (DAFT), a generalization of discrete Fourier transform, which is characterized by two parameters that can be adapted to better cope with doubly dispersive channels. First, we derive the explicit input-output relation in the DAFT domain showing the effect of AFDM parameters in the input-output relation. Second, we show how the DAFT parameters underlying AFDM have to be set so that the resulting DAFT domain impulse response conveys a full delay-Doppler representation of the channel. Then, we show analytically that AFDM can achieve full diversity in doubly dispersive channels, where full diversity refers to the number of multipath components separable in either the delay or the Doppler domain, due to its full delay-Doppler representation. Furthermore, we present a low complexity detection method taking advantage of zero-padding. We also propose an embedded pilot-aided channel estimation scheme for AFDM, in which both channel estimation and data detection are performed within the same AFDM frame. Finally, simulations corroborate the validity of our analytical results and show the significant performance gains of AFDM over state-of-the-art multicarrier schemes in high mobility scenarios.
Detecting Backdoor Poisoning Attacks on Deep Neural Networks by Heatmap Clustering
Venue: arXiv cs.LG 2022
Year: 2022

Predicitions made by neural networks can be fraudulently altered by so-called poisoning attacks. A special case are backdoor poisoning attacks. We study suitable detection methods and introduce a new method called Heatmap Clustering. There, we apply a $k$-means clustering algorithm on heatmaps produced by the state-of-the-art explainable AI method Layer-wise relevance propagation. The goal is to separate poisoned from un-poisoned data in the dataset. We compare this method with a similar method, called Activation Clustering, which also uses $k$-means clustering but applies it on the activation of certain hidden layers of the neural network as input. We test the performance of both approaches for standard backdoor poisoning attacks, label-consistent poisoning attacks and label-consistent poisoning attacks with reduced amplitude stickers. We show that Heatmap Clustering consistently performs better than Activation Clustering. However, when considering label-consistent poisoning attacks, the latter method also yields good detection performance.
Spending Privacy Budget Fairly and Wisely
Venue: arXiv cs.LG 2022
Year: 2022

Differentially private (DP) synthetic data generation is a practical method for improving access to data as a means to encourage productive partnerships. One issue inherent to DP is that the "privacy budget" is generally "spent" evenly across features in the data set. This leads to good statistical parity with the real data, but can undervalue the conditional probabilities and marginals that are critical for predictive quality of synthetic data. Further, loss of predictive quality may be non-uniform across the data set, with subsets that correspond to minority groups potentially suffering a higher loss. In this paper, we develop ensemble methods that distribute the privacy budget "wisely" to maximize predictive accuracy of models trained on DP data, and "fairly" to bound potential disparities in accuracy across groups and reduce inequality. Our methods are based on the insights that feature importance can inform how privacy budget is allocated, and, further, that per-group feature importance and fairness-related performance objectives can be incorporated in the allocation. These insights make our methods tunable to social contexts, allowing data owners to produce balanced synthetic data for predictive analysis.
We're Not Gonna Break It! Consistency-Preserving Operators for Efficient Product Line Configuration
Venue: arXiv cs.SE 2022
Year: 2022

When configuring a software product line, finding a good trade-off between multiple orthogonal quality concerns is a challenging multi-objective optimisation problem. State-of-the-art solutions based on search-based techniques create invalid configurations in intermediate steps, requiring additional repair actions that reduce the efficiency of the search. In this work, we introduce consistency-preserving configuration operators (CPCOs)--genetic operators that maintain valid configurations throughout the entire search. CPCOs bundle coherent sets of changes: the activation or deactivation of a particular feature together with other (de)activations that are needed to preserve validity. In our evaluation, our instantiation of the IBEA algorithm with CPCOs outperforms two state-of-the-art tools for optimal product line configuration in terms of both speed and solution quality. The improvements are especially pronounced in large product lines with thousands of features.
A Bayesian Approach To Graph Partitioning
Venue: arXiv cs.LG 2022
Year: 2022

A new algorithm based on bayesian inference for learning local graph conductance based on Gaussian Process(GP) is given that uses advanced MCMC convergence ideas to create a scalable and fast algorithm for convergence to stationary distribution which is provided to learn the bahavior of conductance when traversing the indirected weighted graph. First metric embedding is used to represent the vertices of the graph. Then, uniform induced conductance is calculated for training points. Finally, in the learning step, a gaussian process is used to approximate the uniform induced conductance. MCMC is used to measure uncertainty of estimated hyper-parameters.
Learning to Transfer Role Assignment Across Team Sizes
Venue: arXiv cs.LG 2022
Year: 2022

Multi-agent reinforcement learning holds the key for solving complex tasks that demand the coordination of learning agents. However, strong coordination often leads to expensive exploration over the exponentially large state-action space. A powerful approach is to decompose team works into roles, which are ideally assigned to agents with the relevant skills. Training agents to adaptively choose and play emerging roles in a team thus allows the team to scale to complex tasks and quickly adapt to changing environments. These promises, however, have not been fully realised by current role-based multi-agent reinforcement learning methods as they assume either a pre-defined role structure or a fixed team size. We propose a framework to learn role assignment and transfer across team sizes. In particular, we train a role assignment network for small teams by demonstration and transfer the network to larger teams, which continue to learn through interaction with the environment. We demonstrate that re-using the role-based credit assignment structure can foster the learning process of larger reinforcement learning teams to achieve tasks requiring different roles. Our proposal outperforms competing techniques in enriched role-enforcing Prey-Predator games and in new scenarios in the StarCraft II Micro-Management benchmark.
Towards a Green Quotient for Software Projects
Venue: arXiv cs.SE 2022
Year: 2022

As sustainability takes center stage across businesses, green and energy-efficient choices are more crucial than ever. While it is becoming increasingly evident that software and the software industry are substantial and rapidly evolving contributors to carbon emissions, there is a dearth of approaches to create actionable awareness about this during the software development lifecycle (SDLC). Can software teams comprehend how green are their projects? Here we provide an industry perspective on why this is a challenging and worthy problem that needs to be addressed. We also outline an approach to quickly gauge the "greenness" of a software project based on the choices made across different SDLC dimensions and present the initial encouraging feedback this approach has received.
NLU++: A Multi-Label, Slot-Rich, Generalisable Dataset for Natural Language Understanding in Task-Oriented Dialogue
Venue: arXiv cs.CL 2022
Year: 2022

We present NLU++, a novel dataset for natural language understanding (NLU) in task-oriented dialogue (ToD) systems, with the aim to provide a much more challenging evaluation environment for dialogue NLU models, up to date with the current application and industry requirements. NLU++ is divided into two domains (BANKING and HOTELS) and brings several crucial improvements over current commonly used NLU datasets. 1) NLU++ provides fine-grained domain ontologies with a large set of challenging multi-intent sentences, introducing and validating the idea of intent modules that can be combined into complex intents that convey complex user goals, combined with finer-grained and thus more challenging slot sets. 2) The ontology is divided into domain-specific and generic (i.e., domain-universal) intent modules that overlap across domains, promoting cross-domain reusability of annotated examples. 3) The dataset design has been inspired by the problems observed in industrial ToD systems, and 4) it has been collected, filtered and carefully annotated by dialogue NLU experts, yielding high-quality annotated data. Finally, we benchmark a series of current state-of-the-art NLU models on NLU++; the results demonstrate the challenging nature of the dataset, especially in low-data regimes, the validity of `intent modularisation', and call for further research on ToD NLU.
Attention Consistency on Visual Corruptions for Single-Source Domain Generalization
Venue: arXiv cs.CV 2022
Year: 2022

Generalizing visual recognition models trained on a single distribution to unseen input distributions (i.e. domains) requires making them robust to superfluous correlations in the training set. In this work, we achieve this goal by altering the training images to simulate new domains and imposing consistent visual attention across the different views of the same sample. We discover that the first objective can be simply and effectively met through visual corruptions. Specifically, we alter the content of the training images using the nineteen corruptions of the ImageNet-C benchmark and three additional transformations based on Fourier transform. Since these corruptions preserve object locations, we propose an attention consistency loss to ensure that class activation maps across original and corrupted versions of the same training sample are aligned. We name our model Attention Consistency on Visual Corruptions (ACVC). We show that ACVC consistently achieves the state of the art on three single-source domain generalization benchmarks, PACS, COCO, and the large-scale DomainNet.
Worst-Case Dynamic Power Distribution Network Noise Prediction Using Convolutional Neural Network
Venue: arXiv cs.LG 2022
Year: 2022

Worst-case dynamic PDN noise analysis is an essential step in PDN sign-off to ensure the performance and reliability of chips. However, with the growing PDN size and increasing scenarios to be validated, it becomes very time- and resource-consuming to conduct full-stack PDN simulation to check the worst-case noise for different test vectors. Recently, various works have proposed machine learning based methods for supply noise prediction, many of which still suffer from large training overhead, inefficiency, or non-scalability. Thus, this paper proposed an efficient and scalable framework for the worst-case dynamic PDN noise prediction. The framework first reduces the spatial and temporal redundancy in the PDN and input current vector, and then employs efficient feature extraction as well as a novel convolutional neural network architecture to predict the worst-case dynamic PDN noise. Experimental results show that the proposed framework consistently outperforms the commercial tool and the state-of-the-art machine learning method with only 0.63-1.02% mean relative error and 25-69$\times$ speedup.
Transitivity on subclasses of bipartite graphs
Venue: arXiv cs.DM 2022
Year: 2022

Let $G=(V, E)$ be a graph where $V$ and $E$ are the vertex and edge set, respectively. For two disjoint subsets $A$ and $B$, we say $A$ dominates $B$ if every vertex of $B$ is adjacent to at least one vertex of $A$. A vertex partition $π= \{V_1, V_2, \ldots, V_k\}$ of $G$ is called a \emph{transitive $k$-partition} if $V_i$ dominates $V_j$ for all $i,j$ where $1\leq i<j\leq k$. The maximum integer $k$ for which the above partition exists is called \emph{transitivity} of $G$ and it is denoted by $Tr(G)$. The \textsc{Maximum Transitivity Problem} is to find a transitive partition of a given graph with the maximum number of partitions. It was known that the decision version of \textsc{Maximum Transitivity Problem} is NP-complete for general graphs, which was proved by Hedetniemi et al. [Iterated colorings of graphs, \emph{Discrete Mathematics}, 278, 2004]. This paper first strengthens the NP-completeness result by showing that this problem remains NP-complete for perfect elimination bipartite graphs. On the other hand, we propose a linear-time algorithm for finding the transitivity of a given bipartite chain graph. We then characterize graphs with transitivity at least $t$ for any integer $t$. This result answers two open questions posed by J. T. Hedetniemi and S. T. Hedetniemi [The transitivity of a graph, \emph{J. Combin. Math. Combin. Comput}, 104, 2018].
FedShuffle: Recipes for Better Use of Local Work in Federated Learning
Venue: arXiv cs.LG 2022
Year: 2022

The practice of applying several local updates before aggregation across clients has been empirically shown to be a successful approach to overcoming the communication bottleneck in Federated Learning (FL). Such methods are usually implemented by having clients perform one or more epochs of local training per round while randomly reshuffling their finite dataset in each epoch. Data imbalance, where clients have different numbers of local training samples, is ubiquitous in FL applications, resulting in different clients performing different numbers of local updates in each round. In this work, we propose a general recipe, FedShuffle, that better utilizes the local updates in FL, especially in this regime encompassing random reshuffling and heterogeneity. FedShuffle is the first local update method with theoretical convergence guarantees that incorporates random reshuffling, data imbalance, and client sampling - features that are essential in large-scale cross-device FL. We present a comprehensive theoretical analysis of FedShuffle and show, both theoretically and empirically, that it does not suffer from the objective function mismatch that is present in FL methods that assume homogeneous updates in heterogeneous FL setups, such as FedAvg (McMahan et al., 2017). In addition, by combining the ingredients above, FedShuffle improves upon FedNova (Wang et al., 2020), which was previously proposed to solve this mismatch. Similar to Mime (Karimireddy et al., 2020), we show that FedShuffle with momentum variance reduction (Cutkosky & Orabona, 2019) improves upon non-local methods under a Hessian similarity assumption.