OpenRaiser/Intern-Atlas huggingface dataset:
Types, Tokens, and Hapaxes: A New Heap's Law
Venue: arXiv cs.CL 2018
Year: 2018

Heap's Law states that in a large enough text corpus, the number of types as a function of tokens grows as $N=KM^β$ for some free parameters $K,β$. Much has been written about how this result and various generalizations can be derived from Zipf's Law. Here we derive from first principles a completely novel expression of the type-token curve and prove its superior accuracy on real text. This expression naturally generalizes to equally accurate estimates for counting hapaxes and higher $n$-legomena.
Supporting software documentation with source code summarization
Venue: arXiv cs.SE 2018
Year: 2018

Source code summarization is a process of generating summaries that describe software code, the majority of source code summarization usually generated manually, where the summaries are written by software developers. Recently, new automated approaches are becoming more useful. These approaches have been found to be effective in some cases. The main weaknesses of these approaches are that they never exploit code dependencies and summarize either the software classes or methods but not both. This paper proposes a source code summarization approach (Suncode) that produces a short description for each class and method in the software system. To validate the approach, it has been applied to several case studies. Moreover, the generated summaries are compared to summaries that written by human experts and to summaries that written by a state-of-the-art solution. Results of this paper found that Suncode summaries provide better information about code dependencies comparing with other studies. In addition, Suncode summaries can improve and support the current software documentation. The results found that manually written summaries were more precise and short as well.
Model Learning: A Survey on Foundation, Tools and Applications
Venue: arXiv cs.FL 2018
Year: 2018

The quality and correct functioning of software components embedded in electronic systems are of utmost concern especially for safety and mission-critical systems. Model-based testing and formal verification techniques can be employed to enhance the reliability of software systems. Formal models form the basis and are prerequisite for the application of these techniques. An emerging and promising model learning technique can complement testing and verification techniques by providing learned models of black box systems fully automatically. This paper surveys one such state of the art technique called model learning which recently has attracted much attention of researchers especially from the domains of testing and verification. This survey paper reviews and provides comparison summaries highlighting the merits and shortcomings of learning techniques, algorithms, and tools which form the basis of model learning. This paper also surveys the successful applications of model learning technique in multidisciplinary fields making it promising for testing and verification of realistic systems.
A Heuristic Algorithm for Network Optimization of OTN over DWDM Network
Venue: arXiv cs.NI 2018
Year: 2018

While the network traffic has seen exponential increase, the revenues have not maintained the same pace. New methods have to be explored to reduce this gap between traffic and revenue. One such method is convergence in networking layers. In this work, we study the convergence of OTN and DWDM layer from a network planning perspective. We compare the costs of planning networks without and with convergence and show that the multilayer planning offers least cost for higher traffic volumes.
Computational Fluid Dynamics on 3D Point Set Surfaces
Venue: arXiv cs.GR 2018
Year: 2018

Computational fluid dynamics (CFD) in many cases requires designing 3D models manually, which is a tedious task that requires specific skills. In this paper, we present a novel method for performing CFD directly on scanned 3D point clouds. The proposed method builds an anisotropic volumetric tetrahedral mesh adapted around a point-sampled surface, without an explicit surface reconstruction step. The surface is represented by a new extended implicit moving least squares (EIMLS) scalar representation that extends the definition of the function to the entire computational domain, which makes it possible for use in immersed boundary flow simulations. The workflow we present allows us to compute flows around point-sampled geometries automatically. It also gives a better control of the precision around the surface with a limited number of computational nodes, which is a critical issue in CFD.
Mechanism to Mitigate AVX-Induced Frequency Reduction
Venue: arXiv cs.DC 2018
Year: 2018

Modern Intel CPUs reduce their frequency when executing wide vector operations (AVX2 and AVX-512 instructions), as these instructions increase power consumption. The frequency is only increased again two milliseconds after the last code section containing such instructions has been executed in order to prevent excessive numbers of frequency changes. Due to this delay, intermittent use of wide vector operations can slow down the rest of the system significantly. For example, previous work has shown the performance of web servers to be reduced by up to 10% if the SSL library uses AVX-512 vector instructions. These performance variations are hard to predict during software development as the performance impact of vectorization depends on the specific workload. We describe a mechanism to reduce the slowdown caused by wide vector instructions without requiring extensive changes to existing software. Our design allows the developer to mark problematic AVX code regions. The scheduler then restricts execution of this code to a subset of the cores so that only these cores' frequency is affected. Threads are automatically migrated to a suitable core whenever necessary. We identify a suitable load balancing policy to ensure good utilization of all available cores. Our approach is able to reduce the performance variability caused by AVX2 and AVX-512 instructions by over 70%.
Data-driven Air Quality Characterisation for Urban Environments: a Case Study
Venue: arXiv cs.CY 2018
Year: 2018

