OpenRaiser/Intern-Atlas huggingface dataset:
Position Heaps for Cartesian-tree Matching on Strings and Tries
Venue: arXiv cs.DS 2021
Year: 2021

The Cartesian-tree pattern matching is a recently introduced scheme of pattern matching that detects fragments in a sequential data stream which have a similar structure as a query pattern. Formally, Cartesian-tree pattern matching seeks all substrings $S'$ of the text string $S$ such that the Cartesian tree of $S'$ and that of a query pattern $P$ coincide. In this paper, we present a new indexing structure for this problem called the Cartesian-tree Position Heap (CPH). Let $n$ be the length of the input text string $S$, $m$ the length of a query pattern $P$, and $σ$ the alphabet size. We show that the CPH of $S$, denoted $\mathsf{CPH}(S)$, supports pattern matching queries in $O(m (σ+ \log (\min\{h, m\})) + occ)$ time with $O(n)$ space, where $h$ is the height of the CPH and $occ$ is the number of pattern occurrences. We show how to build $\mathsf{CPH}(S)$ in $O(n \log σ)$ time with $O(n)$ working space. Further, we extend the problem to the case where the text is a labeled tree (i.e. a trie). Given a trie $T$ with $N$ nodes, we show that the CPH of $T$, denoted $\mathsf{CPH}(T)$, supports pattern matching queries on the trie in $O(m (σ^2 + \log (\min\{h, m\})) + occ)$ time with $O(N σ)$ space. We also show a construction algorithm for $\mathsf{CPH}(T)$ running in $O(N σ)$ time and $O(N σ)$ working space.
Automatically Detecting Cyberbullying Comments on Online Game Forums
Venue: arXiv cs.CL 2021
Year: 2021

Online game forums are popular to most of game players. They use it to communicate and discuss the strategy of the game, or even to make friends. However, game forums also contain abusive and harassment speech, disturbing and threatening players. Therefore, it is necessary to automatically detect and remove cyberbullying comments to keep the game forum clean and friendly. We use the Cyberbullying dataset collected from World of Warcraft (WoW) and League of Legends (LoL) forums and train classification models to automatically detect whether a comment of a player is abusive or not. The result obtains 82.69% of macro F1-score for LoL forum and 83.86% of macro F1-score for WoW forum by the Toxic-BERT model on the Cyberbullying dataset.
A Discussion On the Validity of Manifold Learning
Venue: arXiv cs.LG 2021
Year: 2021

Dimensionality reduction (DR) and manifold learning (ManL) have been applied extensively in many machine learning tasks, including signal processing, speech recognition, and neuroinformatics. However, the understanding of whether DR and ManL models can generate valid learning results remains unclear. In this work, we investigate the validity of learning results of some widely used DR and ManL methods through the chart mapping function of a manifold. We identify a fundamental problem of these methods: the mapping functions induced by these methods violate the basic settings of manifolds, and hence they are not learning manifold in the mathematical sense. To address this problem, we provide a provably correct algorithm called fixed points Laplacian mapping (FPLM), that has the geometric guarantee to find a valid manifold representation (up to a homeomorphism). Combining one additional condition(orientation preserving), we discuss a sufficient condition for an algorithm to be bijective for any d-simplex decomposition result on a d-manifold. However, constructing such a mapping function and its computational method satisfying these conditions is still an open problem in mathematics.
Piercing the Veil: Designs to Support Information Literacy on Social Platforms
Venue: arXiv cs.HC 2021
Year: 2021

