OpenRaiser/Intern-Atlas huggingface dataset:
Size-aware Sharding For Improving Tail Latencies in In-memory Key-value Stores
Venue: arXiv cs.DB 2018
Year: 2018

This paper introduces the concept of size-aware sharding to improve tail latencies for in-memory key-value stores, and describes its implementation in the Minos key-value store. Tail latencies are crucial in distributed applications with high fan-out ratios, because overall response time is determined by the slowest response. Size-aware sharding distributes requests for keys to cores according to the size of the item associated with the key. In particular, requests for small and large items are sent to disjoint subsets of cores. Size-aware sharding improves tail latencies by avoiding head-of-line blocking, in which a request for a small item gets queued behind a request for a large item. Alternative size-unaware approaches to sharding, such as keyhash-based sharding, request dispatching and stealing do not avoid head-of-line blocking, and therefore exhibit worse tail latencies. The challenge in implementing size-aware sharding is to maintain high throughput by avoiding the cost of software dispatching and by achieving load balancing between different cores. Minos uses hardware dispatch for all requests for small items, which form the very large majority of all requests. It achieves load balancing by adapting the number of cores handling requests for small and large items to their relative presence in the workload. We compare Minos to three state-of-the-art designs of in-memory KV stores. Compared to its closest competitor, Minos achieves a 99th percentile latency that is up to two orders of magnitude lower. Put differently, for a given value for the 99th percentile latency equal to 10 times the mean service time, Minos achieves a throughput that is up to 7.4 times higher.
Improved Runtime Bounds for the Univariate Marginal Distribution Algorithm via Anti-Concentration
Venue: arXiv cs.NE 2018
Year: 2018

Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that EDAs may improve optimisation performance on epistatic fitness landscapes by learning variable interactions. However, hardly any rigorous results are available to support claims about the performance of EDAs, even for fitness functions without epistasis. The expected runtime of the Univariate Marginal Distribution Algorithm (UMDA) on OneMax was recently shown to be in $\mathcal{O}\left(nλ\log λ\right)$ by Dang and Lehre (GECCO 2015). Later, Krejca and Witt (FOGA 2017) proved the lower bound $Ω\left(λ\sqrt{n}+n\log n\right)$ via an involved drift analysis. We prove a $\mathcal{O}\left(nλ\right)$ bound, given some restrictions on the population size. This implies the tight bound $Θ\left(n\log n\right)$ when $λ=\mathcal{O}\left(\log n\right)$, matching the runtime of classical EAs. Our analysis uses the level-based theorem and anti-concentration properties of the Poisson-Binomial distribution. We expect that these generic methods will facilitate further analysis of EDAs.
A cost effective and reliable environment monitoring system for HPC applications
Venue: arXiv cs.OH 2018
Year: 2018

We present a slow control system to gather all relevant environment information necessary to effectively and reliably run an HPC (High Performance Computing) system at a high value over price ratio. The scalable and reliable overall concept is presented as well as a newly developed hardware device for sensor read out. This device incorporates a Raspberry Pi, an Arduino and PoE (Power over Ethernet) functionality in a compact form factor. The system is in use at the 2 PFLOPS cluster of the Johannes Gutenberg-University and Helmholtz-Institute in Mainz.
Infinitary and Cyclic Proof Systems for Transitive Closure Logic
Venue: arXiv cs.LO 2018
Year: 2018

Transitive closure logic is a known extension of first-order logic obtained by introducing a transitive closure operator. While other extensions of first-order logic with inductive definitions are a priori parametrized by a set of inductive definitions, the addition of the transitive closure operator uniformly captures all finitary inductive definitions. In this paper we present an infinitary proof system for transitive closure logic which is an infinite descent-style counterpart to the existing (explicit induction) proof system for the logic. We show that, as for similar systems for first-order logic with inductive definitions, our infinitary system is complete for the standard semantics and subsumes the explicit system. Moreover, the uniformity of the transitive closure operator allows semantically meaningful complete restrictions to be defined using simple syntactic criteria. Consequently, the restriction to regular infinitary (i.e. cyclic) proofs provides the basis for an effective system for automating inductive reasoning.
A Model for Learned Bloom Filters and Related Structures
Venue: arXiv cs.DS 2018
Year: 2018

Recent work has suggested enhancing Bloom filters by using a pre-filter, based on applying machine learning to model the data set the Bloom filter is meant to represent. Here we model such learned Bloom filters, clarifying what guarantees can and cannot be associated with such a structure.
Left-Center-Right Separated Neural Network for Aspect-based Sentiment Analysis with Rotatory Attention
Venue: arXiv cs.CL 2018
Year: 2018

