OpenRaiser/Intern-Atlas huggingface dataset:
Fairness via In-Processing in the Over-parameterized Regime: A Cautionary Tale
Venue: arXiv cs.LG 2022
Year: 2022

The success of DNNs is driven by the counter-intuitive ability of over-parameterized networks to generalize, even when they perfectly fit the training data. In practice, test error often continues to decrease with increasing over-parameterization, referred to as double descent. This allows practitioners to instantiate large models without having to worry about over-fitting. Despite its benefits, however, prior work has shown that over-parameterization can exacerbate bias against minority subgroups. Several fairness-constrained DNN training methods have been proposed to address this concern. Here, we critically examine MinDiff, a fairness-constrained training procedure implemented within TensorFlow's Responsible AI Toolkit, that aims to achieve Equality of Opportunity. We show that although MinDiff improves fairness for under-parameterized models, it is likely to be ineffective in the over-parameterized regime. This is because an overfit model with zero training loss is trivially group-wise fair on training data, creating an "illusion of fairness," thus turning off the MinDiff optimization (this will apply to any disparity-based measures which care about errors or accuracy. It won't apply to demographic parity). Within specified fairness constraints, under-parameterized MinDiff models can even have lower error compared to their over-parameterized counterparts (despite baseline over-parameterized models having lower error). We further show that MinDiff optimization is very sensitive to choice of batch size in the under-parameterized regime. Thus, fair model training using MinDiff requires time-consuming hyper-parameter searches. Finally, we suggest using previously proposed regularization techniques, viz. L2, early stopping and flooding in conjunction with MinDiff to train fair over-parameterized models.
Multiple Targets Directed Greybox Fuzzing
Venue: arXiv cs.CR 2022
Year: 2022

Directed greybox fuzzing (DGF) can quickly discover or reproduce bugs in programs by seeking to reach a program location or explore some locations in order. However, due to their static stage division and coarse-grained energy scheduling, prior DGF tools perform poorly when facing multiple target locations (targets for short). In this paper, we present multiple targets directed greybox fuzzing which aims to reach multiple programs locations in a fuzzing campaign. Specifically, we propose a novel strategy to adaptively coordinate exploration and exploitation stages, and a novel energy scheduling strategy by considering more relations between seeds and target locations. We implement our approaches in a tool called LeoFuzz and evaluate it on crash reproduction, true positives verification, and vulnerability exposure in real-world programs. Experimental results show that LeoFuzz outperforms six state-of-the-art fuzzers, i.e., QYSM, AFLGo, Lolly, Berry, Beacon and WindRanger in terms of effectiveness and efficiency. Moreover, LeoFuzz has detected 23 new vulnerabilities in real-world programs, and 11 of them have been assigned CVE IDs.
On the image of an affine subspace under the inverse function within a finite field
Venue: arXiv cs.CR 2022
Year: 2022

We consider the function $x^{-1}$ that inverses a finite field element $x \in \mathbb{F}_{p^n}$ ($p$ is prime, $0^{-1} = 0$) and affine $\mathbb{F}_{p}$-subspaces of $\mathbb{F}_{p^n}$ such that their images are affine subspaces as well. It is proven that the image of an affine subspace $L$, $|L| > 2$, is an affine subspace if and only if $L = q \mathbb{F}_{p^k}$, where $q \in \mathbb{F}_{p^n}^{*}$ and $k \mid n$. In other words, it is either a subfield of $\mathbb{F}_{p^n}$ or a subspace consisting of all elements of a subfield multiplied by $q$. This generalizes the results that were obtained for linear invariant subspaces in 2006. As a consequence, we propose a sufficient condition providing that a function $A(x^{-1}) + b$ has no invariant affine subspaces $U$ of cardinality $2 < |U| < p^n$ for an invertible linear transformation $A: \mathbb{F}_{p^n} \to \mathbb{F}_{p^n}$ and $b \in \mathbb{F}_{p^n}^{*}$. As an example, it is shown that the condition works for S-box of AES. Also, we demonstrate that some functions of the form $αx^{-1} + b$ have no invariant affine subspaces except for $\mathbb{F}_{p^n}$, where $α, b \in \mathbb{F}_{p^n}^{*}$ and $n$ is arbitrary.
A Unified End-to-End Retriever-Reader Framework for Knowledge-based VQA
Venue: arXiv cs.CV 2022
Year: 2022

