OpenRaiser/Intern-Atlas huggingface dataset:
Heterogeneous-Reliability Memory: Exploiting Application-Level Memory Error Tolerance
Venue: arXiv cs.DC 2018
Year: 2018

This paper summarizes our work on characterizing application memory error vulnerability to optimize datacenter cost via Heterogeneous-Reliability Memory (HRM), which was published in DSN 2014, and examines the work's significance and future potential. Memory devices represent a key component of datacenter total cost of ownership (TCO), and techniques used to reduce errors that occur on these devices increase this cost. Existing approaches to providing reliability for memory devices pessimistically treat all data as equally vulnerable to memory errors. Our key insight is that there exists a diverse spectrum of tolerance to memory errors in new data-intensive applications, and that traditional one-size-fits-all memory reliability techniques are inefficient in terms of cost. This presents an opportunity to greatly reduce server hardware cost by provisioning the right amount of memory reliability for different applications. Toward this end, in our DSN 2014 paper, we make three main contributions to enable highly-reliable servers at low datacenter cost. First, we develop a new methodology to quantify the tolerance of applications to memory errors. Second, using our methodology, we perform a case study of three new data-intensive workloads (an interactive web search application, an in-memory key--value store, and a graph mining framework) to identify new insights into the nature of application memory error vulnerability. Third, based on our insights, we propose several new hardware/software heterogeneous-reliability memory system designs to lower datacenter cost while achieving high reliability and discuss their trade-offs. We show that our new techniques can reduce server hardware cost by 4.7% while achieving 99.90% single server availability.
Polar Coding for Processes with Memory
Venue: arXiv cs.IT 2018
Year: 2018

We study polar coding for stochastic processes with memory. For example, a process may be defined by the joint distribution of the input and output of a channel. The memory may be present in the channel, the input, or both. We show that $ψ$-mixing processes polarize under the standard Arıkan transform, under a mild condition. We further show that the rate of polarization of the \emph{low-entropy} synthetic channels is roughly $O(2^{-\sqrt{N}})$, where $N$ is the blocklength. That is, essentially the same rate as in the memoryless case.
Multi-Unit Facility Location Games
Venue: arXiv cs.GT 2018
Year: 2018

Facility location games have been a topic of major interest in economics, operations research and computer science, starting from the seminal work by Hotelling. In the classical pure location Hotelling game businesses compete for maximizing customer attraction by strategically locating their facilities, assuming no price competition, while customers are attracted to their closest facilities. Surprisingly, very little rigorous work has been presented on multi-unit facility location games, where the classical pure location Hotelling games are extended to contexts where each player is to locate several facilities. In this paper we present two major contributions to the study of multi-unit pure location Hotelling games. In the first part of this paper we deal with the two-player multi-unit setting, and fully characterize its equilibria. In the second part of this paper we deal with multi-unit facility location games, with $N\geq 3$ players; our main result in this part is the full characterization of the settings where pure strategy equilibria exist. Our results also extend classical results on necessary and sufficient conditions for a strategy profile to be in equilibrium in a pure location (single-unit) Hotelling game to multi-unit pure location games.
Decoupled Dynamics Distributed Control for Strings of Nonlinear Autonomous Agents
Venue: arXiv cs.SY 2018
Year: 2018

We introduce a distributed control architecture for a class of heterogeneous, nonlinear dynamical agents moving in the "string" formation, while guaranteeing trajectory tracking, collision avoidance and the preservation of the formation's topology. Each autonomous agent uses information and relative measurements only with respect to its predecessor in the string. The performance of the scheme is independent of the number of agents in the network and also on the agent's relative position in the network. The scalability is a consequence of the "decoupling" of a certain bounded approximation of the closed--loop equations, which allows the regulation and controller design (at each agent) to be done individually, in a completely decentralized manner. A practical method for compensating communication induced delays is also presented. Numerical examples illustrate the effectiveness and the main features of the proposed approach.
Axiomatizations of Team Logics
Venue: arXiv cs.LO 2018
Year: 2018

In a modular approach, we lift Hilbert-style proof systems for propositional, modal and first-order logic to generalized systems for their respective team-based extensions. We obtain sound and complete axiomatizations for the dependence-free fragment FO(~) of Väänänen's first-order team logic TL, for propositional team logic PTL, quantified propositional team logic QPTL, modal team logic MTL, and for the corresponding logics of dependence, independence, inclusion and exclusion. As a crucial step in the completeness proof, we show that the above logics admit, in a particular sense, a semantics-preserving elimination of modalities and quantifiers from formulas.
Learning to SMILE(S)
Venue: arXiv cs.CL 2018
Year: 2018

