OpenRaiser/Intern-Atlas huggingface dataset:
Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions
Venue: arXiv cs.NE 2017
Year: 2017

This paper demonstrates the use of genetic algorithms for evolving a grandmaster-level evaluation function for a chess program. This is achieved by combining supervised and unsupervised learning. In the supervised learning phase the organisms are evolved to mimic the behavior of human grandmasters, and in the unsupervised learning phase these evolved organisms are further improved upon by means of coevolution. While past attempts succeeded in creating a grandmaster-level program by mimicking the behavior of existing computer chess programs, this paper presents the first successful attempt at evolving a state-of-the-art evaluation function by learning only from databases of games played by humans. Our results demonstrate that the evolved program outperforms a two-time World Computer Chess Champion.
Expert-Driven Genetic Algorithms for Simulating Evaluation Functions
Venue: arXiv cs.NE 2017
Year: 2017

In this paper we demonstrate how genetic algorithms can be used to reverse engineer an evaluation function's parameters for computer chess. Our results show that using an appropriate expert (or mentor), we can evolve a program that is on par with top tournament-playing chess programs, outperforming a two-time World Computer Chess Champion. This performance gain is achieved by evolving a program that mimics the behavior of a superior expert. The resulting evaluation function of the evolved program consists of a much smaller number of parameters than the expert's. The extended experimental results provided in this paper include a report of our successful participation in the 2008 World Computer Chess Championship. In principle, our expert-driven approach could be used in a wide range of problems for which appropriate experts are available.
Project Success in Agile Development Projects
Venue: arXiv cs.SE 2017
Year: 2017

The paper explains and clarifies the differences between Waterfall and Agile development methodologies, establishes what criteria could be taken into account to properly define project success within the scope of software development projects, and finally tries to clarify if project success is the reason why many organizations are moving to Agile methodologies from other ones such as Waterfall. In the form of a literature review, it analyses several, publications, investigations and case studies that point out the motives why companies moved to Agile, as well as the results they observed afterward. It also analyses overall statistics of project outcomes after companies evolved from traditional methodologies such as Waterfall to Agile development approaches.
Aggregated Load and Generation Equivalent Circuit Models with Semi-Empirical Data Fitting
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we propose a semi-empirical modeling framework for aggregated electrical load and generation using an equivalent circuit formulation. The proposed models are based on complex rectangular voltage and current state variables that provide a generalized form for accurately representing any transmission and distribution components. The model is based on the split equivalent circuit formulation that was previously shown to unify power flow, three phase power flow, harmonic power flow, and transient analyses. Importantly, this formulation establishes variables that are analytical and are compatible with model fitting and machine learning approaches. The parameters for the proposed semi-empirical load and generation models are synthesized from measurement data and can enable real-time simulations for time varying aggregated loads and generation.
Joint User Scheduling and Beam Selection Optimization for Beam-Based Massive MIMO Downlinks
Venue: arXiv cs.IT 2017
Year: 2017

In beam-based massive multiple-input multiple-output systems, signals are processed spatially in the radio-frequency (RF) front-end and thereby the number of RF chains can be reduced to save hardware cost, power consumptions and pilot overhead. Most existing work focuses on how to select, or design analog beams to achieve performance close to full digital systems. However, since beams are strongly correlated (directed) to certain users, the selection of beams and scheduling of users should be jointly considered. In this paper, we formulate the joint user scheduling and beam selection problem based on the Lyapunov-drift optimization framework and obtain the optimal scheduling policy in a closed-form. For reduced overhead and computational cost, the proposed scheduling schemes are based only upon statistical channel state information. Towards this end, asymptotic expressions of the downlink broadcast channel capacity are derived. To address the weighted sum rate maximization problem in the Lyapunov optimization, an algorithm based on block coordinated update is proposed and proved to converge to the optimum of the relaxed problem. To further reduce the complexity, an incremental greedy scheduling algorithm is also proposed, whose performance is proved to be bounded within a constant multiplicative factor. Simulation results based on widely-used spatial channel models are given. It is shown that the proposed schemes are close to optimal, and outperform several state-of-the-art schemes.
Cyclone: High Availability for Persistent Key Value Stores
Venue: arXiv cs.DC 2017
Year: 2017

