OpenRaiser/Intern-Atlas huggingface dataset:
Language Modeling with Reduced Densities
Venue: arXiv cs.CL 2021
Year: 2021

This work originates from the observation that today's state-of-the-art statistical language models are impressive not only for their performance, but also - and quite crucially - because they are built entirely from correlations in unstructured text data. The latter observation prompts a fundamental question that lies at the heart of this paper: What mathematical structure exists in unstructured text data? We put forth enriched category theory as a natural answer. We show that sequences of symbols from a finite alphabet, such as those found in a corpus of text, form a category enriched over probabilities. We then address a second fundamental question: How can this information be stored and modeled in a way that preserves the categorical structure? We answer this by constructing a functor from our enriched category of text to a particular enriched category of reduced density operators. The latter leverages the Loewner order on positive semidefinite operators, which can further be interpreted as a toy example of entailment.
Coding with Noiseless Feedback over the Z-channel
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction $τ\ge 1/4$ vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with $n$ transmissions that achieves a positive rate for any fraction of errors $τ<1$ and $n\to\infty$. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes.
A One-step Approach to Covariate Shift Adaptation
Venue: arXiv cs.LG 2021
Year: 2021

A default assumption in many machine learning scenarios is that the training and test samples are drawn from the same probability distribution. However, such an assumption is often violated in the real world due to non-stationarity of the environment or bias in sample selection. In this work, we consider a prevalent setting called covariate shift, where the input distribution differs between the training and test stages while the conditional distribution of the output given the input remains unchanged. Most of the existing methods for covariate shift adaptation are two-step approaches, which first calculate the importance weights and then conduct importance-weighted empirical risk minimization. In this paper, we propose a novel one-step approach that jointly learns the predictive model and the associated weights in one optimization by minimizing an upper bound of the test risk. We theoretically analyze the proposed method and provide a generalization error bound. We also empirically demonstrate the effectiveness of the proposed method.
Mental representations of objects reflect the ways in which we interact with them
Venue: arXiv cs.CL 2021
Year: 2021

In order to interact with objects in our environment, humans rely on an understanding of the actions that can be performed on them, as well as their properties. When considering concrete motor actions, this knowledge has been called the object affordance. Can this notion be generalized to any type of interaction that one can have with an object? In this paper we introduce a method to represent objects in a space where each dimension corresponds to a broad mode of interaction, based on verb selectional preferences in text corpora. This object embedding makes it possible to predict human judgments of verb applicability to objects better than a variety of alternative approaches. Furthermore, we show that the dimensions in this space can be used to predict categorical and functional dimensions in a state-of-the-art mental representation of objects, derived solely from human judgements of object similarity. These results suggest that interaction knowledge accounts for a large part of mental representations of objects.
SmaAt-UNet: Precipitation Nowcasting using a Small Attention-UNet Architecture
Venue: arXiv cs.LG 2021
Year: 2021

Weather forecasting is dominated by numerical weather prediction that tries to model accurately the physical properties of the atmosphere. A downside of numerical weather prediction is that it is lacking the ability for short-term forecasts using the latest available information. By using a data-driven neural network approach we show that it is possible to produce an accurate precipitation nowcast. To this end, we propose SmaAt-UNet, an efficient convolutional neural networks-based on the well known UNet architecture equipped with attention modules and depthwise-separable convolutions. We evaluate our approaches on a real-life datasets using precipitation maps from the region of the Netherlands and binary images of cloud coverage of France. The experimental results show that in terms of prediction performance, the proposed model is comparable to other examined models while only using a quarter of the trainable parameters.
Efficient Trajectory Compression and Range Query Processing
Venue: arXiv cs.DB 2021
Year: 2021

Nowadays, there are ubiquitousness of GPS sensors in various devices collecting, transmitting and storing tremendous trajectory data. However, such an unprecedented scale of GPS data has posed an urgent demand for not only an effective storage mechanism but also an efficient query mechanism. Line simplification in online mode, searving as a mainstream trajectory compression method, plays an important role to attack this issue. But for the existing algorithms, either their time cost is extremely high, or the accuracy loss after the compression is completely unacceptable. To attack this issue, we propose $ε\_$Region based Online trajectory Compression with Error bounded (ROCE for short), which makes the best balance among the accuracy loss, the time cost and the compression rate. The range query serves as a primitive, yet quite essential operation on analyzing trajectories. Each trajectory is usually seen as a sequence of discrete points, and in most previous work, a trajectory is judged to be overlapped with the query region R iff there is at least one point in this trajectory falling in R. But this traditional criteria is not suitable when the queried trajectories are compressed, because there may be hundreds of points discarded between each two adjacent points and the points in each compressed trajectory are quite sparse. And many trajectories could be missing in the result set. To address this, in this paper, a new criteria based on the probability and an efficient Range Query processing algorithm on Compressed trajectories RQC are proposed. In addition, an efficient index \emph{ASP\_tree} and lots of novel techniques are also presented to accelerate the processing of trajectory compression and range queries obviously. Extensive experiments have been done on multiple real datasets, and the results demonstrate superior performance of our methods.
A deep learning approach to identify unhealthy advertisements in street view images
Venue: arXiv cs.CY 2021
Year: 2021