This paper shows how one can directly apply natural language processing (NLP) methods to classification problems in cheminformatics. Connection between these seemingly separate fields is shown by considering standard textual representation of compound, SMILES. The problem of activity prediction against a target protein is considered, which is a crucial part of computer aided drug design process. Conducted experiments show that this way one can not only outrank state of the art results of hand crafted representations but also gets direct structural insights into the way decisions are made.
Deep Learning in Finance
Venue: arXiv cs.LG 2018
Year: 2018

We explore the use of deep learning hierarchical models for problems in financial prediction and classification. Financial prediction problems -- such as those presented in designing and pricing securities, constructing portfolios, and risk management -- often involve large data sets with complex data interactions that currently are difficult or impossible to specify in a full economic model. Applying deep learning methods to these problems can produce more useful results than standard methods in finance. In particular, deep learning can detect and exploit interactions in the data that are, at least currently, invisible to any existing financial economic theory.
StreamingBandit; Experimenting with Bandit Policies
Venue: arXiv cs.HC 2018
Year: 2018

A large number of statistical decision problems in the social sciences and beyond can be framed as a (contextual) multi-armed bandit problem. However, it is notoriously hard to develop and evaluate policies that tackle these types of problem, and to use such policies in applied studies. To address this issue, this paper introduces StreamingBandit, a Python web application for developing and testing bandit policies in field studies. StreamingBandit can sequentially select treatments using (online) policies in real time. Once StreamingBandit is implemented in an applied context, different policies can be tested, altered, nested, and compared. StreamingBandit makes it easy to apply a multitude of bandit policies for sequential allocation in field experiments, and allows for the quick development and re-use of novel policies. In this article, we detail the implementation logic of StreamingBandit and provide several examples of its use.
Submodular Learning and Covering with Response-Dependent Costs
Venue: arXiv cs.LG 2018
Year: 2018

We consider interactive learning and covering problems, in a setting where actions may incur different costs, depending on the response to the action. We propose a natural greedy algorithm for response-dependent costs. We bound the approximation factor of this greedy algorithm in active learning settings as well as in the general setting. We show that a different property of the cost function controls the approximation factor in each of these scenarios. We further show that in both settings, the approximation factor of this greedy algorithm is near-optimal among all greedy algorithms. Experiments demonstrate the advantages of the proposed algorithm in the response-dependent cost setting.
Simple Bayesian Algorithms for Best Arm Identification
Venue: arXiv cs.LG 2018
Year: 2018

This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. This paper proposes three simple and intuitive Bayesian algorithms for adaptively allocating measurement effort, and formalizes a sense in which these seemingly naive rules are the best possible. One proposal is top-two probability sampling, which computes the two designs with the highest posterior probability of being optimal, and then randomizes to select among these two. One is a variant of top-two sampling which considers not only the probability a design is optimal, but the expected amount by which its quality exceeds that of other designs. The final algorithm is a modified version of Thompson sampling that is tailored for identifying the best design. We prove that these simple algorithms satisfy a sharp optimality property. In a frequentist setting where the true quality of the designs is fixed, one hopes the posterior definitively identifies the optimal design, in the sense that that the posterior probability assigned to the event that some other design is optimal converges to zero as measurements are collected. We show that under the proposed algorithms this convergence occurs at an exponential rate, and the corresponding exponent is the best possible among all allocation
Identification of Parallel Passages Across a Large Hebrew/Aramaic Corpus
Venue: arXiv cs.CL 2018
Year: 2018

We propose a method for efficiently finding all parallel passages in a large corpus, even if the passages are not quite identical due to rephrasing and orthographic variation. The key ideas are the representation of each word in the corpus by its two most infrequent letters, finding matched pairs of strings of four or five words that differ by at most one word and then identifying clusters of such matched pairs. Using this method, over 4600 parallel pairs of passages were identified in the Babylonian Talmud, a Hebrew-Aramaic corpus of over 1.8 million words, in just over 30 seconds. Empirical comparisons on sample data indicate that the coverage obtained by our method is essentially the same as that obtained using slow exhaustive methods.
Automated Clustering and Program Repair for Introductory Programming Assignments
Venue: arXiv cs.PL 2018
Year: 2018

Providing feedback on programming assignments is a tedious task for the instructor, and even impossible in large Massive Open Online Courses with thousands of students. Previous research has suggested that program repair techniques can be used to generate feedback in programming education. In this paper, we present a novel fully automated program repair algorithm for introductory programming assignments. The key idea of the technique, which enables automation and scalability, is to use the existing correct student solutions to repair the incorrect attempts. We evaluate the approach in two experiments: (I) We evaluate the number, size and quality of the generated repairs on 4,293 incorrect student attempts from an existing MOOC. We find that our approach can repair 97% of student attempts, while 81% of those are small repairs of good quality. (II) We conduct a preliminary user study on performance and repair usefulness in an interactive teaching setting. We obtain promising initial results (the average usefulness grade 3.4 on a scale from 1 to 5), and conclude that our approach can be used in an interactive setting.
Bayesian Opponent Exploitation in Imperfect-Information Games
Venue: arXiv cs.GT 2018
Year: 2018

