OpenRaiser/Intern-Atlas huggingface dataset:
Skeletons and Minimum Energy Scheduling
Venue: arXiv cs.DS 2021
Year: 2021

Consider the problem where $n$ jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor has two available states: a \emph{sleep state} where no energy is consumed but also no processing can take place, and an \emph{active state} which consumes energy at a rate of one, and in which jobs can be processed. Transitioning from the active to the sleep does not incur any further energy cost, but transitioning from the sleep to the active state requires $q$ energy units. Jobs may be preempted and (in the multi-processor case) migrated. The single-processor case of the problem is known to be solvable in polynomial time via an involved dynamic program, whereas the only known approximation algorithm for the multi-processor case attains an approximation factor of $3$ and is based on rounding the solution to a linear programming relaxation of the problem. In this work, we present efficient and combinatorial approximation algorithms for both the single- and the multi-processor setting. Before, only an algorithm based on linear programming was known for the multi-processor case. Our algorithms build upon the concept of a \emph{skeleton}, a basic (and not necessarily feasible) schedule that captures the fact that some processor(s) must be active at some time point during an interval. Finally, we further demonstrate the power of skeletons by providing an $2$-approximation algorithm for the multiprocessor case, thus improving upon the recent breakthrough $3$-approximation result. Our algorithm is based on a novel rounding scheme of a linear-programming relaxation of the problem which incorporates skeletons.
Contrastive Predictive Coding for Anomaly Detection
Venue: arXiv cs.CV 2021
Year: 2021

Reliable detection of anomalies is crucial when deploying machine learning models in practice, but remains challenging due to the lack of labeled data. To tackle this challenge, contrastive learning approaches are becoming increasingly popular, given the impressive results they have achieved in self-supervised representation learning settings. However, while most existing contrastive anomaly detection and segmentation approaches have been applied to images, none of them can use the contrastive losses directly for both anomaly detection and segmentation. In this paper, we close this gap by making use of the Contrastive Predictive Coding model (arXiv:1807.03748). We show that its patch-wise contrastive loss can directly be interpreted as an anomaly score, and how this allows for the creation of anomaly segmentation masks. The resulting model achieves promising results for both anomaly detection and segmentation on the challenging MVTec-AD dataset.
A Survey of Knowledge Graph Embedding and Their Applications
Venue: arXiv cs.IR 2021
Year: 2021

Knowledge Graph embedding provides a versatile technique for representing knowledge. These techniques can be used in a variety of applications such as completion of knowledge graph to predict missing information, recommender systems, question answering, query expansion, etc. The information embedded in Knowledge graph though being structured is challenging to consume in a real-world application. Knowledge graph embedding enables the real-world application to consume information to improve performance. Knowledge graph embedding is an active research area. Most of the embedding methods focus on structure-based information. Recent research has extended the boundary to include text-based information and image-based information in entity embedding. Efforts have been made to enhance the representation with context information. This paper introduces growth in the field of KG embedding from simple translation-based models to enrichment-based models. This paper includes the utility of the Knowledge graph in real-world applications.
Nearest neighbor Methods and their Applications in Design of 5G & Beyond Wireless Networks
Venue: arXiv cs.NI 2021
Year: 2021

In this paper, we present an overview of Nearest neighbor (NN) methods, which are frequently employed for solving classification problems using supervised learning. The article concisely introduces the theoretical background, algorithmic, and implementation aspects along with the key applications. From an application standpoint, this article explores the challenges related to the 5G and beyond wireless networks which can be solved using NN classification techniques.
Dark Patterns in Online Shopping: Of Sneaky Tricks, Perceived Annoyance and Respective Brand Trust
Venue: arXiv cs.HC 2021
Year: 2021

Dark patterns utilize interface elements to trick users into performing unwanted actions. Online shopping websites often employ these manipulative mechanisms so as to increase their potential customer base, to boost their sales, or to optimize their advertising efforts. Although dark patterns are often successful, they clearly inhibit positive user experiences. Particularly, with respect to customers' perceived annoyance and trust put into a given brand, they may have negative effects. To investigate respective connections between the use of dark patterns, users' perceived level of annoyance and their expressed brand trust, we conducted an experiment-based survey. We implemented two versions of a fictitious online shop; i.e. one which used five different types of dark patterns and a similar one without such manipulative user interface elements. A total of $n=204$ participants were then forwarded to one of the two shops (approx. $2/3$ to the shop which used the dark patterns) and asked to buy a specific product. Subsequently, we measured participants' perceived annoyance level, their expressed brand trust and their affinity for technology. Results show a higher level of perceived annoyance with those who used the dark pattern version of the online shop. Also, we found a significant connection between perceived annoyance and participants' expressed brand trust. A connection between participants' affinity for technology and their ability to recognize and consequently counter dark patterns, however, is not supported by our data.
Temporal-aware Language Representation Learning From Crowdsourced Labels
Venue: arXiv cs.CL 2021
Year: 2021