While outdoor advertisements are common features within towns and cities, they may reinforce social inequalities in health. Vulnerable populations in deprived areas may have greater exposure to fast food, gambling and alcohol advertisements encouraging their consumption. Understanding who is exposed and evaluating potential policy restrictions requires a substantial manual data collection effort. To address this problem we develop a deep learning workflow to automatically extract and classify unhealthy advertisements from street-level images. We introduce the Liverpool 360 Street View (LIV360SV) dataset for evaluating our workflow. The dataset contains 25,349, 360 degree, street-level images collected via cycling with a GoPro Fusion camera, recorded Jan 14th - 18th 2020. 10,106 advertisements were identified and classified as food (1335), alcohol (217), gambling (149) and other (8405) (e.g., cars and broadband). We find evidence of social inequalities with a larger proportion of food advertisements located within deprived areas and those frequented by students. Our project presents a novel implementation for the incidental classification of street view images for identifying unhealthy advertisements, providing a means through which to identify areas that can benefit from tougher advertisement restriction policies for tackling social inequalities.
GAMA: a General Automated Machine learning Assistant
Venue: arXiv cs.LG 2021
Year: 2021

The General Automated Machine learning Assistant (GAMA) is a modular AutoML system developed to empower users to track and control how AutoML algorithms search for optimal machine learning pipelines, and facilitate AutoML research itself. In contrast to current, often black-box systems, GAMA allows users to plug in different AutoML and post-processing techniques, logs and visualizes the search process, and supports easy benchmarking. It currently features three AutoML search algorithms, two model post-processing steps, and is designed to allow for more components to be added.
How the adoption of feature toggles correlates with branch merges and defects in open-source projects?
Venue: arXiv cs.SE 2021
Year: 2021

Context: Branching has been widely adopted in version control to enable collaborative software development. However, the isolation caused by branches may impose challenges on the upcoming merging process. Recently, companies like Google, Microsoft, Facebook, and Spotify, among others, have adopted trunk-based development together with feature toggles. This strategy enables collaboration without the need for isolation through branches, potentially reducing the merging challenges. However, the literature lacks evidence about the benefits and limitations of feature toggles to collaborative software development. Objective/Method: In this paper, we study the effects of applying feature toggles on 949 open-source projects written in 6 different programming languages. We first identified the moment in which each project adopted a feature toggles framework. Then, we observed whether the adoption implied significant changes in the frequency or complexity of branch merges and the number of defects, and the average time to fix them. Finally, we compared the obtained results with results obtained from a set of control projects that do not use feature toggles frameworks. Results/Conclusion: We could observe a reduction in the average merge effort and an increase in the average total time needed to fix defects after adopting feature toggles frameworks. However, we could not confirm that this increase was influenced by the use of feature toggles.
Meta Soft Label Generation for Noisy Labels
Venue: arXiv cs.CV 2021
Year: 2021

The existence of noisy labels in the dataset causes significant performance degradation for deep neural networks (DNNs). To address this problem, we propose a Meta Soft Label Generation algorithm called MSLG, which can jointly generate soft labels using meta-learning techniques and learn DNN parameters in an end-to-end fashion. Our approach adapts the meta-learning paradigm to estimate optimal label distribution by checking gradient directions on both noisy training data and noise-free meta-data. In order to iteratively update soft labels, meta-gradient descent step is performed on estimated labels, which would minimize the loss of noise-free meta samples. In each iteration, the base classifier is trained on estimated meta labels. MSLG is model-agnostic and can be added on top of any existing model at hand with ease. We performed extensive experiments on CIFAR10, Clothing1M and Food101N datasets. Results show that our approach outperforms other state-of-the-art methods by a large margin.
Submodular Meta-Learning
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we introduce a discrete variant of the meta-learning framework. Meta-learning aims at exploiting prior experience and data to improve performance on future tasks. By now, there exist numerous formulations for meta-learning in the continuous domain. Notably, the Model-Agnostic Meta-Learning (MAML) formulation views each task as a continuous optimization problem and based on prior data learns a suitable initialization that can be adapted to new, unseen tasks after a few simple gradient updates. Motivated by this terminology, we propose a novel meta-learning framework in the discrete domain where each task is equivalent to maximizing a set function under a cardinality constraint. Our approach aims at using prior data, i.e., previously visited tasks, to train a proper initial solution set that can be quickly adapted to a new task at a relatively low computational cost. This approach leads to (i) a personalized solution for each individual task, and (ii) significantly reduced computational cost at test time compared to the case where the solution is fully optimized once the new task is revealed. The training procedure is performed by solving a challenging discrete optimization problem for which we present deterministic and randomized algorithms. In the case where the tasks are monotone and submodular, we show strong theoretical guarantees for our proposed methods even though the training objective may not be submodular. We also demonstrate the effectiveness of our framework on two real-world problem instances where we observe that our methods lead to a significant reduction in computational complexity in solving the new tasks while incurring a small performance loss compared to when the tasks are fully optimized.
KARB Solution: Compliance to Quality by Rule Based Benchmarking
Venue: arXiv cs.SE 2021
Year: 2021

