OpenRaiser/Intern-Atlas huggingface dataset:
A Comparative Study on Crime in Denver City Based on Machine Learning and Data Mining
Venue: arXiv cs.LG 2020
Year: 2020

To ensure the security of the general mass, crime prevention is one of the most higher priorities for any government. An accurate crime prediction model can help the government, law enforcement to prevent violence, detect the criminals in advance, allocate the government resources, and recognize problems causing crimes. To construct any future-oriented tools, examine and understand the crime patterns in the earliest possible time is essential. In this paper, I analyzed a real-world crime and accident dataset of Denver county, USA, from January 2014 to May 2019, which containing 478,578 incidents. This project aims to predict and highlights the trends of occurrence that will, in return, support the law enforcement agencies and government to discover the preventive measures from the prediction rates. At first, I apply several statistical analysis supported by several data visualization approaches. Then, I implement various classification algorithms such as Random Forest, Decision Tree, AdaBoost Classifier, Extra Tree Classifier, Linear Discriminant Analysis, K-Neighbors Classifiers, and 4 Ensemble Models to classify 15 different classes of crimes. The outcomes are captured using two popular test methods: train-test split, and k-fold cross-validation. Moreover, to evaluate the performance flawlessly, I also utilize precision, recall, F1-score, Mean Squared Error (MSE), ROC curve, and paired-T-test. Except for the AdaBoost classifier, most of the algorithms exhibit satisfactory accuracy. Random Forest, Decision Tree, Ensemble Model 1, 3, and 4 even produce me more than 90% accuracy. Among all the approaches, Ensemble Model 4 presented superior results for every evaluation basis. This study could be useful to raise the awareness of peoples regarding the occurrence locations and to assist security agencies to predict future outbreaks of violence in a specific area within a particular time.
Multi-Scale Weight Sharing Network for Image Recognition
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we explore the idea of weight sharing over multiple scales in convolutional networks. Inspired by traditional computer vision approaches, we share the weights of convolution kernels over different scales in the same layers of the network. Although multi-scale feature aggregation and sharing inside convolutional networks are common in practice, none of the previous works address the issue of convolutional weight sharing. We evaluate our weight sharing scheme on two heterogeneous image recognition datasets - ImageNet (object recognition) and Places365-Standard (scene classification). With approximately 25% fewer parameters, our shared-weight ResNet model provides similar performance compared to baseline ResNets. Shared-weight models are further validated via transfer learning experiments on four additional image recognition datasets - Caltech256 and Stanford 40 Actions (object-centric) and SUN397 and MIT Inddor67 (scene-centric). Experimental results demonstrate significant redundancy in the vanilla implementations of the deeper networks, and also indicate that a shift towards increasing the receptive field per parameter may improve future convolutional network architectures.
Hypergraph Cuts with General Splitting Functions
Venue: arXiv cs.DS 2020
Year: 2020

The minimum $s$-$t$ cut problem in graphs is one of the most fundamental problems in combinatorial optimization, and graph cuts underlie algorithms throughout discrete mathematics, theoretical computer science, operations research, and data science. While graphs are a standard model for pairwise relationships, hypergraphs provide the flexibility to model multi-way relationships, and are now a standard model for complex data and systems. However, when generalizing from graphs to hypergraphs, the notion of a "cut hyperedge" is less clear, as a hyperedge's nodes can be split in several ways. Here, we develop a framework for hypergraph cuts by considering the problem of separating two terminal nodes in a hypergraph in a way that minimizes a sum of penalties at split hyperedges. In our setup, different ways of splitting the same hyperedge have different penalties, and the penalty is encoded by what we call a splitting function. Our framework opens a rich space on the foundations of hypergraph cuts. We first identify a natural class of cardinality-based hyperedge splitting functions that depend only on the number of nodes on each side of the split. In this case, we show that the general hypergraph $s$-$t$ cut problem can be reduced to a tractable graph $s$-$t$ cut problem if and only if the splitting functions are submodular. We also identify a wide regime of non-submodular splitting functions for which the problem is NP-hard. We also analyze extensions to multiway cuts with at least three terminal nodes and identify a natural class of splitting functions for which the problem can be reduced in an approximation-preserving way to the node-weighted multiway cut problem in graphs, again subject to a submodularity property. Finally, we outline several open questions on general hypergraph cut problems.
Systematic Convolutional Low Density Generator Matrix Code
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we propose a systematic low density generator matrix (LDGM) code ensemble, which is defined by the Bernoulli process. We prove that, under maximum likelihood (ML) decoding, the proposed ensemble can achieve the capacity of binary-input output symmetric (BIOS) memoryless channels in terms of bit error rate (BER). The proof technique reveals a new mechanism, different from lowering down frame error rate (FER), that the BER can be lowered down by assigning light codeword vectors to light information vectors. The finite length performance is analyzed by deriving an upper bound and a lower bound, both of which are shown to be tight in the high signal-to-noise ratio (SNR) region. To improve the waterfall performance, we construct the systematic convolutional LDGM (SC-LDGM) codes by a random splitting process. The SC-LDGM codes are easily configurable in the sense that any rational code rate can be realized without complex optimization. As a universal construction, the main advantage of the SC-LDGM codes is their near-capacity performance in the waterfall region and predictable performance in the error-floor region that can be lowered down to any target as required by increasing the density of the uncoupled LDGM codes. Numerical results are also provided to verify our analysis.
RAC Drawings in Subcubic Area
Venue: arXiv cs.CG 2020
Year: 2020