Persistent key value stores are an important component of many distributed data serving solutions with innovations targeted at taking advantage of growing flash speeds. Unfortunately their performance is hampered by the need to maintain and replicate a write ahead log to guarantee availability in the face of machine and storage failures. Cyclone is a replicated log plug-in for key value stores that systematically addresses various sources of this bottleneck. It uses a small amount of non-volatile memory directly addressable by the CPU - such as in the form of NVDIMMs or Intel 3DXPoint - to remove block oriented IO devices such as SSDs from the critical path for appending to the log. This enables it to address network overheads using an implementation of the RAFT consensus protocol that is designed around a userspace network stack to relieve the CPU of the burden of data copies. Finally, it provides a way to efficiently map the commutativity in key-value store APIs to the parallelism available in commodity NICs. Cyclone is able to replicate millions of small updates per second using only commodity 10 gigabit ethernet adapters. As a practical application, we use it to improve the performance (and availability) of RocksDB, a popular persistent key value store by an order of magnitude when compared to its own write ahead log without replication.
Towards understanding startup product development as effectual entrepreneurial behaviors
Venue: arXiv cs.CY 2017
Year: 2017

Software startups face with multiple technical and business challenges, which could make the startup journey longer, or even become a failure. Little is known about entrepreneurial decision making as a direct force to startup development outcome. In this study, we attempted to apply a behaviour theory of entrepreneurial firms to understand the root-cause of some software startup s challenges. Six common challenges related to prototyping and product development in twenty software startups were identified. We found the behaviour theory as a useful theoretical lens to explain the technical challenges. Software startups search for local optimal solutions, emphasise on short-run feedback rather than long-run strategies, which results in vague prototype planning, paradox of demonstration and evolving throw-away prototypes. The finding implies that effectual entrepreneurial processes might require a more suitable product development approach than the current state-of-practice.
Modeling Epistemological Principles for Bias Mitigation in AI Systems: An Illustration in Hiring Decisions
Venue: arXiv cs.AI 2017
Year: 2017

Artificial Intelligence (AI) has been used extensively in automatic decision making in a broad variety of scenarios, ranging from credit ratings for loans to recommendations of movies. Traditional design guidelines for AI models focus essentially on accuracy maximization, but recent work has shown that economically irrational and socially unacceptable scenarios of discrimination and unfairness are likely to arise unless these issues are explicitly addressed. This undesirable behavior has several possible sources, such as biased datasets used for training that may not be detected in black-box models. After pointing out connections between such bias of AI and the problem of induction, we focus on Popper's contributions after Hume's, which offer a logical theory of preferences. An AI model can be preferred over others on purely rational grounds after one or more attempts at refutation based on accuracy and fairness. Inspired by such epistemological principles, this paper proposes a structured approach to mitigate discrimination and unfairness caused by bias in AI systems. In the proposed computational framework, models are selected and enhanced after attempts at refutation. To illustrate our discussion, we focus on hiring decision scenarios where an AI system filters in which job applicants should go to the interview phase.
Integrating Privacy-Enhancing Technologies into the Internet Infrastructure
Venue: arXiv cs.CR 2017
Year: 2017

The AN.ON-Next project aims to integrate privacy-enhancing technologies into the internet's infrastructure and establish them in the consumer mass market. The technologies in focus include a basis protection at internet service provider level, an improved overlay network-based protection and a concept for privacy protection in the emerging 5G mobile network. A crucial success factor will be the viable adjustment and development of standards, business models and pricing strategies for those new technologies.
Abstract Interpretation of Binary Code with Memory Accesses using Polyhedra
Venue: arXiv cs.PL 2017
Year: 2017

In this paper we propose a novel methodology for static analysis of binary code using abstract interpretation. We use an abstract domain based on polyhedra and two mapping functions that associate polyhedra variables with registers and memory. We demonstrate our methodology to the problem of computing upper bounds to loop iterations in the code. This problem is particularly important in the domain of Worst-Case Execution Time (WCET) analysis of safety-critical real-time code. However, our approach is general and it can applied to other static analysis problems.
Evaluating the Performance of eMTC and NB-IoT for Smart City Applications
Venue: arXiv cs.IT 2017
Year: 2017

Low power wide area network (LPWAN) is a wireless telecommunication network that is designed for interconnecting devices with low bitrate focusing on long range and power efficiency. In this paper, we study two recent technologies built from existing Long-Term Evolution (LTE) functionalities: Enhanced machine type communications (eMTC) and Narrow band internet of things (NB-IoT). These technologies are designed to coexist with existing LTE infrastructure, spectrum, and devices. We first briefly introduce both systems and then compare their performance in terms of energy consumption, latency and scalability. We introduce a model for calculating the energy consumption and study the effect of clock drift and propose a method to overcome it. We also propose a model for analytically evaluating the latency and the maximum number of devices in a network. Furthermore, we implement the main functionality of both technologies and simulate the end-to-end latency and maximum number of devices in a discrete-event network simulator NS-3. Numerical results show that 8 years battery life time can be achieved by both technologies in a poor coverage scenario and that depending on the coverage conditions and data length, one technology consumes less energy than the other. The results also show that eMTC can serve more devices in a network than NB-IoT, while providing a latency that is 10 times lower.
Facets, Tiers and Gems: Ontology Patterns for Hypernormalisation
Venue: arXiv cs.AI 2017
Year: 2017