In this position paper we approach problems concerning critical digital and information literacy with ideas to provide more digestible explanations of abstract concepts through interface design. In particular, we focus on social media platforms where we see the possibility of counteracting the spread of misinformation by providing users with more proficiency through our approaches. We argue that the omnipresent trend to abstract away and hide information from users via UI/UX design opposes their ability to self-learn. This leads us to propose a different framework in which we unify elegant and simple interfaces with nudges that promote a look behind the curtain. Such designs serve to foster a deeper understanding of employed technologies and aim to increase the critical assessment of content encountered on social platforms. Furthermore, we consider users with an intermediary skill level to be largely ignored in current approaches, as they are given no tools to broaden their knowledge without consultation of expert material. The resulting stagnation is exemplified by the tactics of misinformation campaigns, which exploit the ensuing lack of information literacy and critical thinking. We propose an approach to design that sufficiently emancipates users in both aspects by promoting a look behind the abstraction of UI/UX so that an autonomous learning process is given the chance to occur. Furthermore, we name ideas for future research within this area that take our considerations into account.
Cybersecurity Information Exchange with Privacy (CYBEX-P) and TAHOE -- A Cyberthreat Language
Venue: arXiv cs.CR 2021
Year: 2021

Cybersecurity information sharing (CIS) is envisioned to protect organizations more effectively from advanced cyber attacks. However, a completely automated CIS platform is not widely adopted. The major challenges are: (1) the absence of a robust cyber threat language (CTL) and (2) the concerns over data privacy. This work introduces Cybersecurity Information Exchangewith Privacy (CYBEX-P), as a CIS framework, to tackle these challenges. CYBEX-P allows organizations to share heterogeneous data with granular, attribute based privacy control. It correlates the data to automatically generate intuitive reports and defensive rules. To achieve such versatility, we have developed TAHOE - a graph based CTL. TAHOE is a structure for storing,sharing and analyzing threat data. It also intrinsically correlates the data. We have further developed a universal Threat Data Query Language (TDQL). In this paper, we propose the system architecture for CYBEX-P. We then discuss its scalability and privacy features along with a use case of CYBEX-P providing Infrastructure as a Service (IaaS). We further introduce TAHOE& TDQL as better alternatives to existing CTLs and formulate ThreatRank - an algorithm to detect new malicious even
APES: Audiovisual Person Search in Untrimmed Video
Venue: arXiv cs.CV 2021
Year: 2021

Humans are arguably one of the most important subjects in video streams, many real-world applications such as video summarization or video editing workflows often require the automatic search and retrieval of a person of interest. Despite tremendous efforts in the person reidentification and retrieval domains, few works have developed audiovisual search strategies. In this paper, we present the Audiovisual Person Search dataset (APES), a new dataset composed of untrimmed videos whose audio (voices) and visual (faces) streams are densely annotated. APES contains over 1.9K identities labeled along 36 hours of video, making it the largest dataset available for untrimmed audiovisual person search. A key property of APES is that it includes dense temporal annotations that link faces to speech segments of the same identity. To showcase the potential of our new dataset, we propose an audiovisual baseline and benchmark for person retrieval. Our study shows that modeling audiovisual cues benefits the recognition of people's identities. To enable reproducibility and promote future research, the dataset annotations and baseline code are available at: https://github.com/fuankarion/audiovisual-person-search
A protocol to gather, characterize and analyze incoming citations of retracted articles
Venue: arXiv cs.DL 2021
Year: 2021

In this article, we present a methodology which takes as input a collection of retracted articles, gathers the entities citing them, characterizes such entities according to multiple dimensions (disciplines, year of publication, sentiment, etc.), and applies a quantitative and qualitative analysis on the collected values. The methodology is composed of four phases: (1) identifying, retrieving, and extracting basic metadata of the entities which have cited a retracted article, (2) extracting and labeling additional features based on the textual content of the citing entities, (3) building a descriptive statistical summary based on the collected data, and finally (4) running a topic modeling analysis. The goal of the methodology is to generate data and visualizations that help understanding possible behaviors related to retraction cases. We present the methodology in a structured step-by-step form following its four phases, discuss its limits and possible workarounds, and list the planned future improvements.
Towards a Mathematical Theory of Abstraction
Venue: arXiv cs.AI 2021
Year: 2021

