OpenRaiser/Intern-Atlas huggingface dataset:
Edge Augmentation for Large-Scale Sketch Recognition without Sketches
Venue: arXiv cs.CV 2022
Year: 2022

This work addresses scaling up the sketch classification task into a large number of categories. Collecting sketches for training is a slow and tedious process that has so far precluded any attempts to large-scale sketch recognition. We overcome the lack of training sketch data by exploiting labeled collections of natural images that are easier to obtain. To bridge the domain gap we present a novel augmentation technique that is tailored to the task of learning sketch recognition from a training set of natural images. Randomization is introduced in the parameters of edge detection and edge selection. Natural images are translated to a pseudo-novel domain called "randomized Binary Thin Edges" (rBTE), which is used as a training domain instead of natural images. The ability to scale up is demonstrated by training CNN-based sketch recognition of more than 2.5 times larger number of categories than used previously. For this purpose, a dataset of natural images from 874 categories is constructed by combining a number of popular computer vision datasets. The categories are selected to be suitable for sketch recognition. To estimate the performance, a subset of 393 categories with sketches is also collected.
Review of Hybrid Load Balancing Algorithms in Cloud Computing Environment
Venue: arXiv cs.DC 2022
Year: 2022

In cloud computing environment, load balancing is a key issue which is required to distribute the dynamic workload over multiple machines to make certain that no single machine is overloaded. In recent research, many organizations lose significant part of their revenues in handling the requests given by the clients over the web servers i.e. unable to balance the load for web servers which results in loss of data, delay in time and increased costs. Various static and dynamic algorithms have been proposed and implemented in the past but this have not been fully efficient for load balancing. This gave room to hybrid algorithms. Hybrid methods inherit the properties from both static and dynamic load balancing techniques and attempts at overcoming the limitation of both algorithms. This paper is a study of various hybrid load balancing algorithms in cloud computing environment.
RL-PGO: Reinforcement Learning-based Planar Pose-Graph Optimization
Venue: arXiv cs.RO 2022
Year: 2022

The objective of pose SLAM or pose-graph optimization (PGO) is to estimate the trajectory of a robot given odometric and loop closing constraints. State-of-the-art iterative approaches typically involve the linearization of a non-convex objective function and then repeatedly solve a set of normal equations. Furthermore, these methods may converge to a local minima yielding sub-optimal results. In this work, we present to the best of our knowledge the first Deep Reinforcement Learning (DRL) based environment and proposed agent for 2D pose-graph optimization. We demonstrate that the pose-graph optimization problem can be modeled as a partially observable Markov Decision Process and evaluate performance on real-world and synthetic datasets. The proposed agent outperforms state-of-the-art solver g2o on challenging instances where traditional nonlinear least-squares techniques may fail or converge to unsatisfactory solutions. Experimental results indicate that iterative-based solvers bootstrapped with the proposed approach allow for significantly higher quality estimations. We believe that reinforcement learning-based PGO is a promising avenue to further accelerate research towards globally optimal algorithms. Thus, our work paves the way to new optimization strategies in the 2D pose SLAM domain.
Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework
Venue: arXiv cs.LG 2022
Year: 2022

Online learning in large-scale structured bandits is known to be challenging due to the curse of dimensionality. In this paper, we propose a unified meta-learning framework for a general class of structured bandit problems where the parameter space can be factorized to item-level. The novel bandit algorithm is general to be applied to many popular problems,scalable to the huge parameter and action spaces, and robust to the specification of the generalization model. At the core of this framework is a Bayesian hierarchical model that allows information sharing among items via their features, upon which we design a meta Thompson sampling algorithm. Three representative examples are discussed thoroughly. Both theoretical analysis and numerical results support the usefulness of the proposed method.
Perceptions of the State of D&I and D&I Initiative in the ASF
Venue: arXiv cs.SE 2022
Year: 2022

