OpenRaiser/Intern-Atlas huggingface dataset:
Plane augmentation of plane graphs to meet parity constraints
Venue: arXiv cs.CG 2020
Year: 2020

A plane topological graph $G=(V,E)$ is a graph drawn in the plane whose vertices are points in the plane and whose edges are simple curves that do not intersect, except at their endpoints. Given a plane topological graph $G=(V,E)$ and a set $C_G$ of parity constraints, in which every vertex has assigned a parity constraint on its degree, either even or odd, we say that $G$ is \emph{topologically augmentable} to meet $C_G$ if there exits a plane topological graph $H$ on the same set of vertices, such that $G$ and $H$ are edge-disjoint and their union is a plane topological graph that meets all parity constraints. In this paper, we prove that the problem of deciding if a plane topological graph is topologically augmentable to meet parity constraints is $\mathcal{NP}$-complete, even if the set of vertices that must change their parities is $V$ or the set of vertices with odd degree. In particular, deciding if a plane topological graph can be augmented to a Eulerian plane topological graph is $\mathcal{NP}$-complete. Analogous complexity results are obtained, when the augmentation must be done by a plane topological perfect matching between the vertices not meeting their parities. We extend these hardness results to planar graphs, when the augmented graph must be planar, and to plane geometric graphs (plane topological graphs whose edges are straight-line segments). In addition, when it is required that the augmentation is made by a plane geometric perfect matching between the vertices not meeting their parities, we also prove that this augmentation problem is $\mathcal{NP}$-complete for plane geometric trees and paths. For the particular family of maximal outerplane graphs, we characterize maximal outerplane graphs that are topological augmentable to satisfy a set of parity constraints.
AI4D -- African Language Dataset Challenge
Venue: arXiv cs.CL 2020
Year: 2020

As language and speech technologies become more advanced, the lack of fundamental digital resources for African languages, such as data, spell checkers and Part of Speech taggers, means that the digital divide between these languages and others keeps growing. This work details the organisation of the AI4D - African Language Dataset Challenge, an effort to incentivize the creation, organization and discovery of African language datasets through a competitive challenge. We particularly encouraged the submission of annotated datasets which can be used for training task-specific supervised machine learning models.
Harnessing spatial homogeneity of neuroimaging data: patch individual filter layers for CNNs
Venue: arXiv cs.CV 2020
Year: 2020

Neuroimaging data, e.g. obtained from magnetic resonance imaging (MRI), is comparably homogeneous due to (1) the uniform structure of the brain and (2) additional efforts to spatially normalize the data to a standard template using linear and non-linear transformations. Convolutional neural networks (CNNs), in contrast, have been specifically designed for highly heterogeneous data, such as natural images, by sliding convolutional filters over different positions in an image. Here, we suggest a new CNN architecture that combines the idea of hierarchical abstraction in neural networks with a prior on the spatial homogeneity of neuroimaging data: Whereas early layers are trained globally using standard convolutional layers, we introduce for higher, more abstract layers patch individual filters (PIF). By learning filters in individual image regions (patches) without sharing weights, PIF layers can learn abstract features faster and with fewer samples. We thoroughly evaluated PIF layers for three different tasks and data sets, namely sex classification on UK Biobank data, Alzheimer's disease detection on ADNI data and multiple sclerosis detection on private hospital data. We demonstrate that CNNs using PIF layers result in higher accuracies, especially in low sample size settings, and need fewer training epochs for convergence. To the best of our knowledge, this is the first study which introduces a prior on brain MRI for CNN learning.
Process Symmetry in Probabilistic Transducers
Venue: arXiv cs.LO 2020
Year: 2020