Knowledge-based Visual Question Answering (VQA) expects models to rely on external knowledge for robust answer prediction. Though significant it is, this paper discovers several leading factors impeding the advancement of current state-of-the-art methods. On the one hand, methods which exploit the explicit knowledge take the knowledge as a complement for the coarsely trained VQA model. Despite their effectiveness, these approaches often suffer from noise incorporation and error propagation. On the other hand, pertaining to the implicit knowledge, the multi-modal implicit knowledge for knowledge-based VQA still remains largely unexplored. This work presents a unified end-to-end retriever-reader framework towards knowledge-based VQA. In particular, we shed light on the multi-modal implicit knowledge from vision-language pre-training models to mine its potential in knowledge reasoning. As for the noise problem encountered by the retrieval operation on explicit knowledge, we design a novel scheme to create pseudo labels for effective knowledge supervision. This scheme is able to not only provide guidance for knowledge retrieval, but also drop these instances potentially error-prone towards question answering. To validate the effectiveness of the proposed method, we conduct extensive experiments on the benchmark dataset. The experimental results reveal that our method outperforms existing baselines by a noticeable margin. Beyond the reported numbers, this paper further spawns several insights on knowledge utilization for future research with some empirical findings.
Compressing Pre-trained Transformers via Low-Bit NxM Sparsity for Natural Language Understanding
Venue: arXiv cs.CL 2022
Year: 2022

In recent years, large pre-trained Transformer networks have demonstrated dramatic improvements in many natural language understanding tasks. However, the huge size of these models brings significant challenges to their fine-tuning and online deployment due to latency and cost constraints. New hardware supporting both N:M semi-structured sparsity and low-precision integer computation is a promising solution to boost DNN model serving efficiency. However, there have been very few studies that systematically investigate to what extent pre-trained Transformer networks benefit from the combination of these techniques, as well as how to best compress each component of the Transformer. We propose a flexible compression framework NxMiFormer that performs simultaneous sparsification and quantization using ADMM and STE-based QAT. Furthermore, we present and inexpensive, heuristic-driven search algorithm that identifies promising heterogeneous compression configurations that meet a compression ratio constraint. When evaluated across the GLUE suite of NLU benchmarks, our approach can achieve up to 93% compression of the encoders of a BERT model while retaining 98.2% of the original model accuracy and taking full advantage of the hardware's capabilities. Heterogeneous configurations found the by the search heuristic maintain 99.5% of the baseline accuracy while still compressing the model by 87.5%.
Exploring Temporally Dynamic Data Augmentation for Video Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Data augmentation has recently emerged as an essential component of modern training recipes for visual recognition tasks. However, data augmentation for video recognition has been rarely explored despite its effectiveness. Few existing augmentation recipes for video recognition naively extend the image augmentation methods by applying the same operations to the whole video frames. Our main idea is that the magnitude of augmentation operations for each frame needs to be changed over time to capture the real-world video's temporal variations. These variations should be generated as diverse as possible using fewer additional hyper-parameters during training. Through this motivation, we propose a simple yet effective video data augmentation framework, DynaAugment. The magnitude of augmentation operations on each frame is changed by an effective mechanism, Fourier Sampling that parameterizes diverse, smooth, and realistic temporal variations. DynaAugment also includes an extended search space suitable for video for automatic data augmentation methods. DynaAugment experimentally demonstrates that there are additional performance rooms to be improved from static augmentations on diverse video models. Specifically, we show the effectiveness of DynaAugment on various video datasets and tasks: large-scale video recognition (Kinetics-400 and Something-Something-v2), small-scale video recognition (UCF- 101 and HMDB-51), fine-grained video recognition (Diving-48 and FineGym), video action segmentation on Breakfast, video action localization on THUMOS'14, and video object detection on MOT17Det. DynaAugment also enables video models to learn more generalized representation to improve the model robustness on the corrupted videos.
Story-thinking, computational-thinking, programming and software engineering
Venue: arXiv cs.CL 2022
Year: 2022