The economic and social impact of poor air quality in towns and cities is increasingly being recognised, together with the need for effective ways of creating awareness of real-time air quality levels and their impact on human health. With local authority maintained monitoring stations being geographically sparse and the resultant datasets also featuring missing labels, computational data-driven mechanisms are needed to address the data sparsity challenge. In this paper, we propose a machine learning-based method to accurately predict the Air Quality Index (AQI), using environmental monitoring data together with meteorological measurements. To do so, we develop an air quality estimation framework that implements a neural network that is enhanced with a novel Non-linear Autoregressive neural network with exogenous input (NARX), especially designed for time series prediction. The framework is applied to a case study featuring different monitoring sites in London, with comparisons against other standard machine-learning based predictive algorithms showing the feasibility and robust performance of the proposed method for different kinds of areas within an urban region.
DarwinML: A Graph-based Evolutionary Algorithm for Automated Machine Learning
Venue: arXiv cs.NE 2018
Year: 2018

As an emerging field, Automated Machine Learning (AutoML) aims to reduce or eliminate manual operations that require expertise in machine learning. In this paper, a graph-based architecture is employed to represent flexible combinations of ML models, which provides a large searching space compared to tree-based and stacking-based architectures. Based on this, an evolutionary algorithm is proposed to search for the best architecture, where the mutation and heredity operators are the key for architecture evolution. With Bayesian hyper-parameter optimization, the proposed approach can automate the workflow of machine learning. On the PMLB dataset, the proposed approach shows the state-of-the-art performance compared with TPOT, Autostacker, and auto-sklearn. Some of the optimized models are with complex structures which are difficult to obtain in manual design.
Using an Ancillary Neural Network to Capture Weekends and Holidays in an Adjoint Neural Network Architecture for Intelligent Building Management
Venue: arXiv cs.LG 2018
Year: 2018

The US EIA estimated in 2017 about 39\% of total U.S. energy consumption was by the residential and commercial sectors. Therefore, Intelligent Building Management (IBM) solutions that minimize consumption while maintaining tenant comfort are an important component in addressing climate change. A forecasting capability for accurate prediction of indoor temperatures in a planning horizon of 24 hours is essential to IBM. It should predict the indoor temperature in both short-term (e.g. 15 minutes) and long-term (e.g. 24 hours) periods accurately including weekends, major holidays, and minor holidays. Other requirements include the ability to predict the maximum and the minimum indoor temperatures precisely and provide the confidence for each prediction. To achieve these requirements, we propose a novel adjoint neural network architecture for time series prediction that uses an ancillary neural network to capture weekend and holiday information. We studied four long short-term memory (LSTM) based time series prediction networks within this architecture. We observed that the ancillary neural network helps to improve the prediction accuracy, the maximum and the minimum temperature prediction and model reliability for all networks tested.
Usage of analytic hierarchy process for steganographic inserts detection in images
Venue: arXiv cs.MM 2018
Year: 2018

This article presents the method of steganography detection, which is formed by replacing the least significant bit (LSB). Detection is performed by dividing the image into layers and making an analysis of zero-layer of adjacent bits for every bit. First-layer and second-layer are analyzed too. Hierarchies analysis method is used for making decision if current bit is changed. Weighting coefficients as part of the analytic hierarchy process are formed on the values of bits. Then a matrix of corrupted pixels is generated. Visualization of matrix with corrupted pixels allows to determine size, location and presence of the embedded message. Computer experiment was performed. Message was embedded in a bounded rectangular area of the image. This method demonstrated efficiency even at low filling container, less than 10\%. Widespread statistical methods are unable to detect this steganographic insert. The location and size of the embedded message can be determined with an error which is not exceeding to five pixels.
DesignBIP: A Design Studio for Modeling and Generating Systems with BIP
Venue: arXiv cs.SE 2018
Year: 2018

The Behavior-Interaction-Priority (BIP) framework, rooted in rigorous semantics, allows the construction of systems that are correct-by-design. BIP has been effectively used for the construction and analysis of large systems such as robot controllers and satellite on-board software. Nevertheless, the specification of BIP models is done in a purely textual manner without any code editor support. To facilitate the specification of BIP models, we present DesignBIP, a web-based, collaborative, version-controlled design studio. To promote model scaling and reusability of BIP models, we use a graphical language for modeling parameterized BIP models with rigorous semantics. We present the various services provided by the design studio, including model editors, code editors, consistency checking mechanisms, code generators, and integration with the JavaBIP tool-set.
Spectral Ranking
Venue: arXiv cs.IR 2019
Year: 2019

