OpenRaiser/Intern-Atlas huggingface dataset:
Simplification of multibody models by parameter reduction
Venue: arXiv cs.RO 2017
Year: 2017

Model selection methods are used in different scientific contexts to represent a characteristic data set in terms of a reduced number of parameters. Apparently, these methods have not found their way into the literature on multibody systems dynamics. Multibody models can be considered parametric models in terms of their dynamic parameters, and model selection techniques can then be used to express these models in terms of a reduced number of parameters. These parameter-reduced models are expected to have a smaller computational complexity than the original one and still preserve the desired level of accuracy. They are also known to be good candidates for parameter estimation purposes. In this work, simulations of the actual model are used to define a data set that is representative of the system's standard working conditions. A parameter-reduced model is chosen and its parameter values estimated so that they minimize the prediction error on these data. To that end, model selection heuristics and normalized error measures are proposed. Using this methodology, two multibody systems with very different characteristic mobility are analyzed. Highly considerable reductions in the number of parameters and computational cost are obtained without compromising the accuracy of the reduced model too much. As an additional result, a generalization of the base parameter concept to the context of parameter-reduced models is proposed.
Dependency-Aware Rollback and Checkpoint-Restart for Distributed Task-Based Runtimes
Venue: arXiv cs.DC 2017
Year: 2017

With the increase in compute nodes in large compute platforms, a proportional increase in node failures will follow. Many application-based checkpoint/restart (C/R) techniques have been proposed for MPI applications to target the reduced mean time between failures. However, rollback as part of the recovery remains a dominant cost even in highly optimised MPI applications employing C/R techniques. Continuing execution past a checkpoint (that is, reducing rollback) is possible in message-passing runtimes, but extremely complex to design and implement. Our work focuses on task-based runtimes, where task dependencies are explicit and message passing is implicit. We see an opportunity for reducing rollback for such runtimes: we explore task dependencies in the rollback, which we call dependency-aware rollback. We also design a new C/R technique, which is influenced by recursive decomposition of tasks, and combine it with dependency-aware rollback. We expect the dependency-aware rollback to cancel and recompute less tasks in the presence of node failures. We describe, implement and validate the proposed protocol in a simulator, which confirms these expectations. In addition, we consistently observe faster overall execution time for dependency-aware rollback in the presence of faults, despite the fact that reduced task cancellation does not guarantee reduced overall execution time.
Understanding Reduced-Voltage Operation in Modern DRAM Chips: Characterization, Analysis, and Mechanisms
Venue: arXiv cs.AR 2017
Year: 2017

The energy consumption of DRAM is a critical concern in modern computing systems. Improvements in manufacturing process technology have allowed DRAM vendors to lower the DRAM supply voltage conservatively, which reduces some of the DRAM energy consumption. We would like to reduce the DRAM supply voltage more aggressively, to further reduce energy. Aggressive supply voltage reduction requires a thorough understanding of the effect voltage scaling has on DRAM access latency and DRAM reliability. In this paper, we take a comprehensive approach to understanding and exploiting the latency and reliability characteristics of modern DRAM when the supply voltage is lowered below the nominal voltage level specified by DRAM standards. Using an FPGA-based testing platform, we perform an experimental study of 124 real DDR3L (low-voltage) DRAM chips manufactured recently by three major DRAM vendors. We find that reducing the supply voltage below a certain point introduces bit errors in the data, and we comprehensively characterize the behavior of these errors. We discover that these errors can be avoided by increasing the latency of three major DRAM operations (activation, restoration, and precharge). We perform detailed DRAM circuit simulations to validate and explain our experimental findings. We also characterize the various relationships between reduced supply voltage and error locations, stored data patterns, DRAM temperature, and data retention. Based on our observations, we propose a new DRAM energy reduction mechanism, called Voltron. The key idea of Voltron is to use a performance model to determine by how much we can reduce the supply voltage without introducing errors and without exceeding a user-specified threshold for performance loss. Voltron reduces the average system energy by 7.3% while limiting the average system performance loss to only 1.8%, for a variety of workloads.
Fast Trajectory Optimization for Legged Robots using Vertex-based ZMP Constraints
Venue: arXiv cs.RO 2017
Year: 2017