Learning effective language representations from crowdsourced labels is crucial for many real-world machine learning tasks. A challenging aspect of this problem is that the quality of crowdsourced labels suffer high intra- and inter-observer variability. Since the high-capacity deep neural networks can easily memorize all disagreements among crowdsourced labels, directly applying existing supervised language representation learning algorithms may yield suboptimal solutions. In this paper, we propose \emph{TACMA}, a \underline{t}emporal-\underline{a}ware language representation learning heuristic for \underline{c}rowdsourced labels with \underline{m}ultiple \underline{a}nnotators. The proposed approach (1) explicitly models the intra-observer variability with attention mechanism; (2) computes and aggregates per-sample confidence scores from multiple workers to address the inter-observer disagreements. The proposed heuristic is extremely easy to implement in around 5 lines of code. The proposed heuristic is evaluated on four synthetic and four real-world data sets. The results show that our approach outperforms a wide range of state-of-the-art baselines in terms of prediction accuracy and AUC. To encourage the reproducible results, we make our code publicly available at \url{https://github.com/CrowdsourcingMining/TACMA}.
An Uncertainty-Aware, Shareable and Transparent Neural Network Architecture for Brain-Age Modeling
Venue: arXiv cs.LG 2021
Year: 2021

The deviation between chronological age and age predicted from neuroimaging data has been identified as a sensitive risk-marker of cross-disorder brain changes, growing into a cornerstone of biological age-research. However, Machine Learning models underlying the field do not consider uncertainty, thereby confounding results with training data density and variability. Also, existing models are commonly based on homogeneous training sets, often not independently validated, and cannot be shared due to data protection issues. Here, we introduce an uncertainty-aware, shareable, and transparent Monte-Carlo Dropout Composite-Quantile-Regression (MCCQR) Neural Network trained on N=10,691 datasets from the German National Cohort. The MCCQR model provides robust, distribution-free uncertainty quantification in high-dimensional neuroimaging data, achieving lower error rates compared to existing models across ten recruitment centers and in three independent validation samples (N=4,004). In two examples, we demonstrate that it prevents spurious associations and increases power to detect accelerated brain-aging. We make the pre-trained model publicly available.
Deep Learning to Ternary Hash Codes by Continuation
Venue: arXiv cs.CV 2021
Year: 2021

Recently, it has been observed that {0,1,-1}-ternary codes which are simply generated from deep features by hard thresholding, tend to outperform {-1,1}-binary codes in image retrieval. To obtain better ternary codes, we for the first time propose to jointly learn the features with the codes by appending a smoothed function to the networks. During training, the function could evolve into a non-smoothed ternary function by a continuation method. The method circumvents the difficulty of directly training discrete functions and reduces the quantization errors of ternary codes. Experiments show that the generated codes indeed could achieve higher retrieval accuracy.
Towards a Benchmark Set for Program Repair Based on Partial Fixes
Venue: arXiv cs.SE 2021
Year: 2021

Software bugs significantly contribute to software cost and increase the risk of system malfunctioning. In recent years, many automated program-repair approaches have been proposed to automatically fix undesired program behavior. Despite of their great success, specific problems such as fixing bugs with partial fixes still remain unresolved. A partial fix to a known software issue is a programmer's failed attempt to fix the issue the first time. Even though it fails, this fix attempt still conveys important information such as the suspicious software region and the bug type. In this work we do not propose an approach for program repair with partial fixes, but instead answer a preliminary question: Do partial fixes occur often enough, in general, to be relevant for the research area of automated program repair? We crawled 1500 open-source C repositories on GitHub for partial fixes. The result is a benchmark set of 2204 benchmark tasks for automated program repair based on partial fixes. The benchmark set is available open source and open to further contributions and improvement.
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
Venue: arXiv cs.DS 2021
Year: 2021

In the numerical linear algebra community, it was suggested that to obtain nearly optimal bounds for various problems such as rank computation, finding a maximal linearly independent subset of columns (a basis), regression, or low-rank approximation, a natural way would be to resolve the main open question of Nelson and Nguyen (FOCS, 2013). This question is regarding the logarithmic factors in the sketching dimension of existing oblivious subspace embeddings that achieve constant-factor approximation. We show how to bypass this question using a refined sketching technique, and obtain optimal or nearly optimal bounds for these problems. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors, which after first applying known oblivious subspace embeddings, allows us to quickly spread out the mass of the vector so that sampling is now effective. We thereby avoid a logarithmic factor in the sketching dimension that is standard in bounds proven using the matrix Chernoff inequality. For the fundamental problems of rank computation and finding a basis, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013), and are optimal to within a constant factor and a poly(log log(n))-factor, respectively. Further, for constant-factor regression and low-rank approximation we give the first optimal algorithms, for the current matrix multiplication exponent.
AutoFL: Enabling Heterogeneity-Aware Energy Efficient Federated Learning
Venue: arXiv cs.LG 2021
Year: 2021

