OpenRaiser/Intern-Atlas huggingface dataset:
Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems
Venue: arXiv cs.LG 2019
Year: 2019

Motivated by robust matrix recovery problems such as Robust Principal Component Analysis, we consider a general optimization problem of minimizing a smooth and strongly convex loss function applied to the sum of two blocks of variables, where each block of variables is constrained or regularized individually. We study a Conditional Gradient-Type method which is able to leverage the special structure of the problem to obtain faster convergence rates than those attainable via standard methods, under a variety of assumptions. In particular, our method is appealing for matrix problems in which one of the blocks corresponds to a low-rank matrix since it avoids prohibitive full-rank singular value decompositions required by most standard methods. While our initial motivation comes from problems which originated in statistics, our analysis does not impose any statistical assumptions on the data.
Masked Conditional Neural Networks for Automatic Sound Events Recognition
Venue: arXiv cs.LG 2019
Year: 2019

Deep neural network architectures designed for application domains other than sound, especially image recognition, may not optimally harness the time-frequency representation when adapted to the sound recognition problem. In this work, we explore the ConditionaL Neural Network (CLNN) and the Masked ConditionaL Neural Network (MCLNN) for multi-dimensional temporal signal recognition. The CLNN considers the inter-frame relationship, and the MCLNN enforces a systematic sparseness over the network's links to enable learning in frequency bands rather than bins allowing the network to be frequency shift invariant mimicking a filterbank. The mask also allows considering several combinations of features concurrently, which is usually handcrafted through exhaustive manual search. We applied the MCLNN to the environmental sound recognition problem using the ESC-10 and ESC-50 datasets. MCLNN achieved competitive performance, using 12% of the parameters and without augmentation, compared to state-of-the-art Convolutional Neural Networks.
A Systematic Study of Cross-Project Defect Prediction With Meta-Learning
Venue: arXiv cs.SE 2019
Year: 2019

The prediction of defects in a target project based on data from external projects is called Cross-Project Defect Prediction (CPDP). Several methods have been proposed to improve the predictive performance of CPDP models. However, there is a lack of comparison among state-of-the-art methods. Moreover, previous work has shown that the most suitable method for a project can vary according to the project being predicted. This makes the choice of which method to use difficult. We provide an extensive experimental comparison of 31 CPDP methods derived from state-of-the-art approaches, applied to 47 versions of 15 open source software projects. Four methods stood out as presenting the best performances across datasets. However, the most suitable among these methods still varies according to the project being predicted. Therefore, we propose and evaluate a meta-learning solution designed to automatically select and recommend the most suitable CPDP method for a project. Our results show that the meta-learning solution is able to learn from previous experiences and recommend suitable methods dynamically. When compared to the base methods, however, the proposed solution presented minor difference of performance. These results provide valuable knowledge about the possibilities and limitations of a meta-learning solution applied for CPDP.
Backlash Identification in Two-Mass Systems by Delayed Relay Feedback
Venue: arXiv cs.SY 2019
Year: 2019

Backlash, also known as mechanical play, is a piecewise differentiable nonlinearity which exists in several actuated systems, comprising, e.g., rack-and-pinion drives, shaft couplings, toothed gears, and other machine elements. Generally, the backlash is nested between the moving parts of a complex dynamic system, which handicaps its proper detection and identification. A classical example is the two-mass system which can approximate numerous mechanisms connected by a shaft (or link) with relatively high stiffness and backlash in series. Information about the presence and extent of the backlash is seldom exactly known and is rather conditional upon factors such as wear, fatigue and incipient failures in the components. This paper proposes a novel backlash identification method using one-side sensing of a two-mass system. The method is based on the delayed relay operator in feedback that allows stable and controllable limit cycles to be induced and operated within the (unknown) backlash gap. The system model, with structural transformations required for the one-side backlash measurements, is given, along with the analysis of the delayed relay in velocity feedback. Experimental evaluations are shown for a two-inertia motor bench that has coupling with backlash gap of about one degree.
Learning Data-Driven Objectives to Optimize Interactive Systems
Venue: arXiv cs.AI 2019
Year: 2019