Deep learning techniques have achieved success in aspect-based sentiment analysis in recent years. However, there are two important issues that still remain to be further studied, i.e., 1) how to efficiently represent the target especially when the target contains multiple words; 2) how to utilize the interaction between target and left/right contexts to capture the most important words in them. In this paper, we propose an approach, called left-center-right separated neural network with rotatory attention (LCR-Rot), to better address the two problems. Our approach has two characteristics: 1) it has three separated LSTMs, i.e., left, center and right LSTMs, corresponding to three parts of a review (left context, target phrase and right context); 2) it has a rotatory attention mechanism which models the relation between target and left/right contexts. The target2context attention is used to capture the most indicative sentiment words in left/right contexts. Subsequently, the context2target attention is used to capture the most important word in the target. This leads to a two-side representation of the target: left-aware target and right-aware target. We compare our approach on three benchmark datasets with ten related methods proposed recently. The results show that our approach significantly outperforms the state-of-the-art techniques.
A deep tree-based model for software defect prediction
Venue: arXiv cs.SE 2018
Year: 2018

Defects are common in software systems and can potentially cause various problems to software users. Different methods have been developed to quickly predict the most likely locations of defects in large code bases. Most of them focus on designing features (e.g. complexity metrics) that correlate with potentially defective code. Those approaches however do not sufficiently capture the syntax and different levels of semantics of source code, an important capability for building accurate prediction models. In this paper, we develop a novel prediction model which is capable of automatically learning features for representing source code and using them for defect prediction. Our prediction system is built upon the powerful deep learning, tree-structured Long Short Term Memory network which directly matches with the Abstract Syntax Tree representation of source code. An evaluation on two datasets, one from open source projects contributed by Samsung and the other from the public PROMISE repository, demonstrates the effectiveness of our approach for both within-project and cross-project predictions.
Deep Learning Framework for Multi-class Breast Cancer Histology Image Classification
Venue: arXiv cs.CV 2018
Year: 2018

In this work, we present a deep learning framework for multi-class breast cancer image classification as our submission to the International Conference on Image Analysis and Recognition (ICIAR) 2018 Grand Challenge on BreAst Cancer Histology images (BACH). As these histology images are too large to fit into GPU memory, we first propose using Inception V3 to perform patch level classification. The patch level predictions are then passed through an ensemble fusion framework involving majority voting, gradient boosting machine (GBM), and logistic regression to obtain the image level prediction. We improve the sensitivity of the Normal and Benign predicted classes by designing a Dual Path Network (DPN) to be used as a feature extractor where these extracted features are further sent to a second layer of ensemble prediction fusion using GBM, logistic regression, and support vector machine (SVM) to refine predictions. Experimental results demonstrate our framework shows a 12.5$\%$ improvement over the state-of-the-art model.
Ensembling Neural Networks for Digital Pathology Images Classification and Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

In the last years, neural networks have proven to be a powerful framework for various image analysis problems. However, some application domains have specific limitations. Notably, digital pathology is an example of such fields due to tremendous image sizes and quite limited number of training examples available. In this paper, we adopt state-of-the-art convolutional neural networks (CNN) architectures for digital pathology images analysis. We propose to classify image patches to increase effective sample size and then to apply an ensembling technique to build prediction for the original images. To validate the developed approaches, we conducted experiments with \textit{Breast Cancer Histology Challenge} dataset and obtained 90\% accuracy for the 4-class tissue classification task.
Image Posterization Using Fuzzy Logic and Bilateral Filter
Venue: arXiv cs.CV 2018
Year: 2018

Image posterization is converting images with a large number of tones into synthetic images with distinct flat areas and a fewer number of tones. In this technical report, we present the implementation and results of using fuzzy logic in order to generate a posterized image in a simple and fast way. The image filter is based on fuzzy logic and bilateral filtering; where, the given image is blurred to remove small details. Then, the fuzzy logic is used to classify each pixel into one of three specific categories in order to reduce the number of colors. This filter was developed during building the Specs on Face dataset in order to add a new level of difficulty to the original face images in the dataset. This filter does not hurt the human detection performance; however, it is considered a hindrance evading the face detection process. This filter can be used generally for posterizing images, especially those have a high contrast to get images with vivid colors.
A Graph Theoretic Approach for Training Overhead Reduction in FDD Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

