OpenRaiser/Intern-Atlas huggingface dataset:
Towards Effective Multi-Task Interaction for Entity-Relation Extraction: A Unified Framework with Selection Recurrent Network
Venue: arXiv cs.CL 2022
Year: 2022

Entity-relation extraction aims to jointly solve named entity recognition (NER) and relation extraction (RE). Recent approaches use either one-way sequential information propagation in a pipeline manner or two-way implicit interaction with a shared encoder. However, they still suffer from poor information interaction due to the gap between the different task forms of NER and RE, raising a controversial question whether RE is really beneficial to NER. Motivated by this, we propose a novel and unified cascade framework that combines the advantages of both sequential information propagation and implicit interaction. Meanwhile, it eliminates the gap between the two tasks by reformulating entity-relation extraction as unified span-extraction tasks. Specifically, we propose a selection recurrent network as a shared encoder to encode task-specific independent and shared representations and design two sequential information propagation strategies to realize the sequential information flow between NER and RE. Extensive experiments demonstrate that our approaches can achieve state-of-the-art results on two common benchmarks, ACE05 and SciERC, and effectively model the multi-task interaction, which realizes significant mutual benefits of NER and RE.
A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
Venue: arXiv cs.DS 2022
Year: 2022

The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap $2$-edge connected subgraphs. This has culminated in a $\frac{5}{3}$-approximation algorithm. However, the algorithm and its analysis are fairly involved and do not compare against the problem's well-known LP relaxation called the cut LP. In this paper, we propose a simple algorithm that, guided by an optimal solution to the cut LP, first selects a DFS tree and then finds a solution to MAP by computing an optimum augmentation of this tree. Using properties of extreme point solutions, we show that our algorithm always returns (in polynomial time) a better than $2$-approximation when compared to the cut LP. We thereby also obtain an improved upper bound on the integrality gap of this natural relaxation.
ViNTER: Image Narrative Generation with Emotion-Arc-Aware Transformer
Venue: arXiv cs.CV 2022
Year: 2022

Image narrative generation is a task to create a story from an image with a subjective viewpoint. Given the importance of the subjective feelings of writers, readers, and characters in storytelling, an image narrative generation method should consider human emotion. In this study, we propose a novel method of image narrative generation called ViNTER (Visual Narrative Transformer with Emotion arc Representation), which takes "emotion arc" as input to capture a sequence of emotional changes. Since emotion arcs represent the trajectory of emotional change, it is expected that we can include detailed information about the emotional changes in the story to the model. We present experimental results of both automatic and manual evaluations on the Image Narrative dataset and demonstrate the effectiveness of the proposed approach.
IF-City: Intelligible Fair City Planning to Measure, Explain and Mitigate Inequality
Venue: arXiv cs.HC 2022
Year: 2022

With the increasing pervasiveness of Artificial Intelligence (AI), many visual analytics tools have been proposed to examine fairness, but they mostly focus on data scientist users. Instead, tackling fairness must be inclusive and involve domain experts with specialized tools and workflows. Thus, domain-specific visualizations are needed for algorithmic fairness. Furthermore, while much work on AI fairness has focused on predictive decisions, less has been done for fair allocation and planning, which require human expertise and iterative design to integrate myriad constraints. We propose the Intelligible Fair Allocation (IF-Alloc) Framework that leverages explanations of causal attribution (Why), contrastive (Why Not) and counterfactual reasoning (What If, How To) to aid domain experts to assess and alleviate unfairness in allocation problems. We apply the framework to fair urban planning for designing cities that provide equal access to amenities and benefits for diverse resident types. Specifically, we propose an interactive visual tool, Intelligible Fair City Planner (IF-City), to help urban planners to perceive inequality across groups, identify and attribute sources of inequality, and mitigate inequality with automatic allocation simulations and constraint-satisfying recommendations. We demonstrate and evaluate the usage and usefulness of IF-City on a real neighborhood in New York City, US, with practicing urban planners from multiple countries, and discuss generalizing our findings, application, and framework to other use cases and applications of fair allocation.
A Unified Framework for Masked and Mask-Free Face Recognition via Feature Rectification
Venue: arXiv cs.CV 2022
Year: 2022

Face recognition under ideal conditions is now considered a well-solved problem with advances in deep learning. Recognizing faces under occlusion, however, still remains a challenge. Existing techniques often fail to recognize faces with both the mouth and nose covered by a mask, which is now very common under the COVID-19 pandemic. Common approaches to tackle this problem include 1) discarding information from the masked regions during recognition and 2) restoring the masked regions before recognition. Very few works considered the consistency between features extracted from masked faces and from their mask-free counterparts. This resulted in models trained for recognizing masked faces often showing degraded performance on mask-free faces. In this paper, we propose a unified framework, named Face Feature Rectification Network (FFR-Net), for recognizing both masked and mask-free faces alike. We introduce rectification blocks to rectify features extracted by a state-of-the-art recognition model, in both spatial and channel dimensions, to minimize the distance between a masked face and its mask-free counterpart in the rectified feature space. Experiments show that our unified framework can learn a rectified feature space for recognizing both masked and mask-free faces effectively, achieving state-of-the-art results. Project code: https://github.com/haoosz/FFR-Net
GuaranTEE: Introducing Control-Flow Attestation for Trusted Execution Environments
Venue: arXiv cs.CR 2022
Year: 2022

