OpenRaiser/Intern-Atlas huggingface dataset:
Hard and Easy Instances of L-Tromino Tilings
Venue: arXiv cs.CC 2020
Year: 2020

We study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we identify restrictions to the problem where it either remains NP-complete or has a polynomial time algorithm. First, we characterize the possibility of when an Aztec rectangle and an Aztec diamond has an L-tromino tiling. Then, we study tilings of arbitrary regions where only $180^\circ$ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete; yet, if a region does not contains certain so-called "forbidden polyominoes" as sub-regions, then there exists a polynomial time algorithm for deciding a tiling.
Using Vivado-HLS for Structural Design: a NoC Case Study
Venue: arXiv cs.AR 2020
Year: 2020

There have been ample successful examples of applying Xilinx Vivado's "function-to-module" high-level synthesis (HLS) where the subject is algorithmic in nature. In this work, we carried out a design study to assess the effectiveness of applying Vivado-HLS in structural design. We employed Vivado-HLS to synthesize C functions corresponding to standalone network-on-chip (NoC) routers as well as complete multi-endpoint NoCs. Interestingly, we find that describing a complete NoC comprising router submodules faces fundamental difficulties not present in describing the routers as standalone modules. Ultimately, we succeeded in using Vivado-HLS to produce router and NoC modules that are exact cycle- and bit-accurate replacements of our reference RTL-based router and NoC modules. Furthermore, the routers and NoCs resulting from HLS and RTL are comparable in resource utilization and critical path delay. Our experience subjectively suggests that HLS is able to simplify the design effort even though much of the structural details had to be provided in the HLS description through a combination of coding discipline and explicit pragmas. The C++ source code can be found at https://github.com/zhipengzhaocmu/HLS_NoC.
The Perception-Distortion Tradeoff
Venue: arXiv cs.CV 2020
Year: 2020

Image restoration algorithms are typically evaluated by some distortion measure (e.g. PSNR, SSIM, IFC, VIF) or by human opinion scores that quantify perceived perceptual quality. In this paper, we prove mathematically that distortion and perceptual quality are at odds with each other. Specifically, we study the optimal probability for correctly discriminating the outputs of an image restoration algorithm from real images. We show that as the mean distortion decreases, this probability must increase (indicating worse perceptual quality). As opposed to the common belief, this result holds true for any distortion measure, and is not only a problem of the PSNR or SSIM criteria. We also show that generative-adversarial-nets (GANs) provide a principled way to approach the perception-distortion bound. This constitutes theoretical support to their observed success in low-level vision tasks. Based on our analysis, we propose a new methodology for evaluating image restoration methods, and use it to perform an extensive comparison between recent super-resolution algorithms.
A Genetic Algorithm Approach for ImageRepresentation Learning through Color Quantization
Venue: arXiv cs.CV 2020
Year: 2020

Over the last decades, hand-crafted feature extractors have been used to encode image visual properties into feature vectors. Recently, data-driven feature learning approaches have been successfully explored as alternatives for producing more representative visual features. In this work, we combine both research venues, focusing on the color quantization problem. We propose two data-driven approaches to learn image representations through the search for optimized quantization schemes, which lead to more effective feature extraction algorithms and compact representations. Our strategy employs Genetic Algorithm, a soft-computing apparatus successfully utilized in Information-retrieval-related optimization problems. We hypothesize that changing the quantization affects the quality of image description approaches, leading to effective and efficient representations. We evaluate our approaches in content-based image retrieval tasks, considering eight well-known datasets with different visual properties. Results indicate that the approach focused on representation effectiveness outperformed baselines in all tested scenarios. The other approach, which also considers the size of created representations, produced competitive results keeping or even reducing the dimensionality of feature vectors up to 25%.
End-to-End Supervised Product Quantization for Image Search and Retrieval
Venue: arXiv cs.CV 2020
Year: 2020

Product Quantization, a dictionary based hashing method, is one of the leading unsupervised hashing techniques. While it ignores the labels, it harnesses the features to construct look up tables that can approximate the feature space. In recent years, several works have achieved state of the art results on hashing benchmarks by learning binary representations in a supervised manner. This work presents Deep Product Quantization (DPQ), a technique that leads to more accurate retrieval and classification than the latest state of the art methods, while having similar computational complexity and memory footprint as the Product Quantization method. To our knowledge, this is the first work to introduce a dictionary-based representation that is inspired by Product Quantization and which is learned end-to-end, and thus benefits from the supervised signal. DPQ explicitly learns soft and hard representations to enable an efficient and accurate asymmetric search, by using a straight-through estimator. Our method obtains state of the art results on an extensive array of retrieval and classification experiments.
Parallel Mapper
Venue: arXiv cs.CV 2020
Year: 2020