There are many methodologies and techniques for easing the task of ontology building. Here we describe the intersection of two of these: ontology normalisation and fully programmatic ontology development. The first of these describes a standardized organisation for an ontology, with singly inherited self-standing entities, and a number of small taxonomies of refining entities. The former are described and defined in terms of the latter and used to manage the polyhierarchy of the self-standing entities. Fully programmatic development is a technique where an ontology is developed using a domain-specific language within a programming language, meaning that as well defining ontological entities, it is possible to add arbitrary patterns or new syntax within the same environment. We describe how new patterns can be used to enable a new style of ontology development that we call hypernormalisation.
Bitmap Filter: Speeding up Exact Set Similarity Joins with Bitwise Operations
Venue: arXiv cs.DB 2017
Year: 2017

The Exact Set Similarity Join problem aims to find all similar sets between two collections of sets, with respect to a threshold and a similarity function such as overlap, Jaccard, dice or cosine. The naive approach verifies all pairs of sets and it is often considered impractical due the high number of combinations. So, Exact Set Similarity Join algorithms are usually based on the Filter-Verification Framework, that applies a series of filters to reduce the number of verified pairs. This paper presents a new filtering technique called Bitmap Filter, which is able to accelerate state-of-the-art algorithms for the exact Set Similarity Join problem. The Bitmap Filter uses hash functions to create bitmaps of fixed b bits, representing characteristics of the sets. Then, it applies bitwise operations (such as xor and population count) on the bitmaps in order to infer a similarity upper bound for each pair of sets. If the upper bound is below a given similarity threshold, the pair of sets is pruned. The Bitmap Filter benefits from the fact that bitwise operations are efficiently implemented by many modern general-purpose processors and it was easily applied to four state-of-the-art algorithms implemented in CPU: AllPairs, PPJoin, AdaptJoin and GroupJoin. Furthermore, we propose a Graphic Processor Unit (GPU) algorithm based on the naive approach but using the Bitmap Filter to speedup the computation. The experiments considered 9 collections containing from 100 thousands up to 10 million sets and the joins were made using Jaccard thresholds from 0.50 to 0.95. The Bitmap Filter was able to improve 90% of the experiments in CPU, with speedups of up to 4.50x and 1.43x on average. Using the GPU algorithm, the experiments were able to speedup the original CPU algorithms by up to 577x using an Nvidia Geforce GTX 980 Ti.
Zero-shot Learning via Shared-Reconstruction-Graph Pursuit
Venue: arXiv cs.CV 2017
Year: 2017

Zero-shot learning (ZSL) aims to recognize objects from novel unseen classes without any training data. Recently, structure-transfer based methods are proposed to implement ZSL by transferring structural knowledge from the semantic embedding space to image feature space to classify testing images. However, we observe that such a knowledge transfer framework may suffer from the problem of the geometric inconsistency between the data in the training and testing spaces. We call this problem as the space shift problem. In this paper, we propose a novel graph based method to alleviate this space shift problem. Specifically, a Shared Reconstruction Graph (SRG) is pursued to capture the common structure of data in the two spaces. With the learned SRG, each unseen class prototype (cluster center) in the image feature space can be synthesized by the linear combination of other class prototypes, so that testing instances can be classified based on the distance to these synthesized prototypes. The SRG bridges the image feature space and semantic embedding space. By applying spectral clustering on the learned SRG, many meaningful clusters can be discovered, which interprets ZSL performance on the datasets. Our method can be easily extended to the generalized zero-shot learning setting. Experiments on three popular datasets show that our method outperforms other methods on all datasets. Even with a small number of training samples, our method can achieve the state-of-the-art performance.
A Novel Convolutional Neural Network for Image Steganalysis with Shared Normalization
Venue: arXiv cs.MM 2017
Year: 2017

Deep learning based image steganalysis has attracted increasing attentions in recent years. Several Convolutional Neural Network (CNN) models have been proposed and achieved state-of-the-art performances on detecting steganography. In this paper, we explore an important technique in deep learning, the batch normalization, for the task of image steganalysis. Different from natural image classification, steganalysis is to discriminate cover images and stego images which are the result of adding weak stego signals into covers. This characteristic makes a cover image is more statistically similar to its stego than other cover images, requiring steganalytic methods to use paired learning to extract effective features for image steganalysis. Our theoretical analysis shows that a CNN model with multiple normalization layers is hard to be generalized to new data in the test set when it is well trained with paired learning. To hand this difficulty, we propose a novel normalization technique called Shared Normalization (SN) in this paper. Unlike the batch normalization layer utilizing the mini-batch mean and standard deviation to normalize each input batch, SN shares same statistics for all training and test batches. Based on the proposed SN layer, we further propose a novel neural network model for image steganalysis. Extensive experiments demonstrate that the proposed network with SN layers is stable and can detect the state of the art steganography with better performances than previous methods.
Performance of In-band Transmission of System Information in Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