While the utility of well-chosen abstractions for understanding and predicting the behaviour of complex systems is well appreciated, precisely what an abstraction $\textit{is}$ has so far has largely eluded mathematical formalization. In this paper, we aim to set out a mathematical theory of abstraction. We provide a precise characterisation of what an abstraction is and, perhaps more importantly, suggest how abstractions can be learnt directly from data both for static datasets and for dynamical systems. We define an abstraction to be a small set of `summaries' of a system which can be used to answer a set of queries about the system or its behaviour. The difference between the ground truth behaviour of the system on the queries and the behaviour of the system predicted only by the abstraction provides a measure of the `leakiness' of the abstraction which can be used as a loss function to directly learn abstractions from data. Our approach can be considered a generalization of classical statistics where we are not interested in reconstructing `the data' in full, but are instead only concerned with answering a set of arbitrary queries about the data. While highly theoretical, our results have deep implications for statistical inference and machine learning and could be used to develop explicit methods for learning precise kinds of abstractions directly from data.
Heart Sound Classification Considering Additive Noise and Convolutional Distortion
Venue: arXiv cs.SD 2021
Year: 2021

Cardiac auscultation is an essential point-of-care method used for the early diagnosis of heart diseases. Automatic analysis of heart sounds for abnormality detection is faced with the challenges of additive noise and sensor-dependent degradation. This paper aims to develop methods to address the cardiac abnormality detection problem when both types of distortions are present in the cardiac auscultation sound. We first mathematically analyze the effect of additive and convolutional noise on short-term filterbank-based features and a Convolutional Neural Network (CNN) layer. Based on the analysis, we propose a combination of linear and logarithmic spectrogram-image features. These 2D features are provided as input to a residual CNN network (ResNet) for heart sound abnormality detection. Experimental validation is performed on an open-access heart sound abnormality detection dataset involving noisy recordings obtained from multiple stethoscope sensors. The proposed method achieves significantly improved results compared to the conventional approaches, with an area under the ROC (receiver operating characteristics) curve (AUC) of 91.36%, F-1 score of 84.09%, and Macc (mean of sensitivity and specificity) of 85.08%. We also show that the proposed method shows the best mean accuracy across different source domains including stethoscope and noise variability, demonstrating its effectiveness in different recording conditions. The proposed combination of linear and logarithmic features along with the ResNet classifier effectively minimizes the impact of background noise and sensor variability for classifying phonocardiogram (PCG) signals. The proposed method paves the way towards developing computer-aided cardiac auscultation systems in noisy environments using low-cost stethoscopes.
Salp Swarm Optimization: a Critical Review
Venue: arXiv cs.NE 2021
Year: 2021

In the crowded environment of bio-inspired population-based metaheuristics, the Salp Swarm Optimization (SSO) algorithm recently appeared and immediately gained a lot of momentum. Inspired by the peculiar spatial arrangement of salp colonies, which are displaced in long chains following a leader, this algorithm seems to provide an interesting optimization performance. However, the original work was characterized by some conceptual and mathematical flaws, which influenced all ensuing papers on the subject. In this manuscript, we perform a critical review of SSO, highlighting all the issues present in the literature and their negative effects on the optimization process carried out by this algorithm. We also propose a mathematically correct version of SSO, named Amended Salp Swarm Optimizer (ASSO) that fixes all the discussed problems. We benchmarked the performance of ASSO on a set of tailored experiments, showing that it is able to achieve better results than the original SSO. Finally, we performed an extensive study aimed at understanding whether SSO and its variants provide advantages compared to other metaheuristics. The experimental results, where SSO cannot outperform simple well-known metaheuristics, suggest that the scientific community can safely abandon SSO.
A Comparison for Anti-noise Robustness of Deep Learning Classification Methods on a Tiny Object Image Dataset: from Convolutional Neural Network to Visual Transformer and Performer
Venue: arXiv cs.CV 2021
Year: 2021