Model checking is the process of deciding whether a system satisfies a given specification. Often, when the setting comprises multiple processes, the specifications are over sets of input and output signals that correspond to individual processes. Then, many of the properties one wishes to specify are symmetric with respect to the processes identities. In this work, we consider the problem of deciding whether the given system exhibits symmetry with respect to the processes' identities. When the system is symmetric, this gives insight into the behaviour of the system, as well as allows the designer to use only representative specifications, instead of iterating over all possible process identities. Specifically, we consider probabilistic systems, and we propose several variants of symmetry. We start with precise symmetry, in which, given a permutation $π$, the system maintains the exact distribution of permuted outputs, given a permuted inputs. We proceed to study approximate versions of symmetry, including symmetry induced by small $L_\infty$ norm, variants of Parikh-image based symmetry, and qualitative symmetry. For each type of symmetry, we consider the problem of deciding whether a given system exhibits this type of symmetry.
Online Boosting with Bandit Feedback
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of online boosting for regression tasks, when only limited information is available to the learner. We give an efficient regret minimization method that has two implications: an online boosting algorithm with noisy multi-point bandit feedback, and a new projection-free online convex optimization algorithm with stochastic gradient, that improves state-of-the-art guarantees in terms of efficiency.
Total Domination in Unit Disk Graphs
Venue: arXiv cs.DS 2020
Year: 2020

Let $G=(V,E)$ be an undirected graph. We call $D_t \subseteq V$ as a total dominating set (TDS) of $G$ if each vertex $v \in V$ has a dominator in $D$ other than itself. Here we consider the TDS problem in unit disk graphs, where the objective is to find a minimum cardinality total dominating set for an input graph. We prove that the TDS problem is NP-hard in unit disk graphs. Next, we propose an 8-factor approximation algorithm for the problem. The running time of the proposed approximation algorithm is $O(n \log k)$, where $n$ is the number of vertices of the input graph and $k$ is output size. We also show that TDS problem admits a PTAS in unit disk graphs.
AM-DCGAN: Analog Memristive Hardware Accelerator for Deep Convolutional Generative Adversarial Networks
Venue: arXiv cs.ET 2020
Year: 2020

Generative Adversarial Network (GAN) is a well known computationally complex algorithm requiring signficiant computational resources in software implementations including large amount of data to be trained. This makes its implementation in edge devices with conventional microprocessor hardware a slow and difficult task. In this paper, we propose to accelerate the computationally intensive GAN using memristive neural networks in analog domain. We present a fully analog hardware design of Deep Convolutional GAN (DCGAN) based on CMOS-memristive convolutional and deconvolutional networks simulated using 180nm CMOS technology.
HCMS at SemEval-2020 Task 9: A Neural Approach to Sentiment Analysis for Code-Mixed Texts
Venue: arXiv cs.CL 2020
Year: 2020

Problems involving code-mixed language are often plagued by a lack of resources and an absence of materials to perform sophisticated transfer learning with. In this paper we describe our submission to the Sentimix Hindi-English task involving sentiment classification of code-mixed texts, and with an F1 score of 67.1%, we demonstrate that simple convolution and attention may well produce reasonable results.
Detecting and Enumerating Small Induced Subgraphs in $c$-Closed Graphs
Venue: arXiv cs.DS 2020
Year: 2020

Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called $c$-closure, for a parameterized study of clique enumeration problems. A graph $G$ is $c$-closed if every pair of vertices with at least $c$ common neighbors is adjacent. The $c$-closure of $G$ is the smallest $c$ such that $G$ is $c$-closed. We systematically explore the impact of $c$-closure on the computational complexity of detecting and enumerating small induced subgraphs. More precisely, for each graph $H$ on three or four vertices, we investigate parameterized polynomial-time algorithms for detecting $H$ and for enumerating all occurrences of $H$ in a given $c$-closed graph.
NITS-Hinglish-SentiMix at SemEval-2020 Task 9: Sentiment Analysis For Code-Mixed Social Media Text Using an Ensemble Model
Venue: arXiv cs.CL 2020
Year: 2020