Instead of proofs or logical evaluations, compliance assessment could be done by benchmarking. Benchmarks, in their nature, are applied. So a set of benchmarks could shape an applied solution for compliance assessment. In this paper, we introduce the KARB solution: Keeping away compliance Anomalies by Rule-based Benchmarking. By rule-based benchmarking, we mean evaluation of under-compliance-system by its symbolic specification and by using a set of symbolic rules (on behalf of semantic logic of evaluation). In order to demonstrate and investigate the manner of KARB solution, we conducted a case study. The IR-QUMA study (Iranian Survey on Quality in Messenger Apps) is defined to evaluate the quality of some messenger apps. the results of evaluations suggest that the Hybrid Method of DD-KARB (with combination of semantics-awareness and data-drivenness) is more effective than solo-methods and could compute a somehow good estimation for messenger-apps user quality scores. So DD-KARB could be considered as a method for quality benchmarking in this technical context.
A Computationally Tractable Framework for Nonlinear Dynamic Multiscale Modeling of Membrane Fabric
Venue: arXiv cs.CE 2021
Year: 2021

A general-purpose computational homogenization framework is proposed for the nonlinear dynamic analysis of membranes exhibiting complex microscale and/or mesoscale heterogeneity characterized by in-plane periodicity that cannot be effectively treated by a conventional method, such as woven fabrics. The framework is a generalization of the "finite element squared" (or FE2) method in which a localized portion of the periodic subscale structure is modeled using finite elements. The numerical solution of displacement driven problems involving this model can be adapted to the context of membranes by a variant of the Klinkel-Govindjee method[1] originally proposed for using finite strain, three-dimensional material models in beam and shell elements. This approach relies on numerical enforcement of the plane stress constraint and is enabled by the principle of frame invariance. Computational tractability is achieved by introducing a regression-based surrogate model informed by a physics-inspired training regimen in which FE$^2$ is utilized to simulate a variety of numerical experiments including uniaxial, biaxial and shear straining of a material coupon. Several alternative surrogate models are evaluated including an artificial neural network. The framework is demonstrated and validated for a realistic Mars landing application involving supersonic inflation of a parachute canopy made of woven fabric.
Regularized linear autoencoders recover the principal components, eventually
Venue: arXiv cs.LG 2021
Year: 2021