Open Source Software (OSS) Foundations and projects are investing in creating Diversity and Inclusion (D&I) initiatives. However, little is known about contributors' perceptions about the usefulness and success of such initiatives. We aim to close this gap by investigating how contributors perceive the state of D&I in their community. In collaboration with the Apache Software Foundation (ASF), we surveyed 600+ OSS contributors and conducted 11 follow-up interviews. We used mixed methods to analyze our data-quantitative analysis of Likert-scale questions and qualitative analysis of open-ended survey question and the interviews to understand contributors' perceptions and critiques of the D&I initiative and how to improve it. Our results indicate that the ASF contributors felt that the state of D&I was still lacking, especially regarding gender, seniority, and English proficiency. Regarding the D&I initiative, some participants felt that the effort was unnecessary, while others agreed with the effort but critiqued its implementation. These findings show that D&I initiatives in OSS communities are a good start, but there is room for improvements. Our results can inspire the creation of new and the refinement of current initiatives.
A Dual Neighborhood Hypergraph Neural Network for Change Detection in VHR Remote Sensing Images
Venue: arXiv cs.CV 2022
Year: 2022

The very high spatial resolution (VHR) remote sensing images have been an extremely valuable source for monitoring changes occurred on the earth surface. However, precisely detecting relevant changes in VHR images still remains a challenge, due to the complexity of the relationships among ground objects. To address this limitation, a dual neighborhood hypergraph neural network is proposed in this article, which combines the multiscale superpixel segmentation and hypergraph convolution to model and exploit the complex relationships. First, the bi-temporal image pairs are segmented under two scales and fed to a pre-trained U-net to obtain node features by treating each object under the fine scale as a node. The dual neighborhood is then defined using the father-child and adjacent relationships of the segmented objects to construct the hypergraph, which permits models to represent the higher-order structured information far more complex than just pairwise relationships. The hypergraph convolutions are conducted on the constructed hypergraph to propagate the label information from a small amount of labeled nodes to the other unlabeled ones by the node-edge-node transform. Moreover, to alleviate the problem of imbalanced sample, the focal loss function is adopted to train the hypergraph neural network. The experimental results on optical, SAR and heterogeneous optical/SAR data sets demonstrate that the proposed method comprises better effectiveness and robustness compared to many state-of-the-art methods.
Parallel algorithm for pattern matching problems under substring consistent equivalence relations
Venue: arXiv cs.DS 2022
Year: 2022

Given a text and a pattern over an alphabet, the pattern matching problem searches for all occurrences of the pattern in the text. An equivalence relation $\approx$ is called a substring consistent equivalence relation (SCER), if for two strings $X$ and $Y$, $X \approx Y$ implies $|X| = |Y|$ and $X[i:j] \approx Y[i:j]$ for all $1 \le i \le j \le |X|$. In this paper, we propose an efficient parallel algorithm for pattern matching under any SCER using the"duel-and-sweep" paradigm. For a pattern of length $m$ and a text of length $n$, our algorithm runs in $O(ξ_m^\mathrm{t} \log^2 m)$ time and $O(ξ_m^\mathrm{w} \cdot n \log^2 m)$ work, with $O(τ_n^\mathrm{t} + ξ_m^\mathrm{t} \log^2 m)$ time and $O(τ_n^\mathrm{w} + ξ_m^\mathrm{w} \cdot m \log^2 m)$ work preprocessing on the Priority Concurrent Read Concurrent Write Parallel Random-Access Machines (P-CRCW PRAM).
Approximation Algorithms for Flexible Graph Connectivity
Venue: arXiv cs.DS 2022
Year: 2022