Sentiment Analysis is the process of deciphering what a sentence emotes and classifying them as either positive, negative, or neutral. In recent times, India has seen a huge influx in the number of active social media users and this has led to a plethora of unstructured text data. Since the Indian population is generally fluent in both Hindi and English, they end up generating code-mixed Hinglish social media text i.e. the expressions of Hindi language, written in the Roman script alongside other English words. The ability to adequately comprehend the notions in these texts is truly necessary. Our team, rns2020 participated in Task 9 at SemEval2020 intending to design a system to carry out the sentiment analysis of code-mixed social media text. This work proposes a system named NITS-Hinglish-SentiMix to viably complete the sentiment analysis of such code-mixed Hinglish text. The proposed framework has recorded an F-Score of 0.617 on the test data.
Revisiting Locality in Binary-Integer Representations
Venue: arXiv cs.NE 2020
Year: 2020

Mutation and recombination operators play a key role in determining the speed and quality of Genetic and Evolutionary Algorithms (GEAs). Prior work has analyzed the effects of these operators on genotypic variation, often using locality metrics that measure the sensitivity and stability of genotype-phenotype representations to these operators. In this paper, we focus on an important subset of representations, namely nonredundant bitstring-to-integer representations, and analyze them through the lens of Rothlauf's widely used locality metrics. We first define locality metrics equivalent to Rothlauf's that are tailored to our domain: the \textit{point locality} for single-bit mutation and \textit{general locality} for recombination. With these definitions, we derive tight bounds and a closed form expected value for point locality. For general locality we show that it is asymptotically equivalent across all representations and operators. We also recreate three established GEA experiments to understand the predictive power of point locality on GEA performance, focusing on two popular and often juxtaposed representations: standard binary and binary reflected Gray. We show that standard binary has provably no worse locality than any Gray encoding, including binary reflected Gray. We discuss this result in the context of previous studies that found binary reflected Gray to outperform standard binary, and we argue that locality cannot be the explanation for strong performance. Finally, we provide empirical evidence that weak point locality representations can be beneficial to performance in the exploration phase of the GEA, while strong point locality representations are more beneficial in the exploitation phase.
Clinical Recommender System: Predicting Medical Specialty Diagnostic Choices with Neural Network Ensembles
Venue: arXiv cs.LG 2020
Year: 2020

The growing demand for key healthcare resources such as clinical expertise and facilities has motivated the emergence of artificial intelligence (AI) based decision support systems. We address the problem of predicting clinical workups for specialty referrals. As an alternative for manually-created clinical checklists, we propose a data-driven model that recommends the necessary set of diagnostic procedures based on the patients' most recent clinical record extracted from the Electronic Health Record (EHR). This has the potential to enable health systems expand timely access to initial medical specialty diagnostic workups for patients. The proposed approach is based on an ensemble of feed-forward neural networks and achieves significantly higher accuracy compared to the conventional clinical checklists.
The MMI Decoder is Asymptotically Optimal for the Typical Random Code and for the Expurgated Code
Venue: arXiv cs.IT 2020
Year: 2020

We provide two results concerning the optimality of the maximum mutual information (MMI) decoder. First, we prove that the error exponents of the typical random codes under the optimal maximum likelihood (ML) decoder and the MMI decoder are equal. As a corollary to this result, we also show that the error exponents of the expurgated codes under the ML and the MMI decoders are equal. These results strengthen the well known result due to Csiszár and Körner, according to which, these decoders achieve equal random coding error exponents, since the error exponents of the typical random code and the expurgated code are strictly higher than the random coding error exponents, at least at low coding rates. While the universal optimality of the MMI decoder, in the random-coding error exponent sense, is easily proven by commuting the expectation over the channel noise and the expectation over the ensemble, when it comes to typical and expurgated exponents, this commutation can no longer be carried out. Therefore, the proof of the universal optimality of the MMI decoder must be completely different and it turns out to be highly non-trivial.
Locality-Aware Rotated Ship Detection in High-Resolution Remote Sensing Imagery Based on Multi-Scale Convolutional Network
Venue: arXiv cs.CV 2020
Year: 2020