Two fundamental problems in computational game theory are computing a Nash equilibrium and learning to exploit opponents given observations of their play (opponent exploitation). The latter is perhaps even more important than the former: Nash equilibrium does not have a compelling theoretical justification in game classes other than two-player zero-sum, and for all games one can potentially do better by exploiting perceived weaknesses of the opponent than by following a static equilibrium strategy throughout the match. The natural setting for opponent exploitation is the Bayesian setting where we have a prior model that is integrated with observations to create a posterior opponent model that we respond to. The most natural, and a well-studied prior distribution is the Dirichlet distribution. An exact polynomial-time algorithm is known for best-responding to the posterior distribution for an opponent assuming a Dirichlet prior with multinomial sampling in normal-form games; however, for imperfect-information games the best known algorithm is based on approximating an infinite integral without theoretical guarantees. We present the first exact algorithm for a natural class of imperfect-information games. We demonstrate that our algorithm runs quickly in practice and outperforms the best prior approaches. We also present an algorithm for the uniform prior setting.
Quantum-inspired secure wireless communication protocol under spatial and local Gaussian noise assumptions
Venue: arXiv cs.IT 2018
Year: 2018

Inspired from quantum key distribution, we consider wireless communication between Alice and Bob when the intermediate space between Alice and Bob is controlled by Eve. That is, our model divides the channel noise into two parts, the noise generated during the transmission and the noise generated in the detector. Eve is allowed to control the former, but is not allowed to do the latter. While the latter is assumed to be a Gaussian random variable, the former is not assumed to be a Gaussian random variable. In this situation, using backward reconciliation and the random sampling, we propose a protocol to generate secure keys between Alice and Bob under the assumption that Eve's detector has a Gaussian noise and Eve is out of Alice's neighborhood. In our protocol, the security criteria are quantitatively guaranteed even with finite block-length code based on the evaluation of error of the estimation of channel.
Differential TD Learning for Value Function Approximation
Venue: arXiv cs.SY 2018
Year: 2018

Value functions arise as a component of algorithms as well as performance metrics in statistics and engineering applications. Computation of the associated Bellman equations is numerically challenging in all but a few special cases. A popular approximation technique is known as Temporal Difference (TD) learning. The algorithm introduced in this paper is intended to resolve two well-known problems with this approach: In the discounted-cost setting, the variance of the algorithm diverges as the discount factor approaches unity. Second, for the average cost setting, unbiased algorithms exist only in special cases. It is shown that the gradient of any of these value functions admits a representation that lends itself to algorithm design. Based on this result, the new differential TD method is obtained for Markovian models on Euclidean space with smooth dynamics. Numerical examples show remarkable improvements in performance. In application to speed scaling, variance is reduced by two orders of magnitude.
Dictator Functions Maximize Mutual Information
Venue: arXiv cs.IT 2018
Year: 2018

Let $(\mathbf X, \mathbf Y)$ denote $n$ independent, identically distributed copies of two arbitrarily correlated Rademacher random variables $(X, Y)$. We prove that the inequality $I(f(\mathbf X); g(\mathbf Y)) \le I(X; Y)$ holds for any two Boolean functions: $f,g \colon \{-1,1\}^n \to \{-1,1\}$ ($I(\cdot; \cdot)$ denotes mutual information). We further show that equality in general is achieved only by the dictator functions $f(\mathbf x)=\pm g(\mathbf x)=\pm x_i$, $i \in \{1,2,\dots,n\}$.
Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
Venue: arXiv cs.SI 2018
Year: 2018

One of the longstanding open problems in spectral graph clustering (SGC) is the so-called model order selection problem: automated selection of the correct number of clusters. This is equivalent to the problem of finding the number of connected components or communities in an undirected graph. We propose automated model order selection (AMOS), a solution to the SGC model selection problem under a random interconnection model (RIM) using a novel selection criterion that is based on an asymptotic phase transition analysis. AMOS can more generally be applied to discovering hidden block diagonal structure in symmetric non-negative matrices. Numerical experiments on simulated graphs validate the phase transition analysis, and real-world network data is used to validate the performance of the proposed model selection procedure.
Effortless Data Exploration with zenvisage: An Expressive and Interactive Visual Analytics System
Venue: arXiv cs.DB 2018
Year: 2018