We sketch the history of spectral ranking, a general umbrella name for techniques that apply the theory of linear maps (in particular, eigenvalues and eigenvectors) to matrices that do not represent geometric transformations, but rather some kind of relationship between entities. Albeit recently made famous by the ample press coverage of Google's PageRank algorithm, spectral ranking was devised more than a century ago, and has been studied in tournament ranking, psychology, social sciences, bibliometrics, economy and choice theory. We describe the contribution given by previous scholars in precise and modern mathematical terms: along the way, we show how to express in a general way damped rankings, such as Katz's index, as dominant eigenvectors of perturbed matrices, and then use results on the Drazin inverse to go back to the dominant eigenvectors by a limit process. The result suggests a regularized definition of spectral ranking that yields for a general matrix a unique vector depending on a boundary condition.
Incorporating characteristics of human creativity into an evolutionary art algorithm
Venue: arXiv cs.AI 2019
Year: 2019

A perceived limitation of evolutionary art and design algorithms is that they rely on human intervention; the artist selects the most aesthetically pleasing variants of one generation to produce the next. This paper discusses how computer generated art and design can become more creatively human-like with respect to both process and outcome. As an example of a step in this direction, we present an algorithm that overcomes the above limitation by employing an automatic fitness function. The goal is to evolve abstract portraits of Darwin, using our 2nd generation fitness function which rewards genomes that not just produce a likeness of Darwin but exhibit certain strategies characteristic of human artists. We note that in human creativity, change is less choosing amongst randomly generated variants and more capitalizing on the associative structure of a conceptual network to hone in on a vision. We discuss how to achieve this fluidity algorithmically.
Domination When the Stars Are Out
Venue: arXiv cs.DS 2019
Year: 2019

We algorithmize the recent structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that Dominating Set on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that Dominating Set is not fixed-parameter tractable on the slightly larger class of graphs that exclude K_{1,4} as an induced subgraph (K_{1,4}-free graphs). We show that our algorithmization can also be used to show that the related Connected Dominating Set problem is fixed-parameter tractable on claw-free graphs. To complement that result, we show that Connected Dominating Set has no polynomial kernel on claw-free graphs and is not fixed-parameter tractable on K_{1,4}-free graphs. Combined, our results provide a dichotomy for Dominating Set and Connected Dominating Set on K_{1,L}-free graphs and show that the problem is fixed-parameter tractable if and only if L <= 3.
Fast Balanced Partitioning is Hard, Even on Grids and Trees
Venue: arXiv cs.CC 2019
Year: 2019

Two kinds of approximation algorithms exist for the k-BALANCED PARTITIONING problem: those that are fast but compute unsatisfying approximation ratios, and those that guarantee high quality ratios but are slow. In this paper we prove that this tradeoff between runtime and solution quality is necessary. For the problem a minimum number of edges in a graph need to be found that, when cut, partition the vertices into k equal-sized sets. We develop a reduction framework which identifies some necessary conditions on the considered graph class in order to prove the hardness of the problem. We focus on two combinatorially simple but very different classes, namely trees and solid grid graphs. The latter are finite connected subgraphs of the infinite 2D grid without holes. First we use the framework to show that for solid grid graphs it is NP-hard to approximate the optimum number of cut edges within any satisfying ratio. Then we consider solutions in which the sets may deviate from being equal-sized. Our framework is used on grids and trees to prove that no fully polynomial time algorithm exists that computes solutions in which the sets are arbitrarily close to equal-sized. This is true even if the number of edges cut is allowed to increase the more stringent the limit on the set sizes is. These are the first bicriteria inapproximability results for the problem.
Getting Started with Isabelle/jEdit in 2018
Venue: arXiv cs.LO 2019
Year: 2019

This is a beginner-oriented introduction to Isabelle/jEdit, the main user interface for the proof assistant Isabelle.
Global Majority Consensus by Local Majority Polling on Graphs of a Given Degree Sequence
Venue: arXiv cs.DC 2019
Year: 2019

