nils-herrmann/clean_scirepeval huggingface dataset:
Engineering faster sorters for small sets of items

Sorting a set of items is a task that can be useful by itself or as a building block for more complex operations. That is why a lot of effort has been put into finding sorting algorithms that sort large sets as efficiently as possible. But the more sophisticated and complex the algorithms become, the less efficient they are for small sets of items due to large constant factors. A relatively simple sorting algorithm that is often used as a base case sorter is insertion sort, because it has small code size and small constant factors influencing its execution time. We aim to determine if there is a faster way to sort small sets of items to provide an efficient base case sorter. We looked at sorting networks, at how they can improve the speed of sorting few elements, and how to implement them in an efficient manner using conditional moves. Since sorting networks need to be implemented explicitly for each set size, providing networks for larger sizes becomes less efficient due to increased code sizes. To also enable the sorting of slightly larger base cases, we adapted sample sort to Register Sample Sort, to break down those larger sets into sizes that can in turn be sorted by sorting networks. From our experiments we found that when sorting only small sets of integers, the sorting networks outperform insertion sort by a factor of at least 1.76 for any array size between six and 16, and by a factor of 2.72 on average across all machines and array sizes. When integrating sorting networks as a base case sorter into Quicksort, we achieved far less performance improvements over using insertion sort, which is probably due to the networks having a larger code size and cluttering the L1 instruction cache. The same effect occurs when including Register Sample Sort as a base case sorter for IPS 4 o. But for x86 machines that have a larger L1 instruction cache of 64 KiB or more, we obtained speedups of 12.7% when using sorting networks as a base case sorter in std::sort, and of 5%–6% when integrating Register Sample Sort as a base case sorter into IPS 4 o, each in comparison to using insertion sort as the base case sorter. In conclusion, the desired improvement in speed could only be achieved under special circumstances, but the results clearly show the potential of using conditional moves in the field of sorting algorithms.
An Email Experiment to Identify the Effect of Racial Discrimination on Access to Lawyers: A Statistical Approach

We consider the problem of conducting an experiment to study the prevalence of racial bias against individuals seeking legal assistance, in particular whether lawyers use clues about a potential client's race in deciding whether to reply to e-mail requests for representations. The problem of discriminating between potential linear and non-linear effects of a racial signal is formulated as a statistical inference problem, whose objective is to infer a parameter determining the shape of a specific function. Various complexities associated with the design and analysis of this experiment are handled by applying a novel combination of rigorous, semi-rigorous and rudimentary statistical techniques. The actual experiment is performed with a population of lawyers in Florida.
Neural Plasticity Networks

Neural plasticity is an important functionality of human brain, in which number of neurons and synapses can shrink or expand in response to stimuli throughout the span of life. We model this dynamic learning process as an $L_{0}$ - norm regularized binary optimization problem, in which each unit of a neural network (e.g., weight, neuron or channel, etc.) is attached with a stochastic binary gate, whose parameters determine the level of activity of a unit in the network. At the beginning, only a small portion of binary gates (therefore the corresponding neurons) are activated, while the remaining neurons are in a hibernation mode. As the learning proceeds, some neurons might be activated or deactivated if doing so can be justified by the cost-benefit tradeoff measured by the $L_{0}$-norm regularized objective. As the training gets mature, the probability of transition between activation and deactivation will diminish until a final hardening stage. We demonstrate that all of these learning dynamics can be modulated by a single parameter $k$ seamlessly. Our neural plasticity network (NPN) can prune or expand a network depending on the initial capacity of network provided by the user; it also unifies dropout (when $k=0$), traditional training of DNNs (when $k=\infty$) and interpolates between these two. To the best of our knowledge, this is the first learning framework that unifies network sparsification and network expansion in an end-to-end training pipeline. Extensive experiments on synthetic dataset and multiple image classification benchmarks demonstrate the superior performance of NPN. We show that both network sparsification and network expansion can yield compact models of similar architectures, while retaining competitive accuracies of the original networks. 11Our source code is available at https://github.com/leo-yangli/npns.
Lecture Notes on "Free Probability Theory".

This in an introduction to free probability theory, covering the basic combinatorial and analytic theory, as well as the relations to random matrices and operator algebras. The material is mainly based on the two books of the lecturer, one joint with Nica and one joint with Mingo. Free probability is here restricted to the scalar-valued setting, the operator-valued version is treated in the subsequent lecture series on "Non-Commutative Distributions". The material here was presented in the winter term 2018/19 at Saarland University in 26 lectures of 90 minutes each. The lectures were recorded and can be found online at this https URL
Tensor Product Representations of Subregular Formal Languages