Federated learning enables a cluster of decentralized mobile devices at the edge to collaboratively train a shared machine learning model, while keeping all the raw training samples on device. This decentralized training approach is demonstrated as a practical solution to mitigate the risk of privacy leakage. However, enabling efficient FL deployment at the edge is challenging because of non-IID training data distribution, wide system heterogeneity and stochastic-varying runtime effects in the field. This paper jointly optimizes time-to-convergence and energy efficiency of state-of-the-art FL use cases by taking into account the stochastic nature of edge execution. We propose AutoFL by tailor-designing a reinforcement learning algorithm that learns and determines which K participant devices and per-device execution targets for each FL model aggregation round in the presence of stochastic runtime variance, system and data heterogeneity. By considering the unique characteristics of FL edge deployment judiciously, AutoFL achieves 3.6 times faster model convergence time and 4.7 and 5.2 times higher energy efficiency for local clients and globally over the cluster of K participants, respectively.
Lower Bound for Sculpture Garden Problem
Venue: arXiv cs.CG 2021
Year: 2021

The purpose of the current study is to investigate a special case of art gallery problem, namely Sculpture Garden Problem. In the said problem, for a given polygon $P$, the ultimate goal is to place the minimum number of guards to define the interior polygon $P$ by applying a monotone Boolean formula composed of the guards. As the findings indicate, the conjecture about the issue that in the worst case, $n-2$ guards are required to describe any $n$-gon (Eppstein et al. 2007) can be conclusively proved.
BEDS-Bench: Behavior of EHR-models under Distributional Shift--A Benchmark
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning has recently demonstrated impressive progress in predictive accuracy across a wide array of tasks. Most ML approaches focus on generalization performance on unseen data that are similar to the training data (In-Distribution, or IND). However, real world applications and deployments of ML rarely enjoy the comfort of encountering examples that are always IND. In such situations, most ML models commonly display erratic behavior on Out-of-Distribution (OOD) examples, such as assigning high confidence to wrong predictions, or vice-versa. Implications of such unusual model behavior are further exacerbated in the healthcare setting, where patient health can potentially be put at risk. It is crucial to study the behavior and robustness properties of models under distributional shift, understand common failure modes, and take mitigation steps before the model is deployed. Having a benchmark that shines light upon these aspects of a model is a first and necessary step in addressing the issue. Recent work and interest in increasing model robustness in OOD settings have focused more on image modality, while the Electronic Health Record (EHR) modality is still largely under-explored. We aim to bridge this gap by releasing BEDS-Bench, a benchmark for quantifying the behavior of ML models over EHR data under OOD settings. We use two open access, de-identified EHR datasets to construct several OOD data settings to run tests on, and measure relevant metrics that characterize crucial aspects of a model's OOD behavior. We evaluate several learning algorithms under BEDS-Bench and find that all of them show poor generalization performance under distributional shift in general. Our results highlight the need and the potential to improve robustness of EHR models under distributional shift, and BEDS-Bench provides one way to measure progress towards that goal.
RAMS-Trans: Recurrent Attention Multi-scale Transformer forFine-grained Image Recognition
Venue: arXiv cs.CV 2021
Year: 2021

In fine-grained image recognition (FGIR), the localization and amplification of region attention is an important factor, which has been explored a lot by convolutional neural networks (CNNs) based approaches. The recently developed vision transformer (ViT) has achieved promising results on computer vision tasks. Compared with CNNs, Image sequentialization is a brand new manner. However, ViT is limited in its receptive field size and thus lacks local attention like CNNs due to the fixed size of its patches, and is unable to generate multi-scale features to learn discriminative region attention. To facilitate the learning of discriminative region attention without box/part annotations, we use the strength of the attention weights to measure the importance of the patch tokens corresponding to the raw images. We propose the recurrent attention multi-scale transformer (RAMS-Trans), which uses the transformer's self-attention to recursively learn discriminative region attention in a multi-scale manner. Specifically, at the core of our approach lies the dynamic patch proposal module (DPPM) guided region amplification to complete the integration of multi-scale image patches. The DPPM starts with the full-size image patches and iteratively scales up the region attention to generate new patches from global to local by the intensity of the attention weights generated at each scale as an indicator. Our approach requires only the attention weights that come with ViT itself and can be easily trained end-to-end. Extensive experiments demonstrate that RAMS-Trans performs better than concurrent works, in addition to efficient CNN models, achieving state-of-the-art results on three benchmark datasets.
A new Method for the in vivo identification of material properties of the human eye. Feasibility analysis based on synthetic data
Venue: arXiv cs.CE 2021
Year: 2021