Working with stories and working with computations require very different modes of thought. We call the first mode "story-thinking" and the second "computational-thinking". The aim of this curiosity-driven paper is to explore the nature of these two modes of thinking, and to do so in relation to programming, including software engineering as programming-in-the-large. We suggest that story-thinking and computational-thinking may be understood as two ways of attending to the world, and that each both contributes and neglects the world, though in different ways and for different ends. We formulate two fundamental problems, i.e., the problem of "neglectful representations" and the problem of oppositional ways of thinking. We briefly suggest two ways in which these problems might be tackled and identify candidate hypotheses about the current state of the world, one assertion about a possible future state, and several research questions for future research.
Automatic generation of interpretable hyperelastic material models by symbolic regression
Venue: arXiv cs.CE 2022
Year: 2022

In this paper, we present a new procedure to automatically generate interpretable hyperelastic material models. This approach is based on symbolic regression which represents an evolutionary algorithm searching for a mathematical model in the form of an algebraic expression. This results in a relatively simple model with good agreement to experimental data. By expressing the strain energy function in terms of its invariants or other parameters, it is possible to interpret the resulting algebraic formulation in a physical context. In addition, a direct implementation of the obtained algebraic equation is possible. For the validation of the proposed approach, benchmark tests on the basis of the generalized Mooney-Rivlin model are presented. In all these tests, the chosen ansatz can find the predefined models. Additionally, this method is applied for the multi-axial loading data set of vulcanized rubber. Finally, a data set for a temperature-dependent thermoplastic polyester elastomer is evaluated. In latter cases, good agreement with the experimental data is obtained.
Computing the Parameterized Burrows--Wheeler Transform Online
Venue: arXiv cs.DS 2022
Year: 2022

Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characters and the other to be the alphabet of parameter characters. Two parameterized strings are a parameterized match if there is a bijection over all characters such that the bijection transforms one string to the other while keeping the static characters (i.e., it behaves as the identity on the static alphabet). Ganguly et al. [SODA 2017] proposed the parameterized Burrows--Wheeler transform (pBWT) as a variant of the Burrows--Wheeler transform for space-efficient parameterized pattern matching. In this paper, we propose an algorithm for computing the pBWT online by reading the characters of a given input string one-by-one from right to left. Our algorithm works in $O(|Π| \log n / \log \log n)$ amortized time for each input character, where $n$ and $Π$ denote the size of the input string and the alphabet of the parameter characters, respectively.
Some $3$-designs and shortened codes from binary cyclic codes with three zeros
Venue: arXiv cs.IT 2022
Year: 2022

Linear codes and $t$-designs are interactive with each other. It is well known that some $t$-designs have been constructed by using certain linear codes in recent years. However, only a small number of infinite families of the extended codes of linear codes holding an infinite family of $t$-designs with $t\geq 3$ are reported in the literature. In this paper, we study the extended codes of the augmented codes of a class of binary cyclic codes with three zeros and their dual codes, and show that those codes hold $3$-designs. Furthermore, we obtain some shortened codes from the studied cyclic codes and explicitly determine their parameters. Some of those shortened codes are optimal or almost optimal.
ListBERT: Learning to Rank E-commerce products with Listwise BERT
Venue: arXiv cs.IR 2022
Year: 2022