Ship detection has been an active and vital topic in the field of remote sensing for a decade, but it is still a challenging problem due to the large scale variations, the high aspect ratios, the intensive arrangement, and the background clutter disturbance. In this letter, we propose a locality-aware rotated ship detection (LARSD) framework based on a multi-scale convolutional neural network (CNN) to tackle these issues. The proposed framework applies a UNet-like multi-scale CNN to generate multi-scale feature maps with high-level semantic information in high resolution. Then, a rotated anchor-based regression is applied for directly predicting the probability, the edge distances, and the angle of ships. Finally, a locality-aware score alignment is proposed to fix the mismatch between classification results and location results caused by the independence of each subnet. Furthermore, to enlarge the datasets of ship detection, we build a new high-resolution ship detection (HRSD) dataset, where 2499 images and 9269 instances were collected from Google Earth with different resolutions. Experiments based on public dataset HRSC2016 and our HRSD dataset demonstrate that our detection method achieves state-of-the-art performance.
MULTISEM at SemEval-2020 Task 3: Fine-tuning BERT for Lexical Meaning
Venue: arXiv cs.CL 2020
Year: 2020

We present the MULTISEM systems submitted to SemEval 2020 Task 3: Graded Word Similarity in Context (GWSC). We experiment with injecting semantic knowledge into pre-trained BERT models through fine-tuning on lexical semantic tasks related to GWSC. We use existing semantically annotated datasets and propose to approximate similarity through automatically generated lexical substitutes in context. We participate in both GWSC subtasks and address two languages, English and Finnish. Our best English models occupy the third and fourth positions in the ranking for the two subtasks. Performance is lower for the Finnish models which are mid-ranked in the respective subtasks, highlighting the important role of data availability for fine-tuning.
Abstract Interpretation in Formal Argumentation: with a Galois Connection for Abstract Dialectical Frameworks and May-Must Argumentation (First Report)
Venue: arXiv cs.LO 2020
Year: 2020

Labelling-based formal argumentation relies on labelling functions that typically assign one of 3 labels to indicate either acceptance, rejection, or else undecided-to-be-either, to each argument. While a classical labelling-based approach applies globally uniform conditions as to how an argument is to be labelled, they can be determined more locally per argument. Abstract dialectical frameworks (ADF) is a well-known argumentation formalism that belongs to this category, offering a greater labelling flexibility. As the size of an argumentation increases in the numbers of arguments and argument-to-argument relations, however, it becomes increasingly more costly to check whether a labelling function satisfies those local conditions or even whether the conditions are as per the intention of those who had specified them. Some compromise is thus required for reasoning about a larger argumentation. In this context, there is a more recently proposed formalism of may-must argumentation (MMA) that enforces still local but more abstract labelling conditions. We identify how they link to each other in this work. We prove that there is a Galois connection between them, in which ADF is a concretisation of MMA and MMA is an abstraction of ADF. We explore the consequence of abstract interpretation at play in formal argumentation, demonstrating a sound reasoning about the judgement of acceptability/rejectability in ADF from within MMA. As far as we are aware, there is seldom any work that incorporates abstract interpretation into formal argumentation in the literature, and, in the stated context, this work is the first to demonstrate its use and relevance.
JUNLP@SemEval-2020 Task 9:Sentiment Analysis of Hindi-English code mixed data using Grid Search Cross Validation
Venue: arXiv cs.CL 2020
Year: 2020

Code-mixing is a phenomenon which arises mainly in multilingual societies. Multilingual people, who are well versed in their native languages and also English speakers, tend to code-mix using English-based phonetic typing and the insertion of anglicisms in their main language. This linguistic phenomenon poses a great challenge to conventional NLP domains such as Sentiment Analysis, Machine Translation, and Text Summarization, to name a few. In this work, we focus on working out a plausible solution to the domain of Code-Mixed Sentiment Analysis. This work was done as participation in the SemEval-2020 Sentimix Task, where we focused on the sentiment analysis of English-Hindi code-mixed sentences. our username for the submission was "sainik.mahata" and team name was "JUNLP". We used feature extraction algorithms in conjunction with traditional machine learning algorithms such as SVR and Grid Search in an attempt to solve the task. Our approach garnered an f1-score of 66.2\% when tested using metrics prepared by the organizers of the task.
Machine-learned Regularization and Polygonization of Building Segmentation Masks
Venue: arXiv cs.CV 2020
Year: 2020