This paper provides a geometric characterization of subclasses of the regular languages. We use finite model theory to characterize objects like strings and trees as relational structures. Logical statements meeting certain criteria over these models define subregular classes of languages. The semantics of such statements can be compiled into tensor structures, using multilinear maps as function application for evaluation. This method is applied to consider two properly subregular languages over different string models.
Transferability and Hardness of Supervised Classification Tasks

We propose a novel approach for estimating the difficulty and transferability of supervised classification tasks. Unlike previous work, our approach is solution agnostic and does not require or assume trained models. Instead, we estimate these values using an information theoretic approach: treating training labels as random variables and exploring their statistics. When transferring from a source to a target task, we consider the conditional entropy between two such variables (i.e., label assignments of the two tasks). We show analytically and empirically that this value is related to the loss of the transferred model. We further show how to use this value to estimate task hardness. We test our claims extensively on three large scale data sets---CelebA (40 tasks), Animals with Attributes~2 (85 tasks), and Caltech-UCSD Birds~200 (312 tasks)---together representing 437 classification tasks. We provide results showing that our hardness and transferability estimates are strongly correlated with empirical hardness and transferability. As a case study, we transfer a learned face recognition model to CelebA attribute classification tasks, showing state of the art accuracy for highly transferable attributes.
They may look and look, yet not see: BMDs cannot be tested adequately

. Bugs, misconﬁguration, and malware can cause ballot-marking devices (BMDs) to print incorrect votes. Several approaches to testing BMDs have been proposed. In logic and accuracy testing (LAT) and parallel or live testing, auditors input known test patterns into the BMD and check whether the printout matches. Passive testing monitors the rate at which voters “spoil” BMD printout, on the theory that if BMDs mal-function, the rate will increase. We provide theoretical lower bounds that show that in practice, these approaches cannot reliably detect outcome-altering problems. The bounds are large because: (i) The number of possible voter interactions with BMDs is enormous, so testing interactions uniformly at random is hopeless. (ii) To probe the space of interactions intelligently requires an accurate model of voter behavior, but because the space of interactions is so large, building that model requires observing an enormous number of voters in every jurisdiction in every election—more voters than there are in most U.S. jurisdictions. (iii) Even with a perfect model of voter behavior, the required number of tests exceeds the number of voters in most U.S. jurisdictions. (iv) The distribution of spoiled ballots, whether BMDs misbehave or not, is un-known and varies by election and presumably by ballot style: historical data are of limited use. Hence, there is no way to calibrate a threshold for passive testing, e.g., to guarantee at least a 95% chance of noticing that 5% of the votes were altered, with at most a 5% false alarm rate. (v) Even if the distribution of spoiled ballots were known to be Poisson, the vast majority of jurisdictions to not have enough voters for passive testing to have a large chance of detecting problems while maintaining a small chance of false alarms.
Brown measures of free circular and multiplicative Brownian motions with self-adjoint and unitary initial conditions

Let $x_0$ be a self-adjoint random variable and $c_t$ be a free circular Brownian motion, freely independent from $x_0$. We use the Hamilton--Jacobi method to compute the Brown measure $\rho_t$ of $x_0+c_t$. The Brown measure is absolutely continuous with a density that is \emph{constant along the vertical direction} in the support of $\rho_t$. The support of the Brown measure of $x_0+c_t$ is related to the subordination function of the free additive convolution of $x_0+s_t$, where $s_t$ is the free semicircular Brownian motion, freely independent from $x_0$. Furthermore, the push-forward of $\rho_t$ by a natural map is the law of $x_0+s_t$. 
Let $u$ be a unitary random variable and $b_t$ is the free multiplicative Brownian motion freely independent from $u$, we compute the Brown measure $\mu_t$ of the free multiplicative Brownian motion $ub_t$, extending the recent work by Driver--Hall--Kemp. The measure is absolutely continuous with a density of the special form 
\[\frac{1}{r^2}w_t(\theta)\] 
in polar coordinates in its support. The support of $\mu_t$ is related to the subordination function of the free multiplicative convolution of $uu_t$ where $u_t$ is the free unitary Brownian motion free independent from $u$. The push-forward of $\mu_t$ by a natural map is the law of $uu_t$. 
In the special case that $u$ is Haar unitary, the Brown measure $\mu_t$ follows the \emph{annulus law}. The support of the Brown measure of $ub_t$ is an annulus with inner radius $e^{-t/2}$ and outer radius $e^{t/2}$. The density in polar coordinates is given by 
] 
in its support.
A Multiple-Instance Densely-Connected ConvNet for Aerial Scene Classification