Data visualization is by far the most commonly used mechanism to explore data, especially by novice data analysts and data scientists. And yet, current visual analytics tools are rather limited in their ability to guide data scientists to interesting or desired visualizations: the process of visual data exploration remains cumbersome and time-consuming. We propose zenvisage, a platform for effortlessly visualizing interesting patterns, trends, or insights from large datasets. We describe zenvisage's general purpose visual query language, ZQL ("zee-quel") for specifying the desired visual trend, pattern, or insight - ZQL draws from use-cases in a variety of domains, including biology, mechanical engineering, climate science, and commerce. We formalize the expressiveness of ZQL via a visual exploration algebra, and demonstrate that ZQL is at least as expressive as that algebra. While analysts are free to use ZQL directly, we also expose ZQL via a visual specification interface that we describe in this paper. We then describe our architecture and optimizations, preliminary experiments in supporting and optimizing for ZQL queries in our initial zenvisage prototype, and a user study to evaluate whether data scientists are able to effectively use zenvisage for real applications.
A note on the duals of skew constacyclic codes
Venue: arXiv cs.IT 2018
Year: 2018

Let $\mathbb{F}_q$ be a finite field with $q$ elements and denote by $θ: \mathbb{F}_q\to\mathbb{F}_q$ an automorphism of $\mathbb{F}_q$. In this paper, we deal with skew constacyclic codes, that is, linear codes of $\mathbb{F}_q^n$ which are invariant under the action of a semi-linear map $Φ_{α,θ}:\mathbb{F}_q^n\to\mathbb{F}_q^n$, defined by $Φ_{α,θ}(a_0,...,a_{n-2}, a_{n-1}):=(αθ(a_{n-1}),θ(a_0),...,θ(a_{n-2}))$ for some $α\in\mathbb{F}_q\setminus\{0\}$ and $n\geq 2$. In particular, we study some algebraic and geometric properties of their dual codes and we give some consequences and research results on $1$-generator skew quasi-twisted codes and on MDS skew constacyclic codes.
M$^2$S-Net: Multi-Modal Similarity Metric Learning based Deep Convolutional Network for Answer Selection
Venue: arXiv cs.CL 2018
Year: 2018

Recent works using artificial neural networks based on distributed word representation greatly boost performance on various natural language processing tasks, especially the answer selection problem. Nevertheless, most of the previous works used deep learning methods (like LSTM-RNN, CNN, etc.) only to capture semantic representation of each sentence separately, without considering the interdependence between each other. In this paper, we propose a novel end-to-end learning framework which constitutes deep convolutional neural network based on multi-modal similarity metric learning (M$^2$S-Net) on pairwise tokens. The proposed model demonstrates its performance by surpassing previous state-of-the-art systems on the answer selection benchmark, i.e., TREC-QA dataset, in both MAP and MRR metrics.
A Generic Transformation to Enable Optimal Repair in MDS Codes for Distributed Storage Systems
Venue: arXiv cs.IT 2018
Year: 2018

We propose a generic transformation that can convert any nonbinary $(n=k+r,k)$ maximum distance separable (MDS) code into another $(n,k)$ MDS code over the same field such that 1) some arbitrarily chosen $r$ nodes have the optimal repair bandwidth and the optimal rebuilding access, 2) for the remaining $k$ nodes, the normalized repair bandwidth and the normalized rebuilding access (over the file size) are preserved, 3) the sub-packetization level is increased only by a factor of $r$. Two immediate applications of this generic transformation are then presented. The first application is that we can transform any nonbinary MDS code with the optimal repair bandwidth or the optimal rebuilding access for the systematic nodes only, into a new MDS code which possesses the corresponding repair optimality for all nodes. The second application is that by applying the transformation multiple times, any nonbinary $(n,k)$ scalar MDS code can be converted into an $(n,k)$ MDS code with the optimal repair bandwidth and the optimal rebuilding access for all nodes, or only a subset of nodes, whose sub-packetization level is also optimal.
Mesh Interest Point Detection Based on Geometric Measures and Sparse Refinement
Venue: arXiv cs.CV 2018
Year: 2018

Three dimensional (3D) interest point detection plays a fundamental role in 3D computer vision and graphics. In this paper, we introduce a new method for detecting mesh interest points based on geometric measures and sparse refinement (GMSR). The key point of our approach is to calculate the 3D interest point response function using two intuitive and effective geometric properties of the local surface on a 3D mesh model, namely Euclidean distances between the neighborhood vertices to the tangent plane of a vertex and the angles of normal vectors of them. The response function is defined in multi-scale space and can be utilized to effectively distinguish 3D interest points from edges and flat areas. Those points with local maximal 3D interest point response value are selected as the candidates of 3D interest points. Finally, we utilize an $\ell_0$ norm based optimization method to refine the candidates of 3D interest points by constraining its quality and quantity. Numerical experiments demonstrate that our proposed GMSR based 3D interest point detector outperforms current several state-of-the-art methods for different kinds of 3D mesh models.