We present approximation algorithms for several network design problems in the model of Flexible Graph Connectivity (Adjiashvili, Hommelsheim and Mühlenthaler, "Flexible Graph Connectivity", Math. Program. pp. 1-33 (2021), and IPCO 2020: pp. 13-26). Let $k\geq 1$, $p\geq 1$ and $q\geq 0$ be integers. In an instance of the $(p,q)$-Flexible Graph Connectivity problem, denoted $(p,q)$-FGC, we have an undirected connected graph $G = (V,E)$, a partition of $E$ into a set of safe edges $S$ and a set of unsafe edges $U$, and nonnegative costs $c: E\to\Re$ on the edges. A subset $F \subseteq E$ of edges is feasible for the $(p,q)$-FGC problem if for any subset $F'$ of unsafe edges with $|F'|\leq q$, the subgraph $(V, F \setminus F')$ is $p$-edge connected. The algorithmic goal is to find a feasible solution $F$ that minimizes $c(F) = \sum_{e \in F} c_e$. We present a simple $2$-approximation algorithm for the $(1,1)$-FGC problem via a reduction to the minimum-cost rooted $2$-arborescence problem. This improves on the $2.527$-approximation algorithm of Adjiashvili et al. Our $2$-approximation algorithm for the $(1,1)$-FGC problem extends to a $(k+1)$-approximation algorithm for the $(1,k)$-FGC problem. We present a $4$-approximation algorithm for the $(p,1)$-FGC problem, and an $O(q\log|V|)$-approximation algorithm for the $(p,q)$-FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted $(1,1)$-FGC problem by presenting a $16/11$-approximation algorithm. The $(p,q)$-FGC problem is related to the well-known Capacitated $k$-Connected Subgraph problem (denoted Cap-k-ECSS) that arises in the area of Capacitated Network Design. We give a $\min(k,2 u_{max})$-approximation algorithm for the Cap-k-ECSS problem, where $u_{max}$ denotes the maximum capacity of an edge.
Deep Learning-Based Inverse Design for Engineering Systems: Multidisciplinary Design Optimization of Automotive Brakes
Venue: arXiv cs.LG 2022
Year: 2022

The braking performance of the brake system is a target performance that must be considered for vehicle development. Apparent piston travel (APT) and drag torque are the most representative factors for evaluating braking performance. In particular, as the two performance factors have a conflicting relationship with each other, a multidisciplinary design optimization (MDO) approach is required for brake design. However, the computational cost of MDO increases as the number of disciplines increases. Recent studies on inverse design that use deep learning (DL) have established the possibility of instantly generating an optimal design that can satisfy the target performance without implementing an iterative optimization process. This study proposes a DL-based multidisciplinary inverse design (MID) that simultaneously satisfies multiple targets, such as the APT and drag torque of the brake system. Results show that the proposed inverse design can find the optimal design more efficiently compared with the conventional optimization methods, such as backpropagation and sequential quadratic programming. The MID achieved a similar performance to the single-disciplinary inverse design in terms of accuracy and computational cost. A novel design was derived on the basis of results, and the same performance was satisfied as that of the existing design.
Improving Candidate Retrieval with Entity Profile Generation for Wikidata Entity Linking
Venue: arXiv cs.CL 2022
Year: 2022

Entity linking (EL) is the task of linking entity mentions in a document to referent entities in a knowledge base (KB). Many previous studies focus on Wikipedia-derived KBs. There is little work on EL over Wikidata, even though it is the most extensive crowdsourced KB. The scale of Wikidata can open up many new real-world applications, but its massive number of entities also makes EL challenging. To effectively narrow down the search space, we propose a novel candidate retrieval paradigm based on entity profiling. Wikidata entities and their textual fields are first indexed into a text search engine (e.g., Elasticsearch). During inference, given a mention and its context, we use a sequence-to-sequence (seq2seq) model to generate the profile of the target entity, which consists of its title and description. We use the profile to query the indexed search engine to retrieve candidate entities. Our approach complements the traditional approach of using a Wikipedia anchor-text dictionary, enabling us to further design a highly effective hybrid method for candidate retrieval. Combined with a simple cross-attention reranker, our complete EL framework achieves state-of-the-art results on three Wikidata-based datasets and strong performance on TACKBP-2010.
Negation-Closure for JSON Schema
Venue: arXiv cs.DB 2022
Year: 2022

JSON Schema is an evolving standard for describing families of JSON documents. It is a logical language, based on a set of assertions that describe features of the JSON value under analysis and on logical or structural combinators for these assertions, including a negation operator. Most logical languages with negation enjoy negation closure, that is, for every operator they have a negation dual that expresses its negation. We show that this is not the case for JSON Schema, we study how that changed with the latest versions of the Draft, and we discuss how the language may be enriched accordingly. In the process, we define an algebraic reformulation of JSON Schema, which we successfully employed in a prototype system for generating schema witnesses.
Technical Debt and Maintainability: How do tools measure it?
Venue: arXiv cs.SE 2022
Year: 2022

The technical state of software, i.e., its technical debt (TD) and maintainability are of increasing interest as ever more software is developed and deployed. Since td and maintainability are neither uniformly defined, not easy to understand, nor directly measurable, practitioners are likely to apply readily available tools to assess TD or maintainability and they may rely on the reported results without properly understanding what they embody. In this paper, we: a) methodically identify 11 readily available tools that measure TD or maintainability, b) present an in-depth investigation on how each of these tools measures and computes TD or maintainability, and c) compare these tools and their characteristics. We find that contemporary tools focus mainly on internal qualities of software, i.e., quality of source code, that they define and measure TD or maintainability in widely different ways, that most of the tools measure TD or maintainability opaquely, and that it is not obvious why the measure of one tool is more trustworthy or representative than the one of another.
Interpretable Concept-based Prototypical Networks for Few-Shot Learning
Venue: arXiv cs.LG 2022
Year: 2022