The majority of cloud providers offers users the possibility to deploy Trusted Execution Environments (TEEs) to protect their data and processes from high privileged adversaries. This offer is intended to address concerns of users when moving critical tasks into the cloud. However, TEEs only allow to attest the integrity of the environment at launch-time. To also enable the attestation of a TEE's integrity at run-time, we present GuaranTEE. GuaranTEE uses control-flow attestation to ensure the integrity of a service running within a TEE. By additionally placing all components of GuaranTEE in TEEs, we are able to not only detect a compromised target, but are also able to protect ourselves from malicious administrators. We show the practicability of GuaranTEE by providing a detailed performance and security evaluation of our prototype based on Intel SGX in Microsoft Azure. Our evaluation shows that the need to transfer information between TEEs and the additional verification process add considerable overhead under high CPU load. Yet, we are able to reduce this overhead by securely caching collected information and by performing the analysis in parallel to executing the application. In summary, our results show that GuaranTEE provides a practical solution for cloud users focused on protecting the integrity of their data and processes at run-time.
The Membership Problem for Hypergeometric Sequences with Rational Parameters
Venue: arXiv cs.LO 2022
Year: 2022

We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence $\langle u_n \rangle_{n=0}^\infty$ of rational numbers and a target $t \in \mathbb{Q}$, decide whether $t$ occurs in the sequence. We show decidability of this problem under the assumption that in the defining recurrence $p(n)u_{n}=q(n)u_{n-1}$, the roots of the polynomials $p(x)$ and $q(x)$ are all rational numbers. Our proof relies on bounds on the density of primes in arithmetic progressions. We also observe a relationship between the decidability of the Membership problem (and variants) and the Rohrlich-Lang conjecture in transcendence theory.
A Survey on Image Deblurring
Venue: arXiv cs.CV 2022
Year: 2022

With the improvement of social life quality and the real needs of daily work, images are more and more all around us. Image blurring due to camera shake, human movement, etc. has become the key to affecting image quality. How to remove image blur and restore clear image has gradually become an important research direction in the field of computer vision. After more than half a century of unremitting efforts, the majority of scientific and technological workers have made fruitful progress in image deblurring. This article reviews the work of image deblurring and specifically introduces more classic image deblurring methods, which is helpful to understand current research and look forward to future trends. This article reviews the traditional image deblurring methods and depth-represented image deblurring methods, and comprehensively classifies and introduces the corresponding technical methods. This review can provide some guidance for researchers in the field of image deblurring, and at the same time facilitate their subsequent study and research.
Beyond the Policy Gradient Theorem for Efficient Policy Updates in Actor-Critic Algorithms
Venue: arXiv cs.LG 2022
Year: 2022

In Reinforcement Learning, the optimal action at a given state is dependent on policy decisions at subsequent states. As a consequence, the learning targets evolve with time and the policy optimization process must be efficient at unlearning what it previously learnt. In this paper, we discover that the policy gradient theorem prescribes policy updates that are slow to unlearn because of their structural symmetry with respect to the value target. To increase the unlearning speed, we study a novel policy update: the gradient of the cross-entropy loss with respect to the action maximizing $q$, but find that such updates may lead to a decrease in value. Consequently, we introduce a modified policy update devoid of that flaw, and prove its guarantees of convergence to global optimality in $\mathcal{O}(t^{-1})$ under classic assumptions. Further, we assess standard policy updates and our cross-entropy policy updates along six analytical dimensions. Finally, we empirically validate our theoretical findings.
Robust Multi-Objective Bayesian Optimization Under Input Noise
Venue: arXiv cs.LG 2022
Year: 2022

Bayesian optimization (BO) is a sample-efficient approach for tuning design parameters to optimize expensive-to-evaluate, black-box performance metrics. In many manufacturing processes, the design parameters are subject to random input noise, resulting in a product that is often less performant than expected. Although BO methods have been proposed for optimizing a single objective under input noise, no existing method addresses the practical scenario where there are multiple objectives that are sensitive to input perturbations. In this work, we propose the first multi-objective BO method that is robust to input noise. We formalize our goal as optimizing the multivariate value-at-risk (MVaR), a risk measure of the uncertain objectives. Since directly optimizing MVaR is computationally infeasible in many settings, we propose a scalable, theoretically-grounded approach for optimizing MVaR using random scalarizations. Empirically, we find that our approach significantly outperforms alternative methods and efficiently identifies optimal robust designs that will satisfy specifications across multiple metrics with high probability.
Deep Generative model with Hierarchical Latent Factors for Time Series Anomaly Detection
Venue: arXiv cs.LG 2022
Year: 2022