The construction of Mapper has emerged in the last decade as a powerful and effective topological data analysis tool that approximates and generalizes other topological summaries, such as the Reeb graph, the contour tree, split, and joint trees. In this paper, we study the parallel analysis of the construction of Mapper. We give a provably correct parallel algorithm to execute Mapper on multiple processors and discuss the performance results that compare our approach to a reference sequential Mapper implementation. We report the performance experiments that demonstrate the efficiency of our method.
Machine Learning simulates Agent-Based Model
Venue: arXiv cs.MA 2020
Year: 2020

Running agent-based models (ABMs) is a burdensome computational task, specially so when considering the flexibility ABMs intrinsically provide. This paper uses a bundle of model configuration parameters along with obtained results from a validated ABM to train some Machine Learning methods for socioeconomic optimal cases. A larger space of possible parameters and combinations of parameters are then used as input to predict optimal cases and confirm parameters calibration. Analysis of the parameters of the optimal cases are then compared to the baseline model. This exploratory initial exercise confirms the adequacy of most of the parameters and rules and suggests changing of directions to two parameters. Additionally, it helps highlight metropolitan regions of higher quality of life. Better understanding of ABM mechanisms and parameters' influence may nudge policy-making slightly closer to optimal level.
Perfect Prediction in Normal Form: Superrational Thinking Extended to Non-Symmetric Games
Venue: arXiv cs.GT 2020
Year: 2020

This paper introduces a new solution concept for non-cooperative games in normal form with no ties and pure strategies: the Perfectly Transparent Equilibrium. The players are rational in all possible worlds and know each other's strategies in all possible worlds, which together we refer to as Perfect Prediction. The anticipation of a player's decision by their opponents is counterfactually dependent on the decision, unlike in Nash Equilibra where the decisions are made independently. The equilibrium, when it exists, is unique and is Pareto optimal. This equilibrium is the normal-form counterpart of the Perfect Prediction Equilibrium; the prediction happens "in another room" rather than in the past. The equilibrium can also be seen as a natural extension of Hofstadter's superrationality to non-symmetric games. Algorithmically, an iterated elimination of non-individually-rational strategy profiles is performed until at most one remains. An equilibrium is a strategy profile that is immune against knowledge of strategies in all possible worlds and rationality in all possible worlds, a stronger concept than common knowledge of rationality but also than common counterfactual belief of rationality. We formalize and contrast the Non-Nashian Decision Theory paradigm, common to this and several other papers, with Causal Decision Theory and Evidential Decision Theory. We define the Perfectly Transparent Equilibrium algorithmically and, when it exists, prove its uniqueness, its Pareto-optimality, and that it coincides with the Hofstadter's Superrationality on symmetric games. We also relate to concepts found in literature such as Individual Rationality, Minimax-Rationalizability, the Correlated Equilibrium. Finally, we specifically discuss inclusion relationships on the special case of symmetric games and contrast them with asymmetric games.
Products of Euclidean metrics and applications to proximity questions among curves
Venue: arXiv cs.CG 2020
Year: 2020

The problem of Approximate Nearest Neighbor (ANN) search is fundamental in computer science and has benefited from significant progress in the past couple of decades. However, most work has been devoted to pointsets whereas complex shapes have not been sufficiently treated. Here, we focus on distance functions between discretized curves in Euclidean space: they appear in a wide range of applications, from road segments to time-series in general dimension. For $\ell_p$-products of Euclidean metrics, for any $p$, we design simple and efficient data structures for ANN, based on randomized projections, which are of independent interest. They serve to solve proximity problems under a notion of distance between discretized curves, which generalizes both discrete Fréchet and Dynamic Time Warping distances. These are the most popular and practical approaches to comparing such curves. We offer the first data structures and query algorithms for ANN with arbitrarily good approximation factor, at the expense of increasing space usage and preprocessing time over existing methods. Query time complexity is comparable or significantly improved by our algorithms, our algorithm is especially efficient when the length of the curves is bounded.
Variational Autoencoders for Learning Latent Representations of Speech Emotion: A Preliminary Study
Venue: arXiv cs.SD 2020
Year: 2020

Learning the latent representation of data in unsupervised fashion is a very interesting process that provides relevant features for enhancing the performance of a classifier. For speech emotion recognition tasks, generating effective features is crucial. Currently, handcrafted features are mostly used for speech emotion recognition, however, features learned automatically using deep learning have shown strong success in many problems, especially in image processing. In particular, deep generative models such as Variational Autoencoders (VAEs) have gained enormous success for generating features for natural images. Inspired by this, we propose VAEs for deriving the latent representation of speech signals and use this representation to classify emotions. To the best of our knowledge, we are the first to propose VAEs for speech emotion classification. Evaluations on the IEMOCAP dataset demonstrate that features learned by VAEs can produce state-of-the-art results for speech emotion classification.
Early Detection of Social Media Hoaxes at Scale
Venue: arXiv cs.CL 2020
Year: 2020