Few-shot learning aims at recognizing new instances from classes with limited samples. This challenging task is usually alleviated by performing meta-learning on similar tasks. However, the resulting models are black-boxes. There has been growing concerns about deploying black-box machine learning models and FSL is not an exception in this regard. In this paper, we propose a method for FSL based on a set of human-interpretable concepts. It constructs a set of metric spaces associated with the concepts and classifies samples of novel classes by aggregating concept-specific decisions. The proposed method does not require concept annotations for query samples. This interpretable method achieved results on a par with six previously state-of-the-art black-box FSL methods on the CUB fine-grained bird classification dataset.
Pareto-Rational Verification
Venue: arXiv cs.GT 2022
Year: 2022

We study the rational verification problem which consists in verifying the correctness of a system executing in an environment that is assumed to behave rationally. We consider the model of rationality in which the environment only executes behaviors that are Pareto-optimal with regard to its set of objectives, given the behavior of the system (which is committed in advance of any interaction). We examine two ways of specifying this behavior, first by means of a deterministic Moore machine, and then by lifting its determinism. In the latter case the machine may embed several different behaviors for the system, and the universal rational verification problem aims at verifying that all of them are correct when the environment is rational. For parity objectives, we prove that the Pareto-rational verification problem is co-NP-complete and that its universal version is in PSPACE and both NP-hard and co-NP-hard. For Boolean Büchi objectives, the former problem is $Π_2\mathsf{P}$-complete and the latter is PSPACE-complete. We also study the case where the objectives are expressed using LTL formulas and show that the first problem is PSPACE-complete, and that the second is 2EXPTIME-complete. Both problems are also shown to be fixed-parameter tractable (FPT) for parity and Boolean Büchi objectives. Finally, we evaluate two variations of the FPT algorithm proposed to solve the Pareto-rational verification problem on a parametric toy example as well as on randomly generated instances.
Machine learning techniques to identify antibiotic resistance in patients diagnosed with various skin and soft tissue infections
Venue: arXiv cs.LG 2022
Year: 2022