In contrast with nature scenes, aerial scenes are often composed of many objects crowdedly distributed on the surface in bird’s view, the description of which usually demands more discriminative features as well as local semantics. However, when applied to scene classification, most of the existing convolution neural networks (ConvNets) tend to depict global semantics of images, and the loss of low- and mid-level features can hardly be avoided, especially when the model goes deeper. To tackle these challenges, in this paper, we propose a multiple-instance densely-connected ConvNet (MIDC-Net) for aerial scene classification. It regards aerial scene classification as a multiple-instance learning problem so that local semantics can be further investigated. Our classification model consists of an instance-level classifier, a multiple instance pooling and followed by a bag-level classification layer. In the instance-level classifier, we propose a simplified dense connection structure to effectively preserve features from different levels. The extracted convolution features are further converted into instance feature vectors. Then, we propose a trainable attention-based multiple instance pooling. It highlights the local semantics relevant to the scene label and outputs the bag-level probability directly. Finally, with our bag-level classification layer, this multiple instance learning framework is under the direct supervision of bag labels. Experiments on three widely-utilized aerial scene benchmarks demonstrate that our proposed method outperforms many state-of-the-art methods by a large margin with much fewer parameters.
Globally optimal registration of noisy point clouds

Registration of 3D point clouds is a fundamental task in several applications of robotics and computer vision. While registration methods such as iterative closest point and variants are very popular, they are only locally optimal. There has been some recent work on globally optimal registration, but they perform poorly in the presence of noise in the measurements. In this work we develop a mixed integer programming-based approach for globally optimal registration that explicitly considers uncertainty in its optimization, and hence produces more accurate estimates. Furthermore, from a practical implementation perspective we develop a multi-step optimization that combines fast local methods with our accurate global formulation. Through extensive simulation and real world experiments we demonstrate improved performance over state-of-the-art methods for various level of noise and outliers in the data as well as for partial geometric overlap.
Building Change Detection Based on Multi-Scale Filtering and Grid Partition

Building change detection is of great significance in high resolution remote sensing applications. Multi-index learning, one of the state-of-the-art building change detection methods, still has drawbacks like incapability to find change types directly and heavy computation consumption of MBI. In this paper, a two-stage building change detection method is proposed to address these problems. In the first stage, a multi-scale filtering building index (MFBI) is calculated to detect building areas in each temporal with fast speed and moderate accuracy. In the second stage, images and the corresponding building maps are partitioned into grids. In each grid, the ratio of building areas in time T2 and time T1 is calculated. Each grid is classified into one of the three change patterns, i.e., significantly increase, significantly decrease and approximately unchanged. Exhaustive experiments indicate that the proposed method can detect building change types directly and outperform the current multi-index learning method.
Multi-passage BERT: A Globally Normalized BERT Model for Open-domain Question Answering

BERT model has been successfully applied to open-domain QA tasks. However, previous work trains BERT by viewing passages corresponding to the same question as independent training instances, which may cause incomparable scores for answers from different passages. To tackle this issue, we propose a multi-passage BERT model to globally normalize answer scores across all passages of the same question, and this change enables our QA model find better answers by utilizing more passages. In addition, we find that splitting articles into passages with the length of 100 words by sliding window improves performance by 4%. By leveraging a passage ranker to select high-quality passages, multi-passage BERT gains additional 2%. Experiments on four standard benchmarks showed that our multi-passage BERT outperforms all state-of-the-art models on all benchmarks. In particular, on the OpenSQuAD dataset, our model gains 21.4% EM and 21.5% F1 over all non-BERT models, and 5.8% EM and 6.5% F1 over BERT-based models.
Intra-day Equity Price Prediction using Deep Learning as a Measure of Market Efficiency

In finance, the weak form of the Efficient Market Hypothesis asserts that historic stock price and volume data cannot inform predictions of future prices. In this paper we show that, to the contrary, future intra-day stock prices could be predicted effectively until 2009. We demonstrate this using two different profitable machine learning-based trading strategies. However, the effectiveness of both approaches diminish over time, and neither of them are profitable after 2009. We present our implementation and results in detail for the period 2003-2017 and propose a novel idea: the use of such flexible machine learning methods as an objective measure of relative market efficiency. We conclude with a candidate explanation, comparing our returns over time with high-frequency trading volume, and suggest concrete steps for further investigation.
Semi-supervised Adversarial Active Learning on Attributed Graphs