We propose a machine learning based approach for automatic regularization and polygonization of building segmentation masks. Taking an image as input, we first predict building segmentation maps exploiting generic fully convolutional network (FCN). A generative adversarial network (GAN) is then involved to perform a regularization of building boundaries to make them more realistic, i.e., having more rectilinear outlines which construct right angles if required. This is achieved through the interplay between the discriminator which gives a probability of input image being true and generator that learns from discriminator's response to create more realistic images. Finally, we train the backbone convolutional neural network (CNN) which is adapted to predict sparse outcomes corresponding to building corners out of regularized building segmentation results. Experiments on three building segmentation datasets demonstrate that the proposed method is not only capable of obtaining accurate results, but also of producing visually pleasing building outlines parameterized as polygons.
Towards Improving the Performance of BFT Consensus For Future Permissioned Blockchains
Venue: arXiv cs.DC 2020
Year: 2020

Permissioned Blockchains are increasingly considered in enterprise use-cases, many of which do not require geo-distribution, or even disallow it due to legislation. Examples include country-wide networks, such as Alastria, or those deployed using cloud-based platforms such as IBM Blockchain Platform. We expect these blockchains to eventually run in environments with high bandwidth and low latency modern networks, as well as, advanced programmable hardware accelerators in servers. Even though there is renewed interest in BFT consensus algorithms with various proposals targeting Permissioned Blockchains, related work does not optimize for fast networks and does not incorporate hardware accelerators -- we make the case that doing so will pay off in the long run. To this end, we re-implemented the seminal PBFT algorithm in a way that allows us to measure different configurations of the protocol. Through this we explore the benefits of various common optimization strategies and show that the protocol is unlikely to saturate more than 10Gbps networks without relying on specialized hardware-based offloading. We discuss two concrete ways in which the cost of consensus in Permissioned Blockchains could be reduced in high speed networking environments, namely, offloading to SmartNICs and implementing the protocol on standalone FPGAs.
Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions
Venue: arXiv cs.GT 2020
Year: 2020

We study the problem of finding personalized reserve prices for unit-demand buyers in multi-unit eager VCG auctions with correlated buyers. The input to this problem is a dataset of submitted bids of $n$ buyers in a set of auctions. The goal is to find a vector of reserve prices, one for each buyer, that maximizes the total revenue across all auctions. Roughgarden and Wang (2016) showed that this problem is APX-hard but admits a greedy $\frac{1}{2}$-approximation algorithm. Later, Derakhshan, Golrezai, and Paes Leme (2019) gave an LP-based algorithm achieving a $0.68$-approximation for the (important) special case of the problem with a single-item, thereby beating greedy. We show in this paper that the algorithm of Derakhshan et al. in fact does not beat greedy for the general multi-item problem. This raises the question of whether or not the general problem admits a better-than-$\frac{1}{2}$ approximation. In this paper, we answer this question in the affirmative and provide a polynomial-time algorithm with a significantly better approximation-factor of $0.63$. Our solution is based on a novel linear programming formulation, for which we propose two different rounding schemes. We prove that the best of these two and the no-reserve case (all-zero vector) is a $0.63$-approximation.
Considerations for Eye Tracking Experiments in Information Retrieval
Venue: arXiv cs.HC 2020
Year: 2020

In this survey I discuss ophthalmic neurophysiology and the experimental considerations that must be made to reduce possible noise in an eye-tracking data stream. I also review the history, experiments, technological benefits and limitations of eye-tracking within the information retrieval field. The concepts of aware and adaptive user interfaces are also explored that humbly make an attempt to synthesize work from the fields of industrial engineering and psychophysiology with information retrieval.