Suppose in a graph $G$ vertices can be either red or blue. Let $k$ be odd. At each time step, each vertex $v$ in $G$ polls $k$ random neighbours and takes the majority colour. If it doesn't have $k$ neighbours, it simply polls all of them, or all less one if the degree of $v$ is even. We study this protocol on graphs of a given degree sequence, in the following setting: initially each vertex of $G$ is red independently with probability $α< \frac{1}{2}$, and is otherwise blue. We show that if $α$ is sufficiently biased, then with high probability consensus is reached on the initial global majority within $O(\log_k \log_k n)$ steps if $5 \leq k \leq d$, and $O(\log_d \log_d n)$ steps if $k > d$. Here, $d\geq 5$ is the effective minimum degree, the smallest integer which occurs $Θ(n)$ times in the degree sequence. We further show that on such graphs, any local protocol in which a vertex does not change colour if all its neighbours have that same colour, takes time at least $Ω(\log_d \log_d n)$, with high probability. Additionally, we demonstrate how the technique for the above sparse graphs can be applied in a straightforward manner to get bounds for the Erdős-Rényi random graphs in the connected regime.
Towards Ultrahigh Dimensional Feature Selection for Big Data
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we present a new adaptive feature scaling scheme for ultrahigh-dimensional feature selection on Big Data. To solve this problem effectively, we first reformulate it as a convex semi-infinite programming (SIP) problem and then propose an efficient \emph{feature generating paradigm}. In contrast with traditional gradient-based approaches that conduct optimization on all input features, the proposed method iteratively activates a group of features and solves a sequence of multiple kernel learning (MKL) subproblems of much reduced scale. To further speed up the training, we propose to solve the MKL subproblems in their primal forms through a modified accelerated proximal gradient approach. Due to such an optimization scheme, some efficient cache techniques are also developed. The feature generating paradigm can guarantee that the solution converges globally under mild conditions and achieve lower feature selection bias. Moreover, the proposed method can tackle two challenging tasks in feature selection: 1) group-based feature selection with complex structures and 2) nonlinear feature selection with explicit feature mappings. Comprehensive experiments on a wide range of synthetic and real-world datasets containing tens of million data points with $O(10^{14})$ features demonstrate the competitive performance of the proposed method over state-of-the-art feature selection methods in terms of generalization performance and training efficiency.
Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits
Venue: arXiv cs.LG 2019
Year: 2019

We present a formal model of human decision-making in explore-exploit tasks using the context of multi-armed bandit problems, where the decision-maker must choose among multiple options with uncertain rewards. We address the standard multi-armed bandit problem, the multi-armed bandit problem with transition costs, and the multi-armed bandit problem on graphs. We focus on the case of Gaussian rewards in a setting where the decision-maker uses Bayesian inference to estimate the reward values. We model the decision-maker's prior knowledge with the Bayesian prior on the mean reward. We develop the upper credible limit (UCL) algorithm for the standard multi-armed bandit problem and show that this deterministic algorithm achieves logarithmic cumulative expected regret, which is optimal performance for uninformative priors. We show how good priors and good assumptions on the correlation structure among arms can greatly enhance decision-making performance, even over short time horizons. We extend to the stochastic UCL algorithm and draw several connections to human decision-making behavior. We present empirical data from human experiments and show that human performance is efficiently captured by the stochastic UCL algorithm with appropriate parameters. For the multi-armed bandit problem with transition costs and the multi-armed bandit problem on graphs, we generalize the UCL algorithm to the block UCL algorithm and the graphical block UCL algorithm, respectively. We show that these algorithms also achieve logarithmic cumulative expected regret and require a sub-logarithmic expected number of transitions among arms. We further illustrate the performance of these algorithms with numerical examples. NB: Appendix G included in this version details minor modifications that correct for an oversight in the previously-published proofs. The remainder of the text reflects the published work.
A New Statement for Selection and Exception Handling in Imperative Languages
Venue: arXiv cs.PL 2019
Year: 2019

Diverse selection statements -- if-then-else, switch and try-catch -- are commonly used in modern programming languages. To make things simple, we propose a unifying statement for selection. This statement is of the form seqor(G_1,...,G_n) where each $G_i$ is a statement. It has a a simple semantics: sequentially choose the first successful statement $G_i$ and then proceeds with executing $G_i$. Examples will be provided for this statement.
Learning to Rank for Blind Image Quality Assessment
Venue: arXiv cs.CV 2019
Year: 2019

Blind image quality assessment (BIQA) aims to predict perceptual image quality scores without access to reference images. State-of-the-art BIQA methods typically require subjects to score a large number of images to train a robust model. However, subjective quality scores are imprecise, biased, and inconsistent, and it is challenging to obtain a large scale database, or to extend existing databases, because of the inconvenience of collecting images, training the subjects, conducting subjective experiments, and realigning human quality evaluations. To combat these limitations, this paper explores and exploits preference image pairs (PIPs) such as "the quality of image $I_a$ is better than that of image $I_b$" for training a robust BIQA model. The preference label, representing the relative quality of two images, is generally precise and consistent, and is not sensitive to image content, distortion type, or subject identity; such PIPs can be generated at very low cost. The proposed BIQA method is one of learning to rank. We first formulate the problem of learning the mapping from the image features to the preference label as one of classification. In particular, we investigate the utilization of a multiple kernel learning algorithm based on group lasso (MKLGL) to provide a solution. A simple but effective strategy to estimate perceptual image quality scores is then presented. Experiments show that the proposed BIQA method is highly effective and achieves comparable performance to state-of-the-art BIQA algorithms. Moreover, the proposed method can be easily extended to new distortion categories.