Efficient search is a critical component for an e-commerce platform with an innumerable number of products. Every day millions of users search for products pertaining to their needs. Thus, showing the relevant products on the top will enhance the user experience. In this work, we propose a novel approach of fusing a transformer-based model with various listwise loss functions for ranking e-commerce products, given a user query. We pre-train a RoBERTa model over a fashion e-commerce corpus and fine-tune it using different listwise loss functions. Our experiments indicate that the RoBERTa model fine-tuned with an NDCG based surrogate loss function(approxNDCG) achieves an NDCG improvement of 13.9% compared to other popular listwise loss functions like ListNET and ListMLE. The approxNDCG based RoBERTa model also achieves an NDCG improvement of 20.6% compared to the pairwise RankNet based RoBERTa model. We call our methodology of directly optimizing the RoBERTa model in an end-to-end manner with a listwise surrogate loss function as ListBERT. Since there is a low latency requirement in a real-time search setting, we show how these models can be easily adopted by using a knowledge distillation technique to learn a representation-focused student model that can be easily deployed and leads to ~10 times lower ranking latency.
Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
Venue: arXiv cs.DS 2022
Year: 2022

We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number of queries needed to solve the minimum spanning tree problem, a fundamental combinatorial optimization problem that has been central also to the research area of explorable uncertainty. For all integral $γ\ge 2$, we present algorithms that are $γ$-robust and $(1+\frac{1}γ)$-consistent, meaning that they use at most $γOPT$ queries if the predictions are arbitrarily wrong and at most $(1+\frac{1}γ)OPT$ queries if the predictions are correct, where $OPT$ is the optimal number of queries for the given instance. Moreover, we show that this trade-off is best possible. Furthermore, we argue that a suitably defined hop distance is a useful measure for the amount of prediction error and design algorithms with performance guarantees that degrade smoothly with the hop distance. We also show that the predictions are PAC-learnable in our model. Our results demonstrate that untrusted predictions can circumvent the known lower bound of~$2$, without any degradation of the worst-case ratio. To obtain our results, we provide new structural insights for the minimum spanning tree problem that might be useful in the context of query-based algorithms regardless of predictions. In particular, we generalize the concept of witness sets -- the key to lower-bounding the optimum -- by proposing novel global witness set structures and completely new ways of adaptively using those.
Stochastic Poisson Surface Reconstruction
Venue: arXiv cs.GR 2022
Year: 2022

We introduce a statistical extension of the classic Poisson Surface Reconstruction algorithm for recovering shapes from 3D point clouds. Instead of outputting an implicit function, we represent the reconstructed shape as a modified Gaussian Process, which allows us to conduct statistical queries (e.g., the likelihood of a point in space being on the surface or inside a solid). We show that this perspective: improves PSR's integration into the online scanning process, broadens its application realm, and opens the door to other lines of research such as applying task-specific priors.
Adherence to Misinformation on Social Media Through Socio-Cognitive and Group-Based Processes
Venue: arXiv cs.CY 2022
Year: 2022

Previous work suggests that people's preference for different kinds of information depends on more than just accuracy. This could happen because the messages contained within different pieces of information may either be well-liked or repulsive. Whereas factual information must often convey uncomfortable truths, misinformation can have little regard for veracity and leverage psychological processes which increase its attractiveness and proliferation on social media. In this review, we argue that when misinformation proliferates, this happens because the social media environment enables adherence to misinformation by reducing, rather than increasing, the psychological cost of doing so. We cover how attention may often be shifted away from accuracy and towards other goals, how social and individual cognition is affected by misinformation and the cases under which debunking it is most effective, and how the formation of online groups affects information consumption patterns, often leading to more polarization and radicalization. Throughout, we make the case that polarization and misinformation adherence are closely tied. We identify ways in which the psychological cost of adhering to misinformation can be increased when designing anti-misinformation interventions or resilient affordances, and we outline open research questions that the CSCW community can take up in further understanding this cost.
FL-Tuning: Layer Tuning for Feed-Forward Network in Transformer
Venue: arXiv cs.CL 2022
Year: 2022