The unmoderated nature of social media enables the diffusion of hoaxes, which in turn jeopardises the credibility of information gathered from social media platforms. Existing research on automated detection of hoaxes has the limitation of using relatively small datasets, owing to the difficulty of getting labelled data. This in turn has limited research exploring early detection of hoaxes as well as exploring other factors such as the effect of the size of the training data or the use of sliding windows. To mitigate this problem, we introduce a semi-automated method that leverages the Wikidata knowledge base to build large-scale datasets for veracity classification, focusing on celebrity death reports. This enables us to create a dataset with 4,007 reports including over 13 million tweets, 15% of which are fake. Experiments using class-specific representations of word embeddings show that we can achieve F1 scores nearing 72% within 10 minutes of the first tweet being posted when we expand the size of the training data following our semi-automated means. Our dataset represents a realistic scenario with a real distribution of true, commemorative and false stories, which we release for further use as a benchmark in future research.
Modelling and Using Response Times in Online Courses
Venue: arXiv cs.HC 2020
Year: 2020

Each time a learner in a self-paced online course seeks to answer an assessment question, it takes some time for the student to read the question and arrive at an answer to submit. If multiple attempts are allowed, and the first answer is incorrect, it takes some time to provide a second answer. Here we study the distribution of such "response times." We find that the log-normal statistical model for such times, previously suggested in the literature, holds for online courses. Users who, according to this model, tend to take longer on submits are more likely to complete the course, have a higher level of engagement, and achieve a higher grade. This finding can be the basis for designing interventions in online courses, such as MOOCs, which would encourage "fast" users to slow down.
Near-lossless $\ell_\infty$-constrained Image Decompression via Deep Neural Network
Venue: arXiv cs.CV 2020
Year: 2020

Recently a number of CNN-based techniques were proposed to remove image compression artifacts. As in other restoration applications, these techniques all learn a mapping from decompressed patches to the original counterparts under the ubiquitous $\ell_\infty$ metric. However, this approach is incapable of restoring distinctive image details which may be statistical outliers but have high semantic importance (e.g., tiny lesions in medical images). To overcome this weakness, we propose to incorporate an $\ell_\infty$ fidelity criterion in the design of neural network so that no small, distinctive structures of the original image can be dropped or distorted. Experimental results demonstrate that the proposed method outperforms the state-of-the-art methods in $\ell_\infty$ error metric and perceptual quality, while being competitive in $\ell_2$ error metric as well. It can restore subtle image details that are otherwise destroyed or missed by other algorithms. Our research suggests a new machine learning paradigm of ultra high fidelity image compression that is ideally suited for applications in medicine, space, and sciences.
A Benchmark and Evaluation of Non-Rigid Structure from Motion
Venue: arXiv cs.CV 2020
Year: 2020

Non-Rigid structure from motion (NRSfM), is a long standing and central problem in computer vision and its solution is necessary for obtaining 3D information from multiple images when the scene is dynamic. A main issue regarding the further development of this important computer vision topic, is the lack of high quality data sets. We here address this issue by presenting a data set created for this purpose, which is made publicly available, and considerably larger than the previous state of the art. To validate the applicability of this data set, and provide an investigation into the state of the art of NRSfM, including potential directions forward, we here present a benchmark and a scrupulous evaluation using this data set. This benchmark evaluates 18 different methods with available code that reasonably spans the state of the art in sparse NRSfM. This new public data set and evaluation protocol will provide benchmark tools for further development in this challenging field.
Certified Defenses against Adversarial Examples
Venue: arXiv cs.LG 2020
Year: 2020

While neural networks have achieved high accuracy on standard image classification benchmarks, their accuracy drops to nearly zero in the presence of small adversarial perturbations to test inputs. Defenses based on regularization and adversarial training have been proposed, but often followed by new, stronger attacks that defeat these defenses. Can we somehow end this arms race? In this work, we study this problem for neural networks with one hidden layer. We first propose a method based on a semidefinite relaxation that outputs a certificate that for a given network and test input, no attack can force the error to exceed a certain value. Second, as this certificate is differentiable, we jointly optimize it with the network parameters, providing an adaptive regularizer that encourages robustness against all attacks. On MNIST, our approach produces a network and a certificate that no attack that perturbs each pixel by at most ε= 0.1 can cause more than 35% test error.
Equivariant ZFA and the foundations of nominal techniques
Venue: arXiv cs.LO 2020
Year: 2020