This paper combines the fast Zero-Moment-Point (ZMP) approaches that work well in practice with the broader range of capabilities of a Trajectory Optimization formulation, by optimizing over body motion, footholds and Center of Pressure simultaneously. We introduce a vertex-based representation of the support-area constraint, which can treat arbitrarily oriented point-, line-, and area-contacts uniformly. This generalization allows us to create motions such quadrupedal walking, trotting, bounding, pacing, combinations and transitions between these, limping, bipedal walking and push-recovery all with the same approach. This formulation constitutes a minimal representation of the physical laws (unilateral contact forces) and kinematic restrictions (range of motion) in legged locomotion, which allows us to generate various motion in less than a second. We demonstrate the feasibility of the generated motions on a real quadruped robot.
Optimal-Time Text Indexing in BWT-runs Bounded Space
Venue: arXiv cs.DS 2017
Year: 2017

Indexing highly repetitive texts --- such as genomic databases, software repositories and versioned text collections --- has become an important problem since the turn of the millennium. A relevant compressibility measure for repetitive texts is $r$, the number of runs in their Burrows-Wheeler Transform (BWT). One of the earliest indexes for repetitive collections, the Run-Length FM-index, used $O(r)$ space and was able to efficiently count the number of occurrences of a pattern of length $m$ in the text (in loglogarithmic time per pattern symbol, with current techniques). However, it was unable to locate the positions of those occurrences efficiently within a space bounded in terms of $r$. Since then, a number of other indexes with space bounded by other measures of repetitiveness --- the number of phrases in the Lempel-Ziv parse, the size of the smallest grammar generating the text, the size of the smallest automaton recognizing the text factors --- have been proposed for efficiently locating, but not directly counting, the occurrences of a pattern. In this paper we close this long-standing problem, showing how to extend the Run-Length FM-index so that it can locate the $occ$ occurrences efficiently within $O(r)$ space (in loglogarithmic time each), and reaching optimal time $O(m+occ)$ within $O(r\log(n/r))$ space, on a RAM machine of $w=Ω(\log n)$ bits. Within $O(r\log (n/r))$ space, our index can also count in optimal time $O(m)$. Raising the space to $O(r w\log_σ(n/r))$, we support count and locate in $O(m\log(σ)/w)$ and $O(m\log(σ)/w+occ)$ time, which is optimal in the packed setting and had not been obtained before in compressed space. We also describe a structure using $O(r\log(n/r))$ space that replaces the text and extracts any text substring of length $\ell$ in almost-optimal time $O(\log(n/r)+\ell\log(σ)/w)$. (...continues...)
Optimization of circuitry arrangements for heat exchangers using derivative-free optimization
Venue: arXiv cs.CE 2017
Year: 2017

Optimization of the refrigerant circuitry can improve a heat exchanger's performance. Design engineers currently choose the refrigerant circuitry according to their experience and heat exchanger simulations. However, the design of an optimized refrigerant circuitry is difficult. The number of refrigerant circuitry candidates is enormous. Therefore, exhaustive search algorithms cannot be used and intelligent techniques must be developed to explore the solution space efficiently. In this paper, we formulate refrigerant circuitry design as a binary constrained optimization problem. We use CoilDesigner, a simulation and design tool of air to refrigerant heat exchangers, in order to simulate the performance of different refrigerant circuitry designs. We treat CoilDesigner as a black-box system since the exact relationship of the objective function with the decision variables is not explicit. Derivative-free optimization (DFO) algorithms are suitable for solving this black-box model since they do not require explicit functional representations of the objective function and the constraints. The aim of this paper is twofold. First, we compare four mixed-integer constrained DFO solvers and one box-bounded DFO solver and evaluate their ability to solve a difficult industrially relevant problem. Second, we demonstrate that the proposed formulation is suitable for optimizing the circuitry configuration of heat exchangers. We apply the DFO solvers to 17 heat exchanger design problems. Results show that TOMLAB/glcDirect and TOMLAB/glcSolve can find optimal or near-optimal refrigerant circuitry designs after a relatively small number of circuit simulations.
Diversity Combining for RF Energy Harvesting
Venue: arXiv cs.IT 2017
Year: 2017