Our understanding of learning input-output relationships with neural nets has improved rapidly in recent years, but little is known about the convergence of the underlying representations, even in the simple case of linear autoencoders (LAEs). We show that when trained with proper regularization, LAEs can directly learn the optimal representation -- ordered, axis-aligned principal components. We analyze two such regularization schemes: non-uniform $\ell_2$ regularization and a deterministic variant of nested dropout [Rippel et al, ICML' 2014]. Though both regularization schemes converge to the optimal representation, we show that this convergence is slow due to ill-conditioning that worsens with increasing latent dimension. We show that the inefficiency of learning the optimal representation is not inevitable -- we present a simple modification to the gradient descent update that greatly speeds up convergence empirically.
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
Venue: arXiv cs.DS 2021
Year: 2021

In the online non-metric variant of the facility location problem, there is a given graph consisting of a set $F$ of facilities (each with a certain opening cost), a set $C$ of potential clients, and weighted connections between them. The online part of the input is a sequence of clients from $C$, and in response to any requested client, an online algorithm may open an additional subset of facilities and must connect the given client to an open facility. We give an online, polynomial-time deterministic algorithm for this problem, with a competitive ratio of $O(\log |F| \cdot (\log |C| + \log \log |F|))$. The result is optimal up to loglog factors. Our algorithm improves over the $O((\log |C| + \log |F|) \cdot (\log |C| + \log \log |F|))$-competitive construction that first reduces the facility location instance to a set cover one and then later solves such instance using the deterministic algorithm by Alon et al. [TALG 2006]. This is an asymptotic improvement in a typical scenario where $|F| \ll |C|$. We achieve this by a more direct approach: we design an algorithm for a fractional relaxation of the non-metric facility location problem with clustered facilities. To handle the constraints of such non-covering LP, we combine the dual fitting and multiplicative weight updates approach. By maintaining certain additional monotonicity properties of the created fractional solution, we can handle the dependencies between facilities and connections in a rounding routine. Our result, combined with the algorithm by Naor et al. [FOCS 2011] yields the first deterministic algorithm for the online node-weighted Steiner tree problem. The resulting competitive ratio is $O(\log k \cdot \log^2 \ell)$ on graphs of $\ell$ nodes and $k$ terminals.
Unsupervised Spatio-temporal Latent Feature Clustering for Multiple-object Tracking and Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Assigning consistent temporal identifiers to multiple moving objects in a video sequence is a challenging problem. A solution to that problem would have immediate ramifications in multiple object tracking and segmentation problems. We propose a strategy that treats the temporal identification task as a spatio-temporal clustering problem. We propose an unsupervised learning approach using a convolutional and fully connected autoencoder, which we call deep heterogeneous autoencoder, to learn discriminative features from segmentation masks and detection bounding boxes. We extract masks and their corresponding bounding boxes from a pretrained instance segmentation network and train the autoencoders jointly using task-dependent uncertainty weights to generate common latent features. We then construct constraints graphs that encourage associations among objects that satisfy a set of known temporal conditions. The feature vectors and the constraints graphs are then provided to the kmeans clustering algorithm to separate the corresponding data points in the latent space. We evaluate the performance of our method using challenging synthetic and real-world multiple-object video datasets. Our results show that our technique outperforms several state-of-the-art methods.
On the hop-constrained Steiner tree problems
Venue: arXiv cs.DS 2021
Year: 2021

The hop-constrained Steiner tree problem (HSTP) is a generalization of the classical Steiner tree problem. It asks for a minimum cost subtree that spans some specified nodes of a given graph, such that the number of edges between each node of the tree and its root respects a given hop limit. This NP-hard problem has many variants, often modeled as integer linear programs. Two of the models are so-called assignment and partial-ordering based models, which yield (up to our knowledge) the best two state-of-the-art formulations for the variant Steiner tree problem with revenues, budgets, and hop constraints (STPRBH). The solution of the HSTP and its variants such as the STPRBH and the hop-constrained minimum spanning tree problem (HMSTP) is a hop-constrained tree, a rooted tree whose depth is bounded by a given hop limit. This paper provides some theoretical results that show the polyhedral advantages of the partial-ordering model over the assignment model for this class of problems. Computational results in this paper and the literature for the HSTP, STPRBH, and HMSTP show that the partial-ordering model outperforms the assignment model in practice, too; it has better linear programming relaxation and solves more instances.
SpaceNet: Make Free Space For Continual Learning
Venue: arXiv cs.LG 2021
Year: 2021

The continual learning (CL) paradigm aims to enable neural networks to learn tasks continually in a sequential fashion. The fundamental challenge in this learning paradigm is catastrophic forgetting previously learned tasks when the model is optimized for a new task, especially when their data is not accessible. Current architectural-based methods aim at alleviating the catastrophic forgetting problem but at the expense of expanding the capacity of the model. Regularization-based methods maintain a fixed model capacity; however, previous studies showed the huge performance degradation of these methods when the task identity is not available during inference (e.g. class incremental learning scenario). In this work, we propose a novel architectural-based method referred as SpaceNet for class incremental learning scenario where we utilize the available fixed capacity of the model intelligently. SpaceNet trains sparse deep neural networks from scratch in an adaptive way that compresses the sparse connections of each task in a compact number of neurons. The adaptive training of the sparse connections results in sparse representations that reduce the interference between the tasks. Experimental results show the robustness of our proposed method against catastrophic forgetting old tasks and the efficiency of SpaceNet in utilizing the available capacity of the model, leaving space for more tasks to be learned. In particular, when SpaceNet is tested on the well-known benchmarks for CL: split MNIST, split Fashion-MNIST, and CIFAR-10/100, it outperforms regularization-based methods by a big performance gap. Moreover, it achieves better performance than architectural-based methods without model expansion and achieved comparable results with rehearsal-based methods, while offering a huge memory reduction.