Prompt tuning is an emerging way of adapting pre-trained language models to downstream tasks. However, the existing studies are mainly to add prompts to the input sequence. This way would not work as expected due to the intermediate multi-head self-attention and feed-forward network computation, making model optimization not very smooth. Hence, we propose a novel tuning way called layer tuning, aiming to add learnable parameters in Transformer layers. Specifically, we focus on layer tuning for feed-forward network in the Transformer, namely FL-tuning. It introduces additional units into the hidden layer of each feed-forward network. We conduct extensive experiments on the public CLUE benchmark. The results show that: 1) Our FL-tuning outperforms prompt tuning methods under both full-data and few-shot settings in almost all cases. In particular, it improves accuracy by 17.93% (full-data setting) on WSC 1.0 and F1 by 16.142% (few-shot setting) on CLUENER over P-tuning v2. 2) Our FL-tuning is more stable and converges about 1.17 times faster than P-tuning v2. 3) With only about 3% of Transformer's parameters to be trained, FL-tuning is comparable with fine-tuning on most datasets, and significantly outperforms fine-tuning (e.g., accuracy improved by 12.9% on WSC 1.1) on several datasets. The source codes are available at https://github.com/genggui001/FL-Tuning.
Learning Citywide Patterns of Life from Trajectory Monitoring
Venue: arXiv cs.LG 2022
Year: 2022

The recent proliferation of real-world human mobility datasets has catalyzed geospatial and transportation research in trajectory prediction, demand forecasting, travel time estimation, and anomaly detection. However, these datasets also enable, more broadly, a descriptive analysis of intricate systems of human mobility. We formally define patterns of life analysis as a natural, explainable extension of online unsupervised anomaly detection, where we not only monitor a data stream for anomalies but also explicitly extract normal patterns over time. To learn patterns of life, we adapt Grow When Required (GWR) episodic memory from research in computational biology and neurorobotics to a new domain of geospatial analysis. This biologically-inspired neural network, related to self-organizing maps (SOM), constructs a set of "memories" or prototype traffic patterns incrementally as it iterates over the GPS stream. It then compares each new observation to its prior experiences, inducing an online, unsupervised clustering and anomaly detection on the data. We mine patterns-of-interest from the Porto taxi dataset, including both major public holidays and newly-discovered transportation anomalies, such as festivals and concerts which, to our knowledge, have not been previously acknowledged or reported in prior work. We anticipate that the capability to incrementally learn normal and abnormal road transportation behavior will be useful in many domains, including smart cities, autonomous vehicles, and urban planning and management.
Two-Stage Classifier for COVID-19 Misinformation Detection Using BERT: a Study on Indonesian Tweets
Venue: arXiv cs.CL 2022
Year: 2022

The COVID-19 pandemic has caused globally significant impacts since the beginning of 2020. This brought a lot of confusion to society, especially due to the spread of misinformation through social media. Although there were already several studies related to the detection of misinformation in social media data, most studies focused on the English dataset. Research on COVID-19 misinformation detection in Indonesia is still scarce. Therefore, through this research, we collect and annotate datasets for Indonesian and build prediction models for detecting COVID-19 misinformation by considering the tweet's relevance. The dataset construction is carried out by a team of annotators who labeled the relevance and misinformation of the tweet data. In this study, we propose the two-stage classifier model using IndoBERT pre-trained language model for the Tweet misinformation detection task. We also experiment with several other baseline models for text classification. The experimental results show that the combination of the BERT sequence classifier for relevance prediction and Bi-LSTM for misinformation detection outperformed other machine learning models with an accuracy of 87.02%. Overall, the BERT utilization contributes to the higher performance of most prediction models. We release a high-quality COVID-19 misinformation Tweet corpus in the Indonesian language, indicated by the high inter-annotator agreement.