In this paper, we study tradeoffs between curve complexity and area of Right Angle Crossing drawings (RAC drawings), which is a challenging theoretical problem in graph drawing. Given a graph with $n$ vertices and $m$ edges, we provide a RAC drawing algorithm with curve complexity $6$ and area $O(n^{2.75})$, which takes time $O(n+m)$. Our algorithm improves the previous upper bound $O(n^3)$, by Di Giacomo et al., on the area of RAC drawings.
The Neighbours' Similar Fitness Property for Local Search
Venue: arXiv cs.AI 2020
Year: 2020

For most practical optimisation problems local search outperforms random sampling - despite the "No Free Lunch Theorem". This paper introduces a property of search landscapes termed Neighbours' Similar Fitness (NSF) that underlies the good performance of neighbourhood search in terms of local improvement. Though necessary, NSF is not sufficient to ensure that searching for improvement among the neighbours of a good solution is better than random search. The paper introduces an additional (natural) property which supports a general proof that, for NSF landscapes, neighbourhood search beats random search.
On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes
Venue: arXiv cs.IT 2020
Year: 2020

Optimal locally repairable codes with information locality are considered. Optimal codes are constructed, whose length is also order-optimal with respect to a new bound on the code length derived in this paper. The length of the constructed codes is super-linear in the alphabet size, which improves upon the well known pyramid codes, whose length is only linear in the alphabet size. The recoverable erasure patterns are also analyzed for the new codes. Based on the recoverable erasure patterns, we construct generalized sector-disk (GSD) codes, which can recover from disk erasures mixed with sector erasures in a more general setting than known sector-disk (SD) codes. Additionally, the number of sectors in the constructed GSD codes is super-linear in the alphabet size, compared with known SD codes, whose number of sectors is only linear in the alphabet size.
Architecture and Security of SCADA Systems: A Review
Venue: arXiv cs.CR 2020
Year: 2020

Pipeline bursting, production lines shut down, frenzy traffic, trains confrontation, nuclear reactor shut down, disrupted electric supply, interrupted oxygen supply in ICU - these catastrophic events could result because of an erroneous SCADA system/ Industrial Control System(ICS). SCADA systems have become an essential part of automated control and monitoring of many of the Critical Infrastructures (CI). Modern SCADA systems have evolved from standalone systems into sophisticated complex, open systems, connected to the Internet. This geographically distributed modern SCADA system is vulnerable to threats and cyber attacks. In this paper, we first review the SCADA system architectures that have been proposed/implemented followed by attacks on such systems to understand and highlight the evolving security needs for SCADA systems. A short investigation of the current state of intrusion detection techniques in SCADA systems is done , followed by a brief study of testbeds for SCADA systems. The cloud and Internet of things (IoT) based SCADA systems are studied by analysing the architecture of modern SCADA systems. This review paper ends by highlighting the critical research problems that need to be resolved to close the gaps in the security of SCADA systems.
Generative Pseudo-label Refinement for Unsupervised Domain Adaptation
Venue: arXiv cs.CV 2020
Year: 2020

We investigate and characterize the inherent resilience of conditional Generative Adversarial Networks (cGANs) against noise in their conditioning labels, and exploit this fact in the context of Unsupervised Domain Adaptation (UDA). In UDA, a classifier trained on the labelled source set can be used to infer pseudo-labels on the unlabelled target set. However, this will result in a significant amount of misclassified examples (due to the well-known domain shift issue), which can be interpreted as noise injection in the ground-truth labels for the target set. We show that cGANs are, to some extent, robust against such "shift noise". Indeed, cGANs trained with noisy pseudo-labels, are able to filter such noise and generate cleaner target samples. We exploit this finding in an iterative procedure where a generative model and a classifier are jointly trained: in turn, the generator allows to sample cleaner data from the target distribution, and the classifier allows to associate better labels to target samples, progressively refining target pseudo-labels. Results on common benchmarks show that our method performs better or comparably with the unsupervised domain adaptation state of the art.
On Decoding Using Codewords of the Dual Code
Venue: arXiv cs.IT 2020
Year: 2020