We consider transmission of system information in massive MIMO. This information needs to be reliably delivered to inactive users in the cell without any channel state information at the base station. Downlink transmission entails the use of downlink pilots and a special type of precoding that aims to reduce the dimension of the downlink channel and the pilot overhead, which would otherwise scale with the number of base station antennas. We consider a scenario in which the base station transmits over a small number of coherence intervals, providing little time/frequency diversity. The system information is transmitted with orthogonal space-time block codes to increase reliability and performance is measured using outage rates. Several different codes are compared, both for spatially correlated and uncorrelated channels and for varying amount of time/frequency diversity. We show that a massive MIMO base station can outperform a single-antenna base station in all considered scenarios.
Related family-based attribute reduction of covering information systems when varying attribute sets
Venue: arXiv cs.AI 2017
Year: 2017

In practical situations, there are many dynamic covering information systems with variations of attributes, but there are few studies on related family-based attribute reduction of dynamic covering information systems. In this paper, we first investigate updated mechanisms of constructing attribute reducts for consistent and inconsistent covering information systems when varying attribute sets by using related families. Then we employ examples to illustrate how to compute attribute reducts of dynamic covering information systems with variations of attribute sets. Finally, the experimental results illustrates that the related family-based methods are effective to perform attribute reduction of dynamic covering information systems when attribute sets are varying with time.
Memory Based Online Learning of Deep Representations from Video Streams
Venue: arXiv cs.CV 2017
Year: 2017

We present a novel online unsupervised method for face identity learning from video streams. The method exploits deep face descriptors together with a memory based learning mechanism that takes advantage of the temporal coherence of visual data. Specifically, we introduce a discriminative feature matching solution based on Reverse Nearest Neighbour and a feature forgetting strategy that detect redundant features and discard them appropriately while time progresses. It is shown that the proposed learning procedure is asymptotically stable and can be effectively used in relevant applications like multiple face identification and tracking from unconstrained video streams. Experimental results show that the proposed method achieves comparable results in the task of multiple face tracking and better performance in face identification with offline approaches exploiting future information. Code will be publicly available.
Applications and Challenges of Real-time Mobile DNA Analysis
Venue: arXiv cs.CE 2017
Year: 2017

The DNA sequencing is the process of identifying the exact order of nucleotides within a given DNA molecule. The new portable and relatively inexpensive DNA sequencers, such as Oxford Nanopore MinION, have the potential to move DNA sequencing outside of laboratory, leading to faster and more accessible DNA-based diagnostics. However, portable DNA sequencing and analysis are challenging for mobile systems, owing to high data throughputs and computationally intensive processing performed in environments with unreliable connectivity and power. In this paper, we provide an analysis of the challenges that mobile systems and mobile computing must address to maximize the potential of portable DNA sequencing, and in situ DNA analysis. We explain the DNA sequencing process and highlight the main differences between traditional and portable DNA sequencing in the context of the actual and envisioned applications. We look at the identified challenges from the perspective of both algorithms and systems design, showing the need for careful co-design.
Majority Model on Random Regular Graphs
Venue: arXiv cs.DS 2017
Year: 2017

Consider a graph $G=(V,E)$ and an initial random coloring where each vertex $v \in V$ is blue with probability $P_b$ and red otherwise, independently from all other vertices. In each round, all vertices simultaneously switch their color to the most frequent color in their neighborhood and in case of a tie, a vertex keeps its current color. The main goal of the present paper is to analyze the behavior of this basic and natural process on the random $d$-regular graph $\mathbb{G}_{n,d}$. It is shown that for all $ε>0$, $P_b \le 1/2-ε$ results in final complete occupancy by red in $\mathcal{O}(\log_d\log n)$ rounds with high probability, provided that $d\geq c/ε^2$ for a suitable constant $c$. Furthermore, we show that with high probability, $\mathbb{G}_{n,d}$ is immune; i.e., the smallest dynamic monopoly is of linear size. A dynamic monopoly is a subset of vertices that can take over in the sense that a commonly chosen initial color eventually spreads throughout the whole graph, irrespective of the colors of other vertices. This answers an open question of Peleg.