This paper proposes a new method for in vivo and almost real-time identification of biomechanical properties of the human cornea based on non-contact tonometer data. Further goal is to demonstrate the method's functionality based on synthetic data serving as reference. For this purpose, a finite element model of the human eye is constructed to synthetically generate displacement full-fields from different datasets with keratoconus-like degradations. Then, a new approach based on the equilibrium gap method (EGM) combined with a mechanical morphing approach is proposed and used to identify the material parameters from virtual test data sets. In a further step, random absolute noise is added to the virtual test data to investigate the sensitivity of the new approach to noise. As a result, the proposed method shows a relevant accuracy in identifying material parameters based on displacement full fields. At the same time, the method turns out to work almost in real-time (order of a few minutes on a regular work station) and is thus much faster than inverse problems solved by typical forward approaches. On the other hand, the method shows a noticeable sensitivity to rather small noise amplitudes. However, analysis show that the accuracy is sufficient for the identification of diseased tissue properties.
Generative Pretraining for Paraphrase Evaluation
Venue: arXiv cs.CL 2021
Year: 2021

We introduce ParaBLEU, a paraphrase representation learning model and evaluation metric for text generation. Unlike previous approaches, ParaBLEU learns to understand paraphrasis using generative conditioning as a pretraining objective. ParaBLEU correlates more strongly with human judgements than existing metrics, obtaining new state-of-the-art results on the 2017 WMT Metrics Shared Task. We show that our model is robust to data scarcity, exceeding previous state-of-the-art performance using only $50\%$ of the available training data and surpassing BLEU, ROUGE and METEOR with only $40$ labelled examples. Finally, we demonstrate that ParaBLEU can be used to conditionally generate novel paraphrases from a single demonstration, which we use to confirm our hypothesis that it learns abstract, generalized paraphrase representations.
Tea: Program Repair Using Neural Network Based on Program Information Attention Matrix
Venue: arXiv cs.SE 2021
Year: 2021

The advance in machine learning (ML)-driven natural language process (NLP) points a promising direction for automatic bug fixing for software programs, as fixing a buggy program can be transformed to a translation task. While software programs contain much richer information than one-dimensional natural language documents, pioneering work on using ML-driven NLP techniques for automatic program repair only considered a limited set of such information. We hypothesize that more comprehensive information of software programs, if appropriately utilized, can improve the effectiveness of ML-driven NLP approaches in repairing software programs. As the first step towards proving this hypothesis, we propose a unified representation to capture the syntax, data flow, and control flow aspects of software programs, and devise a method to use such a representation to guide the transformer model from NLP in better understanding and fixing buggy programs. Our preliminary experiment confirms that the more comprehensive information of software programs used, the better ML-driven NLP techniques can perform in fixing bugs in these programs.
From Flow to Fuse: A Cognitive Perspective
Venue: arXiv cs.HC 2021
Year: 2021

The concept of flow is used extensively in HCI, video games, and many other fields, but its prevalent definition is conceptually vague and alternative interpretations have contributed to ambiguity in the literature. To address this, we use cognitive science theory to expose inconsistencies in flow's prevalent definition, and introduce fuse, a concept related to flow but consistent with cognitive science, and defined as the "fusion of activity-related sensory stimuli and awareness". Based on this definition, we develop a preliminary model that hypothesizes fuse's underlying cognitive processes. To illustrate the model's practical value, we derive a set of design heuristics that we exemplify in the context of video games. Together, the fuse definition, model and design heuristics form our theoretical framework, and are a product of rethinking flow from a cognitive perspective with the purpose of improving conceptual clarity and theoretical robustness in the literature.
Spatial Data Generators
Venue: arXiv cs.DB 2021
Year: 2021

This gem describes a standard method for generating synthetic spatial data that can be used in benchmarking and scalability tests. The goal is to improve the reproducibility and increase the trust in experiments on synthetic data by using standard widely acceptable dataset distributions. In addition, this article describes how to assign a unique identifier to each synthetic dataset that can be shared in papers for reproducibility of results. Finally, this gem provides a supplementary material that gives a reference implementation for all the provided distributions.
Adaptive Priority-based Conflict Resolution of IoT Services
Venue: arXiv cs.CY 2021
Year: 2021

We propose a novel conflict resolution framework for IoT services in multi-resident smart homes. An adaptive priority model is developed considering the residents' contextual factors (e.g., age, illness, impairment). The proposed priority model is designed using the concept of the analytic hierarchy process. A set of experiments on real-world datasets are conducted to show the efficiency of the proposed approach.