The overheads associated with feedback-based channel acquisition can greatly compromise the achievable rates of FDD based massive MIMO systems. Indeed, downlink (DL) training and uplink (UL) feedback overheads scale linearly with the number of base station (BS) antennas, in sharp contrast to TDD-based massive MIMO, where a single UL pilot trains the whole BS array. In this work, we propose a graph-theoretic approach to reducing DL training and UL feedback overheads in FDD massive MIMO systems. In particular, we consider a single-cell scenario involving a single BS with a massive antenna array serving to single-antenna mobile stations (MSs) in the DL. We assume the BS employs two-stage beamforming in the DL, comprising DFT pre-beamforming followed by MU-MIMO precoding. The proposed graph-theoretic approach exploits knowledge of the angular spectra of the BS-MS channels to construct DL training protocols with reduced overheads. Simulation results reveal that the proposed training-resources allocation method can provide approximately 35% sum-rate performance gain compared to conventional orthogonal training. Our analysis also sheds light into the impact of overhead reduction on channel estimation quality, and, in turn, achievable rates.
An Area and Energy Efficient Design of Domain-Wall Memory-Based Deep Convolutional Neural Networks using Stochastic Computing
Venue: arXiv cs.NE 2018
Year: 2018

With recent trend of wearable devices and Internet of Things (IoTs), it becomes attractive to develop hardware-based deep convolutional neural networks (DCNNs) for embedded applications, which require low power/energy consumptions and small hardware footprints. Recent works demonstrated that the Stochastic Computing (SC) technique can radically simplify the hardware implementation of arithmetic units and has the potential to satisfy the stringent power requirements in embedded devices. However, in these works, the memory design optimization is neglected for weight storage, which will inevitably result in large hardware cost. Moreover, if conventional volatile SRAM or DRAM cells are utilized for weight storage, the weights need to be re-initialized whenever the DCNN platform is re-started. In order to overcome these limitations, in this work we adopt an emerging non-volatile Domain-Wall Memory (DWM), which can achieve ultra-high density, to replace SRAM for weight storage in SC-based DCNNs. We propose DW-CNN, the first comprehensive design optimization framework of DWM-based weight storage method. We derive the optimal memory type, precision, and organization, as well as whether to store binary or stochastic numbers. We present effective resource sharing scheme for DWM-based weight storage in the convolutional and fully-connected layers of SC-based DCNNs to achieve a desirable balance among area, power (energy) consumption, and application-level accuracy.
Fairness and Accountability Design Needs for Algorithmic Support in High-Stakes Public Sector Decision-Making
Venue: arXiv cs.CY 2018
Year: 2018

Calls for heightened consideration of fairness and accountability in algorithmically-informed public decisions---like taxation, justice, and child protection---are now commonplace. How might designers support such human values? We interviewed 27 public sector machine learning practitioners across 5 OECD countries regarding challenges understanding and imbuing public values into their work. The results suggest a disconnect between organisational and institutional realities, constraints and needs, and those addressed by current research into usable, transparent and 'discrimination-aware' machine learning---absences likely to undermine practical initiatives unless addressed. We see design opportunities in this disconnect, such as in supporting the tracking of concept drift in secondary data sources, and in building usable transparency tools to identify risks and incorporate domain knowledge, aimed both at managers and at the 'street-level bureaucrats' on the frontlines of public service. We conclude by outlining ethical challenges and future directions for collaboration in these high-stakes applications.
Multi-task Learning for Continuous Control
Venue: arXiv cs.LG 2018
Year: 2018

Reliable and effective multi-task learning is a prerequisite for the development of robotic agents that can quickly learn to accomplish related, everyday tasks. However, in the reinforcement learning domain, multi-task learning has not exhibited the same level of success as in other domains, such as computer vision. In addition, most reinforcement learning research on multi-task learning has been focused on discrete action spaces, which are not used for robotic control in the real-world. In this work, we apply multi-task learning methods to continuous action spaces and benchmark their performance on a series of simulated continuous control tasks. Most notably, we show that multi-task learning outperforms our baselines and alternative knowledge sharing methods.
Dynamics of Opinions with Social Biases
Venue: arXiv cs.SI 2018
Year: 2018

This paper aims to provide a systemic analysis to social opinion dynamics subject to individual biases. As a generalization of the classical DeGroot social interactions, defined by linearly coupled dynamics of peer opinions that evolve over time, biases add to state-dependent edge weights and therefore lead to highly nonlinear network dynamics. Previous studies have dealt with convergence and stability analysis of such systems for a few specific initial node opinions and network structures, and here we focus on how individual biases affect social equilibria and their stabilities. First of all, we prove that when the initial network opinions are polarized towards one side of the state space, node biases will drive the opinion evolution to the corresponding interval boundaries. Such polarization attraction effect continues to hold under even directed and switching network structures. Next, for a few fundamental network structures, some important interior network equilibria are presented explicitly for a wide range of system parameters, which are shown to be locally unstable in general. Particularly, the interval centroid is proven to be unstable regardless of the bias level and the network topologies.
Interval Consensus for Multiagent Networks
Venue: arXiv cs.SY 2018
Year: 2018