RF energy harvesting (RFEH) is a promising technology for energy requirements of wireless communication nodes. However, providing sufficient amount of energy to ensure self-sufficient devices based on RFEH may be challenging. In this paper, the use of diversity combining in RFEH systems is proposed to increase the amount of harvested energy. The power consumption of diversity combining process is also taken into account to analyze the net benefit of diversity combining. Performances of RFEH systems are investigated for selection combining (SC), equal gain combining (EGC), and maximal ratio combining (MRC) techniques. Simulations are conducted to compare the numerical results of SC, EGC, and MRC, and the results show that although the diversity combining techniques can improve the energy harvesting performance, the power consumption parameters have a critical importance while determining the suitable technique.
Decorrelation of Neutral Vector Variables: Theory and Applications
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose novel strategies for neutral vector variable decorrelation. Two fundamental invertible transformations, namely serial nonlinear transformation and parallel nonlinear transformation, are proposed to carry out the decorrelation. For a neutral vector variable, which is not multivariate Gaussian distributed, the conventional principal component analysis (PCA) cannot yield mutually independent scalar variables. With the two proposed transformations, a highly negatively correlated neutral vector can be transformed to a set of mutually independent scalar variables with the same degrees of freedom. We also evaluate the decorrelation performances for the vectors generated from a single Dirichlet distribution and a mixture of Dirichlet distributions. The mutual independence is verified with the distance correlation measurement. The advantages of the proposed decorrelation strategies are intensively studied and demonstrated with synthesized data and practical application evaluations.
Constrained Policy Optimization
Venue: arXiv cs.LG 2017
Year: 2017

For many applications of reinforcement learning it can be more convenient to specify both a reward function and constraints, rather than trying to design behavior through the reward function. For example, systems that physically interact with or around humans should satisfy safety constraints. Recent advances in policy search algorithms (Mnih et al., 2016, Schulman et al., 2015, Lillicrap et al., 2016, Levine et al., 2016) have enabled new capabilities in high-dimensional control, but do not consider the constrained setting. We propose Constrained Policy Optimization (CPO), the first general-purpose policy search algorithm for constrained reinforcement learning with guarantees for near-constraint satisfaction at each iteration. Our method allows us to train neural network policies for high-dimensional control while making guarantees about policy behavior all throughout training. Our guarantees are based on a new theoretical result, which is of independent interest: we prove a bound relating the expected returns of two policies to an average divergence between them. We demonstrate the effectiveness of our approach on simulated robot locomotion tasks where the agent must satisfy constraints motivated by safety.
A Receding Horizon Push Recovery Strategy for Balancing the iCub Humanoid Robot
Venue: arXiv cs.RO 2017
Year: 2017

Balancing and reacting to strong and unexpected pushes is a critical requirement for humanoid robots. We recently designed a capture point based approach which interfaces with a momentum-based torque controller and we implemented and validated it on the iCub humanoid robot. In this work we implement a Receding Horizon control, also known as Model Predictive Control, to add the possibility to predict the future evolution of the robot, especially the constraints switching given by the hybrid nature of the system. We prove that the proposed MPC extension makes the step-recovery controller more robust and reliable when executing the recovery strategy. Experiments in simulation show the results of the proposed approach.
Fast Computation of the Roots of Polynomials Over the Ring of Power Series
Venue: arXiv cs.SC 2017
Year: 2017

We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field $\mathbb{K}$. More precisely, given a precision $d$, and a polynomial $Q$ whose coefficients are power series in $x$, the algorithm computes a representation of all power series $f(x)$ such that $Q(f(x)) = 0 \bmod x^d$. The algorithm works unconditionally, in particular also with multiple roots, where Newton iteration fails. Our main motivation comes from coding theory where instances of this problem arise and multiple roots must be handled. The cost bound for our algorithm matches the worst-case input and output size $d °(Q)$, up to logarithmic factors. This improves upon previous algorithms which were quadratic in at least one of $d$ and $°(Q)$. Our algorithm is a refinement of a divide \& conquer algorithm by Alekhnovich (2005), where the cost of recursive steps is better controlled via the computation of a factor of $Q$ which has a smaller degree while preserving the roots.
Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness
Venue: arXiv cs.GT 2017
Year: 2017

We study the mechanism design problem of allocating a set of indivisible items without monetary transfers. Despite the vast literature on this very standard model, it still remains unclear how do truthful mechanisms look like. We focus on the case of two players with additive valuation functions and our purpose is twofold. First, our main result provides a complete characterization of truthful mechanisms that allocate all the items to the players. Our characterization reveals an interesting structure underlying all truthful mechanisms, showing that they can be decomposed into two components: a selection part where players pick their best subset among prespecified choices determined by the mechanism, and an exchange part where players are offered the chance to exchange certain subsets if it is favorable to do so. In the remaining paper, we apply our main result and derive several consequences on the design of mechanisms with fairness guarantees. We consider various notions of fairness, (indicatively, maximin share guarantees and envy-freeness up to one item) and provide tight bounds for their approximability. Our work settles some of the open problems in this agenda, and we conclude by discussing possible extensions to more players.
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
Venue: arXiv cs.DS 2017
Year: 2017

Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp., vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge- and 2-vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with $\widetilde{O}(mn)$ time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced $O(n^2)$ time algorithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time $O(m^{3/2})$, which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k-connectivity for $k>2$. For constant values of k, we extend one of our algorithms to compute the maximal k-edge-connected in time $O(m^{3/2} \log{n})$, improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in $O(n^2 \log n)$ time.
Knowledge Base Completion: Baselines Strike Back
Venue: arXiv cs.LG 2017
Year: 2017