Image classification has achieved unprecedented advance with the the rapid development of deep learning. However, the classification of tiny object images is still not well investigated. In this paper, we first briefly review the development of Convolutional Neural Network and Visual Transformer in deep learning, and introduce the sources and development of conventional noises and adversarial attacks. Then we use various models of Convolutional Neural Network and Visual Transformer to conduct a series of experiments on the image dataset of tiny objects (sperms and impurities), and compare various evaluation metrics in the experimental results to obtain a model with stable performance. Finally, we discuss the problems in the classification of tiny objects and make a prospect for the classification of tiny objects in the future.
Optimizing Rankings for Recommendation in Matching Markets
Venue: arXiv cs.IR 2021
Year: 2021

Based on the success of recommender systems in e-commerce, there is growing interest in their use in matching markets (e.g., labor). While this holds potential for improving market fluidity and fairness, we show in this paper that naively applying existing recommender systems to matching markets is sub-optimal. Considering the standard process where candidates apply and then get evaluated by employers, we present a new recommendation framework to model this interaction mechanism and propose efficient algorithms for computing personalized rankings in this setting. We show that the optimal rankings need to not only account for the potentially divergent preferences of candidates and employers, but they also need to account for capacity constraints. This makes conventional ranking systems that merely rank by some local score (e.g., one-sided or reciprocal relevance) highly sub-optimal -- not only for an individual user, but also for societal goals (e.g., low unemployment). To address this shortcoming, we propose the first method for jointly optimizing the rankings for all candidates in the market to explicitly maximize social welfare. In addition to the theoretical derivation, we evaluate the method both on simulated environments and on data from a real-world networking-recommendation system that we built and fielded at a large computer science conference.
NeRFactor: Neural Factorization of Shape and Reflectance Under an Unknown Illumination
Venue: arXiv cs.CV 2021
Year: 2021

We address the problem of recovering the shape and spatially-varying reflectance of an object from multi-view images (and their camera poses) of an object illuminated by one unknown lighting condition. This enables the rendering of novel views of the object under arbitrary environment lighting and editing of the object's material properties. The key to our approach, which we call Neural Radiance Factorization (NeRFactor), is to distill the volumetric geometry of a Neural Radiance Field (NeRF) [Mildenhall et al. 2020] representation of the object into a surface representation and then jointly refine the geometry while solving for the spatially-varying reflectance and environment lighting. Specifically, NeRFactor recovers 3D neural fields of surface normals, light visibility, albedo, and Bidirectional Reflectance Distribution Functions (BRDFs) without any supervision, using only a re-rendering loss, simple smoothness priors, and a data-driven BRDF prior learned from real-world BRDF measurements. By explicitly modeling light visibility, NeRFactor is able to separate shadows from albedo and synthesize realistic soft or hard shadows under arbitrary lighting conditions. NeRFactor is able to recover convincing 3D models for free-viewpoint relighting in this challenging and underconstrained capture setup for both synthetic and real scenes. Qualitative and quantitative experiments show that NeRFactor outperforms classic and deep learning-based state of the art across various tasks. Our videos, code, and data are available at people.csail.mit.edu/xiuming/projects/nerfactor/.
Provably Secure Generative Linguistic Steganography
Venue: arXiv cs.CL 2021
Year: 2021

Generative linguistic steganography mainly utilized language models and applied steganographic sampling (stegosampling) to generate high-security steganographic text (stegotext). However, previous methods generally lead to statistical differences between the conditional probability distributions of stegotext and natural text, which brings about security risks. In this paper, to further ensure security, we present a novel provably secure generative linguistic steganographic method ADG, which recursively embeds secret information by Adaptive Dynamic Grouping of tokens according to their probability given by an off-the-shelf language model. We not only prove the security of ADG mathematically, but also conduct extensive experiments on three public corpora to further verify its imperceptibility. The experimental results reveal that the proposed method is able to generate stegotext with nearly perfect security.
Attack Prediction using Hidden Markov Model
Venue: arXiv cs.CR 2021
Year: 2021