Active learning (AL) on attributed graphs has received increasing attention with the prevalence of graphstructured data. Although AL has been widely studied for alleviating label sparsity issues with the conventional independent and identically distributed (i.i.d.) data, how to make it effective over attributed graphs remains an open research question. Existing AL algorithms on graphs attempt to reuse the classic AL query strategies designed for i.i.d. data. However, they suffer from two major limitations. First, different AL query strategies calculated in distinct scoring spaces are often naively combined to determine which nodes to be labeled. Second, the AL query engine and the learning of the classifier are treated as two separating processes, resulting in unsatisfactory performance. In this paper, we propose a SEmi-supervised Adversarial active Learning (SEAL) framework on attributed graphs, which fully leverages the representation power of deep neural networks and devises a novel AL query strategy in an adversarial way. Our framework learns two adversarial components; a graph embedding network that encodes both the unlabeled and labeled nodes into a latent space, expecting to trick the discriminator to regard all nodes as already labeled, and a semi-supervised discriminator network that distinguishes the unlabeled from the existing labeled nodes in the latent space. The divergence score, generated by the discriminator in a unified latent space, serves as the informativeness measure to actively select the most informative node to be labeled by an oracle. The two adversarial components form a closed loop to mutually and simultaneously reinforce each other towards enhancing the active learning performance. Extensive experiments on four real-world networks validate the effectiveness of the SEAL framework with superior performance improvements to state-of-the-art baselines.
Multi-Stream Single Shot Spatial-Temporal Action Detection

We present a 3D Convolutional Neural Networks (CNNs) based single shot detector for spatial-temporal action detection tasks. Our model includes: (i) two short-term appearance and motion streams, with single RGB and optical flow image input separately, in order to capture the spatial and temporal information for the current frame; (ii) two long-term 3D ConvNet based stream, working on sequences of continuous RGB and optical flow images to capture the context from past frames. Our model achieves strong performance for action detection in video and can be easily integrated into any current two-stream action detection methods. We report a frame-mAP of 71.30% on the challenging UCF101-24  actions dataset, achieving the state-of-the-art result of the one-stage methods. To the best of our knowledge, our work is the first system that combined 3D CNN and SSD in action detection tasks.
The agreement distance of unrooted phylogenetic networks

A rearrangement operation makes a small graph-theoretical change to a phylogenetic network to transform it into another one. For unrooted phylogenetic trees and networks, popular rearrangement operations are tree bisection and reconnection (TBR) and prune and regraft (PR) (resp. subtree prune and regraft (SPR) on trees). Each of these operations induces a metric on the sets of phylogenetic trees and networks. The TBR-distance between two unrooted phylogenetic trees T and T ′ can be characterised by a maximum agreement forest, that is, a forest with a minimum number of components that covers both T and T ′ in a certain way. This characterisation has facilitated the development of fixed-parameter tractable algorithms and approximation algorithms. Here, we introduce maximum agreement graphs as a generalisations of maximum agreement forests for phylogenetic networks. While the agreement distance – the metric induced by maximum agreement graphs – does not characterise the TBR-distance of two networks, we show that it still provides constant-factor bounds on the TBR-distance. We find similar results for PR in terms of maximum endpoint agreement graphs.
Pro-Cam SSfM: Projector-Camera System for Structure and Spectral Reflectance From Motion

In this paper, we propose a novel projector-camera system for practical and low-cost acquisition of a dense object 3D model with the spectral reflectance property. In our system, we use a standard RGB camera and leverage an off-the-shelf projector as active illumination for both the 3D reconstruction and the spectral reflectance estimation. We first reconstruct the 3D points while estimating the poses of the camera and the projector, which are alternately moved around the object, by combining multi-view structured light and structure-from-motion (SfM) techniques. We then exploit the projector for multispectral imaging and estimate the spectral reflectance of each 3D point based on a novel spectral reflectance estimation model considering the geometric relationship between the reconstructed 3D points and the estimated projector positions. Experimental results on several real objects demonstrate that our system can precisely acquire a dense 3D model with the full spectral reflectance property using off-the-shelf devices.
A CNN toolbox for skin cancer classification

We describe a software toolbox for the configuration of deep neural networks in the domain of skin cancer classification. The implemented software architecture allows developers to quickly set up new convolutional neural network (CNN) architectures and hyper-parameter configurations. At the same time, the user interface, manageable as a simple spreadsheet, allows non-technical users to explore different configuration settings that need to be explored when switching to different data sets. In future versions, meta leaning frameworks can be added, or AutoML systems that continuously improve over time. Preliminary results, conducted with two CNNs in the context melanoma detection on dermoscopic images, quantify the impact of image augmentation, image resolution, and rescaling filter on the overall detection performance and training time.
Diversity in biology: definitions, quantification and models

Diversity indices are useful single-number metrics for characterizing a complex distribution of a set of attributes across a population of interest. The utility of these different metrics or sets of metrics depends on the context and application, and whether a predictive mechanistic model exists. In this topical review, we first summarize the relevant mathematical principles underlying heterogeneity in a large population, before outlining the various definitions of ‘diversity’ and providing examples of scientific topics in which its quantification plays an important role. We then review how diversity has been a ubiquitous concept across multiple fields, including ecology, immunology, cellular barcoding experiments, and socioeconomic studies. Since many of these applications involve sampling of populations, we also review how diversity in small samples is related to the diversity in the entire population. Features that arise in each of these applications are highlighted.