We present novel decoding schemes for hard and soft decision decoding of block codes using the minimal weight codewords of the dual code. The decoding schemes will be described for cyclic codes where polynomials can be used, however, the modification for non-cyclic codes is possible and straight forward. The hard decision decoding calculates syndrome polynomials which are the product of the received polynomial with dual codewords. Proper cyclic shifts of these syndrome polynomials are obtained and the non-zero positions are counted componentwise for these shifts. The values of this counting are a reliability measure and can be used for locating the error and also the non-error positions. This reliability measure is the basis for various variants of hard decision decoding algorithms. Decoding schemes with iterative error reduction are possible as well as information set decoding using the inherent reliability information of the measure even if there is no reliability information from the channel. Further, we will show how reliability information from the channel can be included in order to obtain soft decision decoding schemes. We derive the relation between bit flipping, believe propagation, and majority logic decoding to the novel schemes. As examples to illustrate the functioning we use BCH and Reed-Muller codes as examples for binary codes, and RS codes for non-binary codes. Besides the Plotkin construction we recall a known result that Reed-Muller codes punctured by one position are cyclic and thus, are equivalent to special cases of BCH codes. Simulation results for hard and soft decision decoding will be given for several examples and compared with results from literature. Finally, we analyze the soft decision decoding of the Plotkin construction and derive that one of the two codes uses a $3$ dB better channel (also known as channel polarization).
Expected Improvement versus Predicted Value in Surrogate-Based Optimization
Venue: arXiv cs.NE 2020
Year: 2020