Skin and soft tissue infections (SSTIs) are among the most frequently observed diseases in ambulatory and hospital settings. Resistance of diverse bacterial pathogens to antibiotics is a significant cause of severe SSTIs, and treatment failure results in morbidity, mortality, and increased cost of hospitalization. Therefore, antimicrobial surveillance is essential to predict antibiotic resistance trends and monitor the results of medical interventions. To address this, we developed machine learning (ML) models (deep and conventional algorithms) to predict antimicrobial resistance using antibiotic susceptibility testing (ABST) data collected from patients clinically diagnosed with primary and secondary pyoderma over a period of one year. We trained an individual ML algorithm on each antimicrobial family to determine whether a Gram-Positive Cocci (GPC) or Gram-Negative Bacilli (GNB) bacteria will resist the corresponding antibiotic. For this purpose, clinical and demographic features from the patient and data from ABST were employed in training. We achieved an Area Under the Curve (AUC) of 0.68-0.98 in GPC and 0.56-0.93 in GNB bacteria, depending on the antimicrobial family. We also conducted a correlation analysis to determine the linear relationship between each feature and antimicrobial families in different bacteria. ML techniques suggest that a predictable nonlinear relationship exists between patients' clinical-demographic characteristics and antibiotic resistance; however, the accuracy of this prediction depends on the type of the antimicrobial family.
The Golden Circle: Creating Socio-technical Alignment in Content Moderation
Venue: arXiv cs.SI 2022
Year: 2022

This paper outlines a conceptual framework titled The Golden Circle that describes the roles of actors at individual, organizational, and societal levels, and their dynamics in the content moderation ecosystem. Centering harm reduction and context moderation, it argues that the ML community must attend to multimodal content moderation solutions, align their work with their organizations' goals and values, and pay attention to the ever changing social contexts in which their sociotechnical systems are embedded. This is done by accounting for the why, how, and what of content moderation from a sociological and technical lens.
ESW Edge-Weights : Ensemble Stochastic Watershed Edge-Weights for Hyperspectral Image Classification
Venue: arXiv cs.CV 2022
Year: 2022

Hyperspectral image (HSI) classification is a topic of active research. One of the main challenges of HSI classification is the lack of reliable labelled samples. Various semi-supervised and unsupervised classification methods are proposed to handle the low number of labelled samples. Chief among them are graph convolution networks (GCN) and their variants. These approaches exploit the graph structure for semi-supervised and unsupervised classification. While several of these methods implicitly construct edge-weights, to our knowledge, not much work has been done to estimate the edge-weights explicitly. In this article, we estimate the edge-weights explicitly and use them for the downstream classification tasks - both semi-supervised and unsupervised. The proposed edge-weights are based on two key insights - (a) Ensembles reduce the variance and (b) Classes in HSI datasets and feature similarity have only one-sided implications. That is, while same classes would have similar features, similar features do not necessarily imply the same classes. Exploiting these, we estimate the edge-weights using an aggregate of ensembles of watersheds over subsamples of features. These edge weights are evaluated for both semi-supervised and unsupervised classification tasks. The evaluation for semi-supervised tasks uses Random-Walk based approach. For the unsupervised case, we use a simple filter using a graph convolution network (GCN). In both these cases, the proposed edge weights outperform the traditional approaches to compute edge-weights - Euclidean distances and cosine similarities. Fascinatingly, with the proposed edge-weights, the simplest GCN obtained results comparable to the recent state-of-the-art.
Keyword Optimization in Sponsored Search Advertising: A Multi-Level Computational Framework
Venue: arXiv cs.IR 2022
Year: 2022

In sponsored search advertising, keywords serve as an essential bridge linking advertisers, search users and search engines. Advertisers have to deal with a series of keyword decisions throughout the entire lifecycle of search advertising campaigns. This paper proposes a multi-level and closed-form computational framework for keyword optimization (MKOF) to support various keyword decisions. Based on this framework, we develop corresponding optimization strategies for keyword targeting, keyword assignment and keyword grouping at different levels (e.g., market, campaign and adgroup). With two real-world datasets obtained from past search advertising campaigns, we conduct computational experiments to evaluate our keyword optimization framework and instantiated strategies. Experimental results show that our method can approach the optimal solution in a steady way, and it outperforms two baseline keyword strategies commonly used in practice. The proposed MKOF framework also provides a valid experimental environment to implement and assess various keyword strategies in sponsored search advertising.