The constrained consensus problem considered in this paper, denoted interval consensus, is characterized by the fact that each agent can impose a lower and upper bound on the achievable consensus value. Such constraints can be encoded in the consensus dynamics by saturating the values that an agent transmits to its neighboring nodes. We show in the paper that when the intersection of the intervals imposed by the agents is nonempty, the resulting constrained consensus problem must converge to a common value inside that intersection. In our algorithm, convergence happens in a fully distributed manner, and without need of sharing any information on the individual constraining intervals. When the intersection of the intervals is an empty set, the intrinsic nonlinearity of the network dynamics raises new challenges in understanding the node state evolution. Using Brouwer fixed-point theorem we prove that in that case there exists at least one equilibrium, and in fact the possible equilibria are locally stable if the constraints are satisfied or dissatisfied at the same time among all nodes. For graphs with sufficient sparsity it is further proven that there is a unique equilibrium that is globally attractive if the constraint intervals are pairwise disjoint.
Deep Temporal Clustering : Fully Unsupervised Learning of Time-Domain Features
Venue: arXiv cs.LG 2018
Year: 2018

Unsupervised learning of time series data, also known as temporal clustering, is a challenging problem in machine learning. Here we propose a novel algorithm, Deep Temporal Clustering (DTC), to naturally integrate dimensionality reduction and temporal clustering into a single end-to-end learning framework, fully unsupervised. The algorithm utilizes an autoencoder for temporal dimensionality reduction and a novel temporal clustering layer for cluster assignment. Then it jointly optimizes the clustering objective and the dimensionality reduction objec tive. Based on requirement and application, the temporal clustering layer can be customized with any temporal similarity metric. Several similarity metrics and state-of-the-art algorithms are considered and compared. To gain insight into temporal features that the network has learned for its clustering, we apply a visualization method that generates a region of interest heatmap for the time series. The viability of the algorithm is demonstrated using time series data from diverse domains, ranging from earthquakes to spacecraft sensor data. In each case, we show that the proposed algorithm outperforms traditional methods. The superior performance is attributed to the fully integrated temporal dimensionality reduction and clustering criterion.
Power Allocation Strategy of Maximizing Secrecy Rate for Secure Directional Modulation Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, given the beamforming vector of confidential messages and artificial noise (AN) projection matrix and total power constraint, a power allocation (PA) strategy of maximizing secrecy rate (Max-SR) is proposed for secure directional modulation (DM) networks. By the method of Lagrange multiplier, the analytic expression of the proposed PA strategy is derived. To confirm the benefit from the Max-SR-based PA strategy, we take the null-space projection (NSP) beamforming scheme as an example and derive its closed-form expression of optimal PA strategy. From simulation results, we find the following facts: in the medium and high signal-to-noise-ratio (SNR) regions, compared with three typical PA parameters such $β=0.1, 0.5$, and $0.9$, the optimal PA shows a substantial SR performance gain with maximum gain percent up to more than $60\%$. Additionally, as the PA factor increases from 0 to 1, the achievable SR increases accordingly in the low SNR region whereas it first increases and then decreases in the medium and high SNR regions, where the SR can be approximately viewed as a convex function of the PA factor. Finally, as the number of antennas increases, the optimal PA factor becomes large and tends to one in the medium and high SNR region. In other words, the contribution of AN to SR can be trivial in such a situation.
Weighted Hamming Metric Structures
Venue: arXiv cs.IT 2018
Year: 2018

A weighted Hamming metric is introduced in [4] and it showed that the binary generalized Goppa code is a perfect code in some weighted Hamming metric. In this paper, we study the weight structures which admit the binary Hamming code and the extended binary Hamming code to be perfect codes in the weighted Hamming metric. And, we also give some structures of a 2-perfect code and how to construct a 2-perfect code in some weighted Hamming metric.
Pair-Linking for Collective Entity Disambiguation: Two Could Be Better Than All
Venue: arXiv cs.IR 2018
Year: 2018

Collective entity disambiguation aims to jointly resolve multiple mentions by linking them to their associated entities in a knowledge base. Previous works are primarily based on the underlying assumption that entities within the same document are highly related. However, the extend to which these mentioned entities are actually connected in reality is rarely studied and therefore raises interesting research questions. For the first time, we show that the semantic relationships between the mentioned entities are in fact less dense than expected. This could be attributed to several reasons such as noise, data sparsity and knowledge base incompleteness. As a remedy, we introduce MINTREE, a new tree-based objective for the entity disambiguation problem. The key intuition behind MINTREE is the concept of coherence relaxation which utilizes the weight of a minimum spanning tree to measure the coherence between entities. Based on this new objective, we design a novel entity disambiguation algorithms which we call Pair-Linking. Instead of considering all the given mentions, Pair-Linking iteratively selects a pair with the highest confidence at each step for decision making. Via extensive experiments, we show that our approach is not only more accurate but also surprisingly faster than many state-of-the-art collective linking algorithms.