Surrogate-based optimization relies on so-called infill criteria (acquisition functions) to decide which point to evaluate next. When Kriging is used as the surrogate model of choice (also called Bayesian optimization), one of the most frequently chosen criteria is expected improvement. We argue that the popularity of expected improvement largely relies on its theoretical properties rather than empirically validated performance. Few results from the literature show evidence, that under certain conditions, expected improvement may perform worse than something as simple as the predicted value of the surrogate model. We benchmark both infill criteria in an extensive empirical study on the `BBOB' function set. This investigation includes a detailed study of the impact of problem dimensionality on algorithm performance. The results support the hypothesis that exploration loses importance with increasing problem dimensionality. A statistical analysis reveals that the purely exploitative search with the predicted value criterion performs better on most problems of five or higher dimensions. Possible reasons for these results are discussed. In addition, we give an in-depth guide for choosing the infill criteria based on prior knowledge about the problem at hand, its dimensionality, and the available budget.
Computing Persistent Homology with Various Coefficient Fields in a Single Pass
Venue: arXiv cs.CG 2020
Year: 2020

This article introduces an algorithm to compute the persistent homology of a filtered complex with various coefficient fields in a single matrix reduction. The algorithm is output-sensitive in the total number of distinct persistent homological features in the diagrams for the different coefficient fields. This computation allows us to infer the prime divisors of the torsion coefficients of the integral homology groups of the topological space at any scale, hence furnishing a more informative description of topology than persistence in a single coefficient field. We provide theoretical complexity analysis as well as detailed experimental results. The code is part of the Gudhi software library.
Automatic generation and verification of test-stable floating-point code
Venue: arXiv cs.PL 2020
Year: 2020

Test instability in a floating-point program occurs when the control flow of the program diverges from its ideal execution assuming real arithmetic. This phenomenon is caused by the presence of round-off errors that affect the evaluation of arithmetic expressions occurring in conditional statements. Unstable tests may lead to significant errors in safety-critical applications that depend on numerical computations. Writing programs that take into consideration test instability is a difficult task that requires expertise on finite precision computations and rounding errors. This paper presents a toolchain to automatically generate and verify a provably correct test-stable floating-point program from a functional specification in real arithmetic. The input is a real-valued program written in the Prototype Verification System (PVS) specification language and the output is a transformed floating-point C program annotated with ANSI/ISO C Specification Language (ACSL) contracts. These contracts relate the floating-point program to its functional specification in real arithmetic. The transformed program detects if unstable tests may occur and, in these cases, issues a warning and terminate. An approach that combines the Frama-C analyzer, the PRECiSA round-off error estimator, and PVS is proposed to automatically verify that the generated program code is correct in the sense that, if the program terminates without a warning, it follows the same computational path as its real-valued functional specification.
Objects detection for remote sensing images based on polar coordinates
Venue: arXiv cs.CV 2020
Year: 2020

Arbitrary-oriented object detection is an important task in the field of remote sensing object detection. Existing studies have shown that the polar coordinate system has obvious advantages in dealing with the problem of rotating object modeling, that is, using fewer parameters to achieve more accurate rotating object detection. However, present state-of-the-art detectors based on deep learning are all modeled in Cartesian coordinates. In this article, we introduce the polar coordinate system to the deep learning detector for the first time, and propose an anchor free Polar Remote Sensing Object Detector (P-RSDet), which can achieve competitive detection accuracy via uses simpler object representation model and less regression parameters. In P-RSDet method, arbitrary-oriented object detection can be achieved by predicting the center point and regressing one polar radius and two polar angles. Besides, in order to express the geometric constraint relationship between the polar radius and the polar angle, a Polar Ring Area Loss function is proposed to improve the prediction accuracy of the corner position. Experiments on DOTA, UCAS-AOD and NWPU VHR-10 datasets show that our P-RSDet achieves state-of-the-art performances with simpler model and less regression parameters.
Virtual to Real adaptation of Pedestrian Detectors
Venue: arXiv cs.CV 2020
Year: 2020

Pedestrian detection through Computer Vision is a building block for a multitude of applications. Recently, there was an increasing interest in Convolutional Neural Network-based architectures for the execution of such a task. One of these supervised networks' critical goals is to generalize the knowledge learned during the training phase to new scenarios with different characteristics. A suitably labeled dataset is essential to achieve this purpose. The main problem is that manually annotating a dataset usually requires a lot of human effort, and it is costly. To this end, we introduce ViPeD (Virtual Pedestrian Dataset), a new synthetically generated set of images collected with the highly photo-realistic graphical engine of the video game GTA V - Grand Theft Auto V, where annotations are automatically acquired. However, when training solely on the synthetic dataset, the model experiences a Synthetic2Real Domain Shift leading to a performance drop when applied to real-world images. To mitigate this gap, we propose two different Domain Adaptation techniques suitable for the pedestrian detection task, but possibly applicable to general object detection. Experiments show that the network trained with ViPeD can generalize over unseen real-world scenarios better than the detector trained over real-world data, exploiting the variety of our synthetic dataset. Furthermore, we demonstrate that with our Domain Adaptation techniques, we can reduce the Synthetic2Real Domain Shift, making closer the two domains and obtaining a performance improvement when testing the network over the real-world images. The code, the models, and the dataset are made freely available at https://ciampluca.github.io/viped/
Domain-independent Extraction of Scientific Concepts from Research Articles
Venue: arXiv cs.IR 2020
Year: 2020

We examine the novel task of domain-independent scientific concept extraction from abstracts of scholarly articles and present two contributions. First, we suggest a set of generic scientific concepts that have been identified in a systematic annotation process. This set of concepts is utilised to annotate a corpus of scientific abstracts from 10 domains of Science, Technology and Medicine at the phrasal level in a joint effort with domain experts. The resulting dataset is used in a set of benchmark experiments to (a) provide baseline performance for this task, (b) examine the transferability of concepts between domains. Second, we present two deep learning systems as baselines. In particular, we propose active learning to deal with different domains in our task. The experimental results show that (1) a substantial agreement is achievable by non-experts after consultation with domain experts, (2) the baseline system achieves a fairly high F1 score, (3) active learning enables us to nearly halve the amount of required training data.
Soft Maximum Likelihood Decoding using GRAND
Venue: arXiv cs.IT 2020
Year: 2020

Maximum Likelihood (ML) decoding of forward error correction codes is known to be optimally accurate, but is not used in practice as it proves too challenging to efficiently implement. Here we introduce a ML decoder called SGRAND, which is a development of a previously described hard detection ML decoder called GRAND, that fully avails of soft detection information and is suitable for use with any arbitrary high-rate, short-length block code. We assess SGRAND's performance on CRC-aided Polar (CA-Polar) codes, which will be used for all control channel communication in 5G NR, comparing its accuracy with CRC-Aided Successive Cancellation List decoding (CA-SCL), a state-of-the-art soft-information decoder specific to CA-Polar codes.
Parameterized Complexity of Geodetic Set
Venue: arXiv cs.DS 2020
Year: 2020

A vertex set $S$ of a graph $G$ is geodetic if every vertex of $G$ lies on a shortest path between two vertices in $S$. Given a graph $G$ and $k \in \mathbb N$, the NP-hard Geodetic Set problem asks whether there is a geodetic set of size at most $k$. Complementing various works on Geodetic Set restricted to special graph classes, we initiate a parameterized complexity study of Geodetic Set and show, on the negative side, that Geodetic Set is W[1]-hard when parameterized by feedback vertex number, path-width, and solution size, combined. On the positive side, we develop fixed-parameter algorithms with respect to the feedback edge number, the tree-depth, and the modular-width of the input graph.