Multivariate time series anomaly detection has become an active area of research in recent years, with Deep Learning models outperforming previous approaches on benchmark datasets. Among reconstruction-based models, most previous work has focused on Variational Autoencoders and Generative Adversarial Networks. This work presents DGHL, a new family of generative models for time series anomaly detection, trained by maximizing the observed likelihood by posterior sampling and alternating back-propagation. A top-down Convolution Network maps a novel hierarchical latent space to time series windows, exploiting temporal dynamics to encode information efficiently. Despite relying on posterior sampling, it is computationally more efficient than current approaches, with up to 10x shorter training times than RNN based models. Our method outperformed current state-of-the-art models on four popular benchmark datasets. Finally, DGHL is robust to variable features between entities and accurate even with large proportions of missing values, settings with increasing relevance with the advent of IoT. We demonstrate the superior robustness of DGHL with novel occlusion experiments in this literature. Our code is available at https://github.com/cchallu/dghl.
Shifting Trends of COVID-19 Tweet Sentiment with Respect to Voting Preferences in the 2020 Election Year of the United States
Venue: arXiv cs.CL 2022
Year: 2022

COVID-19 related policies were extensively politicized during the 2020 election year of the United States, resulting in polarizing viewpoints. Twitter users were particularly engaged during the 2020 election year. Here we investigated whether COVID-19 related tweets were associated with the overall election results at the state level during the period leading up to the election day. We observed weak correlations between the average sentiment of COVID-19 related tweets and popular votes in two-week intervals, and the trends gradually become opposite. We then compared the average sentiments of COVID-19 related tweets between states called in favor of Republican (red states) or Democratic parties (blue states). We found that at the beginning of lockdowns sentiments in the blue states were much more positive than those in the red states. However, sentiments in the red states gradually become more positive during the summer of 2020 and persisted until the election day.
EvoKG: Jointly Modeling Event Time and Network Structure for Reasoning over Temporal Knowledge Graphs
Venue: arXiv cs.LG 2022
Year: 2022

How can we perform knowledge reasoning over temporal knowledge graphs (TKGs)? TKGs represent facts about entities and their relations, where each fact is associated with a timestamp. Reasoning over TKGs, i.e., inferring new facts from time-evolving KGs, is crucial for many applications to provide intelligent services. However, despite the prevalence of real-world data that can be represented as TKGs, most methods focus on reasoning over static knowledge graphs, or cannot predict future events. In this paper, we present a problem formulation that unifies the two major problems that need to be addressed for an effective reasoning over TKGs, namely, modeling the event time and the evolving network structure. Our proposed method EvoKG jointly models both tasks in an effective framework, which captures the ever-changing structural and temporal dynamics in TKGs via recurrent event modeling, and models the interactions between entities based on the temporal neighborhood aggregation framework. Further, EvoKG achieves an accurate modeling of event time, using flexible and efficient mechanisms based on neural density estimation. Experiments show that EvoKG outperforms existing methods in terms of effectiveness (up to 77% and 116% more accurate time and link prediction) and efficiency.
Survey of Big Data sizes in 2021
Venue: arXiv cs.DL 2022
Year: 2022

The modern increase in data production is driven by multiple factors, and several stakeholders from various sectors contribute to it. Although drawing a comparison of the sizes at stake for different big data players is hard due to the lack of official data, this report tries to reconstruct the yearly orders of magnitude generated by some of the most important organizations by mining several online sources. The estimation is based on retrieving meaningful unitary data production measures for each of the big data sources considered, and the yearly amounts are then obtained by conjecturing reasonable per-unit sizes. The final result is summarized in the form of a bubble plot.
On the Role of Channel Capacity in Learning Gaussian Mixture Models
Venue: arXiv cs.IT 2022
Year: 2022