Effective optimization is essential for interactive systems to provide a satisfactory user experience. However, it is often challenging to find an objective to optimize for. Generally, such objectives are manually crafted and rarely capture complex user needs in an accurate manner. We propose an approach that infers the objective directly from observed user interactions. These inferences can be made regardless of prior knowledge and across different types of user behavior. We introduce interactive system optimization, a novel algorithm that uses these inferred objectives for optimization. Our main contribution is a new general principled approach to optimizing interactive systems using data-driven objectives. We demonstrate the high effectiveness of interactive system optimization over several simulations.
HybridSVD: When Collaborative Information is Not Enough
Venue: arXiv cs.LG 2019
Year: 2019

We propose a new hybrid algorithm that allows incorporating both user and item side information within the standard collaborative filtering technique. One of its key features is that it naturally extends a simple PureSVD approach and inherits its unique advantages, such as highly efficient Lanczos-based optimization procedure, simplified hyper-parameter tuning and a quick folding-in computation for generating recommendations instantly even in highly dynamic online environments. The algorithm utilizes a generalized formulation of the singular value decomposition, which adds flexibility to the solution and allows imposing the desired structure on its latent space. Conveniently, the resulting model also admits an efficient and straightforward solution for the cold start scenario. We evaluate our approach on a diverse set of datasets and show its superiority over similar classes of hybrid models.
Efficient Collaborative Multi-Agent Deep Reinforcement Learning for Large-Scale Fleet Management
Venue: arXiv cs.MA 2019
Year: 2019

Large-scale online ride-sharing platforms have substantially transformed our lives by reallocating transportation resources to alleviate traffic congestion and promote transportation efficiency. An efficient fleet management strategy not only can significantly improve the utilization of transportation resources but also increase the revenue and customer satisfaction. It is a challenging task to design an effective fleet management strategy that can adapt to an environment involving complex dynamics between demand and supply. Existing studies usually work on a simplified problem setting that can hardly capture the complicated stochastic demand-supply variations in high-dimensional space. In this paper we propose to tackle the large-scale fleet management problem using reinforcement learning, and propose a contextual multi-agent reinforcement learning framework including three concrete algorithms to achieve coordination among a large number of agents adaptive to different contexts. We show significant improvements of the proposed framework over state-of-the-art approaches through extensive empirical studies.
Convexity-Increasing Morphs of Planar Graphs
Venue: arXiv cs.CG 2019
Year: 2019

We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one with strictly convex faces while maintaining planarity at all times. Our morph is convexity-increasing, meaning that once an angle is convex, it remains convex. We give an efficient algorithm that constructs such a morph as a composition of a linear number of steps where each step either moves vertices along horizontal lines or moves vertices along vertical lines. Moreover, we show that a linear number of steps is worst-case optimal. To obtain our result, we use a well-known technique by Hong and Nagamochi for finding redrawings with convex faces while preserving y-coordinates. Using a variant of Tutte's graph drawing algorithm, we obtain a new proof of Hong and Nagamochi's result which comes with a better running time. This is of independent interest, as Hong and Nagamochi's technique serves as a building block in existing morphing algorithms.
Simultaneous Compression and Quantization: A Joint Approach for Efficient Unsupervised Hashing
Venue: arXiv cs.CV 2019
Year: 2019

For unsupervised data-dependent hashing, the two most important requirements are to preserve similarity in the low-dimensional feature space and to minimize the binary quantization loss. A well-established hashing approach is Iterative Quantization (ITQ), which addresses these two requirements in separate steps. In this paper, we revisit the ITQ approach and propose novel formulations and algorithms to the problem. Specifically, we propose a novel approach, named Simultaneous Compression and Quantization (SCQ), to jointly learn to compress (reduce dimensionality) and binarize input data in a single formulation under strict orthogonal constraint. With this approach, we introduce a loss function and its relaxed version, termed Orthonormal Encoder (OnE) and Orthogonal Encoder (OgE) respectively, which involve challenging binary and orthogonal constraints. We propose to attack the optimization using novel algorithms based on recent advances in cyclic coordinate descent approach. Comprehensive experiments on unsupervised image retrieval demonstrate that our proposed methods consistently outperform other state-of-the-art hashing methods. Notably, our proposed methods outperform recent deep neural networks and GAN based hashing in accuracy, while being very computationally-efficient.
Analysis of cause-effect inference by comparing regression errors
Venue: arXiv cs.AI 2019
Year: 2019