We give an accessible presentation to the foundations of nominal techniques, lying between Zermelo-Fraenkel set theory and Fraenkel-Mostowski set theory, and which has several nice properties including being consistent with the Axiom of Choice. We give two presentations of equivariance, accompanied by detailed yet user-friendly discussions of its theoretical significance and practical application.
Soft Computing Techniques for Dependable Cyber-Physical Systems
Venue: arXiv cs.SE 2020
Year: 2020

Cyber-Physical Systems (CPS) allow us to manipulate objects in the physical world by providing a communication bridge between computation and actuation elements. In the current scheme of things, this sought-after control is marred by limitations inherent in the underlying communication network(s) as well as by the uncertainty found in the physical world. These limitations hamper fine-grained control of elements that may be separated by large-scale distances. In this regard, soft computing is an emerging paradigm that can help to overcome the vulnerabilities, and unreliability of CPS by using techniques including fuzzy systems, neural network, evolutionary computation, probabilistic reasoning and rough sets. In this paper, we present a comprehensive contemporary review of soft computing techniques for CPS dependability modeling, analysis, and improvement. This paper provides an overview of CPS applications, explores the foundations of dependability engineering, and highlights the potential role of soft computing techniques for CPS dependability with various case studies, while identifying common pitfalls and future directions. In addition, this paper provides a comprehensive survey on the use of various soft computing techniques for making CPS dependable.
Classification and Disease Localization in Histopathology Using Only Global Labels: A Weakly-Supervised Approach
Venue: arXiv cs.CV 2020
Year: 2020

Analysis of histopathology slides is a critical step for many diagnoses, and in particular in oncology where it defines the gold standard. In the case of digital histopathological analysis, highly trained pathologists must review vast whole-slide-images of extreme digital resolution ($100,000^2$ pixels) across multiple zoom levels in order to locate abnormal regions of cells, or in some cases single cells, out of millions. The application of deep learning to this problem is hampered not only by small sample sizes, as typical datasets contain only a few hundred samples, but also by the generation of ground-truth localized annotations for training interpretable classification and segmentation models. We propose a method for disease localization in the context of weakly supervised learning, where only image-level labels are available during training. Even without pixel-level annotations, we are able to demonstrate performance comparable with models trained with strong annotations on the Camelyon-16 lymph node metastases detection challenge. We accomplish this through the use of pre-trained deep convolutional networks, feature embedding, as well as learning via top instances and negative evidence, a multiple instance learning technique from the field of semantic segmentation and object detection.
Fair comparison of skin detection approaches on publicly available datasets
Venue: arXiv cs.CV 2020
Year: 2020

Skin detection is the process of discriminating skin and non-skin regions in a digital image and it is widely used in several applications ranging from hand gesture analysis to track body parts and face detection. Skin detection is a challenging problem which has drawn extensive attention from the research community, nevertheless a fair comparison among approaches is very difficult due to the lack of a common benchmark and a unified testing protocol. In this work, we investigate the most recent researches in this field and we propose a fair comparison among approaches using several different datasets. The major contributions of this work are an exhaustive literature review of skin color detection approaches, a framework to evaluate and combine different skin detector approaches, whose source code is made freely available for future research, and an extensive experimental comparison among several recent methods which have also been used to define an ensemble that works well in many different problems. Experiments are carried out in 10 different datasets including more than 10000 labelled images: experimental results confirm that the best method here proposed obtains a very good performance with respect to other stand-alone approaches, without requiring ad hoc parameter tuning. A MATLAB version of the framework for testing and of the methods proposed in this paper will be freely available from https://github.com/LorisNanni
Adaptive Coded Caching for Fair Delivery over Fading Channels
Venue: arXiv cs.IT 2020
Year: 2020

The performance of existing coded caching schemes is sensitive to the worst channel quality, a problem which is exacerbated when communicating over fading channels. In this paper, we address this limitation in the following manner: in short-term, we allow transmissions to subsets of users with good channel quality, avoiding users with fades, while in long-term we ensure fairness among users. Our online scheme combines (i) the classical decentralized coded caching scheme \cite{maddah2013decentralized} with (ii) joint scheduling and power control for the fading broadcast channel, as well as (iii) congestion control for ensuring the optimal long-term average performance. We prove that our online delivery scheme maximizes the alpha-fair utility among all schemes restricted to decentralized placement. By tuning the value of alpha, the proposed scheme can achieve different operating points on the average delivery rate region and tune performance according to an operator's choice. We demonstrate via simulations that our scheme outperforms two baseline schemes: (a) standard coded caching with multicast transmission, limited by the worst channel user yet exploiting the global caching gain; (b) opportunistic scheduling with unicast transmissions exploiting the fading diversity but limited to local caching gain.