This paper studies the sample complexity of learning the $k$ unknown centers of a balanced Gaussian mixture model (GMM) in $\mathbb{R}^d$ with spherical covariance matrix $σ^2\mathbf{I}$. In particular, we are interested in the following question: what is the maximal noise level $σ^2$, for which the sample complexity is essentially the same as when estimating the centers from labeled measurements? To that end, we restrict attention to a Bayesian formulation of the problem, where the centers are uniformly distributed on the sphere $\sqrt{d}\mathcal{S}^{d-1}$. Our main results characterize the exact noise threshold $σ^2$ below which the GMM learning problem, in the large system limit $d,k\to\infty$, is as easy as learning from labeled observations, and above which it is substantially harder. The threshold occurs at $\frac{\log k}{d} = \frac12\log\left( 1+\frac{1}{σ^2} \right)$, which is the capacity of the additive white Gaussian noise (AWGN) channel. Thinking of the set of $k$ centers as a code, this noise threshold can be interpreted as the largest noise level for which the error probability of the code over the AWGN channel is small. Previous works on the GMM learning problem have identified the minimum distance between the centers as a key parameter in determining the statistical difficulty of learning the corresponding GMM. While our results are only proved for GMMs whose centers are uniformly distributed over the sphere, they hint that perhaps it is the decoding error probability associated with the center constellation as a channel code that determines the statistical difficulty of learning the corresponding GMM, rather than just the minimum distance.
Rankings in the Zerkani network by a game theoretical approach
Venue: arXiv cs.SI 2022
Year: 2022

This paper introduces the Banzhaf and Banzhaf-Owen values as novel centrality measures for ranking terrorists in a network. This new approach let integrate the complete topology (i.e. nodes and edges) of the network and a coalitional structure on the nodes of the network. More precisely, the characteristics of the nodes (e.g., terrorists) of the network and their possible relationships (e.g., types of communication links), as well as coalitional information (e.g. level of hierarchies) independent of the network. First, for both centrality measures, we provide approximation algorithms and the corresponding R-codes. Second, as illustration, we rank the members of the Zerkani network, responsible for the attacks in Paris (2015) and Brussels (2016). Finally, we give a comparison between the rankings established by Banzhaf and Banzhaf-Owen and the rankings obtained when using the Shapley value (cf. Hamers et al., 2019) and the Owen value as centrality measures
Bohemian Matrix Geometry
Venue: arXiv cs.SC 2022
Year: 2022

A Bohemian matrix family is a set of matrices all of whose entries are drawn from a fixed, usually discrete and hence bounded, subset of a field of characteristic zero. Originally these were integers -- hence the name, from the acronym BOunded HEight Matrix of Integers (BOHEMI) -- but other kinds of entries are also interesting. Some kinds of questions about Bohemian matrices can be answered by numerical computation, but sometimes exact computation is better. In this paper we explore some Bohemian families (symmetric, upper Hessenberg, or Toeplitz) computationally, and answer some open questions posed about the distributions of eigenvalue densities.
Predictability and Surprise in Large Generative Models
Venue: arXiv cs.CY 2022
Year: 2022

Large-scale pre-training has recently emerged as a technique for creating capable, general purpose, generative models such as GPT-3, Megatron-Turing NLG, Gopher, and many others. In this paper, we highlight a counterintuitive property of such models and discuss the policy implications of this property. Namely, these generative models have an unusual combination of predictable loss on a broad training distribution (as embodied in their "scaling laws"), and unpredictable specific capabilities, inputs, and outputs. We believe that the high-level predictability and appearance of useful capabilities drives rapid development of such models, while the unpredictable qualities make it difficult to anticipate the consequences of model deployment. We go through examples of how this combination can lead to socially harmful behavior with examples from the literature and real world observations, and we also perform two novel experiments to illustrate our point about harms from unpredictability. Furthermore, we analyze how these conflicting properties combine to give model developers various motivations for deploying these models, and challenges that can hinder deployment. We conclude with a list of possible interventions the AI community may take to increase the chance of these models having a beneficial impact. We intend this paper to be useful to policymakers who want to understand and regulate AI systems, technologists who care about the potential policy impact of their work, and academics who want to analyze, critique, and potentially develop large generative models.
Russian SuperGLUE 1.1: Revising the Lessons not Learned by Russian NLP models
Venue: arXiv cs.CL 2022
Year: 2022

In the last year, new neural architectures and multilingual pre-trained models have been released for Russian, which led to performance evaluation problems across a range of language understanding tasks. This paper presents Russian SuperGLUE 1.1, an updated benchmark styled after GLUE for Russian NLP models. The new version includes a number of technical, user experience and methodological improvements, including fixes of the benchmark vulnerabilities unresolved in the previous version: novel and improved tests for understanding the meaning of a word in context (RUSSE) along with reading comprehension and common sense reasoning (DaNetQA, RuCoS, MuSeRC). Together with the release of the updated datasets, we improve the benchmark toolkit based on \texttt{jiant} framework for consistent training and evaluation of NLP-models of various architectures which now supports the most recent models for Russian. Finally, we provide the integration of Russian SuperGLUE with a framework for industrial evaluation of the open-source models, MOROCCO (MOdel ResOurCe COmparison), in which the models are evaluated according to the weighted average metric over all tasks, the inference speed, and the occupied amount of RAM. Russian SuperGLUE is publicly available at https://russiansuperglue.com/.