It is important to predict any adversarial attacks and their types to enable effective defense systems. Often it is hard to label such activities as malicious ones without adequate analytical reasoning. We propose the use of Hidden Markov Model (HMM) to predict the family of related attacks. Our proposed model is based on the observations often agglomerated in the form of log files and from the target or the victim's perspective. We have built an HMM-based prediction model and implemented our proposed approach using Viterbi algorithm, which generates a sequence of states corresponding to stages of a particular attack. As a proof of concept and also to demonstrate the performance of the model, we have conducted a case study on predicting a family of attacks called Action Spoofing.
Nonlinear Matrix Approximation with Radial Basis Function Components
Venue: arXiv cs.LG 2021
Year: 2021

We introduce and investigate matrix approximation by decomposition into a sum of radial basis function (RBF) components. An RBF component is a generalization of the outer product between a pair of vectors, where an RBF function replaces the scalar multiplication between individual vector elements. Even though the RBF functions are positive definite, the summation across components is not restricted to convex combinations and allows us to compute the decomposition for any real matrix that is not necessarily symmetric or positive definite. We formulate the problem of seeking such a decomposition as an optimization problem with a nonlinear and non-convex loss function. Several modern versions of the gradient descent method, including their scalable stochastic counterparts, are used to solve this problem. We provide extensive empirical evidence of the effectiveness of the RBF decomposition and that of the gradient-based fitting algorithm. While being conceptually motivated by singular value decomposition (SVD), our proposed nonlinear counterpart outperforms SVD by drastically reducing the memory required to approximate a data matrix with the same L2 error for a wide range of matrix types. For example, it leads to 2 to 6 times memory save for Gaussian noise, graph adjacency matrices, and kernel matrices. Moreover, this proximity-based decomposition can offer additional interpretability in applications that involve, e.g., capturing the inner low-dimensional structure of the data, retaining graph connectivity structure, and preserving the acutance of images.
Least-squares fitting of Gaussian spots on graphics processing units
Venue: arXiv cs.DC 2021
Year: 2021

The investigation of samples with a spatial resolution in the nanometer range relies on the precise and stable positioning of the sample. Due to inherent mechanical instabilities of typical sample stages in optical microscopes, it is usually required to control and/or monitor the sample position during the acquisition. The tracking of sparsely distributed fiducial markers at high speed allows stabilizing the sample position at millisecond time scales. For this purpose, we present a scalable fitting algorithm with significantly improved performance for two-dimensional Gaussian fits as compared to Gpufit.
The Earth Mover's Pinball Loss: Quantiles for Histogram-Valued Regression
Venue: arXiv cs.LG 2021
Year: 2021

Although ubiquitous in the sciences, histogram data have not received much attention by the Deep Learning community. Whilst regression and classification tasks for scalar and vector data are routinely solved by neural networks, a principled approach for estimating histogram labels as a function of an input vector or image is lacking in the literature. We present a dedicated method for Deep Learning-based histogram regression, which incorporates cross-bin information and yields distributions over possible histograms, expressed by $τ$-quantiles of the cumulative histogram in each bin. The crux of our approach is a new loss function obtained by applying the pinball loss to the cumulative histogram, which for 1D histograms reduces to the Earth Mover's distance (EMD) in the special case of the median ($τ= 0.5$), and generalizes it to arbitrary quantiles. We validate our method with an illustrative toy example, a football-related task, and an astrophysical computer vision problem. We show that with our loss function, the accuracy of the predicted median histograms is very similar to the standard EMD case (and higher than for per-bin loss functions such as cross-entropy), while the predictions become much more informative at almost no additional computational cost.
Towards a Cross-Domain Software Safety Assurance Process for Embedded Systems
Venue: arXiv cs.SE 2021
Year: 2021

In this work, we outline a cross-domain assurance process for safety-relevant software in embedded systems. This process aims to be applied in various different application domains and in conjunction with any development methodology. With this approach we plan to reduce the growing effort for safety assessment in embedded systems by reusing safety analysis techniques and tools for the product development in different domains.