Many papers have been published on the knowledge base completion task in the past few years. Most of these introduce novel architectures for relation learning that are evaluated on standard datasets such as FB15k and WN18. This paper shows that the accuracy of almost all models published on the FB15k can be outperformed by an appropriately tuned baseline - our reimplementation of the DistMult model. Our findings cast doubt on the claim that the performance improvements of recent models are due to architectural changes as opposed to hyper-parameter tuning or different training objectives. This should prompt future research to re-consider how the performance of models is evaluated and reported.
A Low Dimensionality Representation for Language Variety Identification
Venue: arXiv cs.CL 2017
Year: 2017

Language variety identification aims at labelling texts in a native language (e.g. Spanish, Portuguese, English) with its specific variation (e.g. Argentina, Chile, Mexico, Peru, Spain; Brazil, Portugal; UK, US). In this work we propose a low dimensionality representation (LDR) to address this task with five different varieties of Spanish: Argentina, Chile, Mexico, Peru and Spain. We compare our LDR method with common state-of-the-art representations and show an increase in accuracy of ~35%. Furthermore, we compare LDR with two reference distributed representation models. Experimental results show competitive performance while dramatically reducing the dimensionality --and increasing the big data suitability-- to only 6 features per variety. Additionally, we analyse the behaviour of the employed machine learning algorithms and the most discriminating features. Finally, we employ an alternative dataset to test the robustness of our low dimensionality representation with another set of similar languages.
Forward-Backward Selection with Early Dropping
Venue: arXiv cs.LG 2017
Year: 2017

Forward-backward selection is one of the most basic and commonly-used feature selection algorithms available. It is also general and conceptually applicable to many different types of data. In this paper, we propose a heuristic that significantly improves its running time, while preserving predictive accuracy. The idea is to temporarily discard the variables that are conditionally independent with the outcome given the selected variable set. Depending on how those variables are reconsidered and reintroduced, this heuristic gives rise to a family of algorithms with increasingly stronger theoretical guarantees. In distributions that can be faithfully represented by Bayesian networks or maximal ancestral graphs, members of this algorithmic family are able to correctly identify the Markov blanket in the sample limit. In experiments we show that the proposed heuristic increases computational efficiency by about two orders of magnitude in high-dimensional problems, while selecting fewer variables and retaining predictive performance. Furthermore, we show that the proposed algorithm and feature selection with LASSO perform similarly when restricted to select the same number of variables, making the proposed algorithm an attractive alternative for problems where no (efficient) algorithm for LASSO exists.
PCM-TV-TFV: A Novel Two Stage Framework for Image Reconstruction from Fourier Data
Venue: arXiv cs.CV 2017
Year: 2017

We propose in this paper a novel two-stage Projection Correction Modeling (PCM) framework for image reconstruction from (non-uniform) Fourier measurements. PCM consists of a projection stage (P-stage) motivated by the multi-scale Galerkin method and a correction stage (C-stage) with an edge guided regularity fusing together the advantages of total variation (TV) and total fractional variation (TFV). The P-stage allows for continuous modeling of the underlying image of interest. The given measurements are projected onto a space in which the image is well represented. We then enhance the reconstruction result at the C-stage that minimizes an energy functional consisting of a fidelity in the transformed domain and a novel edge guided regularity. We further develop efficient proximal algorithms to solve the corresponding optimization problem. Various numerical results in both 1D signals and 2D images have also been presented to demonstrate the superior performance of the proposed two-stage method to other classical one-stage methods.
Generic Tubelet Proposals for Action Localization
Venue: arXiv cs.CV 2017
Year: 2017

We develop a novel framework for action localization in videos. We propose the Tube Proposal Network (TPN), which can generate generic, class-independent, video-level tubelet proposals in videos. The generated tubelet proposals can be utilized in various video analysis tasks, including recognizing and localizing actions in videos. In particular, we integrate these generic tubelet proposals into a unified temporal deep network for action classification. Compared with other methods, our generic tubelet proposal method is accurate, general, and is fully differentiable under a smoothL1 loss function. We demonstrate the performance of our algorithm on the standard UCF-Sports, J-HMDB21, and UCF-101 datasets. Our class-independent TPN outperforms other tubelet generation methods, and our unified temporal deep network achieves state-of-the-art localization results on all three datasets.