We address the problem of inferring the causal direction between two variables by comparing the least-squares errors of the predictions in both possible directions. Under the assumption of an independence between the function relating cause and effect, the conditional noise distribution, and the distribution of the cause, we show that the errors are smaller in causal direction if both variables are equally scaled and the causal relation is close to deterministic. Based on this, we provide an easily applicable algorithm that only requires a regression in both possible causal directions and a comparison of the errors. The performance of the algorithm is compared with various related causal inference methods in different artificial and real-world data sets.
Distributed Recoloring
Venue: arXiv cs.DC 2019
Year: 2019

Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. We are interested in the following questions: How many communication rounds are needed (in the LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier? The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, $3$-regular graphs, and toroidal grids.
CATTmew: Defeating Software-only Physical Kernel Isolation
Venue: arXiv cs.CR 2019
Year: 2019

All the state-of-the-art rowhammer attacks can break the MMU-enforced inter-domain isolation because the physical memory owned by each domain is adjacent to each other. To mitigate these attacks, physical domain isolation, introduced by CATT, physically separates each domain by dividing the physical memory into multiple partitions and keeping each partition occupied by only one domain. CATT implemented physical kernel isolation as the first generic and practical software-only defense to protect kernel from being rowhammered as kernel is one of the most appealing targets. In this paper, we develop a novel exploit that could effectively defeat the physical kernel isolation and gain both root and kernel privileges. Our exploit can work without exhausting the page cache or the system memory, or relying on the information of the virtual-to-physical address mapping. The exploit is motivated by our key observation that the modern OSes have double-owned kernel buffers (e.g., video buffers and SCSI Generic buffers) owned concurrently by the kernel and user domains. The existence of such buffers invalidates the physical kernel isolation and makes the rowhammer-based attack possible again. Existing conspicuous rowhammer attacks achieving the root/kernel privilege escalation exhaust the page cache or even the whole system memory. Instead, we propose a new technique, named memory ambush. It is able to place the hammerable double-owned kernel buffers physically adjacent to the target objects (e.g., page tables) with only a small amount of memory. As a result, our exploit is stealthier and has fewer memory footprints. We also replace the inefficient rowhammer algorithm that blindly picks up addresses to hammer with an efficient one. Our algorithm selects suitable addresses based on an existing timing channel.
Temporal Vertex Cover with a Sliding Time Window
Venue: arXiv cs.CC 2019
Year: 2019

Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph $G$, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge of $G$, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs has focused on the notion of a temporal path and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal graph problems. In this paper, motivated by applications in sensor and in transportation networks, we introduce and study two natural temporal extensions of the classical problem Vertex Cover. In both cases we wish to minimize the total number of "vertex appearances" that are needed to "cover" the whole temporal graph. In our first problem, Temporal Vertex Cover, the aim is to cover every edge at least once during the lifetime of the temporal graph, where an edge can be covered by one of its endpoints, only at a time step when it is active. In our second, more pragmatic variation Sliding Window Temporal Vertex Cover, we are also given a natural number $Δ$, and our aim is to cover every edge at least once at every $Δ$ consecutive time steps. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. In particular, we provide strong hardness results, complemented by various approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions.
Degrees of extensionality in the theory of Böhm trees and Sallé's conjecture
Venue: arXiv cs.LO 2019
Year: 2019

The main observational equivalences of the untyped lambda-calculus have been characterized in terms of extensional equalities between Böhm trees. It is well known that the lambda-theory H*, arising by taking as observables the head normal forms, equates two lambda-terms whenever their Böhm trees are equal up to countably many possibly infinite eta-expansions. Similarly, two lambda-terms are equal in Morris's original observational theory H+, generated by considering as observable the beta-normal forms, whenever their Böhm trees are equal up to countably many finite eta-expansions. The lambda-calculus also possesses a strong notion of extensionality called "the omega-rule", which has been the subject of many investigations. It is a longstanding open problem whether the equivalence B-omega obtained by closing the theory of Böhm trees under the omega-rule is strictly included in H+, as conjectured by Sallé in the seventies. In this paper we demonstrate that the two aforementioned theories actually coincide, thus disproving Sallé's conjecture. The proof technique we develop for proving the latter inclusion is general enough to provide as a byproduct a new characterization, based on bounded eta-expansions, of the least extensional equality between Böhm trees. Together, these results provide a taxonomy of the different degrees of extensionality in the theory of Böhm trees.
Universal Growth in Production Economies
Venue: arXiv cs.GT 2019
Year: 2019

We consider a simple variant of the von Neumann model of an expanding economy, in which multiple producers make goods according to their production function. The players trade their goods at the market and then use the bundles acquired for the production in the next round. We study a simple decentralized dynamic---known as proportional response---in which players update their bids proportionally to how useful the investments were in the past round. We show this dynamic leads to growth of the economy in the long term (whenever growth is possible) but also creates unbounded inequality, i.e. very rich and very poor players emerge. We analyze several other phenomena, such as how the relation of a player with others influences its development and the Gini index of the system. One of the key technical findings is that the players learn a global feature of the network (the optimal cycle) in a decentralized way, while interacting locally with their direct neighbors. We obtain this by studying the volume in the resulting dynamical system and showing that the volume of each cycle expands or contracts by a constant factor in each round.
A New Design of Binary MDS Array Codes with Asymptotically Weak-Optimal Repair
Venue: arXiv cs.IT 2019
Year: 2019

Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provide fault tolerance with minimum storage redundancy but also achieve low computational complexity. They are constructed by encoding $k$ information columns into $r$ parity columns, in which each element in a column is a bit, such that any $k$ out of the $k+r$ columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance in practical applications. Specifically, if a single column fails, our goal is to minimize the repair bandwidth by downloading the least amount of bits from $d$ healthy columns, where $k\leq d\leq k+r-1$. If one column of an MDS code is failed, it is known that we need to download at least $1/(d-k+1)$ fraction of the data stored in each of $d$ healthy columns. If this lower bound is achieved for the repair of the failure column from accessing arbitrary $d$ healthy columns, we say that the MDS code has optimal repair. However, if such lower bound is only achieved by $d$ specific healthy columns, then we say the MDS code has weak-optimal repair. In this paper, we propose two explicit constructions of binary MDS array codes with more parity columns (i.e., $r\geq 3$) that achieve asymptotically weak-optimal repair, where $k+1\leq d\leq k+\lfloor(r-1)/2\rfloor$, and "asymptotic" means that the repair bandwidth achieves the minimum value asymptotically in $d$. Codes in the first construction have odd number of parity columns and asymptotically weak-optimal repair for any one information failure, while codes in the second construction have even number of parity columns and asymptotically weak-optimal repair for any one column failure.
A New Foundation for Finitary Corecursion and Iterative Algebras
Venue: arXiv cs.LO 2019
Year: 2019

This paper contributes to a theory of the behaviour of "finite-state" systems that is generic in the system type. We propose that such systems are modelled as coalgebras with a finitely generated carrier for an endofunctor on a locally finitely presentable category. Their behaviour gives rise to a new fixpoint of the coalgebraic type functor called locally finite fixpoint (LFF). We prove that if the given endofunctor is finitary and preserves monomorphisms then the LFF always exists and is a subcoalgebra of the final coalgebra (unlike the rational fixpoint previously studied by Adámek, Milius, and Velebil). Moreover, we show that the LFF is characterized by two universal properties: (1) as the final locally finitely generated coalgebra, and (2) as the initial fg-iterative algebra. As instances of the LFF we first obtain the known instances of the rational fixpoint, e.g. regular languages, rational streams and formal power-series, regular trees etc. Moreover, we obtain a number of new examples, e.g. (realtime deterministic resp. non-deterministic) context-free languages, constructively S-algebraic formal power-series (in general, the behaviour of finite coalgebras under the coalgebraic language semantics arising from the generalized powerset construction by Silva, Bonchi, Bonsangue, and Rutten), and the monad of Courcelle's algebraic trees.
A Cut-And-Choose Mechanism to Prevent Gerrymandering
Venue: arXiv cs.GT 2019
Year: 2019

This paper presents a novel mechanism to endogenously determine the fair division of a state into electoral districts in a two-party setting. No geometric constraints are imposed on voter distributions or district shapes; instead, it is assumed that any partition of the population into districts of equal population is feasible. One party divides the map, then the other party chooses a minimum threshold level of support needed to win a district. Districts in which neither party meets this threshold are awarded randomly. Despite the inherent asymmetry, the equilibria of this mechanism always yield fair outcomes, up to integer rounding.